强化学习 | (4) RUDDER - Reinforcement Learning with Delayed Rewards

原文地址

论文《RUDDER: Return Decomposition for Delayed Rewards》

最近，通过复杂的策略游戏，需要model-free强化学习的具有延迟奖励的任务引起了很多关注。例如，DeepMind目前专注于延迟奖励游戏《夺旗》和《星际争霸》，而微软则在搭建Marlo环境，Open AI宣布了Dota 2的成就。使用无模型的强化学习来掌握这些具有延迟奖励的游戏带来了巨大的挑战，并且几乎是无法克服的障碍，请参见出色的理解OpenAI Five博客。延迟的奖励很常见，因为它们通常出现在具有偶然(episodic)或稀疏奖励的强化学习（RL）任务中。他们在学习中提出了一个基本问题，其解决方案是RL中长期存在的挑战（摘要，第vii页）。对于复杂的现实世界任务，例如 自动驾驶或控制智慧城市，尚无合适的模型且难于学习，因此，仅model-free的强化学习是可行的。

通过RUDDER，我们引入了一种新颖的model-free RL方法来克服延迟奖励问题。 RUDDER直接和有效地将credit分配给引起奖励的状态-动作对，从而显着加快了有严重延迟奖励的model-free强化学习的速度。

RUDDER主要思想

我们提出了一种范式转换，用于延迟奖励和model-free的强化学习。 常规方法有如下问题：

1. 不要使用时序差分（TD），因为它会遭受信息消失并导致高偏差的影响，即使有资格迹也是如此。
2. 不要使用蒙特卡洛（MC），因为对所有可能的未来进行平均会导致高方差。
3. 不要使用基于状态-动作对的常规价值函数，因为必须从每个状态-动作对中预测期望的return。 单个预测错误可能会妨碍学习。

监督学习：假设你有较高的奖励和平均情节奖励。 监督学习识别出引起高奖励的状态-动作对。 因此，我们希望调整策略，以便更频繁地到达这些状态动作对。 将奖励重新分配给这些状态动作对可实现这些调整。

值函数是阶跃函数(a step function)：RUDDER的主要思想是利用值函数是阶跃函数这一事实。 复杂任务是带有子任务或子目标的分层结构。值函数中的步骤反映了它们的完成。 从这个意义上讲，步骤表示诸如成就，失败或环境/信息更改之类的事件。通常，值函数中的一个步骤是return期望的变化（更高/更低的return量或更高/更低的获得return的可能性）。 奖励将重新分配到这些步骤。 特别是，确定重要步骤非常重要，因为它们可以极大地加快学习速度：

• return大幅增加（调整政策后）。
• 采样更多相关情节。

在这个简单的钥匙门示例中，agent必须拿起钥匙才能打开通往藏宝室的门，在藏宝室中它将找到藏宝。

获得钥匙和打开门都增加了获得宝藏的可能性。 因此，结果价值函数分别具有用于获取钥匙的步骤和用于打开门的步骤。

前馈网络：完全连接的网络的学习step functions需要从每个状态-动作对中提取期望的return。在上图中，常规的价值函数学习必须从每个输入图像中提取agent具有确定正确期望return的钥匙的事实。但是，在“领取钥匙”直到“打开门”之后，以及“开门”直到“领取宝藏”之后，期望的return都不会改变。因此，在这些间隔中，价值函数是恒定的。 没有有关期望return的新信息，而仅重复提取先前的信息。 这样的间隔可能跨越数千个时间步长，即使不改变期望的return，也必须从每个时间步中提取期望的return。


递归神经网络：通过记忆事件（步骤，新信息）来学习step function的采样效率更高。只需要学习相关事件“获取钥匙”和“打开门”的模式即可代表整个价值函数。必须存储这些事件以确定正确的期望return。 在时间值不变的情况下，无需学习任何内容。 如果只有几个步骤，这将非常有效。我们建议使用LSTM网络，其中只有相关事件存储在记忆单元中，而对于不相关事件，LSTM记忆单元不会发生变化，并且LSTM输出会根据需要保持恒定。

奖励重新分配：奖励重新分配到价值函数中的步骤（下面的绿色箭头）。 奖励重新分配是固定的过程，它针对每个情节沿着状态-动作序列向步骤重新分配实现或期望return。重新分配的奖励将在新环境中替换原始奖励（保留状态-动作对）。 在最佳奖励重新分配中，预期的未来奖励始终等于零（下面最后一行中位于零的蓝线）。Q值估计简化为计算平均值的过程，因此学习非常高效。

return分解：奖励重新分配是通过递归神经网络的return分解获得的。return分解从递归神经网络（上面的绿色箭头）确定价值函数的步骤，这些步骤确定了重新分配的奖励。 通过贡献分析确定步骤，该分析计算输入对return预测的贡献。

RUDDER explained on a more detailed example

怀表示例任务将解释RUDDER的以下基本贡献：

• 具有相同最佳策略的等价return决策过程。
• 奖励重新分配，导致return等价的决策过程。
• 最佳奖励重新分配，导致期望的未来奖励为零。
• 通过贡献分析进行return分解。

根据怀表示例任务，此博客将带你逐步了解延迟奖励，预期的未来奖励等于零，return等价，奖励重新分配以及通过贡献分析进行return分解的主题。 我们将展示RUDDER如何有效解决延迟奖励的credit分配问题。

An example task for delayed rewards

在怀表示例任务中，假设您修理怀表然后出售。 对于特定品牌的手表，您必须决定维修是否有回报。销售价格是已知的，但您有未知的成本，即由维修和交付/运输引起的负奖励。在此示例任务中，当您决定某个特定品牌的手表维修它是否平均能得到回报时，延迟奖励是存在的。销售价格是已知的，但是您不知道立即的维修和将来的交付成本。 奖励之所以延迟，是因为只有在知道总费用后，您才知道维修此特定品牌的手表的决定是否有回报。

The problem formulation

您必须决定某个特定品牌的手表是否要维修。 优势函数是销售价格减去期望的立即维修成本减去期望的未来交付成本。 如果优势函数为正，则此修复会得到回报。

Classical RL methods

诸如时序差分（TD）学习，蒙特卡洛学习和蒙特卡洛树搜索之类的大多数经典RL方法尝试通过估计回报（即累积的未来奖励）来解决RL问题。 因此，它们必须对大量可能的未来进行平均。 特别是对于延迟的奖励问题，这具有严重的缺陷。

在示例任务中，许多事件介于“决定是否维修”和实际出售手表之间。 只有return可以告诉您维修是否有回报。为了评估决策，时序差分（TD）学习将TD错误降到最低，这归结为传播奖励（back）。反向传播的奖励纠正了先前状态下TD return估计的偏差。 不幸的是，TD学习需要大量更新才能将奖励传播回去，更新步数随着到达先前状态的路径长度呈指数增长，因此偏差校正指数级速度慢。因此，对于此类问题，TD方法是不可行的。 在（Sutton and Barto）的书中，第297页的公式12.11中显示TD（λ）-return呈指数消失。

TD update rule：
TD更新规则如下：

其中$V(S)$是价值函数，$S_{t?1}$和$S_t$分别是旧状态和当前状态，$R_t$是时刻t的奖励，$gamma$是折扣因子，$\alpha$是正学习率。

在我们的实例任务中，由于奖励$R_T$我们考虑一个新信息。接下来，我们展示如何将这个信息传播回来以提供新的价值。由$R_T$引起的信息用粗体符号表示。在状态$S_{T?1}$, 更新给出以下新价值$V_{new}(S_{T?1})$:

由于RT，使用新信息迭代更新价值将得出：


新信息的衰减系数为${\alpha }^{T?1}{\gamma }^{T?1}$, 这是相对于$R_T$和$S_1$之间的时间间隔T-1的指数衰减.

该决定也可以通过蒙特卡洛学习来评估。 蒙特卡洛在概率环境中对所有可能未来的return进行平均，该数字可能非常大。 如果return具有高方差，则蒙特卡洛学习将非常缓慢。 因此，与TD相比，蒙特卡洛学习存在方差大的问题。

我们得出结论，对于延迟较长的奖励任务，TD和$TD(\lambda )$学习都随着延迟时间的长度而呈指数下降。 另一方面，蒙特卡洛学习存在着return的高样本方差的问题，这在概率环境中是很典型的。

Zero future expected rewards

正如导言中“ RUDDER的主要思想”中所述，我们旨在将奖励重新分配给价值函数的各个步骤，从而极大地简化了学习过程。因此，与大多数传统的RL方法相比，RUDDER的主要目标是构建一个期望未来奖励为零的MDP。如果达成这个目标，Q值的估计将简化为计算即时奖励的均值。在示例任务中，如果知道了期望的未来成本（平均交付成本），则解决该任务变得很简单。可以将期望的未来成本添加到维修成本中，从而使未来成本为零。 因此，您只需要平均修理费用即可。 为了获得这个平均值，您可以使用该品牌的维修经验。

期望的未来奖励等于零为什么有优势？ 由于所有未来的奖励都等于零，因此可以通过对即时维修成本进行平均来轻松估算期望的利润。 这个估计既不会像TD那样遭受指数衰减的奖励传播，也不会像MC学习那样遭受高方差的困扰。 因为，没有必要对所有可能的轨迹求平均（如在MC中）或传播延迟的奖励（如在TD中）。 取而代之的是立即给出期望的利润，做出决定，并且预期不会再获得任何奖励。

在示例任务中，是否决定修理怀表，把期望的未来奖励变成0，只有和品牌相关的交付成本，如 包装成本，需要被估计。决定是否维修只会影响这些成本（负奖励）。 不幸的是，平均交付成本是与品牌相关的成本和与品牌无关的成本（例如， 交付花费的时间）的叠加。 那么，如何区分与品牌相关的成本与品牌无关的成本呢？

Return decomposition and pattern recognition

为了估算与品牌相关的成本，使用了依赖于模式识别的return分解。 在示例任务中，平均交付成本是与品牌相关的成本和与品牌无关的成本（一般交付成本）的叠加。可以假设与品牌无关的成本由模式表示。 如果下雪了，通常会延迟交货，从而导致成本上升。 如果交付遇到交通堵塞，通常也会延迟。如果送货卡车漏气，则送货费用会更高。 还有更多示例。 想法是使用一组完成的交付作为训练集，在有监督的学习中，监督学习可以确定这些事件的模式并将成本归因于这些事件。通过这种方式，RUDDER通过识别关键事件并向其重新分配奖励，从而将预期的未来奖励推向零。 从return中消除与关键事件相关的与品牌无关的交付成本，可以大大减少剩余return的方差，因此，估算与品牌相关的成本变得更加有效。

在RUDDER中，通过引入等价return决策过程，奖励重新分配，return分解和最优奖励重新分配的概念，在数学上认可将预期的未来奖励归零并重新分配奖励。

RUDDER - more technical:

一个有限的马尔科夫决策过程（MDP）P是一个6-元组 $P=(S,A,R,p,\gamma )$:

• 状态s的有限状态集合 S （t时刻的随机变量$S_t$）
• 动作a的有限状态集合A （t时刻的随机变量$A_t$）
• 奖励r的有限集合R (t时刻的随机变量$R_t$)
• 奖励转换分布 $p=(S_{t+1}=s^{\prime },R_{t+1}=r|S_t=s,A_t=a)$
• 折扣因子 $gamma$

期望奖励是所有奖励转换分布的总和：

对于一个有限的水平MDP，序列长度为T，$\gamma =1$, return为：

对于策略$\pi =p(A_{t+1}=a^{\prime }|S_{t+1}=s^{\prime })$，动作价值函数$q^{\pi }(s,a)$为：

学习的目标是最大化t=0时刻的期望的return：

Return equivalent decision processes

序列马尔可夫决策过程（SDP）定义为配备了马尔可夫策略且具有马尔可夫转移概率但不一定是马尔可夫的奖励的决策过程。两个SDPs $\tilde{P}$和P是return等价的，如果：

• 他们只是在奖励转移分布上有所不同
• 对于每个策略$\pi$,在t=0时刻，他们有相同的期望return：${\tilde{v}}_0^{\pi }=v_0^{\pi }$

我们表明，return等价的SDP具有相同的最优策略。 在RUDDER中，想法是将具有延迟奖励的MDP转换为不同的但return等价的SDP，其中奖励的延迟较少，因此更易于学习。

具体来说，在我们的示例任务中，原始MDP会在售出维修后的手表的最后一刻给予奖励。 RUDDER将奖励重新分配给关键事件，并创建一个新的SDP，该SDP确保与原始MDP return等价。 因此，与原始MDP相反，维修手表的决定将立即得到奖励。

Return decomposition

return分解确定了每个状态-动作对对return的贡献-return被分解。每个状态动作对的贡献是新的奖励，并确保一个奖励的重新分配能导致一个新的、return等价的MDP。通过学习一个预测每个状态动作序列return的函数，可以找到该贡献。 随后，此函数有助于在整个序列上分配return。从概念上讲，这是通过贡献分析完成的，其中确定每个序列元素对return预测的贡献。 我们查看当前输入对最终预测有多大贡献，并考虑三种贡献分析方法，尽管在实践中可以使用任何贡献分析方法：

• “预测差异”
• 集成梯度
• 逐层相关性传播

我们更喜欢预测差异，其中预测从一个时间步到下一个时间步的变化是对一个输入对最终预测的贡献的度量。

Optimal return decomposition

什么是好的return分解？ 什么是最优return分解？ 现在，我们将为您提供一个直观的认识。

想象一下，您有一个奖励ledger，它跟踪您的预期累积奖励，但您并未意识到这一点。在每个时间步骤，奖励ledger都会根据当前期望进行更新。假设ledger是非空的，那么没有什么阻止您立即收到预期的奖励，从而清空了ledger。RUDDER利用了这种奖励accounting，在这种情况下，ledger的更改会导致立即pay out，即奖励，这会将ledger再次设置为零。 最优return分解的定义性质是，ledger始终为零，并且如果偏离零，则会立即清空，因此不会有未来的奖励。

我们通过最优条件定义最优return分解，该最优条件是预期的未来累计奖励始终为零。 因此，新的SDP没有延迟的奖励，并且Q值估计没有偏差。

奖励重分布：
奖励重新分配是通过使用函数g来实现的，该函数根据状态动作序列预测情节结束时的return G，然后使用对g的贡献分析。 贡献分析计算当前输入对最终输出的贡献，即当前输入对最终预测的信息增益。 我们将各个（输入）贡献用作新MDP中的新奖励。 我们证明了这种重新分配不会改变最优策略，因为它是return等价的。

在示例任务中，最佳return分解意味着在您决定是否修理某个特定品牌的手表后，便会获得全部奖励。 这种最优的return分解可确保预期的未来奖励为零。 如果在交付过程中发生一些不可预见的事件，则更新奖励ledger，以使预期的未来return保持为零。

RUDDER vs potential-based reward shaping

RL社区中的奖励塑形通过基于势的奖励塑形，look-ahead and look-back advice而闻名。 这些方法将通过塑形奖励增强的原始奖励用作新奖励（$rewar{d}^{new}=rewar{d}^{shaping}+rewar{d}^{ori}$。塑形奖励是通过势能函数差异获得的。 相比之下，RUDDER构造了一个全新的奖励函数，该函数替代了原始奖励（$rewar{d}^{new}=rewar{d}^{redistributed}$）.

通过奖励塑造， look-ahead advice, and look-back advice重新分配奖励是奖励重新分配的一种特殊情况。我们已经表明，从奖励塑形方法的势能函数中减去常数会使塑形奖励的总和为零(${\sum }_{t}rewar{d}_t^{shaping}=0$), 同时保留所有的势能差（塑造奖励）。因此，奖励重新分配会导致产生与原始MDPreturn等价的新SDP。但是，由于这些奖励塑形方法保留了原始奖励，因此它们的奖励重新分配不对应于最优return分解（无延迟奖励），因此，对于剩余的延迟奖励，通过TD进行学习仍然会呈指数缓慢。 RUDDER不是基于势能的奖励塑形。

上图显示了RUDDER与奖励塑形方法的比较。详细地，我们将RUDDER与具有资格迹的Q学习，具有资格迹的SARSA，奖励塑形（RS 原始），look-ahead advice（RS look-ahead），look-back advice（RS look-back）进行比较。对于每种方法，都绘制了解决任务所需的学习时间（以情节/轨迹为单位）与奖励延迟的关系。 蓝点虚线表示将RUDDER应用于具有资格迹的Q学习（RUDDER Q）上。 在所有情况下，RUDDER都是指数级更快，并且明显优于奖励塑形方法。

LSTM in RUDDER

我们已经看到，RUDDER会检测关键事件，并在相关奖励延迟时为它们分配credit。这样，即使相关动作和状态发生的时间早于奖励，也可以将其识别出来。识别由深度学习完成，深度学习擅长于模式识别问题。 在过去的几年中，长短期记忆（LSTM）网络在序列分析中获得了巨大的发展势头。要全面了解递归神经网络，尤其是LSTM，请仔细阅读Andrew Karpathy的博客。 在RUDDER中，LSTM是return预测函数的明显选择，该函数可以进行return分解并基于状态动作序列。 通过分析整个情节，LSTM可以检测出与奖励最相关的关键事件。

Reward redistribution via LSTM

当LSTM检测到关键事件时，就会在LSTM的内存中存储一条信息。 然后将其用于最后的预测。 通过分析LSTM的记忆，我们可以重建这些信息，并将各个状态-动作对的贡献分配给最终的奖励预测。

RUDDER in practice

RUDDER新颖的学习算法是直接估算Q值。但是，通过使用重新分配的奖励作为新的奖励，可以将RUDDER与任何RL算法结合使用。 我们更喜欢将直接Q值估计应用于策略梯度算法，尤其是PPO（请参阅作者和Jonathan Hui的精彩博客）。LSTM使用状态动作序列作为输入来预测return。 所学习的LSTM模型允许通过贡献分析方法执行return分解。 此return分解可应用于任何状态-动作序列（有一个分配的return来重分布奖励）。这种重新分配甚至对于其他的状态动作序列也有效，这些状态动作序列来自一个不同的策略，该策略与训练LSTM和确定return分解的策略不同。

FAQ

• LSTM会使用整个序列，而不只是最后一个状态-动作对吗？
  对于奖励重新分配，我们假设在序列末尾具有一个奖励（=回报）的MDP，可以从最后一个状态-动作对来预测。我们要删除此Markov属性，以强制LSTM存储导致奖励的相关过去事件。这样，贡献分析将识别这些相关的过去事件并给予奖励。为了消除这种马尔可夫性质，我们定义了一个状态动作对及其前驱之间的差异 $\Delta$，其中假设$\Delta s$相互独立。现在，无法根据最后一个$Delta$预测序列末尾的奖励。 仍然可以根据$\Delta s$序列预测return。由于$\Delta s$相互独立，因此每个$\Delta$对于return的贡献必须存储在LSTM的隐藏状态中才能预测最终的奖励。$\Delta$可以是通用的，因为状态和动作可以编号，然后可以将这些数字的差用于$\Delta$。在像Atari这样的具有即时奖励的应用中，我们在情节结束时给出累积的奖励，而不会丰富状态。这具有与使用$\Delta$相似的效果。 我们强迫LSTM建立一个内部状态，该状态跟踪已经累积的奖励。示例：agent必须带一把钥匙才能打开门。 由于它是一个MDP，因此agent始终知道有钥匙（通过一个打开的指示位 为1）。 可以在最后一步中预测奖励。 使用差$\Delta$该指示位为零，除了agent获取钥匙的步骤外。 因此，LSTM必须存储此事件（获取钥匙）并向其转移奖励。

• LSTM是价值函数吗
  LSTM是在时间t的值函数，但基于直到时间t的$\Delta$子序列。LSTM预测可以分解为两个子预测。 第一个子预测是已知直到时间t的子序列$\Delta$对于return的贡献（后向视图）。 第二个子预测是未知的从t + 1开始到return的未来序列的预期贡献（前向视图）。但是，我们对第二个子预测不感兴趣，而仅对时间t处的Δ对预期return预测的贡献感兴趣。第二个子预测与我们的方法无关。 我们通过预测差异来取消第二个子预测。 时间t处的差异给出了时间t的$\Delta$对期望return的贡献。

• 为什么不直接将LSTM用作价值函数？
  我们使用LSTM作为价值函数开始了这个研究项目，但是失败了。我们将LSTM作为示例任务（论文中的人工任务（II））的值函数进行了调查。在RUDDER已解决任务的时间点，LSTM错误仍然太大，无法通过价值函数进行学习。问题在于序列开始处的return方差很大，这阻碍了LSTM学习（前向视图）。 LSTM学习是通过在序列末尾反向传播预测误差来发起的，在该序列末端，return的方差较低（后向视图）。这些后期的预测也开始在序列开始处存储关键事件即使有高预测误差。在关键事件上重新分配的奖励导致RUDDER解决了任务。结论：在RUDDER已经解决任务的时间点，由于return方差很大，所以无法学习早期的预测。因此，将预测用作价值函数没有帮助（前向视图）。

RUDDER demonstration code

您可以找到此博客中描述的示例任务的代码here
您可以找到有关如何执行奖励重新分配的实用教程here
您可以在这里找到我们的github仓库here

Video of RUDDER in the ATARI game Bowling

下面的视频显示了RARDDER在有延迟奖励的ATARI游戏Bowling中的工作。 在这里，agent必须将球朝10个瓶子滚动，以将其击倒。 在保龄球中，agent有两种影响结果的方式。 首先，从起始位置开始，agent在他滚球时就采取了措施，其次，调整球滚向瓶子的曲线。 仅在完成滚动后（最后结果出来后）才对agent进行奖励。 如视频所示，RUDDER管理

• 将奖励分配给成功允许将球弯向瓶子的动作，
• to assign negative rewards for not knocking all of the pins down,
• rolling a strike (as indicated by the blinking scores).
  
  
  视频地址