Playing Atari with Deep Reinforcement Learning

논문 제목 : Playing Atari with Deep Reinforcement Learning(Submitted on 19 Dec 2013)

●  논문 저자 : Volodymyr Mnih (DeepMind)

●  논문 링크 : https://arxiv.org/pdf/1312.5602.pdf

●  이전에 보면 좋은 자료 :

○  Reinforcement Learning: An Introduction (Richard S. Sutton and Andrew G. Barto)

○  UCL Course on RL (David Silver)

●  함께 보면 좋을 논문 : Human-level Control through Deep Reinforcement Learning(2015) 

---

1  Abstract

• Reinforcement Learning(RL)을 이용하여 high-dimensional sensory input으로부터 control policies를 성공적으로 학습한 최초의 Deep Learning(DL) model을 나타내고 있다. 

• DL model은 Q-learning의 한 variant으로서 Convolutional Neural Network(CNN)을 이용한 model이다. 이 model의 input은 raw pixel이고, output은 앞으로의 reward를 평가한 value function이다. 

• Atari games 중에서 7개의 game 환경을 통해 이 방법을 적용했고, 7개 중 6개의 game에서 이전의 모든 접근들을 능가했고, 6개 중에서 3개는 game에서 인간을 넘어섰다.
  

---

2  Introduction 

• 이전까지 대부분의 성공적인 RL application들은 linear value functions 또는 policy representations를 가지는 hand-crafted feature들에 의존적이었다. 다시 말해 RL application의 performance는 feature representation의 quality에 따라 달라졌다. 

• 하지만 최근에는 DL의 발전으로 인해 computer vision이나 speech recognition에서 raw sensory data로부터 high-level features를 추출하는 것이 가능해졌다.

• RL에서 DL을 사용하기 위해서는 많은 문제들을 해결해야 한다.
1. Data를 사용하는 대부분의 성공적인 DL applications는 많은 hand-labelled training data를 통해 학습한다. 반면에 RL algorithm들은 대부분이 sparse하고 noisy하고 delayed하는 scalar reward signal로부터 학습할 수 있어야 한다. 
2. 대부분의 DL algorithm들은 독립된 data sample로부터 학습한다.  반면에 RL algorithm들은 전형적으로 연관되어 있는(correlated, continuous) 상태들의 순서들을 다룬다. 게다가 data distribution은 새로운 행동들을 학습하는 algorithm이기 때문에 변하고, 고정된 distribution을 다루는 DL method인 반면 RL algorithm에서는 문제가 될 수 있다. 

• 따라서 CNN이 복잡한 RL 환경들의 raw video data로부터 성공적인 control policies를 학습하는 것을 보였다. 
1. CNN을 이용한 이 Network는 weights를 업데이트하기 위해 Stochastic Gradient Descent(SGD)를 사용함으로써 Q-learning algorithm의 한 변종이라고 말할 수 있다. 또한 correlated data와 non-stationary distributions의 문제를 완화하기 위해서 experience replay mechanism을 사용한다. 여기서 experience replay mechanism은 이전에 학습한 data들을 저장하여 random한 sample로 사용하고, 그렇게 함으로써 training distribution이 smooth하도록 만드는 방법이다.

• 이 논문의 목표는 가능한 한 많은 game들을 성공적으로 학습할 수 있는 single Neural Network(NN) agent를 만드는 것이다. 이 NN은 어떠한 game-specific information 또는 hand-designed visual feature들을 제공받지도 않고, 내부적인 상태를 알고있지도 않는다. 단지 video input, reward, terminal signals, set of possible actions으로만 학습한다.

• 이 논문에서 쓰인 환경들은 Atari 2600 games이다. Atari 2600은 high dimensional visual input (210 x 160 RGB video as 60Hz)을 가진 agent들을 나타내고, 사람이 하기에도 어렵게 만들어진 RL testbed 환경이다. 

---

3  Background 

Atari 환경에 대한 설명과  현재의 하나의 image만 보고는 agent가 완전히 이해할 수 없기 때문에 sequences of actions and observations를 이용해야 하고,  Markov Decision Process(MDP) 방법을 통해 standard RL methods를 적용한다.  그리고 MDP에 이어서 gamma(discounted factor), return, action-value method(Q-function), policy(distributions over actions)를 설명하고 있다.

또한 Bellman equation과 Value iteration을 통해 다음과 같은 공식이 나온다. (Reference)

이 Bellman equation을 이용한 Loss Function은 다음과 같다.

여기서 y가 바로 (1)에 있는 Bellman equation이다. 

그래서 Gradient로 나타내면 공식은 다음과 같다.

마지막으로 Model-free RL과 Off-Policy에 대해 다룬다.

---

4  Deep Reinforcement Learning

  

이 논문의 목표는 RL algorithm을 SGD를 사용함으로써 효율적으로 training data를 처리하고 RGB images를 직접적으로 받아들이는 DNN으로 연결하는 것이다. 다시 말해 각각의 time-step에서 agent의 경험들을 저장한 experience replay을 이용한다.

이 알고리즘의 이름은 Deep Q-learning(DQN)이다.

- Deep Q-learning(DQN) Algorithm

1) 먼저 replay memory D와 이것을 얼마나 만들 것인지 임의의 capacity N을 초기화한다. (ex. 5000)

2) random weight들을 가진 action-value function Q를 초기화한다.

3) episode를 1부터 M까지 반복한다.

4) s1 = {x1}의 순서와 그것을 preprocessing(전처리)한 것을 초기화한다.

5) time-step인 t = 1부터 T까지 반복한다.

6) -greedy action selection을 통해 하나의 action을 선택한다.

7) action을 실행하고, reward rt와 next image xt+1를 받는다.

8) '현재 state st, 실행한 action at, next image인 xt+1'를 st+1이라고 하고, st+1에 대해서 preprocessing을 한다.

9) replay memory D에 전처리한 현재 state st, 실행한 action at, 받은 reward rt, 전처리한 next state st+1을 저장한다.

10) D에 저장한 sample들 중에서 minibatch의 개수만큼 random하게 뽑는다.

11) yj을 정의하는데, 전처리한 next state st+1에 대해서 목표지점을 도착하면 rj, 목표지점이 아니라면 rj+ gamma*max(Q)로 정의한다.

12) 앞서 봤던 (3)의 gradient 식에 따라 (yj-Q)^2를 Loss Function으로 두고 gradient descent한다.

13) 5~12)를 반복한다.

14) 3~13)을 반복한다. 

• Advantage
1. 각각의 step의 experience는 많은 weight updates에서 potentially하게 사용된다. 또한 더 나은 data efficiency를 가진다.
2. 계속 이어지는 sample들로 직접적으로 learning하는 것은 불충분하다. 왜냐하면 sample들 사이에 correlation(충돌)들이 많기 때문이다. 다시 말해 sample들을 random하게 뽑는 것은 이러한 충돌을 없애주면서 update의 변동을 줄여준다.
3. experience replay를 사용함으로써 parameter들이 '진동 or 발산'하는 것을 피하고, learning이 smooth해지기 때문에 behavior distribution은 이전의 많은 state들에 대해 average된다. 또한 experience replay로 learning할 때, off-policy로 학습하는 것이 필요하다. 왜냐하면 experience replay로 학습한 parameter들은 sample을 만들기위해 사용된 parameter들과 다르기 때문이다.

• Disadvantage
1. replay memory의 최대 용량까지 저장하고, 저장한 용량에서 random하게 뽑는다.  다시 말해 memory buffer가 중요한 transition(실행, 학습할 때 더 좋았던 state, action, reward, next state)들을 구별하지 않는다. 또한 finite memory size N 때문에 항상 overwrite(겹쳐쓰다, 덮어쓰다, minibatch로 뽑았을 때 남아있는 것들을 계속 겹쳐쓰고 덮어쓴다.)하기 때문이다.

4-1  Preprocessing and Model Architectrue

• Preprocessing 
1. 128 color palette를 가진 201 x 160 (x 3(channel)) pixel images인 raw Atari frames을 직접적으로 input으로 놓는 것은 계산하기에 너무 복잡하다. 그래서 먼저 input dimensionality를 줄이는 것을 돕는 basic preprocessing step을 적용한다. gray-scale과 100 x 84 image로 down-sampling하여 RGB값을 표현하는 것이다. 
2. 따라서 최종 image는 게임이 진행되는 부분만 보이는 84 x 84 (x 1(channel))로 잘라낸 부분만 보인다. 아까 살펴본 DQN Algorithm에서 전처리라는 것이 이 부분을 뜻하고 있다. 또한 하나의 image로 판단할 수 없기 때문에 가장 최근의 4 frames의 history만 전처리를 하여 input에 대한 Q-function의 값을 구하기 위해 전처리한 history를 사용한다. 

• Model Architecture : Q-value를 구하는 방법으로는 두 가지가 있다. 
1. history와 action을 DNN의 input으로 하고 output으로 그 history와 그 action에 대한 예측된 Q-value를 구하는 방법이다.
2. 다른 하나는 history만 input으로 하여 output으로는 각 행동에 대한 예측된 Q-value를 구하는 방법이다.

전자의 경우 단점이 있다. 그것은 바로 history에 해당하는 action들에 대해서 하나의 DNN으로 각각 분리된 forward 연산을 진행해야 한다는 것이다. 따라서 후자의 방법으로 사용할 것이며, 이 방법은 하나의 DNN을 통해 주어진 state에서 가능한 모든 action들에 대한 Q-value를 계산하기 때문에 좀 더 효율적이다.

• DNN의 Architecture
1. 전처리된 input은 84 x 84 x 4 image(4 frames)이다.
2. 첫 번째 hidden layer는 input image에 stride 4를 포함한 8 x 8  x 16 (8 x 8 filters, 16 channels)로 합성곱 연산을 하고, rectifier non-linearity(ex. relu)를 적용한다.
3. 두 번째 hidden layer는 stride 2를 포함한 4 x 4 x 32 (4 x 4 filters, 32 channels)로 합성곱 연산을 하고, 다시 한 번 더 rectifier non-linearity를 적용한다.
4. 마지막 hidden layer는 fully-connected를 하고, 256 rectifier units로 구성한다.
5. 최종적으로 output layer는 각각의 action의 Q-value값으로 fully-connected linear layer로서 DNN의 구조가 끝난다.

---

5  Experiments

• Experiments를 살펴보기전에 먼저 algorithm 및 hyper-parameters에 대한 세 가지 settings가 나온다.
1. reward structure :  먼저 training하는 동안 reward structure에 한 가지 변화를 준다. 모든 positive rewards는 1로, 모든 negative rewards는 -1로 고정시키는 것이다. 이렇게 reward를 고정시키는 이유는 loss function으로 gradient를 할 때 derivatives의 error의 scale을 제한하고, 많은 game들 사이에 같은 learning rate를 사용하는 것을 더 쉽게 만들기 때문이다. 
2. RMSProp Algorithm & -greedy : 이 논문에서는 32 size를 minibatches로 하는 RMSProp algorithm을 사용한다. 또한 training동안 behavior policy는 처음 million frames에 대해서 을 1과 0.1사이로 하는 -greedy 방법을 사용하고, 그 후에 은 0.1로 고정시킨다. 그래서 총 10 million frames로 학습을 시켰고, buffer의 최대 용량은 one million으로 가장 최근의 frames를 가지는 replay memory이다.
1. Frame skipping technique : agent는 모든 frame 대신에 모든 임의의 k번째 frame통해 action들을 선택한다. 따라서 one step에 대한 running은 agent가 하나의 action을 선택하는 것보다 훨씬 덜 computation을 필요로 할 것이기 때문에, 이 technique는 run time의 증가없이 대략 k배 game을 더 실행한다. 다시 말해 k가 4라면 연속된 4개의 화면 중에서 3개의 화면은 frame skip을 통해 건너뛰고 나머지 하나의 화면만 실제로 사용된다는 의미이다. 이 논문에서는 k = 4로 사용되었다. 하지만 Space Invaders game에서는 laser가 깜박이는 시기가 있기 때문에 k = 4로 하면 laser가 안보일 수 있다. 따라서 Space Invaders game은 k = 3으로 하여 실행하였다. 

5-1  Training and Stability

Figure 2 : 왼쪽 두 그림은 Breakout과 Seaquest game에서 episode 마다 계산된 average reward를 보여준다. 총 10000 steps에 대해서는 을 0.05를 사용하여 running했다. 오른쪽 두 그림은 action-value를 예측한 average maximum을 보여준다. 하나의 epoch은 50000 minibatch weight updates에 해당하거나 training time이 대략 30분정도 된다.

• 이 논문에서는 evaluation metric이 agent가 하나의 episode 또는 많은 games에 대한 averaged game에서 모은 total reward이기 때문에 training동안에 모은 total reward를 주기적으로 계산해야한다. 따라서 기본적으로 쓰이는 average total reward metric은 때때로 굉장히 noisy하다. 왜냐하면 하나의 policy의 weight들의 작은 변화들이 state의 분포에서는 큰 변화들로 이끌 수 있기 때문이다. 위의 가장 왼쪽 두 가지 그림이 바로 noisy하다는 것을 보여주고 있습니다. 그렇기 때문에 average total reward metric으로 평가할 경우 정확한 지표가 되지 못한다. 

• 따라서 더 안정적인 또 다른 metric은 policy's estimated action-value function Q이다. 이 Q-function은 agent가 주어진 state에서 policy로부터 얻을 수 있는 reward를 얼마나 많이 discounted할 수 있는지에 대한 평가이다. 가장 오른쪽 두 그림은 바로 Q-function을 예측한 average가 앞써 다뤘던 average total reward보다 훨씬 더 smooth하게 증가한다는 것을 보여주고 있다. 

5-2  Visualizing the Value Function

Figure 3 : 가장 왼쪽 그림은 30 frame동안 예측된 value function이다. 나머지 그림들은 A, B, C로 label된 frame들이다. 

• 위의 가장 왼쪽 그림은 학습된 value function을 그래프이다. A의 그림에서 예측된 value가 높아졌고, torpedo로 공격하여 적을 사살하고 있는 B의 그림에서 예측된 value가 가장 높았다. 그리고 C의 그림에서 적이 사라졌기 때문에 value가 떨어진 것을 볼 수 있다. 

5-3  Main Evaluation

Table 1 : 위의 표는 을 0.05으로 하여 -greedy policy로 running한 다양한 learning methods에 대한 average total reward를 비교한 것이다. 아래의 표는 HNeat와 DQN에 대해 가장 episode 실행이 좋았던 결과를 나타낸 것이다. HNeat는 항상 같은 score를 얻는 deterministic policy들을 만들었고, 반면에 DQN은 을 0.05으로 하여 -greedy policy를 이용했다.

• Random : 말 그대로 아무런 알고리즘 없이 랜덤으로 running 했을 때 최고로 높은 점수를 받은 것이다.

• Sarsa : 기본적인 Sarsa Algorithm이지만 input data을 만들기 위해 hand-engineered feature로 linear policies를 학습시킬 수 있는 Sarsa Algorithm이다.

• Contingency : Contingency같은 경우  Sarsa와 같은 접근이지만 다른 점은 feature sets를 증가시킨 것이다.

하지만 Sarsa나 Contingency의 경우 hand-engineered로 하기 때문에 background subtraction을 사용하고 하나의 분리된 channel로서 각각 128 colors로 다루기 때문에 visual problem을 포함하고 있다. 

• HNeat Best : HNeat Best score는 Atari 화면에서 object들의 type들과 location들을 output으로 하는 hand-engineered object detector algorithm을 사용하여 얻은 결과이다.

• HNeat Pixel : HNeat Pixel score는 각각의 channel에서 object label map을 나타내는 Atari 게임의 special 8 color channel를 사용하여 얻은 결과이다. 이 방법의 경우 state들의 하나의 deterministic sequence를 찾아내는 것을 더 중요시하는 방법이고, random한 pertubation들을 generalize하는 것과는 다르다.

• DQN : DQN의 경우 3가지 games(Breakout, Enduro, Pong)을 제외하고는 사람을 뛰어넘지는 못했지만 이전의 방법론들을 뛰어 넘은 performance를 나타내고 있다.

---

6  Conclusion

• 이 논문은 RL에 대해 새로운 DL model을 소개했다. 이 DL model은 RL에 적용한 deep networks를 training 하는데에 더 편안하게 하기 위해 experience replay를 두었고, experience replay를 통해 stochastic minibatch update를 하는 online Q-learning의 하나의 variant이다. 

• 또한 이 논문의 연구는 7가지의 게임 중 6가지에서 state-of-the-art results를 나타냈다.