Nearly Optimal Best Arm Identification for Semiparametric Bandits

• URL: http://arxiv.org/abs/2604.03969v1
• Date: Sun, 05 Apr 2026 05:13:02 GMT
• Title: Nearly Optimal Best Arm Identification for Semiparametric Bandits
• Abstract summary: We study fixed-confidence Best Arm Identification (BAI) in semiparametric bandits, where rewards are linear in arm features plus an unknown additive baseline shift.<n>For the transductive setting, we establish an attainable instance-dependent lower bound characterized by the corresponding linear-bandit complexity on shifted features.<n>Our analysis yields a nearly optimal high-probability sample-complexity upper bound, up to log factors and an additive $d2$ term.
• Score: 2.538209532048867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $d^2$ term, and experiments on synthetic instances and the Jester dataset show clear gains over prior baselines.

Related papers

• Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements [21.28320211178358]
  The least trimmed squares (LTS) regression problem is a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes.<n>Existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and exponential worst-case complexity in the number of observations.<n>We propose a new MIO formulation that embeds hyperplane arrangement logic into a perspective reformulation, explicitly enforcing structural properties of optimal solutions.
  arXiv  Detail & Related papers  (2026-04-13T15:00:53Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  We study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ per instance for prediction.<n>We introduce a new extend-time algorithm, which significantly improves previous regret bounds.
  arXiv  Detail & Related papers  (2025-10-31T05:02:33Z)
• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  We study the fixed-confidence best arm identification problem within the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion.
  arXiv  Detail & Related papers  (2025-10-06T11:49:56Z)
• Identifying All ε-Best Arms in (Misspecified) Linear Bandits [9.638337713545065]
  LinFACT is an algorithm designed to optimize the identification of all epsilon-best arms in linear bandits.<n>We show that LinFACT achieves instance optimality by matching this lower bound up to a logarithmic factor.<n> Numerical experiments, including synthetic and real drug discovery data, demonstrate that LinFACT identifies more promising candidates with reduced sample complexity.
  arXiv  Detail & Related papers  (2025-09-29T22:26:52Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Sample Complexity of Linear Quadratic Regulator Without Initial Stability [7.245261469258501]
  Inspired by REINFORCE, we introduce a novel receding-horizon algorithm for the Linear Quadratic Regulator (LQR) problem with unknown dynamics.<n>Unlike prior methods, our algorithm avoids reliance on two-point gradient estimates while maintaining the same order of sample complexity.
  arXiv  Detail & Related papers  (2025-02-20T02:44:25Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  We give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/sigma) regret for realizable K-wise linear classification. We develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers.
  arXiv  Detail & Related papers  (2022-05-25T21:31:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.