Reinforcement Learning

Decide once what counts as the state, and make it a state that renders the past irrelevant — everything you need to know about history is in the current description. Then the value of a situation decomposes: what you get now, plus the discounted value of wherever you land. That recursion is the whole idea, and it is the reason a problem spanning a thousand steps can be attacked one step at a time. What makes it more than a tautology is the discount. Because a future reward is worth strictly less than a present one, the one-step backup shrinks disagreements between any two guesses by a constant factor, so repeating it drives every starting point to the same answer. Existence, uniqueness and a convergence rate all fall out of that single fact. The cost is stated equally simply: the whole structure rests on the state being genuinely Markov, and when it is not, the equations still have a fixed point — just not the one anybody wanted, and nothing in the arithmetic says so.

Two loops that chase each other. One asks "given how I currently act, what is each state worth?", the other asks "given those values, is there a better action anywhere?". Improve the policy and the old values are stale; re-evaluate and the policy may no longer be greedy. Run them against each other and they converge to the pair that is consistent — the optimal policy and its value function. The interesting part is how much evaluation to do before improving again. Solve it exactly every time and you have policy iteration, which takes very few rounds and pays heavily for each. Do a single backup and improve immediately and you have value iteration, which takes many cheap rounds. They are the two ends of one dial, the answer is identical, and which end is cheaper depends almost entirely on the discount — a fact that decides real runtimes and is almost never checked before a solver is written.

Play the episode to the end, add up what you actually received, and use that as the value of every state-action pair you passed through. Average over enough episodes and the averages converge on the truth, because they are averages of exactly the thing being estimated. Two consequences follow and they are both unusual. The estimate is unbiased and it never assumes the state is Markov — it does not predict the future from the current state, it measures the future that occurred, so a state representation that hides something still produces correct values for the process as experienced. Nothing else in this category can say that. The costs are equally plain. You learn nothing until the episode terminates, which rules out continuing tasks entirely, and the return of a long episode is the sum of many random quantities, so the variance is large and shrinks only as the square root of the episode count. The subject that actually dominates any implementation, though, is neither: it is that a greedy policy visits a vanishing fraction of the state-action pairs, so most of the table is never estimated at all and the improvement step chooses between numbers that were never measured.

Monte Carlo waits for the episode to finish and averages what happened. Temporal-difference learning refuses to wait: it takes one step, sees the reward, looks at its own estimate of where it landed, and updates toward that. The target is therefore partly made up — it contains the very quantity being learned — and the whole method is an argument that this is a good trade. It is. Substituting an estimate for the remaining trajectory removes almost all of the variance, because a single reward plus one value lookup is far less random than a sum over a hundred future steps, and the resulting method learns online, from incomplete episodes, in tasks that never terminate. What it buys with is bias and an assumption. The bias is real and does not vanish with data — a wrong value at the next state propagates backwards into this one. The assumption is that the state is Markov, because bootstrapping trusts the next state's estimate to summarize everything after it; where Monte Carlo is simply indifferent to state aliasing, this converges confidently to the wrong answer. Lambda is the dial between the two extremes, and the best setting is almost always in the middle.

Q-learning asks "what would this be worth if I acted optimally from here?" and answers a question about a policy nobody is following, because the agent is still exploring. SARSA asks the question the agent can actually act on: "what is this worth given that I will keep behaving the way I am behaving, mistakes included?" The change is one symbol in the update — the next action is the one that will be taken rather than the best available — and the consequence is a genuinely different value function. An agent learning under SARSA discovers that standing next to a cliff is dangerous, because sometimes it does fall off, and it routes around the edge. Q-learning learns the shortest path along the edge and then keeps falling off it, because the values it learned assume an optimality its own exploration contradicts. Neither is wrong: SARSA is correct about the policy being run and Q-learning is correct about a policy that would be run if exploration stopped. Which one you want depends on whether exploration is free, and the answer to that is usually no.

Keep a table of "how good is taking action a in state s", then wander the environment updating each entry toward the reward you just got plus the best value you think is available from wherever you landed. The bootstrapping is the whole trick: you never wait to see how the episode ends, you update toward your own current estimate of the future. Do that enough times and the estimates converge on the truth — and acting greedily on them is the optimal policy.

Tabular Q-learning stores one number per state-action pair, which means it cannot play a game whose screen has more configurations than there are atoms in anything. Replace the table with a network that maps a state to a vector of action values and the method generalizes: states that look alike get similar values without being visited separately. That substitution is the entire idea, and it breaks the convergence proof immediately. The proof relied on each update touching exactly one cell; a network update moves every state at once, including the state the target was just computed from, so the agent is chasing a target that moves because it moved. DQN makes this work with two blunt interventions. Experience goes into a large replay buffer and minibatches are drawn from it at random, which breaks the temporal correlation that makes consecutive samples nearly identical. And the target is computed from a separate copy of the network that is frozen for thousands of steps, which stops the target from moving every time the estimate does. Neither is a fix. They convert a method that reliably diverges into one that usually does not, and the residual failure is not an error message — it is a Q-value curve that climbs smoothly to a thousand while the agent gets worse. The right time to reach for DQN is when actions are discrete, a simulator can supply tens of millions of transitions, and a policy-gradient method is not a better fit. That is a narrower set of conditions than its fame suggests.

Every value-based method so far has produced a policy as a by-product: learn the values, take the argmax. That works until the action space is continuous or combinatorial, at which point the argmax itself becomes an optimization problem you cannot afford to solve at every step. REINFORCE takes the other route and parameterizes the policy directly, then asks how to improve it. The obstacle is that expected return is an expectation over trajectories the policy itself generates, so changing the parameters changes the distribution being averaged over, and there is no obvious way to differentiate through that. The score-function identity resolves it in one line: the gradient of an expectation over a parameterized distribution equals the expectation of the outcome times the gradient of the log-density. Both sides are expectations you can sample. So the algorithm is embarrassingly simple — run an episode, compute the return, and take a gradient step that makes every action taken more likely in proportion to how good the return was. Good episodes get reinforced, bad ones get suppressed, and nothing needs to be known about the environment. What you pay for that generality is variance. The estimator is unbiased and it is also so noisy that the raw form is essentially unusable on anything real, which is why every practical policy-gradient method is REINFORCE plus a stack of variance reductions. The failure mode is distinctive too: with no exploration mechanism outside the policy itself, a policy that becomes deterministic early has no way back, because the gradient for an action it never takes is never sampled.

REINFORCE weights each action by the return that actually followed it, which is unbiased and enormously noisy, because a single sampled return over a long horizon is dominated by everything that happened to occur afterwards. The fix is already visible in the theory: any function of state can be subtracted for free, and the best one is the state's own value. Learn that function and two things happen at once. The subtraction removes the part of the return that was predictable from the state, leaving only the part attributable to the action — which is the definition of an advantage. And once a value function exists, the sampled return can be replaced entirely by a bootstrapped estimate, so an update no longer has to wait for the episode to end. What you gain is a dial. Bootstrap after one step and variance nearly vanishes while bias is whatever the critic's error is; bootstrap after the whole episode and you are back to REINFORCE. Generalized advantage estimation makes that dial continuous, and choosing where to set it is the central tuning decision of the method. What you pay is a second learning problem coupled to the first. The critic supplies the actor's training signal, the actor determines the distribution the critic is fitted on, and neither is right at the start. An actor that improves faster than its critic is optimizing against systematically wrong advantages, which is the characteristic failure and the reason relative learning rates matter more here than anywhere else in this category.

Every policy-gradient method so far has a hidden problem: the optimizer controls its own training distribution. A step that is too large produces a worse policy, the worse policy collects worse data, and the next gradient is computed from it — so unlike supervised learning, where a bad step costs one update, here a bad step can end the run. Worse, a learning rate does not control what actually matters. It bounds movement in parameter space, and what needs bounding is movement in policy space, and the relationship between the two is the curvature of the policy manifold, which varies by orders of magnitude across the same network. TRPO fixes this directly: maximize the usual surrogate subject to a hard constraint that the new policy stay within a KL ball of the old one. That is a constrained optimization with a genuine monotonic-improvement result behind it, and it requires the Fisher information matrix, conjugate gradients, and a backtracking line search — correct, and painful enough that most people did not use it. PPO makes the same bargain with a much cruder instrument. Write the surrogate in terms of the probability ratio between the new and old policies, and clip that ratio: once the ratio leaves a small interval, the objective becomes flat and the gradient vanishes, so there is no incentive to move further. No second derivatives, no line search, plain Adam. The clip is not a real trust region and does not actually bound the KL, but it removes the pull toward large steps, and that turns out to be enough — enough that several epochs can be taken over the same batch, which is the actual source of the efficiency gain and the reason PPO became the default.

DQN derives its policy from an argmax over the action values, which requires enumerating the actions. For a continuous action space that is not merely expensive, it does not exist. The deterministic policy gradient resolves this with a substitution that is obvious in hindsight: if the argmax cannot be computed, train a network to approximate it. So there are two networks — a critic Q(s, a) fitted by the usual Bellman regression, and an actor that outputs a single action and is trained to maximize the critic's output at that action. The actor's gradient is the critic's gradient with respect to the action, chained back through the actor, which means the critic must be differentiable in the action and the actor is climbing a surface the critic defines. That last clause is the whole story of this method's difficulty. The actor is an optimizer pointed at a learned function, and a learned function has errors — sharp spurious peaks in regions where little data exists. The actor will find them, because finding maxima is exactly its job, and it will then take the action at the peak, collect data showing the peak is not real, and the critic will correct it while the actor moves to the next one. DDPG does this and is famously brittle. TD3 adds three targeted countermeasures: two critics with the smaller value taken, so overestimation is replaced by deliberate pessimism; delayed actor updates, so the actor climbs a critic that has had time to settle; and noise added to the target action, which smooths the surface so a spike one action-width wide cannot be exploited. None of the three is clever. All three are aimed at the same failure.

Every method so far has treated exploration as something bolted on — an epsilon, a noise scale, an entropy bonus tuned until the run stops collapsing. SAC changes the objective instead: maximize return plus the entropy of the policy, weighted by a temperature. The agent is now paid to remain uncertain, and that single change does a surprising amount of work. Exploration is no longer a schedule to tune, because a policy that narrows onto one action loses entropy and therefore loses objective value; the exploration is whatever the return-versus-uncertainty trade says it should be, state by state. The value function changes shape too. The max over actions in the Bellman equation becomes a log-sum-exp — a soft maximum — so a state with several near-equally-good actions is worth more than a state with one, which is a genuinely different and often better notion of value. And because the policy is stochastic, the actor can be trained by reparameterizing the sample rather than by a score-function estimator, which means the gradient flows through the sampled action into the critic and carries far less variance than REINFORCE-style estimation. What remains from TD3 is the pessimism: two critics with the minimum taken, because an actor is still an optimizer pointed at a learned surface. What goes away is the target actor, the exploration noise schedule, and most of the brittleness. The temperature is the one new knob, and it is usually tuned automatically against a target entropy, which is why SAC in practice has fewer things to get wrong than anything else in this branch.

Everything else in this category spends its effort on credit assignment across time. A bandit has no time to assign across — you pick an arm, you get a reward, and the next decision starts from the same place. What is left when the temporal structure is gone is the exploration-exploitation trade in its purest form: you can only learn about an arm by pulling it, and every pull spent learning is a pull not spent earning. Three answers matter. Epsilon-greedy explores at random with some probability, which is simple and wasteful, because it explores arms it already knows are bad just as often as promising ones. UCB is optimistic in the face of uncertainty: score each arm by its estimated mean plus a confidence bonus that shrinks as it is pulled, then take the best score. An arm that looks bad but has barely been tried keeps a high bonus and gets tried again; an arm that has been tried and is genuinely bad falls away. Thompson sampling is Bayesian and even simpler to state: keep a posterior over each arm's value, draw one sample from each, play the argmax of the samples. Arms the posterior is uncertain about sometimes draw high and get played, in exact proportion to the probability they are best. What makes this group worth studying is that it is the only one here with meaningful theory — regret bounds that hold, are tight, and are actually predictive of behaviour — and simultaneously the group that appears most often in production, usually in contextual form. It is also the group most often reached for wrongly, because the assumption it rests on, that actions do not change the state, fails quietly rather than loudly.

Every method so far has learned what to do without ever learning what happens. A transition gives a model-free agent one scalar of information — the reward — and it throws away the rest, which is the next state, a full observation of how the world responded. Model-based methods keep it. Fit a dynamics model that predicts the next state from the current state and action, and suddenly each interaction is a complete supervised example, which is why this branch routinely learns from one or two orders of magnitude fewer interactions than a model-free one. Once a model exists there are two things to do with it. Plan with it: search over action sequences by rolling them out in imagination, pick the best one, execute only its first action, then throw the rest away and replan from the new state. That last part sounds wasteful and is the entire mechanism — replanning every step means model error never gets a chance to accumulate, and it is why model predictive control is deployed across process industries where no other optimal-control method is. Or generate with it: use the model to synthesize experience and train an ordinary model-free agent on the mix, which is Dyna and its descendants. The catch is the one that keeps recurring in this category. A planner searching for the best action sequence under a learned model is an optimizer pointed at a learned function, and it will find the places where the model is wrong and optimistic — except here the errors compound step by step down the rollout, so a model that is slightly wrong per step can be arbitrarily wrong at horizon twenty. Every serious technique in this area is a response to that.

If an expert already solves the task, the obvious move is to record what they do and fit a model that maps states to their actions. That is behavioural cloning, it is ordinary supervised learning with no reward and no exploration, and it works far more often than the theory suggests it should — which is exactly why the way it fails is worth understanding precisely. The failure is not that the model is inaccurate. It is that the model is evaluated somewhere it was never trained. The demonstrations cover the states an expert visits, and an expert who is good rarely visits bad states, so there is almost no data about how to recover from a mistake. The moment the learner makes a small error it is slightly off the expert's distribution, where its predictions are slightly worse, which produces a slightly larger error, and the drift compounds. The cost of this is not linear in the episode length but quadratic, which is the formal statement of "a small imitation error becomes a large behavioural one". DAgger fixes it by changing what is labelled rather than how it is fitted: run the learner, collect the states IT visits, ask the expert what they would have done there, add those to the dataset, and repeat. Now the training distribution converges toward the one the policy is actually evaluated on, and the error becomes linear again. The catch is in the requirement — an expert who can be queried on arbitrary states, interactively, which is exactly what you usually do not have. Most of the field is about what to do when you only have a fixed set of demonstrations.