智客 ZICQ
EN 登录 / 注册
智客前沿 前沿论文 #ArXiv #多臂老虎机 #Whittle指数 #部分可观测性 #强化学习

ArXiv提出t步前瞻阈值策略:革新部分可观测Restless Bandits的Whittle指数计算

Mr.Xu 的头像

文 / Mr.Xu 智客前沿编译 · 审校

发布时间: · 4 次阅读

中文阅读 (Chinese) English Version
共读互动 选中正文任意句子即可高亮划线、写下你的技术批注,或一键生成金句引用卡。 直达讨论区 ↓

摘要:ArXiv团队提出了一种名为t步前瞻阈值策略的新方法,用于改进部分可观测Restless Bandits中的Whittle指数计算。该方法通过引入t步有限视野价值迭代,显著提升了近似Whittle指数的精度,并实现了对精确决策边界的更紧密跟踪。实验结果表明,随着t的增加,P95指数误差显著降低,且在特定条件下,t=2已能恢复精确的Whittle指数排序。该研究为多臂老虎机问题中的决策优化提供了更高效的解决方案。


背景与动机

在多臂老虎机问题中,Restless Bandits是一种重要的变体,其中非活动臂的状态会随时间演变。部分可观测性使得问题更加复杂,因为即使在单个信念状态下确定无差异补贴,也需要解决一个没有闭式价值函数的无限视野信念状态问题。

主要贡献

ArXiv团队提出了一种名为t步前瞻阈值策略的新方法,旨在解决上述挑战。其核心创新点包括:

  • t步有限视野价值迭代:通过引入t步有限视野价值迭代,算法能够更准确地近似Whittle指数,并实现对精确决策边面的更紧密跟踪。
  • 无需预先索引性假设:该方法不要求预先知道索引性,并包含一个索引性验证步骤。
  • 几何收敛性证明:在原始Whittle索引性条件下,证明了t步近似Whittle指数以几何速率收敛到精确Whittle指数,公式为 ( |\widehat W_t(ω)-W(ω)|=O(β^t) )。

实验结果

实验在2715个三状态实例上进行了验证,结果表明:

  • 索引性验证:所有实例均通过了提出的索引性标准验证。
  • 误差降低:P95指数误差从t=1时的 (2.18\times10^{-2}) 降低到t=8时的 (8.93\times10^{-4})。
  • 实际性能:在 (β=0.9999) 的精确可比实例中,t=2 已能恢复精确的Whittle指数排序。

此外,中等深度的阈值策略在性能上优于单步基线方法,同时保持了接近最优动态规划基准的表现,而运行时间随t的增加仅适度增长。

行业影响与开发者建议

  • 多臂老虎机应用:该方法为多臂老虎机问题中的决策优化提供了更高效的解决方案,尤其适用于资源分配、调度和优化等场景。
  • 算法实现:开发者可以参考该方法实现更精确的Whittle指数计算,并结合具体应用场景调整t值以平衡性能和计算成本。
  • 未来研究方向:进一步研究可以探索如何将t步前瞻策略扩展到更复杂的多臂老虎机变体中,如上下文老虎机或非平稳老虎机。

消息来源:ArXiv cs.LG (2026-08-25)

—— 完 ——

主题标签: #ArXiv #多臂老虎机 #Whittle指数 #部分可观测性 #强化学习

编辑部与事实核查说明:本篇专刊由智客前沿资讯管线根据官方技术公告、学术论文及开源工程文档整理编译,经算法实体核验与人工编辑审校后发布。若发现技术事实纰漏,欢迎依据勘误方针或一键向编辑部发送勘误反馈。

读完这篇,你的第一判断是?
🚀 去【作品】晒出你的相关实践

社区整体评论区

正在加载实时智能评论与划词标注…