The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
Year: 2021

Abstract:
Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example [30] has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problemdependent regret lower bound of order ⌦(log T/ 2) to quantify the hardness of TS to solve CMAB problems with greedy oracle, where T is the time horizon and is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.

heading: 1 Introduction
text: Stochastic multi-armed bandit (MAB) problem [20, 5, 3] is a classical online learning framework. It has been extensively studied in the literature and has a wide range of applications [13, 12, 20]. The problem is modeled by a T -round game between the learning agent and the environment. The environment contains an arm set and each arm is associated with a reward distribution. At each round t, the agent first selects an arm, while the environment generates a random reward for each arm from its reward distribution. The agent then obtains the reward of the selected arm. The objective of the agent is to accumulate as many expected rewards over T rounds, or equivalent to minimizing the cumulative expected regret, which is defined as the cumulative difference between the expected reward of the optimal arm and the selected arms over T rounds. To achieve this long-horizon goal, the learning agent has to face the dilemma of exploration and exploitation in each round. The former aims to try arms that have not been observed enough times to get a potentially higher reward, the latter focuses on the arm with the best observed performance so far to maintain a high profit. How to balance the tradeoff between exploration and exploitation is the main focus of the MAB algorithms.
One of the most popular bandit algorithms is the upper confidence bound (UCB) algorithm [5]. The algorithm aims to construct confidence sets for unknown expected rewards and selects arms according to their highest upper confidence bounds. The UCB-type algorithms have been widely studied and provided theoretical guarantees with regret upper bound of order O(log T/ ), where is the
⇤Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
minimum gap between the expected reward of the optimal arm and any suboptimal arms. Thompson sampling (TS) [3, 26] is another popular method to solve MAB problems. It is a randomized algorithm based on the Bayesian idea, which maintains an iteratively updated posterior distribution for each arm and chooses arms according to their probabilities of being the best one. The TS algorithm was introduced in the 1930s [28], but its theoretical analysis is open until recent years [15, 2]. It was proven that the regret upper bound of the TS algorithm is of the same order of O(log T/ ) in MAB problems [3]. Benefited from the advantages of easier implementation and better empirical performance compared to UCB, the TS-type algorithms attract more attentions in recent years.
Despite its importance, the MAB framework may fail to model many real applications since the agent’s action is usually not a single arm but a combination of several arms. This motivates the study on the combinatorial MAB (CMAB) problem [11, 9, 17, 31, 7, 29, 30, 24]. In the CMAB framework, the agent selects a combination of base arms as an action to play in each round. All outcomes of these selected arms are then revealed to the agent, which is called semi-bandit feedback and is widely studied in the literature [7, 29, 32, 30, 14, 24]. Such CMAB framework can cover many real application scenarios including probabilistic maximum coverage (PMC) [6], online influence maximization (OIM) [29], multiple-play MAB (MP-MAB) [17] and minimum spanning tree (MST).
TS-type algorithms have recently attracted a lot of interest in CMAB problems [17, 30, 14, 24]. All of these works need an exact oracle to provide the optimal solution with sampled parameters as input in each round. However, such oracles are usually not feasible since many offline combinatorial optimization problems, such as the offline problem of PMC and OIM [16], are NP-hard and only approximation oracles are available. With an example [30] illustrating the non-convergent regret of TS with an artificial approximation oracle designed for a specific problem instance, whether TS can work well in CMAB problems with common approximation oracles is still an open problem.
One of the most common oracles for offline combinatorial optimization problems with a theoretical guarantee is the greedy algorithm. It sequentially finds the current optimal arm, or the optimal collection of multiple arms according to the structural correlations, to maximize the current total expected reward. When the termination condition is met, it will return the set of all arms found in previous steps as the solution. The termination condition is usually formulated by a constraint on the number of steps. For example, in the PMC, OIM, and MP-MAB problems, such a process is limited to continue K steps. The greedy algorithm can provide approximate solutions for offline problems of PMC [8] and OIM [16], and exact optimal solutions for offline problems of MP-MAB [17] and MST [18]. In general, as long as the expected reward in a problem satisfies the monotonicity and submodularity on the action set, the greedy algorithm serves as an offline oracle to provide an approximate solution [23].
In this paper, we first formulate the CMAB problems with greedy oracle, which is general enough and covers PMC, MP-MAB, and many other problems. In this framework, the objective of the learning agent is to minimize the cumulative greedy regret, defined as the cumulative difference between the expected reward of the selected action and that of the greedy’s solution in the real environment. Focusing on a specific PMC problem instance, we derive the hardness analysis of the TS algorithm with the greedy oracle to solve CMAB problems. Due to the mismatch between the estimation gaps that need to be eliminated by exploration and the actual regret the algorithm needs to pay for each such exploration, the TS algorithm with greedy oracle in this CMAB problem cannot achieve as good theoretical performance as previous MAB algorithms. A problem-dependent regret lower bound of order ⌦(log T/ 2) is provided to illustrate such hardness, where T is the time horizon and is some reward gap. By carefully exploiting the property of the greedy oracle, we also provide an almost matching problem-dependent regret upper bound, which is tight on that PMC problem instance and also recovers the main order of TS when solving MAB problems [3]. These results are the first theoretical results of TS with approximation oracle to solve CMAB problems, which show that the linear regret example in [30] does not hold for every approximation oracle.

heading: 2 Related Work
text: CMAB problems have been widely studied in the literature [11, 6, 7, 29, 30, 24, 32, 21, 14]. Here we mainly focus on the most relevant works. Gai et al. [11] first study the CMAB problem with linear reward, where the reward of an action is linear in the reward of base arms included in it. They introduce a UCB-type algorithm to solve such problems and allow approximation algorithms to
serve as offline oracles. Later, Chen et al. [6, 7, 29] generalize this framework by considering a larger class of rewards and the case with probabilistically triggered arms (CMAB-T). This framework only assumes the expected reward satisfies the monotonicity and Lipschitz condition on the mean vector of base arms. The combinatorial UCB (CUCB) algorithm is proposed to solve such general CMAB problems, which works with any offline oracle with approximation guarantees. When only approximation oracles are available, the goal of the algorithm is relaxed to minimize the cumulative approximation regret, which is defined as the difference between the expected reward of the selected action and that of the scaled optimal solution. The CUCB algorithm achieves the regret upper bound of order O(log T/ min) [29], where min is the minimum reward gap from the scaled optimal solution over all suboptimal actions.
Compared with UCB-type algorithms which need to compute upper confidence bounds for unknown means of base arms [6, 7, 29], TS-type algorithms do not require the reward function to satisfy the monotonicity on the mean vector of base arms. Benefited from this and other advantages of easier implementation and better practical performances, TS-type algorithms have recently attracted a lot of interest in CMAB problems. Komiyama et al. [17] consider using the TS algorithm to solve the MP-MAB problem, where the agent needs to select K from m arms to maximize the sum of rewards over these selected K arms. They provide an optimal regret upper bound of order O(log T/ K,K+1) for the TS algorithm to solve this problem, where K,K+1 is the reward gap between the K-th and (K + 1)-th optimal arm. Later, Wang and Chen [30] consider using TS to solve more general CMAB problems where only the Lipschitz condition is assumed to be satisfied. Their regret upper bound of order O(log T/ min) matches the main order of the CUCB [29] in the same setting. The coefficient of this upper bound was recently improved by Perrault et al. [24], who study the same CMAB setting. Huyuk et al. [14] extend the analysis of [30] and consider using the TS algorithm to solve the problem of CMAB-T. However, the current regret upper bound is O(1/p⇤) worse than CUCB [29], where p⇤ is the minimum triggering probability.
All of the above TS-based works need an exact oracle to provide the optimal solution with sampled parameters in each round. However, the exact oracles are usually not feasible as many combinatorial optimization problems, such as the offline problem of OIM and PMC, are NP-hard [16]. Wang and Chen [30] have constructed a problem instance and designed an approximation offline oracle for this problem instance. The analysis has shown that the TS algorithm suffers the linear regret of order O(T ) when working with such an approximation oracle. However, this oracle is uncommon and artificial, thus cannot represent the performance of TS when working with common approximation oracles. It is still a significant open problem that whether TS can perform well with approximation oracles.
The greedy algorithm is one of the most important methods with approximation guarantees to solve combinatorial optimization problems. When the mean vector is known beforehand, we call the problem of finding the action with the best expected reward as offline problem. Using the greedy algorithm to solve offline combinatorial problems has been studied for decades, including the problem of shortest spanning subtree [18], shortest connection networks [25], set coverage [8], influence maximization [16], and general submodular optimization [23]. There is also a line of studies considering using greedy to solve online problems [4, 19, 10, 27, 22], some of them require the exact reward function forms as prior knowledge. Among these works the most related to ours is [22], both aiming to solve a general class of online problems. Lin et al. [22] consider using the online greedy strategy to make decisions based on UCB-type estimators. The algorithm sequentially selects a unit to maximize the current expected reward until no feasible unit can be selected in each round. In their setting, a unit conditioned on a set of previously selected units is regarded as an arm and the marginal reward of selecting this unit is the expected reward of this arm. Since the number of combinations of units is usually exponentially large, there is an exponential number of arms to explore, making the algorithm pay exponential memory cost in practical applications. Based on this framework, the algorithm needs to observe the marginal reward after the decision of each step to update the estimate on the arm. However, such observation may be not available as many combinatorial problems treat the action composed of several units as a whole and select them together. Compared to this work, our framework only needs polynomial memory cost and does not require the observation of the marginal reward.
In this paper, we study the problem of CMAB with the common (approximation) greedy oracle and hope to answer the question of whether the TS algorithm can work well in this setting.

heading: 3 Setting
text: The combinatorial multi-armed bandit (CMAB) problem is formulated by a T -round learning game between the learning agent and the environment. The environment contains m base arms and the arm set is denoted by [m] = {1, 2, . . . ,m}. Each arm i 2 [m] is associated with a distribution Di on [0, 1]. We consider a combinatorial setting where the agent can select several base arms at a time. In many applications, different arms usually have structural correlations in the selection decision of the agent. For example, in the PMC problem, base arms (edges) starting from the same node must be selected together. Thus the base arm set [m] can be further divided into n units, with each unit containing several base arms and a unit of arms will be selected together. Let U be the collection of all units and |s| be the number of base arms contained in unit s for any s 2 U .
In each round t = 1, 2, . . ., the learning agent selects an action St 2 S = {S ✓ U : |S| = K} to play. Here S is the set of all candidate actions containing K units. For any action S, denote [S = {i 2 s for some s 2 S} as the set of base arms that belong to units contained in S. The environment then draws a random output of all base arms Xt = (Xt,1, Xt,2, . . . , Xt,m) from the distribution D = D1 ⇥D2 ⇥ . . .⇥Dm. For any t, Xt,i is independent and identically distributed on Di with expectation µi, for any base arm i. Let µ = (µi)i2[m] be the mean vector. We study the semibandit feedback [30, 7, 29] where the agent can observe feedback Qt = {(i,Xt,i) | i 2 [St}, namely the output of all base arms in units contained in St. Denote Ht = {(S⌧ , Q⌧ ) : 1  ⌧ < t} as the history of observations at time t. The agent finally obtains a corresponding reward Rt = R(St, Xt) in this round, which is a function of action St and output Xt. We assume the expected reward satisfies the following two assumptions, which are standard in CMAB works [7, 30, 14, 24, 29].
Assumption 1. The expected reward of an action S only depends on S and the mean vector µ. That is to say, there exists a function r such that E [Rt] = EXt⇠D[R(St, Xt)] = r(St, µ). Assumption 2. (Lipschitz continuity) There exists a constant B such that for any action S and mean vectors µ, µ 0 , the reward of S under µ and µ 0 satisfies
|r(S, µ) r(S, µ0)|  B X
i2[S |µi µ
0 i| . (1)
When the mean vector µ is known beforehand, finding the optimal action containing K units is called the offline problem. However, the offline problems are usually NP-hard and enumerating all actions to find the best one is not feasible as the number of actions is exponentially large. The Greedy algorithm (presented in Algorithm 1) is a common method to solve such offline problems, which is simple to implement and can provide approximate solutions for OIM [16] and PMC [8], and exact solutions for MP-MAB[17]. More specifically, as long as the reward function satisfies monotonicity and submodularity on the action set, the Greedy algorithm can provide solutions with approximate guarantees [23]. Moreover, the Greedy algorithm is also popular to serve as a heuristic method in real applications and has good practical performance even without a theoretical guarantee.
Algorithm 1 Greedy algorithm 1: Input: base arm set [m] and mean vector µ = (µi)i2[m], unit set U , action size K 2: Initialize: Sg = ; 3: for k = 1, 2, · · · ,K do 4: sk = argmaxs2U\Sg r(Sg [ {s} , µ) 5: Sg = Sg [ {sk} 6: end for 7: Output: Sg
We mainly study the CMAB problem with the Greedy oracle. With input µ = (µi)i2[m], it sequentially selects K units to maximize the current expected reward. To simplify, we assume the Greedy’s solution Sg(µ), abbreviated as Sg , is unique, or equivalently the optimal unit in each step k (Line 4 in Algorithm 1) is unique. The general case with multiple solutions can also be solved and would be discussed later. The objective of the learning agent is to maximize the cumulative expected reward over T rounds, or equivalently to minimizing the cumulative expected regret with respect to the
Greedy’s solution Sg , which we call cumulative greedy regret [22] defined by
Rg(T ) = E " TX
t=1
max {r(Sg, µ) r(St, µ), 0}
# , (2)
where the expectation is taken from the randomness in observations and the online algorithm.
We call Greedy an ↵-approximate oracle if r(Sg(µ0), µ0) ↵ · r(S⇤(µ0), µ0) for any input µ0, where S ⇤(µ0) is the optimal action under µ0. Note when Greedy is ↵-approximate, the upper bound for greedy regret also implies the upper bound for the ↵-approximate regret defined by the cumulative distance between scaled optimal reward ↵ ·r(S⇤(µ), µ) and r(St, µ) over T rounds. The approximate regret is adopted in previous CMAB works based on UCB-type algorithms [7, 29, 32, 21]. It is much weaker than greedy regret as it relaxes the requirements for online algorithms and only needs them to return solutions satisfying the relaxed approximation ratio. We discuss more on challenges in analyzing the ↵-approximate regret with TS-type algorithms in Section 6.1.
An example of CMAB: probabilistic maximum coverage (PMC) The input for the PMC problem is a weighted bipartite graph G = (L,R,E), where each edge (u, v) 2 E is associated with a weight µ(u,v). Denote µ = (µ(u,v))(u,v)2E as the edge weight vector. The goal is to find a node set S ✓ L with |S| = K to maximize the number of influenced nodes in R, where each node v 2 R can be influenced by u 2 S with independent probability µ(u,v). The advertisement placement problem can be modeled by PMC, where L is the web page set, R is the user set and µ(u,v) represents the probability that user v clicks the advertisement on web page u. In this application, the user click probabilities are unknown and need to be learned during iterative interactions. The PMC problem fits our CMAB framework with each edge being a base arm and edges starting from the same node forming a unit. The expected reward of an action S is the expected number of nodes finally influenced by it, which is defined as
r(S, µ) = X
v2R
0 @1 Y
(u,v)2E,u2S
1 µ(u,v)
1
A . (3)
It is proved that the reward function satisfies Assumption 2 [7] and the Greedy oracle can provide an approximate solution with approximation ratio (1 1e ) for any input [23].

heading: 4 Algorithm
text: In this section, we introduce the combinatorial Thompson sampling (CTS) algorithm with Beta priors and Greedy oracle (presented in Algorithm 2) for CMAB problems.
Algorithm 2 CTS algorithm with Beta priors and Greedy oracle 1: Input: base arm set [m], unit set U , action size K 2: Initialize: 8i 2 [m], ai = bi = 1 3: for t = 1, 2, · · · do 4: 8i 2 [m] : Sample ✓t,i ⇠Beta(ai, bi). Denote ✓t = (✓t,1, ✓t,2, · · · , ✓t,m) 5: Select action St = Greedy([m], ✓t,U ,K) and receive the observation Qt 6: //Update 7: for (i,Xt,i) 2 Qt do 8: With probability Xt,i, Yt,i = 1; with probability 1 Xt,i, Yt,i = 0 9: Update ai = ai + Yt,i, bi = bi + (1 Yt,i) 10: end for 11: end for
The algorithm maintains a Beta distribution with parameters ai and bi for each base arm i 2 [m]. In the beginning, it initializes ai = bi = 1, 8i 2 [m] (Line 2). In each round t, the algorithm first samples a parameter candidate ✓t,i from Beta(ai, bi) representing the current estimate for µi (Line 4). Then the Greedy oracle outputs the solution St according to the input vector ✓t = (✓t,1, ✓t,2, · · · , ✓t,m) (Line 5). Based on the observation feedback, the algorithm then updates the corresponding Beta distributions for observed base arms (Line 7-10).

heading: 5 Lower Bound
text: We investigate the hardness of the CTS algorithm to solve CMAB problems with Greedy oracle by proving a problem-dependent regret lower bound.
First, we introduce some notations that will be used in the regret analysis. Recall Sg is the solution returned by the Greedy oracle when the input is µ. We denote it as Sg = {sg,1, sg,2, . . . , sg,K}, where sg,k is the k-th selected unit by Greedy. Further, define Sg,k = {sg,1, sg,2, . . . , sg,k} as the sequence containing the first k units for any k 2 [K]. Similarly, let St = {st,1, st,2, . . . , st,K} and St,k = {st,1, st,2, . . . , st,k}. Note Sg,0 = St,0 = ;. The corresponding gaps are defined to measure the hardness of the task and the performance of the algorithm. Definition 1. (Gaps) For any unit s 2 U and index k 2 [K] such that s /2 Sg,k 1, define the marginal reward gap
s,k = r(Sg,k, µ) r(Sg,k 1 [ {s} , µ)
as the reward difference between Sg,k and Sg,k 1 [ {s}. According to the Greedy algorithm, we have s,k > 0 for any k such that s /2 Sg,k. And for any action S 2 S, define S = max {r(Sg, µ) r(S, µ), 0} as the reward difference from the Greedy’s solution Sg . Let
mins = min S2S:s2S S , max s = max S2S:s2S S
be the minimum and maximum reward gap of actions containing unit s, respectively. Denote
max = maxS2S S as the maximum reward gap over all suboptimal actions.
We take the following PMC problem (shown in Figure 1) as the instance to carry out the hardness analysis. Each edge in the graph is a base arm and the set of all outgoing edges from a single node forms a unit. The action size is set to K = 2. The weight µ(u,v) of each edge (u, v) is listed on the edges, where we assume 0 <  0.04. The expected reward r(S, µ) of an action S under µ is defined as Eq (3). For example, when u1 and u2 are selected, the probability of v1 being influenced is 1 (1 µ(u1,v1))(1 µ(u2,v1)) = 0.592 and the probability that v2 is influenced is µ(u2,v2) = 0.3. The expected reward of S = {u1, u2} is r(S, µ) = 0.592 + 0.3 = 0.892. For simplicity, we also assume the output of each base arm in each round is exactly its mean. This assumption still satisfies the above properties and is also adopted in previous lower bound proofs [3] to simplify the analysis.
For convenience, we first list the expected reward of each action in this problem in Table 1. We can find that the greedy solution is Sg = {u2, u1} with sg,1 = u2, sg,2 = u1, and r(Sg, µ) = 0.892, while the optimal action is {u1, u4}. The corresponding marginal reward gaps of each unit can be then computed as follows.
u1,1 = 0.01 ;
u3,1 = , u3,2 = 0.012 + 0.7 ;
u4,1 = 0.02, u4,2 = 0.056 .
In the following, we mainly focus on unit u3 and take it as an example to derive the hardness analysis. According to Table 1, all actions containing u3 are suboptimal actions compared to Sg and minu3 = {u3,u4} = 0.52 +0.008. Thus to avoid regret generation, the algorithm should avoid incorporating u3 in the action St. Intuitively, u3 should be explored at least ⌦ log T/ 2u3,1 = ⌦ log T/ 2 times to be distinguished from sg,1 = u2 and thus can avoid being selected as the first unit by Greedy. However, in each round of exploration for u3, the algorithm needs to pay a constant regret of at least 0.52 + 0.008. Thus the estimation gap needs to be eliminated by exploration on the denominator of ⌦ log T/ 2 cannot be canceled by the actual regret paid in each exploration round.
Such mismatch would cause the greedy regret at least of order ⌦ log T/ 2 .
We give the formal lower bound for both the expected number of selections of each unit and the cumulative greedy regret in the following Theorem 1. Theorem 1. (Lower bound) Using the CTS algorithm with Gaussian priors and Greedy oracle to solve the CMAB problem shown in Figure 1, when T is sufficiently large, we have
E [NT+1,s] = ⌦ log T
2s,1
! , (4)
for any s 6= sg,1 = u2, where NT+1,s = PT
t=1 1{s 2 St} is the number of rounds when s is contained in the selected action set St.
Further, the cumulative greedy regret satisfies
Rg(T ) = ⌦
log T
2u3,1
! = ⌦ ✓ log T
2
◆ . (5)
The proof of Theorem 1 follows directly the intuition of the above hardness analysis. Due to the space limit, we include the detailed proof in Appendix B. The reason why we consider using Gaussian priors to derive the lower bound analysis is that we hope to use its concentration and anti-concentration inequalities. The analysis can directly apply to other types of prior distributions if similar inequalities can be provided. The main operations of CTS with Gaussian priors are very similar to that of Algorithm 2, while the only difference is on the prior distribution for unknown parameters and the corresponding updating mechanism. To be self-contained, we also present the detailed CTS algorithm with Gaussian priors in Appendix B.
Lin et al. [22] also show a lower bound for greedy regret of order ⌦(log T/ 2) with 2 (0, 1/4). However, the problem instance used to derive this lower bound is not a CMAB problem and thus their result is not comparable with Theorem 1.

heading: 6 Upper Bound
text: By investigating the properties of the CTS algorithm and the Greedy oracle, we also provide a problem-dependent regret upper bound for Algorithm 2 to solve general CMAB problems. Theorem 2. (Upper bound) The cumulative greedy regret of Algorithm 2 can be upper bounded by
Rg(T )  X
s 6=sg,1
max k:s/2Sg,k
6B2 |s|2 maxs log T
( s,k 2B |[Sg| ") 2 +
X
k2[K]
C
"2
✓ C 0
"4
◆|sg,k| max
+ ✓ |[Sg| ✓ 2 + 8
"2
◆ + 4m ◆ max (6)
=O
0 @ X
s 6=sg,1
max k:s/2Sg,k
B 2 |s| 2 max log T
2s,k
1
A , (7)
for any " such that 8s 6= sg,1 and k satisfying s /2 Sg,k, s,k > 2B |[Sg| ", where B is the coefficient of the Lipschitz continuity condition, |[Sg| is the number of base arms that belong to the units contained in Sg , C and C 0 are two universal constants.
Due to the space limit, we provide the proof sketch of Theorem 2 in Section 6.2 and defer the formal proof to Appendix C. In order to better compare the upper and lower bounds, we also analyze the greedy regret of the CTS algorithm with Gaussian priors in Appendix D, which achieves the same order of the upper bound with Theorem 2 only up to some constant factors.

heading: 6.1 Discussions
text: Challenges in analyzing the ↵-approximate regret with CTS The ↵-approximate regret is first brought up in analyzing UCB-type algorithms [6, 7, 29]. Under UCB, benefiting from the monotonicity between the true parameter µ and the UCB parameter µ̄, the ↵-approximate regret can be deducted as
↵ · r(S⇤, µ) r(St, µ)  ↵ · r(S ⇤ , µ̄) r(St, µ)  r(St, µ̄) r(St, µ) 
X
i2[St
|µ̄i µi| ,
where S⇤ 2 argmaxS2S r(S, µ) is an exact optimal action under real parameter µ. Thus it only needs to bound the number of selections of bad action St to get an upper bound for the ↵-approximate regret. However, under CTS, since there is no monotonicity between the true parameter µ and the surrogate parameter ✓, the approximate regret can only be deducted as
↵ · r(S⇤, µ) r(St, µ)  ↵ · r(S ⇤ , µ) ↵ · r(S⇤, ✓) + ↵ · r(S⇤, ✓) r(St, µ)
 ↵ · r(S⇤, µ) ↵ · r(S⇤, ✓) + r(St, ✓) r(St, µ)
 ↵
X
i2[S⇤ |✓i µi|+
X
i2[St
|✓i µi| .
To get an upper bound for the RHS, it requires a sufficient number of selections of the exact optimal action S⇤, which may not be the case with approximate oracles like the example shown in Theorem 1. Thus the ↵-approximate regret may not well fit TS-type algorithms.
Tightness of the upper bound We now discuss the tightness of the regret upper bound in Theorem 2 based on the problem instance shown in Figure 1. Specific to this problem, we have |s|  2 for all s since each node has no more than 2 outgoing edges. And based on [21, Theorem 4], the coefficient of the Lipschitz condition in this problem is B = 1. When 0 <  0.04, we have s,1 = mink:s/2Sg,k s,k for any s 6= sg,1 = u2, and max = {u2,u4} = 0.056 is a constant. Thus our regret upper bound in this problem instance is of order
O
0 @ X
s 6=sg,1
max k:s/2Sg,k
B 2 |s| 2 max log T
2s,k
1
A = O
0 @ X
s2{u1,u3,u4}
log T
2s,1
1 A = O ✓ log T
2
◆ ,
where the last equality holds since u1,1 = 0.01, u4,1 = 0.02 are constants and u3,1 = .
We can see our regret upper bound matches the lower bound of (5) in Theorem 1 only up to some constant factors in this specific problem instance.
Comparison with MAB When each unit contains only one base arm and the action size is K = 1, our CMAB framework recovers the MAB problem and the Greedy oracle can provide the exact optimal solution. Thus we can also compare our regret upper bound with the theoretical results of the TS algorithm in MAB problems. In the MAB problem, the expected reward of each action is exactly the mean of the base arm contained in this action. Thus the Lipschitz coefficient is just B = 1 and |s| = 1 for any unit s. The optimal action is Sg = Sg,1 with |[Sg| = 1. And for any unit s 6= sg,1,
we have maxs = s,1. Thus, according to (6) of Theorem 2, the regret upper bound of Algorithm 2 in MAB problems is of order O ⇣P s 6=sg,1 log T s,1 ⌘ , which recovers the main order of the regret upper bound of TS for MAB problems [3].
Comparison with [22] Though Lin et al. [22] also study greedy regret, the results are not directly comparable in general since the setting studied in [22] is not a CMAB setting. We find that the PMC problem under a bar graph in these two settings can be equivalent, where a bar graph is a special bipartite graph with each left node’s outdegree being 1 (indegree being 0) and each right node’s indegree being 1 (outdegree being 0). In this case, our greedy regret upper bound is of order O(m log T/ 2) and theirs is O(mK log T/ 2). So ours is O(K) better than theirs. Even in this case, their algorithm needs to estimate O(m · 2m) parameters, while Algorithm 2 is more efficient and only needs to estimate O(m) parameters.
The definition of the marginal reward gap Recall that the Greedy oracle provides approximate solutions for problems whose expected reward satisfies monotonicity and submodularity on the action set. Formally, the submodularity means for any action S ✓ T and unit s /2 T , there is r(S [ {s} , µ) r(S, µ) r(T [ {s} , µ) r(T, µ), which characterizes the phenomenon of diminishing returns. One may concern that in these problems, due to the submodularity, the marginal reward gap s,k for larger k may become much smaller and the main order of the upper bound thus blows up. We clarify that the submodularity cannot imply the relationships among marginal reward gaps s,k for different k 2 [K]. The problem instance in Figure 1 satisfying submodularity [16] indicates that the marginal reward gap s,k does not necessarily decrease with the increase of k.

heading: 6.2 Proof Sketch
text: In this section, we briefly introduce the proof idea of Theorem 2. At any step k 2 [K], for any unit s /2 Sg,k, the selection of s in action St may force the Greedy oracle to choose a worse action in subsequential steps and make CTS suffer constant regret. A sufficient condition for generating zero greedy regret in round t is that each unit st,k selected in step k is actually sg,k for any k 2 [K]. Thus to bound the cumulative greedy regret, we sequentially analyze whether sg,k is appropriately selected at each step k.
Recall that under the framework of the CTS algorithm, the Greedy oracle sequentially selects st,k for k 2 [K] based on ✓t sampled from posterior distributions in round t. Focusing on step k = 1, to ensure st,1 = sg,1, the algorithm needs to guarantee the accurate estimations ✓t,s for any unit s 2 U such that r({s} , ✓t) < r(Sg,1, ✓t), 8s 6= sg,1, where ✓t,s is the projection of ✓t on unit s. We first assume sg,1 is already estimated well. Then based on this assumption, when all of the other units s 6= sg,1 have been explored O(log T/ 2s,1) times and thus estimated accurately, sg,1 would be selected at the first step with high probability. But if after any other unit s 6= sg,1 has already been estimated well, sg,1 is still not selected appropriately, we can conclude that the estimations for sg,1 are not accurate enough. In this case, the Beta posterior for sg,1 tends to be uniformly distributed. When CTS sample ✓t,sg,1 from its Beta posterior, with constant probability there would be r(Sg,1, ✓t) > r({s} , µ) ⇡ r({s} , ✓t) for any unit s 6= sg,1. Thus after some rounds, sg,1 would be selected for enough times and also estimated accurately. In the following rounds, sg,1 would be selected appropriately at the first step with high probability. Above all, the expected number of misselections at the first step can be bounded.
The above analysis can apply to other cases when k = 2, 3, . . . ,K. Based on the correct selections in the first k 1 steps, the misselection of st,k also comes from the bad estimations for both sg,k and other units s /2 Sg,k. To distinguish r(Sg,k 1 [ {s} , ✓t) from r(Sg,k, ✓t), those units need to be explored at least O(log T/ 2s,k) times.
According to the above analysis, for each unit s 6= sg,1, we define the exploration price as
L(s) = O
max
k:s/2Sg,k
log T
2s,k
! . (8)
To avoid being incorrectly selected at some step k, each unit s /2 Sg,k needs to be explored for at least L(s) times. The sum of L(s) over all units s 6= sg,1 leads to the main order of the regret upper bound in Theorem 2.

heading: 6.3 Extension to Multiple-solution Case
text: We can also extend the analysis of the regret upper bound to the case where multiple solutions may be returned by Greedy with input µ, or equivalently the optimal unit in each step k (Line 4 in Algorithm 1) may not be unique. Let
K = ( {s1, s2, . . . , sK} : s1 2 argmax
s r({s} , µ), . . . , sK 2 argmax s/2{s1,...,sK 1} r({s1, . . . , s} , µ)
)
be the set of all actions that are possibly returned by the Greedy oracle when the input is µ. Here we do not care how Greedy breaks the tie at each step and regard this process as a black box. In order to take into account the worst case where Greedy always returns a solution with minimum reward compared to other possible solutions, we define Sg 2 argminS2 K r(S, µ) as one of Greedy’s possible solutions with the minimum expected reward and consider the cumulative greedy regret defined in Eq (2).
The regret analysis of Algorithm 2 in this case is similar to the proof of Theorem 2. A sufficient condition for generating zero regret in round t is that the selected action St falls into the set K . Thus to bound the cumulative greedy regret, we sequentially analyze whether the unit st,k selected in each step k is an optimal unit conditioned on the previously selected units St,k 1. For completeness, we include the regret upper bound as well as the detailed proof for this case in Appendix E.

heading: 7 Conclusion
text: In this paper, we aim to answer the question of whether the convergence analysis of TS can be extended beyond exact oracles in the CMAB area. Taking the common offline (approximation) Greedy oracle as an example, we derive the hardness analysis of CTS for CMAB problems based on a constructed CMAB problem instance. When using CTS with Greedy oracle to solve this problem, we find that the algorithm needs to explore at least ⌦(log T/ 2) rounds to distinguish suboptimal units from the optimal unit at some step. However, at least constant regret needs to be paid for each exploration round. The mismatch between the gap to be distinguished and the actually paid regret forces the algorithm to pay the cumulative greedy regret of order ⌦(log T/ 2). We also provide an almost matching problem-dependent regret upper bound for the CTS algorithm with Greedy oracle to solve CMAB problems. The upper bound is tight on the constructed problem instance only up to some constant factors and also recovers the main order of TS when solving MAB problems.
An interesting future direction is to extend the current CMAB framework to the case with probabilistically triggered arms (CMAB-T). The CMAB-T framework can model the OIM problem on general social networks. As shown in [21], using UCB-type algorithms to solve such a problem may face great challenges on the computation efficiency. This problem is expected to be avoided by TS-type algorithms since TS would sample candidate parameters to escape the computation of complicated optimization problems. However, the current proof idea based on each selection step of the Greedy oracle (proof of Lemma 1) cannot directly apply to this setting as different units may probabilistically trigger some common base arms. New proof techniques are required to derive the theoretical guarantee of the TS algorithm with the Greedy oracle in this framework.

heading: Acknowledgement
text: The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62006151, 62076161). This work is sponsored by Shanghai Sailing Program.

Review summaries:
This paper studies a setting where Thompson Sampling with greedy approximation oracles is applied to combinatorial semi-bandit. The main contribution is to theoretically reveal how the suboptimality of greedy oracles can affect Thompson sampling in the worst case. Specifically, the greedy regret is shown to be lower bounded by $\Omega(\log T / \Delta^2)$. The authors also prove an almost matching upper bound.   --- After rebuttal ---  I appreciate the authors' kind response. Having read all the responses and review comments, I've found that the result is more significant than I thought. Therefore, I increased my score to 6.  

The paper studies the performance of Thompson-Sampling (TS) when applied to combinatorial multi-armed bandit (CMAB) problems with semi-bandit feedback. It is well known that the combinatorial TS (CTS) algorithm might suffer from linear regret when the combinatorial maximization is solved using an approximation oracle [30]. In this work, the authors apply CTS with a specific family of combinatorial maximization oracles – greedy oracles. They analyze the greedy regret of CTS (which compares the played actions to the greedy solution of the combinatorial problem) and derive regret upper bounds of $O(\log T/\Delta^2)$, where $\Delta$ is a suboptimality gap. They also provide a matching lower bound for CTS on a specific small-scale problem.

The paper studies the combinatorial multi-armed bandit (CMAB) problem in a setting where exactly solving the corresponding offline optimization problem is not feasible (due to its computational hardness) and the learning agent only has access to a greedy oracle which approximately solves the offline optimization problem. In this framework, the paper analyzes the behavior of a natural variant of the Thompson sampling algorithm called Combinatorial Thompson sampling (CTS). The paper first gives an algorithm-dependent and problem-dependent lower bound showing that CTS faces a fundamental limit, then provides an almost matching upper bound.

The paper studies the combinatorial semi-bandit problem. It provides the first analysis of Thompson sampling (TS) with the greedy oracle. It shows instances that the TS with Gaussian priors suffers $\Omega(\log T / \Delta^2)$ regret from. It proposes a modified TS with Beta priors and shows that the proposed algorithm achieves $O(\log T / \Delta^2)$ regret for the instances. The proposed algorithm enjoys near-optimal regret for the multi-armed bandit problem.

The paper presents a TS algorithm that uses Greedy oracle to minimise the cumulative regret on combinatorial multi-armed bandit (CMAB) setting. beside presenting an upper bound, they have also established a lower bound (on the cumulative regret) for their approach. The paper discuss the intuition of behind the proof of their proposed analysis for upper bound assuming the "Greedy" step (Line 4 in  Algorithm 1) returns a unique solution, and then in section 6.2 it relaxes that assumption.  CMAB is a well-known framework in the MAB literature, that generalises probabilistic maximum coverage (PMC), online influence maximization (OIM), multiple-play MAB (MP-MAB), minimum spanning tree (MST) and many others. TS based regret-minimisation algorithms are very efficient for the family of single parameter reward distribution; there are recent studies that apply TS under the CMAB setup. Again, finding the optimal solution (in offline learning) for many problems (like PMC, OIM etc.) is NP-hard. On the other hand, Greedy oracle is a popular choice in various optimisation methods (including submodular maximisation).   Hence, the idea to attack the CMAB setup with TS using a Greedy oracle is very natural.