Batched Stochastic Linear Bandits with 1-Bit Communication Constraints¶
会议: NeurIPS 2026
arXiv: 2605.30976
领域: 强化学习
关键词: 随机线性老虎机, 批处理观测, 1比特通信约束, G-最优实验设计, 阶段消除算法
一句话总结¶
本文研究了在批处理大小为 \(B\) 且每批仅允许智能体向学习者回传 1 比特量化反馈的随机线性老虎机问题，确立了无噪声下依然不可避免的 \(\Omega(B\min\{d,\log|\mathcal{A}|\})\) 通信遗憾下界，并设计了匹配该下界且近乎消除通信瓶颈的两套阶段消除算法。
研究背景与动机¶
随机线性老虎机（Stochastic Linear Bandits）作为序贯决策的核心范式，已被广泛应用于在线广告推荐、临床试验与边缘系统优化等场景。经典线性老虎机假定学习者每一步都能无损、实时地观测到连续奖励值。然而在分布式传感网络、物联网终端或联邦学习体系中，端侧设备受制于严苛的电池功耗与极度匮乏的上行通信带宽，且跨轮次难以维护长期本地记忆。现有的通信受限老虎机文献主要聚焦于两类极端假设：一类是每轮交互均通信但仅传输极少比特（如每步 3-4 比特的即时量化），另一类是假设端侧具有无限本地记忆、在全时间窗内自主决定通信时刻的全局比特预算模型。
这两种极端设定忽略了一个具有高度实用价值的“中间地带”——智能体在长度为 \(B\) 的批次内独立执行动作，但受限于内存与上行信道，在观察完整个批次的 \(B\) 个奖励后，只能向中心学习者回传单一比特（1-bit）的信息摘要。这种设定不仅对中心学习者提出了提前规划动作的强制性批处理约束，更使得有效通信速率被压缩至每轮 \(1/B\) 比特，远低于传统的逐轮量化设定。
这种双重约束引发的核心矛盾在于：极度的信息匮乏（1 比特摘要）与批处理延迟是否会导致线性老虎机的遗憾界不可逆转地恶化？如果可以克服，在不同臂集合规模 \(|\mathcal{A}|\) 与批次大小 \(B\) 下，算法能够达到的理论极限是什么？本文的核心 idea 是：证明纯粹由 1-bit 通信瓶颈引发的 \(\Omega(B\min\{d,\log|\mathcal{A}|\})\) 遗憾下界，并借助 G-最优设计与序列化 1-bit 均值估计技术，通过“安全臂识别 + 预热启动”解耦探索开销，使得单比特反馈即使在批次大至 \(B=\Theta(\sqrt{T})\) 时也能达到与无约束线性老虎机匹配的近最优遗憾界。
方法详解¶
整体框架¶
算法面向的系统交互分为中心学习者（Learner）与批处理无记忆智能体（Agent）。整个时间跨度 \(T\) 被划分为 \(M=\lceil T/B \rceil\) 个固定大小为 \(B\) 的批次。在每个批次 \(m\) 开始时，学习者发送预先确定的 \(B\) 个臂序列 \(A_{(m-1)B+1}, \dots, A_{mB}\) 以及一个 1 比特量化函数 \(Q_m: \mathbb{R}^B \to \{0, 1\}\)；智能体执行这 \(B\) 次拉取，观察连续奖励 \(Y\)，计算 \(Q_m(Y)\) 并回传单比特反馈。
为了在此极端受限通道下实现次线性遗憾，论文提出了统一的阶段消除（Phased Elimination）框架，并针对不同臂集规模演化出两套具体算法：针对指数级大动作集（\(|\mathcal{A}|\)-independent）的 Algorithm 1 与针对多项式/中小规模动作集（\(|\mathcal{A}|\)-dependent）的 Algorithm 2。整个技术流程如下图所示：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入: 动作集 A, 批次大小 B, 预算 T, 置信度 δ"] --> B{"判定批次规模<br/>B ≥ τ = 8K*d(log log d + 11)?"}
B -->|大批次且依赖 |A| | C["安全臂锦标赛识别<br/>二分淘汰获取近似最优 safe arm"]
C --> D["安全臂预热启动过滤<br/>以 safe arm 填补批次空闲槽位得到 A1"]
B -->|小批次或 |A| 独立| E["初始化全量活跃集 A1 = A"]
D --> F["计算 G-最优实验设计<br/>在活跃臂集 Ah 上求解紧凑核心支撑集"]
E --> F
F --> G["序列化 1 比特均值粗定位<br/>对核心臂执行二分/区间测试定位至 O(σ')"]
G --> H["截断与区域化精细估计<br/>多批次多阈值查询结合中位数消除长尾偏差"]
H --> I["参数重构与置信区间消除<br/>反传设计矩阵更新活跃集 Ah+1 并倍增精度"]
I -->|未耗尽预算 T| F
I -->|预算耗尽| J["终止输出并控制累积遗憾"]关键设计¶
1. 基于编码论与 Fano 不等式的纯通信遗憾下界
传统的线性老虎机统计下界 \(\Omega(\sqrt{dT\min\{d,\log|\mathcal{A}|\}})\) 源于噪声引起的假设检验不确定性。然而在 1-bit 批处理通道下，即便环境完全无噪声（\(\sigma = 0\)），信息吞吐量的刚性限制依然构成根本阻碍。论文利用 Gilbert-Varshamov 编码界在超球面上构造了彼此汉明距离不小于 \(d/4\) 的分离向量子集 \(\mathcal{V} \subset \{\pm 1/\sqrt{d}\}^d\)，其内积满足 \(\langle x, x' \rangle \leq 1/2\)。由于每个批次仅传输 1 比特，在经过 \(i-1\) 个批次后，学习者接收到的总历史信息量至多为 \(i-1\) 比特。根据 Fano 不等式，学习者在前 \(i\) 批中选中最优臂的先验后验互信息被硬性限制为 \(I(\Theta; \mathbf{Q}_{i-1}) \leq i-1\)，从而保证每次拉取以至少 \(1 - i/\log_2 K'\) 的概率犯错并承受恒定的次优间隙 \(\Delta = 1/2\)。将此通信下界与标准高斯统计下界正交相加，建立了该问题的基本性能基准： $\(\sup_{\|\theta\|_2 \leq 1} \mathbb{E}[R_T] = \widetilde{\Omega}\left(\min\left\{T, B\min\{d, \log|\mathcal{A}|\} + \sqrt{dT\min\{d, \log|\mathcal{A}|\}}\right\}\right)\)$
2. G-最优设计与 1-Bit 均值估计器的稳健协同
在每个阶段 \(h\)，算法不再依赖经典的加权最小二乘估计（因学习者无法获得未量化的连续观测），而是结合 Kiefer-Wolfowitz 定理求解近似 G-最优设计 \(\rho_h\)，保证核心支撑集大小 \(|\text{supp}(\rho_h)| \leq \widetilde{O}(d)\) 且满足 \(\max_{a \in \mathcal{A}_h} \|a\|_{G_h^{-1}}^2 \leq 2d\)。为估计这 \(O(d)\) 个核心臂的均值，论文引入两阶段 1-bit 机制：
首先通过 1BitLocalize 进行粗定位，借助带噪二分搜索与均值-中位数不等式 \(|\mathbb{E}[X] - M| \leq \sigma'\)，以对数级查询代价将每个支撑臂的均值锁定在宽度为 \(O(\sigma/\sqrt{B})\) 的高置信区间内；随后通过 1BitRefine 执行精细估计。为了在仅具二阶矩假设（重尾/非次高斯噪声）下保证指数级集中性，算法将精细估计划分至 \(K\) 个独立块，在块内利用随机阈值量化实现无偏积分估计，在块间应用 Median-of-Means（MoM）聚合适配，最终将估计截断偏置压低至 \(O(\sigma'/T^2)\)，方差控制在目标精度内。
3. 均匀分配与比例分配的对偶策略设计
在处理置信椭球传播与多臂集中性权衡时，论文针对大动作集与中小动作集提出了两种截然不同的分配范式： - 均匀分配（Algorithm 1）：在核心支撑集上无差别地分配样本量 \(u_h\)，使得每个标量均值估计的误差一致集中。此时，利用 Cauchy-Schwarz 不等式传播到任意活跃臂 \(b\) 的误差满足 \(\sum_{a} \rho_h(a) |b^\top G_h^{-1}a| \leq \sqrt{2d}\)，其联合界仅需跨越 \(O(d)\) 个支撑臂，产生 \(K = \widetilde{O}(\log(d/\delta))\) 个块，但付出了置信区间放大至 \(W_h = \sqrt{2d}\varepsilon_h\) 的代价。 - 比例分配（Algorithm 2）：将样本严格按设计权重 \(u_h(a) \propto \rho_h(a)\) 分配，使得每个臂的方差恰好反比于权重。在反传计算矩阵 \(G_h^{-1}\) 时，权重完全对消：\(\text{Var}(b^\top \hat{\theta}_h^{(j)}) \leq 2d\sigma^2/B\)，成功将置信宽度收紧至无损的 \(W_h = \varepsilon_h\)。但由于必须对所有活跃臂 \(b \in \mathcal{A}_h\) 的内积直接应用 MoM 集中，联合界必须扩展至整个动作集，使得块数上升至 \(K = \widetilde{O}(\log(|\mathcal{A}|/\delta))\)。
4. 大批次场景下的安全臂锦标赛与预热启动机制
当批次规模较大（\(B \geq \widetilde{\Omega}(d\log|\mathcal{A}|)\)）时，比例分配算法面临严重的初始探索过载：在第一阶段若直接进行均匀/全量测试，最大次优间隙为 \(O(1)\)，单步探索将招致高达 \(\widetilde{O}(dBK) = \widetilde{O}(dB\log|\mathcal{A}|)\) 的首轮遗憾，突破了通信下界。为了化解这一困境，算法设计了两步预处理机制： - 安全臂识别（SafeArm）：利用单批次容量充裕的特点，在单个批次内部同时执行 G-最优设计并就地计算样本均值。通过 \(\lceil \log_2 |\mathcal{A}| \rceil\) 轮二分淘汰锦标赛，智能体在端侧直接选出局部占优半区并仅用 1 比特汇报，最终以 \(O(B\log|\mathcal{A}|)\) 的拉取开销锁定一个次优间隙至多为 \(\Delta_{a_{\text{safe}}} \leq \widetilde{O}(\sqrt{d/B}\log^{3/2}|\mathcal{A}|)\) 的安全基准臂 \(a_{\text{safe}}\)。 - 安全臂预热启动（WarmStart）：执行单轮特殊阶段消除，其中核心支撑臂仅拉取 \(u_0(a) = \lceil B\rho_0(a) \rceil\) 次，整个批次中剩余的 \(B - u_0(a)\) 个空闲槽位全部由安全臂 \(a_{\text{safe}}\) 填充。该机制解耦了批次硬性大小与统计探索量的强绑定，将进入正式消除阶段 \(\mathcal{A}_1\) 的所有候选臂的最大次优间隙先验压缩至 \(O(\sqrt{d/B})\)，使得首阶段探索遗憾从 \(\widetilde{O}(dB\log|\mathcal{A}|)\) 骤降至 \(\widetilde{O}(d^{3/2}\sqrt{B}\log^{5/2}|\mathcal{A}|)\)。
一个完整示例¶
考虑一个动作集规模为 \(|\mathcal{A}|=16\)、特征维度 \(d=2\) 的多项式规模问题，假设批次大小 \(B=1000\) 满足大批次条件。算法 2 的执行过程如下： 1. 安全臂识别：初始活跃集 16 个臂，智能体在单个批次中按照 G-最优设计分配这 16 个臂的拉取次数。计算各臂均值后将候选集均分为两组 \(\mathcal{G}_A, \mathcal{G}_B\)，回传 1 比特指示 \(\max \hat{\mu}_A \geq \max \hat{\mu}_B\)。经过 \(\log_2(16) = 4\) 个批次（共消耗 \(4B = 4000\) 步，回传 4 比特），候选集被收缩为单臂 \(a_{\text{safe}}\)，其理论次优差距被压低在 \(\widetilde{O}(\sqrt{2/1000}) \approx 0.045\) 量级。 2. 预热启动：在全集 \(\mathcal{A}\) 上求解设计 \(\rho_0\)，得到极少数核心支撑臂。每个批次中，核心臂仅执行必要的 \(u_0(a)\) 次测量，剩余的数百个槽位全部拉取已知表现良好的 \(a_{\text{safe}}\)。阶段结束时剔除经验差距超过阈值的臂，得到初始活跃集 \(\mathcal{A}_1\)，此时保证保留最优臂且所有留存臂次优差距严格小于 \(0.1\)。 3. 主消除循环：以 \(\mathcal{A}_1\) 启动阶段消除，每阶段精度倍增 \(\varepsilon_h = \sigma 2^{-h}/\sqrt{B}\)，置信宽度 \(W_h = \varepsilon_h\)。因为初始差距极小，算法在极低探索代价下迅速收敛并锁定最优臂。
实验关键数据¶
理论结果横向对比（主结果）¶
论文给出的核心理论贡献是严格的极小化极大遗憾上界，与无通信约束及标准批处理延迟基线在不同参数尺度下的对比如下表所示（设 \(\sigma = \Theta(1)\)，隐藏多项式对数因子）：
| 算法 / 理论设定 | 通信机制 | 批次模式 | 动作集约束 | 累积遗憾界 \(\widetilde{O}(\cdot)\) | 理论最优性匹配 |
|---|---|---|---|---|---|
| 标准线性老虎机 (Dani et al., 2008) | 无限制 (完全精度) | 逐轮更新 (\(B=1\)) | 任意紧集 | \(d\sqrt{T}\) | 极小化极大最优 |
| 有限动作集无约束 (Auer, 2002) | 无限制 (完全精度) | 逐轮更新 (\(B=1\)) | 有限集合 $ | \mathcal{A} | $ |
| 延迟反馈基线 (Vakili et al., 2023) | 无限制 (完全精度) | 延迟/批次 \(B\) | 有限集合 $ | \mathcal{A} | $ |
| 非混合式基线 (Non-Mixing LB) | 1-bit / 甚至精确值 | 单臂整批 (\(B\)) | 标准正交基 | \(\Omega(dB)\) | 出现 \(d\) 倍通信恶化 |
| 本文 Algorithm 1 | 每批严格 1 比特 | 任意固定 \(B\) | 任意/指数级 $ | \mathcal{A} | $ |
| 本文 Algorithm 2 (小批次) | 每批严格 1 比特 | \(B < \widetilde{O}(d\log\|\mathcal{A}\|)\) | 多项式 $ | \mathcal{A} | $ |
| 本文 Algorithm 2 (大批次+预热) | 每批严格 1 比特 | \(B \geq \widetilde{\Omega}(d\log\|\mathcal{A}\|)\) | 多项式 $ | \mathcal{A} | $ |
尺度敏感度与下界差距分析（消融与区域验证）¶
针对 Algorithm 2 在多项式动作集 \(|\mathcal{A}| = \text{poly}(d)\) 下的初始化惩罚项 \(\widetilde{O}(d^{3/2}\sqrt{B})\)，论文给出了不同时间跨度 \(T\) 与批次大小 \(B\) 组合下的理论次优性差距（Gap Ratio）分析表：
| 参数缩放区间条件 | 初始化项是否被吸收 | 主导遗憾项 | 理论下界 \(\mathrm{LB}(B,T,d)\) | 算法遗憾与下界比值 \(\frac{\mathbb{E}[R_T]}{\mathrm{LB}}\) | 收敛状态 |
|---|---|---|---|---|---|
| 超大批次: \(B = \Omega(d^3)\) | 是 (\(d^{3/2}\sqrt{B} \leq O(B)\)) | \(O(B)\) | \(\widetilde{\Omega}(B + \sqrt{dT})\) | \(\widetilde{O}(1)\) | 极小化极大紧致 |
| 长视界大时间跨度: \(T = \Omega(d^2B)\) | 是 (\(d^{3/2}\sqrt{B} \leq O(\sqrt{dT})\)) | \(O(\sqrt{dT})\) | \(\widetilde{\Omega}(B + \sqrt{dT})\) | \(\widetilde{O}(1)\) | 极小化极大紧致 |
| 超长时域保底: \(T = \Omega(d^5)\) | 恒成立 (自动满足前两者之一) | \(B + \sqrt{dT}\) | \(\widetilde{\Omega}(B + \sqrt{dT})\) | \(\widetilde{O}(1)\) | 极小化极大紧致 |
| 中等难度区间: \(T = \Omega(dB) \land T = O(d^2B)\) | 否 (惩罚项占据微弱主导) | \(d^{3/2}\sqrt{B}\) | \(\widetilde{\Omega}(B + \sqrt{dT})\) | 至多 \(\widetilde{O}(\sqrt{d})\) | 极温和退化 |
| 极短信息匮乏区间: \(T = O(dB)\) | 算法早期阶段终止 | \(O(T)\) | \(\widetilde{\Omega}(B + \sqrt{dT})\) | 至多 \(\widetilde{O}(\sqrt{d})\) | 理论保证上界可控 |
关键发现¶
- 1-bit 通信的极限容量：当批次大小缩放至 \(B = O(\sqrt{T})\) 时，两个算法的通信惩罚项 \(B\log|\mathcal{A}|\) 或 \(dB\) 均被主导统计误差项 \(O(d\sqrt{T})\) 或 \(O(\sqrt{dT\log|\mathcal{A}|})\) 完美吸收。这证明：平均每 \(\sqrt{T}\) 步仅传输 1 个比特，系统性能与无限制全精度通信下的线性老虎机完全一致。
- 混合策略的必要性（Non-mixing 的代价）：定理 2 证明若算法在单个批次内强行拉取相同臂，其遗憾将不可避免地下沉至 \(\Omega(dB)\)；而 Algorithm 2 借助批次内多臂混合设计与安全臂槽位填充，打破了这一屏障，将通信代价值拉回至近乎最优的 \(O(B\log|\mathcal{A}|)\)。
- 重尾稳健性：整个框架仅需奖励噪声具备有界二阶矩 \(\mathbb{E}[\xi_t^2] \leq \sigma^2\)，无需常见的亚高斯（sub-Gaussian）假设，在中位数与截断量化机制的配合下维持了对重尾扰动的天然鲁棒。
亮点与洞察¶
- 信息论与极小极大决策的优美交融：利用 Gilbert-Varshamov 码本构造将连续空间线性臂映射为离散通信信道，严格揭示了纯粹由信道容量限制引发的无噪声物理遗憾下界，填补了老虎机通信复杂度的理论空白。
- 批次内部异质动作填充的巧思：在固定大批次场景下，发明了以 safe arm 吸收空闲测量槽位的机制，既满足了系统对固定批长 \(B\) 的工程约束，又在数学上解耦了有效统计量与冗余拉取。
- 分层级、抗偏置的 1-bit 估计范式：将基于对数尺度的粗区间快速搜索（Localize）与基于几何分割的多重随机阈值量化（Refine）组合，成功将单比特量化偏差严格限制在 \(O(1/T^2)\)，彻底规避了累积偏置对多阶段消除算法的系统性破坏。
局限与展望¶
- 中等尺度下的理论代沟：在动作集为多项式规模且视界处于 \(T \in [d, d^5]\) 的狭窄区域时，算法仍残留 \(\widetilde{O}(\sqrt{d})\) 的理论遗憾间隙，未来需探索更紧凑的自适应实验设计消除该初始化惩罚。
- 下行信道的对称性约束：模型假设中心学习者向下分发动作与量化规则的下行链路无限宽带，在极度对称的双向受限网络中需进一步压缩下行规则的描述比特。
- 上下文（Contextual）场景的拓展难题：当前结论建立在固定紧凑动作集上，对于每步环境动态变更的上下文线性老虎机，批处理与 1-bit 反馈的耦合将导致协方差矩阵历史失配，需要新的自适应在线设计。
相关工作与启发¶
- vs Hanna et al. (2022) / Mitra et al. (2023)：先前工作要求智能体每一步（\(B=1\)）回传数个比特（例如 3-4 bits）量化奖励或参数更新；本文将通信频率降低至每 \(B\) 步仅 1 比特，允许更低功耗的间歇式物联网交互。
- vs Salgia & Zhao (2023) / Amani et al. (2023)：既有分布式通信老虎机要求节点拥有无限内存以累积全局状态并自适应触发通信；本文聚焦于“批次间完全无记忆”（batch-wise memoryless）的传感器与边缘设备，系统架构更易解耦。
- vs Cesa-Bianchi et al. (2013) / Gao et al. (2019)：经典批处理老虎机侧重于研究变长批次网格（如几何递增批次）对探索轮数的压缩；本文直面现实中更为普遍的等长固定批次，系统刻画了固定窗口延迟叠加 1 比特约束的复合瓶颈。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次提出并严格解决了批处理与 1 比特极端通信约束交织的线性老虎机问题，建立了全新的通信极小极大下界。
- 理论充分度: ⭐⭐⭐⭐⭐ 涵盖无噪声通信下界、非混合下界、两套互补算法的上界，并在全尺度空间完成了精密的次优性闭环审计。
- 写作质量: ⭐⭐⭐⭐⭐ 叙述严谨，附录推导层层递进，定理构造与直觉阐释高度自洽。
- 价值: ⭐⭐⭐⭐⭐ 为边缘智能计算、去中心化传感网络与隐私通信下的序列决策提供了极具指导意义的理论基准与原型算法。