Reinforcement Learning

RL learns a policy pi(a|s) from a scalar reward that arrives late and aggregated; every algorithm here is one way to estimate “was that action good?” with low bias and low variance, and the reward you write down is the specification the optimizer will exploit to the letter.

MDP and gamma

• MDP = (S, A, P, R, gamma). Data is transitions (s, a, r, s'); no labels.
• Return G_t = r_t + gamma·r_(t+1) + gamma^2·r_(t+2) + ...; objective is E[G_0].
• gamma is a horizon, not a preference. Effective horizon = 1/(1-gamma) steps (0.9→10, 0.99→100).
• Raising gamma sees further but slows learning: it is the Bellman contraction factor, so error shrinks by gamma per sweep.
• A reward past the 1% horizon can’t be learned: at gamma=0.9, a reward 100 steps out is 0.9^100 = 2.7e-5, below gradient noise.
• Value bound at |r|<=1 equals the effective horizon; at gamma=0.99 a value of 80 is fine, 8000 is broken.

Value, Q, advantage, Bellman

• V^pi(s) = expected return from s; Q^pi(s,a) = same but first action forced to a; A = Q - V.
• Advantage is centered: E_{a~pi}[A^pi(s,a)] = 0 (its low-variance value comes from this).
• Bellman = split the return after one step; the only difference is what’s assumed next:

V^pi(s)   = SUM_a pi(a|s)[ R + gamma·SUM_s' P(s'|s,a) V(s') ]
Q^pi(s,a) = R + gamma·SUM_s' P·SUM_a' pi(a'|s') Q(s',a')    <- expectation over a'
Q*(s,a)   = R + gamma·SUM_s' P·max_a' Q*(s',a')             <- max over a'

• Holds only under the Markov property; break it and the estimates converge to the value of nothing.
• Value iteration: each backup moves reward one state backward per sweep → sparse-reward, long-horizon tasks are hard (no gradient until reward propagates).

On-policy vs off-policy

• Differ in one symbol; decides data reuse:

SARSA (on-policy):      Q(s,a) += alpha·[ r + gamma·Q(s',a')      - Q(s,a) ]
Q-learning (off-policy):Q(s,a) += alpha·[ r + gamma·max_b Q(s',b) - Q(s,a) ]

• Q-learning target is rebuilt from current params → replay buffer works. SARSA needs a' written by the old policy → replay it and you learn Q^mu, a policy already abandoned.
• Off-policy does NOT fix the state-action distribution you fit under. Deadly triad = function approximation + bootstrapping + off-policy → can diverge (target fit under one distribution, evaluated under another; no contraction guarantee).
• Cliff walking: Q-learning learns the optimal cliff-edge path (greedy -13, online -41); SARSA learns the safe top row (-17, -20). If you explore in production, SARSA’s pessimism is correct.
• Trajectory importance sampling is unbiased but useless: per-step ratios multiply, spread 2^40 ≈ 1e12 at H=20, so a few trajectories carry all the weight.

Exploration (bandits)

• Regret = SUM_a Delta_a·n_a (gap × pull count). Any fixed-fraction suboptimal pulling → linear regret.
• UCB1: argmax_a [ mu_hat_a + sqrt(2·ln t / n_a) ]; bonus from inverting Hoeffding at delta = t^-4 (union bound over rounds converges to pi^2/6). Shrinks as 1/sqrt(n), grows as sqrt(ln t).
• UCB regret O(log T): arm pulled 8·ln T/Delta_a^2 times, Delta_a·n_a sums to SUM 8·ln T/Delta_a.
• Thompson: sample once from each posterior (Beta for Bernoulli), pull the highest. Exploration rate is the posterior probability the arm is best → no tuning.

• Every bound assumes stationary arms; under drift, keep the posterior wide (discount / sliding window) and buy bounded regret for the ability to track.

Policy gradients + PPO

• Log-derivative trick: grad p = p·grad log p ⇒ grad J = E[ SUM_t grad log pi(a_t|s_t) · R(tau) ] = REINFORCE.
• Model-free because transition terms in log p(tau) carry no theta and vanish from the gradient (you only sample P, never know it).
• Two free variance cuts: reward-to-go G_t (causality), and a baseline b(s). Baseline is unbiased since SUM_a grad pi(a|s) = grad(1) = 0 and b(s) factors out — so it must be action-independent → critic uses V(s), never Q(s,a).
• Un-baselined variance scales with E[G^2], not Var[G]: adding +1000 to every reward is a 121x variance regression on an unchanged MDP (a survival bonus silently kills runs).
• GAE lambda = bias-variance dial; credit-assignment horizon 1/(1-gamma·lambda) ≈ 16.8 steps at 0.99/0.95 (vs 100-step reward horizon).
• PPO reuses data via single-step ratio r_t = pi_theta/pi_old, clipped to [1-eps, 1+eps] (eps≈0.2): L_CLIP = E[min(r·A, clip(r,1±eps)·A)]. The min makes it pessimistic — kills the gradient only after the update overshot in the advantage’s direction, never on the way back. Without it, entropy collapses to a point mass, unrecoverable.

DQN’s three tricks

• Double DQN: online net selects (argmax_b Q_theta), target net evaluates — two noises must agree to inflate.

RLHF and DPO

• MDP mapping: state = prompt + tokens so far, action = next token, policy = the LM, reward = one scorer at completion end.
• Pipeline: pretrain → SFT → collect preferences → train reward model r_phi → PPO maximizing r_phi - beta·KL(pi_theta || pi_ref).
• Bradley-Terry RM loss: -E[ log sigmoid(r_phi(x,y_w) - r_phi(x,y_l)) ]. Reward defined only up to a per-prompt shift → normalize per prompt.
• KL leash exists because r_phi is a proxy fit on the SFT distribution (Goodhart / reward hacking): optimize past peak KL and RM score climbs monotonically while human win-rate rises then collapses. Stop early; evaluate against something the optimizer can’t see.
• DPO removes the RM and sampling loop: the RM was a reparameterization of the policy, and the intractable log Z(x) cancels in the pairwise loss. Pathology: only the margin is constrained, so log pi(y_w) and log pi(y_l) can both fall.

Bandit vs full RL

• Contextual bandit: action doesn’t change the next context → removes credit assignment, gamma, bootstrapping, deadly triad.
• LinUCB = UCB1 with a per-arm linear model; bonus sqrt(x^T A_a^-1 x) is direction-aware uncertainty.
• Off-policy evaluation works in bandits (IPS = (1/n) SUM (pi/mu)·r_i, unbiased only where mu(a|x)>0 → log propensities, keep an exploration floor); it collapses in full RL because weights multiply over the horizon (ESS in single digits).
• Use full RL only when your action changes the next state AND you can simulate it or afford to learn on real users. In ranking/ads/recsys, a bandit is the correct model, not a simplification.
• Three assumptions that break in production: Markov (partial observability), stationary P (drift), and reward-is-the-objective (hacking). A misspecified reward is sought out and amplified, not averaged away.