Tight Sample Complexity Bounds for Best-Arm Identification Under Bounded Systematic Bias

View PDF HTML (experimental) Abstract:As search depth increases in autonomous reasoning and embodied planning, the candidate action space expands exponentially, heavily taxing computational budgets. While heuristic pruning is a common countermeasure, it operates without formal safety guarantees when surrogate models (like LLMs) exhibit systematic evaluation biases. This paper frames the node expansion process as a localized Best-Arm Identification (BAI) problem over dynamic frontiers, subject to a bounded systematic bias $L$. By inverting the Lambert W function, we establish an additive sample complexity of $\mathcal{O}((\Delta-4L)^{-2})$, which indicates that safe node elimination is only feasible when the empirical reward gap exceeds $4L$. We complement this with an information-theoretic lower bound of $\Omega((\Delta-2L)^{-2})$ to confirm the structural limits of biased search. Subsequent evaluations on both synthetic trees and complex reasoning tasks demonstrate that adhering to this local safety boundary successfully preserves optimal trajectories while maximizing sample allocation efficiency. Comments: 10 pages, 5 figures Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) MSC classes: 68T05, 90C40 Cite as: arXiv:2604.14345 [cs.LG] (or arXiv:2604.14345v1 [cs.LG] for this version) https://doi.org/10.48550/arXiv.2604.14345 arXiv-issued DOI via DataCite (pending registration) Submission history From: Tianhao Qian [view email] [v1] Wed, 15 Apr 2026 18:53:25 UTC (5,166 KB)