1 INTRODUCTION↩︎

Consider a hiring platform seeking to hire the optimal candidate from a pool of \(K\) applicants within a limited budget of \(T\) interview rounds. Each candidate \(i\) is inherently characterized by a true background profile, represented as a feature vector \(x_{i} \in \mathbb{R}^d\). The platform evaluates these candidates based on a unified criterion modeled by an unknown latent vector \(\theta^*\), and the true underlying score of candidate \(i\) is represented by the inner product \(\langle \theta^*, x_i \rangle\). At each round, the platform selects one candidate to interview, and obtains a noisy evaluation of that candidate. In this setting, candidates act as self-interested agents whose primary objective is to maximize their probability of being selected as the final hire. To achieve this, they may strategically manipulate their submitted profiles, presenting a falsified feature vector \(x_{t,i} \neq x_i\) to increase their chances of being selected for interview at any round \(t\). However, once selected, their actual performance depends on their true profile \(x_i\) rather than the reported feature \(x_{t,i}\). Consequently, to identify the optimal candidate, the platform must judiciously select interviewees at each round, taking into account noisy evaluations and strategic profile manipulation.

To address such challenge for hiring platforms, we formalize the problem as a fixed-budget Best Arm Identification (BAI) task in strategic linear bandits. The learner’s goal is to identify the optimal candidate within a limited budget of \(T\) interview rounds. While state-of-the-art (SOTA) linear BAI algorithms have achieved minimax-optimal performance in classical linear bandits [1], they are fundamentally vulnerable to arms’ strategic behavior. Specifically, these current SOTA methods rely on optimal design (OD)-based sampling rules such as \(G\)-optimal design and \(\mathcal{XY}\)-allocation [2]; however, we show in this work that such algorithm design allows self-interested arms to manipulate the sampling allocation by misreporting their features, which can lead to the failure of BAI. Recent work has begun to explore the intersection of reinforcement learning and mechanism design. For instance, [3] proposed a two-level deep RL framework that jointly trains self-interested agents and a social planner to optimize tax policy in economic simulations, and [4], [5] integrated mechanism design to to address strategic behavior in bandit problems with the objective of regret minimization. Specially the OptGTM algorithm [4] introduces a Grim Trigger Condition (GTC) to discourage arms from misreporting their features in the contextual linear bandit setting. However, OptGTM’s focus on regret minimization prevents it from efficiently identifying the best arm. Despite these existing studies, the BAI task in strategic bandits remains under-explored. To bridge this gap, we propose Mechanism-Enforced Sequential HAlving (MESHA), which integrates an epoch-wise GTC mechanism alongside a uniform sampling rule. Crucially, while prior work [4], [6] required stringent assumptions on feature reporting, by proving that the GTC inherently constrains arm behavior under a Nash Equilibrium, we establish performance guarantees for MESHA under substantially weaker and more practical assumptions.

1.1 Literature Review↩︎

Bandit literature broadly splits into two paradigms: Regret Minimization (RM) and Best-Arm Identification (BAI). First, in RM, a learner aims to maximize cumulative reward over \(T\) rounds, with regret quantifying the gap between the learner’s cumulative reward and that of an oracle always pulling the optimal arm. Second, the BAI (also called pure exploration) problem is studied under two settings: (i) in the fixed-budget setting, a learner aims to maximize the success BAI probability within a fixed budget \(T\); (ii) in the fixed-confidence setting, a learner aims to minimize the sample complexity required for BAI with a fixed confidence \(\delta\). The RM and BAI tasks necessitate fundamentally different algorithmic designs and theoretical analyses. More specifically, although both efficient RM and BAI algorithms need to carefully balance between exploitation and exploration, exploitation is more critical in achieving the optimal performance for RM, whereas exploration is more crucial for BAI [7]–[9]. To contextualize our work, we first review existing literature on RM in both stochastic and linear bandit settings. Next, we discuss BAI works across both stochastic and linear settings under fixed-confidence and fixed-budget objectives. Finally, we examine existing work on strategic bandits.

Regret Minimization. The regret minimization problem in bandits has been extensively studied [10], [11]. In the standard multi-armed bandit setting, [12] established the first instance-dependent regret lower bound, and [10] proposed the UCB1 algorithm which achieves a regret nearly-matching this lower bound.[13], [14] studied the Thompson sampling algorithms, an alternative Bayesian approach that also achieves near-optimal regret while being computationally efficient in practice [15]. Meanwhile, [16] proposed the LINREL algorithm, one of the first algorithms for stochastic linear bandits. [17] established an \(\Omega(d\sqrt{T})\) minimax lower bound on regret, and [11] proposed the OFUL algorithm, which achieves \(\tilde{O}(d\sqrt{T})\) regret and is therefore minimax optimal up to logarithmic factors. Best Arm Identification. In standard multi-armed bandits, the fixed-confidence BAI problem was studied by [18], [19], who established Median Elimination and Action Elimination algorithms with \((\varepsilon,\delta)\)-PAC guarantees via arm elimination.  [20] later derived a universal instance-dependent lower bound on the sample complexity of any algorithm and proposed the asymptotically optimal Track-and-Stop algorithm, establishing a tight characterization of the sample complexity. In the fixed-budget setting, [21] proposed and analyzed the Successive Rejects algorithm and derived a lower bound on the failure probability of any algorithm with a Bernoulli instance, while [22] proposed Sequential Halving (SH), achieving near-optimal sample complexity with an epoch-based design. Furthermore, [23] refined the analysis of SH by deriving a superior upper bound under a sufficiently large budget \(T\) and polynomially spaced arm gaps. For our comparison, we adopt the more general result of SH established in [22]. Moreover, [24], [25] provided a unified study of both the fixed-confidence and fixed-budget settings.

In linear bandits, where arms’ rewards are linear products of known feature vectors and a common, unknown latent vector, the fixed-confidence BAI problem was first studied by [2], who introduced the \(\mathcal{XY}\)-adaptive algorithm with an optimal design (OD)-based sampling strategy. Subsequently, the LinGapE algorithm proposed by [26] is with a better sample complexity guarantee and it is a fully adaptive algorithm. Moreover, in the transductive setting, [27] designed the RAGE algorithm and derived the upper bound on its sample complexity. For the objective of fixed-budget BAI, [1] designed the OD-LinBAI algorithm based on G-optimal design and proved that the upper bound of OD-LinBAI’s failure probability matches the universal lower bound (also established in this work) up to logarithmic factors; hence, OD-LinBAI is minimax optimal and serves as the current SOTA. Note that \(\mathcal{XY}\)-adaptive and OD-LinBAI are both optimal design(OD)-based algorithms.

Bandits with Strategic Arms. The study of bandit problems with strategic arms was pioneered by [5], who proposed a model where each arm receives a private stochastic reward \(v_a\) upon being pulled, after which the pulled arm strategically reports a reward \(\tilde{v}_a\) to the learner, retaining the residual \((v_a - \tilde{v}_a)\) for itself. Because each arm aims to maximize its cumulative retained reward over \(T\) rounds, a fundamental conflict of interest arises: the learner seeks to maximize \(\sum v_a\), whereas each arm is incentivized to under-report its reward. This severe information asymmetry can mislead the learner into pulling suboptimal arms, ultimately incurring linear regret. Building on this, [28] proved that classical algorithms such as UCB and \(\epsilon\)-greedy are naturally resistant to strategic reward inflation, as long as the manipulation budget of each arm grows sub-linearly with time. [29] studied a similar model where arms are allowed to modify their rewards at a cost, and showed that UCB is not only robust to arms’ strategic behavior but also can incentivize arms to perform rationally without introducing additional mechanism design.

Meanwhile,[30], [31] investigated an alternative manifestation of strategic environment, where arms can create copies of themselves to increase their chances of being selected; these works design mechanism-enforced algorithms — PI-ETC and H-UCB — that are robust to such replication strategies.

More recently, [4], [6] extended strategic learning to linear and contextual bandits by proposing the OptGTM and COBRA algorithms, respectively. To counter feature misreporting, OptGTM integrates a GTC mechanism into LinUCB. On the other hand, inspired by the Vickrey-Clarke-Groves (VCG) mechanism, COBRA contrasts an arm’s individual optimistic reward estimate against a pessimistic estimate built from the history of all other arms. Crucially, the guarantees for both algorithms depend on strigent assumptions: (i) OptGTM relies on the condition that an arm’s reported mean perfectly aligns with its true mean (Lemma E.1 of [4]); (ii) COBRA demands that empirical UCB estimates consistently upper-bound true expected rewards under joint strategic behavior—a property the authors note fails when multiple agents manipulate data simultaneously (Assumption 1 of [6]). Beyond these assumptions, both methods focus exclusively on RM but are without exploration for the BAI task. Finally, while their specific implementations differ, both OptGTM and MESHA build upon GTC principles, and hence we position OptGTM as the more relevant baseline for comparison.

To the best of our knowledge, no prior work has comprehensively explored the BAI task in the presence of strategic arms. To bridge this gap, we develop the MESHA algorithm, which couples a naïve sampling rule with a robust incentive mechanism to ensure a high success probability. Additionally, we expose how SOTA sampling rules for linear bandits break down under strategic environments, underscoring the necessity of our approach.

1.2 Contributions↩︎

In this work, we study the fixed-budget BAI problem in strategic linear bandits, where arms may strategically misreport their features to maximize their probability of being identified as the optimal arm. Our primary contributions are as follows:

• The MESHA Algorithm. We propose Mechanism-Enforced Sequential Halving (MESHA), a BAI algorithm designed for strategic linear bandits. MESHA employs a uniform sampling rule to prevent arms from manipulating the sampling allocation, and incorporates an epoch-wise Grim Trigger Condition (GTC) to eliminate arms whose reported features severely deviate from the ground truth. Assuming an arbitrary Nash Equilibrium, we prove that every arm would attempt to pass the GTC check to maximize its identified probability, building on which we bound the failure probability of MESHA under a weaker and more practical assumption than that in existing works [4], [6].

• Theoretical Guarantees for MESHA. We derive a lower bound on MESHA’s failure probability of near-optimal arm identification under a fixed budget \(T\), assuming an arbitrary Nash equilibrium. MESHA’s failure probability exhibits an exponential decay with respect to the budget \(T\), demonstrating that the algorithm preserves the optimal convergence guarantees of non-strategic BAI baselines even within a strategic environment. Our analysis also reveals an inherent \(\mathcal{O}(d^2 \log T)\) overhead, which arises from MESHA’s need to disincentivize arms from deviating significantly from the ground truth.

• Failure of SOTA Linear BAI Algorithms. We demonstrate that SOTA linear BAI algorithms [1] utilizing G-optimal design-based sampling rules are fundamentally susceptible to strategic manipulation. Absent an incentive mechanism design, strategic arms can directly mislead the learner via feature misreporting. Furthermore, even when equipped with a GTC check, these baselines are vulnerable to a novel starvation attack. In this attack, suboptimal arms coordinate their reported features so that the optimal arm’s feature vector is trapped within the cone spanned by the suboptimal features. This forces the G-optimal design to allocate zero samples to the optimal arm; as a result, the suboptimal arms can pass the GTC check while the optimal arm is completely starved of pulls and missed by the learner. We prove that this failure is structural — no statistical test evaluating only reported features can identify manipulations that distort the underlying feature geometry — thereby justifying both the uniform sampling and GTC framework embedded in MESHA.

• Numerical Experiments. We conduct extensive experiments to evaluate the BAI performance of MESHA against several SOTA baselines. The empirical results demonstrate that MESHA consistently achieves successful BAI across varying budgets \(T\), feature dimensions \(d\), and arm counts \(K\), whereas OD-based algorithms collapse in strategic environments. Furthermore, these experiments highlight the practical advantages of MESHA: first, MESHA’s advantage over feature-agnostic algorithms widens significantly as \(K\) increases; second, its performance gap with OD-LinBAI [1] — even when the latter is evaluated in a non-strategic environment — narrows as \(d\) increases.

2 Problem Formulation↩︎

This section formalizes the BAI problem in strategic linear bandits. Section 2.1 introduces the underlying learning dynamics. Section 2.2 then defines the utility functions — which describe arms’ strategic behaviors —and the corresponding Nash Equilibrium.

2.1 Underlying Dynamics↩︎

For any \(n \in \mathbb{N}\), we denote the set \(\{1, \ldots , n\}\) as \([n]\). A random variable \(X\) (or its distribution) is \(\xi\)-sub-Gaussian (\(\xi\)-SG) if \(\mathbb{E}\big[ \exp( \lambda (X -\mathbb{E}( X)) \big] \leq \exp( {\lambda^{2} \xi^{2}}/{2}).\) In particular, a random variable supported on \([a,b]\) is \(\xi\)-SG with \(\xi=(b-a)/2\). Let there be \(K \in \mathbb{N}\) arms indexed as \([K]\). Each arm \(i\in[K]\) is characterized by a true, unobservable feature vector \(x_i \in \mathbb{R}^d\) and its quality is measured by \(\mu_i := \langle \theta^*, x_i \rangle\), where \(\theta^*\) is a unknown fixed latent vector. The unique optimal arm \(i^*\) is defined by \(\arg\max\limits_{i \in [K]} \mu_i\). The sub-optimality gap for any suboptimal arm \(i\) is strictly positive, defined as \(\Delta_i := \mu_{i^*} - \mu_i > 0\) for all \(i \neq i^*\).

Given a fixed budget of \(T\) rounds, each arm acts as a self-interested agent aiming to maximize its probability of being identified as the best arm. To achieve this goal, each arm \(i\in[K]\) may strategically report a manipulated feature vector \(x_{t,i} \in \mathbb{R}^d\) at any round \(t \in [T]\). At each round \(t\), the learner observes the reported features \(\{x_{t,1}, \dots, x_{t,K}\}\), selects an arm \(i_t\) and then receives a noisy reward generated based on the selected arm’s true feature vector: \[r_{t,i_t} = \langle \theta^*, x_{i_t} \rangle + \eta_t,\] where \(\eta_t\) is an independent \(\xi\)-SG noise. Besides, each arm \(i\) knows its true feature \(x_i\) and the latent vector \(\theta^*\). Moreover, all arms observe the learner’s sequential sampling decisions \(i_t\) and the corresponding reward realizations \(r_{t,i_t}\) over time. We adopt a full information assumption that each arm knows the design of the learner’s algorithm \(\mathcal{A}\). This assumption is natural when the leaner’s algorithm is publicly announced — such as a hiring platform that publishes its evaluation procedure, and represents the worst case for the learner since arms can tailor their misreporting strategies optimally against the known algorithm.

Without loss of generality, we assume that all true features \(x_i\), all reported features \(x_{t,i}\) and the latent vector \(\theta^*\) are bounded in \(\ell_2\)-norm: \(\|x_i\|_2 \le 1\), \(\|x_{t,i}\|_2 \le 1\), and \(\|\theta^*\|_2 \le 1\) for all \(i \in [K]\) and \(t \in [T]\); we also set \(\xi=1\).

2.2 Arm Utility Function and Nash Equilibrium↩︎

Let \(\sigma_i\) denote arm \(i\)’s strategy, which maps its true feature \(x_i\), latent parameter \(\theta^*\), the algorithm \(\mathcal{A}\) and the interaction history \(\mathcal{H}_{t}=\left\{(x_{s,i_s},r_{s,i_s})\right\}_{s\leq t-1}\) to a reported feature \(x_{t,i} \in \mathbb{R}^d\) at round \(t\). We define the joint strategy profile of all arms as \(\boldsymbol{\sigma} := (\sigma_1, \dots, \sigma_K)\), and the profile of all arms except \(i\) as \(\boldsymbol{\sigma}_{-i}\), i.e., \(\boldsymbol{\sigma}_{-i}=(\sigma_1,\cdots,\sigma_{i-1},\sigma_{i+1},\cdots,\sigma_K)\). The truthful reporting strategy, where \(x_{t,i} = x_i\) for all \(t \in [T]\), is denoted by \(\sigma_i^*\) for arm \(i\). To maximize its probability of being selected as the best arm, each arm \(i \in [K]\) strategically reports a manipulated feature vector \(x_{t,i}\) according to its individual strategy \(\sigma_i\). Let \(i_{out,T}^{\mathcal{A},\boldsymbol{\sigma}}\) denote the arm identified as the best arm. Our work studies the learner’s BAI performance when the strategy profile \(\boldsymbol{\sigma}\) reaches a Nash equilibrium. To formalize this strategic environment, we begin by defining the arm utility functions and the corresponding Nash equilibrium.

For fixed \(\zeta\in \mathbb{R}^+\) and \(T\in\mathbb{N}^+\), an algorithm \(\mathcal{A}\) is said to be \((\zeta, \delta_T)\)-PAC (probably approximately correct) if \[\mathbb{P} (\Delta_{i_{out,T}^{\mathcal{A},\boldsymbol{\sigma}}} \ge \zeta \mid \boldsymbol{\sigma} \in \text{NE}(\mathcal{A})) \leq \delta_T,\] where \(\delta_T\) is a function of \(T\). Our goal is to design a \((\zeta, \delta_T)\)-PAC algorithm \(\mathcal{A}\) such that both \(\zeta\) and \(\delta_T\) are as small as possible. This failure probability also reflects the hardness of BAI task under strategic manipulation. We abbreviate \(i_{out,T}^{\mathcal{A},\boldsymbol{\sigma}}\) as \(i_{\mathrm{out}}\) when there is no ambiguity. To further clarify the interaction among learner, arms and environment, we describe the dynamics in the following Protocol [protocol].

3 THE MESHA ALGORITHM↩︎

We now present the Mechanism-Enforced Sequential HAlving (MESHA) algorithm. Designed for BAI in strategic linear bandits, MESHA divides the total budget \(T\) into \(R =\left\lceil \log_2 K \right\rceil\) epochs. In each epoch \(r\in[R]\), MESHA maintains an active set \(\mathcal{A}_{r-1}\) and allocates the budget \(n_r\) to sample each arm. Moreover, the design of MESHA rests on two core principles. First, to prevent being misled by potentially manipulated features, MESHA samples arms uniformly within each epoch. This ensures that the budget allocation is decoupled from the arms’ reported features \(x_{t,i}\). Second, to constrain arms’ strategic behaviors, MESHA incorporates a mechanism called Grim Trigger Condition (GTC) at the end of each epoch. The GTC acts as a statistical consistency check between estimated rewards based on reported features and actual observed rewards generated with true features. Since all arms aim to maximize its utility, that is, the probability of being identified as the best arm, they would attempt to increase the survival probability, and hence the threat of elimination via the GTC forces them to constrain their strategic deviations under an Nash Equilibrium formed by any \(\boldsymbol{\sigma} \in \text{NE}(\text{MESHA})\). The pipeline of MESHA are provided in Algorithm 1 as well as Figure 2 and also elaborated as below.

3.1 Partition of Budget↩︎

MESHA operates over a sequence of \(R =\left \lceil \log_2 K \right\rceil\) epochs. In the beginning, the algorithm initializes the active arm set as \(\mathcal{A}_0 = [K]\). In each epoch \(r \in [R]\), the learner samples every active arm \(i \in \mathcal{A}_{r-1}\) for an equal number of rounds, denoted by \(n_r\). The per-arm sampling budget for epoch \(r\) is defined as: \[n_r = \left\lfloor \frac{T}{|\mathcal{A}_{r-1}| R} \right\rfloor\] where \(|\mathcal{A}_{r-1}|\) is the number of active arms at the beginning of epoch \(r\). As the algorithm progresses and the set \(\mathcal{A}_{r-1}\) shrinks, the per-arm budget \(n_r\) increases. This sampling rule allows MESHA to obtain increasingly accurate reward estimates for the remaining candidates in \(\mathcal{A}_{r-1}\) during later epochs, and the partitioning design ensures that MESHA terminates and outputs one arm within the budget \(T\). Such feasibility is formalized in the following lemma.

3.2 Estimation of Active Arms↩︎

At the end of each epoch \(r \in [R]\), to isolate the potential effects of strategic arms, MESHA maintains a unique estimator \(\hat{\theta}_{r,i}\) for each arm \(i \in \mathcal{A}_{r-1}\), which depends merely on the interaction history with arm \(i\) during epoch \(r\): \[\hat{\theta}_{r,i} = V_{r,i}^{-1} \sum_{t \in S_r} r_{t,i_t} x_{t,i_t} \mathbf{1}(i_t = i),\] where \(V_{r,i} = \lambda I_d + \sum_{t \in S_r} x_{t,i_t} x_{t,i_t}^\top \mathbf{1}(i_t = i)\) and \(S_r\) is the set of all rounds within epoch \(r\). Based on these individual estimators, the estimated mean of arm \(i\) is computed as follows: \[\hat{\mu}_{r,i} = \frac{\sum_{t \in S_r} \langle \hat{\theta}_{r,i}, x_{t,i_t} \rangle \cdot \mathbf{1}(i_t = i)}{n_r(i)}.\] MESHA estimates rewards for each arm separately to decouple the potential strategic behaviors of different arms, which guarantees MESHA can detect the strategic level of each arm individually. This serves as the basis for the success of subsequent epoch-wise Grim Trigger Condition (GTC) mechanism.

3.3 Epoch-wise Grim Trigger Condition↩︎

The epoch-wise GTC in MESHA exploits a fundamental tension in strategic manipulation. An arm that inflates its reported features to appear more attractive cannot make its actual rewards look consistent with its authentic features. Specifically, if arm \(i\) reports an exaggerated feature vector \(x_{t,i}\), the learner’s estimator \(\hat{\theta}_{r,i}\) would predict high rewards for arm \(i\). However, true rewards depend merely on the unobserved true feature \(x_i\) and are unaffected by the manipulation. This creates a detectable gap: estimated cumulative rewards based on reported features might exceed observed cumulative rewards.

To spot arms’ severe strategic behaviors, the epoch-wise GTC in MESHA detects the gap by comparing two confidence bounds. At the end of each epoch, the learner computes a lower confidence bound \(\boldsymbol{RLCB}_{r,i}\) on rewards that are predicted using reported features, and an upper confidence bound \(\boldsymbol{AUCB}_{r,i}\) on rewards that are actually observed for all arm \(i\in\mathcal{A}_{r-1}\). If the former exceeds the latter for one arm, the arm’s reported features seem to be inconsistent with its actual reward. In this case, it is suspicious that the arm behaves dishonestly and the learner hence eliminates this arm immediately and permanently. This GTC design is formalized in Definition 3. Crucially, when the round-wise GTC check in OptGTM [4] depends on the full observation history, the GTC check in MESHA operates epoch-wise, evaluating only the history of the recent epoch. This decoupling mechanism also serves as a cornerstone for MESHA’s performance guarantees.

The epoch-wise GTC imposes a survival constraint on the self-interested arms. Since an arm’s utility immediately drops to zero upon elimination, rational arms are incentivized to bound their strategic deviations in order to pass the GTC check. Besides, we note that the learner’s observed rewards should be close to the mean rewards. Formally speaking, with probability \(1-\delta\), the event \[\mathcal{E}^{\mathrm{noise}} := \left\{\left|\sum_{t \in S_r, i_t=i} (r_{t,i_t} - \mu_i)\right| \leq \sqrt{\frac{n_r(i)\log(2KR/\delta)}{2}},\; \forall r\in[R],\;\forall i \in \mathcal{A}_{r-1}\right\}\] holds. Conditioned on this event, we can characterize the equilibrium behavior of arms as follows.

3.4 Failure probability bound of MESHA↩︎

Given a fixed budget \(T\), we now characterize the \((\zeta, T)\)-PAC failure probability bound for MESHA assuming a corresponding Nash Equilibrium.

Theorem [theorem:errorbound] shows the failure probability of MESHA decays exponentially with \(T\), indicating that MESHA preserves the convergence behavior of non-strategic SOTA algorithms in the strategic environment. Moreover, the factors \(K\) and \(d^2\log T\) in the exponent denominator are due to the strategic arms as elaborated in the Remark [rem:tightness].

3.5 Performance Evaluation of MESHA↩︎

To evaluate MESHA’s BAI performance, we compare the failure probability bound of MESHA established in Theorem [theorem:errorbound] against the bounds of two natural baselines, as summarized in Table 1. We evaluate these methods based on their failure probabilities, despite nuances in their underlying environments and objectives. First, SH is immune to geometric distortions and serves as a feature-agnostic baseline. Second, OD-LinBAI [1] — the current SOTA algorithm for BAI in non-strategic linear bandits — although inherently vulnerable to strategic manipulation, serves as a feature-aware baseline. Our MESHA algorithm, by contrast, is carefully engineered to counter strategic behaviors. Furthermore, when SH and OD-LinBAI aim to identify the exact optimal arm \(i^*\), MESHA accommodates arms’ strategic behaviors to robustly identify a \(\zeta\)-optimal arm. Nevertheless, comparing MESHA against the two baselines isolates the two key dimensions of the BAI task in strategic bandits: the benefit of exploiting the arm features and the cost of mitigating strategic behavior.

Comparison with Classical SH. Classical SH achieves a failure probability of \(\exp\big(-T/(H_2\log_2 K)\big)\) where \(H_2 = \max_i\, i\Delta_{(i)}^{-2}\), and is naturally robust to strategic manipulation since it has no access to feature vectors. However, \(H_2\) can be significantly larger than \((K/\zeta^2)d^2\) when there exists a near-optimal arm with a significantly small suboptimality gap in the instance. Specifically, consider an instance with \(K=16\), \(d=4\), \(\zeta=0.1\), where arm \(1\) is the optimal arm, arm \(2\) is with suboptimality gap \(\Delta_2 = \zeta/(2d\sqrt{K}) \approx 0.003\), and the remaining arms \(i \in \{3,\ldots,16\}\) are with suboptimality gap \(\Delta_i = 2\zeta = 0.2\). In this case, \(H_2 = \max(1 \cdot \Delta_2^{-2}, 2\cdot(2\zeta)^{-2}) = \Delta_2^{-2} = 102400 \gg 25600 = (K/\zeta^2)d^2\), indicating that the failure probability of SH can be far higher than that of MESHA. We note that since \(\Delta_2 < \zeta\), this probability gap may partially result from that identification of arm \(2\) is regarded as success for MESHA but not for SH. Nevertheless, in scenarios where the \(\zeta\)-optimal arms are acceptable, MESHA achieves a higher success probability than SH by exploiting the strategic arm features.

Comparison with OD-LinBAI. OD-LinBAI achieves a smaller failure probability \(\exp\big(-T/(d\log_2 d)\big)\) because under G-optimal design, the optimal allocation \(\pi\) satisfies \(\max_i x_i^\top V(\pi)^{-1}x_i \leq d\) by definition, which naturally bounds the prediction uncertainty with a single \(d\) factor rather than \(d^2\). However, this advantage relies heavily on optimal design-based sampling and is fundamentally vulnerable to the strategic setting: as to be elaborated in Section 4, suboptimal arms can coordinate their reported features so that the optimal arm’s feature vector is trapped within the cone spanned by the suboptimal features, causing G-optimal design to allocate zero pulls to the optimal arm while suboptimal arms can pass the GTC check and the optimal arm would be missed by the learner; this justifies the uniform sampling rule embedded in MESHA.

4 Further Discussion on Algorithms for Linear Bandits↩︎

Having introduced MESHA, a natural question arises: why not simply equip the current SOTA linear BAI algorithm [1] with a GTC mechanism or apply OptGTM [4] directly for BAI instead? We now answer this question by showing that such approaches would fail from the following fundamental perspectives. First, without any mechanism design, strategic arms can directly corrupt the learner’s estimator by misreporting their features. Second, even when equipped with a GTC check, strategic arms can still evade it through a starvation attack — a coordinated manipulation where suboptimal arms misreport their features to ensure that the optimal arm receives zero pulls under \(G\)-optimal design-based sampling rules, while remaining consistent with their own rewards under the GTC check. Furthermore, we also see that the success of round-wise GTC check used in OptGTM [4] relies on a strong assumption which sidesteps the equilibrium analysis. In contrast, our epoch-wise GTC check is designed to actively constraint the arms’ behavior, and our analysis only build on a strictly weaker and more reliable assumption. These altogether justify both the uniform sampling rule and the GTC mechanism integrated in MESHA.

4.1 Vulnerability of OD-LinBAI without Mechanism Design↩︎

The current SOTA linear BAI algorithm OD-LinBAI [1] relies on \(G\)-optimal design-based sampling rule to allocate pulls based on the reported feature vectors of arms. This sampling strategy assumes the reported features reflect the true underlying geometry of the arms. When arms are strategic, however, this assumption may no longer hold: arms can misreport their features to manipulate the sampling process and corrupt the learner’s estimator. We illustrate this through the following example.

In Example 1, the manipulation succeeds because the two arms report identical features, causing the optimal design-based algorithm’s estimator to blend the rewards of both arms. The resulting estimator converges to a weighted average of both arms’ true rewards, rather than the true reward of each individual arm, making identification impossible. This shows that without any mechanism design, even a trivial misreport is sufficient to cause identification failure.

4.2 Vulnerability of OD-LinBAI with Mechanism Design↩︎

The failure of OD-LinBAI in Example 1 suggests that some form of consistency check is needed to detect manipulation. A natural candidate is OD-LinBAI-GTC, which combines OD-LinBAI with the same epoch-wise GTC used in MESHA. The pseudocode is shown in Algorithm 4. However, we find that strategic arms can still pass this check through a starvation attack, by exploiting a structural property of \(G\)-optimal design: if the optimal arm’s reported feature falls within the cone spanned by the suboptimal arms’ reported features, then \(G\)-optimal design allocates zero pulls to the optimal arm. We formalize this phenomenon in the following theorem and postpone its proof to Appendix 11.

Theorem [theorem:misthm] shows that suboptimal arms can coordinate their reported features to starve the optimal arm of any sampling budget, while passing the GTC by remaining consistent with their own rewards. We illustrate this attack through the following example.

In this example, we construct a starvation attack where arms’ rewards depend only on the first feature coordinate. Under strategic reporting, every arm sets the first coordinate of its reported feature to zero, hiding the reward-relevant direction entirely. This places optimal design-based algorithms under maximal strategic pressure while leaving feature-agnostic algorithms unaffected. The starvation attack succeeds because suboptimal arms coordinate their reported features to manipulate the geometric boundary of the feature space, ensuring that the optimal arm is never sampled while their own rewards remain consistent considering the GTC. This implies that the failure of \(G\)-optimal design in strategic settings is structural: no consistency check applied at the reward level can detect a manipulation that operates at the feature geometry level. In contrast, MESHA avoids this style of failures by applying uniform sampling, which ensures that every active arm receives pulls regardless of the reported feature geometry.

4.3 Comparison against OptGTM↩︎

The OptGTM algorithm, recently designed by [4], also incorporates a GTC check to handle strategic behavior in linear bandits but for RM. However, the utilization of GTC in [4] reveals a fundamental limitation. Specifically, their analysis relies on Lemma E.1 of [4], which assumes that for any arm \(i\) and any round \(t\) where \(i_t = i\), we have \[\begin{align} \langle\theta^*, x^*_{t,i}\rangle = \langle\theta^*_i, x_{t,i}\rangle, \label{eq:assum95optGTM} \end{align}\tag{1}\] arms’ strategic manipulation has no effect on the reward evaluation. Under this assumption, every arm automatically passes the GTC check regardless of its actual behavior, rendering the GTC check passive rather than an active mechanism. We think this strong assumption might be introduced because finding a Nash Equilibrium directly proved difficult, and it effectively sidesteps the equilibrium analysis by pre-imposing honest behavior on the arms. In fact, the starvation attack constructed in Example 2 provides an explicit instance where the assumption in Lemma E.1 of [4] is violated: arms 2 and 3 report features inconsistent with their true features while using pseudo-parameters \(\theta_2^*\) and \(\theta_3^*\) to maintain reward consistency, a strategy that OptGTM’s assumption would rule out by construction.

Rather than assuming that arms’ reported mean values are equivalent to true mean values as in 1 , MESHA applies the GTC check to actively constrain arms’ strategic behavior to form a NE under MESHA where the reported rewards remain close to the true rewards, but they do not necessarily coincide. As shown in Lemma [lemma:GTCpass], passing the GTC check is a necessary condition for any arm to survive elimination of MESHA under Nash Equilibrium: a rational arm that expects to be selected in future rounds would attempt to satisfy the GTC, since failing it leads to permanent elimination and zero utility. In brief, the epoch-wise GTC of MESHA naturally constrains the arms’ strategic behavior under a milder condition. Instead of the strong assumption made in Lemma E.1 of OptGTM[4], our analysis merely requires the following relaxed condition.

This is a weaker condition than Lemma E.1 for OptGTM[4]: it allows arms to misreport their features, as long as the resulting deviation in the reward evaluation remains bounded by \(\varepsilon\), rather than being exactly zero. Under this assumption, we establish the following guarantee on the behavior of any arm that survives the GTC check of MESHA and postpone the proof to Appendix 11.

Theorem [theorem:manipulationlevel] implies that the epoch-wise GTC check in MESHA actively constrains the strategic behavior of any surviving arm: the average deviation \(\bar{\varepsilon}_{r,i}\) is bounded in terms of the confidence radius \(\beta_{r,i}\) and the number of pulls \(n_r(i)\). As \(n_r(i)\) grows, this bound tightens, indicating that arms face increasingly stringent constraints on their strategic behavior as the MESHA algorithm progresses. Furthermore, when \(\varepsilon = 0\), Assumption 1 reduces to the assumption for OptGTM (see Lemma E.1 in [4]), indicating that the assumption in [4] is a special case of our framework.

5 Numerical Experiments↩︎

We evaluate MESHA against five baselines: Sequential Halving [22], Successive Rejects[21], OD-LinBAI [1], OD-LinBAI-GTC (introduced in Section 4.2) and OptGTM [4]. We construct several strategic instances motivated by the starvation attack described in Section 4. As baseline algorithms are generally designed for optimal arm identification, we set \(\zeta=\Delta_{\min}/2\) for MESHA and compare the failure probabilities of optimal arm identification of all algorithms. All results are averaged over 5000 independent trials and error bars indicate \(95\%\) wald confidence intervals. More details are provided in Appendix 14.

5.1 Overall Comparison↩︎

In Figure 3 (b), we vary \(T \in \{60, 100, \dots, 800\}\) with fixed \(K = 8\), \(d = 3\). MESHA’s failure probability decays from \(0.188\) when \(T = 60\) to \(0.056\) when \(T = 800\), which exponentially decay on \(T\), corroborating Theorem [theorem:errorbound]. OptGTM follows a similar decay trend and occasionally performs comparably to MESHA when the budget \(T\) is large. However, OptGTM is designed for RM in strategic linear contextual bandits and is with no theoretical guarantee for the BAI tasks. Both SH and SR are unaffected by strategic feature reporting since they are feature-ignostic. However, their failure probabilities decrease slowly, as they cannot utilize arm features to facilitate arm identification. OD-LinBAI and OD-LinBAI-GTC both fail completely, with failure probabilities approaching \(1\) as \(T\) grows, corroborating the starvation attack study in Section 4. Notably, integrating the GTC mechanism does not help OD-LinBAI, implying that the failure is structural. In contrast, OD-LinBAI*, which observes the true feature vectors, achieves near-zero failure probability throughout, demonstrating that the failure of OD-LinBAI is entirely due to strategic feature misreporting rather than any algorithmic deficiency of OD-LinBAI itself.

5.2 Impact of Feature Dimension and Arm Count↩︎

In Figure 3 (c) and Figure 3 (d), we fix \(T = 1{,}500\) and individually vary \(d\) and \(K\) to evaluate the impact of feature dimension and arm count on MESHA’s performance. While Theorem [theorem:errorbound] shows that the failure probability grows with both \(d^2\) and \(K\), numerical results reveal that MESHA’s empirical performance is consistently better than this worst-case theoretical prediction, and its advantage over the baselines widens as either \(d\) or \(K\) grows.

5.2.0.1 Varying \(d\)

With \(K = 64\) fixed, we vary \(d \in \{3, 6, 9, 18, 24\}\) to evaluate the impact of feature dimension on MESHA’s performance. Although Theorem [theorem:errorbound] shows an \(\mathcal{O}(d^2\log T)\) penalty inside the exponent, MESHA’s empirical failure probability increases only moderately with \(d\), suggesting that the theoretical bound is conservative and MESHA performs better in practice than what the worst-case analysis implies. MESHA consistently outperforms OptGTM by roughly \(11\) percentage points across all values of \(d\). Since OptGTM relies on feature-dependent sampling, it remains more susceptible to strategic manipulation than MESHA, whose uniform sampling rule is robust by design. Comparing with OD-LinBAI*, which serves as an oracle baseline with access to true feature vectors, reveals a further advantage of MESHA. When \(d = 3\), OD-LinBAI* achieves a much lower failure probability (\(\approx 6.5\%\)) due to the sample efficiency of \(G\)-optimal design in low dimension space. However, its failure probability rises steeply as \(d\) grows and is similar to that of MESHA near \(d = 18, 24\). This indicates that, despite the \(d^2\) term in Theorem [theorem:errorbound], MESHA is a practically competitive algorithm at large \(d\): it achieves success probability comparable to the oracle baseline OD-LinBAI*.

5.2.0.2 Varying \(K\)

With \(d = 6\) fixed, we vary \(K \in \{16, 24, 32, 64\}\) to evaluate the impact of arm count on MESHA’s performance. Although Theorem [theorem:errorbound] shows that the failure probability grows linearly with \(K\) in the error exponent, MESHA’s empirical failure probability increases at a rate noticeably slower than linear rate suggesting an \(o(K)\) growth in practice. MESHA attains the lowest failure probability than non-linear baselines SR and SH, and its margin over the baselines widens as \(K\) grows, further indicating that MASHE performs better in practice. Both Sequential Halving and Successive Rejects are unaffected by strategic feature reporting since they are feature-ignosmic. However, their failure probabilities increase more rapidly than MESHA’s as \(K\) grows, since they rely solely on the reward signal but no feature information for arm identification. MESHA retains a compounding advantage as \(K\) increases. When the arm set is large and reward gaps are small, the additional discriminative power from features becomes increasingly valuable, and MESHA is the only algorithm that exploits this structure while remaining robust to strategic reporting.

6 Proof Sketch of Theorem [theorem:errorbound]↩︎

The key technical challenge in analyzing the failure probability of MESHA is that arms’ strategic behaviors corrupt the feature-based estimators \(\hat{\theta}_{r,i}\), rendering the standard concentration arguments commonly applied in truthful linear bandits [11] inapplicable. To overcome this challenge, we begin our analysis with defining a “good event” based on the learner’s observed rewards.

Conditioned on \(\mathcal{E}^{\mathrm{noise}}\), Lemma [lemma:GTCpass] implies that all active arms aim to pass GTC check under Nash Equilibrium, and hence we can derive the following strategic deviation bound for active arms.

With Lemmas [lemma:GTCpass], [lemma:concentration] and [lemma:gtc95bound] in place, the remaining analysis is similar to that of SH [22]. Under Nash Equilibrium, every active arm passes the GTC to maximize its utility function value (Lemma [lemma:GTCpass]), so the strategic deviation bound \(\hat{\mu}_{r,i} \leq \mu_i + \omega_{r,i}\) holds for all active arms conditioned on \(\mathcal{E}^{\mathrm{noise}}\). If the optimal arm \(i^*\) is incorrectly eliminated at epoch \(r^*\), there must exist a suboptimal arm \(i\) with \(\hat{\mu}_{r^*,i} \geq \hat{\mu}_{r^*,i^*}\), which combined with Lemma [lemma:gtc95bound] indicates \(\Delta_i \leq \omega_{r^*,i^*} + \omega_{r^*,i}\). Setting \(\delta_r = \delta/(KR)\) and summing them up over all epochs yields the upper bound of MESHA’s failure probability in Theorem [theorem:errorbound].

7 Conclusion and Future Directions↩︎

In this paper, we studied the problem of fixed-budget Best Arm Identification in strategic linear bandits, where arms may strategically misreport their feature vectors to maximize their probability of being identified as the best arm. We proposed MESHA, which equips uniform sampling with an epoch-wise Grim Trigger Condition to handle strategic manipulation. We proved that passing the GTC is a necessary condition for any arm to maximize its utility function values under Nash Equilibrium, and derived a \((\zeta, T)\)-PAC failure probability bound showing that MESHA identifies a near-optimal arm with high probability. our upper bound reveals an \(\mathcal{O}(d^2\log T)\) statistical overhead arising from the Grim Trigger Condition, and we further demonstrated that state-of-the-art linear BAI algorithms relying on G-optimal design-based sampling rules fail under strategic reporting due to the starvation attack, a failure that cannot be addressed by any reward-level consistency check. Our numerical results indicates that MESHA consistently identify the optimal arm across various \(T\), feature dimensions \(d\) and arm counts \(K\).

Several directions remain open for future work. First, our theoretical guarantees hold under Nash Equilibrium, which assumes fully rational arms; extending the analysis to handle deviations from equilibrium behavior remains yet to be explored. Second, a precise characterization of the statistical cost of robustness in strategic linear bandits—in particular, whether the \(\mathcal{O}(d^2\log T)\) penalty reflects a fundamental limitation of the problem or an artifact of the current mechanism design—remains an important open question. Third, extending MESHA to the fixed-confidence setting would require a delicate design of stopping criterion and novel analysis of GTC mechanism for the uncertain budget \(T\). Finally, BAI attempts in environments where arms can also manipulate their rewards, rather than only their feature vectors, would further broaden the scope of this work.

The appendices presents detailed proofs for all theoretical results in this work and additional experimental details, organized in the order they appear in the main text. We also provide more discussion on the failure probability upper bound of MESHA.

Appendix 8 provides basic facts used in our analysis. Appendix 9 proves Lemma [lemma:GTCpass], showing that passing the GTC is a necessary condition for arms maximizing utilities under any Nash Equilibrium. Appendix 10 completes the proof of our main result, Theorem [theorem:errorbound], along with two supporting lemmas introduced in Section 6.

Appendix 11 proves Theorem [theorem:misthm], which establishes the theoretical foundation for the starvation attack in Section 4. Appendix 11 proves Theorem [theorem:manipulationlevel], bounding the average strategic deviation of any arm that survives the GTC. Appendix 12 presents the pseudo-code of OD-LinBAI-GTC, which combines OD-LinBAI[1] with epoch-wise GTC mechanism.

Appendix 13 investigates the tightness of the \(O(d^2\log T)\) in Theorem [theorem:errorbound]: we show that the additional \(d^2\) factor as the cost of bounding strategic deviation is simultaneously achievable by an explicit reporting strategy, and conjectures that the \(d^2\) factor is unavoidable for any algorithm including epoch-wise GTC mechanism and feature-independent sampling rules. Finally, Appendix 14 provides additional experimental details.

8 Useful Facts↩︎

Here are some useful facts that are applied in our proof.

9 Proof of Lemma [lemma:GTCpass]↩︎

10 Proof of Theorem [theorem:errorbound]↩︎

Throughout this section, we set \[\delta = \frac{\lceil\log_2 K\rceil^2}{T}\exp\!\left( -\frac{T\zeta^2}{18Kd^2\log^2\!\left(1+\frac{T}{\lceil \log_2 K\rceil}\right)}\right), \quad \delta_r = \frac{\delta}{KR}, \quad R = \lceil\log_2 K\rceil, \quad N = \frac{T}{\lceil\log_2 K\rceil}.\]

We first establish two supporting lemmas before proving the main result.

The following proof is for the probability of \(\mathcal{E}^{\mathrm{est}}\) defined in Remark [remark:est95event] when all arms report truthfully.

Now we are ready to prove Theorem [theorem:errorbound].

11 Proof of Theorem [theorem:manipulationlevel]↩︎

We first establish a supporting lemma on the concentration of the ridge regression estimator under strategic manipulation, then prove the main result.

12 OD-LinBAI-GTC↩︎

In Section 5, we evaluated OD-LinBAI equipped with the GTC mechanism as one of our baselines. To ensure experimental reproducibility, we present its pseudo-code in Algorithm 4. Following standard epoch-based elimination algorithms, the epoch-wise allocation parameter \(m\) is defined as: \[\label{equation:m} m = \frac{T - \min\big(K, \frac{d(d+1)}{2}\big) - \sum_{r=1}^{\lceil\log_2 d\rceil - 1} \lceil\frac{d}{2^r}\rceil}{\lceil\log_2 d\rceil}.\tag{6}\]

As analyzed in Section 4, although this algorithm incorporates a GTC mechanism, it fundamentally fails to identify the best arm under arms’ strategic reporting. Suboptimal arms can construct reported features such that the optimal arm falls within the cone spanned by their features, causing \(G\)-optimal design to allocate zero pulls to the optimal arm. Since this manipulation is structural in the sense that the learner fails to learn the geometry of arm feature space when using OD-based sampling rules, the GTC check, which detects the gap between reported rewards and actual rewards, cannot help it identify the optimal arm.

13 Tightness of The \(d^2\) Penalty↩︎

This section provides a structural analysis of the \(\mathcal{O}(d^2\log T)\) penalty in Theorem [theorem:errorbound].

We revisit the derivation of \(\omega_{r,i}\) from the proof of Lemma [lemma:gtc95bound]. Starting from this lemma’s GTC-derived bound, any arm \(i\) surviving the GTC at epoch \(r\) satisfies \[\hat{\mu}_{r,i} \;\leq\; \mu_i + \frac{\beta_{r,i}}{n_r} \sum_{t\in S_r,\,i_t=i}\|x_{t,i}\|_{V_{r,i}^{-1}} + \sqrt{\frac{2\log(2/\delta_r)}{n_r}}. \label{eq:gtc-mu-bound}\tag{7}\] Applying the Cauchy-Schwarz inequality to the middle term: \[\frac{\beta_{r,i}}{n_r} \sum_{t:\,i_t=i}\|x_{t,i}\|_{V_{r,i}^{-1}} \;\leq\; \frac{\beta_{r,i}}{\sqrt{n_r}} \sqrt{\sum_{t:\,i_t=i}\|x_{t,i}\|^2_{V_{r,i}^{-1}}}. \label{eq:cs-split}\tag{8}\] We bound the two factors on the right-hand side separately.

13.0.0.1 First factor (first \(\sqrt{d}\)) – confidence radius

By the elliptical potential lemma [11], the ridge regression confidence radius satisfies \[\beta_{r,i} \;\leq\; \sqrt{(d+1)\log\frac{1+n_r}{\delta_r}}, \label{eq:beta-bound}\tag{9}\] where we have \(\log(1+n_r/(\lambda d))\leq\log(1+n_r)\) for \(\lambda\geq 1/d\). This bound holds for any reported feature sequence, as it is derived from Theorem 1 and does not depend on the arms’ reporting strategies.

13.0.0.2 Second factor (second \(\sqrt{d}\)) – potential sum

By the definition \(V_{r,i} = \lambda I_d + \sum_{t:\,i_t=i}x_{t,i}x_{t,i}^\top\), we have \(\sum_{t:\,i_t=i}x_{t,i}x_{t,i}^\top = V_{r,i} - \lambda I_d\), and therefore, \[\sum_{t:\,i_t=i}\|x_{t,i}\|^2_{V_{r,i}^{-1}} \;=\; \mathrm{tr}\!\left(V_{r,i}^{-1}(V_{r,i}-\lambda I_d)\right) \;=\; d - \lambda\,\mathrm{tr}(V_{r,i}^{-1}) \;\leq\; d, \label{eq:trace-id}\tag{10}\] where the last inequality uses \(\mathrm{tr}(V_{r,i}^{-1})\geq 0\). This bound holds for any reported feature sequence with \(\|x_{t,i}\|_2\leq 1\), and follows purely from the definition of \(V_{r,i}\) without invoking the elliptical potential lemma [11].

13.0.0.3 Combining the two factors

Substituting 9 and 10 into 8 yields \[\frac{\beta_{r,i}}{\sqrt{n_r}} \sqrt{\sum_{t:\,i_t=i}\|x_{t,i}\|^2_{V_{r,i}^{-1}}} \;\leq\; \sqrt{\frac{d(d+1)\log\frac{1+n_r}{\delta_r}}{n_r}}. \label{eq:combined}\tag{11}\] With \(\delta_r = \delta/(2KR)\) and \(n_r = \lfloor T/(K_r R)\rfloor\) where \(K_r = \lceil K/2^{r-1}\rceil\), we have \(\log((1+n_r)/\delta_r) = O(\log T)\), so there exists an absolute constant \(c_1 > 0\) such that \[\omega_{r,i} \;\leq\; c_1\sqrt{\frac{d^2\log T}{n_r}}. \label{eq:omega-final}\tag{12}\]

13.0.0.4 Independence of the two factors

The first \(\sqrt{d}\) arises from \(\beta_{r,i}\) via the elliptical potential lemma [11], reflecting the estimation cost of ridge regression in \(\mathbb{R}^d\). The second \(\sqrt{d}\) arises from the trace identity 10 , reflecting the structure of the GTC verification step. These sources are logically independent: the first cannot be reduced without changing the estimator, and the second cannot be reduced without changing the consistency check.

14 Additional Experimental Details↩︎

Hyperparameters. All results are averaged over 5000 independent trials. With random seeds generated as \(\texttt{seed} + 100000 \times T + \texttt{run\_idx}\), where \(\texttt{seed} = 20260323\). Besides, we set \(\lambda=1.35\) for MESHA.

14.1 Experiment 1: Overall Comparison (Varying \(T\))↩︎

Instance Construction. We construct a strategic linear bandit instance with \(K = 8\) arms and feature dimension \(d = 3\). The true parameter is \(\theta^* = (1, 0, 0)\), so the true expected reward of arm \(i\) is determined merely by its first feature coordinate. The true means are \(\boldsymbol{\mu} = (0.52, 0.49, 0.40, 0.33, 0.27, 0.22, 0.18, 0.15)\), with arm \(1\) being the unique optimal arm. Each arm \(i\) receives reward \(r_{t,i} = \mu_i + \eta_t\) where \(\eta_t \sim \mathcal{N} (0, 0.155^2)\). The true feature vectors \(x_i\in \mathbb{R}^3\) are in Table 2. The non-zero coordinates in dimensions \(2\) and \(3\) play no role in determining rewards under \(\theta^* = (1,0,0)\), but serve to create a non-trivial feature geometry that prevents trivial identification of the reward-relevant direction from the feature vectors alone.

Strategic Reporting. Under strategic reporting, every arm sets the first coordinate of its reported feature to zero, completely preventing the learner from learning the reward-relevant direction. Each arm \(i\) maintains a pseudo-parameter \(\theta_i^*\) satisfying \(\langle x_{t,i}, \theta_i^*\rangle = \mu_i\) for all \(t\) to ensure its reported rewards remain locally consistent considering the GTC check. This instance is motivated by the starvation attack discussed in Section 4; it would severely harm the behaviours of feature-dependent algorithms while leaving reward-only algorithms unaffected. The complete true and reported features for this instance are given in Table 2.

Baselines. We compare MESHA against the following SOTA algorithms in linear and non-linear bandits under strategic environment:

• Sequential Halving [22]: a SOTA algorithm that has no access to feature vectors and allocates pulls uniformly across active arms in each epoch.

• Successive Rejects [21]: a SOTA algorithm for standard stochastic bandits and has no access to feature information.

• OptGTM [4]: a GTC-based contextual linear bandit algorithm that uses reported features for sampling with parameters set as in the original work [4].

• OD-LinBAI: OD-LinBAI [1] applied directly to reported features without any mechanism design.

• OD-LinBAI-GTC: OD-LinBAI combined with our GTC mechanism, as described in Appendix 12.

• OD-LinBAI*: OD-LinBAI applied to the true feature vectors, serving as an oracle baseline that represents the best achievable performance without strategic manipulation.

Results. Results are presented in Table 3.

14.2 Experiment 2: Varying Feature Dimension \(d\)↩︎

Instance Construction. We fix \(K = 64\) arms and budget \(T = 1500\), and vary \(d \in \{3, 6, 9, 18, 24\}\). For each \(d\), the true parameter \(\theta^* \in \mathbb{R}^d\) is a fixed dense unit vector whose coordinates are listed in Table 4. The true feature of arm \(i\) is constructed as: \[x_i^* = \mu_i \theta^* + \rho(d) z_i,\] where \(z_i \perp \theta^*\) is a random unit vector orthogonal to \(\theta^*\) and \(\rho(d)\) controls the magnitude of the nuisance direction. The optimal arm is arm \(0\) with true mean \(\mu_0 = 0.62\) across all values of \(d\). The second-best arm has true mean \(\mu_1\), and the suboptimality gap \(\Delta_1 = \mu_0 - \mu_1\) is denoted as “gap” in Table 4; the remaining \(62\) arms have means strictly decreasing from \(\mu_1\) to \(0.12\). The reward noise follows \(\eta_t \sim \mathcal{N}(0, \xi^2)\), where \(\xi\) varies with \(d\) to maintain a consistent signal-to-noise ratio. All instance parameters are summarized in Table 4 and 5.

Strategic Reporting. Each arm \(i\) acts as a self-interested agent aiming to maximize its own probability of being identified as the best arm. Under this strategic instance, every arm sets the first coordinate of its reported feature to zero, hiding the reward-relevant direction from the learner. The suboptimal arms report features with norm \(1.0\) to appear as prominent as possible in the reported feature space, while the optimal arm’s reported feature has norm \(0.88\), making it appear less competitive than the suboptimal arms. Each arm \(i\) maintains a pseudo-parameter \(\theta_i^*\) satisfying \(\langle x_{t,i}, \theta_i^* \rangle = \mu_i\) for all \(t\), ensuring that its estimated rewards under \(\theta_i^*\) remain consistent with its observed rewards and the GTC check is passed. All results are averaged over 1000 independent trials.

Baselines. We compare MESHA against OptGTM [4] and OD-LinBAI*[1], which serves as an SOTA baseline facing non-strategic environment. Note that OD-LinBAI under strategic reporting fails completely in this instance and is omitted from this comparison for clarity.

Results. Algorithms’ empirical BAI failure probabilities are summarized in Table 6.

14.3 Experiment 3: Varying Arm Count \(K\)↩︎

Instance Construction. We fix feature dimension \(d = 6\), budget \(T = 1500\), and sweep \(K \in \{16, 24, 32, 64\}\). The true parameter is the same dense unit vector \(\theta^* = (0.6389,\;0.4518,\;0.3689,\;0.3194,\; 0.2857,\;0.2608) \in \mathbb{R}^6\) across all values of \(K\). The true feature of arm \(i\) is constructed as: \[x_i^* = \mu_i \theta^* + \rho(K) z_i, \quad z_i \perp \theta^*, \quad \|z_i\|_2 = 1,\] where \(z_i\) is a random unit vector orthogonal to \(\theta^*\), and \(\rho(K)\) controls the magnitude of the nuisance direction. The optimal arm is arm \(0\) with true mean \(\mu_0 = 0.62\) fixed across all \(K\). The second-best arm has true mean \(\mu_1 = \mu_0 - \text{gap}(K)\), where the suboptimality gap \(\Delta_1 = \text{gap}(K)\) shrinks as \(K\) grows according to: \[\text{gap}(K) = \max\!\left(0.0022,\;0.010 \times \left(\frac{16}{\max(K,16)}\right)^{1.48}\right).\] The remaining \(K-2\) arms have means linearly spaced between \(\mu_1\) and \(\mu_{\text{tail}} = 0.20\). The noise standard deviation \(\xi\) and nuisance magnitude \(\rho(K)\) increase with \(K\) to reflect the greater difficulty of identifying the optimal arm when more arms compete. All instance parameters are summarized in Table 7.

Strategic Reporting. Under strategic reporting, every arm sets the first coordinate of its reported feature to zero. Unlike the vary-\(d\) experiment, the true optimal arm remains the strongest arm under reported features as well (no collapse bait), so the strategic difficulty comes purely from the geometry compression rather than active misdirection. Each arm maintains a pseudo-parameter satisfying \(\langle x_{t,i}, \theta_i^*\rangle = \mu_i\) to pass the GTC. The reported geometry is scaled by a \(K\)-dependent multiplier (K=16\(\to\)​1.00, 24\(\to\)​1.05, 32\(\to\)​1.12, 64\(\to\)​1.51) to reflect increasing strategic pressure as more arms compete. To ensure consistency across \(K\) values, the instance uses a nested construction where the first \(K'\) arms under a larger \(K\) are identical to those under a smaller \(K\). All results are averaged over 5000 independent trials.

Baselines. We compare MESHA against Sequential Halving [22] and SE, both of which rely solely on observed rewards and are unaffected by strategic feature reporting. OD-LinBAI and OptGTM are omitted from this comparison since they fail under strategic reporting in this instance.

Results. The BAI failure probabilities are summarized in Table 8.

References↩︎

---

1. Xin Li and Zixin Zhong are both with the Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou).↩︎