Not Logged In

PapersDB

High-confidence error estimates for learned value functions

• Touqir Sajed
• Wesley Chung
• Martha White, University of Alberta

Estimating the value function for a fixed policy is a fundamental problem in reinforcement learning. Policy evaluation algorithms—to estimate value functions continue to be developed, to improve convergence rates, improve stability and handle variability, particularly for off-policy learning. To understand the properties of these algorithms, the experimenter needs high-confidence estimates of the accuracy of the learned value functions. For environments 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 statespaces. 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 investigating the number of samples required by this offline algorithm in simple benchmark reinforcement learning domains, and highlight that there are still many open questions to be solved for this important problem.

Citation

BibTeX

@incollection{Sajed+al:UAI18,
  author = {Touqir Sajed and Wesley Chung and Martha White},
  title = {High-confidence error estimates for learned value functions},
  Editor = {Amir Globerson, Ricardo Silva},
  Pages = {683-692},
  booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
  year = 2018,
}

Last Updated: February 25, 2020
Submitted by Sabina P

• Home
• Search
  • Advanced Search
• Publications
  • View Publication Entries
• Authors
  • View Authors
• User
  • Login or Register