揭示随机最短路径学习的样本复杂度下界及可学习条件
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
- 基于生成模型推导最优策略学习的样本下界
- 当最小代价为0时问题可能不可学，比有限时长远难
- 提出匹配下界的算法，需最优策略命中目标时间有界
研究在随机最短路径（SSP）问题中学习ε-最优策略的样本复杂度。当学习者拥有生成模型时，我们证明存在一个最坏情况的SSP实例，包含S个状态、A个动作、最小代价c_min，以及最优策略在所有状态下的最大期望代价B_⋆，任何算法均需至少Ω(SAB_⋆³/(c_minε²))次采样才能以高概率获得ε-最优策略。令人意外的是，这表明当c_min = 0时，SSP问题可能不可学习，揭示了学习在SSP中严格比有限时长远和折扣设定更困难。我们进一步给出一个算法，在一般情况下与该下界匹配（仅对数因子差异）；另有一个算法在c_min = 0时也匹配下界，但需假设最优策略到达目标状态的命中时间有界。
原文摘要 · Abstract (English)
We study the sample complexity of learning an $ε$-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_{\min}$, and maximum expected cost of the optimal policy over all states $B_{\star}$, where any algorithm requires at least $Ω(SAB_{\star}^3/(c_{\min}ε^2))$ samples to return an $ε$-optimal policy with high probability. Surprisingly, this implies that whenever $c_{\min} = 0$ an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this lower bound with an algorithm that matches it, up to logarithmic factors, in the general case, and an algorithm that matches it up to logarithmic factors even when $c_{\min} = 0$, but only under the condition that the optimal policy has a bounded hitting time to the goal state.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。