Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners

Function optimization over structured domains is a basic sequential decision making problem. A well-known formulation of this problem is Probably Approximately Correct (PAC) best arm identification in multi-armed bandits [7], in which a learner is given a set of arms with unknown (and unrelated) means. The learner must sequentially test arms and output, as soon as possible with high confidence, a near-optimal arm (where optimality is defined in terms of the largest mean).

Often, the arms (decisions) and their associated rewards, possess structural relationships, allowing for more efficient learning of the rewards and transfer of learnt information, e.g., two ‘close enough’ arms may have similar mean rewards. One of the best-known examples of structured decision spaces is the linear bandit, whose arms are vectors (points) in $\mathbb{R}^{d}$. The reward or function value of an arm is an unknown linear function of its vector representation, and the goal is to find an arm with maximum reward in the shortest possible time by measuring arms’ rewards sequentially with noise. This framework models an array of structured online linear optimization problems including adaptive routing [2], smooth function optimization over graphs [20], subset selection [13] and, in the nonparametric setting, black box optimization in smooth function spaces [18], among others.

Although no-regret online learning for linear bandits is a well-understood problem (see [14] and references therein), the PAC-sample complexity of best arm identification in this model has not received significant attention until recently [17]. The state of the art here is the work of Fiez et al. [8], who give an algorithm with optimal (instance-dependent) PAC sample complexity. However, a closer look indicates that the algorithm assumes repeated oracle access to a minimax optimization problem¹¹1This is, in fact, a plug-in version of a minimax optimization problem representing an information-theoretic sample complexity lower bound for the problem.; it is not clear, from a performance standpoint, in what manner (and to what accuracy) this optimization problem should be practically solved²²2For its experiments, the paper implements a (approximate) minimax oracle using the Frank-Wolfe algorithm and a heuristic stopping rule, but this is not rigorously justifiable for nonsmooth optimization, see Sec. 4. to enjoy the claimed sample complexity. Hence, the question of how to design an explicit algorithm with optimal PAC sample complexity for best arm identification in linear bandits has remained open.

In this paper, we resolve this question affirmatively by giving an explicit linear bandit best-arm identification algorithm with instance-optimal PAC sample complexity and, more importantly, a clearly quantified computational effort. We achieve this goal using new techniques: the main ingredient in the proposed algorithm is a game-theoretic interpretation of the minimax optimization problem that is at the heart of the instance-based sample complexity lower bound. This in turn yields an adaptive, sample-based approach using carefully constructed confidence sets for the unknown parameter $\theta^{*}$. The adaptive sampling strategy is driven by the interaction of 2 no-regret online learning subroutines that attempt to solve the minimax problem approximately, obviating the worry of i) solving the optimal minimax allocation to a suitable precision and ii) making an integer sampling allocation from it by rounding, which occur in the approach of Fiez et al [8]. We note that the seeds of this game-theoretic approach were laid by the recent work of Degenne et al. [6] for the simple (i.e., unstructured) multiarmed bandit problem. However, our work demonstrates a novel extension of their methodology to solve best-arm learning in structured multi-armed bandits for the first time to the best of our knowledge.

We study the problem of best arm identification in linear bandits with the arm set $\mathcal{X}\equiv\{x_{1},x_{2},\ldots,x_{K}\}$, where each arm³³3In general, the number of arms can be much larger than the ambient dimension, i.e., $d\ll K.$ $x_{a}$ is a vector in $\mathbb{R}^{d}$. We will interchangeably use $\mathcal{X}$ and the set $[K]\equiv\{1,2,\ldots,K\}$, whenever the context is clear. In every round $t=1,2,\ldots$ the agent chooses an arm $x_{t}\in\mathcal{X}$, and receives a reward $y(x_{t})={\theta^{*}}^{T}x_{t}+\eta_{t}$, where $\theta^{*}$ is assumed to be a fixed but unknown vector, and $\eta_{t}$ is zero-mean noise assumed to be conditionally $1-$ subgaussian, i.e., $\forall\gamma\in\mathbb{R},\mathbb{E}\left[{e^{\gamma\eta_{t}}|x_{1},x_{2},\ldots,x_{{t-1}},\eta_{1},\eta_{2},\ldots,\eta_{t-1}}\right]\leqslant\exp\Big{(}\frac{\gamma^{2}}{2}\Big{)}$. We denote by $\nu^{k}_{\theta^{*}}$ the distribution of the reward obtained by pulling arm $k\in[K],$ i.e., $\forall t\geqslant 1,y(x_{t})\sim\nu^{k}_{\theta^{*}},$ whenever $x_{t}=x_{k}.$ Given two probability distributions $\mu,\nu$ over $\mathbb{R}$, $KL(\mu,\nu)$ denotes the KL Divergence of $\mu$ and $\nu$ (assuming $\mu\ll\nu$). Given $\theta\in\mathbb{R}^{d}$, let $a^{*}\equiv a^{*}(\theta)=\mathop{\mathrm{argmax}}\limits_{a\in[K]}{\theta}^{T}x_{a}$, where we assume that $\theta$ is such that the argmax is unique.

A learning algorithm for the best arm identification problem comprises the following rules: (1) a sampling rule, which determines based on the past play of arms and observations, which arm to pull next, (2) a stopping rule, which controls the end of sampling phase and is a function of the past observations and reward, and (3) a recommendation rule, which, when the algorithm stops, offers a guess for the best arm. The goal of a learning algorithm is: Given an error probability $\delta>0$, identify (guess) $a^{*}$ with probability $\geqslant 1-\delta$ by pulling as few (in an expected sense) arms as possible. Any algorithm that (1) stops with probability 1 and (2) returns $a^{*}$ upon stopping with probability at least $1-\delta$ is said to be $\delta$-Probably Approximately Correct ($\delta$-PAC). For clarity of exposition, we distinguish the above linear bandit setting from what we term the unstructured bandit setting, wherein $K=d,$ and $x_{i}=\widehat{e}_{i},~{}\forall k\in[K]$ the canonical basis vectors (the former setting generalizes the latter). The (expected) number of samples $\tau\in\mathbb{N}$ consumed by an algorithm in determining the optimal arm in any bandit setting (not necessarily the linear setting) is called its sample complexity.

In the rest of the paper, we will assume that $\left\lVert x_{k}\right\rVert_{2}\leqslant 1,\forall x_{k}\in\mathcal{X}$. Given a positive definite matrix $A$, we denote by $\left\lVert x\right\rVert_{A}:=\sqrt{x^{T}Ax}$, the matrix norm induced by $A$. For any $i\in[K],i\neq a^{*}$, we define $\Delta_{i}:={\theta^{*}}^{T}(x_{a^{*}}-x_{i})$ to be the gap between the largest expected reward and the expected reward of (suboptimal) arm $x_{i}$. Let $\Delta_{\min}:=\min\limits_{\begin{subarray}{c}i\in[K]\end{subarray}}\Delta_{i}$. We denote $B(z,r)$ as the closed ball with center $z$ and radius $r$. For any measurable space $\left(\Omega,\mathcal{F}\right),$ we define $\mathcal{P}(\Omega)$ to be the set of all probability measures on $\Omega$. $\tilde{\mathcal{O}}$ is big-Oh notation that suppresses logarithmic dependence on problem parameters. For the benefit of the reader, we provide a glossary of commonly used symbols in Sec. A in the Appendix.

Note: $C:=\lambda_{\min}\left(\sum_{x\in\mathcal{X}}xx^{T}\right)$ is a term depending only on the geometry of the arm set.

In this section we describe the main ingredients in our algorithm design and how they build upon ideas introduced in recent work [6, 8] (the explicit algorithm appears in Sec. 4).

The phased elimination approach: Fiez et al [8]. We first note that a lower bound on the sample complexity of any $\delta$- PAC algorithm for the canonical (i.e., unstructured) bandit setting [10] was generalized by Fiez et al [8] to the linear bandit setting, assuming $\{\eta_{t}\}_{t\geqslant 1}$ to be standard normal random variables. This result states that any $\delta$-PAC algorithm in the linear setting must satisfy $\mathbb{E}_{\theta^{*}}[\tau]\geqslant\left(\log{1/2.4\delta}\right)\frac{1}{T_{\theta^{*}}}\geqslant\left(\log{1/2.4\delta}\right)\frac{1}{D_{\theta^{*}}}$, where $T_{\theta^{*}}:=\max_{w\in\mathcal{P}(\mathcal{X})}\min_{\theta:a^{*}(\theta)\neq a^{*}(\theta^{*})}\sum_{k\in[K]}w_{k}KL\left(\nu^{k}_{\theta},\nu^{k}_{\theta^{*}}\right)$ and $D_{\theta^{*}}:=\max\limits_{w\in\mathcal{P}(\mathcal{X})}\min\limits_{x\in\mathcal{X},x\neq x^{*}}\frac{\left({\theta^{*}}^{T}\left(x^{*}-x\right)\right)^{2}}{\left\lVert x^{*}-x\right\rVert^{2}_{\left(\sum_{x\in\mathcal{X}}w_{x}xx^{T}\right)^{-1}}}$, where $x^{*}=x_{a^{*}}$. The bound suggests a natural $\delta$-PAC strategy, namely, to sample arms according to the distribution

In fact, as [8, Sec. 2.2] explains, using the Ordinary Least Squares (OLS) estimator $\widehat{\theta}$ for $\theta^{*}$ and sampling arm $x\in\mathcal{X}$ exactly $2\lfloor w^{*}N\rfloor$ times with $N=\mathcal{O}\left(\frac{\log{K/\delta}}{D_{\theta^{*}}}\right)$ ensures $(x-x^{*})^{T}\widehat{\theta}>0,~{}\forall x\neq x^{*}$ with probability $\geqslant 1-\delta.$ Unfortunately, this sampling distribution cannot directly be implemented since $x^{*}$ is unknown.

Fiez et al circumvent this difficulty by designing a nontrivial strategy (RAGE) that attempts to mimic the optimal allocation $w^{*}$ in phases. Specifically, in phase $m$, it tries to eliminate arms that are about $2^{-m}$-suboptimal (in their gaps), by solving (1) with a plugin estimate of $\theta^{*}$. The resulting fractional allocation, passed through a separate discrete rounding procedure, gives an integer pull count distribution which ensures that all surviving arms’ mean differences are estimated with high precision and confidence.

Though direct and appealing, this phased elimination strategy is based crucially on solving minimax problems of the form (1). Though the inner (max) function is convex as a function of $w$ on the probability simplex (see e.g., Lemma 1 in [21]), it is non-smooth, and it is not made explicit how, and to what extent, it must be solved in [8]. Fortunately, we are able to circumvent this obstacle by using ideas from games between no-regret online learners with optimism, as introduced by the work of Degenne et al [6] for unstructured bandits.

From Pure-exploration Games to $\delta$-PAC Algorithms: Degenne et al [6]. We briefly explain some of the insights in [6] that we leverage to design an explicit linear bandit-$\delta$-PAC algorithm with low computational complexity. For a fixed weight parameter $\theta^{*}\in\mathbb{R}^{d},$ consider the two-player, zero-sum Pure-exploration Game in which the $MAX$ player (or column player) plays an arm $k\in[K]$ while the $MIN$ (or row) player chooses an alternative bandit model $\theta\in\mathbb{R}^{d}$ such that $a^{*}(\theta)\neq a^{*}.$ $MAX$ then receives a payoff of $\sum_{k\in[K]}KL\left(\nu^{k}_{\theta^{*}},\nu^{k}_{\theta}\right)$ from $MIN.$ For a given $w\in\mathcal{P}(\mathcal{X}),$ define $T_{\theta^{*}}(w)=\min_{\theta:a^{*}(\theta)\neq a^{*}}\sum_{x\in\mathcal{X}}w_{x}xx^{T},$ and $w^{*}(\theta^{*})$ the mixed strategy that attains $T_{\theta^{*}}.$ With $MAX$ moving first and playing a mixed strategy $w\in\mathcal{P}(\mathcal{X}),$ the value of the game becomes $T_{\theta^{*}}$. In the unstructured bandit setting, to match the sample complexity lower bound, any algorithm must essentially sample arm $k\in[K]$ at rate $\frac{N^{K}_{t}}{t}\rightarrow w^{*}_{k}(\theta^{*}),$ where $N^{k}_{t}$ is the number of times Arm $k$ has been sampled up to time $t$ [12]. This helps explain why any $\delta$-PAC algorithm implicitly needs to solve the Pure Exploration Game $T_{\theta^{*}}.$

We crucially employ no-regret online learners to solve the Pure Exploration Game for linear bandits. More precisely, no-regret learning with the well-known Exponential Weights rule/Negative-entropy mirror descent algorithm [16] on one hand, and a best-response convex programming subroutine on the other, provides a direct sampling strategy that obviates the need for separate allocation optimization and rounding for sampling as in [8]. One crucial advantage of our approach (inspired by [6]) is that we only use a best response oracle to solve for $T_{\theta^{*}}(w)$, which gives us a computational edge over [8] who employ the computationally more costly max-min oracle to solve $T_{\theta^{*}}(w),$ or, its linear bandit equivalent, $D_{\theta^{*}}.$

Our algorithm, that we call “Phased Elimination Linear Exploration Game” (PELEG), is presented in detail as Algorithm 1. PELEG proceeds in phases with each phase consisting of multiple rounds, maintaining a set of active arms $\mathcal{X}_{m}$ for testing during Phase $m$. An OLS estimate $\widehat{\theta}_{m}$ of $\theta^{*}$ is used to estimate the mean reward of active arms and, at the end of phase $m$, every active arm with a plausible reward more than $\approx 2^{-m}$ below that of some arm in $\mathcal{X}_{m}$ is eliminated. Suppose $\mathcal{S}_{m}:=\left\{x\in\mathcal{X}\setminus\{x^{*}\}:{\theta^{*}}^{T}\left(x^{*}-x\right)<\frac{1}{2^{m}}\right\}$. If we can ensure that $\mathcal{X}_{m}\subset\mathcal{S}_{m}$ in every Phase $m\geqslant 1,$ then PELEG will terminate within $\lceil\log_{2}(1/\Delta_{\min})\rceil$ phases, where $\Delta_{\min}=\min_{x\neq x^{*}}{\theta^{*}}^{T}\left(x^{*}-x\right).$ This statement is proved in Corollary 2 in the Supplementary Material.

If we knew $\theta^{*},$ then we could sample arms according to the optimal distribution $w^{*}$ in (1). However, since all we now have at our disposal is the knowledge that $\Delta_{i}\leqslant 2^{-m},~{}\forall x_{i}\in\mathcal{X}_{m},$ we can instead construct a sampling distribution $w^{*}_{m}$ by solving the surrogate $w^{*}_{m}=\mathop{\mathrm{argmin}}_{w\in\mathcal{P}(\mathcal{X})}\max_{x,x^{\prime}\in\mathcal{X}_{m}:x\neq x^{\prime}}\parallel x-x^{\prime}\parallel^{2}_{\left(\sum_{x\in\mathcal{X}}w_{x}xx^{T}\right)^{-1}}$, and sampling each arm in $\mathcal{X}_{m}$ sufficiently often to produce a small enough confidence set. This is precisely what RAGE [8] does. However solving this optimization is, as mentioned in Sec. 3, computationally expensive and RAGE repeatedly accesses a minmax oracle to do this. Note that in simulating this algorithm, the authors implement an approximate oracle using the Frank-Wolfe method to solve the outer optimization over $w$ [8, Sec. F]. The $\max$ operation, however, renders the optimization objective non-smooth, and it is well-known that the Frank-Wolfe iteration can fail with even simple non-differentiable objectives (see e.g., [4]). We, therefore, deviate from RAGE at this point by employing three novel techniques, the first two motivated by ideas in [6].

• •

  We formulate the above minimax problem as a two player, zero-sum game. We solve the game sequentially, converging to its Nash equilibrium by invoking the use of the EXP-WTS algorithm [3]. Specifically, in each round $t$ in a phase, PELEG supplies EXP-WTS with an appropriate loss function $l^{MAX}_{t-1}$ and receives the requisite sampling distribution $w_{t}$ (lines 15 & 18 of the algorithm). This $w_{t}$ is then fed to the second no-regret learner – a best response subroutine – that finds the ‘most confusing’ plausible model $\lambda$ to focus next on (line 16). This is a minimization of a quadratic function over a union of finitely many convex sets (halfspaces intersecting a ball) which can be transparently implemented in polynomial time.

• •

  Once the sampling distribution is found, there still remains the problem of actually sampling according to it. Given a distribution $w\in\mathcal{P}(\mathcal{X}_{m}),$ approximating it by sampling $x\in\mathcal{X}$ $\lfloor Nw_{x}\rfloor$ or $\lceil Nw_{x}\rceil$ times can lead to too few (resp. many) samples. Other naive sampling strategies are, for the same reason, unusable. While [8] invokes a specialized rounding algorithm for this purpose, we opt for a more efficient tracking procedure (line 19): In each Round $t$ of Phase $m$, we sample Arm $k_{t}:=\mathop{\mathrm{argmin}}\limits_{k\in[K]}n_{t-1}^{k}/\sum\limits_{s=1}^{t}w_{s}^{k}$, where $n^{k}_{t}$ is the number of times Arm $k$ has been sampled up to time $t.$ In Lem. 3, we show that this procedure is efficient, i.e., $\sum\limits_{s=1}^{t}w_{s}^{k}-\left(K-1\right)\leqslant n_{t}^{k}\leqslant\sum\limits_{s=1}^{t}w_{s}^{k}+1.$

• •

  Finally, in each phase $m$, we need to sample arms often enough to (i) construct confidence intervals of size at most $2^{-(m+1)}$ around $(x-x^{\prime})^{T}\theta^{*},~{}\forall x,x^{\prime}\in\mathcal{X}_{m},$ (ii) ensure that $\mathcal{X}_{m}\subset\mathcal{S}_{m}$ and (iii) that $x^{*}\in\mathcal{X}_{m}.$ In Sec. E, we prove a Key Lemma (whose argument is discussed in Sec. 5) to show that our novel Phase Stopping Criterion ensures this with high probability.

It is worth remarking that naively trying to adapt the strategy of Degenne et al [6] to the linear bandit structure yields a suboptimal (multiplicative $\sqrt{d}$) dependence in the sample complexity, thus we adopt the phased elimination template of Fiez et al [8]. We also find, interestingly, that this phased structure eliminates the need to use more complex, self-tuning online learners like AdaHedge [5] in favour of the simpler Exponential Weights (Hedge).

The main theoretical result of this paper is the following performance guarantee.

In Sec. 5, we sketch the arguments behind the result. The proof in its entirety can be found in Sec. F in the Supplementary Material.

This section outlines the proof of the $\delta$-PAC sample complexity of Algorithm 1 (Theorem 1) and describes the main ideas and challenges involved in the analysis.

At a high level the proof of Theorem 1 involves two main parts: (1) a correctness argument for the central while loop that eliminates arms, and (2) a bound for its length, which, when added across all phases, gives the overall sample complexity bound.

1. Ensuring progress (arm elimination) in each phase. At the heart of the analysis is the following result which guarantees that upon termination of the central while loop, the uncertainty in estimating all differences of means among the surviving (i.e., non-eliminated) arms remains bounded.

Proof sketch. Phase $m$ ends at time $t$ when the ellipsoid $\mathcal{E}(0,V_{t}^{m},r_{m})$, with center $0$ and shape according to the arms played in the phase so far, becomes small enough to avoid intersecting the half spaces $\mathcal{C}_{m}(x)$, for all surviving arms $x$, within the ball $\cap B(0,D_{m})$ (Step 13 of the algorithm) which is required to keep loss functions bounded for no-regret properties.

Suppose, for the sake of simplicity, that only two arms $x_{i}$ and $x_{j}$ are present when phase $m$ starts. Figure 1(a) depicts a possible situation when the phase ends. $\mathcal{C}_{m}(x_{i})\equiv\mathcal{C}_{m}(x_{i};\varepsilon_{m})$ and $\mathcal{C}_{m}(x_{j};\varepsilon_{m})$ with $\varepsilon_{m}\approx 2^{-m}$ are halfspaces, denoted in gray, that intersect the ball $B(0,D_{m})$ in the areas colored red. In this situation, the ellipsoid $V_{t}^{m}$, shaded in blue, has just broken away from the red regions in the interior of the ball. Because its extent in the direction $x_{i}-x_{j}$ lies within the strip between the two hyperplanes bounding $\mathcal{C}_{m}(i),\mathcal{C}_{m}(j)$, it can be shown (see proof of lemma in appendix) that $\left\lVert x_{i}-x_{j}\right\rVert_{(V_{t}^{m})^{-1}}$ is small enough to not exceed roughly $2^{-m}$.

The more challenging situation is when the ellipsoid $V_{t}^{m}$ breaks away from the red regions by breaching the boundary of the ball $B(0,D_{m})$, as in the green ellipsoid in Figure 1(b). The while loop terminating at this time would not satisfy the objective of controlling $\left\lVert x_{i}-x_{j}\right\rVert_{(V_{t}^{m})^{-1}}$ to within $2^{-m}$, since the extent of the ellipsoid in the direction $x_{i}-x_{j}$ is larger than the gap between the halfspaces $\mathcal{C}_{m}(x_{i})$ and $\mathcal{C}_{m}(x_{j})$. A key idea we introduce here is to shrink the hyperplane gap (i.e., $\varepsilon_{m}$) by a factor (precisely $D_{m}\sqrt{C}(8\log K^{2}/\delta_{m})^{-1}$) which is represented by the min operation in Step 7. In doing this we bring the halfspaces closer, and then insist that the ellipsoid break away from these new halfspaces within the ball. This more stringent requirement guarantees that when the loop terminates, the extent of the final ellipsoid (shaded in blue) stays within the original, unshrunk, gap ensuring $\left\lVert x_{i}-x_{j}\right\rVert_{(V_{t}^{m})^{-1}}\lessapprox 2^{-m}$.

2. Bounding the number of arm pulls in a phase. The main bound on the length of the central while loop is the following result.

To prove this we use the no-regret property of both the best-response $MIN$ and the EXP-WTS $MAX$ learner (the full proof appears in the appendix). A key novelty here is the introduction of the ball $B(0,D_{m})$ as a technical device to control the $2$-norm radius of the final stopped ellipsoid $\mathcal{E}(0,V_{t}^{m},r_{m})$ (inequality $(i)$ in the proof) when used with the basic tracking rule over arms introduced by Degenne et al [6].

We numerically evaluate PELEG, against the algorithms $\mathcal{X}\mathcal{Y}$-static ([17]), LUCB ([11]), ALBA ([19]), LinGapE ([15]) and RAGE ([8]), for 3 common benchmark settings. The oracle lower bound is also calculated. Note: In our implementation, we ignore the term $B(0,D_{m})$ in the phase stopping criterion; this has the advantage of making the criterion check-able in closed form. We simulate independent, $\mathcal{N}(0,1)$ observation noise in each round. All results reported are averaged over 50 trials. We also empirically observe a $100\%$ success rate in identifying the best arm, although a confidence value of $\delta=0.1$ is passed in all cases.

Setting 1: Standard bandit. The arm set is the standard basis $\left\{e_{1},e_{2},\ldots,e_{5}\right\}$ in 5 dimensions. The unknown parameter $\theta^{*}$ is set to $\left(\Delta,0,\ldots,0\right)$, where $\Delta>0$, with $\Delta$ swept across $\left\{0.1,0.2,0.3,0.4,0.5\right\}$. As noted in [15], for $\Delta$ close to $0$, $\mathcal{X}\mathcal{Y}$-static’s essentially uniform allocation is optimal, since we have to estimate all directions equally accurately. However, PELEG performs better (Fig. 2(a)) due to being able to eliminate suboptimal arms earlier instead of uniformly across all arms. Fig. 2(b) compares PELEG and RAGE in the smaller window $\Delta\in\left[0.11,0.19\right]$, where PELEG is found to be competitive (and often better than) RAGE.

Setting 2: Unit sphere. The arms set comprises of $100$ vectors sampled uniformly from the surface of the unit sphere $\mathbb{S}^{d-1}$. We pick the two closest arms, say $u$ and $v$, and then set $\theta^{*}=u+\gamma(v-u)$ for $\gamma=0.01$, making $u$ the best arm. We simulate all algorithms over dimensions $d=10,20,\ldots,50$. This setting was first introduced in [19], and PELEG is uniformly competitive with the other algorithms (Fig. 2(c)).

Setting 3: Standard bandit with a confounding arm [17]. We instantiate $d$ canonical basis arms $\{e_{1},e_{2},\ldots,e_{d}\}$ and an additional arm $x_{d+1}=(\cos(\omega),\sin(\omega),0,\ldots,0)$, $d=2,\dots,10$, with $\theta^{*}=e_{1}$ so that the first arm is the best arm. By setting $0<\omega<<1$, the $d+1$th arm becomes the closest competitor. Here, the performance critically depends on how much an agent focuses on comparing arm $1$ and arm $d+1$. LinGapE performs very well in this setting, and PELEG and RAGE are competitive with it (Fig. 2(d)).

We have proposed a new, explicitly described algorithm for best arm identification in linear bandits, using tools from game theory and no-regret learning to solve minimax games. Several interesting directions remain unexplored. Removing the less-than-ideal dependence on the feature $C$ of the arm geometry and the extra logarithmic dependence on $\log(1/\delta)$ are perhaps the most interesting technical questions. It is also of great interest to see if a more direct game-theoretic strategy, along the lines of [6], exists for structured bandit problems, as also whether one can extend this machinery to solve for best policies in more general Markov Decision Processes.

Broader Impact. This work is largely theoretical in its objective. However, the problem that it attempts to lay sound theoretical foundations for is a widely encountered search problem based on features in machine learning. As a result, we anticipate that its implications may carry over to domains that involve continuous, feature-based learning, such as attribute-based recommendation systems, adaptive sensing and robotics applications. Proper care must be taken in such cases to ensure that recommendations or decisions from the algorithms set out in this work do not transgress considerations of safety and bias. While we do not address such concerns explicitly in this work, they are important in the design and operation of automated systems that continually interact with human users.