NeurIPS 2026 强化学习上下文多臂老虎机 (Contextual Bandits) 量化加性表示 (Additive Representations) 梯度提升老虎机 (Gradient-Boosted Bandits) 有界内存 (Bounded Memory)

Bandits via Additive Quantized Representations¶

会议: NeurIPS 2026
arXiv: 2610.02440
论文: https://arxiv.org/abs/2610.02440
代码: https://github.com/atavory/rqb
领域: 强化学习
关键词: 上下文多臂老虎机 (Contextual Bandits)、残差量化 (Residual Quantization)、加性表示 (Additive Representations)、梯度提升老虎机 (Gradient-Boosted Bandits)、有界内存 (Bounded Memory)

一句话总结¶

将检索领域的残差量化（RQ）码本重塑为上下文老虎机的非线性表征层，结合级联梯度提升与影子模型在线深度自适应，以严格恒定的 $\mathcal{O}(1)$ 内存开销和极低单步延迟实现了比肩重放缓冲树模型及神经网络老虎机的拟合质量。

研究背景与动机¶

在上下文多臂老虎机（Contextual Bandits）的实际工业部署中，算法必须在实时在线决策、非线性奖励建模能力与计算/存储资源开销之间做出权衡。现有的树集成方法（如 TETS、XGBoost）与深度神经网络老虎机（如 NeuralUCB、NeuralTS）虽然能够灵活拟合复杂的非线性奖励面，但普遍依赖于在线重放缓冲区（Replay Buffer）进行周期性全量重训。随着交互步数 $T$ 的线性累积，其内存消耗呈现 $\mathcal{O}(T)$ 的无界爆炸增长——例如在 500 万轮交互的 28 维特征任务上，指数倍增重训的 XGBoost 需要吞噬超过 1 GB 的重放内存，并引发剧烈的计算抖动。与之相对，经典的线性模型（如 LinTS、LinUCB）尽管能够基于新样本实现严格 $\mathcal{O}(1)$ 内存增量更新，却受限于严格的线性奖励假设，在面对非线性规律明显的真实数据时拟合能力严重匮乏。

这种“非线性表达力与严格有界内存不可兼得”的二元割裂，构成了长久以来的核心工程与理论瓶颈。如果在离线阶段将特征空间做均匀网格或平面聚类（如直方图/分桶老虎机），精细划分出的 $b^\ell$ 个空间单元会导致样本被过度切分（Data Fragmentation/Starvation），每个单元仅能获取极少数观测样本更新，引发极高的勘探方差；若划分过粗，则无法捕捉非线性细节。

面对大量未标注上下文廉价可得、而在线交互奖励代价高昂的现实场景，本文的切入角度是：将信息检索中用于高效向量压缩的残差量化（Residual Quantization, RQ）码本改造为老虎机层级表征。通过离线无监督 $k$-means 学习多层残差聚类中心并冻结，在线阶段借助梯度提升（Gradient Boosting）拟合多层伪残差目标，仅用 $\ell b$ 个共享参数即可跨单元复用信息并精细分辨 $b^\ell$ 个离散网格。核心 idea：将离线训练的冻结残差量化码本作为上下文表征层，通过多层残差级联提升拟合非线性奖励，并结合统计显著性检验的影子机制实现在线深度自适应，以严格恒定的 $\mathcal{O}(1)$ 内存达到与无界重放神经网络和树模型相媲美的累积遗憾。

方法详解¶

整体框架¶

算法分为离线码本预训练与在线梯度提升决策两个阶段。离线阶段利用无标签上下文数据集（规模 $n_{\text{rq}}$），通过逐层迭代的无监督 $k$-means 训练包含 $\ell_{\max}$ 层、每层 $b$ 个质心的 RQ 码本并永久冻结。在线阶段，当环境观测到连续上下文 $x_t \in \mathbb{R}^d$ 时，RQ 编码器逐层贪心匹配质心并扣除残差，生成每层的离散码字索引 $k_i \in [b]$ 与层级残差向量 $x_t^{(i-1)}$。老虎机对每个候选动作 $a \in [K]$ 聚合各层基学习器的汤普森采样（Thompson Sampling）打分，选取打分最高的动作执行并接收反馈奖励 $r_t \in \{0, 1\}$。随后，系统以级联残差形式计算各层伪目标（Pseudo-target）并更新各层参数；同时，在激活深度 $\ell_{\text{act}}$ 的基础上并行维护一个不干扰在线决策的 $\ell_{\text{act}}+1$ 层“影子模型”（Shadow Model），在预定的倍增检验周期执行 Freedman 鞅差显著性检验，一旦影子模型显著降低预测方差即触发提升（Promotion）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["观测上下文 x_t"] --> RQ["残差量化编码 (RQ Codebook)<br/>生成层级索引 k_i 与残差 x_t^(i-1)"]
    RQ --> Base["层级基学习器打分与动作选择<br/>加性聚合多层采样分数选取 a_t"]
    Base --> Env["环境交互与即时奖励<br/>执行动作 a_t 观察奖励 r_t"]
    Env --> Boost["层级残差级联提升更新<br/>计算伪残差目标并增量更新 active 模型"]
    Boost --> Shadow["影子模型并行训练与自适应检验<br/>无开销被动更新并在检验点判定 promotion"]

关键设计¶

1. 残差量化加性表征编码：以 $\ell b$ 参数解析 $b^\ell$ 有效网格空间
针对传统平面空间网格划分导致的样本稀疏与参数爆炸痛点，本文利用无监督 RQ 码本构建多层粗到细的几何逼近。对于输入上下文 $x^{(0)} = x_t$，各层 $i = 1, \dots, \ell_{\max}$ 依次选取距离当前残差最近的质心编号，并更新下一层残差： $$k_i = \arg\min_{k \in [b]} \|x^{(i-1)} - c_k^{(i)}\|^2, \qquad x^{(i)} = x^{(i-1)} - c_{k_i}^{(i)}$$ 该设计使深度为 $\ell$、每层 $b$ 个质心的码本能够表达高达 $b^\ell$ 个空间单元，但每个动作在所有层级上的参数总量仅为 $\mathcal{O}(\ell b)$（或在带线性特征时为 $\mathcal{O}(\ell b d^2)$）。每次交互都会同时为激活的 $\ell$ 个层级对应的质心提供数据更新，实现了跨单元的全局信息池化（Information Pooling），从根本上避免了细粒度单元的数据饥饿问题。

2. 伪目标级联提升机制：在线拟合逐层递减的残差缺口
为将多层离散与连续残差融合成非线性决策函数，算法借鉴了 Friedman 梯度提升机的思路，将浅层未解释的预测误差作为深层的拟合目标。令截断激活函数为 $\sigma(z) = \text{clip}(z + 0.5, 0, 1)$，各层以衰减系数 $\eta \in (0, 1]$ 组合后验均值 $\hat{\mu}_i$。对于已执行的动作 $a_t$，第 $i$ 层的伪残差目标定义为真实奖励减去前 $i-1$ 层的累加预测： $$\tilde{r}_i = r_t - \sigma(\hat{y}_{i-1}), \qquad \hat{y}_i = \hat{y}_{i-1} + \eta^{i-1} \hat{\mu}_i, \quad (\hat{y}_0 = 0)$$ 各层基学习器独立接收对应的层级输入特征 $x_t^{(i-1)}$ 与伪目标 $\tilde{r}_i$ 进行增量递推。随着深度增加，伪目标的方差呈几何级数递减，高层专注于校准微小的局部非线性非对称扰动。

3. 三重基学习器阵列与自洽理论保证：兼顾轻量计数与高维全协方差
算法抽象了三种针对不同算力与内存预算的基学习器变体 $\mathcal{M}$，并在特征残差向量末尾拼接常数偏置项 $[x^{(i-1)}; 1]$ 保证模长下界 $\|\phi_i(x)\| \ge 1$： - TS-RQ：完全舍弃连续特征，每个质心仅维护观测计数 $n$ 与奖励累加和 $s$，单轮开销仅为 $\mathcal{O}(\ell K)$，完全免除矩阵求逆； - SGD-LinTS-RQ：维护对角精度矩阵 $p \in \mathbb{R}^{d+1}$ 和充分统计量 $f$，单轮开销 $\mathcal{O}(\ell d K)$，实现坐标解耦的局部线性建模； - LinTS-RQ：利用 Sherman-Morrison 递归公式在线更新全精度协方差逆矩阵 $B^{-1}$，单轮开销 $\mathcal{O}(\ell d^2 K)$。各层正则化参数按 $\lambda_i = \lambda \cdot 0.25^{i-1}$ 缩放并辅以数值扰动以确保 Cholesky 分解数值鲁棒性。
理论层面，论文证明了只要基学习器满足最终有界性、饥饿状态正方差探索性以及渐进鲁棒一致性三项性质，渐进平均遗憾严格受限于加性误设误差 $\Delta_\ell(\mathcal{M})$，且在重构误差与加性交互尾项满足几何收缩假设时，误设误差以 $\mathcal{O}(\rho^\ell)$ 几何速率逼近不可约下界 $\delta_\infty$。

4. 鞅差驱动的影子提升机制：零决策干扰的在线自适应深度选择
面对不同数据集对模型深度需求的异构性，固定深度容易造成欠拟合或过拟合。算法构建了一种被动旁路“影子模型”（位于 $\ell_{\text{act}} + 1$ 层），其在线接收伪目标更新，但绝不参与当轮动作打分采样，从而避免了类似 CORRAL 等算法引入的 $\tilde{\mathcal{O}}(\sqrt{M})$ 模型选择遗憾惩罚。在预先设定的指数倍增检验点 $t \in \{T_0, 2T_0, 4T_0, \dots\}$（其中 $T_0 = 50 \cdot b \cdot K$），算法利用滑动窗口 $W=1000$ 内的配对均方误差差值，应用非独立同分布适用的 Freedman 鞅不等式进行显著性检验。在经 Bonferroni 校正控制全时间界内错误提升概率至至多 $\alpha=0.05$ 的严格保护下，影子模型一旦通过检验便立即升格为激活层，并衍生出更深一层的全新影子模型。

一个完整示例¶

以单轮交互过程为例，设定参数为 $b=16$ 质心、初始激活深度 $\ell_{\text{act}}=2$、阻尼因子 $\eta=0.5$： 1. 编码：环境输入 28 维特征 $x_t \in \mathbb{R}^{28}$。第 1 层最近质心为 $k_1=3$，残差向量 $x^{(1)} = x_t - c_3^{(1)}$；第 2 层匹配质心 $k_2=11$，残差向量 $x^{(2)} = x^{(1)} - c_{11}^{(2)}$；影子层匹配质心 $k_3=7$。 2. 打分与动作选择：对各个臂 $a$，抽取第 1 层质心 $(1, 3, a)$ 的采样值 $\tilde{\theta}_1^\top [x_t; 1]$ 与第 2 层质心 $(2, 11, a)$ 的采样值 $\tilde{\theta}_2^\top [x^{(1)}; 1]$。综合得分 $s_a = \tilde{\theta}_1^\top [x_t; 1] + 0.5 \cdot \tilde{\theta}_2^\top [x^{(1)}; 1]$。选取使得 $s_a$ 最大的臂 $a_t = 2$ 执行，环境反馈真实奖励 $r_t = 1$。 3. 级联计算伪目标：第 1 层后验均值预测 $\hat{\mu}_1 = 0.6$，初始预测 $\hat{y}_0 = 0$，第 1 层伪目标 $\tilde{r}_1 = 1 - \sigma(0) = 1 - 0.5 = 0.5$；累加预测 $\hat{y}_1 = 0 + 0.6 = 0.6$；第 2 层后验均值预测 $\hat{\mu}_2 = 0.4$，第 2 层伪目标 $\tilde{r}_2 = 1 - \sigma(0.6) = 1 - 1.0 = 0.0$；累加预测 $\hat{y}_2 = 0.6 + 0.5 \times 0.4 = 0.8$；第 3 层影子目标 $\tilde{r}_3 = 1 - \sigma(0.8) = 0.0$。 4. 增量更新：以 $([x_t; 1], \tilde{r}_1)$ 更新质心 $(1, 3, 2)$，以 $([x^{(1)}; 1], \tilde{r}_2)$ 更新质心 $(2, 11, 2)$，同时以 $([x^{(2)}; 1], \tilde{r}_3)$ 被动更新影子质心 $(3, 7, 2)$。当步数达到检验时间点且 Freedman 统计量显著胜出时，深度 $\ell_{\text{act}}$ 自增为 3。

损失函数 / 训练策略¶

离线阶段通过 MiniBatchKMeans（$k=16$，k-means++ 初始化，批大小 1024，最大迭代 100 轮）在 50K 无标签样本上对各层残差执行无监督重构误差最小化训练。在线阶段采用岭回归（Ridge Regression）均方误差作为闭式目标，通过 Sherman-Morrison 秩一更新精确维护后验逆协方差 $B^{-1} \leftarrow B^{-1} - \frac{v v^\top}{1 + {x'}^\top v}$，其中 $v = B^{-1} x'$。超参数保持全局统一（$b=16, \ell_0=2, \ell_{\max}=8, \nu=0.1, \eta=0.5, \lambda=1.0, \alpha=0.05, W=1000$），各数据集完全免调参。

实验关键数据¶

主实验¶

在 13 个涵盖物理学、生物医学、森林分类及点击预测的 OpenML 与 UCI 真实表格数据集上（样本量 $N$ 从 130K 至 11M，特征维数 $d \in [3, 90]$，候选动作数 $K \in [2, 104]$），通过有监督转老虎机评估协议，以 30 个随机种子测定终局累积遗憾率（$R(T)/T$）及相对基线的减少比例（胜负判定基于 95% 置信区间）。

数据集	维度 $d$ / 动作 $K$ / 样本 $T$	LinTS (基线)	LinTS-RQ (本文)	相对降幅 (Gap)	胜负判定 (95% CI)
skin_segmentation	$d=3, K=2, T=195\text{K}$	8.3%	0.3%	−96.1%	显著胜 (Win)
kddcup99	$d=41, K=17, T=440\text{K}$	0.2%	0.2%	−16.0%	平局 (Tie)
covertype	$d=54, K=7, T=530\text{K}$	28.1%	23.9%	−15.0%	显著胜 (Win)
bng_letter	$d=16, K=26, T=950\text{K}$	52.4%	46.6%	−11.0%	显著胜 (Win)
miniboone	$d=50, K=2, T=80\text{K}$	11.0%	9.9%	−10.1%	显著胜 (Win)
higgs	$d=28, K=2, T=6.7\text{M}$	35.5%	32.6%	−8.0%	显著胜 (Win)
susy	$d=18, K=2, T=3.5\text{M}$	21.6%	20.3%	−6.1%	显著胜 (Win)
poker	$d=10, K=9, T=445\text{K}$	49.4%	46.9%	−5.0%	显著胜 (Win)
airlines	$d=7, K=2, T=450\text{K}$	41.3%	39.8%	−3.6%	显著胜 (Win)
beer_reviews	$d=12, K=104, T=450\text{K}$	85.6%	83.0%	−2.9%	显著胜 (Win)
hepmass	$d=27, K=2, T=830\text{K}$	18.6%	18.4%	−1.1%	显著胜 (Win)
bng_elevators	$d=18, K=10, T=950\text{K}$	75.1%	75.0%	−0.2%	平局 (Tie)
year_prediction	$d=90, K=84, T=445\text{K}$	93.6%	97.8%	+4.5%	败 (Loss)

在同类对比汇总中：LinTS-RQ 对比原始 LinTS 取得 10 胜 1 负 2 平；SGD-LinTS-RQ 对比 SGD-LinTS 取得 12 胜 1 负 0 平；纯计数的 TS-RQ 对比无上下文 TS 取得 11 胜 2 负 0 平（kddcup99 降幅达 −97.4%）。与重放集成基线相比，LinTS-RQ 对比 Doubling-XGB 达到 7 胜 4 负 2 平，对比自监督神经表征 TabNet-LinTS 取得 11 胜 2 负 0 平。

消融实验¶

消融实验对比了内存资源开销、自适应深度选择相较于固定深度的收益，以及非线性拟合收敛性：

表 1：内存消耗对比（固定 $\mathcal{O}(1)$ 内存 vs 无界重放缓冲）

数据集与交互规模	TS-RQ 内存	LinTS-RQ 内存	Doubling-XGB 重放内存	内存压缩倍率
higgs ($T=5\text{M}$)	12 KB	620 KB	1.1 GB	> 1700×
susy ($T=5\text{M}$)	22 KB	176 KB	800 MB	> 4500×
covertype ($T=530\text{K}$)	60 KB	10 MB	51 MB	5.1×

表 2：TS-RQ 固定深度 vs 影子自适应深度遗憾率（%）

数据集	固定深度 $\ell=1$	固定深度 $\ell=2$	影子自适应深度 (Adaptive)	自适应最终选定深度
covertype	48.3%	42.2%	38.8%	自动提升至深度 4
higgs	45.4%	43.6%	43.7%	稳定停留在深度 3

关键发现¶

数据充分性准则与参数瓶颈：LinTS-RQ 每个臂维护全协方差，总参数量达 $b K d^2$。论文发现无量纲比值 $N / (b K d^2)$ 是判定算法能否获胜的核心指标。在 12 个比值 $>1.1$ 的数据集上，LinTS-RQ 全部取得优势；唯独在 year_prediction 上（$d=90, K=84$，比值仅为 0.04），数据极端饥饿导致 LinTS-RQ 随深度加深性能恶化（$\ell=1$ 为 96.3%，$\ell=4$ 恶化至 97.4%）。而纯计数的 TS-RQ 每个单元仅需 $\mathcal{O}(1)$ 参数，在该数据集上展现出完全鲁棒的平稳表现（93.0%）。
有效秩崩溃下的鲁棒性：当特征协方差矩阵的有效秩 $\text{tr}(\Sigma)/\lambda_{\max}(\Sigma)$ 低于 1.5 时（如 skin_segmentation 和 miniboone），对角假设的 SGD-LinTS 会在大量噪声维度上平分方差，导致性能甚至劣于无上下文 TS。而 TS-RQ 的聚类质心能够自然捕捉沿主轴分布的非线性流形几何，将遗憾率骤降至 2.6% 与 14.7%。
几何收缩率经验验证：在 39 组（数据集 × 变体）拟合中，对多层遗憾率拟合指数衰减函数 $a + b \rho^\ell$ 获得了高达 0.99 的中位数 $R^2$ 拟合优度，单元内真实奖励方差在各层之间以中位数比率 $\rho=0.83$ 保持几何递减。

亮点与洞察¶

跨领域表征迁移的降维打击：将检索场景成熟的残差量化技术跨界重塑为老虎机的非线性表征层。巧妙利用 RQ 的残差级联结构，将指数级划分的 $b^\ell$ 网格单元压缩在 $\ell b$ 个离散质心参数中，破解了在线学习中长期存在的“空间精细切分必导致样本饥饿”的矛盾。
无遗憾损耗的影子自适应机制：区别于传统多臂/多策略元学习算法（如 CORRAL）需要对候选模型分配勘探权重而不可避免地承担 $\tilde{\mathcal{O}}(\sqrt{M})$ 遗憾惩罚，该算法将影子模型作为完全隔离的离线测试分支，通过 Freedman 鞅差边界严格把关升格门槛，实现了零在线开销的自适应深度递进。
超轻量工业落地的工程极致：最简形态的 TS-RQ 仅维护标量计数器，单步推断与更新延迟低至 50–750 $\mu$s，显存/内存常驻仅十几 KB，却能在非线性数据集上逼平或击败复杂的双重重训神经网络与梯度提升树。

局限与展望¶

高维大动作空间下的协方差爆炸：数据充分性比值 $N / (b K d^2) \gg 1$ 成为 LinTS-RQ 的硬性约束。未来可引入随机投影或 PCA 预降维至 $p \ll d$ 维，将判定条件放宽至 $N / (b K p^2)$。
离线无监督划分与奖励相关性的脱节：当前的码本仅依据未标注特征空间几何重构误差进行 $k$-means 划分，并未感知真实的奖励梯度。在具有高变异奖励而输入几何较平缓的区域可能存在划分浪费，结合有监督树分裂（如 CART 划分）构建奖励感知码本是值得探索的方向。
二值奖励与平方损失的代数不匹配：当前线性学习器直接在二值奖励上采用最小二乘法更新，在严重偏态的数据集上容易因平方损失置信度溢出产生过度自信的错误预测，后续可通过引入 Pólya-Gamma 数据扩增以严格适配贝叶斯逻辑回归。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将残差量化机制与梯度提升级联思想引入上下文老虎机，架构构思巧妙且高度自洽。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 13 个基准数据集、3 种不同层级学习器变体、30 个随机种子，论据详实且包含深入的失效模式诊断（数据充分性比值）。
写作质量: ⭐⭐⭐⭐⭐ 结构紧凑，理论展开严谨，理论上下界与实验现象（如几何衰减规律）高度呼应。
价值: ⭐⭐⭐⭐⭐ 为计算和内存资源受限的高并发工业级在线推荐系统与流式决策提供了极具吸引力的实用范式。

数据集	维度 \(d\) / 动作 \(K\) / 样本 \(T\)	LinTS (基线)	LinTS-RQ (本文)	相对降幅 (Gap)	胜负判定 (95% CI)
skin_segmentation	\(d=3, K=2, T=195\text{K}\)	8.3%	0.3%	−96.1%	显著胜 (Win)
kddcup99	\(d=41, K=17, T=440\text{K}\)	0.2%	0.2%	−16.0%	平局 (Tie)
covertype	\(d=54, K=7, T=530\text{K}\)	28.1%	23.9%	−15.0%	显著胜 (Win)
bng_letter	\(d=16, K=26, T=950\text{K}\)	52.4%	46.6%	−11.0%	显著胜 (Win)
miniboone	\(d=50, K=2, T=80\text{K}\)	11.0%	9.9%	−10.1%	显著胜 (Win)
higgs	\(d=28, K=2, T=6.7\text{M}\)	35.5%	32.6%	−8.0%	显著胜 (Win)
susy	\(d=18, K=2, T=3.5\text{M}\)	21.6%	20.3%	−6.1%	显著胜 (Win)
poker	\(d=10, K=9, T=445\text{K}\)	49.4%	46.9%	−5.0%	显著胜 (Win)
airlines	\(d=7, K=2, T=450\text{K}\)	41.3%	39.8%	−3.6%	显著胜 (Win)
beer_reviews	\(d=12, K=104, T=450\text{K}\)	85.6%	83.0%	−2.9%	显著胜 (Win)
hepmass	\(d=27, K=2, T=830\text{K}\)	18.6%	18.4%	−1.1%	显著胜 (Win)
bng_elevators	\(d=18, K=10, T=950\text{K}\)	75.1%	75.0%	−0.2%	平局 (Tie)
year_prediction	\(d=90, K=84, T=445\text{K}\)	93.6%	97.8%	+4.5%	败 (Loss)

数据集与交互规模	TS-RQ 内存	LinTS-RQ 内存	Doubling-XGB 重放内存	内存压缩倍率
higgs (\(T=5\text{M}\))	12 KB	620 KB	1.1 GB	> 1700×
susy (\(T=5\text{M}\))	22 KB	176 KB	800 MB	> 4500×
covertype (\(T=530\text{K}\))	60 KB	10 MB	51 MB	5.1×