摘要
吸取高阶知识（high-level knowledge）是加快强化学习的一个有效途径。论文研究了一种强化学习问题，其中高阶知识是以reward machines的形式存在的。reward machine是Mealy状态机（Mealy machine）的一类，使用了非马尔科夫（non-Markovian，奖励不仅依赖于当前状态，也依赖于历史状态）的奖励函数（reward function）。论文关注于一个设定，其中这种知识是不能为学习agent所用的先验知识。
论文提出了一种迭代算法，该算法对强化学习（更具体地，q-learning）中的reward machine和policy进行联合推断（joint inference）。在每轮迭代中，算法维护一个hypothesis reward machine和一个RL episode的样本。它为每个hypothesis reward machine中当前状态单独定义了一个q-function。算法使用这些q-functions来确定policy，并应用强化学习更新这些q-functions。当运用强化学习时，算法通过添加反例来更新样本。在下一轮迭代中，算法由更新后的样本推断出一个新的hypothesis reward machine。基于reward machine间的等价关系，作者在连续的迭代中转移hypothesis reward machines间的q-functions。
论文证明了这种算法几乎肯定能在趋于极限时收敛至一个最佳policy。实验表明以reward machine的形式学习高阶知识可以在强化学习中快速收敛至最佳policy。
介绍
吸取高阶知识可以帮助agent以更高效的方式探索环境。这种高阶知识可以表示成各级时间或行为的抽象概念，或抽象概念的分层。
对于许多带有稀疏且非马尔可夫的奖励的复杂任务，存在捕捉奖励函数时间结构的高阶知识。一种编写一个非马尔可夫奖励函数并将其置于标准q-learning算法中的方法是使用Mealy状态机的一类，叫作reward machine。在许多现实环境中，reward machine不是可以直接被手动生成的，通常对学习agent来说是隐含的、未知的。
论文提供了一个框架，让RL agent可以从它探索过程中推断出高阶知识，并利用这些知识对未来的探索进行有效的指导。具体地，用reward machine来表示高阶知识。论文展示了一个迭代算法，算法可以为RL（更具体地，q-learning）提供joint inference of reward machines and policies（JIRP）。
在每轮迭代中，算法维护一个hypothesis reward machine和一个RL episode的样本。它为每个hypothesis reward machine中当前状态单独定义了一个q-function。算法使用这些q-functions来确定policy，并应用强化学习更新这些q-functions。当运用强化学习时，算法通过增加反例（counterexamples）来更新样本。反例可以是奖励与当前hypothesis reward machine的奖励相矛盾的RL episodes。在下一轮迭代中，算法由更新后的样本推断出一个新的hypothesis reward machine。通过自动学习技术（automata learning techniques），更新后的样本用来推断出一个新的minimal hypothesis reward machine。论文证明了如果每个RL episode的最大长度足够长，则提出的算法几乎肯定会在趋于极限时收敛至一个的最佳policy。
算法使用了两个优化：1、定期地分批处理反例并推断新的hypothesis reward machine；2、在连续的迭代中，在两个hypothesis reward machine的等价状态中转移q-functions。
JIRP方法在所有三个场景相对于三个baseline有显著提升。三个baseline：q-learnig in augmented state space、hierarchial reinforcement learning、deep reinforcement learning with double q-learning。三个场景：自动驾驶汽车场景、office world场景、Minecraft world场景。
准备工作
马尔可夫决策过程（MDP）和Reward Machine
本文的MDP定义与传统定义不同：1）奖励函数R是定义在整个历史上的（也就是说，奖励是非马尔可夫的）；2）定义中包含了一个命题集合P和一个labeling函数L（L将各命题-也叫label组合，分配到MDP上的各个transition(s, a, s')上，如Figure 2所示） 。一个label代表了一个transition的高阶描述，足以表达一个奖励。labels由专家知识而来，这些知识是关于成功完成一个任务并被认为可以运用在agent上的。
一个trace是指一个(label sequence, reward sequence)对。
在一种有穷状态机中编码一个（非马尔可夫的）奖励可以由reward machine完成。reward machine是Mealy machine的一个特例。它以命题变量的子集作为输入，以一个实数（也就是，奖励）作为输出。当一个reward machine在它有穷状态中的一个时，它读取一个label，输出一个奖励，并且转换到下一个状态。
带Reward Machine的强化学习
在强化学习中，一个agent探索由MDP建模的环境，根据隐藏的奖励函数获得奖励。一种学习到一个最优策略的方法是tabular q-learning，其中q函数时迭代更新的。
QRM算法改进了q-learning来学习到一个最优policy，其中奖励函数被编入一个reward machine。Algorithm 1展示了QRM算法的一个episode。它维护了一个集合Q，包含每个状态v对应的q-function。在决定下一个动作时，只使用当前状态v对应的q-function（第5行）；而每一轮中，所有状态对应的q-functions都得到了更新（第9行和第13行）。
QRM算法是建立在reward已知、转移概率未知的假设上的。当在JIRP中使用QRM时，这是不适用的，且reward一定是观察到的（第8行）。
每个episode都会收集traces(λ, ρ)（第14行）并返回，这在检查被推断出的reward machine是否与环境中获得的reward一致时会用到。
JIRP
这一章介绍了一个强化学习算法，这个算法迭代地推断出（也就是，学习）一个正确的reward machine和一个最佳policy。这个pocily是关于一个给定的强化学习问题和一个提供高阶知识的labeling function。
本算法结合了一个自动学习算法（来推断hypothesis reward machines）和QRM算法。hypothesis machine和观察到的trace之间的不一致性被用以触发一个reward machine的重新训练。
JIRP算法
Algorithm 2描述了JIRP算法。
它维护了一个hypothesis reward machine，并依此运行QRM算法来学习一个最优policy。QRM是用来收集traces和更新q-functions的。只要traces和当前hypothesis reward machine是一致的，QRM就会使用hyperpothesis reward machine与环境交互。但是如果不一致（第6行），算法就会把这个trace作为反例记在样本X集合中。每当样本更新，JIRP就推断出一个新的与样本一致的最小的（也就是说，状态个数最少）reward machine（第8行）。
推断最小reward machine
任务是给定一个有穷集样本X，构造一个与X中每个trace一致的最小reward machine。作者的主要想法是随着数k的递增，生成一个命题逻辑公式序列。其中命题逻辑公式满足两条件：1）这个命题公式是可满足的当且仅当存在一个k个状态的reward machine与样本X一致；2）这个命题公式的一个可满足赋值包含了足够的信息来生成这样一个reward machine。
通过k=1开始，逐渐对k加一，直到命题公式变成可满足的。使用一个SAT求解器对其进行检查，可以得到有效的算法来推断最小reward machine。
算法优化
对Algorithm 2进一步优化，得到Algorithm 3。优化包含两部分：1）反例的分批处理；2）q-functions的转移。
反例的分批处理
频繁地推断hypothesis reward machine会造成巨大的计算代价，所以Algorithm 3把每个反例存入一个集合Xnew。每经过N（用户定义的超参数）轮episode，如果Xnew非空，则将其中的反例加入样本X，并推断一个新的hypothesis reward machine。
Q-functions的转移
在Algorithm 2中，对q-functions的重新初始化没有用到RL前面几轮迭代的经验。论文提供了一种方法，来将q-functions从之前的reward machine转移到新推断出的reward machine。转移q-functions是基于一个等价状态的概念，定义如下。
可以通过修改Hopcroft的partition refinement算法来确定等价状态对。对于每个新hypothesis reward machine的状态，查看是否有之前hypothesis reward machine的状态与之等价，若有则转移对应q-function。
案例研究
在三个场景中对比了四个方法的表现。作者用tabular q-learnning和libalf library（一个自动学习框架）实现了JIRP的原型。
三个场景：1）自动驾驶车辆场景；2）office world场景；3）Minecraft world场景。
四个方法：1）JIRP；2）QAS；3）HRL；4）DDQN。
Reference
- Xu Z , Gavran I , Ahmad Y , et al. Joint Inference of Reward Machines and Policies for Reinforcement Learning[J]. 2019.