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

Authors: fan chen mit
dylan j foster
yanjun  han
alexander  rakhlin
yunbei  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:09:28

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 inequality, 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. 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{Decision Dimension}, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity of estimation. Using the Decision Dimension, we (i) provide a unified characterization of learnability for \emph{any} structured bandit problem, (ii) close the remaining gap between the upper and lower bounds in Foster et al. (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.

Main paper: 
 introduction: 
 The minimax criterion is a standard approach to studying the intrinsic difficulty of problems in statistics and machine learning. Stated (somewhat informally) asEQUATIONwhere the algorithm ALG collects data (either passively or interactively) from the model M and incurs a cost, and the expression reflects the best cost that can be achieved by an algorithm ALG for a worstcase problem instance in a collection M, measured according to an appropriate cost function Cost.In statistics, the minimax approach was pioneered by A. Wald [82] , who made the connection to von Neumann's theory of games [76] and unified statistical estimation and hypothesis testing under the umbrella of statistical decision theory. Minimax optimality and minimax rates of convergence of estimators have since become a central object in the modern of non-asymptotic statistics [74, 81] ; here, for instance, ALG is an estimator of an unknown parameter based on noisy observations.Upper bounds on the minimax value (1) are typically achieved by choosing a particular algorithm, while lower bounds often require specialized techniques. In statistics, three such techniques are widely used: Le Cam's two-point method, Fano's inequality, and Assouad's lemma. These techniques entail constructing "difficult" choices of subsets of the class M. Le Cam's method focuses on two hypotheses, while Assouad's lemma and Fano's inequality involve multiple hypotheses indexed by the vertices of a hypercube and a simplex, respectively. The relationships between these methods are explored in Yu [87] .Classical statistical estimation is a purely passive task. A parallel line of research considers the task of interactive decision making, where ALG is a multi-round procedure that directly interacts with the data generating process and iteratively makes decisions with the (often contradictory) aims of minimizing cost and collecting information. Proving minimax lower bounds for interactive decision making problems presents unique challenges. The aforementioned lower bound techniques for estimation require quantifying the amount of information that can be gained from passively acquired data from a hard problem instance, but the amount information acquired by an interactive algorithm is harder to quantify [3, 61, 62] , since it depends on the decisions made by the algorithm itself over multiple rounds.In spite of the challenges, recent work of Foster et al. [36, 38] provides lower and upper bounds which show that a complexity measure known as the Decision-Estimation Coefficient (DEC) characterizes the minimax rates for a general class of interactive decision making problems (up to a gap which is related to the complexity of a certain induced estimation problem). Interestingly, the proof techniques in Foster et al. [36] proceed in a seemingly different fashion from classical lower bounds for statistical estimation; most notably, their techniques involve an algorithm-dependent (as opposed to oblivious) choice of a hard-to-distinguish alternative problem instance.Given the differences between the classical Assouad, Fano, and Le Cam methods, and the even larger disparity between these methods and the interactive decision making techniques of Foster et al. [36, 38] , it is natural to ask whether there is a hope of unifying these lower bounds techniques.Beyond the fundamental nature of this question, there is hope that a unified understanding might lead to tighter lower bounds, or even inspire new algorithms and upper bounds; of particular interest is to close the remaining gaps between the upper and lower bounds on the minimax rates for interactive decision making left open by Foster et al. [38] , which are closely related to estimation.Contributions. We present a new framework for information-theoretic lower bounds which allows for a unifying presentation of classical lower bounds in statistical estimation (Assouad, Fano, and Le Cam) and recent DEC-based lower bounds for interactive decision making [36, 38] .• Interactive lower bound framework (Section 3). Our main result is to introduce a new lower bound technique, the interactive Fano method. The interactive Fano method generalizes the stringent separation condition in the classical Fano inequality to a novel algorithm-dependent condition by introducing the concept of "ghost data" generated from a reference distribution. This technique recovers the Le Cam two-point method (and convex hull method), Assouad method, and Fano method as special cases. By virtue of being algorithm-dependent in nature, the interactive Fano method seamlessly recovers DEC-based lower bounds for interactive decision making as a special case, and leads to refined quantile-based variants.• Decision dimension and bandit learnability (Section 4). As an application of the interactive Fano method, we derive lower bounds for interactive decision making based on a new complexity measure, the decision dimension, which quantifies the difficulty of estimating a near-optimal policy/decision, and complements the original DEC lower bounds (which reflect difficulty of exploration as opposed to difficulty of estimation). As an application, the decision dimension provides both lower and upper bound for learning any structured bandit problem, up to an exponential gap.In particular, finiteness of the decision dimension is the first necessary and sufficient condition for finite-time learnability of any structured bandit problem. As a secondary result, we use the decision dimension to close the remaining gap between the upper and lower bounds in Foster et al. [36, 38] (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.Related work. Due to space limitations, we discuss the related work in Appendix A.Let P and Q be two distributions over a space Ω such that P is absolutely continuous with respect to Q. Then, for a convex function f : [0, +∞) → (-∞, +∞] such that f (x) is finite for all x > 0, f (1) = 0, and f (0) = lim x→0 + f (x), the f -divergence of between P and Q is defined asD f (P, Q) := Ω f dP dQ dQ.Concretely, we make use of three well-known f -divergences: the KL-divergence D KL , the squared Hellinger distance D 2 H , and the total variation distance D TV , for which the function f (x) is chosen to be x log x, 1 2 ( √ x -1) 2 , and 1 2 |x -1| respectively. For a pair of random variables (X, Y ) with joint distribution P X,Y , the mutual information is defined asI(X; Y ) = E X D KL P Y |X ∥ P Y ,where P Y |X is the conditional distribution of Y |X and P Y is the marginal distribution of Y . 
statistical estimation and interactive decision making: 
 We work in a general framework we refer to as Interactive Statistical Decision Making (ISDM). We adopt this framework as a convenient formalism which encompasses statistical estimation and interactive decision making in a unified fashion.Interactive Statistical Decision Making. An ISDM problem is specified by (X , M, D, L), where X is the space of outcomes, M is a model class (parameter space), D is the space of algorithms, and L is a non-negative risk function. For an algorithm ALG ∈ D chosen by the learner and a model M ∈ M specified by the environment, an observation X is generated from a distribution induced by M and ALG: X ∼ P M,ALG . The performance of the algorithm ALG on the model M is then measured by the risk function L(M, X). The learner's goal is to minimize the risk by choosing the algorithm ALG. As described in the Introduction, the best possible expected risk the learner may achieve is the following minimax risk:EQUATIONWhile main our results concern the general problem formulation in (2) , we focus on applications to statistical estimation and interactive decision making throughout. Below, we give additional background on these settings and show how to view them as special cases.For a general statistical estimation framework known as statistical decision theory [11, 82] , the learner is given the parameter space Θ, observation space Y, decision space A, and a loss function L.For an underlying parameter θ ⋆ ∈ Θ, n i.i.d. samples Y 1 , ..., Y n ∼ P θ ⋆ are drawn and observed by the learner. The learner then chooses a decision A = A(Y 1 , • • • , Y n ) ∈ A based on the observations, and then incurs the loss L(θ ⋆ , A). This framework subsumes most statistical estimation problems.Any general statistical estimation problem can be viewed as a ISDM instance, by choosing the model class as M = {P θ : θ ∈ Θ} and the algorithm space as D = {ALG : Y ⊗n → A}. For model M = P θ and algorithm ALG, the distribution of the whole observation X ∼ P M,ALG is given byX = (Y 1 , • • • , Y n , A), Y 1 , ..., Y n i.i.d ∼ P θ , A = ALG(Y 1 , • • • , Y n ).The loss under model M is then measured by the loss of the decision A, i.e., L(M, X) := L(θ, A).For interactive decision making, we consider the following variant of the Decision Making with Structured Observations (DMSO) framework [36] , which subsumes bandits and reinforcement learning. The learner interacts with the environment (described by an underlying model M ⋆ : Π → ∆(O), unknown to the learner) for T rounds. For each round t = 1, ..., T :• The learner selects a decision π t ∈ Π, where Π is the decision space.• The learner receives an observationo t ∈ O via o t ∼ M ⋆ (π t ),where O is the observation space.The underlying model M ⋆ is formally a conditional distribution, and the learner is assumed to have access to a known model class M ⊆ (Π → ∆(O)) with the following property.Assumption 1 (Realizability). The model class M contains M ⋆ .The model class M represents the learner's prior knowledge of the structure of the underlying environment. For example, for structured bandit problems, the models specify the reward distributions and hence encode the structural assumptions on the mean reward function (e.g. linearity, smoothness, or concavity). For a more detailed discussion, see Appendix B.To each model M ∈ M, we associate a risk function g M : Π → R ≥0 , which measures the performance of a decision in Π. We consider two types of learning goals under the DMSO framework:• Generalized no-regret learning: The goal of the agent is to minimize the cumulative sub-optimality during the course of the interaction, given byEQUATIONwhere π t can be randomly drawn from a distribution p t ∈ ∆(Π) chosen by the learner at step t.• Generalized PAC (Probably Approximately Correct) learning: the goal of the agent is to minimize the sub-optimality of a final output decision π (possibly randomized), which is selected by the learner once all T rounds of interaction conclude. We measure performance viaEQUATIONWith an appropriate choice for g M , the setting captures reward maximization (regret minimization) [36, 38] , model estimation and preference-based learning [19] , multi-agent decision making and partial monitoring [33] , and various other tasks. In the main text, we focus on reward maximization, and defer the results for more general choices g M to the appendices (cf. Appendix B).Example 1 (Reward maximization). Let R : O → [0, 1] be a known reward function. 1 For a modelM ∈ M, E M,π [•] denotes expectation under the process o ∼ M (π), and f M (π) := E M,π [R(o)]denotes the expected value function. An optimal decision is denoted by π M ∈ arg max π∈Π f M (π), and the sub-optimality measure is defined byg M (π) = f M (π M ) -f M (π) .DMSO as an instance of ISDM. Any DMSO class (M, Π) induces an ISDM as follows. For any t ∈ [T ], denote the full history of decisions and observations up to time t by H t-1 = (π s , o s ) t-1 s=1 . The space of observations X consists of all such X that X = H T ∪ { π}, where π is a final decision. An algorithm ALG = {q t } t∈[T ] ∪{p} is specified by a sequence of mappings, where the t-th mapping q t (• | H t-1 ) specifies the distribution of π t based on H t-1 , and the final map p(• | H T ) specifies the distribution of the output decision π based on H T . The algorithm space D consists of all such algorithms. The loss function is chosen to be L(M ⋆ , X) = Reg DM (T ) for no-regret learning (3), and L(M ⋆ , X) = Risk DM (T ) for PAC learning (4). For any algorithm ALG and model M , P M,ALG (•) is the distribution of X = (H T , π) generated by the algorithm ALG under the model M , and we let E M,ALG [•] to be the corresponding expectation. 
a general lower bound: 
 In this section, we introduce our general lower bound technique, the interactive Fano method, and use it to provide minimax lower bounds for the ISDM framework.Theorem 1 (Interactive Fano method). Fix an f -divergence D f . Let ALG be a given algorithm, δ ∈ (0, 1) be a quantile parameter, and µ ∈ ∆(M) be a prior distribution over models. For reference distribution Q on X and parameter ∆ > 0, we defineEQUATIONThen, the following lower bound holds:sup M ∈M E X∼P M,ALG [L(M, X)] ≥ E M ∼µ E X∼P M,ALG [L(M, X)] ≥ δ • sup Q∈∆(X ),∆>0∆ :E M ∼µ D f P M,ALG , Q < d f,δ (ρ ∆,Q ) ,where we denoted f,δ (p) = D f (Bern(1 -δ), Bern(p)) if p ≤ 1 -δ, and d f,δ (p) = 0 otherwise.This result generalizes existing statements of Fano's method in multiple ways:• It encompasses general interactive learning/estimation problems in the ISDM framework, as opposed to purely passive estimation. This is reflected in the fact that the distribution over the outcome X is allowed to depend on ALG itself.• The most important and novel change is that Theorem 1 generalizes the "hard" separation condition required in the classical Fano method to a "soft" notion of separation captured by the quantile ρ ∆,Q in (5) . The quantile ρ ∆,Q reflects the average separation under "ghost data" X generated from an arbitrary reference distribution Q, which is independent of the true model M ∼ µ.• In addition, instead of relying on mutual information, which is can difficult to quantify for interactive problems, we use divergence with respect to the reference distribution Q, generalizing a central idea in Foster et al. [36, 38] .In what follows, we will show that these generalizations allow the Interactive Fano method to achieve two important desiderata: (1) unifying the methods of Fano, Le Cam, and Assouad (Section 3.1), and (2) integrating these traditional lower bound techniques with contemporary interactive decision making lower bounds to derive new lower bound (see Section 3.2).We begin by applying Theorem 1 to recover classical non-interactive lower bounds for statistical estimation. Since a goal of our paper is to integrate the Fano and Assouad methods with the DEC framework, this serves as an important sanity check to demonstrate that our framework can recover the non-interactive versions of these methods.Fano's method. To recover the Fano method, we specialize Theorem 1 to the KL divergence.Observe that for any reference distribution Q,P M ∼µ,X∼Q (L(M, X) < ∆) ≤ sup x µ(M ∈ M | L(M, x) < ∆). By choosing Q = E M ∼µ P M,ALGin Theorem 1, we obtain the following proposition, which encompasses prior generalizations of Fano's inequality [88, 32, 23] developed in statistical estimation.Proposition 2 (Recovering the generalized Fano method). Fix an algorithm ALG and prior distribution µ ∈ ∆(M), and let I µ,ALG (M ; X) be the mutual information between M and X under M ∼ µ and X ∼ P M,ALG . The following Bayes risk lower bound holds for all ∆ ≥ 0:EQUATIONWhen applied to the statistical estimation setting (Section 2.1), the classical Fano inequality corresponds to the special case of Proposition 2 where Θ = A = {1, 2, . . . , m}, L(θ, a) = 1(θ ̸ = a) is the indicator loss, µ = Unif(Θ) is the uniform prior, and ∆ = 1.Note that in Proposition 2, the term log sup x µ(M ∈ M : L(M, x) < ∆) in the denominator of (6) takes the supremum over the outcome x, resulting in a simplified expression that removes the role of the algorithm ALG. This simplification is often sufficient to derive tight guarantees for estimation, but is insufficient for interactive decision making in general. The DEC, which we define in Section 3.2, more precisely accounts for the role of decisions selected by the algorithm.Le Cam's method and Assouad's method. To recover Le Cam's two-point method and Assouad's method from Theorem 1, we appeal to the following result, which recovers a more general lower bound known as the Le Cam convex hull method [54, 87] .Proposition 3 (Recovering Le Cam's convex hull method). For a parameter space Θ and observation space Y, consider a class of distributionsP = {P θ | θ ∈ Θ} indexed by Θ, P θ ∈ ∆(Y ⊗n ). Let L : Θ × A → R + be a loss function. Suppose Θ 0 ⊆ Θ and Θ 1 ⊆ Θ satisfy the separation condition L(θ 0 , a) + L(θ 1 , a) ≥ 2∆, ∀a ∈ A, θ 0 ∈ Θ 0 , θ 1 ∈ Θ 1 . Suppose that there exist probability measures ν 0 ∈ ∆(Θ 0 ) and ν 1 ∈ ∆(Θ 1 ) such that D TV (ν 0 ⊗ P θ , ν 1 ⊗ P θ ) ≤ 1/2, where ν i ⊗ P θ is the distribution on Y ⊗n induced by θ ∼ ν i , Y 1 , . . . , Y n ∼ P θ for i ∈ {0, 1}. Then inf ALG sup θ∈Θ E Y1,...,Yn∼P θ L(θ, ALG(Y 1 , . . . , Y n )) ≥ ∆/4,where the infimum is taken over all algorithms ALG : Y ⊗n → A.Le Cam's convex hull method is the most general formulation of the Le Cam two-point method, which-in its most basic form-corresponds to the case in which ν 0 and ν 1 are singletons. The convex hull method is also capable of recovering Assouad's method [87] . It is important to note that the classical Fano inequality, e.g. in the form of Proposition 2, cannot recover Proposition 3. This is because of fundamental differences between the divergences (KL versus TV) used in the traditional Fano method and convex hull method.Within the DMSO framework (Section 2.2), Foster et al. [36, 38] introduced the Decision-Estimation Coefficient (DEC) as a complexity measure, providing both upper and lower bounds for any model class M. We now show how to recover the lower bounds of Foster et al. [36, 38] through Theorem 1.We focus on the lower bounds from Foster et al. [38] , which are based on a variant of the DEC called the constrained DEC, and provide the tightest guarantees from prior work.Background on the Decision-Estimation Coefficient. Consider the reward maximization setting (Example 1) under DMSO. For a model class M and a reference modelEQUATIONand define the constrained PAC-DEC viap-dec c ε (M, Ď M ) := inf p,q∈∆(Π) sup M ∈M E π∼p [g M (π)] | E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 . (8)Here, the superscript "c" indicates "constrained", and the superscript "r" (resp. "p") indicates "regret" (resp. "PAC"). We further definep-dec c ε (M) = sup Ď M ∈co(M) p-dec c ε (M, Ď M ), r-dec c ε (M) = sup Ď M ∈co(M) r-dec c ε (M ∪ { Ď M }, Ď M ),where co(M) denotes the convex hull of the model class M.Based on these complexity measures, Foster et al. [38] (see also Glasgow and Rakhlin [40] ) provide the following lower and upper bounds on optimal risk and regret, under mild growth conditions on the DECs.Theorem 4 (Informal; Foster et al. [38] ). Consider the reward maximization variant of the DMSO setting (Example 1). For any model class M and T ∈ N, the following lower and upper bounds hold:(1) For PAC learning,p-dec c ε(T ) (M) ≲ inf ALG sup M ∈M E M,ALG [Risk DM (T )] ≲ p-dec c ε(T ) (M),where ε(T ) ≍ 1/T and ε(T ) ≍ log|M|/T (up to logarithmic factors).(2) For no-regret learning,r-dec c ε(T ) (M) • T ≲ inf ALG sup M ∈M E M,ALG [Reg DM (T )] ≲ r-dec c ε(T ) (M) • T + T • ε(T ).Therefore, up to the log|M|-gap between the parameters ε(T ) and ε(T ) appearing in the lower and upper bounds, the constrained PAC-DEC tightly captures the minimax risk of PAC learning, and the constrained regret-DEC captures the minimax regret of no-regret learning.A new complexity measure: The quantile Decision-Estimation Coefficient. We recover the DEC-based lower bounds from Foster et al. [38] through a new variant we refer to as the quantile DEC. To do so, we briefly recount the proof technique used by Foster et al. [38] .Given an algorithm ALG, the proof strategy is to first fix an arbitrary reference model Ď M , then adversarially choose a hard alternative model M ∈ M (in a way that is guided by the DEC and the algorithm ALG itself) such that D TV (P M,ALG , P Ď M ,ALG ) is small, yet ALG cannot achieve low risk on model M . This lower bound technique does not explicitly require a separation condition between M and Ď M , which is a departure from the classical Fano and two-point methods. Thus to recover it, the lack of an explicit separation condition in Theorem 1 will be critical. More precisely, for any model M , we consider the following distributions over decisions:q M,ALG = E M,ALG 1 T T t=1 q t (• | H t-1 ) ∈ ∆(Π), p M,ALG = E M,ALG p(H T ) ∈ ∆(Π). (9)That is, q M,ALG is the expected empirical distribution over the decisions (π 1 , • • • , π T ) played by the algorithm under M , and p M,ALG is the expected distribution of the final decision π.With these definitions, we instantiate Theorem 1 with the Hellinger distance. We will use the subadditivity of Hellinger distance (Lemma C.1; Foster et al. [36, 39] ), which allows us to boundEQUATIONTheorem 1 then yields the following intermediate result.Lemma 5 (Interactive Fano method lower bound for interactive decision making). Let δ ∈ [0, 1] be given, and consider an algorithm ALG. Define∆ ⋆ ALG,δ := sup Ď M ∈co(M) sup M ∈M sup ∆≥0 ∆ : p Ď M ,ALG (π : g M (π) ≥ ∆) > δ + 14T E π∼q Ď M ,ALG D 2 H M (π), Ď M (π) .Then there exists M ∈ M such that P M,ALG g M ( π) ≥ ∆ ⋆ ALG,δ ≥ δ. Using Lemma 5, as a starting point, we derive a new quantile-based variant of the DEC, which we will show can be viewed as a slight generalization of the original PAC DEC of Foster et al. [38] .For any model M ∈ M and any parameter δ ∈ [0, 1], we define the δ-quantile risk as follows:g M δ (p) = sup ∆≥0 {∆ : P π∼p (g M (π) ≥ ∆)≥ δ}; this serves as a measure of the sub-optimality of the distribution p ∈ ∆(Π) in terms of δ-quantile. We now define the quantile PAC DEC as follows:EQUATIONand define p-dec q ε,δ (M) := supĎ M ∈co(M) p-dec q ε,δ (M, Ď M ).Applying Lemma 5, it is immediate to see that the quantile PAC-DEC provides a lower bound on the PAC risk.Theorem 6 (Quantile DEC lower bound). Let any T ≥ 1 and δ ∈ [0, 1) be given, and define ε δ (T ) := 1 14 δ T . Then, for any algorithm ALG, there exists M ⋆ ∈ M such thatP M ⋆ ,ALG Risk DM (T ) ≥ p-dec q ε δ (T ),δ (M) ≥ δ 2 .Unlike the original constrained DEC lower bounds (Theorem 4), which are restricted to the reward maximization variant of the DMSO setting (Example 1), the quantile DEC lower bound in Theorem 6 holds for any suboptimal measure g M . As a result, the lower bound applies to a broader range of generalized PAC learning tasks, including model estimation [19] and multi-agent decision making [33] , where DEC-based lower bounds from prior work are loose in general; as a concrete application, we derive a new lower bound for interactive estimation (Example 3) in Appendix E.2.Recovering DEC-based lower bounds using the quantile DEC. At first glance, Theorem 6 might appear to be weaker than the constrained PAC-DEC lower bound in Theorem 4 due to the loose conversion from quantile risk to expected risk. However, by specializing to reward maximization (Example 3) and leveraging the structure of the sub-optimality measure g M , we show that quantile PAC-DEC is equivalent to its constrained counterpart for this setting, leading to a tight lower bound.Proposition 7 (Recovering the PAC DEC lower bound). Under the reward maximization setting (Example 1), for any ε > 0 and δ ∈ [0, 1) it holds thatp-dec c ε (M) ≤ p-dec q √ 2ε,δ (M) + 4ε 1-δ .As a corollary, we may choose δ = 1 2 and ε(T ) = 1 20 √T in Theorem 6, so thatsup M ∈M E M,ALG [Risk DM (T )] ≥ 1 4 p-dec q √ 2ε(T ),1/2 (M) ≥ 1 4 p-dec c ε(T ) (M) -8ε(T ) .Thus, the quantile PAC-DEC lower bound indeed recovers the constrained PAC-DEC lower bound in Theorem 4.Our quantile DEC lower bound extends to regret with minor modifications, allowing us to recover the regret lower bounds in Theorem 4. We defer the details to the Appendix E.1 (Theorem E.1).The following result uses Theorem 1 to extend classical Fano method to interactive decision making and achieves tight dependence on the problem dimension that is not recovered by the standard DEC lower bound in Foster et al. [36, 38] .Proposition 8 (Mutual information-based lower bound). Consider the DMSO setting. For any T ≥ 1 and prior µ ∈ ∆(M), we define the maximum T -round mutual information asI µ (T ) := sup ALG I µ,ALG (M ; H T ),where the supremum is taken over all possible DMSO algorithms ALG. Then for any algorithm ALG,sup M ∈M E M,ALG [g M ( π)] ≥ 1 2 sup µ∈∆(M) sup ∆>0 ∆ | sup π µ(M : g M (π) ≤ ∆) ≤ 1 4 exp(-2I µ (T )) .Using Proposition 8, along with mutual information bounds from Rajaraman et al. [ EQUATIONIn Section 4, we also instantiate Proposition 8 to derive a new complexity measure for DMSO. 
application to interactive decision making: bandit learnability and beyond: 
 In this section, we focus on the DMSO setting and apply our general results (Theorem 1) to derive new lower and upper bounds for interactive decision making that go beyond the previous results based on the Decision-Estimation Coefficient [36, 38] Reg ⋆ T := inf ALG sup M ∈M E M,ALG [Reg DM (T )].Given a parameter ∆ > 0, we define the minimax sample complexityEQUATIONas the least value T for which there exists an algorithm that achieves ∆T regret. Clearly, characterizing T ⋆ (M, ∆) is equivalent to characterizing the minimax regret Reg ⋆ T . Consider the following quantity induced by DEC for a class M and parameter ∆ > 0:EQUATION)With this definition, Theorem 4 is equivalent to the following characterization of the minimax sample complexity T ⋆ (M, ∆):EQUATION)That is, Theorem 4 characterizes the minimax sample complexity up to a multiplicative log|M| factor. Our main result in this section will be to use the decision dimension and interactive Fano method (Theorem 1), to (i) tighten (15) for various special cases of interest, and (ii) give a new characterization for T ⋆ (M, ∆) in structured bandit problems which avoids spurious parameters such as log|M| altogether.For the a model class M and parameter ∆ > 0, we define the decision dimension as follows:EQUATIONInformal, the decision dimension value Ddim ∆ (M) represents the best possible coverage over ∆optimal decisions that can be achieved through a single exploratory distribution in the face of an unknown model M ∈ M. As will now show, this quantity naturally arises as a lower bound on optimal risk through the interactive Fano method. We begin with the following regularity assumption.Assumption 2 (Regular model class). There exists a constant C KL > 0 and a reference modelĎ M such that D KL (M (π) ∥ Ď M (π)) ≤ C KL for all M ∈ M and π ∈ Π.Assumption 2 is a mild assumption on the boundedness of KL divergence. As an example, for structured bandits with means in [0, 1] and Gaussian rewards, Assumption 2 holds with C KL = 1 2 . Details and more examples are provided in Appendix B.1. Our main lower bound based on the decision dimension follows by specializing Theorem 1 to KL divergence.Theorem 10 (Decision dimension lower bound). Suppose that M satisfies Assumption 2 with parameter C KL > 0. Then for any algorithm ALG and ∆ > 0, unless T < log Ddim2∆(M)-2, there existsM ⋆ ∈ M such that P M ⋆ ,ALG [g M ⋆ ( π) ≥ ∆] ≥ 1 2 .In particular, decision dimension also implies a regret lower bound through Theorem 10: That is, for any algorithm to achieve ∆T -regret, it is necessary to have T = Ω(log Ddim 2∆ (M)). Combining this with Theorem 4, we conclude that boundedness of both the DEC and the decision dimension is necessary for learning with any model class M.Upper bounds based on the decision dimension. We now complement Theorem 10 by showing that for any reward maximization instance of the DMSO setting (Example 1), boundedness of the decision dimension alone is also sufficient to derive upper bounds on the sample complexity of learning. The caveat is that while the lower bound is logarithmic in Ddim ∆ (M), the upper bound will be polynomial.. There exists an algorithm that for any class M and ∆ > 0, ensures that with probability at least 1 -δ,Reg DM (T ) ≤ T • ∆ + O(log(1/δ)) • T • Ddim ∆ (M).Combining Theorem 10 and Theorem 11 yields the following bounds on T ⋆ (M, ∆) (omitting polylogarithmic factors):EQUATION)The gap between the lower and upper bounds of ( 17) is exponential; however, for model classes with C KL = O(1), (17) suffices to characterize finite-time learnability. As a special case, we now show that decision dimension characterizes the learnability of any structured bandit problem.We consider a structured bandit setting given by a reward function class H ⊆ (Π → [0, 1]). The protocol is as follows: For each round t ∈ [T ], the learner chooses a decision π t ∈ Π, then receives a reward r t ∼ N(h ⋆ (π t ), 1) in response, where the mean reward function h ⋆ ∈ H. This corresponds to an instance of the DMSO framework with induced model classM H = {π → N(h(π), 1) | h ∈ H}.We define the decision dimension for H viaEQUATIONwhere we denote π h := arg max π∈Π h(π). This exactly coincides with the notion of maximin volume of Hanneke and Yang [41] , which was shown to give a tight characterization of learnability for the special case of noiseless binary-valued structured bandits. We discuss the connection to Hanneke and Yang [41] in more detail in Appendix H.1.It is straightforward to show that for any structured bandit problem, the induced class M H satisfies Assumption 2 with C KL = 1 2 (Example 4). This leads to the following lower bound.Corollary 12 (Lower bound for stochastic bandits). For the bandit model class M H defined as above, it holds thatT ⋆ (M H , ∆) ≥ 2Ddim ∆ (H) -2.Combining this result with the upper bound in Theorem 11, we obtain the following bounds on the minimax-optimal sample complexity for the structure bandit problem with class H:EQUATION) This implies that Ddim ∆ (H) characterizes learnability for structured bandits.Theorem 13 (Structured bandit learnability). For a given reward function class H, the bandit problem class M H is learnable for finite T if and only if Ddim ∆ (H) < +∞ for all ∆ > 0.We remark that the lower and upper bound in (19) cannot be improved in terms of the decision dimension alone: (1) For K-armed bandits, we have Ddim ∆ (H) ≤ K, meaning the upper bound is tight. (2) For d-dimensional linear bandits, we have log Ddim ∆ (H) = Ω(d), meaning the lower bound is nearly tight. Nevertheless, the exponential gap in ( 19) can be partly mitigated by combining the decision dimension with the DEC, as we will show in Section 4.3.Our characterization bypasses impossibility results of Hanneke and Yang [41] , who show that for noiseless structured bandit problems, there exist classes H for which bandit learnability is independent of the axioms of ZFC. Therefore, their results rule out the possibility of a characterization of noiseless bandit learnability through any combinatorial dimension [10] for the problem class. Our characterization is compatible with this result because the argument of Hanneke and Yang [41] relies on the noiseless nature of the bandit problem, and hence does not preclude a characterization for the noisy setting. In addition, the decision dimension is not a combinatorial dimension under the definition of Ben-David et al. [10] . Additional discussion is deferred to Appendix H.1.In this section, we derive tighter upper bounds that scale with log Ddim ∆ (M) by combining the decision dimension with the Decision-Estimation Coefficient. For simplicity of presentation, we focus on regret minimization under the setting of Example 1, and we assume the following condition to simplify our bounds (the fully general upper bound is detailed in Appendix G).d : [0, 1] → R is said to have moderate decay if d(ε) ≥ 10ε ∀ε ∈ [0, 1], and there exists a constant c ≥ 1 such that c d(ε) ε ≥ d(ε ′ ) ε ′ for all ε ′ ≥ ε. We assume the function ε → r-dec c ε (co(M)), as a function of ε, satisfies moderate decay for a constant c reg ≥ 1.This condition essentially requires that the DEC for co(M) exhibits moderate growth, which means that learning with co(M) is not "too easy".We now state our upper bound, which tightens Theorem 4 by replacing the log|M| dependence in the upper bound with log Ddim ∆ (M) (with the caveat that the upper bound scales with the DEC for the convexified model class co(M)).Theorem 14 (Upper bound with DEC and decision dimension). Consider the reward maximization variant of the DMSO setting. Let M be any class for which Assumption 3 holds, and assume that Π is finite. Let ε(T ) ≍ log Ddim ∆ (M)/T . Then for any ∆ > 0, Algorithm 1 (see Appendix G) ensures that with high probability,Reg DM ≤ T • ∆ + O c reg T √ log T • r-dec c ε(T ) (co(M)).Restating this upper bound in terms of minimax sample complexity and combining it with the preceding lower bounds yields the following result.Theorem 15. For any class M that satisfies Assumption 2 and 3, we haveEQUATIONup to dependence on c reg and logarithmic factors.In particular, when the model class M is convex (i.e. co(M) = M) and C KL = O(1), Theorem 15 provides lower and upper bounds for learning with M that match up to a quadratic factor. Indeed, for convex model classes, the upper bound of ( 20) is always tighter than (15) (and also tighter than the result in Foster et al. [36, 37] ), as by definition we have log Ddim ∆ (M) ≤ log Ddim 0 (M) ≤ min {log |M|, log |Π|} , ∀∆ > 0. As applications, we apply Theorem 15 to structured bandits and contextual bandits (Appendix H). In what follows, we briefly survey the most relevant related work.There is a vast body of literature on minimax risk bounds for statistical estimation, including Hasminskii and Ibragimov [42] , Bretagnolle and Huber [14] , Birgé [12] , Donoho and Liu [29] , Cover and Thomas [25] , Ibragimov and Has'Minskii [43] , Tsybakov [73] as well as references therein. For minimax lower bounds, the most widely applied techniques are Le Cam's two-point method [54] , Assouad's lemma [7] , and Fano's inequality [25] . Variants and applications of these three methods abound [1, 23, 60, 32 ]; Fano's inequality in particular has perhaps the largest number of variants, of which the most general version we are aware of is due to Chen et al. [23] , which is recovered by our results (Proposition 2). Another celebrated thread, starting from the seminal work of Donoho and Liu [28] , provides upper and lower bounds for a large class of non-parametric estimation problems based on Le Cam's two-point method through the study of a complexity measure known as the modulus of continuity [29, 30, 53, 60] . Specifically, for a functional T : M → R on the space of probability models M, the modulus of continuity is defined asEQUATION)Decision-Estimation Coefficient and Information Ratio. For interactive decision making problems Foster et al. [36, 38] introduce Decision-Estimation Coefficient (DEC) as a complexity measure and show that it characterizes the minimax-optimal regret up to a log|M| factor. The DEC can be viewed as an interactive counterpart of the modulus of continuity in (21) , and captures hardness of interactive decision making related to exploration, but not necessarily estimation. An active line of research has built on the DEC to encompass a variety of more increasing general decision making settings [36, 37, 19, 38, 33, 40] , including adversarial decision making [37] , PAC decision making [19, 38] , reward-free learning and preference-based learning [19] , and multi-agent decision making and partial monitoring [33] .The DEC is closely related to a Bayesian complexity measure known as the information ratio [67, 68, 50, 49, etc.] ,which was originally introduced to analyze Bayesian algorithms such as posterior sampling. It is also related to a more recent generalization known as the algorithmic information ratio (AIR) [86] , developed for frequentist algorithms. Additionally, the DEC is connected to asymptotic instance-dependent complexity, as explored by [79] . Learnability in statistical learning and decision making. In the literature on statistical learning, there is a long line of work which characterizes learnability (i.e., asymptotic achievability of non-trivial sample complexity) of hypothesis classes in terms of abstract complexity measures. Examples include the Vapnik-Chervonenkis dimension for binary classification [75, 13] , the Littlestone dimension [56] for online classification [9] and differentially private classification [16, 5] , and their real-valued counterparts (e.g. scale-sensitive dimensions) for regression [8, 4] .Beyond the settings above-and in particular for interactive settings-learnability is less well understood. The question of what complexity measure characterizes bandit learnability has been raised in e.g. Simchowitz et al. [71] . Remarkably, Ben-David et al. [10] demonstrate that there exist simple and natural learning for which it is impossible to characterize learnability through any combinatorial dimension. More recently, Hanneke and Yang [41] provide similar impossibility results for characterizing learnability of structured bandits in a noiseless setting with real-valued rewards. Hanneke and Yang [41] complement this with a positive result for the case of binary-valued rewards, characterizing learnability through a complexity measure called the maximin volume. Our learnability characterization for noisy structured bandits generalizes this complexity measure.The DMSO framework (Section 1.1) encompasses a wide range of learning goals beyond the reward maximization setting [36, 38] , including reward-free learning, model estimation, and preferencebased learning [19] , and also multi-agent decision making and partial monitoring [33] . We provide two examples below for illustration.Example 2 (Preference-based learning). In preference-based learning, each model M ∈ M is assigned with a comparison functionC M : Π × Π → R (where C M (π 1 , π 2 ) typically the probability of τ 1 ≻ τ 2 for τ 1 ∼ (M, π 1 ), τ 2 ∼ (M, π 2 )), and the risk function is specified by g M (π) = max π ⋆ C M (π ⋆ , π). Chen et al. [19] provide lower and upper bounds for this setting in terms of Preference-based DEC (PBDEC).Example 3 (Interactive estimation). In the setting of interactive estimation (a generalized PAC learning goal), each model M ∈ M is assigned with a parameter θ M ∈ Θ, which is the parameter that the agent aims to estimate. The decision space Π = Π 0 × Θ, where each decision π ∈ Π consists of π = (π 0 , θ), where π 0 is the explorative policy to interact with the model2 , and θ is the estimator of the model parameter. In this setting, we define g M (π) = Dist(θ M , θ) for certain distance Dist(•, •).This setting is an interactive version of the statistical estimation task, and it is also a generalization of the model estimation task studied in Chen et al. [19] . Natural examples include estimating some coordinates of the parameter θ in linear bandits. We provide nearly tight guarantee for this setting in Appendix E.2.Our general interactive Fano method Lemma 5 applies to any generalized no-regret / PAC learning goal (Section 1.1). Therefore, our risk lower bound in terms of quantile PAC-DEC Theorem 6 and decision dimension lower bound Theorem 10 both apply to any generalized learning goal. For a concrete example, see Appendix E.2 for the application to interactive estimation.In this section, we provide three general types of model classes where Assumption 2 holds with mild C KL . It is worth noting that in Assumption 2, the reference model Ď M does not necessarily belong to co(M).Example 4 (Gaussian bandits). Suppose that H ⊆ (A → [0, 1]) is a class of mean value function, and M H,V is the class of the model M associated with a h M ∈ H:M (π) = N(h M (π), 1), π ∈ A.Then, consider the reference model Ď M given by Ď M (π) = N(0, 1)∀π ∈ A. It is clear that for any π, and modelM ∈ M H,V , D KL (M (π) ∥ Ď M (π)) = 1 2 h M (π) 2 ≤ 1 2 ,and hence Assumption 2 holds with C KL = 1 2 . Example 5 (Problems with finite observations). Suppose that the observation space O is finite. Then, consider the reference model Ď M given by Ď M (π) = Unif(O)∀π ∈ Π. It holds thatD KL (M (π) ∥ Ď M (π)) ≤ log |O|, ∀π ∈ Π,and hence Assumption 2 holds with C KL = log |O|.Example 5 can further be generalized to infinite observation space, as long as every model in M admits a bounded density function with respect to the same base measure. The factor of log |C| in Example 6 is due to the definition (39) of log Ddim ∆ (H), where we take supremum over all context distribution µ. This factor can be removed if we instead restrict the model class to have a common context distribution (i.e., the setting where context distribution is known or can be estimated from samples).Lemma C.1 (Sub-additivity for squared Hellinger distance, see e.g. [31, Lemma 9.5.3] [39, Lemma D.2] ). Let (X 1 , F 1 ), . . . , (X T , F T ) be a sequence of measurable spaces, and let X t = t i=1 X i and F t = t i=1 F i . For each t, let P t (• | •) and Q t (• | •) be probability kernels from (X t-1 , F t-1 ) to (X t , F t ).Let P and Q be the laws of X 1 , . . . , X T under X t ∼ P t (• | X 1:t-1 ) and X t ∼ Q t (• | X 1:t-1 ) respectively. Then it holds thatEQUATIONIn particular, given a T -round algorithm ALG and a model M , we can consider random variables X 1 = (π 1 , o 1 ), • • • , X T = (π T , o T ). Then, P M,ALG (X t = • | X 1:t-1 ) is the distribution of (π t , o t ), where π t ∼ p t (• | π 1 , o 1 , • • • , π t-1 , o t--log E [ exp(-X s )| F s-1 ] ≤ t s=1 X s + log (1/δ) .Lemma C.4. For any pair of random variable (X, Y ), it holds thatE X∼P X D 2 H P Y |X , Q Y |X ≤ 2D 2 H (P X,Y , Q X,Y ) .Lemma C.5. Suppose that for a random variable X, its mean and variance under P is µ P and σ 2 P , and its mean and variance under Q is µ Q and σ 2 Q . Then it holds that|µ P -µ Q | 2 ≤ 4 σ 2 P + σ 2 Q + 1 2 |µ P -µ Q | 2 D 2 H (P, Q) .In particular, whenµ P , µ Q , σ P , σ Q ∈ [0, 1], we have D 2 H (P, Q) ≥ 1 10 |µ P -µ Q | 2 .On the other hand, when P = N(µ P , 1),Q = N(µ Q , 1), then D 2 H (P, Q) ≤ 1 8 |µ P -µ Q | 2 .Proof. Let ν = P+Q 2 be the common base measure and set µ = µ P +µ Q.Then|µ P -µ Q | 2 = |E P [X -µ] -E Q [X -µ]| 2 = E ν dP dν - dP dν (X -µ) 2 ≤ E ν   dP dν - dP dν 2   E ν   dP dν + dP dν 2 (X -µ) 2   ≤ 2D 2 H (P, Q) • 2 E P (X -µ) 2 + E Q (X -µ) 2 = 4 σ 2 P + σ 2 Q + 1 2 |µ P -µ Q | 2 D 2 H (P, Q) .In this section, we present proofs for the results in Section 3, except Section 3.2.In the following, we fix a prior µ ∈ ∆(M), quantile δ > 0, f -divergence D f , and an algorithm ALG.We first note that the risk of ALG under prior µ is lower bounded byE M ∼µ E X∼P M,ALG [L(M, X)] ≥∆ • P M ∼µ,X∼P M,ALG (L(M, X) ≥ ∆).It remains to show the following claim.Claim. Suppose that there exists a reference distribution Q such thatd f,δ (ρ ∆,Q ) > E M ∼µ D f P M,ALG , Q , then P M ∼µ,X∼P M,ALG (L(M, X) ≥ ∆) ≥ δ.We denote ρ∆ = P M ∼µ,X∼P M,ALG (L(M, X) < ∆), and recall that we define ρ ∆,Q = P M ∼µ,X∼Q (L(M, X) < ∆). We then consider the following two distributions over M × X :P 0 : M ∼ µ, X ∼ P M,ALG , P 1 : M ∼ µ, X ∼ Q.By the data processing inequality of f -divergence, we haveD f (ρ ∆ , ρ ∆,Q ) ≤ D f (P 0 , P 1 ) = E M ∼µ D f P M,ALG , Q . Therefore, using d f,δ (ρ ∆,Q ) > E M ∼µ D f P M,ALG , Q , we know that d f,δ (ρ ∆,Q ) > D f (ρ ∆ , ρ ∆,Q ).In particular, we know ρ ∆,Q < 1 -δ. Hence, there are two cases:EQUATIONρ∆ > ρ ∆,Q , and we can use the monotone property of D f (Lemma D.1), which also implies ρ∆ ≤ 1 -δ. This immediately givesP M ∼µ,X∼P M,ALG (L(M, X) ≥ ∆) = 1 -ρ∆ ≥ δ.Hence, the proof is completed.Lemma D.1. For x, y ∈ (0, 1), the quantity D f (x, y) is increasing with respect to x when x ≥ y.Proof of Lemma D.1 By definition, we know thatD f (x, y) = yf x y + (1 -y)f 1 -x 1 -y .For any x > z ≥ y, we denotea x = x y , b x = 1 -x 1 -y , a z = z y , b z = 1 -z 1 -y ,and then because f is convex, we knowa z -b x a x -b x f (a x ) + a x -a z a x -b x f (b x ) ≥ f (a z ), b z -b x a x -b x f (a x ) + a x -a z a x -b z f (b x ) ≥ f (b z ).Notice that ya z + (1 -y)b z = 1, and henceyf (a z ) + (1 -y)f (b z ) ≤ yf (a x ) + (1 -y)f (b x ).This gives D f (x, y) ≥ D f (z, y).Q = E M ∼µ P M,ALG . Then, by the choice of Q and definition of KL-divergence, we haveE M ∼µ D f P M,ALG , Q = I µ,ALG (M ; X),and by definition, we haveEQUATIONFor any δ ∈ (0, 1) and ∆ > 0, we apply Theorem 1 to obtain that whenEQUATIONwe haveEQUATIONNote that the KL-divergence between Bern(1 -δ) and Bern(ρ ∆,Q ) is lower bounded byEQUATIONwhere the third inequality is by Jensen's inequality, and the last inequality is by (23) .Takingδ = 1 + I µ,ALG (M ; X) + log 2 log sup x µ(M ∈ M : L(M, x) < ∆) ,we know from ( 26) that ( 24) is true so that the result (25) holds, which proves Corollary 2.We frame the problem in the ISDM framework, where each algorithm corresponds to an estimator θ : Y ⊗n → Θ. Let the model class M = {M 0 , M 1 }, where for each estimator ALG (regarded as an algorithm), P M 0 ,ALG is the distribution of X ∈ A generated byX ∼ M 0 : θ ∼ ν 0 , Y 1 , . . . , Y n ∼ P θ , X = ALG(Y 1 , . . . , Y n ),and P M 1 ,ALG is the distribution of X ∈ A generated byX ∼ M 1 : θ ∼ ν 1 , Y 1 , . . . , Y n ∼ P θ , X = ALG(Y 1 , . . . , Y n ).We further define the new loss for M i , i ∈ {0, 1}:ℓ(M i , X) := inf θ∈supp(νi) L(θ, X), ∀X ∈ A.By the separation condition on Θ 0 and Θ 1 , we have for anyX ∈ A, ℓ(M 0 , X) + ℓ(M 1 , X) ≥ 2∆.This implies thatP M ∼µ (ℓ(M, X) ≥ ∆) ≥ 1/2, ∀X ∈ Θ.Therefore, choosing prior µ = Unif({0, 1}) and referenceQ = E M ∼µ P M,ALG gives ρ ∆,Q = P M ∼µ,X∼Q (ℓ(M, X) < ∆) ≤ 1/2,andE M ∼µ [D TV P M,ALG , Q ] = 1 2 D TV P M0,ALG , Q + D TV P M1,ALG , Q ≤ 1 2 D TV P M0,ALG , P M1,ALG ≤ 1 2 D TV (ν 0 ⊗ P θ , ν 1 ⊗ P θ ) ≤ 1 4 ,where the first inequality is by the convexity of the TV distance and the second inequality is by the data-processing inequality. This shows thatE M ∼µ [D TV (P M,ALG , Q)] ≤ 1/4 ≤ d |•|,1/4 (ρ ∆,Q ).Therefore, applying Theorem 1 givessup θ∈Θ E Y1,...,Yn∼P θ [L(θ, ALG(Y 1 , . . . , Y n ))] ≥ E θ∼ ν 0 +ν 1 2 E Y1,...,Yn∼P θ [L(θ, ALG(Y 1 , . . . , Y n ))] ≥ E M ∼µ E Y1,...,Yn∼P M,ALG [ℓ(M, ALG(Y 1 , . . . , Y n ))] ≥ E M ∼µ E X∼P M,ALG [ℓ(M, X)] ≥ ∆ 4 ,where the second inequality follows from the fact thatE Y1,...,Yn∼P θ [L(θ, ALG(Y 1 , . . . , Y n ))] ≥ E Y1,...,Yn∼P θ [ℓ(M i , ALG(Y 1 , . . . , Y n ))], θ ∈ supp(ν i ),and the last inequality follows from Theorem 1 with δ = 1 4 . This gives the desired result.Consider the following setup of linear bandits: let θ ⋆ ∈ R d be an unknown parameter. At time t, the learner chooses an action π t ∈ {π ∈ R d : ∥π∥ 2 ≤ 1} and receives a Gaussian reward r t ∼ N(⟨θ ⋆ , π t ⟩ , 1). For T ∈ N, let H T = (π 1 , r 1 , • • • , π T , r T ) be the observed history up to time T . The central claim of this section is the following upper bound on the mutual information.Theorem D.2. For any r > 0, we define the prior µ r over B d (r) byµ r : θ ⋆ ∼ N 0, r 2 4d I d | ∥θ ⋆ ∥ ≤ r.Then for any algorithm ALG, we haveI µr,ALG (θ ⋆ ; H T ) ≤ d log 1 + r 2 T 4d 2 .Proof. Denote λ = r 2 4 . We first prove that if θ ⋆ ∼ µ = N(0, λI d /d), thenEQUATION)By the Bayes rule, the posterior distribution of θ ⋆ conditioned on(H t-1 , π t ) is p(θ ⋆ | H t-1 , π t ) ∝ exp - d∥θ ⋆ ∥ 2 2 2λ - 1 2 s<t (r s -⟨θ ⋆ , π s ⟩) 2 ,which is a Gaussian distribution with covariance (Σ t-1 ) -1 , whereΣ t-1 = d λ I d + s<t π s (π s ) ⊤ .Therefore, by the chain rule of mutual information, we haveI µ,ALG (θ ⋆ ; H T ) = T t=1 I µ,ALG (θ ⋆ ; r t | H t-1 , π t ) = T t=1 E µ,ALG 1 2 log 1 + (π t ) ⊤ (Σ t-1 ) -1 π t = E µ,ALG 1 2 T t=1 log det(Σ t ) det(Σ t-1 ) = E µ,ALG 1 2 log det(Σ T ) (d/λ) d ≤ E µ,ALG d 2 log Tr(Σ T )/d d/λ ≤ d 2 log 1 + λT d 2 ,which is exactly (27) .Next we deduce the claimed result from (27) . Consider the random variable Z = 1 {∥θ ⋆ ∥ 2 ≤ r} ∈ {0, 1}, and thend 2 log 1 + λT d 2 ≥ I µ,ALG (θ ⋆ ; H T ) ≥ I µ,ALG (θ ⋆ ; H T | Z) ≥ P(Z = 1) • I µr,ALG (θ ⋆ ; H T |Z = 1) = P µ (∥θ ⋆ ∥ 2 ≤ r) • I µr,ALG (θ ⋆ ; H T ).Here the first inequality is (27) , the second inequality follows fromI(X; Y ) -I(X; Y | f (X)) = I(f (X); Y ) -I(f (X); Y | X)≥ 0, the third identity follows from the definition of conditional mutual information. Finally, noticing that P µ (∥θ ⋆ ∥ 2 ≤ r) ≥ 1 2 by concentration of χ 2 d random variable, we arrive at the desired statement.Next we show how to translate the mutual information upper bound in Theorem D.2 to lower bounds of estimation and regret.Theorem D.3. Let T ≥ 1, r = min c0d √ T , 1 for a small absolute constant c 0 , and consider the prior µ = µ r . For any T -round algorithm with output π, Proposition 8 implies thatE µ,ALG π - θ ⋆ ∥θ ⋆ ∥ 2 ≥ 1 10.Therefore, we may deduce that supM ⋆ ∈M E M ⋆ ,ALG [Risk DM (T )] ≳ min d √ T , 1 .Proof. We first prove the first inequality by applying Proposition 8 to the following sub-optimality measuregM θ (π) = ∥π -normalize(θ)∥ 2 2 ,where we denote normalize(θ) = θ ∥θ∥ ∈ B d (1). Notice that for θ ∈ Θ, we haveg M θ (π) = ∥θ∥ -⟨θ, π⟩ ≥ ∥θ∥ • π - θ ∥θ∥ 2 = ∥θ∥ • gM θ (π).For ∆ ∈ (0, 1), we first claim thatEQUATION)To see so, by symmetry of Gaussian distribution, we know for fixed any π,µ(θ : gM θ (π) ≤ ∆) = P θ∼Unif(B d (1)) θ : ∥θ -π∥ 2 ≤ ∆ ,and hence we can instead consider the uniform distribution over B d (1) . By rotational invariance, we may assume that π = (x, 0, • • • , 0), with x ≥ 0. Thenθ ∈ B d (1) : ∥θ -π∥ 2 2 ≤ ∆ = θ ∈ B d (1) : θ 1 ≥ x 2 + 1 -∆ 2x ⊆ θ ∈ B d (1) : θ 1 ≥ √ 1 -∆ . By Bubeck et al. [15, Section 2], the density of θ 1 ∈ [-1, 1] is given by f (θ 1 ) = Γ(d/2) Γ((d -1)/2) √ π (1 -θ 2 1 ) (d-3)/2 .Therefore,ρ ∆ ≤ 1 √ 1-∆ f (θ 1 )dθ 1 = O( √ d) • (1 - √ 1 -∆)∆ (d-3)/2 = O √ d∆ (d-1)/2 .With the upper bound (28) of ρ ∆ , we know that for ∆ = 1 2 , it holds log(1/ρ ∆ ) ≥ 2I µ (T ), as long as c 0 is a sufficiently small constant. Therefore, Proposition 8 gives thatE µ,ALG ∥ π -normalize(θ ⋆ )∥ 2 = E µ,ALG [g M θ (π)] ≥ 1 4 .This completes the proof of the first inequality.Finally, using the fact that P θ ⋆ ∼µ (∥θ ⋆ ∥ ≤ c 1 r) ≤ 1 100 for a small absolute constant c 1 , we can conclude that supM ⋆ ∈M E M ⋆ ,ALG [Risk DM (T )] ≥ E µ,ALG [g M θ (π)] ≥ c 1 r 8 = Ω min d √ T , 1 .This is the desired result.In addition to the reward-maximization setting (Example 1), we also introduce a slightly more general setting. In this setting, we assume that for each model M ∈ M, the risk function isg M (π) = f M (π M ) -f M (π), but f M is not assumed to be the expected reward function (Example 1). Instead, we only require f M satisfying the following assumption, where M + is a pre-specified model class of reference models that contains co(M) (following Foster et al. [38] ).Assumption 4. Let M + ⊆ (Π → ∆(O)) be a given class of reference models, such that co(M) ⊆ M + . For any M ∈ M, the risk function takes form g M (π) = f M (π M ) -f M (π) for some functional f M : Π → R, so that f M can be extended to M + , such that for any model M ∈ M and reference model Ď M ∈ M + we haveEQUATIONIn some cases, consider a larger reference model class can be convenient for proving lower bounds, see e.g., Appendix B.1 and Appendix I.5.In this section, we demonstrate how our general lower bound approach recovers the regret lower bounds of Foster et al. [38] , Glasgow and Rakhlin [40] . We first state our lower bound in terms of constrained DEC in the following theorem. For the remainder of this section, we sketch how we prove Theorem E.1 in a slightly more general setting (Assumption 4), following Appendix F.3. Before providing our regret lower bounds, we first present several important definitions.Definition of quantile regret-DEC We note that it is possible to directly modify the definition of quantile PAC-DEC (11) , and then apply Theorem 6 to obtain an analogous regret lower bound immediately. However, as Foster et al. [38] noted, the "correct" notion of regret-DEC (cf. Eq. ( 7)) turns out to be more sophisticated. Therefore, we define the quantile version of regret-DEC similarly, as follows.Throughout the remainder of this section, we fix the integer T . DefineΠ T = π : π = 1 T T t=1 δ πt , where π 1 , • • • , π T ∈ Π ⊆ ∆(Π),i.e., Π T is the class of all T -round mixture decision. We introduce the mixture decision space Π T here to handle the average of T -round profile (π 1 , • • • , π T ) of the algorithm. In particular, when Π is convex, we may regard Π T = Π.Next, we define the quantile regret-DEC asEQUATIONand define r-dec q ε,δ (M) := supĎ M ∈M + r-dec q ε,δ (M, Ď M ).The following proposition relates our quantile regret-DEC to the constrained regret-DEC (proof in Appendix F.5).Proposition E.2. Suppose that Assumption 4 holds for M. Then, for any Ď M ∈ M + , it holds thatr-dec c ε (M ∪ { Ď M }, Ď M ) ≤ 2 • r-dec q ε,δ (M, Ď M ) + c δ L r ε,where we denote c δ = max δ 1-δ , 1 . In particular, it holds thatr-dec q ε,1/2 (M) ≥ 1 2 max Ď M ∈M + r-dec c ε (M ∪ { Ď M }, Ď M ) -L r ε .Lower bound with quantile regret-DEC Now, we prove the following lower bound for the regret of any T -round algorithm, via our general interactive Fano method (Lemma 5). The proof is presented in Appendix F.4.Theorem E.3. Suppose that Assumption 4 holds for M. Then, for any T -round algorithm ALG, parameters ε, δ, C > 0, there exists M ∈ M such thatP M,ALG Reg DM (T ) ≥ T • (r-dec q ε,δ (M) -CL r ε) -1 ≥ δ - 1 C 2 - √ 14T ε 2 .As a corollary, there exists M ⋆ ∈ M such thatReg DM (T ) ≥ T 2 • max Ď M ∈M + r-dec c ε(T ) (M ∪ { Ď M }, Ď M ) -4L r ε(T ) -1 ≥ T 2 • r-dec c ε(T ) (M) -4L r ε(T ) -1with probability at least 0.01 under P M ⋆ ,ALG , where ε(T ) = 1 100 √ T . Theorem E.1 is now an immediate corollary, because for reward-maximization setting, we always have L r = √ 2 in Assumption 4.More generally, we show that for a fairly different task of interactive estimation (Example 3), we also have an equivalence between quantile PAC-DEC with constrained PAC-DEC.Recall that in this setting, each model M ∈ M is assigned with a parameter θ M ∈ Θ, which is the parameter that the agent want to estimate. The decision space Π = Π 0 × Θ, where each decision π ∈ Π consists of π = (π 0 , θ), where π 0 is the explorative decision to interact with the model, and θ is the estimator of the model parameter. The risk function is then defined as g M (π) = Dist(θ M , θ), for certain distance Dist(•, •).In interactive estimation, we can show that the quantile DEC is in fact lower bounded the constrained DEC, as follows (proof in Appendix F.6).Proposition E.4. Consider the setting of Example 3. Then as long as δ < 1 2 , it holds that p-dec c ε (M) ≤ 2 • p-dec q ε,δ (M).In particular, for such a setting (which encompasses the model estimation task considered in Chen et al. [19] ), Theorem 6 provides a lower bound of estimation error in terms of constrained PAC-DEC. This is significant because the constrained PAC-DEC upper bound in Theorem 4 is actually not restricted to Example 1, and we have hence shown thatp-dec c ε(T ) (M) ≲ inf ALG sup M ⋆ ∈M E M ⋆ ,ALG [Risk DM (T )] ≲ p-dec c ε(T ) (M),where ε(T ) ≍ 1/T and ε(T ) ≍ log|M|/T . Therefore, for interactive estimation, constrained PAC-DEC is also a nearly tight complexity measure. In particular, for the (non-interactive) functional estimation problem (see e.g. Polyanskiy and Wu [60] ), the parameter space Θ ⊂ R, and hence by considering covering number, we have log |Θ| = O (1). Therefore, for convex M, under mild assumption that the DEC is of moderate decaying (Assumption 3), the minimax risk is then characterized by (up to logarithmic factors)inf ALG sup M ⋆ ∈M E M ⋆ ,ALG [Risk DM (T )] ≍ p-dec c √ 1/T (M).This result can be regarded as a generalization of Polyanskiy and Wu [60] to the interactive estimation setting.Additional notations For notational simplicity, for any distribution q ∈ ∆(Π) and reference model Ď M , we denote the localized model class around Ď M asM q,ε ( Ď M ) := M ∈ M : E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 .We show thatEQUATIONi.e. ∆ ⋆ ALG,δ is the maximum risk of ALG over the model class M, measured in terms of the δ-quantile. Note that by the definition of ∆ ⋆ ALG,δ , we have∆ ⋆ ALG,δ ≥ sup Ď M =M ∈M sup ∆>0 {∆ : p M,ALG (π : g M (π) ≥ ∆) > δ} = sup ∆>0 ∆ : sup M ∈M P M,ALG (g M (π) ≥ ∆) > δ .On the other hand, using the chain rule of Hellinger distance (Lemma C.1), we haveD TV P M,ALG , P Ď M ,ALG ≥ 14T E π∼q Ď M ,ALG D 2 H M (π), Ď M (π) .Therefore, we know∆ ⋆ ALG,δ := sup Ď M ∈co(M) sup M ∈M sup ∆≥0 ∆ : p Ď M ,ALG (π : g M (π) ≥ ∆) > δ + 14T E π∼q Ď M ,ALG D 2 H M (π), Ď M (π) ≤ sup Ď M ∈co(M) sup M ∈M sup ∆≥0 ∆ : p Ď M ,ALG (π : g M (π) ≥ ∆) > δ + D TV P M,ALG , P Ď M ,ALG.Notice that for any Ď M ∈ co(M), M ∈ M, we can take L(M, X) = g M (π) (recall that X = (H T , π) is the whole trajectory), and µ M ∈ ∆(M) supported on M and Q = P Ď M ,ALG in Theorem 1, and hence∆ ⋆ ALG,δ ≤ sup Ď M ∈co(M) sup M ∈M sup ∆≥0 ∆ : D TV 1 -δ, ρ ∆,P Ď M ,ALG > D TV P M,ALG , P Ď M ,ALG ≤ sup M ∈M sup ∆>0 {∆ : P M,ALG ( π : g M ( π) ≥ ∆) > δ} ,where the last line follows from the claim in Appendix D.1. The proof of ( 31) is hence completed.Fix any algorithm ALG and abbreviate ε = ε(T ). Take an arbitrary parameter ∆ 0 < p-dec q ε,δ (M). Then there exists Ď M such that ∆ 0 < p-dec q ε,δ (M, Ď M ). Hence, by the definition (11) , we know that∆ 0 < sup M ∈M g M δ (p Ď M ,ALG ) E π∼q Ď M ,ALG D 2 H M (π), Ď M (π) ≤ ε 2 .Therefore, there exists M ∈ M such thatE π∼q Ď M ,ALG D 2 H M (π), Ď M (π) ≤ ε 2 , P π∼p Ď M ,ALG (g M (π) ≥ ∆ 0 ) ≥ δ. This immediately implies p Ď M ,ALG (π : g M (π) ≥ ∆) > δ 1 + 14T E π∼q Ď M ,ALG D 2 H M (π), Ď M (π) ,where δ 1 = δ -14T ε 2 . Notice that δ 1 > δ 2 , and hence applying Lemma 5 shows that there exists M ∈ M such that P M,ALG g M ( π) ≥ ∆ 0 ≥ δ 2 . Letting ∆ 0 → p-dec q ε,δ (M) completes the proof.In this section, we prove Proposition 7 under the slightly more general setting of Assumption 4.Ď M ∈ M + and ε > 0, δ ∈ [0, 1), it holds that p-dec c ε/ √ 2 (M, Ď M ) ≤ p-dec q ε,δ (M, Ď M ) + 2εL r 1 -δ .For Example 1, we always have L r ≤ √ 2, and hence Proposition 7 follows immediately from Proposition F.1.Proof of Proposition F.1. Fix a reference model Ď M and a ∆ 0 > p-dec q ε,δ (M, Ď M ). Then, we pick a pair (p, q) such that∆ 0 > sup M ∈M g M δ (p) | E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 ,whose existence is guaranteed by the definition of p-dec q ε,δ (M, Ď M ) in (11) . In other words, we haveP π∼ p(g M (π) ≤ ∆ 0 ) ≥ 1 -δ, ∀M ∈ M q,ε ( Ď M ) Consider q = p+q 2 and ε ′ = ε √ 2 . Also let M := arg max M ∈M q,ε ′ ( Ď M ) f M (π M ). Now, consider p ∈ ∆(Π) given by p(•) = p •|g M (π) ≤ ∆ 0 .By definition, for π ∼ p we have f M (π) ≥ f M (π M ) -∆ 0 , and henceE π∼p [g M (π)] = f M (π M ) -E π∼p [f M (π)] ≤ f M (π M ) -E π∼p f M (π) + L r • E π∼p D H M (π), M (π) ≤ f M (π M ) -f M (π M ) + ∆ 0 + L r • E π∼p D H M (π), M (π) .Notice that for anyM ∈ M q,ε ′ ( Ď M ), we have f M (π M ) ≤ f M (π M )and alsoE π∼p D H M (π), M (π) ≤ 1 p(g M (π) ≤ ∆ 0 ) E π∼ pD H M (π), M (π) ≤ 1 1 -δ E π∼ pD H M (π), Ď M (π) + E π∼ pD H M (π), Ď M (π) ≤ 2ε 1 -δ .Combining these inequalities givesp-dec c ε ′ (M, Ď M ) ≤ sup M ∈M E π∼p [g M (π)] | E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 2 ≤ ∆ 0 + 2εL r 1 -δ .Letting ∆ 0 → p-dec q ε,δ (M, Ď M ) completes the proof.Our proof adopts the analysis strategy originally proposed by Glasgow and Rakhlin [40] .Fix a 0 < ∆ < r-dec q ε,δ (M) and a parameter c ∈ (0, 1). Then there exists Ď M ∈ M + such that r-dec q ε,δ (M, Ď M ) > ∆.Fix a T -round algorithm ALG with rules p 1 , • • • , p T , we consider a modified algorithm ALG ′ : for t = 1, • • • , T , and historyH (t-1) , we set p ′ t (•|H (t-1) ) = p t (•|H (t-1) ) if t-1 s=1 g Ď M (π s ) < T ∆ -1, and set p ′ t (•|H (t-1) ) = 1 π Ď M if otherwise.By our construction, it holds that under ALG ′ , we have T t=1 g Ď M (π t ) < T ∆ almost surely. Furthermore, we can define the stopping timeτ = inf t : t s=1 g Ď M (π s ) ≥ T ∆ -1 or t = T + 1 . If τ ≤ T , then it holds that τ t=1 g Ď M (π t ) ≥ T ∆ -1.= P Ď M ,ALG ′ ( 1 T T t=1 π t = •) ∈ ∆(Π T ).Using our definition of r-dec q , we know that E π∼p g Ď M (π) < ∆ by our construction, and hence there exists M ∈ M such thatP π∼p (g M ( π) ≥ ∆) > δ, E π∼p D 2 H M ( π), Ď M ( π) ≤ ε 2 .By definition of p and Lemma C.1, we haveEQUATION)We also knowE Ď M ,ALG ′ 1 T T t=1 |f M (π t ) -f Ď M (π t )| 2 ≤ E Ď M ,ALG ′ 1 T T t=1 L 2 r D 2 H M (π t ), Ď M (π t ) = L 2 r E π∼p D 2 H M ( π), Ď M ( π) ≤ L 2 r ε 2, and hence by Markov inequality,P Ď M ,ALG ′ 1 T T t=1 |f M (π t ) -f Ď M (π t )| ≥ CL r ε ≤ 1 C 2 .In the following, we consider eventsE 1 := T t=1 g M (π t ) ≥ T ∆ ,and the random variableX := T t=1 |f M (π t ) -f Ď M (π t )|. By definition, P Ď M ,ALG ′ (E 1 ) > δ, P Ď M ,ALG ′ (X ≥ CT L r ε) ≤ 1 C 2 .We have the following claim. Claim: Under the event E 1 ∩ {τ ≤ T }, we haveτ t=1 g M (π t ) ≥ T ∆ -X -1.To prove the claim, we boundτ t=1 g M (π t ) = T t=1 g M (π t ) - T t=τ +1 g M (π t ) ≥ T ∆ - T t=τ +1 [f M (π M ) -f M (π t )] ≥ T ∆ -(T -τ )f M (π M ) + T t=τ +1 f Ď M (π t ) -X = T ∆ -(T -τ ) • f M (π M ) -f Ď M (π Ď M ) -X,where the first inequality follows from E 1 , and the second inequality follows fromT t=τ +1 |f M (π t ) -f Ď M (π t )| ≤ X.On the other hand, we can also boundτ t=1 g M (π t ) = τ t=1 [f M (π M ) -f M (π t )] ≥ τ f M (π M ) - τ t=1 f Ď M (π t ) -X = τ • f M (π M ) -f Ď M (π Ď M ) + τ t=1 g Ď M (π t ) -X ≥ τ • f M (π M ) -f Ď M (π Ď M ) + T ∆ -1 -X, where the first inequality follows from τ t=1 |f M (π t ) -f Ď M (π t )| ≤ X,and the second inequality is because τ t=1 g Ď M (π t ) ≥ T ∆ -1 given τ ≤ T , which follows from the definition of the stopping time τ . Therefore, taking maximum over the above two inequalities proves our claim. Now, using the claim, we knowP Ď M ,ALG ′ τ ∧T t=1 g M (π t ) ≥ T (∆ -Cε) -1 ≥ P Ď M ,ALG ′ (E 1 ∩ {X ≤ CT ε}) ≥ δ - 1 C 2 .Notice that D 2 H P M,ALG ′ , P Ď M ,ALG ′ ≤ 7T ε 2 , and hence for any event E, it holds P M,ALG ′ (E) ≥P Ď M ,ALG ′ (E) - √ 14T ε 2 .In particular, we haveP M,ALG ′ τ ∧T t=1 g M (π t ) ≥ T (∆ -CL r ε) -1 ≥ δ - 1 C 2 - √ 14T ε 2 .Finally, we note that ALG and ALG ′ agree on the first τ ∧ T rounds (formally, ALG and ALG ′ induce the same distribution of (π 1 , • • • , π τ ∧T )), and henceP M,ALG τ ∧T t=1 g M (π t ) ≥ T (∆ -CL r ε) -1 ≥ δ - 1 C 2 - √ 14T ε 2 .The proof is hence complete by noticing thatτ ∧T t=1 g M (π t ) ≤ T t=1 g M (π t ) = Reg DM (T ) and taking ∆ → r-dec q ε,δ (M). F.5 Proof of Proposition E.2 Fix a Ď M ∈ M + , and ∆ > r-dec q ε,δ (M, Ď M ). Choose p ∈ ∆(Π T ) such that g M δ (p) ∨ E π∼p [g Ď M (π)] ≤ ∆, ∀M ∈ M p,ε ( Ď M ).The existence of p is guaranteed by the definition (30) . In other words, we have E π∼p [g Ď M (π)] ≤ ∆ andP π∼p (g M (π) ≥ ∆) ≤ δ, ∀M ∈ M p,ε ( Ď M ).We then has the following claim.Claim. Suppose that M ∈ M p,ε ( Ď M ). Then it holds thatEQUATION)Fix any M ∈ M p,ε ( Ď M ), we prove (33) as follows. Consider the event E = {π : g M (π) ≤ ∆}. Then,p(E) f M (π M ) -f Ď M (π Ď M ) = E π∼p 1 {E} g M (π) -g Ď M (π) + f Ď M (π) -f M (π) ≤ p(E)∆ + L r E π∼p 1 {E} D H M (π), Ď M (π) ,where the inequality uses g M (π) ≤ ∆ for π ∈ E and Assumption 4. Therefore,E π∼p g M (π) = E π∼p 1 {E} g M (π) + E π∼p 1 {E c } g M (π) ≤ p(E)∆ + E π∼p 1 {E c } f M (π M ) -f Ď M (π Ď M ) + f Ď M (π) -f M (π) + g Ď M (π) ≤ 2∆ + p(E c )L r p(E) E π∼p 1 {E} D H M (π), Ď M (π) + L r E π∼p 1 {E c } D H M (π), Ď M (π) ≤ 2∆ + max p(E c ) p(E) , 1 L r E π∼p D H M (π), Ď M (π) .This completes the proof of our claim.Therefore, using (33) withE π∼p [g Ď M (π)] ≤ ∆ yields E π∼p [g M (π)] ≤ 2∆ + c δ L r ε, ∀M ∈ M p,ε ( Ď M ).This immediately impliesr-dec c ε (M ∪ { Ď M }, Ď M ) ≤ 2∆ + c δ L r ε.Finally, taking ∆ → r-dec q ε,δ (M, Ď M ) completes the proof.Fix a reference model Ď M and let ∆ 0 > p-dec q ε,δ (M, Ď M ). Then there exists p, q ∈ ∆(Π) such that supM ∈M g M δ (p) | E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 < ∆ 0 .Therefore, it holds thatP π∼p (g M (π) ≤ ∆ 0 ) ≥ 1 -δ, ∀M ∈ M q,ε ( Ď M ).If the constrained set M q,ε ( Ď M ) is empty, then we immediately have p-dec c ε (M, Ď M ) = 0, and the proof is completed. Therefore, in the following we may assume M q,ε ( Ď M ) is non-empty, andM ∈ M q,ε ( Ď M ).Claim. Let θ = θ M and π = (π 0 , θ) for an arbitrary π 0 , it holds thatg M ( π) ≤ ∆ 0 , ∀M ∈ M q,ε ( Ď M ).This is because for any M ∈ M q,ε ( Ď M ), it holds thatP π∼p (g M (π) ≤ ∆ 0 , g M (π) ≤ ∆ 0 ) ≥ 1 -2δ > 0.Hence, there exists θ ∈ Θ such that Dist(θ M , θ) ≤ ∆ 0 and Dist(θ M , θ) ≤ ∆ 0 holds. Therefore, it must hold that Dist(θ M , θ) ≤ 2∆ 0 for any M ∈ M q,ε ( Ď M ).The above claim immediately implies thatp-dec c ε (M, Ď M ) ≤ sup M ∈M g M ( π) | E π∼q D 2 H M (π), Ď M (π) ≤ ε 2 ≤ 2∆ 0 . Letting ∆ 0 → p-dec q ε,δ (M, Ď M ) yields p-dec c ε (M, Ď M ) ≤ 2p-dec q ε,δ (M, Ď M ), which is the desired result.In this section, we present a slightly modified version of the Exploration-by-Optimization Algorithm (ExO + ) developed by Foster et al. [37] , built upon Lattimore and Szepesvári [52] , Lattimore and Gyorgy [49] . The original ExO + algorithm has an adversarial regret guarantee for any model class M, scaling with r-dec o γ (co(M)), the offset DEC of the mode class co(M), and log |Π|, the logcardinality of the decision space. For our purpose, we adapt the original ExO + algorithm by using a prior q ∈ ∆(Π) not necessarily the uniform prior, and with a suitably chosen prior q, ExO + then achieves a regret guarantee scaling with log Ddim ∆ (M), instead of log |Π| (cf. Foster et al. [37] ), which is always an upper bound of log Ddim ∆ (M).Offset DEC for regret. We first recall the following (original) definition of DEC [36] :EQUATIONand r-dec o γ (M) := supĎ M ∈co(M) r-dec o γ (M, Ď M ).Through the Estimation-to-Decision (E2D) algorithm [36] , offset regret-DEC provides an upper bound of Reg DM for any learning problem, and it is also closely related to the complexity of adversarial decision making.As discussed in Foster et al. [38] , in the reward maximization setting (Example 1), the constrained regret-DEC r-dec c can always be upper bounded in terms of the offset DEC r-dec o . Conversely, in the same setting, we also show that the offset DEC can also be upper bounded in terms of the constrained DEC (Theorem I.4), and hence the two concepts can be regarded as equivalent under mild assumptions (e.g. moderate decaying, Assumption 3).Input: Problem (M, Π), prior q ∈ ∆(Π), parameter T ≥ 1, γ > 0.1: Set q 1 = q.2:for t = 1, • • • , T do 3:Solve the exploration-by-optimization objectiveEQUATIONSample π t ∼ p t , execute π t and observe o t 5:Updateq t+1 (π) ∝ π q t (π) exp(ℓ t (π; π t , o t ))Exploration-by-Optimization algorithm. The algorithm, ExO + , is restated in Algorithm 1. At each round t, the algorithm maintains a reference distribution q t ∈ ∆(Π), and use it to obtain a decision distribution p t ∈ ∆(Π) and an estimation functionℓ t ∈ L := (Π × Π × O → R), by solving a joint minimax optimization problem based on the exploration-by-optimization objective: DefiningEQUATIONandEQUATIONthe algorithm solve (p t , ℓ t ) ← arg min p∈∆(Π),ℓ∈L Γ q t ,γ (p, ℓ). The algorithm then samples π t ∼ p t , executes π t and observes o t from the environment. Finally, the algorithm updates the reference distribution by performing the exponential weight update with weight function ℓ t (•; π t , o t ).Guarantee of ExO + . Following Foster et al. [37] , we defineEQUATIONand exo 1/γ (M) = sup q∈∆(Π) exo 1/γ (M, q). The following theorem is deduced from Foster et al.[37, Theorem 3.1 and 3.2].Theorem G.1. Under the reward maximization setting3 (Assumption 4), it holds thatr-dec o γ/4 (co(M))) ≤ exo 1/γ (M) ≤ r-dec o γ/8 (co(M))), ∀γ > 0.Now, we present the main guarantee of Algorithm 1, which has the desired dependence on the prior q ∈ ∆(Π).Theorem G.2. It holds that with probability at least 1 -δ,Reg DM ≤ T ∆ + r-dec o γ/8 (co(M)) + γ log 1 δ • q(π : f M ⋆ (π M ⋆ ) -f M ⋆ (π) ≤ ∆) Proof. Consider the set Π ⋆ := {π : f M ⋆ (π M ⋆ ) -f M ⋆ (π) ≤ ∆} and the distribution q ⋆ = q(•|Π ⋆ ).Following Proposition G.3, we considerX t (π t , o t ) := E π∼q ⋆ ℓ t (π; π t , o t ) -log E π∼q t exp ℓ t (π; π t , o t ) , and Proposition G.3 implies that T t=1 X t (π t , o t ) ≤ log(1/q(Π ⋆ )).1 -δ, T t=1 -log E t-1 exp -X t (π t , o t ) ≤ T t=1 X t (π t , o t ) + log(1/δ).Notice thatE t-1 exp -X t (π t , o t ) = E π∼p t E o∼M ⋆ (π) E π ′ ∼q t exp ℓ t (π ′ ; π, o) -E π ⋆ ∼q ⋆ ℓ t (π ⋆ ; π, o) .Using the fact that 1 -x ≤ -log x and Jensen's inequality, we haveT t=1 E π ⋆ ∼q ⋆ Err(p t , ℓ t ; q t , M ⋆ , π ⋆ ) ≤ log(1/q(Π ⋆ )) + log(1/δ),where we denoteErr(p, ℓ; q, M ⋆ , π ⋆ ) := E π∼p E o∼M ⋆ (π) E π ′ ∼q [1 -exp (ℓ(π ′ ; π, o) -ℓ(π ⋆ ; π, o))].Therefore, it holds thatReg DM = T t=1 E π∼p t f M ⋆ (π M ⋆ ) -f M ⋆ (π) ≤ T t=1 ∆ + E π ⋆ ∼q ⋆ E π t ∼p t f M ⋆ (π ⋆ ) -f M ⋆ (π t ) = T ∆ + γ T t=1 E π ⋆ ∼q ⋆ Err(p t , ℓ t ; q t , M ⋆ , π ⋆ ) + T t=1 E π ⋆ ∼q ⋆ E π t ∼p t f M ⋆ (π ⋆ ) -f M ⋆ (π t ) -γErr(p t , ℓ t ; q t , M ⋆ , π ⋆ ) =Γ q t ,γ (p t ,ℓ t ;M ⋆ ,π ⋆ ) ≤ T ∆ + γ(log(1/q(Π ⋆ )) + log(1/δ)) + T t=1 Γ q t ,γ (p t , ℓ t ) ≤ T ∆ + exo 1/γ (M) + γ(log(1/q(Π ⋆ )) + log(1/δ)).Applying Theorem G.1 completes the proof.Proposition G.3. For any q ′ ∈ ∆(Π), it holds thatT t=1 E π∼q ′ [ℓ t (π; π t , o t )] -log E π∼q t exp ℓ t (π; π t , o t ) ≤ D KL (q ′ ∥ q).Proof. This is essentially the standard guarantee of exponential weight updates. For simplicity, we assume Π is discrete. Then, by definition,q t (π) = q(π) exp t s=1 ℓ s (π; π s , o s ) π ′ ∈Π q(π ′ ) exp t-1 s=1 ℓ s (π ′ ; π s , o s ) , and hence log E π∼q t exp ℓ t (π; π t , o t ) = log E π∼q exp t s=1 ℓ s (π; π s , o s ) -log E π∼q exp t-1 s=1 ℓ s (π; π s , o s ) .Therefore, taking summation over t = 1, • • • , T , we have- T t=1 log E π∼q t exp ℓ t (π; π t , o t ) = -log E π∼q exp T t=1 ℓ t (π; π t , o t ) .The proof is then completed by the following basic fact of KL divergence: for any function h : Π → R,E π∼q ′ [h(π)] ≤ log E π∼q exp(h(π)) + D KL (q ′ ∥ q).H Additional discussion and results from Section 4 H.1 Additional discussion from Section 4.2 Connection to the maximin volume. Hanneke and Yang [41] propose maximin volume, a complexity measure that tightly characterizes the complexity of learning noiseless binary-valued structured bandit problems. For such problem classes, the decision dimension is exactly the inverse of the maximin volume. While the decision dimension can be viewed as a generalization of the maximin volume in this sense, we emphasize that the decision dimension directly arises from our general lower bound framework, and is applicable to general decision making problems in the DMSO framework.Noise distribution. We note that the upper bound in (19) applies to any reward distribution with sub-Gaussian noise (cf. Appendix I.2). Meanwhile, since the lower bound in Corollary 12 is specialized to Gaussian noise, it acts as a lower bound for the broader class of sub-Gaussian noise distributions as well. We expect the lower bound to extend to other "reasonable" noise distributions.We now instantiate our general results to give tighter guarantees for structured bandits, improving the upper bounds in Section 4.2.DEC for structured bandits. We consider the same structured bandit protocol as in Section 4.2; recall that H denotes the reward function class and M H denotes the induced model class. In what follows, we simplify the results in Theorem 15 to be stated purely in terms of H. For a reference value function s h :C × A → [0, 1], we define r-dec c ε (H, s h) := inf p∈∆(Π) sup h∈H E π∼p h(π h ) -h(π) E π∼p (h(π) -s h(π)) 2 ≤ ε 2 ,where we recall that π h := max π∈Π h(π). We then define the DEC for H asr-dec c ε (H) = sup s h∈co(H) r-dec c ε (H ∪ { s h}, s h).As a corollary of Theorem G.2, the r-dec c ε (H) and log Ddim ∆ (H) together provide an upper bound for structured bandits with H.Theorem H.1. Let H be given. Suppose that Π is finite, and that ε → r-dec c ε (co(H)) satisfies moderate decay as a function of ε (Assumption 3) with constant c reg . Let ε(T ) ≍ log Ddim ∆ (H)/T . The Algorithm 1 ensures that high probability,Reg DM ≤ T • ∆ + O(c reg T √ log T ) • r-dec c ε(T ) (co(H)). As a corollary, the minimax sample complexity of structured bandit learning with H is bounded as max T DEC (H, ∆), log Ddim 2∆ (H) ≲ T ⋆ (M H , ∆) ≲ T DEC (co(H), ∆) • log Ddim ∆/2 (H), (38) where we denote T DEC (H, ∆) = inf ε∈(0,1) {ε -2 : r-dec c ε (H) ≤ ∆} (following ( 14)) and omit logarithmic factors and dependence on the constant c reg .There are many standard structured bandit problems where the value function class H is convex, including multi-armed bandits, linear bandits, and non-parametric bandits (with smoothness [65] , or concavity [48] , or sub-modularity [58] , or etc.). For these problem classes, the complexity of noregret learning is completely characterized by the DEC of H and the decision dimension Ddim ∆ (H) (up to a quadratic factor).We also note that the lower bound of ( 38) is proven for Gaussian noise, while our upper bound applies to a much more general class of reward distributions (with bounded variance).Next, we instantiate our general results for stochastic contextual bandits with general function approximation, generalizing the structured bandit problem. We consider the stochastic contextual bandit problem with context space C, action space A, and a reward function class H ⊆ (C ×A → [0, 1]). This problem is a special case of the DMSO setting with decision space Π = (C → A), and the environment is specified by a tuple (h ⋆ ∈ H, ν ⋆ ∈ ∆(C)). The protocol is as follows: For each round t, the environment draws c t ∼ ν, and the learner takes action a t = π t (c t ) based on the decision π t : C → A, and receives a reward r t ∼ N(h ⋆ (c t , a t ), 1).We can formulate the model class as follows. For a reward function h ∈ H and context distribution ν ∈ ∆(C), the corresponding model M h,ν is specified as which corresponds to the maximum of the per-context DEC over all contexts. We also define T DEC (H, ∆) = inf ε∈(0,1) {ε -2 : r-dec c ε (H) ≤ ∆}, following (14) . Decision dimension for contextual bandits. Specializing the decision dimension to contextual bandits, we define(c, a, r) ∼ M h,ν (π) : c ∼ ν, a = π(a), r ∼ N(h(c, a), 1). Let M H = {M h,ν : h ∈ H, ν ∈ ∆(C)}EQUATIONwhere π h ∈ Π is defined via π h (c) := arg max a∈A h(c, a) for c ∈ C.Intuitively, the value of the decision dimension log Ddim ∆ (H) for contextual bandits captures the difficulty of estimating optimal actions, but also the difficulty of generalizing across contexts. For example, when we consider the unstructured contextual bandit problems (i. As a corollary of Theorem 15, we derive the following upper and lower bounds on the complexity of contextual bandit learning with H.Theorem H.2. Let H be given. Suppose that both the context space C and the action space A are finite, and that ε → r-dec c ε (co(H)) satisfies moderate decay as a function of ε (Assumption 3) with constant c reg . Let ε(T ) ≍ log Ddim ∆ (H)/T . Then Algorithm 1 ensures that with high probability, ;Reg DM ≤ T • ∆ + O(c reg T √ log T ) • r-dec c ε(T ) (co(H)). As a corollary, the complexity of learning M H is bounded byEQUATIONomitting dependence on c reg and logarithmic factors.By definition, we have r-dec c ε (co(H)) = r-dec c ε (H) if the per-context value function class H| c is convex for every context c ∈ C. Natural settings in which the per-context value function class H| c is convex include contextual linear bandits [24] , contextual non-parametric bandits [18] , and contextual concave bandits [48] . For these problem classes, the complexity of no-regret learning is completely characterized by the DEC of H and the newly proposed Ddim ∆ (H) (up to a quadratic factor and a factor of log |C|).As a concrete example. we can derive upper bounds based on the decision dimension for finite-action contextual bandits as follows.Corollary H. 3 In this section, we mainly focus on no-regret learning, and we present the regret upper and lower bounds in terms of DEC and log Ddim ∆ (M). The results can be generalized immediately to PAC learning.Fix an arbitrary reference model Ď M ∈ (Π → ∆(O)) such that Assumption 2 holds. We remark that Ď M is not necessarily in M or co(M).We only need to prove the following fact. Notice that by the chain rule of KL divergence, we haveD KL (P M,ALG ∥ P Ď M ,ALG ) = E M,ALG T t=1 D KL (M (π t ) ∥ Ď M (π t )) ≤ T C KL .Hence, using data-processing inequality,D KL (p M,ALG ∥ p Ď M ,ALG ) < log 1/p Ď M ,ALG (π : g M (π) ≤ ∆) -2 2 ≤ D KL (1/2 ∥ p Ď M ,ALG (π : g M (π) ≤ ∆)).This immediately implies p M,ALG (π : g M (π) ≤ ∆) < 1 2 (by Theorem 1, or more directly, by Lemma D.1).Remark I.1. For simplicity, we present the above proof that does not go through our algorithmic Fano's inequality (Proposition 8). However, it is not difficult to see how Theorem 10 can be derived from Proposition 8, as we haveinf µ∈∆(M) sup π∈Π µ(M : g M (π) ≤ ∆) = sup p∈∆(Π) inf M ∈M p(π : g M (π) ≤ ∆),as long as the Minimax theorem can be applied (e.g. when Π is finite or M is finite). Fix a M ∈ M. Let j ∈ {0, • • • , K} be the maximum index such that M ∈ M j . Such a j must exists because M = M 0 . Now,E π∼p [g M (π)] = f M (π M ) -f Ď M (π Ď M ) + E π∼p [g Ď M (π)] + E π∼p [f Ď M (π) -f M (π)] ≤ ∆ j + L r ε j + ∆ + L r E π∼p D H M (π), Ď M (π) .Case 1: j = K. Then, using AM-GM inequality, we haveE π∼p [g M (π)] -γE π∼p D 2 H M (π), Ď M (π) ≤ ∆ K + ε K + ∆ + L 2 r 4γ .Case 2: j < K. Then for each i > j, it holds that E π∼pj D 2 H M (π), Ď M (π) > ε 2 j , and henceE π∼p D 2 H M (π), Ď M (π) ≥ K i=j+1 λ j E π∼pj D 2 H M (π), Ď M (π) ≥ K i=j+1 λ j ε 2 j ≥ cε • ε j 2 .Therefore, using AM-GM inequality,E π∼p [g M (π)] -γE π∼p D 2 H M (π), Ď M (π) ≤ ∆ j + L r ε j + ∆ + 9L 2 r 4γ - 8 9 γE π∼p D 2 H M (π), Ď M (π) ≤ ∆ j + L r ε j + ∆ + 9L 2 r 4γ - 8cγε 9 ε j .By our choice of γ, we have γε ≥ 9 8c ∆j εj + L r , and hence in both cases, we haveE π∼p [g M (π)] -γE π∼p D 2 H M (π), Ď M (π) ≤ ∆ + (D + L r )ε + 9L 2 r 4γ .Note that by definition, we have ∆ ≤ (cK + 1)Dε and γ(ε)• ε = 9 8c (D + L r ), and hence r-dec o γ(ε) (M, Ď M ) ≤ (2D + L r + cKD + 2cL r )ε. Thus, r-dec o γ(ε) (M, Ď M ) + γ(ε)ε 2 ≤ 2D + L r + cK(D + L r ) + 9(D + L r ) 8c ε K .Balancing c and re-arranging yields the desired result.Note that the minimax-optimal sample complexity T ⋆ (M, ∆) is just a way to better illustrate our minimax regret upper and lower bounds. By the definition of T ⋆ (M, ∆), we have1 T Reg ⋆ T = sup{∆ : T ⋆ (M, ∆) ≤ T }.Under Assumption 3, the regret upper bound in Theorem 14 implies (up to c reg , C KL and logarithmic factors)1 T Reg ⋆ T ≲ r-dec c ε(T ) (M).And the regret lower bound Theorem E.1 implies (up to c reg and logarithmic factors)r-dec c ε(T ) (M) ≲ 1 T Reg ⋆ T .By the definition of T ⋆ (M, ∆) and T DEC (M, ∆), we then haveT DEC (M, ∆) ≲ T ⋆ (M, ∆) ≲ T DEC (co(M), ∆) • log Ddim ∆/2 (M).Together with Theorem 10, we prove thatmax T DEC (M, ∆), log Ddim ∆ (M) C KL ≲ T ⋆ (M, ∆) ≲ T DEC (co(M), ∆) • log Ddim ∆/2 (M).For the upper bound, we work with more general noise structure (beyond Gaussian noises). We define M H,V to be the class of all bandits models with mean reward function in H and variance bounded by 1. Specifically, for any M ∈ M H,V , it is associated with a value function h M ∈ H, such that for any decision π ∈ Π, the distribution M (π) of the random reward r has mean h M (π) and variance at most 1.We also recall that the subclass M H ⊆ M H,V is the bandit problem class with the standard Gaussian noise.Proof of Theorem H.1: lower bound of (38) . The lower bound with log Ddim ∆ (H) is exactly Corollary 12.To prove the lower bound with T DEC (H, ∆), we need to lower bound the DEC of M H in terms of the DEC of H, as follows.Lemma I.5. Consider M + = M co(H),V as the class of all reference models (Appendix E). Then,EQUATIONNotice that for M + , Assumption 4 holds with L r = √ 10 (by Lemma C.5). Therefore, as a corollary of Theorem E.3: for any T -round algorithm ALG, there exists M ⋆ ∈ M H such thatEQUATIONwith probability at least 0.01 under P M ⋆ ,ALG , where ε(T ) = 1 50 √T . Therefore, the lower bound in terms of T DEC (H, ∆) follows immediately (using regularity condition Assumption 3).Combining both lower bounds completes the proof.Proof of Theorem H.1: upper bound. We apply Theorem I.3 similar to the proof of Theorem 15 (in Appendix I.2). Using Theorem I.3, we know that ExO + can be suitably instantiated on the model class M H,V so that with probability at least 1 -δ,1 T Reg DM ≤ ∆ + C log(T ) • r-dec c ε(T ) (co(M H,V )),where C is an absolute constant, ε(T ) = log Ddim∆(H)+log(1/δ) T . We only need to upper bound the r-dec c ε (co(M H,V )) (defined in (42) ) in terms of the DEC of co(H). Lemma I.6. For any ε ≥ 0, it holds thatr-dec c ε (M H,V ) ≤ r-dec c √ 10ε (H)We also note that co(M H,V ) ⊆ M co(H),V because the model class M co(H),V is convex and it contains M H,V . Therefore, we knowr-dec c ε (co(M H,V )) ≤ r-dec c ε (M co(H),V ) ≤ r-dec c √ 10ε (co(H)). Using the regularity of ε → r-dec c ε (co(H)), we know r-dec c ε(T ) (co(M H,V )) ≤ c reg • r-dec c √ 10ε (co(H)). This gives the desired upper bound.Fix a ε ∈ [0, 1], we denote ε 1 = 2 √ 2ε and take any ∆ < r-dec c ε1 (H). We pick s h ∈ co(H) such that r-dec c ε1 (H, s h) > ∆. Then, it holds thatinf p∈∆(Π) sup h∈H∪{ s h} E π∼p [h(π h ) -h(a)] | E π∼p (h(a) -s h(a)) 2 ≤ ε 2 1 ≥ ∆.Suppose that s h ∈ co(H) is given by s h = E h∼µ [h] with µ ∈ ∆(H). Then, consider the reference model Ď M ∈ M + with mean reward function s h and Gaussian noise, i.e. Ď M (π) = N s h(π), 1 . Then, we know that forM = M H , r-dec c ε (M ∪ { Ď M }, Ď M ) = inf p∈∆(Π) sup M ∈M∪{ Ď M } E π∼p [g M (π)] | E π∼p D 2 H M (π), Ď M (π) ≤ ε 2 = inf p∈∆(Π) sup h∈H∪{ s h} E π∼p [h(π h ) -h(π)] | E π∼p D 2 H N(h(π), 1), N s h(π), 1 ≤ ε 2 ≥ inf p∈∆(Π) sup h∈H∪{ s h} E π∼p [h(π h ) -h(π)] | E π∼p (h(π) -s h(π)) 2 ≤ 8ε 2 ≥ ∆,where the last line follows from Lemma C.5. Taking ∆ → r-dec c ε1 (H) completes the proof of (43). D 2 H M (π), Ď M (π) ≥ 1 10 |h M (π) -h Ď M (π)| 2 .Therefore, forM = M H,V , r-dec c ε (M ∪ { Ď M }, Ď M ) = inf p∈∆(Π) sup M ∈M∪{ Ď M } E π∼p [g M (π)] | E π∼p D 2 H M (π), Ď M (π) ≤ ε 2 ≥ inf p∈∆(Π) sup M ∈M∪{ Ď M } E π∼p [g M (π)] | E π∼p |h M (π) -h Ď M (π)| 2 ≤ 10ε 2 = inf p∈∆(Π) sup h∈H∪{ s h} E π∼p [h(π h ) -h(π)] | E π∼p (h(π) -s h(π)) 2 ≤ 8ε 2 = r-dec c √ 10ε (H ∪ { s h}, s h),where the second equality follows from the fact that when = h, we have g M (π) = h(π h ) -h(π). Taking supremum over Ď M completes the proof. On the other hand, the lower bound with T DEC (H, ∆) follows from the reduction to the per-context bandits problem. Specifically, for a fixed context c ∈ C, H| c corresponds to a structure bandits class M H|c . Notice that we can naturally regard M H|c ⊂ M H by viewing M H|c as a contextual bandits class with the fixed context c. Therefore, by Theorem H.1 (specifically (44)):1 T Reg ⋆ T ≥ 1 T Reg ⋆ T ≳ r-dec c ε(T ) (H| c ) -6ε(T ), ε(T ) = 1 50 √ T .Taking maximum over c ∈ C yields 1 T Reg ⋆ T ≳ r-dec c ε(T ) (H) -6ε(T ). This gives the desired lower bound with T DEC (H, ∆).Proof of Theorem H.2: upper bound. We follow the proof strategy of Appendix I.5. By Theorem I.3, ExO + can be suitably instantiated on the problem class M H,V so that with probability at least 1 -δ:1 T Reg DM ≤ ∆ + C inf γ>0 r-dec o γ/8 (co(M H,V )) + γ log Ddim ∆ (M) + log(1/δ) T .We also note that co(M H,V ) ⊆ M co(H),V . Therefore, it remains to upper bound the offset DEC of M co(H),V .Lemma I.7. For γ > 0, it holds thatr-dec o γ (M H,V ) ≤ sup c∈C r-dec o γ/2 (M H|c,V ).Then, we can apply the result of Theorem I.4. From the proof of Theorem I.4, it is not hard to see that: for any ε > 0, there exists γ = γ(ε) such that for any c ∈ C,r-dec o γ/2 (M H|c,V ) + γε 2 ≲ log(2/ε) • (c reg • r-dec c ε (co(H)) + ε),where we also use the regularity condition of ε → r-dec c ε (co(H)). This immediately givesReg DM ≤ T ∆ + O(c reg T log T ) • r-dec c ε(T ) (co(H)),where ε(T ) = log Ddim∆(H)+log(1/δ) T . This is the desired upper bound.Fix a reference model Ď M ∈ co(M H,V ), and then Ď M ∈ M co(H),V by definition. In particular, Ď M has mean value function h Ď M ∈ H and context distribution ν ∈ ∆(C). We also know that for eachc ∈ C, h Ď M (x, •) ∈ co(H| c ).Then, by Lemma C.4, we also have2D 2 H M (π), Ď M (π) ≥ E c∼ν M ,a=π(c) D 2 H R M (r = •|c, a), R Ď M (r = •|c, a) .Thus, we adopt the following notations: For each c ∈ C and model M ∈ M H,V , we define M c ∈ M H|c,V to be a bandit model such that for every action a ∈ A, M c (a) = R M (r = •|c, a). Then by definition, it holds that2D 2 H M (π), Ď M (π) ≥ E c∼ν M ,a=π(c) D 2 H M c (a), Ď M c (a) .Now, combining the inequalities above, we haveEQUATION= infEQUATION≤ infEQUATION= inf p=(pc),pc∈∆(A)EQUATION= supc∈C inf pc∈∆(A) sup Mc∈M H|c ,V E a∼pc h Mc (π Mc ) -h Mc (a) - γ 2 D 2 H M c (a), Ď M c (a) = sup c∈C r-dec o γ/2 (M H|c,V , Ď M c ) ≤ sup c∈C r-dec o γ/2 (M H|c,V ),where the equality ( (M H|c,V ) ≤ 8|A| γ .Therefore, Theorem I.3 implies that ExO + achieves with probability at least 1 -δ:1 T Reg DM ≤ ∆ + O |A| γ + γ log Ddim ∆ (H) + log(1/δ) T .Balancing γ > 0 gives the desired upper bound.As a remark, we provide an example of function class H with log Ddim ∆ (H) ≪ log |H|. • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] .Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] .Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] .Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] .Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical work. There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] .Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.We assume R is known without loss of generality, since the observation o may have a component containing the random reward.In other words, M (π) only depends on π through π0.We remark that their proof actually applies to a broader setting, e.g. the setting of interactive estimation (Example 3, and see also Remark E.5). 
 
 Appendix:  


Decision: This paper introduces a new methodology for proving lower bounds in interactive decision making. The framework is broad enough to apply to standard statistical settings with i.i.d. data, and can recover general versions of the inequalities by Fano, Le Cam and Assouad in this setting. In interactive settings, the new method in some senses improves upon recent work by Foster et al ([25] in the paper) and gives a new quantity in terms of which one can find polynomially matching upper and lower bounds for regret.  

The paper received good scores from the four reviewers (6,6,7,8). I actually believe that stronger scores would have obtained from a slightly improved presentation with corrected typos, a clearer message as in the response to uqGG,  and some more examples, for instance the ones on bandits and contextual bandits in the response to Fyj4. The authors' responses make me confident that all of these issues can be adequately addressed. 

Overall, I think the paper makes a significant contribution, and deserves to be widely known amongst theoreticians in the NeurIPS community.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: See questions
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.
limitations: limitations: The work does not explicitly discuss the limitations of their work; at least, I could not find it anywhere.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: questions: See weaknesses.
limitations: limitations: Essentially no broader societal impacts.
paper_summary: paper_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).
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: Yes.
paper_summary: paper_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."
strength_weakness: strength_weakness: 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: questions: See above.
limitations: limitations: N/A

Comments: title: Please interact with the authors
comment: Thanks for the response. As my questions have been adequately addressed, and I did not identify any major flaws or concerns with the approach, I maintain my current rating, and I believe the paper meets the necessary standards for acceptance.
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 the comments! In the revision, we will add a more detailed discussion regarding the "characterization," high probability version of the lower bounds, integrating Fano, and DC vs $\log|\mathcal{M}|$.

>DC vs $\log|\mathcal{M}|$: I was hoping for more quantitative intuition, actually comparing the two quantities. 

Regarding "DC vs $\log |\mathcal{M}|$": Quantitatively, we always have $\mathsf{DC}_\Delta(\mathcal{M})\leq \log|\mathcal{M}|$.  

Specifically, $p_\Delta^\star=\sup_p\inf_M p(\pi:g^M(\pi)\leq \Delta)$ is lower bounded by $1/|\mathcal{M}|$ when $p$ is chosen as the induced distribution of $\pi_M$ for $M\sim \textup{uniform}(|\mathcal{M}|)$. Thus, $ DC_\Delta(\mathcal{M})= \log(1/p_\Delta^\star) \leq \log|\mathcal{M}|$.  

From this perspective, their relation is indeed analogous to VC dimension vs $\log|\mathcal{C}|$ for PAC learning. We will discuss this more thoroughly in the revision.
Thank you for the response. I maintain my current rating, favoring the acceptance of the paper.
Thank you for your response. I have some more comments.

**"Complete characterization"**: please rephrase it in the final paper.

**Fano/Assouad**:
>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.

I actually think this is a much more understandable and convincing message than the current version of the abstract and intro. "Goal is integrating Fano/Assouad, and we do a sanity check" does get around my concern that the ISDM problem and some lemmas looked artificial.

**DC vs $\log|\mathcal{M}|$**: I was hoping for more quantitative intuition, actually comparing the two quantities. I understand that the difference is pretty analogous, in the qualitative sense, to something like VC dimension vs $\log |\mathcal{C}|$ in standard non-interactive PAC learning. I think a more quantitative discussion would strengthen the paper. But even absent that, emphasizing the qualitative difference more clearly would be useful.

**High probability**: Thanks for confirming my guess. I wasn't sure about the quantile, since I didn't have time to read the proofs thoroughly. I think this would be a good remark to put in the paper.