Bandit 003｜如何透過擾動參數來實現最佳探索？

今天聊聊 Marc Abeille[1] 所著作的《Linear Thompson Sampling Revisited》[2]。

這篇文章是分析Linear Thompson Sampling的理論經典文章。

文章裡面示範了如何將 Thompson取樣，

看作是一種對參數的擾動，

進一步對構造擾動的噪音，

加上集中與反集中的條件 (Definition 1)，

進一步在Theorem 1 證明，

線性湯姆森取樣可以有「亞線性後悔 Sublinear Regret」。

其證明過程倚賴構造兩個集合(Definition 3)：

1-信賴集合：此集合能以高機率包含「真實強盜參數 True Bandit Parameter」

2-探索集合：此集合能以高機率包含「隨機探索強盜參數 Stochastic Exploration Bandit Parameter」。

這篇文章證明最有趣的地方在Lemma 3，

其構造了一個「樂觀參數集合 Optimistic Parameter Sets」，

設定為「探索集合」以及「樂觀集合」的交集。

探索集合，是透過算法擾動參數能探索到的區域，

而樂觀集合，則是擁有比真實強盜參數還要高的最優獎勵的區域。

而這個「樂觀參數集合」本身的機率大小有沒有下界，

是整個證明很重要的一環。

而這個「樂觀參數集合」的機率下界由Definition 1中，

「反集中 Anti-Concentration」來保證，

因為在Lemma 3的證明裡面，

Marc能透過一連串Convex Analysis的論證，

把整個機率變成「擾動向量分佈」與「長度一向量」的內積，

是否大過1的機率。

但根據我們的研究，

其實這一步樂觀機率下界可以避免，

只需要引入一種我們稱為「樂觀邊界點」的輔助點。

Reference

[1] https://scholar.google.com/citations?user=0WsQ0uUAAAAJ&hl=da

[2] https://arxiv.org/abs/1611.06534