Multi-Armed Bandits for Adaptive Constraint Propagation

Amine Balafrej, Christian Bessiere, Anastasia PaparrizouIJCAI 2015

Introduction: The Propagation Trade-off

In Constraint Programming (CP), solvers rely on "propagation" to prune the search space by removing values from variable domains that cannot participate in a valid solution. This process involves a fundamental trade-off: weak propagation methods, such as Arc Consistency (AC), are computationally inexpensive but offer limited pruning. Conversely, stronger methods like Partition One-Arc Consistency (POAC) prune the search space aggressively but incur significant computational overhead.

Historically, selecting the optimal propagation level required manual expert tuning or static heuristics. However, the ideal level of consistency often shifts depending on the specific problem instance and even the current depth within the search tree. This paper introduces an automated, "plug-and-play" framework that uses Multi-Armed Bandits (MAB) to dynamically select the most efficient propagation level during search without requiring offline training.

The MAB Framework for Adaptive Selection

The authors frame the selection of a propagation level as a Multi-Armed Bandit problem, where different local consistency algorithms (e.g., AC, maxRPC, POAC) act as the "arms."

Depth-Specific Selectors

A key insight of this work is that context matters. The effectiveness of a propagator at the root of the search tree rarely matches its effectiveness near the leaves. To address this, the framework places a separate MAB selector at each depth of the search tree. This allows the solver to evolve a custom "propagation schedule" tailored to the specific problem's structure.

Reward and Policy

To balance exploration and exploitation, the system employs the UCB1 algorithm. The reward function is the "secret sauce" of the approach: it accounts for both the immediate CPU time required for propagation and the time spent exploring the resulting subtree. This ensures that the MAB recognizes the long-term benefits of heavy pruning, even if the initial propagation step is slow.

Evolution of mean rewards and selection ratios for different consistency levels over time steps.

As shown in the learning curves above, the system dynamically adjusts the selection ratio of different arms based on their observed mean rewards, eventually converging on the most effective strategies for the given context.

Experimental Evaluation

The researchers evaluated the MAB-based solver on 313 instances from the CRIL repository, covering a diverse range of structured, random, and graph-based problems.

Superior Coverage and Speed

The adaptive method utilizing all three consistencies (AC-maxRPC-POAC) demonstrated superior performance, solving 309 out of 313 instances. This outperformed the best single-consistency method, which solved only 296 instances.

Cumulative number of solved instances over time for various propagation strategies.

As illustrated in Figure 1, the MAB-based approaches (represented by the upper dotted and dashed curves) consistently solve more instances faster than static methods. On difficult instances, the speedups were substantial; for example, the total time for the AC-maxRPC-POAC method was approximately 11,104 seconds, compared to 25,599 seconds for standard Arc Consistency.

Conclusion and Future Work

The MAB framework provides a robust safety net for CP solvers. If a strong consistency level performs poorly on a specific problem, the MAB quickly learns to deprioritize it, preventing the solver from becoming bogged down by high overhead.

While UCB1 is effective, future work could explore more granular selection (e.g., per-constraint selectors) or advanced reinforcement learning techniques like Q-learning to better model the dependencies between choices made at different search depths. Currently, the "learning lag" inherent in exploration means that for extremely simple problems solved in seconds, the overhead of the MAB might slightly exceed the benefits, though it remains a powerful tool for complex, real-world constraints.

Summary updated

BibTeX
@inproceedings{balafrej2015multi,
  author = {Amine Balafrej and Christian Bessiere and Anastasia Paparrizou},
  title = {{Multi-Armed Bandits for Adaptive Constraint Propagation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure