Stochastic $k$-Submodular Bandits with Full Bandit Feedback

Let $k$ be a positive integer for the number of types (i.e., types of stories) and $V=[n]$ be the ground set of elements (i.e., users in a social network). Let $(k+1)^{V}:=\{(X_{1},\ldots,X_{k})|X_{i}\subseteq V,i\in\{1,\ldots,k\},X_{i}\cap X_{j}=\emptyset,\forall i\neq j\}$. A function $f:(k+1)^{V}\rightarrow\mathbb{R}$ is called $k$-submodular if, for any $\boldsymbol{x}=(X_{1},\ldots,X_{k})$ and $\boldsymbol{y}=(Y_{1},\ldots,Y_{k})$ in $(k+1)^{V}$, we have

where $\boldsymbol{x}\sqcap\boldsymbol{y}:=(X_{1}\cap Y_{1},\ldots,X_{k}\cap Y_{k}),\boldsymbol{x}\sqcup\boldsymbol{y}:=(X_{1}\cup Y_{1}\setminus(\cup_{i\neq 1}X_{i}\cup Y_{i}),\ldots,X_{k}\cup Y_{k}\setminus(\cup_{i\neq k}X_{i}\cup Y_{i})).$ Note that setting $k=1$ in these definitions recovers submodular functions, set intersection, and set union, respectively. We further define a relation $\preceq$ on $(k+1)^{V}$ so that, for $\boldsymbol{x}=(X_{1},\ldots,X_{k})$ and $\boldsymbol{y}=(Y_{1},\ldots,Y_{k})$ in $(k+1)^{V},\boldsymbol{x}\preceq\boldsymbol{y}$ if $X_{i}\subseteq Y_{i}$ for every $i$ with $i\in[k]$. We also define the marginal gain of assigning type $i\in[k]$ to element $e$ given a current solution $\boldsymbol{x}$ (provided that $e$ has not been assigned any type in $\boldsymbol{x}$),

for $\boldsymbol{x}\in(k+1)^{V},e\notin\bigcup_{\ell\in[k]}X_{\ell}$, and $i\in[k]$.

We define the support of $\boldsymbol{x}\in(k+1)^{V}$ as $\operatorname{supp}(\boldsymbol{x})=\{e\in V\mid\boldsymbol{x}(e)\neq 0\}$ and define the support of type $i\in[k]$ as $\operatorname{supp}_{i}(\boldsymbol{x})=\{e\in V\mid\boldsymbol{x}(e)=i\}$. Further, a function $f:(k+1)^{V}\rightarrow\mathbb{R}$ is called monotone if $\Delta_{e,i}f(\boldsymbol{x})\geq 0$ for any $\boldsymbol{x}\in(k+1)^{V},e\notin\bigcup_{\ell\in[k]}X_{\ell}$, and $i\in[k]$.

In the CMAB framework, we consider sequential, combinatorial decision-making problems over a finite time horizon $T$. Let $\Omega$ denote the ground set of base arms and $n=|\Omega|$ denote the number of arms. Let $D\subseteq 2^{\Omega}$ denote the subset of feasible actions, for which we presume membership can be efficiently evaluated. We will use the terminologies subset and action interchangeably throughout the paper.

At each time step $t$, the learner selects a feasible action $A_{t}\in D$. After the subset $A_{t}$ is selected, the learner receives a reward $f_{t}(A_{t})$. We assume the reward $f_{t}$ is stochastic, bounded in $[0,1]$, and i.i.d. conditioned on the action $A_{t}$. Define the expected reward function as $f(A):=\mathbb{E}[f_{t}(A)]$. The goal of the learner is to maximize the cumulative reward $\sum_{t=1}^{T}f_{t}(A_{t})$. To measure the performance of the algorithm, one common metric is to compare the learner to an agent with access to a value oracle for $f$. However, if optimizing $f$ over $D$ is NP-hard, such a comparison would not be meaningful unless the horizon is exponentially large in the problem parameters. Alternatively, if there exists a known approximation algorithm $\mathcal{A}$ with an approximation ratio $\alpha\in(0,1]$ for optimizing $f$ over $D$, it is more natural to evaluate the performance of a CMAB algorithm against what $\mathcal{A}$ could achieve. In this scenario, we consider the expected cumulative $\alpha$-regret $\mathcal{R}_{\alpha,T}$, which quantifies the difference between $\alpha$ times the cumulative reward of the optimal subset’s expected value and the average received reward, (we write $\mathcal{R}_{T}$ when $\alpha$ is understood from context)

where OPT is the optimal solution, i.e., $\text{OPT}\in\operatorname*{arg\,max}_{A\in D}f(A)$ and the expectations are with respect to both the rewards and actions (if random).

We consider the sequential decision making problem under the stochastic CMAB framework where the expected reward function $f$ is $k$-submodular. Each arm consists of a tuple (we call it an item-type pair): $(e,i)\in V\times[k]$, and a super arm is defined as $\boldsymbol{x}\in(k+1)^{V}$, which is a combination of base arms. We consider full-bandit feedback, where after each time an action $A_{t}$ is selected, the learner can only observe $f_{t}(A_{t})$ as reward. We aim to transform various offline algorithms in $k$-submodular optimization literature to online algorithms, thus we consider $\alpha$ regret as our performance metric and $\alpha$ is defined to be the approximation ratio of the corresponding offline algorithm.

As we adopt the novel offline-to-online transformation framework proposed in (Nie et al., 2023a), in this section, we briefly introduce the framework. In (Nie et al., 2023a), they introduced a criterion for the robustness of an offline approximation algorithm. They showed that this property alone is sufficient to guarantee that the offline algorithm can be adapted to solve CMAB problems in the corresponding online setting with just bandit feedback and achieve sub-linear regret. More importantly, the CMAB adaptation will not rely on any special structure of the algorithm design, instead employing it as a black box. We restate the robustness definition in the following. This definition of robustness indicates that the algorithm $\mathcal{A}$ will maintain reasonably good performance when function evaluations have errors.

Note that when we have access to the exact oracle ($\varepsilon=0$), the definition will give us the same guarantee as the original offline algorithm; if the offline algorithm is exact, $\alpha=1$. Equipped with a robustness assurance, the authors introduced a stochastic CMAB algorithm named “Combinatorial Explore-Then-Commit” (C-ETC). See Algorithm 1 for the pseudocode. C-ETC interfaces with an offline $(\alpha,\delta,N)$-robust algorithm denoted as $\mathcal{A}$. In the exploration phase, when $\mathcal{A}$ requests information from the value oracle pertaining to action $A$, C-ETC adopts a strategy of executing action $A$ multiple times, specifically $m$ times, where $m$ is an optimization parameter. Subsequently, C-ETC computes the empirical mean, represented as $\bar{f}$, of the rewards associated with action $A$ and communicates this computed value back to the offline algorithm $\mathcal{A}$. In the exploitation phase, C-ETC continuously deploys the solution $S$ generated by the $\mathcal{A}$ algorithm. They showed the following theorem:

This approach allows for a CMAB procedure that does not require any specialized structural characteristics from $\mathcal{A}$. It necessitates no intricate construction beyond the execution of $\mathcal{A}$, provided the criteria of robustness (Definition 2.2) are met.

In the following sections, we transform various offline algorithms for $k$-submodular maximization problems under different constraints to online bandit setting by analyzing the robustness of the offline algorithms. In analyzing the robustness of offline algorithms, we assume the offline algorithm is evaluated with a surrogate function $\hat{f}$ with $|f(S)-\hat{f}(S)|\leq\epsilon$ for all $S\in D$, instead of the exact function $f$. We will highlight some parts of the proof for non-monotone unconstrained problem, and defer all missing proofs to the appendix.

We first remark the following key fact for (monotone or non-monotone) $k$-submodular maximization without constraints (see Iwata et al. (2013) for the proof):

This says that there is an optimal solution with all elements included (a combinatorial search is needed to determine their types). Proposition 3.1 remains valid for non-monotone functions due to the special property of $k$-submodular functions (pairwise monotonicity).

Armed with this property, they proposed a randomized offline algorithm for maximizing a non-monotone $k$-submodular maximization without constraint. The algorithm is presented in Algorithm 2 in the appendix. This algorithm iterates through all $e\in V$ (in an arbitrary but fixed order) and selects the type $i\in[k]$ randomly according to some carefully designed probabilities $p_{i}$ for each $e\in V$. The authors showed that this algorithm achieves a $1/2$-approximation ratio for non-monotone $k$-submodular maximization without constraints.

We show that Algorithm 2 is $(\frac{1}{2},\delta,N)$ robust for a certain $\delta$ and $N$. Due to that robustness we can use the framework proposed in Nie et al. (2023a), to transform Algorithm 2 into an online algorithm under bandit feedback achieving sublinear $1/2$-regret.

Let $\boldsymbol{o}$ be an optimal solution with $\operatorname{supp}(\boldsymbol{o})=V$ (by Proposition 3.1 such a solution exists). Let $\boldsymbol{s}$ be the output of the algorithm with $|\operatorname{supp}(\boldsymbol{s})|=n$ using surrogate function $\hat{f}$. We consider the $j$-th iteration of the algorithm, and let $e^{(j)}$ be the element of $V$ considered in the $j$-th iteration, $p_{i}^{(j)}$ be the probability that $i$-th type is chosen in the $j$-th iteration, and $\boldsymbol{s}^{(j)}$ be the solution after the $i$-th iteration, where $\boldsymbol{s}^{(0)}=\mathbf{0}$. Also for $0\leq j\leq n$, let $\boldsymbol{o}^{(j)}$ be the element in $(k+1)^{V}$ obtained from $\boldsymbol{o}$ by replacing the coordinates on $\operatorname{supp}(\boldsymbol{s}^{(j)})$ with those of $\boldsymbol{s}^{(j)}$, and for $1\leq j\leq n$ let $\boldsymbol{t}^{(j-1)}$ be the element in $(k+1)^{V}$ obtained from $\boldsymbol{o}^{(j)}$ by changing $\boldsymbol{o}^{(j)}(e^{(j)})$ with 0.

For $i\in[k]$, let $y_{i}^{(j)}=\Delta_{e^{(j)},i}f(\boldsymbol{s}^{(j-1)})$, $\hat{y}_{i}^{(j)}=\Delta_{e^{(j)},i}\hat{f}(\boldsymbol{s}^{(j-1)})$ and let $a_{i}^{(j)}=\Delta_{e^{(j)},i}f(\boldsymbol{t}^{(j-1)})$, $\hat{a}_{i}^{(j)}=\Delta_{e^{(j)},i}\hat{f}(\boldsymbol{t}^{(j-1)})$. Due to pairwise monotonicity, we have $y_{i}^{(j)}+y_{i^{\prime}}^{(j)}\geq 0$ and $a_{i}^{(j)}+a_{i^{\prime}}^{(j)}\geq 0$ for all $i,i^{\prime}\in[k]$ with $i\neq i^{\prime}$, and thus, while the surrogate function $\hat{f}$ does not necessarily have pairwise monotonicity, we have

for all $i,i^{\prime}\in[k]$ with $i\neq i^{\prime}$ since both inequalities involve a sum of four function values of $\hat{f}$ which can be off by at most $\epsilon$ with respect to $f$. Also from $\boldsymbol{s}^{(j)}\preceq\boldsymbol{t}^{(j)}$ which holds by construction, orthant submodularity implies $y_{i}^{(j)}\geq a_{i}^{(j)}$ for all $i\in[k]$ and thus,

for all $i\in[k]$. W.l.o.g., we assume $f(\boldsymbol{0})=0$.

Before showing the main result, we first show the following lemma, which is a generalization of Lemma 2.2 in Iwata et al. (2015) in the presence of noise.

We defer the proof of this lemma to Section A.1. Then, we show the following proposition:

To show Proposition 3.3, by Definition 2.2, we aim to show that the output $\boldsymbol{s}$ of Algorithm 2 satisfies $\mathbb{E}[f(\boldsymbol{s})]\geq\frac{1}{2}f(\boldsymbol{o})-20n\varepsilon$ when the function evaluation is based on surrogate function $\hat{f}$. By Lemma 3.2 it suffices to prove (4) for every $j\in[n]$ for $c=1$ and $d=14$. For simplicity of the description, we shall omit the superscript $(j)$ if it is clear from the context. Due to limited space, here we only consider the case when $i^{+}\geq 3$ since this case needs more effort technically. The proof for other cases is in supplementary material Section A.2.

Once we have analysed the robustness of Algorithm 2 and identified the number of function evaluations of Algorithm 2 is exactly $nk$, we can employ the framework proposed in Nie et al. (2023a) and obtain the following result: