Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality

Ming Yin, Wenjing Chen, Mengdi Wang, Yu Xiang Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 iterationbased 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022
PublisherAssociation For Uncertainty in Artificial Intelligence (AUAI)
Pages2278-2288
Number of pages11
ISBN (Electronic)9781713863298
StatePublished - 2022
Externally publishedYes
Event38th Conference on Uncertainty in Artificial Intelligence, UAI 2022 - Eindhoven, Netherlands
Duration: Aug 1 2022Aug 5 2022

Publication series

NameProceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI 2022

Conference

Conference38th Conference on Uncertainty in Artificial Intelligence, UAI 2022
Country/TerritoryNetherlands
CityEindhoven
Period8/1/228/5/22

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality'. Together they form a unique fingerprint.

Cite this