PPO presentation outline

What is Reinforcement Learning?

Quick informal recap of what RL is, for the audience to get the vibe

Recap

Reminder of MDPs

Remind the audience of the basic structure of an MDP

• S: state space
• A: action space
• P: state transition probability function
• R: reward function

Policy

A policy is just a mapping from states to actions, it can be deterministic or it van be stochastic

Value functions

• return

$$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\dots$$

• state value:

$$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid s_t=s]$$

• action value:

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid s_t=s,a_t=a]$$

Value functions visual representation

insert graphic of one step lookahead

Algorithms

Value based

learn a value function, and derive a policy from the values (e.g. $\epsilon$-greedy)

we will not talk about these, only the pros and cons

pros:

• easy to understand
• easy to implement
  cons:
• really hard for high dimensional state and/or action spaces
• hard to learn stochastic policy

Policy based

Directly learn a policy, no need for intermediary value function

pros:

• easily adaptable for high dimensional state and/or action spaces
  cons:
• can get stuck in local optima

Value based vs Policy based

insert infographic

Policy gradient

Define a loss function and change the parameters of the policy in the steepest direction

Some examples of objecitve functions:

• If the problem is episodic, meaning that it always starts at state $s_1$ and terminates eventually and restarts at $s_1$, then the objective function of taking the state value of the starting state makes sense:

$$J_1(\theta )=V^{{\pi }_{\theta }}\left(s_1\right)={\mathbb{E}}_{{\pi }_{\theta }}\left[v_1\right]$$

• For continuing environments, that is an environment that does not terminate and restert, but keeps on rolling, the average value of the states weighted by their stationary distribution works:

$$J_{avV}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)V^{{\pi }_{\theta }}(s)$$

• Still for continuing environments, we can also take the average reward after a single step and weigh it by the stationary distibution:

$$\begin{array}{c}{J}_{avR}(\theta )=\sum _s{d}^{{\pi }_{\theta }}(s)\sum _a{\pi }_{\theta }(s,a){\mathcal{R}}_s^a\end{array}$$

Policy gradient theorem

For any differentiable policy ${\pi }_{\theta }$, for any policy objective function $J$, the policy gradient is the following:

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

where $Q^{{\pi }_{\theta }}(s,a)$ is the long-term value of a state action pair.

Actor Critic

Approximate $Q^{{\pi }_{\theta }}$ (Critic) some way and use the approximate $Q$ to update the parameters of the Actor

We will not explain how to approximate $Q$ in this presentation

Baseline function

The policy gradient theorem still holds if we subtract a baseline function from $Q$

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

we can take the state value function as a baseline: $B(s)=V^{{\pi }_{\theta }}(s)$

Advantage function

$$A^{{\pi }_{\theta }}(s,a)=Q^{{\pi }_{\theta }}(s,a)-V^{{\pi }_{\theta }}(s)$$ $${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}[{\nabla }_{\theta }\log {\pi }_{\theta }(s,a)\cdot A^{{\pi }_{\theta }}(s,a)]$$

Estimating the advantage function

$$Q^{{\pi }_{\theta }}(s,a)=\mathbb{E}[G_t\mid s,a]={\mathbb{E}}_{{\pi }_{\theta }}[r+\gamma V^{{\pi }_{\theta }}(s^{\prime })\mid s,a]$$ $$A^{{\pi }_{\theta }}(s,a)={\mathbb{E}}_{{\pi }_{\theta }}[r+\gamma V^{{\pi }_{\theta }}(s^{\prime })\mid s,a]-V^{{\pi }_{\theta }}(s)$$

introduce the td error:

$${\delta }^{{\pi }_{\theta }}=r+\gamma V^{{\pi }_{\theta }}(s^{\prime })-V^{{\pi }_{\theta }}(s)$$ $${\mathbb{E}}_{{\pi }_{\theta }}[{\delta }^{{\pi }_{\theta }}\mid s,a]=A^{{\pi }_{\theta }}(s,a)$$

so the td error is an unbiased estimator of the advantage function

Generalized Advantage Estimator

A single step TD error may result in high variance, thsu we introduce the following:

$$A_t^{(k)}=\sum _{m=0}^{k-1}{\gamma }^m{\delta }_{t+1}^{{\pi }_{\theta }}=-V^{{\pi }_{\theta }}(s_t)+r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots +{\gamma }^k{V}^{{\pi }_{\theta }}(s_{t+k})$$

as $k$ increases, the variance decreases

$$A_t^{\text{GAE}}=(1-\lambda )\left(A_t^{(1)}+\lambda A_t^{(2)}+{\lambda }^2{A}_t^{(3)}+\dots \right)$$

Clipped Surrogate Objective

$$L^{\text{CLIP}}(\theta )={\hat{\mathbb{E}}}_t\left[\min \left(r_t(\theta ){\hat{A}}_t,\mathrm{clip}\left(r_t(\theta ),1-ϵ,1+ϵ\right){\hat{A}}_t\right)\right]$$

PPO (finally)

for each iteration, run the $N$ parallel environments for $T$ timesteps ($T\ne$ episode length), optimize the loss function $L$ with respest to $\theta$ for $K$ epochs and minibatch size $M$