Measurable Monte Carlo Search Error Bounds
This provides a practical tool for evaluating action confidence in Monte Carlo planning, addressing a known limitation in the field.
The authors tackled the problem of measuring confidence in Monte Carlo planners' recommended actions by proving computable bounds on sub-optimality for non-stationary bandits and Markov decision processes, with empirical tests showing tightness in experiments.
Monte Carlo planners can often return sub-optimal actions, even if they are guaranteed to converge in the limit of infinite samples. Known asymptotic regret bounds do not provide any way to measure confidence of a recommended action at the conclusion of search. In this work, we prove bounds on the sub-optimality of Monte Carlo estimates for non-stationary bandits and Markov decision processes. These bounds can be directly computed at the conclusion of the search and do not require knowledge of the true action-value. The presented bound holds for general Monte Carlo solvers meeting mild convergence conditions. We empirically test the tightness of the bounds through experiments on a multi-armed bandit and a discrete Markov decision process for both a simple solver and Monte Carlo tree search.