# Regulation of Algorithmic Collusion

Jason D. Hartline<EMAIL_ADDRESS>,  Sheng Long
<EMAIL_ADDRESS>and  Chenhao Zhang
<EMAIL_ADDRESS>Northwestern UniversityEvanstonUSA

(2024)

###### Abstract.

Consider sellers in a competitive market that use algorithms to adapt their
prices from data that they collect. In such a context it is plausible that
algorithms could arrive at prices that are higher than the competitive prices
and this may benefit sellers at the expense of consumers (i.e., the buyers in
the market). This paper gives a definition of plausible algorithmic non-
collusion for pricing algorithms. The definition allows a regulator to
empirically audit algorithms by applying a statistical test to the data that
they collect. Algorithms that are good, i.e., approximately optimize prices to
market conditions, can be augmented to collect the data sufficient to pass the
audit. Algorithms that have colluded on, e.g., supra-competitive prices cannot
pass the audit. The definition allows sellers to possess useful side
information that may be correlated with supply and demand and could affect the
prices used by good algorithms. The paper provides an analysis of the
statistical complexity of such an audit, i.e., how much data is sufficient for
the test of non-collusion to be accurate.

††journalyear: 2024††conference: Symposium on Computer Science and Law; March
12–13, 2024; Boston, MA, USA††booktitle: Symposium on Computer Science and Law
(CSLAW ’24), March 12–13, 2024, Boston, MA, USA††doi:
10.1145/3614407.3643706††isbn: 979-8-4007-0333-1/24/03††ccs: Applied computing
Law††ccs: Theory of computation Online learning theory††ccs: Theory of
computation Algorithmic game theory and mechanism design

##  1\. Introduction

Algorithms are increasingly being used to price goods and services in
competitive markets. Several recent papers have shown that in certain
settings, some configurations of certain pricing algorithms can find and
maintain supra-competitive prices when in competition with each other (Calvano
et al., 2020; Banchio and Skrzypacz, 2022; Asker et al., 2023; Assad et al.,
2020). As a result, (a) regulators may be concerned about how the risk of
algorithmic collusion can be mitigated and the consistency of this regulation
with legal standards for collusion, (b) individual sellers may be interested
in algorithms that provably do not collude, and (c) third-party
platforms111Current legal standards make it illegal for a platform or third-
party algorithm vendor to recommend/sell algorithms that arrive at supra-
competitive prices (Harrington, 2022). like AirBnB and eBay may want to only
recommend pricing algorithms to their sellers that will not risk incriminating
the platforms themselves for price fixing (Harrington, 2022). Several papers
have proposed ways to change competition and antitrust law in response to the
potential risks brought by algorithmic collusion (Beneke and Mackenrodt, 2019;
Gal, 2023; Harrington, 2018). This paper complements these proposals with a
method for regulating algorithmic collusion from data.

For individual adoption of pricing algorithms, our test for plausible
algorithmic collusion parallels the role that overt communication plays in the
modern legal theory of (non-algorithmic) collusion. Under current, if
controversial, understandings of American antitrust law, an express agreement
(in the form of overt communication) is a prerequisite to establishing
liability under the Sherman Act.222The act of colluding without an express
agreement is known as “tacit collusion”. The Supreme Court defined tacit
collusion as “the process, not in itself unlawful, by which firms in a
concentrated market might in effect share monopoly power, setting their prices
at a profit-maximizing, supracompetitive level by recognizing their shared
economic interests and their interdependence with respect to price and output
decisions” (_Brooke Group Ltd._ v. _Brown & Williamson Tobacco Corp._, 1993).
Courts cannot read the minds of the sellers to understand their pricing
strategies and therefore prefer to rely on evidence of overt illegal
coordination (Harrington, 2018). Similarly, we might not know some of the
fundamentals that guide a seller’s pricing algorithm (e.g., seller’s costs or
information about the demand), but we can identify outcomes that are
competitive for some fundamentals. We refer to such outcomes as plausible non-
collusion. What is left out is outcomes that are non-competitive for any
fundamentals, i.e., regardless of what is in the minds of the sellers. We
argue subsequently that there is no loss in forbidding algorithms that obtain
such non-competitive outcomes.

Status quo and challenges for algorithmic collusion law Under current legal
standards, algorithmic collusion does not constitute an overt agreement and is
not illegal (Harrington, 2018). It is, however, problematic, because
algorithmic interactions can result in supra-competitive prices which harm
consumers without overt communication. Thus, a regulator may want to audit
algorithms for potential collusive behavior. Harrington (2018) noted that
algorithms afford introspection that non-algorithmic human agents do not
afford. He discussed regulating algorithmic collusion by prohibiting pricing
algorithms with certain properties and proposed a few “inside the head”
approaches to check if an algorithm has any of these properties. One approach
is for the regulator to check the source code of the algorithms. This approach
has several drawbacks. On one hand, this approach seems to require costly and
detailed scrutiny by experts (Kroll et al., 2017) and has the potential to
leak the intellectual property of the algorithm developers (_Ruckelshaus_ v.
_Monsanto Co_., 1984). On the other hand, the source code of popular black box
algorithms such as those based on deep neural networks gives little
information about its behavior.

Another approach Harrington (2018) discussed is to conduct dynamic testing on
the pricing algorithms, i.e., running the algorithms by feeding them with
simulated inputs to observe their behavior. Although dynamic testing is
generally considered an effective approach for detecting software bugs, there
are still challenges when applied to understanding the behaviors of pricing
algorithms. To make better pricing decisions in vibrant market environments,
the inputs to pricing algorithms are usually large in dimensions and dynamic.
It is infeasible to exhaust all or even a small portion of the possible inputs
the algorithms could take. Further, the inputs the algorithms receive from the
environments in which they are deployed could be very different from the
simulated ones the regulators could expect. Even worse, the not-so-recent
Volkswagen emissions scandal and the emergence of the field of non-
adversarially robust machine learning (Carlini and Wagner, 2017; Biggio et
al., 2013) showed that inputs, where collusion happens, could be adversarially
hidden to evade scrutiny. As the early pioneer of computer science Edsger W.
Dijkstra noted regarding testing for bug-finding, “The first moral of the
story is that program testing can be used very effectively to show the
presence of bugs but never to show their absence” (Dijkstra, 1970). Dynamic
testing can be largely uninformative for the behavior of pricing algorithms on
inputs that are not tested during simulation but show up during the
algorithms’ actual deployment. Similar points for dynamic testing have also
been made by Desai and Kroll (2017).

Our approach/philosophy: regulation from dataThis paper takes a different
approach. It identifies an empirical condition that can be checked from data
logged by the algorithm while deployed to prove statistically that the
algorithm is not colluding under reasonable assumptions. It provides a way to
augment any “good” algorithm to collect this data without significantly
harming its performance. “Bad” algorithms that collude on implausibly
competitive prices cannot be augmented to collect data and pass the audit. Our
framework enables algorithms to prove that they are plausibly non-collusive
and opens the opportunity for new legal standards for enforcing non-collusion,
namely, requiring the algorithms used to continually pass such a test.

Introduce five properties of non-collusion The paper develops an empirical
definition of plausible non-collusion that has the following two groups of
properties:

  * •

Economic properties:

    * –

(unilateral) non-collusion is a unilateral property that an algorithm can
satisfy independently of what other algorithms are doing.

    * –

(information compatible) it allows the sellers to use side information that
may be correlated.

    * –

(optimal) optimizing is not collusion.

  * •

Legal properties:

    * –

(plausibly correct) algorithms that collude on supra-competitive price
inconsistent with plausible preferences and beliefs of sellers can not satisfy
it.

    * –

(minimum burden of compliance) There are known good algorithms, i.e., those
that do not use suboptimal prices, that satisfy the definition. Any new good
algorithm can be augmented to collect the necessary data to satisfy the
definition with little performance loss.

Relating calibrated best response to equilibrium Justification of economic
properties is as follows. It is critical for a definition of non-collusion to
have the property of being unilateral. A seller should always be able to adopt
a pricing strategy that is non-collusive, regardless of what other sellers do.
It may surprise the reader that our definition of non-collusion allows
correlation of the the sellers’ behavior. This correlation of behavior is
required to handle side information that could be correlated. Consider the
following example, the demand for hotels in the business district is higher
during the week and the day-of-week is known to all sellers. Setting different
prices in response to known differences in demand is not collusion. Last but
not least, if the seller is optimizing given the information they obtained,
then this act of optimization is not collusion. We argue that if algorithms
satisfy the three economic properties, then they are not colluding. If
algorithms do not satisfy these three properties, then something undesirable
is happening that regulators may wish to rule out.

The legal properties our definition satisfies make it appropriate for
regulators to require it for pricing algorithms. Our definition of non-
collusion rules out the algorithms that collude on supra-competitive prices
identifiable without “seeing through the minds” of the sellers deploying them.
Note that this definition does leave two ways sellers could be supra-
competitive but plausibly competitive: by acting as though their costs are
higher than their actual costs or ignoring information that they may have in
the market that would result in lower prices. Since the regulator cannot see
into the minds of the sellers, the legal standards suggest that such plausible
non-collusion is not illegal.333There may be opportunities to be further
restrictive for pricing algorithms recommended by platforms like AirBnB and
eBay that must be configured by individual sellers with information such as
their costs. When the costs are reported and can be logged by the algorithm,
it could be required that the prices are competitive for the reported costs.
This parallels the modern legal theory of regulating non-algorithmic collusion
via explicit agreements. Our definition also places a minimum burden on
sellers deploying pricing algorithms that satisfy the economic properties.
Algorithms that satisfy the properties and collect the relevant data are known
and new algorithms satisfying the property can be augmented to one that
collects relevant data with minor effects on its performance. Therefore, it is
feasible for the regulator to make it a requirement for all pricing algorithms
without putting excessive burdens on firms adopting them.

contributions of this paperIn summary, our main contributions are as follows:
(1) a definition of non-collusion; (2) a framework for empirically auditing
pricing algorithms whether they satisfy plausibly non-collusion (3) an
instantiation of our framework and an analysis of its statistical complexity.
Using our provided framework, algorithms can collect data to prove their
plausible non-collusion and regulators can audit algorithms without checking
source code or limiting algorithms to be a pre-approved set of requirements.
Algorithmic dynamics The main technical analysis of our definition of non-
collusion contributes a quantification of the sample complexity (i.e., how
much data is necessary) for an algorithm to collect to prove with high
confidence that it is plausibly not colluding.

###  1.1. Related literature

Modern legal theory of collusionAs of current, collusion is regulated in the
US legal system by three core federal antitrust laws: the Sherman Act (1890),
the Federal Trade Commission Act (1914), and the Clayton Act (1914). The
standard legal definition for collusion leaves open the issue of whether an
express agreement through overt communication is needed for the behavior to be
deemed illegal (Chassang and Ortner, 2023). Earlier rulings such as
_Interstate Circuit, Inc._ v.  _United States_ (1939) and _American Tobacco
Co._ v.  _United States_ (1946) found firms engaging in illegal collusion
without any explicit agreement via communication. However, more recent
judicial decisions, such as _Brooke Group Ltd._ v. _Brown & Williamson Tobacco
Corp._ (1993), have evolved to require the presence of such agreements. Tacit
collusion by itself is not a violation of the Sherman Act (_In re Text
Messaging Antitrust Litigation_ , 2015). The raison d’être for requiring
express agreement is that it gives an explicit condition that courts can
establish. Courts have declined to impose antitrust liability for tacit
collusion alone, partly because it is difficult to distinguish tacit collusion
from independent decision-making that simply takes into account the actions of
rivals in oligopolistic markets (Yao and DeSanti, 1993). As Judge Breyer puts
it, “[it] is not because such [parallel] pricing is desirable (it is not), but
because it is close to impossible to devise a judicially enforceable remedy
for ‘interdependent pricing’. How does one order a firm to set its prices
without regard to the likely reactions of its competitors?” (_Clamp-All Corp._
v. _Cast Iron Soil Pipe Institute_ , 1988) The courts use an analytical
framework that permits an inference of conspiracy where there is
circumstantial evidence of tacit collusion “plus” something else that tends to
“exclude the possibility that the alleged conspirators acted independently”
(Yao and DeSanti, 1993; Kovacic et al., 2011). Kovacic and Shapiro (2000)
provides a detailed review of the evolution of thinking about competition as
reflected by major antitrust decisions and research in industrial
organizations.

Economists study collusion mostly via the lens of oligopoly theory. Non-
cooperative game theory is the currently accepted economic mode to analyze
oligopolistic interactions (Yao and DeSanti, 1993). Despite the vast
literature, there is no unified theory of oligopolistic rivalry, though the
mainstream models share common assumptions and approaches. That is, economists
agree on what elements a “good” model should contain (Yao and DeSanti, 1993;
Werden, 2004). Earlier works on oligopoly theory include Stigler (1964) and
Friedman (1971). Werden (2004) provides a good review of basic terms and
concepts in game theory as well as modern oligopoly theory.

There has also been a lot of recent work on pricing algorithms and whether/how
they could lead to potentially collusive outcomes. Empirical work, such as
Assad et al. (2020), studied the effects of pricing algorithms in the German
retail gasoline market. They found that prices increased substantially after
both firms in a duopoly switched from manual to algorithmic pricing (Gal,
2023). In a well-cited simulation study, Calvano et al. (2020) showed that a
commonly used reinforcement learning algorithm learned to initiate and sustain
a supra-competitive equilibrium when only instructed to maximize its own
profits in a simultaneous, repeated price competition. Klein (2021) observes a
similar reward-punishment pattern as Calvano et al. (2020). At the same time,
there is also research that provides evidence for the opposite argument. For
example, Abada and Lambin (2023) showed that seemingly collusive outcomes
could originate in imperfect exploration rather than excessive algorithmic
sophistication. den Boer et al. (2022) examined the Q-learning algorithm used
in Calvano et al. (2020) in detail and concluded that “simulations presented
by Calvano et al. (2020a) do not give sufficient evidence for the claim that
these types of Q-learning algorithms systematically learn collusive
strategies.” Banchio and Mantegazza (2023) developed a theory of explaining
the collusive behavior of learning algorithms by their statistical linkage.

Between the economic and legal literature, there seems to be a gap between how
they view collusion. While the law examines whether competitors have taken
possibly avoidable actions from which an anti-competitive agreement may be
inferred, economic theory is more concerned with what final coordinated
outcomes may be produced by certain conduct (Yao and DeSanti, 1993). This may
explain why some legal scholars tend to use the term “collusion” more narrowly
to refer to illegal cartelization only (and not legal oligopolistic
coordination) (Gal, 2023). The term “algorithmic collusion” lends itself to
different interpretations, and we use it throughout the paper to refer to
“algorithmic tacit collusion” as opposed to “algorithmic explicit collusion”,
where algorithms implement an existing collusive strategy potentially defined
or agreed upon by humans (Gautier et al., 2020).

Last but not least, this paper builds on an extensive literature on dynamic
learning of prices. Early papers by Bar-Yossef et al. (2002); Kleinberg and
Leighton (2003); Blum et al. (2003); Blum and Hartline (2005) show that the
dynamic learning of prices fits into the framework of multi-armed bandit
learning, enabling a large portfolio of well-studied algorithms to be
successfully applied. Multi-armed bandit learning can be applied in repeated
interactions with partial information444Here “partial information” is that the
learner only learns the outcome of the selected price, they do not learn
counterfactual outcomes of other prices. There is a canonical reduction from
multi-armed bandit learning to online learning (with full feedback, e.g.,
where the learner also learns the payoffs of counterfactual prices) that
employs propensity scoring, i.e., constructing unbiased estimators of
counterfactual payoffs. Blum and Mansour (2007) reduce best-in-hindsight
learning (a.k.a., external regret) to calibrated learning (a.k.a., internal or
swap regret). Nekipelov et al. (2015) consider inferring values of ad buyers
from bidding data assuming a full feedback model. Our analysis is based on
their definition of the rationalizable set of values and regrets for a buyer,
naturally applied to the dual problem of a seller with a cost, and generalized
from the full feedback setting to the partial feedback setting.

Concurrent to our work, Chassang and Ortner (2023) informally discussed the
idea of enforcing a property (known as “no regret”) on pricing AIs based on
the observation of Chassang et al. (2022). The latter proposed a definition of
competitiveness and applied it to empirically test competitive behaviors with
real-world procurement auction data.

$c_{1}$$p_{1}$1$c_{2}$$p_{2}$1$A_{1}$$A_{2}$$\emptyset$$\mathbf{v}$Seller
1Seller 2 Figure 1. Geometric illustration of the example at a particular
round. Two sellers post prices $p_{1}$ and $p_{2}$ respectively. The buyer
buys from Seller 1 if his valuation $\text{v}\equiv(v_{1},v_{2})$ (represented
by the black dot), lies in the region $A_{1}$. He buys from Seller 2 if v lies
in the $A_{2}$. The buyer buys from neither seller if v lies in the region
$\emptyset$.

##  2\. Preliminaries

###  2.1. Dynamic Imperfect Price Competition

We consider a setting of dynamic imperfect price competitions with $k$
discrete price levels in which $n$ sellers repeatedly compete for selling one
unit of good or service (hereafter referred to as “good”) over $T$ rounds.
Seller $i$ has a fixed cost $c_{i}$ to produce a unit of the good. In each
round $t$:

  * •

Seller $i$ posts a price $p^{t}_{i}\in\mathcal{P}$, where $\mathcal{P}$ is the
set of discretized price levels with ${\left|\mathcal{P}\right|}=k$.

  * •

The market condition for seller $i$ is captured by a demand function555In
mechanism design and auction contexts, demand functions are usually referred
to as “allocation rules”.  $x_{i}^{t}:\mathcal{P}^{n}\to[0,1]$. It produces
the demand $x_{i}^{t}(p_{i}^{t},p_{-i}^{t})$ for seller $i$ where
$p_{-i}^{t}=(p_{1}^{t},\dots,p_{i-1}^{t},p_{i+1}^{t},\dots,p_{n}^{t})$. In
other words, $x_{i}^{t}$ is jointly determined by the prices posted by all
sellers. Assuming normal goods, fixing $p_{-i}$, $x_{i}$ is monotonic in
$p_{i}$.

  * •

Seller $i$ gets a payoff of
$u_{i}^{t}(p^{t}_{i})=(p^{t}_{i}-c_{i})\,x_{i}^{t}(p^{t}_{i},p^{t}_{-i})$.

An illustrative example with two sellers is shown in Figure 1. Seller $1$ and
$2$ have cost $c_{1},c_{2}\in[0,1]$ respectively. The price levels
$\mathcal{P}\subseteq[0,1]$. At each round $t$, a buyer shows up with
valuation $v^{t}_{1}$ and $v^{t}_{2}$ for the goods provided by the two
sellers respectively. After seeing the prices $p^{t}_{1}$ and $p^{t}_{2}$
posted by the two sellers, the buyer chooses to buy from seller $i$ that
maximizes his utility $v^{t}_{i}-p^{t}_{i}$ if $v^{t}_{i}-p^{t}_{i}\geq 0$,
breaking ties in favor of seller 1. He “buys nothing” if
$v^{t}_{i}-p^{t}_{i}<0$ for both $i=1,2$. Suppose each buyer draws his
valuations $(v^{t}_{1},v^{t}_{2})$ from the distribution $D^{t}$, the demand
for Seller 1’s good is

$\displaystyle x^{t}_{1}(p^{t}_{1},p^{t}_{2})$
$\displaystyle=\Pr_{(v^{t}_{1},v^{t}_{2})\sim
D^{t}}[v^{t}_{1}-p^{t}_{1}\geq\max(v^{t}_{2}-p^{t}_{2},0)].$

A special case of this example is when the buyer’s valuations of the two
sellers are i.i.d. uniformly distributed over $[0,1]$ at every round, i.e.,
$D^{t}=U[0,1]\times U[0,1]$. If we further assume that each seller sets one
fixed price to post for all rounds, with cost $c_{1}=0.1$ and $c_{2}=0.2$, the
equilibrium prices are $p_{1}^{eq}\approx 0.50$ and $p_{2}^{eq}\approx 0.55$.
However, if the two sellers collude by setting supra-competitive prices
$p_{1}^{c}\approx 0.60$ and $p_{2}^{c}\approx 0.66$, they will get a higher
total average revenue.

###  2.2. Learning Problem of Sellers

The dynamic pricing problem of each seller is essentially an online learning
problem. At round $t$, seller $i$’s pricing algorithm chooses a price
distribution $\pi_{i}^{t}\in\Delta(\mathcal{P})$ based on her information
about the history and the market. She then draws a price $p_{i}^{t}$ from the
distribution $\pi_{i}^{t}$ and posts $p_{i}^{t}$, where
$p_{-i}^{t}=(p_{1}^{t},\dots,p_{i-1}^{t},p_{i+1}^{t},\dots,p_{n}^{t})$ denotes
the prices set by sellers other than $i$. Following the model of online
learning with bandit feedback, we make the minimum assumption about the
information a seller possesses: After posting $p_{i}^{t}$ at round $t$, seller
$i$ observes the demand for her good $x_{i}^{t}(p_{i}^{t},p_{-i}^{t})$ and
hence her payoff $u_{i}^{t}(p_{i}^{t},p_{-i}^{t})$ as she knows her cost
$c_{i}$.

To measure the performance of a seller’s online learning algorithm, we employ
the concept of hindsight calibrated regret, which is defined as the benefit of
the best-in-hindsight remapping of the actions chosen by the algorithms. We
instantiate this definition in the setting of price competition.

###### Definition 2.0.

Given a sequence of historical prices $\\{(p_{i}^{t},p_{-i}^{t})\\}_{t=1}^{T}$
and demand functions $\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}$ for seller $i$ with
cost $c_{i}$, the _hindsight (realized) regret against a fixed price remapping
$\sigma:\mathcal{P}\to\mathcal{P}$_ is

$\displaystyle R^{T}(\sigma,c_{i})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}u_{i}^{t}(\sigma(p_{i}^{t}),p_{-i}^{t})-u_{i}^{t}(p_{i}^{t},p_{-i}^{t})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}(\sigma(p_{i}^{t})-c_{i})x_{i}^{t}(\sigma(p_{i}^{t}))-(p_{i}^{t}-c_{i})x_{i}^{t}(p_{i}^{t}).$

The maximum hindsight calibrated regret over all remappings,
$\max_{\sigma}R^{T}(\sigma,c_{i})$, is defined to be the _hindsight calibrated
(realized) regret_ (hereafter referred to as “regret” when it is clear from
the context).

Since a seller’s pricing algorithm chooses a distribution of prices at each
round, a performance measure without considering a particular realization of
the distributions is the expected regret.

###### Definition 2.0.

Given a sequence of historical price distributions
$\\{\pi_{i}^{t}\\}_{t=1}^{T}$, prices $\\{p_{-i}^{t}\\}_{t=1}^{T}$, and demand
functions $\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}$, the _expected regret of seller
$i$ with cost $c_{i}$ against a fixed price remapping
$\sigma:\mathcal{P}\to\mathcal{P}$_ is

$\displaystyle ER^{T}(\sigma,c_{i})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p_{i}^{t}\sim\pi_{i}^{t}}[u_{i}^{t}(\sigma(p_{i}^{t}),p_{-i}^{t})-u_{i}^{t}(p_{i}^{t},p_{-i}^{t})]$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p_{i}^{t}\sim\pi_{i}^{t}}[(\sigma(p_{i}^{t})-c_{i})\cdot
x_{i}^{t}(\sigma(p_{i}^{t}),p_{-i}^{t})$
$\displaystyle\phantom{\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p_{i}^{t}\sim\pi_{i}^{t}}[]}-(p_{i}^{t}-c_{i})\cdot
x_{i}^{t}(p_{i}^{t},p_{-i}^{t})].$

The _expected regret_ for $i$ is defined as
$\max_{\sigma}ER^{T}(\sigma,c_{i})$.

Note that calibrated regret is also called “swap regret” or “internal regret”
in the literature. In addition, there is a common weaker notion of regret,
known as the hindsight external regret. Hindsight external regret is defined
as the benefit of deviating to a single best-in-hindsight action.

###### Definition 2.0.

Given a sequence of historical prices $\\{(p_{i}^{t},p_{-i}^{t})\\}_{t=1}^{T}$
and demand functions $\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}$ for seller $i$ with
cost $c_{i}$, the _hindsight external regret_

$\displaystyle R_{\mathrm{ext}}^{t}(c_{i})$
$\displaystyle=\max_{p}\frac{1}{T}\sum_{t=1}^{T}u_{i}^{t}(p,p_{-i}^{t})-u_{i}^{t}(p_{i}^{t},p_{-i}^{t})$
$\displaystyle=\max_{p}\frac{1}{T}\sum_{t=1}^{T}(p-c_{i})x_{i}^{t}(p)-(p_{i}^{t}-c_{i})x_{i}^{t}(p_{i}^{t}).$

Observe that the definition of hindsight external regret does not allow
beneficial side information. Later in this paper, we argue that hindsight
external regret is insufficient for our purposes.

Based on the results of Auer et al. (2002), Blum and Mansour (2007) and Stoltz
(2005) give algorithms that achieve vanishing expected regret for an
individual seller regardless of the market condition and other sellers’
behavior. Such algorithms are generally referred to as “no-regret learning
algorithms”.

###### Theorem 2.4 (Blum and Mansour, 2007; Stoltz, 2005).

For a seller $i$ with cost $c_{i}$, there exists an online algorithm such
that:

  * •

At round $t$, it outputs a price distribution $\pi_{i}^{t}\in\mathcal{P}$
based on the history $\\{p_{i}^{s}\\}_{s=1}^{t-1}$ and
$\\{x_{i}^{s}(p_{i}^{s})\\}_{s=1}^{t-1}$.

  * •

The expected regret of seller $i$ given any sequence of
$\\{p_{-i}^{t}\\}_{t=1}^{T}$ and $\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}$ with the
algorithm’s output $\\{\pi_{i}^{t}\\}_{t=1}^{T}$ satisfies
$\max_{\sigma}ER^{T}(\sigma,c_{i})=o(1)$.

A characteristic of no-regret learning algorithms is that they lead to
_correlated equilibrium_ (Foster and Vohra, 1997). Correlated equilibrium
(Aumann, 1974) is a static equilibrium concept that is often described as a
mediator that draws a profile of prices from a joint distribution and
privately suggests a corresponding price for each seller. The joint
distribution of prices is a correlated equilibrium if each seller has no
incentive to deviate from their suggested price.

###### Definition 2.0.

A joint distribution of prices $\Pi\in\Delta(\mathcal{P}^{n})$ is a
_correlated equilibrium_ if for each seller $i$, any realized price $p_{i}$
from the distribution is a best response conditional on $p_{i}$:

$\displaystyle p_{i}$
$\displaystyle\in\operatorname{argmax}_{p}\mathbb{E}_{(p_{i},p_{-i})\sim\Pi}[u_{i}(p,p_{-i})\,\mid\,p_{i}]\text{
for all $p_{i}$}.$

The regulator of pricing algorithms may not know the cost of the sellers.
Nekipelov et al. (2015) consider inferring both the costs and the regrets of
learning algorithms. They refer to the pairs of costs and regrets that are
consistent with the data to be the rationalizable set. They show how to
identify these rationalizable sets by assuming the pricing data contains
counterfactual outcomes, i.e., what would have happened if a seller used a
different price. We generalize this method to pricing data that does not
contain counterfactual outcomes.

###### Definition 2.0.

Given the historical price distributions $\\{\pi_{i}^{t}\\}^{T}_{t=1}$, prices
$\\{p_{-i}^{t}\\}_{t=1}^{T}$ and demand functions
$\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}$, a cost-regret pair $(c_{i},\epsilon_{i})$
for seller $i$ is _rationalizable_ if it satisfies

(1)
$\forall\sigma,\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p_{i}^{t}\sim\pi_{i}^{t}}[(\sigma(p_{i}^{t})-c_{i})\cdot
x_{i}^{t}(\sigma(p_{i}^{t}),p_{-i}^{t})-(p_{i}^{t}-c_{i})\cdot
x_{i}^{t}(p_{i}^{t},p_{-i}^{t})]\leq\epsilon_{i}$

We define the rationalizable set
$\mathcal{NR}_{i}\left(\\{\pi_{i}^{t}\\}^{T}_{t=1},\\{p_{-i}^{t}\\}_{t=1}^{T},\\{x_{i}^{t}(\cdot)\\}_{t=1}^{T}\right)$
as the set of all rationalizable pairs $(c_{i},\epsilon)$.

Each point $(c_{i},\epsilon_{i})$ on the lower boundary of the rationalizable
set gives the maximum expected regret $\epsilon_{i}$ of seller $i$ when she
has cost $c_{i}$. The rationalizable set can be efficiently computed via the
method provided in Nekipelov et al. (2015) with minimal assumptions.

###  2.3. Collusive Equilibria in Repeated Games

The setting of dynamic imperfect price competition is a repeated game. On the
other hand, correlated equilibria described previously is an equilibrium
concept for a static game (not repeated). No hindsight regret learning
algorithms in the dynamic game, as we have seen, converge to this static
equilibrium concept. The literature on repeated games, on the other hand,
typically talks about dynamic equilibrium concepts, where an agent can
explicitly condition on the actions of other agents in previous stages,
perhaps to punish them for deviating from some prescribed strategy. We view
such equilibria as collusive. The so-called “folk theorem” of repeated games
describes outcomes that are possible as equilibria of a repeated game.

Benoit and Krishna (1985) give a folk theorem for finitely repeated games.
Stated in words: under weak conditions, any feasible and individually rational
payoff of the one-shot game can be approximated by the average payoff in a
subgame-perfect equilibrium of a repeated game with a sufficiently long
horizon. This theorem implies that in the stage game of a dynamic imperfect
price competition game, the minimax payoff for seller $i$, or, the best payoff
that seller $i$ can obtain when other sellers are “punishing” $i$ for
deviating from an agreed-upon action is 0. From this we have the following
corollary:

###### Corollary 2.7.

In a dynamic imperfect price competition game, any sequence of outcomes where
sellers have non-negative utility can be an equilibrium for the repeated game.

We have focused on no hindsight regret learning algorithms that converge to
correlated equilibria in the static game. Another large family of learning
algorithms that are natural to use for price competition is no policy regret
learning algorithms. When a seller is learning how to price, it is natural for
competitors to react to the seller’s prices with their own pricing strategy.
Policy regret algorithms compare their performance to the performance they
could have achieved if they switched to a fixed policy and the others in the
market responded to this switch.

Arora et al. (2018) introduced the notion of a policy equilibrium that
corresponds to outcomes in games played by no-policy-regret learning
algorithms. Policy equilibrium is a strictly larger class than correlated
equilibrium. As correlated equilibrium corresponds to calibrated best response
by each agent in each round, the policy equilibria that are not correlated
equilibria are not best responding in each round. We view these outcomes as
collusion. Hence, we view policy regret learning algorithms as problematic for
algorithmic pricing.

##  3\. Framework for Regulating Collusion

This section presents our definition of plausible non-collusion for sellers
and an empirical framework for auditing it. In our model, the seller has a
potentially private cost, which is static across rounds, and a potentially
private signal that correlates with the demand (and possibly the competition,
which might also correlate with the demand). Our framework is based on the
following sufficient condition for non-collusion:

###### Definition 3.0.

It is non-collusive for a seller to approximately best respond to their
competitive environment.

We may not know the seller’s cost and/or the seller’s beliefs on the
competitive environment. In fact, these beliefs on the environment may be
changing over time (though we assume that the sellers’ costs are stationary).
We will not require that the regulator knows anything about the seller’s costs
or beliefs. Instead, we will apply econometric principles of revealed
preference and revealed information. If a seller is approximately best
responding to their competitive environment, we can infer their cost and
whether or not they are consistently using information that reveals what
information they possess. For this reason, our empirical notion of non-
collusion is only plausible, i.e., there exists a cost and belief that is
consistent with the data for which the seller has approximately best
responded.

While it is plausible that a seller who has not approximately best responded
is not colluding, our framework will not be able to conclude that they have
not colluded. The existence of algorithms that can easily satisfy the
empirical definition we propose is evidence that it is permissible to hold
sellers to such a standard. It is also possible that if the regulator does not
have information on the costs of the sellers, then the sellers can collude to
act as though they have higher costs than they actually possess. The regulator
will not be able to detect such a collusion. It is also possible that sellers
have information about fluctuations in demand but have colluded to not use
this information; again, the regulator will not be able to detect such a
collusion. Our philosophy is that both of these possibilities exist already in
the regulation of collusion absent algorithms, and our focus is on solving new
challenges introduced by algorithms by essentially reducing them to the old
challenges of regulating collusion.

Our definition of non-collusion is unilateral by definition. A seller can
satisfy it regardless of the actions of other sellers. Specifically, it will
not be important to explicitly model the detailed actions of other sellers,
only the impact of those actions on the outcome of a seller. A seller’s
outcome, given the actions of other sellers and buyers, is a function
$x:\mathcal{P}\to[0,1]$ from their price $p\in\mathcal{P}$ to a quantity of
goods sold at this price, a.k.a., a demand function. We will assume that the
goods are normal goods, i.e., the demand function is monotonic where
increasing price results in (weakly) decreasing allocation.

We first give a static definition of non-collusion that applies to a single
round of pricing. We then generalize the definition to repeated pricing and
allow for statistical learning.

###### Definition 3.0.

A joint distribution on pairs of price and demand function
$\Pi\in\Delta(\mathcal{P}\times(\mathcal{P}\to[0,1]))$ is in _calibrated best-
response_ for a seller with cost $c$ if, conditioned on the seller’s price
$p$, $p$ is a best response:

(2) $\displaystyle p\in$
$\displaystyle\operatorname{argmax}_{p^{\prime}}\mathbb{E}_{(p,x)\sim\Pi}[(p^{\prime}-c)\,x(p^{\prime}))\,\mid\,p]$
$\displaystyle\forall\ p\in\mathcal{P}.$

Calibrated best response captures what it means to be a good algorithm and
allows the algorithm to use side information. Collusion is a potentially tacit
agreement between sellers to keep prices higher than those in each seller’s
best interest, given the prices of the other sellers. On the other hand, best
responding to the market and in particular what other sellers are doing is not
collusion. Calibration allows side information. If the side information is
useful, it manifests in distinct prices. The definition conditions the best
response on the prices. In other words, calibration requires an internal
consistency with respect to information that is revealed to be possessed in
variation of prices. It is easy to observe that the calibrated best response
is the unilateral version of correlated equilibrium. If all sellers’ prices
satisfy the calibrated best response then the joint distribution of prices is
a correlated equilibrium.

While it might seem that allowing correlation is allowing collusion, we argue
that, in fact, no reasonable definition of collusion can forbid correlation of
prices. Specifically, non-collusion is inherently about best responding to
market conditions. When consumer demand changes, the best response prices
change. Consumer demand is something that all sellers should be measuring and
it is correlated across sellers that are in price competition. Therefore,
correlation must be allowed. Calibration is a minimal allowance of correlation
and, in particular, it is agnostic to various potential sources of correlation
and does not require that they be explicitly modeled.

###### Definition 3.0.

A joint distribution on pairs of price and demand $\Pi$ is _non-collusive_ for
a seller $i$ if $\Pi$ satisfies the calibrated best response for $i$.

In repeated environments, where sellers are learning about what prices are
good, their prices might not be in the best response. However, as the learning
proceeds, the distance from the best response should diminish. This property
is captured by the following definition for the dynamic settings.

###### Definition 3.0.

An infinite sequence of pairs of price and demand $\\{(p^{t},x^{t})\\}^{t}$ is
_calibrated vanishing regret_ for a seller with cost $c$ if, the maximum
average per-round benefit of deviation over the set of price remaps
$\sigma:\mathcal{P}\to\mathcal{P}$, up to a given round, approaches zero as
the number of rounds goes to infinity:

(3)
$\lim_{T\to\infty}\max_{\sigma}\frac{1}{T}\sum_{t=1}^{T}u(\sigma(p^{t}),x^{t})-u^{t}(p^{t},x^{t})=0.$

where the payoff for a price $p$ on demand $x$ is $u(p,x)=(p-c)\,x(p)$

Calibrated vanishing regret and calibrated best response are related in that:

  * •

If we draw a sequence of prices from a joint distribution that satisfies
calibrated best response for the seller (and payoffs are bounded), then this
sequence of prices will satisfy calibrated vanishing regret for the seller;
and

  * •

in the limit with the number of rounds, the uniform distribution on price-
demand pairs (a.k.a. the empirical distribution) given by a sequence that
satisfies calibrated vanishing regret for the seller approaches a distribution
of prices in calibrated best responses for her.

These two properties give a unilateral version of an equivalence observed by
Foster and Vohra (1997): If the conditions hold for all sellers, then the
empirical distribution of the price sequence approaches a correlated
equilibrium.

Note that requiring calibration is important in our definition of non-
collusion. The weaker notion of vanishing external regret does not require
calibration, and it fails to rule out certain collusive behaviors when the
sellers have private information about the demand.

We demonstrate the problem with external regret with the numerical example
discussed in Section 2.1: Two sellers have cost $c_{1}=0.1$ and $c_{2}=0.2$
respectively and the buyer’s valuations are i.i.d. uniform over $[0,1]$.
However, Seller 1 now possesses private information. She can tell if an
incoming buyer has a low valuation for both sellers, i.e., $v_{1}\leq 0.5$ and
$v_{2}\leq 0.5$. Thus, she can post a different price for these buyers. Seller
1 can take advantage of this private information to collude with Seller 2
while still having non-positive external regret: Seller 2 posts a fixed price
$p_{2}=0.66$. Seller 1 posts $p_{1}^{L}=0.3$ when she knows the buyer has a
low valuation, and the same price $p_{1}=0.66$ as Seller 2 otherwise. However,
in this example, Seller 1 does have positive calibrated regret. She gets a
higher revenue by posting $p^{\prime}_{1}=0.6$ whenever she posts $p_{1}=0.66$
under the current strategy. In other words, the calibrated best response
condition fails to hold, i.e., conditional on her posting $p_{1}=0.66$,
$p_{1}=0.66$ is not a best response.

Our methods will not require the regulator to know the exact cost of a seller.
It will be sufficient to know that the seller’s cost is in a bounded range
$[\underaccent{\bar}{c},\bar{c}]$. The regulator will assume the seller’s
regret is the minimum one that achieves costs in this range.

###### Definition 3.0.

An infinite sequence of price profiles is _plausibly non-collusive_ for cost
range $[\underaccent{\bar}{c},\bar{c}]$ if that seller’s prices satisfy
calibrated vanishing regret for some cost
$c\in[\underaccent{\bar}{c},\bar{c}]$.

There is a long literature that develops good learning algorithms for pricing
with unknown demand, specifically by satisfying vanishing calibrated regret.
Algorithms that do not satisfy vanishing calibrated regret are making mistakes
in optimization that are apparent from the data. Given the information that
the algorithms have which is revealed in the prices, they are not optimizing
well enough that regret vanishes. We view this failure of optimization as a
mistake, and algorithms that make this mistake as not good.

###### Definition 3.0.

An _environment_ is a process that generates the sequence of demands based on
an algorithm’s past decisions, i.e., a sequence of functions mapping a history
of prices or distributions of prices, to a distribution of demand.

###### Definition 3.0.

An algorithm is _good_ for a cost $c$ in an environment if it satisfies
vanishing calibrated regret for cost $c$.

Calibrated vanishing regret cannot be directly observed in the data of a
learning algorithm because a) in practice, only data from a finite horizon can
be observed, and b) outcomes for counterfactual prices are not generally
known.

With data observed from a finite horizon of length $T$, the methodology of
property testing (Goldreich, 2010) can be used to check whether the expected
regret of a seller at $T$ is below a threshold, which approximates the
calibrated vanishing regret.

###### Definition 3.0.

The _expected regret at time $T$_ for a seller with cost $c$ against price
remapping $\sigma$ is

(4)
$ER^{T}(\sigma,c)=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p\sim\pi^{t}}[u(\sigma(p^{t}),x^{t})-u^{t}(p^{t},x^{t})]$

###### Definition 3.0.

The seller’s _plausible regret at time $T$_ is
$R^{T}_{\ast}=\min_{c\in[\underaccent{\bar}{c},\bar{c}]}\max_{\sigma}ER^{T}(\sigma,c)$.

Note that the seller’s plausible regret $R^{T}_{\ast}$ is always smaller than
her true regret $R^{T}=\max_{\sigma}ER^{T}(\sigma,c_{0})$ when her cost
$c_{0}\in[\underaccent{\bar}{c},\bar{c}]$.

While in round $t$, the seller uses price $p^{t}$ and obtains some utility for
it, to test if her regret is low, we need counterfactual outcomes for other
prices that could have been used, which we can only estimate based on the
data.

We measure the statistical complexity of a low plausible regret test by the
number of rounds $T$ that is sufficient to distinguish the two scenarios with
high confidence:

  * •

the seller’s true regret is below a given threshold (for sufficiently
auditable algorithms);

  * •

the plausible regret of the seller is far above the given threshold.

This gives a two-sided bound while allowing for a failure to identify the low
regret of algorithms that do not collect enough data to accurately make such a
determination.

###### Definition 3.0 (Sample complexity with auditability requirement).

A low plausible regret test has _sample complexity $\overline{T}$ with
auditability requirement $C$, confidence $1-\alpha$ and target regret level
$\overline{r}$_, if $\overline{T}$ is the minimum $T$ such that

  * •

if the seller’s true regret $R^{T}\leq\overline{r}$ and the transcript
satisfies the auditability requirement $C$, she passes the test with
probability at least $1-\alpha$;

  * •

if the plausible regret $R^{T}_{\ast}\geq 2\overline{r}$, the seller fails the
test with probability at least $1-\alpha$.

Since counterfactual demand for other prices that could have been used can not
be observed, an algorithm needs to keep additional data in the transcript to
demonstrate that it has low regret.

Algorithms might not be designed to record such information. Our goal for
auditing collusion is to allow any good algorithm to be used. Thus, we look
for tests for which any algorithm can be retrofitted to collect the data so
that, if their regret is low, they pass the test.

###### Definition 3.0.

A low plausible regret test with auditability requirement $C$ is _audit
compatible_ if the following holds: Given time horizion $T$, any algorithm $A$
that gives a seller regret at most $r(T)$ can be augmented to produce a
transcript that satisfies auditability requirement $C$ while giving the seller
regret no more than $O(r(T))+r_{C}(T)$ with $r_{C}(T)=O(1)$ in $T$.

To instantiate the above framework for auditing non-collusion, we must do the
following:

  * •

define a low plausible regret test;

  * •

prove that the test has good sample complexity;

  * •

define a black-box transcription algorithm for converting any good learning
algorithm into one that additionally produces an auditable transcript; and

  * •

prove that the test is audit-completable with a small loss (by analyzing the
transcription algorithm).

The next section completes these steps.

##  4\. Empirical Propensity Score Test

In this section, we give one instantiation of our framework for auditing the
collusion of one seller in dynamic imperfect price competition based on the
propensity score estimator, which is a standard method in multi-armed bandit
algorithms that have been developed for pricing.

Since we are now focusing on one particular seller, as we did in the previous
section, we drop the subscript $i$ from the notations for ease of reading and
use $x^{t}(\cdot)$ to denote the demand determined by the environment at round
$t$. We will also use _regret_ to refer to _expected regret_ for simplicity as
we are only concerned with the latter.

###### Definition 4.0.

The _propensity score transcript_ includes the sequences of

  * •

distributions $\\{\pi^{t}\\}_{t=1}^{T}$ produced by the seller’s algorithm,

  * •

the actual prices posted $\\{p^{t}\\}_{t=1}^{T}$, and,

  * •

the observed demand $\\{x^{t}(p^{t})\\}_{t=1}^{T}$, i.e., the outcomes of
posting price $p^{t}$ at round $t$, the seller experienced.

It is assumed that the price $p^{t}$ is actually drawn from the distribution
$\pi^{t}$. It is not hard for the seller to commit to doing so and convince
the regulator with modern cryptography.

With the price transcript described above, we define an estimated regret using
the propensity score estimator for the unobserved probabilities of sale for
counterfactual prices.

###### Definition 4.0.

Given a price transcript, the _propensity score estimator_ for $x^{t}(\cdot)$
is

(5)
$\tilde{x}^{t}(p)=\begin{cases}\frac{x^{t}(p^{t})}{\pi^{t}(p^{t})}&\mbox{if
$p=p^{t}$}\\\ 0&\mbox{otherwise}\end{cases}$

The propensity score estimator weights the outcome of each observation
inversely proportional to its rarity. Note that for any fixed $p$,
$\tilde{x}^{t}(p)$ is an unbiased estimator for $x^{t}(p)$ as
$\mathbb{E}_{p\sim\pi}[\tilde{x}^{t}(p^{t})]=x^{t}(p^{t})$. We define the
following _estimated regret_ for a seller with cost $c$ and against price
remapping $\sigma:\mathcal{P}\to\mathcal{P}$:

(6) $\displaystyle\widetilde{ER}^{T}(\sigma,c)$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p^{t}\sim\pi^{t}}[\tilde{u}^{t}(\sigma(p^{t}))-\tilde{u}^{t}(p^{t})]$
(7)
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p^{t}\sim\pi^{t}}[(\sigma(p^{t})-c)\cdot\tilde{x}^{t}(\sigma(p^{t}))-(p^{t}-c)\cdot\tilde{x}^{t}(p^{t})].$

and the _estimated regret_ is $\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)$. The
estimator estimates the true regret with the propensity score estimator for
demand.

We define _minimum exploration probability_ to quantify the exploration
demonstrated by a transcript.

###### Definition 4.0.

The _minimum exploration probability_ of a transcript is

(8)
$\underline{\pi}^{T}=\min_{p\in\mathcal{P},t\in\\{1,\dots,T\\}}\pi^{t}(p).$

To infer the cost of the seller, the regulator can compute the _estimated
rationalizable set_ à la Nekipelov et al. (2015):

$\displaystyle\widetilde{NR}$
$\displaystyle=NR\left(\\{\pi^{t}\\}_{t=1}^{T},\\{p^{t}\\}_{t=1}^{T},\\{\tilde{x}^{t}(\cdot)\\}\right)$
$\displaystyle=\biggl{\\{}(c,\epsilon):\forall\sigma,\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{p^{t}\sim\pi^{t}}[(\sigma(p^{t})-c)\cdot\tilde{x}^{t}(\sigma(p^{t}))$
$\displaystyle\phantom{=\biggl{\\{}(c,\epsilon):}-(p^{t}-c)\cdot\tilde{x}^{t}(p^{t})]\leq\epsilon\biggr{\\}}$
$\displaystyle=\left\\{(c,\epsilon):\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)\leq\epsilon\right\\}$

and find

(9)
$\tilde{c}\in\operatorname{argmin}_{c\in[\underaccent{\bar}{c},\bar{c}]}\left\\{\epsilon:(c,\epsilon)\in\widetilde{NR}\right\\}$

as the _estimated plausible cost_ for the seller. $\tilde{c}$ is the cost with
which the seller has the lowest estimated regret according to the data.
“Having cost $\tilde{c}$” is a plausible explanation of the observed data that
is most favorable in terms of estimated regret to the seller.

To test if a seller’s plausible regret $R^{T}_{\ast}\leq\overline{r}$ for
target regret level $\overline{r}$, the regulator conducts the following test
on a transcript defined in Definition 4.1.

###### Definition 4.0 (Empirical propensity score test).

Let the estimator
$\widetilde{R}^{T}=\min_{\tilde{c}\in[\underaccent{\bar}{c},\bar{c}]}\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c},$),
and upper confidence bound
$\operatorname{UCB}^{T}=\widetilde{R}^{T}+\delta^{T}$ where the upper margin
of error

$\delta^{T}=\frac{k\overline{p}}{T}\sqrt{2\log\left(\frac{2k^{2}}{\alpha}\right)\cdot\sum_{s=1}^{T}\left(\frac{1}{\pi^{t}(p)}+1\right)^{2}},$

with confidence $1-\alpha$, the number of price levels $k=|\mathcal{P}|$ and
maximum possible price $\overline{p}=\max_{p}|\mathcal{P}|$. For target regret
level $\overline{r}$,

  * •

pass: $\operatorname{UCB}^{T}\leq 2\overline{r}$;

  * •

fail: otherwise,

The accuracy of the propensity score regret estimator depends on how often the
seller’s algorithm explores. The estimation is accurate only when the
algorithm explores often enough so that enough information is revealed. The
upper margin of error term $\delta^{T}$ is added to the estimated regret in
order to account for the error given the exploration of the seller’s
algorithm. This ensures that when the transcript fails to demonstrate that the
algorithm producing it conducted enough exploration, it is hard for the seller
to pass the test. Hence, a seller with high plausible regret can not pass the
test for getting a low estimated plausible regret when the estimator is
actually unreliable.

###### Theorem 4.5.

The empirical propensity score test has sample complexity

(10)
$\overline{T}=O\left(\log\frac{k^{2}}{\alpha}\cdot\left(2\frac{k\overline{p}}{\overline{r}}\right)^{2}\cdot\left(\frac{1}{\underline{\pi}}+1\right)^{2}\right)$

with minimum exploration requirement $\underline{\pi}$, confidence $1-\alpha$
and target regret level $\overline{r}$, where $k=|\mathcal{P}|$ is the number
of price levels, and $\overline{p}=\max_{p}|\mathcal{P}|$ is the maximum
possible price.

As discussed above, to be able to pass the empirical propensity score test,
the seller’s algorithm needs to explore often enough so that the transcript
satisfies the minimum exploration requirement. The transcripts produced by an
algorithm that doesn’t explore often enough are not auditable using the
empirical propensity score test even if the algorithms are actually non-
collusive.

As long as an algorithm is robust enough in an environment, it can be modified
to produce auditable transcripts in the same environment by mixing it with a
small probability of uniform sampling of all the prices. An algorithm is
robust in its operating environment if a seller’s regret of running the
algorithm is approximately preserved in the same environment when the
algorithm’s decision is sometimes perturbed.

###### Definition 4.0.

Given $\epsilon\in[0,1]$, an algorithm $\hat{A}$ is an _$\epsilon$
-perturbation of algorithm $A$_ if, when $A$ outputs distribution $\pi$,
$\hat{A}$ mixes $\pi$ with some distribution $\tau$, outputting
$(1-\epsilon)\pi^{t}+\epsilon\tau$.

###### Definition 4.0.

An algorithm $A$ is _$\epsilon$ -perturbation robust in an environment for
time horizon $T$_ if the following holds: Let $r(T)$ be the regret of running
$A$ in the environment. For any $\epsilon$-perturbation $\hat{A}$ of $A$, the
regret of a seller running $\hat{A}$ in the environment is
$O(r(T))+\epsilon\cdot\rho(T)$, where $\rho(T)$ is $O(1)$ in $T$.

Good algorithms (as in Definition 3.7) in various environments are
automatically perturbation robust.

###### Lemma 4.8.

A good stochastic algorithm in a stochastic environment is perturbation robust
for any $T$.

###### Lemma 4.9.

A good adversarial algorithm in an arbitrary environment is perturbation
robust for any $T$.

###### Theorem 4.10 (Audit Compatibility).

Given any algorithm $A$ and minimum exploration requirement $\underline{\pi}$,
consider the algorithm $\hat{A}$, which at each round $t$

  * •

w.p. $1-\epsilon_{T}$, output $p$ drawn uniformly from $\mathcal{P}$

  * •

w.p. $\epsilon_{T}$, run $A$ and output its output

with $\epsilon_{T}=k\underline{\pi}$. Then,

  * •

The distribution $\pi^{t}$ produced by algorithm $\hat{A}$ has minimum
exploration probability at least $\underline{\pi}$.

  * •

If $A$ is perturbation robust in the environment and has regret $r(T)$, the
seller’s regret running $\hat{A}$ is no greater than
$O(r(T)+k\underline{\pi})=O(r(T))+O(1)$.

This concludes the auditing of non-collusion with the empirical propensity
score test.

Finally, we provide an analysis of the plausible regret estimator
$\widetilde{R}^{T}=\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})$ used in
the empirical propensity score test when the time horizon $T\to\infty$. The
following two theorems establish the asymptotic consistency of the estimator.

###### Lemma 4.11 (Upper-bound consistency).

Suppose the distributions $\\{\pi^{t}\\}_{t=1}^{T}$ produced by seller’s
algorithm satisfies

(11)
$\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}=o\left(T^{2}/\log(T)\right),$

then $\lim_{T\to\infty}R^{T}\leq 0$ implies
$\lim_{T\to\infty}\widetilde{R}^{T}\leq 0$ almost surely.

Lemma 11 shows that when the algorithm explores reasonably enough, if the true
regret vanishes then the estimated plausible regret vanishes as $T$ goes to
infinity.

###### Lemma 4.12 (Lower-bound consistency with error margin).

Suppose the regulator chooses a vanishing sequence of $\\{\alpha^{T}\\}_{T}$
satisfying $\alpha^{T}=\Theta(T^{-2})$, if $\lim_{T\to\infty}R^{T}>0$, then
$\lim_{T\to\infty}\left(\widetilde{R}^{T}+\delta^{T}\right)>0$ almost surely.

Lemma 4.12 shows that, when the regulator sets an increasing sequence of
confidence levels that tends to $1$ and grows slow enough, if the seller does
not have vanishing regret, the estimated regret for her cost plus the error
margin will not vanish in the long run.

From the above two lemmas, we obtain the following theorem showing that
$\widetilde{R}^{T}$ has desirable vanishing behaviors as $T\to\infty$.
Therefore, in the long run, algorithms with vanishing regret and explore
reasonably enough always pass the check, while algorithms with non-vanishing
plausible regret can not pass the check.

###### Theorem 4.13.

As $T\to\infty$, suppose the regulator chooses a vanishing sequence of
$\\{\alpha^{T}\\}_{T}$ satisfying $\alpha^{T}=\Theta(T^{-2})$,

  * •

if the seller’s algorithm satisfies

(12)
$\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}=o\left(T^{2}/\log(T)\right),$

the sum of the estimated plausible regret and the error margin
$\widetilde{R}^{T}+\delta^{T}$ vanishes when the seller’s true regret $R^{T}$
vanishes almost surely;

  * •

if seller’s plausible regret $R^{T}_{\ast}$ does not vanish then the sum of
the estimated plausible regret and the error margin
$\widetilde{R}^{T}+\delta^{T}$ does not vanish almost surely.

##  5\. Conclusion

In this work, we propose a definition for algorithmic non-collusion for
pricing algorithms and a framework for empirically auditing non-collusion
based on statistical tests on the data. Based on our framework, we give an
instantiation with propensity score estimators and provide its statistical
complexity.

The propensity score estimator for plausible maximum regret used in the
empirical propensity score test introduced in Section 4 makes a few
assumptions on the seller’s algorithm. The seller’s algorithm is required to
either distribute some amount of probabilities on each action at every round
or be robustly good in its operating environment. The accuracy and efficiency
depend reversely on the magnitude of these probabilities. This raises the
question of whether there are estimators without such restrictions.

One natural direction for future work is to find low plausible regret tests
with lower statistical complexity or looser auditability requirements for
transcripts.

Another interesting question is whether auditing non-collusion can be
formulated as a continuing process without the regulator deciding a fixed time
horizon $T$. Many results in this work are also asymptotic, which leaves open
the questions of how parameters such as target regret level should be chosen
in practice with finite time horizon.

###### Acknowledgements.

We thank James B. Speta for helpful comments on our initial draft and the
reviewers of the CSLaw’24 for helpful feedback and revision recommendations.
The authors are partially supported by the National Science Foundation
(CCF-1934931 and CCF-2216970).

## References

  * (1)
  * Abada and Lambin (2023) Ibrahim Abada and Xavier Lambin. 2023.  Artificial intelligence: Can seemingly collusive outcomes be avoided?  _Management Science_ (2023).
  * Arora et al. (2018) Raman Arora, Michael Dinitz, Teodor Vanislavov Marinov, and Mehryar Mohri. 2018.  Policy regret in repeated games.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Asker et al. (2023) John Asker, Chaim Fershtman, and Ariel Pakes. 2023\.  The impact of artificial intelligence design on pricing.  _Journal of Economics & Management Strategy_ (2023).
  * Assad et al. (2020) Stephanie Assad, Robert Clark, Daniel Ershov, and Lei Xu. 2020\.  Algorithmic pricing and competition: Empirical evidence from the German retail gasoline market.  (2020).
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 2002.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ 32, 1 (2002), 48–77.
  * Aumann (1974) Robert J Aumann. 1974\.  Subjectivity and correlation in randomized strategies.  _Journal of mathematical Economics_ 1, 1 (1974), 67–96.
  * Banchio and Mantegazza (2023) Martino Banchio and Giacomo Mantegazza. 2023.  Adaptive Algorithms and Collusion via Coupling. In _Proceedings of the 24th ACM Conference on Economics and Computation_ (London, United Kingdom) _(EC ’23)_. Association for Computing Machinery, New York, NY, USA, 208.  https://doi.org/10.1145/3580507.3597726
  * Banchio and Skrzypacz (2022) Martino Banchio and Andrzej Skrzypacz. 2022.  Artificial intelligence and auction design. In _Proceedings of the 23rd ACM Conference on Economics and Computation_. 30–31.
  * Bar-Yossef et al. (2002) Ziv Bar-Yossef, Kirsten Hildrum, and Felix Wu. 2002.  Incentive-compatible online auctions for digital goods.. In _Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms_ , Vol. 2. 964–970.
  * Beneke and Mackenrodt (2019) Francisco Beneke and Mark-Oliver Mackenrodt. 2019.  Artificial intelligence and collusion.  _IIC-international review of intellectual property and competition law_ 50 (2019), 109–134.
  * Benoit and Krishna (1985) Jean-Pierre Benoit and Vijay Krishna. 1985.  Finitely Repeated Games.  _Econometrica_ 53, 4 (1985), 905–922.
  * Biggio et al. (2013) Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. 2013\.  Evasion attacks against machine learning at test time. In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13_. Springer, 387–402.
  * Blum and Hartline (2005) Avrim Blum and Jason D. Hartline. 2005.  Near-Optimal Online Auctions. In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ (Vancouver, British Columbia) _(SODA ’05)_. Society for Industrial and Applied Mathematics, USA, 1156–1163.
  * Blum et al. (2003) Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. 2003\.  Online learning in online auctions. In _Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms_. 202–204.
  * Blum and Mansour (2007) Avrim Blum and Yishay Mansour. 2007.  From external to internal regret.  _Journal of Machine Learning Research_ 8, 6 (2007).
  * Calvano et al. (2020) Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo, and Sergio Pastorello. 2020.  Artificial intelligence, algorithmic pricing, and collusion.  _American Economic Review_ 110, 10 (2020), 3267–97.
  * Carlini and Wagner (2017) Nicholas Carlini and David Wagner. 2017.  Adversarial examples are not easily detected: Bypassing ten detection methods. In _Proceedings of the 10th ACM workshop on artificial intelligence and security_. 3–14.
  * Chassang et al. (2022) Sylvain Chassang, Kei Kawai, Jun Nakabayashi, and Juan Ortner. 2022.  Robust screens for noncompetitive bidding in procurement auctions.  _Econometrica_ 90, 1 (2022), 315–346.
  * Chassang and Ortner (2023) Sylvain Chassang and Juan Ortner. 2023.  Regulating Collusion.  15, 1 (2023), 177–204.  https://doi.org/10.1146/annurev-economics-051520-021936
  * den Boer et al. (2022) Arnoud V den Boer, Janusz M Meylahn, and Maarten Pieter Schinkel. 2022.  Artificial collusion: Examining supracompetitive pricing by Q-learning algorithms.  _Amsterdam Law School Research Paper_ 2022-25 (2022).
  * Desai and Kroll (2017) Deven R Desai and Joshua A Kroll. 2017.  Trust but verify: A guide to algorithms and the law.  _Harv. JL & Tech._ 31 (2017), 1.
  * Dijkstra (1970) Edsger W Dijkstra. 1970\.  On the reliability of programs.  In _Edsger Wybe Dijkstra: His Life, Work, and Legacy_. 359–370.
  * Foster and Vohra (1997) Dean P Foster and Rakesh V Vohra. 1997.  Calibrated learning and correlated equilibrium.  _Games and Economic Behavior_ 21, 1-2 (1997), 40\.
  * Friedman (1971) James W Friedman. 1971\.  A non-cooperative equilibrium for supergames.  _The Review of Economic Studies_ 38, 1 (1971), 1–12.
  * Gal (2023) Michal S Gal. 2023\.  Limiting Algorithmic Coordination.  _Berkeley Tech. LJ_ 38 (2023), 173.
  * Gautier et al. (2020) Axel Gautier, Ashwin Ittoo, and Pieter Van Cleynenbreugel. 2020\.  AI algorithms, price discrimination and collusion: a technological, economic and legal perspective.  _European Journal of Law and Economics_ 50, 3 (2020), 405–435.
  * Goldreich (2010) Oded Goldreich. 2010\.  Property testing.  _Lecture Notes in Comput. Sci_ 6390 (2010).
  * Harrington (2018) Joseph E Harrington. 2018\.  Developing competition law for collusion by autonomous artificial agents.  _Journal of Competition Law & Economics_ 14, 3 (2018), 331–363.
  * Harrington (2022) Joseph E Harrington. 2022\.  The effect of outsourcing pricing algorithms on market competition.  _Management Science_ 68, 9 (2022), 6889–6906.
  * Klein (2021) Timo Klein. 2021\.  Autonomous algorithmic collusion: Q-learning under sequential pricing.  _The RAND Journal of Economics_ 52, 3 (2021), 538–558.
  * Kleinberg and Leighton (2003) Robert Kleinberg and Tom Leighton. 2003.  The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In _44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings._ IEEE, 594–605.
  * Kovacic et al. (2011) William E Kovacic, Robert C Marshall, Leslie M Marx, and Halbert L White. 2011.  Plus factors and agreement in antitrust law.  _Michigan Law Review_ (2011), 393–436.
  * Kovacic and Shapiro (2000) William E Kovacic and Carl Shapiro. 2000.  Antitrust policy: A century of economic and legal thinking.  _Journal of Economic perspectives_ 14, 1 (2000), 43–60.
  * Kroll et al. (2017) Joshua Kroll, Joanna Huey, Solon Barocas, Edward Felten, Joel Reidenberg, David Robinson, and Harlan Yu. 2017.  Accountable Algorithms.  _University of Pennsylvania Law Review_ 165, 3 (2017), 633\.  https://scholarship.law.upenn.edu/penn_law_review/vol165/iss3/3
  * Nekipelov et al. (2015) Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. 2015\.  Econometrics for Learning Agents. In _Proceedings of the Sixteenth ACM Conference on Economics and Computation_ (Portland, Oregon, USA) _(EC ’15)_. Association for Computing Machinery, New York, NY, USA, 1–18.  https://doi.org/10.1145/2764468.2764522
  * _American Tobacco Co._ v.  _United States_ (1946) _American Tobacco Co._ v.  _United States_. 1946.  _US_ 1946 (1946), 781.
  * _Brooke Group Ltd._ v. _Brown & Williamson Tobacco Corp._ (1993) _Brooke Group Ltd._ v. _Brown & Williamson Tobacco Corp._ 1993\.  , 209 pages.
  * _Clamp-All Corp._ v. _Cast Iron Soil Pipe Institute_ (1988) _Clamp-All Corp._ v. _Cast Iron Soil Pipe Institute_. 1988.  , 478 pages.
  * _Ruckelshaus_ v.  _Monsanto Co_. (1984) _Ruckelshaus_ v.  _Monsanto Co_. 1984.  _US_ 467 (1984), 986.
  * _In re Text Messaging Antitrust Litigation_ (2015) _In re Text Messaging Antitrust Litigation_. 2015.  _F. 3d_ 782, No. 14-2301 (2015), 867.
  * _Interstate Circuit, Inc._ v.  _United States_ (1939) _Interstate Circuit, Inc._ v.  _United States_. 1939.  _US_ 306 (1939), 208.
  * Stigler (1964) George J Stigler. 1964\.  A theory of oligopoly.  _Journal of political Economy_ 72, 1 (1964), 44–61.
  * Stoltz (2005) Gilles Stoltz. 2005\.  _Incomplete information and internal regret in prediction of individual sequences_.  Ph.D. Dissertation. Université Paris Sud-Paris XI.
  * Werden (2004) Gregory J Werden. 2004\.  Economic Evidence on the Existence of Collusion: Reconciling Antitrust Law with Oligopoly Theory.  _Antitrust Law Journal_ 71, 3 (2004), 719–800.
  * Yao and DeSanti (1993) Dennis A Yao and Susan S DeSanti. 1993.  Game theory and the legal analysis of tacit collusion.  _The Antitrust Bulletin_ 38, 1 (1993), 113–141.

##  Appendix A Proofs

###  A.1. Theorem 10

###### Fact 0 (Azuma’s Inequality666From Michel Habib, Colin McDiarmid, Jorge
Ramirez-Alfonsin, Bruce Reed, (1998), Probabilistic Methods for Algorithmic
Discrete Mathematics Theorem 3.10. Proof see Theorem 13.4 of Michael
Mitzenmacher and Eli Upfal (2017) Probability and Computating ).

Given a sequence of random variables $\\{Y_{t}\\}_{t}$ and a filtration
$\\{\mathcal{F}_{t}\\}_{t}$ such that
$\mathbb{E}[Y_{t}\mid\mathcal{F}_{t-1}]=0$. If there exists $\\{d_{t}\\}$ such
that $|Y_{t}|\leq d_{t}$ for every $t$, then for any $\delta\geq 0$ and $T$:

(13)
$\Pr\left[\sum_{t=1}^{T}Y_{t}\geq\delta\right]\leq\exp\left(-\frac{\delta^{2}}{2\sum_{t=1}^{T}d_{t}^{2}}\right),\,\Pr\left[\sum_{t=1}^{T}Y_{t}\leq-\delta\right]\leq\exp\left(-\frac{\delta^{2}}{2\sum_{t=1}^{T}d_{t}^{2}}\right).$

###### Lemma A.1.

Let $c_{0}$ be seller’s true cost,
$\tilde{c}=\arg\min_{c}\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)$ be the
estimated plausible cost, $c_{\ast}=\arg\min_{c}\max_{\sigma}ER^{T}(\sigma,c)$
be the plausible cost, $k=|\mathcal{P}|$ be the number of price levels,
$\min_{p}\pi^{t}(p)=\min_{p}\pi^{t}(p)$ be the minimum among the probabilities
of posting each price level at round $s$ by the seller. We have

(14)
$\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\leq\max_{\sigma}ER^{T}(\sigma,c_{0})+\delta]\geq
1-k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right),$
(15)
$\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\geq\max_{\sigma}ER^{T}(\sigma,c_{\ast})-\delta]\geq
1-2k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)$

where

(16)
$d_{t}=\frac{1}{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)\overline{p}.$

###### Proof.

Observe that for any fixed $c$, since remapping $p$ to $p^{\prime}$ does not
affect the payoff of $p^{\prime\prime}\neq p^{\prime}$, we have

(17)
$\max_{\sigma}ER^{T}(\sigma,c)=\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\sum_{t=1}^{T}\frac{1}{T}\Big{(}\pi^{t}(p)\left(u^{t}(p^{\prime},c)-u^{t}(p,c)\right)\Big{)},$

and similarly

(18)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)=\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\sum_{t=1}^{T}\frac{1}{T}\Big{(}\pi^{t}(p)\left(\tilde{u}^{t}(p^{\prime},c)-\tilde{u}^{t}(p,c)\right)\Big{)}.$

Let

(19) $\displaystyle r^{t}_{p,p^{\prime}}(c)$
$\displaystyle=\frac{1}{T}\Big{(}\pi^{t}(p)\left(u^{t}(p^{\prime},c)-u^{t}(p,c)\right)\Big{)},\tilde{r}^{t}_{p,p^{\prime}}(c)$
$\displaystyle=\frac{1}{T}\Big{(}\pi^{t}(p)\left(\tilde{u}^{t}(p^{\prime},c)-\tilde{u}^{t}(p,c)\right)\Big{)},$
(20)
$R^{T}_{p,p^{\prime}}(c)=\sum_{t=1}^{T}r^{t}_{p,p^{\prime}}(c),\tilde{R}^{T}_{p,p^{\prime}}(c)=\sum_{t=1}^{T}\tilde{r}^{t}_{p,p^{\prime}}(c),$

we have

(21)
$\max_{\sigma}ER^{T}(\sigma,c)=\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime}}(c),$

and

(22)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)=\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(c).$

We first show that for the deviation $\Delta
R^{T}_{p,p^{\prime}}(c)=\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)$
for each $p,p^{\prime}$ is small with high probability using Azuma’s
Inequality.

Let $\Delta
r^{t}_{p,p^{\prime}}(c)=\tilde{r}^{t}_{p,p^{\prime}}(c)-r^{t}_{p,p^{\prime}}(c)$,
we have

(23) $\Delta R^{T}_{p,p^{\prime}}(c)=\sum_{t=1}^{T}\Delta
r^{t}_{p,p^{\prime}}(c),$

i.e., $\\{\Delta r^{t}_{p,p^{\prime}}(c)\\}_{t}$ as the $\\{Y_{t}\\}$ in the
formulation of Azuma’s Inequality given above.

Let $\mathcal{F}_{t}$ be the information available to the seller’s algorithm
up to $s$. We first show that $\mathbb{E}[\Delta
r_{p,p^{\prime}}^{t}(c)\mid\mathcal{F}_{t-1}]=0$, where. In fact,

(24) $\Delta
r^{t}_{p,p^{\prime}}(c)=\frac{1}{T}\cdot\pi^{t}(p)\Big{(}(p^{\prime}-c)(\tilde{x}^{t}(p^{\prime})-x^{t}(p^{\prime}))-(p-c)(\tilde{x}^{t}(p)-x^{t}(p))\Big{)}.$

For all $p\in\mathcal{P}$, by definition of $\tilde{x}^{t}(p)$, we have
$\mathbb{E}[\tilde{x}^{t}(p)\mid\pi^{t}(p)]=\mathbb{E}[\tilde{x}^{t}(p)\mid\mathcal{F}_{t-1}]=x^{t}(p)$
since $\pi^{t}(p)$ is determined by $\mathcal{F}_{t-1}$, as any algorithm can
only use information available up to $t-1$ to compute its distribution of
prices to post at round $s$. The same argument applies to $p^{\prime}$.
Therefore, by linearity of expectation, we have $\mathbb{E}[\Delta
r_{p,p^{\prime}}^{t}(c)\mid\mathcal{F}_{t-1}]=0$.

To apply Azuma’s inequality, we now figure out the bound of the magnitude of
each $\Delta r_{p,p^{\prime}}^{t}(c)$. For $p=p^{\prime}$ we have $\Delta
r_{p,p^{\prime}}^{t}(c)$, hence we assume below that $p\neq p^{\prime}$. Let
$\overline{p}=\max_{p\in\mathcal{P}}{p}$. By definition of
$\widetilde{x}^{t}$, we have:

  * •

When $p^{\prime}=p^{t}$,

(25) $\displaystyle\Delta
r_{p,p^{\prime}}^{t}(c)=\frac{1}{T}\cdot\pi^{t}(p)\Big{(}(p^{\prime}-c)\left(\frac{x^{t}(p^{\prime})}{\pi^{t}(p^{\prime})}-x^{t}(p^{\prime})\right)-(p-c)(0-x^{t}(p))\Big{)}.$

Since for any $p\in\mathcal{P}$, $0\leq\pi^{t}(p)\leq 1,0\leq x^{t}(p)\leq 1$
and $-\overline{p}\leq p-c\leq\overline{p}$, we have

(26) $|\Delta
r_{p,p^{\prime}}^{t}(c)|\leq\frac{1}{T}\left(\frac{1}{\pi^{t}(p^{\prime})}+1\right)\overline{p}.$

  * •

When $p=p^{t}$,

(27) $\displaystyle\Delta r_{p,p^{\prime}}^{t}(c)$
$\displaystyle=\frac{1}{T}\cdot\pi^{t}(p)\Big{(}(p^{\prime}-c)\left(0-x^{t}(p^{\prime})\right)-(p-c)\left(\frac{x^{t}(p)}{\pi^{t}(p)}-x^{t}(p)\right)\Big{)}$
(28)
$\displaystyle=\frac{1}{T}\left((p^{\prime}-c)(-\pi^{t}(p)x^{t}(p^{\prime}))-(p-c)(x^{t}(p)-\pi^{t}(p)x^{t}(p))\right).$

Since for any $p\in\mathcal{P}$, $0\leq\pi^{t}(p)\leq 1,0\leq x^{t}(p)\leq 1$
and $-\overline{p}\leq p-c\leq\overline{p}$, we have

(29) $|\Delta r_{p,p^{\prime}}^{t}(c)|\leq\frac{1}{T}\cdot 2\overline{p}.$

  * •

When $p^{\prime}\neq p^{t}$ and $p\neq p^{t}$,

(30) $\Delta
r_{p,p^{\prime}}^{t}(c)=\frac{1}{T}\cdot\pi^{t}(p)\Big{(}(p^{\prime}-c)\left(0-x^{t}(p^{\prime})\right)-(p-c)\left(0-x^{t}(p)\right)\Big{)}.$

Since for any $p\in\mathcal{P}$, $0\leq\pi^{t}(p)\leq 1,0\leq x^{t}(p)\leq 1$
and $-\overline{p}\leq p-c\leq\overline{p}$, we have

(31) $|\Delta r_{p,p^{\prime}}^{t}(c)|\leq\frac{1}{T}\cdot 2\overline{p}.$

By the fact that $\pi^{t}(p^{\prime})\leq 1$, we have

(32)
$\frac{1}{T}\left(\frac{1}{\pi^{t}(p^{\prime})}+1\right)\overline{p}\geq\frac{1}{T}\cdot
2\overline{p},$

therefore, in conclusion,

(33) $|\Delta
r_{p,p^{\prime}}^{t}(c)|\leq\frac{1}{T}\left(\frac{1}{\pi^{t}(p^{\prime})}+1\right)\overline{p}.$

In Azuma’s inequality, we can take $d_{t}$ to be

(34) $\frac{1}{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)\overline{p},$

which a uniform upper bound for $\Delta r_{p,p^{\prime}}^{t}(c)$ over all
$p,p^{\prime}$.

#### Upper Tail

For any fixed $c$, we have,

(35)
$\displaystyle\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)-\max_{\sigma}ER^{T}(\sigma,c)\geq\delta]$
(36) $\displaystyle=$
$\displaystyle\Pr\left[\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(c)-\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)\geq\delta\right]$
(37) $\displaystyle=$
$\displaystyle\Pr\left[\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(c)-\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)\geq\delta\right]$
(38) $\displaystyle\leq$ $\displaystyle\Pr\left[\exists
p\in\mathcal{P},\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(c)-\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)\geq\frac{\delta}{|\mathcal{P}|}\right]$
(39) $\displaystyle\leq$ $\displaystyle\Pr\left[\exists
p\in\mathcal{P},\max_{p^{\prime}\in\mathcal{P}}\left(\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)\right)\geq\frac{\delta}{|\mathcal{P}|}\right]$
(40) $\displaystyle=$ $\displaystyle\Pr\left[\exists p\in\mathcal{P},\exists
p^{\prime}\in\mathcal{P},\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)\geq\frac{\delta}{|\mathcal{P}|}\right]$

The first inequality comes from the simple fact that at least one element of
the sum must be no less than the average. Taking the union bound over all
$p,p^{\prime}\in\mathcal{P}$, we get

(41) $\Pr\left[\exists p\in\mathcal{P},\exists
p^{\prime}\in\mathcal{P},\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)\geq\frac{\delta}{|\mathcal{P}|}\right]\leq\sum_{p\in\mathcal{P}}\sum_{p^{\prime}\in\mathcal{P}}\Pr\left[\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)\geq\frac{\delta}{|\mathcal{P}|}\right].$

Note that $|\mathcal{P}|=k$, by Azuma’s inequality with $d_{t}$ defined as
above uniformly over all $p,p^{\prime}$, we have

(42)
$\Pr\left[\tilde{R}^{T}_{p,p^{\prime}}(c)-R^{T}_{p,p^{\prime}}(c)\geq\frac{\delta}{|\mathcal{P}|}\right]=\Pr\left[\Delta
R_{p,p^{\prime}}^{T}(c)\geq\frac{\delta}{k}\right]\leq\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right).$

Therefore, for any fixed $c$,

(43)
$\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)-\max_{\sigma}ER^{T}(\sigma,c)\geq\delta]\leq
k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right).$

Now we consider the relationship between
$\min_{c\in[\underaccent{\bar}{c},\bar{c}]}\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)$
and $\max_{\sigma}ER^{T}(\sigma,c_{0})$. By the fact that the estimated
plausible cost
$\tilde{c}=\arg\min_{c}\max_{\sigma}\widetilde{ER}^{T}(\sigma,c)$, we have

(44)
$\begin{split}&\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\leq\max_{\sigma}ER^{T}(\sigma,c_{0})+\delta]\\\
\geq&\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,c_{0})\leq\max_{\sigma}ER^{T}(\sigma,c_{0})+\delta]\\\
\geq&1-k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)\end{split}.$

#### Lower Tail

Let $c_{\ast}=\arg\min_{c}\max_{\sigma}ER^{T}(\sigma,c)$ be the plausible cost
of the seller. By definition of the estimated plausible cost $\tilde{c}$, we
have
$\max_{\sigma}ER^{T}(\sigma,c_{\ast})\leq\max_{\sigma}ER^{T}(\sigma,\tilde{c})$.
Therefore,

(45)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,c_{\ast})\geq\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,\tilde{c}),$

which implies

(46)
$\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,c_{\ast})\leq-\delta]\leq\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,\tilde{c})\leq-\delta].$

Note that since $\tilde{c}$ is a random variable, we can not simply treat it
as a fixed $c$ and obtain a probability bound using the exact same argument as
the upper tail for
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,\tilde{c})$.
Instead, we consider the event across all fixed $c$.

(47)
$\displaystyle\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})-\max_{\sigma}ER^{T}(\sigma,\tilde{c})\leq-\delta]$
(48) $\displaystyle=$
$\displaystyle\Pr\left[\sum_{p\in\mathcal{P}}\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(\tilde{c})-\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(\tilde{c})\leq-\delta\right]$
(49) $\displaystyle=$
$\displaystyle\Pr\left[\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(\tilde{c})-\max_{p^{\prime}\in\mathcal{P}}\tilde{R}^{T}_{p,p^{\prime}}(\tilde{c})\geq\delta\right]$
(50) $\displaystyle\leq$
$\displaystyle\Pr\left[\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(\tilde{c})-\tilde{R}^{T}_{p,p^{\prime\prime}}(\tilde{c})\geq\delta\right]$
(51) $\displaystyle\leq$ $\displaystyle\Pr\left[\exists
c\in[\underaccent{\bar}{c},\bar{c}],\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\geq\delta\right]$
(52) $\displaystyle\leq$ $\displaystyle 1-\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\leq\delta\right].$

Note that with similar arguments for reasoning about the upper tail, we have

(53) $\displaystyle\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\leq\delta\right]$
(54) $\displaystyle\geq$ $\displaystyle\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\forall
p\in\mathcal{P},\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\leq\frac{\delta}{|\mathcal{P}|}\right]$
(55) $\displaystyle=$ $\displaystyle\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\forall p\in\mathcal{P},\forall
p^{\prime\prime}\in\mathcal{P},R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\leq\frac{\delta}{|\mathcal{P}|}\right]$
(56) $\displaystyle=$ $\displaystyle\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\forall p\in\mathcal{P},\forall
p^{\prime\prime}\in\mathcal{P},\Delta
R^{T}_{p,p^{\prime\prime}}(c)\geq-\frac{\delta}{|\mathcal{P}|}\right]$ (57)
$\displaystyle\geq$ $\displaystyle\Pr\left[\forall p\in\mathcal{P},\forall
p^{\prime\prime}\in\mathcal{P},\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\underaccent{\bar}{c})\geq-\frac{\delta}{|\mathcal{P}|}\right)\wedge\left(R_{p,p^{\prime\prime}}^{T}(\overline{c})\geq-\frac{\delta}{|\mathcal{P}|}\right)\right]$

The last inequality follows from the following observation: $\Delta
R_{p,p^{\prime\prime}}^{T}(c)$ is linear in $c$, and hence its minimum over
$c\in[\underaccent{\bar}{c},\bar{c}]$ must be attained at either of the
endpoints, hence we have

(58) $\left[\Delta
R_{p,p^{\prime\prime}}^{T}(\underaccent{\bar}{c})\geq-\frac{\delta}{|\mathcal{P}|}\right]\cap\left[\Delta
R_{p,p^{\prime\prime}}^{T}(\overline{c})\geq-\frac{\delta}{|\mathcal{P}|}\right]\subseteq\left[\forall
c\in[\underline{c},\overline{c}],\Delta
R_{p,p^{\prime\prime}}^{T}(c)\geq-\frac{\delta}{|\mathcal{P}|}\right].$

Therefore, continuing from (52), we have

(59) $\displaystyle 1-\Pr\left[\forall
c\in[\underaccent{\bar}{c},\bar{c}],\sum_{p\in\mathcal{P}}\max_{p^{\prime\prime}\in\mathcal{P}}R^{T}_{p,p^{\prime\prime}}(c)-\tilde{R}^{T}_{p,p^{\prime\prime}}(c)\leq\delta\right]$
(60) $\displaystyle\leq$ $\displaystyle 1-\Pr\left[\forall
p\in\mathcal{P},\forall p^{\prime\prime}\in\mathcal{P},\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\underaccent{\bar}{c})\geq-\frac{\delta}{|\mathcal{P}|}\right)\wedge\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\overline{c})\geq-\frac{\delta}{|\mathcal{P}|}\right)\right]$
(61) $\displaystyle=$ $\displaystyle\Pr\left[\exists p\in\mathcal{P},\exists
p^{\prime\prime}\in\mathcal{P},\left(\Delta
R_{p,p^{\prime}}^{T}(\underaccent{\bar}{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\vee\left(\Delta
R_{p,p^{\prime}}^{T}(\overline{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\right].$

Taking the union bound, we have

(62) $\displaystyle\Pr\left[\exists p\in\mathcal{P},\exists
p^{\prime\prime}\in\mathcal{P},\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\underaccent{\bar}{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\vee\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\overline{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\right]$
(63) $\displaystyle\leq$
$\displaystyle\sum_{p\in\mathcal{P}}\sum_{p^{\prime\prime}\in\mathcal{P}}\left(\Pr\left[\Delta
R_{p,p^{\prime\prime}}^{T}(\underline{c})\leq-\frac{\delta}{|\mathcal{P}|}\right]+\Pr\left[\Delta
R_{p,p^{\prime\prime}}^{T}(\overline{c})\leq-\frac{\delta}{|\mathcal{P}|}\right]\right)$

Note that $|\mathcal{P}|=k$, by Azuma’s inequality with $d_{t}$ defined above
uniformly over all $p,p^{\prime\prime}$, we have for any fixed $c$

(64) $\Pr\left[\Delta
R_{p,p^{\prime\prime}}^{T}(c)\leq-\frac{\delta}{k}\right]\leq\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right).$

Since $\underaccent{\bar}{c},\overline{c}$ are fixed value, we have

(65) $\displaystyle\Pr\left[\exists p\in\mathcal{P},\exists
p^{\prime\prime}\in\mathcal{P},\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\underaccent{\bar}{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\vee\left(\Delta
R_{p,p^{\prime\prime}}^{T}(\overline{c})\leq-\frac{\delta}{|\mathcal{P}|}\right)\right]$
(66) $\displaystyle\leq$ $\displaystyle k^{2}\cdot
2\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right),$

and we conclude that

(67)
$\Pr[\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\geq\max_{\sigma}ER^{T}(\sigma,c_{\ast})-\delta]\geq
1-2k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)$

∎

#### Main Result of Theorem 10

Finally, we restate our theorem and give its proof: For a given confidence
$1-\alpha$, target regret level $\epsilon$ and minimum exploration probability
$\underline{\pi}$, when

(68) $T>\log\frac{2k^{2}}{\alpha}\cdot
2\left(\frac{k\overline{p}}{\epsilon/2}\right)^{2}\cdot\left(\frac{1}{\underline{\pi}}+1\right)^{2},$

the following holds:

  * •

If $\max_{\sigma}ER^{T}(\sigma,c_{0})\leq\epsilon$ and
$\underline{\pi}^{T}=\min_{t,p}\pi^{t}(p)\geq\underline{\pi}$, then with
probability at least $1-\alpha$,

(69) $\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})+\delta^{T}\leq
2\epsilon;$

  * •

if $\max_{\sigma}ER^{T}(\sigma,c_{\ast})>2\epsilon$, then with probability at
least $1-\alpha$,

(70) $\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})+\delta^{T}>2\epsilon.$

where

(71)
$\delta^{T}=\sqrt{\log\frac{2k^{2}}{\alpha}}\cdot\frac{\sqrt{2}k\overline{p}}{T}\cdot\sqrt{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}}.$

with probability $1-\alpha$.

###### Proof.

Assume that

(72) $T>\log\frac{2k^{2}}{\alpha}\cdot
2\left(\frac{k\overline{p}}{\epsilon}\right)^{2}\cdot\left(\frac{1}{\underline{\pi}}+1\right)^{2}.$

  * •

If $\max_{\sigma}ER^{T}(\sigma,c_{0})\leq\epsilon$ and
$\min_{s,p}\pi^{t}(p)\geq\underline{\pi}$, from (44) we have, with probability
at least $1-\alpha$

(73)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\leq\max_{\sigma}ER^{T}(\sigma,c_{0})+\delta^{T}\leq\epsilon+\delta^{T},$

which implies that

(74)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})+\delta^{T}\leq\epsilon+2\delta^{T}.$

Since $\min_{s,p}\pi^{t}(p)\geq\underline{\pi}$, we also have
$\delta^{T}\leq\epsilon/2$. Hence, with probability at least $1-\alpha$

(75) $\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})+\delta^{T}\leq
2\epsilon.$

  * •

If $\max_{\sigma}ER^{T}(\sigma,c_{\ast})>2\epsilon$, from (67) we have, with
probability at least $1-\alpha$,

(76)
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\geq\max_{\sigma}ER^{T}(\sigma,c_{\ast})-\delta^{T}>2\epsilon-\delta^{T},$

which implies that

(77) $\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})+\delta^{T}>2\epsilon.$

∎

#### Skipped Algebraic Steps

We elaborate the algebraic steps in the skipped in the proof immediately
above.

We first plug in

(78)
$d_{t}=\frac{1}{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)\overline{p},$

from (34) into (44) and (67). Solving for $\delta$ fixing other parameters,
i.e., for any given $T$, from (44) and (67) respectively, we get

(79)
$\delta^{T}_{u}=\sqrt{\log\frac{k^{2}}{\alpha}}\cdot\frac{\sqrt{2}k\overline{p}}{T}\cdot\sqrt{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}},$
(80)
$\delta^{T}_{l}=\sqrt{\log\frac{2k^{2}}{\alpha}}\cdot\frac{\sqrt{2}k\overline{p}}{T}\cdot\sqrt{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}}.$

$\delta^{T}$ is taken as $\max(\delta^{T}_{u},\delta^{T}_{l})$.

To see that
$\max_{\sigma}\widetilde{ER}^{T}(\sigma,\tilde{c})\leq\max_{\sigma}ER^{T}(\sigma,c_{0})+\delta^{T}$
and $\delta^{T}\leq\epsilon/2$ holds when
$\min_{s,p}\pi^{t}(p)\geq\underline{\pi}$ and

(81) $T\geq\log\frac{2k^{2}}{\alpha}\cdot
2\left(\frac{k\overline{p}}{\epsilon}\right)^{2}\cdot\left(\frac{1}{\underline{\pi}}+1\right)^{2}$

holds: Multiply both sides of the above inequality by $T$, we get

(82) $T^{2}\geq\log\frac{2k^{2}}{\alpha}\cdot
2\left(\frac{k\overline{p}}{\epsilon/2}\right)^{2}\cdot
T\left(\frac{1}{\underline{\pi}}+1\right)^{2}.$

Further, since for all $t=1,\dots,T$,
$\min_{p}\pi^{t}(p)\geq\min_{s,p}\pi^{t}(p)=\underline{\pi}^{T}\geq\underline{\pi}$,
we have

(83)
$T\left(\frac{1}{\underline{\pi}}+1\right)^{2}\geq\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2},$

hence

(84) $T^{2}\geq\log\frac{2k^{2}}{\alpha}\cdot
2\left(\frac{k\overline{p}}{\epsilon/2}\right)^{2}\cdot\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2},$

i.e.,

(85)
$T\geq\sqrt{\log\frac{2k^{2}}{\alpha}}\cdot\frac{\sqrt{2}k\overline{p}}{\epsilon/2}\cdot\sqrt{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}}.$

We get the desired results by plugging it into (44) and into $\delta^{T}$.

###  A.2. Lemma 11

For any $\delta>0$, Let $A_{T}$ be the event that
$\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{0})<\delta$. To show
that

(86)
$\Pr\left[\liminf_{s\to\infty}A_{T}\right]=\Pr\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{0})<\delta\,(e.v.)\right]=1,$

it suffices to show that

(87)
$\Pr\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{0})\geq\delta\,(i.o.)\right]=\Pr\left[\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{0})<\delta\,(e.v.)\right]^{C}\right]=0.$

By First Borel-Cantelli Lemma777cf. 2.7 of David Williams (1991), Probability
with Martingales and from (44), it suffices to have

(88)
$\sum_{T=1}^{\infty}\Pr\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{0})\geq\delta\right]=\sum_{T=1}^{\infty}k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)<\infty.$

It suffices to have

(89)
$k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)=k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}}\cdot\frac{T^{2}}{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}}\right)=O\left(\frac{1}{T^{2}}\right).$

as $\sum_{T=1}^{\infty}T^{-2}<\infty$. It suffices to have

(90)
$D(T)=\frac{T^{2}}{\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}}=\omega(\log
T),$

which is equivalent to

(91)
$\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}=o\left(T^{2}/\log(T)\right).$

#### Elaboration of (89) implied by (90)

In fact, by definition

(92) $D(T)=\omega(\log T)\Leftrightarrow\forall c>0,\exists T_{0},\mbox{ s.t.
}\forall T>T_{0},c\cdot D(T)>\log T.$

Take $c=\delta^{2}/4k^{2}$, we have for some $T_{0}$, for all $T>T_{0}$,

(93) $\frac{\delta^{2}}{2k^{2}}\cdot D(T)>2\log T,$

which implies that for all $T>T_{0}$,

(94) $k^{2}\exp\left(-\frac{\delta^{2}}{2k^{2}}\cdot
D(T)\right)<\frac{1}{T^{2}},$

which by definition implies (89).

###  A.3. Lemma 4.12

Given a sequence $\\{\delta^{T}\\}_{T}$, let $A_{T}$ be the event that
$\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{\ast})>-\delta^{T}$. To
show that

(95)
$\Pr\left[\liminf_{s\to\infty}A_{T}\right]=\Pr\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{\ast})>-\delta^{T}(e.v.)\right]=1,$

we follow the same steps as the proof of Lemma (11) and conclude that it
suffices to have

(96)
$\sum_{T=1}^{\infty}\Pr\left[\widetilde{ER}^{T}(\sigma,\tilde{c})-ER^{T}(\sigma,c_{\ast})\leq-\delta^{T}\right]=\sum_{T=1}^{\infty}2k^{2}\exp\left(-\frac{(\delta^{T})^{2}}{2k^{2}\sum_{t=1}^{T}d_{t}^{2}}\right)<\infty.$

Plugging in the definition of $\delta^{T}$, the summand becomes $\alpha^{T}$.
Hence, it suffices to have $\alpha^{T}=O(T^{-2})$.

###  A.4. Theorem 4.13

Note that when

(97)
$\sum_{t=1}^{T}\left(\frac{1}{\min_{p}\pi^{t}(p)}+1\right)^{2}=o\left(T^{2}/\log(T)\right),$

and $\alpha^{T}=\Theta(T^{-2})$, we have $\delta^{T}=o(1)$. Combining with the
Lemma (11) we obtain the statement of the first bullet point.

The second bullet point directly comes from Lemma (4.12).