Timezone: »
Poster
Bounded Regret for Finite-Armed Structured Bandits
Tor Lattimore · Remi Munos
We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.
Author Information
Tor Lattimore (DeepMind)
Remi Munos (Google DeepMind)
More from the Same Authors
-
2022 Poster: Regret Bounds for Information-Directed Reinforcement Learning »
Botao Hao · Tor Lattimore -
2018 Poster: TopRank: A practical algorithm for online stochastic ranking »
Tor Lattimore · Branislav Kveton · Shuai Li · Csaba Szepesvari -
2018 Poster: Single-Agent Policy Tree Search With Guarantees »
Laurent Orseau · Levi Lelis · Tor Lattimore · Theophane Weber -
2017 Poster: A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis »
Tor Lattimore -
2017 Poster: Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning »
Christoph Dann · Tor Lattimore · Emma Brunskill -
2017 Spotlight: Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning »
Christoph Dann · Tor Lattimore · Emma Brunskill -
2016 Poster: Refined Lower Bounds for Adversarial Bandits »
Sébastien Gerchinovitz · Tor Lattimore -
2016 Poster: Causal Bandits: Learning Good Interventions via Causal Inference »
Finnian Lattimore · Tor Lattimore · Mark Reid -
2016 Poster: Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities »
Ruitong Huang · Tor Lattimore · András György · Csaba Szepesvari -
2016 Poster: On Explore-Then-Commit strategies »
Aurélien Garivier · Tor Lattimore · Emilie Kaufmann -
2015 Poster: The Pareto Regret Frontier for Bandits »
Tor Lattimore -
2015 Poster: Linear Multi-Resource Allocation with Semi-Bandit Feedback »
Tor Lattimore · Yacov Crammer · Csaba Szepesvari -
2015 Poster: Black-box optimization of noisy functions with unknown smoothness »
Jean-Bastien Grill · Michal Valko · Remi Munos · Remi Munos -
2014 Poster: Active Regression by Stratification »
Sivan Sabato · Remi Munos -
2014 Poster: Best-Arm Identification in Linear Bandits »
Marta Soare · Alessandro Lazaric · Remi Munos -
2014 Poster: Efficient learning by implicit exploration in bandit problems with side observations »
Tomáš Kocák · Gergely Neu · Michal Valko · Remi Munos -
2014 Poster: Optimistic Planning in Markov Decision Processes Using a Generative Model »
Balázs Szörényi · Gunnar Kedenburg · Remi Munos -
2013 Workshop: Bayesian Optimization in Theory and Practice »
Matthew Hoffman · Jasper Snoek · Nando de Freitas · Michael A Osborne · Ryan Adams · Sebastien Bubeck · Philipp Hennig · Remi Munos · Andreas Krause -
2013 Poster: Thompson Sampling for 1-Dimensional Exponential Family Bandits »
Nathaniel Korda · Emilie Kaufmann · Remi Munos -
2013 Poster: Aggregating Optimistic Planning Trees for Solving Markov Decision Processes »
Gunnar Kedenburg · Raphael Fonteneau · Remi Munos -
2012 Poster: Bandit Algorithms boost Brain Computer Interfaces for motor-task selection of a brain-controlled button »
Joan Fruitet · Alexandra Carpentier · Remi Munos · Maureen Clerc -
2012 Poster: Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions »
Alexandra Carpentier · Remi Munos -
2012 Poster: Risk-Aversion in Multi-armed Bandits »
Amir Sani · Alessandro Lazaric · Remi Munos -
2011 Poster: Finite Time Analysis of Stratified Sampling for Monte Carlo »
Alexandra Carpentier · Remi Munos -
2011 Poster: Selecting the State-Representation in Reinforcement Learning »
Odalric-Ambrym Maillard · Remi Munos · Daniil Ryabko -
2011 Poster: Sparse Recovery with Brownian Sensing »
Alexandra Carpentier · Odalric-Ambrym Maillard · Remi Munos -
2011 Session: Spotlight Session 2 »
Remi Munos -
2011 Session: Oral Session 1 »
Remi Munos -
2011 Poster: Optimistic Optimization of Deterministic Functions »
Remi Munos -
2011 Poster: Speedy Q-Learning »
Mohammad Gheshlaghi Azar · Remi Munos · Mohammad Ghavamzadeh · Hilbert J Kappen -
2010 Spotlight: LSTD with Random Projections »
Mohammad Ghavamzadeh · Alessandro Lazaric · Odalric-Ambrym Maillard · Remi Munos -
2010 Poster: LSTD with Random Projections »
Mohammad Ghavamzadeh · Alessandro Lazaric · Odalric-Ambrym Maillard · Remi Munos -
2010 Poster: Scrambled Objects for Least-Squares Regression »
Odalric-Ambrym Maillard · Remi Munos -
2010 Poster: Error Propagation for Approximate Policy and Value Iteration »
Amir-massoud Farahmand · Remi Munos · Csaba Szepesvari -
2009 Poster: Sensitivity analysis in HMMs with application to likelihood maximization »
Pierre-Arnaud Coquelin · Romain Deguest · Remi Munos -
2009 Poster: Compressed Least-Squares Regression »
Odalric-Ambrym Maillard · Remi Munos -
2008 Poster: Online Optimization in X-Armed Bandits »
Sebastien Bubeck · Remi Munos · Gilles Stoltz · Csaba Szepesvari -
2008 Poster: Algorithms for Infinitely Many-Armed Bandits »
Yizao Wang · Jean-Yves Audibert · Remi Munos -
2008 Spotlight: Algorithms for Infinitely Many-Armed Bandits »
Yizao Wang · Jean-Yves Audibert · Remi Munos -
2008 Poster: Particle Filter-based Policy Gradient in POMDPs »
Pierre-Arnaud Coquelin · Romain Deguest · Remi Munos -
2007 Poster: Fitted Q-iteration in continuous action-space MDPs »
Remi Munos · András Antos · Csaba Szepesvari