Towards minimax policies for online linear optimization with bandit feedback

Abstract

We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $\sqrt{dn\log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $\sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d\sqrt{n\log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d\sqrt{n}$ regret, thus improving by a factor $\sqrt{d\log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $\sqrt{dn\log n}$ regret, again shaving off an extraneous $\sqrt{d}$ compared to previous works.

References in corpus (2)

• Regularization Techniques for Learning with Matrices
• Minimax Policies for Combinatorial Prediction Games

Cited by in corpus (22)

• Online Learning: A Comprehensive Survey
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• The Many Faces of Exponential Weights in Online Learning
• The Price of Differential Privacy For Online Learning
• An optimal algorithm for bandit convex optimization
• The entropic barrier: a simple and optimal universal self-concordant barrier
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• An approach to the distributionally robust shortest path problem
• Semiparametric Contextual Bandits
• Bandit Convex Optimization in Non-stationary Environments
• Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
• Bandit Convex Optimization: sqrt{T} Regret in One Dimension
• Online learning in MDPs with linear function approximation and bandit feedback
• A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
• Corralling a Band of Bandit Algorithms
• Regret in Online Combinatorial Optimization
• Online learning with kernel losses
• Minimax Regret for Bandit Convex Optimisation of Ridge Functions
• On the Complexity of Bandit Linear Optimization
• Bandit Online Optimization Over the Permutahedron
• Online Markov Decision Processes with Aggregate Bandit Feedback
• An efficient algorithm for learning with semi-bandit feedback