提出新型贝尔曼算子，融合强化学习中两种估值方法的优势。
To bootstrap or to rollout? An optimal and adaptive interpolation
- 设计可自适应插值的子图贝尔曼算子，连接传统估值方法
- 误差上界逼近最优方差，样本复杂度仅依赖状态子集分布
- 理论证明该方法在有限样本下不可超越，适合策略评估场景
强化学习中的估值函数估计依赖于自举（bootstrapping）和回溯（rollout）两种基本原理。本文提出一类新的贝尔曼算子——子图贝尔曼算子，可在两者之间进行自适应插值。所提出的估计器通过求解经验子图贝尔曼算子的不动点获得，融合了基于自举的时序差分（TD）方法与基于回溯的蒙特卡洛（MC）方法的优点。具体而言，其误差上界趋近于TD方法的最优方差，额外项依赖于所选状态子集的退出概率；同时具备MC方法的有限样本自适应性，样本复杂度仅取决于该子集的占据测度。我们进一步给出了信息论下界，证明该额外项在合理样本量下不可避免。这些结果共同确立了子图贝尔曼估计器作为统一TD与MC方法的最优且自适应框架。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。