Nash Regret Guarantees for Linear Bandits
Authors: Ayush Sawarni
Soumyabrata Pal
Siddharth Barman
Venue: NeurIPS 2023 poster (2023)
Keywords: Sub-Poisson Distribution
Nash Social Welfare
Fairness Quantification
John Ellipsoid
Kiefer-Wolfowitz Optimal Design
Algorithmic Game Theory
Online Learning

Abstract: We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening---referred to as Nash regret---is defined as the difference between the (a priori unknown) optimum and the geometric mean of expected rewards accumulated by the linear bandit algorithm. Since the geometric mean corresponds to the well-studied Nash social welfare (NSW) function, this formulation quantifies the performance of a bandit algorithm as the collective welfare it generates across rounds. NSW is known to satisfy fairness axioms and, hence, an upper bound on Nash regret provides a principled fairness guarantee.    

We consider the stochastic linear bandits problem over a horizon of $\mathsf{T}$ rounds and with a set of arms ${\cal X}$ in ambient dimension $d$. Furthermore, we focus on settings in which the stochastic reward---associated with each arm in ${\cal X}$---is a non-negative, sub-Poisson random variable. For this setting, we develop an algorithm that achieves a Nash regret of $O\left( \sqrt{\frac{d}{\mathsf{T}}} \log(\mathsf{T} |{\cal X}|)\right)$. In addition, addressing linear bandit instances in which the set of arms ${\cal X}$ is not necessarily finite, we obtain a Nash regret upper bound of $O\left( \frac{d^\frac{5}{4}}{\sqrt{\mathsf{T}}}  \log(\mathsf{T})\right)$. Since bounded random variables are sub-Poisson, these results hold for bounded, non-negative rewards. Our linear bandit algorithm is built upon the successive elimination method with novel technical insights, including tailored concentration bounds and the use of sampling via John ellipsoid in conjunction with the Kiefer–Wolfowitz optimal design.

Nash Regret Guarantees for Linear Bandits
Ayush Sawarni Indian Institute of Science Bangalore savarniayush@gmail. com
Soumyabrata Pal Google Research Bangalore soumyabrata@google.com
Siddharth Barman Indian Institute of Science Bangalore
barman@iist ac.
Abstract
We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening-reeereee regret-is defined as the difference between the (a priori unknown) optimum and the geometric mean of expected rewards accumulated by the linear bandit algorithm. Since the geometric mean corresponds to the well-studied Nash social welfare (NSW) function, this formulation quantifies the performance as the collective welfare it generates across rounds. NSW is known to satisfy fairness axioms and, hence, an upper bound on Nash regret provides a principled fairness guarantee.
Nash
bandit algorithm
We consider the stochastic linear bandits problem with set of arms X' in ambient dimension d. Furthermore, we focus on settings in with each arm in X' a non-negative,
horizon of T rounds and
which the stochastic y-sub-Poisson random variable. For this setting, we develop an algorithm that
achieves a Nash regret O (V4 log(T In addition, addressing linear bandit instances in which the set of arms N' is not necessarily finite, obtain a
Nash regret upper bound of O ditt log(T) Since bounded random variables
are sub-Poisson, these results hold for bounded, positive rewards. Our linear bandit algorithm is built upon the successive elimination method with novel technical insights, including tailored concentration bounds and the use sampling via John ellipsoid in conjunction with the Welffr-Wolfooizz optimal design.
Introduction
Bandit optimization is prominent framework for sequential decision making and has several applications across multiple domains, such as healthcare [26] 23 27 and advertising [22]. this framework, have set of arms (possible actions) with unknown means and time horizon. The goal is to sequentially pull the arms such that the regret- which is a notion loss defined over the bandit instance-is minimized.
We consider settings wherein the stochastic rewards generated by a sequential algorithm induces welfare across a population of agents. Specifically, there are agents, arriving one per round; in particular, the reward accrued at each round E [T] corresponds to the value accrued by the agent. Indeed, such a welfarist connection exists in various applications of the bandit framework. Consider, for instance, available drugs. In each round E [T], one of the available drugs is administered to the tt patient. Subsequently, the reward accrued at the 7th round corresponds to the efficacy of the administered drug to the th patient. In such a setting, fairness is fundamental consideration. That is, in addition to cumulative efficacy, individual effectiveness of the drugs is quite important.
classic context of drug trials (24]: Suppose there are patients and several
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

A central notion in the bandit literature is that of average regret, defined as the difference between the priori unknown) optimum and the arithmetic mean of the expected rewards (accumulated by the algorithm) 4 However, average regret fails to capture the fairness criterion that the rewards should be balanced (across the agents) and not just cumulatively high. From a welfarist viewpoint, the standard notion of (average) regret equates the algorithm's 's performance to the social welfare it induces. Social welfare is defined as the sum of agent's 's rewards [19] and can be high among a set of agents even if' fraction of them receive indiscriminately low rewards. For instance, in the drug-trials example provided above, high average efficacy (i.e., high social welfare) does not rule out severely ineffective outcome for a subset of agents.
Given that average regret is defined using the sum of expected rewards, this notion inherits this utilitarian limitation of social welfare. In summary, in welfare-inducing contexts, bandit algorithm with low average regret not guaranteed to induce fair outcomes across rounds.
Addressing this issue and with the overarching aim of achieving faireess across rounds (i.e., across agents that receive rewards from bandit algorithm), the current work considers a strengthened to as Nash regret-is defined as the difference between
notion of regret. The strengthening--eeiceee the priori unknown) optimum and the geometric mean of expected rewards induced by the bandit algorithm. It is relevant to note that the geometric mean (of rewards) corresponds to the Nash social welfare (NSW) function
[9] This welfare function has been extensively studied in mathematical [19) and is known to satisfy fundamental faimess axioms, including the Pigou-
economics (see, e.g., Dalton transfer principle, scale invariance, and independence of unconcerned agents. Hence, by definition, Nash regret quantifies the performance of bandit algorithm as the NSW it generates.
Quantitatively speaking, in order for the geometric mean (i.e., the NSW) to be large, the expected reward at every round should be large enough. The AM-GM inequality also highlights that Nash regret is more demanding objective that average regret.
We obtain novel results for Nash regret in the stochastic linear bandits framework. In this well-studied bandit setup each arm corresponds unknown arm means are modelled to be a linear function of x. With a focus on average regret, stochastic linear bandits have been extensively studied in the past decade [ 21). The current paper extends the line of work on linear bandits with fairness and welfare considerations.
d-dimensional vector (an spe-ifeciiic context) and the
Note that an ostensible approach for minimizing Nash regret is to take the logarithm of the observed rewards and, then, solve the average regret problem. However, this approach has the following shortcomings: (i) Taking log implies the modified rewards can have very large range possibly making the regret vacuous, and (ii) This approach leads to a multiplicative guarantee and not an additive one. In recent work of [5], the authors study Nash regret in the context of stochastic multi-armed bandits (with bounded rewards) and provide optimal guarantees. The current work notably generalizes this prior work to linear bandits.
1.1 Our Contributions and Techniques
We consider the stochastic linear bandits setting with a set of arms X' over a finite horizon of T rounds. Since we consider the welfarist viewpoint, we assume that the rewards across the rounds are positive and, in particular, model the distribution of the arm rewards to be p-sub-Poisson for parameter v E RR.. Our goal to minimize the Nash regret NRT.
We develop a novel algorithm LINNASH that obtains essentially optimal Nash regret guarantees for this setting. Specifically, for finite set of arms X' C Rdd our algorithm LINNASH achieves Nash
regret NRT = O (V dv log log(T))1)) For infinite sets of arms, a modified version of LINNASH
achieves Nash regret NRT = O d VT
log(T) log(T))
Recall that Nash regret is strengthening of the average regret; the AM-GM inequality implies that, for any bandit algorithm, the Nash regret is at least as much as its average regret. Hence, in the linear bandits context, the known Q (d/vT) lower bound on average regret (see [17, Chapter 24) holds

---

for Nash regret well This observation implies that, up to a logarithmic factor, our upper bound on Nash regret is tight with respect to the number of rounds T. We also note that for instances which the number of arms | = w(2"), the Nash-regret dependence on d has a slight gap. Tightening this gap is an interesting direction of future work.
We note that bounded, positive random variables are sub-Poisson (Lemma] I]. Hence, our results hold for linear bandit instances wherein the stochastic rewards are bounded and positive. This observation also highlights the fact that the current work is generalization of the result obtained in [.. In addition, notice that, by definition, Poisson distributions are 1-sub-Poisson. Hence, our guarantees further hold of rewards that are not necessarily sub- Gaussian. Given the recent interest in obtaining regret guarantees bevond Gau-Sausiian rewards [8] 33. our study of sub- uub-Poisson rewards is interesting in its own right
Our linear bandit algorithm, LINNASH, has two parts. In the first part, we develop novel approach of sampling arms such that in expectation the reward obtained is a linear function of the center of John Ellipsoid [I3]. Such a strategy ensures that the expected reward in any round of the first part is sufficiently large. The second part of LINNASII runs in phases of exponentially increasing length. In distribution that is obtained as a solution of concave optimization problem, known as D-optimal design. We construct confidence intervals at each phase and eliminate sub-optimal arms. key novelty in our algorithm and analysis the use of confidence widths that are estimate dependent. We define these widths considering multiplicative forms of concentration bounds and crucially utilize the sub-Poisson property of the rewards. The tail bounds we develop might be of independent interest.
each phase, we sample arms according
1.2 Other Related Work
There has been a recent surge in interest achieve fairness guarantees in the context of multi-armed bandits; see, e.g., 14 7 20 6 [2]. However, these works mostly consider fairness across arms and, in particular, impose fairness constraints that require each arm to be pulled pre-specified fraction of times. By contrast, our work considers fairness across rounds.
Alternative Regret Formulations. In the current work, for the welfare computation, each agent t's value is considered as the expected reward round f. One can formulate stronger notions of regret by, say, considering the expectation of the geometric mean of the rewards, rather than the geometric mean of the expectations. However, as discussed in [5), is not possible to obtain non-trivial guarantees for such reformulations in general: every arm must be pulled at least once. Hence, if one considers the realized rewards (and not their expectations), even a single pull of a zero-reward arm will render the geometric mean zero
2 Problem Formulation and Preliminaries
We will write [m] to denote the set (1, ..]. For a matrix X, let Det(X) to denote the determinant of X. For any discrete probability distribution À with sample space S2 write SApp(A) - {o E Ω Prx-A {X- 2 > 0} to denote the points for which the probability mass assigned by À is positive. For vector
Rd and positive definite matrix V Rdd we will denote ||ally : Va'Vaa Finally, let B {- Rd
||ا||| = 1} be the d-dimensional unit ball.
We address the problem of stochastic linear bandits with a time horizon of T e Z, rounds. Here, an online algorithm (decision maker) is given set of arms X' C Rd Each arm corresponds to d-dimensional vector. Furthermore, associated with each arm x E X, we have a stochastic reward To R4. In the linear bandits framework, the expected value of the reward ru is modeled to be linear function of x E RRd. In particular, there exists an unknown parameter vector 0" E IRd such that, for each X, the associated reward's expected value E/ra] (Ir, 0*). Given the focus on welfare contexts, we will, throughout, assume that the rewards are positive, Tz >> 0, for all x E X.
The online algorithm (possibly randomized) must sequentially select an arm X₂ in each round t [T] and, then, it observes the corresponding (stochastic) reward rx, > 0 For notational convenience,
'This lower bound on average regret is obtained for instances in which the set of arms X are the corners of a hypereube [17].
An intersection between sub- Gaussian and sub- Poisson distribution classes is identified Lemma
Note that, for randomized online algorithm, the selected arm X, is random variable.
3

---

we will write 72 to denote r.x, In particular, if in round t the selected arm X; = 2, then the expected reward is (x, 8²),)))))))))) i.e. Eir, X; x| (z. 8*). We will, throughout, use x¹ to denote the optimal arm, x=' = arg max e 8*) and 8 to denote estimator of l"
In the stochastic linear bandits framework, our overarching objective is to minimize the Nash regret, defined as follows:
1/T
[[E
NRT
max (sc, 0*) ze
Note that the definition of Nash regret is obtained by applying the Nash social welfare (geometric mean) onto ex ante rewards, E (X,, 0*) accrued across the T rounds.
2.1 Sub-Poisson Rewards
In order to model the environment with positive rewards (r, > 0), we assume that the rewards ra associated with the arms x E are v-sub Poisson, for some parameter > 0. Formally, their moment-generating function satisfies the following bound
E
[+] r+] S exp [v-'E(r,] (d"A-1)) 1)) exp (v- 0*) (e 11) for all E R.
(2)
Note that a Poisson random variable 1-sub Poisson. To highlight the generality of u-sub-Poisson distributions, we note that bounded, non-negative random variables are sub-Poisson (Lemma D Further, Lemma we establish a connection between non-negative sub-Gaussian and sub-Poisson random variables.
Lemma 1. Any non-negative random variable X E B) is B-sub-Poisson, i.e. if mean [E[] = 44. then for all R. we have E[e>X] S exp (B-+ 11).
Lemma 2. Let X be non-negative nab-Gaussian random variable X with mean μ E[X] and norm Then, X is also
-ubb-Piisoo.
The proofs of Lemmas and appear in Appendix A Lemma has useful instantiations. In particular, the lemma implies that the half-normal random variable. with variance of ar, is also a -usi-sso-ooss,,,,, where C' is a constant (independent of distribution parameters). Similarly, for other well-studied, positive sub-Gan nub-Gaussian random variables (including truncated and folded normal distributions), the sub-Poisson parameter is small.
Next, we discuss the necessary preliminaries for our algorithm and analysis.
2.2 Optimal Design.
Write A(X') to denote the probability simplex associated with the set of arms X. Let À E A(X) be such a probability distribution over the arms, with X₂ denoting the probability of selecting arm æ. The following optimization problem, defined over the set of arms X, is well-known and is referred to as the G-optimal design problem.
Minimize g(A) A max
|| ||a)|م())), where ((X) and U(A) = --=>>o Ex x
ZEN
The solution to 3 provides the optimal sequence of arm pulls (for given budget of rounds) to minimize the confidence width of the estimated rewards for all arms X. The G-optimal design problem connects to the following optimization problem (known as D-optimal design problem):
Maximize f()) e log (A))), where À E A(X) and U(A) = => Aaxxn
DEX
The lemma below provides an important result of Kiefer and Wolfowitz [15]
Lemma (Kiefer- Wolfowitz). If the set is compact and X spans IR4, then there exists X E A(X) supported over most d(d + 1)/2 arms such that X* minimizes the objective in equation (3) with g(\*)= = d. Furthermore, X* also a maximizer of the D-optimal design objective, i.e., X* maximizes the function f()) = log Det( U()) subject X E ((X).
Here, the expectation is with respect the random variable Xt.

---

Algorithm I GenerateermSequencce (Subroutine to generate Arm Sequence)
Input: Arm set X' and sequence length T 2+.
I: Find the probability distribution À E ((²)) by maximizing the following objective
log (Ao)) subject to λo E ( and Supp(Xo) S d(d 1)/2
(5)
2: Initialize multiset S 0 and set A = Supp(A). Also, initialize count C₂ 0, for each arm E A.
3: Compute distribution U as described in Section
4: for i to T do
5: With probability 1/22 set flag SAMPLE- U. otherwise, set flag D/G-OPT.
flag = SAMPLE-U or 0 then
7: Sample an arm ~ from the distribution U, and update multiset S + SU (a).
8:
else if flag D/G-OPT then
9:
Pick the next arm in A (round rohin). Update multiset S S {=} and increment count cs f c₂ +.
10:
11: c, [A= T/3], then update A + A {z}.
12:
end if
13:
end for
14:
return multiset S
At several places in our algorithm, our goal is to find probability distribution that minimizes the non-convex optimization problem However, instead we will maximize the concave function f(A) log Det Det(U(A)) over X solve the D-optimal design problem (4) and compute X efficiently ([17), Chapter 21). Lemma ensures that this approach works, since the G-optimal and the D-optimal design problems have the same optimal solution X E ( which satisfies Supp(>*) S d(d + 1)/2
A(x)) The Frank- Wolfe algorithm, for instance, can be used to
2.3 John Ellipsoid.
For any convex body K RR. John ellipsoid an ellipsoid with maximal volume that can be inscribed within K. It is known that K itself is contained within the John Ellipsoid dilated by factor of d. Formally
Lemma 4 (.T), Let K C RRd. be convex body (i.e., a compact, convex set with a nonempty interior). Then, there exists an ellipsoid E (called the John ellipsoid) that satisfies E C K C c- d(E-c). Here, c E Rdd denotes the center of E and c + d(E - c) refers to the (dialated) set {c + d(x - c) : E}.
3 Our Algorithm LINNASH and Main Results
In this section, we detail our algorithm LINNASH (Algorithm 2}. and establish an upper bound on the Nash regret achieved by this algorithm. Subsection 3.1 details Part of LINNASH and related analysis. Then, Subsection [3.2 presents and analyzes Part II of the algorithm. Using the lemmas from these two subsections, the regret bound for the algorithm established in Subsection 3.3
3.1 Part Sampling via John Ellipsoid and Kiefer- WolfowiW Optimal Design
As mentioned previously, Nash regret is a more challenging objective than average regret: if in any round & [T], the rewarrd E[re] is zero (or very close zero), then geometrie mean [T_,EErx.] goes to zero, even if the expected rewards in the remaining rounds are large. Hence, need ensure that in every round / [T], specifically the rounds the beginning of the algorithm, the expected rewards are bounded from below. In (5), this problem was tackled for stochastic multi-armed bandits (MAB) by directly sampling each uniformly at random in the initial rounds. Such sampling ensured that, in each of those initial rounds, the expected reward bounded from below by the average of the expected rewards. While such a uniform sampling
'Even though the two optimization problems and share the optimal solution, the optimal objective function values can be different.
'The ellipsoid E considered in Lemma is also the ellipsoid of maximal volume contained in K [I] Heee, the expectation is over randomness in algorithm and the reward noise.
5

---

Algorithm 2 LINNASH (Nash Regret Algorithm for Finite Set of Arms)
Input: Arm set X and horizon of play T.
I: Initialize matrix V + [o]a,a and number of rounds = 3 logTdo Part
2: Generate arm sequence S for the first T rounds using Algorithm
3: for i = to T do
4: Pull the next arm X, from the sequence S, observe corresponding reward r., and update V V+X,x??
end for
6: Set estimate 0 = V=
(Σ r=X,,
7: Compute confidence bounds LNCB(E, 0, T/3 and O, for all æ E X (see equation 77)
Set X
{ { X: UNCB(r, 0, T/3) 2 max;ex LN 0,/33 [/3) and initialize T'
Part II
9:
while end of time horizon T is reached do Initialize V [0]a.a be all zeros d x d matrix and [0] to be an all-zeros vector.
10:
// Beginning of new phase.
11:
Find the probability distribution X E A by maximizing the following objective
log Det(Detuu (eo((U())) subject to λo A(X) and Supp(An) - d(d + 1)/2.
(6)
12:
for each arm in Supp(A) do
13:
Pull arm for the next [A. T'1 rounds. Update V + V + Aa oa".
14:
Observe [Aa I'1 corresponding rewards 21, ...... and update + + (2. 2z)0.
15:
end for
16:
Set estimate = V-1s and compute LNCB(x, 0, T') and UNCB(2, 0, T'), for all x E X (sec
equation
17: Set X
X: UNCB(,,0,T) 2 max,ex LNCB(,,0,T)). // End of phase.
18:
Update T 4- 2T'
19:
end while
strategy is reasonable for the MAB setting, it can be quite unsatisfactory in the current context of linear bandits. To see this, consider linear bandit instance in which, all except for one arms in X' are orthogonal to d" Here, a uniform sampling strategy will lead to an expected reward of (x", /1)/ which can be arbitrarily small for large cardinality X.
To resolve this issue propose novel approach in the initial 3 Tdu (T)(( rounds. In particular, we consider the convex hull of the set of arms X'-denoted as evh(Xt) X') and find the center e E Rd of the John ellipsoid E for the convex hull cvh(X). Since E C cvh (X), the center c of the John ellipsoid is contained within cvh( (X)) well. Furthermore. via Carathéodory's theorem 10]. we can conclude that the center e can be expressed as a convex combination of at most (d + 1) points in X. Specifically, there exists size-(d 1) subset y = (V1,.... ..,,...> [V1,...;d++1] C X' and convex coefficients aj,..., ad+1 [0, 1] such that c = >d+1 agyi with Σ a; = 1. Therefore, the convex coefficients induce a distribution U E A(X) of support size d d+ and with Ex~ [xr]
Lemma 5 below asserts that sampling according to the distribution U leads to an expected reward that is sufficiently large. Hence, U is used in the subroutine AemeeratArrSequuene (Algorithm D
In particular, the purpose of the subroutine is to carefully construct sequence (multiset) of arms S, with size [S] T and to be pulled in the initial T rounds. The sequence S is constructed such that (i) upon pulling arms from S, we have sufficiently large expected reward in each pull, and (ii) we obtain an initial estimate of the inner product of the unknown parameter vector 0* with all arms in X' Here, objective (i) is achieved by considering the above-mentionel distribution U. Now, towards the objective (ii), we compute distribution E ((X') by solving the optimization problem (also known as the D-optimal design problem) stated in equation (
We initialize sequence S = 0 and run the subroutine GenerateArmSequeen for T iterations. In each iteration (of the for-loop in Line 4). with probability 1/2, we sample an arm according to the distribution U (Line 7 and include it in S. Also, in each iteration, with remaining probability 1/2, we consider the computed distribution and, in particular, pick arms z from the support of X in round-robin manner. We include such arms in S while ensuring that, at the end of the subroutine.

---

each such arm (A) is included at least [x 1/3 times. We return the curated sequence of arms S at the end of the subroutine.
Our main algorithm LINNASH (Algorithm erated the sequence S. Then, the algorithm LINNASH sequentially pulls the arms X, from S, for 1 S T rounds. For these initial T {S] rounds, let rr denote the noisy, observed rewards. Using these observed rewards, the algorithm computes the ordinary least squares (OLS) estimate (see Line 6 in Algorithm 2) in particular, 0 = 1 ( rxX,). The algorithm uses the OLS estimate 0 to eliminate several low rewarding arms (in Lines concludes Part of the algorithm LINNASH.
2 first calls subroutine Generate4rmSequencce to gen-
and 8 in Algorithm 2). This
Before detailing Part II (in Subsection 3.2 we provide lemma to be used in the analysis of Part I of LINNASH.
Lemma 5. Let R.d denote the center of John ellipsoid for the convex hull cvh(X) and let U E ( be a distribution that satisfies BESU x = c. Then, holds that
(x",0%
E (x,, (x,
(d (d+1)
Proof. Lemma
ensures that there exists a positive definite matrix H with the property that
x ZERd. (a T) - } cvh((a) s { E Rd
{ V (x- c)
sc) sd..
Now, write = c - and note that
[x c) H [x-
cy- -
I
(since x" cvh(X))
d²
Therefore, y E evh(2). Recall that, for all arms x E X. the associated reward (rx)) non- negative and, hence, the rewards' expected value satisfies {x. 8*) 2 0. This inequality and the containment E cvh((t)) give (y. 0*) 2 O. Substituting = --ك in the last inequality leads to (c, 0*) 2 (z*,0")/(C (d0))((d+ (d +1.. Given that EgaU [x] = C, we obtain the desired incquality
Eg-u (2, )*) = (c, (c) (d+1)
(='.0))
Note that at each iteration of the subroutine GeneratearmSQquence, with probability 1/2, we insert an arm into S that is sampled according to U. Using this observation and Lemma [S] we obtain that, for any round E [T] and for the random arm X, pulled from the sequence S according to our procedure, the observed reward r'x, must satisfy [[[x,] 2(d+1)
we insert arms x E Supp(A) at least [A, T/37 times, where \ corresponds to the solution of D-optimal design problem defined in equation ( Therefore, we can characterize the confidence widths of the estimated rewards for each arm X' computed using the least squares estimate & computed in Line 7 in Algorithm 2
Further, recall that in the subroutine Generate
Broadly speaking, we can show that all arms with low expected reward (less than threshold) also have estimated reward at most twice the true reward. On the other hand, high rewarding arms must have an estimated reward to be within factor of 2 of the true reward. Thus, based on certain high probability confidence bounds (equation (7)). we can eliminate arms in A' with true expected reward less than some threshold, with high probability.
3.2 Part II: Phased Elimination via Estimate Dependent Confidence Widths
Note that while analyzing average regret via confidence bound algorithms, it quite common to use, for each arm confidence width (interval) that does not depend on r's estimated reward. This reasonable design choice for bounding average regret, since the regret incurred at each round is the sum of confidence intervals that grow smaller with the round index and, hence, this choice
Here, the expectation is over both the randomness in including arm X in S and the noise in the reward.
7

---

leads to small average regret. However, for the analysis of the Nash regret, a confidence width that is independent of the estimated reward can be highly unsatisfactory; the confidence width might be larger than the optimal (x", This can in turn allow an arm with extremely low reward to be pulled leading to the geometric mean going to zero. In order to alleviate this issue, is vital that our confidence intervals are reward dependent. This in turn, requires one to instantiate concentration bounds similar to the multiplicative version of the standard Chernoff bound. In general, multiplicative forms of concentration bounds are much stronger than the additive analogues [16]. In prior work [S] on Nash regret for the stochastic multi-armed bandits setting, such concentration bounds were readily available through the multiplicative version of the Chernoff bound. However, in our context of linear bandits, the derivation of analogous concentration bounds (and the associated confidence widths) is quite novel and requires a careful use of the sub-Poisson property.
In particular, we use the following confidence bounds (with estimate dependent confidence widths) in our algorithm. We define the lower and upper confidence bounds considering any arm J. any least squares estimator (of (*), and the number of observations used compute the estimator Φ. That is, for any triple (I, o, t) E X x Id x [T], we define Lower Nash Confidence Bound (LNCB) and Upper Nash Confidence Bound (UNCB) as follows:
(x, d) (T (T))))
LNCB(z, o, t) = (a, の) 6
(x, Dod (o.d))dlog((Tx))
UNCB(2, o, t) (z. の) +
As mentioned previously, the confidence widths in equation 7 are estimate dependent.
Next, we provide a high level overview of Part II in Algorithm 2 This part is inspired from the phased elimination algorithm for the average regret ((17), Chapter 21); a key distinction here is to use the Nash confidence bounds defined in (7). Part II in Algorithm 2 begins with the set of arms X' S X obtained after an initial elimination of low rewarding arms in Part I. Subsequently, Part runs in phases of exponentially increasing length and eliminates sub-optimal arms in every phase.
Suppose at the beginning of the tth phase, X is the updated set of arms. We solve the D-optimal design problem (see )6) corresponding to X' obtain distribution À A(P). For the next O + T) rounds, we pull arms a in the support of (Linee 13): each arm a Supp(A) pulled T' times where T' = T)) Using the data covariance matrix and the observed noisy rewards, recompute: (1) improved estimate 1 (of 0*) and (2) improved confidence bounds for every surviving arm. Then, we eliminate arms based on the confidence bounds and update the set of surviving arms (Lines and
The following lemma provides the key concentration bound for the least squares estimate.
Lemma 6. Let Iı, I2,..... .., I, E H be a a.fixed set of vectors and let T2........ be independent v-sub-Poisson random variables satisfying Er, = (xx:0") for some unknown 6*. Further, let matrix
V Ej= z,z, and θ V-1 (E,rarr) be the least squares estimator of 0". Consider any
E dRd with the property that z"" V VV-1x, S > for all j E [s]. Then, for any E [0, 1] we have
P f((2, 0) 2 (1+ (2 0-) s exp (- (2
(-
and
(8)
317y
p P((s, < (0x0))),220))))))) exp
82(2, 0-)
(9)
207
Lemma is established in Appendix B
Using this lemma, we can show that the optimal arm x² is never eliminated with high probability.
Lemma 7. Consider any bandit instance in which for the optimal arm x" E X we have (a*,0% 2
1 de log(T) Then, with probability at least (1- [--luuT] -
IlogT)
the optimal arm x² always exists
in the surviving set X in Part and in every phase in Part II of Algorithm 2
Finally, using Lemmas 6 and 7 we show that, with high probability, in every phase of Part II all the surviving arms e X have sufficiently high reward means.
8

---

Lemma 8. Consider any phase E in Part 1I of Algorithm 2 and let X be the surviving set of arms at the beginning of that phase. Then, with d log( T XI), have
Pr (x. 0- ,0) 2 3dv 00*) log (T[x1)
4 log T
for all X {
(10)
2
Here, v is the sub-Poisson parameter of the stochastic rewards.
The proofs of the Lemmas 7 and 8
are deferred to Appendix C
3.3 Main Result
This section states and provides proof sketch of the main theorem!
Theorem 1. For any given stochastic linear bandits problem with (finite) of arms X C R time horizon T E Z4, and sub-Poisson rewards, Algorithm 2 achieves Nash regret
NRT = -0(8
dv T log log((Tx1))
Here, max {1, (a*, 0*) log d}, with x² X denoting the optimal arm and 0* the (unknown) parameter vector.
Note that, Theorem lower the value of the optimal expected reward, (x", (")), stronger is the Nash regret guarantee. particular, with standard normalization assumption that (x), S and
for 1-sub Poisson rewards, we obtain a Nash regret of O (V log(((xx)) Also, observe that the regret guarantee provided in Theorem I depends logarithmically on the size X. Hence, the Nash regret is small even when |X| is polynomially large in d.
Proof Sketch of Theorem 7 We condition on the event & defined as the intersection of the (high probability) events defined in Lemmas 7 and 8 respectively. Union bound implies that event E holds with probability at most O(T-1). For Part I, in the first T 3 T (T],() rounds, bound from below the product of the expected rewards, using Lemma as follows
(x", (((11))) 2 (x" (x" 00), (1
Tlog(2 (2 (ddd1)))
EX, 0*) 18
T
1=1
For remaining rounds, invoke Lemma (specifically, equation (10) obtain
T
log T
T (2133 + 2d
3dv log (T)
II B(X,,0' 18 2 (x" 0x) T+++1
II
50
V
T
(x".0")""
Em
The above equations reduce the following bound on the geometric mean of the expected rewards (across the T rounds):
II EXX,, 1 81) Pr(E) (x (x*,0") (1- (1-100 1 T(x0,00)
du
I TEKX, [=1
log (T|x1)
1=1
Therefore, the Nash regret LINNASH satisfies
1/T -0 i EEX,, 03))
NRT (x",0")
=0
/dufar 0+)
log (os(TI)))
This completes the proof sketch.
Due space restrictions, the complete analysis is deferred Appendix
C

---

Computational Efficiency of LINNASH. We note that Algorithm 2 (LINNASH) executes in polynomial time. In particular, the algorithm calls the subroutine GENERATEAR ATARERTTTAESEEEENEE in Part for computing the John Ellipsoid. Given set of arm vectors input, this ellipsoid computation can be performed efficiently (see Chapter 3 in (55 fact, for our purposes an approximate version of the John Ellipsoid suffices, and such an approximation can be found much faster [8] specifically, in time df) Furthermore, the algorithm solves the D-optimal design problem, once in Part and at most (log T) times in Part II. The D D-optimal design is a concave maximization problem, which can be efficiently solved using, say, the Trank-Wolft algorithm with rank-1 updates. Each iteration takes ( time, and the total number of iterations is at most (d) (see, e.g., Chapter 21 of [17] Overall, we get that LINNASH is polynomial algorithm.
and Chapter 23
4 Extension of Algorithm LINNASH for Infinite Arms
The regret guarantee Theorem depends logarithmically on | Such a dependence makes the guarantee vacuous when the set of arms X' is infinitely large (or even |X| ((2 To resolve this limitation, we extend LINNASH with a modified confidence width that depends only on the largest estimated reward = max (I. 0). Specifically, we consider the confidence width T'
V y dd low for all the arms, and select the set of surviving arms in each phase (of Part II of
the algorithm for infinite arms) follows:
d log (T)
X X x: (1, 27- 20000771100 -
(11)
See Algorithm 3 in Appendix D for details. The theorem below is the main result of this section.
Theorem 2. For any given stochastic linear bandits problem with set of arms X' C Rd,, time horizon E., and v-su-PPiisoo rewards, Algorithmm 2 achieves Nash regret
NRT o
( di v0
(oa(T)
Here, 3 = max {1, (a",0% 0*) log d}. with x² E X denoting the optimal arm and 6 the (unknown) parameter vector.
Proof of Theorem 2 and detailed regret analysis of Algorithm can be found in Appendix D
Conclusion and Future Work
Fairness and welfare considerations have emerged central design objectives in online decision- making contexts. Motivated, broadly, by such considerations, the current work addresses the notion of Nash regret in the linear bandits framework. We develop essentially tight Nash regret bounds for linear bandit instances with a finite number of arms.
In addition, we extend this guarantee to settings wherein the number of arms is infinite. Here, our regret bound scales as 5/4, where d is the ambient dimension. Note that, for linear bandits with infinite arms, [ obtains bound of d/ TT for average regret. We conjecture that similar dependence should be possible for Nash regret as well and pose this strengthening as relevant direction of future work. Another important direction would be to study Nash regret for more other bandit frameworks (such as contextual bandits and combinatorial bandits) and Markov Decision Processes (MDPs).
Acknowledgments and Disclosure of Funding
Siddharth Barman's 's reserach is supported by SERB Core research grant (CRG/2021/006165)
10

---

References
[1] Yasin Abbasi- Yadkor,, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135, PMLR, 2013.
[3] Shubhada Agrawal, Sandeep K Juneja, and Wouter M Koolen. Regret minimization in heavy- tailed bandits. In Conference on Learning Theory, pages 26-62. PMLR, 2021.
[4] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, (2(1):48-777 2002.
[5] Siddharth Barman, Arindam Khan, Arnab Maiti, and Ayush Sawarni. Fairness and welfare quantification for regret in multi-armed bandits. arXiv preprint arXiv:2205. 139300, 2022.
[6] llai Bistritz, Tavor Baharav, Amir Leshem, and Nicholas Bambos. My fair bandit: Distributed learning of max-min fairness with multi-player bandits. In International Conference on Machine Learning, pages 930-940. PMLR, 2020.
[7] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-32, 2019.
[8] Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the john ellipsoid. In Conference on Learning Theory, pages 849-873. PMLR, 2019.
[9] Varsha Dani, Thomas P Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008
[10] Jürgen Eckhoff. Helly, radon, and carathéodory type theorems. In Handbook of convex geometry, pages 389-448. Elsevier, 1993.
[11] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combina- torial optimization, volume Springer Science & Business Media, 2012.
[12] Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent multi-armed bandits. Advances in Neural Information Processing Systems, 14:24005-240177 2021.
[13] Ralph Howard. The john ellipsoid theorem. University South Carolina, 1997.
[14] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
[15] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[16] William Kuszmaul and Qi Qi. The multiplicative version of azuma's inequality, with an application to contention analysis. arXiv preprint arXiv:2102.05077, 2021.
[17] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[18] Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pages 1642-1650. PMLR, 2016.
[19] Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
[20] Vishakha Patil, Ganesh Ghalme, Vincet Nair, and Yadati Narahari. Achieving fairness in the stochastic multi-armed bandit problem. The Journal of Machine Learning Research, 22(1))7885-- 7915, 2021.
[21] Paat Rusmevichientong and John Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.

---

[22] Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armes bandit experiments. Marketing Science, 36(4):500-52) 52000,5222220 2017.
[23] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495-517, 2017.
[24] William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-299) 1933.
[25] Michael Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
[26] Yogatheesan Varatharajah and Brent Berry. A contextual contextual-bandit-bsseee approach for informed ppcision-making in clinical trials. Life, 12(8):1277, 2022.
[27] Sofia Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: Benefits and challenges. Statistical Science, 30:199-215, 05 2015,
12

---

Limitations:
The main contributions of our works are theoretical. From a theoretical point of view, the limitations our puper are discussed in Section
particular, we believe that tightening the gap between the upper and lower bounds in Nash regret for an infinite set of arms will require novel and non-trivial algorithmic ideas we leave this as an important direction of future work.
Broader Impact: Due to the theoretical nature of this work, we do not foresee any adverse societal impact of this work.
A Proof of Lemmas 1 and
Lemma 1, Any non-negative random variable X E [0, B] is B-sub-Poisson, ie., if mean E[X] = 14 then for all R, we have EleAx] S exp (B-+ (e - 1)).
Proof. For random variable X we have
X
X
)
E exp (AX))
E
exp
XB
+ (1
)0
B
B
X
X B
E
(AB)
+
1
e
(due to convexity of e*)
B
E
[X]
(eAB -1) 1)
+
B
( -1
+
B
exp
(cAB
- 11
B
Lemma 2. Let X be a non-negative sub- Gabb-iassian random variable X with mean E[X] and
Bub-Gaussian norm a. Then, X is also
-sub-Poisson.
Proof. Since X is o-sub-Gaussian random variable, for any non-negative scalar 2 0, have
(s0)2
B|
S exp
sji
+
2
n²2
so"
/ 2
1
exp
?²
(12)
The fact that is a positive random variable implies that the mean μ > Also, the considered
scalar 2 0 and, hence, the term sa? > 0. Also, recall that ex 2 1 + x. + x²
2. for any non-negative
x. Using these observations and equation (12). we obtain
E x < exp
o P (e=-1)
(13)
For random variable X, inequality (3) ensures that the required mgf bound (equation ( holds for all non-negative and with sub- parameter equal to o²
#
We next complete the proof by showing that the mgf bound holds for negative well. Towards this, write B d² and define random variable Y = 1xx=B} X X ((x>B)) B. Note that is positive, bounded random variable. Furthermore, for any negative s, we have exp (sY) 2 exp (sX).. Therefore, for negative it holds that E [exp(sXX]] < E [exp (sY)). Since positive random variable E [0, B), the mgf bound obtained in Lemma gives us
EE xX
< E
[
< exp
4 (e (c8-1))
Since B = 2" the mgf bound (equation ( on X holds for negative well. This, overall, shows that is -ub- Poission random variable. The lemma stands proved.
13

---

B Proof of Concentration Bounds
Lemma 6. Let I1, 322.... ................................ Ii E TR& be fixed set of vectors and let rı; N2.2..... yT be independent e-sub-Poiison random variables satisfying Er, = (r,, )r) for some unknown 6* Further, let matrix
= -Ei= 25z and θ- = V-1 [S Tyy be the least squares estimator of 0r Consider any 2 E TRd with the property that TTV : S r for all j E [s]. Then, for any E [0, 1] we have
P P( (2, 03 2 (1 6) 03} S exp
(z)
and
(8)
30y
(2(200))
s s( (1-0))200)) s exp
207
Proof. We use the Chernoff method to get an upper bound on the desired probabilities, as shown below
IP { 0) 2 (1 (2,00)(11++
(1- (1))) = P exp(( (z, 0) 2 exp(c(1 + 5)(2,6))) (for some constant c)
Elexp (c 2 V (E, n121))
exp(c (1 + (2, 8)))
I1 Elexp (er.V-1x;))
(ry's 's are independent)
exp(c (1 + 8) 0+))
Ii exp [ir]]
cou -
la -
(rx is sub Poisson)
explc (1 + {){,,
exp -c(z,0)) 8) + Σ (x,00)
(Gevs"v (crve"V'eo-
Pxx 1))
v
Substituting c= 1n
log(1+5)
we get
P (( 0) (1+ (2+ s sexp
(2.0%) (1 + 8) log (1+ (1+))= vy
0²)
(
(1+ (1++0)==vV
(14)
f 1 S we have (1 + 1z S 11+ 8. 2 xr. Substituting in 14 we get
Since
(z, 8) 2 (1 + (2, }7) PP
8 -T
S exp
vy (z, (1 5) log (1 (0)) +
Σ
(zt 0²)
1yy
8
exp
my (z, 01) log (1 0) +
8
(rearranging terms)
vy
5
(z, (-, 0') + 8) log 61+ + in (2 (2,0%) vy
Cinia V)
exp
Using the logarithmic inequality log(1 +5 2
28 2+8.
we further simplify as
(z,0")
P((x,0) 0) 2 (1 (2, s exxp
((1 + 8) log (1 + 5) -5)
MY
52 0*)
exp
(2+ 5) vY (2(2,00)
S exp
(since 8 E |0, 1)
32m
14

---

Following similar steps and substituting log(1-8), we obtain a bound on the lower tail (inequality
P( (1- (1- exp (
1 (- 0') -o) (1 -0- my
(z, 03)
Now, using the logarithmic inequality - (1-6)log(1 - -8) 2 -6
62
2'
we get
P (((2,0) 6) (1 (2, S exp (
(-89 8-))
207
Combining 9 and 8 we get the following Corollary.
Corollary 9. Using the notations as in Lemma 6 we have
{1 Kez, 0) - (z, 2 2,,,0))6(22000))) s exp (-
(-8(3.07)
(15)
37
The next two lemmas are variants of Lemma where we bound the error in terms of an upper bound on (z, 0*).
Lemma 10. Let 21, ,2,..., Is E Rd be a fixed set of vectors and let ri, ........ Vs be independent s-sub Poisson random variables satisfying Er, (I 0*) for some unknown 0" In that case, let
matrix V = Ei= 2 and 0 = - (E, r, be the least squares estimator of 8 Consider
any 2 E IRd that satisfies z" 22v-rr S 7 for all j E [s] and (z,0", 0r) S a. Then any 6 E [0, [0 we
have
p P( (z, P((2,0 0) 2 (1 +1+ 10+ Se
&2
(16)
Proof.
Following the same approach as in the proof of Lemma 6 have
E(exp(c 2 VV (E, rat))
PP ( 0) 2 (1 (+)))aa <
exp(e (1 + +d)a)
-ca(1 -ca(1+0) 00) Σ (2,,0) 00)
(eu="V-''x- -1)
I exp
[=1
(re are sub-poisson and independent)
Now, substituting == log (1 + 6)) and using (1 + +8)
11+ 1 TV Dt we have
P f( 0) (1 + +))
a(1 _
1 log (1 + +
(2,, 0-) 0r (11 (1+)))+(V''>
exp
t=1
5
exp
a(1 8) (1 +6+ +
g
To V- z
vy
1=1
1
5
exp
a(1
8) log (1 + +6 + (2,0*)
vy
in
exp
a(1 + log (1 +
a
(a > (2,8-))
vy
in
-8aa
exp
(using log(1 +8) >
28
(2+
Since 5 E [0, 1). we have the desired result.
Lemma 11. Using the same notations as in Lemma
10 for any 8 E [0, 1]. the following holds
82a
P (z, s (2, 0-) - sa I exp
(17)
27v
15

---

Proof. Using steps similar to the previous lemmas, we obtain
Elexp(e 2 (Σ, rx4:))
P (2 I (2,07
50 S exple ((z, 8*) -da)
Σ (r,, ( (cvu'v-t
S cxp
cad + c(2,0)
V
(Tr are sub-poisson and independent)
Substituting log(1-8) v9
and simplifing we get
P (2, 0) S (2 50} I exp (- (-1x,0% My
(log - 5)+ -1-
8log (1 11 -5)
my
Note that since log(1 - 8) + 8' is negative, (z, 0*) with a.
upper bound the above expression by replacing
s (2,00) P s
5a} s exp
(_a
(log (1 - -8)+6 + -olog (1 -6))
vy
8²a
(since (1 - 6) log(1 -6) - )
S exp
207
Hence, the lemma stands proved.
C Regret Analysis of Algorithm 2
We will first define events E₁ and Ey for each phase of the algorithm and show that they hold with high probability. We will use the events in the regret analysis.
Event El: At the end of Part I, let 0 be the unbiased estimator of 0* and T be as defined in Algorithm 2 All arms X' with (z., 0-) 10 du log (TIx)) satisfy
dv log (TIx1)
(x. 0) 20
(18)
T
In addition, all arms X with (z, 0-) 1
du log (T
satisfy
dv(x, (*) log (T)2')
Kx,00) - (x, -x, (x,0)1 S (13,0)013331 $3/
and
(19)
2/ 0r) <(x, 0) (1, 0r)
(20)
Event Eg: Let X denote the surviving set of arms at the start of a phase in Part II, and
T' be defined in Algorithm 2 For all phases and for all x E X' such that (z, 0*) 2
10 du log (T the estimator (calculated at the end of phase) satisfies
Kr, 0-) (a, 0 3/ du(r,, 0-) log (T)x)) and
(21)
T'
// (z, 0-) S(x, 0) < (z, 0*)
(22)
C.1 Supporting Lemmas
Lemma 12 (Chernoff Bound). Let Zi.... Zn be independent Bernoulli random variables. Consider
the sum S E Z, and let E[S] be its expected value. Then, for any E E [0, 1]. we have
ME²
IP ( < (1 - =) S exp
(-2
2
16

---

Lemma 13. During Part I, arms from D-optimal design are added to S at least T/3 times with probability greater than 1
Proof. We Lemma 12 with Z, indicator random variables that take value one when an arm
from A (the support of À in the optimal design) is chosen. By setting e 3 and the required probability bound.
we obtain
2
Lemma 14. Using the notations in Algorithm [ the event in Lemmal 13 holds, then for each X
and each round Part of the algorithm, we have
3d
5
T
where X, is the arm pulled in round t.
Proof. Let UX) and À denote the optimal design matrix (as defined in (4) and the solution to the D-optimal design problem in Algorithm respectively. That is, À the solution of the optimization
problem stated in equation and U(A) Exex Aaxx". Lemma implies that ||x|| || S vd
for all x E
Next, note that the construction of the sequence in Part (Subroutine GenerateArmSequencc) and the event specified in Lemma
13 give us V > T U(A). Hence,
X, < | V Xillv
(via Hölder's inequality)
| ||
| (fu(N)
+||xall (fu(N))
(since V JU(A))
/3
3
|| |=)lu(())'
V ||Ailluca)
T
3d
3d
(by Lemma
T
T
3d
The next lemma lower bounds the probability of event E₁ (see equations (18). Lemma 15. Event E₁ holds with probability least 7
and (20)
Proof. First, consider all arms E X for which (Ir, 0*) 10
du log (T
Here, we invoke Lemma
10 with (as derived in Lemma a 10
du log (T)
and 1, to obtain
(x, 0) s 201/ dv log (T)x))
8²a
exp
37y
10
du log (T)
3, Tdv log ( (T)x))
exp
3vd
(23)
T|X
Next, consider E X' such that (x. 0*) 2 10 du log (TI and for such arms establish
equations 19) and 20 Towards this, we invoke Lemma 6 with parameters
3d and 8 =
17

---

3/ /dd do log (T)21), It relevant to note that here ò [0, 1] this containment follows from the (a.0-)T
condition (0r 10 de log (TI and Tdl log (T).)). Therefore,
dv(æ 8*) log (T
P 12,00" 0*) - -xx,0) 23V
PP 22(10,00) (2, 2 81 07)
T
(since 5 3/
du log (T)22)
(x,0--)
9dv log (T(xl)
(x,, 0*))
(z,0-)T
S 2 exp
3v 3d
(Lemma 6
(24)
T|X
For establishing equation 20 we invoke Lemma 6 again, now with 7 = 3d and
3/ / Tud log( (T) (or, 0*)
PP (r, 0) 2
(z. 07)
s cxp
27vd
3/Tv log ([ 10
da log (T (()))
S exp
27vd
(25)
T|x
Similarly, with 5 = 2- Lemma gives us
1
(x. 0) v (2. 8*)
(26)
2
T|X
and (6).. and apply a union bound over all arms in X. Then, conditioning on the event in Lemma 13 leads to the stated probability bound. The lemma stands proved.
Finally, we combine 223
24
The next lemma shows that event Eg (see equations ( and 22
holds with high probability
Lemma 16. Event Eg holds with probability at least log
Proof. Consider any phase in Part II and let U()) be the optimal design matrix obtained after solving the D-optimal design problem at the start of the phase. By Lemma for all in, X we have
V r < || -- ||V-'lly
(via Hölder's incquality)
- || --1 |=
T T
First, address equation 21 In particular, we instantiate Lemma 6 with 5 3/
dv log (TIx1)
and
(w.8-)1
7 f. Note that given lower bound on (ar,6t 8*) and the inequality T' 2
ddv log (T]()
ensure that 5 lies in [0, 1]. Hence, substituting these values of 5 and in Lemma 6
we obtain
PP (rx, 0*) - (x.0)) 2 3y
dd(xx, (0)(0,00)er) log (TIx))
2 exp
9dv (TIx2)
(x,0~)1*
(x,, 0-)
T
3 3
2
(T|x1)
18

---

Next. following similar approach as in the proof of Lemma 15 we use Lemma 6 with 8 = and ô 2 to establish the upper and lower bounds of equation (22). respectively. Applying union bound
across arms in X and over all-at at most log --aasss we obtain the desired probability bound of
3 log
Corollary 17.
4 log T
P ( n F22 2
Proof. From Lemma 15 we have P [E1} 2 - 6 Furthermore, from Lemma 16 we have P ((E.)
{E2} 2
1 I. Applying a union bound on the complements of these events establishes the corollary.
Lemma 18. Consider any bandit instance with (x",0" 192 du log (T
event Es holds, eliminated after Part of Algorithm
then any arm with mean 00)0") S 10 de log(T
Proof. We will show that the given bandit instance and under the event F1, for each arm x E X
with mean (z, 8*) S 10 /dr (o the upper Nash confidence bound (see equation 7 is less than the lower confidence bound of the optimal arm x². Hence, all such arms are eliminated from consideration in Line of Algorithm This will establish the lemma.
The upper Nash confidence bound of arm at the end of Part is defined as
3(x, 0 d v log (T)
UNCB (z.0,T/3) (x. 0) + +
T
d v loog [olg((TXX))
3xx, 0) d v log (T|
s 201
+ 61
(via event E1)
T
dv log((T (T2x))
20
du log T|2'
dy log (T]x))
S 20
+ 6
T
3 TVd log( (T)x))
(substituting T)
du log(T
S 47
(27)
T
In the given bandit instance and under event E,, for the optimal arm x", we have
du dv(x** 0r) log (T)x')
(x (x) S (x" (x",0") + +3
T
du log (T))')
(xx, ,0)
1
(substituting T)
(x+ 00), Td lo (T
dy log (T
S (x",, ,0,00)
1 1+3
192 log (T 3
Tvd log( (T](
(using (x" 00) 2 192,
du log (T
17
(x*,0%
(28)
16
Therefore, the lower Nash confidence bound of x² satisfies
3(0 0) d log (T)x))
LNCB (2).0.T/3)= = (xx" 61
19

---

d (x*, 0*) log (T(x))
6V 3/00 00, d log (T]21)
w,,03 3/
T
T
(via in event E1)
51 VV
du (x" 0r) log (T)+1)
-00 -
16
(since (x" 00 = 10 (0= 0*) via 28
dv log (T)x')
(0", 07)
14
(x+ "0,,0- 8*)
dv log (T
(x",0%
- 14
de (og( Tdv (od(ToogTTT))))) (T
192
5 (x" 180)
12
du log( T[x1))
80
(29)
Equations
29 and
27 imply
UNCB 2z, 0, T/3)
LNCB (,t,0,T/3)
(30)
As mentioned previously, Line in Algorithm Zeliminates all arms x that satisfy inequality (3) Hence, the lemma stands proved
C.2 Proofs of Lemmas 7 and
Lemma 7. Consider any bandit instance in which for the optimal arm x² E & we have (x", "²,,0 2 192 4 log(T Then, with probability at least (1- AluxT), the optimal arm x² always exists in the surviving set X Part and in every phase in Part II of Algorithm
Proof. We will show that, under events Eg and Ez, throughout the execution of Algorithm the UNCB of the optimal arm x² is never less than the LNCB any arm æ. Hence, then the optimal arm x' never satisfies the elimination criterion in Algorithm 2 and, hence, 2* always exists in the surviving set of arms.
First, we consider arms x with the property that (z, 0*) < 10 du log (T)) For any such arm æ, at the end of Part of the algorithm we have
LNCB x, 0, T/3) < UNCB (c,0,T/3) via 30
LNCB (x (z',0,1/3) UNCB (st,0
Hence, at the end of Part arm is not eliminated via the LNCB of any which satisfies (x, 8*) < 1 du dog (T] Further, note that, under event E,, such arms are climinated at the end of Part I (Lemmal
18 Hence, the LNCB of such arms are not even considered in the phases of Part II. To complete the proof, we next show that the UNCB of the optimal arm x² is at least the LNCB of all arms a which bear (z, (x. 2 10 du log (T]21) Below, will consider the Nash confidence bounds for a general T'. Replacing T' by T gives us the desired confidence-bounds comparison for the end of Part I this repetition is omitted.
20

---

Under events Ej and Eg, for any arm with (z, 6*) 10
do (T]x1) it holds that
(o. 0) dv log (T(21)
(CCB(,,,TT)) (x, -00 6V
T
d (c,, 0r) log (T
(x, 0) du log (TJx)
$ (x, 00) + +3/
- -61
T' (via (2
T
dv(x, 8*) log (T (T))))
I 0*)
3
((x, 0) 2 2 (z. 0*) via 22
V2
T
S (z, 0*).
(31)
Complementarily, for optimal arm xt we have
(at, 0) d log (T[2')
UNCB(=", ,0,T') -x=0;;=;--0000 6V (x",
T'
dufa" 0*) log (T(21)
(x) (x+, 0) d v log (T(x))
(x", 00) -3V
+6
T'
T'
2 (z 00) +
6 (/22)
-3)
V
dv (xr 0*) log (T
(since (x",
far"00 .0*)
T'
2
(x" 10)
(32)
Since (x",0") comparison:
(x, )r) for all arms x. inequalities
31 and
32
lead the confidence-hounds
UNCB(x 0, T') 2 LNCB (z. 0, T').
Hence, if events Ej and Bg hold, then the optimal arm x² never climinated from Algorithm Further, Corollary 17 ensures that the events Eg and Eg hold with probability at least loog Hence, the lemma stands proved.
Lemma 8. Consider any phase I Part II of Algorithum
2 and let X be the surviving set of arms at the beginning of that phase. Then, with = / dv log(1 Xl), we have
3dv(x (*)) log (T(x)) for all 8 8222
4 4 T
Pr (z, 0-) (x" 0") 25
2
(10)
2' T
Here, v is the sub- Poisson parameter of the stochastic rewards.
Proof. For the amalysis, assume that events E1 and Eg hold. Lemma 7 ensures that the optimal arm contained in the surviving set of arms X. Furthermore, if arm X at the beginning of the gh phase, then it must be the case that arm & was not eliminated in the previous phase (which executed for T'/2 rounds); in particular, we have UNCB(r, 0, 22) 2 LNCB(x* T' This inequality reduces to
(z. 0) 6/ (x, 0) d v log (T
(x+ 0) d v log (T)
(x" 0) - 6/
2
Rearranging the terms, we obtain
(x 0) log (T|x')
(x, 0) d log (T|x))
(x, 03 2 (x".0) 0) -V
6/
T
I 2
4/1z, 0-) d log (T|x))
4(x,, O*) d Volog (T|+))
2 (x", ","00 0) 6/
6
32
3T//2
(1c, 0) S $ (z. 0*) via 22
(x= 8r) d v log (T|x')
2 (x'.0) 0) 201
T'
21

---

Further, invoking equation 21 for x² leads to
(0, 0-) 2 ,-) 201 (x',0") d log (T)+)
(x,,0% ,00 d log (T)
3/
T
(0'.0") d log (T)
2 (a"00" 251/
T
Substituting T' = 2 /3, the above incquality reduces to the desired bound in 10 From Corollary 17 we have that the events Ej and Ez hold with probability at least 1 4log Hence, the lemma stands proved.
C.3 Proof of Theorem
Theorem 1. For any given stochastic linear bandits problem with (finite) set of arms X R time horizon T E Z+, and t-sub-Poissonn rewards, Algorithm 2 accieves Nash regret
NRT = 0 88V d
log( (og((
Here, = max (1, (*) log d}. with x² E X denoting the optimal arm and 8 the (unknown) parameter vector.
Proof. We will assume, without loss of generality, that (x",0") 192 T log (T)())))) otherwise
stated Nash Regret bound directly holds (see equation (T)). Write to denote the 'good' event identified Lemma
8
the lemma ensures that (P) 2 T
During Part I of Algorithm the product of expected rewards, conditioned on E, satisfies
f
(r",0)
II
E[X, 0*)
(via Lemma 5
2(d + 1)
= (,",00 ,03
1 (1_1
2
log log(2(d + 1))
2 (00,000
For analyzing Part II, we will utilize Lemma Write B; to denote all the rounds that belong to Eth phase (in Part II). Also, let T denote the associated phase-length parameter, i.c.. T 2 T/3. Note that each phase É (i.e., in the for-loop at Line 12 of Algorithm D). every arm a in Supp(A) (the support of D-optimal design) is pulled [A, T/ times. Given that [Supp(A) S d(d + 1)/2, we have [B&] S T d(d+11) By construction T/d d(d++1) and, hence, |B&] S 2T Since the phase length parameter, Th doubles after each phase, the algorithm would have most log T phases. Hence, the product expected rewards in Part II satisfies
T
II
(X, 8*) F
Bi(X,, 0*) F
Be
EEB:
18y1
d v (x", 8*) log (T))
II B
(x"00") - 25 1
(Lemma
T'2
log T
(x 0*) I-1
d log (T|x))
1 /
(xr 0+)TT
{=1
2 (x 0'' I-1
lng T
|Bel
v log (T)
1 50
T
(x0", 0-)T/
Fm1
22

---

The last inequality follows from the fact that (1- 1-xz) x)" 2 (1 2rz), for any E [0, and z e
log (T]X] T2 2 2 Tdv log T| and
[0, 1/2]. Note that the term
,0 I 1/2, since (x", 0r) 2 192 dv
T log(T[X()) along with
T e We further simplify the expression as follows
log T
|Bel
dv log (T|
Ing
VT d log (T)x1)
1 1 50
V
(x-, 10
II
100
(x),0))
8=1
t=1
(since B S 2T²
2 1
100
d v log (T|x1)
ing T
Σ
T
T
(xt 0*))
(since (1
a) b) 2 1 1
for a, b2 0)
100
d log (T|x1)
2 1
(VTlog
T
(x",0"
(via Cauchy-Schward inequality)
dv
2 1 - 100
log (T)
T(x*, 0r)
Combining the lower bound for the expected rewards in the two parts get
+
(XX,, 2 II ((Xx,,0) EJ ((E)))
log(2(4 (d 1))T
(10100/ (1- T(x* 0n) log (T1x11) P(E)
du
(x )r)
T
log(2(d 1))T
du -100g T( 00) log (T|x1) P(F)
(x (7)
log(2(d 1))T 100
dv log (T|x1)
(1- log T
2 (x", ,0'
T(x* 00)
T
log(2(d + 1))3 Tdu log( ([x))
dv
log
2 (x",0%
100
log (T(2))
T(x* 0-) d log (T)x))
T
(x* Ad)dv
2 (,,,0" 0-)
100g
log (T|x)) 6(0", "000000))
log (2(d (d + 1)).
Therefore, the Nash Regret can be bounded as
1/T
NRT = (0",0") i [E,,, 00)
s 100 (x+ .. log (T)x)) + -6 d log( ((x()) log(2(d 1))
(33)
$ (100 (2- (0)) (og 1))(z", B8)) V dv log (T|x))
(34)
Hence, with 0 max {1, V(=", 8*), (a* 0*) log d) max f1, (x*, (x",0") log d), from equation
(34) we obtain the desired bound on Nash regret NRT = ( (8v du log(T|x1)) The theorem stands proved.
D Algorithm3 3 and Regret Analysis
23

---

Algorithm 3 LINNASH (Nash Confidence Bound Algorithm for Infinite Set of Arms)
Input: Arm set X' and horizon of play T.
I: Initialize matrix V +- [0] and number of rounds 3oTdd=pplog( Part
2: Generate
sequence S for the first rounds using Algorithm
3: for L = to T do
4: Pull the next arm X, from the sequence S.
Observe reward Fı. and update 4- +x,X
6:
end for
7: Set estimate 0 = V-1 (Et,rex,,) P2X.)
Find y = maxxcx 0)
dd log log
9: Update X + E (2, 2 1
10: T' + T
Part
11:
while end of time horizon T is reached do
12: Initialize V [0]a.. an zeros matrix [0]a to an all all-zeros vector.
// Beginning new phase.
Find the probability distribution E A(X) by maximizing the following objective
log Det(V(A)) subject À A(X) and Supp(A) S d(d + 1)/2.
(35)
14:
for each arm a in (A))(A) do
15:
Pull arm for the next [X., T'l rounds.
16:
Observe rewards and Update V ['aT'] -aa
Observe Aa I'1 corresponding rewards 21, #., and update f 8- (E, 2,)a.
18:
end for Estimate V-1 (Eice xxx.)
20: Find max.ex (2,
21:
-- E (z. (x 2 16V
7 log (T)
22:
T' 2x End of phase.
23:
end while
Instead of ensuring probability bounds on individual arms, construct a confidence ellipsoid around 0r In the context of Algorithm 3 we define the following events for the regret analysis:
G1 In Part I, arms from the D-optimal design are chosen at least T/3 times. If (x",0" 2
196
12.5v log T, then 0 calculated at the end of Part satisfies
- ύ- 1-00ll S ST/(Kr
12.by G2 In Part II, for every phase, if (x",00) 00)0 /
log T, the estimators ① satisfy: T
0 001ly S 27
27 (I 0 v
Without loss of generality, we assume throughout that (x",0" 0-) 2 196 25 log T. Otherwise, the regret bound in Theorem trivially holds. Let B denote the unit ball in Rdd We have
0 8" = vv @ 8
max (v. V 8) wEB
24

---

We construct an E-net for the unit ball, denoted as C.. For any y E B, we define =
arg menbeee
|6 vll2. We can now write
i 0- llv = max (y
ye V2 (0 8*)) + (ye. V 8*))
yEB
11 Vell2 V (0 83>l + Kyye V (0 +*))
S max vEB
S (0 0¹) + Kyye v (0 8*) )>1-
Rearranging, obtain
0 - 0011 - - (we v+
0- 0-)
(36)
In the following lemmas, we show that Kyee V 0*) is small for all values of ys-
Lemma 19. Let .2......2 be a sequence of fixed arm pulls (from set X) such that each arm the support X from D-optimal design (for X) is pulled at least [ times. Consider the matrix
Σド= n5 and let z be a vector such that || S and (VV5,0)) 2 Bu log (T(Cel).
Then, with probability greater than 1 - CCT we have,
3 nd log (TICel)<", 0r)
1=V 0r 00|5
Proof. We begin by utilizing Lemma 6 for any & [n] we have
First, we determine the parameter in the lemma as follows,
(*v+)*
V V-
xx z
vV V-1 |
221l
1 ||| la I|zelll
5 a v-2
(since ||=/|2 S 1)
Let A, be the optimal design matrix. Since V > T TAs have
| S || e
d -
(by Lemma 3
Now, we use Corollary with y V and 5
(3/2 log (T(C.)) (2V2, .*)
Note that å E [0, 1] since
(2V3, 0+) > /v log (T(C.)). We obtain the following probability bound
3 d log (TC,,))
(z (2V3,00 0*)
KK -0)12 2 3v B log (Tic.) o3)
(2V2 2,0+)
$ exp
32
2
(37)
T|C_1
Finally, we establish an upper bound on the term (2 8*) as follows
(2v) 0*) < | v
2
$ V
(since || S 1)
0-T aetaf 0z Σ FEin
Vn (,'"",)) A
(x,, ((r.,8)) S (x",0")
Substituting in 37 get the lemma statement. This completes the proof of the lemma.
0
25

---

Lemma 20. Consider the same notation as Lemma then with probability greater than
19
1f (f
0, .ov / log (T(C.)
TX we have
12 d log (T(C.)).
(=V22 0" 0)1
Utilizing Lemma 10. with 1, a = 6y v _ log (TiC. and = V we have (z 03 - 12 log (T)..)). Since (2V 0*) 2 0, it follows, with probability greater than 1 T|-7] that
Proof.
d - log (TIC.)).
(=V2, -- 0*) s 12
Next, applying Lemma 11 with 5 and / log (T(Ce)), we have, with probability greater than T|x]
(2 0r pr-6 -0) Gu log (TIC.) s 12 log (T(C.)).
Hence, the lemma stands proved.
Lemma 21. If (x) 196 12 log T, then
PP [ 2 T
(38)
Proof. First, note (from Lemma 13 that arms from the solution of the D-optimal design problem selected (with probability greater than }) least T/3 times. Hence, we can use Lemmas 19
and 20 with T/3.
Let us consider the case where (y= V2, 0*) 2 / log (T(C.). We have that the following holds
with probability greater than 1 TIC_)*
0 0--01 8- 1 5 1 - (ye V Ø 8*)
(from (36)
Td
3v
log (T(CEl)x"", 0-)
(using Lemma 19
T
3
33d3d 3d vlog (T(c.))(a", (8))
-
Next, we note that [C.| < (3) 17 and by choosing 1/2 we get
Ø 0*
$ 7 (dd log (T) (T){**)8))
Taking union bound over all elements in C2 gives probability bound of 1 4.
26

---

Now, for the case where (ye V V2,0") we have, with probability greater than
0*)
0, / 3d log (TIGeD)
substituting T/3 in Lemma 20
T/C2]'
0 0-
(ye V 2 -7)
1
12v
d
log (TIC.
(using Lemma 20
1
7
3d3
244
log (T)
(substituting 0.5)
7 d vlawlog (x),
The last inequality is due to the fact that (x),0)) 2 196 18:6u log and T = 3vd2.. log T. We
again take a union bound over all elements Ce to get a probability bound of 7. Finally, union bound over the two cases and the event in Lemma 13 proves the lemma.
Lemma 22. If (x" 000) 196, d2.0y log T, then
log T
P(G2) 2
(39)
Proof. To prove Lemma 22 we follow the same steps as in the proof Lemma 21 19 and Lemma 20 with T', establish that for any fixed phase, the following inequality holds with probability greater than +:
Utilizing Lemma
@ 0r < < d log (xx", 08) 08))
Taking union bound over all at most log T phases Part of Algorithm 3 gives us the desired lower bound on I {G2).
Corollary 23. G holds, then for all X, @ calculated the end of Part I satisfies
3(x 03)d2.5 log T
Kxx, 0) (x. 00 S 1
T
Consider any phase & in Part II. G2 holds, then for every arm in the surviving arm set X, 0 calculated at the end of the phase satisfies
3(x², 3(x,,0 1e,,000ye v.)S...vvlo
(z, 0) (cr
T
Proof. First Hölder's inequality
(xx, 0" - و) < ||
1or δ b,yy
(40)
Since G holds, arms from the optimal design matrix are selected at least T/3 times; have by Lemma
3d
|| v V
T
Similarly, for every phase in Part II with T' = 2 /3 we have
d
| S $v / T
Finally, using bounds on |00 σ from events G1 and G2 and substituting in (40), we get the desired bound.
27

---

Corollary 24. If (f"x00 2 196
س2:5 log T
T
7
13
(=" 00")
S max (2x 0) - (x
(="00"
0*)
10
FeA
10
Proof. Since T' /3, via Corollary
23 any d calculated in Part or during any phase of Part
satisfies
3(0², 0" 022 log T
(o, 0) (x,,0)) sT) STV
T
We have
max =EX
(2,, 0) 2 (x"
(xr 000)d2.5v log
2 (0)) -7p
T
d2.5v T
2 (x",0")
71
(xt 0
2 10
7
(0'
(since (x" ,0, 2 196
d T
log
and T = 3/ /
T
Now, for any x E X.
(xt, Ar) 2 log T
(x. (x,00) +7V
d2.5v log T
I (x",0"
1 1171
13
$ 10 x 8
Hence, the lemma stands proved.
Lemma 25. If events G1 and G2 hold then the optimal arm x² always exists the surviving set X in every phase in Part II of Algorithm 3
Proof. Let
T/3 for Part and 7 T' for every phase of Part II. From Corollary 23 we have
(x+ 0+ )d)5) log T
(x" 0) > (,",0") 7V
(xt O+) ( log T
(x, )-) 7V
(since (x",0) (x,, 8*))
(x 22.5 log
2 (z. 0) 14V
(using Corollary 23
max SE
(a, (z, 0*)d25
2 (x, 0) 161
(using Corollary 24
Hence, the best arm will never satisfy the elimination criteria in Algorithm 3
Lemma 26. Given that events Gn and G2 hold, consider any phase index E in Part II Alg. For the surviving of arms X at the beginning of that phase, and for T / dd (lo.s (T), the following inequality holds for all E X
3d 0-)
0r) 2 (0'00) 26
(41)
2
28

---

Proof. Lemma 25 ensures that the optimal arm is contained in the surviving set of arms X. Fur- thermore, if arm E X' is pulled in the t phase, then it must be the case that arm was not eliminated in the previous phase (with a phase length parameter F) in particular the arms æ does satisfy the inequality on Line of 2 Algorithm This inequality reduces to
max oE (z, 8) d v log (T)
(r, 0) 2 (x", . 16,
r
2
10) d2.5 v log (T)
2 (x* 0) 26v
T
(via Corollary 24
Substituting T' 23/ in the above inequality proves the Lemma.
Theorem For any given stochastic linear bandits problem with set of arms X' C I time horizon T E E., and v-sub-Poisse rewards, Algorithm Saathhm@acchii achieves Nash regret
NRT = - VV log (T)(T))
Vv
Here, max (1, (x",0% 0*) log d}. with x= X denoting the optimal arm and 0* the (unknown) parameter vector.
Proof. Without loss of generality, we assume that (x*,0") 196 12 log T. Otherwise, the Nash
Regret bound is trivially true. For Part I, the product of expected rewards satisfies
( (=) 7 2(d 1)
Il EX(, G [1 2
(From Lemma 5
log(2rd uns
(x", 0r3
0r)
1 1
1og(2(d + T))
2 (x", 0r3
T
For Part II, we use Lemma 8 Let & denote the time interval of the 7th phase, and let T be the phase length parameter in that phase. Recall that |&,| T + d(d+1) Also, the algorithm runs for at most log T phases. Hence, we have
T II B(X,, | T+1
= II II
[( 0*) G1 Ggn
& 3EE,
16g1
d2.5 v (x+ (r) log (T)
II E
(x"00)) 26
T'2
E/1
(x" 8t) +
log
(2.5 log (T)
1 26
log T
(2.5 v log (T)
2 (x" 0z)
1 - 52
T |
(x) 0
29

---

The last inequality is due to the fact that (1 xx)" 2 (1 -rx) where E [0, 1] and x E [0.1
Note that the term
Log (T) (ot TT I 1/2 for (x*,0) 2 1961
d2-5z log T, T' 2 Td log T.
and T 2 e We further simplify the expression as follows
log T
1 - 52 Egl
1 v log (T)
log T
T d(d+1)
d2.5 log (T)
1 - 52
(I",0") T'
( 8T)
j=1
==1
log
d2.5 log (T)
- 78
T
(xr, 0r)
j=1
(assuming T' 2 d(d +))
log T
(2.5 v log (T)
2 78
T
T
(er 07)
2 1 78 1
d2.5 v log (T)
Tlog T
TV
(x0 04)
(using Cauchy Schwarz)
d2.5v
2 1 /
log (T).
T(x*, 0+)
Combining the lower bound for rewards in Part and Part of the algorithm, we obtain
II 10XX,,0''
0") GI [2] P(G
2 (x0,0') (r)
log(2(d I))T
(1 (1-78) 78-78
T(x*, log (og(T) P(GinG))
d2.5y
T
log(2(d 1))T
d..5v
(x000)
78
log (T) P[G1nG2)
T
T(x*, 0-)
log(2(d 1))T
d2.5v
(1 (1- 2 log T
(x",00 (4)
78
log (T) (T))
T(x0,0r) 0n)
log(2(d + 1))3 Tdv log(T)
d2.5y
2 2og T
2 (x",0")
1
T(x", log (T)
T
(x* 6 G2.5
log (T) - fa", log + 1))3 doo((T))
(x", 0*) 78
T
VT
Hence, the Nash Regret can be bounded as
1/T
NRT = (x'-0")
II EKX, 0781
< 78 (xt, 022
log (T) 2 (x",, 0-) log(((d 1))3 dv log(T)
(x",0'
VT
The theorem stands proved.
E
Experiments
We conduct experiments to compare the performance of our algorithm LINNASH with Thompson Sampling synthetic data. For comparison, select Thompson Sampling (Algorithm 1 in
30

---

0.22
LinNash
Thomson Sampling
0.18
Nash Regret
0.16
0.08
10000
15000
20000
25000
30000
35000 40000
45000
50000
Rounds
Figure 1: Nash Regret comparison of LINNASH and Thompson Sampling
Thempson Sampling
0.5
Round wi-e Reward
Round wise Reward
0.4
0.3
0.1
0.1
0.0
40800
10000
20000
40000
Rounds
Rounds
Figure 3: Round-wise reward for Thompson Sam- pling
Figure 2: Round-wise reward for LINNASH
2), instead of UCB/OFUL, since randomization is essential to achieve meaningful Nash Regret guarantees.
We fine-tune the parameters of both algorithms and evaluate their performance in the following experimental setup: We fix the ambient dimension == 80, the number of arms | 10000, and the number of rounds T 50000. Both the unknown parameter vector, 0*, and the arm embeddings are sampled from a multivariate Gaussian distribution. Subscquently, the arm embeddings are shifted and normalized to ensure that all mean rewards are non-negative, with the maximum reward mean being set to 0.5. Upon pulling an arm, we observe a Bernoulli random variable with probability corresponding to its mean reward.
In this experimental setting, we observe a significant performance advantage of LINNASH over Thompson Sampling. We plot our results in Figure which shows that the Nash regret of LINNASH decreases notably faster than that Thompson Sampling.
Another notable advantage of LINNASH evident from the experiments is due to successive elimination. The variance in the quality of arms pulled decreases the number of rounds progresses Figures
2 and This is due to the bulk climination of suboptimal arms at regular intervals. In contrast, Thompson Sampling incurs large variance in quality of arms being pulled even after several rounds, since no arms are being climinated at any point.
31


Reviews:
[{"review_id": "NnsiyyBEXx", "reviewer": "Reviewer_4BdU", "summary": "This paper proposes an approach based on the Nash regret to extend the stochastic linear bandits framework with fairness and welfare considerations. The Nash regret relies on the geometric mean of expected rewards induced by the linear bandit algorithm, which tends to incentivize uniformly high rewards as opposed to the average regret which promotes cumulatively high rewards. In this setting, the authors derived tight upper bounds on this strengthened notion of regret, thereby providing fairness guarantees as the geometric mean of rewards corresponds to the Nash social welfare (NSW) function.\n\nBuilding upon a novel sampling arms strategy based on John ellipsoid and optimal design, as well as tailored concentration bounds, the authors propose an algorithm that achieves $O\\left(\\sqrt{\\frac{d\\nu}{T}}log(T|\\chi|)\\right)$, for a finite set of arms $\\chi$, and $O\\left(\\frac{d^{5/4}\\nu^{1/2}}{\\sqrt{T}} log(T)\\right)$, in the infinite case.", "questions": "What is the computational efficiency of the LinNash algorithm?", "limitations": "The limitations of the proposed framework are not entirely clear.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is technically solid and well-motivated. I really like the idea of inherently imposing fairness to the bandit algorithm via the Nash regret. To the best of my knowledge, the authors' result is new and provides valuable insight into incorporating fairness and welfare considerations into bandit algorithms. In addition, the authors propose tail bounds that may be of broader interest.", "weaknesses": "Although the paper is technically well-set, the contribution seems incremental. The paper is also suffering from a lack of comparisons with existing approaches. The related work section seems a bit short. Having a richer picture of the literature would be beneficial for understanding the context of the paper’s contribution.\n\nLastly, I feel that the paper could benefit from numerical experiments that support the derived theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Although the paper is technically well-set, the contribution seems incremental.***\n\nThe work brings forth (1) important conceptual ideas and (2) entails substantive technical steps. We do not find these results to be incremental and believe the current paper will inspire future research.\n\n1) On the conceptual front, the current work is the first to address Nash regret in the important context of linear bandits. Nash regret systematically incorporates Nash social welfare, which, in turn, upholds fairness axioms, such as Pigou-Dalton transfer principle, scale invariance, and independence of unconcerned agents. Indeed, this principled approach of addressing fairness in bandit algorithms avoids ad hoc criteria and adjustments. \n\n2) On the technical front, the paper develops multiple, novel ideas for bounding the strengthened notion of regret; this includes, (i) sampling from a distribution whose mean is the centre of the John Ellipsoid induced by the arm vectors and (ii) tighter multiplicative forms of concentration bounds that are mean dependent using properties of sub-Poisson random variables. As mentioned in the writeup, these techniques will likely be of independent interest. \n \n\n***The paper could benefit from numerical experiments that support the derived theoretical results.***\n\nKindly see the common response (addressed to all the reviewers); it details experiments supporting our theoretical guarantees. \n\n\n***What is the computational efficiency of the LinNash algorithm?***\n \nThank you for this relevant question. Our algorithm (LinNash) is in fact computationally efficient. A detailed runtime analysis is provided in the common response (addressed to all the reviewers). \n"}, {"review_id": "T0dH78pxHP", "reviewer": "Reviewer_XR4M", "summary": "This paper considers the problem minimize 'Nash regret' in linear bandit, where Nash regret here is defined as the difference between the optimum and the geometric mean of expected rewards induced by the bandit algorithm. The stochastic reward in this paper is assumed sub-Poisson. The authors give algorithm to achieve Nash regret of $O(\\sqrt{d/T}log(T/|\\mathcal{X}|)$ when the set of arms $\\mathcal{X}\\in \\mathbb{R}^d$ is finite and $O(\\frac{d^{5/4}}{\\sqrt{T}}logT)$ when the set of arms $\\mathcal{X}$ is infinite.", "questions": "- The term \"Nash regret\" has been previously used in [1] and [2], but with a different definition from the one presented in this paper. The current name \"Nash regret\" in this paper does not capture the characteristic of the geometric mean.\n\n- Regarding the definition of Nash regret in this paper, the expectation is taken within the geometric mean instead of first taking the geometric mean and then the expectation. Is there any specific reasons or motivations behind the choice of this order?\n\n- In equation (3), the solution obtained provides the optimal sequence of arm pulls. What is the meaning of 'optimal' here? Further explanation and intuition behind equation (3) can be provided by the authors to better understand the optimality criteria and its implications.\n\n- In line 439 in the appendix, there's a wrong ref (Algorithm ??)\n\n[1] Cui, Qiwen, et al. \"Learning in congestion games with bandit feedback.\" Advances in Neural Information Processing Systems 35 (2022): 11009-11022.\n\n[2] Tay, Sebastian Shenghong, et al. \"No-regret Sample-efficient Bayesian Optimization for Finding Nash Equilibria with Unknown Utilities.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.", "limitations": "The authors have partially addressed the limitations of their work, though there is space for improvement (see the section Weaknesses and Questions).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper exhibits a good technical foundation. Specifically, in the finite-arm case, the upper bound is tightly bounded, even considering logarithmic terms.\n\n- The notion of regret explored in this paper is novel and is stronger compared to external regret.", "weaknesses": "The paper lacks experimental results. It would be benefical to compare other bandit algorithm with the algorithm in the paper specifically in terms of this kind of Nash regret.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***The term \"Nash regret\" has been previously used in [1] and [2], but with a different definition from the one presented in this paper. The current name \"Nash regret\" in this paper does not capture the characteristic of the geometric mean.*** \n\nThe papers [1] and [2] consider Nash equilibrium and, hence, refer to “Nash” in their regret analysis. In contrast, the current work builds upon the notion of Nash social welfare (also studied by John Nash). Nash social welfare is defined as the geometric mean of agents’ valuations.\n\n***Regarding the definition of Nash regret in this paper, the expectation is taken within the geometric mean instead of first taking the geometric mean and then the expectation. Is there any specific reasons or motivations behind the choice of this order?***\n\nKindly see Lines 108 to 114 for a full discussion on this very point. \nTo reiterate, taking the geometric mean of expectations corresponds to an ex ante evaluation of welfare: For each of the T agents (arriving one per round), we consider the expected reward (i.e., ex-ante utility) and then compute the welfare (apply geometric mean). Such ex ante assessments are standard in mathematical economics.  \n\nOn the other hand, Jensen’s inequality (in the multivariate form) implies that the variant wherein one considers expected value of the geometric is a more challenging objective. However, as discussed in [4], it is not possible to obtain non-trivial guarantees for the variant in general.\n\n \n***In equation (3), the solution obtained provides the optimal sequence of arm pulls. What is the meaning of 'optimal' here? Further explanation and intuition behind equation (3) can be provided by the authors to better understand the optimality criteria and its implications.***\n\nThank you for pointing out the need for further details. A thorough and mathematically rigorous answer to the question can be found in Chapter 21 of [Lattimore and Szepesvári, 2020]. \n\nAt a high level, given a budget B on the number of arm pulls, there are many possible sequences of B arms that can be selected. Here, an fundamental objective is to identify a sequence of B arms pulls such that the resulting least squares estimate $\\widehat{\\theta}$ (computed from the noisy rewards) minimizes the maximum confidence width in the estimated mean reward over the arms.\n\nThe optimality is in this exact sense. We will clarify this point further in updated version.\n\n***In line 439 in the appendix, there's a wrong ref***\n\nThank you for pointing the typo. We will fix it. \n\n"}, {"review_id": "5uAD9Gf9cd", "reviewer": "Reviewer_Cioh", "summary": "The paper extends algorithmic techniques for the linear bandits problem to the Nash Social Welfare objective function which ensures a level of fairness rather than merely the utilitarian welfare. Their work provides essentially optimal regret guarantees as compared to the traditional linear bandits problem (as it is well known that maximizing the geometric mean is necessarily stronger than the arithmetic mean). These results work for both a finite and infinite set of arms with slightly different regret guarantees.", "questions": "Can you provide a brief sketch of the final theorem (infinite arms) regret guarantee? I understand that the submissions page limit prevents this but it would be helpful to have one in the extended version of the paper.\n\nHave you considered the regret guarantees of the contextual bandits problem with a NSW objective?\n\nHave you considered the multiplicative regret on this multiplicative objective function as well?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper takes a novel approach to the linear bandits problem by adapting the objective function to one that ensures some level of fairness across agents in the given system. Moreover, all results appear sound and presented in a nice and compact form within the main text -- the sketches and intuition are clearly depicted with full proofs (not all of which were verified by this reviewer) in the appendix. In addition to near optimal regret guarantees on this modified problem instance, the authors provide various tail bounds that are of independent research to the community.", "weaknesses": "The paper lacks a comprehensive discussion on the related work surrounding this problem. Though the problem at hand is novel, it does hurt the submission to not include such context for readers. Specifically, there is considerable work on online NSW maximization which is naturally a similar problem. Moreover, discussion of the linear bandits problem and the best known results there would be very useful (in addition to the brief mention of Nash regret being a stronger guarantee). Some discussion on these results for finite and infinite arms would also potentially alleviate the issue of the gap between upper and lower bounds in the latter setting. As noted by the paper, improving the guarantee for the infinite arm problem setting would naturally strengthen the submission considerably.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***The paper lacks a comprehensive discussion on the related work surrounding this problem.***\n\nAs suggested in the review, we will add some discussion on online resource allocation (including online algorithms for NSW maximization).  \n\n \n***Can you provide a brief sketch of the final theorem (infinite arms) regret guarantee? I understand that the submissions page limit prevents this but it would be helpful to have one in the extended version of the paper.*** \n\nWith more available space in the final version, we will include a proof sketch for Theorem 2. Here is an outline:  \n​​\nTo analyse the infinite-arms case, we bound the norm difference between the computed least squares estimator, and the true (unknown) parameter vector. In particular, using the selection criterion for the set of surviving arms (see equation 11 in the paper) and an $\\epsilon$-net argument, we bound the error of the OLS estimate in terms of the reward of the best arm. The main technical novelty in this case is the $\\epsilon$-net argument which needs to be done carefully for this setting. Furthermore, since we sample following the D-optimal design, the confidence widths in the reward estimates of the surviving arms reduces exponentially in every phase. Combining these, for all surviving arms, we can bound the difference in reward with the best arm at every phase and, hence, bound the Nash regret overall. This completes the proof sketch. \n\n\n\n \n***Have you considered the regret guarantees of the contextual bandits problem with a NSW objective?***\n\nThe extension to contextual bandits requires independent ideas. Here, it is worth considering the recent result of Hanna, Yang, and Fragouli (COLT’23) that reduces linear, contextual bandits to standard linear bandits.  Note that, even for cumulative regret, contextual bandits (in the linear setting with changing arm sets) requires involved ideas;  see, e.g., the SupLinUCB paper by Chu et al. (2011). As mentioned in Section 5, we consider contextual bandits as an interesting direction of future work. \n\n\n***Have you considered the multiplicative regret on this multiplicative objective function as well?***\n\nThis is an interesting question. We have considered the multiplicative regret. However, the techniques and results are orthogonal to the current, standard treatment of regret. \n"}, {"review_id": "8IcAQNrgyh", "reviewer": "Reviewer_zbVi", "summary": "The authors consider stochastic linear bandits, and the goal is to minimize Nash regret, which is a stronger notion than the standard regret, by replacing the arithmetic mean reward of the learner over time with the geometric one in the definition.", "questions": "- The current algorithm requires $T$ as input. Do the authors think this is necessary? Part I in Algorithm 2 is somewhat non-standard for a successive elimination algorithm, so I guess it might be difficult to apply a doubling trick to remove the prior knowledge of $T$.\n- Does the sub-Poisson assumption include Gaussian as a special case? If not, can the analysis go through under sub-Gaussian?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. I didn't check the proof but I didn't spot any critical errors in the main text, either. The setting, the algorithms, and the proof sketch all make sense to me. I agree that indeed in some scenarios we may need to consider fairness across rounds and the definition of Nash regret in this paper is probably a good notion to consider in this case.", "weaknesses": "This setting is rarely known. It doesn't mean this problem is unimportant, but I think it would be better to provide more context for it to better evaluate the contributions. In the related work, the authors only mention that this setting differs from prior works because they all consider fairness across arms while this paper focuses on fairness across rounds. However, I would expect more discussions about this like whether previous techniques can be applied here. Also, there is no discussion about the Nash regret of multi-armed bandits, which is an important special case. Although this setup may not be meaningful in practice, it may provide insights into handling the linear case when designing algorithms or proving regret bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***no discussion about the Nash regret of multi-armed bandits, which is an important special case.***\n\n Perhaps the reviewer missed this, but Nash Regret in the context of stochastic multi-armed bandits (MAB) has already been addressed in [4]. The writeup extensively cites this prior work (see Lines 69-70, 89, 111, 180, 254). We have also discussed why the techniques for MAB in [4] fail in the context of linear bandits (see Sections 3.1 and 3.2 for a detailed discussion). \n\n***whether previous techniques can be applied here***\n\nPrevious techniques for analysing fairness across arms (for instance in [18]) are completely unrelated and are based more on combinatorial tools. To support this point, we will add a discussion in the next version of the manuscript.\n\n***The current algorithm requires T as input. Do the authors think this is necessary? Part I in Algorithm 2 is somewhat non-standard for a successive elimination algorithm, so I guess it might be difficult to apply a doubling trick to remove the prior knowledge of T.***\n\nIndeed, Part I requires the knowledge of T and resists the use of the doubling trick. Developing an anytime algorithm for Nash regret in the linear bandits context is an interesting problem and requires a different set of ideas.  \n\n***Does the sub-Poisson assumption include Gaussian as a special case? If not, can the analysis go through under sub-Gaussian?***\n\nKindly see the common response for a detailed discussion on connections between sub-Poisson and sub-Gaussian distributions.\n"}, {"review_id": "3TonzeNbJp", "reviewer": "Reviewer_K5vq", "summary": "In this research, the authors investigate the concept of Nash regret in the context of stochastic linear bandits. Nash regret represents the disparity between the optimal reward and the geometric mean of expected rewards, reflecting fairness considerations across different time instances within the Nash social welfare framework. The study assumes a fixed set of arms denoted as $\\mathcal{X}$, and an unknown vector $\\theta^*$. When an arm x is chosen, the agent observes a sub-Poisson $r_t$ with a mean of $<x,\\theta^*>$. The nash regret is defined as $max_x<x,\\theta^*>-(\\prod_t \\mathbb{E}[<X_t,\\theta^*>])^{1/T}$ where $X_t$ is a selected arm at time t.\n\nTo minimize Nash regret, the authors propose an algorithm that incorporates elimination phases. Firstly, to ensure the lower bound of expected rewards, they employ sampling via the Jon ellipsoid technique, as in Lemma 4. Additionally, they employ a G-optimal design to construct a probability distribution over arms, aiming to minimize the confidence interval width of estimated rewards. By combining these strategies, a sequence of arms is generated, and elimination phases are employed to remove arms with suboptimal mean rewards, utilizing upper confidence bounds (UCB) and lower confidence bounds (LCB) with a doubling time horizon for exploration.\nTo construct the UCB and LCB, a Nash confidence bound is utilized, which contains the mean reward value. Larger mean rewards correspond to larger confidence intervals, as defined in equation (8).\n\nThe theoretical analysis demonstrates that for a finite number of arms, the proposed algorithm achieves a nash regret of approximately $\\tilde{O}(\\sqrt{d/T})$. In the case of an infinite number of arms, the regret is $\\tilde{O}(d^{5/4}/\\sqrt{T})$ with a modified confidence width.", "questions": "- I'm wondering what is the reason for using an elimination-based algorithm rather than UCB.\n- wondering what is the reason to consider sub Poisson distribution rather than sub gaussian.\n- In line 504 (proof of Theorem 1 in appendix), when $\\langle x^*,\\theta^* \\rangle\\le \\sqrt{d\\nu/T}$, what is the reason that the NR bound, which contains $\\langle x^\\star,\\theta^\\star \\rangle$ in the bound,  trivially holds?", "limitations": "- This problem deals with a fixed arms set rather than a contextual linear setting.\n- The regret bound of $d^{5/4}$ in the case of infinite arms may not be tight, and it would be better to elaborate on why the factor of $5/4$ appears. ( $\\sqrt{d\\log|\\mathcal{X}|}$ regret bound for the finite case seems to imply $d$ when we consider $|\\mathcal{X}|=2^d$ for infinite case.)\n- There are no experimental results and discussion on the computational cost, which raises concerns about practical aspects\n\nMinor comments:\n\n- line 441 in Appendix: $d$-> $\\sqrt{d}$\n- line 449 in Appendix: $\\langle x,\\hat{\\theta}\\rangle \\le 20$ --> $\\langle x,\\hat{\\theta}\\rangle \\ge 20$\n- Lemma 7, equation (10) in Appendix: $P()\\le 4T^{-1}\\log T$ -->$P()\\ge 1-4T^{-1}\\log T$  ?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper addresses the concept of nash regret in the context of stochastic linear bandits.\n- It presents a novel algorithm based on elimination phases and provides a detailed regret analysis.", "weaknesses": "- The paper does not discuss the computational aspects of finding the G-optimal distribution and sampling via the John ellipsoid method.\n- It does not include experimental results.\n- In the case of infinite arms, the achieved regret bound may not be sufficiently tight, as it involves a factor of $d^{5/4}$ instead of just $d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***The paper does not discuss the computational aspects of finding the G-optimal distribution and sampling via the John ellipsoid method.***\n\nThank you for this relevant question. Our algorithm (LinNash) is in fact computationally efficient. A detailed runtime analysis is provided in the common response (addressed to all the reviewers). \n\n\n***It does not include experimental results.***\n\nKindly see the common response (addressed to all the reviewers); it details experiments supporting our theoretical guarantees. \n\n\n***I'm wondering what is the reason for using an elimination-based algorithm rather than UCB.***\n\nNote that, in the finite arms setting for linear bandits and even for cumulative regret, theoretical guarantees of UCB/OFUL and Phased Elimination have a gap of $\\sqrt{d}$; see Chapter 22 of [Lattimore and Szepesvári, 2022]. \n\nIn fact, in Chapter 25 of [Lattimore and Szepesvári, 2022] demonstrates the shortcomings of UCB-based algorithms when information is being shared across arms. For these reasons, we opted to focus on an elimination-based algorithm (rather than UCB). Furthermore, note that the results obtained in this work do not make any assumption on the set of arms. \n\n***wondering what is the reason to consider sub Poisson distribution rather than sub gaussian.***\n\nThe main purpose of using sub-Poisson random variables is to exploit tighter multiplicative forms of concentration bounds that are mean dependent. Having said that, many natural random variables (for instance bounded random variables) are jointly sub-Poisson and sub-Gaussian. Kindly see the common response for a detailed discussion on connections between sub-Poisson and sub-Gaussian distributions. \n\n***In line 504 (proof of Theorem 1 in appendix), when $\\dots$***\n\nThere is a typo in the Nash regret statement that caused this confusion. The Nash regret guarantees hold for the scaling factor $\\max( \\{ 1, \\langle x^*, \\theta^* \\rangle \\})$, in place of $\\langle x^*, \\theta^* \\rangle$. This fact has been explained in Lines 294-296, but we have missed placing the scaling factor, as such, in the final expression. \n\nWe thank the reviewer for the careful reading and will address it in the next version.\n\nNote that if we have the $f = \\max (\\{ 1, \\langle x^*, \\theta^* \\rangle\\})$ within the Nash Regret bound, then L504 is easy to follow: the Nash Regret by definition is less than $ \\langle x^*, \\theta^* \\rangle$ and therefore, when $ \\langle x^*, \\theta^* \\rangle = \\widetilde{O}(\\sqrt{d\\nu/T})$, the Nash regret must also be smaller. Hence, proving the WLOG statement.  \n"}]

Author rebuttal:
***Numerical Simulations***

Some reviewers have asked about numerical simulations. In the limited rebuttal time period, we have compared our algorithm LinNash with Thomson Sampling on synthetic data. Note that we chose Thomson Sampling (Algorithm 1 in [1]) instead of UCB/OFUL because it is crucial in our setting to use a randomized algorithm in order to achieve non-trivial Nash Regret guarantees. 

We tune parameters of both algorithms to the best of our ability and compare them in the following setting - we set the ambient dimension to be 80, number of arms to be 10000 and number of rounds to be 50000. Both the unknown parameter vector and the arm embeddings are drawn from a multi-variate gaussian. The arm embeddings are then shifted and normalized so that all true rewards are non-negative and the maximum true reward is 0.5. On pulling an arm, we observe a bernoulli random variable with probability corresponding to its true reward. 

In this setting, we observe that LinNash outperforms Thomson Sampling by a significant difference. Another advantage of LinNash that is apparent from this experiment is successive elimination - the variance in the quality of arms pulled reduces with rounds. This is because sub-optimal arms are being eliminated in bulk at regular intervals. 
In contrast, Thomson Sampling incurs a large variance in quality of arms being pulled even after several rounds - since no arms are being eliminated at any point.

[1] Shipra Agrawal and Navin Goyal. Thompson Sampling for Contextual Bandits with Linear Payoff (2014).


***Computational efficiency of the LinNash algorithm***
 
Some reviewers have asked this relevant question. Our algorithm (LinNash) is in fact computationally efficient. Here, we provide a detailed breakdown of the runtime analysis.

Time Complexity of the developed algorithm: Note that LinNash calls the subroutine GenerateArmSequence in Part 1 (that involves computing the John Ellipsoid). Also, the algorithm solves the optimal design problem once in Part 1 and at most O(log T) times in Part 2. 

We note that each of these modules execute in time polynomial in the size of the arm set. 
Optimal design - In Lines 150-163, we have described that the G-optimal design problem (eq. (3)) and the D-optimal design problem (eq. (4)) share the same optimal solution. The D-optimal design problem is a concave function and the Frank-Wolfe algorithm with rank-1 updates can be used to find the optimal solution efficiently (see Note 3 in Chapter 21 of [Lattimore and Szepesvári, 2022]). More specifically, as discussed in Chapter 3 of [Todd, 2016], the runtime of each iteration is $O(|\mathcal{X}|^2)$ and the number of iterations is at most $O(d)$. Here $|\mathcal{X}|$ is the number of arms and $d$ is the ambient dimension of the arm vectors.
Sampling via John Ellipsoid - Computing the John Ellipsoid given a set of arm vectors is equivalent to the D-optimal design problem (c.f., [Todd 2016]). Furthermore, approximate versions of John Ellipsoids (which also suffices for our purposes) can be computed much faster (see, e.g., [Cohen et al., 2020]) with a runtime of $O(|\mathcal{X}| d^2)$.

In summary, for each round , the runtime of our algorithm is quadratic in the number of arms and the ambient dimension. 

References: 
Minimum Volume Ellipsoids (Theory and Algorithms) by Michael J. Todd.
A near-optimal algorithm for approximating the John Ellipsoid by Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang (2020).


***Connection between sub-Poisson and sub-Gaussian random variables***
 
	
We will focus exclusively on positive random variables so that the Nash Regret is well defined. To provide a general connection between sub-Poisson and sub-Gaussian random variables, we can show the following Lemma: 

Lemma: Any positive $\sigma$ sub-Gaussian random variable, with mean $\mu$ is also  $\frac{\sigma^2}{\mu}$ sub-Poisson.

Before going to the proof, we make the following noteworthy observations using the above lemma:
Bounded, positive random variables are both sub-Gaussian and sub-Poisson (also discussed in Lemma 1).
The half-normal random variable (https://en.wikipedia.org/wiki/Half-normal_distribution), with a variance of $\sigma$, is also a C$\sigma$ sub-Poisson random variable, where C is a constant independent of distribution parameters.
For many positive sub-Gaussian random variables, including truncated and folded Normal distributions, the sub-Poisson parameter is small.

We leave a more in-depth analysis into the connections as future work. For the interested reader, we provide a proof of the above lemma below:

Proof: Let $X$ be any positive $\sigma$ sub-Gaussian random variable. For any positive $s$ and any $K \geq \frac{\sigma}{\mu}$, we have
 $ E[e^{sX}] \leq \texttt{exp} \left( s\mu + \frac{(s \sigma)^2 }{2}\right) \leq \texttt{exp} \left(\frac{\mu}{ K \sigma } \left(K s \sigma + \frac{(K s \sigma^2 )}{2} \frac{\sigma}{\mu K}\right)\right)$.

Now, since $K \geq  \frac{\sigma}{\mu}$ and $e^x \geq 1+ x+ \frac{x^2}{2}$ for non-negative $x$, we obtain $ E[e^{sX}] \leq \texttt{exp} \left(\frac{\mu}{ K \sigma } \left(e^{K s \sigma } - 1 \right)\right)$. 
For negative values of $s$, there exists a bounded random variable $Y$ which takes value in $[0, K \sigma]$ such that $E[e^{sX}] \leq E[e^{sY}]$. Now using Lemma 1 for bounded random variables we obtain $ E[e^{sX}] \le \texttt{exp} \left(\frac{\mu}{ K \sigma } \left(e^{K s \sigma } - 1 \right)\right)$. Finally, substituting $K = \frac{\sigma}{ \mu }$ proves that $X$ is $\frac{\sigma^2}{\mu}$ sub-Poisson.


Meta-review: The submission is a study on a stronger regret form of Nash regret for linear bandits that has fairness implications. The authors design tailored techniques to achieve good regret bounds for this case. All reviewers are positive towards the paper (with scores 7, 6, 6, 6, 6). The main issues raised by the reviewers, such as experimental evaluations and computational efficiency, have been addressed by the authors' rebuttal, and I am confident that they will be incorporate properly into the revised version of the paper. The reviewers also seemed to be satisfied by the rebuttals and some increases their scores as the result. I would like to recommend acceptance to the paper, and encourage the authors to incorporate all constructive comments from the reviewers into the final version of the paper.
Decision: Accept (poster)