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 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, \(\nu\)-sub-Poisson random variable. For this setting, we develop an algorithm that achieves a Nash regret of \(O\left( \sqrt{\frac{d\nu}{\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}\nu^{\frac{1}{2}}}{\sqrt{\mathsf{T}}} \log(\mathsf{T})\right)\). 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 of sampling via John ellipsoid in conjunction with the Kiefer-Wolfowitz optimal design.

1 Introduction↩︎

Bandit optimization is a prominent framework for sequential decision making and has several applications across multiple domains, such as healthcare [1]–[3] and advertising [4]. In this framework, we have a set of arms (possible actions) with unknown means and a time horizon. The goal is to sequentially pull the arms such that the regret—which is a notion of 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 \(\mathsf{T}\) agents, arriving one per round; in particular, the reward accrued at each round \(t \in [\mathsf{T}]\) corresponds to the value accrued by the \(t^{\mathsf{th}}\) agent. Indeed, such a welfarist connection exists in various applications of the bandit framework. Consider, for instance, the classic context of drug trials [5]: Suppose there are \(\mathsf{T}\) patients and several available drugs. In each round \(t\in [\mathsf{T}]\), one of the available drugs is administered to the \(t^{\mathsf{th}}\) patient. Subsequently, the reward accrued at the \(t^{\mathsf{th}}\) round corresponds to the efficacy of the administered drug to the \(t^{\mathsf{th}}\) patient. In such a setting, fairness is a fundamental consideration. That is, in addition to cumulative efficacy, individual effectiveness of the drugs is quite important.

A central notion in the bandit literature is that of average regret, defined as the difference between the (a priori unknown) optimum and the arithmetic mean of the expected rewards (accumulated by the algorithm) [6]. 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 performance to the social welfare it induces. Social welfare is defined as the sum of agent’s rewards [7] and can be high among a set of agents even if a 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 a 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, a bandit algorithm with low average regret is not guaranteed to induce fair outcomes across rounds.

Addressing this issue and with the overarching aim of achieving fairness across rounds (i.e., across agents that receive rewards from a bandit algorithm), the current work considers a strengthened notion of regret. 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 induced by the bandit algorithm. It is relevant to note that the geometric mean (of rewards) corresponds to the Nash social welfare (NSW) function [7]. This welfare function has been extensively studied in mathematical economics (see, e.g., [7]) and is known to satisfy fundamental fairness axioms, including the Pigou-Dalton transfer principle, scale invariance, and independence of unconcerned agents. Hence, by definition, Nash regret quantifies the performance of a 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 a 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 to a \(d\)-dimensional vector \(x\) (an arm-specific context) and the 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 [8]–[10]. The current paper extends the line of work on linear bandits with fairness and welfare considerations.

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 a very large range possibly making the regret vacuous, and (ii) This approach leads to a multiplicative guarantee and not an additive one. In a recent work of [11], 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 \(\mathcal{X}\) over a finite horizon of \(\mathsf{T}\) rounds. Since we consider the welfarist viewpoint, we assume that the rewards across all the rounds are positive and, in particular, model the distribution of the arm rewards to be \(\nu\)-sub-Poisson, for parameter \(\nu \in \mathbb{R}_+\). Our goal is to minimize the Nash regret \(\mathrm{\small NR}_{\mathsf{T}}\).

We develop a novel algorithm LinNash that obtains essentially optimal Nash regret guarantees for this setting. Specifically, for a finite set of arms \(\mathcal{X} \subset \mathbb{R}^d\), our algorithm LinNash achieves Nash regret \(\mathrm{\small NR}_{\mathsf{T}}=O\left( \sqrt{\frac{d\nu}{\mathsf{T}}} \log(\mathsf{T}|{ \cal X }|)\right)\). For infinite sets of arms, a modified version of LinNash achieves Nash regret \(\mathrm{\small NR}_{\mathsf{T}}=O\left( \frac{d^\frac{5}{4}\nu^{\frac{1}{2}}}{\sqrt{\mathsf{T}}} \log(\mathsf{T})\right)\).

Recall that Nash regret is a 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 \(\Omega\left( d /\sqrt{\mathsf{T}} \right)\) lower bound on average regret (see [12], Chapter 24) holds for Nash regret as 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 \(\mathsf{T}\). We also note that for instances in which the number of arms \(|\mathcal{X}|=\omega(2^d)\), 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 [lem:bounded95sub95poisson]). 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 a generalization of the result obtained in [11]. 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 beyond sub-Gaussian rewards [13], [14], our study of sub-Poisson rewards is interesting in its own right.⁵

Our linear bandit algorithm, LinNash, has two parts. In the first part, we develop a novel approach of sampling arms such that in expectation the reward obtained is a linear function of the center of John Ellipsoid [15]. Such a strategy ensures that the expected reward in any round of the first part is sufficiently large. The second part of LinNash runs in phases of exponentially increasing length. In each phase, we sample arms according to a distribution that is obtained as a solution of a concave optimization problem, known as D-optimal design. We construct confidence intervals at each phase and eliminate sub-optimal arms. A key novelty in our algorithm and analysis is 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.

There has been a recent surge in interest to achieve fairness guarantees in the context of multi-armed bandits; see, e.g., [16]–[20]. However, these works mostly consider fairness across arms and, in particular, impose fairness constraints that require each arm to be pulled a 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 in round \(t\). 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 [11], it 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,2,\dots,m\}\). For a matrix \(\mathbf{X}\), let \(\mathsf{Det}(\mathbf{X})\) to denote the determinant of \(\mathbf{X}\). For any discrete probability distribution \(\lambda\) with sample space \(\Omega\), write \(\mathsf{Supp}(\lambda)\triangleq \left\{x \in \Omega: \Pr_{X\sim \lambda} \left\{ X=x \right\} > 0 \right\}\) to denote the points for which the probability mass assigned by \(\lambda\) is positive. For a vector \(\mathbf{a}\in \mathbb{R}^d\) and a positive definite matrix \(\mathbf{V}\in \mathbb{R}^{d\times d}\), we will denote \({\left|\left|a\right|\right|}_{\mathbf{V}} :=\sqrt{a^T\mathbf{V}a}\). Finally, let \(\mathcal{B} := \{x\in \mathbb{R}^d\mid {\left|\left|x\right|\right|}_2=1\}\) be the \(d\)-dimensional unit ball.

We address the problem of stochastic linear bandits with a time horizon of \(\mathsf{T}\in \mathbb{Z}_+\) rounds. Here, an online algorithm (decision maker) is given a set of arms \({ \cal X }\subset \mathbb{R}^d\). Each arm corresponds to a \(d\)-dimensional vector. Furthermore, associated with each arm \(x \in { \cal X }\), we have a stochastic reward \(r_x \in \mathbb{R}_+\). In the linear bandits framework, the expected value of the reward \(r_x\) is modeled to be a linear function of \(x \in \mathbb{R}^d\). In particular, there exists an unknown parameter vector \(\theta^*\in \mathbb{R}^d\) such that, for each \(x \in { \cal X }\), the associated reward’s expected value \(\mathbb{E}[ r_x] = \langle x ,\theta^* \rangle\). Given the focus on welfare contexts, we will, throughout, assume that the rewards are positive, \(r_x>0\), for all \(x \in { \cal X }\).

The online algorithm (possibly randomized) must sequentially select an arm \(X_t\) in each round \(t\in [\mathsf{T}]\) and, then, it observes the corresponding (stochastic) reward \(r_{X_t}>0\).⁶ For notational convenience, we will write \(r_t\) to denote \(r_{X_t}\). In particular, if in round \(t\) the selected arm \(X_t = x\), then the expected reward is \(\langle x ,\theta^* \rangle\), i.e., \(\mathbb{E}[ r_t \mid X_t =x] = \langle x, \theta^*\rangle\). We will, throughout, use \(x^*\) to denote the optimal arm, \(x^* = \mathop{\mathrm{arg\,max}}_{x \in \cal X} \langle x ,\theta^* \rangle\) and \(\widehat{\theta}\) to denote estimator of \(\theta^*\).

In the stochastic linear bandits framework, our overarching objective is to minimize the Nash regret, defined as follows: \[\begin{align} \label{eq:nash} \mathrm{\small NR}_{\mathsf{T}} \mathrel{\vcenter{:}}= \max_{x \in \cal X} \langle x ,\theta^* \rangle - \left( \prod_{t=1}^\mathsf{T}\mathbb{E}[ \langle X_t ,\theta^* \rangle] \right)^{1/\mathsf{T}} \end{align}\tag{1}\] Note that the definition of Nash regret is obtained by applying the Nash social welfare (geometric mean) onto ex ante rewards, \(\mathbb{E}\left[ \langle X_t, \theta^*\rangle \right]\),⁷ accrued across the \(\mathsf{T}\) rounds.

2.1 Sub-Poisson Rewards↩︎

In order to model the environment with positive rewards (\(r_x >0\)), we assume that the rewards \(r_x\) associated with the arms \(x \in { \cal X }\) are \(\nu\)-sub Poisson, for some parameter \(\nu>0\). Formally, their moment-generating function satisfies the following bound \[\begin{align} \label{eq:sub95poisson} \mathbb{E}\left[ e^{\lambda \;r_x} \right] \leq \mathrm{exp}\left(\nu^{-1} \mathbb{E} [r_x] \;\left( e^{\nu\lambda} -1 \right) \right) = \mathrm{exp}\left(\nu^{-1}\langle x, \theta^*\rangle \left( e^{\nu\lambda} -1 \right) \right) \text{ for all }\lambda\in \mathbb{R}. \end{align}\tag{2}\] Note that a Poisson random variable is \(1\)-sub Poisson. To highlight the generality of \(\nu\)-sub-Poisson distributions, we note that bounded, non-negative random variables are sub-Poisson (Lemma [lem:bounded95sub95poisson]). Further, in Lemma [lem:subGaussian], we establish a connection between non-negative sub-Gaussian and sub-Poisson random variables. .

lemmaBoundedSubPoisson Any non-negative random variable \(X\in [0,\mathsf{B}]\) is \(\mathsf{B}\)-sub-Poisson, i.e., if mean \(\mathbb{E}[ X ] = \mu\), then for all \(\lambda \in \mathbb{R}\), we have \(\mathbb{E}[ e^{\lambda X } ] \leq \mathrm{exp} \left( B^{-1} \mu \left( e^{B\lambda} -1 \right) \right)\).

lemmaSubGaussian Let \(X\) be a non-negative sub-Gaussian random variable \(X\) with mean \(\mu = \mathbb{E}[X]\) and sub-Gaussian norm \(\sigma\). Then, \(X\) is also \(\left(\frac{\sigma^2}{\mu}\right)\)-sub-Poisson.

The proofs of Lemmas [lem:bounded95sub95poisson] and [lem:subGaussian] appear in Appendix 7. Lemma [lem:subGaussian] has useful instantiations. In particular, the lemma implies that the half-normal random variable, with variance of \(\sigma\), is also a \(\left(C \sigma\right)\)-sub-Poisson, where \(C\) is a constant (independent of distribution parameters). Similarly, for other well-studied, positive sub-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 \(\Delta(\mathcal{X})\) to denote the probability simplex associated with the set of arms \(\mathcal{X}\). Let \(\lambda\in \Delta(\mathcal{X})\) be such a probability distribution over the arms, with \(\lambda_x\) denoting the probability of selecting arm \(x\). The following optimization problem, defined over the set of arms \(\mathcal{X}\), is well-known and is referred to as the G-optimal design problem. \[\begin{align} \label{eq:goptimal} \text{Minimize } g(\lambda) \triangleq \max_{x\in \mathcal{X}} {\left|\left|x\right|\right|}^2_{\mathbf{U}(\lambda)^{-1}} \text{, where }\lambda\in \Delta(\mathcal{X}) \text{ and }\mathbf{U}(\lambda)=\sum_{x\in \mathcal{X}}\lambda_{x}xx^{T} \end{align}\tag{3}\] The solution to (3 ) provides the optimal sequence of arm pulls (for a given budget of rounds) to minimize the confidence width of the estimated rewards for all arms \(x\in \mathcal{X}\). The G-optimal design problem connects to the following optimization problem (known as D-optimal design problem): \[\begin{align} \label{eq:doptimal} \text{Maximize } f(\lambda) \triangleq \log \mathsf{Det}(\mathbf{U}(\lambda)) \text{, where }\lambda\in \Delta(\mathcal{X}) \text{ and }\mathbf{U}(\lambda)=\sum_{x\in \mathcal{X}}\lambda_{x}xx^{T} \end{align}\tag{4}\] The lemma below provides an important result of Kiefer and Wolfowitz [21].

Lemma 1 (Kiefer-Wolfowitz). If the set \(\mathcal{X}\) is compact and \(\mathcal{X}\) spans \(\mathbb{R}^{d}\), then there exists \(\lambda^*\in \Delta(\mathcal{X})\) supported over at most \(d(d+1)/2\) arms such that \(\lambda^*\) minimizes the objective in equation (3 ) with \(g(\lambda^*) = d\). Furthermore, \(\lambda^*\) is also a maximizer of the D-optimal design objective, i.e., \(\lambda^*\) maximizes the function \(f(\lambda)=\log \mathsf{Det}(\mathbf{U}(\lambda))\) subject to \(\lambda\in \Delta(\mathcal{X})\).

At several places in our algorithm, our goal is to find a probability distribution that minimizes the non-convex optimization problem (3 ). However, instead we will maximize the concave function \(f(\lambda)=\log \mathsf{Det}(\mathbf{U}(\lambda))\) over \(\lambda\in \Delta(\mathcal{X})\). The Frank-Wolfe algorithm, for instance, can be used to solve the D-optimal design problem (4 ) and compute \(\lambda^*\) efficiently ([12], Chapter 21). Lemma 1 ensures that this approach works, since the G-optimal and the D-optimal design problems have the same optimal solution \(\lambda^*\in \Delta(\mathcal{X})\), which satisfies \(\mathsf{Supp}(\lambda^*)\le d(d+1)/2\).⁸

2.3 John Ellipsoid.↩︎

For any convex body \(K\subset \mathbb{R}^d\), a John ellipsoid is 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 a factor of \(d\). Formally,⁹

Lemma 2 ([22]). Let \(K\subset \mathbb{R}^d\) be a 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 \subseteq K \subseteq c+d(E-c)\). Here, \(c \in \mathbb{R}^d\) denotes the center of \(E\) and \(c+d(E-c)\) refers to the (dialated) set \(\{c+d(x-c):x\in E\}\).

3 Our Algorithm LinNash and Main Results↩︎

Figure 1: GenerateArmSequence (Subroutine to generate Arm Sequence) — Figure 1: `GenerateArmSequence` (Subroutine to generate Arm Sequence)

Figure 2: LinNash (Nash Regret Algorithm for Finite Set of Arms)

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 I 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 is established in Subsection 3.3.

3.1 Part I: Sampling via John Ellipsoid and Kiefer-Wolfowitz Optimal Design↩︎

As mentioned previously, Nash regret is a more challenging objective than average regret: if in any round \(t\in [\mathsf{T}]\), the expected¹⁰ reward \(\mathbb{E} [r_{t}]\) is zero (or very close to zero), then geometric mean \((\prod_{t=1}^{\mathsf{T}}\mathbb{E} [r_{X_t}])^{1/\mathsf{T}}\) goes to zero, even if the expected rewards in the remaining rounds are large. Hence, we need to ensure that in every round \(t\in [\mathsf{T}]\), specifically the rounds in the beginning of the algorithm, the expected rewards are bounded from below. In [11], this problem was tackled for stochastic multi-armed bandits (MAB) by directly sampling each arm uniformly at random in the initial rounds. Such a sampling ensured that, in each of those initial rounds, the expected reward is bounded from below by the average of the expected rewards. While such a uniform sampling strategy is reasonable for the MAB setting, it can be quite unsatisfactory in the current context of linear bandits. To see this, consider a linear bandit instance in which, all—except for one—arms in \(\mathcal{X}\) are orthogonal to \(\theta^*\). Here, a uniform sampling strategy will lead to an expected reward of \(\langle x^*, \theta^* \rangle/|\mathcal{X}|\), which can be arbitrarily small for large cardinality \({ \cal X }\).

To resolve this issue we propose a novel approach in the initial \(\widetilde{\mathsf{T}} \mathrel{\vcenter{:}}= 3\sqrt{\mathsf{T}d\nu\log(\mathsf{T}|\mathcal{X}|)}\) rounds. In particular, we consider the convex hull of the set of arms \({ \cal X }\)—denoted as \(\mathrm{cvh}({ \cal X })\)— and find the center \(c\in \mathbb{R}^d\) of the John ellipsoid \(E\) for the convex hull \(\mathrm{cvh}(\mathcal{X})\). Since \(E\subseteq \mathrm{cvh}(\mathcal{X})\), the center \(c\) of the John ellipsoid is contained within \(\mathrm{cvh}(\mathcal{X})\) as well. Furthermore, via Carathéodory’s theorem [23], we can conclude that the center \(c\) can be expressed as a convex combination of at most \((d+1)\) points in \(\mathcal{X}\). Specifically, there exists a size-\((d+1)\) subset \(\mathcal{Y} := \{y_1,\dots,y_{d+1}\}\subseteq \mathcal{X}\) and convex coefficients \(\alpha_1,\dots,\alpha_{d+1} \in [0,1]\) such that \(c = \sum_{i=1}^{d+1} \alpha_i y_i\) with \(\sum_{i=1}^{d+1} \alpha_i = 1\). Therefore, the convex coefficients induce a distribution \(U\in \Delta({\mathcal{X}})\) of support size \(d+1\) and with \(\mathbb{E}_{x\sim U} \left[ x \right]= c\).

Lemma [lem:phaseI95mult95bound] 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 GenerateArmSequence (Algorithm [algo:opt95design]).

In particular, the purpose of the subroutine is to carefully construct a sequence (multiset) of arms \(\mathcal{S}\), with size \(\left|\mathcal{S}\right|=\widetilde{\mathsf{T}}\) and to be pulled in the initial \(\widetilde{\mathsf{T}}\) rounds. The sequence \(\mathcal{S}\) is constructed such that (i) upon pulling arms from \(\mathcal{S}\), we have a sufficiently large expected reward in each pull, and (ii) we obtain an initial estimate of the inner product of the unknown parameter vector \(\theta^*\) with all arms in \(\mathcal{X}\). Here, objective (i) is achieved by considering the above-mentioned distribution \(U\). Now, towards the objective (ii), we compute distribution \(\lambda\in \Delta(\mathcal{X})\) by solving the optimization problem (also known as the D-optimal design problem) stated in equation ([eq:d-optimal1]).

We initialize sequence \(\mathcal{S} = \emptyset\) and run the subroutine GenerateArmSequence for \(\widetilde{\mathsf{T}}\) iterations. In each iteration (of the for-loop in Line [line:for95loop1]), with probability \(1/2\), we sample an arm according to the distribution \(U\) (Line [line:sample95from95U]) and include it in \(\mathcal{S}\). Also, in each iteration, with remaining probability \(1/2\), we consider the computed distribution \(\lambda\) and, in particular, pick arms \(z\) from the support of \(\lambda\) in a round-robin manner. We include such arms \(z\) in \(\mathcal{S}\) while ensuring that, at the end of the subroutine, each such arm \(z\in \mathsf{Supp}(\lambda)\) is included at least \(\lceil \lambda_z \widetilde{\mathsf{T}}/3 \rceil\) times. We return the curated sequence of arms \(\mathcal{S}\) at the end of the subroutine.

Our main algorithm LinNash (Algorithm 2) first calls subroutine GenerateArmSequence to generated the sequence \(\mathcal{S}\). Then, the algorithm LinNash sequentially pulls the arms \(X_t\) from \(\mathcal{S}\), for \(1 \leq t \leq \widetilde{\mathsf{T}}\) rounds. For these initial \(\widetilde{\mathsf{T}} = |\mathcal{S}|\) rounds, let \(r_t\) denote the noisy, observed rewards. Using these \(\widetilde{\mathsf{T}}\) observed rewards, the algorithm computes the ordinary least squares (OLS) estimate \(\widehat{\theta}\) (see Line [line:initial95estimate] in Algorithm 2); in particular, \(\widehat{\theta} := (\sum_{t=1}^{\widetilde{\mathsf{T}}} X_tX_t^T)^{-1}(\sum_{t=1}^{\widetilde{\mathsf{T}}}r_tX_t)\). The algorithm uses the OLS estimate \(\widehat{\theta}\) to eliminate several low rewarding arms (in Lines [line:conf95bound1] and [line:eliminate1] in Algorithm 2). This concludes Part I of the algorithm LinNash.

Before detailing Part II (in Subsection 3.2), we provide a lemma to be used in the analysis of Part I of LinNash.

lemmaLemmaStageIBound Let \(c \in \mathbb{R}^d\) denote the center of a John ellipsoid for the convex hull \(\mathrm{cvh}({ \cal X })\) and let \(U\in \Delta(\mathcal{X})\) be a distribution that satisfies \(\mathbb{E}_{x\sim U} \;x = c\). Then, it holds that \[\begin{align} \mathbb{E}_{x\sim U}[ \langle x , \theta^*\rangle ] \geq \frac{ \langle x^* , \theta^*\rangle }{(d+1)}. \end{align}\]

Proof. Lemma 2 ensures that there exists a positive definite matrix \(\mathbf{H}\) with the property that \[\begin{align} \left\{x \in \mathbb{R}^d : \sqrt{(x-c)^T \mathbf{H} (x-c)} \leq 1 \right\} \subseteq \mathrm{cvh}({ \cal X }) \subseteq \left\{x \in \mathbb{R}^d : \sqrt{(x-c)^T \mathbf{H} (x-c)} \leq d \right\}. \end{align}\] Now, write \(y := c - \frac{x^* -c}{d}\) and note that \[\begin{align} \sqrt{(y-c)^T \mathbf{H} (y-c)} & = \sqrt{\frac{(x^* - c)^T \mathbf{H} (x^* -c)}{d^2}} \leq 1 ({ \cal X })} \end{align}\] Therefore, \(y \in \mathrm{cvh}({ \cal X })\). Recall that, for all arms \(x \in { \cal X }\), the associated reward (\(r_x\)) is non-negative and, hence, the rewards’ expected value satisfies \(\langle x ,\theta^* \rangle \geq 0\). This inequality and the containment \(y \in \mathrm{cvh}({ \cal X })\) give us \(\langle y ,\theta^* \rangle \geq 0\). Substituting \(y= c - \frac{x^* -c}{d}\) in the last inequality leads to \(\langle c,\theta^*\rangle \ge \langle x^* ,\theta^* \rangle/(d+1)\). Given that \(\mathbb{E}_{x \sim U} \;[x] = c\), we obtain the desired inequality \(\mathbb{E}_{x \sim U} \langle x, \theta^*\rangle = \langle c ,\theta^* \rangle \geq \frac{\langle x^* ,\theta^* \rangle}{(d+1)}.\) ◻

Note that at each iteration of the subroutine GenerateArmSequence, with probability \(1/2\), we insert an arm into \(\mathcal{S}\) that is sampled according to \(U\). Using this observation and Lemma [lem:phaseI95mult95bound], we obtain that, for any round \(t\in [\widetilde{\mathsf{T}}]\) and for the random arm \(X_t\) pulled from the sequence \(\mathcal{S}\) according to our procedure, the observed reward \(r_{X_t}\) must satisfy \(\mathbb{E} [r_{X_t}] \ge \frac{ \langle x^* , \theta^*\rangle }{2(d+1)}\).¹¹

Further, recall that in the subroutine GenerateArmSequence, we insert arms \(x\in \mathsf{Supp}(\lambda)\) at least \(\lceil \lambda_x \widetilde{\mathsf{T}}/3 \rceil\) times, where \(\lambda\) corresponds to the solution of D-optimal design problem defined in equation ([eq:d-optimal1]). Therefore, we can characterize the confidence widths of the estimated rewards for each arm in \(\mathcal{X}\) computed using the least squares estimate \(\widehat{\theta}\) computed in Line [line:conf95bound1] in Algorithm 2.

Broadly speaking, we can show that all arms with low expected reward (less than a threshold) also have an estimated reward at most twice the true reward. On the other hand, high rewarding arms must have an estimated reward to be within a factor of \(2\) of the true reward. Thus, based on certain high probability confidence bounds (equation (5 )), we can eliminate arms in \(\mathcal{X}\) 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 is quite common to use, for each arm \(x\), a confidence width (interval) that does not depend on \(x\)’s estimated reward. This is a 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 leads to a 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 \(\langle x^*,\theta^* \rangle\). 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, it 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 [24]. In prior work [11] 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 \(x\), any least squares estimator \(\phi\) (of \(\theta^*\)), and \(t\) the number of observations used to compute the estimator \(\phi\). That is, for any triple \((x,\phi,t)\in \mathcal{X}\times \mathbb{R}^d\times[\mathsf{T}]\), we define Lower Nash Confidence Bound (\(\mathrm{LNCB}\)) and Upper Nash Confidence Bound (\(\mathrm{UNCB}\)) as follows: \[\begin{align} \label{eq:confidence95bound} & \mathrm{LNCB}(x,\phi,t) \! \mathrel{\vcenter{:}}= \! \langle x ,\phi \rangle \! - \!6\sqrt{\frac{ \langle x ,\phi \rangle \nu d \log{\!(\mathsf{T}|{\cal X}|)\!}}{t}} \nonumber \\ & \mathrm{UNCB}(x,\phi,t) \! \mathrel{\vcenter{:}}= \! \langle x ,\phi \rangle \! + \! 6\sqrt{\frac{ \langle x ,\phi \rangle \nu d \log{\!(\mathsf{T}|{\cal X}|)\!}}{t}}. \end{align}\tag{5}\] As mentioned previously, the confidence widths in equation (5 ) 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 ([12], Chapter 21); a key distinction here is to use the Nash confidence bounds defined in (5 ). Part II in Algorithm 2 begins with the set of arms \(\widetilde{\mathcal{X}}\subseteq \mathcal{X}\) obtained after an initial elimination of low rewarding arms in Part I . Subsequently, Part II runs in phases of exponentially increasing length and eliminates sub-optimal arms in every phase.

Suppose at the beginning of the \(\ell^{\mathsf{th}}\) phase, \(\widetilde{\mathcal{X}}\) is the updated set of arms. We solve the D-optimal design problem (see ([eq:d-optimal2])) corresponding to \(\widetilde{\mathcal{X}}\) to obtain a distribution \(\lambda\in \Delta(\widetilde{\mathcal{X}})\). For the next \(O(d^2+2^{\ell}\widetilde{\mathsf{T}})\) rounds, we pull arms \(a\) in the support of \(\lambda\) (Line [line:pull2]): each arm \(a \in \mathsf{Supp}(\lambda)\) is pulled \(\lceil \lambda_a \mathsf{T}' \rceil\) times where \(\mathsf{T}'=O(2^{\ell}\widetilde{\mathsf{T}})\). Using the data covariance matrix and the observed noisy rewards, we recompute: (1) an improved estimate \(\widehat{\theta}\) (of \(\theta^*\)) 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 [line:conf2] and [line:eliminate2]).

The following lemma provides the key concentration bound for the least squares estimate.

lemmaMainConcentration Let \(x_1,x_2,\dots,x_s\in \mathbb{R}^d\) be a fixed set of vectors and let \(r_1,r_2,\dots,r_s\) be independent \(\nu\)-sub-Poisson random variables satisfying \(\mathbb{E}r_s= \langle x_s,\theta^*\rangle\) for some unknown \(\theta^*\). Further, let matrix \(\mathbf{V}=\sum_{j=1}^s x_jx_j^{T}\) and \(\widehat{\theta}= \mathbf{V}^{-1}\left( \sum_{j} r_j x_j \right)\) be the least squares estimator of \(\theta^*\). Consider any \(z\in \mathbb{R}^d\) with the property that \(z^T\mathbf{V}^{-1}x_j \leq \gamma\) for all \(j\in [s]\). Then, for any \(\delta \in [0,1]\) we have \[\begin{align} \mathbb{P} \left\{ \langle z ,\widehat{\theta} \rangle \geq (1+ \delta) \langle z ,\theta^* \rangle \right\} & \leq \mathrm{exp} \left( - \frac{\delta^2 \langle z ,\theta^* \rangle }{3 \nu \gamma} \right) \tag{6}\text{ and } \\ \mathbb{P} \left\{ \langle z , \widehat{\theta} \rangle \leq (1 - \delta) \langle z , \theta^* \rangle \right\} & \leq \mathrm{exp} \left( - \frac{\delta^2 \langle z , \theta^* \rangle }{2 \nu \gamma} \right) \tag{7}. \end{align}\]

Lemma [lem:mult95concentration] is established in Appendix 8. Using this lemma, we can show that the optimal arm \(x^*\) is never eliminated with high probability.

lemmaOptArmNotEliminated Consider any bandit instance in which for the optimal arm \(x^* \in \cal{X}\) we have \(\langle x^* ,\theta^* \rangle \geq 192 \sqrt{\frac{d \; \nu }{T}}\log(\mathsf{T}|{ \cal X }|)\). Then, with probability at least \(\left(1- \frac{4\log{\mathsf{T}}}{\mathsf{T}} \right)\), the optimal arm \(x^*\) always exists in the surviving set \(\widetilde{\mathcal{X}}\) in Part I and in every phase in Part II of Algorithm 2.

Finally, using Lemmas [lem:mult95concentration] and [lem:best95arm], we show that, with high probability, in every phase of Part II all the surviving arms \(x \in \widetilde{{ \cal X }}\) have sufficiently high reward means.

lemmaStageIIRewardBound Consider any phase \(\ell\) in Part II of Algorithm 2 and let \(\widetilde{{ \cal X }}\) be the surviving set of arms at the beginning of that phase. Then, with \(\widetilde{\mathsf{T}}=\sqrt{d\nu\mathsf{T}\log(\mathsf{T}\left|\mathcal{X}\right|)}\), we have \[\label{eq:confidence} \Pr \left\{\langle x ,\theta^* \rangle \geq \langle x^* ,\theta^* \rangle - 25 \sqrt{\frac{ 3d \nu \langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{2^{\ell}\cdot \widetilde{\mathsf{T}}}} \text{ for all }x\in \widetilde{\mathcal{X}}\right\} \ge 1 - \frac{4\log{\mathsf{T}}}{\mathsf{T}}\tag{8}\] Here, \(\nu\) is the sub-Poisson parameter of the stochastic rewards.

The proofs of the Lemmas [lem:best95arm] and [lem:phase95II95reward95bound] are deferred to Appendix 9.

3.3 Main Result↩︎

This section states and proves the Nash regret guarantee achieved by LinNash (Algorithm 2).

theoremSizeDependentRegret For any given stochastic linear bandits problem with (finite) set of arms \(\mathcal{X}\subset \mathbb{R}^d\), time horizon \(\sf{T} \in \mathbb{Z}_+\), and \(\nu\)-sub-Poisson rewards, Algorithm 2 achieves Nash regret \[\begin{align} \mathrm{\small NR}_{\mathsf{T}}= O\left( \beta \sqrt{\frac{ \;d \;\nu }{\mathsf{T}}} \log(\mathsf{T}|{ \cal X }|)\right). \end{align}\] Here, \(\beta = \max \left\{1, \;{\langle x^* ,\theta^* \rangle} \log d \right\}\), with \(x^* \in \mathcal{X}\) denoting the optimal arm and \(\theta^*\) the (unknown) parameter vector.

Proof. We will assume, without loss of generality, that \(\langle x^* ,\theta^* \rangle \geq 192 \sqrt{\frac{d \; \nu }{\mathsf{T}}}\log(\mathsf{T}|{ \cal X }|)\), otherwise the stated Nash Regret bound directly holds (see equation (1 )). Write \(E\) to denote the ‘good’ event identified in Lemma [lem:phase95II95reward95bound]; the lemma ensures that \(\mathbb{P}\{ E \} \geq 1 - \frac{4\log{\mathsf{T}}}{\mathsf{T}}\).

During Part I of Algorithm 2, the product of expected rewards, conditioned on \(E\), satisfies \[\begin{align} \prod_{t = 1}^{\widetilde{\mathsf{T}}} \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid E ]^\frac{1}{\mathsf{T}} &\geq \left(\frac{\langle x^* ,\theta^* \rangle}{2(d+1)}\right)^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} }\\ &=\langle x^* ,\theta^* \rangle^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} \left(1-\frac{1}{2}\right)^{\frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}}} \\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} \left(1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} \right). \end{align}\] For analyzing Part II, we will utilize Lemma [lem:phase95II95reward95bound]. Write \({ \cal B }_\ell\) to denote all the rounds \(t\) that belong to \(\ell^{\text{th}}\) phase (in Part II). Also, let \(\mathsf{T}'_\ell\) denote the associated phase-length parameter, i.e., \(\mathsf{T}'_\ell = 2^\ell \;\widetilde{\mathsf{T}}/3\). Note that in each phase \(\ell\) (i.e., in the for-loop at Line [line:LinNashForLoop] of Algorithm 2), every arm \(a\) in \(\mathsf{Supp}(\lambda)\) (the support of D-optimal design) is pulled \(\lceil \lambda_a \mathsf{T}'_\ell \rceil\) times. Given that \(|\mathsf{Supp}(\lambda)| \leq d(d+1)/2\), we have \(|{ \cal B }_\ell| \leq \mathsf{T}'_\ell + \frac{d(d+1)}{2}\). By construction \(\mathsf{T}'_\ell \geq \frac{d(d+1)}{2}\) and, hence, \(|{ \cal B }_\ell| \leq 2 \mathsf{T}'_\ell\). Since the phase length parameter, \(\mathsf{T}'_\ell\), doubles after each phase, the algorithm would have at most \(\log{\mathsf{T}}\) phases. Hence, the product of expected rewards in Part II satisfies \[\begin{align} \prod_{t = \widetilde{\mathsf{T}}+1 }^{\mathsf{T}} \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid E ]^\frac{1}{\mathsf{T}} &= \prod_{{ \cal B }_\ell} \prod_{t \in { \cal B }_\ell } \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid E ]^\frac{1}{\mathsf{T}} \\ &\geq \prod_{{ \cal B }_\ell} \left(\langle x^* ,\theta^* \rangle - 25 \sqrt{\frac{ d \;\nu \;\langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}'_\ell}} \right)^{ \frac{|{ \cal B }_\ell|}{\mathsf{T}}} } \\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\mathsf{T}-\widetilde{\mathsf{T}}}{\mathsf{T}}} \prod_{\ell=1}^{\log \mathsf{T}} \left( 1 - 25 \sqrt{\frac{ d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_\ell}} \right)^{\frac{|{ \cal B }_\ell|}{\mathsf{T}}}\\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\mathsf{T}-\widetilde{\mathsf{T}}}{\mathsf{T}}} \prod_{\ell=1}^{\log \mathsf{T}} \left( 1 - 50 \frac{|{ \cal B }_\ell|}{\mathsf{T}} \sqrt{\frac{ d \; \nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_\ell}} \right) . \end{align}\] The last inequality follows from the fact that \((1-x)^r \geq (1 - 2rx)\), for any \(r \in [0,1]\) and \(x \in [0,1/2]\). Note that the term \(\sqrt{\frac{ d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_\ell}} \leq 1/2\), since \(\langle x^* ,\theta^* \rangle \geq 192 \sqrt{\frac{d \nu }{\mathsf{T}}}\log(\mathsf{T}|{ \cal X }|)\) along with \(\mathsf{T}'_\ell \geq 2 \sqrt{\mathsf{T}d \nu \log{\mathsf{T}\cal|X|}}\) and \(\mathsf{T}\geq e^4\). We further simplify the expression as follows \[\begin{align} \prod_{\ell=1}^{\log \mathsf{T}} \left( 1 - 50 \frac{|{ \cal B }_\ell|}{\mathsf{T}} \sqrt{\frac{ d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_\ell}} \right) & \geq \prod_{\ell=1}^{\log \mathsf{T}} \left( 1 - 100 \frac{\sqrt{\mathsf{T}'_\ell}}{\mathsf{T}} \sqrt{\frac{ d \;\nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle}} \right) _\ell| \leq 2 \mathsf{T}'_\ell}\\ &\geq 1 - \frac{100}{\mathsf{T}} \sqrt{\frac{ d \;\nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle}} \left( \sum_{\ell=1}^{\log{\mathsf{T}}} \sqrt{\mathsf{T}'_\ell} \right)a,b \geq 0}\\ &\geq 1 - \frac{100}{\mathsf{T}} \sqrt{\frac{ d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle}} \left( \sqrt{\mathsf{T}\log{\mathsf{T}}} \right)\\ & \geq 1 - 100 \sqrt{\frac{ d \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T}|{ \cal X }|)}. \end{align}\] Combining the lower bound for the expected rewards in the two parts we get \[\begin{align} \prod_{t = 1}^{\mathsf{T}} \mathbb{E}[ \langle X_t ,\theta^* \rangle]^\frac{1}{\mathsf{T}} &\geq \prod_{t = 1}^{\mathsf{T}} \biggl( \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid E ] \;\mathbb{P}\{ E \}\biggr) ^\frac{1}{\mathsf{T}} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} \right) \left( 1 - 100 \sqrt{\frac{ d \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T}|{ \cal X }|)} \right)\mathbb{P}\{ E \} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} - 100 \sqrt{\frac{ d \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T}|{ \cal X }|)} \right)\mathbb{P}\{ E \} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} - 100 \sqrt{\frac{ d \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T}|{ \cal X }|)} \right)\left(1 - \frac{4 \log \mathsf{T}}{\mathsf{T}} \right) \\ & \geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) 3\sqrt{\mathsf{T} d \nu \log (\mathsf{T}|\cal{X}|)} }{\mathsf{T}} - 100 \sqrt{\frac{ d \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T}|{ \cal X }|)} - \frac{4 \log \mathsf{T}}{\mathsf{T}} \right) \\ & \geq \langle x^* ,\theta^* \rangle - 100 \sqrt{\frac{\langle x^* ,\theta^* \rangle d \; \nu }{\mathsf{T}}} \log{(\mathsf{T}|{ \cal X }|)} - 6 \langle x^* ,\theta^* \rangle \sqrt{\frac{ d \;\nu \;\log (\mathsf{T}|\cal{X}|)}{\mathsf{T}} }\log(2(d+1)) . \end{align}\] Therefore, the Nash Regret can be bounded as \[\begin{align} \mathrm{\small NR}_{\mathsf{T}} &= \langle x^* ,\theta^* \rangle - \left( \prod_{t=1}^{\mathsf{T}} \mathbb{E}[ \langle X_t ,\theta^* \rangle ] \right)^{1/{\mathsf{T}}} \nonumber \\ &\leq 100 \sqrt{\frac{\langle x^* ,\theta^* \rangle d \; \nu }{\mathsf{T}}} \log{(\mathsf{T}|{ \cal X }|)} + 6 \sqrt{\frac{ d \;\nu \;\log (\mathsf{T}|\cal{X}|)}{\mathsf{T}} }\log(2(d+1)) \langle x^* ,\theta^* \rangle \tag{9} \\ & \leq \left( 100 \sqrt{ \langle x^* ,\theta^* \rangle } + 6 \log(2(d+1)) \langle x^* ,\theta^* \rangle \right) \;\sqrt{\frac{d \nu}{\mathsf{T}}} \log{(\mathsf{T}|{ \cal X }|)} \;\tag{10} \end{align}\] Hence, with \(\beta = \max \left\{1,\sqrt{ \langle x^* ,\theta^* \rangle }, {\langle x^* ,\theta^* \rangle} \log d \right\} = \max \left\{1, \;{\langle x^* ,\theta^* \rangle} \log d \right\}\), from equation (10 ) we obtain the desired bound on Nash regret \(\mathrm{\small NR}_{\mathsf{T}} = O\left( \beta \sqrt{\frac{ \;d \;\nu }{\mathsf{T}}} \log(\mathsf{T}|{ \cal X }|)\right)\). The theorem stands proved. ◻

Note that, in Theorem [thm:size95dependent], lower the value of the optimal expected reward, \(\langle x^*, \theta^* \rangle\), stronger is the Nash regret guarantee. In particular, with a standard normalization assumption that \(\langle x^*, \theta^* \rangle \leq 1\) and for \(1\)-sub Poisson rewards, we obtain a Nash regret of \(O\left( \sqrt{\frac{d}{\mathsf{T}}} \log(\mathsf{T}|{ \cal X }|)\right)\). Also, observe that the regret guarantee provided in Theorem [thm:size95dependent] depends logarithmically on the size of \(\mathcal{X}\). Hence, the Nash regret is small even when \(\left|\mathcal{X}\right|\) is polynomially large in \(d\).

3.3.0.1 Computational Efficiency of LinNash.

We note that Algorithm 2 (LinNash) executes in polynomial time. In particular, the algorithm calls the subroutine GenerateArmSequence in Part I for computing the John Ellipsoid. Given a set of arm vectors as input, this ellipsoid computation can be performed efficiently (see Chapter 3 in [25]). In fact, for our purposes an approximate version of the John Ellipsoid suffices, and such an approximation can be found much faster [26]; specifically, in time \(O(|{ \cal X }|^2d)\). Furthermore, the algorithm solves the D-optimal design problem, once in Part I and at most \(O(\log \mathsf{T})\) times in Part II. The D-optimal design is a concave maximization problem, which can be efficiently solved using, say, the Frank-Wolfe algorithm with rank-\(1\) updates. Each iteration takes \(O(|{ \cal X }|^2)\) time, and the total number of iterations is at most \(O(d)\) (see, e.g., Chapter 21 of [12] and Chapter 3 in [25]). Overall, we get that LinNash is a polynomial-time algorithm.

4 Extension of Algorithm LinNash for Infinite Arms↩︎

Figure 3: LinNash (Nash Confidence Bound Algorithm for Infinite Set of Arms)

The regret guarantee in Theorem [thm:size95dependent] depends logarithmically on \(\left|\mathcal{X}\right|\). Such a dependence makes the guarantee vacuous when the set of arms \(\mathcal{X}\) is infinitely large (or even \(\left|\mathcal{X}\right|=\Omega(2^{\sqrt{\mathsf{T}d^{-1}}})\)). To resolve this limitation, we extend LinNash with a modified confidence width that depends only on the largest estimated reward \(\gamma \mathrel{\vcenter{:}}= \max_{x \in {\cal{X}}} \langle x ,\widehat{\theta} \rangle\). Specifically, we consider the confidence width \(16 \sqrt{\frac{ \gamma \;d^{\frac{5}{2}} \;\nu \; \log{(\mathsf{T})}}{\mathsf{T}'}}\), for all the arms, and select the set of surviving arms in each phase (of Part II of the algorithm for infinite arms) as follows:

\[\begin{align} \widetilde{\cal{X}} = \left\{ x \in {\cal{X}}: \langle x ,\widehat{\theta} \rangle \geq \gamma - 16 \sqrt{\frac{ \gamma \;d^{\frac{5}{2}} \;\nu \; \log{(\mathsf{T})}}{\mathsf{T}'}} \right\}\label{eq:surviveXinf} \end{align}\tag{11}\]

See Algorithm 3 for details. The theorem below is the main result of this section.

theoremSizeIndependentRegret For any given stochastic linear bandits problem with set of arms \(\mathcal{X} \subset \mathbb{R}^d\), time horizon \(\sf{T} \in \mathbb{Z}_+\), and \(\nu\)-sub-Poisson rewards, Algorithm 2 achieves Nash regret \[\begin{align} \mathrm{\small NR}_{\mathsf{T}}=O\left( \beta \frac{ d^\frac{5}{4} \sqrt{\nu }}{\sqrt{{\mathsf{T}}} } \log(\mathsf{T})\right), \end{align}\] Here, \(\beta = \max \left\{1, \;{\langle x^* ,\theta^* \rangle} \log d \right\}\), with \(x^* \in \mathcal{X}\) denoting the optimal arm and \(\theta^*\) the (unknown) parameter vector.

Proof of Theorem [thm:second] and a detailed regret analysis of Algorithm 3 can be found in Appendix 10.

5 Experiments↩︎

We conduct experiments to compare the performance of our algorithm LinNash with Thompson Sampling on synthetic data. For a comparison, we select Thompson Sampling (Algorithm 1 in [27]), 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 \(d = 80\), the number of arms \(|\mathcal{X}| = 10000\), and the number of rounds \(\mathsf{T} = 50000\). Both the unknown parameter vector, \(\theta^*\), and the arm embeddings are sampled from a multivariate Gaussian distribution. Subsequently, 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 a 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 4, which shows that the Nash regret of LinNash decreases notably faster than that of 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 as the number of rounds progresses – see Figures 5 and [fig:Plot32of32arm32variance32TS]. This is due to the bulk elimination of suboptimal arms at regular intervals. In contrast, Thompson Sampling incurs a large variance in quality of arms being pulled even after several rounds, since no arms are being eliminated at any point.

6 Conclusion and Future Work↩︎

Fairness and welfare considerations have emerged as a central design objective in online decision-making. 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 \(d^{5/4}\), where \(d\) is the ambient dimension. Note that, for linear bandits with infinite arms, [8] obtains a bound of \(d/\sqrt{\mathsf{T}}\) for average regret. We conjecture that a similar dependence should be possible for Nash regret as well and pose this strengthening as a relevant direction of future work. Another important direction would be to study Nash regret for other bandit frameworks (such as contextual bandits and combinatorial bandits) and Markov Decision Processes (MDPs).

7 Proof of Lemmas [lem:bounded95sub95poisson] and [lem:subGaussian]↩︎

Proof. For random variable \(X\) we have \[\begin{align} \mathbb{E}\left[\mathrm{exp}\left( \lambda X \right) \right] &= \mathbb{E}\left[\mathrm{exp}\left( \lambda B \frac{X}{B} + (1 - \frac{X}{B}) 0 \right) \right] \\ &\leq \mathbb{E}\left[\frac{X}{B} e^{\left( \lambda B \right)} + \left( 1 - \frac{X}{B}\right) e^0 \right] \\ &= 1 + \frac{\mathbb{E}\left[ X \right]}{\mathsf{B}}\left( e^{\lambda \mathsf{B}} - 1\right) \\ &\leq 1 + \frac{\mu}{\mathsf{B}} \left( e^{\lambda \mathsf{B}} - 1\right)\\ &\leq \mathrm{exp}\left( \frac{\mu}{\mathsf{B}} \left( e^{\lambda \mathsf{B}} - 1\right) \right). \end{align}\] ◻

Proof. Since \(X\) is a \(\sigma\)-sub-Gaussian random variable, for any non-negative scalar \(s \geq 0\), we have \[\begin{align} \mathbb{E}[e^{sX}] &\leq \mathrm{exp}\left( s\mu + \frac{(s \sigma)^2 }{2}\right) \nonumber \\ &= \mathrm{exp}\left(\frac{\mu^2}{ \sigma^2 } \left( \frac{s \sigma^2}{\mu} + \frac{1}{2} \left(\frac{ s \sigma^2}{\mu} \right)^2 \right)\right) \label{eq:subgmgf} \end{align}\tag{12}\] The fact that \(X\) is a positive random variable implies that the mean \(\mu >0\). Also, the considered scalar \(s \geq 0\) and, hence, the term \(\frac{s \sigma^2}{\mu} > 0\). Also, recall that \(e^x \geq 1+ x+ \frac{x^2}{2}\), for any non-negative \(x\). Using these observations and equation (12 ), we obtain \[\begin{align} \mathbb{E}[e^{sX}] \leq \mathrm{exp}\left(\frac{\mu^2}{ \sigma^2 } \left(e^{ \frac{s \sigma^2}{\mu} } - 1 \right)\right) \label{eq:supmgf} \end{align}\tag{13}\] For random variable \(X\), inequality (13 ) ensures that the required mgf bound (equation (2 )) holds for all non-negative \(s\) and with sub-Poisson parameter equal to \(\frac{\sigma^2}{ \mu}\).

We next complete the proof by showing that the mgf bound holds for negative \(s\) as well. Towards this, write \(B \mathrel{\vcenter{:}}= \frac{\sigma^2}{ \mu}\) and define random variable \(Y \mathrel{\vcenter{:}}= \mathbf{1}_{\{X \leq B\}} \; X + \mathbf{1}_{\{X > B\}} \;B\). Note that \(Y\) is a positive, bounded random variable. Furthermore, for any negative \(s\), we have \(\mathrm{exp}\left( s Y \right) \geq \mathrm{exp}\left( s X\right)\). Therefore, for a negative \(s\), it holds that \(\mathbb{E}\left[\mathrm{exp}(s X)\right] \leq \mathbb{E}\left[ \mathrm{exp}\left( s Y \right) \right]\). Since positive random variable \(Y \in [0,B]\), the mgf bound obtained in Lemma [lem:bounded95sub95poisson] gives us \[\begin{align} \mathbb{E}[e^{sX}] \leq \mathbb{E}\left[ e^{sY} \right] \leq \mathrm{exp}\left( \frac{\mu}{\mathsf{B}} \left( e^{s \mathsf{B}} - 1\right) \right). \end{align}\] Since \(B \mathrel{\vcenter{:}}= \frac{\sigma^2}{ \mu}\), the mgf bound (equation (2 )) on \(X\) holds for negative \(s\) as well. This, overall, shows that \(X\) is a \(\left(\frac{\sigma^2}{ \mu} \right)\)-sub-Poission random variable. The lemma stands proved. ◻

8 Proof of Concentration Bounds↩︎

Proof. We use the Chernoff method to get an upper bound on the desired probabilities, as shown below \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \langle z ,\theta^* \rangle \right\} & = \mathbb{P}\left( \mathrm{exp}(c \;\langle z ,\widehat{\theta} \rangle ) \geq \mathrm{exp}( c (1+ \delta) \langle z ,\theta^* \rangle ) \right)\\ & \leq \frac{\mathbb{E}[ \mathrm{exp}\left(c \; z^T \mathbf{V}^{-1} \left( \sum_{t} r_t x_t \right) \right)]}{\mathrm{exp}(c \;(1+ \delta) \langle z ,\theta^* \rangle )} \\ & = \frac{\prod_{t=1}^{s}\mathbb{E}[ \mathrm{exp}\left( c \;r_t \mathbf{V}^{-1} x_t \right)]}{\mathrm{exp}(c \; (1+ \delta) \langle z ,\theta^* \rangle )}\\ & \leq \frac{\prod_{t=1}^{s} \mathrm{exp}\left( \frac{\mathbb{E}[r_t]}{\nu} \left( e^{c \nu z^T \mathbf{V}^{-1} x_t} -1 \right) \right) }{\mathrm{exp}(c \;(1+ \delta) \langle z ,\theta^* \rangle )}\\ & = \exp \left( -c \langle z ,\theta^* \rangle (1+\delta) + \sum_{t=1}^{s} \frac{\langle x ,\theta^* \rangle}{\nu} \left( e^{c \;\nu z^T \mathbf{V}^{-1} x_t} -1 \right) \right). \end{align}\] Substituting \(c = \frac{ \log(1+\delta)}{\nu \gamma}\), we get \[\begin{align} \mathbb{P}& \left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \langle z ,\theta^* \rangle \right\} \leq \exp \left( -\frac{\langle z ,\theta^* \rangle}{\nu \gamma} (1+\delta) \log{(1+\delta)} + \sum_{t=1}^{s} \frac{\langle x_t ,\theta^* \rangle}{\nu} \left( (1+\delta)^{\frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t} -1 \right) \right). \label{ineq:before95kw} \end{align}\tag{14}\] Since \(\frac{1}{\gamma} z^T\mathbf{V}^{-1}x_t \leq 1\) we have \((1+\delta)^{\frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t} \leq 1+ \delta \cdot \frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t\). Substituting in (14 ) we get

\[\begin{align} \mathbb{P}& \left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \langle z ,\theta^* \rangle \right\} \\ & \leq \exp \left( -\frac{1}{\nu \gamma} \langle z ,\theta^* \rangle (1+\delta) \log{(1+\delta)} + \sum_{t=1}^{s} \langle x_t ,\theta^* \rangle \cdot \frac{\delta}{\nu \gamma} z^T \mathbf{V}^{-1} x_t \right) \\ & = \exp \left( -\frac{1}{\nu \gamma} \langle z ,\theta^* \rangle (1+\delta) \log{(1+\delta)} + \frac{\delta}{\nu \gamma} \sum_{t=1}^{s} \theta^{*T} x_t x_t^T \mathbf{V}^{-1} z \right)\\ & = \exp \left( -\frac{1}{\nu \gamma} \langle z ,\theta^* \rangle (1+\delta) \log{(1+\delta)} + \frac{\delta}{\nu \gamma} \langle z ,\theta^* \rangle \right). ^{s} x_t x_t^T = \mathbf{V} } \end{align}\]

Using the logarithmic inequality \(\log(1 + \delta) \geq \frac{2 \delta}{2 + \delta}\), we further simplify as \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \langle z ,\theta^* \rangle \right\} & \leq \exp \left( -\frac{\langle z ,\theta^* \rangle}{\nu \gamma} \left((1+\delta) \log{(1+\delta)} - \delta \right) \right) \\ & \leq \exp \left( \frac{-\delta ^2 \langle z ,\theta^* \rangle}{\left(2+ \delta\right) \nu \gamma}\right) \\ & \leq \exp \left( \frac{-\delta ^2 \langle z ,\theta^* \rangle}{3 \nu \gamma }\right). \end{align}\] Following similar steps and substituting \(c = \frac{\log(1 - \delta)}{\nu \gamma}\), we obtain a bound on the lower tail (inequality 7 ): \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \leq (1- \delta) \langle z ,\theta^* \rangle \right\} \leq \exp \left( -\frac{1}{\nu \gamma} \langle z ,\theta^* \rangle (1 - \delta) \log{(1- \delta)} - \frac{\delta}{ \nu \gamma} \langle z ,\theta^* \rangle \right). \end{align}\] Now, using the logarithmic inequality \((1 - \delta) \log(1 - \delta) \geq -\delta + \frac{\delta^2}{2}\), we get \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \leq (1- \delta) \langle z ,\theta^* \rangle \right\} \leq \exp \left( \frac{-\delta ^2 \langle z ,\theta^* \rangle}{2 \nu \gamma} \right) \end{align}\] ◻

Combining (7 ) and (6 ) we get the following Corollary.

Corollary 1. Using the notations as in Lemma [lem:mult95concentration], we have \[\mathbb{P}\left\{ |\langle z ,\widehat{\theta} \rangle - \langle z ,\theta^* \rangle| \geq \delta \langle z ,\theta^* \rangle \right\} \leq 2 \;\mathrm{exp}\left( - \frac{\delta^2 \langle z ,\theta^* \rangle }{3\gamma} \right).\]

The next two lemmas are variants of Lemma [lem:mult95concentration] where we bound the error in terms of an upper bound on \(\langle z ,\theta^* \rangle\).

Lemma 3. Let \(x_1,x_2,\dots,x_s\in \mathbb{R}^d\) be a fixed set of vectors and let \(r_1,r_2,\dots,r_s\) be independent \(\nu-\)sub Poisson random variables satisfying \(\mathbb{E}r_s= \langle x_s,\theta^*\rangle\) for some unknown \(\theta^*\). In that case, let matrix \(\mathbf{V}=\sum_{j=1}^s x_jx_j^{T}\) and \(\widehat{\theta}= \mathbf{V}^{-1}\left( \sum_{j} r_j x_j \right)\) be the least squares estimator of \(\theta^*\). Consider any \(z\in \mathbb{R}^d\) that satisfies \(z^T\mathbf{V}^{-1}x_j \leq \gamma\) for all \(j\in [s]\) and \(\langle z ,\theta^* \rangle \leq \alpha\). Then for any \(\delta \in [0,1]\) we have \[\mathbb{P}\left\{ \langle z ,\widehat{\theta} \rangle \geq (1+ \delta) \alpha \right\} \leq e^{ - \frac{\delta^2 \alpha }{3\gamma \nu} }.\]

Proof. Following the same approach as in the proof of Lemma [lem:mult95concentration], we have \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \alpha \right\} & \leq\frac{\mathbb{E}[ \mathrm{exp}(c \; z^T \mathbf{V}^{-1}\left( \sum_{t} r_t x_t \right))]}{\mathrm{exp}(c \;(1+ \delta) \alpha )}\\ & \leq \exp \left( -c \alpha (1+\delta) + \sum_{t=1}^{s} \frac{\langle x_t , \theta^* \rangle}{\nu} \left( e^{c \nu z^T \mathbf{V}^{-1} x_t} -1 \right) \right) \end{align}\] Now, substituting \(c = \frac{1}{\nu \gamma} \log{(1+ \delta)})\) and using \((1+\delta)^{\frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t} \leq 1+ \delta \cdot \frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t\) we have \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \geq (1+ \delta) \alpha \right\} & \leq \exp \left( -\frac{1}{\gamma \nu} \alpha (1+\delta) \log{(1+\delta)} + \sum_{t=1}^{s} \frac{\langle x_t ,\theta^* \rangle}{\nu}{\theta^*} \left( (1+\delta)^{\frac{1}{\gamma} z^T \mathbf{V}^{-1} x_t} -1 \right) \right) \\ & \leq \exp \left( -\frac{1}{\nu \gamma} \alpha (1+\delta) \log{(1+\delta)} + \frac{\delta}{\nu \gamma} \sum_{t=1}^{s} \theta^{*T} x_t x_t^T \mathbf{V}^{-1} Z \right) \\ & = \exp \left( -\frac{1}{\nu \gamma} \alpha (1+\delta) \log{(1+\delta)} + \frac{\delta}{\nu \gamma} \langle z ,\theta^* \rangle \right) \\ & \leq \exp \left( -\frac{1}{\nu \gamma} \alpha (1+\delta) \log{(1+\delta)} + \frac{\delta}{\nu \gamma} \alpha \right)\\ & \leq \exp \left( \frac{-\delta ^2 \alpha}{\left(2+ \delta\right) \nu \gamma}\right) {2+ \delta}} \end{align}\] Since \(\delta \in [0,1]\), we have the desired result. ◻

Lemma 4. Using the same notations as in Lemma 3, for any \(\delta \in [0,1]\), the following holds \[\mathbb{P}\left\{ \langle z ,\widehat{\theta} \rangle \leq \langle z ,\theta^* \rangle - \delta \alpha \right\} \leq \mathrm{exp}\left( - \frac{\delta^2 \alpha }{2\gamma \nu} \right)\\None\]

Proof. Using steps similar to the previous lemmas, we obtain \[\begin{align} \mathbb{P}\left\{ \langle z , \widehat{\theta} \rangle \leq \langle z ,\theta^* \rangle - \delta \alpha \right\} & \leq\frac{\mathbb{E}[ \mathrm{exp}(c \; z^T \mathbf{V}^{-1}\left( \sum_{t} r_t x_t \right))]}{\mathrm{exp}(c \;(\langle z ,\theta^* \rangle - \delta \alpha))}\\ & \leq \exp \left( c \alpha \delta + c\langle z ,\theta^* \rangle+ \sum_{t=1}^{s} \frac{\langle x_t , \theta^* \rangle}{\nu} \left( e^{c \nu z^T \mathbf{V}^{-1} x_t} -1 \right) \right) \end{align}\] Substituting \(c = \frac{\log(1-\delta)}{\nu \gamma }\) and simplifing we get \[\begin{align} \mathbb{P}\left\{ \langle z ,\widehat{\theta} \rangle \leq \langle z ,\theta^* \rangle - \delta \alpha \right\} \leq \mathrm{exp}\left( -\frac{\langle z ,\theta^* \rangle}{\nu \gamma} \left( \log{(1- \delta)} + \delta \right) + \frac{\alpha}{\nu \gamma} \delta \log{(1 -\delta)} \right) \end{align}\] Note that since \(\log(1 -\delta) + \delta\) is negative, we can upper bound the above expression by replacing \(\langle z ,\theta^* \rangle\) with \(\alpha\). \[\begin{align} \mathbb{P}\left\{ \langle z ,\widehat{\theta} \rangle \leq \langle z ,\theta^* \rangle - \delta \alpha \right\} & \leq \mathrm{exp}\left( -\frac{\alpha}{\nu \gamma} \left( \log{(1- \delta)} + \delta - \delta \log{(1 -\delta)} \right)\right) \\ & \leq \mathrm{exp}\left( - \frac{\delta^2 \alpha }{2\nu \gamma} \right) {2}}. \end{align}\] Hence, the lemma stands proved. ◻

9 Regret Analysis of Algorithm 2: Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

We will first define events \(E_1\) and \(E_2\) for each phase of the algorithm and show that they hold with high probability. We will use the events in the regret analysis.

Event \(E_1\): At the end of Part I, let \(\widehat{\theta}\) be the unbiased estimator of \(\theta^*\) and \(\widetilde{\mathsf{T}}\) be as defined in Algorithm 2. All arms \(x \in {\cal X}\) with \(\langle x ,\theta^* \rangle < 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\) satisfy \[\langle x ,\widehat{\theta} \rangle \leq 20\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}} \label{ineq:E951195first}\tag{15}\] In addition, all arms \(x \in \cal{X}\) with \(\langle x ,\theta^* \rangle \geq 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\) satisfy \[\begin{align} |\langle x ,\theta^* \rangle - \langle x ,\widehat{\theta} \rangle| & \leq 3\sqrt{\frac{ d \nu \langle x ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\widetilde{\mathsf{T}}}} \tag{16} \;\;\;\text{ and } \\ \frac{1}{2}\langle x ,\theta^* \rangle \leq & \langle x ,\widehat{\theta} \rangle \leq \frac{4}{3} \langle x ,\theta^* \rangle. \tag{17} \end{align}\]
Event \(E_2\): Let \(\widetilde{{ \cal X }}\) denote the surviving set of arms at the start of a phase in Part II, and \(\mathsf{T}'\) be as defined in Algorithm 2. For all phases and for all \(x \in \widetilde{{ \cal X }}\) such that \(\langle x ,\theta^* \rangle \geq 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\), the estimator \(\widehat{\theta}\) (calculated at the end of a phase) satisfies \[\begin{align} |\langle x ,\theta^* \rangle - \langle x ,\widehat{\theta} \rangle| & \leq 3\sqrt{\frac{d \nu \langle x ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} \tag{18} \;\;\;\text{ and }\\ \frac{1}{2}\langle x ,\theta^* \rangle \leq & \langle x ,\widehat{\theta} \rangle \leq \frac{4}{3} \langle x ,\theta^* \rangle.\tag{19} \end{align}\]

9.1 Supporting Lemmas↩︎

Lemma 5 (Chernoff Bound). Let \(Z_1, \ldots, Z_n\) be independent Bernoulli random variables. Consider the sum \(S = \sum_{r=1}^n Z_r\) and let \(\mu = \mathbb{E}[S]\) be its expected value. Then, for any \(\varepsilon \in [0,1]\), we have \[\begin{align} \mathbb{P}\left\{ S \leq (1-\varepsilon) \mu \right\} & \leq \mathrm{exp} \left( -\frac{\mu \varepsilon^2}{2} \right). \end{align}\]

Lemma 6. During Part I, arms from D-optimal design are added to \(S\) at least \(\widetilde{\mathsf{T}}/3\) times with probability greater than \(1 - \frac{1}{\mathsf{T}}\).

Proof. We use Lemma 5 with \(Z_i\) as indicator random variables that take value one when an arm from \({\cal A}\) (the support of \(\lambda\) in the optimal design) is chosen. By setting \(\varepsilon = \frac{1}{3}\) and \(\mu = \frac{\widetilde{\mathsf{T}}}{2}\), we obtain the required probability bound. ◻

Lemma 7. Using the notations in Algorithm [algo:opt95design], if the event in Lemma 6 holds, then for each \(x \in { \cal X }\) and each round \(t\) in Part I of the algorithm, we have \[x^T \mathbf{V}^{-1} X_t \leq \frac{3d}{\widetilde{\mathsf{T}}},\] where \(X_t\) is the arm pulled in round \(t\).

Proof. Let \(\mathbf{U}(\lambda)\) and \(\lambda\) denote the optimal design matrix (as defined in (4 )) and the solution to the D-optimal design problem in Algorithm [algo:opt95design], respectively. That is, \(\lambda\) is the solution of the optimization problem stated in equation ([eq:d-optimal1]) and \(\mathbf{U}({\lambda})=\sum_{x\in \mathcal{X}}\lambda_x xx^T\). Lemma 1 implies that \({\left|\left|x\right|\right|}_{\mathbf{U}(\lambda)^{-1}}\le \sqrt{d}\) for all \(x \in \mathcal{X}\).

Next, note that the construction of the sequence \(\mathcal{S}\) in Part I (Subroutine GenerateArmSequence) and the event specified in Lemma 6 give us \(\mathbf{V}\succ \frac{\widetilde{\mathsf{T}}}{3} \mathbf{U}(\lambda)\). Hence, \[\begin{align} x^T \mathbf{V}^{-1} X_t & \leq \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \left\lVert \mathbf{V}^{-1} X_t \right\rVert_{\mathbf{V}} lder's inequality} \nonumber \\ & = \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \left\lVert X_t \right\rVert_{\mathbf{V}^{-1}} \nonumber \\ & \leq \left\lVert x \right\rVert_{\left(\frac{\widetilde{\mathsf{T}}}{3} \mathbf{U}(\lambda)\right)^{-1}} \left\lVert X_t \right\rVert_{\left(\frac{\widetilde{\mathsf{T}}}{3} \mathbf{U}(\lambda)\right)^{-1}} \nonumber \succ \frac{\widetilde{\mathsf{T}}}{3} \mathbf{U}(\lambda)} \\ & = \sqrt{\frac{3 }{\widetilde{\mathsf{T}}}} \left\lVert x \right\rVert_{ \mathbf{U}(\lambda)^{-1}} \sqrt{\frac{3 }{\widetilde{\mathsf{T}}}} \left\lVert X_t \right\rVert_{ \mathbf{U}(\lambda)^{-1}} \nonumber \\ & \leq \sqrt{\frac{3d }{\widetilde{\mathsf{T}}}} \sqrt{\frac{3d}{\widetilde{\mathsf{T}}}} } \\ & = \frac{3d}{\widetilde{\mathsf{T}}}. \nonumber \end{align}\] ◻

The next lemma lower bounds the probability of event \(E_1\) (see equations (15 ), (16 ), and (17 )).

lemmaLemmaStageIIBound Event \(E_1\) holds with probability at least \(1-\frac{6}{T}\).

Proof. First, consider all arms \(x \in { \cal X }\) for which \(\langle x ,\theta^* \rangle < 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\). Here, we invoke Lemma 3, with \(\gamma = \frac{3d}{\widetilde{\mathsf{T}}}\) (as derived in Lemma 7), \(\alpha = 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\), and \(\delta = 1\), to obtain \[\begin{align} \mathbb{P}\left\{ \langle x ,\widehat{\theta} \rangle \leq 20\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}} \right\} & \leq \mathrm{exp}\left( -\frac{\delta^2 \alpha}{3\gamma \nu} \right) \nonumber \\ & \leq \mathrm{exp}\left( -\frac{10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}} 3\sqrt{T d \nu \log (\mathsf{T}|\cal{X}|)}}{3 \nu d} \right) \nonumber \\ & \leq \frac{1}{\mathsf{T}|{ \cal X }|} \label{ineq:subE951} \end{align}\tag{20}\]

Next, we consider arms \(x \in \mathcal{X}\) such that \(\langle x ,\theta^* \rangle \geq 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\) and for such arms establish equations (16 ) and (17 ). Towards this, we invoke Lemma [lem:mult95concentration], with parameters \(\gamma = \frac{3d}{\widetilde{\mathsf{T}}}\) and \(\delta = 3\sqrt{\frac{d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x ,\theta^* \rangle \widetilde{\mathsf{T}}}}\). It is relevant to note that here \(\delta \in [0,1]\) – this containment follows from the condition \(\langle x ,\theta^* \rangle\geq 10 \sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\) and \(\widetilde{\mathsf{T}}= 3\sqrt{\mathsf{T}d \nu \log (\mathsf{T}|\cal{X}|)}\). Therefore, \[\begin{align} \mathbb{P}\left\{ |\langle x ,\theta^* \rangle - \langle x ,\widehat{\theta} \rangle| \geq 3\sqrt{\frac{ d \nu \langle x ,\theta^* \rangle \log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}} \right\} & = \mathbb{P}\left\{ |\langle x ,\theta^* \rangle - \langle x ,\widehat{\theta} \rangle| \geq \delta \langle x ,\theta^* \rangle \right\} |{ \cal X }|)}}{\langle x ,\theta^* \rangle \widetilde{\mathsf{T}}}}} \nonumber \\ & \leq 2 \exp\left( -\frac{\frac{9d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x ,\theta^* \rangle \widetilde{\mathsf{T}}} \;\langle x ,\theta^* \rangle}{3\nu \frac{3d}{\widetilde{\mathsf{T}}}} \right) } \nonumber \\ & = \frac{2}{\mathsf{T}|{ \cal X }|} \label{ineq:subE952} \end{align}\tag{21}\] For establishing equation (17 ), we invoke Lemma [lem:mult95concentration] again, now with \(\gamma = \frac{3d}{\widetilde{\mathsf{T}}}\) and \(\delta = \frac{1}{3}\): \[\begin{align} \mathbb{P}\left\{ \langle x ,\widehat{\theta} \rangle \geq \frac{4}{3} \langle x ,\theta^* \rangle \right\} &\leq \mathrm{exp}\left( -\frac{3\sqrt{\mathsf{T}\nu d \log (\mathsf{T}|\cal{X}|)} \;\langle x ,\theta^* \rangle}{27 \nu d} \right) \nonumber\\ & \leq \mathrm{exp}\left( -\frac{3\sqrt{\mathsf{T}\nu d \log (\mathsf{T}|\cal{X}|)} \; 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}}}}{27 \nu d} \right) \nonumber\\ & \leq \frac{1}{\mathsf{T}|{ \cal X }|} \label{ineq:subE953} \end{align}\tag{22}\] Similarly, with \(\delta = \frac{1}{2}\), Lemma [lem:mult95concentration] gives us \[\begin{align} \mathbb{P}\left\{ \langle x ,\widehat{\theta} \rangle \leq \frac{1}{2} \langle x ,\theta^* \rangle \right\} \leq \frac{1}{\mathsf{T}|{ \cal X }|} \label{ineq:subE954} \end{align}\tag{23}\] Finally, we combine (20 ), (21 ), (22 ) and (23 ), and apply a union bound over all arms in \({ \cal X }\). Then, conditioning on the event in Lemma 6 leads to the stated probability bound. The lemma stands proved. ◻

The next lemma shows that event \(E_2\) (see equations (18 ) and (19 )) holds with high probability

Lemma 8. Event \(E_2\) holds with probability at least \(1-\frac{3 \log \mathsf{T}}{T}\).

Proof. Consider any phase in Part II and let \(\mathbf{U}(\lambda)\) be the optimal design matrix obtained after solving the D-optimal design problem at the start of the phase. By Lemma 1, for all \(x, z \in \widetilde{{ \cal X }}\) we have \[\begin{align} z^T \mathbf{V}^{-1} x & \leq \left\lVert z \right\rVert_{\mathbf{V}^{-1}} \left\lVert \mathbf{V}^{-1} x \right\rVert_{\mathbf{V}} lder's inequality} \nonumber \\ & \leq \left\lVert z \right\rVert_{\mathbf{V}^{-1}} \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \\ & \leq \sqrt{\frac{d }{\mathsf{T}'}} \sqrt{\frac{d}{\mathsf{T}'}} = \frac{d}{\mathsf{T}'} \end{align}\]

First, we address equation (18 ). In particular, we instantiate Lemma [lem:mult95concentration] with \(\delta =3 \sqrt{\frac{ d \nu \log{(\mathsf{T}|{\cal X}|)}}{\langle x ,\theta^* \rangle \mathsf{T}'}}\) and \(\gamma = \frac{d}{\mathsf{T}'}\). Note that given the lower bound on \(\langle x ,\theta^* \rangle\) and the inequality \(\mathsf{T}'\geq 2\sqrt{\mathsf{T}d \nu \log (\mathsf{T}|\cal{X}|)}\) ensure that \(\delta\) lies in \([0,1]\). Hence, substituting these values of \(\delta\) and \(\gamma\) in Lemma [lem:mult95concentration], we obtain \[\begin{align} \mathbb{P}\left\{ |\langle x ,\theta^* \rangle - \langle x ,\widehat{\theta} \rangle| \geq 3\sqrt{\frac{ d \nu \langle x ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} \right\} & \leq 2 \exp\left( -\frac{\frac{ 9 d \nu \log{(\mathsf{T}|{\cal X}|)}}{\langle x ,\theta^* \rangle \mathsf{T}'} \cdot \langle x ,\theta^* \rangle }{ 3 \frac{d\nu}{\mathsf{T}'} } \right) \\ & \leq \frac{2}{(\mathsf{T}|{ \cal X }|)^3} \end{align}\] Next, following a similar approach as in the proof of Lemma [lem:E9511], we use Lemma [lem:mult95concentration] with \(\delta = \frac{1}{3}\) and \(\delta = \frac{1}{2}\) to establish the upper and lower bounds of equation (19 ), respectively. Applying a union bound across arms in \(\widetilde{{ \cal X }}\) and over all—at most \(\log \mathsf{T}\)—phases, we obtain the desired probability bound of \(1 - \frac{3 \log{\mathsf{T}}}{\mathsf{T}}\). ◻

Corollary 2. \[\mathbb{P}\left\{ E_1 \cap E_2 \right\} \geq 1 - \frac{4 \log{\mathsf{T}}}{\mathsf{T}}.\]

Proof. From Lemma [lem:E9511] we have \(\mathbb{P}\left\{ E_1 \right\} \geq 1 - \frac{6}{\mathsf{T}}\). Furthermore, from Lemma 8 we have \(\mathbb{P}\left\{ E_2 \right\} \geq 1 - \frac{3 \log{\mathsf{T}}}{\mathsf{T}}\). Applying a union bound on the complements of these two events establishes the corollary. ◻

Lemma 9. Consider any bandit instance with \(\langle x^* ,\theta^* \rangle \geq 192 \sqrt{\frac{d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}}}\). If event \(E_1\) holds, then any arm with mean \(\langle x ,\theta^* \rangle\leq 10\sqrt{ \frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}}\) is eliminated after Part I of Algorithm 2.

Proof. We will show that in the given bandit instance and under the event \(E_1\), for each arm \(x \in \cal{X}\) with mean \(\langle x ,\theta^* \rangle\leq 10\sqrt{ \frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}}\) the upper Nash confidence bound (see equation (5 )) is less than the lower confidence bound of the optimal arm \(x^*\). Hence, all such arms \(x\) are eliminated from consideration in Line [line:eliminate1] of Algorithm 2. This will establish the lemma.

The upper Nash confidence bound of arm \(x\) at the end of Part I is defined as \[\begin{align} \mathrm{UNCB}\left(x,\widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) & = \langle x ,\widehat{\theta} \rangle + 6 \sqrt{\frac{ 3 \langle x ,\widehat{\theta} \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}} \nonumber \\ & \leq 20\sqrt{ \frac{d \;\nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} + 6 \sqrt{\frac{ 3\langle x ,\widehat{\theta} \rangle \;d \;\nu \log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}}\nonumber \\ & \leq 20\sqrt{ \frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} + 6 \sqrt{ \frac{3 \cdot 20 \sqrt{ \frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} d \nu \log{(\mathsf{T}|{ \cal X }|)}}{3\sqrt{\mathsf{T}\nu d \log (\mathsf{T}|\cal{X}|)}}} \nonumber }} \\ & \leq 47\sqrt{ \frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} \label{ineq:small95mean95arm} \end{align}\tag{24}\] In the given bandit instance and under event \(E_1\), for the optimal arm \(x^*\), we have \[\begin{align} \langle x^* ,\widehat{\theta} \rangle & \leq \langle x^* ,\theta^* \rangle + 3\sqrt{\frac{d \nu \langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\widetilde{\mathsf{T}}}} \nonumber \\ & = \langle x^* ,\theta^* \rangle \left( 1+ 3\sqrt{\frac{d \nu \log{(\mathsf{T}|{ \cal X }|)}}{\langle x^* ,\theta^* \rangle 3\sqrt{\mathsf{T}d \;\nu \log (\mathsf{T}|\cal{X}|)}}}\right) \nonumber }} \\ & \leq \langle x^* ,\theta^* \rangle \left( 1+ 3\sqrt{\frac{d \nu \log{(\mathsf{T}|{ \cal X }|)}}{192 \sqrt{\frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} 3\sqrt{\mathsf{T}\nu d \log (\mathsf{T}|\cal{X}|)}}}\right) |{ \cal X }|)}}{\mathsf{T}}} } \nonumber \\ & = \frac{17}{16}\langle x^* ,\theta^* \rangle. \label{ineq:opt95arm95mult95bound} \end{align}\tag{25}\] Therefore, the lower Nash confidence bound of \(x^*\) satisfies

\[\begin{align} \mathrm{LNCB}\left( x^*, \widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) & = \langle x^* ,\widehat{\theta} \rangle - 6 \sqrt{\frac{ 3 \langle x^* ,\widehat{\theta} \rangle \;d \;\nu \log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}} \nonumber \\ & \geq \langle x^* ,\theta^* \rangle - 3 \sqrt{\frac{d \;\nu \;\langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}} - 6 \sqrt{\frac{ 3 \langle x^* ,\widehat{\theta} \rangle \;d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\widetilde{\mathsf{T}}}} \nonumber ) in event E_1} \\ & \geq \langle x^* ,\theta^* \rangle - \left(3+ 6\sqrt{\frac{51}{16}}\right) \sqrt{\frac{d \;\nu \;\langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{ \cal X }|)} }{\widetilde{\mathsf{T}}}}\rangle \leq \frac{17}{16} \langle x^* ,\theta^* \rangle via (\ref{ineq:opt95arm95mult95bound})} \nonumber \\ & \geq \langle x^* ,\theta^* \rangle \left(1 - 14\sqrt{\frac{d \nu \;\log{(\mathsf{T}|{\cal X}|)} }{\langle x^* ,\theta^* \rangle \widetilde{\mathsf{T}}}} \right) \nonumber \\ & \geq \langle x^* ,\theta^* \rangle \left(1 - 14\sqrt{\frac{d \nu \;\log{(\mathsf{T}|{\cal X}|)} }{192 \sqrt{\frac{d \nu \;\log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} 3\sqrt{\mathsf{T}d \nu \log (\mathsf{T}|\cal{X}|)} }} \right) \nonumber \\ & \geq \frac{5}{12} \langle x^* ,\theta^* \rangle \nonumber \\ & \geq 80 \sqrt{\frac{d \nu \log(\mathsf{T}|{ \cal X }|)}{\mathsf{T}}} \label{ineq:opt95arm} \end{align}\tag{26}\] Equations (26 ) and (24 ) imply \[\mathrm{UNCB}\left(x,\widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) < \mathrm{LNCB}\left( x^*, \widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) \label{ineq:low95arm95vs95opt}\tag{27}\] As mentioned previously, Line [line:eliminate1] in Algorithm 2 eliminates all arms \(x\) that satisfy inequality (27 ). Hence, the lemma stands proved ◻

9.2 Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

Proof. We will show that, under events \(E_1\) and \(E_2\), throughout the execution of Algorithm 2 the \(\mathrm{UNCB}\) of the optimal arm \(x^*\) is never less than the \(\mathrm{LNCB}\) of any arm \(x\). Hence, then the optimal arm \(x^*\) never satisfies the elimination criterion in Algorithm 2 and, hence, \(x^*\) always exists in the surviving set of arms.

First, we consider arms \(x\) with the property that \(\langle x ,\theta^* \rangle < 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\). For any such arm \(x\), at the end of Part I of the algorithm we have \[\begin{align} \mathrm{LNCB}\left(x,\widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) \leq \mathrm{UNCB}\left(x,\widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) \underset{\text{via (\ref{ineq:low95arm95vs95opt})} }{<} \mathrm{LNCB}\left( x^*, \widehat{\theta}, \widetilde{\mathsf{T}}/3 \right) \leq \mathrm{UNCB}\left( x^*, \widehat{\theta}, \widetilde{\mathsf{T}}/3 \right). \end{align}\]

Hence, at the end of Part I, arm \(x^*\) is not eliminated via the \(\mathrm{LNCB}\) of any \(x\) which satisfies \(\langle x ,\theta^* \rangle < 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\). Further, note that, under event \(E_1\), such arms are eliminated at the end of Part I (Lemma 9). Hence, the \(\mathrm{LNCB}\) of such arms are not even considered in the phases of Part II.

To complete the proof, we next show that the \(\mathrm{UNCB}\) of the optimal arm \(x^*\) is at least the \(\mathrm{LNCB}\) of all arms \(x\) which bear \(\langle x ,\theta^* \rangle \geq 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\). Below, we will consider the Nash confidence bounds for a general \(\mathsf{T}'\). Replacing \(\mathsf{T}'\) by \(\widetilde{\mathsf{T}}\) gives us the desired confidence-bounds comparison for the end of Part I – this repetition is omitted.

Under events \(E_1\) and \(E_2\), for any arm \(x\) with \(\langle x ,\theta^* \rangle \geq 10\sqrt{\frac{d \nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}}}\), it holds that \[\begin{align} \mathrm{LNCB}(x, \widehat{\theta}, \mathsf{T}') & = \langle x ,\widehat{\theta} \rangle - 6 \sqrt{\frac{ \;\langle x ,\widehat{\theta} \rangle \;d \;\nu \;\log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} \nonumber \\ & \leq \langle x ,\theta^* \rangle + 3 \sqrt{\frac{ d \;\nu \;\langle x ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} - 6 \sqrt{\frac{ \;\langle x ,\widehat{\theta} \rangle \;d \nu \;\log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} )} \\ & \leq \langle x ,\theta^* \rangle - \left(\frac{6}{\sqrt{2} }-3 \right) \sqrt{\frac{ d \nu \langle x ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}}\rangle \geq \frac{1}{2} \langle x ,\theta^* \rangle via (\ref{ineq:phase95295mult95bound})} \nonumber \\ & \leq \langle x ,\theta^* \rangle \label{ineq:wm1}. \end{align}\tag{28}\] Complementarily, for optimal arm \(x^*\) we have \[\begin{align} \mathrm{UNCB}(x^*, \widehat{\theta}, \mathsf{T}') & = \langle x^* ,\widehat{\theta} \rangle + 6 \sqrt{\frac{ \;\langle x^* ,\widehat{\theta} \rangle \;d \;\nu \;\log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} \nonumber \\ & \geq \langle x^* ,\theta^* \rangle - 3 \sqrt{\frac{ d \nu \langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}}+ 6 \sqrt{\frac{ \;\langle x^* ,\widehat{\theta} \rangle \;d \;\nu \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}} \nonumber \\ & \geq \langle x^* ,\theta^* \rangle + \left(\frac{6}{\sqrt{2}} -3 \right) \sqrt{\frac{ d \nu \;\langle x^* ,\theta^* \rangle \log{(\mathsf{T}|{\cal X}|)}}{\mathsf{T}'}}\rangle \geq \frac{\langle x^* ,\theta^* \rangle}{2} } \nonumber \\ & \geq \langle x^* ,\theta^* \rangle \label{ineq:wm2} \end{align}\tag{29}\] Since \(\langle x^* ,\theta^* \rangle \geq \langle x ,\theta^* \rangle\) for all arms \(x\), inequalities (28 ) and (29 ) lead to the confidence-bounds comparison: \[\begin{align} \mathrm{UNCB}(x^*, \widehat{\theta}, \mathsf{T}') \geq \mathrm{LNCB}(x, \widehat{\theta}, \mathsf{T}'). \end{align}\] Hence, if events \(E_1\) and \(E_2\) hold, then the optimal arm \(x^*\) is never eliminated from Algorithm 2. Further, Corollary 2 ensures that the events \(E_1\) and \(E_2\) hold with probability at least \(1-\frac{4 \log{\mathsf{T}}}{\mathsf{T}}\). Hence, the lemma stands proved. ◻

Proof. For the analysis, assume that events \(E_1\) and \(E_2\) hold. Lemma [lem:best95arm] ensures that the optimal arm is contained in the surviving set of arms \(\widetilde{{ \cal X }}\). Furthermore, if an arm \(x \in \widetilde{{ \cal X }}\) at the beginning of the \(\ell^{\text{th}}\) phase, then it must be the case that arm \(x\) was not eliminated in the previous phase (which executed for \({\mathsf{T}'}/{2}\) rounds); in particular, we have \(\mathrm{UNCB}(x, \widehat{\theta}, \mathsf{T}'/2) \geq \mathrm{LNCB}(x^*, \widehat{\theta}, \mathsf{T}'/2)\). This inequality reduces to \[\begin{align} \langle x ,\widehat{\theta} \rangle + 6\sqrt{\frac{ \;\langle x ,\widehat{\theta} \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\frac{\mathsf{T}'}{2}}} \geq \langle x^* ,\widehat{\theta} \rangle - 6\sqrt{\frac{ \;\langle x^* ,\widehat{\theta} \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\frac{\mathsf{T}'}{2}}}. \end{align}\] Rearranging the terms, we obtain \[\begin{align} \langle x ,\widehat{\theta} \rangle & \geq \langle x^* ,\widehat{\theta} \rangle - 6\sqrt{\frac{ \;\langle x^* ,\widehat{\theta} \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\frac{\mathsf{T}'}{2}}} - 6\sqrt{\frac{ \;\langle x ,\widehat{\theta} \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\frac{\mathsf{T}'}{2}}} \\ & \geq \langle x^* ,\widehat{\theta} \rangle - 6\sqrt{\frac{\;4 \langle x^* ,\theta^* \rangle \;d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{ 3\mathsf{T}'/2} }- 6\sqrt{\frac{ \;4\langle x ,\theta^* \rangle \;d \;\nu \log{(\mathsf{T}|{ \cal X }|)}}{3\mathsf{T}'/2}}\rangle \leq \frac{4}{3} \langle x ,\theta^* \rangle via (\ref{ineq:phase95295mult95bound}) } \\ & \geq \langle x^* ,\widehat{\theta} \rangle -20 \sqrt{\frac{\;\langle x^* ,\theta^* \rangle \;d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}'} }. \end{align}\] Further, invoking equation (18 ) for \(x^*\) leads to \[\begin{align} \langle x ,\theta^* \rangle & \geq \langle x^* ,\theta^* \rangle -20 \sqrt{\frac{\;\langle x^* ,\theta^* \rangle \;d \;\nu \; \log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}'} } - 3 \sqrt{\frac{\;\langle x^* ,\theta^* \rangle \;d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\frac{\mathsf{T}'}{2} }} \\ & \geq \langle x^* ,\theta^* \rangle -25 \sqrt{\frac{\;\langle x^* ,\theta^* \rangle \;d \;\nu \;\log{(\mathsf{T}|{ \cal X }|)}}{\mathsf{T}'} }. \end{align}\] Substituting \(\mathsf{T}'= 2^\ell \widetilde{\mathsf{T}}/3\), the above inequality reduces to the desired bound in (8 ). From Corollary 2, we have that the events \(E_1\) and \(E_2\) hold with probability at least \(1-\frac{4 \log{\mathsf{T}}}{\mathsf{T}}\). Hence, the lemma stands proved. ◻

10 Regret Analysis of Algorithm 3 ↩︎

Instead of ensuring probability bounds on individual arms, we construct a confidence ellipsoid around \(\theta^*\). In the context of Algorithm 3, we define the following events for the regret analysis:

In Part I, arms from the D-optimal design are chosen at least \(\widetilde{\mathsf{T}}/3\) times. If \(\langle x^* ,\theta^* \rangle \geq 196\sqrt{\frac{ d^{2.5} \nu}{\mathsf{T}}}\log{\mathsf{T}}\), then \(\widehat{\theta}\) calculated at the end of Part I satisfies \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} \leq 7 \sqrt{ \langle x^* ,\theta^* \rangle d^\frac{3}{2} \nu \log{\mathsf{T}}}. \end{align}\]
In Part II, for every phase, if \(\langle x^* ,\theta^* \rangle \geq 196\sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\), the estimators \(\widehat{\theta}\) satisfy: \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} \leq 7 \sqrt{ \langle x^* ,\theta^* \rangle d^\frac{3}{2} \nu \log{\mathsf{T}}}. \end{align}\]

Without loss of generality, we assume throughout that \(\langle x^* ,\theta^* \rangle \geq 196\frac{d^{1.25} \sqrt{\nu}}{\sqrt{\mathsf{T}}} \log{\mathsf{T}}\). Otherwise, the regret bound in Theorem [thm:second] trivially holds. Let \({ \cal B }\) denote the unit ball in \(\mathbb{R}^d\). We have \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} &= \left\lVert \mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \right\rVert_{2} \\ &= \max_{y \in { \cal B }} \;\langle y ,\mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \rangle. \end{align}\] We construct an \(\varepsilon\)-net for the unit ball, denoted as \({ \cal C }_\varepsilon\). For any \(y \in { \cal B }\), we define \(y_\varepsilon \mathrel{\vcenter{:}}= \mathop{\mathrm{arg\,min}}_{b \in { \cal C }_\varepsilon} \left\lVert b - y \right\rVert_{2}\). We can now write \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} &= \max_{y \in { \cal B }} \;\langle y - y_\varepsilon ,\mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \rangle + \langle y_\varepsilon ,\mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \rangle\\ & \leq \max_{y \in { \cal B }} \left\lVert y - y_\varepsilon \right\rVert_{2}\left\lVert \mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \right\rVert_{2} + |\langle y_\varepsilon ,\mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \rangle|\\ & \leq \varepsilon \left\lVert (\widehat{\theta}- \theta^*) \right\rVert_{\mathbf{V}} + |\langle y_\varepsilon ,\mathbf{V}^{\frac{1}{2}}(\widehat{\theta}- \theta^*) \rangle|. \end{align}\] Rearranging, we obtain \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} \leq \frac{1}{1-\varepsilon} |\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\widehat{\theta}- \theta^* \rangle|.\label{ineq:base95bound} \end{align}\tag{30}\] In the following lemmas, we show that \(|\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\widehat{\theta}- \theta^* \rangle|\) is small for all values of \(y_\varepsilon\).

Lemma 10. Let \(x_1,x_2,\dots,x_n\) be a sequence of fixed arm pulls (from a set \({ \cal X }\)) such that each arm \(x\) in the support \(\lambda\) from D-optimal design (for \({ \cal X }\)) is pulled at least \(\lceil \lambda_x \tau \rceil\) times. Consider the matrix \(\mathbf{V}= \sum_{j=1}^n x_jx_j^{\mathsf{T}}\) and let \(z\) be a vector such that \(\left\lVert z \right\rVert_{2} \leq 1\) and \(\langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle \geq 6 \nu \sqrt{\frac{d}{\tau }} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\). Then, with probability greater than \(1 - \frac{2}{\mathsf{T}|{ \cal C }_\varepsilon|}\), we have, \[|\langle z \mathbf{V}^{\frac{1}{2}} , \theta^*- \widehat{\theta} \rangle| \leq \left(3 \nu \sqrt{\frac{nd}{\tau }} \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}{\langle x^* ,\theta^* \rangle} \right)^\frac{1}{2}\]

Proof. We begin by utilizing Lemma [lem:mult95concentration]. First, we determine the \(\gamma\) parameter in the lemma as follows, for any \(t \in [n]\) we have \[\begin{align} \left(z \mathbf{V}^\frac{1}{2}\right)^T \mathbf{V}^{-1} x_t & \leq \left\lVert z \mathbf{V}^\frac{1}{2} \right\rVert_{\mathbf{V}^{-1}} \left\lVert \mathbf{V}^{-1} x_t \right\rVert_{\mathbf{V}} \\ &\leq \left\lVert z \right\rVert_{2} \left\lVert x_t \right\rVert_{\mathbf{V}^{-1}}\\ &\leq \left\lVert x_t \right\rVert_{\mathbf{V}^{-1}}.\leq 1} \end{align}\] Let \(A_\lambda\) be the optimal design matrix. Since \(\mathbf{V}\succ \tau A_\lambda\), we have \[\begin{align} \left\lVert x_t \right\rVert_{\mathbf{V}^{-1}} &\leq \left\lVert x_t \right\rVert_{ \frac{1}{\tau}A_\lambda^{-1}}\\ &\leq \sqrt{\frac{d}{\tau}}. } \end{align}\] Now, we use Corollary 1 with \(\gamma = \sqrt{\frac{d}{\tau}}\) and \(\delta = \left(3 \sqrt{\frac{d}{\tau}} \frac{ \nu \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}}{\langle z \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle} \right)^\frac{1}{2}\). Note that \(\delta \in [0,1]\) since \(\langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle \geq 6 \sqrt{\frac{d}{\tau}} \nu \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\). We obtain the following probability bound \[\begin{align} \mathbb{P}\left\{ |\langle z \mathbf{V}^\frac{1}{2} ,\theta^*- \widehat{\theta} \rangle| \geq \left(3 \nu\sqrt{\frac{d}{\tau}} \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}{\langle z \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle} \right)^\frac{1}{2} \right\} &\leq 2 \;\mathrm{exp}\left( - \frac{ 3 \sqrt{\frac{d}{\tau}} \frac{ \nu \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}}{\langle z \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle} \langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle }{3 \nu \sqrt{\frac{d}{\tau}} } \right) \nonumber \\ &\leq \frac{2}{\mathsf{T}|{ \cal C }_\varepsilon| }. \label{ineq:g95upper95mid} \end{align}\tag{31}\] Finally, we establish an upper bound on the term \(\langle z \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle\) as follows \[\begin{align} \langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle &\leq \left\lVert z \right\rVert_{2} \left\lVert \mathbf{V}^\frac{1}{2} \theta^* \right\rVert_{2} \\ & \leq \sqrt{\theta^{*T} \mathbf{V}\theta^*}\leq 1}\\ & = \sqrt{\left( \sum_{i\in [n]} \theta^{*T} x_i x_i^T \theta^*\right)}\\ &= \sqrt{ n } \langle x^* ,\theta^* \rangle. \end{align}\] Substituting in (31 ) we get the lemma statement. This completes the proof of the lemma. ◻

Lemma 11. Consider the same notation as in Lemma 10. If \(\langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle \in \left[0 , 6 \nu \sqrt{\frac{d}{\tau }} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)} \right]\), then with probability greater than \(1- \frac{2}{\mathsf{T}|{ \cal X }|}\) we have \[|\langle z \mathbf{V}^{\frac{1}{2}} , \theta^*- \widehat{\theta} \rangle| \leq 12 \nu \sqrt{\frac{d}{\tau}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}.\]

Proof. Utilizing Lemma 3, with \(\delta = 1\), \(\alpha = 6 \nu \sqrt{\frac{d}{\tau}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\), and \(\gamma = \sqrt{\frac{d}{\tau}}\), we have \(\langle z \mathbf{V}^\frac{1}{2} ,\widehat{\theta} \rangle \leq 12 \nu\sqrt{\frac{d}{\tau}} \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\). Since \(\langle z \mathbf{V}^\frac{1}{2} ,\theta^* \rangle \geq 0\), it follows, with probability greater than \(1 - \frac{1}{\mathsf{T}|{ \cal X }|}\), that \[\langle z \mathbf{V}^{\frac{1}{2}} , \widehat{\theta}- \theta^* \rangle \leq 12 \nu \sqrt{\frac{d}{\tau}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}.\]

Next, applying Lemma 4 with \(\delta = 1\) and \(\alpha = 6 \nu \sqrt{\frac{d}{\tau}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\), we have, with probability greater than \(1 - \frac{1}{\mathsf{T}|{ \cal X }|}\), \[\langle z \mathbf{V}^\frac{1}{2} ,\theta^*- \widehat{\theta} \rangle \leq 6 \nu \sqrt{\frac{d}{\tau}}\log{(\mathsf{T}|{ \cal C }_\varepsilon|)} \leq 12 \nu \sqrt{\frac{d}{\tau}}\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}.\]

Hence, the lemma stands proved. ◻

Lemma 12. If \(\langle x^* ,\theta^* \rangle \geq 196\sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\), then \[\begin{align} \mathbb{P}\left\{ G_1 \right\} &\geq 1- \frac{ 3 }{\mathsf{T}} \label{ineq:G95195bound} \quad \end{align}\qquad{(1)}\]

Proof. First, we note (from Lemma 6) that arms from the solution of the D-optimal design problem are selected (with probability greater than \(1 - \frac{1}{\mathsf{T}}\)) at least \(\widetilde{\mathsf{T}}/3\) times. Hence, we can use Lemmas 10 and 11 with \(\tau = \widetilde{\mathsf{T}}/3\).

Let us consider the case where \(\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle \geq 6 \sqrt{\frac{3d}{\widetilde{\mathsf{T}}}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)}\). We have that the following holds with probability greater than \(1 - \frac{1}{\mathsf{T}|{ \cal C }_\varepsilon| }\): \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} &\leq \frac{1}{1-\varepsilon}\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\widehat{\theta}- \theta^* \rangle )}\\ &\leq \frac{1}{1-\varepsilon} \left(3 \nu \sqrt{\frac{\widetilde{\mathsf{T}}d}{\frac{\widetilde{\mathsf{T}}}{3}}} \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}{\langle x^* ,\theta^* \rangle} \right)^\frac{1}{2} }\\ & \leq \frac{1}{1-\varepsilon} \left(3 \sqrt{3d} \; \nu \log{(\mathsf{T}|{ \cal C }_\varepsilon|)}{\langle x^* ,\theta^* \rangle} \right)^\frac{1}{2}. \end{align}\] Next, we note that \(|{ \cal C }_\varepsilon| \leq \left( \frac{3}{\varepsilon}\right)^d\) [12], and by choosing \(\varepsilon = 1/2\) we get \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} \leq 7 \left( \nu d^{\frac{3}{2}}\log{(\mathsf{T})}{\langle x^* ,\theta^* \rangle} \right)^\frac{1}{2} \end{align}\] Taking a union bound over all elements in \({ \cal C }_\varepsilon\) gives a probability bound of \(1 - \frac{1}{\mathsf{T}}\).

Now, for the case where \(\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\theta^* \rangle \in \left[0, 6 \sqrt{\frac{3d}{\widetilde{\mathsf{T}}}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)} \right]\), substituting \(\tau = \widetilde{\mathsf{T}}/3\) in Lemma 11 we have, with probability greater than \(1 - \frac{1}{\mathsf{T}|{ \cal C }_\varepsilon| }\), \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} &\leq \frac{1}{1-\varepsilon}\langle y_\varepsilon \mathbf{V}^{\frac{1}{2}} ,\widehat{\theta}- \theta^* \rangle \\ & \leq \frac{12 \nu }{1-\varepsilon} \sqrt{\frac{d }{\tau}} \;\log{(\mathsf{T}|{ \cal C }_\varepsilon|)} }\\ &\leq 24 \nu \sqrt{\frac{3d^3}{\widetilde{\mathsf{T}}}} \;\log{(\mathsf{T})}\\ &\leq 7 \left( d^{\frac{3}{2}} \nu \log{(\mathsf{T})}{\langle x^* ,\theta^* \rangle} \right)^\frac{1}{2} \end{align}\] The last inequality is due to the fact that \(\langle x^* ,\theta^* \rangle \geq 196 \sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\) and \(\widetilde{\mathsf{T}}= 3 \sqrt{\mathsf{T}\nu d^{2.5} \log{\mathsf{T}}}\). We again take a union bound over all elements in \({ \cal C }_\varepsilon\) to get a probability bound of \(1 - \frac{1}{\mathsf{T}}\).

Finally, a union bound over the two cases and the event in Lemma 6 proves the lemma. ◻

Lemma 13. If \(\langle x^* ,\theta^* \rangle \geq 196\sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\), then \[\begin{align} \mathbb{P}\left\{ G_2 \right\} &\geq 1- \frac{ \log{\mathsf{T}} }{\mathsf{T}}. \label{ineq:G95295bound} \end{align}\qquad{(2)}\]

Proof. To prove Lemma 13, we follow the same steps as in the proof of Lemma 12. Utilizing Lemma 10 and Lemma 11 with \(\tau = \mathsf{T}'\), we establish that for any fixed phase, the following inequality holds with probability greater than \(1 - \frac{1}{\mathsf{T}}\): \[\begin{align} \left\lVert \widehat{\theta}- \theta^* \right\rVert_{\mathbf{V}} \leq 7 \left( d^{\frac{3}{2}} \nu \log{\mathsf{T}}\langle x^* ,\theta^* \rangle \right)^\frac{1}{2}. \end{align}\] Taking a union bound over all – at most \(\log{\mathsf{T}}\) – phases in Part II of Algorithm 3 gives us the desired lower bound on \(\mathbb{P}\left\{G_2 \right\}\). ◻

Corollary 3. If \(G_1\) holds, then for all \(x \in { \cal X }\), \(\widehat{\theta}\) calculated at the end of Part I satisfies \[\begin{align} |\langle x ,\widehat{\theta} \rangle - \langle x ,\theta^* \rangle| \leq 7\sqrt{\frac{ 3 \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\widetilde{\mathsf{T}}}} \end{align}\] Consider any phase \(\ell\) in Part II. If \(G_2\) holds, then for every arm in the surviving arm set \(\widetilde{{ \cal X }}\;\), \(\;\widehat{\theta}\) calculated at the end of the phase satisfies \[\begin{align} |\langle x ,\widehat{\theta} \rangle - \langle x ,\theta^* \rangle| \leq 7\sqrt{ \frac{ 3 \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{2^{\ell} \; \widetilde{\mathsf{T}}}}. \end{align}\]

Proof. First we use Hölder’s inequality \[\begin{align} |\langle x ,\theta^*-\widehat{\theta} \rangle| &\leq \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \left\lVert \theta^*- \widehat{\theta} \right\rVert_{\mathbf{V}} \label{ineq:base}. \end{align}\tag{32}\] Since \(G_1\) holds, arms from the optimal design matrix are selected at least \(\widetilde{\mathsf{T}}/3\) times; we have by Lemma 1 \[\begin{align} \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \leq \sqrt{\frac{3d}{\widetilde{\mathsf{T}}}}. \end{align}\] Similarly, for every phase in Part II with \(\mathsf{T}'= 2^\ell \widetilde{\mathsf{T}}/3\) we have \[\begin{align} \left\lVert x \right\rVert_{\mathbf{V}^{-1}} \leq \sqrt{\frac{d}{\mathsf{T}'}}. \end{align}\] Finally, using bounds on \(\left\lVert \theta^*- \widehat{\theta} \right\rVert_{\mathbf{V}}\) from events \(G_1\) and \(G_2\), and substituting in (32 ), we get the desired bound. ◻

Corollary 4. If \(\langle x^* ,\theta^* \rangle \geq 196 \sqrt{\frac{d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\) \[\frac{7}{10}\langle x^* ,\theta^* \rangle\leq \max_{x \in { \cal X }} \langle x ,\widehat{\theta} \rangle \leq \frac{13}{10} \;\langle x^* ,\theta^* \rangle\]

Proof. Since \(\mathsf{T}'\geq 2\widetilde{\mathsf{T}}/3\), via Corollary 3 any \(\widehat{\theta}\) calculated in Part I or during any phase of Part II satisfies \[\begin{align} |\langle x ,\widehat{\theta} \rangle - \langle x ,\theta^* \rangle| \leq 7\sqrt{\frac{ 3 \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\widetilde{\mathsf{T}}}} \end{align}\] We have \[\begin{align} \max_{x \in { \cal X }} \langle x ,\widehat{\theta} \rangle &\geq \langle x^* ,\widehat{\theta} \rangle \\ &\geq \langle x^* ,\theta^* \rangle - 7\sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\widetilde{\mathsf{T}}}} \\ &\geq \langle x^* ,\theta^* \rangle \left(1- 7\sqrt{\frac{ d^{2.5} \nu \log{\mathsf{T}}}{\langle x^* ,\theta^* \rangle \widetilde{\mathsf{T}}}} \right) \\ &\geq \frac{7}{10} \langle x^* ,\theta^* \rangle \nu }{\mathsf{T}}}\log{\mathsf{T}} and \widetilde{\mathsf{T}}= 3\sqrt{\mathsf{T}d^{2.5} \nu \log (\mathsf{T})} } \end{align}\] Now, for any \(x \in { \cal X }\), \[\begin{align} \langle x ,\widehat{\theta} \rangle &\leq \langle x ,\theta^* \rangle + 7\sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\tau}}\\ &\leq \langle x^* ,\theta^* \rangle \left(1+ 7\sqrt{\frac{ d^{2.5} \nu \log{\mathsf{T}}}{\langle x^* ,\theta^* \rangle \tau}} \right) \\ &\leq \frac{13}{10}\langle x^* ,\theta^* \rangle \end{align}\] Hence, the lemma stands proved. ◻

Lemma 14. If events \(G_1\) and \(G_2\) hold then the optimal arm \(x^*\) always exists in the surviving set \(\widetilde{X}\) in every phase in Part II of Algorithm 3

Proof. Let \(\tau = \widetilde{\mathsf{T}}/3\) for Part I and \(\tau = \mathsf{T}'\) for every phase of Part II. From Corollary 3 we have \[\begin{align} \langle x^* ,\widehat{\theta} \rangle &\geq \langle x^* ,\theta^* \rangle - 7 \sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\tau}} \\ &\geq \langle x ,\theta^* \rangle - 7 \sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\tau}} \\ &\geq \langle x ,\widehat{\theta} \rangle - 14 \sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\tau}} }\\ &\geq \langle x ,\widehat{\theta} \rangle - 16 \sqrt{\frac{ \max_{x \in \widetilde{{ \cal X }}} \langle x ,\theta^* \rangle d^{2.5} \nu \log{\mathsf{T}}}{\tau}}. } \end{align}\] Hence, the best arm will never satisfy the elimination criteria in Algorithm 3. ◻

Lemma 15. Given that events \(G_1\) and \(G_2\) hold, consider any phase index \(\ell\) in Part II of Alg. 3. For the surviving set of arms \(\widetilde{{ \cal X }}\) at the beginning of that phase, and for \(\widetilde{\mathsf{T}}=\sqrt{d^{2.5} \nu \mathsf{T}\log(\mathsf{T})}\), the following inequality holds for all \(x\in \widetilde{\mathcal{X}}\) \[\langle x ,\theta^* \rangle \geq \langle x^* ,\theta^* \rangle - 26 \sqrt{\frac{ 3d^{2.5} \nu \langle x^* ,\theta^* \rangle }{2^{\ell}\cdot \widetilde{\mathsf{T}}}}.\]

Proof. Lemma 14 ensures that the optimal arm is contained in the surviving set of arms \(\widetilde{{ \cal X }}\). Furthermore, if an arm \(x \in \widetilde{{ \cal X }}\) is pulled in the \(\ell^{\text{th}}\) phase, then it must be the case that arm \(x\) was not eliminated in the previous phase (with a phase length parameter \(\frac{\mathsf{T}'}{2}\)); in particular the arms \(x\) does not satisfy the inequality on Line [line:elimination95criterial95infinite] of Algorithm 3. This inequality reduces to \[\begin{align} \langle x ,\widehat{\theta} \rangle &\geq \langle x^* ,\widehat{\theta} \rangle - 16 \sqrt{\frac{ \; \max_{x \in {\widetilde{{ \cal X }}}}\langle x ,\widehat{\theta} \rangle \;d^{2.5} \;\nu \; \log{(\mathsf{T})}}{\frac{\mathsf{T}'}{2}}}\\ &\geq \langle x^* ,\widehat{\theta} \rangle - 26 \sqrt{\frac{ \; \langle x^* ,\theta^* \rangle \;d^{2.5} \;\nu \; \log{(\mathsf{T})}}{\mathsf{T}'}}\\ } \end{align}\] Substituting \(\mathsf{T}'= 2^l\widetilde{\mathsf{T}}/3\) in the above inequality proves the Lemma. ◻

Proof. Without loss of generality, we assume that \(\langle x^* ,\theta^* \rangle \geq 196 \sqrt{\frac{d^{2.5} \nu}{\mathsf{T}}}\log{\mathsf{T}}\). Otherwise, the Nash Regret bound is trivially true. For Part I, the product of expected rewards satisfies \[\begin{align} \prod_{t = 1}^{\widetilde{\mathsf{T}}} \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid G_1 \cap G_2 ]^\frac{1}{\mathsf{T}} &\geq \left(\frac{\langle x^* ,\theta^* \rangle}{2(d+1)}\right)^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} }\\ &=\langle x^* ,\theta^* \rangle^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} \left(1-\frac{1}{2}\right)^{\frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}}} \\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\widetilde{\mathsf{T}}}{\mathsf{T}}} \left(1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} \right). \\ \end{align}\]

For Part II, we use Lemma [lem:phase95II95reward95bound]. Let \({ \cal E }_i\) denote the time interval of the \(i^{th}\) phase, and let \(\mathsf{T}'_i\) be the phase length parameter in that phase. Recall that \(|{ \cal E }_i| \leq \mathsf{T}'_i + \frac{d(d+1)}{2}\). Also, the algorithm runs for at most \(\log{\mathsf{T}}\) phases. Hence, we have

\[\begin{align} \prod_{t = \widetilde{\mathsf{T}}+1 }^{\mathsf{T}} \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid G_1 \cap G_2 ]^\frac{1}{\mathsf{T}} &= \prod_{{ \cal E }_j} \prod_{t \in { \cal E }_j } \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid G_1 \cap G_2 ]^\frac{1}{\mathsf{T}} \\ &\geq \prod_{{ \cal E }_j} \left(\langle x^* ,\theta^* \rangle - 26 \sqrt{\frac{ d^{2.5} \;\nu \;\langle x^* ,\theta^* \rangle \log{(\mathsf{T})}}{\mathsf{T}'_j}} \right)^{\frac{|{ \cal E }_j|}{\mathsf{T}}} \\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\mathsf{T}-\widetilde{\mathsf{T}}}{\mathsf{T}}} \prod_{i=1}^{\log{\mathsf{T}}} \left( 1 - 26 \sqrt{\frac{ d^{2.5} \;\nu \;\log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_j}} \right)^{\frac{|{ \cal E }_j|}{\mathsf{T}}}\\ &\geq \langle x^* ,\theta^* \rangle^{\frac{\mathsf{T}-\widetilde{\mathsf{T}}}{\mathsf{T}}} \prod_{i=1}^{\log{\mathsf{T}}} \left( 1 - 52 \frac{|{ \cal E }_j|}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \; \nu \;\log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_j}} \right) \; \end{align}\]

The last inequality is due to the fact that \((1-x)^r \geq (1 - 2rx)\) where \(r \in [0,1]\) and \(x \in [0,1/2]\). Note that the term \(\sqrt{\frac{d^{2.5} \nu \log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_j}} \leq 1/2\) for \(\langle x^* ,\theta^* \rangle \geq 196 \sqrt{\frac{d^{2.5} \nu }{\mathsf{T}}}\log{\mathsf{T}}\), \(\mathsf{T}'\geq 2 \sqrt{\mathsf{T}d^{2.5} \nu \log{\mathsf{T}}}\), and \(\mathsf{T}\geq e^6\). We can further simplify the expression as follows \[\begin{align} \prod_{j=1}^{\log{\mathsf{T}}} \left( 1 - 52 \frac{|{ \cal E }_j|}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \;\nu \;\log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_j}} \right) &\geq \prod_{j=1}^{\log{\mathsf{T}}} \left( 1 - 52 \frac{\mathsf{T}'_j + \frac{d(d+1)}{2}}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \;\nu \; \log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle \mathsf{T}'_j}} \right) \\ &\geq \prod_{j=1}^{\log{\mathsf{T}}} \left( 1 - 78 \frac{\sqrt{\mathsf{T}'_j}}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \;\nu \log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle}} \right) '_j \geq d(d+1) }\\ &\geq 1 - 78 \frac{1}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \;\nu \log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle}} \left( \sum_{j=1}^{\log{\mathsf{T}}} \sqrt{\mathsf{T}'_j} \right) \\ &\geq 1 - 78 \frac{1}{\mathsf{T}} \sqrt{\frac{ d^{2.5} \;\nu \;\log{(\mathsf{T})}}{\langle x^* ,\theta^* \rangle}} \left( \sqrt{\mathsf{T}\log{\mathsf{T}}} \right)\\ & \geq 1 - 78 \sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T})}. \end{align}\] Combining the lower bound for rewards in Part I and Part II of the algorithm, we obtain

\[\begin{align} \prod_{t = 1}^{\mathsf{T}} \mathbb{E}[ \langle X_t ,\theta^* \rangle]^\frac{1}{\mathsf{T}} &\geq \prod_{t = 1}^{\mathsf{T}} \biggl( \mathbb{E}[ \langle X_t ,\theta^* \rangle \mid G_1 \cap G_2 ] \cdot \mathbb{P}\{ G_1 \cap G_2 \}\biggr) ^\frac{1}{\mathsf{T}} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} \right) \left( 1 - 78 \sqrt{\frac{ d^{2.5} \nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T})} \right)\mathbb{P}\{ G_1 \cap G_2 \} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} - 78 \sqrt{\frac{ d^{2.5}\nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T})} \right)\mathbb{P}\{ G_1 \cap G_2 \} \\ &\geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) \widetilde{\mathsf{T}}}{\mathsf{T}} - 78 \sqrt{\frac{ d^{2.5}\nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T})} \right)\left(1 - \frac{2 \log{\mathsf{T}}}{\mathsf{T}} \right) \\ & \geq \langle x^* ,\theta^* \rangle \left( 1 - \frac{\log(2(d+1)) 3\sqrt{\mathsf{T}d \nu \log (\mathsf{T})} }{\mathsf{T}} - 78 \sqrt{\frac{ d^{2.5}\nu }{\mathsf{T}\langle x^* ,\theta^* \rangle}} \log{(\mathsf{T})} - \frac{2 \log{\mathsf{T}}}{\mathsf{T}} \right) \\ & \geq \langle x^* ,\theta^* \rangle - 78 \sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5}\nu }{\mathsf{T}}} \log{(\mathsf{T})} - 2 \frac{\langle x^* ,\theta^* \rangle \log(2(d+1)) 3\sqrt{ d \log (\mathsf{T})} }{\sqrt{\mathsf{T}}}. \end{align}\] Hence, the Nash Regret can be bounded as \[\begin{align} \mathrm{\small NR}_T &= \langle x^* ,\theta^* \rangle - \left( \prod_{t=1}^T \mathbb{E}[ \langle X_t ,\theta^* \rangle ] \right)^{1/T} \\ &\leq 78 \sqrt{\frac{ \langle x^* ,\theta^* \rangle d^{2.5}\nu }{\mathsf{T}}} \log{(\mathsf{T})} + 2 \frac{ \langle x^* ,\theta^* \rangle\log(2(d+1)) 3\sqrt{ d \nu \log (\mathsf{T})} }{\sqrt{\mathsf{T}}}. \end{align}\] The theorem stands proved. ◻

References↩︎

[1]

Yogatheesan Varatharajah and Brent Berry. A contextual-bandit-based approach for informed decision-making in clinical trials. Life, 12(8):1277, 2022.

[2]

Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495–517, 2017.

[3]

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.

[4]

Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500–522, 2017.

[5]

William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294, 1933.

[6]

Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77, 2002.

[7]

Hervé Moulin. Fair division and collective welfare. MIT press, 2004.

[8]

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.

[9]

Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.

[10]

Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010.

[11]

Siddharth Barman, Arindam Khan, Arnab Maiti, and Ayush Sawarni. Fairness and welfare quantification for regret in multi-armed bandits. arXiv preprint arXiv:2205.13930, 2022.

[12]

Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

[13]

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.

[14]

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.

[15]

Ralph Howard. The john ellipsoid theorem. University of South Carolina, 1997.

[16]

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.

[17]

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.

[18]

Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari. Achieving fairness in the stochastic multi-armed bandit problem. The Journal of Machine Learning Research, 22(1):7885–7915, 2021.

[19]

Ilai 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.

[20]

Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent multi-armed bandits. Advances in Neural Information Processing Systems, 34:24005–24017, 2021.

[21]

Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363–366, 1960.

[22]

Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012.

[23]

Jürgen Eckhoff. Helly, radon, and carathéodory type theorems. In Handbook of convex geometry, pages 389–448. Elsevier, 1993.

[24]

William Kuszmaul and Qi Qi. The multiplicative version of azuma’s inequality, with an application to contention analysis. arXiv preprint arXiv:2102.05077, 2021.

[25]

Michael J Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.

[26]

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.

[27]

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127–135. PMLR, 2013.

Indian Institute of Science. ayushsawarni@iisc.ac.in↩︎
Google Research, Bangalore. soumyabrata@google.com↩︎
Indian Institute of Science. barman@iisc.ac.in↩︎
This lower bound on average regret is obtained for instances in which the set of arms \(\mathcal{X}\) are the corners of a hypercube [12].↩︎
An intersection between sub-Gaussian and sub-Poisson distribution classes is identified in Lemma [lem:subGaussian].↩︎
Note that, for a randomized online algorithm, the selected arm \(X_t\) is a random variable.↩︎
Here, the expectation is with respect to the random variable \(X_t\).↩︎
Even though the two optimization problems (3 ) and (4 ) share the optimal solution, the optimal objective function values can be different.↩︎
The ellipsoid \(E\) considered in Lemma 2 is also the ellipsoid of maximal volume contained in \(K\) [22].↩︎
Here, the expectation is over randomness in algorithm and the reward noise.↩︎
Here, the expectation is over both the randomness in including arm \(X_t\) in \(\mathcal{S}\) and the noise in the reward.↩︎

Nash Regret Guarantees for Linear Bandits

Abstract

1 Introduction↩︎

1.1 Our Contributions and Techniques↩︎

2 Problem Formulation and Preliminaries↩︎

2.1 Sub-Poisson Rewards↩︎

2.2 Optimal Design.↩︎

2.3 John Ellipsoid.↩︎

3 Our Algorithm LinNash and Main Results↩︎

3.1 Part I: Sampling via John Ellipsoid and Kiefer-Wolfowitz Optimal Design↩︎

3.2 Part II: Phased Elimination via Estimate Dependent Confidence Widths↩︎

3.3 Main Result↩︎

3.3.0.1 Computational Efficiency of LinNash.

4 Extension of Algorithm LinNash for Infinite Arms↩︎

5 Experiments↩︎

6 Conclusion and Future Work↩︎

7 Proof of Lemmas [lem:bounded95sub95poisson] and [lem:subGaussian]↩︎

8 Proof of Concentration Bounds↩︎

9 Regret Analysis of Algorithm 2: Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

9.1 Supporting Lemmas↩︎

9.2 Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

10 Regret Analysis of Algorithm 3 ↩︎

References↩︎

Subjects

Updated on Academus

Nash Regret Guarantees for Linear Bandits

Abstract

1 Introduction↩︎

1.1 Our Contributions and Techniques↩︎

1.2 Other Related Work↩︎

2 Problem Formulation and Preliminaries↩︎

2.1 Sub-Poisson Rewards↩︎

2.2 Optimal Design.↩︎

2.3 John Ellipsoid.↩︎

3 Our Algorithm LinNash and Main Results↩︎

3.1 Part I: Sampling via John Ellipsoid and Kiefer-Wolfowitz Optimal Design↩︎

3.2 Part II: Phased Elimination via Estimate Dependent Confidence Widths↩︎

3.3 Main Result↩︎

3.3.0.1 Computational Efficiency of LinNash.

4 Extension of Algorithm LinNash for Infinite Arms↩︎

5 Experiments↩︎

6 Conclusion and Future Work↩︎

7 Proof of Lemmas [lem:bounded95sub95poisson] and [lem:subGaussian]↩︎

8 Proof of Concentration Bounds↩︎

9 Regret Analysis of Algorithm 2: Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

9.1 Supporting Lemmas↩︎

9.2 Proofs of Lemmas [lem:best95arm] and [lem:phase95II95reward95bound]↩︎

10 Regret Analysis of Algorithm 3↩︎

References↩︎

Subjects

Updated on Academus

10 Regret Analysis of Algorithm 3 ↩︎