mlsanityData to 14 Oct 2026

Nearly Optimal Best Arm Identification for Semiparametric Bandits

arXiv 2604.03969 ↗First posted 5 Apr 2026stat.ML cs.LG stat.MEcited by 0

Not on the map. Why?

Abstract (arXiv)

We study fixed-confidence Best Arm Identification (BAI) in semiparametric bandits, where rewards are linear in arm features plus an unknown additive baseline shift. Unlike linear-bandit BAI, this setting requires orthogonalized regression, and its instance-optimal sample complexity has remained open. For the transductive setting, we establish an attainable instance-dependent lower bound characterized by the corresponding linear-bandit complexity on shifted features. We then propose a computationally efficient phase-elimination algorithm based on a new XY-design for orthogonalized regression. Our analysis yields a nearly optimal high-probability sample-complexity upper bound, up to log factors and an additive d2 term, and experiments on synthetic instances and the Jester dataset show clear gains over prior baselines.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 41 references that are in the map. First posted on arXiv 5 Apr 2026.

Builds on

16 of 41 references.

References · 16

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  3. 2014Best-Arm Identification in Linear Banditscited by 100
  4. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
  5. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  6. 2020Gamification of Pure Exploration for Linear Banditscited by 63
  7. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  8. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  9. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  10. 2017Action Centered Contextual Banditscited by 23
  11. 2018Semiparametric Contextual Banditscited by 19
  12. 2019Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Modelcited by 10
4 more
  1. 2020Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptionscited by 9
  2. 2025Joint Value Estimation and Bidding in Repeated First-Price Auctionscited by 6
  3. 2022Semi-Parametric Contextual Bandits with Graph-Laplacian Regularizationcited by 4
  4. 2025Experimental Design for Semiparametric Banditscited by 1

Built on by

Not cited yet.