이번 포스팅은 지난 포스팅 Model-Free Policy Evaluation에 이어 Model-Free Policy Control에 대해 다루도록 하겠습니다. CS234 4강, Deep Mind의 David Silver 강화학습 강의 5강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 5, 6 기반으로 작성하였습니다.

지난 포스팅에서는 일정 정책 $\pi$ 아래 환경 모델을 모를 때 가치함수를 추정하는 방법인 Monte-Carlo(MC) policy evaluation과 Temporal Difference(TD) policy evaluation에 대해 다뤘습니다. 그러나 sequential decision prcoess 문제의 최종 목표는 최적화된 정책을 갖는 것(Control)입니다. 환경 모델을 알 때 Dynamic Programming(DP)는 policy iteration과 value iteration을 통해 최적 정책을 구할 수 있습니다. 환경 모델을 모를 때 최적 정책을 찾는 방법 Model-Free Control에 대해 자세히 다루기 전에 먼저, Generalized Policy Iteration에 대해 알아보겠습니다.

Generalized Policy Iteration

DP에서의 policy iteration을 다시 자세히 살펴봅시다. 정책 발전(policy improvement)를 greedy하게 하였으며, policy evaluation과 policy improvement를 번갈아 반복하는 policy iteration을 통해 최적 가치함수와 최적 정책을 구했습니다.

[\pi_0 \overset E\to v_{\pi_0} \overset I\to \pi_1 \overset E\to v_{\pi_1} \overset I\to \pi_2 \overset E\to \cdots \overset I\to \pi_\ast \overset E\to v_\ast]

<그림 1.>은 policy iteration을 그림으로 표현한 것입니다. 두 선은 각각 수렴된 가치함수와 정책들을 의미하고, 화살표는 policy evaluation과 policy improvement를 나타냅니다. 이 과정은 모두 결국 최적 정책과 최적 가치함수를 찾기 위한 것이기 때문에 두 선은 한 점에서 만납니다. 그런데, policy evaluation은 수렴할 때까지 시간이 오래 소요됩니다. 따라서, 위 가치함수 라인에 다다를 때까지 policy evaluation을 수행할 필요가 있을까요 ?

policy evaluation은 수렴할 때까지 시간이 오래 소요되기 때문에, 수렴할 때까지 기다리는 것이 아니라, 좀 더 효율적으로 접근하는 방법이 value iteration입니다. 가치함수를 한 스텝에 대해서만 업데이트를 하고, greedy policy improvement를 수행하는 value iteration을 통해 최적 가치함수와 정책을 찾았습니다.

위 두 방법 모두 결국 policy evaluation과정과 policy improvement과정의 상호작용으로 이뤄집니다. 두 과정 모두 안정화될 때, 즉 더 이상의 변화나 발전이 이뤄지지 않을 때, 그 때의 가치함수와 정책은 최적입니다. 따라서, 상호작용되는 과정이 조금씩은 차이가 있을 수 있지만 결국 둘의 상호작용으로 최적점에 다다르게 되는 것입니다. 이것이 바로 Generalized Policy Iteration(GPI)입니다.

Model-free control도 마찬가지로 GPI를 통해 최적 가치 함수와 최적 정책을 구합니다. Model-free control에 대해 알아보도록 하겠습니다. Model-free policy evaluation하는 방법으로 Monte-Carlo(MC)와 Temporal Difference(TD)가 있습니다. 마찬가지로, model-free control 하는 방법으로도 Monte-Carlo control와 Temporal-Difference control이 있습니다. 먼저, Monte-Carlo control부터 알아보겠습니다.

Monte-Carlo Control

지난 포스팅에서 알아본 monte-carlo estimation이 이제 control에 어떻게 사용되는지 생각해봅시다.

Monte Carlo Estimation of Action Values

Monte-Carlo control도 Monte-Carlo estimation과 함께 GPI를 통해 최적정책을 찾아나갑니다. 그러나, DP에서 다른 점이 있습니다. DP는 현재 상태 $s$ 에서 행동 $a$ 를 취했을 때, 받을 수 있는 보상과 다음 상태가 어떻게 될지 알 수 있습니다. 따라서 다음 상태로 올 수 있는 모든 후보들과 보상을 고려하여 최대 가치를 반환하는 다음 상태를 찾은 후 그 상태로 가게 되는 행동을 취합니다. 즉, 상태 가치 함수 정보만으로 충분합니다.

그러나 model-free 환경의 문제점은 직접 경험하지 않는 이상 다음 상태와 보상이 어떻게 될지 알 수 없습니다. 따라서 상태 가치 함수만으로 행동을 선택할 때 충분한 정보를 제공하지 못합니다. 이러한 이유로 model-free control에서는 상태 가치 함수 $v(s)$ 에 대한 evaluation이 아니라, 상태-행동 가치 함수 $q(s,a)$ 에 대한 evaluation을 수행합니다. 상태 s에 대해 모든 행동 a에 대해 $q(s,a)$ 를 비교하여 가장 가치가 높은 행동을 선택하는 것이 상태 s에 대한 정책이 되는 것입니다.

Importance of Exploration

GPI는 ‘좋은’ 정책 $\pi$ 을 계속 찾아나가면 언젠간 최적 정책 $\pi_*$ 에 수렴합니다. 그러면 ‘좋은’ 정책 $\pi$ 는 ‘좋은’ $Q_\pi$ 추정치를 찾아야 합니다. 그래야지만 policy improvement를 통해 최적 정책을 찾아나갈 수 있기 때문입니다.

[q_{\pi}(s, \pi’(s)) \geq v_\pi(s)]

‘좋은’ $Q_\pi$ 추정치는 어떻게 찾을까요? 가능한 한 나올 수 있는 모든 $(s,a)$ 시퀀스를 경험하면 됩니다. MC policy evaluation에서 true expected value에 수렴하기 위해서 에피소드 샘플링을 많이 해야 하는 것과 같습니다.

그러나 model-free 환경에서 모든 $(s,a)$ 쌍으로 구성된 모든 시퀀스를 경험하기는 어렵습니다. 경우의 수가 너무 많기 때문이고, 환경을 모르기 때문에 예측도 어렵습니다. <그림 5.>를 보면 DP같은 경우는 환경을 알기 때문에 V(s)를 추정하기 위해 다음에 나올 trasition model $P^{a}_{ss’}$ 와 함께 모든 상태 s를 고려할 수 있습니다. 따라서, ‘좋은’ 추정치를 계산할 수 있습니다. 즉, 이렇게 찾아진 가치 함수 추정치 기반으로 greedy하게 행동을 선택해도 policy improvement가 일어납니다( DP포스팅 policy improvement 참고 ).

반면에, model-free 같은 경우, MC와 TD모두 샘플링을 통해 (s,a)를 경험해 나갑니다. 그렇기 때문에 많은 (s,a)쌍을 방문하지 못하는 문제가 발생합니다. 이로 인해 어떤 (s,a)에 대해서는 좋은 추정치를 얻지 못합니다. 따라서 부정확한 추정치 기반으로 greedy하게 행동을 선택하는 건 심각한 문제를 일으킵니다. Q(s,a)를 추정하는 이유는 상태 s에 있을 때, 여러 행동 a들을 비교하기 위해서입니다. 그러나 어떤 행동 a에 대해서 Q(s,a)가 나쁜 값을 가지게 된다면 공정한 비교가 되지 않습니다. 즉, 학습이 제대로 이뤄지지 않게 되는 것입니다. 이 문제가 바로 ‘exploration’ 문제입니다. 따라서 정책을 평가하기 위한 좋은 Q(s,a)를 구하기 위해선 충분하고 지속적인 탐험(continual exploration)이 보장되어야 합니다.

충분하고 지속적인 탐험을 가장 심플하게 구현한 건 모든 행동들에 대해 선택할 가능성을 열어두는 것입니다. 이러한 방법 중 하나가 $\epsilon-greedy$ 입니다.

The simplest idea for ensuring continual exploration is that all actions are tried with non-zero probability.

$\epsilon-greedy$ 는 $\epsilon$ 의 확률로 행동을 랜덤하게 선택하고, $1-\epsilon$ 의 확률로 greedy한 행동을 선택합니다. $\frac{\epsilon}{m} + 1-\epsilon + \frac{\epsilon}{m}\times(m-1) = 1$ 이 되므로 $\epsilon-greedy$ 식을 아래와 같이 구축할 수 있습니다. 여전히 $\epsilon$ 의 확률로 탐험할 가능성을 두는 것입니다.

[\pi(a \mid s) = \begin{cases} \frac{\epsilon}{m} + 1-\epsilon & \quad \text{if} \quad a^{*}=arg \underset m maxQ(s,a)
\frac{\epsilon}{m} & \quad \text{otherwise} \end{cases}]

on-policy Monte-Carlo Control

이 단락에서 다루는 MC Control은 on-policy 기반입니다. on-policy와 off-policy의 차이는 off-policy MC Control에서 설명하도록 하겠습니다.

진짜로 이제 MC기반의 Control에 대해 알아보겠습니다. 위에서 model-free인 경우도 Generalized Policy Iteration을 통해 최적 가치함수와 최적 정책을 찾는다고 하였습니다. MC기반 policy evaluation은 상태-행동 가치 함수인 $Q_\pi$ 를 찾는 것이고, MC기반 policy improvement는 $\epsilon-greedy$ 를 따릅니다. 그런데, <그림 6.>의 왼쪽 그림처럼, policy evaluation을 $Q_\pi$ 를 수많은 에피소드를 샘플링해서 수렴할 때 반복하는 건 너무 번거롭습니다. 따라서 DP의 value iteration처럼 에피소드 하나가 끝날 때까지만 상태-행동 가치 함수 Q를 업데이트하고, policy improvement를 수행합니다.

이런 방식의 MC 기반 GPI가 과연 최적 정책을 찾게 해주는지에 대해선 아직 해결해야 할 문제가 남았습니다. $\epsilon-greedy$ 방식이 진짜로 정책을 발전 시키는지에 대한 문제와 하나의 최정정책, 가치함수로의 수렴하는지에 대한 문제입니다. 먼저 첫번째 문제부터 살펴보겠습니다.

$\epsilon-greedy$ Improvement
$\epsilon-greedy$ 방식으로 정책을 발전시키려면 $V_{\pi_{i+1}}(s) \geq V_{\pi_{i}}(s)$ 를 만족해야 합니다. 아래는 이와 관련된 증명입니다.

$Q^{\pi_i}(s,\pi_{i+1}(s)) \geq V_\pi(s)$ 이므로, $V_{\pi_{i+1}}(s) \geq V_{\pi_{i}}(s)$ 가 성립합니다. 이렇게 되는 자세한 과정은 지난 DP 포스팅 policy improvement쪽을 참고 바랍니다. 따라서, $\epsilon-greedy$ 에 의한 정책 발전이 일어납니다.

Greedy in the Limit of Infinite Exploration
정책 발전이 일어나는 것과 동시에, 매 스텝마다 정책을 발전시키려면 결국 greedy한 정책으로 수렴해야 합니다. $\epsilon-greedy$ 방식은 모든 행동이 선택될 확률이 non-zero probability라 가정을 하지만, 결국 iteration을 반복해 나가면서 하나의 행동에 대해 $\pi(a \mid s) = 1$ 의 확률을 가져야 되는 것입니다. 이것에 관한 내용을 Greedy in the Limit of Infinite Exploration(GLIE) 라 합니다. 따라서, GLIE를 만족해야 수렴된 정책을 가질 수 있습니다.

$e-greedy$ 가 GLIE를 만족하게 하는 가장 심플한 방법은 $\epsilon = \frac{1}{k}$ 로 하여 매 스텝마다 $\epsilon$ 을 감소시켜 0에 수렴하게 하는 것입니다. 따라서, GLIE Monte-Carlo Control 알고리즘을 정리하면 아래와 같습니다.

off-policy Monte-Carlo

Off-policy MC에 대해 설명하기 전에 on-policy learning과 off-policy learning에 대해 알아보겠습니다.

on-policy vs. off-policy
이제까지 설명한 MC control 방법은 on-policy control입니다. On-policy란 탐험할 때 따르는 정책과 찾고자 하는 최적 정책이 같은 경우입니다. $\epsilon-greedy$ MC control이 왜 on-policy인지 살펴보면 다음과 같습니다. 한 에피소드 내에서 매 상태 s마다 행동 a를 샘플링합니다. 이 때, $\epsilon$ 의 확률로 정책에 따른 행동 $a=arg \underset m maxQ(s,a)$ 을 샘플링합니다. 그리고 한 에피소드가 다 끝나고 정책을 업데이트 할 때도 이렇게 정책에 따른 행동들을 기반으로 가치함수를 업데이트하여 $\pi_k = \epsilon-greedy(Q)$ 로 정책을 발전시킵니다. 즉, 기존 행동 샘플링할 때 사용된 정책 기반으로 정책을 발전시키는 것입니다. 이것이 바로 on-policy learning입니다.

On-policy learning is
- learn on the job
- learn about policy $\pi$ from experience sampled from $\pi$

그러나 이미 정책을 발전시키는 과정이 greedy한 정책을 한번 찾은 후, 그 정책 위에서 $\epsilon-greedy$ 같은 방법으로 탐험을 하는 것입니다. 그렇기 때문에 탐험을 하는 (s,a)공간이 매우 협소합니다. 이미 발전시킨 정책 위에서 탐험을 하기 때문에, (s,a) 공간위에서 보면 이미 발전시킨 정책 $\pi$ 에 해당되는 공간 근처에서만 탐험이 이뤄지는 것입니다. 마치 그림으로 표현하면 아래와 같을 수 있습니다.

그렇다면 이를 해결할 수 있는 방법은 어떤 것이 있을까요? 바로, 탐험하는 정책과 최적 정책을 찾기 위해 학습하는 정책을 분리하는 것입니다. 이것이 바로 off-policy learning입니다. 마치 분류 모델을 위한 지도학습을 진행 할 때, 모든 라벨에 해당되는 데이터가 존재하고, 분포도 고루 존재하면 학습이 더 잘되는 것과 비슷하다고 생각하면 됩니다. 좀 더 다양한 경험을 한 시퀀스 데이터가 많으면 best 답안에 가까운 정책을 찾을 수 있습니다. 그렇기 위해선 탐험의 범위가 넓어야 합니다.

Off-policy learning is
- look over someone's shoulder
- learn about policy $\pi$ from experience sampled from $\mu$

일반적으로, 학습하고자 하는 정책을 target policy라 하고, 학습을 위한 데이터를 생성하기 위한 정책을 behavior정책이라 합니다. 학습을 위한 데이터를 학습하고 하는 정책에서 ‘벗어나서’ 수집하기 때문에, ‘off-policy’라 합니다.

Importance Sampling
대부분의 off-policy 방식은 importance sampling을 이용합니다. Importance sampling이란 기댓값을 계산하고자 하는 확률 분포 $p(x)$ 의 확률 밀도 함수(probability density function, PDF)를 모르거나 안다고 해도 $p$ 에서 샘플을 생성하기 어려울 때, 비교적 샘플을 생성하기 쉬운 $q(x)$ 에서 샘플을 생성하여 $p$ 의 기댓값을 계산하는 것입니다.

[\begin{align} E_{x \sim p}[f(x)]&=\int p(x)f(x)dx\&=\int \frac{p(x)}{q(x)}q(x)f(x)dx\&=E_{x \sim q}[\frac{p(x)}{q(x)}f(x)] \end{align}]

Importance Sampling for Off-Policy Monte-Carlo
그렇다면 importance sampling을 off-policy MC에서 어떻게 이용하는지 알아보도록 하겠습니다. 위에서 설명한 importance sampling 개념대로 target policy와 behavior policy를 보면, 기댓값을 계산하고자 하는 확률 분포 $p(x)$ 에 해당하는 건 target policy $\mu$ 이고, 실제 샘플하는 분포 $q(x)$ 는 behavior policy $\pi$ 입니다. 우리가 계산하고자 하는 기댓값은 $V(s) = E[G_t \mid S_t=s]$ 이므로, 즉 두 분포의 비율 $\frac{\pi(A_t \mid S_t)}{\mu(A_t \mid S_t)}$ 을 $G_t$ 에 곱하여 기댓값을 계산해야 합니다. 그러나, 단일 샘플링이 아니라 전체 에피소드에 대한 샘플링이기 때문에 importance sampling한 $G_t^{\pi/\mu}$ 는 아래와 같습니다.

[G_t^{\pi/\mu} = \frac{\pi(A_t \mid S_t)}{\mu(A_t \mid S_t)}\frac{\pi(A_{t+1} \mid S_{t+1})}{\mu(A_{t+1} \mid S_{t+1})} \dots \frac{\pi(A_{T} \mid S_{T})}{\mu(A_{T} \mid S_{T})}G_t]

따라서 MC policy evaluation에서 $G_t$ 가 아닌 $G_t^{\pi/\mu}$ 로 가치함수를 업데이트해주면 됩니다.

[V(S_t) \leftarrow V(S_t) + \alpha(G_t^{\pi/\mu} - V(S_t))]

그러나 importance sampling 같은 경우 infinite variance를 가지는 단점이 있습니다. 이러한 이유로 수렴하기가 매우 어렵습니다. 따라서 현실적으로 importance sampling을 통한 off-policy Monte-Carlo방식은 사용되지 않습니다.

Temporal-Difference Control

다음은 Temporal-Difference(TD) Control에 대해 알아보겠습니다. On-policy TD control을 Sarsa이고, off-policy TD control을 Q-Learning이라 합니다. SARSA에 대해서 먼저 알아보겠습니다.

Sarsa : On-policy TD Control

TD control도 MC control과 마찬가지로, Generalized policy iteration(GPI) 을 따릅니다. Policy evaluation만 TD update을 이용하고 그 외 다른 건 모두 MC control와 같습니다.

[Q(S,A) \leftarrow Q(S,A) + \alpha(R+\gamma Q(S’,A’) - Q(S,A))]

위 update 식에서 샘플링 단위가 (S, A, R, S’, A’)이기 때문에 Sarsa 라는 이름이 붙여졌습니다. Srasa 알고리즘 전체는 아래와 같습니다.

Sarsa도 on-policy MC에서 살펴본 것처럼 정책 발전 문제와 수렴 문제를 살펴보겠습니다. 정책 발전 문제는 on-policy MC와 동일하게 $\epsilon-greedy$ 를 사용하기 때문에 정책 발전은 일어납니다.

반면에 수렴문제는 GLIE를 만족시키는 것 이외에 업데이트 스텝 크기인 $\alpha$ 에 대한 조건이 더 필요합니다. 그 이유는 MC와 다르게 TD는 스텝마다 업데이트가 일어나는 on-line 방식이기 때문에 스텝사이즈 크기에 따라 수렴이 되지 않고 발산이 될 수 있습니다. 스텝크기 $\alpha$ 는 Q 가치함수가 변화가 일어나야 하므로 충분히 크며 동시에 Q 가치함수가 수렴해야 하므로 충분히 작아야 합니다.

[\sum_{t=1}^{\infty}\alpha_t=\infty]

[\sum_{t=1}^{\infty}\alpha^2_t<\infty]

그러나 실제 문제를 풀 때 $\alpha$ 를 결정하는 건 위의 이론을 이용하진 않고 domain-specific하게 또는 실험적으로 정한다고 합니다.

sarsa 문제 예를 보겠습니다. 아래는 S에서 시작해서 G로 가야하는 문제입니다. 행동은 위, 아래, 좌, 우이며, 화살표가 있는 곳에서 아래에서 위로 바람이 불고 있습니다. 따라서 이 곳을 지날 때 실제 위로 가는 행동을 해도 실제 움직임은 대각선 우상향으로 가게 됩니다. 매 스텝마다 보상은 -1이며 discount factor 1입니다.

<그림 12.> 그래프는 Sarsa 학습 결과입니다. 1에피소드가 끝날 때 까지 2000 스텝을 밟지만 그 다음부터 학습속도가 빨라지는 것을 볼 수 있습니다.

Q-Learning : Off-policy TD Control

다음은 off-policy TD 방식인 Q-Learning에 대해서 알아봅시다. Off-policy MC와 다르게 importance sampling이 필요 없습니다. Sarsa 에서 $Q(S_t, A_t)$ 를 업데이트 하기 위해, 정책 $\pi$ 에 따라 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ 을 샘플링 한 후, $Q(S_{t+1}, A_{t+1})$ 기반으로 현재 상태 $(S_t, A_t)$ 를 수정했습니다. 즉, 샘플링된 정책과 학습하는 정책이 일치합니다. 그러나 Q-Learning은 off-policy로 샘플링되는 정책(behavior policy)과 학습하는 정책(target policy)이 다릅니다.

[Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1}+\gamma Q(S_{t+1},A’)-Q(S_t, A_t))]

• Next action is chosen using behavior policy $A_{t+1} \sim \mu(\cdot \mid S_t)$
• But we consider alternative successor action $A’ \sim \pi(\cdot \mid S_t)$

다음 상태에 대한 행동을 behavior policy에 따라 선택하지만 실제 $Q(S_t, A_t)$ 를 업데이트하기 위해서 다음 상태에 대한 행동은 behavior policy와 다른 target policy에 의해 선택합니다. 즉, $A’$ 에 대해서 $Q(S_t, A_t)$ 를 업데이트하고 다음 업데이트 할 (s,a) 쌍은 $(S_{t+1}, A’)$ 이 아니라 behavior policy 따른 $(S_{t+1}, A_{t+1})$ 인 것입니다. 이 때, $A’=A$ 일수도 있고, $A’ \ne A$ 일수도 있습니다.

Q-learning은 taret policy와 behavior policy를 같이 발전시켜 나갑니다. 이때, target policy $\mu$ 는 $Q(s,a)$ 에 관한 greedy policy이고 behavior policy $\pi$ 는 $Q(s,a)$ 에 관한 $\epsilon-greedy$ 입니다.

• Target policy : $\pi(S_{t+1}) = arg \underset {a’} maxQ(S_{t+1},a’)$
• Behavior policy :
  \(\mu(a \mid s) = \begin{cases} \frac{\epsilon}{m} + 1-\epsilon & \quad \text{if} \quad a^{*}=arg \underset m maxQ(s,a) \\ \frac{\epsilon}{m} & \quad \text{otherwise} \end{cases}\)

위의 behavior policy와 target policy를 가지고 Q-Learning 식을 다시 쓰면 아래와 같습니다.

[\begin{align} Q(S_t,A_t) &\leftarrow Q(S_t, A_t) + \gamma Q(S_{t+1},A’)\&\leftarrow Q(S_t, A_t) + \gamma Q(S_{t+1},arg \underset {a’} maxQ(S_{t+1},a’)\&\leftarrow Q(S_t, A_t) + \gamma m \underset {a’} ax Q(S_{t+1}, a’) \end{align}]

따라서, Q-learning 알고리즘은 아래와 같습니다.

Sarsa vs. Q-Learning
그렇다면 Sarsa와 Q-Learning은 실제 학습 시 어떤 차이를 보일까요 ? 아래 cliff Waling 예제를 통해 확인해 보겠습니다.

S에서 시작해서 G로 가는 문제입니다. The Cliff에 도달하면 R=-100을 받고 다시 S로 돌아갑니다. 다른 곳에 밟으면 R=-1을 받습니다. 행동은 위, 아래, 좌, 우이며, $\epsilon=0.1$ 입니다. 학습이 완료됐을 때 최적 정책 결과는 <그림 14.>에서 위에 있는 그림입니다. Sarsa는 safe path로 학습되지만 Q-learning은 optimal path로 학습됩니다.

Sarsa는 학습되는 방향이 현재 따르는 정책에서 선택된 행동이 고려되기 때문에 path의 길이는 길지만 좀 더 안전한 길을 선택하게 됩니다. 반면에, Q-Learning 같은 경우 학습되는 방향이 현재 따르는 정책과 무관하기 때문에 현재 상태에서 가장 최적의 선택이 될 수 있는 길로 학습이 됩니다. 그렇기 때문에 Sarsa 같은 경우 보상의 합이 Q-Learning보다 크게 나타납니다.

이상으로 이번 포스팅을 마치겠습니다. 읽어주셔서 감사합니다.

1. Importance Sampling, https://untitledtblog.tistory.com/135

이번 포스팅과 다음 포스팅은 유한개의 상태, 유한개의 행동에 대해 환경 모델을 모를 때, sequential decision process를 푸는 방법에 다룹니다. 지난 DP 포스팅에서, policy iteration을 이용하여 MDP를 풀었습니다. 마찬가지로 환경 모델을 알지 못한 경우도 유사하게 접근할 수 있습니다. policy iteration은 policy evaluation과 policy control로 나뉘는데 이번 포스팅은 policy evaluation을 푸는 방법에 다룰 것이고 다음 포스팅은 policy control에 대해 다루도록 하겠습니다. CS234 3강, Deep Mind의 David Silver 강화학습 강의 4강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 5, 6 기반으로 작성하였습니다.

policy evaluation은 현 정책이 얼마나 좋은지 평가하는 것으로, 현 정책 아래 가치함수를 구하는 것입니다. DP는 환경 모델을 알 때, 벨만 기대 방정식을 이용하여 iterative한 방법으로 현 정책 아래에서 가치함수를 구하는 과정입니다. 현 상태에서 특정 행동을 취할 때, 나올 수 있는 다음 상태와 받을 보상을 알고 있기 때문에 아래 식과 같이 expectation을 직접 “계산”을 할 수 있었습니다.

(이러한 이유로, DP는 learning이 아니라 planning이라 했었습니다.) 그러나 환경 모델을 알지 못할 때, 즉, 상태 변환 모델과 보상 모델을 알지 못할 때 어떻게 정책을 평가할 수 있을까요? 바로 경험(experience)을 직접하는 것입니다. 시퀀스를 직접 밟아 나가면서 가치함수를 학습해 나가는 것입니다. 이 때, 경험을 통해 가치함수를 학습하는 방법을 두가지가 있습니다. Monte Carlo 방식와 Temporal Difference 방식입니다. 먼저, Monte Carlo policy evaluation 부터 알아보겠습니다.

Monte-Carlo Policy Evaluation

Monte-Carlo Policy Evaluation을 살펴보기 전에, Monte-Carlo 방식을 우선 알아보겠습니다.

Monte-Carlo Methods

Monte-Carlo 방법은 무작위 샘플링을 통해 우리가 알아보고자 하는 시스템의 분포를 추정하는 것입니다. 아래 그림은 Monte-Carlo 방식으로 원의 넓이를 추정하는 것입니다.

원의 넓이를 구하는 방법이 너무나 복잡하거나 알 수 없다고 가정해 봅시다. 이런 상황에서 원의 넓이를 가장 쉽게 구하는 방법은 점을 무수히 많이 뿌려본 뒤, 사각형의 넓이 $\times$ (원 안에 들어온 점의 갯수 / 전체 점의 갯수) 로 원의 넓이를 추정할 수 있습니다. 이처럼 Monte-Carlo방식은 점을 무수히 많이 찍는 것처럼 무작위 샘플링으로 데이터를 많이 수집하게 되면 우리가 알고자 하는 시스템의 분포를 추정할 수 있다는 개념입니다.

Monte-Carlo Policy Evaluation

따라서, Monte-Carlo Policy Evaluation이란 에이전트가 환경과 직접 상호작용하여 상태, 행동, 보상으로 이뤄진 시퀀스를 무수히 많이 sampling하여 경험을 얻고, 그 경험을 바탕으로 가치함수를 구하는 것입니다. 즉, 무작위 샘플링을 통해 환경 모델을 내재적으로 추정하는 것이죠. ‘내재적’이라 표현한 이유는 추정하고자 하는 것이 상태 변이 확률 또는 보상 확률이 아니라 value function이기 때문입니다. 결국 value function를 구하기 위해선 환경 정보를 알고 있어야 구할 수 있는데(DP에서의 Policy Evaluation 참고) 샘플링을 통해 이를 구하는 것이 내재적으로 환경모델을 추정하는 거라고 생각할 수 있는 것이죠.

다시 정리하면 Monte-Carlo 방식은 환경에 대한 정보없이, 오로지 ‘경험(experience)’를 통해 학습하는 것입니다.

사실 학습은 policy evaluation과 policy control의 상호작용으로 이뤄집니다. 본 포스팅은 학습이라 표현하지만, policy evaluation에 초점을 맞춰 작성하였습니다.

value function의 정의를 다시 살펴보면,

상태 s에서의 return $G_t$ 에 대한 기댓값입니다. Monte-Carlo 방식으로 value function을 구하면 샘플링한 많은 경험들 중에서 상태 s에서부터의 return $G_t$ 를 직접 구한 뒤, 경험의 갯수만큼 나눠주면 됩니다. 즉, return에 대한 기댓값이 아니라 return에 관한 평균값입니다.

Monte-Carlo policy evaluation uses empirical mean return instead of expected return. In other words, Policy is evaluated based on averaging sample returns.

아래 예시를 통해, 어떻게 계산하는지 알아봅시다.

<그림 2>와 같이, C1에서 시작한 시퀀스들에 대한 return 값들이 있습니다. $s_t = C1$ 의 value function을 Monte-Carlo 방식으로 추정하면 (-2.25-3.125-3.41-3.20)/4 = -3.0 이 됩니다.

그러나 Monte-Carlo 방식으로 가치함수를 추정하려면 샘플 시퀀스인 episode가 끝나야 합니다. 즉, 모든 에피소드가 끝나야 Monte-Carlo 방식을 적용할 수 있습니다. 따라서 에피소드가 끝날 때 까지 기다린 후, 평균값을 업데이트하는 방식으로 적용할 수 있습니다.

first-visit MC vs. every-visit MC

Monte-Carlo 방식은 두 가지가 있습니다. first-visit MC와 every-visit MC입니다. 한 에피소드에서 같은 상태를 여러번 반복해서 지나갈 수 있습니다. 이 때, 첫번째 상태에 대한 return값만 value function 업데이트에 이용하고, 나머지는 무시하는 방법이 first-visit MC이고 모든 경우를 고려한 것이 every-visit MC입니다. 아래 그림은 first-visit MC policy evaluation과 every-visit MC policy evaluation 순서입니다.

일반적으로 first-visit MC를 많이 씁니다. 그렇다면 first-visit과 every-visit은 어떤 차이가 있을까요? first-visit MC 같은 경우, 각 상태에 대한 return들은 모두 독립입니다. 왜냐하면 샘플링된 episode가 독립이므로 first-visit만 고려하기 때문에, 각 상태에 대한 return $G_t$ 은 서로 관련이 없고 독립입니다. 즉, 상태 s에 대한 return $G_t$ 는 $v_\pi(s)$ 분포에서, i.i.d성질을 지니게 됩니다(independent and identically distributed). 따라서, 대수 법칙(law of large numbers)에 따라, 상태 s에 대한 return 값을 무수히 많이 샘플링 하게 된다면, return에 대한 평균은 우리가 구하고 싶은 상태 s의 value function 기댓값인 $\mathbb{E_\pi}[G_t \mid s_t=s]$ 에 수렴합니다.

쉽게 다시 설명하겠습니다. 어떤 상태 s에 대한 가치를 구할 때마다 항상 다르게 나올 수 있습니다. 그런데 충분히 많이 상태 s를 밟는다면 대표적으로 많이 나오는 값이나 그 값 주변 값이 자주 등장하겠지요. 즉, 우리는 $v_\pi(s)$ 가 분포를 이룬다고 생각할 수 있습니다. 그런데 우리가 구하고 싶은 건 분포안에서 $v_\pi(s)$ 를 대표하는 값을 찾고 싶은 것입니다. 즉, 자주 등장하는 값을 말입니다. 따라서, 그 분포의 평균인 기댓값 $\mathbb{E_\pi}[G_t \mid s_t=s]$ 을 말입니다. first-visit MC 방식으로 샘플링한 $G_t$ 는 i.i.d성질을 띄기 때문에, 분포를 정확히 모르지만(분포를 안다면 굳이 샘플링 하지 않고 바로 기댓값이 계산이 가능하겠죠?) 결국 $v_\pi(s)$ 분포를 추정할 수 있고, 이는 우리가 구하고 싶은 기댓값에 수렴할 수 있음을 의미합니다.

따라서, first-visit MC 방식에 의한 추정은 unbiased한 성질을 지닙니다. 반면에, every-visit MC 방식에 의한 추정은 biased한 성질을 띕니다. 한 에피소드 내에서 같은 상태를 여러 번 반복해서 지나갔다면, 그 상태들 간은 독립적이지 않고, 상관관계를 가지게 됩니다. 따라서, i.i.d하지 않기 때문에 biased합니다. 그렇기 때문에 MC 방식에 의한 policy evaluation은 first-visit MC를 선호하는 편이라 합니다(sutton and barto교재 및 stanford강의 참고).

Incremental Monte-Carlo Updates

Value function을 업데이트하는 방식을 에피소드가 끝날 때마다 마치 온라인 방식처럼 순차적으로 업데이트할 수 있습니다. 시퀀스 $x_1, x_2, \dots$ 에 대한 평균 $\mu_1, \mu_2, \dots$ 가 있을 때,

[\begin{align} \mu_k&=\frac{1}{k}\sum_{j=1}^{k}x_j\&=\frac{1}{k}\left(x_k+\sum_{j=1}^{k-1}x_j\right)\&=\frac{1}{k}\left(x_k + (k-1)\mu_{k-1}\right)\&=\mu_{k-1}+\frac{1}{k}\left(x_k-\mu_{k-1}\right)\end{align}]

입니다. 따라서, episode $S_1, A_1, R_2, \dots, S_T$ 가 끝날 때마다 아래와 같이 업데이트 할 수 있습니다.

[N(S_t) \leftarrow N(S_t) + 1]

[V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)}\left(G_t-V(S_t)\right)]

두번째 식을 마치 $\left(G_t-V(S_t)\right)$ 를 새로운 데이터와 기존 평균과의 오차 즉 에러항으로 본다면, 기존 평균값을 오차의 방향으로 1/k만큼 수정해 나간다고 해석할 수 있습니다.

위의 업데이트 방식은 맨 처음에 샘플한 에피소드부터, 가장 최근에 샘플한 에피소드까지 모두 중요하게 생각함을 의미합니다. 왜냐하면 동등하게 에피소드 개수만큼으로 나누고 있기 때문입니다. 하지만 시간에 따라 조금씩 변하는 문제 같은 경우(non-stationary)에 위와 같은 업데이트 방식은 적합하지 않습니다. 따라서, 새 에피소드와 기존 평균사이의 오차를 항상 일정 크기만큼 업데이트하여 시간이 지날수록 오래된 과거는 잊고 가장 최근 사건을 좀 더 기억할 수 있게끔 해줍니다.

[V(S_t) \leftarrow V(S_t) + \alpha\left(G_t-V(S_t)\right)]

Temporal-Difference Policy Evaluation

다음은 Temporal-Difference Policy Evaluation에 대해 알아보겠습니다. Temporal-Difference(TD) 도 Monte-Carlo(MC) 와 마찬가지로 환경 모델을 알지 못할 때(model-free), 직접 경험하여 Sequential decision process 문제를 푸는 방법입니다. Temporal-Difference 학습은 Monte-Carlo와 Dynamic Programming을 합쳐 놓은 방식입니다. MC처럼, 환경모델을 알지 못하기 때문에 직접 sampling한 데이터를 통해 학습을 해야 합니다. DP처럼, 에피소드가 끝날 때까지 기다리지 않고 다른 가치 추정치를 가지고 현재 상태 가치를 추정합니다. 이를 bootstrap이라 합니다.

TD는 MC와 다르게 무한한 에피소드에 대해서도 적용할 수 있습니다. 그 이유는 MC는 업데이트를 하기 위해서 한 에피소드가 끝날 때까지 기다려야 합니다. 그래야 return $G_t$ 를 구한 뒤, 업데이트를 할 수 있기 때문입니다. 따라서, MC는 에피소드 샘플링을 통해 실제 return $G_t$ 을 향해 $V(S_t)$ 를 수정해나갑니다.

[V(S_t) \leftarrow V(S_t) + \alpha\left(G_t-V(S_t)\right)]

반면에, TD는 에피소드가 끝날 때까지 기다릴 필요 없이, 다음 상태를 밟을 때까지만 기다렸다가 업데이트합니다. 그렇기 때문에 에피소드가 끝나지 않는 시퀀스에 대해서도 적용할 수 있으며, 시퀀스를 밟아나가면서 그때그때 가치함수를 수정해 나갈 수 있습니다. 이러한 특징으로 인해, TD 방법은 online learning이 가능합니다. 이 부분이 TD의 매우 큰 장점입니다.

[V(S_t) \leftarrow + \alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]]

TD policy evaluation을 상세히 살펴보면, DP에서의 벨만 기대 방정식을 이용한 policy evaluation과 유사한 것을 보실 수 있습니다.

그러나 DP는 환경모델을 알기 때문에, 다음 상태가 될 수 있는 모든 후보들을 고려하여 가중 평균을 한 추정값으로 다음 상태의 가치 추정값만을 가지로 현재 상태의 가치를 업데이트합니다. 반면에, TD는 환경에 대한 정보가 없기 때문에 다음 상태까지 직접 밟아보는 것입니다. 이것을 ‘다음 상태 s’를 직접 샘플링하였다’라고 합니다. 그러나 DP처럼 다른 상태의 추정값을 가지고 현재 상태값을 수정하고자 합니다. 이를 bootstrap이라 합니다. 즉, TD에서의 bootstrap은 아래 그림 처럼 이해할 수 있습니다.

따라서, MC는 실제 return $G_t$ 를 향해 $V(S_t)$ 를 수정해 나가지만 TD는 estimate $G_t$ 을 향해 $V(S_t)$ 를 고쳐나가면서 시퀀스를 진행합니다.

• MC Policy Evaluation :
  update value $V(S_t)$ toward actual return $G_t$
• TD Policy Evaluation :
  update value $V(S_t)$ toward estimated return $R_{t+1} + \gamma V(S_{t+1})-V(S_t)$

General form of update rule

위의 MC/TD 업데이트 식은 일반적으로 아래와 같은 형태를 띕니다.

[NewEstimate \leftarrow OldEstimate + StepSize \left[Target - OldEstimate\right]]

$\left[Target - OldEstimate\right]$ 는 오차를 나타냅니다. MC와 TD 모두 Target을 향해 기존 Estimate을 업데이트합니다. 그러나, 기존 estimate을 새로운 target으로 교체하는 건 위험합니다. 왜냐하면 초기단계에서는 새로운 target이 우리가 찾는 정답이 아닐 수도 있기 때문에, target과 기존 estimate의 오차의 일부만큼만 조금씩 수정해 나갑니다. MC target은 $G_t$ 이고, TD target은 $R_{t+1}+\gamma V(S_{t+1})$ 입니다. 또한, MC error는 $G_t - V(S_t)$ 이고, TD error는 $R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ 입니다. 보통 TD error는 $\delta_t$ 로 표현합니다. 왜냐하면, 같은 에피소드 내에서, TD error는 매 t step마다 다르기 때문입니다.

Temporal Difference Policy Evaluation Algorithm

TD policy evaluation 알고리즘 순서도는 아래와 같습니다.

일정 정책 $\pi$ 아래, (S, A, R, S’)를 샘플링하고, 업데이트합니다. 그런 다음 (S’, A’, R, S’‘)를 샘플링하고 업데이트합니다. 이 과정을 V(S)가 수렴할 때까지 반복합니다. 여기서 한가지 의문점이 있습니다. MC방식은 unbiased estimator이기 때문에 대수의 법칙에 따라, true expected estimate에 수렴한다고 하였습니다. 과연 TD방식은 수렴할까요? 이는 다음 포스팅 Model-Free Control에서 다루도록 하겠습니다.

TD policy evaluation 예를 살펴보겠습니다.

먼저 $(s_3, a_1, 0, s_2)$ 에 대해 $v(s_3)$ 를 업데이트하고, 그 다음 $(s_2, a_1, 0, s_2)$ 에 대해 $v(s_2)$ 를, $(s_2, a_1, 0, s_1)$ 에 대해 $v(s_2)$ 를, 마지막으로 $(s_1, a_1, 1, terminal)$ 에 대해 $v(s_1)$ 을 업데이트하면 한 에피소드에 대해 업데이트를 완료하게 됩니다.

Monte-Carlo vs. Temporal-Difference

이제까진 MC와 TD방식으로 policy evaluation하는 것을 보았습니다. 그러면 두 방식의 특성을 비교하겠습니다.

Bias/Variance Trade-Off

MC와 TD의 특징을 bias-variance trade-off 관점에서 보겠습니다. MC는 위에서 설명한 것처럼, return $G_t$ 는 $v_\pi(S_t)$ 의 unbiased estimate 입니다. 따라서 MC는 low bias의 특징을 띕니다. 반면에, TD는 bootstrap 기반이기 때문에 TD target $R_{t+1} + \gamma V(S_{t+1})$ 은 $v_\pi(S_t)$ 의 biased estimate 입니다. 따라서 TD는 high bias 특징을 가집니다.

그러나, variance관점에서 두 방식은 반대입니다. MC같은 경우, 한 에피소드가 끝날 때까지 계속 샘플링을 해야합니다. 이로인해, random성이 많이 증가하게 되죠. 반면에, TD같은 경우 업데이트를 위해 (s, a, r, s’)을 한번만 샘플링 하기 때문에 MC에 비해 random성이 작습니다. 이러한 특징으로 인해, MC는 high variance를, TD는 low variance를 갖습니다.

• Return depends on many random actions, transitions, rewards
• TD target depends on one random action, transition, reward

Properties of MC and TD

위의 bias-variance trade-off 성질로 인해 MC와 TD는 아래와 같은 특성을 같습니다.

MC : high variance and zero bias
MC는 zero bias이기 때문에 초기값에 상관없이 항상 수렴하게 됩니다. 이러한 수렴을 잘하는 특징 덕분에 좋은 근사 가치 함수도 갖게 됩니다(value function approximation, 추후에 포스팅 예정). 그러나, high variance인해 항상 true expected value에 수렴함에 불구하고, 언제 수렴할지는 불분명합니다. 왜냐하면, high variance로 인해 수렴할 때까지 굉장히 많은 에피소드 샘플링이 필요하기 때문입니다. 그리고 한 에피소드가 끝날 때까지 기다려야 하는데, 에피소드의 길이가 긴 경우 더욱 적용하기 어렵습니다. 따라서 실용성 측면에서 떨어지는 단점이 있습니다.

MC가 zero bias를 가질 수 있는 이유는 $G_t$ 가 i.i.d성질을 가지기 때문이라고 설명하였습니다. 이는 $V(S_t)$ 를 계산하는데 $S_t$ 의 markov property를 이용하지 않음을 뜻합니다. 따라서, Markov domain인 아닌 경우 MC를 적용하여 문제를 해결할 수 있습니다(handling non-markovian domains).

TD : low variance and high bias
반면에 TD는 low variance로 인해 수렴이 가능하다면, MC에 비해 수렴지점까지 빨리 도달할 수 있습니다(그림 11,12 참고). 하지만 초기값에 따라 수렴여부가 달라지고(sensitive to initial value), 그리고 근사 가치 함수를 찾지 못할 수도 있습니다. 하지만, on-line 학습이 가능하기 때문에, 따라서 쉽게 적용할 수 있습니다.

TD는 $V(S_t)$ 를 계산하기 위해서 $V(S_{t+1})$ estimate 을 이용합니다(bootstrap). 이는 MC와는 다르게 markov property를 이용합니다. 따라서, TD는 Markovian domain에서 적용가능합니다.

위에서 설명한 MC와 TD의 특성을 정리하면 아래와 같습니다.

위 표에서 마지막 특성에 관하여 MC, TD와 DP 사이의 관계를 back-up diagram과 함께 잘 나타낸 그림이 있습니다.

DP같은 경우, 환경 모델을 잘 알기 때문에 다음 스텝에 대해 full backup을 그린 관계와 같습니다. 그러나 에피소드가 끝날 때까지 backup을 그릴 필요가 없기 때문에 shallow-backup이고, bootstrap을 이용합니다. 반면에, TD같은 경우, 다음 상태에 대해 한 상태에 대해서만 샘플링을 하기 때문에 sample-backup이며, DP와 마찬가지로 한 스텝만 내다보기 때문에 shallow-backup이며 bootstrap을 이용합니다. 마지막으로 MC같은 경우, 모든 에피소드가 끝날 때까지 기다려야 하기 때문에 deep-backup이고, 샘플링을 하여 경험을 쌓기 때문에 sample-backup입니다. 그러나 bootstrap을 이용하지 않습니다.

TD가 MC보다 수렴이 더 빠른 것에 대해 수학적으로 증명된 적은 없습니다. 그러나, 실험적으로 확인했을 때 TD가 MC보다 수렴이 빠릅니다. 이에 관해 Sutton과 berto교재에 MC와 TD의 수렴에 관한 예제가 있습니다.

위의 예는 C에서 시작하여 각 스텝마다 왼쪽 또는 오른쪽으로 0.5의 확률로 동일하게 갈 수 있다고 할 때, 양 끝의 사각형에 도달하면 에피소드가 끝나는 문제입니다. 각 상태 A, B, C, D, E에서 value를 MC와 TD를 이용하여 구한 결과는 아래와 같습니다. 이때, 각 상태에서의 true value는 1/6, 2/3, 3/6, 4/6, 5/6입니다.

왼쪽 그림은 TD(0)를 여러 에피소드를 거쳤을 때, 각 상태에서의 value입니다. 100 에피소드 정도 진행했을 때, true value에 수렴하는 것을 확인할 수 있습니다. 오른쪽 그림은 step size $\alpha$ 를 달리했을 때 각각 MC와 TD에서의 RMS error 입니다. 실험적으로 TD가 MC보다 더 빨리 수렴합니다.

differences between MC and TD trough Batch Update
MC와 TD의 작동원리를 보여주는 사례를 하나 더 소개하겠습니다. 먼저 그전에 batch update에 대해 설명하도록 하겠습니다. k개의 에피소드 또는 k개의 스텝을 미리 샘플링 해 놓은 뒤, k개의 MC 또는 TD 방식의 error를 각각 구해서 다 합한 후, 한 번 update를 하는 방식을 batch update이라 합니다. 아래 예를 각각 MC와 TD 방식의 batch update로 풀어보겠습니다.

아래와 같이 8개의 에피소드가 있습니다. 첫번째 에피소드는 A에서 시작해서 reward를 0을 받고, 그 다음 B로 가고 reward를 0을 받고 끝납니다. 그 다음 여섯개 에피소드는 B에서 시작해서 reward를 1을 받고 끝납니다. 마지막 하나는 B에서 시작해서 reward를 1을 받고 끝납니다. 이때, MC와 TD방식으로 V(A), V(B)가 각각 어떻게 될까요 ?

MC방식으로 한다면, $V(A)=0, V(B)=\frac{3}{4}$ 입니다. 그러나 TD방식으로 한다면 $V(B)=0$ 이지만 $V(A)=\frac{3}{4}$ 입니다. $V(A)$ 에서 차이가 나는 이유는 MC는 mean squared error를 최소화하는 방식으로 해답을 구하지만, TD는 markov model의 likelihood를 최대화하는 방식으로 해답을 구하기 때문입니다.

[\sum_{k=1}^{K}\sum_{t=1}^{T_k}\left(G_t^k - V(s_t^k)\right)^2]

• MC converges to solution with minimum mean-squared error
• Best fit to the observed returns

MC는 관측된 return이 true value estimate과의 차이가 최소화시키는 방향으로 갑니다. 반면에, TD는 markov property 성질을 이용하기 때문에 MDP를 해결하는 방향으로 갑니다. 실제 구현은 아니지만 내재적으로는 마치 환경모델의 transition model과 reward model의 maximum likelihood를 구한 뒤 DP를 푸는 방식과 유사하게 작동하는 것입니다. 실제로 위의 예제를 아래 방식으로 환경 모델을 구한 뒤 DP로 접근하면 똑같은 해답을 구할 수 있습니다.

[\hat P^a_{s,s’} = \frac{1}{N(s,a)}\sum_{k=1}{K}\sum_{t=1}{T_k}\mathbf 1(s_t^k, a_t^k, s_{t+1}^k = s, a, s’)]

[\hat R^a_s = \frac{1}{N(s,a)}\sum_{k=1}{K}\sum_{t=1}{T_k}\mathbf 1(s_t^k, a_t^k=s,a)r^k_t]

• TD(0) converges to solution of max likelihood Markov model
• Solution to the MDP $<S, A, \hat P, \hat R, \gamma >$ that best fits the data

이상으로 이번 포스팅을 마치겠습니다. 다음 포스팅은 Model-Free Control에 대해 진행하겠습니다.

지난 MDP 포스팅에 이어서, 이번 포스팅은 MDP를 iterative하게 푸는 방법 중 하나인 Dynamic Programming(DP)에 대해서 다룹니다. CS234 2강, Deep Mind의 David Silver 강화학습 강의 3강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 4 기반으로 작성하였습니다. 또한, 대부분 수식 표기법은 Sutton 교재를 따랐습니다.

일반적으로 Dynamic Programming란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 지난 시간에서 벨만 방정식(벨만 기대 방정식, 벨만 최적 방정식)은 recursive한 관계를 가지고 있기 때문에, 벨만 방정식을 풀기 위한 솔루션으로 DP 사용이 적합하다고 할 수 있습니다.

따라서, 상태 $s \in S$, 행동 $a \in A$, 보상 $r \in R$ 인 환경 모델 $p(s’,s|r,a)$ 을 아는 상황에서, 벨만 기대 방정식과 벨만 최적 방정식의 recursive한 성질을 이용하여 최적 가치 함수 $v_\ast, q_\ast$ 를 구하는 것이 Dynamic Programming을 이용한 MDP 를 푸는 것입니다.

MDP문제는 환경모델을 완벽하게 아는 상황이기 때문에, dynamic programming은 'reinforcement learning'이 아니라 'planning' 방법입니다.

DP설명은 finite MDP에 유한하여 설명하도록 하겠습니다. 일반적으로 continuous MDP문제는 DP방법이 아닌 다른 방법을 이용하여 풀기 때문입니다.

지난 강화학습 소개[2] 포스팅에서, sequential decision making 문제 종류로 evaluation(prediction)과 control을 소개하였습니다. evaluation은 일정 정책 아래, 기대보상을 추정하여 현재 따르는 정책의 좋고/나쁨을 평가하는 것입니다. 즉, 현재 정책의 평가가 되는 것입니다. control은 정책들의 평가를 기반으로 최적의 정책을 찾는 것입니다. evaluation과 control은 독립적인 과정이 아니라 서로 연계되어 있는 과정이라 하였습니다. 마찬가지로 Dynamic Programing도 evaluation에 해당하는 Policy Evaluation과 control에 해당하는 Policy Improvement로 구성됩니다. 각각에 대해 알아봅시다.

DP설명은 finite MDP에 유한하여 설명하도록 하겠습니다. 일반적으로 continuous MDP문제는 DP방법이 아닌 다른 방법을 이용하여 풀기 때문입니다.

Policy Evaluation

Policy evaluation은 벨만 기대 방정식을 이용하여 iterative한 방법으로 현 정책 아래의 가치함수를 구하는 과정입니다. 아래 벨만 기대 방정식을

update rule의 관계를 가진 방정식으로 취급한 뒤,

k=0부터 수렴할 때까지 반복적으로 계산하는 것입니다. 즉 가치 함수를 초기화한 후, $v_0 \to v_1 \to v_2 \to \cdots \to v_\pi$ 으로 수렴할 때까지 모든 상태에 대해서 동시에 업데이트하는 것입니다.

이를 back-up diagram으로 다시 표현해 봅시다.

그림 4.를 보시면, k 스텝에서 다음 상태를 이용하여 k+1 스텝의 현재 상태를 업데이트합니다. 또한 업데이트되는 방식은 다음 상태에서 나올 수 있는 누적보상의 가중 평균으로 계산됩니다(벨만 기대 방정식이기 때문입니다).

To produce each successive approximation, $v_{k+1}$ from $v_{k}$, iterative policy evaluation applies the same operation to each state s: it replaces the old value of s with a new value obtained form the old values of the successor states of s and the expected immediate rewards, along all the one-step transitions possible under the policy being evaluated. - Sutton and Barto, Reinforcement Learning : An Introduction

아래 그리드월드 예제로, policy evaluation을 살펴봅시다.

처음 시작 상태에서 여러 경로를 다니다가 회색색깔에 도착하면 끝나는 게임이 있다고 합시다. 각 상태마다 받는 보상은 -1이고, 행동 좌,우,위,아래 방향에 대해 갈 확률은 0.25라 한다면, k=0, k=1, k= $\infty$ 을 수렴할 때까지 반복하면 각 $v_k$ 에 대해 각 상태의 가치함수 값은 아래 그림과 같습니다.

왼쪽 행은 가치함수 결과이고, 오른쪽 행은 각 가치함수에서 greedy한 전략을 보여줍니다. 그러나 위 예제같은 경우는 간단한 케이스이어서 빨리 수렴에 도달합니다. 일반적으로 상태 집합의 크기 $|S|$ 가 큰 경우, 수렴할 때까지의 속도가 매우 느릴 수도 있기 때문에, 아래 알고리즘과 같이 어느 정도 수렴조건을 만족하면 다음 스텝으로 넘어가는 방법을 주로 택합니다.

Policy Improvement

결국 현재 정책을 평가하는 이유는 더 나은 정책을 찾기 위한 것입니다. 그렇다면 현재 정책 평가한 것을 기반으로 어떻게 더 나은 정책을 찾는지 알아보도록 하겠습니다.

임의의 정책 $\pi$ 아래 policy evaluation을 통해 $v_\pi$ 를 구했다고 하겠습니다. 그림 6.에서 처럼 수렴된 $v_\pi$ 에 대한 greedy policy가 있을 것입니다. 하지만 그 greedy policy 이외의 다른 행동 $a$ 을 선택하고, 즉, $a \neg \pi(s)$ 하고, 기존 정책 $\pi$ 를 따른다고 했을 때,

기존 정책에 따른 $v_\pi(s)$ 보다 크다면 새로 선택된 행동 a가 발전된 전략일 것입니다(policy improvement).

[q_\pi(s, \pi’(s)) \geq v_\pi(s)]

처음에, 이 부분을 혼자 공부할 때, 이해하기 어려웠던 부분이 ‘greedy policy 이외의 다른 행동 $a$ 를 선택하고 기존 정책을 따른다는 부분’이었습니다. 저는 이 부분은 아래와 같이 이해하였습니다.

그러나, 지난 MDP 포스팅에서 더 나은 정책이 되려면 $q_\pi(s, \pi’(s)) \geq v_\pi(s)$ 가 아닌 $v_{\pi}(s) \geq v_{\pi’}(s)$ 를 만족해야 합니다. 이를 유도하는 수학적 증명은 아래와 같습니다.

따라서, greedy하게 policy improvement하는 방식을 수식으로 깔끔하게 정리하면

입니다. 즉 기존 정책에서 발전된 새로운 정책 $\pi’$ 가 되었습니다.

만약에, 새로운 정책 $\pi’$ 가 기존 정책 $\pi$ 에서 더이상의 발전이 없다면, $v_\pi=v_\pi’$ 이를 만족하기 때문에, 아래 식이 성립됩니다.

위의 식을 가만보면, 어디서 많이 봤습니다. 바로 벨만 최적 방정식입니다. 즉, 더이상 발전이 없을 때, $v_\pi’$ 는 최적정책임을 의미합니다.

Policy Iteration

최적 정책을 찾기 위해서 결국 evaluation과 imporvement과정을 번갈아 가면서 정책이 더 이상 발전이 없을 때까지 진행해야 합니다. 이를 policy iteration이라 합니다.

[\pi_0 \overset E\to v_{\pi_0} \overset I\to \pi_1 \overset E\to v_{\pi_1} \overset I\to \pi_2 \overset E\to \cdots \overset I\to \pi_\ast \overset E\to v_\ast]

E는 evalution이고, I는 improvement를 뜻합니다. Finite MDP인 경우 정책 후보의 갯수도 유한하기 때문에 반드시 언젠간 수렴합니다. Policy iteration 알고리즘은 아래 그림과 같습니다.

그림 9.를 보면, policy improvement를 한 후, 다시 policy evalutation을 할 때, 이전 정책 $/pi$ 에 관한 $v_\pi$ 로 초기값으로 하여 진행합니다.

Value Iteration

최적 정책을 찾는 방법엔 policy iteration 말고 value iteration도 있습니다. Value iteration에 대해 설명하기 전에 먼저 벨만 최적 방정식에서의 optimality의 개념을 다시 한번 생각해 봅시다.

Principle of Optimality

벨만 최적 방정식을 다시 한번 살펴보면,

상태 s에서 optimal value를 가지려면, 다음 상태 s’까지 진행해봐야 상태 s의 가치가 최적인지 아닌지 판단할 수 있습니다. 아래와 같이 $s_t$ 가 terminal state인 시퀀스가 있다고 한다면,

[s_0 \to s_1 \to s_2 \to \cdots \to s_t]

상태 $s_0$ 의 가치는 $s_1$ 에 도착해야 알고, $s_1$ 의 가치는 $s_2$ 에 도착해야 알고, …, $s_{t-1}$ 의 가치는 $s_t$ 에 도착해야 압니다. 즉 $s_t$ 의 최적가치를 알고 있어야 처음 상태 $s_0$ 의 최적가치값을 알 수 있단 얘기입니다. 아래 예를 살펴보겠습니다.

회색인 부분이 도달해야 하는 골이라 하면, 골까지 가는 가장 짧은 경로를 찾는 문제입니다. 흰색 칸을 밟을 때마다 받는 보상은 -1, 회색 칸을 밟으면 보상 0을 받는다고 할 때, 처음 상태가 정해진 것이 아니라면 당연히 회색 부분 근처 칸에서 시작하는게 최적일 것입니다. 그리고 회색 칸은 종결지점이기 때문에 회색 칸 이후로 더이상의 시퀀스가 존재하지 않아, 회색 칸의 최적가치는 즉각적인 보상인 0일 것입니다. 그렇다면 골에서 가장 멀리 있는 맨 오른쪽 칸의 최적 가치는 어떻게 구할까요? 골의 최적가치가 골에서 가까운 위치부터 퍼져나가 맨 오른쪽 칸의 최적 가치를 계산할 수 있도록 도달해야 합니다.

그러나, DP에서 모든 상태에 대한 업데이트를 동시에 진행하기 때문에, 골의 최적가치가 퍼져나가 다른 상태의 최적가치를 구할 수 있을 때까지 여러 번 반복 진행해야 합니다. 이것이 바로 “Value Iteration”입니다.

Value iteration을 수식으로 표현하면 아래와 같습니다.

위 수식을 보시면, 벨만 최적 방정식과 유사합니다. 즉, value iteration은 벨만 최적 방정식을 업데이트 형식으로 바뀐 것입니다.

policy evalutation은 벨만 기대 방정식을 업데이트 형식으로 바꾼 것이고, value iteration은 벨만 최적 방정식을 업데이트 형식으로 바뀐 것입니다.

value iteration은 policy iteration 처럼 명시적인 정책 발전 과정을 중간에 생략하고, 최적 가치 함수를 바로 계산하여 마지막에 정책 발전을 한번만 수행하여 최적 정책을 얻는 과정이라 생각할 수 있습니다.

이상으로 이번 포스팅을 마치겠습니다. 읽어주셔서 감사합니다.

1. CS234 Winter 2019 course Lecture 2
2. Richard S. Sutton and Andre G. Barto : Reinforcement Learning : An Introduction
3. David Silver Lecture 3
4. 위키백과, 동적계획법

이전 포스팅 강화학습 소개[1], 강화학습 소개[2]에 이어서, MDP에 대해 다룹니다. CS234 2강, Deep Mind의 David Silver 강화학습 강의 2강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 3 기반으로 작성하였습니다.

강화학습은 sequential decision process 문제를 푸는 방법입니다. 그렇다면 sequential decision process를 풀기 위해서 수학적으로 표현해야 하는데 이것이 바로 Markov Decision Process(MDP)입니다. 또한 MDP는 에이전트 상태가 마코브 성질을 따르는 경우이기 때문에, 환경모델을 완벽하게 아는 Fully Observability를 가집니다.

MDPs are a mathematically idealized form of the reinforecement learning problem for which precise theoretical statements can be made. - Sutton and Barto, Reinforcement Learning: An Introduction

지난 포스팅에서 대부분의 문제들은 그러나 Partial Observability를 가지는 POMDP라 하였습니다. 그러나, POMDP를 풀기 위해서도 MDP가 중요합니다. 그 이유는 POMDP는 MDP의 상태를 히스토리로 두고 풀 수 있기 때문입니다.

MDP를 자세히 이해하기 위해서 Markov process(Markov Chain)와 Markov Reward Process를 먼저 살펴본 뒤, MDP를 살펴보도록 하겠습니다.

Markov Process

Markov Process(Markov chain)은 마코브 성질을 가지는 랜덤 상태 $S_1, S_2, \dots$ 들의 시퀀스입니다. Finite Markov Process인 경우 상태들의 집합은 유한개로 구성됩니다.

상태들간의 변환 확률 행렬(state transition matrix)은 현재 상태에서 다른 상태로 갈 확률을 모든 상태에 대해 행렬 형태로 나타낸 것입니다. 현재 상태 s에서 다음 상태 s’로 갈 확률은

입니다. 따라서, 상태 변환 확률 행렬 $\mathit P$ 는 아래와 같습니다. 각 행의 합은 1이 됩니다.

[\mathit P = \left( \begin{matrix} \mathit P_{11} & \cdots & \mathit P_{1n}
\vdots & \ddots & \vdots
\mathit P_{n1} & \cdots & \mathit P_{nn}
\end{matrix} \right)]

Markov Process 예를 들어봅시다. 아래 예는 학생들의 수업을 듣는 패턴을 Markov Process로 나타낸 것입니다. 동그라미는 학생들의 상태(facebook, class1, …)이며, 화살표는 각 상태에서 다른 상태로 넘어갈 확률을 나타냅니다.

그림 2.를 보면, 시작하는 상태가 같아도 밟고 지나가는 상태들의 경우가 모두 다를 수 있습니다. 예를 들어서, Class1에서 시작하여도

• C1 C2 C3 Pass Sleep
• C1 fb fb C1 C2 Sleep
• C1 C2 C3 Pub C2 C3 Pass Sleep

이처럼, 실제로 이렇게 샘플된 시퀀스를 에피소드(episode)라 부릅니다.

Markov Reward Process

다음으로는 Markov Reward Process(MRP)를 살펴봅시다. MRP는 Markov chain에 reward가 더해진 것입니다. 임의의 상태들의 시퀀스를 상태 변환 확률에 따라 밟아가면서 각 상태에 도착할 때마다 보상을 얼마나 받는지도 시퀀스로서 파악하는 것입니다.

$R_s$ 는 보상함수로, 상태 $S_s$ 일 때, 받을 수 있는 즉각적인 보상에 대한 기댓값이다. 여기서 중요한 점은 앞으로 받을 보상들을 고려한 누적 보상값이 아닌 즉각적으로 받는 보상(immediate reward)입니다.

지난 포스팅에서 환경모델은 크게 상태변이모델과 보상모델로 구성된다고 했습니다. 따라서, 상태변이확률과 보상함수를 결합하여 환경 모델을 아래와 같이 표현할 수도 있습니다. 이는 현재 상태 t-1 스텝에서, 다음 스텝에 받을 보상과 상태가 r과 s’이 될 확률입니다.

아래는 학생 Markov Reward Process 예시입니다. 빨간색으로 표시된 숫자가 각 상태에서 받는 즉각적인 보상입니다.

return and value function

MRP에서 Reward는 즉각적인 보상입니다. 그러나 우리가 궁극적으로 하고 싶은 건 매 스텝마다 받는 보상을 누적했을 때, 이 누적값이 최대화가 되도록 하는 것입니다(reward hypothesis - 지난 포스팅 참조.) 따라서, 누적된 보상은 어떻게 구할까요 ? 이를 위해 필요한 개념이 return과 value function입니다.

Return and Horizon
먼저, horizon에 대한 개념을 살펴봅시다. horizon은 에피소드에서의 t 스텝 갯수입니다. 유한 개일수도 무한 개일수도 있습니다. 유한개일 경우 finite MRP(또는 finite MDP)라 합니다.

Return은 t 스텝에서부터 horizon까지 디스카운트된 누적 보상(discounted sum of rewards)의 합입니다.

discount factor $\gamma \in [0,1]$ 은 미래 보상을 현재 가치로 환산해주는 요소입니다. 왜 현재 가치로 환산해야 할까요? 여러가지 이유가 있습니다. 먼저 수학적으로 계산 시 수렴해야 하기 때문입니다. 그렇지 않으면 반환값이나 앞으로 설명할 가치함수가 전혀 수렴되지 않기 때문이죠. 다른 이유로는 미래에 대한 불확실성 때문입니다. 금융에서 이자를 떠올리시면 됩니다. discount factor가 1에 가까울수록 미래보상을 더 중요한거고 0에 가까울수록 현재보상이 더 중요한 것입니다.

만약에 종결 상태가 있는 경우, 즉 horizon이 유한한 경우, $\gamma=1$ 로 둘 수 있습니다.

아래 그림은 student MRP에서, 각 episode마다 return을 계산한 것입니다.

Value Function
가치함수는 현재 놓여진 상태가 얼마나 좋은지를 알려주는 함수입니다. ‘얼마나 좋은지’에 대한 개념은 결국 현재 상태에서 앞으로 시퀀스를 밟아나갈 때 받을 누적보상이 얼마나 클까?와 관련됩니다. 따라서 가치 함수의 정의는 return의 기댓값입니다. MRP에서는 현재 에이전트의 행동에 관한 요소가 없기 때문에, 상태 가치 함수이지만, 추후에 MDP는 행동요소가 포함되어 있기 때문에 MDP에서의 가치함수는 상태-행동 가치 함수입니다.

상태 가치 함수는 어떻게 계산할 수 있을까요? 가장 간단하게는 에피소드를 엄청나게 많이 샘플링하는 것입니다. 그 다음 각 에피소드마다 return을 계산하고, 그 return값들을 평균내면 됩니다. 이를 simulation 이라 합니다. 그러나 마코브 성질을 이용하면 가치함수는 recursive한 형태로 변하게 됩니다. 이것이 바로 bellman equation입니다.

Bellman Equation for MRPs

가치함수는 위 그림처럼 현 상태에서의 즉각적인 보상 $R_{t+1}$ 와 다음 상태에서 받을 누적 보상 $\gamma v(S_{t+1})$ 로 분해되며 recursive한 구조를 가집니다. 이는 현재 상태 가치와 다음 상태 가치사이의 관계를 나타냅니다. 이 방정식이 바로 벨만 방정식(Bellman Equation)입니다.

벨만 방정식은 현재 상태와 다음 상태 사이의 관계를 나타내기 때문에 아래와 같이 back-up diagram으로 많이 표현합니다.

finite MDP인 경우, 아래 그림과 같이 행렬방정식으로 표현됩니다. 벨만 방정식이 선형방정식으로, 아래와 같이 직접적으로 풀 수 있으나 계산 복잡도가 높습니다.

상태, 행동집합의 크기가 작은 경우엔 행렬방정식으로 풀 수 있지만 크기가 큰 경우에는 불가능합니다. 따라서 이런 경우엔 iterative한 방법으로 방정식을 풀 수 있습니다. iterative 방법들에 대해선 추후에 다루도록 하겠습니다.

• dynamic programming
• monte-carlo evaluation
• temporal difference learning

이제까지 MRP를 정의하였고 MRP를 정의내리기 위해 필요한 return, 가치함수, 가치함수로 유도되는 벨만방정식도 살펴보았습니다. 이제 Markov Decision Process를 살필 준비가 되었습니다.

Markov Decision Process

Markov Decision Process(MDP)는 MRP에 행동(actions)이 더해진 것입니다. 즉, 명시적인 의사결정이 등장합니다.

위에서 언급했듯이, 환경모델은 상태변이모델과 보상모델로 이뤄졌기 때문에, MRP에서 이를 하나로 나타낼 수 있었습니다. 마찬가지로, MDP에서 환경모델은 행동(action)까지 고려한 통합된 환경모델은 아래와 같습니다.

Policies

MDP에서 좋은 의사결정을 하기 위해, 에이전트 내부에 행동 전략을 가지고 있어야 합니다. 이를 policy라 합니다. 정책의 정의는 아래 식처럼,

현재 상태 $S_t=s$ 에서, 모든 행동들에 대한 확률 분포입니다. 상태는 마코브 성질을 가지므로, 현재 상태만으로도 의사결정 시 충분한 근거가 될 수 있습니다. 따라서, 현재상태만 조건으로 가진 조건부 확률분포가 되는 것입니다. 또한, MDP의 policy는 시간에 따라 변하지 않습니다(stationary). 이 말은 시간이 지남에 따라 에이전트가 동일한 상태를 여러번 지나간다 해도 그 상태에 있을 때의 행동전략은 변하지 않는다는 뜻입니다.

MDP와 명시적인 policy가 있다면, 이는 MRP문제와 동일합니다. MDP의 보상함수는

는 policy와 가중평균으로 MRP의 보상함수로 바뀝니다. 마찬가지로, MDP의 상태변이함수도

policy와의 가중평균으로 MRP의 상태변이함수가 됩니다. 이 두식의 변환은 결국 MDP에서의 벨만방정식을 풀 때, MRP에서 사용한 방법(simulation, analytic solution, iterative method)을 동일하게 사용해도 되는 것을 뜻합니다.

Value Function and Bellman Expectation Equation

MDP아래에서 Value Function을 다시 살펴봅시다. 기존에 상태만은 고려한 state value function이 있고, 이젠 행동까지 고려한 state-action value function이 있습니다.

State value function을 현 상태와 다음 상태사이의 관계로 분해한 것처럼, state-action value function도 동일한 방식으로 분해할 수 있습니다. 이렇게 분해된 식은 Bellman expectation equation 또는 bellman equation이라 합니다.

$v_{\pi}$, $q_{\pi}$ 의미는 정책 $\pi$ 에 따라 행동했을 때의 가치함수를 의미합니다.

MRP에서, 벨만 방정식을 back-up diagram으로 나타낸 것처럼 $v_{\pi}$, $q_{\pi}$ 도 back-up diagram으로 표현가능합니다.

총 4종류의 back-up diagram이 나오며, 이는 4종류의 bellman equation을 뜻합니다.

Bellman Optimal Equation

이제까지 알아본 가치함수(또는 벨만 기대 방정식)는 일정 정책 아래에서의 가치를 구한 것이기 때문에, 정책의 가치라고도 생각할 수 있습니다. 그러나 강화학습의 목표는 reward hypothesis에 따라, 누적보상이 최대가 되는 “최적 정책”을 찾는 것입니다. 그럼 최적 정책은 어떻게 찾을까요? 여러 정책들 간의 비교를 통해서 찾을 수 있습니다. 이와 관련된 개념이 ‘partial ordering’입니다.

partial ordering
여러 정책들 간 비교가 가능하다는 건 ‘이 정책이 다른 정책보다 낫다’가 수학적으로 비교가 가능하다는 것입니다. 따라서 이 수학적 비교의 척도가 되는 것이 가치함수간의 비교입니다. 정책 $\pi$ 가 다른 정책 $\pi’$ 보다 나을려면, 각 정책 아래 가치함수를 구했을 때 모든 상태에 대해서 $v_{\pi}(s) \geq v_{\pi’}(s)$ 입니다.

[\pi \geq \pi’, if\,\,and\,\,only\,\,if\,\,v_{\pi}(s) \geq v_{\pi’}(s), for \,\,all\,\,\,s \in S]

즉, 최소한 하나의 정책이 다른 정책보다 같거나 나은 정책이 존재한다는 것입니다. 이것이 바로 최적 정책(optimal policy) $\pi_\ast$ 이고 이때 가치 함수를 최적 가치 함수(optimal value function) $v_\ast(s)$ 라 합니다. 가치함수의 종류에는 상태-가치 함수와 상태-행동 가치 함수가 있습니다. 최적 상태-가치 함수(optimal state-value function) $v_*(s)$ 는

[v_*(s) = \underset{\pi}max\,v_{\pi}(s)]

이고, 최적 상태-행동 가치함수(optimal state-action value function) $q_*(s,a)$ 는

[q_*(s,a) = \underset{\pi}max\,q_{\pi}(s,a)]

입니다. MDP에서 최적 가치 함수를 찾았다면, 이는 결국 일련의 최고의 결정을 수행할 수 있는 것을 뜻하고, sequntial decision making 문제를 “해결”한 것입니다.

Bellman Optimality Equations
상태 가치 함수와 상태-행동 가치 함수를 back-up diagram을 이용하여 4종류의 bellman expectation equation을 세울 수 있었습니다. 마찬가지로, 최적 상태 가치 함수와 최적 상태-행동 가치 함수를 같은 방식으로 4종류의 bellman optimality equation을 세울 수 있습니다.

벨만 기대 방정식과 벨만 최적 방정식은 현 상태와 이전 상태 사이에서의 recursive한 관계를 가진다는 것이 특징입니다. MDP문제를 푸는 방법(벨만 방정식을 푸는 방법)중 하나인 Dynamic Progamming은 바로 이 recursive한 관계를 이용하여 iterative하게 해답을 찾아나가는 과정입니다. DP는 추후 포스팅에서 다루도록 하겠습니다.

Finding an Optimality and Solving the Bellman Optimality Equation
이제까지 최적정책의 정의와 최적정책을 찾기 위한 최적 가치 함수에 대해서 알아봤습니다. 그런데 아직 해결이 안된 부분이 있습니다. 바로, 최적 가치 함수를 이용하여 어떻게 최적 정책을 찾을까?에 관한 물음과 상태의 갯수가 많은 상황에서, 즉 복잡도가 높은 MDP문제에서 방정식을 어떻게 풀까?에 관한 물음입니다. 먼저 전자부터 살펴보겠습니다.

벨만 최적 방정식을 풀어서 $v_\ast$ 를 구했다면, 정책을 구하는 건 어렵지 않습니다. 그림 13.에서 1번, 3번 최적방정식에서,

[\pi_\ast(s) = arg \underset a max(q_\ast(s,a))]

$q_\ast(s,a)$ 가 최대가 되는 행동 a 가 바로 상태 s에 대한 최적 정책입니다. Recursive한 관계에서 살펴보면,

[\pi_\ast(s) = arg \underset a max(R^a_s + \gamma\sum_{s’}P^a_{ss’}v_\ast(s’))]

와 같습니다. 즉, 최적 정책을 찾을 땐 greedy하게 찾습니다. greedy한 이유는 정책의 행동을 선택할 때, 앞으로의 모든 상황을 고려하는 것이 아니라 다음 상태의 상황만을 고려하기 때문입니다. 그러나 greedy하게 선택해도 될까요 ? 정답은 yes 입니다. 왜냐하면 이미 가치함수를 구하는 과정에서 미래 상황까지 고려한 가치를 구했기 때문에 이것을 기반으로 한 greedy 선택 안에는 이미 long-term sequence를 고려한 것입니다.

마지막으로, 방정식을 푸는 방법에 대한 물음입니다. 이미 이전에 벨만 기대 방정식을 푸는 방법에 대해서 살펴보았습니다. 벨만 기대 방정식은 linear equation이기 때문에, 복잡도가 높지 않은 MDP 문제에서 analytic하게 구할 수 있습니다. 그러나 복잡도가 높은 MDP문제는 불가능하므로, iterative method인 dynammic progamming, monte-carlo evalution, Temporal difference가 있다고 하였습니다. 반면에, 벨만 최적 방정식은 non-linear equation이기 때문에 analytic하게 풀 수는 없습니다. 따라서 위에서 언급한 iterative method를 적용해야 합니다.

이상으로 MDP 포스팅을 마치겠습니다. 다음 포스팅은 Dynamic Progamming에 대해 진행하겠습니다.

1. CS234 Winter 2019 course Lecture 2
2. Richard S. Sutton and Andre G. Barto : Reinforcement Learning : An Introduction
3. David Silver Lecture 2

이번 포스팅은 강화학습 소개[1]에 이어서 진행합니다. CS234 1강, Deep Mind의 David Silver 강화학습 강의 1강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 1 기반으로 작성하였습니다.

지난 포스팅에서, 강화학습의 특성과 강화학습 문제를 정의하기 위해 필요한 요소, 강화학습 문제의 종류에 대해서 알아봤습니다. 에이전트는 에이전트의 상태를 가지고 어떻게 좋은 행동을 선택할 수 있을까요 ? 이 문제에 대한 답을 하기 전에, 에이전트가 상태 이외에 어떠한 요소를 가지고 있어야 하는지 알아봅시다.

Major Components of an RL Agent

강화학습 에이전트를 구성하는 요소는 크게 정책(policy), 가치 함수(value function), 모델(Model)입니다.

Policy
정책은 에이전트의 행동전략(agent’s behavior)입니다. 정책은 일종의 함수로, 주체의 상태를 행동으로 맵핑합니다. 정책의 종류는 deterministic policy $a = \pi(s)$ 와 stochastic policy와 $\pi(a|s) = P [A_t=a|S_t=s]$ 가 있습니다.

A policy is a map from state to action

아래와 같이 화성탐사기 예를 들어봅시다.

위의 그림과 같이, 화성탐사기가 도달할 수 있는 상태는 총 7가지 상태이고, 각 상태에서 취할 수 있는 행동은 왼쪽/오른쪽 두가지입니다. s1 상태에서 +1 보상을, s7 상태에서 +10 보상을, 나머지 상태에서 0의 보상을 받습니다.

위 예는 화성 탐사가 가질 수 있는 정책 중 하나입니다(사실 이 예제는 너무 단순해서 이 정책이 최적 정책이긴 합니다). s7상태에서 가장 큰 보상을 받기 때문에 어떤 상태에서 시작하던 간에 오른쪽으로 가는 것이 최고의 정책이죠. 또한 이 정책의 특성은 deterministic입니다. 그 이유는 각 상태에서 나올 수 있는 모든 행동들의 가능성을 보여주는 것이 아니라, 한가지 행동만을 출력하기 때문입니다.

Value Function
다음은 가치 함수입니다. 가치 함수는 특정 정책 아래, 현재 에이전트 상태에서 앞으로 받을 미래 보상까지 고려한 누적보상 예측값입니다. 에이전트는 이 가치값을 기반으로 현 상태의 좋고 나쁨을 판단합니다. 또한 정책 간 가치함수를 비교를 통한 행동 선택의 기반이 되기도 합니다.

$\gamma$ 는 discount factor로, 현재 보상과 미래 보상간의 중요도 차이를 보여줍니다. 추후에 더 자세히 설명하도록 하겠습니다. 아래는 가치함수의 예입니다.

화성 탐사 문제를 그림 1. 처럼 정의했을 때, 각 상태에서 가질 수 있는 화성 탐사 에이전트의 가치함수입니다.

Model
모델이란 환경(정확히, 주체가 영향을 받고 있는 환경)이 주체의 행동에 따라 어떻게 변하는지에 관한 모델입니다. 즉 환경의 동적모델(dynamic models of the environment)이죠.

• A model predicts what the environment will do next
• $P$ predicts the next state
• $R$ predicts the next immediate reward

환경의 모델은 크게 두 가지가 있습니다. 변이모델(transition/dynamics model)과 보상입니다. 변이모델은 에이전트의 행동에 따라 다음 상태에 대한 정보를 알려줍니다. 보상모델은 에이전트가 선택한 행동에 대해 변이모델에 따라 다음 상태에 갔을 때 받는 즉각적인 보상입니다. 아래는 모델에 관한 화성탐사 예시입니다.

Categorizing RL Agents

에이전트를 구성하는 요소로는 모델, 가치함수, 정책임을 알았습니다. 그러나 사실 구성요소를 어떻게 조합하느냐에 따라 강화학습 에이전트의 종류를 몇가지로 나눌 수 있습니다.

• Value Based
에이전트가 행동을 선택할 때, 가치함수의 결과값이 가장 높은 쪽으로 선택하는 것입니다. 이때, 정책이 명시적으로 표현되지 않고 내재적으로 표현됩니다.
• Policy Based
명시적인 정책을 가진 에이전트입니다. 즉, 특성 상태에서 어떤 행동이 확률적으로 높은지를 보고 행동하는 것입니다.
• Actor-Critic
위 Value-based와 policy based가 합쳐진 상태입니다.
• Model Free
변이확률과 보상함수에 대한 정보가 없는 경우입니다. 에이전트는 환경모델을 알 수 없으나 경험을 해나가면서 환경을 이해해 나가면서 문제를 해결하는 케이스입니다.
• Model Based
환경 모델을 구축하여 문제를 푸는 케이스입니다.

Key Challenges in Learning to Make Sequences of Good Decisions

연속적인 의사 결정 문제는 문제의 상태에 따라 다르게 접근해야 합니다. 어떤 문제 같은 경우, 환경의 모델을 완벽하게 아는 경우가 있을 수 있습니다. 예를 들어, 무인 헬리콥터에서, 헬리콥터가 있는 환경에서 바람의 속도, 바람의 방향, 장애물의 위치, 날씨, 온도등 헬리콥터에 영향을 줄 수 있는 모든 요소들을 다 파악할 수 있으면 환경 모델을 완벽하게 아는 경우입니다. 이런 경우, 우리는 헬리콥터를 움직일 때마다 어떠한 결과를 초래하고 헬리콥터 움직임에 좋은지 나쁜지를 일일이 “계산”할 수 있습니다. 이런 경우를 Planning이라 합니다.

하지만, 대부분의 경우, 환경 모델을 완벽하게 아는 것은 불가능합니다. 따라서 환경에 직접 부딪혀 가면서(환경과 상호작용하면서) 경험을 통해 환경모델을 간접적으로 익히는 것입니다. 따라서 에이전트는 환경과의 상호작용을 통해 얻은 경험을 바탕으로 자신만의 전략을 구축해 나가는 것입니다. 포커 게임에서, 상대방이 가지고 있는 패나 전략을 알 순 없지만 상대방과 여러 번 게임을 통해 상대방 전략을 간접적으로 익힐 수 있습니다. 이렇게 푸는 방법이 “Reinforcement Learning”입니다.

Exploration and Exploitation

강화학습은 환경과의 상호작용을 통해 경험을 쌓아가면서 에이전트의 전략을 스스로 구축해나가는 것이라 하였습니다. 좋은 전략을 구축하기 위해, 실패도 해보고 성공도 해보면서 배워나가야 합니다. 그러나 어느 정도 경험을 했다면, 이 경험을 바탕으로 대략적인 전략을 구축해 나가야합니다. 이와 관련 강화학습 문제가 exploration과 exploitation입니다.

exploration이란 추후에 에이전트가 더 좋은 결정을 내릴수도 있기 때문에 새로운 결정을 시도해보는 과정입니다. 반면에, exploitation은 이제까지의 경험을 바탕으로 결정을 내리는 과정입니다. 이 둘 사이는 trade-off관계에 있습니다. exploration을 많이 하면 새로운 시도로 좋은 의사 결정 전략을 구축할 수 있지만 반면에 지금 당장 받을 보상을 희생해야 합니다. 이 둘 사이의 trade-off관계에 관한 예를 들어봅시다. 외식을 하기 위해 식당을 선택하는 경우, 이제까지 경험을 바탕으로 좋아하는 식당을 가는 건 exploitation이고, 새로운 식당을 시도해 보는 건 exploration입니다. 이 외에 다른 예는 아래와 같습니다.

Evalutation(Prediction) and Control

에이전트는 좋은 경험을 쌓기 위해서, exploration과 exploitation을 균형있게 활용해야합니다. 하지만 어떻게 활용하면서 경험을 쌓고, 전략을 구축하는 걸까요? 이제 관한 문제가 evalution과 control입니다.

evaluation은 일정 정책 아래, 기대보상을 추정하여 현재 따르는 정책이 좋고/나쁨을 평가하는 것입니다. 기대보상 추정은 결국 가치함수를 구하는 것입니다. 가치함수 $V_{\pi}(s)$ 는 현 정책을 따랐을 때, 상태 $s$ 의 가치입니다. 직접적으로는 현 상태의 가치지만 현 정책 아래에서 계산한 것이기 때문에 현 정책의 가치로도 생각할 수 있습니다. control은 최적정책을 찾는 것입니다. evalutation과정을 통해 정책의 가치를 평가했다면, 이 평가를 기반으로 더 나은 정책이 있는지를 찾는 과정입니다.

evaluation과 control은 독립적인 과정이 아닙니다. evaluation을 해야 control을 하고, control을 해야 evalutation을 할 수 있습니다. 즉 서로 맞물려서 최적의 정책을 찾아 나가는 것입니다. 아래 그리드월드 예제를 들어봅시다.

그림 9에서 주어진 정책은 모든 행동(좌, 우, 위, 아래)으로 갈 확률이 0.25로 동일합니다. 이 정책 아래 각 상태(그리드월드 한 칸)의 가치를 평가하면 오른쪽 숫자로 채워진 테이블이 됩니다. 최적 정책을 최적 가치함수 기반으로 찾을 수 있습니다. 그림 10처럼 최적 가치함수가 가운데 표처럼 구해졌다고 합시다. 이 기반으로 구한 최적 정책은 오른쪽 표와 같습니다. A’상태에서의 최적 정책은 위로 올라가는 것입니다. 왜냐하면 A’ 주변 가치함수 값들은 14.4, 17.8, 14.4입니다. A’에서 가장 높은 17.8의 가치를 가진 상태로 가는 것이 최적이기 때문입니다.

이상으로, Reinforcement Learning 소개[2] 포스팅을 마치겠습니다. 다음 포스팅은 Markov Decision Process을 알아보도록 하겠습니다.

1. CS234 Winter 2019 course Lecture 1
2. Richard S. Sutton and Andre G. Barto : Reinforcement Learning : An Introduction
3. David Silver Lecture 1