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

Summary

This paper aims to provide a unified framework for deriving lower bounds of interactive decision-making problems using an extended technique adapted from Chen et al., 2016 [11], which was established only for non-interactive estimation problems. The paper offers a quite general formulation of the minimax value of interactive decision-making that encompasses both previously known and novel formulations. In particular, the paper demonstrates that such a lower bounding technique can be used to rederive the lower bounds from Foster et al., 2023 [25] and provide tighter lower and upper bounds via a new complexity named "decision coverage."

Strengths

I find the general formulation and the technique based on percentiles (instead of the expected value used in prior literature such as [25]) for deriving lower bounds to be quite appealing. Although it appears to me that the lower bounding techniques are essentially "abstracted out" from prior literature, such as [11] and [23, 25], the paper presents it in a quite clean manner. The paper also provides several new results, such as interactive parameter estimation and tighter bounds for interactive reward maximization. I generally enjoyed reading this paper and find it worthy of publishing at NeurIPS. I expect the paper to have a broad impact on the community.

Weaknesses

My main complaint about this paper is that it contains many hand-waving arguments. I had to fill in many gaps in the proofs myself to verify and understand the results. I outline some specific comments below (some are minor, while others need additional justifications): 1. I'm not sure if it is appropriate to call Corollary 2 a "Generalized Fano’s inequality", as it is not clear to me that it implies the original Fano's inequality (though they are "qualitatively" equivalent, i.e., both require $I(M,X) \ll \log |\mathcal{M}|$ to arrive at a constant lower bound). 2. You claim in line 186 "Fano’s inequality, e.g., in the form of Corollary 2, cannot be used to prove Lemma 3." Is there an argument why this is true? 3. Can you explain how Theorem 5 is instantiated from Theorem 1? It appears to me that its proof is completely self-contained without invoking any parts of Theorem 1. 4. Can you comment on how prior technique for deriving Corollary 9 differs from your Fano's inequality-based argument? 5. Can you explain how $T^*(\mathcal{M},\Delta)$ characterizes the regret? Specifically, it does not appear to me that there is a simple way to express the regret in terms of $T^*(\mathcal{M},\Delta)$. Moreover, why does Theorem 4 imply the statement in line 282? 6. The proof of Theorem 10 is too sketchy. It is not clear to me that (12) shares the structure as Proposition 8. Are you applying the minimax theorem here? 7. Theorem 10 looks quite trivial to me, as it does not depend on any information-theoretical structure of the model class (except Assumption 2). 8. Given point 5, I'm not sure how to interpret your Theorem 12 and how to compare it with [25]. It appears you are claiming this as a main result; can you provide any specific examples that demonstrate the improvement (i.e., explicitly computing the "decision coverage" for some classes)? 9. You claim that "Theorem 12 provides (polynomially) matching lower and upper bounds for learning M." Isn't $\max\\{a,b\\}$ can be arbitrarily smaller than $a \cdot b$? How should the "matching" be interpreted? 10. It appears to me the upper bound of Theorem 11 essentially converts the dependency on the size of the model class to that of the decision space. Given the similarity of the proof with that in [24], can you comment on if the results from [24] recover your upper bound (with possible replacement of decision coverage with $\log|\Pi|$)? 11. Typos (there are many, but I only include what I still remember): - $D_f(a,b)$ was never properly defined, though one can guess it is for $D_f(\text{Bern}(a),\text{Bern}(b))$. - What is the $\alpha$ in line 873?

Questions

See above.

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper develops the notion of Interactive Statistical Decision Making (ISDM), and a generic lower bound (Theorem 1) which can be instantiated to capture the standard Le Cam, Assaoud, Fano methods as well as recent lower bound results in interactive decision making. The authors further use Theorem 1 to derive new sample complexity bounds (Theorem 12, 13) on interactive decision making contexts (under some regularity conditions on the model class).

Strengths

I think it's interesting to try to unify different lower bound approaches in order to gain new insights, so the premise of the paper is very intriguing to me. The submission further uses the general theorem to derive new bounds, based on the new notion of Decision Coverage, that tightens existing results in interaction decision making.

Weaknesses

It may be due to my lack of expertise in interaction decision making literature, but I'm having trouble understanding and evaluating the new contributions, with intuition missing that I hoped the paper would give. Some of the contributions also seem a bit overclaimed. I hope the following constructive criticisms would help the authors improve the paper. - "Addressing remaining gap" and "complete characterization": the authors say that the new results (Theorems 12/13) "completely characterize" the sample complexity of interactive decision making for convex model classes, but the left and right hand sides differ quadratically (and ignores log factors). Am I misinterpreting the results? They aren't even tight up to constants. - Line 56: I don't quite understand why "unifying two-point vs mixture-vs-mixture methods" is a new contribution. Mixture-vs-mixture is clearly a generalization of singleton two-point methods, so why is the unification sold as a new contribution? - Generally I find the bound in Theorem 1 challenging to interpret, as opposed to two-point or mixture-vs-mixture methods that make intuitive sense. I'm struggling to understand the insight gained by the Theorem 1 formulation through unifying two-point methods and Fano with interaction decision making. To me, ISDM reads like a very generic minimax game formulation, and then Theorem 1 tags on the reference distribution/ghost data $\mathbb{Q}$ in order to encompass existing techniques for interaction decision making. Lemma 3 then removes this extra component by declaring $\mathbb{Q}$ simply as the transcript of the algorithm, so what have we learned about standard statistical estimation through Theorem 1? In other words, my question is, why is Le Cam/Assaoud/Fano even part of the paper, instead of focusing only on the new bounds in interactive decision making? What am I missing? - Theorem 12 is a bit too informal, hiding the log factors (especially without specifying log factors in what). It also wasn't actually proven -- I think the calculations using Assumptions 2 and 3 (and applied to Theorem 11) should be explicitly shown in the appendix. - Relatedly, again on the topic of needing more interpretation, I wish the submission explained how DC is better than the $\log |\mathcal{M}|$ factor in Line 282. Misc typos I spotted and other small comments: - First page, should define Perf as cost, so that minimization is the correct direction. - End of Line 123, should the asterisk in $M^\ast$ be removed? - Line 177, $L:\Theta \times \mathcal{A} \rightarrow \mathbb{R}_+$ right? Instead of domain being $\Theta \times \Theta$? Just a consistency issue with the rest of the lemma. - Line 594, I presume "ISDM" instead of "ASDM"?

Questions

Please see weaknesses above. - Could the authors also comment on how the techniques apply/adapt if we want to show lower bounds on high-probability loss instead of expected loss? Two-point methods are straightforward (and even simpler than Le Cam) to use in a high-probability setting.

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Summary

This paper proposes a unified framework for lower-bound methods in statistical estimation and interactive decision-making. The authors integrate classical lower bound techniques (Fano's inequality, Le Cam's method, Assouad's lemma) with recent minimax lower bounds for interactive decision-making (Decision-Estimation Coefficient). The framework is based on a general algorithmic lower bound method and introduces a novel complexity measure, decision coverage. The paper also has a lot of other results, including the unification of classical and interactive methods, the generalization of Fano's separation condition, and the derivation of new lower bounds for interactive decision-making.

Strengths

* The framework developed in the paper is valid for a very general class of problems and unifies classical and classical lower bound techniques, Fano's inequality, Le Cam's method, and Assouad's lemma, and provides a comprehensive framework for statistical estimation and decision making. * Lots of other contributions: incorporating the previous work on DEC into the framework of this paper introduces a new complexity measure called decision coverage, which quantifies the complements of the previous DEC lower bounds. * Except for a few typos, the paper is well-written. * Overall, it is a solid paper, and contributions are significant.

Weaknesses

* I dont find any major technical weakness in this work. The work is good and a bit hard to follow for someone who is a non-expert in this area. Most of the points I highlight below are bunch of typos that I found and clarification that I think its good to include. * Line 123, I think it should be $L(M,X)$ instead of $L(M^*,X)$ * The proof of corollary 2 is skipped. It involves 3-4 steps, and therefore I don't think it is trivial, especially for those who are not experts in dealing with these inequalities. * There seem to be a lot of (minor) typos in Lemma 3, and it's proof. 1. Firstly, it's better to clarify whether sets $\theta_0, \theta_1$ are required to be distinct or not in the Lemma statement. 2. ASDM is not defined in the first line of proof. 3. I think the second equality in Line 602 will contain a factor of $1/2$. Can authors also clarify if the next step follows by data processing? 4. In line 603, $ d_{3/4}(\cdot,\cdot)$ is not defined. May be authors mean $ d_{f, 3/4}(\cdot,\cdot)$. Please also explain why that inequality follows, is it by choice of $\Delta$ and so that Theorem 1 can be applied? 5. There seems to be a typo in the subscripts of expectation in line 604, third inequality. * I guess in Line 218 Eq. 9, $p_{out}$ is not defined. * I don't think $\pi_{out}$ in Line 226 is defined before (in the statement of theorem 5). * I would appreciate if the authors mention where the realizability assumption (Assumption 1) is needed and the issues that arise in the agnostic setting, i.e., when realizability does not hold. Also, please provide examples (or references) of well-posed model classes in Assumption 2. * It is not clear to me why there exists $M$ in the model class, i.e., why is the supremum achieved here by some $M$ in proof of Theorem 5. * Line 329, I don't think $\mathbb{V}$ is defined.

Questions

See weaknesses.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

Essentially no broader societal impacts.

Summary

This work provides a unified perspective of existing techniques for deriving lower bounds. This viewpoint covers techniques that are useful for traditional statistical estimation (e.g., Fano's inequality, Le Cam's method, and Assouad's approach) as well as the recently proposed approach using decision-estimation coefficients that concerns interactive decision-making. In addition, this work proposes a novel complexity measure called decision coverage. Using this novel measure, this work derives lower and a polynomially matching upper bound for learning convex model classes.

Strengths

S1. The paper discusses a unified perspective of techniques to derive lower bounds. It integrates classical techniques (Fano’s inequality, Le Cam’s method, and Assouad’s lemma) with contemporary methods for interactive decision-making, based on the Decision-Estimation Coefficient (DEC). S2. This work introduces a novel complexity measure called decision coverage. This measure facilitates the derivation of new lower bounds specifically tailored for interactive decision-making.

Weaknesses

See questions

Questions

Q1. How realistic is Assumption 2? It seems to require that we have a model $\bar{M}$ that is close to all models $M \in \mathcal{M}.$ It is unclear why should such an assumption be true for a finite $C_{KL}?$ Similarly, how realistic is Assumption 3? Can you give some application examples where Assumptions 2 and 3 hold? Q2. What is $\mathbb{V}$ in line 329? Is it variance? Q3. Why is Assumption 2 not needed in Theorem 13, even though the line above says that this result is a corollary to Theorem 12? Q4. Can the ideas in this work be extended to the RL setup? Q5. Can the ideas in this work be extended to the case of interactive decision-making with multiple agents? I am happy to increase my score based on your response.

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

The work does not explicitly discuss the limitations of their work; at least, I could not find it anywhere.