Combinatorial Bandits Revisited
Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, marc lelarge
Abstract
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 CombEXP, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.
BibTeX
@inproceedings{NIPS2015_0ce2ffd2,
author = {Combes, Richard and Talebi Mazraeh Shahi, Mohammad Sadegh and Proutiere, Alexandre and lelarge, marc},
booktitle = {Advances in Neural Information Processing Systems},
editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Combinatorial Bandits Revisited},
url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/0ce2ffd21fc958d9ef0ee9ba5336e357-Paper.pdf},
volume = {28},
year = {2015}
}