Tight Sample Complexity Bounds for Best-Arm Identification Under Bounded Systematic Bias
For autonomous reasoning and planning systems using heuristic pruning with biased surrogate models (e.g., LLMs), this work provides formal safety guarantees and optimal sample allocation bounds.
This paper establishes tight sample complexity bounds for best-arm identification under bounded systematic bias, showing that safe node elimination requires the empirical reward gap to exceed 4L, with an additive complexity of O((Δ-4L)^{-2}) and a matching lower bound of Ω((Δ-2L)^{-2}). Experiments on synthetic trees and reasoning tasks confirm that respecting this safety boundary preserves optimal trajectories while maximizing efficiency.
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}((Δ-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 $Ω((Δ-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.