[RL] Dynamic Programming

Introduction

Dynamic programming, 동적 프로그래밍이란 복잡한 하나의 문제를 여러 개의 소문제로 나눈 후, 각 소문제의 해를 합쳐 문제를 풀어나가는 문제해결 패러다임이다. 동적 프로그래밍은 다음과 같은 2가지 성질을 가진 문제를 풀 때 사용될 수 있다. 

• Optimal substructure
  • Principle of optimality (최적성의 원리)가 적용될 수 있음
  • 문제의 최적의 해가 소문제의 해들로 분해될 수 있음

• Overlapping subproblems
  • Subproblems recur many times
  • 문제의 솔루션들은 저장되어 재사용할 수 있음

위 성질을 만족하는 예시 중 하나가 바로 MDP이다. 벨만 방정식은 재귀적으로 분해될 수 있으며, 각 state에 대한 value function은 저장되어 다른 state의 value function을 구할 때 사용할 수 있다. 따라서 동적 프로그래밍은 강화학습에서 environment의 완벽한 model이 주어졌을 때 최적의 policy를 구할 때 사용할 수 있다. 즉, 동적 프로그래밍은 MDP의 모든 요소들이 주어졌을 때 사용할 수 있는 것이다. 이때문에 주로 planning, 계획법 중 하나로 사용된다. 

 

하지만 이러한 상황이 흔하지는 않다. 따라서 MDP를 알지 못하더라도 사용할 수 있는 model-free 알고리즘이 존재하는데, 이는 추후 다뤄볼 것이다. 

 

---

Policy Evaluation

첫 번째로, 주어진 임의의 policy $\pi$에 대해 state value function을 구하는 법을 알아보자. 즉, policy $\pi$의 성능을 평가 (evaluate) 하는 것이다. Dynamic programming에서 우리는 $v_\pi$를 Bellman expectation backup을 반복적으로 수행함으로써 구한다.

Policy Evaluation 
For each $t = 0, 1, 2, \cdots$
1. for all states $s \in \mathcal{S}$, 
2. Update $v_{t+1}(s)$ from $v_t (s^\prime)$ where $s^\prime$ is a successor state of $s$. 

 

이러한 backup 방식을 synchronous, 동기화 방식이라고 한다. 각 시점마다 모든 state에 대해 value function을 업데이트하기 때문이다. 당연히 asynchronous, 비동기화 방식도 존재하는데, 글의 마지막 부분에서 살펴볼 것이다. 또한 이 알고리즘의 수렴성 역시 수학적으로 증명되어 있고, 이 역시 다음 포스트에서 간단하게 다뤄볼 것이다.

 

Update 수식은 $v_\pi$의 Bellman equation을 따르고 있는 것을 볼 수 있는데, 다음과 같다. 

$$
\begin{aligned}
  v_{k+1} (s) = \sum_{a \in \mathcal{A}} \pi (a | s) [\mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_k (s^\prime) ]
\end{aligned}
$$

 

즉 실제 value function $v_\pi$는 이 방정식의 고정점 (fixed point)임을 알 수 있다. 또한 $v$를 한 번 update할 때 모든 state에 대한 value를 update하므로 이러한 backup을 full backup이라고 한다. 모든 state에 대한 backup이므로 다음과 같이 행렬 형태로 나타낼 수 있다는 특징이 있다. 

$$
\begin{aligned}
  \mathbf{v}^{k + 1} = \boldsymbol{\mathcal{R}}^\boldsymbol{\pi} + \gamma \boldsymbol{\mathcal{P}}^\boldsymbol{\pi} \mathbf{v}^{k}
\end{aligned}
$$

 

$\mathbf{v}^{k + 1}$와 $\mathbf{v}^{k}$을 저장할 수 있는 두 배열만으로 알고리즘을 구현할 수 있는 것이다. (in-place backup 방식으로 구현된다면 하나의 배열로 충분하다)

 

$\mathbf{Example.}$ Evaluating a Random Policy in the Small Gridworld

다음과 같은 $4 \times 4$ gridworld를 생각해보자.

Nonterminal state는 $\mathcal{S} = \{ 1, 2, \cdots, 14 \}$으로 구성되고, 각 상태마다 4가지의 action이 가능하다: $\mathcal{A} = \{ \text{ up }, \text{ down }, \text{ right }, \text{ left } \}$. 각 action은 agent가 world를 빠져나가지 않는 한 에이전트의 다음 상태를 deterministic하게 결정한다. 각 action마다 $-1$의 reward로 페널티를 받으므로, agent는 최대한 빨리 terminal state에 도달해야한다. 

Agent가 random policy를 따르고 있다고 가정해보자. 즉 모든 action을 동일한 확률 $\frac{1}{4}$로 취한다. 아래 그림의 왼쪽 열은 policy evaluation에 따른 $v_k$들을 나타낸다.

 

마지막 $v_k$는 policy evaluation의 수렴성에 따라 $v_\pi$와 일치한다. 각 state마다 episode의 termination까지 필요한 step 수 기댓값에 음수를 취한 것임을 볼 수 있다. 

 

---

Policy Iteration

우리는 policy evaluation 알고리즘을 통해 어떤 policy $\pi$가 주어져도 이에 대한 value function을 계산함으로써 policy의 성능을 평가할 수 있게 되었다. 이제 Policy iteration를 통해, 주어진 $\pi$의 성능을 향상시켜 최적의 policy  $\pi_*$를 찾는 법을 알아보고자 한다. Policy iteration은 action-value function $q_\pi (s, a)$으로 현재 policy을 향상시킬지 결정한다. 

Policy Improvement

주어진 policy $\pi$를 평가하고 난 후, 즉 

$$
\begin{aligned}
  v_\pi (s) = \mathbb{E} [R_{t+1} + \gamma R_{t+2} + \cdots | S_t = s]
\end{aligned}
$$

 

를 계산하고 나면 우리는 $v_\pi$에 대해 탐욕적으로 행동함 (acting greedily)으로써 향상된 policy를 얻는다. 다음과 같은 결정적 정책 (deterministic policy) $a = \pi (s)$를 생각해보자. 그러면, 특정 state $s$에 대해 탐욕적으로 행동한다는 것은 action-value 값이 가장 큰 방향으로 action을 결정한다는 의미이다. 

$$
\begin{aligned}
  \pi^\prime (s) = \underset{a \in \mathcal{A}}{\text{ arg max }} q_\pi (s, a)
\end{aligned}
$$

 

탐욕적으로 action을 선택하면 $\pi$에 대한 action-value function과 state-value function 사이에 다음과 같은 부등식이 형성된다. 

$$
\begin{aligned}
  q_\pi (s, \pi^\prime (s)) = \underset{a \in \mathcal{A}}{\text{ max }} q_\pi (s, a) \geq q_\pi (s, \pi (s)) = v_\pi (s)
\end{aligned}
$$

 

즉, 위의 부등식을 다음과 같이 사용함으로써, 현재 value function $v_\pi (s)$가 한 단계 향상되는 것 ($v_{\pi^\prime} (s) \geq v_\pi (s)$)을 관찰할 수 있다.

$$
\begin{aligned}
  v_\pi (s) &\leq q_\pi (s, \pi^\prime (s)) = \mathbb{E}_{\pi^\prime} [R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s] \\
  &\leq \mathbb{E}_{\pi^\prime} [R_{t+1} + \gamma q_{\pi^\prime} (S_{t+1}, \pi^\prime (S_{t+1})) | S_t = s] \\
  &\leq \mathbb{E}_{\pi^\prime} [R_{t+1} + \gamma R_{t+2} + \gamma^2 q_{\pi^\prime} (S_{t+2}, \pi^\prime (S_{t+2})) | S_t = s] \\
  &\leq \mathbb{E}_{\pi^\prime} [R_{t+1} + \gamma R_{t+2} + \cdots | S_t = s] = v_{\pi^\prime} (s)
\end{aligned}
$$

 

이러한 과정을 토대로 얻어낸 결과를 policy improvement theorem이라고 한다.

$\mathbf{Thm.}$ Policy Improvement Theorem
Let $\pi$ and $\pi^\prime$ be any pair of deterministic policies such that, for all $s \in \mathcal{S}$, $q_\pi (s, \pi^\prime(s)) \geq v_\pi (s)$. Then, the policy $\pi^\prime$ must be as good as, or better than $\pi$, in other words, $v_{\pi^\prime} (s) \geq v_\pi (s)._\blacksquare$

---

여기서 한 가지 짚고 넘어갈 것이 있는데, 바로 $q_\pi (s, \pi^\prime (s))$의 의미이다. 이 notation은 state $s$에 대해, 다음 action $A$가 $\pi^\prime (\cdot | s)$ 분포를 따르고 ($A \sim \pi^\prime (\cdot | s)$) 그 이후 시점부터는 다시 $\pi$를 따를 때, return의 기댓값을 나타낸다. 수식으로 나타내면 이해가 더 쉬울 수 있다. 

$$
\begin{aligned}
q_\pi (s, A) = \mathbb{E}_{\pi} [G(s, A) | S_t = s] \text{ where } A \sim \pi^\prime (\cdot | s)
\end{aligned}
$$

 

아직 stochastic policy를 다루지 않아 헷갈릴 수 있으나, 만약 $\pi^\prime$이 deterministic policy라면

$$
\begin{aligned}
q_\pi (s, A = \pi^\prime (s)) & = \mathbb{E}_{\pi} [G (s, \pi^\prime (s)) | S_t = s] \\
  & = \mathbb{E}_{\pi} [G (s, A_t = a) | S_t = s, A_t = \pi^\prime (s)]
\end{aligned}
$$ 

 

이 된다. 또는 discrete action space에 대한 stochastic policy의 경우 다음과 같이 나타낼 수 있다. 

$$
\begin{aligned}
q_\pi (s, A = \pi^\prime (s)) & = \mathbb{E}_{\pi} [G (s, A) | S_t = s] \\
  & = \sum_{a \in \mathcal{A}} \pi^\prime (a | s) \mathbb{E}_{\pi} [G (s, a) | S_t = s] \\
  & = \sum_{a \in \mathcal{A}} \pi^\prime (a | s) \mathbb{E}_{\pi} [G (s, A_t) | S_t = s, A_t = a] \\
  & = \sum_{a \in \mathcal{A}} \pi^\prime (a | s) q_\pi (s, a)
\end{aligned}
$$ 

 

위의 정의에 따라, $v_\pi (s)$는 $q_\pi (s, \pi(s))$로도 표현될 수 있는 것이다. 

---

이제 iteration의 종료 조건을 알아보자. 만약 성능이 더 이상 향상되지 않는다면, 

$$
\begin{aligned}
  q_\pi (s, \pi^\prime (s)) = \underset{a \in \mathcal{A}}{\text{ max }} q_\pi (s, a) = v_\pi (s)
\end{aligned}
$$

 

Bellman optimality equation $v_\pi (s) = \underset{a \in \mathcal{A}}{\text{ max }} q_\pi (s, a)$가 만족하는 것을 볼 수 있다! 따라서 policy iteration이 종료되면 우리는 최종 $\pi$가 optimal policy임을 확신할 수 있게 된다. 다음 pseudo-code로 policy improvement 알고리즘의 전체적인 과정을 복습해보자. 

 

$\mathbf{Fig\ 1.}$ Full policy iteration algorithm

Generalized Policy Iteration 

Policy evaluation과 policy improvement를 합치면, 드디어 generalized policy iteration 알고리즘이 완성된다. Policy evaluation을 통해 현재 policy 성능을 측정하고, policy improvement를 통해 향상된 새로운 policy $\pi^\prime$을 얻는다. 다시 이 $\pi^\prime$의 성능을 policy evaluation을 통해 측정하며 알고리즘을 반복하는 형태가 된다. 

 

$\mathbf{Fig\ 2.}$ Generalized Policy Iteration

 

$\mathbf{Example.}$ Jack's Car Rental

Jack manages two locations for a car rental company. Each day, some number of customers arrive at each location to rent cars. If Jack has a car available, he rents it out and is credited $10$ by the national company. If he is out of cars at that location, then the business is lost. Cars become available for renting the day after they are returned. To help ensure that cars are available where they are needed, Jack can move them between the two locations overnight. 
  
Then, we can construct a finite MDP environment as follows:

• Timestep: days
• States: Number of cars at each location (suppose that maximum $20$)
• Actions: Number of cars that are moved to 2nd from 1st
• Reward: $10 for each car rented (must be available)
• Transitions: Cars returned and requested randomly 
  • Poisson distribution; $n$ returns and requests with probability $\frac{\lambda^n}{n!} e^{-\lambda}$
  • 1st location: average request = 3, average returns = 3
  • 2nd location: average request = 4, average returns = 2

The following figure shows the sequence of policies searched by policy iteration.
  

---

Value Iteration

Policy iteration은 policy를 평가하는 과정과 이를 개선시키는 과정이 반복적으로 일어난다. 현재의 policy를 발전시키기 위해선 policy evaluation이 끝나기를 기다려야 하는데, 이러한 불필요한 반복을 줄이기 위해 value iteration이라는 또 다른 알고리즘이 존재한다. Value iteration은 최적성의 원리 (principle of optimality)를 기반으로 한다.

Principle of Optimality 

$\mathbf{Thm.}$ Principle of Optimality
A policy $\pi (a | s)$ achieves the optimal value from state $s$, $v_\pi (s) = v_* (s)$ if and only if for any state $s^\prime$ reachable from $s$, $\pi$ achieves the optimal value from state $s^\prime$, $v_\pi(s^\prime) = v_* (s^\prime)$. 

Deterministic Value Iteration

따라서, 만약 $v_* (s^\prime)$를 알고 있다면, 이전 상태 $v_* (s)$ 역시 알 수 있게 되는 것이다. 

$$
\begin{aligned}
  v_* (s) \longleftarrow \underset{a \in \mathcal{A}}{\text{ max }} \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_* (s^\prime)
\end{aligned}
$$

 

이는 앞서 살펴보았던 dynamic programming을 적용할 수 있는 문제의 조건 중 소문제의 답을 알고 있다면 이를 합성하여 다른 문제의 답을 얻어낼 수 있어야 한다는 것과 일치한다. Value iteration은 이와 같은 update를 모든 iteration마다 실행해준다. 즉, 각 $k+1$번째 반복마다 모든 state $s \in \mathcal{S}$에 대해 

$$
\begin{aligned}
  v_{k+1} (s) & = \underset{a \in \mathcal{A}}{\text{ max }} \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_k (s^\prime) \\
  \mathbf{v}_{k + 1} & = \underset{a \in \mathcal{A}}{\text{ max }} [\boldsymbol{\mathcal{R}^a} + \gamma \boldsymbol{\mathcal{P}^a} \mathbf{v}_k ]\\
\end{aligned}
$$

 

$\mathbf{Fig\ 3.}$ Backup diagram for Value Iteration

 

잘 살펴보면 Bellman optimality equation을 update 방식으로 채택한 것을 볼 수 있다. 오직 value function만을 고려하기 때문에 policy를 평가할 일도 없으며, policy iteration보다 더 간단한 알고리즘이 되는 것이다. 반대로 value iteration에는 explicit하게 policy가 존재하지 않으며, value iteration 중간, 또는 알고리즘이 끝났을 때 얻은 value function $v$에 대해 그와 일치하는 policy가 존재하지 않을 수 있다. 즉 $\forall \pi, \; v_\pi \neq v$일 수 있다는 것이다. 다음 pseudo-code로 value iteration 알고리즘의 전체적인 과정을 복습해보자. 

$\mathbf{Fig\ 4.}$ Full Value Iteration

---

Extension to DP  

Asynchronous DP

지금까지 우리는 synchronous DP 알고리즘들을 다루어왔다. 이러한 알고리즘은 각 시점에서 모든 state에 대한 value를 업데이트하는 방식이었다. 그러나 만약 state space가 매우 거대하다면 모든 state의 value를 고려하는 것은 굉장히 비효율적이다. 

 

$\mathbf{Fig. 5}$ Summary of synchoronous DP

Asynchronous DP 알고리즘은 synchronous 알고리즘의 비효율적인 업데이트와 반복을 피하고, 각 시점마다 특정 state들만 업데이트하는 방식을 취한다. 크게 3가지 방식의 알고리즘을 다루어보려한다. 

1. In-place dynamic programming
2. Prioritised sweeping
3. Real-time dynamic programming

In-place dynamic programming은 기존 DP 알고리즘처럼 2개의 배열 ($v_{k+1}$과 $v_k$)을 통해 구현되지 않고, in-place 방식을 통해 오직 하나의 배열만을 유지한다. 연산과 할당을 동시에 한다는 의미로 한국어로는 복합 대입이라 부르는데, 영단어가 더 익숙하므로 in-place라 하겠다. 

 

다시 말해, 다음과 같은 pseudocode가 아니라

$$
\begin{aligned}
  &\text{for all } s \in \mathcal{S} \\
  &\quad v_{\text{new}} (s) =  \underset{a \in \mathcal{A}}{\text{ max }} (\mathcal{R}_s^a + \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_{\text{old}} (s^\prime) \\
  &v_{\text{new}} \longleftarrow v_{\text{old}}
\end{aligned}
$$

in-place 대입으로 value iteration을 구현하면 된다.

$$
\begin{aligned}
  &\text{for all } s \in \mathcal{S} \\
  &\quad v (s) =  \underset{a \in \mathcal{A}}{\text{ max }} (\mathcal{R}_s^a + \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v (s^\prime))
\end{aligned}
$$

 

불필요한 배열 업데이트와 저장공간이 확보되므로, synchronous value iteration에 비해 더욱 효율적이다. 다만 value function은 Bellman equation에 의해 다른 state의 영향을 많이 받는다. 따라서 비동기화 방식의 독립적인 업데이트는 알고리즘을 더 불안정하게 한다. (물론 모든 state들이 독립적이더라도 꾸준하게 업데이트가 되면 수렴성은 보장된다. 불안정하다는 뜻은 수렴 시간이 더 길어질 수 있다는 것을 의미한다.)

---

Priortised sweeping은 backup될 state에 우선순위를 부여하는 방식이다. 만약 특정 state가 더 많은 업데이트를 필요로 한다면 높은 우선순위를 할당한다. 그리고 업데이트가 필요한 정도는 Bellman error을 기준으로 한다:

$$
\begin{aligned}
  | \underset{a \in \mathcal{A}}{\text{max }} (\mathcal{R}_s^a + \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v (s^\prime)) - v(s) |
\end{aligned}
$$

 

자세히 살펴보면 굉장히 직관적이게도 optimal value function과 현재 value function의 차이임을 볼 수 있다. 즉, Bellman error가 0인 경우 Bellman optimality equation을 만족하므로 backup할 필요가 없다. 반대로 만약 어떤 state가 가장 큰 Bellman error 값을 갖는다면 그 state를 먼저 backup하는 방식인 것이다. 우선순위를 따지는 알고리즘이므로 우선순위 큐를 통해 효율적으로 구현될 수 있다. 

---

마지막으로 real-time dynamic programming은 agent와 관련된 state만 업데이트한다. 다시 말하면 agent가 방문해본 적이 있는 state만 backup한다. 즉 agent가 방문해보지 못했거나 방문할 필요가 없는 state는 backup에서 배제된다. 따라서, 각 timestep $t$에 대해 agent는 $S_t, A_t, R_{t+1}$를 경험해보았으니, state $S_t$를 다음과 같이 backup한다.

$$
\begin{aligned}
  v (S_t) =  \underset{a \in \mathcal{A}}{\text{ max }} (\mathcal{R}_{S_t}^a + \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{S_t s^\prime}^a v_{\text{old}} (s^\prime))
\end{aligned}
$$

 

위 3가지 알고리즘들에서는 모든 state를 backup하지 않을 수 있기 때문에, 모든 state들이 꾸준하게, 골고루 update될 경우에만 실제 optimal point로 수렴하게 되고 일반적으로는 수렴성이 보장되지 않는다. 

Full-width and sample backups

Synchronous, asynchronous 방식과는 무관하게 dynamic programming 알고리즘은 MDP의 모든 정보, 즉 transition과 reward dynamic 등을 필요로 한다. 또한 value를 한 번씩 업데이트할 때마다 특정 state에서 가능한 모든 action과 그에 따른 successor state를 고려해야 한다. (이러한 방식을 full-width backup이라고 부른다.)

 

그러나 대부분의 environment의 MDP는 매우 복잡하고 잘 알려져있지 않다. 또한 state 및 action space가 굉장히 클 경우 차원의 저주 (curse of dimensionality)가 발생한다. 따라서 full-width backup 대신 RL에서 주로 쓰이는 알고리즘들은 sample backup 방식을 사용하는데, 이후 글에서 살펴볼 것이다. 미리 언급하자면 Monte-Carlo methods, Temporal Difference가 sample backup 방식을 사용한다. 

 

이러한 방식은 말 그대로 통계학에서 sampling 기법을 사용해 업데이트하는 것이다. Sample backup은 실제 reward function $\mathcal{R}$과 transition dynamics $\mathcal{P}$ 대신 sample reward와 sample transition, $\left\langle S, A, R, S^\prime \right\rangle$을 사용한다. Sample된 한 세트의 $\left\langle S, A, R, S^\prime \right\rangle$을 사용하기 때문에 full-width backup보다 간편하고, MDP의 정보를 필요로 하지 않으니 (model-free) 실용적이다.

---

Summary 

이 글에서는 MDP의 모든 정보를 알고 있는 상황에서 optimal policy $\pi^*$를 찾기 위한 방법을 살펴보았고, policy iteration과 value iteration 2가지가 있었다. Policy iteration은 policy evaluation과 policy improvement로 나뉘고, value iteration은 policy iteration의 2가지 subproblem들을 효율적으로 합친 알고리즘이다. 두 알고리즘의 pseudocode를 하나씩 비교해보는 것 [5] 으로 글을 마친다. 

 

$\mathbf{Fig. 6}$ Comparison between policy and value iteration

일반적으로 policy iteration이 value iteration보다 더 수렴이 빠른 것으로 알려져 있는데, 주로 policy가 value function보다 더 간단한 형태이기 때문이다.

---

Reference

[1] Reinforcement Learning: An Introduction. Richard S. Sutton and Andrew G. Barto, The MIT Press.

Reinforcement Learning

[2] Introduction to Reinforcement Learning with David Silver

Introduction to Reinforcement Learning with David Silver

[3] Planning by Dynamic Programming by Maël Fabien

Planning by Dynamic Programming

[4] A (Long) Peek into Reinforcement Learning

A (Long) Peek into Reinforcement Learning

[5] What is the difference between value iteration and policy iteration?

What is the difference between value iteration and policy iteration?