Transcription
大家早上好。欢迎来到 IFDS 工作坊的第二天。今天上午，我们将进行一个关于强化学习的精彩环节。我们的第一位演讲者是来自伊利诺伊大学厄巴纳-香槟分校的 Nanjang。他曾在密歇根大学获得博士学位，并在微软研究院纽约分部做过博士后。我说得对吗？是的。然后他加入了伊利诺伊大学，并一直担任那里的教职，致力于强化学习的理论基础研究。他获得了许多奖项，如美国国家科学基金会职业奖、斯隆奖、谷歌研究奖，以及一些最佳论文奖。今天，他将与我们分享他对强化学习的一个新视角。
>> 感谢您的介绍，也感谢大家的到来。我研究强化学习，希望今天能从一个你们可能从未听过的角度，告诉你们一些关于强化学习的差异。
好的。我们已经看到了强化学习在各种游戏，如棋盘游戏、电子游戏，甚至聚变反应模拟中取得的令人瞩目的成功。虽然这些成功非常令人印象深刻，但如果我们仔细审视这些案例，它们的共同点是它们都发生在模拟器中，在那里我们拥有无限的训练数据。基本上，唯一的限制是我们的计算预算，我们可以通过试错来学习，并且可以自由地采取任何我们想要的行动，而无需担心采取次优甚至危险行动的后果。
另一方面，许多重要的潜在强化学习应用并没有高保真模拟器，例如在医疗场景或在线推荐中。当人类是我们要优化的环境的一部分时，这一点尤其如此。即使在高度复杂的物理系统中，我们也无法完全依赖模拟器。模拟器并非完美，可能需要使用一些真实世界的数据来弥合模拟与现实之间的差距。在这些场景中，我们大多数依赖模拟器便利性的算法将不再直接适用。
为了应对这一挑战，强化学习社区已经达成共识：离线强化学习，即仅基于预先收集的数据训练智能体，是实现强化学习在现实生活中应用的重要范式。现在已经过去几年了，发表了成千上万篇关于这个主题的论文。但你可能会问：应用在哪里？为什么我们没有看到离线强化学习在我们生活的方方面面得到部署？
好的，这就是我想提供的一个原因。作为副产品，我的演讲也将触及强化学习的各种理论基础。在强化学习中，最终每个人都希望解决高维复杂环境的问题，这些环境具有高维状态或观测空间，我们需要使用神经网络进行泛化。但为了建立理论基础，我们通常需要先简化问题。传统上，我们这样做的方式是远离复杂环境，研究具有有限且小状态空间的玩具问题。这就是所谓的“表格法”，就像维基百科上关于马尔可夫决策过程的页面一样，我们在这里发展成熟的理解，开发正确的算法，然后将算法和分析扩展到复杂设置。
那么，建立理论基础的唯一方法就是这样吗？或者是否存在一些替代的表述，能够为我们提供多年来一直未能获得的根本性见解？作为一点剧透，你可以考虑的一种具体方法不是简化环境，而是简化假设空间，就像我们在学习理论中所做的那样。我们将继续考虑高维复杂环境，这在整个演讲中都将如此。但如果我们不考虑神经网络，而是从有限的假设类开始呢？甚至更简单，如果我们要求你比较两个候选假设呢？即使这个问题看起来微不足道，事实上，在监督学习中，这个问题的某个版本（我稍后会谈到）在强化学习中已经悬而未决了二十多年。
那么，让我们开始回答我的主要问题：为什么我们没有在现实应用中到处看到离线强化学习？为了回答这个问题，我们可以看看最成熟的机器学习范式，即监督学习，看看我们可以从中吸取什么教训。说到监督学习，许多人会直接想到我们使用的算法、优化、新架构等等。但我认为，监督学习在现实世界中的巨大成功，依赖于一些我们常常认为理所当然的更基本的东西：当你拿到一个数据集时，你做的第一件事不是运行你最喜欢的训练算法，而是将其划分为训练集、验证集和测试集。你可以尝试任何你想要的东西，即使是奇怪的东西，在训练集上进行尝试，最终依赖验证数据集和测试集来告诉你哪个表现最好，以及它有多好。
那么，考虑到离线强化学习和监督学习之间的相似性，因为在这两种情况下你都只有一个数据集，并且最终你想要输出一个机器学习解决方案，也许我们在离线强化学习中也应该做类似的事情。当然，我们可以进行相同的数据划分，但问题在于我们如何在强化学习中比较不同的训练算法？回想一下，在强化学习中，最终的输出是一个策略，它告诉你应该在不同情况下采取什么样的行动。因此，验证任务本质上是评估或比较这些策略的性能。由于这些策略通常会采取与数据收集期间不同的行动，因此我们面临着所谓的“离策略评估”（OPE）问题。
让我简要地深入探讨这个问题，看看典型的处理方法，这也能让我们快速回顾强化学习的基础，并确保大家都在同一页面上。顺便说一句，如果你有任何问题，请随时打断，我很乐意让这次会议尽可能互动。
在强化学习中，我们通常将问题视为一个序贯决策的动态系统。在观察到状态 $S_t$ 后，你采取行动 $A_t$，获得奖励 $R_t$，并根据转移分布随机转移到下一个状态 $S_{t+1}$。你有一个策略，它将状态映射到行动的分布。策略的最终性能由这个期望回报决定，即从某个初始状态 $S_0$ 开始的折扣奖励的总期望值。
本讲座中定义的策略评估的目标是估计给定策略 $\pi$ 的标量值。而训练的目标，通常是策略优化，是找到一个最大化或近似最大化这个期望回报的策略。
那么，我们如何进行策略评估呢？这是我们目前的重点，因为我们想要进行验证，你已经有了策略，我们想要比较它们。
事实证明，一种非常有用的方法是首先估计价值函数。这里的 Q 函数告诉我们，当你从一个特定的状态-行动对开始时的期望回报。一旦你得到了 Q 函数 $Q^{\pi}$，期望回报的标量值就是初始状态下的 Q 函数值。那么，我们如何估计 $Q^{\pi}$ 呢？我们知道 $Q^{\pi}$ 满足贝尔曼方程，它本质上谈论的是一种时间一致性，即今天的预测应该与明天的预测一致。在强化学习的基本理论中，你被告知，如果你能将这个方程作为对每个状态-行动对的约束，你就能保证 $Q^{\pi}$ 是唯一的解。
当然，在任何实际感兴趣的问题中，这都不会发生。在任何实际问题中，我们都有大量的状态。所以我们通常的做法是，将你的状态或观测值参数化，例如使用神经网络，并尝试近似 $Q^{\pi}$。我们今天主要关注的算法称为“固定点 Q 评估”（FQE）。它的做法是迭代地解决一系列最小二乘回归问题，其中回归目标（你从这里预测）依赖于算法上一轮迭代的输出 $Q^{k-1}$。这是一个迭代算法，这里的期望通常是基于你拥有的任何数据，我们通常将其视为元组的分布，而实际上它通常是从轨迹数据中提取的。
这个过程模仿了动态规划中著名的价值迭代算法，它也可以被看作是更熟悉的算法，如时间差分（TD）的理论版本、原型、批量版本或原型。如果你考虑一下 TD 实际上在做什么，当你去掉所有这些复杂性，如目标网络、异步更新等等，这就是最清晰的版本。
现在，如果我们采用这个算法，但简单地改变行动选择，从你要评估的策略改为贪婪选择，最大化行动，我们就得到了 FQI 迭代或 FQI，它最终实际上估计了最优 Q 函数，从而诱导了近似的最优策略。同样，这是熟悉强化学习训练算法，如 DQN 或带函数逼近的 Q-learning 的批量版本或原型。
为了本次演讲的目的，你可以认为我们首先运行 FQI，可能使用不同的神经网络架构、不同的学习率等等，然后你得到近似 $Q^*$，它们输出一个近似 $Q^*$ 的函数，然后你将其贪婪化，得到一个潜在的近似最优策略，但其中一些可能很差，然后你将它们插入 FQE，它告诉你每个策略有多好。然后你说，好吧，我选择评估值最高的策略。
那么，问题是什么？好的，所以如果你考虑这个问题，实际上这个范式，我给你的这个流程，在以下方面是绝对荒谬的：我们试图做一些类似交叉验证的事情，其目的通常是调整训练的优化参数和神经网络架构等等。但验证过程本身是一个复杂的算法，其结构与训练算法几乎相同。如果这个过程选择了训练的所有这些参数，那么谁选择了这个过程呢？这实际上是一个巨大的鸡生蛋问题，它基本上一直存在，只是除了我之外没人谈论它。但对我来说，这是离线强化学习许多实际部署的真正瓶颈。事实上，几个月前，我们有一位来自 Meta 的访客，他正在研究用于推荐系统的强化学习，他们有一个非常长期的优化问题。他直接问我，他说我运行 FQE，但我绝对不知道是否应该信任它，因为如果我改变神经网络架构，它们都会给出看起来合理的结果，但它们只是都不同，而且基本上你没有合理的方法来判断哪个更正确。
那么，他们问的问题是：是否存在可以真正帮助你以一种真正无超参数的方式进行验证的替代方法？事实证明，答案是肯定的，你可以使用所谓的“重要性采样”方法。回想一下，我们之所以面临这个问题，是因为在收集数据时，你选择的行动与候选策略会选择的行动不同。这很自然，因为在收集数据时，你甚至不知道一个好的策略是什么，你怎么知道应该选择什么行动？重要性采样框架首先要求你在数据收集期间随机化你的行动选择，然后粗略地说，以一种非常简化的方式，你所做的就是只查看数据收集期间那些随机碰巧与你要评估的目标策略匹配的数据点。如果你做得正确，你将获得无偏估计，但代价是更高的方差，或者从另一个角度看，有效样本量减少。
这在许多单步强化学习的赌博机场景中效果非常好，我也见过工业部署。但它在多阶段决策制定中确实存在一个大问题：首先，你需要轨迹数据；其次，你需要丢弃所有数据轨迹，只要其中有一个行动不匹配。你可以想象，剩下的仍然有用的样本，其数量只是你整个数据集的一个指数级小的部分。你们中的一些人可能知道，你可以使用方差控制技术，或者双重稳健估计器来减少重要性采样估计器的方差。我们尝试过，它有帮助，但根本上，如果你的环境是随机的，指数级方差就不会消失。
所以，如果你想以一种无超参数的方式评估策略，至少目前看来，这似乎是一条死胡同。但这并不是故事的结局。让我们再看看训练算法。我们拟合一个近似函数来近似 $Q^*$，最优 Q 函数，就是这个家伙，然后将其贪婪化成一个策略。所以，与其直接看策略，不如看看价值函数怎么样？希望价值函数比策略具有更丰富的信息和更多的结构。所以也许我们有机会以更有效的方式比较它们。
这是重新表述的问题。你运行不同的训练算法，得到候选价值函数 $f_1, f_2, f_3$ 等等。我们有一个数据集，就像往常一样，包含状态、行动、奖励、下一个状态元组。任务是，如果其中一个候选函数接近 $Q^*$，我们希望找到它。为了消除退化解，我们将要求留出样本量要小，这意味着它不应该对 horizonte 有指数依赖性，或者你对重要性采样感到满意。它也不应该有对状态数量的显式依赖性，否则你就可以采用表格法。此外，不要告诉我使用任何进一步的函数逼近，说“哦，我们可以解决这个问题，如果这是你应该逼近的对象，让我们写一个神经网络来逼近它。”不。因为那样的话，我怎么选择那个神经网络的参数呢？所以，没有进一步的函数逼近。基本上，$f_1, f_2$ 等等。以及数据集，所有你可以用来写算法的符号都在这个幻灯片上。你不能使用任何其他东西。
事实上，我将进一步简化它。假设我们只有两个函数 $f_1$ 和 $f_2$，我告诉你其中一个是 $Q^*$，我们一无所知，你怎么区分它们？你可能不相信我，但让我告诉你，如果你深入思考这个问题，你会想到的第一个想法是什么？事实上，有人在近 30 年前就考虑过这个问题，Leon Bear 在 1995 年。他考虑了这个问题，当然不是通过交叉验证，因为那时离线学习还不是一个概念，但他通过训练的视角来考虑它，我们将看到，这个训练视角对于解决我们这里的问题至关重要，并且将我们试图解决的问题与现代深度强化学习中的一些核心算法挑战联系起来。Bear 的问题很简单，他问：我想从数据中进行价值函数估计，我能以一种简单的方式将其表述为：我可以写一个损失函数，一个关于不同候选函数的损失，使得价值函数估计可以写成最小化这个损失，并且损失可以从数据中估计出来吗？
听起来熟悉吗？是的，这就是我们大多数情况下进行机器学习的方式。你有一个损失，你从数据中估计它，然后你 just 优化它。不幸的是，对于大多数基于...抱歉...你可能想知道这与模型选择或交叉验证有什么关系？因为如果这是真的，我们就可以立即解决交叉验证问题，只需让函数空间成为我们从中选择的候选函数集。毕竟，验证本质上是一个在不同数据集上进行的二次训练过程，具有有限且易于管理的假设类。
对你们中的一些人来说，反应可能是：等等，当前的算法不是这样的。嗯，它们不是。对于大多数基于动态规划的算法，我们之前提到过，你所做的是解决一系列最小二乘回归问题。当你解决最小二乘回归时，它是一个优化问题，但更高级别来说，它实际上具有迭代性质。所以你不能写下一个单一的优化目标，说这就是我正在优化的东西。迭代性质也至少部分地导致了你在深度强化学习中看到的各种训练不稳定的问题。
理论上可以证明，这些迭代算法都存在严重问题，因为存在非常简单的环境，你可以证明这些算法即使拥有无限的数据和完美表示目标价值函数的单维线性函数类，也会发散。我不知道还有什么更好的性质可以想象。
那么，问题是，但我们仍然有大量的强化学习理论论文，我们如何绕过这个问题？在我们的理论中，我们通常的做法是引入所谓的“贝尔曼完备性假设”，该假设声称我们使用的函数空间不仅捕获了 $Q^*$，即我们要使用的目标函数，而且在贝尔曼算子下是闭合的，也就是说，当你对函数类中的一个函数进行贝尔曼更新时，它仍然在函数类中。当然，这是一个假设，因为通常情况并非如此。通常，即使你的函数空间捕获了目标函数，如果你看其他任意函数并进行贝尔曼更新，它们通常会让你脱离你的函数空间。有人可能会争辩说，如果你使用丰富的神经网络和丰富的连续假设类，这个假设可能是合理的。但对于交叉验证来说，你的假设空间只是少数离散假设，这完全没有意义。
长话短说，用单一优化替换迭代算法是强化学习中的一个梦想，如果我们能做到这一点，我们也将立即解决我们的模型选择问题。为什么这么难？为了理解其中的难度，让我们回顾一下 Leon Bear 的做法。他的推理非常自然。我们知道 $Q^*$ 满足贝尔曼方程，对吧？那么，我们为什么不直接取方程两边的差值呢？然后将其作为损失。现在，方程的差值仍然是方程，它是一个函数，仍然是状态-行动对的函数。所以我们取它的平方，并对我们在数据中看到的状态-行动对的某个分布取期望。我们有了一个损失。事实上，这就是人们在不严谨的经验论文中告诉你的：哦，强化学习就是最小化贝尔曼误差，这就是贝尔曼误差。他们不是，他们是前面幻灯片中看到的迭代算法。
那么，为什么人们不这样做呢？因为我们不能。如果你真的写下这个损失函数，你会发现棘手的部分是，你有一个条件期望，它对应于平方内的贝尔曼算子，我们知道这是我们在估计中不喜欢的东西。如果你有一个平方内的条件期望，这意味着你不能直接估计它。如果你使用朴素估计器，有时我们称之为单样本估计器，它只是忽略条件期望并使用数据中看到的随机下一个状态，它已知是一个有偏估计器。你有一个额外的方差项，它在不同的候选函数之间变化。所以你不能，不像监督学习中固有的标签噪声项对所有预测器都相同。所以即使你知道有这个额外的项，你也可以忽略它。在这里，不能安全地忽略这个项。
历史上，人们一直在思考如何消除这种偏差。嗯，事实证明，要么需要一个模拟器，如果你能从同一个状态中抽取两个独立的下一个状态，你就可以很容易地得到一个无偏估计器，这个过程被称为“双重采样”，这也是这个困难得名的地方。它通常被称为“双重采样问题”或“双重采样困难”。或者你需要一个辅助类，你需要额外的函数逼近来逼近候选函数的贝尔曼更新，这又引入了我们问题中的鸡生蛋问题。
好了，从训练的角度看到了问题的难度之后，我现在将告诉你我们如何解决这个问题。提醒大家一下，我想解决的问题是：我有两个候选函数 $f_1$ 和 $f_2$。其中一个是 $Q^*$。我想找到它。为了理解我们的解决方案，我们需要 Jeff Gordon 大约在同一时间得到的关于训练的旧结果。回想一下，所有这些动态规划算法在强化学习中通常是不稳定的，它们可能会发散。它们没有保证，如果你只假设最终你想要学习的函数是可实现的。
如果线性不起作用，也许更简单的方法可以起作用？我们知道表格法可以工作，但有没有介于表格法和线性之间的方法呢？事实证明，是的。如果你在训练或近似动态规划中使用分段常数函数类，你就能保证稳定性和收敛性。这本质上是将你的状态空间或状态-行动空间划分为不同的组，你基本上将该组中的所有状态视为等同于某种巨型状态。这在所谓的“状态抽象”或“状态聚合”文献中得到了研究。对于分段常数函数类，它本质上只是诱导它的分区的不同表示。在接下来的演讲中，我将交替使用这两个术语。
这是为了训练，但我们也可以将这个结果翻译到验证。也就是说，如果有人给了我们这样一个好的函数类或状态空间的划分，我将在验证的上下文中称之为 $G$，那么有无数种方法可以让我用它来找出正确的 Q 函数。其中一种方法是，我现在可以估计所谓的“投影误差”，这可以从数据中估计出来，并且保证如果这个误差很小，我就可以找出正确的 Q 函数。但技术上，我们需要对这个函数类有什么样的条件呢？嗯，你需要三个条件。一是分段常数，我们刚刚谈过。二是可实现性，即这个函数类可以表示 $Q^*$。三是它需要有少量分区，因为这决定了估计任何涉及这个类的东西的统计复杂性。
这就是我们将要采取的方法。当然，问题是，谁给了你这个好的神奇函数类 $G$ 呢？如果我将其作为附加输入要求，那又是一个鸡生蛋问题。现在我们来到了我们方法的最后一步，我将告诉你，我们可以基本上凭空创造这个神奇的函数类 $G$，当然有一些注意事项。
作为第一步，我们需要做的是验证这个神奇的 $G$ 对于任意的 MDP，可能非常非常复杂，高维等等，总是存在的。好消息是，它总是存在的。在这里，因为我只证明它的存在，我将假装我了解 MDP 的一切，并将给你一个建设性的证明，基于我不应该拥有的这些信息。我们怎么做呢？这其实非常非常简单。你看，这是 MDP 的真实 $Q^*$ 函数。我将要做的是，我首先离散化这个 $Q^*$ 的输出值，我付出了小的离散化误差，这完全没问题。然后我将要做的是，我基本上会把所有具有相同离散化输出值的状态-行动对称为同一块，即使它们在状态-行动空间中“相距遥远”，我也可以完全聚合在一起，比如这里显示的橙色区域。正如你所见，这完全有效。我使用的是一维可视化，但即使你的状态-行动空间是超高维的，这仍然有效。它保证是分段常数的，并且构造保证我可以近似表示 $Q^*$。此外，有多少块？有多少块？是 $1/\epsilon$，因为 $\epsilon$ 是离散化误差，因为 $1/\epsilon$ 基本上是函数可以取值的可能离散化值的数量。我认为人们明白了，但这通常是困惑点，所以我创建了一个更极端的例子。假设我有一个函数 $f(x)$，假设这是我的价值函数，它在所有有理数上取值 1，在所有无理数上取值 0。根据我对分段常数的定义，我需要多少块来表示它？两块，因为所有有理数是一块，所有无理数是另一块。所以我们完全忽略了状态-行动空间的拓扑结构，我们从这个函数的输出来构建这个拓扑结构。
事实上，这大致就是我们将如何构造这个神奇的函数类 $G$ 的方法。当然，你在这里有一个问题，即这个构造依赖于 $Q^*$，这是我们最终的学习目标，当然你无法访问它。但现在我声称我们基本上完成了。回到这个问题。回想一下模型选择或交叉验证问题，我们有两个候选函数 $f_1$ 和 $f_2$，我们想知道哪个是 $Q^*$。我们知道，如果有人给了你这个神奇的 $G$ 类，这个满足那些标准的划分，我就可以做到。现在我需要这个 $G$ 类。我怎么做？嗯，你只需同时根据这两个函数来划分你的状态-行动空间。
它满足之前的所有条件，并且你得到的分区的数量，因为现在你的分区是根据两个函数来的，你得到的是 $1/\epsilon^2$ 而不是 $1/\epsilon$。这不像理想情况那么好，但也不是太差，考虑到我们之前完全不知道如何解决这个问题。现在，这是两个函数的情况。如果你天真地将其扩展到多个函数，情况会很快变得非常糟糕，因为你得到的分区数量是 $1/\epsilon$ 的函数数量次方。你不想那样。所以我们做的是一个淘汰赛程序，你对你的类中的每一对函数运行这个程序，然后进行某种类型的 minimax。我在这里不详细说明，但你可以证明，对于这个程序，你有一个样本复杂度界限，它对 horizonte 的多项式依赖性，对 $1/\epsilon$ 的对数依赖性，以及候选数量，直接来自联合界和覆盖参数，这是现代强化学习理论中非常重要的一个标准保证，它衡量你的数据分布如何覆盖由不同策略引起的状态分布。那里有一些细微之处，这是一个完全独立的话题，因为这种覆盖的概念对现代强化学习理论，尤其是在离线强化学习中，是如此核心。我有一些专门讨论这个话题的演讲，但今天不是。
此外，当你尝试实现这个算法时，你可能会担心的是，哦，我们正在谈论这种潜在的、可能非常奇怪的划分，需要划分所有实数，抱歉，所有有理数作为一块，无理数作为另一块。你怎么可能用解析方法表示这个划分呢？好消息是，要实际实现这个算法，你只需要对我们拥有的数据，我们拥有的整个数据集进行投影步骤。事实证明，你只需要查看留出数据集中的数据点，你只需要判断哪些数据点属于同一组，这很容易检查。因此，你可以非常容易地用所有封闭形式的表达式来实现这个算法，没有优化，没有近似，什么都没有，而且我们确实这样做了。
这是在一些 Gym 环境以及一些 Atari 游戏（如视觉视频游戏环境，具有高维视觉输入）中的交叉验证实验结果。你只需按原样实现算法，没有任何启发式方法或近似方法等等。我在这里不详细说明，但你获得了非常有希望的性能和良好的样本效率。
好了，这是演讲的主要部分。
>> 你消除了可实现性假设。
>> 我猜你的意思是，如果 $Q^*$ 不在候选者之列怎么办？
>> 那么，如果你仍然有一个足够好的近似值，你仍然能够进行分析，但近似误差将进入最终的界限，而且方式更差。所以，如果你考虑一下，这个淘汰赛程序与像 Chef 淘汰赛那样用于 TV 距离最小化非常相似。对于所有这些淘汰赛算法来说，情况都是如此，近似误差的放大比标准 ERM 设置要多得多，在这些设置中，你知道你有多少近似误差，它直接进入最终的界限，乘数为一。但在这里，我的意思是在强化学习中，无论你有什么近似误差，它都会被放大，涉及 horizonte 等等。但在这里，它甚至更糟。所以...
>> 在非参数估计中，像一个常数因子是三或什么的。
>> 是的，所以，再次，问题在于，在强化学习中，即使在标准、研究充分的设置中，并且所有条件都很好，它也不会是常数。放大因子通常涉及 horizonte 因子。这非常糟糕。我们甚至没有谈论这个问题，这个问题甚至更难。
>> 解释一下为什么在你的淘汰赛中，比如说，如果 opt 是这个家族 f 中任何函数能得到的最好的损失，那么最终的误差不会是 opt 的常数倍。
>> 好的，我不确定我能解释得非常……如何说呢？所以，我甚至不需要谈论我的算法。让我们看看这个非常简单的程序，比如说有人给了你这个神奇的 G，然后从中学习。如果这个神奇的 G 只能以 $\epsilon$ 的精度表示 $Q^*$，一般来说，如果你在它上面运行你的算法，你会得到类似 $\epsilon / (1-\gamma)$ 的结果，所以你已经支付了 horizonte 的因子，这就像使用函数逼近的最标准、最简单的设置。我不知道如何……也许这里有一个模糊的直觉是……
>> 问题在于它有……淘汰赛的问题在于，你已经有了所有这些放大，在你能看到的强化学习的每一个算法中。
>> 我认为一个好的理解方式是，你可能会得到一个常数近似，比如说……淘汰赛目标本身的价值，但你需要将其转化为实际……
>> 所以，也许这里有另一种思考方式。所以这个函数空间可以表示 $Q^*$ 到一定程度的 $\epsilon$，但你并没有说……在监督学习中，你所做的是，你使用这个函数空间，使用空间中的函数直接逼近你的目标函数，带有一些噪声。但在强化学习中，你使用它的方式不同，你将其用于动态规划，这是一个迭代算法，你一遍又一遍地使用它，所以每次使用它时，近似的因子都会进入一次，所以 horizonte 的放大因子是预期的。你本可以问，“你对正确的最优 F 的估计有多好？”
>> 这不是一个强化学习问题，对吧？但你却说你只会得到一个常数……
>> 但你不知道。
>> 如果不是，我想看你的论文。
>> 你说的估计有多好是什么意思？
>> 所以，我不知道。我只是看看……Q 函数误差。有一个 $Q^*$。它在我的类别中。我给你 $f_1$ 到 $f_k$，我说选择最好的，直到……
>> 在某个与动态规划相关的范数下，最接近 $Q^*$ 的近似值。
>> 好的。
>> 我会得到一个常数近似吗？
>> 不。
>> 不。
>> 当然不是。我的意思是，这里也是一样。
>> 我的意思是，还有其他事情，就像在强化学习中，有几件事。比如说，当你说的“我有函数，我有……”，这是我在演讲前进行的对话。比如说，你如何衡量 f 和任何候选函数以及 f 和 $Q^*$ 之间的范数，甚至不清楚……在旧文献中，标准做法是使用无穷范数，但这太严格了，因为人们不知道如何处理分布偏移等等，所以这已经很严格了，而且你实际上无法获得任何无穷范数保证。所以你需要使用某种加权二范数，但问题是，你在什么分布下测量你的加权二范数？这甚至还没有弄清楚。所以，你不仅要支付 horizonte 的因子，你还需要支付这个分布偏移因子，这就像覆盖问题一样。所以，我理解这种不信任，但我向你保证，我见过……我学过学习理论 101。我见过这些近似是如何工作的。我研究过……淘汰赛调查。我知道淘汰赛是如何工作的。我向你保证，这种动态规划的性质，多步……正如你所见，我们在这里遇到的核心困难是，当你有多步决策时，像重要性采样这样的东西会产生指数级方差。所以，当你有非恒定的决策阶段时，会发生一些戏剧性的事情。如果你只看到多项式增长，你说哇，这是世界上最好的东西。常数……你知道，抱歉，关于优化。所以，你……
>> 我只是担心运行时间是线性的，与……
>> 是的，它是。所以你不能用它来训练。是的，它只用于模型选择。
>> 所以你可以减少搜索空间中的一些搜索问题，你可能希望以比大小小得多的时间来完成。所以至少我们还没有……嗯，我想你可以做的是，也许你可以分而治之，分成子组，在里面运行淘汰赛等等，但我认为这会损害……
>> 是的，或者，实际上它甚至不是线性的，它是二次的。
>> 是的，等等，为什么不是？
>> 我需要对所有候选函数对进行成对比较。
>> 对，哦，我以为你说的是淘汰赛。
>> 是的，是的，它是。
>> 那就再看看，不是……
>> 你真的必须做所有对，所以它真的是……
>> 是的，你需要做所有对。
>> 好的，所以你可以说你只是再看看，但没有办法……搜索问题……
>> 不，我不这么认为。
>> 我的意思是，或者，鉴于这个问题在统计学上有多难，我甚至没有担心计算问题。如果我需要支付 10 倍的计算量来获得……正如你们都可以认识到的，有所有这些不寻常的爆炸，从标准的学习理论角度来看非常糟糕。所以，如果有一些方法可以稍微改善统计特性，我愿意忍受 10 倍的计算量，但我们不知道方法。
>> Matt 正在暗示的是，存在比标准 Seref 淘汰赛更快的版本，它们不需要二次时间，可以通过一些技巧以几乎线性的时间完成。也许如果你有兴趣，可以改进你的方法使其更快。但你说这不是目标。目标是得到一个……
>> 是的。是的。所以这是一件事。而且我认为淘汰赛在这里还有一些不同之处。在 Seref 淘汰赛中，当你比较两个……抱歉，两个候选分布，它们都远离真实分布时，你所做的是，你仍然……你知道……定义样本空间的一个子集，并测量样本在该子集中的经验频率。所以，在某种意义上，你估计的任何东西仍然是无偏的，它只是缺乏区分这两个分布的能力，或者说哪个更接近。但在这里，情况更糟，因为你看，我们正在使用这种投影贝尔曼误差，我们正在测量这种投影贝尔曼误差。G 来自构造，它是由当前一对函数构建的，而这个 G 只有在它能表示 $Q^*$ 时才好。所以当你从两个都远离 $Q^*$ 的函数对构建它时，就像你有一个非常糟糕的法官一样。这个量本身就会失去所有必要的保真度，使其有意义。所以，情况比 Seref 还要糟糕。
>> 所以，是的。这实际上是一个旧的演讲。我的意思是，我有点 guilty，因为我重复使用演讲，但我以为我会谈论一些新的东西，但我想我只能一带而过。我们最近将其扩展到策略评估。基本上，整个事情是一个食谱，它说，如果你能找到一个具有常规动态规划算法所不具备的额外稳定性的基础强化学习算法，你基本上可以将其插入我们的食谱中，并获得一个模型选择算法。不幸的是，在强化学习中，满足这一标准的算法并不多。但如果你专注于策略评估任务，事实证明，我们所知的唯一其他算法是文献中被遗忘的 LSTD 算法。我们实际上将其变成了一个新的模型选择问题，你的目标是选择 $Q^{\pi}$ 而不是 $Q^*$。而且在实践中效果也非常好。
>> 而且，这里也有一些讨论。正如我所说，每当我谈论这个时，许多人的第一反应是：为什么你不采用基于模型的方法？我认为，当他们说“基于模型”时，他们脑子里想的是，他们想构建一个基于表格的模型，然后用它来评估你的策略。当然，这不会发生。而且，每当你构建一个模型时，在实际问题中，你需要函数逼近，你需要所有这些超参数。所以这是另一个鸡生蛋问题。
>> 话虽如此，基于模型的方法确实有一个相当大的优势。那就是你可能可以在模型学习阶段进行调优、验证、模型选择。一旦你学会了模型，你就信任它。为什么呢？因为你知道模型学习步骤基本上是一个监督学习问题。你根据当前的状态-行动对来预测下一个状态。所以有一个真实值，就是下一个状态。所以你基本上可以使用任何你喜欢的东西来进行模型选择，除了那里有各种各样的注意事项。例如，你可能有一个模型，它进行平均预测加上一些噪声，然后你说，好吧，我们如何使用一个损失，它是数据中的真实下一个数据减去模型预测，这是一个随机状态，然后说，让我们取一些范数。嗯，首先，范数是一个任意的设计选择，其次，真的，如果你有一个随机系统，你真正应该做的是比较你的模型的转移分布和数据的转移分布。所以，一个合适的损失应该是……我没有时间详细介绍。
>> 有些人也这样做，我不是直接学习一个原始模型来预测下一个状态，而是学习一个表示，将原始观测映射到一个更紧凑的低维状态空间，并在那里学习一个潜在的动态 G。希望这能解决一些问题。但实际上，不清楚正确的损失是什么。许多人会考虑使用损失，比如说，哦，让我们只使用潜在层面的预测损失，忽略那里的随机性问题。但即使在这里，这个损失实际上也是退化的，并且有问题，因为你不再有一个不可操纵的真实值，因为你正在联合选择 $\phi$ 和 $G$。无论你为 $\phi$ 选择什么，这个压缩也会改变潜在层面的 $S'$ 的标签 $\phi$。正如你所想象的，我可以选择一个 $\phi$，它丢弃了原始状态中的所有信息，给你一个非常容易的潜在层面的预测任务。所以，关于 MDP 和随机过程的模拟理论，有很多有趣的问题。我们有一些最近的工作解决了这些问题。
>> 还有一个最后的幻灯片，讨论了如果你真的必须在模拟器或动态模型上进行模型选择怎么办。我的建议是，至少如果你的目标是策略评估，将其简化为基于价值的情况。因为，你知道，在基于价值的情况下，我们关注的概念是贝尔曼误差。但事实证明，贝尔曼误差也秘密地是一个基于模型损失。它实际上可以写成候选近似动态和真实动态之间的 IPM。而真正好的地方是，即使你有高维状态空间，这个 IPM 实际上会投影到一个单一维度，一个标量值。这是与你的最终任务最相关的，如果你的任务是，比如说，策略评估，预测策略的性能。
>> 好了，时间有限，有一些有趣的未来方向，我很乐意在会后讨论。否则，谢谢大家。