High-confidence error estimates for learned value functions

Touqir Sajed, Wesley Chung, Martha White
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:682-691, 2018.

Abstract

Estimating the value function for a fixed pol- icy is a fundamental problem in reinforcement learning. Policy evaluation algorithms—to es- timate value functions—continue to be devel- oped, to improve convergence rates, improve stability and handle variability, particularly for off-policy learning. To understand the prop- erties of these algorithms, the experimenter needs high-confidence estimates of the accu- racy of the learned value functions. For en- vironments with small, finite state-spaces, like chains, the true value function can be easily computed, to compute accuracy. For large, or continuous state-spaces, however, this is no longer feasible. In this paper, we address the largely open problem of how to obtain these high-confidence estimates, for general state- spaces. We provide a high-confidence bound on an empirical estimate of the value error to the true value error. We use this bound to design an offline sampling algorithm, which stores the required quantities to repeatedly compute value error estimates for any learned value function. We provide experiments in- vestigating the number of samples required by this offline algorithm in simple benchmark re- inforcement learning domains, and highlight that there are still many open questions to be solved for this important problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-sajed18a, title = {High-confidence error estimates for learned value functions}, author = {Sajed, Touqir and Chung, Wesley and White, Martha}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {682--691}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/sajed18a/sajed18a.pdf}, url = {https://proceedings.mlr.press/r16/sajed18a.html}, abstract = {Estimating the value function for a fixed pol- icy is a fundamental problem in reinforcement learning. Policy evaluation algorithms—to es- timate value functions—continue to be devel- oped, to improve convergence rates, improve stability and handle variability, particularly for off-policy learning. To understand the prop- erties of these algorithms, the experimenter needs high-confidence estimates of the accu- racy of the learned value functions. For en- vironments with small, finite state-spaces, like chains, the true value function can be easily computed, to compute accuracy. For large, or continuous state-spaces, however, this is no longer feasible. In this paper, we address the largely open problem of how to obtain these high-confidence estimates, for general state- spaces. We provide a high-confidence bound on an empirical estimate of the value error to the true value error. We use this bound to design an offline sampling algorithm, which stores the required quantities to repeatedly compute value error estimates for any learned value function. We provide experiments in- vestigating the number of samples required by this offline algorithm in simple benchmark re- inforcement learning domains, and highlight that there are still many open questions to be solved for this important problem.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T High-confidence error estimates for learned value functions %A Touqir Sajed %A Wesley Chung %A Martha White %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-sajed18a %I PMLR %P 682--691 %U https://proceedings.mlr.press/r16/sajed18a.html %V R16 %X Estimating the value function for a fixed pol- icy is a fundamental problem in reinforcement learning. Policy evaluation algorithms—to es- timate value functions—continue to be devel- oped, to improve convergence rates, improve stability and handle variability, particularly for off-policy learning. To understand the prop- erties of these algorithms, the experimenter needs high-confidence estimates of the accu- racy of the learned value functions. For en- vironments with small, finite state-spaces, like chains, the true value function can be easily computed, to compute accuracy. For large, or continuous state-spaces, however, this is no longer feasible. In this paper, we address the largely open problem of how to obtain these high-confidence estimates, for general state- spaces. We provide a high-confidence bound on an empirical estimate of the value error to the true value error. We use this bound to design an offline sampling algorithm, which stores the required quantities to repeatedly compute value error estimates for any learned value function. We provide experiments in- vestigating the number of samples required by this offline algorithm in simple benchmark re- inforcement learning domains, and highlight that there are still many open questions to be solved for this important problem. %Z Reissued by PMLR on 04 October 2026.
APA
Sajed, T., Chung, W. & White, M.. (2018). High-confidence error estimates for learned value functions. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:682-691 Available from https://proceedings.mlr.press/r16/sajed18a.html. Reissued by PMLR on 04 October 2026.

Related Material