Incentivizing Combinatorial Bandit Exploration
Authors: Xinyan Hu
Dung Daniel Ngo
Aleksandrs Slivkins
Steven Wu
Venue: NeurIPS 2022 Accept (2022)
Keywords: incentivized exploration
multi-armed bandits
combinatorial semi-bandits
Thompson Sampling
Bayesian incentive-compatibility

Abstract: Consider a bandit algorithm that recommends actions to self-interested users in a recommendation system. The users are free to choose other actions and need to be incentivized to follow the algorithm's recommendations. While the users prefer to exploit, the algorithm can incentivize them to explore by leveraging the information collected from the previous users. All published work on this problem, known as incentivized exploration, focuses on small, unstructured action sets and mainly targets the case when the users' beliefs are independent across actions. However, realistic exploration problems often feature large, structured action sets and highly correlated beliefs. We focus on a paradigmatic exploration problem with structure: combinatorial semi-bandits. We prove that Thompson Sampling, when applied to combinatorial semi-bandits, is incentive-compatible when initialized with a sufficient number of samples of each arm (where this number is determined in advance by the Bayesian prior). Moreover, we design incentive-compatible algorithms for collecting the initial samples.


Incentivizing Combinatorial Bandit Exploration
Xinyan Hu', Dung Daniel Ngo?, Aleksandrs Slivkins and Zhiwei Steven Wut
University of California, Berkeley. Email: xinyanhu @ berkeley.edu
University of Minnesota. Email: ngo00054 @ umn.edu
Miiroooft Research NYC. Email: slivkins @ microsoft.com "Careggi Mellon University. Email: zstevenwu @ cmu.edu
Abstract
Consider bandit algorithm that recommends actions to self-interester users in a recommendation system. The users are free to choose other actions and need be incentivized to follow the algorithm's recommendations. While the users prefer to exploit, the algorithm can incentivize them to explore by leveraging the information collected from the previous users. All published work on this problem, known as incentivized exploration, focuses on small, unstructured action sets and mainly targets the case when the users' beliefs are independent across actions. However, realistic exploration problems often feature large, structured action sets and highly correlated beliefs. We focus on paradigmatic exploration problem with structure: combinatorial semi-bandits. We prove that Thompson Sampling, when applied to combinatorial with sufficient number of samples of each arm (where this number is determined in advance by the Bayesian prior). Moreover, we design incentive-compattble algorithms for collecting the initial samples.
mani-bandits, is mncentivecoompatbbee when initialized
Introduction
We consider incentivized exploration: how to incentivize self-interested users to explore. A social planner interacts with self-interested users (henceforth, agents) and make recommendations but cannot enforce the agents to comply with these recommendations. The agents face uncertainty about the available alternatives. The social planner would like the agents to trade off exploration for the sake of acquiring new information and exploitation, making optimal near-term decisions based on the current information. The agents, on the other hand, prefer to exploit. However, the algorithm can incentivize them to explore by leveraging the information collected from the previous users. This problem has been studied since Kremer al. (2014), see (llikkins (2019) Ch. 11) for an overview.
The basic model of incentivized exploration is very stylized and can be extended along two "dimen- sion": more sophisticated economic models for agents' behavior and incentives, and more complex machine-learning models for actions' structures and rewards. All published work has only dealt with the former, whereas we pursue the latter. In particular, all published work focuses on small, unstructured action sets. Moreover, the case of independent priors when the users' beliefs are independent across actions emphasized as the main. paradigmatic special case when specific performance guarantees are derived. However, realistic exploration problems often feature large sets with some known structure that connects actions to one another. A major recurring theme the vast literature on algorithm to cope with the large number actions.
bandits is taking advantage of the available structure so as to enable the
Reseearch done while X.Hu was an undergraduate student at Peking University and a (virtual) visiting student at Carnegie Mellon University.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We focus on paradigmatic, well-studied exploration problem with structured actions: combinatorial semi-bandin Here, each arm is subset of some ground set, whose elements are called atoms. In each round, the algorithm chooses an arm, and observes/collects reward for each atom in this arm. The reward for each atom is drawn independently from some fixed (but unknown) distribution specific to this atom. The set of feasible arms reflects the structure of the problem, e.g., it can comprise all subsets of atoms of a given cardinality, or all edge-paths in a given graph. Since the number of arms (K) can be exponential in the number of atoms (d), the main theme is replacing the dependence on K in regret bounds for "unstructured" K Kaareed bandits with a similar dependence on d.
We adopt a standard model for incentivized exploration from Kremer et al. (2014). The social planner implemented as a bandit algorithm. Each round corresponds to a new agent which arrives and receives the arm chosen by the algorithm as a recommendation. Agents have Bayesian beliefs, independent across the atoms (but highly correlated across the arms). The algorithm must ensure that following its recommendation is in each agent's best interest, a condition called Bayesian incentive- compatibility (BIC). Each agent does not observe what happened with the previous agents, but the algorithm does. This information asymmetry is crucial for creating incentives.
Our contributions. We prove that Thompson Sampling BIC when initialized with at least Thrs samples of each atom, where Ars is determined by the prior and scales polynomially in the number of atoms (d). Thompson Sampling [Thompson] [933) well-know bandit algorithm with near- optimal regret bounds and good empirical performance. The initial samples can be provided by another BIC algorithm (more on this below). or procured exogenously, e.g., bought with money.
Next, we consider the problem of initial exploration: essentially, design a BIC algorithm that samples each atom least once. Such algorithms interesting in their own right, and can be used to bootstrap Thompson Sampling, as per above. We present two such algorithms, which build on prior work (Mansour al. 2020 Simchowitz and Slivkins 202T and extend in non-trivial ways. The objective to be optimized is the sufficient number of rounds To. and particularly its dependence on d. To calibrate, prior work on incentivized exploration in multi-armed bandits with correlated priors does not provide any guarantees for super-constant number of arms (K), and is known to have To > exp ((p()))) in some natural examples (Mansour et al. 2020). In contrast, our algorithms satisfy To S exp(O(d)) for paradigmatic special case, and To exp(O(d))) in general.
Finally, what if the prior is not independent across atoms? We foeus correlation, a fundamental special case of incentivized exploration, and prove that our analysis of Thompson Sampling extends to the case. This result may be of independent interest.
arms with arbitrary
Discussion. Like all prior work on incentivized exploration, we consider standard, yet idealized models for agents' economic behavior and the machine-learning problem being solved by the social planner. The modeling captures something essential about exploration and incentives in recommenda- tion systems, but is not supposed to capture all the particularities of any specific application scenario. The goal of this paper is to bring more complexity into the machine- machine-learning problem; advancing the economic model is beyond our scope.
We focus on establishing the BIC property and asymptotic guarantees in terms of the number of atoms, without attempting to optimize the dependence on the per-atom Bayesian priors. Our Thompson Sampling result has an encouraging practical implication: a standard, well-performing bandit algorithm plays well with users' incentives, provided small (in theory) amount of initial data.
(Stylized) motivating examples of incentivized exploration in combinatorial semi-bandits include: recommending online content, e.g., for news or entertainment (with atoms as e.g., specific news articles); recommending complementary products, e.g., a suit that consists of multiple items of clothing; recommending driving directions; see Appendix A for more details. In all examples, the social planner corresponds to the online platform issuing the respective recommendations. Such online platforms are often interested in maximizing users' happiness, rather than (or in addition to) the immediate revenue, as way to ensure user engagement and long-term success.
Related work. Incentivized exploration, as defined in this paper, has been introduced in Kremer et al. (2014) and subsequently studied, e.g., in Mansour et al. (220 2022]; Immorlica et al. (2020): Bahar et al. (2016 2019), along with some extensions. Most related is Sellke and Slivkins 2021 which
obtains similar BIC results for the special case of multi-
bandits with independent priors, both
for Thompson Sampling and for initial exploration. A yet unpublished working paper of Siichhoitzz
and Slivkins (202l) provides a BIC algorithm for initial exploration in reinforcement learning; we
2

---

build on this result in one of ours. Similar, but technically incomparable versions have been studied. e.g. with time-discounted rewards (Bimpikis al. 2018 and creating incentives via money (Frazier
et al. 2014, Chen et al., 2018) Db.
From the perspective of theoretical economics, incentivized exploration is related the literature on information design (Kamenical 2019 Bergemann and Morris, 2019): essentially, one round of incentivized exploration an instance of Bayesian persuasion, central model in this literature. Other "online" " models of Bayesian persuasion have been studied (e.g,, Castiglioni et al. 2020 Zu et al. 202I). but are very different from ours that the planner's 's private signal is drawn IID in each round (whereas in our model it is the algorithm's 's history); the problem has nothing to do with exploration, and is not even meaningful without incentives.
On the machine learning side, this paper is related to the work on combinatorial semi-bandits, starting from György et al. (0077) e-g., (Chen et al.. 2013 Kveton al. 2015 2014), and the work on Thompson Sampling, see Russo et al. (2018) for a survey. In particular, near-optimal Bayesian regret bounds have been derived in Russo and Van Roy (2014, 2016), and frequentist ones in (Agrawal and Goyal 2017 Kaufmann et al. (012). Thompson Sampling has been applied to combinatorial
semi-bandits, (e.g., Gooalan et 2014 Wen et al.
2015 Degenne and Perchet 2016 Wang and
Chen 2018). with Bayesian regret bounds derived in Russo and Van Roy (2016).
2 Problem Formulation and Preliminaries
Our algorithm operates according to the standard protocol for combinatorial semi-bandits, with an ancillary incentive- coepaiie-oompaaibiiity constraint, standard in the literature on incentivized exploration.
Combinatorial semi-bandits. There are T rounds, d atoms and K arms, where each arm is a subset of atoms. The set A of feasible arms is fixed and known. In each round I,, each atom generates reward ( E [0, 1J. The algorithm chooses arm A E A and observes the reward of each atom in this arm (and nothing else). Algorithm's 's reward in this round is the total reward of these atoms.
T for the set of all rounds and [d] for the set of all atoms, so that arms are subsets A C [d]. Let de be the expected reward of atom & E [d], and let p(A) Eee 0g be the expected reward of given arm A
Formally, we write [T] := {1,
[d]. Note that d-armed bandits are special case when the feasible arms are singleton sets {(), f E [d].
Stochastic rewards and Bayesian priors. The reward of each atom 8 E [0, 1] is drawn independently in each round from a fixed distribution De specific to this atom. This distribution comes from a parametric family, parameterized by the expected reward 6.. The (realized) problem instance is therefore specified by the mean reward vector 0 = (01.
O2). Initially, each 6e is drawn independently from a Bayesian prior Pr with support è C [0, 1]. Put differently, the mean reward vector 0 is drawn from the product prior P = Pi x ... x Pa-
The algorithm must ensure that in each round f, conditional on a particular arm A = At being chosen, the expected reward of this arm is at least as good as that of any other arm. Formally, the algorithm is called Bayesian ancentive-coppatinnn
incentive-oompatibiliy..
(BIC) if for each round E [T],
E[ ((A) ((A') A A|20 O V arrms A, A' E A with P[A()) = A]> > O.
(1)
This definition is based on the following stylized story In each round t, a new user arrives to a recommendation system, observes the arm A()) chosen by our algorithm, and interprets it as a recommendation. Then the user decides which arm to choose (not necessarily the arm recommended), and receives the corresponding reward. Accordingly, the user needs to be incentivized to follow the recommendation. We adopt a standard setup from economic theory (and the prior work on incentivized exploration): each user has the same prior P. knows the algorithm, and wishes to maximize her expected reward. We posit that the user does not observe anything else before making her decision, other than the recommended arm. In particular, she does not observe anything about the previous rounds. Then, [ ensures that she is (weakly) incentivized to follow her recommendation. assuming that the previous users followed theirs. We posit that under (I). the user does follow recommendations, and then reports the rewards of all atoms the algorithm.
We emphasize that this story is not a part of our formal model (although it can be expressed as such needed). In fact, the story can be extended to allow the algorithm to reveal an arbitrary "message"
3

---

to each user, but this additional power is useless: essentially, anything that can be achieved with arbitrary messages can also be achieved with arm recommendations. This can easily be proved as a version of Myerson's s direct revelation principle from theoretical economics.
Conventions. Each atom satisfies P 0] 0: else, its rewards all 0, so it can be ignored.
No arm is contained in any the other arm. This is w.l.o.g. for Bernoulli rewards, and more generally P[r = 0 0g > 0] > 0: if A C A' for arms A, A' then A cannot be chosen by any BIC algorithm.
W.l.o.g,, order the atoms by their prior mean rewards 09 == E[Oe]. so that E[ 2 ... B[()) Let A arg max AcA (A) denote the best arm overall, with some fixed tie- heebbrekiig rule.
By slight abuse of notation, each arm A C [d] is sometimes identified with binary vector E 10" such that Uy + e A, for each atom & E [d]. In particular, we write A Eg..
Thompson Sampling has very simple definition, generic to many versions of multi-armed bandits. Let F, denote the realized history (tuples of chosen actions and realized rewards of all atoms) up to and not including round L. Write E() [.] = E Fi. and p(t)) [.] PP] P[- F, as shorthand for posterior updates. Thompson Sampling a given round I. draws an arm independently at random from distribution (A) = [ = A). A E A. If Thompson Sampling is started from some fixed round to > 1, this is tantamount to starting the algorithm from round 1, but with prior P(: Ft,)) rather than P. The algorithm is well-defined for an arbitrary prior P.
While this paper is not concerned with computational issues, they are as follows. The posterior update P(- | FF) can be performed for each atom l separately: Ppl( Fi,e), where Fi,e is the corresponding history of samples from this atom. A standard implementation draws 02 E [0, 1] independently from Pe(- Fr,e), for each atom l, then chooses the best arm according to these draws: arg max LiEA A 8/. The posterior updates P.(- Fe,e) and the arg max choice are not computationally efficient in general, and may require heuristics (this is a common situation for all variants of Thompson Sampling). A paradigmatic special case is Beta priors Pe and Bernoulli reward distributions De, so that the posterior update Pe(- Fi,e) is another Beta prior.
Composition of BIC algorithms. We rely on generic observation from Mansour et al. 2020 2022 that the composition of two BIC algorithms also BIC.
Lemma 2.1. Let ALG be a BIC algorithm which stops after some round To. Let ALG' ALG be another algorithm that initially inputs the history H collecied by ALG, and suppose it is BIC. Consider the composite algorithm: ALG followed by (H). which stops at the time horizon T. If To is determined before the composite algorithm starts, then this algorithm is BIC.
3 Thompson Sampling is BIC
Our main result is that Thompson Sampling is BIC when initialized with at least Thys samples each atom, where nis is determined by the prior and scales polynomially in d, the number of atoms.
Theorem 3.1. Let ALG be any BIC algorithm such that by some time To S T (determined by the prior) it almost surely collects at least This = Crs d² -ess Log((0s)) samples from each atom, where
CTS
min ([(((A) ((A))+ and 87s = min P(A" = A), A.A'EA
(2)
AEA
and CTs is large enough absolute constant. Consider the composite algorithm which runs ALG for the first To rounds, followed by Thompson sampling. This algorithm is BIC.
Note that To and Tiis are "constants" once the prior is fixed, in the sense that they do not depend on the time horizon T, the mean reward vector 6, or the rewards in the data collected by ALG.
Remark 3.2. For statistical guarantees, consider Bayesian regret, i.e., regret in expectation over the Bayesian prior. Bayesian regret of the composite algorithm in Theorem 3.1 is most Tp plus Bayesian regret of Thompson Sampling. The latter is D(VdTloo log d) for any prior (Russo and Van Roy 20166. For an end-to-end result, we provide a suitable ALG Section 4.1 with a specific To
Remark 3.3. We can invoke Lemma 2.1 since To is determined advance. So, it suffices to show that each round t of Thompson Sampling satisfies the BIC condition (

---

Let us clarify the dependence on d. Note that parameters érs and ôrs may depend on d through the prior. To separate the dependence on d from that on the prior, we posit that each per-atom prior Pa belongs to fixed collection C. We make mild non-degeneracy assumptions
IP (I((A') < [[]())]] > 0
for all arms A o A'.
(3)
P > > >|>0
for all atoms & [d] and some (0,
(4)
P(d,- < x) > poly(1/2) exp(exx
for all atoms e E [d], x E (0, 1/2) and some a 2 0.
(5)
Corollary 3.4. Suppose all priors Pi of atoms é E [d] belong to some fixed, finite collection C of priors and assumptions 3 are satisfied with some absolute constants a, Then Ths Ocld log d). where Og hides the absolute constants and the dependency on C.
Remark 3.5. The initial data can also be provided to Thompson Sampling exogenously (rather than via BIC algorithm ALG), e.g., purchased with money. More formally, one would need to provide collection of (arm, atoms' rewards) datapoints such that each atom is sampled at least Thys times f
Proof Sketch for Theorem 3.7 (full proof in Appendix B In order to establish the BIC condition in ①1 for Thompson Sampling, we first observe that PIA- = A] is a positive prior-dependent constant for all arms A, it suffices to prove E
[T (m(A) =(A')] [(A 2 for all A, A'.
Next, to show a lower bound on E (u((A) - ((A')) [イ ]. we will leverage the Harris inequal- ity Theorem D.2 which says increasing functions of independent random variables are nengtegatyvely correlated. Observe that the functions (m(A) p((4))+ and (A*=A} are co-monotone in each coordinate of 0 (i.e., either both increasing both decreasing in coordinate). Then, the mixed- monotonicity Harris inequality (see Theorem D.2) implies that:
E (u(A) p(A')) [(A-=A) where 5A P(A" A) N लrs-
(a((A) p(A))+ 1, GTS dA
(6)
To finish the proof, we show the expected absolute difference between E(a) (u(A)) (AA')] - ((1-
and (u(A) ((A')) 1 ((A==A) is upper bounded by érs 6A. By regrouping and using triangle
inequality as well |ar [AA=A) = |a|| =A== we can upper bound this estimation error by sum of E (E() [u(A)]] - [A) 1[4-=A} and E [E( [ 1 [AA==)) apply Bayesian Chernoff (see Lemma D. and observe that these two terms are "17s 1/21/2 times SuuG-aaaaan random variables. By the sub-Gaussian tail bound (see Lemma D.4. we upper bound both terms by O 1/2 5 /log(/))))
Since
the mean reward of each atom can be estimated by their empirical average,
We conclude by using our choices of Mts and observing that 6Ts S 8
To derive the dependence of reys on d, we investigate how the prior-dependent constants érs and ôTS depends on d. First, we can let eg be version of (rs where the min is taken over all ordered pairs of priors in C. Since C is finite and satisfies the pairwise non-dominance assumption
Proof Sketch for Corollary 3.4 (full proof in Appendix By.
CTs cc 0.
By definition, 87s = min PAA" = A] is the minimum probability that arm A is the best arm overall. Fix an arm A. We observe that the event where arm A is the best arm is more likely than the event where each atom in is larger than т, and all other atoms not in A is smaller than 1/d. Hence, we can lower bound IP = A] by E [1(2EE..02T]] 1 [(vgg A,9, ///44/ Since the prior P is independent across atoms, we can write the expression above as product of E [1veE4.0) and
E [1 A, ST/4]] s//4) As the values (0e bejd are independent and co-monotone in each in coordinate of 0, repeated application of moxeddmoontonicityy Harris inequality (see Remark D.3) implies that:
PIA" A] > II E 1 [m2n]
II E [1 [[c05v]]]
II p(0 2 r| II P $ 7/d] EEA
EEA
a
d II
P P(0 < 7/4
FFrr the special case of d-armed bandits, assumption is necessary and sufficient for the respective arm A be explorable: chosen in some round by some BIC algorithm (Selike and Slivkins 2021). "A subtlety: the number of samples of each arm should be known in advance. This is because otherwise Bayesian update this data may become dependent on the data-collection algorithm.
5

---

By full support assumption +. we define prior-dependent constant p, = me 2 0.
Then, by definition of Pr and the non-degeneracy assumption ( the expression above is lower bounded by 1 -poly (d (r1*) exp(-d(r/a) -)) Plugging this bound into nrs, we obtain Rrs Oc logd).
3.1 The two-arm case with arbitrary correlation
What if the prior is not independent across atoms? Our analysis extends to the case of K = 2 arms A, A' with arbitrary correlation between the atoms. In fact, we do not assume combinatorial semi-bandit structure, and instead focus on the fundamental special case of incentivized exploration: when one has two arms A, A' with arbitrary joint prior on (μ(A), p(A'))
Theorem 3.6. The assertion in Theorem 3.7 holds for the when one has two arms A, A' and an arbitrary joint prior on (p(A) (u)A), (-)
This result completes our understanding of incentivized exploration with two correlated arms: indeed, a necessary and sufficient condition (and the algorithm) are known for collecting the initial data Mansourr et al. 2020 A similar result for two independent arms is in (Sellke and Slivkins 2021)
The analysis is very similar to that of Theorem 3.1 and omitted. Unfortunately, our technique does not appear to extend to larger number of arbitrarily correlated arms.
4 BIC algorithms for initial exploration
We present two BIC algorithms for initial exploration, where the objective is to sample each atom at least once (i.e., choose arms whose union is [d]) and complete in No rounds for some No determined by the prior. Such algorithms are interesting in their own right, and can be used to bootstrap Thompson Sampling as per Theorem 3. (To collect n samples of each arm, repeat the algorithm times.) Both algorithms complete in the number of rounds that is exponential in poly(d). The first algorithm completes in exp(Op(d) (d)))) rounds, but is restricted to arms of the same size and Beta-Bernoulli priors. We obtain exp(Opl (df)) for arbitrary sets of arms. The second algorithm sidesteps the Beta- Beta-Bernoulli restriction, but completes in exp(Op (d rounds.
4.1 Reduction to K-armed bandits
The first algorithm builds a substantial "super-structure" on top of the "hidden exploration" " paradigm from Mansour al. (2020) The latter paradigm is defined for K-armed bandits and is proved to work for arms with independent priors, ordered by their prior mean rewards. However, for combinatorial semi-bandits, the arms' priors are highly correlated. We provide a new interpretation of their analysis in terms of exploring generic sequence of arms that satisfies a certain property (P). Our technical contribution is construct sequence of arms and prove that it satisfies Property (P). Note that suffices to explore sequence of arms which collectively cover all the atoms.
Throughout this subsection, we make the following assumptions:
the prior Pe for each atom L is Beta distribution with parameters (az, Be): the reward distributions Dj are Bernoulli distributions.
(7)
(8)
This is paradigmatic special case for Thompson Sampling (and Bayesian inference in general).
Let ve(n)= at / (at 3e + n)). n 2 0 be the posterior mean reward of atom when conditioned on n samples of this atom such that each of these samples returns reward 0.
Given any number n E N, let us define a sequence of s(n) I arms VI".... V k(n) E A. Let Vi be a prior-best arm: any arm with the largest prior mean reward. The subsequent arms are defined inductively. Essentially, we pretend that each atom in each arm in the sequence so far has been sampled exactly times and received each time it has been sampled. The next arm is defined the posterior-bess arm: an arm with largest posterior reward after seing these samples. Formally, for each 2 2, we define arm V."" given the previous arms V/"
V For each atom l [d] define
'Equivalenlly we have d = 2 atoms with an arbitrary joint prior on (0,, 0z). and the feasible arms are the two singleton arms (1) and (2).

---

(c) if this atom is contained in one of the previous arms in the sequence, and set (e) = 0 otherwise. Then, define V as the posterior best arm if the posterior mean rewards for atoms / given by (e) ). That is:
V E arg max AEA
Σ ve (0)( BEA
The sequence stops when the arms therein cover all atoms at least once, and continues infinitely otherwise; this defines x(n).
To state Property (P), we focus on this sequence for a particular, prior-dependent choice n.
(P)
There exist numbers up N and TP,PP E (0, 1), determined by the prior P, which satisfy the following. Focus on the sequence of arms V1,
Vx where k: k(Up) and Vi V, for each i [N]. Let H i E [K] be dataset that consists of exactly N E N samples each arm V1
Vs, where each sample contains the reward for each atom in the respective arm, and H is an empty dataset. Then
P X
2 Pp
Vi [x] and N 2 np,
(10)
where the random variable X:" is defined as
X
min
E [[a(V) - (((A) m A
In intuition, any given arm Vi can be the posterior best arm with margin and probability at least Pp after seeing at least np samples of the previous arms V1, Vi-1.
Given Property (P), prior work guarantees the following (without relying on assumptions
Theorem 4.1 (Mansour et al. (2200).. Assume Property (P) holds with constants Tp, Pp and = x(np). Then there exists a BIC algorithm which explores each arm Vi.... .Vx at least nop times and completes in To rounds, where To np (1 + d) / (TP pp).
Next, we establish (P). First we state a result for a paradigmatic case when all arms have the same cardinality, then relax it in what follows (with a somewhat weaker guarantee).
Theorem 4.2. Assume Mata-Benouulli priors
Further, assume that
The arms are all subsets of [d] of a given size m.
(11)
Then Property (P) holds with k((p)) [d/m]] and
np [.a/aak max [av]]
(12)
EE[4]
TP atoms E min (0,
(ue(n) up (n'))
(13)
pp (1 - d
(14)
as long as Tp and Pp are strictly positive.
Proof Sketch. For each arm V,, i E [K]] we consider the event that the dataset H. from Property (P) contains the reward of for each samples of each atom. We take to be large enough so that this event makes all arms Vi Vz-1 look inferior to V,, in terms the posterior mean reward. The key is to lower-bound the probability of this event; non-trivial step here requires Harris inequality.
We show that To, the requisite number rounds, depends exponentially on the number of atoms d. To this end, define suitable parameterization of the priors. To handle Tp in Theorem 4 posit a lower bound that depends on d, but this dependence is very mild.
In Theorem 4.2 and Theorem 4.4 upper-bound r<rr)) for some prior-dependent nP.
7

---

Corollary 4.3. Assume priors 7 g and that ①1 holds. Fix some absolute constants
co N and e, d (0, 1). Suppose [ < for all atoms, and the priors satisfy the following non-degeneracy conditions:
max E
[Beeae] [aoe S Co.
min E co)
(ue(n) ue (n')l Si(=a))
Then there exists BIC algorithm which samples each atom least once and completes in
No O (co d Φd)
rounds, where +
d) -o constant.
Finally, we handle general feasible sets, ie., without assumption 11 weaker, in that we have d in the exponent rather than d.
The guarantee becomes slightly
Theorem 4.4. Assume Beta-Bernoulli priors
g
Then Property (P) holds with k(np) S and
np [(aa + Ba)/oal
max
[ael d
(15)
EE [d]
Tp (U,
min
Σ
Eu((ne) Σ (e(e))
(16)
BEA
MEA
PP = (1- (1-69) d0)
(17)
as long as Tp and pp are strictly positive.
Corollary 4.5. Assume Reta-Bernoull priors 8 Fix some absolute constants C1 N and
02, E (0, 1). Suppose E [0e] S C3 for all atoms, and the priors satisfy the following non- degeneracy conditions:
max [lace + Be)/aal for sa atoms (.
min Ane
Σ ve(ne) -
Σ
Dy (n()))
2 20
(18)
EEA
PEA
Then there exists BIC algorithm which samples each atom least once and completes in
No = 000(c c0((u d² odd
rounds, where +
-c is constant.
In Appendix C.4 we provide some motivation for why 18 a mild assumption. Our intuition
that "typically" Tp should be on the order of e-O(d), whereas (8) only requires it to be 2 e-
Reduction to incentivized reinforcement learning
Our second algorithm builds on the Hidden Hallucination approach from Simchowitz and Slivkins (202T), which targets incentivized exploration for episodic reinforcement learning. We use this approach by "encoding" problem instance of combinatorial semi-bandits as a tabular MDP, so that actions the MDP correspond to atoms, and feasible trajectories correspond to feasible arms. Then invoke theorem in Simchowitz and Slivkins 2021 and "translate" this theorem back to combinatorial semi-bandits.
More specifically, consider a tabular MDP with deterministic transitions and unique initial state. Each action in this MDP correspond to some atom E; then the action's 's reward is drawn from the corresponding reward distribution De. In general, only subset of actions is feasible at given state- stage pair the MDP. Let G be the transition graph in such MDP: the nodes of G correspond to state-stage pairs in the MDP (the root node corresponding to the initial state and stage 0). Fach edge (u, v) G corresponds to some MDP action feasible u, i.e., to some atom. While different edges in G can correspond the same atom, require that any rooted directed
a rooted directed graph such that

---

path in G' cannot contain two edges that correspond to the same atom. Let Ap be the subset of atoms that corresponds to a given rooted directed path P. and let AG = { Ap rooted directed paths in G } be the family of arms "encoded" by G. A family of arms A is called -DP-encoduble if A = Ag for some transition graph G as defined above with O(d2) nodes.
Our result applies to all MDP-encodable feasible sets. In particular, the set of all subsets of exactly m atoms, for some fixed m S d, is MDP-encodable. To see this, consider an MDP with m stages and d states, where each state & E [d] corresponds to the largest atom already included in the arm, and actions feasible at given stage i and state E correspond to all atoms larger than L.
Our result allows for arbitrary per-atom priors Pt, subject to a minor non non-degeneracy condition, and reward distributions Dj that are supported on the same countable set.
Theorem 4.6. Consider a feasible arm set A that is -DD-encodable, as defined above. Suppose the per-atom priors Pt lie in some fixed, finite collection C such that any Pe E C satisfies P(te S c) > 0 for all e > O and E [O]]]= >> O. Further, suppose all reward distributions 'De that are supported on the same countable set. Fix parameter ö E (0, 1). There is BIC algorithm such that with probability at least 1 - each atom is sampled at least once. This algorithm completes in No, rounds, where d8 No &b c -Oe (poly(d)- log(6-1)) for some constant &e (0,1) determined by collection C.
Remark 4.7. While the guarantee in Theorem holds with probability 1 - 8, rather than almost surely, it suffices to bootstrap Thompson Sampling in Theorem 3.1 To this, let ALG be an algorithm that runs for To = No RTTs + d 7h7s rounds (with nhss from Theorem B.J). and proceeds as follows: first it repeats the algorithm from Theorem 4.6 firs times, and in the remaining rounds it deterministically plays an arm with the largest prior mean reward (this algorithm is BIC). Define the "success event" as one in which ALG samples each atom 2 ViTs times in the first No- Nrs rounds. Consider another algorithm, ALG", which runs for To rounds, coincides with ALG on the first No Nrs rounds, and in the remaining rounds coincides with ALG on the success event, and otherwise plays some arms so as to sample each atom at least once (this algorithm is not necessarily BIC). Now, if Thompson Sampling is preceded by ALG', then the analysis Theorem 3.1 guarantees that each round of Thompson Sampling satisfies the BIC property Q.. and does so with strictly positive prior-dependent constant on the right hand side of (I) Therefore, the same holds for ALG, since coincides with ALG" w.h.p., if the failure probability ó in Theorem 4.6 is chosen small enough.
Acknowledgments and Disclosure of Funding
ZSW, DN were supported in part by the NSF FAI Award # 1939606, NSF SCC Award # #1952085, Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, and a Mozilla Research Grant. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and not necessarily reflect the views of the National Science Foundation and other funding agencies. We would like to thank Keegan Harris and Max Simchowitz for brief collaborations, and Mark Sellke for insightful conversations on incentivized exploration.
References
S. Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. J. of the ACM, 64(5): 30:1-30:24, 2017. Preliminary version in AISTATS 2013.
G. Bahar, R. Smorodinsky, and M. Tennenholtz. Economic recommendation systems. In 16th ACM Conf. on Electronic Commerce (ACM-EC), 2016.
G. Bahar, R. Smorodinsky, and M. Tennenholtz. Social learning and the innkeeper's challenge. In ACM Conf. on Economics and Computation (ACM-EC), pages 153-170, 2019.
D. Bergemann and S. Morris. Information design: A unified perspective. Journal of Economic Literature, 57(1):44-95, March 2019.
K. Bimpikis, Y. Papanastasiou, and N. Savva. Crowdsourcing exploration. Management Science, 64 (4):1477-1973, 2018.
M. Castiglioni, A. Celli, A. Marchesi, and N. Gatti. Online bayesian persuasion. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
B. Chen, P. Frazier, and D. Kempe. Incentivizing exploration by heterogeneous users. In Conf. on Learning Theory (COLT), pages 798-815 2018.

---

W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In 20th Intl. Conf. on Machine Learning (ICML), pages 151-159, 2013.
R. Degenne and V. Perchet. Combinatorial semi-bandit with known covariance. In Advances in Neural Information Processing Systems, volume 29, 2016.
Frazier, D. Kempe, J. M. Kleinberg, and R. Kleinberg. Incentivizing exploration. In ACM Conf. on Economics and Computation (ACM-EC), 2014.
A. Gopalan, S. Mannor, and Y. Mansour. Thompson sampling for complex online problems. In ICML, 2014.
A. György, T. Linder, G. Lugosi, and G. Ottucsák. The on-line shortest path problem under partial monitoring. J. of Machine Learning Research (JMLR), 022369-2403 2007.
T. E. Harris. A lower bound for the critical probability in certain percolation process. Mathematical Proceedings of the Cambridge Philosophical Society, 56(1):13-20) 1960.
N. Immorlica, J. Mao, Slivkins, and S. Wu. Incentivizing exploration with selective data disclosure. In ACM Conf. on Economics and Computation (ACM-EC), 2020. Working paper available at https: //rxi///rxxvvv// arxiv. org/ abs /1111.1111 06026.
E. Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11(1):
249 272, 2019.
E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In 23rd Intl. Conf. on Algorithmic Learning Theory (ALT), pages 199-213, 2012.
I. Kremer, Y. Mansour, and M. Perry. Implementing the "wisdom of the crowd". J. of Political Economy, (2(5):988-10122 2014. Preliminary version in ACM EC 2013.
B. Kveton, Z. Wen, A. Ashkan, H. Eydgahi, and B. Eriksson. Matroid bandits: Fast combinatorial optimization with learning. In / 13th Conf. on Uncertainty in Artificial Intelligence (UAI), pages 429, 2014.
B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvári. Tight regret bounds for stochastic combinatorial semi-bandits. In 18th Intl. Conf. Artificial Intelligence and Statistics (AISTATS), 2015.
Y. Mansour, A. Slivkins, and V. Syrgkanis. Bayesian axcettve-coopptible bandit exploration. Operations Research,
132-1161, 2020. Preliminary version in ACM EC 2015.
Y. Mansour, A. Slivkins, V. Syrgkanis, and S. Wu. Bayesian exploration: Incentivizing exploration in Bayesian games. Operations Research, 70(2), 2022. Preliminary version ACM EC 2016.
D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4): 122--143, 2014.
D. Russo and B. Van Roy. An informatiio-ttherrtiic analysis of thompson sampling. J. of Machine Learning Research (JMLR), 17:68:1-68:30 2016.
D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen. A tutorial on thompson sampling. Foundations and Trends Machine Learning, 11(1):1996, 2018. Published with Now Publishers (Boston, MA, USA). Also available at https: / rrviv ortpabssssr//s/soo//ooo..... aaaaab//700 17777 02038.
M. Sellke and A. Slivkins. The price of incentivizing exploration: characterization via thompson sampling and sample complexity. In 22th ACM Conf. on Economics and Computation (ACM-EC), 2021.
M. Simchowitz and Slivkins. Incentives and exploration in reinforcement learning, 2021. Working
paper, available at https: /ttttss:/araas //axivivv.///////// org/ abs 2203. 003600.
A. Slivkins. Introduction to multi-armed bandits. Foundations and Trends@) in Machine Learning, 12(1-2):1-286, Nov. 2019. Published with Now Publishers (Boston, MA, USA). Also available at ht https:://axxt:
oroo htgg//b////// 904404444 00272. Latest online revision: Jan 2022.
W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
S. Wang and W. Chen. Thompson sampling for combinatorial semi-bandits. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5114-5122. PMLR, 10-15 Jul 2018.
Z. Wen, B. Kveton, and A. Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In 32nd Intl. Conf. on Machine Learning (ICML), pages 1113-1122, 2015.
10

---

Y. Zu, K. Iyer, and H. Xu. Learning to persuade on the fly: Robustness against ignorance. In ACM
Conf. on Economics and Computation (ACM-EC), pages 927-928, 2021.


Reviews:
[{"review_id": "xVg1rSeyZxx", "reviewer": "Reviewer_jo2d", "summary": "This paper investigates the incentivized exploration problem in combinatorial semi-bandits setting. The authors prove that Thompson Sampling is incentive-compatible when initialized with a sufficient number of samples of each arm in combinatorial semi-bandits. In addition, the authors design ", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and compares with previous literature thoroughly. The main results of this paper are solid, however, I have no enough expertise to judge whether the proof technique is trivial or not compared with the existing literature. The initial exploration algorithms seems rely on the reduction to previous literature and the BIC-bandit expert can help to judge the technical contribution of this paper. \n\nWeaknesses: This paper is a bit incremental from my perspective, which generalizes previous incentivized exploration to combinatorial semi-bandit problems. The significance of this paper needs to be justified further by BIC-bandit expert.\n\nOverall, this is a good theoretical paper. Whether to accept the paper depends on the technical contribution of this paper.", "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": "X5vLAuvnSq2", "reviewer": "Reviewer_tHsD", "summary": "This paper studied incentivized exploration problem, and provided some theoretic study of using combinatorial semi-bandits to solve the problem. The paper does not seem to be complete, since there is no experimental sections to show the results to support the proposed algorithm.", "questions": "Incentivizing Combinatorial Bandit is an interesting research topic. However, without experiment justification, there is no point to show the paper in the high standard NeurIPS conference. ", "limitations": "Since there is no experiment result presented in the paper, it is hard to reproduce the work.", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The mathematical framework seems ok, including Thompson Sampling, BIC algorithm and so on. However, there is no experimental justification at all.", "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": "NAAhYZe-r82", "reviewer": "Reviewer_CaZr", "summary": "This paper considers a combinatorial multi-armed bandits (CMAB) setting where multiple users interact with a learning algorithm. The algorithm recommends arms and the users decide whether they want to follow algorithm's recommendation (explore) or choose different arms (exploit). The paper considers the problem of incentivizing identical Bayesian users to follow the algorithm's recommendation. Precisely, an algorithm is considered Bayesian Incentive Compatible (BIC) if for every trial the algorithm plays an arm that has the best expected reward with respect to prior belief of a given user. The paper shows that the Thompson sampling algorithm for CMAB satisfies BIC given a sufficient number of bootstrap samples for each arm. The paper then considers the goal of designing BIC algorithms for providing bootstrap samples and proposes two algorithms: (1) based on a reduction to incentivized K-armed bandits problem, (2) based on a reduction to incentivized reinforcement learning.  ", "questions": "I would request the authors to specify the challenges in achieving incentivized exploration for combinatorial bandits, and the technical ideas used to overcome these challenges. ", "limitations": "I do not foresee any negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is very well-written with proper intuition for various assumptions/ideas. Prior work has also been addressed adequately. \n\nWeaknesses: I think that the contribution of the paper is incremental in nature given the amount of existing work on incentivizing exploration. For example, it was already shown by Selke & Slivkins (2021) that Thompson sampling is BIC for classical bandits and it does not seem surprising that the same result also holds for the combinatorial bandits setting (albeit for a different number of bootstrap samples). The bootstrap algorithms proposed by the paper are also based on existing ideas in Mansour et al. (2020) and Simchowitz & Slivkins (2021). ", "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": "BdClT2UTH6L", "reviewer": "Reviewer_gfpS", "summary": "This work investigates incentivized exploration in a combinatorial semi-bandits setting. There are two main theoretical results. First, it was proven that Thompson sampling (TS), when concatenated with a first algorithm that generates at least given number of samples for each atom, is Bayesian incentive-compatible (BIC). Second, the authors propose two approaches, both adapted from the existing literature to handle the additional challenges of combinatorial semi-bandits, that satisfy the requirements of the first algorithm before TS.", "questions": "- The second approach (Sec. 4.2) seems an overkill given that Simchowitz and Slivkins (2021) handles the more difficult episodic RL setting. Is there any way to simplify?\n- Line 291, should it be (11) instead of (7)?\n", "limitations": "The authors did a great job explaining limitations and social impact in the Introduction section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The studied problem of incentivized exploration in combinatorial semi-bandits is novel. In particular, TS is considered as the bandit learning algorithm, which is both interesting and challenging.\n\n2) Theoretically establishing that TS is BIC is a strong contribution.\n\n3) The two approaches to satisfy the requirements of $\\texttt{ALG}$ are interesting, particularly in the combinatorial semi-bandits setting.\n\nWeaknesses:\n\n- There lacks a discussion of motivating/matching applications of incentivized exploration (which is well motivated in prior papers) specifically for combinational semi-bandits. It was briefly mentioned in Page 2 but I feel that a detailed example would be beneficial. \n- A discussion of how to handle $K>2$ in Section 3.1 would be valuable.\n- It is worth discussing the constant (number of samples) in the theorems. Will they blow up $T$?\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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept