eeb69a3cb92300456b6a5f4162093851-Paper.pdf

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 ofthe problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model forK episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is eO( p (B2?+B?)|S||A|K)whereB?