Reinforcement Learning(1)
13기 이재빈
과제 내용
논문 리뷰: 'Playing Atari with Deep Reinforcement Learning'
우수과제 선정이유
강의중에 설명이 부족했던 개념들(e-greedy, off-policy 등)을 따로 찾아서 명료하게 정리해 주셔서 다른 분들에게 많은 참고가 될 것 같아서 선정하였습니다.
Atari2006은 Reinforcement Learning에 Deep Learning을 접목시켜, 사람이 플레이하는 수준으로 구현해 낸 learning algorithm입니다. model = CNN + Q-Learning
Deep Learning을 그대로 RL에 적용시키기에는 몇 가지 문제가 발생합니다.
data의 Label이 존재하지 않습니다
RL은 (sparse, noisy, delayed) 특성을 가진 scalar reward로부터 학습합니다
데이터가 iid를 따르지 않습니다 (highly correlated)
RL은 time series data이기 때문에, sequence들 끼리 높은 상관관계를 가지고 있습니다
일정한 분포를 따르지 않습니다 (non-stationary dist)
RL의 algorithm은 새로운 behavior를 계속적으로 학습합니다
.
따라서 여기 논문에서는, 다음과 같은 사항들을 통해 딥러닝과 강화학습을 접목시켰습니다.
CNN +) Q-Learning +) replay mechanism
선택한 action은 emulator에게 전달됩니다
state & score를 수정합니다
또한 게임은 언젠가 끝날 것이기 때문에, emulator의 학습 과정은 종결될 것이라고(finite) 가정하고, finite MDP(Markov Decision Process) 로 model을 가정합니다.
우리의 목표는 agent가 emulator와 상호작용하여, future reward를 최대화하는 적절한 action을 선택하는 것입니다. 이를 위해, 다음과 같이 정의합니다.
Q-function ( $${Q^*}.$$, Optimal action-value function) $Q^*(s,a) = \max_{\pi}\mathbb{E}[R_t|s_t=s, a_t=a, \pi]$ ($\pi$ = policy)
(1) Q-function은 Bellman equation을 따르게 됩니다.
$Q^*(s,a) = \mathbb{E}_{s'~ \varepsilon}[r + \gamma\max_{a'}Q^*(s,a)|s,a]$
위의 식에서, expected value를 최대화하는 $a'$ 값을 선택하게 됩니다
value iteration 혹은 policy iteration 과정을 거치면서, action-value function을 최적화 하게 됩니다.
(2) Q-Network는 Q-function을 modeling한 network이며, $Q(s,a;\theta)$ ≃ $Q^*(s,a)$입니다. (Freeze target Q-network)
최적화
최적화의 경우, 보통 linear로 실행되며
Neural Network처럼 non-linear로 실행되는 경우도 있습니다. ($\theta$ = weights)
Q-Network는 loss function인 $L_i(\theta_i)$ 를 최소화 하기 위한 방향으로 업데이트 됩니다. .
behavior distribution
$\rho(s,a)$는 s, a의 probability distribution 입니다.
model-free
MDP의 model에 관계없이 optimal policy를 구하는 방법입니다.
$\varepsilon$을 정확하게 알고 구하는 것이 아니라, $\varepsilon$에서 sampling 하여 action을 취해보고 정책 함수를 선정합니다.
off-policy
두 가지 policy를 동시에 사용할 경우를 말합니다.
learning에 사용되는 policy는 greedy하기 improve를 하고
움직일 때는 현재의 Q function을 토대로 $\varepsilon$-greedy하게 움직입니다.
+) behavior policy $\mu$을 $\varepsilon$-greedy로, target policy $\pi$를 greedy로 택하게 됩니다.
cf) on-policy vs off-policy
On-policy: 학습하는 policy와 행동하는 policy가 반드시 같아야만 학습이 가능한 RL 알고리즘
ex) SARSA
On-policy의 경우 한번이라도 학습을 해서 policy imporvement를 시킨 순간, 그 policy가 했던 과거의 experience들은 모두 사용이 불가능합니다.
한 번 exploration을 해서 얻은 experience를 학습하고 나면 바로 재사용은 불가능합니다.
따라서, 매우 데이터 효율성이 떨어집니다.
Off-policy: 학습하는 policy와 행동하는 policy가 반드시 같지 않아도 학습이 가능한 RL 알고리즘
ex) Q-Learning
Off-policy는 현재 학습하는 policy가 과거에 했던 experience도 학습에 사용이 가능하고,
사람이나 다른 agent들을 통해서도 학습이 가능합니다.
exploration을 계속하면서도 optimal한 policy를 학습할 수 있습니다.
하나의 policy를 따르면서도 multiple policy를 학습할 수 있습니다.
cf) $\varepsilon$-greedy
greedy
한 번 exploration 한 후, 최고의 보상을 받을 수 있는 action을 계속 취하는 것
ex) 한 번 플레이 한 후, 돈을 가장 많이 딴 슬롯머신에 모두 투자
수렴은 빠르지만, 충분한 탐험을 하지 않았기 때문에 local minimum에 빠질 가능성이 있습니다.
$\varepsilon$-greedy
greedy strategy를 따르는 action을 취할 확률: $1-\varepsilon$
random action을 취할 확률: $\varepsilon$
ex) 동전을 던져서 윗면이 나오면 점수 좋았던 슬롯머신, 뒷면이 나오면 랜덤으로 선택
TD-gammon
model-free
value function을 MLP (with one hidden layer)로 계산합니다.
backgammon에서만 적용될 수도 있다는 한계가 있습니다.
Diverge : Q-Learning & non-linear function approximators일 때, 발산 가능성이 존재합니다. 수렴성 을 보장하기 위해서는 linear function approximator & better guarantees 필요합니다.
Deep Learning + 강화학습 ?
$\varepsilon$: Deep Neural Network
Value Function, policy: Boltzmann machines
divergence: gradient temporal-difference (nonlinear function approximator, restricted variant)
NFQ: Neural fitted Q-Learning
RPROP 알고리즘
batch update: 많은 computational cost가 발생합니다.
autoencoder: 저차원으로 데이터로 시작하는 것이 raw visual input을 사용하는 것 보다 좋은 결과를 보입니다.
. 따라서... Atari2600에 다음과 같은 사항을 적용시켜 비교해 보게 됩니다.
standard RL with linear function approximation & generic visual features
a large number of features -> low-dimentional space
HyperNEAT evolutionary architecture
trained repeatedly
Deep Reinforcement Learning¶
experience replay¶
위와 같이 세팅한 Deep RL에는 reward와 Q-value 값이 엄청나게 커질 수 있기 때문에 stable한 SGD 업데이트가 어려워진다는 단점이 있습니다.
또한 on-policy sample을 통해 update하게 되면 sample에 대한 의존성이 커져서 policy가 수렴하지 못하고 진동할 수 있습니다.
이를 해결하기 위한 논문의 핵심 idea가 experience replay 입니다.
each time step마다 agent의 experience를 저장합니다.
$e_t = (s_t, a_t, r_t, s_{t+1})$ (experience)
$D = e_1, ... , e_N$ (튜플 형태로 마지막 N개 데이터 저장)
replay memory
sample을 업데이트 합니다.
Q-learning updates, minibatch updates
experience replay가 끝난 후, $\varepsilon$-greedy policy를 사용해 action을 선택합니다.
.
experience replay를 수행함으로써,
behavior distribution은 이전 state들의 평균을 기반으로 한 분포를 사용하게 됩니다.
따라서 학습을 smoothing out 할 수 있으며,
진동하거나 발산하는 가능성을 방지해 줍니다.
Deep Q-Learning¶
data efficiency: 모든 experience들이 weight update 되는 데에 계속 reuse 되기 때문에, experience로 weight update를 한 번만 진행하는 것 보다 훨씬 효율적입니다.
break correlation 데이터 특성 상 연속적인 sample끼리는 corr이 강합니다. ramdom하게 sample을 뽑아 minibatch로 구성하기 때문에, update들의 variance를 줄일 수 있습니다.
determine next samples 다음 training을 위한 data sample을 어느 정도 결정할 수 있습니다. 예를 들어 지금 왼쪽으로 가도록 action을 고른다면, 다음 sample들은 왼쪽에 있는 sample들이 주로 나올 것이라고 예측할 수 있습니다. 따라서 현재 action을 고려하여 효율적으로 뽑을 수 있습니다.
(주의점: off-policy로 학습해야 합니다.)
Preprocessing
gray-scale & down-sampling (110* 84)
GPU 환경에 맞게 square로 crop 합니다
last 4 frame을 stack으로 쌓아서, $\phi$의 input data로 넣습니다.
이 모델은 $Q^*$를 단 한번의 forward pass만으로 구할 수 있다는 장점이 있습니다.
input: $\phi(s_t)$
ouput: 가능한 모든 action에 대한 Q-value (4~18)
reward: (1,0,-1) 값으로 고정
RMSProp algorithm with minibatches of size 32
$\varepsilon$-greedy policy: $\varepsilon$ = 1 to 0.1 (~백만), $\varepsilon$ = 0.1 (o.w)
a simple frame-skipping technique (agent가 on every kth frame에만 action을 선택)
논문에서 주목할만한 4가지 contribution¶
raw pixel을 받아와 directly input data로 다룬 것
CNN을 function approximator로 이용한 것
하나의 agent가 여러 종류의 Atari game을 학습할 수 있는 능력을 갖춘 것
Experience replay를 사용하여 data efficiency를 향상한 것
Last updated
