Reinforcement learning

On-policy methods learn the value of (and improve) the same policy used to generate behavior, so the data must come from the current policy (e.g., SARSA, PPO). Off-policy methods learn about a target policy while behaving according to a different behavior policy, enabling reuse of replay buffers and exploratory data (e.g., Q-learning, DQN, SAC). Off-policy learning is often more sample-efficient but can suffer from instability due to distribution mismatch, frequently mitigated with importance sampling, target networks, or specialized targets.

The Bellman optimality equation is Q*(s,a) = E[ r + γ max_{a'} Q*(s',a') | s,a ]. The max operator over next actions makes the equation nonlinear (non-smooth/piecewise) in Q, which is why it is solved by iterative methods like value iteration rather than a single linear solve. It encodes that the optimal value of a state-action pair equals the immediate expected reward plus the discounted value of acting optimally thereafter.

The deadly triad is the combination of (1) function approximation, (2) bootstrapping (updating estimates from other estimates), and (3) off-policy training. When all three are present, the contraction guarantees of tabular methods break down and value estimates can diverge. DQN mitigates this with a target network (slowing bootstrap target changes) and experience replay (decorrelating samples and stabilizing the data distribution).

Standard DQN overestimates Q-values because the same network is used to both select and evaluate the max action, and the max operator over noisy estimates introduces a positive bias. Double DQN decouples selection from evaluation: the online network picks the argmax action, and the target network evaluates it: y = r + γ Q_target(s', argmax_{a'} Q_online(s',a')). This reduces overestimation bias and typically improves stability and final performance.

a_star = Q_online(s2).argmax(dim=1, keepdim=True)
y = r + gamma * (1 - done) * Q_target(s2).gather(1, a_star)

The policy gradient theorem gives ∇_θ J(θ) = E_{π}[ ∇_θ log π_θ(a|s) · Q^π(s,a) ]. Subtracting a state-dependent baseline b(s) yields ∇_θ J = E[ ∇_θ log π_θ(a|s) · (Q^π(s,a) − b(s)) ], which remains unbiased because E[∇_θ log π_θ(a|s) · b(s)] = 0. A common and effective choice is the state value V^π(s), giving the advantage A(s,a) = Q(s,a) − V(s); the baseline lowers gradient variance without changing the expected gradient (the exact variance-minimizing baseline is a gradient-magnitude-weighted value, but V^π is the standard practical choice).

PPO maximizes L = E[ min(r_t(θ)·A_t, clip(r_t(θ), 1−ε, 1+ε)·A_t) ], where r_t(θ) = π_θ(a|s)/π_old(a|s) is the probability ratio. Clipping removes the incentive to move the ratio beyond [1−ε, 1+ε], implicitly limiting policy change without solving a constrained optimization each step like TRPO. This makes PPO first-order, simple to implement, and robust, trading TRPO's theoretical monotonic-improvement guarantee for practical efficiency.

ratio = torch.exp(logp - logp_old)
l1 = ratio * adv
l2 = torch.clamp(ratio, 1-eps, 1+eps) * adv
loss = -torch.min(l1, l2).mean()

GAE computes the advantage as an exponentially-weighted sum of TD residuals: A_t = Σ_{l≥0} (γλ)^l δ_{t+l}, where δ_t = r_t + γV(s_{t+1}) − V(s_t). λ=0 reduces to the one-step TD advantage (low variance, high bias), while λ=1 recovers the Monte Carlo advantage (low bias, high variance). Intermediate λ (commonly 0.95) balances the two, smoothing the advantage estimate used in actor-critic methods like PPO.

delta = r + gamma * V_next * (1-done) - V
adv = delta + gamma * lam * (1-done) * adv_next

Q-learning learns the optimal greedy policy regardless of the exploratory behavior, so it tends to walk the optimal but risky edge of the cliff and falls more during ε-greedy exploration. SARSA is on-policy: its TD target r + γQ(s',a') uses the actually-chosen (possibly exploratory) next action, so it accounts for the cost of exploration and learns a safer path away from the cliff. Thus SARSA yields higher online returns during learning, while Q-learning converges to the optimal policy's value (and matches it as exploration is annealed).

SAC optimizes the maximum-entropy objective J = Σ_t E[ r_t + α·H(π(·|s_t)) ], adding the policy entropy H scaled by temperature α to the reward. This encourages exploration and robustness by preferring stochastic policies that maximize reward while remaining as random as possible. α can be tuned automatically by minimizing a temperature loss that drives the policy entropy toward a target H_target, making SAC sample-efficient and stable for continuous control.

DDPG learns a deterministic policy μ_θ(s) so it can apply the deterministic policy gradient ∇_θ J = E[∇_a Q(s,a)|_{a=μ(s)} · ∇_θ μ_θ(s)], which is more sample-efficient for continuous actions than stochastic-policy gradients. Because the policy is deterministic, exploration must be injected externally by adding noise to actions (originally Ornstein-Uhlenbeck, often simple Gaussian) during data collection. TD3 later improved DDPG with twin critics, delayed policy updates, and target-policy smoothing.

TD3 adds (1) Twin critics with a min over the two Q-values in the target to combat overestimation bias; (2) Delayed policy updates—updating the actor less frequently than the critics to reduce error accumulation from a poorly-estimated value function; and (3) Target policy smoothing—adding clipped noise to the target action to regularize Q and avoid exploiting sharp peaks. Together they make deterministic continuous-control learning markedly more stable than DDPG.

target_q = r + gamma * (1 - done) * torch.min(q1_t, q2_t)

Exploitation chooses the action with the highest estimated reward; exploration tries uncertain actions to improve estimates—balancing them is essential to maximize cumulative reward. UCB (Upper Confidence Bound) selects a_t = argmax_a [ Q(a) + c·sqrt(ln t / N(a)) ], adding an optimism bonus that shrinks as an arm is pulled more (N(a) grows). This 'optimism in the face of uncertainty' yields logarithmic regret, automatically exploring under-sampled arms.

a = argmax(Q + c * sqrt(log(t) / (N + 1e-8)))

Thompson Sampling maintains a posterior distribution over each action's reward (or over model parameters) and, at each step, samples one value per action from the posterior and picks the action with the highest sample. This naturally balances exploration and exploitation: actions with uncertain posteriors occasionally produce high samples and get explored, while well-estimated good actions are exploited. It is computationally simple, Bayesian, and achieves near-optimal regret in many bandit settings.

Reward shaping adds an auxiliary reward to guide learning, but arbitrary shaping can change the optimal policy. Ng et al. (1999) proved that potential-based shaping F(s,s') = γ·Φ(s') − Φ(s), for any potential function Φ, leaves the optimal policy invariant. This is because the added terms telescope over a trajectory and only shift state values by Φ, so the relative ordering of policies—and hence the optimum—is unchanged.

γ ∈ [0,1) weights future rewards: the return is Σ_t γ^t r_t. A γ near 0 makes the agent myopic, valuing immediate rewards and ignoring long-term consequences, which simplifies learning but can be short-sighted. A γ near 1 makes the agent far-sighted but increases the effective horizon, the variance of returns, and the difficulty of credit assignment and convergence; γ also bounds the value function magnitude (≈ R_max/(1−γ)).

Monte Carlo (MC) estimates values by averaging complete sampled returns, so it is unbiased but high-variance and requires episodes to terminate before updating. Temporal Difference (TD) bootstraps—updating V(s) toward r + γV(s')—so it can learn online from incomplete episodes, with lower variance but bias from using estimated successor values. TD typically learns faster in practice; n-step and TD(λ) methods interpolate between the two.

PER samples transitions with probability proportional to their TD-error magnitude (p_i ∝ |δ_i|^α), so high-error 'surprising' transitions are replayed more often, improving sample efficiency. Because this changes the sampling distribution away from uniform, it biases the expected update, which is corrected with importance-sampling weights w_i = (1/(N·P(i)))^β, with β annealed toward 1 over training. The α parameter controls how much prioritization is applied (α=0 is uniform).

p = (abs(td_error) + eps) ** alpha
w = (1.0 / (N * P)) ** beta

The dueling architecture splits the Q-network into two streams—a state-value V(s) and an advantage A(s,a)—and recombines them as Q(s,a) = V(s) + (A(s,a) − mean_a A(s,a)). The mean-subtraction (identifiability) ensures a unique decomposition. This lets the network learn which states are valuable without having to learn the effect of each action separately, which is especially helpful when many actions have similar values.

Q = V + (A - A.mean(dim=1, keepdim=True))

HER targets sparse-reward, goal-conditioned tasks where the agent rarely reaches the intended goal. It relabels failed trajectories by pretending the achieved final (or intermediate) state was the goal all along, so even unsuccessful episodes yield positive learning signal. This dramatically improves sample efficiency for manipulation/navigation problems where reward is only given upon reaching a specified goal.

Model-based RL learns (or is given) a model of the environment's transition and reward dynamics and uses it for planning or generating simulated experience (e.g., Dyna, MuZero, world models). Model-free RL learns policies/values directly from real experience without an explicit dynamics model (e.g., DQN, PPO). Model-based methods are typically far more sample-efficient but risk compounding model bias—errors in the learned model can lead the policy to exploit inaccurate predictions.

MuZero learns a representation function (observation → latent state), a dynamics function (latent + action → next latent + reward), and a prediction function (latent → policy + value). Crucially it plans in an abstract latent space and never reconstructs raw observations—it only models the quantities needed for planning (reward, value, policy). This lets it master Atari, Go, chess, and shogi without a given simulator, learning a value-equivalent model rather than a pixel-accurate one.

Credit assignment is the difficulty of determining which past actions are responsible for a delayed reward, especially over long horizons. Mechanisms that help include eligibility traces / TD(λ) (which propagate credit backward over recent states), advantage estimation and bootstrapping (which localize value contributions), and attention/transformer-based or return-decomposition methods (e.g., RUDDER) that redistribute delayed reward to causal steps. Better credit assignment reduces variance and accelerates learning in sparse, long-horizon tasks.

Actor-critic combines a policy (actor) updated by policy gradients with a learned value function (critic) that provides a low-variance estimate of expected return. REINFORCE uses full Monte Carlo returns as the gradient signal, which are unbiased but high-variance; the critic replaces these with a bootstrapped advantage A(s,a) = r + γV(s') − V(s), trading a small bias for a large variance reduction. This yields more stable, sample-efficient updates and underpins A2C/A3C, PPO, and SAC.

Offline RL learns a policy purely from a fixed, previously-collected dataset without any further environment interaction. The core challenge is distributional shift: the learned policy may query actions outside the dataset's support, where the value function extrapolates erroneously (often overoptimistically), and these errors compound through bootstrapping. Algorithms like CQL (conservatively lower-bounding Q on OOD actions) and BCQ/TD3+BC (constraining the policy to stay near the behavior data) address this.

CQL adds a regularizer that pushes down Q-values for actions not well-supported by the dataset while pushing up Q-values for in-distribution (dataset) actions, learning a conservative lower bound on the true value. This penalizes the value function from being overoptimistic about out-of-distribution actions, so the resulting greedy policy avoids exploiting extrapolation errors. The strength is controlled by a coefficient α balancing conservatism against standard Bellman error.

RLHF (Reinforcement Learning from Human Feedback) has three stages: (1) supervised fine-tuning (SFT) on demonstration data; (2) training a reward model on human preference comparisons (pairs ranked better/worse), which learns a scalar reward representing human preference; and (3) optimizing the policy (the LLM) against this reward with an RL algorithm—usually PPO—plus a KL penalty to the SFT/reference model to prevent reward hacking and degeneration. The reward model is a learned proxy for human judgments of response quality.

DPO reframes preference alignment as a direct classification-style loss on preference pairs, eliminating the need to train a separate reward model and run online RL. It uses a closed-form relationship between the optimal RLHF policy and the reward to derive a loss that directly increases the log-likelihood ratio of preferred over dispreferred responses (relative to a reference policy), with an implicit KL regularization via β. DPO is simpler, more stable, and cheaper than PPO-RLHF, though PPO can still outperform it on some tasks with online sampling.

loss = -F.logsigmoid(beta * ((logp_w - ref_logp_w) - (logp_l - ref_logp_l))).mean()

GRPO is a policy-optimization method (popularized by DeepSeek) that estimates the advantage by sampling a group of outputs per prompt and normalizing each output's reward relative to the group's mean and std, removing the need for a separate learned value/critic network. This cuts memory and compute versus PPO (no critic) while providing a stable, low-variance baseline from the group statistics. It is widely used for RL-based reasoning fine-tuning of LLMs (e.g., with verifiable/rule-based rewards).

adv = (rewards - rewards.mean()) / (rewards.std() + 1e-8)

Reward hacking occurs when an agent maximizes the given reward signal in unintended ways that diverge from the designer's true intent—e.g., an LLM producing verbose or sycophantic text that the reward model scores highly but humans dislike. In RLHF it is commonly mitigated with a KL-divergence penalty keeping the policy close to a reference model, reward-model ensembling/uncertainty penalties, periodic reward-model retraining on fresh data, and length/format normalization. Fundamentally it reflects the gap between a proxy reward and the true objective.

The KL penalty constrains the RL policy to stay close to a reference (SFT) model, balancing reward maximization against staying within the distribution of coherent, well-formed text. If the coefficient is too small, the policy drifts far from the reference, often reward-hacking and producing degenerate or off-distribution outputs; if too large, the policy barely updates and gains little from RL. It is typically tuned (or adapted dynamically) to keep KL within a target range.

V^π(s) is the expected return starting from state s and following policy π thereafter; Q^π(s,a) is the expected return from taking action a in state s and then following π. They relate via V^π(s) = Σ_a π(a|s) Q^π(s,a). The advantage A^π(s,a) = Q^π(s,a) − V^π(s) measures how much better action a is than the policy's average behavior in s, and is central to actor-critic and policy-gradient variance reduction.

Importance sampling corrects for the mismatch between the behavior policy (which generated the data) and the target policy by reweighting returns with the ratio ρ = π_target(a|s)/π_behavior(a|s). For multi-step returns, these per-step ratios multiply along the trajectory, so the product can explode or vanish—causing extremely high variance, especially over long horizons. Remedies include weighted/per-decision importance sampling, truncation/clipping (as in V-trace/Retrace), and keeping behavior and target policies close.

rho = pi_target(a, s) / pi_behavior(a, s)

A POMDP is an MDP where the agent does not directly observe the true state but receives observations that are a probabilistic function of it, so the Markov property no longer holds for raw observations. The principled solution is to maintain a belief state (posterior over states), but in deep RL the common practical approach is to aggregate history—e.g., stacking recent frames or using a recurrent network (LSTM/GRU) or a transformer over the observation sequence—to approximate a sufficient statistic of the history.