Online Learning for Stochastic Shortest Path Model via Posterior Sampling

Abstract

We consider the problem of online reinforcement learning for the Stochastic Shortest Path (SSP) problem modeled as an unknown MDP with an absorbing state. We propose PSRL-SSP, a simple posterior sampling-based reinforcement learning algorithm for the SSP problem. The algorithm operates in epochs. At the beginning of each epoch, a sample is drawn from the posterior distribution on the unknown model dynamics, and the optimal policy with respect to the drawn sample is followed during that epoch. An epoch completes if either the number of visits to the goal state in the current epoch exceeds that of the previous epoch, or the number of visits to any of the state-action pairs is doubled. We establish a Bayesian regret bound of $O(B_{\star }S\sqrt{AK})$, where $B_{\star }$ is an upper bound on the expected cost of the optimal policy, $S$ is the size of the state space, $A$ is the size of the action space, and $K$ is the number of episodes. The algorithm only requires the knowledge of the prior distribution, and has no hyper-parameters to tune. It is the first such posterior sampling algorithm and outperforms numerically previously proposed optimism-based algorithms.

References in corpus (13)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• (More) Efficient Reinforcement Learning via Posterior Sampling
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• A Tutorial on Thompson Sampling
• Learning-based Control of Unknown Linear Systems with Thompson Sampling
• Thompson Sampling for Linear-Quadratic Control Problems
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• Online Learning for Unknown Partially Observable MDPs
• Minimax Regret for Stochastic Shortest Path
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

Cited by in corpus (4)

• Online Learning for Unknown Partially Observable MDPs
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Learning Stochastic Shortest Path with Linear Function Approximation
• Adaptive Multi-Goal Exploration