Efficient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams

Shinsaku Sakaue, Masakazu Ishihata, Shin-ichi Minato
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:585-594, 2018.

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 this Paper

BibTeX
@InProceedings{pmlr-v84-sakaue18a, title = {Efficient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams}, author = {Sakaue, Shinsaku and Ishihata, Masakazu and Minato, Shin-ichi}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {585--594}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/sakaue18a/sakaue18a.pdf}, url = {https://proceedings.mlr.press/v84/sakaue18a.html}, 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.} }
Endnote
%0 Conference Paper %T Efficient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams %A Shinsaku Sakaue %A Masakazu Ishihata %A Shin-ichi Minato %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-sakaue18a %I PMLR %P 585--594 %U https://proceedings.mlr.press/v84/sakaue18a.html %V 84 %X 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.
APA
Sakaue, S., Ishihata, M. & Minato, S.. (2018). Efficient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:585-594 Available from https://proceedings.mlr.press/v84/sakaue18a.html.

Related Material