On Stochastic Contextual Bandits with Knapsacks in Small Budget Regime

This paper studies stochastic contextual bandits with knapsack constraints (CBwK), where a learner observes a context, takes an action, receives a reward, and incurs a vector of costs at every round. The learner aims to maximize the cumulative rewards across T rounds under the knapsack constraints with an initial budget of B. We study CBwK in the small budget regime where the budget B " Ωp ?

T q and propose an Adaptive and Universal Primal-Dual algorithm (AUPD) that achieves strong regret performance: 1) AUPD achieves Õpp1

νδ b q ? T q regret under the strict feasibility assumption without any prior information, matching the bestknown bounds; 2) AUPD achieves Õp ? T ν? b T 3 4 q regret without strict feasibility assumption, which, to the best of our knowledge, is the first result in the literature. Here, the parameter ν ˚represents the optimal average reward; b " BT is the average budget and δb is the feasibility/safety margin. We establish these strong results through the adaptive budget-aware design, which effectively balances reward maximization and budget consumption. We provide a new perspective on analyzing budget consumption using the Lyapunov drift method, along with a refined analysis of its cumulative variance. Our theory is further supported by experiments conducted on a large-scale dataset.