Loading...
Please wait, while we are loading the content...
Similar Documents
cient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sakaue, Shinsaku Ishihata, Masakazu Shin-Ichi |
| Copyright Year | 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 zerosuppressed 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( p T ) expected regret at any T -th round. Typically, our algorithm works e ciently 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://proceedings.mlr.press/v84/sakaue18a/sakaue18a.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
