Combinatorial Bandits Revisited
This work addresses combinatorial bandit problems, offering incremental algorithmic improvements for researchers and practitioners in online learning and optimization.
The paper tackles stochastic and adversarial combinatorial multi-armed bandit problems by proposing ESCB for the stochastic setting with improved performance guarantees and practical outperformance, and CombEXP for the adversarial setting with lower computational complexity while matching state-of-the-art regret scaling.
This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the adversarial setting under bandit feedback, we propose \textsc{CombEXP}, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.