由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
