![[논문 리뷰] Playing Atari with Deep Reinforcement Learning (DQN)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbyqg4Y%2Fbtr4TKku7LE%2FVk0yFugIFrfuOZuYWulKt0%2Fimg.png)
이제부터 이 블로그에 논문을 하나씩 읽으면서 리뷰를 해보려고 한다. 아마 분야마다 시간을 순서대로 큰 영향을 미친 논문을 읽을 것 같다. 이번 논문은 강화학습에 DL을 적용한 첫 번째 성공적인 연구인 Playing Atari with Deep Reinforcement Learning을 읽어보려고 한다. 코드 구현은 다른 글로 해보겠다.
[1312.5602] Playing Atari with Deep Reinforcement Learning (arxiv.org)
Playing Atari with Deep Reinforcement Learning
We present the first deep learning model to successfully learn control policies directly from high-dimensional sensory input using reinforcement learning. The model is a convolutional neural network, trained with a variant of Q-learning, whose input is raw
arxiv.org
Abstract
The model is a convolutional neural network, trained with a variant of Q-learning.
여기서 배경지식이 되는 두 개의 아주 중요한 term이 나온다. 사실 이 두 개의 단어가 이 논문의 핵심이라고 생각해도 된다. 이 두 개에 대해서는 다른 글로 아마 다루겠지만 여기서 잠깐 설명하고 가겠다.
CNN(Convolutional Neural Network)이란 이미지처리를 위한 신경망인데, 위치 관계를 잃어버리는 fully-connected neural network와 달리 공간적 관계를 감지할 수 있기 때문에 더 효과적이다. 필터를 픽셀 위로 움직여서 feature map을 만드는데, 이 필터만 학습을 시키면 된다. 그리고 필터 외에도 보통 pooling layer이 있는데 차원을 낮추어주는 역할을 한다.
Q-learning이란 강화학습 알고리즘의 한 종류로, 최적의 policy를 학습하는 방법이다. 모든 단계를 거쳤을 때 받는 보상을 최적화하는 것을 목표로 한다. 각각의 action에 Q(quality) 값을 부여해서 더 좋은 행동을 취하는 방식이다.
We apply our method to seven Atari 2600 games from the Arcade Learning Environment, with no adjustment of the architecture or learning algorithm. We find that it outperforms all previous approaches on six of the games and surpasses a human expert on three of them.
이 논문의 결과가 인간을 뛰어넘는 성능을 보여줄 수 있다는 결과를 내었다고 하고 있다.
Introduction
Most successful RL applications that operate on these domains have relied on hand-crafted features combined with linear value functions or policy representations. Clearly, the performance of such systems heavily relies on the quality of the feature representation.
Recent advances in deep learning have made it possible to extract high-level features from raw sensory data, leading to breakthroughs in computer vision and speech recognition.
이전의 RL은 인간이 직접 만든 feature로 작동했기 때문에 이 feature의 quality에 따라 성능이 좌우되었다. Object detection 같은 분야도 처음에는 hand-crafted방식이었지만 현재는 DL을 사용하는 것을 보면, RL에서도 충분히 가능한 일이다.
However reinforcement learning presents several challenges from a deep learning perspective.
하지만 논문에서는 DL을 RL에 바로 적용하기에는 문제가 있다고 하는데 이는
- DL은 보통 많은 labeled 데이터가 필요하지만 RL은 reward 같은 scalar, sparse, noisy, and delayed 한 metric에 따라 학습한다. 즉 action과 reward가 엄청 긴 시간 사이를 지나 연관이 있을 수 있다.
- DL에서는 데이터들이 independent 하지만 RL에서는 서로 연관이 되어있다.
- RL에서는 데이터들이 agent가 학습하면서 바뀐다.
이 논문에서는 이를 해결할 방법으로 CNN과 experience replay mechanism을 내세운다. 이에 대한 설명은 뒤에서 하겠다.
Our goal is to create a single neural network agent that is able to successfully learn to play as many of the games as possible. The network was not provided with any game-specific information or hand-designed visual features, and was not privy to the internal state of the emulator; it learned from nothing but the video input.
하나의 네트워크로 다양한 게임을 할 수 있게 한다는 것은 환경에 관계없이 학습을 할 수 있다는 것이다. 이를 보여주기 위해 DeepMind 팀은 hyperparameter를 고정을 시켜 학습을 시켰다.
Background
The emulator’s internal state is not observed by the agent; instead it observes an image $x_t ∈ R^d$ from the emulator, which is a vector of raw pixel values representing the current screen.
agent는 스크린에 있는 픽셀 값만 입력으로 받고 다른 internal 한 정보를 받지 않는다. 또한 모든 sequence는 유한하기 때문에 MDP(Markov Decision Process)가 적용이 된다.
MDP를 이해하기 위해서는 Markov Property를 이해해야 한다. Markov Property는 한마디로 미래는 현재가 주어졌을 때 독립적이라는 것이다.
즉, $P [S_{t+1}|S_t]=P [S_{t+1}|S_1,..., S_t]$가 성립한다.
이 말의 뜻은 $S_t$를 알면 $S_{t+1}$을 찾기 위해 과거의 정보가 필요 없다는 뜻이다. 즉 memory-efficient 하다.
이제 Markov Decision Process라는 것은 state, action, state transition property, reward function, 그리고 discount factor들의 요소가 있는 것의 정의이다. 보통의 RL은 이것들을 포함하고 있기 때문에 알고리즘들을 적용할 수 있다.
이때 이제 $Q(s, a)$라는 $Q$함수를 정의하고 최적의 함수는 $Q^*(s, a)=\max_\pi \mathbb {E}[R_t|s_t=s, a_t=a,\pi]$로 된다.
여기에서 Bellman equation을 사용해서 최적의 Q함수를 찾는 strategy를 구할 수 있는데 이는 $Q^*(s, a)=\mathbb {E}_{s'\sim \epsilon}[r+\gamma \max Q^*(s', a')|s, a]$이다.
이 value iteration algorithm을 쓰면 $Q_i \rightarrow Q^* $ as $i \rightarrow \infty$ 에 최적의 함수로 수렴한다는 게 보장이 된다. 하지만, 이 방법을 쓰면 각 sequence마다 측정해야 하기 때문에 function approximator를 사용해서 action-value function을 근사한다 $Q(s, a;\theta) \approx Q^*(s, a)$. 이 논문에서는 non-linear 한 방식으로 neural-network를 사용한다. 이를 Q-network라고 부르는데
$$L_i(\theta_i) = \mathbb {E}_{s, a\sim \rho(\cdot)}[(y_i-Q(s, a;\theta_i))^2]$$
$$\text {where}$$
$$y_i =\mathbb {E}_{s'\sim \mathcal {E}}[r+\gamma \max Q^*(s', a';\theta_{i-1})|s, a]$$ 이 loss function을 최소화하는 것으로 구할 수 있다.
Supervised learning과는 다르게 $y_i$인 target은 $\theta_{i-1}$의 영향을 받음으로써 학습 데이터 자체가 학습 시작 전에 정해진 것이 아니라 학습을 하면서 바뀐다.
위의 손실함수를 미분해서 복잡하게 구할 수 있지만, SGD(Stochastsic Gradient Descent)를 통해서 최적화하는 게 computationally expendient 하다.
이 알고리즘은 model-free 하고($\mathcal {E}$의 estimate을 학습하는 것보다 그것에서 나온 sample만으로도 학습한다) off-policy 하다($a=\max_a Q(s, a;\theta)$ 의 그리디 전략으로만 학습하고 $\epsilon$-greedy 전략으로 충분한 state space를 탐색한다.
Related Work
TD-gammon: 현재의 DQN과 비슷하나 특별한 케이스에서만 작동하고 체스나 바둑 같은 게임에서는 작동하지 않는다. 또한, Q-network는 발산하기가 쉽기 때문에 linear function approximator를 이전에서는 많이 사용했다.
NFQ(Neural Fitted Q-learning): RPROP 알고리즘을 사용해서 Q-network를 업데이트하지만 batch update를 사용함으로써 높은 computational cost를 가지고 있다. 또한 DQN과 다르게 deep autoencoder를 사용해서 이 task의 representation을 먼저 학습하기 때문에 end-to-end RL인 DQN과는 차이가 있다.
Deep Reinforcement Learning
Our goal is to connect a reinforcement learning algorithm to a deep neural network which operates directly on RGB images and efficently process training data by using stochastic gradient updates.
Deepmind 팀은
TD-Gammon 같은 online approach보다 experience replay라는 mechanism을 사용해서 $e_t=(s_t, a_t, r_t, s_{t+1})$라는 데이터를 $\mathcal {D} = e_1,... e_N$라는 큐에 저장하는 방식을 채용했다. 이를 실행한 뒤에는 $\epsilon$-greedy라는 방법을 사용해서 state space를 탐색한다.
$\epsilon$-greedy를 간단하게 설명하자면 policy가 정한 action을 $1-\epsilon$의 확률로 실행하고 나머지 확률인 $\epsilon$동안에는 랜덤한 action을 실행한다. 이를 통해서 더욱더 다양한 state들을 탐색해 볼 수 있다.
이 논문에서는 이 알고리즘을 Deep Q Learning이라고 소개하고 있다.
Online Q learning보다 DQL이 우수한 이유:
- 한 데이터가 여러번의 update에 쓰일 수 있기때문에 데이터적으로 효율적이다.
- 연속적인 샘플으로 학습을 하는 것은 데이터간의 상관관계가 크기 때문에 비효율적이다. 랜덤한 데이터를 사용하는게 gradient 업데이트의 편차를 줄여준다. 만약에 연속적인 샘플로 학습을 한다면, 그 연속적인 샘플과 완전히 다른 데이터가 들어올 경우에는 gradient값이 확 튀어서 generalization 성능이 내려간다.
- on-policy로 학습을 하면 현재의 parameter이 샘플에 영향을 주기 때문에 bias된 샘플만 학습이 될 수 있다. 만약에 왼쪽으로 가는 Q 값이 제일 크다면 그 값을 학습한것 때문에 다음에도 왼쪽으로만 가는 feedback loop이 생길 수 있다. 이는 weight값을 무한히 발산하게 만들 수 있는 문제를 일으킬수 있다. 이 논문에서는 off-policy인 experience replay를 사용하면서 parameter의 발산을 막았다.
하지만 이 논문에서는 이 experience replay방법은 각 step의 다른 중요성을 고려하지 않기 때문에 priortized sweeping 같은 방법을 제안한다. 나중에 나오는 논문에서 이것을 사용한다.
논문에서 사용한 전처리 방법:
Atari게임의 frame은 210 x 160 컬러 픽셀 이미지이다. 이를 그대로 학습에 사용한다면 computationally demanding 하기 때문에 전처리를 거쳐야 한다.
- grey-scale로 바꾸어서 이미지의 채널을 3에서 1로 줄여준다 (RGB to black and white)
- 이미지를 110x84로 downsampling 한다
- 게임 화면만 들어올수 있게 84x84로 cropping한다. (이를 하는 이유는 2D Convolution이 정사각형만의 input을 받기 때문에
- 최근 4개의 전처리된 프레임을 쌓아서 Q-function의 입력으로 넣어준다
$Q$를 neural network로 구하는 방법 여러가지가 있다. 첫번째 방법은 image와 action을 신경망에 넣어서 $Q$값을 구하게 하는 방법이다. 이 방법의 문제는 각각의 action마다 forward pass를 실행해야하기에 $n$개의 가능한 action이 있다면 $O(n)$번이나 반복해야한다.
이 방법보다 더 효율적인 방법이 있는데, 이는 신경망에 마지막 출력 노드들 하나당 가능한 하나의 action으로 정의하고 그 노드에 나온 출력 값이 action에 따른 $Q$값에 대응한다. 이는 첫번째 방법보다 $O(1)$이라는 시복도로 더 효율적이고 action space가 넓어질수록 효과적이다.
모델 아키텍쳐 (Deep Q Network):
- 84x84x4
- 8x8x16 (Stride 4)
- ReLU
- 4x4x32 (Stride 2)
- ReLU
- layer with 256 hidden node
- output node corresponding to number of valid actions
Experiments
7개의 게임에서 실험을 하였고 각 게임마다 점수의 magnitude가 다르기 때문에
positive reward: +1
negative reward: -1
으로 설정하여 게임마다 같은 hyperparameter을 사용할 수 있게 하였다.
Hyperparameters
Optimizer: RMSProp
Batchsize: 32
$\epsilon$-greedy decay: anealling linearly from 1 to 0.1 over the timestep of 1,000,000
$k$, the frame skipping constant: 4 for most games (performing action every $k$th frame)
Model Performance Evaluation
- agent가 한 에피소드당 모으는 최대의 reward (noisy)
- 최대 평균 $Q$값 (smooth)
- 학습시에 value function이 바뀌는 것을 볼 수 있음
다른 연구들과의 비교
결론
This paper introduced a new deep learning model for reinforcement learning, and demonstrated its ability to master difficult control policies for Atari 2600 computer games, using only raw pixels as input. We also presented a variant of online Q-learning that combines stochastic minibatch up- dates with experience replay memory to ease the training of deep networks for RL. Our approach gave state-of-the-art results in six of the seven games it was tested on, with no adjustment of the architecture or hyperparameters.
이 논문에서는 딥러닝 모델을 사용하여 강화학습을 진행하는 연구를 진행하였다. Experience replay memory를 사용하여 Q-learning의 변형인 DQN을 만들었다. 7개의 Atari 게임 중에서 6개의 게임에서 state-of-the-art를 달성했다.