Critic Algorithm, GAE

16기 · 강화학습 · 3주차

Policy gradient의 목적함수와 advantage estimation을 연결하고, critic 기반 학습 안정화 흐름을 설명한 보고서입니다.

수식 전개와 직관을 함께 정리해 이후 RL 프로젝트의 공통 언어를 만들었습니다.

Limitations on Policy Gradients

일단 먼저 policy gradient에서 이상적인 목적 함수의 gradient 식을 다시 보자. ideal policy gradient function

\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \Bigg[ \sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t \mid s_t) \left( \sum_{t' = t}^{T}  \, r(s_{t'}, a_{t'}) \right) \Bigg]

그런데 우리는 실제로 저 기댓값을 쓸 수 없다. 왜? 모든 경로를 전부 고려하는 것(혹은 분석적 해 도출)이 불가능하기 때문이다. 따라서 우리는 다음과 같이 몇 번의 샘플링을 통해 위의 식을 근사한다. Monte Carlo policy gradient estimator

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T_i} \nabla_\theta \log \pi_\theta(a_t^{(i)} \mid s_t^{(i)}) \left( \sum_{t' = t}^{T_i}  \, r\big(s_{t'}^{(i)}, a_{t'}^{(i)}\big) \right)

근데 문제가 있다.

\sum_{t' = t}^{T_i}  \, r\big(s_{t'}^{(i)}, a_{t'}^{(i)}\big)

위 식에서 이 부분이 variance가 너무 높다. 이론적으로는 기댓값을 취해 variance가 작으나 여기서는 고작 몇 개의 샘플만 고려하므로 variance가 클 수밖에 없다. 아래에서는 이를 어떻게 개선했는지 살펴보자.

Improvement

Baseline

말그대로 baseline을 두어 variance를 감소시키는 방법이다.

\sum_{t' = t}^{T_i}  \, r\big(s_{t'}^{(i)}, a_{t'}^{(i)}\big)-b

여기서 $b$가 baseline이고, 이 값은 상수가 될 수도, $s_{t'}$ 등에 종속적인 값이 될 수도 있다.

Critic model

일단 먼저 아래 식을 생각해보자.

Q(s_t,a_t) \approx \hat{Q}_{i,t}=\sum_{t' = t}^{T_i}  \, r\big(s_{t'}^{(i)}, a_{t'}^{(i)}\big)

그러니까 이 식이 의미하는 바는, 우변이 Q-function을 추정한 값이라는 것인데,

Q(s_t, a_t) = \sum_{t'=t}^{T} \mathbb{E}_{\pi_\theta} \left[ r(s_{t'}, a_{t'}) \mid s_t, a_t \right]

즉 위의 식을 추정한 것이라는 소리다. 다시 말해, 원래는 모든 경로에 대한 기댓값이 Q-function인데, 우리가 실제로 학습에서 사용하는 값은 하나의 경로에 대한 값을 원래 Q-function의 추정값으로 보고 그냥 쓴다는 것이다. 그러면 여기서 드는 의문은 그냥 $Q(s_t, a_t)$를 사용하면 되지 않을까? 하지만 그것은 불가능하다. 이전에도 말했다시피 모든 경로를 전부 보는 것은 불가능하기에. 그렇다면, 살짝 우회해서 $Q(s_t,a_t)$를 학습하는 모델을 쓰면 되지 않을까? 이 아이디어가 바로 critic model이다. 핵심은 이렇다.

신경망을 활용해서, $V,Q,A$ 등을 학습하자.

실제로 학습은 이렇게 이루어진다 — $V$의 경우

\text{training data}=\left\{ \left( s_{i,t}, y_{i,t}=\sum_{t'=t}^{T} r(s_{i,t'}, a_{i,t'}) \right) \right\}

\mathcal{L}(\phi) = \tfrac{1}{2} \sum_i \left\| \hat{V}^{\pi}_{\phi}(s_i) - y_i \right\|^2

즉, 실제로 샘플링한 trajectory의 state와 그 state에서 받을 reward 총합을 GT로 해서, 학습을 진행하겠다는 것이다. 우리는 이렇게 학습한 모델을 baseline에도, $\sum_{t' = t}^{T_i} \, r\big(s_{t'}^{(i)}, a_{t'}^{(i)}\big)$값에도 적용할 수 있다.

Actor-Critic Algorithm

Value, Q, Advantage Function

actor-critic을 소개하기 전에 먼저 위의 3가지 function에 대해서 확실하게 짚고 넘어가고자 한다. 먼저 value function value function

V^\pi(s) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{T} r(s_t, a_t) \,\Big|\, s_0 = s \right]

의미는 — state $s$에서 policy $\pi$를 따를 때 얻을 수 있는 누적 reward의 기댓값이다.

state-action value function(Q-function)

Q^\pi(s,a) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{T} r(s_t, a_t) \,\Big|\, s_0 = s, a_0 = a \right]=r(s,a)+ \mathbb{E}_{s' \sim P(\cdot \mid s,a)} \left[V^\pi(s') \right]

의미는 — state $s$에서 action $a$를 취한 뒤 policy $\pi$를 따를 때 얻을 수 있는 누적 reward의 기댓값이다. 그리고 위처럼 value function과의 관계식으로도 표현할 수 있다. advantage function

A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)

의미는 — state $s$에서 action $a$를 취한 것이 평균적인 action을 취한 것보다 얼마나 누적 reward가 더 큰 지이다. 즉, value function이 baseline의 역할을 한다고 보면 된다.

Main Algorithm — Batch Actor-Critic

actor-critic은 위 챕터(Improvement)에서 언급한 개선점들을 적용한 방법론이라고 보면 된다. 바로 알고리즘을 보자.

1. $\{s_i,a_i\}$를 policy $\pi_\theta(a\mid s)$에서 샘플링한다(실제로 환경에서 돌린다).

1. 실제로 돌려서 나온 누적 reward를 토대로 $\hat{V}^\pi_\phi(s)$를 학습시킨다.

1. $\hat{V}^\pi_\phi(s)$를 토대로 advantage function을 추정한다.

\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \hat{V}^\pi_\phi(s_i') - \hat{V}^\pi_\phi(s_i)

1. policy gradient 식

\nabla_\theta J(\theta) \approx \sum_i \nabla_\theta \log \pi_\theta(a_i \mid s_i)\, \hat{A}^\pi(s_i, a_i)

1. policy gradient 식에 따라 파라미터를 업데이트한다.

\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)

즉 그러니까 기존 policy gradient에서

1. value function을 critic model을 통해 추정해서 썼고,

1. 그 추정한 value function을 baseline으로 활용

이런 점을 개선했다.

Discount Factors

문제점이 있다. 지금까지 다룬 policy gradient나 actor-critic은 모두 trajectory가 유한한 길이라고 가정한 것이다. 그렇다면 무한한 길이에서는? reward가 무한대가 되기 때문에 전혀 잘 작동하지 않는다. 그래서 이를 해결하고자 아주 심플하고 직관적인 관점을 도입하고자 한다.

가까운 미래의 reward가 더 중요하다.

이는 당연하다. 당장 100만원을 준다고 하면 엄청 좋겠지만, 10년 뒤에 100만원을 준다고 하면 별 감흥이 없지 않겠는가? 그래서 이를테면, 현재 state $s$에서 받은 reward를 100이라고 치자. 그리고 다음 state $s'$에서 받을 reward도 100이라고 치자. 그러면 reward 합계는

100+\gamma100 \,\,\, \text{where} \,\,\, \gamma \in [0,1]

여기서 $\gamma$를 할인율(discount factor)이라고 하는데, 이렇게 미래 reward에 대해서는 할인율을 적용해서 그 가치를 떨어뜨리는 것이다. 이러한 논리를 actor-critic에 적용하면 이렇다.

1. $\{s_i,a_i\}$를 policy $\pi_\theta(a\mid s)$에서 샘플링한다(실제로 환경에서 돌린다).

1. 실제로 돌려서 나온 누적 reward(+할인율 고려)를 토대로 $\hat{V}^\pi_\phi(s)$를 학습시킨다.

1. advantage function 추정 — $\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \gamma\hat{V}^\pi_\phi(s_i') - \hat{V}^\pi_\phi(s_i)$

1. policy gradient 식 — $\nabla_\theta J(\theta) \approx \sum_i \nabla_\theta \log \pi_\theta(a_i \mid s_i)\, \hat{A}^\pi(s_i, a_i)$

1. 파라미터 업데이트 — $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

여기서 바뀐 부분은 2번과 3번.

Architecture Design

Online Actor-Critic

이전에 소개한 main algorithm은 batch 방식인데, 이것은 한 번의 iteration step에서 전체 trajectory 데이터가 필요하다는 단점이 있다. 그러니까 — 오래걸린다. 그래서 online actor-ctiric에서는 한 번의 iteration step에서 action을 한 개만 쓴다. 즉 — action 한 번 하고, 학습 한 번 하는 식이다. 구체적인 알고리즘은 이렇다.

1. $\pi_\theta(a\mid s)$에서 action $a$를 뽑아 수행하고 결과 $(s,a,s',r)$을 얻는다.

1. $\hat{V}^\pi_\phi(s)$를 $r+\gamma \hat{V}^\pi_\phi(s')$를 통해 학습시킨다.

1. advantage function 추정 — $\hat{A}^\pi(s, a) = r(s, a) + \gamma\hat{V}^\pi_\phi(s') - \hat{V}^\pi_\phi(s)$

1. policy gradient 식 — $\nabla_\theta J(\theta) \approx \nabla_\theta \log \pi_\theta(a \mid s)\, \hat{A}^\pi(s, a)$

1. 파라미터 업데이트 — $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

주목해야 할 부분은 2번. 이전의 방법에서는 전체 trajectory를 볼 수 있기에 누적 reward를 구할 때 실제로 나온 reward를 합산하면 된다. 그러나 여기서는 action 한 번에 대해서 하기에 그것이 불가능하다. 그래서 아래의 근사식을 사용한다.

\hat{V}^\pi_\phi(s_t) \;\leftarrow\; r_t \;+\; \gamma \, \hat{V}^\pi_\phi(s_{t+1})

원래 더 정확히 하려면 $\hat{V}^\pi_\phi(s_{t+1})$이 부분이 기댓값이어야 하지만, 우리는 환경 $p(s_{t+1}\mid s_t,a_t)$을 모르므로 샘플링된 결과로 퉁치는 것이다.

GAE — Generalized Advantage Estimation

먼저 actor-critic과 policy gradient를 bias와 variance의 관점에서 살펴보자. 우선 actor-critic부터

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \left( r(s_{i,t}, a_{i,t}) + \gamma \hat{V}^\pi_\phi(s_{i,t+1}) - \hat{V}^\pi_\phi(s_{i,t}) \right)

• 장점 — low variance

• 단점 — high bias

왜? reward를 trajectory기반이 아닌 critic model 기반으로 계산하기에 variance는 낮다. 근데 문제는 그 critic model이 실제 $V^\pi$값과 당연히 오차가 있기에 bias가 있다. 다음으로 policy gradient

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \left( \left( \sum_{t'=t}^T \gamma^{\,t'-t} r(s_{i,t'}, a_{i,t'}) \right) - b \right)

• 장점 — low bias

• 단점 — high variance

왜? reward를 실제 trajectory를 기반으로 계산하기에 bias는 없다. 다만 단일 경로이므로 variance는 크다. 이를 해결하기 위한 첫 번째 단계는 이런 것이다.

이 그림처럼 보통은 time step이 멀어질 수록 variance가 커지니까, 너무 variance가 커지기 전에 적당한 time step에서 자르자는 것이다.

\hat{A}^\pi_n(s_t, a_t) 
= \sum_{t'=t}^{t+n} \gamma^{\,t'-t} r(s_{t'}, a_{t'}) 
- \hat{V}^\pi_\phi(s_t) 
+ \gamma^n \hat{V}^\pi_\phi(s_{t+n})

이것은

1. 시작 time step = $t$

1. $t+n$까지는 기존 trajectory 경로의 reward를 그대로 사용한다.

1. $t+n$이후부터는 critic model의 추정 reward를 사용한다.

이렇게 trajectory의 variance가 어느 정도 커지면 그 구간부터는 critic model을 사용하는 방식으로 절충하겠다는 것이다. 이걸 n-step advantage estimator 이라고 한다. 여기서 드는 의문은 이런 것이다 — 꼭 하나의 $n$을 사용해야 하는가? 그래서 여기서 두 번째 발전이 있고, 이게 GAE의 핵심 아이디어이다.

여러 $n$-step advantage estimator를 섞어 쓰자.

실제 수식을 보면 이렇다. advantage estimator in GAE

\hat{A}^{\pi}_{t}(\gamma,\lambda)
\;=\;
\sum_{l=0}^{\infty} (\gamma\lambda)^{\,l}\,\delta_{t+l}
\quad \text{where} \quad \delta_t = r_t + \gamma \hat{V}^\pi_\phi(s_{t+1}) - \hat{V}^\pi_\phi(s_t)

이게 핵심 아이디어란 뭔 관계인지

좋아! nn-step advantage → GAE 로 가는 과정을 한 줄씩 풀어서 유도해볼게

1) nnstep return과 nnstep advantage

\hat{A}^\pi_n(s_t,a_t)
= \Bigg( \sum_{l=0}^{n-1} \gamma^{\,l} r_{t+l} \Bigg)
+ \gamma^{\,n}\hat{V}^\pi_\phi(s_{t+n})
- \hat{V}^\pi_\phi(s_t)

2) TD residual(오차) 도입

\delta_t \;\;=\;\; r_t \;+\; \gamma \hat{V}^\pi_\phi(s_{t+1}) \;-\; \hat{V}^\pi_\phi(s_t)

3) nnstep advantage를 TD residual들의 합으로 표현

(전개해보면 아래 식이 성립)

\hat{A}^\pi_n(s_t,a_t) \;=\; \sum_{l=0}^{n-1} \gamma^{\,l}\,\delta_{t+l}

4) 여러 nnstep advantage를 지수 가중 평균 → GAE 정의

(가중치는 (1−λ)(γλ)n−1(1-\lambda)(\gamma\lambda)^{n-1}, 합치면 1-step부터 무한대까지)

\hat{A}^{\pi}_{t}(\gamma,\lambda)
\;=\;
(1-\lambda)\sum_{n=1}^{\infty} (\gamma\lambda)^{\,n-1}\, \hat{A}^\pi_n(s_t,a_t)

5) TD residual 표현을 대입해 간단화

3)의 결과를 4)에 넣으면 텔레스코핑처럼 깔끔하게 정리되어,

\hat{A}^{\pi}_{t}(\gamma,\lambda)
\;=\;
\sum_{l=0}^{\infty} (\gamma\lambda)^{\,l}\,\delta_{t+l}

6) 관계 요약(핵심)

• nnstep advantage는 연속된 TD residual의 유한 합

• GAE는 모든 nnstep advantage를 (γλ)n−1(\gamma\lambda)^{n-1}로 지수 가중 평균한 것

• 동치 형태: GAE = 지수 감쇠된 TD residual들의 무한 합

이렇게 보면, GAE는 “여러 nn-step 추정치의 혼합”