Pure Exploration for Multi-Armed Bandit Problems

Details Pure Exploration for Multi-Armed Bandit Problems Pure Exploration for Multi-Armed Bandit Problems

2008-02-19

arxiv.org/abs/0802.2655v6

Mathematics

Statistics Theory

Scientific paper

We consider the framework of stochastic multi-armed bandit problems and study the possibilities and limitations of forecasters that perform an on-line exploration of the arms. These forecasters are assessed in terms of their simple regret, a regret notion that captures the fact that exploration is only constrained by the number of available rounds (not necessarily known in advance), in contrast to the case when the cumulative regret is considered and when exploitation needs to be performed at the same time. We believe that this performance criterion is suited to situations when the cost of pulling an arm is expressed in terms of resources rather than rewards. We discuss the links between the simple and the cumulative regret. One of the main results in the case of a finite number of arms is a general lower bound on the simple regret of a forecaster in terms of its cumulative regret: the smaller the latter, the larger the former. Keeping this result in mind, we then exhibit upper bounds on the simple regret of some forecasters. The paper ends with a study devoted to continuous-armed bandit problems; we show that the simple regret can be minimized with respect to a family of probability distributions if and only if the cumulative regret can be minimized for it. Based on this equivalence, we are able to prove that the separable metric spaces are exactly the metric spaces on which these regrets can be minimized with respect to the family of all probability distributions with continuous mean-payoff functions.

Affiliated with

Also associated with

No associations

Rating

Pure Exploration for Multi-Armed Bandit Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pure Exploration for Multi-Armed Bandit Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pure Exploration for Multi-Armed Bandit Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338723