The policy\pi defines the action probabilities, P(A_t | S_t).
The horizonT, i.e. number of steps (either finite or infinite).
The discount factor\gamma (with 0 < \gamma \le 1).
Horizon and discount factor:
For finite horizon, we usually take \gamma = 1.
For infinite horizon, we usually take \gamma < 1,
Ensure that the objective is not infinite (assuming that the rewards are bounded).
This favors immediate rewards rather than delayed rewards.
This can be interpreted as a (1 - \gamma) probability that the execution stops after each time step.
Note: continuous state and action spaces
For simplicity, I am assuming here finite state and action space for the formulas in most places. This makes the formulas more approachable for people who are not much comfortable with integrals, probability densities and general distributions, etc. The formulas can be generalized for continuous state and action spaces in most cases.
Policy
For finite horizon problems, the action usually depends on the current time t:
i.e. \pi = (\pi_0, \ldots, \pi_{H-1})
For deterministic policies: A_t = \pi_t(S_t)
For stochastic policies: (A_t | S_t = s) \sim \pi_t(s)
For infinite horizon problems, the action selection does not need to depend on the current time t:
For deterministic policies: A_t = \pi(S_t)
For stochastic policies: (A_t | S_t = s) \sim \pi(s)
Additional definitions
The return (or reward-to-go) G_t is the (discounted) sum of the rewards R_t: G_t \triangleq \sum_{u=t}^{H-1} \gamma^{u-t} R_u
We define R(s,a) as the expected reward given S_t = s and A_t = a: R(s,a) \triangleq \mathbb{E} \left[ R_t | S_t = s, A_t = a \right] = \underset{r \sim \mathcal{R}(s,a)}{\mathbb{E}} \left[ r \right]
A trajectory\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots) (or an episode) is a sequence of states, actions and rewards.
We note R(\tau) the return for a given trajectory \tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots): R(\tau) \triangleq \sum_{t=0}^{H-1} \gamma^t r_t
We note J(\pi) the utility function, i.e. the expected return for policy \pi: J(\pi) \triangleq \mathbb{E}\left[G_0 | \pi\right] = \mathbb{E}\left[\sum_{t=0}^{H-1} \gamma^t R_t | \pi\right] = \mathbb{E}\left[ R(\tau) | \pi\right] = \mathbb{E}\left[ V^\pi(S_0) \right]
Value of a policy
The value function of a policy \pi gives the expected return when following policy \pi starting from state S_0 = s: V^\pi(s) \triangleq \mathbb{E} \left[ G_0 | S_0 = s, \pi \right] = \mathbb{E} \left[ \sum_{t=0}^{H-1} \gamma^t R^t | S_0 = s, \pi \right]
The action-value function (or Q-function) of a policy \pi gives the expected return when taking action a in state s and then following policy \pi: Q^\pi(s,a) \triangleq \mathbb{E} \left[ G_0 | S_0 = s, A_0 = a, \pi \right] = \mathbb{E} \left[ \sum_{t=0}^{H-1} \gamma^t R^t | S_0 = s, A_0 = a, \pi \right]
The advantage function, gives the advantage of taking action a in state s and then following \pi instead of following \pi immediately: A^\pi(s,a) \triangleq Q^\pi(s,a) - V^\pi(s)
In finite horizon, the functions depend on the current time stamp t: \begin{aligned} V^\pi_t & \triangleq \mathbb{E} \left[ G_t | S_t = s, \pi \right] && = \mathbb{E} \left[ \sum_{u=t}^{H-1} \gamma^u R^u | S_t = s, \pi \right] \\ Q^\pi_t & \triangleq \mathbb{E} \left[ G_t | S_t = s, A_t = a, \pi \right] && = \mathbb{E} \left[ \sum_{u=t}^{H-1} \gamma^u R^u | S_t = s, A_t = a, \pi \right] \\ A^\pi_t & \triangleq Q^\pi_t(s,a) - V^pi_t(s) \end{aligned}
Bellman equation
When using infinite horizon, the Bellman equations characterizes the value function (and action-value function) of a policy \pi: \begin{aligned} V^\pi(s) & = \underset{a \sim \pi(s), s' \sim \mathcal{T}(s,a) }{\mathbb{E}} \left[ R(s, a) + \gamma V^\pi(s') \right] \\ Q^\pi(s, a) & = R(s, a) + \gamma \underset{s' \sim \mathcal{T}(s,a), a' \sim \pi(s')}{\mathbb{E}} \left[ Q^\pi(s', a') \right] \end{aligned}
For discrete state and action spaces: \begin{aligned} V^\pi(s) & = \sum_{a} \pi(a|s) \left[ R(s, a) + \gamma \sum_{s'} \mathcal{T}(s'|s,a) \, V^\pi(s') \right] \\ Q^\pi(s, a) & = R(s, a) + \gamma \sum_{s',a'} \mathcal{T}(s'|s,a) \, \pi(a'|s') \, Q^\pi(s', a') \end{aligned}
For discrete state space and deterministic policies: \begin{aligned} V^\pi(s) & = R(s, \pi(s)) + \gamma \sum_{s'} \mathcal{T}(s'|s,\pi(s)) \, V^\pi(s') \\ Q^\pi(s, a) & = R(s, a) + \gamma \sum_{s'} \mathcal{T}(s'|s,a) \, Q^\pi(s', \pi(s')) \end{aligned}
Policy Evaluation
The policy Evaluation algorithm computes the value function of a given policy \pi by iterative computation of approximations of V^\pi
In infinite horizon, the following algorithm estimates V^\pi: \begin{aligned} V_0(s) & \leftarrow 0 \text{ (or any other value)} \\ V_{k+1}(s) & \leftarrow \sum_a \pi(a|s) \left[ R(s, a) + \gamma \sum_{s'} \mathcal{T}(s'|s,a) V_k(s') \right] \end{aligned}
This converges to V^\pi: V_k(s) \overset{k \rightarrow \infty}\longrightarrow V^\pi(s).
In finite horizon, we can compute the value function t each time stamp V^\pi_t: \begin{aligned} V^\pi_H(s) & \leftarrow 0 \\ V^\pi_{t-1}(s) & \leftarrow \sum_a \pi(a|s) \left[ R(s, a) + \gamma \sum_{s'} \mathcal{T}(s'|s,a) V^\pi_t(s') \right] \end{aligned}
Planning
Computing the optimal policy when the world model is known.
Optimal policy
A policy \pi^\star is optimal if its value function is at least as high as the value function of any other policy (for all states): \forall \pi, \forall s, V^{\pi^\star}(s) \ge V^\pi(s)
There can be more than one optimal policy.
A deterministic optimal policy always exists. We can assume that the policy is deterministic: A_t = \pi(S_t)
The optimal value/action-value/advantage functions, V^\star(s), Q^\star(s,a) and A^\star(s,a), is the value/action-value/advantage functions of a/any optimal policy: \begin{aligned} V^\star(s) & = V^{\pi^\star}(s) && = \max_\pi V^\pi(s) \\ Q^\star(s,a) & = Q^{\pi^\star}(s,a) &&= \max_\pi Q^\pi(s,a) \\ A^\star(s,a) & = A^{\pi^\star}(s,a) &&= Q^\star(s,a) - V^\star(s) \end{aligned}
Note: using the optimal value functions
We can derive (a) the optimal policy \pi^\star from V^\star(s) if we know the world model (R(s,a) and \mathcal{T}(s'|s,a)): \pi^\star(s) = \argmax_a \left[ R(s,a) + \gamma \sum_{s'} \mathcal{T}(s' | s,a) V^\star(s') \right]
We can derive the optimal policy from Q^\star(s,a) without the world model: \pi^\star(s) = \argmax_a Q^\star(s,a)
If we learn Q^\star (Q-learning), we can directly use it to derive the optimal policy.
with \alpha, the learning rate ( 0 < \alpha < 1 ).
Monte Carlo estimation (where \text{target} = g_t is the value of the return G_t): V(s_t) \leftarrow V(s_t) + \alpha \overbrace{\left( g_t - V(s_t) \right)}^\text{MC error} = (1 - \alpha) \, V(s_t) + \alpha \, g_t
Instead of using a tabular value function, we can use a parametric function V_\phi(s).
We can minimize the squared-error loss: \mathcal{L}(\phi) \triangleq \frac{1}{|\mathcal{D}|} \sum_{s,\text{target}} \left( \text{target} - V_\phi(s) \right)^2
This gives the following gradient: \nabla_\phi \mathcal{L}(\phi) = - \frac{2}{|\mathcal{D}|} \sum_{s,\text{target}} \left( \text{target} - V_\phi(s) \right) \nabla_\phi V_\phi(s)
Monte Carlo estimation uses the reward to go of a single trajectory (g = R(\tau)) as target: \phi \leftarrow \phi + \alpha \left( g_t - V_\phi(s_t) \right) \nabla_\phi V_\phi(s_t)
Instead of using a tabular value function, we can use a parametric function Q_\phi(s,a). For example, this can be a neural network taking the state as input and with one output neuron per action value.
SARSA with function approximation: \phi \leftarrow \phi + \alpha \left[ r + \gamma Q_{\bar{\phi}}(s',a') - Q_\phi(s,a) \right] \nabla_\phi Q_\phi(s,a)
Q-learning
In Q-learning (off-policy TD control[1]), we learn the optimal action-value function Q^\star, or an approximation of it (\hat{Q}^\star \approx Q^\star), from (off-policy) trajectories. We can then use this learned function to choose the best action for a given state: \begin{aligned} \pi^\star(s) = \argmax_{a} Q^\star(s,a) \\ \hat\pi^\star(s) = \argmax_{a} \hat{Q}^\star(s,a) \end{aligned}
Tabular Q-learning
In tabular Q-learning, the value function Q(s,a) is represented as a table: Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]
This assumes that the state space and the action space are finite and is not practical if the action and state spaces are not too big. One drawback is that there is no generalization across states and actions.
The algorithm is:
Generate a action a for current state s, typically using an ε-greedy policy for Q and obtain transition (s,a,r,s')
Tabular Double Q-learning learns two functions Q and Q' in order to mitigate the maximization bias: \begin{aligned} Q(s,a) & \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q'(s', \argmax_{a'} Q(s',a')) - Q(s,a) \right] \\ Q'(s,a) & \leftarrow Q'(s,a) + \alpha \left[ r + \gamma Q(s', \argmax_{a'} Q'(s',a')) - Q'(s,a) \right] \end{aligned}
Q-Networks
Q-networks: using Q-learning with function approximation (i.e. neural networks). When the Q-networks are deep neural networks, we have Deep Q-learning.
We can minimize the a mean squared error loss of the form: \mathcal{L}(\phi) \triangleq \frac{1}{|\mathcal{D}|} \sum_{(s,a,r,s') \in \mathcal{D}} \left( r + \gamma \max_{a'} Q_{\bar{\phi}}(s',a') - Q_\phi(s,a) \right)^2
where \bar{\phi}=\phi but is considered frozen and therefore does not contribute to the derivation (stop-gradient).
This gives the following gradient: \nabla_\phi \mathcal{L}(\phi) = - \frac{2}{|\mathcal{D}|} \sum_{(s,a,r,s') \in \mathcal{D}} \left( r + \gamma \max_{a'} Q_{\bar{\phi}}(s',a') - Q_\phi(s,a) \right) \nabla_\phi Q_\phi(s, a)
And the update: \phi \leftarrow \phi + \alpha \frac{1}{|\mathcal{D}|} \sum_{(s,a,r,s') \in \mathcal{D}} \left( r + \gamma \max_{a'} Q_{\bar{\phi}}(s',a') - Q_\phi(s,a) \right) \nabla_\phi Q_\phi(s, a)
Double DQN
Double Deep Q Networks (Double DQN) is double Q-learning with Q-networks: \begin{aligned} \phi \leftarrow \phi + \alpha \frac{1}{|\mathcal{D}|} \sum_{(s,a,r,s',a') \in \mathcal{D}} \left( r + \gamma Q_{\phi'}(s', \argmax_{a'} Q_{\bar{\phi}}(s',a') - Q_\phi(s,a) \right) \nabla_\phi Q_\phi(s, a) \\ \phi' \leftarrow \phi' + \alpha \frac{1}{|\mathcal{D}|} \sum_{(s,a,r,s',a') \in \mathcal{D}} \left( r + \gamma Q_{\phi}(s', \argmax_{a'} Q_{\bar{\phi}'}(s',a') - Q_{\phi'}(s,a) \right) \nabla_{\phi'} Q_{\phi'}(s, a) \end{aligned}
Policy optimization
In policy optimization methods, we directly learn/optimize the policy. The goal is to find a policy \pi in order to optimize the utility J(\pi): J(\pi) \triangleq \mathbb{E}\left[G_0 | \pi\right] = \mathbb{E}\left[\sum_{t=0}^{H-1} \gamma^t R_t | \pi\right] = \mathbb{E}\left[ R(\tau) | \pi\right]
Note: policy optimization objective and state visitation
In infinite-horizon discounted settings we have: J(\pi) = \sum_s \rho_\pi(s) \sum_a \pi(a|s) \, R(s,a)
with \rho_\pi(s) the (non-normalized) state visitation weights given by,\rho_\pi(s) = \sum_{t=0}^{H-1} \gamma^t P(S_t = s | \pi)
In infinite horizon no discount, we can maximize the long-term expected reward instead, \max_\pi \lim_{n \rightarrow \infty} \frac{1}{n} \mathbb{E}\left[ \sum_{t=0}^n R_t \right]
which gives: J(\pi) = \sum_s \rho_\pi(s) \sum_a \pi(a|s) R(s,a)
with \rho_\pi(s) the (normalized) state visitation probabilities.
In both cases, we have the policy gradient: \nabla_\theta J(\theta) = \sum_s \rho_\pi(s) \sum_a Q^\pi(s,a) \nabla_\theta \pi_\theta(a|s)
Form of the policy
In order to make the policy derivable, we often consider stochastic policies. When using a continuous action space, the policy can be deterministic as well.
We use the following notations: \begin{align*} (A_t|S_t = s) & \sim\pi_\theta(s) \\ \pi_\theta(a|s) &= P(A_t = a | S_t = s) & \text{ discrete action space } \\ \pi_\theta(a|s) &= p(A_t = a | S_t = s) & \text{ continuous action space } \end{align*}
Note: finite horizon
When using finite horizon, the action selection usually depends on the current time t: (A_t|S_t = s) \sim\pi_{\theta,t}(s), etc. When using a parameterized function (eg. based on a neural network), t can be an input of the neural network.
We simplify the notations by introducing: J(\theta) \triangleq J(\pi_\theta)
Finite action space
For a finite action space, the policy \pi_\theta uses a categorical policy and is typically defined by a neural network of the form \pi_\theta(s) = \mathrm{softmax}(f_\theta(x)) (i.e. taking the state as input and with one output neuron per action value): \begin{aligned} (A_t | S_t = s) & \sim \mathrm{Cat}(\mathrm{softmax}(f_\theta(s))) \\ \pi_\theta(s) & = \begin{pmatrix} P(A_t = \mathfrak{a}_1 | S_t = s, \pi_\theta) \\ P(A_t = \mathfrak{a}_2 | S_t = s, \pi_\theta) \\ \ldots \end{pmatrix} = \mathrm{softmax} (f_\theta(s)) \end{aligned}
where \mathfrak{a}_i are the different possible action values.
Continuous action space
For a continuous action space, we can often use diagonal normal policies given by a neural network of the form: (A_t | S_t = s) \sim \mathcal{N}( \mu_\theta(s), \Sigma_\theta(s))
where \mu_\theta(s) gives the means and \Sigma_\theta(s) is a diagonal covariance matrix.
Note: policy gradient for deterministic policies
For a policy gradient algorithm which works with deterministic policies, a = \pi_\theta(s) (on contiunous action spaces), see Deep Deterministic Policy Gradient (DDPG), in Continuous control with deep reinforcement learningnn, Lillicrap et al (2015).
Policy Gradient methods
Policy gradient methods are of the form: \theta \leftarrow \theta + \alpha \, \underbrace{\nabla_\theta J(\theta)}_\text{policy gradient}
Leading to: \theta \leftarrow \theta + \alpha \frac{1}{|\mathcal{D}|} \sum_{(a,s,\psi) \in \mathcal{D}} \sum_{t=0}^{H-1} \psi_t \, \nabla_\theta \log \pi_{\theta}(a_t | s_t)
Actor-critic methods
Actor-critic methods are policy gradient methods which learn a value function at the same time. This value function is used to approximate a TD target.
A2C
Advantage actor-critic (A2C) learns an approximation of the current policy value function V_\phi. This function is used to compute a TD target g_{t:t+1} \approx r_t + \gamma \, V_\phi(s_{t+1}): \begin{aligned} \delta_t & = \overbrace{r_t + \gamma \, V_\phi(s_{t+1})}^{\text{target } \approx g_{t:t+1}} - \overbrace{V_\phi(s_t)}^{b(s_t)} &\text{(TD error)} \\ \phi & \leftarrow \phi + \eta \, \delta_t \, \nabla_\phi V_\phi(s_t) &\text{(critic)} \\ \theta & \leftarrow \theta + \alpha \, \delta_t \, \nabla_\theta \log \pi_\theta(a_t | s_t) &\text{(actor)} \end{aligned}
When the policy and the value function have shared parameters \varphi (multi-headed neural network), we can use a single objective: \begin{aligned} \min_\varphi \mathcal{L}(\varphi) \\ \mathcal{L}(\varphi) & = \lambda_1 \mathcal{L}_1(\varphi) - \lambda_2 \mathcal{L}_2(\varphi) - \lambda_3 \mathcal{L}_3(\varphi) \\ \mathcal{L}_1(\varphi) &= \frac{1}{T} \sum_{0}^{H-1} (r_t + \gamma \, V_{\bar{\varphi}}(s_{t+1}) - V_\varphi(s_{t+1}))^2 & \text{(critic)}\\ \\ \mathcal{L}_2(\varphi) &= \frac{1}{T} \sum_{t=0}^{H-1} (r_t + \gamma \, V_{\bar{\varphi}}(s_{t+1}) - V_\varphi(s_{t+1})) \log \pi_\varphi(a_t | s_t) & \text{(actor)} \\ \\ \mathcal{L}_3(\varphi) &= - \frac{1}{T} \sum_{t=0}^{H-1} \sum_a \pi_\varphi(a | s_t) \log \pi_\varphi(a | s_t) & \text{(entropy)} \end{aligned}
The (optional) entropy term acts as a regularizer.
Kakade's Natural Policy Gradient is using a natural gradient ascent with a constraint on the KL divergence between the current policy \pi_\theta and the new policy \pi_{\theta'}: \theta \leftarrow \theta + \alpha \, \argmax_{\delta} J(\theta+\delta) \text{ s.t. } \underbrace{ \underset{s \sim \rho_\theta}{\mathbb{E}}\left[ D_\mathrm{KL}(\pi_\theta(s) \| \pi_{\theta+\delta}(s)) \right] }_{D(\theta\|\theta+\delta) \triangleq} \le \epsilon
This gives the update: \theta \leftarrow \theta + \alpha \, \underbrace{ \hat{H}_\theta^{-1} \, \nabla_\theta \hat{J}(\theta)}_{\text{natural policy gradient}}
We can replace the constraint of the optimization problem by a penalization (soft-constraint): \theta \leftarrow \theta + \alpha \, \argmax_\delta \underbrace{ \left( J(\theta) - \beta \underset{s \sim \rho_\theta}{\mathbb{E}}\left[ D_\mathrm{KL}(\pi_\theta(s) \| \pi_{\theta+\delta}(s)) \right] \right) }_{L_\theta(\delta)}
Morimura's Natural Policy Gradient (aka natural state-action gradient) uses a constrained base on the KL divergence of the joint distribution over states and actions, P_\theta(s,a), instead of over states, \pi_\theta(a|s): \theta \leftarrow \theta + \alpha \, \argmax_\delta J(\theta+\delta) \text{ subject to } D_\mathrm{KL}(P_\theta, P_{\theta + \delta}) \le \epsilon
with q(a|s) a sampling distribution, typically \pi_\theta(a|s), and \pi_{\theta'}(s|a)/q(s|a) is the likelihood ratio introduced because we are sampling a using q(s) instead of \pi_{\theta'}(s) (importance sampling).
Leading to the update: \begin{aligned} s & \leftarrow \hat{H}_\theta^{-1} \, \hat{g}_\theta & \text{ (search direction)} \\ \beta & \leftarrow \sqrt{\frac{2 \epsilon}{s^T \, \hat{H}_\theta^{-1} \, s}} \\ \beta & \leftarrow \eta^k \beta & \text{ where } k \in \mathbb{N} \text { is the smallest natural integer} \\ && \text{such that } \hat{D}(\theta, \theta + \eta^k \, \beta \, s) & \le \epsilon \\ && \text{and } \tilde{J}_\theta(\theta + \eta^k \, \beta \, s ) & \gt \tilde{J}_\theta(\theta) \\ \theta & \leftarrow \beta \, s \end{aligned}
with 0 < \eta < 1.
The Q values Q^{\pi_\theta}(s,a) can for example be estimated by the reward to go g_t of the sampled trajectories.
Note: TRPO (single-path) algorithm
Sample trajectories from \pi_\theta
Compute \hat{g}_\theta = \nabla_\theta\left[ \frac{1}{n} \sum_{s,a,g} \frac{\pi_{\theta+\delta}(a|s)}{\pi_\theta(a|s)} \, g \right] where g is the reward-to-go after (s,a) of the sampled trajectory
Find search direction s \leftarrow \hat{H}_\theta^{-1} \, \hat{g}_\theta (using the conjugate gradient algorithm)
Increase of the objective: \text{and } \tilde{J}_\theta(\theta + \eta^k \, \beta \, s ) \gt \tilde{J}_\theta(\theta)
Update parameters \theta \leftarrow \theta + \beta s
Repeat
Note: derivation
Once the search direction s has been found, we find the step size (i.e. \beta) so that the KL constraint is verified.
We start with the largest \beta such that: \begin{aligned} \frac{1}{2} \, (\beta s)^T \, \hat{H}_\theta \, (\beta s) & \le \epsilon \\ \frac{1}{2} \, \beta^2 \, s^T \, \hat{H}_\theta \, s & \le \epsilon \end{aligned}
Which gives: \beta^\star = \sqrt{\frac{2 \epsilon}{s^T \, \hat{H}_\theta \, s}}
And then we choose the largest \beta = \eta^k \, \beta^\star (i.e. the smallest k \in \mathbb{N}) such that:
the constraint is verified, D(\theta, \theta + \beta \, s) \le \epsilon;
the objective is improved, \tilde{J}_\theta(\theta + \beta \, s ) \gt \tilde{J}_\theta(\theta) .
PPO
Proximal Policy Optimization (PPO) uses the same idea as TRPO (avoiding moving too far away from the current policy) but without using second-order derivatives (the hessian).
PPO-clip is using an update of the form: \begin{aligned} \theta & \leftarrow \theta + \argmax_\delta \underbrace{ \underset{s \sim \rho_\theta, a \sim \pi_\theta(s)}{\mathbb{E}} \left[ \overbrace{ \min \left( \frac{ \pi_{\theta+\delta}(a|s) }{ \pi_{\theta}(a|s) } \hat{A}_{\pi_\theta}(s,a), g_\epsilon( \hat{A}_{\pi_\theta}(s,a) ) \right) }^{L_\theta(\delta,s,a)} \right] }_{L_\theta(\delta)} \\ g_\epsilon(x) & = \begin{cases} 1 + \epsilon & \text{ if } x \ge 0 \\ 1 - \epsilon & \text{ if } x \lt 0 \end{cases} \end{aligned}
where \argmax_\delta is solved using gradient ascent.
The \epsilon parameter is typically around \epsilon = 0.2
Note: explanation of the surrogate objective
This surrogate objective L_\theta(\delta) removes the incentive to move to far away from \pi_\theta based on the \frac{ \pi_{\theta+\delta}(a|s) }{ \pi_{\theta}(a|s) } ratio:
For \hat{A}_{\pi_\theta}(s,a) > 0, \nabla_\delta L_\theta(\delta,s,a) = 0 when \frac{ \pi_{\theta+\delta}(a|s) }{ \pi_{\theta}(a|s) } > 1 + \epsilon.
For \hat{A}_{\pi_\theta}(s,a) < 0, \nabla_\delta L_\theta(\delta,s,a) = 0 when \frac{ \pi_{\theta+\delta}(a|s) }{ \pi_{\theta}(a|s) } < 1 - \epsilon.
Note: PPO-clip algorithm
Sample trajectories from \pi_\theta
Estimate advantages \hat{A}_{\pi_\theta}(s,a)
Optimize \max_\delta L_\theta(\delta) using gradient ascent
PPO-Penalty uses the following problem the penalized objective \delta \leftarrow \argmax_\delta \underset{s \sim \rho_\theta, a \sim \pi_\theta(s)}{\mathbb{E}} \left[ \frac{ \pi_{\theta+\delta}(a|s) }{ \pi_{\theta}(a|s) } \hat{A}_{\pi_\theta}(s,a) - \beta D_\mathrm{KL}( \pi_\theta(s) \| \pi_{\theta+\delta}(s)) \right]
where \argmax_\delta is solved using gradient ascent.
The KL penalty is adaptive. After each update of \theta, the \beta parameter is updated in order to track a target KL divergence d_\text{target}: \begin{aligned} d & \leftarrow \underset{s \sim \rho_\theta}{\mathbb{E}} \left[ D_\mathrm{KL}( \pi_\theta(s) \| \pi_{\theta+\delta}(s)) \right] \\ \beta & \leftarrow \begin{cases} \beta/2 & \text{if } d < d_\text{target}/1.5 \\ \beta & \text{if } d \in [d_\text{target}/1.5, 1.5 \, d_\text{target}] \\ 2 \, \beta & \text{if } d > 1.5 \, d_\text{target}/1.5 \\ \end{cases} \\ \theta & \leftarrow \theta + \delta \end{aligned}
If the expectation of the KL divergence was too small, \beta is reduced which leads to greater policy steps. On the other hand, if the expectation of the KL divergence was too big, \beta is increased which leads to smaller policy steps.
Note: PPO-penalty algorithm
Sample trajectories from \pi_\theta;
Estimate advantages \hat{A}_{\pi_\theta}(s,a);
Optimize \max_\delta L_\theta(\delta) using gradient ascent
Adaptive update of parameter \beta based on \underset{s \sim \rho_\theta}{\mathbb{E}} \left[ D_\mathrm{KL}( \pi_\theta(s) \| \pi_{\theta+\delta}(s)) \right]
Model-based reinforcement learning (MBRL) methods learn the world model. Once the world mode is learned we can use planning algorithms.
Not covered here.
Exploration/exploitation trade-off
In order to make the RL algorithm work, we need to find a balance between exploration (of new states, trajectories, actions) and exploitation (of known good states and actions).
ε-soft policies
An \epsilon-soft policy is a policy such that: \forall s, \forall a, \pi(a|s) \ge \frac{\epsilon}{|\mathbb{A}|}
One example are \epsilon-greedy policies. An \epsilon-greedy policy takes the best action (according to some Q function) with probability (1 - \epsilon) and a random action with probability \epsilon.
This is often used with Q learning in order to have some amount of exploration.
Entropy regularization
We can add some regularization in order to prevent the policy from being too deterministic and keep some amount of exploration.
A max-entropy term can be added in the objective function in order to prevent the policies from being to deterministic: \max_\pi \mathbb{E} \left[ \sum_{t=0}^T \gamma^t \left[ R_t + \beta \, \mathcal{H}(\pi(S_t)) \right] \middle| \pi \right]
is an estimator of \underset{X \sim P}{\mathbb{E}} \left[ f(X) \right] ,
with w(x) = P(x) / Q(x) or more generally w(x) = \lambda \, P(x) / Q(x) is the likelihood ratio;
assuming that as Q(x) > 0 for all x such that P(x) > 0 (which ensures that w(X_i) is finite and therefore that the denominator of the estimator does not become infinite).
Benefits:
This can be used if we can only know P(x) and/or Q(x) up to a scale factor.
Avoid the inconsistent estimates problem mentioned in the previous section.
Drawbacks:
In contrast to the previous one, it is not unbiased.
Stronger requirements on Q.
Appendix, Kullback–Leibler divergence
Kullback–Leibler divergence
The Kullback–Leibler divergence (KL divergence) D_\mathrm{KL}(P \| Q) between to distribution P and Q measures the difference between a (real) P distribution and a Q distribution (often an approximation of P):
The Hesssian of the KL divergence between P_\theta and P_{\theta'} evaluated at \theta' \coloneqq \theta is the Fisher information matrix \mathcal{I}_X(\theta) of X \sim P_\theta: \begin{aligned} \left[ \nabla^2_\theta D_\mathrm{KL}(P_\theta \| P_{\theta'}) \right]_{\theta' \coloneqq \theta} & = \mathcal{I}_X(\theta) \end{aligned}
Ordinary gradient descent for \min_\theta f(\theta) can be seen as an approximation of: \theta ← \theta + \argmin_\delta f(\theta + \delta) \text{ subject to } \|\delta\|_2^2 \le \epsilon
i.e. we are searching for \theta' = \theta + \delta for a small \delta.
Leading to: \theta ← \theta - \alpha \, \nabla_\theta f(\theta)
Note: derivation
We can use a relaxation of the constrained problem: \min_\delta \underbrace{ f(\theta + \delta) + \lambda \|\delta\|_2^2 }_{L(\delta)}
for some \lambda \ge 0. We can then search a local optimum by solving \nabla_\delta L(\delta) = 0.
Equivalently, we can form the Lagrangian, L(\delta, \lambda) = f(\theta + \delta) + \lambda (\|\delta\|_2^2 - \epsilon) and find a local optimum by solving \nabla_\delta L(\delta, \lambda) = 0 and \nabla_\lambda L(\delta, \lambda) = 0 for unknown \delta and \lambda. The former equation is equivalent to the gradient of the relaxed problem and the latter equation is equivalent to the constraint ( \|\delta\|_2^2 = \epsilon ).
We use a linear approximation of f around \theta: f(\theta + \delta) = f(\theta) + \delta^T \, \nabla_\theta f(\theta) + O(\|\delta\|^2)
We search a local optimum by solving \nabla_\delta \tilde{L}(\delta) = 0 for the unknown \delta: 0 + \nabla_\theta f(\theta) + 2 \, \lambda \, \delta = 0
More generally, we can introduce a constraint using another metric \|\delta\|_G^2 defined as: \|\delta\|_G^2 \triangleq \delta^T \, G(\theta) \, \delta = \sum_{i,j} \delta_i \, \delta_j \, G_{i,j}(\theta)
where G(\theta) is a positive-definite matrix.
Which gives the constrained optimization problem: \theta ← \theta + \argmin_\delta f(\theta) \text{ subject to } \|\delta\|_G^2 \le \epsilon
Leading to the natural gradient descent update: \theta ← \theta - \alpha \, G(\theta)^{-1} \, \nabla_\theta f(\theta)
This generalizes the previous section, when using G(\theta)=I.
Note: derivation
Relaxed problem after Taylor approximation of f: \min_\delta \underbrace{ f(\theta) + \delta^T \, \nabla_\theta f(\theta) + \lambda \, \delta^T \, G(\theta) \, \delta }_{\tilde{L}(\delta)}
We find a local minimum by solving \nabla_\delta \tilde{L}(\delta) = 0: \begin{aligned} \nabla_\theta f(\theta) + 2 \, \lambda \, G(\theta)\, \delta = 0 \end{aligned}
More generally, if we consider a constraint of the form D(\theta,\theta+\delta) \le \epsilon where D(\theta,\theta+\delta) is a distance or divergence: \min_\delta f(\theta + \delta) \text{ subject to } D(\theta,\theta+\delta) \le \epsilon
We get the natural gradient update: \theta ← \theta - \alpha \, H_\theta^{-1} \, \nabla_\theta f(\theta)
where H_\theta is the hessian of the distance function D(\theta,\theta') evaluated at \theta'=\theta: H_\theta = \left[ \nabla_\delta D(\theta, \theta+\delta) \right]_{\delta \coloneqq 0}
Some assumptions:
This assumes that \left[ \nabla_\theta D(\theta, \theta+\delta) \right]_{\delta \coloneqq 0} which is true if D(\theta,\theta) is a local minimum and \theta is not a boundary.
We assume that D(\theta,\theta') > 0 for \theta \ne \theta'. This implies that H_\theta is definite positive and therefore invertible.
Note: derivation
We can approximate D(\theta,\theta+\delta) using a second order Taylor expansion: \begin{aligned} D(\theta,\theta+\delta) & = \underbrace{ D(\theta,\theta) }_{=0} + \delta^T \, \underbrace{ \left[ \nabla_\theta D(\theta, \theta+\delta) \right]_{\delta \coloneqq 0} }_{ =0 } + \frac{1}{2} \, \delta^T \, H_\theta \, \delta + O(\|\delta\|)^3 \\ & \approx \frac{1}{2} \delta^T \, H_\theta \, \delta \end{aligned}
Relaxed problem after Taylor approximation of f: \min_\delta \underbrace{ f(\theta) + \delta^T \, \nabla_\theta f(\theta) + \frac{1}{2} \lambda \, \delta^T \, H_\theta \, \delta }_{\tilde{L}(\theta)}
We don't want to explicitly form \hat{H}(\theta) (which is very huge for large deep network models), and we don't want to inverse it using basic matrix inversion methods.
Because \hat{H}(\theta) is positive semi-definite, we can use the conjugate gradient algorithm to efficiently find an approximate solution. This algorithm only needs evaluating \hat{H}(\theta) \, x (Hessian-Vector product, HVP).
The Hessian-Vector product can be computed using the following equation (using some autodiff library): (\nabla^2_\theta h(\theta)) \, x = \nabla_\theta\left[ (\nabla_\theta h(\theta))^T \, x \right]
When trying to learn a probability distribution P_\theta (eg. using maximum likelihood or maximum a posteriori), we can limit the size of the steps by adding a constraint in the probability distribution space: \theta \leftarrow \theta + \argmax_{d\theta} f(\theta + \delta) \text{ subject to } D_\mathrm{KL}(P_\theta \| P_{\theta + \delta}) \le \epsilon
Note: constraint in the distribution space
In many cases, adding a constraint in the distribution space, D_\mathrm{KL}(P_\theta \| P_{\theta+\delta}) \le \epsilon, makes a lot more sense that a constraint on the parameter space, \|d\theta\|_2^2 \le \epsilon.
This gives the natural gradient descent update: \theta \leftarrow \theta + \alpha \, H_\theta^{-1} \, \nabla_\theta f(\theta)