[CS285] 6. Actor-Critic Algorithms

💡 이 글은 『2024 PseudoLab 전반기 강화학습팀』으로 진행되었으며, CS285 Fall 2023를 따라 정리했습니다.

1. Actor-critic Algorithms

Policy gradient는 간단한 알고리즘이고, 안정적인 학습이 가능하지만 한편으로는 variance가 크고, 하나의 episode가 전부 끝나야만 학습이 가능하기 때문에 학습이 느리다는 문제가 있었다. 이를 해결하기 위해 causality, baseline, off-policy 등의 방법을 사용할 수 있었다. 이번 강의에서는 이를 개선하기 위한 Actor-critic Algorithms에 대해 알아보자.

1.1. Improving the policy gradient

Policy gradient에서는 다음과 같이 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} \vert s_ {i,t}) \hat{Q}_ {i, t} ^ { \pi}\]

이때 $\hat{Q}_ {i, t} ^ { \pi}$는 “reward to go”, 즉 state $s_ {i, t}$에서 action $a_ {i, t}$를 취했을 때의 total reward의 추정값을 의미한다. 즉 다음과 같다.

\[\hat{Q}_ {i, t} ^ { \pi} = \sum_ {t'=t} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime})\]

이 의미를 생각해보면 $\hat{Q}_ {i, t} ^ { \pi}$는 $s_ {i, t}$에서 $a_ {i, t}$를 취했을 때 중 한 가지 trajectory를 따라 얻을 수 있는 reward의 추정값임을 알 수 있다.

그러나 실제로는 randomness에 의해 결과가 한 가지 trajectory만 나타나는 것이 아니므로 이 모든 trajectory에 대하여 평균값을 구하는 것이 더욱 정확한 추정이 될 것이다. 이를 수식으로 나타내면 다음과 같다.

\[Q(s_t, a_t) = \sum _ {t'=t} ^T \mathbb{E} _ {\pi _ \theta} \left[r(s_ {t ^ \prime}, a_ {t ^ \prime}) \vert s_t, a_t \right]\]

이제 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} \vert s_ {i,t}) Q(s_ {i,t}, a_ {i,t})\]

이제 policy gradient를 개선했던 것처럼 baseline을 도입해보자. 그때 baseline을 전체 reward의 평균으로 구했던 것과 유사하게 여기서는 다음과 같이 value function $V(s_t)$를 baseline으로 사용할 수 있다. 다만 이 방법은 unbiased가 아니다.

\[V(s_t) = \mathbb{E} _ {a_t \sim \pi_ \theta (a_t \vert s_t)} \left[Q(s_t, a_t) \right]\]

이제 다시 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} \vert s_ {i,t}) \left(Q(s_ {i,t}, a_ {i,t}) - V(s_ {i,t}) \right)\]

그리고 이를 간단하게 두기 위하여 $A^ \pi (s_t, a_t) = Q^ \pi (s_t, a_t) - V^ \pi (s_t)$로 정의하자. 각각 수식을 정리하면 다음과 같다.

\[\begin{aligned} Q^ \pi (s_t, a_t) &= \sum _ {t'=t} ^T \mathbb{E} _ {\pi _ \theta} \left[r(s_ {t ^ \prime}, a_ {t ^ \prime}) \vert s_t, a_t \right] \\ V^ \pi (s_t) &= \mathbb{E} _ {a_t \sim \pi_ \theta (a_t \vert s_t)} \left[Q^ \pi (s_t, a_t) \right] \\ A^ \pi (s_t, a_t) &= Q^ \pi (s_t, a_t) - V^ \pi (s_t) \\ \end{aligned}\]

Q-function은 $s_t$에서 $a_t$를 택하는 경우의 total reward, Value function은 $s_t$에서 어떤 action을 택하든 얻을 수 있는 reward의 평균값, advantage function은 그 차이, 즉 $a_t$가 평균보다 얼마나 나은지를 의미한다.

한편 $Q^\pi$를 다음과 같이 나타낼 수 있다.

\[\begin{aligned} Q^ \pi (s_t, a_t) &= r(s_t, a_t) + \sum_ {t^\prime = t+1} ^T \mathbb{E} _ {\pi _ \theta} \left[r(s_ {t ^ \prime}, a_ {t ^ \prime}) \vert s_t, a_t \right] \\ &= r(s_t, a_t) + \mathbb{E} _ {s_{t+1} \sim p(s_{t+1} \vert s_t, a_t)} \left[ V^ \pi (s_{t+1}) \right] \\ &\approx r(s_t, a_t) + V^ \pi (s_{t+1}) \\ \end{aligned}\]

대신 이는 여러 가능성 있는 $s_{t+1}$ 중 하나만 선택하는 것이므로 variance가 커지는 문제가 있다. 그러나 이러한 방법은 간단하다. 결과적으로 action function을 다음과 같이 근사할 수 있다.

\[A^ \pi (s_t, a_t) \approx r(s_t, a_t) + V^ \pi (s_{t+1}) - V^ \pi (s_t)\]

$Q, A$와는 달리 value function $V$는 $s_t$만을 인수로 가지기 때문에 simple fitting이 가능하다. 즉, value function fitting을 진행하는 것이 경제적이다.

2. Policy Evaluation

이제 우리의 목표는 다음과 같은 value function을 추정하는 것이다.

\[V^ \pi (s_t) = \sum _ {t^ \prime = t} ^T \mathbb{E} _ {\pi _ \theta} \left[ r(s_ {t ^ \prime}, a_ {t ^ \prime}) \vert s_t \right]\]

좋은 방법 중 하나는 여러 trajectory에 대한 값을 이용하여 policy evaluation을 진행하는 것이다.

\[V^ \pi (s_t) \approx \frac{1}{N} \sum_ {i=1} ^N \sum_ {t^ \prime = t} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime})\]

그러나 이러한 방법은 $s_t$에서 여러 가능성을 테스트해야 한다는 것이고, simulator를 이용한 환경이라면 가능할지 몰라도 실제 환경에서는 불가능하다. 따라서 아쉽지만 다음과 같이 single sample로 추정해야 한다.

\[V^ \pi (s_t) \approx \sum _ {t^ \prime = t} ^T r(s_ {t ^ \prime}, a_ {t ^ \prime})\]

Actor-critic methods에서는 neural network $\hat{V}_ \phi ^ \pi (s_{i, t})$를 이용하여 value function을 추정한다. 이때 $\phi$는 neural network의 parameter이다. $y_{i, t} = \sum _ {t^ \prime = t} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime})$라고 할 때, 다음과 같은 supervised regression을 통해 $\phi$를 학습할 수 있다.

\[\mathcal{L} ( \phi) = \frac{1}{2} \sum_ i \left\Vert \hat{V}_ \phi ^ \pi (s_i) - y_i \right\Vert ^ 2\]

지금까지 우리는 Monte Carlo target $y_ {i, t} = \sum _ {t^ \prime = t} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime})$를 이용하여 value function을 추정했다. 이는 high variance를 가지는 방법이다. 이를 해결하기 위해 bootstrapping을 이용할 수 있다. 우리가 추정하고자 하는 ideal target을 다음과 같이 근사할 수 있다. 이는 $Q^ \pi$의 근사와 동일한 과정이다.

\[\begin{aligned} y_ {i, t} &= \sum _ {t^ \prime = t} ^T \mathbb{E} _ {\pi _ \theta} \left[ r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \vert s_t \right] \\ &\approx r(s_ {i, t}, a_ {i, t}) + V^ \pi (s_ {i, t+1}) \\ &\approx r(s_ {i, t}, a_ {i, t}) + \hat{V}_ \phi ^ \pi (s_ {i, t+1}) \\ \end{aligned}\]

이러한 ideal target $y_ {i, t}$을 이용하면 더 많은 샘플에 대한 평균을 추정하는 것과 유사하게 되므로 variance가 감소하는 효과가 있다.

3. Discount Factors

지금까지의 actor-critic algorithm을 정리하면 다음과 같다.

1. Sample $\lbrace s_i, a_i \rbrace$ from $\pi _ \theta (a \vert s)$
2. Fit $\hat{V}_ \phi ^ \pi (s_i)$ to sampled reward sums
3. Evaluate $\hat{A} ^ \pi (s_i, a_i) = r(s_ i, a_ i) + \hat{V}_ \phi ^ \pi (s_ i ^ \prime) - \hat{V}_ \phi ^ \pi (s_ i)$
4. $\nabla_ \theta J(\theta) \approx \sum_ i \nabla_ \theta \log \pi_ \theta (a_ i \vert s_ i) \hat{A} ^ \pi (s_ i, a_ i)$
5. $\theta \leftarrow \theta + \alpha \nabla_ \theta J(\theta)$

그러나 만약 episode length $T$가 $\infty$라면 $\hat{V}_ \phi ^ \pi (s_ i)$는 무한히 커지는 문제가 발생한다. 이를 해결하기 위해 discount factor $\gamma$를 도입할 수 있다. 이는 future reward에 대한 가중치를 조절하는 역할을 한다. 아래 식은 나중보다 지금 reward를 받는 것이 더 중요하다는 것을 의미한다.

\[y_{i, t} \approx r(s_ {i, t}, a_ {i, t}) + \gamma \hat{V}_ \phi ^ \pi (s_ {i, t+1})\]

이때 $\gamma \in [0, 1]$이고, 보통 0.99 정도의 값을 사용한다. 이를 MDP에 반영하기 위하여, 아래와 같이 transition 시에 $1-\gamma$의 확률로 death state로 이동하도록 한다.

간단한 policy gradient에 이 discount factor를 적용해보자. 먼저 기존 policy gradient는 다음과 같이 쓸 수 있다.

\[\begin{aligned} \nabla_ \theta J(\theta) &\approx \frac{1}{N} \sum_ {i=1} ^N \left( \sum_ {t=1} ^T \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \right) \left( \sum_ {t ^ \prime = 1} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ &= \frac{1}{N} \sum_ {i=1} ^N \sum_ {t=1} ^T \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \left( \sum_ {t ^ \prime = t} ^T r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ \end{aligned}\]

첫 번째 식에 $\gamma$를 적용하면 다음과 같다.

\[\begin{aligned} \nabla_ \theta J(\theta) &\approx \frac{1}{N} \sum_ {i=1} ^N \left( \sum_ {t=1} ^T \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \right) \left( \sum_ {t ^ \prime = 1} ^T \gamma ^ {t ^ \prime - 1} r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ &= \frac{1}{N} \sum_ {i=1} ^N \sum_ {t=1} ^T \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \left( \sum_ {t ^ \prime = t} ^T \gamma ^ {t ^ \prime - 1} r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ &= \frac{1}{N} \sum_ {i=1} ^N \sum_ {t=1} ^T \gamma ^ {t-1} \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \left( \sum_ {t ^ \prime = t} ^T \gamma ^ {t ^ \prime - t} r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ \end{aligned}\]

두 번째 식에 $\gamma$를 적용하면 다음과 같다.

\[\begin{aligned} \nabla_ \theta J(\theta) &\approx \frac{1}{N} \sum_ {i=1} ^N \sum_ {t=1} ^T \nabla_ \theta \log \pi_ \theta (a_ {i, t} \vert s_ {i, t}) \left( \sum_ {t ^ \prime = t} ^T \gamma ^ {t ^ \prime - t} r(s_ {i, t ^ \prime}, a_ {i, t ^ \prime}) \right) \\ \end{aligned}\]

두 번째 식에 비해 첫 번째 식이 더욱 합리적인 것처럼 보인다. 첫 번째 식은 future reward 뿐만 아니라 future policy, 혹은 future decision 또한 덜 고려하겠다는 의미를 내포하고 있기 때문이다. 그러나 실제로는 첫 번째 식을 사용한다. 사실 우리가 discount factor $\gamma$를 사용하는 이유는 $\hat{V}_ \phi ^ \pi (s_ {i, t+1})$를 계산할 수 있는 값으로 만들기 위해서이지 future decision을 덜 고려하기 위함이 아니다. 즉, 오히려 첫 번째 식은 future decision이 덜 고려되기 때문에 최종 학습 후에는 두 번째 식보다 성능이 낮다. 한편 discount factor가 작을수록 미래의 reward를 덜 고려하게 되므로 variance를 낮게 만들 수 있다.

Discount factor를 고려한 actor-critic algorithm은 다음과 같다.

1. Sample $\lbrace s_i, a_i \rbrace$ from $\pi _ \theta (a \vert s)$
2. Fit $\hat{V}_ \phi ^ \pi (s_i)$ to sampled reward sums
3. Evaluate $\hat{A} ^ \pi (s_i, a_i) = r(s_ i, a_ i) + \gamma \hat{V}_ \phi ^ \pi (s_ i ^ \prime) - \hat{V}_ \phi ^ \pi (s_ i)$
4. $\nabla_ \theta J(\theta) \approx \sum_ i \nabla_ \theta \log \pi_ \theta (a_ i \vert s_ i) \hat{A} ^ \pi (s_ i, a_ i)$
5. $\theta \leftarrow \theta + \alpha \nabla_ \theta J(\theta)$

Discount factor를 고려하면 online learning이 가능해지며, 이를 포함한 online actor critic algorithm은 다음과 같다.

1. Take action $a \sim \pi_ \theta (a \vert s)$, get $(s, a, s^ \prime, r)$
2. Update $\hat{V}_ \phi ^ \pi (s)$ with target $r + \gamma \hat{V}_ \phi ^ \pi (s^ \prime)$
3. Evaluate $\hat{A} ^ \pi (s, a) = r(s, a) + \gamma \hat{V}_ \phi ^ \pi (s ^ \prime) - \hat{V}_ \phi ^ \pi (s)$
4. $\nabla_ \theta J(\theta) \approx \nabla_ \theta \log \pi_ \theta (a \vert s) \hat{A} ^ \pi (s, a)$
5. $\theta \leftarrow \theta + \alpha \nabla_ \theta J(\theta)$

이제 이러한 알고리즘을 실제로 어떻게 디자인할지 알아보자.

4. Actor-critic Algorithm Design

4.1. Architecture Design

첫 번째로 고려할 점은 architecture design이다. value function과 policy function을 하나로 구성할지, 두 개로 구성할지 결정해야 한다.

두 개의 독립된 네트워크로 구성하는 것은 간단하고, 학습이 안정적이다. 그러나 같은 네트워크를 공유하는 경우 서로 도움을 줄 수 있다는 장점이 있다. 예를 들어 둘 다 이미지를 입력으로 받는 CNN 모델일 경우 서로의 perception에 도움을 줄 수 있다. 둘 중 어떤 것이 더 좋다는 절대적인 정답은 없고, 데이터의 형태나 문제의 복잡도에 따라 다르게 결정해야 한다.

4.2. Online actor-critic in practice

한편 online actor-critic algorithm에서 고려해야 할 요소는 batch training이다. $\hat{V}_ \phi ^ \pi (s)$ 및 $\pi_ \theta (a \vert s)$를 학습할 때 mini-batch를 사용하는 것이 학습의 안정성을 높일 수 있는데, 이를 활용하기 위해 아래와 같이 synchronized parallel actor-critic 또는 asynchronous parallel actor-critic을 사용할 수 있다.

Synchronized를 사용하는 것이 좋지만, 실제 환경에서는 parallel agent마다 다른 환경에서 다른 시간동안 학습을 진행하기 때문에 효율을 생각한다면 asynchronous를 사용하는 것이 좋다. 그러나 asynchronous의 문제는 policy가 학습되는 동안 다른 agent에서 수집한 data가 예전 policy에 의해 얻어질 수 있다는 것이다. 즉, bias와 off-policy 문제가 있다. 차라리 이를 해결하기 위하여 off-policy actor critic을 만들어 사용하면 어떨까?

즉, 일종의 replay buffer에 이전에 수집한 data를 저장해두고, 이를 이용하여 batch training을 진행하는 것이다. 그러나 replay buffer의 $\lbrace s_i, a_i, r_i, s_i ^ \prime \rbrace$은 past policy로 얻은 data이기 때문에 present policy update에 이를 사용하는 것은 부적절하다. 이를 해결하기 위해 target을 다음과 같이 수정한다.

\[\begin{aligned} y_i &= r_i + \gamma \hat{V}_ \phi ^ \pi (s_i ^ \prime) \\ &= r_i + \gamma \hat{Q}_ \phi ^ \pi (s_i ^ \prime, a_i ^ \prime) \quad a_i ^ \prime \sim \pi_ \theta (a_ i ^ \prime \vert s_ i ^ \prime) \\ \end{aligned}\]

$a_i ^ \prime$은 present policy로부터 얻은 action이기 때문에 target의 오차가 어느 정도 보정되게 되고, 이를 활용하여 학습하면 off-policy actor-critic을 구현할 수 있다. 학습 역시 $\hat{V}_ \phi ^ \pi (s)$가 아닌 $\hat{Q}_ \phi ^ \pi (s, a)$를 이용하여 진행한다.

\[\mathcal{L} ( \phi) = \frac{1}{N} \sum_ i \left\Vert \hat{Q}_ \phi ^ \pi (s_i, a_i) - y_i \right\Vert ^ 2\]

지금까지의 알고리즘을 정리하면 다음과 같다.

1. Take action $a \sim \pi_ \theta (a \vert s)$, get $(s, a, s^ \prime, r)$, store in $\mathcal{R}$
2. Sample a batch $\lbrace s_i, a_i, r_i, s_i ^ \prime \rbrace$ from buffer $\mathcal{R}$
3. Update $\hat{Q}_ \phi ^ \pi$ with target $y_i = r_i + \gamma \hat{Q}_ \phi ^ \pi (s_i ^ \prime, a_i ^ \prime)$ for each $s_i, a_i$
4. $\nabla_ \theta J(\theta) \approx \frac{1}{N} \sum_ i \nabla_ \theta \log \pi_ \theta (a_i ^ \pi \vert s_i) \hat{Q} ^ \pi (s_i, a_i ^ \pi)$ where $a_i ^ \pi \sim \pi_ \theta (a_i \vert s_i)$
5. $\theta \leftarrow \theta + \alpha \nabla_ \theta J(\theta)$

남은 문제는 $s_i \sim p_\theta (s)$가 아니라는 것이다. 하지만 이것까지 어떻게 할 수는 없다. 오히려 $s_i$가 $p_\theta (s)$의 broader distribution에서 sampling되는 것이라고 생각하는 수밖에는 없는 것이다.

5. State-dependent Baselines

5.1. State-dependent Baselines

Critic을 policy gradient의 state-dependent baseline으로 사용할 수 있다. 먼저 actor-critic과 policy gradient를 다시 살펴보면 다음과 같다.

이제 baseline $b$ 대신 state-dependent value function $\hat{V}_ \phi ^ \pi (s)$를 사용하면, 다음과 같이 bias 없이 lower variance를 얻는다.

이처럼 bias-variance trade-off를 조절하는 다른 방법으로는 N-step returns, GAE(Generalized Advantage Estimation) 등이 있다.

5.2. N-step returns

N-step returns는 critic과 Monte Carlo 간의 장단점을 leverage하는 아이디어로부터 시작한다. Actor-critic은 variance가 작은 대신 bias가 크고, Monte Carlo는 bias가 없는 대신 variance가 크다.

Actor-critic은 value function을 이용해 single-sample estimate를 보완하는 방법으로 $s_{t+1}$부터 모든 시점의 평균을 예측하는 반면, Monte Carlo는 $s_t$부터 마지막 시점까지 single-sample estimate를 얻는 방식이다. 따라서 둘은 서로 양극단에 있고, 적당히 N-step까지는 Monte Carlo를 통해 single-sample estimate를 얻고 나머지는 value function으로 나머지 시점의 평균을 예측하는 것이 N-step returns이다.

따라서 이를 식으로 나타내면 다음과 같다.

\[\hat{A}_ n ^ \pi (s_t, a_t) = \sum_ {t^\prime = t} ^ {t+n} \gamma ^ {t^\prime - t} r(s_ {t^\prime}, a_ {t^\prime}) + \gamma ^ n \hat{V}_ \phi ^ \pi (s_ {t+n}) - \hat{V}_ \phi ^ \pi (s_t)\]

$n$이 커질수록 Monte Carlo의 영향이 커지고, $n$이 작을수록 value function의 영향이 커진다. 이를 이용하면 bias-variance trade-off를 조절할 수 있다.

5.3. Generalized Advantage Estimation (GAE)

Generalized Advantage Estimation (GAE)는 N-step returns의 일반화된 형태로, exponentially-weighted average of N-step returns를 사용한다. 즉, 모든 $n$에 대하여 N-step returns를 계산하고, 이를 weighted sum으로 더해 사용한다.

\[\hat{A}_ {GAE} ^ \pi (s_t, a_t) = \sum_ {n=1} ^ \infty w_n \hat{A}_ n ^ \pi (s_t, a_t)\]

보통 작은 $n$의 비율이 높아야 variance가 낮기 때문에, 이를 반영하여 점점 감소하는 $w_n = \lambda ^{n-1}$로 설정(exponential falloff)한다. 참고로 GAE의 식을 다시 정리하면 다음과 같은데,

\[\hat{A}_ {GAE} ^ \pi (s_t, a_t) = \sum_ {t^\prime = t} ^ \infty (\gamma \lambda)^ {t^\prime - t} \left( r(s_ {t^\prime}, a_ {t^\prime}) + \gamma \hat{V}_ \phi ^ \pi (s_ {t^\prime + 1}) - \hat{V}_ \phi ^ \pi (s_ {t^\prime}) \right)\]

이로부터 $\lambda$도 discount factor $\gamma$와 마찬가지로 variance를 조절하는 hyperparameter로 사용할 수 있다. $\lambda$가 작을수록 future reward를 덜 고려하게 되므로 variance가 낮아진다.

CS285 카테고리 내 다른 글 보러가기