Dynamic Programming : Policy Iteration & Value Iteration

Dynamic Programming : Policy Iteration & Value Iteration

돌아서면 까먹는 미래의 나를 위해....

다시 보아도 바로 이해할 수 있도록 정리한다.

---

MDP가 뭐였지?

Markov Decision Processes는 Total Reward를 최대로 만들고, 이때의 Optimal Policy를 찾는 방법이었다.

MDP에서 중요한 점은 Model을 알고 있다는 점이다.

여기서 Model은  Transition Probability, Reward Function을 말하는데, 보통은 Transition Probability를 의미한다.

즉, 모든 상황(Observation)을 다 알고 있다는 의미다. 

Agent가 지금 state에서 action을 취했을 때, 다음 state의 확률분포를...

Bellman Equation

앞선 포스팅에서 언급했듯 Bellman Equation은 두개로 나뉜다.

정리해보면 다음과 같다.

1) Bellman Expectation Equation

Bellman Expectation Equation

2) Bellman Optimality Equation

Bellman Optimality Equation

이 Equation은 추후 계속활용되니 반드시 숙지하도록 한다.

---

Policy Iteration?

말그대로 Policy를 업데이트하는 과정을 의미한다.

업데이트되는 방식은 다음과 같다.

1) Policy Evaluation : 먼저 State Value Function 'V'를 구한다. (Prediction 문제)

지금 가지고 있는 Policy π를 가지고 V를 업데이트해준다. 

어떻게? 앞서배운 Bellman Expectation Equation으로!!!

Policy Evaluation

좀 더 자세하게 보면, 이는 iterative policy evaluation이다.

뭔말이냐...하면....

iterative policy evaluation

(위 내용은 David Silver의 강의자료다.)

이 policy iteration부분에서 내가 한 가장 큰 착오는

evaluation과 improvement가 1번씩 번갈아가면서 진행된다고 생각한 것이다.

물론, 이렇게 해도 되지만 위 그림대로 설명하자면 아래와 같다.

policy π가 주어졌다...다시 말해서!!!!

4가지 action에 0.25씩 부여하든 뭘하든 아무튼 초기값 세팅으로 정해진게 있을 것이다.

이 policy를 가지고 value를 Bellman expectation equation으로 업데이트한다.

여기서 알아야될건 업데이트했다고 improvement로 넘어가는 것이 아니라!!

Vπ에 수렴할때까지 계속 evaluate해야한다!!!!

Vπ에 수렴한다??(위 그림의 빨간줄을 보세요)

evaluate을 계속하면 계속 value가 바뀐다.(업데이트된다.)

이게 바뀌지 않을때까지 evaluate을 하라는 말이다.

그렇게 되면 policy π가 주어졌을 때, Vπ에 수렴할때까지 

iterative하게 value를 evaluation시킨 것이다.

Policy π를 가지고 evaluation과정을 value가 바뀌지 않을때까지 반복하면,

Vπ에 수렴한다. 수렴하면 improvement해서 policy 업데이트해주고 다시 evaluation!!

2) Policy Improvement : Q를 구하고, Optimal Policy를 구한다. (Control 문제)

1)에서 구한 V로 Bellman Expectation Equation을 이용하여 Q를 구하고,

이 Q를 최대로 만드는 action a에 1 / 나머지action에는 0을 부여

Policy 업데이트를 해준다.

Policy Evaluation

이 과정을 for문으로 반복해주면 되는 것이다.

언제까지? Converge할때까지...

evaluate해도, improvement후 evaluate해도 value가 바뀌지 않으면, converge한 것이다.

modified value iteration

David Silver에 말에 따르면,

Vπ에 수렴할때까지  evaluation하고 improvement해도되고,

한번한번씩 번갈아가면서 update해도 된다고 한다.(이경우는 value iteration과 같은 iteration형태)

Value Iteration?

Value Iteration은 Bellman Optimality Equation을 이용한다.

Value Iteration

Value Iteration with explicit policy

Max를 사용하기때문에 Policy π의 영향을 받지 않는다.

그냥 움직여서 value를 계산해보고 큰쪽으로 policy를 1로 맞춰주는 방식

Policy Iteration vs Value Iteration

Policy Iteration vs Value Iteration

결국, 같은 수렴점을 향해 다가간다.