Skip to Main content Skip to Navigation
Conference papers

On the Refinement of Conflict History Search Through Multi-Armed Bandit

Mohamed Sami Cherif 1 Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : Reinforcement learning has shown its relevance in designing search heuristics for backtracking algorithms dedicated to solving decision problems under constraints. Recently, an efficient heuristic, called Conflict History Search (CHS), based on the history of search failures was introduced for the Constraint Satisfaction Problem (CSP). The Exponential Recency Weighted Average (ERWA) is used to estimate the hardness of constraints and CHS favors the variables that often appear in recent failures. The step parameter is important in CHS since it controls the estimation of the hardness of constraints and its refinement may lead to notable improvements. The current research aims to achieve this objective. Indeed, a Multi-Armed Bandits (MAB) framework can select an appropriate value of this parameter during the restarts performed by the search algorithm. Each arm represents a CHS with a given value for the step parameter and it is rewarded by its ability to improve the search. A training phase is introduced earlier in the search to help MAB choose a relevant arm. The experimental evaluation shows that this approach leads to significant improvements regarding CHS and other state-ofthe-art heuristics.
Document type :
Conference papers
Complete list of metadata
Contributor : Cyril Terrioux <>
Submitted on : Thursday, February 4, 2021 - 9:15:55 PM
Last modification on : Saturday, February 6, 2021 - 3:29:25 AM
Long-term archiving on: : Wednesday, May 5, 2021 - 7:30:21 PM


Files produced by the author(s)




Mohamed Sami Cherif, Djamal Habet, Cyril Terrioux. On the Refinement of Conflict History Search Through Multi-Armed Bandit. IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2020, Baltimore, United States. pp.264-271, ⟨10.1109/ICTAI50040.2020.00050⟩. ⟨hal-03132228⟩



Record views