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

Abstract

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 $\tilde{O}(B_{\star }\sqrt{SAK})$, where $K$ is the number of episodes, $S$ is the number of states, $A$ is the number of actions, and $B_{\star }$ 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_{\star }$, nor of $T_{\star }$, 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_{\star }$ is available) where the regret only contains a logarithmic dependence on $T_{\star }$, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.

NeurIPS 2021

References in corpus (13)

• Empirical Bernstein Bounds and Sample Variance Penalization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Online Convex Optimization in Adversarial Markov Decision Processes
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Minimax Regret for Stochastic Shortest Path

Cited by in corpus (4)

• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Learning Stochastic Shortest Path with Linear Function Approximation
• Adaptive Multi-Goal Exploration