今天繼續聊聊由Yasin Abbasi-Yadkori [1] 於2011年發表的文章，
《Improved Algorithms for Linear Stochastic Bandits》[2]。
今天主要想討論在第11頁的Lemma 8，
Yasin 展示了如何構造「超鞅 Supermartingale」，
來進一步使用「鞅集中不等式 Martingale Concentration Inequality」做分析。
直觀看，行動特徵向量是d維度的，而鞅原則上都是1維度的，
兩者如何能結合呢？
這一定有某個地方，把行動特徵向量做了降維度。
而沒錯，這裡也做了降維度。
Lemma 8 主要介紹一個參數向量 lambda，
跟特徵向量做內積，於是就變成1維了。
而更有趣的技巧在，
文章第4頁定義了 Sgima-代數，
是有包含行動特徵向量的，
所以並不需要考慮行動特徵向量的分佈，
因為在給定的「過濾 Filtration」下，
行動特徵向量並沒有隨機性。
如此，隨機性就完全來自源頭假設獎勵模型裡面的噪音。
Yasin這篇文章中，假設的分佈是 R-次高斯，
所以可以先透過一些高斯分佈相關的Calculus，
來了解給這個噪音乘以常數除以常數後的分佈。
於是，就從原本R-次高斯分佈的定義，
推導出了「鞅差 Martingale Difference」的定義，
進一步構造了「超鞅 Supermartingale」。
Bandit算法裡面各種對任何時刻都對的機率不等式，
基本上都有「超鞅 Supermartingale」在裡面。
Reference
[1] https://scholar.google.com/citations?user=0WsQ0uUAAAAJ&hl=da
[2] https://arxiv.org/abs/1611.06534
