강화 학습(RL)_ MDP
Markov Decision Process
이번 포스팅은 지난 Introduction에 이어 마르코프 결정 과정(MDP, Markov Decision Process)에 대해서 다루어 보려고 합니다.
지난 포스팅에서는 강화 학습의 기본 구조를 다루어 보았는데, Agent인 컴퓨터는 환경(Environment)과 상호작용(Interaction)하면서 받는 보상(Reward)을 통해 학습하게 된다는 것을 알았습니다.
Figure 1. The Agent-Environment Interaction어떤 문제를 컴퓨터가 풀기 위해서는 수학적으로 정의되어 있어야 하는데, 마르코프 결정 과정(MDP)은 이때 의사결정 과정을 모델링하는 틀을 제공합니다.
마르코프 결정 과정은 ( S, A, P, R, γ )로 표현되며, 마르코프 프로세스(Markov Process) or 마르코프 연쇄(Markov Chain) 또는 마르코프 보상 과정(Markov Reward Process)의 확장된 형태로 볼 수 있다.
Markov Process를 먼저 확인해보면,
A Markov Process is a random process, as sequence of random states S1, S2,... Sn with the Markov property
Markov Process는 상태(State, S)와 상태 이행 확률(Probability, P)로 구성되며, P는 상태 s에서 s'으로 전이될 확률을 말한다.
(Markov property는 현재가 주어졌을 때, 미래는 과거에 대해 독립인 것을 말한다. )
아래 그림은 어떤 문장을 Markov chain 형식으로 나타낸 것이다.
She is bad라는 문장과 She is good라는 문장이 있을 때, She 다음에는 is가 올 확률은 100%, 즉 1.0이다. 하지만 is 뒤에 bad 또는 good이 올 수 있으며 이는 확률 P로 표현된다.
Figure 2. Markov Chain Example다음과 같이 문장 세 개가 있다고 하자.
She is a good person.
He is a bad person.
The movie is good.
이를 State transition matrix, 상태 이행 확률 행렬로 나타내면 다음과 같이 표현된다.
Figure 3. State Transition Matrix즉, 각 단어를 하나의 상태로 보며 순차적으로 진행된다고 할 때,
'She'라는 단어 뒤에는 무조건 'is' 가 오기 때문에 1.0,
'is'라는 단어 뒤에는 'a' 가 2번, 'good' 가 한번 왔기 때문에, 'a' 가 0.66, 'good' 가 0.33을 갖게 된다.
이번에는 더 확장하여 보상(Reward)과 감가율(Discount Factor)을 추가하여 마르코프 보상 과정(Markov Reward Process)을 살펴보겠습니다.
A Markov Reward Process is a Markov chain with values
Figure 4. Markov Reward Process Example위 그림은 Markov chain에 보상(R)을 추가하여 Reward Process를 나타낸 것이다.
Reward Process에 대해서 알아보기 전에, 보상과 감가율에 대해서 먼저 다루어 보면,
Reward is passed from environment to the agent at each time step
Reward Hypothesis
A reward is a scalar feedback signal
Goals and purposes can be thought as the maximization of the expected cumulative reward
즉, 보상은 Agent가 환경으로부터 매 step이 진행될 때마다 받는 스칼라 값으로, 이를 최대화하는 것을 목표로 한다.
감가율(Discount Factor)은 경제용어 중 할인율과 비슷한 개념으로 미래의 가치를 현재의 가치로 환산하는 것이라 볼 수 있다.
예를 들면, 지금 당장 만원을 받는 것과 10년 뒤 만원을 받는 것 중 고르라면, 당신은 지금 당장 만원을 받는 것을 고를 것이다. 왜냐하면, 지금 당장 받으면 기분이 좋을 뿐 아니라 훨씬 이득이기 때문이다. 미래의 만원과 현재의 만원은 그 '가치'가 다르기 때문에 이를 맞추는 것을 감가율로 볼 수 있다.
Discount Factor, γ 는 0과 1 사이의 값을 가지기 때문에, 보상(R)에 곱해지면 보상이 감소한다.
보상과 감가율을 통해 얻게 되는 것이 Discounted return(G)로 time-step t 동안의 보상들에 대해 감가율을 고려하여 모두 더한 것을 Gt라 한다.
Discounted return Gt is the total discounted reward from time-step t
The γ determines the discount rate of the future rewards
If γ close to 0, it leads to 'myopic'(근시안적인) evaluation --> 거의 다음 단계까지만 고려
If γ close to 1, it leads to 'far-sighted' evaluation --> 모든 reward를 고려( γ ≒ 1)
Discount를 하는 두 가지 이유에 대해서 살펴보면,
Figure 5. Why discount(1)
Figure 6. Why discount(2)즉, 등비수열 합의 형식으로 수학적으로 나타내기 편리하며, 미래의 불확실성으로 인해 미래의 가치는 떨어지며, 인간은 당장의 보상을 선호하는 경향이 있기 때문이다.
따라서 마르코프 보상 과정은 ( S, P, R, γ )로 표현되며 위의 MRP 그림처럼 표현이 가능해진다.
Agent가 State s에서 s'으로 움직이게 되면 보상이 따라오게 되는데, 이를 통해 어떤 state로 움직이는 것이 가장 최고의 보상을 얻는 방법인지를 학습하게 된다. 따라서 각 state마다 보상에 대한 기댓값이 정해지게 되는데 이를 'Value function of a state', 즉 특정 상태에서의 가치 함수로 표현할 수 있다.
정의는 다음과 같다.
즉, 어떤 상태 s에서의 가치 함수는, 어떤 상태 s에서의 discounted return의 기댓값이다.
이를 다음의 episode에 대해서 적용해 보겠습니다.
She is good
She is bad
Figure 7. Markov Reward Process Example두 개의 문장이 있을 때, She라는 state가 갖는 value는 다음과 같이 계산된다. (이때, gamma = 0.5라고 가정)
이므로,
She -> is -> bad -> (end)의 경로의 경우
She -> is -> good -> (end)의 경로의 경우
이므로,
가 된다.
따라서 'She' state에 대한 value function 값은 0이다. 이처럼 모든 state에 대한 value를 구할 수 있게 된다.
각 state에서 어떤 state로 agent가 움직이는 것을 action이라 하는데, 이 action까지 추가하면 MDP, Markov Decision Process가 된다.
정리하면, MDP란 순차적 행동 결정 문제를 수학적으로 정의하는 것으로 상태, 행동, 상태 전이 확률, 보상, 감가율로 구성된다.
순차적 행동 결정 문제를 푼다는 것은 각 상태에서 최적의 행동을 찾는 것으로 더 좋은 정책을 찾는 과정을 말한다.
Markov Decision Process는 다음과 같이 표현된다
Figure 8. Markov Decision Process Example앞서 정의된 가치 함수(value function)인 v(s)에 대해 식을 약간 변형해 보겠습니다.
Figure 9. Value Function to Recursive Form식의 중간에 등장하는 Discounted Return 항을 풀어쓰게 되면, 공통 인자인 discount factor로 묶어 recursive 한 형식으로 나타낼 수 있다
이를, Bellman Equation(벨만 방정식)이라 하고, 현재 상태의 가치 함수와 다음 상태의 가치 함수의 관계를 식으로 나타낸 것이다.
여기까지는 가치 함수를 정의할 때 정책을 고려하지 않습니다. 여기서 정책(policy)란, 어떤 상태에서 Agent가 취할 행동을 말합니다.
다음 시간에는 정책(Policy)에 대해서 더 알아보도록 하고, 이와 함께 Bellman expectation Equation(벨만 기대 방정식)과 Bellman optimality equation(벨만 최적 방정식)에 대해서 다루겠습니다.
Additional References
Myerson, J., & Green, L. (1995). Discounting of delayed rewards: Models of individual choice. Journal of the Experimental Analysis of Behavior, 64(3), 263-276
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons
[2018년 가을학기에 서울대학교에서 열린 "컴퓨터 언어학 연습(강화 학습을 이용한 자연어 처리)" 수업의 수업자료도 함께 참고하였습니다]
구독과 라이킷, 댓글과 공유는 작가에게 큰 힘이 됩니다.
