Nearly Horizon-Free Offline Reinforcement Learning

2021/03/25 by Tongzheng Ren, Jialian Li, Ren, Tongzheng +7 · 2 citations
Computer Science · Mathematics · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2103.14077

NeurIPS 2021

openalex publication_date 2021/03/25 · arxiv created 2022/02/10 · arxiv updated 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(√((1)/(Kd_m)) ) error bound for the plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on poly(H, S, A, d) in higher-order term. 2.For offline policy optimization, we obtain an O(√((1)/(Kd_m)) + (min(S, d))/(Kd_m)) 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 \citecui2020plug that has additional poly(H, S, d) factors in the main term. To the best of our knowledge, these are the 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.

Citations

• Playing Atari with Deep Reinforcement Learning
• Consistent On-Line Off-Policy Evaluation
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Approximating Interactive Human Evaluation with Self-Play for Open-Domain Dialog Systems
• Learning dexterous in-hand manipulation
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Conservative Q-Learning for Offline Reinforcement Learning
• Off-Policy Evaluation via the Regularized Lagrangian
• Batch Value-function Approximation with Only Realizability
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning

Cited by

• Structural Information-based Hierarchical Diffusion for Offline Reinforcement Learning
• Statistical and Algorithmic Foundations of Reinforcement Learning

Related

• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning