CS234 資料效率 I：multi-armed bandit、regret 與 UCB
CS234 L9 與 L10 前半把「探索」從 ε-greedy 這種經驗法則，變成可以證明的東西。先定義 regret：跟一直選最好的手臂相比，你少拿了多少。greedy 會鎖死在次佳手臂，固定 ε 的 ε-greedy 永遠有 ε 比例在亂選，兩者的 regret 都隨時間線性成長。Lai-Robbins 下界說最好也要對數成長，而 UCB 靠「對不確定的手臂樂觀一點」做到了：Bandit Algorithms 定理 7.1 給出每隻次佳手臂只會被拉大約 16 log n / Δ² 次。