貝爾曼秩（Bellman rank）

在函數近似下，有些強化學習問題用不多的資料就學得會，有些則毫無希望，而表面上很難分辨是哪一種。貝爾曼秩就是為了畫出這條界線而發明的複雜度度量。直覺上它捕捉的是：每個新策略對其他所有策略的貝爾曼誤差，到底揭露了多少真正新的資訊——若這些資訊活在低維空間裡，探索就無法永遠不斷給你驚喜。

形式上，我們把「策略 i 的價值估計在策略 j 下評估的平均貝爾曼誤差」排成一個矩陣，貝爾曼秩就是該矩陣的秩。秩小代表有一個低維結構把所有候選價值函數綁在一起，OLIVE 之類的演算法於是能以「對該秩、視界與函數類大小的對數呈多項式」的樣本複雜度學到近最優策略——而非對狀態數量。線性 MDP 與其他數個可解模型都有低貝爾曼秩。

低貝爾曼秩對「樣本高效學習」是充分條件，卻不一定計算高效，而它只是數個彼此競爭的複雜度度量之一（貝爾曼–Eluder 維度、決策–估計係數），研究者至今仍在爭論哪一個最乾淨地刻畫了「一般函數近似何時可學」。