Yuandong：强化学习新方向研讨会。上次我试图用这台笔记本电脑进行演示时，发生了一些滑稽的事情。但让我们看看，希望这次能顺利一些。好的，我有三个想要讨论的话题，显然我无法充分涵盖这些话题中的任何一个。但我只是想反思一下研讨会的标题——“强化学习的新方向”。对于一个在这里待了不知多少年的人来说，什么是新的呢？因此，我将介绍一些对我来说比较新颖、且在领域内可能尚未得到充分探索的内容。任何时候如果你们有任何问题，请举手。我会尽量回应你们，如果有需要澄清的问题，我们可以进行 clarification。
好的，让我们开始吧。我将讨论好奇心、答案词（answer words）以及在强化学习中的函数逼近。我是说，当你做神经网络时，要么你深入研究神经网络，要么你是神经网络的用户。如果你是用户，那么你通常停留在高层级，只需将它们视为为你进行函数逼近的强大工具即可。然后你可以问一个问题：你是如何做到这一点的？这就是第三部分的内容。好的，关于好奇心。那是杀死猫的东西（好奇害死猫）。但我实际上拍了一张照片，只是没时间上传。所以没人需要被说服去相信好奇心的重要性及其对任何智能代理的重要程度。但它是什么样的？你如何形式化好奇心？如何在理论框架中研究好奇心？
在第一部分，我选择讨论 Peter Auer 和 Lim Ching Koon（Lim）的一篇旧论文。起初，Peter Dayan 也是团队的一员，他们试图形式化某种好奇心概念，并得出了关于它的一些非常有趣的结果。最近，我们重新审视了这一点并对其进行了改进（spice it up），因为世界不是静止的。我们要问的问题是：当世界在你脚下发生变化时，你如何保持你的好奇心？好的，这就是第一部分。那么我们如何对好奇心进行建模呢？显然，我们需要一个控制过程。你必须与世界互动，并运行好奇心的实验，对吧？并且你想要获取知识。我们喜欢保持随机性，因为这会让事情变得更有趣，甚至可能更真实。
如果世界是随机的，那肯定会更有趣。现在引入一些非常强的简化假设。我将假定状态空间是一个受控马尔可夫过程。到目前为止还不错。你有动作，有状态转移。状态空间将是可数无限的。对。你可能会说，这真的很局限。但好吧，你必须从某处开始，至少它可以是无限的，对吧？这就是你的起点。另一个连接演讲第二部分的重大简化假设是你观察到状态，对吗？所以你迈出一步。你选择一个动作，进行转移，看到一个状态，并观察到下一个状态。控制理论人员会对此立即感到反感（throw up），但你知道在人工智能中，你们拥有非常好的传感器，因此至少可以暂时将其轻描淡写地忽略过去。这就是我们要做的，这里还有一个更大的简化假设。
这只是为了说有一个母亲照顾你，对吗？所以你可以重置到初始状态，对吧？如果你在了解一个环境，它可能有陷阱，你可能会死掉，这真的很糟糕。或者也许你只是在树林里迷路了，对吗？所以理想情况下，你想要哭喊找妈妈，然后妈妈把你带回家，像放在床上一样安置好你，这样你就可以在第二天继续学习。所以这就是重置。我将假定我们将拥有重置功能。这实际上是启动所必需的。好的，那么目标是什么？因此，你可以将生活在这个受控马尔可夫过程中的好奇代理的目标形式化为发现可达状态集的目标。如果它工作良好，它应该尽可能快地完成这一发现过程。
好的，作为一个性能指标，这有点复杂。在高层级上，你想要最大化每时间步可靠可达的状态数量。但即使要谈论这一点，我们也必须经过一些类似精细推理的过程。我无法向你传达为什么你必须以这种方式具体定义事物，但有一些反例表明更简单的定义根本行不通。好的，我们该怎么做呢？所以在状态上固定一个任意的偏序关系。学习者可能不知道这一点，并固定 L（L 是视界）。你想要发现平均在 L 步内可达的状态集。这是一个期望值，然后你根据偏序关系增量定义在 s 步内可达的状态集。重置状态在这个集合中，然后如果你能找到一种策略，在平均 s 步内到达另一个状态，且该策略保持在已定义的集合内的状态下。
你使用偏序关系来限制处于该集合中的状态集，那么那个状态也在这个集合中。好的，所以这个偏序关系就像某种枚举一样。它在状态之间给你一个顺序。然后可达状态集对偏序关系不敏感。所以你取所有可能的偏序关系，并说在 n 步内的可达状态集是所有可能偏序关系的并集。你可以证明我所说的简单定义行不通，并且你还可以证明实际上存在一个偏序关系，使得可达状态集就是相对于该偏序关系的可达状态集。好的，所以在某种程度上，学习者需要弄清楚它应该访问状态的顺序并保持安全。
幸运的是，因为我们在无限空间中，嗯，你也可以证明这是有限的。所以你有机会在有限时间内发现所有这样定义的可达状态。好的，非常简要地说，Argatum 算法只是上置信界（UCB）算法的一种变体。它的工作方式有点像广度优先搜索，但它是经过改进或加强的版本。该算法有一组已知状态，然后它还知道边缘状态（fringe states）。所以这些就是边缘状态。让我们看看
是否如此？哎呀，这没起作用。好吧，这些是边缘状态（fringe states）。算法也包含这些边缘状态，当它发现可以可靠地从初始状态到达新状态时，它就会前往那里并尝试每种动作大约 L 次以发现新状态。这些就是被发现的新状态。当它尝试这些动作时，经常会回到原点，对吧？因此它不会添加任何新动作。接着它就拥有了新的边缘状态。
它会考虑所有这些边缘状态，就像对它们持乐观态度一样思考：鉴于对这个世界的所有不确定性以及我所有的知识，这些状态中哪一个看起来最接近初始状态？这就是乐观路径。你在其中考虑不确定性并选择该路径，这是算法的提议阶段。一旦选定目标，你就尝试验证你的提议是否正确。
你根据所提出的策略前往该状态（基于你的知识），看看能否到达那里。好吧，你在中间有些许移动，并尝试若干次试验。如果足够多的试验成功，并在合理时间内频繁到达该状态，那么这就成为了已知状态，过程继续。当你发现没有更多已知状态时停止。
关于该算法我们知道什么？基本上，它必须稍微超出可行状态的集合，因为它无法真正区分。没有任何算法能区分“1+ε 倍 L 个可达状态”和“L 个可达状态”。它必须稍微超出一点。对于每个这样的状态，它将花费一定的时间。
但发现这些状态所花费的时间将与集合的大小成线性比例（直到对数因子），即与待发现集合的大小成正比。而对于每个状态，它将花费一些时间。不幸的是，这在所有误差项上是三次方的。好吧，这是 ε 近似因子。所以如果你担心这一点，向算法输入时，你可以引入某种加倍技巧和联合界（union bounds），然后算法就可以继续运行。
这就是真正的持续学习，它只是不断尝试扩展可达状态集合，并以合理的方式进行。我真的很喜欢这项工作。一个显而易见的问题是这些界限在任何意义上是否都是最优的，比如你能改善这种三次方依赖关系吗？这似乎有点苛刻。这是一个问题。
现在谈谈非平稳环境（non-stationary worlds），对吧？风在变，世界在变，代理的视角有限。因此，即使代理生活在一个平稳的世界中，这个世界也可能表现为非平稳的。所以思考非平稳世界非常有价值。特别是你与任何运行强化学习算法或控制算法的实践者交谈时，他们会倾向于抱怨如果你的学习率趋于零。
他们会说：“啊不，现在的学习率不能为零。”因为世界会在你脚下发生变化，对吧？所以你必须准备好应对变化。总会有你没看到的部分在变化。那么如果世界发生变化，好奇心会怎样？简单的问题：我们如何对此建模？
如果我们问的问题是：代理有它的生命周期，它度过一生，而世界在代理脚下突然变化了 f 次。因此转移概率核改变了 f 次。代理不知道何时发生变化以及转移概率核如何变化。也许它以无关紧要的方式改变，或者从代理技能的角度来看以绝对相关的方式改变（即到达可达状态集合的技能）。
我知道代理必须继续下去，这有点像一个关于代理需要多少时间的问题。比如代理首先应如何发现变化？以及代理将在这个“悲惨状态”中停留多久，即不知道变化已经发生，所以他们认为自己很有技能但实际上并非如此？这就是我们要最小化的指标。
你可能会想：好吧，如果找到所有合格状态需要 W 的工作量，那么如果有 f 次变化，代理不知道该做什么、没有技能的时间步数应该与变化的数量不成比例。所以理想情况下你要瞄准这一点。剧透预警：我们达不到那个目标，但正在接近。好吧，这只是想说算法要么胜任，要么不胜任。你想最小化不胜任的步骤数。
那么我们该怎么做呢？我们会面临一些困难。我们要复用之前的算法，所以你取用前一个算法并开始构建可达状态集合。在这样做时，事情可能会在它脚下发生变化。但为了简单起见，假设这没有发生。然后之后事物可以改变。
一旦构建阶段结束，代理仍然必须去检查是否有新的可达状态出现，或者哪些原本可达的状态不再可达。所以它必须继续并不断进行实验。这就是检查阶段，代理将执行此操作。为了在检查阶段查看是否出现新状态，它基本上必须重复构建过程，对吧？
就像尝试发现新的可达状态。如果这花费太多时间，那么好吧，它就知道环境发生了变化，然后一个新的阶段或新的回合开始。构建有什么问题？算法根本无法知道其正在构建的内容是否正确。因为它正忙于做某事，而环境的其他地方发生了变化。它如何知道？
我们提出的解决方案有点简单化，就像每个人都会想到的那样：你启动许多并行的、错开的进程。比如你稍后开始一些构建过程，并希望其中一个能完成。一旦那个完成了，你就进入检查阶段。好吧，这就是你所做的。仅此而已。
尝试调整调度器，因为生命只有一次，所以必须模拟并行执行这些操作。这就是算法，得到的结果大致如下：如果环境变化为 f，通常工作量是 w。遗憾的是我们无法获得 fw 的界限，但得到了 fw² 的界限，这源于交错模拟过程。因此存在这些开放性问题：二次依赖是否必要？在静态环境中构建的成本是否为最佳可能？当然，你可以思考如何将所有这些扩展到非表格环境。好的，DAM 是第一部分，有点慢。有问题吗？我会参加整个研讨会，所以在休息期间如果有评论或问题请找我。
第二部分，我之前提到假设状态可观测有点奇怪。任何控制领域的人都会立即反应说这太荒谬了，不能这样做。但好吧，我们仍然这么做。然而我们也假设强化学习中奖励是可观测的，如果仔细想想这甚至更荒谬。因为有很多过程你可以推断出奖励但无法直接观测到它，比如你知道奖励大于五或小于四，但你不知道确切值。这不是噪声问题，只是你对情况的信息有限，存在潜在变量。
那么当奖励不可观测时会发生什么？显然这对规划有影响，在部分可观察马尔可夫决策过程（POMDP）设置中规划会变得非常困难。这也对学习有影响，即使对于学习你也可能需要采取仅收集关于情况信息的行动。如果环境中有一些潜在信息，你想去调查，比如在进一步采取行动前打开冰箱看看里面是什么。
我喜欢将一切简化为基本要素，这也是我研究多臂老虎机的原因。动态规划非常复杂，如果你想研究探索也许可以从老虎机开始。如果在一个奖励不可观测的 POMDP 中假设状态是独立同分布过程，你就得到了所谓的部分监控问题。这是本部分的主题，这里有一个例子来说明：也许是在轮次中进行，或者使用图形模型。
智能体可以选择展示网页，用户访问网站拥有复杂的个性兴趣而我们知之甚少。假设你想最大化智能体的幸福，如何在了解如此少的情况下实现？也许有时你可以采取一些行动来告诉你用户的内部状态信息，从而弄清楚什么能让用户开心。你必须采取明确行动来确定用户喜欢什么，但糟糕的是我们并不直接观察用户的快乐，只观察其行为如点击。
可以形式化这个问题：环境选择 x，智能体行动 a，存在观测值和未观测损失。以序列方式进行，学习者获得损失映射和观察映射两个函数。环境选择结果，学习者行动并遭受隐藏的损失，同时观察到观测值。在这种情况下学习者应该做什么？首先问题是学习者的目标是什么？
假设学习者试图最小化遗憾，这很好因为不需要对环境做独立同分布等假设。你可以研究最坏情况，这种框架很简洁且有很多例子符合它。对于这类游戏的主要结果是分类结果，这是多年研究的成果。该结果表明如果取有限部分监控博弈（有限结果和动作），关于最小最大遗憾的缩放有四种可能性。
可以用很好的几何方式描述，游戏结构在单纯形上产生了几何性质，据此可以描述游戏属于哪一类。人们花了很多时间研究其中两种情况：这两种显然是 trivial 的困难或简单游戏，不太有趣。有趣的是像老虎机那样遗憾随根号 n 缩放的游戏，以及最难设计好算法的情况。
目前为止需要注意的第一件事是经典针对老虎机的算法行不通，如许多目标方法不关心信息只关心损失。乐观估计、汤普森采样或指数加权都不适用，还有一些更复杂的算法如解决马尔可夫链不动点等很难实现。我要讲的是一个新的存档结果，与 Stolte 合作的新算法简单、在所有情况下有效且具有竞争力。
专门针对特定情况，如老虎机问题。在实际性能方面，它在我们要检查的所有情况下都获得了最好的界限。因此，该算法非常直观。我们仍然依赖指数加权法。大家可能都知道指数加权：你估计损失，一旦有了损失估算值，你就对它们进行指数运算，然后标准化后创建一个概率分布。通常在这里我们只是匆忙地尝试从该分布中进行采样。但这里我们要做一些不同的事情。我说，好吧，让我们不要这么匆忙。我们要提出另一个分布，因为我们也关心信息量。
因此，在这个其他分布中，我们可能会偏离指数基础分布，正因如此，我们要承受损失。这就是我们要承受的代价。所以我们在思考如何选择这个分布 p。我们愿意为获得信息而付出代价。那么如何量化信息呢？人们有很多想法。我们认为最好的方法是查看可以推导出的遗憾界限，从这些界限中可以看出存在一个惩罚项。
这是由于分析 resulting 算法所产生的信息而带来的，因此将其包含在优化问题中。熟悉指数加权分析的人对这个项很熟悉。这是你总是难以保持有界的那个项。所以他会说，好吧，让我们解决这个优化问题：我们针对该分布进行优化，同时由于估算奖励的方式多种多样，我们也必须对此进行优化。
这就像是对函数 chi 的一个线性约束。因此这是一个具有线性约束的问题，而你试图最小化它。如果你想的话，这是一个鞍点问题，但它是凸优化问题。所以你解决这个方程组，然后简单地从分布 pt 中进行采样。之后，你根据来自优化问题的估计器更新你的损失估算值。
其思想是联合优化估计器和分布，并关注遗憾界限。这确实奏效了。这是一个单一算法，适用于所有这些情况，并获得最佳的遗憾界限。我不会用实验细节来烦扰你们，但我们很高兴该算法在实际中是一个好算法，它击败了 EXP3。这可能不是什么大事，但这是一个通用算法，所以还不错，而且看起来它在做正确的事情。
在这些实验中，仅为了电池续航的好处（注：此处原文可能有误或为俚语），嗯……好吧，细节太多了。你可以问我。是的，问题是这个算法是否变成像 EXP3 那样的算法？不，它的玩法与 EXP3 不同。McMahon, Brandon McMahon 在不同的背景下也有类似的想法。但这不一样，是的。不过证明过程是相同的：基本上你说优化问题包含了 EXP3 会做出的选择。因此我们有了遗憾界限，不需要太费力地工作。
是的，好吧。更多实验显示我们始终处于蓝色状态（注：可能指图表中的曲线），Solar 更好，它总是非常好。总之，结论是。部分监控比你知道的老虎机问题或其他版本要雄心勃勃得多。所以我从中学到，有时候雄心壮志并不坏。这是一把双刃剑。提出这个算法花了很长时间。但我认为这是一个非常好的算法，我们需要更多实验。
优化问题是个巨兽。所以我们正在努力使这个优化问题变得友好。它倾向于破坏所有的求解器。其性质是，在非常接近最优解的地方，有些方向表面非常平坦，而其他方向则极其弯曲且导数非常高。因此，如果你没有一个出色的自适应求解器，它很容易就会崩溃。但我们设法找到了一些可以解决它的求解器。
当结果空间更大、无限时会发生什么？你能将其推广到其他情况吗？我认为这里有一些探索的空间。好吧，最后一部分。我不知道。关于这部分有什么任何问题吗？在继续之前。是的，是的，是的。它是相对于……定义的。对，是的。问题是：在最后一种情况下，你没有观察到损失或奖励，遗憾是如何定义的呢？
遗憾仍然是相对于损失定义的。学习者获得了所有可能结果的损失函数。它没有看到的是环境选择的结果，因此它可以基于观察到的信息推断出原本会发生的损失。这就是为什么……但遗憾的定义是相同的。在那里，好吧，我们可以离线处理它。关于这一点还有更多话要说，但为了节省时间，我就继续了。好的，很好。
最后一部分关于强化学习中那些对函数逼近友好的算法的探索。我已经在这个主题上工作相当长一段时间了。为什么你需要这个？显然，世界非常巨大且复杂，你需要进行近似处理。坏消息是，我们的算法往往对如何进行近似非常敏感。
你可以用许多不同的方式进行近似。我将介绍三种不同的方法，然后我们可以讨论它们的优缺点。一般来说，我们感兴趣的是什么？通常你会建立一个简化环境某些方面的模型，这会导致策略中出现一些误差，你的策略将不如最优策略那么好。因此，你想要界定你策略的这种次优差距作为你所使用模型质量的函数。
这方面已经有很多工作了。好的，所以有三个不同的结果。首先，我将讨论一个框架：自适应线性规划、近似动态编程（我们应该使其具有适应性）。以及一些那里的结果。然后是因子线性模型，最后是免模型强化学习。好的，近似线性规划：你可能知道 MDP 问题在折扣设置和无折扣设置的许多情况下都可以重写为线性规划。
很早以前，人们就说：“嘿，这个线性规划的变量太多了（状态的数量），约束也太多（状态动作对的数量）。所以为什么……”
我们是否引入了一些近似？例如，变量数量等于状态数，这编码了价值函数。那么，我们为什么不认为这些可以用 k 个参数而不是与状态数成正比的参数来编码呢？这样它们就生活在一个线性子空间中。因此，你可以进行这种子空间缩减。这就导致了这样一个结果：你拥有这个 phi，它是一个矩阵；R 是一个向量；这是一个低维量。因此，这将它扩展为一个高维量，然后你最小化这个值。C 只是一个归一化的向量，使其总和为一。任何向量都可以选择。Alpha 是折扣因子。G(a) 是底层的奖励向量；对于每个状态，它是一个高维量。维度是每个动作的状态。它是奖励向量。这是下一个状态的分布；它是马尔可夫转移核。
因此，这种形式应该是熟悉的，除了这里通常对所有动作都有所有这些约束。所以没有这个求和。所以我只是加上这个求和，因为，嗯，我们喜欢线性关系，对吧？所以我们要投影约束。因此，如果你进入对偶空间，这有点像说，哦，也许你正在做一些近似，针对的是对偶变量，在这种情况下是占用度量。但无论如何，w 是非负值的。也许你可以归一化它们，因为你没有失去任何东西。然后你问的问题：好吧，这样做的收益是什么？你重用了约束的数量，对吧？这是一种投影。我知道你的约束少得多。
以前人们采样等等。这有点像平滑版的史密斯采样（Smith sampling）。因此，你可以问这个问题：好吧，如果我解决这个问题，解的质量如何？关于这个问题的解与最优价值函数的质量之间的关系，我能说什么呢？你可以得到这个结果。假设如下：所以如果你读出这个问题的解，这是该优化问题的解，并将其扩展到大的空间，你有一个近似的价值函数，而你关心它与真实价值函数的偏差有多大。你在生成模型中，所以仅知道这个差异，加上做一些模拟可能允许你接近最优地行动，如果这个界限很小，如果那个矩量很小的话。
好吧，所以进一步的计算将允许你很好地行动。好的，所以我们希望保持这个量很小。在这个定理中，你会看到，这是与 Chandru 和 Shahab 的联合工作。你可以看到这个量随 epsilon 缩放。这是你选择的子空间中接近最优价值函数的最佳近似，然后发生了一些膨胀（blow up）。我认为你可以争辩说这种膨胀是无法避免的。并且有一些额外的项。因此，AIP 的经典结果只有第一项而没有第二项。经典结果不压缩约束。所以压缩约束的代价是这一第二项。如果你过度压缩约束，你可能会到达一个可行区域为空的问题，从而一无所获。这就是问题所在。当然，你必须小心。
然后有一些想法关于如何避免这种情况。第一个想法是，嗯，只看这些量。那么这些量是什么？所以这些量是两个生活在一个高维空间中的价值函数。第一个是使用你的基对最优价值函数的最小上界近似。第二个是类似的，但给定约束条件。这也考虑了约束。因此，这两者之间的差异就是进行这种压缩的额外代价。好吧，所以你可能认为，嗯，这也许是可接受的。考虑这个上界近似有点奇怪。那么，我们可以做点别的吗？好吧，所以是的，也许你可以。
事实上，如果你回到文献中，回顾 Whitt 的工作，我认为他是第一个考虑这样一个问题的人：嘿，我想在一个 MDP（马尔可夫决策过程）中行动，我有另一个 MDP。我在那个 MDP 中寻找最优策略，而我在原始 MDP 中表现如何？对吧？那么，策略误差是多少呢？所以他基本上提出了这样一个结果：告诉你误差由这些转移核的差异界定（它们也隐藏了动作，所以它们是更高维的），以及近似模型的价值函数。因此，差异不必处处很小。但不方便与否，它必须在你将要计算的价值函数处很小。
现在，如果你对那一无所知，也许你知道它有界，你可以得到一个结果。这仅仅表明如果这些在 L1 中闭合（closed in L one），那么你可以得到 L无穷大界限，然后其他不等式告诉你：好的，转移核的 L1 闭合性足以获得良好的策略误差。问题是，你能比这做得更好吗？我想说：是的，这很棒，但也许通过假设额外的结构，你可以做得更好。
所以我真的很喜欢的一个模型，而且似乎当前不同背景下的文献也在采纳它。在这里我只是思考基于智能体的情况（agent-based）。所以有人给你这个近似模型，你解决它，读出策略。你会表现如何？所以我真的很喜欢的一类模型是这些因子线性模型（factor linear models）。在这些因子线性模型中，有很多我无法解释的东西，但要点是转移核具有因式分解的形式。这样你就有一个内核走向低维空间（这就像一个分析内核进入低维空间），然后有另一个内核扩展回高维空间。
那么，你怀疑如果这种因式分解是好的，那么至少基于之前的结果，你应该能得到一个好的结果。那好在哪里呢？如果你这样做，你可以在低维空间中完成所有计算（有时），所以你的复杂度将与你投影到的空间的维度成比例，比如这里的 R^D。有很多特殊情况，这是人们之前考虑的许多模型的特例。这很巧妙。好吧，那么在这种情况下我们可以得到什么结果呢？有点复杂。所以这是关于策略的误差，即偏离多少
策略的损失与最优策略所能获得的收益相比，由两项界定。这两项中的一项均值值得注意，你可以选择这两个量中最小的一个。第二个量仅仅是V的结果。好的，所以这也是一样的。U*本质上是压缩模型的最优值函数的不动点，也就是近似模型的。这就是它的结果。你也可以用这个其他量取均值，但在另一个量中，你可以代入最优值函数。你的模型只需在最优值函数以及你读取出的策略的值函数处准确即可。所以这里有两个量，真正值得注意的是：1/(1-γ)因子不适用于此。
这是一个高维量，其范数希望保持较小，且不被1-γ除，这非常巧妙。我们不喜欢除以(1-γ)，因为它在问题视界增长时显示出爆炸趋势，这很不方便。而在这里你有另一个项，但在该其他项中，你在计算误差前将其投影到低维空间。所以这是一个不错的结果。好的，当然，哎呀。有人问：这个界限是否紧致？这主要讨论的是状态抽象的因子分解。但你希望无缝地进行时间和动作抽象，并将类似的方法应用于这种情况。我不知道该怎么做。
如何高效地学习呢？这种因子分解在例如考虑核均值嵌入时非常自然地出现。问题在于，如果你有n个数据点，那么所有算法都将随n的立方缩放。你可以尝试将其应用于投影和其他技术。我们尝试过的方法效果并不好。所以，这是一个如何在至少非参数世界中使其实用的问题。好的，最后一部分只有一分钟，零秒，好吧，我们开始晚了，对吧？是的。好的，最后一部分是关于在线学习的新方向。它是无模型的，动机来自与DeepMind同事的交谈。
看起来，虽然我们也做一点基于模型的方法，但目前我们在使用基于模型的算法方面远不如无模型算法成功。这是一个好问题：为什么？但既然我们在无模型算法上更成功，且人们喜爱它们，那我们为什么不使它们更高效呢？这里的问题是：如何为强化学习设计无模型算法，使得在使用神经网络等背景函数逼近来近似值函数时，你能给出合理的理论保证？这就是无模型强化学习。
就像你直接去估计值函数并尝试改变策略，并以一种巧妙的方式进行，以便将一切控制在手中。所以这是在线设置。如果是在线设置，那么你关心的是遗憾值（regret）。即与从一开始就采取最优行动或根据你关心的某个固定参考策略行动的相比，你损失了多少。那就是π*。还有一个称为伪遗憾（pseudo regret）的量，它仅比较在时间步t执行的政策π(t)的平均性能增益与最优政策的平均增益。
伪遗憾与实际遗憾之间的差异，如果你有混合马尔可夫决策过程（MDPs）或其他情况是可以界定的。就像我刚才说的，我不在乎那些细节，我认为伪遗憾足以进行控制。它实际上告诉你有多熟练。好的，所以我们要控制伪遗憾，有一个美丽的公式给出了伪遗憾的等式。你只需看这个公式并说：“啊。”埃拉德，你会怎么说？这只是在线学习，对吧？好的。
对于这里的每一个状态，你都有这个线性表达式，对吧？所以你想保持这种遗憾较小。这就是你所选择的分布，它与这个损失（或者奖励，我忘了，我想是奖励）取内积。不，它是损失，对吧？所以我们处于损失框架中，因为π*是第二好的选择。Q函数用于成本，因此你必须将其与事后最佳选择或任何固定参考分布进行比较。对于每个状态，你都必须控制这些量。
我的意思是，你最好控制它们，只要控制它们是足够的。如果你为每个状态都控制了它们，那么你就会做得很好。这看起来就像是线性在线学习或在线线性优化，对吧？这个表达式是线性的，分布也是线性的，这些损失函数很复杂。我们不知道它们，对吧？但这就是酷的地方：之后你做一些事情，也许你会学到关于它们的某些知识，然后你可以控制它们。
因为对于你的策略，你从未见过动作值函数。是的，这是一个恒等式。所以我没有选择它，我只是喜欢它。当然，这个表达式是对称的。你可以把π(t)放在这里，但这会太复杂且对我想说的没有帮助。这是一个恒等式，就像你可以证明它只是平衡方程一样。经过几步代数运算就能得到这个结果，我们可以讨论一下。是的，这很酷。
它称为性能差异引理（performance difference lemma），给出了这个结果。是的，虽然不太直观，但事实如此。好的，Q_t不可访问，但学习者将估计Q_t。Q_t是策略的动作值函数，因此你可以写出另一个恒等式，将这个差异分解为这三个不同的项。这两个家伙引入后相互抵消。你可以使用在线线性优化（OLO）来控制第一个量。
只要你保持这些项有界并调整步长，虽然那里有些棘手之处，但你可以使用在线学习工具将其控制在手中。我们将假设你有强大的函数逼近器，所以函数逼近器可以控制其他两项，对吧？它们只是近似误差，比如Q_t与真实值的接近程度。我想说，如果你收集更多数据，它会更接近，这取决于你的函数逼近器。好的，这里有一些细节。
我虽然隐藏了，但就像跳到了下一步。那么由此产生的算法是什么呢？在线优化中最简单的算法是指数权重法。你代入指数权重，瞧，你就得到了这种策略迭代版本。在策略迭代中，你只需这样做，我们称之为 Polytag。带有专家建议的策略迭代，或者其他的指数权重法……我忘了。然后你可以选择熵正则化，或者说这种指数运算。这也类似于泊松平均，对此可以直观地理解：也许这样做允许你运行更短的阶段，因为发生了一些方差缩减。
无论如何，如果你这么做，你就能得到一个元结果，表明如果你在每次迭代中都能控制函数逼近误差（通常是参数化速率），那么你可以读出整体的遗憾率，它将是 T 的负四分之三次方。这是第一步的平均遗憾。有点慢，不太喜欢它。但好处是，如果下界 epsilon 为零，那么它就出现在遗憾中，这是不可避免的，但这已经是你所能做到的最好结果了。
不过这里有一些问题。我们真的能做到这一点吗？一个好的测试方法是研究线性值函数逼近。事实证明，这已经表明误差可能会爆炸，因此试图求解不动点方程的函数逼近器的误差可能远大于在线性子空间中能获得的最小可能误差。这是开放性问题一：你能做得比这更好吗？也许不能。
你可以对此进行细化。问题的一个方面是，隐含地隐藏了你实际上是在无限期地探索所有动作。如果这种情况没有发生，那么你最好将状态值函数与动作值函数分开。增加对动作的探索，然后你可以细化结果。在这里，你只需要假设所有策略都能激发特征，即底层的数据格拉姆矩阵的特征值在所有你将遇到的策略中一致地远离零。这仍然是一个相当强的结果，所以我们可以细化它吗？是的，你可以。
如果你回到好奇心方面，那里有一个策略只是在探索空间。所以如果有人给你一个执行此操作的策略……好吧，它不必探索整个空间，但它必须探索特征空间。然后你可以使用该策略来激发所有特征以离开执行。复杂性在于，现在你处于离策（off-policy）体制中。你必须使用离策学习。对于控制函数逼近误差的离策学习，我们并没有很好的结果。
你可以对事物进行调整并仍然获得遗憾界限，但这并不完美，也不像是一个完成的产品。所以有很多显而易见的问题：我们能用其他在线学习方法做得更好吗？平均化真的是必要的吗？我们要如何设计更好的值函数学习者？好了，因为人们想要休息……我不知道。有咖啡吗？没有咖啡，休息一下吧，人们想休息一下。好吧，我们讨论了好奇心、通过优化的探索以及其他的泛化问题。你可以看到很多活动正在进行中，这是一个令人兴奋的时代。谢谢。