Title: Reinforcement Learning

Q: Trajectory
A: A trajectory \(\tau\) is a sequence of states and actions in the world \(\tau = (s_0, a_0, s_1, a_1, ...).\).

Q: On-Policy Value Function
A: \(V^{\pi}(s)\) is the value function conditioned on \(s\) and \(\pi\).

Q: Optimal Value Function
A: \(V^*(s)]\) is the value function conditioned on \(s\)

Q: On-Policy Action-Value Function
A: \(Q^{\pi}(s,a)\) conditions on \(s,a, \pi\).

Q: Optimal Action-Value Function
A: $Q^*(s,a)]$ is the value function conditioned on $s, a$.

Q: Bellman backup
A: RHS of the Bellman equation, i.e. reward + next value

Q: Advantage function
A: Relative action-value function \(A_{\pi}(s,a) = Q^{\pi}(s,a) - V^{\pi}(s).\)

Q: Taxonomy of approaches to RL
A: - Pure Planning
  - policy-free approach using the model to improve the short-run state
- Expert Iteration
  - learning a policy to match a pure-planning expert
- Q-learning
  - learn an approximator \(Q_{\theta}(s,a)\) for \(Q^*(s,a)\)
  - optimisation usually off-policy so leverages all the collected data
  - policy is given by \(a(s) = \arg \max_a Q_{\theta}(s,a)\)
- Policy optimisaton
  - learn a policy \(\pi_\theta(a|s)\)
  - on-policy optimisation

Q: Policy gradient
A: \[
\begin{align*}
\nabla_\theta J\left(\pi_\theta\right) & =\nabla_\theta \underset{\tau \sim \pi_\theta}{\mathrm{E}}[R(\tau)] & \\
& =\nabla_\theta \int_\tau P(\tau \mid \theta) R(\tau) & \text { Expand expectation } \\
& =\int_\tau \nabla_\theta P(\tau \mid \theta) R(\tau) & \text { Swap diff/int } \\
& =\int_\tau P(\tau \mid \theta) \nabla_\theta \log P(\tau \mid \theta) R(\tau) & \text { Log-derivative trick } \\
& =\underset{\tau \sim \pi_\theta}{\mathrm{E}}\left[\nabla_\theta \log P(\tau \mid \theta) R(\tau)\right] & \text { Return to expectation } \\
& =\underset{\tau \sim \pi_\theta}{\mathrm{E}}\left[\sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a_t \mid s_t\right) R(\tau)\right] & \text { See below}
\end{align*}
\]
Last step comes from differentiating
\[
\log P(\tau \mid \theta)=\log \rho_0\left(s_0\right)+\sum_{t=0}^T\left(\log P\left(s_{t+1} \mid s_t, a_t\right)+\log \pi_\theta\left(a_t \mid s_t\right)\right).
\]
In words: \(\theta\) affects \(\tau\) via actions, not dynamics.

Q: Vanilla policy gradient
A: We estimate the policy gradient
\[
\nabla_\theta J\left(\pi_\theta\right)=\underset{\tau \sim \pi_\theta}{\mathrm{E}}\left[\sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a_t \mid s_t\right) R(\tau)\right]
\]
using
\[
\hat{g}=\frac{1}{|\mathcal{D}|} \sum_{\tau \in \mathcal{D}} \sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a_t \mid s_t\right) R(\tau)
\]
where \(\mathcal{D}=\left\{\tau_i\right\}\) where are sample trajectories using the policy \(\pi_\theta\).

Q: Reward-to-go policy gradient
A: Intuition: we should only push up logits for actions on the basis of their consequences
Claim: We can swap out the total reward in vanilla policy gradient for reward-to-go minus baseline
\[
R(\tau) \mapsto \Phi_t :=\sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1}) - b(s_t)
\]
where usually we pick \(b(s_t)=V^\pi(s_t)\) to give \(\Phi_t = Q(s_t, a_t) - V^\pi(s_t) =A_\pi(s_t, a_t)\) which is the advantage function.
Proof: We check that any term which is just a function of the history sums to zero:
\[
\begin{align*}
&\sum_{t=1}^T\mathbb{E}_{\tau\sim\pi_\theta}\left[\nabla_\theta\log\pi_\theta(a_t|s_t) b(s_0, a_1, s_1, \ldots s_t) \right] \quad (\text{Markov}) \\
=&\sum_{t=1}^T \mathbb{E}_{\tau:s_t\sim\pi_\theta} \mathbb{E}_{a_t\sim\pi_\theta | s_t} \left[\nabla_\theta\log\pi_\theta(a_t|s_t) b(s_0, a_1, s_1, \ldots s_t) \right] \quad (\text{split expectation})\\
=&\sum_{t=1}^T \mathbb{E}_{\tau:s_t\sim\pi_\theta} \left[ b(s_0, a_1, s_1, \ldots s_t)\mathbb{E}_{a_t\sim\pi_\theta | s_t} \left[\nabla_\theta\log\pi_\theta(a_t|s_t)  \right]\right] \\
=& \ 0 \qquad (\text{EGLP}).
\end{align*}
\]

Q: EGLP Lemma
A: Expected Grad-Log-Prob Lemma. For \(P_\theta\) any a parameterized probability distribution over a random variable, \(x\):
\[
\underset{x \sim P_\theta}{\mathrm{E}}\left[\nabla_\theta \log P_\theta(x)\right] = 0.
\]
Proof. Differentiating the normalisation condition:
\[
\begin{aligned}
1 &= \int_x P_\theta(x) \\
0 & =\nabla_\theta \int_x P_\theta(x) \\
& =\int_x \nabla_\theta P_\theta(x) \\
& =\int_x P_\theta(x) \nabla_\theta \log P_\theta(x) \\
\therefore 0 & =\underset{x \sim P_\theta}{\mathrm{E}}\left[\nabla_\theta \log P_\theta(x)\right] .
\end{aligned}
\]

Q: GAE
A: First define the temporally discounted residual
\[
\delta_t^V=r_t + \gamma V(s_{t+1}) - V(s_t)
\]
which we can sample over the next state to get the advantage function:
\[
\begin{align*}
\mathbb{E}_{s_{t+1}}[\delta_t^V]
&= Q(s_t, a_t) - V(s_t)\\
&= A_\pi(s_t, a_t). \\
\end{align*}
\]
We can generalise this to the k-step advantage with telescopic sum
\[
\begin{align*}
\hat A_t^{(k)} &= \sum_{\ell = 0}^{k-1} \gamma^\ell \delta_{t+\ell}^V  \\
&= \gamma^k V(s_{t+k}) - V(s_t) + \sum_{\ell = 0}^{k-1} \gamma^\ell r_{t+\ell}^V.
\end{align*}
\]
Finally we define the EMA as the Generalised Advantage Estimate:
\[
\begin{align*}
\mathrm{GAE}(\gamma, \lambda, t)
&= (1 - \lambda)\sum_{k=0}^\infty \lambda^k \hat A_t^{(k + 1)} \\
&= (1 - \lambda)\sum_{k=0}^\infty \lambda^k \sum_{\ell = 0}^{k} \gamma^\ell \delta_{t+\ell}^V  \\
&= (1 - \lambda)\sum_{\ell=0}^\infty \gamma^\ell \delta_{t+\ell}^V
\sum_{k \geq \ell} \lambda^k  \\
&= \sum_{\ell=0}^\infty (\lambda\gamma)^\ell \delta_{t+\ell}^V.
\end{align*}
\]
Setting \(\lambda=0\) gives TD (low variance) whereas \(\lambda=1\) gives MC (low bias).

Q: Temporal Difference learning
A: - Model-free setting
  - cf. DP has access to a model of the env
  - cf. MC does not even assume Markovian
- Uses the reward to for online learning at every step (cf. MC updates each episode) so converges quickly and is appropriate for long tasks
- The update is \(V\left(S_t\right) \leftarrow V\left(S_t\right)+\alpha\left[R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_t\right)\right]\)
- Bootstrapping method
  - i.e. requires initialisation of \(V(S)\)
  - cf. MC always samples from the same distribution
- Converges to the certainty-equivalence estimate
  - i.e. assume the MLE of the Markov process is certain
  - cf. MC minimises unconstrained training error
- Low variance, high bias
  - cf. MC: high variance, low bias

Q: Behaviour vs. target policy
A: - The behavior policy is a policy that includes random exploration
- The target policy does not include \(\varepsilon\) randomness

Q: SARSA vs. Q-learning
A: - Sarsa
  - on-policy TD control
  - only learns from data that was actually generated by the current behavioural policy
  - \(Q\left(s_t, a_t\right) \leftarrow Q\left(s_t, a_t\right)+\eta\left(r_{t+1}+\gamma Q\left(s_{t+1}, a_{t+1}\right)-Q\left(s_t, a_t\right)\right)\)
  - Better online performance (behavioural policy) because it takes into account randomness in the action selection
- Q-learning
  - off-policy TD control
  - i.e. we pick \(a_{t+1}\) using a pure greedy policy
  - \(Q\left(s_t, a_t\right) \leftarrow Q\left(s_t, a_t\right)+\eta\left(r_{t+1}+\gamma \max _a Q\left(s_{t+1}, a\right)-Q\left(s_t, a_t\right)\right)\)
  - The target policy converges to the optimal policy

Q: Experience replay buffer
A: List of {states, actions, rewards} recorded in DQN for use in the update step.

Q: Target network
A: A copy of the \(Q\)-network in DQN that only updates every C (e.g. C=1000) timesteps for a stable estimate of future reward

Q: Optimistic initial values
A: Setting initial arm value estimates to be high to encourage exploration

Q: UCB
A: Try every action in a MABP to ensure \(N_t(a)\geq 1\) then for some exploration parameter \(c>0\), pick action
\[
A_t = \text{argmax}_a \left[Q_t(a) + c\sqrt{\frac{\log(t)}{N_t(a)}} \right]
\]
Intuition: for sub-gaussian RVs we have the Chernoff-Hoeffding inequality
\[
\mathbb{P}(|X| > x) \leq C \exp\left(-\frac{x^2}{2\sigma^2}\right)
\]
hence for the gaussian mean
\[
\mathbb{P}(|\bar{X}_n| > x) \leq C \exp\left(-\frac{nx^2}{2\sigma^2}\right)
\]
and thus a \(1-\delta\) upper confidence bound is
\[
x = \sqrt{\frac{2\sigma^2}{n}} \log\left(\frac{C}{\delta}\right).
\]
Setting linear decay \(\delta = \frac{1}{t}\) gives the desired form.

Q: MABP incremental value update rule
A: \[
\begin{align*}
Q_{k+1} &= \frac{1}{k}\sum_{i=1}^k R_i \\
&= \frac{1}{k} \left( R_k + (k-1)Q_{k} \right) \\
&= Q_{k} + \frac{1}{k} \left( R_k - Q_{k} \right).
\end{align*}
\]
Or in general for non-stationary problems, we use a step size \(\alpha\):
\[
\begin{align*}
Q_{k+1} &= \alpha R_k + (1-\alpha)Q_k \\
&= (1-\alpha)^k Q_1 + \alpha \sum_{i=1}^k (1-\alpha)^{k-i}R_i \\
&= (1-\alpha)^k Q_1 + \alpha \{(1-\alpha)^i\}\ast \{R_i\}.
\end{align*}
\]

Q: Preference updating
A: We assign a preference \(H_t(a)\) to each action then pick actions based on the softmax probability distribution
\[
\pi_t(a):= \mathbb{P}(A_t = a) = \frac{\exp(H_t(a))}{\sum_b \exp(H_t(b))}.
\]
We update these preferences in a way that
- keeps the sum of the preferences constant \(\sum_b \frac{\partial\pi_t(b)}{\partial H_t(a)}=0\)
- most aggressively reweights our preferences for the most sampled actions
- is analogous to SGD.
Applying the quotient rule
\[
\begin{align*}
H_{t+1}(a) &= H_t(a) + \alpha \frac{\partial\mathbb E[R_t]}{\partial H_t(a)} \\
&= H_t(a) + \alpha \frac{\partial}{\partial H_t(a)} \sum_b \pi_t(b)q(b)\\
&= H_t(a) + \alpha  \sum_b \frac{\partial \pi_t(b)}{\partial H_t(a)}(q(b) - \bar R_t)\\
&= \begin{cases}
H_t(A_t) + \alpha (R_t - \bar R_t)(1-\pi_t(A_t)) \quad  & (a= A_t)\\
H_t(a) - \alpha (R_t - \bar R_t)\pi_t(a) \quad  & (a\neq A_t)
\end{cases}
\end{align*}
\]

Q: PPO
A: Proximal Policy Optimisation is an on-policy RL algorithm using actor/critic networks.
Etymology: \(\mathrm{prox}_f(y) = \mathrm{argmin}_x \left( f(x) + \frac{1}{2}\|x - y\|^2 \right)\)
PPO comes in flavours with different defences against overfitting:
- Raw \(\max \left[ r_t(\theta) \hat A_t \right]\)
- Clip \(\max \left[ \min( r_t(\theta) \hat A_t, \mathrm{clip}(r_t(\theta), 1-\varepsilon, 1+ \varepsilon) \hat A_t) \right]\)
- Penalty \(\max \left[ r_t(\theta) \hat A_t - D_{KL}(\pi_{\theta_k}, \pi_\theta) \right]\)

Q: Importance sampling
A: \[
\begin{aligned}
&\text { Lemma: if } f, g \text { are both PDFs, then } \mathbb{E}_{x \sim g}\left[\frac{f(x)}{g(x)} h(x)\right]=\mathbb{E}_{x \sim f}[h(x)] \\
&\text { Proof: } \quad \mathbb{E}_{x \sim g}\left[\frac{f(x)}{g(x)} h(x)\right]=\int_x g(x) \times \frac{f(x)}{g(x)} h(x) d x \\
&=\int_x f(x) h(x) \\
&=\mathbb{E}_{\boldsymbol{x} \sim f}[h(x)] \\
&
\end{aligned}
\]

Q: Actor for policy gradient methods
A: Claim: The following loss function has the required gradient
 \[
L(\theta)=\underset{a, s \sim \pi_{\theta_{\text {old }}}}{\mathbb{E}}\left[\frac{\pi_\theta(a \mid s)}{\pi_{\theta_{\text {old }}}(a \mid s)} \hat{A}(a, s)\right].
\]
In PPO, we add an entropy bonus and \(\boldsymbol\varepsilon\)-clip as
\[
\begin{align*}
L\left(s, a, \theta_k, \theta\right)
&=\min \left(\frac{\pi_\theta(a \mid s)}{\pi_{\theta_k}(a \mid s)} \hat{A}_t, \operatorname{clip}\left(\frac{\pi_\theta(a \mid s)}{\pi_{\theta_k}(a \mid s)}, 1-\epsilon, 1+\epsilon\right) \hat{A}_t\right)
\end{align*}.
\]
Proof: we differentiate, using grad-log and importance sampling:
 \[
\begin{aligned}
\nabla_\theta L(\theta) &=\underset{a, s \sim \pi_{\theta_{\text {old }}}}{\mathbb{E}}\left[\frac{\nabla_\theta \pi_\theta(a \mid s)}{\pi_{\theta_{\text {old }}}(a \mid s)} \hat{A}(a, s)\right] \\
&=\underset{a, s \sim \pi_{\theta_{\text {old }}}}{\mathbb{E}}\left[\frac{\pi_\theta(a \mid s)}{\pi_{\theta_{\text {old }}}(a \mid s)} \nabla_\theta \log \pi_\theta(a \mid s) \hat{A}(a, s)\right] \\
&=\underset{a, s \sim \pi_\theta}{\mathbb{E}}\left[\nabla_\theta \log \pi_\theta(a \mid s) \hat{A}(a, s)\right].
\end{aligned}
\]

Q: Critic for policy gradient
A: The idea is to model the value function in order to better handle sparse reward problems.
We pick \(V_\theta\) to minimise squared error with \(\varepsilon\)-clipping:
\[
L^V=\max \left[\left(V_{\theta_t}-V_{\text {targ }}\right)^2,\left(\operatorname{clip}\left(V_{\theta_t}, V_{\theta_{t-1}}-\varepsilon, V_{\theta_{t-1}}+\varepsilon\right)-V_{\text {targ }}\right)^2\right].
\]

Q: Rollout phase (PPO)
A: Sample from environments for some number of steps, sampling actions from actor network without grad

Q: Learning phase (PPO)
A: Run epochs of training on mini-batches

Q: Episodic tasks
A: Tasks which break down into subsequences called *episodes* which terminate with a an *absorbing state*, i.e. zero marginal reward and the task is reset to a standard starting state

Q: Continuing tasks
A: Tasks without episodes

Q: Myopic policy
A: Zero discount rate policy, i.e. maximises only immediate reward

Q: Numerical policy evaluation
A: Substitute repeatedly into the Bellman equation for \(V_\pi\) until \(L^\infty\) convergence:
\[
V_\pi(s)=\sum_{s^{\prime}} T\left(s^{\prime} \mid s_i, \pi(s)\right)\left(R\left(s, \pi(s), s^{\prime}\right)+\gamma V_\pi\left(s^{\prime}\right)\right).
\]

Q: Exact policy evaluation
A: Define value vector \(\mathbf{v} \in \mathbf{R}^{|S|}\) to be a vector representing the value function \(V_{\boldsymbol{\pi}}\) for each state:
\[
\mathbf{v}=\left[V_\pi\left(s_1\right), \ldots, V_\pi\left(s_N\right)\right].
\]
Define transition matrix \(P^\pi\) and reward matrix \(R^\pi\), both of shape (num_states, num_states):
\[
P_{i, j}^\pi=T(i, \pi(i), j) \quad R_{i, j}^\pi=R(i, \pi(i), j).
\]
Then the Bellman equation becomes
\[
\begin{gathered}
\mathbf{v}_i=\sum_j P_{i, j}^\pi\left(R_{i, j}^\pi+\gamma \mathbf{v}_j\right) \\
\mathbf{v}_i=\sum_j P_{i, j}^\pi R_{i, j}^\pi+\gamma \sum_j P_{i, j}^\pi \mathbf{v}_j
\end{gathered}
\]
We can define the diagonal vector \(\mathbf{r}_i^\pi=\sum_j P_{i, j}^\pi\left(R^\pi\right)_{i, j}=\left(P^\pi\left(R^\pi\right)^T\right)_{i i}\) to simplify further:
\[
\mathbf{v}_i=\mathbf{r}_i^\pi+\gamma\left(P^\pi \mathbf{v}\right)_i
\]
A little matrix algebra, and we obtain the closed form solution:
\[
\mathbf{v}=\left(I-\gamma P^\pi\right)^{-1} \mathbf{r}^\pi.
\]

Q: Contraction mapping
A: We say \(f\) is a contraction if for some \( \lambda < 1\)
\[
\forall x, y: d(f(x), f(y)) \leq \lambda d(x, y).
\]

Q: Banach Fixed Point Theorem
A: Let \((\boldsymbol{X}, \boldsymbol{d})\) be a non-empty complete metric space with a contraction mapping \(T: X \rightarrow X\). Then
- \(T\) admits a unique fixed-point \(x^*\) in \(X\)  such that \(T\left(x^*\right)=x^*\).
- for any \(\boldsymbol{x}_0 \in \boldsymbol{X}\), define a sequence \(\left(x_n\right)_{n \in \mathbb{N}}\) by \(x_n=T\left(x_{n-1}\right)\) for \(n \geq 1\). Then \(\lim _{n \rightarrow \infty} x_n=x^*\).

Q: Bellman operator
A: Define \(B: \Pi\to\Pi\) which maps
\[
\pi(s) \mapsto \mathrm{argmax}_a  \left\lbrace \sum_{s^{\prime}} T\left(s^{\prime} \mid s, a\right)\left(R\left(s, a, s^{\prime}\right)+\gamma V_\pi\left(s^{\prime}\right)\right) \right\rbrace
\]
One can show that the Bellman operator is a $\gamma$-contraction on $(\Pi, L^\infty)$ by cancelling the reward terms and using the triangle inequality. Hence the Bellman equation has a unique solution which can be approximated through iteration, i.e. there is a unique optimal policy.