Nearly Horizon-Free Offline Reinforcement Learning

Abstract

We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes (MDP). For tabular MDP with $S$ states and $A$ actions, or linear MDP with anchor points and feature dimension $d$, given the collected $K$ episodes data with minimum visiting probability of (anchor) state-action pairs $d_m$, we obtain nearly horizon $H$-free sample complexity bounds for offline reinforcement learning when the total reward is upper bounded by $1$. Specifically: 1. For offline policy evaluation, we obtain an $\tilde{O}\left(\sqrt{\frac{1}{K{d}_m}}\right)$ error bound for the plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on $\mathrm{poly}\left(H,S,A,d\right)$ in higher-order term. 2.For offline policy optimization, we obtain an $\tilde{O}\left(\sqrt{\frac{1}{K{d}_m}}+\frac{\min (S,d)}{K{d}_m}\right)$ sub-optimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by \cite{cui2020plug} that has additional $\mathrm{poly}\left(H,S,d\right)$ factors in the main term. To the best of our knowledge, these are the \emph{first} set of nearly horizon-free bounds for episodic time-homogeneous offline tabular MDP and linear MDP with anchor points. Central to our analysis is a simple yet effective recursion based method to bound a "total variance" term in the offline scenarios, which could be of individual interest.

NeurIPS 2021

References in corpus (14)

• Conservative Q-Learning for Offline Reinforcement Learning
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Off-Policy Policy Gradient with State Distribution Correction
• Consistent On-Line Off-Policy Evaluation
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Batch Value-function Approximation with Only Realizability
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Off-Policy Evaluation via the Regularized Lagrangian
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?

Cited by in corpus (3)

• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approach