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

arXiv: https://arxiv.org/abs/2410.05117 · HTML: https://mlsanity.com/paper/2410.05117/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 56 references that are in the map.
- First posted on arXiv 7 Oct 2024.

## Builds on (most cited first, 22 of 22)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring](https://mlsanity.com/paper/2305.00684/) (2023)
- [Online Estimation via Offline Estimation: An Information-Theoretic Framework](https://mlsanity.com/paper/2404.10122/) (2024)
- [Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory](https://mlsanity.com/paper/2304.12466/) (2023)
- [Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond](https://mlsanity.com/paper/2209.11745/) (2022)

## Built on by (most cited first, 12 of 12)

- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Decision Making in Hybrid Environments: A Model Aggregation Approach](https://mlsanity.com/paper/2502.05974/) (2025)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making](https://mlsanity.com/paper/2510.05808/) (2025)
- [Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation](https://mlsanity.com/paper/2606.07931/) (2026)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Bellman-sufficient Information Complexity](https://mlsanity.com/paper/2606.11171/) (2026)
- [The Critical Horizon: Inspection Design Principles for Multi-Stage Operations and Deep Reasoning](https://mlsanity.com/paper/2602.09394/) (2026)
- [On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization](https://mlsanity.com/paper/2603.18514/) (2026)
- [Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems](https://mlsanity.com/paper/2604.12519/) (2026)
- [Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy](https://mlsanity.com/paper/2606.23096/) (2026)

## Abstract (arXiv)

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 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 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 interactive Fano method. As an application, we introduce a novel complexity measure, the 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 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.