Fetching the paper…
Reading the bibliography…
While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL) -- the complexity of learning on the "worst-case" instance -- such measures of complexity often do not capture the true difficulty of learning.
An algorithm for quadratic programming
Frank, M. and Wolfe, P · 1956
Earlier work this paper cites.
Frequentist regret bounds for randomized least-squares value iteration
Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A · 1964
Earlier work this paper cites.
On tail probabilities for martingales
Freedman, D. A · 1975
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Baird, L · 1995
Earlier work this paper cites.
Linear least-squares algorithms for temporal difference learning
Bradtke, S. J. and Barto, A. G · 1996
Earlier work this paper cites.
Finite-sample convergence rates for q-learning and indirect algorithms
Kearns, M. and Singh, S · 1998
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y · 1999
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, R. I. and Tennenholtz, M · 2002
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Kakade, S. M · 2003
Earlier work this paper cites.
Optimal design of experiments
Pukelsheim, F · 2006
Earlier work this paper cites.
Mechanism design via differential privacy
McSherry, F. and Talwar, K · 2007
Earlier work this paper cites.
Q-learning with linear function approximation
Melo, F. S. and Ribeiro, M. I · 2007
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R · 2010
Earlier work this paper cites.
Best-arm identification in linear bandits
Soare, M., Lazaric, A., and Munos, R · 2014
Earlier work this paper cites.
Sample complexity of episodic fixed-horizon reinforcement learning
Dann, C. and Brunskill, E · 2015
Earlier work this paper cites.
On the complexity of best-arm identification in multi-armed bandit models
Kaufmann, E., Cappé, O., and Garivier, A · 2016
Earlier work this paper cites.
Contextual decision processes with low bellman rank are pac-learnable
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E · 2017
Earlier work this paper cites.
Is q-learning provably efficient?
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I · 2018
Earlier work this paper cites.
Exploration in structured reinforcement learning
Ok, J., Proutiere, A., and Tranos, D · 2018
Earlier work this paper cites.
Policy certificates: Towards accountable reinforcement learning
Dann, C., Li, L., Wei, W., and Brunskill, E · 2019
Cited alongside, same era.
Is a good representation sufficient for sample efficient reinforcement learning?
Du, S. S., Kakade, S. M., Wang, R., and Yang, L. F · 2019
Cited alongside, same era.
Sequential experimental design for transductive linear bandits
Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L · 2019
Cited alongside, same era.
Provably efficient maximum entropy exploration
Hazan, E., Kakade, S., Singh, K., and Van Soest, A · 2019
Cited alongside, same era.
Non-asymptotic gap-dependent regret bounds for tabular mdps
Simchowitz, M. and Jamieson, K · 2019
Cited alongside, same era.
Nearly minimax optimal reinforcement learning for linear mixture markov decision processes
Zhou, D., Gu, Q., and Szepesvari, C · 2020
Later among the works it cites.
Agarwal, N., Chaudhuri, S., Jain, P., Nagaraj, D., and Netrapalli, P · 2021
Later among the works it cites.
Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning
Dann, C., Marinov, T. V., Mohri, M., and Zimmert, J · 2021
Later among the works it cites.
Bilinear classes: A structural framework for provable generalization in rl
Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A · 2019
Cited alongside, same era.
Sample-optimal parametric q-learning using linearly additive features
Yang, L. and Wang, M · 2019
Cited alongside, same era.
Almost horizon-free structure-aware best policy identification with a generative model
Zanette, A., Kochenderfer, M. J., and Brunskill, E · 2019
Cited alongside, same era.
Model-based reinforcement learning with value-targeted regression
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L · 2020
Cited alongside, same era.
Optimal approximation-smoothness tradeoffs for soft-max functions
Epasto, A., Mahdian, M., Mirrokni, V., and Zampetakis, E · 2020
Cited alongside, same era.
Logarithmic regret for reinforcement learning with linear function approximation
He, J., Zhou, D., and Gu, Q · 2020
Cited alongside, same era.
Model-based reinforcement learning with value-targeted regression
Jia, Z., Yang, L., Szepesvari, C., and Wang, M · 2020
Cited alongside, same era.
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A · 2021
Later among the works it cites.
Online sparse reinforcement learning
Hao, B., Lattimore, T., Szepesvári, C., and Wang, M · 2021
Later among the works it cites.
Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms
Jin, C., Liu, Q., and Miryoosefi, S · 2021
Later among the works it cites.
Navigating to the best policy in markov decision processes
Marjani, A. A., Garivier, A., and Proutiere, A · 2021
Later among the works it cites.
An exponential lower bound for linearly-realizable mdps with constant suboptimality gap
Wang, Y., Wang, R., and Kakade, S. M · 2021
Later among the works it cites.
Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions
Weisz, G., Amortila, P., and Szepesvári, C · 2021
Later among the works it cites.
Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap
Xu, H., Ma, T., and Du, S. S · 2021
Later among the works it cites.
Reward is enough for convex mdps
Zahavy, T., O’Donoghue, B., Desjardins, G., and Singh, S · 2021
Later among the works it cites.
Zhang, Z., Yang, J., Ji, X., and Du, S. S · 2021
Later among the works it cites.
Provably efficient reinforcement learning for discounted mdps with feature mapping
Zhou, D., He, J., and Gu, Q · 2021
Later among the works it cites.
Instance-optimal pac algorithms for contextual bandits
Li, Z., Ratliff, L., Nassif, H., Jamieson, K., and Jain, L · 2022
Closest in time.
Active exploration via experiment design in markov chains
Mutny, M., Janik, T., and Krause, A · 2022
Closest in time.
Near instance-optimal pac reinforcement learning for deterministic mdps
Tirinzoni, A., Al-Marjani, A., and Kaufmann, E · 2022
Closest in time.
Reward-free rl is no harder than reward-aware rl in linear markov decision processes
Wagenmaker, A., Chen, Y., Simchowitz, M., Du, S. S., and Jamieson, K · 2022
Closest in time.