Reinforcement Learning with Segment Feedback

分段反馈强化学习

https://arxiv.org/pdf/2502.01876

摘要

标准的强化学习（RL）假设智能体能够对每个状态-动作对观测到相应的奖励。然而，在实际应用中，为每个状态-动作对收集奖励往往困难且成本高昂。尽管已有若干研究考虑了基于轨迹反馈的强化学习，但当轨迹较长时，轨迹反馈在学习过程中是否效率低下仍不清楚。在本研究中，我们提出了一种名为“基于分段反馈的强化学习”（RL with segment feedback）的模型，该模型提供了一个通用框架，填补了逐状态-动作反馈与整条轨迹反馈之间的空白。在该模型中，我们考虑一个分幕式马尔可夫决策过程（episodic MDP），其中每一幕被划分为 m 个分段，智能体仅在每个分段结束时获得奖励反馈。在此模型下，我们研究了两种常见的反馈设置：二元反馈和求和反馈。在二元反馈中，智能体根据底层奖励函数观测到一个二元结果；在求和反馈中，智能体观测到该分段内奖励的总和。为了探究分段数量 m 对学习性能的影响，我们设计了高效的算法，并针对两种反馈设置分别建立了遗憾（regret）的上界和下界。我们的理论分析和实验结果表明：在二元反馈下，增加分段数 m 能以指数速率降低遗憾；相反，令人惊讶的是，在求和反馈下，增加 m 并不能显著减少遗憾。

强化学习（RL）是一类序列决策算法，其中智能体随时间与未知环境进行交互，目标是最大化所获得的奖励。强化学习具有多种应用，例如机器人、自动驾驶和游戏博弈。

在经典的强化学习（RL）中，当智能体在某个状态下采取一个动作时，环境会为该状态-动作对提供一个奖励。然而，在实际应用中，为每个状态-动作对收集奖励往往是困难且代价高昂的。例如，在机器人领域，当我们指示机器人炒鸡蛋时，很难为每一个具体动作定义奖励。在自动驾驶中，考虑到安全性、舒适性和速度等多个标准，评估每一个动作是困难且繁重的。

基于这一现实，已有若干研究考虑了具有轨迹反馈的强化学习（Efroni 等，2021；Chatterji 等，2021）。在这些研究中，智能体仅在每一幕结束时获得一次奖励信号，而不是在每一步都获得反馈，该信号表示在该幕中生成的轨迹的质量。尽管这些工作缓解了经典强化学习中每步奖励反馈不切实际的问题，但反馈频率与强化学习算法性能之间的关系仍不清楚。特别是，如果我们在每条轨迹中获得两次反馈，相较于每条轨迹仅一次反馈，性能是否会显著提升？

为回答这一问题，我们研究了一种称为“基于分段反馈的强化学习”（RL with segment feedback）的一般性模型，该模型填补了经典强化学习中逐状态-动作反馈（Sutton & Barto, 2018）与近期研究中轨迹反馈（Efroni 等, 2021; Chatterji 等, 2021）之间的空白。在该模型中，我们考虑一个分幕式马尔可夫决策过程（episodic MDP），其中每一幕被均等地划分为 m 个分段。在每一幕中，每一步智能体首先观测当前状态，采取一个动作，然后根据转移分布转移到下一个状态。智能体仅在每个分段结束时观测到一个奖励信号。在此模型下，我们考虑两种奖励反馈设置：二元反馈和求和反馈。在二元反馈设置中，智能体观测到一个由该分段上奖励经过Sigmoid函数生成的二元结果（例如，点赞/踩）。在求和反馈设置中，智能体观测到该分段内所有奖励的总和。在我们的模型中，智能体需要从二元或求和的分段反馈中学习底层的奖励函数（即状态和动作的期望奖励函数），并最大化所获得的期望奖励。虽然 Tang 等（2024）此前也研究过这一分段模型（他们称之为“从打包奖励中学习的强化学习”，RL from bagged reward），但他们的工作主要是经验性的，未为算法提供理论保证，也未严格揭示分段数量对学习的影响。

该模型适用于许多涉及人类查询的场景。例如，在自动驾驶中，驾驶轨迹通常被划分为若干段，人类标注者被要求对每一段提供反馈，例如点赞或踩。与状态-动作对或整条轨迹相比，分段更容易且更高效地进行评估，因为人类标注者可以集中关注并评价每个分段中的行为，例如通过十字路口、倒车或停车。

在该分段模型中，存在一个关于分段数量（即向人类发起的查询次数）与所收集观测信息之间的有趣权衡：我们希望获得更多的观测信息，但同时也希望减少查询次数。因此，在该问题中，关键在于研究分段带来的收益与查询次数增加之间的权衡，这本质上归结为一个问题：分段数量 m 如何影响学习性能？

为回答这一问题，我们为二元反馈和求和反馈设置分别设计了在转移函数已知和未知情况下的高效算法，并提供了遗憾（regret）的上界和下界，以严格揭示分段数量对学习性能的影响。我们还通过实验验证了理论结果。

需要注意的是，研究具有等长分段的强化学习是一个重要的起点，为后续研究更一般的模型以及非等长分段的强化学习分析奠定了基础。即使在等长分段的情况下，该问题仍然极具挑战性：（i）该问题无法直接应用先前的轨迹反馈研究（例如 Efroni 等，2021）来解决，因为这些研究在分析中利用了后续轨迹之间的鞅性质，而同一幕内的各个分段之间存在依赖关系，因此后续分段并不构成鞅；（ii）在先前的轨迹反馈研究中（Efroni 等，2021；Chatterji 等，2021），对于求和反馈，其上界与下界之间仍存在差距，而对于二元反馈则尚未建立下界。这一事实为我们理解分段数量 m 对学习性能的影响带来了重大挑战。

我们的工作克服了上述挑战，主要贡献如下：

  1. 我们研究了一种称为“基于分段反馈的强化学习”（RL with segment feedback）的一般性模型，该模型无缝地弥合了经典强化学习中的逐状态-动作反馈与轨迹反馈之间的差距。在此模型下，我们考虑了两种反馈设置：二元反馈和求和反馈。

  2. 针对二元反馈，我们分别为转移函数已知和未知的情况设计了计算高效且样本高效的算法 SegBiTS 和 SegBiTS-Tran。我们给出了依赖于 exp(−Hrₘₐₓ²/m) 的遗憾上界和下界，其中 H 表示每幕的长度，rₘₐₓ 是奖励的通用上界。我们的结果表明，在二元反馈下，增加分段数量 m 能显著加速学习过程。

  3. 针对求和反馈，我们设计了算法 E-LinUCB 和 LinUCB-Tran，它们在 H 和 m 的意义下实现了近似最优的遗憾。我们还建立了下界以验证其最优性，并证明最优遗憾并不依赖于 m。我们的结果揭示了一个令人惊讶的现象：在求和反馈下，增加分段数量 m 并不能显著加快学习速度。

  4. 我们发展了若干新颖的技术，这些技术本身可能具有独立的研究价值，包括利用KL散度分析推导二元反馈下的指数型下界，以及在算法 E-LinUCB 中采用E-最优实验设计方法，以优化协方差矩阵的特征值并降低遗憾。

1. 相关工作在本节中，我们简要回顾先前的相关研究。

经典强化学习的算法与分析在文献中已有深入研究（Sutton & Barto, 2018；Jaksch 等, 2010；Azar 等, 2017；Jin 等, 2018；Zanette & Brunskill, 2019）。Tang 等（2024）提出了基于分段反馈的强化学习问题（他们称之为“从打包奖励中学习的强化学习”，RL from bagged rewards），并设计了一种基于Transformer的算法。然而，他们的工作主要是经验性的，并未提供理论保证。Gao 等（2025）研究了具有“打包决策时刻”的强化学习，其中在一个“包”内的状态转移是非马尔可夫的，并在包结束时观测到一个奖励。但Gao等（2025）的重点是使用因果有向无环图来处理包内的非马尔可夫状态转移，而不是像我们这样研究如何从打包的奖励中推断状态-动作对的奖励函数。此外，据我们所知，目前尚无现有工作能够严格量化分段数量对学习性能的影响。

有两项先前的工作（Efroni 等, 2021；Chatterji 等, 2021）研究了具有轨迹反馈的强化学习，与我们的工作最为相关。Efroni 等（2021）研究了具有求和型轨迹反馈的强化学习，设计了具有遗憾保证的置信上界（UCB）类型和汤普森采样（TS）类型算法。Chatterji 等（2021）研究了具有二元轨迹反馈的强化学习，但其对二元反馈的建模方式与我们不同。具体而言，在他们的设定中，目标是寻找一个策略，使其生成反馈为1的概率的期望最大；由于Sigmoid函数的非线性性质，其最优策略可能是非马尔可夫的。而在我们的设定中，目标是通过从二元反馈中推断奖励，找到在标准MDP定义下的最优策略，因此我们考虑的是马尔可夫策略。由于其目标函数的非线性以及直接在所有非马尔可夫策略上进行优化，Chatterji 等（2021）提出的算法要么计算效率低下，要么遗憾阶次次优。我们的算法通过采用汤普森采样（TS）风格以及在马尔可夫策略下的高效MDP规划，实现了计算上的高效性。由于问题设定不同，我们的遗憾结果无法直接与Chatterji 等（2021）的结果进行比较。

此外，与Efroni 等（2021）和Chatterji 等（2021）不同，我们研究的是基于分段反馈的强化学习，允许在一条轨迹内从多个分段获得反馈，而逐状态-动作反馈和整条轨迹反馈则分别对应于该模型的两个极端情况。在求和反馈设置下，当问题退化为轨迹反馈情形时，我们通过实验设计将Efroni 等（2021）的结果在遗憾上改进了√H因子。在二元反馈设置下，我们提出了具有计算效率的TS风格算法，并建立了下界，揭示了遗憾界中不可避免的指数因子，这在强化学习文献中是新颖的。

我们的工作也与线性赌博机（linear bandits，Abbasi-Yadkori 等, 2011）和逻辑斯蒂赌博机（logistic bandits，Filippi 等, 2010；Faury 等, 2020；Russac 等, 2021）相关，并借鉴了这些领域中的分析技术。

2. 问题设定

在本节中，我们给出具有二元反馈和求和反馈的分段式强化学习的问题形式化描述。

在我们的模型中，代理只在每个阶段结束时观察奖励反馈，而不是像经典强化学习那样在每一步都观察。我们考虑以下两种奖励反馈设置：

我们注意到，据我们所知，在二元反馈情况下，只能获得关于总奖励的极其粗略的信息，这使得对两种反馈模型进行统一分析变得不可能。

3. 基于二元片段反馈的强化学习

在本节中，我们研究基于二元片段反馈的强化学习。为了将片段反馈的影响与转移模型学习分离开来，我们首先为转移模型已知的情形设计了一种计算高效且样本高效的算法 SegBiTS，并建立了一个新的下界，以展示在二元反馈情况下结果中不可避免的指数依赖性。随后，我们进一步开发了算法 SegBiTS-Tran，该算法针对转移模型未知的情形，精心设计了转移奖励项。

3.1 已知转移模型下的算法 SegBiTS

3.2 已知转移模型下的遗憾下界
下面我们提供一个下界，该下界首次表明，在具有二元反馈的强化学习中，遗憾界中出现指数因子是不可避免的。

3.3. 未知转移情况下的算法 SegBiTS-Tran

4. 具有总和片段反馈的强化学习

在本节中，我们转向具有总和片段反馈的强化学习。与之前的总和轨迹反馈算法（Efroni等人，2021）不同，后者直接使用最小二乘估计器，并具有次优的遗憾界限，我们为已知转移的情况开发了一种算法E-LinUCB，该算法采用实验设计进行初始探索，并实现了相对于H和m的近优遗憾。为了验证最优性，我们进一步建立了一个遗憾下界。此外，我们设计了一个算法LinUCB-Tran，配备了一个方差感知的转移奖励，以处理未知转移的情况。

4.1. 已知转移的E-LinUCB算法

4.2. 已知转移的遗憾下界

我们为具有总和片段反馈和已知转移的强化学习建立了如下的遗憾下界。

定理 4.2。考虑具有总和片段反馈和已知转移的强化学习。存在一种实例分布，其中任何算法的遗憾必须为：

定理 4.2 表明，我们对算法 E-LinUCB 的遗憾上界（定理 4.1）在忽略对数因子时，相对于 H 和 m 是最优的。此外，这个下界证实了片段数量 m 本质上并不影响遗憾结果。

4.3 未知转移情况下的算法 LinUCB-Tran

定理 4.3 表明，与算法 E-LinUCB 类似，当忽略对数因子时，LinUCB-Tran 的遗憾并不依赖于片段数量 m。对 |S|、|A| 和 H 更强的依赖性是由于对未知转移分布的估计。我们还为未知转移情况提供了一个下界，这表明最优遗憾确实不依赖于 m，并且我们的上界相对于 H 是近优的（见附录 D.5）。

5 实验

6 结论

原文链接：https://arxiv.org/pdf/2502.01876