這篇《Fast Counterfactual Inference for History-Based Reinforcement Learning》提出一種快速因果推理算法，使得因果推理的計(jì)算復(fù)雜度大幅降低——降低到可以和online 強(qiáng)化學(xué)習(xí)相結(jié)合的程度。

?本文理論貢獻(xiàn)主要有兩點(diǎn)：

?1、提出了時(shí)間平均因果效應(yīng)的概念；

2、將著名的后門準(zhǔn)則從單變量干預(yù)效應(yīng)估計(jì)推廣到多變量干預(yù)效應(yīng)估計(jì)，稱之為步進(jìn)后門準(zhǔn)則。

背景

需要準(zhǔn)備關(guān)于部分可觀測強(qiáng)化學(xué)習(xí)和因果推理的基礎(chǔ)知識。這里不做過多介紹，給幾個(gè)傳送門吧：

部分可觀測強(qiáng)化學(xué)習(xí)：

POMDP講解 https://www.zhihu.com/zvideo/1326278888684187648

因果推理：

深度神經(jīng)網(wǎng)絡(luò)中的因果推理 https://zhuanlan.zhihu.com/p/425331915

動(dòng)機(jī)

從歷史信息中提取/編碼特征是解決部分可觀測強(qiáng)化學(xué)習(xí)的基本手段。主流方法是使用sequence-to-sequence（seq2seq）模型來編碼歷史，比如領(lǐng)域內(nèi)流行使用的LSTM/GRU/NTM/Transformer的強(qiáng)化學(xué)習(xí)方法都屬于這一類。這一類方法的共同之處在于，根據(jù)歷史信息和學(xué)習(xí)信號（環(huán)境獎(jiǎng)勵(lì)）的相關(guān)性來編碼歷史，即一個(gè)歷史信息的相關(guān)性越大所分配的權(quán)重也就越高。

然而，這些方法不能消除由采樣導(dǎo)致的混雜相關(guān)性。舉一個(gè)撿鑰匙開門的例子，如下圖所示：

在這里agent能否開門只取決于歷史上是否有拿到過鑰匙，而不取決于歷史上的其他狀態(tài)。然而，如果agent的采樣策略是對一些路徑有偏好的，就會(huì)導(dǎo)致這些偏好路徑上的狀態(tài)具有高相關(guān)性。比如agent拿到鑰匙之后，傾向于走 （上面那條路）開門而不是走 去開門（下面那條路）的話，就會(huì)使得開門這件事情和電視機(jī)有很高的相關(guān)性。這一類非因果但高度相關(guān)的狀態(tài)就會(huì)被seq2seq賦予比較高的權(quán)重，使得編碼的歷史信息非常冗余。在這個(gè)例子里，當(dāng)我們估計(jì)電視機(jī)和開門之間的相關(guān)性時(shí)，由于鑰匙的存在，兩者產(chǎn)生了混雜的高相關(guān)性。要估計(jì)電視機(jī)對開門的真實(shí)效應(yīng)，就要去除這種混雜的相關(guān)性。

這種混雜相關(guān)性可以通過因果推理中的do-calculus來去除[1]：分離可能造成混淆的后門變量鑰匙和球，從而切斷后門變量（鑰匙/球）和電視機(jī)之間的統(tǒng)計(jì)相關(guān)性，然后將p(Open| ，鑰匙/球)的條件概率關(guān)于后門變量（鑰匙/球）進(jìn)行積分（Figure 1右圖），得到真實(shí)的效應(yīng)p(Open|do( ))=0.5。由于有因果效應(yīng)的歷史狀態(tài)相對稀疏，當(dāng)我們?nèi)コ祀s的相關(guān)性以后，可以大幅壓縮歷史狀態(tài)的規(guī)模。

因此，我們希望用因果推理來去除歷史樣本中混雜的相關(guān)性，然后再用seq2seq來編碼歷史，從而獲得更緊湊的歷史表征。（本文動(dòng)機(jī)）

[1]注：這里考慮的是使用后門調(diào)整的do-calculus，附一個(gè)科普鏈接https://blog.csdn.net/qq_31063727/article/details/118672598

困難

在歷史序列中執(zhí)行因果推理，不同于一般的因果推理問題。歷史序列中的變量既有時(shí)間維也有空間維，即觀測-時(shí)間組合,其中o是觀測，t是時(shí)間戳（相比之下MDP就很友好了，馬爾可夫狀態(tài)只有空間維）。兩個(gè)維度的交疊，使得歷史觀測的規(guī)模相當(dāng)龐大——用表示每個(gè)時(shí)間戳上的觀測取值個(gè)數(shù)，用T來表示時(shí)間總長度，則歷史狀態(tài)的取值有 種（其中正體O( )為復(fù)雜度符號）。[2]

以往的因果推理方法基于單變量干預(yù)檢測，一次只能do一個(gè)變量。在具有龐大規(guī)模的歷史狀態(tài)上進(jìn)行因果推理，將造成極高的時(shí)間復(fù)雜度，難以和online RL算法相結(jié)合。

[2]注：單變量干預(yù)因果效應(yīng)的正式定義如下

如上圖所示，給定歷史  ，要估計(jì)對轉(zhuǎn)移變量 的因果效應(yīng)，做以下兩步：1）干預(yù)歷史狀態(tài)do ，2）以先前的歷史狀態(tài) 為后門變量，為響應(yīng)變量，計(jì)算如下積分即為所要求取的因果效應(yīng)

既然單變量干預(yù)檢測難以和online RL相結(jié)合，那么開發(fā)多變量干預(yù)檢測方法就是必須的了。

思路

本文的核心觀察（假設(shè)）是，因果狀態(tài)在空間維上稀疏。這個(gè)觀察是自然而普遍的，比如拿鑰匙開門，過程中會(huì)觀測到很多狀態(tài)，但鑰匙這個(gè)觀測值才決定了是否能開門，這個(gè)觀測值在所有觀測取值中占比稀疏。利用這個(gè)稀疏性我們可以通過多變量干預(yù)一次性就篩除掉大量沒有因果效應(yīng)的歷史狀態(tài)。但是時(shí)間維上因果效應(yīng)并不稀疏，同樣是拿鑰匙開門，鑰匙可以被agent在絕大部分時(shí)刻都觀測到。時(shí)間維上因果效應(yīng)的稠密性會(huì)妨礙我們進(jìn)行多變量干預(yù)——無法一次性去除大量沒有因果效應(yīng)的歷史狀態(tài)。

基于上述兩點(diǎn)觀察，我們的核心思路是，先在空間維上做推理，再在時(shí)間維上做推理。利用空間維上的稀疏性大幅減少干預(yù)的次數(shù)。為了單獨(dú)估計(jì)空間因果效應(yīng)，我們提出先求取時(shí)間平均因果效應(yīng)，就是把多個(gè)歷史狀態(tài)的因果效用在時(shí)間上進(jìn)行平均（具體定義請見原文）。

基于這個(gè)idea，我們將問題進(jìn)行聚焦：要解決的核心問題是如何計(jì)算干預(yù)多個(gè)不同時(shí)間步上取值相同的變量(記作)的聯(lián)合因果效應(yīng)。這是因?yàn)?strong>后門準(zhǔn)則不適用于多個(gè)歷史變量的聯(lián)合干預(yù)：如下圖所示，考慮聯(lián)合干預(yù)雙變量和，可以看到，時(shí)間步靠后的的一部分后門變量里包含了，兩者不存在公共的后門變量。

方法

我們改進(jìn)后門準(zhǔn)則，提出一個(gè)適用于估計(jì)多變量聯(lián)合干預(yù)效應(yīng)估計(jì)的準(zhǔn)則。對于任意兩個(gè)被干預(yù)的變量 和 (i<j)，我們給出用于估計(jì)它們的聯(lián)合干預(yù)效應(yīng)的準(zhǔn)則，如下

步進(jìn)后門調(diào)整準(zhǔn)則(step-backdoor adjustment formula)

該準(zhǔn)則分離了，介于相鄰兩個(gè)時(shí)間步的變量之間的其他變量，稱為步進(jìn)后門變量。在滿足這個(gè)準(zhǔn)則的因果圖中，我們可以估計(jì)任意兩個(gè)被干預(yù)變量的聯(lián)合因果效應(yīng)。包括兩步：step 1、以時(shí)間步上小于i的變量作為后門變量，估計(jì)do因果效應(yīng)；step 2、以取定的后門變量和取定的為條件，以介于和之間的變量為新的關(guān)于的后門變量（即關(guān)于和步進(jìn)后門變量），估計(jì)do的條件因果效應(yīng)。則聯(lián)合因果效應(yīng)為這兩部分的乘積積分。步進(jìn)后門準(zhǔn)則將普通的后門準(zhǔn)則使用了兩步，如下圖所示

上式使用了更一般的變量表示符X。

對于三個(gè)變量以上的情況，通過連續(xù)使用步進(jìn)后門準(zhǔn)則——將每兩個(gè)時(shí)間步相鄰的干預(yù)變量之間的變量視作步進(jìn)后門變量，連續(xù)計(jì)算上式，可以得到多變量干預(yù)的聯(lián)合因果效應(yīng)如下：

Theorem 1. Given a set of intervened variables with different timestamps, if every two temporally adjacent variables meet the step-backdoor adjustment formula, then the overall causal effect can be estimated with

具體到部分可觀測強(qiáng)化學(xué)習(xí)問題上，用觀測o替換上式的x后，有如下因果效應(yīng)計(jì)算公式：

Theorem 2. Given and  , the causal effect of Do(o) can be estimated by

至此，論文給出了計(jì)算空間因果效應(yīng)（即時(shí)間平均因果效應(yīng)）的公式，這一段方法將干預(yù)的次數(shù)由O(）降低為O（）。接下來，就是利用（本章開頭提及）空間因果效應(yīng)的稀疏性，進(jìn)一步對干預(yù)次數(shù)完成指數(shù)級縮減。將對一個(gè)觀測的干預(yù)替換為對一個(gè)觀測子空間的干預(yù)——這是一個(gè)利用稀疏性加速計(jì)算的通常思路（請見原文）。在本文中，開發(fā)了一個(gè)稱為Tree-based history counterfactual inference （T-HCI）的快速反事實(shí)推理算法，這里不作贅述（詳見原文）。其實(shí)基于步進(jìn)后門準(zhǔn)則后續(xù)還可以開發(fā)很多歷史因果推理算法，T-HCI只是其中的一個(gè)。最后的結(jié)果是Proposition 3 (Coarse-to-fine CI). If , the number of interventions for coarse-to-fine CI is）。

算法結(jié)構(gòu)圖如下

算法包含兩個(gè)loops，一個(gè)是T-HCI loop，一個(gè)是策略學(xué)習(xí)loop，兩者交換進(jìn)行：在策略學(xué)習(xí)loop里，agent被采樣學(xué)習(xí)一定回合數(shù)量，并將樣本存在replay pool中；在T-HCI loop中，利用存儲的樣本進(jìn)行上述的因果推理過程。

Limitations：空間維上的因果推理對歷史規(guī)模的壓縮幅度已經(jīng)足夠大了。盡管時(shí)間維上做因果推理可以進(jìn)一步壓縮歷史規(guī)模，但考慮到計(jì)算復(fù)雜度需要平衡，本文在時(shí)間維上保留了相關(guān)性推理（在有空間因果效應(yīng)的歷史狀態(tài)上端到端使用LSTM），沒有使用因果推理。

驗(yàn)證

實(shí)驗(yàn)上驗(yàn)證了三個(gè)點(diǎn)，回應(yīng)了前面的claims：1) Can T-HCI improve the sample efficiency of RL methods? 2) Is the computational overhead of T-HCI acceptable in practice? 3) Can T-HCI mine observations with causal effects? 詳見論文的實(shí)驗(yàn)章節(jié)，這里就不占用篇幅了。當(dāng)然，有興趣的小伙伴還可私信我/評論哦。

未來可拓展的方向

說兩點(diǎn)，以拋磚引玉：

1、HCI不限于強(qiáng)化學(xué)習(xí)的類型。雖然本文研究的是online RL，但HCI也可自然地拓展到offline RL、model-based RL等等，甚至于可以考慮將HCI應(yīng)用于模仿學(xué)習(xí)上；

2、HCI可以視作一種特殊的hard attention方法——有因果效性的序列點(diǎn)獲注意力權(quán)值1，反之獲注意力權(quán)值0。從這個(gè)角度看，一些序列預(yù)測問題也可能嘗試使用HCI來處理。