Sharp Dichotomies for Regret Minimization in Metric Spaces

Details Sharp Dichotomies for Regret Minimization in Metric Spaces Sharp Dichotomies for Regret Minimization in Metric Spaces

2009-11-06

arxiv.org/abs/0911.1174v1

Computer Science

Data Structures and Algorithms

Full version of a paper in ACM-SIAM SODA 2010

Scientific paper

The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on the difference in expected payoff between certain pairs of strategies. Classical results of (Lai and Robbins 1985) and (Auer et al. 2002) imply a logarithmic regret bound for the Lipschitz MAB problem on finite metric spaces. Recent results on continuum-armed bandit problems and their generalizations imply lower bounds of $\sqrt{t}$, or stronger, for many infinite metric spaces such as the unit interval. Is this dichotomy universal? We prove that the answer is yes: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in \omega(\log t)$, or bounded below by any $g\in o(\sqrt{t})$. Perhaps surprisingly, this dichotomy does not coincide with the distinction between finite and infinite metric spaces; instead it depends on whether the completion of the metric space is compact and countable. Our proof connects upper and lower bound techniques in online learning with classical topological notions such as perfect sets and the Cantor-Bendixson theorem. Among many other results, we show a similar dichotomy for the "full-feedback" (a.k.a., "best-expert") version.

Affiliated with

Also associated with

No associations

Rating

Sharp Dichotomies for Regret Minimization in Metric Spaces 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 Sharp Dichotomies for Regret Minimization in Metric Spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Dichotomies for Regret Minimization in Metric Spaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-390713