Policy Gradient

Policy Gradient

01. Deep Reinforcement Learning Overview

Monte Carlo, Sarsa, Q-learning과 같은 일반적인 RL이 state-action value 테이블을 만드는 tabular updating method를 구하는 방법이라면, DRL은 DNN을 통하여 state-action value function이나 policy를 approximating하는 방법이다.

Tabular method를 사용하지 않기 때문에 state 혹은 action space가 continuous한 경우에도 활용 가능하다.

• Deep Q-Network는 DNN을 통해 value function $Q(s, a)$를 approximation 함.
• REINFORCE와 같은 Policy Gradient 방법은 policy $ \pi(a|s)$를 approximation.
• A3C는 value function과 policy를 모두 approximation 함.

02. Policy Gradient algorithm

02.1 Overview

Policy Gradient algorithm은 countinuous action space를 갖는 RL 문제에서 사용된다. DQN이 Q-value값을 학습하여 policy를 정한다면, Policy Gradient algorithm은 optimal policy를 직접적으로 학습한다는 장점이 있다. policy $\pi(a|s)$는 각 state $s$에 대한 action $a$의 확률분포를 나타내는데, parametric policy $\pi_\theta(a|s)$를 neural network를 통해 optimal action의 확률분포를 학습한다.

DQN에서는 neural network를 통해 입력 state에 대하여 모든 action에 대한 Q-value값을 출력했다면, Policy Gradient algorithm은 state가 입력으로 들어오면 $\theta$로 parameterized된 neural network를 통해 action의 확률분포 $(\pi_{\theta}(a|s))$를 얻는다.

DQN vs PG

위의 그림은 DQN과 PG의 차이점을 보여준다. DQN의 경우, state $s$를 입력받으면 Neural Network를 통해 각 action의 Q-value 값을 출력한다. 이러한 특성으로 인해 action space가 매우 크거나 continuous한 경우에는 출력 차원이 매우 커지거나 심지어는 무한대까지 확장되어야 하기 때문에 DQN 사용이 불가능하다. Policy Gradient algorithm을 사용하게 되면 입력 state $s$에 대하여 Neural Network가 policy의 확률 분포를 출력하게 되어 action space가 continuous한 경우에도 활용이 가능하다.

02.2 Objective function & update

$\pi_\theta(a|s)$에 initial state $s_0$가 주어지면 확률적으로 $a_0$를 얻을 수 있다. 이렇게 얻어진 $a_0$에 따라 reward $r_1$이 주어지며 다음 state $s_1$로 transition이 이루어진다. 이 과정을 $T$번 반복하면 다음과 같이 state, action, reward로 이루어진 Trajectory $\tau$를 얻는다.

\[\tau = s_0, a_0, r_1, s_1, a_1, r_2, s_2, \cdots, s_T\]

이 trajectory에 대한 total reward를 $\mathrm{r}(\tau)$라고 한다면 $\mathrm{r}(\tau)$는 trajectory 내에 있는 모든 reward의 합으로 다음과 같이 정의된다.

\[\mathrm{r}(\tau) = \sum_{t=1}^T r_t\]

Policy gradient algorithm은 total reward $\mathrm{r}(\tau)$를 maximize 하도록 학습하기 때문에, parameterized policy $\pi_\theta$에 대한 $\mathrm{r}(\tau)$의 기댓값 $\mathbb{E}_{\pi_\theta}[\mathrm{r}(\tau)]$ 을 objective function으로 한다.

\[J(\theta) = \mathbb{E}_{\pi_\theta}[\mathrm{r}(\tau)] = \int{\mathrm{r}(\tau)\pi_\theta(\tau) d\tau}\]

여기에서 $\pi_\theta(\tau)$는 $\theta$로 parameterized된 policy $\pi$에서 trajectory $\tau$가 나올 확률로 trajectory의 pdf를 의미한다.

optimal $\theta$는 gradient ascent 방법을 사용하여 objective function $J(\theta)$를 maximize해서 얻게 된다.

\[\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)\]

그러면 $\nabla_\theta J(\theta)$는 어떻게 구할까?

02.3 $\nabla_\theta J(\theta)$

\(\nabla_\theta J(\theta)\)는 다음과 같이 정의된다.

\[\nabla_\theta J(\theta) = \nabla_\theta \mathbb{E}_{\pi_\theta}[\mathrm{r}(\tau)] = \mathbb{E}_{\pi_\theta} \Big[\mathrm{r}(\tau)\sum_{t=0}^{T-1}\nabla_\theta \ln \pi_\theta(a_t|s_t)\Big]\]

위 식의 유도과정은 아래와 같다.

\[\begin{aligned} \nabla_\theta J(\theta) & = \nabla_\theta \mathbb{E}_{\pi_\theta}[\mathrm{r}(\tau)]\\ & = \nabla_\theta \int \pi_\theta(\tau) \mathrm{r}(\tau) d\tau\\ & = \int \nabla_\theta \pi_\theta(\tau) \mathrm{r}(\tau) d\tau\\ & = \int \pi_\theta(\tau) \mathrm{r}(\tau) \nabla_\theta \ln \pi_\theta(\tau) d\tau \qquad \because \nabla_\theta \pi_\theta(\tau) = \pi_\theta(\tau)\nabla_\theta \ln \pi_\theta (\tau)\\ & = \mathbb{E}_{\pi_\theta} \big[\mathrm{r}(\tau) \nabla_\theta \ln \pi_\theta(\tau)\big] \end{aligned}\]

이제 $\nabla_\theta \ln \pi_\theta(\tau)$를 정리하면 된다. 먼저 trajectory $\tau = s_0, a_0, r_1, s_1, a_1, \cdots$에 대한 $\pi(\tau)$를 전개해보면 다음과 같다. (Markov property, Chain rule 적용)

\[\begin{aligned} \pi(\tau) & = p(s_0)p(a_0|s_0)p(s_1|s_0, a_0)p(a_1|s_1)p(s_2|s_1, a_1)p(a_2|s_2)\cdots\\ & = p(s_0)\prod_{t=0}^{T-1}p(a_t|s_t)p(s_{t+1}|s_t, a_t)\\ & = p(s_0)\prod_{t=0}^{T-1}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t) \qquad \because p(a_t|s_t) = \pi_\theta(a_t|s_t)\\ \end{aligned}\]

log의 성질에 의해 $\pi(\tau)$에 log를 취하면 다음과 같다.

\[\begin{aligned} \ln \pi(\tau) & = \ln\big[p(s_0)\prod_{t=0}^{T-1}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t)\big]\\ & = \ln p(s_0) + \sum_{t=0}^{T-1} \ln\pi_\theta(a_t|s_t) + \sum_{t=0}^{T-1}\ln p(s_{t+1}|s_t, a_t) \end{aligned}\]

여기에서 $\theta$에 관한 함수인 $\pi_\theta$를 제외하면 모두 상수값이다. 따라서 $\nabla_\theta$를 취하게 되면 $\sum_{t=0}^{T-1}\pi_\theta(a_t|s_t)$을 제외한 모든 항은 0이 된다.

\[\begin{aligned} \nabla_\theta \ln \pi(\tau) & = \nabla_\theta \sum_{t=0}^{T-1}\ln \pi_\theta(a_t|s_t)\\ & = \sum_{t=0}^{T-1} \nabla_\theta \ln \pi_\theta(a_t|s_t) \end{aligned}\]

결과적으로

\[\begin{aligned} \nabla_\theta J(\theta) &= \mathbb{E}_{\pi_\theta} \big[\mathrm{r}(\tau) \nabla_\theta \ln \pi_\theta(\tau)\big]\\ &= \mathbb{E}_{\pi_\theta} \big[\mathrm{r}(\tau) \sum_{t=0}^{T-1} \nabla_\theta \ln \pi_\theta(a_t|s_t)\big] \end{aligned}\]

를 얻을 수 있다.

위의 식은 trajectory 전체에 대한 확률인 $p(\tau;\theta)$와 transition probability $p(s_{t+1}|s_t, a_t)$를 알지 않아도 계산이 가능하다는 장점이 있다.

Expectation $\mathbb{E}_{\pi_\theta}[\cdot]$또한 직접 구할 필요 없이, minibatch를 통해 approximation을 진행한다.

03. REINFORCE

REINFORCE 알고리즘은 위에서 얻은 기본적은 Policy gradient에 몇 가지 변형을 취한다.

\[\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \big[\mathrm{r}(\tau) \sum_{t=0}^{T-1} \nabla_\theta \ln \pi_\theta (a_t|s_t)]\]

• $\mathrm{r}(\tau)$를 discounted return $G_t$로 변경
• $\mathbb{E}_{\pi_\theta}[\cdot]$ 대신 $M$개의 sample을 통한 평균값으로 대체

위와 같은 변형을 취하는 이유는 1. 전체 trajectory를 고려하는 $\mathrm{r}(\tau)$보다 시점 $t$이후의 보상을 고려하는 $G_t$를 사용하여 이미 지난 시점의 보상은 고려 대상에서 제외하여 더 효율적인 policy optimization을 진행, 2. $M$개의 sample만 활용하여 expectation $\mathbb{E}_{\pi_\theta}[\cdot]$를 approximation.

REINFORCE 알고리즘의 objective function은 $M$개의 sample을 통해 $J(\theta)$를 approximation하는 함수로 여기에서는 $\tilde{J}(\theta)$라고 표현하겠다.

\[\nabla_\theta \tilde{J}(\theta) = \frac{1}{M}\sum_{i=1}^{M}\big(\sum_{t=0}^{T-1}G_t^{(i)} \nabla_\theta \ln \pi_\theta (a_t^{(i)}, s_t^{(i)})\big) \approx \nabla_\theta J(\theta)\]

03.1 REINFORCE with baseline

데이터 샘플의