Abstract
In this paper, we consider online continuous DR-submodular maximization with linear stochastic long-term constraints. Compared to the prior work on online submodular maximization, our setting introduces the extra complication of stochastic linear constraint functions that are i.i.d. generated at each round. In particular, at each time step a DR-submodular utility function and a constraint vector, i.i.d. generated from an unknown distribution, are revealed after committing to an action and we aim to maximize the overall utility while the expected cumulative resource consumption is below a fixed budget. Stochastic long-term constraints arise naturally in applications where there is a limited budget or resource available and resource consumption at each step is governed by stochastically time-varying environments. We propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class of online problems. We analyze the performance of the OLFW algorithm and we obtain sub-linear regret bounds as well as sub-linear cumulative constraint violation bounds, both in expectation and with high probability.
Introduction
In many real-world scenarios—such as allocating advertising budgets or recommending content—decisions must be made sequentially under uncertainty. The goal is often to maximize a utility function exhibiting "diminishing returns," a property known as DR-submodularity. However, practitioners face two major hurdles: the reward function is typically unknown until after an action is taken, and the "cost" of an action is often stochastic, revealed only after the fact.
While Online Convex Optimization (OCO) is well-understood for convex functions, many modern machine learning objectives are submodular but not necessarily concave. This work fills a critical gap by addressing how to maximize these complex functions while managing a long-term budget where costs are drawn from an unknown distribution. As summarized in the table below, this approach is the first to provide sub-linear regret and constraint violation bounds for DR-submodular objectives under adversarial or stochastic linear constraints.
The Online Lagrangian Frank-Wolfe (OLFW) Algorithm
To address these challenges, we propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm. OLFW combines a projection-free Frank-Wolfe variant with a Lagrangian quadratic penalty method.
Key features of the algorithm include:
- Projection-Free Optimization: By using a linear optimization oracle instead of expensive projections, Frank-Wolfe is computationally efficient for large-scale submodular maximization.
- Lagrangian Penalty: To respect long-term budget constraints, the algorithm incorporates a penalty term. If the cumulative resource consumption exceeds the expected budget, the penalty increases, steering future actions toward more "budget-friendly" choices.
- Empirical Estimation: The algorithm maintains a running average of observed costs to estimate the unknown underlying distribution of constraints.
- Confidence Intervals: To achieve high-probability guarantees, a "confidence term" ($\gamma_t$) is subtracted from constraint estimates, preventing over-optimism due to random fluctuations.
Key Results and Empirical Performance
The theoretical analysis proves that OLFW achieves sub-linear regret and sub-linear constraint violation. Notably, the high-probability regret bound is $O(\sqrt{T})$, which is the optimal rate for this class of online problems.
Empirically, OLFW was evaluated on the Jester Dataset, a collaborative filtering task involving 4.1 million ratings. The goal was to recommend jokes under a total time budget. As shown in the figures below, OLFW significantly outperforms standard baselines. While "Greedy" approaches ignore the budget and "Budget-Cautious" methods are too conservative, OLFW finds an optimal balance, maximizing cumulative utility while ending the simulation precisely at the budget limit.
The algorithm also demonstrates robustness across various hyperparameters, including step sizes ($\mu$) and penalty parameters ($\delta$), making it highly practical for real-world deployment.
Conclusion and Future Work
This work provides a robust framework for online DR-submodular maximization under stochastic constraints. While it marks a significant advancement, several avenues for future research remain. Currently, the framework assumes linear constraints; extending this to non-linear or submodular cost functions would broaden its applicability. Additionally, moving from "Full Information" feedback (where the entire utility function is revealed) to "Bandit Feedback" (where only the reward of the chosen action is seen) presents a more challenging and realistic frontier for online submodular optimization.
Summary updated