Temporal-Difference Calibration of Black-Box Simulators
Authors: Min Zeng, Xin Wen, Xi Chen, Yichen Zhang, Wen-Xin Zhou
Organizations: College of Computing, City University of Hong Kong · Stern School of Business, New York University · Daniels School of Business, Purdue University · Department of Information and Decision Science, University of Illinois Chicago
We develop a derivative-free temporal-difference (TD) framework for calibrating black-box simulators using one-step transitions from a target system and noisy simulator-generated continuation values. The calibration parameter is defined through Bellman orthogonality, recovering the physical parameter under correct simulator specification and yielding a near-optimal L2 approximation of the policy value under misspecification. We propose three TD algorithms based on random-direction finite differences, distinguished by their query costs and reuse of noisy simulator evaluations. We establish almost-sure convergence, last-iterate mean-square error bounds, and central limit theorems for Polyak-Ruppert averages across four query-noise regimes. Our analysis reveals a specification-dependent bias phenomenon: for two algorithms, the finite-difference bias of the TD estimating equation vanishes at the calibration target under correct specification, even when the gradient surrogate remains biased. This permits a fixed perturbation radius and rate exponents approaching 1/2 in the simulator rollout budget, whereas misspecification generally recovers the classical Kiefer-Wolfowitz rates. We also develop a few-replicate online bootstrap that yields Student-t calibrated confidence intervals under negligible query noise, and identify a covariance mismatch that can invalidate conventional multiplier inference along Markov trajectories. Finally, a second-stage TD recursion corrects the remaining value discrepancy without additional simulator queries.
Figures & tables
Noise regime
Lead term
Rate aT
Additional rate conditions
Qregalg
Fast-decaying: ζ>2β
mt
T
κalgβ>1/2
Q
Boundary: ζ=2β>0
mt+qt
T
κalgβ>1/2
Qbdryalg
Intermediate: 0<ζ<2β
qt
T(1−2β+ζ)/2
2α+ζ−2β>1 , and κalgβ>(1−2β+ζ)/2
Qintalg
Persistent: ζ=0
qt
T(1−2β)/2
2α−2β>1 , and κalgβ>(1−2β)/2
Qpersalg
Table 1: Query-noise regimes for Polyak–Ruppert averages.
Quantity
DF-Ind
DF-Fwd
DF-Sym
Fresh queries per update Lalg
4
3
3
Bias order κalg
2
1
2
Gradient-noise factor
21
2
21
Covariance in the fast-decaying regime
Q
Q
Q
Product-noise factor, persistent regime
21+γ2
2γ2+1+μ4
2γ2+8μ4−1
Root shift under correct specification at fixed ν
none
none
O(ν2)
Table 2: Query cost, finite-difference accuracy, leading effects of query noise, and target preservation across the three DF-TD designs. The gradient-noise factors multiply (σt2/νt2)Id in Cov(N∇,t∣Ft−1) . The product-noise factors multiply cσ2{cν2(1+2β)}−1Id in Qpersalg . The root-shift bounds follow from Corollary 2 . The last row assumes query variance v(s,θ)/M at fixed replication M and follows from Proposition S3 in the Appendix.
Figure 1: Tuning geometry for averaged DF-TD inference when the finite-difference bias at the root does not vanish. The solid line ζ=2β separates the fast-decaying region from the region dominated by query noise. Dashed lines give the boundaries for the finite-difference bias in the first- and second-order cases. Table 1 gives the exact rates and the additional α -dependent conditions.
We investigate the statistical properties of Temporal Difference (TD) learning with Polyak-Ruppert averaging, arguably one of the most widely used algorithms in reinforcement learning, for the task of estimating the parameters of the optimal linear approximation to the value function. Assuming independent samples, we make three theoretical contributions that improve upon the current state-of-the-art results: (i) we establish refined high-dimensional Berry-Esseen bounds over the class of convex sets, achieving faster rates than the best known results, and (ii) we propose and analyze a novel, computationally efficient online plug-in estimator of the asymptotic covariance matrix; (iii) we derive sharper high probability convergence guarantees that depend explicitly on the asymptotic variance and hold under weaker conditions than those adopted in the literature. These results enable the construction of confidence regions and simultaneous confidence intervals for the linear parameters of the value function approximation, with guaranteed finite-sample coverage. We demonstrate the applicability of our theoretical findings through numerical experiments.
Weichen Wu, Gen Li, Yuting Wei +1
The Voleon Group, New York, NY, USA · Department of Statistics, The Chinese University of Hong Kong, Hong Kong SAR. · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. +1
Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target. For fixed-stepsize linear TD, we establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error. We then derive a joint functional limit for parallel Richardson--Romberg (RR) recursions driven by the same trajectory. A Brownian-bridge self-normalizer yields asymptotically pivotal confidence regions for prespecified state-value contrasts without estimating the long-run covariance or selecting a bandwidth or batch length. For such a contrast, the procedure admits a one-pass implementation whose memory does not grow with the trajectory length. At a fixed stepsize, the inferential center is the RR stationary target. We also study horizon-indexed designs in which the stepsize remains constant within each run and decreases across longer horizons. Under an explicit RR-dependent rate window, the residual RR target shift, multiplicative remainder, and initialization effect are negligible at the root-n scale, yielding inference for the projected Bellman solution. Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.
Min Zeng, Yichen Zhang, Xiaofeng Shao
Department of Biostatistics, City University of Hong Kong, Hong Kong SAR, China · Department of Quantitative Methods, Purdue University, West Lafayette, Indiana, USA · Department of Statistics and Data Science, Washington University in St. Louis, St. Louis, Missouri, USA +1
Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice -- such as the minimum eigenvalue of the feature covariance (ω) or the mixing time of the underlying Markov chain (τmix). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d.\ setting, the proposed algorithm does not require knowledge of problem-dependent quantities such as ω, and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of τmix or ω.
Yunxiang Li, Mark Schmidt, Reza Babanezhad +1
University of British Columbia · Samsung AI - Montreal · Simon Fraser University