Fetching the paper…
Reading the bibliography…
This work considers the sample and computational complexity of obtaining an $\epsilon$-optimal policy in a discounted Markov Decision Process (MDP), given only access to a generative model.
Zanette, A. and Brunskill, E. (2019) · 1901
Earlier work this paper cites.
Stochastic approximation with cone-contractive operators: Sharp ℓ \ell -infty -bounds for q-learning
Wainwright, M. J. (2019) · 1905
Earlier work this paper cites.
Dynamic programming and stochastic control
Bertsekas, D. P. (1976) · 1976
Earlier work this paper cites.
An upper bound on the loss from approximate optimal-value functions
Singh, S. and Yee, R. (1994) · 1994
Earlier work this paper cites.
Finite-sample convergence rates for q-learning and indirect algorithms
Kearns, M. J. and Singh, S. P. (1999) · 1999
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Kakade, S. M. et al. (2003) · 2003
Earlier work this paper cites.
Pac model-free reinforcement learning
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006) · 2006
Earlier work this paper cites.
Probably approximately correct (PAC) exploration in reinforcement learning
Strehl, A. L. (2007) · 2007
Cited alongside, same era.
Reinforcement learning in finite mdps: Pac analysis
Strehl, A. L., Li, L., and Littman, M. L. (2009) · 2009
Cited alongside, same era.
Near-optimal regret bounds for reinforcement learning
Jaksch, T., Ortner, R., and Auer, P. (2010) · 2010
Cited alongside, same era.
The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
Ye, Y. (2011) · 2011
Cited alongside, same era.
On the sample complexity of reinforcement learning with a generative model
Azar, M. G., Munos, R., and Kappen, B. (2012) · 2012
Cited alongside, same era.
Minimax pac bounds on the sample complexity of reinforcement learning with a generative model
Model-based reinforcement learning and the eluder dimension
Osband, I. and Van Roy, B. (2014) · 2014
Later among the works it cites.
Markov decision processes: discrete stochastic dynamic programming
Puterman, M. L. (2014) · 2014
Later among the works it cites.
Sample complexity of episodic fixed-horizon reinforcement learning
Dann, C. and Brunskill, E. (2015) · 2015
Later among the works it cites.
Minimax regret bounds for reinforcement learning
Azar, M. G., Osband, I., and Munos, R. (2017) · 2017
Later among the works it cites.
Wang, M. (2017) · 2017
Later among the works it cites.
Is q-learning provably efficient?
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018) · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Azar, M. G., Munos, R., and Kappen, H. J. (2013) · 2013
Cited alongside, same era.
Kalathil, D., Borkar, V. S., and Jain, R. (2014) · 2014
Cited alongside, same era.
Near-optimal time and sample complexities for solving markov decision processes with a generative model
Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. (2018a)
Cited in the paper.
Variance reduced value iteration and faster algorithms for solving markov decision processes
Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018b)
Cited in the paper.
Later among the works it cites.