8-探索與開發(fā)（Exploration and Exploitation）

1.導(dǎo)論

探索與開發(fā)二難問題

基于決策的決策過程存在以下兩種選擇

開發(fā)：基于目前的學(xué)習(xí)做最優(yōu)的決策
探索：獲取更多的學(xué)習(xí)

最佳的長期策略或許會包含一些短期的犧牲
獲取足夠的信息更能得到最為全面的決策

探索的方案（Approach to Exploration）

隨機探索（Randon exploration）

通過隨機動作進(jìn)行探索（如(epsilon-Greedy, softmax)）

基于不確定性的最優(yōu)解

先估計各種價值的不確定性
然后優(yōu)先選擇最高不確定性的狀態(tài)與動作

信息狀態(tài)空間

將智能體agent的信息也作為狀態(tài)部分之一
前向觀察看看得到的信息對回報有沒有幫助

狀態(tài)-動作探索與參數(shù)探索

狀態(tài)-動作探索（Sate-action exploration）

系統(tǒng)性地對狀態(tài)/動作空間進(jìn)行探索
例如在每次到達(dá)(S)選擇不同的動作(A)

參數(shù)探索（Parameter exploration）

存在參數(shù)策略(pi(A|S,mathbf u))
例如，每次都選擇不同的參數(shù)然后測試一下
好處在于：可持續(xù)性的探索行為
劣勢在于：不能獲知狀態(tài)/動作空間（即事實上并非因為信息增益而走出了這一步）

因此我們重點在于狀態(tài)-動作探索

2.多臂老（和諧）虎（和諧）機問題(Multi bandit）

對于一個多臂老（和諧）虎（和諧）機模型是一個元組(langle mathcal{A,R}angle)
(mathcal{A})是一個已知的動作序列（”搖臂“）
(mathcal{R^a}(r)=mathbb{P}[R=r|A=a])則是一個未知的回報概率分布
對于每一步(t)，智能體agent會選擇一個動作(A_tinmathcal{A})
然后環(huán)境在生成一個回報(R_tsimmathcal{R^{A_t}})
目標(biāo)在于最大化累計回報(sum^t_{r=1}R_r)

**可以看作一個單步MDP模型

分析

對于一個動作-價值是對于動作(a)的一個均值回報

[q(a)=mathbb{E}[R|A=a]
]

對于最優(yōu)價值(v_*)則是

[v_*=q(a^*)=max_{ainmathcal{A}}q(a)
]

對于悔數(shù)（Regret）則是對于每一步的機會損失（opportunity loss）

[l_t=mathbb{E}[v_*-q(A_t)]
]

總的悔數(shù)則是總的機會損失

[L_t = mathbb{E}igg[sum^t_{ au=1}v_*-q(A_ au)igg]
]

最大化累計回報(equiv)最小化總悔數(shù)

計算悔數(shù)（Counting Regret）

對于計數(shù)(N_t(a))是對于選擇動作(a)的期望

對于間隔（gap）(Delta_a)是動作(a)與最優(yōu)動作(a^*)的價值之差，(Delta_a = v_*-q(a))

悔數(shù)則是與間隔與計數(shù)相關(guān)的函數(shù)

[egin{align}
L_t & = mathbb{E}igg[sum^t_{ au=1}v_*-q(A_{ au})igg] \
& = sum_{ainmathcal{A}}mathbb{E}[N_t(a)](v_*-q(a)) \
& = sum_{ainmathcal{A}}mathbb{E}[N_t(a)]Delta_a
end{align}
]

對于一個性質(zhì)良好的算法可以確保小計數(shù)量就可以得到大的間隔

問題在于間隔乃是未知的！

貪心算法（Greedy Algorithm）

我們認(rèn)定算法中存在近似關(guān)系(Q_t(a)approx q(a))

然后通過蒙特卡羅評估去估計每一次動作的價值

[Q_t(a) = frac{1}{N_t(a)}sum^T_{t=1}mathbf1(A_t=a)R_t
]

貪心算法選擇最高價值的動作

[A_t=mathop{argmax}_{ainmathcal{A}}Q_t(a)
]

為此貪心算法（因為其完全不探索）使得其局限于局部最優(yōu)解動作中

為此貪心算法的總悔數(shù)函數(shù)是呈線性的

最優(yōu)初始化的貪心算法（Greedy Algorithm with optimistic initialisation）

將價值初始化為最大值即(Q(a)=f_max)

然后運行貪心算法的行為：

[A_t=mathop{argmax}_{ainmathcal{A}}Q_t(a)
]

鼓勵去探索未知的價值

同樣也存在一些情況會使得其無法找到最優(yōu)解動作

同樣最優(yōu)初始化貪心算法也是線性悔數(shù)

主要思想：未知價值的動作高階于已知價值的動作

(epsilon-Greedy)算法

對于(epsilon-Greedy)一直保持探索狀態(tài)

對于(1-epsilon)的概率選擇

[A_t=mathop{argmax}_{ainmathcal{A}}Q_t(a)
]

對于(epsilon)的概率會選擇一個隨機動作

但是(epsilon-Greedy)同樣會是線性的總悔數(shù)

跟Softmax探索差不多

衰變(epsilon-Greedy)算法（Decaying (epsilon-Greedy) Algorithm）

我們?yōu)?epsilon_1,epsilon_2)去加入一個衰變的新方式

如下所示;

[egin{align}
c & > 0 \
d & = min_{a|Delta_a>0}Delta_a \
epsilon_t & = minigg{1,frac{c|mathcal{A}|}{d^2t}igg}
end{align}
]

衰變(epsilon-greedy)算法對數(shù)漸近的總悔數(shù)

不過不幸的是，這種衰變形式需要提前知道間隔

目標(biāo)：找到一個在多臂老（和諧）虎（和諧）機上具有近似于線性總悔數(shù)的算法（一開始對于(mathcal{R})是一無所知的）

算法的表現(xiàn)主要取決于最優(yōu)搖臂以及其他搖臂的差距

最復(fù)雜的問題就是相似的搖臂但是有多個均值

主要是用間隔(Delta_a)以及分布的相似度（KL散度）：(KL(mathcal{R^a|R^(a^*)}))

黎·拉賓氏定理（Lai and Robbins）**黎氏：黎子良（Tze Leung Lai）香港美籍科學(xué)家

對于漸近總悔數(shù)其下界至少是與步數(shù)呈對數(shù)增長

[lim_{tightarrowinfin} L_t ge log t sum_{a|Delta > 0}frac{Delta_a}{KL(mathcal{R^a|R^{a^*}})}
]

上確信界（Upper Confidence Bounds）

為每個動作價值估算一個上確信界(U_t(a))

例如說(q(a)le Q_t(a) + U_(a))就具有較高的概率

這主要取決于計數(shù)(N(a))的取值

如果是小的(N_t(a))情況下(ightarrow)具有較大的(U_t(a))（這么說估計價值是不確定的）
如果是大的(N_t(a))情況下(ightarrow)具有較小的(U_t(a))（這么說估計價值是精確的）

為此我們選擇上確信界（UCB）最大的動作

[A_t = mathop{argmax}_{ainmathcal{A}}Q_t(a) + U_t(a)
]

霍夫丁不等式（Hoeffding;s Inequality）

使(X_1,dots,X_t)是符合(i.i.d.)條件的處于區(qū)間([0,1])隨機變量，并且使得(overline X_t = frac{1}{ au}sum^t_{ au=1}X_ au)作為采樣均值。然后：

[mathbb{P}[mathbb{E}[X]>overline X_t + u]le e^{-2tu^2}
]

我們將會把霍夫丁不等式應(yīng)用于老（和諧）虎（和諧）機問題的回報

由選擇動作作為條件

[mathbb{P}[q(a)>Q_t(a) + U_t(a)] le e^{-2N_t(a)U_t(a)^2}
]

解決上確信界（Solving Upper Confidence Bounds）

求出真實價值超出(UCB)的概率(p)

開始求解(U_t(a))

[egin{align}
e^{-2N_t(a)U_t(a)^2} & = p \
U_t(a) & = sqrt{frac{-log p}{2N_t(a)}}
end{align}
]

當(dāng)我們對回報的觀測越多，(p)就會降低，例如說(p = t^{-4})

確保我們在(tightarrow infin)時每次選擇最優(yōu)動作

[U_t(a) = sqrt{frac{2log t}{N_t(a)}}
]

為此引出了(UCB1)算法（還有很多形式可供嘗試）

[A_t = mathop{argmax}_{ainmathcal{A}}igg(Q_t(a) + sqrt{frac{2log t}{N_t(a)}}igg)
]

為此(UCB)算法成功達(dá)到了對數(shù)漸近總悔數(shù)

[lim_{tightarrowinfin}L_tle 8log tsum_{a|Delta_a > 0}Delta_a
]

更多的上確信界形式

上確信界也可以用其他不等式去表示

伯恩斯坦不等式（bernstein's inequality）
經(jīng)驗伯恩斯坦不等式（Empirical Bernstein's inequality）
車爾諾夫不等式（Chernoff inequality）
奧茲瑪不等式（Azuma's inequality）
...

貝葉斯老（和諧）虎（和諧）機（Bayesian bandits）

貝葉斯老（和諧）虎（和諧）機顯式地利用了以往關(guān)于回報的學(xué)習(xí)，即(p[mathcal{R^a}])

我們定義一個帶有參數(shù)(mathbf w)關(guān)于動作-價值函數(shù)分布(p[Q|mathbf w])

例如說多組獨立的高斯分布(mathbf w = [mu_1,sigma_1^2,dotsmu_k,sigma^2_k])對于所有的(ain[1,k])

貝葉斯方法在于計算后來的關(guān)于(mathbf w)的分布

[p[mathbf w | R_1,dots,R_t]
]

通過后來的數(shù)據(jù)來制導(dǎo)探索進(jìn)程

上確信界
概率匹配（Probability Matching）

前置信息越精確，那么算法性能越好

基于上確信界的貝葉斯老（和諧）虎（和諧）機（Bayesian Bandits with Upper Confidence Bounds）

通過貝葉斯定律計算前置(p[mathbf w|R_1,dots R_{t-1}])

計算動作-價值的后置分布

(p[Q(a)|R_1,dots R_{t-1}]=p[Q(a)|mathbf w]p[mathbf w|R_1,dots,R_{t-1}])

然后估計后置狀態(tài)的上確信界，如(U_t(a)=csigma(a))

其中(sigma(a))是(p(Q(a)|mathbf w))的標(biāo)準(zhǔn)差

然后選擇動作以讓(Q_t(a) + csigma(a))最大化

概率匹配（Probability Matching）

概率匹配基于(a)是最優(yōu)動作的概率去選擇動作

[pi(a)=mathbb{P}igg[Q(a) =max_{a'}Q(a')|R_1,dots,R_{t-1}igg]
]

概率匹配在于未確定下方面也是充分樂觀的

對于不確定性的動作有更高的可能性成為最大值

但是解析性地計算后續(xù)狀態(tài)的(pi(a))比較困難

辛普森采樣（Thompson Sampling）

辛普森采樣屬于一種基于采樣的概率匹配

[pi(a)=mathbb{E}igg[mathbf 1(Q(a)=max_{a'}Q(a'))|R_1,dots,R_{t-1}igg]
]

然后通過貝葉斯定律去計算后續(xù)分布

[p_mathbf w(Q|R_1,dots,R_{t-1})
]

從前驅(qū)狀態(tài)去采用一個動作-價值函數(shù)(Q(a))

然后通過最大化采樣去選擇動作

[A_t = mathop{argmax}_{ainmathcal{A}}Q(a)
]

對于伯努利老（和諧）虎（和諧）機，辛普森采樣成功達(dá)到了黎氏與拉賓氏最低悔數(shù)下界

價值信息（Value Information）

探索之所以好用乃是因為其增長了信息
那么我們可以去量化信息的價值嗎？

多少回報對于一個決策器會準(zhǔn)備去付出代價去探索獲取其信息，而不著急于決策
獲取信息后的長期回報與短期回報（瞬間回報）的對比

在不確定性的情況下，顯然信息增益更為重要
為此在未知情況下進(jìn)行探索更為合理
當(dāng)我們知道了信息的價值之后，我們就能最優(yōu)地權(quán)衡探索與開發(fā)了

信息狀態(tài)空間（Information State Space）

我們已經(jīng)將老（和諧）虎（和諧）機問題視為一步?jīng)Q策問題了

同樣也可以視為序列決策問題

每一步都存在一個信息狀態(tài)(overline{S})把過去所有的信息累計起來

對于每個動作(A)會引出一個狀態(tài)轉(zhuǎn)移到達(dá)新的一個信息狀態(tài)(overline{S'})（通過信息加和），基于概率(overline{P}^A_{overline{S},overline{S}'})

為此現(xiàn)在我們就擁有了一個增強信息狀態(tài)空間的(MDP mathcal{overline{M}})

[mathcal{overline{M}}=langle overline{S}, mathcal{A},mathcal{overline{P}},mathcal{R},gammaangle
]

伯努利老（和諧）虎（和諧）機（Bernoulli Bandit）

我們定義伯努利老（和諧）虎（和諧）機即：(mathcal{R^a}=mathcal{B}(mu_a))
例如說：藥動力學(xué)成功的概率就有(mu_a)
欲找出最高(mu_a)的搖臂
因此信息空間為(overline{S}=langlealpha, etaangle)

(alpha_a)計數(shù)了拉取搖臂(a)然后其回報為0
(eta_a)計數(shù)了拉取搖臂(b)然后其回報為1

信息狀態(tài)空間老（和諧）虎（和諧）機（Information State Space Bandits）

我們通過一個關(guān)于信息狀態(tài)的無窮MDP來方程化這個老（和諧）虎（和諧）機
這個MDP顯然可以用強化學(xué)習(xí)解決
無模型強化學(xué)習(xí)（Model-free reinforcement learning）

例如：Q-learning（Duff，1994）

基于貝葉斯模型的強化學(xué)習(xí)

例如：吉丁斯指標(biāo)（Gittins indices）（Gittins，1979）

后來的方法一般被認(rèn)為是適應(yīng)于貝葉斯的強化學(xué)習(xí)
尋找關(guān)于先前分布的探索/開發(fā)貝葉斯最優(yōu)解

適應(yīng)于貝葉斯的伯努利老（和諧）虎（和諧）機（Bayes-adaptive Bernoulli Bandits）

從關(guān)于回報函數(shù)(mathcal{R^a})的(Beta(alpha_a,eta_a))開始

每一次時間選擇動作(a)，然后更新后續(xù)的(mathcal{R^a})

(Beta(alpha_a + 1,eta))若回報為0
(Beta(alpha_a,eta_a+1))若回報為1

如此就得以為適用于貝葉斯的MDP了一個狀態(tài)轉(zhuǎn)移函數(shù)(mathcal{overline{P}})

對于所有的信息狀態(tài)((alpha,eta))代表著一個模型(Beta(alpha,eta))

而每次狀態(tài)轉(zhuǎn)移則代表一個貝葉斯模型的更新

求解適用于貝葉斯的MDP需要考慮到價值信息

因為新信息的影響會作為因子影響到模型更新中

更多拓展

在伯努利的問題中，適用于貝葉斯的MDP可以直接通過動態(tài)規(guī)劃解決

這種解法正是被稱之為吉丁斯索引（Gittins index）

但是精確來說解決一個適用于貝葉斯的MDP是有點麻煩的

近來的方法已經(jīng)可以做到探索大規(guī)模規(guī)劃了

（例如蒙特卡羅樹搜索算法）

供以構(gòu)造一顆前向樹然后尋找貝葉斯從最開始的學(xué)習(xí)狀態(tài)的最優(yōu)探索與開發(fā)權(quán)衡

解決多臂老（和諧）虎（和諧）機的總算法

隨機探索

(epsilon-Greedy)
(Softmax)
高斯噪音

基于不確定性的最樂觀情況（當(dāng)未知狀態(tài)太多時容易陷入無窮狀態(tài)）

最優(yōu)初始化
確信上界
辛普森采樣

學(xué)習(xí)狀態(tài)空間

吉丁斯指標(biāo)
適用于貝葉斯的MDP

上下文式老（和諧）虎（和諧）機

對于一個上下文式老（和諧）虎（和諧）機定義為元組(langle mathcal{A, color{red}{S},R} angle)
(mathcal{A})為一個已知的動作集（或者稱為搖臂）
(mathcalcolor{red}{S}=mathbb{P}[mathcal{S}])則為一個關(guān)于狀態(tài)（或者稱為上下文）相關(guān)的未知分布
(mathcal{R^a_color{red}{s}}(r)=mathbb{P}[R=r|color{red}{S=s},A=a])則為一個關(guān)于回報未知的概率分布
對于每一步(t)

環(huán)境產(chǎn)生狀態(tài)(S_tsim mathcal{S})
智能體選擇動作(A_tinmathcal{A})
環(huán)境產(chǎn)生回報(R_tinmathcal{R^{A_t}_{S_t}})

目標(biāo)是最優(yōu)化累計回報(sum^t_{r=1}R_r)

馬爾科夫決策過程

上確信界的馬爾科夫決策過程

對于UCB法也能應(yīng)用于整個MDPs
然后給出一個無模型的強化學(xué)習(xí)算法
最大化動作-價值函數(shù)中的上確信界

[A_t=mathop{argmax}_{ainmathcal{A}}Q(S_t,a)+U(S_t,a)
]

其中有一個較成功的方法去解決無模型強化學(xué)習(xí)的探索與開發(fā)

首先構(gòu)造一個MDP模型
對于未知或者是知道極少的狀態(tài)，直接用(r_max)去取代他的回報函數(shù)
即是：非常樂觀地面對不確定性
通過你喜歡的算法解決這個樂觀MDP即可

策略迭代
價值迭代
樹形搜索
...

例如說 Rmax算法

適用于貝葉斯的MDP

MDPs同樣可以通過信息狀態(tài)來增強

現(xiàn)在增強過的狀態(tài)為(overline{S}=langle S,Iangle)

其中(S)是MDP的原狀態(tài)
其中(I)是累計的信息

適用于貝葉斯的方法得到了一個后繼狀態(tài)模型代表著每個已經(jīng)被增強過的狀態(tài)(mathbb{P}[mathcal{P,R}|I])

求解適用于貝葉斯的MDP去尋找最優(yōu)探索開發(fā)權(quán)衡必須關(guān)系與前驅(qū)狀態(tài)

然而增強MDP一般來說都較為龐大

蒙特卡羅樹形搜索在這里就被證明比較高效了（Guez等人的工作）

進(jìn)階的來說還有更多用來安排探索與開發(fā)的復(fù)雜方法

隨機探索
樂觀不確定性
學(xué)習(xí)狀態(tài)空間

總結(jié)

以上是生活随笔為你收集整理的机器学习 | 强化学习（8） | 探索与开发（Exploration and Exploitation）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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