[강화학습] Dynamic Programming

다음으로 dynamic programming을 알아보자. 

dynamic programming은 쉽게 말하면 어려운 문제를 쪼개서 푸는 것을 말한다. 이는 transition probability / dynamics를 알 때만 사용할 수 있으며, 모르면 dynamic programming으로 해결할 수 없다. 

dynamic programming은 value function을 구하는 policy evaluation과 더 좋은 policy를 구하는 policy improvement로 이루어진다. 이들을 bellman equation에 대입해서 반복하면 policy iteration이다.

• policy evaluation
  • 특정 state에 대해서 value function을 구하고 그를 bellman equation에 넣어 다른 state에서의 value function을 구하는 과정을 반복하면서 해당 policy에 대한 true value function를 구한다.
• policy improvement
  • $q_\pi (s,\pi'(s)) \ge v_\pi (s)$을 만족할 때 $ argmax_{\pi'} q_\pi (s,\pi'(s)) $인 $\pi'$에 대해 $v_{\pi'}(s) \ge v_\pi(s)$ 는 policy improvement theorem을 이용하여 더 좋은 value function을 policy로 update하는 과정이다.
  • 즉, state 별로 취할 수 있는 action에 대한 value function을 바탕으로 더 좋은 policy를 선택하는 것이다.

이렇게 policy evaluation과 policy improvement를 반복하는 과정을 통해 optimal policy를 찾는 것이 policy iteration의 핵심이다.

value iteration은 bellman equation 대신 optimal bellman equation을 사용하여 반복적으로 value function을 업데이트하는 방식이다. 각 상태에서 가능한 모든 행동 중에서 가장 높은 기대값을 선택함으로써, 매 단계에서 최적의 행동을 가정하고 value function을 업데이트하기 때문에, 결과적으로 최적 정책도 자연스럽게 도출된다. 

이들은 항상 수렴할까? 라는 의문에 대해 Banach Fixed Point Theorem을 이용하여 답할 수 있다.

• Contraction Mapping
  
  • $(X,d)$가 metric space일 때, map $T: X\rightarrow X$가 모든 $x,y \in X$에 대해 $d(T(x),T(y)) \leq q d(x,y)$를 만족하는 $q\in [0,1)$이 존재한다면 $T$를 contraction mapping이라 한다.
• Banach Fixed Point Theorem
  
  • $(X,d)$가 non-empty complete metric space이고 $T: X\rightarrow X$가 contraction mapping일 때, $T$는 a unique fixed-point $x^* \in X$를 갖는다.
  • 즉, $T(x^*) = x^*$를 만족하는 $x^*$가 존재하고 이는 유일하다.

Policy Iteration과 Value Iteration은 모두 Bellman operator를 기반으로 한다. Bellman operator는 다음과 같이 정의된다.
$$
T : V \mapsto \max_{a \in \mathcal{A}} \, \mathbb{E}_{s' \sim p(\cdot|s,a)} \left[ r(s,a) + \gamma V(s') \right]
$$
이 연산자 $T$는 두 함수 $V_1$, $V_2$에 대해 다음을 만족한다.
$$
\| T(V_1) - T(V_2) \|_\infty \leq \gamma \| V_1 - V_2 \|_\infty
$$
즉, $\gamma \in [0,1)$일 때 $T$는 contraction mapping이므로, Banach Fixed Point Theorem을 적용하면 반복 적용 시 수렴함이 자명하다.
Value Iteration은 위의 Optimal Bellman Operator를 반복 적용하며, 이는 Banach Theorem에 의해 fixed point $V^*$로 수렴한다. $T(V^*) = V^*$로, $V^*$는 다음을 만족하는 유일한 fixed point다. 그리고 이로부터 유도되는 optimal policy $\pi^*$는 다음과 같다.
$$
\pi^*(s) = \arg\max_{a \in \mathcal{A}} \, \mathbb{E}_{s' \sim p(\cdot|s,a)} \left[ r(s,a) + \gamma V^*(s') \right]
$$
따라서 $\pi^*$는 optimal policy이며, 모든 $\pi$와 상태 $s$에 대해 $V_{\pi^*}(s) \geq V_\pi(s)$를 만족한다. 이때, 고정점 $V^*(s)$는 바로 $V_{\pi^*}(s)$, 즉 optimal value function이 된다.

이제 dynamic programming의 policy iteration과 value iteration을 구현해보자.

https://www.gymlibrary.dev/environments/toy_text/frozen_lake/#frozen-lake

Frozen Lake - Gym Documentation

FrozenLake-v1은 에이전트가 얼어붙은 호수를 건너 목표 지점에 도달해야 하는 간단한 강화학습 환경이다.

상태 공간이 작고 구조가 명확하여, policy iteration이나 value iteration 같은 Dynamic Programming 기법을 설명하고 실습할 때 가장 널리 사용되는 예제 중 하나이다. policy iteration과 value iteration을 구현하고 이 두가지를 비교해보았다. 자세한 내용은 아래 깃허브 링크에서 확인할 수 있다.

Github : https://github.com/seonvin0319/25RL_Study/tree/main/DP

25RL_Study/DP at main · seonvin0319/25RL_Study

 

하지만 policy iteration과 value iteration 모두 계산량이 매우 크고, dynamics를 알고 있어야 한다는 점에서 실제 문제에 적용하는 데 한계가 있다. 이를 보완하기 위해, 전체 상태에 대해 일괄적으로 업데이트하는 full-width backup 방식 대신, trial and error를 통해 일부 샘플만을 이용해 업데이트하는 sample backup 방식이 도입되었다.

이 글은 Sutton & Barto의 Reinforcement Learning 4장을 바탕으로 작성되었으며, 실습 코드는 [위키독스 실습 예제](https://wikidocs.net/218783)를 참고하였다.