提出新方法，让退化多臂赌博机的误差降至1/N量级。
Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation
- 用高斯随机系统同时捕捉均值与方差，改进传统平均近似。
- 在退化情形下实现约1/N的最优差距，优于旧方法的1/√N。
- 适合研究动态资源分配或强化学习中需高精度策略的场景。
研究具有N个同质臂的有限时域非平稳多臂赌博机（RMAB）问题。已有研究发现，当RMAB满足非退化条件时，基于流体近似的线性规划策略可实现指数级小的最优差距。然而，实际中RMAB常为退化情形，此时基于流体近似的策略会产生每臂Θ(1/√N)的最优差距。本文提出一种新型基于随机规划（SP-based）的策略，在唯一性假设下，对退化RMAB实现了˜𝒪(1/N)的最优差距。该方法通过构建一个能同时捕捉系统均值与方差的高斯随机系统，获得比流体近似更精确的逼近，再求解该系统的随机规划以得到策略。这是首个在退化情形下建立˜𝒪(1/N)最优差距的结果。
原文摘要 · Abstract (English)
We study the finite-horizon Restless Multi-Armed Bandit (RMAB) problem with $N$ homogeneous arms. Prior work has shown that when an RMAB satisfies a non-degeneracy condition, Linear-Programming-based (LP-based) policies derived from the fluid approximation, which captures the mean dynamics of the system, achieve an exponentially small optimality gap. However, it is common for RMABs to be degenerate, in which case LP-based policies can result in a $Θ(1/\sqrt{N})$ optimality gap per arm. In this paper, we propose a novel Stochastic-Programming-based (SP-based) policy that, under a uniqueness assumption, achieves an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs. Our approach is based on the construction of a Gaussian stochastic system that captures not only the mean but also the variance of the RMAB dynamics, resulting in a more accurate approximation than the fluid approximation. We then solve a stochastic program for this system to obtain our policy. This is the first result to establish an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。