minimax lower bounds

Upper bounds say "this algorithm can learn this fast." Minimax lower bounds say the opposite and harder thing: "no algorithm, however clever, can do better than this on the worst case." They mark the floor of difficulty. When an algorithm's upper bound matches the minimax lower bound up to logarithmic factors, you know the problem is essentially solved — there is no room left for a fundamentally smarter method.

The proofs are adversarial. You construct a family of MDPs that look nearly identical from limited data — say, two reward distributions a learner cannot tell apart without many samples — and show that any algorithm must do badly on at least one of them. Tools like Le Cam's two-point method and Fano's inequality convert "these instances are statistically indistinguishable" into "so you must incur this much error or regret." The result is information-theoretic, independent of computation.

Lower bounds are worst-case over a class, so a benign real problem can be far easier than the floor suggests. Their role is to certify optimality and to reveal which problem parameters — horizon, the gap between actions, feature dimension — are intrinsically expensive.