論文筆記 Joint Inference of Reward Machines and Policies for Reinforcement Learning

摘要

吸取高階知識（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

1. Xu Z , Gavran I , Ahmad Y , et al. Joint Inference of Reward Machines and Policies for Reinforcement Learning[J]. 2019.