MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Xin Li; Zixin Zhong

REVIEW 4 major objections 3 minor 32 references

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

T0 review · 4 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read MESHA claims that a uniformly sampling, epoch-wise Grim Trigger algorithm identifies a ζ-optimal arm in strategic linear bandits with failure probability exponentially decaying in the budget, and that G-optimal-design algorithms fail struct

desk verdict The central failure bound is not established: Lemma 5 is false as stated, and the proof of Theorem 6 leans on an undefined deviation; still, the starvation-attack observation is real and the strategic BAI setting is new. read the letter →

arxiv 2607.14706 v1 pith:E6DWM3GZ submitted 2026-07-16 cs.LG

Xin Li , Zixin Zhong This is my paper

classification cs.LG

keywords strategiclinearbanditsbestarmidentificationGrimtriggerconditionNashequilibriumG-optimaldesignsequentialhalvingfeaturemisreportingfixedbudget

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Best-arm identification usually assumes arms report their true feature vectors. This paper studies what happens when each arm can lie about its features to increase its chance of being picked, and asks whether a learner can still identify a near-best arm with high probability. The answer it proposes is MESHA: sample all remaining arms equally, and after each epoch run a Grim Trigger consistency check that eliminates any arm whose reported features predict substantially higher rewards than were actually observed. The paper proves that in any Nash equilibrium every surviving arm is forced to keep its average misreport small, yielding an exponential-in-T upper bound on failure probability. It also shows that state-of-the-art G-optimal-design algorithms are vulnerable to a starvation attack that no reward-level check can detect, which motivates the uniform-sampling design.

What carries the argument

The central mechanism is the epoch-wise Grim Trigger Condition (GTC), a statistical consistency check applied at the end of each sequential-halving epoch: an arm survives only if its lower confidence bound on cumulative rewards predicted from reported features does not exceed an upper confidence bound on rewards actually observed. MESHA couples this with a naive uniform sampling rule, so budget allocation never depends on reported geometry, and with per-arm ridge-regression estimators so each arm's behavior is checked individually. The GTC is load-bearing: Lemma 5 uses it to convert equilibrium rationality into a bound on average misreporting, which then yields the exponential failure bound;

What would settle it

Construct K=2, d=1, θ*=1, true features x1=1, x2=0, rewards with noise bounded in [−0.05,0.05] so arm 2 can never beat arm 1. Let arm 2 report x=1, which makes it fail the GTC; since its selection probability is zero under both failing and truthful reporting, no profitable deviation exists, so this profile is a Nash equilibrium in which Lemma 5's 'every equilibrium arm passes the GTC' fails. Checking this instance with T large, either by simulation or by exact calculation of utilities, settles whether the theorem's incentive argument holds.

Watch

Extended reading notes

Core claim

This paper claims that fixed-budget best-arm identification in linear bandits can be made robust to strategic feature misreporting. It proposes MESHA, which samples every active arm uniformly and, at the end of each epoch, applies a Grim Trigger Condition: an arm is eliminated if a lower confidence bound on rewards predicted from its reported features exceeds an upper confidence bound on rewards actually observed. The paper proves that under any Nash equilibrium every arm must pass this check to maximize its chance of being selected, and that MESHA is (ζ, δ_T)-PAC with δ_T = (⌈log2 K⌉²/T) exp(−Tζ²/(18 K d² log²(1+T/⌈log2 K⌉))), i.e., failure probability decays exponentially in budget T. It a

Load-bearing premise

The proof of Lemma 5 assumes that, under any Nash equilibrium, an arm that fails the Grim Trigger check can profitably deviate to a calibrated strategy that passes it and then has strictly positive probability of eventually being chosen; this requires unstated conditions on noise support and mean gaps, and the lower-bound half of Theorem 6 additionally relies on a deviation strategy whose GTC-passing property is asserted without proof.

Editorial extensions

If this is right

Under any Nash equilibrium, MESHA identifies a ζ-optimal arm with failure probability at most (⌈log2 K⌉²/T) exp(−Tζ²/(18 K d² log²(1+T/⌈log2 K⌉))), so the error decays exponentially with budget T.
Arms' equilibrium misreporting is actively constrained: any arm surviving the GTC has average per-round strategic deviation bounded by a term that shrinks as (√d log n)/√n as it is pulled more often.
Optimal-design-based linear BAI algorithms are structurally vulnerable: the starvation attack can force zero sampling of the optimal arm, and no reward-level consistency check can recover it.
The O(d² log T) overhead in the exponent is the price of strategic robustness; the paper exhibits a reporting strategy that attains this overhead and conjectures it is unavoidable for GTC-based feature-independent sampling.
MESHA's advantage over feature-agnostic baselines widens as the number of arms grows, since uniform sampling plus the GTC exploits features without trusting reported geometry.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the Nash-equilibrium guarantee extends to approximately rational arms, MESHA could serve as a pre-processing layer: run uniform sampling with an epoch-wise GTC, then hand the surviving arms to a more sample-efficient feature-aware procedure.
A testable strengthening is to replace the static GTC threshold with one adaptively calibrated to each arm's reported norm; the paper's analysis suggests part of the d² factor comes from a trace bound, so a non-ridge estimator might shrink the exponent.
The starvation attack points to a broader principle: any sampling rule that optimizes over reported geometry is gameable at the geometry level, so robustness requires either budget allocation independent of reports or a mechanism that directly prices geometric misreporting.
Extending the setting to arms that also manipulate their realized rewards would require a second consistency check between reported and realized rewards; the current GTC alone would likely be insufficient.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth a look from anyone working on strategic bandits, but the main theorem should not be trusted in its current form. The setting is genuinely new: fixed-budget best-arm identification when arms can misreport feature vectors. MESHA's combination of uniform sampling and an epoch-wise GTC is a reasonable starting point, and the structural observation in Theorem 9—that G-optimal design can starve the optimal arm when its reported feature lies in the cone spanned by the others—is a nice, credible insight. That part held up when I checked it; it is essentially a convex-hull property of G-optimal design, but the strategic interpretation is useful and appears to be original.

The serious soft spot is Lemma 5, which is the hinge of the whole paper. The proof claims that after passing the GTC a suboptimal arm has strictly positive probability of ultimately being output because the noise has non-degenerate support. That is not true. Take two arms with true means 0.9 and 0.1 and noise bounded in [-0.05, 0.05]. No matter what the weak arm reports, its empirical mean almost surely stays below the strong arm's, so its output probability is exactly zero. There is no profitable deviation from failing the GTC, and a Nash equilibrium can include an arm that fails it. The stress-test note constructs exactly this case, and it lands. The proof also invokes an undefined σ'_i in the lower-bound half of Theorem 6, with its GTC-passing property asserted via Remark 15, whose proof only covers truthful reporting. These are not cosmetic gaps; they break the chain from NE behavior to the exponential failure bound.

I also noticed a numerical inconsistency: Section V-A says MESHA's failure probability decays from 0.188 to 0.056, but Table III reports 0.1210 to 0.0366 for the same experiment. That is a factual mismatch that should have been caught before submission.

On the positive side, the paper is clearly written, the literature review is honest, and the idea of proving that the GTC actively constrains equilibrium misreporting is worthwhile. The flaw is localized enough that a fix might be possible—say, by adding a condition on the noise support or by redefining the utility to allow for ζ-optimal identification in a way that gives weak arms a real shot. As it stands, the paper does not establish its main claim.

Who should read it: researchers working on strategic bandits or on the robustness of optimal-design sampling. It deserves a serious referee, but the referee should be told to focus on Lemma 5 and the lower-bound step in Theorem 6. My recommendation is to engage with it, but not to accept it without substantial revision.

Referee Report

4 major / 3 minor

Summary. This paper introduces MESHA, a fixed-budget best-arm-identification algorithm for linear bandits in which arms may strategically misreport their feature vectors. MESHA combines uniform sampling with an epoch-wise Grim Trigger Condition (GTC) that eliminates arms whose reported features are inconsistent with observed rewards. The main theoretical claim is Lemma 5: under any Nash equilibrium, every active arm must pass the GTC; from this, Theorem 6 derives an exponential-in-T upper bound on the probability of outputting an arm with suboptimality gap at least ζ. The paper also argues that G-optimal-design linear BAI algorithms are vulnerable to strategic manipulation even when augmented with a GTC, via a starvation attack, and reports simulations comparing MESHA with several baselines.

Significance. The problem is well motivated and the paper identifies a real vulnerability: G-optimal-design sampling based on reported features can be manipulated, and the starvation attack is a useful conceptual contribution. The experimental study is broad and includes the important oracle baseline OD-LinBAI*. However, the central equilibrium analysis is not sound: Lemma 5 fails under the paper's own noise model, and the proof of Theorem 6 contains an undefined deviation and a misapplication of Remark 15. The exponential failure-probability guarantee is therefore not established by the submitted proofs, and the contribution as a whole cannot be accepted.

major comments (4)

[Appendix B, Lemma 5] The proof asserts that a calibrated deviation that passes the GTC has strictly positive utility because 'the reward noise has non-degenerate support.' Non-degenerate support is insufficient. Under the paper's own Example 8 noise model η_t~Uniform[-0.05,0.05] with μ1=0.9 and μ2=0.1, the difference of equal-size sample means is supported in [0.7,0.9], so arm 2 has zero probability of ever being output, irrespective of its reporting strategy. Hence failing the GTC costs arm 2 nothing and the contradiction argument for Lemma 5 collapses. Additionally, the calibrated deviation's GTC-passing property is asserted rather than proved: no argument shows that the reported features and the per-arm ridge estimator satisfy RLCB ≤ AUCB.
[Appendix C, 'Bounding μhat'] The lower bound μhat_{r,i} ≥ μ_i − ω_{r,i} is obtained by postulating an undefined σ'_i ('let σ'_i denote the strategy σ'_i that is with empirical mean ...') and claiming Remark 15 implies it passes the GTC. Remark 15 concerns truthful reporting by all arms; its proof only establishes E_est under truthful reporting and does not apply to a unilateral deviation. Without a construction of σ'_i that passes the GTC, the two-sided confidence interval on μhat is unsupported; the subsequent failure-event chain Δ_i ≤ 2ω^* depends on both sides of that interval.
[Appendix C, parameter bookkeeping before Theorem 6] The proof sets δ = R²/T·exp(−Tζ²/(18Kd²log²(...))) and later says 'Setting ζ = 2ω^*', although ζ is already fixed as the target accuracy. Since ω^* contains log(2KR/δ) and δ contains ζ, the argument has a fixed-point character that is never resolved. The theorem's stated condition ζ ≥ 12d√(K log²K log(1+T))/√T is not shown to imply ζ ≥ 2ω^*, nor is the displayed failure bound derived from the condition. The claimed inclusion of the failure event in (E_noise)^c therefore does not follow from the written proof.
[Section IV-B, 'structural' claim] The text states that the failure of G-optimal design is structural and that 'no statistical test evaluating only reported features can identify manipulations that distort the underlying feature geometry.' Theorem 9 proves only that a cone condition permits a G-optimal allocation with zero mass on one arm, and Example 10 is one attack instance. No formal impossibility result over statistical tests is given. This overclaim goes beyond the proven statements and should be either proved or qualified.

minor comments (3)

[Algorithm 1 vs Definition 4] Line 7 of Algorithm 1 uses √(2n log(4KR/δ)), while Definition 4 uses √(2n log(2/δ_r)) and Appendix C uses δ_r = δ/(KR) in Lemma 14 and δ_r = δ/(2KR) in its proof. The GTC threshold is thus not consistently defined across the paper.
[Lemma 13 proof] The proof states r_t,i − μ_i ∈ [−2,2] almost surely from ξ-sub-Gaussianity. Sub-Gaussian noise need not be bounded; concentration should be derived from the sub-Gaussian parameter directly.
[Typos and notation] Contributions say 'lower bound on MESHA's failure probability' where an upper bound is meant; Fig. 2 caption refers to 'GSE' although the baseline is SR; Algorithm 1's Lemma 3 proof references a nonexistent line 18; λ=1 in Algorithm 1 but λ=1.35 in Appendix G; several spelling errors ('Grin Trigger Condition', 'feature-ignosmic', 'MASHE').

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: MESHA's bound follows from explicit concentration and GTC design, not fitted inputs; Lemma 5 has a rigor gap but not a circular reduction.

full rationale

The main claim is not circular. Theorem 6's δ is an explicit confidence parameter set to the final bound; Lemma 13 proves P(E_noise) ≥ 1 − δ by Azuma/union bound, Lemma 14 algebraically converts the GTC condition into μ̂ ≤ μ + ω, and the failure event is contained in (E_noise)^c. No fitted parameter is relabeled as a prediction. The GTC is the mechanism under test, not an input assumption, and Lemma 5 attempts an equilibrium deviation proof rather than defining 'pass GTC' into existence. The only self-citation ([8], a literature-review pointer) is not used in any proof. The real weaknesses are non-circular rigor gaps: Lemma 5's 'non-degenerate support ⇒ positive probability of ultimately being output' is unstated and false under bounded noise with large gaps, and the lower-bound half of Theorem 6 invokes Remark 15 even though Remark 15 explicitly says E_est fails under strategic reporting and only proves GTC-passing under truthful reporting. These are omitted-condition/proof issues, not reductions to inputs, so circularity score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 1 invented entities

The central theorem rests on the Nash-equilibrium assumption and on an unstated positive-probability-of-winning condition in Lemma 5. The only hand-chosen numeric constant in the algorithm itself is λ; the experimental instances contain many tuned parameters but those do not enter the theorem.

free parameters (1)

λ (ridge regularization) = λ = 1 in Algorithm 1; λ = 1.35 in experiments
Chosen by hand; affects V_r,i, estimators, and confidence radii. It is not fitted to data but is a free algorithmic constant.

assumptions (5)

domain assumption Arms play a Nash equilibrium of the induced game.
Theorem 6 is conditional on σ ∈ NE(MESHA); existence of such an equilibrium is not proven.
domain assumption Full information: each arm knows θ*, its own true feature, the algorithm A, and observes all pulls and rewards.
Stated in Section II-A; needed for the calibrated-deviation argument in Lemma 5 and for coordinated starvation attacks.
ad hoc to paper Each active arm that passes the GTC has strictly positive probability of eventually being output as the best arm.
Appendix B asserts this in the proof of Lemma 5; it is not stated as an assumption and fails for bounded noise with large gaps where sample-mean supports do not overlap.
domain assumption Assumption 11: ⟨θ*_i, x_t,i⟩ − ⟨θ*, x_i⟩ ≤ ε.
Used for Theorem 12; θ*_i is never formally defined as part of the arm model, making the assumption ambiguous.
standard math Ridge-regression confidence ellipsoid theorem (Abbasi-Yadkori et al.).
Invoked via Theorem 16 in Appendix A to control estimation error in GTC definitions and Lemma 18.

invented entities (1)

Pseudo-parameter θ*_i per arm
purpose: Used in Assumption 11, Example 10, Theorem 12, and the experiments to make reported features reward-consistent with the GTC.
It is a mathematical auxiliary with no falsifiable handle outside the paper; the arms' actual reports could be represented by many such pseudo-parameters.

how reviews work

0 comments

Cite this review

Pith. "Pith review of MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits." pith.science (2026). https://pith.science/paper/E6DWM3GZ

@misc{pith2026260714706,
  author       = {Pith},
  title        = {Pith review of: MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E6DWM3GZ}},
  note         = {Machine review of arXiv:2607.14706}
}

abstract

We design and analyze \underline{M}echanism-\underline{E}nforced \underline{S}equential \underline{HA}lving (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\"ive 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 {\it 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.

Figures

Figures reproduced from arXiv: 2607.14706 by the authors.

**Figure 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… view at source ↗

**Figure 2.** Empirical BAI failure probability of all algorithms under the strategic instance except for that OD-LinBAI* represents OD-LinBAI itself when facing [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 2 linked inside Pith

[1]

Minimax optimal fixed-budget best arm identification in linear bandits,

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

2022
[2]

Best-arm identification in linear bandits,

M. Soare, A. Lazaric, and R. Munos, “Best-arm identification in linear bandits,”Advances in neural information processing systems, vol. 27, 2014

2014
[3]

The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning,

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

2022
[4]

Strategic linear contextual bandits,

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

2024
[5]

Multi-armed bandit problems with strategic arms,

M. Braverman, J. Mao, J. Schneider, and S. M. Weinberg, “Multi-armed bandit problems with strategic arms,” inConference on Learning Theory. PMLR, 2019, pp. 383–416

2019
[6]

Cobra: Contextual bandit algorithm for ensuring truthful strategic agents,

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

arXiv 2025
[7]

Lattimore and C

T. Lattimore and C. Szepesv ´ari,Bandit algorithms. Cambridge University Press, 2020

2020
[8]

Achieving the pareto frontier of regret minimization and best arm identification in multi-armed bandits,

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

arXiv 2021

Show all 32 references

[9]

Bridging the gap between regret minimization and best arm identification, with application to a/b tests,

R. Degenne, T. Nedelec, C. Calauz `enes, and V . Perchet, “Bridging the gap between regret minimization and best arm identification, with application to a/b tests,” inThe 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 1988–1996

2019
[10]

Finite-time analysis of the multiarmed bandit problem,

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

2002
[11]

Improved algorithms for linear stochastic bandits,

Y . Abbasi-Yadkori, D. P ´al, and C. Szepesv ´ari, “Improved algorithms for linear stochastic bandits,”Advances in neural information processing systems, vol. 24, 2011

2011
[12]

Asymptotically efficient adaptive allocation rules,

T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,”Advances in applied mathematics, vol. 6, no. 1, pp. 4–22, 1985

1985
[13]

On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,

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

1933
[14]

Analysis of thompson sampling for the multi-armed bandit problem,

S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” inConference on learning theory. JMLR Workshop and Conference Proceedings, 2012, pp. 39–1

2012
[15]

An empirical evaluation of thompson sampling,

O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,”Advances in neural information processing systems, vol. 24, 2011

2011
[16]

Using confidence bounds for exploitation-exploration trade-offs,

P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,”Journal of machine learning research, vol. 3, no. Nov, pp. 397–422, 2002

2002
[17]

Stochastic linear optimization under bandit feedback,

V . Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” in21st Annual Conference on Learning Theory, no. 101, 2008, pp. 355–366

2008
[18]

Pac bounds for multi-armed bandit and markov decision processes,

E. Even-Dar, S. Mannor, and Y . Mansour, “Pac bounds for multi-armed bandit and markov decision processes,” inInternational Conference on Computational Learning Theory. Springer, 2002, pp. 255–270

2002
[19]

Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems

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

2006
[20]

On the complexity of best-arm identification in multi-armed bandit models,

E. Kaufmann, O. Capp ´e, 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

2016
[21]

Best arm identification in multi-armed bandits,

J.-Y . Audibert and S. Bubeck, “Best arm identification in multi-armed bandits,” inCOLT-23th Conference on learning theory-2010, 2010, pp. 13–p

2010
[22]

Almost optimal exploration in multi-armed bandits,

Z. Karnin, T. Koren, and O. Somekh, “Almost optimal exploration in multi-armed bandits,” inInternational conference on machine learning. PMLR, 2013, pp. 1238–1246

2013
[23]

Revisiting simple regret: Fast rates for returning a good arm,

Y . Zhao, C. Stephens, C. Szepesv ´ari, and K.-S. Jun, “Revisiting simple regret: Fast rates for returning a good arm,” inInternational Conference on Machine Learning. PMLR, 2023, pp. 42 110–42 158. 24

2023
[24]

Universal best arm identification,

C. Shen, “Universal best arm identification,”IEEE Transactions on Signal Processing, vol. 67, no. 17, pp. 4464–4478, 2019

2019
[25]

Best arm identification: A unified approach to fixed budget and fixed confidence,

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

2012
[26]

A fully adaptive algorithm for pure exploration in linear bandits,

L. Xu, J. Honda, and M. Sugiyama, “A fully adaptive algorithm for pure exploration in linear bandits,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2018, pp. 843–851

2018
[27]

Sequential experimental design for transductive linear bandits,

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

2019
[28]

The intrinsic robustness of stochastic bandits to strategic manipulation,

Z. Feng, D. Parkes, and H. Xu, “The intrinsic robustness of stochastic bandits to strategic manipulation,” inInternational Conference on Machine Learning. PMLR, 2020, pp. 3092–3101

2020
[29]

Robust performance incentivizing algorithms for multi-armed bandits with strategic agents,

S. A. Esmaeili, S. Shin, and A. Slivkins, “Robust performance incentivizing algorithms for multi-armed bandits with strategic agents,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 39, no. 13, 2025, pp. 13 814–13 822

2025
[30]

Replication-proof bandit mechanism design,

S. Esmaeili, M. Hajiaghayi, and S. Shin, “Replication-proof bandit mechanism design,”arXiv e-prints, pp. arXiv–2312, 2023

2023
[31]

Multi-armed bandit algorithm against strategic replication,

S. Shin, S. Lee, and J. Ok, “Multi-armed bandit algorithm against strategic replication,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 403–431

2022
[32]

Probability inequalities for sums of bounded random variables,

W. Hoeffding, “Probability inequalities for sums of bounded random variables,”Journal of the American statistical association, vol. 58, no. 301, pp. 13–30, 1963

1963

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

Minimax optimal fixed-budget best arm identification in linear bandits,

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

2022

[2] [2]

Best-arm identification in linear bandits,

M. Soare, A. Lazaric, and R. Munos, “Best-arm identification in linear bandits,”Advances in neural information processing systems, vol. 27, 2014

2014

[3] [3]

The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning,

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

2022

[4] [4]

Strategic linear contextual bandits,

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

2024

[5] [5]

Multi-armed bandit problems with strategic arms,

M. Braverman, J. Mao, J. Schneider, and S. M. Weinberg, “Multi-armed bandit problems with strategic arms,” inConference on Learning Theory. PMLR, 2019, pp. 383–416

2019

[6] [6]

Cobra: Contextual bandit algorithm for ensuring truthful strategic agents,

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

arXiv 2025

[7] [7]

Lattimore and C

T. Lattimore and C. Szepesv ´ari,Bandit algorithms. Cambridge University Press, 2020

2020

[8] [8]

Achieving the pareto frontier of regret minimization and best arm identification in multi-armed bandits,

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

arXiv 2021