【強化學習理論 66】StatisticalRL 9

這是UIUC姜楠老師開設的CS598統計強化學習（理論）課程的第六講，這一講的主要內容是Fitted Q-iteration。

原文傳送門

一、Importance sampling

1。 估計期望

當要估計

的時候，如果可以從分佈 p 中取樣，那麼可以直接把樣本上的平均函式值作為該期望的無偏估計；如果只能從另外一個分佈 q 中取樣，那麼可以使用一個調整係數

來使其仍然是一個無偏估計。這樣做的要求是 p is fully supported on q（具體定義見截圖）。這種方法叫做 importance sampling （IS）。

2。 考慮單步情形

構造一個無偏估計

考慮單步的情形，即contextual bandit問題。同時假設狀態分佈為

，獎勵範圍在

之間。假設有使用behavior policy

取樣到的的資料集

，目標是使用該資料集估計target policy下的效能

。

方式很簡單，就是選用如下estimate

它是unbiased的，根據之前的結論，使用importance weight是unbiased，即

而該importance weight可以僅使用behavior policy和target policy來計算出來

方差分析

下面來分析這種方法的方差，為了便於分析，假設behavior policy是對於各個action均勻取樣，而target policy是一個確定性策略，同時獎勵是一個確定性的常數。那麼其方差可以較為容易地推匯出來

其中

是可能動作的個數。觀察到，當 behavior policy = target policy 時，方差應該為零，而加上了 IS 之後產生了更大的方差。可以想象成只有取樣到的樣本選擇的動作和 target policy 選擇的動作相同的時候，該樣本才能用上，因此會有了一個產生與

有關的方差。

當獎勵不是確定性的常數而是在

之間的隨機變數時，方差上界為

有限樣本分析

下面考慮使用有限數目的樣本能夠使用

估計

到何種精度。使用Bernstein不等式相比於Hoeffding不等式能夠得到更緊的上界。考慮

，可以得到上界為

其中使用到的Bernstein不等式可以表述為

Weighted importance sampling

回到獎勵是確定性常數以及target policy為確定性策略的情形，在這種情況下，如果只使用和target policy一致的樣本（subsamples），那麼應該該估計的方差應該為零，但是前面介紹的 IS 方法得到的方差卻不為零。IS方法的估計為

如果分母部分為

，那麼就相當於在subsample上做估計，得到的估計方差為零；但是現在這裡分母卻不是

，而是它的期望

，這導致了估計的方差大於零。weighted importance sampling（WIS）則另外構造了下面這樣的估計方法，可以在此情況下方差為零，起到了減小方差的目的。

WIS的缺點是它是biased的，即樣本有限時，期望不等於真實數值；不過它是consistent的，即當樣本數目趨向於無窮的時候，其分佈會趨向於真實分佈。

進一步減小方差

根據前面的結果，方差和獎勵的平方有關，由此想到可以先把獎勵減去某個常數 c，然後求導相應的估計之後，再加上這個常數，由此能夠得到更小的方差

。

進一步推廣可以得到 doubly robust （DR） estimate，即使用一個估計來的

來替代前面根據先驗知識設定的

，並且期望

。

3。 考慮多步情形

無偏估計

類似地，對於多步情形（即標準的RL設定），可以得到無偏的估計

由此可以得到

per-trajectory IS estimator

觀察到第h步之後的樣本不會影響到第h步的獎勵，因此，對於第h步來說，計算IS的時候，可以把h步之後都去掉。得到

per-step IS estimator

它還可以寫成遞迴的形式，即

類似地，可以得到

DR estimator

透過遞迴的形式，可以順著遞迴地證明上述estimator是都是無偏的。

方差分析

下面分析DR estimator的方差

考慮on-policy並且測量是確定性的情形，上式可以化簡為如下形式，即Bellman equation for variance。

二、策略梯度

略。主要講了策略梯度的推導和使用baseline來減小variance，本專欄的入門系列有講，同時貼一下個人之前總結的筆記。