← Back to all news
arXiv Statistics ML By Wenlong Mou, Jian Qian

Temporal difference learning adapts to incomplete coverage: an oracle inequality over subgraphs

Read the original on arXiv Statistics ML →

The paper demonstrates that ordinary temporal difference (TD) learning in a tabular setting automatically combines the asymptotic efficiency of TD with the visitation requirements of Monte Carlo (MC) methods. By introducing the subgraph Bellman variance—a measure of variance arising from bootstrapping within a subgraph and rollouts outside it—the authors prove a non‑asymptotic oracle inequality: the mean squared error of full TD is bounded by this variance divided by the sample size for every sufficiently covered subgraph containing the target, plus a higher‑order remainder that depends only on that subgraph. Importantly, the algorithm does not need to be supplied with any subgraph, allowing TD to adapt to incomplete coverage without global visitation guarantees.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv Statistics ML.

Related stories

arXiv Machine Learning
Sep 18

Model-based Bootstrap for Offline Policy Evaluation in Tabular Reinforcement Learning

The paper introduces a model-based bootstrap framework for uncertainty quantification in offline policy evaluation (OPE) within finite-horizon, time-inhomogeneous Markov decision processes. Unlike traditional bootstrap methods that resample entire episodes, this approach regenerates trajectories from an estimated MDP, enabling use of diverse offline data formats such as complete trajectories, transition-level observations, and trajectory fragments. The authors prove bootstrap distributional consistency, asymptotically valid confidence intervals, and consistent variance estimation, and demonstrate through simulations that the method yields tighter confidence intervals and more accurate variance estimates compared to existing techniques.

By Weiwei Wang, Yuqiang Li, Xianyi Wu, Bingyi Jing
reinforcement-learning
More like this →
arXiv Machine Learning
Oct 22

A Model-Free Continuous-Time RL Algorithm from Discrete-Time Off-Policy Data with End-to-End Guarantees

The paper introduces a model‑free continuous‑time reinforcement learning algorithm that learns from a fixed batch of discrete‑time off‑policy data. It builds on the PhiBE‑Q framework to create a PhiBE‑PI policy iteration that uses a single state‑action critic, avoiding explicit drift or diffusion estimation. The authors provide a local end‑to‑end suboptimality guarantee under linear function approximation, analyze error propagation from discretization, function approximation, and finite samples, and reveal a bias‑variance trade‑off where finer time discretization can worsen statistical error.

By Chaorui Yao, Yuming Paul Zhang, Lin Yang, Yuhua Zhu
diffusionreinforcement-learningsafety
More like this →