Multi-Armed Bandits for Adaptive Constraint Propagation

1 Introduction

Constraint propagation is an essential component for efficiently solving constraint satisfaction problems (CSPs). Due to its ability to reduce the search space, constraint propagation is considered as the reason for the success and spread of Constraint Programming (CP) in solving many large-scale, real-world problems. Since the early 70's, CP research has provided a wide range of effective, either general-purpose or specialized propagation techniques. Despite this big variety, CP solvers need a expert user to tune the solver so that it becomes more efficient. In addition, solvers are constraint oriented, in the sense that they associate a specialized propagation for each type of constraint. On the other hand, the drawback of this design, is that they overlook the general picture of the problem (i.e., structural dependencies, constraint intersections) as well as the internal operations that occur during search. For example, in many cases, propagation effects indicate a need for changing the ordering in variable selection (e.g., domain wipeouts in dom/wdeg heuristic [Boussemart et al., 2004]).

This work aims at developing a simple framework that can learn the right combination of propagation levels during solving (online). It is based on a light learning technique, called

∗This work was supported by the EU under the project "Inductive Constraint Programming", contract FP7 FET-Open 284715.

Christian Bessiere CNRS, U. Montpellier Montpellier, France bessiere@lirmm.fr

Anastasia Paparrizou

CNRS, U. Montpellier Montpellier, France paparrizou@lirmm.fr

multi-armed bandits (MAB), that was inspired by the slot machines in casinos and the problem that a gambler has to decide which machines to play, in which order and how many times to play each one. Each machine, after being used, returns a reward from a distribution specific to that machine. The goal is to maximize the sum of rewards obtained through a sequence of plays [Gittins, 1989].

We use a MAB model to select the right level of propagation (also called level of consistency) to enforce at each node during the exploration of the search tree. We specify a simple reward function and the upper confidence bound (UCB) to estimate the best arm, namely the best consistency to apply. An experimental evaluation on various benchmark classes shows that the proposed framework, though being simple and preliminary, results in a more efficient and stable solver. We provide a clear evidence that the proposed adaptive technique is able to construct the right combination of the available consistency algorithms of a solver. It can be much more efficient than any level of consistency alone. The MAB framework as proposed here does not require any training or information from preprocessing and can improve its decision vigorously during search.

2 RelatedWork

Although CP community has provided a wide range of efficient propagation techniques, standard solvers do not adjust the propagation level depending on the characteristics of the problem. They either preselect the propagator or use costs and other measures to order the various propagation techniques. In [Schulte and Stuckey, 2008], some state-of-theart methods are presented to order propagation techniques in well known solvers (e.g., Gecode, Choco).

There has been a significant amount of work on adaptive solving through the use of machine learning (ML) methods, either with a training phase or without. The goal of the learning process is to automatically select or adapt the search strategy, so that the performance of the system is improved. There are two main approaches that have been studied. In the first case, a specific strategy (e.g., a search algorithm or a specific solver) is selected automatically among an array of available strategies, either for a whole class of problems or for a specific instance. Such methods, called portfolios, perform the learning phase offline, on a training set of instances. Portfolios have been initially proposed for SAT

(e.g., SATzilla [Xu et al., 2008]) and then for CSPs (e.g., CPHydra [O'Mahony et al., 2008], Proteus [Hurley et al., 2014]). In the second case, a new strategy can be synthesized (e.g., a combination of search algorithm and heuristics) through the use of ML [Epstein and Petrovic, 2007; Xu et al., 2009]. The learning phase is again performed as a preprocessing. On the contrary, in [Loth et al., 2013], multi-armed bandits are exploited to select online (i.e., without training phase) which node of a Monte Carlo Tree Search (MCTS) to extend. In that paper, the Bandit Search for Constraint Programming (BaSCoP) algorithm adapts MCTS to the CSP search to explore the most promising regions according to a specified reward function.

There has been little research on learning strategies for constraint propagation. In [Epstein et al., 2005], ML is used to construct a static method for the pre-selection between Forward Checking and Arc Consistency. The work in [Kotthoff et al., 2010] evaluates ensemble classification for selecting an appropriate propagator for the alldifferent constraint. But this is again done in a static way prior to search.

Recent papers have shown an increasing interest for adapting the propagation level through the use of heuristic methods. The initial approach, appeared in [Stergiou, 2008], showed many advantages in favor of heuristics. They are both inexpensive to apply and dynamic, based on the actual effects of propagation during search (i.e., domain wipeouts (DWOs), value deletions). This approach was later improved by a more general model for n-ary constraints that does not require any parameter tuning [Paparrizou and Stergiou, 2012]. This direction of research has led to the parameterized local consistency approach for adjusting the level of consistency depending on a stability parameter over values [Balafrej et al., 2013; Woodward et al., 2014]. Parameterized local consistencies choose to enforce either arc consistency or a stronger local consistency on a value depending on whether the stability of the value is above or below a given threshold. Interestingly, they propose ways to dynamically adapt the parameter, and thus the level of local consistency, during search. In [Balafrej et al., 2014], the number of times variables are processed for singleton tests on their values is adapted during search. The learning process is based on measuring a stagnation in the amount of pruned values.

Thus, we have on the one hand the use of ML techniques that are heavy to be applied online and can be mainly used prior to search (static). Hence the actual effect during search is ignored. In addition, the vast majority of works in this direction were proposed for adapting the variable ordering heuristics, not for adapting the propagation level during search. On the other hand, we have heuristics methods to automatically adapt consistency during search, but heuristics are only defined for two levels of consistency (i.e., a weak and a strong one). This limits their applicability.

The technique we propose in this paper fills the gap in the literature by proposing a ML approach for selecting automatically and dynamically among any number of propagation levels, without the need for training.

3 Background

A constraint network is defined as a set of n variables X = {x1, ..., xn}, a set of domains D = {D(x1), ..., D(xn)}, and a set of e constraints C = {c1, ..., ce}. Each constraint ck is defined by a pair (var(ck), sol(ck)), where var(ck) is an ordered subset of X, and sol(ck) is a set of combinations of values (tuples) satisfying ck.

The technique presented in this paper is totally generic in the sense that it can be used with any set of local consistencies. In our experiments, we use arc consistency (AC), max restricted path consistency (maxRPC), and partition one arc consistency (POAC). We give the necessary background to understand them. As maxRPC is defined for binary constraints only, we simplify the notations by considering that all constraints are binary. A binary constraint between xi and xj will be denoted by cij, and Γ(xi) will denote the set of variables xj involved in a constraint with xi.

A value vj ∈ D(xj) is called an arc consistent (AC) support for vi ∈ D(xi) on cij iff (vi, vj) ∈ sol(cij). A value vi ∈ D(xi) is arc consistent (AC) if and only if for all xj ∈ Γ(xi) vi has an AC support on cij. A network is arc consistent if all the values of all its variables are arc consistent. We denote by AC(N) the network obtained by enforcing arc consistency on N.

A value vj ∈ D(xj) is a max restricted path consistent (maxRPC) support for vi ∈ D(xi) on cij if and only if it is an AC support and the tuple (vi, vj) can be extended to any third variable xk while satisfying cik and cjk. A value vi ∈ D(xi) is maxRPC iff for all xj ∈ Γ(xi) vi has a maxRPC support vj ∈ D(xj) on cij . A network is maxRPC if all the values of all its variables are maxRPC.

Given a constraint network N = (X,D, C), a value vi ∈ D(xi) is partition-one-AC (POAC) iff AC(N ∪ {xi = vi}) does not have empty domains, and ∀j ∈ 1..n, j ̸= i, ∃vj ∈ D(xj) such that vi ∈ AC(N ∪ {xj = vj}). A network is POAC if all the values of all its variables are POAC.

4 Multi-Armed Bandits for Adaptive Constraint Propagation

We describe a simple framework for adaptive propagation based on Multi-Armed Bandits (MAB). The successive selection of a consistency level during search is a sequential decision problem and as such, it can be represented as a multiarmed or k-armed (for k different consistencies) bandit problem. One needs to select amongst k consistencies to enforce in order to maximize the cumulative reward by selecting each time the best one. Initially, such a choice is taken under uncertainty, since the underlying reward distributions are unknown. Later in the process, potential rewards are estimated based on past observations. The more the search tree grows, the more knowledge we acquire and the better decisions we make.

The critical question that needs to be addressed in bandit problems is related to the tradeoff between "exploitation" of the arm with the greatest expected reward (based on the knowledge already acquired) and "exploration" of other, currently sub-optimal arms to further increase knowledge about them and which may become superior in the future. This is related to the exploitation vs. exploration dilemma in reinforcement learning.

4.1 The multi-armed bandit model

We use the multi-armed bandit problem to learn what is the appropriate level of consistency to enforce during solving a CSP. We call MAB selector the ML component that decides a level of consistency to use. We can have such a selector for each constraint, for each variable, or, more coarsely, for each level of the search tree. The selector is based on a model defined over:

• A set of k arms {LC1, . . . , LCk}. Each arm corresponds to an algorithm that enforces a specific level of local consistency.
• A set of rewards Ri(j) ∈ R, 1 ≤ i ≤ k, j ≥ 1, where Ri(j) is the reward delivered when an arm LCi has been chosen at time j.

The reward function can be any measure that reflects the performance or a criterion that indicates the appropriate arm. The performance can be either positive (e.g., values removed) or negative (e.g., CPU time).

In MAB models, we must define a policy to choose the next arm based on the sequence of previous trials. It is important not to discard an arm forever to ensure that any arm that could become later optimal is not omitted in favor of other currently sub-optimal arms. As a result, it is useful to know the upper confidence bound (UCB) that any given arm will be optimal.

Since the model cannot always make the best decision, its expected loss or regret is considered after m times. Auer et al. [Auer and Cesa-Bianchi, 2002], propose a simple UCB policy that has an expected logarithmic growth of regret uniformly over m (not just asymptotically) without any prior knowledge regarding the reward distributions. Their policy, called UCB1, selects the arm i that maximizes:

where ¯ Ri is the mean of the past rewards of the i arm, mi is the number of times arm i was selected and m is the current number of all trials. The reward term ¯ Ri encourages the exploitation of local consistencies with higher-rewards, while the √ 2 ln m mi termpromotes the exploration of the less selected local consistencies.

The literature contains more elaborated versions of multiarmed bandits where additional parameters allow to insist more on exploration or exploitation depending on the context. As one of our goal is to assess the simplicity of this direction of research, we use the most basic regret policy defined in equation 1, where no parameter tuning is required.

4.2 AMAB selector for adapting consistency online

When designing a MAB selector we have to define the reward function and to decide the granularity at which the MAB operates. Concerning the granularity, there exist various natural ways to attach MAB selectors to a CP solver. We could decide to attach a MAB selector per variable in the network, per constraint, etc. Depending on the place where a MAB selector is attached, the most natural parameters used for the reward function may change.

In this preliminary work, we follow an observation made by Debruyne. In [Debruyne, 1998], he observed that changing the level of consistency with the depth in the search tree can improve search significantly. By depth, we mean the number of variables assigned. 1 In his work, Debruyne was manually tuning the solver to change the level of consistency from AC to maxRPC or maxRPC to AC at predefined depths depending on the class of problems, based on his own experience. We then decided to define a MAB model where we have a MAB selector at each depth in the search tree. Our goal is to show that the MAB selectors will learn by themselves which level of local consistency to use at which depth.

Once the places to attach MAB selectors is decided, we have to define the reward function. We chose to define a reward function that takes into account the actual CPU time needed to explore the subtree rooted at this depth once the decision of which local consistency to use has been taken by the MAB selector of the given depth.

For each depth in the search tree we have a separate MAB selector, with its own time parameter j. We denote by Ti(m) the CPU time needed to enforce LCi at the mth visit of a node at the given depth plus the time to explore the subtree rooted there. (Ti(m) is not defined if this is not LCi that has been chosen at time m.) The reward Ri(j) is computed based on the performance of LCi at time j compared to performance of all consistencies at previous visits at this depth.

Formula 2 is normalized so that Ri(j) ∈ [0, 1]. Indeed, remember that ρ in Formula 1 computes the sum of rewards.

The backtrack search algorithm that uses this MAB model calls the MAB selector of a given depth h each time it instantiates a variable at depth h in the search tree. The search algorithm progressively builds a search tree and applies a local consistency LCi at depth h guided by results of previous choices at the same depth.

These are the steps that the algorithm follows after each variable assignment x ← a:

1. We call the MAB selector of the depth at which x ← a occurs.
2. We select the LCi that maximizes ρ(i).
3. We store the current time startTime[depth] of the machine.
4. LCi is executed on that node.
5. When backtracking to that node, we read the current time endTime of the machine and we update the reward Ri(j). Ti(j), which was defined as the sum of the CPU time required to enforce LCi after the assignment of x plus the CPU time required to explore the resulting subtree is simply obtained by endTime - startT ime[depth].

1 In 2-way branching, x = a is considered as an assignment whereas the refutation x ̸= a is not.

5 Experimental Evaluation

We ran experiments on problem classes from real world applications and classes following a regular pattern involving a random generation (REAL and PATT in www.cril.univartois.fr/˜lecoutre/benchmarks.html). The algorithms were implemented with a CP solver written in Java and tested on an 2.8 GHz Intel Xeon processor and 16 GB RAM. A cut-off of 3,600 seconds was set for all algorithms and all instances. We used the dom/deg heuristic for variable ordering and lexicographic value ordering. We used three levels of consistency: AC (AC2001 [Bessiere et al., 2005]), maxRPC (maxRPC3 [Balafoutis et al., 2011]), and POAC (POAC1 [Balafrej et al., 2014]). For AC2001 and maxRPC3 we used their residual versions ([Lecoutre and Hemery, 2007]) to avoid maintaining AC and maxRPC supports during search. From these three consistencies we built six solving methods: Three of them maintain a single local consistency during the whole search (AC, maxRPC or POAC). The three others are adaptive methods using a MAB selector to decide which local consistency to apply among {AC, maxRPC}, {AC, POAC} and {AC, maxRPC, POAC}, respectively denoted by ACmaxRPC, AC-POAC and AC-maxRPC-POAC.

Table 1 (except last column) shows the results of the six solving methods where the adaptive ones use a MAB selector for each depth in the search tree and a reward function based on CPU time as described in Section 4.2. Comparing these six methods on the instances solved by all of them, we observe that overall, adaptive methods are faster than methods maintaining a single consistency. This is especially true on difficult problems. The row 'Total' (last row of the table) shows that all adaptive methods have a total sum of CPU time smaller than the CPU time of methods maintaining a single consistency. The adaptive method using the three consistencies (AC-maxRPC-POAC) is the fastest. The total number of solved instances confirms this behavior as adaptive methods including a strong consistency LC solve more instances than those maintaining LC alone. Once more, ACmaxRPC-POAC is the best, solving 309 instances among the

313 tested.

When looking at the results in more details, we observe that in a few cases, when one of the local consistencies behaves significantly worse than the others (such as POAC in graph), the MABs including it are penalized. The reason is that UCB forces the MABs to select this bad consistency for exploration purposes. It takes some time to learn not to select it.

In the last column of Table 1, we report the results of an experiment done to assess the learning capabilities of our MAB selectors. The solver uses the three consistencies AC, maxRPC, and POAC, but instead of using a MAB selector to select the right consistency to apply at a node, it selects one consistency randomly. Thanks to the use of three consistencies, this baseline algorithm has a good behavior. It is better than any single consistency and also better than MAB selectors with only two consistencies. But when the MAB also uses three consistencies, it has a significantly better behavior (faster and solving more instances).

In Figure 1, we report the cactus plot of the number of instances solved per method while the time limit increases. What we see on the zoom on the first seconds of time is that AC is the one that solves the more instances in less than 5 seconds and POAC the less. When the time limit is between 5 seconds and approximately 200 seconds, maxRPC is the one that solves more instances while AC deteriorates. Among the methods maintaining a single consistency, POAC is the one that solves the fewest instances until we reach a time limit of 500 seconds. After 500 seconds, AC becomes the worst among all and it remains the worst until the cutoff of 3600 seconds. Concerning the adaptive methods, ACmaxRPC is second best in the zone where maxRPC is the best (5-200 seconds). But as time increases, AC-POAC and ACmaxRPC-POAC solve more instances than the other methods, AC-maxRPC-POAC being the clear winner by solving more instances than all others from 200 seconds until the cutoff.

The important information that this cactus plot gives us, is that, on very hard instances, the adaptive methods are never worse than any consistency they include (e.g., AC-maxRPC

Table 1: Sum of CPU times (in sec.) and #solved instances per class and per algorithm.

AC

maxRPC POAC AC-maxRPC AC-POAC AC-maxRPC-POAC

AC-maxRPC-POAC(rand)

is close to maxRPC and better than AC) and they can even be superior to any consistency they include (e.g., AC-POAC solves constantly more instances than AC or POAC). This means that given an instance to solve, they not only understand which consistency is the best overall, but they benefit from the temporary superiority of another consistency.

We also ran Adaptive POAC [Balafrej et al., 2014] on the same classes. Adaptive POAC is generally faster than MABs on easy instances. On hard instances, Adaptive POAC is far slower than MABs containing POAC: it only solves 296 instances overall, that is, more than single consistencies and AC-maxRPC, but less than AC-POAC, AC-maxRPC-POAC, and AC-maxRPC-POAC(rand).

6 Discussion

Simplicity of use and low computation cost are good reasons to choose multi-armed bandits for adapting consistency during search. Low computation cost is an essential property for an online technique. Another reason is that successive choices of a consistency at a given depth yield rewards that are independent. This ensures that there is no hidden correlation that a MAB selector could not learn (as MABs only learn independent rewards). In a setting where we would learn sequences of choices of local consistencies on a sequence of successive depths, a Q-learning framework would probably be more relevant [Sutton and Barto, 1998; Xu et al., 2009].

The MAB model as defined in equations 1 and 2 has originally been proposed for stationary arms, that is, arms for which the reward received when playing an arm follows a probability distribution that remains unchanged along the plays. Under this condition, UCB1 ensures that the average regret converges to zero with probability 1, that is, UCB1 ensures that the optimal arm is played exponentially more often than any other arm. In our setting, however, we cannot guarantee that arms are stationary because the reward of a local consistency may change as search progresses. Several versions of UCB have been proposed to deal with environments that change over time. However, it is recognized that the basic UCB has low probability to show a worst-case behavior when applied to such changing environments [Fialho et al., 2010]. In addition, versions of UCB that deal with changing environments require some parameter tuning, such as the decay factor or the length of time window. As observed in [Fialho et al., 2010], a bad configuration of the parameters can produce too much forgetting when the environment does not change as fast as expected. For these reasons, in this first attempt to exploit MAB in adaptive propagation, we chose to remain on the simple version of UCB where there is no parameter to tune before use.

To illustrate this ability of UCB to adapt despite dynamic environment, we focus on the internal behavior of our MABs. Figure 2 displays the internal behavior of the MAB selector AC-maxRPC-POAC at several depths (77, 104, 155) when solving the instance 3-insertion-4-3. As time increases, the values of the mean reward ¯ Ri and the ratio of calls to each consistency are plotted. (The ratio is the number of times LCi was selected divided by total number of times the selector was called.) On all three graphs we observe that MAB selects more frequently the local consistency with the highest mean reward. On the top graph we see that at depth 77, POAC is learned as the best and is then chosen the most often. On the middle graph we see that in the begining, POAC is preferred to AC and maxRPC because its mean reward is the highest. After 6000 time steps, maxRPC suddenly starts increasing its reward resulting in being quickly promoted, as the steep inclination of its ratio curve shows. This both illustrates that rewards are non stationary and that our simple UCB is able to detect it. Finally, on the bottom graph we see that at depth 155 (close to the leaves) things are less clear but AC tends to be the preferred one, confirming an observation made in [Debruyne, 1998].

Figure 2 shows that MAB learns what is the most efficient consistency to enforce at a given time during search. AC-maxRPC-POAC solved this instance in 1, 661 seconds, POAC in 4, 602 seconds and both AC and maxRPC failed to solve it in 4 hours. The adaptive technique was able to be faster than the best consistency alone (here POAC), because it is able to enforce the right consistency at the right node during search. MAB selectors can construct the right combination of the available propagation levels of a solver, adapted to each instance, without any preprocessing knowledge or other information prior to search. These first results show the potentiality of a CP solver that is able to exploit any algorithm that it has in its arsenal without having the knowledge of when/where to use it. This is another step in the direction of an autonomous solver.

7 Conclusion

In this paper, we have introduced a simple framework for adaptive constraint propagation based on multi-armed bandits learning. The proposed framework allows the automatic selection of the right propagation technique among several, overcoming the strong limitation of previous works. Due to its light learning mechanism, our framework can be applied dynamically, considering the effects of propagation during search. The experiments on various benchmark classes showed that the proposed framework increases the efficiency and robustness of a CP solver.

Acknowledgments

We would like to thank Nadjib Lazaar for his help on multiarmed bandits.