1 Introduction↩︎

The study of bandit algorithms has seen a resurgence over the past two decades, driven by applications in online advertising [1], [2], clinical trials [3], anomaly detection [4], [5], and recommendation systems [6], [7]. Within this framework, we consider a sequential decision-making problem arising from a fundamental asymmetry in communication bandwidth. A learner coordinates with an agent in the field: the learner can transmit detailed instructions prescribing a batch of \(B\) measurements for the agent to take, but the agent—after observing all \(B\) outcomes—can respond with only a single bit of feedback. This model is motivated by settings where devices observing rewards have severely limited communication capacity and cannot accumulate memory between interactions. In sensor networks used for environmental monitoring or industrial diagnostics, for instance, each sensor may be battery-constrained and able to transmit only a limited number of bits per reporting interval, and its on-board memory may be too small to store a full history of measurements. Similarly, in federated learning and edge computing deployments, a central server orchestrates experiments by dispatching actions to end devices—phones, IoT endpoints, and similar devices—which execute them over a fixed window before returning a short summary; crucially, the device participating in one round may differ from the device participating in the next, precluding any accumulation of local state. In both cases, single-device-with-unlimited-memory models such as [8], [9] and per-pull few-bits models such as [10]–[12] (outlined in more detail below) may not fully capture the relevant constraints.

We study the above setting under the standard stochastic linear bandit observation model, in which each reward is a linear function of an unknown parameter vector corrupted by noise. Our goal is to characterize the fundamental limits of learning under this one-bit uplink bottleneck, and to design algorithms whose performance approaches those limits. Specifically, we focus on regret minimization: minimizing the cumulative sub-optimality gap—the difference in mean reward between the best action and the action played—over a fixed time horizon \(T\).

In the standard linear bandit setting [13], the learner directly observes the generated rewards in each time step, and can use this information to guide decision-making in future time steps. Two prominent lines of work studying the role of communication constraints in linear bandits are as follows:

• In works such as [10]–[12], a memoryless decentralized agent observes each reward, and based on that reward alone, it sends back a few bits of information (e.g., 3 or 4 bits), i.e., a quantization of the reward.

• In works such as [8], [9], the agent(s) observing the rewards has unlimited memory,¹ and the communication constraint is on the total number of bits sent throughout the time horizon. This allows each agent to perform local estimation and send larger amounts of information at suitably-chosen times (while sending nothing at the other times).

As hinted above, the main premise of our work is that these settings leave a considerable unexplored “middle ground” in which the agent has limited memory and communication occurs at regular intervals, but not every round. This setting leads to both distinct algorithmic ideas and new insights, such as just one bit at the end of each \(\sqrt{T}\)-round batch (with time horizon \(T\)) often sufficing to match the minimax-optimal regret of unconstrained learning to within logarithmic factors.

Our paper is organized as follows: In Section 1.1, we provide a more detailed summary of existing works related to our problem; in Section 1.2, we outline our main contributions; in Section 2, we give a formal presentation of the problem setup; in Section 3, we formally state our main results; and in Section 4, we detail the corresponding algorithms. The proofs can be found in the appendix.

1.1 Related Work↩︎

Linear Bandits. Stochastic linear bandits were first studied in the “standard” setting (i.e., without communication or batch constraints) in [14], and a prominent follow-up work is [15], who considered an algorithm for stochastic linear bandits with a finite action set based on the “optimism principle” [13]. [16] extended these ideas to provide an algorithm attaining \(\widetilde{O}(d\sqrt{T})\) regret for any action set with bounded mean rewards, which they also showed to be minimax optimal up to logarithmic factors for worst-case action sets. The same \(\Omega(d\sqrt{T})\) minimax lower bound was subsequently established for the unit sphere and hypercube action sets [13]. Further algorithms for linear bandits with finite action sets were later derived [17]–[19], all of which (alongside [15]) obtain an upper bound of \(\widetilde{O}(\sqrt{dT \log \lvert \cA \rvert})\) on the regret, with varying logarithmic dependence. Complementary lower bounds of \(\widetilde{\Omega}(\sqrt{dT \min\{d, \log \lvert \cA \rvert \} })\) are also well-known for fixed finite action sets (e.g., see [20], [21]), and \(\Omega(\sqrt{dT \log (T/d) \log \lvert \cA \rvert})\) for finite action sets that change in each time step [19].

Bandits with Communication Constraints. Most work on linear bandits assumes that the reward of an action can be observed directly by the learner (with full precision). However, this assumption may be impractical for real-world applications in which the reward observations are done by some agent (e.g., sensor) before being communicated to the learner (central server). This motivated various communication-constrained linear bandit problems, which have garnered significant attention in recent research; see [8] and the references therein. The studies most pertinent to this work are those that focus on the quantization of the reward feedback communicated from agent to learner, which is motivated by applications where uplink communication bandwidth is limited. In particular, [10] devised a quantization scheme that allows existing multi-armed and linear bandit algorithms to be run with an uplink communication cost² of a few bits per arm pull, while maintaining the same regret as the unquantized algorithm up to a small multiplicative factor. An approach based on quantizing the linear parameters (rather than the rewards) was also proposed in [11], attaining \(\widetilde{O}(d\sqrt{T})\) regret with an uplink communication cost of \(\Theta(d)\) per round. In contrast to these works, our agents have limited memory and can only send one bit after an entire batch of \(B\) pulls, which forces the learner to pre‑commit actions and reduces the effective communication rate to \(1/B\) bits per round, which can be far less than 1 bit per round when \(B\) is large.

Beyond these, communication-constrained bandits have been studied under a variety of related assumptions, including federated linear bandits [22]–[26] and differentially private linear bandits [27]–[29] where the privacy constraint induces a communication-like bottleneck. Since the number of such works is large and most operate under assumptions substantially different from ours (e.g., multi-agent coordination, privacy, or unlimited per-agent memory), we focused primarily on the few above that are most directly comparable.

Batched Bandits. Batched bandits were first studied in [30], where they showed that in the multi-armed setting, \(O(\log \log T)\) batches suffice to attain order-optimal regret. It was then shown in [31] that in order to obtain order-optimal minimax regret in the multi-armed setting, \(\Theta(\log \log T)\) batches is both necessary and sufficient for a finite time horizon \(T\). \(O(\log \log T)\) batches were also shown to be sufficient to obtain order-optimal regret in the contextual linear bandit setting [32]–[34], of which linear bandits are a special case. Finally, [35] proved that 3 batches are necessary and sufficient to attain asymptotic optimality for a fixed instance as \(T \to \infty\). We also note that, while not explicitly stated as such, the algorithms in [8], [17]–[19] choose multiple arms simultaneously and thus permit varying degrees of batching.

The preceding works allow variable-length batches, whereas fixed batch lengths can also have significant practical relevance, and are popular in related topics such as Bayesian optimization [36]. While fixed batch lengths have been considered in linear bandits, the ones that we are aware of have a different emphasis such as privacy [37], [38], best-arm identification [39], or converting arbitrary algorithms to batch settings [40]. Accordingly, we believe that our findings on regret with fixed batch lengths are of general interest even regardless of communication considerations. We also briefly note that the concept of delayed feedback is relevant [41], [42], since a batch length \(B\) implies a delay lying in the range \([0,B]\). Within this setting, we note a result from [43], which when translated to our setup (without \(1\)-bit constraints), yields a regret upper bound of \(\widetilde{O}(B + \sqrt{dT \min\{d, \log \lvert \cA \rvert\}} )\). Compared to the regret in the vanilla linear bandit setup, this introduces an additive “batch or delay penalty” of \(\widetilde{O}(B)\). In contrast, Corollary 1 establishes that a significantly larger additive penalty of \(\Omega(B \min\{d, \log \lvert \cA \rvert\})\) is unavoidable in our setup. This demonstrates that our batched and communication constrained setup is a strictly harder setting compared to the standard delayed-feedback setting.

1.2 Contributions↩︎

As noted above, we introduce a new problem setup serving as a “middle ground” between two extremes studied in previous works. Our technical contributions are outlined as follows for an action set \(\cA\), batch size \(B\), dimension \(d\), and time horizon \(T\) (see Section 2 for the detailed problem setup):

• We provide an algorithm that achieves an \(\lvert\cA \rvert\)-independent regret bound that is minimax order-optimal (up to logarithmic factors), even when the noise terms \((\xi_t)_{t=1}^T\) are only assumed to have finite variance (thus potentially being much heavier than sub-Gaussian noise).

• We provide a second algorithm that achieves an \(\lvert \cA \rvert\)-dependent regret bound that is order-optimal (up to logarithmic factors) in broad scaling regimes of \((\lvert \cA \rvert , B,d,T)\).

• We provide an algorithm-independent minimax lower bound, showing that incurring an expected regret of \(\Omega(B\min\{d, \log \lvert \cA \rvert \})\) is unavoidable in the worst case. In fact, this bound holds even in the completely noiseless setting (\(\sigma = 0\)), demonstrating that this bottleneck is purely a consequence of the \(1\)-bit communication constraint. This is combined with well-known lower bounds for standard linear bandits to establish the above near-optimality claims.

Our algorithm for \(\lvert \cA \rvert\)-independent regret is the simpler of the two (though still having numerous technical challenges compared to the standard setting), and involves performing phased elimination with mean rewards that are estimated by always pulling the same arm \(B\) times in a given batch. In contrast, our algorithm for \(\lvert \cA \rvert\)-dependent regret crucially avoids doing this³ and instead incorporates initial steps to find a safe arm whose regret is “not too high”, and partially relies on it to reduce regret.

2 Problem Setup↩︎

We consider a stochastic linear bandit instance with dimension \(d \in \bN\), a finite⁴ action set \(\cA \subset \bR^d\), unknown parameter vector \(\theta \in \bR^d\), and time horizon \(T \in \bN\). At each time step \(t \in \{1,\dots, T\}\), an action \(A_t \in \cA\) is played, and the reward \[\label{eq:reward} Y_t = \langle A_t, \theta\rangle + \xi_t\tag{1}\] is generated, where \((\xi_t)_{t=1}^T\) is a sequence of i.i.d. noise terms with \(\bE[\xi_t] = 0\) and \(\bE[\xi_t^2] \leq \sigma^2\) for some known \(\sigma > 0\). We further assume the feature vectors in \(\cA\) are unique and span \(\bR^d\), and that mean rewards are bounded, in the sense that \(\lvert \langle a, \theta\rangle \rvert \leq 1, \;\forall a \in \cA\).

For a parameter \(B \in \{1,\dots, T\}\), we assume the time horizon is split into \(M = \lceil T/B\rceil\) equal-sized batches of size \(B\) (except possibly a shorter final batch). In each batch \(m \in \{1,\dots, M\}\), we have the following interaction between a central learner and an agent:

1. At the beginning of the batch, the learner chooses a length-\(B\) sequence of arms \(A_{(m-1)B+1}\), \(A_{(m-1)B +2}, \dots, A_{mB}\) and a \(1\)-bit quantization function \(\smash{Q_m : \bR^B \to \{0,1\}}\), both of which may depend on the feedback received from batches \(1,\dots,m-1\).

2. The agent receives the \(1\)-bit quantization function \(Q_m\), and directly observes the rewards \(Y_{(m-1)B + 1}, Y_{(m-1)B + 2}, \dots, Y_{mB}\), generated according to 1 .

3. The agent computes \(Q_m(Y_{(m-1)B + 1}, Y_{(m-1)B + 2}, \dots, Y_{mB})\) and transmits it to the learner.

The goal of the learner is to design an algorithm to minimize the cumulative regret, defined as \[\label{eq:regret95definition} R_T \mathrel{\vcenter{:}}= \sum_{t=1}^T \langle a^* - A_t, \theta \rangle,\tag{2}\] where \(a^* \mathrel{\vcenter{:}}= \arg\max_{a \in \cA} \, \langle a, \theta \rangle\) is the optimal arm. We will consider both the expected regret \(\mathbb{E}[R_T]\) and high-probability guarantees that hold with probability \(1-\delta\), noting the latter can easily be converted to the former (while at most affecting logarithmic terms) by setting \(\delta = \frac{1}{T}\).

3 Main Results↩︎

We now formally state our main results, which together characterize the minimax regret of stochastic linear bandits under 1-bit per-batch communication constraints. A notable consequence of our bounds is that a single bit of feedback per batch suffices to match near-optimal unquantized, unbatched regret even for batch sizes as large as \(B = \widetilde{O}(\sqrt{T})\). This demonstrates that the communication bottleneck is less severe than one might expect. The proofs are given in Appendices 8, 9, and 10.

3.1 Regret Lower Bound↩︎

We begin by stating our algorithm-independent minimax lower bound.

We informally outline the proof idea as follows: When \(\lvert \cA \rvert \le \exp(\Theta(d))\), the \(B \log \lvert \cA \rvert\) term arises because we can form \(\lvert \cA \rvert\) “well-separated” unit-norm vectors using tools from coding theory. We require \(\log_2 \lvert \cA \rvert\) bits to identify the correct one (corresponding to \(B \log \lvert \cA \rvert\) pulls), and before this is achieved, we incur constant regret per round. When \(\lvert \cA \rvert \ge \exp(\omega(d))\), we can still use this argument on a subset of size \(\exp(\Theta(d))\), with the remaining actions being “dummy” suboptimal actions.

Crucially, this lower bound holds even in the completely noiseless setting (\(\sigma = 0\)): even with perfect reward observations, the 1-bit uplink constraint alone forces \(\Omega(B\min\{d,\log|\cA|\})\) regret. This demonstrates that the bottleneck is purely a communication bottleneck rather than a statistical one.

For the remainder of the paper we assume \(\sigma = \Theta(1)\) (see Remark [rem:sigma95scaling] for extensions to other scalings); stochastic noise then introduces an additional statistical barrier on top of the communication bottleneck. Combining Theorem 1 with the well-known minimax lower bounds for standard linear bandits without communication constraints (e.g., [20]), we immediately obtain the following general lower bound.

The lower bound can be further tightened for the class of “non-mixing” algorithms, where in each batch \(m = 1,\dotsc, M\) the learner selects a single arm \(A_m \in \mathcal{A}\), and the agent pulls this arm \(B\) times, i.e., every arm chosen in the batch must be identical.

3.2 Regret Upper Bounds↩︎

With the lower bounds on regret established, we now turn to establishing upper bounds on the regret: Theorem 3 gives a regret bound that is independent of the action set size \(\lvert \cA \rvert\), while Theorem 4 gives an \(\lvert\cA \rvert\)-dependent upper bound that we then specialize to polynomial-size action sets.

In view of Corollary 1, we see that by setting \(\delta = 1/T\), Theorem 3 yields an expected regret that matches the minimax lower bound (up to logarithmic factors) when \(\lvert \cA \rvert = \exp(\Omega(d))\).

To better understand the behavior of this regret bound, we specialize Theorem 4 to the important special case where the action set size is polynomial in \(d\). Here we set \(\delta = 1/T\) to obtain a bound on the expected regret, though a high-probability counterpart naturally also follows.

Notice that ?? consists of three components: the fundamental communication bottleneck \(\Omega(B)\), the standard statistical bottleneck \(\Omega(\sqrt{dT})\), and an “algorithmic initialization penalty” \(\widetilde{O}(d^{3/2}\sqrt{B})\) (see Section 4 for discussion). The algorithm achieves near minimax optimality whenever this penalty term is absorbed by either of the two lower bounds. This is formalized in the following proposition, which also establishes that the degradation is not too severe when the penalty is not fully absorbed.

The proof of Corollary 3 is deferred to Appendix 10.4. The condition \(T/B = \Omega(d^2)\) requires that the horizon is long enough for the learner to receive \(\Omega(d^2)\) batches of feedback; this is natural given that the agent transmits only 1 bit per batch, so the learner is severely information-starved in short horizons. However, Corollary 3 guarantees a gap of at most \(\widetilde{O}(\sqrt{d})\) even in these harder regimes.

3.3 Discussion and Open Problems↩︎

While Theorem 3 attains near-optimal regret for exponential-sized action sets without any assumption on \(T\), some gaps remain in the guarantees of Theorem 4 for smaller action sets. For \(\lvert\cA\rvert = \mathrm{poly}(d)\), Corollary 3 establishes that \(T = \Omega(d^5)\) suffices for near order-optimality (or more generally, at least one of \(B = \Omega(d^3)\) or \(T = \Omega(d^2 B)\)), which captures broad scalings but is stricter than the \(T = \Omega(d)\) condition required in the standard unconstrained setting. For intermediate-sized action sets \(\lvert\cA\rvert = \exp(\Theta(d^\alpha))\) with \(\alpha \in (0,1)\), a similar argument to Corollary 3 reveals that Theorem 4 achieves the target bound \(\widetilde{O}(d^\alpha B + \sqrt{d^{1+\alpha}T})\) when either \(B = \Omega(d^{3(1+\alpha)})\) or \(T/B = \Omega(d^{2(1+2\alpha)})\). In summary, our results demonstrate near-optimality across broad scaling regimes of \((\lvert\cA\rvert, B, d, T)\); closing the remaining gaps is an interesting direction for future work.

4 Proposed Algorithms↩︎

In this section, we introduce the two algorithms establishing Theorems 3 and 4. Both are built on the phased elimination framework with a common template, but they differ fundamentally in how they handle the trade-off between communication efficiency and statistical precision. The algorithm for Theorem 3 prioritizes simplicity at the cost of a \(\sqrt{d}\) factor in the confidence width, while the algorithm for Theorem 4 recovers that factor via proportional sample allocation at the cost of a larger median-of-means block count. See Remark [rem:comparison] in Appendix 10 for a detailed comparison of the two algorithms, and Algorithms 1 and 2 in Appendices 9 and 10 for the full algorithm descriptions.

4.1 Preliminaries: Phased Elimination and 1-bit Mean Estimation↩︎

Phased elimination with \(G\)-optimal designs. Phased elimination algorithms [13], [17], [21], [45]–[47] partition the time horizon into epochs \(h = 1, 2, \dots\), maintaining an active set \(\cA_h \subseteq \cA\) of plausibly-optimal arms (with \(\cA_1 = \cA\)). Within each epoch, the learner uses an experimental design \(\rho_h \colon \cA_h \to [0,1]\) to efficiently estimate the mean rewards of all arms in \(\cA_h\) before eliminating those that appear suboptimal based on the confidence width \(W_h\).

Throughout, we make use of near \(G\)-optimal designs; specifically, provided that \(\cA_h\) is compact and spans \(\bR^d\), there exist designs with the following guarantees: \[\label{eq:near95optimal95design} \max_{a \in \cA_h} \lVert a \rVert_{G_h^{-1}}^2 \le 2d, \qquad \lvert \supp(\rho_h)\rvert \le 4d(\log\log d + 11) = \widetilde{O}(d),\tag{3}\] where \(G_h = \sum_{a \in \cA_h}\rho_h(a) aa^\top\) and \(\lVert a \rVert_V = \sqrt{a^\top V a}\) for a positive semi-definite matrix \(V\). For instance, such designs can be computed in polynomial time via the Frank-Wolfe algorithm [48]. The set \(\supp(\rho_h)\) is called the core set, and notably has a size of only \(\widetilde{O}(d)\). In the standard (unquantized and unbatched) setting, the rewards are directly observed, each core-set arm is pulled in proportion to \(\rho_h\), and a weighted least-squares estimator \(\hat{\theta}_h\) is formed. The mean reward of any arm \(b \in \cA_h\) is then estimated by \(\langle b, \hat{\theta}_h\rangle\). With appropriate epoch lengths and elimination thresholds, this yields the standard minimax regret bound of \(\widetilde{O}(\sqrt{dT \log \lvert \cA \rvert})\).

Adapting to our setting. Two immediate challenges arise in our constrained setup: (i) the learner observes only 1-bit summaries of \(B\) rewards rather than \(B\) unquantized rewards, rendering the standard weighted least-squares estimator unusable, and (ii) the allocation dictated by the continuous experimental design may not yield a whole number of batches, complicating the protocol.

We resolve (ii) by rounding per-arm allocations up to multiples of \(B\): each batch then pulls either a single arm (in Algorithm 1, and in most batches of Algorithm 2) or one core-set arm plus a pre-determined safe arm to fill the remaining slots (in the warm-start of Algorithm 2).

To resolve (i), we replace the standard mean estimator with a 1-bit mean estimator built on the framework of [49], [50]. In our setting, a single 1-bit “query” is executed by having the agent pull the same arm \(B\) times (or possibly fewer in Algorithm 2, but we defer this distinction to later) and applying a 1-bit threshold to the sample mean. This reduces the effective standard deviation of the continuous measurement to \(\sigma' = \sigma/\sqrt{B}\). With this established, we can employ two subroutines: 1BitLocalize uses \(\widetilde{O}\left(\log \frac{1}{\sigma'} + \log \frac{1}{\delta}\right)\) queries to return an interval \([L_a, U_a] \subseteq [-1,1]\) of width \(O(\sigma')\) that contains \(\mu_a\) with high probability; and 1BitRefine uses \(n_{\rm q}\) additional queries (for some suitably chosen \(n_{\rm q}\)) to return a final estimate \(\hat{Y}_{a,h}\) with variance \(\widetilde{O}(\sigma'^2/n_{\rm q})\) and bias \({O}(\sigma'/T^2)\). The detailed subroutines and their formal guarantees are given in Appendix 7.

Common template. Combining the preceding ingredients, a given epoch (indexed by \(h\)) in both algorithms proceeds as follows:

1. Compute a near \(G\)-optimal design \(\rho_h\) on \(\cA_h\) satisfying 3 .

2. Run 1BitLocalize on each \(a \in \supp(\rho_h)\) to obtain an interval \([L_a, U_a]\).

3. Split the refinement budget into \(K\) blocks. For each block \(j = 1, \dots, K\) and each core-set arm \(a \in \supp(\rho_h)\), run 1BitRefine to obtain independent scalar estimates \(\hat{Y}_{a,h}^{(j)}\).

4. Form a robust mean reward estimate \(\hat{\mu}_{b,h}\) for every active arm \(b \in \cA_h\) using the scalar estimates \(\hat{Y}_{a,h}^{(j)}\) and the design weights \(\rho_h\). This involves computing design-weighted parameter estimates (using the inverse matrix \(G_h^{-1}\)) and applying median-of-means aggregation. The order of steps is algorithm-dependent: Algorithm 1 takes the median of the scalars first, whereas Algorithm 2 computes block-wise parameters first.

5. Eliminate arms whose empirical gap exceeds the confidence width \(W_h\): \[\cA_{h+1} = \left\{a \in \cA_h : \max_{b \in \cA_h} \hat{\mu}_{b,h} - \hat{\mu}_{a,h} \le 2 W_h \right\}.\]

The two algorithms differ in (a) how refinement samples are allocated across core-set arms, (b) the order of operations in Step 4, (c) the number of blocks \(K\), (d) the confidence width \(W_h\), and (e) additional pre-processing before the main loop (for the \(\lvert \cA \rvert\)-dependent algorithm with large \(B\)). Both algorithms make use of a common precision parameter chosen as \(\eps_h = \sigma 2^{-h}/\sqrt{B}\), but they differ in how this translates to the final confidence width \(W_h\). We now outline both algorithms in more detail.

4.2 Algorithm 1: \(\lvert\cA\rvert\)-Independent Regret↩︎

For our \(\lvert\cA\rvert\)-independent result (which is primarily suited to large action sets, e.g., exponential-sized), we exploit the observation that it suffices to accurately estimate only the \(\widetilde{O}(d)\) scalars \(\{\mu_a\}_{a\in\supp(\rho_h)}\) rather than all \(|\cA|\) arm means simultaneously, replacing a union bound over \(|\cA|\) arms with one over only the \(\widetilde{O}(d)\) core-set arms. This enables two simplifications:

• Refinement samples are distributed uniformly across core-set arms (rather than proportionally to \(\rho_h\)), ensuring that each scalar estimate \(\hat{Y}_{a,h}\) has variance \(O(\epsilon_h^2)\) independent of \(\rho_h\).

• Median-of-means is applied directly to the scalar estimates to form a robust target \(\hat{Y}_{a,h} = \operatorname{median}\{\hat{Y}_{a,h}^{(j)}\}_{j=1}^K\). The global parameter is then estimated via the design weights as \[\label{eq:theta95hat95exp} \hat{\theta}_h = G_h^{-1}\sum_{a \in \supp(\rho_h)} \rho_h(a) \cdot a \cdot \hat{Y}_{a,h} \qquad \text{where} \qquad G_h = \sum_{a \in \supp(\rho_h)} \rho_h(a)\,aa^\top.\tag{4}\] Because concentration is only required over the \(\widetilde{O}(d)\) support arms, this requires only \(K = \widetilde{O}(\log(d/\delta))\) blocks⁷ rather than \(\widetilde{O}(\log(\lvert\cA\rvert/\delta))\).

The price paid for this simplification is a slightly looser confidence width \(W_h = \sqrt{2d}\,\epsilon_h\), arising from bounding the error propagation through \(\hat{\theta}_h\) (via Corollary 4 in Appendix 9). Pseudocode is given in Algorithm 1 in Appendix 9, and the full analysis is also given in Appendix 9.

4.3 Algorithm 2: \(\lvert\cA\rvert\)-Dependent Regret↩︎

For smaller (e.g., polynomial-sized) action sets, the extra \(\sqrt{d}\) penalty in the confidence width of Algorithm 1 prevents us from reaching minimax optimality. Algorithm 2 (detailed in Appendix 10) rectifies this by allocating refinement samples proportionally to \(\rho_h\) (see 3 ). By doing so, the resulting variances \(\Var(\hat{Y}_{a,h}^{(j)}) \propto 1/\rho_h(a)\) perfectly cancel against the design weights when propagating through the block-wise parameter estimates \[\label{eq:theta95hat95poly} \hat{\theta}_h^{(j)} = G_h^{-1}\sum_{a \in \supp(\rho_h)} \rho_h(a) \cdot a \cdot \hat{Y}_{a,h}^{(j)} \qquad \text{where} \qquad G_h = \sum_{a \in \supp(\rho_h)} \rho_h(a)\,aa^\top,\tag{5}\] yielding the tighter confidence width \(W_h = \eps_h\). However, because median-of-means must now be applied to the inner products \(\hat{\mu}_{b,h} = \operatorname{median}\{\langle b, \hat{\theta}_h^{(j)}\rangle\}_{j=1}^{K}\) simultaneously for all \(b \in \cA_h\), ensuring concentration requires a union bound over the active set. Under our finite-variance assumption, this necessitates using \(K = \widetilde{O}(\log(\lvert\cA\rvert/\delta))\) blocks, contributing the \(\sqrt{\log\lvert\cA\rvert}\) factor to the regret.

Small-\(B\) regime. Let \(\tau = \widetilde{O}(d\log(\lvert\cA\rvert/\delta))\) denote the “threshold” between the small-\(B\) regime and large-\(B\) regime (see Line [algline:tau] of Algorithm 2 for a precise definition). When \(B < \tau\), we simply initialize \(\cA_1 = \cA\) and run the common template above for all epochs. While this incurs an initialization cost of \(\widetilde{O}(dBK)\), the restricted size of \(B\) ensures this cost is bounded by \(\widetilde{O}(d^{3/2}\sqrt{B}\log^{3/2}(\lvert \cA \rvert/\delta))\).

Large-\(B\) regime. When \(B \geq \tau\), an initialization term of \(\widetilde{O}(dBK)\) becomes prohibitive, with the trivial global gap bound \(\Delta_b \le 2\) forcing significant over-exploration when \(B \gg d\). We circumvent this by prepending two pre-processing steps that restrict the effective suboptimality gap of every arm entering \(\cA_1\) from \(O(1)\) down to \(O(\sqrt{d/B})\):

• Safe arm identification (Algorithm 3). Through \(\lceil\log_2\lvert\cA\rvert\rceil\) rounds of tournament-style bisection, we iteratively split the candidate set in half, using a single bit to indicate which half has the higher estimated maximum mean reward, and keep only the winning half. Within each round, the agent executes a \(G\)-optimal design within a single batch, pulling multiple core-set arms simultaneously and computing their unquantized sample means, in contrast to the single-arm batches used in the main phased elimination loop. After \(\lceil\log_2\lvert\cA\rvert\rceil\) rounds, the surviving arm \(a_{\rm safe}\) has suboptimality gap at most \(\widetilde{O}(\log^{3/2}\lvert\cA\rvert\sqrt{d/B})\). This step uses \(O(B\log\lvert\mathcal{A}\rvert)\) arm pulls.

• Warm start (Algorithm 4). We run a single warm-start epoch of phased elimination in which \(a_{\rm safe}\) fills every slot not used by a core-set arm. This produces a refined active set \(\cA_1 \subseteq \cA\) whose maximum gap is \(O(\sqrt{d/B})\). The key insight is that \(a_{\rm safe}\) absorbs the vast majority of slots in each batch, effectively decoupling the exploration budget from the rigid batch size constraint: core-set arms are pulled only \(\widetilde{O}(B\log(\lvert\cA\rvert/\delta))\) times in total, keeping the initialization regret at \(\widetilde{O}(d^{3/2}\sqrt{B}\log(\lvert\cA\rvert/\delta))\) rather than the \(\widetilde{O}(dBK)\) incurred without warm-starting.

Following these pre-processing steps, the main phased elimination loop proceeds on \(\cA_1\) according to the common template. Pseudocode for the main loop is given in Algorithm 2, with the pre-processing subroutines detailed in Algorithms 3 and 4. See Appendix 10 for the detailed regret analysis.

5 Conclusion↩︎

We have studied the problem of batched stochastic linear bandits with a ‘batch-wise memoryless’ agent and a \(1\)-bit communication constraint. We presented two algorithms and provided a new minimax lower bound in this setting. For exponential-sized action sets, we provided an algorithm that matches our lower bound on the regret up to logarithmic factors, while for smaller action sets, we provided similar guarantees under broad scalings of the batch size, dimension, and time horizon. Notably, the regret from the standard setting can be matched to within logarithmic factors even in certain severely communication-constrained scenarios such as “1 bit per length-\(\sqrt{T}\) batch”. Perhaps the most immediate direction for future work is to devise an algorithm that attains near-optimal regret in the remaining scaling regimes where a gap remains.

6 Concentration and Experimental Design Inequalities↩︎

Here we provide formal statements of several inequalities used throughout the paper. We begin by presenting the theoretical guarantee of the median of means estimator, with the precise statement being taken from [51].

The next two results concern experimental design properties that will be used throughout the subsequent proofs. While these results are well-known, we include their proofs for the sake of completeness.

7 Details of 1-Bit Mean Estimation Subroutines↩︎

The subroutines in this section operate on a sequence of i.i.d. scalar observations \(X_1, X_2, \ldots\) with mean \(\mu \mathrel{\vcenter{:}}= \mathbb{E}[X] \in [-1,1]\) and variance \(\mathrm{Var}(X) \le \sigma'^2\), where \(\sigma' > 0\) is the effective standard deviation of a single observation.

The sample complexity is stated in terms of the number of 1-bit threshold queries: one query presents a single observation \(X_j\) to the learner and returns the single bit \(\mathbb{1}\{X_j \ge \gamma\}\) for a learner-chosen threshold \(\gamma\). The cost in raw arm pulls equals the number of queries multiplied by the number of arm pulls per observation, which varies depending on the context. In our algorithms, two settings arise:

• Full-batch queries (Algorithm 1 and Step 3 of Algorithm 2): In each batch the agent pulls arm \(a\) exactly \(B\) times, computes the batch average \(\bar{Y}_B = \tfrac{1}{B}\sum_{i=1}^B Y_i\), and returns a single bit. Thus \[X = \bar{Y}_B, \qquad \sigma' = \frac{\sigma}{\sqrt{B}}, \qquad \text{and one query costs } B \text{ raw arm pulls.}\]

• Partial-batch queries (Algorithm 4, Warm-Start epoch): For arm \(a \in \mathrm{supp}(\rho_0)\) with allocation \(u_0(a) = \lceil B\rho_0(a)\rceil\), the agent pulls arm \(a\) exactly \(u_0(a)\) times per batch (filling the remaining \(B - u_0(a)\) slots with \(a_{\mathrm{safe}}\)), computes the average of those \(u_0(a)\) rewards, and returns a single bit. Thus \[X = \bar{Y}_{u_0(a)}, \qquad \sigma' = \frac{\sigma}{\sqrt{u_0(a)}}, \qquad \text{and one query costs } u_0(a) \text{ raw arm pulls.}\]

Both subroutines below apply verbatim to either setting once \(\sigma'\) is identified from the context.

7.1 1BitLocalize: Coarse Interval Estimation↩︎

When our bandit algorithms invoke \([L_a, U_a] \leftarrow \mathrm{\small 1BitLocalize}(a, \delta_{\mathrm{loc}}, \sigma')\), the subroutine executes the localization protocol of [50] over \([-1,1]\). This procedure treats each scalar observation \(X_j\) as a single noisy measurement of \(\mu_a\) with standard deviation \(\sigma'\).

Specifically, the protocol uses existing median estimation techniques such as noisy binary search (e.g., [52]) to first locate a high-probability confidence interval \([L_a', U_a']\) containing the median \(M\) using 1-bit threshold queries. Then, by leveraging the well-known mean-median inequality \(|\mathbb{E}[X] - M| \le \sigma'\), we naturally obtain a high-probability confidence interval \([L_a, U_a] = [L_a' - \sigma', U_a' +\sigma']\) containing the true mean \(\mu_a\). See [50] for the full derivation leading to the following guarantee.

7.2 1BitRefine: Refined Mean Estimation↩︎

Given the localized interval \([L_a, U_a]\), we shift coordinates by setting \(X' \mathrel{\vcenter{:}}= X - \tfrac{L_a+U_a}{2}\). Then \(X'\) has mean \(\mu' \mathrel{\vcenter{:}}= \mu_a - \tfrac{L_a+U_a}{2}\) and \(\mathrm{Var}(X') \le \sigma'^2\). Conditioned on the localization event, \(|\mu'| \le 4\sigma'\). The base estimator proceeds as follows.

7.2.0.1 1. Modified Cutoff and Partitioning.

Fix a target accuracy \(\epsilon > 0\). We select a truncation threshold \[\label{eq:cutoff} t = 2^{i_{\max}} \cdot \sigma', \quad \text{where} \quad i_{\max} \mathrel{\vcenter{:}}= \left\lceil \log_2 T^2 \right\rceil,\tag{6}\] so that \(t \ge T^2\sigma'\). Following [49], we then partition \([-t, t]\) into non-overlapping symmetric regions \(R_1, R_{-1}, R_2, R_{-2}, \ldots, R_{\imax}, R_{-\imax}\) defined by exponentially growing interval boundaries \(m_i \sigma'\): \[R_i = \begin{cases} \sigma' \cdot \left[m_{i-1} , m_i \right) & \text{if } i \ge 1 \\ \\ - R_{-i} & \text{if } i \le -1 \end{cases} \quad \text{where} \quad m_0 = 0 \text{ and } m_i = 2^{i} \text{ for } i \ge 1.\]

Using a similar argument in [49], we can show that treating the insignificant region \(\{\lvert X \rvert > t\}\) as zero introduces a truncation bias bounded by \(O(\sigma'/T^2)\). We include the relevant steps here for the sake of completeness. For \(T \ge 3\), since \(|\mu'| \le 4\sigma'\) under the localization event, we have \[t \ge T^2\sigma' \ge 8\sigma' \ge 2|\mu'| \implies t - \lvert \mu' \rvert \ge \frac{t}{2} \implies \{|X'| > t \} \subseteq \{|X'-\mu'| > t/2 \}.\] Using this event inclusion together with the triangle inequality and Chebyshev’s inequality, we obtain \[\label{eq:trunc95bias} \begin{align} \left|\mathbb{E}\left[X' \cdot \mathbb{1}(|X'| > t)\right]\right| &\le \mathbb{E}\left[|X'-\mu'| \cdot \mathbb{1}\left(|X'| > t\right)\right] + \mathbb{E}\left[|\mu'| \cdot \mathbb{1}\left(|X'| > t\right)\right] \\ &\le \mathbb{E}\left[|X'-\mu'| \cdot \mathbb{1}\Big(|X'-\mu'| > \frac{t}{2}\Big)\right] + |\mu'| \cdot \mathbb{P}(|X'| > t) \\ &\le \mathbb{E}\left[ \frac{|X'-\mu'|^2}{t/2}\right] + |\mu'| \cdot \mathbb{P}(|X'| > t) \\ &\le \frac{\sigma'^2}{t/2} + 4\sigma' \cdot \frac{\sigma'^2}{(t/2)^2} \\ &\le \frac{2\sigma'}{T^2} + \frac{16\sigma'}{T^4} \\ &\le \frac{3\sigma'}{T^2}, \end{align}\tag{7}\] where the second last inequality follows from \(t \ge T^2 \sigma'\) and the last inequality holds for \(T \ge 4\). We note that the choice of truncation threshold \(t \ge T^2\sigma'\) makes the bias bound depend solely on \(T\) and \(\sigma'\), thus decoupling bias from the target accuracy parameter \(\epsilon\). This is the key modification we make relative to [49], where the authors chose \(t = \Theta(\sigma'^2/\epsilon)\) to achieve a bias of \(O(\epsilon)\), which is sufficient for their purpose of 1-dimensional mean estimation.

7.2.0.2 2. Region-Wise Estimation via Threshold Queries.

Next, we form an estimate \(\hat{\mu}_i'\) of each local mean contribution \(\mu_i' \mathrel{\vcenter{:}}= \mathbb{E}[X' \cdot \mathbb{1}(X' \in R_i)]\) for region \(R_i = [a_i, b_i)\). As established in [49], this task is reduced to drawing random thresholds \(T_i \sim \mathrm{Unif}(a_i, b_i)\) and comparing \(X'\) against the region boundaries and these random thresholds. Specifically, we allocate \(n_i = \lceil C\sigma'^2/\epsilon^2\rceil\) queries to each of the following \(4\) distinct threshold-query types per region:⁹ \[\mathbb{1}\{X' \ge a_i\}, \quad \mathbb{1}\{X' \ge T_{i}\}, \quad \mathbb{1}\{X' \le b_i\}, \quad \text{and } \quad \mathbb{1}\{X' \le T_{i}\},\] where \(C \ge 1\) is the absolute constant from [49], and fresh samples and thresholds are drawn for each query. Because we allocate queries to 4 types across the \(2 i_{\max}\) regions, the ceiling operator enforces a structural floor of \(n_i \ge 1\), requiring a minimum total budget of \(8 i_{\max}\) queries. The final shifted estimate aggregates these unbiased local estimates across the entire collection of regions up to \(i_{\max}\): \(\hat{\mu}_a = \sum_{|i| \le i_{\max}} \hat{\mu}_i' + \tfrac{L_a+U_a}{2}\), which satisfies the following guarantee.

In our phased elimination bandit algorithms, rather than specifying a target accuracy upfront, the learner allocates some fixed query budget \(n_{\rm q}\) to each arm. By inverting the sample complexity bound in Lemma 3, we obtain the following fixed-budget guarantee, which serves as the primary formal interface invoked by our bandit algorithms via the call \(\hat{Y}_{a,h}^{(j)} \leftarrow \mathrm{\small 1BitRefine}(a, [L_a, U_a], n_{\rm q})\)

8 Proofs of Lower Bounds↩︎

8.1 Proof of Theorem 1 (General Lower Bound)↩︎

We first state a connection between Hamming distance and inner product, whose proof is immediate from their definitions (and thus omitted).

Therefore, in order to produce a set \(\mathcal{V} \subset \{\pm1/\sqrt d\}^d\) with small pairwise inner products, it suffices to construct a binary code \(\cC \subset \{0, 1\}^d\) with block length \(d\) and Hamming distance at least \(d/4\). The Gilbert–Varshamov (GV) bound guarantees the existence of such a code.

We now prove Theorem 1 using the bounds above.

8.2 Proof of Theorem 2 (Lower Bound for Non-Mixing Algorithms)↩︎

9 Proof of Theorem 3 (\(\lvert \cA \rvert\)-Independent Upper Bound)↩︎

In this section, we formally establish Theorem 3 by providing the detailed pseudocode and regret analysis of our first algorithm with an \(\lvert \cA \rvert\)-independent regret bound. As discussed in Section 4.1, this approach exploits the fact that it suffices to estimate only the \(\lvert\supp(\rho_h)\rvert = \widetilde{O}(d)\) scalar quantities \(\{\langle a,\theta\rangle\}_{a \in \supp(\rho_h)}\) to successfully recover \(\hat{\theta}_h\). Thus, we can apply median-of-means directly to these individual scalar estimates, limiting the required number of blocks to \(K = \widetilde{O}(\log(d/\delta))\). Furthermore, by distributing the refinement queries uniformly across the core set, each scalar estimate achieves a variance of at most \(\eps_h^2/16\) unconditionally, which allows us to bound the confidence width by \(W_h = \sqrt{2d}\,\eps_h\) via Corollary 4.

The detailed pseudocode is presented in Algorithm 1. We first proceed with the analysis by first bounding the sample complexity of the localization and refinement stages (Appendix 9.1). We then establish a high-probability good event for the 1-bit estimators (Appendix 9.2), verify the confidence width and retention of the optimal arm (Appendix 9.3), and finally bound the cumulative regret (Appendix 9.4).

Throughout this section, let \(\sigma' = \sigma/\sqrt{B}\) and \(\eps_h = 2^{-h}\sigma'\) as in Line [algline:eps95h95exp] of Algorithm 1. We invoke Corollary 5 with the full-batch effective standard deviation \(\sigma' = \sigma/\sqrt{B}\); each query corresponds to \(B\) raw arm pulls. The resulting guarantees from ?? are: \[\label{eq:subroutine95constants} \Var(\hat{Y}) \le \frac{C_V \sigma'^2\log_2 T}{n_{\mathrm{q}}}, \qquad \lvert\mathrm{Bias}(\hat{Y})\rvert \le \frac{3\sigma'}{T^2},\tag{8}\] where \(n_{\mathrm{q}}\) denotes the number of queries (i.e., the number of raw samples divided by \(B\)) and \(C_V \ge 48\) is the variance constant from Corollary 5. Crucially, the bias bound is independent of both \(n_{\mathrm{q}}\) and the epoch index \(h\).

9.1 Sample Complexity per Epoch↩︎

To facilitate the regret analysis, we separate the sample complexity of the localization and refinement stages in each epoch.

9.1.0.1 Localization cost.

By Proposition [prop:localize], each call to 1BitLocalize with effective standard deviation \(\sigma' = \sigma/\sqrt{B}\) and failure probability \(\delta_{\mathrm{loc}} = \delta/(2S_{\max}\widetilde{H})\) uses at most \[n_{\mathrm{loc}} = C_{\mathrm{loc}}\left(\log\Big(\frac{1}{\sigma'}\Big) + \log\Big(\frac{1}{\delta_{\mathrm{loc}}}\Big)\right) = C_{\mathrm{loc}}\left(\frac{1}{2}\log\Big(\frac{B}{\sigma^2}\Big) + \log\left(\frac{2S_{\max}\widetilde{H}}{\delta}\right)\right)\] queries, where \(C_{\mathrm{loc}} > 0\) is the absolute constant from Proposition [prop:localize]. Since each query costs \(B\) raw arm pulls, and since \(S_{\max} = O(d \log \log d)\), and \(\widetilde{H} = \lceil \log_2 T \rceil\), the total localization cost over all support arms is bounded by \[\label{eq:mloc95h95exp} m_{\mathrm{loc},h} \le S_{\max} \cdot B \cdot n_{\mathrm{loc}} = O\left(dB \log\log d \cdot \log\Big(\frac{dB \log T}{\delta}\Big)\right),\tag{9}\] where we have absorbed \(\sigma = \Theta(1)\) into the \(O(\cdot)\) notation.

9.1.0.2 Refinement cost.

Because the uniform allocation \(u_h\) (see Line [algline:uh95exp]) is identical for every arm in the support, the total refinement cost \(m_{\mathrm{ref},h}\) is exactly \(K \cdot |\supp(\rho_h)| \cdot u_h\) raw arm pulls. Using \(\lvert\supp(\rho_h)\rvert \le S_{\max} = O(d \log\log d)\) and \(u_h \le B(16C_V \cdot 4^h \log_2 T + 1)\), we have \[\label{eq:mref95h95exp} m_{\mathrm{ref},h} \le K \cdot S_{\max} \cdot B\!\left(16C_V\cdot 4^h\log_2 T + 1\right) = O\!\left(K d B \log T \log\log d \cdot 4^h\right).\tag{10}\]

9.2 High-Probability Good Event↩︎

Define \(H\) as the final epoch of Algorithm 1 and the good event \(\cE = \cE_{\mathrm{loc}} \cap \cE_{\mathrm{ref}}\), where \[\begin{align} \cE_{\mathrm{loc}} &\mathrel{\vcenter{:}}= \bigcap_{h=1}^{H} \bigcap_{a \in \supp(\rho_h)} \left\{\mu_a \in [L_a, U_a] \;\text{ and }\; U_a - L_a \le \tfrac{8\sigma}{\sqrt{B}}\right\},\\[4pt] \cE_{\mathrm{ref}} &\mathrel{\vcenter{:}}= \bigcap_{h=1}^{H} \bigcap_{a \in \supp(\rho_h)} \left\{\lvert \hat{Y}_{a,h} - \mu_a \rvert \le \eps_h\right\}. \end{align}\]

9.3 Confidence Width and Arm Elimination↩︎

9.4 Regret Bound↩︎

10 Proof of Theorem 4 (\(\lvert \cA \rvert\)-Dependent Upper Bound)↩︎

In this section, we provide the pseudocode and detailed regret analysis for our second phased elimination algorithm, formally establishing the bounds stated in Theorem 4. The detailed pseudocode is presented in Algorithm 2.

We split our analysis into two regimes: the small-\(B\) regime, where \(B < 8K_\star d(\log \log d + 11) = \widetilde{O}(d\log (\lvert \cA \rvert /\delta))\), and the large-\(B\) regime, where \(B\) exceeds this threshold (see Line [line:threshold] of Algorithm 2 for the definition of \(K_\star\)). In the small-\(B\) regime, the pre-processing is safely bypassed and only Step 3 (phased elimination) is executed with the initial active set \(\cA_1 = \cA\) (analyzed in Appendix 10.1). In the large-\(B\) regime, Steps 1 and 2 (safe arm identification and a warm start epoch) are run first to produce a “warm-started” active set \(\cA_1 \subseteq \cA\) before proceeding to Step 3 (analyzed in Appendix 10.2). The main difference between the two regimes is the worst-case suboptimality gap available at the first epoch of Step 3: a trivial \(O(1)\) bound in the small-\(B\) case versus the refined \(O(\sigma\sqrt{d/B})\) guarantee from the warm start in the large-\(B\) case.

10.1 Small-\(B\) Regime: Step 3 as a Standalone Algorithm↩︎

In the small \(B\) regime where \(B < 8K_\star d(\log \log d + 11) = \widetilde{O}(d \log (\lvert \cA \rvert /\delta))\), Algorithm 2 skips Steps 1 and 2 and directly runs the phased elimination algorithm (Step 3) starting with \(\cA_1 = \cA\). We first establish the shared technical machinery for the phased elimination (sample complexity, good event, confidence width, and arm elimination), which applies to both regimes. We then derive the small-\(B\) regret bound. The large-\(B\) analysis in Appendix 10.2 reuses most of these lemmas unchanged, differing only in the first-epoch suboptimality gap.

Throughout this section, let \(\sigma' = \frac{\sigma}{\sqrt{B}}\) and \(\eps_h = 2^{-h}\sigma'\) as defined in Line [algline:poly95eps95h] of Algorithm 2. We invoke Corollary 5 with the full-batch effective standard deviation \(\sigma' = \frac{\sigma}{\sqrt{B}}\); each query corresponds to \(B\) raw arm pulls. The resulting guarantees from ?? are: \[\label{eq:subroutine95constants95poly} \Var(\hat{Y}) \le \frac{C_V \sigma'^2\log_2 T}{n_{\mathrm{q}}}, \qquad \lvert\mathrm{Bias}(\hat{Y})\rvert \le \frac{3\sigma'}{T^2},\tag{18}\] where \(n_{\mathrm{q}}\) denotes the number of queries (i.e., the number of raw samples divided by \(B\)) and \(C_V \ge 48\) is the variance constant from Corollary 5. The bias bound is independent of \(n_{\mathrm{q}}\) and the epoch index \(h\).

10.1.1 Sample Complexity per Epoch↩︎

10.1.1.1 Localization cost.

By the same argument as in Appendix 9.1, with failure probability \(\delta_{\mathrm{loc}} = \frac{\delta}{6 S_{\max} H}\) in place of \(\frac{\delta}{2 S_{\max} H}\), the total localization cost over all support arms satisfies \[\label{eq:poly95mloc} m_{{\rm loc},h} \;\le\; C_{\mathrm{loc}} \cdot S_{\max} \cdot B\!\left( \frac{1}{2}\log\frac{B}{\sigma^2} + \log\frac{6 S_{\max} H}{\delta} \right) \;=\; \widetilde{O}\!\left(dB\log\Big(\frac{1}{\delta}\Big)\right).\tag{19}\] As in Appendix 9, the \(\log\frac{1}{\sigma}\) term is absorbed into the \(\widetilde{O}(\cdot)\) notation since we assume \(\sigma = \Theta(1)\).

10.1.1.2 Refinement cost.

We bound the “true” refinement budget by summing the per-arm allocations \(u_h(a)\) from Line [algline:poly95uh95a] over the support and multiplying by \(K\) blocks. Using \(\lceil x\rceil \le x+1\) and \(\lvert\supp(\rho_h)\rvert = \widetilde{O}(d)\), we bound the number of arm pulls used for refinement in an epoch by \[\label{eq:A-dependent95mref95bound} \begin{align} m_{\mathrm{ref},h} &=K\sum_{a\in\supp(\rho_h)} u_h(a) \\ &\le KB \sum_{a\in\supp(\rho_h)} \left( 32C_V \cdot d \cdot \log_2 T \cdot 4^h \cdot \rho_h(a) + 48 \log_2 T + 1 \right) \\ &= O(dBK \cdot \log T \cdot \log\log d \cdot 4^h), \end{align}\tag{20}\]

The localization floor \(\widetilde{O}(dB\log(1/\delta))\) is present at every epoch, while the refinement term \(\widetilde{O}(dBK\cdot 4^h)\) grows geometrically and thus the largest \(h\) value is the dominant one.

10.1.2 High-Probability Good Event↩︎

Define \(H\) as the final epoch and the good event \(\cE_3 = \cE_{3,\mathrm{loc}} \cap \cE_{3,\mathrm{ref}}\), where \[\begin{align} \cE_{3,\mathrm{loc}} &\mathrel{\vcenter{:}}= \bigcap_{h=1}^{H}\bigcap_{a\in\supp(\rho_h)} \left\{ \mu_a \in [L_a,U_a] \;\text{ and }\; U_a - L_a \le \tfrac{8\sigma}{\sqrt{B}} \right\}, \\[4pt] \cE_{3,\mathrm{ref}} &\mathrel{\vcenter{:}}= \bigcap_{h=1}^{H}\bigcap_{b\in\cA_h} \left\{ \left|\hat{\mu}_{b,h} - \mu_b\right| \le \varepsilon_h \right\}. \end{align}\]

10.1.3 Confidence Width and Arm Elimination↩︎

Based on \(\cE_{3,\mathrm{ref}} \supseteq \cE_{3}\) in the good event, we immediately have the following guarantee on the confidence width.

10.1.4 Regret Bound for the Small-\(B\) Regime↩︎

In the small-\(B\) regime, \(B = \widetilde{O}(d \log (\lvert \cA \rvert /\delta))\) implies \(dB =\widetilde{O} (d^{3/2}\sqrt{B \log (\lvert \cA \rvert/\delta)})\), and so the first term in 25 scales as \(d^{3/2}\sqrt{B}\log^{\frac{3}{2}}(\lvert \cA \rvert /\delta)\) up to logarithmic factors, meaning the regret is upper bounded by \[R_T = \widetilde{O}\left( d^{3/2}\sqrt{B} \log^{\frac{3}{2}}\Big(\frac{\lvert\cA\rvert}{ \delta}\Big) + \sqrt{dT\log\Big(\frac{\lvert\cA\rvert}{\delta}}\Big) \right).\]

10.2 Regret Bounds for Large \(B\)↩︎

We first explain why Theorem 5 is insufficient for large \(B\). The first-epoch regret \(\widetilde{O}(dBK)\) in that theorem arises from the trivial gap bound \(\Delta_b \le 2\): without prior information, no tighter bound is available at epoch \(1\). When \(B \gg d\), this is wasteful because the \(dBK\) term dominates both the communication bottleneck \(\Omega(B\log\lvert \cA \rvert)\) and the standard linear bandit term \(\Omega(\sqrt{dT\log\lvert \cA \rvert})\). A key observation towards improving this is that when \(B \gg d\), a single batch is large enough to run a full experimental design within the batch.

Specifically, the first two steps of Algorithm 2 address this by prepending two pre-processing stages before the main phased elimination loop. Step 1 identifies a safe arm \(a_{\mathrm{safe}}\) with suboptimality gap \(\widetilde{O}(\sqrt{d/B})\). Step 2 uses \(a_{\mathrm{safe}}\) to run a warm-start epoch that filters the initial active set down to \(\cA_1 \subseteq \cA\) with \(\Delta_b = O(\sqrt{d/B})\) for all \(b \in \cA_1\). With this tighter first-epoch gap bound, the first-epoch regret shrinks from \(\widetilde{O}(dBK)\) to an improved term of \(\widetilde{O}(d^{3/2}\sqrt{B}K)\).

We now present the pseudocode for each pre-processing stage, followed by its regret analysis. Throughout, we assume \(B \ge 8K_\star d(\log\log d + 11)\), where \(K_\star = \lceil 8\log(3\lvert \cA \rvert\lceil\log_2\lvert \cA \rvert\rceil/\delta)\rceil\).

10.2.1 Step 1: Safe Arm Identification↩︎

Algorithm 3 runs \(\lceil\log_2\lvert \cA \rvert\rceil\) rounds of tournament-style bisection. In each round, the active set is split in two, both halves are evaluated via a \(G\)-optimal design using the unquantized sample means available within a single batch, and the half with the higher estimated maximum is retained. After \(\lceil\log_2\lvert \cA \rvert\rceil\) rounds, a single arm remains.

Regret of Step 1. Algorithm 3 pulls each arm at most \(B\) times per round over \(\lceil\log_2\lvert \cA \rvert\rceil\) rounds, so the total arm pulls are at most \(B\lceil\log_2\lvert \cA \rvert\rceil\). Since the instantaneous regrets is at most \(2\), the regret contribution \(R_{\mathrm{safe}}\) in this part satisfies \[R_{\mathrm{safe}} \le 2B\lceil\log_2\lvert \cA \rvert\rceil = O(B\log\lvert \cA \rvert).\]

Guarantee of Step 1. The following lemma, proved in Appendix 10.3.1, bounds the suboptimality of the returned arm.

10.2.2 Step 2: Warm Start↩︎

Algorithm 4 runs a single epoch of phased elimination with a key twist: in every batch, \(a_{\mathrm{safe}}\) fills all slots not needed by a core-set arm. This means core-set arms are pulled only \(u_0(a) = \lceil B\rho_0(a)\rceil \le B\) times per batch, while \(a_{\mathrm{safe}}\) absorbs the remaining \(B - u_0(a)\) pulls. The effective standard deviation for estimating \(\mu_a\) is therefore \(\sigma/\sqrt{u_0(a)}\) rather than \(\sigma/\sqrt{B}\), which is the key difference from the main phased elimination loop. Arms whose estimated gap exceeds \(8\sigma\sqrt{2d/B}\) are eliminated, producing the warm-started active set \(\cA_1\).

Regret of Step 2. The warm-start regret has three components: localization, refinement, and safe arm pulls. Since \(B \ge 8K_\star d(\log\log d + 11) \ge 2S_{\max} \ge |\supp(\rho_0)|\) by assumption and 3 , and \(\lceil x\rceil \le x +1\), we have \[\sum_{a\in\supp(\rho_0)} u_{0}(a) \le \sum_{a\in\supp(\rho_0)} \left(B \rho_0(a) + 1 \right) = B + |\supp(\rho_0)| \le 2B.\]

Localization. By Proposition [prop:localize] with \(\sigma' = \sigma/\sqrt{u_0(a)}\) and failure probability \(\delta_{\mathrm{loc}} = \delta/(6S_{\max})\), each invocation of \(\mathrm{\small 1BitLocalize}(a, \delta_{\mathrm{loc}}, \sigma')\) uses at most \[n_{\mathrm{loc},0}(a) = C_{\mathrm{loc}}\left(\frac{1}{2}\log\left(\frac{u_0(a)}{\sigma^2}\right) + \log\left(\frac{6S_{\max}}{\delta}\right)\right) = O\left( \log \left(\frac{dB}{\delta}\right)\right)\] queries, where we use \(u_0(a) \le B\), and \(\sigma = \Theta(1)\), and \(S_{\max} = O(d \log \log d) = \widetilde{O}(d)\). Since each query costs \(u_0(a)\) arm pulls and the regret of each pull is at most 2, summing the regret over \(\supp(\rho_0)\) yields a contribution \(R_{\mathrm{ws,loc}}\) to the regret satisfying \[\begin{align} R_{\mathrm{ws,loc}} \le 2\sum_{a\in\supp(\rho_0)} u_0(a) \cdot n_{\mathrm{loc},0}(a) = O\left(B \log\left(\frac{dB}{\delta}\right)\right). \end{align}\]

Refinement. Each block uses \(\lceil C_V\log_2 T\rceil\) queries per arm, each costing \(u_0(a)\) pulls and each pull incurs regret at most 2. Summing over \(K_0 = O(\log(\lvert \cA \rvert/\delta))\) blocks and \(\supp(\rho_0)\) yields a contribution \(R_{\mathrm{ws,ref}}\) to the regret satisfying \[R_{\mathrm{ws,ref}} \le 2K_0\sum_{a\in\supp(\rho_0)}u_0(a)\cdot\lceil C_V\log_2 T\rceil = O\left(B\log\left(\frac{\lvert \cA \rvert}{\delta}\right)\log T\right).\]

Safe arm pulls. From the above discussion, the total number of batches consumed by localization and refinement is at most \[\sum_{a \in {\supp(\rho_0)}} \left( n_{{\rm loc},0}(a) + K_0 \cdot \lceil C_V\log_2 T\rceil \right) = O\left(S_{\max} \cdot \log \Big(\frac{dB \lvert \cA \rvert }{ \delta}\Big) \cdot \log (T)\right).\] In each batch, \(a_{\mathrm{safe}}\) is pulled at most \(B\) times. Conditioned on \(\cE_1\), Lemma 13 gives \(\Delta_{a_{\mathrm{safe}}} = \widetilde{O}\Big(\log\lvert \cA \rvert\sqrt{\frac{d}{B}\log\frac{\lvert \cA \rvert}{\delta}}\Big)\), so we get a contribution \(R_{\mathrm{ws,safe}}\) to the regret satisfying \[\begin{align} R_{\mathrm{ws,safe}} \le \Delta_{a_{\mathrm{safe}}} \cdot O\left(B \cdot S_{\max} \cdot \log \Big(\frac{dB \lvert \cA \rvert }{ \delta}\Big) \cdot \log (T)\right) = \widetilde{O}\left( d^{3/2}\sqrt{B} \cdot \log^{5/2}\left(\frac{\lvert \cA \rvert}{\delta}\right) \right). \end{align}\]

Combining all three components, we obtain a total contribution \(R_{\mathrm{ws}}\) satisfying \[\label{eq:R95ws} R_{\mathrm{ws}} = R_{\mathrm{ws,loc}} + R_{\mathrm{ws,ref}} + R_{\mathrm{ws,safe}} = \widetilde{O} \left( B\log \left(\frac{\lvert \cA \rvert}{\delta}\right) + d^{3/2}\sqrt{B}\log^{5/2} \left(\frac{\lvert \cA \rvert}{\delta}\right) \right).\tag{26}\]

Guarantee of Step 2. The following lemma, proved in Appendix 10.3.2, bounds the suboptimality of every arm in \(\cA_1\).

10.2.3 Step 3: Phased Elimination and Total Regret↩︎

With a warm-started active set \(\cA_1\) in hand, the main phased elimination loop of Algorithm 2 proceeds exactly as in the small-\(B\) regime, starting from \(\cA_1\) rather than \(\cA\).

We bound the Step 3 regret conditioned on \(\cE_1 \cap \cE_2 \cap \cE_3\). Since \(a^* \in \cA_1\) by condition (ii) of \(\cE_2\), Lemma 11 continues to hold from epoch \(1\) onward.

Let \(R_{\mathrm{loc}}\) denote the contribution to the regret from localization, and let \(R_{\mathrm{ref},h}\) denote the contribution from refinement in epoch \(h\). For all epochs \(h \ge 1\), since \(\cA_h \subseteq \cA_1\), condition (i) of \(\cE_2\) guarantees that \(\Delta_b \le 16\sigma\sqrt{2d/B}\) for all active arms. Therefore, the total localization regret across all \(H\) epochs is bounded by \[\label{eq:new95R95loc} R_{\mathrm{loc}} \le 16\sigma\sqrt{\frac{2d}{B}} \sum_{h=1}^H m_{\mathrm{loc}, h} = \widetilde{O}\left(\sqrt{\frac{d}{B}} \cdot dB\right) = \widetilde{O}\left(d^{3/2}\sqrt{B}\right),\tag{27}\] where we used the localization cost bound \(\sum_h m_{\mathrm{loc},h} = \widetilde{O}(dB)\) from 22 and \(\sigma = \Theta(1)\). For the refinement regret in the first epoch (\(h = 1\)), we similarly use the warm-start gap bound: \[\label{eq:new95R195ref} R_{\mathrm{ref}, 1} \le 16\sigma\sqrt{\frac{2d}{B}} \cdot m_{\mathrm{ref}, 1} = \widetilde{O}\!\left(d^{3/2}\sqrt{B}\,K\right),\tag{28}\] where we used 20 . For epochs \(h \ge 2\), since \(a^* \in \cA_1\), Lemma 12 applies and the argument is identical to that of Theorem 5 from epoch 2 onward, giving \(\sum_{h=2}^H R_{\mathrm{ref},h} = \widetilde{O}(\sqrt{KdT})\). Adding the localization and refinement components and substituting \(K = \widetilde{O}(\log(\lvert \cA \rvert/\delta))\), the total regret \(R_{\mathrm{phased}}\) from the phased elimination part satisfies \[\label{eq:R95pe} R_{\mathrm{phased}} = R_{\mathrm{loc}} + R_{\mathrm{ref}, 1} + \sum_{h=2}^H R_{\mathrm{ref},h} = \widetilde{O}\!\left( d^{3/2}\sqrt{B}\log\!\Big(\frac{\lvert \cA \rvert}{\delta}\Big) + \sqrt{dT\log\!\Big(\frac{\lvert \cA \rvert}{\delta}\Big)} \right).\tag{29}\]

Total Regret. Combining \(R_{\mathrm{safe}}\), \(R_{\mathrm{ws}}\), and \(R_{\mathrm{phased}}\), conditioned on \(\cE_1 \cap \cE_2 \cap \cE_3\), \[R_T = \widetilde{O}\!\left( B\log\!\Big(\frac{\lvert \cA \rvert}{\delta}\Big) + d^{3/2}\sqrt{B}\log^{5/2}\!\Big(\frac{\lvert \cA \rvert}{\delta}\Big) + \sqrt{dT\log\!\Big(\frac{\lvert \cA \rvert}{\delta}\Big)} \right).\] It remains to show that \(\cE_1 \cap \cE_2 \cap \cE_3\) holds with probability at least \(1-\delta\). We have \(\mathbb{P}(\cE_1) \ge 1-\delta/3\) and \(\mathbb{P}(\cE_2 \mid \cE_1) \ge 1-\delta/3\) by Lemmas 13 and 14 respectively. For the third factor, we note that Steps 1, 2, and 3 use entirely disjoint sets of arm pulls. Hence, for any fixed realization of \(\cE_1 \cap \cE_2\), which depends only on the arm pulls of Steps 1 and 2, the arm pulls of Step 3 remain independent and their joint distribution is unchanged. The proof of Lemma 9 therefore applies similarly, conditionally on any such realization, giving \(\mathbb{P}(\cE_3 \mid \cE_1 \cap \cE_2) \ge 1-\delta/3\). Combining the three bounds, we obtain \[\mathbb{P}(\cE_1 \cap \cE_2 \cap \cE_3) = \mathbb{P}(\cE_1)\, \mathbb{P}(\cE_2 \mid \cE_1)\, \mathbb{P}(\cE_3 \mid \cE_1 \cap \cE_2) \ge \Big(1-\frac{\delta}{3}\Big)^3 \ge 1-\delta\] as desired.

10.3 Proofs of Auxiliary Lemmas↩︎

We now prove Lemmas 13 and 14, which establish the guarantees of Algorithms 3 and 4 respectively.

10.3.1 Proof of Lemma 13 (Safe Arm Guarantees)↩︎

Feasibility of arm pulls per batch. Set \(m_\star = B/(2K_\star)\). Since \[u_h(a) = \lceil B\rho_h(a)/(2K_\star)\rceil \le m_\star\rho_h(a) + 1,\] we have \[K_\star\sum_{a\in\supp(\rho_h)} u_h(a) \le K_\star(m_\star + |\supp(\rho_h)|) \le \frac{B}{2} + 4K_\star d(\log\log d + 11) \le B,\] using \(|\supp(\rho_h)| \le S_{\max}\) and the assumption on \(B\). Any remaining slots are filled by an arbitrary arm whose rewards are ignored by the agent.

Concentration of arm estimates. Fix a round \(h\) and let \(\mathcal{F}_{h-1}\) be the \(\sigma\)-algebra of all randomness before round \(h\). We condition on an arbitrary fixed realization of \(\mathcal{F}_{h-1}\), making \(\cA_h\), \(\rho_h\), and \(\{u_h(a)\}\) deterministic. Since each block \(j\) uses fresh arm pulls with the same fixed protocol, the \(K_\star\) block estimates \(b^\top\hat{\theta}_h^{(1)},\ldots,b^\top\hat{\theta}_h^{(K_\star)}\) are i.i.d.for any fixed \(b \in \cA_h\).

Because \(\bar{Y}_{a,h}^{(j)}\) is the sample mean of \(u_h(a)\) independent rewards, \(\mathbb{E}[\bar{Y}_{a,h}^{(j)}] = \mu_a\) and \(\mathrm{Var}(\bar{Y}_{a,h}^{(j)}) \le \sigma^2/u_h(a)\). Since \(\mathbb{E}[b^\top\hat{\theta}_h^{(j)}] = \mu_b\) (no bias), the variance of the block estimate satisfies \[\begin{align} \mathrm{Var}(b^\top\hat{\theta}_h^{(j)}) &= \sum_{a\in\supp(\rho_h)} (b^\top G_h^{-1}a)^2\rho_h(a)^2 \cdot\frac{\sigma^2}{u_h(a)} \le \frac{\sigma^2}{m_\star} \sum_{a\in\supp(\rho_h)} (b^\top G_h^{-1}a)^2\rho_h(a) \le \frac{2d\sigma^2}{m_\star}, \end{align}\] using \(u_h(a) = \lceil m_\star\rho_h(a) \rceil \ge m_\star\rho_h(a)\) and Lemma 2.

Applying Lemma 1 to the \(K_\star\) i.i.d.block estimates with variance at most \(2d\sigma^2/m_\star\), using failure probability \(\delta/(3\lvert \cA \rvert\lceil\log_2\lvert \cA \rvert\rceil)\) and substituting \(K_\star m_\star = B/2\), we have \[|\hat{\mu}_{b,h} - \mu_b| \le \sqrt{\frac{64d\sigma^2}{K_\star m_\star} \log\!\Big(\frac{3\lvert \cA \rvert\lceil\log_2\lvert \cA \rvert\rceil}{\delta}\Big)} = 8\sigma\sqrt{\frac{2d}{B} \log\!\Big(\frac{3\lvert \cA \rvert\lceil\log_2\lvert \cA \rvert\rceil}{\delta}\Big)} \eqqcolon \epsilon_{\mathrm{safe}},\] with probability at least \(1 - \delta/(3\lvert \cA \rvert\lceil\log_2\lvert \cA \rvert\rceil)\) under our conditioning. Since \(\cA_h \subseteq \cA\) deterministically and the bound holds for every fixed \(b \in \cA_h\), a union bound over all \(b \in \cA\) (which contains \(\cA_h\)) inside the conditioning gives \[\mathbb{P}\!\Big( \exists\,b\in\cA_h : |\hat{\mu}_{b,h}-\mu_b|>\epsilon_{\mathrm{safe}} \;\Big|\;\mathcal{F}_{h-1} \Big) \le \frac{\delta}{3\lceil\log_2\lvert \cA \rvert\rceil}.\] Since this holds for every fixed realization of \(\mathcal{F}_{h-1}\), the law of total expectation removes the conditioning, and a further union bound over \(h \in \{1,\ldots,\lceil\log_2\lvert \cA \rvert\rceil\}\) gives that the event \[\cE_{\mathrm{safe}} \mathrel{\vcenter{:}}= \bigcap_{h=1}^{\lceil\log_2\lvert \cA \rvert\rceil}\bigcap_{b\in\cA_h} \bigl\{|\hat{\mu}_{b,h}-\mu_b|\le\epsilon_{\mathrm{safe}}\bigr\}\] holds with probability at least \(1-\delta/3\).

Suboptimality gap of the safe arm. We condition on \(\cE_{\mathrm{safe}}\). In round \(h\), let \(a_h^* = \arg\max_{a\in\cA_h}\mu_a\). If the group containing \(a_h^*\) is eliminated, there exists \(b\) in the retained group with \(\hat{\mu}_{b,h} \ge \hat{\mu}_{a_h^*,h}\), so \[\mu_b \ge \hat{\mu}_{b,h} - \epsilon_{\mathrm{safe}} \ge \hat{\mu}_{a_h^*,h} - \epsilon_{\mathrm{safe}} \ge \mu_{a_h^*} - 2\epsilon_{\mathrm{safe}}.\] Hence \(\mu_{a_{h+1}^*} \ge \mu_{a_h^*} - 2\epsilon_{\mathrm{safe}}\), and induction from \(\mu_{a_1^*} = \mu_{a^*}\) yields \(\mu_{a_{h+1}^*} \ge \mu_{a^*} - 2h\,\epsilon_{\mathrm{safe}}\). In other words, \(\Delta_{a_{h+1}^*} \le 2h\,\epsilon_{\mathrm{safe}}\). After the final round \(h = \lceil\log_2\lvert \cA \rvert\rceil\), the active set \(\cA_{\lceil\log_2\lvert \cA \rvert\rceil + 1}\) contains only a single arm \(a_{\mathrm{safe}}\), i.e., \(a_{\mathrm{safe}} = a_{\lceil\log_2\lvert \cA \rvert\rceil + 1}^*\). Applying the induction bound at \(h = \lceil\log_2\lvert \cA \rvert\rceil\) gives \(\Delta_{a_{\mathrm{safe}}} \le 2\lceil\log_2\lvert \cA \rvert\rceil\,\epsilon_{\mathrm{safe}}\). Substituting \(\epsilon_{\mathrm{safe}}\) yields ?? , i.e., event \(\cE_1\) holds. It follows that \(\mathbb{P}(\cE_1) \ge \mathbb{P}(\cE_{\mathrm{safe}}) \ge 1-\delta/3\).

10.3.2 Proof of Lemma 14 (Warm Start Guarantees)↩︎

Since Algorithm 4 uses arm pulls entirely disjoint from those of Algorithm 3, all concentration bounds below are independent of \(\cE_1\), and hold with the stated unconditional probabilities conditionally on any fixed value of \(a_{\mathrm{safe}}\). We prove \(\mathbb{P}(\cE_2 \mid \cE_1) \ge 1-\delta/3\) by establishing an event of the form \(\cE_{\mathrm{ws}} \mathrel{\vcenter{:}}= \cE_{\mathrm{ws,loc}} \cap \cE_{\mathrm{ws,ref}}\) (see below for the definitions), from which both conditions of \(\cE_2\) follow.

Part 1: Localization event \(\cE_{\mathrm{ws,loc}}\). For each \(a \in \supp(\rho_0)\), 1BitLocalize is called with effective standard deviation \(\sigma' = \sigma/\sqrt{u_0(a)}\) and failure probability \(\delta/(6S_{\max})\). Since \(|\supp(\rho_0)| \le S_{\max}\), Proposition [prop:localize] and a union bound give that \[\label{eq:E95ws95loc} \cE_{\mathrm{ws,loc}} \mathrel{\vcenter{:}}= \bigcap_{a\in\supp(\rho_0)}\!\! \Bigl\{ \mu_a \in [L_a,U_a] \;\text{ and }\; U_a-L_a \le \tfrac{8\sigma}{\sqrt{u_0(a)}} \Bigr\}\tag{30}\] holds with probability at least \(1-\delta/6\).

Part 2: Refinement event \(\cE_{\mathrm{ws,ref}}\). We condition on fixed intervals satisfying \(\cE_{\mathrm{ws,loc}}\), which makes them valid for 1BitRefine. Since each block \(j\) uses independent arm pulls with the same fixed parameters, the \(K_0\) estimates \(b^\top\hat{\theta}_0^{(1)},\ldots,b^\top\hat{\theta}_0^{(K_0)}\) are i.i.d. for any fixed \(b \in \cA\). We bound their variance and bias as follows:

• Variance. Each call to 1BitRefine for arm \(a\) uses \(n_{\mathrm{q}} = \lceil C_V\log_2 T\rceil\) queries. Because arm \(a\) is pulled only \(u_0(a)\) times per query (with the rest of the batch padded by \(a_{\mathrm{safe}}\)), the effective standard deviation is \(\sigma' = \sigma/\sqrt{u_0(a)}\). Applying the bound from Corollary 5 yields \[\mathrm{Var}(\hat{Y}_{a,0}^{(j)}) \le \frac{C_V (\sigma')^2 \log_2 T}{n_{\mathrm{q}}} \le \frac{C_V (\sigma^2 / u_0(a)) \log_2 T}{C_V \log_2 T} = \frac{\sigma^2}{u_0(a)}.\] Combining this with \(u_0(a) \ge B\rho_0(a)\) and Lemma 2, we obtain \[\mathrm{Var}(b^\top\hat{\theta}_0^{(j)}) = \sum_{a} (b^\top G_0^{-1}a)^2\rho_0(a)^2 \cdot\mathrm{Var}(\hat{Y}_{a,0}^{(j)}) \le \frac{\sigma^2}{B} \sum_{a} (b^\top G_0^{-1}a)^2\rho_0(a) \le \frac{2d\sigma^2}{B}.\]

• Bias. Corollary 5 gives \(|\mathrm{Bias}(\hat{Y}_{a,0}^{(j)})| \le 3\sigma/(T^2\sqrt{u_0(a)}) \le 3\sigma/T^2\). By writing \(\mu_b = b^\top G_0^{-1} G_0\theta\) and using the triangle inequality alongside Corollary 4, we obtain \[|\mathbb{E}[b^\top\hat{\theta}_0^{(j)}] - \mu_b| \le \frac{3\sigma}{T^2} \sum_{a\in\supp(\rho_0)}\rho_0(a)|b^\top G_0^{-1}a| \le \frac{3\sqrt{2d}\,\sigma}{T^2} \le 2\sigma\sqrt{\frac{2d}{B}},\] where the last step uses \(T \ge B\) and \(B \ge 4d(\log\log d+11) \ge 4\), giving \(T^2 \ge B^2 \ge 4B \ge \frac{3}{2}\sqrt{B}\).

Applying Lemma 1 to the \(K_0\) i.i.d.block estimates with variance at most \(2d\sigma^2/B\) and failure probability \(\delta/(6\lvert \cA \rvert)\), then combining with the bias bound via the triangle inequality, we obtain \[|\hat{\mu}_{b,0} - \mu_b| \le \sqrt{\frac{64d\sigma^2}{BK_0} \log\!\Big(\frac{6\lvert \cA \rvert}{\delta}\Big)} + 2\sigma\sqrt{\frac{2d}{B}} \le 4\sigma\sqrt{\frac{2d}{B}},\] with probability at least \(1-\delta/(6\lvert \cA \rvert)\) under our conditioning, where the last step uses \(K_0 = \lceil 8\log(6\lvert \cA \rvert/\delta)\rceil\). Since \(\cA\) is a fixed non-random set, a union bound over all \(b \in \cA\) inside the conditional measure gives \[\mathbb{P}\!\Big( \exists\,b\in\cA : |\hat{\mu}_{b,0}-\mu_b| > 4\sigma\sqrt{2d/B} \;\Big|\;\cE_{\mathrm{ws,loc}} \Big) \le \frac{\delta}{6},\] so the event \[\cE_{\mathrm{ws,ref}} \mathrel{\vcenter{:}}= \bigcap_{b\in\cA}\left\{|\hat{\mu}_{b,0}-\mu_b| \le 4\sigma\sqrt{\frac{2d}{B}} \right\}\] satisfies \(\mathbb{P}(\cE_{\mathrm{ws,ref}}^c \mid \cE_{\mathrm{ws,loc}}) \le \delta/6\).

Part 3: Optimality of retained arms. Conditioned on \(\cE_{\mathrm{ws}} = \cE_{\mathrm{ws,loc}} \cap \cE_{\mathrm{ws,ref}}\), we have \(|\hat{\mu}_{b,0}-\mu_b| \le 4\sigma\sqrt{2d/B}\) for all \(b \in \cA\). We then have the following two conditions.

Condition (i): Gap bound. For any \(a \in \cA_1\), the elimination rule (see Line [algline:warm95start95elim95rule]) gives \[\hat{\mu}_{a^*,0} - \hat{\mu}_{a,0} \le 8\sigma\sqrt{2d/B}.\] Combining this with standard decomposition and the estimation error guarantee under \(\cE_{\mathrm{ws,ref}}\) yields \[\Delta_a = \mu_{a^*} - \mu_a \le \underbrace{(\mu_{a^*} - \hat{\mu}_{a^*,0})}_{\le 4\sigma\sqrt{2d/B} \text{ under } \cE_{\mathrm{ws,ref}}} + (\hat{\mu}_{a^*,0} - \hat{\mu}_{a,0}) + \underbrace{(\hat{\mu}_{a,0} - \mu_a)}_{\le 4\sigma\sqrt{2d/B} \text{ under } \cE_{\mathrm{ws,ref}}} \le 16\sigma\sqrt{\frac{2d}{B}}.\]

Condition (ii): Optimal arm retained. If \(a^* \notin \cA_1\), some \(b\) satisfies \(\hat{\mu}_{b,0} - \hat{\mu}_{a^*,0} > 8\sigma\sqrt{2d/B}\), which gives \(\mu_b - \mu_{a^*} > 8\sigma\sqrt{2d/B} - 2\cdot 4\sigma\sqrt{2d/B} = 0\), contradicting the optimality of \(a^*\). Thus, it must hold that \(a^* \in \cA_1\).

Part 4: Conclusion. Since WarmStart uses arm pulls independent of SafeArm, the probabilities of \(\cE_{\mathrm{ws,loc}}\) and \(\cE_{\mathrm{ws,ref}}\) are unchanged conditionally on \(\cE_1\). Therefore, \[\mathbb{P}(\cE_2 \mid \cE_1) \ge \mathbb{P}(\cE_{\mathrm{ws}} \mid \cE_1) = \mathbb{P}(\cE_{\mathrm{ws,ref}} \mid \cE_1\cap\cE_{\mathrm{ws,loc}}) \mathbb{P}(\cE_{\mathrm{ws,loc}} \mid \cE_1) \ge \Big(1-\frac{\delta}{6}\Big)^2 \ge 1-\frac{\delta}{3}.\]

10.4 Proof of Corollary 3 (Gap to The Lower Bound)↩︎

In this section, we provide the analysis for Corollary 3. This establishes that the expected regret upper bound of Corollary 2 is order-optimal up to \(\mathrm{polylog}(d, T)\) factors provided that either \(B = \Omega(d^3)\) or \(T = \Omega(d^2 B)\). Furthermore, in all remaining regimes, we show that it is suboptimal by at most an \(\widetilde{O}(\sqrt{d})\) factor compared to the lower bound \(\mathrm{LB}(B,T,d) = \Omega(B+\sqrt{dT})\) implied by Corollary 1 for \(|\mathcal{A}|=\mathrm{poly}(d)\). Note that throughout we slightly abuse the \(\widetilde{O}(\cdot)\) notation to include \({\rm polylog}(d,T)\) factors, even when they do not appear in the argument.

We first recall the simplified expected regret bound of Corollary 2, under the assumptions that \(|\mathcal{A}|=\mathrm{poly}(d)\) and \(\sigma = \Theta(1)\): \[\mathbb{E}[R_T] = \widetilde{O}\left(B + d^{3/2}\sqrt{B} + \sqrt{dT}\right).\] We first observe that the middle term is dominated by the first or last whenever \[B = \Omega(d^3) \implies d^{3/2} = O(\sqrt{B}) \implies \mathbb{E}[R_T] = \widetilde{O}(B + \sqrt{dT}),\] or \[T = \Omega(d^2B) \implies d^{3/2}\sqrt{B} = O(\sqrt{dT}) \implies \mathbb{E}[R_T] = \widetilde{O}(B + \sqrt{dT}).\]

We now bound the general suboptimality by \(\widetilde{O}(\sqrt{d})\) by considering two different regimes for \(T\).

10.4.0.1 Case 1: \(T = \Omega(dB)\).

The assumption \(T = \Omega(dB)\) implies \(\sqrt{dB} = O(\sqrt{T})\), and thus \(d^{\frac{3}{2}} \sqrt B \le O(d \sqrt{T})\). It follows that the ratio to the lower bound satisfies \[\frac{\mathbb{E}[R_T]}{\mathrm{LB}(B,T,d)} = \widetilde{O}\!\left(\frac{B + d\sqrt{T} + \sqrt{dT}}{B + \sqrt{dT}}\right) = \widetilde{O}(\sqrt{d}).\]

10.4.0.2 Case 2: \(T = O(dB)\).

We can further split the case \(T = O(dB)\) into two smaller sub-cases: \(T = O(B \log d)\), and \(T = \Omega(B \log d)\). In each case, we analyze the regret accumulated by Algorithm 2 up to early termination.

First, if \(T = O(B \log d)\), the regret is trivially bounded by \(2T = O(B \log d)\), yielding \[\frac{\mathbb{E}[R_T]}{\mathrm{LB}(B,T,d)} \le O\left(\frac{T}{B + \sqrt{dT}}\right) \leq O\left(\frac{T}{B} \right) = O(\log d).\]

For the regime where \(T = \Omega(B \log d)\) and \(T = O(dB)\), we split the analysis into two cases: (i) the pre-processing steps in Algorithm 2 are not performed; and (ii) the pre-processing steps in Algorithm 2 are performed. For case (i), Line [algline:tau] of Algorithm 2 implies that \(B = \widetilde{O}(d)\). Using this and the trivial bound \(\mathbb{E}[R_T] \le 2T\), we have \[\frac{\mathbb{E}[R_T]}{\mathrm{LB}(B,T,d)} \le O\!\left(\frac{T}{B + \sqrt{dT}}\right) \le O\!\left(\frac{T}{\sqrt{dT}}\right) = O\!\left(\sqrt{\frac{T}{d}}\right) = O\!\left(\sqrt{B}\right) = \widetilde{O}(\sqrt{d}),\] where the last two steps follow from \(T = O(dB)\) and \(B = \widetilde{O}(d)\).

For case (ii), we may assume that there are sufficiently many arm pulls for the SafeArm subroutine to complete (otherwise we are in the \(T = O(B\log d)\) sub-case already handled above). By Lemma 13 with \(\delta = 1/T\), the returned arm satisfies \(\Delta_{a_{\mathrm{safe}}} = \widetilde{O}(\sqrt{d/B})\) with probability at least \(1 - 1/(3T)\); on the complementary failure event (probability at most \(1/(3T)\)), \(\Delta_{a_{\mathrm{safe}}} \le 2\) since all mean rewards are bounded. Hence \[\mathbb{E}[\Delta_{a_{\mathrm{safe}}}] \le \widetilde{O}\left(\sqrt{\frac{d}{B}}\right) + 2 \cdot \frac{1}{3T} = \widetilde{O}\left(\sqrt{\frac{d}{B}} +\frac{1}{T}\right).\] During the subsequent WarmStart epoch, the core-set arms are pulled at most \(\widetilde{O}(B)\) times in total while \(a_{\mathrm{safe}}\) fills all remaining slots. Thus, even if the algorithm terminates midway through this epoch, the total expected regret incurred is bounded by \(\widetilde{O}(B)\) (for the safe arm identification and core set pulls) plus the regret from pulling \(a_{\mathrm{safe}}\) up to \(T\) times: \[\mathbb{E}[R_T] \le \widetilde{O}(B) + T\cdot\mathbb{E}[\Delta_{a_{\mathrm{safe}}}] = \widetilde{O}\left(B + T\sqrt{\frac{d}{B}} + 1\right) = \widetilde{O}\left(B + T\sqrt{\frac{d}{B}}\right).\] We can rewrite the second term as \(T\sqrt{\frac{d}{B}} = \sqrt{\frac{T}{B}} \cdot \sqrt{dT}\). Because we are in the regime where \(T = O(dB)\), it follows that \(\frac{T}{B} = O(d)\), and therefore \(\sqrt{\frac{T}{B}} = O(\sqrt{d})\). Substituting this into the ratio yields \[\frac{\mathbb{E}[R_T]}{\mathrm{LB}(B, T, d)} \le \widetilde{O} \left(\frac{B+ \sqrt{\frac{T}{B}} \cdot \sqrt{dT} }{B+\sqrt{dT}} \right) = \widetilde{O} \left(\frac{B+ \sqrt{d} \cdot \sqrt{dT} }{B+\sqrt{dT}} \right) = \widetilde{O}(\sqrt{d}).\] This completes the proof of Corollary 3.

References↩︎

---

1. They also allow multiple distributed agents, but we are mainly interested in the special case of a single agent.↩︎

2. We refer to the “uplink communication cost” as the number of bits communicated by the agent to the central learner in a given time step.↩︎

3. Theorem 2 will reveal that any strategy doing so must be highly suboptimal in regimes of smaller \(\lvert \cA \rvert\).↩︎

4. Although we formally assume \(\cA\) is finite to cleanly maintain active sets and compute experimental designs, the regret bounds attained by our \(\lvert \cA \rvert\)-independent algorithm (Theorem 3) also hold for arbitrary compact sets with possibly infinite cardinality via a standard covering argument; see Remark [rem:infinite95sets] for details.↩︎

5. By defining the action set such that \(\max_{a \in \cA} \|a\|_2 \le 1\) and allowing the adversary to pick any \(\theta\) such that \(\|\theta\|_2 \le 1\), the mean reward satisfies \(|\langle a, \theta \rangle| \le \|a\|_2 \|\theta\|_2 \le 1\) by the Cauchy-Schwarz inequality.↩︎

6. The first two terms can be tightened to \(\min\{B\log(|\cA|/\delta) + d^{3/2}\sqrt{B}\log^{5/2}(|\cA|/\delta),\, dB\log(|\cA|/\delta)\}\) by taking the better of the small-\(B\) and large-\(B\) analyses, see Theorem 5 in Appendix 10.↩︎

7. When referring to the number of median-of-means blocks, we slightly abuse notation throughout and hide \({\rm poly}(\log T)\) factors in the \(\widetilde{O}(\cdot)\) notation for ease of presentation.↩︎

8. For ease of presentation, we assume \(\sigma'\) is strictly less than 1 throughout, so that the \(\log(1/\sigma')\) term is non-negative. If \(\sigma' \ge 1\), we can simply skip the localization step and return \([L_a, U_a] = [-1,1]\), since \(\lvert [-1,1]\rvert \le 2\sigma'\) in this case.↩︎

9. Because our problem setup permits any arbitrary 1-bit quantization function, the learner is not strictly restricted to using simple threshold queries. In practice, one could halve the required query complexity by directly employing interval queries considered in [50] (i.e., querying \(\mathbb{1}\{a_i \le X' < T_i\}\) and \(\mathbb{1}\{T_i \le X' < b_i\}\)) rather than querying individual thresholds and subtracting their empirical estimates.↩︎