We study the stochastic shortest path problem with sparse adversarial costs and under known transitions characterize the minimax regret achieved by OMD with a novel $\ell_r$-norm regularizer with $r \in [1,2]$.