机器学习(ML)(二十三) — 强化学习探析

发表于 分类于 阅读次数： 本文字数： 13k 阅读时长 ≈ 43 分钟

递归内省

递归内省(Recursive Introspection)是一种新方法，旨在教授语言模型智能体（如大语言模型，LLMs）如何自我改进。该方法的核心在于使模型能够对自身行为进行内省、推理并纠正错误。其主要特点：自我改进能力，递归内省的目标是使语言模型能够在多轮交互中逐步改善其响应。这种方法强调通过反复的反馈和调整，模型能够识别并纠正先前的错误；RISE方法，该方法被称为RISE(Recursive IntroSpEction)，是一种微调技术，允许模型在面对复杂问题时，通过观察之前的失败尝试和额外的环境反馈来调整其策略；多轮数据收集与训练，RISE借鉴了在线模仿学习和强化学习的原则，提出了多轮数据收集和训练策略，以增强LLM在后续迭代中递归检测和纠正错误的能力。

RISE将单轮提示的微调视为解决多轮马尔可夫决策过程(MDP)，其中初始状态为提示。受在线模仿学习和强化学习的启发，提出了多轮数据收集和训练策略，以使LLM具备在后续迭代中递归检测和纠正其先前错误的能力。实验表明，RISE使Llama2、Llama3和Mistral模型能够通过在更多回合在数学推理任务上自我改进，在相同推理时间计算下超越了几种单轮策略。还发现RISE具有良好的扩展性，通常在更强大的模型上获得更大的收益。RISE对响应做出了改进，使其能够在不干扰单轮能力的情况下找到挑战性提示的正确解决方案。

递归内省(RISE)是一种利用迭代多轮训练的方法，旨在通过策略回放和奖励函数的监督来训练模型，使其能够在多个回合中自我改进。在推理阶段，对来自不同回合的候选输出进行多数投票，以获得最终响应。

可以训练模型使其具备自我改进响应的能力吗？如果做到这一点，并在多样化的问题和场景中进行训练，这可能为大语言模型(LLM)引入一种通用的方法，指导其如何通过自我改进来应对困难提示，而不是仅仅监督其“应该”如何响应，因为这种方法在测试提示超出分布时可能不具备泛化能力。尽管一种直接的方法是生成多个顺序回合改进的数据，但仅仅模仿这些数据并不足以赋予模型这种能力。这主要有两个原因：首先，来自不同模型的多轮数据不会展示学习者所犯错误的改进，因此对学习者而言是无关的。其次，通常从专有模型收集的顺序多轮数据质量也不高，因为这些模型通常不擅长提出对自身错误的有意义改进。因此，需要一种不同的策略来赋予模型自我改进的能力。关键是以迭代方式监督学习者自身响应的改进，借鉴在线模仿学习和强化学习(RL)中的方法。这种监督可以是从更强大模型中独立同分布抽样得到的对提示的oracle（指提供最优策略或环境模型的信息源）响应，或者由学习者自身生成。递归内省(RISE)在给定提示的多个尝试中提高LLM的自我改进能力。在每次迭代中，递归内省(RISE)从学习者的策略回放中引导出更好的下一回合响应，这些响应是通过在多个修订候选中运行最佳（使用任务成功指标）获得的，这些候选可以是从学习者自身抽样得到的，也可以是使用更强大模型的响应。通过这种方式，能够构建回放，使学习者了解如何在自身分布下改善其响应。然后，使用奖励加权回归(RWR)目标对学习者进行微调，该目标能够从这些回放的高质量和低质量部分中学习。通过反复迭代这一过程，能够将自我改进能力灌输到LLM中。结果表明，通过递归内省(RISE)训练的LLM能够在更多提示上产生正确响应，在更具难度的提示上随着回合数增加而改善。尽管强大的基础和指令调优大语言模型(LLMs)在多个顺序尝试中常常未能改善其响应，递归内省(RISE)成功地赋予了类似规模的LLM自我改进能力，使其在每个回合后的任务表现单调增加。

具体而言，给定一个数据集，其中包含问题 和对应的oracle响应，目标是获得一个LLM，该模型在给定问题、之前模型对该问题的尝试，以及辅助指令（例如，查找错误并改进响应的指令；或来自环境的额外编译器反馈）时，尽可能正确地解决给定问题。为此，将这一目标编码为优化的以下学习目标：与标准的监督微调不同，后者训练模型在给定的情况下产生单一响应，训练对其自身先前的响应历史作出反应。通过将单回合问题转换为多回合马尔可夫决策过程(MDP)。需要注意，基于提示的方法(Self-Refine)仍然可以被视为训练优化，但仅在允许调节提示来优化以上公式，由于参数不变，这样做并不能有效地完全优化该目标。

递归内省(RISE)方法，首先将问题转换为多回合马尔可夫决策过程，然后收集数据，最后在这个多回合马尔可夫决策过程中运行离线奖励加权监督学习。

将单回合问题转换为多回合马尔可夫决策过程，状态由提示、先验的历史和来自环境的可选反馈组成。动作是基于迄今为止多轮交互状态生成的LLM响应。数据收集：通过将当前模型展开次，然后生成改进版本的响应来收集数据，该响应可以通过以下方式获得：(1)自我蒸馏：从当前模型中采样多个响应，并使用最佳的响应；(2)蒸馏：通过查询更强大的模型获得oracle响应。

思维链(Chain-of-Thought, CoT)是一种提升大语言模型(LLM)在复杂推理任务上的技术。它的核心理念是模拟人类的推理过程，通过逐步推导出一系列中间步骤或子目标，从而最终得出正确答案。其特点：

  • 逐步推理：CoT技术要求模型在生成最终答案之前，先产生一系列中间推理步骤。这些步骤构成了一个“思维链”，帮助模型更清晰地理解问题并找到解决方案。
  • 可解释性：由于CoT提供了推理过程的可见性，用户可以更容易理解模型的决策过程，从而提高模型的可解释性。
  • 逻辑推理能力：CoT能够帮助模型进行复杂的逻辑推理，特别是在需要综合多个事实或信息片段的问题上。
  • 上下文利用：在CoT中，模型可以利用上下文信息，通过逐步推理来解决问题，而不是仅仅依赖于直接的答案。

构建递归内省(RISE)方法的第一步是将单回合数据集的提示和oracle响应构建为多回合马尔可夫决策过程。给定一个数据集，其中包含提示和相应的oracle响应（例如，数学问题及其自然语言响应），将从构建一个诱导的MDP，然后在这个MDP中学习策略。该MDP中的初始状态是一个提示。将基础模型的输出响应表示为动作。给定状态，下一个状态可以通过将表示状态的标记与模型提出的动作以及一个额外的固定提示连接起来获得。奖励函数是一个稀疏的二元指标，用于指示在给定状态下答案的正确性，定义为：当且仅当，并由答案检查函数获得。这种从数据集到MDP的构造如下所示：

在MDP构建完成后，下一步是训练模型在回放过程中自我改进。可以采用一种离线学习的方法，具体描述如下：

  • 步骤一：自我改进的数据收集，为了确保这个多回合马尔可夫决策过程(MDP)的回放数据对教授模型如何自我改进是有用的，它必须满足几个条件：(1)必须展示学习者可能犯的错误，并展示如何在下一次尝试中改进这些错误；(2)数据必须展示与给定问题和上下文中先前尝试相关的响应；(3)必须不包含在后续回合中退化的回放。在给定回合中，对于给定问题，展开当前模型尝试生成多个顺序，记作。在有外部输入（例如，编译器反馈）的情况下，观察到一个可变长度的自然语言外部输入（例如，在数学问题中，要求模型自我纠正）。还观察到一个标量奖励值，简称为，将这个模型回放的数据集记作。对于每个时间步，构建响应，记作。与这个改进响应相关的奖励分数为，或简称为。为了获得响应的改进版本，可以采用几种策略。最直接的方法是查找一个更强大的模型，根据提示、先前响应和外部反馈（可选）提供正确的响应。将其称为蒸馏变体，因为它使用强大的“教师”模型来指导自我改进（请注意，这与经典的知识蒸馏概念不同）。 第二种变体，旨在减轻对教师模型的依赖，通过从学习者自身多次采样来构建改进响应。将这种方法称为自我蒸馏变体。具体而言，对于数据集中每个状态，从模型中采样个响应，并使用这个候选响应中最好的一个（根据奖励值来衡量）来重新标记改进轨迹中下一步的模型响应。形式上，设，那么在步骤中将数据集中的响应标记为改进响应及其相关的奖励值：
  • 步骤二：策略改进，通过上上面的数据构建方案，现在可以在这些数据集上训练模型。一般来说，可以使用任何离线强化学习(RL)方法在这些数据上进行训练，也可以使用加权监督学习的方法。执行加权监督回归，其中权重由数据集中奖励值的指数变换给出。 温度参数用于进一步扩展或缩小良好和不良动作之间的差异。在初步实验中，发现以上公式会导致偏向于提高高奖励响应的对数似然，优先更新那些奖励已经很高的简单问题。为了解决这个问题，对以上公式进行了轻微修改，使得指数化的奖励围绕在给定提示的所有尝试中平均的均值进行中心化，这类似于优势加权回归(advantage-weighted regression, AWR)。使用优势代替奖励有助于避免在简单问题上出现“富者愈富”的现象。

优势加权回归(Advantage-Weighted Regression, AWR)是一种强化学习中的策略优化方法，旨在通过利用优势函数来改进学习过程。它的核心思想是通过对回报进行加权，从而增强学习信号的质量，并有效利用历史数据，即使在非互动环境中也能发挥作用。

在部署时推理：RISE可以在推理时使用两种模式运行。最直接的方式是通过多回合回放运行由RISE训练的策略，在这种模式下，模型根据过去的上下文（即多回合MDP中的状态）采样新的响应。这个过去的上下文包括与响应相关的外部反馈，并且一旦当前响应根据环境的答案验证函数被判断为正确，回放就会终止。换句话说，在奖励等于oracle响应的奖励时终止回放：。这个协议在每个回合后调用奖励函数进行查询。由于执行了多个奖励函数查询，我们将这种方法称为“有oracle”。RISE还可以在一种模式下运行，该模式避免在回放过程中查询结果检查器或奖励函数。在这种情况下，通过强制模型重试来运行完整长度的回放，而忽略响应的正确性。然后，利用基于多数投票的自一致机制来决定每个回合结束时的候选响应。具体而言，在每个回合结束时，通过对前几个回合的所有响应候选进行多数投票来确定响应，包括第回合。称之为“无oracle”。大多数评估使用的是无oracle的方法。在迭代中，由于智能体能够从改进其响应到（当时），为了避免测试时分布偏移，在这两种模式下，当回合数大于迭代数时，使用大小为的滑动窗口来存储最近的对话历史。

如上图所示，RISE推理时有两种查询模型的方式：(1)有oracle（左侧）：每当模型改进其响应时，它可以检查其答案与环境的匹配，并在找到正确答案后提前终止；(2)无oracle（右侧）：要求模型顺序修正其自身的响应次，并对来自不同回合的所有候选输出进行多数投票，以获得最终响应。如果回合数大于迭代数，则智能体仅保留最近的历史记录，限制为次交互，以避免测试时分布偏移。

多智能体模仿学习

多智能体模仿学习(Multi-Agent Imitation Learning, MAIL)是一种研究如何通过模仿专家的行为来训练多个智能体的学习方法。该方法的核心思想是利用专家在特定环境中的示范，帮助学习者协调和优化一组智能体的行为。主要特点：模仿学习基础，多智能体模仿学习(MAIL)基于模仿学习的原理，旨在让智能体通过观察专家的行为来学习如何在复杂环境中做出决策，而无需依赖明确的奖励信号；行为匹配，传统的模仿学习方法通常将问题简化为在专家示范的支持范围内匹配专家的行为。这种方法在非战略性智能体中能够有效地减少学习者与专家之间的价值差距，但对于具有战略性的智能体则可能不够鲁棒；遗憾差距，在多智能体环境中，由于智能体之间可能存在战略性偏离，因此需要引入新的目标，例如“遗憾差距”，以更好地处理可能的策略偏离。这种方法考虑了智能体在面对不同状态时可能采取的不同策略，从而提高了系统的稳定性和鲁棒性。多智能体模仿学习(MAIL)的方法可以包括行为克隆(Behavior Cloning)和逆强化学习(Inverse Reinforcement Learning)。行为克隆直接模仿专家的动作，而逆强化学习则试图推断出专家行为背后的奖励函数。处理战略性偏离是多智能体模仿学习(MAIL)面临的一大挑战。未来的研究可能会集中在如何设计更有效的算法，以应对智能体之间的相互影响和复杂交互。未来多智能体模仿学习(MAIL)也需要适应动态变化的环境，以实现更高效的协作和决策能力。

遗憾差距(Regret Gap)是多智能体模仿学习(MAIL)中的一个重要概念，旨在解决智能体之间的策略协调问题。与传统的价值差(Value Gap)不同，遗憾差距明确考虑了智能体可能的策略偏离，提供了一种新的目标函数来提高系统的鲁棒性。遗憾差距定义：遗憾差距是指在多智能体系统中，由于智能体的策略偏离而导致的性能损失。它关注的是在给定状态下，智能体在选择不同策略时可能产生的遗憾值。价值差通常用于衡量学习者与专家之间的行为匹配程度，而遗憾差距则更关注在面对战略性偏离时的表现。研究表明，即使实现了价值等价，遗憾差距仍然可能非常大，这意味着在多智能体模仿学习(MAIL)中实现遗憾等价比实现价值等价更为复杂。为了最小化遗憾差距，研究者提出了两种有效的方法：MALICE(在专家覆盖假设下)和BLADES(在可查询专家的情况下)。这些方法通过将问题规约到无遗憾在线凸优化中，从而有效地处理策略偏离的问题。遗憾差距作为多智能体模仿学习(MAIL)中的新目标，为处理智能体之间的策略协调和鲁棒性问题提供了新的视角。通过深入研究价值差与遗憾差之间的关系，以及提出有效的算法来最小化遗憾差距，可以显著提升多智能体系统在复杂环境中的表现和稳定性。

无遗憾在线凸优化(No-Regret Online Convex Optimization)是一种在线学习框架，旨在通过优化算法在动态环境中有效地处理凸优化问题。该方法的核心思想是设计能够在面对对手或环境变化时，保证学习者的决策不会产生显著的遗憾值。特点：在线学习，无遗憾在线凸优化关注的是在每一轮决策中，学习者根据当前信息选择一个决策，并在后续观察到损失。学习者的目标是通过不断更新策略来最小化累积损失；凸优化，该方法假设损失函数是凸的，这意味着任何局部最优解都是全局最优解。凸函数具有良好的数学性质，使得优化过程更为稳定和可预测；遗憾度，遗憾度是指在在线学习过程中，学习者所遭受的实际损失与最优静态策略所能获得的损失之间的差距。无遗憾在线凸优化算法旨在确保随着时间的推移，学习者的遗憾度逐渐减小。其算法包括：在线梯度下降(Online Gradient Descent, OGD)OGD是无遗憾算法中最经典的算法之一。它通过在每个时间步使用当前损失函数的梯度来更新模型，从而实现对损失函数的有效优化；在线牛顿步(Online Newton Step, ONS)ONS是另一种用于处理在线凸优化问题的方法，特别适用于强凸函数。它通过利用二阶信息来加速收敛，并能够达到更优的遗憾界限。

遗憾界限(Regret Bound)是一个重要的概念，尤其在在线学习和决策理论中。它用于描述在特定决策过程中，学习者与最优策略之间的性能差距，具体体现在遗憾值的上限。特点：遗憾界限是指在一系列决策中，学习者所遭受的实际损失与最优静态策略所能获得的损失之间的最大差距。它衡量的是学习者在面对动态环境时，未能选择最优策略所造成的潜在损失；遗憾值，遗憾值是指学习者在每个时间步骤中，基于其选择的动作与所有可能动作的最佳结果之间的差异。遗憾界限则提供了一个数学上可量化的上限，表示随着时间推移，学习者的遗憾值不会无限增长；无遗憾算法，在无遗憾在线凸优化中，算法设计的目标是确保遗憾界限随着时间的推移而收敛到0。这意味着，通过足够多的学习和调整，学习者的决策将逐渐接近最优决策。

遗憾界限在在线学习算法中起着核心作用，特别是在需要实时决策和适应环境变化的场景，如金融市场、广告投放和推荐系统中。在多智能体环境中，如果所有智能体都采用无遗憾学习算法，那么它们的联合行为将渐进地收敛于一组无遗憾点。遗憾界限帮助分析和优化智能体之间的协调与合作。在数学上，遗憾界限通常通过不等式来表示，例如：

其中是在次决策中的总遗憾值，而是一个常数或函数，表示遗憾界限。通过设计有效的算法，研究者可以控制这个界限，使其保持在可接受范围内。

策略偏离(Strategic Deviation)是多智能体系统和博弈论中的一个重要概念，指的是智能体在决策过程中选择与预定策略不同的行动。这种偏离可能是出于自我利益的考虑，尤其是在存在多个智能体相互影响的环境中。特点：自利行为，智能体可能会因为追求个人利益而偏离团队策略。例如，在合作博弈中，某个智能体可能选择背叛而不是合作，以期获得更高的短期收益；对系统的影响，策略偏离可能导致整体系统性能下降，因为个别智能体的自利行为可能破坏团队的协调与合作。例如，在多智能体强化学习中，如果某个智能体偏离了团队策略，可能会导致整个团队无法达到最优解；博弈论中的均衡，博弈论背景，纳什均衡是一种状态，其中没有参与者能够通过单方面改变自己的策略来获得更好的收益。策略偏离意味着某个智能体试图打破这种均衡，从而可能导致新的均衡状态或不稳定性。策略偏离是多智能体系统中的一个关键问题，它影响着系统的稳定性和效率。通过合理设计奖励机制、使用遗憾最小化算法以及强化学习中的合作机制，可以有效应对策略偏离带来的挑战，提高多智能体系统的整体性能。假设开发一个路由应用程序，为一组用户提供个性化的路线推荐（），这些用户具有联合策略（例如，Google Maps中提供的路由策略）。与模仿学习(IL)中的常规假设一样，假设访问来自专家的示范（例如，历史版本）。两种类型的用户（智能体）：非战略用户，他们盲目跟随路由应用程序的推荐；以及战略用户，他们在有激励时会偏离推荐（例如，向繁忙的司机推荐了一条较长的路线）。用表示中介学习到的策略在第个智能体的价值。

  • 案例一：无战略智能体。在所有智能体都完全服从的理想情况下，将多智能体模仿学习(MAIL)问题视为联合策略上的单智能体模仿学习(SAIL)问题。 将价值差距降低到0，只要所有智能体盲目遵循建议，学会了一种策略，其表现至少与专家的策略相当。在路由应用程序中，意味着如果没有司机偏离先前的行为，所有司机的满意度至少与应用程序的先前版本相同。
  • 案例二，战略智能体，对于任何多智能体模仿学习(MAIL)问题，如果智能体具有代理权，需要考虑到智能体可能会偏离建议，如果从他们的主观角度来看这样做似乎是有利的。将智能体的偏差（即策略修改）类表示为。定义由中介的策略引起的遗憾为： 其中，是智能体的战略偏差，而是由除之外的所有智能体遵循的建议所诱导的联合智能体策略。直观上，遗憾捕捉了任何智能体在群体中偏离中介建议的最大动机。然后，比较专家和学习者策略之间的这一指标，以得出遗憾差距。 将遗憾差距降低到0（即实现遗憾等价）意味着，即使智能体可以自由偏离，学习到的策略在群体中任意智能体的角度来看，至少与专家的策略同样优秀。但所有智能体在选择替代路线时的动机不会比在应用程序的历史版本下更大。较小的价值差距通常并不意味着较小的遗憾差距。考虑在所有服从的情况下学习者策略与偏离的第个智能体之间的性能差异()和()。我们可以将这个量分解为以下内容： 其中表示在专家建议和偏差下的智能体联合行为。第三项是标准的单智能体价值差距（即在假设没有智能体偏离的情况下的性能差异）。第二项是专家在偏差下的遗憾（即无法控制的量）。遗憾差距与价值差距目标之间的差异可以归结为第一项：。请注意，由于偏差引起的状态分布变化，最小化第三项并不能保证第一项的结果。在多智能体模仿学习(MAIL)中，遗憾是困难的，因为它需要知道专家在面对任意智能体偏差时会做什么。
  • 马尔可夫博弈中多智能体模仿学习(MAIL)的遗憾差距。与单智能体模仿学习中的标准目标——价值差距不同，遗憾差距捕捉了群体中的智能体可能会偏离中介建议的事实。从价值差距到遗憾差距的转变反映了单智能体模仿学习和多智能体模仿学习问题之间的根本区别。
  • 遗憾差距与价值差距之间的关系。在完全奖励和偏差函数类别的假设下，遗憾等价意味着价值等价。然而，价值等价对遗憾差距几乎没有保证，从而确立了将单智能体模仿学习算法应用于多智能体模仿学习问题的基本局限性。
  • 提供了一对在特定假设下最小化遗憾差距的高效算法。虽然在一般情况下实现遗憾等价是困难的，因为它依赖于反事实专家建议，但推导出一对高效的方法来最小化遗憾差距，这些方法在不同假设下运行：MALICE（在覆盖假设下运行）和BLADES（需要访问可查询的专家）。证明这两个算法可以提供关于遗憾差距的界限，其中是时间范围，与单智能体模仿学习中已知的最强结果相匹配。

单智能体模仿学习(SAIL)的理论大多集中在单智能体设置上。离线方法如行为克隆(BC)将模仿问题简化为纯粹的监督学习。忽视专家和学习者策略之间状态分布的协变量偏移可能导致累积错误。为此，交互式模仿学习方法如逆强化学习(IRL)允许学习者在训练过程中观察其行为的后果，从而防止累积错误。由于需要反复解决一个困难的强化学习问题，这些方法可能相当低效。替代方法包括交互式查询专家，以获取学习者诱导状态分布上的动作标签(DAgger)，或者在假设演示完全覆盖的情况下，使用重要性加权来纠正协变量偏移(ALICE)。在相同假设下运行，BLADES和MALICE算法可以看作是遗憾差距与价值差距的类比。

多智能体模仿学习(MAIL)的遗憾差距概念最早是在Waugh等人的工作中提出的，尽管他们的研究仅限于标准形式博弈(NFG)，而我们关注的是更一般的马尔可夫博弈(MG)。Fu等人简要考虑了马尔可夫博弈中的遗憾差距，但并未探讨其性质或提供有效最小化的算法。大多数经验性的多智能体模仿学习(MAIL)工作基于价值差距，而我们则退一步思考，首先要问的是多智能体模仿学习(MAIL)的正确目标是什么。

逆游戏理论(Inverse Game Theory)是博弈论的一个分支，主要关注如何根据观察到的智能体行为推导出效用函数或策略，而不是通过示范学习来协调行为。这种理论的核心在于理解和重建参与者在博弈中所采取的策略背后的动机和效用。特点：目标导向，逆游戏理论的主要目标是恢复一组效用函数，这些函数能够合理化观察到的智能体行为。这与传统的博弈论不同，后者通常关注如何在给定的效用函数下优化策略；应用场景，逆游戏理论常用于分析多智能体系统中的决策过程，尤其是在信息不完全或不对称的情况下。它可以帮助研究者理解复杂环境中各个智能体之间的互动；方法论，逆游戏理论通常涉及从智能体行为中推断出潜在的效用结构。研究者可能会使用统计和机器学习方法来分析数据，以识别和恢复这些效用函数；与逆强化学习的关系，逆游戏理论与逆强化学习有交集，后者同样关注从专家行为中推导出奖励信号。在逆强化学习中，目标是找到一个奖励函数，使得专家的行为是最优的，而在逆游戏理论中，则是找到合理化智能体行为的效用函数。

效用函数(Utility Function)是博弈论和经济学中的一个重要概念，用于量化参与者在决策过程中所获得的效用或满意度。定义：效用函数通常表示为，其中是消费品或策略的集合，是实数集。该函数将每个可能的结果映射到一个实数值，表示该结果所带来的效用。在博弈论中，效用函数用于描述每个参与者在不同策略组合下的收益。例如，在一个策略型博弈中，每个参与者的效用不仅取决于自己的策略选择，还取决于其他参与者的策略。因此，参与者会根据自己的效用函数来选择最优策略，以最大化自身的收益。效用函数的类型分为2种：直接效用函数，只依赖于消费束（商品数量向量），例如；间接效用函数，依赖于商品价格和消费者预算约束，例如。效用函数是理解经济行为和决策过程的重要工具。它不仅帮助研究者分析消费者行为，还在博弈论中为参与者提供了评估和选择策略的方法。通过建立适当的效用函数，可以更好地理解和预测个体在复杂环境中的行为。

首先表示集合上的概率分布空间。用表示每个算法优化的损失函数，这可以被视为对总变差距离(Total Variation Distance, TV)的一个凸上界。当损失函数恰好是总变差距离时，则用来表示。总变差距离(TV)是一种用于量化两个概率分布之间差异的统计测量。它被定义为两个不同分布在同一事件上分配的概率之间的最大差异。

马尔可夫博弈(MG)，用来表示一个包含个智能体的马尔可夫博弈(MG)。这里是时间范围，是状态空间，是所有智能体的联合动作空间。用来表示转移函数。此外，智能体的奖励（效用）函数表示为。最后，用表示初始状态分布，从中抽样初始状态。

学习协调，不考虑在马尔可夫博弈中学习单个智能体策略的问题，而是从中介的角度出发，给每个智能体提供建议，以帮助他们协调行动（例如，一个智能手机地图应用为一组用户提供方向）。在每个时间步，中介会给每个智能体在当前状态下一个私有的动作建议。关键是，没有智能体会观察到中介提供给其他智能体的建议。可以将中介表示为一个马尔可夫联合策略，其中。用表示在状态下推荐联合动作的概率。用表示智能体根据中介策略所采取的联合策略。当智能体完全遵循中介的建议时，联合策略表示为。

轨迹指的是从开始生成的一系列状态-动作对，通过反复从策略和转移函数中抽样联合动作和下一个状态，进行次时间步。设表示在时间步长下按照策略的状态访问分布，并且让 为平均状态分布。让表示占用测度——即在时间步长到达状态并采取动作的概率。根据定义，。让为平均占用测度。

用表示智能体在此策略下从时间步长开始的期望累计奖励，即，将智能体的Q值函数定义为。定义智能体的优势为其在选定动作上的Q-值与状态的V-值之间的差，即，还定义从智能体的角度来看策略的表现为，注意，表现是占用测度与智能体奖励函数之间的内积，即。

通过引入相关均衡(CE)的概念。首先，将第个智能体的策略偏差定义为映射。直观上，策略偏差捕捉了智能体如何响应当前世界状态和中介的建议——他们可以选择服从（此时）或偏离（此时）。令为智能体的偏差集合，它是所有可能偏差的子集。用来表示所有智能体的偏差。假设对于所有的，恒等映射属于。用来表示由中介策略被偏差覆盖所诱导的联合智能体策略，即。

设为马尔可夫博弈中的中介策略，并且为每个智能体的偏差类。然后，定义中介策略的遗憾（遗憾）为：

一个中介策略诱导一个-近似相关均衡(CE)，如果：

遗憾（遗憾）捕捉了任何智能体通过偏离中介建议所能获得的最大效用。相关均衡(CE)是一个诱导的联合策略，在这个策略下，没有智能体有很大的动机去偏离。

遗憾差距与价值差距之间的关系：

  • 价值差距(value gap)：定义专家策略与学习者策略之间的价值差距为：
  • 遗憾差距(regret gap)：定义专家策略与学习者策略之间的遗憾差距为： 当学习者的策略在价值/遗憾等价时，则价值/遗憾差距为0。如上图所示，多智能体模仿学习(MAIL)中价值和遗憾差距之间的关系，用和来表示策略在奖励函数下的价值/遗憾。

如果奖励函数类和偏差类都是完整的，那么遗憾等价性等同于价值等价性。当奖励函数类是完整的时，则（即所有状态-动作指标的凸组合）；而当偏差类是完整的时，则对于每个智能体，有（即所有可能的偏差）。

定理一：如果奖励函数类和偏差类是完整的，并且满足遗憾等价性（即），那么价值等价性也得以满足：。

定理二：存在一个马尔可夫博弈(MG)、一个专家策略和一个训练过的策略，使得真实奖励函数满足遗憾等价性，即，而价值差距为。

综合这些结果，当奖励函数/偏差类足够表达时，遗憾等价性比价值等价性更强。价值等价性并不代表着低遗憾差距！在最坏的情况下，价值等价性无法提供任何有意义的遗憾差距保证。这揭示了SAIL与MAIL之间的一个关键区别。

定理三：存在一个马尔可夫博弈(MG)、一个专家策略和一个学习者策略，使得即使策略的占用测度与完全匹配，即对所有状态和动作组合有（即在所有奖励下具有价值等价性），遗憾差距却满足。
如下图所示，专家和学习者策略仅访问下路径中的状态。训练过的策略通过在访问的状态中采取相同的动作，完美匹配了专家的占用测度。然而，专家演示缺乏对状态的覆盖，因为通过执行无法到达该状态。当智能体1偏离原始策略时，这一遗漏变得至关重要，使得状态在高概率下无法到达。因此，训练过的策略在状态的表现可能很差，而专家在真实奖励函数下却能表现出色。这一例子突显了价值等价性与遗憾等价性之间的关键区别：前者仅依赖于策略实际访问的状态，而后者则依赖于学习者在未访问状态下对智能体偏离所做出的反事实推荐。

正如定理三所示，即使学习者能够从专家演示中获得关于均衡路径的无限样本，学习者仍可能对专家在未被访问（但可由偏离的智能体的联合策略到达）的状态下的行为一无所知。因此，从信息理论的角度来看，学习者无法在不知道专家在这些状态下会如何行动的情况下最小化遗憾差距。这展示了最小化遗憾差距的根本困难，因此，在MAIL中，遗憾是“困难”的。因此，需要一种新的MAIL算法范式来最小化遗憾差距。

在这里，。注意，当所有智能体都遵循时，且状态是未被访问的，但在偏离策略下，其访问概率为1（）。这意味着，除非知道专家在状态下会如何进行反事实推荐，否则无法最小化遗憾差距。

定理四：如果专家策略诱导了一个-近似的相关均衡(CE)，并且学习者策略满足，那么诱导一个-近似的相关均衡(CE)。

然后，通过与定理三结合，可以得出低价值差距并不意味着学习者正在执行相关均衡。

推论：存在一个马尔可夫博弈(MG)、一个专家策略和一个学习者策略，使得诱导了一个-近似的相关均衡(CE)，并且满足，则诱导一个-近似的相关均衡(CE)。综合这些结果表明，如果希望在智能体中诱导出一个相关均衡(CE)，那么遗憾差距是一个更合适的目标。

尽管已经表明价值差距在某种意义上是一个“较弱”的目标，但在许多现实场景中，智能体可能是非战略性的。在这些场景中，最小化价值差距可以是一个合理的学习目标。单智能体逆向强化学习算法的多智能体推广可以有效地最小化价值差距——因此，在多智能体学习中，价值是“简单的”。行为克隆(BC)和逆向强化学习是两个旨在最小化价值差距的单智能体模仿学习算法。通过在联合策略上运行这些算法，我们可以将行为克隆(BC)和逆强化学习 应用于多智能体设置，称之为联合行为克隆(J-BC)和联合逆向强化学习(J-IRL)。这样做会导致与单智能体设置相同的价值差距界限。

定理五：如果J-BC返回一个策略，使得，那么价值差距。

定理六：如果J-IRL输出一个策略，其此刻的匹配误差满足：

那么价值差距为：。满足上述任一定理的条件可以通过归约到无遗憾在线学习以高效地实现。

如何区分多智能体逆向学习与单智能体问题。简而言之，在具有战略性的智能体问题中（这些智能体并非仅仅是傀儡），需要处理：群体中智能体偏离（一种新的分布变化）。这种新的分布变化来源于无法通过与环境有效的交互（即逆向强化学习）。在这种情况下，需要能够估计专家在反事实状态下的行为。基于这一问题，提出了2种最小化遗憾差距的方法：MALICE(在专家覆盖假设下) 和 BLADES(在可查询专家的情况下)。