Skip to Main content Skip to Navigation
Conference papers

Sample complexity bounds for stochastic shortest path with a generative model

Jean Tarbouriech 1, 2 Matteo Pirotta 1 Michal Valko 3 Alessandro Lazaric 1 
2 Scool - Scool
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : We consider the objective of computing an ε-optimal policy in a stochastic shortest path (SSP) setting, provided that we can access a generative sampling oracle. We propose two algorithms for this setting and derive PAC bounds on their sample complexity: one for the case of positive costs and the other for the case of non-negative costs under a restricted optimality criterion. While tight sample complexity bounds have been derived for the finite-horizon and discounted MDPs, the SSP problem is a strict generalization of these settings and it poses additional technical challenges due to the fact that no specific time horizon is prescribed and policies may never terminate, i.e., we are possibly facing non-proper policies. As a consequence, we can neither directly apply existing techniques minimizing sample complexity nor rely on a regret-to-PAC conversion leveraging recent regret bounds for SSP. Our analysis instead combines SSP-specific tools and variance reduction techniques to obtain the first sample complexity bounds for this setting.
Document type :
Conference papers
Complete list of metadata
Contributor : Michal Valko Connect in order to contact the contributor
Submitted on : Friday, July 16, 2021 - 3:57:04 PM
Last modification on : Sunday, June 26, 2022 - 9:10:13 AM
Long-term archiving on: : Sunday, October 17, 2021 - 7:05:20 PM


Files produced by the author(s)


  • HAL Id : hal-03288988, version 1



Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with a generative model. Algorithmic Learning Theory, 2021, Paris, France. ⟨hal-03288988⟩



Record views


Files downloads