Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
Authors: Benjamin Schiffer
Mark Sellke
Venue: NeurIPS 2025 spotlight ()
Keywords: Multi-armed bandits
Bayesian Incentive Compatible
Exploration
Primary area: theory

Abstract: In the incentivized exploration model, a principal aims to explore and learn over time by interacting with a sequence of self-interested agents. It has been recently understood that the main challenge in designing incentive-compatible algorithms for this problem is to gather a moderate amount of initial data, after which one can obtain near-optimal regret via posterior sampling. With high-dimensional contexts, however, this \emph{initial exploration} phase requires exponential sample complexity in some cases, which prevents efficient learning unless initial data can be acquired exogenously. We show that these barriers to exploration disappear under mild geometric conditions on the set of available actions, in which case incentive-compatibility does not preclude regret-optimality. Namely, we consider the linear bandit model with actions in the Euclidean unit ball, and give an incentive-compatible exploration algorithm with sample complexity that scales polynomially with the dimension and other parameters.

Geometry Meets Incentives: Sample-Eficient Incentivized Exploration with Linear Contexts
Benjamin Schiffer Department of Statistics Harvard University
Mark Sellke
Department of Statistics
Harvard University
Oxford St bschiffer10g harvard.
Oxford St msellke@fan as www.aaardd.... edu
Abstract
In the incentivized exploration model, principal aims to explore and learn over time by interacting with sequence of self-interested agents. has been recently understood that the main challenge in designing incentive-compatible algorithms for this problem to gather a moderate amount of initial data, after which one can obtain near-optimal regret via posterior sampling. With high-dimensional contexts, however, this initial exploration phase requires exponential sample com- plexity in some cases, which prevents efficient learning unless initial data be acquired exogenously. We show that these barriers to exploration disappear under mild geometric conditions on the set of available actions, in which case aicentive-compatbbee does not preclude regret-optimality. Namely, we consider the linear bandit model with actions in the Euclidean unit ball, and give incentive- compatible exploration algorithm with sample complexity that scales polynomially with the dimension and other parameters.
1 Introduction
The exploration/exploiiatioon trade-off is fundamental to online decision making, This trade-off is classically exemplified by the multi-armed bandit problem, where single agent chooses actions sequentially and learns to improve over time. In this setting, the agent has clear justification for early exploration because they can reap future rewards by exploiting the knowledge gained by exploration. But what if agents are unable reap these future rewards, and so each decision must be justifiable on its own terms without taking into account future rewards? This may occur when actions are recommendations made to different agents by a central platform based on user feedback, as in e-commerce, traffic routing, movies, restaurants, etc. In these settings, agents may have prior for the rewards of the actions in addition to the recommendation made by the platform. Therefore, while platform makes recommendations with the goal of learning over time, individual myopic agents will decline to follow any recommendations which seem suboptimal based on their individual priors.
The incentivized exploration problem was introduced in Kremer et [2014] Che and Hörner [2018) to understand this fundamental tension, and extends the well-studied problem of Bayesian Persuasion information design Bergemann and Morris [2019] Kamenical [2019]. The model adopted in these early works consists of finite set of actions, each with a (publicly shared) Bayesian prior distribution rewards. A sequence of agents arrives one by one, and each agent is recommended an action made using (publicly known)
by central planner. The central planner's 's recommendations randomized algorithm, and the agents are assumed to selfish and rational, aiming only to maximize their own expected reward. Given the planner's recommendation, each agent computes and chooses the posterior-optimal action (using Bayes' rule). As observed in the original works, thanks to the revelation principle of Myerson 1986), the latter step is equivalent assuming that the planner's recommendations are Bayesian dicentive-compatiiee (BIC) so that rational agents will always follow the recommendations (at least under the assumption of agent homogeneity).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Initially, most work on incentivized exploration dealt with small finite sets of actions Mansour et al. 2020 2022, exploring economic aspects of the problem such as exogenous payments for exploration
Frazier et al. [2014. Kannan et al. [2017], 7], Wang and Huang] [2018), Agrawal and Tulabandhula
[2020], Wang et al. [002]] partial data disclosure Immorlica et al. [2020]. and agent heterogeneity
Immorlica et al. 2019]. See also the surveys [Slivkins, 2019, Chapter 11] and (Immorlica et al., 2023] Chapter 31j. More recently, extensions to combinatorial action sets, multi-stage reinforcement
learning, and linear contexts were also considered in Hu et al. [2022], Simchowitz and Slivkins (0224), Sellke 2023]. In these more complex machine learning settings, a fundamental question is how the regret scales with problem parameters such as the size of the action space.
This quantitative dependence was studied in [Sllke and Slivkins [2023), which provided a new two-stage algorithm. The algorithm first obtains constant number of samples from each arm, and then switches permanently to Thompson sampling. The initial stage enjoys samplc-efficincy thanks to carefully tuned "exponential exploration" strategy, and Thompson sampling is BIC after this constant amount of initial exploration (see Gur et al. (2024) for a more general perspective on the latter property). This yielded polynomial regret dependence on the number of actions and other natural parameters, and ensured the "price of incentivization" in the regret is only additive relative to Thompson sampling, which known to exhibit near-optimal performance Kaufmann et al. (2012), Bubeck and Liu 2013). Agrawal and Goyal 2017], Russo and Van Roy [2014] 2016). Zimmert and Lattimore 2019 Bubeck and Sellke| 2022). Importantly, however, all these results require that the rewards for the actions are independent under the prior.
A natural setting to consider dependent actions is the linear bandit model, where Thompson sampling remains gold-standard algorithm Agrawal and Goyal [2013), Dong and Van Roy (2018.. For this setting, Sellkee| [2023) showed that Thompson sampling is again BIC after an initial data collection stage under mild conditions, but that the sample complexity of collecting initial data can scale exponentially with the dimension. In some applications, using exogenous payments for initial exploration can bypass this exponential barrier, but such workarounds are contingent on problem- specific regulatory and ethical constraints. In our work, we show that the exponential barrier disappears when the action set the d-dimensional unit ball, and we provide an incentive-compatible initial exploration algorithmic with polynomial sample complexity.
1.1 Our Results
We consider a linear bandit problem where the A of possible actions is the d-dimensional unit ball. In this model, the observed reward for agent using action A E A in round is
(+) = (A (4) e") + Wi,
where w; (0, 1) and Wt, TL Wr, for all t # 12. We assume that E" is drawn from known prior distribution μ on Rdd (known both to agents and to the algorithm). As our model and algorithm will be rotationally invariant, we assume for convenience (without loss of generality) that E[e", { = 0 for all i >>> 1 and E[E",) 1] 2 O. Importantly, unlike in Sellke and Slivkins [2023), we do not require that L" is independent of L", , for * j.
At each time step / >1 1, the algorithm recommends an action (() E A to agent I. We study Bayesian Incentive Compatible (BIC) algorithms, which means that the algorithm will make recommendations such that rational expectation mexiriizimmiimiiiinggg. agents will always be incentivized to follow the algorithm's recommendation. More formally, BIC actions can be defined as follows:
Definition 1. An action A (t) at time t is Bayesian Incentive Compatible (BIC) for all A A:
EIKE A) A (0) A]
sup E((e" A') A A].
A'EA
Similarly, a bandit algorithm is BIC if for all E [1, T) the algorithm recommends a BIC action (1).
For the rest of this paper, we will only consider BIC algorithms and rational expectation maximizing agents, which means that the recommended action (() will always be the action chosen by agent t. Our main goal is to develop BIC algorithms that incentivize the agents to explore the entire action space using poly(d) samples. More precisely, given the linear reward structure, we ask our algorithm
expectation-maxiiiznng
to recommend actions A (1) A (T) such that for some (possibly large) constant À >> 0 we have

---

almost surely:
T Σ 1)A = AI.
(1)
1=1
(Here we use the standard notation that M 3 if M is positive semi-definite; is equivalent to all eigenvalues of >i= (A (1))) being at least X.) This was termed X-spectral exploration in Sellke [2023], and shown to imply Thompson Sampling is BIC after time T under mild conditions.
Therefore, our problem can informally be summarized as the following:
Problem 2. In the linear bandit setting, can we design BIC algorithms that guarantee X-spectral exploration of the action space in only polynomial in d number of steps?
For some priors, it is impossible to explore the action space with a BIC algorithm (see e.g. Mansour will require mild non- the prior. Roughly speaking. e" should not be confined to any half-space and should have neither minuscule nor enormous fluctuations in any direction.
ct al. 2020, Section 4] or [Sellke and Slivkins 2023] Section 8)). Thus we
degeneracy assumptions
Assumption 3. There exist constants Cd, Cd, Cv, K 0 such that:
1. E is not confined to any half-space: minl Pr ((v, 2 ca) 2 Es.
2. e has non-degenerate covariance: min |v|==1 Var((v, Cv-
3. e" is sub-gaussian: max /v|== P(I(v, 2 S 20-2//1 P/K² for all > 0.
The first two conditions above are both necessary in some form; see Appendix B The third is standard condition on the fluctuations of μ.. Our main result is as follows. Theorem 4. Under Assumption E there exists BIC algorithm (Algorithm 7 which almost surely
achieves X-spectral exploration in sample complexity
x Cv +c2 )
d
O(1)
log(1/ca)-
Note that (2) depends polynomially on Cd, Cy but only logarithmically on cg. This is important because in typical high-dimensional settings, éa will be exponentially small in the dimension while the other parameters will not. The next two propositions give illustrative but not exhaustive examples of such nigh-dimensional distributions. In the first, we take μ to be uniform
convex body IC with B, (0) S K C Bj (0) for some 0 < r < 1, and say such f is r-regular. This is the main setting considered in (Sllke ] and as explained in Section [5] combining SSllkee 2023) with our results yields an end-to-end low-regret algorithm which cBBIC (i.e. with c subtracted from the right-hand side in Definition 1 with initial sample complexity poly(d, 1/r, 1/e). (The combination
only satisfies e-BIC because Sellke 2023) only shows Thompson sampling is e-BIC unless actions
well-separated.)
Proposition 5 (Proof in Appendix D. Any r-regular P. satisfies Assumption 3 with cd = r/3 and ca = (r/3)² and c, = 2(r /d²) and K = 1.25.
The second example consists of log-concave distributions (e.g. Gaussians). We say a density dp(i) x dv is a-log-concave and (3-log-mmooth for 0 < a < if
-BIa = V²V(x) -ala, Vx E IRd.
Proposition 6 (Proof in Appendix M.. Let μ be cul-tog-concave and Bd-log--smood with mode x"
_2 120-2 for J = + + Vod + Ca and satisfying ||x*|| S 7. Then Assumption holds with e 2 (1+J23d)
any > O. Further, we may take Cv = 1 and K = 2( + v ad + (ad) -1/2). Conversely, there
3d
exists such μ with ||x = 0 and (a, B) = (1 in which min =1 Pr ((v, ) 2 0) S e Bid)
We note that if p has mean O, then ||x*| || S a 1/2 so the above results apply (see Fact 27 in the Appendix). In fact when μ has mean 0, one will always have ca 2 22(1) for ca 1 (as noted within the proof of Proposition 6). Proposition 6 rrepresents the typical case in that μ can be "mildly off-centered",, for example by centering around point drawn from μ itself (see again Fact 27
In Appendix B we show tightness of the dependency of Equation 2 on the parameters of Assumption More formally, we prove three lower bounds, one corresponding to each of the parameters ca, Cv. Ed-
3

---

In doing so, we show that there exist instances of the problem such that no algorithm can achieve 1- spectral exploration with fewer than (2(1/z)) samples, 2(1/ cv) samples, and ([(og(1/Ex)) samples. Therefore, we can conclude that Theorem is tight in terms of these three parameters up to polynomial factors. Furthermore, for the distributions discussed in Propositions and [ these results imply a lower bound on the number of samples that is superlinear in d. Whether or not tight lower bounds exist that exactly match the sample complexity in Equation (2 remains an open question.
On the Smoothness of the Action Space in Online Optimization and Learning Our positive results are contrast with [Sellke] 2023, Proposition 3.9], which shows that eR(d) time can be necessary for BIC exploration for r-regular js. We believe that our results are not specific to the unit ball, but that the fundamental distinction between these two examples the smoothness of the action set. In [Sellke] 2023] Proposition 3.9], the action set is non-smooth polytope with corners, and the optimal action under the prior distribution is one of the corners. This means that given a small amount of new information, the posterior-optimal action will not change at all. By contrast our main algorithm crucially relies on expansiveness of the function
G arg max x).
xEA
In setting A is the unit ball and this function is simply E" /|| However expect methods to generalize to other smooth bodies, and plan to pursue this in future work.
It is worth mentioning that the geometry of the action has long been understood to play an important role in high-dimensional learning and optimization. This was exemplified by the interplay between self-concordant barrier functions Nesterov and Nemirovskil [1944] and linear bandits via online stochastic mirror descent Abernethy et al. [2008). Bubeck et al. 22012a b 2018 Bubeck and Eldan [0119] Kerdreux al. [0021b). Geometric properties of the action space are also known to yield acceleration for full-intormation online learning and offline optimization Garber and Hazan
[2015). Huang al. [0117]. Levy and Krause 2019 Kerdreux al. 2021a] Mhammedi [2022].
Molinaro 2023) suchiya and Ito 2024]]
1.2 Additional Notation
We will use the following notation throughout the paper. Unless otherwise specified, ||-Il will refer to the le norm. We will use e; to refer to the ith vector of the standard basis. For a random variable X,
we say that X is --sub-gaussian if P(X 2 t) < 2e 20-22//// ///K? We use the standard fd) = Ogg(d)
(and corresponding ?2) to mean that there exists some constant C' > 0 such that f(d S C g(d) for all sufficiently large d. We often write 82 for æx. T. We also use Ps(u) to represent the projection of the vector u onto the space S.
1.3 Outline
The rest of the paper will be organized as follows. In Section 2, we present sketches of our main algorithms and discuss the three key technical ideas behind the algorithm and analysis. In Section 3 we give the detailed main algorithm, present the two key technical propositions, and formally state our main theorem bounding the sample complexity of the algorithm.
2 Algorithm and Technical Overview
In this section, we present pseudocode for the main algorithm and give informal intuition for the key technical ideas used to show that this algorithm is BIC and satisfies the sample complexity bound of Theorem 4
2.1 Algorithm Sketch
Before presenting the algorithm, we first state Lemmal) 7 which is the key observation used by the algorithm to select BIC actions. Informally, this lemma says that for any ve that is a function of historical actions and rewards and possibly external randomness (but
on future information), the
action A (1) in the direction of E[[" <b is BIC (or any action is BIC if EE["" v5] 0). Thus to prove action A (1) is BIC, it suffices to find such sb that (()) is in the direction of B[e" | vi] whenever Eie" [/] + O.
Lemma 7 (Proof in Appendix D). Suppose that vp is a function of the history before time t and potentially some external independent randomness i.e. (A (1), (1-11) A (t-1) --11),,(())) p(1-1), E).

---

Let v be any vector in R.. Define
BE [ [ I
if i rall + 0
Exploit(1,, v)
otherwise.
Then A Exploit(s), v) is BIC at time t.
presents high-level sketch of the procedure used to prove Theorem 4 The algorithm first uses the prior-based BIC action (e1) for poly(d) steps. In order to explore
Algorithm T together with Algorithms
rest of the action space, Algorithm Truns single loop that repeatedly checks X-spectral exploration has been achieved. If X-spectral exploration has not yet been achieved, then Algorithm| | uses the subroutine InitialExploration to find BIC action a that has magnitude at least (Eaa) when projected onto the space of not-yet-suuficiently explored actions. Algorithm [ then gives a as input to the subroutine ExponentialGrowwth. ExponentialGrowwth returns another BIC action that has at least twice large of magnitude when projected onto the not-yet-sufficee space of actions. Algorithm repeaeedly passes the action a through ExponentialGrowthh until the BIC action a has magnitude of at least VÁ when projected onto the space of sot-yet-sufficienly explored actions. Algorithm I then uses this action for poly(d) steps. If X-spectral exploration has still not been achieved, then Algorithm| [ a new direction by repeating the process of calling InitialExploration followed by repeated calls to ExponentialGtowth. In Sections 2.2 and 2.3 discuss the main intuition the subroutines InitialExploration and ExponentialGrowth respectively.
cxplored
Algorithm 1 BIC Exploration Pseudocode
1: Set A (1) e; for poly(d) steps
2: while >-spectral exploration has yet been achieved do
3: S' + space of actions that have already been sufficiently explored
4: < InitialExploration())
BIC-vector with maaa)mmag when projected onto StL
5: while magnitude of when projected onto S less than vÀ do
6: f- ExponentialGrowthhaa
new BIC-vector with double the magnitude when
projected onto S
7: Set A (f) for poly(d) steps
Algorithm 2 InitialExploration Pscudocode
1: M Σ t-1 (A))
2: W Wiz <- orthonormal eigenvectors of M with corresponding eigenvalues greater than À
3: S Span( Wi:-.. W:.) :e.)
Space of already-sufficiently explored actions
4: 0i < empirical estimate of (E", w;) for igri lx
5: <- E[e" [
6: f + function of z such that [z)] = 0 and f(z) E [[(ea), 1].
7: < [Bernouli(ff())) 1}
8: Set A (4) Exploit(1:; v) for S+ (1) explores direction with probability (z)
9: r (1) if explored and otherwise r + 10,
10: return Exploit(sign(().)))
where is in S
Algorithm 3 ExponentialGrowwh Pseudocode
1: S space of actions that have already been sufficiently explored
2: Set A (+) = a for poly(d) steps to observe a set of rewards (r-(t))
3: + average of rewards from the component of projected onto the space of not-yet-sufficiently
explored actions 1)
4: return Exploit(signi) (R)ign(R).v
where v is in S
2.2 Initial Exploration
The goal of the InitialExploration routine (Algorithm 2 is find BIC action that has sufficient magnitude when projected onto the not-yet--sufficienty explored space of actions S-. To do this,
5

---

first design an event E' based on the historical actions and rewards H, and external randommess such that P(E H 2 ((ez)) for all histories H, and such that conditional on E. E" has expectation when projected onto any direction in S. We then choose the BIC action A in Line & that A explores 8- whenever event E holds. More concretely, the second condition on E implies that the action A = Exploit(1 (1g v) for any V E 5- will satisfy A E 5- whenever event E holds, and A is BIC by Lemma Using this BIC action on Line 8 therefore explores S whenever event E holds. We define the signal r as the reward at time é if event E holds and otherwise as independent N (O, 1) noise. We next show that, conditional on the sign of the expectation of l always has sufficient magnitude when projected onto 5 (see Lemma [4). This implies that for any the action Exploil(sign(11) v) will have sufficient magnitude when projected onto St desired. Therefore, we can return the action Exploi((*). v), which is BIC by Lemmal)
v E S
All that remains is to define the event E. from the previous paragraph. Formally, we want an event E that is a function of the historical actions and rewards and independent random variable & such that [E, w.) E] = 0 for all i < ex and such that P(E H₂) 2 (2(E)) for all histories H,, The key to constructing E is Lemma g which implies that for any random variable x not confined to any half-spaces, there exists function such that has expectation equal to 0 conditional the event (fermoulliffxx) = =1}
Lemma (Proof Appendix G). Let μ be a probability distribution on I&d with finite first moment and suppose for 0 < S 1/2 we have that
min E [Vv,)
||||==
Then there exists a Borel measurable function f :d
1 with [xx](x)) = 0.
If we knew the exact values of the vector x := ((e", Wi)...., (e", W),)), then we could directly apply Lemma 8 to and use the resulting function f to define the event F = (x))) = 1}. This for i S Ex and that Pr(E H,) = ((aa) for all H, However, we do not know the exact values of (e", w'),,.,.. (f", We,) because we do not know E", and therefore this event is not a function of historical actions and rewards. Instead, we can estimate (L", w.) as ÿs using the historical actions and returns. These estimates will be relatively accurate because these directions are already well-explored. Defining z = E[e" [9]. we show that z also satisfies the assumption of Lemma 8 (Lemma 17]. Therefore, applying Lemma g to z gives a function f such that f(z) 2 M(ea) for all z. z is a function of historical actions and rewards and external randomness desired. Defining the event E (Bernoulli f()) 1}, we have as desired that E((",, w;) E] = 0 for all i I &x and that P(F H₂) = (((c)) for all H,
event E would satisfy the desired property that E((e", w,) E]
2.3 Exponential Growth
The goal of the ExponentialGrowth routine (Algorithm 3) to take BIC action and return new BIC action that has twice as large of a magnitude when projected onto the not not-yye-suuficient) explored space of actions S Using Lemma 7 we will find a signal R such that for any v S the action Exploit (aploittR, R, v) will have twice as large magnitude when projected onto S as a has.
The key intuition is that because the action space is curved, conditioning noisy information about the sign of E" in specific direction will increase the magnitude of the expectation of l projected in that direction. Consider the following simplified example. Suppose that d = 2. Also suppose we already know E", 1, and the goal is to explore L" f²2. Furthermore, assume that the initial BIC action is A (1) shown in the left- most diagram of Figure that has e as the y- y-coordinate. Using this action gives rewards (()), Because we know the value of l', 1, we can remove this component of the reward r()), and we are left with a signal r = cl", + N o²) for some r² > 0. If we take A (++1) to be the unit vector in the direction of EE[e" rl. then we will have that the new y-coordinate is 2c. By Lemma 7 this choice of A (++1) is BIC, which is an important consequence of the curved action space. We then observe y (1+1), and we can repeat this process again to find BIC action A (1+2) that has y-coordinate of 4e. Therefore, in this simplified example we are able exponentially grow the y-coordinate for BIC actions, which is consequence of the curvature of the action space. This process is demonstrated in Figure 0
Equipped with the intuition of the previous paragraph, we now analyze Algorithm 3 Recall that S is the space of actions that have already been sufficiently explored. Algorithm first uses the action A (4) for poly(d) steps. Taking average of the rewards (1)( from these actions gives

---

2'2
E22
E2
A (r+22
(())
A (++1)
1
2c
c E²
l'
Figure I: Diagram illustrating exponentially growing exploration. First, we have a BIC action (1) with y-coordinate c. Using r(1), we design signal conditional on which the expectation of L doubles. Exploit(-) then gives BIC action ((+1) with y-coordinate 2c. Using r((+1), double the conditional expectation of f and get BIC action A with y-coordinate 4e. Increasing the conditional expectation of L" gives a BIC action with larger y-coordinate, and this action's s feedback gives a stronger signal that more rapidly increases the conditional expectation of f This allows us to "bootstrap" an exponentially weak starting signal all the way to constant signal strength without suffering exponential sample complexity.
again
a close estimate of (a, {") Using the previous observed actions and rewards, we can remove the component of (a, ) that comes from a projected onto S. This leaves signal R which is the average of rewards from the component of a projected onto just S-, Using concentration laws for conditional probabilities (Lemmas [3] and T6). we formalize the intuition from the previous paragraph to show that for any E S+, the projection of Exploit RR, v) onto 8- will always have magnitude at least 2Ps4 (a). The action Exploit Rt, v) is BIC by Lemma 7 Therefore, we have found a new BIC action Exploit(R, v) that has twice large magnitude when projected onto S as a.
2.4 Pushing eigenvalues upwards
An important step of the proof of Algorithm I is showing that the while loop will terminate in polynomial time. To show this, we show that the action a used for poly(d) steps at the end of each round of the while loop sufficiently increases the eigenvalues of M : Σt (A() @2
Note that
each time the matrix ((t) increases by a rank-1 update, i.e. ( M0 (A (1+1)
&2 In
order to show that we will eventually achieve X-spectral exploration, we must show that the small cigenvalues of (++1) increase relative to the small eigenvalues of ( after each round of the while loop. Although we do not follow this route, we mention that Golub [1973] provides exact deseriptions for the eigenvalues of rank-one updates as above, giving a rational function wxx) (with coefficients depending on ( and A (1+1) which has roots equal to the eigenvalues of M(++)) However, it is not clear how helpful this is for the quantitative estimates require.
At first glance, we might hope that we can sufficiently increase all of the eigenvalues of ((6) in just d rounds if in each round we partially explore new not-yet-explored direction. However, this unfortunately is not always the case. For example, suppose in the first round we use BIC action (1)
(1, O, ..., 0). Writing yp 1/V5, we then in the next d actions use the BIC actions A (2) (2ip. -,, 0, O, ..., 0). A (3) (0, 24p, -ip, O, O.... 0), and on until (dd) (0, O, ..., 0, 24, -;p). Then each A (6) has distance & = S?(1 from the span of the preceding actions, so we might hope that this already yields ((pestptta exploration. However, note that the vector
x 2, ....................... 1.....,,211 2d-1) satisties (x, A (a) = | - 2 (d-1) |x|| for all S < d. It follows that the matrix (( Di= (A $2
has smallest eigenvalue which exponentially small in d (since (x, (d x) /|x is exponentially small).
We show that our algorithm terminates in poly(d) steps using the linear algebraic Lemma below, which may be of independent interest. Informally, this lemma says that if u has non-negligible projection onto the space orthogonal to the large-or-medium eigenvalues of M, then the rank-l
update of M + u increases the total sum of the small-or-mediug eigenvalues non-negl.g.bly. Lemma 9 (Proof in Appendix D. Let V1, V2,,..V, E Rd such that |v:ll = 1. Define M =
Σ
822 Suppose Wi...., Wa are orthonormal eigenvectors of M with corresponding eigenvalues
7

---

A 2 A 2 O. Define & as the largest index such that >3 2 for some 0 < < 1, and define S S-SSSpaa........ We,). Suppose u is vector such that P (u)ll² 2 and define M' M+ Let ..'.. be the orthonormal eigenvectors of M' with corresponding eigenvalues X 2 2 X/. Finally, let be the largest index such that X 2004
Then
Σ 2/
Σ X
i=t+1
Main Results
In this section, we will formally state our main algorithms and theorems. For presentation purposes, for the formal algorithms and theorems will define
(c. //8888 4d π 1)2
min 1, min(
-M(c /d),
where d is constant from Lemma 15 and
are constants from Lemma 16 Note that we can spspecral exploration rounds with this value of X, then for any we can s-spectaal exploration -
rounds by simply repeating the algorithm [ times. Therefore, if we can ensure x-spectral exploration for the À value described above in poly(d) rounds, then we can also ensure s-spectral exploration in À poly(d) rounds for any A.
3.1 Algorithms
Our main algorithm is presented in Algorithm 4 with subroutines in Algorithms and 6 Note that these three algorithms directly correspond to the pseudocode presented in Algorithms
Algorithm 4 BIC Exploration
Input:
4d(K (((K+++1)++)
K max
A
2:
f- Cj
3: for / E 00 K) do
4:
Set (t) V1
5:
oi + x(t)
6: t
7: j +
8: while minimum eigenvalue of M =
Σ v is smaller than À do
9:
Wi...., Wa t orthonormal eigenvectors of M with corresponding eigenvalues A 2 ... Aa- E + max X X}
10:
8 Span ( We,)
a, IntiaalExploraatio(((1]11 (A) (ve) (tg )r=b)
13:
while |iPs (a)]l < do
14:
a, < ExxonentialGrowthhe (w.)) (Ad),, (vilknn ) M
Vj+1 <a a for t' E [0: do
16:
17:
Set A (t+(') =a
d + (++t')
18:
20:
j+j+1
Lemma 10 shows that the application of Lemma 8 (in the form of Lemmal 17 in Algorithm il valid.
Lemma 10 (Proof in Cpp Every time Algorithm 3 [ine 2 calls Algorithm 4 to define De. we have
01 2 + (O, x, Thus, z(y) (Line satisfies the assumptions of Lemma with e 5400

---

Algorithm 5 InitialExploration
Input: (w,)/=i:(up [ur [vik-1 Hog 18-11/
1: Define x" E R as 2 = (E", We).
2: Define y R Dr 1
Σ
(ve.we) de
ok
D Dir c by
Lemma 18 via Lemma 10
3: z(y) t E[x* y y
4: f < function from Lemma 8 for zy)) with c= caea
exists by Lemma 17 via Lemma 10
5: V < Bernoulii (f(z)))))
6: Set (4)
(r(0)
w.p. 10(KVR+1))((()))
Cada
v -1
7:
The above equation involves valid
[N(0.)) otherwise
probabilities by Lemma 8 and because max m (y)]) | [
8: a Exxloit(IRso) Wes+1).
9: return a, a
Algorithm 6 ExponentialGrowth
Input: a, [w:)
(2)) (vile Hot Wotte W
Span 1=1
S
W1 (Wi,..g We,)
Po (a)
2:
P (m)
3: ck Σ (s for [1
D Ps(aa -Ek= CVVA by Lemma 18
4: I +- 4d(E(e" (1+))
5: For E t + L), A (P)
6: + Li
7: R 1itti1 (1(t) Ek=1 c
8: b Exploit(1 Wea-1)
9: return b,
3.2 Propositions and Theorem
As discussed in Section 2.2 the main purpose of Algorithm 5 is to find a BIC action that has sufficiently high magnitude when projected onto the space of not-yet--uuficiently explored actions. This is formalized in Proposition II As discussed in Section 2.3 the main purpose of Algorithm to double the magnitude of a when projected onto the space nottyet-suuficiently explored actions. This is formalized in Proposition Proposition 11 (Proof Appendix
The action a returned by Algorithm 3 satisfies
| (a)ll 2 C 2.3 EaCa
2.5
16 (K = cril
C. C.Ca-
Proposition 12 (Proof in Appendix J. The action returned by Algorithm satisfies
IPs > (Ps=(a)))
We can now state our main theorem bounding the sample complexity Algorithm 4
Theorem 13 (Proof in Appendix K). Algorithm 4 is BIC and has sample complexity
ds
d²
O log
(
Cv eaca
As discussed above, for any Å, we can repeat Algorithm 4 for [ times get X-spectral explo-
ration. This is because trace is additive, and therefore if running Algorithm 4 once gives A-spectral exploration, then running it [X/2] times will give X-spectral exploration. Multiplying the bound from
O(1) log(1/ca)
Theorem 13 by [5/2] gives that X-spectral exploration achievable
-ea
rounds, matching the desired result of Theorem 4

---

Rasthee HC DI
Retion bask (angredd)
R8:000245:0 4 4- 1.0 C1360 2440
FC FC3 5 -05 L.00100
Guatic 1100ped,
10700
Sandiee Cor plodty Troshacs (kgrowo2)
Duxtin Crasth liep Loef (Depcttdd sowet m-4)
Sance Corpleity Seeel Loy Exacuat scmo 21
14'1
42
Figure 2: Summary of computational scaling. (a)-(b) show polynomial fits supporting quartic runtime and quadratic sample complexity: (d)- residuals indicate good model adequacy; (e)-(f) log log plots corroborate slopes near 4 and 2, respectively.
4 Experimental Results
Finally, we conclude with a simple experiment validating the practicality of the proposed algorithm. We implemented Algorithm 4 and tested on synthetic data (Figure 2 Our experiments focus on the setting where the prior distribution is a d-dimensional Gaussian that is independent across all dimensions and has mean 0.1 in the first dimension and mean 0 in all other dimensions. Note that our algorithm can be applied to arbitrary prior distributions, however we ran experiments for the independent case as this simplifies the code significantly. For this setting, Aasumptionn3Joll holds for 1. The constants in our algorithm are certainly not optimal
1, K 1, and for this specific instance, yet these constants are what allows our theoretical results to hold for any prior distribution. We ran our algorithm for values of d ranging from d = 2 to d = 24 and tracked the number of samples necessary to achieve X-spectral exploration. The results show quadratic dependence of the sample complexity on dimension, and quartic scaling for running time. Therefore, in practice the number of steps grows polynomially in at a much better rate than the worst-case bound in our theoretical results. One reason for this is that a factor of d in our bound comes from Lemmaf9, which is a worst-case bound on how much exploration we gain in each step due to subtleties of dimensianli geometry. Experiments were an XPS 13 with an Intel Core i7.
<a = 0.1,
5 Discussion
We conclude with more detailed discussion on how our results be combined with the results
of Sellke 2023 to achieve end-to-end guarantees for incentivized exploration. Here we focus
r-regular μ as assumed in that work, which is encapsulated by Proposition []] Recall [Sellke)
2023
Theorem 3.5] shows that for > 0, if an algorithm has already achieved O(dt//² O(d+/)==")sspoctral -spectral
exploration at time f, then running Thompson sampling from time onward will be <-BIC (where
term from the right-hand side). Theorem Lefficiently achieves the necessary spectral exploration, with at most poly(d, 1/r, 1/c) sample complexity (and thus additional regret). Note that our algorithm actually gives stronger guarantee than in Sellke 2023 (BIC rather than e-BIC). If we only need to guarantee the initial exploration is eBII, then we longer need the InitialExploration phase of the algorithm, and therefore can drop Assumption I Combining our result with Sellke 2023 and the analysis of Thompson sampling in Dong and Van Roy 2018 or Agraaal and Goyal 2013 we therefore obtain an end-to-end e-BIC algorithm with respectively Bayesian regret (dly 1/r, 1/e) + ((d/T) or frequentist regret poly(d, 1/r, 1/e) O(d3/2 Namely, one first runs our algorithm for poly (d, 1/r, 1/e) steps to guarantee the required spectral exploration, and then uses Thompson Sampling for all remaining steps. Since the regret from the initial exploration phase is constant relative T (and polynomial in d), this combined algorithm will asymptotically obey the ofte-of-the-art regret bounds for Thompson Sampling.
<BIC relaxes Definition by subtracting
10

---

References
Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization. In COLT, pages 263-274. Citeseer, 2008.
Priyank Agrawal and Theja Tulabandhula. Incentivising exploration and recommendations for contextual bandits with payments. In Mulli-Agent Systems and Agreement Technologies: 17th European Conference, EUMAS 2020, and 7th International Conference, AT 2020, Thessaloniki, Greece, September 14-15, 2020, Revised Selected Papers 17, pages 159-170. Springer, 2020.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson Sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An Introduction to Random Matrices. Number 118. Cambridge university press, 2010.
Dirk Bergemann and Stephen Morris. Information Design: A Unified Perspective. Journal of Economic Literature, 57(1):44-95, 2019.
Sébastien Bubeck and Ronen Eldan. The entropic barrier: Exponential families, log-concave geometry, and seff-concordance. Mathematics of Operations Research, 44(1):264-276, 2019.
Sébastien Bubeck and Che-Yu Liu, Prior-free and prior-dependent regret bounds for Thompson Sampling. Advances in neural information processing systems, 26, 2013.
Sébastien Bubeck and Mark Sellke. First-Order Bayesian Regret Analysis of Thompson Sampling. IEEE Transactions on Information Theory, 69(3): 1795-1823, 2022.
Sébastien Bubeck, Nicolo linear optimization with bandit feedback. In Conference Learning Theory, pages Workshop and Conference Proceedings, 2012a.
and Sham M Kakade. Towards minimax policies for online
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012b 2b.
Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature in multi-armed bandits. In Algorithmic Learning Theory, pages 111-127. PMLR, 2018.
Yeon-Koo Che and Johannes Hörner. Recommender systems as mechanisms for social learning. The
Quarterly Journal of Economics, 33((2)871-9255 2018.
Sinho Chewi and Aram-Alexandre Pooladian. An entropic generalization of Caffarelli's contraction theorem via covariance inequalities. Comptes Rendus. Mathématique, (69): 2023.
Shi Dong and Benjamin Van Roy. An - Analysis for Thompson Sampling with Many Actions. Advances in Neural Information Processing Systems, 31, 2018.
Alain Durmus and Éric Moulines. High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm. Bernouli,, 25(4A). 2019.
Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis- Hastings algorithms are fast. Journal of Machine Learning Research, 20(183): 1-2,, 2019.
Peter Frazier, David Kempe, Jon Kleinberg, and Robert Kleinberg. Incentivizing exploration. In Proceedings of the fifteenth ACM conference Economics and computation, pages 5-22, 2014.
Dan Garber and Elad Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
Gene H Golub. Some modified matrix eigenvalue problems. SIAM review, 15(2):318-334 1973.
Robert D Gordon. Values of Mills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. Ann. Math. Stat., 12(3):64-3666 1941.

---

Yonatan Gur, Anand Kalvit, and Aleksandrs Slivkins. Incentivized Exploration via Filtered Posterior Sampling. Proceedings of the 25th ACM Conference on Economics and Computation, pages 1200-1200, 2024.
Xinyan Hu, Dung Daniel Ngo. Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing Com- binatorial Bandit Exploration. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. Journal of Machine Learning Research, 18(145)1-31, 2017.
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Bayesian exploration with heterogeneous agents. In The world wide web conference, pages 751-761, 2019.
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing Explo- ration with Selective Data Disclosure. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 647-648, 2020.
Nicole Immorlica, Federico Echenique, and Vijay V Vazirani, Online and Matching- -aased Market Design. Cambridge University Press, 2023.
Emir Kamenica. Bayesian Persuasion and Information Design. Annual Review of Economics, 11: 249-272, 2019.
Sampath Kamnan, Michael Kearns, Jamie Morgenstern, Mallesh Pai. Aaron Roth, Rakesh Vohra, and Zhiwei Steven Wu. Faimess incentives for myopic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 369-386, 2017.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic' learning theory, pages 199-213. Springer, 2012.
Thomas Kerdreux, Alexandre d' d'Aspremont, and Sebastian Pokutta. Projection-free optimization on uniformly convex sets. In International Conference on Artificial Intelligence and Statistics, pages 19-27. PMLR, 2021a.
Thomas Kerdreux, Christophe Roux, Alexandre d' Aspremont, and Sebastian Pokutta. Linear bandits on uniformly convex sets. Journal of Machine Learning Research, 22(284):1-23 2021b.
Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "Wisdom of the Crowd". Journal of Political Economy, 122(5))988-1012 2014.
Kfir Levy and Andreas Krause. Projection Free Online Learning over Smooth Sets. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1458-1466. PMLR, 2019.
Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian Incentive-Compatible Bandit Exploration. Operations Research, 68(4):1132- 2020. Preliminary version in ACM EC 2015.
Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Steven Wu. Bayesian exploration: Incentivizing exploration in Bayesian games. Operations Research, 70(2), 2022. Preliminary version in EC 2016.
Zakaria Mhammedi. Exploiting the curvature of feasible sets for faster projection -ree online learning. arXiv preprint arXiv:2205. 1470 2022.
Marco Molinaro. Strong Convexity of Feasible Sets in Off-line and Online Optimization. Mathematics of Operations Research, 48(2):865 884, 2023. doi: 10. 20.12877moo..222.111 1285.
Roger B Myerson. Multistage games with communication. Econometrica: Journal of the Econometric Society, pages 323-358, 1986.
Yurii Nesterov and Arkadii Nemirovskii, Interior polynomial algorithms in convex program- ming. SIAM, 1994.
12

---

Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling, Mathematics of Operations Research, 39(4):1221-1243, 2014.
Daniel Russo and Benjamin Van Roy. An information-theerrticc analysis of thompson sampling. JMLR, 17:68: 1-::30, 2016.
Adrien Saumard and Jon A Wellner. Log-coneavity and strong log-concavity: review. Statistics surveys, 8:45, 2014.
Mark Sellke. Incentivizing exploration with linear contexts and combinatorial actions. In International Conference on Machine Learning, pages 30570-30583, PMLR, 2023.
Mark Sellke and Aleksandrs Slivkins. The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity. Operations Research, 7165):1706- 177--1723, 2023.
Max Simchowitz and Aleksandrs Slivkins. Exploration and incentives in reinforcement learning. Operations Research, 72(3):983-998, 2024.
Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2))1-233) November 2019.
Taira Tsuchiya and Shinji Ito. Fast rates in stochastic online convex optimization by exploiting the curvature of feasible sets. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Ramon Van Handel. Probability in high dimension. Lecture Notes (Princeton University), 2(3):2-3, 2014.
Huazheng Wang, Haifeng Xu, Chuanhao Li, Zhiyuan Liu, and Hongning Wang. Incentivizing exploration linear contextual bandits under information gap. In Proceedings of the 17th ACM Conference Recommender Systems, pages 415-425 2023.
Siwei Wang and Longbo Huang. Multi-armed bandits with compensation. Advances in Neural Information Processing Systems, 31, 2018.
Julian Zimmert and Tor Lattimore. Connections between mirror descent, Thompson sampling and the information ratio. Advances in neural information processing systems, 32, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims of BIC exploration are discussed in both the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss each the assumptions of our model in depth in the introduction
section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
14

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All complete theoretical proof' included in the appendix of our paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The parameters of the experiment are described in detail.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
15

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
The algorithm is simple implement and all details are included in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/ cublic//uides/Codeee /ww.e/eummissiionooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https)
/ haappp/.cc/pllllcc/iiiee////dddd htw.:iddeee/ooeeuuunissiiioooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Description of parameters is included in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiments are meant to only show an example of how the algorithm behaves (not justify any formal claims), and graphs are included showing the performance trends.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Included in experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
17

---

Question:
Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have reviewed the NeurlPS Code of Ethics and they are met by our paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The broader impacts of our work are discussed in the introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cow com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do include any experimental results as this primarily theory paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non stannaddd components.
Please refer to our LLM (ttt:ee//eerrrpppccc///ffereeeee for what should should not be described.
20

---

A Technical Lemmas
In this appendix, we introduce a series of technical lemmas that form the basis our results. Our proofs rely carefully analyzing how the conditional expectation of L changes when conditioning on different signals 1b. Lemmas 17 are the main tools we use to analyze the behavior of these
conditional expectations.
Lemma 14 says that for random variable X, we have some signal R that equal to X plus noise with some small probability and is just pure noise otherwise, then the conditional expectation of X given the sign of R has magnitude that is S2()). In the "initial exploration" phase our algorithm we explore
(not previously explored) direction with very small probabilityy Lemma 14 imipiiess that this exploration will lead to the conditional expectation of in the newly newly-explored direction having magnitude proportional to the probability of exploration.
Lemma 14, Suppose X is a real-valued K-sub- Ssub-gauusian random variable such that [[ = 0, E[X"] xx. Let R ~ X N(, 1) with probability and R N(0 1) with probability 1 Then there exists en independent of X such that
[ |Rsooll 2 X
The proof of Lemma 14 can be found in Appendix [H.1]
Lemmas 15 and 16 are the main technical tools that allow for us to exponentially grow the amount of exploration in any new direction. Informally, Lemma [55 says that even if X forms only an fraction of the signal r, conditioning on the sign of r will increase the conditional expectation of X by a multiplicative factor. This lemma will be applied to the expectation of l in the trying to explore. Lemma 16 says that any random variable conditioned on the sign of r cannot have conditional expectation increase by more than Oee). This will be applied to the expectation of l in all of the directions that we have already explored. These two lemmas combined allow our algorithm to multiplicatively increase the magnitude of the expectation of l in unexplored direction relative to the already explored directions.
direction
Lemma 15. Let X be E-sub-ggassiin random variable satisfying E[X] = 0 and E[X?] =ox >
Cv. For Z ~ N(0 o²) such that Z 11. X and >> O, define r = eX + Z. Then there exists a constant
6 15 such that if c/o 8 15
60
Cve
B[X Tr>o]]
2
20 2
2m
BTO
The proof of Lemma 15 can be found in Appendix G.
Lemma 16. For K sas-uu--gause -auusgaasian random variables X, such that [[X] = E[y] = 0 and for Z ~
N (0, o2) independent of X and Y, let eX + Z. Suppose < 8 m
min
(1,
2K (og(22
Then there exists constant C 0 such that
[
T
S C.po /a.
The proof of Lemma 16 can be found in Appendix
G.2
Lemma 17 is a more technical lemma that allows us to better understand the distribution of E" when condition averages based previous rewards. More specifically, this allows us to apply Lemma & to the random variable z as described in Section 2.2 The proof Lemma 17 can be found in Appendix
Lemma 17. For random variable X in Rd, define Y = X + W where W ~ NO, Diag(s)) and W is independent of X. Define Z(Y) ) E[X Y). If min Pr ((X, v) ca) Z eg and for all
/3/32 then
i [1 d). 8, I C1 == log(4/ra)
min ( v)) EdCa
||
The final lemma for this section says that any vector in the span of the top eigenvectors of a positive semi-definite matrix can be represented as linear combination of these top eigenvectors with coefficients that are not too large. The proof of Lemma [8 can be found in Appendix F
21

---

Lemma 18. V1 V2,...; E Re such that llv - 1. Define = Ei= 892
v SSuppose Wi.... Wa
are orthonormal eigenvectors of M with corresponding eigenvalues 21 2 ... A1 0. Suppose
Ae 2 E. Then for any u E Span(w1,.., We) such that ||ui]| S 1, we have u Ei=1 Vi where G = Ei (v..w))x..wl) Furthermore, 1. 5
We also note that any sub- ganssaausin random variable satisfying P([X] 1) S -e-
for all
t 2 0 (as in Condition satisfies the following bounds on the moments of X:
B B - [[| ( (( t) - J
/
2e - di K kVT,
(2)
E[X !
IPX2 tjdt z {
2e 2e-t/K t/K² dt 2K?
oo
B Discussion on Assumptions
Here we illustrate the importance of Assumption 3 by presenting a series of propositions lower bounding the number of samples needed in the worst-case for 1-spectral exploration in terms of the different parameters Assumption Lemma 19. There exist instances that require (11/c,) samples for 1-spectral exploration.
proof. Consider the following example with d = 2 and where the coordinates of l" are independent (and assume that ca < 11 Ea < c, 1):
-ca
w.p. Ed
c-{-00
6 f-{- Co
f-00
w.p. 1/2
G - 1
w.p. 1 ed
w.p. 1/2
Oeea) 0.5 for sufficiently small cd, then no optimal action will ever weight more than (c,)) on the second coordinate because the magnitude of E is bounded by Cp- This implies that we must need 1/c, steps in order to guarantee 1-spectral exploration.
Note that E[f v- =1 1
Proposition 20. There exist instances that require ((ca) samples for 1-spectral exploration.
proof. Consider the following example
- Cd
w.p. cd
f -Cp
w.p. 1/2
2ca
w.p. 2cd
Eg
Cv
w.p. 1/2
w.p. 3ca
Once again, the first action must be ej. Furthermore, in this case we need ((poly(1/ca)) actions of ei in order decrease the conditional expectation of E be O, need this many samples to be able to effectively distinguish between L = ca and l = 2ca. This implies that we require Oppoly(1/ca) samples to explore the second dimension this example.
Lemma 21. Let I. = +c be uniformly random for some |c| < 1. Suppose we receive noisy observations r; s,L + Zz for sequence r1,... that is adapted to the filtration F, generated by (81, T1, 82, r....., St, vt). (Iee. the signal strengths 8; may depend on the past.) Let T. Ei= Then the expected information gain on L is at most (EE
proof. This is a special case of observing Brownian motion with drift up to the random stopping
time T,. (Since observing r; L + Z; is equivalent to observing Brownian motion with drift L. for time o7. up to rescaling.) Let (T.) be the laws of Brownian motion with drifts the up time T, By symmetry the expected information gain can be computed assuming L c, and is bounded by
22

---

Convexity [0K000/khh00.000)--xx00000000000
$ [T]]
Here we used
= c [T[T) by Girsanov's theorem.
Corollary 21.1. the setting of Lemma 21 let C E EILI(s1, Sty Pi, m.. re). Then [|C;] & O(ET)).
proof. This follows from the previous lemma: the expected relative entropy between the prior and posterior distributions of L is precisely the information gain. In turn, the relative entropy a strictly convex and even function of C2 which is (2(C?).
Proposition 22. There exist instances that require ((log(1/<a) samples for 1-spectral exploration.
Proof of Proposition 22 This proof is more subtle and requires inductive control of the information gain on the 2nd coordinate.
We now return to the first example prior from the Co lower bound, and apply Corollary 21.1 to the observations of the 2nd coordinate. To make the application direct, whenever an action (01.t 02,1) is played, we replace the noisy reward observation with separate observations for both (a1,t. 0) and (0, (2.)) (with half the noise level, which only affects constant factors in the argument). This gives strictly more information since the two separate observations can be added to recover the original observation. We let C,, from above correspond to observations the second coordinate.
At each time i, by Jensen's inequality the convex function f(x) (1/3 r)+, we see that for any signal t
PEELI < 1/2] ((E[((E))) < O(EI((E)) S O(Ea).
On the main high-probability event that [vL 1/2, the 2nd coordinate of Exploit(v) has absolute value at most O((C,).. Via the Lemma and Corollary above, it follows that
B[T++1] [[T] S O(E[T)] + +a)-
Namely case [V[ S 1/2] contributes Olea) while the remaining case contributes ( O(B[T.).
Since To = 0, this implics by induction that
E < ow0)
Finally that need T, > 1 for 1-spectral exploration. Indeed, 1-spectral exploration requires that the actions ai..... de satisfy
(o Max) 2 Tr(M)
for all positive semi-definite matrices M, and taking M = (o. 0 1 gives the desired log(1/ea) lower bound.
recovers the claim. In all this
23

---

C Proof of Lemma I0
Proof of Lemma 10 Recall that the input parameters from Algorithm 5 come from their use in indicating equality distribution.
Algorithm
We compute as follows, with A
we)
91 ACpp 1v
9k
(Vk: Wel
VK. We
AC
(V:: (²) ACI
1)
d
d
P==
p=0
k=
(Vis we) Vi )
(V&, wr)2
Ae 1
+ N
0, 0,10117
de
X2
16
Ac
E,
Aer
+ N 0.
Mw;
[Lemma 18 (u w/)
X2
t==0
22 + N 0, C
We will apply Lemma 17 with X = x", Y ý, and Z(Y) z()). As shown above, (and using that
Xe < 1 for all l s Ex) we have that Y X has the appropriate distribution. The last thing need
to show is that
min Pr ((X, q) 2 ca) |q||=1
min Pr
Σ (e',
we)ge 2
=|
8=1
Ex
min
Pr
E"
Σ qowe
cd
l|
min
Pr ((e", v)
ca)
|||
Ed-
[Assumption D
This means we can apply Lemma
17 get that
min (l(z()) v)
CaCa 4
||v|=1
We have therefore shown that z(y) satisfies the assumptions of Lemma with SaCa
D Proof of Lemma 7
Proof of Lemma) 7
The BIC optimal action given vá is
A' arg max (A,AA"))) b/]
A
arg max A, E[e"
v))
AEsS-1
Therefore, the BIC action is A" is BIC including v.
Eje |
if [E[e
+ill + 0. |E(e"
= 0, then any action
E Proof of Lemma 9
We will prove the following equivalent lemma.

---

Lemma 23. In the setting of Lemma 9
Σ
We first observe that Lemma 23 implics the desired Lemma
Proof of Lemma 9 By linearity of trace,
Σ x1 Σ A
Therefore, Lemma 23 implies the desired result that
Σ 2/2 X
Proof of Lemma 23
First, note the following, where the max is X1, X1,..., Xy that orthonormal.
X max X
x, M'x; = max
Σ x, Mx; + Σ (x,, u)
X XI...X
Define
xi...,, xi = arg max Σ x, M'x
(5)
Xi,..,,;; i=1
We will now prove (by contradiction) that for all i 5 l, [Ps (x;) S Tood
Suppose that there
exists some i' E 11... l such that ||Ps4 (x;))11 > 100 Then we find
(x)
M'x;
= Σ (xf)
Mx;
[x u)²
1=1
$14 +
(x]) T Mx
[x orthonormal so (x), u2 < ||u||2 < 1]
1=1
=1+ Σ
(Pss (xi) MP (x²) + Ps(x)) (PP(Xs((MMP(((((( MMP((())
=1+ Σ
Ps (x+) MPss (x+) + Σ Px)) [Boxx))MPP(55)) 'MPs(x))
=1 +
Ps(x?) TMPs(x?)
IS_ span of evectors with evalues S c]
1=1
=1 de +
( WE
M Σ xx wx)
i=1
1 de
(x) w 2W Mw
==1==
=1 + de +
(x, wx) A
(6)
k=1
25

---

Because x are orthonormal, we know that E (x. wx)2 - Wk 1/ 1. Because we assumed
that [P (xx)112 > 1007 we know that _im1 Et (x.. wx - IPs [x5(x;)]l
s
2²
100a
Combining these two statements with the fact that X is decreasing in K.
1
wx)
-
Xe +
100d?
i=1 k=1
Continuing where we left off with Equation 6
we have that
Ax s de (1-
e²
=1 + de
(x) w&)
Ae
100d
==
1 1 + de
A
100d
200d
< 1 de - 2d +
X
D 2
2
i=1
[c [<<1] [11]
i=1
i w. Mw, S Σ w. M'w:
Therefore, have contradiction, xi. .... x3 cannot be solution to Equation vectors are strictly beaten by Wi,.., We.
( because these
Therefore, we have shown that |Asu (xt) < 1000 for all i.
In the following equation, we define Ps as the projection matrix for projecting vector onto S. Now, we have that
Σ
Σ (xf)
Σ ui,u)²
1=1
i=1
i=1
Σ
A
(x u)²
1=1
< Σ
xx+ Σ
(Ps(x)), + (Ps
1=1
1=1
2 100d
Σ + Σ
1nd
E
[|] (x))) <
2m1
2²
Σ A Σ
(Ps(x)),Ps(u))
(Ps(x)), Ps(u)M +
5d
100
i=1
2
Σ A
Σ
(Ps(x)), Ps(
5d
100d
1=1
2
A
+
+
Σ (Ps(x)))
5
100d
1=1
2
Σ
Σ ((x)) P5 Psu)² 2
5
100d
2
Σ ((x)) T Psu)² 2
5
100d
26

---

A
+
+
Σ
xx
Ps(u))
5
100d
6²
A
+
[
5
100d
1=1
6²
1
5
100d
i=1
Σ Ae + (1-e2)/))
i=1
This completes the proof of Lemma 23
F Proof of Lemma 18
Proof of Lemmal 18 Define A E Rixd with rows corresponding to Vi, Vy. Then M = ATA. We want to write u = A ATc. c for c E TR..
Because Wir... Wy are orthonormal and Span(w1,... We), we have that
uu w,),;
Because w, is an eigenvector of M with eigenvalue X we know that for any é I
Aw Mw, A Aw,
Rearranging terms and multiplying both sides by (u, w.). we have that for any i < l
[u, w;)
(u, w,; =; AT
A
Therefore, we have that
(i.
(u, (w,
Σ (u,
Σ A
A
A
d
Now, we can define
(u, (u,w:)Aw,
(u, W
c=
= A
A
A
This implies that
uu, w Wi
|c
2
A
2
iu, w
fu, w
M
d
(u,, We)
2
M.W. -11
A
(u, w.)
A
|
This vector therefore satisfies the desired properties.
27

---

G Proof of Lemma g
We begin by proving the following lemma. Lemma 24. Let p be probability distribution on Rd with finite first moment and suppose
min EE [V:x--12 [|v|==
Then for any w with [[]]] < there is [0, 1]-valued measurable function such that R[xʃ(x)] = w.
Proof of Lemma 24 Let K be the set of possible vectors Exxf(x)) where f is [0, 1] valuue measurable function. Then for any a, b E K, there exist corresponding [0. 1]-valued functions f and for such that [[xf"(xx) because f(xf" ta + (1 - t)b for (x) tf (1 t) (x). This implies that K is convex.
and gxx f (x)) b. Therefore for any E [0. 1], + t)b K
We will now prove the desired result by contradiction. Suppose & K. Because K is convex, if w & then there a "separating hyperplane" unit vector v such that
sup (v, u) S (v, w). uek
(Note that do argue here that K is closed.) Because by assumption we have that ||w| <e. this implies that
sup (v, u) <.
uek
For any by definition of K and linearity of expectation we have that
sup (v, [v (xf(xx)) uEK f.R0-(0,11
sup (v, u)
(x)(x((
sup
f
[v,[((v))+]]
2 e.
where the last line followed from the assumption of the lemma. This gives a contradiction, and therefore K must be true.
Proof of Lemma g
Applying the above lemma with w 0, there exists fo Rd + [0. such that
E[xf*(xx) O. Define the function f' f'(x) m [R(x]]l
(x)++2
By this construction,
/ (x)] 2e Ex
2e ||[
[[[(x/(xx)]]
4 max [[xx]
4 Ex]]111 2
Therefore, w = -=[[xx((x)) satisfies ||wl| < Applying the above lemma again, there exists
1 Rd [0, such that [xx f((x 1max(]E[)]]1.>> Furthermore, by linearity of construction, have that 1 2 f(x) 2
(x)) Now define f(x) f( By
2
expectation and the construction of f we have that
[[xf(x)) = E x fx() + f (x)
[E[xf(xx) + E[xf"(x))) = [E[xf'(x)) E[xf = 0.
Therefore, f(x) is 1max I valued function that satisfies [x) 0 desired.
G.1 Proof of Lemma
Lemma 25. Let (0(x) = P(Z z) for / 2 NO, Then for |x| S
(0(x)= (1
22T" #) )
< | 1/15
28

---

Proof of Lemma 23 A third order Taylor expansion shows the error is at most
(
| sup
For |ul S we easily compute
11² 1/e 1/121//2
12/2
(()
S 1//V2x $ 2/5.
V
Lemma 26. If X is K sub--aussian, then for any event F: and any P(E) 2 a >> 0, we have
1[x²1 S K2 K²Pr(E) (2/() + K²a, a
B[X1A] < ((Pr(())oog(//o)))
Proof of Lemma moment,
26
We prove both estimates using the tail-sum formula. For the truncated second
E x 1 F.
Pr([X21 2 l)di
(T)(P t))dt
min(Pr(E3),2e )tt
- (r())log(2/a)K²+ 1og(2/0)133
2e 2// di
K Pr()))/)g///// + K2a.
Similarly for the truncated first moment,
E 1111 F
Pr[|X1æ| 2 l)dt
min(Pr(E), Pr(X t))
min m 1k'3 )tt
< (o(E/)/og((//a)) +
2e -t/K3
dt
Vlog3//ojK
(og()))))
Proof of Lemma 15 Let dux be the law of X and dpxps>0 be the conditional law of X given the
event r > 0. Then by Bayes rule,
dpx)>>((z) Pr(r > 0 X = 2)dpx(a)
Pr(r 0)
Pr Pr(N 0²) > 0) dux(xx
Pr(r >0)
$C (0((=x/o)d)xx(1)
Pr(r> > 0)
Note that
r > 0) = 1
L x (-ee//oo)) (x).
E X
xdpx))>0(0))
Pr(r > 0)
29

---

Since Pr(r= > 0) S it suffices to lower-bound the latter integral by a suitable positive value. As
long as c/0 I 1
we have
403 V2F
r
E2/ )d)x(x))
0
1
e3
dux(x)
2
V 2T
0
1
El
dpx(z)
0
2
x
Φ
E0
1 dpx(o))
[E[]] 0]
ov 2m
0
2
0
00
2 2 E
Inequality Below]
2m
σ3
2m
0²
E V 2n
Above we used the following estimate (). For sufficiently small 8
1
1
x Φ
dux(x)
00
0
2T
Φ
Eτ
1
Ex
dpx(()) + /
Φ
Ex
1 Ex
dpx(c)
x
I
|0|
0
22T
v
12/> 10e
0
2nx o
C
1
dpx(()) -
/
[z|
+
Ex
dux (z)
1 dhe
V2T
|0|>
2
1 1
E2
/
[z|
Ex²
|0||
dxx(x)
+
dux(zz
[emma 25
|0|2 1oc
2
0v2R
2
+
dux(xx
1//> 18
2
ov2x
E[X
dxx
lif e/o S 8 S 1/10]
1 for
(K²2 Pr(E) log(2/o) + K²aa
[emma 26 E = f|r
}. a 2e 1602"R2
T3
10c"
1
0²
2K E I,
100.2 +1)
(Pr(E) S 2e -o² (1000>
2
[2K
22 10o
100c2 + +1) 5
o²
(0
E[x
where the second to last line holds for sufficiently small c/o.
G.2 Proof of Lemma
Proof of Lemma 16 First, we observe that E[Y r >>> 0] also have that
B F(r20)
If 5 K / log(4) < 1/2,
Pr(r > 0)
Pr(r > 0 -K (loo(())) Pr(X 2 -K (lo(4()
C ( K log(4) Pr(X 2 -K
K (loo((4)
$0 e Kv /log( 4)) (1-2e- 2e 2e- 12 log(4)/K²)
30

---

(1/2)11
- K v 1og(4) 1/2]
1/88.
Therefore, it is sufficient to upper bound [r 0J]1
By law of total expectation,
Y 0}} E 0} x E Y X _xx]
Define Q(X) - E| X]. Because is sub-gaussian, the random variable Q(X) must also be sub- gaussian with parameter / 18K (see [Van Handel 2014 Exercise 3.1J). Furthermore, [x)( = x]] [E[ 0. Now, have the following
BL
B
r 0}]1
E
Y x|p(Z>
-x
Q())
((0)dux(()++ / Q(x)) 10 - dux(xt)
B[Q(X)] / Q(x)
(-
ex
2 duxx (x)
1
2
Q(x)
(0-
1
dux((x)
2
[er
6T 33
10(x)l
+1=
dux(()
|0|S OF
0V2
((x)
Φ (-
_
- dux(x)
[Lemma 25
[
1
/
[())
|299
dux (x) +
(px))
[e/o < 1]
2
|0/>
27 )
5
E[Q(X)?]
1209
0
(2c 10022 ))
[Lemma 26 Equation
10cK
((E/o))
where in the second to last line used that Pr([X] K m/T8-sub-gaussian The last line again uses that both X and Q(X) are sub-gaussian. Therefore, have shown that
a S 2e 10 and that Q(X) is
E Y > 0H P(r >
Y > Ojl =
<SEY1 > 0311 = 0(e/o).
By symmetric arguments to the ones above, we have the same bound |EEY S OJ|-
H Proof of Lemma 17
Proof of Lemma 17 Fix any v such that ||v|| = 1. First, we will show that
Pr((v (Z(Y) -X) 2 ca/2) S ca/2.
To do this, we will show that (v, (Z(Y) X)) is sub-gaussian random variable. Let X be draw from the distribution of X Y. Then we have that
- (v. (v. Y) (v, X).
31

---

By standard properties of posterior samples, (v. - Y) and (v, Y - -) are identically distributed with distribution N(0, o²) for o² = Σ d we have that
i=1 v.s, (here one averages over all randomness). Therefore,
E exp
(t(v, Z(Y) - X])]
E exp
[(v,E[xi -X)
[[vV [[v;x-xi]]
EE
exp
[Jensen]
t(v, - YY +Y x))]
E
exp
(2t(v, x x;)] B lexp (2t/v, Y - X))l
- E exp
(Cauchy-Schwarc
S 220
Therefore, (2()) X)) is sub sub-gaussian and satisfies the tail bound
(ellv,((()) - xx) > t) 2e (t/0/(0)0))
Taking = ca/2, because o² Σd v7.8, S max; 8; S
23/32
we have that
Tog(4/Ea)
Cd Pr(K(v, (Z(Y) - X
2 s 2c - (/202) cd/2.
(10)
Now, we can prove the desired result that
(()))
2 E
((Z(Y), (Z() - XXXI
2t X 2 o Pr (Ivv (Z(Y) xx)1 Cd (X.))
Cd
2 (X.v) 204)
2
E
Cdl
2
KV, (Z(Y) -))1 X))
2
(X.v) cd Pr (ZV) -X)I s ạ
2
X v) 20)
Pr
((v) -x))
Cd
XX, v)
(X 2
2
cd
Pr
(r(, v) 2 c2) Pr ((v (Z(Y) -x)|>> )
Cd
Cd
2 2
Ed
EE 10 and lemma assum]
2
Cdld
4
H.1
Proof of Lemma 14
Proof of Lemma 14 Let B be Bernouli random variable such that Pr(B 1) and let
N (0, 1) be independent of and X. Then we can write R X- B Z.
Then we have that
E
R > 0]
X R> 0, B=
0) R, O 0 R>
=||X
X + Pr = 11
Pr(R B]
-E|X X= 0
Pr(R>00
E|X X Pr(R > B))==))r((BBBBB 1)
E[X X Pr(X + O)c.
(11)
32

---

Next, we need to lower bound E X + Z > Pr + Z> 0). Applying Baye's 's rule gives
E|X X + -> Pr(X Z 0)
= Pr(X + +Z>00
adux|x+2>000))
(0 (-x)) (z)
a ($0(-x) - 1/2) (x)
[E| 0]
Note that ( 1/2) has the same sign as x and has magnitude increasing in (ar]. Therefore,
0x
P
0 0 2
ox
dux(z)+
/
ox
P
0
Z
ox
dux
2X V10
10
v1O
105-
2x
v10
v10
(0
Z
xx
v10
P(|X
ax
V10
VI0
P0 S 7 S xx)
4
[Equation
13) below]
V10
5K2 log
20K2 xx
2 ).
(12)
Combining Equations 11 and
12) gives the desired result of the lemma.
remains to show the lower bound on P([X
ox vIG
used in the penultimate line above.
Define a K2 log
200 ox
2 ox log(10)/2 > / 10 (using Equation (3) ). Next, we observe that
E E[
P(X2; > t)dt
P(X: Viddt
x/10
P(X > vijdl 1" P(X> > VTydt+ 1- P(X Viddl
033/10
I"
P(X > Vi)dt + I 2e t/K33 dt
S 00x/10
/
/11
P(X > Vtjdt + 2a22-1/K²
0
= o51
P(X > Viltt
[Def of a]
Ja3/10
$ 5xx15+
(a-
2
P
X
σx v10
[P Vt)
monotone decr.]
10
Since E xx. this implies that
(a-
xx
p
x
σx
40
10
V10
5
Therefore, conclude that
33

---

P
x
Ox
4
4
40
(13)
V10
x
a
5K2 log
20
x
By symmetry, identical logic as above gives the desired upper bound on E[[ R S 0j.
I Proof of Proposition
Proof of Proposition 17 We first show that A on Line 6 satisfies A S when v 1. Recall x" defined as 2 we) and recall that z(y) = E[xx y = y]. By construction,
x
1]
E[xx V 1, = y/dpy vy)
E|x² I =yl Pr( = 1 = y) dxp(y)
[ = is function of y
Pr(vi = 1)
/ E[x' y ylf (z(y)) drs(r)
Pr(v = 1).
Pr(v= = / (2)))(((())))4
E (z(5))(((())
Pr(v= =
= 0.
[Definition of f]
Because 27 = (l", we) for f < εx this implies that (E( we) v = 1] 0 for < lx. Therefore,
we must have that E[e" V = 1] E s By construction of A in Line 6 this implies that A E S- when V = 1.
Define
Eie" v=
F V 1] # otherwise,
A
10=1]l
Wix+1
in other words A equal A (1) when V =
By the choice of f. we have that IP(V = 1) 2 16 line we used that Equation A implies
6404
6a0d
where in the last
[
I6(KT++1]
max()I[|z})]]I 1) = max [E[x"]l., 1) < max
[[] 1) S max (K < -VT+1
By construction, we therefore have that for any realization of z the probability that R = (()) and otherwise It ~ NO, 1).
(E*, (9) + Wi = (L", A) + we is exactly Eade 16(k)
We can now apply Lemma with X = A), and = or
6aed Io(K(T+1)
to get that either a = Wex+1
Vaa A))2.5
CHLL c. 2.5
(A, a) = (A, Eie" LRSOL>| = = IRso]l
16 16(K
16 (
where in the last inequality we used Assumption
Because A E S and |||| 1, the previous equation implies the desired result that ||P (a)l >
aITTaaa 2.5
16(Kv++1)
Proof of Proposition 12
Proof of Proposition 72
The first step is to rewrite R from Algorithm 6 Line 80 that we can apply
Lemmas 15 and [6
34

---

Define
1+4-1 W
1+4-1
We
(ash - (v(v
Σ
wy Σ
cash
+ 1.
ck (V E))
v==t
k=1
h=1
k=1
Note that W is normally distributed with mean 0 and variance oi = L( + Σ (g) construction, we can rewrite R as
By
R
,(0)
c
k=1
((a, + we) Σ ck
P=t
14-1
Σ
(a, 1. Σ. ck (vk, e") + W
P=t
k=1
I((a (.(Ps(a), (0) W
[eemma 18 implies Ps(a)
Σ
k=1
L((a 1 Ps((a)), 6n) +W
L(Pss (a), (a), (-) W L1 (a) (x, l²) + W.
(14)
Therefore, R is exactly in the form necessary to apply Lemmas 15 and 16
In order to apply these
lemmas, we need that P| (a)
and P||
8 15
6 16
respectively.
dw
dw
To see this, note that Ps (a) S and therefore
(as otherwise ExponentialGrowth would not have been called),
L || (a)ll
LVA
OW
T(1 Σ k==1 2
(E Le + 1)2
4dd (K VT + 1)2
[Equation
A
Assum
(cv )2
min(8 11
1/C
(15)
[c, /v8m)² Ad(Kv /J++1
where in the last line we used X < min
by our assumption on X.
Applying Lemmas 15 and 16 gives the following two bounds. Define y E[e" 1 [R The first is
lower bound on (x, |-
Importantly, we can apply Lemma 15 for X = (x because of Equations
and 15
(x, y)
(xx, E(e" IRSUlX
= [|x e") |
7 ||Ps (a)ll
[Lemma 15
dw
LL |PsA (a)ll
V Σ c
Ad(EE(" 1 1)2
c
| (a)
35

---

Vadcole 1)a |p (a)ll
2v P (a)l
(16)
The next equation is an upper bound on ||y for all E [d]:
ly. EE[E": IR
< EE[e", :] + c || (a)ll fow
[Lemma 16
- [R(E") +
[Equation 15
Using the above equation, can bound l|yl| follows. Because IB[e") > Ble" x] for all i
1yyl2 S ++ vd(E(e"1)
Equation (16) implies that y o O. This implies by construction that = Exploit(1Rso, Wex+1) y Ty] Putting everything together, we have that
(x. b)l = 1(x, 2v + 1)) (a)ll llyl2
2 iPs (a)ll
V((F(e
Finally, because x E S this implies the desired result that
[Ps- (b)ll 2 [x, b)l 2 2 [| (a)ll
K Proof of Theorem
Proof of Theorem
13
We begin by proving that Algorithm 4 is BIC. There are four places where we Line Algorithm 4 where we set (4) ej. This BIC because we
set A (t), The first is assumed (without loss of generality) that E(e", 0 for all i >> and EE 0.
The second place we set A is in Line 6 of Algorithm by construction and Lemma
This choice of A (1) is BIC with the signal
The third place we A (1) is in Line 5 of Algorithm In order for this be BIC, we must show that every input to Algorithm 3 is BIC. The first time Algorithm[6j used for any fixed value of the input action is the action returned by Algorithm [ This BIC for signal R defined on Line 7 of Algorithm 5 by construction. Each subsequent call to Algorithm 66 for fixed value of j uses an action a that is returned by the previous call to Algorithm 6 of Algorithm
This BIC for signal R defined on Line
The final time we set an action is on Line 17 of Algorithm This action again an action returned by the last call to Algorithm 6, which argued above is BIC for signal R.
The rest of the proof will focus on bounding the sample complexity Algorithm
First, will bound the number of times the inner while loop (Line 13) calls Algorithm 6 for
each value of j. By Proposition 11 the action returned by Algorithm 5 satisfies |P
C, 2.5 edCa- Furthermore, by Proposition 12 [|Ps4 (a)] doubles with each call to Algorithm
Therefore, (a)]l 2 vă will be satisfied after at most logo
(log eaca
calls to Algorithm
Next we will bound the number of steps in each call to Algorithm o which is equivalent to bounding the L defined on Line Algorithm 6 To do this, we note that the c; in Algorithm 6 are the same as
the c; in Lemma 18 with
X, l lx Ps+ (a), and vi...., Vj. This implies that
Σ &
[Lemma
k=1
36

---

Therefore, we can bound as follows:
L 4d(E 1) + Ek=1 4)
4d( 1)(1 +
4d(K VT + 1)(1 + x)
[Assum
Eq Aj
6²2 (88)
Ac,²
For each loop of the while loop on Line we also have = O /ea)
d
steps in the loop
Acd
Xe,
on Line I6
All together, this gives that each iteration of the loop on Line 8
takes most
dlogg
log(1/ea) X
= (1)((()tt))
(
( A
Gv Geti
Xc,²
Gv Eaca
Ae
steps. Next, will bound the number of iterations of the while loop Line 8
u Vj+1. and the vectors Vi..., Vj. By construction of the algorithm, 5 is non-empty because the algorithm has not yet terminated, and Pas (V 2 A by the termination condition the while loop on Line 13 Algorithm Therefore, this satisfies the assumption of Lemma Define Ai. X/ as the eigenvalues of M : Σ/_ = v and define é as the largest index such that X 200d /X? (and e if all cigenvalues of MD less than 200d /2²). Now define
For each j. we will apply Lemma with
200d
21
Σ
X2
im8i41
Note that for any fixed i, the ith eigenvalue does not decrease between MD and M Because of this monotonicity, Lemma implies that for every round j. either
SAi X
g+ 2 e
+1 +1+1
or 1++1
200
Because g1 2 and A <
200d X
2004 this implies that after
X/2 + d applications of Lemma
9 either e = d or A = 0. This means that after 400d X² + d applications of Lemma the smallest cigenvalue of M2 must be at least 200d /X² > A. However, this means that the algorithm must terminate before round 400d*/>² +d. Therefore, the number of iterations of the while loop on Line is less than (dd /x3). Putting everything together, the total number of steps needed for X-exploration upper bounded by
( O log
Cv eaca))
1
d Ae,
Xee
)
0
d
13
=0
=0
(
+ cz
) O
L Proof of Proposition 5
Proof of Proposition
5
First, for any unit vector v, have B, (.,a((2rr/33)) S K. S (1). Therefore
(BB/aa(2rr//) =
Vol( 2
(B = (r/3)a.
Since (x, v) 2 r/3 for all x E (2rv /3), this confirms the values (ca, <a) =
The bound c, follows by Sellke 2023 Lemma 3.2) and Jensen's inequality since K. has width at least 2r in any direction. The bound K is trivial since 2e 2e-(t/ (x/1.25)2 > 1 for < 1.
M Proof of Proposition 6
We first recall several useful facts log-concave distributions. Throughout we take to be a-log- concave and B-log-smooth with mode x" and mean x, possibly in dimension (The proof will use 1 1-dimensional projections of the original measure μ.) We will write instead of l" p.
37

---

Fact 27 (Dwivedi et al.
2019 Lemma 5], Durmus and Moulines 1/a and with probability
2019 Theorem 1J). For x ~
we have E 2 x" |||
log(1/8)
log( 18)
|| x x0112 S 2a 1/2
1
d
Fact 28 ([Chewi and Pooladian
2023
Lemma 2J).
We have the covariance bounds
Ia ad = Cov(u) =
Ia
(18)
3d
Fact 29, Any 1-dimensional projection of p is also add-og-concave and 9d-log-smooth.
Proof. Preservation of strong log-concavity under projection is well known, see e.g. (Saumard and Wellner 2014 Theorem 3.8]. For log-smoothness, supposing for convenience that the projection is onto the first coordinate axis, the claim is proved by the following standard computation. With e-((x) the density of ll and e ==((2) the density of the projection of μ to the first coordinate axis, one may compute as in (Saumard and Wellner 2014 Proof of Proposition 7.1] that
g"(x) = [" (x))), = x]
Var" [ar (x) s| s E
x] S 3d.
This completes the proof.
Proof of Proposition 0
We have 2 3d directly from 18
For ea, let X be the mean under and note that from
18 we find
X - x'1| sup (x- x w)
w
sup Ex ((x x", w)l
sup ExmH - x", (\) w||=1
$ v (Cov(p), w
1/ ood.
Fixing a unit vector v as in Assumption 3 we consider the projection P onto the 1-dimensional subspace spanned by v, and let P(u) be the pushforward of μ under the projection (to which Fact 29 applies). Identifying P(Rd) isometrically with IR, let & be the mode of P(t). Then the same argument a|| 1/ 1/dod, and
as above applies P(n) shows P(x))
2
| <
x
add
Vad
(Note that x then this shows | < V od, which following the arguments below leads to ca 2 (2( as mentioned below Proposition
Write f + R_ for the density of P(u), and g(x) log fx)) We have f(( 0 and so g'(i) also. By Fact 29) we have g"(x) E Bd, aad] for all æ, so for x 2 & we have:
(((x) d'(x) g(t) = ' x g'(y) E [-Bd(x - 4), cdd(x })
Integrating again, we find
-ad(s J d'()ddy e 1-Bd(x - -2)2
g(z) (())
Identical reasoning gives the same conclusion for &. Translating back to f = ea, we conclude that for each z E I:
e - f < [(x)
f(t) < add2 xadlz=1f 2
38

---

= l" ~ and P(u): It follows that xorx=
Pr[(v, x) 2 cal 2 Pr/=274
Vod + cal.
Letting J = y 2 + ca. the latter probability is at least
Vad
e va/3 T (Jv 2 Bd/2 ood
(1 J23d) 2
The last inequality follows from the classical bound Φ (K)
( Itx where is the standard Gaussian
density Gordon [941]. This confirms the value of Ed.
For K consider a similar projection, and note that by Fact 29 and the Bakry-Emer theory for strongly log-concave measures (see e.g. [Anderson et al.
2010 Lemma 2.3.3), we have
E Mvx x S e
E R.
Thus with Jo = - + Ved (xx, v)ll, have (using AJo S 1+A233
B(eA(vx)) S (A2aad/2++2b) S Sed 0.3 e (1g+odd)/2 I 26 (J3
follows by the usual Markov inequality arguments that
Pr[l(v x) 2 t| S 4c 2 +o0d
Since probabilities are at most 1 and a I V for a I we find
Pr]l(v,)) 2 t| < 2e at +04)
which completes the verification of K since (Jß ad) 1/2 Jo + Vod.
For the counterexample, we may take (a, B) (1 and v be the distribution on R with density proportional to e dx- (1+12o00))) Then let Sdd so that x ~ μ has IID coordinates with law v. Then the mode x" is indeed zero but the mean of y is non-zero so taking v = 11, 1)/ 1)/vd,
Chernoff estimate shows Px*~H[x [xx v) > 0j < -((d)
39


Reviews:
[{"review_id": "yzDbsexxEU", "reviewer": "Reviewer_Rjs1", "summary": "This work studies the problem of incentivized exploration in linear bandits. Prior work of Sellke 2023 has shown that Thompson Sampling is BIC with an exponentially (in dimensions) number of initial samples. In this work, the authors show that it is possible to improve on this initial sample complexity when the action set is contained in a $d$-dimensional unit ball. Specifically, the authors provide an initial sampling algorithm with polynomial sample complexity. This is a significant improvement over the current literature on incentivized exploration in bandits.", "questions": "Please answer the questions listed above in the weaknesses. Furthermore, do the authors have any insight on whether this initial sample complexity is tight or can it still be improved in the future?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The improvement over prior work is a significant contribution. \n- The paper is generally well-written. \n- The problem of incentivized exploration in linear bandits is not new, but the initial sampling algorithm is novel. \n- The proof sketches are intuitive and easy to follow.\n\nWeaknesses:\n- The paper did not include any experiments. \n- The paper focuses solely on the initial sampling exploration, and needs to be combined with Sellke 2023's result to have an end-to-end BIC algorithm. Thus, the contribution may seem a bit incremental.\n- The paper did not explain the constants $c_v, c_d, \\epsilon_d$ in assumption 2. Having more elaborate justification of what each constant means and how they should be chosen in practice would help with understanding these assumptions.", "was_revised": true, "final_justification": "After seeing the responses to my review and other reviewers' comments, I still strongly recommend this paper for acceptance. This paper presents a very strong theoretical contribution to the problem of initial sampling for incentivized bandits exploration, and the authors have included a minimal working experiment as requested in the responses.", "rebuttal": ">*The paper did not include any experiments.*\n\nFirst, we want to emphasize that the main contribution and algorithm of this paper are theoretical and show that it is possible to explore every dimension in $poly(d)$ time. That being said, the algorithm itself is relatively simple to implement. Due to the interest from reviewers, we implemented our main algorithm (Algorithm 1) along with the two helper algorithms (Algorithms 2 and 3) in Python (which only takes ~100 lines of code). We then tested the algorithm on synthetic data with varying dimensions when the prior distribution is a $d$-dimensional Gaussian that is independent across dimensions and has mean $1$ in the first dimension and mean $0$ in all other dimensions. Note that our algorithm also can be applied to prior distributions with dependencies between coordinates, however we ran experiments for the independent case as this simplifies the code significantly (and also matches the independent priors in [Sellke-Slivkins 2023]). For this simple setting, we are able to run our algorithm with the constants of $\\epsilon_d = 0.1$, $c_d = 1$, $K= 1$, and $c_v = 1$. \n\nOf course, the bound in Theorem 3 is a worst-case bound on the sample complexity, and therefore we would expect that on most instances of the problem the number of steps is significantly less than that upper bound. Furthermore, we note that the constants in our algorithm are certainly not optimal for this specific instance of the problem, yet these (relatively large) constants are what allows our theoretical results to hold for any prior distribution. While we are unable to load a graph in this rebuttal, we ran our algorithm for values of $d$ ranging from $d = 1$ to $d = 24$, and sampled $\\ell^*$ from the prior distribution 100 times for each value of $d$ and then calculated the number of samples necessary to achieve $\\lambda$-spectral exploration. The results show a clear quadratic dependence of the sample complexity on the dimension, and quartic scaling for the running time.\n\n| Dimension | Sample Complexity   | Time (seconds)     | Sample Complexity / $d^2$         | Time/$d^4$         |\n|----|--------|--------|--------|------------|\n| 2  | 5132   | 0.02   | 1283.00| 1.2e-03    |\n| 3  | 11781  | 0.06   | 1309.00| 7.7e-04    |\n| 4  | 21145  | 0.17   | 1321.56| 6.6e-04    |\n| 5  | 32614  | 0.38   | 1304.56| 6.0e-04    |\n| 6  | 47121  | 0.82   | 1308.92| 6.4e-04    |\n| 7  | 64278  | 1.51   | 1311.80| 6.3e-04    |\n| 8  | 84107  | 2.49   | 1314.17| 6.1e-04    |\n| 9  | 106573 | 5.43   | 1315.72| 8.3e-04    |\n| 10 | 131696 | 6.19   | 1316.96| 6.2e-04    |\n| 11 | 159505 | 10.34  | 1318.22| 7.1e-04    |\n| 12 | 189954 | 14.30  | 1319.13| 6.9e-04    |\n| 13 | 223085 | 20.67  | 1320.03| 7.2e-04    |\n| 14 | 258838 | 26.72  | 1320.60| 7.0e-04    |\n| 15 | 297248 | 35.88  | 1321.10| 7.1e-04    |\n| 16 | 338359 | 46.61  | 1321.71| 7.1e-04    |\n| 17 | 382100 | 57.79  | 1322.15| 6.9e-04    |\n| 18 | 428515 | 74.51  | 1322.58| 7.1e-04    |\n| 19 | 477573 | 93.26  | 1322.92| 7.2e-04    |\n| 20 | 529270 | 114.13 | 1323.18| 7.1e-04    |\n| 21 | 583683 | 137.98 | 1323.54| 7.1e-04    |\n| 22 | 640716 | 168.16 | 1323.79| 7.2e-04    |\n| 23 | 700428 | 201.52 | 1324.06| 7.2e-04    |\n| 24 | 762755 | 241.09 | 1324.23| 7.3e-04    |\n\n\n\nWe do want to emphasize that for a specific instance of our problem (i.e. a specific prior), a user could tune the worst-case constants used in the algorithm to get faster $\\lambda$-spectral exploration. However, the above table just uses the default constants of the algorithm with the goal of showing that \n- the algorithm is implementable in relatively few lines of python code\n- the algorithm is efficient to run for reasonably large values of $d$\n- in practice, the number of steps grows polynomially in $d$ at a much better rate than the worst-case bound in our theoretical results (in this experiment we see a roughly quadratic relationship between the dimension and the number of steps). We are of course happy to add this result to the final version of our paper with more details about the implementation and with graphs showing the trends. \n- One reason why the sample complexity is so much better here than in our worst-case bound is that a factor of $d^4$ in our worst-case bound comes from applying Lemma 8 in our paper. This lemma is very much a worst-case bound for how much exploration we gain in each step in terms of the eigenvalues, and comes from subtleties of high-dimensional geometry. In most practical settings we would not expect to need as many steps as implied by that lemma.\n \nWe don't include all of the code due to space constraints, but the main algorithm corresponds to the algorithm in the paper pretty clearly as follows\n```\n\ndef bic_exploration(d, lambda_val, eps_d, c_d, cLA2, cLA4, K, cv, ell_star, ell0_mean):\n    kappa = max(1 / (lambda_val * cLA4), (4 * d * (K * np.sqrt(np.pi) + 1) * (1 + 1 / lambda_val)) / (cv ** 2 / (8 * np.pi)))\n    v_list = [np.eye(d)[0]]  # Start with e1\n    q_list = [[0]*int(kappa)]\n\n    # Initial exploration with e1\n    for i in range(int(kappa)):\n        q_list[0][i] = np.dot(v_list[0], ell_star)+ np.random.normal()  # reward proxy\n\n    t = int(kappa)\n    j = 0\n    M = lambda V: sum(np.outer(v, v) for v in V)\n    while np.min(np.linalg.eigvals(M(v_list))) \\le lambda_val:\n        eigvals, eigvecs = np.linalg.eigh(M(v_list))\n        idx = np.argsort(-eigvals)\n        lambdas = eigvals[idx]\n        w = eigvecs[:, idx].T\n        ell_lambda = np.sum(lambdas >= lambda_val)\n\n        a, t = initial_exploration(w, lambdas[:ell_lambda], v_list, q_list, t, cLA4, lambda_val, eps_d, c_d, K, ell_star, j+1)\n        while np.linalg.norm(a - w[:ell_lambda].T @ (w[:ell_lambda] @ a)) \\le np.sqrt(lambda_val):\n            a, t = exponential_growth(a, w, lambdas[:ell_lambda], v_list, q_list, t, ell0_mean, cLA2, lambda_val, ell_star, j+1)\n        v_list.append(a)\n        q_list.append([0]*int(kappa))\n        for i in range(int(kappa)):\n            q_list[-1][i] = np.dot(a, ell_star)+ np.random.normal()\n        t += int(kappa)\n        j += 1\n    return t\n```\n\n\n\n\n>*The paper focuses solely on the initial sampling exploration, and needs to be combined with Sellke 2023's result to have an end-to-end BIC algorithm. Thus, the contribution may seem a bit incremental.*\n\nWe respectfully disagree that the contribution is incremental. The key technical gap left open by Sellke 2023 was that its Thompson‑sampling stage becomes BIC only after collecting an **exponentially large** amount of initial data in the dimension d. Consequently, there was no sample‑efficient end‑to‑end algorithm in high dimensions prior to our work, and it was not clear whether such guarantees should even be possible.\n\n>*The paper did not explain the constants in assumption 2. Having more elaborate justification of what each constant means and how they should be chosen in practice would help with understanding these assumptions.*\n\nPropositions 4 and 5 both give examples of common distributions and associated constants for Assumption 2 that can be used in practice. We also include in Appendix B a more detailed discussion of the necessity for each of these constants and intuition for why we need these assumptions. While we unfortunately had to move this to the appendix for the submission, we are also happy to elaborate on this more in the body for the final version.\n\n\n>*Furthermore, do the authors have any insight on whether this initial sample complexity is tight or can it still be improved in the future?*\n\nThere is of course a trivial $\\lambda d$ lower bound on the number of samples needed to do $\\lambda$-exploration, so we also know that $poly(d)$ is the right rate. Closing the gap between our upper bound and the linear in $d$ lower bound is a very interesting question for future work! \n\nFurthermore, the examples discussed in Appendix B actually imply lower bounds on the number of samples necessary for exploration in terms of the parameters of Assumption 2. More formally, these examples imply the following three lower bounds. For proof sketches of these three lower bounds, please see the rebuttal to **Reviewer V6tS** (they are omitted here due to space constraints).\n\n**Lower bound $c_v:$** There exist instances (i.e. prior distributions) that require $\\Omega(1/c_v)$ samples for $1$-spectral exploration.\n\n**Lower bound $c_d:$** There exist instances that require $\\Omega(c_d)$ samples for $1$-spectral exploration.\n\n**Lower bound $\\epsilon_d:$** There exist instances that require $\\Omega(\\log(1/\\epsilon_d))$ samples for $1$-spectral exploration.\n\nThe three lower bounds described above give a more complete picture of how are algorithm is tight in a polynomial sense for these problem parameters. Furthermore, these results combined with Propositions 4-5 imply a stronger lower bound than just linear in $d$ for the distributions discussed in these propositions. We are very happy to include these more detailed discussions about problem-parameter lower bounds in the final version of the paper."}, {"review_id": "zlwDt4iX5O", "reviewer": "Reviewer_V6tS", "summary": "The paper studies the incentivized exploration problem in linear bandits, where a principal needs to gather information by recommending actions to a stream of myopic self-interested agents while remaining Bayesian Incentive Compatible (BIC).\nEarlier work (Sellke ’23) showed a hard instance in which the amount of data needed before one can safely switch to Thompson sampling could be exponentially many rounds. The authors show that this exponential barrier is not intrinsic under mild conditions. More specifically, when the action set is a unit ball, there exists an algorithm whose sample complexity is only polynomial in the dimension.", "questions": "- Can authors discuss the tightness of dependence on d?\n\n- What's the computational cost and memory cost of the proposed algorithms?\n\n- If the reward mean is not as a linear function but as a general function, can we get similar results under the same conditions? If not, what's could be the main challenges?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Given the hard result by (Sellke ’23), authors show that when the action set is a unit ball, there exists an algorithm which can break the exponential barrier under mild conditions. Authors present two illustrative examples that satisfy those conditions, including r-regular distributions and a type of log-concave distributions with a certain smoothness. To me, this finding is interesting since it opens some new problems, e.g., can we find a broader class of action sets?\n\n- The algorithm and subroutines are easy to follow. I appreciate the explanations and intuitions behind the algorithm design.\n\n- The paper is generally well-written and well-organized. Prior works are clearly contrasted.\n\nWeaknesses:\n\n- The main results rely on the unit ball assumption. Extending to general smooth convex bodies is hinted at but left open.\n\n- Though the sample complexity is polynomial in parameter d, it suffers large poly(d) factors. It could be helpful to discuss the tightness of dependence on d.\n\n- There is no discussion or analysis on the computational cost and memory cost.\n\nOther minors: \n\n- It could be better to split section 1.1 into two parts: one is problem setting and the other one shows your main results. Mixing them together seems to be a mess to me.\n\n- Adding a link of references and equations is helpful for readers. There is a ref issue in line 218 and 226, it should be Figure 1 instead of Figure 2.3.", "was_revised": true, "final_justification": "This paper makes solid theoretical contributions and all my concerns are addressed by authors in their rebuttal.", "rebuttal": "Thank you for your helpful comments and feedback. Below we address your specific questions:\n\n>*Can authors discuss the tightness of dependence on d?*\n\nThere is of course a trivial $\\lambda d$ lower bound on the number of samples needed to do $\\lambda$-exploration, so we also know that $poly(d)$ is the right rate. Closing the gap between our upper bound and the linear in $d$ lower bound is a very interesting question for future work! \n\nFurthermore, the examples discussed in Appendix B actually imply lower bounds on the number of samples necessary for exploration in terms of the parameters of Assumption 2. More formally, these examples imply the following three lower bounds, and we include a brief proof sketch of each below.\n\n\n\n**Lower bound $c_v:$** There exist instances  (i.e. prior distributions) that require $\\Omega(1/c_v)$ samples for $1$-spectral exploration.\n\n**Proof sketch**\nConsider the following example with $d=2$ and where the coordinates of $\\ell^\\ast$ are independent (and assume that $c_d < 1, \\epsilon_d < 1, c_v < 1$):\n\n$$\\\\ell^\\\\ast_1 = \\\\begin{cases}  -c_d & \\\\text{w.p. $\\epsilon_d$} \\newline       1 & \\\\text{w.p. $1-\\\\epsilon_d$} \\\\end{cases},\\\\quad\\\\quad\n\\\\ell^\\ast_2 = \\\\begin{cases}  -c_v & \\\\text{w.p. $1/2$} \\newline         c_v & \\\\text{w.p. $1/2$} \\\\end{cases}$$\n\nNote that if $E[\\ell_1^* \\mid \\psi] = 1-O(\\epsilon_d) \\ge  0.5$ for sufficiently small $\\epsilon_d$, then no optimal action will ever put weight more than $O(c_v)$ on the second coordinate because the magnitude of $\\ell_2^*$ is bounded by $c_v$. This implies that we must need $1/c_v$ steps in order to guarantee $1$-spectral exploration.\n\n$\\blacksquare$\n\n\n\n\n\n\n\n**Lower bound $c_d:$** There exist instances that require $\\Omega(c_d)$ samples for $1$-spectral exploration.\n\n**Proof Sketch**\n\nConsider the following example\n\n$$\\ell^\\ast_1 = \\begin{cases}  -c_d & \\text{w.p. $\\epsilon_d$}\\newline   2c_d & \\text{w.p. $2\\epsilon_d$} \\newline       1 & \\text{w.p. $1-3\\epsilon_d$} \\end{cases},\\quad\\quad\n\\ell^\\ast_2 = \\begin{cases}  -c_v & \\text{w.p. $1/2$}\\newline         c_v & \\text{w.p. $1/2$} \\end{cases}$$\n\nOnce again, the first action must be $e_1$. Furthermore, in this case we need $O(poly(1/c_d))$ actions of $e_1$ in order to decrease the conditional expectation of $\\ell^\\ast_1$ to be $0$, as we need this many samples to be able to effectively distinguish between $\\ell_1^* = -c_d$ and $\\ell_1^* = 2c_d$. This implies that we require $O(poly(1/c_d))$ samples to explore the second dimension in this example. \n$\\blacksquare$\n\n\n\n**Lower bound $\\epsilon_d:$** There exist instances that require $\\Omega(\\log(1/\\epsilon_d))$ samples for $1$-spectral exploration.\n\n\n**Proof sketch:** \n\nThis proof is more subtle and requires inductive control of the information gain on the 2nd coordinate. We provide a preparatory lemma and corollary. \n\n**Lemma**: let $L=±c$ be uniformly random for some $|c|≤1$. Suppose we receive noisy observations $r_i = s_i L + Z_i$ for a sequence $r_1,...$ that is adapted to the filtration $\\mathcal F_t$ generated by $(s_1,r_1,s_2,r_2,...,s_t,r_t)$. (I.e. the signal strengths $s_i$ may depend on the past.) Let $T_t=\\sum_{i=1}^t s_i^2$. Then the expected information gain on $L$ is at most $O(E[T_t])$.\n\n\nProof: this is a special case of observing Brownian motion with drift $L$ up to the random stopping time $T_t$. (Since observing $r_i = s_i L + Z_i$ is equivalent to observing Brownian motion with drift $L$ for time $s_i^2$, up to rescaling.) Let $Q_±(T_t)$ be the laws of Brownian motion with drifts $±c$ up to time $T_t$. By symmetry the expected information gain can be computed assuming $L=c$, and is bounded by\n\n$$\\begin{align}\n&E[KL(Q_+(T_t),[Q_+(T_t)+Q_-(T_t)]/2)]\n\\\\\n&\\stackrel{\\text{Convexity of KL}}{\\leq}\nE[KL(Q_+(T_t),Q_+(T_t))]\n+\nE[KL(Q_+(T_t),Q_{-}(T_t))]\n\\\\\n&\\leq \nE[T_t].\n\\end{align}$$\n\n\nHere we used $E[KL(Q_+(T_t)|Q_-(T_t))]=c^2 E[T_t]≤E[T_t]$ by Girsanov's theorem. $\\blacksquare$\n\n\n**Corollary**: in the setting of the previous lemma, let  $C_t = E[L|\\mathcal F_t] = E[L|(s_1,...,s_t,r_1,...,r_t)].$ Then $E[C_t^2] \\leq O(E[T_t])$.\n\nProof: This follows from the previous lemma: the expected relative entropy between the prior and posterior distributions of $L$ is precisely the information gain. In turn, the relative entropy is a strictly convex and even function of $C_t$ which is $\\Omega(C_t^2)$. $\\blacksquare$\n\n\n\nWe now return to the first example prior from the $c_v$ lower bound, and apply the Corollary to the observations of the 2nd coordinate. To make the application direct, whenever an action $(a_{1,t},a_{2,t})$ is played, we replace the noisy reward observation with separate observations for both $(a_{1,t},0)$ and $(0,a_{2,t})$ (with half the noise level, which only affects constant factors in the argument). This gives strictly more information since the two separate observations can be added to recover the original observation. \nWe let $C_t,\\mathcal F_t$ from above correspond to observations in the second coordinate.\n\n\nAt each time $t$, by Jensen's inequality on the convex function $f(x)=(1/3 - x)_+$, we see that for any signal $\\psi$:\n\n\n$$P[E[\\ell_1 | \\psi]≤1/2]\n\\leq \nO(E[f(E[\\ell_1 | \\psi])])\n\\leq \nO(E[f(\\ell_1)])\n\\leq \nO(\\epsilon_d).$$\n\n\nOn the main high-probability event that $E[\\ell_1 | \\psi]≥1/2$, the 2nd coordinate of $Exploit(\\psi)$ has absolute value at most $O(|C_t|)$. Via the Lemma and Corollary above, it follows that \n\n\n$$\\mathbb E[T_{t+1}] - \\mathbb E[T_t] ≤ O(\\mathbb E[T_t] + \\epsilon_d).$$\n\nNamely the case $\\{E[\\ell_1 | \\psi]≤1/2\\}$ contributes $O(\\epsilon_d)$ while the remaining case contributes $O(\\mathbb E[C_t^2])\\leq O(\\mathbb E[T_t])$.\n\n\nSince $T_0=0$, this implies by induction that \n\n\n$$\\mathbb E[T_t] ≤ e^{O(t)} \\epsilon_d.$$\n\n\nFinally note that we need $T_t ≥ 1$ for $1$-spectral exploration. Indeed, $1$-spectral exploration requires that the actions $a_1,\\dots,a_t$ satisfy\n$$\n\\sum_{i=1}^t \\langle a_t^{\\top}, M a_t\\rangle \n\\geq \nTr(M)\n$$\nfor all positive semi-definite matrices $M$, and taking $M=\\begin{pmatrix} 0 & 0 \\newline 0 & 1\\end{pmatrix}$ recovers the claim. In all this gives the desired $\\log(1/\\epsilon_d)$ lower bound. $\\blacksquare$\n\n\n\nThe three lower bounds described above give a more complete picture of how are algorithm is tight in a polynomial sense for these problem parameters. Furthermore, these results combined with Propositions 4-5 imply a stronger lower bound than just linear in $d$ for the distributions discussed in these propositions. We are very happy to include these more detailed discussions about problem-parameter lower bounds in the final version of the paper.\n\n>*What's the computational cost and memory cost of the proposed algorithms?*\n\n\nThe memory of the algorithms as-written scales linearly with the number of steps (which is of course polynomial in $d$), as the only information that needs to be stored are the action and reward from each step. The computational cost is also also polynomial in $d$, with the exception potentially of computing the function $f$ used in Line 4 of Algorithm 5. In our paper, we only prove the existance of such a function $f$. However, for many high-dimensional distributions (for example correlated Gaussians) this can be found in polynomial (in $d$) time using a simple linear program. In fact, for independent Gaussians (as in our experimental example), this $f$ can be directly computed in constant time without even needing a linear program. \n\nWe mention that this situation is similar to [Sellke-Slivkins 2023] in the $K$-armed setting, where the main algorithm is also shown to be efficient only in special cases. Their examples involve Beta prior distributions (see Appendix G therein) rather than Gaussians.\n\n>*If the reward mean is not as a linear function but as a general function, can we get similar results under the same conditions? If not, what's could be the main challenges?*\n\nThis is a great question, and indeed [Sellke 2023] briefly considers generalized linear bandits where a non-linear link function is applied to the inner product. The link function there is required to be strictly increasing with uniformly upper and lower bounded derivative. We do not see any conceptual barriers to extending our results to a similar class of functions, since the main property we rely on is the sensitivity of the optimal action with respect to the posterior mean reward. At the same time it is not straightforward and would require re-thinking many intermediate steps in the algorithm and analysis. (Both of these comments parallel the discussion at the end of page 3 of potentially generalizing to smooth non-spherical action sets.)"}, {"review_id": "9g6fDAbSER", "reviewer": "Reviewer_1V5y", "summary": "The paper \"Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts\" proposes to explore the problem of a planner that provides recommendations to selfish and rational agents that aim only to maximize their own expected reward based on its posterior. In order to minimize cumulative regret, the planner needs to incentivize exploration in its recommendations. However, if these recommandations are not in line with agent's own interest, they won't be followed and the process does not collect the expected exploration knowledge. The goal in the paper is to build a BIC planner as a linear bandit, which ensures that recommandations allow to cover the entire action space (in the sense of the \\lambda-spectral exploration following [Sellke et al., 2023]. The proposal strongly build on  [Sellke et al., 2023], that proposes to divide the process in two steps of pure exploration followed by a Thompson Sampling procedure. The core idea is that after enough free exploration steps, where the agent has no information at all to decline the recommandation, the parameter posterior is sufficiently concentrated to make sampled recommendations always the most credible from the agent's perspective. Authors show that under some assumptions over the actions space and rewards distribution, the length of the exploration phase can be significantly reduced. More specifically, they propose an algorithm that performs exploration coverage without greatly fewer initial steps of initial data collection.", "questions": "see strengths and weaknesses", "limitations": ".", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths : \n- Significant theoretical contribution (I did not check all the proofs though)\n\nWeaknesses :\n\n- The paper is only theoretical. It would have been very useful to get some experimental results of the proposed algorithm, both for use cases comprehension and also to capture the benefits of the proposal in various settings, including some of them not fully respecting working assumtpions\n- Lack of pedagogy: the setting is not clearly / formally defined. For readers that do not know the incentivized exploration problem, it is very hard to capture what are the objectives of this kind of problem. I had to read [Sellke, 2023] to understand the problem, what is given to agents, what is the goal, etc. In comparison [Sellke, 2023] is far more clear in presenting the problem. \n- Beyond the lack of formal presentation of the problem, the paper also uses many notations that are never defined : e.g.,  the symbol used for positive semidefinite partial order on symmetric matrices (I had to find it in Sellke, 2023), the symbol used to define product tensors at order 2, $\\Omega$, etc\n- While I find the problem theoretically interesting, I am not fully convinced by its real interest for pratical applications, as users can interact multiple times, have their own interests, their own history, the knowledge and understanding of the planner's algorithm, etc. Practical uses should be more discussed in the paper.  \n- The central assumption of the algorithm is that actions live in a d-dimentionnal unit ball. Isn't it limitative for some applications ? And more importantly, in that setting what would justify a prior that would not be uniform over every vector from that ball ? This can be very limitative for the paper if no reasonnable pratical justification for this  can be found since taking a fully non informative prior is a trivial setting, for which TS is BIC without any initial exploration phase. Or am I wrong on this point ?", "was_revised": true, "final_justification": "After discussions with the authors I think the paper can be useful for the community, despite some lack of pedagogy in its current form.  \nI raised my score to 4, assuming the authors implement the presentation improvements discussed in their final version of the paper.", "rebuttal": "Thank you for your helpful comments and feedback. Below we address your specific questions:\n\n>The paper is only theoretical. It would have been very useful to get some experimental results of the proposed algorithm [...]\n\nFirst, we want to emphasize that the main contribution and algorithm of this paper are theoretical and show that it is possible to explore every dimension in $poly(d)$ time. That being said, the algorithm itself is relatively simple to implement. Due to the interest from reviewers, we implemented our main algorithm (Algorithm 1) along with the two helper algorithms (Algorithms 2 and 3) in Python (which only takes ~100 lines of code). We then tested the algorithm on synthetic data with varying dimensions when the prior distribution is a $d$-dimensional Gaussian that is independent across dimensions and has mean $1$ in the first dimension and mean $0$ in all other dimensions. Note that our algorithm also can be applied to prior distributions with dependencies between coordinates, however we ran experiments for the independent case as this simplifies the code significantly (and also matches the independent priors in [Sellke-Slivkins 2023]). For this simple setting, we run our algorithm with $\\epsilon_d = 0.1$, $c_d = 1$, $K= 1$, and $c_v = 1$. \n\nOf course, the bound in Theorem 3 is a worst-case bound on the sample complexity, and therefore we would expect that on most instances of the problem the number of steps is significantly less than that upper bound. Furthermore, we note that the constants in our algorithm are certainly not optimal for this specific instance of the problem, yet these (relatively large) constants are what allows our theoretical results to hold for any prior distribution. While we are unable to load a graph in this rebuttal, we ran our algorithm for values of $d$ ranging from $d = 1$ to $d = 24$, and sampled $\\ell^*$ from the prior distribution 100 times for each value of $d$ and then calculated the number of samples necessary to achieve $\\lambda$-spectral exploration. The results show a clear quadratic dependence of the sample complexity on the dimension, and quartic scaling for the running time.\n\n| Dimension | Sample Complexity   | Time (seconds)     | Sample Complexity / $d^2$         | Time/$d^4$         |\n|----|--------|--------|--------|------------|\n| 2  | 5132   | 0.02   | 1283.00| 1.2e-03    |\n| 3  | 11781  | 0.06   | 1309.00| 7.7e-04    |\n| 4  | 21145  | 0.17   | 1321.56| 6.6e-04    |\n| 5  | 32614  | 0.38   | 1304.56| 6.0e-04    |\n| 6  | 47121  | 0.82   | 1308.92| 6.4e-04    |\n| 7  | 64278  | 1.51   | 1311.80| 6.3e-04    |\n| 8  | 84107  | 2.49   | 1314.17| 6.1e-04    |\n| 9  | 106573 | 5.43   | 1315.72| 8.3e-04    |\n| 10 | 131696 | 6.19   | 1316.96| 6.2e-04    |\n| 11 | 159505 | 10.34  | 1318.22| 7.1e-04    |\n| 12 | 189954 | 14.30  | 1319.13| 6.9e-04    |\n| 13 | 223085 | 20.67  | 1320.03| 7.2e-04    |\n| 14 | 258838 | 26.72  | 1320.60| 7.0e-04    |\n| 15 | 297248 | 35.88  | 1321.10| 7.1e-04    |\n| 16 | 338359 | 46.61  | 1321.71| 7.1e-04    |\n| 17 | 382100 | 57.79  | 1322.15| 6.9e-04    |\n| 18 | 428515 | 74.51  | 1322.58| 7.1e-04    |\n| 19 | 477573 | 93.26  | 1322.92| 7.2e-04    |\n| 20 | 529270 | 114.13 | 1323.18| 7.1e-04    |\n| 21 | 583683 | 137.98 | 1323.54| 7.1e-04    |\n| 22 | 640716 | 168.16 | 1323.79| 7.2e-04    |\n| 23 | 700428 | 201.52 | 1324.06| 7.2e-04    |\n| 24 | 762755 | 241.09 | 1324.23| 7.3e-04    |\n\nWe do want to emphasize that for a specific instance of our problem (i.e. a specific prior), a user could tune the worst-case constants used in the algorithm to get faster $\\lambda$-spectral exploration. However, the above table just uses the default constants of the algorithm with the goal of showing that \n- the algorithm is implementable in relatively few lines of python code\n- the algorithm is efficient to run for reasonably large values of $d$\n- in practice, the number of steps grows polynomially in $d$ at a much better rate than the worst-case bound in our theoretical results (in this experiment we see a roughly quadratic relationship between the dimension and the number of steps). We are  happy to add this result to the final version of our paper with more details about the implementation and with graphs showing the trends. \n - Please refer to the rebuttal to **Reviewer Rjs1** for a code snippet (not included here due to char limit).\n\n>Lack of pedagogy: the setting is not clearly / formally defined. For readers that do not know the incentivized exploration problem, it is very hard to capture what are the objectives of this kind of problem. [...] Beyond the lack of formal presentation of the problem, the paper also uses many notations that are never defined [...]\n\nWe sincerely apologize for this. Paralleling [Sellke 2023], we will add clearer presentation, motivation and other discussion for the problem formulation, as well as definitions of these notations, to the final version of the paper.\n\n>While I find the problem theoretically interesting, I am not fully convinced by its real interest for pratical applications, as users can interact multiple times, have their own interests, their own history, the knowledge and understanding of the planner's algorithm, etc)\n\nWe agree that the constant arrival of new agents is a strong assumption in works on Bayesian Incentive Compatible algorithms. Firstly, there is a substantial literature on more realistic models of incentivized exploration, incorporating e.g. agent heterogeneity ([IMSW 19]) and partial data disclosure ([IMSW 20]) and other references from the introduction. Actually the fact that we consider linear bandits makes our work more realistic than the original finite-armed bandit models used to study incentive compatibility. In any case, for theoretical understanding it is also valuable to understand simple models, as they can inform a wide range of more realistic models which each have their own quirks. For example, covariate diversity among agents is generally understood to aid exploration (see e.g. the paper *Mostly Exploration-Free Algorithms for Contextual Bandits*). Thus we expect the simple nature of our setting to only make the problem harder, meaning that our algorithms could be potentially finetuned and/or streamlined if the model were refined to be more realistic. We are happy to add more discussion of these points, including potential caveats and further citations to related works that study various problem setting. \n\nRegarding applications, many modern online platforms recommend products to customers, for example an online retailer recommends certain products for a consumer to buy. The customers can then choose to accept the recommendation and buy the product or ignore the recommendation and buy a different product. The goal of the platform is to learn the optimal product to recommend based on customer feedback. However, if customers ignore the platform’s recommendation based on a prior belief that another option is better, then the platform may be unable to learn efficiently. This motivates our studying of Bayesian Incentive Compatible algorithms, i.e. algorithms that make recommendations in a way that incentivizes the customers to always follow the platform’s recommendation. Other similar instances of this problem are in mobile health applications that make recommendations to patients that patients can choose to follow or ignore. As mentioned at the start of [Sellke 2023], the BIC property also implies that \"exploration helps everyone\"; this may be especially relevant for reliability in health applications as a codification of the Hippocratic Oath. We will add further discussion of this point in the paper.\n\n>The central assumption of the algorithm is that actions live in a d-dimentionnal unit ball. Isn't it limitative for some applications ? And more importantly, in that setting what would justify a prior that would not be uniform over every vector from that ball ? This can be very limitative for the paper if no reasonnable pratical justification for this can be found since taking a fully non informative prior is a trivial setting, for which TS is BIC without any initial exploration phase. Or am I wrong on this point ?\n\nFirst, we want to clarify: it is definitely **not known** that Thompson Sampling is BIC on its own for spherical action sets and uniform priors, even though all arms have the same mean reward under the prior. The **only** bandit setting where this kind of result has been proved is for discrete action sets with independent priors across the arms (in [Sellke-Slivkins 2023]). The proof there applies correlation inequalities to the increments of two Doob martingales, and strongly makes use of this independence. The work [HNSW22] follows up on [Sellke-Slivkins 2023] considers combinatorial semi-bandits (where actions are sets of multiple arms) but does not include a result of this type. [Sellke 2023] considers linear bandits and provides a **counterexample** showing the Thompson sampling may be BIC at time 1 but not time 2. It is plausible that a linear bandit extension of this result is true under some rotational symmetry conditions, but it would be a new, very interesting theorem. \n\nRegarding the prior, note that in our setting the prior encapsulates the knowledge that a fresh agent enters the system with. Thus in modeling, **the prior should take into account all publicly available knowledge**. For example, the publication of a scientific paper or news article related to some of the actions should certainly influence the prior. While it might be challenging to describe exactly the correct prior to use in a particular real-life setting, we believe this illustrates the need for flexibility in handling rather general priors. Note that using a completely wrong prior means that the BIC guarantees we pursue are rendered invalid. This is in contrast with ordinary bandit problems, where the only downside to using a simpler prior is potentially slower learning in the early stages."}, {"review_id": "YM2h8rWrm8", "reviewer": "Reviewer_8Eaz", "summary": "The paper considers how geometric conditions can help the initial exploration phase. They use a Bayesian framework and some not-that-intuitive algorithms to prove a polynomial complexity. It avoids exponential dependency.", "questions": "Can you provide more motivation and any potential applications of the problem?\n\nDo you have any results of corresponding lower bounds? Lower bounds can make the paper sound and more complete.\n\nThe results heavily rely on the agents being myopic. However, in practice, some agents may consider future revenue and misreport now. In other words, they may sacrifice current revenue to mislead the planner. Could you discuss the importance of this assumption and any potential difficulty extending the existing results?\n\nThe authors don't provide any experiments. Even a simulation comparing their algorithms and existing algorithms will improve the paper significantly.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The problem is interesting and important to learning theory. In my opinion, the results are non-trivial and inspiring. However, the paper lacks enough comparison of existing literature; for example, more discussion on \"Incentivizing Exploration with Linear Contexts and Combinatorial Actions\" is needed. I'm looking forward to a new but small section about the difference (new results under what conditions) between the paper and others.", "was_revised": true, "final_justification": "I think the authors address most of my concerns. I hope they can give a rigorous proof of the lower bound in the final version. Based on these, I keep my score.", "rebuttal": "Thank you for your helpful comments and feedback. Below we address your specific questions:\n\nFirst, we will happily provide more discussion on the related work in the final version of the paper and apologize for the initial confusion.\n\n>*Can you provide more motivation and any potential applications of the problem?*\n\n\nMany modern online platforms recommend products to customers, for example an online retailer recommends certain products for a consumer to buy. The customers can then choose to accept the recommendation and buy the product or ignore the recommendation and buy a different product. The goal of the platform is to learn the optimal product to recommend based on customer feedback. However, if customers ignore the platform’s recommendation based on a prior belief that another option is better, then the platform may be unable to learn efficiently. This motivates our studying of Bayesian Incentive Compatible algorithms, i.e. algorithms that make recommendations in a way that incentivizes the customers to always follow the platform’s recommendation. Other similar instances of this problem are in mobile health applications that make recommendations to patients that patients can choose to follow or ignore. As mentioned at the start of [Sellke 2023], the BIC property also implies that \"exploration helps everyone\"; this may be especially relevant for reliability in health applications as a codification of the Hippocratic Oath. We will add further discussion of this point in the paper.\n\n\n\n>*Do you have any results of corresponding lower bounds? Lower bounds can make the paper sound and more complete.*\n\nThere is of course a trivial $\\lambda d$ lower bound on the number of samples needed to do $\\lambda$-exploration, so we also know that $poly(d)$ is the right rate. Closing the gap between our upper bound and the linear in $d$ lower bound is a very interesting question for future work! \n\nFurthermore, the examples discussed in Appendix B actually imply lower bounds on the number of samples necessary for exploration in terms of the parameters of Assumption 2. More formally, these examples imply the following three lower bounds. For proof sketches of these three lower bounds, please see the rebuttal to **Reviewer V6tS** (they are omitted here due to space constraints).\n\n**Lower bound $c_v:$** There exist instances (i.e. prior distributions) that require $\\Omega(1/c_v)$ samples for $1$-spectral exploration.\n\n**Lower bound $c_d:$** There exist instances that require $\\Omega(c_d)$ samples for $1$-spectral exploration.\n\n**Lower bound $\\epsilon_d:$** There exist instances that require $\\Omega(\\log(1/\\epsilon_d))$ samples for $1$-spectral exploration.\n\nThe three lower bounds described above give a more complete picture of how are algorithm is tight in a polynomial sense for these problem parameters. Furthermore, these results combined with Propositions 4-5 imply a stronger lower bound than just linear in $d$ for the distributions discussed in these propositions. We are very happy to include these more detailed discussions about problem-parameter lower bounds in the final version of the paper.\n\n>*The results heavily rely on the agents being myopic. However, in practice, some agents may consider future revenue and misreport now. In other words, they may sacrifice current revenue to mislead the planner. Could you discuss the importance of this assumption and any potential difficulty extending the existing results?*\n\nWhen there is a steady arrival of new agents interacting with the platform, we generally expect rational agents to act myopically (without trying to mislead the planner). This is because even if a single agent does interact with the platform multiple times, that agent is still one of many agents that the platform observes, and therefore that agent will have a very small affect on the planner. Intuitively, this suggests it should be hard for that single agent to act strategically in a way that is very advantageous for their own future interactions. \n\n\nWe do also agree that the constant arrival of new agents is a strong assumption in works on Bayesian Incentive Compatible algorithms. Indeed there is a substantial literature on more realistic models of incentivized exploration, incorporating e.g. agent heterogeneity ([IMSW 19]) and partial data disclosure ([IMSW 20]) and other references from the introduction. Actually the fact that we consider linear bandits is another step in this direction, as it makes our work more realistic than the finite-armed bandit models originally used to study incentive compatibility. In any case, for theoretical understanding it is also valuable to understand simple models, as they can inform a wide range of more realistic models which each have their own quirks. For example, covariate diversity among agents is generally understood to aid exploration (see e.g. the paper *Mostly Exploration-Free Algorithms for Contextual Bandits*). We thus expect the lack of agent-specific contexts in our setting to only make the problem harder, i.e. our algorithm could be potentially finetuned and/or streamlined to take further advantage of such information. We are happy to add more discussion of these points, including potential caveats and further citations to related works that study various problem settings. \n\n\n>*The authors don't provide any experiments. Even a simulation comparing their algorithms and existing algorithms will improve the paper significantly.*\n\nFirst, we want to emphasize that the main contribution and algorithm of this paper are theoretical and show that it is possible to explore every dimension in $poly(d)$ time. Furthermore, there **are no** existing algorithms for this problem. That being said, the algorithm itself is relatively simple to implement. Due to the interest from reviewers, we implemented our main algorithm (Algorithm 1) along with the two helper algorithms (Algorithms 2 and 3) in Python (which only takes ~100 lines of code). We then tested the algorithm on synthetic data with varying dimensions when the prior distribution is a $d$-dimensional Gaussian that is independent across dimensions and has mean $1$ in the first dimension and mean $0$ in all other dimensions. Note that our algorithm also can be applied to prior distributions with dependencies between coordinates, however we ran experiments for the independent case as this simplifies the code significantly (and also matches the independent priors in [Sellke-Slivkins 2023]). For this simple setting, we run our algorithm with $\\epsilon_d = 0.1$, $c_d = 1$, $K= 1$, and $c_v = 1$. \n\nOf course, the bound in Theorem 3 is a worst-case bound on the sample complexity, and therefore we would expect that on most instances of the problem the number of steps is significantly less than that upper bound. Furthermore, we note that the constants in our algorithm are certainly not optimal for this specific instance of the problem, yet these (relatively large) constants are what allows our theoretical results to hold for any prior distribution. While we are unable to load a graph in this rebuttal, we ran our algorithm for values of $d$ ranging from $d = 1$ to $d = 24$, and sampled $\\ell^*$ from the prior distribution 100 times for each value of $d$ and then calculated the number of samples necessary to achieve $\\lambda$-spectral exploration. The results show a clear quadratic dependence of the sample complexity on the dimension, and quartic scaling for the running time.\n\n| Dimension | Sample Complexity   | Time (seconds)     | Sample Complexity / $d^2$         | Time/$d^4$         |\n|----|--------|--------|--------|------------|\n| 2  | 5132   | 0.02   | 1283.00| 1.2e-03    |\n| 3  | 11781  | 0.06   | 1309.00| 7.7e-04    |\n| 4  | 21145  | 0.17   | 1321.56| 6.6e-04    |\n| 5  | 32614  | 0.38   | 1304.56| 6.0e-04    |\n| 6  | 47121  | 0.82   | 1308.92| 6.4e-04    |\n| 7  | 64278  | 1.51   | 1311.80| 6.3e-04    |\n| 8  | 84107  | 2.49   | 1314.17| 6.1e-04    |\n| 9  | 106573 | 5.43   | 1315.72| 8.3e-04    |\n| 10 | 131696 | 6.19   | 1316.96| 6.2e-04    |\n| 11 | 159505 | 10.34  | 1318.22| 7.1e-04    |\n| 12 | 189954 | 14.30  | 1319.13| 6.9e-04    |\n| 13 | 223085 | 20.67  | 1320.03| 7.2e-04    |\n| 14 | 258838 | 26.72  | 1320.60| 7.0e-04    |\n| 15 | 297248 | 35.88  | 1321.10| 7.1e-04    |\n| 16 | 338359 | 46.61  | 1321.71| 7.1e-04    |\n| 17 | 382100 | 57.79  | 1322.15| 6.9e-04    |\n| 18 | 428515 | 74.51  | 1322.58| 7.1e-04    |\n| 19 | 477573 | 93.26  | 1322.92| 7.2e-04    |\n| 20 | 529270 | 114.13 | 1323.18| 7.1e-04    |\n| 21 | 583683 | 137.98 | 1323.54| 7.1e-04    |\n| 22 | 640716 | 168.16 | 1323.79| 7.2e-04    |\n| 23 | 700428 | 201.52 | 1324.06| 7.2e-04    |\n| 24 | 762755 | 241.09 | 1324.23| 7.3e-04    |\n\nWe do want to emphasize that for a specific instance of our problem (i.e. a specific prior), a user could tune the worst-case constants used in the algorithm to get faster $\\lambda$-spectral exploration. However, the above table just uses the default constants of the algorithm with the goal of showing that \n- the algorithm is implementable in relatively few lines of python code\n- the algorithm is efficient to run for reasonably large values of $d$\n- in practice, the number of steps grows polynomially in $d$ at a much better rate than the worst-case bound in our theoretical results (in this experiment we see a roughly quadratic relationship between the dimension and the number of steps). We are  happy to add this result to the final version of our paper with more details about the implementation and with graphs showing the trends."}]

Author rebuttal:

Meta-review: Previous work, Selke 2023, studied incentivized exploration in linear bandits and proposed Thompson sampling as an exploration method. An unfortunate property of this algorithm is that it requires a number of initial samples that is exponentially large in the dimension before it becomes BIC (Bayesian Incentive Compatible). The current paper addresses this gap, proposing a new method for generating initial samples that becomes BIC after a polynomial number of samples.

Strengths 
- The improvement over Selke is significant 
- The initial sampling algorithm and its analysis is novel
- The paper is well written, including clear proof sketches, and there is a good discussion of prior work

Weaknesses
- The paper did not include any experiments, though the authors addressed this in their rebuttal
- The reviewers had some questions about the relevance of incentivized exploration to practice and whether the assumptions (e.g., of a linear bandit) restrict the applicability. It is worth observing that incentivized exploration of linear bandits is a well-accepted problem. It and similar problems have been studied by a number of researchers and is generally viewed as important from a theoretical perspective, even if the current level of applicability is not as high as with some other parts of the bandit literature.
- The reviewers identified some opportunities to improve clarity, which were discussed in the rebuttal.

Overall, this is a solid theory paper addressing an important gap in the literature. It is of note that the two reviewers who engaged with the paper most closely and who are most familiar with this part of the literature rated it both 5.  I am recommending acceptance.
Decision: Accept (spotlight)