Learning Stochastic Shortest Path with Linear Function Approximation

Abstract

We study the stochastic shortest path (SSP) problem in reinforcement learning with linear function approximation, where the transition kernel is represented as a linear mixture of unknown models. We call this class of SSP problems as linear mixture SSPs. We propose a novel algorithm with Hoeffding-type confidence sets for learning the linear mixture SSP, which can attain an $\tilde{\mathcal{O}}(d{B}_{\star }^{1.5}\sqrt{K/c_{\min }})$ regret. Here $K$ is the number of episodes, $d$ is the dimension of the feature mapping in the mixture model, $B_{\star }$ bounds the expected cumulative cost of the optimal policy, and $c_{\min }>0$ is the lower bound of the cost function. Our algorithm also applies to the case when $c_{\min }=0$, and an $\tilde{\mathcal{O}}(K^{2/3})$ regret is guaranteed. To the best of our knowledge, this is the first algorithm with a sublinear regret guarantee for learning linear mixture SSP. Moreover, we design a refined Bernstein-type confidence set and propose an improved algorithm, which provably achieves an $\tilde{\mathcal{O}}(d{B}_{\star }\sqrt{K/c_{\min }})$ regret. In complement to the regret upper bounds, we also prove a lower bound of $\Omega (d{B}_{\star }\sqrt{K})$. Hence, our improved algorithm matches the lower bound up to a $1/\sqrt{c_{\min }}$ factor and poly-logarithmic factors, achieving a near-optimal regret guarantee.

46 pages, 1 figure. In ICML 2022

References in corpus (12)

• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Planning with Goal-Conditioned Policies
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Minimax Regret for Stochastic Shortest Path
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation

Cited by in corpus (1)

• Adaptive Multi-Goal Exploration