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

Thank you for your insightful feedback and for dedicating time to review our paper!

Q1. I'm not sure if it's appropriate to call Corollary 2 "Generalized Fano’s inequality"

In our proof of Theorem 1 on page 15, we actually prove Theorem D.1, which holds for general quantile $\delta\in(0,1)$ rather than $½$. Similarily, Corollary 2 can be generalized to any $\delta$: when $I(M;X)+\log 2\leq (1-\delta)\cdot \log \frac{1}{\mu(M \in \mathcal{M} : L(M,x) < \Delta)}$, the Bayes risk $\geq\delta\Delta$. This precisely implies original Fano’s inequality when $\mu$ is uniform, $\mathcal{M}=\mathcal{X}, L(M,x)=\mathbb{1}(M\neq x), \Delta=1$. We will restate Corollary 2 for arbitrary $\delta$ and clearly explain the generalization.

Q2. You claim in line 186 "Fano’s inequality, e.g., in the form of Corollary 2, cannot be used to prove Lemma 3."

Fano’s method and the “mixture vs mixture” method described in Lemma 3 are conceptually distinct due to the use of different divergences. In particular, Lemma 3 (and the mixture vs mixture method in general) use total variation distance, whereas Fano inequality uses KL-based mutual information. As a result, unless the distributions under consideration have favorable structure that allow one to bound the KL-based mutual information by total variation distance, it does not appear to be possible to recover Lemma 3 from Corollary 2.

We mention in passing that we are not aware of any results which recover guarantees based on the mixture vs. mixture method from Fano method in prior work.

Q3. How Theorem 5 is instantiated from Theorem 1?

The current proof of Theorem 5 is indeed self-contained (for completeness), but the idea is the same as Theorem 1, and it can indeed be proven as a corollary. To instantiate Theorem 1, we can choose the $f$-divergence to be the squared Hellinger distance, set $\mathbb{Q}=\mathbb{P}^{\overline{M},ALG}$, and choose $\mu$ to be the delta distribution on the model $M$. We will clarify this in the revision.

Q4. How prior technique for deriving Corollary 9 differs from your Fano's inequality-based argument?

Prior work proves the regret lower bound in Corollary 9 using Assouad’s lemma (see e.g. Section 24 of [34]), which explicitly relies on the hypercube structure of the parameter space. By contrast, the proof of Corollary 9 is based on bounding the mutual information under a certain (uniform) prior and then applying Fano’s inequality. Conceptually, these two approaches appear to be fairly distinct (Assouad’s lemma often gives tight results when hypercube structure is available, while the Fano method is somewhat more general, but can require more effort to apply, particularly in interactive settings; therefore, it is interesting to see that both lead to the same result here).

Q5. How T∗(M,Δ) characterizes the regret? Why does Theorem 4 imply line 282?

By the definition of $T^\star(\mathcal{M},\Delta)$, we have

$$\frac{1}{T}\mathrm{Reg}^\star_T=\sup\{ \Delta: T^\star(\mathcal{M},\Delta)\leq T \}.$$

For example, $T^\star(\mathcal{M},\Delta) \asymp \frac{C}{\Delta^2}$ implies that $\mathrm{Reg}^\star_T \asymp \sqrt{CT}$.

Further, notice that Theorem 4 implies (under Assumption 3)

$$\mathrm{dec}^c_{\underline{\epsilon}(T)}(\mathcal{M}) \lesssim\frac{1}{T}\mathrm{Reg}^\star_T\lesssim \mathrm{dec}^c_{\bar{\epsilon}(T)}(\mathcal{M})$$

The statement in line 282 then follows from the definition of $T^\star(\mathcal{M},\Delta)$ and $T^{\rm DEC}(\mathcal{M},\Delta)$.

Q6. The proof of Theorem 10 is too sketchy. Are you applying the minimax theorem here?

Thank you for pointing this out. The current presentation of the proof focuses on highlighting the connection to Proposition 8, which is somewhat subtle and requires applying the minimax theorem. We will be sure to include more details in the final revision (there is also a more direct proof, which we are happy to include for completeness).

Q7. Theorem 10 looks quite trivial...

Indeed, the quantity DC measures certain inherent complexity of the decision space, and it does not depend on the information-theoretical structure of the model class. However, it does imply non-trivial lower bounds for various model classes:

(1) Linear bandits: $\mathsf{DC}\gtrsim d$

(2) Unstructured contextual bandits with context space $\mathcal{C}$: $\mathsf{DC}\gtrsim |\mathcal{C}|\log|\mathcal{A}|$

(3) Tabular RL: $\mathsf{DC}\gtrsim |\mathcal{S}|$.

Given that the proof of Theorem 10 only utilizes the structure of the decision space, DC should be regarded as a (non-trivial) complexity measure that is complementary to DEC (which captures the information-theoretical structure of the model class), in the sense that the lower bounds they provide are complementary, and together they provide also an upper bound (Theorem 11).

Q8. How to interpret your Theorem 12? Any specific examples? Q9. Isn't max{a,b} can be arbitrarily smaller than a⋅b? How should the "matching" be interpreted?

The main contribution of Theorem 12 is that the upper bound is at most the square of the lower bound (as $a\cdot b\leq \max(a,b)^2$). Therefore, for any convex model class, the sample complexity is completely determined by DEC and DC up to a square gap. Such a characterization of sample complexity for general decision making is new, and we believe it to be conceptually important.

Q10. Can you comment on if the results from [24] recover your upper bound (with possible replacement of decision coverage with log⁡|Π|)?

Our proof of Theorem 11 is essentially an adaptation [24], with the goal of replacing $\log|\Pi|$ by the decision coverage in the upper bound. For general decision making problems, $\log|\Pi|$ can be arbitrarily larger than the decision coverage, meaning that our upper bound represents a significant improvement.

Typos

Thank you for pointing out these typos. Indeed, $D_f(a,b)$ is the abbreviation of $D_f(Bern(a),Bern(b))$, and $\alpha$ in line 873 is a typo. We will clarify these in the revision.

Thank you for your careful review and constructive criticism! We will work on better presenting the intuition behind our results and revise our statements to make them more precise.

Regarding "addressing remaining gap" and "complete characterization": the lower and upper bounds differ quadratically ...They aren't even tight up to constants.

Indeed, by using the term "complete characterization", we want to highlight that DC and DEC together provide a characterization of polynomial learnability. Although their lower and upper bounds may not offer a tight characterization of the T-round minimax risk, our one-round complexity measures, DC and DEC, elucidate what is necessary and sufficient for the estimation component (DC) and the estimation-to-decision-making component (DEC) in interactive decision making. 

DC is essential because it appears in both the upper and lower bounds (similar to DEC). In contrast, prior work [23][25] includes a $\log|\mathcal{M}|$ factor only in the upper bound, with no hope of it appearing in a lower bound. This discrepancy was identified as a major open question in previous studies [23][25]. To address this gap, we need to eliminate $\log|\mathcal{M}|$ and identify DC that appears in both upper and lower bounds.

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?

Sorry for the confusion. Mixture-vs-mixture is indeed a generalization of the singleton two-point method, and we mean to say that our approach recovers both, rather than unifying them into one concept. Our intention is to convey that our method unifies mixture-vs-mixture (and thus the entire scope of two-point methods) with Fano's and Assoud's methods, where these three previously lacked a unified perspective. We will rewrite the sentence as “unify mixture-vs-mixture (and thus the entire scope of two point methods) as a special case of our general algorithmic lower bound” to convey the right message.

Generally I find the bound in Theorem 1 challenging to interpret, ...why is Le Cam/Assaoud/Fano even part of the paper, instead of focusing only on the new bounds in interactive decision making?

Our goal is to integrate the Fano and Assouad methods (which provide dimensional insights but are typically challenging to apply in interactive settings and inherently follow a T-round analysis approach) with the DEC framework (which offers one-round complexity measures for interactive settings but previously lacked a dimensional factor/estimation component in the lower bound). Therefore, it is crucial to demonstrate that our framework can recover the non-interactive versions of these methods as a special case, serving as an important sanity check.

Moreover, by utilizing the algorithmic Fano method (Proposition 8), we not only introduce the new complexity measure DC (Theorem 12), which includes the dimension in the lower bound, but also recover a tight lower bound for linear bandits (Corollary 9), which would otherwise not be captured by Theorem 12. This also illustrates the advantage of having a unified method for interactive decision making and Fano’s method.

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.

Thanks! We will provide a detailed step-by-step explanation in the revised version. The minimax-optimal sample complexity $T^\star(\mathcal{M},\Delta)$ is just a way to better illustrate our minimax regret upper and lower bounds. Assumptions 2 and 3 are conditions to establish that the additional terms in the regret upper (Theorem 11) and lower bound (Theorem E.1) are of the same order as the dec terms. This ensures that one has 

$$\mathrm{dec}^c_{\underline{\epsilon}(T)}(\mathcal{M}) \lesssim\frac{1}{T}\mathrm{Reg}^\star_T\lesssim \mathrm{dec}^c_{\bar{\epsilon}(T)}(\mathcal{M})$$

Theorem 12 is then proved by using the definitions of sample complexities $T^\star(\mathcal{M},\Delta)$ and $T^{\rm DEC}(\mathcal{M},\Delta)$.

Relatedly, again on the topic of needing more interpretation, I wish the submission explained how DC is better than the factor $\log|\mathcal{M}|$ in Line 282.

DC is fundamentally different with $\log|\mathcal{M}|$ because it arise in both the upper and the lower bounds, while $\log|\mathcal{M}|$ only appears in the upper bound (and there is no hope for having it appear in a lower bound in general). Comparing Theorem 12 and Line 282, one can observe that DC together with DEC gives a complete characterization of the sample complexity up to a quadratic order. In contrast, $\log|\mathcal{M}|$ is clearly not a good candidate for the estimation component in the lower bound, as it is the coarsest measure in learning theory.

Moreover, for examples like convex bandits, the $\log|\mathcal{M}|$ factor is obviously too loose, which will be $\exp(d)$ for the complete class of convex functions, while we know that $poly(d)$ regret is achievable for convex bandits [23][32].

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? ...

This is a great question! In our proof of Theorem 1, we essentially establish a lower bound for the quantile $\mathbb{P}_{M∼\mu, X\sim{\mathbb{P}^{M,ALG}}} (L(M, X) \geq \Delta)$ (line 578). This quantile lower bound (Theorem D.1) can be directly used to prove a high-probability lower bound in a straightforward manner (for any error $\delta$).

Misc typos I spotted and other small comments...

Many thanks for pointing these out. We will be sure to clarify these issues in the final revision.

Thank you for your insightful feedback and for dedicating time to review our paper!

Q1. How realistic is Assumption 2? It seems to require that we have a model that is close to all models It is unclear why should such an assumption be true for a finite Similarly, how realistic is Assumption 3? Can you give some application examples where Assumptions 2 and 3 hold?

A1: Assumption 2 is a relatively mild condition on the model class $\mathcal{M}$. Examples:

(1) Bandits. Suppose that $\mathcal{M}$ is a class of bandits with Gaussian rewards, i.e. $\Pi=\mathcal{A}$ is the action space, and for each $M\in \mathcal{M}$, $a\in\mathcal{A}$, the observation is generated as $o\sim N(f^M(a),1)$. Then, we can consider the reference model $\overline{M}$ with $f^{\overline{M}}(a)\equiv 0$, and $D_{KL}(M(a)||\overline{M}(a))=\frac{f^M(a)^2}{2}$. Therefore, $C_{KL}$ is bounded as long as the mean reward is uniformly bounded for models in the model class $\mathcal{M}$.

(2) Contextual bandits. Suppose that $\mathcal{M}$ is a class of contextual bandits with context space $\mathcal{C}$ and Gaussian rewards. Then, similar to (1), we can bound $C_{KL}\leq \log|\mathcal{C}|+O(1)$.

(3) Problem classes with bounded observation $\mathcal{O}$. For finite $\mathcal{O}$, we can always bound $C_{KL}\leq \log|\mathcal{O}|$.

More generally, $C_{KL}$ is bounded as long as the models in $\mathcal{M}$ admit uniformly bounded density functions with respect to a common base model. This is indeed the case for most applications, including many control problems and RL problems.

Assumption 3 is a growth condition on the DEC. For a broad range of model classes, including bandits, contextual bandits and structured RL problems (see e.g. [25] and also [23, 9]), the DEC of $\mathcal{M}$ scales as $C\sqrt{\epsilon}$, where $C$ is a quantity depending on the complexity of model class $\mathcal{M}$, and hence the DEC (as a function of $\epsilon$) is indeed of moderate growth for such classes.

Q2. What is in line 329? Is it variance?

A2: Yes, it is variance. We will clarify this in the revision.

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?

A3: For contextual bandits problem, we can directly bound $C_{KL}$ by $\log|\mathcal{C}|$, which is a logarithmic factor and hence hidden in $\lesssim$. We will clarify this in the revision.

Q4. Can the ideas in this work be extended to the RL setup?

A4: Yes, the RL setup is encompassed by the DMSO framework [9], so our results can be applied as-is. It has been shown in [25, 9] that many existing lower bounds for RL problems can be recovered by the DEC framework, and hence the ideas of this work can be directly applied to RL setup. Further, when applied to the RL setup, our framework can give more powerful results than the commonly used Fano method and DEC method, and hence we expect it to provide a unified perspective for proving lower bounds for RL problems.

Q5. Can the ideas in this work be extended to the case of interactive decision-making with multiple agents?

A5: Yes, the problem of equilibrium computation in multi-agent decision making is encompassed by the DMSO framework [21], so our results can be applied as-is. In particular, the lower bounds in [21] can also be recovered by our framework through Theorem 6.

Dear reviewer,

Thanks for your work on this submission. Can you please interact with authors at this stage? At a minimum this would require acknowledging their rebuttal and saying whether you intend to change your score.

Best, Roberto

Thank you for your insightful feedback and for dedicating time to review our paper! We respond to the specific questions as follows:

1. 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.

Thank you for the feedback. We will be sure to include a detailed proof for Corollary 2 for readers less familiar with these sorts of manipulations.

2. There seem to be a lot of (minor) typos in Lemma 3, and it's proof.

Firstly, it's better to clarify whether sets $\theta_0,\theta_1$ are required to be distinct or not in the Lemma statement.

In the most general case, $\Theta_0$ and $\Theta_1$ do not have to be distinct. It could be implied to be distinct if the loss function $L$ satisfies $L(\theta,\theta) = 0$ for all $\theta\in \Theta$.

ASDM is not defined in the first line of proof. We apologize for the typo. This line is meant to say “ISDM”.

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?

Yes, it will contain a factor of 1/2, and it is an inequality due to the convexity of TV distance. And yes, the next step follows by data-processing inequality.

In line 603, $d_{3/4}(\cdot,\cdot)$ is not defined. May be authors mean $d_{d,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?

In line 574, we defined $d_{f,\delta}$. In line 603, we mean $d_{|\cdot|, 1/4}$ where $f(x)=|x|$, which yields the TV distance. We then apply Theorem D.1 with $f(x)=|x|$ and $\delta=1/4$.

There seems to be a typo in the subscripts of expectation in line 604, third inequality.

We apologize for the typo. This should be $\mathbb{E}_{M\sim\mu}\mathbb{E} _{X\sim {\mathbb{P}^{M,`ALG`}}}[\ell(M,X)]$.

3. 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).

The output decision $\pi_{\text{out}}$ is the decision $\hat{\pi}$ in line 104, and the output policy $p_{\text{out}}$ is the distribution over the output decision $\pi_{\text{out}}$. We will make sure to add these explanations.

4. 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.

Without the realizability assumption, the lower bound still holds since the model can be arbitrary. The realizability assumption is required for the upper bound, e.g., the last inequality of line 835 in Theorem F.2. When the realizability assumption is not satisfied, the algorithm of EXO+ is not known to adapt to misspecification, so no results can be established.

Assumption 2 is a relatively mild condition on the model class $\mathcal{M}$. Examples:

(1) Bandits. Suppose that $\mathcal{M}$ is a class of bandits with Gaussian rewards, i.e. $\Pi=\mathcal{A}$ is the action space, and for each $M\in \mathcal{M}$, $a\in\mathcal{A}$, the observation is generated as $o\sim N(f^M(a),1)$. Then, we can consider the reference model $\overline{M}$ with $f^{\overline{M}}(a)\equiv 0$, and $D_{KL}(M(a)||\overline{M}(a))=\frac{f^M(a)^2}{2}$. Therefore, $C_{KL}$ is bounded as long as the mean reward is uniformly bounded for models in the model class $\mathcal{M}$.

(2) Contextual bandits. Suppose that $\mathcal{M}$ is a class of contextual bandits with context space $\mathcal{C}$ and Gaussian rewards. Then, similar to (1), we can bound $C_{KL}\leq \log|\mathcal{C}|+O(1)$.

(3) Problem classes with bounded observation $\mathcal{O}$. For finite $\mathcal{O}$, we can always bound $C_{KL}\leq \log|\mathcal{O}|$.

More generally, $C_{KL}$ is bounded as long as the models in $\mathcal{M}$ admit uniformly bounded density functions with respect to a common base model. This is indeed the case for most applications, including many control problems and RL problems.

5. 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.

We proved in Theorem 5 that $\sup_{M\in\mathcal{M}} \mathbb{P}^{M,`ALG`}\left( g^M(\pi)\geq \Delta \right)> \delta$. Notice the supremum is strictly larger. Thus, by the definition of supremum, there exists one model that is larger than $\delta$.

6. Line 329, I don't think $\mathbb{V}$ is defined.

Thank you for pointing this out. \mathbb{V} is defined as variance. We will be sure to clarify this in the final revision.