Learning is planning: near Bayes-optimal reinforcement learning via\n Monte-Carlo tree search

2012/02/14 by John Asmuth, Michael L. Littman, Asmuth, John +1 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1202.3699

openalex publication_date 2012/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Bayes-optimal behavior, while well-defined, is often difficult to achieve.\nRecent advances in the use of Monte-Carlo tree search (MCTS) have shown that it\nis possible to act near-optimally in Markov Decision Processes (MDPs) with very\nlarge or infinite state spaces. Bayes-optimal behavior in an unknown MDP is\nequivalent to optimal behavior in the known belief-space MDP, although the size\nof this belief-space MDP grows exponentially with the amount of history\nretained, and is potentially infinite. We show how an agent can use one\nparticular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an\nefficient way to act nearly Bayes-optimally for all but a polynomial number of\nsteps, assuming that FSSS can be used to act efficiently in any possible\nunderlying MDP.\n

Cited by

• Neural Predictive Belief Representations

Related

• Bayesian Reinforcement Learning via Deep, Sparse Sampling
• Non-Asymptotic Analysis of Monte Carlo Tree Search
• Near-optimal Reinforcement Learning in Factored MDPs
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need
• Robust Bayesian reinforcement learning through tight lower bounds