Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality
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 current consideration.