🤖 machine learning

Breaking the Grid: Distance-Guided Reinforcement Learning in Large Discrete Action Spaces

本文介绍了距离引导强化学习（DGRL），这是一种新颖的算法，它通过结合采样的动态邻域和基于距离的更新，将策略优化转化为稳定的回归任务，从而克服了大规模离散动作空间（高达 $10^{20}$ 个动作）中的维度灾难，并实现了相较于最先进方法的显著性能与收敛性提升。

原作者： Heiko Hoppe, Fabian Akkerman, Wouter van Heeswijk, Maximilian Schiffer

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Heiko Hoppe, Fabian Akkerman, Wouter van Heeswijk, Maximilian Schiffer

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

想象一下，你是一艘巨大宇宙飞船的船长，正试图在拥有数十亿个可能目的地的银河系中航行。在人工智能领域，这就是“强化学习”（RL）试图完成的任务：教导计算机智能体在复杂环境中做出最佳决策，例如管理仓库、调度工厂作业或推荐电影。

问题出在哪里？当可能的目的地（即动作）数量变得极其庞大——例如达到 $10^{20}$ ，这个数字超过了地球上的沙粒总数——传统的人工智能方法就会彻底迷失。它们会遭受“维度灾难”的困扰，这是一种委婉的说法，意指搜索空间太大，无法逐一检查。

本文介绍了一种名为**距离引导强化学习（DGRL）**的新方法。这就好比给这位人工智能船长配备了一枚智能指南针和一张可靠的地图，而不是让它去逐一检查天空中的每一颗星星。

以下是 DGRL 的工作原理，分解为简单的概念：

1. 问题：“网格”陷阱

旧的方法试图通过将动作空间视为刚性网格（就像国际象棋棋盘）来解决这个问题。

缺陷： 如果你的目的地分布不规则（就像真实银河系中的星星，而非完美的网格），或者网格过于巨大，这些方法就会失效。它们要么陷入局部循环，要么计算耗时无穷无尽。这就像试图只沿着城市的主干道行走，而忽略所有小巷和捷径，以此来寻找特定的房屋。

2. 解决方案：DGRL 的两步舞

DGRL 通过将问题拆分为两个聪明的步骤来解决：即寻找邻域和学习路径。

步骤 A：采样动态邻域（SDN）——“智能探照灯”

AI 不再检查每一个可能的动作，而是首先对优质目的地可能所在的位置做出“最佳猜测”（即一个连续的原动作）。

类比： 想象你在一个巨大的图书馆里寻找一本特定的书。与其走过每一条过道，不如先猜测大致所在的区域。
神奇之处： DGRL 使用一种特殊的“探照灯”（称为切比雪夫度量）来扫描该猜测周围的三维空间。关键在于，随着图书馆变得更大，这束探照灯并不会变弱。它会在该空间内采样几本随机书籍，以查看哪一本最好。
为何酷： 它忽略了刚性网格。它能够处理混乱、不规则的空间，在这些空间中，“优质”动作并非整齐排列。这就像通过撒网来搜索房间，而不是沿着直线行走。

步骤 B：基于距离的更新（DBU）——“温和的导师”

一旦 AI 找到了一个良好的候选动作，它就需要从中学习。当选项列表极其庞大时，传统方法往往会变得“嘈杂”或困惑。

类比： 想象一位老师试图指导学生。与其说“你错了，再试一次”（这既模糊又令人沮丧），不如说：“你瞄准的是 A 点，但最佳位置是 B 点。让我们只需将你的瞄准点稍微向 B 点移动一点。”
神奇之处： DGRL 将学习过程转化为一个简单的“距离游戏”。它计算 AI 的猜测与其找到的“最佳”目标之间的距离，然后微调 AI 使其更接近。这使得学习过程既稳定又快速，即使面对万亿种选项也是如此。它消除了通常导致 AI 在选项过多时崩溃的“噪声”。

3. 应对“混合”挑战

现实世界的问题往往混合了不同类型的决策。例如，机器人可能需要选择使用哪种工具（离散选择：锤子、螺丝刀或扳手），以及用多大力去敲击（连续选择：10% 的力、50% 的力等）。

旧方法： 大多数 AI 将这些视为两个独立的问题，先解决一个，再解决另一个。这就像试图通过先决定方向盘的角度，再决定油门踏板，且两者互不沟通来驾驶汽车。这会导致错误。
DGRL 方法： 它将整个决策视为一个单一、统一的动作。它学会同时控制转向和踩油门，理解它们是协同工作的。这防止了 AI 陷入“承诺陷阱”，即过早做出糟糕的选择，从而毁掉整个计划。

4. 结果：更快、更智能

作者在各种“银河系”（环境）中测试了该方法：

迷宫： 导航复杂的迷宫。
车间调度： 调度工厂机器。
推荐系统： 向用户推荐电影。

在这些测试中，DGRL 不仅奏效，而且表现卓越。

性能： 在某些情况下，它比当前最佳方法高出多达 66%。
速度： 它学习速度快得多，并且当选项数量爆炸式增长至 $10^{20}$ 时不会崩溃。
稳定性： 它能够处理其他方法完全失效的混乱、不规则环境。

总结

可以将 DGRL 视为将人工智能从一个蒙着眼睛的人，试图通过检查每一根稻草来在干草堆里找针，升级为一位聪明的侦探，他：

对针可能所在的位置做出明智的猜测。
使用磁性网快速扫描该区域，寻找最佳候选者。
通过测量与目标的距离并调整瞄准点来学习，忽略干草堆其余部分的混乱。

这使得人工智能能够解决以前因规模过大或过于混乱而无法解决的大规模现实世界问题。

技术摘要：大规模离散动作空间中的距离引导强化学习

问题陈述

强化学习（RL）在连续域和小规模离散域中已取得显著成功，但在物流、调度和推荐系统等大规模决策问题中，却难以克服“基数诅咒”。这些应用通常涉及基数高达 $10^{20}$ 的动作空间，包含高维离散分量、分类变量或混合离散 - 连续参数。

现有方法面临三个主要瓶颈：

梯度方差：随着动作空间增大，概率质量 $\pi(a|s)$ 趋于消失，导致标准策略梯度出现方差爆炸。
计算可行性：依赖穷举枚举或预计算查找表的方法（如 Wolpertinger），随着维度增加而变得不可行。
结构僵化：动态邻域构建（DNC）等方法依赖规则网格结构（如数值邻接性），在间距不规则或稀疏的可行区域中失效。此外，混合动作空间通常需要分层序列处理，这会引入承诺瓶颈并破坏训练稳定性。

方法论：距离引导强化学习（DGRL）

作者提出了距离引导强化学习（DGRL），这是一种离线策略的演员 - 评论家算法，旨在扩展至包含多达 $10^{20}$ 个候选项的动作空间。DGRL 在离散动作空间的连续松弛空间中运行，并利用由两个协同组件组成的体积投影循环：

1. 采样动态邻域（SDN）

SDN 通过在演员生成的连续“原型动作” $\hat{a}$ 周围执行随机体积探索，解决了高维离散空间中的探索挑战。

机制：SDN 不依赖刚性网格线或预计算的最近邻表，而是构建一个由切比雪夫（ $L_\infty$ ）半径 $L$ 界定的动态邻域 $B(\hat{a})$ 。
独立坐标采样：为了避免枚举超立方体中所有整数点带来的组合爆炸，SDN 独立地对每个维度进行采样。它将 $\hat{a}$ 解释为采样分布的众数，并抽取 $K$ 个候选动作。采样候选项的概率随其与 $\hat{a}$ 的距离增加而降低。
维度不变性：通过使用 $L_\infty$ 度量，搜索体积在维度 $N \to \infty$ 时保持稳定。这确保了采样概率不会消失，而欧几里得（ $L_2$ ）度量所需的半径则随 $\sqrt{N}$ 增长。
复杂度：该方法将搜索复杂度从指数级 $O((2L)^N)$ 降低到线性级 $O(N \cdot K)$ ，使其能够扩展到 $N > 100$ 的维度。

2. 基于距离的更新（DBU）

DBU 通过将策略优化转化为稳定的回归任务，解决了梯度方差和不稳定性问题。

目标构建：算法扰动原型动作 $\hat{a}$ 以生成 $M$ 个辅助候选项。它利用评论家评估这些候选项以获得 Q 值，并将这些候选项的softmax 加权平均构建为目标动作 $\bar{a}$ 。这充当了去噪滤波器，减轻了评论家的过估计并平滑了损失景观。
回归损失：演员通过最小化原型动作 $\hat{a}$ 与目标 $\bar{a}$ 之间的距离（例如使用 Huber 损失）进行更新。
方差独立性：理论上，DBU 的梯度方差与动作空间基数 $|A|$ 无关。更新仅取决于松弛动作空间的几何形状和固定数量的采样候选项 $M$ ，从而将梯度噪声与动作空间的大小解耦。

混合空间的统一处理

DGRL 通过输出联合原型动作 $(\hat{a}_d, \hat{a}_c)$ 来处理混合动作空间 $A \subset \mathbb{Z}^N \times \mathbb{R}^M$ 。SDN 和 DBU 均同时对完整向量进行操作。这允许联合优化，其中离散和连续分量通过共享表示层相互提供信息，避免了分层方法中高层选择限制底层优化所导致的典型“遗憾下限”。

主要贡献

算法框架：提出了 DGRL，结合 SDN 和 DBU，实现在多达 $10^{20}$ 个动作的空间中进行高效强化学习。
理论保证：
- 证明了基于切比雪夫的采样在维度增加时能保持稳定的搜索体积（命题 4.1）。
- 证明了 DBU 的梯度方差与动作基数 $|A|$ 无关（定理 4.2）。
- 在 Lipschitz 连续性假设下，建立了结构化任务中的局部价值改进保证（命题 4.5）。
可扩展性：证明了 DGRL 随维度 $N$ 线性扩展，而非随基数 $|A|$ 指数扩展，并能自然地泛化到结构不规则和混合动作空间。

实验结果

作者在四个环境的十二种变体上评估了 DGRL：二维迷宫、作业车间调度、联合库存补货和推荐系统。这些环境包括结构化（规则）和不规则结构拓扑，动作空间范围从 $5^4$ 到 $343^{10}$ 。

性能：DGRL 在离散环境中比最先进基准（包括 Wolpertinger、DNC、Cacla 和 LAR）高出66%，在混合环境中高出129%。
鲁棒性：与在高度不规则空间中崩溃的 DNC 不同，DGRL 保持了稳定性和性能。与基于 DDPG 的基线相比，它还表现出显著更低的方差和更快的收敛速度。
计算效率：DGRL 表现出相对于动作空间大小近乎恒定的步长时间，而依赖查找表的方法（Wolpertinger、LAR）变得计算上不可行，DNC 的步长时间则随维度退化。
消融研究：结果证实，SDN（用于体积探索）和 DBU（用于稳定回归更新）都是必不可少的；移除任一组件都会导致性能下降或不稳定。

意义与主张

该论文声称，DGRL 为感知度量的强化学习提供了一种基础方法，表明利用问题结构和距离引导采样可以替代大规模决策中的分类表示。

作者断言，DGRL 通过以下方式成功弥合了强化学习中的可扩展性差距：

将梯度方差与动作空间基数解耦。
实现了对不规则动作空间结构具有鲁棒性的体积探索。
促进混合空间中的联合优化，同时避免了分层分解的不稳定性。

该工作被呈现为解决“基数诅咒”的方案，为大规模离散和混合动作空间中的穷举搜索提供了计算上可行的替代方案，并为策略梯度方法提供了更稳定的替代方案。