Finite Horizons, Batch Data, and Dynamic Treatment Regimes#

A bridge to the statistical RL literature — for readers sitting on logged experimental data, clinical records, or historical instrument runs rather than a simulator.

Backward induction: Bellman without the fixed point#

Everything so far assumed an infinite horizon with discount $\gamma$, where the Bellman equation is a fixed-point equation and algorithms iterate to convergence. Many scientific and clinical problems are instead finite-horizon and episodic: a treatment protocol with $T$ decision points, an experimental campaign with $T$ stages. Then the value functions are time-indexed, the optimal policy is non-stationary, and the Bellman equation becomes an exact backward recursion:

$$ Q_T^*(s, a) = \mathbb{E}\big[ r_T \mid s, a \big], \qquad Q_t^*(s, a) = \mathbb{E}\big[ r_t + \max_{a'} Q_{t+1}^*(s_{t+1}, a') \;\big|\; s, a \big]. $$

No contraction argument needed — the recursion terminates in $T$ steps by construction. Discounting and finite horizon are two devices for the same job: keeping the recursion well-posed.

The statistical algorithm: regression + backward induction#

Given a batch of $n$ logged trajectories $\{(s_1, a_1, r_1, \dots, s_T, a_T, r_T)\}_{i=1}^n$:

  1. Stage $T$: regress $r_T$ on $(s_T, a_T)$ to get $\hat{Q}_T$.
  2. Stage $t < T$: form pseudo-outcomes $y_t = r_t + \max_{a'} \hat{Q}_{t+1}(s_{t+1}, a')$ and regress them on $(s_t, a_t)$ to get $\hat{Q}_t$.
  3. Recurse down to $t = 1$; the estimated regime is $\hat{\pi}_t(s) = \arg\max_a \hat{Q}_t(s, a)$.

Each stage is an ordinary supervised regression — linear models, splines, trees, networks, whatever fits. This is why the statistics community favors the formulation: it admits sample-complexity analysis, semiparametric efficiency theory, and honest confidence intervals in a way that online stochastic approximation resists. In biostatistics this is Q-learning for dynamic treatment regimes (DTRs) (Murphy, 2005); in the RL literature the batch-regression idea is Fitted Q-Iteration (Ernst et al., 2005).

Where it sits in the lecture's taxonomy: value-based (learns $Q$, acts by argmax) · model-free ($P$ is never estimated) · off-policy (the $\max$ is a Bellman optimality backup, so it learns the optimal regime from whatever behavior policy — e.g. clinicians — generated the data) · and squarely offline: the "orthogonal axis" of the taxonomy figure, here as the main event.
Deep dive: why backward induction is stable where DQN needs tricks
The pseudo-outcomes bootstrap on $\hat{Q}_{t+1}$ — TD-style, not Monte Carlo, even though full trajectories are in hand. But because induction runs backward, each $\hat{Q}_{t+1}$ is already final when it is used: there is no moving target and one sweep suffices. DQN fights the moving-target problem with a frozen target network; backward induction gets that stability for free from the finite horizon. Indeed, a useful mental model is:

DQN ≈ Fitted Q-Iteration made incremental — the replay buffer plays the role of the batch, the target network the role of the previous iterate.

The cost does not vanish, it moves: regression error at stage $t{+}1$ propagates into the stage-$t$ pseudo-outcomes, so errors compound across stages rather than across iterations — the bias–propagation analyses in the DTR literature quantify exactly this. And the $\max$ over an estimated $\hat{Q}_{t+1}$ inherits the optimizer's curse: noise is selected upward, the finite-horizon cousin of the overestimation that motivates Double DQN.
Deep dive: is SGD on fitted-Q the same as Q-learning?

Exactly yes in the tabular case; instructively no under function approximation. Both approximate the same operation (i.e. value iteration, $Q \leftarrow \mathcal{T}Q$) but with different error structure. The mapping is a chain of three equivalences, each of which breaks at a specific link.

The exact correspondence. Take fitted-Q and replace the full regression solve with a single SGD step on the squared Bellman loss, holding the target fixed (a "semi-gradient" step with no differentiation through the target):

$$ \theta \leftarrow \theta + \alpha \big[\, r + \gamma \max_{a'} Q_\theta(s',a') - Q_\theta(s,a) \,\big] \nabla_\theta Q_\theta(s,a). $$

With a tabular parameterization where $Q_\theta(s,a) = \theta_{sa}$, so the gradient is an indicator, this is literally the classical Q-learning update, symbol for symbol. Tabular Q-learning is SGD on the fitted-Q objective, with three specific choices: one sample per step, target refreshed every step, semi-gradient.

Under function approximation, each choice becomes a fork:

  • 1. Target freshness. FQI freezes $\hat{Q}_{k-1}$ for an entire regression solve, which is a sequence of well-posed supervised problems. Online Q-learning refreshes the target with every parameter update, chasing a moving target. With function approximation this is the deadly triad (bootstrapping + approximation + off-policy data) and can diverge outright — Baird's counterexample is the classic demonstration. Same limit point when both behave; very different stability guarantees. DQN's target network is exactly the interpolation: freeze for $C$ steps, i.e. partially solve each FQI regression before refreshing.
  • 2. Semi-gradient vs. true gradient. The correspondence requires not differentiating through the target component $\max_{a'} Q_\theta(s', a')$. Taking the honest gradient of the squared Bellman error (residual-gradient methods) gives a different algorithm converging to a different fixed point under approximation. "SGD on the TD loss" means Q-learning only under the stop-gradient convention, which enforced silently in deep-RL code (target.detach()) and easy to miss on paper.
  • 3. How far each regression is solved. If the per-iteration problem is convex (e.g. linear function classes) and SGD runs to convergence before the target refreshes, SGD-FQI recovers batch FQI exactly — SGD is then merely the optimizer, not part of the algorithm's identity. One step per refresh is the fully online end. Everything between is a genuinely different algorithm with different error propagation: FQI's approximation error compounds across Bellman iterations (the $\sum_k \gamma^{K-k}\,\varepsilon_k$-style bounds of the batch-RL literature), while online Q-learning's analysis runs through stochastic approximation with a moving target.

A quieter statistical difference: FQI reuses the same batch at every iteration, which is data-efficient, but errors correlate across iterations, while classical online Q-learning consumes each transition once. Replay buffers move the online algorithm toward the batch regime: another sense in which DQN ≈ FQI made incremental.

The one-line summary: tabular Q-learning = single-sample, per-step-refreshed, semi-gradient SGD on the fitted-Q objective exactly. Under function approximation the two separate, and the separation (moving targets, deadly triad, error compounding) is precisely what DQN's replay buffer and target network are engineering responses to.

No exploration knob: coverage and pessimism#

Offline, the corridor-vs-corner lesson returns in sharper form. There is no $\varepsilon$ to turn up and you are stuck with wherever the behavior policy went. The tabular condition “visit every $(s,a)$ infinitely often” becomes a coverage (concentrability) assumption: the logged data must put mass on the state–action pairs that candidate optimal policies would visit. When coverage fails, $\max_{a'} \hat{Q}_{t+1}$ happily selects actions the data barely support — extrapolation error dressed up as optimality.

The modern offline-RL response is pessimism: penalize or constrain value estimates in poorly-covered regions, so the learned policy prefers actions the data can actually vouch for. The same instinct appears as conservative value estimates (CQL), policies constrained toward the behavior policy, and uncertainty-penalized pseudo-outcomes. It has a familiar statistical reading: report a lower confidence bound, not the point estimate, when someone is about to act on it.

For practitioners: if you plan to learn a regime from logged data, the first question is not which algorithm but what did the behavior policy explore? A dataset of uniformly good decisions is, paradoxically, a poor teacher — it contains no information about the alternatives. This is the offline mirror of the exploration–exploitation trade-off, and it is a data-collection (design!) problem before it is an estimation problem.

Pointers into the literature#

  • Murphy (2005), A generalization error for Q-learning, JMLR — Q-learning with backward induction for dynamic treatment regimes, with finite-sample guarantees; the companion methodology line begins with Murphy (2003), Optimal dynamic treatment regimes, JRSS-B.
  • Ernst, Geurts & Wehenkel (2005), Tree-based batch mode reinforcement learning, JMLR — Fitted Q-Iteration: the batch-regression view of Q-learning that DQN later made incremental.
  • Levine et al. (2020), Offline reinforcement learning: tutorial, review, and perspectives on open problems — the modern survey; start here for the pessimism line (e.g. CQL: Kumar et al., 2020) and coverage assumptions.
  • For the DTR-statistics view at book length: Tsiatis et al. (2020), Dynamic Treatment Regimes: Statistical Methods for Precision Medicine.
Backward 2.3 Q-Learning: Learning Without a Model 3. Deep RL: DQN → PPO Forward