強(qiáng)化學(xué)習(xí)基礎(chǔ)篇（三十五）探索與利用（Exploration and Exploitation）

1、探索與利用簡(jiǎn)介

在強(qiáng)化學(xué)習(xí)中，探索（Exploration ）的目的是找到更多有關(guān)環(huán)境的信息，而利用（Exploitation）的目的是利用已知的環(huán)境信息來(lái)最大限度地提高獎(jiǎng)勵(lì)。簡(jiǎn)而言之，探索是嘗試還未嘗試過的動(dòng)作行為，而利用則是從已知?jiǎng)幼髦羞x擇下一步的動(dòng)作。

探索與利用之間的如何權(quán)衡，是強(qiáng)化學(xué)習(xí)的一個(gè)基本的問題。例如在很多情況，為了獲得最佳的長(zhǎng)期策略，可能需要做一些短期的犧牲。為了能夠獲得最佳的總體策略，往往需要收集到更多的信息。

有幾種方式可以達(dá)到探索的目的：

第一種是樸素探索(Naive Exploration)，類似 $\epsilon?greedy$ 算法在一定概率基礎(chǔ)下隨機(jī)選擇一些action。
第二種是樂觀初始估計(jì)(Optimistic Initialization)，優(yōu)先選擇當(dāng)前被認(rèn)為是最高價(jià)值的行為，除非新信息的獲取推翻了該行為具有最高價(jià)值這一認(rèn)知；
第三種是不確定優(yōu)先(Optimism in the Face of Uncertainty):，更加傾向選擇更加具有不確定性的狀態(tài)/動(dòng)作，這種方法就需要一種方法來(lái)衡量這種不確定性
第四種是概率匹配（Probability Matching): 根據(jù)當(dāng)前估計(jì)的概率分布采樣行為；
第五種是信息狀態(tài)搜索(Information State Search)，將已探索的信息作為狀態(tài)的一部分聯(lián)合個(gè)體的狀態(tài)組成新的狀態(tài)，以新狀態(tài)為基礎(chǔ)進(jìn)行前向探索。

根據(jù)搜索過程中使用的數(shù)據(jù)結(jié)構(gòu)，可以將搜索分為：

依據(jù)狀態(tài)行為空間的探索(State-Action Exploration)，其針對(duì)每一個(gè)當(dāng)前的狀態(tài)，以一定的算法嘗試之前該狀態(tài)下沒有嘗試過的行為。
參數(shù)化搜索（Parameter Exploration)。直接針對(duì)策略的函數(shù)近似，此時(shí)策略用各種形式的參數(shù)表達(dá)，探索即表現(xiàn)為嘗試不同的參數(shù)設(shè)置。

其優(yōu)點(diǎn)是：得到基于某一策略的一段持續(xù)性的行為；

其缺點(diǎn)是：對(duì)個(gè)體曾經(jīng)到過的狀態(tài)空間毫無(wú)記憶，也就是個(gè)體也許會(huì)進(jìn)入一個(gè)之前曾經(jīng)進(jìn)入過的狀態(tài)而并不知道其曾到過該狀態(tài)，不能利用已經(jīng)到過這個(gè)狀態(tài)這個(gè)信息。

為了較簡(jiǎn)單的描述各類搜索的原理，下一節(jié)將使用一種與狀態(tài)無(wú)關(guān)的Bandit來(lái)進(jìn)行講解。

2、與狀態(tài)無(wú)關(guān)的k-bandit問題

k-bandit問題考慮的是如下的學(xué)習(xí)問題：你要重復(fù)地在k個(gè)選項(xiàng)或者動(dòng)作中進(jìn)行選擇。每次做出選擇后，都會(huì)得到一定數(shù)值的收益，收益由你選擇的動(dòng)作決定的平穩(wěn)概率分布產(chǎn)生。目標(biāo)是在某一段時(shí)間內(nèi)最大化總收益的期望。

image.png

該問題定義是：

multi-bandit可以看成是由行為空間和獎(jiǎng)勵(lì)組成的元組 $<A,R>$ ，動(dòng)作空間 $A$ 是m個(gè)動(dòng)作（即每個(gè)arms），每一個(gè)行為對(duì)應(yīng)拉下某一個(gè)拉桿。獎(jiǎng)勵(lì) $\mathcal{R}^{a}(r)=\mathbb{P}[r \mid a]$ 是未知的概率分布
在每個(gè)時(shí)間步t，智能體會(huì)選擇動(dòng)作 $a_t \in A$ ，然后環(huán)境將生成獎(jiǎng)勵(lì) $r_t \sim R^{a_t}$ ，目標(biāo)為最大化累計(jì)收益 $\sum_{T-1}^{t}r_{\tau}$ 。

3、后悔值（Regret）

為了方便描述問題，我們先給出幾個(gè)定義：

action-value

一個(gè)行為的價(jià)值等于該行為能得到的即時(shí)獎(jiǎng)勵(lì)期望，即該行為得到的所有即時(shí)獎(jiǎng)勵(lì)的平均值。
$Q(a)=E[r|a]$
optimal value

我們能夠事先知道哪一個(gè)bandit能夠給出最大即時(shí)獎(jiǎng)勵(lì)，那我們可以每次只選擇對(duì)應(yīng)的那個(gè)拉桿。如果用 $V^*$ 表示這個(gè)最優(yōu)價(jià)值， $a^*$ 表示能夠帶來(lái)最優(yōu)價(jià)值的行為，則：
$V^{*}=Q\left(a^{*}\right)=\max _{a \in \mathcal{A}} Q(a)$
Regret

事實(shí)上我們不可能事先知道拉下哪個(gè)拉桿能帶來(lái)最高獎(jiǎng)勵(lì)，因此每一次拉桿獲得的即時(shí)獎(jiǎng)勵(lì)可能都與最優(yōu)價(jià)值 $V^*$ 存在一定的差距，我們定義這個(gè)差距為后悔值(regret):
$l_{t}=\mathbb{E}\left[V^{*}-Q\left(a_{t}\right)\right]$
Total Regret

每做出一個(gè)行為，都會(huì)產(chǎn)生一個(gè)后悔值,因此隨著持續(xù)的拉桿行為，將所有的后悔值加起來(lái)，形成總后悔值(Total Regret)：
$L_{t}=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right]$

這樣，最大化累計(jì)獎(jiǎng)勵(lì)的問題就可以轉(zhuǎn)化為最小化總后悔值了。之所以這樣轉(zhuǎn)換，是為了描述問題的方便，在隨后的講解中可以看到，較好的算法可以控制后悔值的增加速度。而用最大化累計(jì)獎(jiǎng)勵(lì)描述問題不夠方便直觀。

4、Regret的推導(dǎo)

從另一個(gè)角度重寫總后悔值。定義 $N_t(a)$ 為到 $t$ 時(shí)刻時(shí)已執(zhí)行行為 $A$ 的次數(shù)，定義差距（gap） $\Delta a$ 為最優(yōu)動(dòng)作 $a^*$ 與行為 $a$ 之間的差。那么總后悔值可以這樣推導(dǎo)：
$\begin{aligned} L_{t} &=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right] \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right]\left(V^{*}-Q(a)\right) \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right] \Delta_{a} \end{aligned}$
這相當(dāng)于把個(gè)行為的差距與該行為發(fā)生的次數(shù)乘起來(lái)，隨后把行為空間的所有行為的這個(gè)乘積再相加得到，只不過這里是期望。

把總后悔值用計(jì)數(shù)和差距描述可以使我們理解到一個(gè)好的算法應(yīng)該盡量減少那些差距較大的行為的次數(shù)。不過我們并不知道這個(gè)差距具體是多少，因?yàn)楦鶕?jù)定義雖然最優(yōu)價(jià)值 $V^*$ 和每個(gè)行為的差距（gap） $\Delta a$ 為靜態(tài)的，但我們并不清楚這兩者的具體數(shù)值，我們所能使用的信息就是每次行為帶來(lái)的即時(shí)獎(jiǎng)勵(lì) $r$ 。那么我們?nèi)绾卫妹看涡袨榈募磿r(shí)獎(jiǎng)勵(lì)呢？

我們使用每次的即時(shí)獎(jiǎng)勵(lì)來(lái)計(jì)算得到 $t$ 時(shí)刻止某一行為的平均價(jià)值：
$\hat{Q}_{t}(a)=\frac{1}{N_{t}(a)} \sum_{t=1}^{T} r_{t} \mathbf{1}\left(a_{t}=a\right)$
這個(gè)方法也叫蒙特卡羅評(píng)估, 以此來(lái)近似該行為的實(shí)際價(jià)值 $Q(a):$ $\hat{Q}_{t}(a) \approx Q(a)$

5、Total Regret的直觀理解

我們先直觀了解下不同形式的隨機(jī)策略其總后悔值隨著時(shí)間的變化曲線：

image.png

（1）對(duì)于 $\epsilon?greedy$ 探索方法，總后悔值會(huì)呈線性增長(zhǎng)，這是一個(gè)好的算法所不能接受的。這是因?yàn)槊恳粋€(gè)時(shí)間步，該探索方法有一定的幾率選擇最優(yōu)行為，但同樣也有一個(gè)固定小的幾率采取完全隨機(jī)的行為，如采取隨機(jī)行為，那將一直會(huì)帶來(lái)一定后悔值，如果持續(xù)以雖小但卻固定的幾率采取隨機(jī)行為，那么總的后悔值會(huì)一直遞增，導(dǎo)致呈現(xiàn)與時(shí)間之間的線性關(guān)系。類似的softmax探索方法與此類似。

（2）對(duì)于greedy探索方法，其總后悔值也是線性的，這是因?yàn)樵撎剿鞣椒ǖ男袨檫x擇可能會(huì)鎖死在一個(gè)不是最佳的行為上。

（3）目標(biāo)就是找到一種探索方法，使用該探索方法時(shí)隨著時(shí)間的推移其總后悔值增加得越來(lái)越少，后續(xù)將依次介紹幾種較好的探索方法。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

強(qiáng)化學(xué)習(xí)基礎(chǔ)篇（三十五）探索與利用（Exploration and Exploitation）