Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously

Abstract

We develop the first general semi-bandit algorithm that simultaneously achieves $\mathcal{O}(\log T)$ regret for stochastic environments and $\mathcal{O}(\sqrt{T})$ regret for adversarial environments without knowledge of the regime or the number of rounds $T$. The leading problem-dependent constants of our bounds are not only optimal in some worst-case sense studied previously, but also optimal for two concrete instances of semi-bandit problems. Our algorithm and analysis extend the recent work of (Zimmert & Seldin, 2019) for the special case of multi-armed bandit, but importantly requires a novel hybrid regularizer designed specifically for semi-bandit. Experimental results on synthetic data show that our algorithm indeed performs well uniformly over different environments. We finally provide a preliminary extension of our results to the full bandit feedback.

Cited by in corpus (13)

• An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
• Exploration by Optimisation in Partial Monitoring
• Corruption-robust exploration in episodic reinforcement learning
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Learning-based decentralized offloading decision making in an adversarial environment
• Corralling Stochastic Bandit Algorithms
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• No-regret Learning in Price Competitions under Consumer Reference Effects
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Memory-Constrained No-Regret Learning in Adversarial Bandits
• Best-of-Both-Worlds Algorithms for Partial Monitoring
• Combinatorial Bandits under Strategic Manipulations