Three things separate it from supervised learning. No example carries its correct answer — only a number saying how good the chosen action turned out. Consequences are delayed, so the reward that arrives now may be owed to a decision taken far earlier. And the agent's own actions decide what data it will see next, which makes the training distribution a consequence of the policy rather than a fixed fact.

It is an assumption the field adopts, not a theorem it proves. It buys a single, comparable objective; it costs the ability to express goals that are genuinely multi-objective or lexicographic without first choosing an exchange rate between them. Later topics on reward shaping, reward misspecification and reward hacking are all consequences of taking it seriously.

Written with the convention that the agent in state s_t takes a_t and receives r_{t+1} on arriving in s_{t+1}, so a reward is always indexed by the state it arrives with. A trajectory is the unit of data for every Monte Carlo method and the object whose probability the policy-gradient theorem differentiates.

The distinction decides whether a return can be summed without discounting. An episodic task has a finite sum by construction; a continuing one does not, which is the whole reason discounting is introduced. A terminal state is conventionally absorbing with zero reward, which lets both cases share one set of equations.

Written as a tuple so that every later claim has something precise to quantify over. Finite state and action sets make tables and exact solutions possible; continuous ones do not, and the course's whole second half is the consequence.

A property of the state representation, not of the world. The same physical system is Markov under one choice of state variables and not under another — which is why dropping a variable from a gridworld's state breaks it, and why partial observability is a modelling failure rather than a different universe.

Knowing it is exactly what separates planning from learning. Dynamic programming assumes it; model-free methods refuse to; model-based methods learn an approximation of it and pay for the approximation's errors along a rollout.

Fixing one collapses an MDP into a Markov reward process, which is why a policy can be evaluated at all. Deterministic policies are a special case; stochastic ones are strictly better when the state is aliased or an opponent can exploit predictability.

The induced chain has transition matrix P^π and reward vector R^π obtained by averaging the MDP's own over the policy's action distribution. Every policy-evaluation method in the course is a method for this object, not for the MDP.

The practical reason stochastic policies are needed: a deterministic rule must choose the same action in both, and if the right actions differ it is wrong in at least one. Randomising bounds the damage. Aliasing is the same defect that partial observability formalises.

An expectation over everything random downstream — the policy's action choices and the environment's transitions. Defining it as an expectation is what makes states comparable at all, since individual returns from the same state can differ arbitrarily.

More useful than V^π for control: acting greedily on Q needs no model, while acting greedily on V requires looking one step ahead through the transition kernel. That single fact is why every model-free control method in the course learns Q rather than V.

It has mean zero under the policy, which is exactly the property that makes it a legitimate baseline-subtracted signal in policy gradients. It isolates the part of a return that the action is responsible for, discarding the part that the state alone explains.

Obtained by expanding the return one step with the law of total expectation. It turns an exponential enumeration over trajectories into a linear system in the state values, solvable in closed form as (I − γP^π)⁻¹R^π for γ < 1. Every prediction algorithm in the course is a way of solving or approximating it.

That such a policy exists at all is a theorem, not a definition — the partial order on policies is not obviously total. For a finite discounted MDP one exists and can be taken deterministic and stationary, which is why the search can be restricted to that much smaller set.

The maximum makes the system nonlinear, so the matrix solve that worked for a fixed policy no longer applies — which is precisely the gap dynamic programming fills by iterating an operator instead of inverting a matrix.

Greedy with respect to Q* is optimal. Greedy with respect to an approximate Q is not, and the loss is bounded by the value error amplified by 2γ/(1−γ) — a bound that explains why small value errors are tolerable and why the tolerance shrinks as the horizon grows.

It makes the objective linear: expected return is the occupancy-weighted average reward, up to the 1/(1−γ) factor. That linearity is what turns policy search into a linear program, what the performance-difference lemma is stated in, what adversarial imitation matches, and what constrained MDPs write their constraints over.

The dual counterpart of the Bellman equation. Where the Bellman equation propagates value backwards, the flow constraint propagates probability forwards, and the two are the primal and dual of the same linear program.

The realistic case: a camera frame, a sensor reading or a token prefix is not the state. Memoryless policies over observations can be arbitrarily bad, so a POMDP forces the agent to carry some summary of history — which every practical agent does, whether as stacked frames, a recurrent state or a context window.

It restores the Markov property exactly, turning the POMDP into an MDP over beliefs. The price is that the belief space is a continuous simplex even when the underlying state set is small, so exact solution is intractable in general and practical agents approximate the belief with a learned summary instead.

Random, because both the policy and the dynamics are. That randomness is the reason a state cannot be scored by one observed return and the reason value functions are defined as expectations. Its one-step recursion G_t = r_{t+1} + γ G_{t+1} is the seed of every Bellman equation.

It does two jobs that are worth separating. Mathematically it guarantees convergence and bounds the return by R_max/(1−γ). Behaviourally it encodes a preference for sooner over later — and where the real goal has no such preference, γ misstates it, which is the case for the average-reward formulation.

It comes straight out of the geometric series, and it is the right unit for reading every bound in the course. A 1/(1−γ)² factor in an error bound is not arbitrary — it is one horizon for the length of a trajectory and another for the number of trajectories the error propagates through.

Stripping out state and delayed consequences leaves exploration in pure form — to learn which action is best you must spend pulls on actions that may be worse. Everything the full problem adds sits on top of this; nothing about it goes away.

Its decomposition into gaps times expected pull counts is what makes analysis tractable: a strategy is judged by how many times it pulls each suboptimal arm, and the gap converts that count into a cost. Sublinear regret means the per-step loss vanishes; linear regret means it does not.

It appears twice and in opposite directions. A small gap makes an arm cheap to pull wrongly but hard to rule out, and the 1/Δ² in every pull-count bound times the Δ in the regret decomposition gives the characteristic 1/Δ dependence.

With α = 1/n it computes the exact running mean in constant memory. With α constant it becomes an exponential recency-weighted average that tracks a changing target and never fully forgets its initial value. This shape — estimate, target, step size — is reused by every learning update in the course.

The weights are a geometric sequence that never reaches zero, so a constant step size is the right choice when the target moves and the wrong one when it does not — the estimate keeps a permanent variance floor proportional to α.

The simplest strategy that explores at all, and the baseline every better one is measured against. Its exploration is undirected: it spends the same budget on an arm already known to be terrible as on one that might still be best, which is exactly why a fixed ε gives linear regret.

A trick, not a strategy: it explores only while the initial optimism survives, which is a transient whose length can be computed. It also needs a bound on the rewards, and it does nothing for a non-stationary problem where exploration is needed permanently.

The principle behind UCB and, later, behind count-based exploration bonuses in deep RL. Its self-limiting property is the point: an arm's optimistic index falls as it is pulled, so an arm that is genuinely bad stops being chosen without anyone deciding to stop.

It comes from a tail bound rather than from taste: Hoeffding plus a union bound over arms and rounds fixes how wide the interval must be for the optimism to be valid simultaneously everywhere. Shrinking it makes the algorithm greedy and can lose a good arm permanently.

It is what makes UCB's bound meaningful: the logarithm is not an artefact of the analysis, it is the truth. Read its scope carefully — it is asymptotic in the horizon and instance-dependent, so it constrains neither finite horizons nor worst-case bounds.

Exploration falls out of the posterior's width rather than from a hand-built bonus, and the probability of pulling an arm equals the posterior probability that it is best. It handles prior knowledge, batched feedback and delay more gracefully than an index rule, because a stale posterior is still a valid posterior.

The property that defines Thompson sampling, and the reason a single posterior draw is enough: the draw is the sampling mechanism, not an approximation to one.

The right model for recommendation and personalised ranking, and the exact boundary of the bandit reduction: it holds as long as the action does not change the next context. Once it does, the problem is a full MDP and the bandit guarantees stop applying.

The bonus is the Mahalanobis norm of the feature vector under the inverse design matrix, which is large exactly in directions the data has not covered. Its guarantee rests on the reward really being linear in the features — a modelling assumption, not a free lunch.

Both objective and constraint are linear in the occupancy measure, so the problem is a linear program; the optimum usually sits on the constraint boundary, which is why the optimal policy is generally stochastic rather than a switch.

The update lambda <- [lambda + eta(J_c - d)]+ replaces the guessed penalty in r - lambda c with a price the constraint itself sets. On a piecewise-affine dual the iterates oscillate; the running average converges and the deployed policy is the time-mixed one.

Its deeper reading is a POMDP whose hidden state is the parameter vector: a policy with memory trained on the randomised problem performs online system identification — early steps probe the dynamics, later steps exploit what was inferred.

Start collapsed at the nominal parameter; expand a dimension's range when success at its boundary passes a threshold. The distribution grows outward at the speed competence grows, so training signal survives and coverage eventually includes reality.

Robust to RL's bimodal return law, where a mean over five seeds averages a lottery: two lucky 950s and three failed 50s read as competence. The IQM reports the bulk — what a random run actually delivers.

Profiles expose trade-offs no scalar can: curves that cross mean neither algorithm dominates, and the answer depends on which threshold the application cares about. No crossing means the domination is real.

A Mann-Whitney-type statistic that asks the deployment question directly — what does one run deliver — rather than the mean's question of what an imaginary average run delivers. Under 0.5, the 'worse' algorithm wins the pairwise lottery.

The course's decision order, cheapest question first: each answer eliminates a family, and two of the common outcomes are that RL is the wrong tool — stateless feedback is a bandit, and a hard physical bound needs enforcement, not optimisation.

A primitive action is the degenerate option — available everywhere, terminating in one step. Options generalise actions so a planner can decide 'walk to the door' once instead of re-deciding every step; the catch is that the option was designed, and learning it is the next topic's problem.

Its Bellman equation differs from the ordinary one in exactly the discount: the successor is weighted by gamma^k for the option's random duration k, because rewards keep arriving per step while the decision waits for termination.

The data are off-policy for the consistent options, so they can learn from trajectories they never executed. The consistency check is the action-level condition importance sampling needs, which is what makes the update legitimate.

Nothing in the objective prefers long options, so the trivial hierarchy is an interior optimum. The fixes are a per-termination deliberation cost, or a feudal architecture where a slow manager's held goal cannot re-decide early.

From any one agent's view the kernel averages over the opponents' policies, so the environment moves whenever they learn — the structural reason single-agent convergence guarantees stop applying.

Existence needs mixed strategies; matching pennies shows why — every deterministic pair has a deviating player, and the only stable point is half-half mixing, computed by a one-variable linear program.

Conditioned on the joint action the environment's law is fixed, so the critic regresses a stationary target while the actors stay deployable. The non-stationarity does not vanish — it moves into the training signal.

QMIX enforces the monotonicity with non-negative mixer weights. The price is that only monotone factorisations are expressible — a genuinely non-monotonic synergy cannot be represented.

COMA's D_i asks 'did your action beat your own policy' while holding the others fixed — computable only because the centralised critic can evaluate counterfactual joint actions at training time.

The potential appears twice in the Bellman equation with opposite signs and cancels, so Q* shifts by a per-state constant and every argmax is unchanged. A shaping that is not a potential can carry a positive cycle the agent exploits forever.

N_hat = rho(1-rho')/(rho'-rho) recovers the empirical count exactly for the tabular model, so it is a true count extended to pixel states, not a proxy. It needs a learning-positive model and counts observation novelty, not relevance — the noisy TV scores as permanently novel.

The pathology that splits epistemic from aleatoric error. ICM filters it at the features (only action-predictive structure survives); RND removes it at the target (a fixed random function has no aleatoric floor). Both are ways of changing what is predicted so the bonus cannot pay noise.

The target is deterministic, so the error is entirely epistemic — a state is surprising only if unfit. The TV is fit once and dropped; the method trades ICM's action-filtering for a guarantee that no noise floor can persist.

A per-state bonus is a signal, not a memory — it cannot say 'return here later'. Archive-based exploration fixes it by keeping the frontier as a data structure: cells visited, with the best trajectory reaching each.

Valid because the dynamics ignore the goal, so the transition is real experience for any reward function that depends on g alone. Biased in stochastic environments, where conditioning on the achieved outcome keeps the lucky draws.

The simulated update is the same code path fed by the stored transition instead of the world; n moves the propagation bottleneck from environment to compute.

When a state's value moves its predecessors are enqueued; the change propagates backward along model edges at compute speed. Costs an inverse-adjacency table and only pays off when the error landscape is sparse.

Anytime — every iteration improves the root estimate. Spends compute on the reachable frontier instead of a value for every state; the rollout policy's bias is its cap.

Each node is a bandit; Kocsis-Szepesvari proved root regret is logarithmic in simulations, which is why the most-visited child is trustworthy under a finite budget.

Repairs the shortcut-maze failure by making an unvisited passage's simulated value grow until it wins; the stored reward stays honest, the planner is paid to retest.

The condition under which Monte Carlo control converges without exploring starts: GLIE pairs epsilon-softness with epsilon decaying to zero, so the policy becomes greedy in the limit while never stopping exploration early.

Ordinary IS is unbiased but its variance explodes with trajectory length; weighted IS normalises by the sum of ratios, trading a small bias for a usable variance.

It learns the value of the exploring policy, including the cost of its own exploration — which is why it takes the safe path on the cliff walk while Q-learning hugs the edge.

The leave-one-out form removes the baseline-sample correlation; it is a Monte Carlo estimate of V(s), so it needs no trained network but no per-token credit either.

The clipped surrogate is unchanged; the conventions it adds — the std divisor, the token-average, the KL placement — are where the two derived biases live.

Counters the symmetric clip's positive feedback on already-likely tokens, which is the mechanism of entropy collapse; the entropy curve is the diagnostic it flattens.

Trained on human or teacher step labels and aggregated by min/mean/product; it fixes the outcome reward's blindness to the derivation but reintroduces a learned boundary the policy can probe.

A hard-threshold approximation of the tilted optimum pi_ref * e^(beta R): it bootstraps the policy toward its own successes and plateaus at best-of-k, which is why an optimiser follows it.

Four attack surfaces: simulator physics, learned-reward format, test coverage, rater sycophancy. Countermeasures bound (KL), detect (held-out, spot checks), or shrink (adversarial tests) — none removes the gap.

Crediting the policy for tool outputs would teach it to produce what it does not control; the mask is the whole gradient correctness of multi-turn RL.

First-visit treats each episode as one sample per state; every-visit reuses repeats. On blackjack the two coincide because states cannot repeat; on loopy tasks they diverge.

Positive δ means the step went better than the estimate said. It is a biased estimator of the Bellman error whose fixed point is V^π.

The source of TD's bias and its speed: it does not wait for outcomes, but it writes the current estimates' errors into itself. MC is unbiased at the price of episode-length variance.

On finite data this is the optimum TD reaches and MC misses: TD exploits the Markov structure to reuse every transition, MC fits the returns without assuming it.

Interpolates between TD(0) (n=1, biased but low-variance) and Monte Carlo (n=infinity, unbiased but high-variance); the best n is empirical, not derivable.

Equivalent in expectation to weighting every n-step target; implementable online only through eligibility traces, which is why the two objects are taught as one.

The online mechanism that produces the lambda-return update: accumulate traces, apply the TD error to all of them at once. Dutch traces fix the accumulating trace's overcounting.

No importance ratios needed — the max is over the action set, not over the sampled action. Converges to Q* under Robbins-Monro step sizes plus every pair visited infinitely often (Watkins-Dayan).

Lower variance than SARSA's sampled target, so a larger step size works; reduces to Q-learning exactly when the target policy is greedy.

Shift-invariant — only reward differences are identified, which is why the DPO partition function cancels rather than needing to be computed.

Accurate only near the distribution it trained on — the overoptimisation curve is the measured version of that limit.

InstructGPT's pipeline: the reward is per-token -beta log(pi/pi_ref) plus the model score at the end token.

Gao-Schulman-Hilton's fitted laws: d(alpha - beta log d) for RL, d(alpha - beta d) for best-of-n; the peak moves with proxy data and size, never vanishes.

Only the log-ratio to pi_ref is supervised, so both completions' likelihoods can fall while the margin rises; off-policy by construction.

The middle ground between frozen offline pairs and per-step online labelling; per-round cost is 2K generations + K labels.

With fewer parameters than states the true values are unreachable — minimising the weighted error is what generalisation means here.

Convex objectives, one optimum for gradient Monte Carlo; linearity is what makes the theory tight and the features decisive.

Resolution comes from tile width, generalisation from the number of tilings; the standard recipe for linear methods on continuous state spaces.

Cost-blind and distribution-blind: errors are unweighted by consequence, and the fit is certified only under the expert's state distribution.

The union bound 1-(1-eps)^t summed over the horizon gives the square; the bound is tight, and only training on the learner's own occupancy removes it.

Trains under the learner's own state distribution and recovers O(epsilon H); costs a queryable expert and executing imperfect policies.

Ill-posed — R=0 always fits and potential shaping preserves the optimal policy; feature matching w^T mu(pi*) >= w^T mu(pi) is the usable form.

ML gradient is demonstrated minus expected feature counts — and the expectation needs a soft-optimality solve per gradient step.

Trades IRL's inner solve for an ordinary RL run against a moving discriminator — tractable, unstable, and produces no inspectable reward.

The TD target r + γv(s′,w) itself depends on w. A semi-gradient update differentiates only the prediction and treats the target as fixed. The fix works on-policy (a contraction argument gives convergence) but fails under off-policy sampling, function approximation and bootstrapping together — the deadly triad — where divergence is possible.

Plain Q-learning lets one estimate both choose and score the next action, so max-over-estimates overshoots max-over-truth. Keeping Q1 and Q2 and alternating which selects and which evaluates makes the estimator unbiased in the iid case and cuts maximisation bias sharply in practice; the same trick applies to Sarsa and Expected Sarsa.

Every offline method is bounded by it: values queried outside support extrapolate and inflate (the bootstrapping failure); constraints forbid leaving it; pessimism penalises it; return-conditioning silently answers beyond it. Coverage quality — which good actions appear — sets the achievable ceiling.

Appears as √C in FQE’s γ/(1−γ)² error bound and in IS variance: where the candidate asks about actions the log lacks, C explodes and the guarantee is vacuous. It is the same diagnostic ESS measures for importance sampling.

\hat V + ρ(r + γ\hat V′ − \hat Q): the correction has zero mean under a correct model and telescopes to unbiasedness under correct ratios. Variance scales with the residual, not the return — the control-variate gain over plain IS.

IQL’s soft argmax over the data’s support: fit V to the τ-expectile of observed targets r+γV(s′), never querying an unseen action. The τ→1 limit is the best logged continuation, not the best action.

The sigma->0 limit of the stochastic gradient; the score estimator's variance explodes as the policy sharpens (1/sigma^2 amplification), which is what the deterministic form avoids. Requires off-policy data because a deterministic actor cannot explore.

Smooths the bootstrap target the way periodic hard copies cannot — the lag damps the chase-the-target oscillation instead of jumping it. Used on both actor and critic in DDPG/TD3/SAC.

Derived by Lagrange multipliers from max E[Q] + alpha*H. alpha->0 recovers greedy; the partition function Z is what makes it intractable in continuous spaces, forcing SAC's KL-projection approximation.

SAC uses a = tanh(mu_theta + sigma_theta * eps), eps ~ N(0,I): pathwise gradients with far less variance than score-function estimates. The tanh squash needs the log-determinant correction log pi(a) = log N(u) - sum log(1 - tanh^2 u).

Total variance = mean of member variances + variance of member means. Only the second shrinks with data — and only it warns a planner it has left the training support, because a single head’s confidence is itself untrustworthy off-distribution.

MBPO’s whole trick: the real buffer anchors every synthetic transition. The bound trades a model-bias term growing in k against a coverage term shrinking as gamma^k, so optimal k is 1–5 whenever the model is imperfect.

The P factor is what distinguishes it from plain UCT: the network concentrates simulations on moves a strong player would consider. Value backups flip sign at each edge under the player-to-move convention.

MuZero’s defining choice: the latent is a sufficient statistic for search targets, so it can be an uninspectable planning summary rather than a world rendering. Costs: opacity and reward-dependence — no reuse under a changed objective.

Features proportional to the score make the fitted advantage “compatible”: the natural gradient equals the true policy gradient regardless of approximation error. It is why a state-value baseline is safe and an action-dependent one needs care.

lambda=0 is the one-step TD advantage (low variance, biased toward the critic); lambda=1 is the Monte Carlo advantage (unbiased, high variance). lambda is set by how much the critic can be trusted, independently of gamma's discounting role.

F^-1 nabla J makes the update invariant to parameterisation and approximately KL-bounded. TRPO is its constrained form; a Gauss–Newton-style solver makes it practical at network scale.

The new policy's return gain equals its own occupancy's expectation of the old advantage. Surrogate objectives replace d^pi' by d^pi and bound the discrepancy — TRPO's trust region is the price of that swap.

The log-derivative trick: E[f nabla log pi] estimates nabla E[f] without differentiating the environment. For softmax policies it is the feature vector minus its policy-weighted mean; for Gaussian, (a-mu)/sigma^2 times the state features.

The return scales the whole episode’s score sum; subtracting a learned value baseline keeps the estimator unbiased while cutting orders of magnitude of variance — the step every modern actor–critic descends from.

The stationary occupancy d^pi carries the state weighting, so the theorem lets a Monte Carlo critic stand in for everything the model would have supplied. It is the foundation beneath REINFORCE, actor–critic, TRPO and the deterministic variant alike.

TRPO’s max L(theta) s.t. mean-KL <= delta: the theory pays a quadratic penalty for monotonic improvement; the practice solves a linear-quadratic model by conjugate gradient with Fisher-vector products and a backtracking line search.

The clip removes the incentive to move the probability ratio beyond the bracket: improvement is free inside it, flat outside. Empirically matches TRPO-class performance at a fraction of the machinery — which is why it became the default.

In most states every action is near-equivalent, so separate V learning is the sample-efficient path. Mean subtraction beats max subtraction in training despite being less principled — the mean is what E_pi[A]=0 actually imposes.

W_p(u,v) = (int_0^1 |F_u^-1(t) - F_v^-1(t)|^p dt)^(1/p); it scales as W_p(gU,gV)=gW_p(U,V), giving the gamma-contraction the tabular proof needs. The same operator provably does not contract in KL or total variation.

The contraction proof lives in Wasserstein but the training loss is cross-entropy — the gap between metric of proof and metric of optimisation is the method's honest caveat. Distribution knowledge buys risk sensitivity and richer learning signal.

The 2017 headline: component fixes are composable because each addresses a different failure (overestimate, prioritisation, state-vs-advantage, return variance, credit window, exploration). The ablation — each removal hurts — is the evidence for composing rather than choosing.

Feedback that names the correct output is supervised learning and should stay there. Evaluative feedback whose actions do not change the future state is a bandit, which is far cheaper to solve. Reinforcement learning earns its cost only when both conditions hold.

Test a candidate representation by asking whether two histories leading to the same state can have different futures. If they can, a variable is missing, and every convergence result in the course stops applying. Adding history — stacked frames, a recurrent summary, a context window — is the standard repair.

For a fully observed finite MDP a deterministic stationary optimal policy exists, so randomness buys nothing at the optimum. Under aliasing or against an adversary the best deterministic policy can be strictly worse than a stochastic one, and the gap is computable.

Acting greedily on V requires looking one step ahead through the transition kernel, which a model-free agent cannot do. Q removes that requirement at the cost of a table or network |A| times larger. Actor–critic methods take the third route: learn V and let a separate policy choose.

The closed form (I − γP^π)⁻¹R^π is exact and costs O(|S|³), which is fine for a few hundred states and hopeless beyond. It also evaluates one policy rather than finding a good one: the optimality equations are nonlinear, so they admit no such solve at all.

A uniformly small value error does not give a uniformly small policy loss — the horizon multiplies it. At γ = 0.99 a value error of 0.1 permits a policy loss near 20, so 'the values look close' is not evidence the policy is.

Constraints phrased over trajectories or over value functions are awkward; the same constraint over d^π is linear, which is what makes constrained policy search a linear program and what lets the performance-difference lemma be stated at all.

Exact belief-state filtering restores the Markov property but lives on a continuous simplex and is intractable in general. Practical agents approximate the belief with a fixed-length summary: a frame stack, a recurrent hidden state, or the whole token prefix.

A γ too small makes long-horizon credit invisible, and the agent optimises a different problem from the one intended. A γ near one lengthens the horizon but inflates variance and slows every bound's constant. Where the real objective has no time preference at all, say so and consider the average-reward formulation rather than pushing γ towards one.

A bandit has provable logarithmic regret and no credit-assignment problem. Check the assumption honestly: if today's recommendation changes tomorrow's user, the reduction is invalid and the bandit's guarantee does not transfer.

The sample average is the efficient estimator for a stationary arm and converges; a constant step size never converges but tracks. Picking a constant for a stationary problem buys a permanent variance floor for nothing.

ε-greedy is worth keeping only for its simplicity, or where a fixed exploration rate is itself desirable. Optimism and posterior sampling both concentrate exploration on arms that could still be best, which is what turns linear regret into logarithmic.

Under delay an index rule commits the whole batch to one arm, because nothing in its input has changed. Posterior sampling keeps drawing different worlds, so the batch spreads itself across arms without any special handling.

An informative prior is worth real regret when the horizon is short. The flip side is that a badly wrong prior is also taken seriously, so state what the prior encodes rather than reaching for a conjugate default.

A per-context independent bandit wastes every observation on one context. A linear model shares evidence across contexts, at the price of an assumption that must be checked: if the reward is not linear in the features, the confidence ellipsoid is not a confidence set.

A fixed penalty is a price nobody knows: too cheap and the agent pays it whenever profitable, too dear and it refuses earned reward, and at the exact price the objective is flat across compliant and violating policies. Only feedback on the violation resolves the knife-edge. If the bound must hold per episode — never once — it is not a CMDP at all but a shield outside the objective.

Choose the ranges to cover reality but stay inside the action envelope; widen them with a boundary-proven curriculum (ADR) rather than hand-setting. The alternative is system identification when few parameters are wrong and some real data exists — identify to tighten the ranges, then randomise what remains.

RL returns are bimodal, so a small-sample mean averages a lottery and its confidence interval is wider than the gap it reports. The rliable toolkit answers the question a deployment asks — what one run delivers — and printing the interval is the minimum viable fix.

The two commonest rejections: stateless feedback (a bandit, not an MDP) and supervision masquerading as RL. A hard physical bound is also a rejection — an invariant to enforce, not an objective to optimise.

A goal separated from the start by twenty-two primitive backups is nearly invisible at gamma=0.9; the same reward through four option-level backups is reachable. If the macro-actions are hand-designable, use the SMDP equations directly; if they must be learned, add a deliberation cost or a feudal timescale so the hierarchy does not collapse to primitives.

The collapse is the optimum of the stated objective: nothing pays for duration. A per-termination penalty shifts the stopping threshold so options persist; a feudal architecture prevents the manager from re-deciding at all. Choose the cost when flexibility matters and a hyperparameter is acceptable; the feudal wall when the abstraction must be structural.

Zero-sum gives a clean minimax value and minimax-Q to reach it; general-sum gives equilibria with possibly different values and no canonical 'the value'. If independent Q-learners are cycling, the fix is rarely more samples — it is a formalism that names the moving target.

The asymmetry is the method — the critic is thrown away at execution so its privileged view never leaks into the policy. It fails only when no training-time joint state exists to exploit, e.g. logged partial observations.

Shaping is safe only in the form gamma*Phi(s')-Phi(s); anything else can carry a cycle the agent exploits. If no Phi exists, pseudo-counts generalise UCB's optimism, prediction-error bonuses pay for learnable ignorance (filter it with ICM or RND to survive the noisy TV), and Go-Explore's archive keeps the frontier when the agent must return to a distant one.

ICM learns features that keep only what the agent's actions influence — the noise predicts no action and is dropped. RND predicts a fixed random target — deterministic, so there is no noise floor. Pick ICM when the controllable structure matters; RND when you want the simplest novelty signal that cannot be gamed by a TV.

Valid because dynamics do not depend on the goal; biased on stochastic tasks where conditioning on the achieved outcome keeps the lucky draws. If the goal is not expressible in the state, or the goal changes the physics, the trick does not apply.

Episodes-to-solve on a maze drop an order of magnitude at n=50. The model is tabular and only knows visited transitions — add Dyna-Q+'s staleness bonus when the world might change, and prioritised sweeping when most of the model is already stable.

The budget concentrates on the reachable frontier. The rollout policy caps accuracy; replacing it with a learned prior is the AlphaZero step.

On the cliff walk, SARSA's higher per-episode return under epsilon-greedy is the honest comparison: it prices its own exploration. Q-learning's learned values are optimal for the deterministic policy it will never exactly follow.

RLVR works where a checker exists — maths, code, formal domains. Its own failure modes are enumerable (equivalence, coverage), not a continuous exploit surface. Where no checker exists, bound the learned reward with KL and audit with held-out graders.

The symmetric clip gains epsilon of a large probability but only epsilon of a near-zero one — a positive feedback that sharpens the policy until groups agree and the gradient vanishes. Watch the group-advantage zero-rate, not just reward.

Verifiable+sample: GRPO (filtered SFT as cold start). Non-verifiable+sample: PPO-RLHF. No sampling: DPO on preferences. Demonstrations only: SFT. Distance-to-target and reward quality refine within the branch.

The price is a biased target and a Markov assumption. Choose Monte Carlo only when the task is Markov-violating or returns are cheap and unbiased estimates matter more than speed.