Minimax Regret for Stochastic Shortest Path

Abstract

We study the Stochastic Shortest Path (SSP) problem in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model for $K$ episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is $\tilde{O}(\sqrt{(B_{\star }^2+B_{\star })|S||A|K})$ where $B_{\star }$ is a bound on the expected cost of the optimal policy from any state, $S$ is the state space, and $A$ is the action space. This matches the $\Omega (\sqrt{B_{\star }^2|S||A|K})$ lower bound of Rosenberg et al. [2020] for $B_{\star }\ge 1$, and improves their regret bound by a factor of $\sqrt{|S|}$. For $B_{\star }<1$ we prove a matching lower bound of $\Omega (\sqrt{B_{\star }|S||A|K})$. Our algorithm is based on a novel reduction from SSP to finite-horizon MDPs. To that end, we provide an algorithm for the finite-horizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.

References in corpus (10)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Online Convex Optimization in Adversarial Markov Decision Processes
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Confidence-Budget Matching for Sequential Budgeted Learning

Cited by in corpus (5)

• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Learning Stochastic Shortest Path with Linear Function Approximation
• Adaptive Multi-Goal Exploration