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\}\{Kd_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\}\{Kd_m\}\} + \frac\{\min(S, d)\}\{Kd_m\}\right)\) sub-optimality gap for the empirical optimal policy, which approach

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyren2021nearly

Related papers

• Near-optimal Offline Reinforcement Learning Via Double Variance Reduction (2021)0.00
• Policy Finetuning: Bridging Sample-efficient Offline And Online Reinforcement Learning (2021)0.00
• Online Sparse Reinforcement Learning (2020)0.00
• A Primal-dual Algorithm For Offline Constrained Reinforcement Learning With Linear Mdps (2024)0.00
• Optimal Uniform OPE And Model-based Offline Reinforcement Learning In Time-homogeneous, Reward-free And Task-agnostic Settings (2021)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Settling The Horizon-dependence Of Sample Complexity In Reinforcement Learning (2021)3.58