Fast Rates For The Regret Of Offline Reinforcement Learning

Abstract

We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinite-horizon discounted Markov decision process (MDP). While existing analyses of common approaches, such as fitted \(Q\)-iteration (FQI), suggest a \(O(1/\sqrt\{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 \(Q^*\), the regret of the policy it defines converges at a rate given by the exponentiation of the \(Q^*\)-estimate's pointwise convergence rate, thus speeding it up. 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 resid

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keyhu2021fast

Related papers

• Improved Regret Bound And Experience Replay In Regularized Policy Iteration (2021)0.00
• Regret-optimal Model-free Reinforcement Learning For Discounted Mdps With Short Burn-in Time (2023)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00
• Efficient Online Learning With Offline Datasets For Infinite Horizon Mdps: A Bayesian Approach (2023)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
• Rate-optimal Policy Optimization For Linear Markov Decision Processes (2023)0.00