Compiling Combinatorial Prediction Games
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.
Code (0)
등록된 구현이 없습니다.
Tasks
NegationPredictionSimilar Papers 제목 키워드 기반
A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games
Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs…
Repeated Games against Budgeted Adversaries
We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player's best mixed strategy with …
Learning Self-Game-Play Agents for Combinatorial Optimization Problems
Recent progress in reinforcement learning (RL) using self-game-play has shown remarkable performance on several board games (e.g., Chess and Go) as well as video games (e.g., Atari games and Dota2). It is plausible to co…
Atari GamesBoard GamesCombinatorial OptimizationReinforcement Learning+1Quantum Combinatorial Games: Structures and Computational Complexity
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in representation, rich in structu…
Combinatorial Multi-armed Bandits for Real-Time Strategy Games
Games with large branching factors pose a significant challenge for game tree search algorithms. In this paper, we address this problem with a sampling strategy for Monte Carlo Tree Search (MCTS) algorithms called {\em n…
Multi-Armed BanditsReal-Time Strategy Games