Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Sur la Compilation de Jeux de Prédiction Combinatoire

Abstract : In online optimization, the goal is to iteratively choose solutions from a decision space, so as to minimize the average cost over time. As long as this decision space is described by combinatorial constraints, the problem is generally intractable. In this paper, we consider the paradigm of compiling the set of combinatorial constraints into a deterministic and Decomposable Negation Normal Form (dDNNF) circuit, for which the tasks of linear optimization and solution sampling take linear time. Based on this framework, we provide efficient characterizations of existing combinatorial prediction strategies, with a particular attention to mirror descent techniques. These strategies are compared on several real-world benchmarks for which the set of Boolean constraints is preliminarily compiled into a dDNNF circuit.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Monday, July 16, 2018 - 5:14:10 PM
Last modification on : Wednesday, November 3, 2021 - 6:49:45 AM
Long-term archiving on: : Wednesday, October 17, 2018 - 4:17:44 PM


Files produced by the author(s)


  • HAL Id : hal-01840835, version 1



Frédéric Koriche. Sur la Compilation de Jeux de Prédiction Combinatoire. Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes (JFPDA 2018), Jul 2018, Nancy, France. ⟨hal-01840835⟩



Record views


Files downloads