强化学习新方向与演讲框架

本次研讨会聚焦于强化学习（Reinforcement Learning）的新兴研究方向。尽管演讲者在该领域已深耕多年，但他仍试图挖掘那些相对新颖且未被充分探索的议题。演讲主要涵盖三个核心主题：好奇心（Curiosity）、答案词（Answer Words）以及强化学习中的函数逼近（Functional Approximation）。对于神经网络用户而言，通常将其视为强大的工具进行高层抽象；而对于研究者，则需深入其内部机制。演讲者强调，由于世界并非静止不变，传统的理论框架需要更新以应对动态环境下的挑战。他邀请听众随时提问，以便在出现理解偏差时及时澄清问题，确保对复杂概念的准确传达。

好奇心理论的形式化重构：从静态到动态环境

第一部分深入探讨了好奇心的形式化建模。演讲者回顾了Peter Auer、Lim Ching Koon以及早期参与者Peter Dayan的经典论文，该研究试图在理论框架内量化好奇心。然而，原始模型假设世界是静止的，这与现实不符。“The world is not stationary... how do you keep your curiosity up when the world is changing underneath you?” 为了适应这一现实，团队重新审视并增强了该理论。核心假设包括：环境是一个受控马尔可夫过程（Controlled Markov Process），状态空间为可数无限集。虽然控制论专家可能反对这种简化（如假设完全观测状态），但在AI领域，良好的传感器数据使得这一假设有其合理性。此外，引入重置机制（Reset）至关重要：当智能体陷入陷阱或迷失时，可以回到初始状态继续学习。这种机制确保了探索过程的安全性与可持续性。

可达状态集的定义与发现算法

好奇心的目标被形式化为快速发现所有可到达的状态集合。为了量化这一性能，演讲者引入了复杂的数学定义：在任意给定的偏序关系（Partial Ordering）和 horizon $L$ 下，增量定义可达状态集。初始重置状态属于该集合；若存在策略能在平均 $s$ 步内到达新状态，且中间过程保持在已定义集合内（依据偏序限制），则该新状态也被纳入。最终，可达状态集是所有可能偏序关系下集合的并集。这种定义方式避免了简单定义的缺陷，证明了在无限状态空间中，总存在一种偏序使得可达集是有限的。这意味着智能体有希望在有限时间内发现所有可到达状态。为此，演讲者提出了基于上置信界（Upper Confidence Bound, UCB）的算法变体，其运作方式类似于广度优先搜索（BFS），但通过维护已知状态集和边缘状态集（Fringe States）来优化探索效率。

算法的探索与验证机制

该强化学习算法的核心在于对“边缘状态”（fringe states）的处理与扩展。当智能体发现从初始状态 $s_0$ 能够可靠地到达一个新状态时，它会尝试执行多种动作（约 $L$ 次），以探索并发现更多的新状态。然而，许多尝试往往会导致智能体回到原有路径，并未产生新的动作或边缘状态。在确定了所有当前的边缘状态后，算法采取乐观策略（optimistic approach）来应对世界的不确定性。它会基于现有知识，评估哪些边缘状态最接近初始状态或最具可达性，从而选择一条乐观路径。这一过程构成了算法的“提议阶段”（proposal phase）。

在选定目标状态后，进入关键的验证阶段。智能体必须依据提议的策略执行多次试验，以确认该状态是否真的可达。如果在合理的时间范围内，足够多的尝试能够成功到达目标状态，则该状态被标记为“已知状态”，算法继续扩展。这个过程持续进行，直到发现没有更多的已知状态可以扩展为止。这种机制确保了智能体在探索过程中既能利用现有知识，又能通过实证验证新发现的可信度。

复杂度分析与持续学习特性

关于该算法的性能，存在几个重要的理论界限。首先，由于任何算法都无法在数学上严格区分 $L$ 个可达状态与 $(1+\epsilon)L$ 个可达状态，因此算法必须略微高估（overshoot）可行状态的集合。在时间复杂度方面，发现这些状态所需的时间与待发现的状态集大小成线性比例关系（直至对数因子）。然而，对于每个状态的探索时间，原文指出其复杂度为关于 $\alpha$ 的立方（cubic in all o rapsum），这是一个较为严苛的性能瓶颈。

针对这一立方依赖性问题，如果担心算法效率，可以引入倍增技巧（doubling trick）和联合界（union bounds）来优化。这种机制使得算法能够进行真正的持续学习（continual learning），即不断尝试扩展可达状态集，并以一种合理的方式运行下去。尽管存在立方复杂度的缺点，但这种通过并行和边界处理来维持长期探索的能力，是该算法在动态环境中保持鲁棒性的关键所在。

非平稳环境下的挑战与建模

现实世界中的强化学习面临非平稳性（non-stationary）的巨大挑战。即使物理环境本身是静止的，由于智能体的视角有限或世界本身的细微变化，对智能体而言环境可能表现为非平稳的。从业者普遍反对将学习率设为零（learning rate goes to zero），因为世界随时可能在脚下发生变化。因此，研究的核心问题转变为：当环境发生突变时，好奇心机制和探索策略该如何适应？

“如果问题是我们问的是：智能体有它的生命周期，而世界在智能体脚下突然改变了 f 次。”

为了量化这种变化带来的影响，研究者构建了一个模型：假设环境在智能体不知情的情况下发生了 $f$ 次突变，导致转移概率核（transition probability kernel）发生改变。这些变化可能是无关紧要的，也可能是严重影响智能体技能发挥的关键变化。研究的目标是衡量并最小化“无知状态”（miserable state）的持续时间——即智能体认为自己具备技能，但实际上已失效的时间段。理想情况下，这种无效操作的时间不应与变化次数 $f$ 成正比。

应对变化的并行构建策略

为了在非平稳环境中保持能力，算法需要经历两个主要阶段：构建阶段（building phase）和检查阶段（checking phase）。在构建阶段，智能体建立可达状态集；而在之后，即使环境未变，智能体仍需定期检查是否有新状态出现或旧状态变得不可达。这要求算法具备持续的实验能力。

“要么算法是胜任的，要么是不胜任的。你想要最小化不胜任的步骤数。”

然而，直接复用原有算法面临一个根本难题：智能体在忙碌构建时无法得知环境是否已发生变化，因此无法判断当前正在构建的状态集是否正确。为解决这一困境，研究者提出了一种看似简单但有效的解决方案：启动多个并行且交错（staggered）的构建进程。通过让不同的子过程在不同时间点开始探索，只要其中有一个进程能够顺利完成并进入检查阶段，就能确认当前环境的状态。一旦检测到新状态的出现或旧状态的消失，便触发新一轮的构建周期。这种方法虽然增加了计算开销，但为在动态变化的世界中维持智能体的有效性提供了一种可行的工程路径。

并行模拟算法的性能界限与开放问题

在讨论调度器（scheduler）时，由于智能体仅有一个生命周期，必须通过模拟来并行执行操作。这种交错式模拟过程（staggered simulation process）导致了算法性能的特定界限：如果环境变化量为 $f$，工作量为 $w$，虽然无法获得理想的 $fw$ 界限，但能得到 $f imes w^2$ 的界限。这一结果源于模拟过程中的交错特性，而非更优的理论推导。

针对该算法，目前仍存在几个关键的开放性问题：二次依赖关系（quadratic dependence）是否是必要的？ 以及在平稳环境中构建模型的代价是否已达到最优？此外，如何将这些理论扩展至非表格环境（non-tabular environments）也是重要的研究方向。这部分内容作为 DAM 的第一部分，虽然算法稍显缓慢，但为后续讨论奠定了基础。

从完全可观测到部分可观测：奖励隐式化的挑战

第二部分探讨了强化学习中一个常被忽视但极具破坏性的假设：状态是可观测的。控制领域专家对此往往持反对意见，认为这极不现实。更严重的是，强化学习通常还假设奖励是可观测的（observable rewards），这在许多实际场景中更为离谱。在许多过程中，我们只能对奖励进行推断，而无法直接观测其确切值。

"There are many, many processes where you can make inferences about the reward, but you don't directly observe the reward."

我们可能知道奖励大于 5 或小于 4，但无法得知确切数值。这并非噪声问题，而是信息受限（limited information）导致的潜在变量存在。当奖励不可观测时，规划变得极其困难，特别是在部分可马尔可夫决策过程（POMDP）设定下。学习阶段同样受到影响，智能体可能需要采取专门用于收集信息的行动（如“打开冰箱看看里面有什么”），以推断环境状态，而非直接追求即时奖励最大化。

部分监控问题与几何分类理论

为了简化研究，可以将 POMDP 中状态为独立同分布（IID）的情况抽象为部分监控问题（partial monitoring problem）。以网页推荐为例，用户拥有复杂的内在兴趣状态，智能体只能观察到用户的点击行为（观测值），而无法直接看到用户是否快乐（隐藏损失）。在这种序列决策框架中，学习者通过给定的“损失映射”和“观测映射”，在每一轮中选择动作并承受隐藏的损失，同时获得有限的观测信息。

针对这类有限部分监控博弈（finite partial monitor game），经过多年研究，学界得出了一个重要的分类结果（classification result）。该结果表明，对于具有有限动作和结果的博弈，其最小最大遗憾值（minimax regret）的缩放比例存在 4 种可能性。这种分类可以通过单纯形上的几何结构来描述，从而确定博弈所属的类别。这一理论框架为理解不同信息条件下的学习难度提供了统一的视角。

传统算法的失效与新算法的贡献

在四种分类中，两类 trivially hard（显然困难）和 trivial easy（显然简单）的博弈相对无趣。真正具有挑战性的是那些类似 Bandit 的问题，其遗憾值随 $ ext{sqrt}(n)$ 缩放。然而，传统的 Bandit 算法在此类部分监控问题中完全失效。例如，UCB（Upper Confidence Bound）、Thompson Sampling 或指数加权平均法（Exponential Weights）等算法，要么不关心信息收集，要么仅关注损失值，无法有效处理部分监控中的几何复杂性。

"Neither optimism or Thompson sampling or exponential weights are going to work."

虽然存在一些基于马尔可夫链不动点求解的复杂算法，但它们难以实现且效率低下。最新的研究成果（与 Stolte 合作）提出了一种新的简单算法。该算法能够适用于所有可能的分类情况，并且在性能上与现有的复杂算法相当。这一进展解决了部分监控领域中长期存在的算法设计难题，为在信息受限环境下进行高效探索和利用提供了可行的解决方案。

联合优化分布与估计量以突破指数权重局限

在针对特定案例（如Bandits）的算法设计中，虽然传统的指数权重法 (Exponential Weights) 能带来最佳的性能边界，但直接使用该分布往往忽略了信息获取的重要性。演讲者提出了一种更直观且高效的策略：不再急于从损失估计中直接采样，而是联合优化概率分布与奖励估计量。这种方法承认为了获取更多信息需要付出“损失代价”，因此通过优化问题来平衡这一权衡。

具体而言，算法通过分析遗憾界 (Regret Bounds) 中的惩罚项来量化信息价值。这个通常难以控制的术语被纳入优化目标中，形成一个凸问题 (Convex Problem) 或鞍点问题。我们需要同时优化分布 $p$ 和估计量 $ ilde{ au}$，其中后者受到线性约束。通过求解这个优化问题得到的分布 $p_t$ 被用于实际决策，随后基于该估计量更新损失。这种联合优化机制确保了算法在所有检查过的案例中都能获得最佳的遗憾界。

"So we're thinking about choosing this distribution p. So, we're gonna pay... We're ready to pay if we get information."

实验结果显示，该算法在实际性能上优于 EXP3。虽然这可能看似微不足道，但作为一个通用算法，它展现了正确的行为逻辑。证明过程同样简洁：由于优化问题包含了 EXP3 可能做出的选择，因此自然继承了其遗憾界保证。

部分监控中的优化挑战与无限结果空间探索

在部分监控 (Partial Monitoring) 场景中，学习者无法直接观察到环境选择的结果或奖励/损失。尽管如此，遗憾的定义依然基于损失函数。学习者通过观察到的信息推断潜在损失，从而定义与标准设定相同的遗憾指标。这一领域比单纯的 Bandits 问题更为宏大和雄心勃勃，虽然算法开发耗时漫长，但成果显著。

然而，该优化问题在数值求解上极具挑战性。演讲者指出，这是一个“野兽般”的优化难题。在接近最优解时，目标函数表面在某些方向上极其平坦，而在其他方向则曲率极大、导数极高。这种特性导致大多数自适应求解器容易崩溃。

"The optimization problem is a beast... It tends to break all the solvers. The nature of it is that, like very close to the optimum..."

为了解决这一问题，团队必须寻找能够处理这种极端几何特性的超级自适应求解器 (Superb adaptive solver)。目前，虽然已找到能解决该问题的方法，但在无限结果空间 (Infinite outcome space) 或其他更广泛设置下的泛化能力仍有待探索，这为未来的研究留下了广阔空间。

强化学习中的函数近似友好型算法框架

最后部分转向强化学习 (RL) 中寻求对函数近似友好的算法。由于现实世界极其复杂，必须使用模型简化环境，但这会导致策略次优性。核心目标是将策略的次优差距 (Suboptimality gap) 建模为模型质量的函数，从而对近似误差进行界限控制。

演讲者介绍了三种不同的方法框架： 1. 自适应线性规划 (Adaptive Linear Programming) / 近似动态规划。 2. 因子化线性模型 (Factorized linear models)。 3. **无模型强化学习 (Model-free RL)。

这些方法旨在解决传统算法对近似方式过于敏感的问题。通过构建简化模型，我们期望在保持计算可行性的同时，严格界定因近似带来的性能损失。这一部分为后续讨论不同近似方法的优缺点奠定了基础。

"Obviously the world is huge and it's very complicated, and you need to do approximations. And the bad news is that our algorithms tend to be really sensitive to how you're doing approximations."

线性子空间近似与约束压缩

在强化学习中，为了处理状态空间巨大的问题，我们引入线性子空间的近似方法。传统的值函数编码需要与状态数量成正比的参数，而通过假设这些变量可以仅用 $k$ 个参数编码并生活在线性子空间中，我们可以实现降维（Subspace Reduction）。这种方法将高维量展开后最小化，其中 $ heta$ 是一个矩阵，$ ho$ 是低维向量。具体而言，展开过程涉及归一化的向量 $C$（总和为1）、折扣因子 $eta$、每个状态-动作对的奖励向量 $G(a)$，以及马尔可夫转移核（Next State Distribution）。

"So why don't we just think that, like, ah, those can be encoded with k parameters instead of parameters proportional to the number of states?"

为了保持线性性质，演讲者对约束进行了投影处理。在双空间（Dual Space）中，这相当于对占用度量（Occupancy Measures）进行近似。权重 $w$ 被设定为非负值并可能经过归一化，因为这样做不会丢失任何信息。这种约束压缩的核心优势在于重用了约束数量。通过投影，我们显著减少了需要处理的约束规模，这类似于平滑版的采样方法。然而，这种压缩是有代价的：如果过度压缩约束，可能导致可行域为空（Empty Feasible Region），从而无法得到任何解。因此，必须谨慎处理压缩程度。

近似误差分析与理论界限

求解经过约束压缩的优化问题后，关键问题是评估解的质量。我们将解展开回高维空间得到近似值函数，并关注其与真实值函数的偏差。在生成模型（Generative Model）中，如果这个差异足够小，通过额外的模拟即可实现近最优策略。根据与 Chandru 和 Shahab 的联合研究成果，该偏差量随 $ ilde{ ho}$ 缩放。

"You can see that this quantity scales with epsilon. This is the best approximation to the optimal value function with the subspace that you have chosen, and then there is some blow up happening."

这里的 $ ilde{ ho}$ 代表在所选子空间中最优值函数的最佳近似。理论结果表明，除了这一项外，还存在一个额外的“膨胀”（Blow up）项。经典的结果通常只包含第一项而不压缩约束，因此压缩约束的代价就是这第二项。如果过度压缩导致可行域为空，则一无所获。为了理解这一额外代价，我们需要考察两个高维空间中的值函数：一个是使用基函数的最优值函数的最小上界近似，另一个是考虑约束后的类似近似。这两者之间的差异即为压缩带来的额外价格。

策略误差与因子线性模型

回顾 Whitt 的研究，他探讨了在一个 MDP（马尔可夫决策过程）中求解最优策略后，在原 MDP 中的表现如何。其结论指出：策略误差由转移核的差异界定。虽然差异不必处处很小，但必须在计算出的值函数处足够小。如果假设转移核在 $L_1$ 范数下闭合，则可获得策略误差的界限。

"The error is bonded between the difference of these transition kernels... and the value function for the approximate model."

为了超越这一界限，演讲者引入了因子线性模型（Factor Linear Models）。在该模型中，转移核具有分解形式：一个核映射到低维空间（分析核），另一个从低维扩展回高维。如果这种分解良好，基于前述结果可获得优异表现。其优势在于所有计算可在低维空间（如 $ ilde{R}^D$）中进行，复杂度随投影空间的维度缩放。许多先前考虑的模型均为该框架的特例。

"If you do this, you can do all the computations sometimes in the low dimensional space... And there's a lot of special cases, which are special cases of this."

虽然具体的误差结果较为复杂，但核心思想是利用这种结构化分解来降低计算复杂度并保证策略质量。

策略损失界限与压缩模型的最优值函数

在强化学习中，当前策略相对于最优策略的损失可以通过两个关键项进行界定。这两个项允许我们选择其中较小的一个作为评估基准，从而更精确地衡量性能差距。第二个量直接源于 V*（最优值函数）。这里的 U 本质上是压缩模型或近似模型的固定点，即最优值函数。这一结论表明，我们可以将均值与另一个量结合使用。在另一种情形下，可以代入最优值函数，这意味着模型只需在最优值函数以及所读取策略的值函数处保持准确性*。这种双项界定方式为评估近似模型提供了更灵活的视角，避免了单一指标的局限性。

无折扣因子的高维量与投影误差控制

该理论框架中一个显著的特点是，1/(1-γ) 因子并不适用于这一特定项。这是一个高维量，其范数需要保持较小，且未除以 1-γ。这一特性非常关键，因为通常人们不喜欢涉及 (1-γ) 除法的情况，因为它会导致问题视界（horizon）增长时数值爆炸，带来极大的不便。而在另一项中，在计算误差之前先将其投影到低维空间。这种处理方式巧妙地规避了长期累积带来的数值不稳定问题，使得在高维度环境下进行策略评估变得更加可行和稳健。

状态抽象的局限性与非参数世界的挑战

尽管上述理论在状态抽象（state abstraction）方面表现良好，但实际应用中仍面临诸多挑战。例如，如何无缝地实现时间和动作抽象（time and action abstraction）并应用类似方法？目前尚不清楚如何高效地学习这种结构。当考虑核均值嵌入（kernel mean embeddings）时，因子分解自然出现，但随之而来的是计算复杂度的问题：如果拥有 n 个数据点，所有算法的复杂度都将随 n³ 增长。尝试通过投影和其他技术来解决这一问题并未取得理想效果。因此，如何在非参数世界中使这些方法真正可行，仍是一个亟待解决的核心难题。

在线学习中的伪遗憾与性能差异引理

最后一部分转向无模型强化学习与在线学习（online learning），这一方向受 DeepMind 同事启发。鉴于目前基于模型的方法不如无模型方法成功，重点在于设计具有合理理论保证的函数近似（如神经网络）算法。在在线设置中，关注的是遗憾值（regret），即与从头开始最优行动或固定参考策略 π 相比的损失。虽然存在伪遗憾（pseudo regret），但在混合马尔可夫决策过程等条件下，伪遗憾与实际遗憾之间的差异是可以被界定的。控制伪遗憾足以反映策略的技能水平，且其公式揭示了在线线性优化（online linear optimization）*的结构。

损失框架下的策略更新与近似误差控制

在损失框架（loss framework）下，Q 函数对应成本，需与事后最佳选择进行比较。对于每个状态，都需要控制线性表达式中的量。只要对每个状态进行控制即可保证整体性能。虽然 Q_t（策略的动作值函数）不可直接访问，学习者需对其进行估计，但可以通过恒等式将差异分解为三项。其中两项相互抵消，第一项可通过在线线性优化（OLO）进行控制。只要保持其他项有界并自适应调整步长，即可利用在线学习工具进行管理。此外，假设使用强大的函数近似器来控制其余两项（即近似误差），随着数据收集量的增加，Q_t 将更接近真实值。这一分解依赖于性能差异引理（performance difference lemma），尽管其直观性不强，但代数推导证实了其有效性。

基于指数权重算法的在线优化与策略迭代

在强化学习的最新研究方向中，在线优化（online optimization） 提供了一种基础的算法构建思路。最简单的实现方式是采用 指数权重（exponential weights）算法。当将这一机制应用于策略优化时，可以直接推导出一种特定版本的 策略迭代（policy iteration） 算法。这种结合专家建议或指数权重更新的策略迭代方法，在结构上与 Poisson 平均 相似。从直觉上理解，这种算法机制能够引入某种程度的 方差缩减（variance reduction） 效果。这意味着在训练过程中，算法允许运行更短的 阶段（phases），从而在保证稳定性的同时提高计算效率。这种通过指数化或熵正则化处理的方式，为策略更新提供了一种更为平滑且具备统计优势的迭代路径。

函数近似误差控制与遗憾率界限分析

该算法框架的一个核心元结果（meta result）关注于 函数近似误差 的控制。研究指出，如果在每一次迭代中能够有效控制函数近似的误差（通常遵循参数化速率），那么整个系统的 遗憾率（regret rate） 可以被推导出来。具体而言，平均遗憾率的收敛速度为 $t^{-3/4}$（即时间步长的负四分之三次方）。演讲者坦言，这一收敛速度相对较慢。然而，该理论的一个显著优势在于其对 函数近似下界（floor of there is epsilon zero） 的处理：如果存在一个不可避免的最小误差项，该遗憾率公式中会直接包含这一项。这表明当前的理论界限已经触及了理论上可能达到的 最佳性能（best possible），即无法进一步消除由近似本身带来的固有误差。

线性值函数近似的挑战与探索机制的必要性

尽管理论界限看似完美，但在实际应用中仍存在显著问题。以 线性值函数近似（linear value function approximation） 为例，研究表明误差可能会剧烈膨胀。具体而言，试图求解 不动点方程（fixed point equation） 的函数近似器所产生的误差，可能远大于在线性子空间中能获得的 最小可能误差（smallest possible error）。这构成了该领域的一个开放性问题：是否存在比现有方法更优的近似策略？此外，原始算法隐含地假设了 无限探索所有动作（exploring all the actions indefinitely）。如果这一条件不满足，则必须将 状态值函数（state value function） 与动作值函数分离，并显式地加入对动作的探索机制。为了简化问题，可以假设所有策略都能 激发特征（exciting the features），即底层数据格拉姆矩阵的特征值在所有遭遇的策略中一致地远离零。这一假设虽然强大，但仍需进一步验证其普适性。

好奇心驱动探索与离线学习困境

为了突破上述限制，可以借鉴 好奇心（curiosity） 驱动的方法。在这种设定下，存在一个专门用于探索空间的策略。如果该策略能够充分 激发特征空间（explore the feature space），即可利用它来执行复杂的探索任务。然而，这种做法引入了 离线学习（off-policy regime） 的复杂性。在离线学习中，控制函数近似误差并保证理论结果变得极具挑战性，因为目前针对 离线学习（off-policy learning） 的良好结果非常有限。虽然可以通过调整算法细节来获得遗憾率界限，但 resulting bound 并不美观（not super nice），且感觉尚未形成完整的产品级解决方案。当前仍有许多明显的问题亟待解决：例如使用其他在线学习方法是否能取得更好效果？平均化是否真的必要？以及如何设计更优秀的 值函数学习者（value function learners）。这些问题的探索标志着当前强化学习研究正处于一个充满活力且令人兴奋的阶段。

"The simplest algorithm that you can use in online optimization is exponential weights. You plug in exponential weights, and lo and behold, you get this version of policy iteration."

"If the floor of there is epsilon zero, then that just appears there in the regret... it's the best possible that you can do."

"We don't have very good results for off-policy learning and controlling the function approximation error. So you can massage things and still get the regret bound, but it's not super nice and doesn't feel like a finished product."

结论

本次研讨会的三项核心研究均揭示了强化学习在理论严谨性与实际可行性之间的张力。好奇心驱动探索算法虽确立了动态环境下的可达性界限，但立方复杂度及二次依赖瓶颈限制了其即时应用。部分监控领域通过联合优化分布与估计量，突破了传统算法在信息受限场景下的失效困境。函数近似方面，线性子空间投影与因子模型提供了策略误差的严格界限并规避了数值爆炸风险。然而，离线学习中的近似误差控制仍缺乏优雅的理论保证，且高维非参数世界的计算复杂度尚未解决。这些成果明确了当前RL从理想化假设走向复杂现实环境的关键障碍与理论边界。