# Nearly Optimal Best Arm Identification for Semiparametric Bandits

arXiv: https://arxiv.org/abs/2604.03969 · HTML: https://mlsanity.com/paper/2604.03969/

## 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 (most cited first, 16 of 16)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Action Centered Contextual Bandits](https://mlsanity.com/paper/1711.03596/) (2017)
- [Semiparametric Contextual Bandits](https://mlsanity.com/paper/1803.04204/) (2018)
- [Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Model](https://mlsanity.com/paper/1901.11221/) (2019)
- [Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions](https://mlsanity.com/paper/2010.07904/) (2020)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization](https://mlsanity.com/paper/2205.08295/) (2022)
- [Experimental Design for Semiparametric Bandits](https://mlsanity.com/paper/2506.13390/) (2025)

## 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.