Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

In this paper, we develop a unified framework for lower bound methods in statistical estimation and interactive decision making. Classical lower bound techniques—such as Fano’s inequality, Le Cam’s method, and Assouad’s lemma—have been central to the study of minimax risk in statistical estimation, yet they are insufficient for the analysis of methods that collect data in an interactive manner. The recent minimax lower bounds for interactive decision making via the Decision-Estimation Coefficient (DEC) appear to be genuinely different from the classical methods. We propose a unified view of these distinct methodologies through a general algorithmic lower bound method. We further introduce a novel complexity measure, decision coverage, which facilitates the derivation of new lower bounds for interactive decision making. In particular, we establish necessary and sufficient complexity measures for convex model classes, addressing the remaining gap between upper and lower bounds in Foster et al.