Abstract
Automated algorithm design traditionally treats programs as "black boxes," optimizing parameters based solely on final performance metrics. This paper proposes a fundamental shift toward a "white box" approach by reformulating the algorithm design problem as a Markov Decision Process (MDP). By exploiting internal execution data and tracking unique execution paths, this framework enables orders-of-magnitude faster optimization and the creation of adaptive algorithms that respond to runtime context.
Introduction
The current state-of-the-art in automated algorithm design—often called Programming by Optimization (PbO)—relies on black-box configurators like ParamILS or SMAC. These tools provide a set of parameters, run the algorithm, and receive a single cost value (e.g., execution time) upon completion. However, this approach suffers from two major flaws: information waste and static designs. Black-box tools ignore when and how a decision affects performance, and they typically return a single, static configuration that cannot adapt to the specific problem state encountered during execution.
Methodology: Algorithm Design as an MDP
The core contribution of this work is the formalization of the Algorithm Design Problem (ADP) as a Markov Decision Process (MDP). In this model:
- States ($S$): Represent the internal state of the algorithm.
- Actions ($A$): Represent the design choices or parameter settings available at specific "choice points."
- Transitions ($T$): Represent the execution of logic between choice points.
- Rewards ($R$): Provide incremental feedback during execution.
By linking rewards to specific transitions, the optimizer can perform precise credit assignment, understanding exactly which decision led to a performance gain. To implement this, the authors introduced Path-based Uniform Random Sampling (PURS), a sampling agent that explores unique execution paths rather than just unique parameter configurations. This allows the system to generalize data across thousands of configurations that share the same initial execution steps.
Experimental Evaluation
The authors evaluated the white-box approach using two micro-benchmarks designed to isolate specific advantages:
Benchmark 1: Search Speedup
This benchmark features a large configuration space ($2^{20}$ possible settings) but only 21 possible execution paths. It tests how quickly an optimizer can find the optimal path when many configurations are functionally redundant.
As shown in the results, the white-box optimizer (WB-PURS) found the optimal configuration in approximately 100 evaluations. In contrast, standard black-box random search required nearly 1,000,000 evaluations, and the state-of-the-art ParamILS required roughly 10,000.
Benchmark 2: Design Adaptivity
This benchmark tests the ability to learn a dynamic policy where the optimal decision depends on the order in which choices are encountered—a context invisible to static configurators.
The white-box approach successfully learned an adaptive policy reaching a reward of 5.0. Because black-box approaches are limited to static configurations, they could never exceed a reward of 1.0, regardless of the number of evaluations performed.
Conclusion and Future Work
While the white-box approach offers significant gains in efficiency and adaptivity, challenges remain regarding state-space explosion. Modeling every variable as an MDP state is impractical; future work must focus on automated feature selection to identify relevant context. Additionally, while current implementation requires manual code instrumentation (using getDecision and feedback hooks), future integration into compilers could automate this process, making white-box optimization a standard part of the software development lifecycle.
Summary updated