[논문 리뷰 스터디] Playing Atari with Deep Reinforcement Learning

작성자 : 17기 문성빈

✏️ 논문링크✏️ 

Playing Atari with Deep Reinforcement Learning

Playing Atari with Deep Reinforcement Learning

0. Basic of Reinforcement Learning

Unknown environment가 존재할 때, agent는 이 environment와 상호작용 하며 reward를 얻을 수 있다. 이 때, agent는 cumulative rewards를 maximize한다.

 

RL의 goal은 experimental trials와 relative simple feedback으로부터 agent가 좋은 strategy를 학습하는 것이다. Optimal strategy을 통해 agent는 환경에 actively하게 적응하여 future rewards를 maximize할 수 있다.

 

Agent는 environment에서 acting한다. 위에서 언급했듯이 environment는 특정 action을 취하는데, 이는 model을 통해 정해진다. Agent는 environment의 수많은 states 중 한 개의 state에 있을 수 있고, 이러한 state에서 다른 state로 바뀔 때 수많은 actions 중 한 개의 action을 수행한다. 이 때, agent가 어떤 state에 도달하는지는 states 사이의 transition probabilities에 의해 결정된다. 한 번 action이 수행되면, environment는 feedback으로 reward를 전달한다.

 

Model은 reward function과 transition probabilities를 정한다.

• Model을 알 때 : Planning with perfect information → model-based RL. Environment에 대해 충분히 알고있기 때문에 Dynamic Programming(DP)으로 optimal solution을 찾을 수 있다. ex) longest increasing subsequence, traveling salesmen problem etc..
• Model을 모를 때 : Learning with incomplete information → Model-free RL or Learning the model explicitly as part of the algorithm

Agent의 policy $\pi(s)$는 total rewards를 maximize하기 위해 특정 state에서 optimal action이 무엇인지에 대한 guideline을 제공한다. 각 state는 해당하는 policy를 acting하여 받을 수 있는 future rewards에 대해 예측하는 value function과 연관이 되어있다. 즉, value function은 현재 state가 얼마나 좋은지 평가하는 것이다. Policy와 value function은 모두 RL을 통해 learning하려는 것들이다.

Time $t = 1, 2, ..., T$에서 agent와 environment사이의 interaction은 sequence of actions와 observed rewards를 포함한다. Process 진행 중에 agent는 environment에 대해 아는 것들을 축적하고, optimal policy를 learning하며, 어떠한 action을 다음에 취할지 결정하며 효과적으로 best policy를 learning한다.

Time step t에서 각 state, action, reward는 $S_t, A_t, R_t$라 하면 agent와 environment사이의 interaction의 sequence는 한 개의 episode(or trial or trajectory)로 설명할 수 있다. 이 때, sequence는 terminal state $S_t$로 끝나며 아래와 같이 나타낼 수 있다.

$S_1, A_1, R_2, S_2, A_2, ..., S_T$

RL algorithms의 여러 categories들을 보면 만날 수 있는 단어들은 아래와 같다.

• Model-based : Environment의 model에 의존; Model을 알거나 algorithm이 명백하게 model을 learning한다.
• Model-free : Learning도중 model에 대한 의존이 없다.
• On-policy : Algorithm을 train하기 위해 target policy로부터 deterministic outcomes 또는 samples를 사용한다.
• Off-policy : Target policy가 아닌 서로 다른 behavior policy로부터 생성되는 episodes 또는 transitions의 distribution을 train한다.

---

• Model, Policy, Value Function, Optimal Value and PolicyModel은 environment의 descriptor이다. 이러한 model을 통해 environment가 agent와 어떻게 interact하고 feedback을 제공하는지 알거나 추론할 수 있다. Model은 transition probability function P와 reward function R이라는 두 가지의 major parts로 구성되어있다.Transition function P는 action a를 실행하여 reward r을 얻은 후 state s에서 s’으로의 transitioning probability를 저장한다. $\mathbb{P}$를 “probability”의 기호로 사용한다.따라서 state-transition function은 $P(s',r|s,a)$로 정의할 수 있다.Reward function R은 one action으로부터 발생되는 next reward를 예측한다.Policy
  • Deterministic : $\pi(s) = a$
  • Stochastic : $\pi(a|s) = \mathbb{P}_\pi[A=a|S=s]$
  Value Function$G_t = R_{t+1} + \gamma R_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$
  • Future rewards는 더 높은 uncertainty를 가질 수 있다; i.e stock market.
  • Future rewards는 즉각적인 benefits를 제공하지 않는다; i.e 사람이 5년 이후보다 현재의 즐거움을 선호하는 것과 비슷하다!
  • Discounting은 mathematical convenience를 제공한다; i.e Return을 계산하기 위해 끝나지 않는 future steps를 따라갈 필요가 없다.
  • State transition graph에서 infinite loops를 걱정할 필요가 없다.
  State s의 state-value는 time t에서 이 state에 있을 때($S_t=s)$의 expected return이다.비슷하게 state-action pair의 **action-value(Q-value)**를 정의할 수 있다.추가적으로 target policy $\pi$를 따라가기 때문에 possible actions의 probability distribution 또는 Q-values를 state-value를 찾을 수 있다.Action advantage function(A-value)은 action-value와 state-value사이의 차이이다.Optimal Value and Policy$V_{}(s) = \max_{\pi} V_{\pi}(s),Q_{}(s, a) = \max_{\pi} Q_{\pi}(s, a)$
• $\pi_{} = \arg\max_{\pi} V_{\pi}(s),\pi_{} = \arg\max_{\pi} Q_{\pi}(s, a)$
• Optimal policy는 optimal value functions를 얻는다.
• Optimal value function은 maximum return을 생성한다.
• $A_{\pi}(s, a) = Q_{\pi}(s, a) - V_{\pi}(s)$
• $V_{\pi}(s) = \sum_{a \in \mathcal{A}} Q_{\pi}(s, a) \pi(a \vert s)$
• $Q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_t \vert S_t = s, A_t = a]$
• $V_{\pi}(s) = \mathbb{E}_{\pi}[G_t \vert S_t = s]$
• Discounting factor $\gamma \in [0,1]$은 future rewards를 penalize한다. 그 이유는 아래와 같다.
• Value function은 future reward의 prediction으로부터 state의 goodness 또는 state, action을 어떻게 rewarding할지 측정한다. Return으로 알려진 future reward은 진행되는 과정 속에서 discounted rewards의 총합이다. Time t로 시작하여 return $G_t$를 계산하는 것은 아래와 같다.
• Policy는 agent의 behavior function $\pi$이고 state s에서 어떠한 action을 실행해야하는지 알려준다. 이는 state s와 action a사이의 mapping이며 deterministic이거나 stochastic이다.
• $R(s, a) = \mathbb{E} [R_{t+1} \vert S_t = s, A_t = a] = \sum_{r\in\mathcal{R}} r \sum_{s' \in \mathcal{S}} P(s', r \vert s, a)$
• $P_{ss'}^a = P(s' \vert s, a)  = \mathbb{P} [S_{t+1} = s' \vert S_t = s, A_t = a] = \sum_{r \in \mathcal{R}} P(s', r \vert s, a)$
• $P(s', r|s,a) = \mathbb{P}[S_{t+1} = s', R_{t+1} =r|S_t=s, A_t =a]$
• 우리가 state s에 있을 때 action a를 실행하여 다음 state s’에 도달하고 reward r을 얻었다고 해보자. 이것이 one transition step이고, tuple (s, a, s’, r)로 나타낼 수 있다.
• Model : Transition and Reward

 

출처 : https://dacon.io/forum/406104?dtype=recent

---

1. Introduction

1.1 가치 기반 강화학습

강화학습 안에서 모델을 나누는 기준은 다양하지만, 그 중 한 가지는 가치 기반 강화학습과 정책 기반 강화학습으로 나누는 것이다.

가치 기반 강화학습은 가치를 기반으로 Agent에 대한 의사결정을 수행하는 것이다. 자세히 말해보자면, 최적의 Q 함수값을 도출할 수 있도록 학습하고, 해당 Q 함수값을 통해 의사결정을 수행하는 것이다.

q 함수값에 대한 벨만 최적 방정식

학습률(벨만 최적 방정식을 통한 Q 함수값 - Q 함수값의 예측값)

충분한 학습을 거치면 시간차 오차가 0으로 수렴하게 된다. 이 때, Q 함수가 최적의 Q 함수로 수렴했다고 할 수 있다. 결국, 학습을 통해 벨만 최적 방정식을 통해서 구한 Q함수값에 가까워지도록 업데이트하는 것이다.

2. DQN Algorithm

2.1 DQN algorithm의 개요

2.1.1 CNN

기존에 Q-learning은 모든 상태, 행동에 대한 Q 함수값을 따로 저장하고 이를 이용하여 학습을 진행하였다.이는 많은 상태가 존재하는 경우에는 사용하기 어렵다.

하지만 DQN과 같이 CNN을 이용하면 각 상태와 행동에 대한 Q 함수값을 근사할 수 있고 이렇게 되면 Q 함수값을 따로 저장할 필요가 없어진다.

2.1.2 $\epsilon$-greedy algorithm

앞 부분에서 Q함수값이 결정되면 엡실론 그리디 기법에 따라 행동을 결정한다. 행동이 결정되면 이에 따라 Agent가 행동을 취하고, Environmnet에 변화가 생기면서 다음 State, reward, termination에 대한 정보를 얻을 수 있다. 이 정보들을 이용해 CNN에서 parameter들을 학습을 시작하고, 다시 행동을 도출하며 이를 계속 반복하여 train을 진행하는 것이다.

2.2 Experience Replay

DQN에서 안정성 및 성능 개선에 큰 영향을 가진 기법은 총 2가지가 있는데, 그 중 하나가 experience replay이다.

Experience Replay는 experience(경험)이라는 데이터를 이용한다. 이는 ***[현재 상태, 현재 행동, 보상, 게임 종료, 다음상태]***로 구성되어 있으며, 매 스텝마다 Replay buffer라는 메모리에 이가 저장된다.

이를 저장해놓고 mini batch training을 진행합니다. 이는 서로 유사하지 않은 다양한 데이터를 이용하며, 실제로 시간과 같은 데이터 사이의 상관관계를 어느정도 무시할 수 있는 기법이므로 학습이 더 안정적이다.

2.3 Target Network

DQN을 학습하려면 학습의 목표과 되는 Target value를 계산해야한다. 이 때 Target network를 사용하는데, 이는 2가지의 network가 사용된다. 한 개는 Q 함수값을 예측할 때 사용하는 일반적인 network, 다른 하나는 target value를 이용하는 target network이다.

Target value는 Supervised Learning과 비슷하게 진행되는데, network가 매 스텝마다 학습되고, 이 network를 이용해 target value를 구한다면 같은 input에도 당연하게 다른 output이 도출될 수 있다. Network의 parameters들이 매 step마다 변하기 때문이다.

이에 target network는 일정 step동안 업데이트를 수행하지 않고 동일한 input에 대해 동일한 target value를 도출해낼 수 있도록 하고, 이는 발산하지 않고 수렴할 수 있도록 안정성을 향상시키는 역할을 한다.

3. DQN Training

DQN의 학습에 대한 target value의 계산 방법과, Loss function에 대해 설명할 것이다.

3.1 Target value

Q Function

가치 기반 강화학습은 최적의 Q Function을 얻기 위해 Q(s,a) 학습의 목표에 가까워지도록 업데이트한다.

Target value y

3.2 Loss Function

Huber loss function