Online DR-Submodular Maximization with Stochastic Cumulative Constraints
  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.
