Fetching the paper…
Reading the bibliography…
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator).
A theoretical analysis of deep Q-learning
Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2019) · 1901
Earlier work this paper cites.
Wainwright, M. J. (2019a) · 1905
Earlier work this paper cites.
Variance-reduced Q-learning is minimax optimal
Wainwright, M. J. (2019b) · 1906
Earlier work this paper cites.
Pananjady, A. and Wainwright, M. J. (2019) · 1909
Earlier work this paper cites.
On the theory of dynamic programming
Bellman, R. (1952) · 1952
Earlier work this paper cites.
Convergence of stochastic iterative dynamic programming algorithms
Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994) · 1994
Earlier work this paper cites.
Asynchronous stochastic approximation and Q-learning
Tsitsiklis, J. N. (1994) · 1994
Earlier work this paper cites.
Linear least-squares algorithms for temporal difference learning
Bradtke, S. J. and Barto, A. G. (1996) · 1996
Earlier work this paper cites.
An analysis of temporal-difference learning with function approximation
Tsitsiklis, J. and Van Roy, B. (1997) · 1997
Earlier work this paper cites.
The asymptotic convergence-rate of Q-learning
Szepesvári, C. (1998) · 1998
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.
Finite-sample analysis of stochastic approximation using smooth convex envelopes
Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2020) · 2002
Earlier work this paper cites.
Finite time analysis of linear two-timescale stochastic approximation with Markovian noise
Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T. (2020) · 2002
Earlier work this paper cites.
A sparse sampling algorithm for near-optimal planning in large Markov decision processes
Kearns, M., Mansour, Y., and Ng, A. Y. (2002) · 2002
Earlier work this paper cites.
Learning rates for Q-learning
Even-Dar, E. and Mansour, Y. (2003) · 2003
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Kakade, S. (2003) · 2003
Earlier work this paper cites.
Is temporal difference learning optimal? an instance-dependent analysis
Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2020) · 2003
Earlier work this paper cites.
On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration
Mou, W., Li, C. J., Wainwright, M. J., Bartlett, P. L., and Jordan, M. I. (2020) · 2004
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.
Algorithms for reinforcement learning
Szepesvári, C. (2010) · 2010
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.
Error bounds for constant step-size Q-learning
Beck, C. L. and Srikant, R. (2012) · 2012
Cited alongside, same era.
PAC bounds for discounted MDPs
Lattimore, T. and Hutter, M. (2012) · 2012
Cited alongside, same era.
Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
Azar, M. G., Munos, R., and Kappen, H. J. (2013) · 2013
Cited alongside, same era.
On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
Finite-time error bounds for linear stochastic approximation and TD learning
Srikant, R. and Ying, L. (2019) · 2019
Later among the works it cites.
The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint
Tu, S. and Recht, B. (2019) · 2019
Later among the works it cites.
Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time
Wang, M. (2019) · 2019
Later among the works it cites.
Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples
Xu, T., Zou, S., and Liang, Y. (2019) · 2019
Later among the works it cites.
Sample-optimal parametric Q-learning using linearly additive features
Yang, L. and Wang, M. (2019) · 2019
Later among the works it cites.
Model-based reinforcement learning with a generative model is minimax optimal
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
El Karoui, N. (2015) · 2015
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Azar, M. G., Osband, I., and Munos, R. (2017) · 2017
Cited alongside, same era.
Dynamic programming and optimal control (4th edition)
Bertsekas, D. P. (2017) · 2017
Cited alongside, same era.
A finite time analysis of temporal difference learning with linear function approximation
Bhandari, J., Russo, D., and Singal, R. (2018) · 2018
Cited alongside, same era.
Finite sample analyses for TD(0) with function approximation
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. (2018) · 2018
Cited alongside, same era.
Is Q-learning provably efficient?
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018) · 2018
Cited alongside, same era.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
Lakshminarayanan, C. and Szepesvari, C. (2018) · 2018
Cited alongside, same era.
Agarwal, A., Kakade, S., and Yang, L. F. (2020) · 2020
Closest in time.
Provably efficient reinforcement learning with linear function approximation
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020) · 2020
Closest in time.
Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution
Ma, C., Wang, K., Chi, Y., and Chen, Y. (2020) · 2020
Closest in time.
Finite-time analysis of asynchronous stochastic approximation and Q-learning
Qu, G. and Wierman, A. (2020) · 2020
Closest in time.
A finite-time analysis of Q-learning with neural network function approximation
Xu, P. and Gu, Q. (2020) · 2020
Closest in time.
Spectral methods for data science: A statistical perspective
Chen, Y., Chi, Y., Fan, J., and Ma, C. (2021) · 2021
Closest in time.
Minimax sample complexity for turn-based stochastic game
Cui, Q. and Yang, L. F. (2021) · 2021
Closest in time.
Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. (2021) · 2021
Closest in time.
Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative model
Wang, B., Yan, Y., and Fan, J. (2021) · 2021
Closest in time.
Inference for heteroskedastic PCA with missing data
Yan, Y., Chen, Y., and Fan, J. (2021) · 2021
Closest in time.
Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning
Yin, M., Bai, Y., and Wang, Y.-X. (2021) · 2021
Closest in time.
Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity
Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022) · 2022
Closest in time.
Is Q-learning minimax optimal? a tight sample complexity analysis
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. (2023) · 2023
Closest in time.