Combinatorial Multi-armed Bandits for Resource Allocation

Jinhang Zuo, Carlee Joe-Wong

Introduction

Resource allocation is a fundamental challenge in engineering and computer science. Whether it involves a cloud provider distributing CPU cycles among virtual machines or a wireless base station partitioning spectrum for mobile users, the goal is to maximize a cumulative reward given a finite budget. Traditional optimization assumes that the reward functions—the mapping from resource allocation to utility—are known. However, in real-world scenarios, these functions are often stochastic and unknown, necessitating an online learning approach. This paper presents a robust framework for solving these problems using the Combinatorial Multi-armed Bandit (CMAB) framework.

The Resource Allocation Problem

The paper addresses the problem of sequential resource allocation under uncertainty. In this setting, a decision-maker must repeatedly allocate a fixed budget across multiple resources. Because the rewards are unknown, the agent faces the classic exploration-exploitation tradeoff: should it stick with allocations that have performed well in the past (exploit), or explore new allocations to discover potentially higher rewards (explore)?

Unlike previous research that often relied on restrictive assumptions—such as the reward functions being strictly linear or concave—this work proposes a general framework that works for any reward function. This flexibility allows the model to fit complex, real-world scenarios where reward structures may be irregular.

Methodological Framework

The authors introduce two primary algorithms based on the Combinatorial Upper Confidence Bound (CUCB) framework, tailored for different budget types. Both algorithms rely on semi-bandit feedback, meaning the agent observes the individual reward from every resource it allocated a budget to, rather than just a single total sum.

1. Discrete Resource Allocation (CUCB-DRA)

For discrete budgets, the algorithm treats each possible pair of (resource $k$, budget $a$) as a "base arm." It maintains an Upper Confidence Bound (UCB) for each arm—essentially an optimistic estimate of the expected reward. In each round, these optimistic estimates are fed into an offline oracle (an optimization solver) to determine the best allocation for that step.

2. Continuous Resource Allocation (CUCB-CRA)

Continuous budget spaces present a greater challenge due to the infinite number of possible allocations. The authors employ a fixed discretization technique, slicing the continuous budget into small, discrete steps. By assuming the reward function is Lipschitz continuous (meaning small changes in budget lead to small changes in reward), they can mathematically bound the error introduced by this "rounding."

Key Insights

Decoupling Learning from Optimization

A significant contribution of this work is the decoupling of the learning process from the optimization task. By utilizing an offline oracle, the bandit algorithm focuses on managing uncertainty (the learning), while the oracle handles the mathematical constraints of the budget (the optimization). This modularity allows for the integration of various optimization solvers depending on the specific application.

The Discretization Trade-off

For the continuous case, the authors identify a "Goldilocks" level of discretization. If the steps are too large, the system loses accuracy (discretization error). If they are too small, the agent has too many arms to learn about, slowing down the learning process. The paper mathematically identifies the optimal granularity to balance these two factors.

Results and Performance

The efficiency of these algorithms is measured by "regret"—the difference between the reward of the optimal allocation (if the functions were known) and the reward actually obtained.

  • Logarithmic Regret for Discrete Budgets: The authors prove that CUCB-DRA achieves $O(\ln T)$ regret. In bandit theory, logarithmic regret is the "gold standard," indicating that the agent's average error per round drops toward zero very quickly.
  • Sublinear Regret for Continuous Budgets: For the continuous case, they achieve a regret bound of $O(T^{2/3} (\ln T)^{1/3})$. While not as tight as the discrete case, it is still sublinear, proving that the agent will eventually converge on a near-optimal strategy.
  • Smoothness Guarantees: The proofs demonstrate that these rewards satisfy "1-norm bounded smoothness," a technical condition ensuring that the combinatorial nature of the problem does not cause the learning complexity to explode.

Limitations and Future Work

While the framework is robust, the authors identify several areas for improvement:

  1. Feedback Granularity: The current model only considers the final reward. In some systems, the reward might reveal extra information about the environment (e.g., the "urgency" of a task) that could be exploited to further reduce regret.
  2. Continuous Regret Gap: The $T^{2/3}$ bound for continuous budgets is looser than the discrete $O(\ln T)$. Future work may explore adaptive discretization—where the algorithm "zooms in" and uses finer steps only in promising areas of the budget space—to close this gap.
  3. Oracle Efficiency: The real-world performance is tied to the efficiency of the offline oracle. If the underlying optimization problem is NP-hard, the algorithm's runtime might become a bottleneck in practical applications.

Summary updated

BibTeX
@inproceedings{zuo2021combinatorial,
  author = {Jinhang Zuo and Carlee Joe-Wong},
  title = {{Combinatorial Multi-armed Bandits for Resource Allocation}},
  booktitle = {CISS},
  year = {2021},
  url = {https://openreview.net/forum?id=temJ6_OIAe},
}
Figure