Online Bellman Residual Algorithms with Predictive Error Guarantees

Wen Sun Carnegie Mellon University, J. Andrew Bagnell Carnegie Mellon University
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:830-839, 2015.

Abstract

We establish a connection between optimizing the Bellman Residual and worst case long-term predictive error. In the online learning framework, learning takes place over a sequence of trials with the goal of predicting a future discounted sum of rewards. Our analysis shows that, together with a stability assumption, any no-regret online learning algorithm that minimizes Bellman error ensures small prediction error. No statistical assumptions are made on the sequence of observations, which could be non-Markovian or even adversarial. Moreover, the analysis is independent of the particular form of function approximation and the particular (stable) no-regret approach taken. Our approach thus establishes a broad new family of provably sound algorithms for Bellman Residual-based learning and provides a generalization of previous worst-case result for minimizing predictive error. We investigate the potential advantages of some of this family both theoretically and empirically on benchmark problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15t, title = {Online Bellman Residual Algorithms with Predictive Error Guarantees}, author = {University, Wen Sun Carnegie Mellon and University, J. Andrew Bagnell Carnegie Mellon}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {830--839}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15t/university15t.pdf}, url = {https://proceedings.mlr.press/r13/university15t.html}, abstract = {We establish a connection between optimizing the Bellman Residual and worst case long-term predictive error. In the online learning framework, learning takes place over a sequence of trials with the goal of predicting a future discounted sum of rewards. Our analysis shows that, together with a stability assumption, any no-regret online learning algorithm that minimizes Bellman error ensures small prediction error. No statistical assumptions are made on the sequence of observations, which could be non-Markovian or even adversarial. Moreover, the analysis is independent of the particular form of function approximation and the particular (stable) no-regret approach taken. Our approach thus establishes a broad new family of provably sound algorithms for Bellman Residual-based learning and provides a generalization of previous worst-case result for minimizing predictive error. We investigate the potential advantages of some of this family both theoretically and empirically on benchmark problems.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Online Bellman Residual Algorithms with Predictive Error Guarantees %A Wen Sun Carnegie Mellon University %A J. Andrew Bagnell Carnegie Mellon University %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15t %I PMLR %P 830--839 %U https://proceedings.mlr.press/r13/university15t.html %V R13 %X We establish a connection between optimizing the Bellman Residual and worst case long-term predictive error. In the online learning framework, learning takes place over a sequence of trials with the goal of predicting a future discounted sum of rewards. Our analysis shows that, together with a stability assumption, any no-regret online learning algorithm that minimizes Bellman error ensures small prediction error. No statistical assumptions are made on the sequence of observations, which could be non-Markovian or even adversarial. Moreover, the analysis is independent of the particular form of function approximation and the particular (stable) no-regret approach taken. Our approach thus establishes a broad new family of provably sound algorithms for Bellman Residual-based learning and provides a generalization of previous worst-case result for minimizing predictive error. We investigate the potential advantages of some of this family both theoretically and empirically on benchmark problems. %Z Reissued by PMLR on 04 October 2026.
APA
University, W.S.C.M. & University, J.A.B.C.M.. (2015). Online Bellman Residual Algorithms with Predictive Error Guarantees. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:830-839 Available from https://proceedings.mlr.press/r13/university15t.html. Reissued by PMLR on 04 October 2026.

Related Material