提出SOIDS算法，在无贝叶斯假设下实现高维稀疏强化学习的最优最坏情况表现。
Sparse Optimistic Information Directed Sampling
- 采用乐观信息导向采样思想，结合时间依赖学习率设计新算法
- 在数据丰富与贫乏两种场景下均达到最优最坏情况后悔界
- 首次实现无需贝叶斯假设的自适应最优性能，适合高维在线决策场景
许多高维在线决策问题可建模为随机稀疏线性老虎机问题。现有算法通常在数据丰富场景（多项式依赖环境维度）或数据贫乏场景（维度无关但轮次依赖更差）中取得最优最坏情况后悔界。相比之下，稀疏信息导向采样（Sparse IDS）算法在贝叶斯设定下可同时实现两者的最优率。本文研究稀疏乐观信息导向采样（SOIDS），在无贝叶斯假设下实现相同自适应性。通过一种新颖分析，引入时间依赖学习率，证明SOIDS能最优平衡信息获取与后悔。结果扩展了IDS的理论保证，首次提供在数据丰富与贫乏双重场景下均达最优最坏情况后悔界的算法。实验验证了SOIDS的良好性能。
原文摘要 · Abstract (English)
Many high-dimensional online decision-making problems can be modeled as stochastic sparse linear bandits. Most existing algorithms are designed to achieve optimal worst-case regret in either the data-rich regime, where polynomial dependence on the ambient dimension is unavoidable, or the data-poor regime, where dimension-independence is possible at the cost of worse dependence on the number of rounds. In contrast, the sparse Information Directed Sampling (IDS) algorithm satisfies a Bayesian regret bound that has the optimal rate in both regimes simultaneously. In this work, we explore the use of Sparse Optimistic Information Directed Sampling (SOIDS) to achieve the same adaptivity in the worst-case setting, without Bayesian assumptions. Through a novel analysis that enables the use of a time-dependent learning rate, we show that SOIDS can optimally balance information and regret. Our results extend the theoretical guarantees of IDS, providing the first algorithm that simultaneously achieves optimal worst-case regret in both the data-rich and data-poor regimes. We empirically demonstrate the good performance of SOIDS.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。