Bandit 001｜如何將未知量轉化為已知量？

由Yasin Abbasi-Yadkori [1] 於2011年發表的文章，

《Improved Algorithms for Linear Stochastic Bandits》[2]，

是每一個做 Bandit Problem 學術研究的人必讀的經典。

而看Bandit相關的Paper，我的第一步是從Regret Analysis開始看。

在Yasin這篇文章的第15頁，

我們可以看到對「瞬間後悔 instantaneous regret」的完整分析過程。

瞬間後悔的定義，是「在真實強盜參數 (Bandit Parameter)下，

強盜算法 (Bandit Algorithms)，

所選擇的行動 (Action)所得到的獎勵 (Reward)，

以及可能達到的最大獎勵 (Maximal)之間的差距 (Gap)。」

Yasin 在證明的第一步，用了一個很巧妙的上界，

直接點出了其在Section 2 描述的

「面對不確定性下的樂觀 Optimism in the Face of Uncertainty (OFU)」

在瞬間後悔分析時達到的效果：

將「未知的"真實強盜參數"與未知的"最優行動"」

替換成「已知的“估計強盜參數與已知的”強盜算法選擇的行動“」。

於是，在瞬間後悔定義中用到的未知量，

都能轉化為強盜算法設計就能知道的已知量，

那麼分析就能繼續下去。

這個思維在做理論研究的時候相當重要，

因為當我們在選取Performance Measure時，

通常會涉及一些「無法觀察的未知量」。

而如何用上界或下界來替換成「能計算的已知量」，

是一個演算法能不能做理論分析的關鍵。

Reference

[1] https://yasin-abbasi.github.io/

[2] https://papers.nips.cc/paper_files/paper/2011/hash/e1d5be1c7f2f456670de3d53c7b54f4a-Abstract.html