🤖 machine learning

Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

本文介绍了概率性超维上下文多臂老虎机（HD-CB），这是一种低精度变体，它用随时间衰减的概率更新规则取代确定性累积，以防止溢出并降低计算成本，同时在资源受限设备上优于二值化替代方案。

原作者： Marco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Marco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名小型电池供电机器人的管理者，它需要每天快速做出决策。例如，它需要选择最佳路线来递送包裹，或者选择最佳时间开启灯光以节省能源。这是一个经典的“上下文多臂老虎机”（Contextual Bandit）问题：机器人观察到一个情境（上下文），选择一个动作，获得奖励（或惩罚），并从中学习以便下次做得更好。

本文解决了一个具体的难题：如何教导这台机器人在不耗尽电池或填满其微小内存的情况下进行学习？

以下是该问题及其解决方案的故事，拆解为简单的概念。

问题：“巨型笔记本”与“微型记事本”

标准学习算法就像拥有巨型笔记本的学生。每学到新东西，他们就会在一张巨大的数字表中记录下来。

问题所在： 随着世界变得更加复杂（需要跟踪的变量增多），那本笔记本会变得巨大无比。对于小型设备（如可穿戴设备或传感器）而言，这是不可能的。在那本巨型笔记本上记录需要占用太多内存和电池电量。

为了解决这个问题，研究人员此前尝试了一种称为**超维计算（Hyperdimensional Computing, HD-CB）**的方法。他们不使用巨型表格，而是使用“超向量”——你可以将其想象成一串长长的珠子，每颗珠子都是一个数字。

旧的 HD-CB： 每次机器人学习时，都会在串上添加一颗珠子。问题在于？珠子上的数字会像滚下山坡的雪球一样变得越来越大。最终，数字会变得如此巨大，以至于撑爆机器人的微小内存。
之前的修复方案（二值化 HD-CB）： 为了防止数字变得过大，旧方法采用了“硬重置”。每隔几步，它会查看所有珠子，并强制将它们设为"0"或"1"，丢弃中间所有的细微差别。
- 缺陷： 这就像每周擦除你的整个日记，只保留标题。你失去了关于你有多喜欢某事的细节，而不仅仅是是否喜欢它。这导致机器人做出了更差的决策。

解决方案：“概率”方法

本文作者引入了一种名为**概率 HD-CB（Probabilistic HD-CB）*的新方法。他们不仅仅是强制进行硬重置，而是改变了机器人学习的方式*。

想象机器人拥有一组饱和计数器（就像一个机械里程表，停在某个数字，比如 7，而不会变成 8）。

不再有巨大的雪球： 机器人被设计为数字永远不能超过一个小限制（例如 -7 到 +7），而不是让数字无限增长。这完美地适配于微小的芯片。
“抛硬币”更新： 这里是巧妙之处。在旧方法中，机器人每次学习时都会更新串上的每一颗珠子。这非常昂贵。
- 在新方法中，机器人对每颗珠子抛一次硬币。
- 早期： 硬币被加权，使其经常落在“正面”，因此会更新许多珠子。
- 后期： 随着机器人变得更聪明，硬币被加权，使其倾向于落在“反面”。它只更新随机少数几颗珠子。
为何有效： 通过随时间更新更少的珠子，机器人节省了电池和内存。但由于它是随机更新而不是强制硬重置，它保留了所学内容的“故事”。它没有丢弃信息的量级，只是将其随时间分散开来。

结果：小即是美

研究人员使用标准模拟（测试这些算法的“游乐场”）将这种新方法与旧方法进行了对比测试。

优于“硬重置”： 新方法（概率法）始终比旧的“二值化”方法做出更好的决策。它没有丢失那么多信息。
微小却强大： 最令人惊讶的结果是，新方法在使用每颗珠子仅 3 位内存的情况下，表现几乎与“巨型笔记本”（高精度版本）一样好。
- 类比： 这就像说，“只要我在正确的时间选择正确的字母，我就能用仅由 3 个字母组成的字母表写出一部伟大的小说。”
内存节省： 由于新方法不需要保留额外的“备份副本”或“计数器”来管理硬重置，其内存占用量低于之前的低精度方法。

核心结论

本文提出了一种将智能、自适应的决策直接部署到小型低功耗设备（如边缘设备）上的方法，而无需依赖云端计算机。

通过从“不断累加数字直到崩溃”转变为“抛硬币来更新小的、有界的计数器”，研究人员创造了一个学习系统，它：

更轻量： 占用更少内存。
更智能： 比之前的低功耗方法做出更好的决策。
更高效： 随着学习的深入，通过减少更新频率来节省能源。

简而言之，他们找到了一种方法，让微型机器人在不需要“大脑”或“满箱燃料”的情况下有效学习。

技术摘要：基于概率学习的资源受限设备上下文多臂老虎机

问题陈述
上下文多臂老虎机（Contextual Bandits, CB）是个性化推荐和边缘计算等自适应服务中在线序列决策的基础。然而，将 CB 代理直接部署到资源受限的设备（如移动设备、可穿戴设备、空中设备）上面临着重大挑战。标准的线性 CB 算法虽然有效，但需要维护随上下文维度呈二次方增长的协方差矩阵（ $O(Nd^2)$ 内存），并涉及计算昂贵的线性代数运算（ $O(d^3)$ 复杂度），这使得它们不适合内存、计算和能量约束严格的设备。

最近的研究引入了超维上下文多臂老虎机（Hyperdimensional Contextual Bandits, HD-CB），利用超维计算（Hyperdimensional Computing, HDC）在超维空间中通过轻量级向量运算解决 CB 问题。虽然 HD-CB 提供了线性时间复杂度和更好的可扩展性，但其标准实现依赖于基于累加的更新机制，导致动作向量分量无限增长。这需要高精度数值类型（例如 32 位浮点数）以防止溢出，从而抵消了内存效率的提升。此前的一种低精度变体 HD-CBBIN 通过定期将向量二值化并重置计数器来解决溢出问题。然而，这种确定性二值化丢弃了累积的幅度信息，导致性能下降，特别是在噪声较大或数据稀缺的情况下。

方法论：概率 HD-CB（HD-CBPROB）
本文提出了HD-CBPROB，这是一种 HD-CB 的低精度变体，用概率更新规则取代了确定性累加。其核心创新在于通过设计来限制学习过程，而非通过周期性重置。

有界整数分量：HD-CBPROB 不允许多向量分量无限增长，而是将每个分量限制在预定义的整数范围 $[-\kappa, +\kappa]$ 内。这使得可以使用低精度饱和整数计数器（例如 2、3 或 4 位）。
概率更新规则：为了在这些严格界限内实现学习而不丢失信息，该算法用基于频率的更新取代了基于幅度的更新。在每个时间步 $t$ $t$ ，仅根据随时间衰减的概率 $\alpha_t$ $α_{t}$ 更新向量的随机子集。
- 更新概率定义为 $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$ 。
- 对于每个分量 $i$ ，采样一个随机值 $m_{t,i} \sim U(0, 1)$ 。仅当 $m_{t,i} \leq \alpha_t$ 时，才执行更新。
- 当发生更新时，分量根据上下文和奖励超向量的绑定关系递增或递减 $\pm 1$ ，然后截断至范围 $[-\kappa, +\kappa]$ 。
机制：这种方法有效地实现了一种“饱和随机游走”。通过控制更新的频率而非存储值的幅度，代理即使在低精度分量中也能高保真地保留历史信息。这消除了 HD-CBBIN 所需的辅助计数器和周期性二值化步骤。

主要贡献

算法创新：引入了一种用于 HD-CB 的概率更新规则，使得无需周期性信息丢失即可使用低精度饱和整数分量。
资源效率：该方法通过消除先前低精度变体所需的辅助计数器和独立的二值化向量副本，减少了内存占用。同时，由于概率 $\alpha_t$ 随时间衰减，预期更新次数减少，从而降低了计算成本。
性能保持：该方法通过更新频率保留幅度信息，避免了硬二值化带来的性能下降，从而保持了动作的排序质量。

实验结果
作者利用 Open Bandit Pipeline (OBP) 在标准化的合成 CB 基准上通过离线策略评估对 HD-CBPROB 进行了评估，并将其与以下方法进行了比较：

LinEPS：标准线性 CB（基线）。
HD-CBREAL：实值 HD-CB。
HD-CBBIN：带有周期性重置的二值化 HD-CB。
HD-CBPROB：提出的概率变体。

主要发现包括：

优于二值化变体：在所有测试配置（变化的上下文维度 $d$ 和动作数量 $N$ ）下，HD-CBPROB 在同等精度水平上始终优于 HD-CBBIN。具体而言，3 位 HD-CBPROB 实现比 3 位 HD-CBBIN 实现的累积奖励提高了约 5.8%。
接近实值性能：3 位 HD-CBPROB 配置（饱和阈值 $\kappa=3$ ）实现了接近实值 HD-CBREAL 基线的性能，平均差距仅为 2.5%。
精度的边际收益递减：对于 HD-CBPROB，将精度从 3 位增加到 4 位带来的收益递减或略有负面，表明在这些合成设置中，3 位足以捕捉动作质量。
内存效率：HD-CBPROB 在相同位宽下所需的内存严格少于 HD-CBBIN，因为它不需要辅助机制（计数器和临时二值化副本）。与线性 CB 不同，其内存占用相对于上下文维度保持恒定。

意义与主张
本文声称，概率 HD-CB 解决了先前超维方法中固有的内存占用与信息丢失之间的权衡。通过将基于幅度的累加转变为基于频率的概率更新，该方法使得在电源、内存和计算预算紧张的设备上部署自适应、自主代理成为可能。作者将 HD-CBPROB 定位为边缘智能的有力替代方案，提供了一种实现近最优决策性能的方法，与标准线性算法及现有的低精度超维变体相比，其资源需求显著降低。

作者指出的未来工作包括在真实世界的日志化老虎机数据集上评估该方法，在更复杂的奖励分布下进行测试，以及在嵌入式硬件上获取直接的延迟和能量测量数据，以证实边缘部署的主张。

问题：“巨型笔记本”与“微型记事本”

解决方案：“概率”方法

结果：小即是美

核心结论

技术摘要：基于概率学习的资源受限设备上下文多臂老虎机

类似论文