将网络互动引入多臂老虎机，提升资源分配效率。
Networked Restless Multi-Arm Bandits with Reinforcement Learning
- 融合独立级联模型构建带网络交互的多臂老虎机框架
- 提出近似算法实现1-1/e性能保证，且可收敛
- 实验证明在真实图数据上优于传统方法，适合社交网络场景
传统的非休息多臂老虎机（RMAB）假设各臂之间相互独立，难以捕捉现实环境中个体间的交互影响。本文提出网络化RMAB框架，结合独立级联模型刻画网络中臂之间的动态交互。定义了网络化RMAB的贝尔曼方程，但面临动作与状态空间指数增长的计算挑战。通过证明贝尔曼方程的次模性，采用爬山算法实现贝尔曼更新的$1- rac{1}{e}$近似保证。进一步通过改进的压缩分析证明近似更新的收敛性。为验证理论结果，设计了一种针对网络环境的高效Q-learning算法。在真实图数据上的实验表明，该方法显著优于$k$步前瞻和无网络感知的方法，凸显了在存在网络效应时建模交互的重要性。
原文摘要 · Abstract (English)
Restless Multi-Armed Bandits (RMABs) are a powerful framework for sequential decision-making, widely applied in resource allocation and intervention optimization challenges in public health. However, traditional RMABs assume independence among arms, limiting their ability to account for interactions between individuals that can be common and significant in a real-world environment. This paper introduces Networked RMAB, a novel framework that integrates the RMAB model with the independent cascade model to capture interactions between arms in networked environments. We define the Bellman equation for networked RMAB and present its computational challenge due to exponentially large action and state spaces. To resolve the computational challenge, we establish the submodularity of Bellman equation and apply the hill-climbing algorithm to achieve a $1-\frac{1}{e}$ approximation guarantee in Bellman updates. Lastly, we prove that the approximate Bellman updates are guaranteed to converge by a modified contraction analysis. We experimentally verify these results by developing an efficient Q-learning algorithm tailored to the networked setting. Experimental results on real-world graph data demonstrate that our Q-learning approach outperforms both $k$-step look-ahead and network-blind approaches, highlighting the importance of capturing and leveraging network effects where they exist.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。