[강화학습 #03] MDP Planning

MDP에 대한 정보를 모두 알고 있을 때, 이들을 사용하여 policy를 개선하는 과정을 MDP Planning이라고 한다. 이러한 최적의 policy를 찾는 이유는 에이전트가 받게 되는 보상을 최대화하기 위함이다. 이 MDP Planning은 크게 Policy Iteration과 Value Iteration이 있다.

Policy Iteration

Policy Iteration Process

Policy Iteration은 크게 두 과정으로 나뉘고 이를 최적의 policy를 찾기 전까지 계속 반복하는 형태이다.

• Policy Evaluation : 정해진 Policy로 state value값들을 업데이트하는 단계
• Policy Improvement : 업데이트된 state value로 새로운 policy를 결정하는 단계

1) Policy Evaluation

초기에는 Policy가 존재하지 않으므로 아래와 같은 초기 policy를 정해서 시작하고, 이후에는 결정된 policy를 사용한다.

• Discound factor = 1
• 모든 reward는 -1
• terminal state value는 0으로 고정
• 각 state에서 가능한 모든 action들을 취할 확률은 모두 동일 (아래 예시에서는 0.25)

아래의 Bellman Equation을 사용해서 state value를 업데이트하면 된다.

Bellman Equation

Policy Evaluation using Small Gridworld

2) Policy Improvement

 

Policy Evaluatioin이 종료되면, 이 state 값들로 향상된 policy를 정하는 단계이다. 각 상태 s에서 가장 높은 Q(s, a)를 가지는 action인 a를 선택하여 새로운 policy인 π'를 만든다. 이 새로운 π'를 사용하여 계산한 action value값은 기존 π에서의 action value값보다 당연히 같거나 커지게 되는데, 이를 풀어쓰면 위 식처럼 V_π(s) <= V_π'(s)도 성립한다.

 

 

이렇게 두 과정을 계속 반복하는데, 만약 π'에서의 action value와 π에서의 state value가 같아지면 더이상의 계산이 의미가 없으므로, 반복을 종료하고 그때의 π를 optimal한 policy로 간주한다. 

---

Value Iteration

이전의 Policy Iteration과 달리, Value Iteration은 2장 마지막에서 봤던 Bellman Optimal Equation을 사용해서 최적의 state value를 수렴할때까지 업데이트하고, 결정된 state value값들로 optimal한 policy를 바로 찾는다.

Bellman Optimal Equation

Value Iteration Example