A Unified Model and Dimension for Interactive Estimation
Authors: Nataly Brukhim
Miroslav Dudík
Aldo Pacchiano
Robert E. Schapire
Venue: NeurIPS 2023 poster (2023)
Keywords: Interactive learning
bandits
statistical queries

Abstract: We study an abstract framework for interactive learning called interactive estimation in which the goal is to estimate a target from its ``similarity'' to points queried by the learner.
We introduce a combinatorial measure called Dissimilarity dimension which largely captures learnability in our model.
We present a simple, general, and broadly-applicable algorithm, for which we obtain both regret and PAC generalization bounds that are polynomial in the new dimension. We show that our framework subsumes and thereby unifies two classic learning models:
statistical-query learning and structured bandits. We also delineate how the Dissimilarity dimension is related to well-known parameters for both frameworks, in some cases yielding significantly improved analyses.

A Unified Model and Dimension for Interactive Estimation
Nataly Brukhim
Miro Dudik
Princeton University
Microsoft Research
nbrukkiimpprinctton.cc
ndudikemicroooff.
Aldo Pacchiano
Robert Schapire Microsoft Research
Broad Institute of MIT and Harvard & Boston University
apachhi@@broadd.ssiituu....
rchapiire@microoffe com
Abstract
We study an abstract framework for interactive learning called interactive esti- mation in which the goal is to estimate target from its "similarity" to points queried by the learner. We introduce combinatorial measure called dissimilarity dimension which is used to derive learnability bounds in our model. We present simple, general, and appllaa-applicaale algorithm, for which we obtain both regret and PAC generalization bounds that are polynomial in the new dimension. We show that our framework subsumes and thereby unifies two classic learning models: statistical-quer learning and structured bandits. We also delineate how the dissimilarity dimension is related to well-know parameters for both frameworks, in some cases yielding significantly improved analyses.
Introduction
We study general interactive learning protocol called interactive estimation. In this model, the learner repeatedly queries the environment with an element from a set of alternatives, and observes a stochastic reward whose expectation is given by arbitrary measure of the "similarity" between the queried alternative and the unknown ground truth. Thus, in rough terms, the goal is to estimate target from its similarity queried alternatives. By studying such general abstraction of interactive learning, we are able to reason about the properties of a very broad family of learning settings, and to make connections across a variety contexts.
Our results are based dimension, which is used to derive Icarnability bounds in our model. Intuitively, this measure corresponds the length of the longest sequence of alternatives in which each has similar suboptimal value of similarity to its predecessors. We then use the measure to analyze the performance of simple, broadly-applicable class of algorithms which repeatedly make queries that best fit the preceding observations. We prove both regret bounds and PAC generalization bounds that are all polynomial the dissimilarity dimension.
combinatorial complexity measure we introduce called the dissimilarity
We show that our learning framework subsumes two classic learning models that were seemingly unrelated prior to this work:
First, our model subsumes the statistical query (SQ) model, introduced by Kearns [19 for designing noise-tolerant learning algorithms. In the SQ model, the learner can sequentially ask certain queries of an oracle, who responds with answers that are only approximately correct, with the goal of correctly estimating target. Despite its simplicity, it has been proven to be a powerful model. Indeed, wide range of algorithmic techniques in machine learning are implementable using SQ learning. Thus. has been proven useful, not only for designing noise-tolerant algorithms, but also for its connections
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

to other noise models, and as an explanatory tool to prove hardness of many problems (see the survey of Reyzin (23). We show that our framework subsumes the SQ model, and furthermore that the dissimilarity dimension generalizes well-known parameters that characterize SQ learnability.
Second, our model captures structured bandits, which the learner repeatedly chooses actions which yield stochastic rewards, with the goal of minimizing regret relative to the best action in hindsight. Over more than a decade, the eluder dimension [24] has been a central technique for analyzing regret for contextual bandits and reinforcement learning (RL) with function approximation [30 22 29 10)
We will see that the dissimilarity dimension upper-boundes by the eluder dimension, and that there can in fact be large gap between the two. This sometimes leads to improved analysis when relying on the proposed dissimilarity measure rather than the cluder dimension.
Because SQ and bandits are both subsumed by our framework, all the results mentioned above directly apply to those settings as well, including the applicability of our general-purpose purpose algorithms.
To summarize, main contributions are follows:
Unified framework. We derive a general framework which captures various interactive learning settings, including specifically SQ and bandits.
Novel dimension, performance bounds. We introduce the dissimilarity dimension that is used to derive learnability bounds in our model. We study a general, simple algorithm, and give a novel analysis that results in both regret and PAC generalization bounds that are polynomial in the new dimension. We also give lower bounds in the SQ and bandit settings.
Improved analysis. We show instances in which the standard analysis of certain class of algorithms using the eluder dimension yields bounds that are arbitrarily large, but in which an analysis using our dimension yields low regret bounds.
Related work. The interactive estimation model we consider in this work is defined with respect to an evaluation function that can be thought of as an arbitrary measure of the "similarityy between the queried alternative and the target. Previously, Balcan and Blum 3 developed theory of similarity- based learning that generalizes kernel methods, providing sufficient conditions for a similarity function to be useful for learning. Chen et al. { review several approaches to classification based on similarity between examples, including, for instance, kernels and nearest neighbors. Ben-David by-distances model that resembles ours using a metric as a measure of
et al. [5] studied a similarity. In comparison to these works, our model admits an arbitrary similarity measure for which we derive a general dimension, algorithm, and bounds.
In the context of bandit and reinforcement learning, parameter called the decision-estimatio coefficient (DEC) has recently been proposed by Foster et al. [15] to characterize learnability in interactive decision making. Unlike DEC, our dimension is combinatorial in nature, and applies to settings like SQ, which are not captured by DEC.
As discussed above, model subsumes SQ and bandits, both of which have been extensively studied (see the references above as well as various surveys (20 23
2 Setting
In this paper, we study interactive learning protocol called interactive estimation. In this protocol, the leamer is provided with a set Z of alternatives, and an evaluation function p Z x Z + [-1, 1]. Intuitively, P can be viewed as a measure of "similarity," though it need not be symmetric. There is also a distinguished alternative z" E 2 called the target, fixed throughout the interaction, and unknown to the learner. In each of a sequence of steps = -....., T. the learner selects one alternative 2, E Z and receives a stochastic reward re E [-1, 1] drawn independently, conditioned on &t with expectation satisfying E/r, 2 = p(2; a²) Informally, by choosing alternatives and observing their similarity to 2", the learner aims to get close to the target. The special case when p(2e 2²) that is, when rewards are deterministic functions of the queried alternatives, is referred to as the deterministic setting.
We generally assume
2 p(= 1=" for all E and denote this optimal value as a" : p(=" )) We will assume that the value of a* is known to the learner or that we are provided with an alternate optimality level a S a" such that the task is to identify z with p(z =*)= 2 a. At the end of Section we discuss how this assumption can be relaxed.

---

We consider two alternative goals for leamer in this model: sublinear regret and PAC  A  achieves rublinear regrer relative to an Optimalliy level a < a if Regretti a) =o =(T). vemee where
Regret(T,o) a) = -( ( C(2-p(2e12)
T -
plzz p(==((=)=))) 1=').
We say that leamen achieves PAC remeralizane if for any c, 0 and S a", with inbaabliii at least 1 - 5 (over the aandomen of the query responsee and the learner's Sermer's s own randomization after mice 6, ) interactions in the protocol above, the learner outputs & such that p( ==)) Z a - c. The The function vn(e, 6, a)) is referred to as sample co We recover standard notions of regret and PAC generalization by setting a = =a"
Exampre (Point on a sphere). Ler ||-I| denote the standard Euclidean norm in Ip" and let 2 = Let||
- {z E R ||z|| = 1) be the unit sphere in RR. The goat is to estimate an unknown point z E S..11 basedooo on rewards equal to the inner product between the queries and the target,  that is rt Pephere (Ze) (22)) = (Z,, 2").
We now introduce the two main examples corresponding to classic learning models that are subsumed by the interactive estimation model.
Example (Structuree bandits). Let A be an action set, F a space of reward reward functions f : A -1,1]. and f E F the target reward function. In step t, the learner chooses an action O E A and receives reward rt E [-111] 1] with E(r, ail = (at). The goal is to masiimie the sum of rewards Let a' = Seemmassee fr (0) be an optimal action. To represent bandits in our formalism. we let
optinad
2 - F x A.= x ( " and Prandits (J
= f (a)-
The structured bandit handitpae problem has been extensively studied, and Example capturee its expressivenesss within our framework. For exampie- it recovers the possibly simplest case of K Karmedd bandits, by considers considering A = {I, .... }} and F = [0, 1]x At each round, the learner chooses arm Ot E AA and observes reward ri which is drawn from a distribution with mean f (a,).. See Appendix D for
more concrete example of K K-armed bandits instantiated within within our framewodd In Section
5 we also e
give concrete bounds for other exampie classes Including linear bandits and GLM bandits.
We remark that although the protocol in which the learner submits pairs (f, in each round rather than an action a, may seem more complicaut than the standard bandits protocol, it is in fact equivalent function as the function f is ignored in the evaluation. Moreover, this formulation raturally captures any
algorithing for realizable bandits. Such algorithmne often keep track of a version space (set of functions if consistent with the data), and so at each point of interaction, there is an implicit fi that is associated with a produced at that time. The above p protocol simply makes the choice of fa explicit. explictt
producee
Example 3 (sQ learning). Given a domain X, the& goal is to learn a binary classifier ht" : X + {+1} from some hypottessts class H. C {=1}*, based on training examples (z. y) drawn from some distribu- tion D such that y = h (z). In step t, the learner produces a hypothesis he and observes the accuracy of he on a fresh finite sammple In this case, Z = H. the evaluation renction is equal to the expected ac- [m( (x)], and the reward is the empirical accuracy on a fresh sample. = Eg-D D
curacy (s (h) kt*)
The SQ learning model considered in this work (Exxmple 3 differs from the original model of Kearns 19 because it is restricted, as in previous works [3] 31,, to so-called orreeiationnne
Responaa (SOs) and g
of queries (called various various SQ variants in serendda queries and adversarial
assumes stochastic pepponee as opposed to allowing arbitrary
dalationssii between weeeennennnneeeee p
We discuss
We finish this section by mitrodhgiie central concept of this paper, new combinatoria complexity ainuue meeaure called the bysimiitarti
protocol. eetoeeeetstiiii etlmaadtoo iitemmitoon which, as we will see, allows us to derive tearaaility
bounds for the interactive recrective
Definition DDissimijll
intensionn, For a set 2, scalars a E RR, 6 > O, and ovaluation function 11, the Aimmmaaiy dimensioon d2(2, a, is the largent integer d for which there e G, such that for all i < 3.
Definition
p: 2 x Z - 1-11
with?P - 2a E Z with p(2: 2.) 2 a, and a scalar c S a - exist 21. -..
| (2))) - c s Vd
3

---

dd
vd
(
C )
0
Q
1
Figure An illustration of the dissimilarity dimension dz(2, a, 4. The figure shows p values the [0, 1] interval for sequence of elements 21, 22, 23, 24. The four green points represent self-evaluation values p(z; z;) for I,..., 4; all are greater than or equal to a. The six blue points represent values p(z; 2ÿ) for < j: all are within the distance e/ e/vá from the value a
Furthermore, denote the monotonic dissimilarity dimension as á,(Z, max./e malp/aaxxe/eee.... a2,,,, a,,),,,))))
Note that d,(2, a. = if there is no such that p(=|22 a, and otherwise 4p a c) 2 In particular, if a S a' then d, a,
In rough terms, this dimension corresponds to the longest sequence of points with e-large self- evaluation, such that the evaluation p(z; 2j) of each point 2; relative every successive point 2j is "small" (significantly less than a), and also tightly clustered around some value c. Thus, each point similar itself, but dissimilar from all successive points about the same degree. The idea is illustrated in Figure []] The monotonic dissimilarity dimension is the tightest upper bound on the dissimilarity dimension that is con-innreasing
Various concrete examples where the dissimilarity dimension can be bounded are provided in Section 5) For instance, using a general bound for linear bandits from Section 5 we can show that for the task of finding point on sphere based on inner products (Example T). the dimension Pasterc (2,a,)) < 4n + 3, a bound that is independent of both a and e.
a
3 Algorithms and upper bounds
In this section we analyze algorithms for the interactive estimation protocol, which we call inferactive estimation algorithms. We show that when an interactive estimation algorithm satisfies two properties, large self-evaluations and decaying estimation error, then its regret can be bounded using the dissimilarity dimension. We introduce a simple algorithm (Algorithm [ which satisfies these properties for many standard classes of alternatives. The first property requires that the algorithm only select alternatives that would achieve the expected reward of at least a they were the target:
Definition (o-large self-evaluations).
interactive estimation algorithm has a-large self- evaluations if at every time step = 1,...,T, T, it selects query such that E Z where
2, = E 2 p(=
(1)
Algorithm Trarrithmmssaiiinn satisfies this property, with the optimality level provided as input. At the end of the section, we discuss the case when a is not provided and ax is unknown. We derive an optimistic version of Algorithm that achieves llage self-evaluations with high probability.
The second property states that the queries produced by the algorithm provide increasingly good estimates of the expected rewards the previous rounds (that is they are good estimators with the benefit of hindsight), as quantified by the square loss.
Definition (Decaying estimation error). An interactive estimation algorithm has decaying estima- tion error if there exists Cr,$ 2 growing sublinearly in T, that is, Cr o(T',, such that with
We remark that the term Vd in Definition | can be generalized any function g(d) and state main results in terms of However. for case of presentation we pick g(d) = Vd as it simplifies the comparison between the dissimilarity dimension and eluder dimension (e.g. Thm. and Prop. 12

---

Algorithm Interactive Estimation via Least Squares
1: Input: set of alternatives 2, evaluation function p. optimality level a, number of steps T.
2: for = 1,..., T do
3: Submit the query R1 = arginin =E2. 1=1
Σ
p05 -ra)
4: Observe reward rt-
5: end for
probability at least 8 the sequence of queries 2 24 produced by the algorithm satisfies
Σ (plzll22) -(=2)=1)))) S Cr,6
(2)
for all t E {I,...,,Ty . simultaneously.
Algorithm ! opttimizes an empirical version of Eq. (). with the observed rewards ry in place of the expectations p(z; 2²). Thus, in the deterministic setting, with r; p(z; =²), Algorithm satisfies
this property with Cr,6 O. It can also be shown that it satisfies this property when the set of
alternatives is finite:
Theorem 4. Assume that Z co. Then Algorithm satisfies the decaying estimation enror property with Cr,s (I((T)Z)/6).
In the general case, when is infinite, we show that Algorithm satisties the decaying estimation error property with Cr.s Olog((TN/o)) where N is a suitable covering number of Z (see Corollary i Appendix A. For example, for linear bandits, which is an instance of Example 2 in which the action set and function class correspond to subset of the unit ball in R", we obtain CT,3 (n (o/(1/c) log(T/))).
In Appendix A.3 we discuss an approach in which we have access to an online regression oracle for the least squares problem in step 3 We show that suitably modified version of Algorithm [1 has a decaying estimation error as long as the online regression oracle achieves a sublinear regret (but without further dependence on covering number).
To develop some intuition how Algorithm [ works, we can again consider the K K-armed bandit problem (a special case of Example 2). and suppose that 0.75. In each step, the algorithm picks pair (fe, oz), where ft E [o, 1]a is the vector of mean reward estimates and a, is the arm with the largest mean estimate. The estimates fi(a),
1,..., K, are formed by optimizing the least squares eтror of the observed rewards, under the constraint that at least one of the mean estimates must be above 0.75. As result, the algorithm pulls the arm with the largest average reward long as that average is above 0. 75 (arms that have not been pulled are assumed to have averages above 0.75). If all the averages n. (0.75 )aa) where na is how many times the arm has been pulled so far and Paa is its average reward; it can be verified that this solves the least squares problem subject the constraint that at least one of the mean estimates is above 0.75.
below 0.75 then the algorithm selects the arm with the smallest value
We next state our main results: regret bound and PAC generalization guarantee. They are both based on bounding how many "bad" queries any algorithm with large self-evaluations and decaying estimation error can make. Concretely, we say that a query Z is e-bad if its suboptimalty gap is greater than e, that is, if
<a-c
The next lemma shows that the number of e-bad queries is upper bounded polynomially in the dissimilarity dimension.
Lemma (Few had queries). Let c,6 > O, and let d d= (2, < 00 for some set Z, evaluation function p and a S a". Let Alg be interactive estimation algorithm with a-large self-evaluations and a decaying estimation error with some CT,S. Then, with probability at least 1 - 5, the number of e-bad queries that Alg makes in T steps is at most 2d In(4/c) + 12d==Cr,s/ee. Consequently, if Cr 2 In(2T). then with probability at least 1 8, the number of e-bad queries is at most 36d2. 5 s/2,, and if Cr.s then it is at most 2d In(4/e).
5

---

Algorithm 2 PAC Interactive Estimation
1: Input: set of alternatives 2, evaluation function e. optimality level a.
base interactive estimation algorithm Alg, parameters T, n1, n22
2: Run algorithm Alg with the provided Z, P; a.
3: Sample nu indices .1y..., bng uniformly at random from {
4: For each 8 1,..., RI, submit query 2 for rt times; denote the average response Fre
5: Let é argmax Ptg-
6: Output Ztz-
The above result is the core component of our main theorems. The proof is given in Appendix A.44 here we sketch the main ideas. The goal is to show that the "bad" interval [-1, c] cannot contain too many queries made by Alg. The proof starts by partitioning this interval into disjoint subintervals and then bounds the number of queries in each subinterval. It does so by constructing a graph with nodes corresponding to queries, which are connected by an edge if they satisfy the dimension conditions. The decaying errors that imply certain minimum number of edges (as function of number of queries). On the other hand, the dissimilarity dimension bounds the size of the largest clique, which implies an upper bound on the number of edges (using Turán's Theorem [26), a standard result from extremal graph theory). Combining the bounds yields an upper bound on the number of queries in the subinterval. Summing across subintervals proves the lemma.
The following theorems use Lemma to bound both the regret and PAC sample complexity. The proofs are deferred to Appendices and A.7 and
Theorem (Regret). Let 5, > O, and let d,(2,,, oz, 1/T) and S a². Let Alg be an interactive estimation algorithm with a-large self-evaluations and decaying estimation error with some CT,5. Cr,5 2 In(2T)) then with probability at least the regret of Alg satisfies
( for some set 2, evaluation function p
Regret a) < 1 12d 25 VCr,TT
In the deterministic setting, Regret(T,a) < 1 12d
For an algorithm with a decaying estimation error, the term Cr,8 sublinear in T, implying a sublinear regret in Theorem/6) For example, Algorithm| 1 has decaying estimation error with Cr, that scales logarithmically with T/ for many standard function classes, and so the overall regret scales as O(vT log T') (see Corollary
18 in Appendix A.
To derive PAC generalization guarantees, we apply a variant of online-to to-tcch reduction to any algorithm with large self-evaluations and decaying estimation error. The resulting approach, shown in Algorithmm [ satisfies the following guarantee (proved in appendix(A.7}
Theorem 7 (PAC generalization). Let 6 > O, and let d = á,(2, 6) for some set 2, evaluation function p and a S a". Let Alg be an interactive estimation algorithm with a-large self-evaluations and decaying estimation error with CT,5 s > In(2T)) and suppose that we run Algorithm 2 with Alg as the base algorithm, T > (CT.55(CTT//) Then, with probability at least the output E Z satisfies
and n2 = [128 In (a0mmm//)))) /
=
p(2 1=1) 2 a a-c,
and the overall number of issued queries is O R Cran))))))
In the deterministic setting, it suffices to Alg with T 28 (4//c) and return 3 == = where i argmax,g((.....?77 it. is the index of the largest observed reward. Then, with probability obtain p(8 )=*))) 2 a - and issue at most O In(4/e)) queries.
Unknown a' and optimism. Algorithms 1 Jannd] achieve performance guarantees with respect to provided optimality level S a". When is not easy to provide a non-trivial (for example, when a" is unknown and cannot be non-trivially bounded), Algorithm 3 uses the optimistic least squares algorithmic template (see, e.g., (24) to ensure a llrge self-evaluations with high probability and to achieve sublinear Regret(T, ). Algorithm 3 takes as input confidence radius parameter R of the same order as the decaying estimation error parameter Cr,S for Algorithm [ We can then show that 2" Zi with high probability for all t E {L....,)). Therefore, & must satisfy

---

Algorithm 3 Optimistic Interactive Estimation via Least Squares
1: Input: set of alternatives 2, evaluation function number of steps T, confidence-set radius R.
2: for / = I,..., T do
3: Compute confidence set
L-1
& argmin
( (2) -r:)
EE2
i=1
1-1
Σ
p(z) 2)) - (2))11)) s RJ.
2x
2 E 2
1=1
4: Submit the query 2 argmax
22)
5: Observe reward rz.
6: end for
p(2e (4) p==*|==)= - a²" In Appendix A.I A.I we show this modified version of the algorithm satisfies the decaying estimation eπror property. This technique allows us to achieve sublinear Regret(T, a without knowing a" beforehand. Similar to the case of fixed a, it is possible to derive a version of Algorithm
3 that leverages online regression oracle. (See Appendix A.3 for details.)
4 Statistical queries
In this section consider the statistical query (SQ) model, defined in Example In particular, we study the connection between our generalized framework and SQ learning, showing specifically that the dissimilarity dimension be used recover generalization bounds based known combinatorial parameter that characterizes SQ learning, called the strong SQ dimension. There are
several notions of such dimension 12 25 Here focus the one due to Szörényi (55
Definition 4 (Strong SQ dimension, 25 1). For a fixed distribution D over X, the strong SQ dimension
of hypothesis class H S {=1)* with respect to some >> denoted dimso (H, c). is the largest number d for which there exist hi,..., ha E H such that:
(a) (ha, h53l < 1 for all < < S d, and
(b) (he, hy) - (hr, h1)) I & for all 1 < i < seLs < dd
where (h, h") := (h))
The dissimilarity and strong SQ dimensions are closely related to one another in the sense of each providing a kind of polynomial bound on the other, as stated in the next proposition (see Appendix B.I for the proof).
Proposition 8. Let D a fixed distribution over X, and ler H S (=13* be hypotheses class. For > O, let dsq(e) = dimso H. e), and let dp(e) dpsa (H, 1,e).
If (c) 2 then
min (dso(e). |4e² (dso(t)) & do(e) & max maxxfsso (so(le/4), 4e2 (dsole/4) + +}}] (3)
Similarly, if dp(e)) 2 2 then
(4c
dp(c)
min (de),
< dso(t) S max de(e).
(4)
8e
2
We next give a lower bound based on the strong SQ dimension, which together with Proposition will allow lower bound sample complexity of any interactive estimation algorithm in the SQ setting in terms of the dissimilarity dimension.
Theorem 9 (SQ lower bound). Let
O, and ler 7 S [+1]* x be hypothesis class with strong SQ dimension dsq = dimso (,, , 2c) 2 11. Let Alg be any interactive estimation algorithu with the property that for any target h* E H. Alg outputs e-approximation to h" with probability at least
2/3 using at most queries. Then 2/doo/1 12.
7

---

The proof relies on reduction to a lower bound of Szörényi [25]. However, the lower bound of Szörényi [25 holds within an SQ model that differs from ours, in that it allows adversarial query responses. Therefore, we first need to show how to obtain a learning algorithm Alg' that can be used with an adversarial oracle from an interactive estimation algorithm Alg that uses an unbiased stochastic query oracle (as we assume in this work). To do this, we apply the reduction technique developed by Feldman et al. [33. (See Appendix B.2 the full proof and additional details.)
Combining Theorem and Proposition 8 yields lower bound on the sample complexity of interactive estimation in the SQ setting, for sufficiently small c, in terms of the dissimilarity dimension:
Corollary 10. Let > O, and let H S {+1}² K be a hypothesis class with strong SQ dimension dimso (H 26) 2 11. Let dole) = dpsa e)), Assume S (d(e).. Let Alg be any interactive estimation algorithm with the property that for any target h" H. Alg outputs an e-approximation h² with probability at least 2/3 using at most mn queries. Then m \/dle)/12.
5 Bandits
In this section we focus on the bandits setting described in Example 2 We study the relationship between the dissimilarity dimension and the eluder dimension 244, a common combinatorial dimen- sion for bounding regret of bandit algorithms. We show that eluder dimension can be used to upper bound the dissimilarity dimension, and we also highlight the cases when dissimilarity dimension leads to a tighter analysis.
Throughout this section we follow the setup introduced in Example 2 We consider an action set A, a class of reward functions f A > [-1, 1], and target reward function f E F. We map this to our setting by considering the set of alternatives Z F A, evaluation function Pbandits (U,a) (J',a)) = f'(a) and the target (f", aa)), where a" = argmax (a(a..
5.1 Comparison with eluder dimension
We start by describing the relationship between our dimension and the eluder dimension. Following Russo and Van Roy 224. we define e-dependence and c-eluder dimension as follows:
Definition 5 (e-dependence). An action a E A is e-dependent on actions {ai, {a1,..., an3 S A with respect to F if any pair of functions J. E F satisfying v V (f(a:) - ['(a:))² S e also satisfies f(a)- S. Furthermore, action is e-independent of (a1.... (n) with respect to F if is not e-dependent on {a,.-..,,n).
Definition 6 (c-eluder dimension). The c-eluder dimension (Fmg(F, c) is the length d of the longest sequence of elements in A such that every element c-independent of predecessors. Moreover, the monotone eluder dimension is defined as dimg c) = maxe dims (F,,)
The next theorem shows that the dissimilarity dimension is upper bounded by the eluder dimension (see Appendix C.T for proof):
Theorem 11. Let == x A p Phandits > 0, a a². Then áz(Z, a, 3e/2) S 9 dimp (F, e).
Nevertheless, as the next example shows, the cluder dimension can be arbitrarily large, while the dissimilarity dimension remains constant. In this example, the action set is a circle in R², that is, A = = (v E E²² |||| = =1}. We fix two open semicircles Co, U1 C C with positive x and coordinates, respectively. and for any N E N and > O, construct function class FN., with all the functions f AA + [- 1, 1] obtained by the following process. First, pick one of the semicircles U, and any N points from U,. On each of these points, f can equal either +e or ec. Everywhers else in Uy f equals zero, and everywhere outside U,. it equals the linear function (v, a) parameterized by some v C Uz- Thus, the functions are constructed to be "simple" (namely, linear) near the optimal action v, but complex far from it. The eluder dimension is large to capture overall complexity, whereas the dissimilarity dimension is small to capture the simplicity near the optimum. (See Appendix for the formal construction of FN.e and the proof of Proposition] [2)
Proposition 12. Let a function class FN.e. S [-1,1]] such that for ZN., = FNN, x A. dp(ZN, 1, c) 16, but the eluder dimension is lower bounded dimg (FN,.. N.
(0.1/2), N N and consider the action set A C. Then, there is Pbantius it holds that
Thus, our regret bound based on the dissimilarity dimension implies that (optimistic) least squares algorithms have regret independent of N. The same analysis with the eluder dimension 24] yields
8

---

regret bound scaling polynomially with N. This shows that in the cases when the function classes are simple near the optimum, but complex far from it, the dissimilarity dimension can better capture the statistical complexity of bandit optimization than the eluder dimension.
5.2 Dissimilarity dimension bounds
We next derive dissimilarity dimension bounds for several standard bandit classes. Existing bounds on eluder dimension can be used immediately bound the dissimilarity dimension, but in several cases we are able to obtain tighter bounds.
We first consider linear bandits. Let B, (v e R" ||v|| S 1} be the unit ball in R" Actions are chosen from set A S Bn; the reward function class is F = [So 0 E Q), where θ S B, and (a) (0, a). The corresponding set of alternatives is denoted z F x A. In this case we obtain the following bound (see Appendix C.2 a proof):
Theorem 13 (Linear bandits), Let 2h be as defined above, let p= Peandiss and let e > 0, a aa". Then d a, <) S 4n + 3. Moreover, when = 1, then dz(2",, a, 2n + 1.
The proof proceeds by deriving an upper bound as well as a lower bound on the rank of the matrix M with entries M,j = p(z; 2: 2z) - obtained from elements E1.....: 2d that satisfy the dimension condition for d = dp (2,
a, <) with a scalar c. The upper bound on the rank is n + 1, and the lower
bound is d/ (which can be tightened to d/2 when M is symmetric). The upper bound is obtained by basic linear algebra and the lower bound from a standard result on ranks of perturbed identity matrices (2, Lemma 2.2]. Combining these bounds then yields the claim of Theorem 13 Similar to existing bounds on eluder dimension 244 Proposition 6], our bound in Theorem 13 is linear n. However, the eluder dimension bound has an additional dependence on 1/e, while our bound does not.
Next, we consider generalized linear model (GLM) bandits. Similar linear bandits, the action set is A C B,,, but the function class includes a nonlinearity. Specifically, we are provided with a function g TK -> TR that differentiable and strictly increasing, and consider the function class Falm = {fo 0 E } where θ C B,, and fo(a) (( a)). Furthermore, we assume that there are h. h > 0 such that for all a E A. 0 E O, we have h S g' ((((0 a)) S h. Define = h/h. We again denote Zglm_ = Frlm x A. Using an existing bound on the eluder dimension for GL.M bandits (24). Proposition 7) and the fact that our dimension bounded by the eluder dimension (Theorem obtain the following bound (see Appendix for a proof):
we
Theorem 14 (GLM bandits). Let Zalm be as defined above, let p == Pbandits, and let c 0, o a Then dp Zghm a. t) S O(rr log(h/t)).
By considering a different proof technique, along the lines of Theorem 13 it might be possible to tighten this bound. We leave this extension for future work.
Next, we consider bandit setting that is similar to GLMs, but in this case the non-linearity is provided by the non-differentiable rectified linear unit (ReLU) activation function relu(z) = max(2;00 0). We consider the action set A = Bn, and the set of reward functions F consisting of all functions of the form (a) = relu( (0, a) b) for some f E B, and E [0, 1). The subset of Freil with a fixed value of is denoted Frmll, and we consider the set of alternatives 2 = Frclu x B,
Unlike the classes considered above, this setting can be shown to be challenging to learn in the general case. Indeed, it turns out that eluder dimension (as well as a related measure called star dimension) is growing at least exponentially with (21 [O]. The same lower bound can be shown for the dissimilarity dimension by a similar proof technique. The following theorem also provides an exponential upper bound, showing that in certain regimes the exponential dependence is tight (see Appendix C.4 for a proof):
Theorem 15 (ReLU bandits), Let reei be as defined above, let p Phandits, and let e, b > 0 such that b < 1 Then d,(2,clu, 1 b, e) = 00E-n((0 and dz(2) e) = Q(e=n/2)).
We note that previous work ([IO), Theorem 5.1) has shown that for a function class of one-layer neural networks with ReLU activations, obtaining sublinear regret requires T = (n--2)))))
6 Conclusion
In this paper, we have introduced a new model for interactive estimation and proposed a new combinatorial dimension, called dissimilarity dimension, to study the hardness of learning in this
9

---

model. In (stochastic, correlational) statistical query learning, our dimension is polynomially related the strong SQ dimension. In bandits, our dimension upper bounded by the eluder dimension, and there are examples where the dissimilarity dimension leads to much tighter regret bounds.
While this work provides initial investigation of the dissimilarity dimension, many open questions remain. For example, our regret bound for the general setting scales as d'.25, Is it possible to tighten this linear dependence, as is the case, for example, for eluder dimension? On the algorithmic side, we currently require solving a least squares problem of size ł in iteration t. Although we also introduce algorithm that leverages an online regression oracle (see Appendix A.3)). the oracle-based approach still requires solving a least squares problem (on the data smoothed by the oracle). Is it possible to derive dissimilarity Setlaartt-ddmmsiio--bbe by the oracle? Ultimately, we hope investigations of relationships between dissimilarity dimension and related notions may help us understand the hardness of learning in interactive settings.
regret bounds directly for the predictions produced
Acknowledgments and Disclosure of Funding
Aldo Pacchiano would like to thank the support of the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard. This work was supported in part by funding from the Eric and Wendy Schmidt Center the Broad Institute of MIT and Harvard.
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646 PMLR, 2014.
[2] Noga Alon. Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability and Computing, 18(1-2)33-15, 2009.
[3] Maria-Florina Balcan and Avrim Blum. On theory of learning with similarity functions. In Proceedings of the 23rd international conference on Machine learning, pages 73-80, 2006.
[4] Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. Journal of Computer and System Sciences, 56(3):277-298, 1998.
[5] Shai Ben-David, Alon Itai, and Eyal Kushilevitz. Learning by distances. Information and Computation, 1 1172))240-250, March 1995.
[6] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[7] Nader H Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2(Feb):359 3355,9999,-9 2002.
[8] Yihua Chen, Eric K Garcia, Maya R Gupta, Ali Rahimi, and Luca Cazzanti. Similarity-based classification; Concepts and algorithms. Journal of Machine Learning Research, 10(3), 2009.
[9] Thomas M Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991.
[10] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34:26168 68 26122182 2021.
[11] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826.2836. PMLR, 2021.
[12] Vitaly Feldman. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer and System Sciences, 1444) 2012.
[13] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2): 1-37, 2017.
10

---

[14] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference Machine Learning, pages 3199-3210. PMLR, 2020.
[15] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
[16] David Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-115 118, 1975.
[17] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[18] Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, pages 423-440, 2002.
[19] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
[20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[21] Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint arXiv:2104.06977 2021.
[22] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Newral Information Processing Systems, 27, 2014.
[23] Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiw:2004.00055 00557, 2020.
[24] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[25] Balázs Szörényi. Characterizing statistical query learning: simplified notions and proofs. In International Conference on Algorithmic Learning Theory, pages 186-200. Springer, 2009.
[26] P Turán. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48:436 452, 1941.
[27] Roman Vershynin. High-dimenssioal probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[28] Vladimir Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 16(2):153-173, 1998.
(29) Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135, 2020.
[30] Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. Advances Neural Information Processing Systems, 26, 2013.
[31] Ke Yang. New lower bounds for statistical query learning. Journal of Computer and System Sciences, 70(4):485-50) 4099 2005.

---

A Missing proofs of Section
A.1 Analysis of Least Squares Algorithms (Algorithms) [
Our analysis relies the following variant of Freedman's inequality 16] (see Agarwal et al. Lemma 9] and Beygelzimer et al. [6 Theorem ID.
Lemma 16 (Simplified Freedman's 's inequality). Let R.> > 0 and let Xi...., Xn be sequence of real-
valued random variables, such that for all i E [m]] it holds that X; S R and [[X; X (I..... X;-1] = For any 8 (0, 1), and 7 (0, R),, with probability at least 1
1 ln(1/6)
Σ 1=1
E
Σ 1=1
B|X? X 1x.1Ix,...,........
(5)
Next we define an e-cover of a set Z. that will be used in the bound of Theorem 17
Definition (c-cover). Let to be the pseudometric over the set 2 defined, for any 21, 22 E 2, as
(b2,, = =sup plz (2)) - plz 122) =EZ
(6)
We say a set N C Z is an 6-cover of 2 with respect to 1/ for every 2 E 2 there exists some 2' E N such that (> 2/)
We denote by (2, the minimum cardinality of any (-cover of 2.
For example, in the case of linear bandits (see Section 5.2) when Z = t and Poandits it can be shown that (2 <) upper bounded by the Eg co-crvng number of the n-dimensiooal unit ball. This is because for any 2, 21, E θ x A.
|p( x1) - p(= 22) = (0, a) (02, = |00 - 02|||a|| s [|0 - -221--
The bound on N2 ,e) now follows because the fz-covering number of the unit ball with radius is ((3/)))) (see, for example, Lemma D.1 of Du et al.
We next show that Algorithm [ satisfies the decaying estimation error property with Cr.s that scales logarithmically with the covering number with respect to V.
Theorem 17 (LS guarantee). Consider the setting from Section 2 where the learner sequentially issues the queries Z1,.... 2T and receives responses r1,..., TT. Assume there
such that Te Rfr =,]] S 3 for all i, and B' 2 2,3 such that for all z, z', |o(=|=²) p(= =0) < B¹ Let Z be a set of alternatives such that x" E Z and let 2, be defined as the least squares optimizer.
Σ ((((a12)-1))
2 argmin =E
Then, for any sequence of queries 21, 21...., 28 E 2 (possibly equal to 2,, br), have with probability - 6, for all E [T] simultaneously.
Σ (0=x11)) - -p(z
-(==1=))) 1=))²² < Cr,5, and
x' x' fef=e z: -
p(zz (2l12)
s <TT }
1=1
where Cr,5 = 1633' In (2,
0)).
Proof. For i 1,..., T, let h, (21, (21, Fi...., T3-,, denote the history of interaction up to the query 2;, but excluding the response r,, and let & = r; - p(z: =²). In the interactive estimation setting, then have EE[E h:] = 0, and by the lemma assumption, EE{? ha] < ,
Since &, is the minimizer of the least squares loss up to time we have
(p(z (x) -r)) <
p(=: 22*) -3)
12

---

which can be rewritten, substituting r; = =p(zs 2²)) + E1, as
2 Σ (p(z) 12)- x²) - [s)
1-1
-
Therefore, by re-arranging terms, we get
Σ
(ptz p 2))
p(zs 12') 2
1-1 Σ E p(2s (2) - p(zs
-p(z) (0/2il=²)) 2*).
==1
Set 61 = B/T, and let N be a minimal éi-cover of 2 with respect to the pseudometric el (see Eq. 6 Furthermore, let 2f E N be an element of this cover that is éi-close to &n (with respect to ()). Then,
Σ p((z ax) - p(z) 12)) S
S: (p(2z) (2) - p(zz 1²*)
1-1 & (p(z) &t) - p(2z (2)
+ p(zz | - p(zs x²))
< 21 + 2 Σ & (p(=: { - p(zz ppzz x*));
(8)
where the first inequality follows from Eq. 77. and the last inequality follows because |&:l S B and of is é--close to &,
Now, for any = N and E [T], define
KF = E, (p(2) (2) - p(z)) x²)))
Since B[E; h,] = O, we have, for any fixed & E N, B[K hj] = 0. This means that for any fixed
= E N, Ki Kf...,, Kj is martingale difference sequence. By the lemma assumptions, |K?] S 38 Also,
B[(K))* h.] < B' (plz) 1) p(z: =²))² 11: 8² (p(zz =) p(zs 2 x²))²²
6 Thus, by Freedman's inequality (Lemma 16 with ' = 1/(433') and 8' = TIN we obtain that for any fixed 2 N and t E [T), with probability at least - 8¹,
- -(==)===)))))) Σ E -
t-1
1
82 (p(z)) 2)) - -p(z) 12*)) +433' In
(TINI)
-
4,30
8
[-1
T[N
Σ
p(zz 2) -))pp(z)>>))) 2()) + 433' In
(10)
43
Taking union bound over all 2 N and /. E [7]. we obtain that Eq. TOp holds with probability
least 1 - 5 simultancously for all 2 E N and E [7]. Henceforth, we assume that we are in the event
when Eq. (IO) holds for all N and [T].
Applying the bound of Eq. (T)p with z = Ef to the sum on the right-hand side of Eq. ( then yields
Σ (p(z)) 1 Ex) plzz p(zz)=z)) 1=²)² < 21,311 +
B
p(=s ((==;12)) p(zz 25)
2
(1I)
TIN)
+ +8,38' In
Using the inequality (a + b)2 < 2a² + 2b2, which holds for any a, b R. and the fact that 2f and & are é el-close, we obtain, for every = l,...,
(p(za (5) p(z: (z)))
2 = (letz) ( p( [x)] + [p(2s (2) p(z; 1 =²)))²
13

---

< 26 + +((p(2s 12)) - &c))
Plugging this into the right-hand side of Eq. [1] yields
Σ [0< - p(zs 1=)) 2 2 21,311 +
3
1-1
+
Σ
((zz) [2x) - p(zz =0)
3
==1
(TIM)
+ 8333" In
6
t,et
t-1 Σ
< 21BeI +
+
p(zz ε - p(zz | (2))
2
1=1
(TIN))
833' In +
where the last inequality follows by the assumption that 8 2 23. Then, by re-arranging terms and multiplying by 2, we get
((pe) p(zs 12)= S 4tBe1
2t
+ 1638' In
T
3
Recall that set E 3/T, and N is minimal co-er of E, so | N\(,, B/T). Plugging these values in the previous equation, we thus obtain that with probability at least - ó, for all LE (T).
23 Σ (2)))2)) ((<a)~p(s1>>)) o()) S 438' +
TN((2 8
+
1639' In
T
(2,
S 1633''n In
(12)
8
where the last inequality follows because 4 < 161n 2 for T 2 1. Finally, when Eq. 12 holds, we also have
E (p(xx1=)- p(z= ax) < 16,38' In
(2, B,/T))
8
Considering Algorithm I and using Theorem 17 with Za. 2e 2, 8 2 and 3 = 4 then immediately yields the following corollary (a-large self-evaluations follow because & E Za):
Corollary 18. Consider the setting from Section 2 with set of alternatives Z and an evaluation function P. Let o be an optimality level such that N (Za, 4/T) (T() Then Algorithm I has a-large
self-evaluations and satisfies the decaying error property with CT, 55 128 In (2TN (Z.. 8/)
Similarly, Theorem 17 also implies that Algorithm 3 satisfies the decaying error property as well as
a llage self-evaluationn, although a is not known:
Corollary 19. Consider the setting from Section with a set alternatiise Z and an evaluation func- tion p. and assume that (22, 4/T/T))== ( Then Algorithm 3 with R= 128 in (F,N(ZZ//T///// has a" -large self-evaluations and satisfies the decaying error property with Cr. 4R 512 (22TT(2,,
Proof. We apply Theorem 17 with 2 2, B-
and 8 4. Our choice of in Algorithm
coincides with the value of CT.s s appearing in Theorem 17 and therefore the theorem implies that
z" E Z, with probability at least - å for all TT. In that case the queries 2, issued by the
algorithm satisfy p(=,1 =)) 2 p(> |²*) = a² and thus the algorithm has a llarge self-evaluations.
For the second part, the triangle inequality implies that with probability at least for all e [T],
(((s 1=) p(z: a():l
Σ (p(z 12) p( 2 +
Σ (p(= (x) p(=: 21) 2
S VVR+V VR,
where the bound on the first term on the right-hand side follows by Theorem 17 and the bound on the second term by the fact that 2, Z,
D
14

---

A.2 Proof of Theorem !
The theorem follows immediately from Corollary 18 because (2) and c.
1|2a S |2| < oo for any
A.3 Online Regression Oracles
We assume access to an online regression oracle Reg, which solves a regression problem over function class & {Øz (=(=') = p(= z) for all x' E Z; that is, functions @ evaluate in its first argument.
E 2} indexed by E Z, where Φ2 Z + I is defined as
The oracle operates in the following protocol: In each time step, the oracle receives observation Zg. produces a prediction Pe E IR, and finally receives a response 7 and incurs square loss (pr re)² We assume that for any T and sequence of observations and responses (even if generated adaptively), the oracle satisfies the following regret bound:
T
E - rr) t=1
inf (((e sE2 t=1
- -)))) Regret (T),
(13)
where Reg (.) is non-decreasing sublinear function (that typically also depends various properties of p. 2, and the range of responses r₁). For many function classes, there are well well-known constructions of online regression oracles that satisfy Eq. (13) 99 28 [8]. For example, if & is finite, there are oracles with Regret (T) = (I Φl) and for parametric classes, such as linear functions, there are oracles with Regret (T) (d (T/)). More examples can be found in Section 2.2
of Foster and Rakhlin [14].
Algorithm 4 Interactive Estimation via Least Squares
1: Input: online regression oracle Reg, optimality level a.
2: Initialize to arbitrary element of Za.
3: for t = ....T . do
4: Use Reg to predict Pe given the observation 2t.
5: Observe reward r++1 and pass it to Reg.
6: Set 2 1 argmin Σ (p(z p4
zEZ, i=1
7:
end for
We now analyze Algorithm 4 under the assumption of access to an online regression oracle. This algorithm takes as input an online regression oracle Reg. Algorithm 4 can also be modified using the optimistic least squares template of Russo and Van Roy [24] to handle the case when a* unknown. This is done by replacing step of Algorithm with the following two steps:
{ E Z: [(p(z p.)² S R).
Z
1=1
21+1 = argmaa (2)
=E
where R = Rey (T) + 64,3 max (3, 8') In( ln(?) and 3, are defined as in Lemma 20 The results of Lemma (anmam20jjuuiaa justify the validity of these choices (using a similar reasoning as CoroTlar 19 and imply that A Algorithm 4 satisfies the decaying estimation error property (Definition 3). provided that the regression oracle Reg satisfics the regret bound of Eq. [13.
Lemma 20. Consider the setting defined in Section 2 with S a", and assume there are 3.8' 2 0 such that [r- Err, 21]1 8 for all and there is 3' 2 23 s.t. for all z Z and p E l T -p( 2²)] < 3' where Tz C IR is the space of plausible responses of Reg for imput The
sequence of queries 21,..., 2r as defined in Algorithm 4 satisfies with probability at least - ō for all i E [T] simultaneously.
Σ (p(z) 2441) p(z: 1²²))² S Cr. and =² =' == Z, E
Eb(2 (2)2)11) -p)) s Cr,8
where Cr,s &Regret (T) 643 max (3,8 In (?).
15

---

Proof. Let &: ri p(z; 2²). Recall that E/r, 2,] p(z,) 2²) and therefore, by assumption, 15:1 $ 3 for all By definition, the online regression oracle satisfies
(pi ri)² - inf Σ (p(z) 22) rz)² 09²= Regret (t) ZE2
(3)
(o(z) |x*) ri)) + Regret (1)
Σ 2 + Reg (t).
(14)
Inequality (i) holds because 2" E Z. Expanding the LHS,
Σ (p. r:)3 (p: (2.122)) 2E/(pi p(z 2²))) + +
Plugging this back into Eq.
14 and rearranging, we obtain
Σ ( pl 2²))²
26 (p: - p(zi =²)) + Regret (1).
(15)
i=1
For any e [7'] we define:
K; = Ei(P: - p(zs 1²)))
Observe that
E [ fee, pe) O.
Thus Ki,..., Kr is martingale difference sequence. Notice that [Kg] S /33' and that
E B[<?| Pelimil S [ p(= =))) (ze, = B² (ū. p(z: =²))²²
Then, by plugging this into Freedman's 's inequality (Lemma 16 with 17 = min(1182, (13n1)))11/35) and = 8/T, we get that for any fixed / E [T], with probability at least 1 -- 6,
Σ cc p(z: 12)) <
(o= p(z; 12)) + 43 13,38 In
(16)
Plugging Eq. (66 back into Eq. 15) and rearranging terms yields
Στ. p( 2²) < 2Regret (t) + 1633 max 8') In
T
(17)
with probability at least for all / E (T).
8 for all / E (T). Thus we conclude that with probability at least - 8,
2" x f2 =E Za: (p(2)12) pp)²² s C
1=1
By the triangle inequality.
Σ (olz) x**) p(zil Ze+ 1=+1))) <
Σ (p(zs)
-p:)a -
Σ (p p( 1 1))
Ei=1 (p(zi ((zz(2) - ww have
Since by definition 2++1 argmin
Σ (p(=s 20+1) - p:: 2 5
t (plzs |2*) -D.)²
16

---

Substituting back into the triangle inequality above,
Σ (p(z) 1=*) p(==) =x+1)) 5 Σ (plz) =+) -..)2
implying
Σ (p(z 12) p(z; s++1))² S Σ
(p(z) |-- - -p:)?.
i=1
Plugging Eq. 17 on the right-hand side yields
T
Σ (0(2)1=))) p(z: 2++1))² &Regret Rey (1) + 64,3 max max (3,37 In
The result follows by using the monotonicity of Regret (t).
A.4 Proof of Lemma
The proof uses Turán's Theorem 26 a standard result from extremal graph theory that bounds the number of edges of a graph that does not contain a clique of a given size:
Theorem 21 (Turán's 's Theorem). Let G EV be undirected graph without self-loops and whose largest clique is of size at most d. Then
VI2
E
2
We now turn to the proof of Lemma
First note that if e 2 1 + a then no query is c-bad, because S 5-15 S p( 2²*) for every z and therefore the lemma holds. In the remainder of the
5
proof, we assume that 0 < < a. a.
Consider the queries 21..... #т and their corresponding values relative to =", denoted as O p(z)l=*) fort E [T]. A query 2n is e-bad if its corresponding value i is in the interval / a-1,a-e). The proof proceeds by partitioning the interval / into subintervals and separately bounding the number of values D2 in each subinterval.
To define these subintervals, let = =1 +
1 and consider the sequence of suboptimality gaps va
6 E for I,...,h. n + 1, where
1 1
logg
The gaps 6 form increasing sequence e, gc, g'c.",,....
such that the last element satisfies
1 +
En+1 = E²
E = ==1+a
Using these gaps we define intervals 1, = la - Ci+1, a - 44) for i = 1...., n. Since ex+1 2 1 + a, the union I U... ....U,, U., [a En+1, covers the interval I. We bound the number of values et in each interval T,.
p( 1=" E T:). let m, = |Sa], and assume that m, 2 2 (the case m, < will be dealt with later). Furthermore, let c -a-(c- c be the midpoint of the interval I, Since the width of the interval I, is
Let S: be the set of query indices with values in 7, that is S: = (t E [T]
c++1 - (q 1)c, = 4// Vd, we obtain
1(=e -cal 2
(18)
for all E S,.
Let d, d,(2, ot, Ei) be the (non-monotonic) dissimilarity dimension with respect to the subopti- mality gap f,. Since a a" and 6; 2 6, we have S d, d. We construct an upper bound on m,, exploiting the fact that d, is the dissimilarity dimension with respect to e,.
17

---

In the rest of the proof we refer to pair of queries with indices s, E S; such that < t as dissimilar if
|p(zs =x) cs VJ:
This is exactly the property appearing in the definition of the dissimilarity dimension with respect to 6,, and there cannot be more than d3 queries such that every pair is dissimilar (note that all the queries 24 satisfy p( | 2x) 2 a thanks to o-large self-evaluations).
The derivation of the bound on my proceeds in several steps. First, we identify pairs of dissimilar queries and construct a graph where each edge corresponds to a dissimilar pair. Second, we use Turán's Theorem (Theorem 21] to upper bound the number of such pairs, using the fact that the graph cannot contain a clique of size greater than d,. Finally, using the bound on the number of dissimilar pairs, we bound m,-
To start, let & < t2 < ... tm, be the query indices included in S, and let E {2..... m.). Consider a uniform distribution over f E k - 1]. Then by Markov's inequality and the decaying estimation error property, we obtain
(plate | axx) - p( |x1) 2
2
4d
plase | (xxe) - p(2re 1z*))
4e
k
(p(zs) 2(xe -p(zo 1x²)
4d
k:
s=1
CT.8 4d
k 6,
Multiplying by we therefore obtain
{ E St ty and p(2, I 2w) - p(zz |2t)
) 2vd 1
4dCT,5
&
and summing across all is (2, (2,...,,m, m.} then yields
{ s,te S. < t and plzz I 2x) p(zs |z0) 2
4dCr.6
I m
(19)
2/d
E
We next construct an undirected graph without self-loops, Gi = (Vi, E.). The vertex set of the graph V- S,. The edge set defined to be
E,
[t. $} S, < t and p(zs (2)) p(z6 (())
2/d
By comparing with Eq.
19 we obtain
m; m,(m; - 1)
4dCr.6
Eg
mi
(20)
Note that any pair of vertices << connected by an edge corresponds to dissimilar pair of queries:
[p(za 21) - co| S |p(z
2x) - p(2s |=0)| +
1/z.1=") - cil
6
2dd
2vd
< e
vd,
where the first inequality is the triangular inequality, the second inequality follows by combining the definition of E, and Eq. (18). and the final one is from the fact that d, S d. From the definition of the dissimilarity coefficient, the largest clique in G; is of size at most d, Using Turán's 's Theorem, we thus must have
1 1
1 di
m
- - m 2
E. I
<
2
18

---

Combining with the lower bound on E from Eq. (20)
we obtain
m, (m; - 1) 2 Dividing by my multiplying by 2d, and rearranging then yields
4dCT,5
m
m,
&
2
mi 2d (1 +
4dCr, ) Cr.
-
of
We have originally assumed that m, 2 2, but the bound that we have just derived also holds when my (because d 2 1).
To complete the proof suffices to sum up the upper bounds on my across 1, ,,..,,
Sr.
d
-11/9))
e
Cr. S nd +
1
(21)
22
(1//2)))
To bound n, we use the fact that a & 1, the inequality In(1 + x) 2 and the fact that d 2 1: S 1 (2/c)
x
(which holds for x 2 0),
Itr
+ ln(c/c)
S 1 [In(2/e]] va + (Vd+1)ln(2/)
In(1 + Vi
< 2ln + 2wddmm2////e < 2vdln(4/c.
Also,
2
1
1
2
2 3
2
1
1
14
2
14
2
Vd
2
va
Vd
Plugging these back Eq. 21 yields
12 ST,
Σ m. S 25 In(4/)) +
62
completing the proof of the main claim of the lemma. The second claim holds vacuously when T = O, so assume that T 2 If Cr.6 2 In(2)), and using the fact that (In æ) I and 2 < 3 2,
write
16.
24(l2)ddL.
24.2.5
24
2 In(e/) = 2.5 In (166/22)
<
Im(2T) -
2
2
22
which yields the first part the second claim. The second part is immediate by plugging in Cr.8 = in the main claim.
A.5 Useful lemmas
In this subsection we prove two lemmas that will be needed for the proofs of the main results
(Theorems 66 and ( in Appendices A.6 A.7 They both rely on standard technique of bounding
a sum by definite integral:
Proposition 22. Let f IR + R be non-increasing function and T 1. Then
f()) (" f(t)dt.
Proof. The proof is immediate noting that f(t) li= ft)dt.
In the lemmas below we write R4, denote [0, +00).
19

---

Lemma 23. Let q......9 be sequence in R+, and let K R4 + R be hon-increasing function such that for all >
T
x(e) 2²
Σ
(
2 c) =
1=1
Then, for any T 2 O,
T Σ
S TT 2
Proof. First, since we are only concerned with bounding the sum E. 9t. we assume without loss of
generality that the sequence is in descending order, i.e., 91 gr. Then, for any T 2 0.
T
T
T 1 ST)+ Σ al > T) TT +
T
Σ
th -
Σ
n 1 > 7).
(22)
Consider any k such that > T. Since the sequence q1, 91,.... QT is non-increasing, we have
K<
<(gx)
k(T)
h
Σ t=1
1(
9h) 1
q
where the last inequality follows by the monotonicity of This in turn implies that OA S Vatt). Therefore.
T
T 1)
k(T)
Σ
%
>
Σ
(23)
t=1
t=1
By Proposition 22
T
Σ
1
2VT.
(24)
Vt
Combining Eqs.
22
23 and
24
we get
Σ 4 < TT TT 2
which concludes the proof.
Lemma 24. Let >> O, let q1..... be a sequence of reals in [0, a). and let x. R. - R2 be
non-increusing function such that for all a),
T
Σ
1(g 2 c) S x(c) In (
1=1
Then, for any T 2 0.
< TT + a(1 + =([)]] exp (_1 (-x1))
Σ
k(T))
Proof. We follow similar proof strategy in Lemma 23 and start by bounding the sum Σ, 9r. We assume without loss of generality that the sequence is in descending order, i.e., Q1 2 ... 2 fr. Then, for any 2
T
T
T
T
q
q: 1 (gt
ST) +
Σ 9:l >c)
3)
ST Σ (1 >).
(25)
1=1
20

---

Consider any i such that > T. Then
T
(-
1 Σ
2 qx) S (())) In
x(T)
In
==1
where the last inequality follows by the monotonicity of a. and the fact that In(a/ gx) 2 This in turn implies that dk S axepp(
x(r) Therefore,
I
T
9: > r) = Σ
a exp
(26)
1=1
By Proposition 22
T
T (<((T)
Σ
exp
k((T)
I exp (-x(T)
x((T)
-x((T
exp
- exp
<T(T)
t=1
[1 + x(T) exp
(27)
x(T)
Combining Eqs.
26 and 27 get
(-x77)
l q: s TT + a[1 + x<[]]
x(T)]expp
exp
(Tx(T) xx(T)
which concludes the proof.
A.6 Proof of Theorem
Throughout the proof we use the shorthand de = d2( a, 8o == d1/r- The proof proceeds by applying Lemmas 23 and 24 to the bounds the number of bad queries from Lemma Specifically, let q: = [a p( ]]+ denote the suboptimality of each query &t made by the algorithm. Then, for any e > 0, the number of e-bad queries can be written as Σ 1(4 2 e).
First consider the case Cr, In(27). By Lemma with probability least - 6, the number of e-bad queries is at most 36d.-Grr.5 /r. Setting k(E) 36d2 Gr,5. apply Lemma 23 with
t 1/T, to obtain that with probability at least
T
Regret a) S
Σ qi S1+ 12 VCr,T.
If Cr,s 0, then by Lemma the number of e-bad queries is at most 2d. In(4/e). Setting and <(c) 2d we apply Lemma 24 with 1/T, to obtain
1
Regret (T,a) Σ ai 4(1 2) exp
S 114 1.5
2d1.3
completing the proof.
A.7 Proof of Theorem 7
First, we consider the deterministic setting. By Lemma 5 at most 2d Alg are e-bad. Setting T > 2d In(4/e) implies that at least one query is not e-bad. Thus, returning for which the observed reward is the largest guarantees that p(2 2²)) 2 a e, as needed.
In(4/e) of queries issued by
Next, we prove the result for the case Cr,s 2 In(2T). By Lemma 5 with probability at least 1 - 8/2. 16 36d (Cr,5/2) queries that are 3e/4-bad. Setting T' > 64d22((Cr.s/))
there are at most 5e implies that at least half of the queries are not 3e/ Be/4-bad. the remainder the proof, we only consider the high-probabilityy event in which this is the case.
For nn (ogg(4/6) the probability that all n, samples are 3r/ Be/4-aa is at most (1/2) S 6/4.
21

---

For [128 In (88n1/6)/e", by applying Hoeffding's ' inequality and union bound over each of the my rounds we get that with probability most 0/4 there is some index I ni for which Fit - p(=,, =²) s/8.
Overall, with probability least 1 we get that there is least one index j of the n, sampled indices that is not 3e/ 4-bad, and that [it, p x*)1 5 e/8 for all & f= ,..... Therefore.
Fe 2 p(2,, 1²") - c/8 2 -e/4 e/8 a 77/8.
For all indices that are e-bad we have
Fu S p(z)) 22)) c/8 a c/8 7c/8.
Thus, for all of the e-bad queries we have Ft, < Fty. and so Algorithm 2 will not return any of the c-bad queries, because choosing the index with maximum value of ft, In other words, the returned query Sty satisfies
p(213 1=") a-
B Missing proofs of Section
First we discuss the connection between our SQ setting and the SQ model of Kearns [9] We focus on two aspects in which they appear to differ and explain why these models are equivalent.
Correlational vs general statistical queries. The restriction of the SQ model in which the oracle may only output the approximate correlation between query and the target function, termed correlational statistical query (CSQ), was studied by Bshouty and Feldman (7] The CSQ oracle can be viewed providing something akin negative distance between the query and the target. This equivalent to the learning by distances framework of Ben- Ben-David al. (5), who defined their model independently of Kearns [99 Bshouty and Feldman [7] showed that arbitrary statistical query can be answered by asking two SQs that are independent of the target and two CSQs. That is, in the distribution-ddeeeneent learning model (i.e., when the learner has access to the distribution over X),
correlational queries can simulate general queries.
Adversarial vs statistical noise. The setting we consider in this work assumes stochastic query responses, similar to several previous works [33 4 On the other hand, the original SQ model [19 assumed that the query oracle can respond with an adversarial (rather than statistical) noise, up to a pre-specified tolerance parameter T > 0. The previous works have shown that the two noise models
are equivalent 13 31
B.1 Proof of Proposition
We first prove the first inequality of Eq. 3 Let c > and let dso(c). Then there exists sequence h...... ha E H. satisfying both conditions of Definition 4 Let d' be equal to the leftmost expression of Eq. (3). We aim to show dp(e) 2 d'. Note that d' < d.
Let e be the midpoint between Gmin = mimine (hi, 122) and Cmaz maxic (h2 hz). Then e S -e. Moreover, for all A
(12, h1) - Cmaz Cminn
6
2d
dd
where the last inequality follows from our choice of d' (which ensures d' < ))) Thus. har, the first d' elements of the original sequence of hypotheses, satisfy Definition proving the claim.
We prove the first inequality of Eq. (4) in similar way. Let us re-define be equal to the leftmost expression of Eq. (4). As before, d' < d. Then there exists sequence hy...., h4 H. satisfying the conditions Definition [ for some
(4e) and let d'
4e. Then for all i +
(h;, h1) c de < -e, since d 2 2. Moreover, for all i * and i' " + j',
Ja
8c 1 Vd
Kh h₂) (hey, hyy) (14, hT) c c (le, hh
d'
with the last inequality following from our choice of d'. Thus, hı,..., ha, the first d' hypotheses in the original sequence, satisfy Definition
22

---

The second inequality of Eq. 4., now follows from the first inequality of Eq. 33. since if the second inequality of Eq. (4) does not hold then the leftmost expression of Eq. ( must be least dp(e), a contradiction. Likewise, the second inequality of Eq. (3). now follows from the first inequality of Eq. (
B.2 Lower bound setting
Definition 8 (SQ oracle (adversarial)). Let D be the input distribution over the domain X. For tolerance parameter > 0, Oado (r) == O (T) oracle is the oracle that for any query function h E H. returns value Ju- 5, / + T). where μ = Ex- (1(x)h" (x)].
Definition 9 (Sample oracle (statistical)). Let be the input distribution over the domain X. The Sample oracle O OD oracle is the oracle that given any function h E H. takes independent random sample x from D and returns the value e = hh(x)((""" (x)
We will need the following results for our proof. The first is reduction from an adversarial noise oracle to a statistical one. Specifically, consider the learning setting defined Section 2 for a sample oracle O. Let Alg be (possibly randomized) algorithm for that setting. The following theorem shows a simulation of O via Oudy the SQ oracle.
Theorem 25 133 Theorem 3.13). Assume that Alg outputs a e-approximation to ht with probability at least using m samples from O. Then, for any 8' E (0, 1/4), there exists a SQ algorithm Alg' that uses at most m queries to (8d2(82 /m) and outputs an e-approximation to h² with probability at least 8 8'. 8'.
Their result is obtained by simulating Alg using Onde as follows: for any query of Alg to O, the response of Oadv to that query is used as bias for coin flip, which is then given to the learner as the simulated outcome of O. They then prove that the true m samples of O and the simulated coin flips are statistically close by bounding their distributional distance. This implies that the success probability of Alg', the simulated algorithm, is not much worse than that of Alg, the original algorithm.
We note that the result originally stated in [3] differs from Theorem 25 above in two ways. First, reduces to variant of (rde(7) with tolerance r' E [T, /T]. Thus, holds for (adu(7) as well. Second, it is phrased in a more general setting of search problems over distributions, which captures the SQ model, as detailed in [3), Section 6.
The second result that needed for our proof is the following lower bound due to 25
Theorem 26 (25). Theorem 8). Let > O, and let H. S + be hypothesis space with strong
SQ dimension dsq == dimsq (H, 2c) 2 3 (see Definition D. Then for any SQ algorithm Alg using m queries to andv (r) with tolerance т 2 2/ / dss. there exist h* H such that if Alg outputs an c-approximation to ht, then m > dsa /33
B.2.1 Proof of Theorem
Set = 2/3. Let D be a distribution over X. Assume towards contradiction that there exists a learning algorithm Alg such that for any h² H. given oracle access to O = OD and using m s/dso/1 samples from O, the algorithm Alg outputs an e-approximation h" with probability at least 6.
We then apply Theorem 25 for 8' = 5/2 simulate the algorithm using Oude O The
resulting algorithm uses m \/ /dsq/12 12 queries to Oadu (T) for 8/2 //2mm > 4/(3 // dsp >
2/v dsq and has success probability of at least 8 8' =022 1/3. By Theorem 26 we obtain contradiction, as m > d dso/2.
C Missing proofs of Section
C.1 Proof of Theorem
Let = ā, at 3c/2). Note that the eluder dimension is always at least 1, so the theorem trivially holds if d < 9. In the remainder of the proof assume that d 2 10.
From the definition of the monotonic dissimilarity dimension, there exists 2 3r/2 such that d d(Z, a, r). Let (f1, (fa, aa) be a sequence satisfying the dimension conditions for
23

---

We will show that the first [d/9] elements of this sequence also satisfy the conditions of the eluder dimension for some e' E. Specifically, we will show that there is some e' 2 e such that every element aj with v [d/9] in the sequence above is e'-independent of its predecessors. That is, we will show that for every such element 0j. there exists pair of functions f, E F that satisfy
[H(aa)) sc.
yet it also holds that - >(. By definition of the dissimilarity dimension, there exists S a 7 such that for all < j.
- Vd [a(a,) - (((r:::))
T
(28)
Then, by the triangle inequality,
2T
- [ fa+1 - ((lc))cccc ( - c + |53+1 - -cl
(29)
vd
Therefore,
47
(30)
d
and for all j i [d/9] holds that,
E(s(a)) - (3+1( 47
4-1
(31)
Next, recall that for all j S d have fy(a,) 2 a 2 and fs+1(a;) S c Va Thus,
2r
[(a;)) (41) 2Ct- Vd
(32)
3
where the last inequality holds for 10. Overall, Eqs. 31) and (32 then demonstrate that for = 27/3 2 e, the element aj is e' <'-independent of its predecessors, finishing the proof.
C.2 Proof of Theorem 13
Our proof uses the following result ranks of perturbed identity matrices (see 22] Lemma 2.2]):
Lemma 27. Let A E Raxd d be symmetric matrix such that Aa 1 for all and AAy < dd all i j. Then rank(A) > d/2.
j.
The proof begins by constructing matrix M whose entries derived from the evaluation values of elements that satisfy the dimension condition. Then we bound the rank of M from above as well as from below. The lower bound is expressed in terms of the dimension bound is expressed in terms of n. Combining the bounds then yields the result of the theorem.
d, a, E) while the upper
Construction of M. Let (fe,.. a1)...., (fea. az) denote the alternatives that satisfy the dimension conditions, with respect to some value such that c S a - (see Definition I Define M to be the x d matrix with entries My = (0,, ay) c for i, < Note that all diagonal entries of M are at least a c e, and all other entries are in Va Va
Upper bound rank(M), Let K Rdxd be the matrix of inner products, K3j (0,, ay), and let U be the Gram matrix for the set vectors 0 .,..... 0a, the rank most n, because the vectors are of the dimension n (see, e.g., [17 Theorem 7.2. 10)), and K is a submatrix of U, so rank(K) & rank(U) S n. Moreover, M = K cl1T where is the all-ones vector ıdd Therefore, by subadditivity of rank.
(.....9p.
a ......,,,, ag. Then is 2d x 2d matrix of
rank(M) rank(K - c11 rank(K) rank(-c11 11
(33)
24

---

Lower bound on rank(M). Let D E Raxd be the diagonal matrix with entries Dj: = 1/vM, Since Mn have 0 Du S 1/v/. Consider the matrix M' DMD. Then
Pank(M) rank(DMD) = rank(M),
(34)
because the matrix D is non-singular (see 17 Section 0.4.6(b))). Furthermore, matrix M' satisfies Mr = for all and
| = M Dil vc vd
<
vc
vd
for all i + j. Consider the symmetric matrix S = (M' + (M') (M))) Then, we also have Sä = 1 for all i, and [Syl < L/vd for all i j. Thus, by Lemma 27 rank(S) > d/2, Moreover, by the subadditivity of the rank
d/2 rSnk(S) Tran((M/22 /2) rank /2) 2rank(M').
(35)
Combining Eqs.
35
34 and 33 we therefore obtain
d/2 < 2 rank(M') = 2 rank rank(M) < 2n 2m++2 2,
and so d < 4n + 4. Since d is an integer, we must have d S 4n +.
In the special case that a 1, we have (0,, a.) 2 1 for all S d, which is only possible when 0, a, for all < As result, the matrices M and M' are both symmetric, and thus S M' and
d/2 < rank(S) rank(M') rank(M) <n+1,
implying that d S 2n + 1.
C.3 Proof of Theorem [4
Using an existing bound on the eluder dimension for GLM bandits ( (24). Proposition 7), and the fact that our dimension is bounded by the eluder dimension (Theorem the result follows.
C.4 Proof of Theorem 15
Denote = d2 that (a) < (0) 1 b. Let (fo,, 01),.... (fo.,br 02) be sequence of elements satisfying the dimension definition, with respect to a corresponding scalar S - b - Since the evaluation symmetric for ReLU functions, we can view this sequence as a set, and denote U (0..... ......... Oa}. In addition, note that by the dimension definition, for all 0 E U, | = 1.
b, c). Notice that since b < 1, for any 0, a E Bn such that 0 o a it holds
We start by proving an upper bound on d. Assume d 2 9. First, consider the case e S </3. Let Uo be any subset of the unit sphere such that for all 0 + 0' in Un it holds that (0, 0') < b + 2e/3. Observe that for all such 0 f we have fe, (u')= = fe (0) E [0, 2c/3. Thus, we get that d < (Vo].
standard sphere covering argument shows that the size of such a set is upper bounded as follows. The 5-covering number of the unit sphere is at most (3/8)² ([27). Cor. 4.2. Thus, there are at most
(3/0)" points such that each pair of 0' satisfies | 0' 2 or equivalently (0, 0') S 82 82/2. By setting = 22 - 2c/3) we get that (Ub S (3)" I (2/2(6-2013) I (4/ V2)", which
yields the desired bound.
Now, consider the case c <> c/3. In this case, for all i * j. we have that f0, (0,) 2 c Va 2
c- e/3 0, and so (0,,0)) > b. Let é' c b. Thus, it must also hold that, (0, 0,) c/ V for all # j. Note that < 1 - c. Then, by applying Lemma 13 we get that d is upper bounded by 2n + 4. Overall, the bound in the claim holds.
Next, we show lower bound on d dp(2i e, e). by lower bounding the size of the set U defined above. We now apply a sphere packing argument, which shows that there exists such a set with size [U] 2 (1/2c)m/2, 1/2 We follow a similar argument as above. Specifically, the 5 g-packing number of the unit sphere is at most (1/5)" (27), Cor. 43). By plugging 22e, yields the desired bound.
25

---

C.5 Proof of Proposition 12
We start with an auxiliary lemma:
Lemma 28 (dissimilarity subadditivity). Let 21 and Zn be two sets, and let a E R and e > 0. Denote 21 U Z2 and p: 2 be an evaluation function. Then, do(2,a,e) - d (1), a, e) a,,))
and
d, 7 (21 a, (2, c),
Proof. Let :1: S 2 such that there exists e S a- with |(z, - cl S Vd for <
and p(=ilzs) 2 a. Let I,, 12 S [d] be disjoint sets of indices with {zi)ien, C 21 and 12 [d] T1. Consider the sub-sequence ,,,,..., 11 ordered by appearance in ø1, #1,...; Fd elements in /T By definition for all j,
10(ze, cl Vd
Therefore the sequence Re....., 2i,, satisfies |0 (2e, cl s V
for all i < j and therefore
|1 S 4p(21,, a, c). The same logic implies |/2| S dp (22, a, c). To get the monotonic version, note that c- = arg max 20 4, 2, a. a,)),
á,(2, = a,,
d2 a, e²) + d2(2,, (Z1, a, c) a, (2,
where the first inequality is by the first statement of the lemma which was proved above, the next inequality is by definition of the monotonic dimension, and the last inequality follows by e S O
We can now construct the classes that demonstrate the separation of the eluder and dissimilarity dimension.
We consider two overlapping semicircles, indexed by E {0, 1}, and defined as (- } and U1 (cos 2, sin
Un = { (cos
x, sinæ) sinss,ssnz))
x E (0, ().
For each j E {0, 1}, and any N E N and > O, we define the function class
FJ,N. { [vv.s vEC S SCU, (S| = N, N. e
containing functions
if \S,
-((()) (v,a) ifaeC\Ug.
(v.
(a) if
(36)
In words, the functions in the class F,,N,r are linear outside of the semicircle U,. and zero in the semicircle U, except for of size N. where they take any combination of values +e and c. For any E N and 6 > 0, we define the class Fx.. == Uje (0,1) Fj,N.e and show that this class has a constant dissimilarity dimension but its eluder dimension is at least N.
Finally, consider the action set A = C and the function class FN,e defined above. Let ΣN,e FN.e x A, p Poandits and e E (0, 1/2). We how show that dimg(FN..c c) > N, but dz 1, 16. First we prove the following lower bound on the eluder dimension of FJ.N.e-
Lemma 29. The eluder dimension of Fj,N.e satisfies dimg dimg(F (Jj,N,e:&) e) 2 N for all j E (0,1).
Proof. Let a....., ay be arbitrary of points in U, and consider the functions (/)) C Sy. that for all i, i' < N satisfy:
if +
f((a;)
[- if =
26

---

and fa,) = for all i S N. We now show that for all i N, the action is e-independent of a...... a,-1 with respect to F,, S. This holds since ()((a)())))) [N+1(a,)) = 0 while
(f((a)) fN+1(a.)] = 2c > c. This finalizes the proof.
Lemma 30. Denote 2N FN,, x A and let E (0, 1/2. Then, dp(ZN.e: 1, 1, 16.
Proof. Denote by Nj,N.r Fj,N,e A for all E {0, 1}. We start by showing that for all E 1), N,,2, I,e. S 8. Let 21,...; Zd be a maximal sequence certifying the dissimilarity dimension dp(2N.e:1,c) d, ic., it holds that,
(p(z)(z)) cls Vd
for all i < while p(zi(zi) 1.
Since p(z)|22) 2 must be the case that 2, (fv....a.. v2) with V, Ui (since otherwise the self' evaluations would be strictly less than 1). This implies that p(2,|2,) = (v., v2) for all < j. Consequently, the score evaluations of all 21...., 2d are equivalent the score evaluations of the linear problem defined by Vi...., Vd- Thus Theorem [3] implies the maximum length of such
sequence can be of size most 2 2 Finally the sub-additivity of the dissimilarity dimension (see Lemma? 28 implies,
dp(ZN ., 1,c) S Σ d2 1, 16.
Combining the results of Lemmas
and 30 finalizes the proof of Proposition 12
D Multi-Armed Bandits
In this section we explore the dissimilarity dimension of the K-armed bandit problem. In this setting the learner interacts with set of K arms and every step of sequential interaction pulls a, E [K] and receives a reward r2 such that E[rr] = 14, where (aa, is the mean reward of arm a, For simplicity we will assume Haa E [0, 1] for all a [K] and that [rl S 1.
The K-armed bandit problem is an instance structured bandits where A= = [K] and F = =00, 1]K. The dissimilarity dimension of the K K-armed bandit problem satisfies.
Proposition 31. Consider the action set A = [K] and the function class F= [0, 1]Kk as defined above. Let [0, 1] and Z F A. p Pbandits and (0,1/2). Then dz a, s K.
Proof. Let c < a and Z1 E Z with (fr,as) be maximal sequence such that, p(z))z)) 2 a while
| -d 6
Vd
For < j. Substituting the definition of p, this implies fi(a;) 2 for all [K] while (f,( -cl S for all i < j. By definition of c, if d 222 vi
1 < /2 <aaa
e
<a Va
for all i <j
(37)
4'
Let Le - (ar) be the set of actions up to index in the tuple sequence ,,,..., 2z Equation 37 implies that (a) S for all j > i. Since aj satisfies fa(a,) 2 a a- this implies a, g T,- We conclude that a; F aj for all j. Since there are at most K different arm values, this implies d < K.
D.1 Structured Bandits
We will now explain in detail how what Cnborithm[rrducee in the structured bandits setting from Example 2 We write z, = (fr, az) for all E [T]. The large evaluation set Z,, can be reduced to the following set of functions,
F. = (f E Fs max f(a) 2 a).
27

---

Algorithm 5 Interactive Estimation for Structured Bandits
1: Input: action set A, function class F. optimality level a, number of steps T. Compute large- evaluation function-action set Fr {S F s.t. maxacA f(a) a}.
2: for t= 1, 7 do
3: Compute regression function
ft argmin JEF
4: Submit the query ae = a Si(a).
5: Observe reward rı-
6: end for
Since the Poandits function Pbandits (zi[z) independent on for (ff the least squares equation argmin. Ei= p((z 1 =) - r3 reduces to,
f. = argmin JEF.
Σ (s(as) - -
finally, to ensure the action query has self evaluation of at least a, output a, aE Sela).
We will now explain in detail what the Optimistic Interactive Estimation Algorithm reduces to in the structured bandits setting from Example 2
We write 2; (fi, for all i E [T'.
The least squares objective (44 argmin, 2cZ, 2e2, Σ (p(z) (p(z 2) -r:) can be written as,
f. argmin JEF
(f(as) - 2r))
The action component of the element in this objective be ignored since the Prandits evaluation function does not depend on it. The confidence ball 2, 2 Σ (p(s 12) p(zs 12)) <
R
reduces to,
F. -
H [(1a)) s SR
The query can be reduced the action component of 2,,
4: = argmax (aa)
faeFixA
Algorithm summarizes this reduction and corresponds to the standard optimistic least squares for sturctured bandit problems from (24).
28

---

Algorithm 6 Optimistic Interactive Estimation for Structured Bandits
1: Input: action set A. function class F, confidence-sel radius R. number of steps T.
2: for = I,..., T do
3: Compute confidence set
ft = argmin TEF (f(a;) ri:)
F FEF: Σ -f((a)- - fila)) sRj.
4: Submit the query a, argmax XA f(a).
5: Observe reward r;-
6:
end for
29


Reviews:
[{"review_id": "Wa1DjOBiEF", "reviewer": "Reviewer_Yyus", "summary": "This paper presents a novel unified framework for interactive estimation. The framework involves a learner making repeated queries to the environment and observing rewards that correspond to the similarity between the query and an unknown target. The algorithm then uses these observed signals to estimate the target. This general framework for interactive learning is connected to two instantiations of learning models: the SQ model and structured bandits, which are studied in this paper. Additionally, a new combinatorial dimension is proposed to measure the difficulty of learning, and it is used to offer standard analysis to achieve tighter regret bounds.", "questions": "1. Why do we need a new dissimilarity measure and the intuition behind it? I am curious about the difference between it and typical approach as dissimilarity measurement.\n\n2. Since this framework claims to be unified to many settings, is there any experiment we can validate its universal feature?", "limitations": "The paper introduces a unified framework for interactive learning that has the potential to be applied in various scenarios. It also establishes connections with two classical models to demonstrate its impact and applicability. The completeness of the framework can be further enhanced through additional empirical experiments.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has several notable strengths. It proposes a new unified framework for interactive estimation and a novel dimension called dissimilarity dimension to measure hardness. It connects two classical frameworks and offers the analysis with them, then finds with their proposed dimension, tighter regret bound can be achieved. Furthermore, it shows another possible to rely on the proposed dissimilarity measure.", "weaknesses": "Here are some potential improvements to the original content:\n\n1. The writing sometimes is too abstract to understand the concept (Introduction) and hard to follow (Section 3 Algorithm). It can be beneficial if more explanation and practical settings are provided.\n\n2. The completeness of the framework can be further enhanced through additional empirical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their overall feedback and suggestions.\n- “Dissimilarity measure” - To clarify, it is not our goal to quantify dissimilarity. Instead, our goal is to quantify learning complexity. As in similar approaches for characterizing learnability (e.g., the classical VC dimension for PAC learning, the Littlestone dimension for online learning, etc.), we introduce a new dimension that will quantify learnability in settings of interactive estimation, such as bandits and SQ. Only the *name* of the dimension is dissimilarity, chosen merely as an intuition for its definition.\n- “Experiments” - we emphasize that our main contribution is the theoretical framework  characterizing learning complexity for interactive learning settings. While there is an algorithmic aspect to our work, it is not the primary focus of the paper. The proposed algorithm is, in fact, an abstraction of existing algorithms for well-studied specific settings, such as multi-armed bandits (see Appendix D for details). We believe that the real significance of our work lies in the conceptual unification of classically studied learning settings. Thus, it provides a new analytical perspective for various learning scenarios. Notably, our approach yields an improved analysis of existing algorithmic approaches in bandit learning.\n"}, {"review_id": "8Bdl6rjWtn", "reviewer": "Reviewer_rc2q", "summary": "The paper introduces a learning model where an unknown target exists, and in each round, the learner selects a choice and receives a stochastic feedback indicating the similarity between the choice and the target. The objectives examined involve minimizing regret or providing a PAC-style guarantee, ensuring that a choice with approximately maximum similarity to the goal is returned with high probability. This model encompasses both bandits and correlational statistical query algorithms.\n\nThe paper introduces the concept of \"dissimilarity dimension\", a combinatorial measure that captures the learnability within the model. It proves that the dissimilarity dimension implies learnability and can be achieved by any algorithm satisfying two properties: (i) selecting choices with high similarity to themselves and (ii) improving the quality of reward estimates over time. The paper presents a simple algorithm that satisfies these properties, demonstrating that it achieves bounded regret and a PAC generalization guarantee.\n\nIn terms of the connection to the statistical query (SQ) model, the paper establishes that the dissimilarity dimension is polynomially related (both in upper and lower bounds) to the “strong SQ dimension”. Additionally, regarding the connection to bandits, the paper demonstrates that the dissimilarity dimension is upper bounded by the eluder dimension, which is commonly used in bandit problem literature. The paper provides concrete examples of bounding the dissimilarity dimension for bandit problems and illustrates cases where the dissimilarity dimension is significantly smaller than the eluder dimension.\n", "questions": "I was under the impression that the results in Szörényi 2009 hold for real-valued hypotheses as well. Is there a particular reason why Section 4 restricts to binary classifiers? ", "limitations": "Addressed.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper introduces a novel learning protocol and presents a combinatorial dimension that captures learnability. Furthermore, it establishes connections between this dimension and two extensively studied learning models. The fact that the proposed dimension can be much smaller than the existing eluder dimension is particularly interesting and perhaps surprising result. The work is original and novel, and I would be happy to recommend acceptance.", "weaknesses": "I do not see any strong weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their overall feedback and suggestions.\n- “Szörényi 2009 - real-valued functions?” - Perhaps we are missing something, but it seems that in the Preliminaries section of [25], Szörényi defines a “concept” to always be a mapping from the domain to binary labels {-1, 1}. The proof he gives on the upper bound of the Strong-SQ Dimension is also relying on that assumption. \n- In addition, as far as we know, standard SQ models only deal with binary labeled hypotheses (see survey [23]). In another extension of the classic model to distribution learning, the queries themselves remain binary (e.g Definition 26 in [23]), leading to 0/1-loss instead of other losses for real-valued hypotheses. In contrast, our framework encompasses real-valued hypotheses learning, akin to linear bandit learning, as suggested by our model.\n"}, {"review_id": "yVd5AvtXaO", "reviewer": "Reviewer_RZw8", "summary": "In this work the authors introduce a framework for interactive estimation, where the learner interacts with some oracle that provides information in the following way: the learner submits a query $z$ and the oracle returns a stochastic reward whose mean is given by a measure of dissimilarity between the query and the ground truth. The main benchmark they care about is the regret guarantees that the learner can achieve. The authors propose a dimension which they call the dissimilarity dimension whose finiteness provides a sufficient condition for learnability in this model. They also propose an algorithm based on the least-squares method that achieves sublinear regret when the dissimilarity dimension is finite. Then, they also describe an online-to-batch conversion that can be used to establish learning guarantees in the offline setting. Moreover, they show how their framework can be instantiated to capture the SQ learning setting and the structured bandit setting. Finally, they illustrate learning tasks for which their approach yields sharper bounds than the state of the art.", "questions": "* What is the intuition behind the scaling of the distance in definition 1 by $\\sqrt{d}$?\n* The example in Proposition 12 is certainly interesting, but are you aware of some more \"natural\" settings where the dissimilarity dimension can be finite whereas the eluder dimension is infinite?\n* Can you derive logarithmic regret bounds that depend on some notion of suboptimality gap? For instance, in the context of bandits that would be the gap between the reward of the best arm and the second best arm.\n* Can the results be extended to contextual bandits and RL? A long line of work has established strong connections between the eluder dimension and regret bounds in various RL settings.", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The authors are studying fundamental learning problems and any new perspectives which lead to better results in this line of work should be welcome.\n* The dissimilarity dimension can be viewed as a more localized version of the eluder dimension, which as the authors show, can lead to better bounds than the latter.\n* It is always interesting to try to unify settings, but I have some doubts about this unification (see Weaknesses/Questions).\n* Even though the techniques build upon the prior work, they are not trivial.\n* This dimension could have applications in other settings as well.\n* The paper is well-written and easy to follow, I particularly enjoyed the comparison with the eluder dimension and the explanation about the improvement that the dissimilarity dimension yields.", "weaknesses": "* My main concern is that the unification that the authors propose under this framework feels a bit forced and not very natural. In particular, in the model the authors propose the learner queries a point $z_t$ in every round $t$ and gets a stochastic reward whose mean is $\\rho(z_t|z^\\star)$, where $z^\\star$ is the ground truth and $\\rho$ can be thought of as a dissimilarity measure. In order to get the results in the bandit setting, they let $z = (a, f)$, where $a$ is some arm and $f$ is some reward function that maps arms to rewards. This does not feel very natural because the traditional way to think of this setting is that the learner queries arms, and not arms and functions. Moreover, the way the distance function is defined is $\\rho_{bandits}((f,a)|(f^\\star,a^\\star)) = f^\\star(a)$, so we can see that both $a^\\star, f$ do not affect its value. It seems as if it was defined this way in order to make the definition of the dissimilarity measure work, but it does not exactly convey the message it was supposed to. Am I missing something?\n* Line 50: \"Largely characterizes learnability in our setting\". This is a bit vague and inaccurate. I don't understand what it means for a dimension to \"largely characterize\" learnability, since it either characterizes it or it doesn't. What you have shown is that finite dissimilarity dimension implies learnability, and that there are instances with infinite such dimension that are not learnable. However, there could be  problems whose dissimilarity dimension is infinite, by they are still learnable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their overall feedback and suggestions.\n\n- “My main concern… not very natural. …” - Note that we are *not* suggesting a new protocol for bandit learning. Instead, we are presenting a reduction from bandit learning to our setting, and using that to obtain a tighter analysis of optimistic algorithms for bandits.\nAlthough the protocol where the learner submits pairs (f,a) seems more complicated than the standard bandits protocol, we believe that it is a fairly natural fit for many algorithms for realizable bandits. Such algorithms often keep track of a version space (set of functions f consistent with data), and so at each point of interaction, there is an implicit f_t that is associated with a_t produced at that time. Our protocol is just making this f_t explicit. We will add discussion of this intuition to the paper.\n- “Largely captures” - We agree with the reviewer. We will clarify that we show a general upper bound as well as lower bounds for certain instances, though not a complete characterization. \n- “​​intuition behind … sqrt(d) “ - This is a great question. The sqrt(d) factor simplifies the comparison between the dissimilarity dimension and eluder dimension (e.g. Thm. 11 and Prop. 12). However, it is possible to replace sqrt(d) by a general growth function g(d) and then state the bounds in terms of the function g. We have not been able to take advantage of that generality, but we will mention it in the paper (and leave open for future research).\n- “Example in Proposition 12” - The key aspect of the example is the fact that the function class is simple near the optimal action, but can be complicated far from it. We expect this to occur in a wide range of cases. As a simple example, consider non-zero linear functions on the [0,1] interval. Clearly the optimal “arm” would always be on the boundary, either 0 or 1. Even in this simple case we can “inject” as many bad points as we want into the linear functions some distance away from the optimum. This will “fool” the eluder dimension which can be arbitrarily large, but the dissimilarity dimension will remain constant. The choice of the circle example in proposition 12 demonstrates this happens even when all arms are optimal for some function. \n- “suboptimality gap” + “contextual bandits and RL”  - Both of the last questions posed by the reviewer are very interesting ideas that are beyond the scope of this work, and could be explored in future research.\n"}, {"review_id": "nfDpBQ4ZFi", "reviewer": "Reviewer_YF8R", "summary": "This paper studies a general interactive learning setting, which is termed \"interactive estimation\". In this model, we are given a set of alternatives, which contains the target. At each step, the learner can choose an alternative and receive the similarity of this alternative with the target. Based on this input, the goal is to get as close as possible to the target. The authors then demonstrate that many well studied settings are special cases of this general framework, including structured bandits and SQ learning. Then, they introduce a novel combinatorial parameter which they call \"dissimilarity dimension\". They prove that a general algorithm which, under reasonable assumptions, has regret that is bounded by a polynomial of the dissimilarity dimension. Furthermore, they show that the dissimilarity dimension is polynomially related to the strong SQ dimension, which automatically gives lower bounds in the sample complexity in terms of the dissimilarity dimension. Lastly, they prove that the dissimilarity dimension is upper bounded by the Eluder dimension and give concrete examples where the gap between the two is quite wide, which yields improved regret analysis for some bandit settings. ", "questions": "-One question, which is also briefly discussed by the authors, involves the computational complexity of the proposed algorithms. In particular, are there some interesting conditions for the similarity measure $\\rho$, under which the least squares optimization of Algorithm 1 can be implemented in polynomial time? \n-It is implicitly assumed that for any given $z_1,z_2 \\in \\mathcal{Z}$, the algorithm can compute $\\rho(z_1|z_2)$. This is certainly the case in the specific settings of SQ learning and structured bandits, which are studied in the paper, but one could imagine situations where that computation is not possible. Would it be possible to impose some conditions on $\\rho$ which still enable learning of the target, without having access to an evaluation oracle for $\\rho$?", "limitations": "Yes, the limitations have been adequately addressed. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, the contributions of this paper are novel and highly relevant for the learning theory community.\nIn terms of results, both definitions of the interactive estimation setting and the dissimilarity dimension are valuable contributions of this work. It is interesting that one can define such a general setting that encompasses various seemingly unrelated problems and still provide a meaningful combinatorial measure of complexity that characterizes learnability under general conditions. The fact that studying the dissimilarity dimension results in tightening various existing results about specific bandit settings is also an important feature of this work, and it seems to open up unexplored directions of research in this well-established field. Another important aspect of this work is that it provides an algorithmic template, which can be instantiated using various algorithms that exist in the literature.\nOn the technical side, the main proofs contain novel and non-trivial ideas, such as the idea of using Turan's Theorem to bound the number of bad queries in terms of the dissimilarity dimension in Lemma 5. \nIn terms of presentation, the paper is very well written, with all key ideas explained clearly and succinctly. It is also nice that the authors try to give intuition for the important ideas that are involved in proving the Theorems, such as the intuitive reason for why the dissimilarity dimension is \"tighter\" than the Eluder dimension (before Proposition 12). ", "weaknesses": "The main weakness in terms of results is the decaying estimation assumption, which is crucial in order for Algorithm 1 to work. The authors provide several alternative assumptions which imply the decaying estimation, such as the existence of an online regression oracle with sublinear regret, or bounded covering numbers for the set of alternatives. While these are reasonable assumptions that have been used in many settings in prior work, it would be interesting to see whether they can be relaxed, or whether they are somehow related to the assumption of boundedness of the dissimilarity dimension. Right now there is no discussion in the paper about that relation. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their overall feedback and suggestions.\n- “Decaying estimation” - First, we note that the analysis of the eluder dimension [24] exhibits a similar dependence: their upper bound relies on both the eluder dimension and the log of the covering number. As the reviewer points out, we also offer various alternative assumptions that imply the decaying estimation property. Nonetheless, we do not dismiss the possibility that the boundedness of the dissimilarity dimension could potentially relax the need for such additional assumptions. We leave this question as an interesting future work. \n- The case that rho cannot be computed is an interesting setting to be considered. In this case, the learner cannot access the value of rho, and thus cannot directly exploit the connections (or “dissimilarity”) between different functions in the functions class, as we do in our framework. It seems to be akin to zeroth-order optimization. Although it is beyond the scope of this work, it is an interesting problem to study within the interactive estimation framework. \n"}]

Author rebuttal:

Meta-review: The authors consider an abstract problem of interactive estimation of a target, where the learner can query the similarity of a point to the target. The authors propose a new dimension called the "dissimilarity dimension", and show its boundedness is sufficient for learning in this model. The authors claim that their framework subsumes/unifies the statistical-query learning model and learning structured bandits.

The reviewers were generally positive about the paper and its significant theoretical contributions. One of the main concerns was that the claim that the proposed dimension "largely characterizes" learnability is not substantiated. The authors agree with this, and are expected to update the paper/abstract for the camera ready.

I recommend acceptance.
Decision: Accept (poster)