Variance-based rewards for approximate Bayesian reinforcement learning
Jonathan Sorg, Satinder Pal Singh, Richard L. Lewis · 2010
The explore–exploit dilemma is one of the central challenges in Reinforcement Learn-ing (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over envi-ronments; however, full Bayesian planning is intractable. Planning with the mean MDP is a common myopic approximation of Bayesian planning. We derive a novel reward bonus that is a function of the posterior distribution over environments, which, when added to the reward in planning with the mean MDP, re-sults in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninfor-mative or unstructured prior, unlike existing methods, our method can exploit structured priors. We prove that our method results in a polynomial sample complexity and empirically demonstrate its advantages in a structured exploration task. 1