D-DL4CV-Lec21f-REINFORCE_Algorithm

Simple Conclusion

Statement

Let $x=(s_0,a_0,s_1,a_1,\dots )$ be the sequence of states and actions we get when following policy ${\pi }_{\theta }$ which is sampled from $x\sim p_{\theta }(x)$

Then

$$J(\theta )={\mathbb{E}}_{x\sim p_{\theta }}[f(x)]$$

and we can calculate the gradient by

$$\frac{\partial J}{\partial \theta }=\frac{\partial }{\partial \theta }{\mathbb{E}}_{x\sim p_{\theta }}\left[f(x)\right]={\mathbb{E}}_{x\sim p_{\theta }}\left[f(x)\sum _{t\ge 0}\frac{\partial }{\partial \theta }\log {\pi }_{\theta }(a_t|s_t)\right]$$

Intuition

When $f(x)$ is high, increase the probability of the action we took, and vice versa

Steps

• Initial random weights $\theta$
• Repeat:
  • Collect trajectories $x$ and reward $f(x)$ using policy ${\pi }_{\theta }$
  • Compute $\partial J/\partial \theta$
  • Gradient ascent on $\theta$

---

Derivation

Objective

We want to find expression for $\partial J/\partial \theta$ which is able to be computed effectively

Derivation

Revise Original Expression

$$\begin{array}{rl}\frac{\partial J}{\partial \theta }& =\frac{\partial }{\partial \theta }{\mathbb{E}}_{x\sim p_{\theta }}[f(x)]=\frac{\partial }{\partial \theta }{\int }_X{p}_{\theta }(x)f(x)dx={\int }_{X}f(x)\frac{\partial }{\partial \theta }{p}_{\theta }(x)dx\\ & ={\int }_{X}f(x)p_{\theta }(x)\frac{\partial }{\partial \theta }\log p_{\theta }(x)dx\\ & ={\mathbb{E}}_{x\sim p_{\theta }}\left[f(x)\frac{\partial }{\partial \theta }\log p_{\theta }(x)\right]\end{array}$$

The second to last ”=” comes from:

$$\frac{\partial }{\partial \theta }\log p_{\theta }(x)=\frac{1}{p_{\theta }(x)}⟹\frac{\partial }{\partial \theta }{p}_{\theta }(x)=p_{\theta }(x)\frac{\partial }{\partial \theta }\log p_{\theta }(x)$$

Compute $\frac{\partial }{\partial \theta }\log p_{\theta }(x)$

$$\begin{array}{rl}& p_{\theta }(x)=\prod _{t\ge 0}P(s_{t+1}|s_t,a_t){\pi }_{\theta }(a_t|s_t)\\ ⟹& \log p_{\theta }(x)=\sum _{t\ge 0}\left(\log P(s_{t+1}|s_t,a_t)+\log {\pi }_{\theta }(a_t|s_t)\right)\end{array}$$

$P(s_{t+1}|s_t,a_t)$ is impossible to compute because transition is decided by the environment, which we can’t backpropagate

However, surprisingly, we’ll eliminate this term when computing gradient

$$\frac{\partial }{\partial \theta }\log p_{\theta }(x)=\sum _{t\ge 0}\frac{\partial }{\partial \theta }\log {\pi }_{\theta }(a_t|s_t)$$

Conclusion

Putting the two derivations together we have:

$$\frac{\partial J}{\partial \theta }=\frac{\partial }{\partial \theta }{\mathbb{E}}_{x\sim p_{\theta }}\left[f(x)\right]={\mathbb{E}}_{x\sim p_{\theta }}\left[f(x)\sum _{t\ge 0}\frac{\partial }{\partial \theta }\log {\pi }_{\theta }(a_t|s_t)\right]$$