Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition

Abstract

We study the stochastic shortest path problem with adversarial costs and known transition, and show that the minimax regret is $\tilde{O}(\sqrt{D{T}^{\star }K})$ and $\tilde{O}(\sqrt{D{T}^{\star }SAK})$ for the full-information setting and the bandit feedback setting respectively, where $D$ is the diameter, $T^{\star }$ is the expected hitting time of the optimal policy, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Our results significantly improve upon the existing work of (Rosenberg and Mansour, 2020) which only considers the full-information setting and achieves suboptimal regret. Our work is also the first to consider bandit feedback with adversarial costs. Our algorithms are built on top of the Online Mirror Descent framework with a variety of new techniques that might be of independent interest, including an improved multi-scale expert algorithm, a reduction from general stochastic shortest path to a special loop-free case, a skewed occupancy measure space, and a novel correction term added to the cost estimators. Interestingly, the last two elements reduce the variance of the learner via positive bias and the variance of the optimal policy via negative bias respectively, and having them simultaneously is critical for obtaining the optimal high-probability bound in the bandit feedback setting.

References in corpus (8)

• Contextual Bandit Algorithms with Supervised Learning Guarantees
• More Adaptive Algorithms for Adversarial Bandits
• Online Convex Optimization in Adversarial Markov Decision Processes
• Learning in Games: Robustness of Fast Convergence
• Model selection for contextual bandits
• Efficient Online Portfolio with Logarithmic Regret
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications

Cited by in corpus (8)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Minimax Regret for Stochastic Shortest Path
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Learning Stochastic Shortest Path with Linear Function Approximation