Fetching the paper…
Reading the bibliography…
We consider the development of adaptive, instance-dependent algorithms for interactive decision making (bandits, reinforcement learning, and beyond) that, rather than only performing well in the worst case, adapt to favorable properties of real-world instances for improved performance.
Asymptotically efficient adaptive allocation rules
Tze Leung Lai and Herbert Robbins · 1985
Earlier work this paper cites.
Asymptotically efficient adaptive allocation schemes for controlled markov chains: Finite parameter space
Rajeev Agrawal, Demosthenis Teneketzis, and Venkatachalam Anantharam · 1988
Earlier work this paper cites.
Optimal adaptive policies for sequential allocation problems
Apostolos N Burnetas and Michael N Katehakis · 1996
Earlier work this paper cites.
Asymptotically efficient adaptive choice of control laws in controlled Markov chains
Todd L Graves and Tze Leung Lai · 1997
Earlier work this paper cites.
An asymptotic property of model selection criteria
Yuhong Yang and Andrew R Barron · 1998
Earlier work this paper cites.
Finite-time analysis of the multiarmed bandit problem
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer · 2002
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Sham Machandranath Kakade · 2003
Earlier work this paper cites.
Hannan Consistency in On-Line Learning in Case of Unbounded Losses Under Partial Monitoring , pages 229–243
Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák · 2006
Earlier work this paper cites.
Stochastic linear optimization under bandit feedback
Varsha Dani, Thomas P Hayes, and Sham M Kakade · 2008
Earlier work this paper cites.
Minimax policies for adversarial and stochastic bandits
Jean-Yves Audibert and Sébastien Bubeck · 2009
Earlier work this paper cites.
Improved algorithms for linear stochastic bandits
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári · 2011
Earlier work this paper cites.
Better algorithms for benign bandits
Elad Hazan and Satyen Kale · 2011
Earlier work this paper cites.
A variant of azuma’s inequality for martingales with subgaussian tails
Ohad Shamir · 2011
Earlier work this paper cites.
Eluder dimension and the sample complexity of optimistic exploration
Daniel Russo and Benjamin Van Roy · 2013
Earlier work this paper cites.
lil’ucb: An optimal exploration algorithm for multi-armed bandits
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck · 2014
Earlier work this paper cites.
Lipschitz bandits: Regret lower bound and optimal algorithms
Stefan Magureanu, Richard Combes, and Alexandre Proutiere · 2014
Earlier work this paper cites.
Regret lower bound and optimal algorithm in finite stochastic partial monitoring
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa · 2015
Earlier work this paper cites.
Continuous control with deep reinforcement learning
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra · 2015
Earlier work this paper cites.
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Earlier work this paper cites.
Learning in games: Robustness of fast convergence
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos · 2016
Earlier work this paper cites.
Optimal best arm identification with fixed confidence
Aurélien Garivier and Emilie Kaufmann · 2016
Earlier work this paper cites.
On explore-then-commit strategies
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann · 2016
Earlier work this paper cites.
On the complexity of best-arm identification in multi-armed bandit models
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier · 2016
Earlier work this paper cites.
On lower bounds for regret in reinforcement learning
Ian Osband and Benjamin Van Roy · 2016
Earlier work this paper cites.
Simple bayesian algorithms for best arm identification
Daniel Russo · 2016
Earlier work this paper cites.
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al · 2016
Cited alongside, same era.
Nearly instance optimal sample complexity bounds for top-k arm selection
Lijie Chen, Jian Li, and Mingda Qiao · 2017
Cited alongside, same era.
Minimal exploration in structured stochastic bandits
Richard Combes, Stefan Magureanu, and Alexandre Proutiere · 2017
Cited alongside, same era.
Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning
Christoph Dann, Tor Lattimore, and Emma Brunskill · 2017
Cited alongside, same era.
Contextual decision processes with low Bellman rank are PAC-learnable
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2017
Cited alongside, same era.
Adaptive exploration in linear contextual bandit
Botao Hao, Tor Lattimore, and Csaba Szepesvari · 2020
Later among the works it cites.
Crush optimism with pessimism: Structured bandits beyond asymptotic optimality
Kwang-Sung Jun and Chicheng Zhang · 2020
Later among the works it cites.
An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits
Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al · 2020
Later among the works it cites.
An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits
Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric · 2020
Later among the works it cites.
Optimal learning for structured bandits
Bart PG Van Parys and Negin Golrezaei · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Tor Lattimore and Csaba Szepesvari · 2017
Cited alongside, same era.
The simulator: Understanding adaptive sampling in the moderate-confidence regime
Max Simchowitz, Kevin Jamieson, and Benjamin Recht · 2017
Cited alongside, same era.
Sparsity, variance and curvature in multi-armed bandits
Sébastien Bubeck, Michael Cohen, and Yuanzhi Li · 2018
Cited alongside, same era.
Refining the confidence level for optimistic bandit strategies
Tor Lattimore · 2018
Cited alongside, same era.
Exploration in structured reinforcement learning
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos · 2018
Cited alongside, same era.
Learning to optimize via information-directed sampling
Daniel Russo and Benjamin Van Roy · 2018
Cited alongside, same era.
More adaptive algorithms for adversarial bandits
Chen-Yu Wei and Haipeng Luo · 2018
Cited alongside, same era.
Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang · 2020
Later among the works it cites.
Adaptive sampling for best policy identification in markov decision processes
Aymen Al Marjani and Alexandre Proutiere · 2021
Later among the works it cites.
Navigating to the best policy in markov decision processes
Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere · 2021
Later among the works it cites.
Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert · 2021
Later among the works it cites.
Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko · 2021
Later among the works it cites.
Bilinear classes: A structural framework for provable generalization in RL
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang · 2021
Later among the works it cites.
The statistical complexity of interactive decision making
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin · 2021
Later among the works it cites.
Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi · 2021
Later among the works it cites.
Asymptotically optimal information-directed sampling
Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári · 2021
Later among the works it cites.
A fully problem-dependent regret lower bound for finite-horizon mdps
Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric · 2021
Later among the works it cites.
Task-optimal exploration in linear dynamical systems
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson · 2021
Later among the works it cites.
Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon
Zihan Zhang, Xiangyang Ji, and Simon Du · 2021
Later among the works it cites.
Nearly minimax optimal reinforcement learning for linear mixture markov decision processes
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari · 2021
Later among the works it cites.
Fan Chen, Song Mei, and Yu Bai · 2022
Later among the works it cites.
Asymptotic instance-optimal algorithms for interactive decision making
Kefan Dong and Tengyu Ma · 2022
Later among the works it cites.
Near instance-optimal pac reinforcement learning for deterministic mdps
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann · 2022
Later among the works it cites.
Instance-dependent near-optimal policy identification in linear mdps via online experiment design
Andrew Wagenmaker and Kevin Jamieson · 2022
Later among the works it cites.
Leveraging offline data in online reinforcement learning
Andrew Wagenmaker and Aldo Pacchiano · 2022
Later among the works it cites.
Tight guarantees for interactive decision making with the decision-estimation coefficient
Dylan J. Foster, Noah Golowich, and Yanjun Han · 2023
Closest in time.