Ch12. Asynchronous Advantage Actor Critic (A3C) Network

DQN에 이어 또다른 Deep Reinforcement Learning인 Asynchronous Advantage Actor Critic Network (A3C)에 대해 알아보자.

 

DQN 내용은 이전 포스팅을 참조하자.

 

https://jjuke-brain.tistory.com/99?category=957313 

Ch11. Deep Q Network

 

 

 

목차

 

 

 

 

0. DQN의 문제점 및 A3C의 고안

 

Deep Q Network를 통해 Atari Game에서 사람 수준의 성능을 보이는 agent를 학습시킬 수 있었다.

하지만 문제점이 존재했는데, computational cost가 매우 많이 들고,(특히 replay buffer 때문에 메모리 사용량이 매우 크다.) 학습 시간이 매우 오래 걸린다는 점이다.

 

따라서 Google의 DeepMind에서 이를 보완한 또다른 강화학습 알고리즘을 제시하였는데, 그것이 바로 Aysnchronous Advantage Actor Critic (A3C) 알고리즘이다.

A3C 알고리즘은 (발표 당시) 그리 큰 cost와 학습 시간을 들이지 않고도 다른 deep reinforcement learning 알고리즘의 성능을 압도하는 알고리즘이었다.

 

A3C 알고리즘의 주요 아이디어는 '여러 agent를 병렬로 학습시킨 후 합친다'라는 점이다.

어떤 방법으로 이와 같은 성능을 내는지 구체적으로 살펴보자.

 

 

 

 

 

1. Dueling Network Architecture

 

A3C 알고리즘을 이해하기 위해 알아두어야 할 개념이 몇 가지 존재한다.

그중 첫 번째는 'Dueling Network'라는 개념이다.

 

 

 

 

1) Advantage Function

 

이제까지 Q function과 Value Function에 대한 개념을 수없이 말해왔다.

간단히 개념을 정리하자면, Q function은 state \(s\)에서 특정 action \(a\)가 얼마나 좋은지를 나타내는 함수이고,

Value function은 agent가 존재하는 state \(s\)가 얼마나 좋은지를 나타낸다.

 

여기서, Advantage Funtion이란, 단순히 Value Function과 Q Function의 차이를 말한다.

 

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

 

value function은 개념적으로 해당 state가 '평균적으로' 얼마나 좋은지를 나타낸다고 볼 수 있다.

따라서 state value function (Q function)에서 value function을 뺀다는 것은 개념적으로 'state \(s\)에서 action \(a\)를 하는 게 다른 action을 하는 것보다 얼마나 좋은가?'를 나타낸다.

 

단순히 위 수식을 변형하여, Q function을 Value Function과 Advantage Function의 합으로 나타낼 수도 있다.

 

\( Q(s, a) = V(s) + A(a) \)

 

 

 

 

2) Dueling Network Architecture

 

Dueling Network를 앞서 배웠던 DQN 관점에서 알아보자. (Dueling DQN)

 

기존 DQN은 입력으로 이미지가 주어지고, 하나의 DQN network를 통해 Q function의 값을 출력했다.

그런데 Dueling DQN은 fully connected layer 부분에서 다음 그림과 같이 두 가지 stream으로 나뉜다.

 

DQN vs Dueling DQN

 

위쪽 stream에서는 state value function인 \(V(s)\)를 계산하고, 아래쪽 stream에서는 advantage function인 \(A(a)\)(정식 표현은 state를 포함하는 것이 맞지만, 간단히 이와 같이 표기한다)를 계산한다.

각각의 뉴런 개수가 다른데, 이는 value function과 advantage function의 개념을 생각해보면 쉽다. value function은 현재 state 개수와 같으므로, 뉴런이 하나일 것이고, advantage function은 action 각각에 대해 계산되어야 하므로 action의 개수만큼 뉴런이 존재할 것이다.

이렇게 계산된 \(V(s)\)와 \(A(a)\)를 더해 \(Q(s, a)\)를 구할 수 있다.

 

그렇다면 이렇게 두 stream으로 나누어 계산을 진행했을 때의 장점이 무엇일까?

 

복잡한 environment에서는 많은 state와 각 state에서의 action들이 존재할 것이다. 특히 해당 state에서의 action space가 매우 클 때에는 모든 action을 일일이 계산하는 것은 그리 중요한 작업이 아니다.

 대부분의 action은 state에 크게 영향을 주지 않기 때문이다.

이러한 경우, dueling DQN이 기존 DQN보다 더 정확한 Q value를 추정한다. 그리고 더 효율적이고, 강건하다(robust).

첫 번째 stream, 즉 value function stream에서 특히 각각의 action에 대한 값을 계산하는 것이 중요하지 않다. value function은 state가 얼마나 좋은지만 나타내기 때문이다.

 

이러한 dueling nerwork 방식은 A3C network에서도 사용되므로, 개념을 숙지해두자.

 

 

 

 

 

2. Policy Gradient Methods

 

Policy Gradient Method를 이해하기 위해서는 수식을 이해해야 한다. 복잡한 수식 전개 과정을 모두 아는 것 보다, 개념적으로 수식의 의미를 파악해보자.

 

 

 

1) action-value methods vs policy gradient methods

 

이제까지 배운 모든 강화학습 알고리즘에서는 optimal policy를 찾기 위해 Q function을 사용했다. 이를 다른 말로 'action-value methods'라고 한다.

좀 더 구체적으로 말하자면, action의 값을 학습하고, 추정된 action 값을 기반으로 최적의 action을 선택하는 것이다.

따라서 Q function 없이는 optimal policy를 찾을 수 없었다.

 

하지만 Policy Gradient Methods를 사용하면, Q function 없이 Policy Gradient를 사용하여 직접적으로 optimal policy를 찾을 수 있다.

 

이제까지 policy는 함수로 나타낸 적은 없었는데, 직접적으로 최적화하기 위해서는 policy를 함수로 표현해주어야 한다.

이를 위해 policy를 \(\theta\)로 parameterize해준다.

 

\(\pi(a|s;\theta) = Pr\{ A_t = a | S_t = s, \theta_t = \theta \} \)

 

이 식이 의미하는 것은, time \(t\)에서 state \(s\)라는 environment가 주어졌을 때, action \(a\)가 선택될 확률을 \(theta\)로 parameterize한 것이다.

(참고로 value function은 그대로 존재하지만, parameter의 학습에만 사용된다.)

 

이때 parameter \(theta\)를 deep neural network로 학습시킬 수 있다.

performance measure (scalar) \(J(\theta)\)'에 대해 parameter \(theta\)를 다음과 같이 update할 수 있다.

 

\( \theta_{t+1} = \theta_t + \alpha \nabla J(\theta_t) \)

 

여기서 주의할 점은, \(J(\theta)\)는 loss가 아닌 성능을 나타내는 지표로써, maximize해야한다는 것이다. 따라서 gradient ascent 방식을 구현하기 위해 gradient를 더해주어 weight를 update한다.

 

위와 같은 방법을 policy gradient methods라 하고, value function 또한 근사(학습)가 가능하다. (불가능할수도 있다.)

이때 policy와 value function을 모두 학습하는 방법을 'actor-critic method'라 한다.

• actor : learned policy를 통해 action을 고르는 것, 또는 고르는 주체자인 agent를 말한다.
• critic : 학습된 value function을 '평가'한다는 의미로, 보통 state value function을 말한다.

 

그렇다면, Policy Gradient \(\nabla J(\theta)\)를 어떻게 구하는지 간단하게 알아보자.

 

 

 

 

2) Monte Carlo Policy Gradient

 

먼저, gradient를 구하는 식은 다음과 같다.

 

\( \begin{align*} \nabla J(\boldsymbol{\theta}) & \propto \underset{s}{\sum} \mu (s) \underset{a}{\sum} q_\pi (s, a) \nabla \pi (a|s, \boldsymbol{\theta}) \\ &= \mathbb{E}_\pi \left[ \underset{a}{\sum} q_\pi(S_t, a) \nabla \pi(a|S_t, \boldsymbol{\theta}) \right] \end{align*} \)

 

여기서, 아래 식의 \(q_\pi \)는 \(\theta\)와 관련이 없고, \(\nabla \pi \)부분이 parameterized policy임을 주목하자.

 

\( \begin{align*} \nabla J(\boldsymbol{\theta}) &= \mathbb{E}_\pi \left[ \underset{a}{\sum} \pi(a|S_t, \boldsymbol{\theta})q_\pi(S_t, a) \frac{\nabla \pi (a|S_t, \boldsymbol{\theta})}{\pi (a|S_t, \boldsymbol{\theta})} \right] \\ &= \mathbb{E}_\pi \left[ q_pi(S_t, A_t) \frac{\nabla \pi (a|S_t, \boldsymbol{\theta})}{\pi (a|S_t, \boldsymbol{\theta})} \right] \qquad (replacing \; a \; by \; the \; sample \; A_t ~ \pi ) \\ &= \mathbb{E}_\pi \left[G_t \frac{\nabla \pi (a|S_t, \boldsymbol{\theta})}{\pi (a|S_t, \boldsymbol{\theta})} \right] \qquad (\because \mathbb{E}_\pi[G_t|S_t, A_t] = q_\pi(S_t, A_t)) \end{align*} \)

 

\(\pi\) policy에서 \(A_t\)를 샘플링하므로 첫 번째 식에서 두 번째 식을 얻을 수 있고,

\(G_t\)는 expected return이므로 마지막 식으로 정리할 수 있다.

 

따라서 최종적으로 weight \(\boldsymbol{\theta}\)를 update하는 식은 다음과 같이 작성할 수 있다.

 

\( \boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t + \alpha G_t \frac{\nabla \pi(A_t | S_t, \boldsymbol{\theta}_t)}{\pi(A_t | S_t, \boldsymbol{\theta}_t)} \)

 

이때, log의 미분에 의해 \( \frac{\nabla \pi(A_t | S_t, \boldsymbol{\theta}_t)}{\pi(A_t | S_t, \boldsymbol{\theta}_t)} \)는 \( \nabla \ln \pi(A_t|S_t, \boldsymbol{\theta}) \)로 대체 가능하다.

또한, 이 벡터를 'eligibility vector'라 한다.

 

 

 

 

3) REINFORCE with Baseline

 

앞서 언급한 policy gradient의 식은 다음과 같다.

 

\( \nabla J(\boldsymbol{\theta}) \propto \underset{s}{\sum} \mu (s) \underset{a}{\sum} q_\pi (s, a) \nabla \pi (a|s, \boldsymbol{\theta}) \)

 

여기서 action value를 임의의 baseline '\(b(s)\)'와 비교하는 term을 통해 좀 더 일반화가 가능하다.

 

\( \nabla J(\boldsymbol{\theta}) \propto \underset{s}{\sum} \mu (s) \underset{a}{\sum} \left( q_\pi (s, a) - b(s) \right) \nabla \pi (a|s, \boldsymbol{\theta}) \)

 

따라서 weight의 update도 다음 식으로 대체된다.

 

\( \boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t + \alpha \left( G_t - b(S_t) \right) \frac{\nabla \pi(A_t | S_t, \boldsymbol{\theta}_t)}{\pi(A_t | S_t, \boldsymbol{\theta}_t)} \)

 

이는 Monte Carlo에서 계산된 expected return 값인 \(G_t\)가 최소한 baseline \(b\) 이상이 되는 것이 좋다는 의미를 갖는다.

일반적으로 baseline은 state value \( \hat{v}(S_t, \mathbf{w}) \)를 추정한다. (이때, \( \mathbf{w} \in \mathbb{R}^d \) 는 강화학습 알고리즘으로 학습된 weight vector를 말한다.)

따라서, 이때 '\(G_t - \hat{v}(S_t, \mathbf{w})\)'는 Advantage Function을 나타낸다. (\(Q - V\))

 

 

 

 

4) Actor-Critic Methods

 

REINFORCE-with-baseline 방법이 policy와 state-value function을 모두 학습하기는 하지만, 이를 actor-critic이라 하지는 않는다.

왜냐하면 state-value function은 baseline으로 쓰일 뿐, actor의 행동을 평가하는 'critic'의 역할을 하지는 않기 때문이다.

 

One-step Actor-Critic (TD(0), 즉 전체 return이 아닌 한 step만의 reward로 학습하는 방법)에서 weight update는 다음과 같이 이루어진다.

 

\( \begin{align*} \boldsymbol{\theta}_{t+1} &= \boldsymbol{\theta}_t + \alpha \left( G_{t:t+1} - \hat{v}(S_t, \mathbf{w}) \right) \frac {\nabla \pi (A_t | S_t, \boldsymbol{\theta}_t)}{\pi (A_t | S_t, \boldsymbol{\theta}_t)} \\ &= \boldsymbol{\theta}_t + \alpha \left( R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) - \hat{v}(S_t, \mathbf{w}) \right) \frac {\nabla \pi (A_t | S_t, \boldsymbol{\theta}_t)}{\pi (A_t | S_t, \boldsymbol{\theta}_t)} \\ &= \boldsymbol{\theta}_t + \alpha \delta_t \frac {\nabla \pi (A_t | S_t, \boldsymbol{\theta}_t)}{\pi (A_t | S_t, \boldsymbol{\theta}_t)} \end{align*} \) 

 

간단히 \(\theta_t\) 부분만 Temporal Difference를 사용하면서 바뀐 모습이다.

Temporal Difference를 사용함으로써 episode를 끝까지 실행하지 않고도 Return을 계산할 수 있게 된다.

 

 

 

 

3. Asynchronous Advantage Actor Critic (A3C)

 

A3C network는 DQN의 확장 버전으로 생각해볼 수 있다.

연속적 action space, 이산적 action space 어디서든 잘 작동하고, 여러 agent들을 각각 복사된 environment에서 서로 다른 policy를 통해 독립적으로, 병렬로 학습시킬 수 있다.

예를 들어, 어떤 agent는 exploration 위주로, 다른 agent는 exploitation 위주로 학습시킨 후 합치는 것이다.

이렇게 개별적으로 학습된 agent들은 'global agent'로 합쳐진다.

global agent는 master network, global network 등으로도 불리며, 각각 학습된 agent들은 workers라고도 불린다.

 

이제 A3C의 동작 과정을 구체적으로 살펴보면서 DQN과의 차이점을 살펴보자.

 

 

 

 

1) first A - Asynchronous

 

'Asynchronous'는 사전적 의미로 '동시에 존재하지 않는'이라는 의미이다.

이는 곧 복사된 environment에서 각각 학습하는 agent들은 서로 독립적이라는 것을 말한다.

 

DQN에서는 하나의 agent가 학습을 진행하지만, A3C에서는 여러 agent가 독립적으로 학습을 진행한다.

 

 

 

 

2) second A - Advantage

 

두 번째 A는 Advantage Function을 말한다. ( \(Q - V\) )

앞서 policy를 \(\theta\)라는 weight로 parameterize하여 함수로 표현했다.

이러한 weight는 deep neural network의 학습 대상이 되고, 이에 따른 objective function \(J\)가 바로 Advantage Function이다.

 

 

 

 

3) third A and C - Actor Critic

 

마지막으로 A와 C는 Actor-Critic method를 의미한다.

아키텍쳐는 actor와 critic이라는 network로 나뉘는데, actor는 policy를 (직접적으로) 배우는 agent를, critic은 actor가 배운 policy가 얼마나 좋은지 평가하는 value function을 의미한다.

 

수식 기준으로는 다음과 같은 의미를 갖는다.

• Actor Network : DNN의 parameter \(\theta\)로 parameterize된 policy를 학습한다.
• Critic Network : \(\theta\)로 parameterize된 Value Function을 학습한다.

 

따라서, 이는 Dueling Network의 특성으로 볼 수 있다.

 

 

 

 

4) The Architecture of A3C

 

전체적인 A3C 아키텍쳐는 다음 그림과 같다.

 

Architecture of A3C

 

n개의 worker는 복사된 environment에서 policy를 학습하고, policy loss의 gradient를 계산하여 global network의 gradient를 update한다.

global network는 모든 agent(worker)에 의해 동시에 update된다.

 

DQN과 비교하여 중요한 특징 중 하나는, A3C는 experience replay memory(buffer)를 사용하지 않는다는 것이다.

각 worker들이 독립적으로 하습하기 때문에, experience 간의 상관 관계가 존재하지 않게 되므로 experience replay buffer가 필요 없고, 따라서 메모리 용량과 계산 시간이 절약된다.

 

 

 

5) A3C 특징 및 동작

 

A3C 방법의 장점은 다음과 같다.

• 독립적인 여러 기기와 파라미터 서버 대신, 한 기기 내에서 multiple CPU thread를 사용한다. 한 기기 내에서 여러 agent를 학습시킬 경우, gradient와 parameter를 보낼 때 발생하는 communication cost가 사라진다.
• 여러 actors-learners (workers)가 병렬적으로 (서로 다른 exploration policy로) 학습함으로써 environment의 여러 다른 부분을 explore 할 수 있게 된다.
• experience replay가 필요 없으므로, neural network 학습 시에 Sarsa, actor-critic 등의 on-policy reinforcement learning을 사용할 수 있다.

 

(참고로, on-policy는 하나의 policy로 학습을 진행하는 방법이고, off-policy는 target policy, behavior policy를 따로 두어 학습하는 방법이다.)

 

A3C 방법의 학습 순서는 다음과 같다.

1. worker agent가 global network를 리셋한 후, environment와 상호작용하며 학습을 시작한다.
2. 각 worker는 (일반적으로) 서로 다른 exploration policy를 사용하여 optimal policy를 학습한다.
3. value loss (critic)와 policy loss (actor)를 계산하고, 각 loss의 gradient를 계산하여 global network의 gradient를 update한다.
4. worker가 global network를 리셋하고 같은 과정을 반복할 때까지 위 과정을 반복한다.

 

그렇다면 value loss function과 policy loss function이 어떻게 계산되는지 살펴보자.

그 전에, advantage function이 어떻게 계산되는지 살펴볼 필요가 있다.

advantage function의 정의는 다음과 같다.

 

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

 

A3C에서는 Q value를 직접적으로 계산하지 않기 때문에, Q value를 추정하기 위해 discounted return을 사용한다.

 

\( R = r_n + \gamma r_{n-1} + \gamma^2 r_{n-2} \)

 

위 식의 return \(R\)은 two step을 살펴본 return으로, \(G_t\)에 해당한다.

이제 Q function을 discounted return \(R\)로 대체하면 다음과 같다.

 

\( A(s, a) = R - V(s) \)

 

이제, value loss를 계산한다. value loss function은 discounted return과 state value의 차의 제곱 합을 사용한다.

 

\( ValueLoss(L_v) = \sum \left( R - V(s) \right)^2 \)

 

그리고 policy loss는 다음과 같이 계산한다.

 

\( PolicyLoss(L_p) = Log \left( \pi(s) \right) * A(s) + \beta H(\pi) \)

 

여기서 \(Log\)는 log probability를 의미한다.

value loss, policy loss 모두 줄여야할 term이다. 따라서 policy gradient method에 따라 gradient descent 방법을 사용한다.

또한 \(H(\pi)\) term은 entropy term으로 다음과 같은 특징을 갖는다.

• entropy : 복잡도라는 의미를 갖고, \(\pi\)에 대한 entropy는 \(a\)가 선택될 확률의 분포의 복잡도를 의미한다.
• entropy 값이 커지면 분포가 펼쳐짐을 의미하고, entropy가 최대이면 모든 action이 선택될 확률이 동일함을 의미한다.
• entropy 값이 작아지면 특정 action이 선택될 확률이 높아지는 것을 의미한다. 작은 값일수록 action을 deterministic하게 선택할 수 있다.

 

따라서, policy loss 계산 시 entropy term을 더함으로써 agent가 더 explore하도록 할 수 있고, local optima에 빠지는 상황을 벗어나게 해준다.