Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality

Authors: antoine  scheid
aymeric  capitaine
etienne  boursier
eric  moulines
michael i jordan
alain  durmus
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:21:58

Abstract: In Economics, the concept of externality refers to any indirect effect resulting from an interaction between players and affecting a third party without compensation. Most of the models within which externality has been studied assume that agents have perfect knowledge of their environment and preferences. This is a major hindrance to the practical implementation of many proposed solutions. To adress this issue, we consider a two-players bandit game setting where the actions of one of the player affect the other one. Building upon this setup, we extend the Coase theorem [Coase, 2013], which suggests that the optimal approach for maximizing the social welfare in the presence of externality is to establish property rights, i.e., enabling transfers and bargaining between the players. Nonetheless, this fundamental result relies on the assumption that bargainers possess perfect knowledge of the underlying game. We first demonstrate that in the absence of property rights in the considered online scenario, the social welfare breaks down. We then provide a policy for the players, which allows them to learn a bargaining strategy which maximizes the total welfare, recovering the Coase theorem under uncertainty.

Main paper: 
 introduction: 
 The concept of externality is used in economics to capture phenomena that impact the global welfare stemming from economic interactions without any compensation [Buchanan and Stubblebine, 2006, Shah et al., 2018] . Externality is generally considered as market failure since they result in a loss of collective welfare. Given its practical importance [Dahlman, 1979 , Greenfield et al., 2009] , mechanisms that characterize and mitigate externalities are central to modern economic thinking.A first approach to tackle the adverse effects of externalities in modern economics was based on quotas and taxation [see, e.g., Pigou, 2017 , and the references therein]. However, Coase's theorem [Coase, 2013] shows that in the presence of well-defined property rights and low transaction costs, parties affected by externalities can privately negotiate efficient solutions, and recover a welfare efficient allocation through transfers and bargaining.Throughout the paper, we use the following simple example to illustrate our results. Example 1. Consider two firms 1 (upstream) and 2 (downstream) respectively producing quantities q 1 ⩾ 0 and q 2 ⩾ 0 of a good sold at a fixed price p > 0. They incur strictly increasing and convex costs, captured by the differentiable cost functions c 1 : q 1 → c 1 (q 1 ) and c 2 : q 2 → c 2 (q 2 ), satisfying c 1 (0) = 0 and c 2 (0) = 0. We assume that firm 1 exerts on firm 2 a constant externality α > 0 per unit produced. In other words, their profit functions (or utilities) are given by π 1 (q 1 ) = pq 1 -c 1 (q 1 ) and π 2 (q 1 , q 2 ) = pq 2 -c 2 (q 2 ) -αq 1 .One simple concrete illustration consists in an upstream firm emitting pollutants that reduce the downstream firm's production. If the upstream firm owns the property rights, it may receive a payment from the downstream one to reduce its output and thereby pollution. On the other hand, if the downstream firm owns the property right, it may require compensation from the upstream firm to allow its operation.The Coase theorem demonstrates that in both cases with appropriate property rights, the resulting levels of production would be welfare efficient. The theorem is typically explained in textbooks under the assumption that the players have perfect knowledge of their own utility or profit function, as well as that of others. However, this assumption is unlikely to hold in real-world scenarios, where players have to learn about their own preferences and those of their competitors. This example is, of course, a simplification of real world scenarios. For example, Abildtrup et al. [2012] consider a more complex setting to model the interaction between farmers and waterworks in Denmark where the farmers have the property rights whereas the waterworks can pay to reduce pollution. In particular, they demonstrate the failure of the theorem, attributing it to the breakdown of the main assumptions: no transaction costs, maximizing behaviors and perfect information, with an important focus on strategic behaviors and the asymmetry of information. We restore the latter in our work and provide foundations for the theorem to hold in more realistic scenarios.A key question is whether the Coase theorem holds when players learn their preferences over time.We investigate this question within the framework of a multi-armed bandit learning. We build upon recent works that extend the classical bandit setting to economics in which there are two players interacting via principal-agent protocols [Dogan et al., 2023b ,a, Scheid et al., 2024] . This allows us to capture, for example, a version of the two-firm problem where firms are uncertain regarding both their profit functions and the degree of externality on other firms. We represent production decisions in this problem as arms which can be played by the firms at any round over time, with the goal of finding decisions that maximize their rewards. More precisely, we assume that the reward of the upstream firm only depends on its own action, while the reward of the downstream firm depends on both its action and the upstream firm's action. This dependency on both actions allows us to capture externalities.The property rights in Example 1, or more generally over a bandit instance, amount to giving a firm the possibility of engaging in monetary transfers that influence the arms that are played over time. The owner of the bandit instance will face a problem of bandit learning with transfers with an upstream player who is also learning his preferences.To account for the efficiency of a policy in this setup, we extend the classical static notion of welfare efficiency to the online setting. We say that a policy is Welfare efficient if the social welfare regret is sub-linear. Proving the Coase theorem within our setup therefore boils down to show that if the bandit owner (who is without loss of generality the upstream player in this study1 ) runs a no-regret bandit algorithm to learn and exploit his preferences, the downstream player can then choose an optimal transfer scheme leading to a sub-linear total regret.Our contributions are as follows:• We show that when an upstream agent exerts externality on a downstream agent, in the absence of property right, the social welfare breaks down. Put differently, no joint policy of the agents can be welfare efficient. • We then introduce property rights and show how it affects the game. In this case, bargaining and transfers are available to the players. We propose a policy for the downstream player that leads to welfare efficiency when the upstream player follows any black-box no-regret policy under mild assumption. This solution addresses the breakdown issue at equilibrium. Put together, we show an online version of the Coase theorem.2 Setup and Inefficiency of Externality 
bandit game: 
 We consider a sequential bandit game in which two players (downstream and upstream) simultaneously play actions in a bandit instance for a horizon T ∈ N ⋆ . The action set for both players is A = {1, . . . , K}, K ∈ N ⋆ .The reward distributions of the agents differ. Given a family of distributions {γ a : a ∈ A} indexed by A, the upstream player's rewards are provided by an i.i.d. family of random variables {(Z a (t)) t∈[T ] : a ∈ A} , where Z a (t) ∼ γ a for any t ∈ [T ] and a ∈ A .To model the externality exerted by the upstream on the downstream player, we assume that the latter has a reward that depends both on her action and on that of the upstream player. Formally, this is modeled through a family of distributions {ν a,b : a, b ∈ A} double-indexed by A and an i.i.d. family of random variables{(X a,b (t)) t∈[T ] : a, b ∈ A} , where X a,b (t) ∼ ν a,bis the reward received by the downstream player at time t if she pulls the arm b and the upstream player pulls the arm a.Players. We assume that players are risk-neutral expected-utility maximizers, and we define their expected utilities for any Moreover, we suppose that players are rational in hindsight; that is, they minimize their regret. Formally, the upstream player aims to minimize his regret defined asEQUATIONwhile the downstream player seeks to minimize her external regret defined asEQUATIONwhere the players' actions(A t ) t∈[T ] , (B t ) t∈[T ]as well as their policies Π up n , Π down n are defined below. Note that the utility of the downstream player also depends on the actions taken by the upstream player, which represents the externality exerted by the upstream player on the downstream player, hence the strategic dimension of our setting. We first consider a game where no property right is defined, so each player is free to pick his preferred arm irrespectively of the other player's choice. This will result in a breakdown of the total utility.Policies without property rights. Consider first the upstream player. Based on a policy Π up n (for example a no-regret bandit algorithm such as the Upper Confidence Bounds algorithm (UCB) [Auer, 2002] or the ε-greedy algorithm [Robbins, 1952, Langford and Zhang, 2007] ), we define his history (H up,n t ) t∈[T ] by induction. We set H up,n 0 = ∅ and supposing that H up,n t is defined fort ∈ [T ], then H up,n t+1 = H up,n t ∪ A t+1 , V t+1 , Z At+1 (t + 1), where (V s ) s∈N ⋆ is a family of independent uniform random variables in [0, 1], allowing for randomization in the policy, and A t+1 is provided byΠ up n , following Π up n : (V t+1 , H up,n t ) → A t+1 .Second, consider the downstream player and an algorithm Π down n (specifically a no-regret bandit algorithm). We define her history (H down,n t ) t∈[T ] by induction. We set H down,n 0 = ∅ and supposing that H down,n t is defined for t ∈ [T ], thenH down,n t+1 = H down,n t ∪ A t+1 , B t+1 , U t+1 X At+1,Bt+1 (t + 1) ,where (U s ) s∈N ⋆ is a family of independent uniform random variables in [0, 1] allowing for randomization in the policy and B t+1 is provided byΠ down n , following Π down n : (U t+1 , H down,n t ) → B t+1 .Welfare efficiency. We now introduce the notion of Welfare efficiency for our setup. The global utility, or social welfare, of the players at round t is defined as v up (A t ) + v down (A t , B t ). We define the socially optimal action (a sw , b sw ) ∈ A × A of the game asEQUATIONas well as the global regret (or social welfare regret) associated with policies Π up n and Π down n asEQUATIONThen, the joint policies Π up n and Π down n for the players are said to be Welfare efficient iflim T →+∞ R sw (T, Π up n , Π down n )/T = 0 .Intuitively, this condition implies that the frequency of the socially optimal action (a sw , b sw ) tends to 1 as T goes to infinity. In this sense, it mimics the usual, static Welfare efficiency criterion. As we will see, (Π up n , Π down n) is typically not Welfare efficient when there is a disalignment in the game between the players' individual interests based on their rationality and the social welfare.We first present a result that captures the adverse consequence of externality on social welfare. The upstream player does not take into account the indirect cost incurred by the downstream player when he chooses his action. This drives the social welfare away from its optimal level. We illustrate this fact within our simple bilateral externality example. Example 1 (continuing from p. 1). We show that the competitive outcome, where each firm maximizes its profit independently, is not welfare efficient in the presence of externality. Define the social welfare as the function W : (q 1 , q 2 ) → π 1 (q 1 ) + π 2 (q 1 , q 2 ) = p(q 1 + q 2 ) -(c 1 (q 1 ) + c 2 (q 2 )) -αq 1 .(5)By definition, the welfare efficient outcomeEQUATIONNote that at the welfare efficient optimum, firm 1 does not equalize marginal cost with marginal profit, but produces less to account for the negative effect of externality on firm 2. We now characterize the competitive outcome (q ′ 1 , q ′ 2 ) ∈ R 2 + . Since π 1 and π 2 are differentiable and strictly concave,(q ′ 1 , q ′ 2 ) satisfies c ′ 1 (q ′ 1 ) = p and c ′ 2 (q ′ 2 ) = p .(7) For the competitive outcome to be welfare efficient, we require, by Equation (6) and Equation (7),c ′ 1 (q ′ 1 ) -α = c ′ 1 (q ′ 1 ), that is α = 0 . This proves that whenever there are externalities, no competitive outcome is efficient.We now show that in our model, when there is no property right and under mild assumptions, no achievable policy is welfare efficient whenever there is a misalignment between the players' interests and the social welfare. The upstream player's policyEQUATIONfor any b ∈ A. In the absence of property rights and when the upstream player runs any no-regret policy Π up n , we haveR sw (T, Π up n , Π down n ) = Ω(T ). Therefore, R sw (T, Π up n , Π down n ) = Ω(T ) and (Π up n , Π down n ) is not welfare efficient.Condition (8) in Theorem 2 represents the unalignment between the upstream player's preference and the optimal choice from a social welfare point of view. Note that the upstream and downstream players can both have an o(T ) external regret, while the social welfare regret still grows linearly with T because of the unfavorable interactions between their policies.3 Online Property Game with Bargaining Players 
online property game: 
 We now consider the same repeated game in the form of a property game where one of the players possesses the bandit instance (upstream player). As in the original setup of Coase [2013] , the other player (downstream player) will provide the bandit owner with transfers to incentivize him to choose some specific action and influence the outcome of the game in her favor.We show in Appendix B that our method applies similarly when property rights are given to the upstream player rather than the downstream player. Hence, there is no loss of generality in considering the aforementioned framework. In this sense, we recover the invariance property of the Coasean bargaining [Mas-Colell et al., 1995] .Example 1 (continuing from p. 1). We now illustrate how Coasean bargaining re-instaures efficiency. Suppose without loss of generality that property rights are such that firm 2 can pay τ ∈ R + to firm 1 for it to operate at a level q1 . Profits become π2 : (q 1 , q 2 , τ, q1 ) → π 2 (q 1 , q 2 ) -1 {q1=q1} τ and π1 : (q 1 , τ, q1 ) → π(q 1 ) + 1 {q1=q1} τ.Consider the competitive outcome (q 1 , q 2 , τ, q1 ) ∈ R 4 + which satisfiesq 1 = q 1 (τ, q1 ) ∈ arg max q ′ 1 ⩾0 π1 (q ′ 1 , τ, q1 ) and π2 (q 1 (τ, q1 ), q 2 , τ, q1 ) = max q ′ 2 ,τ ′ ,q ′ 1 π2 (q 1 (τ ′ , q′ 1 ), q ′ 2 , τ ′ , q′ 1 ).The condition on q 1 accounts for the rationality of the firm 1 and the fact that its choice depends on the payment (τ, q1 ). Obviously, the optimal solution is reached for q1 = q 1 and τ = max q ′ π 1 (q ′ )π 1 (q 1 ). Plugging this back in the expression of π2 then yields(q 1 , q 2 ) = argmax q ′ 1 ,q ′ 2 π 1 (q ′ 1 ) + π 2 (q ′ 2 ) = argmax q ′ 1 ,q ′ 2 W (q ′ 1 , q ′ 2 ) ,so the competitive outcome (q 1 , q 2 ) is welfare efficient.The transfers at each step can be interpreted as a contract between two players [see, e.g., Bolton and Dewatripont, 2004, Salanié, 2005 , for general contract theory] and providing the right amount of incentives relates to adjusting a contract in an online setting [see Dütting et al., 2019 , Guruganesh et al., 2021 , Zhu et al., 2022 , Fallah and Jordan, 2023 , Guruganesh et al., 2024 , Ananthakrishnan et al., 2024 , for learning-based perspectives about contracts].Similarly to Example 1, we modify the players' policies to now account for the transfer τ (t) that the downstream player offers at round t to the upstream player if he picks action ãt . The downstream player's policy at round t does not only output an arm B t but now a triple (ã t , τ (t), B t ), where B t is the arm that she should play and ãt is the arm on which a transfer τ (t) is offered to the upstream player. On the upstream player's side, the policy still outputs an arm A t to play but also takes as an input the incentive (ã t , τ (t)). In addition, the instantaneous utility of the upstream player becomes Z At (t) + 1 ãt (A t )τ (t), whereas the downstream player receives X At,Bt (t) -1 ãt (A t )τ (t).Policies with property rights. Based on policies Π up p for the upstream player and Π down p for the downstream player, we define their histories (H Players' goal. Given a transfer τ from the downstream to the upstream player on arm ã, actions a and b respectively are chosen by the upstream and the downstream player, the upstream player's expected utility reads v up (a) + 1 ã(a)τ while the downstream player's expected utility is v down (a, b) -1 ã(a)τ . This defines the upstream player's expected regret for a horizon T asR up p (T, Π up p , Π down p ) = E T t=1 max a∈A {v up (a) + 1 ãt (a)τ (t)} -(v up (A t ) + 1 ãt (A t )τ (t)) . (9)Based on the upstream player's utility, the downstream player aims on a single round at proposing an optimal transfer τ opt on an arm a opt ∈ A as well as picking an arm b opt ∈ A which solves maximize (a, b, τEQUATION)Her regret for any horizon T is defined asEQUATIONwhere we define µ ⋆,down = v down (a opt , b opt ) -τ opt as the optimal utility she can aim for. We can see that the downstream player's influence is exerted through her action choice B t as well as through transfers which enable her to influence the upstream player's actions. Hence, the notion of external regret is obsolete here. The game has now the form of a repeated Stackelberg game [Von Stackelberg, 2010] . Lemma 1. Recall that µ ⋆,down is the downstream player's optimal reward as defined as a solution of (10). We have µ ⋆,down = max a,b∈A {v down (a, b) + v up (a)} -max a ′ ∈A {v up (a ′ )}, as well as (a opt , b opt ) = (a sw , b sw ) and µ ⋆,up +µ ⋆,down = v up (a sw )+v down (a sw , b sw ) = max a,b∈A {v up (a)+ v down (a, b)}, where µ ) .This lemma has an interesting economic interpretation: if both players individually seek for their own interest within this online property game, they will together converge towards the optimal global utility. Individual rationality moves the outcome of the game towards the optimal social welfare. The transfers allow the players to align their goals and share the global reward, in line with the Coase theorem. Consequently, if both players run no-regret policies Π up p and Π down p , the social welfare regret will also be in o(T ). The rest of the paper shows that such no-regret policies exist. To this end, we introduce the following assumptions.Without loss of generality, we assume that the upstream player's utility is rescaled and shifted, which corresponds to the following assumption on the reward distribution (γ a ) a∈A in R. H1. For any a ∈ A, we have v up (a) ∈ [0, 1].We now make a high probability bound assumption on the upstream player's regret.2 . H2. There exist C, ζ > 0, κ ∈ [0, 1) such that for any s, t ∈ [T ] with s+t ⩽ T , any {τ a } a∈[K] ∈ R K + and any policy Π down p that offers almost surely a transfer (ã l , τ (l)) = (ã l , τ ãl ) for any l ∈ {s + 1, . . . , s + t}, the batched regret of the upstream player following Π up p satisfies, with probability at least1 -t -ζ , s+t l=s+1 max a∈A {v up (a) + 1 ãl (a)τ ãl } -(v up (A l ) + 1 ãl (A l )τ ãl ) ⩽ Ct κ .The constraint on the downstream player's algorithm Π down p enforces constant incentives associated with any arm a ∈ A withtin the batch, while the incentivized actions (ã l ) l∈{s+1,...,s+t} may change. Proposition 2 in Appendix C shows that an adaptation of UCB taking account the incentives satisfies H2 with C = 8 K log(KT 3 ), κ = 1/2 and ζ = 2. Note that usual bandit algorithms such as AAE, ETC or EXP-IX also satisfy the assumption [see, e.g., Donahue et al., 2024, Lattimore and Szepesvári, 2020] .We fix the policy Π up p which can be any algorithm satisfying H2 for the upstream player and introduce the algorithm BELGIC (Bandits and Externalities for a Learning Game with Incentivized Coase) which provides a policy achieving sub-linear regret for the downstream player. It can be seen as an online bargaining strategy to mitigate externalities. Simply put, BELGIC unfolds in two steps. First note that for any action a ∈ A, the optimal (lowest) transfer to offer to the upstream player to make him choose a isEQUATIONas detailed in Appendix A. Therefore, a batched binary search procedure (Algorithm 2) first allows the downstream player to estimate the optimal transfers τ ⋆ 1 , . . . , τ ⋆ K with a good precision level of 1/T β , where β > 0. More precisely, the downstream player offers a constant incentive (ã, τ ã) for a batch of time steps of length T = ⌈T α ⌉. The observation of T ̸ = ã , the number of steps from the batch for which the upstream player does not pick ã allows her to estimate whether τ ã is above or below τ ⋆ ã and adjust it, following Lemma 2 in Appendix A under the condition that α, β satisfyEQUATIONThe procedure needs to be run for K⌈T α ⌉⌈log 2 T β ⌉ rounds since we have to make ⌈log 2 T β ⌉ batches of binary search of length ⌈T α ⌉ on each of the K arms [see Scheid et al., 2024] . This corresponds to the first phase of BELGIC as described in Algorithm 2. At the end of this stage, the estimated transfers (τ a ) a∈A satisfy the bound in Proposition 1. These are then used to feed the subroutine Bandit-Alg.Proposition 1. Under H1 and H2, after the first phase of BELGIC which consists in K⌈T α ⌉⌈log T β ⌉ steps of binary search grouped in ⌈log 2 T β ⌉ batches per arm a ∈ A, we have thatP for any a ∈ A, τa -4/T β -CT (κ-1)/2 ⩽ τ ⋆ a ⩽ τa ⩾ 1 -K⌈log 2 T β ⌉/T αζ .The additional term 1/T β + CT κ-1 in τa ensures that if H2 holds, the upstream player necessarily plays the incentivized action ãt at round t with high probability. Lemmas 2 and 6 from Appendix C show how the binary search batches in BELGIC allow us to estimate τ ⋆ a depending on T -T ̸ = a , the number of times that arm a has been pulled by the upstream player during the batch.Then, any bandit subroutine Bandit-Alg, such as UCB or ε-greedy, for instance, can be run in a black-box fashion on the shifted bandit instance, where the rewards are shifted by the upper estimated transfers (τ a ) a∈A . The downstream player computes a shifted history Hdown,p t such that for anyEQUATIONwhich serves to feed Bandit-Alg, followingEQUATION)For any family of constant incentives {τ a } a∈A ∈ R K + , we define R Bandit-Alg (T, ν, {τ a } a∈A ) as the regret for the downstream player's subroutine Bandit-Alg on the bandit instance with shifted means over T rounds, followingR Bandit-Alg (T, ν, {τ a } a∈A ) = T max a,b∈A 2 E v down a,b (1) -τ a -E T t=1 v down (ã t , B t ) -τ ãt .Note that here, Bandit-Alg aims to maximize the shifted reward(v down (a, b) -τ a ) (a,b)∈A 2 . Algorithm 1 BELGIC 1: Input: Set of actions A = [K], time horizon T , subroutine Π up p , upstream player's regret constants C, κ, parameters α and β. 2: Compute Hdown,p s = ∅ for any s ⩽ K⌈log 2 T β ⌉⌈T α ⌉. 3: for a ∈ A do 4: # See Algorithm 2 5:τ a , τ a = Binary Search(a, ⌈log 2 T β ⌉, ⌈T α ⌉, 0, 1) 6: end for 7: For any action a ∈ A, τa = τ a + 1/T β + CT (κ-1)/2 . 8: for t = K⌈T α ⌉⌈log 2 T β ⌉ + 1, . . . , T do 9:Get recommended actions by Bandit-Alg on the A × A bandit instance, (ã t , B t ) = Bandit-Alg(U t , Hdown,p t-1).Offer a transfer τãt on action ãt , nothing for any other action a ′ ∈ A and play action B t . 11: Observe A t = Π up p (ã t+1 , τ (t + 1), V t , H up,p t-1 ), X ãt,Bt (t) 12: if A t =1: Input: action a, N T , T , τ a , τ a . 2: for d = 0, . . . , N T -1 do 3: Compute τ mid a = (τ a (d) + τ a (d))/2, T ̸ = a = 0.4:for t = d T + 1, . . . , d T + T do 5:Propose transfer τ mid a (d) on arm a and nothing for any other action a ′ ∈ A.6:A t = Π up p (t, τ mid (a), a, V t , H up,p t-1 ) 7: if A t ̸ = a then: T ̸ = + = 1 8: end if 9:Update upstream player's history H up,p t . 10:end for11: if C T κ+β/α < T ̸ = a < T -C T κ+β/α then Return τ a (d), τ a (d).12: end if 15: end for Theorem 3. Assume that H1 and H2 hold. Then BELGIC, run with α, β satisfying (13) and any bandit subroutine Bandit-Alg, has an overall regret R down p such thatelse if T ̸ = a ⩽ T -C T κ+β/α then τ a (d) = τ midR down p (T, Π up p , BELGIC) ⩽ 2(3 + 2C + v -v) log 2 (T )(2T 1-αζ + T (κ+1)/2 + ⌈T α ⌉) + 4T 1-β + R Bandit-Alg (T, ν, {τ a } a∈A )where, for ease of notationv = max a,b∈A×A {v down (a, b)} and v = min a,b∈A×A {v down (a, b)} .Knowledge of C and κ. An upper bound on C and κ is sufficient to compute the hyperparameters in BELGIC. Theorem 3 shows that the bigger C and κ are, the worse is the downstream player's regret, hence the interest of knowing them more precisely.Corollary 1. Assume that the upstream player's distribution (γ a ) a∈A is such that H 1 holds. In addition, suppose that the distributions (γ a ) a∈A and (ν a,b ) a,b∈A×A are 1-sub-Gaussian and that the upstream player plays Π up p = Algorithm 3 (a slight modification of UCB to take into account the incentives). Then the downstream player's regret when she runs BELGIC with parameters α = 3/4 and β = 1/4 (which satisfy (13)) and subroutine Bandit-Alg = UCB satisfies the following upper bound3 R down p (T, UCB, BELGIC) ⩽ (10 + 4K + 32 K log 2 (KT 3 ) + v -v) log 2 (T )(3 + 2T 3/4 ) + 3K 2 (v -v) .The upper bound on the social welfare regret in Lemma 1 together with Corollary 1 shows that when the upstream player runs Π up p = UCB and the downstream player runs BELGIC, the social welfare regret then satisfies R sw (T, Π up p , BELGIC) = O(K log(T )T (κ+1)/2 ). In other words, if the downstream player runs BELGIC which produces a policy Π n down , for any upstream policy Π up p , (Π n down , Π up p ) is welfare efficient. Influence of the upstream performance. It is interesting to note that in the downstream player's regret bound, the upstream player's regret bound in O(T κ ) plays a significant role: the downstream player never learns faster than the upstream player. The latter's performance determines the social welfare convergence rate towards the social optimum. We can observe that the players' bounded rationality [Selten, 1990 , Jones, 1999] and personal interest make the game converge towards the optimal social welfare equilibrium-even though they are both learning here. Experiments. We conclude this section with experiments showing the empirical convergence of our algorithm to a social optimum. In the simulation, we consider two firms, with firm 1 being upstream and firm 2 being downstream. Their profit functions are respectively given byEQUATIONπ 2 (q 1 , q 2 ) → max -16 q 1 10 - 6 10 2 + 8 q 1 - 6 10 2 + 1 50 q 2 , 0 .Thus, firm 1's and firm 2's profit functions depends quadratically on q 1 with an firm 1 optimum at q ′ 1 = 5 and a social optimum at q ⋆ 1 = 8. Note that in the expression of π 2 , q 2 has very little influence as compared to q 1 -which allows to plot profits for only one value of q 2 . We discretize the setup, consider a bandit instance (horizon T = 5.10 6 , 10 arms, average over 10 rounds) and we assume that UCB is used as a subroutine. In the first setting, there are no property rights and each firm runs UCB on their side. Second, property rights are defined and firm 2 runs BELGIC as its policy. The plots in Figure 1 display the empirical frequencies and show empirically the effectiveness of BELGIC to mitigate externalities.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: Our work presents a lot of theorems supported by assumptions (see H2, Theorems 2 and 3...). All of Appendix C is here to provide a theoretical support to these results.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
related work: 
 Our work addresses the impact of externalities and is therefore related to taxation theory [see, e.g., Mirrlees et al., 2011 , Salanie, 2011 , and the references therein], a prominent solution for this issue, as exemplified by the Pigouvian tax [see Pigou, 2017] . Taxation is a fundamental aspect of all developed economies, with 30% to 50% of national income derived from taxes. The topic has been fruitful for various scenarios, including the carbon tax [Carattini et al., 2018, Metcalf and Weisbach, 2009] , alcohol markets [Griffith et al., 2019] , or business taxation [Boadway and Bruce, 1984] . Taxation can also be studied through an operations research lens, where it is used to enhance system efficiency or manage specific games [Roughgarden, 2010 , Caragiannis et al., 2010 , Bilò and Vinci, 2019] . Recent work by Cui et al. [2024] explores online mechanisms to maximize efficiency in congestion games.Mechanism designs [Myerson, 1989 , Nisan and Ronen, 1999 , Laffont and Martimort, 2009] allow to design games that have specific desired outcomes. Deploying these mechanisms in their classical ecnomical form assume that players' utility functions are known a priori, which is often unrealistic. There is a major need to blend mechanism design with machine learning. However, our approach differs, since, drawing inspiration from Coase's theory, we implement an online version of his theorem [Coase, 2013 , Cooter, 1982] , incorporating uncertainty to tackle the breakdown of social welfare in an online setting. We use the bandit setup [see Lattimore and Szepesvári, 2020, Slivkins et al., 2019] as a general and convenient way to model the game introduced by Coase. However, our work differs from considering a single agent playing a bandit game. Instead, we focus on the more general problem of multi-players bandits, a field receiving a growing attention from the community [see e.g., Boursier and Perchet, 2019 , 2022 , Sankararaman et al., 2019] .Our approach is inspired by the principal-agent model introduced by Dogan et al. [2023b] , which was further extended by Dogan et al. [2023a] , Scheid et al. [2024] . However, unlike the models proposed in the work of Dogan et al. [2023b,a] , we do not specify a particular bandit algorithm for the upstream player and instead, we allow him to use any no-regret algorithm satisfying H2 in a black-box fashion. Conversely, the model of Scheid et al. [2024] assumes that the upstream player is always fully informed and best-responding, whereas we assume that he is also learning. Chen et al. [2023b] leverages a similar model to study information acquisition by a principal through an agent's actions. However, in their model, the agent is also almighty and knows exactly the costs associated with each action. Designing incentives in an unknown environment is related to auction theory incorporating uncertainty, as it is explored in the work of Feng et Donahue et al. [2024] also study a two-players repeated Stackelberg game on a bandit instance but instead of allowing for transfers, their main focus concerns the achievability of a Stackelberg equilibrium through iterations of bandit policies: the same kind of goal also appears in Collina et al. [2023] . Such principal-agent setups are of some interest to model various real-world situations such as the design of fundings for hospitals [Wang et al., 2024] or have been studied with multiple agents through the lens of auction design in dynamic setups [Bergemann and Said, 2010, Chen et al., 2023c] , or to account for fairness [Fallah et al., 2024] .In our game, the downstream player needs to learn the optimal transfers/incentives to offer to the upstream player. This is related to the Incentivized Exploration literature [Mansour et al., 2016 , Simchowitz and Slivkins, 2023 , Esmaeili et al., 2023] , which is often cast in terms of a benevolent planner who aims to optimize the global welfare of agents via plausible recommendations. A related model is Bayesian Persuasion [Kamenica and Gentzkow, 2011] , where a sender influences a receiver's action through sending a signal. This model has begun to be studied in learning settings [see, e.g., Castiglioni et al., 2020 , Bernasconi et al., 2022 , Wu et al., 2022b,a] .Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: Since our work is mostly a theoretic contribution, we do not present experiments. Therefore, our paper is not concerned by this issue. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
conclusion: 
 This paper studies a model of externalities in a two-players sequential game where both players learn their optimal actions. We first show that when the players act independently, then a misalignment between the players' interests and the social welfare leads to a breakdown of the global utility. We then introduce interactions through transfers, which restores a social welfare optimum, representing the online version of the Coase theorem. To that purpose, we propose a policy for the downstream player which allows her to estimate the optimal transfers as well as choosing the best actions. The mathematical difficulty comes from the learning aspect on both sides. Since our work is coined in a learning framework for mechanism design, several directions for research are open, as for instance extensions to the multi-agent setting, which raises many questions.A Algorithmic Subroutine for the Binary Search Optimal Transfer. For any given round t ⩾ 1, action a ∈ A and ε > 0, the downstream player can incentivize any best-responding upstream player to choose a by offering a transfer, τ ⋆,ε a ∈ R + , defined as:τ ⋆,ε a = max a ′ ∈A v up (a ′ ) -v up (a) + ε .With this transfer, it holds that for any a ′ ∈ A, a ′ ̸ = a, we have v up (a ′ ) < v up (a) + τ ⋆,ε a , ensuring the upstream player's action A t = a, since action a yields a superior reward. Consequently,τ ⋆ a = lim ε→0 τ ⋆,ε a = max a ′ ∈A v up (a ′ ) -v up (a)represents the infimal transfer necessary to make arm a the best upstream player's choice.First step of BELGIC: estimation of the optimal transfers. Suppose that we consider an arm a ∈ A and that the downstream player offers an incentive τ a to the upstream player if he picks this arm. We consider this procedure with a constant incentive τ a for a batch of time steps of length T = ⌈T α ⌉ due to the fact that the upstream player is learning [see Perchet et al., 2016 , for batched bandits in the usual multi-armed setting]. Lemma 2 shows that for BELGIC to accurately estimate τ ⋆ a with high probability, it must holdEQUATION)This is why we impose the condition (13) on α and β, namely β/α < 1 -κ, which ensures that κ(α -1) + β < 0 and therefore lim T →+∞ T κ(α-1)+β = 0. More precisely, we define for a ∈[K] Λ a = (a -1)⌈log 2 T β ⌉ T ,which is the step after which starts the binary search procedure on arm a. For any d ∈ {1, . . . , ⌈log 2 T β ⌉} on arm a, we defineEQUATIONas the step after which starts the d-th batch iteration on arm a, and we considerEQUATIONwhere (A t ) t∈{1,...,K⌈log 2 T β ⌉ T } is given by Algorithm 2. Lemma 2 shows that for any a ∈ A, d ∈ {1, . . . , ⌈log 2 T β ⌉}, with high probabilityEQUATIONwhere τa,d is the current estimate of τ ⋆ a offered for iteration k a,d . In case (18) does not hold, it means that the upstream player has misplayed and has chosen most of the steps a suboptimal action, leading to an instantaneous regret for him larger than the bound given in H2. This is why (19) holds with high probability. To sum up, the first phase of BELGIC consists in ⌈log 2 T β ⌉ batches of binary search on each arm a ∈ A to obtain a precision level 1/T β on the optimal transfer τ ⋆ a . During this phase in Algorithm 2, we define τ a (d) ∈ R + as the upper estimate and τ a (d) ∈ R + as the lower estimate of τ ⋆ a after d ∈ {1, . . . , ⌈log 2 T β ⌉} rounds of binary search on arm a. For any t ∈ [T ] and a ∈ A, we define τ mid After this first binary search phase, the downstream player computes estimates of the optimal transfers τ ⋆ a (τ a ) a∈A = (τ a (⌈log 2 T β ⌉) + 1/T β + CT (κ-1)/2 ) a∈A , and offers these transfers (τ ⋆ a ) a∈A to make the upstream player play any action ã ∈ A she wants. Second Step. After the first phase during which the optimal incentives are estimated by the downstream player through (τ a ) a∈A , she runs in the second phase the subroutine Bandit-Alg on the A×A bandit instance driven by her action B t and the upstream player's one A t . More precisely, any bandit subroutine Bandit-Alg, such as UCB or ε-greedy, for instance, can be run in a black-box fashion on the shifted bandit instance, where rewards are shifted by the upper estimated transfers (τ a ) a∈A . The downstream player computes a shifted history Hdown,p t = ∅ for any t ⩽ K⌈T α ⌉⌈log 2 T β ⌉ and for any t > K⌈T α ⌉⌈log 2 T β ⌉ Hdown,pa (t) = (τ a (t) + τ a (t))/2. τ a (d), τ a (d), τ midt = {ã t , B t , τ (t), U t , X ãt,Bt (t) -τãt } ∪ Hdown,p t-1 if ãt = A t Hdown,p t-1 otherwise .which serves to feed Bandit-Alg, following Bandit-Alg : (U t , Hdown,pt-1 ) → (ã t , B t ) ∈ A × A.Note that here, Bandit-Alg aims to maximize the shifted reward(ν down (a, b) -τa ) (a,b)∈A 2 .Based on this decision by Bandit-Alg, Π down p offers the incentive τãt associated with action ãt and plays action B t . Lemma 5 ensures that ãt is the upstream player's best choice. Therefore, H2 ensures that the upstream player will not deviate from the downstream player's recommendation with high probability.B Invariance when the property rights are given to the downstream player Our focus in the paper was the case where the upstream player possesses the bandit instance and receives monetary payments. We argue here that the symmetric situation, i.e. when the property rights are given to the downstream player, can be analysed in the exact same way.Assume that the the downstream player owns the bandit instance. This implies that (i) they can prescribe what arm the upstream player has to play at each round, and (ii) the upstream player may perform a monetary transfer to influence the arm they are allowed to pull.Consider the same bandit setup as before. Formally, the downstream player's action is (A t , B t ) ∈ A × A where A t is the arm that the upstream player is prescribed to pull (he cannot deviate since the downstream player has the property rights), while B t is the arm played by the downstream player. On the other hand, the upstream player's policy outputs at each round the action (ã t , τ (t)) ∈ A × R + , where ãt is the arm they choose to incentivize and τ (t) is the amount of transfer. It means that the downstream player receives a transfer τ (t) if she prescribes action A t = ãt . As a consequence, the instantaneous utility of the upstream player is Z At -1 ãt (A t )τ (t), while the downstream player receives X At,Bt + 1 ãt (A t )τ (t). In that case, the upstream player may perform a binary search on each arm ā ∈ A to identify the optimal incentive τ ⋆ ā , by considering Card {t ∈ [T ] such that ãt = ā} during batches designed for the binary search and then play on the shifted bandit instance as we explained. This situation and the upstream player's strategy are now equivalent to the one presented before.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: Since our work is mostly a theoretic contribution, we do not present experiments. Therefore, our paper is not concerned by this issue (same answer as for item 5). Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: Since our work is mostly a theoretic contribution, we do not present experiments. Therefore, our paper is not concerned by this issue (same answer as for item 5). Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: Since our work is mostly a theoretic contribution, we do not present experiments. Therefore, our paper is not concerned by this issue (same answer as for item 5). Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: As explained in the Related Works, an issue with externalities is the harm caused to all the parties involved in the considered setting. Here, we try to provide a setup so the players can negociate and achieve a social welfare optimal equilibrium. Therefore, we are confident in the fact that we follow the NeurIPS Code of Ethics. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We consider an issue arising in several real-world situations and provide an algorithmic solution to it. We realize that this theoretical contribution still needs some work to be implemented but we hope that it will contribute to positive social impacts in the future. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Recall that we defined the shifted history Hdown,p t that will serve to feed Π down p at time t as Hdown,pt = (ã s , τ (s), A s , V s , Z As (s)) s⩽t .Theorem 4. Suppose that argmax a∈A v up (a) is the singleton {a u ⋆ } and thatv up (a sw ) + v down (a sw , b sw ) -v up (a u ⋆ ) + v down (a u ⋆ , b) > 0 , for any b ∈ A.In the absence of property rights and when the upstream player runs any noregret policy Π up n , we haveR sw (T, Π up n , Π down n ) ⩾ T ∆ sw -R up n (T, Π up n )∆ sw /∆ up , where ∆ up = min a ′ ∈A\{a u ⋆ } v up (a u ⋆ ) -v up (a ′ ) and ∆ sw = v up (a sw ) + v down (a sw , b sw ) -max b∈A (v up (a u ⋆ ) + v down (a u ⋆ , b)). Therefore, R sw (T, Π up n , Π down n ) = Ω(T ) and (Π up n , Π down n ) is not welfare efficient.Proof of Theorem 4. Since argmax a∈A v up (a) is the singleton {a up ⋆ }, we define ∆ up = min a ′ ∈A\{a u ⋆ } v up (a u ⋆ ) -v up (a ′ ) as the upstream player reward gap and∆ sw = v up (a sw ) + v down (a sw , b sw ) -max b∈A (v up (a u ⋆ ) + v down (a u ⋆ , b)) as the social welfare reward gap if the upstream player plays his most preferred action.Denote N up ⋆ (T ) the number of pulls of the upstream player up to time T on the arm a u ⋆ . By definition of ∆ up , we have that for any step t ∈[T ] such that A t ̸ = a up ⋆ , max a∈A {v up (a)} -v up (A t ) = v up (a up ⋆ ) -v up (A t ) ⩾ min a ′ ∈A\{a u ⋆ } v up (a u ⋆ ) -v up (a ′ ) = ∆ up . There are T -N up ⋆ (T ) such steps, which leads to R up n (T, Π up n , Π down p ) ⩾ E T t=1 max a∈A {v up (a)} -v up (A t ) ⩾ (T -E[N u ⋆ (T )])∆ up , and we obtainE[N u ⋆ (T )] ⩾ T -R up n (T, Π up n )/∆ up .Moreover, for any t ∈ [T ] such that A t = a up ⋆ and anyB t ∈ A, v up (a sw ) + v down (a sw , b sw ) - (v up (A t ) + v down (A t , B t )) = v up (a sw ) + v down (a sw , b sw ) -(v up (a up ⋆ ) + v down (a up , B t )) ⩾ ∆ sw by definition, which leads to R sw (T, Π up n , Π down n ) ⩾ E[N u ⋆ (T )]∆ sw , and we obtainR sw (T, Π up n , Π down n ) ⩾ T ∆ sw -R up n (T, Π up n )∆ sw /∆ up . Since lim T →+∞ R up n (T, Π up n )/T = 0, we have lim T →+∞ R sw (T, Π up n , Π down n )/T = ∆ sw > 0, hence the result.The proof of Theorem 2 is an immediate consequence of Theorem 4. Lemma 1. Recall that µ ⋆,down is the downstream player's optimal reward as defined as a solution of (10). We have µ ⋆,down = max a,b∈A {v down (a, b) ) .+ v up (a)} -max a ′ ∈A {v up (a ′ )}, as well as (a opt , b opt ) = (a sw , b sw ) and µ ⋆,up +µ ⋆,down = v up (a sw )+v down (a sw , b sw ) = max a,b∈A {v up (a)+ v down (a, b)}, where µ ⋆,upProof of Lemma 1. Recall that µ ⋆,down is defined as µ ⋆,down = sup a,b∈A 2 ,τ ∈R+ {v down (a, b)τ } , such that a ∈ argmax a ′ ∈A {v up (a ′ ) + 1 a (a ′ )τ } and a up ⋆ = argmax a ′ ∈A v up (a). Note that we can writeµ ⋆,down = max{sup a,b∈A 2 ,τ ∈R+ 1 Ã(a, τ )(v down (a, b) -τ ), max b∈A v down (a up ⋆ , b)} ,where Ã = {(a, τ ) : v up (a) + τ ⩾ max a ′ v up (a ′ ) + 1 a (a ′ )τ } which is the set of pairs (a, τ ) ∈ A × R + such that the constraint binds. However, we also have by definition that v up (a up ⋆ ) + 0 ⩾ max a ′ ∈A v up (a ′ ) + 1 a up ⋆ (a ′ ) • 0 and hence, (a up ⋆ , 0) ∈ Ã. Therefore, since v down (a up ⋆ , b) ⩾ 0 for any b ∈ A, we can writeµ ⋆,down = sup (a,τ )∈ Ã,b∈A {v down (a, b) -τ } . First note that if (a, τ ) ∈ Ã, then for any a ′ ∈ A, τ ∈ R + , v up (a) + τ ⩾ v up (a ′ ) + 1 a (a ′ )τ , which gives v up (a) -v up (a ′ ) ⩾ (1 a (a ′ ) -1)τ .However, either a = a ′ and hence v up (a) -v up (a ′ ) = 0, either a ̸ = a ′ and hence 1 a (a ′ ) = 0. Therefore, we have thatv up (a) -v up (a ′ ) ⩾ -τ ,which implies by definition of the optimal incentives that τ ⩾ v up (a ′ ) -v up (a) for any a ′ ∈ A, and hence τ ⋆ a ⩽ τ for any (a, τ ) ∈ Ã. In addition, (a, τ ⋆ a ) ∈ Ã by definition. Consequently,µ ⋆,down = max a,b∈A 2 {v down (a, b) -τ ⋆ a } = max a,b∈A {v down (a, b) -max a ′ ∈A {v up (a ′ )} + v up (a)} ,hence the first part of the result. Since µ ⋆,up is defined as µ ⋆,up = max a∈A v up (a), we have thatµ ⋆,down + µ ⋆,up = max a,b∈A {v down (a, b) -max a ′ ∈A {v up (a ′ )} + v up (a)} + max a∈A v up (a) = max a,b∈A {v down (a, b) + v up (a)} = v up (a sw ) + v down (a sw , b sw ) .Now summing R down p and R up p as defined in ( 9) and ( 11), we obtainR up p (T, Π up p , Π down p ) + R down p (T, Π up p , Π down p ) = E T t=1 max a∈A {v up (a) + 1 ãt (a)τ (t)} -(v up (A t ) + 1 ãt (A t )τ (t)) + T max a,b∈A 2 {v down (a, b) -max a ′ ∈A {v up (a ′ )} + v up (a)} -E T t=1 v down (A t , B t ) -1 ãt (A t )τ (t) ⩾ T max a∈A {v up (a)} -E T t=1 v up (A t ) + 1 ãt (A t )τ (t) -E T t=1 v down (A t , B t ) -1 ãt (A t )τ (t) + T max a,b∈A 2 {v down (a, b) + v up (a)} -T max a ′ ∈A {v up (a ′ )} = T max a,b∈A 2 {v up (a) + v down (a, b)} -E T t=1 v up (A t ) + v down (A t , B t ) = R sw (T, Π up p , Π down p ) ,hence the result. Recall the assumption that we use on the upstream player's regret for a policy Π up p . We show here that it is satisfied by typical no-regret bandit algorithms. H2. There exist C, ζ > 0, κ ∈ [0, 1) such that for any s, t ∈ [T ] with s+t ⩽ T , any {τ a } a∈[K] ∈ R K + and any policy Π down p that offers almost surely a transfer (ã l , τ (l)) = (ã l , τ ãl ) for any l ∈ {s + 1, . . . , s + t}, the batched regret of the upstream player following Π up p satisfies, with probability at least1 -t -ζ , s+t l=s+1 max a∈A {v up (a) + 1 ãl (a)τ ãl } -(v up (A l ) + 1 ãl (A l )τ ãl ) ⩽ Ct κ .We present the upstream player's UCB subroutine. Proposition 2. Let s, t ∈ [T ] such that s + t ⩽ T . Suppose that there exists a family (τ a ) a∈A of constant incentives associated with each arm a ∈ A such that we have in Algorithm 3: (ã l , τ (l)) s+l∈{s+1,...,s+t} = (ã l , τ ãl ) l∈{s+1,...,s+t} as an output of Π down p . Suppose that the distributions γ a are 1-sub-Gaussian. Then with probability at least 1 -T -2 , the regret of the version of UCB given in Algorithm 3 run by the upstream player satisfies Note that the major difference between this assumption and the regret bounds that we generally consider in multi-armed bandit problems is that we consider the regret without expectation here.Algorithm 3 Upstream player's UCB 1: Input: Set of arms K, horizon T . 2: Initialize: For any arm a ∈ [K], set μa = 0, T a = 0.3: for 1 ⩽ t ⩽ K: do 4:Pull arm A t = t 5:Update μAt = X At (t), T At (t) = 1 6: end for 7: for t ⩾ K + 1 do 8:Observe the incentive (ã t , τ (t)).Pull arm A t ∈ argmax a∈[K] μa (t -1) + 2 log(KT 3 ) Ta(t-1) + 1 ãt (a)τ (t)10: Update T At (t) = T At (t -1) + 1, μAt (t) = 1 T A t (t) (T At (t -1)μ At (t -1) + X At (t)) 11: end forProof of Proposition 2. The proof is adapted from the proof of Bubeck et al. [2012, Theorem 2.1] . Let s, t ∈ [T ] such that s + t ⩽ T . For any integer l ∈ {s + 1, . . . , s + t}, we write n l (a) = Card {l ′ ∈ [l] such that A l ′ = a} for the number of pulls of arm a and μa (l) for the empirical mean utility of the arm a ∈ A estimated on the batch {1, . . . , l}: μa (l) = n l (a) -1 l k=1 1 a (A k )X a (k). Since the rewards on the incentivized bandit instance are 1-sub-Gaussian, a Hoeffding bound gives that for any δ ∈ (0, 1), a ∈ A, l ∈ {s + 1, . . . , s + t}, and any family of arms (a l ′ ) l ′ ∈{1,...,l} such that Card {j : a j = a} = k, we have thatP |μ a (l) -v up (a)| ⩾ 2 log(2/δ)/k (A l ′ ) l ′ ∈{1,...,s+l} = (a l ′ ) l ′ ∈{1,...,s+l} ⩽ δ .Therefore, for any δ ∈ (0, 1), a ∈ A, l ∈ {s + 1, . . . , s + t}, we have the following boundP |μ a (l) -v up (a)| ⩾ 2 log(2/δ)/n l (a) = P      l k=1 (a l ′ ) l ′ s.t. Card{l ′ ∈{1,...,l} : a l ′ =a}=k {|μ a (l) -v up (a)| ⩾ 2 log(2/δ)/k}      ⩽ l k=1 P      (a l ′ ) l ′ s.t. Card{l ′ ∈{1,...,l} : a l ′ =a}=k {|μ a (s + l) -v up (a)| ⩾ 2 log(2/δ)/k}      ⩽ l k=1 (a l ′ ) l ′ s.t.Card{l ′ ∈{1,...,l} : a l ′ =a}=kP |μ a (s + l) -v up (a)| ⩾ 2 log(2/δ)/k A l = a l P(A l = a l )⩽ T δ , and with an union bound, we obtain thatP ∃ l ∈ [t], a ∈ A such that |μ a (l) -v up (a)| ⩾ 2 log(2/δ)/n l (a) ⩽ T 2 Kδ ,Considering the probability of the opposite event, we have thatEQUATIONwhere we rescaled δ as δ/T 2 K.For the remaining of the proof, we take δ = T -2 and define a ⋆ l = argmax a∈A {v up (a) + 1 ãl (a)τ }. We now assume that the event {for any l ∈ {s + 1, . . . , s + t}, a ∈ A, |μ a (l) -v up (a)| ⩽ 2 log(2T 2 K/δ)/n l (a)} holds. If at some step l ∈ {s + 1, . . . , s + t}, action A l is chosen in Algorithm 3, it means thatμA l (l) + 2 log(tK/δ)/n l (A l ) + 1 ãl (A l )τ ãl ⩾ μa ⋆ l (l) + 2 log(tK/δ)/n l (a ⋆ l ) + 1 ãl (a ⋆ l )τ ãl ,with regards to the choice of actions in UCB based on the upper confidence bound. We now decompose the whole regret on the batch {s + 1, . . . , s + t} defined as Rup p ({s + 1, . . . , s + t}, UCB, Π down p ). (20) ensures that with probability at least 1 -1/T 2 Rup p ({s + 1, . . . , s + t}, UCB,Π down p ) = s+t l=s+1 v up (a ⋆ l ) + 1 ãl (a ⋆ l )τ ãl -(v up (A l ) + 1 ãl (A l )τ ãl ) ⩽ s+t l=s+1 μa ⋆ l (l) + 2 log(Kt/δ)/n l (a ⋆ l ) -v up (A l ) + 1 ãl (a ⋆ l )τ ãl -1 ãl (A l )τ ãl ⩽ s+t l=s+1 μA l (l) + 2 log(Kt/δ)/n l (A l ) -v up (A l ) ⩽ s+t l=s+1 μA l (l) + 2 log(Kt/δ)/n l (A l ) -(μ A l (l) -2 log(Kt/δ)/n l (A l )) ⩽ 4 log(Kt/δ) s+t l=s+1 1/n l (A l ) ,and we haveEQUATIONwhere the last step holds because for any integers s, t ∈ N ⋆ , we have thats+t l=s+1 1 √ l = s+t l=s+1 1 √ l l x=l-1 dx ⩽ s+t l=s+1 l x=l-1 dx √ x = s+t x=s dx √ x = 2( √ s + t - √ s) .Using Cauchy-Schwarz inequality we obtain from ( 21)1/K s+t l=s+1 1/n l (A l ) ⩽ 2 1/K K i=1 n s+t (i) -n s (i) = 2 t/K , which gives s+t l=s+1 1/n l (A l ) ⩽ 2 √ tK.Finally plugging all the terms together, since δ = 1/T 2 , we obtain that with probability at least1 -1/T 2 Rup p ({s + 1, . . . , s + t}, UCB) ⩽ 8 log(KT 3 ) √ tK .Lemma 2. Assume H2 holds and consider some arm a ∈ A such that we run the d-th batch of binary search on a with d ∈ {1, . . . , ⌈log 2 T β ⌉}: for any t ∈ {k a,d + 1, . . . , k a,d + T }, we have (ã t , τ (t)) = (a, τ a ) with τ a = τ mid a (d) and T = ⌈T α ⌉. Recall that we defined in (18):T ̸ = a,d = Card {t ∈ {k a,d + 1, . . . , k a,d + T } such that A t ̸ = a}. Let β ∈ (0, 1) be such that β < α(1 -κ). Given that the event { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ } holds, we have that • If T ̸ = a,d < T -C T κ+β/α , then τ ⋆ a < τ a + 1/T β . • If T ̸ = a,d > C T κ+β/α , then τ ⋆ a > τ a -1/T β .Consequently, with probability at least1 -2T -αζ , if C T κ+β/α < T ̸ = a,d < T -C T κ+β/α , then |τ ⋆ a -τ a | ⩽ 1/T β .Proof of Lemma 2. The whole proof is done conditionally on the event{ Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ } .Note that it holds with probability at least 1 -T -ζ ⩾ 1 -T -αζ since we suppose that Π up p satisfies H2.Suppose that we have τ a ⩾ τ ⋆ a + 1/T β . By definition of the optimal incentives, we obtain, using by assumptionτ a ⩾ τ ⋆ a + 1/T β 1 a (a)τ a + v up (a) ⩾ τ ⋆ a + v up (a) + 1/T β = max a ′ ∈A v up (a ′ ) -v up (a) + v up (a) + 1/T β = max a ′ v up (a ′ ) + 1/T β ,which ensures that a is the optimal arm for the upstream player during the batch {k a,d + 1, . . . , k a,d + T } that we consider. In that case, since a is the best arm, by definition of the upstream player's utility, the reward gap E[v up (a) + τ a -(v up (A t ) + 1 a (A t )τ a )] for the upstream player at any step t ∈ {k a,d + 1, . . . , k a,d + T } is at least v up (a) + τ a -max a ′ ∈A v up (a ′ ), and we obtainC T κ ⩾ Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩾ T ̸ = a,d (τ a + v up (a) -max a ′ ∈A {v up (a ′ )}) ,by H2, T ̸ = a,d being the number of steps for which a suboptimal arm has been chosen. Therefore, by definition of the optimal incentives, we obtain thatC T κ ⩾ T ̸ = a,d (τ a -τ ⋆ a ) ⩾ T ̸ = a,d /T β ⩾ T ̸ = a,d T -β/α , which gives: T ̸ = a,d ⩽ C T κ+β/α. Therefore, if we take the contrapositive, we obtain that during the sequence {ka,d + 1, . . . , k a,d + T }, if T ̸ = a,d > C T κ+β/α , then with probability at least 1 -T -αζ , τ a < τ ⋆ a + 1/T β , or equivalently τ ⋆ a > τ a -1/T β . Now suppose that τ a ⩽ τ ⋆ a -1/T β .By definition of the optimal incentives, we obtain1 a (a)τ a + v up (a) ⩽ τ ⋆ a + v up (a) ⩽ max a ′ ∈A v up (a ′ ) -v up (a) + v up (a) -1/T β = max a ′ v up (a ′) -1/T β , which ensures that a is a suboptimal arm for the upstream player during this batch of time steps. Therefore, arm a which has a reward gap bigger than 1/T β since max a ′ ∈A {v up (a) + 1 a (a ′ )} -(v up (a) + τ a ) ⩾ 1/T β and arm a has been picked T -T ̸ = a,d times. Consequently, we have thatC T κ ⩾ Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩾ ( T -T ̸ = a,d )(max a ′ ∈A v up (a ′ ) -(τ a + v up (a)) ⩾1/T β ) ⩾ ( T -T ̸ = a,d ) T -β/α , which gives T ̸ = a,d ⩾ T -C T κ+/β/α. Therefore, if we take the contrapositive, we obtain that ifT ̸ = a,d < T -C T κ+/β/α , then with probability at least 1 -T -αζ , τ a > τ ⋆ a -1/T β , or equivalently τ ⋆ a < τ a + 1/T β .For the second part of the proof, suppose that: C T κ+β/α < T ̸ = a,d < T κ+β/α -C T κ+β/α . From the above result, we have that τ ⋆ a < τ a + 1/T β and τ ⋆ a > τ a -1/T β with probability at least 1 -2T -αζ . Plugging these inequalities in the absolute value |τ ⋆ a -τ a | concludes the proof.Lemma 3. Assume that we run Algorithm 2 and consider some binary search batch iterationd ∈ ⌈log T β ⌉ run on arm a ∈ A. Then 0 ⩽ τ a (d) ⩽ τ mid a (d) ⩽ τ a (d) ⩽ 1.Proof of Lemma 3. The proof proceeds by induction. Considering some action a ∈ A, we have for the initialisation before any binary search is run: τ a (0) = 0, τ a (0) = 1 and therefore τ mid a (0) ∈ [τ a (0), τ a (0)]. We now consider that a number d of binary search batches has been run on a. Suppose that we run an additional binary search batch on action a. We have Lemma 4. Consider some arm a ∈ A and suppose that we have run D ∈ N ⋆ batches of binary search of length T on a. Then, we have that EQUATIONP   d∈[D] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ }   ⩾ 1 -D/T αζ .) ⩾ C T κ ⩽ 1/ T ζ ,and applying a union bound over the D batches, we have thatP   d∈[D] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩾ C T κ }   ⩽ D j=1 P { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩾ C T κ } ⩽ D/ T ζ ,which gives thatP   d∈[D] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ }   ⩾ 1 -D/T αζ ,hence the result.Lemma 5. Suppose that the upstream player runs a subroutine Π up p satisfying H 2. Consider some action a ∈ A and the D-th binary search batch of length T run on arm a with D ∈ {1, . . . , ⌈log 2 T β ⌉}. Thend∈[D] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ } ⊆ {τ ⋆ a ∈ [τ a (D), τ a (D)]} ,and the probability of these events is at least 1 -⌈log 2 T β ⌉/T αζ . We also have that|τ a (D) -τ a (D)| ⩽ 1/2 D + 2/T β holds almost surely .Proof of Lemma 5. Suppose that the conditions of the lemma hold and consider some arm a.We show by induction on the number of binary search batches D that have been run on a thatd∈[D] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ } ⊆ {τ ⋆ a ∈ [τ a (D), τ a (D)]}.If it is true, Lemma 4 completes this first part of the proof.The initialisation holds since τ a (0) = 0, τ a (0) = 1 and τ⋆ a = max a ′ ∈A v up (a ′ ) -v up (a) ∈ [0, 1] with probability 1 -since max a ′ ∈A v up (a ′ ) ∈ [0, 1] and v up (a) ∈ [0, 1].We suppose that the property is true for some integer D < ⌈log 2 T β ⌉ and that we have run one more binary search on arm a. We haveτ mid a (D + 1) = τ a (D) + τ a (D) 2 ,τ mid a (D + 1) being the incentive offered to the upstream player if he chooses action a during the D-th batch {k a,D + 1, . . . , k a,D + T }. After this batch, ifT ̸ = a,D < T -C T κ+β/α , BELGIC updates τ a (D + 1) = τ mid a (D + 1) + 1/T β , τ a (D + 1) = τ a (D) and Lemma 2 ensures that τ a (D + 1) < τ ⋆ a < τ a (D + 1) given { Rup p ({k a,D+1 + 1, . . . , k a,D+1 + T }, Π up p , Π down p ) ⩽ C T κ }. Thus the induction holds. Otherwise, if T ̸ = a,D > C T κ+β/α , BELGIC updates τ a (D + 1) = τ mid a (D + 1) -1/T β , τ a (D + 1) = τ a (D) and Lemma 2 ensures that τ a (D + 1) < τ ⋆ a < τ a (D + 1) given { Rup p ({k a,D+1 + 1, . . . , k a,D+1 + T }, Π up p , Π down p ) ⩽ C T κ }.The induction still holds.Consequently, we have that for any number D of binary search batches run on arm a, τ ⋆ a ∈ [τ a (D), τ a (D)] with probability 1 -D/T αζ For the second part of the proof, we define u(D) = τ a (D) -τ a (D) ⩾ 0 as the length of the interval containing τ ⋆ a with probability at least 1-D/T αζ . We have u(0) = 1. Suppose that after D iterations of binary search batches, the next batch of binary search {k a,D+1 + 1, . . . , k a,D+1 + T } outputsT ̸ = a,D+1 < T -C T κ+β/α . Then, the update of Algorithm 2 gives u D+1 = τ a (D + 1) -τ a (D + 1) = τ mid a (D + 1) + 1/T β -τ a (D) = τ a (D) + τ a (D) 2 -τ a (D) + 1/T β = τ a (D) -τ a (D) 2 + 1/T β = u D /2 + 1/T β .On the other hand, if T ̸ = a,D+1 > C T κ+β/α , the update givesu D+1 = τ a (D + 1) -τ a (D + 1) = τ a (D a t ) -(τ mid a (D + 1) -1/T β ) = τ a (D) - τ a (D) + τ a (D) 2 + 1/T β = τ a (D) -τ a (D) 2 + 1/T β = u D /2 + 1/T β .We can see that (u D ) D⩾0 is an arithmetico-geometric sequence defined byu D+1 = u D /2 + 1/T β with an initial term u 0 = 1. Writing r = 1/T β /(1 -1/2) = 2/T β , we obtain that |τ a (D) -τ a (D)| = u D = 1/2 D (1 -r) + r = 1/2 D (1 -2/T β ) + 2/T β ⩽ 1/2 D + 2/T β ,for any D ∈ {1, . . . , ⌈log 2 T β ⌉}, hence the result.Lemma 6. Suppose that the upstream player runs a policy Π up p satisfying H2. Considering some action a ∈ A, we have that after the binary search batch D = ⌈log 2 T β ⌉:P(τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a + 3/T β ) ⩾ 1 -D/T αζ .Proof of Lemma 6. We suppose that the eventd∈[⌈log 2 T β ⌉] { Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ } holds.Lemma 4 ensures that this event holds with probability at least 1 -⌈log 2 T β ⌉/T αζ .After D = ⌈β log 2 T ⌉ batches of binary search on arm a, we have by Lemma 5 that|τ a (D) -τ a (D)| ⩽ 1/2 D + 2/T β ⩽ 1/2 β log 2 T + 2/T β = 3/T β .Lemma 5 guarantees that τ ⋆ a ∈ [τ a (D); τ a (D)] with probability at least 1 -D/T αζ , and we obtain τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a (D) + 3/T β with the same probability. Proposition 1. Under H1 and H2, after the first phase of BELGIC which consists in K⌈T α ⌉⌈log T β ⌉ steps of binary search grouped in ⌈log 2 T β ⌉ batches per arm a ∈ A, we have thatP for any a ∈ A, τa -4/T β -CT (κ-1)/2 ⩽ τ ⋆ a ⩽ τa ⩾ 1 -K⌈log 2 T β ⌉/T αζ .Proof of Proposition 1. We consider a number of binary search batches D = ⌈log T β ⌉ and we define the event G as G = for any a ∈ A, τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a (D) + 3/T β . We have thatP(G) = P a∈A τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a + 3/T β = 1 -P a∈A τ a (D) ⩽ τ ⋆ a ⩽ τ a (t) ⩽ τ a (D) + 3/T β c ⩾ 1 - a∈A P τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a (D) + 3/T β c ,where the last inequality holds with an union bound. Lemma 6 with D = ⌈log 2 T β ⌉ ensures that we haveP τ a (D) ⩽ τ ⋆ a ⩽ τ a (D) ⩽ τ a (D) + 3/T β c ⩽ D/T αζ ,and since Card{A} = K, we obtainP(G) ⩾ 1 -K⌈log 2 T β ⌉/T αζ .Since the estimated incentives are defined as τa = τ a (⌈log 2 T β ⌉) + 1/T β + CT (κ-1)/2 , we can concludeP( for any a ∈ A, τa -4/T β -CT (κ-1)/2 ⩽ τ ⋆ a ⩽ τa ) ⩾ 1 -K⌈log 2 T β ⌉/T αζ , since whenever τ a (⌈log 2 T β ⌉) ⩽ τ ⋆ a ⩽ τ a (⌈log 2 T β ⌉) ⩽ τ a (⌈log 2 T β ⌉) + 1/T β , we also have by definition: τa (⌈log 2 T β ⌉) -4/T β -CT (κ-1)/2 ⩽ τ a (⌈log 2 T β ⌉) ⩽ τ ⋆a ⩽ τa (⌈log 2 T β ⌉). Theorem 3. Assume that H1 and H2 hold. Then BELGIC, run with α, β satisfying (13) and any bandit subroutine Bandit-Alg, has an overall regret R down p such thatR down p (T, Π up p , BELGIC) ⩽ 2(3 + 2C + v -v) log 2 (T )(2T 1-αζ + T (κ+1)/2 + ⌈T α ⌉) + 4T 1-β + R Bandit-Alg (T, ν, {τ a } a∈A )where, for ease of notationv = max a,b∈A×A {v down (a, b)} and v = min a,b∈A×A {v down (a, b)} .Proof of Theorem 3. Suppose that the conditions of Theorem 3 are satisfied. By definition,Λ K+1 + 1 ∈ [T ]is the step at which starts the run of the subroutine Bandit-Alg, since Λ K+1 = K⌈T α ⌉⌈β log T ⌉. All the binary searche batches have length T = ⌈T α ⌉. For any a ∈ A, d ∈ {1, . . . , ⌈log 2 T β ⌉}, we define the eventB a,d = Rup p ({k a,d + 1, . . . , k a,d + T }, Π up p , Π down p ) ⩽ C T κ ,as well asE = a∈[K] d∈[⌈β log T ⌉] B a,d Rup p ({Λ K+1 + 1, . . . , T }, Π up p ) ⩽ C(T -Λ K+1 ) κ ,and by H2 and Lemma 4, with an union bound, we have thatP(E) = 1 -P     a∈[K] d=∈[⌈log T β ⌉] B c a,d Rup p ({Λ K+1 + 1, . . . , T }, Π up p , Π down p ) ⩽ C(T -Λ K+1 ) κ     ⩾ 1 - a∈[K] d∈[⌈log T β ⌉] P(B c a,d ) + P( Rup p ({Λ K+1 + 1, . . . , T }, Π up p ) ⩽ C(T -Λ K+1 ) κ ) ⩾ 1 -K⌈β log T ⌉ T -ζ -(T -Λ K+1 ) -ζ ⩾ 1 -K⌈β log T ⌉T -αζ -T -ζ ,and we now decomposeEQUATIONwhere Rdown p is defined asRdown p (T, Π up p , Π down p ) = T µ ⋆,down - T t=1 (v down (A t , B t ) -1 ãt (A t )τ (t)) .By definition, µ ⋆,down ⩾ min a,b∈A×A v down (a, b) ⩾ v and since Lemma 1 allows to write µ ⋆,down = max a,b∈A×A {v down (a, b)+ v up (a)} -max a ′ ∈A {v up (a ′ )}, we have that v ⩽ µ ⋆,down ⩽ 1 + v ,and note that since κ < 1, for any a ∈ A, τaEQUATIONWe consider the second term in (23) . We decompose it between the steps of binary search {1, . . . , K⌈T α ⌉⌈log 2 T β ⌉} during which we run the Binary Search Subroutine and the following ones when we run Bandit-Alg, which givesEQUATION⩽ E       1(E) K⌈T α ⌉⌈log 2 T β ⌉ t=1 µ ⋆,down -(v down (A t , B t ) -1 ãt (A t )τ (t)) (A)       + E        1(E) T t=K⌈T α ⌉⌈log 2 T β ⌉+1 µ ⋆,down -(v down (A t , B t ) -1 ãt (A t )τ (t)) (B)        .Similarly to (24), we use the bound on µ ⋆,down to bound (A), which givesEQUATIONAfter the binary search, at each step t ∈ {Λ K+1 + 1, . . . , T }, Bandit-Alg recommends (ã t , B t ) ∈ A × A following (15) and BELGIC offers an incentive (ã t , τãt ) with τa = τ a (⌈log2 T β ⌉) + 1/T β + CT (κ-1)/2 . Lemma 5 ensures that E ⊆ {τ ⋆ a ∈ [τ a (⌈log 2 T β ⌉), τ a (⌈log 2 T β ⌉)] for any a ∈ A} { Rup p ({Λ K+1 + 1, . . . , T }, Π up p ) ⩽ C(T -Λ K+1 ) κ }.Therefore, if E holds, for any a ∈ A, we have thatv up (a) + τa = v up (a) + τ a + 1/T β + CT (κ-1)/2 > v up (a) + τ ⋆ a + CT (κ-1)/2 = v up (a) + max a ′′ ∈A v up (a ′′ ) -v up (a) + CT (κ-1)/2 ,and therefore, for any a ′ ∈ A such that a ′ ̸ = a, we have thatEQUATION)This shows that at any steps t ∈ {Λ K+1 + 1, . . . , T } after the binary search, we have on the event E thatEQUATIONand the reward gap at step t for any a ̸ = ãt is defined asEQUATIONFollowing ( 27), the reward gap from (29) satisfiesmax a ′ ∈A {v up (a ′ ) + 1 ãt (a ′ )τ ãt } -(v up (a) + 1 ãt (a)τ ãt ) ⩾ CT (κ-1)/2 .We now define two setsI T = {t ∈ {K⌈T α ⌉⌈log 2 T ⌉ + 1, . . . , T } such that ãt = A t } , J T = {t ∈ {K⌈T α ⌉⌈log 2 T ⌉ + 1, . . . , T } such that ãt ̸ = A t } ,which satisfy I T ∪ J T = {K⌈T α ⌉⌈log 2 T ⌉ + 1, . . . , T } almost surely. As shown in ( 28), I T corresponds to all the steps during which the upstream player picked the best arm and for any t∈ I T v up (A t ) + 1 ãt (A t )τ (t) ⩾ max a∈A {v up (a) + 1 ãt (a)τ (t)} ,while by (29), for any t ∈ J T , we have thatEQUATION)H2 ensures that if E holds, then R up p ({Λ K+1 + 1, . . . , T }, Π up p , BELGIC) ⩽ C T κ , and this condition together with (30) gives that Card{J T } C T (κ-1)/2 ⩽ R up p ({Λ K+1 + 1, . . . , T }, Π up p , BELGIC) ⩽ CT κ , and consequently Card{J T } ⩽ T (κ+1)/2 . We now bound (B) as followsE[1(E)(B)] = E   1(E) T t=Λ K+1 +1 µ ⋆,down -v down (A t , B t ) -τãt   = E 1(E) t∈I T max a,b∈A×A {v down (a, b) -τ ⋆ a } -v down (ã t , B t ) -τãt + E   1(E) t∈J T µ ⋆,down -v down (A t , B t ) -τãt ⩽3+C+v-v    ⩽ E 1(E) t∈I T max a,b∈A×A v down (a, b) -τa -(v down (ã t , B t ) -τãt ) + max a ′ ∈A {τ a ′ -τ ⋆ a ′ } + (3 + C + v -v)E[1(E)Card{J T }] = E 1(E) t∈I T max a,b∈A×A v down (a, b) -τa -(v down (ã t , B t ) -τãt ) + E 1(E) t∈I T max a ′ ∈A {τ a ′ -τ ⋆ a ′ } + (3 + C + v -v) T (κ+1)/2 ⩽ R Bandit-Alg (Card{I T }, ν, {τ a } a∈A ) + E 1(E)Card{I T } max a ′ ∈A {τ a ′ -τ ⋆ a ′ } + (3 + C + v -v) T (κ+1)/2 ,where the first step holds by Lemma 1. Using Lemma 5, as well as the definition of E, we obtainE 1(E)Card{I T } max a ′ ∈A {τ a ′ -τ ⋆ a ′ } ⩽ E 1(E)Card {E}(4/T β + CT (κ-1)/2 ) ⩽ E[1(E)T ](4/T β + CT (κ-1)/2 ) ⩽ 4T 1-β + CT (κ+1)/2 ,which finally givesEQUATIONand plugging together ( 26) and (31) in the decomposition (25) gives the following boundE 1(E) Rdown p (T, Π up p , BELGIC)) ⩽ R Bandit-Alg (T, ν, {τ a } a∈A ) + 4T 1-β + (3 + 2C + v -v) T (1+κ)/2 + (3 + C + v -v)K⌈T α ⌉(1 + log 2 T ) ,and summing the bounds on the events E and E c finally givesR down p (T, Π up p , BELGIC) ⩽ R Bandit-Alg (T, ν, {τ a } a∈A ) + 4T 1-β + (3 + 2C + v -v) T (1+κ)/2 + (2 + C + v -v)K⌈T α ⌉(1 + log 2 T ) + (3 + C + v -v)(K(1 + log 2 T )T 1-αζ + T 1-ζ ) ⩽ R Bandit-Alg (T, ν, {τ a } a∈A ) + 4T 1-β + (3 + 2C + v -v) T (1+κ)/2 + (3 + C + v -v)((1 + log 2 T )(⌈T α ⌉ + T 1-αζ ) + T 1-ζ ) ⩽ (3 + 2C + v -v)(T 1-ζ + T (κ+1)/2 + (1 + log 2 T )(⌈T α ⌉ + T 1-αζ )) + R Bandit-Alg (T, ν, {τ a } a∈A ) + 4T 1-β ⩽ 2(3 + 2C + v -v) log 2 (T )(2T 1-αζ + T (κ+1)/2 + ⌈T α ⌉) + 4T 1-β + R Bandit-Alg (T, ν, {τ a } a∈A ) .Corollary 1. Assume that the upstream player's distribution (γ a ) a∈A is such that H 1 holds. In addition, suppose that the distributions (γ a ) a∈A and (ν a,b ) a,b∈A×A are 1-sub-Gaussian and that the upstream player plays Π up p = Algorithm 3 (a slight modification of UCB to take into account the incentives). Then the downstream player's regret when she runs BELGIC with parameters α = 3/4 and β = 1/4 (which satisfy (13)) and subroutine Bandit-Alg = UCB satisfies the following upper bound4 R down p (T, UCB, BELGIC) ⩽ (10+ 4K + 32 K log 2 (KT 3 ) + v -v) log 2 (T )(3 + 2T 3/4 ) + 3K 2 (v -v) .Proof of Corollary 1. First note that Π up p = Algorithm 3 satisfies H2 with constants κ = 1/2, ζ = 2, C = 8 K log(KT 3 ), following Proposition 2. Note that β/α = 1/3 < 1/2 = 1 -κ, therefore Equation ( 13) is satisfied. Plugging these terms in the bound from Theorem 3 with α = 3/4, β = 1/4 givesR down p (T, UCB, BELGIC) ⩽ 2(3 + 16 K log 2 (KT 3 ) + v -v) log 2 (T )(2T 1-3/2 + T 3/4 + ⌈T 3/4 ⌉) + 4T 1/4 + 8 K 2 log 2 (T ) T 1/2 + 3K 2 (v -v)where we use the bound for R Bandit-Alg (T, ν, {τ a } a∈A ) with Bandit-Alg = UCB run on any bandit instance with K 2 arms, 1-subgaussian rewards and reward gaps of at most max a,b∈A×A v down (a, b)min a,b∈A×A v down (a, b) = v -v, following [Lattimore and Szepesvári, 2020, Theorem 7.2 ]. Therefore, we have thatR down p (T, UCB, BELGIC) ⩽ (6 + 32 K log 2 (KT 3 ) + v -v) log 2 (T )(2 + 1 + 2T 3/4 ) + 4T 1/4 + 3K 2 (v -v) + 8K log 2 T T 1/2 ⩽ (10 + 32 K log 2 (KT 3 ) + v -v) log 2 (T )(3 + 2T 3/4 ) + 3K 2 (v -v) + 8K log 2 (T ) T 1/2 , which finally gives R down p (T, UCB, BELGIC) ⩽ (10 + 4K + 32 K log 2 (KT 3 ) + v -v) log 2 (T )(3 + 2T 3/4 ) + 3K 2 (v -v) ,hence the result. Justification: Our work presents a model to explore an online version of a theory from economics. Thereby, it implicitly has limitations due to the fact that a choice was made in the model.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.The fact that efficiency is restored whoever is given the property rights is known as the invariance property of the Coase theorem.A similar assumption is made in the work ofDonahue et al. [2024] but with a stronger instantaneous regret bound which does not encompass the UCB's regret bound.Note that it is K and not √ K here, since the action space is of cardinality K 2 for the downstream player.Note that it is K and not √ K here, since the action space is of cardinality K 2 for the downstream player. 


Decision: There was a consensus that this work tackles an interesting problem and provides significant results. All questions raised by the reviewers were addressed by the authors, and no further issues were raised during the discussion period. This is an easy accept (spotlight).

Reviews: review: paper_summary: paper_summary: The paper presents a two-player sequential game with bandit feedback where one player's actions create externalities that affect the other player's outcomes. In this model, the utility of only one player (the downstream player) is impacted by the collective actions of both the upstream and downstream players. They consider two scenarios: one where players act independently to maximize individual utility, and another where players can interact via transfers.

In the first scenario (without transfers), the authors show that individual utility maximization can lead to suboptimal social welfare in some instances. In the second scenario, where the downstream player can choose a transfer, they demonstrate that social welfare can reach its optimum. They propose an algorithm for the downstream player that achieves this outcome, provided the upstream player follows any no-regret policy. This effectively presents an online version of the Coase theorem, establishing that even with imperfect information, the two-player sequential game converges to the global optimum outcome when transfers are allowed.
strength_weakness: strength_weakness: Please see the questions section.
questions: questions: 1. It is not clear whether the regret incurred by the downstream player is optimal. Even if the upstream player is assumed to follow UCB, it's not evident whether a regret scaling as $\sqrt{T}$ policy is achievable for the downstream player as well. 
2. It is stated (on lines 111-112) that the assumption that the rewards are bounded is "without loss of generality" (WLOG). Can you please explain why? Would this work even in the case of other standard reward distributions in bandit literature, such as sub-Gaussian rewards?
3. In the current setup, it is assumed that transfers occur only on a single action, with the transfer function taking a value of 0 for all but one action. Is there a particular reason for assuming such a transfer function? Can we work with more general transfer functions where the downstream player can choose to make transfers on multiple actions? How would this affect the regret of the downstream player?
limitations: limitations: This paper does not have any negative social impact.
paper_summary: paper_summary: The paper explores the field of mitigating externalities in economic interactions by applying the Coase Theorem with hindsight rationality. The Coase Theorem, a fundamental concept in economics, suggests that in the presence of externalities, property rights, and bargaining strategies can be utilized to achieve an optimal outcome for all parties involved. However, traditional applications of the Coase Theorem assume that players have perfect knowledge of the game, which may not hold true in real-world scenarios.

In this paper, the authors introduce the concept of hindsight rationality, where players learn from past interactions to improve their decision-making processes. By incorporating hindsight rationality into the Coase Theorem framework, the paper aims to provide a mechanism through which players can adapt their strategies over time to maximize social welfare, even in the presence of uncertainty. The theoretical foundation of the paper is built upon a series of theorems supported by assumptions and proofs. 

Overall, the paper offers a novel perspective on addressing externalities in economic settings by integrating hindsight rationality into the Coase Theorem framework. Through a rigorous theoretical analysis, ethical considerations, and a discussion of limitations, the paper contributes to the ongoing discourse on optimizing social welfare in the presence of externalities.
strength_weakness: strength_weakness: W1. One significant weakness of the paper is the lack of empirical validation or experimental results to back up the proposed theoretical framework. Although the theoretical analysis is good, empirical evidence would improve the practical applicability and real-world relevance of the research findings.

W2. It would have been insightful to see a comprehensive discussion on the potential challenges and complexities associated with implementing the proposed approach in practical economic settings. Addressing implementation hurdles could provide valuable insights for policymakers and practitioners.

W3. The setting (extension of Coase theorem in a two-player bandit setting where the actions of one of the players affect the other player) considered in the paper is narrow and limited. The results are also exemplified for a simple setting of two firms, an upward and a downward. Do the observations apply to potentially broader settings? 

W4. The mathematical notations provided in the paper sometimes become too difficult to follow and correlate with the text.
questions: questions: Please clarify the points in the Weaknesses section.
limitations: limitations: Yes, the limitations of the proposed method are discussed in the paper.
paper_summary: paper_summary: This work considers a two player game with externalities imposed from one agent (“upstream”) to the other (“downstream”) agent. Equilibrium in the absence of taxation or payments between players would result in heavy efficiency loss due to the externalities.

The Coase theorem tells us that in these situations we should expect to see payments from the downstream agent to the upstream agent in order to restore the socially optimal outcome.

This work formulates this scenario as a multi-armed bandit problem, in which the payment term forms a part of the players payoffs and options. Namely, the downstream agent can put a conditional payment on the arms played by the upstream bandit. In this situation, the paper asks whether or not normal bandit learning algorithms can learn the optimal outcome.

The paper puts forwards an assumption that must be satisfied on the upstream agents learning behavior, which is satisfied for many common bandit learning algorithms. A translation is given for the downstream agent to go from the raw bandit problem to a transformed bandit problem. With these, sublinear regret is realized relative to the socially optimal outcome.
strength_weakness: strength_weakness: The paper and situation is quite interesting, but is one specific (classic) example scenario so applicability is good because it is a classic example, but still limited. A natural followin question is how broad do we expect these situations to go - can we recover general externalities in multi agent situations?
questions: questions: How broad do you expect the BELGIC routine to be applicable? In a general $M$ agent situation with less obvious structure on the externalities would you expect optimal transfers to still be learned efficiently?
limitations: limitations: Yes the authors have adequately addressed limitations of their work.

Comments: comment: Thank you for your response. I have no further questions.
Thank you for your responses. The authors address some of my concerns and I am happy to increase my score to 6.