[논문] Playing Atari with Deep Reinforcement Learning

Abstract

• RL을 사용해 high-dimensional sensory input으로 부터 directly control policies를 배운것을 성공한 첫번째 deep learning Model
• Model : DQN, 변형된 Q-Learning으로 학습한 CNN
• Input : raw pixels
• output : Value function (미래의 reward를 추정)

7개의 Atari 2600 game에 적용했다. Learning algorithm or Architechture를 변경하지 않음

결과로 6개의 게임에서 이전의 모든 접근 방식을 능가했고 그 중 3개의 게임은 전문가보다 더 나은 성능을 보여줌

1. Introduction

• Vision and Speech와 같은 high-digemsional sensory input으로부터 직접 agent control하는 것을 학습하는 것은 RL의 오랜 도전 과제였다.
• 이 분야에서 성공한 대부분의 RL은 hand-crafted features (linear value function or policy representations)에 의존했다. 이러한 시스템은 feature representation의 품질에 매우 의존한다.

최근 DL에서의 발전은 raw sensory data에서 high-level features를 얻는 것이 가능하게했다. 그리고 이것은 computer vision과 speech recognition의 한계를 돌파하게 했다.

이러한 발전은 CNN, multilayer perceptrons, Boltzmann machines 그리고 RNN, supervised, unsupervised learning등 다양한 기법들이 탄생하게 했다.

⇒ 이러한 방법들이 RL에서도 도움이 될까?

RL에 DL방식들을 적용하기에는 몇가지 문제점들이 있었다.

1. 대부분 성공한 DL applications는 엄청난 양의 hand-labelled 훈련 데이터를 필요로했다. 반면 RL은 sparse, noisy, delay된 scalar reward signal을 통해 배울수 있어야한다.
   • action과 reward사이의 delay는 수천의 step이 걸릴 수 있다. 이것은 지도학습에서 볼 수 있는 input과 target간의 직접적인 연관성과 비교했을 때 더 어렵게 느껴진다.
2. 대부분의 DL 알고리즘은 data sample이 독립적이라고 가정한다, 하지만 RL에서는 매우 연관된 State의 Sequences 이다.
3. RL에서는 알고리즘이 새로운 행동을 학습함에 따라 데이터 분포가 변하기 때문에, fixed underlying distribution을 가정하는 딥러닝 방식을 적용할 때 문제를 일으킬 수 있다.

이 논문은 CNN이 복잡한 RL 환경에서 raw video data로 부터 성공적으로 policy를 control 하는 것을 학습해 이러한 문제를 극복할 수 있다는 것을 설명한다.

1. 이 네트워크는 SGD(stochastic gradient descent)으로 weight를 업데이트 한 변형된 Q-learning으로 훈련했다.
2. correlated data\(_{(2)}\)와 non-stationary distribution\(_{(3)}\)의 문제를 완화하기 위해, 우리는 Experience Replay Mechanism을 사용한다. 이 메커니즘은 이전의 transition들을 무작위로 샘플링하여, 여러 과거 행동에 걸쳐 학습 분포를 부드럽게 만든다.

---

위 방법으로 Atrai 2600 Game에 적용했다.

목표

• 가능한 많은 게임을 성공적으로 플레이 할 수 있는 single neural netwrok agent를 만드는 것

방법

• 네트워크에 어떤 게임 특화적인 정보나 hand-designed visual features를 사용하지 않는다.
• 어떤 emulator의 state도 모르고, input, reward signal, terminal signal, actions들로만 학습
• 네트워크 아키텍쳐와 하이퍼 파라미터는 모든 게임에서 같았다.

결과

• 7개 게임중 6개 게임에서 기존의 RL 알고리즘 성능을 넘어섰다.
• 그중 3개의 게임은 사람(전문가)를 넘어섰다.

2.Background

formalism : large but finite Markov decision process (MDP)

• environment : \(E\) (stochastic)
• observation : partially observed
• state : vector of raw pixel values (images_
• action : \(a_t\) ( A = {1, … ,K) )
• reward : \(r_t\)
• discount factor : \(\gamma\)

agent의 목표 : emulator와 상호작용을 통해 action을 골라 미래의 reward maximises

Optimal action-value function은 Bellman euqation으로 구할 수 있다.

\(r + \gamma Q^*(s',a')\)를 최대로 하는 action을 선택한다.

value iteration algorithm을 사용하면 \(Q_i → Q*\) as \(i → \infty\)에 optimal으로 수렴을 보장할 수 있다.

하지만 이 방식은 일반화 없이 매 sequence action-value function을 추정해야 하므로 비효율적이다.

대신 function approximator를 사용해 action-value function를 근사할 수 있다.

RL에서 주로 linear function approximator를 사용하지만 가끔 neural network 같은 non-linear도 사용을 하고, 이 논문에서는 Q-network라고 부른다.

Q-network는 loss function \(L_i(\theta_i)\)를 최소화 하게 함으로써 학습할 수 있다.

전체 기대값을 다 계산하는 것 보다 SGD를 사용해 loss function을 최적화하는게 계산비용적으로 맞다.

만약 가중치가 매 step마다 업데이트가 되고, 기댓값이 행동 분포 P, emulator E로부터 단일 샘플로 대체된다면 Q-learning 알고리즘이다.

이 알고리즘은

• model-free이다. E의 estimate를 학습하는게 아니라 sampling을 사용해 학습한다.
• off-policy이다. greedy 방식으로 학습을 하고, \(\epsilon\)-greedy 방식을 사용해, 적절한 exploration을 활용한 behavior distribution을 따른다.

3. Related Work

RL에서 가장 성공한 것으로 알려진 것은 TD-gammon이다.

backgammon을 RL, self-play로 학습했고 사람의 실력을 뛰어넘었다.

TD-gammon은 Q-learning으로 비슷하지만 multi-layer perceptron을 approximate할 때 사용했다.

TD-gammon은 체스,바둑과 같은 게임에선 성공하지 못했다. backgammon같은 특수한 경우에만 유효했다. (주사위를 통해 stochasticity하게 state를 explore하는게 value function을 smooth하게함)

Q-learning같은 model-free를 (혹은 off-policy까지) non-linear function approximator와 결합을 하면 Q-network가 발산하는 문제가 있었다. 그래서 보통 linear function approximator가 수렴성을 보장하기 때문에 사용했다.

최근 다시 딥러닝과 RL의 결합을 연구하면서 gradient temporal-difference 방법을 통해 고정된 policy와 non-linear function approximator를 결합해도 수렴한다는 것을 증명했다.

앞선 연구중에 가장 비슷한 것이 NFQ(Neural Fitted Q-learning)이다.

NFQ는 RPROP 알고리즘을 사용해서 Q-network를 업데이트하지만 batch update를 사용함으로써 높은 computational cost를 가지고 있다. 또한 DQN과 다르게 deep autoencoder를 사용해서 이 task의 representation을 먼저 학습하기 때문에 end-to-end RL인 DQN과는 차이가 있다.

4. Deep Reinforcement Learning

목표 : RL 알고리즘을 RGB 이미지를 직접 처리하는 심층 신경망에 연결하고 stochastic gradient updates를 사용해 효율적으로 학습 데이터를 처리하는 것이다.

Experience replay의 사용

• time-step마다 에피소드 $e_t = (s_t, a_t, r_t, s_{t+1})\(를 Data-set\)D = e_1, … , e_N$$에 저장한다.
• mini batch update로 D에서 sample 하나를 뽑는다.

Experience replay후에는 \(\epsilon\)-greedy 방식을 통해 state space를 탐색한다.

이것이 이논문이 제시하는 DQN 방식이다.

DQN이 기존의 Q-Learning보다 나은 점

1. 매 단계의 경험이 재활용이 될 수 있다 → 데이터 효율성이 좋다.
2. 연속적인 sample 간의 강한 상관관계를 깰수있다. → 분산을 줄일 수 있다.
3. on-policy에서 파라미터의 학습이 진행되고 샘플링을 하면 파라미터가 편향될 수있다.
4. off-polcy의 사용→ 파라미터의 진동 혹은 발산을 피할 수 있다.

Experience Reply로 학습을 하면, Off-policy를 사용해야한다. (현재의 파라미터는 sample을 발생시키는데 어렵다\(_{(3)}\)) 이것이 Q-learning을 선택하게된 동기였다.

지난 \(N\)개의 경험만 메모리에 저장하고, update할때는 D에서 균일한 랜덤으로 sampling 한다.

이 방법도 제한점이 있다.

1. 메모리 버퍼는 중요한 transitions을 구분하지 못한다. 그리고 유한한 메모리 사이즈 N때문에 항상 덮어 쓰여진다.
2. 모든 sampling은 동등한 중요도를 갖는다.

이러한 문제의 대안으로는 Priortized sweeping 같은 방법이 있다.

Algorithm

4.1 Preprocessing and Model Architecture

input의 계산량을 줄이기 위해서 기본적인 전처리 과정을 거친다.

1. RGB → gray-scale (210 X 160)
   1. 차원수 3 → 1
2. down-sampling images (110 X 84)
3. cropping images to 84 X 84
   1. 2D convolutions은 정사각형을 input으로 해야함
4. stack 4 frames image : Q-function의 input으로 한다.

Q를 neural network로 구하는 방법 여러가지가 있다.

첫번째 방법은 image와 action을 neural network에 넣어서 Q값을 구하게 하는 방법이다.

이 방법의 문제는 각각의 action마다 forward pass를 실행해야하기에 계산량이 action 수에 linear하게 증가한다.

개선된 방식은 neural network에 마지막 출력 노드들 하나당 가능한 하나의 action으로 정의하고 그 노드에 나온 출력 값이 action에 따른 Q값에 대응한다.

입력을 image만 넣을 수 있다.

DQN Model architecture

input Layer

• 84 X 84 X 4 image

first hidden layer

• 8 X 8 X 16 필터 (stride 4)
• ReLU

Second hidden layer

• 4 X 4 X 32 필터 (stride 2)
• ReLU

Final hidden layer

• Fully connected
• 256개의 ReLU

Output Layer

• Fully connected
• single output (valid action)
• 게임에서 고려된 output action은 4개에서 18개이다.

5. Experiments

7개의 Atari 게임을 통해 평가했다.

모든 게임의 Reward를 +1, 0, -1로 고정해 진행했다.

• RMSProp algorithm으로 최적화를 진행
• mini batch size는 32로 설정했다.
• \(\epsilon\)-greedy decay : \(\epsilon\)은 1에서 시작해 0.1로 linear하게 감소했다. 첫 million frams 이후부터는 0.1로 고정했다
• 총 1000만 프레임 동안 훈련을 진행했으며, 최근 100만 프레임을 저장하는 리플레이 메모리를 사용
• simple frame-skipping techique를 사용했다. 매 frame마다 agent가 보고 action을 하는 것이 아니라 일정한 K번째의 frame에서 보고 action을 고른다. 다시 다음 주기가 오기 전까지는 마지막으로 한 action을 반복한다. 이렇게 하면 계산을 줄일 수 있다.

Space Invader를 제외한 게임에서는 K = 4를 사용했고 space invadet에서는 K=3을 사용했다.

space invader의 경우 3으로 사용하면 laser가 보이지 않아서 4로 선택했고

이것은 유일하게 다르게 사용된 parameter이다.

5.1 Training and Stability

RL에서 학습중간에 agent를 평가하는 것은 어렵다. agent가 한 에피소드당 얻을 수 있는 reward로 평가하는 것은 noisy하다. 작게 변한 정책의 weight가 큰 변화를 유발할 수 있다.

아래 그림은 Seaquest와 Breakout의 예시이다. noisy 하게 보인다.

왼쪽 두 그래프는 훈련중의 episode마다 Average reward를 보여준다. (Breakout, Seaquest)

• \(ε\)-greedy policy with \(ε\)=0.05 for 10000 steps.

오른쪽 두 그래프는 average maximum predicted action-value를 보여준다.

• One epoch corresponds to 50000 minibatch weight updates or roughly 30 minutes of training time.

더 안정적인 평가 방법은 action-value Q로 평가하는 것이다.

학습 시작전에 랜덤 정책으로 State를 수집하고, 학습 중 이 state들에 대해 최대 Q값의 평균을 구한다.

오른쪽 두 그래프는 Average Q로 평가한 모습이다. 뿐만 아니라 나머지 게임에서도 smooth하게 올라가는 모습을 볼 수 있다.

학습 중 발산의 문제가 없고, 아직 이론적 수렴 증명이 안되었지만, SGD를 통해 대규모 신경망을 안정적으로 학습할 수 있다는 것을 알 수 있다.

Value function

Evaluation

6. Conclusion

• 강화학습을 위한 새로운 딥러닝 모델 DQN을 소개했고, 그것의 성능을 Atari 2600 Game에 적용해 보여줬다.
• DQN은 Stochastic minibatch update와 experience replay memory를 통해 RL을 위한 deep networks의 훈련을 가능하게했다.
• 아키텍쳐나 하이퍼파라미터의 조정없이 7개중 6개의 게임에서 성공을 거두었다.

맨 위로 이동하기

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