[AI] 6. Markov Decision Process

 

Markov Decision Process 

앞 장에서 설명한 바와 같이 Non-Deterministic Problem은 next state를 deterministic하게 결정할 수 없는 State space를 가진 문제를 의미하며, 예를 들면 로봇 혹은 Packman이 Agent가 지시한 대로 항상 움직이는 것이 아니라 확률적으로 Noise를 갖게 되면 이 문제는 Non-Deterministic 해진다. MDP(Makov Decision Process)는 이렇게 확률적으로 noise 상황에서 의사결정을 할 수 있게 해주는 아주 파워풀한 Tool 이다.

Baseline

MDP를 풀기 위해서는 Formalize와 더불어 MDP에서 지정한 몇 가지 가정, 규칙 등에 대해서 숙제하고 들어가는게 좋으니 일단 아래 개념에 대해 기억하도록 하자.

1. Formulation

MDP를 Formalize 하기 위한 정의에 대해서 먼저 알아보자.

• set of state s ∈ S

• set of actions a ∈ A

• transition function T(s, a, s')

• reward function R(s, a, s')

이전에 배운 search problem과 크게 다른점은 transition function이 확률이라는 것이다. 즉, state에 action이 주어졌을 때 s'이 나올 확률을 의미하며, 이 transition function 자체를 model 혹은 dynamics라 부른다. 

이 transition function이 확률이라는 것이 MDP의 존재 이유이다. 다시 말하면 next state를 선택하는데 있어 각 action별로 계산 가능한 확률 함수가 존재하고, 각 reward가 계산 될 때 MDP로 접근할 수 있다.

※ 참고로 transition function이 주어지지 않는다면 sample들로부터 함수를 알아내야 하는데 이러한 기법은 Reinforcement learning기술로 볼 수 있으며 다음 글에서 다룰 예정이다.

그리고 MDP는 한가지 가정을 하는데 state는 비록 time=1~t까지 historical 하게 왔겠지만 t+1의 state(St+1)는 현재 state(St)만 영향을 미친 다는 것이다. (1st order Markov assumption) 물론 St-1까지 고려할 수도 있지만 (2nd order Markov assumption) 계산량이 급격히 많아짐으로 통상 현재 state만 고려한다.

2. Policies

어쨌든 MDP의 최종 목적은 action의 sequence (plan)을 구하는 것이며 plan을 구하기 위해 optimal policy 함수(π*)를 구하는 것을 목표로 한다. π*(s)는 최적의 action을 출력하는 함수이며, maximize expected utility역할을 한다.(expected utility를 최대화 하는 action을 선택하는 함수) 그리고 π 자체는 모든 policies를 포함하는 dictionary 정도로 이해하면 된다. (Key는 state, Value는 action인 dictionary)

그리고 optimal policy를 구하려면 expected utility로 Reward를 사용하게 되는데, Reward 함수는 보상만을 의미하는 것이 아니라 penalty 정보를 가지고 있을 때 더욱 효과를 본다. 위 예제를 보더라도, 적절한 Reward 함수가 주어져야만 optimal policy를 찾을 수 있음을 확인 할 수 있다.

3. MDP Search Trees

MDP문제는 change node를 가지는 Expectimax 문제를 푸는 것과 유사하기 때문에 Expectimax search tree와 매우 유사하게 표현될 수 있다. MDP에서도 마찬가지로 chance 노드를 가지는데 change node를 q-state라 부른다. q-state는 action을 취하고 나서 next state로 넘어가기 직전의 상태라 생각하면 된다. 다시 말하면 next state로 가기 위해서는 transition function의 확률이 적용되어야 하는데 그 직전 단계가 q-state이며, transition 확률이 적용되고 난 후에는 next state인 s'으로 이동한다.

4. Utilities of Sequences

MDP를 solve 하면 현재 이후의 상황을 sequential 하게 예측 할 수가 있다. 즉 미래의 reward 또한 추론하는데, 이 때 어떤 것에 더 가치를 둘 것인가가 의사결정에 큰 영향을 미칠 것이다. 

MDP는 기본적으로 미래에 받을 reward에 대해서 가중치를 낮게 준다. 위 그림의 γ는 0~1 사이의 값이기 때문에 미래의 가치는 점점 낮아진다. 위와 같이 미래의 가치를 낮게 두는 것을 Discounting이라고 한다.

5. Infinite Utilities

게임이 영원히 끝나지 않을 것 같으면 계속해서 계산하고 있을 수 없기 때문에 3가지 옵션을 가진다.

1) Discounting

첫번째는 앞서 배운 Discounting을 활용 하는 것이다. γ는 0~1 사이 값인데 이 값을 작게 둘수록 미래의 reward는 더 빠르게 0으로 수렴한다. 이 성질을 이용하면 적절한 threshold를 이용해 search를 조기에 끝낼 수 있다.

2) Finite horizon

depth-limited search와 유사하게 예측할 step T를 미리 선언하는 방법이다.

3) Absorbing state

강제로 끝나게 되는 state를 지정한다. 예를 들어 racing의 경우 overheating 됐을 때가 terminate state라는 것을 지정하는 것과 같다.

Solving MDPs

자, 지금까지 MDP를 풀기 위해 필요한 기초 지식을 강제 주입했다. 이제 진짜 문제를 한번 풀어보자.

1. Optimal Quantities

우리의 목적은 optimal policy π*의 sequence를 구하는 것이다. 그리고 optimal policy를 구하기 위해서는 각 state에서의 value를 계산하는 것 부터 시작된다. 

(value=utility =reward 혼용해서 사용하기 시작하는데 value라 하면 utility 혹은 reward로 이해하자.)

• V*(s) : s부터 goal state까지 갔을 때 얻을 수 있는 maximum expected utility
• Q*(s, a) : s에서 action a를 택했을 때 얻을 수 있는 maximum expected utility
• π*(s) : s에서의 optimal action

  

위 그림을 참고하면 V*와 Q*, π*에 대해 이해할 수 있을 것이다. s = (2, 1)이라 가정한다면,

Q*(s, E)=-0.6,  Q*(s, N) = 0.57,  Q*(s, W) = 0.53,  Q*(s, S) = 0.3이고,

V*(s)는 그 중 가장 높은 expected utility를 가지는 0.57이다.

그리고 V*(s)를 위한 optimal policy  π*(s) = 'North' 가 된다.

2. Values of State

그럼 이제 optimal value를 구해보도록 하자.

(Bellman Equation)

앞서 설명한 정의를 이해했다면 V*(s)는 Q*(s, a) 중에서 가장 최대값을 택하면 구할 수 있다.

중요한 것은 Q*(s, a)를 구하는 것이고, 위 재귀식을 분리해서 해석해보면, 

ΣT(s, a, s') * R(s, a, s')은 「s에서 a를 택할 확률 * utility의 평균」이고,

ΣT(s, a, s') * γV*(s')은 「Q*(s', a')의 최대값」으로 미래에 얻을 수 있는 value값이다. (재귀)

즉, 현재 action을 통해 얻을 수 있는 value + 미래에 얻을 value의 집합이 Q*(s, a)이다.

아직까지는 T(s, a, s')을 어떻게 학습하는지 배우지 않았지만, T(s, a, s')을 구했다고 가정한다면 expectimax value를 구하는 것과 다르지 않다는 것을 알 수 있다.

3. Time-Limited Value

그런데 문제에 따라서 MDP Tree는 무한대로 뻗어나갈 수 있다. 즉, Bellman Equation의 V*(s')를 무한히 계산해야 할 수도 있다는 말이다. 이 문제 해결을 위해 depth limited search 방식을 적용하여 새로운 Value Vk(s)를 정의한다.

• Vk(s) = s부터 k까지 가면 게임이 끝난다 가정하고 depth=k일때 Value

여기서 많은 사람들이 헷갈려하는데, Vk+1(s)가 미래가 아니라 Vk(s')이 미래 state 인 점을 기억해야 한다. 

4. Value Iteration

Vk(s)를 정의함으로써 Bellman equation은 아래의 식으로 일반화하여 풀수가 있게 된다.

위 식이 재귀적으로 진행되면 V0(s')를 구하는 순간이 오는데 V0(s')=0 기저조건을 설정하면 위 수식은 재귀적으로 쉽게 풀 수 있다. (V0(s')은 Terminal state로 더 이상 action을 하지 않음으로 얻을 수 있는 value도 0이다)

지금까지 학습한 내용을 가지고 T(s, a, s')이 주어졌다는 가정하에 간단한 Value Iteration 예제를 풀어보자.

V0는 앞서 말한 것과 같이 action을 하지 않을 예정이기 때문에 0으로 초기화 되어 있다.

V1, slow는 (1.0 * (1.0 + V0 slow)와 {(0.5 * (2+V0 slow) + 0.5 * (2+V0 fast)} 를 비교,
V1, fast는 {0.5 * (1.0 + V0 slow) + 0.5 * (1.0 + V0 fast)}와 (1.5 * (-10+V0 overheat)) 를 비교,

V2 slow 는 (1.0 * (1 + 1 * V1, slow)) 와 { (0.5 * (2 + V1, slow) + 0.5 * (2 + V1, fast)} 를 비교한다.

5. Convergence*

Value Iteration을 다시 한번 상기해보면면 Vk의 k가 커질수록 Vk왜 Vk+1의 차이는 점점 작아지며, 특히 discount 변수 γ가 주어지면 Vk와 Vk+1의 차이는 γ^k에 비례하여 작아진다. 즉 k가 클수록 Vk와 Vk+1의 차이가 0으로 수렴하게 되며, 이 뜻은 value는 언젠간 수렴한다고 말할 수 있다.

6. Policy Evaluation

π(s)가 주어졌다고 할 때 그때 V를 계산하는 방법에 대해 알아보자.

어떤 policy π(s)를 fix 했다고 가정하면 graph가 일단 심플해고, Bellman Equation을 통해 value값을 구할 수 있다. 아래 식에서 max함수가 없는 것에 주목하자. 이미 action을 선택했기 때문에 max 함수를 취할 필요가 없다.

위 식을 풀려면 V'을 재귀적으로 풀어야 함으로 Value Iteration의 Idea를 빌려 아래와 같이 표현하면 π(s)가 주어졌을 때 value를 구할 수 있다.

7. Policy Extraction

π(s)의 value를 구할 수 있다면, 이제는 optimal π*(s)를 구할 수 있어야 한다.

Bellman equation을 통해 우리가 V*(s)를 구했다고 가정하면 위 식으로 π(s)를 구할 수 있긴 하다. 이 식에서 T, R은 상수이기 때문에 value로 부터 π(s)를 구하는 과정을 Policy Extraction이라고 한다. 

만약에 Q* value가 있다고 가정하면 더욱 쉽게 구할 수 있다. 사실 위 식의 argmax 우측 항은 Q*(s, a)에 대응된다.

7. Policy Iteration

위 5, 6, 7번 chapter를 활용하면 Value Iteration과 같이 Policy를 Iterative하게 연산하여 구할 수 있는데 몇 가지 문제점이 있다.

• 첫 번째는 Value Iteration과 같이 재귀적으로 Bellman update를 수행시 시간이 너무 오래걸린다는 것이며,
• 두 번째는 매 반복시 호출되는 max함수의 computing 효율이 좋지 않으며,
• 세 번째는 어느정도 반복하면 policy가 수렴하기 때문에 마찬가지로 비효율적이다.

  

특히 세 번째 문제점을 위 사례로 분석해보면 생각보다 policy는 value에 비해 일찍 수렴한다는 것을 알 수 있다. 실제로 5번의 재귀 이후에 policy는 수렴하였지만 value값은 100번째 재귀 호출까지 계속해서 변하고 있는 모습을 확인할 수 있다. 

여기서 얻은 아이디어는 Bellman updates를 활용한 Value Iteration을 사용하지 않는 것이다.

VI를 사용하지 않고 PI를 하기 위해 2가지 step을 반복한다.

• step 1. Policy evaluation : 임의의 π(s)로 V(s)를 계산한다

• step 2. Policy extraction : π(s)를 또 다른 policy로 변경 한다.

위 과정을 반복하며 Policy가 더 이상 변하지 않으면 PI를 종료하게 된다.

사실 아직도 PI, VI 방정식 전개에 대해서 완벽히 이해하진 못해서 좀 더 스터디가 필요하다. 다만, 확실한 것은 PI, VI의 목적은 Iterative 한 방법으로 특정 step후의 optimal value V*(s)와 optimal policy π*(s)를 구하기 위함이라는 것이다.

일단 PI, VI의 필요성과 개념만 이정도 이해한 상태에서  Reinforce Learning로 넘어 가고, PI, VI에 대한 지식이 좀 더 다듬어지면 게시글을 수정하도록 해야겠다.