Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
Authors: Fan Chen
Dylan J Foster
Yanjun Han
Jian Qian
Alexander Rakhlin
Yunbei Xu
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Information-theoretic lower bound
online learning
interactive decision making
statistical learning
minimax lower bound
Primary area: learning_theory
TL;DR: The paper develops a unified framework for lower bound methods in statistical estimation and interactive decision making.

Abstract: We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques---such as Fano's method, Le Cam's method, and Assouad's lemma---are central to the study of minimax risk in statistical estimation, yet are insufficient to provide tight lower bounds for \emph{interactive decision making} algorithms that collect data interactively (e.g., algorithms for bandits and reinforcement learning). Recent work of Foster et al. provides minimax lower bounds for interactive decision making using seemingly different analysis techniques from the classical methods. These results---which are proven using a complexity measure known as the \emph{Decision-Estimation Coefficient} (DEC)---capture difficulties unique to interactive learning, yet do not recover the tightest known lower bounds for passive estimation. We propose a unified view of these distinct methodologies through a new lower bound approach called \emph{interactive Fano method}. As an application, we introduce a novel complexity measure, the \emph{Fractional Covering Number}, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity of estimation. Using the fractional covering number, we (i) provide a unified characterization of learnability for \emph{any} stochastic bandit problem, (ii) close the remaining gap between the upper and lower bounds in Foster et al. (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
Fan Chen
Dylan J. Foster
Yanjun Han New York University yanjunhanenyu. edu
MIT
Microsoft Research
fanchen@mit.cc edu
dylanfosteremmlcrosffftccm
Jian Qian MIT jianqianemit.edu
Alexander Rakhlin
Yunbei Xu National University of Singapore
MIT rakhlin@mit.edu
yunbeiênus.c
Abstract
We develop a unifying framework for information-thewe statistical estimation and interactive decision making. Classical lower bound techniques-such as Fano's method, Le Cam's 's method, and Assouad's lemma- central the study of minimax risk in statistical estimation, yet are insufficient to provide tight lower bounds for interactive decision making algorithms that col- lect data interactively (e.g., algorithms for bandits and reinforcement learning). Recent work of Foster et al. [40, 42] provides minimax lower bounds for inter- active decision making using seemingly different analysis techniques from the classical methods. These results wesults-wiich which are proven using complexity mea- sure known as the Decision-Estimation Coefficient unique to interactive learning, yet do not recover the tightest known lower bounds for passive estimation. We propose a unified view of these distinct methodolo- gies through new lower bound approach called interactive Fano method. As an application, we introduce a novel complexity measure, the Fractional Covering Number, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity estimation. Using the fractional covering number, we (i) provide unified characterization learnability for any stochastic bandit problem, (ii) close the remaining gap be- tween the upper and lower bounds in Foster et al. [40, 42] (up to polynomial fac- tors) for any interactive decision making problem in which the underlying model class is convex.
lower bound
(EEC)-cppurre difficulties
Introduction
The minimax criterion is standard approach to studying the intrinsic difficulty of problems in statis- ties and machine learning. For an algorithm ALG that collects data (either passively or interactively) from the model M, the minimax criterion (stated somewhat informally here) is
min max Cost(ALG, M). MEM
The expression reflects the best cost that can be achieved by an algorithm ALG for a worst-case problem instance in a collection M, measured according to an appropriate cost function Cost. In statistics, the minimax approach was pioneered by A. Wald [90], who made the connection to von Neumann's theory of games [84] and unified statistical estimation and hypothesis testing under the umbrella of statistical decision theory. Minimax optimality and minimax rates of convergence of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

estimators have since become central object in the modern non-asymptotic statistics [82, 89]; here, for instance, ALG is an estimator of an unknown parameter based on noisy observations.
Upper bounds on the minimax value (I) 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 s method, and Assouad's method. These techniques entail constructing "difficult" subsets of the class M. Le Cam's method focuses on two hypotheses, while Assouad's 's method and Fano's 's method involve multiple hypotheses. The relationships between these methods are explored in Yu [96].
Classical statistical estimation is a purely passive task. A parallel line of research [57] 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 deci- sion 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 harder to quantify [4, 68, 69), since it depends on the decisions made by the algorithm itself over multiple rounds.
In spite of the challenges, recent work of Foster al. [40, 42] shows that complexity measure known as the Decision-Extimmatin Coefficient (DEC) leads to both lower and upper bounds on the minimax rates for a general class of interactive decision making problems. Interestingly, the lower bound techniques in Foster et al. [40] proceed in a seemingly different fashion from classical lower bounds for statistical estimation; most notably, their techniques involve an (egorithm-depender (as opposed to oblivious) choice of hard-to-distinguiss 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. [40, 42], it is natural to ask whether there is 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 (estimation-base bbaed) gaps between the upper and lower bounds on the minimax rates for interactive decision making left open by Foster et al. [42].
Contributions. We present new framework for information -thooreticccccccco 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 [40, 42].
Interactive lower bound framework (Section 3). Our main result is to introduce new lower bound technique, the interactive Fano method. The interactive Fano method generalizes the strin- gent separation condition in the classical Fano inequality dition 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 in nature, the interactive
novel algorithm-dependent con-
Fano method as special cases. By virtue of being aigorithh-dependde Fano method seamlessly recovers DEC-based lower bounds for interactive decision making as a special case, and leads to refined quantile-based variants.
Fractional covering number and bandit learnability (Section 4). As application of the interactive Fano method, we derive lower bounds for interactive decision making based on a new complexity measure, the fractional covering number, which quantifies the difficulty of estimating a near-optimal policy/decision, and complements the original DEC lower bounds (which reflect difficulty of exploration opposed to difficulty of estimation). As application, the fractional covering number provides both lower and upper bound for learning any structured bandit problem, up to exponential gap. In particular, finiteness of the fractional covering number is the first necessary and sufficient condition for finite-time learnability of any structured bandit problem. As secondary result, we the fractional covering number to close the remaining gap between the upper and lower bounds in Foster et al. [40, 42] (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.

---

1.1 Preliminaries
Let P and Q be two distributions over space l such that P is absolutely continuous with respect to Q. Then, for a convex function f [0, +00) + (-00, +oo such that (xx) is finite for all x O, f(1) 0, and f(( = limm=o0+ (xr), the f-divergence of between P and Q is defined as
Dy(P.Q) JS'
dP dQ
dQ.
Concretely, we make use of three well-known f-divergences: the KL-divergence DKL. the squared Hellinger distance ii, and the total variation distance Drv, for which the function f(x) chosen to be æ log x. 1 {(v 1)?, and L/2=- - 1| respectively. For a pair of random variables (X, Y) with joint distribution Px,y, v, the mutual information is defined
I(x;)) Ex [KL (Pyix II Py)]
where Pr|x is the conditional distribution of Y|X and Py is the marginal distribution of Y.
2 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 unified fashion. We first introduce the framework and show how subsumes statistical estimation (Section 2.1) and interactive decision making (Section 2.2), then give brief background on existing lower bound techniques and gaps in understanding (Appendix A).
Interactive Statistical Decision Making. An ISDM problem is specified by (X, D. L), where X' is the space of outcomes, M is model class (parameter space), D is the space of algorithms, and L is a non-negative risk function. For an algorithm ALG E 'D chosen by the learner and a model M E .M specified by the environment, observation X is generated from distribution induced by M and ALG: X ~ pprras The performance of the algorithm ALG on the model M is then measured by the risk function L(M, 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:
infALGED SUPMEM A. (M,,, X)).
While main results concern the general problem formulation in Eq. (2), we focus applica- tions to statistical estimation and interactive decision making throughout. Below, we give additional background on these settings and show how to view them special cases.
2.1 Statistical estimation
In statistical decision theory [90, 13, 12], the learner is given the parameter space Q observation space DW decision space A, and a loss function L. For an underlying parameter 6* E θ, n i.dd samples Y, .... Y, ~ Po- are drawn and observed by the learner. The learner then chooses decision A = A(Y, ... Y,)) E A based on the observations, and incurs the loss L(B",A)
Any general statistical estimation problem can be trivially viewed as a ISDM instance, by choosing the model class as M (Pa 0 E } and the algorithm space as D = {ALG yon + A}. For model M = Pe and algorithm ALG, the distribution of the whole observation X ~ par.u is given by
X = (Y
Yn. A),
Yi. Yn Lid Pa. A ALG(Y), ,Yn).
The loss under model M is then measured by the loss of the decision A, i.e. L(M, X)= L(O,A).
2.2
Interactive decision making
For interactive decision making, we consider the following variant of the Decision Making with Structured Observations (DMSO) framework [40], which subsumes bandits and reinforcement learning. The learner interacts with the environment (described by an underlying model M* :I A(O), unknown to the learner) for T rounds. For each round = I...,,
The learner selects a decision x' E II, where II is the decision space.
The learner receives observation of O via of M (T²", where O is the observation space.
3

---

The underlying model M is formally conditional distribution, and the learner is assumed have access to a known model class M C (IT - (())) with the following property.
Assumption (Realizabilitty. The model class M contains M
The model class M represents the learner's prior knowledge of the structure of the underlying envi- ronment. 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, smooth- ness, or concavity). For more detailed discussion, see Appendix B.
To each model M M, we associate risk function -(M,,) II + Rzo, which measures the performance of a decision in IT under M. 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 subooptimaliy during the course of the interaction, given by
RegOM == = (MM"x'))
(3)
where x' can be randomly drawn from a distribution p' E ATTI chosen by the learner at step l. Generalized PAC (Probably Approximately Correct) learning: the goal of the agent is minimize the sub-optimality of a final output decision से (possibly randomized), which selected by the learner once all T' rounds of interaction conclude. We measure performance via
RiskOM (T) := L(M", 7)-
(4)
With an appropriate choice for L, the setting captures reward maximization (regret minimiza- tion) [40, 42], model estimation and sifference-basee learning [23], multi-agent decision making and partial monitoring [37], and various other tasks. In the main text, we focus on reward maxi- mization and defer the results for more general choices L to the appendices (ef. Appendix B).
Example (Reward maximization). In the reward-maximization task, R : O - [0, is a known reward function. ! For a model M E M, [M][[-] denotes expectation under the process
M(), and fM (T) == EM [R(o)] denotes the expected value function. For any M E .M, we let T&r E arg max fM ( be an optimal decision under M. and the risk function is defined by L(M, x)
fM (TM) fM (T). measuring the sub-optimality of the decision π under model M.
DMSO instance of ISDM. Any DMSO class (M, IT) induces an ISDM follows. For any t [T], denote the full history of decisions and observations up to time by 7 (x* (T*, The space of observations X' consists of all X of the form X = (H(T, 7), where मे is a final decision. algorithm ALG (4') (etr)) U (p) is specified by a sequence of mappings, where the 1-th mapping
q'(: )) specifies the distribution of n' based on H²-1, and the final map p(- HT) specifies the distribution of the output decision क based on H" The algorithm space DD consists of all such algorithms. The loss function is chosen to be L(M*, X) = T(M*,5) for PAC learning (4), and L(M X) ΣT= L(M", æ²) for no-regret learning (3). For any algorithm ALG and model M, (...aa.)) is the distribution of X (HT generated by the algorithm ALG under the model M, and we let Ruaas)) !)] to be the corresponding expectation.
3 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 f f-divergence Dj. Let ALG be given algoritim, E ((M) be a given prior distribution over models, and A > be a given risk level. For any reference distribution Q A(X), we define
Pa. PM (L(,X () < A).
(5)
Then, the following lower bound holds:
sup Ex MEM
[LM, [X A
sup (E
{8: EM (Dy (PMMO ( ddsllpa,))
We assume the reward function R is known without loss of generality, since the observation o may have a component containing the random reward.

---

where we denote dz,s(p) Dy 6), Bern(p)) ifp S 1 ö, and dz, 0 otherwise. This result generalizes the classical Fano method the prequel (as well as more sophisticated vari- ants [97, 36, 27J) in multiple ways:
encompasses general interactive learnin//estimation problems in the ISDM framework, as op- posed 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 generalizes the "hard" separation condi- tion required in the classical Fano method to "soft" notion of separation captured by the quantile Pa.Q in Eq. (5). The quantile PA.Q reflects the average separation under "ghost data" X generated from arbitrary reference distribution Q which is independent of the true model M /t-
In addition, instead relying on mutual information, which can difficult to quantify for inter- active problems, we use divergence with respect to the reference distribution Q generalizing central idea in Foster et al. [40, 42].
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 the DEC approach [40, 42] to derive new lower bounds (see Section 3.2).
3.1 Recovering non-interactive lower bounds
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 the non-interactive versions of these methods.
important sanity check to demonstrate that our framework can recover
Fano method. We specialize Theorem to the KL divergence. Observe that for any reference distribution Q.
PM PM-H.X-O(L(M,X) < A)= < sup, μ(M L(M,x) < A).
By choosing Q EM par in Theorem I, obtain the following proposition, which encom- passes prior generalizations of Fano's inequality [97, 36, 27] developed in statistical estimation.
Proposition 2 (Recovering the generalized Fano method). Fix an algorithm ALG and prior distribu- tion μ E (MM) and let I M: X) be the mutual information between M and X under M μ and X ~ PM... The following Bayes risk lower bound holds for all A 2 0:
EAS-IEx-Pe [L(M, (M) 2 A
T (MxX)+ logsup, l (MM.
(6)
When applied to the statistical estimation setting (Section 2.1), the classical Fano method corre-
sponds to the special case of Proposition 2 where ④ = A = {1, 2, ...., m.) L(O,a) 1(0 + a) is the indicator loss, μ = (ni the uniform prior, and A
Note that in Proposition 2, the term log sup, (MM E M L(M,z) < A) in the denominator of 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 detine in Section 3.2, more precisely accounts for the role of decisions selected by the algorithm.
Eq. (6) takes the supremum over the outcome x, resulting
Le Cam's '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 lower bound known as the Le Cam convex hull method [61, 96] which generalizes both approaches.
Proposition 3 (Recovering Cam's convex hull method). For a parameter space θ and obser- vation space y, consider class of distributions P = {Po 0 E θ} S A()) indexed by θ. Let L: x
R., be a loss function. Suppose O, C and θ C satisfy the separation condition
L(O0, a) + L(01, a) 2A, Va E A, E Oo, 01 E e
(7)
Then
A
2 inf sup Ey L(0,AA 2
max 10EA(O0)
(1- (I-Drv (Pg" pe)))
ALG 9g8
5

---

where the infimum is taken over all algorithms ALG yoo A, and p is the distribution on yoor induced by 9 ~ V4, Y (Yi....,, Yn) Lid faror i E {0,1).
Le Cam's convex hull method is the most general formulation of the Le Cam two-point method, which-in its most basic correspooss to the case in which Po and ii singletons. The convex hull method also capable of recovering Assouad's method [96]. It important to note that the classical Fano's method, e.g. in the form of Proposition 2, cannot recover Proposition This is because of fundamental differences between the divergences (KL versus TV) used in the traditional Fano method and the convex hull method.
3.2 Recovering DEC-based lower bounds for interactive decision making
Within the DMSO framework (Section 2.2), Foster et al. [40, 42] introduced the Decision- Esttiiont-ttiaattion 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. [40, 42] through Theorem 1. We focus on the lower bounds from Foster et al. [42], 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 model class M and reference model M IT - A(O) (not necessarily in M), we define the constrained regret-DEC. via
I.d M)
inf sup { (Ex~pI (MM, Da M(()) s $= (8) PEΑ(IT) MEM
and define the constrained PAC-DEC via
p-dec M) == inf sup { [ExxpIL(M,,)) Bang DH ((T)),((T)) S {
p. MEM
Here, the superscript "c" indicates "constrained", and the superscript "r" (resp. "p") indicates "re- gret" (resp. "PAC"). We further define
(Mde = sup p-dec MM, r-dec Meco(M)
sup de (MU (M), Mcco(M)
where co(M) denotes the convex hull of the model class M.
Based on these complexity measures, Foster et al. [42] (see also Glasgow and Rakhlin [44]) provide the following lower and upper bounds on optimal risk and regret, under mild growth conditions on the DECs.
Theorem (Informal; Foster al. [42]). Consider the reward maximization variant of the DMSO setting (Example ). For any model class M and T E N, the following lower and upper bounds hold: (1) For PAC learning,
p-dec (T) (M) S inf sup M. (aiko(issoMMTT) & ALS MEM
where E(T) V1/T and E(T) x VloglM// (up logarithmic factors. (2) For no-regret learning.
(drc) T inf sup EM ReeDMM S r-dec T + T TT(())
ALG MEM
Therefore, up to the loglM| -gap between the parameters e(T) and E(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. [42] through a new variant we refer to as the quan- tile DEC. To do so, we briefly recount the proof technique used by Foster et al. [42].
Given an algorithm ALG, the proof strategy to first fix an arbitrary reference model M, then ad- versarially choose a hard alternative model M E M (in way that is guided by the DEC and the algorithm ALG itself) such that Drv pMr small, yet ALG cannot achieve low risk on model M. This lower bound technique does not explicitly require separation condition between

---

M and M, which is departure from the classical Fano and two-point methods. Thus recover it, the lack of an explicit separation condition in Theorem will be critical. More precisely, for any model M, we consider the following distributions over decisions:
AMLAI M E g'(- [(11) (TI), Preme = EM [p(HT)] E AIT).
(10)
That is, IMa is the expected empirical distribution over the decisions (x T played by the algorithm under M, and Par.u is the expected distribution of the final decision म.
With these definitions, we instantiate Theorem I with the Hellinger distance. We will use the sub- additivity of Hellinger distance (Lemma C.1), which allows us to bound
D (IMM,, paat ma) s 7T' 1E an [
M()))
(11)
Theorem then yields the following intermediate result.
Lemma 5 (Recovering interactive two-point method). Let 5 E [0. 1] be given, and consider an algorithm ALG. Define
AiL. == sup sup sup (A: VPRNa L(M, π MEco(M) MEM A20
V8+ |1TT Ex x D2 (M(T).
Then there exists M M such that pm.ss (M,,
8.
AL5,6
Using Lemma 5, as a starting point, we derive a new quantile-bass variant of the DEC, which we will show can be viewed slight generalization of the original PAC DEC of Foster et al. [42].
For any model M M and any parameter E [0, 1]. we define the ō-quantile risk as follows:
Lx(M, p) = supa20 ( (P>>((((M, x) 2 A) 2 5);
this serves as a measure of the sub-optimality of the distribution E (lI)) in terms of 8-quantile. We now define the quantile PAC DEC follows:
p-dec 5,6 (M, M) == inf inf (m)) SUPMEM { (M)(M))) E DH (M(T). M())).((=)) < < (12)
and define p-dec", a (M) == (EeoMM))( p-dec 2.6 e. (M, Applying Lemma 5, 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 8 [0, be given, and define (T) == L. Then, for any algorithm ALG, there exists M M such that
paat
(RiskoM (T) 2 p-dec p- (
IV
Unlike the original constrained DEC lower bounds (Theorem 4), which are restricted the reward maximization variant of the DMSO setting (Example 1). the quantile DEC lower bound in Theo- rem 6 holds for any risk function L. As a result, the lower bound applies to a broader range of gen- eralized PAC learning tasks, including model estimation [23] and multi-agent decision making [37], where DEC-based lower bounds from prior work are loose in general;
concrete application, we derive a new lower bound for interactive estimation (Example 3) in Appendix F.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 expected risk. However, by specializing (Example 3) and leveraging the structure of the risk function L, we show that quantile PAC-DEC is equivalent its constrained counterpart for this setting, leading tight lower bound.
reward maximization
Proposition 7 (Recovering the PAC DEC lower bound). Under the reward maximization setting (Ex- ample 1), for any > O and 8 E [0,1) 1) it holds that
p-dec (MM) S p-dect
V2c,5 (M) +
4e 1-3"
As a corollary, we may choose and E(T') = 200T in Theorem 6, so that
SuPMEM E. RiskpM (T)) 2 p-dec" 1// (M) 2 ( (M) 8g(T))
1
4
Thus, the quantile PAC-DEC lower bound indeed recovers the constrained PAC-DEC lower bound in Theorem 4.
7

---

Our quantile DEC lower bound extends regret with minor modifications, allowing us recover the regret lower bounds in Theorem 4. We defer the details to the Appendix E.1 (Theorem E.
3.3
Recovering mutual information-based lower bounds for interactive decision making
The following result uses Theorem 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 al. [40, 42].
Proposition 8 (Mutual information based lower bound). Consider the DMSO setting. For any T 2 1 and prior μ E A(M), we define the maximum T-round mutual information (M; )."),
(T) == suPAIG I pLsL [:;
where we recall that (M; H²) the mutual information between M and H. under M a and H2 pa and the supremum laken over all possible DMSO algorithms ALG. Then for any algorithm ALG,
1 sup sup sup B. (MM, ()) MEM
A wu L(M, x) < A) S exp(-22, (1))
(EA(M) A>O
Using Proposition 8, along with mutual information bounds from Rajaraman et al. [70], we recover Q(d/v/) PAC lower bound for d-dimensional linear bandits, which in turn recovers the ((dvT) regret lower bound [30, 73, 57, etc.].
Corollary 9. For d 2 2, consider the d-dimensional linear bandit problem with decision space II = {ar E Fd : ||||2 S 1}, parameter space rewards. The model class is M = (Mo rece, where for each A E O, the model Mg is given by Mo(a) = -N((T 0) 1). Then Proposition 8 implies a minimax risk lower bound:
{0 Fd [|0112 I 1}. and Gaussian
inf SUPMEM I RRikkoM()) (T)] 2 Ω (min(d/vT,1))
(13)
In Section also instantiate Proposition 8 to derive new complexity measure for DMSO.
4 Application to Interactive Decision Making: Bandit Learnability and Beyond
In this section, focus the DMSO setting and apply our general results (Theorem 1) derive new lower and upper bounds for interactive decision making that go beyond the previous results based on the Decision-Fssimmation Coefficient [40, 42] by incorporating hardness of estimation.
Background: Gaps between DEC-based and upper and lower bounds. A fundamental open question of the DEC framework is whether the log MMll-ga between DEC lower and upper bounds in Theorem 4 can be closed. To highlight this gap in a more interpretable fashion, we re-state Theorem 4 in terms of quantity we refer as the minimax sample complexity. Let focus on regret. Recall that for a fixed model class M, the following notion of minimax regret (2) is the
central objective of interest:
Reg" (M, T) == inf supseM M. [RegoM (T))-
Given a parameter A > 0, we define the minimax sample complexity
T (M,, A) == infr2 (T' (M,,) STA)
(14)
as the least value T for which there exists an algorithm that achieves AT regret. Clearly, character- izing T** (M,, A) is equivalent to characterizing the minimax regret Reg"(M,
Consider the following quantity induced by DEC for class M and parameter A > 0:
70EC (M, A) inf (s-2 r-dec S A).
(15)
With this definition, Theorem is equivalent to the following characterization of the minimax sample complexity T (M, A):
7 S S TTC log [M].
(16)
That is, Theorem 4 characterizes the minimax sample complexity up to multiplicative log|Ml M| factor. Our main result this section will to use the fractional covering number and interactive Fano method (Theorem 1), to (i) tighten the above characterization (16) for various special cases of interest, and (ii) give new characterization for TMM, A) in structured bandit problems which avoids spurious parameters such as log|M| altogether.
8

---

4.1
New upper and lower bounds through the fractional covering number
For the a model class M and parameter A > O, we define the fractional covering number as follows:
Nfa (M, A)
inf sup pEA(I) MEM : L)
(17)
Informally, the fractional covering number (M, A) represents the best possible coverage over A-optimal decisions that can be achieved through single exploratory distribution in the face of an unknown model M E M. As we will now show, this quantity naturally arises as lower bound on optimal risk through the interactive Fano method. We begin with the following assumption.
Assumption (Regular model class). There exists a constant CKL > and reference model M such that DKL (M) II (T)) S CKL for all M E M and E II.
Assumption 2 is mild assumption the boundedness of KL divergence. As an example, for structured bandits with means [o, 1] and Gaussian rewards, Assumption holds with CKL = 2- Details and more examples provided in Appendix B.2. Our main lower bound based the fractional covering number follows by specializing Theorem 1 to KI. divergence.
Theorem 10 (Fractional covering number lower bound). Suppose that M satisfies Assumption 2 with parameter CKI. O. Then for any algorithm ALG and A 0, unless T >
log Nivec --2)-2
20kL.
there exists M E MM such that pa' [LM" #) 22>24 2
In particular, for (generalized) no-regret learning, fractional covering number also implies regret lower bound through Theorem 10. That is, for any algorithm to achieve AT-regret, is necessary to have T (log [M (JM, 22)). Combining this with Theorem 4, we conclude that boundedness of both the DEC and the fractional covering number is necessary for learning with any model class M.
Upper bounds based on the fractional covering number. We now complement Theorem 10 by showing that for any reward maximization instance of the DMSO setting (Example 1), boundedness of the fractional covering number alone is also sufficient to derive upper bounds the sample complexity of learning. The caveat is that while the lower bound is logarithmic in Nirac (JM, A), the upper bound will be polynomial.
Theorem (Fractional covering number upper bound). Consider the reward maximization task (Example 1). There exists algorithm that for any class M and A >> O, ensures that with proba- bility at least 1-8
RegDM (T) ST A 0(log((T/)) VT. Nfrac (M,
Combining Theorem 10 and Theorem 11 yields the following bounds T (M,, A) (omitting poly- logarithmic factors):
log Ner.e(MM.. OKL
I TTM, Nirae (M,4/2) A
(18)
The gap between the lower and upper bounds of (18) is exponential; However, for model classes with CKL = O(1), (18) suffices to characterize finite-time learnability. As special case, we now show that fractional covering number characterizes the learnability of any structured bandit problem.
4.2 Application: Bandit learnability
We consider structured bandit setting given by a reward function class H C (II + 1)) The pro- tocol as follows: For each round E [7). the learner chooses decision n² ТI, then receives re- ward p² ~ N (h,, (xx)) ), 1) in response, where the mean reward function h, E H. This corresponds to an instance of the DMSO framework with induced model class Mx = { + (V)(TT), h E H]. We define the fractional covering number for H. via
Ntaa (H, A) Nirac A) = inf sup
(19)
PEλ(I)) NEH p( h(TA)) - h(T) h(T) A
where we denote TA := arg max h(()). This exactly coincides with the notion of maximin volume of Hanneke and Yang [45], which was shown give tight characterization of learnability for the special case of noiseless binary-valued structured bandits. We discuss the connection to Hanneke and Yang [45] in more detail in Appendix G.2.
straightffrward to show that for any structured bandit problem, the induced class Mx satisfies Assumption 2 with CKL = (Example 7). This leads to the following lower bound.

---

Corollary 12 (Lower hound for stochastic bandits). For the bandit model class Mu defined as above, it holds that T (MH, A) 2 2oo Nfrae A)
Combining this result with the upper bound in Theorem 11, obtain the following bounds on the minimax-optimal sample complexity for the structure bandit problem with class H:
log Nire 2A) - TT (MH, A) S MrraeHH.A/3)
(20)
A
This implies that Niaa (H, A) characterizes learnability for structured bandits.
Theorem 13 (Structured bandit learnability). For a given reward function class H. the bandit prob- lem class My is learnable for finite I if and only if Nirac(H, A) < +oo for all A > O.
We remark that the lower and upper bound in Eq. (20) cannot be improved in terms of the fractional covering number alone: (1) For K-armed bandits, we have Ntrec (H, , A) - K, meaning the upper bound is tight. (2) For d-dimensional linear bandits, we have log fre (7,, A} D(d). meaning the lower bound is nearly tight. Nevertheless, the exponential gap in Eq. (20) can be partly mitigated by combining the fractional covering number with the DEC, as we will show in Section 4.3.
Our characterization bypasses the impossibility results of Hanneke and Yang [45]. Specifically, Hanneke and Yang [45] show that for noiseless structured bandit problems, there exist classes H for which bandit lcarnability is independent of the axioms of ZFC. Therefore, their results rule out the possibility of characterization of noiseless bandit learnability through any combinatorial dimension [11] for the problem class. Our characterization is compatible with this result because the argument of Hanneke and Yang [45] relies on the noiseless nature of the bandit problem, and hence does not preclude a characterization for the noisy setting. Additional discussion deferred to Appendix G.2.
4.3 Improved upper bounds for general decision making
To close this section, we derive tighter upper bounds that scale with log Nar (M, A) by combining the fractional covering number with the tion, we focus on regret minimization under the setting of Example 1, and we assume the following condition simplify our bounds (the fully general upper bound detailed in Appendix G.3).
Coefficient. For simplicity of presenta-
Assumption (Regularity of constrained DEC). A function d : [o, 1] + R is said to have moderate decay if d(c) 2 10c Ve 10, and there exists constant 2 1 such that d(e) > e! for all function of e, satisfies moderate decay
d(s')
e' > We assume the function + (coM)., a
for a constant Greg 2 1.
This condition essentially requires that the DEC for co(M) exhibits moderate growth, which means that learning with co(M not "too easy". We now state our upper bound, which tightens Theorem by replacing the logi M dependence in the upper bound with log Vraa(M, A) (with the caveat that the upper bound scales with the DEC for the convexified model class (MM).
Theorem 14 (Upper bound with DEC and fractional covering number). Consider the reward max- imization variant of the DMSO setting. Let M be any class for which Assumption holds, and assume that II is finite. Let E(T) z Vlog Nirac[M, A)/T. Then for any A >> Algorithm (see Appendix G.3) ensures that with high probability,
Regpm I T A (CreTTVVloT) r-dec (co())
Restating this upper bound in terms of minimax sample complexity and combining it with the pre- ceding lower bounds yields the following result.
Theorem 15. For any class M that satisfies Assumption and 3, we have
max (M,, A), log (M.22)) S (M,, (co((c) A)
(21)
up to dependence on Greg and logarithmic factors.
In particular, when the model class M is convex (i.e. co(M) = M) and CKT. = O(). 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 (21) is always tighter than (16) (and also tighter than the result in Foster al. [40, 41J) J),, by definition we have
log Ntrac A) < log Nirae (M, 0) < min (log [M], log I])
As applications, we apply Theorem 15 to structured bandits and contextual bandits (Appendix G).
10

---

Acknowledgements
We acknowledge support from ARO through award W911NF-21-1-0022. the Simons Foundation and the NSF through award DMS-2031883, as well as NSF PHY-2019786.
References
[1] Jacob Abernethy, Kareem Amin, Michael Kearns, and Moez Draief. Large-scale bandit prob- lems and kwik learning. In International Conference on Machine Learning, pages 588-596, 2013.
[2] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
[3] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
[4] Alekh Agarwal, Peter L Bartlett, Pradeep Ravikumar, and Martin J Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions Information Theory, 585)).235-332322 2012.
[5] Noga Alon, Shai Ben-David, Nicolo Cesa- BiaacBBincci, and David Haussler. Scale-sensitive di- mensions, uniform convergence, and learnability. Journal of the ACM, 44:615-631 1997.
[6] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online Icarnability are equivalent. ACM Journal of the ACM (JACM), 69(4))1-34, 2022.
[7] Ery Arias-Castro, Emmanuel Candes, and Mark A Davenport. On the fundamental limits of adaptive sensing. IEEE Transactions on Information Theory, 59(1):472-444 -2112 2012.
[8] Patrice Assouad. Deux remarques esstimation. Comptes rendus des séances de I' l'Académie des sciences. Série 1, Mathématique,
1983.
[9] Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Computational learning theory, pages 299-310, 1994.
[10] Shai Ben-David, David Pal, and Shai Shalev-Shwartz. Agnostic online learning. In Proceed- ings of the 22th Annual Conference on Learning Theory, 2009.
[11] Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Learnabil- ity can be undecidable. Nature Machine Intelligence, 1(1):4448, 2019.
[12] James O Berger. Statistical Decision Theory and Bayesian Analysis. Springer Science & Business Media, 1985.
[13] P.J. Bickel and K.A. Doksum. Mathematical Statistics: Basic Ideas and Selected Topics. Number v. 1 in Mathematical Statistics: Basic Ideas and Selected Topics. Prentice Hall, 2001. ISBN 97801 38503635.
[14] Lucien Birgé. Approximation dans les espaces métriques et théorie de I' l'estimation. Zeitschrift für Wahhscheiiliickkeissheeeee und verwandte Gebiete, 65(2):181-23) 1983.
[15] Lucien Birgé. On estimating density using hellinger distance and some other strange facts. Probability theory and related fields, 71(2):271-291 1986.
[16] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the copnik-chervonenkis dimension. Journal of the ACM (JACM). 36(4))929-965 1989.
[17] Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wabrscheinlickkiissheerr und verwandte Gebiete, 47:119-137, 1979.
11

---

[18] Sébastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. Bandit convex optimization: regret in one dimension. In Conference on Learning Theory, pages 266- 278. PMLR, 2015.
[19] Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49(3):503-532, 2016.
[20] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389-402. IEEE, 2020.
[21] Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):233--2333, 2008
[22] Nicolò Cesa-Bianchi Pierre Gaillard, Claudio Gentile, and Sébastien Gerchinovitz. Algorith- mic chaining and the role of partial feedback in online nonparametric learning. In Conference Learning Theory, 2017.
[23] Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimation coefficients: pac, reward-free, preference-based learning, and beyond. arXiv preprint arXiv:2209.11745, 2022.
[24] Fan Chen, Junyu Zhang, and Zaiwen Wen. A near-optimal primal-dual method for off-policy learning in cmdp. Advances in Neural Information Processing Systems, 35:10521-10532, 2022.
[25] Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing pomdps. arXiv preprint arXiv:2302.01333, 2023.
[26] Fan Chen, Constantinos Daskalakis, Noah Golowich, and Alexander Rakhlin. Near-optimal learning and planning in separated latent mdps. In Shipra Agrawal and Aaron Roth, editors, Proceedings Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 995-1067. PMLR, 30 Jun-03 Jul 2024.
[27] Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. On bayes risk lower bounds. The Journal of Machine Learning Research, 17(1)77887-744, 2016.
[28] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proccedings. 2011.
[29] Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 1999.
[30] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008
[31] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learn- ing Theory, pages 578-598. PMLR, 2021.
[32] David L Donoho and Richard C Liu. Geometrizing rates of convergence, I. Technical Report 137a, Dept. Statistics, Univ. California, Berkeley, 1987.
[33] David Donoho and Richard C Liu. Geometrizing rates of convergence, II. The Annals of Statistics, pages 633-667, 1991.
[34] David I. Donoho and Richard C Liu. Geometrizing rates of convergence, III. The Annals of Statistics, pages 668-701, 1991.
[35] John C Duchi. Lecture notes on statistics and information theory. 2024.
12

---

[36] John C Duchi and Martin Wainwright. Distance-based and continuum fano inequalities with applications to statistical estimation. arXiv preprint arXiv: 1.../111..2000 1,2669, 2013.
[37] Dean Foster, Dylan Foster, Noah Golowich, and Alexander Rakhlin. the complexity of multi-agent decision making: From learning in games to partial monitoring, In The Thirty Sixth Annual Conference on Learning Theory, pages 2678-2792. PMLR, 2023.
[38] Dylan J Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. arXiv preprint MrXiv:2002.04926 pages 3199-3210, 2020.
[39] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspec- tive. arXiv preprint arXiv:2010.03104, 2020.
[40] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 2021.
[41] Dylan Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. arXiv preprint arXiv:2206. 13063, 2022.
[42] Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimattion coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969-4044 PMLR, 2023.
[43] Dylan J Foster, Yanjun Han, Jian Qian, and Alexander Rakhlin. Online estimation via offline estimation: An information-theorede framework. arXiv preprint 2tt:::200410122: 2024.
[44] Margalit Glasgow and Alexander Rakhlin. Tight bounds for 7rregret via the decision- estimation coefficient. arXiv preprint 20X3v=2303.03327, 2023.
[45] Steve Hanneke and Liu Yang. Bandit learnability can be undecidable. In The Thirty Sixth Annual Conference on Learning Theory, pages 5813-5849, PMLR, 2023.
[46] Tatsunori Hashimoto, Steve Yadlowsky, and John Duchi. Derivative free optimization via repeated classification. In International Conference on Artificial Intelligence and Statistics, pages 2027-2036. PMLR, 2018.
[47] Rafail Z Hasminskii and Ildar A Ibragimov. On the nonparametric estimation of functionals. In Proceedings of the Second Prague Symposium on Asymptotic Statistics, volume 473, pages 474-482. North-Holland Amsterdam, 1979.
[48] Ildar Abdulovich Ibragimov and Rafail Zalmanovich Has' Minskii. Statistical estimation: asymptotic theory. Springer Science & Business Media, 1981.
[49] TS Jayram. Hellinger strikes back: A note on the multi-party information complexity of and. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 562-573. Springer, 2009.
[50] Yassir Jedra and Alexandre Proutiere. Sample complexity lower bounds for linear system identification. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 2676- 1681. IEEE, 2019.
[51] Ying Jin, Zhuoran Yang, and Zhaoran Wang. pessimism provably efficient for offline rI? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
[52] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
[53] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
13

---

[54] Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Math- ematical Statistics and Learning, 2(3):311-334, 2020.
[55] Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. Conference on Learning Theory, pages 2965-2992. PMLR, 2021.
[56] Tor Lattimore and Csaba Szepesvári. An information-theoreti approach to minimax regret in partial monitoring. In Conference on Learning Theory, pages 2111-2139. PMLR, 2019.
[57] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[58] Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pages 2488-2515. PMLR, 2020.
[59] Lucien Le Cam. Asymptotic methods in statistical decision theory. Springer New York, NY, 1986.
[60] Lucien Le Cam and Grace Lo Yang. Asymptotics in statistics: some basic concepts. Springer Science & Business Media, 2000.
[61] Lucien LeCam. Convergence of estimates under dimensionality restrictions. Statistics, pages 38-53. 1973.
The Annals of
[62] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi. and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233-22 2024.
[63] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
[64] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable rein- forcement learning not scary? arXiv preprint arXiv:2204.00 08967, 2022.
[65] Guanyu Nie, Mridul Agarwal, Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christo- pher John Quinn. An explore-then-commit algorithm for submodular maximization under full-bandit feedback. In Uncertainty in Artificial Intelligence, pages 1541-1551. PMLR, 2022.
[66] Ian Osband and Benjamin Van Roy. On lower bounds for regret reinforcement learning. arXiv preprint arXiv: 1608.0260002232 2016.
[67] Yury Polyanskiy and Yihong Wu. Dualizing le cam's method for functional estimation, with applications to estimating the unseens. arXiv preprint arXiv:1902.05616, 2019.
[68] Maxim Raginsky and Alexander Rakhlin. Information-batt based complexity, feedback and dy- namics in convex programming. IEEE Transactions on Information Theory. 77(10):7036 7056, 2011.
[69] Maxim Raginsky and Alexander Rakhlin. Lower bounds for passive and active learning. In Advances in Neural Information Processing Systems, pages 1026-1034, 2011.
[70] Nived Rajaraman, Yanjun Han, Jiantao Jiao, and Kannan Ramchandran. Statistical complexity and optimal algorithms for non-linear ridge bandits. arXiv preprint arXiv:2302.06005,, 2023.
[71] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging of- fline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1712-117766.11 2021.
[72] Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. arXiv preprint I 1630, page 54, 2010.
[73] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-41)) 2010.
14

---

[74] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of opti- mistic exploration. In Advances in Neural Information Processing Systems, volume 26, pages 2256-2264, 2013.
[75] Daniel Russo and Benjamin Van Roy. An informatiinnthhorrce analysis of thompson sam- pling. The Journal of Machine Learning Research, 17(1):2442-2471, 2016.
[76] Daniel Russo and Benjamin Van Roy, Learning to optimize via informatiion-iiectee sampling. Operations Research, 66(1): (6(1):230-22) 252,0 2018.
[77] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. arXiv preprint arXiv:2003. 12699, 2020.
[78] Max Simehowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
[79] Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adap- tive sampling in the moderate-confideecce regime. In Conference on Learning Theory, pages 1794-1834, PMLR, 2017.
[80] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[81] Alexandre B Tsybakov. Introduction Nonparametric Estimation. Springer Publishing Com- pany, Incorporated, 2008.
[82] Sara van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
[83] Vladimir N. Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity, 16(2):11, 1971.
[84] John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. 1944.
[85] Andrew Wagenmaker and Kevin Jamieson. Active learning for identification of linear dynam- ical systems. Conference on Learning Theory, pages 3487-3582. PMLR, 2020.
[86] Andrew Wagenmaker, Guanya Shi, and Kevin G Jamieson. Optimal exploration for model- based rl nonlinear systems. Advances in Neural Information Processing Systems, 36, 2024.
[87] Andrew J Wagenmaker and Dylan Foster. Instance-optimality in interactive decision making: Toward a asymptoicc theory. The Thirty Sixth Annual Conference on Learning Theory, pages 1322-1477 1472. PMLR, 2023.
[88] Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Task-optimal exploration in linear dynamical systems. In International Conference on Machine Learning, pages 10641- 10652. PMLR, 2021.
[89] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[90] Abraham Wald. Statistical decision functions which minimize the maximum risk. Annals of Mathematics, pages 265-280, 1945.
[91] Yuanhao Wang, Ruosong Wang, and Sham M Kakade. An exponential lower bound for linearly-realizable MDPs with constant suboptimality gap. Neural Information Processing Systems (NeurIPS). 2021.
[92] Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
15

---

[93] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407, 2021.
[94] Yunbei Xu and Assaf Zeevi. Bayesian design principles for frequentist sequential learning. In International Conference Machine Learning, pages
PMLR, 2023.
[95] Yuhong Yang and Andrew Barron. Information-theorrtic determination of minimax rates of convergence. Annals of Statistics, pages 1564-15999 1999.
[96] Bin Yu. Assouad, fano, and cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, pages 423 433-435.20 Springer, 1997.
[97] Tong Zhang. Information-theeoreie upper and lower bounds for statistical estimation. IEEE Transactions Information Theory, 1274)11007-132, 2006.
[98] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 3532-4570 PMLR, 2021.
[99] Ingvar Ziemann and Henrik Sandberg. Regret lower bounds for learning linear quadratic gaus- sian systems, IEEE Transactions on Automatic Control, 2024.
16

---

Contents of Appendix
A Related Work
17
B Additional Background on DMSO Framework
19
B.I Examples for statistical estimation (Section 2.1)
19
B.2 Examples for Assumption 2...
19
C Technical Tools
20
D Proofs from Section 3
21
D.1 Additional background on classical Fano's method
ret.............................
D.2 Proof of Theorem
22
D.3 Proof of Proposition
D.4 Proof of Proposition 3
24
D.5 Proof of Corollary 9
25
Additional Results from Section 3.2
27
E.1
Recovering DEC-based regret lower bounds
27
E.2
Results for interactive estimation
28
Proofs from Section 3.2 and Appendix
29
F.1
Proof of Lemma 5
29
F22
Proof of Theorem
29
F33
Proof of Proposition
30
F.4
Proof of Proposition
F.5
Proof of Theorem E.3
31
F.6
Proof of Proposition E.2
32
F.7
Proof of Proposition E.4
G Additional Discussion and Results from Section 4
34
G.1 Properties of the fractional covering number
G.2 Additional discussion from Section 4.2
................................
35
G.3 iilioratioonb--Optimmzee
Algorithm
35
G.4 Application: Structured bandits..
G.5 Application: Contextual bandits with general function approximation
39
H Proofs from Section 4 and Appendix G
40
H.1
Proof of Theorem 10
40
H.2
Proof of Theorem 11
41
H.3
Proof of Lemma G.
H.4
Proof of Example 12
42
H.5
Proof of Theorem
42
H.6
Proof of Theorem 15
45
H.7
Proof of Theorem G.5
45
H.8 Proof of Theorem G.6
47
H.9 Proof of Corollary G.7
48
A Related Work
To motivate our results, we briefly survey the most relevant lower bound techniques for estimation and decision making.
Minimax bounds for statistical estimation. There is a vast body of literature minimax risk bounds for statistical estimation, including Hasminskii and Ibragimov [47], Bretagnolle and Huber [17], Birgé [15], Donoho and Liu [33], Cover and Thomas [29], Ibragimov and Has' Minskii [48], Tsybakov [81] as well as references therein. For minimax lower bounds, the most widely applied techniques are Le Cam's two-point method and convex-hull method [61], Assouad's lemma [8], and Fano's method [29]. Variants and applications of these three methods abound [2, 27, 67. 36]; Fano's
method in particular has perhaps the largest number of variants, of which the most general version
17

---

are aware of is due to Chen al. [27], which is recovered by our interactive Fano method (cf. Proposition 2). Another celebrated thread, starting from the seminal work of Donoho and Liu [32], 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 complexity measure known as the modulus of continuity [33, 34, 60, 67].
Lower bounds for interactive learning. There is a long line of work studying the fundamental limits of online learning and reinforcement learning (RL), including lower bounds for structured ban- dits [30, 73, 79, 57, 52, etc.J, contextual bandits [72, 39, etc.J, Markov Decision Processes (MDPs) [66, 31, 98, 92, 91, etc.J, partially observable RL [53, 64, 25, 26, etc.J, dynamical systems and con- trol [80, 50, 78, 85, 99, etc.J, and offline RL [71, 93, 88, 51, 24, 62, 86, etc.J. Most of these lower bounds are proven in case-by-car basis, as the constructions of hard instances are specialized to the specific settings.
Decision-Estimattoo Coefficient. Toward unifying understanding of the minimax complexity for interactive decision making problems, Foster et al. [40, 42] introduce -astimattn Co- efficient (DEC) as complexity measure and show that characterizes the minimax-optimal regret up to a logl.M| factor. The DEC can be viewed as an interactive counterpart of the modulus of continuity [32], 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 variety of more general decision making settings [40, 41, 23, 42, 37, 44], including adversarial decision mak- ing [41], PAC decision making [23, 42], reward- free learning and preference-baser learning [23], and multi-agent decision making and partial monitoring [37].
However, there a remaining gap between the DEC lower and upper bounds [40, 42), which closely relates to the complexity of estimation. Specifically, through the DEC framework, the sample com- plexity (number of rounds required to achieve e-risk) characterized as
TOE (M,,) X # sample complexity S T (0EC(M X Est(M),
where 7 (M,, 2) is quantity measuring the complexity of exploration, and Est(MM is a measure of the complexity of online estimation over M. The dependency on Est(M) can be necessary: For example, in linear bandits, the optimal sample complexity scales as d² /e/e", while (M, x d/E?, and (st(M)= x d. However, the complexity of estimation Est(MM is missing from the DEC lower bound. This gap remains one of the main open questions in the DEC approach.
One potential reason is that the DEC lower bound does not recover Fano's method or Assouad's lemma, as it essentially generalizes Le Cam's 's two-point method. More specifically, while the statis- tical estimation task is subsumed by the DMSO framework, the DEC lower bound specialized to this setting at best recovers Le Cam's two-point method. On the other hand, the 2dd2 /E") lower bound for linear bandits is typically proven through Assouad's lemma [18] or Fano's method [70], similar to its statistical estimation analog. Therefore, to close the remaining gap in the DEC approach, is necessary to have deeper understanding of the latter two methods in the interactive setting.
Additional related work. large portion of the aforementioned lower bounds for interactive learning are proven using (variants of) the two-point method and can be recovered by the DEC lower bound approach [40, 42]. Beyond the two-point method, comparatively fewer lower bounds for interactive learning have been established using Assouad's 's lemma or Fano's 's method [21, 72, 3, 69, 39, 78, 70, etc.). The approaches in these papers are specialized to the specific settings under consideration, and there is not a general principle through which Fano's 's method or Assouad's 's lemma can be lifted to handle interactivity. Indeed, the challenge of applying Fano's 's method in interactive contexts has been highlighted in various prior works, e.g., Arias-Castro et al. [7, Section 1.3] and Rajaraman et al. [70, Section 1.5.4].
The DEC is also closely related to a Bayesian complexity measure known as the information ratio [75, 76, 56, 55, wwhic 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) [94], developed for frequentist algorithms. Additionally, the DEC is connected to asymptotic instance-dependent complexity, as explored by [87].
Formally, the quantity DEC (MM, here is the sample complexity implied by DEC (cf. Section 4).
18

---

B Additional Background on DMSO Framework
The DMSO framework (Section 1.1) encompasses wide range of learning goals beyond the reward maximization setting [40, 42], including reward-free learning, model estimation, and preference- based learning [23], and also multi-agent decision making and partial monitoring [37]. We provide two examples below for illustration.
Example 2 (Preference-based learning). In preference-based learning, each model M M is + R (where CM (T1, #2) typically the probability of T2 for T1 ~ (M, #1); 72 (M, 72)); and the risk function is specified by L(M, x) max,* CM (M"" (T),,)) Chen et al. [23] provide lower and upper bounds for this setting in terms of Preference-based DEC (PBDEC).
assigned with a comparison function CM IT x
Example 3 (Interactive estimation). In the setting of interactive estimation (a generalized PAC learn- ing goal), each model M M is assigned with a parameter 0M O, which is the parameter that the agent aims to estimate. The decision space II = II x O, where each decision π E II consists of π (To, l). where xo is the explorative policy interact with the model", and 0 is the estima- tor of the model parameter. In this setting, we define (MM, T) Dfs 0) for certain distance D.)
This setting is an interactive version of the statistical estimation task, and it is also generalization of the model estimation task studied in Chen et al. [23]. Natural examples include estimating some coordinates of the parameter 0 in linear bandits. We provide nearly tight guarantee for this setting in Appendix E.2.
Applicability of our results Our general interactive Fano method Lemma applies to any gen- eralized no-regret / PAC learning goal (Section 1.1). Therefore, our risk lower bound in terms of quantile PAC-DEC Theorem 6 and fractional covering number lower bound Theorem both apply to any generalized learning goal. For concrete example, see Appendix E.2 for the application to interactive estimation.
B.1 Examples for statistical estimation (Section 2.1)
Example 4 (Mean estimation). For the mean estimation task, the parameter space ② C Rdd, and for each 0 E θ, Po N N(,, Ta). The goal is to estimate the ground truth parameter 0*, i.e., the decision space is A = R4_ and the loss is given by A0) = 0 - All, where ||-I| is a norm over Rd
Example (Functional estimation). In the functional estimation task, function T + R is given, and the goal is to estimate the value of T(0*), i.c., the decision space is A = R, and the loss L(0, A) (() Al.
Example 6 (Density estimation). In the density estimation task, the goal is to estimate Po., i.e., the decision space A C A()), and the loss is given by L(8, A) D(Po, A), where D is a certain divergence (e.g.. TV distance or KL divergence).
B.2 Examples for Assumption 2
In this section, we provide three general types of model classes where Assumption 2 holds with mild OKL- It is worth noting that in Assumption 2, the reference model M does not necessarily belong to (M..
Example 7 (Gaussian bandits). Suppose that 7. S (AA + [0, 1]) is a class of mean value function, and Mx,V is the class of the model M associated with hed H:
M(r) ((h 1). A.
Then, consider the reference model M given by M(T) = NOO 1)V7 E A. is clear that for any ा and model M E MHH..
(ML(M(T) (()) } 1M (T)² < 2'
1
and hence Assumption 2 holds with CKI. 2
In other words, M (x) only depends through mo.
19

---

Example 8 (Problems with finite observations). Suppose that the observation space O is finite. Then, consider the reference model M given by M()) = Unif(O)Vr E IT. holds that
(M) (()) - log [O], VI E II.
and hence Assumption 2 holds with OKL log O).
Example can further be generalized to infinite observation space, as long as every model in M admits bounded density function with respect the same base measure.
Example (Contextual bandits). Suppose that H. C (C x A + [0, 1I) is class of mean value function, and MH, is the class of the model M specified by value function hMd and context distribution Var E ACC). More specifically, for any E II = (C + A), ((T) is the distribution of (c, a, r). generated by e ~ PM, a [c), and r N(hh (c, (c,a),
Then, consider the reference model M specified by VM = Uni and ha = 0. It is clear that for any n, and model M E MM,V.
DKL (M (T)) S log |C] +
and hence Assumption 2 holds with OKL log C| +
The factor of log [C] in Example due to the definition (45) log Nire (H, A), where we take supremum over all context distribution μs. This factor can be removed if we instead restrict the model class to have common context distribution (i.e., the setting where context distribution known or can be estimated from samples).
C Technical Tools
The following lemma is the "chain rule" of Hellinger distance [49] (see also Duchi [35, Lemma 11.5.3] and Foster et al. [43, Lemma D.2]).
Lemma C.1 addiiiviiyv for squared Hellinger distance). Let F1), (Kr, Fr) be se- quence of measurable spaces, and let X II X, and F 2i-1 Fc. For each t, let Pe
and Q .) be probability kernels from (X+-1 [t-1 10 Fz).
Let P and Q be the laws of X1 N1....,No Nx under X1 ~ Pt(, | X1--1) and X, ~ Q' | X1a-1) respectively. Then holds that
T DP (1a-))) Q' Xia-1)) (
(P,00) ST
(22)
In particular, given T-runnd algorithm ALG and model M, we can consider random variables
X1 = (mr..0²) )..... Xx (xx" ,0")) Then, PM (X,, = X1=t11) is the distribution of (r* o²), where x' ~ p- nI o² -- , o and of ~ M(*)). Therefore, applying Lemma C.1 to
D (PMMs ppat gives the following corollary.
Corollary C.2. For any T T-round algorithm ALG, it holds that
1 DTV (pariss p.S. pos)oo22 < Di (pMsAs IpS..0)) S TT Ex-Pa [ (()))
2
Lemma C.3 (Foster et al. [40, Lemma A.4)). For any sequence of real-valued random variables (Xi)er adapted to a filtration (Fi)esr it holds that with probability at least 1 - 5, for all t S T,
log E [exp( 1osp(-X.lo X F. S Σ x. log (1/5).
Lemma C.4. For any pair of random variable (X,Y) Y). it holds that
Ex-ex [D] (Prix, Qy1x)] 2D (Px,,, Qxx).
20

---

Lemma C.S. Suppose that for random variable X, its mean and variance under PP is pip and of. and its mean and variance under Q is μo and oz Then it holds that
Ie - uul S 4
oz oā + 1z2 - 11mp-nal DH (P.Q)-
In particular, when pe, HQ, op, oq E [0, 11, we have D Q) 2 To Mp pgll" On the other hand, when P (uu,, 1), Q = Nu 1), then D2 (TP Q) S glur uel?
Proof. Let V/ = P+2 be the common base measure and set μ = Me Mg Then 2
2
110 - me
EEp
X
Eg[X
u
dP
dP
X 11)
dv
dv
dP
dP
dP
dP
En
V dv
+
(X 1))
dv
dv
dv
2D (IP Q) 2 1xx(X
112
BB(X - 11)
oF + oB 1 up uel?)
1
)
DR (P,Q).
D Proofs from Section 3
In this section, we present proofs for the results Section 3, except Section 3.2.
Before proceeding to proofs, we first discuss the classical Fano's 's method to motivate our approach.
D.I Additional background on classical Fano's method
To motivate our approach, which can be viewed as generalization of the classical Fano method [29], let us briefly recall the classical approach and highlight some shortcomings. The classical Fano method applies to the statistical estimation setting Section 2.1 (a special case of ISDM), and takes the following form.
Proposition D.1 (Classical Fano method). Consider the statistical estimation setting (Section 2. with parameter space O. Suppose that there exist 0I,...,,0 ,m E O such that the following separation condition holds:
L(O,, a) + L(0,, 2 2A, Vi VijjE [m], Va], E A.
(23)
Let μ be the uniform distribution over (01, 0m) J. and let I (0; Y) denote the mutual information iid
of (0, Y) ~ Py generated by 0 ~ p and Y = have
Yn)
~ Po. Thenfoor any algorithm ALG, we
Ea-n,Y~P (L(O,ALG(Y)) 2 A sup(ō I, Y) kl(1 - 1/m)), 5>0
(24)
where the binary KL divergence is defined kl(p || 9) DKL (Ber((p) Bern(g)). This implies the minimax lower bound
infALG supece Ey [L(0,ALG(Y ALG(()) I 2 (1 [=(0;
(25)
log m
The log m factor in Eq. (25) reflects the complexity of estimation in the parameter space, which is key concept aim incorporate into interactive decision making. Looking deeper, the "estimation complexity" term log m in Eq. (25) arises from the "quantile" parameter 1 1/m appearing in the Eq. (24). This parameter reflects the fact that under the separation condition (23), the following quantile probability is at most 1/m for any distribution Y ~ Q:
1
P Po (I < A) S sup PapPo (L(0,)) < A <
(26)
21

---

Note that in this expression, 0 is drawn from the uniform prior j and Y is drawn independently of To deduce Eq. (24), it suffices to choose Q = Eo-y Pe and apply data-processing inequality:
I Y) 2 (L(O, ALG(Y)) < A) || P (L 2 (LO,, ALG(()) < A) 1/m)..
< A))
In particular, for any å E (0, 1) such that I (8: S kl(1 - || 1/m), we have )))) < A) < 6, using the monotonicity of the KI. divergence. This argument gives Eq. (24) immedi- ately, and by choosing 8, = 1 (+ in Eq. (24), we arrive in the canonical statement in Eq. (25).
log
To summarize, the structure of the classical Fano lower bound involves (i) a prior μs, (ii) reference distribution Q = Eg-yPe, and (iii) a quantile parameter determined by the (iv) separation condition (23) in the argument above. Crucially, we understand that the complexity of estimation log m arises from the quantile probability P F (L(0, (L
ALG(Y)) < A), and the only use of the
traditional separation condition (23) to further bound this quantile by 1/m as Eq. (26).
Having gained these insights into classical Fano method, we would like to point out several limitations:
First, in the form above, is only applicable to statistical estimation rather than general interactive settings.
Second, it relies on mutual information due to the choice of the reference distribution, which depends on the evolution of the algorithm over all T rounds in interactive settings, making it difficult to analyze many interactive problems.
Third, and perhaps most importantly. the separation condition (23) must hold for an arbitrary decision a. This "hard" separation condition unlikely hold for general model classes, as noted throughout the DEC approach [42, Remark 2.3] line of work.
To address these shortcomings, we make use of core concepts (prior, reference distribution, quantile parameter, separation condition) above, but adopt a new perspective that emphasizes and generalizes the role of the quantile probability P (L (L)))AL(() < A).
D.2 Proof of Theorem
In the following, we fix prior μ A(M). parameter A > f-divergence Dy, and an algorithm ALG. For simplicity, we denote D y) (Bern(r)), Bern(y)) for x, E [0, 1].
We first prove the following quantile lower bound:
P PM (L (L(M, X) 2 A) >
sup (x))x))
(0: (Dr=a(Ds(PPa Q) < d).(())))))
(27)
We only need to prove the following claim.
Claim. Suppose that there exists a reference distribution Q such that
d5.6(Pa,0) EM D (TMMMM Q),
then IP
(L(M, A) 2 6.
We denote Pa = PMru.XmpM.a (L(M,X) < A). and recall that we define Pa.0 = P (Mmmxx=Q(L(M)) (L(M, X) A). We then consider the following two distributions over M x X:
Po M U,X ~ pprau
P:: M x Q.
By the data processing inequality of f- f-divergence, we have
Dy S (Po,, (1 P1) = EM D (IPM..u Q).
Therefore, using d (p..() > EMwyD (FMM. Q2), we know that ds.s(Pa.)) > Dy(ps. In particular, this implies PI.Q < 1 5, and
Dy(Ps.PA.)) < - 8,pa.))
-
22

---

Hence, consider Pa.Q < - 6. For case (2), we can use the monotone property of Dy (Lemma D.2), which also implies Pa < 1 d.
(1) Pa S Pa.Q. and (2) Pa PA,0- For case (1), we have PA S
Therefore, it holds that Pa < d, and
P Mm (L(M, 2 A) =1 PA > 8.
Hence, the proof of Eq. (27) is completed. The in-expectation lower bounds then follows from the fact that
EM..B (LM, MMw. (L(M, A).
Lemma D.2. For z, E [0, 1]. the quantity Dy(x, y) is increasing with respect when x 2 y.
Proof of Lemma D.2 Fix any
2 x >
2 2 y 2 0, we define
x E
[0, 1},
I- z E [0, 1). == (1 y)
x
I
Then, by definition,
p(1 2) -z =
p(1 3) qy y,
and hence for the channel P from {0, to itself given by P(-10) = (ern()), = Bern(q), it holds that
Po Bern(x) = Bern(=),
Pe Bern(y) = Bern(y).
Therefore, by data proccesocessngggg inequality, we have
(B(B)r(2)),Bnn) < Dy (Bern((x) Byrn(y)).
This is the desired result.
D.3 Proof of Propasition? 2
Fix the parameter A > 0 and let E A(M) be given. To apply Theorem 1, we consider KL divergence (corresponding to fxx) log 2) and choose the reference distribution
Em~HPe pMr.s
Then, by the choice of Q and definition of Ki-divergence, have
SML (pm Q = L (X)
and by definition, we have
PA.0
X') A) Supp(M L(M,a) < A),
(28)
By Theorem 1, for any 8 E (0, 1) such that T M; X) < kl(1 - || PA.G), we have
Ex.MEx L(M 2 6A.
In particular, we may choose
I J_A log?
8. 1 +
log sup, μ(M: L(M, x) < A)
As long as 8- > 0. we have E (TMM, X)) S.A. This gives the desired lower bound (note that if 6, S 0. there is nothing prove).
[, X)
kl(1 6, || (A.2), and hence
O
23

---

D.4 Proof of Proposition 3
We recover this result by applying Theorem 1 with TV distance. We first frame the problem in the ISDM framework. Consider the "enlarged" model class M (Mr U E A())), where for any algorithm ALG yon -> A. the distribution P.M.,ALG is given by
(Y,)L)(Y) p.M.,ALG; 0 ~ v. (Y, Yn) Lid Pp-
In other words, APM, is the distribution induced by the prior and the algorithm ALG. We then extend the loss function to L : M x X' R+ as inf L(O, ALG(Y)), L(M,, agsupp(u)
XA = (Y)ALG(Y)) EEA
By the separation condition (7), we have L(M,, + L(M,, X) 2 2 for any vo E A(O)).
in A( Therefore, choosing the prior μ = Unif( Unif([M, (Mo, My,3) and the reference distribution Q = EM IPM gives
PA. = PM (L(M, < A) 1/2
and by the data data-procese processing inequality,
1
E
|DVV Dry (pMa.s Q11 Drv (polo) MLG Q) + Drv (P.Mo,, ALG 2))
2
1
- Drv (p-Moo ALG MM, .LG) I 2
Drv (pign, p!
2
Therefore, for any 0 s 8 < Div (P potn). we have
EM Drv (EMMA Q)) S drv.s(pa.c),
and hence applying Theorem gives
A (1- Drv (pre" pon))
E 2u Ey [LO,, ALG(Y))) 2 Taking the supremum over Py E ((0)) and 1 E A(01) gives the desired result.
2
We can use the Le Cam convex hull method to recover the classic two-point method and Assouad's method, as follows.
Example 10 (Le Cam's two-point method). In Proposition 3, we can take the distribution up (V1) single point in Oo (G1), to recover the classical two-point method. Concretely,
to be supported under the setting and assumption of Proposition 3, we have the following two-point lower bound:
infALG supsce L(0, ALG(Y)) A maxe P1E0, (1 DTV (P p(r)
where per is the distribution of Y (Y Yn) LLd Po.
Example 11 (Assouad's method). Suppose that θ = { - 1, 1]dt for some d 2 1, and that the loss function has the following coordinate-we structure:
L( = Σ (0,
WEO,aEE
#=1
We write 0 ~ 0' if 0 and 0' differ only in the j-th coordinate. Assume that the following separation condition holds for all j E [d]:
(0, + (0', a) 2 24, Va A,0~,, 6..
To apply Proposition 3, consider 0 = (0 0g i) for i E {0, 1) and j [d]. Then, for each j E [d], the separation condition (7) holds for the loss Lg and the subsets 6/ O¹. Therefore, applying Proposition for each j E [d] with of Uni and of Unif(0)) gives the following Assouad-type lower bound:
dA
inf sup Ey-n, L(00, 2
min (1 Drv (P@" PS"))
ALG aee
3/:8~;0
24

---

D.5 Proof of Corollary 9
Consider the following setup of linear bandits: let 0* E Rd be an unknown parameter. At time the learner chooses an action o' E { E Rd || S 1] and receives Gaussian reward be the observed history up to time T. The central claim of this section is the following upper bound on the mutual information.
r ~ , ; 1). For 7 E N, let H = (n (r,,
ा r")
Theorem D.3. For any > O, we define the prior pe over (r) by
Py 0 N (0.4d) 4d Ju)
|10 Sr.
Then for any algorithm ALG, have
T²T 1
(0,,m S dl dllog]
4d
Proof. Denote À T. We first prove that if 0 μ =N(0,, Ala/d), then
XI d2
J (0:; ;²) S log 1
(29)
By the Bayes rule, the posterior distribution of 0* conditioned on (H²-1, , is
p(0" | 11'11,7 x²) x exp
rr*
10 ;,)))
2A
s<
which is a Gaussian distribution with covariance
(E'-1)-1, where
hーZ d
Σ TT"""
Therefore, by the chain rule of mutual information, we have
100 H
Σ
3 1²-1,
=
B.,
log (1 + (T')
2
1=1
1
det
BV,ALG
log det (I1-1)
t=1
1
dET
BB.ALGG
log (d/A)d
2
d
Tr(ET))
LBMALGG
log
2
d/>
XT
1 log
1
d2
which is exactly Eq. (29).
Next we deduce the claimed result from Eq. (29). Consider the random variable Z
111011/2 rr E {0, 1}. and then
d log
AT
1+
2 [="
2
d2
2 : (2)
P(z 1) L ALo : H 1)
25

---

( St) A H²))
Here the first inequality is Eq. (29), the second inequality follows from I(X;Y) - f(X)) -) conditional mutual information. Finally, noticing that P. (u I r) by concentration of xa random variable, arrive at the desired statement.
X) O, the third identity follows from the definition of
Next we show how translate the mutual information upper bound in Theorem D.3 lower bounds of estimation and regret.
cod vT 1 for a small absolute constant co. and consider the prior μ py- For any T T-round algorithm with output म,, Proposition 8 implies that
Theorem D.4. Let T 2 L min
{
0-
27
2 4
00-
Therefore, we may deduce that
sup M M-EM
EMd Riskpm (T) 2 min
VT 5
Proof. We first prove the first inequality by applying Proposition 8 to the following risk function L(Mo, x) = || normalize(0)
where we denote normalize(f) = |0|| E BB(1) (1). Notice that for 0 E O, we have
L(M,, x) = =|0|| - (0, π) 2 ||0||
||l|| L(Mo.
|0| =
For A 10, we first claim that
Pa == sup u (0: L(Mo T) S = -
(30)
x
To see so, by symmetry of Gaussian distribution, we know for fixed any E Bdd
ra iMMM, T) s A) Po- (0: |0 2 < A
and hence we can instead consider the uniform distribution over the sphere Sd-1, By rotational invariance, we may assume that π = (xr, -,... ,0), with æ 2 0. Then
{
x² +1 -
{0 E E 110 112 S }}
0 E ga-1;
c sf0Est :0 2 V
2x
By Bubeck et al. [19, Section 2), for Unir(gd-1), the density of 0, E [-1,1] is given by T(d/2)
f(01) [((d 1)/2) (1 (d-
Therefore,
PA <
f(01)d0; O(Va) (1-
v1 A) ()-3)/2 1/33 (V
With the upper bound (30) of Pa. know that for A = J. it holds log(1/pa) 2 (T), as long cu is sufficiently small constant. Therefore, Proposition 8 gives that 1
normalize(f)]1 Ru.us 7. i. 7)
This completes the proof of the first inequality.
Finally, using the fact that Por (0)00(11001 S cir) S 100 for small absolute constant C1 we conclude that
sup BMT,NG -M "<iss<M (T)) 2 Bu [ x) 2 cr 2 min { VT 1))
M.EM This is the desired result.
26

---

E Additional Results from Section 3.2
In addition to the mexard-maxinization setting (Example 1), we also introduce slightly more gen- eral setting. In this setting, we assume that for each model M M. the risk function is L(M, x) f (Txx) fM (T)) but fM is not assumed to be the expected reward function (Example 1). Instead, we only require far satisfying the following assumption, where MM C (II + (())) specified model class of reference models that contains co(M) (following Foster et al. [42]). The lower bound we prove can be stronger by allowing M be a larger model class.
pre-
Assumption 4. Let M C (II A(O)) be a given class of reference models, such that co(M) S M For any M M, the risk function takes form L(M,T) π) (" far (T) for some functional for : 11 - R. so that f can be extended to M succ that for any model M E M and reference model M MM+ we have
15"(M) (T)) C M()),
VT Tmell III
(31)
In some cases, considering larger reference model class M can be convenient for proving lower bounds, see e.g.. Appendix B.2 and Appendix H.7.
E.1 Recovering DECC-based regret lower bounds
In this section, we demonstrate how general lower bound approach recovers the regret lower bounds of Foster et al. [42], Glasgow and Rakhlin [44]. We first state our lower bound terms of constrained DEC in the following theorem.
Theorem E.1. Under the reward maximization setting (Example for any Troundd algorithm ALG, there exists M E .M such that
T 2
(r-dec - -GE(T) -1
RegoM
with probability at least 0.01 under pM MI where s(T)
100VT'
Theorem E immediately yields an in-expectation regret lower bound in terms of constrained DEC. It also shaves off the unnecessary logarithmic factors in the lower bound of Foster et al. [42, Theorem 2.2].
For the remainder of this section, we sketch how we prove Theorem E. in a slightly more general setting (Assumption 4), following Appendix F.3. Before providing our regret lower bounds, first present several important definitions.
Definition of quantile regret-DEC We note that is possible directly modify the definition of quantile PAC-DEC (12), and then apply Theorem 6 to obtain an analogous regret lower bound immediately. However, as Foster et [42] noted, the "correct" notion of regret-DEC (ef. Eq. (8) 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 I'. Define
I
π
: न
8RL where TI, "T
Fr E II C
T
i.e, HT the class of all T-round mixture decision. We introduce the mixture decision space IT here to handle the average of T-ouund profile (* RT) of the algorithm. In particular, when II is convex, we may regard 11. II.
Next, we define the quantile regret-DEC as
r-dec (M,, ==
inf sup { (M. (LM, Emn Di (((T), s {e²] PEA(IIT) MEM
(32)
and define r-dec_ 2, (M) := SuPMEM+ rede (M, M). 5.5
The following proposition relates our quantile regret-DEC to the constrained regret-DECC (proof in Appendix F.6).
27

---

Proposition E.2. Suppose that Assumplion 4 holds for M. Then, for any M E M it holds that r-dec (M), & r-dec (M, M) + csCre,
}. In particular, holds that where we denote c9 = max { 1-n:
r-dec (,1
IV
max - (M), -CG)) MEM
Lower bound with quantile regret-DEC Now, we prove the following lower bound for the re- gret of any T -round algorithm, via our general interactive Fano method (Lemma 5). The proof is presented in Appendix F.5.
Theorem E.3. Suppose that Assumption 4 holds for M. Then, for any T-round algorithm ALG, parameters E, C, there exists M M such that
pasas RegoM (T) 2 T ( CC,,) 2 C
1
VIATE?.
As corollary, there exists M E M such that
RegoM (T) 2
T
M) max r-dec Ecry (MU (MM) 4CGE(TT) MEM!
2
T'
(1-dec (M) 4C(e(T)) -
2
with probability at least 0.01 under Ipa" uu, where s(T) 100VT
Theorem E.1 is now immediate corollary, because for reward- wwward-maximization setting, always have C, = 2 in Assumption 4.
E.2 Results for interactive estimation
More generally, we show that for a fairly different task of interactive estimation (Example 3), we also have equivalence between quantile PAC-DEC with constrained PAC-DEC.
Recall that this setting, each model M E .M is assigned with a parameter 0,, O, which the parameter that the agent want estimate. The decision space 1I = 1lg θ, where each decision т 1I consists of π = (To, 0), where xo is the explorative decision to interact with the model, and 0 is the estimator of the model parameter. The risk function is then defined as L(M, π) p(0 0), for certain distance +).
In interactive estimation, we can show that the quantile DEC is in fact lower bounded the constrained DEC, as follows (proof in Appendix F.7).
Proposition E.4, Consider the setting of Example 3. Then as long as < }, it holds that
(MM < 2 p-dec_.(M))
In particular, for such setting (which encompasses the model estimation task considered in Chen al. [23]). 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 restricted Example 1, and we have hence shown that
(M) S inf sup "MM (RiskoM(7)) S p-dect p-dec (TT)
ALG M-EM
where (T) x V1/T and E(T) x PAC-DEC also nearly tight complexity measure.
Therefore, for interactive estimation, constrained
Remark E.5. The log [MI-gap between the lower and upper bound can further be closed for convex model class, utilizing the upper bounds in Appendix G.3. More specifically, consider convex model class M, where M + Ow is a convex function on M. Then, suitable instantiation of ExO+ (Algorithm 1) achieves
Riskpm (T) A inf (Md + log N (O, A) + log(l/0) 7>0
T
28

---

where N(O, A) is the A-covering number of O because have log Nfrac (M, A) log N(,, A) by considering the prior = Uni for minimal A-covering of θ. Similar to Theorem H.5, can upper bound p-dec;, (M) by (M) Taking these pieces together, we can show that under the assumption that p-dec" (M) is of moderate decay, ExO* + achieves RiskpM(T) 2 p-dec ( (M),
where e(7) Vlog 1/T,
In particular, for the (non-interactive) functional estimation problem (see e.g. Polyanskiy and Wu [67]) the parameter space @ C IR, and hence by considering covering number, have log |+|
(1). Therefore, for convex M, under mild assumption that the DEC of moderate decaying (Assumption 3), the minimax risk is then characterized by (up to logarithmic factors)
inf sup "ee""""Riskko (T)] p-dec V1/T (M).
ALG M+
This result can be regarded as a generalization of Polyanskiy and Wu [67] to the interactive estima- tion setting.
F Proofs from Section 3.2 and Appendix E
Additional notations For notational simplicity, for any distribution q E AIII and reference model M, we denote the localized model class around M
Mg.e(M) = { M E E. Exng Dj (M(z), M(T)) s E
F.1 Proof of Lemma 5
To apply Theorem 1, we consider the squared Hellinger distance (which we recall is a f-divergence
corresponding to f(z) = 1 [VE - 1) Consider a fixed tuple (M,M, A) with M E M, M e
co(M), and A 2 that satisfies
( L(M, σ) Z
V8++ / |14T BATTE--RRaa Di (TT)
(33)
We choose the reference distribution to be Q P p and take to be the singleton distribution supported on M. Recall that for the DMSO framework, the observation X (H" f). and the loss function is L(M, X) = L(M, (Section 2.2). Then, by definition, we have
Pa.q P. Px~q Pxxx(L(M,M)) (L,M, X) < A) = Prt.us(TT L(M, T) A). Further, using the sub-additivity of Hellinger distance (11), we have
D (IpM..u p..... I 7T E D (M()),
Therefore, using the condition (33), we have
2
2 V8 VT PA.0) > D3 (PMM pm...
Hence, it holds that D (PM
D (1 5, pp..) and applying Theorem gives
par (L(M, #) 2 A) 2
Taking supremum over pairs (M, M, A) satisfying Eq. (33) gives the desired lower bound.
F.2 Proof of Theorem
Fix any algorithm ALG and abbreviate ET). Take arbitrary parameter Ao p-dec (M). Then there exists M such that Ao < p-dec E.d (M, M). Hence, by the definition (12), we know that
Ao < sup { [L, (M.PP MEM
Enognade Di (M( < <=²
Therefore, there exists M M such that
Ex us This immediately implies
D2 (TT,, M())) S
PROPS as (L(M,T) 2 Ao) 2
Pst NO L(M.T) A) Vor 14T Di (M(T),
where Voi V0 VI4TE2 Notice that 8, by the choice of & 1/ f. and hence
applying Lemma 5 shows that there exists M M such that (PMMEL(MM 2 Ao) 9 Letting An + p-dec? (M) completes the proof.
29

---

F.3 Proof of Proposition 7
In this section, we prove Proposition 7 under the slightly more general setting of Assumption 4. Proposition F.I. Under Assumption for any reference model M E M and > 0, E [0. 1), holds that
2aC₁
p-dec e/ (M, M) p-dec (M, M) + 1--8
For Example 1, we always have C. S v2, and hence Proposition 7 follows immediately from Proposition F.I.
Proof of Proposition F.I. Fix reference model M and Ao p- (M, M). Then, pick pair (p, g) such that
Ao
sup MEM
(M.))) Ex M(T) S ==²
whose existence is guaranteed by the definition p-dec ( M) in (12). In other words, we have
P (L,, & Ao) 21
vM E EM.Ma..MM (q.
Consider 9
Ptu and g' V2" Also let
M arg (TT()))).
McM,,e(MM)
Now, consider p A(II) given by
p(-) p0 ((-IL(M, T) S Ao).
By definition, for ग we have f (T) 2 fall (Txr) - Do. and hence
E E fM (Tx) Exupl (x)]
s fM (TT) ExuD f (T))
+ Ex D (M(()),, (M(T),
S 2 (TT) fM (TT Do + C, Exup ((T). M(x))
Notice that for any M E MM,. (M). have fm (Txx) S fM (T and also
Ex-n Dr ((T))
L(M, S Ao) E D1 (((T), M())
(Beng DE (M()), M(T) + E Du (M) M(T))
$ 1-
1 1-6
Combining these inequalities gives
E² s 2
2=C,
c-dec (M, S sup MEM
EnnpI Di (M))..
Ao +
1-8 5"
Letting Ao + p-dec. (M, completes the proof.
F.4 Proof of Proposition 8
Recall that we frame the DMSO setting an instance of ISDM in Section 2.2, where the observation given by (HT 7), and the loss L(M, X) L(M, 7). In particular, for any prior μ e
A ((M), we have
sup p(M L(M,X) < A) sup p(M : L(M, T) < A),
30

---

and by definition, (M; S (T). In particular, for any pair (A, such that
1
sup (M L(M, T) S A S exp(-2Ip(T)
(34)
4
we have
T M.X)++oog?
and hence applying Proposition 2 gives
lug H(M:L(M,)<Ka SMPMEM BuCa [MM, +)] gives the desired lower bound.
2
Taking supremum over all pairs (A, satisfying (34)
E5 Proof of Theorem E.3
Our proof adopts the analysis strategy originally proposed by Glasgow and Rakhlin [44].
Fix 0 A < r-dec",, (MM and a parameter (0, 1). Then there exists M .M such that r-dec" 5, (M, MM A.
Fix a T-round algorithm ALG with rules "r,... ,T. we consider a modified algorithm ALG': for = 1, ,T, and history ((t-1), we set p/(-117 (((-1H((-1)) = (-(((((1)) if E:= L(M, π²) < TA - 1, and set (117(((())) 1z if otherwise. By our construction, it holds that under ALG', we have DT. L(M, +*) TA almost surely. Furthermore, we can define the stopping time
T T= ==inl] inf
1:
L(M, m² 2 TA or = =T+1
8=1
If r S T, then it holds that Ei=1 L(M, 2 TA 1.
Now, consider p ph..s ( Σx= x² = that Ex LM, T) < A by our construction, and hence there exists M M such that
A(II). Using our definition of r-dec9, we know
P Prop (L(M, σ 2 A) >
Ei (M(T), M())) S E²
By definition of and Lemma C.I, have
past
Σ L(M,'') TA 8,
DR (pMMa spmmuee < T1
(35)
We also know
T
< B.R.
C
T
T
C. Di (M( s CoC
and hence by Markov inequality,
Mo ALd
Σ T
(
CG,e < C
In the following, consider events
E Σ T(M,**) TA
and the random variable X == (+) By definition, pm > 6.
pa.ud (X CTC,) ट.. We have the following claim.
Claim: Under the event n (T T}, we have
Σ L(M, T 2TA-X-L
31

---

To prove the claim, we bound
L(M,
Σ
I( - Σ I(M,
[=1
1=1
t=
TA
Σ
(T - (m(((()
I=T+1
T TA (T - TT) (TT) + Σ (mT) X
1=++
= =TA
r) (f X,
where the first inequality follows from Eg. and the second incquality follows from (*')| S X. On the other hand, we can also bound
Et (T+)
Σ I(M, = ΣV (TTA)) 8
2 (T))) Σ (x²)
(TTa)) - ff' (T)a)
Σ L(M, x²) X
[=1
27. (T)) - fM (T))) TA - 1 X,
where the first incquality follows from (z (T(() - X, and the second inequality is because Ei=1 L(M,x*) 2 TA 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 know
TAT
Σ L(M, 2 T(A T(A- (E) -1 2 PRR. (X 2 C
Notice that D1 (PMMe', PRAAd S 7T and hence for any event E, it holds PM.dd (E) 2
P.M aod (E) V14T22 In particular, have
par.uo LLM T CC,E) -1 -1)
0 C
V
Finally, we note that ALG and ALG' agree on the first A rounds (formally, ALG and ALG' induce the same distribution of (IT) TTAT)), )), and hence
TAT
L(M, 2 T(A CC.E) -1 2 8
1
VI4T.²
C
The proof hence complete by noticing that ΣTAT L(M, TT) < ΣT L(M, = RegpM (T) and taking A + r-dec (M).
E.6 Proof of Proposition E.2
Fix M E M and A > r-dec (M, Choose p E A(Irr) such that
(,,,)) V B m) A
VM E Mp.e (M).
The existence of is guaranteed by the definition (32). In other words, we have Ex mp (M, < A and
P Pa-D (L(, 2 A) < 8,
VM E Mp.((M).
32

---

We then has the following claim.
Claim. For any model M M, it holds that
Ex-pl (L,, m)] Ex- + Dn M(T).
(36)
Fix any M M,, we prove (36) as follows. Consider the event & { (L,, TT - A}. Then,
p(E)(N - 1 (TT)) Px-p1 (8) (L(M, - L(M, + (m) - (
$ p(E)) + C. {8) Du (M), M(T)),
where the inequality uses L(M, π) < A for E and Assumption 4. Therefore,
Se x) Tpp {8) (. =) + Empp (E)) =() $ ( + E (89) (Txx 1 (T()) ('(()) - 1 (x) + I(M,=))
$ 2A + p(E9) Exppl {8} (M((((T)) ( M(T) + C,E (8r) Du PH(M((T) M(T))
P(E)
plE P(E)
2A + max
1
This completes the proof of our claim.
Therefore, using (36) with Ex-p [LM m)] < A yields
( m - 2A + tccCe
AM E Mp.((M).
This immediately implies
-dec (M) .M) s 2A cgC,E,
Finally, taking A - r-dec 8 (M, M) completes the proof.
F.7 Proof of Proposition E.4 Fix a reference model M and let Ao p-dec_ (M, M). Then there exists p, A(II) such that
sup { (M,,)) MEM
Eang (M(T), S s <o.
Therefore, holds that
IP Px (M) Ao) 2-
vM E Mg.
If the constrained set My.s (M) is empty, then we immediately have (M, M) 0, and the proof completed. Therefore, in the following we may assume My.e (M) is non-empty, and M E MM..((M)
Claim. Let θ 0,g and ât = (mo, 0) for arbitrary no. it holds that
L(M, +) S Ao.
VM E MM.)(M).
This is because for any M E Mg.e (.g.((M)) (M), it holds that
P (L, & Ao. L(M, Ao) 2 - 28 > 0. Hence, there exists 8 E such that p(f,,, 8) S Do and p(O 0) s Au holds. Therefore, must hold that p(0xr, 0) < 2A, for any M E MM (M).
The above claim immediately implies that
(M, sup MEM
((M, Exng Di (M(z), <=²} $ 2Ag
Letting Ao + p-deo S (M,M) yields p-deo (M, 2p-dect (M, M), which is the desired result.
33

---

G Additional Discussion and Results from Section 4
G.1 Properties of the fractional covering number
Before proceeding to applications, let us briefly discuss some connections between the fractional covering number and classical notions of covering number considered in the context of statistical estimation.
To start, we recall that for many standard statistical estimation tasks such as regression and non- parametric estimation, the risk function L is given by (pseudo) metric (e.g.. l2 distance between parameters or mean-squared error in predictions). The following lemma shows that in this case, the fractional covering number coincides with the classical covering number induced by the metric, e.g., in location estimation (Example 4), density estimation (Example 6), etc.
Lemma G.1 (Connection to classical covering numbers). Suppose the decision space II is equipped with a pseudo-metric p IT x II + RR and there is a map M + TM E IT such that the risk function
given by
vM E M, ETT. Let 1IM == = : M E M} C II, and define N(IIM: A) to be the A-covering number of IIM
I(M, πT p( T):
(37)
under p. Then
N(IIM 24)= S Nfrac (M, N(IIM.)).
Duality between fractional covering and fractional packing For classical covering numbers with respect to pseudo-metric (as in Lemma G.I), it is known that there is duality between covering and packing. In spite of a lack of metric structure for the general setting we study, we can show that fractional covering number naturally admits dual representation in terms of fractional packing number. Specifically, it holds that
PEA(T) MEM MEMP(T inf sup ((M L(M, T) م = sup inf p( L(M, T) S A), PEА(M) rell
as long as the minimax theorem can be applied (e.g. when II or M are finite satisfy appropriate compactness conditions). Therefore, in this case, we have
Nirac (M,, sup inf (EA(M) TEll μ(M: L(M, T TT A)
(38)
which can be interpreted as a fractional packing number. We mention in passing that using this interpretation, is possible derive Theorem 10 directly from Proposition 8.
Recovering the Yang-Barron method. As a simple example of the fractional covering number, we recover and further generalize the well-known Yang-Barrof method [95] for statistical estimation problems (see also [89, Section 15.3.5]).
(Yang-Barron Barron method). For statistical estimation problem with model class M, define the KL. covering number of M as
Example 12 (Yang-
NKL (ML, c) == min k: EM-
M .K. E E, such that VM E M, min DKL M*) s e2 iE[k]
For fixed parameter minje DKL(M I| M') I 2² for all M E M. Then, let us consider the localized sub-class M; := {M E M: DRI, (M M') < E for each i E [k:] It clear that Assumption 2 holds for each M; with OKL 8². Further, using M U M, have
O,
pick i (KL(M,E) and M M M such that
log Ntrac (M, A) < max log Nirac A) + log k.
(39)
sE[k
For details, see Appendix H.4. Therefore, applying Theorem 10 to M; and take supremum over i E [k] and E > 0 gives the following result: For any algorithm ALG to achieve supgce 1 LLM, x) S A, it is necessary that
log Nfrac (M, A) < inf (2T'² + log NKL(ME +
e>0
When the risk function L is given by metric (cf. Eq. (37)), this inequality coincides with the Fang-Barron method formulated in Wainwright [89, Section 15.3.5], as the fractional covering num- ber Niaac (M, A) be lower bounded by the covering number (Lemma G.
34

---

Recovering the local packing lower bound for statistical estimation. As simple example of the fractional covering number, we recover the well-known local packing- based lower bound [15] for the classical problem of location estimation [89].
Example 13 (Local packing lower bound for location estimation). In the location estimation task (Example 4), recall that the model class is given by M {Ma 0 E )), where Mo ((, Ia)- Consider the local packing number of @ around 6 E θ, which is given by
( (96) == max { l 30" 8 E |10 0 = A.
00 - 8i11
2 Vi x
Then, for the localized sub-class Me..- == {Mo : |10 - 0- S E} C M, Assumption 2 holds
with CKL S _=² and we also have Nta (M, sM 2 Nooc O o, 0; Therefore, we can apply
Theorem 10 to Me.e. and take supremum over all 6* 2 and E 2 8A to show the following result:
| For any algorithm ALG to achieve supsee B A|| I A. it is necessary that
log ( (0,E) -
T M sup
$28A
g2
( where (e, = supp. ee Nioe (9, e; 8*) is the local packing number of O. This lower bound is known to be tight in general [14, 15, 59, etc.].
G.2 Additional discussion from Section 4.2
In the literature statistical learning, there is long line of work which characterizes learnabil- ity of hypothesis classes in terms of abstract complexity measures. Examples include the Vapnik- Chervonenkis dimension for binary classification [83, 16], the Littlestone dimension [63] for online classification [10] and differentially private classification [20. 6], and their realevalued counterparts (e.g. scale-sensitive dimensions) for regression [9, 5].
Beyond the settings above- particulalyyll for interactive Kettings-learnabblne is less well under- stood. The question of what complexity measure characterizes bandit learnability has been explored in Russo and Van Roy [74], Abernethy et al. [1]. Simchowitz et al. [79], Hashimoto et al. [46, etc.), but a complete resolution has yet be reached. Remarkably, Ben-David et al. [11] demonstrate that there exists a simple and natural learning task for which it is impossible to characterize learnabil- ity through any combinatorial dimension. More recently, Hanneke and Yang [45] provide similar impossibility results for characterizing the learnability of noiseless structured noiseless bandits with real-valued rewards.
Our characterization bypasses the impossibility results of Hanneke and Yang [45]. Specifically, Hanneke and Yang [45] 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 characterization of noiseless bandit learnability through any combinatorial dimension ]] for the problem class. Our characterization is compatible with this result because the argument of Hanneke and Yang [45] relies the noiseless nature of the bandit problem, and hence does not preclude a characterization for the noisy setting.
Connection to the maximin volume. Hanneke and Yang [45] propose maximin volume, a complex- ity measure that tightly characterizes the complexity of learning noiseless binary-valued structured bandit problems. For such problem classes, the fractional covering number is exactly the inverse of the maximin volume. While the fractional covering number can be viewed as a generalization of the maximin volume in this sense, we emphasize that the fractional covering number 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 (20) applics to any reward distribution with sub- Gaussian noise (cf. Appendix H.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 well. We expect the lower bound extend to other "reasonable" noise distributions.
G.3 wwwrratiinn-h-Oppiiiiitiiit Algorithm
In this section, we present slightly modified version of the Exploration-by-Optiizzze Algorithm (Ex0+) developed by Foster et al. [41], built upon Lattimore and Szepesvári [58], Lattimore and
35

---

Algorithm Exploration-by-Oppiiizzati (ExO*)
Input: Problem (M, I1), prior q E A(II,, parameter T 2 1, 7222000 0.
I: Set q² = 9.
2: for = 1........ , do
3: Solve the exploration-byyooiiiiaaaainn objective
(p',6)
arg min (p, рEA(M)εE
4: Sample n²' ~y, execute n² and observe of
5: Update
(T) &x exp(e (m;n',
Gyorgy [55]. The original ExO+ algorithm has an adversarial regret guarantee for any model class M, scaling with r-dec,, (c)) the offset DEC of the mode class co(M), and log [II], the log- cardinality of the decision space. For our purpose, we adapt the original ExO* algorithm by using prior q (III) not necessarily the uniform prior, and with suitably chosen prior q, ExO then achieves a regret guarantee scaling with log Nfreo (M, A), instead of log [II] (cf. Foster et al. [41]), which is always upper bound of log (MM, A).
Offset DEC for regret. We first recall the following (original) definition of DEC [40]:
r-dec (M,,
inf sup LE, [ER=p[[(M, x)] DBa-pD (M) (T)) (()).
(40)
PEΔ(T) MEM
and r-dec", == SuP (-dec (M, M). Through the Estimation-to-Decissooo (E2D)
algorithm [40], offset regret-DEC provides an upper bound of RegDM for any learning problem, and it is also closely related to the complexity of adversarial decision making.
As discussed in Foster et al. [42], in the reward maximization setting (Example 1), the constrained regret-DEC r-dec always be upper bounded in terms of the offset DEC r-dec". Conversely, in the same setting, we also show that the offset DEC can also be upper bounded in terms of the constrained DEC (Theorem H.5), and hence the two concepts can be regarded equivalent under mild assumptions (e.g. moderate decaying, Assumption 3).
algorithm. The algorithm, ExO+, is restated in Algorithm 1. At each round t, the algorithm maintains a reference distribution q' E AII), and use it obtain decision distribution p' E A(II) and estimation function L L x + R), by solving joint minimax optimization problem based on the exploration-by--ptiiizaaoon objective: Defining
cisploration-b-Optiinte
Tan (p, (,,)) I (T))
(41)
BET (ar) Bringl exp (E(T'; ;(m===,,)))
and
Ta (p,(
sup P (p, M, m)), MEM
(42)
the algorithm solve (p',e) 4- arg min)e 19t, (p, E). The algorithm then samples n¹ ~ p¹, executes n' and observes of from the environment. Finally, the algorithm updates the reference distribution by performing the exponential weight update with weight function ('(==t,,')
Guarantee of ExOt. Following Foster et al. [41]. we define
exo (M.,) =
inf I (p.
(43)
PEAIT))EEL
and exo (MM) SU) (MM, The following theorem is deduced from Foster et al. [41, Theorem 3.1 and 3.2].
36

---

Theorem G.2. Under the reward maximization selting" (Assumption 4), it holds that
& ex01/,(M) S [r-dec,ssco((M))
<> 0.
Now, we present the main guarantee of Algorithm 1, which has the desired dependence on the prior q E (IT).
Theorem G.3. It holds that with probability at least
RegOM S <T(A r-dec (co()()))(c()))))) + log
8. g(T f"r (Tx) for (T) S A)
Proof. Consider the set II* : { f (T prr (T) S A} and the distribution q" = ((-(11)).
Following Proposition G.4, we consider
X₃(x', o') Enrgr [T: log loggErry Ex (exp (T;
and Proposition G.4 implies that
T
Σ
Xi(=' < log(1/q((1)))
t=1
Applying Lemma C.3, we have with probability at least
log E,- [exp (-X,(x', ,'))] S Σ X ,') log(1/8).
Notice that
E |exp ( (-X,(T', o'))] Emap Bonnp rugh lexp (f Eq ( o))]
Using the fact that
log and Jensen's 's inequality, we have
Σ
E Nu E 44:4 M m²) s log(1/a(1I*)) + 1og(1/0),
1=1
where we denote
Err(p, Eg M*) Mo exp (?(=''==,o) - ((===( :T, o))].
Therefore, holds that
RegoM
Emaupt (fM)(TT))) par (T))
T
<
+ E E rug Egg
Extinpt [f*²((**) - fM (x²)]
T
TA +
E Enr(p', ,', M,, x²))
E rug"
E Eyiing pMl (TT') far (n*)) Err(p' S.:pp.... L. M .m*)
=I Co (8:MM-
< TA + 7ll00//ll(01//// log(1/0)) + Σ (p',
1=1
T(A + (M) + (log(1// (II")) log(1/6))
Applying Theorem G.2 completes the proof.
WWe remark that their proof applies long fM can be linearly extended to co(M)
37

---

Proposition G.4. For any of ATT), it holds that
Σ t=1
En 14 (T: d']] log Ex Er (exp (T; ,o))] s Dru(d' ll q).
Proof. This is essentially the standard guarantee of exponential weight updates. For simplicity, assume 1l is discrete. Then, by definition,
((TT) exp ( ,,; (T; 0*))
(T))= =
( exp (2xm (* (T()
and hence
log Ex (exp (1;,, log B Bx exp
Σ (T: (T)
es (T:; ( 0z)
log Exng exp
Therefore, taking summation over t = 1,.., ,T, we have
T
e' ( nh, el o5) )
Σ log Exng' (exp (T;;"', = - log Bronn
Σ
exp
The proof is then completed by the following basic fact of KL divergence: for any function h : IT -
RR,
Ex [h(TT] S log Ennu exp(((TT) + DRI(d || g).
G.4 Application: Structured bandits
We now instantiate general results to give tighter guarantees for structured bandits, improving the upper bounds 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 Mr denotes the induced model class. In what follows, we simplify the results in Theorem 15 to be stated purely in terms of H. For reference value function C x + [0, 1], we define
r-dec (H, := inf sup { [E<=p[((TA)) h(T)] (Er~((((T)) h(T))) ((T))) < {
PEA(T) NEH
where we recall that Ta == max h(T)). We then define the DEC for 7 as
r-dec = sup r-dec (H U h).
kEco(H)
As corollary of Theorem G.3, the r-dec (H) and log Nfrac (H, A) together provide an upper bound for structured bandits with H.
Theorem G.5. Let H. be given. Suppose that II is finite, and that = ++ (co((H) satisfies mod- erate decay function of e (Assumption 3) with constant Greg: Let E(T) x Vlog Nira (H, A) The Algorithm ensures that high probability,
RegOM T A + O'CregT VooggTT/oog T) r-dec (C)()))-
As a corollary, the minimax sample complexity of structured bandit learning with H. bounded as max 0E0 lo, Nura (H, 22)} $ T (MH, A) S DEC (co A) log Nivac (H, 2/2),
(44)
where we denote TOEC (H, A) = inf e) redec (H) S A} (following Eq. (15)) and omit logarithmic factors and dependence on the constant Creg.
38

---

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 [72], or concavity [54], sub-modularity [65]. or etc.). For these problem classes, the complexity of no-regret learning is completely characterized by the DEC of H. and the fractional covering number Nivae (H, A) (up quadratic factor).
We also note that the lower bound of Eq. (44) is proven for Gaussian noise, while our upper bound applies much more general class of reward distributions (with bounded variance).
G.5 Application: Contextual bandits with general function approximation
Next, we instantiate our general results for stochastic contextual bandits with general function ap- proximation, generalizing the structured bandit problem. We consider the stochastic contextual ban- dit problem with context space C, action space A, and a reward function class H. C (C A + [0, 1))- This problem special case of the DMSO setting with decision space II (C + A). and the en- vironment is specified by tuple (h, E H, the environment draws
AC)).. The protocol is as follows: For each round v, and the learner takes action a² 7 (e²) based on the decision n² C + A, and receives reward p² ~ (N, ,
We can formulate the model class as follows. For a reward function H and context distribution E ACC), the corresponding model MA, is specified as
(c, a, (T) c~vva = v(a), Nhh(c, a),
Let My = {Mr,, h E H. E A(C) be the induced model class of contextual bandits. Following Appendix G.4, we instantiate Theorem 15 provide characterization of learning Mr.
DEC for contextual bandits. For any context E C, the value function class induces a restricted value function class H/ (h(c,-) h E H}. which corresponds to a (non-contextual) bandit function class. We define the following variant of the DEC
r-dec (H) := sup (
cEC
which corresponds to the maximum of the per-context DEC over contexts. We also define TOEC (H, A) inf=e(o.1){ r-dec S A), following Eq. (15).
Fractional covering number for contextual bandits. Specializing the fractional covering num- ber contextual bandits, we define
Niva (H,
inf sup PEA(TT) (EH. P(π : (Mlc, (c(c)) h(c, (c)) < AA)
(45)
where TH E II is defined via (c) arg max hi(c, a) for CEC.
Intuitively, the value of the fractional covering number log Nira A) for contextual bandits cap- tures 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.e.. H (C x A [0, 1))), it holds that log NfrreeH, A) [C] AA,, but in general we can have log Nuse (H,, A) < log [II| = log [.A]
As corollary of Theorem 15, we derive the following upper and lower bounds the complexity of contextual bandit learning with H.
Theorem G.6. Let H be given. Suppose that both the context space C and the action space A are finite, and that E +> =dec((co(H)) satisfies moderate decay as function of (Assumption 3) with constant Greg. Let E(T) x /log Nirac A//T. Then Algorithm I ensures that with high probability,
RegDM I T A (Crrog Mog T) r-dec (c0
As corollary, the complexity of learning Ma is bounded by
max ( TTE AH, log Nfrac (H, 22)
(T*, $ TEC (CE A) .log Nirac A/2).
log
(46)
omitting dependence Creg and logarithmic factors
39

---

By definition, have r-dec, (co(H)) r-dec (H) if the per-context value function class H|c is convex for every context E C. Natural settings in which H/c is convex include contextual linear bandits [28], contextual non non-parametric bandits [22], contextual concave bandits [54], etc. For these problem classes, the complexity of no-regret learning is completely characterized by the DEC of H and the newly proposed Nfr H., A) (up to quadratic factor and factor of log (C]).
As a concrete example. we can derive upper bounds based on the fractional covering number for finite-action contextual bandits follows.
Corollary G.7. For any value function class H. Algorithm I ensures the following regret bound with high probability.
RegDM (T) ( A (VTIA) log Ntrac (H, A)).
Compared to the well-known regret bound of
log [H] for learning any with any fi- nite contextual bandit class H [38, 77], this result above always provides tighter upper bound, as log Nirac (H, A) < log [H| For certain (very simple) function classes H. the quantity log Nirac (H, A) can be much smaller than log HH] (for details, see Example 14). More importantl, log Nirac A) leads to lower bounds for any contextual bandit function class (Theorem G.6). By contrast, lower bounds for structured contextual bandits in prior work have been proven in a case- by-case fashion (for specific value function classes H).
H Proofs from Section 4 and Appendix G
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 (M A). The results be generalized immediately PAC learning.
H.1 Proof of Theorem 10
Fix an arbitrary reference model M E (II A(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.
log Ne (M.A)-2 then for any T-round algorithm ALG, there exists model M M 20KL.
Fact. If T
such that RiskpM (T) 2 A with probability at least 1 under P.M.AGGG
2
Proof. By the definition (17) of (ttac A), we know
= sup inf p( L(M,T) S A). PEA(M) MEM
Nirac (MM,
Therefore, we have
inf PM ALO(: T(M, T) AD) 5 Nirac (MM A) MEM
and hence there exists M E .M such that
log (1/PM L(M, R) S A)) - T
2CkI.
Notice that by the chain rule of KL divergence, we have
DKL (PAAG M.M.. M.ALG
Σ
DKL((T (((7) < TCKL.
1=1
Hence, using data- aata-processing inequality,
log (1/PM : L(M, S <A)) -
DRL(PMALG AG)) <
2
Dkt. / || PM L(M, T) < A)).
This immediately implies pM. : I(M,T) & A) < by the monotonicity of KI. divergence.
40

---

H.2 Proof of Theorem 11
In this section, we present algorithm based on reduction to multi-arn bandits (Algorithm 2) that achieves the desired upper bound. For the application to bandits with Gaussian rewards, we relax the assumption R O - [0, 1] as follows.
Assumption 5. For any M M and IT, the random variable R(o) is I-sub-Gaussian under (T).
Suppose that A > 0 is given, and fix distribution PA that attains the infimum of (17). Based on PA. we consider a reduced decision space Ilsub C I1, generated as
Tlub (1) x (M)), T(), , x( p independently,
where we set N (MM, log(1/5) Then the space aub is guaranteed to contain a near- optimal decision, follows.
Lemma H.1. With probability at least there exists π E sub such that L(M*, m) S A.
Therefore, we can then regard _M* as N-arm bandit instance with action space A = Hlub and for each pull of an arm E AA the stochastic reward generated as r R(o), o (T).
Then, we pick standard bandit algorithm BanditALG, e.g. the UCB algorithm (sec c.g. Lattimore and Szepesvári [57], and apply the multi-are arm bandit instance Bandit and the guarantee of BanditALG G yields
T
Σ max fdh (I') - (xt) 0 OOTNNOoO(T// log(T/)))))
Ellib t=1
with probability at least 8. Therefore, we have
RegoM (T) - T (f" (Tu-) max PM (T')) + + TN log(T/8) x'Ellon
TT AT-A+ + V TN log(T/))
with probability least 25. This gives the desired upper bound, and we summarize the full algorithm in Algorithm 2.
Proof of Lemma H.1. By definition,
P(ViE [N), LIM', > A) S S ((M",))>>
>
(T) A)
N
Nira (M, A)
N
exp
Nirac (M, A) 56.
H.3 Proof of Lemma G.1
Proof of the upper bound. Take minimal A-covering of II,, i.e., a set ( , C such that for all M E M, there exists i E [n)] such that p(TTr x²) A. Therefore, we may consider the distribution p = Unif(( .... 7))), which guarantee
Ntrac (M, A)
sup
< N(IL,,
MEM p(T (( AA
Proof of the lower bound. Consider the maximal 2A 2A-packing of II,, i.e., let { ........ ,, C 1I be a maximal set such that p( ((T';T)) > 2A for any i + j. Then, by the duality between packing and covering, the set ( ..r.... , .²" form 2A-covering of IIM, and hence have > N(IM,, 2A). On the other hand, the sets IIo == { p(T, T²) < A} are pairwise disjoint, and hence for any p E A(II), we have
m inf MEM p( P(TTM -A) $
Σ p( p( x)) <A)= 1
t=1
Therefore, it holds that Nirac Mita (M, N(II,, 21).
41

---

Algorithm A reduction algorithm based on the fractional covering number
Input: Problem (M, II), parameter A, 0, T 2 1, Algorithm BanditAL G for multi-arm bandits.
1: Set
PÀ = arg inf PEA(T)) MEM
sup
(47)
p(T L(M, TT A)
2: Set N = Ntrac A) lo/(1/6) and sample the decision subspace Ilsub ( ,
C
IT as
11)
(N) PA independently.
3: Run the bandit algorithm BanditALG on the instance Mandit for T rounds.
H.4 Proof of Example 12
remains to prove Eq. (39). More generally, we prove the following lemma. Lemma H.2. For model class M = Uh Mr it holds that
Nerac Netac(M, S
Ntrac (Mis A).
Proof of Lemma H.2 For each E [n], we define A
(Mne(M,, Σラ= Ntrac (My.aj*
Fix pi,... ,rn E (IT). Then, let us consider the distribution p = E Aipl E A(T). For any model M M, there exists Mi, and hence p(= I[M, A) z X minM,.. pi( L(M,, x) < A). Therefore, it holds that
inf p(T T) I A) 2 min d inf iE(m) MEM,
pı(T: : L(M, T) S).
MEM
In other words,
1
sup MEM p( L(M, TT) S A)
max
sup
iE|n] d MEM; Pi(T: L(M, T)) S A)
Taking infimum over Pr E AII) gives
N frac (M,A)=
inf sup PEA(I)) MEM p( L(M, T. 3)) A)
max sup
TE(n) d MEM; pi(m: : L(M, S A)
1 sup
inf
P1." Pr. (I) (E(n d MEM. Pi(T L(M SA)
1 inf sup vE(n) X (EE(IT) MEM. Pi(m: : L(M, m) S A)
1
max
Nirac (Mi,A)) Ntroc A),
max ve(m) X;
1=1
where the last line follows from the definition ...... An This the desired result.
H.S Proof of Theorem
We first state the following more general result, and Theorem 14 is then a direct corollary (under Assumption 3). Analoguous guarantees also hold for PAC learning.
Theorem H.3. Let T 2 1 E (0, 1). With suitably chosen prior E A(II,, ExO+ (Algorithm 1) achieves with probability at least - 8:
RegoM $ 5A+ A r-dec / (co(M)) + log Mitac(M, A) log(1/))
(48)
T
42

---

In particudar, when M is reward-maximization problem class (Example 1), ExO+ achieves (with a suitable parameter ()) that with probability at least 6:
RegoM SA+ Colog(T) (ry (co(M)).
(49)
where C is an absolute constant, E(T)
log Naver (M, (M. (Mo))H and the modifted version of
constrained regret-DEC is defined
r-dec (co(M))
(coee == g sup e'Ele,1]
(50)
el
Remark H.4 (Upper bound without regularity condition). In Theorem 14 (and Eq. (49)), sume that (1) M is a satisfies certain regularity condition (Assumption 3). We can relax these two assumptions and obtain a weaker upper bound. Specifically, we may only assume that f II + [o. 1J is affine with respect to M E co(M) (cf. Theorem G.2). In this case, we can still bound the regret of ExO* as
problem, and (2) the constrained regret-DEC of co(M)
Va/3 V> (c)(M)) +Y log Nirac (M, A) + log 1og(1/6)
T RegDM & A + r-dect
(51)
T
which follows from Eq. (48) and the fact that (by definition)
(coc s r-dec (co(M)),
by > 0.
In partieular, using Eq. (51) above, we can show that (omitting holy-togarithmic factors)
T (M, A (CE()) A/3) log ( (M, A/2).
This is worse than the upper bound of Theorem 15 by (roughly) a factor of A A-1 Proof of Theorem H.3. By the definition (17) of Nirac (M, A), we know
sup inf p( L(M, S A). PεΔ(1) MEM
Mrac,M,
Therefore, there exists y A(II) such that
inf g(T L(M, (A) Nirao (M, A)
MEM
We then instantiate Algorithm with such prior g, and Eq. (48) follows immediately from The- orem G.3. To prove Eq. (49), we invoke the following structural result that relates offset DEC to constrained DEC.
Theorem H.S. Suppose that Assumption 4 holds for the model class M. Then for any E (0, 1), holds that
inf (r-dec, + 7E²) < (3 [log + (2)dd))))
(r-dec
+c,).
>>0
Under the assumption that + r-dec (-o (c)) is of moderate decay with a constant Crego we have
(coec((co(M)) r-ec
Ve (0, 1].
Hence, Eq. (49) follows from (48) as long as the parameter yy is chosen according to Eq. (H.5).
H.S.1 Proof of Theorem H.5
Fix a E (0, 1] and M E co(M). We only need to prove the following result:
Claim. Suppose that r-dect (M, M) < De' for all e' [e, 1]. Then there exists 7 ((D,e) such that
I- + 70? < (og2 + +2) (D Cr)e.
43

---

Set K 1ogg (1/6] and fix a parameter c() (0, 2 be specified later in proof. Define
et 2 2 for 0,... K and ēK =e We also define X cs. 2 for i 0, K and
AK 1 Σx= X; c.
Define A; r-dec (M {M M), and let ps attains the infy. In the following, we choose
=D) = -()+Cr)
By definition of p., it holds that
E Ex (M, Ass
AM E EMMM Exop, DH (M(T), S S
In particular, we may abbreviate M, = {M E EM: Eaope DH (M(T), M M(x) - 8 and it holds
(M S (T<)) A + Crec
EMEM:
Next, we choose
E Xop ATT), and we know
Ba>p!L(M,,) S Σ ((M,TI & Σ NA =:A.
Fix M E M. Let j {0...., ,K} be the maximum index such that M E Mj. Such a must
exists because M MM Now,
Br-p!L(M,rr πT) =-= ("
(m En LLM, m)] Bm= (m))
s A + Cjy + + C-Ea~p (T)). (x)).
Case 1: = K. Then, using AM-GM inequality, we have
((M, m] BB Di (M(T), S A +ēk + A + L
4
Case 2: j K. Then for each i j, holds that Eawp, D (M (T). M (=))
5j. and hence
Ep Da ((()),((T)) >
Σ
AyErap (M(T), M(x))
Σ
Xze N
C8 .gj
1=+1
Therefore, using AM-GM inequality.
E Trmp|L(M,,a) x
B.u Di (M M())
90
A + G.ey + A
E D (M
47
9
9C
Soye
A + G.ey +
9 Eg.
47
By our choice of y, we have y 2
g
A
+
C,
and hence in both cases, we have
Nc.
Expp (MM, T]] yD D (M(T), M())) < (D C,)++ 9C2
4
Note that by definition, we have A < (cK + 1)De and (5) E = 9 8c
DD + C.), and hence
r-dec (M, M) < (2D + C. cKD + 2cC,)e.
Thus,
9(D - Cr)
r-dec" (M, 7 < 2D + CD cc
EK.
8c
Balancing and re-arranging yields the desired result.
44

---

H.6 Proof of Theorem 15
Note that the minimax-optimal sample complexity T (M, A) is just a way better illustrate minimax regret upper and lower bounds. By the definition of T (M,, A), we have
Reg' (M, sup(A: 7M ( S T)
Under Assumption 3, the regret upper bound in Theorem 14 implies (up to Creg; CKI. and logarithmic factors)
T Reg" (M,T) S (r)
And the regret lower bound Theorem E.1 implies (up to Grog and logarithmic factors)
r-dec (T) (M) x T Reg (M,T).
By the definition of T (M, A) and T (M, A), then have
(OEE(M, S (M,, & 7
log Nirac (M,
Together with Theorem 10, we prove that
max THE (M.
log (M. A)
(T. (cOM)M A) log (MM
CKL
H.7 Proof Theorem G.5
For the upper bound, we work with more general noise structure (beyond Gaussian noises). We define Mu.V to be the class of all bandits models with mean reward function in H. and variance bounded by 1. Specifically, for any M E Ma,y, y, it is associated with value function h" M H, such that for any decision π E II. the distribution ((r) of the random reward has mean h M (T) and variance at most 1.
We also recall that the subclass Mr S MH is the bandit problem class with the standard Gaussian noise.
Proof of Theorem G.5: lower bound of (44). The lower bound with log Ntrac (H, A) is exactly Corollary 12.
To prove the lower bound with TOEC (H,,)) A), we need lower bound the DEC of Mr in terms of the DEC of H, follows.
Lemma H.6. Consider M+ Mco(H),v the class of all reference models (Appendix E). Then,
max
(-d U (M), M) 2 r-dec (H)..
(52)
MEMt
Notice that for M Assumption 4 holds with C, v10 (by Lemma C.5). Therefore, corollary of Theorem E.3: for any T-round algorithm ALG, there exists M E MMx such that
T' 2
RegoM (T) (r-dec ((T) (H) - 5g( -
(53)
with probability least 0.01 under part, where g(T) terms of DEC (H, A) follows immediately (using regularity condition Assumption 3).
1
Therefore, the lower bound in
50VT
Combining both lower bounds completes the proof.
45

---

Proof of Theorem G.5: upper bound. (in Appendix H.2).
We apply Theorem H.3 similar to the proof of Theorem 15
Using Theorem H.3, we know that ExO+ can be suitably instantiated on the model class MH, so that with probability at least 1 -8, 8,
RegOM S + C (T)
T
where is an absolute constant, ((T)
log No (H, (log((())) We only need to upper bound
T
the r-dec_ (co(MH,v)) (defined in (50)) in terms of the DEC of co(H).
Lemma H.7. For any 0, it holds that
I-dec S r-dec V10e (H)
We also note that co(MH,v) S M because the model class Mco(H), is convex and contains MHyv. Therefore, we know
(co & r-dect (Meo(H).v) I r-dec VIo (H)).
Using the regularity of z I-oec we know
(co < Greg r-dec VTo vToe (co(H)
This gives the desired upper bound.
H.7.1 Proof of Lemma H.6
Fix E [0, 1], we denote E = 2/2c and take any A < r-dec, (H). We pick h E co(H) such that r-dect, (H, A. Then, it holds that
inf PEA(I)) kE)
sup
(Er=p(M(TT) M())]l (emp(M(a) M()))² S sei) 2 A.
Suppose that h E co(H) is given by h = En~nlh] with A(H). Then, consider the reference model M M with mean reward function h and Gaussian noise, ie. M(T) A (N(h(T),,) Then, we know that for M Mr.
(MU (MLMMMMM)AA) M) inf sup PEA(TT) McMU(M)
{ (EaspL((M,n) r)] Di (M(T), M(+)) s
inf sup PEA(IT) he HU())
{ (Bmppl((TT) - |((T]] Ex-p Di (W(h(=), 1), (),,((((T).11) S )²
inf sup PEA(II) (E))(A)
{ (Emoplh(TT) - h((T]] (x(p(((TT) h(())² s < A4
where the last line follows from Lemma C.5. Taking A + r-dect (H) completes the proof of (52).
H.7.2 Proof of Lemma H.7
Fix reference model M co(Mu,y). By definition, we know the mean reward function hat of M belongs coH), i.e. M E MMooHHj... Therefore, for any model M MM and decision E TT, by Lemma C.5,
Di (M()) 2 h²'(T) h2 (2)
Therefore, for M MH.v
(M U (M) M)
inf sup { (Eapp [(M, x)] En (MTT),((T)) s Ee² PEA(I)) M)
46

---

inf sup EEA(T) MEMU(M)
(BT~plT(M,RT) Ex-p/hi 1 (x) 1h" (x) - 10s2)
inf sup (Ex=plh(TT) - h(+=]]] Bn- T((=))² s 88=²)
PEA(T) hE)U(
r-dec Viee (HU (h),
where the second equality follows from the fact that when = h, we have ((, = h(TA)) ) ((T)))
Taking supremum over M completes the proof.
H.8 Proof of Theorem G.6
Similar to Appendix H.7, we consider a larger model class Mx, of models with general noise structure. model M E Mx.Y is specified by a context distribution VM ACC,, reward function hM E H. and a reward distribution RM (-I:-) ) such that for any C, E A, r ~ R (-le, a) has mean hM (c, a) and variance most 1, The model M is then given by
(c, a, r) ( e~2 T(C), R RM (.c,.))
The model class MH, is defined to be the set of all possible models described above.
Proof Theorem G.6: lower bound. The lower bound with log Nirae H. A) follows immedi- ately by applying Theorem 10 to the class MH. which admits CKL. = O (log (C)) in Assumption (as shown Example 9).
On the other hand, the lower bound with (H, A) follows from the reduction to the per-context bandits problem. Specifically, for fixed context E C. Hlc corresponds structure bandits class MHI. Notice that we can naturally regard MH c .Mx by viewing Mzj. as contextual bandits class with the fixed context c. Therefore, by Theorem G.5 (specifically (53)):
Reg" (MH, T) 2 Reg" (Mz). T) r-dec (M(c) - (g(T), T
E(T) 50/T
T
Taking maximum over e E yields
1
+
(Regg(Mx T) Z r-dec ( 6g(T).
This gives the desired lower bound with ( Combining both lower bounds completes the proof.
(H, A).
Proof of Theorem G.6: upper bound. We follow the proof strategy of Appendix H.7. By Theo-
rem H.3, ExO+ can be suitably instantiated on the problem class MH. that with probability at least 1 - 8:
(=deci + log Nuse (M, A) + log(1/6)
RegDM I A C' inf 950
T
T
We also note that co(MHH S Meo(p)).v Therefore, it remains to upper bound the offset DEC of Mco
Lemma H.8. For > 0, it holds that
(. S r-dec (M
dEC
Then, apply the result of Theorem H.5. From the proof of Theorem H.5, it not hard to that: for any E > 0, there exists 7 7()) such that for any E C,
r-dec (MM + 7 S Vlog(2/s) (Creg (co(H)) + +): where we also use the regularity condition of & +> r-dec", (co()))) This immediately gives
RegOM S TA O(Cre Tog (co
where E(T)
Ing Ng (H.A) A) +0)++logg0 log(1/8)
This is the desired upper bound.
47

---

H.8.1
Proof of Lemma H.8
Fix reference model . E co(Mx,v), and then M E Meo by definition. particular, M has mean value function hMd E H and context distribution i E A(C). We also know that for each E C, (x, E co(Hlc)-
Then, by Lemma C.4, we also have
2D (MT), (()) 2 Rews).a=x()) Di (R = Ic, a), (r (c)
Thus, we adopt the following notations: For each c E C and model M E MH,,, we define Md E MRI..V to be a bandit model such that for every action a E A, Mc(a) RM(r a), Then by definition, it holds that
2 (M)T), 2 Be-rsr DH (Mo,()), (Mala),Ma(a)).
Now, combining the inequalities above, we have
i-dec", M)
inf sup B - - BBap Di (MTT),M(T)
PEΔ(I) MEMN.Y
Excu E Boop h"" (c, nM (c)) h2d (c, 7 DD (Mc(a),
inf sup
PEA(I) MEMR.V
2
(1)
inf sup p (=(A)) MEMN.V
E Bewes
11 (c, - 11 (c, a)
1 D (Ma(a), (Ma(a).M.(a)))
(2)
inf sup (=(A))PEEA( MEMu.v CEC
sup Banpe had (C. (c. - h2d (c, a)
? Di (Mo(a). Mc(a))
2
Banpo (TT - h 11 ? D (Mc(a), Mc(a))
inf sup sup p= (PA)) cEC M.EM
Eanpe 1 - (a) - - - (Mr(a), M.(a))
sup inf sup M.EMMIONN
cEC PeEA(A)
sup r- (M) Mc) S supr-dec (2 sup (MHH..)))
<EC
EEC
where the equality (1) is because for sequence (p. A(A))cECc there corresponding p E A(TI) such that for ~ p, we have (c) ~ Pe independently; in inequality (2) we bound the expectation over c ~ Par by the supremum supaeci the equality (3) follows from the fact that Me MH
hM (c, -); and the equality (4) is because can choose Pe separately for every c C. By the arbitrariness of M E co(M), we now have
bandit model with mean reward function h
r-dec (Muv) S sup dec, (2(M), cEC
H.9 Proof of Corollary G.7
We follow the notations of Appendix H.8. By Lemma H.8, we have
(- S sup /2
aEC
Notice that for each E C, MaI..v is a class of [Al-arm bandits, and hence by Foster et al. [40, Proposition 5.1] and Lemma C.5, we have
8|A|
r-dec, (MHL.V) <
Therefore, Theorem H.3 implies that ExO+ achieves with probability at least 8:
T RegoM 5 + 16] + log Nirac (H, A) + log(1/6)
T
Balancing 7 > 0 gives the desired upper bound.
As remark, provide example of function class H. with log Nare (H, A) < log [H].
48

---

Example 14. Suppose that A {0, 1}, and the function class H fle where
1, c= H; 0, c c# x.
h2 0) 2' helc,, =
Clearly, we have log [H] = log [C].
On the other hand, we consider distribution p over policies, such that π generated as (c)) ~ (er, independently over all c ~ C. Then, for any h = h₂ E H and E ACC), we have
Be (M(c, mn(c)) - hec, (c))] = v(x) 1 (π(() = 1} + 2
1 E |1 fo x, ((c) = 1}}.
Notice that π(x) = with probability A, and conditional on the event { (x) = 1}.
Ea-p|Eeswl [1 fo x, (()) [-] = 1] A.
Hence,
A
p( : EEewwhh(e [T(c)) - Mc. [())) = A) N
2
which implies log Nuscc (H, A) - (2)(2/A).
Therefore, for unbounded context space C, we have log Nurto Ntta (H class H defined above.
< log [|] for the function
49

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not re- move the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- ation. While "[Yes] " generally preferable to "[No] is perfectly acceptable answer "[No] provided a proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way. we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
used"). In
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes].
Justification: The main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope. The claims are validated by detailed proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the con- tributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
50

---

Answer: [Yes].
Justification:
The paper discusses the limitations of the work performed.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to vi- olations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general. empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification:
The paper provides detailed assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
51

---

Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution. reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
model (c.g., large language model), then there should
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In case of closed-source models, may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other rescarchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc/ mubllc//rrilessooddeiiiiiisooooe
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not
52

---

including code, unless this is central to the contribution (e.g., for open-source benchmark).
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: http://pbbb//.uuieeeooootettiiie
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 subset of experiments reproducible, they should state which ones are omitted from the script and why.
submission time, to preserve anonymity, the authors should release anonymized ver- sions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 necessary to appreciate the results and make sense them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
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, statistical significance tests, at least for the experiments that support the main claims 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, 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 the standard deviation or the standard error of the mean.
53

---

is OK report 1-sigma bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 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 fig- ures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 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 failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
http://ppppppppcccc/ccccctaaaa.. ines?
Answer: [Yes].
Justification: The research conducted in the paper conforms, every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make preserve anonymity (e.g., if there is special consider- ation due to laws or regulations their jurisdiction).
10. 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 theoretical work. There is no socictal 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.
54

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimnsss 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 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 needed point out that 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses 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 access the model 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 challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA].
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
55

---

For seraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ daneettsssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA].
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limi- tations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to NeurlPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]-
Justification: This paper does not involve crowdsourcing or research with human subjects.
56

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted. IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
57


Reviews:
[{"review_id": "z6vT7TOsOm", "reviewer": "Reviewer_3RHd", "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.", "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?\n\nQ2. What is $\\mathbb{V}$ in line 329? Is it variance?\n\nQ3. Why is Assumption 2 not needed in Theorem 13, even though the line above says that this result is a corollary to Theorem 12?\n\nQ4. Can the ideas in this work be extended to the RL setup? \n\nQ5. Can the ideas in this work be extended to the case of interactive decision-making with multiple agents? \n\nI am happy to increase my score based on your response.", "limitations": "The work does not explicitly discuss the limitations of their work; at least, I could not find it anywhere.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "S1. The paper discusses a unified perspective of techniques to derive lower bounds. It integrates classical techniques (Fano’s inequality, Le Cam’s method, and Assouad’s lemma) with contemporary methods for interactive decision-making, based on the Decision-Estimation Coefficient (DEC). \n\nS2. This work introduces a novel complexity measure called decision coverage. This measure facilitates the derivation of new lower bounds specifically tailored for interactive decision-making.", "weaknesses": "See questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper!\n\n\n> Q1. How realistic is Assumption 2? It seems to require that we have a model that is close to all models It is unclear why should such an assumption be true for a finite Similarly, how realistic is Assumption 3? Can you give some application examples where Assumptions 2 and 3 hold?\n\nA1: Assumption 2 is a relatively mild condition on the model class $\\mathcal{M}$. Examples:\n\n(1) **Bandits.** Suppose that $\\mathcal{M}$ is a class of bandits with Gaussian rewards, i.e. $\\Pi=\\mathcal{A}$ is the action space, and for each $M\\in \\mathcal{M}$, $a\\in\\mathcal{A}$, the observation is generated as $o\\sim N(f^M(a),1)$. Then, we can consider the reference model $\\overline{M}$ with $f^{\\overline{M}}(a)\\equiv 0$, and $D_{KL}(M(a)||\\overline{M}(a))=\\frac{f^M(a)^2}{2}$. Therefore, $C_{KL}$ is bounded as long as the mean reward is uniformly bounded for models in the model class $\\mathcal{M}$.\n\n(2) **Contextual bandits.** Suppose that $\\mathcal{M}$ is a class of contextual bandits with context space $\\mathcal{C}$ and Gaussian rewards. Then, similar to (1), we can bound $C_{KL}\\leq \\log|\\mathcal{C}|+O(1)$.\n\n(3) **Problem classes with bounded observation $\\mathcal{O}$.** For finite $\\mathcal{O}$, we can always bound $C_{KL}\\leq \\log|\\mathcal{O}|$.\n\nMore generally, $C_{KL}$ is bounded as long as the models in $\\mathcal{M}$ admit uniformly bounded density functions with respect to a common base model. This is indeed the case for most applications, including many control problems and RL problems. \n\nAssumption 3 is a growth condition on the DEC. For a broad range of model classes, including bandits, contextual bandits and structured RL problems (see e.g. [25] and also [23, 9]), the DEC of $\\mathcal{M}$ scales as $C\\sqrt{\\epsilon}$, where $C$ is a quantity depending on the complexity of model class $\\mathcal{M}$, and hence the DEC (as a function of $\\epsilon$) is indeed of moderate growth for such classes.\n\n\n\n\n> Q2. What is  in line 329? Is it variance?\n\nA2: Yes, it is variance. We will clarify this in the revision.\n\n\n\n> 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?\n\nA3: For contextual bandits problem, we can directly bound $C_{KL}$ by $\\log|\\mathcal{C}|$, which is a logarithmic factor and hence hidden in $\\lesssim$. We will clarify this in the revision.\n\n\n\n> Q4. Can the ideas in this work be extended to the RL setup?\n\nA4: Yes, the RL setup is encompassed by the DMSO framework [9], so our results can be applied as-is. It has been shown in [25, 9] that many existing lower bounds for RL problems can be recovered by the DEC framework, and hence the ideas of this work can be directly applied to RL setup. Further, when applied to the RL setup, our framework can give more powerful results than the commonly used Fano method and DEC method, and hence we expect it to provide a unified perspective for proving lower bounds for RL problems.\n\n\n\n> Q5. Can the ideas in this work be extended to the case of interactive decision-making with multiple agents?\n\nA5: Yes, the problem of equilibrium computation in multi-agent decision making is encompassed by the DMSO framework [21], so our results can be applied as-is. In particular, the lower bounds in [21] can also be recovered by our framework through Theorem 6.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U8RCLTIZqL", "reviewer": "Reviewer_Fyj4", "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.", "questions": "See weaknesses.", "limitations": "Essentially no broader societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* The framework developed in the paper is valid for a very general class of problems and unifies classical and classical lower bound techniques, Fano's inequality, Le Cam's method, and Assouad's lemma, and provides a comprehensive framework for statistical estimation and decision making.\n* Lots of other contributions: incorporating the previous work on DEC into the framework of this paper introduces a new complexity measure called decision coverage, which quantifies the  complements of the previous DEC lower bounds.\n* Except for a few typos, the paper is well-written.\n* Overall, it is a solid paper, and contributions are significant.", "weaknesses": "* I dont find any major technical weakness in this work. The work is good and a bit hard to follow for someone who is a non-expert in this area. Most of the points I highlight below are bunch of typos that I found and clarification that I think its good to include. \n* Line 123, I think it should be $L(M,X)$ instead of $L(M^*,X)$\n* 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.\n\n* There seem to be a lot of (minor) typos in Lemma 3, and it's proof.\n1. Firstly, it's better to clarify whether sets $\\theta_0, \\theta_1$ are required to be distinct or not in the Lemma statement.\n2. ASDM is not defined in the first line of proof.\n3. 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? \n4. 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?  \n5. There seems to be a typo in the subscripts of expectation in line 604, third inequality.\n\n* I guess in Line 218 Eq. 9, $p_{out}$ is not defined.\n* I don't think $\\pi_{out}$  in Line 226 is defined before (in the statement of theorem 5).\n* 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.\n* 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.\n* Line 329, I don't think $\\mathbb{V}$ is defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper! We respond to the specific questions as follows:\n\n> 1. The proof of corollary 2 is skipped. It involves 3-4 steps, and therefore I don't think it is trivial, especially for those who are not experts in dealing with these inequalities.\n\nThank you for the feedback. We will be sure to include a detailed proof for Corollary 2 for readers less familiar with these sorts of manipulations.\n\n> 2.  There seem to be a lot of (minor) typos in Lemma 3, and it's proof.\n\n>> Firstly, it's better to clarify whether sets $\\theta_0,\\theta_1$ are required to be distinct or not in the Lemma statement.\n\nIn the most general case, $\\Theta_0$ and $\\Theta_1$ do not have to be distinct. It could be implied to be distinct if the loss function $L$ satisfies $L(\\theta,\\theta) = 0$ for all $\\theta\\in \\Theta$.  \n\n>> ASDM is not defined in the first line of proof.\nWe apologize for the typo. This line is meant to say “ISDM”.\n\n>> 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?\n\nYes, it will contain a factor of 1/2, and it is an inequality due to the convexity of TV distance. And yes, the next step follows by data-processing inequality.\n\n>> In line 603, $d_{3/4}(\\cdot,\\cdot)$ is not defined. May be authors mean $d_{d,3/4}(\\cdot,\\cdot)$. Please also explain why that inequality follows, is it by choice of $\\Delta$ and so that Theorem 1 can be applied?\n\nIn line 574, we defined $d_{f,\\delta}$. In line 603, we mean $d_{|\\cdot|, 1/4}$ where $f(x)=|x|$, which yields the TV distance. We then apply Theorem D.1 with $f(x)=|x|$ and $\\delta=1/4$.\n\n>> There seems to be a typo in the subscripts of expectation in line 604, third inequality.\n\t\nWe apologize for the typo. This should be $\\mathbb{E}_{M\\sim\\mu}\\mathbb{E}\n_{X\\sim {\\mathbb{P}^{M,\\texttt{ALG}}}}[\\ell(M,X)]$.\n\n> 3. I guess in Line 218 Eq. 9, $p_{out}$ is not defined. ...I don't think $\\pi_{out}$ in Line 226 is defined before (in the statement of theorem 5).\n\nThe output decision $\\pi_{\\text{out}}$ is the decision $\\hat{\\pi}$ in line 104, and the output policy $p_{\\text{out}}$ is the distribution over the output decision $\\pi_{\\text{out}}$. We will make sure to add these explanations.\n\n> 4. I would appreciate if the authors mention where the realizability assumption (Assumption 1) is needed and the issues that arise in the agnostic setting, i.e., when realizability does not hold. Also, please provide examples (or references) of well-posed model classes in Assumption 2.\n\n\nWithout the realizability assumption, the lower bound still holds since the model can be arbitrary. The realizability assumption is required for the upper bound, e.g., the last inequality of line 835 in Theorem F.2. When the realizability assumption is not satisfied, the algorithm of EXO+ is not known to adapt to misspecification, so no results can be established. \n\nAssumption 2 is a relatively mild condition on the model class $\\mathcal{M}$. Examples:\n\n(1) **Bandits.** Suppose that $\\mathcal{M}$ is a class of bandits with Gaussian rewards, i.e. $\\Pi=\\mathcal{A}$ is the action space, and for each $M\\in \\mathcal{M}$, $a\\in\\mathcal{A}$, the observation is generated as $o\\sim N(f^M(a),1)$. Then, we can consider the reference model $\\overline{M}$ with $f^{\\overline{M}}(a)\\equiv 0$, and $D_{KL}(M(a)||\\overline{M}(a))=\\frac{f^M(a)^2}{2}$. Therefore, $C_{KL}$ is bounded as long as the mean reward is uniformly bounded for models in the model class $\\mathcal{M}$.\n\n(2) **Contextual bandits.** Suppose that $\\mathcal{M}$ is a class of contextual bandits with context space $\\mathcal{C}$ and Gaussian rewards. Then, similar to (1), we can bound $C_{KL}\\leq \\log|\\mathcal{C}|+O(1)$.\n\n(3) **Problem classes with bounded observation $\\mathcal{O}$.** For finite $\\mathcal{O}$, we can always bound $C_{KL}\\leq \\log|\\mathcal{O}|$.\n\nMore generally, $C_{KL}$ is bounded as long as the models in $\\mathcal{M}$ admit uniformly bounded density functions with respect to a common base model. This is indeed the case for most applications, including many control problems and RL problems. \n\n\n> 5. It is not clear to me why there exists $M$ in the model class, i.e., why is the supremum achieved here by some $M$ in proof of Theorem 5.\n\nWe proved in Theorem 5 that $\\sup_{M\\in\\mathcal{M}} \\mathbb{P}^{M,\\texttt{ALG}}\\left( g^M(\\pi)\\geq \\Delta \\right)> \\delta$. Notice the supremum is *strictly* larger. Thus, by the definition of supremum, there exists one model that is larger than $\\delta$.\n\n> 6. Line 329, I don't think $\\mathbb{V}$ is defined.\n\nThank you for pointing this out. \\mathbb{V} is defined as variance. We will be sure to clarify this in the final revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MfsSPXFVlG", "reviewer": "Reviewer_uqGG", "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).", "questions": "Please see weaknesses above.\n\n- 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": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think it's interesting to try to unify different lower bound approaches in order to gain new insights, so the premise of the paper is very intriguing to me. The submission further uses the general theorem to derive new bounds, based on the new notion of Decision Coverage, that tightens existing results in interaction decision making.", "weaknesses": "It may be due to my lack of expertise in interaction decision making literature, but I'm having trouble understanding and evaluating the new contributions, with intuition missing that I hoped the paper would give. Some of the contributions also seem a bit overclaimed. I hope the following constructive criticisms would help the authors improve the paper.\n\n- \"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.\n\n- 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?\n\n- 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?\n\n- 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.\n\n- 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.\n\nMisc typos I spotted and other small comments:\n\n- First page, should define Perf as cost, so that minimization is the correct direction.\n- End of Line 123, should the asterisk in $M^\\ast$ be removed?\n- 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.\n- Line 594, I presume \"ISDM\" instead of \"ASDM\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and constructive criticism! We will work on better presenting the intuition behind our results and revise our statements to make them more precise.\n\n> Regarding \"addressing remaining gap\" and \"complete characterization\": the lower and upper bounds differ quadratically ...They aren't even tight up to constants.\n\nIndeed, by using the term \"complete characterization\", we want to highlight that DC and DEC together provide a characterization of *polynomial learnability*. Although their lower and upper bounds may not offer a tight characterization of the T-round minimax risk, our one-round complexity measures, DC and DEC, elucidate what is necessary and sufficient for the estimation component (DC) and the estimation-to-decision-making component (DEC) in interactive decision making. \n\nDC is essential because it appears in both the upper and lower bounds (similar to DEC). In contrast, prior work [23][25] includes a $\\log|\\mathcal{M}|$ factor only in the upper bound, with no hope of it appearing in a lower bound. This discrepancy was identified as a major open question in previous studies [23][25]. To address this gap, we need to eliminate $\\log|\\mathcal{M}|$ and identify DC that appears in both upper and lower bounds.\n\n> 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?\n\nSorry for the confusion. Mixture-vs-mixture is indeed a generalization of the singleton two-point method, and we mean to say that our approach recovers both, rather than unifying them into one concept. Our intention is to convey that our method unifies mixture-vs-mixture (and thus the entire scope of two-point methods) with Fano's and Assoud's methods, where these three previously lacked a unified perspective. We will rewrite the sentence as “unify mixture-vs-mixture (and thus the entire scope of two point methods) as a special case of our general algorithmic lower bound” to convey the right message.\n\n> Generally I find the bound in Theorem 1 challenging to interpret, ...why is Le Cam/Assaoud/Fano even part of the paper, instead of focusing only on the new bounds in interactive decision making?\n\nOur 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.\n\nMoreover, by utilizing the algorithmic Fano method (Proposition 8), we not only introduce the new complexity measure DC (Theorem 12), which includes the dimension in the lower bound, but also recover a tight lower bound for linear bandits (Corollary 9), which would otherwise not be captured by Theorem 12. This also illustrates the advantage of having a unified method for interactive decision making and Fano’s method.\n\n> 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.\n\nThanks! We will provide a detailed step-by-step explanation in the revised version. The minimax-optimal sample complexity $T^\\star(\\mathcal{M},\\Delta)$ is just a way to better illustrate our minimax regret upper and lower bounds. \nAssumptions 2 and 3 are conditions to establish that the additional terms in the regret upper (Theorem 11) and lower bound (Theorem E.1) are of the same order as the dec terms. This ensures that one has \n$$\n\\mathrm{dec}^c_{\\underline{\\epsilon}(T)}(\\mathcal{M}) \\lesssim\\frac{1}{T}\\mathrm{Reg}^\\star_T\\lesssim \\mathrm{dec}^c_{\\bar{\\epsilon}(T)}(\\mathcal{M})\n$$\nTheorem 12 is then proved by using the definitions of sample complexities $T^\\star(\\mathcal{M},\\Delta)$ and $T^{\\rm DEC}(\\mathcal{M},\\Delta)$. \n\n> Relatedly, again on the topic of needing more interpretation, I wish the submission explained how DC is better than the factor $\\log|\\mathcal{M}|$ in Line 282.\n\nDC is fundamentally different with $\\log|\\mathcal{M}|$ because it arise in both the upper and the lower bounds, while $\\log|\\mathcal{M}|$ only appears in the upper bound (and there is no hope for having it appear in a lower bound in general). Comparing Theorem 12 and Line 282, one can observe that DC together with DEC gives a complete characterization of the sample complexity up to a quadratic order. In contrast, $\\log|\\mathcal{M}|$ is clearly not a good candidate for the estimation component in the lower bound, as it is the coarsest measure in learning theory.\n\nMoreover, for examples like convex bandits, the $\\log|\\mathcal{M}|$ factor is obviously too loose, which will be $\\exp(d)$ for the complete class of convex functions, while we know that $poly(d)$ regret is achievable for convex bandits [23][32].\n\n> 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? ...\n\nThis is a great question! In our proof of Theorem 1, we essentially establish a lower bound for the quantile $\\mathbb{P}_{M∼\\mu, X\\sim{\\mathbb{P}^{M,ALG}}} (L(M, X) \\geq \\Delta)$ (line 578). This quantile lower bound (Theorem D.1) can be directly used to prove a high-probability lower bound in a straightforward manner (for any error $\\delta$).\n\n> Misc typos I spotted and other small comments...\n\nMany thanks for pointing these out. We will be sure to clarify these issues in the final revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Har1XJrGzm", "reviewer": "Reviewer_zJ4c", "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.\"", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I find the general formulation and the technique based on percentiles (instead of the expected value used in prior literature such as [25]) for deriving lower bounds to be quite appealing. Although it appears to me that the lower bounding techniques are essentially \"abstracted out\" from prior literature, such as [11] and [23, 25], the paper presents it in a quite clean manner. The paper also provides several new results, such as interactive parameter estimation and tighter bounds for interactive reward maximization. I generally enjoyed reading this paper and find it worthy of publishing at NeurIPS. I expect the paper to have a broad impact on the community.", "weaknesses": "My main complaint about this paper is that it contains many hand-waving arguments. I had to fill in many gaps in the proofs myself to verify and understand the results.\n\nI outline some specific comments below (some are minor, while others need additional justifications):\n\n1. 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).\n2. 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?\n3. 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.\n4. Can you comment on how prior technique for deriving Corollary 9 differs from your Fano's inequality-based argument?\n5. 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?\n6. 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?\n7. Theorem 10 looks quite trivial to me, as it does not depend on any information-theoretical structure of the model class (except Assumption 2).\n8. 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)?\n9. 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?\n10. 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|$)?\n11. Typos (there are many, but I only include what I still remember):\n    - $D_f(a,b)$ was never properly defined, though one can guess it is for $D_f(\\text{Bern}(a),\\text{Bern}(b))$.\n    - What is the $\\alpha$ in line 873?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper!\n> Q1. I'm not sure if it's appropriate to call Corollary 2 \"Generalized Fano’s inequality\"\n\nIn our proof of Theorem 1 on page 15, we actually prove Theorem D.1, which holds for general quantile $\\delta\\in(0,1)$ rather than $½$. Similarily, Corollary 2 can be generalized to any $\\delta$: when $I(M;X)+\\log 2\\leq (1-\\delta)\\cdot \\log \\frac{1}{\\mu(M \\in \\mathcal{M} : L(M,x) < \\Delta)}$, the Bayes risk $\\geq\\delta\\Delta$. This precisely implies original Fano’s inequality when $\\mu$ is uniform, $\\mathcal{M}=\\mathcal{X}, L(M,x)=\\mathbb{1}(M\\neq x), \\Delta=1$. We will restate Corollary 2 for arbitrary $\\delta$ and clearly explain the generalization.\n> Q2. You claim in line 186 \"Fano’s inequality, e.g., in the form of Corollary 2, cannot be used to prove Lemma 3.\"\n\nFano’s method and the “mixture vs mixture” method described in Lemma 3 are conceptually distinct due to the use of different divergences. In particular, Lemma 3 (and the mixture vs mixture method in general) use total variation distance, whereas Fano inequality uses KL-based mutual information. As a result, unless the distributions under consideration have favorable structure that allow one to bound the KL-based mutual information by total variation distance, it does not appear to be possible to recover Lemma 3 from Corollary 2.\n\nWe mention in passing that we are not aware of any results which recover guarantees based on the mixture vs. mixture method from Fano method in prior work.\n> Q3. How Theorem 5 is instantiated from Theorem 1?\n\nThe current proof of Theorem 5 is indeed self-contained (for completeness), but the idea is the same as Theorem 1, and it can indeed be proven as a corollary. To instantiate Theorem 1, we can choose the $f$-divergence to be the squared Hellinger distance, set $\\mathbb{Q}=\\mathbb{P}^{\\overline{M},ALG}$, and choose $\\mu$ to be the delta distribution on the model $M$. We will clarify this in the revision.\n> Q4. How prior technique for deriving Corollary 9 differs from your Fano's inequality-based argument?\n\nPrior work proves the regret lower bound in Corollary 9 using Assouad’s lemma (see e.g. Section 24 of [34]), which explicitly relies on the hypercube structure of the parameter space. By contrast, the proof of Corollary 9 is based on bounding the mutual information under a certain (uniform) prior and then applying Fano’s inequality. Conceptually, these two approaches appear to be fairly distinct (Assouad’s lemma often gives tight results when hypercube structure is available, while the Fano method is somewhat more general, but can require more effort to apply, particularly in interactive settings; therefore, it is interesting to see that both lead to the same result here).\n> Q5. How T∗(M,Δ) characterizes the regret? Why does Theorem 4 imply line 282?\n\nBy the definition of $T^\\star(\\mathcal{M},\\Delta)$, we have\n$$\n\\frac{1}{T}\\mathrm{Reg}^\\star_T=\\sup\\{ \\Delta: T^\\star(\\mathcal{M},\\Delta)\\leq T \\}.\n$$\nFor example, $T^\\star(\\mathcal{M},\\Delta) \\asymp \\frac{C}{\\Delta^2}$ implies that $\\mathrm{Reg}^\\star_T \\asymp \\sqrt{CT}$.\n\nFurther, notice that Theorem 4 implies (under Assumption 3)\n$$\n\\mathrm{dec}^c_{\\underline{\\epsilon}(T)}(\\mathcal{M}) \\lesssim\\frac{1}{T}\\mathrm{Reg}^\\star_T\\lesssim \\mathrm{dec}^c_{\\bar{\\epsilon}(T)}(\\mathcal{M})\n$$\n\nThe statement in line 282 then follows from the definition of $T^\\star(\\mathcal{M},\\Delta)$ and $T^{\\rm DEC}(\\mathcal{M},\\Delta)$.\n> Q6. The proof of Theorem 10 is too sketchy. Are you applying the minimax theorem here?\n\nThank you for pointing this out. The current presentation of the proof focuses on highlighting the connection to Proposition 8, which is somewhat subtle and requires applying the minimax theorem. We will be sure to include more details in the final revision (there is also a more direct proof, which we are happy to include for completeness).\n> Q7. Theorem 10 looks quite trivial...\n\nIndeed, the quantity DC measures certain inherent complexity of the decision space, and it does not depend on the information-theoretical structure of the model class. However, it does imply non-trivial lower bounds for various model classes:\n\n(1) Linear bandits: $\\mathsf{DC}\\gtrsim d$\n\n(2) Unstructured contextual bandits with context space $\\mathcal{C}$: $\\mathsf{DC}\\gtrsim |\\mathcal{C}|\\log|\\mathcal{A}|$\n\n(3) Tabular RL: $\\mathsf{DC}\\gtrsim |\\mathcal{S}|$.\n\nGiven that the proof of Theorem 10 only utilizes the structure of the decision space, DC should be regarded as a (non-trivial) complexity measure that is complementary to DEC (which captures the information-theoretical structure of the model class), in the sense that the lower bounds they provide are complementary, and together they provide also an upper bound (Theorem 11).\n> Q8. How to interpret your Theorem 12? Any specific examples?\n> Q9. Isn't max{a,b} can be arbitrarily smaller than a⋅b? How should the \"matching\" be interpreted?\n\nThe main contribution of Theorem 12 is that the upper bound is at most the square of the lower bound (as $a\\cdot b\\leq \\max(a,b)^2$). Therefore, for **any** convex model class, the sample complexity is completely determined by DEC and DC up to a square gap. Such a characterization of sample complexity for general decision making is new, and we believe it to be conceptually important.\n> Q10. Can you comment on if the results from [24] recover your upper bound (with possible replacement of decision coverage with log⁡|Π|)?\n\nOur proof of Theorem 11 is essentially an adaptation [24], with the goal of replacing $\\log|\\Pi|$ by the decision coverage in the upper bound. For general decision making problems, $\\log|\\Pi|$ can be arbitrarily larger than the decision coverage, meaning that our upper bound represents a significant improvement.\n> Typos\n\nThank you for pointing out these typos. Indeed, $D_f(a,b)$ is the abbreviation of $D_f(Bern(a),Bern(b))$, and $\\alpha$ in line 873 is a typo. We will clarify these in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (spotlight)