MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits Xin Li, Graduate Student Member, IEEE, Zixin Zhong, Member, IEEE

Abstract

arXiv:2607.14706v1 [cs.LG] 16 Jul 2026

We design and analyze Mechanism-Enforced Sequential HAlving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits. In this setting, each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, when rewards are generated from the arms’ true but unobservable features. The design of MESHA applies the naı̈ve uniform sampling rule and an epoch-wise Grim Trigger Condition (GTC): the former reduces the impact of arms’ strategic behaviours and the latter eliminates arms whose reported features severely deviate from the ground truth. Considering an arbitrary Nash Equilibrium, we prove that any arm would attempt to pass the GTC check to maximize its identified probability and derive an upper bound on the failure probability of MESHA within a fixed budget T . We also show that state-of-the-art linear BAI algorithms with G-optimal design would fail in such strategic environment, as the optimal design (OD)-based sampling rule based on strategically reported features may starve the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms baselines that rely on OD-based sampling rules as well as the feature-agnostic baselines, corroborating the efficacy of MESHA. Index Terms Strategic linear bandits, best arm identification, mechanism design.

I. INTRODUCTION ONSIDER 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 xi ∈ Rd . The platform evaluates these candidates based on a unified criterion modeled by an unknown latent vector θ∗ , and the true underlying score of candidate i is represented by the inner product ⟨θ∗ , xi ⟩. 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 xt,i ̸= xi to increase their chances of being selected for interview at any round t. However, once selected, their actual performance depends on their true profile xi rather than the reported feature xt,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 X Y-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.

A. 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 Xin Li and Zixin Zhong are both with the Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou).

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 δ. 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, √ [17] established √ [16] proposed the LINREL algorithm, one of the first algorithms for stochastic linear bandits. an Ω(d T ) minimax lower bound on regret, and [11] proposed the OFUL algorithm, which achieves Õ(d 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 (ε, δ)-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 X Y-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 X Y-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 va upon being pulled, after which the pulled arm strategically reports a reward ṽa to the learner, retaining the residual (va − ṽa ) for itself. Because each arm aims to P maximize its cumulative retained reward over T rounds, a fundamental conflict of interest arises: the learner seeks to maximize va , 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 ϵ-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. B. 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 O(d2 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 featureagnostic 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. II. P ROBLEM F ORMULATION This section formalizes the BAI problem in strategic linear bandits. Section II-A introduces the underlying learning dynamics. Section II-B then defines the utility functions — which describe arms’ strategic behaviors —and the corresponding Nash Equilibrium. A. Underlying Dynamics For any n ∈ N, we denote the set {1, . . . , n} as [n]. A random variable X (or its distribution) is ξ-sub-Gaussian (ξ-SG) if E exp(λ(X − E(X)) ≤ exp(λ2 ξ 2 /2). In particular, a random variable supported on [a, b] is ξ-SG with ξ = (b − a)/2. Let there be K ∈ N arms indexed as [K]. Each arm i ∈ [K] is characterized by a true, unobservable feature vector xi ∈ Rd and its quality is measured by µi := ⟨θ∗ , xi ⟩, where θ∗ is a unknown fixed latent vector. The unique optimal arm i∗ is defined by arg max µi . The sub-optimality gap for any suboptimal arm i is strictly positive, defined as ∆i := µi∗ − µi > 0 for all i ̸= i∗ . i∈[K]

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 ∈ [K] may strategically report a manipulated feature vector xt,i ∈ Rd at any round t ∈ [T ]. At each round t, the learner observes the reported features {xt,1 , . . . , xt,K }, selects an arm it and then receives a noisy reward generated based on the selected arm’s true feature vector: rt,it = ⟨θ∗ , xit ⟩ + ηt ,

(1) ∗

where ηt is an independent ξ-SG noise. Besides, each arm i knows its true feature xi and the latent vector θ . Moreover, all arms observe the learner’s sequential sampling decisions it and the corresponding reward realizations rt,it over time. We adopt a full information assumption that each arm knows the design of the learner’s algorithm 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 xi , all reported features xt,i and the latent vector θ∗ are bounded in ℓ2 -norm: ∥xi ∥2 ≤ 1, ∥xt,i ∥2 ≤ 1, and ∥θ∗ ∥2 ≤ 1 for all i ∈ [K] and t ∈ [T ]; we also set ξ = 1.

B. Arm Utility Function and Nash Equilibrium Let σi denote arm i’s strategy, which maps its true feature xi , latent parameter θ∗ , the algorithm A and the interaction history Ht = {(xs,is , rs,is )}s≤t−1 to a reported feature xt,i ∈ Rd at round t. We define the joint strategy profile of all arms as σ := (σ1 , . . . , σK ), and the profile of all arms except i as σ −i , i.e., σ −i = (σ1 , · · · , σi−1 , σi+1 , · · · , σK ). The truthful reporting strategy, where xt,i = xi for all t ∈ [T ], is denoted by σi∗ for arm i. To maximize its probability of being selected as the best arm, each arm i ∈ [K] strategically reports a manipulated feature vector xt,i according to its individual strategy σi . Let iA,σ out,T denote the arm identified as the best arm. Our work studies the learner’s BAI performance when the strategy profile σ reaches a Nash equilibrium. To formalize this strategic environment, we begin by defining the arm utility functions and the corresponding Nash equilibrium. Definition 1. (Arm’s Utility Function) Given a learning algorithm A, the utility function of each arm i ∈ [K] under strategy profile σ is defined as the probability of being identified as the best arm, i.e., Ui (A, σ) := P(iA,σ out,T = i | σ).

(2)

Definition 2. (Nash Equilibrium) A strategy profile σ forms a Nash Equilibrium (NE) under algorithm A if, for any arm i ∈ [K] and any alternative strategy σi′ , the following holds: Ui (A, (σi , σ −i )) ≥ Ui (A, (σi′ , σ −i )).

(3)

The set of all strategy profiles forming a Nash Equilibrium under A is denoted as NE(A).

For fixed ζ ∈ R+ and T ∈ N+ , an algorithm A is said to be (ζ, δT )-PAC (probably approximately correct) if P(∆iA,σ ≥ ζ | σ ∈ NE(A)) ≤ δT , out,T

(4)

where δT is a function of T . Our goal is to design a (ζ, δT )-PAC algorithm A such that both ζ and δT are as small as possible. This failure probability also reflects the hardness of BAI task under strategic manipulation. We abbreviate iA,σ out,T as iout when there is no ambiguity. To further clarify the interaction among learner, arms and environment, we describe the dynamics in the following Protocol II-B. Protocol 1 Interaction Protocol: BAI in Strategic Linear Bandits 1: Learner picks algorithm A given a fixed budget T and arm set [K]. 2: for t = 1, . . . , T do 3: All arms report potentially gamed features {xt,1 , · · · , xt,K } based on σ, learner selects arm it ∈ [K] based on Ht and receives reward rt,it := ⟨θ∗ , xit ⟩ + ηt where ηt is zero-mean ξ-SG noise, θ∗ ∈ Rd is unknown latent vector, and the reward rt,it is generated based on the true feature xit . 4: end for 5: Learner outputs the identified optimal arm iout based on HT . III. 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 = ⌈log2 K⌉ epochs. In each epoch r ∈ [R], MESHA maintains an active set Ar−1 and allocates the budget nr 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 xt,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 σ ∈ NE(MESHA). The pipeline of MESHA are provided in Algorithm 1 as well as Figure 1 and also elaborated as below.

Algorithm 1 Mechanism-Enforced Sequential HAlving (MESHA) 1: Input: total budget T , arm set A = [K], and target accuracy ζ. ⌈log2 K⌉2 T ζ2 . 2: Initialize: t0 = 0, A0 = A, R = ⌈log2 K⌉, S0 = ∅, λ = 1, and δ = exp − 2 2 T 18Kd log (1+T /⌈log2 K⌉) 3: for r = 1 to R do 4: Pull each arm i ∈ Ar−1 for T nr (i) = |Ar−1 |⌈log2 K⌉ times and update

tr = tr−1 + |Ar−1 | · nr (i), 5:

Sr = {tr−1 , . . . , tr − 1}.

Collect reported vectors {xt,1 , · · · , xt,K } ⊂ Rd for all t ∈ Sr and update statistics Vr,i and θ̂r,i for arm i ∈ Ar−1 : X X −1 Vr,i = λId + xt,it x⊤ θ̂r,i = Vr,i rt,it xt,it 1(it = i). t,it 1(it = i), t∈Sr

t∈Sr

Update the cumulative lower confidence bound of reward based on reported features for arm i: X ⟨θ̂r,it , xt,it ⟩ − βr,i ∥xt,it ∥V −1 · 1(it = i). RLCBr,i = r,it

t∈Sr

Update the upper confidence bound of cumulative reward based on actual rewards for arm i: X p AUCBr,i = rt,it 1(it = i) + 2nr (i) log(4KR/δ).

8: 9: 10: 11:

for each arm i ∈ Ar−1 do if RLCBr,i > AUCBr,i then Eliminate arm i from set Ar−1 . else Update its estimated reward

t∈Sr

12:

P µ̂r,i =

t∈Sr

⟨θ̂r,it , xt,it ⟩ · 1(it = i) nr (i)

13: end if 14: end for 15: Update Ar as the set of min(|Ar−1 |, ⌈ 2Kr ⌉) arms in Ar−1 with largest µ̂r,i . 16: end for 17: Output the single arm iout in set AR .

A. Partition of Budget MESHA operates over a sequence of R = ⌈log2 K⌉ epochs. In the beginning, the algorithm initializes the active arm set as A0 = [K]. In each epoch r ∈ [R], the learner samples every active arm i ∈ Ar−1 for an equal number of rounds, denoted by nr . The per-arm sampling budget for epoch r is defined as: T nr = |Ar−1 |R

where |Ar−1 | is the number of active arms at the beginning of epoch r. As the algorithm progresses and the set Ar−1 shrinks, the per-arm budget nr increases. This sampling rule allows MESHA to obtain increasingly accurate reward estimates for the remaining candidates in Ar−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. Lemma 3.

R P r=1

|Ar−1 | · nr (i)1(i ∈ Ar−1 ) ≤ T .

Proof of Lemma 3. By definition of Ar−1 and nr (i) in line 18 and line 7 in algorithm 1, we have X r∈[R],i∈Ar−1

|Ar−1 | · nr (i) =

R X r=1

|Ar−1 | · ⌊

R R X X T T T ⌋≤ |Ar−1 | · = = T. |Ar−1 |⌈log2 K⌉ |Ar−1 |⌈log2 K⌉ r=1 ⌈log2 K⌉ r=1

Statistical Elim. (Suboptimal µ̂r,i )

Mechanism Elim. (Dishonest behavior)

1. Sampling & Estimation Ar−1

T Pull arm i with nr (i) = ⌊ |Ar−1 |⌈log ⌋ 2 K⌉ P ⊤ Vr,i = λId + t∈Sr xt,it xt,it −1 P θ̂r,i = Vr,i t∈Sr rt,it xt,it

Phase 1

···

2. Grin Trigger Condition

3. Halving

For each active arm i:

Empirical mean: P µ̂r,i = nr1(i) t ⟨θ̂r,i , xt,it ⟩

···

iout

Keep if RLCBr,i ≤ AUCBr,i

Eliminate if RLCBr,i > AUCBr,i

Ar−1

Phase r

Retain Top min(|Ar−1 |, ⌈ 2Kr ⌉)

AR−1

Phase R

Fig. 1. The pipeline of MESHA. In each epoch r, arms are first sampled uniformly and corresponding statistics are updated accordingly. The GTC check then eliminates arms exhibiting exceedingly dishonest behavior (Mechanism Elimination), and Sequential Halving removes the remaining suboptimal arms based on empirical means (Statistical Elimination). This process repeats over at most R = ⌈log2 K⌉ epochs until a single arm iout is identified.

B. Estimation of Active Arms At the end of each epoch r ∈ [R], to isolate the potential effects of strategic arms, MESHA maintains a unique estimator θ̂r,i for each arm i ∈ Ar−1 , which depends merely on the interaction history with arm i during epoch r: X −1 θ̂r,i = Vr,i rt,it xt,it 1(it = i), t∈Sr ⊤ t∈Sr xt,it xt,it 1(it

where Vr,i = λId + = i) and Sr is the set of all rounds within epoch r. Based on these individual estimators, the estimated mean of arm i is computed as follows: P ⟨θ̂r,i , xt,it ⟩ · 1(it = i) . µ̂r,i = t∈Sr nr (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. C. 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 xt,i , the learner’s estimator θ̂r,i would predict high rewards for arm i. However, true rewards depend merely on the unobserved true feature xi 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 RLCBr,i on rewards that are predicted using reported features, and an upper confidence bound AUCBr,i on rewards that are actually observed for all arm i ∈ Ar−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 4. 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. q Definition 4. (Grim Trigger Condition) Let βr,i = d log 1+nδrr (i) + 1. At the end of each epoch r, if arm i satisfies RLCBr,i > AUCBr,i , MESHA will eliminate arm i from the active set Ar and exclude it from all subsequent rounds, where X RLCBr,i := ⟨θ̂r,i , xt,i ⟩ − βr,i ∥xt,i ∥V −1 , r,i

t∈Sr ,it =i

AUCBr,i :=

X t∈Sr ,it =i

rt,it +

p 2nr (i) log(2/δr ).

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 − δ, the event   r  X  n (i) log(2KR/δ) r E noise := (rt,it − µi ) ≤ , ∀r ∈ [R], ∀i ∈ Ar−1   2 t∈Sr ,it =i

holds. Conditioned on this event, we can characterize the equilibrium behavior of arms as follows. Lemma 5. Fix any strategy profile σ ∈ NE(MESHA). For any epoch r ∈ [R] and any arm i ∈ Ar−1 , arm i must pass the GTC check at the end of epoch r conditioned on event E noise . D. Failure probability bound of MESHA Given a fixed budget T , we now characterize the (ζ, T )-PAC failure probability bound for MESHA assuming a corresponding Nash Equilibrium. Theorem 6. If the strategy profile σ forms a Nash Equilibrium under MESHA, then for any target accuracy ζ satisfying p 12d K log2 K log(1 + T ) √ , ζ≥ T MESHA is with   ⌈log2 K⌉2 T  . exp − P ∆iout ≥ ζ ≤ T T 18 K2 d2 log 1 + ζ

⌈log2 K⌉

Theorem 6 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 d2 log T in the exponent denominator are due to the strategic arms as elaborated in the Remark 7. Remark 7 (Origins of K and d2 log T in the Exponent). First, the K factor arises from the possibility of incorrect elimination of the optimal arm i∗ during epoch r = 1. Specifically, under uniform sampling, each arm is pulled n1 = ⌊T /(KR)⌋ times during r = 1. The optimal arm i∗ may be eliminated during epoch r = 1 if some suboptimal arm i ̸= i∗ achieves a higher estimated mean reward than i∗ , i.e., µ̂1,i ≥ µ̂1,i∗ . Applying a union bound over the probalities of such events for all K − 1 2 suboptimal arms, the failure probability due to elimination in epoch r = 1 scales as K · exp(−ζ 2 /ω1,i ). As substituting 2 2 n1 ∝ T /K implies ω1,i ∝ K/T , the failure probability becomes exp(−T ζ /K), which explicitly yields the K factor. Since epoch r = 1 is with the smallest per-arm budget n1 and ωr,i is decreasing in nr , the failure probability due to epoch 1 results as the bottleneck of analyzing MESHA. √ Second, the d2 log T factor arises from the epoch-wise GTC check step: the confidence radius qP βr,i = O( d log n √r ) roots 2 ≤ ∥x ∥ from the application of elliptical potential lemma introduced by [11], and the trace bound d roots −1 t,i t:it =i V r,i

from the definition of Vr,i . When we bound the strategic deviation of arms under Nash Equilibrium, these two terms leads to the (d2 log T ) factor. Both terms persist under any reporting strategy and are mutually independent. In contrast, OD-LinBAI achieves a tighter d factor in non-strategic environment [1] because under G-optimal design, the optimal allocation √ π satisfies −1 d from the maxi x⊤ V (π) x ≤ d by definition, which directly bounds the prediction uncertainty without the additional i i trace identity. More explanation can be found in Appendix F. However, as we will show in Section IV, G-optimal design is fundamentally vulnerable to strategic manipulation and its theoretical guarantee would collapse. E. Performance Evaluation of MESHA To evaluate MESHA’s BAI performance, we compare the failure probability bound of MESHA established in Theorem 6 against the bounds of two natural baselines, as summarized in Table I. 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 ζ-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 − T /(H2 log2 K) where H2 = maxi i∆−2 (i) , and is naturally robust to strategic manipulation since it has no access to feature vectors. However, H2 can

TABLE I T HEORETICAL C OMPARISON BETWEEN MESHA AND BASELINES Algorithm

Setting

Sampling Rule

MESHA (Ours)

Strategic Linear

Uniform

Classical SH [22]

Stochastic

Uniform

OD-LinBAI [1]

Linear

G-optimal

Exponential Decay Rate T exp − (K/ζ 2 )·d 2 log T 2 T exp − H log 2 2K T exp − d log d 2

Strategic Robustness Yes (under NE) Yes (feature-free) No (truthful arms only)

be significantly larger than (K/ζ 2 )d2 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, ζ = 0.1, where arm 1 is the optimal arm, arm 2 √ is with suboptimality gap ∆2 = ζ/(2d K) ≈ 0.003, and the remaining arms i ∈ {3, . . . , 16} are with suboptimality gap −2 2 2 ∆i = 2ζ = 0.2. In this case, H2 = max(1 · ∆−2 ) = ∆−2 2 , 2 · (2ζ) 2 = 102400 ≫ 25600 = (K/ζ )d , indicating that the failure probability of SH can be far higher than that of MESHA. We note that since ∆2 < ζ, 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 ζ-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 − T /(d log2 d) because under G−1 optimal design, the optimal allocation π satisfies maxi x⊤ xi ≤ d by definition, which naturally bounds the prediction i V (π) 2 uncertainty with a single d factor rather than d . However, this advantage relies heavily on optimal design-based sampling and is fundamentally vulnerable to the strategic setting: as to be elaborated in Section IV, 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. IV. F URTHER D ISCUSSION ON A LGORITHMS FOR L INEAR 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. A. 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. Example 8. Consider a 2-armed linear bandit. The true action space is defined as X = {x1 , x2 }, where x1 = (0.9, 0) and x2 = (0.1, 0). The unknown environment parameter is θ∗ = (1, 0). At any round t, pulling arm it yields a noisy reward rt,it = ⟨θ∗ , xit ⟩+ηt , where ηt ∼ Unif(−0.05, 0.05). Consequently, the true expected rewards are µ1 = 0.9 (the optimal arm) and µ2 = 0.1. Suppose both arms strategically report identical features to a G-optimal design-based learner: xt,1 = xt,2 = (1, 0) for all t ∈ [T ]. Then the learner is unable to distinguish the two arms, and the failure probability approaches 1/2. Proof. Observing the reported set X̃ = {x̃1 = (1, 0), x̃2 = (1, 0)}, any sampling rule based on G-optimal design will allocate pulls uniformly between the two arms. The learner computes the global least-squares estimator θ̂t as: θ̂t =

t X s=1

xs,is x⊤ s,is

t −1 X

xs,is rs,is .

s=1

Since the reported features have a non-zero component only in the first dimension, the first element of the estimator simplifies to: t 1X (1) θ̂t = rs,is . t s=1

(1)

By the Law of Large Numbers, as t → ∞, θ̂t → E[r] = 0.9 × 0.5 + 0.1 × 0.5 = 0.5. Thus, the empirical mean of both arms approaches 0.5 when the algorithm proceeds, and the learner is unable to distinguish the optimal arm, resulting in an failure probability approaching 1/2. In Example 8, 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. B. Vulnerability of OD-LinBAI with Mechanism Design The failure of OD-LinBAI in Example 8 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 2. 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 D. Theorem 9. Let x1 , · · ·P , xK ∈ Rd . Suppose there exists an index j and non-negative coefficients {λi }i∈[K]\{j} such that P i̸=j λi ≤ 1 and xj = i̸=j λi xi . Then, in the G-optimal design problem: min

−1 max x⊤ xi , i V (ω)

ω∈∆K i=1,...,K

there exists an optimal allocation ω

∗

V (ω) =

K X

ωi x i x ⊤ i ,

i=1

such that ωj∗ = 0.

Theorem 9 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. Example 10. Consider a 3-armed bandit with budget T . The true action space consists of x1 = (0.5, 0, 0) and x2 = x3 = (0.45, 0, 0). Given the true parameter θ∗ = (1, 0, 0), the expected rewards are µ1 = 0.5 (the optimal arm) and µ2 = µ3 = 0.45. The noisy reward follows rt,it = µit + ηt , where ηt ∼ N (0, σ 2 ). When arms 2 and 3 strategically coordinate their reported features to starve arm 1 of any pulls. Then arm 1 can be deterministically eliminated, leading to a identification failure of OD-LinBAI-GTC. Proof. Suppose the arms adopt the following strategies: • Arm 1: Reports xt,1 = (0, 1/2, 1/6). ∗ ∗ • Arm 2: Reports xt,2 = (0, 0.9, 0) with pseudo-parameter θ2 = (0, 0.5, 0.5) satisfying ⟨θ2 , xt,2 ⟩ = 0.45 = µ2 . ∗ ∗ • Arm 3: Reports xt,3 = (0, 0, 0.9) with pseudo-parameter θ3 = (0, 0.5, 0.5) satisfying ⟨θ3 , xt,3 ⟩ = 0.45 = µ3 . 5 5 5 20 5 Since xt,1 = 9 xt,2 + 27 xt,3 with 9 + 27 = 27 < 1, Theorem 9 guarantees there exists an optimal G-design allocation ω ∗ with ω1∗ = 0, so OD-LinBAI exclusively samples Arms 2 and 3 throughout. Since the true rewards of Arms 2 and 3 are generated from their true features as rt,i = ⟨θ∗ , xi ⟩ + ηt = 0.45 + ηt , and their pseudo-parameters satisfy ⟨θi∗ , xt,i ⟩ = 0.45 = µi , the GTC-predicted rewards are consistent with the observed rewards, so Arms 2 and 3 can pass the GTC check. Since only Arms 2 and 3 are sampled and their reported features have zero first coordinate, the global OLS estimator satisfies θ̂t → θ2∗ (= θ3∗ ) as t → ∞. When t grows, the estimate of Arm 1 approaches ⟨θ2∗ , xt,1 ⟩ = 0.4 < 0.45, so Arm 1 is ranked below Arms 2 and 3 and deterministically eliminated, causing identification failure. 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.

C. 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 it = i, we have ⟨θ∗ , x∗t,i ⟩ = ⟨θi∗ , xt,i ⟩,

(5)

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 10 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 θ2∗ and θ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 (5), 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 5, 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. Assumption 11. For any arm i pulled at round t, the strategic deviation satisfies: ⟨θi∗ , xt,i ⟩ − ⟨θ∗ , xi ⟩ ≤ ε. 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 ε, 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 D. Theorem 12. Conditioned on Assumption 11, any arm i passing the GTC check of MESHA at the end of epoch r satisfies: s ! p log(2/δr ) βr,i +ε , 2d log(1 + nr (i)) + 3 ε̄r,i ≤ p nr (i) nr (i) P where ε̄r,i = nr1(i) t∈Sr ,it =i (⟨θi∗ , xt,i ⟩ − µi ) represents the average per-round strategic deviation of arm i during epoch r. Theorem 12 implies that the epoch-wise GTC check in MESHA actively constrains the strategic behavior of any surviving arm: the average deviation ε̄r,i is bounded in terms of the confidence radius βr,i and the number of pulls nr (i). As nr (i) grows, this bound tightens, indicating that arms face increasingly stringent constraints on their strategic behavior as the MESHA algorithm progresses. Furthermore, when ε = 0, Assumption 11 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. V. N UMERICAL E XPERIMENTS We evaluate MESHA against five baselines: Sequential Halving [22], Successive Rejects [21], OD-LinBAI [1], OD-LinBAIGTC (introduced in Section IV-B) and OptGTM [4]. We construct several strategic instances motivated by the starvation attack described in Section IV. As baseline algorithms are generally designed for optimal arm identification, we set ζ = ∆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 G. A. Overall Comparison In Figure 2b, we vary T ∈ {60, 100, . . . , 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 6. 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 IV. 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.

1.0

OD-LinBAI

0.8

BAI failure probability

OD-LinBAI-GTC Successive Rejects Sequential Halving OptGTM MESHA

0.6

0.4

0.2

OD-LinBAI* 0.0

100

200

300

400

500

600

700

800

Budget T

(b) Impact of Budget T 0.50

0.6

0.45

0.35

BAI failure probability

0.40

0.30 0.25 0.20 0.15

0.5

0.4

0.3

0.10

0.2

0.05 0.00

Feature dimension d

Number of arms K

(d) Impact of Arm Count K

Fig. 2. Empirical BAI failure probability of all algorithms under the strategic instance except for that OD-LinBAI* represents OD-LinBAI itself when facing truthful arms. We compare MESHA against 5 baseline algorithms. (b) With fixed K = 8, d = 3 and varying T : OD-LinBAI fail as T grows while MESHA and OptGTM achieve consistent failure decay. Sequential Halving and GSE decrease slowly due to lack of feature information. (c) With fixed K = 64, T = 1,500 and varying d: MESHA consistently outperforms OptGTM; OD-LinBAI* starts with lower failure probability at small d but performs similarly to MESHA as d grows. (d) With fixed d = 6, T = 1,500 and varying K: MESHA maintains the lowest failure probability across all arm counts, with the margin over GSE and SH widening as K increases.

B. Impact of Feature Dimension and Arm Count In Figure 2c and Figure 2d, 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 6 shows that the failure probability grows with both d2 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. a) Varying d: With K = 64 fixed, we vary d ∈ {3, 6, 9, 18, 24} to evaluate the impact of feature dimension on MESHA’s performance. Although Theorem 6 shows an O(d2 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 (≈ 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 d2 term in Theorem 6, MESHA is a practically competitive algorithm at large d: it achieves success probability comparable to the oracle baseline OD-LinBAI*. b) Varying K: With d = 6 fixed, we vary K ∈ {16, 24, 32, 64} to evaluate the impact of arm count on MESHA’s performance. Although Theorem 6 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. VI. P ROOF S KETCH OF T HEOREM 6 The key technical challenge in analyzing the failure probability of MESHA is that arms’ strategic behaviors corrupt the feature-based estimators θ̂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. 2 T ζ2 Lemma 13. Let δ = ⌈log2T K⌉ exp − 18Kd2 log2 (1+T and define a “good event” based on the the learner’s observed /⌈log2 K⌉) rewards as:   r   X n (i) log(2KR/δ) r , ∀r ∈ [R], ∀i ∈ Ar−1 . E noise := (rt,it − µi ) ≤   2 t∈Sr ,it =i

Then E

noise

holds with probability at least 1 − δ.

Conditioned on E noise , Lemma 5 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. 2 T ζ2 Lemma 14. Let δ = ⌈log2T K⌉ exp − 18Kd2 log2 (1+T and assume E noise holds. For any arm i ∈ Ar−1 during epoch /⌈log2 K⌉) r ∈ [R], arm i can pass the GTC check only if µ̂r,i ≤ µi + ωr,i , s r r−1 where ωr,i = 4d ⌈K/2N ⌉ log 1 + ⌈K/2Nr−1 ⌉ + log 1 + ⌈K/2Nr−1 ⌉ log(2KR/δ) and N = ⌈logT K⌉ . 2

With Lemmas 5, 13 and 14 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 5), so the strategic deviation bound µ̂r,i ≤ µi + ωr,i holds for all active arms conditioned on E noise . If the optimal arm i∗ is incorrectly eliminated at epoch r∗ , there must exist a suboptimal arm i with µ̂r∗ ,i ≥ µ̂r∗ ,i∗ , which combined with Lemma 14 indicates ∆i ≤ ωr∗ ,i∗ + ωr∗ ,i . Setting δr = δ/(KR) and summing them up over all epochs yields the upper bound of MESHA’s failure probability in Theorem 6. Remark 15. We can also define the event E est := {θ∗ ∈ Cr,i : ∀r ∈ [R], i ∈ Ar−1 } q r (i)) }. When all arms report truthfully, E est holds with probability with Cr,i = {θ ∈ Rd : ∥θ̂r,i − θ∥Vr,i ≤ d log KR(1+n δ at least 1 − δ and then all arms pass GTC check (the proof is in Appendix C). [4] analyzes the regret bound of OptGTM for strategic linear contextual bandits conditioned on a similar event with E est (Assumption in Lemma E.1 of [4]). However, E est does not hold under strategic reporting: each arm i reports manipulated features, so the estimator θ̂r,i is built on corrupted knowledge and may diverge from θ∗ . In particular, E est requires θ∗ to lie in the confidence ellipsoid of a single global estimator, which is not likely to happen when different arms report different manipulated features. Crucially, our analysis is independent of whether E est holds. Instead, MESHA triggers every active arm to pass the GTC check under Nash Equilibrium, which by Lemma 5 is a necessary condition under any Nash Equilibrium. Under this condition, E noise holds with probability at least 1 − δ, since it depends only on the concentration of true rewards around their means and is independent of the reported features. Importantly, each arm i maintains its own per-arm estimator θ̂r,i , which may converge to a different value than θ∗ ; what matters is not where θ̂r,i converges, but rather what the GTC check implies about the empirical mean µ̂r,i . VII. C ONCLUSION AND F UTURE D IRECTIONS 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 (ζ, T )-PAC failure probability bound showing that MESHA identifies a near-optimal arm with high probability. our upper bound reveals an O(d2 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 O(d2 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.

Appendices 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 A provides basic facts used in our analysis. Appendix B proves Lemma 5, showing that passing the GTC is a necessary condition for arms maximizing utilities under any Nash Equilibrium. Appendix C completes the proof of our main result, Theorem 6, along with two supporting lemmas introduced in Section VI. Appendix D proves Theorem 9, which establishes the theoretical foundation for the starvation attack in Section IV. Appendix D proves Theorem 12, bounding the average strategic deviation of any arm that survives the GTC. Appendix E presents the pseudo-code of OD-LinBAI-GTC, which combines OD-LinBAI [1] with epoch-wise GTC mechanism. Appendix F investigates the tightness of the O(d2 log T ) in Theorem 6: we show that the additional d2 factor as the cost of bounding strategic deviation is simultaneously achievable by an explicit reporting strategy, and conjectures that the d2 factor is unavoidable for any algorithm including epoch-wise GTC mechanism and feature-independent sampling rules. Finally, Appendix G provides additional experimental details. A PPENDIX A U SEFUL FACTS Here are some useful facts that are applied in our proof. ∞ Theorem 16. (Confidence Ellipsoid, Theorem 2 in [11]) Let {Ft }∞ t=0 be a filtration. Let {ηt }t=1 be a real-valued stochastic process such that ηt is Ft -measurable and ηt is conditionally R-sub-Gaussian for some R ≥ 0 i.e. 2 2 λ R . ∀λ ∈ R E eληt | Ft−1 ≤ exp 2 d Let {Xt }∞ t=1 be an R -valued stochastic process such that Xt is Ft−1 -measurable. Assume that V is a d × d positive definite matrix. For any t ≥ 0, define t t X X ⊤ ηs Xs . Xs Xs St = Vt =V + s=1

s=1

Furthermore, we let V = λI, λ > 0, define Yt = ⟨Xt , θ∗ ⟩ + ηt and assume that ∥θ∗ ∥2 ≤ S and for all t ≥ 1, ∥Xt ∥2 ≤ L then with probability at least 1 − δ, for all t ≥ 0, θ∗ lies in the set s ( ) 1 + tL2 /λ ′ d 1/2 b Ct = θ ∈ R : ∥θt − θ∥V t ≤ R d log +λ S . δ Theorem 17. (Hoeffding Inequality, Theorem 2 in [32] If X1 , X2 , · · · , Xn are independent and ai ≤ Xi ≤ bi (i = 1, 2, · · · , n), then for t > 0 2 2 Pn 2 Pr X − µ ≥ t ≤ e−2n t / i=1 (bi −ai ) . A PPENDIX B P ROOF OF L EMMA 5 Lemma 5. Fix any strategy profile σ ∈ NE(MESHA). For any epoch r ∈ [R] and any arm i ∈ Ar−1 , arm i must pass the GTC check at the end of epoch r conditioned on event E noise . Proof. Consider a fixed epoch r and a history Hr−1 = {(xt,it , rt,it )}t≤tr at the commencement of epoch r. Assume arm i ∈ Ar−1 is active and that Hr−1 is reachable with strictly positive probability under the strategy profile σ. We proceed by contradiction. Suppose that under strategy σi , arm i fails the GTC check at the end of epoch r, conditioned on the good event E true . By the design of MESHA, an arm that fails the GTC check at epoch r is eliminated immediately and permanently from all subsequent epochs. Since the utility Ui is defined as the probability of being identified as the best arm iout , and a permanently eliminated arm can never be identified as iout , the utility of arm i from this history onward is zero: Ui (MESHA, {σi , σ −i } | Hr−1 , E noise ) = 0. Now consider a unilateral deviation to a calibrated strategy σi0 from history Hr−1 onward, which satisfies the mean-matching condition ⟨θi∗ , xt,i ⟩ = µi for all subsequent pulls. On the good event E noise , the concentration of reward noise and the definition of the confidence bounds guarantee that arm i passes the GTC check at the end of epoch r under σi0 . Conditioned on passing the GTC check, arm i remains in the active set Ar and continues to compete in subsequent epochs. Since the sequential halving rule retains the top ⌈K/2r ⌉ arms based on empirical means, and the reward noise has nondegenerate support, arm i has a strictly positive probability of achieving a sufficiently high empirical mean to survive every

subsequent epoch and be ultimately output as iout , regardless of whether i is the optimal arm. Therefore, the expected utility under this deviation is strictly positive: Ui (MESHA, {σi0 , σ −i } | Hr−1 , E noise ) > 0. This means σi0 is a profitable deviation from Hr−1 , which contradicts the assumption that σ is a Nash Equilibrium. Therefore, conditioned on E noise , every active arm must pass the GTC check at the end of each epoch under any Nash Equilibrium. A PPENDIX C P ROOF OF T HEOREM 6 Throughout this section, we set  2 T ζ2 ⌈log2 K⌉ exp− δ= T 18Kd2 log2 1 +

 T ⌈log2 K⌉

 ,

δr =

δ , KR

R = ⌈log2 K⌉,

T . ⌈log2 K⌉

We first establish two supporting lemmas before proving the main result. 2 T ζ2 Lemma 13. Let δ = ⌈log2T K⌉ exp − 18Kd2 log2 (1+T and define a “good event” based on the the learner’s observed /⌈log2 K⌉) rewards as:   r  X  nr (i) log(2KR/δ) (rt,it − µi ) ≤ E noise := , ∀r ∈ [R], ∀i ∈ Ar−1 .   2 t∈Sr ,it =i

Then E noise holds with probability at least 1 − δ. Proof. Fix any epoch r ∈ [R] and arm i ∈ Ar−1 . Let Ft−1 = σ({xs,is , rs,is }s<t ) denote the natural filtration generated by all observations up to round t − 1. Given ∥x∗i ∥2 ≤ 1 for all arms i ∈ [K] and ∥θ∗ ∥2 ≤ 1, each reward satisfies rt,it − µi = ⟨θ∗ , x∗it ⟩ − µi + ηt ∈ [−2, 2] almost surely. Furthermore, E[rt,it − µi | Ft−1 ] = 0, and hence the sequence {rt,it − µi }t∈Sr ,it =i forms a martingale difference sequence with respect to Ft−1 . Applying Azuma’s inequality to the sum of nr (i) such terms:   r X n (i) log(2/δ ) r r  ≤ δr . P (rt,it − µi ) > 2 t∈Sr ,it =i

For each pair (r, i) with r ∈ [R] and i ∈ Ar−1 , define the bad event   r   X n (i) log(2/δ ) r r noise . Br,i := (rt,it − µi ) >   2 t∈Sr ,it =i

noise From the bound above, P(Br,i ) ≤ δr for each pair (r, i). Since there are at most R · K such pairs, applying the union bound

implies:

P (E noise )c ≤

X r∈[R], i∈Ar−1

noise P(Br,i ) ≤ KR · δr = KR ·

δ = δ. KR

Therefore P(E noise ) ≥ 1 − δ, completing the proof.

The following proof is for the probability of E est defined in Remark 15 when all arms report truthfully.

Proof of Remark 15. Fix any epoch r ∈ [R] and arm i ∈ Ar−1 . Under truthful reporting, the estimator θ̂r,i is computed via ridge between the learner and arm i during epoch r, with design matrix Vr,i = P regression on the interaction history P ∗ ∗ λId + t∈Sr ,it =i xt,i x⊤ t,i and response vector t∈Sr ,it =i rt,it xt,i . The rewards satisfy rt,it = ⟨θ , xit ⟩ + ηt where ηt is ξ-sub-Gaussian. By the elliptical potential lemma for ridge regression [11], with probability at least 1 − δr : s 1 + nr (i) ∗ + 1. ∥θ̂r,i − θ ∥Vr,i ≤ βr,i , where βr,i = d log δr By the definition of Cr,i , this is equivalent to θ∗ ∈ Cr,i , so P(θ∗ ∈ / Cr,i ) ≤ δr . For each pair (r, i) with r ∈ [R] and i ∈ Ar−1 , define the bad event est Br,i := {θ∗ ∈ / Cr,i }.

est ) ≤ δr . Since there are at most R · K such pairs, the union bound gives From the bound above, P(Br,i   [ X δ est  est P (E est )c = P Br,i ≤ P(Br,i ) ≤ KR · δr = KR · = δ. KR r∈[R], i∈Ar−1

r∈[R], i∈Ar−1

Hence P(E est ) ≥ 1 − δ.

2 T ζ2 and assume E noise holds. For any arm i ∈ Ar−1 during epoch Lemma 14. Let δ = ⌈log2T K⌉ exp − 18Kd2 log2 (1+T /⌈log2 K⌉) r ∈ [R], arm i can pass the GTC check only if µ̂r,i ≤ µi + ωr,i , s r r−1 where ωr,i = 4d ⌈K/2N ⌉ log 1 + ⌈K/2Nr−1 ⌉ + log 1 + ⌈K/2Nr−1 ⌉ log(2KR/δ) and N = ⌈logT K⌉ . 2

δ implies: Proof. By the definition of the GTC check, an arm i passing the check at epoch r with δr = 2KR s X X nr (i) 2 ⟨θ̂r,i , xt,i ⟩ − βr,i ∥xt,i ∥V −1 ≤ rt,it + log . r,i 2 δr t∈Sr ,it =i

t∈Sr ,it =i

Rearranging and using

t∈Sr ,it =i rt,it ≤ nr (i)µi +

X t∈Sr ,it =i

nr (i) 2 2 log δr

⟨θ̂r,i , xt,i ⟩ ≤ nr (i)µi +

from E noise : r βr,i ∥xt,i ∥V −1 + r,i

t∈Sr ,it =i

2nr (i) log

2 . δr

Dividing both sides by nr (i): X βr,i µ̂r,i ≤ µi + ∥xt,i ∥V −1 + r,i nr (i) t∈Sr ,it =i | {z }

2 log(2/δr ) . nr (i)

(6)

(♠)

We bound (♠) using the Cauchy-Schwarz inequality and the elliptical potential lemma [11]: X βr,i βr,i p ∥xt,i ∥V −1 ≤ p 2d log(1 + nr (i)). r,i nr (i) nr (i) t∈Sr ,it =i q δ Substituting βr,i = d log 1+nδrr (i) + 1, δr = KR , and nr (i) = ⌈K/2Nr−1 ⌉ into (6) yields µ̂r,i ≤ µi + ωr,i , where # "s s √ N N ⌈K/2r−1 ⌉ ⌈K/2r−1 ⌉ 2KR + log log 1 + log 1 + , ωr,i = (2 2d + 1) N ⌈K/2r−1 ⌉ N ⌈K/2r−1 ⌉ δ completing the proof. Now we are ready to prove Theorem 6. Proof of Theorem 6. Fix any strategy profile σ ∈ NE(MESHA). With δ and δr as defined at the beginning of this appendix, Lemma 13 guarantees that E true holds with probability at least 1 − δ. We condition on E true for the remainder of the proof. Bounding µ̂r,i . By Lemma 5, under σ ∈ NE(MESHA), every active arm passes the GTC check at every epoch. By Lemma 14, for any arm i ∈ Ar−1 and epoch r ∈ [R]: µ̂r,i ≤ µi + ωr,i , conditioned on E

true

. Now we would like to show µ̂r,i ≥ µi − ωr,i

also holds by contradiction. Assume the contrary that under some σ ∈ NE(MESHA), there exists an epoch r, an active arm i, and a reachable history such that, conditioned on E noise , arm i attains µ̂r,i < µi − ωr,i with positive probability under σi . Besides, let σi′ denote the strategy σi′ that is with empirical mean µ̂′r,i such that < µi − ωr,i < µ̂′r,i < µi + ωr,i . When σi′ is applied, Remark 15 implies that arm i can also the GTC. As σi′ apparently yields a larger µ̂r,i than σi and thus strictly increases arm i’s utility function (probability of being ultimately selected), the assumption σ ∈ NE(MESHA) is contradicted. Hence, under any Nash equilibrium, µ̂r,i ≥ µi − ωr,i .

Therefore µ̂r,i ∈ [µi − ωr,i , µi + ωr,i ] holds conditioned on E noise , for all active arms and all epochs. Bounding ω. Since ωr,i is maximized at epoch r = 1 where ⌈K/20 ⌉ = K: "r # r √ 2KR K K ωr,i ≤ ω1,i ≤ (2 2d + 1) log(1 + N ) + log(1 + N ) log =: ω ∗ . N N δ Hence ω := maxr, i∈Ar−1 (ωr,i∗ + ωr,i ) ≤ 2ω ∗ . Failure event analysis. By Lemma 5, the optimal arm i∗ can only be eliminated via the sequential halving step. Let ∗ ri∗ = max{r : i∗ ∈ Ar−1 } denote the epoch at which i∗ is incorrectly eliminated. For any suboptimal arm i ∈ Ari∗∗ that survives over i∗ , the empirical ordering µ̂ri∗∗ ,i∗ ≤ µ̂ri∗∗ ,i gives: µi∗ − ω ∗ ≤ µ̂ri∗∗ ,i∗ ≤ µ̂ri∗∗ ,i ≤ µi + ω ∗ ,

hence ∆i = µi∗ − µi ≤ 2ω ∗ . Setting ζ = 2ω ∗ : and therefore:

P ∆iout ≥ ζ ≤ P E

true c

c ∆iout ≥ ζ ⊆ E noise ,  T ζ2 ⌈log2 K⌉2 exp− ≤δ= T 18Kd2 log2 1 +

 T ⌈log2 K⌉

 ,

which completes the proof. A PPENDIX D P ROOF OF T HEOREM 12 We first establish a supporting lemma on the concentration of the ridge regression estimator under strategic manipulation, then prove the main result. Lemma 18. Under Assumption 11, for any arm i in epoch r, the ridge regression estimator θ̂r,i satisfies the following concentration bound with probability at least 1 − δ: p |⟨θ̂r,i − θi∗ , x⟩| ≤ βr,i + ε nr (i) ∥x∥V −1 , ∀x ∈ Rd , r,i q where βr,i = d log 1+nδr (i) + 1. −1 P Proof. Define the auxiliary estimator θ̃r,i = Vr,i t∈Sr :it =i (rt,it + εt,i )xt,i , which is an unobservable estimator based on {(xt,it , rt,it + εt,i )}t∈Sr ,it =i . Applying Theorem 16 with S = L = λ = 1, θ̂t = θ̃r,i , Yt = rt,i + εt,i and V̄t = Vr,i , we have that |(θ̃r,i − θi∗ )⊤ x| ≤ ∥θ̃r,i − θi∗ ∥Vr,i ∥x∥V −1 ≤ βr,i ∥x∥V −1 r,i r,i q holds with probability at least 1 − δr , where βr,i = d log( 1+nδr (i) ) + 1. Expanding the expression actual estimator θ̂r,i and applying the triangle inequality yields: ⊤  X −1 |⟨θ̂r,i − θi∗ , x⟩| = Vr,i rt,i xt,i − θi∗  x t∈Sr ,it =i

⊤

 X

−1 = Vr,i

−1 (−εt,i )xt,i  x + Vr,i

t∈Sr ,it =i

≤ ≤

X t∈Sr ,it =i

(rt,i + εt,i ) − θi∗  x

−1 ∗ ⊤ εt,i x⊤ t,i Vr,i x + |(θ̃r,i − θi ) x|

−1 εt,i x⊤ t,i Vr,i x + βr,i ∥x∥V −1 , r,i

t∈Sr ,it =i

⊤



(7)

where εt,i = ⟨θi∗ , xt,i ⟩ − ⟨θ∗ , x∗i ⟩ is the round-wise strategic bias. Note that εt,i ≤ ε for all t ∈ [T ] and i ∈ [K]. By applying the Cauchy-Schwarz inequality, we have X t∈Sr ,it =i

s −1 ≤ ε εt,i x⊤ V x nr (i) t,i r,i

−1 2 (x⊤ t,i Vr,i x)

t∈Sr ,it =i

s = ε nr (i)

−1 −1 x⊤ Vr,i xt,i x⊤ t,i Vr,i x

t∈Sr ,it =i

q −1 −1 = ε nr (i)x⊤ Vr,i (Vr,i − Id×d )Vr,i x q −1 x ≤ ε nr (i)x⊤ Vr,i p = ε nr (i)∥x∥V −1 .

(8)

r,i

By substituting (8) into (7), we can complete this proof. Proof of Theorem 12. By the definition of GTC, under Nash Equilibrium, Lemma 5 implies that for any arm i ∈ Ar−1 and t ∈ Sr , we have X X p ⟨θ̂r,i , xt,i ⟩ − βr,i ∥xt,i ∥V −1 ≤ rt,i + 2nr (i) log(2/δr ). (9) r,i

t∈Sr ,it =i

By Lemma 18, under the good event E

true

, the term ⟨θ̂r,i , xt,i ⟩ satisfies: p ⟨θ̂r,i , xt,i ⟩ ≥ ⟨θi∗ , xt,i ⟩ − βr,i + ε nr (i) ∥xt,i ∥V −1 . r,i

Substituting this into the LHS of (9): LHS ≥

X t∈Sr ,it =i

⟨θi∗ , xt,i ⟩ −

2βr,i + ε

t∈Sr ,it =i

Substituting rt,i = µi + ηt,i into the RHS and rearranging (9): X X p (⟨θi∗ , xt,i ⟩ − µi ) ≤ 2βr,i + ε nr (i) t∈Sr ,it =i

t∈Sr ,it =i

nr (i) ∥xt,i ∥V −1 .

∥xt,i ∥V −1 +

r,i

ηt,i +

2nr (i) log(2/δr ).

t∈Sr ,it =i

p P −1 ≤ Dividing by nr (i) and applying the elliptical potential bound 2dnr (i) log(1 + nr (i)) and the noise t ∥xt,i ∥Vr,i concentration bound from E noise : s ! p 2βr,i log(2/δr ) ε̄r,i ≤ p +ε 2d log(1 + nr (i)) + 3 . nr (i) nr (i) Simplifying the constants completes the proof. A PPENDIX E OD-L IN BAI-GTC In Section V, 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 2. Following standard epoch-based elimination algorithms, the epochwise allocation parameter m is defined as: P⌈log2 d⌉−1 d T − min K, d(d+1) − r=1 ⌈ 2r ⌉ 2 m= . (10) ⌈log2 d⌉

As analyzed in Section IV, 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.

Algorithm 2 OD-LinBAI Combined with GTC Mechanism 1: Input: budget T , arm set A = [K], reported vectors {x1,1 , · · · , x1,K } ⊂ Rd in the first round and λ. 2: Initialize: t0 = 0, A0 = A, d0 = d 3: Compute m according to (10) 4: for r = 1 to ⌈log2 d⌉ do 5: dr = dim (span ({x̄r−1,i : i ∈ Ar−1 })) 6: if dr ̸= dr−1 then 7: Find Br ∈ Rdr−1 ×dr whose columns form an orthonormal basis of span ({x̄r−1,i : i ∈ Ar−1 }) 8: for each arm i ∈ Ar−1 do 9: x̄r−1,i ← Br⊤ x̄r−1,i 10: end for 11: end if 12: if r = 1 then 13: Pull each arm i ∈ Ar−1 uniformly for Tr (i) = ⌈m/K⌉ times 14: else 15: Update average historical features in epoch r for each arm i ∈ Ar−1 : X 1 xt,i · 1(it = i) ∀i ∈ Ar−1 x̄r−1,i = Tr−1 (i) t∈Sr−1

16: 17: 18:

Compute G-optimal design πr : {x̄r−1,i : i ∈ Ar−1 } → [0, 1] and set Tr (i) = ⌈πr (i) · m⌉ and pull each arm i ∈ Ar−1 accordingly end if Update the global statistics Vr and θ̂r : X X Vr = xt,it x⊤ θ̂r = Vr−1 xt,it rt,it t,it , t∈Sr

t∈Sr

for each arm i ∈ Ar−1 do Compute empirical mean: µ̂r,i = ⟨θ̂r , x̄r,i ⟩ end for Apply GTC: eliminate any arm i ∈ Ar−1 with RLCBr,i > AUCBr,i Update Ar to retain the min{|Ar−1 |, ⌈d/2r ⌉} arms with largest µ̂r,i 24: Update tr+1 = tr + Tr 25: end for 26: Return the unique arm iout in A⌈log2 d⌉

19: 20: 21: 22: 23:

A PPENDIX F T IGHTNESS OF T HE d2 P ENALTY This section provides a structural analysis of the O(d2 log T ) penalty in Theorem 6. We revisit the derivation of ωr,i from the proof of Lemma 14. Starting from this lemma’s GTC-derived bound, any arm i surviving the GTC at epoch r satisfies s βr,i X 2 log(2/δr ) µ̂r,i ≤ µi + ∥xt,i ∥V −1 + . (11) r,i nr nr t∈Sr , it =i

Applying the Cauchy-Schwarz inequality to the middle term: sX βr,i X βr,i ∥xt,i ∥V −1 ≤ √ ∥xt,i ∥2V −1 . r,i nr t: i =i nr t: i =i r,i t

(12)

We bound the two factors √ on the right-hand side separately. a) First factor (first d) – confidence radius: By the elliptical potential lemma [11], the ridge regression confidence radius satisfies r 1 + nr βr,i ≤ (d + 1) log , (13) δr where we have log(1 + nr /(λd)) ≤ log(1 + nr ) for λ ≥ 1/d. This bound holds for any reported feature sequence, as it is derived from Theorem 16 and does not depend on the arms’ reporting strategies.

b) Second factor (second Vr,i − λId , and therefore,

√

d) – potential sum: By the definition Vr,i = λId +

X t: it =i

−1 ∥xt,i ∥2V −1 = tr Vr,i (Vr,i − λId ) r,i

⊤ t: it =i xt,i xt,i , we have

−1 = d − λ tr(Vr,i ) ≤ d,

⊤ t: it =i xt,i xt,i =

(14)

−1 where the last inequality uses tr(Vr,i ) ≥ 0. This bound holds for any reported feature sequence with ∥xt,i ∥2 ≤ 1, and follows purely from the definition of Vr,i without invoking the elliptical potential lemma [11]. c) Combining the two factors: Substituting (13) and (14) into (12) yields s sX r d(d + 1) log 1+n βr,i δr ∥xt,i ∥2V −1 ≤ . (15) √ nr t: i =i nr r,i t

With δr = δ/(2KR) and nr = ⌊T /(Kr R)⌋ where Kr = ⌈K/2r−1 ⌉, we have log((1 + nr )/δr ) = O(log T ), so there exists an absolute constant c1 > 0 such that s d2 log T ωr,i ≤ c1 . (16) nr √ arises from βr,i via the elliptical potential lemma [11], reflecting the d) Independence of the two factors: The first d √ estimation cost of ridge regression in Rd . The second d arises from the trace identity (14), 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. A PPENDIX G A DDITIONAL E XPERIMENTAL D ETAILS Hyperparameters. All results are averaged over 5000 independent trials. With random seeds generated as seed + 100000 × T + run_idx, where seed = 20260323. Besides, we set λ = 1.35 for MESHA. A. 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 θ∗ = (1, 0, 0), so the true expected reward of arm i is determined merely by its first feature coordinate. The true means are µ = (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 rt,i = µi + ηt where ηt ∼ N (0, 0.1552 ). The true feature vectors xi ∈ R3 are in Table II. The non-zero coordinates in dimensions 2 and 3 play no role in determining rewards under θ∗ = (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 θi∗ satisfying ⟨xt,i , θi∗ ⟩ = µ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 IV; 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 II. TABLE II T RUE FEATURES , REPORTED FEATURES IN THE VARY-T INSTANCE (K = 8, d = 3, θ∗ = (1, 0, 0)). Arm i 0 1 2 3 4 5 6 7

µi 0.520 0.490 0.400 0.330 0.270 0.220 0.180 0.150

xi (0.520, 0.000, 0.000) (0.490, 0.110, −0.080) (0.400, −0.120, 0.090) (0.330, 0.065, 0.050) (0.270, −0.050, −0.060) (0.220, 0.050, −0.050) (0.180, −0.060, 0.030) (0.150, 0.050, −0.040)

xt,i (0.000, 1.850, 0.000) (0.000, 0.667, 0.667) (0.000, 0.000, 1.949) (0.000, −0.586, 0.586) (0.000, −0.771, 0.000) (0.000, −0.505, −0.505) (0.000, 0.000, −0.657) (0.000, 0.424, −0.424)

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 E. • 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 III. • •

TABLE III BAI FAILURE PROBABILITIES FOR VARYING BUDGET T (K = 8, d = 3). T

MESHA

OptGTM

OD-LinBAI

OD-Lin-GTC

OD-LinBAI*

60 100 140 200 300 400 500 600 700 800

0.1210 0.1130 0.1110 0.1022 0.0890 0.0792 0.0612 0.0542 0.0432 0.0366

0.318 0.300 0.240 0.216 0.168 0.140 0.088 0.094 0.062 0.050

0.362 0.266 0.266 0.169 0.120 0.111 0.068 0.080 0.036 0.038

0.174 0.162 0.158 0.114 0.140 0.098 0.086 0.068 0.054 0.030

0.816 0.814 0.858 0.886 0.950 0.956 0.984 0.986 0.988 1.000

0.052 0.036 0.048 0.058 0.042 0.030 0.024 0.024 0.012 0.018

B. Experiment 2: Varying Feature Dimension d Instance Construction. We fix K = 64 arms and budget T = 1500, and vary d ∈ {3, 6, 9, 18, 24}. For each d, the true parameter θ∗ ∈ Rd is a fixed dense unit vector whose coordinates are listed in Table IV. The true feature of arm i is constructed as: x∗i = µi θ∗ + ρ(d)zi , where zi ⊥ θ∗ is a random unit vector orthogonal to θ∗ and ρ(d) controls the magnitude of the nuisance direction. The optimal arm is arm 0 with true mean µ0 = 0.62 across all values of d. The second-best arm has true mean µ1 , and the suboptimality gap ∆1 = µ0 − µ1 is denoted as “gap” in Table IV; the remaining 62 arms have means strictly decreasing from µ1 to 0.12. The reward noise follows ηt ∼ N (0, ξ 2 ), where ξ varies with d to maintain a consistent signal-to-noise ratio. All instance parameters are summarized in Table IV and V. TABLE IV I NSTANCE PARAMETERS FOR THE VARYING -d EXPERIMENT (K = 64, T = 1500). “ GAP ” DENOTES THE SUBOPTIMALITY GAP ∆1 = µ0 − µ1 BETWEEN THE OPTIMAL ARM AND THE SECOND - BEST ARM . d

gap

ρ(d)

3 6 9 18 24

0.0150 0.0135 0.0122 0.0096 0.0093

0.1400 0.1461 0.1522 0.1705 0.1826

0.350 0.411 0.472 0.567 0.567

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 rewardrelevant 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 θi∗ satisfying ⟨xt,i , θi∗ ⟩ = µi for all t, ensuring that its estimated rewards under θ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 VI.

TABLE V VALUES OF θ∗ FOR EACH COORDINATE k ACROSS DIFFERENT FEATURE DIMENSIONS d IN THE VARYING -d EXPERIMENT. “—” INDICATES THE COORDINATE DOES NOT EXIST FOR THE CORRESPONDING d. k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

d=3 0.7385 0.5222 0.4264 — — — — — — — — — — — — — — — — — — — — —

d=6 0.6389 0.4518 0.3689 0.3194 0.2857 0.2608 — — — — — — — — — — — — — — — — — —

d=9 0.5945 0.4204 0.3433 0.2973 0.2659 0.2427 0.2247 0.2102 0.1982 — — — — — — — — — — — — — — —

d = 18 0.5349 0.3782 0.3088 0.2674 0.2392 0.2184 0.2022 0.1891 0.1783 0.1691 0.1613 0.1544 0.1484 0.1430 0.1381 0.1337 0.1297 0.1261 — — — — — —

d = 24 0.5146 0.3639 0.2971 0.2573 0.2301 0.2101 0.1945 0.1819 0.1715 0.1627 0.1552 0.1486 0.1427 0.1375 0.1329 0.1287 0.1248 0.1213 0.1181 0.1151 0.1123 0.1097 0.1073 0.1050

TABLE VI BAI FAILURE PROBABILITIES IN THE VARYING -d EXPERIMENT (K = 64, T = 1500) d

MESHA

OptGTM

OD-LinBAI*

3 6 9 18 24

0.201 0.236 0.268 0.337 0.358

0.320 0.358 0.402 0.442 0.457

0.060 0.125 0.213 0.314 0.369

C. Experiment 3: Varying Arm Count K Instance Construction. We fix feature dimension d = 6, budget T = 1500, and sweep K ∈ {16, 24, 32, 64}. The true parameter is the same dense unit vector θ∗ = (0.6389, 0.4518, 0.3689, 0.3194, 0.2857, 0.2608) ∈ R6 across all values of K. The true feature of arm i is constructed as: x∗i = µi θ∗ + ρ(K)zi ,

zi ⊥ θ∗ ,

∥zi ∥2 = 1,

where zi is a random unit vector orthogonal to θ∗ , and ρ(K) controls the magnitude of the nuisance direction. The optimal arm is arm 0 with true mean µ0 = 0.62 fixed across all K. The second-best arm has true mean µ1 = µ0 − gap(K), where the suboptimality gap ∆1 = gap(K) shrinks as K grows according to: 1.48 ! 16 gap(K) = max 0.0022, 0.010 × . max(K, 16) The remaining K − 2 arms have means linearly spaced between µ1 and µtail = 0.20. The noise standard deviation ξ and nuisance magnitude ρ(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 VII. 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 ⟨xt,i , θi∗ ⟩ = µi to pass the GTC. The reported geometry is scaled by a K-dependent multiplier

TABLE VII I NSTANCE PARAMETERS FOR THE VARYING -K EXPERIMENT (d = 6, T = 1500). “ GAP ” DENOTES THE SUBOPTIMALITY GAP ∆1 = µ0 − µ1 BETWEEN THE OPTIMAL ARM AND THE SECOND - BEST ARM . K

gap

ρ(K)

µ1

16 24 32 64

0.0100 0.0055 0.0036 0.0022

0.1400 0.1512 0.1675 0.2128

0.350 0.376 0.412 0.497

0.6100 0.6145 0.6164 0.6178

(K=16→1.00, 24→1.05, 32→1.12, 64→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 VIII. TABLE VIII BAI FAILURE PROBABILITIES FOR VARYING K (d = 6, T = 1500, ± INDICATES WALD 95% CI HALF - WIDTH ). K

MESHA

Sequential Halving

16 24 32 64

0.222 0.342 0.390 0.426

0.247 0.397 0.415 0.482

0.2144 0.3524 0.4198 0.4716

R EFERENCES [1] J. Yang and V. Tan, “Minimax optimal fixed-budget best arm identification in linear bandits,” Advances in Neural Information Processing Systems, vol. 35, pp. 12 253–12 266, 2022. [2] M. Soare, A. Lazaric, and R. Munos, “Best-arm identification in linear bandits,” Advances in neural information processing systems, vol. 27, 2014. [3] S. Zheng, A. Trott, S. Srinivasa, D. C. Parkes, and R. Socher, “The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning,” Science advances, vol. 8, no. 18, p. eabk2607, 2022. [4] T. Kleine Buening, A. Saha, C. Dimitrakakis, and H. Xu, “Strategic linear contextual bandits,” Advances in Neural Information Processing Systems, vol. 37, pp. 116 638–116 675, 2024. [5] M. Braverman, J. Mao, J. Schneider, and S. M. Weinberg, “Multi-armed bandit problems with strategic arms,” in Conference on Learning Theory. PMLR, 2019, pp. 383–416. [6] A. Verma, I. Saha, M. Yokoo, and B. K. H. Low, “Cobra: Contextual bandit algorithm for ensuring truthful strategic agents,” arXiv preprint arXiv:2505.23720, 2025. [7] T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020. [8] Z. Zhong, W. C. Cheung, and V. Y. Tan, “Achieving the pareto frontier of regret minimization and best arm identification in multi-armed bandits,” arXiv preprint arXiv:2110.08627, 2021. [9] R. Degenne, T. Nedelec, C. Calauzènes, and V. Perchet, “Bridging the gap between regret minimization and best arm identification, with application to a/b tests,” in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 1988–1996. [10] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” Machine learning, vol. 47, no. 2, pp. 235–256, 2002. [11] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” Advances in neural information processing systems, vol. 24, 2011. [12] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in applied mathematics, vol. 6, no. 1, pp. 4–22, 1985. [13] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” Biometrika, vol. 25, no. 3/4, pp. 285–294, 1933. [14] S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” in Conference on learning theory. JMLR Workshop and Conference Proceedings, 2012, pp. 39–1. [15] O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,” Advances in neural information processing systems, vol. 24, 2011. [16] P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” Journal of machine learning research, vol. 3, no. Nov, pp. 397–422, 2002. [17] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” in 21st Annual Conference on Learning Theory, no. 101, 2008, pp. 355–366. [18] E. Even-Dar, S. Mannor, and Y. Mansour, “Pac bounds for multi-armed bandit and markov decision processes,” in International Conference on Computational Learning Theory. Springer, 2002, pp. 255–270. [19] E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan, “Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.” Journal of machine learning research, vol. 7, no. 6, 2006. [20] E. Kaufmann, O. Cappé, and A. Garivier, “On the complexity of best-arm identification in multi-armed bandit models,” The Journal of Machine Learning Research, vol. 17, no. 1, pp. 1–42, 2016. [21] J.-Y. Audibert and S. Bubeck, “Best arm identification in multi-armed bandits,” in COLT-23th Conference on learning theory-2010, 2010, pp. 13–p. [22] Z. Karnin, T. Koren, and O. Somekh, “Almost optimal exploration in multi-armed bandits,” in International conference on machine learning. PMLR, 2013, pp. 1238–1246. [23] Y. Zhao, C. Stephens, C. Szepesvári, and K.-S. Jun, “Revisiting simple regret: Fast rates for returning a good arm,” in International Conference on Machine Learning. PMLR, 2023, pp. 42 110–42 158.

[24] C. Shen, “Universal best arm identification,” IEEE Transactions on Signal Processing, vol. 67, no. 17, pp. 4464–4478, 2019. [25] V. Gabillon, M. Ghavamzadeh, and A. Lazaric, “Best arm identification: A unified approach to fixed budget and fixed confidence,” Advances in neural information processing systems, vol. 25, 2012. [26] L. Xu, J. Honda, and M. Sugiyama, “A fully adaptive algorithm for pure exploration in linear bandits,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2018, pp. 843–851. [27] T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff, “Sequential experimental design for transductive linear bandits,” Advances in neural information processing systems, vol. 32, 2019. [28] Z. Feng, D. Parkes, and H. Xu, “The intrinsic robustness of stochastic bandits to strategic manipulation,” in International Conference on Machine Learning. PMLR, 2020, pp. 3092–3101. [29] S. A. Esmaeili, S. Shin, and A. Slivkins, “Robust performance incentivizing algorithms for multi-armed bandits with strategic agents,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, no. 13, 2025, pp. 13 814–13 822. [30] S. Esmaeili, M. Hajiaghayi, and S. Shin, “Replication-proof bandit mechanism design,” arXiv e-prints, pp. arXiv–2312, 2023. [31] S. Shin, S. Lee, and J. Ok, “Multi-armed bandit algorithm against strategic replication,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 403–431. [32] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American statistical association, vol. 58, no. 301, pp. 13–30, 1963.

Record · ID 373413 · SHA-256 f1a3e93f2b9f4d4c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.