Minimax Regret for Stochastic Shortest Path

Understand

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 $\widetilde 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.