2021/12/18 by Liyu Chen, Chen, Liyu, Rahul Jain +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2112.09859
openalex publication_date 2021/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce two new no-regret algorithms for the stochastic shortest path (SSP) problem with a linear MDP that significantly improve over the only existing results of (Vial et al., 2021). Our first algorithm is computationally efficient and achieves a regret bound \widetildeO(√d3B⋆2T⋆ K), where d is the dimension of the feature space, B⋆ and T⋆ are upper bounds of the expected costs and hitting time of the optimal policy respectively, and K is the number of episodes. The same algorithm with a slight modification also achieves logarithmic regret of order O(\fracd3B⋆4cmin2gapminln5\fracdB⋆ Kcmin ), where gapmin is the minimum sub-optimality gap and cmin is the minimum cost over all state-action pairs. Our result is obtained by developing a simpler and improved analysis for the finite-horizon approximation of (Cohen et al., 2021) with a smaller approximation error, which might be of independent interest. On the other hand, using variance-aware confidence sets in a global optimization problem, our second algorithm is computationally inefficient but achieves the first "horizon-free" regret bound \widetildeO(d3.5B⋆√(K)) with no polynomial dependency on T⋆ or 1/cmin, almost matching the Ω(dB⋆√(K)) lower bound from (Min et al., 2021).