When Combinatorial Thompson Sampling meets Approximation Regret
Authors: Pierre Perrault
Venue: NeurIPS 2022 Accept (2022)
Keywords: combinatorial multi-armed bandit
semi-bandit
thompson sampling
approximation regret
oracle
probabilistically triggered arms
greedy oracle

Abstract: We study the Combinatorial Thompson Sampling policy (CTS) for combinatorial multi-armed bandit problems (CMAB), within an approximation regret setting. Although CTS has attracted a lot of interest, it has a drawback that other usual CMAB policies do not have when considering non-exact oracles: for some oracles, CTS has a poor approximation regret (scaling linearly with the time horizon $T$) [Wang and Chen, 2018]. A study is then necessary to discriminate the oracles on which CTS could learn. This study was started by Kong et al. [2021]: they gave the first approximation regret analysis of CTS for the greedy oracle, obtaining an upper bound of order $\mathcal{O}{\left(\log(T)/\Delta^2\right)}$, where $\Delta$ is some minimal reward gap. In this paper, our objective is to push this study further than the simple case of the greedy oracle. We provide the first $\mathcal{O}{\left(\log(T)/\Delta\right)}$ approximation regret upper bound for CTS, obtained under a specific condition on the approximation oracle, allowing a reduction to the exact oracle analysis. We thus term this condition Reduce2Exact, and observe that it is satisfied in many concrete examples. Moreover, it can be extended to the probabilistically triggered arms setting, thus capturing even more problems, such as online influence maximization.

When Combinatorial Thompson Sampling meets Approximation Regret
Pierre Perrault
Idemia pierre serre.pperrallteedmmaa..oom
Abstract
We study the Combinatorial Thompson Sampling policy (CTS) for combinatorial multi-armed bandit problems (CMAB), within approximation regret setting. Although CTS has attracted a lot of interest, it has drawback that other usual CMAB policies do not have when considering non-exact oracles: for some oracles, CTS has a poor approximation regret (scaling linearly with the time horizon T" [Wang and Chen, 2018]. A study is then necessary to discriminate the oracles on which CTS could learn. This study was started by Kong et al. [2021]: they gave the first approximation regret analysis of CTS for the greedy oracle, obtaining an upper bound of order O (log(T) (T) > where A is some minimal reward gap. In this paper, our objective is to push this study further than the simple case the greedy oracle. We provide the first O (log((7) (T) / A) approximation regret upper bound for CTS, obtained under a specific condition on the approximation oracle, allowing a reduction to the exact oracle analysis. We thus term this condition REDUCE2EXACT. satisfied many concrete examples. Moreover, it can be
and observe that extended to the probabilistically triggered arms setting, thus capturing even more problems, such as online influence maximization.
Introduction
Stochastic multi-armed bandits (MAB) [Robbins, 1952, Berry and Fristedt, 1985, Lai and Robbins, 1985] are decision-making problems in which an agent acts sequentially in an uncertain environment. At each round E N the agent must select one arm from fixed set n arms, denoted by [n] A (1,...,,1) n). using a policy, based on feedback from the previous rounds. Then it gets as feedback outcome Xt, E R random variable sampled from IPx,, independently from previous rounds where is the selected arm and IP x; is a probability distribution unknown to the agent of mean μr The goal for the agent is to maximize the cumulative reward over total of rounds (I' is the time horizon and may be unknown). The performance metric of policy is its regret Rt, which is the expectation of the difference over T' rounds between the cumulative reward of the policy that always picked the arm with the highest expected reward and the cumulative reward of the learning policy. MAB models the called dilemma between exploration and exploitation, i.e., whether to continue exploring arms to obtain more information (and thus strengthen the confidence in the estimates of the distributions PPx.). according to the observations so far.
use the information gathered by playing the best arm
In this paper, we study stochastic combinatorial multi-armed bandit (CMAB), with semi-bandis feedback, a.k.a. stochastic semi-bandit (still abbreviated as CMAB this paper), an extension of MAB where the agent plays an action (also called super-arm) Ar E A C P([n]) at each round t, where is fixed and called action space. The feedback includes the outcomes of all base arms in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the played super-arm. The expected reward, given A,, is assumed to be in the form² r(A,, v²),, where fe" E IR" is the unknown vector of expectations (traditionally, the reward is linear and equal to e (²). In recent years, CMAB has attracted a lot of interest (see e.g. Cesa- Bianchi and I. Lugosi [2012], Gai et al. [2012]. Chen et al. [2013, 2016). Kveton et al. [2015], Wang and Chen [2017], Perrault [2020], particularly due to its wide applications in network routing, online advertising. recommender system, influence marketing, etc.
Many CMAB policies are based on the Upper Confidence Bound (UCB) approach, extending the classical UCB policy [Auer et al., 2002] from MAB to CMAB. This type of approach uses an optimistic estimate μ4, of μ (i.e., for which the reward function is overestimated), lying in well- chosen confidence region. Then, the action is chosen by plugging be inside an oracle (typically, Oracle(H") is a maximizer of the reward function A F r(A, μe D). An example of such policy Combinatorial Upper Confidence Bound (CUCB) [Chen et al., 2013, Kveton et al., 2015], that uses a Cartesian product of the individual confidence intervals of each arm as a confidence region. For mutually independent arms, Combes et al. [2015] provided the UCB-style policy Fffficiens Sampling for Combinatorial Bandit (ESCB), building tighter axis-aligned ellipsoidal confidence region around the empirical mean, which helps to better restrict the exploration. Degenne and Perchet [2016] provided a policy called OLS-UCB, leveraging a sub- sub-Gassiinitty assumption on the arms to generalize the ESCB approach. These policies have been further extended to more general settings afterwards [Perrault et al., 2020c,d, 2019a]. Although improving CUCB, all these generalizations are inefficient in terms of computation time.
Another paradigm that has recently gained interest (and which will be our focus in this paper) is to rely on Thompson Sampling (TS) instead of UCB, still targetting frequentist regret. Although introduced much earlier by Thompson [1933], the theoretical analysis of TS for MAB is quite recent: Kaufmann et al. [2012]. Agrawal and Goyal [2012] gave a regret bound matching the UCB policy theoretically. Moreover, TS often performs better than UCB in practice, making TS an attractive policy for further investigations. For CMAB, TS extends to Combinatorial Thompson Sampling (CTS). In CTS, the unknown mean fe is associated with a belief (a prior distribution, that could be e.g. a product of Beta or Gaussian distributions) updated to a posterior with the Bayes rule, each time a feedback is received. In order to choose action at round t, CTS draws sample O, from the current belief, and plays the action given by Oracle(0; (f.). CTS is an attractive policy because it has similar ad advantages to the previously mentioned policies working with ellipsoidal confidence regions while being, like CUCB, computationally efficient. Indeed, recently, for mutually independent arms and Gaussian arms respectively, Wang and Chen [2018], Perrault et al. [2020a] proposed tight analyses of CTS.
Unlike UCB-based policies, the analysis of CTS is valid only when Oracle is exact, i.e., when
Oracle(ı) E arg magmax/i ((A, p1).
arg. AEA
Although this holds true for many combinatorial problem described by the pair (r, Ar) (we recall that is usually linear), there exist some problems where the requirement on Oracle has to be relaxed in order to make it tractable. This is usually done considering an a-approximation oracle [Chen et al., 2013, 2016, Wen et al., 2016], for a E (0, 1):
r(Oracle(p)) 11) 2 max rA,, 14).
(1)
AEA
Under an a-approximation oracle, the benehmark cumulative reward is the a-fraction of the optimal reward, leading to the notion of approximation regrer [Kakade et al., 2009, Streeter and Golovin, 2009, Chen et al., 2016].
Aware of the limitation of their CTS analysis (that works only with exact oracles), Wang and Chen [2018] also proved, in their Theorem that this limitation is not technical artifact. More precisely, they provided a specific CMAB instance with an associated approximation oracle, such that CTS on this instance and with this oracle must have a regret scaling linearly in T. Although this negative result is of great interest to the research community, some concerns limit its consideration. Indeed,
'Note that will consider the probabilistically triggered arms extension in this paper. i.e. where the feedback on triggered arms. For brevity, we do not present this generalization in introduction.
"Henceforth, we typeset vectors and matrices in bold and indicate components with indices, e.g., a (as) IR.. We also let e; be the 4h canonical unit vector of I2". and define the incidence vector of any
subset A [n]] e e Eied c; We denote by ④ b A (a:b:) the Hadamard product of two vectors and b.
2

---

not only the CMAB instance provided by Wang and Chen [2018] is actually a MAB one (meaning that there is an efficient oracle that simply enumerates the arms), so the use of an approximation regret is not justified, but above all, both the oracle and the instance are uncommon and designed for the proof.
Interested in the question of whether the example provided by Wang and Chen [2018] is pathological or generalizable, Kong et al. [2021] recently initiated a study, which revealed that linear approximation regret for CTS seems to be pathological. More precisely, they derived a (log( (T)/A²) bound for the specific case of greedy oracle', where A is some reward gap. This result is obtained by bounding the approximation regret by a greedy regret, that simply replaces a max AE A r( A, j²") with r(Oracle ): fz") ), using equation (1). They also gave tight lower bound on the greedy regret.
In this paper, we want to explore another class of oracles covering more problems in practice. Our goal is to demonstrate that although there are instrumental examples of problems where CTS has a linear regret, the majority of concrete problems do not follow this regime, and are in fact similar to the exact oracle case.
Contributions With a specific condition on Oracle, we describe a general set of CMAB problems where the approximation regret of CTS has a (log(T)) A) bound, improving by a factor I/A over the bound of Kong et al. [2021]. This does not contradict their lower bound, which is focused on the greedy regret. We call this set of CMAB problems REDUCE2EXACT, because, as we will see, a REDUCE2EXACT problem can be approximated using a reduction to sub-problems that can be solved exactly. Our main result is the approximation regret guaranty for REDUCE2EXACT problems, provided in Theorem The REDUCE2RX condition on Oracle is structural and applies notably to greedy algorithms for submodular maximization. In particular, it allows to deal with problems such as probabilistic maximum coverage. We note that REDUCEEEXACT is compatible with the probabilistically triggered arms setting, which allows us to capture even more problems, such as online influence maximization [Wen et al., 2017, Wang and Chen, 2017]. As we want to focus on concrete problems, we provide several other examples that belongs to REDUCE2EXACT: Metric k-center, Vertex cover, Max-Cut and Travelling salesman problem.
Further related work We refer the reader to Wang and Chen [2018] for more related work on TS for combinatorial bandits. Briefly, one can mention Gopalan et al. [2014], that gave a frequentist high-probability regret bounds for TS with a general action space and feedback model - Komiyama et al. [2015], that studied TS for the mn-sets action space - Wen et al. [2015], that studied TS for contextual CMAB problems, using the Bayesian regret metric (see also Russo and Van Roy [2016]).
Other known limitations of CTS Apart from the limitation related to the approximation regret that interests us in this paper, there are some other existing limitations of CTS highlighted in the literature, which we review here: The CTS policy has an exponential constant term in its regret upper bound [Wang and Chen, 2018, Perrault et al., 2020a], and Wang and Chen [2018] proved in their Theorem 3 that this is unavoidable. A similar behavior have been demonstrated in Zhang and Combes [2021] l], where it is shown that CTS does not scale polynomially in the ambient dimension in general. In addition, Zhang and Combes [2021] also proved that CTS is not minimax optimal. Actually, they even proved that in high dimensions, the minimax regret of CTS is almost linear in T.
The strengths of CTS Despite the weaknesses mentioned above, CTS remains a widely used policy, mainly because of its empirical performance. Indeed, CTS generally outperforms other policies such as CUCB and ESCB [Wang and Chen, 2018, Perrault et al., 2020a]. Moreover, it is relatively simple to implement, and is computationally efficient (just like CUCB). On the theory side, another advantage is that for an exact oracle, CTS is asymptotically quasi-optimal" for many settings where CUCB is not, and where ESCB is computationally inefficient [Perrault et al., 2020a]. It would be desirable that these advantages also apply to the case of approximation regret, thus motivating our investigations.
'It is worth mentioning that this oracle is one of most common, so it logical to focus on it first. 'This means that it has a distribution distributtonndepeedeet dependent regret upper bound whose leading term in I has an optimal rate, up to logy-logari factor in
3

---

2 Model and definitions
For more generality, we consider the probabilistically triggered extension of CMAB [Chen et al., 2016, Wang and Chen, 2017], abbreviated to CMAB-T. In this context, the action A E A selected is not necessarily equal the triggered super-arm S. More precisely, the action space A is no longer necessarily a subset of P(nxl) and can be infinite. At round 6, the agent selects A E A,
@ es...) and possible extra source of randomness (we denote by Fr the filtration containing Hi and the extra randomness of round t - in particular, Ag is F:-meauurable). Then, an independent sample X, ~ Pxx X, E IR" drawn and random subset S. E S C P(m)) of arms are triggered (S is called super-arm space or subset space). We assume that St is drawn independently from a distribution Drig (Ar, X.) and that the outcome of an arm does not depend on whether it is triggered. In addition, we don't have we assume that Drng doesn't 't depend on X,. For the feedback, the outcome of each
based on the history of observations H, _ o (X1 @ es ... X,-1
Px Biejn) 1 x,, triggered arm is observed, i.e., es, @ X, is observed. The expected reward is of the form r( (A,, p²), where is a function defined on domain A M, with M C TR. The objects A, Drig: are known to the agent. We assume that ((,,/"' admits a maximum r(A",, ju") on A. In the following, we give the definition of the probability that an arm E [n] is triggered (and thus that a feedback from obtained) by having played a certain action A E A. Definition (Triggering probabilities). The triggering probabilities are defined for all E [nx] and A E A as (A) & Pfi E S], where S ~ Dini( X), X ~ Px.
Under an a-approximation Oracle, we use the approximation regret to evaluate the performance of policy т, defined as follows.
Definition 2 (Approximation regret). The T Tround a-approximation regret of a learning policy that selects action A₁ A at round t is defined as follows, where the approximation gap is defined as A, A (A.) A V (ar(A", 1²) - r(Ar, 11") ()) with A E arg max ma (A,,"')
RT (T)
E
A (E(T]
To approach the problem of minimizing Rr, we consider the following standard assumptions [Wang and Chen, 2017]. Assumption 1 (Approximation oracle). The agent has access to an Oracle such that for any mean vector μ M,
r(Oracle(p)) p1) 2 or(A", .t).
Assumption 2 (1-norm triggering probability modulated bounded smoothness). There exists B E R such that for all A E A, for all μ. H E M.
Ir(A, p) r(A, A') & Σ Pi(A)B A4l-
iE|m]
Assumption 3 "Sub-Gaussianity of the outcome distribution). Px is such that VA E R",
IE N n") S 1/Al///
For example, Pxx @ xx, and X, 0.2. Definition 3 (Other definitions), We define, for i E [m], the minimal gap of an action containing as
É [0, 1] (from Hoeffiding's 's Lemma [Hoeffding, 1963]).
A,min AEA: mi(A)s0, ((A)S A(A).
inf
The minimal and maximal gaps are defined as
Amin
min Atmin
and
Amax sup A(A).
sE(ni
AEA
For A E A. we let T(A) & fi E [n] P((A) > 0} be the set of arms that are triggerable by selecting
action A. We finally define
m A sup [(A)):
m [(AA)),
and p"
sE|n], AEA: p(lA)>0 (A()).
inf

---

Algorithm CTS-BETA
Initialization: For each arm i, let ni d; 1.
For all t 2 1:
Draw 0, ~ @i (et 6z). Play A, = Oracle(O,) (O,).
Get the observation X, 3 es., and draw Y, &ies. Bernoulli(X,p)
For all i E St update y Yo + Yi, and 6; <- ò + Yi,
Algorithm 2 CTS-GAUSSIAN
Input: 3 >>> 1.
Initialization: Play each arm once (if the agent knows that μ1" E [a, b)", this might be skipped) For every subsequent round t:
Draw 0₂ ~ [ig[n] (T (F N, 11/41//44 (0,, ~ U b) if No.-1 0).
Play A, = Oracle ()).
Get the observations X, @ es, and let Y, X,-
Update - and counters accordingly.
Combinatorial Thompson Sampling and exact oracle analysis
In this section, we present the CTS policy, focusing on two versions, one working with Beta prior, and the other with a Gaussian prior. Then, we present an associated analysis for the exact oracle case (i.e., with 1).
3.1 Algorithms
Based on the above assumptions, we focus on two versions of CTS. The first version is CTS-BETA [Wang and Chen, 2018] (Algorithm 1), working when we assume furthermore that Px 04E(M) Px,
and X 0.8. E [o. 1] (note that this actually covers the case of bounded X, by adjusting the parameter B). For each arm E [m]] CTS-BETA maintains Beta prior distribution with parameters % and 5, (initialized to 1). At each round t, for each arm i, the algorithm sample 8ú, from the corresponding prior, representing the current estimate of μ.- Then the oracle outputs the action A, to play according to the input vector 0,, Based on the observation feedback, the algorithm then updates the corresponding Beta distributions. The second version is CTS-GAUSSIAN [Perrault et al., 2020a] (Algorithm 2), that works under the more general Assumption It essentially the same as CTS-BETA, except that the prior distributions are Gaussian. For both Algorithm I and Algorithm and an arm E [n]. we define the number of time has been triggered at the beginming of round t, called counter of arm
N
Σ Iii E Sr). rE(t-1
We also define the empirical mean at the beginning round as
Iii SYYY
Nr.-1
-E(-1
3.2 Analysis of CTS: the a case
Although this is close some known results in the current literature [Huyuk and Tekin, 2019, Perrault et al., 2020a], there is no proof for the classical (log(m) (og(T) B. A regret bound under the above assumptions in the CMAB-T setting, either for CTS-BETA (Algorithm 1) or CTS- GAUSSIAN (Algorithm 2). We thus provide such a result in Theorem 1 (the proof is postponed to Appendix A). We can notice a difference with the work Huyuk and Tekin [2019] concerning the Assumption 2, where the triggering probabilities do not appear (and are present in the main term of their final regret bound). The main difference with Perrault al. [2020a] is that they not consider probabilisticalyy triggered arms.
5

---

Theorem 1. If min > 0 and p" > O, the policy x described in Algorithm 1 (under Assumptions 1, 2
and Px Bieln xx,, X É [0, 11a) or Algorithm 2 (under Assumptions 1, 2 and 3) has a regret of order
0.s.
B² (ogg(m)loo(
RT, = =0
Σ
iimin
/E/m]
In addition to being new result in itself, Theorem 1 will be useful for the a < 1 case. Concerning the bound, after changing the CMAB setting to CMAB-T, it should be noticed that the T-independent additive constant depends on 1/p", , the cause being the use of the Lipschitz condition (Assumption 2) without weighting by probabilities. We think that this dependence should be avoidable, but it seems that another technique has be considered. Finally, we remark that this kind of bound can be usually transformed into gap-independent /T bound [Chen et al., 2013], however, for CTS, achieving this transformation impossible since CTS is not minimax optimal (as we mentioned the paragraph "Other known limitations of CTS").
4 The a < 1 case for REDUCE2EXACT problems
We will now look the approximation algorithms involve a relaxation, or reduction to one more problems that can be solved exactly (in this paper, we use the terminology sub-problems to refer to them). The approximation guarantee for such an approximation algorithm is thus obtained by linking the original problem to those sub-proe aob-problems. We give a simple abstract example to illustrate this idea. Let's say we want to maximize function f on some set F, using an a-approximation algorithm. Assume there exist two other functions g and h defined on sets G and H respectively, such that x H C F and such that g and h can be maximized exactly G and H respectively. Finally, assume that for all (z, v) E G x H,
case. Our strategy is based on the following observation: many
max f(x, v) S maxg g(x) + max h h(y))
F
This means that an a-approximation algorithm maximize f can simply output the feasible solution (arg max 9. arg max n /a) E This example may seem very basic and artifactual at first glance, but turns out that many approximation algorithms rely on the same principle, as we will see in subsection 4.2. To see how this can be exploited for approximation regret minimization, we can notice that the LHS of (2) is an approximation gap (as defined Definition 2, taking the max with and considering that the choice (Ir, y) E F is that of policy at given round, with F playing the role of the action space) and that the RHS is the sum of two gaps, with G (respectively H) playing the role of the action space, but this time without approximation factor. Summing over the rounds, we find that the corresponding approximation regret is bounded by the sum of two "classical" regrets (in this paper, we use the terminology sub-regrets). Thus, the bounds we obtain on these two sub-regrets using CTS with the corresponding exact oracles translate into an bound on the approximation regret.
Avoiding the "mismatch" phenomenon Kong et al. [2021] identified the reason why their regret bound has a 2 in the denominator, while the usual CMAB algorithms only have A. They term a "mismatch" between the estimated gaps that need to be eliminated by exploration and the actual regret the algorithm needs to pay. We argue that, in fact, this mismatch phenomenon should exist in principle, even for non-approximation regret. It is usually avoided using a smoothness assumption like Assumption 2, linking our estimations (here the arms that generate the feedback) and what is paid. In the above example, although we are in an approximation context, the situation is fundamentally no different. We see that (2) links the paid approximation regret with two exact sub-regrets which themselves assumed to be related to estimates through a smoothness-like property. There is thus an indirect link between the approximation regret and the outcomes, which enables one of the A present in the denominator of the exploration term log(T")/A* to be cancelled out by the actual regret paid, thus avoiding the mismatch phenomenon.
To summarize, just as the approximation relation is obtained by linking the original problem to sub-problems that can be solved exactly, the idea behind REDUCE2EXACT problems is to link the approximation regret to several sub-regrets, each satisfying the appropriate properties for CTS, namely a smoothness relationship and the availability of an exact oracle. We formalize this in the following assumption.

---

Assumption 4 (REDUCE2EXACT) There exist E N", c E R4 and B, ; all j [e] such that the following true. Oracle is of the form Oracle Oracle, Oracle,, where Oracle, and Oraclez are described as follows.
Oracle For pa M, Oracle (1)) must ouiput sequence (Fi,..., Ex) described as follows. For each j E [f]. let E (F F)-1) be a sub-action space which may depend on Ei...., Æ--1 and let (, : R be a reward sub sub-finction. Then, we require that Eg arg maxg (,(E,
Oraclez : For an input E1 E EE, Eg E &t, Oraclez ( Ee) must outpu an action in A such that:
A(Oracley(En) (E Ee)) -
Σ (r,(Ej (r, cj.
(3)
JEL
where for all j [C], EJ E arr maKee, (, μ²).
Finally, in addition to the above constraints on Oracle: and Oraclez, for each j E [(], we require that the reward sub-function rj satisfies Assumption with the constants Bj and with the triggering probabilities p; (Oracley(E1.... Et)). [n]]
Informally, in the above Assumption 4, for E M, Oracle (p)) exactly solves a finite sequence of recursively defined optimization sub-problems and Oracle, builds an action in A for the original approximation problem using the intermediate solutions provided by Oracle At first sight, Assump- tion 4 seems very specific and rather difficult to fulfill. However, we will see in subsection 4.2 that many concrete problems satisfy it.
4.1 Analysis
In this subsection, we give in Theorem the main result of this paper. It basically states that under Assumptions 4, the CTS policy have regret bound comparable to the exact oracle case. The proof is postponed to Appendix B.
Theorem 2. If Amin 0 and O, the policy described in Algorithm I (under Assumption
and Px- = Siein Px. X E
a.s.
[0, 1) or Algorithm 2 (under Assumptions 3 and 4) has regret of order
EEjeqa Bije)) log(m) log(T')
Rr.a 00
Σ 1E/ml
Ai,ain
The idea of the proof is quite simple once Assumption 4 has been made. We can see that the approximation regret can be decomposed into é sub-regrets, according to equation (3). Then, one must focus on the fact that the sub-regrets may dependent on each other and that the right gap (defined with the original reward function) must be obtained in the denominator of the final bound.
4.2 Examples of REDUCE2EXACY problems
Here, we present several problems belonging to REDUCE2EXACT. Each time, after a quick introduc- tion of the problem, we translate it into CMAB- T context, and finally show how satisfies the REDUCE2EXACT criteria. The Travelling salesman problem (TSP) is treated in Appendix C.
Submodular maximization (e.g., probabilistic maximum coverage (PMC)) Here, only ex- pose the PMC example, noting that the same derivation can be applied to monotone submodular function. PMC is of the main examples proposed by Kong al. [2021]. Given weighted bipartite graph G (L, R, E), with weights μ 2 (M(w,)))(,,))e: (notice there thus E arms, recalling that for can choose as an action, explaining why arms are not indexed by vertices here), the goal to find an
is only something that produces outcome, not something
$f is monotone if for every A C B. we have f(A) & f(B). It is submodular if for every A, B we have that () & f(A) f(B).
7

---

action A E A _ {A C L: : |A| - =) k maximizing the expected number of influenced nodes R, where each node v E R can be independently influenced by with probability H(w..) i...
EVER( 11 ILEA:: (u.))E((1 Mia.e))) This problem can be applied to the semi-bandit framework called the ad placement problem, where L are the web pages, R are the users and (iu.,) is the probability that user clicks the ad on web page In this application, the user's click probabilities are unknown and must be learned the rounds progress. The Greedy oracle can provide an approximate solution with approximation ratio = 1 - 1/e [Nemhauser et al., 1978]. This setting fits REDUCE2EXACT as follows:
maximizing fA,
Oracle (1)) For E [b], let & - {(a1....,aa)) (a), (a1,..., Fi-1, LABr-1 and rı((a),.... ..... 0:), p)) _ f ((aa)...., H))
Oracley EE,.... Ex): Let (aI...., ax) a Eg. Oracloz returns A = faI...., ax]
Let A' {(1...................... } for some E [K] and by abuse of notation, let f f(', Informally, we see that in the above decomposition of the oracle, at each step, Oracle; maximizes f(AA) with A fixed, i.e., Oracle; optimizes only a; (we thus recover the greedy algorithm). It is precisely these sub-problems of finding a, that can be solved exactly. Then, we see that Oracle, simply returns the last A constructed. We will now prove the relation (3). The following is true using that f is monotone submodular (this is actually the way Nemhauser et al. [1978] proved the approximation guarantee, and is true for any monotone submodular function):
f(A*) f(A') &
Σ (f((a)uA5) f(A+t)) -(A-t))))) + ) - f(A))) "E
Once the above relation is obtained, we can actually continue the original proof from Nemhauser et al. [1978], skipping each step where we would need to use the property of Oracle,, thus leaving a term in the right-hand side for each time we skipped.
S(A*) f(1²) = s(A7) 1(1--1) - - s
-
- ((AA))-((A--))) 1 k
-
Σ
(((
... ..A))()) (1 1 (1-11
1
+ Σ
E (f((a)UAt)) f(A
k
k
iml
ARA
Finally, since (1 - )) S e_1 we get that A(Oracle (FI..... Ek)) = (1 - (-))) S(A) is bounded by
1111
k Σ
5) k
(
-K--441 (Bk
Note in passing that we recover the classical approximation if the right- hand-side was equal to 0. It is easy to see that the reward function ry satisfies Assumption 2 with B, = e/n)- We thus finally get our Assumption 4.
Online influence maximization (OIM) As the analysis mentioned above only uses submodularity, it can be extended to the problem of online influence maximization in social network. A social network is modeled as a directed graph G (V, with nodes V representing users and edges E representing connections. For a node E V, a subset A C V, and a vector x E (0, 1) F let the predicate A x i hold if, in the graph defined by Gx A (V, (ij E E, = 1}), there is forward path from a node in A to the node i. If holds, we say that is influenced by A under x. The goal to find an action A E A - (A (ACV: |A| = k} maximizing the influence spread where X ((),)) Beruoulli(A(..v)) This model called the independent cascude model [Kempe et al., 2003, 2015]. A notable property to use the greedy oracle is that a monotone submodular. As the exact calculation of a is prohibitive, is estimated by simulating the diffusion process, resulting in an approximation factor 1 e- E in the
(A, (A) 1E
A V
8

---

above greedy oracle analysis [Kempe et al.. 2015, Feige, 1998. Chen et al., 2010], with E >> 0. In OIM, arms may be probabilistically triggered, and Assumption holds with the constants being all (1(2)0))
equal to max NEW V, {u} can reach [Wang and Chen, 2017]. As previously, we thus get Assumption with Bj being Cin] times this constant.
which is the largest number of nodes any node
Metric k-center This example and the following ones are less common for CMAB, but allow to well illustrate REDUCE2EXACT. Given set of cities, one wants to build & warehouses in different cities and minimize the maximum distance of a city to a warchouse. Formally, given a complete undirected weighted graph G' EV) whose distances d(u,, U2) satisfy the triangle inequality, the goal is find an action A A - {A V |A| = k} that minimizes max d(u, A). We can consider the semi-bandit setting where the set of base arms is E, μ² - (d(v,, U;)) (n.n))) and (,))(,,)))
the feedback set includes the edges of the graph induced by the chosen action. We can target an approximation regret with = 1/2 using the following oracle (which is simply the standard greedy algorithm for this problem).
{(a Oracle: (pI) For E [k:], let & & {(a1 ........,... a.) (a1..... a.-1) E, E V\E and rı((a)..... a.), 14) f min Panay (with 11 0). One can notice we thus have E E arg max (o........ d(aii (0),).,,0;-1)) = arg max (a........ d(a;; Es-1).
Oraclez [E,,..., Eg) Let (a1....,ap) & Eg. Oraclez returns A {aI,.... .......).....)..)))..... Let w E arg m d(v, A).
We thus have:
1 max d(u, max d(u, max A(),
1
max d(u, A) VEY
min min d(a,a') aEAu(w) a' a'E
2
2
1
max
max d(u, A) d(a,+1, Eg) BEV
jE(k
1
$
max
max d(u, EE) - d(as+ı, E,)
2 jE(k-1 1]
max (ri+1 Fjj 11++:14)) - r (F(+1,
2 jE(k-1]
Where the first inequality is deduced as follows: the map v + arg = d(a", u) defines a partition of V into h = |A*| clusters. By the the pigeonhole principle, one cluster contains 2 different points a, a' E A U {w} (simply because its size is k + 1). We can assume a' E A without loss of generality. Thus, since M(a) = f(a',, we get d(a, a') S d(a, + d(a', f(a')) = d(a, A*) + d(a', A*) < 2 max.ev d(v, A*).
Vertex cover The problem consists, given an undirected graph G (V, E). in finding set of vertices with minimal cost to cover all the edges of E. Formally, with μz" E RY, the goal is to find an action A E A A (A CVCV V(u, v) E E, u E A or v E A} that minimizes ea,²". The semi-bandis feedback is defined directly as S = A. We can target an approximation regret with a = 1/2 using the following linear programming (LP) relaxation oracle.
Oracle (HI) Let & A {
x E 10,1/2,1)* 13 V(u E E, Du + x 2 1) and ri 11) 2
-x
Oraclez (Ei) Let A Er. Oraclez returns A (ue V : 2 2 1/2} E A (since A (u, v) E E, + Fy 2 1, so x. 2 1/2 or x, 2 1/2,, so A A). Let & E
We have:
2 00' - S 5''p" - e n²¹ Sx' - x" (B), ri (Ei, n²).
'The LP relaxation of vertex cover is half-integral, so that we can allow each variable to be in f0, 1/2, 1} rather than the interval from to 1.

---

Notice, satisfies Assumption 2 with the constants being 1, using x E 10, that x S e,.
Max-Cut Given an undirected weighted graph G = EV, with weights μ² _ (1 (UM))E
the goal is to find an action A E A á (A (Ac C 3 maximizing the total weight of the edges between A and its complement, i.e., 1 2 (u,))E oo (1 - yuye), where y - еλ ev We consider the semi-bandit context where E is the set of arms, and the feedback set includes the edges between A and its complement, i.e., S {(u, v) E, MuM/ - -11. To include randomization within the oracle, we can extend the action space A to the set of probability measures on {A C VJ. replacing ((A) by its expectation on A, function of the distribution of A. The polynomial-tin algorithm for Max-Cun with the best known approximation ratio [Goemans and Williamson, 1995] uses semidefinite programming and randomized rounding, and achieves an approximation ratio of x minogesa I-cos0 0.878. In context, it can be defined follows.
approximation
Oracle1(4) We define & - {(ua)uev E (v EVERY lIvll2 = =1"" and
rı((Vu)ueV: (t) - E(W)EE M(n,o) - v.)o).
Oracley (E1) Let (VulueV A E1. Oraclez returns the distribution of A {u V, v 2 0}, where Z a~ ~u((v ERV. =|v]|22= 1}).
The following proved by Goemans and Williamson [1995]:
1 sign( (v,, Z siigniiv...
Σ (u,))E
Σ
((,,))
2
(A.))EE
arccos Vo)
Σ
(u,e)E
Vive
Σ
ar ((vi(vv)
M(uee)
2
(a.v)EE
Thus, Pi satisfies Assumption with the constants being 1/a. We also get, with y - ex evia-
((Oacclo(E11)>
Σ ((n,o)
1 yove
E
Σ
1 1- sign(v (i)ggny)
2
(u,v)E
(a.u)E
I -mM(,
5
Conclusion
In this article, our main objective to further expand the "approximation regret scope" of the CTS policy. We not only expand it to probabilistically triggered arms (which was one of the open questions by Kong et al. [2021]). but we also consider broader class of oracles compatible with CTS. More precisely, we propose condition, REDUCE2EXACT, which may seem unnatural at first, but which in fact simply expresses that sub- broblerssems that can be solved exactly must be hidden in the original approximation problem, and that the approximation oracle exploit them to output the final solution. Knowing that the majority of approximation algorithms use one or more relaxations to an exact problem (e.g., solving convex programming relaxation to obtain a fractional solution and then rounding this fractional solution to get feasible solution), our assumption falls within the range of many CMAB-T settings. From this reduction, we naturally obtain the standard tight regret bound ([og(())Ammn)) This is the first tight bound for the approximation regret on non-exact oracles.
As future work, it may be interesting to explore other CMAB-T problems where the REDUCE2EXACT condition does (or doesn't 't) hold. We also think our setting should be generalizable to the budgeted regret setting without much difficulty (see Perrault et al. [2019b, 2020c.b] for examples with an approximation oracle). Finally, we have that the approximation regret is in some way conservative compared to the greedy regret. For a given oracle, we can easily consider the equivalent of the greedy regret for that oracle. An interesting investigation would then be to extend the work of Kong et al. [2021] in this direction, considering other types of oracle.
10

---

References
S. Agrawal and N. Goyal. Thompson Sampling for Contextual Bandits with Linear Payoffs. CoRR, abs/1209.3352, http://aratioonr/abb/22233333232 sep 2012. URL httpp::/aaax...oogaabb////////// 3352.
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235 2002.
D. A. Berry and B. Fristedt. Bandit Problems: Sequential Allocation of Experiments, volume 38 of Monographs statistics and applied probability. Chapman and Hall, 1985.
N. Assa-Bianci and G. Lugosi. Combinatorial bandits. In Journal of Computer and System Sciences, volume 78, pages 1404-1422, 2012.
S.-H. Chang, P. C. Cosman, and L.. B. Milstein. Chernoff-type typeeoffffttteooooo bounds for the gaussian error function. IEEE Transactions on Communications, (9(11):29992244 2011.
W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Knowledge Discovery and Data Mining, 2010.
W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 151-159, Atlanta, Georgia, USA, 2013. PMLR. URL http: httpt::p/ppoceeinngss. mlr pww.ppressseee.e /v88/ chen13a. html.
W. Chen, Y. Wang, and Yuan. Combinatorial multi-armed bandit and its extension to probabilisti- cally triggered arms. Journal Machine Learning Research, 17, 2016.
N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.
R. Combes, S. Talebi Mazraeh Shahi, A. Proutiere, and m. lelarge. Combinatorial bandits revisited. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2116-2124. Curran Associates, Inc., 2015. URL sttt:://paeet nips wwtps.cc/ppppeeee hccpppper/581-commineeeeeee
www.aaa-bbaanitteeiiiiiieeeeeeee .ddf.
R. Degenne and V. Perchet. Combinatorial semi-bandit with known covariance. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 2972-2980. Curran Associates, Inc., 2016. URL http: /ttp://papp....ee nips. cttpspercppp///ccceaeeee 11trr/1177---- www.7//oomiatttoiii....oooooo.. setttoorrrlsmmmmmi wwwsseemdiittiiiiieeeeeeeeeeeeee www.ithhh-wwo-ooooo covariance.e.ooooo .pff. -ow-tt----ooo--ooviaaneeeee
R. Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
U. Feige. A threshold of for approximating set cover. Journal of the ACM (JACM), 45(4): 634 652, 1998.
Y. Gai, B. Krishnamachari, and R. Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. Transactions on Networking. 20(5):1466 1478, 2012.
M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
A. Gopalan, S. Mannor, and Y. Mansour. Thompson sampling for complex bandit problems. In International Conference on Machine Learning, 2014.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
A. Huyuk and C. Tekin. Analysis of Thompson Sampling for combinatorial multi-armeds bandit with probabilisticaly triggered arms. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1322-1333 1330. PMLR, 2019.
I. M. Jacobs and Wozencraft. Principles of communication engineering. 1965.
M. Kakade, A. T. Kalai, and Ligett. Playing games with approximation algorithms. SIAM Journal on Computing, 39(3): 1088-11066 2009.

---

E. Kaufmann, N. Korda, and R. Munos. Thompson Sampling: An Asymptotically Optimal Finite Time Analysis. Algorithmic Learning Theory, 2012.
D. Kempe, J. Kleinberg, and Ê. Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. Theory of Computing, 11(4):105-14) 2015.
J. Komiyama, J. Honda, and H. Nakagawa. Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays. jun 2015, URL http: //axxiv. org/abs/ /106/ 00779.
Kong, Yang, W. Chen, and S. Li. The Hardness Analysis of Thompson Sampling for Combina- torial Semi-bandits with Greedy Oracle, 2021.
B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, 2015.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4 22, 1985.
O. Marchal, Arbel, et al. On the sub- tob--guusiianty of the beta and dirichlet distributions. Electronic Communications in Probability, 22, 2017.
G. L. Nemhauser, I.. A. Wolsey, and M. I.. Fisher. An analysis of approximations for maximizing submodular set functions-L. Mathematical Programming. 14(1):265-299 1978.
P. Perrault. Efficient Learning in Stochastic Combinatorial Semi-Bandits. Theses, Univeristé Paris- Saclay, Nov. 2020. URL https: //tp:l//eeeeeeeee http://tte.a.....eeeeeeeeeeseeee
archives coweesss-uveeeeese fr wtt.teeotoo0e2e.......
P. Perrault, V. Perchet, and M. Valko. Exploiting structure of uncertainty for efficient matroid semi- bandits. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5123-5132, Long Beach, California, USA, 2019a. PMLR. URL http::/pproceedingg mlr. Sttess/v97/perruull
html.
P. Perrault, V. Perchet, and M. Valko. Finding the bandit in a graph: Sequential search-and-stop In K. Chaudhuri and M. Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 1668-1677 PMLR, 2019b. URL. http: //proceedings... mlr trrees/v89/peraaaee
html.
Perrault, E. Boursier, V. Perchet, and M. Valko. Statistical Efficiency of Thompson Sampling for Combinatorial
arXiv preprint arXiv:2006.0mm 06616, 2020a.
Perrault, J. Healey, Z. Wen, and M. Valko. On the approximation relationship between optimizing ratio of submodular (rs) and difference of submodular (ds) functions, 2020b.
P. Perrault, J. Healey, Z. Wen, and M. Valko. Budgeted online influence maximization. In Proceedings of the 37th International Conference on Machine Learning, pages 5588-6599. 2020c.
Perrault, V. Perchet, and M. Valko. Covariance-adapting algorithm for semi-bandits with application to sparse rewards. In Conference Learning Theorr, 2020d.
H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematics Society, 58:527-535, 1952.
D. Russo and B. Van Roy. An information analysis of thompson sampling. The Journal of Machine Learning Research, 17(1)24442-4471, 2016.
M. Streeter and D. Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems, pages 1577-1584, 2009.
W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25:285-294, 1933.
Q. Wang and W. Chen. Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. In Neural Information Processing Systems, 2017. URL.
12

---

01610.
S. Wang and W. Chen. Thompson Sampling for Combinatorial Semi-Bandie Bandits. mar 2018. URL http:// //axiv//axvvvev wwwp:/oggggabb/aeeeee 04623.
Z. Wen, B. Kveton, and A. Ashkan, Efficient learning in large-scale combinatorial semi-handits. In International Conference on Machine Learning, pages 1113-1122. 2015.
Z. Wen, B. Kveton, and M. Valko, Influence maximization with report, 2016.
feedback. Technical
Z. Wen, B. Kveton, M. Valko, and S. Vaswani. Online influence maximization under independent cascade model with
feedback. In Neural Information Processing Systems, 2017.
R. Zhang and R. Combes, On the Suboptimality of Thompson Sampling in High Dimensions. arXiv preprint 00Iv:2202.005002, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Abstract and section 1.
(b) Did you describe the limitations your work? [Yes] See the paragraph "Other known limitations of CTS" and the second paragraph in section 5.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work does not have any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] See all sections in Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "cOD-w6mkoUW", "reviewer": "Reviewer_6J2J", "summary": "This work studies the behavior of the Combinatorial Thompson Sampling policy (CTS) for the probabilistically triggered arms extension of CMAB (CMAB-T). They propose a specific condition for the approximation oracle: REDUCE2EXACT based on the intuition of reduction, and show some problems using the approximation oracle such as the greedy oracle and the LP relaxation oracle which meet the REDUCE2EXACT assumption. This novel decomposition of the approximation oracle is helpful for the analysis of the approximation oracle by CTS. For example, when the reward function is monotone submodular and the oracle is the greedy oracle, it can avoid the \"mismatch\" phenomenon mentioned in the previous work and obtain a better regret upper bound. Under the REDUCE2EXACT assumption, this paper proves the first $O(\\text{log}(T)/\\Delta)$ approximate regret upper bound for CTS. In addition, this work also provides a counter-example for a deeper understanding of REDUCE2EXACT.", "questions": "Please also see the weakness part.\n\nIt seems that when the approximation oracle is greedy, the reward function must be monotone submodular. Can you give an example of the reward function without too many assumptions and meeting the REDUCE2EXACT assumption?\n\nSuggestion:\n\n1. The process will be clearer if useful notations are defined.\n\n2. It will be better if this work can describe the process of OIM meeting the REDUCE2EXACT assumption in detail. This will help readers understand how REDUCE2EXACT works under CMAB-T.\n", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This work is novel in the understanding and analysis of the approximation oracle, and is helpful for the analysis of CTS of the approximation oracle. Under REDUCE2EXACT assumption, this work proves a better regret upper bound compared with Kong et al. [2021].\n\n2. This work provides a counter-example for the REDUCE2EXACT assumption, which clearly describes the limitations of REDUCE2EXACT assumption.\n\nWeakness：\n\n1. I did not see too many difficulties in the regret analysis process of Theorem 1. It seems that the proof process of Theorem 1 is a reorganization of the proof processes of Huyuk and Tekin [2019], Perrault et al. [2020a] and Perrault [2020]. It is worth noting that this work does not describe the difficulties or non-trivial tricks of the proof after changing the CMAB setting to CMAB-T.\n\n2. This work is a follow-up work based on Kong et al. [2021], but in this work it is not described how they avoid the \"mismatch\" phenomenon mentioned in Kong et al. [2021]. This may confuse readers.\n\n3. The abuse of notation: In the appendix, there is the abuse of notation due to the need to cite other works. Specifically, there are some notations defined in other articles that are not defined in this work, such as $\\tau_j$, $Z^c$; and there are also some notations that I have not seen defined in the works they refer to, such as $ \\eta_{q,k}$.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Sgl4L3wOE34", "reviewer": "Reviewer_DcCA", "summary": "This paper concerns the performance of Thompson sampling for combinatorial semibandits with an imperfect \\alpha-approximate oracle for the underlying combinatorial optimization problem. It shows regret bounds compared to an alpha-approximation to optimality, under a structural assumption on this oracle which is satisfied for e.g. greedy algorithms for submodular objectives.", "questions": "Major comments:\n\n\n1. I found the setup regarding \\mu very confusing. At the start of page 2, when \\mu is used for the first time, it would be helpful to explain that it is just a model parameter. Later at the top of page 4, it was unclear to me why \\mu should be n-dimensional for n the number of arms. In fact if I understand correctly, this is not the case for the first PMC example later in the paper (I believe there, \\mu is indexed by edges of a graph while arms are indexed by vertices). This might affect Assumption 2 which as stated requires \\mu to be n-dimensional.\n\n\n2. Why is 1/\\Delta_{i,min} a reasonable parameter for regret to depend on? I would typically expect it to be exponentially large in n, e.g. for a random choice of \\alpha. If it is possible to have a sqrt(T) type regret bound I would find it much more convincing.\n\n\n\nMinor comments:\n\n\n1. In the Contributions paragraph, it could be made clearer that the condition on Oracle is structural and applies to greedy algorithms for submodular optimization. Otherwise, it sounds like maybe this condition is \"exogenous\" and only holds in extremely specific cases, or that the assumption amounts to bounding some problem-dependent parameter. Basically, I found the result more interesting than I expected to from the introduction!\n\nAlso in this paragraph, I would reference Theorem 2 and the following examples when appropriate so the claims are not just flying around in this paragraph.\n\n2. I believe this paper is targetting frequentist regret for TS, but it could be made clearer since often TS is analyzed with Bayesian regret.\n\n\n3. The setup at the start of section 2 is confusing in several ways. \"A_t\\in\\mathcal F_t\" does not make sense to me, I imagine the intended meaning is that A_t is \\mathcal F_t measurable. \n\n\n4. Line 141: \"assumptions are often made struck me as an unconvincing justification.\n\n5. Line 146: please define p_i outside of this assumption.\n\n6. Definition 2: please use way more lines here. It is pretty miserable to read this as currently formatted.\n\n\nIn fact, in the later examples, more space around the definitions of Oracle_1 and Oracle_2 would be highly appreciated as well.\n\n\n7. \"Exact subproblem\" was confusing to me. I think what is intended is that some sub-optimization-problem is solved exactly. I would just write this out in more words. Similarly, I found \"exact sub-regrets\" a confusing terminology. In some areas of math, \"exact\" is a serious technical term!\n\nAlso the first paragraph of Section 4 didn't make sense to me. Perhaps it could be clarified, I'm not sure.\n\n\n8. It seems to be that \"Assumption 4\" should usually say \"Assumption 4 with parameter vector c\". It is confusing as written because c does not appear in Assumption 4 until Oracle_2, but c does appear in e.g. the statement of Theorem 2. I would introduce c at the start of Assumption 4.\n\n\nActually in general, Assumption 4 felt frustrating to read. For example, when I read the definition of Oracle_1, I first see \"There are \\ell reward functions (r_j)_{j\\in[\\ell]}.\" At this point, I have no idea what spaces r_j are defined on, what their codomains are, etc. Mathematical definitions should never work this way. (Also at the end of the definition, it is still unclear what the codomain of r_j is...). I would say something more like:\n\n\"Oracle_1(\\mu) must output a sequence (E_1,...,E_{\\ell]) described as follows. For each j\\in [\\ell], let \\mathcal E_j=\\mathcal E_j(E_1,\\dots,E_{j-1}) be a finite subaction space which may depend on E_1,...,E_{j-1}. Then we require that E_j\\in \\arg\\max_{E\\in\\mathcal E_j} r_j(E,\\mu).\n\nInformally, Oracle_1(\\mu) exactly solves a finite sequence of recursively defined optimization subproblems. Note that the subproblems may have multiple optimal solutions, so Oracle_1(\\mu) may output many values for each given \\mu.\"\n\n\n9. In line 226, it is unclear where the definition of Oracle_2 ends.\n\n10. Many minor grammatical issues especially around singular/plural. I am not taking this much into account for my score since the authors might not be native English speakers, but it would improve readability to fix them. E.g.:\n\n\t- Line 134: \"outcomes\" -> \"outcome\"\n\n\t- Line 135-136: A, D_{trig}, r don't seem to be \"quantities\", which should refer to actual numbers.\n\n\t- Line 202: \"Assumptions\" -> \"Assumption\", \"have\" -> \"has\".\n\n\n11. For many of the references, \"thompson sampling\" is in lower case when it should not be. Use double brackets {{ }} around the title in the bibtex to fix this.\n", "limitations": "--", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The technical content of this paper looks nice and possibly accept worthy. The authors show that for combinatorial optimization problems with natural structure, Thompson sampling does achieve good approximation regret, even though counterexamples without this structure do exist. I found the result illuminating and creative (though I haven't thought about this issue in the past). I do have some qualms about the notion of gap that is used for regret as it seems potentially exponentially small (mentioned below in the questions section).\n\nHowever I think the writing is really quite confusing in many places, which is the main reason for my low score. I understand that the page limit is rather stringent, so my high-level suggestion for the authors in the future would be to move some later content (e.g. examples and the TSP counterexample) to the appendix to make space for proper exposition. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5TaHipOkxER", "reviewer": "Reviewer_aZHQ", "summary": "This paper studies the combinatorial Thompson sampling (CTS) algorithm for CMAB-T with approximate oracles. They first show that CTS can achieve O(log T/\\Delta) regret for CMAB-T problem with exact oracles. As for the general approximate oracle, they introduce an assumption and show that once the assumption holds, the alpha-approximate regret can be decomposed by the sum of several exact regrets. And thus the upper bound for the \\alpha-approximate regret can be derived. This is also the first guarantee for alpha-approximate regret of the CTS algorithm. ", "questions": "Please see above weakness. ", "limitations": "The work is about online learning theory and does not have negative societal impact.  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \nThis paper makes progress on the open question that whether the CTS algorithm can achieve sub-linear alpha-approximate regret guarantee. By establishing an assumption which is satisfied in common applications, they show that the alpha-approximate regret can be decomposed as the sum of several exact regrets. And these exact regrets can be simply upper bounded. \nThey find several examples such as greedy and LP that satisfy the proposed assumption.  \nWeakness:\nIn fact, the constant term in current regret upper bound has an additional 1/p* term, where p* can be exponentially small since the triggering probability can be small. It seems that such a term appears mainly due to the Lipschitz condition without using the TPM condition. So I want to ask that would it possible to avoid the 1/p* term in the regret? \nThe authors should also compare the derived regret upper bound with the upper bound for CUCB. \nThe presentation is not easy to follow, especially for the description of Assumption 4 and the analysis of PMC. I think more explanations are required for better understanding. \n\nTypo:\nLine 192: depends -> depend\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1U3F0pWthJK", "reviewer": "Reviewer_4G2X", "summary": "The authors study stochastic combinatorial Thompson Sampling (CTS), with semi-bandit feedback in a setting where exactly solving the corresponding offline optimization problem is not feasible. While existing work provided approximation regret analysis of CTS for the greedy oracle, the proposed work provides a regret upper bound for CTS, obtained under a specific condition on the approximation oracle. The authors present various examples where the specific conditions are satisfied and counter-examples. \n\nThe paper identifies assumptions (mainly 2 and 4) under which the problem becomes exact with O(log T/\\Delta).  Contribution is more on identifying these assumptions than the associated regret analysis.", "questions": "Is Assumption 2 verifiable?", "limitations": "yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper identifies assumptions (mainly 2 and 4) under which the problem becomes exact with O(log T/\\Delta).  \n\nWeakness:\n\nSince the condition reduces to the exact oracle, I am not sure whether it is correct to say that it is the first  O(log T/\\Delta) approximation regret.\n\nWriting style can be improved.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept