Fetching the paper…
Reading the bibliography…
Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer $\Omega(\sqrt{SAT})$ regret on some MDP, where $T$ is the elapsed time and $S$ and $A$ are the cardinalities of the state and action spaces.
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
William Thompson · 1933
Earlier work this paper cites.
Optimal adaptive policies for Markov decision processes
Apostolos Burnetas and Michael Katehakis · 1997
Earlier work this paper cites.
Learning dynamic bayesian networks
Zoubin Ghahramani · 1998
Earlier work this paper cites.
Efficient reinforcement learning in factored MDPs
Michael Kearns and Daphne Koller · 1999
Earlier work this paper cites.
Stochastic dynamic programming with factored representations
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt · 2000
Earlier work this paper cites.
A Bayesian framework for reinforcement learning
Malcom Strens · 2000
Earlier work this paper cites.
Policy iteration for factored MDPs
Daphne Koller and Ronald Parr · 2000
Earlier work this paper cites.
Max-norm projections for factored MDPs
Carlos Guestrin, Daphne Koller, and Ronald Parr · 2001
Cited alongside, same era.
Near-optimal reinforcement learning in polynomial time
Michael Kearns and Satinder Singh · 2002
Cited alongside, same era.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Ronen Brafman and Moshe Tennenholtz · 2003
Cited alongside, same era.
Efficient solution algorithms for factored MDPs
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman · 2003
Cited alongside, same era.
Inequalities for the L1 deviation of the empirical distribution
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger · 2003
Cited alongside, same era.
Model-based reinforcement learning in factored-state MDPs
Alexander Strehl · 2007
Cited alongside, same era.
Regal: A regularization based algorithm for reinforcement learning in weakly communicating MDPs
Peter Bartlett and Ambuj Tewari · 2009
Later among the works it cites.
Optimistic initialization and greediness lead to polynomial time learning in factored MDPs
István Szita and András Lőrincz · 2009
Later among the works it cites.
Carlos Diuk, Lihong Li, and Bethany R Leffler · 2009
Later among the works it cites.
Near-optimal regret bounds for reinforcement learning
Thomas Jaksch, Ronald Ortner, and Peter Auer · 2010
Later among the works it cites.
Efficient solutions to factored MDPs with imprecise transition probabilities
Karina Valdivia Delgado, Scott Sanner, and Leliane Nunes De Barros · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Efficient structure learning in factored-state MDPs
Alexander Strehl, Carlos Diuk, and Michael Littman · 2007
Cited alongside, same era.
Scott Sanner and Craig Boutilier · 2012
Later among the works it cites.
(More) Efficient Reinforcement Learning via Posterior Sampling
Ian Osband, Daniel Russo, and Benjamin Van Roy · 2013
Later among the works it cites.