Fast Rates for the Regret of Offline Reinforcement Learning
Authors:
- 1 February 2025
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 50 (1) , 633-655
Abstract
We study the regret of offline reinforcement learning in an infinite-horizon discounted Markov decision process (MDP). While existing analyses of common approaches, such as fitted Q-iteration (FQI), suggest root-n convergence for regret, empirical behavior exhibits much faster convergence. In this paper, we present a finer regret analysis that exactly characterizes this phenomenon by providing fast rates for the regret convergence. First, we show that given any estimate for the optimal quality function, the regret of the policy it defines converges at a rate given by the exponentiation of the estimate’s pointwise convergence rate, thus speeding up the rate. The level of exponentiation depends on the level of noise in the decision-making problem, rather than the estimation problem. We establish such noise levels for linear and tabular MDPs as examples. Second, we provide new analyses of FQI and Bellman residual minimization to establish the correct pointwise convergence guarantees. As specific cases, our results imply one-over-n rates in linear cases and exponential-in-n rates in tabular cases. We extend our findings to general function approximation by extending our results to regret guarantees based on Lp-convergence rates for estimating the optimal quality function rather than pointwise rates, where L2 guarantees for nonparametric estimation can be ensured under mild conditions. Funding: This work was supported by the Division of Information and Intelligent Systems, National Science Foundation [Grant 1846210].Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- High-Dimensional Statistics2019
- A Linear Response Bandit ProblemStochastic Systems, 2013
- Minimax PAC bounds on the sample complexity of reinforcement learning with a generative modelMachine Learning, 2013
- The multi-armed bandit problem with covariatesThe Annals of Statistics, 2013
- Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample pathMachine Learning, 2007
- Fast learning rates for plug-in classifiersThe Annals of Statistics, 2007
- Optimal aggregation of classifiers in statistical learningThe Annals of Statistics, 2004
- Smooth discrimination analysisThe Annals of Statistics, 1999
- An upper bound on the loss from approximate optimal-value functionsMachine Learning, 1994
- Empirical Processes1990