2022

Settling the Sample Complexity of Model-Based Offline Reinforcement Learning

Li, Gen, Shi, Laixi, Chen, Yuxin et al.

Understand

This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration.

Effective offline RL would be able to accommodate distribution shift and limited data coverage.
However, prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality, thus posing an impediment to efficient offline RL in sample-starved applications.
We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost for tabular Markov decision processes (MDPs).

Built on

A theoretical analysis of deep Q-learning
Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2019) · 1901
Earlier work this paper cites.
Stochastic approximation with cone-contractive operators: Sharp ℓ ∞ \ell_{\infty} -bounds for Q-learning
Original
Wainwright, M. J. (2019b) · 1905
Earlier work this paper cites.
Variance-reduced Q-learning is minimax optimal
Original
Wainwright, M. J. (2019c) · 1906
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. and Monro, S. (1951) · 1951
Earlier work this paper cites.
A comparison of signalling alphabets
Gilbert, E. N. (1952) · 1952
Earlier work this paper cites.
Asymptotically efficient adaptive allocation rules
Lai, T. L. and Robbins, H. (1985) · 1985
Earlier work this paper cites.
Q-learning
Watkins, C. J. and Dayan, P. (1992) · 1992
Earlier work this paper cites.
The asymptotic convergence-rate of Q-learning
Szepesvári, C. (1998) · 1998
Earlier work this paper cites.
High-dimensional data analysis: The curses and blessings of dimensionality
Donoho, D. L. et al. (2000) · 2000
Earlier work this paper cites.
Fixed point theory and applications
Agarwal, R. P., Meehan, M., and O’regan, D. (2001) · 2001
Earlier work this paper cites.
Learning rates for Q-learning
Even-Dar, E. and Mansour, Y. (2003) · 2003
Earlier work this paper cites.
Offline reinforcement learning: Tutorial, review, and perspectives on open problems
Original
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020) · 2005
Earlier work this paper cites.
A generalization error for Q-learning
Murphy, S. (2005) · 2005
Earlier work this paper cites.
Logarithmic online regret bounds for undiscounted reinforcement learning
Auer, P. and Ortner, R. (2006) · 2006
Earlier work this paper cites.
Improved analysis of UCRL2 with empirical Bernstein inequality
Original
Fruit, R., Pirotta, M., and Lazaric, A. (2020) · 2007
Earlier work this paper cites.
Provably good batch reinforcement learning without great exploration
Original
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020) · 2007
Earlier work this paper cites.
Performance bounds in l p l_{p} -norm for approximate value iteration
Munos, R. (2007) · 2007
Earlier work this paper cites.
Introduction to nonparametric estimation
Tsybakov, A. B. (2009) · 2009
Earlier work this paper cites.
Error propagation for approximate policy and value iteration
Farahmand, A.-m., Szepesvári, C., and Munos, R. (2010) · 2010
Earlier work this paper cites.
Optimism in reinforcement learning and kullback-leibler divergence
Filippi, S., Cappé, O., and Garivier, A. (2010) · 2010
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Jaksch, T., Ortner, R., and Auer, P. (2010) · 2010
Earlier work this paper cites.
Error bounds for constant step-size Q-learning
Beck, C. L. and Srikant, R. (2012) · 2012
Earlier work this paper cites.
Batch reinforcement learning
Lange, S., Gabel, T., and Riedmiller, M. (2012) · 2012
Earlier work this paper cites.
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
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Johnson, R. and Zhang, T. (2013) · 2013
Earlier work this paper cites.
On minimax optimal offline policy evaluation
Original
Li, L., Munos, R., and Szepesvári, C. (2014) · 2014
Earlier work this paper cites.
Doubly robust off-policy value evaluation for reinforcement learning
Jiang, N. and Li, L. (2016) · 2016
Earlier work this paper cites.
Data-efficient off-policy policy evaluation for reinforcement learning
Thomas, P. and Brunskill, E. (2016) · 2016
Earlier work this paper cites.
Minimax regret bounds for reinforcement learning
Azar, M. G., Osband, I., and Munos, R. (2017) · 2017
Earlier work this paper cites.
Dynamic programming and optimal control (4th edition)
Bertsekas, D. P. (2017) · 2017
Earlier work this paper cites.
Stochastic variance reduction methods for policy evaluation
Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D. (2017) · 2017
Earlier work this paper cites.

Similar

Mastering the game of Go without human knowledge
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017) · 2017
Cited alongside, same era.
Introductory lectures on stochastic optimization
Duchi, J. C. (2018) · 2018
Cited alongside, same era.
Visual foresight: Model-based deep reinforcement learning for vision-based robotic control
Original
Ebert, F., Finn, C., Dasari, S., Xie, A., Lee, A., and Levine, 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.
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. (2018) · 2018
Cited alongside, same era.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G. (2018) · 2018
Cited alongside, same era.
Variance-aware regret bounds for undiscounted reinforcement learning in mdps
Talebi, M. S. and Maillard, O.-A. (2018) · 2018
Cited alongside, same era.
High-dimensional probability: An introduction with applications in data science
Vershynin, R. (2018) · 2018
Cited alongside, same era.
Provably efficient Q-learning with low switching cost
Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019) · 2019
Cited alongside, same era.
Information-theoretic considerations in batch reinforcement learning
Chen, J. and Jiang, N. (2019) · 2019
Cited alongside, same era.
Exploration bonus for regret minimization in discrete and continuous average reward MDPs
Qian, J., Fruit, R., Pirotta, M., and Lazaric, A. (2019) · 2019
Cited alongside, same era.
Q-learning with UCB exploration is sample efficient for infinite-horizon MDP
Wang, Y., Dong, K., Chen, X., and Wang, L. (2019) · 2019
Cited alongside, same era.

Then

Reinforcement learning: Theory and algorithms
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2021) · 2021
Later among the works it cites.
Minimax sample complexity for turn-based stochastic game
Cui, Q. and Yang, L. F. (2021) · 2021
Later among the works it cites.
Umbrella: Uncertainty-aware model-based offline reinforcement learning leveraging planning
Original
Diehl, C., Sievernich, T., Krüger, M., Hoffmann, F., and Bertran, T. (2021) · 2021
Later among the works it cites.
Optimal policy evaluation using kernel-based temporal difference methods
Original
Duan, Y., Wang, M., and Wainwright, M. J. (2021) · 2021
Later among the works it cites.
Nearly minimax optimal reinforcement learning for discounted MDPs
He, J., Zhou, D., and Gu, Q. (2021) · 2021
Later among the works it cites.
Is pessimism provably efficient for offline RL?
Jin, Y., Yang, Z., and Wang, Z. (2021) · 2021
Later among the works it cites.
Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021) · 2021
Later among the works it cites.
Sample complexity of offline reinforcement learning with deep ReLU networks
Original
Nguyen-Tang, T., Gupta, S., and Venkatesh, S. (2021) · 2021
Later among the works it cites.
Nearly horizon-free offline reinforcement learning
Ren, T., Li, J., Dai, B., Du, S. S., and Sanghavi, S. (2021) · 2021
Later among the works it cites.
Model selection for offline reinforcement learning: Practical considerations for healthcare settings
Tang, S. and Wiens, J. (2021) · 2021
Later among the works it cites.
Pessimistic model-based offline reinforcement learning under partial coverage
Original
Uehara, M. and Sun, W. (2021) · 2021
Later among the works it cites.
Batch value-function approximation with only realizability
Xie, T. and Jiang, N. (2021) · 2021
Later among the works it cites.
Policy finetuning: Bridging sample-efficient offline and online reinforcement learning
Original
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021) · 2021
Later among the works it cites.
A unified off-policy evaluation approach for general value function
Original
Xu, T., Yang, Z., Wang, Z., and Liang, Y. (2021) · 2021
Later among the works it cites.
Towards instance-optimal offline reinforcement learning with pessimism
Yin, M. and Wang, Y.-X. (2021) · 2021
Later among the works it cites.
Provable benefits of actor-critic methods for offline reinforcement learning
Zanette, A., Wainwright, M. J., and Brunskill, E. (2021) · 2021
Later among the works it cites.
Finite-sample regret bound for distributionally robust offline tabular reinforcement learning
Zhou, Z., Zhou, Z., Bai, Q., Qiu, L., Blanchet, J., and Glynn, P. (2021) · 2021
Later among the works it cites.
When is offline two-player zero-sum Markov game solvable?
Original
Cui, Q. and Du, S. S. (2022) · 2022
Closest in time.
Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2022) · 2022
Closest in time.
Sample complexity of robust reinforcement learning with a generative model
Panaganti, K. and Kalathil, D. (2022) · 2022
Closest in time.
A survey on offline reinforcement learning: Taxonomy, review, and open problems
Original
Prudencio, R. F., Maximo, M. R., and Colombini, E. L. (2022) · 2022
Closest in time.
Bridging offline reinforcement learning and imitation learning: A tale of pessimism
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2022) · 2022
Closest in time.
Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity
Original
Shi, L. and Chi, Y. (2022) · 2022
Closest in time.
Representation learning for online and offline RL in low-rank MDPs
Uehara, M., Zhang, X., and Sun, W. (2022) · 2022
Closest in time.
Model-based reinforcement learning is minimax-optimal for offline zero-sum Markov games
Original
Yan, Y., Li, G., Chen, Y., and Fan, J. (2022) · 2022
Closest in time.
Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism
Yin, M., Duan, Y., Wang, M., and Wang, Y.-X. (2022) · 2022
Closest in time.
Offline reinforcement learning with realizability and single-policy concentrability
Original
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. D. (2022) · 2022
Closest in time.
Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets
Original
Zhong, H., Xiong, W., Tan, J., Wang, L., Zhang, T., Wang, Z., and Yang, Z. (2022) · 2022
Closest in time.
Minimax-optimal reward-agnostic exploration in reinforcement learning
Original
Li, G., Yan, Y., Chen, Y., and Fan, J. (2023) · 2023
Closest in time.
The efficacy of pessimism in asynchronous Q-learning
Yan, Y., Li, G., Chen, Y., and Fan, J. (2023) · 2023
Closest in time.
Settling the sample complexity of online reinforcement learning
Original
Zhang, Z., Chen, Y., Lee, J. D., and Du, S. S. (2023) · 2023
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…