提出更鲁棒的拉格朗日索引策略，适合动态资源分配场景
Lagrangian Index Policy for Restless Bandits with Average Reward
- 基于拉格朗日松弛设计索引策略，适应非平稳环境
- 在威特尔策略失效时仍保持高性能，尤其在重启模型中表现优异
- 可实现低内存在线学习，适合大规模多臂老虎机问题
本文研究带有长期平均奖励的非平稳多臂赌博机中的拉格朗日索引策略（LIP）。与已知渐近最优的威特尔索引策略（WIP）相比，尽管两者多数情况下性能相近，但在WIP表现不佳时，LIP依然表现稳健。我们进一步提出了基于表格和神经网络的强化学习算法，实现模型无关的LIP在线学习，其内存需求显著低于对应WIP方案。文中通过解析计算得到了重启模型下的拉格朗日索引，该模型适用于最优网页爬取及加权信息年龄最小化问题。此外，基于可交换性与德·菲内蒂定理，给出了同质臂情形下当臂数趋于无穷时渐近最优性的新证明。
原文摘要 · Abstract (English)
We study the Lagrangian Index Policy (LIP) for restless multi-armed bandits with long-run average reward. In particular, we compare the performance of LIP with the performance of the Whittle Index Policy (WIP), both heuristic policies known to be asymptotically optimal under certain natural conditions. Even though in most cases their performances are very similar, in the cases when WIP shows bad performance, LIP continues to perform very well. We then propose reinforcement learning algorithms, both tabular and NN-based, to obtain online learning schemes for LIP in the model-free setting. The proposed reinforcement learning schemes for LIP require significantly less memory than the analogous schemes for WIP. We calculate analytically the Lagrangian index for the restart model, which applies to the optimal web crawling and the minimization of the weighted age of information. We also give a new proof of asymptotic optimality in case of homogeneous arms as the number of arms goes to infinity, based on exchangeability and de Finetti's theorem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。