Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path

arXiv:2402.08998v1 Announce Type: new
Abstract: We study the Stochastic Shortest Path (SSP) problem with a linear mixture transition kernel, where an agent repeatedly interacts with a stochastic environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the cost function or an upper bound of the expected length for the optimal policy. In this paper, we propose a new algorithm to eliminate these restrictive assumptions. Our algorithm …

abstract agent arxiv cost cs.lg environment kernel linear minimax path positive state stat.ml stochastic study transition type