Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
read the original abstract
We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's method, Le Cam's method, and Assouad's lemma -- are central to the study of minimax risk in statistical estimation, yet are insufficient to provide tight lower bounds for \emph{interactive decision making} algorithms that collect data interactively (e.g., algorithms for bandits and reinforcement learning). Recent work of Foster et al. (2021, 2023) provides minimax lower bounds for interactive decision making using seemingly different analysis techniques from the classical methods. These results -- which are proven using a complexity measure known as the \emph{Decision-Estimation Coefficient} (DEC) -- capture difficulties unique to interactive learning, yet do not recover the tightest known lower bounds for passive estimation. We propose a unified view of these distinct methodologies through a new lower bound approach called \emph{interactive Fano method}. As an application, we introduce a novel complexity measure, the \emph{Fractional Covering Number}, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity of estimation. Using the fractional covering number, we (i) provide a unified characterization of learnability for \emph{any} stochastic bandit problem, (ii) close the remaining gap between the upper and lower bounds in Foster et al. (2021, 2023) (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Algorithms and matching lower bounds for s-sparse contextual bandits yield Õ((s/ε² + |A|/ε) log |Π|/δ) samples to output an ε-optimal policy.
-
Bellman-sufficient Information Complexity
Introduces Bellman-sufficient information complexity as a representation-level framework for sequential decision making that unifies upper and lower bounds through a conditional Bellman information-risk sandwich.
-
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Proves pointwise majorizing-measure theorem for Gaussian processes, records Bayesian algorithmic lower bounds, and constructs a separation example among different complexity measures.
-
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Establishes a variance-aware pointwise majorizing-measure theorem for Gaussian fields, records Bayesian algorithmic lower bounds, and constructs a separation example among classical, algorithmic, and pointwise quantities.
-
Pointwise Generalization in Deep Neural Networks
Proposes pointwise Riemannian Dimension from feature eigenvalues to derive tighter, representation-aware generalization bounds for deep networks in the nonlinear regime.
-
Bellman-sufficient Information Complexity
Proposes Bellman-sufficient state representations and information indices Y=χ(Ω) to organize sequential decision making with a conditional Bellman information-risk sandwich providing matching upper and lower complexit...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.