2009 ExplorationExploitationTradeoff

• (Audibert et al., 2009) ⇒ Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. (2009). “Exploration-exploitation Tradeoff Using Variance Estimates in Multi-armed Bandits.” In: Theoretical Computer Science Journal, 410(19). doi:10.1016/j.tcs.2009.01.016

Subject Headings: Upper Confidence Bound Algorithm, Upper Confidence Bound Bandit Algorithm.

Cited By

• http://scholar.google.com/scholar?q=%222009%22+Exploration-exploitation+Tradeoff+Using+Variance+Estimates+in+Multi-armed+Bandits
• http://dl.acm.org/citation.cfm?id=1519541.1519712&preflayout=flat#citedby

Quotes

Abstract

Algorithms based on upper confidence bounds for balancing exploration and exploitation are gaining popularity since they are easy to implement, efficient and effective. This paper considers a variant of the basic algorithm for the stochastic, multi-armed bandit problem that takes into account the empirical variance of the different arms. In earlier experimental works, such algorithms were found to outperform the competing algorithms. We provide the first analysis of the expected regret for such algorithms. As expected, our results show that the algorithm that uses the variance estimates has a major advantage over its alternatives that do not use such estimates provided that the variances of the payoffs of the suboptimal arms are low. We also prove that the regret concentrates only at a polynomial rate. This holds for all the upper confidence bound based algorithms and for all bandit problems except those special ones where with probability one the payoff obtained by pulling the optimal arm is larger than the expected payoff for the second best arm. Hence, although upper confidence bound bandit algorithms achieve logarithmic expected regret rates, they might not be suitable for a risk-averse decision maker. We illustrate some of the results by computer simulations.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ExplorationExploitationTradeoff	Csaba Szepesvári Jean-Yves Audibert Rémi Munos			Exploration-exploitation Tradeoff Using Variance Estimates in Multi-armed Bandits				10.1016/j.tcs.2009.01.016		2009