08. Monte-Carlo Policy Gradient

• 참고: Deep Q-learning

Policy-based Reinforcement Learning

Deep Q-learning을 생각해보자. 여기서는 value와 action-value 값을 어떤 parameter $\theta$를 갖는 함수로 모델링하였다.

$$v_{\theta }(s)\approx v^{\pi }(s),Q_{\theta }(s,a)\approx Q^{\pi }(s,a)$$

즉, Deep Q-learning은 value function에 대한 추정을 통해 좋은 policy를 생성하는 것이 목적이다. 이러한 학습 방법을 value-based RL이라고 한다.

Policy-based RL은 value function을 따로 정의하지 않고, policy를 parameterize하여 해당 parameter를 직접적으로 최적화하는 방식을 말한다.

$${\pi }_{\theta }(s,a)=\mathbb{P}[a\mid s,\theta ]$$

Policy-based RL은 일반적으로 value-based에 비해 convergence가 빠르고, stochastic한 policy를 만들어낼 수 있다는 장점이 있다. 특히, action이 단순하지 않고 high-dimensional하거나 continuous한 경우에 효과적이다. 하지만, 일반적으로 local optimum에 도달할 확률이 높고, 또한 policy에 대한 evaluation이 쉽지 않다는 특징도 있다.

Policy Gradient in One-Step MDPs

Parameterized policy ${\pi }_{\theta }(s,a)$의 reward function은 다음과 같다.

$$J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}[r]$$

Policy-based RL은 $J(\theta )$를 maximize하는 best $\theta$를 찾는 것이 목적이기에, gradient ascent와 같은 알고리즘을 사용하기 위해서는 $J(\theta )$에 대한 gradient ${\nabla }_{\theta }J(\theta )$ 계산이 필요하다.

Example: One-Step MDPs

${\nabla }_{\theta }J(\theta )$이 어떤 형태의 값을 갖는지 알아보기 위해 우선 간단한 one-step MDP를 고려해보자. 즉, 하나의 time-step이 지나면 reward $r$과 함께 episode가 종료된다.

이 경우, reward function $J(\theta )$는 다음과 같다.

$$\begin{array}{rl}J(\theta )& ={\mathbb{E}}_{{\pi }_{\theta }}[r]\\ & =\sum _s{d}^{{\pi }_{\theta }}(s)V^{{\pi }_{\theta }}(s)=\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(s,a)R_s^a\end{array}$$

여기서 $d^{{\pi }_{\theta }}(s)$는 ${\pi }_{\theta }$를 따랐을 때의 Markov chain의 stationary distribution을 의미한다.

위 식을 이용하면, ${\nabla }_{\theta }J(\theta )$는 다음과 같다.

$${\nabla }_{\theta }J(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\nabla }_{\theta }{\pi }_{\theta }(s,a)R_s^a$$

이 때, ${\nabla }_{\theta }{\pi }_{\theta }(s,a)$는 likelihood ratio로 표현할 수 있다.

$${\nabla }_{\theta }{\pi }_{\theta }(s,a)={\pi }_{\theta }(s,a)\frac{{\nabla }_{\theta }{\pi }_{\theta }(s,a)}{{\pi }_{\theta }(s,a)}={\pi }_{\theta }(s,a){\nabla }_{\theta }\log {\pi }_{\theta }(s,a)$$

위 식를 이용해서 ${\nabla }_{\theta }J(\theta )$를 다시 쓰면,

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\nabla }_{\theta }{\pi }_{\theta }(s,a)R_s^a\\ & ={\mathbb{E}}_{{\pi }_{\theta }}[{\nabla }_{\theta }\log {\pi }_{\theta }(s,a)r]\end{array}$$

이 때, ${\nabla }_{\theta }\log {\pi }_{\theta }(s,a)$를 score function이라고 부른다.

즉, sample을 통해 직접적으로 gradient 계산이 가능하다.

Softmax Policy: Discrete Actions

Action space가 discrete한 경우에 많이 사용되는 policy로는 softmax policy가 있다. Softmax policy의 경우, 각 action에 대해서 state-action feature vector $\varphi (s,a)$를 이용하여 다음과 같이 확률을 부여한다.

$${\pi }_{\theta }(s,a)=\frac{\exp (\varphi (s,a{)}^T\theta )}{{\sum }_b\exp (\varphi (s,b{)}^T\theta )}$$

Softmax policy에 nonlinearity를 부여하기 위해 $\varphi (s,a)$를 neural net으로 변경할 수도 있다.

Softmax policy의 score function은 다음과 같다.

$${\nabla }_{\theta }\log {\pi }_{\theta }(s,a)=\varphi (s,a)-{\mathbb{E}}_{{\pi }_{\theta }}[\varphi (s,\cdot )]$$

Gaussian Policy: Continuous Actions

반대로, action space가 continuous한 경우 주로 Gaussian policy가 사용된다.

$$a\sim N(\mu (s),{\sigma }^2)$$

여기서 mean은 state feature로써 표현된다: $\mu (s)=\varphi (s{)}^T\theta$. Variance는 일반적으로 constant로 고정시키지만, parameterize할 수도 있다.

Gaussian policy 역시 $\varphi (s)$를 neural net으로 변경하여 nonlinearity를 부여할 수 있다.

Gaussian policy의 score function은 다음과 같다.

$${\nabla }_{\theta }\log {\pi }_{\theta }(s,a)=\frac{(a-\mu (s))\varphi (s))}{{\sigma }^2}$$

Monte-Carlo Policy Gradient

Policy Gradient Theorem

앞서 살펴본 one-step MDP에 적용한 policy gradient 접근 방법을 multi-step MDPs로 일반화할 수 있다. 다음 Theorem은 One-step MDP에서의 reward $r$을 long-term value $Q^{{\pi }_{\theta }}(s,a)$로 대체하는 것으로 유도할 수 있다.

Theorem: Policy Gradient Theorem For any differentiable policy ${\pi }_{\theta }$ and any policy objective function, the policy gradient is

\nabla_\theta J(\theta) = \mathbb{E}{\pi\theta} [\nabla_\theta \log \pi_\theta(s, a) ; Q^{\pi_\theta}(s,a) ]

REINFORCEMENT Algorithm

Policy gradient theorem에 기반하여 Monte-Carlo estimation을 이용하면 policy gradient RL이 가능해진다. 이를 REINFORCEMENT 알고리즘이라고 한다.

REINFORCEMENT 알고리즘은 $Q^{{\pi }_{\theta }}(s,a)$에 대한 unbiased sample로 return $G_t$를 사용한다.

$$\Delta {\theta }_t=\alpha {\nabla }_{\theta }\log {\pi }_{\theta }(s_t,a_t)G_t$$

REINFORCEMENT 알고리즘의 pseudocode는 다음과 같다.

1. $\theta$를 임의의 값으로 초기화한다.

2. 각 episode $\{s_1,a_1,r_2,\cdots ,s_{T-1},a_{T-1},r_T\}\sim {\pi }_{\theta }$에 대해, $t=1\cdots T-1$ 동안 아래 식을 이용해서 update 진행.

   $$\theta \leftarrow \theta +\alpha {\nabla }_{\theta }\log {\pi }_{\theta }(s_t,a_t)G_t$$

3. 2번을 반복적으로 수행 후, 최종 $\theta$ return.