Reinforcement Learning: Quick recap

01 MDPs and Bellman equations

A finite MDP is $(\mathcal S, \mathcal A, P, R, \gamma)$ . Markov: the next state and the reward depend on the past only through $(s_t, a_t)$ .
The return is $G_t = \sum_{k \ge 0} \gamma^k r_{t+k} = r_t + \gamma G_{t+1}$ ; with $\gamma < 1$ the agent looks about $1/(1-\gamma)$ steps ahead.
$V^\pi(s) = \mathbb E_\pi[G_t \mid s_t = s]$ and $Q^\pi(s,a) = \mathbb E_\pi[G_t \mid s_t = s, a_t = a]$ ; the advantage is $A^\pi = Q^\pi - V^\pi$ .
$V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s,a)$ and $Q^\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s')$ .
The Bellman expectation equation $V^\pi = r_\pi + \gamma P_\pi V^\pi$ is linear: $V^\pi = (I - \gamma P_\pi)^{-1} r_\pi$ , and $I - \gamma P_\pi$ is invertible for $\gamma < 1$ because $\|\gamma P_\pi\|_\infty \le \gamma < 1$ .
With $\gamma = 1$ , the values are finite only if the policy ends every episode with probability 1.
The optimality equations put a max over actions inside: $V^*(s) = \max_a [R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s')]$ .
A policy that is greedy with respect to $Q^*$ is optimal in every state and deterministic.

02 Policy and value iteration

Iterative policy evaluation repeats $V_{k+1} = r_\pi + \gamma P_\pi V_k$ ; synchronous sweeps use the old vector, in-place sweeps the newest values.
The Bellman operators are $T^\pi V = r_\pi + \gamma P_\pi V$ and $(TV)(s) = \max_a [R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s')]$ ; both are monotone.
Max lemma: $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$ .
$T$ and $T^\pi$ are $\gamma$ -contractions in the $\infty$ -norm, so they have unique fixed points $V^*$ and $V^\pi$ , and $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$ .
Stopping rule: $\|V_{k+1} - V^*\|_\infty \le \frac{\gamma}{1-\gamma}\|V_{k+1} - V_k\|_\infty$ ; value iteration needs about $\log(1/\varepsilon)/\log(1/\gamma)$ iterations.
Policy improvement theorem: if $Q^\pi(s, \pi'(s)) \ge V^\pi(s)$ in every state, then $V^{\pi'} \ge V^\pi$ in every state; the greedy policy satisfies the condition.
Policy iteration (exact evaluation + greedy improvement) stops after finitely many steps at an optimal policy; one iteration costs $O(S^3 + S^2A)$ . Value iteration costs $O(S^2A)$ per iteration but needs many more.
Generalized policy iteration: any interleaving of evaluation and improvement converges to $V^*$ and $\pi^*$ ; most RL algorithms have this form.

03 Bandits and exploration

A $K$ -armed bandit has arm means $\mu_a$ , best mean $\mu^*$ and gaps $\Delta_a = \mu^* - \mu_a$ . It is an MDP with one state: the pure exploration–exploitation problem.
The sample mean updates as $Q_k = Q_{k-1} + \frac{1}{k}(x_k - Q_{k-1})$ ; a constant step $\alpha$ gives an exponential recency-weighted average for changing means.
The pseudo-regret is the expected loss against always pulling the best arm: $\bar R(T) = \sum_a \Delta_a\, \mathbb E[n_a(T)]$ .
Greedy can lock onto a bad arm; fixed ε-greedy has linear regret $\ge \frac{\varepsilon T}{K}\sum_a \Delta_a$ .
UCB1 pulls $\arg\max_a \hat\mu_a + \sqrt{2\ln t / n_a}$ ; the bonus comes from Hoeffding with failure probability $t^{-4}$ ; it pulls each bad arm at most about $8 \ln T / \Delta_a^2$ times.
Lai–Robbins: every consistent algorithm has regret of order at least $\log T$ , with constant $1/\mathrm{KL}(\mu_a, \mu^*)$ per bad arm.
Thompson sampling draws $\theta_a$ from each Beta posterior and pulls the largest; each arm is pulled with the posterior probability that it is best (probability matching).

04 Monte Carlo and TD prediction

Prediction estimates $V^\pi$ from episodes without a model. Both MC and TD move $V(s_t)$ a step $\alpha$ toward a target.
Monte Carlo uses the return $G_t$ : unbiased, high variance, needs complete episodes, does not need the Markov property.
TD(0) uses $r_t + \gamma V(s_{t+1})$ and the TD error $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ , with $V = 0$ after a terminal state: biased while $V \ne V^\pi$ , low variance, online.
The expected TD(0) target is $(T^\pi V)(s)$ , so TD(0) is a sampled form of iterative policy evaluation; and $G_t - V(s_t) = \sum_{k \ge t} \gamma^{k-t}\delta_k$ .
Batch MC converges to the average observed returns; batch TD converges to the values of the maximum-likelihood Markov model (certainty equivalence).
The λ-return gives weight $(1-\lambda)\lambda^{n-1}$ to the n-step return $G_t^{(n)}$ and the rest, $\lambda^{T-t-1}$ , to $G_t$ ; λ = 0 is TD(0), λ = 1 is MC.
TD(λ) keeps traces $z \leftarrow \gamma\lambda z$ , $z(s_t) \mathrel{+}= 1$ and updates $V \leftarrow V + \alpha\delta_t z$ ; offline it equals the λ-return updates.
Importance sampling with $\rho = \prod_k \pi(a_k \mid s_k)/\pi_b(a_k \mid s_k)$ : ordinary IS is unbiased with high variance; weighted IS is biased, consistent and stays in the range of the returns.

05 SARSA and Q-learning

Control without a model learns $Q(s, a)$ : the greedy step $\arg\max_a Q(s, a)$ needs no $P$ or $R$ . GPI then alternates (partial) evaluation of $Q$ and ε-greedy improvement.
ε-greedy gives the greedy action $1 - \varepsilon + \varepsilon/|\mathcal A|$ and every other action $\varepsilon/|\mathcal A|$ . If $\pi$ is ε-soft, the ε-greedy policy with respect to $Q^\pi$ is at least as good as $\pi$ ; reaching $\pi^*$ needs GLIE exploration.
All three methods update $Q(s, a) \leftarrow Q(s, a) + \alpha[y - Q(s, a)]$ . Targets: SARSA $r + \gamma Q(s', a')$ ; expected SARSA $r + \gamma \sum_{a'} \pi(a' \mid s') Q(s', a')$ ; Q-learning $r + \gamma \max_{a'} Q(s', a')$ ; and $y = r$ at the end of an episode.
SARSA is on-policy (it learns $Q^{\pi_b}$ of the exploring policy); Q-learning is off-policy (it learns $Q^*$ from any data that visit every pair); expected SARSA with a greedy target policy is Q-learning.
Tabular Q-learning converges to $Q^*$ with probability 1 if every pair is updated infinitely often and $\sum_t \alpha_t = \infty$ , $\sum_t \alpha_t^2 < \infty$ (Watkins and Dayan, 1992).
On cliff walking with $\varepsilon = 0.1$ , Q-learning learns the 13-step edge path but has the worse online return (about $-50$ per episode); SARSA learns a safer path and loses less while exploring (about $-25$ ).
Maximization bias: $\mathbb E[\max_i \hat X_i] \ge \max_i \mu_i$ for unbiased $\hat X_i$ . The double estimator $\hat Y_{\arg\max \hat X}$ with independent $\hat Y$ is not biased upward; double Q-learning keeps two tables and updates one at random.

06 Function approximation and DQN

A linear value function is $\hat v(s, w) = w^\top x(s)$ with $\nabla_w \hat v = x(s)$ ; one-hot features give the table, state aggregation a staircase. The objective is $\overline{VE}(w) = \sum_s \mu(s)\,[V^\pi(s) - \hat v(s, w)]^2$ with the on-policy distribution $\mu$ .
Gradient MC, $w \leftarrow w + \alpha[G_t - \hat v(s_t, w)]\,\nabla \hat v(s_t, w)$ , is SGD on $\overline{VE}$ . Semi-gradient TD uses $r_t + \gamma \hat v(s_{t+1}, w)$ as a constant target; it is not the gradient of any loss.
On-policy linear TD converges to the TD fixed point $w_{TD} = A^{-1}b$ , $A = \mathbb E[x_t(x_t - \gamma x_{t+1})^\top]$ , $b = \mathbb E[r_t x_t]$ ; its error can exceed the best fit (by at most $1/(1-\gamma)$ in continuing tasks).
Deadly triad: function approximation + bootstrapping + off-policy data can diverge; with any two of the three, instability can be avoided. In the $w \to 2w$ example, $w \leftarrow (1 + \alpha(2\gamma - 1))w$ diverges for $\gamma > 1/2$ .
DQN minimizes a Huber or squared loss on $y - Q_\theta(s, a)$ with $y = r + \gamma(1 - d)\max_{a'} Q_{\theta^-}(s', a')$ , no gradient through $y$ ; a replay buffer decorrelates samples, a target network (copy every $C$ steps or Polyak averaging) fixes the labels.
Double DQN: $y = r + \gamma(1 - d)\,Q_{\theta^-}(s', \arg\max_{a'} Q_\theta(s', a'))$ : the online network selects, the target network evaluates.
Offline RL: the max picks out-of-distribution actions whose values are never corrected (extrapolation error). CQL adds $\alpha(\log\sum_a e^{Q(s,a)} - Q(s, a_{\mathcal D}))$ , whose gradient $\operatorname{softmax}(Q) - e_{a_{\mathcal D}}$ lowers unsupported values and raises data actions.

07 Policy gradients and REINFORCE

A policy-gradient method does gradient ascent on $J(\theta) = \mathbb E[\sum_t \gamma^t r_t] = \sum_s p_0(s) V^{\pi_\theta}(s)$ directly in the policy parameters.
Log-derivative trick: $\nabla \pi = \pi \nabla \log \pi$ , so $\nabla \mathbb E_{a \sim \pi_\theta}[r(a)] = \mathbb E_{a \sim \pi_\theta}[\nabla \log \pi_\theta(a)\, r(a)]$ ; the reward need not be differentiable.
Scores: softmax $\nabla_\theta \log \pi(a) = e_a - \pi$ ; Gaussian $\partial_\mu \log \pi(a) = (a - \mu)/\sigma^2$ .
Policy gradient theorem: $\nabla J = \mathbb E[\sum_t \gamma^t \nabla \log \pi_\theta(a_t \mid s_t)\, Q^\pi(s_t, a_t)] = \sum_s d^\pi(s) \sum_a \nabla \pi_\theta(a \mid s) Q^\pi(s, a)$ ; the dynamics drop out and there is no $\nabla d^\pi$ term.
REINFORCE: $\hat g = \sum_t \gamma^t (G_t - b(s_t)) \nabla \log \pi_\theta(a_t \mid s_t)$ from one episode, with the reward-to-go $G_t$ (rewards before $t$ have a mean-zero term).
Any baseline $b(s)$ keeps the estimate unbiased because $\sum_a \nabla \pi(a \mid s) = 0$ ; $b \approx V^\pi$ turns $G_t - b$ into an advantage estimate and cuts the variance. A baseline $b(s, a)$ adds bias.
Tabular softmax: $\partial J / \partial \theta(s, a) = d^\pi(s)\, \pi(a \mid s)\, A^\pi(s, a)$ .
When states cannot be told apart, the best policy can be stochastic: in the short corridor $p^* = 2 - \sqrt 2$ and $J(p^*) \approx -11.66$ .

08 Actor-critic, GAE and SAC

Actor-critic: the critic $V_\phi$ gives the TD error $\delta_t = r_t + \gamma(1 - d_t)V_\phi(s_{t+1}) - V_\phi(s_t)$ ; the critic moves by $\eta_\phi \delta_t \nabla V_\phi$ and the actor by $\eta_\theta \delta_t \nabla \log \pi_\theta(a_t \mid s_t)$ .
The $k$ -step estimator $\hat A_t^{(k)} = \sum_{l<k}\gamma^l r_{t+l} + \gamma^k V(s_{t+k}) - V(s_t)$ has bias $\gamma^k e(s_{t+k})$ from the critic error at the bootstrap state; more real rewards mean less bias and more variance.
GAE: $\hat A_t = (1-\lambda)\sum_{k \ge 1}\lambda^{k-1}\hat A_t^{(k)} = \sum_{l \ge 0}(\gamma\lambda)^l \delta_{t+l}$ ; $\lambda = 0$ gives $\delta_t$ , $\lambda = 1$ gives $G_t - V(s_t)$ ; with an exact critic every $\lambda$ is unbiased.
Backward recursion: $\hat A_t = \delta_t + \gamma\lambda(1 - d_t)\hat A_{t+1}$ , value targets $\hat A_t + V(s_t)$ ; $d_t = 1$ only for real terminations, and truncations bootstrap from $V$ of the next state.
$\gamma$ is part of the objective; $\lambda$ only trades the critic's bias against the rewards' variance.
A2C loss: $-\log \pi\,\hat A + c_v (V - \hat G)^2 - c_e \mathcal H(\pi)$ , on fresh on-policy data from parallel environments.
TD3 fixes DDPG with clipped double Q, delayed actor updates and target policy smoothing.
SAC maximizes $\mathbb E[\sum_t \gamma^t(r_t + \alpha\mathcal H(\pi(\cdot \mid s_t)))]$ ; for discrete actions the soft-greedy policy is $\pi \propto \exp(Q/\alpha)$ and $V = \alpha\log\sum_a e^{Q/\alpha} = \pi^\top Q + \alpha\mathcal H(\pi)$ .

09 PPO and RL for LLMs

Performance difference lemma: $J(\pi') - J(\pi) = \sum_s d^{\pi'}(s) \sum_a \pi'(a \mid s) A^\pi(s, a)$ , proved by telescoping $\gamma V^\pi(s_{t+1}) - V^\pi(s_t)$ along trajectories of $\pi'$ .
The surrogate $L_\pi(\pi') = \sum_s d^\pi(s) \sum_a \pi'(a \mid s) A^\pi(s, a)$ uses the old states; it has the same value and gradient as the true improvement at $\pi' = \pi$ , but can be badly wrong for large steps.
TRPO maximizes the surrogate subject to an average KL $\le \delta$ , using $\mathrm{KL} \approx \tfrac12 \Delta^\top F \Delta$ with the Fisher matrix $F$ , conjugate gradient and a line search.
PPO maximizes $\hat{\mathbb E}[\min(\rho_t \hat A_t, \operatorname{clip}(\rho_t, 1-\varepsilon, 1+\varepsilon)\hat A_t)]$ : a pessimistic lower bound on $\hat{\mathbb E}[\rho_t \hat A_t]$ whose gradient is zero only for samples that already moved more than $\varepsilon$ in the helpful direction.
The clip does not bound the KL; PPO monitors $k_3 = (\rho - 1) - \log\rho$ , an unbiased and non-negative estimate of $\mathrm{KL}(\pi_{\text{old}} \| \pi_\theta)$ , and stops early.
LLM generation is a token-level MDP with deterministic transitions; the KL-regularized objective $\mathbb E[r] - \beta\,\mathrm{KL}(\pi_\theta \| \pi_{\text{ref}})$ gives the per-token reward $-\beta \log(\pi_\theta/\pi_{\text{ref}})$ plus the score at the last token.
The KL-regularized optimum is $\pi^* \propto \pi_{\text{ref}} \exp(r/\beta)$ with value $\beta \log Z$ ; DPO uses this formula to fit preferences without RL.
RLOO uses $A_i = \frac{K}{K-1}(r_i - \bar r)$ (unbiased); GRPO uses $(r_i - \bar r)/\mathrm{std}$ inside a clipped ratio; both replace the critic by a group of responses to the same prompt.

10 Model-based RL and AlphaZero

A model predicts $(r, s')$ from $(s, a)$ ; planning uses it to improve values or policies without new real experience. Dyna-Q = Q-learning on each real step plus $n$ Q-learning updates on transitions replayed from the model.
MPC: plan an action sequence in the model, run only the first action, observe the real state, plan again. Random shooting and the cross-entropy method (CEM) are common planners.
Open-loop model error compounds: with one-step error $\varepsilon_m$ and $L$ -Lipschitz dynamics, $\|\hat s_H - s_H\| \le \varepsilon_m (L^H - 1)/(L - 1)$ . Planners also exploit model errors (model bias).
MCTS repeats Select, Expand, Evaluate, Backup. UCT selects $\arg\max_a Q(s, a) + c\sqrt{\ln N(s)/N(s, a)}$ : UCB1 at every node. In two-player games the backup flips the sign at every level.
Behaviour cloning with error $\varepsilon$ on the expert's states has extra cost at most $T^2\varepsilon$ , and this order is reached; DAgger trains on the learner's own states with expert labels and gets $O(T\varepsilon)$ .
AlphaZero: $(p, v) = f_\theta(s)$ ; PUCT selects $\arg\max_a Q + c_{\text{puct}} P \sqrt{N(s)}/(1 + N(s, a))$ ; self-play gives targets $(\pi, z)$ ; loss $(z - v)^2 - \pi^\top \log p + c\|\theta\|^2$ . MCTS is the policy improvement step of an approximate policy iteration.
MuZero plans with MCTS in a learned latent model trained to predict rewards, values and policies; Dreamer trains an actor-critic on imagined latent rollouts; MBPO uses short model rollouts from real states.