Improved Algorithms for Multi-period Multi-class Packing Problems with~Bandit~Feedback

Wonyoung Kim, Garud Iyengar, Assaf Zeevi

TL;DR

This paper introduces a novel algorithm, AMF (Allocate to the Maximum First), for solving complex resource allocation problems where decisions are based on contextual information and feedback is limited. By utilizing a new "doubly robust" estimator that pools data across different arrival classes and leverages the features of unselected actions, the authors achieve a significantly better regret bound that scales sublinearly with context dimension and the number of classes, even under tight budget constraints.

What Problem Does This Paper Address?

Imagine you are managing a limited inventory of medical supplies or digital ad slots. Every time a "customer" arrives, you see their features (context), choose one of several possible actions, and then observe a reward and a resource cost. This is the Multi-period Packing Problem (MPP) with bandit feedback.

The challenge is three-fold:

  1. Bandit Feedback: You only see the outcome of the action you actually took. You don't know what would have happened if you had chosen differently.
  2. Knapsack Constraints: You have a hard budget. If you run out of resources before the time horizon ends, you can't take any more actions.
  3. Heterogeneity (Multi-class): Arrivals aren't all the same; they belong to different "classes" (e.g., different demographics or regions) with different underlying behaviors.

Previous research struggled to provide efficient algorithms when the budget was small or when there were many different classes. Specifically, a major open question in the field was whether an algorithm could achieve "sublinear dependence" on the context dimension $d$ when the budget $B$ is only proportional to $\sqrt{T}$ (where $T$ is the total time).

Methods

The authors propose the Linear Multi-class Multi-period Packing (LMMP) framework. Their solution relies on two key innovations:

  • The Doubly Robust (DR) Estimator: Standard bandit algorithms only learn from the action taken. The authors realized that even if an action isn't chosen, its context (the features associated with that choice) is still observed. Their new estimator uses these "missing" contexts to build a more accurate model of the world much faster than traditional methods. This allows the algorithm to "pool" data across different classes, effectively learning the shared structure of the problem.
  • The AMF Algorithm: "Allocate to the Maximum First" is an optimistic policy. At each step, it solves a closed-form optimization problem that balances the potential reward (using Upper Confidence Bounds) against the potential resource cost (using Lower Confidence Bounds). Crucially, it allows the decision-maker to "skip" an arrival if the cost-to-reward ratio is unfavorable, saving budget for better opportunities later.

Datasets

The paper evaluates the algorithm using synthetic experiments designed to test the limits of the theory.

  • Setup: They simulated environments with up to 20 actions ($K$), 20 resources ($m$), and varying context dimensions ($d$).
  • Benchmarks: They compared AMF against the state-of-the-art Online Mirror Descent-based algorithm (referred to as OCO) from Agrawal & Devanur (2016).
  • Scenarios: They tested different budget levels, specifically $B = \sqrt{dT^{3/4}}$ and the more challenging $B = \sqrt{dT}$.

Key Insights and Ideas

  • Context is "Free" Information: Even if you don't pick an action, you've seen its features. By treating unselected actions as a "missing data" problem and applying statistical techniques like Doubly Robust estimation, you can learn the underlying parameters much faster.
  • Transfer Learning via Pooling: In a multi-class setting, traditional algorithms treat each class separately, leading to regret that grows linearly with the number of classes ($J$). By pooling data, AMF achieves a regret bound that scales with $\sqrt{J}$, a massive improvement for large-scale systems.
  • Solving the "Small Budget" Problem: The authors proved that their algorithm remains efficient even when the budget is relatively small ($\Omega(\sqrt{T})$). This settles a long-standing open problem regarding the feasibility of contextual bandits with knapsacks under tight constraints.

Key Results

  • Theoretical Bound: The algorithm achieves a regret of $\tilde{O}(\frac{OPT}{B}\sqrt{JdT})$. This is the first result to show sublinear dependence on $d$ for budgets as small as $\sqrt{T}$.
  • Numerical Superiority: In simulations, AMF consistently outperformed the OCO benchmark. While the OCO algorithm often ran out of budget prematurely (leading to a sharp spike in regret), AMF managed resources gracefully throughout the entire time horizon.
  • Robustness: Sensitivity analysis showed that the algorithm's performance is not highly sensitive to its hyperparameters ($\gamma$ and $\delta$), making it practical for real-world deployment.

Limitations and Future Work

  • Non-Degeneracy Assumption: The theoretical guarantees rely on the assumption that the stochastic contexts are "non-degenerate" (i.e., they provide enough variability to explore the feature space). While common in literature, this might not hold in highly constrained or biased real-world data.
  • Linearity: The model assumes that rewards and costs are linear functions of the context. Exploring non-linear (e.g., neural network-based) reward functions within this packing framework is a natural next step.
  • Resource Dynamics: The current model assumes a fixed budget that is consumed. Future work could look at "replenishing" resources or more complex inventory dynamics.

Summary updated

BibTeX
@inproceedings{kim2023improved,
  author = {Wonyoung Kim and Garud Iyengar and Assaf Zeevi},
  title = {{Improved Algorithms for Multi-period Multi-class Packing Problems with~Bandit~Feedback}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=TlCi3HwLMj},
}
Figure