Fighting Bandits with a New Kind of Smoothness

2015/12/14 by Abernethy, Jacob, Lee, Chansoo, Tewari, Ambuj · 5 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1512.04152

Abstract

We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularization via the Tsallis entropy, which includes EXP3 as a special case, achieves the Θ(√(TN)) minimax regret. Second, we show that a wide class of perturbation methods achieve a near-optimal regret as low as O(√(TN log N)) if the perturbation distribution has a bounded hazard rate. For example, the Gumbel, Weibull, Frechet, Pareto, and Gamma distributions all satisfy this key property.

Cited by

• Robust equilibria in continuous games: From strategic to dynamic robustness
• The Hidden Cost of Approximation in Online Mirror Descent
• Self-Concordant Perturbations for Linear Bandits
• Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
• Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems

Related

• Fighting Contextual Bandits with Stochastic Smoothing
• Beyond the Hazard Rate: More Perturbation Algorithms for Adversarial Multi-armed Bandits
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• On the Optimality of Perturbations in Stochastic and Adversarial\n Multi-armed Bandit Problems
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits