Anticipatory Asynchronous Advantage Actor-Critic (A4C)

논문 제목 : Anticipatory Asynchronous Advantage Actor-Critic (A4C)

●  논문 저자 : Tharun Medini

●  논문 링크 : 

○ ICLR 2018 Conference Withdrawn Submission (Reject)

○ ICLR 2018 Workshop Submission (Reject)

●  이전에 보면 좋은 논문 :

○  Asynchronous Advantage Actor-Critic (A3C)

○  GA3C: GPU-based A3C for Deep Reinforcement Learning

---

Abstract

기존의 Deep Reinforcement Learning(Deep RL)에 확장하여 추가적으로 Policy의 한 부분으로써 행동들의 순서들을 고릅니다. 다시 말해 Neural Network(NN)가 행동 순서들의 보상을 예측합니다. 이 논문에 따르면 이러한 방법은 더 좋은 convergence으로 이어지는 exploration을 향상시킨다고 합니다. 또한 이 방법은 simple하고 flexible하다고 합니다. 

그럼 Introduction부터 자세히 살펴보겠습니다.

---

1  Introduction

Slow Progress with Deep RL : 현존하는 Deep RL 알고리즘들은 좋은 performance가 나오기에 굉장히 많은 학습 시간이 걸립니다. 왜냐하면 초기의 경험이 매우 낮은 보상을 가진 random한 행동들의 순서들이기 때문입니다. 즉, poor exploration때문에 느린 학습의 원인이 됩니다.

특히 NN이 수렴하기에 오래걸리고 움직였던 행동이 random할 때, exploration을 통한 좋은 행동의 순서를 찾는 것은 굉장히 오랜시간이 걸립니다. 

Introduce Method : 따라서 이 논문의 방법을 간략히 소개해보면, 먼저 NN이 {a1, a2, a3, ...}와 같은 순차적인 행동들을 포함한 enlarged action space에 대해 보상들을 예측하도록 합니다. 그래서 Deep RL Framework가 하나의 state  St에 대해서 미리 정한 행동의 순서들을 취하도록 합니다. 즉, 하나의 행동의 순서에 대한 예측된 보상이 충분히 좋다면, 이 알고리즘은 다음의 최적의 행동 대신 행동들의 하나의 순서를 미리 결정할 수 있다는 것입니다.

---

2  Background

이 논문은 아래와 같은 Method들을 안다는 가정하에 설명을 하고 있습니다. 

- Value-based Methods

- Policy-based Methods

- Actor-Critic Methods

- Asynchronous Advantage Actor-Critic (A3C)

- GPU enabled A3C (GA3C)

---

3  Our Proposal : A4C

먼저 예측하기 위해서 basic action set A에서 enlarged action space A+로 확장합니다. 그리고 A+은 Length K까지 행동들의 순서를 포함합니다. 만약에 A = {L, R}, 2-step anticipation(K = 2)이 있다면 A+ = {L, R, LL, LR, RL, RR}이 됩니다. A+에 속하는 각각의 a+들을 바로 meta-action이라고 부릅니다. 그리고 meta-action들은 L, R과 같은 single basic action과 행동들의 하나의 순서를 포함하고 있습니다.

전형적인 Deep RL 알고리즘들은 estimated Q-values 또는 policy distributions들을 output으로 하는 Deep Neural Network(DNN)를 가집니다. 이 논문에서도 마찬가지로 DNN을 가지지만, output으로 enlarged action set A+에서 각각의 meta-action에 대한 값들을 두고 있습니다. 

---

3-1  Intuition

이 논문에서는 meta-action을 설명하기 위해 먼저 인기게임 중 하나인 'Counter Strike'의 예로써 Combo에 대해 말하고 있습니다. single actions(ex. 주먹, 발차기)보다는 several of common actions(ex. 주먹-발차기, 발차기-주먹)이 더 강력할 수 있다고 합니다. 이러한 예시는 combo의 potential을 exploration하는 데에 도움을 준다고 합니다.

또한 행동들의 순서에 대한 예측의 장점은 Multi-task Learning과 Generalization과 관련되어 더 좋은 Parameter Sharing을 한다는 것입니다. 

Parameter Sharing : sharing하는 여러 task들은 NN을 generalization하기에 더 좋습니다. 또한 mate-action을 추가하기 때문에 Parameter Sharing은 NN의 layer가 최적의 행동을 예측하기에 유용할 뿐만 아니라 meta-action들의 적합성도 예측하도록 할 것입니다.  

Figure 1 : Enlarged action set {L, R, LL, LR, RL, RR}을 가지는 Anticipatory Deep Q-Network(ADQN)에 대한 toy example

이 그림에서 검은색 박스의 parameter들은 basic action들 뿐만 아니라 meta-action들의 gradient로부터 동시에 학습되어 sharing하는 representation입니다.

Anticipatory Deep Q-Network : 이 논문은 A4C를 보여주기 전에  먼저 DQN에 anticipation을 추가한 ADQN에 대해 말하고 있습니다.

방법은 간단합니다. ADQN은 enlarged action space에서 각각의 meta-action에 대한 Q-value를 output으로 하는 DNN입니다. 예를 들어, Cartpole game에서 basic action들의 집합인 A = {L, R}입니다. 따라서 만약 K = 2라고 한다면, A+ = {L, R, LL, LR, RL, RR}으로 나타낼 수 있습니다. 

학습을 시작하면서 state St에 대해 두 가지 업데이트를 할 수 있습니다. 

이 Update는 각각의 state에 대해 두 가지 gradient update를 진행하고, NN이 각각의 meta-action에 대해 Q-value를 output으로 하도록 만듭니다.

---

3-2  Anticipatory Asynchronous Advantage Actor-Critic (A4C)

하지만 DQN은 start-of-art algorithm이 아닙니다. 왜냐하면 수렴하기에 너무 복잡하기 때문입니다. 따라서 이 논문에서는 simplicity와 generality때문에 anticipation을 A3C에 적용합니다.

이 논문은 Anticipation을 강화하기 위해서 다른 NN의 architecture로 바꾸는 것없이 layer에서 policy node의 수를 확장합니다. 

A4C 알고리즘에서 NN은 두 가지로 사용됩니다. Prediction & Training

A4C는 NN의 output이 meta-actions인 A+의 하나의 분포로 나오도록 합니다. 그리고 각각의 state에서 output 분포에 따라 하나의 meta-action을 고릅니다. 그 다음으로 그 고른 meta-action의 순서대로 실행합니다.

A4C는 A3C의 strict generalization이기 때문에 주어진 action-reward frame에 대해 세 가지 gradient update가 있습니다.

세 가지 gradient update는 바로 Dependent Updating(DU), Independent Updating(IU), Switching입니다.

이 세 가지 gradient update에 대해서 자세히 살펴보도록 하겠습니다.

---

 3-2-1  Dependent Updating(DU)

meta-action 중 하나의 원소는 single action의 조합일 것입니다. 그리고 각각의 meta-action들은 dependent basic action을 가질 것입니다.

DU는 meta-action을 취하여 reward를 얻을 때, 우리는 이 meta-action에 대해 gradient를 계산할 뿐만 아니라, 그 meta-action과 일치하는 basic actions에 대해서도 gradient를 계산할 것입니다.

만약 {s0, a0, r0, s1, a1, r1, s2, ...} 가 있다고 하고 2-step anticipation까지 생각한다고 하면, s0에서 {a0} 뿐만 아니라 {a0, a1}도 업데이트를 할 것입니다.  따라서 우리는 Dependent Updating이라고 말할 수 있습니다. 

- Dependent Updating(DU) Algorithm

# DU 알고리즘 설명

1) 먼저 global shared parameter vector와 thread-specific parameter vector를 가정합니다. 또한 global shared T = 0으로 초기화합니다.

2) 그리고 basic set A와 enlarged action set A+를 정합니다.

3) 모델 업데이트 주기인 t를 t= 1로 초기화합니다.

4) policy와 value gradient를 0으로 reset합니다. 그리고 모든 thread-specific parameter vector들을 global shared parameter vector와 동시에 같도록 만듭니다. 그리고 state St에 대해서 다음과 같이 진행합니다.

5) policy distribution에 따라 하나의 a+(meta-action)를 고릅니다. a+에 해당하는 행동의 순서인 {a1, a2, ...}에서 하나의 basic action을 꺼내어 그 action을 수행하고, reward를 받고, 새로운 state St+1를 수행합니다. 그리고 t = t+1, T = T+1을 합니다.

6) 5)를 state St가 도착지점이거나 임의로 정한 tmax를 넘을 때까지 계속 반복합니다. 

7) R의 값을 구합니다. 만약 state St가 도착지점이라면 0, 아니라면 state St에 대한 state-value function인 V(Baseline)를 R로써 정의합니다.

8) 앞써 실행했던 time step의 개수의 순번을 i로 하고, i의 순번대로 받았던 reward + gamma(Discount Factor) * R을 하여 새로운 R로 정의합니다.

9) i부터 min(i+K, t-1)까지의 개수의 순번을 j로 하고( min(i+K, t-1)이기 때문에 tmax는 넘지 않습니다. ), 실행했던 모든 action에 대한 meta-action들을 aij이라고 하고, aij를 차례대로 gradient 식에 대입하여 thread-specific의 policy parameter vector로 gradient합니다. (실행했던 모든 action들을 i, j에 따라 aij의 output을 이용하여 gradient합니다. 각각의 meta-action들이 dependent meta-action으로 볼 수 있기 때문에 DU라고 할 수 있습니다.)

10) 9)에서 j의 순번이 끝날 때마다 thread-specific의 value parameter vector로 gradient합니다.

11) gradient한 것을 이용하여 global parameter vector로 asynchronous update를 합니다. ( 4)에서  global parameter vector를 thread-specific parameter vector들과 같게 하기 때문에 다시 역으로 update가 됩니다.)

12) 4~11)를 임의로 정한 global shared Tmax까지 진행합니다.

---

3-2-2  Independent Updating(IU)

IU는 각각의 독립된 action으로서 하나의 meta-action인 a+를 독립적으로 볼 수 있습니다. a+의 reward는 a+에 있는 모든 basic action을 위하는 reward의 합입니다.

따라서 IU는 Update동안에 meta-action들 사이에 dependencies와 relation에 관계없이 reward와 a+의 다음 state의 정보를 사용할 것입니다.

- Dependent Updating(DU) Algorithm

# IU 알고리즘 설명 

거의 DU 알고리즘과 똑같습니다. 다른 점만 살펴보면 다음과 같습니다.

- 다른 점 1

5) policy distribution에 따라 하나의 a+(meta-action)를 고릅니다. 

6) a+에 해당하는 행동의 순서인 {a1, a2, ...}에서 하나의 basic action을 꺼내어 그 action을 수행하고, reward를 받고, 새로운 state St+1를 수행합니다. 

7) 6)이 끝나면, a+에 대해 받았던 reward를 합치고, a+에 있던 basic action 순서의 횟수만큼 new state를 증가시킵니다. 그리고 t = t+1, T = T+1을 합니다.

8) 5~7)을 state St가 도착지점이거나 임의로 정한 tmax를 넘을 때까지 계속 반복합니다. 

- 다른 점 2

9) 앞써 실행했던 time step의 개수의 순번을 i로 하고, i의 순번대로 받았던 reward + gamma(Discount Factor) * R을 하여 새로운 R로 정의합니다.

10) 실행했던 각각의 meta-action들을 순서대로 ai이라고 하고, ai를 차례대로 gradient 식에 대입하여 thread-specific의 policy parameter vector로 gradient합니다. (실행했던 각각의 meta-action들을 i에 따라 ai의 output을 이용하여 gradient합니다. 각각의 meta-action들이 Independent meta-action으로 볼 수 있기 때문에 IU라고 할 수 있습니다.)

11) thread-specific의 value parameter vector로 gradient합니다.

IU는 meta-action의 본질적인 관계에 대한 추가적인 정보를 사용하지 않기 때문에 DU보다 less aggressive update라고 할 수 있습니다. 하지만 우수한 performance를 보였습니다. 그 이유는 high reward들을 일정하게 산출하는 action들의 다양한 패턴들이 존재하였고, anticipatory action space는 Network가  다양한 종류의 action 패턴들을 exploration하도록 만들었습니다.

---

3-2-3  Switching

DU-A4C는 다양한 Atari game에서 original A3C보다 짧은 학습 시간동안 더 빠르게 수렴하고, speed면에서도 더 큰 차이를 보입니다. 그러나 긴 학습 시간이라면 aggressive update(즉, DU)는 Network가 더 빨리 saturate(포화)되도록 유발합니다. (그렇기 때문에 IU로 switching하여 aggressive update로 인해 saturate되는 것을 막는 것입니다.) 이러한 현상은 Stochastic Gradient Descent(SGD) updates와 유사합니다. 그리고 SGD의 초기의 update도 aggressive합니다. 그러나 매 시간마다 learning rate를 decay하기 때문에 lee aggressive update로 바뀝니다.

정리해보면, 처음에 DU로 시작하여 aggressive update로 학습을 하다가 어느정도 시간이 되면 IU로 바꿔서 less aggressive update로 바꾸는 것입니다. 왜냐하면 DU는 anticipatory actions으로 부터 얻는 정보를 잘 사용하고 빠른 수렴을 산출하는 반면, IU는 update에 대해 less aggressive 방법을 사용하지만, 긴 학습 시간에 대해 growth를 지속시킵니다. 그렇기 때문에 이 논문에서는 이 두 가지 update 방법의 장점을 결합한 switching 방법을 제안합니다.

Switching is simple : 방법은 다음과 같습니다. 첫 번째로 일정 시간동안 NN을 학습시키기 위해 DU 방법을 사용합니다. 그리고 나서 IU 방법으로 switching을 합니다. 두 방법 모두 NN이 같기 때문에, switching 과정은 별로 큰 신경을 쓸 필요는 없습니다. 또한 switching은 전형적인 NN training에서 epoch을 가진 learning rate를 decaying하는 것과 유사합니다. 이 논문에서의 접근과 learning rate decay의 차이점은 learning rate decay는 soft reduction인 반면, switching 방법은 hard reduction이라는 것입니다.

까다로운 부분은 역시 우리가 switching을 언제 해야하는지입니다. 실제로, 언제 switching을 하는지는 heuristic 방식에 가깝습니다. 논문에서는 half-way 방법으로 switching을 합니다. half를 고른 이유는 first half에서 빠르게 수렴하기 위해서 DU를 이용하고, second half에서는 IU를 이용하여 aggressive update에서 less aggressive update로서 안정화되고 계속 growth(higher score)를 유지할 수 있기 때문입니다.  

논문의 저자는 연구을 해보면서 다양한 switching point의 선택을 통해 robust performance가 나오도록 해봐야할 것 같다고 합니다.

---

4  Evaluations

4-1  Study of Exploration using Cartpole Game

Figure 2 

Left : Cartploe game에서 실행한 ADQN vs DQN

Right : total 5000 episodes를 5 stage로 나눠서 실행한 action distributions

Left :  Cartpole game은 2 basic action(L, R)을 가집니다. 왼쪽 그림은 DU를 이용하여 2-step ADQN과 general DQN을  비교하고 있습니다. 그림에서 볼 수 있듯이 value-based RL에서도 anticipation의 좋은 점을 보여주고 있습니다. 

Right : 오른쪽 그림은 다른 learning period에서 6 meta-action의 probability (frequency) distribution을 나타냅니다. Basic action들의 확률은 learning을 하면 할수록 증가하고, multi-step action의 확률은 떨어집니다. 이러한 경우는 multi-step action이 초기에 agent가 탐험하기에 더 좋다는 것을 보여줍니다. 그리고 episode가 증가할수록 basic action을 유일하게 선택할 것입니다.

---

4-2  Atari Games

Figure 3 : GA3C와 A4C의 세 가지 변종의 비교. Switching time은 각각 실행에서 다릅니다. 그리고 대략적으로 가리키는 switching time을 표시했습니다. Atari game 중 대표적으로 인기있는 네 가지 game인 Pong, Qbert, BeamRider, SpaceInvader을 A4C로 학습시켰습니다. 

논문에서는 gradient의 minimum training batch size, max norm(clip gradient라면 default로 Max Norm=40), learning rate, switching을 시작하는 time instant와 같은 다양한 hyperparameter값을 가지고 연구를 했습니다. 위의 보이는 그림들은 optimal setting입니다.

그림을 보면 IU는 Qbert game을 제외하곤 모든 경우에서 AG3C보다 더 좋은 결과를 나타냅니다. DU 방법 또한 GA3C보다 더 빠르게 증가합니다. 하지만 3-2-3에서 DU 방법으로 계속 학습하면 aggressive update 때문에 NN이 더 빨리 포화되도록 유발된다는 점때문에 growth를 잘 유지하지 못합니다. DU가 growth한 유일한 case는 Pong game입니다. 

Hybrid Switching Method(sw)는 GA3C의 가장 좋은 score보다 higher scores를 만들면서 모든 게임에서 일관되게 잘 수행합니다. 그러나 Beam Rider와 Space Invaders game에서 IU보다 뒤쳐집니다. 합쳐서 IU가 2 game에서 좋은 반면에, 짧은 학습 시간에 DU와 IU의 Switching은 가장 robust 방법이라고 할 수 있습니다.

---

5  Atari Games

이 논문은 현재 가장 좋은 GA3C 방법에서 anticipatory action을 추가하여 간단하지만 아직은 덜 효과적인 기술을 제안했습니다. 그리고 여러 인기있는 Atari game에서 전반적으로 scores를 성취했고 수렴하는 데에 있어서도 중요한 발전을 하였습니다. 

또한 higher order actions에 대한 범위가 있었습니다. 하지만 action space는 지수적으로 anticipation의 order를 증가시킵니다. 따라서 larger action space를 다루는 것은 더 연구해야 할 사항으로 남아있다고 합니다.