Provably Efficient Algorithm Configuration with Local Structure and Reuse of Observations

We study the problem of algorithm configuration (AC) under realistic performance landscapes that exhibit local structure, but lack strong global regularity. While recent theoretically grounded AC methods provide PAC-style guarantees, they often rely on global exploration or restrictive assumptions on the reward distributions, limiting their practical efficiency. In this work, we introduce a new AC framework based on a relaxed structural assumption that captures local smoothness of the performance landscape. Under this assumption, we design an algorithm that identifies an $ϵ$-optimal configuration with probability of at least $(1-\delta )$ using predominantly local sampling. Our method efficiently reuses problem instances, narrowing the performance gap to heuristic AC methods. A key feature of our approach is the principled and consistent reuse of previously observed evaluations. In contrast to prior methods, this induces an implicit, data-dependent capping mechanism that reduces evaluation cost while preserving statistical guarantees. We provide theoretical bounds on the sample complexity of our algorithm and show that it improves over existing approaches under our structural assumptions. Empirical results further support our theory, demonstrating competitive or superior performance on benchmark configuration tasks. The code and experimental data are available at https://anonymous.4open.science/r/LoRe-AC-Band-045E.