To bootstrap or to rollout? An optimal and adaptive interpolation
Bootstrapping and rollout are two fundamental principles for value function estimation in reinforcement learning (RL). We introduce a novel class of Bellman operators, called subgraph Bellman operators, that interpolate between bootstrapping and rollout methods. Our estimator, derived by solving the fixed point of the empirical subgraph Bellman operator, combines the strengths of the bootstrapping-based temporal difference (TD) estimator and the rollout-based Monte Carlo (MC) methods. Specifically, the error upper bound of our estimator approaches the optimal variance achieved by TD, with an additional term depending on the exit probability of a selected subset of the state space. At the same time, the estimator exhibits the finite-sample adaptivity of MC, with sample complexity depending only on the occupancy measure of this subset. We complement the upper bound with an information-theoretic lower bound, showing that the additional term is unavoidable given a reasonable sample size. Together, these results establish subgraph Bellman estimators as an optimal and adaptive framework for reconciling TD and MC methods in policy evaluation.
Code (0)
등록된 구현이 없습니다.
Tasks
Reinforcement Learning (RL)Similar Papers 제목 키워드 기반
Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-dependent regret bound. The first innovation is…
Multi-Armed BanditsAdaptive N-step Bootstrapping with Off-policy Data
The definition of the update target is a crucial design choice in reinforcement learning. Due to the low computation cost and empirical high performance, n-step returns with off-policy data is a widely used…
Atari GamesMuJoCoCADENCE: Closing the Reasoning Gap via Coverage-Adaptive On-Policy Distillation
On-policy knowledge distillation transfers reasoning from large teachers to compact students, but existing approaches suffer three compounding failure modes: (i) cold-start collapse, where a fresh student assigns near-ze…
Knowledge DistillationContextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards
Reinforcement Learning with Verifiable Rewards (RLVR) is an effective paradigm for improving the reasoning capabilities of large language models. However, existing RLVR methods utilize rollouts in an indiscriminate and s…
Reinforcement LearningMathematical ReasoningRollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation
We provide a unifying approximate dynamic programming framework that applies to a broad variety of problems involving sequential estimation. We consider first the construction of surrogate cost functions for the purposes…
Bayesian Optimization