遺憾值與探索的代價

把遺憾值講精確

在 T 步之內，遺憾值就是「最優策略原本能賺到的總回報」減去「你的演算法實際賺到的」。衡量標準在於遺憾值是否隨 T 次線性（sublinear）成長：若是，你每步的平均回報就會逼近最優，也就是在有意義的意義下「學會了如何行動」。線性遺憾值代表每一步都永遠損失一個固定量——你其實從未真正學會。功夫就在於把遺憾值壓到統計法則所允許的最小。

面對不確定性時保持樂觀

最成功的探索原則是不確定下的樂觀（optimism under uncertainty）：在你資料允許的範圍內，假裝世界跟它可能達到的一樣好，然後照此行動。如果某個動作真的好，你就利用它；如果它只是不確定，樂觀會誇大它的價值，於是你去嘗試、進而學到東西——兩種情況你都是贏家。它在吃角子老虎機上的版本就是著名的上信賴界（upper confidence bound，UCB）：挑選「平均值加信賴寬度」最高的那隻手臂。

信賴寬度直接來自集中不等式：你嘗試某隻手臂的次數越多，它的平均值就越緊地集中在真值附近，於是樂觀加成（bonus）就越縮越小。因此樂觀是自我修正的——它恰好去探索那些你仍不確定的動作，而不再把時間浪費在已成定局的動作上。

a_t=\arg\max_{a}\left(\hat{\mu}_a+\sqrt{\dfrac{2\ln t}{N_t(a)}}\right)

把樂觀寫成公式：選擇上置信界最大的動作，獎勵項隨著該臂被拉次數的增加而收縮。

UCRL：把樂觀推廣到整個 MDP

把 UCB 從單一狀態提升到完整的 MDP，就得到 UCRL 演算法（Upper Confidence RL）。UCRL 不是為每隻手臂維護一個樂觀數值，而是維護一個由可信 MDP 組成的信賴集——所有與目前資料一致的轉移與獎勵模型——並針對其中回報最高的那一個來做規劃。接著它執行這個樂觀策略，直到某個狀態–動作的計數翻倍，再重算信賴集、如此反覆。這個「樂觀地規劃、行動、縮小不確定性」的迴圈，是 MDP 中幾乎所有可證明高效探索的範本。

# UCRL, episode loop (sketch)
while t < T:
    M_set = confidence_set(counts, reward_hat, P_hat)   # plausible MDPs
    pi    = plan(optimistic_MDP(M_set))                 # extended value iteration
    # act under pi until any (s,a) visit count doubles
    while not any_count_doubled():
        s, a, r, s2 = step(pi); update_counts(s, a, r, s2); t += 1
# regret(T) = O~( D * S * sqrt(A * T) )

信賴集加上樂觀規劃，使遺憾值以 √T（而非 T）的速度成長。

\mathrm{Regret}(T)=\tilde{O}\!\left(D\,S\sqrt{A\,T}\right)

UCRL 的回報：在可能的 MDP 上構建樂觀置信集，使遺憾按 √T 而非 T 的速度增長。

√T 屏障：任何演算法都打不過的線

√T 的遺憾值只是我們找到的最好，還是可能的最好？這時極小極大下界給出答案：可以構造出一些在統計上極易混淆的 MDP，逼得任何學習者至少要承受約 √(D·S·A·T) 等級的遺憾值。由於 UCRL 風格的上界恰好匹配這個 √T 的成長率（差在維度因子上），對 T 的速率因而塵埃落定。剩下的戰場，是對直徑 D 以及對 S、A 的依賴——正是那些探索代價項。

從遺憾值到樣本複雜度

遺憾值與樣本複雜度是同一種效率的兩個視角。一個次線性遺憾值的演算法只會犯下有界次數的「大錯」，而這個次數本質上就是一個 PAC 樣本複雜度界。所以 UCRL 不只以低累積損失學會行動，還能在可預期數量的樣本之後保證得到一個接近最優的策略。下一篇我們要問更難的問題：一旦狀態空間大到放不進一張表，這些保證還能留下哪些？