Beyond Bellman: High-Order Generator Regression for Continuous-Time Policy Evaluation

1. Problem Statement

The paper addresses the problem of finite-horizon continuous-time policy evaluation using discrete, logged closed-loop trajectories under time-inhomogeneous dynamics.

• Context: In reinforcement learning (RL) and stochastic control, the goal is often to estimate the value function $V(s, t)$ of a fixed controller. The true value function satisfies a backward parabolic partial differential equation (PDE) driven by the system's generator (drift and diffusion).
• The Challenge: Data is observed only on a discrete time grid with step size $\Delta t$. The standard approach, the Bellman baseline, combines the continuous-time value equation with a single forward time step.
• The Limitation: While the Bellman baseline is the natural statistical comparator, it suffers from a first-order discretization error ($O(\Delta t)$). This is because it effectively uses a one-step difference (left-Riemann sum) to approximate the integral of the reward and value over time. As the horizon $T$ is fixed and the number of steps $T/\Delta t$ increases, the accumulated global error remains first-order, limiting accuracy even with dense sampling.

2. Methodology: High-Order Generator Regression

The authors propose replacing the one-step discretization of the Bellman baseline with a high-order generator regression approach that utilizes multi-step transitions.

Core Concept

Instead of directly regressing the value function using one-step transitions, the method estimates the space-time generator $G = \partial_t + \mathcal{L}_{\mu, \Sigma}$ (where $\mathcal{L}$ is the infinitesimal generator of the diffusion) using multi-step moment matching.

1. Multi-Step Expansion: Using Dynkin's formula, the expectation of a function $U$ over $j$ steps is expanded as a Taylor series in $\Delta t$ involving powers of the generator $G^k$.
2. Moment Matching Coefficients: The authors define coefficients $a^{(i)} = (a^{(i)}_0, \dots, a^{(i)}_i)$ such that a weighted linear combination of multi-step expectations cancels out lower-order truncation terms ($k=0, 2, \dots, i$) while isolating the first-order term ($k=1$).
   • This allows the construction of an estimator for the generator $G$ with an error of order $O(\Delta t^i)$.
   • Gen2 ($i=2$) and Gen3 ($i=3$) are the second and third-order estimators, respectively.
3. Surrogate PDE: The estimated generator (via estimated drift $\hat{\mu}_i$ and diffusion $\hat{\Sigma}_i$) is plugged into the backward PDE. The resulting surrogate value function $\hat{V}_i$ is solved via backward regression on the original time grid.
4. Temporal Pooling: To handle finite-sample noise, the method employs temporal pooling (averaging over a window $h$) to estimate the moments required for the generator coefficients.

Theoretical Framework

The paper provides a rigorous end-to-end error decomposition for the estimator. The total error is bounded by:
$$\text{Total Error} \leq C_{ms} \left( C_0 (\eta_{gen} + \eta_{proj} + \eta_{pool} + \eta_{stat}) + \eta_{start} \right)$$
Where:

• $\eta_{gen}$: Generator misspecification (reduced to $O(\Delta t^i)$ by the method).
• $\eta_{proj}$: Projection error (due to function approximation).
• $\eta_{pool}$: Pooling bias (due to non-stationarity over the pooling window).
• $\eta_{stat}$: Finite-sample statistical error.
• $\eta_{start}$: Start-up error (from the terminal block of the multistep recursion).
• $C_0$: Local inversion constant.
• $C_{ms}$: Global amplification constant determined by the stability of the backward recursion.

3. Key Contributions

1. Bellman-to-Generator Viewpoint: The paper unifies the Bellman baseline and high-order methods under a single argument. It demonstrates that the Bellman baseline is simply the $i=1$ case of a family of generator estimators. The proposed method cancels lower-order terms to achieve higher-order population surrogates without changing the information class (logged trajectories).
2. End-to-End Recursion Theorem: The authors derive a single theorem with explicit constants ($C_0$ and $C_{ms}$) that decomposes the error into distinct, interpretable components (misspecification, projection, pooling, statistics, start-up). This moves beyond asymptotic "big-O" claims to provide concrete bounds on stability and convergence.
3. Decision-Frequency Regime Map: A critical theoretical contribution is the identification of a regime map that dictates when higher-order gains are visible. The authors define a "nonstationarity floor" ($F_{ns}$) determined by the trade-off between pooling bias and variance.
   • Regime 1: If $F_{ns} \gtrsim \Delta t$, all methods are dominated by sampling noise; no order gain is visible.
   • Regime 2: If $\Delta t^2 \lesssim F_{ns} \lesssim \Delta t$, Gen2 reliably outperforms the Bellman baseline, but Gen3 may not stabilize.
   • Regime 3: If $F_{ns} \lesssim \Delta t^2$, third-order gains (Gen3) become visible, provided variance is controlled.

4. Experimental Results

The authors evaluated the method across four scales of benchmarks (Small $d=2$ to XLarge $d=24$), including nonlinear pendulums, coupled regulators, and networked linear-quadratic systems.

• Calibration: In controlled settings with known ground truth, the error scaling matched theoretical predictions: $O(\Delta t)$ for Bellman, $O(\Delta t^2)$ for Gen2, and $O(\Delta t^3)$ for Gen3.
• Benchmark Performance:
  • Gen2 consistently outperformed the Bellman baseline, reducing integrated Root Mean Squared Error (RMSE) by 13% to 48% depending on the task scale.
  • The improvement was most significant on medium-to-large tasks where the accumulation of first-order Bellman errors over the horizon was substantial.
  • Gen2 remained stable even when compared against "fitted-dynamic" anchors (model-based approaches), which failed to remain stable as task complexity increased.
• Operating Region Validation:
  • Experiments confirmed the regime map: Gen2 gains were largest when the nonstationarity floor was low enough to allow the second-order discretization gain to dominate.
  • Failure Modes: The method failed to outperform the baseline when feature classes were too restricted (poor approximation) or when the gain mismatch (behavior policy vs. target policy) was too severe, confirming the theoretical boundaries.
• Robustness: Gen2 proved to be the "safe default," offering significant gains over Bellman without the instability risks associated with higher-order (Gen3) methods in noisy, finite-sample regimes.

5. Significance and Impact

• Interpretability: Unlike "black-box" deep RL methods, this approach offers a clear, interpretable mechanism for improving policy evaluation: explicitly canceling truncation errors in the generator expansion.
• Practical Guidance: The "Regime Map" provides practitioners with a clear decision rule: Gen2 is usually the optimal choice for continuous-time evaluation from logged data, as it balances high-order accuracy with stability. Higher orders (Gen3) are only beneficial in very specific, low-noise, high-data regimes.
• Theoretical Rigor: By providing explicit constants and an end-to-end error bound, the paper bridges the gap between numerical PDE solvers and statistical learning theory, offering a new standard for analyzing continuous-time RL algorithms.
• Applicability: The method is applicable to any time-inhomogeneous diffusion process where logged trajectories are available, making it relevant for financial engineering, robotics, and control systems where continuous-time modeling is essential but data is discrete.

In summary, the paper successfully demonstrates that moving beyond the first-order Bellman baseline via high-order generator regression is a viable, theoretically grounded, and empirically superior strategy for continuous-time policy evaluation, provided the operating conditions (data density and non-stationarity) fall within the identified stable regime.