PG REINFORCE

Monte-Carlo Policy Gradient(REINFORCE)

Introduction

1. The gradient-ascent algorithm maximizing $J(\theta )$ is $$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }J({\theta }_t)\\ & ={\theta }_t+\alpha \mathbb{E}\left[q_{\pi }(S_t,A_t){\nabla }_{\theta }\ln \pi (A_t|S_t,{\theta }_t)\right]\end{array}$$
2. Since the true gradient is unknown, we can replace it by a stochastic one: $$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha q_{\pi }(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\end{array}$$
3. Furthermore, since $q_{\pi }$ is unknown, it can be replaced by an estimate: $$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha q_t(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\end{array}$$

Implementation

If $q_{\pi }$ is estimated by Monte Carlo estimation, then the algorithm is called REINFORCE.

Version 1

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Policy Gradient by Monte Carlo (REINFORCE)}\\ & \text{Initialization: }\text{Initial parameter }\theta ,\gamma \in (0,1),\alpha >0\\ & \text{For each episode, do:}\\ & \text{Generate episode }{s}_0,a_0,r_1,s_1,\dots ,s_{T-1},a_{T-1},r_T\text{ following }\pi (\theta ).\\ & \text{For }t=0,1,\dots ,T-1:\\ & \text{Value update: }{q}_t(s_t,a_t)=\sum _{k=t+1}^T{\gamma }^{k-t-1}{r}_k\\ & \text{Policy update: }\theta \leftarrow \theta +\alpha q_t(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )\end{array}}$$

Version 2

可以看到上面计算g时很多地方都是重复计算了，我们优化这部分的计算，同时我们按照之前的想法引入常数C，使得最终的更新公式变得更加简洁：

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Policy Gradient by Monte Carlo (REINFORCE)}\\ & \text{Initialization: }\text{Initial parameter }\theta ,\gamma \in (0,1),\alpha >0,C=1/(1-\gamma )\\ & \text{For each episode, do:}\\ & G=0\\ & \text{Generate episode }{s}_0,a_0,r_1,s_1,\dots ,s_{T-1},a_{T-1},r_T\text{ following }\pi (\theta ).\\ & \text{For }t=T-1,T-2,\dots ,0:\\ & \text{Value update: }G=\gamma G+r_{t+1}\\ & \text{Policy update: }\theta \leftarrow \theta +\alpha CG{\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )\end{array}}$$

复习：MC是offline的

我们这里是不能做到边收集数据边更新的，一定要等episode结束之后才能更新。后面介绍TD版本的方法就可以做incremental update(online)了

Remarks

How to do sampling?

$${\mathbb{E}}_{S_t\sim \mu ,A_t\sim \pi }\left[q_{\pi }(S_t,A_t){\nabla }_{\theta }\ln \pi (A_t|S_t,\theta )\right]⟶q_{\pi }(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )$$

• How to sample $S_t$?
  • $S_t\sim \mu$, where the on-policy distribution $\mu$ is a long-run behavior under $\pi$.
  • In practice, people usually do not care about it.
• How to sample $A_t$?
  • $A_t\sim \pi (A_t|S_t,\theta )$. Hence, $a_t$ should be sampled following $\pi ({\theta }_t)$ at $s_t$.
  • Therefore, policy gradient methods are on-policy.

How to interpret this algorithm?

Since

$${\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )=\frac{{\nabla }_{\theta }\pi (a_t|s_t,\theta )}{\pi (a_t|s_t,\theta )}$$

the algorithm can be rewritten as

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha q_t(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )\\ & ={\theta }_t+\alpha q_t(s_t,a_t)\frac{{\nabla }_{\theta }\pi (a_t|s_t,\theta )}{\pi (a_t|s_t,\theta )}\\ & ={\theta }_t+\alpha \underset{{\beta }_t}{\underbrace{\left(\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,\theta )}\right)}}{\nabla }_{\theta }\pi (a_t|s_t,\theta )\\ & ={\theta }_t+\alpha {\beta }_t{\nabla }_{\theta }\pi (a_t|s_t,\theta )\end{array}$$

这里对$\pi$用一下泰勒一次展开

When ${\theta }_{t+1}-{\theta }_t$ is sufficientlt small:

$$\begin{array}{rlrl}\pi (a_t|s_t,{\theta }_{t+1})& \approx \pi (a_t|s_t,{\theta }_t)+({\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){)}^T({\theta }_{t+1}-{\theta }_t)& & \\ & =\pi (a_t|s_t,{\theta }_t)+({\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){)}^T\alpha {\beta }_t{\nabla }_{\theta }\pi (a_t|s_t,\theta )& & (\text{substitute }{\theta }_{t+1}-{\theta }_t)\\ & =\pi (a_t|s_t,{\theta }_t)+\alpha {\beta }_t\Vert {\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){\Vert }^2& & (\text{rearrange terms})\end{array}$$

Interpretation:

• If $q_t(s_t,a_t)>0\to {\beta }_t>0$, then the probability of choosing $(s_t,a_t)$ is increased. $$\pi (a_t|s_t,{\theta }_{t+1})>\pi (a_t|s_t,{\theta }_t)$$
• If $q_t(s_t,a_t)<0\to {\beta }_t<0$, then the probability of choosing $(s_t,a_t)$ is decreased. $$\pi (a_t|s_t,{\theta }_{t+1})<\pi (a_t|s_t,{\theta }_t)$$

${\beta }_t$ can balance exploration and exploitation.

• $q_t(s_t,a_t)\uparrow$ -⇒ ${\beta }_t\uparrow$ -⇒ $\pi (a_t|s_t,{\theta }_{t+1})\uparrow$, intends to exploit actions with greater values.
• $\pi (a_t|s_t,\theta )\downarrow$ -⇒ $|{\beta }_t|\uparrow$ -⇒ $|\pi (a_t|s_t,{\theta }_{t+1})-\pi (a_t|s_t,{\theta }_t)|\uparrow$, intends to explore actions with lower probabilities if q>0, intends to give up actions with lower probabilities if q<0.