非平稳多臂老虎机与非完美二元反馈：PCL-可索引性分析与计算

# 具有不完美二元反馈的不安分老虎机：PCL-可索引性分析与计算

来源：https://arxiv.org/html/2606.11192

José Niño-Mora  
Departamento de Estadística  
Universidad Carlos III de Madrid  
28903 Getafe (Madrid), Spain  
[email protected] (https://arxiv.org/html/2606.11192v1/mailto:[email protected])  
https://alum.mit.edu/www/jnimora  
http://orcid.org/0000-0002-2172-3983

作者的工作部分得到了卡洛斯三世大学（UC3M）内部研究计划资助和研究工具购置资助的支持。（提交于2026年3月27日）

###### 摘要

我们研究了具有二元潜在状态和不完美二元反馈的不安分老虎机，其动机来自于存在感知误差的机会频谱接入。针对相关的信念状态模型，我们开发了一个基于部分守恒律（PCL）的分析与计算框架，用于建立可索引性并评估Whittle指数，该框架建立在实数状态折扣不安分老虎机的验证定理之上。该框架通过一个相关的确定性骨架、更新分解以及单词组合学来分析随机动力学。它在几个阈值区域中为折扣奖励和资源度量提供了易处理的表达式，从而能够在那里完全验证PCL可索引性条件。对于剩余区域（本文未进行完整分析验证），我们推导出有效的数值方案来计算相关的边际度量和边际生产率（MP）指数，当这些条件成立时，该指数等于Whittle指数。大量的计算实验提供了强有力的证据，表明这些条件在该区域以及广泛的参数范围内也成立，且没有先前工作中施加的严格参数限制。实验进一步表明，MP指数策略通常优于标准基准策略，并且往往有显著的优势。

关键词：不安分多臂老虎机；部分可观测性；感知误差；Whittle指数；可索引性；守恒律；机会频谱接入

## 1 引言

### 1.1 背景与动机

许多顺序资源分配问题涉及一组随机演化的实体，这里称为*项目*，其潜在状态仅被部分观测到。在每个离散时间段内，控制器只能激活有限数量的项目，从而获取信息并可能获得奖励。我们考虑一个实际相关的设置，其中每个项目的潜在状态是二元的（坏/好），激活会产生不完美的、*单侧*的二元ACK/NACK反馈：ACK确认了一个好的状态并立即获得奖励，而NACK（未观察到成功）不产生奖励并且本质上是模糊的，因为它即使在潜在状态为好时也可能发生。由于项目在未被选择时会继续演化，控制器必须平衡即时利用与信息收集和未来机会。这种探索-利用权衡自然导致了*不安分多臂老虎机问题*（RMABP），这是一个由Whittle[36]引入的广泛研究的建模框架；参见，例如，[17; 22; 23; 15; 19; 5]了解部分观测不安分老虎机的代表性工作，以及[32]了解更广泛的综述。

我们研究一个部分观测的RMABP，其中N个N个项目，标记为 n ∈ 𝒩 ≜ {1, ..., N}，具有作为马尔可夫链外生演变的二元潜在状态，且独立于控制器的动作。在每个时间段内，控制器选择要激活哪些项目，受限于激活容量约束；未选择的项目是被动的。被动的动作既不产生反馈也不产生奖励，相应的信念状态使用潜在状态动态进行预测性更新。相比之下，当项目n被激活时，它会在潜在状态为好以概率 0 < κ_n < 1 生成一个ACK，并且ACK产生奖励 r_n > 0。在观察到ACK/NACK后，控制器通过贝叶斯规则更新其后验信念。

设 X_n(t) ∈ [0,1] 表示项目n在时段t开始时处于好状态的后验概率。向量 **X**(t) = (X_n(t))_{n∈𝒩} 是一个充分统计量，因此整个控制问题成为信念状态空间上的一个高维*马尔可夫决策过程*（MDP），由部分可观测性[16]引起。由于信念状态RMABP通常难以精确求解，本文的主要目标是利用该模型的特殊结构——动作无关的潜在状态转移、单侧ACK/NACK反馈以及ACK相关奖励——将Niño-Mora[31]提出的基于*部分守恒律*（PCL）的验证定理应用于此设置。该定理为折扣实数状态不安分老虎机提供了可索引性和Whittle指数评估的充分条件。在几个阈值区域中，我们获得了所需*PCL可索引性条件*的完整分析验证。对于剩余区域（完整分析尚未实现），我们推导出有效的计算方案，并利用它们提供广泛的数值证据表明这些条件也成立。我们进一步计算了相关的*边际生产率*（MP）指数，在PCL条件下该指数等于Whittle指数。

这种问题结构受到几个现代工程应用的启发。认知无线电网络中的*机会频谱接入*（OSA）是一个自然的例子。每个项目对应一个主用户（PU）信道，其可用性演变为二态马尔可夫链，控制器在每个时段内感知多达M个信道。在感知误差和外生冲突容忍约束下，次用户（SU）使用感知结果来决定是否传输。根据Chen等人[10]的分离原理，访问决策在给定感知结果时是近视最优的，因此感知误差对每个信道的影响可以在我们的简化模型中用一个参数 κ_n 来概括，该参数是信道n可用时的最大可行传输概率。这种感知-访问机制在我们的模型中引入了单侧反馈结构：ACK确认信道可用，而 κ_n 决定了有效的ACK-给定-可用概率。详见第2.2节。类似的模型也出现在链路或服务器探测问题中，其中控制器顺序测试或选择时间变化的资源（其可用性外生演变）并且仅在成功传输或服务时获得奖励；参见，例如，[17; 24]。另一个例子是分布式设备中的远程诊断，其中成功的心跳检查确认存活，而失败的检查虽然模糊但具有信息量；参见，例如，[9; 2]。

### 1.2 部分观测不安分老虎机、Whittle指数和OSA的相关工作

与本文最相关的相关工作分为三个方向：(i) 针对具有二元马尔可夫信道的OSA的部分观测MDP（POMDP）公式和结构结果；(ii) 针对连续信念状态的感知和调度问题的Whittle指数方法；(iii) 关于不完美二元反馈下的阈值最优性和可索引性的结果，包括最接近本文研究的单侧ACK/NACK设置的工作。

#### 1.2.1 OSA作为信念状态POMDP

部分观测二元马尔可夫系统的控制自然地被公式化为信念状态MDP，即一个POMDP，其充分统计量是好状态的后验概率。在OSA文献中，早期工作研究了单信道上的最优传输——通常在Gilbert–Elliott模型下——并建立了阈值策略的最优性等结构性质[14]。后续工作考虑了感知误差和时间，以及通过约束POMDP公式和启发式方法处理延迟或能量成本[13]，而具有感知误差和冲突约束的多信道OSA在[37]中被公式化为一个POMDP。一个关键的后期发展是Chen等人[10]的*分离原理*，该原理在一大类不完美感知OSA模型中将感知和访问决策解耦。

#### 1.2.2 从POMDP到RMABP和Whittle指数

由于此类POMDP通常难以精确求解，大量文献利用其作为具有连续信念状态的RMABP的结构。在经典的*静止*情况下，Gittins指数产生最优指数策略[12]，但OSA以及许多监控和调度问题是*不安分*的。这激发了*Whittle指数*[36]的使用，它提供了一个可扩展的启发式策略，并且通常伴随可计算的性能界限。在OSA中，Ahmad等人[4]建立了*近视感知*最优的条件，而Liu和Zhao[17]在完美感知情况下建立了*可索引性*并推导了闭式Whittle指数表达式。相关的不完美检测模型在[18]中进行了分析，尽管那里没有讨论可索引性。更广泛地说，具有不完美、有限或受限观测的不安分老虎机已经在涵盖OSA类型模型的框架中进行了研究，包括隐马尔可夫和受限反馈公式[22; 23; 15]，以及旨在不完美反馈下实现低复杂度Whittle指数计算的方法[19]。最近的工作还考虑了数据驱动和风险感知的RMAB扩展[20; 21]；另见[1; 5]。

#### 1.2.3 不完美二元反馈下的最相关工作

与我们的设置最密切相关的工作解决了信念状态RMABP在（通常带有参数限制）不完美二元反馈下的阈值最优性和/或Whittle可索引性。
Meshram等人[23]研究了一个更广泛的模型，允许动作相关的转移，并引入了*近似可索引性*。他们的阈值最优性和可索引性结果仅在严格的参数限制下成立；当专门应用于我们的设置时，这些限制简化为低自相关（0 ≤ ρ ≤ 1/5）和强折扣（β < 1/3）。
Wang等人[35]研究了我们模型的OSA特例，并提出了一种不动点/区域划分分析来研究诱导的非线性信念动态，并结合分段线性化论证来支持可索引性和闭式指数表达式。他们的处理强调了分段阈值动态的作用，但跨区域边界的几个连续性和单调性问题仅被隐式处理。后续工作Wang和Chen[34, Ch. 3]提供了更多细节。他们的分析集中于确定性信念更新映射 φ^0 和 φ^1（见第4.1节）的选定迭代。相比之下，我们设置中阈值策略生成这些映射的更广泛混合组合，以及单侧模型中ACK诱导的重置，而这种更丰富的结构驱动了所得度量的分段和不连续行为。他们的充分感知误差条件，以虚警概率 ε 表示（其中 κ = 1 - ε），在我们符号中特化为 ε ≤ p_{01}p_{10} / ((1-p_{01})(1-p_{10})). 当 ρ > 0 时，这可能相当严格，因为右侧可以任意小。
Kaza等人[15]研究了一个具有ACK/NACK反馈和稀疏观测的隐状态RMABP。他们在强条件下建立了单项目子问题的阈值最优性（定理1），要求低自相关（0 < ρ < 1/3）和折扣因子 β ≤ 1/2。此外，他们的可索引性分析（定理2）对每个项目施加了一个额外的单调性条件（条件(B.1)），该条件依赖于κ；当 ρ ≥ 1/3 时，该条件可能要求 κ 接近1/2。总之，现有工作要么为可索引性提供了严格的充分条件（通常排除本领域核心的中到高自相关情况），要么依赖于不完全严谨的分析论证。本文旨在填补这一空白。