這篇《Fast Counterfactual Inference for History-Based Reinforcement Learning》提出一種快速因果推理算法，使得因果推理的計算復雜度大幅降低——降低到可以和online 強化學習相結合的程度。

?本文理論貢獻主要有兩點：

?1、提出了時間平均因果效應的概念；

2、將著名的后門準則從單變量干預效應估計推廣到多變量干預效應估計，稱之為步進后門準則。

背景

需要準備關于部分可觀測強化學習和因果推理的基礎知識。這里不做過多介紹，給幾個傳送門吧：

部分可觀測強化學習：

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

因果推理：

深度神經網絡中的因果推理 https://zhuanlan.zhihu.com/p/425331915

動機

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

然而，這些方法不能消除由采樣導致的混雜相關性。舉一個撿鑰匙開門的例子，如下圖所示：

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

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

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

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

困難

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

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

[2]注：單變量干預因果效應的正式定義如下

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

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

思路

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

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

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

方法

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

步進后門調整準則(step-backdoor adjustment formula)

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

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

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

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

具體到部分可觀測強化學習問題上，用觀測o替換上式的x后，有如下因果效應計算公式：

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

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

算法結構圖如下

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

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

驗證

實驗上驗證了三個點，回應了前面的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? 詳見論文的實驗章節(jié)，這里就不占用篇幅了。當然，有興趣的小伙伴還可私信我/評論哦。

未來可拓展的方向

說兩點，以拋磚引玉：

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

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