Introduction
Stochastic optimization problems, such as the Stochastic Knapsack and Multi-Armed Bandits (MAB), are fundamental to resource allocation under uncertainty. However, traditional models often rely on simplifying assumptions—such as independence between rewards and sizes, or the martingale property—that rarely hold in complex real-world scenarios. This paper introduces the first constant-factor approximation algorithms for the Stochastic Knapsack with correlated rewards and sizes, as well as Budgeted Learning (MAB) without the martingale assumption.
The Challenge of Correlation and Non-Martingale Dynamics
In the standard Stochastic Knapsack problem, an agent selects items with uncertain sizes and rewards to maximize expected total reward within a budget $B$. Previous work largely assumed independence between an item's size and its reward. In practice, these are often correlated; for instance, a marketing campaign's "size" (time spent) might be directly linked to the probability of a "reward" (conversion).
Similarly, in Multi-Armed Bandits, the "martingale assumption" posits that the expected future reward of an arm is its current reward. This fails in "budgeted learning" where an arm might require multiple pulls to transition from a low-reward state to a high-reward state. The authors demonstrate that traditional "local" linear programming (LP) relaxations suffer from massive integrality gaps in these settings, as they fail to account for the temporal contention between items.
Methodology: Global Time-Indexed LP
The core innovation of this work is the move from local LPs to a Global Time-Indexed LP. Instead of merely tracking the total expected time an arm is pulled, this framework tracks when (at specific global time steps $t$) an arm is pulled. This approach explicitly models the physical reality that multiple items cannot occupy the same early time slots, which are most valuable for ensuring completion before the budget $B$ is exhausted.
Convex Decomposition and Strategy Forests
The authors prove that any fractional solution to this time-indexed LP can be decomposed into a convex combination of integral strategies. For problems modeled as trees, these are "Strategy Forests"; for more complex transition graphs, they are "Strategy DAGs." This decomposition provides a roadmap for converting theoretical LP values into executable policies.
Gap-Filling and Adaptive Rounding
A significant hurdle in rounding LP solutions is that they often suggest "preemptive" strategies—playing an arm, pausing, and returning later. To address this, the authors introduce a gap-filling procedure. They show that if these gaps are sufficiently small, the schedule can be "advanced" to play arms contiguously without significant performance loss. The final algorithm employs an adaptive rounding policy that samples from the decomposed strategies and uses the LP’s time-ordering to resolve contention in real-time.
Key Results
The paper establishes several landmark results in stochastic approximation:
- Stochastic Knapsack: A 1/8-approximation for the correlated version without cancellations.
- Cancellations: For versions allowing job cancellation, the authors provide a constant-factor approximation by partitioning the problem into "early reward" and "late reward" sub-cases.
- Non-Martingale Bandits: The first constant-factor approximation for budgeted learning on arbitrary Directed Acyclic Graphs (DAGs), removing the restrictive martingale requirement.
- Computational Efficiency: While the base LPs are pseudo-polynomial in the budget $B$, the authors describe a time-grouping technique that yields a truly polynomial-time algorithm with a minor reduction in the approximation factor (e.g., to 1/16).
Conclusion
By introducing time-indexed LP relaxations and sophisticated rounding techniques, this work bridges the gap between theoretical stochastic models and the complexities of real-world resource management. The ability to handle correlation and non-martingale dynamics marks a significant step forward in the design of robust, adaptive algorithms for uncertain environments. Future research may focus on tightening the constant factors and extending these decomposition methods to contextual bandit settings.
Summary updated