Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
This research introduces EB-SSP, a new model-based algorithm for solving Stochastic Shortest Path problems where costs and dynamics are unknown. It achieves minimax regret bounds while being parameter-free and provides horizon-free regret guarantees, meaning performance depends only logarithmically on the time to reach the goal.