Timezone: »

Combinatorial Bandits Revisited
Richard Combes · M. Sadegh Talebi · Alexandre Proutiere · marc lelarge

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #96 #None

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.

Author Information

Richard Combes (Supelec)

I am currently an assistant professor in Centrale-Supelec in the Telecommunication department. I received the Engineering Degree from Telecom Paristech (2008), the Master Degree in Mathematics from university of Paris VII (2009) and the Ph.D. degree in Mathematics from university of Paris VI (2013). I was a visiting scientist at INRIA (2012) and a post-doc in KTH (2013). I received the best paper award at CNSM 2011. My current research interests are machine learning, networks and probability.

M. Sadegh Talebi (KTH Royal Inst. of Technology)
Alexandre Proutiere (KTH)
marc lelarge (INRIA - ENS)

More from the Same Authors