後悔界（regret bounds）

後悔值量的是「邊做邊學」的代價。想像一個智能體從第一天就必須在真實環境中行動；每次它選了次優的動作，就比一個一開始就知道最優策略的先知少賺一點報酬。後悔值就是 T 步內這些損失的累加。後悔值低，代表即使必須臨場摸索，智能體損失的也很少。

後悔界保證這個累積虧損隨 T 增長得很慢。黃金標準是次線性後悔，通常是 √T 量級，意思是每步的平均後悔趨近於零——智能體最終幾乎是最優地行動。這類界也揭示對 S、A、視界與問題結構的依賴；最緊的界會在對數因子內貼合資訊論下界。

後悔值與樣本複雜度是表親但不相同：後悔值對你沿途每個錯誤都收費，而 PAC 式的樣本複雜度只在你輸出好策略之前收費。兩者可以互換，但換算從來不是免費的。