MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Xin Li; Zixin Zhong

cs.LGJul 16, 2026

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

Authors: Xin Li, Zixin Zhong

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ï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 {\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.

Explore similar work

Jan 30, 2026cs.LG

Improved Algorithms for Nash Welfare in Linear Bandits

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension

d

, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of

p

-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear

p

-means regret for the entire range of

p

. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.

Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury

Dynamic Regret Bounds Fairness-Aware Learning

Ask PDF

May 7, 2026cs.AI

Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback

We study fixed-confidence best arm identification in generalized linear bandits under a hybrid feedback model: at each round, the learner may query either (i) absolute reward feedback from a single arm or (ii) relative (dueling) feedback from an arm pair, both governed by generalized linear models. We introduce a likelihood-ratio--based confidence sequence that unifies heterogeneous generalized linear observations and yields an explicit ellipsoidal confidence set under a self-concordance assumption. Building on this confidence set, we propose a hybrid Track-and-Stop algorithm that adaptively allocates queries by tracking a minimax-optimal design over a joint action space of arms and pairs. We establish

δ

-correctness and provide high-probability upper bounds on the stopping time. We further extend the framework to a cost-aware setting that accounts for heterogeneous acquisition costs across feedback modalities. Empirical experiments demonstrate that the proposed algorithms significantly improve sample efficiency over baseline methods.

Qirun Zeng, Xuchuang Wang, Jiayi Shen +3

Generalized Linear Bandit Natural Language Feedback

Ask PDF

Jul 13, 2026cs.LG

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Generalized Linear Bandit Budgets Fundamental Limits Exponential Family

Ask PDF