论文笔记 Learning Reward Machines for Partially Observable Reinforcement Learning

摘要

Reward Machines 提供了一种对奖励函数进行结构化的、基于自动机的表示，让agent得以将一个RL问题分解成结构化的子问题，这样一来可以通过离线学习（off-policy）高效解决。

本文展现了RM可以通过经验学习到（而不是由用户来具体说明），以及问题分解可以用来有效解决部分可观察的（partially observable）RL问题。作者将学习RM的任务作为一个离散的优化问题，其目标是找到一个可以将一个问题分解成一系列子问题的RM。这些子问题的最优无记忆（optimal memoryless）policies的结合就是对原问题的最优policy。

本文展示了这个方法在三个部分可观察领域的有效性，并且在其中表现比A3C、PPO、ACER更好。本文还讨论了它的优缺点以及潜力。

介绍

RL（包括DRL）方法在部分可观察的环境中表现不佳，原因是这种环境下的agent往往需要某种记忆形式来学习最佳表现。关于提供RL agent记忆的最近方法要不就是用RNN，要不就是用memory-augmented neural network。

作者展示了Reward Machine是另一种有效的工具来在部分可观察的环境中提供记忆。

RM最初用来提供一种对奖励函数结构化的、基于自动机的表示。显现的结构可以为Q-Learning for Reward Machines（QRM）所用。QRM为每个RM中的状态同时单独学习一个policy。QRM被证明在许多离散和连续领域比经典和分层DRL表现更好。但是QRM只能用于完全可观察的环境，并且RM是手动生成的。

作者提出一种在一个部分可观察的环境中直接从经验学习到RM的方法。这是通过让RM作为一个RL算法的记忆实现的。要求是RM学习方法需要被给定一个detectors for properties的有穷集合，作为RM的词汇表。作者描述了一个RM学习的目标，得以将任务形式化成一个离散最优问题，并且提出一个高效本地搜索方法来解决它。

通过同时学习一个RM和一个policy，可以在三个部分可观察领域显著超越许多将RNN作为记忆的DRL baselines。

准备工作

强化学习

Q-learning

部分可观察

信念状态

Reward Machines for Partially Observable Environments

本章会定义reward machines for partially observable environments，将使用一些例子来帮助理解。

Reward Machine

如Definition 3.1所示，RM是一个元组（有穷状态集，初始状态，状态转移函数，奖励转移函数），用来编码一个奖励函数的有穷状态机。给定经验e = (o, a, o')，labeling函数 L可以为命题符号集合P赋值，从而获得高阶特征。其中o'是观察o时执行动作a后的观察。

The cookie domain

The cookie domain（见Figure 1a）有三个房间并由走廊连接。agent（紫色三角形）可以四个基本方向移动。黄色房间里有一个按钮，按了就会让一个cookie随机地在红色或蓝色房间里产生。当到达cookie处，agent获得奖励+1，然后继续去按按钮。在到达cookie前按按钮，会把agent送到一个随机位置。episode开始时没有cookie。这是一个部分可观察环境，因为agent只有当他进入房间才能知道房间里有什么。

命题符号集。这些属性为true的条件如下。在经验结束时，：agent和cookie在同一个房间；：agent按下按钮；：agent吃掉了cookie；：agent待在该颜色的地方（房间/走廊）。

Figure2展示了cookie domain中三个可能的RM。奖励符号1为吃掉cookie，0为没吃掉。Figure 2b中，u0和u2之间的label代表，表示走到红色房间，发现并吃掉cookie，获得奖励+1。o/w表示otherwise。

当为给定RM学习一个policy时，一个简单的方法是学习一个考虑当前观察o和当前RM状态u的policy π(o, u)；另一种方法是使用QRM。

QRM

当应用tabular q-learning时，QRM被证明在完全可观察问题中可以收敛到一个最优policy。然而在部分可观察环境中，一个经验e会或多或少取决于它被收集时的RM状态。例如，经验e可能在RM状态ui中是可能出现的，而在RM状态uj中不可能出现。因此，如果像QRM一样使用e来为uj更新policy，会导致一个q函数的偏差。

用traces学习reward machine

本文总体思想是找到一个RM作为agent的外部记忆。本文方法只取一个高阶命题符号集合P和一个labelling函数L作为输入。关键问题是这样的RM有什么特性。

有三种方法在文献中出现，第一种没有提供记忆，第二种计算量太大，故本文采取第三种：来自文献Predictive State Representation（PSR）、Deterministic Markov Models（DMMs）和 model-based RL的方法。这些工作建议学习一个记忆足够历史信息的RM来对下一个观察作出精确的马尔可夫预测。如Figure 2c所示，由于跟踪更多信息并不能带来更好的预测，所以 这个RM是perfect的。

Perfect Reward Machines的定义和特性

Perfect Reward Machines的学习方法

本文提出了一种关注于perfect RM的必要条件的学习方法：RM必须抽象地预测在环境中什么是可能和不可能的。例如，Figure 2c中状态u3不可能有抽象观察，因为要么cookie被看见在蓝色房间里，要么cookie不在红色房间里，否则RM不会到达u3。

注意到在模型LRM中是个自由变量，为了让其对环境给出的外部奖励信息建模，作者使用在上的经验期望来估计。

使用Tabu Search搜索一个Perfect RM

现在介绍一种特定的优化技术来解决LRM。作者检验了若干方法并选择了local search算法。local search在其中是最高效的，能在限定短时间内找到高质量RMs。进一步讲，作者使用了Tabu search，一种简单而多功能的local search程序，并且具备收敛性，多次在文献中被成功应用。

在本文背景下， Tabu search从一个随机RM开始，然后每轮迭代中它评估所有的邻近RMs。定义一个RM的邻居是一个只在一个转移上不同（也就是，删除/添加一个转移，或改变它的值）的RM集合。使用LRM的目标函数对RMs进行评估。当所有邻近RMs被评估后，算法选择一个值最小的并将其设为当前RM。为避免局部最小值，Tabu search为所有曾被作为当前RM的RMs维护了一个Tabu列表。然后，当计算当前RM的邻居时，在Tabu列表中的RMs被剪枝。

同时学习一个RM和Policy

实验评估

在三个部分可观察领域（Figure 1）上测试了本方法。这些都是随机领域，一个动作的结果以5%的概率随机变化。

本文测试了两个版本的LRM方法：LRM+DDQN和LRM+DQRM，都是从经验中学习一个RM，区别在于两者用于学习policy的方法不同。参数设置：=10，=200000，-贪婪policy的=0.1且折扣因子γ=0.9。Tabu列表大小和在找到最佳RM前的Tabu search步数为100。

本文比较了4个baseline：DDQN、A3C、ACER、PPO。Figure 3展示了每个方法每10000步训练所获的累积总奖励，并且加上一个最佳policy进行比较。LRM方法显著优胜于其他方法，在前两个领域达到接近最优policy的表现。LRM+DQRM比LRM+DDQN学习速度更快，但也更不稳定。在2-keys中，LRM+DQRM比LRM+DDQN收敛至一个更好的policy。作者相信这是由于QRM的经验分享机制。

LRM方法表现出色的一个关键因素是Tabu search在少于100步local search下找到高质量的RMs。事实上，Tabu search在大多数情况下找到了perfect RM，尤其是在symbol domain。

讨论、局限性、潜力

局限性：在抽象水平上学习RM是高效的，但是需要忽略低阶信息；如何解决在高阶检测器L上的噪声以及如何在学习新RMs时从之前学习的policies上迁移学习是不清楚的；为一个给定环境定义一个合适的高阶检测器集合是一个挑战。

潜力：未来工作，找到方法来自动化定义L是一个重要方向。