DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems
Abstract
The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multi-armed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed Constraint Optimization Problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions.
Cite
Text
Ottens et al. "DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8129Markdown
[Ottens et al. "DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/ottens2012aaai-duct/) doi:10.1609/AAAI.V26I1.8129BibTeX
@inproceedings{ottens2012aaai-duct,
title = {{DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems}},
author = {Ottens, Brammert and Dimitrakakis, Christos and Faltings, Boi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {528-534},
doi = {10.1609/AAAI.V26I1.8129},
url = {https://mlanthology.org/aaai/2012/ottens2012aaai-duct/}
}