極小化極大下界（minimax lower bounds）

上界說「這個演算法能學得這麼快」。極小化極大下界說的是相反且更難的事：「無論多聰明的演算法，在最壞情況下都不可能做得更好」。它標出了難度的地板。當一個演算法的上界在對數因子內貼合 minimax 下界，你就知道這個問題本質上解決了——已經沒有空間留給根本上更聰明的方法。

證明是對抗式的。你建構一族從有限資料看來幾乎一模一樣的 MDP——比方說兩個學習者沒蒐集很多樣本就分不出的報酬分布——並證明任何演算法在其中至少一個上必然表現不佳。勒康（Le Cam）的雙點法與法諾（Fano）不等式這類工具，把「這些實例在統計上不可分辨」轉成「所以你必須承受這麼多誤差或後悔」。結果是資訊論的，與計算無關。

下界是對某一類取最壞情況，所以一個良性的真實問題可能遠比地板暗示的容易。它的角色是認證最優性，並揭示哪些問題參數——視界、動作之間的差距、特徵維度——是本質上昂貴的。