今天聊聊 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