Fractional Moments on Bandit Problems

Ananda Narayanan B, Balaraman Ravindran
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:597-604, 2011.

Abstract

Reinforcement learning addresses the dilemma between exploration to find profitable actions and exploitation to act according to the best observations already made. Bandit problems are one such class of problems in stateless environments that represent this explore/exploit situation. We propose a learning algorithm for bandit problems based on fractional expectation of rewards acquired. The algorithm is theoretically shown to converge on an eta-optimal arm and achieve O(n) sample complexity. Experimental results show the algorithm incurs substantially lower regrets than parameter-optimized eta-greedy and SoftMax approaches and other low sample complexity state-of-the-art techniques.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-b11a, title = {Fractional Moments on Bandit Problems}, author = {B, Ananda Narayanan and Ravindran, Balaraman}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {597--604}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/b11a/b11a.pdf}, url = {https://proceedings.mlr.press/r9/b11a.html}, abstract = {Reinforcement learning addresses the dilemma between exploration to find profitable actions and exploitation to act according to the best observations already made. Bandit problems are one such class of problems in stateless environments that represent this explore/exploit situation. We propose a learning algorithm for bandit problems based on fractional expectation of rewards acquired. The algorithm is theoretically shown to converge on an eta-optimal arm and achieve O(n) sample complexity. Experimental results show the algorithm incurs substantially lower regrets than parameter-optimized eta-greedy and SoftMax approaches and other low sample complexity state-of-the-art techniques.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fractional Moments on Bandit Problems %A Ananda Narayanan B %A Balaraman Ravindran %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-b11a %I PMLR %P 597--604 %U https://proceedings.mlr.press/r9/b11a.html %V R9 %X Reinforcement learning addresses the dilemma between exploration to find profitable actions and exploitation to act according to the best observations already made. Bandit problems are one such class of problems in stateless environments that represent this explore/exploit situation. We propose a learning algorithm for bandit problems based on fractional expectation of rewards acquired. The algorithm is theoretically shown to converge on an eta-optimal arm and achieve O(n) sample complexity. Experimental results show the algorithm incurs substantially lower regrets than parameter-optimized eta-greedy and SoftMax approaches and other low sample complexity state-of-the-art techniques. %Z Reissued by PMLR on 04 October 2026.
APA
B, A.N. & Ravindran, B.. (2011). Fractional Moments on Bandit Problems. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:597-604 Available from https://proceedings.mlr.press/r9/b11a.html. Reissued by PMLR on 04 October 2026.

Related Material