Learning values from experience

A machine has one switch. Leaving it on pays 1 every minute and changes nothing; switching it off pays 0 and stops the machine. That is a task with one state and two actions, stay and leave. With γ = 0.5, staying forever is worth 1 + 0.5 + 0.25 + ··· = 2, which beats leaving.

If you know these rules you can compute the answer with arithmetic, and if you do not you must act and watch what happens. The question this section answers is how to find the best policy in each case. The answer has two halves: sweeps when the world is known, and sampled updates when it is not. A sweep is one pass over the states, updating each value once. !Both updates aim at the same target: the reward plus gamma times the value of the next state. The left averages that target over every next state, which needs a model. The right uses the one state the agent reached, which needs only experience; alpha sets how far the estimate moves toward it. The figure is schematic. Status: schematic.

A model is a rule that says which next state and reward follow each state and action [S:83:96]. With a model the problem becomes a computation over a table, and without one the table must be filled from experience. !Staying pays 1 at every step, so at gamma = 0.5 the state is worth 2. A sweep of the Bellman equation lands at 1, then 1.5, then 1.75; a TD update with alpha = 0.5 climbs from 0.5 to 0.875 and on. Both approach 2, one by arithmetic over a known model and one from sampled steps. The figure is synthetic: both series are computed from the plan's one-state example. Status: synthetic.

Start with the one-state task above and a guess of 0. Policy evaluation asks what staying forever is worth under the current policy: sweep the Bellman equation and the guess climbs 0, 1, 1.5, 1.75 [S:83:96]. Policy improvement then asks whether leaving beats staying at that value; it does not, because leaving pays 0, so the policy is already optimal [S:83:100]. Repeating the pair is policy iteration, which reaches an optimal policy in a finite number of rounds for a finite problem [S:83:102]. Dynamic programming is the name for this whole family of sweeps over a known model [S:83:96].

Value iteration folds the two steps into one sweep [S:83:105], in which each state takes the best action, adds the reward, and borrows the discounted value of the next state. The table starts arbitrary and is overwritten until the changes are small enough. Small enough means below a threshold you choose; the next layer turns that threshold into a bound on the error.

The improvement step cannot make the policy worse; that is the policy improvement theorem [S:83:100], which is the reason the loop is safe: each round either improves the policy or proves it already optimal.

Worked example. Start the value at 0. Sweep one gives 1, because stay pays 1 and the next value is still 0. Sweep two gives 1.5, sweep three 1.75, and sweep four 1.875. The sequence approaches 2, the value of staying forever, and the computation uses only the model and the current table, with no experience needed.

Without a model, the agent replaces the expected next value with one sampled next state, which is temporal-difference learning, and the simplest rule is TD(0) [S:83:142]. The zero means the update looks one step ahead and no further. The bracket in the update is the TD error: the gap between the old estimate and a better one-step estimate [S:83:143]. We write the value estimate as V and the step size as α.

That line says move the old value a fraction α of the way toward the one-step target. The arrow means "becomes": the new value replaces the old one. The target is the reward plus the discounted value of where you actually landed.

Now hide the model and start again with V = 0, α = 0.5, and γ = 0.5. Take stay, receive 1, and land in the same state. The target is 1 + 0.5×0 = 1, so the new value is 0 + 0.5×1 = 0.5. A second identical step gives target 1 + 0.5×0.5 = 1.25, so the value becomes 0.875, and experience moves the estimate toward 2 without ever using the model.

Q-learning applies the same rule to action values and takes the maximum over the next actions [S:83:153]. The Q is the conventional name for the action value and carries no further meaning. It can learn the best policy while following an exploratory one, because the update does not depend on the action the agent will actually take next.

A model-free agent must still try every action in every state, or those values never improve. That is exploration again, now inside the value update; a model removes the need to visit, because it can compute the expectation without acting.

Think of learning to bake: a recipe lets you compute the cake before touching an oven; experience lets you bake, taste, and adjust. The comparison breaks because a recipe can be followed once, while experience needs many attempts before the estimates settle.

The price can be steep: Q-learning takes a maximum over noisy estimates, which tends to overestimate the best action's value [S:83:156]. Without a model, every state-action pair must be visited often enough, and a table with one row per pair is too large to fill for images or robot positions. Function approximation replaces the table with a parametric function, and a convergence guarantee is a proof that the updates reach the right values; the clean guarantees do not survive unchanged [S:83:146].

The formal statement. Policy evaluation iterates the Bellman expectation equation over the table [S:83:96]. Value iteration replaces the average over actions by a maximum [S:83:105]. TD(0) replaces the expectation by one sampled transition, moving the current value a fraction $\alpha$ of the way toward a one-step target [S:83:142]. Q-learning applies the same rule to action values and bootstraps from the best next action [S:83:153]. The step size $\alpha$ lies between zero and one.

The derivation. Treat the right-hand side of the Bellman equation as an operator on value tables. For any two tables, the largest absolute change the operator can produce is at most the discount times the largest difference between the tables [S:82:57-58]. So the operator is a contraction with modulus equal to the discount, and it has one fixed point, reached from any starting table [S:82:54-56]. TD(0) is the sampled version. Conditional on the current state, the target of reward plus discounted next value has expectation equal to the Bellman backup of the current table. The update therefore moves the table toward that backup without a model. The omitted step is the stochastic-approximation argument that turns this unbiasedness into convergence when the step size decreases.

The edge case. L1 says the table is overwritten until the changes become small. Small is not zero. Exact convergence takes infinitely many sweeps [S:83:105]. A real program halts when the largest change in a sweep falls below a threshold [S:83:97]. That threshold sets the error. At a halt with change below the threshold, the distance to the fixed point is at most the threshold divided by one minus the discount. The derivation runs the contraction inequality once more and solves for the error. Two runs that both look finished can differ by that bound.

What L1 hid. L1 used a constant step size of 0.5 in a deterministic example. In a stochastic task a constant step size leaves the estimate moving forever, because each update responds to the most recent episode [S:83:147]. The guarantee with probability one needs a decreasing step size [S:83:146]. L1's example hid this because the transition was certain, so the only source of noise was gone.

Where the analogy breaks. A recipe can be followed once and the cake is done. TD needs many passes, and each pass changes the estimate that the next pass uses as a target. The recipe analogy suggests a fixed procedure with a fixed output. The update is a moving target, and that is the whole difficulty.

Original sources. Sutton and Barto state TD(0) in §6.1, with the update, the TD error and the claim that its target is the reward plus the discounted next estimate [S:83:142-143]. They call it a bootstrapping method, because it learns a guess from an existing guess [S:83:142]. They also show that a Monte Carlo error equals a sum of TD errors when the table is held fixed during the episode [S:83:143]. They attribute Q-learning to Watkins, 1989 [S:83:153]. The dynamic-programming algorithms are in Chapter 4 [S:83:102].

An open question. The book states that nobody has proved which of TD and Monte Carlo converges faster, and that it is not clear how to phrase the question [S:83:146]. That remains the sharpest open question here. The two estimators differ in bias and variance, and "faster" needs a fixed budget, a fixed accuracy and a fixed class of tasks. Evidence that would settle it: a sample-complexity theorem for both methods under matched assumptions, with matching upper and lower bounds.

A frontier result. The Atari agent trains a convolutional network with a variant of Q-learning. Its input is raw pixels and its output is a value function [S:274:1]. It outperforms previous approaches on six of the games and surpasses a human expert on three of them [S:274:1]. The update survives and the table is replaced by a network. That replacement is where the clean guarantee is lost, because most convergence proofs cover only the table-based case [S:83:146].

What to read next. Read §4.1 of Sutton and Barto for policy evaluation [S:83:96] and §4.4 for value iteration [S:83:105]. Read §6.1 and §6.5 for TD and Q-learning [S:83:153]. Then read Chapter 3 of Zhao for the contraction proof that L2 uses [S:82:57-58], and the overview of Szepesvári for how samples and function approximation turn dynamic programming into a practical algorithm [S:80:4].