PAC 強化學習（probably approximately correct RL）

PAC 代表機率近似正確（probably approximately correct），這是從監督式學習理論借來的框架。它的承諾刻意保守：我們不要求以確定性拿到完全最優的策略，只要一個近似正確（與最優差距在 ε 內）且高機率成立（至少 1−δ）的策略。ε 與 δ 這兩個旋鈕讓保證可被否證，也讓我們能算出要多少資料才換得到。

在強化學習裡，PAC 保證通常是界定智能體「行動比 ε 還差」的時步數量——也就是「錯誤」的次數——而不是時鐘上的收斂。若這個次數對 S、A、1/(1−γ)、1/ε 與 log(1/δ) 是多項式的，演算法就稱為 PAC-MDP。R-MAX 與延遲 Q-學習等經典結果正是這樣證明的：把樂觀原則與對估計報酬、轉移的集中界結合起來。

PAC 不告訴你哪些錯誤在何時發生，只說總數很少。在某些面向它比後悔界弱、某些面向又更強；該選哪個概念，取決於早期錯誤是會釀成大禍，還是只是代價較高。