RLPG discussions #1 (DQN)

RLPG 그룹 멤버들 간의 토론을 통해 이 노트가 만들어지고 있습니다:

권휘 김경환(부랩짱, 윈짱) 김민지(맥짱) 류주영 박창규 백병인 이규복 이승재 전효정 조동헌(우짱) 이일구(코짱) 정재윤 최윤규

Bellman equation

Bellman equation 은 MDP 형태로 주어진 강화학습 문제에서 임의의 policy $\pi$ 가 주어졌을 때, 이에 해당하는 value 함수 $v_\pi: \mathscr{S} \rightarrow \mathbb{R}$ 와 $q_\pi: \mathscr{S} \times \mathscr{A} \rightarrow \mathbb{R}$ 가 각각 만족하게 되는 방정식이다.

먼저 state value 함수 $v_\pi$ 의 경우:

$\begin{aligned} v_\pi(s) &= \mathbb{E}(G_t \vert S_t = s) \\ &= \mathbb{E}(R_{t+1} + \gamma \,G_{t+1} \vert S_t = s) \\ &= \mathbb{E}(R_{t+1} \vert S_t = s) + \gamma \,\mathbb{E}_{S_t = s}(G_{t+1}\vert S_{t+1}) \\ &= \mathbb{E}(R_{t+1} \vert S_t = s) + \gamma \,\mathbb{E}_{S_t = s} \, (v_\pi(S_{t+1})) \end{aligned}$

action-value 함수 $q_\pi(s, a)$ 의 경우도 마찬가지로:

$\begin{aligned} q_\pi(s, a) &= \mathbb{E}(G_t \vert S_t = s, A_t = a) \\ &= \mathbb{E}(R_{t+1} + \gamma \,G_{t+1} \vert S_t = s, A_t = a) \\ &= \mathbb{E}(R_{t+1} \vert S_t = s, A_t = a) + \gamma \,\mathbb{E}_{S_t = s, A_t = a}(G_{t+1}\vert S_{t+1}, A_{t+1}) \\ &= \mathbb{E}(R_{t+1} \vert S_t = s, A_t = a) + \gamma \,\mathbb{E}_{S_t = s, A_t = a} \, q_\pi(S_{t+1}, A_{t+1}) \end{aligned}$

State value 함수의 Bellman equation 을 이용하여 optimal policy $\pi^\star$ 를 정의할 수 있고 $\pi^\star$ 애 대한 value 함수 (optimal value 함수) $v_\pi^\star$ 와 $q_\pi^\star$ 를 정의할 수 있는데 이 optimal value 함수들도 같은 형태의 Bellman equation 을 만족하게 된다. 따라서 transition probability 가 알려진 경우 DP (Dynamic Programming) 을 이용하여 optimal policy $\pi^\star$ 로 수렴하는 policy 의 수열을 생성하는 효율적인 알고리즘을 디자인할 수 있다.

DP 를 이용한 알고리즘의 수렴성을 이용하여 transition probability 를 이용하지 않고 “optimal policy 로 수렴하는 알고리즘”을 디자인할 수 있는데 sampling 을 이용한 통계학적인 접근이 그것이다. Sampling 을 이용한 방법은 bootstrapping 여부에 따라 Monte Carlo 와 Temporal Difference 두 가지가 있다.

$Q$-learning as an off-policy TD learning

Off-policy control 방법은 behavior policy $\beta$ 와 target policy $\pi$ 를 구분하여 운용한다. 학습을 위한 experience 를 획득하기 위한 action의 선택은 $\beta$ 를 통하여서 한다. 그리고 학습된 내용으로 policy $\pi$ 를 업데이트 하여 optimal policy 로 수렴되도록 한다.

그러면 target policy 를 업데이트 한다는 것은 어떤 의미인가? Optimal policy $\pi^\star$ 로 수렴시킬 목적으로 정의된 “target variable” $Q(s, a)$ 를 각 $(s, a)$ 마다 업데이트 하는 것을 의미한다. 즉, $Q \rightarrow q^\star$ 의 수렴성을 얻기 위한 업데이트이다.

Policy 는 보통 주어진 state 에서 가능한 action 들에 대한 확률함수로 주어지지만, 여기서는 편의상 behavior policy 를 다음과 같은 형태의 함수로 정의하자.

$\beta : \mathscr{S} \rightarrow \mathscr{A}.$

즉, 주어진 state $s$ 에 대한 함숫값 $\beta(s) \in \mathscr{A}$ 는 $s$ 에서 policy $\beta$ 가 선택하는 action 이 된다. 다시 한번 강조하자면 off-policy control 은 behavior policy $\beta$ 의 선택을 통하여 진행된 경험으로 얻은 reward 를 바탕으로 target policy $\pi$ 의 action value 함수에 해당하는 target variable $Q(s, a)$ 를 업데이트한다. 구체적으로 target policy 의 업데이트는 다음과 같은 형태로 이루어진다.

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left(R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a') - Q(S_t, A_t)\right).$

Behavior policy $\beta$ 에 의해 생성된 에피소드에서 timestep $t$ 에서의 state 가 $S_t = s$, 선택된 action 이 $A_t = a$ 라고 할 때 $Q(s, a)$ 의 값을 좀 더 optimal 에 가까운 값으로 업데이트 하려는 의도인데, 그 방법이 현재의 값과 실제로 얻을 수 있는 값과의 차이를 계산해서 이를 반영하게 다는 것이다. 즉 현시점에서의 (temporal) 차이 (difference) 를 근거로 삼아 업데이트 한다는 전략이다.

그러면 실제 optimal 한 action value 는 어떤 값일까? 모델을 가정하여 상상해보면

$q^\star(s, a) = \mathbb{E}_{\pi}(R_{t+1}+ \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \vert S_t=s, A_t = a)$

임을 알 수 있다. 하지만 우리는 모델을 이용하지 않고 이 값에 “가까운” 값을 계산하여 대신하려고 한다. Sampling 을 통한 반복적인 업데이트로 수렴성을 획득하려는 전략이기 때문에 expectation 부분은 점진적으로 해결이 된다고 보면, 결국

$R_{t+1}+ \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

에 최대한 가까운 값을 계산할 수 있으면 될 것 같다.

그렇다면 behavior policy $\beta$ 를 이용하여 action 을 취해나가면서 reward 를 긁어모아야 하나? 라고 생각할 수 있지만.. TD($0$) 의 아이디어는 이 시점에서 bootstapping 을 도입하자는 것이다. 구체적으로, $\beta$ 에 의해 선택된 $a$ 로 인해 이미 $R_{t+1}$ 의 값은 이미 획득했고,

$\gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) = \gamma G_{t+1}$

임을 고려하면

$R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) \approx R_{t+1}+ \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

일 것이라는 예상을 할 수 있다. 즉, $\beta$ 를 통한 sampling 로 얻은 값 $R_{t+1}$ 에 직전까지 업데이트되어있던 값 $Q(S_{t+1}, A_{t+1})$ 으로 bootstrap 하면 될 것 같다. 하지만 여기서 한가지 결정적인 이슈가 발생한다

그 이슈란 바로 state $S_{t+1} = s’$ 에서 어떻게 다음 action 을 선택할 것인가의 문제이다. Off-policy control 을 지향하기 때문에 target policy $\pi$ 는 이용할 수 없다. 그렇다고 behavior policy $\beta$ 를 이용하면 두 policy 간의 차이로 인한 variance 를 고려해야만 한다. 결론적으로, Q-leaning 의 선택은 $S_{t+1} = s’$ 에서 취할 수 있는 모든 action $a’$ 각각에 대한 값 $Q(s’, a’)$ 을 모두 들여다본 후, 그중에 제일 큰 값 $\max_{a’ \in \mathscr{A}} Q(s’, a’)$ 를 취하는 것이다. 즉,

$R_{t+1} + \gamma Q(S_{t+1}, \arg\max_{a' \in \mathscr{A}} Q(s', a')) \approx R_{t+1}+ \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

의 선택을 하겠다는 것이다. (참고로 최댓값 대신 평균을 취하는 선택을 하는 전략은 Expected Sarsa 라고 불린다.)

종합하면 처음에 나왔던 업데이트 식

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left(R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a') - Q(S_t, A_t)\right)$

를 얻게된다.

Deep Q-learning with experience replay & “target-stable” updates

Algorithm. [2]
initialize $D$ to capacity $N$
initialize $Q$ with random weights $\theta$
initialize $Q^-$ with weights $\theta^- = \theta$
$\texttt{for}$ $episode$ in $\texttt{range}(1, M)$:
$\,\,\,\,\,$ Initialize $s_1 = \{x_1\}$
$\,\,\,\,\,$ Initialize $\phi_1 = \phi(s_1)$
$\,\,\,\,\,$ $\texttt{for}$ $t$ in $\texttt{range}(1,T)$:
$\,\,\,\,\,$ $\,\,\,\,\,$ $\texttt{if} \, coin_\varepsilon == 0$:
$\,\,\,\,\,$ $\,\,\,\,\,$ $\,\,\,\,\,$ select a random $a_t \in \mathscr{A}$
$\,\,\,\,\,$ $\,\,\,\,\,$ $\texttt{else}$:
$\,\,\,\,\,$ $\,\,\,\,\,$ $\,\,\,\,\,$ $a_t = \arg\max Q_\theta(\phi(s_t),a)$
$\,\,\,\,\,$ $\,\,\,\,\,$ execute $a_t$ in emulator
$\,\,\,\,\,$ $\,\,\,\,\,$ observe $r_t$ and $x_{t+1}$
$\,\,\,\,\,$ $\,\,\,\,\,$ $s_{t+1} = s_t \, a_t \, x_{t+1}$
$\,\,\,\,\,$ $\,\,\,\,\,$ $\phi_{t+1} = \phi(s_{t+1})$
$\,\,\,\,\,$ $\,\,\,\,\,$ $D \leftarrow (\phi_t, a_t, r_t, \phi_{t+1})$
$\,\,\,\,\,$ $\,\,\,\,\,$ sample random minibatch $(\phi_j, a_j, r_j, \phi_{j+1})$ from $D$
$\,\,\,\,\,$ $\,\,\,\,\,$ $\texttt{if}$ $episode$ terminates at step $j+1$:
$\,\,\,\,\,$ $\,\,\,\,\,$ $\,\,\,\,\,$ $y_j = r_j$
$\,\,\,\,\,$ $\,\,\,\,\,$ $\texttt{else}$:
$\,\,\,\,\,$ $\,\,\,\,\,$ $\,\,\,\,\,$ $y_j = r_j + \gamma \max_{a’} Q^-_{\theta^-}(\phi_{j+1}, a’)$
$\,\,\,\,\,$ $\,\,\,\,\,$ gradient descent on $(y_j - Q_\theta(\phi_j, a_j))^2$
$\,\,\,\,\,$ $\,\,\,\,\,$ every $C$ steps reset $Q^- = Q$

Why double networks? Deep reinforcement learning 이 tabular reinforcement learning 과 구별되는 중요한 차이 중 하나는 action value 함수는 더 이상
state, action 에만 의존하는 함수가 아니고 네트워크 파라미터 $\theta$ 가 또 하나의 argument 로 추가된다는 것이다. Q-learning 의 경우 네트워크를 구성하는 CNN 파라미터 $\theta$ 가 그것이다. 구체적으로 CNN 은 $\theta$ 에 대한 다음과 같은 함수를 생성하는 역할을 한다.

$\theta \mapsto Q(\,\cdot \, , \cdot \,; \theta) : \mathscr{S} \times \mathscr{A} \rightarrow \mathbb{R}.$

즉, 각 $\theta$ 값은 하나의 state-action value 함수에 대응되는데 이 함수는 임의의 state-action pair $(s, a)$ 에 대한 action value 를 출력한다. 일반적으로, $\theta$ 의 값이 달라지면 같은 $(s, a)$ 에 대해서라도 다른 값을 출력하게 된다.

우선 하나의 네트워크로 Q-learning 알고리즘을 구성하는 경우를 생각해보자. 이 경우 gradient decent step 을 적용하게 되는 loss 함수는 일반적으로 (즉, 에피소드가 끝나기 직전 스텝이 아니기만 하면)

$L_j(\theta):= (r_j + \gamma \max_{a'}Q_\theta(\phi_{j+1},a') - Q_\theta(\phi_j, a_j))^2$

로 주어진다. 설명의 편의를 위하여 $\phi_t = s_t$ 로 단순화하고 batch 업데이트를 이용하지 않는 것으로 가정하고 논의를 진행해보자.

Behavior policy $\beta$ 에 의해 다음과 같이 에피소드가 진행되었다고 하자.

$\cdots, S_t = s_t, A_t = a, R_{t+1} = r_t, S_{t+1} = s_{t+1}, A_{t+1} = a_{t+1}, R_{t+2} = r_{t+2}, S_{t+2} = s_{t+2}, \cdots.$

Timestep $t$ 에서 gradient descent 를 적용하기 직전의 파라미터 값을 $\theta = \theta_0$ 라고 하면, gradient descent 를 취하는 순간 $\theta = \theta_t$ 였던 파라미터는 loss

$L_t(\theta_t) = (r_t + \gamma \max_{a'}Q_{\theta_t}(s_{t+1},a') - Q_{\theta_t}(s_t, a_t))^2$

를 줄이는 방향으로 조금 변화하여 $\theta = \theta_{t+1}$ 이 된다. 이로 인해 높은 확률로 부등식 $L_t(\theta_t) > L_{t+1}(\theta_{t+1})$ 이 성립할 것으로 기대할 수 있다. 그다음 스텝의 업데이트를 위한 loss 는

$L_{t+1}(\theta_{t+1}) = (r_{t+1} + \gamma \max_{a'}Q_{\theta_{t+1}}(s_{t+1},a') - Q_{\theta_{t+1}}(s_t, a_t))^2$

으로 temporal difference 계산을 위한 타겟을 정의하는 함수가 $Q_{\theta_t}$ 에서 $Q_{\theta_{t+1}}$ 로 바뀌어있는 상태이다. 따라서 업데이트 스텝이 진행될 때마다 타겟이 계속 변화함을 알 수 있다.

그럼 이번에는 논문에서 제시된 것과 같이 두 개의 네트워크를 이용하여 업데이트를 하는 경우를 생각해보고 그 차이를 살펴보도록 하자. 이 경우에는 timestep $t$ 에서의 loss 가 다음과 같이 정의된다.

$L_t(\theta_t) = (r_t + \gamma \max_{a'}Q^-_{\theta_t^-}(s_{t+1},a') - Q_{\theta_t}(s_t, a_t))^2.$

여기에서 포인트는 TD 타겟 $r_t + \gamma \max_{a’}Q^-_{\theta_t^-}(s_{t+1},a’)$ 가 더이상 $\theta$ 에 대한 함수가 아니라 상수라는 점이다. 기술된 알고리즘에서 보다시피 현재 주어진 에피소드에 대한 업데이트가 진행되는 $C$ 스텝 동안은 $\theta^-$는 고정된 수이기 때문이다. 따라서 이 기간 동안 타겟은 state-action pair $(s,t)$ 가 무엇이든 관계없이 모두 고정된 함수 $Q^-_{\theta^-}$ 의 함숫값이 된다. 따라서 하나의 네트워크를 이용하는 경우와 비교하여 적어도 $Q^-_{\theta^-}$ 가 고정되는 $C$ 스텝 동안은 타겟

$R_t+j + \gamma \max_{a'}Q_{\theta_{t+1}}(s_{t+1},a') \, (j \in \{0, \ldots, C-1\})$

의 값들 간에 “consistancy” 가 존재하게 된다.

그렇다면 이러한 알고리즘상의 변화가 알고리즘의 성능 향상에 기여할 것인가의 문제가 남았는데, 논문에서는 구현을 통하여 어느 정도 성능향상의 증거를 제시하는 듯 보인다. 성능향상의 근거를 수치적으로 정밀하게 분석하거나 이론적으로 증명하는 것은 간단하지 않을 것으로 보이지만 의미 있는 후속 연구의 방향이 아닐까 생각한다.

참고자료

[1] R. Sutton, A. Barto, Reinforcement learning: an introduction, second edition (final draft).
[2] V. Mnih et al., Human-level control through deep reinforcement learning, Nature vol. 518, 529–533 (26 February 2015).

읽으시다 오류나 부정확한 내용을 발견하시면 꼭 알려주시길 부탁드립니다. 감사합니다.