针对稀疏代价的随机最短路径问题，提出自适应稀疏性的新算法。
Stochastic Shortest Path with Sparse Adversarial Costs
- 用ℓ_r范数正则化替代负熵，适配稀疏性
- 后悔值降至√log M，优于传统方法的√log(SA)
- 适用于状态动作对中仅少量有代价的场景
我们研究在全信息反馈下具有稀疏代价的对抗性随机最短路径（SSP）问题。已知转移情况下，基于在线镜像下降（OMD）与负熵正则化的现有边界随√log(SA)增长，其中SA为状态动作空间大小。尽管这在最坏情况下已最优，却未能体现仅少量（M ≪ SA）状态动作对产生代价时的稀疏优势。事实上，我们证明负熵本质上不适应稀疏性：在稀疏问题上其后悔值仍达√log S。为此，我们提出一簇ℓ_r-范数正则化（r ∈ (1,2)），可自适应稀疏性，实现后悔值仅随√log M增长。我们通过匹配下界证明此结果最优，表明有效维度由M而非SA决定。在未知转移情况下，稀疏性优势受限：我们证明即便在稀疏问题上，任意学习者的极小极大后悔值仍随SA多项式增长。
原文摘要 · Abstract (English)
We study the adversarial Stochastic Shortest Path (SSP) problem with sparse costs under full-information feedback. In the known transition setting, existing bounds based on Online Mirror Descent (OMD) with negative-entropy regularization scale with $\sqrt{\log S A}$, where $SA$ is the size of the state-action space. While we show that this is optimal in the worst-case, this bound fails to capture the benefits of sparsity when only a small number $M \ll SA$ of state-action pairs incur cost. In fact, we also show that the negative-entropy is inherently non-adaptive to sparsity: it provably incurs regret scaling with $\sqrt{\log S}$ on sparse problems. Instead, we propose a family of $\ell_r$-norm regularizers ($r \in (1,2)$) that adapts to the sparsity and achieves regret scaling with $\sqrt{\log M}$ instead of $\sqrt{\log SA}$. We show this is optimal via a matching lower bound, highlighting that $M$ captures the effective dimension of the problem instead of $SA$. Finally, in the unknown transition setting the benefits of sparsity are limited: we prove that even on sparse problems, the minimax regret for any learner scales polynomially with $SA$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。