技术摘要：基于上下文老虎机的联合 AP 探测与调度

问题定义

本文研究了在多个接入点（AP）协作服务单个移动客户端的场景下，如何高效分配无线资源。核心难点在于数据速率的不确定性：每个链路的容量遵循一个未知的分布，该分布会根据客户端的位置和环境因素（如遮挡、干扰）而变化。

不同于传统的链路调度问题（决策者必须在没有任何先验观测的情况下选择一条链路），这项工作假设了一个**联合探测与执行（joint probing and play）**的设定。在每个时间步，决策者可以探测有限数量的 $K$ 个 AP（其中 $K < N$，且 $N$ 为总 AP 数）以观测其瞬时奖励（数据速率），然后再选择一个单一的 AP 来服务客户端。其目标是通过学习一个最优策略来平衡探索（通过探测来学习分布）与利用（服务客户端），从而在时间跨度 $T$ 内最大化累积期望奖励。

作者将此建模为一个**带有探测的上下文老虎机（Contextual Bandit with Probing, CBwP）**问题。“上下文”是客户端的位置，“臂”（arms）是各个 AP。给定上下文 $x$ 时，臂 $a$ 的奖励分布 $\Phi(a|x)$ 是未知的。

方法论

1. 离线最优结构（MDP 建模）

在解决在线学习问题之前，作者首先分析了奖励分布已知的离线设定。他们将每个时间步的联合探测与执行决策建模为一个马尔可夫决策过程（MDP）。

• 状态： 已探测臂及其观测到的奖励的历史记录。
• 最优执行策略： 他们证明了对于任何探测历史，最优策略是确定性的：执行被探测臂中观测到最大奖励的臂，或者在未被探测的臂中执行具有最高期望奖励的臂。
• 最优探测策略： 对于特定的伯努利奖励情况（即奖励以概率 $\mu(a|x)$ 为 1，否则为 0），他们推导出了一个简单的非自适应最优策略：探测具有最高期望奖励 $\mu(a|x)$ 的 $K$ 个臂，如果其中没有产生 1 的奖励，则执行第 $(K+1)$ 个最优的臂。

2. 在线学习算法：上下文缩放（Contextual Zooming）

为了处理未知分布的在线设定，作者将上下文缩放算法（最初为标准上下文老虎机提出）扩展到了 CBwP 框架。

• 空间划分： 算法为每个 AP 维护一组“活跃球”（active balls）（即上下文空间中的区域）。初始时，整个空间由一个半径为 1 的单一球体覆盖。
• 指数计算： 对于每个球 $B$，算法计算一个指数 $I_t(B)$，该指数结合了平均观测奖励、球的半径以及一个置信项（上置信界 UCB 风格）。
• 每轮的三阶段决策过程：
  1. 探测规则： 算法选择最多 $K$ 个臂进行探测。它选择包含当前上下文 $x_t$ 的活跃球中，且与之关联的未探测臂中具有最高指数的臂。如果探测到一个奖励为 1 的臂（针对伯努利分布）或达到 $K$ 次探测后，探测会提前停止。
  2. 执行规则： 探测完成后，算法选择一个臂进行执行。如果被探测的臂产生了 1 的奖励，则执行该臂。否则，算法执行具有最高估计值的臂（无论是被探测的观测值，还是未被探测的指数）。
  3. 激活规则： 如果一个臂被探测或执行，算法会更新统计数据。如果当前球的置信半径小于该球的物理半径，则通过激活一个以当前上下文为中心、半径减半的新子球来对该球进行“缩放”（zoom in）。

3. 遗憾分析（Regret Analysis）

作者在伯努利奖励的假设下，为该算法建立了理论遗憾界（regret bound）。他们定义了“清洁运行”（clean runs）场景，即估计奖励与真实均值非常接近（处于置信区间内）的情况。通过限制“糟糕运行”（bad runs）的概率，并利用奖励函数相对于上下文距离的 Lipschitz 连续性来分析清洁运行期间的遗憾，他们推导出了一个取决于上下文空间覆盖数和探测限制 $K$ 的次线性遗憾界。

核心贡献

1. 新颖框架 (CBwP)： 本文引入了带有探测的上下文老虎机，这是对经典上下文老虎机模型的全新扩展，它明确地在“执行”阶段之前加入了“探测”阶段。这模拟了现实世界的约束，即在传输之前可以进行有限的信道探测（例如波束赋形）。
2. 结构性见解： 作者提供了离线最优解的结构性质，证明了对于伯努利奖励，贪婪的非自适应探测策略是最优的。
3. 算法设计： 他们提出了一种高效的在线学习算法，该算法将上下文缩放技术应用于联合探测/执行设定，处理了探测成本与信息增益之间的权衡。
4. 理论保证： 针对所提出的算法，在伯努利奖励情况下建立了正式的遗憾界。
5. 实验验证： 使用来自 802.11ad 测试床和毫米波信道模拟器的真实信道轨迹对方案进行了评估。

实验结果

评估是在“学生大厅”场景下进行的，使用 802.11ad 路由器和笔记本电脑，模拟在环境中移动的移动客户端。

• 基准测试： 将提出的 CBwP 算法与四个基准算法进行了比较：随机探测/随机执行 (RR)、随机探测/带探索的贪婪执行 (RG)、随机探测/不带探索的贪婪执行 (RG2)，以及贪婪探测/不带探索的执行 (GNE)。
• 性能表现：
  • 遗憾值： CBwP 始终比所有基准算法实现更低的累积遗憾。虽然基准算法的遗憾随 AP 数量增加而上升，但 CBwP 保持稳定。
  • 探测限制 ($K$)： 增加 $K$（允许的探测次数）会降低所有算法的遗憾，但无论 $K$ 如何变化，CBwP 都保持着显著优势。
  • 可扩展性： 随着 AP 数量 ($N$) 的增加，基准算法的性能下降，而 CBwP 展示了鲁棒性。
  • 动态环境： 该算法成功适应了进入房间此前未探索区域的新客户端，表现出向低遗憾快速收敛的能力。

意义与主张

论文声称 CBwP 模型 是对经典上下文老虎机框架的一种新颖扩展。其主要意义在于能够为那些在行动前可以获取部分信息（通过探测）的序列决策问题建模并求解，且这些问题存在不确定性。

作者断言，该框架可直接应用于下一代毫米波 WLAN（802.11ad/ay）中的联合波束赋形与调度，在这些场景中，全量波束赋形的成本过高，但有限的探测是可行的。此外，他们指出该模型在涉及联合探测与执行的其他领域也具有广泛的应用前景，例如：

• 组合多臂老虎机 (Combinatorial Multi-Armed Bandits)： 用于多 AP、多客户端的设置。
• 路网中的路径规划： 在这种场景下，搜索者可以在选择路径之前，向服务器查询有限的交通提示，从而在查询成本与旅行延迟之间取得平衡。

这项工作强调，虽然探测减少了不确定性，但并不能完全消除不确定性；因此，所提算法将探索机制同时整合到探测和执行两个阶段，对于实现最优性能至关重要。