Online DR-Submodular Maximization with Stochastic Cumulative Constraints
This addresses resource allocation problems in stochastically time-varying environments, such as limited budget scenarios, but is incremental as it extends prior online submodular maximization work by adding stochastic constraints.
The paper tackles online continuous DR-submodular maximization with stochastic linear long-term constraints, where utility functions and constraint vectors are revealed after actions are taken, aiming to maximize utility while keeping expected cumulative resource consumption below a budget. It proposes the Online Lagrangian Frank-Wolfe algorithm, achieving sub-linear regret and constraint violation bounds in expectation and with high probability.
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. To be precise, at step $t\in\{1,\dots,T\}$, a DR-submodular utility function $f_t(\cdot)$ and a constraint vector $p_t$, i.i.d. generated from an unknown distribution with mean $p$, are revealed after committing to an action $x_t$ and we aim to maximize the overall utility while the expected cumulative resource consumption $\sum_{t=1}^T \langle p,x_t\rangle$ is below a fixed budget $B_T$. 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.