Abstract
Bandit Combinatorial Optimization (BCO) involves making sequential decisions over a vast set of feasible solutions, often referred to as the action set. In many practical scenarios, such as network routing or Steiner tree construction, the number of possible actions grows exponentially with the size of the problem, rendering standard bandit algorithms computationally infeasible. This paper presents COMBD3, an efficient algorithm that leverages Zero-suppressed Binary Decision Diagrams (ZDDs) to represent massive action sets compactly. By performing dynamic programming directly on the ZDD structure, COMBD3 achieves state-of-the-art theoretical regret bounds while providing orders of magnitude improvements in scalability and running time compared to existing methods.
Introduction
In the Bandit Combinatorial Optimization (BCO) framework, a learner repeatedly selects a combinatorial object (e.g., a path in a graph) and receives feedback in the form of the total cost associated with that object. Unlike the full-information setting, the learner only observes the aggregate cost of the chosen action, not the individual costs of its components (edges).
The primary bottleneck in BCO is the sheer size of the action set. For instance, finding all paths between two nodes in a large network or all possible Steiner trees involves a number of choices that is exponential relative to the number of edges. Traditional algorithms require explicit enumeration or complex mathematical operations over every possible action, which is impossible for large-scale real-world networks. Furthermore, many existing "efficient" algorithms are restricted to specific structures like directed acyclic graphs and fail on general undirected networks.
Methodology: The ZDD Approach
The core innovation of this work is the integration of Zero-suppressed Binary Decision Diagrams (ZDDs) into the online learning process. A ZDD is a graph-based data structure designed to represent collections of sets efficiently by suppressing redundant information.
The proposed algorithm, COMBD3, utilizes ZDDs in two critical ways:
- Efficient Sampling: The authors adapt a "weight pushing" technique that allows for sampling an action from the ZDD in time proportional to the number of nodes in the ZDD, rather than the total number of actions.
- Unbiased Estimation: BCO algorithms rely on a Co-occurrence Probability Matrix (CPM) to update their internal models. Calculating the CPM is typically the most computationally expensive step. COMBD3 introduces a novel Dynamic Programming (DP) approach that computes the CPM through forward and backward passes over the ZDD, transforming an exponential-time task into one that is linear relative to the ZDD's size.
Additionally, the authors introduce COMBD (COMBAND with Decreasing Parameters), a theoretical refinement that ensures "any-time" performance guarantees, meaning the algorithm remains effective even without prior knowledge of the total number of rounds.
Experimental Evaluation
The performance of COMBD3 was evaluated using both artificial grid networks and real-world topologies from the Internet Topology Zoo. In artificial $3 \times m$ grid networks, the algorithm was tested on Online Shortest Path (OSP) and Dynamic Steiner Tree (DST) problems.
As shown in the results, COMBD3 demonstrates remarkable scalability. For a Steiner Tree problem on a $3 \times 10$ grid, which contains approximately 110 billion possible actions, the ZDD representation requires only about 1 million nodes. While baseline algorithms either exceeded memory limits or took hours to compute, COMBD3 completed the same tasks in seconds.
In simulations of real-world network congestion games (using the MCI and ATT North America topologies), players using COMBD3 successfully learned to distribute traffic across multiple paths to minimize costs, achieving near-optimal strategies using only limited bandit feedback. The algorithm maintains strong theoretical guarantees, achieving $O(T^{2/3})$ regret with high probability or $O(\sqrt{T})$ expected regret.
Conclusion
By bridging the gap between compact data structures and online learning, this research provides a practical and theoretically sound solution for large-scale bandit combinatorial optimization. The use of ZDDs allows COMBD3 to handle action sets of astronomical size, making it a powerful tool for adaptive routing, network design, and other complex decision-making problems in dynamic environments. Future work may explore the construction of ZDDs for more diverse combinatorial structures beyond paths and trees.
Summary updated