Reinforcement Learning

Reinforcement learning is the problem of acting to maximize long-run reward when four difficulties hit at once: you optimize a utility, consequences are delayed (credit assignment), you must explore to discover what’s good, and you must generalize across states you’ve never seen. Everything in the subject hangs off one object — the value function $V^\pi(s)$, the expected discounted return from $s$ under policy $\pi$ — and one recursion, the Bellman equation, which says today’s value is the immediate reward plus the discounted value of where you land. From there the field forks along two axes. Known vs unknown model: with the model you plan (dynamic programming — iterate a Bellman operator to its fixed point); without it you learn from samples (Monte Carlo vs temporal difference). Value-based vs policy-based: value methods estimate $V/Q$ then act greedily; policy methods ascend the policy’s value directly. Convergence is earned, not assumed, and a small set of proof strategies recur — contraction + fixed point, monotone improvement, telescoping advantages, Jensen, Robbins–Monro, the score-function trick, mean-zero baselines, concentration + union bound, importance reweighting. Naming the strategy at each proof is the point: it turns a wall of derivations into a handful of reusable moves. Prerequisites cashed in: expectation, variance, conditional expectation, Markov chains (track 1); MLE and bias/variance (tracks 3, 6); contraction/fixed-point and norms (track 2); SGD, function approximation, the score function (tracks 11a, 11b); concentration and Jensen (track 1); conjugate priors (track 7); importance sampling intuition (track 9).

1. The problem: MDPs, returns, and value functions

• The agent–environment loop. At each step $t$ the agent takes action $a_t$, the world transitions and emits observation $o_t$ and reward $r_t$. The agent picks actions from a policy $\pi$ to maximize expected cumulative reward. We seek states of high value (long-run reward), not high immediate reward — that’s the whole delayed-consequence problem.
• The Markov assumption. $p(s_{t+1}\mid s_t, a_t) = p(s_{t+1}\mid h_t, a_t)$ — the state is a sufficient statistic of history; given the present, the future is independent of the past. (You can always make the state the full history, but that’s unwieldy; we assume $s_t = o_t$, full observability.)
• The MDP is the tuple $(S, A, P, R, \gamma)$: states, actions, transition dynamics $P(s'\mid s,a)$, reward $R(s,a) = \mathbb E[r_t\mid s_t{=}s, a_t{=}a]$, discount $\gamma\in[0,1]$. A policy $\pi(a\mid s)$ is a distribution over actions. (MDP + fixed policy collapses to a Markov reward process with averaged dynamics $P^\pi(s'\mid s) = \sum_a \pi(a\mid s)P(s'\mid s,a)$ — useful: prediction problems reduce to MRPs.)
• Return and value. The return is the discounted reward sum $G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots$ ($\gamma$ toward 1 weights the future more; $\gamma<1$ keeps infinite-horizon returns finite). The state-value and action-value functions are

$V^\pi(s) = \mathbb E_\pi[G_t\mid s_t{=}s], \qquad Q^\pi(s,a) = \mathbb E_\pi[G_t\mid s_t{=}s, a_t{=}a].$

$V$ measures how good a state is; $Q$ how good an action is from a state. They link by $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')$.

• Two tasks: prediction (evaluate a given $\pi$) vs control (find the best $\pi$). Model-based (you have/estimate $P, R$) vs model-free (you only sample).

Core competency set

• State the Markov assumption, the MDP tuple, return, and $V^\pi/Q^\pi$ with their linking equations.
• Distinguish prediction vs control and model-based vs model-free.

2. The Bellman equations — the recursion everything rests on

• Where it comes from — split the return after one step, $G_t = r_t + \gamma G_{t+1}$, and take expectations:

$V^\pi(s) = \mathbb E_\pi[r_t + \gamma G_{t+1}\mid s_t{=}s].$

The expected next-step return is itself a value, $\mathbb E_\pi[G_{t+1}\mid s_{t+1}] = V^\pi(s_{t+1})$:

$V^\pi(s) = \mathbb E_\pi[r_t + \gamma V^\pi(s_{t+1})\mid s_t{=}s].$

Reading the expectation out over $\pi$ and $P$ gives the Bellman expectation equation

$V^\pi(s) = R^\pi(s) + \gamma\sum_{s'}P^\pi(s'\mid s)\,V^\pi(s').$

Today’s value = immediate reward + discounted value of the next state. A one-step lookahead, in other words.

• Matrix form (finite states): $V = R^\pi + \gamma P^\pi V$, solved directly by $V = (I - \gamma P^\pi)^{-1}R^\pi$ — exact but $O(|S|^3)$ and needs the inverse to exist (it does for $\gamma<1$).
• Bellman optimality for the best policy maxes over actions instead of averaging:

$V^*(s) = \max_a\Big[R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V^*(s')\Big].$

• The Bellman operators turn these equations into maps on value functions — the objects whose fixed points are the value functions:

$(B^\pi V)(s) = R^\pi(s) + \gamma\sum_{s'}P^\pi(s'\mid s)V(s'), \qquad (B^*V)(s) = \max_a\Big[R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V(s')\Big].$

$V^\pi$ is the fixed point of $B^\pi$; $V^*$ the fixed point of $B^*$. The next section’s algorithms are just iterating these operators.

• Picture (draw it): the backup diagram — state $s$ at the root branches down to action nodes (the agent’s choice), each action branches to next-state nodes (the environment’s chance), one step deep. The Bellman expectation equation averages values back up this tree; optimality takes a max at the action layer instead of an average. Every value-based algorithm is some version of backing values up this diagram.

Core competency set

• Derive the Bellman expectation equation from $G_t = r_t + \gamma G_{t+1}$; write the optimality equation and the matrix solve.
• Define $B^\pi$ and $B^*$ and state that $V^\pi, V^*$ are their fixed points.

3. Planning by dynamic programming (known model)

• Policy evaluation = compute $V^\pi$ by iterating $V_{k} = B^\pi V_{k-1}$ from any $V_0$ until convergence (a “Bellman backup,” a full sweep of states each iteration). It converges because $B^\pi$ is a contraction (proved below alongside $B^*$).
• Policy iteration = alternate evaluate ($V^\pi$) and greedily improve ($\pi'(s) = \arg\max_a Q^\pi(s,a)$) until the policy stops changing. Two guarantees make it work:
  • Policy improvement theorem — strategy: telescoping the one-step improvement inequality. Let $\pi'$ be greedy w.r.t. $Q^\pi$, so $Q^\pi(s,\pi'(s)) = \max_a Q^\pi(s,a) \ge Q^\pi(s,\pi(s)) = V^\pi(s)$. Then unroll:

$V^\pi(s) \le Q^\pi(s,\pi'(s)) = \mathbb E_{\pi'}[r_t + \gamma V^\pi(s_{t+1})\mid s_t{=}s]$

$\le \mathbb E_{\pi'}[r_t + \gamma Q^\pi(s_{t+1},\pi'(s_{t+1}))\mid s_t{=}s]$

$\le \mathbb E_{\pi'}[r_t + \gamma r_{t+1} + \gamma^2 V^\pi(s_{t+2})\mid s_t{=}s] \le \cdots \le V^{\pi'}(s).$

Each step replaces a $V^\pi$ by the at-least-as-large $Q^\pi(\cdot,\pi')$ and expands one more reward; in the limit, $V^{\pi'} \ge V^\pi$.

• Termination — strategy: monotone improvement over a finite set. Each iteration strictly improves a deterministic policy, and there are only $|A|^{|S|}$ of them, so no policy repeats → it halts. At the halt, greedy gives no change, so $V^\pi(s) = \max_a Q^\pi(s,a)$ — the Bellman optimality equation — hence $\pi$ is optimal.
• Value iteration = iterate the optimality operator $V_{k} = B^* V_{k-1}$ directly (no separate evaluation phase), reading off $\pi$ at the end via one greedy step. Intuition: $V_k$ is the optimal value with $k$ steps left; grow the horizon. (Unlike policy iteration, the iterates don’t increase monotonically — they converge from wherever they start.)
• The convergence proof (the centerpiece) — strategy: contraction mapping + Banach fixed-point theorem. Claim: $B^*$ is a $\gamma$-contraction in the sup-norm, $\lVert B^*V - B^*U\rVert_\infty \le \gamma\lVert V - U\rVert_\infty$. For any state $s$,

$|B^*V(s) - B^*U(s)| = \Big|\max_a Q_V(s,a) - \max_a Q_U(s,a)\Big| \le \max_a |Q_V(s,a) - Q_U(s,a)|$

(using $|\max_a f - \max_a g| \le \max_a |f-g|$), and each term is

$\max_a\,\gamma\Big|\sum_{s'}P(s'\mid s,a)\big(V(s') - U(s')\big)\Big| \le \gamma\max_a\sum_{s'}P(s'\mid s,a)\,\lVert V-U\rVert_\infty = \gamma\lVert V-U\rVert_\infty$

(probabilities sum to 1). Take the max over $s$: $\lVert B^*V - B^*U\rVert_\infty \le \gamma\lVert V-U\rVert_\infty$. Since $\gamma<1$, Banach gives a unique fixed point $V^*$ and geometric convergence $\lVert V_k - V^*\rVert_\infty \le \gamma^k\lVert V_0 - V^*\rVert_\infty$. The identical argument for $B^\pi$ proves policy evaluation converges to the unique $V^\pi$.

• Finite horizon: just iterate value iteration exactly $H$ times ($V_0 = 0$); now the optimal policy is non-stationary — with 1 step left vs 10, the best action differs.

Problem	Bellman equation	Algorithm
Prediction	expectation	iterative policy evaluation
Control	expectation + greedy improvement	policy iteration
Control	optimality	value iteration

Core competency set

• Run policy evaluation/iteration/value iteration as operator iterations; state which Bellman equation each uses.
• Prove the policy improvement theorem (telescoping) and policy-iteration termination (monotone + finite).
• Prove $B^*$ (and $B^\pi$) is a $\gamma$-contraction and invoke Banach for unique fixed point + geometric convergence.

4. Model-free prediction — learning $V^\pi$ from samples

The move to learning: we no longer know $P, R$, only sampled experience. Two estimators of $V^\pi$, trading off bias and variance.

• Monte Carlo (MC). Replace the expectation $\mathbb E[G_t]$ with an empirical mean of complete-episode returns. Maintain a count $N(s)$ and update incrementally (the running-mean identity $\mu_k = \mu_{k-1} + \tfrac1k(x_k - \mu_{k-1})$):

$V^\pi(s) \leftarrow V^\pi(s) + \tfrac{1}{N(s)}\big(G_{t} - V^\pi(s)\big).$

First-visit MC (count only the first visit per episode) is unbiased; every-visit is biased (within-episode dependence) but consistent. Properties: no Markov assumption, but episodic only (you must wait for the episode to end), and high variance (a full return accumulates all the randomness of a trajectory).

• Temporal difference (TD(0)). Don’t wait for the episode — bootstrap: replace the unknown rest-of-return with the current estimate of the next state’s value. With the TD target $r_t + \gamma V^\pi(s_{t+1})$ and TD error $\delta_t = r_t + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)$,

$V^\pi(s_t) \leftarrow V^\pi(s_t) + \alpha\,\delta_t.$

This is the Bellman equation with the expectation over $s_{t+1}$ replaced by a single sample. Properties: online (updates every step), works in continuing settings, uses the Markov property, lower variance (only one step’s randomness) but biased (the bootstrap target uses an estimate).

• DP with certainty equivalence: estimate the MLE model from data (count transitions, average rewards), then plan on it. Data-efficient and consistent, but expensive (re-solve the MDP each update).
• The comparison. MC is unbiased, high-variance, assumption-light, insensitive to initialization; TD is biased, low-variance, more data-efficient, Markov-exploiting, but converges only guaranteed under tabular representations. The classic AB example: MC converges to the minimum-MSE fit on the observed returns; TD converges to the value of the maximum-likelihood Markov model — so TD effectively builds and exploits a model of the world.
• Numeric anchor (Mars rover, $\gamma = 0.9$, observed trajectory $s_3\!\to\!s_2\!\to\!s_2\!\to\!s_1\!\to$ terminal with rewards $0,0,0,1$). Returns per visit: $G(s_3) = \gamma^3 = 0.729$, first $G(s_2) = \gamma^2 = 0.81$, second $G(s_2) = \gamma = 0.9$, $G(s_1) = 1$. First-visit MC counts only the first $s_2$: $V(s_2) = 0.81$. Every-visit MC averages both visits: $V(s_2) = \tfrac12(0.81 + 0.9) = 0.855$. TD(0) on the first tuple $(s_3, r{=}0, s_2)$ with $\alpha = 0.5$ and all values init 0: target $0 + \gamma V(s_2) = 0$, so $V(s_3)$ stays 0 — TD propagates the terminal reward back one step per sweep, where MC moved it in a single episode (variance-for-immediacy, made concrete).

Core competency set

• Write MC (incremental mean) and TD(0) (TD error/target) updates; identify TD as “Bellman with a sampled next state.”
• Lay out the MC-vs-TD tradeoff (bias/variance, episodic/online, Markov) and the AB / min-MSE-vs-max-likelihood distinction.

5. Model-free control — learning to act

• Generalized policy iteration (GPI) without a model. Greedy improvement on $V$ needs the model ($\arg\max_a R + \gamma\sum P V$), so switch to $Q$: $\arg\max_a Q(s,a)$ needs no model. But pure greed never explores untried actions — hence the explore/exploit tradeoff. Picture (draw it): GPI as two interacting processes pulling on $(V,\pi)$ — evaluation drags $V$ toward $V^\pi$, improvement drags $\pi$ toward greedy$(V)$; each step partly undoes the other, and they come to rest only at $(V^*,\pi^*)$, the one point consistent with both (the Bellman optimality equation). Almost every control algorithm here is GPI with a different evaluation step (MC/TD/$n$-step) and a softened greedy ($\varepsilon$-greedy).
• $\varepsilon$-greedy balances them: with prob $1-\varepsilon$ take the greedy action, else a uniform random one.
  • Monotone $\varepsilon$-greedy improvement — strategy: the policy improvement theorem again, checking the one-step inequality survives. For the $\varepsilon$-greedy $\pi'$ w.r.t. $Q^\pi$,

$\sum_a \pi'(a\mid s)Q^\pi(s,a) = \tfrac{\varepsilon}{|A|}\sum_a Q^\pi(s,a) + (1-\varepsilon)\max_a Q^\pi(s,a) \ge V^\pi(s),$

because shifting weight onto the max action (relative to $\pi$) can only raise the average. The improvement theorem then gives $V^{\pi'}\ge V^\pi$.

• GLIE (Greedy in the Limit with Infinite Exploration): every $(s,a)$ visited infinitely often and the policy converges to greedy (e.g. $\varepsilon_i = 1/i$). GLIE Monte-Carlo control converges to $Q^*$.
• SARSA — on-policy TD control on $Q$, updating from the tuple $(s,a,r,s',a')$ where $a'$ is drawn from the current ($\varepsilon$-greedy) policy:

$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\big(r_t + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)\big).$

Convergence to $Q^*$ requires (1) a GLIE policy sequence and (2) Robbins–Monro step sizes $\sum_t \alpha_t = \infty,\ \sum_t \alpha_t^2 < \infty$ — strategy: stochastic approximation (steps big enough to reach anywhere, shrinking enough to settle).

• Q-learning — off-policy control: bootstrap off the best next action rather than the one taken, so it learns $Q^*$ while behaving with an exploratory policy:

$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\big(r_t + \gamma\max_{a'}Q(s_{t+1},a') - Q(s_t,a_t)\big).$

Needs only $(s,a,r,s')$. Converges to $Q^*$ with all $(s,a)$ visited infinitely often and R–M step sizes — not requiring GLIE (that’s only needed to make the behavior policy optimal).

• Maximization bias — strategy: Jensen’s inequality (max is convex). Even with unbiased per-action estimates $\hat Q$, the greedy value over-estimates:

$\hat V^{\hat\pi}(s) = \mathbb E\big[\max_a \hat Q(s,a)\big] \ge \max_a \mathbb E[\hat Q(s,a)] = \max_a Q(s,a).$

The fix — double Q-learning — splits the data into two independent estimates, using $Q_1$ to select $a^* = \arg\max_a Q_1(s,a)$ and $Q_2$ to evaluate $Q_2(s,a^*)$, decoupling selection from evaluation so the estimate is unbiased.

Core competency set

• Explain why control needs $Q$ (model-free greedy) and $\varepsilon$-greedy; prove monotone $\varepsilon$-greedy improvement.
• Write SARSA (on-policy) vs Q-learning (off-policy, the max) and their convergence conditions (GLIE + R–M; R–M alone for $Q^*$).
• Derive maximization bias via Jensen and explain double-Q’s selection/evaluation split.

6. Value-function approximation and deep RL

• Why. Tabular $V/Q$ can’t handle large or continuous state spaces. Parameterize $\hat V(s;w)$, $\hat Q(s,a;w)$ (tabular is the special case where features are state indicators). Fit by SGD on the mean-squared value error $\text{MSVE}(w) = \sum_s \mu(s)\big(V^\pi(s) - \hat V(s;w)\big)^2$, $\mu$ the state-visitation distribution.
• The oracle/supervised view. If an oracle gave $V^\pi(s)$, this is regression on $(s, V^\pi(s))$ pairs: $\Delta w = \alpha\big(V^\pi(s) - \hat V(s;w)\big)\nabla_w\hat V$. No oracle exists, so plug in a target:
  • MC-VFA: target = return $G_t$ (unbiased). $w \leftarrow w + \alpha(G_t - x(s)^Tw)x(s)$; converges to the min-MSVE weights $w_{MC}$ (the best linear approximation, which may not be $V^\pi$).
  • TD-VFA: target = bootstrapped $r + \gamma\hat V(s';w)$ (a semi-gradient — we don’t differentiate through the target); biased, but lower variance, and converges to a different fixed point.
• The deadly triad. Combining bootstrapping + function approximation + off-policy learning can diverge. (Each pair is fine; all three together is the danger — the central caution of deep RL.)
• DQN makes Q-learning + neural nets stable with two tricks that attack the triad’s instabilities: experience replay (sample past transitions in random minibatches — breaks the temporal correlation that violates i.i.d.) and a target network (a periodically-frozen copy supplies the bootstrap target — stops the target from chasing the parameters). Extensions: double DQN (maximization-bias fix, online net selects / target net evaluates), prioritized replay (sample high-TD-error transitions more often), dueling DQN (split the head into $V(s)$ + advantage $A(s,a)$).

Core competency set

• Set up MSVE and the SGD update; contrast MC-VFA (unbiased target) vs TD-VFA (semi-gradient, biased) and their fixed points.
• State the deadly triad and how DQN’s replay + target network address it; name double/prioritized/dueling.

7. Policy gradient methods — optimize the policy directly

• Why policy-based. Parameterize the policy $\pi_\theta(a\mid s)$ and ascend its value. Advantages: smoother convergence (no value-function discontinuities flipping the greedy action), works in continuous/high-dimensional action spaces (no global $\max_a$), and can represent stochastic optimal policies (needed under partial observability / state aliasing — e.g. rock-paper-scissors). Disadvantage: typically local optima, high variance.
• The objective $J(\theta) = V^{\pi_\theta}(s_0) = \sum_\tau P(\tau;\theta)R(\tau)$ over trajectories $\tau$.
• The score-function / likelihood-ratio trick — strategy: $\nabla p = p\,\nabla\log p$ to turn a gradient of a probability into an expectation. Differentiate the objective:

$\nabla_\theta J = \sum_\tau \nabla_\theta P(\tau;\theta)\,R(\tau).$

Multiply and divide by $P$ (the log-derivative identity):

$= \sum_\tau P(\tau;\theta)\,\nabla_\theta\log P(\tau;\theta)\,R(\tau).$

Recognize the weighted sum as an expectation:

$= \mathbb E_\tau\big[R(\tau)\,\nabla_\theta\log P(\tau;\theta)\big].$

Now expand the trajectory log-prob into its factors:

$\nabla_\theta\log P(\tau;\theta) = \nabla_\theta\Big[\log\mu(s_0) + \sum_t \log p(s_{t+1}\mid s_t,a_t) + \sum_t\log\pi_\theta(a_t\mid s_t)\Big].$

Drop every term free of $\theta$ — $\mu$ and the dynamics $p$ vanish, the key payoff: the model cancels:

$\nabla_\theta\log P(\tau;\theta) = \sum_t \nabla_\theta\log\pi_\theta(a_t\mid s_t).$

Estimate by sampling $m$ trajectories: $\hat g = \tfrac1m\sum_i R(\tau_i)\sum_t\nabla_\theta\log\pi_\theta(a_t^i\mid s_t^i)$.

• Policy gradient theorem (general, beyond episodic): for any of the standard objectives,

$\nabla_\theta J(\theta) = \mathbb E_{\pi_\theta}\big[\nabla_\theta\log\pi_\theta(a\mid s)\,Q^{\pi_\theta}(s,a)\big].$

The intuition: push up the log-probability of actions in proportion to how good they are. (Softmax policy score: $\nabla_\theta\log\pi = \phi(s,a) - \mathbb E_{\pi}[\phi(s,\cdot)]$ — feature of the action taken minus its average.)

• REINFORCE: use the sampled return $G_t$ as an unbiased estimate of $Q^{\pi}$: $\theta \leftarrow \theta + \alpha\,\nabla_\theta\log\pi_\theta(s_t,a_t)\,G_t$. Correct but high variance (it’s Monte-Carlo).
• Baselines and the advantage — strategy: subtract a mean-zero term to cut variance without touching the mean. Claim: for any $b(s)$ that depends only on the state, $\mathbb E_\pi[\nabla_\theta\log\pi_\theta(a\mid s)\,b(s)] = 0$. Pull $b(s)$ out and write the inner sum over actions:

$\mathbb E_{\pi}\big[\nabla_\theta\log\pi_\theta(a\mid s)\,b(s)\big] = \sum_s d(s)\,b(s)\sum_a \pi_\theta(a\mid s)\,\nabla_\theta\log\pi_\theta(a\mid s).$

Undo the log-derivative ($\pi\,\nabla\log\pi = \nabla\pi$):

$= \sum_s d(s)\,b(s)\sum_a \nabla_\theta\pi_\theta(a\mid s).$

Swap the sum and gradient; the action probabilities sum to 1, so its gradient is 0:

$= \sum_s d(s)\,b(s)\,\nabla_\theta\!\Big(\sum_a\pi_\theta(a\mid s)\Big) = \sum_s d(s)\,b(s)\,\nabla_\theta 1 = 0.$

So subtracting $b(s)$ leaves the gradient unbiased but can shrink its variance. The near-optimal choice is $b(s) = V^\pi(s)$, giving the advantage $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$ (“how much better than average is this action”):

$\nabla_\theta J = \mathbb E_{\pi}\big[\nabla_\theta\log\pi_\theta(a\mid s)\,A^\pi(s,a)\big].$

• Actor–critic. Maintain an actor (policy $\theta$) and a critic (value estimate $w$). The critic supplies the advantage. The clean trick: the TD error is an unbiased sample of the advantage —

$\mathbb E_\pi\big[\delta^\pi\mid s,a\big] = \mathbb E_\pi\big[r + \gamma V^\pi(s')\mid s,a\big] - V^\pi(s).$

The first term is exactly $Q^\pi(s,a)$ (Bellman), so the difference is the advantage:

$\mathbb E_\pi\big[\delta^\pi\mid s,a\big] = Q^\pi(s,a) - V^\pi(s) = A^\pi(s,a),$

so $\nabla_\theta J = \mathbb E_\pi[\nabla_\theta\log\pi_\theta(a\mid s)\,\delta^\pi]$, using the approximate $\delta_v = r + \gamma V_w(s') - V_w(s)$ in practice. Variance reduction also comes from reward-to-go (only future rewards multiply each $\nabla\log\pi_t$) and $n$-step / blended targets.

• Monotonic improvement → TRPO. Stepping too far in RL is unrecoverable (a bad policy collects bad data). The performance-difference lemma — strategy: express one policy’s value via the other’s advantages —

$V(\tilde\theta) = V(\theta) + \mathbb E_{\pi_{\tilde\theta}}\Big[\sum_{t}\gamma^t A_{\pi_\theta}(s_t,a_t)\Big].$

Why (telescoping): along a $\tilde\pi$-trajectory, expand the advantage $A_{\pi_\theta}(s_t,a_t) = r_t + \gamma V_{\pi_\theta}(s_{t+1}) - V_{\pi_\theta}(s_t)$, so

$\sum_t \gamma^t A_{\pi_\theta}(s_t,a_t) = \sum_t \gamma^t r_t - V_{\pi_\theta}(s_0)$

(the discounted $V$ terms telescope) $= G - V(\theta)$; take $\mathbb E_{\tilde\pi}$ to get $V(\tilde\theta) - V(\theta)$. Exact, but it needs the new policy’s state distribution $\mu_{\tilde\pi}$. Local approximation swaps in the old $\mu_\pi$ to get a surrogate $L_\pi(\tilde\pi)$ that matches $V$ and its gradient at $\theta$. Conservative policy iteration bounds the gap by a term in the policy difference; generalizing to a KL-divergence penalty gives a guaranteed-improvement lower bound. TRPO maximizes the surrogate subject to a trust-region KL constraint (the principled, larger step size), using importance sampling and a linear-objective/quadratic-constraint solve.

Core competency set

• Derive $\nabla J = \mathbb E[\nabla\log\pi\,R]$ via the score-function trick and show the dynamics cancel; state the policy gradient theorem.
• Prove the baseline leaves the gradient unbiased ($\mathbb E[\nabla\log\pi\,b(s)] = 0$) and define the advantage; show $\delta$ is an unbiased advantage sample.
• Explain REINFORCE → actor-critic (variance reduction) and the performance-difference-lemma → TRPO trust-region story.

8. Exploration and bandits

• Multi-armed bandit (MAB) = a single-state MDP: actions (“arms”) with unknown reward distributions; maximize cumulative reward. The pure-greedy estimator $\hat Q_t(a) = \tfrac{1}{N_t(a)}\sum r\mathbb 1[a_\tau{=}a]$ can lock onto a suboptimal arm forever.
• Regret is the currency: $L_t = \mathbb E\big[\sum_\tau V^* - Q(a_\tau)\big]$. Decompose it by gaps and counts — strategy: rewrite the sum over time as a sum over arms — with gap $\Delta_a = V^* - Q(a)$:

$L_t = \sum_a \mathbb E[N_t(a)]\,\Delta_a.$

A good algorithm keeps small counts on large-gap arms. Greedy and fixed-$\varepsilon$-greedy have linear regret (a constant fraction of pulls are suboptimal); the goal is sub-linear, and the lower bound is logarithmic, $L_t \gtrsim \log t\sum_a \Delta_a / D_{KL}(\mathcal R^a\Vert\mathcal R^{a^*})$.

• Optimism under uncertainty → UCB — strategy: a concentration inequality + invert for a bonus + union bound over time. Hoeffding: $P\big(\mathbb E[X] > \bar X_n + u\big) \le e^{-2nu^2}$. Set the RHS to a target $\delta$ and solve for the bonus:

$e^{-2N_t(a)\,u^2} = \delta \ \Rightarrow\ u = \sqrt{\frac{\log(1/\delta)}{2N_t(a)}},$

so $Q(a) \le \hat Q_t(a) + u$ with probability $\ge 1-\delta$. Choosing $\delta = t^{-4}$ (so it holds across all steps, via a union bound) gives UCB1:

$a_t = \arg\max_a\Big[\hat Q_t(a) + \sqrt{\tfrac{2\log t}{N_t(a)}}\Big].$

Less-tried arms (small $N_t$) get a bigger bonus → exploration. Regret bound — strategy: a pulled suboptimal arm had a high UCB, so the gap is bounded by the bonus. When UCB pulls suboptimal $a$, its index beats the optimal’s, which (under the concentration event) exceeds $Q(a^*)$; chaining gives $2\sqrt{C\log t/N_t(a)} \ge \Delta_a$, hence $N_t(a) \le 4C\log t/\Delta_a^2$, and $L_t = \sum_a \Delta_a N_t(a) = O\big(\sum_a \log T/\Delta_a\big)$ — logarithmic, matching the lower bound’s rate. Picture: draw each arm’s value as a distribution; optimism compares the upper ends, so a wide (uncertain) arm can outrank a higher-mean narrow one — and its band shrinks as you sample it, which is the explore→exploit transition made visible.

• PAC (an alternative criterion): act $\varepsilon$-optimally with probability $\ge 1-\delta$ on all but a polynomial number of steps. Optimistic initialization (init $Q$ high) is a simpler route to sub-linear regret if tuned right — but optimism may not survive function approximation.
• Bayesian bandits & Thompson sampling. Keep a posterior over each arm’s reward parameter (e.g. Beta–Bernoulli conjugacy, posterior $\text{Beta}(\alpha+\#1, \beta+\#0)$). Thompson sampling: sample a parameter from each arm’s posterior, act greedily w.r.t. the sampled values, update the chosen arm’s posterior. It implements probability matching — select arm $a$ with probability that it is optimal, $\pi(a\mid h_t) = P(Q(a) > Q(a')\ \forall a'\mid h_t)$ — which is automatically optimistic (more-uncertain arms have more upside mass). Achieves the Lai–Robbins lower bound; sensitive to prior misspecification (no mass on the truth → can’t converge). Contextual bandits add an i.i.d. context per step (between bandits and MDPs).
• Numeric anchor. UCB, two arms at $t = 10$: arm 1 pulled $N_1 = 8$, mean $\hat Q_1 = 0.5$; arm 2 pulled $N_2 = 2$, mean $\hat Q_2 = 0.4$. Bonuses $\sqrt{2\ln 10 / 8} \approx 0.76$ and $\sqrt{2\ln 10 / 2} \approx 1.52$; indices $0.5 + 0.76 = 1.26$ vs $0.4 + 1.52 = 1.92$ → pull the less-tried arm 2 despite its lower mean (optimism in action). Thompson: arm with prior $\text{Beta}(1,1)$ (mean $0.5$), observe reward 0 → posterior $\text{Beta}(1,2)$ (mean $\tfrac13$); a later reward 1 → $\text{Beta}(2,2)$ (mean back to $0.5$, but tighter).

Core competency set

• Define regret and decompose it into gaps × counts; explain why greedy/$\varepsilon$-greedy are linear and the log-$t$ lower bound.
• Derive the UCB bonus from Hoeffding (+ union bound) and sketch the $N_t(a) = O(\log t/\Delta_a^2)$ regret argument.
• Explain Thompson sampling and that it implements probability matching.

9. Fast MDP learning and offline (batch) RL

• Optimism in MDPs: MBIE-EB adds an exploration bonus to rewards in a tabular MDP (the UCB idea lifted to states/actions); Bayesian MDPs maintain a posterior over dynamics.
• The batch/offline setting: you’re handed a fixed dataset of trajectories from a behavior policy $\pi_b$ and must evaluate/optimize a new policy $\pi_e$ without collecting more data — the counterfactual, censored-data problem (you only see outcomes of decisions actually taken). Assumptions to make it tractable: stationarity, Markov, sequential ignorability (no unrecorded confounders — the potential-outcomes link to track 9), and overlap ($\pi_b(a\mid s) > 0$ wherever $\pi_e(a\mid s) > 0$ — you can’t evaluate actions the data never tried). The deadly triad bites again for off-policy value methods.
• Off-policy evaluation by importance sampling — strategy: importance reweighting (multiply and divide by the sampling density). To estimate $\mathbb E_p[r]$ from samples drawn from $q$:

$\mathbb E_p[r] = \sum_x p(x)\,r(x).$

Multiply and divide by the sampling density $q$:

$= \sum_x q(x)\,\frac{p(x)}{q(x)}\,r(x) = \mathbb E_q\Big[\tfrac{p(x)}{q(x)}\,r(x)\Big].$

Estimate from samples $x_i \sim q$:

$\approx \tfrac1N\sum_i \frac{p(x_i)}{q(x_i)}\,r(x_i).$

Sample under $q$ (behavior), reweight by $p/q$ — unbiased given overlap. Lifted to trajectories, $V^\pi(s) = \mathbb E_{\tau\sim\pi_b}\big[\tfrac{p(\tau\mid\pi)}{p(\tau\mid\pi_b)}R(\tau)\big]$, and expanding the trajectory probabilities, the dynamics $p(s'\mid s,a)$ cancel — only the product of policy ratios $\prod_t \tfrac{\pi(a_t\mid s_t)}{\pi_b(a_t\mid s_t)}$ remains. So importance sampling is unbiased with no Markov assumption and no model — but high variance: the product of ratios makes variance scale exponentially in the horizon. Per-decision IS trims it (a reward only needs the ratios up to its own time, since later actions can’t affect it). (Effective sample size flags how little data a recommendation truly rests on.)

Core competency set

• List the offline-RL assumptions (stationarity, Markov, ignorability, overlap) and why overlap is required.
• Derive the importance-sampling estimator and the trajectory version where dynamics cancel; state its unbiasedness, the no-Markov property, and the exponential-in-horizon variance.

10. Model-based RL and Monte Carlo tree search

• Model-based RL: learn $\hat p(s'\mid s,a)$ and $\hat r(s,a)$ from experience (supervised regression / density estimation), then plan on the learned model. Upside: data-efficient, and the model’s uncertainty can guide exploration. Downside: two error sources — model error and planning error on top of it.
• Sample-based planning: use the model only as a simulator of $(s', r)$, then run any model-free method on the simulated experience.
• Simulation-based search computes a policy only for the current state (no full state-space sweep — efficient when you visit only a small subset). Simple MC search: from the current state, simulate $K$ episodes per action under a fixed policy and pick the highest mean return (one step of policy improvement). The expectimax tree does better — full lookahead taking $\max$ at action nodes and expectation at state nodes (value iteration on the current sub-MDP) — but is $(|S||A|)^H$. Picture (draw it): the expectimax tree — square max nodes (actions) alternating with round expectation nodes (next states), rooted at the current state; MCTS grows only the promising branches (UCB-selecting at each max node) and rolls out a default policy past the frontier, instead of expanding the whole tree.
• MCTS avoids building the whole tree: run $K$ simulations from the root, each with a tree policy (pick actions to maximize $Q$ inside the explored tree) and a rollout policy (random/default once you leave it); a node’s value is the average return of simulations passing through it. Converges to the optimal action with enough simulations; best for large state space, small action space, long horizon.
• UCT = MCTS where each tree node is treated as its own bandit and actions are chosen by UCB: $Q(s,a,i) + c\sqrt{\tfrac{\ln n(s)}{n(s,a)}}$ — so search effort concentrates on promising, under-explored branches. The simulating policy changes as estimates evolve.
• AlphaGo ties it together: an adversarial (minimax) tree, a value network for position evaluation and a policy network (bootstrapped by imitation learning of human moves, then self-play) to prune the huge action branching, bootstrapping instead of rolling to the leaf (MC → TD), and self-play to densify the win/loss reward signal.

Core competency set

• Contrast model-based (learn model, plan; two error sources) with model-free; explain sample-based planning.
• Explain MCTS (tree vs rollout policy, node value) and UCT (each node a UCB bandit); summarize AlphaGo’s value net + policy net + self-play.

11. Memorize cold

• Return $G_t = \sum_k \gamma^k r_{t+k}$; value $V^\pi(s) = \mathbb E_\pi[G_t\mid s]$, $Q^\pi(s,a) = \mathbb E_\pi[G_t\mid s,a]$; $V^\pi(s) = \sum_a\pi(a\mid s)Q^\pi(s,a)$.
• Bellman expectation $V^\pi = R^\pi + \gamma P^\pi V^\pi$ (matrix solve $(I-\gamma P^\pi)^{-1}R^\pi$); optimality $V^*(s) = \max_a[R(s,a) + \gamma\sum_{s'}P(s'\mid s,a)V^*(s')]$. Operators $B^\pi, B^*$; $V^\pi, V^*$ are their fixed points.
• $B^*$ is a $\gamma$-contraction in $\lVert\cdot\rVert_\infty$ → Banach → unique $V^*$, $\lVert V_k - V^*\rVert_\infty \le \gamma^k\lVert V_0 - V^*\rVert_\infty$. (proof strategy: contraction + fixed point.)
• Policy iteration: evaluate + greedy; improvement theorem (telescoping) + finite policies → terminates at optimal. Value iteration: iterate $B^*$.
• MC update $V\leftarrow V + \tfrac1N(G_t - V)$ (unbiased FV, high variance, episodic). TD(0) $V(s_t)\leftarrow V(s_t) + \alpha\delta_t$, $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ (biased, low variance, online, Markov).
• SARSA (on-policy) target $r + \gamma Q(s',a')$; Q-learning (off-policy) target $r + \gamma\max_{a'}Q(s',a')$. Converge with R–M steps ($\sum\alpha=\infty, \sum\alpha^2<\infty$); SARSA→$Q^*$ needs GLIE.
• Maximization bias: $\mathbb E[\max\hat Q]\ge\max\mathbb E[\hat Q]$ (Jensen) → double-Q (select with $Q_1$, evaluate with $Q_2$).
• Deadly triad = bootstrapping + function approximation + off-policy → can diverge. DQN = replay + target network.
• Score-function trick: $\nabla_\theta J = \mathbb E[\nabla_\theta\log\pi_\theta(a\mid s)\,Q^\pi(s,a)]$; dynamics cancel in $\nabla\log P(\tau)=\sum_t\nabla\log\pi_\theta$. REINFORCE uses $G_t$. Baseline $b(s)$ keeps it unbiased ($\mathbb E[\nabla\log\pi\,b]=0$); advantage $A = Q - V$; TD error is an unbiased $A$ sample.
• Regret $L_t = \sum_a \mathbb E[N_t(a)]\Delta_a$. UCB1 $\hat Q(a)+\sqrt{2\log t/N_t(a)}$ (Hoeffding + union bound) → $O(\sum_a\log T/\Delta_a)$ regret. Thompson sampling = sample posterior, act greedy = probability matching.
• Importance sampling $\mathbb E_p[r]=\mathbb E_q[\tfrac pq r]$; trajectory IS keeps only $\prod_t\pi/\pi_b$ (dynamics cancel) — unbiased, no Markov, variance exponential in $H$. Needs overlap.
• UCT = MCTS with a UCB bandit at each node.

Named moves (cross-track glossary): value-is-the-object (everything hangs off $V/Q$); one-step-lookahead (the Bellman recursion); contraction-then-fixed-point (VI/PE convergence — Banach, track 2); monotone-improvement-over-finite-set (PI terminates); telescope-the-advantage (policy improvement & performance-difference lemmas); bootstrap-vs-sample-the-return (TD vs MC, the bias/variance dial); Robbins–Monro (stochastic-approximation step sizes); Jensen-overestimates-the-max (maximization bias → decouple select/evaluate); score-function-trick ($\nabla p = p\nabla\log p$, model-free policy gradient — tracks 11a/11b); subtract-a-mean-zero-baseline (variance reduction without bias); TD-error-is-the-advantage; optimism-under-uncertainty (UCB / MBIE / Thompson); concentration-plus-union-bound (UCB bonus & regret — track 1); probability-matching (Thompson); importance-reweighting (off-policy evaluation, dynamics cancel — track 9); bandit-at-every-node (UCT); simulate-don’t-enumerate (sample-based planning breaks the curse of dimensionality).