强化学习基础及其在计算机系统中的应用

强化学习在AI与系统领域的兴起背景

本次讲座由Meta AI的研究科学家Viendo主讲，旨在压缩讲解强化学习（Reinforcement Learning, RL）的基础知识及其在计算机系统中的应用。鉴于时间限制，演讲者试图在有限篇幅内让听众对强化学习的核心概念及著名应用案例建立粗略但完整的认知框架。强化学习不仅在传统游戏领域取得了巨大成功，如围棋、国际象棋、星际争霸等，近期更在大语言模型（LLM）的优化中展现出复兴态势。例如，在ChatGPT和GPT-4的开发中，研究人员首先利用大量数据对智能体进行监督训练，随后基于对比数据训练奖励模型，最后通过强化学习对语言模型进行微调（RLHF）。这一过程证明了强化学习在构建最先进聊天机器人中的关键作用，尽管本次讲座将重点聚焦于计算机体系结构领域，而非NLP方向。

"what they do is that the first Trend and supervise the agent uh with a lot of data using language models and then you can basically train a reward model on this comparison data and finally you can basically tune the language model with reinforcement learning"

计算机系统为何需要强化学习：优化问题的本质

计算机系统研究者关注强化学习，核心原因在于系统设计中存在大量的多维访问优化问题。系统工程师通常致力于优化内存使用、延迟和效率等指标，这些优化问题往往处于高维空间中。传统的优化方法通常从初始解出发，尝试以顺序方式逐步改进解决方案。如果将这些问题建模为马尔可夫决策过程（Markov Decision Process, MDP），就可以利用强化学习来改进现有方案并寻找更优解。演讲者列举了多个典型应用场景，包括编译器优化、网络规划、计算机体系结构优化以及缓存时序攻击中的攻击者与防御者策略寻找。这些案例共同表明，强化学习是解决复杂系统优化问题的有效工具。

"if you want to think about optimization problem is high dimensional space usually what people will do is that we start with some kind of initial solution and then you find try to find a way to improve that in a in a sequential manner"

强化学习核心机制：智能体、状态与奖励

强化学习的基本范式可以通过一个智能体（Agent）与环境交互的循环来描述。智能体感知世界，将感知信息压缩为状态（State, s），并根据当前状态采取行动（Action）。行动会改变环境状态及智能体行为，同时智能体获得奖励（Reward）。这一过程以迭代方式进行。以迷宫游戏为例，智能体（红点）的位置由二维坐标（X, Y）表示，行动则是坐标的加减操作。智能体从初始状态S1开始，通过执行动作A1到达状态S2，并在此过程中获得奖励。奖励函数的设计至关重要，例如在迷宫中，越接近目标状态（出口），获得的奖励越高，从而引导智能体向目的地移动。强化学习的总体目标是最大化长期累积奖励，即最大化资本R函数。该函数通常是短期奖励的线性组合，其中包含一个折扣因子（Gamma, γ），用于平衡短期奖励与长期奖励的权重。

"the goal of reinforcement overall is to maximize the long-term reward uh by uh maximizing this like a capital R functions and that random reward usually is a linear combination of all the short-term reward a one-step reward and here the gamma is a discount Factor"

讲座内容架构：从值基到策略基方法

本次教程将涵盖强化学习的两大主要分支：基于值的方法（Value-based approaches）和基于策略的方法（Policy-based approaches）。在基于值的方法部分，将重点介绍Q-Learning和AlphaZero算法，并以AlphaTensor作为案例研究，展示如何利用该技术寻找最高效的矩阵乘法算法。在基于策略的方法部分，将讲解策略梯度、Actor-Critic架构以及PPO（Proximal Policy Optimization）算法，并探讨如何利用Actor-Critic解决网络规划问题这一系统级挑战。此外，还将简要介绍AlphaDev，该研究利用类似AlphaZero的技术寻找最短的汇编代码以优化排序算法。通过这些案例，演讲者旨在展示强化学习如何从理论算法转化为解决具体计算机系统问题的强大工具。

"the second and third we're going to talk a little bit about the two different branches of reinforcement learning that's equal to value-based approaches... and finally we're going to talk about the policy based approach this include the policy gradient like the critic PPO and also an application that try to leverage acid critic to network planning problems"

强化学习的核心要素与策略优化路径

强化学习的核心目标在于寻找一种最佳策略，使得智能体在环境中获得的长期奖励最大化。为了实现这一目标，必须理解三个关键量：策略（Policy）、Q函数和V函数。策略定义为在特定状态 $s$ 下采取动作 $a$ 的概率分布；Q函数表示从状态 $s$ 开始并执行动作 $a$ 后的预期奖励；而V函数则仅表示从状态 $s$ 开始（不条件于具体动作）的预期奖励。这三者之间存在紧密的逻辑联系，只要掌握其中任意一个，就足以推导出最优策略。例如，若已知策略，只需查阅策略表即可决定当前动作；若已知Q函数，则通过遍历所有可能动作并选择Q值最大的动作，同样能获得最优策略。

基于优化对象的不同，强化学习方法主要分为两大流派：基于策略的方法（Policy-based）和基于价值的方法（Value-based）。前者直接优化策略函数，后者则通过优化Q函数或V函数来间接获得策略。在深入探讨具体算法之前，理解这种分类对于把握不同算法的设计初衷至关重要。正如演讲者所述："> you basically want to find like what is the best strategy uh to move around in this in this world so that the London world is maximized"。这种从状态到动作的映射关系，构成了所有强化学习算法的基础框架。

Q表优化与深度Q网络（DQN）的引入

在基于价值的方法中，最直观的形式是使用Q表来存储状态-动作对的Q值。假设状态空间大小为 $S$，动作空间大小为 $A$，则Q表的大小为 $S \times A$。优化的目标是通过迭代更新填充满这个表格，使其收敛至最优Q值。更新公式通常涉及当前Q值与目标Q值的差异。然而，现实世界中的状态空间往往是指数级增长的，且动作空间可能是连续值，这使得传统的Q表方法在扩展性上面临巨大挑战。为了解决这一问题，研究者引入了参数化函数，即使用神经网络来近似Q函数，从而形成了深度Q网络（DQN）。

使用神经网络参数化Q函数带来了泛化能力，使得模型能够处理从未见过的状态。然而，直接优化这种端到端的网络会导致训练极不稳定。因为Q函数的目标值本身也是由同一个网络（或另一个网络）预测的，这种"自举"过程会导致目标值随网络参数变化而剧烈波动。为了解决这一稳定性问题，DQN算法引入了两项关键技术：固定目标网络和时序差分误差（TD Error）。固定目标网络意味着在更新当前Q网络时，目标Q值由一个参数固定不变的"目标网络"提供，从而切断了目标值随当前网络参数剧烈变化的反馈回路。同时，TD误差作为修正项，使得更新过程更加平滑。该算法于2015年发表在《Nature》上，标志着深度强化学习的重要突破。

DQN在Breakout游戏中的应用与进阶技术

DQN算法的有效性在经典游戏Breakout（打砖块）中得到了直观展示。在该实验中，智能体的目标是通过移动挡板接住弹球，从而击碎屏幕顶部的所有砖块。训练初期，智能体的表现非常糟糕，几乎无法有效击球，导致游戏失败。但随着Q函数的不断训练和优化，智能体逐渐学会了追踪弹球轨迹，并最终能够清除所有砖块，展现出超越人类水平的游戏能力。这一案例不仅验证了DQN在复杂环境中的学习能力，也展示了从随机行为到最优策略的演化过程。

为了进一步提升Q学习的效果，研究者提出了多种扩展技术。其中，多步学习（Multi-step learning）是一种标准且有效的方法。与单步更新不同，多步学习允许智能体向前看多个步骤，利用更远处的未来Q值来更新当前Q值。这种方法通常能提供更准确的未来价值估计，从而加速收敛并提高策略质量。此外，经验回放缓冲区（Replay Buffer）也是DQN架构中的关键组件，它通过存储和随机采样历史经验，打破了数据之间的时序相关性，进一步提升了训练的稳定性。这些技术的结合，使得基于价值的强化学习算法能够在高维、连续的状态空间中取得显著成果。

回放缓冲区与动态数据集机制

强化学习中的核心机制之一是回放缓冲区（Replay Buffer），它本质上是一个动态数据集。在该机制中，智能体（Agent）通过执行策略生成数据，并将这些经验存储到缓冲区中。随后，算法从缓冲区中采样数据以更新模型。这一过程类似于监督学习，但存在本质区别：数据集包含专家经验，并在训练过程中持续更新。这种动态特性使得数据分布随模型进化而改变，从而支持更复杂的探索策略。

"The replay buffer is actually you can see this as like a dynamic datasets right the dataset has a lot of expert experience and you take the data sets inside and you're updating it at the same time you train these models."

这种机制允许智能体从历史数据中学习，同时通过新产生的数据不断优化自身。与静态数据集不同，回放缓冲区中的每一批数据都反映了当前策略的状态，这使得训练过程更加高效且具备自我进化的能力。通过这种方式，智能体能够逐步积累更丰富的环境交互经验，为后续的策略优化奠定基础。

离线策略与在线策略的根本差异

在强化学习中，策略更新方式主要分为离线策略（Off-policy）和在线策略（On-policy）两类。离线策略类似于监督学习，使用固定的数据集进行训练，这些数据通常来自专家行为或历史记录。相比之下，在线策略的数据由当前模型采样生成，且随着模型更新，数据分布也会随之变化。这种差异导致在线策略中的智能体不仅从数据中学习，还主动选择学习哪些数据，从而形成独特的探索与利用平衡。

"On policy usually the datasets are sampled by the current models and the data will actually be updated again with the model get update as well."

在线策略的关键在于智能体对数据分布的控制能力。通过不断调整探索范围，智能体可以逐步覆盖更大的状态空间，使策略更加稳定。然而，由于状态空间呈指数级增长，无法穷尽所有可能状态，因此需要在探索与效率之间做出权衡。这种权衡机制是强化学习算法设计的核心挑战之一，也是实现高性能策略的关键所在。

蒙特卡洛树搜索与AlphaZero范式

为了解决探索与利用的权衡问题，蒙特卡洛树搜索（MCTS）被广泛应用于强化学习中。MCTS通过动态更新Q值，根据探索结果优化策略，从而在长期运行中覆盖整个搜索空间并找到最优策略。这一方法在DeepMind的AlphaZero系列中得到了成功应用，其核心循环包括：利用MCTS收集数据、通过反向传播更新模型、再用新模型生成更多数据。这一范式最终实现了超越人类水平的表现。

"This Loop is actually quite simple it's exactly like what I just said you start from this medical research and then you collect lots of data and then once you have lots of data you update your current models uh using reverse memory."

该范式不仅应用于游戏领域，还被扩展至其他复杂优化问题。例如，2019年的一项研究利用类似方法在单GPU上创建了能击败职业选手的机器人，展现了其在实时决策任务中的强大潜力。通过迭代式的数据收集与模型更新，AlphaZero范式证明了强化学习在解决高维、非线性问题上的优越性，为后续研究提供了重要参考。

AlphaTensor与矩阵乘法优化

AlphaTensor是AlphaZero范式的又一重要应用，专注于矩阵乘法优化问题。其目标是以最少乘法次数完成两个N×N矩阵的相乘。数学上，这等价于最小化三阶张量的秩。具体而言，给定一个预定义的张量TN（尺寸为N²×N²×N²），代表矩阵乘法的结构，算法需找到最优分解方式，使分解项数（即秩）最小化。该过程被建模为强化学习任务：初始状态为TN，每一步动作选择U、V、W并从TN中减去相应项，直至状态变为零。

"The goal is to search this UV and W so that this constraint satisfied and the I is minimized."

通过AlphaTensor方法，研究者发现了新的矩阵乘法方案，其乘法次数低于此前已知最优解。例如，当N=2时，张量维度为4×4×4（即64维），算法通过迭代搜索找到最优分解路径。这一成果展示了强化学习在解决传统计算机优化问题上的潜力，证明了其能够突破人类数学直觉的限制，发现更高效的算法结构。

基于策略的方法与梯度估计

强化学习不仅限于价值函数方法，还可以采用基于策略（Policy-based）的方法。这类方法的核心在于直接学习一个策略函数，旨在最大化整体奖励。目标函数 $J(\theta)$ 直接由策略函数构成，通过计算轨迹（trajectories）上的累积奖励来优化。经过数学推导，可以得到目标函数的梯度更新公式。该梯度本质上是一个数学期望，由评分函数与奖励的乘积构成。由于直接计算期望较为困难，实践中通常采用蒙特卡洛采样的方法来近似梯度。具体而言，通过从当前策略中采样不同的轨迹，计算这些轨迹的奖励总和，从而得到梯度的近似值，并利用该近似梯度更新参数（如CDAS等）。这种方法允许算法在探索过程中不断调整策略，以寻找更优的动作序列。

离策略数据与重要性采样修正

在强化学习算法中，数据是否来自当前策略（On-policy）至关重要。如果数据是离策略（Off-policy）的，即数据由另一个行为策略（Behavior policy, $\beta$）生成，而当前策略（$\pi$）已经更新，直接使用该数据更新会导致偏差甚至错误。这是因为数据分布与当前策略不再匹配。为解决这一问题，研究者引入了重要性采样（Importance Sampling）技术，即在梯度更新中加入一个修正项 $r_t$。该修正项是当前策略与行为策略概率比值的累积乘积。当当前策略与行为策略一致时，比值为1，公式回归到标准的策略梯度更新。然而，如果行为策略中从未出现过某个动作，而当前策略却选择了它，比值 $r_t$ 可能会趋向无穷大，导致估计不稳定。因此，实践中通常对 $r_t$ 进行截断（Clipping）处理，以限制其范围，确保算法的稳定性，尽管这会引入一定的偏差。

Actor-Critic 架构与 PPO 算法

为了进一步优化策略梯度，Actor-Critic 架构被广泛采用。该架构同时优化两个部分：Actor（策略网络）和 Critic（价值网络）。Critic 负责估计状态价值函数 $V$ 或动作价值函数 $Q$，而 Actor 利用 Critic 提供的信息来计算优势函数（Advantage Function）。优势函数衡量的是某个动作相对于其他动作的相对优劣，即该动作带来的回报与平均回报的差值。通过优势函数，算法可以更准确地评估动作的价值，从而指导策略更新。基于此架构，近端策略优化（PPO, Proximal Policy Optimization） 成为了一种广泛使用的算法。PPO 在策略梯度更新中同样使用优势函数，并对重要性采样比值进行截断，确保策略更新不会过大，从而保持训练的稳定性。PPO 因其高效性和稳定性，被广泛应用于 OpenAI 的 GPT-4 等复杂场景中，以及在网络规划等系统优化问题中。

强化学习在网络规划中的应用

强化学习不仅限于游戏或通用AI，还可应用于具体的网络规划问题。例如，在一个包含 $N$ 个节点的网络中，节点间通过光纤或电缆连接，具有不同的容量。目标是满足数据流的传输需求，同时最小化网络建设成本。这是一个典型的组合优化问题。通过构建强化学习模型，可以将网络状态定义为节点连接和流量需求，动作定义为链路容量的分配或路由选择，奖励函数则结合满足需求的程度和成本开销。利用 PPO 等算法，智能体可以学习如何在复杂的约束条件下，自动规划出成本最低且性能达标的网络拓扑结构。这种方法能够处理传统优化算法难以应对的高维、动态网络环境，展示了强化学习在计算机系统优化中的实际价值。

整数规划在光纤网络中的求解困境

在光纤网络规划场景中，整数规划（Integer Programming, IP） 常被用于优化不同站点间光纤的借用成本，以最小化整体开销。然而，该问题面临极其复杂的约束条件，包括网络流守恒、链路容量限制以及其他多种容量约束，同时还需避免对现有拓扑结构进行过度调整。由于问题规模庞大，若从头开始求解，传统方法可能需要数天甚至数周的时间。面对这种计算复杂度，研究人员通常不得不设计启发式算法，在最优性和可接受性之间进行权衡，例如先解决小规模问题再组合方案。但这种方法的核心痛点在于，很难为这类复杂的 IP 问题找到可行的初始解，导致求解效率低下。

"it's very tricky to use it because the problem itself can be huge right so it may take days or weeks in order to solve this problem uh but from scratch"

基于强化学习的两阶段求解架构

为了解决上述可行性难题，研究提出了一种两阶段强化学习（RL）方法。在第一阶段，系统从给定的拓扑结构出发，初始状态下所有边均无容量。强化学习智能体（Agent）通过策略网络，逐步在特定边上增加容量，直到问题变为可行（Feasible）。这一阶段的设计逻辑在于，检查问题的可行性比直接寻找全局最优解要容易得多，且可以利用图聚合等技巧加速可行性验证。智能体通过图神经网络（GNN）提取拓扑特征，Actor 网络决定在哪些地址增加容量，Critic 网络评估该动作的潜力，从而学习出在何时何地增加容量的最佳策略。

"the reason why we think this is more reasonable than like the solves the entire problem in one sketch is that it's much easier to check the feasibility of problems than to find the optimal solution of the problem in one shot"

第二阶段优化与性能对比实验

一旦强化学习阶段生成了可行的初始解，便进入第二阶段。此时，将 RL 生成的解反馈给 IP 求解器，并限制求解器仅在 RL 解的局部邻域（Local Varsity）内进行搜索。由于 RL 解提供了一个良好的下界（Lower Bound），IP 求解器能更高效地找到更优解。实验对比了五种不同规模的拓扑结构（A 至 E，其中 E 为最大规模）。结果显示，传统 IP 求解器在较大拓扑（D 和 E）上往往无法在短时间内给出可行解，而本方法不仅能快速找到高质量解，还能处理更大规模的网络拓扑，显著优于传统启发式方法。

"we are able to find a good Solutions at the same time and it's quite fast for larger Networks"