強(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)而言之，探索是嘗試還未嘗試過(guò)的動(dòng)作行為砸脊，而利用則是從已知?jiǎng)幼髦羞x擇下一步的動(dòng)作是偷。
探索與利用之間的如何權(quán)衡拳氢，是強(qiáng)化學(xué)習(xí)的一個(gè)基本的問(wèn)題募逞。例如在很多情況，為了獲得最佳的長(zhǎng)期策略馋评，可能需要做一些短期的犧牲放接。為了能夠獲得最佳的總體策略，往往需要收集到更多的信息留特。
有幾種方式可以達(dá)到探索的目的：
- 第一種是樸素探索(Naive Exploration)纠脾，類似
算法在一定概率基礎(chǔ)下隨機(jī)選擇一些action。
- 第二種是樂(lè)觀初始估計(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īng)顟B(tài)為基礎(chǔ)進(jìn)行前向探索芒篷。
根據(jù)搜索過(guò)程中使用的數(shù)據(jù)結(jié)構(gòu)搜变，可以將搜索分為：
依據(jù)狀態(tài)行為空間的探索(State-Action Exploration)，其針對(duì)每一個(gè)當(dāng)前的狀態(tài)针炉，以一定的算法嘗試之前該狀態(tài)下沒(méi)有嘗試過(guò)的行為挠他。
-
參數(shù)化搜索（Parameter Exploration)。直接針對(duì)策略的函數(shù)近似篡帕，此時(shí)策略用各種形式的參數(shù)表達(dá)殖侵，探索即表現(xiàn)為嘗試不同的參數(shù)設(shè)置。
其優(yōu)點(diǎn)是：得到基于某一策略的一段持續(xù)性的行為镰烧；
其缺點(diǎn)是：對(duì)個(gè)體曾經(jīng)到過(guò)的狀態(tài)空間毫無(wú)記憶拢军，也就是個(gè)體也許會(huì)進(jìn)入一個(gè)之前曾經(jīng)進(jìn)入過(guò)的狀態(tài)而并不知道其曾到過(guò)該狀態(tài)，不能利用已經(jīng)到過(guò)這個(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問(wèn)題
k-bandit問(wèn)題考慮的是如下的學(xué)習(xí)問(wèn)題：你要重復(fù)地在k個(gè)選項(xiàng)或者動(dòng)作中進(jìn)行選擇度陆。每次做出選擇后，都會(huì)得到一定數(shù)值的收益献幔，收益由你選擇的動(dòng)作決定的平穩(wěn)概率分布產(chǎn)生懂傀。目標(biāo)是在某一段時(shí)間內(nèi)最大化總收益的期望。
該問(wèn)題定義是：
- multi-bandit可以看成是由行為空間和獎(jiǎng)勵(lì)組成的元組
蜡感，動(dòng)作空間
是m個(gè)動(dòng)作（即每個(gè)arms）蹬蚁，每一個(gè)行為對(duì)應(yīng)拉下某一個(gè)拉桿恃泪。獎(jiǎng)勵(lì)
是未知的概率分布
- 在每個(gè)時(shí)間步t，智能體會(huì)選擇動(dòng)作
缚忧，然后環(huán)境將生成獎(jiǎng)勵(lì)
悟泵， 目標(biāo)為最大化累計(jì)收益
。
3闪水、后悔值（Regret）
為了方便描述問(wèn)題糕非，我們先給出幾個(gè)定義：
-
action-value
一個(gè)行為的價(jià)值等于該行為能得到的即時(shí)獎(jiǎng)勵(lì)期望，即該行為得到的所有即時(shí)獎(jiǎng)勵(lì)的平均值球榆。
-
optimal value
我們能夠事先知道哪一個(gè)bandit能夠給出最大即時(shí)獎(jiǎng)勵(lì)朽肥，那我們可以每次只選擇對(duì)應(yīng)的那個(gè)拉桿。如果用
表示這個(gè)最優(yōu)價(jià)值持钉，
表示能夠帶來(lái)最優(yōu)價(jià)值的行為衡招，則：
-
Regret
事實(shí)上我們不可能事先知道拉下哪個(gè)拉桿能帶來(lái)最高獎(jiǎng)勵(lì)，因此每一次拉桿獲得的即時(shí)獎(jiǎng)勵(lì)可能都與最優(yōu)價(jià)值
-
Total Regret
每做出一個(gè)行為始腾，都會(huì)產(chǎn)生一個(gè)后悔值,因此隨著持續(xù)的拉桿行為，將所有的后悔值加起來(lái)空执，形成總后悔值(Total Regret)：
這樣浪箭，最大化累計(jì)獎(jiǎng)勵(lì)的問(wèn)題就可以轉(zhuǎn)化為最小化總后悔值了。之所以這樣轉(zhuǎn)換辨绊，是為了描述問(wèn)題的方便奶栖，在隨后的講解中可以看到，較好的算法可以控制后悔值的增加速度门坷。而用最大化累計(jì)獎(jiǎng)勵(lì)描述問(wèn)題不夠方便直觀宣鄙。
4、Regret的推導(dǎo)
從另一個(gè)角度重寫(xiě)總后悔值默蚌。定義為到
時(shí)刻時(shí)已執(zhí)行行為
的次數(shù)冻晤，定義差距（gap）
為最優(yōu)動(dòng)作
與行為
之間的差。那么總后悔值可以這樣推導(dǎo)：
這相當(dāng)于把個(gè)行為的差距與該行為發(fā)生的次數(shù)乘起來(lái)绸吸，隨后把行為空間的所有行為的這個(gè)乘積再相加得到鼻弧，只不過(guò)這里是期望。
把總后悔值用計(jì)數(shù)和差距描述可以使我們理解到一個(gè)好的算法應(yīng)該盡量減少那些差距較大的行為的次數(shù)惯裕。不過(guò)我們并不知道這個(gè)差距具體是多少温数，因?yàn)楦鶕?jù)定義雖然最優(yōu)價(jià)值和每個(gè)行為的差距（gap）
為靜態(tài)的，但我們并不清楚這兩者的具體數(shù)值蜻势，我們所能使用的信息就是每次行為帶來(lái)的即時(shí)獎(jiǎng)勵(lì)
撑刺。那么我們?nèi)绾卫妹看涡袨榈募磿r(shí)獎(jiǎng)勵(lì)呢？
我們使用每次的即時(shí)獎(jiǎng)勵(lì)來(lái)計(jì)算得到時(shí)刻止某一行為的平均價(jià)值：
這個(gè)方法也叫蒙特卡羅評(píng)估, 以此來(lái)近似該行為的實(shí)際價(jià)值
5握玛、Total Regret的直觀理解
我們先直觀了解下不同形式的隨機(jī)策略其總后悔值隨著時(shí)間的變化曲線：
（1）對(duì)于探索方法够傍，總后悔值會(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ù)將依次介紹幾種較好的探索方法窟感。
