Krylov-Bellman boosting: Super-linear policy evaluation in general state spaces

2022-10-20 · Eric Xia, Martin J. Wainwright

We present and analyze the Krylov-Bellman Boosting (KBB) algorithm for policy evaluation in general state spaces. It alternates between fitting the Bellman residual using non-parametric regression (as in boosting), and estimating the value function via the least-squares temporal difference (LSTD) procedure applied with a feature set that grows adaptively over time. By exploiting the connection to Krylov methods, we equip this method with two attractive guarantees. First, we provide a general convergence bound that allows for separate estimation errors in residual fitting and LSTD computation. Consistent with our numerical experiments, this bound shows that convergence rates depend on the restricted spectral structure, and are typically super-linear. Second, by combining this meta-result with sample-size dependent guarantees for residual fitting and LSTD computation, we obtain concrete statistical guarantees that depend on the sample size along with the complexity of the function class used to fit the residuals. We illustrate the behavior of the KBB algorithm for various types of policy evaluation problems, and typically find large reductions in sample complexity relative to the standard approach of fitted value iterationn.

📄 PDF Abstract BibTeX arXiv:2210.11377

Code (0)

등록된 구현이 없습니다.

Basis refinement strategies for linear value function approximation in MDPs

2015-12-01 · NeurIPS 2015 12 · Gheorghe Comanici, Doina Precup, Prakash Panangaden

We provide a theoretical framework for analyzing basis function construction for linear value function approximation in Markov Decision Processes (MDPs). We show that important existing methods, such as Krylov bases and …

The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation

2024-06-17 · Noah Golowich, Ankur Moitra

In this paper, we study the offline RL problem with linear function approximation. Our main structural assumption is that the MDP has low inherent Bellman error, which stipulates that linear value functions have linear B…

Offline RL

Learning Bellman Complete Representations for Offline Policy Evaluation

2022-07-12 · Jonathan D. Chang, Kaiwen Wang, Nathan Kallus, Wen Sun

We study representation learning for Offline Reinforcement Learning (RL), focusing on the important task of Offline Policy Evaluation (OPE). Recent work shows that, in contrast to supervised learning, realizability of th…

continuous-control Continuous Control Reinforcement Learning (RL)Representation Learning

Representations for Stable Off-Policy Reinforcement Learning

2020-07-10 · ICML 2020 1 · Dibya Ghosh, Marc G. Bellemare

Reinforcement learning with function approximation can be unstable and even divergent, especially when combined with off-policy learning and Bellman updates. In deep reinforcement learning, these issues have been dealt w…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning

2021-04-28 · Andrew Patterson, Adam White, Martha White

Many reinforcement learning algorithms rely on value estimation, however, the most widely used algorithms -- namely temporal difference algorithms -- can diverge under both off-policy sampling and nonlinear function appr…

reinforcement-learning Reinforcement Learning (RL)