用Q学习方法实现随机多臂赌博机的威特尔索引学习
Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes
- 采用双时标随机逼近，慢速更新索引，快速更新Q值
- 常数步长下算法收敛，支持DQN与线性函数近似
- 适用于需要长期策略优化的动态资源分配场景
本文研究了用于随机多臂赌博机的威特尔索引学习算法。采用带有探索策略（ε-贪心、Softmax、ε-Softmax）的Q学习方法，并将其扩展至单臂随机赌博机的索引学习。提出一种双时标随机逼近算法：在较慢时标上更新索引学习机制，在较快时标上以固定索引值进行Q学习更新，且更新为异步方式。研究了常数步长下的双时标随机逼近分析。进一步探讨了基于深度Q网络（DQN）和状态聚合的线性函数逼近的索引学习方法。通过数值实验验证算法性能，表明基于Q学习、DQN和函数逼近的索引学习能有效学习威特尔索引。
原文摘要 · Abstract (English)
We study the Whittle index learning algorithm for restless multi-armed bandits. We consider index learning algorithm with Q-learning. We first present Q-learning algorithm with exploration policies -- epsilon-greedy, softmax, epsilon-softmax with constant stepsizes. We extend the study of Q-learning to index learning for single-armed restless bandit. The algorithm of index learning is two-timescale variant of stochastic approximation, on slower timescale we update index learning scheme and on faster timescale we update Q-learning assuming fixed index value. In Q-learning updates are in asynchronous manner. We study constant stepsizes two timescale stochastic approximation algorithm. We provide analysis of two-timescale stochastic approximation for index learning with constant stepsizes. Further, we present study on index learning with deep Q-network (DQN) learning and linear function approximation with state-aggregation method. We describe the performance of our algorithms using numerical examples. We have shown that index learning with Q learning, DQN and function approximations learns the Whittle index.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。