News & Events
[Reinforcement Learning] 4. Markov Decision Processes (2)
3. Markov Decision Process
이전까지 살펴보았던 Markov reward process 에 의사결정에 대한 개념을 더 추가합니다. 이를 Markov decision process (MDP) 라고 합니다. 당연히 모든 state가 Markov 인 환경에서 이루어집니다.
A 라고 하는 action이 가능한 집합을 표현하는 notation이 하나가 더 추가가 되었습니다. 이를 통해서 현재 상태 s 에서 a 라고 하는 action을 할 때 다음 상태 s’ 로 가게 될 확률을 P 에 대한 내용으로 표현을 하게 됩니다.
R 도 reward 에 대한 함수인데 마찬가지로 현재 상태 s 에서 a 라는 action을 할때 기대되어지는 보상을 표현하게 됩니다.
그외 나머지는 이전 내용과 동일하니까 생략합니다.
다시 이전에 사용했던 학생 예제를 살펴보면, class 1 의 상태에서 할 수 있는 action 은 study, facebook이 될 겁니다. 만약 study라는 action을 취한다면 reward 를 -2 얻고 다음 state인 class 2로 이동하게 되겠습니다.
facebook이라는 행동을 취했다면 reward를 -1 얻고 다음 상태인 facebook으로 이동하게 되겠지요. 여기서는 다시 facebook 과 quit 이라는 action을 취하여 state를 transition하게 될 것입니다.
용어를 다르게 사용했는데 결국은 같은 의미입니다.
이번에는 policy 에 대해서 살펴보겠습니다. policy는 agent가 행동을 하는데 중요한 역할을 하게 됩니다. 현재 state에 대해서 어떤 action을 취할 확률을 나타냅니다. 또는 현재 state와 action을 mapping 하는 것이라고도 표현합니다. 그리하여 policy, 정책은 파이에 대한 함수로 표현이 됩니다.
MDP policy에서는 현재 state만 고려하고 과거의 것들을 고려하지 않고 action을 하는데, 이때에 stochastic 하게, 확률적으로 action을 결정하게 됩니다.
그리고 policy는 time step의 변화에 무관하게 독립적으로 진행이 되므로 stationary 하다고 할 수 있습니다.
하나의 MDP가 주어졌을 때 하나의 policy가 존재합니다. 이 policy 개념을 Markov process에 적용을 하여 표현을 하면 P 윗첨자에 파이가 표시가 되고, 이를 policy 파이를 따르는 P라고 읽습니다. 왜냐하면 policy 를 벗어난 state transition은 발생할 수 없기 때문입니다.
마찬가지로 Markov reward process 에서의 주요 항목들도 policy 하에서의 P 와 R로 표현이 추가 됩니다.
예를들어서, 우리가 공원에 산책을 나갔습니다. 현재 공원 벤치에 있다고 생각해보겠습니다. 벤치에서 할 수 있는 action은 ‘누워서 잔다’ 혹은 ‘좀더 산책을 한다’ 를 선택할 수 있을 것입니다. 하지만 이 공원에 정책상 벤치에서 누워서 자는 것은 허락되지 않습니다. 그러면 우리는 산책을 하는 행동을 취하게 되는 것과 비슷합니다. 물론 또 다른 선택지가 있다면 그에 대한 선택할 확률이 적용될 것입니다.
이번에는 value function에 policy를 적용해보겠습니다.
위의 공식을 말로 풀어보면, state s 에서 policy를 따르는 v 가 되며 이것은 동일하게 state s인 조건에서 policy를 따르는 기대되는 미래 보상들을 모든 합의 값이 됩니다. 이를 state-value function, v 이라고 합니다.
이를 의미적으로 다시 말하면, 현재 상태에서 이 policy를 따랐을 때 얼마나 좋은지, 얼마나 가치있는지를 나타내는 값이 되겠습니다.
여기다가 action a 개념을 추가하면 action-value function, q 가 됩니다. 이것은 state s 이면서 action a 인 조건에서 policy를 따르는 기대되는 미래 보상들을 모두 합의 값이 됩니다.
이를 의미적으로 다시 말하면, policy를 따라서 이 action을 행동했을때 얼마나 좋은지, 가치를 나타내는 값이 됩니다.
학생 예제를 통해 표현을 해보면, policy 의 값이 0.5 인 상황이므로 현재 state에서 두가지 action을 취하게 될 확률이 반반이 될 겁니다. class 1의 위치에서 본다면 study를 할 확률이 반이고 facebook을 할 확률이 반이 되는 것입니다.
이러한 policy 를 따르는 value 값을 표현하면 빨간색과 같이 될 수 있습니다.
지금까지 살펴본 v function과 q function을 Bellman equation을 사용해서 분리 하면 위와 같이 됩니다. 현재 상태에서 policy를 따르는 value는 즉시 받게 되는 reward, R 과 할인율을 적용한 다음 상태에서의 value 값에 합으로 나타낼 수 있게 되었습니다.
q도 동일하게 Bellman equation을 사용해서 표현하면 위와 같이 되는 것을 알 수 있으실 겁니다. 현재 상태가 s 일때 취할 수 있는 액션들중에서 a 라는 액션을 했을때의 가치를 나타냅니다.
v와 q 에 대하여 backup diagram으로 도식화를 하면 위와 같이 됩니다.
현재 state s에서 policy를 따르는 v 는 두가지의 action 중에 하나에 대한 action a 를 취했을 때 policy를 따르는 q가 있고, 나머지 다른 action에 대한 q가 있겠죠. 이때 두가지의 q 를 합하면 v를 구성하게 됨을 나타내고 있습니다.
이는 state-value function이 나타내는 의미는 현재 상태에서의 모든 액션을 이미 고려한 가치를 나타내고 있다는 것이고, 이 것에서 조금더 들어가서 각각의 action에 대한 것을 action-value function으로 표현할 수 있다는 것을 보여줍니다.
또 현재 state s 에서 action a를 취할때 policy를 따르는 q 는 그로 인해서 받게 되는 reward r과 다음 state인 s’ 으로 이동을 하게 될 것입니다. 그러므로 다음 state s’ 에서의 policy를 따르는 v 값이 또 있겠죠.
하지만, action a 를 선택했음에도 불구하고 우리가 environment 속에서 항상 같은 결과가 나타나는 것이 아니기 때문에 s’로 가지 않고 다른 상태로 갈 수도 있습니다. 왜냐하면 우리가 같은 행동을 하더라도 다른 결과가 오는 경우가 많은 것처럼 (내가 땅을 사면 안오르는데 다른 사람이 땅을 사면 오르는것처럼?) 말입니다. 우리가 사는 실제 세상은 확률적인 결과로 나타나지게 되기 때문입니다.
여하튼 이러한 가능성들을 모두 고려하여 합산하면 q를 위와 같은 공식으로 표현할 수 있게 됩니다.
뭔가 조금씩 복잡해지는 것 같아 보이지만, 결국 agent가 최적의 의사결정을 하는 방법을 위한 과정들을 하나씩 보고 계시는 것입니다.
위에 두 가지로 각각 살펴본 것을 이제 하나로 합쳐서(averaging), 그리고 하나의 사이클로 표현을 해보면 위와 같이 되겠습니다. 아이고 복잡해~ 하지만 충분히 이해할 수 있으실 겁니다.
공식을 자세히 보시면 v 는 처음에는 q로 구성이 되었었지만 현재는 결국 다음 state의 v로만 표현이 되며, q도 마찬가지로 처음에는 v로 구성이 되었었지만 현재는 다음 state의 q로 표현이 된다는 것을 발견할 수 있습니다.
다시 학생 예제를 꺼내서 한번 살펴보겠습니다. 빨간색 원으로 표시된 class 3의 state가 현재 상태라고 할때, v 값을 구하면 위와 같이 됩니다. 이 예제에서의 policy는 0.5 임으로 반반의 확률로 study를 선택하거나 pub을 선택하게 될 겁니다. study 를 action으로 취한 경우에는 0.5 * 10 이 되어 간단하게 계산이 됩니다.
반대로 50%의 확률로 선택이 될 pub을 action으로 취한 경우에는 보상 +1을 받고 20%의 확률로 class 1로 가게 되어 value 가 -1.3 이되는 것이 하나입니다. (0.2 *-1.3) 그런데 여기서 하나가 아니죠. 40% 확률로 class 2로 가고 (0.4 * 2.7) 또 40% 확률로 class 3으로 다시 돌아오는 것 (0.4 * 7.4) 모두를 고려해서 계산을 하면 되겠습니다.
지금까지 살펴본 Bellman expectation equation 을 간단히 표현을 하면 위에 첫번째 공식과 같이 됩니다. 그리고 이전에 살펴본것과 같이 이 방정식을 선형으로 직접 풀어내면 두번째 공식이 되는 것을 보았습니다. policy R의 앞에 값이 상수값이 되기 때문에 선형이 되는 것을 확인할 수 있습니다.
여기서의 P와 R은 모든 가능한 확률들에 대한 것이 고려되어 averaged 되어 사용이 됩니다.
지금까지 배운 내용을 토대로 하여 최적화하는 방법에 대하여 알아보도록 하겠습니다. optimal value function에 대하여 생각해 봅니다.
state-value function이 갖는 값이 최대값이 되도록 하는 max 를 구한다면 이것이 가장 최적의 v 가 될 것입니다. 이때의 v 를 v*로 표현을 하며 이것이 곧 optimal state-value function이 됩니다.
마찬가지로 action-value function이 갖는 값이 최대값이 되도록 하는 max를 구한다면 이때의 q 를 q*로 표현하고 이는 곧 optimal action-value function이 됩니다.
이렇게 최적화된 value function을 찾는 것이 우리의 목표가 되며 MDP를 푼다고 표현을 하기도 합니다.
학생 MDP 예제로 돌아가서 v*를 생각해 보면 위와 같이 됩니다. 각각의 state 마다 최적의 v 값이 보여지고 있습니다. 나중에 이러한 v 값을 따라서 행동을 취하게 되면 어떻게 되는지 보게 됩니다. 그전에 미리 예상을 해보시는 것도 재밌을거 같습니다.^^
이번에는 마찬가지로 q* 에 대한 내용이 추가되어 있습니다. 각각의 state에서 취할 수 있는 action이 보이고 그에 따른 q* 값들이 보입니다. 역시 이를 통해서도 최적의 행동을 예상할 수 있겠습니다.
policy가 여러개가 있을때 각각의 policy들이 어떤 관계가 있을까를 한번 생각해보도록 하겠습니다. 위와 같이 공식으로 표현이 되어 있는 것을 말로 풀어보면 다음과 같이 됩니다.
모든 state에 대하여, 만약 policy를 따르는 v(s)가 다른 policy’를 따르는 v(s)보다 크거나 같다면 policy가 policy’ 보다도 더 좋거나 같은 결과를 내는 정책이다.
즉, 모든 상황에 대해서 가장 최적이 되는 policy는 반듯이 하나 혹은 하나 이상이 존재한다는 것입니다. 이를 가능하게 하기 위해서는 위에 두가지의 방법이 가능합니다. 하나는 optimal value function을 따르는 optimal policy를 발견하는 것이고, 또 하나는 optimal action-value function을 따르는 optimal policy를 찾으면 되겠습니다.
q* 를 사용해서 maximising 하는 optimal policy가 있다고 하면, 위와 같이 나타낼 수 있겠습니다. q*가 최대 값이 되도록 하는 a 라는 action일때에 policy* 가 1이 되고 그렇치 않으면 0이 되면 되겠지요. 1일때가 최적의 행동을 취하도록 실행이 되게 될 거기 때문입니다.
이러한 방법은 deterministic한 optimal policy를 표현합니다. 그러므로 stochastic한 optimal policy에서는 이렇게 하면 안됩니다.
그럼 위에서 구했던 q*를 활용해서 optimal policy를 예제에 표현을 해보면 각 state에서 최적의 행동을 취하도록 할 것입니다. 그리하여 그 행동을 따르게 되면 빨간색 화살표와 같이 움직이게 되겠습니다. 공부를 열심히 하도록 만들어져 있군요~
각각의 상태에서 최선의 선택은 역시 공부하기 였습니다. 공부합시다 여러분~
이전에도 한번 봤던 diagram 입니다. 여기서는 Bellman optimality equation을 표현하고 있습니다.
state 입장에서 보면 v* 는 곧 q* 들이 이루는 값에서 최대치 값을 갖는 q 를 선택하면 된다는 것입니다.
또 action 입장에서 보면 q* 는 즉시 받게 될 rewards R + 다음 states들의 확률과 value의 곱을 모두 고려한 것으로 나타낼 수 있습니다. 최대값을 갖는 action을 취하더라도 다음 state로 가게되는 것이 확률적(stochastically)으로 결정이 되므로 최적화된 q*는 이와 같이 표현이 됩니다.
위의 두가지 v* 를 펼처서 보게 되면 위와 같이 되고 이때의 v* 값은 위에 있는 공식과 같이 됩니다. 여기서 max 가 적용되는 부분에 주목해서 보실 필요가 있습니다.
역시 마찬가지로 q* 에 대한 내용을 펼쳐서 보면 위와 같이 도식화가 됩니다. 이때의 q* 값은 위의 공식이 되고 여기서도 중요하게 살펴봐야 할 것은 max가 어느 부분에 적용이 되는지입니다.
학생의 예제에서 첫번째 state (빨간색)에 있다고 할 때 최적이 되는 value 값은 6이 됩니다. 두가지의 action 이 있고 이에 대한 보상가 미래가치를 구하서 max가 되는 것을 찾아내면 결국 Study를 하게 될 겁니다^^
간단하게 몇가지 Bellman Optimality Equation이 가지고 있는 특성에 대해서 살펴보겠습니다.
일단 non-linear 하다는 것입니다. 이전에는 linear 했었는데 이번에는 왜 비선형(곡선)이 되는 함수가 될까요. 바로 최적화를 하기 위해서 추가되었던 max 연산 때문입니다.
그래서 일반적으로는 이를 제대로 연산을 할 수가 없습니다. 왜냐하면 이러한 연산은 상당히 큰 연산이고 state가 많아질수록 어마어마한 연산을 해야하기 때문입니다. 각각의 상태에서 이러한 연산을 모두 수행하고 진행을 하는 것은 현실적으로 불가능에 가까울 수 있습니다.
그렇기 때문에, 이를 확장한 다양한 다른 똑똑한 방식들이 나타나게 됩니다. 뒤에서 아마도 다루게 될 내용들인 것 같네요
그와는 다르게 MDPs 환경들도 다양한 환경이 있습니다. 무한하고 지속되는 환경도 있고 부분적으로만 볼 수 있고 전체적인 것을 알 수 없는 환경도 있습니다. 또 미래 보상을 할인하지 않거나 다르게 처리해야 하는 환경도 있을 것입니다.
지금까지 배운 내용들을 잘 이해하고 응용하기 위한 환경과 상황에 따라 적절하게 적용할 수 있어야 하겠습니다.
