No-regret exploration in goal-oriented ...
Type de document :
Communication dans un congrès avec actes
Titre :
No-regret exploration in goal-oriented reinforcement learning
Auteur(s) :
Tarbouriech, Jean [Auteur]
Scool [Scool]
Facebook AI Research [Paris] [FAIR]
Garcelon, Evrard [Auteur]
Facebook AI Research [Paris] [FAIR]
Valko, Michal [Auteur]
DeepMind [Paris]
Pirotta, Matteo [Auteur]
Facebook AI Research [Paris] [FAIR]
Lazaric, Alessandro [Auteur]
Facebook AI Research [Paris] [FAIR]
Scool [Scool]
Facebook AI Research [Paris] [FAIR]
Garcelon, Evrard [Auteur]
Facebook AI Research [Paris] [FAIR]
Valko, Michal [Auteur]
DeepMind [Paris]
Pirotta, Matteo [Auteur]
Facebook AI Research [Paris] [FAIR]
Lazaric, Alessandro [Auteur]
Facebook AI Research [Paris] [FAIR]
Titre de la manifestation scientifique :
International Conference on Machine Learning
Ville :
Vienna / Virtual
Pays :
Autriche
Date de début de la manifestation scientifique :
2020
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [en]
Many popular reinforcement learning problems (e.g., navigation in a maze, some Atari games, mountain car) are instances of the episodic setting under its stochastic shortest path (SSP) formulation, where an agent has to ...
Lire la suite >Many popular reinforcement learning problems (e.g., navigation in a maze, some Atari games, mountain car) are instances of the episodic setting under its stochastic shortest path (SSP) formulation, where an agent has to achieve a goal state while minimizing the cumulative cost. Despite the popularity of this setting, the explorationexploitation dilemma has been sparsely studied in general SSP problems, with most of the theoretical literature focusing on different problems (i.e., finite-horizon and infinite-horizon) or making the restrictive loop-free SSP assumption (i.e., no state can be visited twice during an episode). In this paper, we study the general SSP problem with no assumption on its dynamics (some policies may actually never reach the goal). We introduce UC-SSP, the first no-regret algorithm in this setting, and prove a regret bound scaling as O(DS √ ADK) after K episodes for any unknown SSP with S states, A actions, positive costs and SSP-diameter D, defined as the smallest expected hitting time from any starting state to the goal. We achieve this result by crafting a novel stopping rule, such that UC-SSP may interrupt the current policy if it is taking too long to achieve the goal and switch to alternative policies that are designed to rapidly terminate the episode.Lire moins >
Lire la suite >Many popular reinforcement learning problems (e.g., navigation in a maze, some Atari games, mountain car) are instances of the episodic setting under its stochastic shortest path (SSP) formulation, where an agent has to achieve a goal state while minimizing the cumulative cost. Despite the popularity of this setting, the explorationexploitation dilemma has been sparsely studied in general SSP problems, with most of the theoretical literature focusing on different problems (i.e., finite-horizon and infinite-horizon) or making the restrictive loop-free SSP assumption (i.e., no state can be visited twice during an episode). In this paper, we study the general SSP problem with no assumption on its dynamics (some policies may actually never reach the goal). We introduce UC-SSP, the first no-regret algorithm in this setting, and prove a regret bound scaling as O(DS √ ADK) after K episodes for any unknown SSP with S states, A actions, positive costs and SSP-diameter D, defined as the smallest expected hitting time from any starting state to the goal. We achieve this result by crafting a novel stopping rule, such that UC-SSP may interrupt the current policy if it is taking too long to achieve the goal and switch to alternative policies that are designed to rapidly terminate the episode.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-03287824/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03287824/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03287824/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- tarbouriech2020no-regret.pdf
- Accès libre
- Accéder au document