Near-Optimal BRL using Optimistic Local Transitions

Abstract

Model-based Bayesian Reinforcement Learning (BRL) allows a found formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces BOLT, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze BOLT's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.

ICML2012

References in corpus (1)

• A Bayesian Sampling Approach to Exploration in Reinforcement Learning

Cited by in corpus (6)

• Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models
• Bayesian Reinforcement Learning: A Survey
• Cover Tree Bayesian Reinforcement Learning
• Variational Bayesian Reinforcement Learning with Regret Bounds
• A General Framework for Interacting Bayes-Optimally with Self-Interested Agents using Arbitrary Parametric Model and Model Prior
• A Greedy Approximation of Bayesian Reinforcement Learning with Probably Optimistic Transition Model