思考Information Ratio
紫式晦澀每日一篇文章第32天
前言
-
今天是2022年第30天, 全年第5週, 一月的第五個週日. 今天來爬梳「資訊比(Information Ratio)」的相關知識.
-
今天的素材主要來自各種關於Information Ratio的文章.
- 2019: Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
- 2020 Thesis: Adversarially robust stochastic multi-armed bandits
- 2014 MOR: Learning to Optimize via Posterior Sampling
- 2018: Learning to optimize via information-directed sampling
心法
資訊比的非形式化定義與直覺:
- 證明的基礎: 資訊比 $$ \text { information ratio }_{t}=\frac{(\text { expected regret in round } t)^{2}}{\text { expected information gain in round } t}, $$
- 資訊比小: 學習者的後悔夠小, 或者得到資訊夠多.
要馬「決策得好」要馬「學很多」
資訊獲取(Information gain)的實踐法:
- 相互資訊 (Mutual Information)[25]
- 廣義Bregman divergence (Generalization on a Bregman divergence)[21]
資訊理論分析搭非負熵勢能-minimax最優:
- 資訊理論分析(Information-Theoretic Analysis)
- 非負熵勢能(negentropy potential)
- 得到的bounds, 在K-armed bandit與Exp3雷同.
- 在Tsallis entropy與INF strategy也成立[6]J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of Conference on Learning Theory (COLT), pages 217–226, 2009.
資訊比與線上隨機鏡面下降:
- 分析技巧的雷同
- Bound資訊比(Bound information ratio)
- 控制線上隨機鏡面下降的穩定度(Control stability of online stochastic mirror descent)
技法
用OSMD的技術設計TS算法
但這樣bandit與full information的邊界在哪裡?
連結四大問題:資訊理論, 鏡面下降, 貝氏後悔, 對抗學習:
- 分析「線上隨機鏡面下降」的工具, 可以得到一種版本的「Thompson取樣」, 把「鏡面下降更新(Mirror descent update)」換成「貝氏更新(Bayesian update)」.
- 資訊理論分析<->線上隨機鏡面下降(OSMD)更新分析
- OSMD <-> 貝氏後悔分析
- 貝氏後悔分析–>對抗框架
關鍵函數:
- 取樣策略P: 決定算法如何探索
- 勢能函數F: 凸勢能,
- 估計函數E: 估計無法觀察的損失向量
最小化「獲得每單位資訊的成本」:
- 權衡:小的期望後悔 VS 學那個行為是最優新資訊
- 範圍: 各種取樣分佈
- IDS會短視近利, 要最小化「獲得每單位資訊的成本」.
用法
K-armed對抗強調是minimax最優:
- Lattimore與Szepesvari[21]: 證明k-armed adversarial bandits is minimax optimal
- 應用1: graph feedback
- 應用2: linear bandits on $l_p$-balls.
後記
今天大概看一看相關的文獻, 之後在陸續累積insights.天天向上, 共勉之！
2022.01.29. 紫蕊 於 西拉法葉, 印第安納, 美國.
評論