Offline Stochastic Shortest Path: Learning, Evaluation And Towards Optimality

Abstract

Goal-oriented Reinforcement Learning, where the agent needs to reach the goal state while simultaneously minimizing the cost, has received significant attention in real-world applications. Its theoretical formulation, stochastic shortest path (SSP), has been intensively researched in the online setting. Nevertheless, it remains understudied when such an online interaction is prohibited and only historical data is provided. In this paper, we consider the offline stochastic shortest path problem when the state space and the action space are finite. We design the simple value iteration-based algorithms for tackling both offline policy evaluation (OPE) and offline policy learning tasks. Notably, our analysis of these simple algorithms yields strong instance-dependent bounds which can imply worst-case bounds that are near-minimax optimal. We hope our study could help illuminate the fundamental statistical limits of the offline SSP problem and motivate further studies beyond the scope of cur

Stats

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

Related papers

• Optimal Uniform OPE And Model-based Offline Reinforcement Learning In Time-homogeneous, Reward-free And Task-agnostic Settings (2021)0.00
• Near-optimal Provable Uniform Convergence In Offline Policy Evaluation For Reinforcement Learning (2020)0.00
• Pessimistic Nonlinear Least-squares Value Iteration For Offline Reinforcement Learning (2023)0.00
• Projected State-action Balancing Weights For Offline Reinforcement Learning (2021)0.00
• Offline Policy Evaluation For Reinforcement Learning With Adaptively Collected Data (2023)0.00
• Efficient Evaluation Of Natural Stochastic Policies In Offline Reinforcement Learning (2020)0.00
• POPO: Pessimistic Offline Policy Optimization (2020)5.24
• Conservative Equilibrium Discovery In Offline Game-theoretic Multiagent Reinforcement Learning (2026)0.00