樣本複雜度（sample complexity）

樣本複雜度問的是一個「預算」問題：學習者要和環境互動多少次——多少筆轉移、回合或步數——才能輸出一個接近最優的策略？它相當於監督式學習裡「需要多少筆樣本」的問題，但更難，因為在強化學習中你蒐集到的資料取決於你當下執行的策略，早期的爛策略會讓你拿不到「正是最關鍵那些狀態」的資訊。

形式上我們固定精度 ε 與信心水準 1−δ，求最小的樣本數 N(ε,δ)，使得至少有 1−δ 的機率，回傳的策略與最優差距在 ε 之內。這類界通常隨狀態數 S、動作數 A、有效視界 1/(1−γ) 與 1/ε 變化。對視界的依賴往往是最主要也最棘手的項；能省下哪怕一個 1/(1−γ) 因子，都是備受讚譽的理論成果。

樣本複雜度是對某一類 MDP 取最壞情況，所以看起來會比實務悲觀。它真正的價值在於比較：它告訴你哪些結構假設——生成模型、線性特徵、低貝爾曼秩——真的能換來更便宜的學習。