Variance-Based Rewards for Approximate Bayesian Reinforcement Learning

Jonathan Sorg, Satinder Singh, Richard Lewis
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:563-570, 2010.

Abstract

The explore–exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; 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, results in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninformative 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-sorg10a, title = {Variance-Based Rewards for Approximate {B}ayesian Reinforcement Learning}, author = {Sorg, Jonathan and Singh, Satinder and Lewis, Richard}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {563--570}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/sorg10a/sorg10a.pdf}, url = {https://proceedings.mlr.press/r8/sorg10a.html}, abstract = {The explore–exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; 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, results in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninformative 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Variance-Based Rewards for Approximate Bayesian Reinforcement Learning %A Jonathan Sorg %A Satinder Singh %A Richard Lewis %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-sorg10a %I PMLR %P 563--570 %U https://proceedings.mlr.press/r8/sorg10a.html %V R8 %X The explore–exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; 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, results in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninformative 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. %Z Reissued by PMLR on 04 October 2026.
APA
Sorg, J., Singh, S. & Lewis, R.. (2010). Variance-Based Rewards for Approximate Bayesian Reinforcement Learning. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:563-570 Available from https://proceedings.mlr.press/r8/sorg10a.html. Reissued by PMLR on 04 October 2026.

Related Material