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

Wonyoung Kim, Garud Iyengar, assaf zeevi

Introduction

This article explores the Linear Multi-class Multi-period Packing (LMMP) problem, a framework for making sequential resource-allocation decisions for heterogeneous populations under bandit feedback. The authors propose a novel "doubly robust" estimator that learns from unselected actions alongside a closed-form policy called AMF (Allocate to the Maximum First). This approach achieves sublinear regret even with significantly smaller budgets than previous state-of-the-art methods, resolving a long-standing open problem in the field.

The Challenge: Contextual Bandits with Knapsacks

Imagine an e-commerce platform with a limited inventory of various products. Customers from different "classes" (e.g., varying demographics or regions) arrive sequentially. For each customer, the platform observes a "context" (user features) and must choose one of several offers. Each offer yields an unknown reward and consumes unknown amounts of resources.

The catch is twofold: you only observe the outcome of the offer you actually make (bandit feedback), and you must stay within a strict total budget. This scenario is a classic example of the Contextual Bandits with Knapsacks (CBwK) problem. While well-studied, existing solutions have historically suffered from two major flaws:

  1. Poor Scaling: They struggle to handle multiple classes of arrivals efficiently, with performance often scaling linearly with the number of classes.
  2. The "Budget Gap": A famous open problem from 2016 noted that existing algorithms required a very large budget ($B = \Omega(T^{3/4})$) to guarantee that the "regret" (the performance gap between the algorithm and an omniscient oracle) wouldn't grow too fast.

Methodology: A Two-Pronged Solution

The authors tackle these scaling and budget issues with two primary innovations:

1. The Doubly Robust (DR) Estimator

Standard bandit algorithms only learn from the action they explicitly choose. However, in contextual problems, the decision-maker observes the features (contexts) of all possible actions at every step, even the unselected ones.

The authors develop a new estimator using a statistical "missing data" technique. By carefully resampling actions and creating "pseudo-rewards," they leverage the contexts of unselected actions. This allows for data pooling across different classes, leading to a much faster convergence rate ($O(\sqrt{Jd/n})$) for the model parameters. The realization that context is free information allows the algorithm to learn the underlying structure of the problem much faster than traditional bandit methods.

2. The AMF Algorithm

The AMF (Allocate to the Maximum First) algorithm operates in two phases:

  • Exploration: Initially, it takes actions that help "spread out" the data (maximizing the minimum eigenvalue of the context matrix) to ensure the model is well-calibrated.
  • Exploitation: Once the model is stable, it uses an optimistic policy. It calculates Upper Confidence Bounds (UCB) for rewards and Lower Confidence Bounds (LCB) for resource consumption. It then solves a per-period optimization problem to decide which action to take (or whether to skip the arrival entirely to save budget). Crucially, the authors provide a closed-form solution for this optimization, making it highly computationally efficient.

Key Results and Insights

The proposed algorithm achieves a theoretical regret bound of $\tilde{O}(\frac{OPT}{B} \sqrt{JdT})$. This is a significant improvement in how the error scales with the number of classes ($J$) and the dimension ($d$). By improving the estimation rate, the authors prove that sublinear regret is possible even when the budget $B$ is only $\Omega(\sqrt{T})$, effectively closing the 2016 open problem.

Empirically, the algorithm was evaluated using synthetic datasets designed to test specific theoretical limits, demonstrating clear superiority over standard Online Convex Optimization (OCO) benchmarks.

Budget Efficiency

AMF maintains high performance even as budgets are tightened to the $\sqrt{T}$ limit, a threshold where previous algorithms often fail or run out of resources prematurely.

Regret comparison between AMF and OCO under a restricted budget

Dimension Agnosticism

While benchmark regret often grows sharply with the feature dimension $d$, the AMF algorithm's regret remains remarkably stable, demonstrating the power of its improved estimator across varying feature spaces.

Log-log plot of regret versus dimension

Limitations and Future Work

While AMF represents a significant step forward, the authors note a few limitations:

  • Linearity Assumption: The model assumes that rewards and resource consumption are linear functions of the context. Exploring non-linear (e.g., neural network-based) reward models is a natural next step.
  • Non-Degeneracy: The theoretical guarantees rely on the assumption that the contexts are "non-degenerate" (i.e., they span the feature space well). If contexts are highly correlated or low-dimensional, the exploration phase might take longer.
  • Computational Overhead: While the policy itself is closed-form, the estimator requires updating and inverting a $Jd \times Jd$ matrix, which could become a bottleneck for extremely high-dimensional problems with many classes.

Summary updated

Abstract

We consider the linear contextual multi-class multi-period packing problem (LMMP) where the goal is to pack items such that the total vector of consumption is below a given budget vector and the total value is as large as possible. We consider the setting where the reward and the consumption vector associated with each action is a class-dependent linear function of the context, and the decision-maker receives bandit feedback. LMMP includes linear contextual bandits with knapsacks and online revenue management as special cases. We establish a new estimator which guarantees a faster convergence rate, and consequently, a lower regret in LMMP. We propose a bandit policy that is a closed-form function of said estimated parameters. When the contexts are non-degenerate, the regret of the proposed policy is sublinear in the context dimension, the number of classes, and the time horizon $T$ when the budget grows at least as $\sqrt{T}$. We also resolve an open problem posed in Agrawal & Devanur (2016) and extend the result to a multi-class setting. Our numerical experiments clearly demonstrate that the performance of our policy is superior to other benchmarks in the literature.
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