Bandit 002|信心集合在強盜算法中有什麼作用?

Bandit 002|信心集合在強盜算法中有什麼作用?

更新於 發佈於 閱讀時間約 3 分鐘

今天繼續聊聊由Yasin Abbasi-Yadkori [1] 於2011年發表的文章,


《Improved Algorithms for Linear Stochastic Bandits》[2]。


在15頁的順間後悔分析中,


我們在B001講到上界已經替換為


「強盜算法行動在強盜參數估計得到的獎勵」


以及「強盜算法行動在真實強盜參數下的獎勵」兩者的差異。


有趣的是,這裡的「行動」已經固定為「強盜算法選擇的行動」,


所以我們只需要關心「強盜參數估計」與「真實強盜參數」之間的差異就可以。


而根據Yasin在Section 2的描述,


這裡的「強盜參數估計」只會在一個特定的「信心集合 Confidence Set」搜尋。


而對這個「信心集合 Confidence Set」的要求也很基礎,


就是要有高的機率能夠抓到「真實強盜參數」。


有了信心集合這個工具以後,


我們選取「信心集合原點」來當作橋樑,


連結「強盜參數估計」以及「真實強盜參數」。


首先,由於信心集合的基礎要求,


就是高機率可以抓住真實強盜參數,


所以「信心集合原點」與「真實強盜參數」之間的差距,


最遠就是「信心集合的半徑」。


接下來,由於強盜參數估計只會在信心集合內搜尋,


所以「強盜參數估計」與「真實強盜參數」之間的差距,


最遠也只是「信心集合的半徑」。


如此,只要我們能計算「信心集合的半徑」,


那麼瞬間後悔的大小,


就小於2倍的「信心集合的半徑」乘上「強盜算法行為的長度」。


而由於整個論證其實對「強盜參數估計」只有一個樂觀估計的要求,


所以只要我們能提出一種估計,


是樂觀而且在構造出來的信心集合內,


那麼用同樣證明邏輯都走得通。



Reference

[1] https://yasin-abbasi.github.io/

[2] https://papers.nips.cc/paper_files/paper/2011/hash/e1d5be1c7f2f456670de3d53c7b54f4a-Abstract.html

avatar-img
王啟樺的沙龍
558會員
1.8K內容數
Outline as Content
留言
avatar-img
留言分享你的想法!
王啟樺的沙龍 的其他內容
Passive Consumption(被動接收) vs. Active Reading(主動閱讀)|真正讓你進化的閱讀差在這裡 碩博士生每天都在讀論文、讀報告、讀教材, 但大多數人其實只是「看過了」,不是「讀進去了」。 讀很多卻吸收很少,記不起重點、寫不出心得, 不是你不夠努力,而是你還停
4 個關鍵洞見 + 讓你看懂中美 AI 競爭 + 若不讀,你就可能錯失整個時代的最大機遇 AI 的發展速度,真的快到讓人心驚。 我們常常以為美國在 AI 領域穩居頂尖,可現在中國的 AI 創新力好像開始迎頭趕上,這背後的原因是什麼? 若我們沒有跟上這波 AI 變革,就可能被遠遠拋在後面,錯失技
Passive Consumption(被動接收) vs. Active Reading(主動閱讀)|真正讓你進化的閱讀差在這裡 碩博士生每天都在讀論文、讀報告、讀教材, 但大多數人其實只是「看過了」,不是「讀進去了」。 讀很多卻吸收很少,記不起重點、寫不出心得, 不是你不夠努力,而是你還停
4 個關鍵洞見 + 讓你看懂中美 AI 競爭 + 若不讀,你就可能錯失整個時代的最大機遇 AI 的發展速度,真的快到讓人心驚。 我們常常以為美國在 AI 領域穩居頂尖,可現在中國的 AI 創新力好像開始迎頭趕上,這背後的原因是什麼? 若我們沒有跟上這波 AI 變革,就可能被遠遠拋在後面,錯失技