強化學(xué)習(xí) 課件 第2章 Bandit問題

第二章Bandit問題北京大學(xué)余欣航目錄

Bandit問題多臂老虎機問題（Multi-ArmedBandit，MAB）

多臂老虎機問題是退化的MDP

多臂老虎機問題（Multi-ArmedBandit）

如何使累積獎勵最大？滿足伯努利分布：只取0（吐出硬幣）或1（未吐出硬幣）簡單策略

搖臂編號10.720.530.240.150.8最佳操作是選擇第5個搖臂期望獎勵估計表簡單策略的缺點

貪心策略（greedy）

搖臂編號10.720.530.240.150.8搖臂編號10.720.530.240.150.82期望獎勵估計表進行第1次游戲選擇5號搖臂進行操作，得到1枚硬幣

期望獎勵估計表貪心策略的缺點總是選擇當(dāng)前概率最大的搖臂進行操作，而真正中獎概率高的搖臂可能是那些當(dāng)前估計概率低的搖臂！在有限游戲次數(shù)下，是堅持在當(dāng)前中獎概率高的搖臂下操作（利用），還是嘗試別的搖臂（探索）呢？如何在探索和利用之間進行平衡，稱為探索利用困境(exploration-exploitationdilemma)探索與利用平衡生活中的探索與利用去經(jīng)常光顧的咖啡館喝咖啡（利用）嘗試去其它咖啡館，或許會喝到更喜歡的咖啡（探索）在MAB問題基礎(chǔ)上增加狀態(tài)的ContextualBandit問題經(jīng)常被用于廣告推薦Agent不斷選擇商品推送給顧客，并通過反饋判斷其喜歡什么商品只有通過不斷試驗，才能逐步了解顧客，推送準(zhǔn)確的商品但這個過程中，如果推送了顧客不喜歡的產(chǎn)品，必然會造成經(jīng)濟損失Refer:/news/201704/c9wvaAoGb39f8OBt.html生活中的探索與利用臨床試驗利用：試驗期間盡可能有效地治療患者探索：通過研究確定最佳治療方法在線廣告利用：堅持至今效果最好的廣告探索：目標(biāo)是使用點擊率收集有關(guān)廣告效果的信息生活中的探索與利用探索利用困境強化學(xué)習(xí)中，經(jīng)常會考慮另外一種設(shè)定，即先將Agent在特定的環(huán)境上訓(xùn)練好，然后再考察它的效果例如要訓(xùn)練一個玩游戲的Agent，可以先用它在電腦上訓(xùn)練很多輪，然后再看它能達到何種性能唯一目標(biāo)是在訓(xùn)練完畢之后它能拿出足夠好的表現(xiàn)而其在訓(xùn)練中的表現(xiàn)是完全不重要的！這樣的話，還需不需要exploitation？有監(jiān)督學(xué)習(xí)與強化學(xué)習(xí)的區(qū)別有監(jiān)督學(xué)習(xí)中，訓(xùn)練與測試必須嚴(yán)格分開，而評價算法的標(biāo)準(zhǔn)必須是測試誤差而非訓(xùn)練誤差強化學(xué)習(xí)中，直接針對未知環(huán)境學(xué)習(xí)最佳策略，訓(xùn)練與測試都是在同一個環(huán)境進行，訓(xùn)練誤差與測試誤差不必嚴(yán)格分開需要結(jié)合現(xiàn)實中的具體情況，去定義問題是“邊訓(xùn)練邊測試”還是“先訓(xùn)練后測試”算法的成本任何的算法都要考慮成本在“先訓(xùn)練后測試”的情形下，所考慮的成本主要是用到了多少數(shù)據(jù)例如在訓(xùn)練玩游戲的Agent時，訓(xùn)練的成本是它訓(xùn)練的輪數(shù)，而不是訓(xùn)練時它的表現(xiàn)在“邊訓(xùn)練邊測試”的情形下，所考慮的成本不只是數(shù)據(jù)的成本，也和數(shù)據(jù)的內(nèi)容有關(guān)例如在多臂老虎機問題中，訓(xùn)練的主要成本是損失的金幣玩多臂老虎機的時候，究竟是否需要考慮贏輸金幣的多少？關(guān)鍵要確定目標(biāo)！重新定義MAB問題

重新定義MAB問題在前50次模擬中，得出如下估計結(jié)果：接下來還應(yīng)該認(rèn)為各個搖臂都有相同可能是最佳搖臂嗎應(yīng)該認(rèn)為第1、2、5號搖臂更有可能是最佳搖臂搖臂編號實驗次數(shù)10.71020.51030.21040.11050.810將接下來50次試驗的機會平均分配給第1、2、5號搖臂，得到如下結(jié)果：上述結(jié)果可以認(rèn)為，第1和第5兩個搖臂更可能是最佳搖臂重新定義MAB問題搖臂編號實驗次數(shù)10.762720.582630.21040.11050.7827重新定義MAB問題將最后50次試驗機會平均分配給第1和第5號搖臂，得到如下結(jié)果：根據(jù)右表的結(jié)果可以認(rèn)為，

第5號搖臂更可能是最佳搖臂！搖臂編號實驗次數(shù)10.755220.582630.21040.11050.7952

利用的意義

反映了exploitation的基本思想利用的意義

探索與利用

探索和利用

探索率的選擇如果將其設(shè)計得太高（即更傾向于“探索”）會導(dǎo)致較少選擇“看起來是最好”的搖臂如果將其設(shè)計得太低（即更傾向于“利用”）則會導(dǎo)致不能充分探索環(huán)境以及時發(fā)現(xiàn)“最好”的搖臂應(yīng)該如何選擇探索率呢？

初步探索次數(shù)的選擇

ε遞減策略（ε-greedywithεdecayed）

Boltzmann策略

在“先訓(xùn)練再測試”的設(shè)定下，ε-greedy并不是一個高效的算法假設(shè)先對每個搖臂各試驗10次（即一共試驗了50次），得到：第1號搖臂比起第3號搖臂更有可能是最佳搖臂但是在ε-greedy算法中，并沒有體現(xiàn)出第1與第3號搖臂的不同—只要它們不是“當(dāng)前認(rèn)為最佳”的搖臂，在它們上面分配的次數(shù)就是一樣多的搖臂編號實驗次數(shù)10.71020.51030.21040.11050.810回顧上節(jié)給出的算法結(jié)果：最后不僅需要選擇一個最好的搖臂，還要盡力比較所有候選的搖臂不應(yīng)該根據(jù)搖臂能夠帶來多大的收益來對每一個搖臂分配實驗次數(shù)，而應(yīng)該根據(jù)它“有多大可能是最佳的搖臂”搖臂編號實驗次數(shù)10.755220.582630.21040.11050.7952

Boltzmann策略

Boltzmann策略

Boltzmann策略上置信界策略（UCB）UCB策略（UpperConfidenceBound）

UCB策略

UCB策略的理解

UCB策略的理解

總結(jié)

實踐案例：多臂老虎機問題策略實現(xiàn)案例簡介利用Python實現(xiàn)多臂老虎機問題的4種策略：隨機選擇、ε-greedy、Boltzmann和UCB搖臂的個數(shù)為5，真