提出一种多步展望的近似惠特尔索引方法，提升部分可观测强化学习中的决策精度。
From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
- 采用t步有限时域价值迭代计算动作优势，构建补贴依赖的阈值策略
- 在2715个三状态实例中全部验证为可索引，95%误差从0.0218降至0.000893
- 仅需两步展望即可恢复精确索引排序，适合高精度资源分配场景
惠特尔索引策略为不可观测的随机多臂老虎机问题提供可扩展解法，但在部分可观测情形下，确定单个信念下的无差异补贴需求解无限时域信念状态问题，且无闭式值函数。刘[10]通过线性化未知决策边界，建立线性系统并获得闭式近似惠特尔索引。但该阈值仅基于一步动作比较，忽略长期延续值。本文将该框架拓展至$ t $-步前瞻阈值策略：对每个补贴$ m $，阈值由$ t $-步有限时域值迭代下的主动-被动优势定义。当$ t=1 $时，阈值与$ m $无关，复现刘[10]的线性阈值；当$ t>1 $时，通过诱导首次穿越结构实现补贴依赖，并更贴近精确决策边界。所提算法无需输入可索引性，内置索引性验证。在原始惠特尔可索引条件下，证明$ t $-步近似惠特尔索引以几何速度收敛至精确索引，满足$ |\ widehat W_t(ω)-W(ω)|=O(β^t) $。数值实验表明，所有2,715个三状态实例均按新准则被验证为可索引。P95索引误差从$ t=1 $时的$ 2.18\times10^{-2} $降至$ t=8 $时的$ 8.93\times10^{-4} $。在$ β=0.9999 $的精确可比实例中，$ t=2 $已恢复精确索引排序。适度深度的阈值策略优于一步基线，且接近最优动态规划基准，运行时间随$ t $温和增长。
原文摘要 · Abstract (English)
Whittle index policies offer a scalable method for restless multi-armed bandits, but under partial observability even determining the indifference subsidy at a single belief requires solving an infinite-horizon belief-state problem with no closed-form value function. Liu [10] addresses this difficulty by linearizing the unknown decision boundary, leading to a linear system and a closed-form approximate Whittle index. However, the resulting threshold uses only a one-step active--passive comparison and does not account for longer-horizon continuation values. We extend this framework to a \emph{$t$-step lookahead threshold policy}. For each subsidy $m$, the threshold is defined by the active-minus-passive advantage under $t$-step finite-horizon value iteration. At $t=1$, the threshold is $m$-independent and recovers the linear threshold of Liu [10]; for $t>1$, it becomes subsidy-dependent through the induced first-crossing structure and tracks the exact decision boundary more closely. The proposed algorithm does not require indexability as an input and includes an indexability verification. Under the original Whittle indexability, we prove that the $t$-step approximate Whittle index converges geometrically to the exact Whittle index, \[ |\widehat W_t(ω)-W(ω)|=O(β^t). \] Numerically, all 2,715 tested three-state instances are verified as indexable according to the proposed criterion. The P95 index error decreases from $2.18\times10^{-2}$ at $t=1$ to $8.93\times10^{-4}$ at $t=8$. In an exact-comparable instance with $β=0.9999$, $t=2$ already recovers the exact Whittle-index ordering. Moderate-depth threshold policies also outperform the one-step baseline and remain close to the optimal dynamic-programming benchmark, while runtime grows mildly with $t$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。