Deep Q-Network

Created on July 20, 2024

2024   ·   Reinforcement Learning   DQN   ·   ML/DL Theory

Deep Q-Network

Deep Q-Network, 즉 DQN은 action-value function인 \(Q\) function을 neural network로 근사하는 value-based Temporal Difference, 즉 TD 알고리즘이다.

DQN은 discrete action space를 갖는 environment에 적용할 수 있다. 연속적인 action space를 직접 다루기보다는, 선택 가능한 action이 유한하게 정의된 문제에서 사용된다.

DQN은 off-policy 알고리즘이다. 즉, agent가 현재 어떤 policy를 통해 experience를 수집했는지와 무관하게, 수집된 데이터를 다시 학습에 사용할 수 있다. 이를 위해 experience replay memory를 사용한다.

Exploration을 위해서는 Boltzmann policy distribution을 사용할 수 있다. 이는 \(\epsilon\)-greedy policy와 달리 action의 상대적인 \(Q\) value를 softmax probability로 변환하여 action을 선택하는 방식이다.

DQN은 Bellman equation을 기반으로 \(Q\) function을 학습한다. 따라서 현재 state-action pair의 value를 reward와 next state에서의 maximum future value로 업데이트한다. 이 글은 7주차 Reinforcement Learning lecture slide 내용을 기준으로 정리하였다.

Q Learning

Action-value function을 근사하는 value network를 \(Q_\theta\)라고 할 때, DQN은 \(Q_\theta\)가 각 state-action pair의 value를 잘 예측하도록 학습한다.

먼저 policy \(\pi\)에 따라 trajectory \(\tau\)를 생성한다. 이후 neural network \(Q_\theta^\pi\)를 이용하여 모든 state \(s\)와 action \(a\)에 대해 predicted Q value를 계산한다.

\[\hat{Q}^{\pi}(s,a) := Q_\theta^{\pi}(s,a)\]

위 수식에서 \(\hat{Q}^{\pi}(s,a)\)는 network가 예측한 action-value를 의미한다. \(Q_\theta^{\pi}(s,a)\)는 parameter \(\theta\)를 갖는 value network가 policy \(\pi\) 아래에서 state \(s\)와 action \(a\)에 대해 출력한 값을 의미한다.

TD learning에서는 trajectory에서 얻은 experience를 이용하여 target value를 계산한다. 하나의 experience는 \((s,a,r,s',a')\)로 표현할 수 있다.

\[Q_{\text{tar}}^{\pi}(s,a) := r + \gamma \hat{Q}^{\pi}(s',a')\]

위 수식에서 \(Q_{\text{tar}}^{\pi}(s,a)\)는 target Q value를 의미한다. \(r\)은 현재 action 이후 얻은 reward이고, \(\gamma\)는 discount factor이다. \(\hat{Q}^{\pi}(s',a')\)는 다음 state \(s'\)와 다음 action \(a'\)에 대한 predicted Q value를 의미한다.

Value network는 predicted value와 target value 사이의 차이를 줄이도록 학습된다. 일반적으로 MSE와 같은 regression loss를 사용한다.

\[L := \sum_{s,a} \left( Q_\theta^{\pi}(s,a) - Q_{\text{tar}}^{\pi}(s,a) \right)^2\]

이 수식에서 loss \(L\)은 predicted Q value와 target Q value 사이의 squared error를 모든 state-action pair에 대해 합산한 값이다. DQN은 이 loss를 최소화하는 방향으로 value network parameter \(\theta\)를 업데이트한다.

Bellman Equation

Action-value function은 특정 state \(s\)에서 action \(a\)를 선택한 뒤, policy \(\pi\)를 따라 episode가 진행될 때 기대되는 discounted return으로 정의된다.

\[Q^{\pi}(s,a) = \mathbb{E}_{s_0=s, a_0=a, \tau \sim \pi} \left[ \sum_{t=0}^{T} \gamma^t r_t \right]\]

위 수식에서 \(Q^{\pi}(s,a)\)는 policy \(\pi\) 아래에서 state \(s\)와 action \(a\)의 expected return을 의미한다. \(r_t\)는 time step \(t\)에서 얻은 reward이고, \(\gamma\)는 future reward를 현재 시점에서 얼마나 반영할지 결정하는 discount factor이다.

Infinite-horizon setting에서 discounted return은 다음과 같이 분리할 수 있다.

\[Q^{\pi}(s,a) = \mathbb{E}_{s_0=s, a_0=a, \tau \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \right]\] \[= \mathbb{E}_{s_0=s, a_0=a, \tau \sim \pi} \left[ r_0 + \gamma \sum_{t=1}^{\infty} \gamma^{t-1} r_t \right]\]

현재 reward \(r_0\)를 분리하면, 나머지 항은 next state \(s'\)와 next action \(a'\)에서 다시 시작하는 action-value function으로 해석할 수 있다.

\[Q^{\pi}(s,a) = r + \gamma \mathbb{E}_{s_0=s', a_0=a', \tau \sim \pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \right]\] \[= r + \gamma Q^{\pi}(s',a')\]

따라서 Bellman equation은 현재 state-action value가 immediate reward와 next state-action value의 discounted sum으로 표현될 수 있음을 보여준다.

TD Learning: SARSA and DQN

SARSA와 DQN은 모두 TD learning을 기반으로 하지만, target value를 계산하는 방식이 다르다.

SARSA는 next state \(s'\)에서 실제로 선택된 action \(a'\)를 이용하여 target value를 계산한다.

\[Q_{\text{tar:SARSA}}^{\pi}(s,a) := r + \gamma \hat{Q}^{\pi}(s',a')\]

위 수식에서 \(a'\)는 policy \(\pi\)에 의해 실제로 선택된 next action이다. 따라서 SARSA는 현재 policy가 생성한 action을 그대로 target 계산에 사용한다.

DQN은 next state \(s'\)에서 가능한 모든 action 중 가장 큰 Q value를 갖는 action을 이용하여 target value를 계산한다.

\[Q_{\text{tar:DQN}}^{\pi}(s,a) := r + \gamma \max_{a'} \hat{Q}^{\pi}(s',a')\]

위 수식에서 \(\max_{a'} \hat{Q}^{\pi}(s',a')\)는 next state \(s'\)에서 선택 가능한 action들 중 predicted Q value가 가장 큰 값을 의미한다.

이 차이 때문에 SARSA는 on-policy algorithm으로 분류된다. SARSA는 policy \(\pi\)에 의해 실제로 결정된 next action \(a'\)를 target 계산에 사용하기 때문이다.

반면 DQN은 off-policy algorithm으로 분류된다. DQN은 현재 policy가 실제로 어떤 action을 선택했는지보다, next state에서 가능한 action들 중 maximum Q value를 기준으로 target을 정의하기 때문이다.

DQN Training Strategy

DQN이 off-policy algorithm이라고 하더라도, agent가 experience를 어떻게 수집하는지는 중요하다.

State-action space가 매우 크면 모든 \((s,a)\) pair를 충분히 경험하는 것은 어렵다. 따라서 agent는 training 초기에 state-action space를 빠르게 탐색해야 한다. 그래야 좋은 action을 찾을 확률이 높아진다.

Training이 진행되고 agent가 더 많이 학습하면, exploration의 비율을 점차 낮추고 exploitation에 더 집중해야 한다. 즉, 초반에는 다양한 action을 시도하고, 후반에는 이미 학습한 좋은 action을 더 자주 선택해야 한다.

Value function을 근사하는 deep neural network의 generalization 성능은 경험하지 않은 state-action pair에 대한 예측을 어느 정도 완화할 수 있다. 하지만 이것만으로 exploration 문제를 완전히 해결할 수는 없다.

따라서 DQN에서는 좋은 policy가 자주 방문할 가능성이 높은 state와 action에 집중하여 학습하는 것이 중요하다.

Boltzmann Policy Distribution

Exploration-exploitation balance를 조절하는 대표적인 방법에는 \(\epsilon\)-greedy policy와 Boltzmann policy distribution이 있다.

Boltzmann policy distribution은 action의 상대적인 Q value를 이용하여 action을 선택한다. 이를 위해 softmax function을 사용하여 state \(s\)에서 가능한 모든 action \(a\)에 대한 probability distribution을 만든다.

\[p_B(a \mid s) = \frac{ \exp \left( \frac{Q^{\pi}(s,a)}{\tau} \right) }{ \sum_{a'} \exp \left( \frac{Q^{\pi}(s,a')}{\tau} \right) }\]

위 수식에서 \(p_B(a \mid s)\)는 state \(s\)에서 action \(a\)를 선택할 probability를 의미한다. \(Q^{\pi}(s,a)\)는 해당 action of value이고, \(\tau\)는 temperature parameter이다.

Temperature \(\tau\)는 probability distribution의 sharpness를 조절한다. \(\tau\)가 작으면 높은 Q value를 가진 action에 probability가 집중된다. 반대로 \(\tau\)가 크면 action probability가 더 완만하게 분포한다.

Epsilon-Greedy Policy

\(\epsilon\)-greedy policy는 agent가 random action을 선택할지 greedy action을 선택할지를 결정하는 방식이다.

Agent는 probability \(\epsilon\)으로 random action을 선택한다. 이 경우 가능한 action들에 대해 uniform distribution을 사용한다.

반대로 probability \(1-\epsilon\)으로 greedy action을 선택한다. 이 경우 state에서 선택 가능한 모든 action의 Q value를 계산하고, maximum Q value를 갖는 action을 선택한다.

Training이 진행될수록 random action을 선택할 probability \(\epsilon\)을 감소시킨다. 이를 통해 초반에는 exploration을 많이 수행하고, 후반에는 exploitation을 강화한다.

Action Selection Policy Comparison

다음 예시는 action space가 \(\mathcal{A} = \{a_1, a_2\}\)인 경우를 비교한다. \(\epsilon\)-greedy policy에서는 \(\epsilon = 0.05\)를 사용하고, Boltzmann policy에서는 \(\tau = 1.0\)과 \(\tau = 5.0\)을 비교한다.

\(Q^{\pi}(s,a_1)\) \(Q^{\pi}(s,a_2)\) \(p_{\epsilon}(a_1 \mid s)\) \(p_{\epsilon}(a_2 \mid s)\) \(p_B(a_1 \mid s), \tau=1.0\) \(p_B(a_2 \mid s), \tau=1.0\) \(p_B(a_1 \mid s), \tau=5.0\) \(p_B(a_2 \mid s), \tau=5.0\)
1.00 9.00 0.05 0.95 0.00 1.00 0.17 0.83
4.00 6.00 0.05 0.95 0.12 0.88 0.40 0.60
4.90 5.10 0.05 0.95 0.45 0.55 0.49 0.51
5.05 4.95 0.95 0.05 0.52 0.48 0.50 0.50
7.00 3.00 0.95 0.05 0.98 0.02 0.69 0.31
8.00 2.00 0.95 0.05 1.00 0.00 0.77 0.23


\(\epsilon\)-greedy policy는 Q value의 차이가 작더라도 maximum Q value를 갖는 action에 높은 probability를 부여한다. 예를 들어 \(Q^{\pi}(s,a_1)=5.05\)이고 \(Q^{\pi}(s,a_2)=4.95\)인 경우에도 \(a_1\)이 greedy action이므로 높은 probability를 갖는다.

반면 Boltzmann policy distribution은 Q value의 상대적인 차이를 probability에 반영한다. 두 action의 Q value가 비슷하면 probability도 비슷해진다. Q value 차이가 커지면 높은 Q value를 갖는 action의 probability가 증가한다.

Temperature \(\tau\)가 작을수록 probability distribution은 sharper해진다. \(\tau=1.0\)에서는 Q value 차이가 큰 경우 한 action에 probability가 거의 집중된다. \(\tau=5.0\)에서는 같은 Q value 차이에서도 probability가 더 완만하게 분포한다.

Experience Replay Memory

Experience replay memory는 off-policy training을 가능하게 하는 핵심 기법 중 하나이다.

Agent가 한 번 사용한 experience를 바로 폐기하지 않고 memory에 저장한 뒤, 이후 training에서 다시 사용한다. 이를 통해 과거 experience를 재활용할 수 있다.

Experience replay memory는 fixed-size queue와 같은 자료구조를 갖는다. Agent가 확보한 가장 최신 \(k\)개의 experience를 저장한다. Memory가 가득 차면 가장 오래된 experience부터 제거된다.

Training 단계에서는 memory에서 하나 이상의 mini-batch를 uniform distribution으로 random sampling한다. 이후 sampling된 mini-batch를 이용하여 Q function network의 parameter를 업데이트한다.

Memory size \(k\)는 일반적으로 \(10^4\)에서 \(10^6\) 사이의 큰 값을 갖는다. 반면 mini-batch size는 보통 32에서 2048 정도의 크기를 갖는다.

Experience replay memory를 사용하면 training에 사용되는 experience들 사이의 correlation이 낮아진다. 또한 parameter update의 variance가 줄어들어 training stability를 높이는 데 도움이 된다.

DQN Algorithm

DQN algorithm의 input은 learning rate \(\alpha\), temperature \(\tau\), batch size \(B\), sample size \(h\), memory size \(K\)이다. Output은 optimal policy \(\pi\)이다.

Algorithm의 전체 흐름은 experience collection, replay memory update, mini-batch sampling, TD target calculation, loss accumulation, parameter update, temperature decay로 구성된다.

  • Line 1에서는 experience replay memory \(\mathcal{M}\)을 초기화한다.

  • Line 2에서는 parameter \(\theta\)를 갖는 value network를 초기화한다.

  • Line 3에서는 \(m=1,\dots,\text{MAX_STEPS}\) 동안 training loop를 반복한다.

  • Line 4에서는 current policy를 이용하여 \(h\)개의 experience \((s,a,r,s')\)를 sample한다.

  • Line 5에서는 sample된 experience를 replay memory \(\mathcal{M}\)에 enqueue한다.

  • Line 6에서는 loss accumulator \(L\)을 0으로 초기화한다.

  • Line 7–8에서는 batch size \(B\)만큼 replay memory에서 experience \((s_i,a_i,r_i,s_i')\)를 sampling한다.

  • Line 9에서는 DQN target value \(y_i\)를 계산한다.

\[y_i = r_i + \gamma \max_{a_i'} Q_\theta^{\pi}(s_i',a_i')\]

위 수식에서 \(y_i\)는 \(i\)번째 sampled experience에 대한 TD target이다. \(r_i\)는 immediate reward이고, \(\max_{a_i'} Q_\theta^{\pi}(s_i',a_i')\)는 next state \(s_i'\)에서 가능한 action 중 maximum predicted Q value를 의미한다.

  • Line 10에서는 target value \(y_i\)와 current prediction \(Q_\theta^{\pi}(s_i,a_i)\) 사이의 squared error를 loss에 누적한다.
\[L \leftarrow L + \left( y_i - Q_\theta^{\pi}(s_i,a_i) \right)^2\]

위 수식에서 \(Q_\theta^{\pi}(s_i,a_i)\)는 value network가 현재 state-action pair에 대해 예측한 Q value이다.

  • Line 12에서는 accumulated loss \(L\)에 대한 gradient를 이용하여 parameter \(\theta\)를 업데이트한다.
\[\theta \leftarrow \theta - \alpha \nabla_{\theta} L\]

위 수식에서 \(\alpha\)는 learning rate이고, \(\nabla_{\theta}L\)은 value network parameter \(\theta\)에 대한 loss gradient이다.

  • Line 13에서는 temperature \(\tau\)를 감소시킨다. 이를 통해 training이 진행될수록 exploration을 줄이고 exploitation을 강화한다.

Summary

DQN은 action-value function을 deep neural network로 근사하는 value-based TD algorithm이다.

DQN은 next state에서 가능한 action들 중 maximum Q value를 사용하여 TD target을 정의한다.

SARSA는 실제로 선택된 next action을 target 계산에 사용하므로 on-policy algorithm이고, DQN은 maximum Q value를 기준으로 target을 계산하므로 off-policy algorithm이다.

Boltzmann policy distribution은 Q value의 상대적 크기를 probability로 변환하여 action을 선택한다. Temperature \(\tau\)는 exploration-exploitation balance를 조절한다.

Experience replay memory는 과거 experience를 저장하고 random mini-batch로 재사용하여 training stability를 높인다.

DQN의 핵심은 Bellman equation 기반 TD target, replay memory 기반 off-policy learning, 그리고 exploration을 위한 action selection policy의 조합으로 이해할 수 있다.