# Combinatorial Bandits Revisited

arXiv: https://arxiv.org/abs/1502.03475 · HTML: https://mlsanity.com/paper/1502.03475/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2015.

## Built on by (most cited first, 3 of 3)

- [Sequential Decision Problems with Weak Feedback](https://mlsanity.com/paper/2212.11603/) (2022)
- [Decentralized Smart Charging of Large-Scale EVs using Adaptive Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2307.10704/) (2023)
- [Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits](https://mlsanity.com/paper/2604.14908/) (2026)

## Abstract (arXiv)

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 textscCombEXP, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.