Study
RL · Study

3. Dynamic Programming으로 Known MDP 풀기

환경 모델을 알고 있을 때 정책 반복과 가치 반복으로 최적 정책을 계산하는 과정을 정리한다.

reinforcement-learningdynamic-programmingpolicy-iterationvalue-iteration

0. MDP를 푸는 두 접근: 계획과 학습

MDP를 푼다는 것은 장기 return을 최대화하는 최적 정책을 찾는 것이다. 차이는 환경 모델을 알고 있는지에 있다.

0.1 Model-Based 접근

상태 전이 확률과 보상 함수를 알고 있으면 실제 행동을 해보기 전에 계산으로 가치 함수와 정책을 구할 수 있다. 이 과정을 planning이라고 부른다.

Model-based approach overview

0.2 Model-Free 접근

환경 모델을 모르면 agent가 직접 행동하고 보상을 받으며 경험을 모아야 한다. Q-Learning, SARSA, DQN은 이쪽에 속한다.

Model-free approach overview

1. Dynamic Programming

DP는 Known MDP에서 벨만 방정식을 반복적으로 적용해 최적 가치 함수와 정책을 계산하는 planning 방법이다.

Dynamic programming concept

강화학습에서 DP가 성립하려면 완전한 환경 모델이 필요하다. 가능한 다음 상태와 그 확률, 보상을 모두 알고 있어야 full backup을 할 수 있다.

2. Policy Iteration

Policy Iteration은 현재 정책의 가치를 평가하고, 그 가치 함수를 기준으로 정책을 개선하는 두 단계를 반복한다.

Policy iteration overview

2.1 Policy Evaluation

정책 평가에서는 현재 정책을 따를 때 각 상태의 가치가 얼마인지 벨만 기대 방정식으로 반복 계산한다.

Policy evaluation equation

2.2 Policy Improvement

정책 개선에서는 평가된 가치 함수를 이용해 더 큰 action value를 주는 행동을 선택하도록 정책을 바꾼다.

Policy improvement equation

Policy iteration convergence result

Policy improvement theorem

Policy iteration grid world example

평가와 개선을 반복하다가 정책이 더 이상 바뀌지 않으면 최적 정책에 도달한 것으로 본다.

3. Value Iteration

Value Iteration은 policy evaluation을 끝까지 하지 않고, 한 번의 Bellman optimality backup 안에 개선 단계를 섞는다.

Value iteration equation

Value iteration grid world example

Value iteration Q-table example

Policy Iteration은 해석이 명확하지만 평가 단계가 무거울 수 있고, Value Iteration은 더 가볍게 반복할 수 있지만 수렴 조건을 적절히 잡아야 한다.

4. 정리

  • DP는 Known MDP에서 사용하는 planning 방법이다.
  • Policy Iteration은 평가와 개선을 명확히 나누어 반복한다.
  • Value Iteration은 최적성 backup을 반복해 가치와 정책을 함께 끌어올린다.
  • 환경 모델을 모르는 경우에는 다음 글의 RL 방법처럼 sample로 값을 추정해야 한다.