Tree Exploration for Bayesian RL Exploration

2009/02/02 by Christos Dimitrakakis, Dimitrakakis, Christos
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.0902.0392

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

Abstract

Research in reinforcement learning has produced algorithms for optimal decision making under uncertainty that fall within two main types. The first employs a Bayesian framework, where optimality improves with increased computational time. This is because the resulting planning task takes the form of a dynamic programming problem on a belief tree with an infinite number of states. The second type employs relatively simple algorithm which are shown to suffer small regret within a distribution-free framework. This paper presents a lower bound and a high probability upper bound on the optimal value function for the nodes in the Bayesian belief tree, which are analogous to similar bounds in POMDPs. The bounds are then used to create more efficient strategies for exploring the tree. The resulting algorithms are compared with the distribution-free algorithm UCB1, as well as a simpler baseline algorithm on multi-armed bandit problems.

Related

• Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning
• Robust Bayesian reinforcement learning through tight lower bounds
• A Greedy Approximation of Bayesian Reinforcement Learning with Probably Optimistic Transition Model
• Bayesian Reinforcement Learning via Deep, Sparse Sampling
• Nearly optimal exploration-exploitation decision thresholds