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

今天繼續聊聊由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