Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case

Abstract

We make significant progress toward the stochastic shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve $\tilde{O}(\sqrt{S^{2}AD{T}_{\star }K})$ regret for the full-information setting and $\tilde{O}(\sqrt{S^3{A}^{2}D{T}_{\star }K})$ regret for the bandit feedback setting, 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 work strictly improves (Rosenberg and Mansour, 2020) in the full information setting, extends (Chen et al., 2020) from known transition to unknown transition, and is also the first to consider the most challenging combination: bandit feedback with adversarial costs and unknown transition. To remedy the gap between our upper bounds and the current best lower bounds constructed via a stochastically oblivious adversary, we also propose algorithms with near-optimal regret for this special case.

arXiv commentICML 2021

References in corpus (8)

• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Online Convex Optimization in Adversarial Markov Decision Processes
• 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
• No-Regret Exploration in Goal-Oriented Reinforcement Learning
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning

Cited by in corpus (4)

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