  Stochastic shortest path (SSP) is a well-known problem in planning and
control, in which an agent has to reach a goal state in minimum total expected
cost. In the learning formulation of the problem, the agent is unaware of the
environment dynamics (i.e., the transition function) and has to repeatedly play
for a given number of episodes while reasoning about the problem's optimal
solution. Unlike other well-studied models in reinforcement learning (RL), the
length of an episode is not predetermined (or bounded) and is influenced by the
agent's actions. Recently, Tarbouriech et al. (2019) studied this problem in
the context of regret minimization and provided an algorithm whose regret bound
is inversely proportional to the square root of the minimum instantaneous cost.
In this work we remove this dependence on the minimum cost---we give an
algorithm that guarantees a regret bound of $\widetilde{O}(B_\star |S|
\sqrt{|A| K})$, where $B_\star$ is an upper bound on the expected cost of the
optimal policy, $S$ is the set of states, $A$ is the set of actions and $K$ is
the number of episodes. We additionally show that any learning algorithm must
have at least $\Omega(B_\star \sqrt{|S| |A| K})$ regret in the worst case.
