Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

Tarbouriech, Jean; Zhou, Runlong; Du, Simon; Pirotta, Matteo; Valko, Michal; Lazaric, Alessandro

Type de document :

Communication dans un congrès avec actes

Titre :

Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

Auteur(s) :

Tarbouriech, Jean [Auteur]
Scool [Scool]
Facebook AI Research [Paris] [FAIR]
Zhou, Runlong [Auteur]
Tsinghua University [Beijing] [THU]
Du, Simon [Auteur]
Paul G. Allen School of Computer Science and Engineering [Seattle]
Pirotta, Matteo [Auteur]
Facebook AI Research [Paris] [FAIR]
Valko, Michal [Auteur]
DeepMind [Paris]
Lazaric, Alessandro [Auteur]
Facebook AI Research [Paris] [FAIR]

Titre de la manifestation scientifique :

Neural Information Processing Systems (NeurIPS)

Ville :

Virtual/Sydney

Pays :

Australie

Date de début de la manifestation scientifique :

2021-12-06

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Apprentissage [cs.LG]

Résumé en anglais : [en]

We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP ...
Lire la suite >We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP that carefully skews the empirical transitions and perturbs the empirical costs with an exploration bonus to induce an optimistic SSP problem whose associated value iteration scheme is guaranteed to converge. We prove that EB-SSP achieves the minimax regret rate O(B* √ SAK), where K is the number of episodes, S is the number of states, A is the number of actions, and B* bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of B*, nor of T*, which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of T* is available) where the regret only contains a logarithmic dependence on T*, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-03479782/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-03479782/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-03479782/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

Stochastic%20Shortest%20Path.pdf
Accès libre
Accéder au document

document
Accès libre
Accéder au document

Stochastic%20Shortest%20Path.pdf
Accès libre
Accéder au document

Stochastic Shortest Path: Minimax, ... BibTeX CSV Excel RIS

Fichiers

Stochastic Shortest Path: Minimax, ...

BibTeX

CSV

Excel

RIS