這是一篇1997年由Pendrith發(fā)表在AAAI上的一篇比較久遠的文章，讓我去看這篇論文的原因是在TD3論文中出現(xiàn)了這篇論文的reference，因此我就找了這篇文章。主要為了探究在RL中，值函數(shù)估計對bias、varience的影響。這篇文章主要是針對Varience而言的。
文章總體思路不難，觀點也很明確，主要得出了3個結(jié)論：

在RL中，過量的估計誤差會導(dǎo)致學(xué)習(xí)不穩(wěn)定。

指出了通過調(diào)節(jié)超參數(shù)的方式來處理方差問題是有問題的，特別是在noisy環(huán)境和非馬爾可夫環(huán)境中。

為了解決RL中方差較大的問題，作者提出并驗證了一種叫ccBeta的算法，用于設(shè)計合適的學(xué)習(xí)率。

Estimator Varience in RL:Theoretical Problems and Preatical Solutions

• Abstract
• Introduction
• • RL as On-line Dynamic Programming
  • Q-learning as on-line value iteration
• CTR Bias and Varience
• • CTR Bias and Varience in NMDPs
• $\beta$：Varience versus Adaptability
• • The ccBeta Algorithm
• Experimental Result
• • Simulation experiment 1
  • Simulation experiment 2
  • Experiment 3:Learning to Walk
  • The RL algorithms
• Conclusions
• 學(xué)習(xí)中的不足之處：

Abstract

在強化學(xué)習(xí)中，很多算法都需要進行估計，比如Q-learning算法中需要估計Q(s,a)。估計必然會引入bias和varience。較高的方差會導(dǎo)致學(xué)習(xí)過程不穩(wěn)定，甚至導(dǎo)致無效的學(xué)習(xí)。

為了控制估計的方差，之前廣為流傳的是用一種調(diào)節(jié)超參數(shù)的方式，比如TD($\lambda$)中的超參數(shù)$\lambda$，通過調(diào)節(jié)$\lambda$來trade-off方差(the level of estimator perturbation)和bias或者對環(huán)境改變的適應(yīng)速度(the rate of adaptation)問題。

接下來作者會用實驗證明這種說法的不正確。然后是這篇文章最有價值的地方：提出了ccBeta算法來處理估計高方差問題。并且ccBeta在實驗中的表現(xiàn)也是不錯的。

Introduction

RL as On-line Dynamic Programming

這部分主要交代了RL基于MDP的相關(guān)背景：即<S,A,R,P,E>,以及RL的目的是為了最大化累計獎賞。這部分略。

Q-learning as on-line value iteration

這部分主要介紹Q-learning算法：一種基于DP中值迭代的model-free算法。主要有one-step和n-step兩種形式。
Q-learning算法的更新基于"delta rule":
$$\begin{gathered} Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\beta {\Delta }_t \\ {\Delta }_t=r_t^{(1)}?Q(s_t,a_t) \\ {r}_t^{(1)}=r_t+\gamma \underset{a}{\max }Q(s_{t+1},a) \end{gathered}$$
(其實這就是一種軟更新的形式，$\beta$就是我們所說的學(xué)習(xí)率，一般用$\alpha$表示，但文章是用$\beta$表示的)
其中，$r_t^{(1)}$被稱為1-step corrected truncated return,簡稱1-stepCTR，也就是我們的TD目標(biāo)值。
單步CTR轉(zhuǎn)變成n步CTR：
$$\begin{gathered} r_t^{(n)}=r_t^{[n]}+{\gamma }^n\underset{a}{\max }Q(s_{t+n},a) \\ {r}_t^{[n]}=\sum _{i=0}^{n?1}{\gamma }^i{r}_{t+i} \end{gathered}$$
其中$r_t^{[n]}$被稱為uncorrected n_step truncated return,簡稱UTR。
此外，后文出現(xiàn)的CTR的長度n代表著n-step的TD算法，比如TD($\lambda$)。

CTR Bias and Varience

這一節(jié)就是摘要的第二部分
在這篇文章發(fā)表之前呢，廣為流傳的平衡bias和varience問題是通過調(diào)節(jié)CTR的長度來實現(xiàn)的：CTR越短，比如最短的是1-step算法，其方差越小，偏差越大；CTR越長，比如最長的是MC算法，其方差越大，因為實時獎勵的方差是很大的，偏差越小，因為MC是Q真值的無偏估計。
但是作者指出，這個idea是錯誤的。接下來作者通過2個實驗去證明了其錯誤性。
2個思路：

CTR較短的時候，且在任務(wù)初始時期，可能會存在高方差+高偏差的情況。CTR較長的時候，可能會存在低方差+低偏差的情況。

在非馬爾科夫決策環(huán)境下，即NMDPs，可能會存在較短的CTR的方差比較長的CTR的方差更大。

實驗如下：
①：對于思路1：

如上圖所示，這是一個4狀態(tài)1動作，獎勵為0的MDP環(huán)境。
我們可以借用RL算法中的TD算法來理解：
對于較短的CTR，選擇單步的TD算法，給出更新公式：
$$Q(s_t,a_t)=Q(s_t,a_t)+\beta (r+\gamma Q(s_{t+1},a_{t+1})?Q(s_t,a_t))$$
我們考察Q(s1,a0)，剛初始化的時候，狀態(tài)s1的動作值函數(shù)取決于狀態(tài)s2或s3的動作值函數(shù)，由于這兩個值本身自己也是估計值，因此是不準(zhǔn)確，故高偏差問題是顯然的。至于方差問題，如果S2、S3的Q值相差不小，那么就會直接導(dǎo)致Q(s1,a0)的不穩(wěn)定，即較大的方差問題。
因此，在初始時期，較短的CTR會出現(xiàn)高方差+高偏差的情況。
同理，對于較長的CTR，作者直接選用2-step，這里我們同樣用TD算法來理解，其實2-step在上圖中就相當(dāng)于MC算法了。
給出更新公式：
$$Q(s_t,a_t)=Q(s_t,a_t)+\beta (r1+\gamma r2+0?Q(s_t,a_t))$$
首先，TD目標(biāo)值本身就是$G_t$的形式，自然是無偏的，本來獎勵r是高方差的，但是由于實時獎勵為0，因此直接0方差。
因此，較長的CTR也會出現(xiàn)低方差+低偏差的情況。

最后作者指出:

當(dāng)值函數(shù)估計值全局收斂的時候，n-step CTR估計的方差取決于UTR的長度。
即：
$$i<j?r_t^{[i]}\le r_t^{[j]}?var[r_t^{(i)}]\le var[r_t^{(j)}]$$
2.對于bias/varience的trade-off是沒有具體設(shè)計方式的，也就是說對于n-step算法，n的取值是沒有標(biāo)準(zhǔn)的策略。

②：對于思路2：

CTR Bias and Varience in NMDPs

作者設(shè)計了一個非NMDPs的環(huán)境，原理也很簡單，就是不符合馬爾科夫性質(zhì)就行（指當(dāng)前狀態(tài)只取決于上個狀態(tài)，而與過去無關(guān)）。

NMDPs如上圖所示:
R($A|0$)=0
R($A|1$)=0
R($B|0$)=0（當(dāng)狀態(tài)A執(zhí)行動作0）
R($B|0$)=1（當(dāng)狀態(tài)A執(zhí)行動作1）
因為主要研究MDP環(huán)境，中間的具體分析見原文，直接給出結(jié)論：
在NMDPs中，作者發(fā)現(xiàn)1-step CTR的方差比n-step CTR的方差還要大。

總結(jié)：綜上2個實驗所述，CTR的長度（或者說超參數(shù)$\lambda$的選擇）不能作為平衡bias和varience的方式，因此不能根據(jù)CTR的長度來解決高方差問題，也就是這個說法是錯誤的。

那么如何解決高方差問題呢？

就是接下去作者引出的ccBeta算法，也是我認(rèn)為這篇文章最有價值的地方。

$\beta$：Varience versus Adaptability

在RL學(xué)習(xí)中，學(xué)習(xí)率是一個很重要的超參數(shù)，現(xiàn)在普遍的做法是窮舉比如10個值，通過不斷試錯來找到使Agent性能最佳的值，但是這種做法是很耗時的。
通常的選擇方案是：在環(huán)境適應(yīng)力(fast adaptation)和低方差的平衡中選擇。一般而言，環(huán)境適應(yīng)力越強，意味著學(xué)習(xí)率$\beta$越大，更新快，學(xué)習(xí)速率高；低方差，意味著$\beta$越小，比如Q-learning中，本來剛開始大家的Q值都是不準(zhǔn)確的，這時候你學(xué)習(xí)率太大，反而會造成值更新的不穩(wěn)定，方差就會很大。
（適應(yīng)力就是比如某個穩(wěn)定的環(huán)境下，Agent的值函數(shù)收斂至穩(wěn)定的值，當(dāng)環(huán)境突然變化，Agent的值函數(shù)收斂至另一個穩(wěn)定值的速度有多快。其就是學(xué)習(xí)速率）
作者給出了當(dāng)下2種常見的學(xué)習(xí)率處理方案以及本文提出的ccBeta算法：

衰減的學(xué)習(xí)率設(shè)置：
$$\begin{gathered} {\beta }_i=\frac{1}{i} \\ \sum _{i=1}^{\infty }{\beta }_i=\infty ,and\sum _{i=1}^{\infty }{\beta }_i^2<\infty \end{gathered}$$
（這就是隨機收斂定理）

固定學(xué)習(xí)率設(shè)置：如$\beta =0.1$。

ccBeta算法。

作者記下來分別對三種設(shè)置進行分析與實驗對比。

對于衰減的$\beta$:
根據(jù)收斂定理，這個$\beta$可以使得RL算法最終收斂，也就是能較不錯的減少方差。但是其不適用于不穩(wěn)定的環(huán)境，比如從環(huán)境中獲取的return經(jīng)常會發(fā)生變動，環(huán)境中會有噪聲等。對于穩(wěn)定的環(huán)境，這是一種最佳的算法，甚至表現(xiàn)的比ccBeta更好，但是對于變化不穩(wěn)定的環(huán)境，會導(dǎo)致算法的適應(yīng)力變?nèi)?#xff0c;值函數(shù)的更新會很慢。至于變慢的原因，在后面實驗2中會有解釋。
對于固定的$\beta$：
與衰減的$\beta$不同，它可以適應(yīng)變化的環(huán)境，對環(huán)境變化敏感，即環(huán)境發(fā)生改變，他可以立即反應(yīng)過來，較快的更新值函數(shù)。但是收斂性比穩(wěn)定環(huán)境中差一些，特別是在隨機策略下的環(huán)境中或有噪聲的環(huán)境下收斂效果更差。在這種環(huán)境下，固定$\beta$較差的收斂性會導(dǎo)致學(xué)習(xí)不穩(wěn)定。其在學(xué)習(xí)速率和降低方差之間的trade-off較難實現(xiàn)，因為學(xué)習(xí)率高的話，其方差都會較大。
Note：
①：不要將隨機環(huán)境下的探索率$?$和學(xué)習(xí)率搞混了。
②：在隨機環(huán)境或者噪聲環(huán)境中收斂效果差主要是因為，比如說在暫時穩(wěn)定的環(huán)境中，算法已經(jīng)收斂了，TSE很小。這時候，環(huán)境突然地變化使得殘差中的真值需要重新分布，故算法需要重新進行收斂，這樣的話又會產(chǎn)生新的error，使得總體的error增大。在下面的實驗二中也會論證這一點。

那么有沒有一種方法可以trade-off上述兩種方法呢，既不固定也不逐漸衰減呢？

那就是ccBeta！

The ccBeta Algorithm

ccBeta算法是針對“delta-rule”而言的：
$$\begin{gathered} {\Delta }_i\leftarrow z_i?Q_{i?1} \\ {Q}_i\leftarrow Q_{i?1}+{\beta }_i{\Delta }_i \end{gathered}$$
其中，$z_i$是第i個step $Q_i$更新的目標(biāo)值，${\Delta }_i$是第i個step的error值。
ccBeta的原理就是根據(jù)是否序列相關(guān)（自相關(guān)）來調(diào)整$\beta$。具體如下：
假設(shè)$z_i$與$Q_{i?1}$可以由一條曲線來擬合。另${\Delta }_i$為第i個step的殘差項。

當(dāng)一系列殘差項自相關(guān)時，說明每一個$Q_i$過估計或者欠估計。說明此時已經(jīng)到了訓(xùn)練的中后期或者說每一個值函數(shù)都已經(jīng)找到了正確的目標(biāo)值，只是數(shù)值上還沒接近，即值函數(shù)的估計值和目標(biāo)值在同一方向上，只是數(shù)值間相差一些，這時候只要增大$\beta$，加快更新幅度即可。

當(dāng)一系列殘差項不相關(guān)時，無序性說明這時候還是訓(xùn)練初期，$\beta$
不能過大，否則會造成值函數(shù)的更新不穩(wěn)定，即方差會很大，因此需要減小$\beta$來使得方差盡可能的小。

接下來作者給出ccBeta算法的按指數(shù)方式加權(quán)的自適應(yīng)系數(shù)$c{c}_i$以及$\beta$的設(shè)置

$$\begin{gathered} sum\_square\_er{r}_i\leftarrow K?sum\_square\_er{r}_{i?1}+{\Delta }_i^2 \\ sum\_produc{t}_i\leftarrow K?sum\_produc{t}_{i?1}+{\Delta }_i{\Delta }_{i?1} \\ c{c}_i\leftarrow \frac{sum\_produc{t}_i}{\sqrt{sum\_square\_er{r}_i?sum\_square\_er{r}_{i?1}}} \end{gathered}$$

Note:

sum_square_err和sum_product的初始值都是0，為了避免$c{c}_i$出現(xiàn)inf，令這種情況下$c{c}_i=1$。

K是一個0-1之間的數(shù)，這樣設(shè)置的好處在于：首先2個sum值都有上限，這是防止訓(xùn)練到后面sum值越來越大導(dǎo)致系數(shù)溢出。其次自相關(guān)系數(shù)會更加關(guān)注偏袒于離當(dāng)前時間點近的error值，越是時間上較早的$\Delta$值,其$\Delta$值一般越不準(zhǔn)確，通過K的衰減早期的$\Delta$就變得越來越?jīng)]影響力(這有點像被$\gamma$衰減的累計獎勵，但它衰減的是未來的)。關(guān)注當(dāng)前遺忘過去的好處在于對于不穩(wěn)定的環(huán)境（或者說noisy環(huán)境）Agent的適應(yīng)力更強。也就是說，當(dāng)新環(huán)境出現(xiàn)時，舊環(huán)境中的${\Delta }_i$相對新環(huán)境而言也是不準(zhǔn)確，應(yīng)該給予衰減，減小其參考權(quán)重。

對于${\Delta }_i$項，作者提出了一種更為魯棒的變體：$sgn({\Delta }_i)$。這么做的好處在于經(jīng)過階躍函數(shù)處理的$\Delta$在noisy環(huán)境中的表現(xiàn)更加好。作者給出的理由如下：

作者給出K=0.9是最佳實踐參數(shù)。

下面是$c{c}_i$導(dǎo)出${\beta }_i$的偽代碼以及折線圖：
$$\begin{gathered} if(c{c}_i>0):{\beta }_i\leftarrow c{c}_i?MAX\_BETA \\ else:{\beta }_i\leftarrow 0 \\ if({\beta }_i<MIN\_BETA):{\beta }_i\leftarrow MIN\_BETA \end{gathered}$$

從上述關(guān)系可知：

當(dāng)${\Delta }_i$呈現(xiàn)負(fù)的自相關(guān)或者無自相關(guān)的時候，此時error的值是正負(fù)交替，表示學(xué)習(xí)初期，從上述條件語句可以看出${\beta }_i$會很小，甚至為0，這樣就可以有效降低方差。

當(dāng)${\Delta }_i$呈現(xiàn)正的自相關(guān)，此時error是同符號的過估計或者欠估計，表示學(xué)習(xí)后期，從上述條件語句可以看出，${\beta }_i$會很大，這樣就可以加快學(xué)習(xí)，提升適應(yīng)力。

設(shè)置MAX_BETA=1.0以及MIN_BETA=0.01是最佳實踐。

作者還指出使用$c{c}_i^2$來代替$c{c}_i$去權(quán)衡${\beta }_i$值能產(chǎn)生更好地結(jié)果：更低的total square error(TSE)以及更低的varience。作者給出的理由如下：

接下來作者會進行2個實驗來證明三種$\beta$設(shè)置的對比

Experimental Result

相關(guān)設(shè)置：
K=0.9
error選擇$sgn({\Delta }_i)$
自相關(guān)系數(shù)選擇$c{c}_i$
MAX_BETA=1.0
MIN_BETA=0.01

Simulation experiment 1

這次仿真，作者安排了6組實驗，每一組實驗都是跟蹤一個在以[-0.25,+0.25]為波動上限，在0值附近上下波動（即信號均值為0）的一個信號10000個steps，并重復(fù)進行n次，檢測指標(biāo)是TSE（可用來衡量收斂特性）以及std標(biāo)準(zhǔn)差。實驗的目的是為了得出學(xué)習(xí)率的設(shè)置對估計error和估計方差的影響。實驗結(jié)果如下：

從實驗結(jié)果我們可以得出：

在穩(wěn)定環(huán)境中，衰減的$\beta$能取得最好的效果，最低的TSE以及較低的方差（標(biāo)準(zhǔn)差的平方）。

從固定的$\beta$可以看出，隨著數(shù)值增大，TSE和Std逐漸增加。

ccBeta雖然不如衰減的$\beta$來得好，但是比絕大多固定$\beta$表現(xiàn)得好，其能較好的減小方差。

Simulation experiment 2

這個仿真實驗的信號和實驗1相同，但是在400步之后加入了noisy，將輸入信號的均值從0提升到了1.0。實驗的目的是為了評估學(xué)習(xí)率對Agent適應(yīng)力的影響。
實驗結(jié)果曲線圖如下（圖中只畫了50步，噪聲在400步加入）：

從曲線圖可知：

從第一張曲線圖中，固定值的$\beta$對噪聲環(huán)境的適應(yīng)力較強；相反衰減$\beta$的適應(yīng)力很弱，更新十分緩慢，從$0\to 0.95$甚至用了9950步。這是因為我們知道學(xué)習(xí)率越低，其更新速度越慢，當(dāng)執(zhí)行到400步的時候，此時學(xué)習(xí)率為0.0025，此時讓他開始重新學(xué)習(xí)的話，其更新自然非常慢，這就解釋了為啥衰減$\beta$適應(yīng)力弱了。

從第二張曲線圖中，ccBeta對噪聲環(huán)境的適應(yīng)力也不錯，能較快的根據(jù)環(huán)境變化，將估計值達到1附近。

實驗結(jié)果統(tǒng)計如下：

其中，Steps to Crossing意思是，環(huán)境發(fā)生改變之后，Agent做出回應(yīng)，更新估計值第一次到新的一個估計值所用的步數(shù)，用來衡量適應(yīng)力。

從表中看出衰減$\beta$的適應(yīng)力很差，而且由于更新太慢，所以TSE會非常大，綜合表現(xiàn)力較差。

對于固定的$\beta$值，正如前面所說，其適應(yīng)力較強，對環(huán)境改變敏感。隨著$\beta$的提升，其適應(yīng)力增強，i.e.適應(yīng)速度加快，或者說學(xué)習(xí)速率提升。但是我們都知道$\beta$越高，其方差越大。因此固定的$\beta$難以在學(xué)習(xí)速率和降低方差上有效trade-off。

兩張表對比：

正如之前所說，固定的學(xué)習(xí)率，在噪聲環(huán)境中，其收斂效果較差，這點從TSE中可以看出，噪聲環(huán)境中的TSE顯然增加了。
4. 從表中看出ccBeta算法在噪聲環(huán)境中以不俗的適應(yīng)力超過大多學(xué)習(xí)率設(shè)置。

ccBeta算法，無論環(huán)境是否有噪聲，都能表現(xiàn)不俗。當(dāng)無噪聲的時候，其TSE和Std僅次于最優(yōu)的衰減$\beta$設(shè)置。在有噪聲的時候，其TSE僅次于固定$\beta =0.1$，其適應(yīng)力也幾乎僅次于$\beta =0.3$。換句話說，在學(xué)習(xí)速度上，其能力不凡。在降低方差上，其效果也不錯，因此ccBeta是一種可以在學(xué)習(xí)速率和降低方差上trade-off的學(xué)習(xí)率選擇方案。

Experiment 3:Learning to Walk

略

The RL algorithms

略

Conclusions

總結(jié)：

在RL中，過量的估計方差會導(dǎo)致不穩(wěn)定的學(xué)習(xí)。

之前流傳的 關(guān)于CTR長度和方差、偏差的關(guān)系是不準(zhǔn)確的，因此通過調(diào)節(jié)超參數(shù)來trade-off，來降低估計方差是有待驗證的。

ccBeta算法是一個有效控制varience的好辦法，在仿真和實際環(huán)境中都表現(xiàn)不錯。其可以在保證最小化方差的同時防止在不穩(wěn)定環(huán)境（噪聲環(huán)境）中因為適應(yīng)力較弱而使得TSE太大。這是一個可以有效trade-off學(xué)習(xí)速率和降低方差的好辦法。

ccBeta算法適用性很強，就像model-free算法一樣，和設(shè)計本身關(guān)系不大，可適用于很多算法中。

任何符合“delta rule”的算法都能在ccBeta上取得很好的表現(xiàn)。

學(xué)習(xí)中的不足之處：

對于$sgn({\Delta }_i)$代替${\Delta }_i$的理由不是很明白。

對于$c{c}_i^2$代替$c{c}_i$的理由不是很明白。

有明白的同學(xué)麻煩告知下，謝謝。

總結(jié)

以上是生活随笔為你收集整理的论文笔记之Estimator Varience in RL的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。