Value-Based and Policy-Based Reinforcement Learning

Temporal-difference (TD) learning, as presented in Sutton and Barto's textbook, updates a value estimate using a bootstrapped target built from one step of real experience plus the agent's own current estimate of what comes after, rather than waiting for an entire episode to finish and using the actual return, as Monte Carlo methods do. The simplest form, TD(0), updates a state-value estimate V(s) toward the target r + γV(s'), where r is the reward just observed, γ is the discount factor, and V(s') is the current estimate of the value of the state the agent just moved into. The gap between this target and the current estimate, δ = [r + γV(s')] − V(s), is called the TD error, and the update rule is simply V(s) ← V(s) + αδ, where α is a step-size parameter controlling how much of that error is corrected on each visit. Because the target itself depends on an estimate rather than a fully realized outcome, TD learning can update its values after every single step, without waiting for an episode to terminate, which is what lets it learn online, incrementally, and even in tasks that never end.

A concrete pass through the arithmetic makes this mechanical. Suppose V(s) = 2.0, the agent takes an action, observes reward r = 1, discount γ = 0.9, and lands in a state with current estimate V(s') = 3.0. The TD target is r + γV(s') = 1 + 0.9 × 3.0 = 1 + 2.7 = 3.7. The TD error is δ = 3.7 − 2.0 = 1.7. With step size α = 0.5, the updated estimate is V(s) ← 2.0 + 0.5 × 1.7 = 2.0 + 0.85 = 2.85 — the estimate moves partway toward the bootstrapped target, exactly as much as α dictates, leaving room to be corrected further on future visits to the same state. Notice that the update never required knowing the true value of state s, nor the true value of s' — only a single observed reward and the agent's own running estimate of what follows. That is the entire mechanism by which TD methods propagate information backward through a sequence of states over many visits, gradually tightening every estimate toward internally consistent values without ever needing a complete episode to finish first.

Q-learning, introduced by Watkins and Dayan in 1992 and described in Sutton and Barto, extends this same bootstrapping idea to action-values rather than state-values, and does so off-policy: the update rule Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') − Q(s,a)] always bootstraps toward the maximum estimated value over the next state's actions, regardless of which action the agent's behavior policy actually selected next. This is what makes Q-learning off-policy — it can learn about the greedy, value-maximizing target policy while behaving according to a different, more exploratory policy (such as one that occasionally picks a random action) — in contrast to on-policy methods, which evaluate the very policy generating the data. Working through numbers again: if Q(s,a) = 4.0, the observed reward is r = 2, γ = 0.9, and the largest Q-value among the next state's available actions is max_a' Q(s',a') = 5.0, then the target is 2 + 0.9 × 5.0 = 2 + 4.5 = 6.5, the error is 6.5 − 4.0 = 2.5, and with α = 0.1 the updated estimate is 4.0 + 0.1 × 2.5 = 4.0 + 0.25 = 4.25 — inching Q(s,a) toward the reward plus the best available continuation, exactly as the off-policy target prescribes.

Q-learning and other value-based methods derive a policy indirectly, by acting greedily with respect to learned action-values, which becomes awkward once the action space is continuous or extremely large, since "take the maximum over all actions" is no longer a simple lookup. Policy gradient methods instead parameterize a policy π_θ(a|s) directly — for instance as a softmax over action preferences, or a Gaussian over a continuous control — and adjust its parameters θ by gradient ascent on the expected return J(θ). The policy gradient theorem, proved by Sutton, McAllester, Singh, and Mansour in 1999, gives a remarkably clean expression for this gradient: ∇J(θ) = E[∇θ log π_θ(a|s) · Q^π(s,a)], an expectation taken over states and actions visited under the current policy. The significance of this result is that it avoids having to differentiate through the (generally unknown and much harder to characterize) distribution over states the policy induces — the gradient can be estimated using only samples of states, actions, and their associated values, which is what makes policy-based learning practical.

Williams' 1992 REINFORCE algorithm is the direct Monte Carlo instantiation of this theorem: instead of a learned Q^π(s,a), it uses the actual observed return G_t from that point in the episode onward as an unbiased, if high-variance, stand-in for the action-value term. Because G_t is a single noisy sample of what could have happened from that state onward, rather than an averaged estimate, REINFORCE updates tend to be erratic from episode to episode even when they are correct on average, which can slow learning considerably in practice. A well-known variance-reduction technique subtracts a baseline b(s) — commonly an estimate of the state's value — from the return before weighting the log-probability gradient, using (G_t − b(s)) in place of G_t; because the baseline does not depend on the action taken, this subtraction leaves the expected gradient unchanged while typically shrinking its variance substantially, which speeds up and stabilizes learning without introducing bias. The choice of baseline matters for how much variance is removed, but not for whether the resulting gradient estimate remains correct in expectation.

A small worked example shows the mechanics. Consider a two-action softmax policy with π(a₁|s) = 0.3 and π(a₂|s) = 0.7, parameterized by logits z₁ and z₂. The standard softmax log-derivative identity gives ∇z₁ log π(a₁|s) = 1 − π(a₁|s) = 1 − 0.3 = 0.7, and ∇z₂ log π(a₁|s) = −π(a₂|s) = −0.7. Suppose the agent takes action a₁ and observes return G = 10, with step size α = 0.01: the REINFORCE update pushes Δz₁ = α·G·0.7 = 0.01 × 10 × 0.7 = 0.07 and Δz₂ = α·G·(−0.7) = −0.07, raising the logit for the action taken and lowering the other, exactly as intended for a positive return. Now introduce a baseline b = 6, so the advantage is G − b = 10 − 6 = 4: the update shrinks to Δz₁ = 0.01 × 4 × 0.7 = 0.028 and Δz₂ = −0.028 — the same direction, but a much smaller step, illustrating how a baseline reduces the magnitude (and, over many samples, the variance) of the update without changing which direction it points.

Actor-critic methods combine the two ideas from the previous lessons: an actor, a directly parameterized policy updated via the policy gradient, and a critic, a learned value function that supplies a much lower-variance substitute for the raw Monte Carlo return REINFORCE relies on. Konda and Tsitsiklis formalized this architecture in 1999–2000, proving convergence results for actor-critic algorithms under function approximation and establishing it as a distinct, theoretically grounded family rather than an ad hoc combination. The critic's TD error, δ = r + γV(s') − V(s), is itself a natural, low-variance approximation to the advantage of the action just taken — how much better or worse that action was than the state's average value — so the actor can use δ in place of the return-minus-baseline term from REINFORCE. Reusing the TD-error value computed earlier, δ = 1.7, against the same softmax policy (π(a₁|s) = 0.3, α = 0.01) gives an actor update of Δz₁ = α·δ·(1 − π(a₁|s)) = 0.01 × 1.7 × 0.7 = 0.0119 and Δz₂ = −0.0119 — the critic's bootstrapped, one-step error stands in for the full-episode return, letting the actor update after every step instead of waiting for an episode to end.

Scaling these ideas up is where deep reinforcement learning enters. DQN, covered in this course's Reinforcement Learning module, showed that a deep convolutional network could approximate an action-value function directly from raw pixels, stabilized by experience replay and a target network; TRPO, introduced by Schulman and colleagues in 2015, and its simpler successor PPO, introduced by Schulman and colleagues in 2017, apply the same policy-gradient machinery from this module but constrain each update — via a trust region in TRPO, or a clipped surrogate objective in PPO — to prevent the large, destabilizing policy changes that plain gradient ascent on J(θ) is prone to when function approximation is involved. AlphaGo, described by Silver and colleagues in their 2016 Nature paper, combined a policy network trained partly via policy-gradient self-play with a value network functioning much like a critic, feeding both into Monte Carlo tree search to defeat top human Go players — an actor-critic-shaped architecture operating at a scale far beyond the two-action toy example above, but built from exactly the same value-based and policy-based ingredients this module introduces.