Bandit Social Learning under Myopic Behavior
Authors: Kiarash Banihashem
MohammadTaghi Hajiaghayi
Suho Shin
Aleksandrs Slivkins
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
greedy algorithm
social learning
myopic behavior
learning failures
algorithmic game theory
TL;DR: We analyze exploration failures when myopic agents collectively face a simple multi-armed bandit problem and act in a(ny) way consistent with confidence intervals.

Abstract: We study social learning dynamics motivated by reviews on online platforms. The
agents collectively follow a simple multi-armed bandit protocol, but each agent
acts myopically, without regards to exploration. We allow a wide range of myopic
behaviors that are consistent with (parameterized) confidence intervals for the arms’
expected rewards. We derive stark exploration failures for any such behavior, and
provide matching positive results. As a special case, we obtain the first general
results on failure of the greedy algorithm in bandits, thus providing a theoretical
foundation for why bandit algorithms should explore.

Bandit Social Learning under Myopic Behavior
Kiarash Banihashem University of Maryland, College Park ki kiarash@umd.cm edu
MohammadTaggh Hajiaghayi University of Maryland, College Park sajiagha@umd.cc edu
Suho Shin
Aleksandrs Slivkins Microsoft Research NYC s1i Mlikkins@microson com
University Maryland, College Park suhoshin@umd.co edu
Abstract
We study social learning dynamics motivated by reviews online platforms. The agents collectively follow a simple multi-armed bandit protocol, but each agent myopically, without regards exploration. We allow wide range of myopic behaviors that are consistent with (parameterized) confidence intervals for the arms' expected rewards. We derive stark exploration failures for any such behavior, and provide matching positive results. As a special case, we obtain the first general results on failure of the greedy algorithm in bandits, thus providing theoretical foundation for why bandit algorithms should explore
Introduction
Reviews and ratings are pervasive in many online platforms. customer consults reviews/ratings, then chooses a product and then (often) leaves feedback, which is aggregated by the platform and served to future customers. Collectively, customers face tradeoff between exploration and exploitation, i.e., between acquiring new information while making potentially suboptimal decisions and making optimal decisions using information currently available. However, individual customers tend to act myopically and favor exploitation, without regards to exploration for the sake of the others. On high level, we ask whether/how the myopic behavior interferes with efficient exploration. We are particularly interested in learning failures when only a few agents choose an optimal action.
We distill this issue down to its purest form. We posit that the customers make one decision each and do observe any personalized payoff-relevant information prior their decision, whether public or private. In particular, the customers believe they are similar to one another. They have only two alternative productssexperiinees to choose from, a.k.a., arms, and no way infer anything about one arm from the other. The platform provides each customer with full history on the previous agents [
Concretely, posit Bandit Social Learning (BSL): variant of social learning in which the customers (henceforth, agents) arrive sequentially and follow a simple multi-ane aammi- bandit protocol. Each agent observes full history, chooses arm, and receives reward: Bernoulli random draw whose mean arm-specific and unknown. Initial knowledge (a dataset with some samples of each arm) may be available all agents. When all agents are governed by centralized algorithm, this setting is known as stochastic bandils, a standard and well-understood variant of multi-armed bandits.
'Early versions of our results on the greedy algorithm (Corollary and Theorem 6.1 have been available a book chapter by A. Slivkins [54] Ch. 11]. The authors acknowledge Mark Sellke for proving Theorem 6.] suggesting proof plan version Corollary 3.6 The authors are grateful Mark Sellke and Chara Podimata for hrief collaborations (with A. Slivkins) in the initial stages of this project.
In practice, online platforms provide summaries such as the average score and the number of samples.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Mean rewards
Beliefs
Behavior
Result
fixed
"frequentist"
n-confident
Thm.
3.1
(main),
confidence intervals
Thm.
3.9
(small No).
unbiased/Grreedy Re-pessimsstic
Cor.
3.6
Thm.
0
Bayesian (independent)
Bayesian-unbiased 7)- --BByesian-onfiddne
Thm.
Thm.
b)
Bayesian (correlated) Table 1: Our negative results: learning failures.
Bayesian (and correct)
Bayesian-unbiased
Thm.
6.1
We allow wide range of myopic behaviors that are consistent with observations. Given an arm, consider the confidence interval for its mean reward, parameterized by 1) 2 0: the sample average plus/minus the "confidence term", v1j/ ///tsaallles.... An n)-confident agent evaluates each arm to an index: some number within this arm's confidence interval (and otherwise arbitrary), and chooses an arm with largest index. (Computational implementation of this process irrelevant to our model.) Crucially, the and the agents' behavior given and cannot be influenced by the platform.
This model subsumes the "unbiased" behavior, when the index equals the sample average, well as various "behavioral biases" (see "related work" for citations). Most notably: ""optimism" and "pessimism", when the index is, resp., larger or smaller than the sample average. (These can also be interpreted resp., risk seeking and risk aversion.) The model also allows for probabilistic decisions (via randomized indices), correlated behaviors (when samples from one arm affect the behavioral bias on another), and recency bias (when one favors more recent observations). Further, an agent may treat each arm differently, and different agents may exhibit different biases.
We target the regime when parameter is constant w.r.t. the number of agents T. L.e., the agents' population is characterized by constant 7). We are interested in the asymptotic behavior when T increases, An extreme version of our model, with r log(("), ). is only considered for intuition and sanity checks. Interestingly, this version subsumes two well-known bandit algorithms: UCBI (6) and Thompson Sampling [57 [22, which achieve optimal regret bounds. These algorithms can be seen as behaviors: resp., extreme optimism and probability matching [49 [59], well-known randomized behavior. More "moderate" versions of these behaviors are consistent with 7-confidence as defined above, and are subject to the learning failures described below.
Our results. We are interested in learning failures when all but a few agents choose the bad arm, and how the failure probability scales with the parameter. Our main result is that with c-confident agents, the failure probability is at least -0())) (see Section 3). Consequently, regret is at least Q(T e -0())) for any given problem instance, in contrast with the O(log 7') regret rate obtained by optimal bandit algorithms. Further, the e0())) scaling is the best possible: indeed, regret for optimistic agents is at most O (T e- + n) for a given problem instance (Theorem 4.1 Note that the negative result deteriorates as ry increases, and becomes vacuous when 1) log 7 the upper bound then essentially matches the optimal Ollog T') regret of the UCB algorithm [6]).
We refine these results in several directions. First, if all agents are "unbiased"' the failure probability scales as the difference in expected reward between the two arms (Corollary (.6)). Second, if all agents are pessimistie, then any level of pessimism, whether small or large different across agents, leads to the similar failure probability as in the unbiased case (Theorem 3.10). Third, small fraction of optimists goes a long way! That is, if all agents are n--onfident and even a g-fraction of them are opttimisii then we obtain regret O (T (i()) + n/q) regardless of the other agents
Our results extend to Bayesian agents who have independent priors across the arms and act according to their posteriors. Such agents are consistent with our main model of co-oofident agents, and therefore are subject to the same negative results (Section 5). Further, we focus on Bayesian- -ubbaseed agents and allow arbitrary correlated Bayesian belief' (when the agents make inferences about one arm from the observations on the other). We derive a general result on learning failures, assuming that the mean rewards are actually drawn according to the belief's ())
'Then the confidence interval contains the (true) mean reward with probability at least 2n, A similar result holds even the agents hold different levels of optimism, see Theorem 4.5

---

Mean rewards
Beliefs
Behavior
Result
fixed
"frequentist" confidence intervals
q-optimistic
Thm.
ne n--optimistic, 17 E [7, Mmax
Thm.
small fraction of optimists
Thm.
Table 2: Our positive results: upper bounds on regret.
Our results are summarized in Tables and
Implications for multi-armed bandits. The negative results for unbiased agents be seen as general results on the failure of the greedy algorithm: a bandit algorithm that always exploits. This theoretical foundation for why bandit algorithms should explore and indeed why one should design them. We are not aware of any general results of this nature, whether published or known previously "folklore", which is quite surprising given the enormous literature multi-armed bandits. Therefore, we believe our results fill an important gap in the literature.
How surprising are these results? It has been folklore knowledge for several decades that the greedy algorithm is inefficient in some simple special cases, and folklore belief that this should hold much more generally. However, recent results reveal more complex picture: the greedy algorithm fails under some strong assumptions, but works well under some other strong assumptions (see Related Work). Thus, it has arguably became less clear which assumptions would be needed for negative results and what would be the "shape" and probability of learning failures.
Further, our results on n-confident agents explain why UCB1 algorithm requires extreme optimism, why any algorithm based on narrow (constant-n) confidence intervals is doomed to fail, and also why "pessimism under uncertainty" is not productive approach for exploration.
Novelty and significance. BSL was not well-understood previously even with unbiased agents, as discussed above, let alone for more permissive behavioral models. It was very unclear priori how to analyze learning failures and how strong would be the guarantees, in terms of the generality of agents' behaviors, the failure events/probabilities, and the technical assumptions.
On technical level, our proofs have very little to do with standard lower-bound analyses in bandits stemming from 43 7 These analysis apply any algorithm and prove "sublinear" lower bounds on regret, such as (log T) for a given problem instance and [ ((VTT) ) in the worst case. Their main technical tool is KL-divergence analysis showing that algorithm can distinguish between given tuple of "similar" problem instances. In contrast, we prove linear lower bounds on regret, our results apply a particular family of behaviors/algorihhms. and we never consider tuple of similar problem instances. Instead, we use anti-concentration and martingale tools to argue that the best arm is never played (or played only few times), with some probability. The result correlated beliefs in Section 6 has a rather short but "conceptual" proof which we believe is well-suited for a textbook.
While positive results in Section 4 are restricted to "optimistic" agents, we do not assert that such agents are necessarily typical. The primary point here is that our results on learning failures essentially tight. That said, "optimism" is well-documented behavioral bias (e.g., [50) and references therein). So, a small fraction optimists (leveraged in Theorem 4.5) is not unrealistic.
Our proofs are more involved compared to the standard analysis of the UCB1 algorithm. This is because we cannot make the 7) parameter as large as needed to ensure that the complements of certain "clean events" can be ignored. Instead, we need to define and analyze these "clean events" in more careful way. These difficulties are compounded in Theorem 4.5 our most general result. As far as the statements concerned, the basic result in Theorem 4.1 is perhaps what one would expect to hold,
whereas the extensions in Theorem and Theorem 4.5 are more surprising.
Framing. We target the scenario in social learning when both actions and rewards are observable in the future, and the agents do not receive any other payoff-relevan signals. As in much of algorithmic game theory, we discuss the influence of self-interested behavior on the overall welfare of the system. We consider how such behaviour can cause "learning failures", which is a typical framing in the literature on social learning. From the perspective of multi-armed bandits, we investigate the failures of the greedy algorithm, and more generally any algorithm that operates on narrow confidence intervals. We do not attempt to design new algorithms, as version of UCB1 is proved optimal.
3

---

Map of the paper. Section defines our model. Section 3 derives the learning failures. Section provides positive results for optimistic agents. Section and Section 6 handle agents with Bayesian beliefs. Most proofs are moved to the supplement.
Related work. A vast literature social learning studies agents that learn over time in shared environment. A prominent topic is learning failures such as ours. Models vary across several dimensions: e.g,, the information acquired/ransmmitedd, the communication network, agents' life-span and decision rules, etc. All models from prior work are very different from ours. In the supplement, separate our model from several most relevant ones: "sequential social learning" [27]. "strategic experimentation" 33 networked myopic learners 8 46 and misspecified belief's [31 15 25 44).
Positive results for the greedy bandit algorithm 33
focus contextual bandits, an extension
of stochastic bandits where a payoff-relevan signal (contexi) is available before each round. Equiva- lently, each agent in BSL receives such signal along with the history (incl. all previous signals). Very strong assumptions are needed: linearity of rewards and diversity of contexts. A similar result holds for BSL with private signals, under different (and also very strong) assumptions
structure and diversity []] In all this work, agents' diversity substitutes for exploration, and structural assumptions allow aggregation across agents. Moreover, the greedy algorithm obtains o(T)) regret in various scenarios with a very large number of near-optimal arms 13 35 e.g., in Bayesian bandits with K >> VT arms and independent uniform priors. We focus on a more basic model, with only two arms and contexts, where all these channels are ruled out.
Learning failures for the greedy algorithm are derived for bandit problems with I-dimensional action spaces under (strong) structural assumptions: e.g., dynamic pricing with linear demands [30, [2] and dynamic control in a (generalized) linear model [4] (4). In all these results, the failure probability is only proved positive, but not otherwise characterized.
Incentivized exploration takes a mechanism design perspective on BSL, whereby the platform strives to incentivize individual agents to explore for the sake of the common good. In most of this work, starting from 441 19], the platform controls the information flow, egg,, can withhold history and instead issue recommendations, and uses this information asymmetry to create incentives; see (55), target stochastic bandits as the underlying do. In [3], the platform constructs (very) particular communication
[54] Ch. 11] for surveys In particular, 48
53
learning problem, same network for the agents, and then the agents engage in BSL on this network.
Non- Non-Bayesian models of behavior are prominent in social learning, starting from DeGroot [2]]: agents use variants of statistical inference and/or naive rules-of-thumb to infer the state of the world. In particular, our model of n--oofident agents is essentially special case of rease decision theory" 26). Well-documented behavioral biases allowed by our model include: optimism and pessimism (e.g., [50] and [18 [2], resp.. and references therein), risk aversion/risk seeking [36. 10) recency bias (e.g., (24) and references therein), randomized decisions (with theory tracing back to Luce 47) ), and probubility matching more specifically (49 59).
Our perspective of multi-arme armed bandits is very standard in machine learning theory: we consider asymptotic regret rates without time-discounting. The vast literature on regret-minnnizing bandits is summarized in books [17 54 45). Stochastic bandits is standard, basic version with i.i.d. rewards
and no auxiliary structure. Most relevant are the UCB1 1 algorithm ( Thompson Sampling [57 52
(particularly the "frequentist" analyses thereof
38 ) and the lower-bound results 43
2 Our model and preliminaries
Our model, called Bandit Social Learning, is defined as follows. There are T rounds, where T e N is the time horizon, and two arms (i.e., alternative actions). We use T and [2] to denote the set of rounds and arms, respectively[1 In each round E [7], a new agent arrives, observes history hist, (defined below), chooses an arm a, E [2]. receives reward r; E [0. 1] for this arm, and leaves forever. When given arm a E [2] is chosen, its reward is drawn independently from Bernoulli distribution
Alternatively, the agents ohserve full history, but the platform uses payments to create incentives Throughout, denote [n]] 21,2, ... n }. for any N.
23

---

with mean jaa E [0. 1]. The mean reward is fixed over time, but not known to the agents. Some initial data is available to all agents, namely No samples of each arm a E [2]. We denote them ra, E [0, 1], E [No]. The history in round t consists of both the initial data and the data generated by the previous agents. Formally, it is tuple of arm-reward pairs,
hist, == ((a, r..))
[2]. E [No]: (a.,r,): s s 11)
We summarize the protocol for Bandit Social Learning as Protocol |
Protocol I: Bandit Social Learning
Problem instance: two arms E [2] with (fixed, but unknown) mean rewards Pr, M2 E [0, 1];
Initialization: hist + No samples of each arm }; for each round ( = 1, .., do
agent l arrives, observes hist and chooses
a, E [2]
reward ra E [0, 1] is drawn from Bernoulli distribution with mean paas
new datapoint (a;, rt) is added to hist
Remark 2.1. The initial data-points represent reports created outside our model, e.g., by ghost shoppers or influencers, and available before the products enter the market. One could interpret them as simple "frequentist" representation for the initial beliefs of the agents, with Ng as the beliefs' "strength". We posit No 2 to ensure that the arms' average rewards are always well-defined.
the agents were controlled by an algorithm, this protocol would correspond to stochastic bandits with two arms, the most basic version of multi-armed bandits. A standard performance measure in multi-armed bandits (and online machine learning more generally) is regret, defined as
Regret(T) == == /z - E EiE'y Mas
(2.1)
where μ² max(u1, p2) is the maximal expected reward of an arm.
Each agent / chooses its arm o, myopically. Each agent endowed with some (possibly randomized) mapping from histories to arms, and chooses an arm accordingly. This mapping, called behavioral type, encapsulates how the agent resolves uncertainty on the rewards. More concretely, each agent maps the observed history hist, to an index Inde, E IR for each arm a E [2], and chooses an arm with a largest index. The ties are broken independently and uniformly at random.
We allow for a range of myopic behaviors, whereby each index can take an arbitrary value in the (parameterized) confidence interval for the corresponding arm. Formally, fix arm E [2] and round t E [T]. Let na,,r denote the number of times this arm has been chosen in the history hist, (including the initial data), and let fa.. denote the corresponding average reward. Given these samples, standard (frequentist, truncated) upper and lower confidence bounds for the arm's 's mean reward Pa (UCB and
LCB, for short) are defined follows:
==min UCB =- min 1, Pa,t + V n//na
and LCB == max (0,
0, Pu.tt V /n/maax
(2.2)
where 2 0 is parameter. The interval [LCB", UCB", will be referred to as nyconfidence interval. Standard concentration inequalities imply that Me contained in this interval with probability least
1 - 2 221 (where the probability is over the random rewards, for any fixed value of p.). We allow the index to take an arbitrary value in this interval:
Inda, [LCB",, UCB".. for each arm E [2].
(2.3)
We refer such agents as confiident 17 > 0 will be a crucial parameter throughout.
On special cases. Our model accommodates a number behavioural biases. Most notably: unbiased agents, who set Ind,,: Pa,t, n-optimiistic agents, who set Ind,,: UCB" and 17- pessimistic agents who Ind,,t LCB". Unbiased agents formally correspond to the greedy algorithm, whereas extreme optimism, i.e., n-ppimmism with 17 ~ log(T), corresponds to UCB1 algorithm 6
"Our results on upper bounds (Section 4 and Bayesian learning failures (Section 6 allow each arm to have arbitrary reward distribution on [0, 1]. We omit further mention of this to simplify presentation.
5

---

Our model also allows version of Thompson Sampling in which the posterior samples are truncated the n--onfidence interval. [ More generally, we allow Bayesian agents that preprocess observations to Bayesian posterior, and use the latter to define their indices. See the supplement for more details.
Preliminaries. When fi, A2 are fixed (not drawn from a prior), we posit μ41 J22, i.e., arm 1 is the good arm, and arm 2 is the bad arm. Our guarantees depend on quantity A := μu 422 called the gap (between the two arms). It is a very standard quantity for regret bounds in multi-armed bandits.
We use the big-O notation to hide constant factors. Specifically, O(X) and (XX) mean, resp.. "at most co X"" and "at least Cu XX" for some absolute constant Co 0 that is not specified in the paper. When and cu depends on some other absolute constant c that we specify explicitly, we point this out in words and/or by writing, resp., Ox(X) and (X).. As usual, (xX) ) is shorthand for "both O(X) and ((X)", and writing (x( emphasizes the dependence on c.
Algorithms UCB1 and Thompson Sampling achieve regret
(2.4) This regret rate is essentially optimal among all bandit algorithms: it is optimal up to constant factors for fixed > O, and up to (log T' factors for fixed T' (see "related work" for citations).
Regret(T) S O( min( 1/4, VT) ) logT").
A key property of a reasonable bandit algorithm is that Regret(T)/TT 0; this property is also called no-regret. Conversely, algorithms with Regret(T) S2()) are considered very inefficient.
3 Learning failures
We are interested in learning failures when all but a few agents choose the bad arm. More precisely, we define the n-sampling failure an event that all but at most n agents choose the bad arm.
We make two technical assumptions:
mean rewards satisfy < #22 < f1 < 1 - c for some absolute constant E (0, 1/2),
(3.1)
the number of initial samples satisfies No 2 64 1/c.
(3.2)
The meaning of (3.1) is that it rules out degenerate behaviors when mean rewards are close to the known upper/lower bounds. The big-O notation hides the dependence the absolute constant c, when and if explicitly stated so. Assumption (3.2) ensures that the c-confidence interval is proper subset of [o, 1] for all agents; sidestep this assumption later in Theorem 3.9
Our main result allows arbitrary //confident agents and asserts that O-sampling failures happen with probability least Ptail ~ e -(n),, This a stark failure when n is a constant relative T. Theorem 3.1 (n-connident agents). Suppose all agents are n-confident, for some fixed 1j > 0. Make assumptions 3.1 and 3.2). Then the O-sampling failure occurs with probability at least"
Prail lo( A + v//No ) Oo(n + No4"), where
A
P1
42
(3.3)
Consequently, Regret (7) 2 A Ptail T.
We emphasize generality: the agents can exhibit any behaviors consistent with c-condideece, possibly different for different agents and different arms. From multi-armed bandit perspective, the theorem implies that bandit algorithms consistent with 7/-coffidence cannot have regret sublinear in T.
The guarantee in Theorem 3.1 deteriorates the parameter 17 increases, and becomes vacuous when (T). This makes sense, as this regime of v is used in UCBI algorithm.
Discussion 3.2. Assumption (3.2) is innocuous from the social learning perspective: essentially, the agents hold initial beliefs grounded in data and these beliefs are not completely uninformed. From the bandit perspective, this assumption is more substantive, as an algorithm can always choose to discard data. In any case, we remove this assumption in Theorem 3.9 below.
Remark 3.3. A weaker version of (3.2), namely No 2 17, is necessary guarantee an n-sampling failure for any rp-onfident agents. Indeed, suppose all agents are nooptimistic for arm 1 (the good arm), and r-pessimistic for arm (the bad arm). If No < n, then the index for arm is 0 after the initial samples, whereas the index of arm 1 is always positive. Then all agents choose arm 1.
$ For 17 ~ log T, this coincides with Thompson Sampling with very high probability. Throughout the paper, we use the notation O: to hide the dependence the absloute constant

---

Next, we spell out two corollaries which help elucidate the main result. Corollary 3.4. If the gap is sufficiently small, A < O (1/vNo). then Theorem 3.1 holds with
Pratl Sec( A + /n/No) -0.(1)
(3.4)
Remark 3.5. The assumption in Corollary 3.4 is quite mild in light of the fact that when A > a (To(())NN) ). the initial samples suffice to determine the best arm with high probability. Corollary 3.6. If all agents are unbiased, then Theorem 3.7 holds with rj and
Presl = =2 (A) -Oa(No 2²)
(3.5)
22 (A)
(A<OO1/VN))
Remark 3.7. A trivial failure result for unbiased agents relies on the event & that all initial samples of arm 1 (i.e,, the good arm) are realized as O. This would indeed imply a O-sampling failure (as long as at least one initial sample of arm 1 is realized to 1), but the event & happens with probability exponential in No, the number of initial samples. In contrast, in our result Preil only depends on No through the assumption that A < O (1/vNo)
Discussion 3.8. Corollary 3.6 can be seen as general result the failure of the greedy algorithm.
This is the first such result with a non- non-trivial dependence on No, to the best of our knowledge.
We can remove assumption 3.2 and allow a small No if the behavioral type for each agent also satisfies natural (and very mild) properties of symmetry and monotonicity:
(PI) (symmetry) if all rewards in hist, are O, the two arms are treated symmetrically TO
(P2) (monotonicity) Fix any arm a [2]. any t-round history in which all rewards are 0 for both arms, and any other f-round history H' that contains the same number of samples of arm a such that all these samples have reward 1. Then
Pr Pr[a: = a hist; H' 2 Pr Pr[a: a hist, = H..
(3.6)
Note that both properties would still be natural and mild even without the "all rewards are zero" clause. The resulting guarantee on the failure probability is somewhat cleaner.
Theorem 3.9 (small No). Fix v) 2 O, assume Eq. (. and let No E [1,N"], where N = [64n/c2 + 1/c]. Suppose each agent is n-confident and satisfies properties (P1) and (P2). Then n-sampling failure, n = N No. occurs with probability at least
Ptail = Pcl 2N ) -Pc( (0o()))))))
(3.7)
Consequently, (T)ret(T)& 2 A Prail (T-n). n).
If all agents are pessimistic, we find that any levels of pessimism, whether small or large or different across agents, lead to O-sampling failure with probability Pc(A)., matching Corollary 3.6 for the unbiased behavior. This happens in the (very reasonable) regime when
(o( No < <(1/A3).
(3.8)
Theorem 3.10 (pessimistic agents). Suppose each agent E [T'] is The Ti-pessimistic, for some πe 2 0. Suppose assumptions (3.7) and (.2) hold for = max Ut- Then the O-sampling failure occurs
with probability lower-bounded by Eq. 3.5). Consequently, Regret(T) 2 (2((2)) - -Oe(No A?).
We allow extremely pessimistic agents (1) ~ log T), and the pessimism levels т can vary across
agents While the relevant parameter 1) max Te, the failure probability in (3.5) does not contain the e term. In particular, Ptas1 = 2(A) when N2 < O(1AA)). However, the dependence
on 7) "creeps in" through assumption 3.2 i.e., that No > (r()))
Proof Overview. We first show that the average reward of arm 1 (the good arm), is upper bounded by some threshold Q1- This is only guaranteed with some probability and only when this arm is sampled exactly N times, for particular N > No. Next, we lower bound the average reward of arm (the bad arm): we show that with some probability it is always above some threshold E M2). Focus
Tha is, the behavioral type stays the same if the arms' labels switched.
7

---

on the round t" when the good arm is sampled for the N-th time (if this ever happens). If both of these events hold, from round tn onwards the bad arm will have larger average reward by constant margin 922 T1- Consequently, as we prove, the bad arm has a larger index, and therefore gets chosen.
The details of this argument differ from one theorem to another. For Theorem 3.1
it suffices to set the thresholds 92, q1 such that 92 41 (//oo))). For Theorem 3.10 we use a more involved argument: since the LCB of an arm increases when it is played, playing this arm only strengthens the preference of pessimistic agents for this arm. We are therefore less constrained in the choice of q1. 92 and we can prove that a learning failure occurs whenever 91 < 92 11| In both proofs, we also require qi and Q2 be close [1 and μ2, resp.. so as to lower-bound the probability of the two desirable events. For Theorem 3.9, the case of small No. our analysis becomes more subtle. We can (in some sense) simplify the two events defined above, but we need to introduce third event: if arm is chosen by at least n agents (for a suitably defined n). then arm 2 is chosen by agents before arm 1 is. The crux is "deterministic" argument which derives failure when all three events hold jointly.
To formalize, we represent realized rewards of each arm a as written out in advance on a "tape", where each entry is an independent Bernoulli draw with mean pa. 12 The i-th entry is returned as reward when and if arm a is chosen for the i-th time. (We start counting from the initial samples, which comprise entries E (Nol.) We analyze each arm separately (and then invoke independence).
We use some tools from probability: a sharp cnti-concentration incquality for arm and a martingale argument for arm 2. Let (XI))eN be a sequence of i.i.d. Bernoulli random variables with mean p E [c, - c). for some absolute constant e E (0, 1/2). The anti-concentration is as follows:
(Vn 2 1/c, q E (c/8, p)) The martingale argument leads to this:
Pr Pr En
X S a
2 Q 0(((p-))))
(3.9)
Vy E (0)
Pr Pr[V vr[v~21: 1:
1 x E X; x 2 P ()) 9)-
(3.10)
We each tool to the tape for the respective arm, and lower hound the probability of the desirable event.
While the novelty is mainly in how
these tools, the tools themselves not very standard. Eq. C.II follows from the anti-concentration inequality in [6] and a reverse Pinsker inequality in
28 More standard anti-concentration results via Stirling's 's approximation lead to an additional factor of 1/vii on the right-hand side of (C.1). For Eq. (C.2), we introduce an exponential martingale and relate the event in Eq. (C.2) to deviation of this martingale. We then use Ville's 's inequality (a
version of Doob's 's martingale inequality) to bound the probability that this deviation occurs.
Upper bounds for optimistic agents
We upper-bound regret for optimistic agents: we match the exponential-in-y scaling from Corol- lary [34] and then extend this result to different behavioral types. On a technical level, we prove three regret bounds of the same shape 1..1). but with a different & term. (The unified presentation emphasizes this similarity.) Throughout, = P1 P2 denotes the gap between the two arms.
Theorem 4.1. Suppose all agents are nopptimistic, for some fixed 1j > 0. Then, letting = 7).
RTgret(T) s 0 (T-e (O (2()) A(1 log 1/2) 0/A).
(4.1)
Discussion 4.2. The main take-away is that the exponential-in-- scaling from Corollary [344is tight for n-optimistic agents, and therefore the best possible lower bound for 77-confident agents. This result holds for any given No. the number of initial samples [3 Our guarantee remains optimal in the "extreme optimism" regime when 1 log(T), matching the optimal regret rate, O (og(T))A).
What if different agents can hold different behavioral types? First, let allow agents to have varying amounts of optimism, possibly different across arms and possibly randomized.
Definition 4.3. Fix Mmax 2 1) > 0. An agent E [Z'] is called [17, 7max wwxx l-ppimmisiic if its index Inda, lies in the interval UCB" a, UCB? J. for each arm a E [2].
We also require 91 > v / No to ensure that the confidence lower bounds are not truncated to zero. This an equivalent (and well-known) representation of rewards in stochastic bandits.
For ease of exposition, do not track the improvements in regret when No becomes larger.
8

---

We show that the guarantee in Theorem 4.1 is robust to varying the optimism level "upwards".
Theorem 4.4 (robustness). Fix Mmaa 2 1 > Suppose all agents are [n, Mmax -optimistic. Then regret bound 4.7 holds with +b = Mmmx
Note that the upper bound Maax has only mild influence on the regret bound in Theorem 4.4
Our most general result only requires a small fraction of agents to be optimistic, whereas all agents are only required to be Tmax-confident (allowing all behaviors consistent with that).
Theorem 4.5 (recurring optimism). Fix Tmmax 2 1j > O. Suppose all agents are Tmax confideon, Further, suppose each agent's behavioral type is chosen independently at random so that the agent is [1) Mmax J-ptimissic with probability at least 9 > 0. Then regret bound (.1 holds with + = 7mmax
1 Thus, with even small fraction of optimists, 9 A.o(T): the behavioral type of less optimistic agents does not have much impact regret. In particular, it does not hurt much if they become very pessimistic. A small fraction of optimists goes long way! Further, a small-bute butal-bbt-constam fraction of extreme optimists, i.e., 7, Mmax log(T') in Theorem 4.5 yields optimal regret rate, (og(T)/A)
5 Learning failures for Bayesian agents
In this section, we posit that agents are endowed with Bayesian beliefs. The basic version that all agents believe that the mean reward of each arm is initially drawn from uniform distribution on [0, 1]. (We emphasize that the mean rewards are fixed and nor actually drawn according to these beliefs.) Each agent t computes a posterior Pa, for Pe given the history hist,, for each arm [a].
and maps this posterior to the index Inda,: for this arm 14
The basic behavior is that Inda.t the posterior mean reward, E [P,,, We call such agents Bayes-unbiased Further, we consider Bayesian version of co-oodiidntt agents, defined by
Inda,t E [Qa,r(S), Qo,(( -)] for each arm a E [2].
(5.1)
where (-)(()) denotes the quantile function of the posterior Pa. and Ç E 1/2) is fixed parameter (analogous to y elsewhere). The interval in Eq. (5.T) is a Bayesian version of c-confidence intervals. Agents t that satisfy Eq. (5.1) are called G-Bayes-confident
We allow more general belief's given by independent Beta distributions. For each arm E [2]. all agents believe that the mean reward H.a is initially drawn as an independent sample from Beta distribution with parameters Ou, 32 E N. Our results are driven by parameter M m Oa + Sa- We refer to such beliefs as Beta-beliefs with strength M. The intuition is that the prior on each arm can be interpreted as being "based on" ag + Ba samples from this arm
Our technical contribution here is that Bayes-unbiased (resp., (-Bayes-confident agents are 1/- confident for suitably large y, and therefore subject the learning failure in Theorem 3.1
Theorem 5.1. Consider Bayesian agent that holds Beta-beliefs with strength M 2 1.
(a) the agent is Bayes-unbiased, then it is 11-cofident for some 1) O(M/vNo).
(b) If the agent is (-Bayes-confient, then it is r-cooffidett for 7) O M/ /No + In(1/))) Discussion 5.2. Beta-beliefs may be completely unrelated the actual mean rewards. If Ç and M are constants relative to T, the resulting is constant, too. Our guarantee is stronger if the beliefs are weak (i.e,, M is small) or are "dominated"" by the initial samples, in the sense that No > (2M2). Discussion 5.3. (-Bayes-confident agents subsume Bayesian version of optimism and pessimism, where the index Inda,: is defined as, resp., Qo (1 () and QC,+(C), as well as all the Bayesian versions of all other behaviorial biases discussed previously as special cases of n-confidence.
Bayesian model with arbitrary priors
We consider mhyesian-unbiasee agents in "fully Bayesian" model such that the mean rewards are actually drawn from prior. We are interested in Bayesian probability and Bayesian regret, i.e., resp..
" "Note that the Bayesian update for agent t does not depend on the beliefs of the previous agents.
Moore precisely, any Beta distribution with integer parameters (a, (3) can be seen as a Bayesian posterior obtained by updating uniform prior [0, with + 3 2 data points.

---

probability and regret in expectation over the prior. We focus on learning failures when the agents never choose an arm with the largest prior mean reward (as opposed to an arm with the largest realized mean reward, which is not necessarily the same arm). We do not explicitly allow initial samples (i.e., we posit No- = here), because they are implicitly included in the prior.
Compared to Section S the benefit is that we allow arbitrary priors, possibly correlated across the Iwo arms, Further, our guarantee does not depend on the prior, other than through the prior gap Elui - p2], and does not contain any hidden constants. On the other hand, the guarantees here are only in expectation over the prior, whereas the ones in Section 5 hold for fixed Ml, H2. Also, our result here is restricted to
agents.
Theorem 6.1. Suppose the pair (μ1, (12) is initially drawn from some Bayesian prior P such that Elua] > E[ Assume that all agents are Bayesian unbiiased, with beliefs given by P. Then with Bayesian probability at least Elp U2), the agents never choose arm 2.
Proof. W.l.o.g.. assume that agents break ties in favor of arm 2. In each round f,, the key quantity is Z = Eip- - P2 hist,]. Indeed, arm is chosen if and only if Ze I 0. Let r be the first round when arm 2 is chosen, or T 1 if this never happens. We martingale techniques to prove that
E[Z+] = Elui - 12]-
(6.1)
We use the optional stopping theorem (OST). We observe that T stopping time relative to H. = hist, & E [T' + 1]). and (4 : [T'+ 1]) is martingale relative to H. [6] OST asserts
that E Z- E[Z1 for any martingale Z₁ and any bounded stopping time т. Eq. 66.1
follows
because E Z = Elpp [2) On the other hand, by Bayes' theorem it holds that
E| [ = Pr 7 S E[Z 1 TT) Pr(T > 7] E|Z, [TTT]
(6.2)
Recall that < T implies that arm 2 is chosen in round which in turn implies that Z, S 0. It
follows that ET,,, T S T - 0. Plugging this into Eq. (6.2 we find that
Elu1 μ2 E Pr[T> T Pr armm 2 never chosen].
As a corollary, we derive a O-sampling failure, leading to S?(T) Bayesian regret. Specifically, the agents start out playing arm (because it has higher prior mean reward), and never try arm 2 when is in fact the best arm. This happens whenever the prior is independent across arms and has a positive density on the entire [0, IJ interval (see the supplement for the exact statement). Note that is a (much) more general family of priors compared to independent Beta-priors allowed in Section
Conclusions and open questions
We examine the dynamics of social learning in a multi-armed bandit scenario, where agents sequen- tially choose arms and receive rewards, and observe the full history of previous agents. For a range of agents' myopic behavior, we investigate how they impact exploration, and provide tight upper and lower bounds on the learning failure probabilities and regret rates. In particular, we obtain the first general results the failure of the greedy algorithm in bandits.
With our results as "departure point", one could study ESL more complex bandit models with many arms and/or some known structure of rewards that the agents' myopic behaviour would account for 17 The greedy algorithm fails for some structures (e.g., our current model) and works well for some others (e.g.. for linear contextual bandits with smoothed contexts [3] [5), when all arms have the same rewards). The whole world is in between these two extremes. It is not at all clear which structures would cause learning failures and which would enable learning, and which structures would be amenable to analysis, one way or another.
8 Acknowledgements
This work is partially supported by DARPA QUICC NSF and AF:Small #2218678, #41142
1he latter follows from a general fact that sequence E[x histc), E [T' 1] a martingale w.r.t. 7/ for any random variable X with E. [[X]] < co. It known as Doob martingale for X. 17,, E.g.. linear, convex, Lipschitz and combinatorial structures well-studied, see books 17 34 45
10

---

References
[1] D. Acemoglu, A. Makhdoumi, A. Malekian, and Ozdaglar. Learning From Reviews: The Selection Effect and the Speed of Learning. Econometrica, 2022. Working paper available since 2017.
[2] S. Agrawal and N. Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem. In 25nd Conf. on Learning Theory (COLT), 2012.
[3] Agrawal and Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[4] S. Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. J. of the ACM, 6465):301133::24, 2017. Preliminary version in AISTATS 2013.
[5] Audibert and Bubeck. Regret Bounds and Minimax Policies under Partial Monitoring, J. of Machine Learning Research (JMLR). 11:2785-288 2236, 2010. Preliminary version in COLT 2009.
[6] Auer, N. Biaachi and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, (11223))235-222 2002.
[7] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1))48-77, 2002. Preliminary version in 36th IEEE FOCS, 1995.
[8] V. Bala and S. Goyal. Learning from neighbours. Review of Economic Studies, 65(3):595-621,
1998.
[9] A. V. Banerjee. A simple model of herd behavior. Quarterly Journal of Economics, 107: 797-817, 1992.
[10] N. Barberis and R. Thaler. A survey of behavioral finance. In Handbook of the Economics of Finance, volume 1, pages 1053-1128. Elsevier, 2003.
[11] H. Bastani, M. Bayati, and K. Khosravi. Mostly exploration- algorithms for contextual bandits. Management Science, 67(3):1329-1344) 2021. Working paper available on arxiv org since 2017.
[12] M. Bateson. Optimistic and pessimistic biases: a primer for behavioural ecologists. Current Opinion in Behavioral Sciences, 12,,111,,,,00000
[13] M. Bayati, N. Hamidi, R. Johari, and K. Khosravi. Unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms. In 33rd Advances in Neural Information Processing Systems (NeurIPS), 2020.
[14] Bikhchandani, D. Hirshleifer, and I. Welch. Theory Fads, Fashion, Custom, and Cultural Change as Informational Cascades. Journal of Political Economy, 100(5):992-0026 1992.
[15] A. Bohren and D. N. Hauser. Learning with Heterogeneous Misspecified Models: Characteriza- tion and Robustness. Econometrica, 396))3322--0777, Nov 2021.
[16] Bolton and C. Harris. Strategic Experimentation. Econometrica, 67(2):349-374, 1999.
[17] S. Bubeck and N. Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi- Munti--rmed Bandit Problems. Foundations and Trends in Machine Learning, 5(1):1-
122, 2012. Published with Now Publishers (Boston, MA, USA). Also available https: hitps://arxivy http://axxvvvoo/./// abs/1204.57221
[18] E. C. Chang. editor. Optimism and pessimism: Implications for theory, re- search, and practice.
American Psychological Association, 2000. See
https://www. apa. org/ trrg/pbbs/booke /40kk//33154A for the table of contents.
[19] Y.-K. Che and Hörner. Recommender systems as mechanisms for social learning. Quarterly Journal of Economics, 133(2):871-925, 2018. Working paper since 2013, titled 'Optimal design for social learning'.
[20] B. Chen, P. I. Frazier, and D. Kempe. Incentivizing exploration by heterogeneous users. In Conf. on Learning Theory (COLT), pages 798-818, 2018.
[21] M. DeGroot. Reaching Consensus. Journal of the American Statistical Association, 69 18-11, 1974.
[22] A. den Boer and B. Zwart. Simultaneously learning and optimizing using controlled variance pricing. Management Science, 7703)777 2014.

---

[23] P. Frazier, D. Kempe, J. M. Kleinberg, and R. Kleinberg. Incentivizing exploration. In ACM Conf. on Economics and Computation (ACM-EC), pages 5-22, 2014.
[24] D. Fudenberg and D. K. Levine. Learning with recency bias. Proceedings of the National Academy of Sciences, 111 111:10826-1082,, 2014.
[25] D. Fudenberg, G. Lanzani, and P. Strack. Limit Points of Endogenous Misspecified Learning. Econometrica, 3913):1065--1999 May 2021.
[26] I. Gilboa and D. Schmeidler. Case-Based Decision Theory. The Quarterly Journal of Economics,
1 110(3):005-633 63390005566,,66 08 1995.
[27] B. Golub and E. D. Sadler. Learning in social networks. In Y. Bramoullé, A. Galeotti, and B. Rogers, editors, The Oxford Handbook of the Economics of Networks. Oxford University Press, 2016.
[28] Götze, H. Sambale, and A. Sinulis. Higher order concentration for functions of weakly dependent random variables. Electronic Journal of Probability, 24:1-19, 2019.
[29] L. Han, D. Kempe, and R. Qiang. Incentivizing exploration with heterogeneous value of money,
In 1 11th Intl. Conf. on Web and Internet Economics (WINE), pages 370-383, 2015.
[30] M. Harrison, N. B. Keskin, and A. Zeevi. Bayesian dynamic pricing policies: Learning and earning under a binary prior distribution. Management Science, 58(3):570-586, 2012.
[31] P. Heidhues, B. Koszegi, and P. Strack. Unrealistic expectations and misguided learning. Econometrica, 86(4): 159-11141 2018.
[32] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963.
[33] J. Hörner and A. Skrzypacz. Learning, experimentation, and information design. In B. Honoré, A. Pakes, M. Piazzesi, and L. Samuelson, editors, Advances in Economics and Econometrics:
I 1th World Congress, volume page 63 63-98. Cambridge University Press, 2017.
[34] N. Immorlica, J. Mao, A. Slivkins, and S. Wu. Incentivizing exploration with selective data disclosure. In ACM Conf. on Economics and Computation (ACM-EC) EC), pages 647-648, 2020. Working paper available https: : / //arx//vvvvv///////////////aaava
[35] M. Jedor, J. Louëdec, and V. Perchet. Be greedy in multi-armed bandits, 2021. Working paper, available on sttps://arxiss wwwp:/rgg/////oeteoooo 2200 01086.
[36] D. Kahneman and A. Tversky. Judgment under uncertainty: Heuristics and biases. Cambridge University Press. 1982.
[37] S. Kannan, Morgenstemn A. Roth, B. Waggoner, and Z. S. Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems (NIPS), pages 2231-2241 2018.
[38] 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.
[39] G. Keller, S. Rady, and M. Cripps. Strategic Experimentation with Exponential Bandits. Econometrica, 73(1):39-6) (9))))9-68,,200 2005.
[40] N. B. Keskin and A. Zeevi. On incomplete learning and certainty-equiivllnne control. Oper. Res., 66(4): 136-1167, 2018.
[41] I. Kremer, Y. Mansour, and M. Perry. Implementing the "wisdom of the crowd". J. of Political Economy, 12265)9988-1012, 2014. Preliminary version in ACM EC 2013.
[42] T. Lai and H. Robbins. Iterated least squares in multiperiod control. Advances in Applied Mathematics, 111:50073, 1982.
[43] T. L. Lai and H. Robbins. Asymptotically efficient Adaptive Allocation Rules. Advances in Applied Mathematics, 6:4-22, 1985.
[44] G. Lanzani. Dynamic Concern for Misspecification, 2023. Working paper.
[45] Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
12

---

[46] D. Lazer and A. Friedman. The network structure of exploration and exploitation. Administrative Science Quarterly, 52:667-694, 2007.
[47] R. D. Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, New York, NY, USA, 1959.
[48] Y. Mansour, A. Slivkins, and V. Syrgkanis. Bayesian incentive- comppibe bandit exploration. Operations Research, 68(4): 132-)111321111,, 2020. Preliminary version in ACM EC 2015.
[49] J. L. Myers. Probability learning and sequence learning. In W. Estes, editor, Handbook of Learning and Cognilive Processes: Approuches to Human Learning and Motivation, pages 171-205. Erlbaum, Hillsdale, NJ, 1976.
[50] M. Puri and D. T. Robinson. Optimism and economic choice. Journal of Financial Economics, 86(1):71-99) 2007.
[51] M. Raghavan, A. Slivkins, J. W. Vaughan, and Z. S. Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM on Computing (SICOMP), 52(2):487 2023. Preliminary version at COLT 2018. Working paper available at arxiv. org/abs abs/a0/5. 20bb//2005.0224........
[52] D. Russo, B.
Van Roy. A. Kazerouni, I. Osband, and Z. Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-9,, 2018. Published with Now Publishers (Boston, MA, USA). Also available at https: //arxiv www//os///a/aaeeeo//oooeee aabs/1707.000
[53] M. Sellke and A. Slivkins. The price of incentivizing exploration: A characterization via thompson sampling and sample complexity. Operations Research, 71(5), 2022. Preliminary version in ACM EC 2021.
[54] 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 https::///// //arxiv./.iivve/ orgooog////... /111/994477....
07272. Latest online revision: Jan 2022.
[55] A. Slivkins. Exploration and persuasion.
Echenique, N. Immorlica, and Vazirani, editors, Online and Matthingg-asseee Market Design. Cambridge University Press, 2023. Also available at stttp:/ssivvee
wwm/coomoooooooo httl//ook/BBBt warck/xxplPerss. .
[56] L. Smith and P. Sørensen. Pathological outcomes of observational learning. Econometrica, 68: 371-398, 2000.
[57] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):85-294,, 1933.
[58] J. Ville. Etude critique de la notion de collectif. Bull. Amer. Math. Soc, 45(11):824, 1939.
[59] N. Vulkan. An economist's perspective on probability matching. Journal of Economic Surveys, 14:101-118, 2000.
[60] I. Welch. Sequential sales, learning, and cascades. The Journal of finance, 47:695-732, 1992.
[61] A. R. Zhang and Y. Zhou. On the non-asymptotic and sharp lower tail bounds of random variables. Stat, 91)xe314, 2020.
13

---

SUPPLEMENTARY MATERIALS FOR "BAYESIAN BANDIT SOCIAL LEARNING UNDER MYOPIC BEHAVIOR"
The supplement contains the proofs, as well as detailed discussion of related work on social learning.
Contents
Related Work on Social Learning
15
B Preliminaries: Reward-Tape
15
Proofs from Section Learning Failures
16
D Proofs from Section 4
Upper Bounds for Optimistic Agents
22
Proofs from Section
3 Learning Failures for Bayesian Agents
25
The corollary from Section 6
26
14

---

A Related Work on Social Learning
vast literature on social learning studies agents that learn over time in shared environment. prominent topic is the presence or absence of learning failures such ours. Models vary across several dimensions, such as: which information is acquired or transmitted, what is the communication network, whether agents are long- lived or only act once, how they choose their actions, etc. Below we discuss several lines of work that are most relevant.
14 561, agents observe private signals, but only the chosen actions observable in the future; see Golub and Sadler [27] for a survey. The social planner (who chooses agents' actions given access to the knowledge of all previous agents) only needs to exploit, i.e., choose the best action given the previous agents' signals, whereas in our model it also needs to explore. Learning failures are (also) of primary interest, but they occur for an entirely different reason: restricted information flow, ie., the fact that the private signals are not observable in the future.
In "sequential social learning", starting from g
60
"Strategic experimentation". starting from Bolton and Harris [T6] and Keller al. 39 studies long-lived learning agents that observe both actions and rewards of one another; see Hörner and Skrzypacz [3) for survey. Here, the social planner also solves a version of multi-armed bandits, albeit a very different one (with time-discounting. "safe" arm that is completely known, and "risky" arm that follows stochastic process). The main difference is that the agents engage in a complex repeated game where they explore but prefer to free-ride on exploration by others.
Bala and Goyal [8] and Lazer and Friedman 46) consider network of myopic learners, all faced with the same bandit problem and observing each other's s actions and rewards. The interaction protocol is very different from ours: agents are long-lived, act all at once, and only observe their neighbors on the network. Other specifics are different, too. Bala and Goyal [ makes strong assumptions on learners' beliefs, which would essentially cause the greedy algorithm work well in BSL. In Lazer and Friedman [46), each learner only retains the best observed action, rather than the full history. Both papers study social learning under different network topologies.
targets agents with misspecified beliefs, i.e. beliefs whose support does not include the correct model. The framing is similar to BSL with Bayesian- unbiased agents: agents arrive one by one and face the same decision problem, whereby each agent makes rational decision after observing the outcomes of the previous agents [8] Rational decisions under misspecified beliefs make a big difference compared to BSL, and structural assumptions about rewarrs/observations and the state space tend to be very different from ours. The technical questions being asked tend to be different, too. E.g., convergence of beliefs is of primary interest, whereas the chosen arms and agents' beliefs/estimates trivially converge in our setting.
Prominent recent work, egg., [31 15 25 44),
[9
B Preliminaries: Reward- Tape
It is convenient for our analyses to interpret the realized rewards of each arm as if they are written out in advance on "tape". We posit a matrix ( (Taee,.: E [0, 1] : a E [2]. i [T'] ). called reward-tape such that each entry Tape,, is an independent Bernoulli draw with mean M4. This entry is returned
as reward when and if arm a is chosen for the i-th time. (We start counting from the initial samples, which comprise entries i E (No].) This is an equivalent (and well-known) representation of rewards in stochastic bandits.
We will use the notation for the UCBs/LCBs defined by the reward-tape, Fix arm a E [2] and n E [T]. Let stape = 1 Eiejj) Tape,,; be the average over the first n entries for arm a. Now, given v) 2 0, define the appropriate confidence bounds:
UCB tape.p = min 1, Phape + vn/nn and LCBtape, " := max { 0, Mepp - Vn/n (B.1)
The original framing in this work posits single learner that makes (possibly) myopic decisions over time and observes their outcomes. An alternative interpretation is that each decision is made by a new myopic agent who observes the history.
"Essentially, if an arm is chosen infinitely often then the agents beliefs/estimate converge on its true mean reward; else, the agents eventually stop receiving any new information about this arm.
15

---

C Proofs from Section 3
Learning Failures
Our proofs rely on two tools from Probability (proved Section C.4 and C.5
sharp anti-
concentration inequality for Binomial distribution and lemma that encapsulates martingale argument.
Lemma C.1 (anti-concentrationn) Let (Xi)seN be a sequence of independent Bernoulli random variables with mean p E [c. - for some (0, 1/2) interpreted as absolute constant. Then
( Pr P E x, x, 22( 0000-=00(00ppp ((((v-9)))
(An 2 1/e, E (c/8,
(C.1)
where Q(-)) and O()) hide the dependence on c.
Lemma C.2 (martingale argument). In the setting of Lemma C.1
Vg E (0.p)
Pr[Vn 21: - 2 Polp q).
(C.2)
The overall argument will be as follows. We will use Lemma C.1 to upper-bound the average reward of arm i.e,, the good arm, by some threshold 91- This upper bound will only be guaranteed to hold when this arm is sampled exactly N times, for a particular N 2 Ng. Lemma C.2 will allow us uniformly lower-bound the average reward of arm 2, i.e. the bad arm, by some threshold Q2 (2)) Focus on the round 1a when the good arm is sampled for the N-th time (if this ever happens). If the events in both lemmas hold, from round 1" onwards the bad arm will have a larger average reward by constant margin 42 41- We will prove that this implies that the bad arm has larger index, and therefore gets chosen by the agents. The details of this argument differ from one theorem to another.
Lemma C is a somewhat non-standard statement which follows from the anti-concentration in- equality in 61 and a reverse Pinsker inequality in (28). More standard anti-concentration results via Stirling's upproximation lead to an additional factor of 1//nn on the right-hand side of (C.1). For
2 Lemma we introduce an exponential martingale and relate the event in (C.2) to a deviation of this martingale. We then use Ville's inequality (a version of Doob's martingale inequality) to bound the probability that this deviation occurs.
C.1 Proof of Theorem 3.1 c-oofideet agents
Fix thresholds 91 Q2 to be specified later. Define two "failure events":
Failı: the average reward of arm after the No initial samples is below q1; Faily: the average reward of arm is never below 42-
In a formula, using the reward-tape notation from Appendix these events are
Fail, := {
tape 11
< 91 and Fail, = Vn E [2] : tape
P2,n
2 42 }
(C.3)
We show that event Fail := Fail, O Faily implies the 0-sampling failure, as long as the margin Q2 Q1 is sufficiently large.
Claim C.3. Assume Q2 > 2- n/No and event Fail. Then arm 1 is never chosen by the agents.
Proof. Assume, for the sake of contradiction, that some agent chooses arm Let be the first round when this happens. Note that Indj.: Ind2,:- We will show that this is not possible by upper-bounding Indi,: and lower-bounding Ind2.
By definition of round t, arm has been previously sampled exactly No times. Therefore,
Indj. S tape No + Vn/No
(by definition of index)
S 91 + /
(by Failı)
< 92
nnNoo
(by assumption).
16

---

Let n be the number of times arm 2 has been sampled before round t. This includes the initial samples, so n 2 No- It follows that
Ind2,t 2
122,
ptape
Vnnn
(by definition of index)
2 Q2
N/No
(by Fail2 and n 2 No)-
Consequently, Ind2, Ind1,t, contradiction.
In what follows, let e be the absolute constant from assumption 3.1
Let us lower bound Pr Fail] by applying Lemmas C.I and C.2 to the reward-tape.
Claim C.4. Assume c/4 91 Q2 μ22. Then
Pr Fail] Mtail Re(ue 92) O.( (Nouu (o)m)-9))))
(C.4)
Proof. To handle Failı, apply Lemma C.I to the reward-tape for arm 1, i.e, to the random sequence ()) with No and q Q1 Recalling that No 2 1/c by assumption (3.2),
Pr [Fail;] 2 Doe
To handle Fail2, apply Lemma C.2 the reward-tape for arm 2, i.e. to the random sequence (Tapez;)ke(r). with threshold q = 92. Then
Pr Pr[Fii22] s2 92).
Events Fail, and Fail, are independent, because they are determined by, resp., realized rewards of arm 1 and realized rewards of arm 2. The claim follows.
Finally, let us specify suitable thresholds that satisfy the preconditions in Claims C.3 and C.4
= μl2 - 4 Vn/No cA/4 and 42 = l/2 - / / cA/4.
Plugging in #2 2 and N, 2 64 n/c,,/ it easy to check that 2 c/4, as needed for Claim C.4
Thus, the preconditions in Claims C33 and C.4 are satisfied. It follows that the O-failure happens with probability at least (tail, as defined in Claim C.4 We obtain the final expression in Eq. (33) because
Ha - 9o = O.(A + v ()o)) for both arms a E [2].
C.2 Proof of Theorem 3.10; pessimistic agents
We reuse the machinery from Section C.1
we define event Fail = Fail, O Faill per Eq. C33
for some thresholds qi < (2 to specified later, and use Claim C.4 to bound Pr [ail]. However, we need different argument to prove that Fail implies the O-sampling failure, and different way set the thresholds.
Claim C.5. Assume / Vnooo and event Fail. Then amm 1 is never chosen by the agents.
Proof. Assume, for the sake of contradiction, that some agent chooses arm Let be the first round when this happens. Note that Indı,: 2 Ind2,:- We will show that this is not possible by upper-bounding Ind1,: and power-bounding Ind2.
By definition round t, arm has been previously sampled exactly Ng times. Therefore, (by definition of index) (by Faili)
Ind = max M1,No
stape V //NNo
< (0, 91
n/No
(1 Vn/Noo
(by assumption).
Let n be the number of times arm 2 has been sampled before round t. This includes the initial samples, s0 n > No. It follows that
Ind2,1 2 stape
Vn/n
(by definition of index)
2 42 n/o
(by Fail, and 2 No)-
Consequently, Indg, Indj,ts contradiction.
17

---

Now, set the thresholds 91, 92 follows:
a1 = - c0/4 and Q2 1 cA/8.
Plugging in μ2 and No 64 n/c2 is easy check that the preconditions in Claims C.4 and C.5 are satisfied. So, the O-failure happens with probability at least frai1 from Claim C.4 The final expression Eq. (33) follows because paa qa O.(A) for both arms [2].
C.3 Proof of Theorem small No
We focus on the case when No S N : [64n/c² 1/cl. We can afford to handle the initial samples in a very crude way: our failure events posit that all initial samples the good arm return reward 0, and all initial samples of the bad arm return reward 1.
Fail: (vi E [1, Tape 0}
Fail2 == (Vi E [1, Tapez, = and
E [T]
tape P2.
2 92
Here, 92 > is the threshold be defined later.
On the other hand, our analysis given these events becomes more subtle. In particular, we introduce another "failure event" Fail3, with a more subtle definition: if arm is chosen by least n N* - No agents, then arm is chosen by agents before arm I is.
We first show that Fail Fail, n Faily n Faily implies the n-sampling failure.
Claim C.6. Assume that q2 2 c/4 and Fail holds. Then at most N No agents choose arm
Proof. For the sake of contradiction, suppose arm I is chosen by more than n agents. Let agent é be the (n 1)-th agent that chooses arm 1. In particular, Ind1, 2 Ind2,1-
By definition of t, arm has been previously sampled exactly N times before (counting the No initial samples). Therefore,
Ind1, S M1,N- Vn/N"
(by (-confidence)
Vn/N=
(by event Failı) (by definition of N*),
c//
Let m be the number of times arm 2 has been sampled before round t. Then
Ind2, 2 P2.m
4/m m
(by n-confidence)
Q2 nn/m
(by event Fail2)
2 92 V ///N
(since m 2 N by event Failç)
92 c/8
(by definition of N*)
> c/8
(since q2 2 c/2).
Therefore, Ind2, > Indi,e. contradiction.
Next, we lower bound the probability of Fail, O Failz using Lemma C.2
Claim C.7. 1f #2 then Pr [aill O Fail,] 2 P,(12 92) 2NN
Proof. Instead of analyzing Fail, directly, consider events
3 : (vi E
Tape }} and E' := Vm E I + 1,7] M-N- E Tape,, 2 92 ( [1,
Note that E implies Fail2. Now, Pr Fail,] > f1] N" 2 N and Pr [ (1 (1111)) > N~ Further, Pr[E'] 2 Qz(uz - 42) by Lemma C.2 mutually independent.
The claim follows since these three events are
18

---

To bound Pr [Fail], J. we argue indirectly, assuming Fail; O Faily and proving that the conditional probability of Fail; is at least 1/2. While this statement feels natural given that Fail Fail2 favors arm 2, the proof requires a somewhat subtle inductive argument. This is where we use the symmetry and monotonicity properties from the theorem statement.
Claim C.8. Pr Fail3 Fail1 (1 Fail2] 1
Now, we can lower-bound Pr Fail by 22(12- - -22) -2) 22 .inally, we set the threshold to 92 c/2 and the theorem follows.
Proof of Claim C.8 Note that event Fail, is determined by the first N entries of the reward-tape for both arms, in the sense that it does not depend on the rest of the reward-tape.
For each arm and [T]. let agent Ta,s be the i-th agent that chooses arm a, if such agent exists, and T; T + otherwise. Then
Faily { 72.m I Ti,
Ti. 2 2n
(C.5)
Let & be the event that the first N entries of the reward-tape are for both arms. By symmetry between the two arms (property (P1) in the theorem statement) we have
Pr Pr 12.n Tim E] = Pr(rre, > -im [E] 1/2,
and therefore
Pr [Faill
[l Pr T2, S Fin [ 2 1/2.
(C.6)
Next, for two distributions F, G, write F rood G if F first-order stochastically dominates G. A conditional distribution of random variable given event is denoted (X(E). For each E [T], we consider two conditional distributions for Ti, one given Fail, n Fail, and another given E, and prove that the former dominates:
( [1, Fail, (Fail2) Iooad (1
(C.7)
Applying CC.7
with i n, it follows that
Pr Faily
Fail, O Faile]
= Pr Fi,m 2 2n
Fail, [Faily]]
2 Pr Ti.m 2 2n {] = 1/2.
(The last equality follows from C..6 and Eq. (C.6).) Thus, it remains to prove CC.7
Let us consider fixed realization of each agents' behavioral type, ie., fixed, deterministic mapping from histories arms. W.l.o.g. interpret the behavioral type of each agent as first determin- istically mapping history hist, to a number P: [0, 1]. then drawing threshold 0g E [0. 1] independently and uniformly at random, and then choosing arm if and only if Z O.. Note that P: Pr [a, = 1 hist.]. So, we pre-select the thresholds 0, for each agent t. Note the agents retain the monotonicity property (P2) from the theorem statement. (For this property, the probabilities on both sides of Eq. (3.6) are now either 0 or 1.)
Let us prove (C7 for this fixed realization of the types, using induction on Both sides of (C.7 are now deterministic: let A,, B, denote, resp., the left-hand side and the right-hand side. So, we need to prove that A, > B, for all i (n). For the base case, take 0 and define Ag = Bg 0. For the inductive step, assume A, 2 B, for some 2 O. We'd like to prove that Ai+1 2 B Suppose, for the sake of contradiction, that this not the case, i.e., A411 < B,41. Since A, A by definition of the sequence (Ta.i E [7]), we must have
B S A A+1 < Bi+1.
Focus on round t = A;+1. Note that the history hist, contains exactly i agents that chose arm both under event Fail, n Fail, and under event E. Yet, arm chosen under E, while arm 1 is chosen under Fail, 0 Failg. This violates the monotonicity property (P2) from the theorem statement. Thus, we've proved (C.7) for any fixed realization of the types. Consequently, (C.7) holds in general.
19

---

C.4 Proof of Lemma C1
Proof. We use the following sharp lower bound on the tail probability of binomial distribution.
Theorem C.9 (Theorem in (1]) Let a e N be positive integer and let (Xi)ee(n) be a sequance of Li.d Bernoulli random variables with prameter For any B > there exists constants Cg and C3 that only rely on B, such that for all x satisfying x E [o, and n(1 p) 2 we have
n np x X;
Pr
Σ
e&e cge CanD(onn--
where D(xlly) denotes the KL divergence between two Bernoulli random variables with parameters and y.
We use the above result with x = n(p - q) and β 1-c Note that 3 > 1 since e < 2' We first 1-
verify that x, 3 satisfy the conditions of the lemma. The x + n21 p) 2 condition holds by the assumption 2 1/c:
+ n1 p) 2 n(1 p) 2 1.
As for the S 3 condition, by definition of
np
(pp
q) p
Since p 1 and p-g
is decreasing in p for p 9. further bound this with
P 2 p-9 1-c-9
1 c
2 1 1 c
= 3
where the second inequality follows from 9 2 c/8 and 9 S together with the fact that 1-c is decreasing in for < 1 - c. We obtain x < "2
by rearranging.
I-c-y
Invoking Theorem
C.9
with the given values, we obtain
Pr
-==
<q 2 eae CanD(allp) ?i O(nD(elle))
(C.8)
Next, we use the following type of reverse Pinsker's inqeuality to upper bound ((gll)).
Theorem C.10 ((28) For any two probability measures P and Q on a finite support X, if Q is absolutely continuous with respect P. then the their KL divergence D(Q) P) is upper bounded by 25((, 2) where ap minlxe P(x) and 8(Q, P) denotes the total variation distance between P Pand Q.
Setting P Bernoull(pp) and Q = Bernoulli(q). we have ap = min(p, 1 p). and P Therefore, since min(p, -pp) p) by assumption, conclude D(gl (p) S O( =) Plugging this back in Equation C.8) finshes the proof.
C.5 Proof of Lemma
Our proof will rely on the following doob-style inequality for (satna)mariingalles
Lemma C.11 (Ville's Inequality (58)) Let )n2 be positive supermartingale with respect to
filtration (Fn)zoo iee. Zn 2 E Zn+ F for any n 2 0. Then the following holds for any x >> 0,
Pr
max Zn
< E 1/2.
In order to use this result, we will define the martingale 2n == Lin for suitable choice of u as specified by the following lemma.
20

---

Lemma C.12. Let be an absolute constant. For any p É (c, 1 c) and (0,p), there exists value of (0, 1) such that
(p. 1o- + (1 p) 9)=-= =
(C.9)
In addition, u satisfies
p(1 9) 2 Op 9).
(C.10)
Proof. To see why such u exists, define f(x) (p-x' 1- (1- p) 9)). It clear that f(1)
and lim f(x)= = oo as lim p) 00. Furthermore,
fz))) p. (1 q) x (1 p) (-
which implies
p)g = p- - 7>6 0. (((1 - p(1 - (1-
Therefore, f(z) is decreasing at x = 1. Since lim f (x) > f(1), this implies that f(u) f(1)
for some (0, 1), proving Equation (C.9)
We now prove Equation 10, define xo as z0 (1- plg Note that zo < since p q. We claim that u S ro. To see why, we first note that fz) can be rewritten as
p(1-))
x (xp(1 9)
p)g)
It is clear that ('(x)) = O. Since xp(( g) (1 - p)g is increasing in this further implies that f'(x) > 0 for x > z0- Now. if > zg. then since (x) > for x > zo, we would conclude that
f(u) < f(), which is not possible since f(u) f11 1. Therefore,
zo as claimed.
We now claim that zo 1-2 < 1 + This would finish the proof since, together with S zo, this would imply
p(1 - u 9) 2 p(1 1
- 2 p(p q) = h(p 9),
where for the last equation we have used the assumption E (c. - c).
To prove the claim, define & == p
We need to show that x 1-9 I - E, or equivalently
in(l-c) By defintion of zo. this is equivalent to In (xo) I 1-4
(1 (1- ( 1- 1
In (1 (1-p+e)p
In(1 In(1-e) -)).
(C.11)
Fix and consider both hand sides function of E. Putting 0, both hands side coincide as they both equal 0. To prove Euqation (C.IT). it suffices to show that we increase e, the left hand side decreases faster than the right hand side. Equivalently, we need to show that the derivative of the LHS with respect to is larger than the derivative of the RHS with respect to for S [0. p). Taking the derivative with respect to E on LHS, we obtain
d
(In(1 p) + In(p 5) - In(1 + In(p)) de
D- 1 p +
Similarly taking the derivative on RHS we obtain
d In(1 (m(1-s)
1
In(1 E)
de
1- 1-p+e
(1 - (1-8((1 - -
(1 - + 8)²
We therefore need to show that
-1
-1
Inn( s) (1 (1-p E)
+
<
(C.12)
1 1-
p- (1 - (1-p+33 +) =))
We note however that
-1
E E-p p-p- 1
1-p+6
p p-8
-)) (1-p+s)(1-
Therefore Equation
C.12
equivalent to
In(1 (1 8)
2 0,
p + 2)²
which is true since [0, p). This proves the claim
1-9 < 1 finishing the proof.
21

---

We now prove Lemma C.2 using Lemma C.11 and C.I2
proof of Lemmal C.2 Define the random variable Y, as as X,+1 q. Note that Y; takes value
with probability p and takes -9 with probability 1 p. Set to be the value specified in Lemma
C.12 For n 2 O, define Zn == - Vi, We first observe that Zn is martingale with respect to
1...... as
E Zn+1 Yr,
Yn E w 111 Yn
w V. (p. ut- (1 p) 2
Dis Vi Zn.
Since 0
1, this further implies
Pr
Vn 2 0: Σ 1222-1
- Pr
On 0: Σ
Y 1----
i=1
max u El Y. 29-1 .1Em
Pr
E Z1
ud
where the first inequality follows from Lemma C.11 and the final equality follows from EE [
E [ = E u0] 1.
Since Y, is funetion of X,-1, independently have X₁ with probability p. Therefore, with probability p(1 - u 1
X, and Vn 1: Σ (X: - ②) 29-1,
which further implies
Σ (X, 9) Therefore,
Σ X; 2 2 p(1 - ut-9) +)9 2 22 - 4),
Pr Vn 2
where the inequality follows from Equation (C.1O).
D Proofs from Section 4 Upper Bounds for Optimistic Agents
D.1 Proof of Theorem 4.1 and Theorem
We define certain "clean events" capture desirable realizations of random rewards, and decompose our regret bounds based on whether not these events hold. The "clean events" ensure that the index of each arm is not too far from its true mean reward; more specifically, that the index is "large enough" for the good arm, and "small enough" for the bad arm. We have two "clean events", "", one for each arm, reward-table as follows:
defined in terms
Clean" Vi E [
UCB
Lapeapo.
tape. 2111 4/2).
(D.1)
Clean = { Vi 2 64n/A² UCB
tape. " < P2 A/4).
(D.2)
Our analysis is more involved compared to the standard analysis of the UCB1 algorithm [6]. essentially because we cannot make be "as large as needed" to ensure that clean events hold with very high probability. For example, round and naively take a union bound over all rounds 20 Instead, we apply more careful "peeling technique", used e.g., in Audibert and Bubeck [5]. below.
cannot upper-bound the deviation probability separately for each
avoid any dependence T in the lemma
Indeed, this would only guarantce that clean events hold with probability least O(T -R(n)),, which in turn would lead regret bound like O(1²,, . -R()).
22

---

Lemma D.1. The clean events hold with probability
Pr [r[lean)]] 2 1 - O ( (1+ (og(//(/))) - )
(D.3)
Pr [Clean]]
2 0 (-()m)
(D.4)
We show that under the appropriate clean events, n-optimistic agents cannot play the bad arm too often. In fact, this claim extends to [1) "/mxx)-opimissic agents.
Claim D.2. Assume that events Clean? and Cleang Muas hold. Then [1). Mmax -pttmisiii agents cannot choose the bad arm more than 64 maax/ A times.
Proof. For the sake of contradiction, suppose [n) Mmmx) lottimiiti agents choose the bad arms at least n = 64 mmax/ / / times, and let t be the round when this happens. However, by event Clean". the index of arm
at least μ4 A/2. By event Clean fmaae the index of arm at least
UCB S #2 + A/4, which is less than the index of arm 1, contradiction.
For the "joint" clean event, Clean := Clean" n Clean Tisox Lemma D.I implics
Pr [Cleen]]
0 log (1/2)- -((m))
(D.5)
When the clean events fail, we upper-bound regret by A T, which is the largest possible. Thus, and and Eq. (D.5) imply Theorem 4.4 which in turn implies Theorem 4.1as as a special case.
Lemma D.2
D.2 Proof of Theorem 4.5
We reuse the machinery from Section D.I. but we need some extra work. Recall that all agents are assumed to be 7max 7maxx-oonidee confident, whereas only a fraction are optimistic. Essentially, we rely on the optimistic agents to sample the good arm sufficiently many times (via Claim[D.2). Once this happens, all other agents "fall in line" and cannot choose the bad arm too many times.
In what follows, let = 1 + 64 //maa/// 2
Claim D.3. Assume Clean. Suppose the good arm is sampled at least times by some round to- Then after round lo. agents cannot choose the bad arm more than m times.
Proof. For the sake of contradiction, suppose agent t > to has at least samples of the bad arm (i.e,, 122 2 m), and chooses the bad arm once more. Then the index of the good arm satisfies
Indi,: 2 L.
(Tmax confiden agents) (by definition of to)
2
LCB
tape, Mmxx 1,m
UCB
tape, Qmax 1,m
2 V Mmnax/ m m
(by definition of UCBs/LCBs)
UCB tape,
1 2 //mmax/ m
(since Tmma 2 1)
M4 A/2
(by Clean" and the definition of m).
The index of the bad arm satisfies
Ind2,: < UCB",,
(n-confident agents)
S2 + A/4
(by Clean, and the definition of m),
which is strictly smaller than Indi,r, contradiction.
For Claim D.3 to "kick in", we need sufficiently many optimistic agents to arrive by time fo. Formally, let & be the event that at least 2m agents are [7, Mmax |-optimistic in the first rounds. Corollary D.4. Assume Clean. Further, assume event E for some round to. Then (by Claim D.2) D.2i the good arm is sampled at least m times before round to. Consequently (by Claim D.3 cannot choose the bad arm more than m + to times.
agents
Finally, it is easy to see by Chernoff Bounds that Pr (r() 12.11 1 E -2(r) for some 4 = (( where y is the probability from the theorem statement. So, Pr Clean n Etg is lower-bounded as in Pr[[1rrere Eq. (D55.. Again, when Clean O &,, fails, we upper-bound regret by A T. So, Corollary and the lower bound on Pr Clean O Ec) implics the thcorem.
23

---

D.3 Proof of Lemma D.1
We assume without loss of generality that 1 If 2, the Lemma's statement can be made vacuous using large enough constants in O. In addition, for mathematical convenience, we will assume that the tape for each arm is infinite, even though the entries after T will never actually be seen by any of the agents.
For each a, first separately consider each interval of the form [n,, 2n] and bound the probability that UCB sape. deviates too much from Ma for i [n, 2n]. While this can be done crudely by applying a union bound over all i, we use the following maximal inequality.
Lemma D.5 (Eq. (2.17) in (2... Given sequence of ii.d. random variables (Xi)seta) [0, 1] such that E X; = μ4, the inequality states that for any x > 0,
Pr
3i
Σ j=1
(X, - p)
m > x
2u < 2e
Focusing on some interval of the form [n,, 2n| for n E N, and applying this inequality to the reward tape of arm a, we conclude that
Pr Ei (n, 2m]
Ma 2 x]] O(e -((n=)))
(D.6)
Define ;= [64n/ We note that f= 0n/ A²) given the assumption > 2. In order to bound Pr [ Clean]] ) we will apply this inequality each interval [n, 2m] for n 2 f. and take a union bound. Formally,
1 - Pr Clean!]
< Pr 3i
tape P2,
> μ2 + A/8]
(Since n/i S A/8 f)
Pr
3i E 1 -1 12. > μ22 + A/8]
(Union bound)
2
00
0(n2')
(By Eq. (.6
0
0(m(r+1))
(Since 2" 2 1forr N)
0 cf(n)
(Sum of geometric series)
< Ole -Q(n))
(By 2)
In order to bound Pr Clean"] ). we separately handle the intervals < f and 2 For 2 repeating the same argument as above for arm implies
Pr [32
Stape <pi P
A/8 < (0(--R(m))
For n < f. we use modified argument that utilizes the extra 7 term UCB Instead of bounding the probability #1,1
stape having deviation A /8, bound the probability that it deviates by

---

Vn/i. This results in marked improvement because vn/i increases as we decrease i. Formally,
Pr
Bi [1,
Tapa < p1
n/2
[og(f)]
Pr Di 12", 2 ,i,s < μn Vn/ii
(Union bound)
1=0
[lg((1)
Σ
Pr Di E [2", 2 M1 < μn V1/2r+1
(By assumption on
[log(f)
0
Σ
-((n)
(By Eq. D.6
= =[[lo[([)] 1())).
Finally, we note that since 2,
[og( < O(1 + log(s)) = O(1 + log(n) log(1/A))-
This implies Eq. (D.) because O(log(n)e- (R()) can be rewritten as O -(()) by changing the constant behind Ω
E Proofs from Section 5: Learning Failures for Bayesian Agents
In this section, we prove Theorem 5.1 We first briefly review some properties of the beta distribution. Throughout the section, consider beta distribution with parameters o,
Lemma E.1 (Fact 1 in [3). Let FR, denote the CDF of the binomial distribution with paramters n. p and pbeta denote the CDF the beta distribution. Then,
Facte (v) = ==
for a, 3 that are positive integers.
Using Hoeffding's inequality for concentration of the binomial distribution, we immediately obtain the following corollary.
Corollary E.2. Define Pa.3 = 3),
a-1 1+ If X is sampled from the beta distribution with parameters
X - Pa.s S y1 < 20-
In addition, letting ((-) denote the quantile function of the distribution,
In(2/C)
In(2/C) a 3 -
[Q(S), Q(1-
Pa.8 V a V
Pa. Pa.B
Let Csa,ns Ba,n denote the posterior distribution after observing n entries of the tape for amm a. Note that since we are assuming independent priors, the posterior for each is independent of the seen rewards of the other arm. Define Ma,, == Caaaa + Ba.n- We note that by definition, 0a,0, 80.0 coincide with the prior aa, 3.. We analogously define M. a. Ba. Define Pa,n Ma,a and Sa,n = aa. We note that Ea,n the mean of the posterior distribution after observing n entries of arm Ma,n
2..a -1
Lemma E.3. For all
Pa,n
Ea, S S0
0
Ma.a n+MMa
Proof. After observing n entries, the posterior parameters satisfy
Oa, = Oa,D
Tape
Ban := 3a,0 + Σ Tape ..
i5n
25

---

Ma It follows that
Sa, Da,u + Eisn Tape a. Cla,0 + -a,00 + n
Defining X = Eign Tape a,i* we can bound the difference between Ea,n and Pa,n as
0a,0 + X
X
naa,0 + nX - -nX- - XM,00
Ma.0
n(n + Ma,o)
naa.0 - XMa.
n(n Ma.0)
Ca.0 +
Ma.0
(Since X 2n)
Ma.0 n + Ma.0
Ma.0
$ 0
Ma,0
Lemma E.4. For all n 2 0, 1a,m Pa,n 00
n M..0
Proof.
Qa, -1
Ga.n Majn.
-Man + Otain
Ma,n
Ma,a (Man 1)
Man
Ma. (Main
Man
1
(Since Ma, = Ma,0 + n and Ma,0 2 1)
+ Ma,0
We can now prove Theorem 5.1
Proof of Theorem 5.7 We start with part (a). Set 17 to be large enough such that
prape Ea,n
m
Since Mr
M S n by Lemma E.3 this can achieved with r) 2 O(Ma/VNo), which proves part
(a).
For part (b), set 77 to be large enough such that Pran - Pa,n $ 1 / T Given, Lemmas E.3 and
E,4
this can be achieved with 2 O(Ma/
O(Ma/VNo). /No). Since MM- - 2 n, we can further gaurantee
in by setting 1 O(n(1/()), which finishes the proof together with Corollary E.2
F
The corollary from Section 6
we derive a O-sampling failure, leading to I2 Bayesian regret. Specifically,, the agents never try prior is independent across arms and has a positive density on the entire [0, 1] interval.
As a corollary of Theorem 6.1
when it is in fact the best arm. This happens whenever the
Corollary F.I. the setting of Theorem 6.1 I. suppose the prior P independent across arms and has positive density for each arm (i.e., has probability density function that is strictly positive on [0, 1].. Then [[egret([)) 2 cp T, where the constant ep > 0 depends only on the prior P.
This follows from a more explicit, but more cumbersome corollary.
26

---

Corollary F22 Denote / Elui] and μ42 = Eluz]. Consider independent priors such that
Pr[p1 =1] < (n) p2)/2. 2. Pick any a such that Pr Pr[m: 2 1 2a s (n (1))2) Then
p22/2.
Bayesian regret least T' (4/2 (nf - -g)) Pr I 1 al).
Proof. Let & be the event that < 2a and arm 2 is never chosen. By Theorem 6.1 and the definition of a, have Pr [E] 2 (pl p2)/2.
Let &g be the event that #2 > - a. Under event & n each round contributes #2 # 2 a to regret, so B. ((()T) & n 2 a.T
Since event & is determined by the prior on arm and the rewards of arm 2, it independent from E. It follows that
E(R(T)) 2 E(R(T) & n - Pr|& n
2 aT (N4 -22)/2 Pr[&)].
27


Reviews:
[{"review_id": "YAY1KjKzzC", "reviewer": "Reviewer_XcKk", "summary": "This paper considers a social learning problem motivated by reviews on online platforms, where (myopic) users make (purchase) decisions based on historical reviews and generate new reviews in an online fashion. It considers several different user behavioral types, such as the confidence based optimistic, pessimistic and neutral users. In addition, the users could have Bayesian belief on the mean reward and act according to the posterior update based on the history. The paper characterizes several cases where the learning failure occurs i.e., when all but a few agents choose the bad arm.\n", "questions": "Please see the points listed up the weakness part. I really liked the problem setup, and I am willing to raise my score if the authors could convince me of the technical/conceptual significance of their existing results.  ", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper introduces and analyzes an interesting setup of social learning. I can see how this setup may be applied to many real world applications, such as online recommendation systems (especially in presence of purchase decisions). I also expect many research projects to follow up on this fundamental social learning model.\n2. The technical tools used in this paper are somewhat different from the standard bandit literature.\n3. The possible results as the implications regarding the optimistic agents are very interesting.", "weaknesses": "1. The presentation and structure of this paper requires some improvements. The current version seems to have many results scattered around the paper, making it hard for us readers to switch the context from one section to another.  Section 3 is named as \"learning failure\", but it actually considers several different setups (theorem 3.1, 3.9, 3.10). Why not merge theorem 3.1 and 3.9? It might also be a good idea to use a table to summarize the results under different setups, e.g., when it fails, when it doesn't.  \n2. Overall, I find the problem setting interesting, but the technical results are not that surprising. For example, Theorem 3.1 requires a fixed \\eta for every agent, which more or less violates its motivation of social learning --- the agents tend to have heterogeneous behavior types. I also wish the paper could connect its results and setups to real world applications (instead of imagining purely idealized scenarios).\n3. The entire paper chooses to only focus on the two arms case. I expect the author to point out the exact technical challenges (or practical motivations) that prevent the analysis to be extended to the general cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful review. Let us respond point-by-point to the stated weaknesses. \n\n**[W1]** The structure of the paper is driven (and necessitated) by the somewhat intricate collection of results, see “technical story” in the general rebuttal. Given the commonality / connections both in story and in techniques, we believe it makes sense to group all negative results in one section and discuss them jointly; likewise, all positive results and all “Bayesian beliefs” results. In particular, negative and positive results match “globally” but not “point-by-point”: instead each “side” has its own “sub-story”. \n\nRe “not merging Thm 3.1 and Thm 3.9”: please see the general rebuttal. \nAdding a table is a great idea, we’ll do it!\n\n\n**[W2]** Please note that our negative results allow heterogeneous behaviors. In Thm 3.1, “$\\eta$-confidence” with fixed $\\eta$ defines not a particular behavior but a wide range of allowed behaviors, including heterogeneity, see “generality” in the general rebuttal. Likewise Thm 3.9 (under minor restrictions of symmetry and monotonicity). Even Thm 3.10, while focusing on pessimists, allows for varying levels of pessimism. \n\nWith this generality, we plausibly capture what myopic real-world agents might do when faced with a simple learning problem. Moreover, the particular behaviors that we capture are well-documented in the literature on behavioral economics and/or cognitive psychology (e.g., optimism/pessimism, probability matching, recency bias). \n\nWe note, however, that results for homogeneous behavioral types are quite common in the literature, as they tend to make the intended points in a most concrete and elegant way. For example, Thm 4.1 obtains a clean upper bound that matches our negative results. (Meanwhile, Thm 4.4 and Thm 4.5 drill deeper to investigate heterogeneity.) \n\n\n**[W3]** Please see “K>2 arms” in the general rebuttal. \n"}, {"review_id": "tesIRgPSJq", "reviewer": "Reviewer_ZFQ2", "summary": "The paper proposes the model of social learning under myopic behavior, where a 2-armed bandit problem is considered with agents that behave myopically. Upper and lower bounds on the probability that all but \\leq n agents choose the bad arm are derived.", "questions": "Please see weaknesses.", "limitations": "Yes.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and easy to follow.\n- The considered model is novel.\n- The bounds on failure probability are tight.", "weaknesses": "- The results are only limited to the case of 2 arms.\n- Assumption 3.2 is strong and seems to be unnecessary. For example if mu_1 is very small, then a lot of initial samples N0 are required even if mu_2 is close to 1 which is an easy to solve case that does not require a lot of samples.\n- The considered myopic strategies are limited to a few number of strategies (confident, unbiased, optimistic, pessimistic, bayesian).\n- The results are not surprising and can be obtained using standard concentration inequalities in the bandit literature, e.g., see [1].\n- As the paper is only concerned about failure probabilities without the need to decide on a strategy, I am not convinced about the importance of the results.\n\n[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful and explicit review. Let us respond point-by-point to the stated weaknesses, in the same order.\n\n**[W1]** Please see “K>2 arms” in the general rebuttal. \n\n\n**[W2]** Assumption (3.2) is not that strong in the theoretical sense: it merely requires $N_0$ to be larger than a constant. Essentially, it ensures that the confidence intervals are proper subintervals of [0,1] – which matters even if $\\mu_1$ is close to 0 and $\\mu_2$ is close to 1. \n\nThis assumption is needed for our analysis of Thm 3.1. However, we do remove it later on – which is the whole point of Thm 3.11 – but at the cost of minor-but-technical assumptions on the behaviors and some substantial complications in the analysis. We’d be thrilled to get rid of this assumption in any simpler way, suggestions welcome!\n\n\n**[W3]** On the contrary, $\\eta$-confidence in Thm 3.1 (and Thm 3.9) allows for a range of behaviors, incl. unbiased and pessimism/optimism as special cases. Please see “generality” in the general rebuttal. \n\n**[W4]** Our negative results critically rely on anti-concentration and martingale tools, which are **not** standard in bandit lower bounds. In particular, it is really unclear how to get them while only using concentration tools, let alone standard ones such as Azuma-Hoeffding. \n\nOur positive results require *non-standard* tools to handle concentration, and (more importantly) a rather delicate way to define “clean events” and argue about them. Please also see “techniques” in the general rebuttal.\n\n\n**[W5]** There are thousands of papers on designing bandit algorithms, but ours is the first one on learning failures. Thus, we believe we fill an important gap in the literature. \n\nFurther, learning failures are a very common theme in the vast literature on social learning, and usually are considered a main result (and often *the* main result). Learning failures arise in different technical settings and due to different reasons; we discuss this literature in Appendix A.\n\n"}, {"review_id": "0fMfmZZ1Pr", "reviewer": "Reviewer_piEt", "summary": "This paper studies bandit social learning problem with two arms. Instead of aiming to design an efficient algorithm with theoretial guarantee, the authors demonstrate negative results regarding myoptic behaviors of agents. The main contribution of this paper is proving the regret lower bounds of $\\eta$-confidence agents, together with nearly matching upper bounds, which explains why greedy algorithms i.e., always exploit, are not efficient and why UCB1 algorithm requires extreme optimism.", "questions": "It might be better to add experiment simulations to validate the theory.\n\n*Typo*\n\nLine 39: the number of agents $T$...: should here be number of time steps?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* This paper is well written and easy to follow. The author does a great job of explaining complex concepts in a clear and concise way.\n* The proofs appear solid and complete to me that both of UCB and Bayesian agents are taken into consideration in this paper.", "weaknesses": "* I believe this is a good paper because it provides solid theoretical insights into why agents perform less optimistically as UCB-type algorithms perform worse, and how this degradation varies with the degree of optimism. However, I feel that the proofs do not introduce any new techniques, which lowers my overall score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful and a largely positive review!\n\n**[W]** Re techniques, please see “techniques” in the general rebuttal. We would also like to re-emphasize the generality of allowed behaviors, please see “generality” in the general rebuttal.\n\n**[Q]** We’ve included some experiments as requested, please see in the general rebuttal.\n\nRe Line 39, “the number of agents $T$”: in our setup a new agent shows up in each round, so agents and rounds are essentially the same.  "}, {"review_id": "kCcJezr0A7", "reviewer": "Reviewer_1URz", "summary": "The paper posits a bandit social learning (BSL) problem, which consists of a multi-armed bandit (MAB) problem where at each round an arm is pulled by a newly arrived agent, as a function of the history. This is motivated by reviews on online platforms, where agents pick decisions sequentially based on past reviews. Compared to standard MAB, where a centralized algorithm is run to minimize regret, in BSL each agent acts myopically and can be, e.g., greedy, optimistic, or pessimistic w.r.t. confidence intervals constructed around the reward estimate for each arm. The authors analyze the 2-arms setup and provide several learning failure results in identifying the optimal arm. Notably, the learning \"fails\" when agents are greedy or pessimistic, while it achieves optimal regret when a small fraction of the agents are optimistic. This was a general belief in standard MAB, but to the best of authors' knowledge their results are the first ones to assess it theoretically. Similar learning failures are also established for Bayesian agents who act according to their posterior.", "questions": "I would like to know the author's view on extending such results to more than 2 arms. In particular, is a bigger set of arms always more detrimental in terms of learning/exploration? Should the initial number of samples $N_0$ intuitively scale with the number of arms?", "limitations": "Limitations are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper reads really well and the results are sound. Moreover, the authors did a good job of positioning it into the existing related literature.\n- The introduced BSL problem is simple, albeit very interesting, and of practical relevance, e.g., in review systems. \n- Although the flavor of the results is quite specific to the BSL problem (where agents have different myopic behavior), the negative results apply to the more general MAB, constituting a relevant contribution to the broader bandits community. \n", "weaknesses": "- The authors consider 2-armed bandits for the sake of their analysis and negative results. However, it is not clear how the picture would change in the presence of more arms.\n- No experiments are performed. Although the paper is of theoretical nature, would be nice to demonstrate the proven failure probabilities and how the injected optimism facilitates learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful and a largely positive review!\n\n**[W1 and Q]** Please see “K>2 arms” in the general rebuttal. In particular, adding more arms could affect the failure probability positively, negatively, or not at all, depending on the problem instance. \n\nRe the semantics of $N_0$: indeed, it would make sense to have $N_0$ samples of each arm. (Note, however, that we think of $N_0$ as an exogenous parameter.) \n\n**[W2]** We’ve included some experiments as requested, please see in the general rebuttal.\n \n\n\n\n\n"}, {"review_id": "WPYPZK2q31", "reviewer": "Reviewer_Nim8", "summary": "The paper considers social learning in a two-armed Bernoulli bandit scenario, where agents sequentially arrive and pull an arm with the highest index, where the index is arbitrarily chosen to be within some confidence bound of the empirical mean of the arm, parametrized by $\\eta$. This behavior subsumes greedy behavior ($\\eta = 0$) and regret-optimal policies such as UCB1. The main contribution is a tight characterization of the probability of learning failure, i.e., most agents will pull the suboptimal arm as a function of the reward gap and $\\eta$. They extend this result to the case where agents are Bayesian and use truncated priors to inform indices.", "questions": "Could you comment on the qualitative difference between Theorem 3.9 and Theorem 3.1, and whether focusing on Theorem 3.9 with the very reasonable assumptions in P1-P2 would achieve the goals of the paper?\n\n---------------------------\nPost rebuttal: Thanks for the clarifications. While my original concerns about the practicality of regimes and the surprise-factor remain, I see the conceptual value of the results and believe they deserve to be published. I have raised my score accordingly.\n", "limitations": "The results pertain to a very specific two-armed bandit model and so the paper is explicit about its limitations and applicability.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- As the paper suggests, while the fact that greedy behavior causes learning failure with constant probability in standard classes of K armed bandit problems is folklore, there is no formal study of the boundaries of regimes where greedy behavior starts failing. Thus the motivation of the paper is solid.\n- The techniques for proving the lower bounds on the probabilities of failure are novel relative to standard bandit literature. ", "weaknesses": "- The paper's conceptual takeaways are not surprising, and the technical contribution adds little beyond tightly characterizing the probabilities of failure as a function of $\\eta$, the value of which is unclear for such a specific model of social learning. \n- The examples where the greedy behavior suffices in prior literature are contextual bandit environments where context diversity is the driver of exploration. So it seems that understanding the boundaries of greedy behavior must work with some interpolation between contextual and independent armed environments. Instead, the present paper focuses on a two-armed bandit environment where the confidence bounds are parametrized, the value of which is unclear since one anticipates learning failure for any fixed parameter value. \n- The interpretation of the results for the non-Bayesian setting is obfuscated by the dependency on $N_0$, the initial number of samples. It seems that a lot of technical maneuvering (e.g., assumption 3.2) arises because, when $N_0$ is small, one cannot eliminate the possibility of avoiding learning failure due to the confidence bounds being truncated at the boundary of $[0,1]$. This seems orthogonal to the central issue of focus (in this regard, Theorem 3.9 certainly appears to be cleaner). This makes the results appear too technical without adding anything substantial to the dialogue on the sufficiency of greedy algorithms for bandit learning.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful review which raises several rather subtle issues. Let us address the stated weaknesses point-by-point.\n\n**[W1]** What might count as “surprising” is that we managed to *prove* any/all these things, let alone in such generality. Given that such results remained unproved for so long, despite its obvious foundational value, we believe that success was very unclear in hindsight. (Note that proving “expected” results is often valuable – as a super-extreme example, consider proving P\\neq NP.)\n\nOne “conceptual takeaway” that may actually be surprising per se is that we provide a lower bound on the failure probability that does not degrade with the “strength of initial beliefs”. This point is most clearly stated in the “fully Bayesian” result (Thm 6.1), where the failure probability is lower-bounded by the Bayesian-expected gap, independently of the Bayesian prior. For the frequentist results in Sec3, the situation is a bit more subtle: “strength of beliefs” is driven by $N_0$, and the non-trivial regime is $\\Delta < O(1/\\sqrt{N_0})$ (otherwise the initial data alone essentially resolves the best arm). Then we get a lower bound of $\\Delta \\cdot e^{O_c(\\eta)}$. This should be contrasted with the “naive” failure mode when all examples from the good arm fail, which only happens with probability exponential in $N_0$ (see Remark 3.7).  \n\n\nFor good measure, let us recap our other \"conceptual takeaways\":\n- Greedy algorithm fails, essentially for any two-armed bandit instance.\n- In fact, any myopic behavior fails, with \"severity\" driven by $\\eta$. (More on this under \"generality\" in the general rebuttal.)\n- Optimism is essentially optimal for a given $\\eta$, while pessimism does much worse. \n- Small fraction of optimists goes a long way. \n- The failure results admit both \"frequentist\" and \"Bayesian\" framing. \n\nWe believe the significance of $\\eta$ is very clear: it defines the range of permissible behaviors, has a clear interpretation in terms of confidence intervals, and drives the “severity” of failures throughout various twists and turns of our technical story. \n\n**[W2]** We completely agree that a good path forward is to interpolate between a few complex environments where the greedy algorithm is known to work and the simple structure(s) in which it is known to fail. In fact, this direction is/was very much on our radar!  However, we believe our current paper is a necessary precursor – and a badly missing one! Please also see para1 and “greedy” in the general rebuttal.\n\nA minor point: what drives the positive results on Greedy in prior work is not just the diversity of contexts but also some structural assumption that enables aggregation (linearity in some papers, separability in some others).  A few other positive results are driven by a (very) large number of arms (under some additional assumptions).  \n\n\n**[W3 and Q]** The meaning of $N_0$ is that it controls the “strength of initial beliefs”, in the a natural frequentist interpretation thereof as the amount of initial data. So, in a sense, it is more than just an annoying technicality that we need to account for. \n\nIn a narrower technical sense, we need to consider larger $N_0$ in order to avoid a trivial failure mode when *all* initial samples of the good arm have reward 0 (see Remark 3.7). Then, indeed, we indeed need some “technical maneuvering” around the case of very small $N_0$. To answer your direct question, please see “not merging Thm 3.1 and Thm 3.9” in the general rebuttal.\n\nWe emphasize, however, that there’s much more to our technical story than the distinction between Thm 3.1 and Thm 3.9, e.g., see “technical story” in the general rebuttal. \n\n \n \n\n"}]

Author rebuttal:
Thanks for the thoughtful reviews. Many of our points are relevant to several reviews at once. 

**[SIMULATIONS: NEW]** As requested, we provide simulations to illustrate our main findings. We focus on the fundamental regime when agents are homogeneously all $\eta$-optimistic (resp., all $\eta$-pessimistic) for some fixed $\eta\geq 0$. Mirroring our negative results, we investigate the probability of a learning failure. Consider the event $F_t$ that the bad arm is chosen in all rounds between $t$ and the time horizon $T$. We re-run the simulation 1000 times, and plot the fraction of runs for which $F_t$ happens, as a curve over time $t$.

We plot such curves for several representative values of $\eta$, ranging from LCB to greedy to UCB. Qualitatively, we find significant failures which (predictably) get worse as $\eta$ decreases (treating LCBs as negative $\eta$). We consider mean rewards $0.5 \pm \epsilon$, with  $\epsilon=0.05$ ("large gap", top) and $\epsilon=0.01$ ("small gap", middle).

We also investigate UCBs with larger $\eta$, and find similar failures (with smaller probs) at a larger $T$. (We check that including "weaker" failure modes would not change this plot by much.) 

We'll be happy to include [even] more refined simulations in the final paper, if requested. 
\
\
**[K>2 arms]** We emphasize that 2 arms is the fundamental case for negative results, which are the main theme in our paper. (The purpose of our positive results is to better characterize the failures.) Besides, many papers on social learning concentrate on two arms as a fundamental case, even for positive results. So, we strive to fully understand the 2-armed case, which – as we find -  allows for elegant guarantees, yet requires a rather complex “technical story” (see below).

That said, our negative results trivially extend to some instances with K>2 arms: e.g., just add K-2 arms with 0 reward. For some other instances, failure probabilities get much smaller (e.g., with many “best” arms, all of them need to experience a “bad” random event), or much larger (e.g., one good arm and many equally bad arms). We can spell out such extensions in the revision. 

However, a general characterization of failure probability for K>2 arms is likely to be much more cumbersome, as it would now depend on several arms. While it may be within reach given our techniques, the “technical story” in such characterization is likely to be quite complex (e.g., as complex as the story in our paper, and possibly more so). We feel strongly that we are already near the limit of what one could put into a single paper, both conceptually and because of the page limit. 
\
\
**[Generality]** While focusing on the basic learning problem, we allow considerable generality on the “behavioral side” (Lines 32-38, 183-189). We allow any behaviors consistent with the confidence intervals, possibly randomized and/or correlated across arms. In addition to greedy/unbiased behavior and varying levels of optimism/pessimism, this includes, e.g., versions of “active arms elimination” and “Thompson Sampling” (a.k.a. “probability matching” in behavioral economics). These behaviors can be arbitrarily different across agents, and also across arms (e.g., optimism on one arm, pessimism on the other). We also accommodate a form of “recency bias”, whereby one is more optimistic about an arm if more recent observations are better than the older ones. All these behaviors are well-documented in the literature on behavioral economics. We will include a more detailed discussion in the revision.
\
\
**[Greedy]** We believe the failure analysis of the greedy algorithm should stand on its own, as a badly missing foundational piece for bandit theory. While consistent with our expectations, it was not clear in hindsight which assumptions would be needed and what would be the “strength” and generality of the learning failures. 
\
\
**[Techniques]**  Our lower-bound analysis relies on anti-concentration and martingale tools, which are not very standard per se (see Lines 280-285), and very non-standard for bandit lower bounds. However, the main technical complexity is in _applying_ these tools, i.e., setting up the right events and arguing what happens when these events hold (especially so for Thm 3.9). The positive results reuse the standard UCB machinery, but require a much more delicate setup and analysis of the “clean events” (particularly so in Thm 4.5). Unfortunately, we could only hint at all this complexity in the body of the paper! (Lines 85-103). Our techniques and tricks provide foundation for subsequent work on bandit social learning in more complex learning problems.
\
\
**[Technical story]** The technical story in our paper is quite intricate, illustrating the complexity of the problem even for 2 arms, and necessitating a particular order of presentation. The story  proceeds from the main failure result (Thm 3.1) to handling a somewhat trickier case of small $N_0$ (Thm 3.9), to proving a much stronger failure for pessimistic agents (Thm 3.10). Bayesian beliefs are handled as a special case (Thm 5.1). The upper bounds proceed from uniform optimism (Thm 4.1) to upwards-varying optimism (Thm 4.4) to a small fraction of optimists  (Thm 4.5). Finally, there’s a much stronger result in a “fully Bayesian” setup, with a different proof.  
\
\
**[Not merging theorems Thm 3.1 and Thm 3.9]** Merging them would lose the appealing generality of behaviors in Thm 3.1, as well as its relative simplicity compared to Thm 3.9 (both in the statement and in the analysis). Further, the symmetry assumption (P1) in Thm 3.9 may actually break if an agent gives more “benefit of a doubt” to one of the arms when both arms look very bad. (E.g., what if when both Chinese and Italian restaurants look bad, one chooses Chinese.)  This is why we chose to separate these two results, specialized Thm 3.9 for the case of very small $N_0$, and in fact used Thm 3.1 to *motivate* Thm 3.9. 

Meta-review: The paper studied bandit social learning problem motivated by reviews on online platforms, where myopic users make decisions based on historical reviews and generate new reviews on the fly. The paper considered two-armed Bernoulli bandits where the myopic behavior follows choosing the index of action within some confidence bound of the empirical mean of the arm parametrized by $\eta$. The authors demonstrate negative results regarding myoptic behaviors of agents. Understanding when failure occurs is a novel result and a major contribution of the paper. The authors provide the regret lower bounds of $\eta$-confidence agents, together with nearly matching upper bounds, which explains why greedy algorithms are not efficient and why UCB1 algorithm requires extreme optimism. Overall, the reviewers appreciate the novel problem setting, the clear writing, the sound theoretical results, and the insights behind the negative results. One reviewer has concerns regarding the limitation of two-armed bandit setting and strong assumptions, but the authors' response addressed those concerns in my opinion. I recommend acceptance.
Decision: Accept (poster)