针对稀缺资源每次只能分配一次的场景，提出高效索引策略。
Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation
- 用虚拟状态扩展系统，强制每臂仅可触发一次
- 首次证明平均最优差距以√ρ衰减，优于传统方法
- 适合医疗干预等资源极度稀缺的决策场景
在许多实际应用中，如医疗干预项目，资源极为稀缺，每个个体最多只能获得一次资源。标准的多臂赌博机（RMAB）框架在此类场景下表现不佳。为此，本文提出有限时域单次触发赌博机（SPRMAB），其中每条臂仅允许被触发一次。这一约束引入了额外复杂性，导致现有大多数RMAB解决方案失效或次优。我们通过引入虚拟状态来扩展系统，确保一旦某臂被激活，其状态转移将仅限于虚拟状态。在此基础上设计了一种轻量级索引策略。首次证明该策略在有限臂数下，平均最优差距以$ ilde{ ext{O}}ig( rac{1}{ ho^{1/2}}ig)$的速率子线性衰减，其中ρ为每簇臂的缩放因子。大量仿真验证了该方法在多种场景下的稳健性能，显著优于现有基准。
原文摘要 · Abstract (English)
Restless multi-armed bandits (RMABs) have been highly successful in optimizing sequential resource allocation across many domains. However, in many practical settings with highly scarce resources, where each agent can only receive at most one resource, such as healthcare intervention programs, the standard RMAB framework falls short. To tackle such scenarios, we introduce Finite-Horizon Single-Pull RMABs (SPRMABs), a novel variant in which each arm can only be pulled once. This single-pull constraint introduces additional complexity, rendering many existing RMAB solutions suboptimal or ineffective. %To address this, we propose using dummy states to duplicate the system, ensuring that once an arm is activated, it transitions exclusively within the dummy states. To address this shortcoming, we propose using \textit{dummy states} that expand the system and enforce the one-pull constraint. We then design a lightweight index policy for this expanded system. For the first time, we demonstrate that our index policy achieves a sub-linearly decaying average optimality gap of $\tilde{\mathcal{O}}\left(\frac{1}{ρ^{1/2}}\right)$ for a finite number of arms, where $ρ$ is the scaling factor for each arm cluster. Extensive simulations validate the proposed method, showing robust performance across various domains compared to existing benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。