Bandit 004｜如何使用鞅集中不等式分析強盜演算法？

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