REINFORCE

Spinnig Up: Intro to Policy Optimization | code

The goal of reinforcement learning is to find an optimal behavior strategy for the agent to obtain optimal rewards. The policy gradient methods target at modeling and optimizing the policy directly. The policy is usually modeled with a parameterized function respect to $\theta ,{\pi }_{\theta }(a|s)$. The value of the reward (objective) function depends on this policy and then various algorithms can be applied to optimize $\theta$ for the best reward.

• it is on-policy
• can be used for both discrete and continuous action spaces

We have a stochastic, parameterized policy, ${\pi }_{\theta }$ and want to maximize the expected return $J({\pi }_{\theta })=\underset{\tau \sim {\pi }_{\theta }}{\mathbb{E}}[R(\tau )]$, so we are going to optimize the policy parameters $\theta$ via gradient ascent:

$${\theta }_{k+1}={\theta }_k+\alpha +{\nabla }_{\theta }J({\pi }_{\theta }){|}_{{\theta }_k}$$

The ${|}_{{\theta }_k}$ is just a very explicit notation, that the gradient is calculated with a specific set of parameters in time - I think.
${\nabla }_{\theta }J({\pi }_{\theta })$, the gradient of the policy performance is called policy gradient.
Policy gradient algorithms are e.g. VPG, TRPO, PPO.

derivation for basic policy gradient

The Probability of a Trajectory $\tau =(s_0,a_0,\dots ,s_{T+1})$ given that actions ome from ${\pi }_{\theta }$ is

$$P(\tau |\theta )={\rho }_0(s_0)\prod _{t=o}^{T}P{(}_{t+1}|s_t,a_t){\pi }_{\theta }(a_t|s_t)$$

($\rho$ is the start state distribution, see Introduction to RL)

The Log-Derivative Trick:

log-derivative trick

The derivative of a function is the function times the derivative of its log:

$$\begin{array}{rl}\frac{d}{dx}\log f(x)& =\frac{1}{f(x)}\cdot f^{\prime }(x)\\ f(x)\frac{d}{dx}\log f(x)& =f^{\prime }(x)\end{array}$$

This can be useful, when you are dealing with products in the derivative, as the log will turn products into a sum, e.g.:

$$\frac{d}{dx}\log (f(x)g(x)h(x))=\frac{f^{\prime }(x)}{f(x)}+\frac{g^{\prime }(x)}{g(x)}+\frac{h^{\prime }(x)}{h(x)}$$

… as opposed to this:

$$\frac{d}{dx}f(x)g(x)h(x)=f^{\prime }(x)g(x)h(x)+f(x)g^{\prime }(x)h(x)+f(x)g(x)h^{\prime }(x)$$ Link to original

So we can write

$${\nabla }_{\theta }P(\tau |\theta )=P(\tau |\theta ){\nabla }_{\theta }\log P(\tau |\theta )$$

For the Log-Probability of the Trajectory, we can then turn the products into sums:

$$\log P(\tau |\theta )=\log {\rho }_0(s_0)+\sum _{t=0}^T\left(\log P(s_{t+1}|s_t,a_t)+\log {\pi }_{\theta }(a_t|s_t)\right)$$

The environment has no dependence on $\theta$, so gradients of ${\rho }_0(s_0),P(s_{t+1}|s_t,a_t),\text{and}R(\tau )$ are zero.
Why? The actions directly influence the environment, but the network internal parameters do not directly influence the parameters. $\theta$ and ${\theta }^{\prime }$ can lead to the same action in some states, or even to the same policies. The environment only depends on its current state and the actions it receives to generate the next state: $P(s_{t+1}|a_t,s_t)$

The gradient of the log-probability of a trajectory is thus

$$\begin{array}{rl}{\nabla }_{\theta }\log P(\tau |\theta )& =\cancel{{\nabla }_{\theta }\log {\rho }_0(s_0)}+\sum _{t=0}^T\left(\cancel{{\nabla }_{\theta }\log P(s_{t+1}|s_t,a_t)}+{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\right)\\ & =\sum _{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\end{array}$$

Putting it together, we derive the following:

Derivation for Basic Policy Gradient

$$\begin{array}{rlr}{\nabla }_{\theta }J({\pi }_{\theta })& ={\nabla }_{\theta }{\mathbb{E}}_{\tau \sim {\pi }_{\theta }}\left[R(\tau )\right]& \\ & ={\nabla }_{\theta }{\int }_{\tau }P(\tau |\theta )R(\tau )& \text{Expand expectation}\\ & ={\int }_{\tau }{\nabla }_{\theta }P(\tau |\theta )R(\tau )& \text{Bring gradient under integral}\\ & ={\int }_{\tau }P(\tau |\theta ){\nabla }_{\theta }\log P(\tau |\theta )R(\tau )& \text{Log-derivative trick}\\ & =\underset{\tau \sim {\pi }_{\theta }}{\mathbb{E}}\left[{\nabla }_{\theta }\log P(\tau |\theta )R(\tau )\right]& \text{Return to expectation form}\\ \therefore {\nabla }_{\theta }J({\pi }_{\theta })& =\underset{\tau \sim {\pi }_{\theta }}{\mathbb{E}}\left[\sum _{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)R(\tau )\right]& \text{Expression for grad-log-prob}\end{array}$$

${\int }_{\tau }$ means that wer are integrating over all possible trajectories.
We estimate the expectation of the policy gradient with a set of $\mathcal{D}=\{{\tau }_i{\}}_{i=1},\dots ,N$ trajectories, where each trajectory is obtained by letting the agent act in the environment using the policy ${\pi }_{\theta }$ :

$${\nabla }_{\theta }J({\pi }_{\theta })\approx \frac{1}{|\mathcal{D}|}\sum _{\tau \in \mathcal{D}}\sum _{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)R(\tau )$$

where $\frac{1}{|\mathcal{D}|}=N=$ number of trajectories.

---

The reward function is defined as:

$$J(\theta )=\sum _{s\in \mathcal{S}}{d}^{\pi }(s)V^{\pi }(s)=\sum _{s\in \mathcal{S}}{d}^{\pi }(s)\sum _{a\in \mathcal{A}}{\pi }_{\theta }(a|s)Q^{\pi }(s,a)$$

where $d^{\pi }(s)$ is the stationary distribution of Markov chain for ${\pi }_{\theta }$ (on-policy sate d)

The expected finite-horizon undiscounted return $J$ is

$${\nabla }_{\theta }J({\pi }_{\theta })=\underset{\tau \sim {\pi }_{\theta }}{\mathbb{E}}[R(\tau )]=\underset{\tau \sim {\pi }_{\theta }}{\mathbb{E}}\left[\sum _{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)A^{{\pi }_{\theta }}(s_t,a_t)\right]$$

$\tau \dots$ trajectory
$A^{{\pi }_{\theta }}\dots$ advantage function of current policy
(the log simplifies the gradient calculation, as it turns the product of probabilities into a sum)

The weights are updated via stochastic gradient ascent:

$${\theta }_{k+1}={\theta }_k+\alpha {\nabla }_{\theta }J({\pi }_{{\theta }_k})$$

Policy gradient implementations typically compute advantage function estimates based on the infinite-horizon discounted return, despite otherwise using the finite-horizon undiscounted policy gradient formula.

References

https://spinningup.openai.com/en/latest/algorithms/vpg.html

https://medium.com/@sofeikov/reinforce-algorithm-reinforcement-learning-from-scratch-in-pytorch-41fcccafa107

reinforcement learning