Efficient Bandit Combinatorial Optimization Algorithm with Zero-Suppressed Binary Decision Diagrams
Abstract
We consider bandit combinatorial optimization (BCO) problems. A BCO instance generally has a huge set of all feasible solutions, which we call the action set. To avoid dealing with such huge action sets directly, we propose an algorithm that takes advantage of zero-suppressed binary decision diagrams, which encode action sets as compact graphs. The proposed algorithm achieves either $O(T^{2/3})$ regret with high probability or $O(\sqrt{T})$ expected regret at any $T$-th round. Typically, our algorithm works efficiently for BCO problems defined on networks. Experiments show that our algorithm is applicable to various large BCO instances including adaptive routing problems on real-world networks.
Cite
Text
Sakaue et al. "Efficient Bandit Combinatorial Optimization Algorithm with Zero-Suppressed Binary Decision Diagrams." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[Sakaue et al. "Efficient Bandit Combinatorial Optimization Algorithm with Zero-Suppressed Binary Decision Diagrams." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/sakaue2018aistats-efficient/)BibTeX
@inproceedings{sakaue2018aistats-efficient,
title = {{Efficient Bandit Combinatorial Optimization Algorithm with Zero-Suppressed Binary Decision Diagrams}},
author = {Sakaue, Shinsaku and Ishihata, Masakazu and Minato, Shin-ichi},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {585-594},
url = {https://mlanthology.org/aistats/2018/sakaue2018aistats-efficient/}
}