Timezone: »
We study an idealised sequential resource allocation problem. In each time step the learner chooses an allocation of several resource types between a number of tasks. Assigning more resources to a task increases the probability that it is completed. The problem is challenging because the alignment of the tasks to the resource types is unknown and the feedback is noisy. Our main contribution is the new setting and an algorithm with nearly-optimal regret analysis. Along the way we draw connections to the problem of minimising regret for stochastic linear bandits with heteroscedastic noise. We also present some new results for stochastic linear bandits on the hypercube that significantly out-performs existing work, especially in the sparse case.
Author Information
Tor Lattimore (University of Alberta)
Yacov Crammer (Technion)
Csaba Szepesvari (University of Alberta)
More from the Same Authors
-
2023 Poster: Context-lumpable stochastic bandits »
Chung-Wei Lee · Qinghua Liu · Yasin Abbasi Yadkori · Chi Jin · Tor Lattimore · Csaba Szepesvari -
2023 Poster: Probabilistic Inference in Reinforcement Learning Done Right »
Jean Tarbouriech · Tor Lattimore · Brendan O'Donoghue -
2022 Poster: Finite Sample Analysis Of Dynamic Regression Parameter Learning »
Mark Kozdoba · Edward Moroshko · Shie Mannor · Yacov Crammer -
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: Efficient Loss-Based Decoding on Graphs for Extreme Classification »
Itay Evron · Edward Moroshko · Yacov Crammer -
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: Rotting Bandits »
Nir Levine · Yacov Crammer · Shie Mannor -
2017 Poster: Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning »
Christoph Dann · Tor Lattimore · Emma Brunskill -
2017 Poster: Multi-view Matrix Factorization for Linear Dynamical System Estimation »
Mahdi Karami · Martha White · Dale Schuurmans · Csaba Szepesvari -
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 -
2014 Poster: Learning Multiple Tasks in Parallel with a Shared Annotator »
Haim Cohen · Yacov Crammer -
2014 Poster: Bounded Regret for Finite-Armed Structured Bandits »
Tor Lattimore · Remi Munos -
2013 Workshop: Resource-Efficient Machine Learning »
Yevgeny Seldin · Yasin Abbasi Yadkori · Yacov Crammer · Ralf Herbrich · Peter Bartlett -
2012 Workshop: Multi-Trade-offs in Machine Learning »
Yevgeny Seldin · Guy Lever · John Shawe-Taylor · Nicolò Cesa-Bianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett -
2012 Poster: Volume Regularization for Binary Classification »
Yacov Crammer · Tal Wagner -
2012 Spotlight: Volume Regularization for Binary Classification »
Yacov Crammer · Tal Wagner -
2012 Poster: Learning Multiple Tasks using Shared Hypotheses »
Yacov Crammer · Yishay Mansour -
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò Cesa-Bianchi · Francois Laviolette · John Shawe-Taylor -
2010 Poster: Learning via Gaussian Herding »
Yacov Crammer · Daniel Lee -
2010 Poster: New Adaptive Algorithms for Online Classification »
Francesco Orabona · Yacov Crammer -
2009 Workshop: Advances in Ranking »
Shivani Agarwal · Chris J Burges · Yacov Crammer -
2009 Poster: Adaptive Regularization of Weight Vectors »
Yacov Crammer · Alex Kulesza · Mark Dredze -
2009 Spotlight: Adaptive Regularization of Weight Vectors »
Yacov Crammer · Alex Kulesza · Mark Dredze -
2008 Session: Oral session 6: Neural Coding »
Yacov Crammer -
2008 Poster: Exact Convex Confidence-Weighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira -
2008 Spotlight: Exact Convex Confidence-Weighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira -
2007 Poster: Learning Bounds for Domain Adaptation »
John Blitzer · Yacov Crammer · Alex Kulesza · Fernando Pereira · Jennifer Wortman Vaughan -
2006 Poster: Learning from Multiple Sources »
Yacov Crammer · Michael Kearns · Jennifer Wortman Vaughan -
2006 Poster: Analysis of Representations for Domain Adaptation »
John Blitzer · Shai Ben-David · Yacov Crammer · Fernando Pereira