오늘은 DQN 에 이어서 A3C 에 대해서 공부해보고자 한다. A3C 는 비동시적으로 여러 Actor 들을 두어서 학습의 병렬처리를 통하여 (일종의 Exploration) 데이터간의 상관관계를 끊고 효율적으로 학습을 진행하는 알고리즘이다.

DQN 에서는 Sequence 로 쌓이는 데이터를 그대로 학습에 사용하면 데이터간의 상관성 때문에 학습 자체가 모델이 편향되게끔 학습이 진행된다. 이건 신경망의 파라미터 업데이트 특성상 일어날 수 밖에 없는 숙명이다. DQN 에서는 이런 데이터 상관성을 끊기 위해서 Replay buffer 를 이용해 Experience 들을 쌓아두었다가 랜덤하게 샘플링해서 업데이트를 진행했다.

Q-Learning

이전에 학습한 DQN 을 one-step Q-learning 이라고 칭함. 왜냐하면, DQN 에서는 Q(s,a) 를 업데이트할때, 바로 다음 step 인 s' 에서의 보상을 기준으로 업데이트가 이뤄지기 때문임.

• 11번째 time-step 에서 얻은 큰 보상은 10번째 time-step 의 action-value 에만 영향을 주게끔 update 가 됨.
• 같은 sequence 에 있는 1~9번째 time-step 의 aciton-value 도 업데이트하기 위해서는 총 10번의 업데이트 과정이 필요하게 된다.
• 위와같은 이유로 (모든 시퀀스에 대한 업데이트가 따로따로 필요) one-step Q-learning

따라서, 업데이트 과정이 너무 느리다는 단점이 있다. 그래서 제안된게 n-step Q-learning. n-step 에 걸쳐서 action 을 취해보고 n개의 보상을 토대로 Q(s,a) 를 업데이트한다.

Policy Based Algo.

Policy Based model free 알고리즘으로는 REINFORCE 알고리즘을 소개하고있다. policy 를 parametrize (매개변수화) 해서 이를 학습해서 사용한다.

그럼 policy based 랑 value-based 의 차이가 무엇인가? 둘다 reward 를 이용해서 업데이트가 이뤄지는건 동일하다. policy based 의 경우에는 특정 state 에서 보상이 높았던 action 의 확률값을 높여주도록 업데이트를 하고, value based 는 특정 state 에서 보상이 가장 높았던 action 을 토대로 실제 기대보상을 업데이트한다.

Asynchronous

논문에서는 CPU 의 쓰레드 단위로 learner 를 두어서, exploration policy 를 달리함으로써 environments 의 다양한 부분을 탐색할 수 있게 되었다. 더불어, Single machine 을 사용함으로써 learner 들끼리의 communication 과정에서의 loss 도 최소화할 수 있었다.

• learner 들간의 communication 은 Gradient 값 공유 등을 의미한다.

Replay memory 를 사용하지 않고, on-policy 방식을 사용한다.

• DQN 논문의 경우, 수집된 데이터의 correlation 을 깨기 위해서 Replay memory 를 이용해 랜덤 샘플링을 통해 과거 데이터를 통해 학습을 진행했다.
• A3C 논문의 경우, CPU 쓰레드마다 learner 를 둠으로써, Parallelism 을 통해 데이터의 편향성을 막은 것이다.

이제 Asynchronous 를 적용시킨 다양한 Variants of Algorithm 들을 소개한다.

Asynchronous one-step Q-learning

CPU 의 각 쓰레드의 learner 들은 environments 의 copy 와 interact 를 하고, 각 time step 마다 Q-learning loss 의 gradient 를 계산하게 된다.

이렇게 계산한 gradient 는 바로 적용되지않고, accumulate 된 다음, 설정한 주기마다 네트워크를 업데이트하는데,

Gradient 를 모아서 업데이트를 하면, learner 들끼리의 파라미터 overwrite 를 방지하고, 학습 속도를 높일 수 있게 된다.

Asynchronous one-step Sarsa

Sarsa 알고리즘은 Q-learning 과 Target value 를 계산하는 수식에서 차이가 있다.

• Q-learning 은 off-policy 기반 알고리즘으로, 다음 state 에서 어떤 action 을 취했는가? 보다 가장 높은 value 를 가진 action 을 기준으로 업데이트가 이뤄진다.
• 반면에 Sarsa 는 on-policy 기반 알고리즘으로, 다음 state 에서 어떤 action 을 취했으며, 그 action 으로 얻은 보상을 기준으로 업데이트가 이뤄진다.

Asynchronous n-step Q-learning

n-step Q-learning 은 forward view 를 기준으로 적용되었다. forward view 는 time step 't' 로부터 't+1', 't+2', ... 't+n-1' 까지의 n개의 보상을 이용해 업데이트를 한다.

• momentum-based (관성에 힘을 싣어 gradient 를 업데이트하는 방법) 로 신경망을 update 하는 경우, forward view 가 학습이 더 쉽게 되었다고 함

Target Network 업데이트 과정에서는 n-step 임으로, n=4 일때 t, t+1, t+2, t+3 까지 time-step 을 밝게되고 각각 아래와 같은 방법으로 target 값을 계산하게 된다.

• t+3 시점 : 1-step Q-learning
• t+2 시점 : 2-step Q-learning
• t+1 시점 : 3-step Q-learning
• t 시점 : 4-step Q-learning

위와같이 n-step 에 걸쳐서 계산한 Target 값을 누적해주고, 이 값으로 딱 한번 Global Network 에 Gradient step 을 밟게 된다.

그리고 위 과정은 쓰레드마다 존재하는 learner 들에게 독립적으로, 비동기적으로 이뤄지게된다.

Asynchronous Advantage Actor-Critic (A3C)

A3C 도 마찬가지로 forward view 에 의해 동작작하고, n-step return 을 이용해서 policy 와 value-function 을 업데이트한다. (n-step Q-learning 과 동일)

업데이트 과정에서 Advantage 가 사용되는 것이 핵심이다.

$$\nabla_{θ'}log\pi(a_t|s_t;θ') \textcolor{blue}{A(s_t,a_t;θ, θ_v)}$$

• (참고: Policy based 의 REINFORCE 알고리즘은 아래와 같은 수식을 사용한다. Gradient 에 Reward 를 가중치처럼 곱해서 사용한다.

$$\nabla_{θ'}log\pi(a_t|s_t;θ) \textcolor{blue}{R_t}$$

Advantage 은 아래 수식에 의해서 계산된다.

$$\underbrace{∑_{i=0}^{k-1}γ^ir_{t+i} + γ^kV(s_{t+k};θ_v)}_{(1)} - \underbrace{V(s_t;θ_v)}_{(2)} \\ \rightarrow \underbrace{R_t}_{(1)} - \underbrace{V_t}_{(2)}$$

• (1) 은 Target 계산을 의미한다. n-step return 을 Discount Factor 를 이용해 가중합해주는 것이다. k번째 텀은 실제로 받은 보상(r) 이 아니라 기대되는 미래 보상을 추측한 값(V function) 을 사용한다.
• (2) 는 일종의 Baseline 의 역할을 하는 텀이다. Value function 자체를 baseline 으로 사용한다. (1) 에서 (2) 를 빼줌으로써 (like normalization) $s_t$ 에서 기대되는 평균적인 보상으로부터 얼마나 잘했는지 못했는지를 알 수 있다.
  • Gradient 의 변동성이 줄어든다는 장점이 있다.

Advantage 값을 계산하는 수식에서, θ 는 $r_{t+i}$ 와 $s_{t+i}$ 를 생성하기 위한 Policy 에 사용되는 파라미터이고, Value function 에 사용되는 $θ_v$ 는 \theta 와 분리되어 있는 것 같지만, 실제로는 서로 일부부을 공유하여 사용한다.

또, A3C 에서는 Entropy 이용한다. π (policy function) 의 Entropy ($H$) 를 목적함수에 넣어준다. 이를 통해 local optimal 에 수렴하는 것을 막을 수 있다고 한다.

일종의 Regularization Term 의 역할을 하며, 일반적인 머신러닝에서는 Lasso, Ridge 등 모델이 너무 복잡해지지 않게하기 위한 정규화를 적용한다면, RL 에서는 특정한 Action 의 확률을 100% 에 가깝게 설정되지 않게끔 막기 위해 정규화를 적용한다.

Entropy 를 적용한 수식은 다음과 같다.

$$\nabla_{θ'}log\pi(a_t|s_t;θ')(R_t-V_t) + \beta\nabla_{θ'}H(π(s_t;θ'))$$

Optimizer (해공간 탐색 함수) 로는 SGD with momentum , RMSProp, RMSProp with shared statistics. 3가지가 사용되었다.

• Shared Statistics 는 각 쓰레드에 있는 learner 들이 Gradient 를 공유해서 평균적인 Gradient 를 계산해, 평균적인 기울기를 구하고, 이를 반영해 업데이트를 진행하는 것을 얘기한다.
  • learner 끼리 Shared 할 수 있는 $g$ 라는 변수가 있고, 모든 learner 들은 업데이트 과정에서 다른 learner 들을 기다리지 않고, 계산한 gradient 에 제곱($g^2$) 을 씌워서 $g$ 변수에 누적해준다.
  • 제곱을 하는 이유는, Gradient 의 가파른 정도만을 확인하기 위해서이다.