(Almost) Free Incentivized Exploration from Decentralized Learning Agents
Authors: Chengshuai Shi
Haifeng Xu
Wei Xiong
Cong Shen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Incentivized Exploration
Principal Agent Models
Multi-armed Bandits

Abstract: Incentivized exploration in multi-armed bandits (MAB) has witnessed increasing interests and many progresses in recent years, where a principal offers bonuses to agents to do explorations on her behalf. However, almost all existing studies are confined to temporary myopic agents. In this work, we break this barrier and study incentivized exploration with multiple and long-term strategic agents, who have more complicated behaviors that often appear in real-world applications. An important observation of this work is that strategic agents' intrinsic needs of learning benefit (instead of harming) the principal's explorations by providing "free pulls". Moreover, it turns out that increasing the population of agents significantly lowers the principal's burden of incentivizing. The key and somewhat surprising insight revealed from our results is that when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free. Our main results are built upon three novel components which may be of independent interest: (1) a simple yet provably effective incentive-provision strategy; (2) a carefully crafted best arm identification algorithm for rewards aggregated under unequal confidences; (3) a high-probability finite-time lower bound of UCB algorithms. Experimental results are provided to complement the theoretical analysis.

(Almost) Free Incentivized Exploration from Decentralized Learning Agents
Chengshuai Shi
Haifeng Xu University of Virginia hx4ad@virginia edu
University of Virginia cs7ync@virginia. edu
Wei Xiong
Cong Shen
The Hong Kong University of Science and Technology wxiongaeSconnect. ust.hk
University of Virginia cong@virginia. edu
Abstract
Incentivized exploration in multi-armed bandits (MAB) has witnessed increasing interests and many progresses recent years, where a principal offers bonuses agents to do explorations her behalf. However, almost all existing studies are confined to temporary myopic agents. In this work, we break this barrier and study incentivized exploration with multiple and long-term strategic agents, who have more complicated behaviors that often appear in real-world applications. An im- portant observation of this work is that strategic agents' intrinsic needs of learning benefit (instead of harming) the principal's 's explorations by providing "free pulls". : Moreover, it turns out that increasing the population of agents significantly lowers the principal's 's burden incentivizing. The key and somewhat surprising insight revealed from our results is that when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free. Our main results are built upon three novel components which may of independent interest: (I) simple yet provably effective incentive-provision strategy; (2) carefully crafted best arm identification algorithm for rewards aggregated under unequal confidences; (3) a high- probability finite-tima lower bound of UCB algorithms. Experimental results are provided complement the theoretical analysis.
Introduction
Multi-armed bandits (MAB) is simple yet powerful model for sequential decision making with tradcoff (Bubeck and Cesa- Bianchii 2012 Lattimore and Szepesvári, 2020). In standard MAB settings, one principal, who has long-term system-level objective, takes charge of selecting and playing arms. However, such assumption does not always hold reality. It is often the case that pulls are performed by multiple different agents whose individual goals not aligned with the system, and the principal can only observe agents' actions. One typical example the individual buyers (agents) and the online shopping platform (the principal). Such scenarios complicate decision making and introduce significant difficulties to optimize the system performance.
Incentivized exploration has been proposed address this problem (Frazier et al. 2014 Mansour Øt 2015).. Specifically, bonuses can be offered by the principal to incentivize agents to perform specific actions, e.g., to explore their originally underrated arms. This framework provides an opportunity to reconcile different interests between the principal and agents. As a concrete example, the online shopping platform can offer discounts on certain items that individual buyers would buy them and provide feedbacks, which can be used to optimize future strategies of the platform.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

While incentivized exploration has been investigated in the existing literature, we recognize two major limitations. First, almost all of the existing works assume the participating agents be myopic, i.e. they always choose the empirically best arm. Second, it is always assumed that at each time slot, one new agen! participates in the system, i.e., agents never stay or return. other words, prior research mainly considers how to incentivize one single temporary myopic agent. These two assumptions largely limit the applicability of incentivized exploration.
In this work, we extend the study of incentivized exploration beyond the aforementioned barriers, and investigate situations with multiple long-term strategic agents. In particular, we focus on the scenarios (see Section[3.] where the principal wants to identify the (overall) best arm whereas the heterogeneously involved agents only care about their different individual cumulative rewards. For such scenarios, the "Observe-then- tthen-nncentiviee" (OTI) mechanism is proposed and several interesting observations are obtained. First, we find that strategic agents' intrinsic needs of learning can actually benefit principal's exploration by providing "free pulls". In other words, as opposed to myopic agents, the self interests of strategic agents can be exploited by the principal. Second, it turns out that increasing the number of participating agents can significantly mitigate the principal's '' burden on incentivizing, which highlights the importance of increasing the population of agents. A crux of our findings is the following intriguing conceptual message: when there are sufficiently many learning agents involved, the exploration process of the principal could be (almost) free.
Behind these findings, three novel technical components play critical roles in the design and analysis of OTI, all of which may have independent values.
First, a simple yet provably effective incentive-provisiee strategy is developed, which can efficiently regulate strategic agents' behaviors and serves as the foundation of the algorithm analysis.
Second, a best arm identification algorithm is carefully crafted to tackle the varying amounts of
local information from heterogeneous agents. This setting itself is novel in best arm identification. A high-probabiie finite-time lower bound of UCB algorithms (Auer et al. 2002) is proved, which contributes a better understanding of the celebrated UCB.
These insights and techniques are unique in incentivizing multiple long-term strategic agents, which may find applications in related problems, and encourage future research in this direction.
2 Related Works
Incentivized exploration. Since proposed by Frazier et al. (2014); Kremer et al. (2014), many progresses have been made in incentivized exploration in MAB. Especially, there exist two lines of studies. The first one (Kremer et al. 2014 Mansour et al. 2015 2016 Immorlica et al.) 2020 Selike and Slivkins, 2020) assumes the principal can observe the full history while the agents cannot, and the principal leverage such information advantage to perform incentivizing. The second line, which our setting follows, considers publicly available history while the incentives are done through compensations. This idea is first introduced by |Fazierr et al. (2014) and generalized by Hann et al. (2015), both on Bayesian settings. The non- oon-Baysiann case, as adopted in this work, is first studied by Wang and Huang (2018), and recently extended by Liu et al. (020); Wang et al. (202T).
However, the aforementioned works mainly consider that one new myopic agent enters the system at each time slot and leaves afterward. The only exception is Mansour et al. (2016). where multiple but still temporary and myopic agents are considered. This work differs from them in considering multiple long-term strategic agents. In addition, another notable difference is that almost all prior works focus on regret minimization for the principal, instead of best arm identification.
One important related work is Chen et al. (2018), which studies temporary myopic agents with het- also observed there because heterogeneous preferences result in agents exploiting all arms. However, the "free pulls" of OTI is provided by strategic agents' intrinsic needs for explorations, which is fundamentally different. Regardless of the differences, both results show the value of further investigating agents' behaviors in incentivized exploration.
erogeneous preferences. Free explorations
Federated MAB. This work is related to and can potentially contribute to the studies of federated MAB (FMAB) (Shi and Shen 2 Shi et al. 2021 Zhu et al., (021), which considers a similar framework of multiple heterogeneous agents and global principal. These studies assume agents would unconditionally give up learning their own local ones and naively follow global instructions. which seldom holds in practice and makes those approaches unrobust. However, the proposed
2

---

incentivizing exploration scheme achieves the "best" of both worlds, i.c., agents learn local models with additional compensations and the principal learn the global model via a small amount of cost.
3 Incentivized Exploration from Decentralized Learning Agents
3.1 Motivation
Consider the following scenario: one company (the principal) can manufacture several products, and it would like to identify one product that best suits the market. A natural strategy is to perform a market survey by having group of users to try these products for some time and observing their feedbacks. However, different users have different preferences over these products and they are also learning in this process. Once they identify their preferred products, there little incentive for them to explore others, which limits the information gathering by the company. Such a scenario is common in real life. For example, telecommunications companies such as AT&T (the principal) try to find the optimal channel to serve the clients (agents) of an area through a period of trials; content-providing websites such as YouTube (the principal) test the proposed features with prospective users (agents).
The idea of incentivized exploration fits in these practical scenarios perfectly since it can be utilized to provide extra bonuses for users to try different products. However, the principal now faces the problem of how to incentivize multiple long-term strategic agents simultaneously. which has not been investigated in the prior research to the best of our knowledge. In addition. similar settings of applications are also considered in the recently proposed federated MAB (FMAB) (Shi and Shen 202T Zhu al. (.2T). However, current FMAB studies only consider naive users who always follow the principal's instructions, and cannot be applied to strategic users that have individual learning abilities and objectives.
3.2 Agents and the Principal
we consider a total of M available decentralized agents, each of which interacts with local bandit environment equipped with the same set of K arms (referred to as local arms) but with agent-dependent arm utilities. Namely, at time step t, a reward Xt,m(t) E [0, 1] is associated with agent m's action of pulling arm k which is sampled independently from an unknown distribution whose expectation is Us.m == E[Xx,,. (t)] In general, Uk.m A pk.n for m * n. These agents are (naturally) assumed be decentralized and self-interested, i.e, their goal is to collect as much (of their own) reward as possible during a certain time horizon.
Following the motivation example in Section 3.1
Besides these heterogeneous agents, there is also a principal. The principal faces global bandit game, which also has the same set of K arms (referred to as global arms for distinction). The expected rewards of global arm le are the exact average of corresponding local arms, i.e., M4 t Eme[M]] Me.m The principal's 's goal is to identify the optimal global arm with a certain confidence 1- 8 within a time horizon T. where 8 E (0, 1) is pre-fixed constant of the failure probability.
Without loss of generality, each local bandit game assumed have one unique optimal local arm, which is denoted as ka,m = arg max M for agent m and its expected reward is Pa.m
[4,, m. m- Correspondingly. the sub-optimal gap for arm k + k..m is defined as Ag, := Pa.m 4kkm and for arm k. k.m denote Ak.,..m Amin, minky4.,,.. Ag. Similarly, we also assume there is one unique optimal global arm k, == arg max X] A* in the global bandit game, whose expected reward is μ := μk,-- The global sub-optimal gap for arm ls + kt is defined as A := μe, P* and for arm k,, denote Ak. Amin = mink Ag. In addition, the time horizon T is assumed to be known to the principal but not to agents, as it is often the principal who determines such a horizon.
3.3 Interaction and Observation Model
While the agents can directly pull their local arms and observe rewards, the principal cannot interact with the global game. Instead, she can only observe local actions and rewards. In other words, with agent m pulling arm & at time t and getting reward Xk.m (t), the principal can also observe the action i and the reward N (l), which may be used to estimate expected rewards of global arms. It is helpful to interpret the global game as virtual global characterization of all the local games (although it does not necessarily align with any specific one), which results in the challenge that cannot be directly interacted with but can only be inferred indirectly.
3

---

This indirect information gathering introduces significant difficulties for the principal. In particular, it challenging obtain sufficient local information from self-interested agents to aggregate precise global information. For example, arm & can be exactly, or very close to, the optimal one in the global model, but also be highly sub-optimal on agent 's local model. Thus, the principal needs large amount of local explorations on arm l to estimate it, which contradicts with agent m 's willingness as arm k may not provide high local rewards. Thus, the task of best (global) arm identification is likely to fail only with this passive gathering of information, which is numerically verified in Section 6
3.4 Incentivized Exploration
To address these challenges, we resort to the paradigm of incentivized exploration, which provides a means for the principal to influence local actions. At time step f, the principal can provide extra bonuses for agents to explore arms, which will be announced to the agents before their decision making. Specif- ically, at time I, the bonus on arm k for agent v is denoted as Im. 2 O. If agent m chooses arm k. she has an observation of X (t) but obtains a reward X (t) Xk.mm (t) + m (t). Intuitively, if the principal wants to incentivize agent m explore certain arm against the agent's 's original willingness, she should give high bonus, i.e., In.m (t) > 0: other- wise, she should spare no bonus, i.e., J m (4) 0. In this way, the principal can leverage the extra bonuses to have agents gather her desired local information. The interaction model with incentivized exploration between the principal and one agent (among overall M agents) is illustrated in Fig
Principal
Knowledge and X (t)
Incentive lpm(0 (1)
Local Model m
Action k
D0
Reward (1
Agent 772
Figure 1: Incentivized exploration of the prin- cipal and agent m. The agent performs ac- tions and gets both rewards and incentives. The principal pays the incentives and observes local actions and rewards.
Under the basic framework, we now formally define the learning objectives of agents and the principal.
Agents' Objectives. First, the self-interested agents want to collect as many rewards as possible, note that the rewards now consist two parts: the original rewards generated by pulled arms and additional bonuses from principal's 's incentives. Thus, the cumulative rewards of agent is defined as
Ry (T) = -'= (x)..(1)).m)))) + Im. (t).m (t))
where (t) denotes the arm pulled by agent m at time t. We remark that such rational learning agents differ fundamentally from myopic ones assumed in most research of incentivized exploration.
Principal' Objectives. On the principal's side, her first goal to identify the best global arm with a confidence higher than --8. 8. Rigorously, this goal can be stated as
P (T)
(T) k. N 1 8,
where k. (T)) denotes the identified arm at horizon T.
Given that the identification is correct, the principal also aims at spending as few cumulative incentives as possible, which is defined as
C(T) : -T:=-'- T E MEIMI (1).
Note that best arm identification is the principal's 's major task whereas minimizing cost C(T') is only meaningful given (T) = h. is achieved. Though not central, our mechanism will also satisfy other desirable properties such storage efficiency.
In this work, we adopt the perspective of the principal, and try to optimize the principal's performance w.r.t. her learning objectives specified above. In other words, agents are ignorant of principal's 's goals and only focus on their individual rewards, and we only incorporate their "selffihness" to design an effective and efficient strategy for the principal. Such choice is natural in common applications where

---

the behaviors of principal (e.g., company, commercial platform) can be designed, while agents (e.g.. users, customers) normally perform their own decision making which cannot be specified.
Remark, Note that agents and the principal actually represent two kinds of bandit learning objectives. Namely, the agents target regret minimization (Auer et al. (002) Garivier and Cappé (2011) (although we here use the equivalent notation of cumulative rewards instead of regret), while the principal aims best arm identification (Audibert et al., 2010 Jamieson et al.) 2014, Garivier and Kaufmann 2016). This formulation is reasonable as agents often care more about their own cumulative benefits while the principal aims the final result, which can then be used in the future. However, as noted in Bubeck et al. (201T) even with the same game instance, these two objectives do not necessarily align with each other, not to mention the additional global-local heterogeneity considered in our model.
4 A Mechanism for Incentivizing Exploration
In this section, the seteerve-the--nnnetiviii (OTI) algorithm is proposed, which can effectively solve the best arm identification problem the global model while using small amount of incentives and maintaining efficient storage. As indicated by the name, the key idea of OTI is "Observe-thee then- Incentivize", which comes from its two phases: the observing phase and the incentivizing phase.
4.1 The "Take-or-Ban -Bnn Incentive-Provision Protocol
Before designing detailed mechanisms, we first recognize one major challenge to incentivize forward- looking agents is that even if we provide sufficient bonuses to compensate her reward at the current round, the agent may not want to take it for various reasons, c.g., giving up her current choice may lead to significant future losses, or refusing the current compensation may trick the principal to offer more future bonuses. Therefore, it not clearly how to regulate agents' behaviors through incentives. To overcome this barrier, we propose the "Take-or- or-an" incentive-pre -provvii- protocol, which provably guarantees that it is in the best interest for every agent to follow the offered incentives. This protocol is announced to the agents at the beginning of the game, and detailed as follows.
"Take". At time step I, bonuses TR.m(( (t) offered agent m are set as a binary value. Specifically, m (t) = 1 if principal wants to incentivize exploration on her arm k; otherwise It (t) = O. In other words, if her arm is incentivized, agent m gets reward X (t) 1+ Xx.m (f) by pulling
"Ban". To avoid intractable agent behaviors, the following safeguard approach is adopted. Specifi- cally, at time step 8, if agent m is provided incentive for taking some action (i.e., 3k, T (8) = 1) but she does not pull it (i.e., nm (s) * k),, she is marked as "banned" by the principal. The principal stops providing bonuses for any banned agent in the future, i.e., Vt > 8, Vk E [K), (t) = O. In other words, due to her failure in following the current incentive, agent m loses the chance of taking future bonuses (bu she is still free to play the local game and get original rewards Xp. (t)).
4.2 The Observing Phase
Interestingly, while strategic agents introduce substantial challenges to the principal's learning problem, their fundamental need of learning local models can be blessing. In order collect more local rewards, agents naturally have to address the intrinsic "expllration-exxloitttoon dilemma. In particular, guarantee low regrets, some (but maybe limited) explorations on each arm are required by each agent. Specifically, this argument is supported by the following asymptotic lower bound (Lai and Robbins, 1985): with any consistent agent strategy for arm k o kem it holds that
B[N k.m (T)
1
lim P-+00
lTg(T)
KL(Jkk 14, )
where Ny. (T) is the number of pulls by agent m on arm up to time when there are no incentives, and (I m)) is the KL--divergence between two corresponding reward distributions. In other words, to guarantee local performance, agents would spontancously explore all local arms.
On the principal's side, this observation indicates that free local information can be obtained by just letting agents directly run their own local algorithms. Thus, intuitively, it is wise not to incentivize at the beginning of the game, but to observe and enjoy the "free rides" provided by agents' exploration.
A "consistent" strategy has regret of o(1")) in any bandit instance, Vel 0 Lai and Robbins 1985
5

---

However, since local models are often not aligned with the global model, it may not be desirable to fully rely on the "free rides" from local agents' actions since they may gradually converge to their own optimal local arms, which may not be what the principal is interested in exploring.
Thus, it is necessary to reserve some time be- fore the end of the game for adaptive adjust- ments. By putting these intuitions together, in the design of OTI, we specify the observing phase to last x(T)=
Algorithm 1 OTI: Principal
1: Initialization: bk E [K], E [M], (0)
O, pr.m (0) +
time steps from the beginning of the game To summarize, in this observing phase, the principal does not incen- tivize at all. i.., Vt E [0, 31. Vk E [K], Vm E [M], (m, O. Instead, she only observes local actions and rewards. Due to our choice of space-efficient information aggregation (spec- ified at the end of Section 4.3), by the end of the observing phase. the principal has the record {Ne.. (F), Pr. ( 1 E [K], Vm E [M]] where
2: for t = 1,2,
do
D. -Observing Phase
3:
Ak E [M] vm E [M]] It.m(t)) +0
4: Vm E [M], observe {Im {tm((), (xm(0.m)))t))) (t)),
then update (1m())) and (kmm(0)m))))
5: end for
> Incentivizing Phase:
6: Set S + [K]
b Incentivizing Phase
7: for _ + 1, + T do
8:
Vk E [K] jux (1 (L-1)) 1)
N7 Σ [ ml
1) and set C CBBB (t - 1) with Eqn. 2
is the number pulls performed
9:
Update S(t) as specified in Eqn.
by agent m on arm k up to time i and ju (t) is the corresponding sample means from these
10:
if [S(t) 2 then
k(()) <- arg max4
CB -1) 1)
pulls. These information serve as the foundation
12:
m(t) arg [M N Ne(e). (1 1)
for the remaining L time slots of the incentiviz-
13:
(i()).(11) (t) t
ing phase.
14:
Ip.m (t) 4 0, Vm # ml), Vk + R())
15:
else
4.3 The Incentivizing Phase
16:
(T') + the remaining arm in S(t)
17:
end if
From time slot _ + 1, the principal enters the in- centivizing phase, where she actively leverages incentives instead of passively observing. The first challenge she has is how to aggregate local information. Especially, the local sample means (i.e., fm.m (t)) are from different agents and associ- ated with different number of pulls (i.e., NN. (t)), which further result in their individually unequal
18:
end for
Output: K.
uncertainties. To address this challenge, new (global) arm elimination algorithm is proposed, which
is inspired by standard arm elimination algorithms in best arm identification (Even- Dar et al. [2002]
Karnin et al. 2013) but is specifically designed to tackle the new issue of global-local heterogeneity.
Specifically, at each time step f E 1 + 1, T). with the record {N (t - 1), f.. (1 1)| e [K]. Vm E [M]), the principal estimates the expected reward of global arm k as jux (t 1) = M Eme(M] As.m(( (t- 1) and associates global arm i with the following confidence bound:
CB, ( 1) = M/ V Σ ME(M) Nt. 1) ( log
KT
KT
+ 4M log log
(2)
Note that Eqn. (2) incorporates the different number of pulls on arm & by all the local agents, i.c., It is more challenging than the standard confidence bound design in best arm identification (Jamieson and Nowak 2014] Gabillon et al. 2012), which only considers one source of arm pulls. This complication can be better understood in later theoretical analysis.
{N (t- E [.]].
With the estimation and confidence bound, arms that are sub-optimal with high probabilities can be identified and eliminated while the other arms are left for more explorations in the future. Namely, let the active arm set S()) denote the arms that have not been determined to be sub-optimal up to time step i, which is initialized as 5( = [K]. the new active arm set S(t) is updated from S(t - 1) as
(t)(t- - (B 1)] mn}- (3)
stt) k E S(t - S(t-t())Aa(( - 1) + CB - -1) max SES(t-1)
To have the the arms in set (t). Hence, incentives play a critical role and the principal needs to decide which
procedure effectively iterate over time, explorations are required for
T 4 VT, etc. Details Note that although re())) is chosen to be 2 here, there are other possible choices, e.g., for the influence of this choice provided in the supplementary material.
T

---

arm amm-agent pair to incentivize. In OTI, this decision process consists of two steps. The first step is to find the active arm with the largest confidence bound, i.c.,
k(t) == arg max CB 1).
kES(1)
Then, the second step is to further identify the local agent who has the least pulls on arm k(() i.e.
mtt) == arg min NE(t). -0-1.
me(M]
Finally, the principal would only incentive agent ml) to explore the arm k((), i.e.,
{
if k(I) and mm())
Ie,(t) (t)
otherwise
Intuitively, the arm-agent pair {k(t), mt)} represents the largest source of uncertainties in the current estimation of active global arms, i.e., the arm with largest confidence interval and the agent who had the fewest pulls on it. Thus, explorations on this pair is naturally the most efficient way to increase the confidence of estimations.
By iterating this process of eliminating and incentivizing, the principal would eventually have sufficient information shrink the active arm have only one arm left when the horizon is sufficient, i.e., [S(t) 1, and this remaining arm is output as the identified optimal arm i. (T).
Space-efficient Information Aggregation. While the principal can observe local actions and re- wards, it is not storage- storage-friendly
store all raw local data sequence (T). X (r),(....))))))) (T) (T) [M]. VT < t). which requires memory space of order O(Mt) that grows linearly in t. Instead, OTI is designed to keep track of {N k.mm (t), m (t) E []] Vm E [M]]. These values can be updated iteratively and only take constant memory space of ((K)) regardless of the horizon.
Theoretical Analysis
5.1 Main Results
The performance of OTI is theoretically analyzed from several different aspects. With agents running general consistent local strategies, the following theorem establishes the success of best arm identification and bounds the expected cumulative incentives.
Theorem 1. is the best interest for every agent to always accept the incentivized explorations under the "Take-or- Barke-or-Bard Ban" protocol. Moreover, if the agents' local strategy is consistent without incentives and the horizon T is sufficiently large, the OTI algorithm satisfies thut ((k,(T) = =k.] Z 8, and the expected cumulative incentives are bounded as
log KT MA
log log( KT min
T
log 2 2 KL( Ha
}. (4)
E(C(T)) = Σ
Σ
kE(K) MEIM
where: + max(x1 03.
While Theorem 1 provides general upper bound with arbitrarily consistent local strategies, Eqn. (4) is an upper bound on expected cumulative incentives. does not imply a (stronger) high-probability bound. For example, the incentives may be of order (logg (T)) with 1/ Iog(T) probability.
To better understand the performance of OTI, next we consider agents who run UCB (Auer et al. 2002), one of the most commonly adopted MAB algorithms. Specifically, agents assumed to the following a-UCB algorithm (Bubeck and Cesa- Bianchi 2012) when there are no incentives:
Tea (t) + arg max [At.m(t 1) + / log(t)/Nk. 11] kE(K]
where a a positive constant specified in the design, and a typical choice a = 2 (Auer al. 2002). In this case, able to achieve a stronger high-prroabiility guarantee for incentives.
7

---

Theorem 2. While the agents run a- UCB algorithms with 2 3. and the horizon T is sufficiently = k.]
2
large, the OTI algorithm satisfies that P[K (T)
2 1 8. Moreover, it holds that
P plom- - Σ Σ
log(
KT
log log( KT
a (oog(()) ( []]
4MK
2 T
(5)
M
A7 k,m
KE[K] MEIM
In both Eqns. (4) and ( the first two terms represent the number of pulls that the principal needs on agent mn' arm & to determine whether it is optimal or not. They are proportional to 1/ as in standard best arm identification algorithms (Jamieson and Nowak 2014). In addition, the second term is lower-order one w.r.t. 1/8. Taking deeper look into these results, we see that the first term decreases with increasing number of agents (proportional to 1 1/M). This observation indicates that increasing the population of agents actually benefits the learning of the principal. We note that the importance of agent population has not been fully recognized in prior studies.
Furthermore, both last terms in Eqns 4 and (5) characterize the number of spontaneous pulls that agent m performs on arm & during the observing phase, which is the amount of "free pulls" taken by the principal. This term is guaranteed by Eqn. TT) for general consistent local strategies, and by the to-be presented Lemma 4 for UCB. In other words, the learning behavior of strategic agents benefits the exploration of the principal. This observation is interesting since as opposed to most prior studies of myopic agents, the principal can leverage the natural behavior of strategic agents.
Both of the aforementioned observations lead to our key result, that if there are enough amount of agents, i.e., M large, the last term dominates the first two terms, which means no incentives are needed. Correspondingly, somewhat surprising result emerges when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free.
The key parts in the proofs are illustrated in the following, which may be of independent interests.
5.2 Proof Step Effectiveness of the "Take-or-Bari Incentive-Provision Strategy
In prior works with myopic agents, it is obvious that with sufficient instantancous bonuses, they would pull the incentivized arms. However, this work deals with strategic agents with long-term goals. As stated in Section 4.1 these strategic agents have much more complicated behaviors, e.g., they may occasionally (instead of always) follow incentives, or they may refuse incentives first but accept later, which requires more careful agent behavior analysis. Fortunately, our "Take-or or-Ban" protocol guarantees that agents will always follow the incentives. as stated in the following lemma. Lemma 1. Under the "Take-or marke-or-Bll caae-orr-''" Ban" incentive prrvviiiii protocol. following incentives, whenever offered, is optimal w.r.f. the expected cumulative rewards (compared not following) for every agent.
Note that the above lemma does not rely on agent's 's learning algorithm and holds for all possible ones. Thus regardless of local agents' original intentions, as long as they are self-inte interested and rational, they should always follow the incentives, i.e., pull the arm which has extra bonus offered. This design provides a clean characterization of agent behaviors for our analysis of OTI next.
Remark. The "Take-or-Ban" protocol is designed for theoretical rigor. For practical applications, the design OTI algorithm can be implemented with relaxed protocols; it is just that the rigorous theoretical incentive guarantee may not hold for some rational users with sophisticated strategies.
5.3 Proof Step 2: Effectiveness of Best Arm Identification
Some key lemmas presented to demonstrate the effectiveness and efficiency of the designed best arm identification algorithm. Inspired by proof techniques in combinatorial MAB (CMAB) literature (Combes et al. 2015), the confidence bound design in Eqn. (2) is validated in the following lemma. Lemma 2. Denote H. == (vt E 132 + 11. Vk E [K], (t 1) - pal < CBx 1)}. When the horizon T is sufficiently large, it holds that PPHH) 2 8.
Conditioned on event H. the required number of local pulls characterized in the following lemma. Lemma 3. When event H happens, Vt E [ + 1, 1,TT), T) we have k. E S(t), iee, the optimal global arm would not be eliminated. Moreover, it suffices to eliminate arm ls + k. at time t, ie., k & S(t), when
16 log KT/ 64 log log(KT/ (TT/))
Vm E [M], (t (t- 1), Ne..,
mm (t-
1) 2
+
M
A
8

---

100
Incerstives (100)
CTT (10%
Identried
$3 236
10 In(
20
omth
(agentarm)
14
(a) With or w/o incentives. (b) Incentives assignment.
(c) Incentives v.s. (d) Incentives V.s. M
Figure 2: Experimental results. (a)-(c) are performed under 2-agents-3-ad -ramss example while (d) is evaluated with random instances with 30 arms and varying number of agents. (a) reports the identification accuracy with and w/o incentives, (b) the assignment of incentives, (c) the logarithmic dependence on ó, and (d) the diminishing effect of cumulative incentives with M increasing.
With the decision process in Section 4.3 and the lower bound in Eqn. T Theorem I can be proved.
5.4 Proof Step 3: A Finite-time Lower Bound of UCB
An important ingredient to prove Theorem Dis finite-time probbbbrbbbbllityy lower bound for a- a-UCB:
4K(3/3/2) 3/222 the a-UCB algorithm with 2 - satisfies that
Lemma 4. When A satisfies
[A]
A min,m
(Va- v1.5) 1 2
2K
P vk E [K], N k.m (A)
2 1
(6)
4
We note that Eqn. 66 is valuable along multiple lines. First, is finite-time bound as opposed to the asymptotic one in Eqn. (I). Second, while Eqn. (I) holds in expectation, Equ. (6) is a stronger high-probbe high-probability bound, and implies bound of the same order for expectation. We believe that this result itself may contribute to the understanding of UCB. Specifically, this lemma characterizes UCB's conservativeness, i.e., it would (nearly) always explore every at least logarithmic times.
6 Experiments
Numerical experiments have been carried out to evaluate OTI. All the results are averaged over 100 runs of horizon 7' 10th and the agents perform the e-UCB algorithm specified in Section 5.1 with with
= 2. More experimental details can be found in the supplementary material.
First, with toy example of M 2 agents and K 3 arms, the ineffectiveness of not in- centivizing is illustrated. Specifically, agent I's expected rewards for the three arms are set as [0.89, 0.47, 0.07) while agent 2's as [0.01, 0.47, 0.89], which results in a global instance with ex- pected rewards [0.45, 0.47, 0.45] Note that the optimal global arm is arm 2, while the local optimal arm is (resp. 3) for agent (resp. 2), which raises the global-local conflicts. Without incentives, the principal can only output the arm with the largest aggregated global mean at the end of the horizon. As shown Fig. 2(a) such "purely passive" principal does not perform the identification well. Especially, she only outputs the correct arm (i.e., arm 2) with 53% accuracy. To make things worse, the principal has no control of this result, which may be even lower in other instances.
As opposed to the poor performance without incentives, Fig. 2(a) demonstrates that with incentives, OTI (using 8 0.01) always identify the optimal global arm. Correspondingly, Fig. 2(b) presents the amount of incentives spent on each agent-arm pair. It can be observed that the principal never assigns incentives on the optimal arm of each agent, i.e., arm (resp. 3) for agent 1 (resp. 2), which is intuitive since agents converge to these arms quickly and the "free pulls" on them is already sufficient. Furthermore, most of incentives are on arm 2, which because it is sub-optimal for both agents and lacks natural explorations. Moreover, OTI is tested with varying ó under the same --agents-3-arm instance. Fig. 2(c) illustrates that the cumulative incentives of OTI are (nearly) proportional to log(1/8), which verifies the logarithmic dependence on 1/6 in Eqns. and (5) when M is small.
At last, Fig 2(d) reports the dependence of cumulative incentives on the number of agents. Under different M, random local instances with 30 arms are generated to compose global instances with
"Athhough being toy example, the seemingly simple instance is actually hard in terms of small global sub-optimality gap (Amin 0.02), large global-local divergences and small number of involving agents.

---

Amin E (4.5 x 10-3 As shown in Fig 2(d) the cumulative incentives (with 8 = 0.01) gradually diminish as M increases. When more than 120 agents are involved, the principal spends no incentive but can still learn the optimal global arm, which verifies our theoretical finding that with sufficiently many learning agents involved, the exploration process of the principal can be (almost) free.
Discussions and Future Works
While progresses have been made in this work, some problems are worth future investigations.
Personalized Tasks. This work focuses on identifying one common optimal global arm among the entire group of agents. This objective is well-motivated (Zhu et al. [021) as only one arm can be selected for the collective interest in many applications. For example, due to the budget constraint, many companies must choose one out of multiple potential products for R&D. However, we note that is also an interesting direction to use global information for personalized tasks, e.g., recommend items to the customer based on both her own favor and the overall popularity. The idea of FMAB with personalization in Shi et al. (202T) is one potential direction, where weighted sums with the global and local model are set as the learning objectives.
Agent Sampling. The principal in this work targets at learning the optimal global arm among the involved group of agents, which is reasonable for many use cases. For example, cellular communi- cation operators typically can access data from all users to find the optimal channel. Moreover, to provide products to its chain stores, the company can easily perform a market survey with all of them. Nevertheless, in some applications, the principal only has access to the feedback from a sampled population but nevertheless would like to learn the best arm for the underlying entire population. We believe our findings is an important step towards this more challenging setting, where certain probably approximately correct (PAC) learning style of analysis may be needed since one may have to bound the mismatch between the best arm for the involved group and that for the whole population as the number of involved agents grows.
"Take-or-Ban" is for the purpose of rigorous theoretical analysis. Without this scheme, it is very challenging to rule out the possibility that some rational users may employ sophisticated strategies to intentionally reject an earlier incentive in order to induce higher future incentives. We note that it is intriguing to develop other agent regulation protocols or even directly analyze agents' behaviors without regulation. However, reality, when facing less sophisticated users, we expect the insight revealed from our theoretical analysis still to be useful for less restrictive protocols, such as banning an agent for a few rounds or after a few (instead of one) refuses of the incentives (see the supplementary material for some experimental illustrations).
Dicentive-Provisoon Protocol. As mentioned in Section 5.2
Other Extensions. In Section 5 a high-probability upper bounds of C(T) is established for the agents who run Q-UCB. It is conceivable to extend the proof to other optimism- based algorithms, e.g.. KL-UCB (Garivier and Cappé, 201T). However, would be interesting to provide similar guarantees with agents running Thompson Sampling (Agrawal and Goyal| (012)) or c-greedy (Auer et al. 2002). Furthermore, it is worth exploring how to extend the study to other bandit types.
8 Conclusions
In this work, we studied incentivized exploration with multiple long-tem term strategic agents. Motivated by practical applications, the formulated problem involves multiple heterogeneous agents aiming at collecting high cumulative local rewards and one principal trying to identify the optimal global arm but lacking direct accesses to the global model. The OTI algorithm was designed for the principal to intelligently leverage incentives have local agents explore information on her behalf.
Three key novel components played critical roles in the design and analysis of OTI: (1) provably effective "Take-or-Bee -ann incentive-pree provission strategy guarantee agents' behaviors; (2) specifically
designed best arm identification algorithm to aggregate local information of varying amounts provided by heterogeneous agents; (3)& highh-robabiility lower-bound for UCB algorithms that proved its conservativenes: The regret analysis of OTI showed that the learning behaviors of strategic agents can provide "free pulls" to benefit the principal's exploration. Moreover, we observed that increasing the population of agents can also contribute to lower the burden of principal. At last, the key and somewhat surprising result was revealed that with sufficiently many learning agents involved, the exploration process of the principal can be (almost) free.
10

---

Acknowledgement
The CSs acknowledge the funding support by the US National Science Foundation under Grant ECCS- 2029978, ECCS-2033671, and CNS-2002902, and the Bloomberg Data Science Ph.D. Fellowship. WX acknowledges the funding support by the Hong Kong Ph.D. Fellowship. HX supported by Google Faculty Research Award.
References
Agrawal, S. and Goyal, N. (2012). Analysis of thompson sampling for the multi-an aumti-armed bandit problem. In Conference on learning theory, pages 39-1.
Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT, pages 41-53.
Auer, P., Cesa-Bianchi, N., and Fischer, (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-2555
Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations Trends in Machine Learning.
Bubeck, S., Munos, R., and Stoltz, G. (2011). Pure exploration in finitely-armed and continuous- armed bandits. Theoretical Computer Science, 412(11):1832-1852
Chen, B., Frazier, P., and Kempe, D. (2018). Incentivizing exploration by heterogeneous users. In Conference On Learning Theory, pages 798-818 PMLR.
Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. (2015). Combinatorial bandits revisited. Advances in neural information processing systems, 28:21 16-2124.
Even-Dar, E., Mannor, S., and Mansour, Y. (2002). Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pages 255- 270. Springer.
Frazier, P., Kempe, D., Kleinberg, J., and Kleinberg, R. (2014). Incentivizing exploration. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 5-22.
Gabillon, V., Ghavamzadeh, M.. and Lazaric, A. (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. NIPS-Twenty-Siie Annual Conference on Neural Information Processing Systems.
Garivier, A. and Cappé, O. (2011). The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376.
Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1021 PMLR.
Han, L., Kempe, D., and Qiang, R. (2015). Incentivizing exploration with heterogeneous value of money. In International Conference Web and Internet Economics, pages 370-383. Springer.
Immorlica, N., Mao, J.. Slivkins, A., and Wu, Z. S. (2020). Incentivizing exploration with selective data disclosure. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 647-648.
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. (2014). lil'ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439, PMLR.
Jamieson, K. and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
Karnin, Z.,, Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR

---

Kremer, I., Mansour, Y., and Perry, M. (2014). Implementing the "wisdom of the crowd". Journal of Political Economy, 12265):988-1012.
Lai, T. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules, Adv. Appl. Math. 6(1):4-22.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Liu, Z., Wang, H., Shen, F., Liu, K., and Chen, L.. (2020). Incentivized exploration for multi-armed bandits under reward drift. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4981-4988.
Magureanu, S., Combes, R., and Proutiere, A. (2014). Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999. PMLR.
Mansour, Y., Slivkins, A., and Syrgkanis, V. (2015). Bayesian incentive-compatibl bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 565-582.
Mansour, Y., Slivkins, A., Syrgkanis, V., and Wu, Z. S. (2016). Bayesian exploration: Incentivizing exploration in bayesian games. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 661-661.
Perrault, P. (2020). Efficient Learning in Stochastic Combinatorial Univeristé Paris-Saclay.
PhD thesis,
Rangi, A., Tran-Thani L.. Xu, H., and Franceschetti, M. (2021). Secure-ucb: Saving stochastic bandits from poisoning attacks via limited data verification. arXiv preprint arXiv:2102.07711
Sellke, M. and Slivkins, A. (2020). Sample complexity of incentivized exploration. arXiv preprint arXiv:2002.00558.
Shi, C. and Shen, C. (2021). Federated multi-armed bandits. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI).
Shi, C., Shen, C., and Yang. (2021). Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925, PMLR.
Wang. H., Xu, H., Li, C., Liu, Z., and Wang. H. (2021). Incentivizing exploration in linear bandits under information gap. arXiv preprint arXiv: 104. 03360.
Wang, S. and Huang, L. (2018), Multi-armed bandits with compensation. Proceedings of the 32nd
International Conference Neural Information Processing Systems, pages 51 5119-5128.
Zhu, Z., Zhu, J.. Liu, J., and Liu, Y. (2021). Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29.
12


Reviews:
[{"review_id": "kIcefvj6MhA", "reviewer": "Reviewer_WEri", "summary": "This paper studies incentivized exploration in multi-armed bandits with long-term strategic agents. The question of how to incentivize agents to explore underrated actions/arms has become an increasingly popular topic in the recent few years. Yet, it is still a relatively underexplored area for studying how to incentivize UCB agents. Therefore, I think the proposed method contributes to a significant problem. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Below I want to summarize some of my concerns.\n\n1. Best Arm Identification\n \nIn this paper, it is assumed that the principal aims to find the (global) best arm. I think the authors should explain more about why such a goal is significant in this setting, although three relevant papers with the same goal (best arm identification) are cited. Personally, I think \"which can be used in the future\" is not enough. \n\nIn the cited paper (Audibert et al., 2010), there is only one agent. In this paper, there are multiple agents with different utility functions. The heterogeneity of the agents makes the problem a little bit different. For example, if there are only two arms A and B. Half of the agents hate A and like B, while the other half like A and hate B. In such a setting, finding the \"averagely\" best arm seems to be useless. In recent years, \"personalized incentives\" and \"personalized recommendations\" have received more and more attention. In this sense, finding a global best arm with respect to all of the agents seems to be less attractive. \n\nThis problem is not relevant to the algorithms. What I want to stress is that I hope the authors can identify some concrete scenarios in which identifying the best global arm plays an important role. \n\n2. Take-or-Ban\n\nIn the take-or-ban protocol, an agent will be marked as \"banned\" forever as long as it refuses the bonus once. I hope the authors can specify more clearly the reasons for devising such a protocol. I'm not sure what \"to avoid intractable agents behaviors\" means: psychologically or mathematically intractable? Also, without such a protocol, is your algorithm still able to find the best arm? \n\nHere I understand such a protocol can simply the scenario, especially the agents' behavior. While I also want to see if it is a prerequisite for the proposed algorithm. \n\n3. Related Works.\n\nSome of the papers cited in Section 6 helped me a lot in understanding the motivations. Yet, the related works are summarized on the last page of the paper. I think it may be a better idea to present the related works just after the introduction part as normal because without presenting enough relevant papers, it is difficult to illustrate that the assumptions on the agents are different.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The suggestions are included together with the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "5tuz4PVd93r", "reviewer": "Reviewer_tYjP", "summary": "The paper proposes incentivized exploration in multi-armed bandits (MAB) that includes multiple and long-term strategic agents that have individual learning abilities and objectives. They find that the intrinsic needs of the agents to learn benefits the principal and that increasing the number of these agents can result in (almost) free exploration process for the principal. The contribution of the paper is that it goes beyond previous researches in the field that dealt with temporary myopic agents and studied long-term strategic agents for MAB, proposing Observe-then-Incentivize (OTI) algorithm in the process. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes incentivized exploration in multi-armed bandits (MAB) that includes multiple and long-term strategic agents that have individual learning abilities and objectives. They find that the intrinsic needs of the agents to learn benefits the principal and that increasing the number of these agents can result in (almost) free exploration process for the principal. The contribution of the paper is that it goes beyond previous researches in the field that dealt with temporary myopic agents and studied long-term strategic agents for MAB, proposing Observe-then-Incentivize (OTI) algorithm in the process. \n\nStrengths:\n\nThe paper is clear about the contributions and the extension of previous MAB settings to incorporating long-term strategic agents has strong real-world connections and significance. It is relevant to the NeurIPS community because the study deals with decision-making process of the principal and the agents and their interactions. The Observe-then-Incentivize (OTI) algorithm is a framework that can be extended further and be applied to diverse settings where the principal interacts with agents with varying self-interests. The mathematical formulation of the setting is clear and sound.\n\nThe paper is clearly written and communicates thoroughly the connection to real-world applications. The paper is well organized in sections and is easy to follow. Also, the mathematical formulation and the setting are clearly discussed in detail and understandable. \nThe claims and methods are correct given their assumptions and principles. The empirical methodology is correct but would be much better if carried out with more agents and arms.  \n\n\nWeaknesses:\n\nThe experimental section is a little weak and could be expanded with more large-scale experiments and discussion. The “Ban” protocol is used to ensure that the agents pull the incentivized arm. According to this protocol, when an agent refuses to pull the arm that is incentivized by the principal, the principal bans that agent and does not offer any incentive in the future. This strategy seems to be limiting for the agents and breaks the high connection to real-world scenarios. More discussions need to be in place to justify this strategy.  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.  The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "5BcYPuUw3Xk", "reviewer": "Reviewer_jSch", "summary": "The authors study the problem of incentivizing heterogeneous agents to explore in multi-armed bandit setting. The OTI algorithm with two phases is proposed. Theoretical guarantees are established for general agents, and for agents with UCB exploration. Moreover, a byproduct of their analysis suggests UCB's conservativeness.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The writing quality and clarity are good. The idea and the approach are novel to the best of my knowledge. And the problem setting is relevant and relatively new. Below are some questions/suggestions:\n\n(1) Why does the principal want to identify the best arm that has the highest average reward among the agents who are in the test? I hope that the authors add some discussions to this issue. For instance, if a company is only testing a product on a group of people, there may be a gap between the best arm for this group and the whole population (all the customers). Can the algorithm and the analysis be carried out under the setting where there is a ground truth for the best arm? If not, what's the technical barrier?\n\n(2) Effect of number of agents: \n\n(i) In the theory section, the authors highlight \"proportional to $1/M$\". However, there is a $\\sum_{m \\in [M]}$ before that term. Wouldn't this cancel the term $1/M$?\n\n(ii) In the experiment section, $M = 60$ agents seems to be a quite large number compared to $K = 3$ arms. I think extra experiment results with larger number of arms $K$, each case run with different $M$, are desirable. With only one $K$ tested, the real dependency among $C(T)$, $K$, and $M$, seems very unclear.\n\nOverall, the paper makes solid contribution and extension on a relevant and relatively new (but important) problem.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are positive with this submission. The reviewers agree that this paper is studying a relevant and new problem, and it is well-written. The reviewers also mention some suggestion for motivating the problem and the presentation order. I think the paper can benefit from these suggestions.
Decision: Accept (Poster)