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

arXiv:2604.14345v1 Announce Type: new 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 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.

Related

• Differentially Private Best-Arm Identification
• Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning
• Atropos: Improving Cost-Benefit Trade-off of LLM-based Agents under Self-Consistency with Early Termination and Model Hotswap
• LoDAdaC: a unified local training-based decentralized framework with adaptive gradients and compressed communication
• FedQUIT: On-Device Federated Unlearning via a Quasi-Competent Virtual Teacher

Source: arXiv cs.LG | 2026-04-17