II · THE IDEA · ARTIFICIAL INTELLIGENCE
Temporal Difference Learning Theory
▶ Listen · narrated
In reinforcement learning the target is rarely fixed. Non-stationary dynamics and heteroscedastic noise both shape whether an update rule converges or merely looks calm.
At a glance
- Setting
- Markov decision processes that need not stay stationary
- One approach
- Worst-case, model-based reinforcement learning
- Noise model
- Heteroscedastic variance via a variational parameterisation
- Design aims
- Simplicity, reliability and calibration of variance
Think of learning the value of chess positions by always guessing from your current guesses, not by playing every game to the end. Two things make that fragile. First, the rules of the “board” may slowly change—non-stationarity—so yesterday’s good guess is today’s biased one. A worst-case, model-based approach tries to plan for a range of allowed changes instead of pretending the rules freeze. Second, some positions are just noisier than others—heteroscedastic noise. A variational model of that variance tries to estimate how noisy each region is, simply and in a calibrated way, so you do not take huge steps on chaotic signals or tiny steps on clean ones. Linear approximation is like fitting with a rigid set of rulers; nonlinear approximation bends more, which can cut systematic bias but makes the interaction with drift and noise harder to control. The bias–variance tradeoff is the balance between those systematic errors and the jitter from noise and moving targets.
Bootstrapped value updates couple parameter motion to target motion. In a non-stationary MDP, target motion also reflects changes in transition or reward structure. A worst-case model-based formulation encodes a set of admissible process behaviours and seeks policies or value estimates with guarantees across that set, altering the fixed-point notion relative to classical stationary analyses. Separately, residuals may be heteroscedastic. A variational parameterisation of noise variance aims for simplicity of optimisation, reliability in training, and calibration between predicted and observed variance. Under linear function approximation, projection onto a feature span leaves approximation bias wherever the true value lies outside that span; under nonlinear approximation the hypothesis class expands, but the composition of bootstrapping, worst-case objectives and learned variance becomes non-convex and sensitive to step-size and capacity allocation. Bias arises from approximation and from worst-case conservatism; variance arises from sampling noise and from variance-model misspecification that warps effective learning rates. The sources motivate treating non-stationarity and heteroscedastic variance as first-class modelling choices, not as residuals to be absorbed silently into a mean TD update.
Look closer
The process itself may drift
A non-stationary Markov decision process does not promise fixed transition or reward structure over time. Any method that bootstraps a value estimate from later estimates therefore chases a moving target. A worst-case, model-based treatment makes that drift an explicit adversary rather than an unmodelled nuisance, which changes what “convergence” can mean: not settling to a single optimum of a fixed process, but remaining controlled under permitted changes.
Variance need not be constant
Heteroscedastic noise means the variance of the residual depends on the input or state, not a single global scale. A variational parameterisation of that variance is offered as a simple, reliable and calibrated way to represent uncertainty in the noise itself. Calibration matters because over-confident variance estimates tighten updates too aggressively; under-confident ones slow learning without buying real robustness.
Bias and variance pull opposite ways
When function approximation is used—linear or nonlinear—the representation can introduce systematic bias while the update noise contributes variance. Model-based worst-case reasoning tends to spend capacity on robustness to drift; a richer variance model spends capacity on describing noise. Neither choice is free: capacity used for one side of the tradeoff is unavailable to the other, and the supplied work treats those as design decisions rather than settled optima.
The story
Temporal-difference style learning updates a value estimate from another estimate rather than from a complete return. That single design choice couples the learner to whatever non-stationarity and noise live in the data stream. The material here does not re-derive classical tabular convergence theorems; it frames two practical pressures that appear as soon as the process or the noise model is taken seriously.
The first pressure is non-stationarity. In a non-stationary Markov decision process, the rules that generate the next state and reward may change. Bootstrapped targets then move not only because the learner’s own parameters move, but because the environment’s generating process moves. A worst-case, model-based approach responds by treating admissible changes as something the model must withstand, rather than assuming the process will sit still long enough for ordinary fixed-point arguments to apply unchanged. Convergence, under that view, is judged against a set of possible process behaviours, not against a single stationary optimum.
The second pressure is noise that refuses a constant variance. Residuals in value learning are often heteroscedastic: some regions of the state or feature space are inherently noisier than others. A variational parameterisation of that variance aims to be simple to fit, reliable in use, and calibrated so that stated uncertainty matches observed scatter. When variance is mis-specified, the learner’s effective step sizes warp—too large where noise is underestimated, too small where it is overestimated—so the bias–variance balance of the whole procedure shifts even if the mean model is untouched.
Function approximation sits across both pressures. A linear approximator restricts the hypothesis class and can leave irreducible bias wherever the true value function lies outside the span of the features. A nonlinear approximator enlarges that class and can reduce approximation bias, yet it also complicates the interaction between parameter updates, bootstrapped targets and any worst-case or variational objective. Nothing in the supplied sources claims a universal winner between linear and nonlinear forms; they only make clear that non-stationarity and heteroscedastic noise remain live terms in the tradeoff wherever approximation is used.
Read together, the two strands suggest a sober checklist rather than a single algorithm. Ask whether the process may drift, and if so whether the method is model-based and worst-case with respect to that drift. Ask whether residual variance is roughly constant, and if not whether the variance model is parameterised, trained and calibrated with the same care as the mean. Ask, finally, how much of the approximator’s capacity is absorbed by robustness and noise modelling rather than by representing the value function itself. Those questions do not replace detailed convergence proofs for particular TD updates, but they locate where bias, variance and the meaning of convergence actually arise once stationarity and homoscedasticity are no longer granted.
Why it mattered then
Non-stationary Markov decision processes force a break with analyses that assume a fixed kernel and reward. A worst-case, model-based treatment was a way to keep learning well-defined when those assumptions fail: the designer specifies what may change and seeks behaviour that remains acceptable across that set. In parallel, care about heteroscedastic noise and calibrated variance reflects a wider shift in statistical modelling—away from a single global noise scale toward variance that tracks the data. Placed beside value-based reinforcement learning, those choices mattered because bootstrapped updates amplify both drift and mis-specified noise; addressing them at the model level was an attempt to stop those errors being silently folded into the value estimate.
Why it matters now
Deployed learners rarely enjoy a stationary process or tidy, constant-variance residuals. Recommendation dynamics shift, robotics hardware wears, and simulators diverge from the field. Model-based worst-case thinking remains a template for stating what kinds of change a system must tolerate. Calibrated heteroscedastic variance remains a template for not trusting every residual equally. For anyone still using bootstrapped value updates under linear or nonlinear approximation, the bias–variance tradeoff is not an abstract curve: it is the live tension between robustness to drift, honesty about noise, and whatever capacity is left to fit the value function.
The surprising detail
The two strands pull in different directions with the same limited capacity. Worst-case, model-based reasoning spends modelling power on what the process might do under admissible change. Variational heteroscedastic variance spends modelling power on how loud the noise is in each region. A learner cannot treat both as free add-ons; every parameter used to harden against drift or to fit a variance surface is a parameter not used to reduce approximation bias in the mean value. The tradeoff is architectural, not merely a matter of tuning a step size.
What is disputed
The supplied sources address non-stationary MDPs via worst-case model-based reinforcement learning, and heteroscedastic noise via a variational variance parameterisation. They do not, by themselves, establish classical convergence theorems for particular temporal-difference algorithms under linear or nonlinear function approximation. Where this lesson discusses TD-style bootstrapping and bias–variance tradeoffs, it does so as a framing of those two strands, not as a claim that the sources settle open theoretical disputes about TD convergence.
Remember this
Bootstrapped value learning inherits non-stationarity and noise structure; worst-case models and calibrated heteroscedastic variance are two different ways to pay for that inheritance.
Test yourself
A team adds a richer heteroscedastic variance model to a bootstrapped value learner and, separately, considers a worst-case model-based treatment of process drift. Why might doing both without enlarging the approximator fail to reduce error as much as either change promises on paper?
Both interventions consume representational and optimisation capacity—one to describe state-dependent noise, one to cover admissible process changes. If the mean approximator is left unchanged, capacity that might have reduced approximation bias is diverted into robustness and variance fitting. Mis-calibrated variance can still warp effective step sizes, and worst-case objectives can still steer updates toward conservative predictions. Without extra capacity or an explicit budget between mean, variance and worst-case components, the bias–variance–robustness tradeoff can shift rather than shrink overall error.
Go deeper
- [1904.10090] Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version · arxiv.org
- [2006.04910] Variational Variance: Simple, Reliable, Calibrated Heteroscedastic Noise Variance Parameterization · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.