Competing Bandits: Learning under Competition
Yishay Mansour Aleksandrs Slivkins Zhiwei Steven Wu


Non-Concave Network Utility Maximization in Connectionless Networks: A Fully Distributed Traffic Allocation Algorithmacknowledgement

    Zhisheng Duanaddress_wang
    December 30, 2023
=====================================================================================================================================




Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition—how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems.

In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen.



We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the “competition vs. innovation" relationship, a well-studied theme in economics.








§ INTRODUCTION


Learning from interactions with users is ubiquitous in modern customer-facing systems, from product recommendations to web search to spam detection to content selection to fine-tuning the interface. Many systems purposefully implement exploration: making potentially suboptimal choices for the sake of acquiring new information. Randomized controlled trials, a.k.a. A/B testing, are an industry standard, with a number of companies such as Optimizely offering tools and platforms to facilitate them. Many companies use more sophisticated exploration methodologies based on multi-armed bandits, a well-known theoretical framework for exploration and making decisions under uncertainty.



Systems that engage in exploration typically need to compete against one another; most importantly, they compete for users. This creates an interesting tension between and . In a nutshell, while exploring may be essential for improving the service tomorrow, it may degrade quality and make users leave today, in which case there will be no users to learn from! Thus, users play three distinct roles: they are customers that generate revenue, they generate data for the systems to learn from, and they are self-interested agents which choose among the competing systems.


We initiate a study of the interplay between and . The main high-level question is: whether and to what extent competition incentivizes adoption of better exploration algorithms. This translates into a number of more concrete questions. While it is commonly assumed that better learning technology always helps, is this so for our setting? In other words, would a better learning algorithm result in higher utility for a principal? Would it be used in an equilibrium of the “competition game"? Also, does competition lead to better social welfare compared to a monopoly? We investigate these questions for several models, as we vary the capacity of users to make rational decisions () and the severity of competition between the learning systems (). The two are controlled by the same “knob" in our models; such coupling is not unusual in the literature, see <cit.>.

On a high level, our contributions can be framed in terms of the “inverted-U relationship" between rationality/competitiveness and the quality of adopted algorithms (see fig:inverted-U).

The relationship between the severity of competition among firms and the quality of technology adopted as a result of this competition is a familiar  theme in the economics literature, known as “competition vs. innovation".
[In this context, usually refers to adoption of a better technology as a substantial R&D expense to a given firm. It is not as salient whether similar ideas and/or technologies already exist outside the firm. ]
We frame our contributions in terms of the “inverted-U relationship", a conventional wisdom regarding “competition vs. innovation" (see fig:inverted-U).













Our model. We define a game in which two firms (principals) simultaneously engage in exploration and compete for users (agents). These two processes are interlinked, as exploration decisions are experienced by users and informed by their feedback. We need to specify several conceptual pieces: how the principals and agents interact, what is the machine learning problem faced by each principal, and what is the information structure. Each piece can get rather complicated in isolation, let alone jointly, so we strive for simplicity. Thus, the basic model is as follows:




  * A new agent arrives in each round t=1,2, …, and chooses among the two principals. The principal chooses an action (a list of web search results to show to the agent), the user experiences this action, and reports a reward. All agents have the same “decision rule" for choosing among the principals given the available information.


  * Each principal faces a very basic and well-studied version of the multi-armed bandit problem: for each arriving agent, it chooses from a fixed set of actions  (a.k.a. arms) and receives a reward drawn independently from a fixed distribution specific to this action.


  * Principals simultaneously announce their learning algorithms before round 1, and cannot change them afterwards. There is a common Bayesian prior on the rewards (but the realized reward distributions are not observed by the principals or the agents). Agents do not receive any other information. Each principal only observes agents that chose him.


Technical results.
Our results depend crucially on agents' “decision rule" for choosing among the principals. The simplest and perhaps the most obvious rule is to select the principal which maximizes their expected utility; we refer to it as . We find that is not conducive to adopting better algorithms. In fact, each principal's dominant strategy is to do no purposeful exploration whatsoever, and instead always choose an action that maximizes expected reward given the current information; we call this algorithm . While this algorithm may potentially try out different actions over time and acquire useful information, it is known to be dramatically bad in many important cases of multi-armed bandits — precisely because it does not explore on purpose, and may therefore fail to discover best/better actions. Further, we show that is very sensitive to tie-breaking when both principals have exactly the same expected utility according to agents' beliefs. If tie-breaking is probabilistically biased — say, principal 1 is always chosen with probability strictly larger than 12 — then this principal has a simple “winning strategy" no matter what the other principal does.

We relax to allow each principal to be chosen with some fixed baseline probability. One intuitive interpretation is that there are “random agents" who choose a principal uniformly at random, and each arriving agent is either or “random" with some fixed probability. We call this model . We find that better algorithms help in a big way: a sufficiently better algorithm is guaranteed to win all non-random agents after an initial learning phase. While the precise notion of “sufficiently better algorithm" is rather subtle, we note that commonly known “smart" bandit algorithms typically defeat the commonly known “naive" ones, and the latter typically defeat . However, there is a substantial caveat: one can defeat any algorithm by interleaving it with . This has two undesirable corollaries: a better algorithm may sometimes lose, and a pure Nash equilibrium typically does not exist.

We further relax the decision rule so that the probability of choosing a given principal varies smoothly as a function of the difference between  principals' expected rewards; we call it . For this model, the “better algorithm wins" result holds under much weaker assumptions on what constitutes a better algorithm. This is the most technical result of the paper. The competition in this setting is necessarily much more relaxed: typically, both principals attract approximately half of the agents as time goes by (but a better algorithm may attract slightly more).

All results extend to a much more general version of the multi-armed bandit problem in which the principal may observe additional feedback before and/or after each decision, as long as the feedback distribution does not change over time. In most results, principal's utility may depend on both the market share and agents' rewards.

Economic interpretation.
The inverted-U relationship between the severity of competition among firms and the quality of technologies that they adopt is a familiar theme in the economics literature <cit.>.
[The literature frames this relationship as one between “competition" and “innovation". In this context, “innovation" refers to adoption of a better technology, at a substantial R&D expense to a given firm. It is not salient whether similar ideas and/or technologies already exist outside the firm. It is worth noting that adoption of exploration algorithms tends to require substantial R&D effort in practice, even if the algorithms themselves are well-known in the research literature; see <cit.> for an example of such R&D effort.]
We find it illuminating to frame our contributions in a similar manner, as illustrated in fig:inverted-U.

Our models differ in terms of rationality in agents' decision-making: from fully rational decisions with to relaxed rationality with to an even more relaxed rationality with . The same distinctions also control the severity of competition between the principals: from cut-throat competition with to a more relaxed competition with , to an even more relaxed competition with . Indeed, with you lose all customers as soon as you fall behind in performance, with you get some small market share no matter what, and with you are further guaranteed a market share close to 12 as long as your performance is not much worse than the competition. The uniform choice among principals corresponds to no rationality and no competition.

We identify the inverted-U relationship in the spirit of fig:inverted-U that is driven by the rationality/competitiveness distinctions outlined above: from to to to . We also find another, technically different inverted-U relationship which zeroes in on the model. We vary rationality/competitiveness inside this model, and track the marginal utility of switching to a better algorithm.

These inverted-U relationships arise for a fundamentally different reason, compared to the existing literature on “competition vs. innovation.” In the literature, better technology always helps in a competitive environment, other things being equal. Thus, the tradeoff is between the costs of improving the technology and the benefits that the improved technology provides in the competition. Meanwhile, we find that a better exploration algorithm may sometimes perform much worse under competition, even in the absence of R&D costs.

Yishay's edits, slightly edited by Alex

Discussion. We capture some pertinent features of reality while ignoring some others for the sake of tractability. Most notably, we assume that agents do not receive any information about other agents' rewards after the game starts. In the final analysis, this assumption makes agents' behavior independent of a particular realization of the Bayesian prior, and therefore enables us to summarize each learning algorithm via its Bayesian-expected rewards (as opposed to detailed performance on the particular realizations of the prior). Such summarization is essential for formulating lucid and general analytic results, let alone proving them. It is a major open question whether one can incorporate signals about other agents' rewards and obtain a tractable model.

We also make a standard assumption that agents are myopic: they do not worry about how their actions impact their future utility. In particular, they do not attempt to learn over time, to second-guess or game future agents, or to manipulate principal's learning algorithm. We believe this is a typical case in practice, in part because agent's influence tend to be small compared to the overall system. We model this simply by assuming that each agent only arrives once.

Much of the challenge in this paper, both conceptual and technical, was in setting up the right model and the matching theorems, and not only in proving the theorems. Apart from making the modeling choices described above, it was crucial to interpret the results and intuitions from the literature on multi-armed bandits so as to formulate meaningful assumptions on bandit algorithms and Bayesian priors which are productive in our setting.

Open questions.
How to incorporate signals about the other agents' rewards? One needs to reason about how exact or coarse these signals are, and how the agents update their beliefs after receiving them. Also, one may need to allow principals' learning algorithms to respond to updates about the other principal's performance. (Or not, since this is not how learning algorithms are usually designed!) A clean, albeit idealized, model would be that (i) each agent learns her exact expected reward from each principal before she needs to choose which principal to go to, but (ii) these updates are invisible to the principals. Even then, one needs to argue about the competition on particular realizations of the Bayesian prior, which appears very challenging.

Another promising extension is to heterogeneous agents. Then the agents' choices are impacted by their idiosyncratic signals/beliefs, instead of being entirely determined by priors and/or signals about the average performance. It would be particularly interesting to investigate the emergence of specialization: whether/when an algorithm learns to target specific population segments in order to compete against a more powerful “incumbent".
 


Map of the paper.
We survey related work (Section <ref>), lay out the model and preliminaries (Section <ref>), and proceed to analyze the three main models, , and (in Sections <ref>, <ref>, and  <ref>, respectively). We discuss economic implications in Section <ref>. Appendix <ref> provides some pertinent background on multi-armed bandits. Appendix <ref> gives a broad example to support an  assumption in our model.












§ RELATED WORK


Multi-armed bandits (MAB) is a particularly elegant and tractable abstraction for tradeoff between exploration and exploitation: essentially, between acquisition and usage of information. MAB problems have been studied in Economics, Operations Research and Computer Science for many decades; see <cit.> for background on regret-minimizing and Bayesian formulations, respectively. A discussion of industrial applications of MAB can be found in <cit.>.

The literature on MAB is vast and multi-threaded. The most related
thread concerns regret-minimizing MAB formulations with IID rewards
<cit.>. This thread includes “smart" MAB
algorithms that combine exploration and exploitation, such as UCB1
<cit.> and Successive Elimination
<cit.>, and “naive” MAB algorithms that separate
exploration and exploitation, including explore-first and
-Greedy <cit.>.

The three-way tradeoff between exploration, exploitation and incentives has been studied in several other settings:
incentivizing exploration in a recommendation system
    <cit.>,
dynamic auctions
    <cit.>,
pay-per-click ad auctions with unknown click probabilities
    <cit.>,
coordinating search and matching by self-interested agents
    <cit.>,
as well as human computation
    <cit.>.

<cit.> studied models with self-interested agents jointly performing exploration, with no principal to coordinate them.

There is a superficial similarity (in name only) between this paper and the line of work on “dueling bandits"
    <cit.>.
The latter is not about competing bandit algorithms, but rather about scenarios where in each round two arms are chosen to be presented to a user, and the algorithm only observes which arm has “won the duel".

Our setting is closely related to the “dueling algorithms" framework <cit.> which studies competition between two principals, each running an algorithm for the same problem. However, this work considers algorithms for offline / full input scenarios, whereas we focus on online machine learning and the explore-exploit-incentives tradeoff therein. Also, this work specifically assumes binary payoffs (win or lose) for the principals.

Other related work in economics. The competition vs. innovation relationship and the inverted-U shape thereof have been introduced in a classic book <cit.>, and remained an important theme in the literature ever since <cit.>. Production costs aside, this literature treats innovation as a priori beneficial for the firm. Our setting is very different, as innovation in exploration algorithms may potentially hurt the firm.

A line of work on platform competition, starting with <cit.>, concerns competition between firms (platforms) that improve as they attract more users (network effect); see <cit.> for a recent survey. This literature is not concerned with , and typically models network effects exogenously, whereas in our model network effects are endogenous: they are created by MAB algorithms, an essential part of the model.

Relaxed versions of rationality similar to ours are found in several notable lines of work. For example, “random agents" (a.k.a. noise traders) can side-step the “no-trade theorem” <cit.>, a famous impossibility result in financial economics. The model is closely related to the literature on product differentiation, starting from <cit.>, see <cit.> for a notable later paper.

There is a large literature on non-existence of equilibria due to small deviations   (which is related to the corresponding result for ), starting with <cit.> in the context of health insurance markets. Notable recent papers <cit.> emphasize the distinction between and versions of .


While agents' rationality and severity of competition are often modeled separately in the literature, it is not unusual to have them modeled with the same “knob" <cit.>.












§ OUR MODEL AND PRELIMINARIES




Principals and agents. There are two principals and T agents. The game proceeds in rounds (we will sometimes refer to them as global rounds). In each round t∈ [T], the following  interaction takes place. A new agent arrives and chooses one of the two principals. The principal chooses a recommendation: an action a_t∈ A, where A is a fixed set of actions (same for both principals and all rounds). The agent follows this recommendation, receives a reward r_t∈ [0,1], and reports it back to the principal.

The rewards are i.i.d. with a common prior. More formally, for each action a∈ A there is a parametric family ψ_a(·) of
reward distributions, parameterized by the mean reward μ_a. (The paradigmatic case is 0-1 rewards with a given expectation.) The
mean reward vector μ = (μ_a:  a∈ A) is drawn from prior distribution  before round 1. Whenever a given action a∈ A is chosen, the reward is drawn independently from distribution ψ_a(μ_a). The prior  and the distributions (ψ_a(·) a∈ A) constitute the (full) Bayesian prior on rewards, denoted .

Each principal commits to a learning algorithm for making recommendations. This algorithm follows a protocol of multi-armed bandits (MAB). Namely, the algorithm proceeds in time-steps:
[These time-steps will sometimes be referred to as local steps/rounds, so as to distinguish them from “global rounds" defined before. We will omit the local vs. local distinction when clear from the context.] each time it is called, it outputs a chosen action a∈ A and then inputs the reward for this action. The algorithm is called only in global rounds when the corresponding principal is chosen.


The information structure is as follows. The prior  is known to everyone. The mean rewards μ_a are not revealed to anybody. Each agent knows both principals' algorithms, and the global round when (s)he arrives, but not the rewards of the previous agents. Each principal is completely unaware of the rounds when the other is chosen.

Some terminology. The two principals are called “Principal
1" and “Principal 2".

The algorithm of principal i∈{1,2} is called “algorithm i" and denoted
[i]. The agent in global round t is called “agent t"; the
chosen principal is denoted i_t.



Throughout, [·] denotes expectation over all applicable randomness.

Bayesian-expected rewards.
Consider the performance of a given algorithm [i], i∈{1,2}, when it is run in isolation (without competition, just as a bandit algorithm). Let _i(n) denote its Bayesian-expected reward for the n-th step.

Now, going back to our game, fix global round t and let n_i(t) denote the number of global rounds before t in which this principal is chosen. Then:

    [r_t |principal i is chosen in round t and n_i(t)=n ]
        = _i(n+1)    (∀ n∈).


Agents' response.
Each agent t chooses principal i_t as as follows: it chooses a distribution over the principals, and then draws independently from this distribution. Let p_t be the probability of choosing principal 1 according to this distribution. Below we specify p_t; we need to be careful so as to avoid a circular definition.

Let _t be the information available to agent t before the
round. Assume _t suffices to form posteriors for quantities
n_i(t), i∈{1,2}, denote them by it. Note
that the Bayesian expected reward of each principal i is a function
only of the number rounds he was chosen by the agents, so the
posterior mean reward for each principal i can be written as

    _i(t) := [r_t |_t and i_t=i ]
        = [_i(n_i(t)+1) |_t]
        = _n∼it[_i(n+1)].

This quantity represents the posterior mean reward for principal i
at round t, according to information _t; hence the notation . In general, probability p_t is defined by the
posterior mean rewards _i(t) for both principals. We assume a
somewhat more specific shape:

    p_t = ( _1(t) - _2(t)  ).

Here :[-1,1]→ [0,1] is the response function, which is the same for all agents. We assume that the response function is known to all agents.

To make the model well-defined, it remains to argue that information _t is indeed sufficient to form posteriors on n_1(t) and n_2(t). This can be easily seen using induction on t.

Since all agents arrive with identical information (other than knowing which global round they arrive in), it follows that all agents have identical posteriors for n_i,t (for a given principal i and a given global round t). This posterior is denoted it.

Response functions.
We use the response function  to characterize the amount of rationality and competitiveness in our model. We assume that  is monotonically non-decreasing, is larger than 12 on the interval (0,1], and smaller than 12 on the interval [-1,0). Beyond that, we consider three specific models, listed in the order of decreasing rationality and competitiveness (see fig:response-functions):





  * :  equals 0 on the interval [-1,0) and 1
  on the interval (0,1]. In other words, the agents will
  deterministically choose the principal with the higher posterior
  mean reward.


  * :
    
     equals _0 on the interval [-1,0) and 1-_0 on the interval (0,1], where _0∈ (0,12) are some positive constants. In words, each agent is a agent with probability 1-2_0, and with the remaining probability she makes a random choice.



  * : (·) lies in the interval [_0,1-_0], _0>0, and is “smooth" around 0 (in the sense defined precisely in Section <ref>).



We say that  is symmetric if (-x)+(x)=1
for any x∈ [0,1]. This implies fair tie-breaking:
(0)=12.


MAB algorithms.
We characterize the inherent quality of an MAB algorithm in terms of its Bayesian Instantaneous Regret (henceforth, ), a standard notion from machine learning:

    (n) := _μ∼[ max_a∈ Aμ_a] - (n),

where (n) is the Bayesian-expected reward of the algorithm for the n-th step, when the algorithm is run in isolation. We are primarily interested in how scales with n; we treat K, the number of arms, as a constant unless specified otherwise.

We will emphasize several specific algorithms or classes thereof:



  * “smart" MAB algorithms that combine exploration and exploitation, such as UCB1 <cit.> and Successive Elimination <cit.>. These algorithms achieve
        (n) ≤Õ(n^-1/2)
    for all priors and all (or all but a very few) steps n. This bound is known to be tight for any fixed n.
    [This follows from the lower-bound analysis in <cit.>.]


  * “naive" MAB algorithms that separate exploration and exploitation, such as Explore-then-Exploit and -Greedy. These algorithms have dedicated rounds in which they explore by choosing an action uniformly at random. When these rounds are known in advance, the algorithm suffers constant in such rounds. When the “exploration rounds" are instead randomly chosen by the algorithm, one can usually guarantee an inverse-polynomial upper bound , but not as good as the one above: namely,
        (n) ≤Õ(n^-1/3).
    This is the best possible upper bound on for the two algorithms mentioned above.


  * : at each step, recommends the best action according to the current posterior: an action a with the highest posterior expected reward
        [μ_a |],
     where  is the information available to the algorithm so far.
     has (at least) a constant for some reasonable priors, (n)>Ω(1).


  * : always recommends the prior best action,an action a with the highest prior mean reward  _μ∼[μ_a]. This algorithm typically has constant .


We focus on MAB algorithms such that (n) is non-increasing; we call such algorithms monotone. While some reasonable MAB algorithms may occasionally violate monotonicity, they can usually be easily modified so that monotonicity violations either vanish altogether, or only occur at very specific rounds (so that agents are extremely unlikely to exploit them in practice).

More background and examples can be found in Appendix <ref>. In particular, we prove that is monotone.



Competition game between principals.
Some of our results explicitly study the game between the two principals. We model it as a simultaneous-move game: before the first agent arrives, each principal commits to an MAB algorithm. Thus, choosing a pure strategy in this game corresponds to choosing an MAB algorithm (and, implicitly, announcing this algorithm to the agents).

Principal's utility is primarily defined as the market share, the number of agents that chose this principal. Principals are risk-neutral, in the sense that they optimize their expected utility.

Assumptions on the prior. We make some technical assumptions for the sake of simplicity. First, each action a has a positive probability of being the best action according to the prior:

    ∀ a∈ A:   _μ∼[μ_a  > μ_a' ∀ a'∈ A]
    > 0.


Second, posterior mean rewards of actions are pairwise distinct almost
surely. That is, the history h at any step of an MAB algorithm
[The history of an MAB algorithm at a given step
  comprises the chosen actions and the observed rewards in all
  previous steps in the execution of this algorithm.]
 satisfies

    [μ_a | h] ≠[μ_a'| h]   ∀ a,a'∈ A,

except at a set of histories of probability 0.  In
particular, prior mean rewards of actions are pairwise distinct:
[μ_a] ≠[μ_a'] for any a,a'∈ A. 

We provide two examples for which property (<ref>) is `generic', in the sense that it can be enforced almost surely by a
  small random perturbation of the prior. Both examples focus on 0-1 rewards and priors  that are independent across arms. The first example
  assumes Beta priors on the mean rewards, and is very easy.
  [Suppose the rewards are Bernouli r.v. and the mean reward
    μ_a for each arm a is drawn from some Beta distribution
    Beta(α_a, β_a). Given any history that contains
    h_a number of heads and t_a number of tails from arm a, the
    posterior mean reward is
    α_a + h_a/α_a + h_a + β_a + t_a. Note that
    h_a and t_a take integer values. Therefore, perturbing the
    parameters α_a and β_a independently with any
    continuous noise will induce a prior with property
    (<ref>) with probability 1.  ]  The second
  example assumes that mean rewards have a
  finite support, see Appendix <ref> for details.

Some more notation. Without loss of generality, we label actions as A=[K] and sort them according to their prior mean rewards, so that
    [μ_1] > [μ_2] > … > [μ_K].

Fix principal i∈{1,2} and (local) step n. The arm chosen by algorithm [i] at this step is denoted a_i,n, and the corresponding is denoted _i(n). History of [i] up to this step is denoted H_i,n.


Write
    (a| E) = [μ_a | E]
for posterior mean reward of action a given event E.





 §.§ Generalizations



Our results can be extended compared to the basic model described above.





First, unless specified otherwise, our results allow a more general notion of principal's utility that can depend on both the market share and agents' rewards. Namely, principal i collects U_i(r_t) units of utility in each global round t when she is chosen (and 0 otherwise), where U_i(·) is some fixed non-decreasing function with U_i(0)>0. In a formula,

    U_i := ∑_t=1^T i_t=i· U_i(r_r).


Second, our results carry over, with little or no modification of the proofs, to much more general versions of MAB, as long as it satisfies the i.i.d. property. In each round, an algorithm can see a context before choosing an action (as in contextual bandits) and/or additional feedback other than the reward after the reward is chosen (as in, semi-bandits), as long as the contexts are drawn from a fixed distribution, and the (reward, feedback) pair is drawn from a fixed distribution that depends only on the context and the chosen action. The Bayesian prior  needs to be a more complicated object, to make sure that and are well-defined. Mean rewards may also have a known structure, such as Lipschitzness, convexity, or linearity; such structure can be incorporated via . All these extensions have been studied extensively in the literature on MAB, and account for a substantial segment thereof; see <cit.> for background and details.






 §.§ Chernoff Bounds


We use an elementary concentration inequality known as Chernoff Bounds, in a formulation from <cit.>.


Consider n i.i.d. random variables X_1 … X_n with values in [0,1]. Let
    X = 1n∑_i=1^n X_i be their average, and let ν = [X]. Then:

    min( [ X-ν > δν ],  [ ν-X > δν ]
         )
        < e^-ν n δ^2/3  for any δ∈ (0,1).
























































§ FULL RATIONALITY (HARDMAX)



In this section, we will consider the version in which
the agents are fully rational, in the sense that their response function is . We show that principals are not incentivized to explore— to deviate from . The core technical result is that if one principal adopts , then the other principal loses all agents as soon as he deviates.

To make this more precise, let us say that two MAB algorithms deviate at (local) step n if there is an action a∈ A and a set of step-n histories of positive probability such that any history h in this set is feasible for both algorithms, and under this history the two algorithms choose action a with different probability.


  Suppose that an algorithm π is not dynamic greedy. Then
  the first exploration for π is the first time step where
  there is a non-zero probability that the recommended action has a
  lower expectation than exploitation option.define...





Assume response function with fair tie-breaking. Assume that [1] is , and [2] deviates from starting from some (local) step n_0<T. Then all agents in global rounds t≥ n_0 select principal 1.



The competition game between principals has a unique Nash equilibirium: both principals choose .




This corollary holds under a more general model which allows time-discounting: namely, the utility of each principal i in each global round t is U_i,t(r_t) if this principal is chosen, and 0 otherwise, where U_i,t(·) is an arbitrary non-decreasing function with U_i,t(0)>0.




 §.§ Proof of Theorem <ref>


The proof starts with two auxiliary lemmas: that deviating from implies a strictly smaller Bayesian-expected reward, and that implies a “sudden-death" property: if one agent chooses principal 1 with certainty, then so do all subsequent agents do. We re-use both lemmas in later sections, so we state them in sufficient generality.



Assume that [1] is , and [2] deviates from starting from some (local) step n_0<T. Then _1(n_0)>_2(n_0). This holds for any response function .


Lemma <ref> does not rely on any particular shape of the response function because it only considers the performance of each algorithm without competition.


Since the two algorithms coincide on the first n_0-1 steps, it follows by symmetry that histories H_1,n_0 and H_2,n_0 have the same distribution. We use a coupling argument: w.l.o.g., we assume the two histories coincide,
    H_1,n_0 = H_2,n_0 = H.

At local step n_0, chooses an action a_1,n_0 = a_1,n_0(H)
which maximizes the posterior mean reward given history H: for any realized history h∈(H) and any action a∈ A

    (a_1,n_0| H = h) ≥(a | H=h).


Rewrote the rest of the proof to account for positive-prob set of histories.

By assumption (<ref>), it follows that 

    (a_1,n_0| H = h) > (a | H=h)
       for any h∈(H) and a≠ a_1,n_0(h).


Since the two algorithms deviate at step n_0, there is a set S⊂(H) of step-n_0 histories such that [S]>0 and any history h∈ S satisfies
    [a_2,n_0≠ a_1,n_0| H=h]>0.
Combining this with (<ref>), we deduce that 

    (a_1,n_0| H = h) > [ μ_a_2,n_0| H=h ]
       for each history h∈ S.

Using (<ref>) and (<ref>) and integrating over realized histories h, we obtain
    _1(n_0) > _2(n_0).




Consider response function with (0)≥12. 
Suppose [1] is monotone, and _1(t_0)>_2(t_0) for some global round t_0. Then _1(t)>_2(t) for all subsequent rounds t.



Let us use induction on round t≥ t_0, with the base case t=t_0. Let =_1,t_0 be the agents' posterior distribution for n_1,t_0, the number of global rounds before t_0 in which principal 1 is chosen. By induction, all agents from t_0 to t-1 chose principal 1, so _2(t_0)= _2(t). Therefore,

    _1(t)
        = n∼_1(n+1+t-t_0)≥n∼_1(n+1)
        =_1(t_0) > _2(t_0)= _2(t),

where the first inequality holds because [1] is monotone, and the second one is the base case.



Since the two algorithms coincide on the first n_0-1 steps, it follows by symmetry that _1(n) = _2(n) for any n< n_0.
By Lemma <ref>,
    _1(n_0) > _2(n_0).

Recall that n_i(t) is the number of global rounds s<t in which principal i is chosen, and it is the agents' posterior distribution for this quantity. By symmetry, each agent t<n_0 chooses a principal uniformly at random. It follows that
    1n_0 = 2n_0
(denote both distributions by  for brevity), and (n_0-1)>0.
Therefore:

    _1(n_0)
         = n∼_1(n+ 1)
       = ∑_n = 0^n_0-1(n) ·_1(n + 1)
        > (n_0-1)·_2(n_0) + ∑_n = 0^n_0-2(n)·_2(n + 1)
       = n∼_2(n + 1) = _2(n_0)

So, agent n_0 chooses principal 1. By Lemma <ref> (noting that is monotone), all subsequent agents choose principal 1, too.
































 §.§ with biased tie-breaking



The model is very sensitive to the tie-breaking rule. For starters, if ties are  broken deterministically in favor of principal 1, then principal 1 can get all agents no matter what the other principal does, simply by using .


Assume response function with (0)=1 (ties are always broken in favor of principal 1). If [1] is , then all agents choose principal 1.



Agent 1 chooses principal 1 because of the tie-breaking rule. Since is trivially monotone, all the subsequent agents choose principal 1 by an induction argument similar to the one in the proof of Lemma <ref>.


A more challenging scenario is when the tie-breaking is biased in favor of principal 1, but not deterministically so: (0)>12. Then this principal also has a “winning strategy" no matter what the other principal does. Specifically, principal 1 can get all but the first few agents, under a mild technical assumption that deviates from . Principal 1 can use , or any other monotone MAB algorithm that coincides with in the first few steps.







Assume response function with (0)>12 (tie-breaking is biased in favor of principal 1). Assume the prior  is such that deviates from starting from some step n_0. Suppose that principal 1 runs a monotone MAB algorithm that coincides with in the first n_0 steps. Then all agents t≥ n_0 choose principal 1.




The proof re-uses Lemmas <ref> and <ref>, which do not rely on fair tie-breaking.

Because of the biased tie-breaking, for each global round t we have:

    if _1(t)≥_2(t) then [i_t=1]>12.

Recall that i_t is the principal chosen in global round t.

Let m_0 be the first step when [2] deviates from , or deviates from , whichever comes sooner. Then [2], and coincide on the first m_0-1 steps. Moreover, m_0≤ n_0 (since deviates from at step n_0), so [1] coincides with on the first m_0 steps.

So, _1(n)=_2(n) for each step n<m_0, because [1] and [2] coincide on the first m_0-1 steps. Moreover, if [2] deviates from at step m_0 then
    _1(m_0) > _2(m_0) 
by Lemma <ref>; else, we trivially have
    _1(m_0) = _2(m_0). To summarize:

    _1(n)≥_2(n)  for all steps n≤ m_0.


We claim that [i_t=1]>12 for all global rounds t≤ m_0. We prove this claim using induction on t. The base case t=1 holds by (<ref>) and the fact that in step 1, chooses the arm with the highest prior mean reward. For the induction step, we assume that [i_t=1]>12 for all global rounds t<t_0, for some t_0≤  m_0. It follows that distribution 1t_0 stochastically dominates distribution 2t_0.
[For random variables X,Y on , we say that X stochastically dominates Y if [X≥ x] ≥[Y≥ x] for any x∈.]
Observe that

    _1(t_0)
      = n∼1t_0_1(n+1)≥n∼2t_0_2(n+1)
      = _2(t_0).

So the induction step follows by (<ref>). Claim proved.

Now let us focus on global round m_0, and denote _i = im_0.  By the above claim,

    _1 stochastically dominates _2, and moreover
        _i(m_0-1)>_i(m_0-1).


By definition of m_0, either (i) [2] deviates from starting from local step m_0, which implies _1(m_0)> _2(m_0) by Lemma <ref>, or (ii) deviates from starting from local step m_0, which implies _1(m_0)>_1(m_0-1) by Lemma <ref>. In both cases, using (<ref>) and (<ref>), it follows that the inequality in (<ref>) is strict for t_0=m_0.

Therefore, agent m_0 chooses principal 1, and by Lemma <ref> so do all subsequent agents.



























































§ RELAXED RATIONALITY: HARDMAX & RANDOM


This section is dedicated to the response model, where each principal is always chosen with some positive baseline probability. The main technical result for this model states that a principal with asymptotically better wins by a large margin: after a “learning phase" of constant duration, all agents choose this principal with maximal possible probability (1). For example, a principal with (n)≤Õ(n^-1/2) wins over a principal with (n)≥Ω(n^-1/3). However, this positive result comes with a significant caveat detailed in Section <ref>.

We formulate and prove a cleaner version of the result, followed by a more general formulation developed in a subsequent Remark <ref>. We need to express a property that [1] eventually catches up and surpasses [2], even if initially it receives only a fraction of traffic. For the cleaner version, we assume that both algorithms are well-defined for an infinite time horizon, so that their does not depend on the time horizon T of the game.  Then this property can be formalized as:

    (∀>0)    _1( n)/_2(n) → 0.

In fact, a weaker version of (<ref>) suffices:
denoting _0 = (-1), for some constant n_0 we have

    (∀ n≥ n_0)     _1(_0 n/2)/_2(n) <12.

We also need a very mild technical assumption on the “bad" algorithm:

    (∀ n≥ n_0)     _2(n) > 4 e^-_0 n/12.



Assume response function. Suppose both algorithms are monotone and well-defined for an infinite time horizon, and satisfy (<ref>) and (<ref>). Then each agent t≥ n_0 chooses principal 1 with maximal possible probability (1) = 1- _0.



Consider global round t≥ n_0. Recall that each agent chooses principal 1 with probability at least
    (-1)>0.

Then
    [n_1(t+1)] ≥ 2_0 t.
By Chernoff Bounds (Theorem <ref>), we have that
    n_1(t+1)≥_0 t
holds with probability at least 1-q,
where q = exp(-_0 t/12).

We need to prove that
    _1(t) - _2(t)>0.
For any m_1 and m_2, consider the quantity

    Δ(m_1,m_2) := _2(m_2+1) - _1(m_1+1).

Whenever m_1 ≥_0 t/2 -1 and m_2<t, it holds that

    Δ(m_1,m_2) ≥Δ(_0 t / 2, t)
        ≥_2(t)/2.

The above inequalities follow, resp., from algorithms' monotonicity and (<ref>). Now,

    _1(t) - _2(t)
           = m_1∼1t, m_2∼2tΔ(m_1,m_2)
       ≥ -q
            + m_1∼1t, m_2∼2tΔ(m_1,m_2)| m_1 ≥_0 t/2-1
       ≥_2(t)/2-q 
       > _2(t)/4 > 0  by (<ref>).




  Many standard MAB algorithms in the literature are parameterized by
  the time horizon T. Regret bounds for such algorithms usually
  include a polylogarithmic dependence on T. In particular, a
  typical upper bound for has the following form:
  [We
    provide upper bounds on for several standard MAB algorithms
    to illustrate these dependencies in the appendix.added]

    (n| T)≤(T)· n^-γ  for some γ∈(0,12].

Here we write (n| T) to emphasize the dependence on T.

We generalize (<ref>) to handle the dependence
on T: there exists a number T_0 and a function n_0(T)∈(T) 
such that 

    (∀ T≥ T_0,  n≥ n_0(T))   _1(_0 n /2| T)/_2(n| T) <1/2.

If this holds, we say that [1] BIR-dominates [2].

We provide a version of Theorem <ref> in which algorithms are parameterized with time horizon T and condition (<ref>) is replaced with (<ref>); its proof is very similar and is omitted.











To state a game-theoretic corollary of Theorem <ref>, we consider a version of the competition game between the two principals in which they can only choose from a finite set  of monotone MAB algorithms. One of these algorithms is “better" than all others; we call it the special algorithm. Unless specified otherwise, it BIR-dominates all other allowed algorithms. The other algorithms satisfy (<ref>). We call this game the restricted competition game.


Assume response function. Consider the restricted competition game with special algorithm . Then, for any sufficiently large time horizon T, this game has a unique Nash equilibrium: both principals choose .





 §.§ A little greedy goes a long way



Given any monotone MAB algorithm other than , we design a modified algorithm which learns at a slower rate, yet “wins the game" in the sense of Theorem <ref>. As a corollary, the competition game with unrestricted choice of algorithms typically does not have a Nash equilibrium.

Given an algorithm [1] that deviates from starting from
step n_0 and a “mixing” parameter p, we will construct a
modified algorithm as follows.


  * The modified algorithm coincides with [1] (and )
for the first n_0-1 steps;

  * In each step n≥ n_0, [1] is invoked with probability
  1-p, and with the remaining probability p does the “greedy
  choice": chooses an action with the largest posterior mean reward
  given the current information collected by [1].


For a cleaner comparison between the two algorithms, the modified algorithm does not record rewards received in steps with the “greedy choice". Parameter p>0 is the same for all steps.


Assume symmetric response function. Let _0 = (-1) be the baseline probability. Suppose [1] deviates from starting from some step n_0. Let [2] be the modified algorithm, as described above, with mixing parameter p such that
    (1-_0)(1-p)>_0.
Then each agent t≥ n_0 chooses principal 2 with maximal possible probability 1-_0.



  Suppose that both principals can choose any monotone MAB algorithm, and assume the symmetric response
  function. Then for any time
  horizon T, the only possible pure Nash equilibrium is one
  where both principals choose . Moreover, no pure Nash
  equilibrium exists when some algorithm “dominates" in
  the sense of (<ref>) and the time horizon T
  is sufficiently large.




The modified algorithm performs exploration 
at a slower rate. Let us argue how this may translate  into a larger compared to the original algorithm. Let  '_1(n) be the of the “greedy choice" after after n-1 steps of [1]. Then

    _2(n)
           = m∼ (n_0-1)+Binomial(n-n_0+1,1-p)(1-p) ·_1(m) + p ·'_1(m).

In this expression, m is the number of times [1] is invoked in the first n steps of the modified algorithm. Note that
    [m] = n_0-1 + (n-n_0+1)(1-p) ≥ (1-p)n.

Suppose _1(n)= β n^-γ for some constants β,γ>0. Further, assume 
    '_1(n)≥  c _1(n),
for some c>1-γ.
Then for all n≥ n_0 and small enough p>0 it holds that:

    _2(n) 
           ≥  (1-p+pc) [ _1(m)  ] 
    [ _1(m)  ]
           ≥_1( [m]  )        (By Jensen's inequality)
       ≥_1(  (1-p)n  )        (since [m]≥ n(1-p))
       ≥β· n^-γ· (1-p)^-γ       (plugging in _1(n)=β n^-γ)
       > _1(n)   (1-pγ)^-1       (since (1-p)^γ < 1-pγ).
    _2(n) 
           >α·_1(n),
           where  α = 1-p+pc1-pγ>1.

(In the above equations, all expectations are over m distributed as in (<ref>).)




  Let '_1(n) denote the Bayesian-expected reward of the “greedy
  choice” after after n-1 steps of [1]. Note that
  _1(·) and '_1(·) are non-decreasing: the former
  because [1] is monotone and the latter because the “greedy
  choice” is only improved with an increasing set of
  observations. Therefore, the modified algorithm [2] is monotone
  by (<ref>).

  By definition of the “greedy choice,” _1(n)≤'_1(n)
  for all steps n. Moreover, by Lemma <ref>,
  [1] has a strictly smaller (n_0) compared to ;
  so, _1(n_0)<_2(n_0).fixed inequalities; but this paragraph is still not perfectly clear

Let  denote a copy of [1] that is running “inside" the modified algorithm [2]. Let m_2(t) be the number of global rounds before t in which the agent chooses principal 2 and is invoked; in other words, it is the number of agents seen by before global round t. Let _2,t be the agents' posterior distribution for m_2(t).

We claim that in each global round t≥ n_0, distribution _2,t stochastically dominates distribution 1t, and _1(t)<_2(t). We use induction on t. The base case t=n_0 holds because _2,t = 1t (because the two algorithms coincide on the first n_0-1 steps), and _1(n_0)<_2(n_0) is proved as in (<ref>), using the fact that _1(n_0)<_2(n_0).

The induction step is proved as follows. The induction hypothesis for global round t-1 implies that agent t-1 is seen by with probability (1-_0)(1-p), which is strictly larger than _0, the probability with which this agent is seen by [2]. Therefore, _2,t stochastically dominates 1t.

    _1(t)
         = n∼1t_1(n+1)
       ≤m∼_2,t_1(m+1)
       < m∼_2,t(1-p)·_1(m+1) + p·'_1(m+1)
       = _2(t).

Here inequality (<ref>) holds because _1(·) is monotone and _2,t stochastically dominates 1t, and inequality (<ref>) holds because _1(n_0)<_2(n_0) and _2,t(n_0)>0.
[If _1(·) is strictly increasing, then inequality (<ref>) is strict, too; this is because _2,t(t-1)>1t(t-1).  ]










§ SOFTMAX RESPONSE FUNCTION


This section is devoted to the model. We recover a positive result under the assumptions from Theorem <ref> (albeit with a weaker conclusion), and then proceed to a much more challenging result under weaker assumptions. We start with a formal definition:


A response function  is if the following conditions hold:


  * (·) is bounded away from 0 and 1:
    (·)∈ [,1-] for some ∈ (0,12),

  * the response function
 (·) is “smooth" around 0:
 
    ∃ constants δ_0,c_0,c'_0>0    ∀ x∈ [-δ_0,δ_0]     
        c_0 ≤'(x) ≤ c'_0.


  * fair tie-breaking: (0)=12.




This definition is fruitful when parameters c_0 and c_0' are close to 12. Throughout, we assume that [1] is better than [2], and obtain results parameterized by c_0. By symmetry, one could assume that [2] is better than [1], and obtain similar results parameterized by c_0'.


Our first result is a version of Theorem <ref>, with the same assumptions about the algorithms and essentially the same proof. The conclusion is much weaker: we can only guarantee that each agent t≥ n_0 chooses principal 1 with probability slightly larger than 12. This is essentially unavoidable in a typical case when both algorithms satisfy (n)→ 0, by Definition <ref>.


  Assume response function. Suppose [1] has better
  in the sense of (<ref>), and [2]
  satisfies the condition (<ref>). Then each agent
  t≥ n_0 chooses principal 1 with probability

    [i_t = 1]≥12 +  c_04 _2(t).




We follow the steps in the proof of Theorem <ref> to derive 
    _1(t) - _2(t)
           ≥_2(t)/2 -q,
          where q = exp(-_0 t/12).

This is at least _2(t)/4 by (<ref>). Then (<ref>) follows by the smoothness condition (<ref>).




We recover a version of Corollary <ref>, if each principal's utility is the number of users (rather than the more general model in (<ref>)). We also need a mild technical assumption that cumulative Bayesian regret () tends to infinity. is a standard notion from the literature (along with ):

    (n) := n·_μ∼[ max_a∈ Aμ_a] - ∑_n=1^n (n')
        = ∑_n'=1^n (n').



Assume that the response function is , and each principal's  utility is the number of users.



Consider the restricted competition game with special algorithm , and assume that all other allowed algorithms satisfy (n)→∞. Then, for any sufficiently large time horizon T, this game has a unique Nash equilibrium: both principals choose .


Further, we prove a much more challenging result in which the
condition (<ref>) is replaced with a much
weaker “BIR-dominance” condition. For clarity, we will again assume
that both algorithms are well-defined for an infinite time
horizon. The weak BIR dominance condition says there exist
constants β_0, α_0∈ (0, 1/2) and n_0 such that
 
    (∀ n≥ n_0)   _1((1-β_0)  n)/_2(n) <1-α_0.







 If this holds, we say that [1] weakly BIR-dominates
 [2]. Note that the condition (<ref>)
 involves sufficiently small multiplicative factors (resp., _0/2
 and 12), the new condition replaces them with factors that
 can be arbitrarily close to 1.

 We make a mild assumption on [1] that its _1(n) tends to
 0. Formally, for any > 0, there exists some n() such
 that
 
    (∀ n≥ n())     _1(n) ≤.

 We also require a slightly stronger version of the technical
 assumption (<ref>):
 
for some n_0,

    (∀ n≥ n_0)     _2(n) ≥4/α_0exp( -min{_0, 1/8} n/12)






  Assume the response function. Suppose [1]
  weakly-BIR-dominates [2], [1] satisfies (<ref>),
  and [2] satisfies (<ref>). Then there
  exists some t_0 such that each agent t≥ t_0 chooses principal
  1 with probability

    [i_t = 1]≥12 +  c_0α_04 _2(t).






The main idea behind our proof is that even though [1] may have a
slower rate of learning in the beginning, it will gradually catch up
and surpass [2]. We will describe this process in two phases. In
the first phase, [1] receives a random agent with probability at
least (-1) = _0 in each round. Since _1 tends to 0,
the difference in s between the two algorithms is also
diminishing. Due to the response function, [1]
attracts each agent with probability at least 1/2 - O(β_0) after
a sufficient number of rounds. Then the game enters the second phase:
both algorithms receive agents at a rate close to 12, and the
fractions of agents received by both algorithms — n_1(t)/t and
n_2(t)/t — also converge to 12. At the end of the second
phase and in each global round afterwards, the counts n_1(t) and
n_2(t) satisfy the weak BIR-dominance condition, in the sense that
they both are larger than n_0 and n_1(t)≥ (1-β_0)  n_2(t).
At this point, [1] actually has smaller , which reflected in the s eventually. Accordingly, from then on [1]
attracts agents at a rate slightly larger than 12. We prove
that the “bump” over 12 is at least on the order of
_2(t).



  Let β_1 = min{c_0'δ_0, β_0/20} with δ_0
  defined in (<ref>).  Recall each agent chooses
  [1] with probability at least (-1)= _0.  By
  condition (<ref>) and (<ref>),
  there exists some sufficiently large T_1 such that for any
  t≥ T_1, _1(_0 T_1/2) ≤β_1/c_0' and
  _2(t) > e^-_0 t/12. Moreover, for any t≥ T_1, we
  know [n_1(t+1)] ≥_0 t, and by the Chernoff Bounds
  (Theorem <ref>), we have n_1(t+1) ≥_0 t/2
  holds with probability at least 1 - q_1(t) with
  q_1(t) = exp(-_0 t/12) < _2(t). It follows that for any t≥ T_1,

    _2(t) - _1(t)    = m_1∼1t, m_2∼2t_1(m_1+ 1) - _2(m_2+1)
       ≤ q_1(t)  + m_1∼1t_1(m_1+ 1)| m_1 ≥_0 t/2 - 1  - _2(t)
       ≤_1(_0 T_1/2) ≤β_1/c_0'


Since the response function  is c_0'-Lipschitz in the
neighborhood of [-δ_0, δ_0], each agent after round T_1
will choose [1] with probability at least

    p_t ≥1/2 - c_0'(_2(t) - _1(t)) ≥1/2 - β_1.


Next, we will show that there exists a sufficiently large T_2 such
that for any t≥ T_1 + T_2, with high probability
n_1(t) > max{n_0, (1 - β_0)n_2(t)}, where n_0 is defined
in (<ref>). 


Fix any t ≥ T_1 + T_2. 
Since each agent chooses [1] with probability at least
1/2 - β_1, by Chernoff Bounds (Theorem <ref>) we
have with probability at least 1 - q_2(t) that the number of agents
that choose [1] is at least β_0(1/2 - β_1)t/5, where the
function

    q_2(x) = exp( -(1/2 - β_1)(1 - β_0/5)^2x/3).

Note that the number of agents received by [2] is at most
T_1 + (1/2 + β_1)t + (1/2 - β_1)(1 - β_0/5)t.

Then as long as




T_2 ≥5T_1/β_0, we can guarantee that
n_1(t) > n_2(t) (1 - β_0) and n_1(t) > n_0 with probability at
least 1 - q_2(t) for any t ≥ T_1 + T_2.







Note that the weak BIR-dominance condition
in (<ref>) implies that for any t≥ T_1 + T_2
with probability at least 1 - q_2(t),

    _1(n_1(t)) < (1- α_0)_2(n_2(t)).

It follows that for any t≥ T_1 + T_2,

    _1(t) - _2(t)    = m_1∼1t, m_2∼2t_2(m_2+ 1) - _1(m_1+1)
       ≥ (1 - q_2(t))α_0 _2(t) - q_2(t)
       ≥α_0 _2(t)/4

where the last inequality holds as long as
q_2(t) ≤α_0_2(t)/4, and is implied by the condition
in (<ref>) as long as T_2 is sufficiently
large. Hence, by the definition of our response
function and assumption in (<ref>), we have

    [i_t = 1] ≥1/2 + c_0α_0_2(t)/4.





Similar to the condition (<ref>), we can also
generalize the weak BIR-dominance condition (<ref>)
to handle the dependence on T: there exist some T_0, a function
n_0(T)∈(T), and constants β_0,α_0∈ (0, 1/2), such that 

    (∀ T≥ T_0,  n≥ n_0(T))   _1((1-β_0)  n| T)/_2(n| T) <1-α_0.


We also provide a version of Theorem <ref> under this
more general weak BIR-dominance condition; its proof is very similar
and is omitted. The following is just a direct consequence of
Theorem <ref> with this general condition.added




Assume that the response function is , and each principal's  utility is the number of users. Consider the restricted competition game in which the special algorithm weakly-BIR-dominates the other allowed algorithms, and the latter satisfy (n)→∞. Then, for any sufficiently large time horizon T, there is a unique Nash equilibrium: both principals choose .













§ ECONOMIC IMPLICATIONS


We frame our contributions in terms of the relationship between and on one side, and adoption of better algorithms on the other. Recall that both (of the game between the two principals) and (of the agents) are controlled by the response function .

 
We frame our contributions in terms of the relationship between and , between the extent to which the game between the two principals is competitive, and the degree of innovation — adoption of better that these models incentivize. is controlled via the response function , and refers to the quality of the technology (MAB algorithms) adopted by the principals. The vs. relationship is well-studied in the economics literature, and is commonly known to often follow an inverted-U shape, as in fig:inverted-U (see Section <ref> for citations). in our models is closely correlated with : the extent to which agents make rational decisions, and indeed is what  controls directly.
 

Main story.
Our main story concerns the restricted competition game between the two principals where one allowed algorithm is “better" than the others. We track whether and when is chosen in an equilibrium. We vary /by changing the response function from (full rationality, very competitive environment) to to  (less rationality and competition). Our conclusions are as follows:


  * Under , no innovation: is chosen over .

  * Under , some innovation:  is chosen as long as it BIR-dominates.

  * Under , more innovation: is chosen as long as it weakly-BIR-dominates.
[This is a weaker condition, the better algorithm is chosen in a broader range of scenarios.]

These conclusions follow, respectively, from Corollaries <ref>, <ref> and <ref>. Further, we consider the uniform choice between the principals. It corresponds to the least amount of rationality and competition, and (when principals' utility is the number of agents) uniform choice provides no incentives to innovate.
[On the other hand, if principals' utility is somewhat aligned with agents' welfare, as in (<ref>), then a monopolist principal is incentivized to choose the best possible MAB algorithm (namely, to minimize cumulative Bayesian regret (T)). Accordingly, monopoly would result in better social welfare than competition, as the latter is likely to split the market and cause each principal to learn more slowly. This is a very generic and well-known effect regarding economies of scale.]
Thus, we have an inverted-U relationship, see fig:inverted-U2.





Secondary story.
Let us zoom in on the symmetric  model. Competitiveness and rationality within this model are controlled by the baseline probability _0 = (- 1), which goes smoothly between the two extremes of (_0=0) and the uniform choice (_0=12). Smaller _0 corresponds to increased rationality and increased competitiveness. For clarity, we assume that principal's utility is the number of agents.

We consider the marginal utility of switching to a better algorithm. Suppose initially both principals use some algorithm , and principal 1 ponders switching to another algorithm ' which BIR-dominates . We are interested in the marginal utility of this switch. Then:



  * _0 = 0 ():     the marginal utility can be negative if is .


  * _0 near 0:     only a small marginal utility can be guaranteed, as it may take a long time for ' to “catch up" with , and hence less time to reap the benefits.


  * “medium-range" _0:     large marginal utility, as ' learns fast and gets most agents.


  * _0 near 12:     small marginal utility, as principal 1 gets most agents for free no matter what.

The familiar inverted-U shape is depicted in Figure <ref>.
















§ ACKNOWLEDGEMENTS

The authors would like to thank Glen Weyl for discussions of related work in economics.


plainnat








§ BACKGROUND ON MULTI-ARMED BANDITS









This appendix provides some pertinent background on multi-armed
bandits (MAB). We discuss and monotonicity of several MAB algorithms, touching upon: and (Section <ref>), “naive" MAB algorithms that separate exploration and exploitation (Section <ref>), and “smart" MAB algorithms that combine exploration and exploitation (Section <ref>).

As we do throughout the paper, we focus on MAB with i.i.d. rewards and a Bayesian prior; we call it Bayesian MAB for brevity.











 §.§ and 



We provide an example when and have
constant , and prove monotonicity of . For the
example, it suffices to consider deterministic rewards (for
each action a, the realized reward is always equal to the mean
μ_a) and independent priors (according to the prior
, random variables μ_1 μ_K are mutually
independent) each of full support.




































The following claim is immediate from the definition of the CDF
function

Assume independent priors. Let F_i be the CDF of the mean reward
μ_i of action a_i∈ A. Then, for any numbers
z_2>z_1>[μ_2] we have
    [μ_1≤ z_1 and μ_2≥ z_2] = F_1(z_1)(1-F_2(z_2)).

















We can now draw an immediate corollary of the above claim


Consider any problem instance of Bayesian MAB with two actions and independent
priors which are full support. Then:


  (a) With constant probability, has a constant for all steps.

  (b) Assuming deterministic rewards, with
constant probability has a constant for all steps.




A similar result holds for  rewards which are distributed as
Bernoulli random variables. In this case we consider accumulative
reward of an action as a random walk, and use a high probability
variation of the law of iterated logarithms. (Details omitted.)



Next, we show that is monotone.


is monotone, in the sense that (n) is non-decreasing.
Further, (n) is strictly increasing for every time step n with [a_n≠ a_n+1]>0.



We prove by induction on n that (n)≤(n+1) for
. Let a_n be the random variable recommended at time
t, then [μ_a_n| _n ]=(n). We can rewrite this as:

    (n)=__n[_r_n[μ_a_n|r_n,_n]] =
    __n+1[μ_a_n|_n+1]

since _n+1=(_n,r_n). At time n+1 will select
an action a_n+1 such that:

    (n+1)=[μ_a_n+1|_n+1]≥[μ_a_n
    |_n]=(n)









which proves the monotonicity. In cases that [a_n≠
a_n+1]>0] we have a strict inequality, since with some
probability we select a better action then the realization of a_n.







 §.§ “Naive" MAB algorithms that separate exploration and exploitation








MAB algorithm (m) initially explores each action
with m agents and for the remaining T-|A|m agents recommends the
action with the highest observed average. In the explore phase it
assigns a random permutation of the mK recommendations.



The (T^2/3log |A|/δ) algorithm has, with
probability 1-δ, for any  n≥ |A|T^2/3 we have
(n)=O(T^-1/3). In addition, (m) is monotone.



In the explore phase we we approximate for each action a∈ A, the
value of μ_a by μ̂_a. Using the standard Chernoff
bounds we have that with probability 1-δ, for every action
a∈ A we have |μ_a -μ̂_a| ≤ T^-1/3.

Let a^* = max_a μ_a and a^ee the action that
selects in the explore phase after the first
|A|T^2/3 agents. Since μ̂_a^*≤μ̂_a^ee, this implies that μ_a^* -
μ_a^ee=O(T^-1/3).

To show that (m) is monotone, we need to show only
that (mK) ≤(mK+1). This follows since for any t< mK
we have (t)=(t+1), since the recommended action is
uniformly distributed for each time t. Also, for any t≥ mK+1
we have (t)=(t+1) since we are recommending the same
exploration action. The proof that (mK) ≤(mK+1) is the
same as for in Lemma <ref>.


We can also have a a phased version which we call
(m_t), where time is partition in to phases.
In phase t we have m_t agents and a random subset of K explore
the actions (each action explored by a single agent) and the other
agents exploit. (This implies that we need that m_t≥ K for all
t. We also assume that m_t is monotone in t.)


Consider the case that K=2 and the rewards of the actions are
Bernoulli r.v. with parameter μ_i and Δ=μ_1-μ_2.
Algorithm (m_t) is monotone and for m_t =
√(t) it has (n)=O(n^-1/3+e^-O(Δ^2 n^2/3))). 



We first show that it is monotone. Recall that μ_1>μ_2. Let
S_i=∑_j=1^t r_i,j be the sum of the rewards of action i
up to phase t. We need to show that [S_1>S_2]+ (1/2)
[S_1=S_2] is monotonically increasing in t. Consider the
random variable Z=S_1-S_2. At each phase it increases by +1 with
probability μ_1(1-μ_2), decreases by -1 with probability
(1-μ_1)μ_2 and otherwise does not change.

Consider the values of Z up to phase t. We really care only
about the probability that is shifted from positive to negative and
vice versa.

First, consider the probability that Z=0. We can partition it to
S_1=S_2=r events, and let p(r,r) be the probability of this
event. For each such event, we have p(r,r)μ_1 moved to Z=+1
and p(r,r)μ_2 moved to Z=-1. Since μ_1>μ_2 we have that
p(r,r)μ_1≥ p(r,r)μ_2 (note that p(r,r) might be zero, so
we do not have a strict inequality).

Second, consider the probability that Z=+1 or Z=-1. We can
partition it to S_1=r+1;S_2=r and S_1=r;S_2=r+1 events, and let
p(r+1,r) and p(r,r+1) be the probabilities of those events.

It is not hard to see that p(r+1,r)μ_2=p(r,r+1)μ_1.

This implies that the probability mass moved from Z=+1 to Z=0 is
identical to that moved from Z=-1 to Z=0.

We have showed that [S_1>S_2]+ (1/2) [S_1=S_2] and therefore
the expected valued of the exploit action is non-decreasing. Since
we have that the size of the phases are increasing, the  is
strictly increasing between phases and identical within each phase.

We now analyze the  regret. Note that agent n is in phase
O(n^2/3) and the length of his phase is O(n^1/3). The 
has two parts. The first is due to the exploration, which is at most
O(n^-1/3). The second is due to the probability that we exploit
the wrong action. This happens with probability [S_1<S_2]+ (1/2)
[S_1=S_2] which we can bound using a Chernoff bound by
e^-O(Δ^2n^2/3), since we explored each action
O(n^2/3) times.



Actually we have a tradeoff depending on the parameter m_t between
the regret due to exploration and exploitation. (Note that the
monotonicity is always guarantee assuming m_t is monotone.) If we
can set that m_t = 2^t then at time n we have 2/ n probability
of an exploit action. For the explore action we are in phase log
n so the probability of a sub-optimal explore action is
n^-O(Δ^-2). This should give us
(n)=O(n^-O(Δ^-2)).




























































 §.§ “Smart" MAB algorithms that combine exploration and exploitation










































































































MAB algorithm works as follows. It keeps
a set of surviving actions A_s⊆ A, where initially
A_s=A. The agents are partition into phases, where each phase is a
random permutation of the non-eliminated actions.


Let μ̂_i,t be the average of the rewards of action i up
to phase t and μ̂^*=max_i μ̂_i,t. We eliminate
action i at the end of phase t, i.e., delete it from A_s, if
μ̂_t^*-μ̂_i,t > log(T/δ)/√(t).


In we simply reset the algorithm with
A=A_s-A_e,t, where A_e,t is the set of eliminated actions
after phase t. Namely, we restart μ̂_i,t and ignore the
old rewards before the elimination.



The algorithm , has, with probability
1-δ, (n)=O(log(T/δ)/√(n/K)).



Let the best action be a^*=max_a μ_a. With probability
1-δ at any time n we have that for any action i∈ A_s
that |μ̂_i -μ_i|≤log(T/δ)/√(n/K), and
a^*∈ A_s. This implies that any action a such
μ_a^*-μ_a> 3log(T/δ)/√(n/K) is eliminated.
Therefore, any action in A_s has (n) of at most
6log(T/δ)/√(n/K).



Assume that if μ_i≥μ_j then the rewards r_i
stochastically dominates the rewards r_j.

Then, is monotone



Consider the first time T an action is eliminated, and let
T=τ be a realized value of T. Then, clearly for n<τ we
have (n)=(1) .

Consider two actions a_1,a_2∈ A, such that μ_a_1≥μ_a_2. At time T=τ, the probability that  a_1 is
eliminated is smaller than the probability that a_2 is eliminated.
This follows since μ̂_a_1 stochastically dominates
μ̂_a_2, which implies that for any threshold θ we
have [μ̂_a_1≥θ]≥[μ̂_a_2≥θ].

After the elimination we consider the expected reward of the
eliminated action ∑_i∈ Aμ_i q_i, where q_i is the
probability that action i was eliminated in time T=τ. We have
that q_i ≤ q_i+1, from the probabilities of elimination.

The sum ∑_i∈ Aμ_i q_i with q_i ≤ q_i+1 and
∑_i q_i=1 is maximized by setting q_i=1/|A|. (We can see that
if there are q_i≠ 1/|A|, then there are two q_i< q_i+1,
and one can see that setting both to (q_i+ q_i+1)/2 increases
the value.) Therefore we have that the (τ)≥(τ-1).

Now we can continue by induction. For the induction, we can show the
property for any remaining set of at most k-1 actions. The
main issue is that restarts from scratch,
so we can use induction.





§ NON-DEGENERACY VIA A RANDOM PERTURBATION


We show that Assumption (<ref>) holds almost surely under a small random perturbation of the prior. We focus on problem instances with 0-1 rewards, and assume that the prior  is independent across arms and has a finite support.
[The assumption of 0-1 rewards is for clarity. Our results hold under a more general assumption that for each arm a, rewards can only take finitely many values, and each of these values is possible (with positive probability) for every possible value of the mean reward μ_a.]
 Consider the probability vector in the prior for arm a:

    p⃗_a = ( [μ_a=ν]: ν∈(μ_a) ).

We apply a small random perturbation independently to each such vector:

    p⃗_a ←p⃗_a + q⃗_a,
          where  q⃗_a∼_a.

Here _a is the noise distribution for arm a: a distribution over real-valued, zero-sum vectors of dimension d_a = |(μ_a)|. We need the noise distribution to satisfy the following property:

    ∀ x∈ [-1,1]^d_a∖{0}    _q∼_a[ x·(p⃗_a+ q) ≠ 0 ] =1.



Consider an instance of MAB with 0-1 rewards. Assume that the prior  is independent across arms, and each mean reward μ_a has a finite support that does not include 0 or 1. Assume that noise distributions _a satisfy property (<ref>). If random perturbation (<ref>) is applied independently to each arm a, then eq:assn-distinct holds almost surely for each history h.



As a generic example of a noise distribution which satisfies
  Property (<ref>), consider the uniform
  distribution  over the bounded convex set
  
    Q = {q ∈^d_a| q ·1⃗ = 0 q_2 ≤},
 where 1⃗ denotes the all-1
  vector. If x = a 1⃗ for some non-zero value of a, then
  (<ref>) holds because
  
    x · (p+q) = x · p = a≠ 0.
 Otherwise, denote
  p=p⃗_a and observe that x·(p+ q) = 0 only if
  x · q = c ≜ x · (-p). Since x≠1⃗, the
  intersection Q∩{ x· q = c } either is empty or has
  measure 0 in Q, which implies
  _q[ x·(p+ q) ≠ 0 ] =1.



To prove Theorem <ref>, it suffices to focus on two arms, and perturb one of them. Since realized rewards have finite support, there are only finitely many possible histories. Therefore, it suffices to focus on a fixed history h.


Consider an instance of MAB with 0-1 rewards. Assume that the prior  is independent across arms, and that (μ_1) is finite and does not include 0 or 1. Fix history h. Suppose random perturbation (<ref>) is applied to arm 1, with noise distribution _1 that satisfies (<ref>). Then
    [μ_1| h] ≠[μ_2| h]
almost surely.



Note that [μ_a| h] does not depend on the algorithm which produced this history. Therefore, for the sake of the analysis, we can assume w.l.o.g. that this history has been generated by a particular algorithm, as long as this algorithm can can produce this history with non-zero probability. Let us consider  the algorithm that deterministically chooses same actions as h.

Let S = (μ_1). Then:

    [μ_1| h]
           = ∑_ν∈ Sν·[μ_1 =ν| h]
        = ∑_ν∈ Sν·[h |μ_1 =ν] ·[μ_1=ν] / [h], 
    [h]
           = ∑_ν∈ S[h |μ_1 =ν] ·[μ_1=ν].

Therefore,
    [μ_1| h] = [μ_2| h]
if and only if

    ∑_ν∈ S (ν-C) ·[h |μ_1 =ν] ·[μ_1=ν] = 0,
       where    C=[μ_2| h].

Since [μ_2| h] and [h |μ_1 =ν] do not depend on the probability vector p⃗_1, we conclude that

    [μ_1| h] = [μ_2| h]
      ⇔   x·p⃗_1 =0,

where vector
    
    x := (  (ν-C) ·[h |μ_1 =ν]: ν∈ S ) ∈ [-1,1]^d_1

does not depend on p⃗_1.

Thus, it suffices to prove that x·p⃗_1 ≠ 0 almost surely under the perturbation. In a formula:

    _q∼_1[ x·( p⃗_1+q) ≠ 0 ] =1


Note that [h |μ_1 =ν]>0 for all ν∈ S, because 0,1∉S. It follows that at most one coordinate of x can be zero. So  (<ref>) follows from property (<ref>).








