# Online Learning in Betting Markets: Profit versus Prediction

Haiqing Zhu  Alexander Soen  Yun Kuen Cheung  Lexing Xie

###### Abstract

We examine two types of binary betting markets, whose primary goal is for
profit (such as sports gambling) or to gain information (such as prediction
markets). We articulate the interplay between belief and price-setting to
analyse both types of markets, and show that the goals of maximising bookmaker
profit and eliciting information are fundamentally incompatible. A key insight
is that profit hinges on the deviation between (the distribution of) bettor
and true beliefs, and that heavier tails in bettor belief distribution imply
higher profit. Our algorithmic contribution is to introduce online learning
methods for price-setting. Traditionally bookmakers update their prices rather
infrequently, we present two algorithms that guide price updates upon seeing
each bet, assuming very little of bettor belief distributions. The online
pricing algorithm achieves stochastic regret of $\mathcal{O}(\sqrt{T})$
against the worst local maximum, or $\mathcal{O}(\sqrt{T\log T})$ with high
probability against the global maximum under fair odds. More broadly, the
inherent trade-off between profit and information-seeking in binary betting
may inspire new understandings of large-scale multi-agent behaviour.

Online Learning, Regret, Betting Market, Prediction Market

##  1 Introduction

Betting on future events is interesting for at least two reasons: to elicit
and aggregate belief as done in online prediction markets, or to profit from
correct forecasts as done in traditional betting market. There is a vast
(albeit separate) literature about prediction and betting markets. A closer
examination prompts us to ask three questions. Can one describe prediction
market and traditional betting market using a shared mathematical model? Given
the many empirical studies on bettor and bookmaker strategies in betting
markets, what is a theoretical model for setting the book? Also, can
prediction-market-style online algorithms help profit-oriented bookmakers?

#### Related work.

Prediction markets (Wolfers & Zitzewitz, 2006) have had great algorithmic
success as information aggregators. Early development focused on how market
maker used _proper scoring rule_ to reward forecasters and encourage honest
predictions (Brier, 1950; Good, 1952; McCarthy, 1956; Savage, 1971; Gneiting &
Raftery, 2007). A landmark result is the automated market maker (Hanson, 2007)
using the _logarithmic market scoring rule_ (LMSR). The inherent connection of
LMSR to online optimisation led to various generalisations of LMSR in
algorithms and market structures (Chen & Pennock, 2007; Chen et al., 2008;
Agrawal et al., 2008; Guo & Pennock, 2009; Chen & Vaughan, 2010; Agrawal et
al., 2011; Abernethy et al., 2013; Frongillo et al., 2012; Othman et al.,
2013), and convergence analyses of the relevant dynamic processes (Frongillo &
Reid, 2015; Yu et al., 2022b).

For betting markets, Kelly betting (Kelly, 1956; Rotando & Thorp, 1992;
Busseti et al., 2016) is a prominent model and applicable to different domains
(Thorp, 2008). Levitt (2004)’s empirical work on bookmaker strategy identified
that better prediction ability and their systematic exploitation of bettor
biases as two main drivers of bookmakers’ profit. More recently, Yu et al.
(2022a) characterised the uniqueness of the equilibrium of the betting market
model under the special case that the odds are fair and no profit is earned.
Compared to the above, our work provides theoretical explanations of Levitt’s
findings based on a more general online betting model. Furthermore, we show
that bookmakers can earn higher profit not only by exploiting bettor biases,
but also by exploiting polarised bettor belief distributions that have heavy
tails. Remarkably, we show that such exploitation is not only feasible, but
can be done in an online setting with little knowledge of bettor belief
distribution beforehand.

Our profit-maximisation problem is distinct from other online learning
problems. For example, multi-armed bandits (Thompson, 1933; Slivkins et al.,
2019; Lattimore & Szepesvári, 2020) optimise profit for the (repeating) bettor
when the rate of return is unknown, whereas our problem maximises the
bookmaker profit when bettor belief distribution is unknown. The unknown
belief distribution constitute the uncertain component in both the objective
function and its gradient – but noisy estimates of both are used in our
algorithms. Focusing on gradient information, one could think of this problem
as between Online Convex Optimisation (Hazan et al., 2016) with known gradient
and Bandit Convex Optimisation problems (Hazan & Levy, 2014; Lattimore, 2024)
with no gradient available. Additionally, the optimisation objective here is
also uncertain and generally non-convex.

#### Our contributions.

We consider markets betting on binary outcomes. Table 1 summarises several key
concerns. Two choices determine the market setting: whether the bookmaker aims
to update their own belief – No (N) for traditional betting, and Yes (Y) for
prediction markets; and whether prices for the two outcomes are fair. Here
fair odds/prices Y means the implied event probabilities sum to one, and
unfair odds N means the bookmaker ignore this constraint to ensure profit.
Traditional betting markets can seek to maximise profit with either fair or
unfair odds, whereas prediction market seek to aggregate belief and invariably
uses fair odds tied to the estimates of the event probability. The setting of
belief update under unfair odds has contradictory effects – namely,
discouraging some bettor from participating but trying to elicit their belief
– and therefore is out of scope from this (and others’) work. This work
assumes the common Kelly model for bettor behaviour, which allows us to focus
on the properties and strategies of the bookmaker.

Table 1: An overview of market settings and key quantities in online learning.
Our contributions are highlighted in  green. $*$ with high probability. $\\#$
the algorithm is due to (Frongillo et al., 2012). $\dagger$ captures local
maxima and has stronger assumptions.

Market Setting | Market Properties
---|---
Goal |  Update Belief? |  Fair odds? |  Max Profit |  Online Learning | Regret
Profit | N | N | $>0$ | SA Sec 4 |  $\mathcal{O}(\sqrt{T})$†
Y | $>0$ | FTL Sec 5 |  $\mathcal{O}(\sqrt{T\log T})$∗
Prediction | Y | Y | $=0$ | Mirror Descent# |  $\mathcal{O}(\sqrt{T\log T})$∗

Our first set of results describe the conflict between profit and prediction
(in Sections 2 and 3). We show that bookmakers can expect positive profit in
both fair and unfair odds settings. In particular, the bookmaker setting a
price to exploit the difference between the bettors’ average belief and their
own will lead to profit. On the other hand, when the bookmaker set their own
belief to match the bettors’ average belief, the setting turns into a
prediction market with maximum profit being zero. Moreover, we show that
second order stochastic dominance relations across bettor belief distributions
implies the same ordering in profit – the bookmaker can obtain more profit
from heavier tails of the distributions. To the best of our knowledge, this is
the first formal result on bookmaker profit under unfair odds.

The next contribution is to introduce online learning to book-making,
resulting in two algorithms that optimise profit. Algorithm 1 (Section 4) is a
stochastic approximation algorithm (Mertikopoulos et al., 2020) to find
optimal prices with unfair odds. It does so with local gradient updates, and
achieves a regret of $\mathcal{O}(\sqrt{T})$ against a local maximum.
Algorithm 2 (Section 5) is a _Follow the Leader_ (Hazan et al., 2016)-type
algorithm in the fair odds setting. It computes a running estimate of average
bettor belief and uses the first-order analytical solution in the fair odds
setting to converge to globally optimal prices. We observe both algorithms
outperform the respective risk-balancing and logarithmic market scoring
baselines in empirical simulations, and are robust to different
initialisations (Section 6).

##  2 Betting Markets

Consider a betting market on binary outcomes, called A and B 111We choose to
focus on pre-determined binary outcomes in this work, e.g. home team winning
in a sporting event. Such setting is commonly used in prediction markets
(Beygelzimer et al., 2012; Frongillo et al., 2012; Wolfers & Zitzewitz, 2006).
We assume bookmakers are setting the price for A and B but not defining the
event, such as the point spread at which home team winning (Levitt, 2004). We
leave non-binary betting markets as future work. . A bookmaker sets a price
${a}$ for A and ${b}$ for B, with ${a},{b}\in(0,1]$ , respectively222Here
${a}$, ${b}$ represent price for unit return. Another commonly used, and
equivalent, representation is to express them in odds, which are $1/{a}$ and
$1/{b}$, respectively.. A bettor bets an amount $v$ on either outcome. If they
lose, $v$ goes to the bookmaker; if they win, ${v}/{a}$ or ${v}/{b}$ is paid
out to the bettor.

Denote the bookmaker’s estimate of the underlying probability of event A as
$g$.If the bookmaker and the bettors all took $g$ as their beliefs that A
occurs, then setting prices ${a}=g$ and ${b}=1-g$ would clear the market, with
no one expecting to make a profit – but this setting is neither realistic nor
interesting. The rest of this section considers the bettor-bookmaker dynamic
as a game, and addresses the following questions. If the individual belief of
the $t$-th bettor of A is $p_{t}\in[0,1]$, then how much would they bet given
the prices $({a},{b})$? Given such utility-maximizing bettors, what is the
expected profit for the bookmaker?

A table of key notation is presented in Appendix A. Proofs and additional
expositions are deferred to the appendix.

###  2.1 Kelly bettors and their optimal strategies

We consider _Kelly bettors_ (Kelly, 1956), indexed sequentially by
$t\in\\{1,\ldots,T\\}$. Each bettor possesses an initial wealth $w_{t}$ and
has an underlying belief $p_{t}$ that event A will occur, implying that belief
for event B is $q_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}1-p_{t}$.

A Kelly bettor bets an amount $v_{t}$ that maximises a utility representing
the expected logarithm of their wealth,

$v_{t}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\operatorname*{arg\,max}_{v\colon
v\geq 0}\left\\{\varphi_{t}^{{a}}(v)\vee\varphi_{t}^{{b}}(v)\right\\}.$ (1)

Here $\varphi_{t}^{{a}}(v)$ and $\varphi_{t}^{{b}}(v)$ are the expected log
wealth after bettor $t$ bets on event A or B, respectively. The inner $\max$
(via symbol $\vee$) indicate which side to bet on, while the outer max is over
the amount of the bet.

$\displaystyle\varphi_{t}^{{a}}(v)$
$\displaystyle=p_{t}\log\left(w_{t}+\frac{1-{a}}{{a}}v\right)+q_{t}\log(w_{t}-v);$
$\displaystyle\varphi_{t}^{{b}}(v)$
$\displaystyle=q_{t}\log\left(w_{t}+\frac{1-{b}}{{b}}v\right)+p_{t}\log(w_{t}-v).$

The first term in utility function $\varphi_{t}^{a}$ is the probability of A
happening $p_{t}$ times the log of the resulting wealth, with the profit from
the win being $\frac{1-{a}}{{a}}v$. The second term is the probability of B
happening $q_{t}$ times the log of initial wealth $w_{t}$ subtracting the loss
$v$. Similarly for utility $\varphi_{t}^{b}$ w.r.t. event B. Eq. 2 contains
the analytic solution for Problem (1) where the first case corresponds betting
on A and the second case corresponds to betting on B. See Appendix G for a
derivation and an illustration.

$v_{t}=\begin{cases}\frac{p_{t}-{a}}{1-{a}}\cdot
w_{t},&\text{if}~{}p_{t}>{a};\\\ 0,&\text{if}~{}1-{b}\leq p_{t}\leq{a};\\\
\frac{q_{t}-{b}}{1-{b}}\cdot w_{t},&\text{if}~{}q_{t}>{b}.\end{cases}$ (2)

The Kelly betting model is commonly applied in various fields, including
sports betting and gambling (Thorp, 2008), portfolio management (Thorp, 1975),
and stock market (Rotando & Thorp, 1992). It is proven to be asymptotically
optimal such that it maximises the long-term compounded returns (Kelly, 1956;
Algoet & Cover, 1988; Cover, 1999) . Despite its effectiveness, the Kelly
betting approach faces criticism for being overly aggressive (Busseti et al.,
2016) or, conversely, too conservative (Hsieh et al., 2016). To address these
issues, various alternative betting strategies have been proposed, such as
fractional (Davis & Lleo, 2013) and distributional robust (Sun & Boyd, 2018)
Kelly and modern portfolio theory (Markowitz, 1952). Our model is applicable
for fractional Kelly strategy by replacing the wealth distribution with a
joint distribution of wealth and fractions. Detailed analysis of these
alternative strategies is left for future research.

###  2.2 The bookmaker: maximising expected profit

Key moderation signals for betting markets are the prices $({a},{b})$, set by
the bookmaker. The setting when ${a}+{b}=1$ is called fair in prices and odds
(Wikipedia Contributors, 2024)333$a+b<1$ allows arbitrage – guaranteed profit
for bettors placing bets on both sides simultaneously – and hence not
applicable.; the setting ${a}+{b}>1$ is commonly used to guarantee bookmaker
profits. The amount ${a}+{b}-1$ is called overround or bookmaker margin. Given
prices $({a},{b})$ and a bookmaker’s belief $g$ of event A happening, one can
calculate their expected profit $u_{t}({a},{b})$ for a single bettor with unit
wealth ($w_{t}=1$), where the expectation is taken over bettor belief $p_{t}$:

$\displaystyle
u_{t}({a},{b})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)$
$\displaystyle\cdot\mathbb{E}\left[(p_{t}-{a})_{+}\right]$ (3)
$\displaystyle+\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)$
$\displaystyle\cdot\mathbb{E}\left[(q_{t}-{b})_{+}\right].$

Derivation of Eq. 3 is in Appendix H, which involves breaking down expected
payin minus payout according to event A or B actually happening using Eq. 2.
For both terms in Eq. 3 to be non-negative, the bookmaker would set
${a}\in[g,1]$ and ${b}\in[1-g,1]$. Eq. 3 is inherently connected to the notion
of _conditional value-at-risk_ (CVaR) (Rockafellar et al., 2000) in financial
markets due to both terms being functions of conditional expectations w.r.t.
the tails of belief distributions. An exposition of which is presented in
Appendix B. Note that Eq. 3 does not use the true event probability of A, but
only the bookmaker’s belief $g$, which leads to the following discussion.

#### The bookmaker’s belief versus event probabilities.

$g$ is a key quantity that influences the expected profit. In real-world
markets such as sports betting, bookmaker belief is known to be at least as
close to the true probability as the most competent bettor (Levitt, 2004).
Nonetheless, $g$ is not the true probability of event A. Eq. 3 is still
meaningful because it is an expectation from the bookmaker’s perspective.
Maximising Eq. 3 is also theoretically and practically sound, because even
when the bookmaker’s belief is uncertain, i.e., in the form of an interval
$(g_{-},g_{+})$ enclosing the ground-truth probability, we show that bookmaker
profit under true event probability is still positive, and that algorithms
proposed in Section 4 can maximise its lower bound with trivial changes to
incorporate $g_{-},g_{+}$. Details of this _imprecise belief lemma_ are in
Appendix C.

#### Profit under fair odds and prediction market.

When ${a}+{b}=1$, the expected profit function Eq. 3 simplifies to

$u_{t}({a},1-{a})=-\frac{({a}-g)({a}-\mathbb{E}\left[p_{t}\right])}{{a}(1-{a})}.$
(4)

Notice that the denominator is positive. Thus, the bookmaker makes a profit
iff ${a}$ is strictly between $g$ and $\mathbb{E}\left[p_{t}\right]$. In other
words, the bookmaker’s profit hinges on the aggregated bettor opinion
deviating from their own belief $g$.

When the bookmaker’s belief coincides with the aggregated bettor opinion, or
$g=\mathbb{E}\left[p_{t}\right]$ under fair odds, the optimal market price for
the bookmaker becomes exactly ${a}^{\star}=g$, leading to an expected profit
of zero – _i.e_., the price elucidates the mean belief of bettors. This
includes the setting of prediction markets (Beygelzimer et al., 2012; Wolfers
& Zitzewitz, 2006). This is surprising as the underlying dynamics of
prediction markets optimise a utility function entirely different from the
average profits. Indeed, the implicit utility function of the prediction
market is
${a}\mapsto-\mathrm{KL}(\mathbb{E}\left[p_{t}\right]\mathrel{\|}{a})$
(Frongillo et al., 2012, Corollary 1), which directly corresponds to
information elucidation.

##  3 Equilibria in Betting Markets

Notice that Eq. 2 depicts the behaviours of bettors when they maximise their
own utility; and Eq. 3 is the bookmaker’s possible utility when bettors act in
this optimal manner. A natural question arises of whether there exists an
equilibrium state where both the bettors and bookmaker’s utility are maximised
by a pair of prices $({a}^{\star},{b}^{\star})$ and investments $v_{t}$ (for
all $t\in\\{1,\ldots,T\\}$).

To consider this question, we first define the bookmaker’s total utility over
all bettors $\\{1,\ldots,T\\}$. This is simply defined as the sum of Eq. 3
weighted by expected wealth/budget of each bettor:

$u_{1:T}({a},{b})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{t=1}^{T}u_{t}({a},{b})\cdot\mathbb{E}\left[w_{t}\right].$
(5)

Here, we are using the assumption that the wealth $w_{t}$ and belief $p_{t}$
distributions for bettors are independent. We further assume the p.d.f. of
these distribution is differentiable almost everywhere. The function $u_{1:T}$
in Eq. 6 is generally non-concave when ${a}+{b}>1$ (via Eq. 3).

This utility function encodes a two-stage Stackelberg game (Von Stackelberg,
1934) between the bookmaker and the bettors. Indeed, with the knowledge that
the bettors make their optimal response simultaneously, the bookmaker (as the
Stackelberg leader) can make a pricing decision based on Eq. 5. When the
bookmaker makes an optimal pricing, a Stackelberg equilibrium is achieved.

######  Definition 3.1.

A Stackelberg equilibrium is achieved when the bettor with utility functions
$\varphi^{{a}^{\star}}$ and $\varphi^{{b}^{\star}}$ bets optimally with wager
from Eq. 1 and the bookmaker sets the price to maximise the expected profit
over a set of bettors assuming the bettors bet optimally

$({a}^{\star},{b}^{\star})=\operatorname*{arg\,max}_{({a},{b})\colon{a}+{b}\geq
1}~{}u_{1:T}({a},{b}).$ (6)

This type of equilibria can be categorised as Nash equilibria, as each
player’s strategy is optimal given the decisions of others. It should be noted
that, in general, the equilibria we consider differs from the typical market
equilibrium in economics (Arrow & Debreu, 1954), where supply equals demand.
There is a special case the types of equilibria are equivalent in binary
prediction market with fair odds, where marginal utility maximisation clears
the market (Beygelzimer et al., 2012).

The Stackelberg equilibrium is achieved as long as the expected profit of the
bookmaker is maximised since the Kelly betting rule Eq. 1 has analytical
solutions $v_{t}$ for each bettor. We note that such equilibrium is unique for
common distributions of bettors’ beliefs, see Appendix D for more details.
Lemma 3.2 establishes the existence of a Stackelberg equilibria and Lemma 3.3
shows that such equilibria will deviate from the bookmaker’s belief $g$.

######  Lemma 3.2.

For any fixed $T$, the profit function $u_{1:T}$ in Eq. 6 is upper-bounded,
and it admits at least one maximiser $({a}^{\star},{b}^{\star})\in(0,1)^{2}$.

######  Lemma 3.3.

Suppose the bettor belief distribution $f(x)>0$ for all $x\in(0,1)$, then for
prices with non-zero overround ${a}+{b}>1$, all maximisers
$({a}^{\star},{b}^{\star})$ of profit satisfies

$1-{b}^{\star}<g<{a}^{\star}.$

The combination of Lemmas 3.2 and 3.3 clarifies the claim that the optimal
prices, without fair odds, must necessarily deviate from the bookmaker’s
belief, which can be used to create a “house edge” in the prices. Proposition
3.4 presents a lower-bound of profit with the belief deviation between the
bookmaker and the bettors.

######  Proposition 3.4.

Let $u^{\star}$ denote the maximum utility corresponding to Eq. 6. Then
$u^{\star}\geq(g-\mathbb{E}\left[p_{t}\right])^{2}.$

Proposition 3.4 and Section 2.2 discussed the effect of mean bettor belief
$\mathbb{E}\left[p_{t}\right]$, the rest of this section establishes that a
larger second-order deviation (or more diversity in bettor beliefs) will
result in a larger profit. We first define second-order stochastic dominance
(SOSD), a well-established concept in economics, to formally describe bettor
diversity.

######  Definition 3.5 (Dentcheva & Ruszczynski (2003, Definition 2.1)).

Let $F_{1}$ and $F_{2}$ be c.d.f.s over the interval $(0,1)$. $F_{1}$ is SOSD
over $F_{2}$ if and only if $S_{1}(Z)<S_{2}(Z)$ for all $Z\in(0,1)$ and
$S_{1}(1)=S_{2}(1)$, where

$S_{i}(Z)=\int_{0}^{Z}F_{i}(z)\ \mathrm{d}\mathrm{}z,\quad i\in\\{1,2\\}.$

The following shows that ordering belief distributions by SOSD implies the
same order in the expected profits.

######  Proposition 3.6.

Fixing $g$, let $u_{1},u_{2}$ be profit functions Eq. 3 using preference
distributions $F_{1},F_{2}$, respectively. Assume the p.d.f.’s $f_{1},f_{2}$
satisfy $\mathrm{supp}(f_{1})=\mathrm{supp}(f_{2})=[0,1]$. If $F_{1}$ is SOSD
over $F_{2}$, then for any pair of prices ${a}\in(g,1)$ and ${b}\in(1-g,1)$,
we have

$u_{1}({a},{b})<u_{2}({a},{b});\quad u_{1}^{\star}<u_{2}^{\star},$

where $u_{1}^{\star}=\max_{{a},{b}}u_{1}({a},{b})$ and
$u_{2}^{\star}=\max_{{a},{b}}u_{2}({a},{b})$.

Proposition 3.6 matches the intuition that bookmakers can make more profit by
exploiting stubborn bettors on both ends of the preference spectrum, _i.e_.,
when the variance is larger or when the distribution has heavier tails.

Figure 1: _Left_ : Probability density function $f_{0.75,0.25,0.1}(p)$. _Right_ : Profit function, with profit-maximising prices $({a}^{\star},{b}^{\star})=(0.70710,0.63395)$ marked by the green point. Table 2:  Range of $({a}^{\star},{b}^{\star})$ for different values of $m$. $m$ | range of $\Delta_{1},\Delta_{2}$ | range of ${a}^{\star},{b}^{\star}$
---|---|---
$0.55$ | $(0~{},~{}0.05]$ | $(0.52506~{},~{}0.53353)$
$0.65$ | $(0~{},~{}0.15]$ | $(0.57677~{},~{}0.60608)$
$0.75$ | $(0~{},~{}0.25]$ | $(0.63395~{},~{}0.70710)$
$0.85$ | $(0~{},~{}0.15]$ | $(0.70420~{},~{}0.70710)$

#### Example: Profit maximisation and prediction aggregation are incompatible.

We construct a family of belief distributions whose means are all $0.5$, each
parameterised by $m$, $\Delta_{1},\Delta_{2}$. We assume the bookmaker’s
belief is $g=0.5$ too. We refer to $0.5$ as the “common belief”. The parameter
$m=\mathbb{E}\left[p_{t}\mid p_{t}\geq 0.5\right]$ lies between $0.5$ and $1$.
By design, $\mathbb{E}\left[p_{t}\mid p_{t}<0.5\right]=1-m$. When $m$ is
larger, the distribution is more polarised. The parameter
$\Delta_{1},\Delta_{2}$ lie between $0$ and $\min\\{m-0.5,1-m\\}$, which
represent how spread the distribution is over the regions $p_{t}\geq 0.5$ and
$p_{t}<0.5$ respectively. The distribution has the following p.d.f.:

$f_{m,\Delta_{1},\Delta_{2}}(p)=\begin{cases}\frac{1}{4\Delta_{1}},&\text{if
}p\in m\pm\Delta_{1};\\\ \frac{1}{4\Delta_{2}},&\text{if }p\in
1-m\pm\Delta_{2};\\\ 0,&\text{otherwise}.\end{cases}$

Under such belief distribution, the expected profit Eq. 3 admits a unique
maximizer $({a}^{\star},{b}^{\star})$. For several values of $m$, we compute
the possible range of ${a}^{\star}$ and ${b}^{\star}$ when
$\Delta_{1},\Delta_{2}$ vary. The result is summarised in Table 2, with its
derivation and explanation given in Appendix E.

For all values of $m$ in the table, the range of ${a}^{\star}$ and
${b}^{\star}$ does not include the common belief. Furthermore, as the
polarisation parameter $m$ increases, ${a}^{\star},{b}^{\star}$ can become as
large as $0.70710$, which is 41.4% more than the common belief. The prices do
not give useful indication of where the common belief locates.

When $\Delta_{1},\Delta_{2}$ are different, we may have skewed prices. In Fig.
1, we consider the case $m=0.75$, $\Delta_{1}=0.25$ and $\Delta_{2}=0.1$. The
prices are ${a}^{\star}=0.70710$ and ${b}^{\star}=0.63395$, which have a
relative difference of 11.5%. Consequently, even the prices after
normalization,
$(\frac{{a}^{\star}}{{a}^{\star}+{b}^{\star}},\frac{{b}^{\star}}{{a}^{\star}+{b}^{\star}})$,
do not give an accurate indication of the common belief.

With prices $({a}^{*},{b}^{*})$ maximising profit, a natural question is “how
to find them”? The online setting sets the stage for an answer, however, there
is a subtle (but important) difference in bettor and bookmaker behavior.
Bettors approaching the market at different times potentially face different
prices updated by the bookmaker, where bettors behave in accordance to
maximising their expected utility (in the Kelly sense) given the currently
available price. We present online algorithms to set the book in the next two
sections.

##  4 Online Learning under Unfair Odds

#### Setting.

We aim to find an optimal prices series $({a}_{t},{b}_{t})$ in an online
learning setting. Bettors $t\in\\{1,\ldots,T\\}$ arrive sequentially, each
making a bet in response to the current prices $({a}_{t},{b}_{t})$. We assume
that the bettors’ belief distributions are i.i.d., and denote the p.d.f. and
c.d.f. of their belief distributions as $f$ and $F$ respectively. The size of
each bet $v_{t}\geq 0$ in dollars / wealth and the side taken (either A or B)
are visible to bookmaker to update prices to $({a}_{t+1},{b}_{t+1})$. The
bookmaker aims to maximise an online version of their own expected profit with
the price series

$u_{1:t}({a}_{1:t},{b}_{1:t})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sum_{\tau=1}^{t}u_{t}({a}_{\tau},{b}_{\tau})\cdot\mathbb{E}\left[w_{\tau}\right].$
(7)

The bookmaker knows neither bettor belief $p_{t}$ nor its distribution $f(p)$
a-priori, but it will gather information as the bets come in. We assume that
bookmaker has an estimate of the average wealth of bettors
$\overline{W}_{t}\approx\mathbb{E}\left[w_{t}\right]$, which can be available
via, _e.g_., the online wallet of bettor $t$ on a betting platform or the
average behaviour among a set of bettors. We estimate the belief of bettor $t$
by:

$\widehat{p_{t}}=\begin{cases}{a}_{t}+(1-{a}_{t})\cdot\frac{v_{t}}{\overline{W}_{t}},&\textrm{if
the bet is on {A}};\\\
(1-{b}_{t})\cdot\left(1-\frac{v_{t}}{\overline{W}_{t}}\right),&\textrm{if the
bet is on {B}}.\end{cases}$ (8)

As the bettors are Kelly Bettors, by Eq. 2, $\widehat{p_{t}}$ is an unbiased
estimator of $\mathbb{E}\left[p_{t}\right]$ when
$\overline{W}_{t}=\mathbb{E}\left[w_{t}\right]$. However, the estimates
$\widehat{p_{t}}$ may not necessarily lie in $[0,1]$. To ensure that
$\widehat{p_{t}}$ is a valid probability, we can either assume bet size
$v_{t}\leq\overline{W}_{t}$ (Theorem 4.3), or “clip” the value of
$\widehat{p_{t}}$ to a subinterval of $[0,1]$ as in the fair odds setting
(Section 5).

#### Stochastic Approximation (SA).

The profit function Eq. 3 is non-concave in general, which presents a
challenge in finding the optimal prices. One might want to consider utilising
general first-order optimisation methods, _e.g_., gradient descent. However,
it is still challenging to directly apply these methods as the gradients
$\nabla u_{t}({a},{b})$ rely on the tail expectations, _e.g_., estimating the
c.d.f. $F({a})$ over a variety of prices ${a}$. Nevertheless, the first-order
optimality conditions of $u_{t}({a},{b})$ will become useful in deriving an
algorithm for online profit maximisation.

######  Theorem 4.1.

The first-order optimality condition could be reformulated as

$\left\\{\begin{aligned}
\Upsilon^{R}({a})&\stackrel{{\scriptstyle\mathrm{.}}}{{=}}G({a})+{a}-\mathbb{E}\left[p_{t}\mid
p_{t}\geq{a}\right]=0;\\\
\Upsilon^{L}({b})&\stackrel{{\scriptstyle\mathrm{.}}}{{=}}G({b})+{b}-\mathbb{E}\left[p_{t}\mid
p_{t}\leq 1-{b}\right]=0,\end{aligned}\right.$ (9)

where $G(x)=x(1-x)(x-g)/(x^{2}-2gx+g)$.

Eq. 9 describes potential local maxima – finding optimal prices is equivalent
to a stochastic root-finding problem. Similar problems have been extensively
studied and can be efficiently solved via stochastic approximation (SA)
algorithms (Robbins & Monro, 1951).

######  Definition 4.2 (Robbins & Monro (1951)).

For some twice differentiable function $h$, a stochastic approximation process
is a process $(X_{t})_{t\in\mathbb{N}}$ adapted to the filtration
$(\mathcal{F}_{t})_{t\in\mathbb{N}}$ that admits the following form

$X_{t+1}=X_{t}-\eta_{t+1}(h(X_{t})+M_{t+1}),$

where $(M_{t})_{t\in\mathbb{N}}$ is a random noise process satisfying
$\mathbb{E}\left[M_{t+1}\mid\mathcal{F}_{t}\right]=0$, and the sequence of
step sizes $(\eta_{t})_{t\in\mathbb{N}}$ satisfies
$\sum_{t\in\mathbb{N}}\eta_{t}=\infty$ and
$\sum_{t\in\mathbb{N}}\eta_{t}^{2}<\infty$. In addition, $h(X_{t})$ is
uniformly bounded over $t\in\mathbb{N}$.

A special case of the SA algorithm is when the function $h$ in Definition 4.2
corresponds to an unbiased estimator of a function’s gradient. Without random
noise, _i.e_. $M_{t}=0$ over all $t$, the process becomes stochastic gradient
descent (SGD) (Robbins & Monro, 1951; Bottou et al., 2018). When the random
noise is set to be sampled from a standard Gaussian, the process becomes
stochastic gradient Langevin dynamics (SGLD) (Borkar & Mitter, 1999; Welling &
Teh, 2011). Both SGD and SGLD can be perceived as stochastic root-finding
algorithms, aiming to locate points where an equation of “gradient equals
zero” is satisfied.

In this work, we aim to solve Eq. 9 using SA algorithms, summarised in
Algorithm 1. In particular, to set prices we run two instances of SA where we
set $h$ to be $\Upsilon^{R}({a})$ and $\Upsilon^{L}({b})$ as per Theorem 4.1.
In addition the random noise $M_{t+1}$ are set to be the deviation between an
estimate of the $t$-th bettor’s belief and the true mean tail means of the
bettor distribution, _i.e_., $M_{t+1}=\mathbb{E}\left[p_{t}\mid
p_{t}\geq{a}_{t}\right]-\widehat{p_{t}}$ and
$M_{t+1}=\mathbb{E}\left[q_{t}\mid q_{t}\geq{b}_{t}\right]-1+\widehat{p_{t}}$,
respectively. The resulting SA updates are given by Eqs. 10 and 11.

Algorithm 1 Online SA Algorithm

0: Wealth estimate $(\overline{W}_{t})_{t\in\mathbb{N}}$, ground-truth
estimate $g$, initial price $({a}_{1},{b}_{1})$.

1: for each bettor entering the market at time $t$ do

2: Receive the bet placed by the bettor $v_{t}$.

3: Estimate bettor belief $\widehat{p_{t}}$ with $({a}_{t},{b}_{t})$ via Eq.
8.

4: if bettor $t$ bets for A then

5: Update the price ${a}_{t+1}$ as follows:
$\displaystyle{a}_{t+1}={a}_{t}-\eta_{t+1}({a}_{t}+G({a}_{t})-\widehat{p_{t}}).$
(10)

6: else if bettor $t$ bets for B then

7: Update the price ${b}_{t+1}$ as follows:
$\displaystyle{b}_{t+1}={b}_{t}-\eta_{t+1}({b}_{t}+G({b}_{t})-1+\widehat{p_{t}}).$
(11)

8: end if

9: end for

#### Convergence.

Under mild assumptions, Algorithm 1 converges to a local maximum of the
bookmaker’s profit, which is formally stated in the following theorem.

######  Theorem 4.3.

Suppose that

  * •

The probability density function $f$ is differentiable and the support of $f$
satisfies $\mathrm{supp}(f)=[0,1]$;

  * •

Bettors will not place bets exceeding the estimated wealth, _i.e_.,
$v_{t}\leq\overline{W}_{t}$;

  * •

The set of solutions to Eq. 9 is finite;

  * •

For $i\in\\{L,R\\}$ and for any $p$ satisfying $\Upsilon^{i}(p)=0$, there
exists a neighbourhood $\mathcal{N}$ of $p$ such that $\Upsilon^{i}(z)(z-p)<0$
for all $z\in\mathcal{N}\setminus\\{p\\}$.

Then for sufficiently large $m,\gamma>0$, Algorithm 1 will almost surely
converges to a local maximum of $u$ when using a learning rate
$\eta_{t}={\gamma}/{(t+m)}$.

The second assumption in Theorem 4.3 ensures us that the individual point-wise
predictions of bettor’s beliefs $v_{t}/\overline{W}_{t}$, for any $t$, lies in
the interval $[0,1]$. This further ensures $\widehat{p_{t}}\in[0,1]$ as per
Eq. 8. For the last assumption, it is also sufficient to have the first
derivatives of $\Upsilon^{R},\Upsilon^{L}$ (assuming differentiability) to be
non-zero at the critical points.

The proof of Theorem 4.3 can be divided into the following key steps. First,
by exploiting the bettors’ strategies, we demonstrate that the SA algorithm is
well-defined according to Definition 4.2. Second, by identifying the explicit
Lyapunov function of the process, we show that the SA dynamic almost surely
converges to a critical point of $u$. Third, we adopt the saddle point
avoidance results of Pemantle (1990) to rule out the possibility that the
dynamic converges to critical points other than local maximisers.

Regarding the efficiency of the algorithm, we establish an
$\mathcal{O}(1/\sqrt{T})$ convergence against the worst maximiser of $u_{t}$.

######  Theorem 4.4.

Suppose that the assumptions of Theorem 4.3 holds. Let
$({a}^{\sharp},{b}^{\sharp})$ be the worst local maximiser of $u_{t}$,

$({a}^{\sharp},{b}^{\sharp})=\operatorname*{arg\,min}_{({a},{b})\in\mathcal{W}}u_{t}({a},{b}),$

where $\mathcal{W}$ is the set of all local maximisers of $u_{t}$. Then, there
exists a finite constant $L_{u}>0$ which is dependent on $u_{t}$, such that,
for sufficiently large $T\in\mathbb{N}$, we have

$\mathbb{E}\left[u_{T}({a}_{T},{b}_{T})\right]\geq
u_{t}({a}^{\sharp},{b}^{\sharp})-7L_{u}T^{-1/2}.$

In particular, when the maximiser is unique,
$({a}^{\sharp},{b}^{\sharp})=({a}^{\star},{b}^{\star})$ is the global
maximiser and hence the equilibrium price. In our analysis, we note that the
process will converge to one of the local maximisers, which is guaranteed to
have a neighbourhood where $u_{t}$ is locally Lipschitz smooth and concave. By
the fact that the process will be in one of such neighbourhoods when $t$ is
large enough, we could characterise the convergence rate under such
assumptions. The detailed analysis is given in Appendix L. Moreover, by
conducting the non-escape analysis, similar to Mertikopoulos et al. (2020,
Theorem 4), we obtain a stronger result which clarifies which local maximiser
the process converges to.

######  Theorem 4.5.

Suppose that the assumptions of Theorem 4.3 holds. For any constant
$\delta<\frac{1}{2}$, let $({a}^{\flat},{b}^{\flat})$ be one of the local
maximisers of $u_{t}$. Then there exist neighbourhoods $\mathcal{U}_{1}$ and
$\mathcal{U}$ of $({a}^{\flat},{b}^{\flat})$ such that, if
$({a}_{1},{b}_{1})\in\mathcal{U}_{1}$, the event

$\Omega_{\mathcal{U}}=\\{({a}_{t},{b}_{t})\in\mathcal{U}~{}\text{for
all}~{}t\in\mathbb{N}\\}$

occurs with probability at least $1-\delta$. Moreover, there exists a finite
constant $L_{u}>0$ which is dependent on $u_{t}$, such that, for sufficiently
large $T\in\mathbb{N}$, we have

$\mathbb{E}\left[\left|u_{t}({a}_{T}^{\flat},{b}_{T}^{\flat})-u_{t}({a}_{T},{b}_{T})\right|~{}\mid~{}\Omega_{\mathcal{U}}\right]\leq
4\sqrt{6}L_{u}T^{-1/2}.$

Our proof mainly follows Mertikopoulos et al. (2020) but addresses several
additional technical difficulties. For example, our SA algorithm does not
perform the exact gradient step and every bettor does not cause prices to be
updated (they however will contribute to the total time complexity).

#### Regret.

Although the previous results characterise the limiting case when $T$ is
large, we also want to characterise the cumulative penalty across all
timesteps/bettors $t\in\\{1\ldots T\\}$. This can be concretely described by
_regret_ (Hazan & Kale, 2014; Hazan et al., 2016). In the case of our bettors
and bookmaker profits, we define stochastic regret in the following.

######  Definition 4.6.

Given a sequence of bookmaker prices
$({a}_{1},{b}_{1}),\ldots,({a}_{T},{b}_{T})$, the stochastic regret against
$({a},{b})$ is

$\textsc{Regret}(T,{a},{b})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}u_{1:T}({a},{b})-u_{1:T}({a}_{1:T},{b}_{1:T}).$
(12)

Standard stochastic regret (Hazan & Kale, 2014, Section 2.2) is given by
$\textsc{Regret}(T,{a}^{\star},{b}^{\star})$ with
$({a}^{\star},{b}^{\star})=\operatorname*{arg\,max}_{{a},{b}}u_{t}({a},{b})$.
Since $u_{t}({a}_{t},{b}_{t})$ is bounded for all $t\in\mathbb{N}$, the
following result on local stochastic regret can be obtained immediately.

######  Corollary 4.7.

Suppose that the assumptions of Theorem 4.3 holds. Then we have

$\mathbb{E}\left[\textsc{Regret}(T,{a}^{\flat},{b}^{\flat})\mid\Omega_{\mathcal{U}}\right]=\mathcal{O}(\sqrt{T}).$

The expected regret without conditioning can also be derived as
$\mathcal{O}(\sqrt{T})$, as per Theorem 4.5 and its assumptions.

##  5 Online Learning under Fair Odds

Algorithm 2 Follow The Leader

0: Wealth estimate $(\overline{W}_{t})_{t\in\mathbb{N}}$, ground-truth
estimate $g$, clipping value $\tau\in(0,0.5)$, initial price ${a}_{1}$.

1: for each bettor entering the market at time $t$ do

2: Receive the bet placed by the bettor $v_{t}$.

3: Estimate bettor belief $\widehat{p_{t}}$ with $({a}_{t},1-{a}_{t})$ via Eq.
8

4: Update the estimate of expected belief as  $\displaystyle\overline{p_{t}}$
$\displaystyle=\frac{t-1}{t}\cdot\overline{p}_{t-1}+\frac{1}{t}\cdot\widehat{p_{t}}.$
(13)

5: Following Eq. 14, update the price with a clipped cumulative average:
${a}_{t+1}=\psi\left(\mathrm{clip}(\overline{p_{t}};\tau,1-\tau)\right).$

6: end for//
$\mathrm{clip}(x;l,u)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}((x\vee l)\wedge
u)$ for $l<u$

In this section, we assume that the bookmaker maintains fair odds ${a}+{b}=1$.
We note that Algorithm 1 cannot be directly used for the fair odds case due to
two reasons. . First, prices (and their optimal value) must be restricted to a
region $({a}_{t},{b}_{t})\in(g,1)\times(1-g,1)$ in Theorem 4.3. Second, the
convergence of Theorem 4.3 relies on the prices $({a}_{t},{b}_{t})$ staying
within a region where profit $u_{t}({a}_{t},{b}_{t})$ is lower-bounded. We do
not have the same control to restrict ${a}$ under fair odds from reaching the
boundaries of $[0,1]$, where the gradient of the profit ${a}\mapsto
u_{t}({a},1-{a})$ can be infinite. Instead, we exploit the overall concavity
of the profit function to adapt a _follow the leader_ (FTL) (Hazan et al.,
2016) algorithm for fair odds, as presented in Algorithm 2. Although our FTL
algorithm has worse asymptotic regret bounds than Algorithm 1, it will have
better convergence conditions – importantly, FTL’s convergence is to the
global maxima unlike Algorithm 1.

#### Follow The Leader (FTL).

As we have fair odds, ${b}_{t}=1-{a}_{t}$, our goal is to maximise profit via
the map ${a}\mapsto u_{t}({a},1-{a})$, which is concave, see Eq. 4. Thus, by
taking the first-order optimality condition of $u_{t}({a},1-{a})$, we get the
following closed-form expression of the (unique) maxima
${a}^{\star}=\psi(\mathbb{E}\left[p_{t}\right])$, where

$\psi(p)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\frac{\sqrt{gp}}{\sqrt{gp}+\sqrt{(1-g)(1-p)}}.$
(14)

Notably, the optimal price Eq. 14 does not require knowledge of the entire
belief distribution $f$ – only the first moment $\mathbb{E}\left[p_{t}\right]$
is needed. As a result, to find the optimal price ${a}^{\star}$ in an online
setting, we only need to obtain an online estimate of the expected bettor’s
belief $\mathbb{E}\left[p_{t}\right]$.

To estimate the $\mathbb{E}\left[p_{t}\right]$, we utilise a cumulative
average – taking into account all prior bets $t^{\prime}<t$ – which is
equivalent to making the optimal estimate of
${a}_{t}^{\star}=\psi(\mathbb{E}\left[p_{t}\right])$ in hindsight, _i.e_., a
FTL algorithm (Hazan et al., 2016). To ensure that our cumulative average of
bettor belief does not fall outside of $[0,1]$, we clip each $\widehat{p_{t}}$
to a region $[\tau,1-\tau]$ for $\tau\in(0,0.5)$.

Figure 2: Simulation of Algorithm 1 with 100,000 bettors. _Left_ : The
distribution of bettors’ beliefs, unknown to bookmaker. _Middle_ : Regrets
over 100,000 iterations, comparing Algorithm 1 under different initialisation
to risk-balancing. Markers “$\times$” indicate number of iterations on a log-
scale $\\{10^{1},\ldots,10^{5}\\}$. _Right_ : Contour plot of
$\delta(a,b)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}u_{1:T}({a}^{\star},{b}^{\star})-u_{1:T}({a},{b})$
where $T=10^{5}$, darker colours means closer to maximum profit.

#### Convergence.

We are interested in analysing how the learned prices $({a}_{T},{b}_{T})$
learned by Algorithm 2 converges to the optimal prices
$({a}^{\star},{b}^{\star})$ w.r.t. utility $u$. A stochastic convergence
result for Algorithm 2 can be obtained by considering the local Lipschitz
properties of functions.

######  Theorem 5.1.

Suppose that both $g$ and $\mathbb{E}\left[p_{t}\right]$ lie in the open
interval $(\tau,1-\tau)$ and $w_{t}$ is uniformly bounded above by an absolute
constant, almost surely. Suppose $({a}_{t},{b}_{t})_{t\in\mathbb{N}}$ is the
price sequence generated by Algorithm 2. Then there exists a finite $L>0$ such
that for any $\delta>0$ and for sufficiently large $T\in\mathbb{N}$, we have

$u_{t}({a}_{T},{b}_{T})\geq
u_{t}({a}^{\star},{b}^{\star})-LT^{-1/2}\sqrt{\log(1/\delta)},$

with probability at least $1-\delta$.

The constant $L$ in Theorem 5.1 corresponds to a product local Lipschitz
constants of $u$ and $\psi$ when restricting $\overline{p_{t}}$ to
$(\tau,1-\tau)$. In general, a larger $\tau$ will result in a larger $L$.

#### Regret.

Theorem 5.1 can be restated w.r.t. a high probability regret bound (Bubeck et
al., 2012; Bartlett et al., 2008).

######  Corollary 5.2.

Suppose that the assumptions of Theorem 5.1 holds. Then with probability
$1-\delta$, we have

$\textsc{Regret}(T,{a}^{\star},{b}^{\star})=\mathcal{O}(\sqrt{T\log T}).$

The proof is immediate from a union bound, yielding sublinear regret. Although
the regret when compared to Algorithm 1 is worse by a factor of
$\mathcal{O}(\sqrt{\log T})$ (Corollary 4.7) there are notable differences
which make the FTL bound preferable. For instance, in Theorem 5.1 convergence
is w.r.t. to the global optimal prices $({a}^{\star},{b}^{\star})$ whilst
Theorem 4.5 is only w.r.t. a local maxima. Furthermore, in Theorem 5.1 we do
not need to condition our price sequence on $\Omega_{\mathcal{U}}$ to achieve
a convergence rate.

As the fair odds setting of betting markets coincides with prediction markets
when $g=\mathbb{E}\left[p_{t}\right]$, one may want to consider FTL’s regret
in comparison to prediction markets. From Frongillo et al. (2012, Corollary
1), we know that prediction market dynamics follow online mirror descent
updates, where the maximised function is a KL-divergence
${a}\mapsto-\mathrm{KL}(\mathbb{E}\left[p_{t}\right]\mathrel{\|}{a})$. The
prediction market’s regret (Duchi et al., 2010) w.r.t. this KL-utility can be
shown to be $\mathcal{O}(\sqrt{T\log T})$ – taking appropriate step sizes
(Hazan et al., 2016, Chapter 5.3) and a union bound over $\delta/T$ steps,
similar to Corollary 5.2 – matching the FTL regret. As such, despite the
difference in utilities being maximised, our regret matches automated market
makers derived from strictly convex functions (Abernethy et al., 2013).

##  6 Empirical Results

We illustrate the efficiency of Algorithms 1 and 2 empirically444Code and data
to reproduce results are found at: https://github.com/haiqingzhu543/Betting-
Market-Simulation-2024.. An advantage of our theoretic results is that they
hold for a wide range of bettor belief distributions, only requiring weak
assumptions. Our empirical analysis aims to elucidate how different properties
of the belief distributions (not captured by theory) change the performance of
our algorithms.

#### Settings.

We set the bookmaker’s belief $g=0.5$ throughout all simulations. We generate
$10^{5}$ Kelly bettors with a mixture of beliefs – one Gaussian for event A
and B respectively, followed by a sigmoid function to ensure that beliefs lie
within (0, 1), _i.e_. $p_{t}=\text{sigmoid}(s_{t}),~{}{t=1,\ldots,10^{5}}$
with $s_{t}\sim 0.25\cdot\mathcal{N}(2,1)+0.75\cdot\mathcal{N}(-1,1)$. The
histogram of the distribution is in Fig. 2 (Left). We note that the
distribution has one mode on either side of $g$ but is not symmetric around
$g$. We compute regret using Definition 4.6, where the optimal price
is$({a}^{\star},{b}^{\star})=\operatorname*{arg\,max}_{{a}+{b}\geq
1}u_{t}({a},{b})$ generally, and under fair odds
${a}^{\star}=\operatorname*{arg\,max}_{{a}\in(0,1)}u_{t}({a},1-{a})$.

Fig. 2 summarises our observations of Algorithm 1. We use four different
initialisations, and set the learning rate as $\eta_{t+1}=300/(t+5000)$. As a
baseline, we compare this to a risk-balancing heuristic (Levitt, 2004) where
bookmakers try to equalise the number of dollars wagered on each outcome, the
implementation is described in Section F.I. Fig. 2 (Middle) shows that under
all initialisations, the SA algorithm could maintain low regret $\leq 10^{2}$.
However, the regret under the risk-balancing scheme is larger by more than an
order of magnitude, and keeps increasing (note y-axis is in log scale). Fig. 2
(Right) shows the trajectories of the price dynamics - all trajectories
converge to the global maximiser. Further, when $t\geq 10^{4}$, the
trajectories stay within the last contour, verifying Theorems 4.3 and 4.5,
_i.e_. the dynamic will converge to a (local) maximiser and stays in the
neighbourhood of the maximiser if it enters it. Overall, when the maximiser is
unique, Algorithm 1 is robust across different initialisations, converges fast
and suffers low regret. If the p.d.f. has multiple modes on each side, it will
result in different landscapes of the profit maximisation problems, one such
case is in Appendix F.

Figure 3: Simulating FTL and LMSR over 100,000 iterations. _Left_ : Regret.
_Right_ : Price trajectory ${a}_{t}$.

Fig. 3 examines Algorithm 2 (FTL) empirically. We compare it to the market-
making approach via the Logarithmic Market Scoring Rule (LMSR) for Kelly
bettors (Hanson, 2007; Abernethy et al., 2013; Beygelzimer et al., 2012) which
is primarily designed for prediction markets to elicit the bettors’ beliefs.
Fig. 3 (Left) presents the regrets over time for both algorithms. It is
observed that the regret of FTL stays $\leq 10^{1}$ throughout and grows
slowly, validating Theorem 5.1. On the other hand, the regret of LMSR grows
faster than FTL. Fig. 3 (Right) presents the trajectories of ${a}_{t}$ of both
algorithms. Both processes converge to steady-states quickly but there is a
noticeable gap between the limits. We found that the price dynamic of LMSR
approximately converges to the average belief of the crowd. As expected, FTL
converges to a point between the bookmaker’s belief $g=0.5$ and the crowd’s
average belief. Such findings echo the insight that the bookmaker exploits the
bias of bettors to maximise the profit, _c.f_. discussion in Section 2.2.

##  7 Conclusion

We articulate a binary betting market model among Kelly bettors and utility-
maximising bookmakers. This model encompasses prediction markets and betting
markets with fair and unfair odds. It pinpoints the conflict between profit-
making and eliciting predictions from the crowd – a fact known by others (Chen
& Pennock, 2007), but not explicitly connected to betting markets. This model
provides rigorous justifications of the empirical observations on bookmakers
exploiting bettor bias for profit-making (Levitt, 2004) – answering an old
academic joke “we know it works in practice, but does it work in theory?”
(Wolfers & Zitzewitz, 2006). Connecting these two insights motivated us to
introduce modern online learning methods into bookmaker strategy, proposing
two algorithms for finding optimal prices. While online learning strategies
abound for prediction markets (Chen & Vaughan, 2010; Frongillo et al., 2012),
ours might be the first implementable for a betting market.

Directions for future work include: (i) extensions to non-binary markets; (ii)
extensions to alternative bettor behaviours, including non-Kelly bettors,
non-i.i.d. beliefs, and belief distribution supported by a strict subset of
interval $[0,1]$; (iii) trade-offs between prediction and profit-making; (iv)
quantification of players’ power in betting markets; and (v) conditions for
unique equilibrium.

## Acknowledgements

This work is supported in part by the Australian Research Council (ARC)
projects DP240100506 and FT230100563. We thank Rui Zhang and Álvaro Flores for
their insightful comments on earlier drafts of this paper. We thank Yanjun Liu
for pointers to the theory of stochastic approximation.

## Impact Statement

This work presents several theoretical advances on binary betting markets.
Betting (_e.g_. sports betting and many other varieties) is a domain loaded
with ethical and societal concerns. We will discuss the potential benefits and
harms on several relevant aspects on betting, and then on potential impacts in
other domains.

Theoretical understanding on bookmaker behaviour as public knowledge is
relatively scant compared to those on bettor behaviour and betting strategies
in both research (Thorp, 1975) and popular
culture555https://en.wikipedia.org/wiki/21_(2008_film). Much knowledge on
bookmaker operation are hidden under commercial confidentiality, available
literature are either empirical (Levitt, 2004) or whistle-blowing on a
particular aspect666https://www.theguardian.com/society/2022/feb/19/stake-
factoring-how-bookies-clamp-down-on-successful-gamblers. Therefore we deem new
theoretical understanding on what makes bookmaker profitable, and how much the
profit could be to have significant potential benefits. On the value of giving
bookmakers a strategy to update prices frequently, a potential benefit is to
have a public strategy that could level the field of gambling industry. A
potential harm could be to increase or decrease revenue for specific
bookmakers, thereby affecting fairness, or negatively affect a firm or its
bettor population.

Bettor behaviour is deemed to follow a particular model (Kelly, 1956) in this
work. Our study focuses on bookmaker behaviour, but we do not rule out
potential flow-on effects that influence the bettors and could cause potential
harm. This could include peripheral measures that bookmakers adopt (other than
adjusting odds and prices) to limit or encourage bettors to bet.

The gap between theory and practice is non-trivial for this work. First of
all, most betting markets are non-binary (including point spread in sports, or
overlapping events), and the price structure is more complex than what is
assumed in this work. Even if someone wants to adopt the online learning
strategies in pricing, it might help or hurt the overall profit in a complex
operations environment influenced by many other factors.

Finally, our eventual goal is to translate the methods and insights from
binary betting to large-scale online behaviour mediated by algorithms. Drawing
on the analogy with multi-armed bandit problems being applicable to domains as
diverse as clinical trials to adaptive routing, it is conceivable that
bookmaking strategy can be applicable to domains that either elicit or exploit
belief of the crowd. In particular, this work quantifies platform power
represented by bookmaker profit obtained using prices as the instrument. We
hope the methodology could help understand other large-scale online platforms
such as social media and online attention (potential benefit), but also
acknowledge that giving online platforms an implementable profit maximisation
scheme may further increase platform power (potential harm to societal
values).

## References

  * Abernethy et al. (2013) Abernethy, J., Chen, Y., and Vaughan, J. W.  Efficient market making via convex optimization, and a connection to online learning.  _ACM Transactions on Economics and Computation (TEAC)_ , 1(2):1–39, 2013.
  * Agrawal et al. (2008) Agrawal, S., Wang, Z., and Ye, Y.  Parimutuel betting on permutations.  In _Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings_ , volume 5385 of _Lecture Notes in Computer Science_ , pp. 126–137. Springer, 2008.  doi: 10.1007/978-3-540-92185-1“˙21.
  * Agrawal et al. (2011) Agrawal, S., Delage, E., Peters, M., Wang, Z., and Ye, Y.  A unified framework for dynamic prediction market design.  _Operations Research_ , 59(3):550–568, 2011.
  * Al-Zahrani & Stoyanov (2008) Al-Zahrani, B. and Stoyanov, J.  On some properties of life distributions with increasing elasticity and log-concavity.  _Applied Mathematical Sciences_ , 2(48):2349–2361, 2008.
  * Algoet & Cover (1988) Algoet, P. H. and Cover, T. M.  Asymptotic optimality and asymptotic equipartition properties of log-optimum investment.  _The Annals of Probability_ , pp. 876–898, 1988.
  * Arrow & Debreu (1954) Arrow, K. J. and Debreu, G.  Existence of an equilibrium for a competitive economy.  _Econometrica: Journal of the Econometric Society_ , pp. 265–290, 1954.
  * Bartlett et al. (2008) Bartlett, P., Dani, V., Hayes, T., Kakade, S., Rakhlin, A., and Tewari, A.  High-probability regret bounds for bandit online linear optimization.  In _Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008_ , pp. 335–342. Omnipress, 2008.
  * Beygelzimer et al. (2012) Beygelzimer, A., Langford, J., and Pennock, D. M.  Learning performance of prediction markets with kelly bettors.  In _Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3_ , AAMAS ’12, pp. 1317–1318, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.  ISBN 0981738133.
  * Borkar & Mitter (1999) Borkar, V. S. and Mitter, S. K.  A strong approximation theorem for stochastic recursive algorithms.  _Journal of optimization theory and applications_ , 100:499–513, 1999.
  * Bottou et al. (2018) Bottou, L., Curtis, F. E., and Nocedal, J.  Optimization methods for large-scale machine learning.  _SIAM review_ , 60(2):223–311, 2018.
  * Brier (1950) Brier, G. W.  Verification of forecasts expressed in terms of probability.  _Monthly Weather Review_ , 78(1):1–3, 1950.  doi: 10.1175/1520-0493(1950)078¡0001:VOFEIT¿2.0.CO;2.
  * Bubeck et al. (2012) Bubeck, S., Cesa-Bianchi, N., et al.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , 5(1):1–122, 2012.
  * Busseti et al. (2016) Busseti, E., Ryu, E. K., and Boyd, S.  Risk-constrained kelly gambling.  _The Journal of Investing_ , 25(3):118–134, 2016\.
  * Chen & Pennock (2007) Chen, Y. and Pennock, D. M.  A utility framework for bounded-loss market makers.  In _UAI 2007, Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, Vancouver, BC, Canada, July 19-22, 2007_ , pp. 49–56. AUAI Press, 2007.  doi: 10.5555/3020488.3020495.  URL https://dl.acm.org/doi/10.5555/3020488.3020495.
  * Chen & Vaughan (2010) Chen, Y. and Vaughan, J. W.  A new understanding of prediction markets via no-regret learning.  In _Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010_ , pp. 189–198. ACM, 2010.  doi: 10.1145/1807342.1807372.  URL https://doi.org/10.1145/1807342.1807372.
  * Chen et al. (2008) Chen, Y., Goel, S., and Pennock, D. M.  Pricing combinatorial markets for tournaments.  In _Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008_ , pp. 305–314. ACM, 2008.  doi: 10.1145/1374376.1374421.  URL https://doi.org/10.1145/1374376.1374421.
  * Chung (1954) Chung, K. L.  On a stochastic approximation method.  _The Annals of Mathematical Statistics_ , pp. 463–483, 1954.
  * Cover (1999) Cover, T. M.  _Elements of information theory_.  John Wiley & Sons, 1999.
  * Davis & Lleo (2013) Davis, M. and Lleo, S.  Fractional kelly strategies in continuous time: Recent developments.  _Handbook of the Fundamentals of Financial Decision Making: Part II_ , pp. 753–787, 2013.
  * Dentcheva & Ruszczynski (2003) Dentcheva, D. and Ruszczynski, A.  Optimization with stochastic dominance constraints.  _SIAM Journal on Optimization_ , 14(2):548–566, 2003.
  * Duchi et al. (2010) Duchi, J. C., Shalev-Shwartz, S., Singer, Y., and Tewari, A.  Composite objective mirror descent.  In _COLT_ , volume 10, pp. 14–26. Citeseer, 2010.
  * Frongillo et al. (2012) Frongillo, R., Della Penna, N., and Reid, M. D.  Interpreting prediction markets: A stochastic approach.  In _Proceedings of Neural Information Processing Systems_ , Lake Tahoe, USA, December 2012.
  * Frongillo & Reid (2015) Frongillo, R. M. and Reid, M. D.  Convergence analysis of prediction markets via randomized subspace descent.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pp. 3034–3042, 2015.  URL https://proceedings.neurips.cc/paper/2015/hash/66be31e4c40d676991f2405aaecc6934-Abstract.html.
  * Gadat (2018) Gadat, S.  Stochastic optimization algorithms, 2018.
  * Gneiting & Raftery (2007) Gneiting, T. and Raftery, A. E.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American Statistical Association_ , 102(477):359–378, 2007.  doi: 10.1198/016214506000001437.
  * Good (1952) Good, I. J.  Rational decisions.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 14(1):107–114, 1952.  doi: 10.1111/j.2517-6161.1952.tb00175.x.
  * Guo & Pennock (2009) Guo, M. and Pennock, D. M.  Combinatorial prediction markets for event hierarchies.  In _8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 1_ , pp. 201–208. IFAAMAS, 2009.  URL https://dl.acm.org/citation.cfm?id=1558041.
  * Hanson (2007) Hanson, R.  Logarithmic markets scoring rules for modular combinatorial information aggregation.  _The Journal of Prediction Markets_ , 1(1):3–15, 2007.
  * Hazan & Kale (2014) Hazan, E. and Kale, S.  Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization.  _The Journal of Machine Learning Research_ , 15(1):2489–2512, 2014.
  * Hazan & Levy (2014) Hazan, E. and Levy, K.  Bandit convex optimization: Towards tight bounds.  _Advances in Neural Information Processing Systems_ , 27, 2014.
  * Hazan et al. (2016) Hazan, E. et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hsieh et al. (2016) Hsieh, C.-H., Barmish, B. R., and Gubner, J. A.  Kelly betting can be too conservative.  In _2016 IEEE 55th conference on decision and control (CDC)_ , pp. 3695–3701. IEEE, 2016.
  * Kelly (1956) Kelly, J. L.  A new interpretation of information rate.  _the bell system technical journal_ , 35(4):917–926, 1956.
  * Lattimore (2024) Lattimore, T.  Bandit convex optimisation, 2024.
  * Lattimore & Szepesvári (2020) Lattimore, T. and Szepesvári, C.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Levitt (2004) Levitt, S. D.  Why are gambling markets organised so differently from financial markets?  _The Economic Journal_ , 114(495):223–246, 2004\.
  * Markowitz (1952) Markowitz, H.  Portfolio selection.  _The Journal of Finance_ , 7(1):77–91, 1952.  ISSN 00221082, 15406261.  URL http://www.jstor.org/stable/2975974.
  * McCarthy (1956) McCarthy, J.  Measures of the value of information.  _Proceedings of the National Academy of Sciences_ , 42(9):654–655, 1956.  doi: 10.1073/pnas.42.9.654.
  * Mertikopoulos et al. (2020) Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V.  On the almost sure convergence of stochastic gradient descent in non-convex problems.  _Advances in Neural Information Processing Systems_ , 33:1117–1128, 2020.
  * Othman et al. (2013) Othman, A., Pennock, D. M., Reeves, D. M., and Sandholm, T.  A practical liquidity-sensitive automated market maker.  _ACM Trans. Econ. Comput._ , 1(3), sep 2013.  ISSN 2167-8375.  doi: 10.1145/2509413.2509414.  URL https://doi.org/10.1145/2509413.2509414.
  * Pemantle (1990) Pemantle, R.  Nonconvergence to unstable points in urn models and stochastic approximations.  _The Annals of Probability_ , 18(2):698–712, 1990\.
  * Renlund (2010) Renlund, H.  Generalized pólya urns via stochastic approximation.  _arXiv preprint arXiv:1002.3716_ , 2010.
  * Robbins & Monro (1951) Robbins, H. and Monro, S.  A Stochastic Approximation Method.  _The Annals of Mathematical Statistics_ , 22(3):400 – 407, 1951.  doi: 10.1214/aoms/1177729586.  URL https://doi.org/10.1214/aoms/1177729586.
  * Rockafellar et al. (2000) Rockafellar, R. T., Uryasev, S., et al.  Optimization of conditional value-at-risk.  _Journal of risk_ , 2:21–42, 2000.
  * Rotando & Thorp (1992) Rotando, L. M. and Thorp, E. O.  The kelly criterion and the stock market.  _The American Mathematical Monthly_ , 99(10):922–931, 1992.
  * Savage (1971) Savage, L. J.  Elicitation of personal probabilities and expectations.  _Journal of the American Statistical Association_ , 66(336):783–801, 1971.  doi: 10.1080/01621459.1971.10482321.
  * Slivkins et al. (2019) Slivkins, A. et al.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ , 12(1-2):1–286, 2019.
  * Sun & Boyd (2018) Sun, Q. and Boyd, S.  Distributional robust kelly gambling.  _arXiv preprint arXiv:1812.10371_ , 2018.
  * Thompson (1933) Thompson, W. R.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Thorp (1975) Thorp, E. O.  Portfolio choice and the kelly criterion.  In _Stochastic optimization models in finance_ , pp. 599–619. Elsevier, 1975.
  * Thorp (2008) Thorp, E. O.  The kelly criterion in blackjack sports betting, and the stock market.  In _Handbook of asset and liability management_ , pp. 385–428. Elsevier, 2008.
  * Von Stackelberg (1934) Von Stackelberg, H.  _Marktform und Gleichgewicht_.  Vienna/Berlin: Julius Springer, 1934.
  * Welling & Teh (2011) Welling, M. and Teh, Y. W.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pp. 681–688. Citeseer, 2011.
  * Wikipedia Contributors (2024) Wikipedia Contributors.  Mathematics of bookmaking, 2024.  URL https://en.wikipedia.org/wiki/Mathematics_of_bookmaking.  [Online; Last accessed Feb 2024].
  * Wolfers & Zitzewitz (2006) Wolfers, J. and Zitzewitz, E.  Interpreting prediction market prices as probabilities, 2006.
  * Yu et al. (2022a) Yu, D., Gao, J., and Wang, T.  Betting market equilibrium with heterogeneous beliefs: A prospect theory-based model.  _European Journal of Operational Research_ , 298(1):137–151, 2022a.
  * Yu et al. (2022b) Yu, D., Gao, J., Wu, W., and Wang, Z.  Price interpretability of prediction markets: A convergence analysis.  In _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022_ , pp. 466–467. ACM, 2022b.  doi: 10.1145/3490486.3538347.  URL https://doi.org/10.1145/3490486.3538347.

Supplementary Material

This is the Supplementary Material to Paper ”Online Learning in Betting
Markets: Profit versus Prediction”. To differentiate with the numberings in
the main file, the numbering of Theorems is letter-based (A, B, …).

## Table of contents

Additional discussions
$\hookrightarrow$ Appendix A: Table of Notations Pg A
$\hookrightarrow$ Appendix B: Connecting $\mathrm{CVaR}$ and Expected Profit
Pg B
$\hookrightarrow$ Appendix C: Lemma on Imprecise Bookmaker Belief Pg C
$\hookrightarrow$ Appendix D: Uniqueness of Maximisers Pg D
$\hookrightarrow$ Appendix E: Incompatibility of Profit Maximisation and
Prediction Aggregation Pg E
$\hookrightarrow$ Appendix F: Additional Empirical Results Pg F

Proofs and derivations
$\hookrightarrow$ Appendix G: Derivation of Kelly Bettor Strategy, Eq. 2 Pg G
$\hookrightarrow$ Appendix H: Derivation of the Bookmaker’s Expected Profit,
Eq. 3 Pg H
$\hookrightarrow$ Appendix I: Proofs for Section 3 Pg I
$\hookrightarrow$ Appendix J: Proof of Theorem 4.1 Pg J
$\hookrightarrow$ Appendix K: Proof of Theorem 4.3 Pg K
$\hookrightarrow$ Appendix L: Proof of Theorem 4.4 Pg L
$\hookrightarrow$ Appendix M: Proof of Theorem 4.5 Pg M
$\hookrightarrow$ Appendix N: Proof of Theorem 5.1 Pg N

##  Appendix A Table of Notations

Symbol | Meaning | Defined
---|---|---
$\mathbb{N}$ | Natural numbers $\\{1,2,\ldots\\}$ |
$x\wedge y$ | $\min\\{x,y\\}$ |
$x\vee y$ | $\max\\{x,y\\}$ |
$(x)_{+}$ | $\max\\{x,0\\}=x\vee 0$ |
$\mathrm{clip}(x;l,u)$ |  $\min\\{\max\\{x,l\\},u\\}=((x\vee l)\wedge u)$ for $l<u$ | Algorithm 2
A, B | Outcomes of binary events (A = $\neg$ B) | Section 2
$t$ | Timestamp and index for bettors, assuming arriving sequentially | Section 2
$T$ | Total number of bettors considered | Section 3
${a}$ | Price for event A, $0<{a}<1$ | Section 2
${b}$ | Price for event B, $0<{b}<1$ | Section 2
$g$ | Bookmaker’s belief | Section 2
$p_{t}$ | Bettor $t$’s belief in event A | Section 2.1
$q_{t}$ | Bettor $t$’s belief in event B | Section 2.1
$w_{t}$ | Bettor $t$’s wealth | Section 2.1
$v_{t}$ | Absolute value of bettor $t$’s investment (bet) | Section 2.1
$f$ | p.d.f. of bettors’ belief distribution | Section 4
$F$ | c.d.f. of bettors’ belief distribution | Section 4
$({a}^{\star},{b}^{\star})$ | Optimal prices (equilibrium prices) | Eq. 6
$({a}^{\sharp},{b}^{\sharp})$ | Worst local maximiser of $u_{t}$ | Theorem 4.4
$({a}^{\flat},{b}^{\flat})$ | One of the local maximisers of $u_{t}$ | Theorem 4.5
$\varphi_{t}^{{a}}$ | Expected logarithm of wealth after bettor $t$ bets on event A | Section 2.1
$\varphi_{t}^{{b}}$ | Expected logarithm of wealth after bettor $t$ bets on event B | Section 2.1
$u_{t}({a},{b})$ | The bookmaker’s expected profit at time $t$ | Section 2.2
$u({a},{b})$ | Same as $u_{t}({a},{b})$; used in the appendix only |
$u_{t}({a},1-{a})$ | The bookmaker’s expected profit at time $t$ when the odds are fair | Section 2.2
$u_{1:T}({a},{b})$ | Bookmaker’s cumulative profit | Section 3
$u_{1:t}({a}_{1:t},{b}_{1:t})$ | Online version of their own expected profit | Section 4
$\overline{W}_{t}$ | Bookmaker’s estimate of the average wealth of bettor $t$ | Section 4
$\widehat{p_{t}}$ | Bookmaker’s estimate the belief of bettor $t$ | Section 4
$\eta_{t}$ | Learning rate of the Algorithm 1 | Algorithm 1
$\Upsilon^{R}$, $\Upsilon^{L},G$ | Auxiliary functions for characterising the first-order condition | Theorem 4.1
$\textsc{Regret}(T,{a},{b})$ | Regret of online algorithms | Definition 4.6

##  Appendix B Connecting $\mathrm{CVaR}$ and Expected Profit

One interesting perspective of Eq. 3 is its connection to conditional value-
at-risk ($\mathrm{CVaR}$) (Rockafellar et al., 2000). Suppose that both terms
in Eq. 3 are positive, and that ${a}$ and ${b}$ are sufficiently far from $g$.
We derive a lower bound of $u_{t}(a,b)$ in terms of $\mathrm{CVaR}$ values of
the belief distribution. Thus, one can conclude that the utility in Eq. 3 is
lower bounded by the tail behaviour of $p_{t},q_{t}$. For any random variable
$\mathsf{X}$ of the belief distribution, let

$\mathrm{CVaR}_{\alpha}(\mathsf{X})\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\mathbb{E}\left[~{}\mathsf{X}\mid\mathsf{X}\geq\text{the
$(1-\alpha)$-quantile value of the belief distribution}~{}\right],$

######  Proposition B.1.

Suppose that ${a}\in[\sqrt{g},1]$ and ${b}\in[\sqrt{1-g},1]$. Then,

$u({a},{b})\geq\mathrm{CVaR}_{\alpha}(p_{t})+\mathrm{CVaR}_{\beta}(q_{t})-({a}+{b}),$

where

$\displaystyle\alpha=\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)^{-1};\quad\beta=\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)^{-1}.$

###### Proof.

We will use the variational form of $\mathrm{CVaR}$ depicted in the following
theorem.

######  Theorem B.2 (Rockafellar et al. (2000, Theorem 1)).

The conditional value-at-risk of a random variable has the following
variational form:

$\mathrm{CVaR}_{\alpha}(\mathsf{Z})=\inf_{\rho\in\mathbb{R}}\left\\{\rho+\frac{\mathbb{E}\left[(\mathsf{Z}-\rho)_{+}\right]}{\alpha}\right\\}.$
(15)

By using the variational form Eq. 15, we have

$\displaystyle\mathbb{E}\left[(p_{t}-{a})_{+}\right]$
$\displaystyle=\alpha\cdot\left({a}+\frac{\mathbb{E}\left[(p_{t}-{a})_{+}\right]}{\alpha}-{a}\right)$
$\displaystyle\geq\alpha\cdot\left(\inf_{\rho}\left\\{\rho+\frac{\mathbb{E}\left[(p_{t}-\rho)_{+}\right]}{\alpha}\right\\}-{a}\right)$
$\displaystyle=\alpha\cdot\left(\mathrm{CVaR}_{\alpha}(p_{t})-{a}\right).$

Analogously,
$\mathbb{E}\left[(q_{t}-{b})_{+}\right]\geq\beta\cdot\left(\mathrm{CVaR}_{\beta}(q_{t})-{b}\right)$.

One can verify that given the conditions of ${a},{b}$, we have that the terms
satisfy:

$\displaystyle\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)^{-1},\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)^{-1}\in[0,1]$

As such, taking $\alpha$ and $\beta$ per the theorem, we have,

$\displaystyle u({a},{b})$
$\displaystyle=\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]+\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)\mathbb{E}\left[(q_{t}-{b})_{+}\right]$
$\displaystyle=\alpha^{-1}\mathbb{E}\left[(p_{t}-{a})_{+}\right]+\beta^{-1}\mathbb{E}\left[(q_{t}-{b})_{+}\right]$
$\displaystyle\geq\mathrm{CVaR}_{\alpha}(p_{t})+\mathrm{CVaR}_{\beta}(q_{t})-({a}+{b}).\qed$

##  Appendix C Lemma on Imprecise Bookmaker Belief

In the following, we present a formal Lemma to clarify our statement about a
bookmaker having a belief of A in the form of an interval $(g_{-},g_{+})$.
This imprecise belief allows the bookmaker to be less committed to their
position about A.

######  Lemma C.1.

Suppose $g_{-}$ and $g_{+}$ are the bookmaker’s lower and upper bound
estimates of the ground truth probability $\mathbb{P}\left[{A}\right]$ such
that $0\leq g_{-}\leq\mathbb{P}\left[{A}\right]\leq g_{+}\leq 1$. Then, there
exists $({a},{b})$ such that the bookmaker’s estimated profit is non-negative
at time $t$, for any preference distribution.

###### Proof.

The proof follows similarly to the derivation of the bookmaker’s expected
profit Eq. 3, as proven in Appendix H. Consider the expected bookmaker’s
profit over the ground truth probability at time $t$:

$u_{t}^{\text{true}}({a},{b})=\left(\frac{1-\mathbb{P}\left[{A}\right]}{1-{a}}-\frac{\mathbb{P}\left[{A}\right]}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]+\left(\frac{\mathbb{P}\left[{A}\right]}{1-{b}}-\frac{1-\mathbb{P}\left[{A}\right]}{{b}}\right)\mathbb{E}\left[(q_{t}-{b})_{+}\right].$

Since, $g_{-}\leq\mathbb{P}\left[{A}\right]\leq g_{+}$, the bookmaker could
obtain the following lower bound:

$u_{t}^{\text{true}}({a},{b})\geq\left(\frac{1-g_{+}}{1-{a}}-\frac{g_{+}}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]+\left(\frac{g_{-}}{1-{b}}-\frac{1-g_{-}}{{b}}\right)\mathbb{E}\left[(q_{t}-{b})_{+}\right].$
(16)

By setting $a\geq g_{+}$ and $1-b\leq g_{-}$, we can conclude that both terms
are nonnegative. ∎

We remark that Algorithm 1 could still be applied to the scenario that the
bookmaker has imprecise estimates of the probability. The reason is that the
SA algorithm could be regarded as two separate stochastic approximation
processes on $\Upsilon^{R}$ and $\Upsilon^{L}$ (see Eq. 9). Hence we could
work on those problems with $g_{+}$ and $g_{-}$ (as parameters of the function
$G$) separately to optimise the lower bound Eq. 16.

##  Appendix D Uniqueness of Maximisers

Critical points of of the profit function Eq. 3 are determined by the
following equation

$\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}\right]-{a}=\frac{{a}(1-{a})({a}-g)}{{a}^{2}-2g{a}+g},$
(17)

where the LHS is known as the Mean Residual Life (MRL) of the bettors’ belief
distribution. It is known that the MRL is decreasing when the belief
distribution is log-concave (Al-Zahrani & Stoyanov, 2008). If the root of the
above equation is unique in the open interval $(0,1)$, then the root must be
the unique maximiser of the profit function Eq. 3.

We empirically examine the uniqueness of such roots for common distributions.
Fig. I (Left) depicts the roots of the equation above. As demonstrated, the
belief distribution used in the experiment of Section 6 corresponds to unique
profit maximiser. Whereas the belief distribution corresponds to multiple
maxmisers (Appendix F) induces multiple roots of the above equation. Further,
we plotted cases of (truncated) normal distribution and (truncated)
exponential distributions. It turns out that all the cases we have tested
admit unique profit maximisers.

Figure I: Illustrations of the roots of Eq. 17. The dashed red line represents
the value of RHS and all others represent the LHS with expectations taken
w.r.t. different distributions. (left plot) Distributions used in Section 6
and Appendix F. (right plot) Truncated exponential distributions with
different parameters $\lambda\in\\{1,2,5\\}$.

Figure II: Illustrations of the roots of Eq. 17. The dashed red line
represents the value of RHS and all others represent the LHS with expectations
taken w.r.t. different belief distributions. (left plot) Truncated Gaussian
distributions with different means $\\{0.5,0.6,0.7,0.8,0.9\\}$ and the same
variance $0.2$. (right plot) Truncated Gaussian distributions with the same
mean $0.2$ but different variances $\\{0.2,0.1,0.05\\}$.

##  Appendix E Incompatibility of Profit Maximisation and Prediction
Aggregation

By Eq. 3, the expected profit when $g=0.5$ is

$\frac{1}{2}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\cdot\mathbb{E}\left[(p_{t}-{a})_{+}\right]+\frac{1}{2}\left(\frac{1}{1-{b}}-\frac{1}{{b}}\right)\cdot\mathbb{E}\left[(q_{t}-{b})_{+}\right]~{}.$

Let’s focus on the first term. If $m-\Delta_{1}\leq{a}\leq m+\Delta_{1}$, the
first term becomes

$\frac{1}{2}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\cdot\mathbb{E}\left[(p_{t}-{a})_{+}\right]~{}=~{}\frac{1}{2}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\cdot\int_{{a}}^{m+\Delta_{1}}(p-{a})\cdot\frac{1}{4\Delta_{1}}\,dp~{}=~{}\frac{1}{16\Delta_{1}}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\left({a}-(m+\Delta_{1})\right)^{2}~{}.$

If $0.5\leq{a}\leq m-\Delta_{1}$, the first term becomes

$\frac{1}{2}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\cdot\mathbb{E}\left[(p_{t}-{a})_{+}\right]~{}=~{}\frac{1}{2}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)\cdot\int_{m-\Delta_{1}}^{m+\Delta_{1}}(p-{a})\cdot\frac{1}{4\Delta_{1}}\,dp\\\
~{}=~{}\frac{1}{8}\left(\frac{1}{1-{a}}-\frac{1}{{a}}\right)(m-{a})~{}.$

We seek ${a}={a}^{\star}$ that maximizes the expected profit over the interval
$[0.5,m+\Delta_{1}]$. There is no simple closed-form formula for
${a}^{\star}$, so we numerically compute ${a}^{\star}$ for different
combinations of $m$ and $\Delta_{1}$. For any fixed $m$, we report the
possible range of ${a}^{\star}$ in Table 2.

##  Appendix F Additional Empirical Results

###  F.I The Risk Balancing Algorithm

Algorithm 3 Risk Balancing Algorithm

0: Initial price ${a}_{0},{b}_{0}$, Learning rate
$(\eta_{t+1})_{t\in\mathbb{N}}$.

1: Initialise the total bets as $B_{L}=B_{R}=0$

2: for each bettor entering the market at time $t$ do

3: Receive the bet placed by the bettor $v_{t}$.

4: if the bet is placed on A then

5: Update the total amount bet on A.  $B_{R}=B_{R}+v_{t}$ (18)

6: else

7: Update the total amount bet on B.  $B_{L}=B_{L}+v_{t}$ (19)

8: end if

9: Update the prices following
${a}={a}+\eta_{t+1}(B_{R}-B_{L}),~{}~{}{b}={b}+\eta_{t+1}(B_{L}-B_{R}).$

10: end for

###  F.II SA under Multi-modal Distribution

Figure III: Simulation results of Algorithm 1 algorithm with $100,000$
bettors. Left: The histogram distribution of bettors’ beliefs. Middle: The
regrets over $100,000$ iterations, data is collected every $1,000$ iterations.
The points of # iterations = $\\{10^{1},\ldots,10^{5}\\}$ are marked with
”$\times$”. Right: Contour plot of
$\delta(a,b)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}u_{1:T}({a}^{\star},{b}^{\star})-u_{1:T}({a},{b})$,
the darkness is of colour is associated with the value $\delta$ according to
the color bar to the right.

Fig. III shows the cases when the maximiser of $u$ is not unique. From the
right plot, we can see that these four processes, under different
initialisations, will converge to four different maximisers respectively. From
the middle plot, we could find that the regrets of processes converging to
extremely “bad” maximisers (_i.e_. green and purple) are increasing
drastically and comparable to the risk balancing scheme. The process converges
to the global maximiser (red) and has regret $\leq 10^{1}$ throughout.
Therefore, we conclude that under the regimes that the maximisers are not
unique, proper initialisation is needed to attain the desired regret bound.

###  F.III Different Regret Definitions

Other than the “stochastic regret” definition we used throughout the main
text, another commonly used definition is the “adversarial regret” (Hazan &
Kale, 2014), which could be defined as:

$\displaystyle\textsc{Regret}^{\text{adv}}(T)$
$\displaystyle=\max_{({a},{b}):{a}+{b}\geq
1}\left\\{\sum_{t=1}^{T}\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)(p_{t}-{a})_{+}w_{t}+\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)(q_{t}-{b})_{+}w_{t}\right\\}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{t=1}^{T}\left(\frac{1-g}{1-{a}_{t}}-\frac{g}{{a}_{t}}\right)(p_{t}-{a}_{t})_{+}w_{t}+\left(\frac{g}{1-{b}_{t}}-\frac{1-g}{{b}_{t}}\right)(q_{t}-{b}_{t})_{+}w_{t},$

The adversarial regret is based on true wealth and beliefs of the bettors. We
note that this quantity is not accessible for bookmakers, as the exact
quantities of $w_{t}$ and $p_{t}$ are not assumed to be known by the
bookmaker. However, we could still test our algorithm under such a benchmark
to examine the efficiency.

Figure IV: Stochastic and Adversarial Regrets under the belief distribution
discussed in Section 6

We could identify that stochastic regret and adversarial regret are nearly
indistinguishable after $10^{3}$ iterations, which justifies that our
algorithm is also efficient in terms of adversarial regret.

##  Appendix G Derivation of Kelly Bettor Strategy, Eq. 2

Consider the problem

$\max_{v\geq 0}\varphi_{t}^{{a}}(v)=\max_{v\geq
0}\left\\{p_{t}\log\left(w_{t}+\frac{1-{a}}{{a}}v\right)+q_{t}\log(w_{t}-v)\right\\}.$

Let $v_{a}^{\star}=\operatorname*{arg\,max}_{v\geq 0}\varphi_{t}^{{a}}(v)$. It
is straightforward to verify that this problem is concave. Hence, by
equalising the gradient to $0$, we have

$\frac{\partial\varphi_{t}^{{a}}(v_{a}^{\star})}{\partial
v}=p_{t}\cdot\frac{\frac{1-{a}}{{a}}}{w_{t}+\frac{1-{a}}{{a}}v_{a}^{\star}}-q_{t}\cdot\frac{1}{w_{t}-v_{a}^{\star}}=0.$

This implies $v_{a}^{\star}=\frac{p_{t}-{a}}{1-{a}}w_{t}$ if $p_{t}>a$ and
$v_{a}^{\star}=0$ otherwise. By symmetry,
$v_{b}^{\star}\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\operatorname*{arg\,max}_{v\geq
0}\varphi_{t}^{{b}}(v)=\frac{q_{t}-{b}}{1-{b}}w_{t}$ if $q_{t}>b$ and
$v_{b}^{\star}=0$ otherwise. This implies the result.

One example of the Kelly Bettor strategy is illustrated in Fig. V, where
positive values are the amounts bet on A, and negative values are the amounts
bet on B.

Figure V: An illustration of Kelly Bettor strategy with prices ${a}=0.6$ and
${b}=0.7$, bettor wealth $w_{t}=1$. (left plot) Optimal investment strategy
$v_{t}^{*}$ is a function of bettor belief $p=p_{t}$. (middle and right plots)
An illustration of the expected log wealth function for betting on either side
$\varphi^{a}(v)$, $\varphi^{b}(v)$, with their maximum marked in red. At
$p_{t}=0.8$, the optimal betting amount is $v^{*}=0.5$ for event A; at
$p_{t}=0.2$, the optimal betting amount is $v^{*}=0.33$ for event B.

##  Appendix H Derivation of the Bookmaker’s Expected Profit, Eq. 3

The bookmaker’s expected profit at time $t$ is equal to the expected amount of
payin minus the expected amount of payout. Since the wealth of bettors is
independent of the beliefs, we first assume the bettor’s wealth is $1$.

If event A happens, by Eq. 2, the amount of payin minus payout is

$\displaystyle~{}~{}~{}\int_{{a}}^{1}\frac{p-{a}}{1-{a}}f(p)\
dp+\int_{0}^{1-{b}}\frac{1-p-{b}}{1-{b}}f(p)\
dp-\frac{1}{{a}}\int_{{a}}^{1}\frac{p-{a}}{1-{a}}f(p)\ dp$
$\displaystyle=\frac{1}{{a}}\int_{{a}}^{1}({a}-p)f(p)\
dp+\int_{0}^{1-{b}}\frac{1-p-{b}}{1-{b}}f(p)\ dp.$

Similarly, if the event B happens, the amount of payin minus payout is

$\displaystyle~{}~{}~{}\int_{{a}}^{1}\frac{p-{a}}{1-{a}}f(p)\
dp+\int_{0}^{1-{b}}\frac{1-p-{b}}{1-{b}}f(p)\
dp-\frac{1}{{b}}\int_{0}^{1-{b}}\frac{1-p-{b}}{1-{b}}f(p)\ dp$
$\displaystyle=\int_{{a}}^{1}\frac{p-{a}}{1-{a}}f(p)\
dp+\frac{1}{{b}}\int_{0}^{1-{b}}({b}+p-1)f(p)\ dp.$

We could get the result directly by combining the terms and noticing the facts

$\displaystyle-\mathbb{E}\left[(p_{t}-{a})_{+}\right]$
$\displaystyle=\int_{{a}}^{1}({a}-p)f(p)\ dp,$
$\displaystyle-\mathbb{E}\left[(1-p_{t}-{b})_{+}\right]$
$\displaystyle=\int_{0}^{1-{b}}({b}+p-1)f(p)\ dp.$

##  Appendix I Proofs for Section 3

###  I.I Proof of Lemma 3.2

See 3.2

###### Proof.

Since $T$ is fixed, it suffices to consider the static case where
$u\stackrel{{\scriptstyle\mathrm{.}}}{{=}}u_{t}$. To see $u$ is upper-bounded,
for the first term we have

$\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]=\frac{{a}-g}{(1-{a}){a}}\int_{{a}}^{1}(p-{a})f(p)\
\text{d}p\leq 1-\frac{g}{{a}},$

where the last inequality follows from $p\leq 1$. Similarly,

$\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)\mathbb{E}\left[(1-{b}-p_{t})_{+}\right]=\frac{{b}-(1-g)}{(1-{b}){b}}\int_{0}^{1-{b}}(1-{b}-p)f(p)\
\text{d}p\leq 1.$

Therefore, $u$ is upper-bounded. Next, to show the maximiser exists, we first
recall that the domain of the profit function is the set $D=${$0<{a}<1$,
$0<{b}<1$, ${a}+{b}\geq 1$}. Define a sequence $(x_{k})\subset D$ such that
$u(x_{k})\rightarrow\sup_{x\in D}u(x)$. Since the sequence is bounded, there
exists $x^{*}$ which is the limit of a convergent subsequence. We only need to
show $x^{*}\in D$. Indeed, $x^{*}$ is in the closure of $D$. Denote the
closure of $D$ as $\bar{D}$, we notice that $\bar{D}\setminus
D=\\{(a,b):a=1\text{ or }b=1,a+b\geq 1\\}$. We can see that the limit

$\lim_{a\rightarrow
1}\frac{(1-g)\mathbb{E}\left[(p_{t}-{a})_{+}\right]}{1-a}=\lim_{a\rightarrow
1}\frac{(1-g)\cdot\int_{a}^{1}1-F(x)~{}\text{d}x}{1-a}=\lim_{a\rightarrow
1}\frac{(1-g)\cdot(F(a)-1)}{-1}=0.$

Therefore,

$\lim_{{a}\rightarrow
1}\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]=\lim_{{a}\rightarrow
1}-\frac{g}{{a}}\mathbb{E}\left[(p_{t}-{a})_{+}\right]=0.$

However, it is clear that the term
$\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]$
could achieve some positive value when $g<a<1$. Thus, we can rule out the
cases that any sequences
$(x_{k})_{k\in\mathbb{N}}=(a_{k},b_{k})_{k\in\mathbb{N}}$ such that
$a_{k}\rightarrow 1$ will converge to some maximiser. Exactly the same
arguments could also rule out the cases that sequences with $b_{k}\rightarrow
1$ will converge to some maximiser, which concludes that the maximiser should
exist in the set $D$. ∎

###  I.II Proof of Lemma 3.3

See 3.3

###### Proof.

For notational simplicity, we denote the first term of $u$ as $\Pi_{1}$ and
the second term of $u$ as $\Pi_{2}$:

$\displaystyle\Pi_{1}$
$\displaystyle=\left(\frac{1-g}{1-{a}}-\frac{g}{{a}}\right)\mathbb{E}\left[(p_{t}-{a})_{+}\right]$
$\displaystyle\Pi_{2}$
$\displaystyle=\left(\frac{g}{1-{b}}-\frac{1-g}{{b}}\right)\mathbb{E}\left[(1-{a}-p_{t})_{+}\right].$

We will prove by contradiction. Since ${a}+{b}\geq 1$, the other possibilities
of the ordering could be $1-{b}^{*}\leq{a}^{*}\leq g$ or $g\leq
1-{b}^{*}\leq{a}^{*}$. Suppose $1-{b}^{*}\leq{a}^{*}\leq g$, then we must have
$\Pi_{1}\leq 0$. However, if we increase ${a}^{*}$ to $\widetilde{{a}^{*}}$
such that $\widetilde{{a}^{*}}>g$. We will have

$\Pi_{1}(\widetilde{{a}^{*}})>0\geq\Pi_{1}({a}^{*}).$

Therefore, $(\widetilde{{a}^{*}},{b}^{*})$ is still a maximiser. Hence, this
leads to a contradiction since $({a}^{*},{b}^{*})$ cannot be the maximiser.
With the same arguments, we can also rule out the other case. ∎

###  I.III Proof of Proposition 3.4

See 3.4

###### Proof.

We consider the case that ${a}+{b}=1$ since the lower bound is still valid
when we ease the assumption to ${a}+{b}\geq 1$. Consider the price
${a}=\frac{\mathbb{E}\left[p_{t}\right]+g}{2}$, the profit becomes

$u({a},1-{a})=\frac{g-\mathbb{E}\left[p_{t}\right]}{2}\cdot\frac{g-\mathbb{E}\left[p_{t}\right]}{2}\cdot\frac{1}{(1-{a}){a}}$

where the term $\frac{1}{(1-{a}){a}}$ is minimised when ${a}=\frac{1}{2}$.
Hence, we could conclude the result.

∎

###  I.IV Proof of Proposition 3.6

See 3.6

###### Proof.

Since $F_{1}$ SOSD over $F_{2}$, we have

$\int_{0}^{x}F_{1}(w)\ dw<\int_{0}^{x}F_{2}(w)\ dw.$

Substracting both sides with $\int_{0}^{1}F_{1}(w)\ dw=\int_{0}^{1}F_{2}(w)\
dw$ we have

$\int_{x}^{1}F_{1}(w)\ dw>\int_{x}^{1}F_{2}(w)\ dw.$

For the profit function, we note that

$\mathbb{E}\left[(p_{t}-{a})_{+}\right]=\int_{{a}}^{1}(p-{a})f(p)\
dp=1-{a}-\int_{{a}}^{1}F(p)\ dp,$

where $F$ is the cdf. Hence,

$\mathbb{E}_{1}[(p_{t}-{a})_{+}]=1-{a}-\int_{{a}}^{1}F_{1}(p)\
dp<1-{a}-\int_{{a}}^{1}F(p)\ dp=\mathbb{E}_{2}[(p_{t}-{a})_{+}].$

Similarly, for the second term, we have

$\mathbb{E}_{1}[(1-{b}-p_{t})_{+}]=\int_{0}^{1-{b}}F_{1}(p)\
dp<\int_{0}^{1-{b}}F_{2}(p)\ dp=\mathbb{E}_{2}[(1-{b}-p_{t})_{+}].$

Since $1-{b}<g<{a}$, the coefficients of expectations in the profit function
are positive. Therefore, it is clear that $u_{1}({a},{b})<u_{2}({a},{b})$.

For the maxima of profit, suppose $({a}^{*},{b}^{*})$ is the maximiser of
$u_{1}$. By Lemma 3.3, we know that $1-{b}^{*}<g<{a}^{*}$. Therefore,
$u_{1}^{*}=u_{1}({a}^{*},{b}^{*})<u_{2}({a}^{*},{b}^{*})\leq u_{2}^{*}$.

∎

##  Appendix J Proof of Theorem 4.1

See 4.1

###### Proof.

By symmetry, we will focus on the right hand side price ${a}$. We notice that

$\displaystyle\mathbb{E}\left[(p_{t}-{a})_{+}\right]$
$\displaystyle=\mathbb{P}\left[p_{t}\geq{a}\right]\cdot\mathbb{E}\left[(p_{t}-{a})_{+}~{}|~{}p_{t}\geq{a}\right]+\mathbb{P}\left[p_{t}\leq{a}\right]\cdot\mathbb{E}\left[(p_{t}-{a})_{+}~{}|~{}p_{t}\leq{a}\right]$
(20)
$\displaystyle=\mathbb{P}\left[p_{t}\geq{a}\right]\cdot\mathbb{E}\left[p_{t}-{a}~{}|~{}p_{t}\geq{a}\right]$
$\displaystyle=\mathbb{P}\left[p_{t}\geq{a}\right]\cdot(\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}\right]-{a})$
$\displaystyle=(1-F(a))\cdot(\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}\right]-{a}).$

On the other hand,
$\mathbb{E}\left[(p_{t}-{a})_{+}\right]=\int_{{a}}^{1}(p_{t}-{a})f(p_{t})\,dp_{t}$,
so by the Leibniz integration rule,
$\frac{\partial\mathbb{E}\left[(p_{t}-{a})_{+}\right]}{\partial{a}}=-\int_{{a}}^{1}f(p_{t})\,dp_{t}=F(a)-1$.
Thus, the derivative of the profit function is

$\frac{\partial
u}{\partial{a}}=\frac{(F({a})-1)({a}-g)}{{a}(1-{a})}+\frac{\mathbb{E}\left[(p_{t}-{a})_{+}\right]({a}^{2}-2g{a}+g)}{{a}^{2}(1-{a})^{2}}.$

Hence, for critical points, we have

${a}(1-{a})({a}-g)(F({a})-1)+\mathbb{E}\left[(p_{t}-{a})_{+}\right]({a}^{2}-2g{a}+g)=0.$

Further, by Eq. 20, we can reformulate above equation to

$\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}\right]-{a}=\frac{{a}(1-{a})({a}-g)}{{a}^{2}-2g{a}+g}.$

∎

##  Appendix K Proof of Theorem 4.3

We first restate the theorem: See 4.3 The proof of Theorem 4.3 has three main
steps. First, we show that the update rule in Algorithm 1 is indeed a
stochastic approximation process as in Definition 4.2. Second, we leverage the
convergence results of stochastic approximation process from existing
literature (Gadat, 2018) to show that Algorithm 1 converges toward a critical
point. Finally, we use two theorems of Pemantle (1990); Renlund (2010) to show
that the critical point is a local maximizer almost surely. The proofs below
focus on Eq. 10 where the bettors bet on the positive side (i.e.
$p_{t}>{a}_{t}$). The other side is symmetric.

###  K.I Step 1: Algorithm 1 is a Stochastic Approximation Process

The update rule Eq. 10 can be written in the form of

${a}_{t+1}={a}_{t}-\eta_{t+1}(h({a}_{t})+M_{t+1}),$

where
$h({a}_{t})={a}_{t}+G({a}_{t})-\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]$
and
$M_{t+1}=\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]-\widehat{p_{t}}$.
We will show that this update rule is a stochastic approximation process as in
Definition 4.2. First, we check that $|h({a}_{t})|$ and $|M_{t+1}|$ are
bounded for every $t\in\mathbb{N}$.

######  Lemma K.1.

Assume the process $({a}_{t})_{t\in\mathbb{N}}$ is generated by Algorithm 1
and stays in the region $[g,1]$. Then,

$|h({a}_{t})|\leq 2,~{}~{}~{}|M_{t+1}|\leq 1,$

for every $t\in\mathbb{N}$.

###### Proof.

First of all,

$\left|h({a}_{t})\right|=\left|{a}_{t}+G({a}_{t})-\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]\right|\leq\left|G({a}_{t})\right|+\left|{a}_{t}-\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]\right|.$

For any ${a}_{t}\in[g,1]$, we have

$G({a}_{t})=\frac{{a}_{t}(1-{a}_{t})({a}_{t}-g)}{{a}_{t}^{2}-2g{a}_{t}+g}=\frac{{a}_{t}(1-{a}_{t})({a}_{t}-g)}{{a}_{t}({a}_{t}-g)+g(1-{a}_{t})}\leq
1-{a}_{t}\leq 1.$

Also, both ${a}_{t}$ and $\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]$
are bounded within $[0,1]$, so their absolute difference is at most 1. This
concludes that $\left|h({a}_{t})\right|\leq 2$.

To bound $|M_{t+1}|$, we notice that by the assumption
$v_{t}\leq\overline{W}_{t}$, we have

$0\leq\widehat{p_{t}}=\frac{(1-{a}_{t})v_{t}}{\overline{W}_{t}}+{a}_{t}\leq
1-{a}_{t}+{a}_{t}=1.$

Hence, both $\widehat{p_{t}}$ and
$\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]$ are bounded within
$[0,1]$, so their absolute difference is at most $1$. ∎

It remains to show that $\mathbb{E}\left[M_{t+1}\mid\mathcal{F}_{t}\right]=0$,
which is established in the next lemma.

######  Lemma K.2.

Let $(\mathcal{F}_{t})_{t\in\mathbb{N}}$ be the filtration that the SA process
generated by Algorithm 1 adapted to. For every $t\in\mathbb{N}$, we have

$\mathbb{E}\left[\widehat{p_{t}}\mid\mathcal{F}_{t}\right]=\mathbb{E}\left[p_{t}\mid
p_{t}\geq{a}_{t}\right].$

###### Proof.

We could notice that

$\mathbb{E}\left[\widehat{p_{t}}\mid\mathcal{F}_{t}\right]=\mathbb{E}\left[\frac{(1-{a}_{t})v_{t}}{\overline{W}_{t}}+{a}_{t}\mid\mathcal{F}_{t}\right],$

where $v_{t}=\frac{p_{t}-{a}_{t}}{1-{a}_{t}}w_{t}$ from the Kelly bettor’s
rule. Hence,

$\displaystyle\mathbb{E}\left[\frac{(p_{t}-{a}_{t})w_{t}}{\overline{W}_{t}}+{a}_{t}\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[{a}_{t}(1-\frac{w_{t}}{\overline{W}_{t}})+p_{t}\mid\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[p_{t}\mid\mathcal{F}_{t}\right]+{a}_{t}\frac{\mathbb{E}\left[\overline{W}_{t}-w_{t}\right]}{\overline{W}_{t}}$
$\displaystyle=\mathbb{E}\left[p_{t}\mid
p_{t}\geq{a}_{t}\right]+{a}_{t}\frac{\mathbb{E}\left[\overline{W}_{t}-w_{t}\right]}{\overline{W}_{t}}$
$\displaystyle=\mathbb{E}\left[p_{t}\mid p_{t}\geq{a}_{t}\right].$

where the third equality follows from the fact that, at time $t$, $p_{t}$ is
sampled from the belief distribution conditioned on the event
$\\{p_{t}>{a}_{t}\\}$ and the last equlity holds as $\overline{W}_{t}$ is the
unbiased estimator of $w_{t}$. ∎

###  K.II Step 2: Convergence to Critical Points

It is known that SA dynamics converge under some assumptions. In our case, we
immediately identify that the profit function $u$ is a Lyapunov function of
the dynamic. We will adopt the following technical result.

######  Theorem K.3 (Gadat (2018, Corollary 2.3.2)).

Let $\Omega$ be a convex set in $\mathbb{R}$. Suppose
$(X_{t})_{t\in\mathbb{N}}\subset\Omega$ is a stochastic approximation process
defined in Definition 4.2. Let $V$ be twice differentiable and $L$-smooth
function such that for any $x\in\Omega$,

$\nabla V(x)\cdot h(x)\geq 0,~{}~{}~{}|h(x)|^{2}+|\nabla V(x)|^{2}\leq
C(1+V(x))$

for some positive constant $C$; furthermore, the noise terms satisfies

$\mathbb{E}\left[|M_{t}|^{2}|\mathcal{F}_{t-1}\right]\leq
C(1+V(X_{n-1}))~{}~{}~{}\forall t\in\mathbb{N}.$

Assume that the set $\\{x\mid V(x)=v\\}\cap\\{x\mid\nabla V(x)\cdot h(x)=0\\}$
is finite for every $v\in\mathbb{R}$. Then, $X_{t}$ converges towards
$X_{\infty}$ almost surely and $\nabla V(X_{\infty})\cdot h(X_{\infty})=0$.

Therefore, by restricting the learning rate $\eta_{t}$ so that $a_{t}$ remains
bounded within the interval $[g,1]$, we can use the above theorem to establish
the convergence result. We prove the following lemma to show that the process
is restricted in the region ${a}_{t}\in(g,1)$ and ${b}\in(1-g,1)$ under the
assumptions of Theorem 4.3.

######  Lemma K.4.

The process $({a}_{t})_{t\in\mathbb{N}}\subset(g,1)$ for all $t\in\mathbb{N}$
if and only if $a_{0}\in[g,1)$ and

$\eta_{t}<\min\left\\{1,\frac{1}{L_{G}}\right\\},$

where $L_{G}$ is the Lipschitz constant of the function $G$ defined in Theorem
4.1.

###### Proof.

We will prove by induction. For the base case, $a_{0}$ is picked within
$[g,1)$ on purpose. Next, we assume ${a}_{t}\in[g,1)$. We note that

$\displaystyle{a}_{t+1}$
$\displaystyle={a}_{t}+\eta_{t}(\widehat{p_{t}}-{a}_{t}-G({a}_{t}))$
$\displaystyle={a}_{t}+\eta_{t}\left(\frac{(p_{t}-{a}_{t})w_{t}}{\overline{W}_{t}}-G({a}_{t})\right)$
$\displaystyle\geq{a}_{t}-\eta_{t}\cdot G({a}_{t}).$

where the inequality follows from the fact that $p_{t}\geq{a}_{t}$. If
$\eta_{t}\leq\frac{1}{L_{G}}$, then

$\eta_{t}\leq\frac{1}{L_{G}}\leq\frac{{a}_{t}-g}{G({a}_{t})-G(g)}=\frac{{a}_{t}-g}{G({a}_{t})}.$

It follows that

${a}_{t+1}\geq{a}_{t}-\eta_{t}\cdot G({a}_{t})\geq g.$

Since $\widehat{p_{t}}\leq 1$, by the fact that $\eta_{t}\leq 1$, we can
conclude that

$\displaystyle{a}_{t+1}$
$\displaystyle={a}_{t}+\eta_{t}(\widehat{p_{t}}-{a}_{t}-G({a}_{t}))$
$\displaystyle\leq{a}_{t}+\eta_{t}(1-{a}_{t}-G({a}_{t}))$ $\displaystyle\leq
1-G({a}_{t})\leq 1.\qed$

###  K.III Step 3: Non-convergence to local minimizers or boundary points

The last part to conclude the proof is to classify the critical points and
show that the SA dynamic will avoid local minimisers with probability $1$.
First, we utilise the following theorem to exclude the probability that the
dynamic will converge to interior local minimisers.

######  Theorem K.5 (Pemantle (1990, Theorem 1)).

Let $(X_{t})_{t\in\mathbb{N}}$ be a stochastic approximation process defined
in Definition 4.2. Suppose
$(X_{t})_{t\in\mathbb{N}}\subset\text{int~{}}\Omega$ for some set $\Omega$,
and $h(p)=0$ for some $p\in\Omega$. Let $\mathcal{N}_{p}$ be a neighbourhood
of $p$. Assume that, for some constants $c_{1},c_{2},c_{3},c_{4}>0$, the
following conditions are satisfied whenever $X_{t}\in\mathcal{N}_{p}$ and $t$
is sufficiently large:

  * •

$h$ is twice differentiable; t

  * •

$h(x)(x-p)<0$ for any $x\neq p$ and $x$ is close to $p$;

  * •

$\frac{c_{1}}{t}\leq\eta_{t}\leq\frac{c_{2}}{t}$;

  * •

$\mathbb{E}\left[|M_{t}|\right]\geq c_{3}$; and

  * •

$|M_{t}|\leq c_{4}$ almost surely.

Then $\mathbb{P}\left[X_{t}\rightarrow p\right]=0$.

Since the last assumption of Theorem 4.3 rules out the possibility of saddle
points, the critical point is either a local maximiser or a local minimiser.
Applying Theorem K.5 will rule out the possibility of convergence to local
minimisers. Next, we are still left to check that the dynamic will not
converge to boundaries, where we note that the boundary points $\\{0,1\\}$ are
indeed critical points of the profit function, which could not be handled
directly by Theorem K.5. To demonstrate non-convergence to such boundaries, we
will rely on Renlund’s (Renlund, 2010) result and control the convergence to
the boundary by inspecting the intrinsic characteristics of the dynamics.

We will focus on the non-convergence to $1$. It is immediate that $1$ is a
critical point. Moreover, the profit is $0$ when ${a}=1$. We formally state
the main technical tool below.

######  Theorem K.6 (Renlund (2010, Theorem 3)).

Suppose that $(X_{t})_{t\in\mathbb{N}}\subset(a,b)$ is a SA process defined in
Definition 4.2. Assume that for any $p\in\\{a,b\\}$, $h(p)=0$ and
$h(x)(x-p)<0$ for any $x\neq p$ and $x$ is close to $p$. Also, assume there
exists positive constants $K_{1},K_{2}$ such that

$\mathbb{E}\left[M_{t+1}^{2}|\mathcal{F}_{t}\right]\leq K_{1}|X_{t}-p|,$
$[h(x)]^{2}\leq K_{2}|x-p|,$
$t\cdot|X_{t}-p|\rightarrow\infty,~{}~{}\text{as}~{}t\rightarrow\infty.$ (21)

Then $\mathbb{P}\left[X_{t}\rightarrow p\right]=0$.

We start by checking $h(x)(x-1)<0$ when $x$ is near $1$. It is equivalent to
showing $h(x)>0$ when $x$ is near $1$. Recall that
$h(x)=x+G(x)-\mathbb{E}\left[p_{t}\mid p_{t}\geq x\right]=\Upsilon^{R}(x)$,
which is a continuous function since the p.d.f. $f$ is differentiable. By the
third assumption of Theorem 4.3, $\Upsilon^{R}(x)$ has finitely many roots in
the interval $(0,1)$. Thus, for all $x$ between the largest root and $1$,
$\Upsilon^{R}(x)$ must have the same sign. By our calculations in Appendix J,
$\Upsilon^{R}(x)$ has opposite sign of $\frac{\partial u(x)}{\partial x}$.
Also, observe that in Eq. 3, when $x$ is near 1,
$\left(\frac{1-g}{1-x}-\frac{g}{x}\right)\mathbb{E}\left[(p_{t}-x)_{+}\right]$
is strictly positive while its value is zero when $x\nearrow 1$. Combining all
of the above, $\frac{\partial u(x)}{\partial x}$ must be negative when $x$ is
near $1$, implying $h(x)=\Upsilon^{R}(x)$ must be positive.

Then we will mainly focus on verifying Eq. 21 since the other assumptions in
the above theorem are immediately satisfied. To start, we have the following
lemma.

######  Lemma K.7.

For $x\in[g,1]$,

$1-x-G(x)\leq C\cdot(1-x)^{2}$

for some constant $C$.

###### Proof.

By direct calculation, we could see that it is equivalent to show that

$\frac{g}{x^{2}-2gx+g}\leq C.$

For $C\geq\frac{1}{1-g}$, we have $(1-\frac{1}{C})g\geq g^{2}$. Hence,
$x^{2}-2gx+(1-\frac{1}{C})g\geq x^{2}-2gx+g^{2}\geq 0$. It concludes the
proof. ∎

Next, we are ready to verify that (21) is satisfied for the dynamic generated
by Algorithm 1.

######  Lemma K.8.

Let $({a}_{t})_{t\in\mathbb{N}}$ be the process generated by Algorithm 1, we
have

$t\cdot|{a}_{t}-1|\rightarrow\infty,~{}~{}\text{as}~{}t\rightarrow\infty.$

###### Proof.

First, since $v_{t}\leq\overline{W}_{t}$, by Lemma K.7 we have

$\displaystyle{a}_{t+1}$
$\displaystyle={a}_{t}+\eta_{t}(\widehat{p_{t}}-{a}_{t}-G({a}_{t}))$
$\displaystyle\leq{a}_{t}+\eta_{t}(1-{a}_{t}-G({a}_{t}))$
$\displaystyle\leq{a}_{t}+C\eta_{t}(1-{a}_{t})^{2}.$

For some large enough $T$, we have $\frac{C\gamma}{t+m}\leq 1$ for all $t\geq
T$. Define a sequence $(x_{t})_{t\in\mathbb{N}}$ such that $x_{1}={a}_{T}$ and
$x_{t+1}=x_{t}+\frac{1}{t+T+m+1}(1-x_{t})^{2}$. It follows that
$1-{a}_{t+T}\geq 1-x_{t}$ for any $t\geq 1$. Hence, it suffices to show that
$t\cdot(1-x_{t})\rightarrow\infty$. Let $y_{t}=1-x_{t}$, We hypothesise that
$y_{t}\geq\frac{1}{\sqrt{t}}y_{1}$. We will prove inductively. The base case
is trivial. For the step case, we assume that
$y_{t}\geq\frac{1}{\sqrt{t}}y_{1}$, we aim to show that
$y_{t+1}\geq\frac{1}{\sqrt{t+1}}y_{1}$. Notice that,

$(t+1)\cdot t^{1/2}-(t+1)^{1/2}\cdot t\geq y_{1},$

for $y_{1}$ sufficiently small. And the LHS is increasing as $t$ increases.
Hence,

$\frac{1}{t+1}\cdot\frac{1}{t}\cdot
y_{1}^{2}\leq\left(\frac{1}{t^{1/2}}-\frac{1}{(t+1)^{1/2}}\right)\cdot y_{1}.$

Therefore, by inductive hypothesis

$y_{t+1}\geq
y_{t}-\frac{1}{t+1}y_{t}^{2}\geq\frac{1}{t^{1/2}}y_{1}-\frac{1}{t+1}\cdot\frac{y_{1}^{2}}{t}\geq\frac{1}{(t+1)^{1/2}}y_{1}.$

Therefore, we have shown that $y_{t}\geq\frac{1}{\sqrt{t}}y_{1}$ for every
$t\in\mathbb{N}$ as long as $y_{1}$ is sufficiently small, which could be
assumed to be true since otherwise will yield our result directly. To
conclude, we notice that $t\cdot y_{t}\geq t^{1/2}\cdot
y_{1}=t^{1/2}\cdot(1-x_{1})$, which goes to infinity as $t\rightarrow\infty$.
∎

##  Appendix L Proof of Theorem 4.4

We first restate the theorem here. See 4.4 In this section, we will emphasise
that the meaning of step-index $t$ is the total number of bettors interacting
with the market. Denote the probability that the bettor will bet on the ”not
happen” and ”happen” sides as $\kappa_{t}:=F(1-{b}_{t})$ and
$\rho_{t}:=1-F({a}_{t})$ respectively. We consider the ”happen” side, with
probability $\rho_{t}$ the process is updated as

${a}_{t+1}={a}_{t}-\eta_{t+1}(h({a}_{t})+M_{t+1}),$

where
$h({a}_{t})={a}_{t}+G({a}_{t})-\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]$
and
$M_{t+1}=\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}_{t}\right]-\widehat{p_{t}}$.
First, we need to identify the following fact.

######  Lemma L.1.

Under the assumptions of Theorem 4.3, if $({a}^{\sharp},{b}^{\sharp})$ is a
local maximiser of $u({a},{b})$, then, within a compact convex neighbourhood
$\mathcal{K}$ of ${a}^{\sharp}$, there exists constants $\alpha,\beta>0$ such
that

$\alpha({a}-{a}^{\sharp})^{2}\leq
h({a})\cdot({a}-{a}^{\sharp})\leq\beta({a}-{a}^{\sharp})^{2}.$

###### Proof.

By Mertikopoulos et al. (2020, Lemma D.2), we first have

$-\beta^{\prime}({a}-{a}^{\sharp})^{2}\leq\frac{\partial
u}{\partial{a}}\cdot({a}-{a}^{\sharp})\leq-\alpha^{\prime}({a}-{a}^{\sharp})^{2},$

for some positive constants $\alpha^{\prime},\beta^{\prime}$. We also notice
that

$\displaystyle\frac{\partial u}{\partial{a}}$
$\displaystyle=\frac{(F({a})-1)({a}-g)}{{a}(1-{a})}+\frac{\mathbb{E}\left[(p_{t}-{a})_{+}\right]({a}^{2}-2g{a}+g)}{{a}^{2}(1-{a})^{2}}$
$\displaystyle=\frac{(1-F({a}))({a}^{2}-2g{a}+g)}{{a}^{2}(1-{a})^{2}}\left[-G({a})+\mathbb{E}\left[p_{t}~{}|~{}p_{t}\geq{a}\right]-{a}\right]$
$\displaystyle=\frac{(1-F({a}))({a}^{2}-2g{a}+g)}{{a}^{2}(1-{a})^{2}}\cdot(-h({a})).$

It is clear that the function
$\frac{(1-F({a}))({a}^{2}-2g{a}+g)}{{a}^{2}(1-{a})^{2}}$ is strictly positive
and continuous for $0<a<1$. Since the neighbourhood $\mathcal{K}$ is compact,
hence the function is bounded. In particular, it is lower bounded by some
positive constant as long as $\mathcal{K}$ is small enough. Therefore, the
result follows. ∎

We are ready the present the descent lemma.

######  Lemma L.2.

Define $D_{t}=\frac{1}{2}({a}_{t}-{a}^{\sharp})^{2}$. Let $\mathcal{K}$ and
$\alpha$ be as in Lemma L.1. Suppose the process stays in $\mathcal{K}$
whenever $t\geq 1$. If the bettor’s belief $p_{t+1}\geq{a}_{t}$ then

$D_{t+1}\leq(1-2\alpha\eta_{t+1})D_{t}+\eta_{t+1}\xi_{t+1}+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a}_{t})^{2},$
(22)

where $\xi_{t+1}=M_{t+1}({a}^{\sharp}-{a}_{t})$ and
$\tilde{h}({a}_{t})=h({a}_{t})+M_{t+1}$.

###### Proof.

We could notice that,

$\displaystyle D_{t+1}$
$\displaystyle=\frac{1}{2}({a}_{t+1}-{a}^{\sharp})^{2}$
$\displaystyle=\frac{1}{2}\left[{a}_{t}-\eta_{t+1}(h({a}_{t})+M_{t+1})-{a}^{\sharp}\right]^{2}$
$\displaystyle=D_{t}-\eta_{t+1}(h({a}_{t})+M_{t+1})({a}_{t}-{a}^{\sharp})+\frac{1}{2}\eta_{t+1}^{2}(h({a}_{t})+M_{t+1})^{2}$
$\displaystyle\leq
D_{t}-2\alpha\eta_{t+1}D_{t}+\eta_{t+1}\xi_{t+1}+\frac{1}{2}\eta_{t+1}^{2}(h({a}_{t})+M_{t+1})^{2},$

where the last inequality follows from Lemma L.1. ∎

Next, we present a technical lemma characterising the growth of the recurrence
relation we are studying.

######  Lemma L.3 (Chung (1954, Lemma 2)).

Let $(x_{t})_{t\in\mathbb{N}}$ be a nonnegative sequence such that

$x_{t+1}\leq\left(1-\frac{P}{t+m}\right)x_{t}+\frac{R}{(t+m)^{1+r}},$

where $r,m,P,R>0$ and $P>r$. Then

$x_{t}\leq\frac{R}{P-r}\frac{1}{t}+o\left(\frac{1}{t}\right).$

Now, we are ready to prove Theorem 4.4.

###### Proof of Theorem 4.4.

We first assume that the process is bounded within the neighbourhood
$\mathcal{K}$ of a maximiser ${a}^{\sharp}$ defined in Lemma L.2. We note that

$\mathbb{E}\left[\eta_{t+1}\xi_{t+1}\right]=\eta_{t+1}\mathbb{E}\left[\mathbb{E}\left[\xi_{t+1}~{}|~{}\mathcal{F}_{t}\right]\right]=\eta_{t+1}\mathbb{E}\left[({a}^{\sharp}-{a}_{t})\mathbb{E}\left[M_{t+1}~{}|~{}\mathcal{F}_{t}\right]\right]=0.$
(23)

And also,

$\mathbb{E}\left[\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a}_{t})^{2}\right]=\frac{1}{2}\eta_{t+1}^{2}\mathbb{E}\left[(h({a}_{t})+M_{t+1})^{2}\right]\leq\eta_{t+1}^{2}\mathbb{E}\left[h({a}_{t})^{2}+M_{t+1}^{2}\right]\leq
5\eta_{t+1}^{2},$ (24)

where the last inequality follows from Lemma K.1. Denote $A_{t}$ as the event
that bettor $t$ will bet on the positive side. Then

$\displaystyle\mathbb{E}\left[D_{t+1}\right]$
$\displaystyle=\rho_{t}\mathbb{E}\left[D_{t+1}~{}|~{}A_{t+1}\right]+(1-\rho_{t})\mathbb{E}\left[D_{t+1}~{}|~{}A_{t+1}^{c}\right]$
$\displaystyle=\rho_{t}\mathbb{E}\left[D_{t+1}~{}|~{}A_{t+1}\right]+(1-\rho_{t})\mathbb{E}\left[D_{t}\right]$
$\displaystyle\leq\rho_{t}(1-2\alpha\eta_{t+1})\mathbb{E}\left[D_{t}\right]+5\rho_{t}\eta_{t+1}^{2}+(1-\rho_{t})\mathbb{E}\left[D_{t}\right]$
$\displaystyle=(1-2\alpha\rho_{t}\eta_{t+1})\mathbb{E}\left[D_{t}\right]+5\rho_{t}\eta_{t+1}^{2},$

where the third line follows from Lemma L.2 and the fact that the sigma-
algebras $\sigma(A_{t+1})$ and $\sigma(D_{t})$ are independent. Further, since
the process is bounded within $\mathcal{K}$, we have

$\rho_{t}=1-F({a}_{t})\geq 1-F(\sup\mathcal{K})=:\rho.$

Since $\mathcal{K}$ could be arbitrarily small, and the number of maximisers
is finite, we could assume that $\sup\mathcal{K}<1$ and hence $\rho>0$. Then

$\mathbb{E}\left[D_{t+1}\right]\leq(1-2\alpha\rho\eta_{t+1})\mathbb{E}\left[D_{t}\right]+5\eta_{t+1}^{2}$

Hence, by Lemma L.3, when $\alpha\rho\gamma>1$ and $t$ is large enough, we
have

$\mathbb{E}\left[D_{t}\right]\leq\frac{5}{2\alpha\rho\gamma-1}\frac{1}{t}+o\left(\frac{1}{t}\right)\leq\frac{6}{t},$

where $\gamma$ could be taken to be large enough that $\alpha\rho\gamma>1$.
Recalling that $\eta_{t+1}=\frac{\gamma}{t+m}$, this does not affect the
former statements on restricting the process within $[g,1]$ since we could let
$m$ be large enough accordingly. By the Jensen’s inequality,

$\mathbb{E}\left[\left|{a}_{t}-{a}_{t}^{\sharp}\right|\right]^{2}\leq
2\mathbb{E}\left[D_{t}\right]\leq\frac{12}{t},$

which implies that
$\left|\mathbb{E}\left[|{a}_{t}-{a}_{t}^{\sharp}|\right]\right|\leq\sqrt{\frac{12}{t}}$.
By the Lipschitz continuity of $u$, we could further get

$\mathbb{E}\left[\left|u({a}_{t},{b}_{t})-u({a}_{t}^{\sharp},{b}_{t}^{\sharp})\right|\right]\leq
L_{u}\mathbb{E}\left[\left|{a}_{t}-{a}_{t}^{\sharp}\right|+\left|{b}_{t}-{b}_{t}^{\sharp}\right|\right]\leq
4\sqrt{3}L_{u}t^{-1/2}.$

Now we ease the assumption that the process
$({a}_{t})_{t=1}^{\infty}\subset\mathcal{K}$. By Theorem 4.3, the process will
converge to at least one of the maximisers with probability $1$. Hence, there
exists some constant $N$, we must have
$({a}_{t})_{t=N}^{\infty}\subset\mathcal{K}$. Therefore, for $t$ large enough,
we could eventually get

$\mathbb{E}\left[\left|u({a}_{t},{b}_{t})-u({a}_{t}^{\sharp},{b}_{t}^{\sharp})\right|\right]\leq
4\sqrt{3}L_{u}(t-N)^{-1/2}\leq 7L_{u}t^{-1/2}.$

Finally, as we could not make sure which maximiser is
$({a}^{\sharp},{b}^{\sharp})$, we could at least take
$({a}^{\sharp},{b}^{\sharp})$ as the worst maximiser as stated in the theorem,
which yields the result. ∎

##  Appendix M Proof of Theorem 4.5

See 4.5 Let $\mathcal{U}$ be a neighbourhood of ${a}^{\sharp}$ and
$\epsilon>0$, similar to Mertikopoulos et al. (2020), we will use the
following notations,

$\displaystyle A_{t}$ $\displaystyle=\\{p_{t}\geq p_{m,t-1}\\},$
$\displaystyle\zeta_{t}$
$\displaystyle=\sum_{k=1}^{t}\mathds{1}_{A_{k+1}}\eta_{k+1}\xi_{k+1},~{}~{}S_{t}=\frac{1}{2}\sum_{k=1}^{t}\mathds{1}_{A_{k+1}}\eta_{k+1}^{2}\tilde{h}(p_{m,k})^{2},$
$\displaystyle R_{t}$ $\displaystyle=\zeta_{t}^{2}+S_{t},$
$\displaystyle\Omega_{t}$
$\displaystyle=\Omega_{t}(\mathcal{U})=\\{p_{m,k}\in\mathcal{U}~{}\text{for
all}~{}k=1,2,\ldots,t\\},$ $\displaystyle E_{t}$
$\displaystyle=E_{t}(\epsilon)=\\{R_{k}\leq\epsilon~{}\text{for
all}~{}k=1,2,\ldots,t\\}.$

In particular, we make the following relation between $\mathcal{U}$ and
$\epsilon$ that

$\\{{a}:({a}-{a}^{\sharp})^{2}\leq
4\epsilon+2\sqrt{\epsilon}\\}\subset\mathcal{U}.$

The following technical lemma further controls the noise terms $R_{t}$. We
will present the proof for the sake of completeness but we note that the proof
idea is similar to Lemma D.3 of Mertikopoulos et al. (2020).

######  Lemma M.1 (Mertikopoulos et al. (2020, Lemma D.3)).

Asumme that $({a}_{1}-{a}^{\sharp})^{2}\leq 2\epsilon$, under the assumptions
in Theorem 4.3, for $t=1,2,\ldots$, we have

  1. 1.

$\Omega_{t+1}\subset\Omega_{t}$ and $E_{t+1}\subset E_{t}$.

  2. 2.

$E_{t-1}\subset\Omega_{t}$.

  3. 3.

Consider the following event

$\tilde{E}_{t}:=E_{t-1}\setminus
E_{t}=E_{t-1}\cap\\{R_{t}>\epsilon\\}=\\{R_{k}\leq\epsilon~{}\text{for
all}~{}k=1,2,\ldots,n-1~{}\text{and}~{}R_{t}>\epsilon\\},$

and let $\tilde{R}_{t}=R_{t}\mathds{1}_{E_{t-1}}$ denote the cumulative error
subject to the fact that the noise is being small until $t$, then

$\mathbb{E}\left[\tilde{R}_{t}\right]\leq\mathbb{E}\left[\tilde{R}_{t-1}\right]+\left(5+r_{\mathcal{U}}^{2}\right)\eta_{t+1}^{2}-\epsilon\mathbb{P}\left[\tilde{E}_{t-1}\right],$
(25)

where $r_{\mathcal{U}}=\sup_{{a}\in\mathcal{U}}|{a}-{a}^{\sharp}|$ and, by
convention, we set $\tilde{E}_{0}=\emptyset$ and $\tilde{R}_{0}=0$.

###### Proof.

For 1, it comes directly from the definition of $E_{t}$ and $\Omega_{t}$.

For 2, we will prove it by induction. For the base case ($t=1$), we have
$E_{0}=\Omega$ which is the whole probability space, and
$\Omega_{1}=\\{{a}_{1}\in\mathcal{U}\\}$ which is specified by the assumption
that $({a}_{1}-{a}^{\sharp})^{2}\leq 2\epsilon$. For the step case, we assume
that $E_{t-1}\subset\Omega_{t}$. It is equivalent to the fact that if
$R_{k}\leq\epsilon$ for every $k=1,2,\ldots,t-1$ then $p_{m,k}\in\mathcal{U}$
for all $k=1,2\ldots t$. Hence, by the fact that $E_{t+1}\subset E_{t}$, we
only need to show that ${a}_{t+1}\in\mathcal{U}$ when $R_{t}\leq\epsilon$. For
realisations that $p_{t+1}<{a}_{t}$, we could see that
${a}_{t+1}={a}_{t}\in\mathcal{U}$. For realisations that $p_{t+1}\geq{a}_{t}$,
by Lemma L.2, we have

$D_{k+1}\leq
D_{k}+\eta_{k+1}\xi_{k+1}+\frac{1}{2}\eta_{k+1}^{2}\tilde{h}({a}_{t})^{2},$

for every $k=1,2,\ldots,t$. Therefore, summing up both sides from $k=1$ to
$k=t$ gives

$D_{t+1}\leq
D_{1}+\zeta_{t}+S_{t}\leq\sqrt{R_{t}}+R_{t}\leq\epsilon+\sqrt{\epsilon}+\epsilon=2\epsilon+\sqrt{\epsilon}.$

Since $\\{{a}:({a}-{a}^{\sharp})^{2}\leq
4\epsilon+2\sqrt{\epsilon}\\}\subset\mathcal{U}$, the results follows.

For 3, we notice that

$\displaystyle\tilde{R}_{t}$
$\displaystyle=R_{t}\mathds{1}_{E_{t-1}}=R_{t-1}\mathds{1}_{E_{t-1}}+(R_{t}-R_{t-1})\mathds{1}_{E_{t-1}}$
(26)
$\displaystyle=R_{t-1}\mathds{1}_{E_{t-2}}-R_{t-1}\mathds{1}_{\tilde{E}_{t-1}}+(R_{t}-R_{t-1})\mathds{1}_{E_{t-1}}$
$\displaystyle=\tilde{R}_{t-1}+(R_{t}-R_{t-1})\mathds{1}_{E_{t-1}}-R_{t-1}\mathds{1}_{\tilde{E}_{t-1}}.$

We first focus on the term $(R_{t}-R_{t-1})\mathds{1}_{E_{t-1}}$. If
$p_{t}<{a}_{t}$, then $R_{t}-R_{t-1}=0$. If $p_{t}\geq{a}_{t}$, we have

$\displaystyle R_{t}-R_{t-1}$
$\displaystyle=\zeta_{t}^{2}-\zeta_{t-1}^{2}+S_{t}-S_{t-1}$
$\displaystyle=\eta_{t+1}\xi_{t+1}(\zeta_{t}+\zeta_{t-1})+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a}_{t})^{2}$
$\displaystyle=2\eta_{t+1}\xi_{t+1}\zeta_{t-1}+\eta_{t+1}^{2}\xi_{t+1}^{2}+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a}_{t})^{2}.$

Then, we deal with the above term by term. For the first term, we have

$\mathbb{E}\left[\mathds{1}_{E_{t-1}}2\eta_{t+1}\xi_{t+1}\zeta_{t-1}~{}|~{}A_{t}\right]=\mathbb{E}\left[\mathds{1}_{E_{t-1}}2\eta_{t+1}\zeta_{t-1}\mathbb{E}\left[\xi_{t+1}~{}|~{}\mathcal{F}_{t}\right]~{}|~{}A_{t}\right]=0,$

where the first equality follows from the fact that $\zeta_{t-1}$ and
$\mathds{1}_{E_{t-1}}$ are $\mathcal{F}_{t}$ measurable and $\eta_{t+1}$ is
constant, the second equality follows from the assumption that
$\mathbb{E}\left[M_{t+1}~{}|~{}\mathcal{F}_{t}\right]=0$. For the second term,
we have

$\mathbb{E}\left[\eta_{t+1}^{2}\mathds{1}_{E_{t-1}}\xi_{t+1}^{2}\right]\leq\eta_{t+1}^{2}\mathbb{E}\left[\mathds{1}_{\Omega_{t}}M_{t+1}^{2}({a}^{\sharp}-{a}_{t})^{2}\right]\leq\eta_{t+1}^{2}r^{2}_{\mathcal{U}}.$

For the third term, we have

$\frac{1}{2}\eta_{t+1}^{2}\mathbb{E}\left[\tilde{h}({a}_{t})^{2}\right]\leq\frac{1}{2}\eta_{t+1}^{2}\mathbb{E}\left[2(M_{t+1}^{2}+h({a}_{t})^{2})\right]\leq
5.$

Therefore, in summary, we have

$\mathbb{E}\left[\mathds{1}_{E_{t-1}}(R_{t}-R_{t-1})\right]\leq\eta_{t+1}^{2}(5+r^{2}_{\mathcal{U}}).$

Next, for the last term of (26), we have

$\mathbb{E}\left[R_{t-1}\mathds{1}_{\tilde{E}_{t-1}}\right]\geq\epsilon\mathbb{E}\left[\mathds{1}_{\tilde{E}_{t-1}}\right]=\epsilon\mathbb{P}\left[\tilde{E}_{t-1}\right],$

where the first inequality follows from the definition of $\tilde{E}_{t-1}$.
Putting everything together to (26) will yield the result. ∎

The following lemma controls the probability of escaping.

######  Lemma M.2 (Mertikopoulos et al. (2020, Proposition D.2)).

Fix the tolerance level $\delta>0$, under the assumptions in Theorem 4.3 and
Theorem 4.4, we have

$\mathbb{P}\left[E_{t}\right]\geq 1-\delta,~{}~{}\forall t\in\mathbb{N}.$

###### Proof.

First, we note that

$\mathbb{P}\left[\tilde{E}_{t}\right]=\mathbb{P}\left[E_{t-1}\cap\\{R_{t}>\epsilon\\}\right]=\mathbb{E}\left[\mathds{1}_{E_{t-1}}\cdot\mathds{1}_{\\{R_{t}>\epsilon\\}}\right]\leq\mathbb{E}\left[\mathds{1}_{E_{t-1}}\cdot\frac{R_{t}}{\epsilon}\right]=\mathbb{E}\left[\tilde{R}_{t}\right]/\epsilon,$

where the inequality follows from the fact that $R_{t}/\epsilon>1$ when
$R_{t}>\epsilon$. Next, summing over both sides from $1$ to $t$ for (25), we
get

$\mathbb{E}\left[\tilde{R}_{t}\right]\leq\mathbb{E}\left[\tilde{R}_{0}\right]+R_{\star}\sum_{k=1}^{t}\eta_{k+1}^{2}-\epsilon\sum_{k=1}^{t}\mathbb{P}\left[\tilde{E}_{k-1}\right],$

where $R_{\star}=5+r_{\mathcal{U}}^{2}$. Hence, we combining the above
findings, we have

$\sum_{k=1}^{t}\mathbb{P}\left[\tilde{E}_{k}\right]=\mathbb{P}\left[\tilde{E}_{t}\right]+\sum_{k=1}^{t}\mathbb{P}\left[\tilde{E}_{k-1}\right]\leq\frac{1}{\epsilon}\left(\mathbb{E}\left[\tilde{R}_{t}\right]+\mathbb{E}\left[\tilde{R}_{0}\right]-\mathbb{E}\left[\tilde{R}_{t}\right]+R_{\star}\sum_{k=1}^{t}\eta_{k+1}^{2}\right)=\frac{R_{\star}}{\epsilon}\sum_{k=1}^{t}\eta_{k+1}^{2}.$

Therefore, by controlling the learning rate small enough such that
$\frac{R_{\star}}{\epsilon}\sum_{k=1}^{t}\eta_{k+1}^{2}\leq\delta$, and the
fact that $(\tilde{E}_{k})_{k=1}^{t}$ are disjoint, we could conclude that

$\mathbb{P}\left[E_{t}\right]=\mathbb{P}\left[\bigcap_{k=1}^{t}\tilde{E}_{k}^{c}\right]=1-\mathbb{P}\left[\bigcup_{k=1}^{t}\tilde{E}_{t}\right]=1-\sum_{k=1}^{t}\mathbb{P}\left[\tilde{E}_{k}\right]\geq
1-\delta.$

∎

Now, we are ready to put everything together.

###### Proof of Theorem 4.5.

First, we have

$\mathbb{P}\left[\Omega_{\mathcal{U}}\right]=\mathbb{P}\left[\bigcap_{t=1}^{\infty}\Omega_{t}\right]=\inf_{t\in\mathbb{N}}\mathbb{P}\left[\Omega_{t}\right]\geq\inf_{t\in\mathbb{N}}\mathbb{P}\left[E_{t-1}\right]\geq
1-\delta,$

where the second-to-last inequality follows from the fact that
$E_{t-1}\subset\Omega_{t}$ for every $t\in\mathbb{N}$, and the last inequality
follows from Lemma M.2. Next, by (23) and (24), we have

$\mathbb{E}\left[\mathds{1}_{\Omega_{n}}\left(\eta_{t+1}\xi_{t+1}+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a})^{2}\right)\right]\leq\mathbb{E}\left[\eta_{t+1}\xi_{t+1}+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a})^{2}\right]\leq
5\eta_{t+1}^{2}.$

Hence, let $\bar{D}_{t}=\mathbb{E}\left[\mathds{1}_{\Omega_{t}}D_{t}\right]$,
$\rho=1-\sup\mathcal{U}$, by (22), we have

$\displaystyle\bar{D}_{t+1}$
$\displaystyle=\rho_{t}\mathbb{E}\left[\bar{D}_{t+1}~{}|~{}A_{t+1}\right]+(1-\rho_{t})\mathbb{E}\left[\bar{D}_{t+1}~{}|~{}A_{t+1}^{c}\right]$
$\displaystyle=\rho_{t}\mathbb{E}\left[\bar{D}_{t+1}~{}|~{}A_{t+1}\right]+(1-\rho_{t})\mathbb{E}\left[\bar{D}_{t}~{}|~{}A_{t+1}^{c}\right]$
$\displaystyle\leq\rho_{t}(1-2\alpha\eta_{t+1})\bar{D}_{t}+\mathbb{E}\left[\mathds{1}_{\Omega_{n}}\left(\eta_{t+1}\xi_{t+1}+\frac{1}{2}\eta_{t+1}^{2}\tilde{h}({a})^{2}\right)\right]+(1-\rho_{t})\bar{D}_{t}$
$\displaystyle\leq(1-2\rho\alpha\eta_{t+1})\bar{D}_{t}+5\eta_{t+1}^{2}.$

where the third line follows from Lemma L.2, the independence of
$\sigma(A_{t+1})$ and $\sigma(D_{t})$, and the fact that
$\Omega_{t+1}\subset\Omega_{t}$. Therefore, by Lemma L.3, we have

$\bar{D}_{t}\leq\frac{5}{2\alpha\rho\gamma-1}\frac{1}{t}+o\left(\frac{1}{t}\right)\leq\frac{6}{t},$

whenever $\alpha\rho\gamma\geq 1$ and $t$ is large enough. Also, we have

$\mathbb{E}\left[({a}_{t}-{a}^{\sharp})^{2}~{}|~{}\Omega_{\mathcal{U}}\right]\leq\frac{\mathbb{E}\left[({a}_{t}-{a}^{\sharp})^{2}\mathds{1}_{\Omega_{\mathcal{U}}}\right]}{\mathbb{P}\left[\Omega_{\mathcal{U}}\right]}\leq\frac{2}{1-\delta}\bar{D}_{t}\leq\frac{12}{1-\delta}\cdot\frac{1}{t}.$

By Jensen’s inequality, we could conclude that

$\mathbb{E}\left[\left|{a}_{t}-{a}^{\sharp}\right|~{}|~{}\Omega_{\mathcal{U}}\right]\leq\sqrt{\frac{12}{1-\delta}}\cdot
t^{-1/2}.$

Hence,

$\displaystyle\mathbb{E}\left[\left|u({a}_{t},{b})-u({a}^{\sharp},{b}^{\sharp})\right|~{}|~{}\Omega_{\mathcal{U}}\right]$
$\displaystyle\leq
L_{u}\mathbb{E}\left[\left|{a}_{t}-{a}^{\sharp}\right|~{}|~{}\Omega_{\mathcal{U}}\right]+L_{u}\mathbb{E}\left[\left|{b}_{t}-{b}^{\sharp}\right|~{}|~{}\Omega_{\mathcal{U}}\right]$
$\displaystyle\leq 4\sqrt{\frac{3}{1-\delta}}L_{u}\cdot t^{-1/2}\leq
2\sqrt{6}L_{u}\cdot t^{-1/2}.$

∎

##  Appendix N Proof of Theorem 5.1

See 5.1 First, it is straightforward to verify that $u({a},1-{a})$ is concave
w.r.t. ${a}$. By equating the gradient to $0$, we could get the following
closed-form expression of the unique maximiser

${a}^{\star}=\frac{\sqrt{g\cdot\mathbb{E}\left[p_{t}\right]}}{\sqrt{g\cdot\mathbb{E}\left[p_{t}\right]}+\sqrt{(1-g)\cdot(1-\mathbb{E}\left[p_{t}\right])}}.$
(27)

The remainder of the proofs comes from determining a martingale property for
the accumulation of $\widehat{p_{t}}$, utilising the Azuma-Hoeffding
Inequality, and exploiting the local Lipschitz properties of functions. We
first recall the Azuma-Hoeffding Inequality.

######  Theorem N.1 (Azuma-Hoeffding Inequality).

Let $(X_{t})_{t\in\mathbb{N}\cup\\{0\\}}$ be a martingale w.r.t. filtration
$(\mathcal{F}_{t\in\mathbb{N}\cup\\{0\\}})$. Suppose that $|X_{t}-X_{t-1}|\leq
c_{t}$ for all $t\in\mathbb{N}$ for non-negative $(c_{t})_{t\in\mathbb{N}}$.
Then

$\mathbb{P}\left[\left|X_{T}-X_{0}\right|>r\right]\leq
2\exp\left(-\frac{2r^{2}}{\sum^{T}_{t=1}c_{t}^{2}}\right).$

###### Proof of Theorem 5.1.

Let $\tau>0$. By unwinding Eq. 13, we have

$\overline{p_{t}}=\frac{1}{t}\sum_{t^{\prime}=1}^{t}\widehat{p_{t^{\prime}}}.$

Let $X_{0}=0$, and
$X_{t}=\sum_{t^{\prime}=1}^{t}(\widehat{p_{t^{\prime}}}-\mathbb{E}\left[p_{t}\right])$.
Note that $X_{t}=X_{t-1}+(\widehat{p_{t}}-\mathbb{E}\left[p_{t}\right])$.
Since $\widehat{p_{t}}$ is an unbiased estimator of
$\mathbb{E}\left[p_{t}\right]$ under the filtration $\mathcal{F}_{t-1}$, the
sequence $(X_{t})_{t\in\mathbb{N}\cup\\{0\\}}$ is a martingale w.r.t. to its
natural filtration $(\mathcal{F}_{t})_{t\in\mathbb{N}\cup\\{0\\}}$. Also, due
to the assumption that $w_{t}$ is bounded almost surely, each
$\widehat{p_{t^{\prime}}}$ is bounded almost surely too. Thus, for all
sufficiently large $T$, we can apply the Azuma-Hoeffding inequality to derive
that

$\mathbb{P}\left[X_{T}>r\right]\leq 2\exp\left(-\Omega(r^{2}/T)\right).$

In particular, by setting $r=\Theta(\sqrt{T\log\frac{1}{\delta}})$, the RHS of
the above inequality is at most $\delta$. By noting that
$\overline{p_{T}}=\frac{1}{T}X_{T}+\mathbb{E}\left[p_{t}\right]$, we can
conclude that with probability $1-\delta$, $\overline{p_{T}}$ lies within the
interval
$\mathbb{E}\left[p_{t}\right]\pm\Theta(T^{-1/2}\sqrt{\log\frac{1}{\delta}})$.
When $T$ is sufficiently large, this interval is a strict subset of the
interval $[\tau,1-\tau]$, so the clipping in Algorithm 2 is no longer
effective.

Thus, $a_{T}$ updated by the algorithm using Eq. 14 lies within the interval
$\psi(\mathbb{E}\left[p_{t}\right])\pm\mathcal{O}(T^{-1/2}\sqrt{\log\frac{1}{\delta}})$,
since the function $\psi$ is Lipschitz continuous locally around
$\mathbb{E}\left[p_{t}\right]$. Here, we use the assumption that both $g$ and
$\mathbb{E}\left[p_{t}\right]$ lie in the open interval $(\tau,1-\tau)$, to
ensure that ${a}^{\star}=\psi(\mathbb{E}\left[p_{t}\right])\in(\tau,1-\tau)$
too, and hence the interval
${a}^{\star}\pm\mathcal{O}(T^{-1/2}\sqrt{\log\frac{1}{\delta}})$ is a subset
of $(\tau,1-\tau)$ for all sufficiently large $T$.

Finally, the theorem follows by using the local Lipschitz continuity around
${a}^{\star}$ of the profit function. ∎