The stochastic multi-armed bandits (MAB) problem involves selecting an arm in each round t and observing a reward that follows an unknown distribution. The objective is to maximize the accumulated reward within a finite time horizon T . Solving the classical MAB problem requires striking a balance between exploration and exploitation. Should the agent try arms that have been explored less frequently to gather more information (exploration), or should it stick to arms that have yielded higher rewards based on previous observations (exploitation)? An extension of the MAB problem is the combinatorial MAB problem, where, instead of choosing a single arm per round, the agent selects a set of multiple arms and receives a joint reward for that set. When the agent only receives information about the reward associated with the selected set of arms, it is known as full-bandit feedback or simply bandit feedback. On the other hand, if the agent obtains additional information about the contribution of each arm to the overall reward, it is referred to as semi-bandit feedback. The full-bandit feedback setting poses a more significant challenge as the decision-maker has significantly less information than the semi-bandit feedback scenario (Fourati et al. 2023a). This paper focuses on the first scenario for combinatorial MAB, i.e., the bandit feedback setting.
In recent years, there has been growing interest in studying combinatorial multi-armed bandit problems with submodularfoot_0 reward functions (Niazadeh et al. 2020;Nie et al. 2022;Fourati et al. 2023a). The submodularity assumption finds motivation in various real-world scenarios. For instance, opening additional supermarkets in a specific location would result in diminishing returns due to market saturation. As a result, submodular functions are commonly used as objective functions in game theory, economics, and optimization (Fourati et al. 2023a). Submodularity arises in important contexts within combinatorial optimization, such as graph cuts (Goemans and Williamson 1995;Iwata, Fleischer, and Fujishige 2001), rank functions of matroids (Edmonds 2003), and set covering problems (Feige 1998). Some key problems where combinatorial multi-armed bandit problems with submodular reward functions include proposing items with redundant information (Qin and Zhu 2013;Takemori et al. 2020), optimizing client participation in federated learning (Balakrishnan et al. 2022;Fourati et al. 2023b), and social influence maximization without knowledge of the network or diffusion model (Wen et al. 2017;Li et al. 2020;Perrault et al. 2020;Agarwal et al. 2022;Nie et al. 2022).
Similar to previous works (Streeter and Golovin 2008;Golovin, Krause, and Streeter 2014;Niazadeh et al. 2021;Agarwal et al. 2021Agarwal et al. , 2022;;Nie et al. 2022), we assume that the reward function is non-decreasing (monotone) in expectation. Without further constraints, the optimal set will contain all the arms in this setup. Thus, we limit the cardinality of the set to k. Recently, (Nie et al. 2022(Nie et al. , 2023) ) studied this problem and proposed an explore-then-commit greedy (ETCG) algorithm for this problem with full-bandit feedback and showed a (1 -1/e)-regret bound of O ˜(n
where n is the number of arms. The algorithm follows a greedy explore-then-commit approach that greedily adds base arms to a super arm (a subset of base arms) until the cardinality constraint is satisfied. It then exploits this super arm for the remaining time. To determine which base arm to add to the super arm, the remaining arms are sampled m times each (where m is a hyper-parameter), and the arm with the highest average reward is chosen. However, in practical scenarios with many arms, exploring all remaining arms in each iteration may require a significant time and thus is unsuitable for smaller T . Therefore, we propose a modified approach where a smaller subset of arms is randomly selected for exploration in each iterative round, and the arm with the highest reward is chosen.
It is worth noting that a similar random selection-based algorithm has been considered in (Mirzasoleiman et al. 2015) for the offline setup, providing a (1-1/e-ϵ)-approximation guarantee, where ϵ determines the reduction in the number of arms selected in each iteration. However, although beneficial for exploration, this sub-selection of arms in each iteration leads to suboptimal approximation guarantees. In this paper, we ask the question: "Can exploring a subset of arms in each iteration achieve a benefit regarding the (1 -1/e)regret bound compared to selecting all remaining arms?"
We answer this question in a positive. By carefully selecting the parameter ϵ, we achieve a (1 -1/e)-regret bound of O ˜(n
). This improvement in regret bound surpasses that of (Nie et al. 2022(Nie et al. , 2023) ) by orders of magnitude in terms of k. This improvement is particularly significant for larger values of k. Our proposed approach reduces exploration while enhancing expected cumulative (1-1/e)-regret performance.
We present the main contributions of this paper as follows:
• We introduce stochastic-greedy bandit (SGB), a novel technique in the explore-then-commit greedy strategy with bandit feedback, wherein an optimized proportion of remaining arms are randomly sampled in each greedy iteration. More precisely, rather than sampling (n -i + 1) arms in greedy iteration i, random (n -i + 1) min{1, log(1/ϵ)/k} arms are chosen for an appropriately selected ϵ = O(n
), which reduces the amount of exploration.
• We provide theoretical guarantees for SGB by proving that it achieves an expected cumulative (1 -1/e)-regret of at most O ˜(n
3 ) for monotone stochastic submodular rewards. This represents an improvement of k 1 3 compared to the previous state-of-the-art method (Nie et al. 2023).
• We conduct empirical experiments to evaluate the performance of our proposed SGB algorithm compared to the previous state-of-the-art algorithms specialized in monotone stochastic submodular rewards (Nie et al. 2022(Nie et al. , 2023)). We specifically focus on the online social influence maximization problem and demonstrate the efficiency of SGB in achieving superior results in terms of cumulative regret. In particular, the results show that the proposed algorithm outperforms the baselines, with the performance gap increasing as k increases.
This section discusses the works closely related to the problem we are investigating. Multi-armed bandits have been considered in two different settings: adversarial setting, where an adversary produce a reward succession that may be affected by the agent's prior decisions (Auer et al. 2002), and a stochastic setting, where the reward of each action is randomly drawn from a specific distribution, as described in (Auer, Cesa-Bianchi, and Fischer 2002). In this work, we focus on stochastic reward functions. Standard multi-armed bandits find adversarial settings more challenging, and the outcome can be immediately used as one workable method for the stochastic scenario (Lattimore and Szepesvári 2020). However, this is different for submodular bandits. While adversarial environment in adversarial bandits selects a series of submodular functions {f 1 , • • • , f T } (Streeter and Golovin 2008;Golovin, Krause, and Streeter 2014;Roughgarden and Wang 2018;Niazadeh et al. 2020), in the submodular stochastic setting the realizations of the stochastic function in the problem we define need not be submodular, it only needs to be submodular in expectation (Fourati et al. 2023a), meaning the stochastic setting is not a particular case of the adversarial setting. Submodular maximization has been proven to be NPhard. Even achieving an approximation ratio of α ∈ (1 -1/e, 1] under a cardinality constraint with access to a monotone submodular value oracle is also NP-hard (Nemhauser, Wolsey, and Fisher 1978;Feige 1998;Feige, Mirrokni, and Vondrák 2011). However, (Nemhauser, Wolsey, and Fisher 1978) proposed a simple greedy (1 -1/e)-approximation algorithm for monotone submodular maximization under a cardinality constraint. Therefore, the best approximation ratio for monotone submodular objectives with a polynomial time algorithm is 1 -1/e. Thus, we study (1 -1/e)-regret combinatorial MAB algorithms in this paper.
Table 1 enumerates related combinatorial works with monotone submodular reward function under bandit feedback for both adversarial and stochastic settings. The table summarizes that the proposed approach achieves the state-of-the-art (1 -1/e)-regret result. Even though we consider stochastic submodular rewards, full-bandit feedback has been studied for non-submodular rewards, including linear reward functions (Dani, Hayes, and Kakade 2008;Rejwan and Mansour 2020) and Lipschitz reward functions (Agarwal et al. 2021(Agarwal et al. , 2022)). In these works, the optimal action (best set of k arms) is to use the k individually best arms; that property does not hold for submodular rewards. Further, non-monotone submodular functions with bandit feedback without cardinality constraint have been studied in (Fourati et al. 2023a), where 1 2 -regret is derived. However, this algorithm cannot be directly applied to our setup since it lacks a cardinality constraint.
Recently, (Nie et al. 2023) provided a framework that adapts offline algorithms for combinatorial optimization with a robustness guarantee to online algorithms with provable regret guarantees. We could use this framework for the offline approximation algorithm described in (Mirzasoleiman et al. 2015) for the problem. At the same time, we note that such an approach will result in (1 -1/e -ϵ)-
Stochastic (1 -1/e)-Regret (Streeter and Golovin 2008) O ˜( n
Table 1: Table of selected approximation because the offline algorithm has (1-1/e-ϵ) guarantee. Thus, exploring only a subset of arms in each iteration and achieving a (1 -1/e)-regret is non-trivial and requires careful analysis, which is done in this paper.
In this section, we present the problem formally. We denote Ω, the ground set of base arms which includes n base arms. We consider decision-making problems with a fixed time horizon T , where the agent, at each time step t, chooses an action S t ⊆ Ω, with maximum cardinality constraint k. Let S = {S|S ⊆ Ω and |S| ≤ k} represent the set of all permitted subsets at any time step.
After deciding the action S t , the agent acquires reward f t (S t ). We assume the reward f t is stochastic, bounded in [0, 1], i.i.d. conditioned on a given action, submodular in expectation 2 , and monotonically non-decreasing in expectation 3 . The goal of the agent is to maximize the cumulative reward ∑︁ T t=1 f t (S t ). Define the expected reward function as f (S) = E[f t (S)], hence S ⋆ = arg max S:|S|≤k f (S) denote the optimal solution in expectation. One common metric to measure the algorithm's performance is to compare the learner to an agent that has and always chooses the optimal set in expectation S ⋆ .
The best approximation ratio for monotone-constrained submodular objectives with a polynomial time algorithm is 1 -1/e (Nemhauser, Wolsey, and Fisher 1978). Therefore, we compare the learner's cumulative reward to (1 -1/e)T f (S ⋆ ), and we denote the difference as the (1 -1/e)regret, which is defined as follows
(2)
2 A stochastic set function f : 2 Ω → R defined on a finite set Ω is considered submodular in expectation if for all A ⊆ B ⊂ Ω, and x ∈ Ω\B, we have,
Algorithm 1: SGB
, β} end for for remaining time do Play S (k) end for Note that the (1 -1/e)-regret R(T ) is random and depends on the subsets chosen. In this work, we focus on minimizing the expected cumulative (1 -1/e)-regret
where the expectation is over both the environment and the sequence of actions.
This section presents our proposed combinatorial stochasticgreedy bandit (SGB) algorithm that applies our optimized stochastic-explore-then-commit approach. We provide its pseudo-code in Algorithm 1.
The algorithm follows the explore-then-commit structure where base arms are added to a super arm over time greedily until the cardinality constraint is satisfied and then exploits that super arm. However, in contrast to previous explorethen-commit approaches in (Nie et al. 2022(Nie et al. , 2023)), which at every exploration phase has a search space of O(n), to minimize its expected cumulative regret, SGB reduces its search space to O( n k min{k, log( 1 ϵ )}) arms. The aim of reducing the searched arms in each iteration is to reduce the time spent in the exploration.
Let S (i) represent the super arm when i < k base arms are selected. Our algorithm starts with the empty set, S (0) = ∅.
To add an arm to the set S (i-1) , ETCG explores the full subset Ω \ S (i-1) . Instead, our procedure explores a smaller subset, i.e., a random subset
(4) For β < 1, during each exploration phase i, while ETCG explores (n -i + 1) arms, SGB only explores (n -i + 1)β arms. Therefore, SGB requires fewer oracle queries per exploration phase than ETCG. For β ≥ 1, during each exploration phase i, SGB explores (n -i + 1) arms, leading it to become a deterministic greedy algorithm and recover the same results as ETCG. We note that β < 1 happens when ϵ > e -k . Therefore, the lower bound on ϵ exponentially decreases as a function of k, ensuring this is true for most instances. To minimize the cumulative regret, ϵ is optimized as a function of n, k, and T .
Let T i denote the time step when phase i finishes, for i ∈ {1, • • • , k}. We also denote T 0 = 0 and T k+1 = T for notational consistency. Let f ¯t(S) denote the empirical mean reward of set S up to and including time t. Let
} denote the set of actions considered during phase i. Each action comprises the super arm S (i-1) decided during the last phase and an additional base arm. Each action S ∈ S i is played the same number of times; let m denote that number. The choice of m will be optimized later to minimize regret. At the end of phase i ∈ {1, . . . , k}, SGB selects the action that has the largest empirical mean,
and include it in the super arm S (i) = S (i-1) ∪ {a i }. During the final phase, the algorithm exploits S (k) ; it plays the same action
Similar to previous state-of-the-art approaches, SGB has low storage complexity. During exploitation, for t ∈ {T k + 1, • • • , T k+1 }, only the indices of the k base arms are stored, and no additional computation is required. During exploration, for t ∈ {1, • • • , T k }, for every phase i, SGB needs to store the highest empirical mean and its associated base arm a ∈ A i . Therefore, SGB has O(k) storage complexity. In comparison, the algorithm suggested by (Streeter and Golovin 2008) for the full-bandit adversarial environment has a storage complexity of O(nk).
We note that the reduction of exploration time through random subset sampling from the remaining arms comes at the expense of reduced offline approximation guarantee to (1 -1/e -ϵ) in (Mirzasoleiman et al. 2015). Thus, it is apriori unclear if such an approach can maintain the online (1 -1/e)-regret guarantees with the reduced exploration, which is studied in the next section.
This section analyses the regret for Algorithm 1. We begin by stating the main theorem, which bounds the expected cumulative (1 -1/e)-regret of SGB.
Theorem 1. For the decision-making problem defined in Section 2 with T ≥ n(k + 1) √︁ log(T ), the expected cumulative (1 -1/e)-regret of SGB is at most O(n
). The rest of the section provides the proof of this result. Since for each phase i, we select each action S (i-1) ∪ {a} ∈ S i exactly m times, we consider the equal-sized confidence radii rad = √︁ log(T )/m for all the actions S (i-1) ∪ {a} ∈ S i at the end of phase i. Denote the event that the empirical means of actions played in phase i are concentrated around their statistical means as
Then we define the clean event E to be the event that the empirical means of all actions selected up to and including phase k is within rad of their corresponding statistical means:
Although the E i 's are not independent, by conditioning on the sequence of played subsets {︁ S (0) , S (1) , . . . , S (k) }︁ and using the Hoeffding bound (Hoeffding 1994), we show in the Appendix (see (Fourati et al. 2023c)) that E happens with high probability. We use the concentration of empirical means, Equation (6), and properties of submodularity to show the following result.
Lemma 1. Under the clean event E, for all i ∈ {1, 2, • • • , k}, for all positive ϵ,
Proof. Recall that a i , defined in (5), is the index of the arm that with S (i-1) forms the action with the highest empirical mean at the end of phase i, and S (i) = S (i-1) ∪ {a i }. Let a * i denote the index of the arm that with S (i-1) forms the action with the highest expected value. For each a ∈ A i , the event that the empirical mean f ¯(S (i-1) ∪ {a}) is concentrated within a radius of size rad around the expected value. We lower bound the expected reward f (S (i) ) for the empirically best action in phase i, S (i) = {a i } ∪ S (i-1) . To do so, we apply (6) to two specific arms, the empirically best a i out of A i and the statistically best a ⋆ i out of A i .
( using ( 6))
Furthermore, using Lemma 2 in (Mirzasoleiman et al. 2015), with
).
(7) Combining the above results, we conclude that
This lemma identifies a lower bound of the expected marginal gain f (︁
) )︁ of the empirically best action S (i) at the end of phase i. As a corollary of Lemma 1, using properties of submodular set functions, we can lower bound the expected value of SGB's chosen set S (k) of size k, which is used for exploitation; Corollary 1. Under the clean event E, for all positive ϵ,
Proof. Applying Lemma 1 result recursively for i = k, until we get to
Simplifying the geometric summation,
Continuing with (8),
Therefore, for 0 ≤ ϵ ≤ 1, using e ϵ ≤ 1 + eϵ , we have
We use the above Corollary 1 to bound the expected cumulative regret of our proposed algorithm. We split the expected (1 -1/e)-regret (3) conditioned on the clean event E into two parts, one for the exploration and one for the exploitation,
Note that during phase i, each of the s i actions in S i is selected exactly m times, thus T i -T i-1 = ms i . For each action S t choosed during phase i, that is for t
, by monotonicity of the expected reward function f we have f (S (i-1) ) ≤ f (S t ). Thus we can upper bound the expected regret E[R(T )|E] incurred during the first k phases (first term of ( 10)) as
The last inequality follows because the rewards are in [0, 1].
We can upper bound the expected regret E[R(T )|E] incurred during the exploitation phase (phase k + 1; second term of (10)) by applying Corollary 1 as follows
Combining the upper bounds ( 11) and ( 12), we get
We have
m . Therefore, we have
First, trivially min{k, log
Setting the derivative (with respect to ϵ) of the bound to 0, 0 = -mn
The second derivative (with respect to ϵ), mnϵ -2 , is positive so the stationary point is a minimizer. Plugging ϵ = mn T into the regret upper bound,
The above inequality is valid for all m strictly greater than zero. Hence, to find a tighter bound, we find m ⋆ that minimizes the right side. Thus we get
For
Based on m ⋆ , we define the optimal ϵ ⋆ as follows
Under the bad event, i.e., the complement E ¯of the good event E, given that the rewards are bounded in [0, 1], it can be easily seen that E[R(T ) | E ¯] ≤ T . Moreover, by using the Hoeffding inequality (Hoeffding 1994), for T ≥ nk, we have P(E ¯) ≤ 2 T , see Appendix (available at (Fourati et al. 2023c)). Therefore, we obtain
). Remark 1. The framework of Nie et al. (2023) that adapts offline algorithms for combinatorial optimization problems with robustness guarantees to online settings via the explorethen-commit approach can be applied to the offline algorithm in (Mirzasoleiman et al. 2015). However, as this offline algorithm has (1 -1/e -ϵ)-approximation guarantee, such an approach will give a weaker (1 -1/e -ϵ)-regret guarantee rather than (1 -1/e)-regret guarantee studied in this paper.
Remark 2. For unknown time horizon T , the geometric doubling trick can extend our result to an anytime algorithm. To initialize the algorithm, we choose T 0 to be large enough, then we choose a geometric succession T i = T 0 2 i for i ∈ {1, 2, • • • }, and run our algorithm during the time interval T i+1 -T i with a complete restart. From Theorem 4 in (Besson and Kaufmann 2018), we can prove that the regret bound preserves the T 2/3 dependency with changes only in the constant factor. Remark 3. For the scenario we study in this paper of combinatorial multi-armed bandit with submodular rewards in expectation and under full-bandit feedback, it is still unknown if O ˜(T 1/2 ) expected cumulative (1 -1/e)-regret is possible (ignoring n and k dependence), and only O ˜(T 2/3 ) bounds have been shown in the literature; see Table 1.
Social influence maximization is a combinatorial problem, which consists of selecting a subset of nodes in a graph that can influence the remaining nodes. For instance, when marketing a newly developed product, one strategy is to identify a group of highly influential individuals and rely on their recommendations to reach a broader audience. Influence maximization can be formulated as a monotone submodular maximization problem, where adding more nodes to the selected set yields diminishing returns without negatively affecting other nodes. Typically, there is a fixed constraint on the cardinality of the selected set. While some works have addressed influence maximization as a multiarmed bandit problem with additional feedback (Lei et al. 2015;Wen et al. 2017;Vaswani et al. 2017;Li et al. 2020;Perrault et al. 2020), this feedback is often unavailable in most social networks, except for a few public accounts. Recently, (Nie et al. 2022) proposed the ETCG algorithm for influence maximization under full-bandit feedback. Their algorithm demonstrated superior performance through empirical evaluations compared to other full-bandit algorithms. In this work, we compare our SGB method, for different ϵ values, including the optimized value ϵ ⋆ = ( nk 2 4T log(T ) )
1 3 , with ETCG (Nie et al. 2022(Nie et al. , 2023)).
For the experiments, instead of (1 -1/e) regret in Eq.
(2), which requires knowing S ⋆ , we compare the cumulative rewards achieved by SGB for different ϵ, including ϵ ⋆ , and ETCG against T f (S grd ), where S grd is the solution returned by the offline (1 -1/e)-approximation algorithm suggested by (Nemhauser, Wolsey, and Fisher 1978). Since f (S grd ) ≥ (1 -1/e)f (S ⋆ ), thus T f (S grd ) is a more challenging reference value than (1 -1/e)T f (S ⋆ ).
We experimented using a portion of the Facebook network (Leskovec and Mcauley 2012). We used the community detection method proposed by (Blondel et al. 2008) to detect a community with 534 nodes and 8158 edges, enabling multiple experiments for various horizons. The dif- fusion process is simulated using the independent cascade model (Kempe, Kleinberg, and Tardos 2003), wherein in each discrete step, an active node (that was inactive at the previous time step) independently tries to infect each of its inactive neighbors. We used 0.1 uniform infection probabilities for each edge. For every time horizon T ∈ {2 × 10 4 , 3 × 10 4 , 4 × 10 4 , 5 × 10 4 }, we tested each method ten times.
Figures (1a), (1b), and (1c) show average cumulative regret curves for SGB with different values of the parameter ϵ, including the optimal value ϵ ⋆ = ( nk 2 4T log(T ) ) 1 3 , for various time horizon values T , with a cardinality constraint k set to 8, 24, and 32, respectively. The shaded areas depict the standard deviation. The figure axes are linearly scaled, so a linear cumulative regret curve corresponds to a linear ˜︁ O(T ) cumulative regret. When k = 8, SGB with ϵ ⋆ demonstrates nearly the lowest average cumulative regret across different time horizons T . However, with non-optimal values of ϵ (0.2 and 0.5), the cumulative regret of SGB is higher than that of ETCG. For higher values of k, such as 24 and 32, with ϵ ⋆ as shown in Figures (1b) 1f), SGB with different ϵ values ends exploration 30 times faster than ETCG to a solution within a 0.01 neighborhood of 0.37. Furthermore, using ϵ ⋆ yields the best result compared to other values. Therefore, as predicted by the theory, SGB using ϵ ⋆ has lower expected cumulative regret than ETCG. Additionally, as observed in the experiments and predicted by the theory, our method becomes more effective for larger values of k.
This paper introduces SGB, a novel method in the online greedy strategy, which incorporates subset random sampling from the remaining arms in each greedy iteration. Theoretical analysis establishes that SGB achieves an expected cumulative (1-1/e)-regret of at most O ˜(n
) for monotone stochastic submodular rewards, outperforming the previous state-of-the-art method by a factor of k 1/3 (Nie et al. 2023). Empirical experiments on online influence maxi-mization shows SGB's superior performance, highlighting its effectiveness and potential for real-world applications.
A set function f :
Ω → R defined on a finite set Ω is considered submodular if it exhibits the property of diminishing returns: for any A ⊆ B ⊂ Ω and x ∈ Ω\B, it holds thatf (A ∪ x) -f (A) ≥ f (B ∪ x) -f (B).