Timezone: »

 
Poster
Minimal Exploration in Structured Stochastic Bandits
Richard Combes · Stefan Magureanu · Alexandre Proutiere

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #4
in Posters Tue »

This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, lipschitz, unimodal, combinatorial, dueling,...) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of ``optimism in the face of uncertainty'' or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling

Keywords: Bandit Algorithms · Online Learning · Reinforcement Learning
[ Paper] 

Author Information

Richard Combes (Centrale-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.

Stefan Magureanu (KTH)
Alexandre Proutiere (KTH)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors