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 metadatas
Contributor : Cyril Terrioux <>
Submitted on : Thursday, February 4, 2021 - 9:15:55 PM
Last modification on : Saturday, February 6, 2021 - 3:29:25 AM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-05-01

Please log in to resquest access to the document




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