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(dB_{\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.

本论文研究了具有线性函数逼近的随机最短路径问题，提出了一种使用 Hoeffding 类型置信度集的新算法，能够实现次线性后悔保证。同时，对于在 $c_{min}=0$ 的情况，可以保证近似次立方的后悔保证。此外，通过设计改进的贝恩斯坦置信度集，改进的算法能够保证近乎最优的后悔保证。