Playing Atari with Deep Reinforcement Learning
0. Abstract
▶ 강화학습(Reinforcement Learning)을 사용하는 high-dimensinosal sensory input(ex. vision, speech)에서 policy control를 직접 학습하는 DL(Deep Learning) model
▶ Q-learning의 일종으로 훈련된 CNN(Convolutional Neural Network)
- model input: raw pixel
- model output: value function(future reward를 estimate하는 함수)
1. Introduction
(1) Past RL challenges
▶ vision, speech와 같은 high-dimensional sensory input에서의 agent를 control하는 것은 RL에서의 오랜 과제
▶ 기존 RL application의 성능은 feature representation(데이터 표현)에 대한 quality(품질)에 의존
▶ 기존 RL은 hand-crafted features에 의존한 linear value function나 policy representation과 연결되어 동작
(2) DL advances
▶ DL의 발전으로 raw sensory data에서 high-level feature를 추출 가능 → 데이터 품질의 중요성이 떨어짐
▶ computer vision, speech recognition은 다양한 DL 방법을 활용(ex. CNN, multilayer perceptrons, restricted Boltzmann machine, RNN, supervised & unsupervised learning)
▶ 그렇다면 DL에 사용한 방식들이 RL에도 적용이 가능한가?
(3) Challenge to apply DL method to RL
▶ 첫번째, 현재 DL application에는 많은 양의 handlabelled training data가 필요
그러나 RL algorithms은 frequently sparse, noisy, delayed된 환경에서 scalar reward signal을 학습할 수 있어야함
→ RL의 데이터는 DL만큼 feature에 대한 quality가 높게 제공되지 않음
수 천 단계의 time-steps가 될 수 있는 action과 resulting rewards 사이의 delay는 supervised learning에서의 input과 output 사이의 direct association과는 동떨어짐
→ action을 수행하고 나서의 result가 수많은 timestep 뒤에 제공되어 delay가 발생
▶ 두번째, 일반적인 DL algorithm에서의 data sample은 dependent 하지만, RL에서는 일반적으로 data sample 간 high correlated state sequences가 발생
RL에서 data distribution은 algorithm이 새로운 동작을 학습함에 따라 변경되며, 이는 fixed underlying distribution을 가정하는 DL 방식에 문제가 될 수 있다.
(4) Demonstrations of paper
▶ raw video data로부터 성공적인 control policies를 학습하기 위해 CNN을 사용해 극복
▶ network는 weight를 update하기 위해 SGD(Stochastic Gradient Descent)를 사용하여 Q-learning algorithm의 일종으로 훈련
▶ correlated data & non-stationary distribution 문제를 완화하기 위해, 이전의 transitions를 randomly sampling하여 과거 action에 대한 training distribution을 매끄럽게하는 experience replay mechanism을 사용
(5) Experiment environment
- environment: Atari 2600 games in ALE(Arcade Learning Environment)
- model input: 210 x 160 RGB video at 60Hz(high dimensional visual input)
▶ research goal: 가능한 많은 게임을 성공적으로 학습할 수 있는 single neural network agent 생성
훈련에 사용된 network architecture과 hyperparameter는 모든 게임들에서 일정하게 유지
▶ result: 시도한 7개 게임 중 6개에서 이전의 모든 RL algorithms를 능가했으며, 3개는 전문가 인간 플레이어를 능가
2. Background
(1) Precondition
▶ agent가 ɛ와 interaction 하는 task를 sequence of actions, observations, and rewards에서 고려
- ɛ: environment
▶ 각 time-step에서 agent는 set of actions 중 a_t를 선택
- A = {1, ... , K}: set of action
- a_t: action
▶ action은 emulator로 전달되고 internal state과 game score를 조정
▶ 일반적으로, ɛ는 stochastic 할 수 있음
▶ agent는 emulator의 internal state 대신, x_t ∈ R^d를 관찰
// x_t: 현재 화면을 표현하는 raw pixel value vector
▶ 추가로 game score의 변화를 나타내는 r_t를 받음
// r_t: reward
▶ 일반적으로 game score는 이전의 sequence of actions and observations에 기반
→ action에 대한 feedback은 수천 번의 time-step가 경과한 후에 받기 가능
(2) Finite MDP
▶ agent는 현재 화면의 이미지만 관찰하므로 task는 paritally observed 되며, emulator state는 perceptually alisased
→ agent는 현재 화면 x_t만으로는 현재 상황을 완전히 이해가 불가능
▶ 따라서 sequences of actions and observations를 고려하고 이러한 sequence에 의존하는 game strategies를 학습
// s_t = x_1, a_1, x_2, a_2, ... , a_(t-1), x_t: sequence of actions & observations
// x: observation(이미지)
// a: action
▶ emulator의 모든 sequence는 finite number of time-step에서 종료된다고 가정
→ 이러한 formalism은 각 sequence가 distinct state인 large하지만 finite MDP를 발생
▶ 결과적으로 time t에서 완전한 sequence s_t를 state representation으로 사용하여 standard RL method for MDP에 적용 가능
(3) Reward function
▶ agent의 목표는 future reward를 maximise하는 방식으로 action을 선택하여 emultor과 interaction하는 것
→ future reward를 극대화하는 action을 선택하는 agent
▶ future reward는 time-step 마다 factor γ만큼 discounted된다는 것을 표준 가정하고, 시간 t에서의 future discounted return를 아래와 같이 정의
// γ: discount factor
// T: 게임이 종료되는 time-step
(4) Action value function
▶ optimal action-value function: 어떤 policy를 따랐을 때, 얻을 수 있는 maximum expected return
// π: sequence s에 매핑되는 action(or action들에 대한 distributions)
▶ optimal action-value function은 bellman equation을 따름
▶ bellman equation: next time-step에서 sequence s'의 optimal value Q*(s', a')가 모든 action a'에 대해 아는 경우, optimal strategy는 expected value인 r + γQ*(s', a')를 최대화 하는 action a'를 선택
▶ RL algorithm의 기본 아이디어는 bellman equation을 iterative update하여 action-value function을 estimate하는 것
▶ 이러한 value iteration algorithm은 optimal action-value function를 Qi -> Q* as i -> ∞로 수렴
→ 그러나 실제로 이러한 접근은 일반화 없이 각 sequence마다 action-value function을 추정하기 때문에 비현실적이므로 function approximator를 사용하여 action-value function을 추정하는 것이 일반적
▶ 일반적으로는 linear function approximator가 사용되지만, non-linear function approximator(ex. neural network)가 사용되기도 함
▶ weight θ가 있는 neural network function approximator를 Q-network로 사용
▶ Q-network는 반복되는 i마다 Loss function을 minimise하며 학습
▶ 이 때, y_i는 iteration i의 target이고, p(s,a)는 behaviour distribution이라 하며, sequence s & action에 대한 probability distribution
// y_i: target value
// Q(s, a,; θ_i): estimated value
▶ 이전 iteration의 θ_(i−1)의 parameters는 loss function L_i(θi)를 최적화할 때, 고정된 값으로 유지
▶ 가중치에 대한 loss function을 미분하면, 다음 gradient에 도달
▶ 위 gradient에서 full expectations를 계산하는 것보다 SGD를 사용하여 loss function을 optimise하는 것이 효과적
(5) Note
▶ model-free algorithm: E estimate를 명시적으로 구성하지 않고, emulator E로부터의 sample을 직접 사용하여 강화학습 문제를 해결
▶ off-policy algorithm: state space의 적절한 exploration을 보장하는 behaviour distribution을 따르면서, greedy strategy a = max_a Q(s, a;θ)에 대해 학습
→ 실제로, behaviour distribution은 e 확률에 따른 random action을 선택하고 1-e 확률에 따른 greedy strategy를 선택하는, e-greedy strategy에 의해 선택된다.
3. Related Work
(1) TD-gammon
▶ TD-gammon은 Q-leraning과 유사한 model-free algorithm을 사용하고, 하나의 hidden layer가 있는 multi-layer perceptron을 사용하여 value function을 approximate
▶ 그러나 체스나 바둑같은 다른 game에서는 성능이 좋지 않음
→ 실제로 TD-gammon은 action-value function Q(s, a) 보다는 state-value function V(s)를 approximate하고 자체 플레이 게임에서 직접 on-policy를 학습함
(2) Recent research
▶ DL은 environment E를 estimate하는데 사용
▶ restricted Boltzmann machine은 value function or policy function을 estimate하는데 사용
▶ Q-learning의 발산 문제는 gradient TD(temporal-defference)로 부분적 해결
→ 이 방법은 non-linear function approximator로 fixed policy를 evaluate 하거나 Q-learning의 제한된 변형을 사용하여 linear function approximation로 control policy를 학습할 때 수렴하는 것으로 증명
→ 그러나 이 방법은 아직 non-linear control로 확장되지는 못한 상태
(3) NFQ(neural fitted Q-learning)
▶ NFQ는 Q-network의 parameter를 update하기 위해, RPROP algorithm을 사용하여 loss function sequence(DQN의 loss function과 동일)를 최적화
▶ 그러나 iteration 마다 computational cost가 data set의 크기에 비례하는 batch update를 사용
→ DQN은 iteration 마다 low constant cost로 대규모 dataset로 확장되는 stochastic gradient update를 고려
▶ NFQ는 deep autoencoders를 사용하여 low dimensional representation를 학습한 다음, 이 표현에 NFQ를 적용함으로써 purely visual input을 사용하는 control task에도 성공적으로 적용
→ DQN은 visual input에서 직접 RL을 end-to-end로 적용하여, 결과적으로 action-values를 판단하는 것과 직접적으로 관련된 feature를 학습 가능
▶ Q-learning은 이전에 experience replay & simple neural network와 결합되었지만, raw visual input이 아닌 low dimensional state로 시작했었음
4. Deep RL
▶ research goal: RL algorithm을 RGB 이미지에서 직접 작동하는 neural network에 연결하고 SGD update를 사용하여 학습 데이터를 효율적으로 처리하는 것
▶ 성공적인 접근방식: SGD 기반으로 하는 lightweight update를 사용하여 raw inputs에서 직접 훈련
→ neural network에 충분한 데이터를 제공하면 효과적인 학습하는 것이 가능
(1) TD-gammon architecture
▶ TD-gammon architecture는 env와 algorithm의 intercation에서 on-policy sample로부터의 experience(s_t, a_t, r_t, s_(t+1), a_(t+1))에서 직접 value function을 추정하는 network의 parameter를 update
▶ DQN에서는 agent의 많은 experience를 저장하는 experience replay를 활용
→ 각 time-step t 마다 e_t = (s_t, a_t, r_t, s_(t+1)) in a dataset D = e1, ..., eN는 많은 에피소드에 걸쳐 replay memory로 pooling
(2) DQN step
▶ algorithm의 내부 루프 동안 저장된 sample pool에서 무작위로 추출한 experience sample e~D에 Q-learning update 또는 mini batch update를 적용
▶ experience replay를 수행한 후 agent는 e-greedy policy에 따라 action을 선택하고 실행
▶ 임의 길이의 데이터를 neural network의 input으로 사용하는 것이 어려울 수 있기 때문에, Q-function은 대신 함수 φ에 의해 생성된 고정된 길이의 데이터로 작동
실제로 DQN은 replay memory D에서 최근 N개의 experience tuples만을 저장하고 update를 수행할 때, D에서 무작위로 균일하게 sampling 수행
균일한 sampling은 replay memory의 모든 transition에 동일한 중요성을 부여
이 접근방식은 memory buffer가 중요한 transition을 판별하지 않고, finite memory size N으로 인해 항상 최근 trainsition으로 덮어쓰기 때문에 어떤 면에서는 제한적
보다 정교한 sampling strategy(ex. prioritized sweeping)는 가장 많이 학습 가능한 transition을 강조도 가능
(3) DQN advnaces
▶ 첫번째, experience의 각 step은 잠재적으로 많은 weight update에 사용되어 data efficiency를 높임
▶ 두번째, sample를 randomize하면 sample 간의 correlation가 깨져 update의 variance가 줄어듬
→ 연속적인 sample에서 직접 학습하는 것은 sample 간의 correlation으로 인해 비효율적
▶ 세번째, off-policy의 사용으로 안정적인 학습 진행
→ experience replay로 학습할 때, Q-learning을 선택하도록 동기를 부여하는 off-policy(현재 parameter가 sample 생성에 사용된 parameter과 다르기 때문에 사용)를 학습해야함
on-policy를 학습할 때는 현재 parameter는 parameter가 학습되는 다음 data sample을 결정
→ local minumum에 빠질 가능성이 높아지며 이는 experience replay를 사용하여 behavior distribution은 previous states에 대해 평균화되어 학습을 원활하게 하고, parameter의 진동 또는 발산을 방지
4.1 Preprocessing
▶ raw image를 직접 input으로 사용하는 것은 계산적으로 까다로울 수 있으므로, input dimensionality를 줄이는 것을 목표로 하는 기본 전처리 단계를 φ 함수를 통해 적용
// φ function: raw image → gray-scale → down-sampling(110 x 84) → cropping(84 x 84)
- final input representation: 84 x 84 region of image
▶ neural network를 사용하여 Q를 parameterize 하는 몇가지 방법이 존재
→ Q는 history action pairs를 Q-value의 scalar estimates에 매핑하기 때문에, history & action은 일부 previous approaches에 의해서 neural network에 대한 input으로 사용되었음
▶ 이러한 유형의 architecture의 단점은 각 action의 Q-value를 계산하기 위해 별도의 forward pass가 필요하므로 cost가 action 수에 따라 linearly하게 확장됨
→ 대신 가능한 각 action에 대해 별도의 output unit이 있고, state representation만 neural network에 대한 input인 architecture를 사용
→ outputs은 input state에 대한 개별 action의 predicted Q-value에 해당
▶ 이러한 architecture의 장점은 network를 통한 single forward pass로만으로 주어진 state에서 가능한 모든 action에 대한 Q-value 계산이 가능
4.2 Model architecture
- model input: φ에 의해 생성된 84 x 84 x 4 이미지
- hidden layer 1: 16개 8 x 8 filter, 4 stride → non-linearyity recifier 처리
- hidden layer 2: 32개 4 x 4 filter, 2 stride → non-linearyity recifier 처리
- hidden layer 3: 256개 fully-connected linear layer
- model output: 각각의 valid action(atari에서 고려한 게임에서 4~18 사이의 수)에 대한 single output
5. Experiments
(1) Background
▶ Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest, Space Invaders 등 7개의 인기 있는 ATARI 게임에 대한 실험을 수행
▶ 7개 game 모두에서 동일한 network architecture에서 학습 algorithm 및 hyperparameter를 설정을 사용하여 우리의 접근 방식이 게임별 정보를 통합하지 않고도 다양한 게임에서 작동할 수 있을 만큼 강력함을 보여줌
(2) Detail
▶ 게임에서 reward structure만 변경이 존재하는데, 점수의 척도는 게임마다 크게 다르기 때문에 모든 positive reward는 1로, 모든 negative reward는 -1로, leaving은 0으로 설정
→ 이러한 방식으로 reward를 clipping하면 error derivatives의 규모가 제한되고 여러 게임에서 동일한 학습률을 더 쉽게 사용 가능하지만 동시에 다른 크기의 reward를 구별할 수 없기 때문에, agent 성능에 영향을 끼칠 수도 있음
▶ 해당 실험에서는 32 mini batch와 RMSProp algorithm을 사용
▶ 훈련 중 behavior policy는 초기 100만 frame에 대해 1에서 0.1까지 linear하게 annealed된 e-greedy하게 행동했고 그 이후에는 0.1로 고정
▶ 총 1000만 frame에 대해 훈련했고 가장 최근 100만 frame의 replay memory를 사용
▶ 이전의 Atari game 접근 방식에 이어 간단한 frame 건너뛰기 기술도 사용
→ agent가 runtime을 크게 늘리지 않고도 약 k배 더 많은 게임을 플레이 가능
▶ k 번째 frame마다 action을 보고 선택하며 건너뛴 프레임에서 마지막 action이 반복
5.1 Training and Stability
▶ 지도 학습에서는 훈련 및 검증 세트에서 모델을 평가하여 훈련 중에 모델의 성능을 쉽게 추적 가능
▶ 그러나 강화학습에서는 훈련 중 agent의 상황을 정확하게 평가하는 것이 어려움
▶ evaluation metric은 agent가 episode or game에서 수집하는 total reward이므로 여러 game에 대해 평균을 내고 훈련 중에 이를 주기적으로 계산
→ 평균 total reward metric은 policy weight의 작은 변화가 distribution of states policy visit의 큰 변화로 이어질 수 있기 때문에 매우 noisy함
▶ 더 안정적인 또 다른 metric은 policy의 estimated action-value function Q로, agent가 주어진 state에서 policy를 따를 때 얻을 수 있는 discounted reward estimate
→ 훈련이 시작되기 전에 무작위 policy를 실행하여 fixed set of states를 수집하고 이러한 state에 대한 maximum predicted Q의 평균을 추적
▶ 훈련 중에 predicted Q에 대해 비교적 순조롭게 개선되는 것을 보는 것 외에도 모든 실험에서 발산되지 않음
▶ 이론적 수렴 보장이 없음에도 불구하고 이 방법이 RL signal과 SGD를 사용하여 안정적인 방식으로 대규모 neural network를 훈련할 수 있음을 시사
5.2 Visualizing the value function
▶ Seaquest 게임에서 학습된 value function의 시각화
5.3 Main evaluation
▶ Sarsa: several different feature sets에 대한 linear policies를 학습
▶ Contingency: Sarsa와 동일한 기본 접근 방식을 사용했지만 agent의 제어 하에 있는 화면 부분의 learned representation으로 feature sets를 보강
▶ 위 두가지 방법 모두 background subtraction을 사용하고 각 128개 색상을 별도의 채널로 처리하여 시각적 문제에 대한 상당한 사전 지식을 통합
→ 각 색상을 별도로 취급하는 것은 각 object type의 존재를 인코딩하는 별도의 binary map를 생성하는 것과 유사
▶ 대조적으로, agent는 raw RGB 화면만 input으로 받으며 스스로 물체를 감지하는 법을 배워야함
▶ 학습된 agent 외에도, 전문 인간 게임 플레이어의 점수와 무작위로 균일하게 action을 선택하는 policy도 고려
▶ HNeat Best: Atari 화면에서 물체의 locations & types를 출력하는 hand-engineered object detector algorithm을 사용하여 얻은 결과 반영
▶ HNeat Pixel: 각 채널에서 object label map을 나타내는 Atati emulator의 특수 8색을 사용한 결과 반영
6. Conclusion
▶ 해당 논문에서는 RL을 위한 새로운 DL model를 소개하고, raw pixel input을 사용하여 Atari 2600 games에 대한 어려운 policy control을 마스터하는 능력을 보여줌
▶ 또한 stochastic minibatch updates와 experience replay memory를 결합하여 Rl에 대한 deep network 교육을 용이하게 하는 online Q-learning의 변형을 제시
▶ 이러한 접근 방식은 architecture & hyperparameter을 조정하지 않고 테스트한 7개 game 중 6개에서 최고의 결과를 제공
'논문 리뷰 > 과거 RL 정리' 카테고리의 다른 글
| Semi-supervised classification with GCN (0) | 2022.01.21 |
|---|---|
| Prioritized Experience Replay (0) | 2021.12.29 |
| Dueling DQN (0) | 2021.12.14 |
| DDQN(Double DQN) (0) | 2021.12.12 |
댓글