# A PDE approach for regret bounds under partial monitoring

Erhan Bayraktar  Department of Mathematics, University of Michigan
<EMAIL_ADDRESS>,  Ibrahim Ekren  Department of Mathematics, Florida State
University<EMAIL_ADDRESS>and  Xin Zhang  Department of Mathematics,
University of Vienna<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study a learning problem in which a forecaster only observes
partial information. By properly rescaling the problem, we heuristically
derive a limiting PDE on Wasserstein space which characterizes the asymptotic
behavior of the regret of the forecaster. Using a verification type argument,
we show that the problem of obtaining regret bounds and efficient algorithms
can be tackled by finding appropriate smooth sub/supersolutions of this
parabolic PDE.

E. Bayraktar is partially supported by the National Science Foundation under
grant DMS-2106556 and by the Susan M. Smith chair.

I. Ekren is supported in part by NSF Grant DMS 2007826.

##  1\. Introduction

In this paper, we study a zero-sum game between a forecaster and an adversary.
At each round, the forecaster chooses an action between $K\geq 2$ alternative
actions based on his partial observations aiming at performing as well as the
best constant strategy, while the adversary aims at maximizing the
forecaster’s regret. Our problem is motivated by _prediction with expert
advice_ and _bandit problems_ (see e.g. [13, 9]), which are fundamental
problems in online learning and sequential decision making. The main
difference between prediction with expert advice and bandit problem is the
information observed by the forecaster. In prediction with expert advice
problems, the forecaster can monitor the outcomes of each alternative action,
whereas in bandit problems, the forecaster can only observe the outcome of the
action chosen. Thus, the former problem is a full information game whereas the
latter is a bandit game (see e.g. [1, 2]).

The most commonly used algorithm for decision making and prediction problem is
the so-called _multiplicative weights algorithm_ , which assigns initial
weights to each expert, update these weights multiplicatively and iteratively
based on their performance, and randomly choose experts according to their
weights. This simple algorithm is widely used and has been proven efficient in
practice. However, it cannot provide accurate regret bounds and best
strategies for the forecaster. In [18], techniques from partial differential
equations were first employed to understand asymptotic behavior of prediction
of expert advice problems. Since then, it became popular and has been proven
powerful in certain problems, see e.g. [17, 23, 24, 6, 7, 5, 8, 22, 26, 21].

In full information games, these papers rely on the fact that the difference
$(X^{i}_{t})_{i=1,\ldots,N}=(G^{i}_{t}-G_{t})_{i=1,\ldots,N}\in{\mathbb{R}}^{K}$
between the gain $G_{t}$ of the forecaster and the gain $G^{i}_{t}$ of each
action $i$ is a natural state variable for the dynamic game between the
forecaster and the adversary. Thus, the minimax regret of the forecaster
satisfies a finite dimensional dynamic programming principle whose scaling
limit is a parabolic partial differential equation on ${\mathbb{R}}^{N}$. For
bandit games or in the presence of partial information such methodology cannot
be applied. Indeed, due to partial information, the natural state variable for
the dynamic programming principle is the set of probability distributions on
${\mathbb{R}}^{N}$ which encodes the distribution $m_{t}$ of $X_{t}$
conditional on the information of the forecaster. Thus, with partial
information, the fundamental problem is to understand the dynamics of $m_{t}$
and how these dynamics behave in the long-time regime.

Our main contribution consists in showing that the update of the conditional
distribution between two consecutive time steps from $m_{t}$ to $m_{t+1}$
admits a scaling limit that can be described using partial differential
equations in the Wasserstein space. The equations we obtain are fully
nonlinear versions of the PDEs appearing in mean-field games and Mckean-Vlasov
control problems, see e.g. [11, 15, 3]. This novel relation between the
discrete-time bandit problem and the continuous-time equations comes from the
fact that in the game we study, the updated measure $m_{t+1}$ can be written
as a push-forward operator on $m_{t}$, i.e. $m_{t+1}=(Id+Y_{t})\sharp m_{t}$
where $Y_{t}$ is a (random) function describing the feature learned by the
forecaster on $[t,t+1]$. If the game is played $T$ times and if we rescale the
problem with its natural $\sqrt{T}$ scaling, the update of the $m_{t}$ can be
written as $m_{t+\frac{1}{T}}=(Id+\frac{Y_{t}}{\sqrt{T}})\sharp m_{t}$. In the
long-time regime, i.e., as $T\to\infty$, by the definition of the Wasserstein
derivative (see [11, Proposition 2.3]), we obtain that for any smooth function
$U$, we have the expansion

$U\left(m_{t+\frac{1}{T}}\right)=U\left(m_{t}\right)+\frac{1}{\sqrt{T}}\int
D_{m}U(m_{t},x)Y_{t}(x)\,m(dx)+\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{\scalebox{0.7}{$\scriptscriptstyle\mathcal{O}$}}\left(\frac{1}{\sqrt{T}}\right).$

Thus, the impact of the Bayesian update of the distribution $m_{t}$ can be
characterized in the long-time regime using the Wasserstein derivative
$D_{m}U$. In fact, we derive a second order expansion of
$U(m_{t+\frac{1}{T}})$ involving the derivatives $D_{x}D_{m}U$ and
$D_{mm}^{2}U$ which allows us to heuristically exhibit a second order
parabolic equation of type

(1.1) $\displaystyle 0$ $\displaystyle=\partial_{t}U(t,m)$
$\displaystyle+F\left(\int D_{m}U(t,m,x)m(dx),\int
D_{x}D_{m}U(t,m,x)m(dx),\iint D^{2}_{mm}U(t,m,x,y)m(dx)m(dy)\right)$

which is expected to govern the dynamics of the prediction problem in the
long-time regime. In this equation, the unknown is the function $U$, $F$ is a
function that can be explicitly computed from the Bayes’ rule, and the
derivatives are defined as in [11, 15].

The equation (1.1) gives simple methods to obtain algorithms and regret bounds
for the long-time regime of the prediction problem with partial information.
Indeed, using a verification type argument we show that the gradient $D_{m}U$
of any smooth supersolution $\phi$ of (1.1) satisfying some growth condition
yields to an algorithm that guarantees an upper bound for regret of order
$\phi(0,\delta_{0})\sqrt{T}$ where $\delta_{0}$ is the Dirac mass at $0$. A
similar result also holds for appropriate subsolutions.

Due to the nonlinearity on the second derivative term $D_{mm}^{2}U$,
wellposedness of viscosity solutions for (1.1) is not available in the
literature. Hence, the questions of establishing appropriate comparison result
for viscosity solutions and obtaining the exact growth of the regret as for
example in [18] are left for future research.

The rest of paper is organized as follows. In Section 2, we formulate our
problem and show that the value function of the game depends only on the law
$m_{t}$ of $X_{t}$ conditional on the information of the agents. Then, using
Bayes’ rule, we compute explicitly the update of beliefs and prove a dynamic
programming principle. In Section 3, by properly rescaling the value function
and using differential calculus on the space of measures, we heuristically
obtain a limiting PDE of type (1.1) on the Wasserstein space. In Section 4 and
5, using smooth supersolutions and subsolutions of the PDE, we construct
strategies for the forecaster and the adversary, and find upper and lower
bounds of expected regret.

###  1.1. Notations

For any positive integer $K$, define $[K]=\\{1,\dotso,K\\}$, and
$\mathcal{S}_{K}$ to be the set of positive semidefiniete $K\times K$
matrices. $Id$ stands for the identity mapping of appropriate dimension. For
any $x\in{\mathbb{R}}^{K}$, denote its $i$-th coordinate by $x^{i}$. Let
$\\{e_{i}:\,i=1,\dotso,K\\}$ be the canonical basis of ${\mathbb{R}}^{K}$, and
for any $j\subset[K]$, denote $e_{j}=\sum_{i,i\in j}e_{i}$ and
$e=\sum_{i=1}^{K}e_{i}$.

We fix $K\geq 2$ and denote by ${\mathcal{P}}_{2}({\mathbb{R}}^{K})$ the set
of probability measures $m$ on ${\mathbb{R}}^{K}$ such that
$\int|x|^{2}\,m(dx)<\infty$. For any $v\in{\mathbb{R}}^{K}$,
$\lambda\in{\mathbb{R}}$, and $m\in{\mathcal{P}}_{2}({\mathbb{R}}^{K})$, we
define the measures $m_{\sharp v}:=(Id+v)\sharp m$ and $m^{*\lambda}$ via

$\displaystyle\int f(x)\,m_{\sharp v}(dx)$ $\displaystyle=\int f(x+v)\,m(dx),$
$\displaystyle\int f(x)\,m^{*\lambda}(dx)$ $\displaystyle=\int f(\lambda
x)\,m(dx)\mbox{ for all }f\mbox{ continuous and bounded}.$

Additionally, for any function $f$ and
$m\in{\mathcal{P}}_{2}({\mathbb{R}}^{K})$, we denote

$\displaystyle f([m]):=\int f(x)\,m(dx).$

##  2\. Formulation of the problem

Our online prediction problem with partial observation can be described as a
$T$-round game, played by a forecaster in an adversarial environment. Suppose
that there are $K$ actions. At each round $t$, the forecaster chooses an
action $I_{t}\in[K]$, and independently the adversary chooses the reward
$J^{i}_{t}$ of action $i$ to be $0$ or $1$, i.e., $J_{t}\in\\{0,1\\}^{K}$.
Then the total gain of the forecaster $G_{t}$ and the total gain $G_{t}^{i}$
of action $i$ evolve as

$\displaystyle G_{t+1}-G_{t}={\mathbf{1}}_{I_{t}\in J_{t}},$ $\displaystyle
G^{i}_{t+1}-G^{i}_{t}={\mathbf{1}}_{i\in J_{t}},\,\,\,i=1,\dots,K.$

The goal of the forecaster is to design a robust strategy that performs as
well as the best constant strategy under any adversarial environment, i.e., to
minimize $\max\limits_{Adversary}{\mathbb{E}}[\max_{i}X_{T}^{i}]$, where
$X_{t}^{i}:=G^{i}_{t}-G_{t}$ is the state variable evolving as

$\displaystyle X_{t+1}-X_{t}:=e_{J_{t}}-{\mathbf{1}}_{I_{t}\in
J_{t}}e\in{\mathbb{R}}^{K}.$

Both the forecaster and the adversary are allowed to adopt randomized
strategies. At each round $t$, they decide on distributions $b_{t}$ of $I_{t}$
and $a_{t}$ of $J_{t}$ respectively. If we allow both agents to observe the
outcomes of $I_{t}$ and $J_{t}$, this problem is the classical prediction with
expert advice problem in the adversarial setting, see for example [16, 13, 19,
18].

Let us now describe information observed by the forecaster and his admissible
strategies in the partial information problem we aim to study. At initial time
$t=0$, both the adversary and the forecaster get informed of the distribution
$m_{0}$ of $X_{0}$. For any $t\geq 0$, the random variable

$\displaystyle Y_{t}:={\mathbf{1}}_{I_{t}\in
J_{t}}{I_{t}}-{\mathbf{1}}_{I_{t}\not\in J_{t}}{I_{t}}\in\\{\pm i\\}$

indicates whether the forecaster makes a good decision or not. Both players
can observe the law of adversary’s control $a_{t-1}$ and the indicator
$y_{t-1}$. Their accumulated information is given by

$\displaystyle
h_{t}:=(m_{0},a_{0},y_{0}\dotso,a_{t-1},y_{t-1})\in\mathcal{H}_{t},\quad(h_{0}:=m_{0}\in\mathcal{H}_{0}),$

where
$\mathcal{H}_{t}:={\mathcal{P}}({\mathbb{R}}^{K})\times\left({\mathcal{P}}(\\{0,1\\}^{K})\times\\{\pm
i\\}\right)^{t}.$ The strategies of the forecaster and the adversary are
measurable functions $\beta_{t}:\mathcal{H}_{t}\to{\mathcal{P}}([K])$ and
$\alpha_{t}:\mathcal{H}_{t}\to{\mathcal{P}}(\\{0,1\\}^{K})$ respectively.
Define $\mathcal{A}$ to be the set of all possible strategies
$\alpha:=(\alpha_{0},\alpha_{1},\dotso,\alpha_{T-1})$, and $\mathcal{B}$
similarly.

Suppose this game starts from time $t$ with an initial distribution
$m\in{\mathcal{P}}({\mathbb{R}}^{K})$. Then given any strategies
$\alpha\in\mathcal{A}$, $\beta\in\mathcal{B}$, the regret for the forecaster
is given by

$\displaystyle\gamma_{T}(t,m,\alpha,\beta):={\mathbb{E}}^{m,\alpha,\beta}[\max_{i}X^{i}_{T}\,|\,X_{t}\sim
m].$

From the perspective of the forecaster, we aim at solving a minimax problem

(2.1) $\displaystyle
v_{T}(t,m):=\inf_{\beta\in\mathcal{B}}\sup_{\alpha\in\mathcal{A}}\gamma_{T}(t,m,\alpha,\beta),$

and we denote this two player game by $\Gamma_{T}(t,m)$.

######  Remark 2.1.

(i) This formulation is motivated by the classical bandit problems, see for
example [13, 9]. Similar to the bandit problems, both agents have access to
the same partial information and they simultaneously choose their strategies
to be played at each round. Before each round, our adversary has the same
information as the non-oblivious adversary of [1]. However, unlike the bandit
problems where the agents only observe $Y_{t}$, after each round, the
forecaster also learns the strategy $a_{t}$ chosen by the adversary in the
previous round. Therefore, both players does not get access to state variable
$X_{t}$, but still can compute the same update of its law conditional to a
common filtration.

(ii) We note that the observation of $a_{t}$ by the forecaster has a practical
implication in terms of design of recommender systems. In the problem that we
envision, the forecaster recommends successively one item among $K$
alternatives to a sequence of users. The forecaster’s strategy is the choice
of a randomization $b_{t}\in{\mathcal{P}}([K])$ which leads to the realization
of a random variable $I_{t}\in[K]$ representing the recommendation of the
forecaster. A sequence of users arrive and decide whether or not they accept
the successive recommendations of the forecaster. We identify each user with
$a_{t}\in{\mathcal{P}}(\\{0,1\\}^{K})$ so that the realization of random
variable $J_{t}\in\\{0,1\\}^{K}$ represents the random choice that each
successive user makes. Thus, unlike stochastic bandit problems, $a_{t}$ is
chosen adversarially at each round and learned by the forecaster after the
round. In this context, the assumption that the forecaster learns $a_{t}$
means that after proposing $I_{t}$, the forecaster learns the identity of the
user $a_{t}$.

(ii) In our context, since the forecaster learns $a_{t}$, he can update
$m_{t}$ via Bayes’ rule. This update is impossible in the classical bandit
problems. An interesting question that is left for future research is to
extend our PDE tools to allow such an uncertainty on the update procedure of
the conditional distribution.

###  2.1. Dynamic programming principle

In this subsection, we establish the dynamic programming principle for the
game (2.1), and reduce controls $\alpha,\beta$ to functions of conditional
distribution of the state $X$. Let us first compute the distribution of $X$,
i.e., belief, given prior information. Suppose the current distribution is $m$
and $X$ is a random variable with distribution $m$. We denote $\Delta X$ the
change of $X$ between two rounds. The players choose strategies
$a\in{\mathcal{P}}(\\{0,1\\}^{K})$ and $b\in{\mathcal{P}}([K])$ respectively,
and receive signal $y\in\\{\pm i\\}$. We denote by ${\mathcal{L}}^{a,b}$ the
distribution of a random variable and by ${\mathbb{P}}^{a,b}$ the probability
of an event given the strategies of the agents. We omit the superscripts $a$
or $b$ if this dependence is clear from the context. We also denote by

$l(m,a,y):=\mathcal{L}^{a}(X+\Delta X|X\sim
m,Y=y)\in{\mathcal{P}}({\mathbb{R}}^{K})$

the Bayesian update of the distribution.

We will compute the explicit formula of $l(m,a,y)$ in the next Lemma. For any
$a\in{\mathcal{P}}(\\{0,1\\}^{K})$, $b\in{\mathcal{P}}([K])$, denote

$\displaystyle\hat{a}(i):=\sum_{j,i\in
j}a(j),\quad\hat{a}(-i):=\sum_{j,i\notin j}a(j),\quad\forall\,i\in[K].$

######  Proposition 2.1.

Given $a\in{\mathcal{P}}(\\{0,1\\}^{K})$ and the distribution
$m\in{\mathcal{P}}({\mathbb{R}}^{K})$, we have that

$\displaystyle l(m,a,i)=\sum_{j,i\in
j}\left(\frac{a(j)}{\hat{a}(i)}m\right)_{\sharp-e_{j^{c}}},\quad
l(m,a,-i)=\sum_{j,i\notin j}\left(\frac{a(j)}{\hat{a}(-i)}m\right)_{\sharp
e_{j}}.$

We make the convention in these expressions that
$l(m,a,y)=\delta_{\mathbf{0}}\in{\mathcal{P}}({\mathbb{R}}^{K})$ whenever
$\hat{a}(y)=0$.

###### Proof.

For $j\subset[K]$ and $i\in[K]$, it can be easily verified that

$\displaystyle{\mathbb{P}}(\Delta X=e_{j},Y=-i,X\in dx)$
$\displaystyle={\mathbf{1}}_{i\notin j}a(j)b(i)m(dx)$
$\displaystyle{\mathbb{P}}(\Delta X=-e_{j^{c}},Y=i,X\in dx)$
$\displaystyle={\mathbf{1}}_{i\in j}a(j)b(i)m(dx)$
$\displaystyle{\mathbb{P}}(Y=i)$ $\displaystyle=b(i)\sum_{k,i\in k}a(k)$
$\displaystyle{\mathbb{P}}(Y=-i)$ $\displaystyle=b(i)\sum_{k,i\notin k}a(k)$
$\displaystyle{\mathbb{P}}(\Delta X=e_{j},X\in dx\,|\,Y=-i)$
$\displaystyle=\frac{{\mathbf{1}}_{i\notin j}a(j)m(dx)}{\sum_{k,i\notin
k}a(k)}$ $\displaystyle{\mathbb{P}}(\Delta X=-e_{j^{c}},X\in dx\,|\,Y=i)$
$\displaystyle=\frac{{\mathbf{1}}_{i\in j}a(j)m(dx)}{\sum_{k,i\in k}a(k)}.$

Therefore, conditioning on $Y$, the distribution of $X+\Delta X$ is given by

$\displaystyle{\mathbb{P}}\left[(X+\Delta X)\in dx\,|\,Y=i\right]$
$\displaystyle=\sum_{j,i\in j}{\mathbb{P}}\left[X\in d(x+e_{j^{c}}),\Delta
X=-e_{j^{c}}\,|\,Y=i\right]$ $\displaystyle=\sum_{j,i\in
j}\frac{a(j)m(d(x+e_{j^{c}}))}{\hat{a}(i)},$ $\displaystyle=\sum_{j,i\in
j}\left(\frac{a(j)}{\hat{a}(i)}m\right)_{\sharp-e_{j^{c}}}(dx),$

and

$\displaystyle{\mathbb{P}}\left[(X+\Delta X)\in dx\,|\,Y=-i\right]$
$\displaystyle=\sum_{j,i\notin j}{\mathbb{P}}\left[X\in d(x-e_{j}),\Delta
X=e_{j}\,|\,Y=-i\right]$ $\displaystyle=\sum_{j,i\notin
j}\frac{a(j)m(d(x-e_{j}))}{\hat{a}(-i)}$ $\displaystyle=\sum_{j,i\notin
j}\left(\frac{a(j)}{\hat{a}(-i)}m\right)_{\sharp e_{j}}(dx).$

∎

The following theorem proves a dynamic programming principle showing that one
can solve (2.1) with a backward induction.

######  Theorem 2.1.

For any distribution $m\in{\mathcal{P}}({\mathbb{R}}^{K})$ and
$T\in{\mathbb{N}}$ we have that

$\displaystyle v_{T}(t,m)=$
$\displaystyle\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\left(\sum_{i=1}^{K}b(i)\hat{a}(i)v_{T}(t+1,l(m,a,i))\right.$
(2.2)
$\displaystyle+\left.\sum_{i=1}^{K}b(i)\hat{a}(-i)v_{T}(t+1,l(m,a,-i))\right),$

where $b(i)\hat{a}(i)$, $b(i)\hat{a}(-i)$ represent the probability of
receiving signal $i$, $-i$ respectively, and $l(m,a,\pm i)$ is the update of
beliefs.

###### Proof.

The equation (2.1) holds trivially for $t=T-1$. Suppose it is true for $t+1$.
Let us prove it for $t$. Denote by $v$ the value of the right hand side of
(2.1). For any $\alpha\in\mathcal{A}$ and $\beta\in\mathcal{B}$, denote
$\alpha_{t+1:T}=\\{\alpha_{t+1},\dotso,\alpha_{T-1}\\}$,
$\beta_{t+1:T}=\\{\beta_{t+1},\dotso,\beta_{T-1}\\}$. It is clear that

$\displaystyle\gamma_{T}(t,m,\alpha,\beta)=$
$\displaystyle\sum_{i=1}^{K}\sum_{k:i\in
k}\beta_{t}(i)\alpha_{t}(k)\gamma_{T}(t+1,l(m,\alpha_{t},i),\alpha_{t+1:T},\beta_{t+1:T})$
(2.3) $\displaystyle+\sum_{i=1}^{K}\sum_{k:i\notin
k}\beta_{t}(i)\alpha_{t}(k)\gamma_{T}(t+1,l(m,\alpha_{t},-i),\alpha_{t+1:T},\beta_{t+1:T}),$

where $l(m,\alpha_{t},\pm i)$ is the conditional distribution of $X_{t+1}$.
For the game $\gamma_{T}(t+1,l(m,\alpha_{t},\pm i))$, due to our induction
hypothesis, the value of this game exists and is just
$v_{T}(t+1,l(m,\alpha_{t},\pm i))$. Taking supremum over $\alpha$ on both
sides of (2.1), it can be easily seen that

$\displaystyle\sup_{\alpha}\gamma_{T}(t,m,\alpha,\beta)\geq$
$\displaystyle\sup_{\alpha_{t}}\left(\sum_{i=1}^{K}\sum_{k:i\in
k}\beta_{t}(i)\alpha_{t}(k)v_{T}(t+1,l(m,\alpha_{t},i))\right.$
$\displaystyle+\left.\sum_{i=1}^{K}\sum_{k:i\notin
k}\beta_{t}(i)\alpha_{t}(k)v_{T}(t+1,l(m,\alpha_{t},-i))\right).$

Taking infimum over $\beta$, we conclude that $v_{T}(c,m)\geq v$.

Then we prove that for any $\epsilon>0$, there exists a robust strategy
$\beta^{*}$ of the forecaster such that

(2.4)
$\displaystyle\sup_{\alpha}\gamma_{T}(t,m,\alpha,\beta^{*})<v+2\epsilon.$

Take $\beta_{t}^{*}\in{\mathcal{P}}([K])$ with the property that

$\displaystyle v+\epsilon>$
$\displaystyle\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\left(\sum_{i=1}^{K}\sum_{k:i\in
k}\beta_{t}^{*}(i)a(k)v_{T}(t+1,l(m,a,i))\right.$
$\displaystyle+\left.\sum_{i=1}^{K}\sum_{k:i\notin
k}\beta_{t}^{*}(i)a(k)v_{T}(t+1,l(m,a,-i))\right).$

By induction hypothesis, for any belief $l(m,a,\pm i)$, the forecaster can
choose a strategy $\beta_{t+1:T}^{*}$ such that

$\displaystyle v_{T}(t+1,l(m,a,\pm
i))+\epsilon>\sup_{\alpha_{t+1:T}}\gamma_{T}(t+1,l(m,a,\pm
i),\alpha_{t+1:T},\beta_{t+1:T}^{*}).$

Taking $\beta^{*}=(\beta_{t}^{*},\beta^{*}_{t+1:T})$, clearly it is measurable
and satisfies (2.4). ∎

##  3\. Heuristic expansion of the rescaled value function

Let us define the rescaled value functions

$\displaystyle u^{T}(s,m):=\frac{1}{\sqrt{T}}v_{T}\left({\lceil
sT\rceil},m^{*\sqrt{T}}\right),$

and equivalently

$\displaystyle v_{T}({\lceil
sT\rceil},m)=\sqrt{T}u^{T}\left(s,m^{*\sqrt{T^{-1}}}\right).$

For any $a\in{\mathcal{P}}(\\{0,1\\}^{K})$ and belief
$m\in{\mathcal{P}}({\mathbb{Z}}^{K})$, denote

(3.1) $\displaystyle A^{a,m}_{i,\sqrt{T}}$ $\displaystyle=\left({\sum_{j,i\in
j}\left(\frac{a(j)}{\hat{a}(i)}m^{*\sqrt{T}}\right)_{\sharp-
e_{j^{c}}}}\right)^{*\frac{1}{\sqrt{T}}},\,\,\,\,\,A^{a,m}_{-i,\sqrt{T}}$
$\displaystyle=\left(\sum_{j,i\notin
j}\left(\frac{a(j)}{\hat{a}(-i)}m^{*\sqrt{T}}\right)_{\sharp
e_{j}}\right)^{*\frac{1}{\sqrt{T}}}.$

Then due to (2.1), it holds that

$\displaystyle u^{T}\left(s-\frac{1}{T},m\right)=$
$\displaystyle\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\bigg{(}\sum_{i}b(i)\hat{a}(i)u^{T}\left(s,A^{a,m}_{i,\sqrt{T}}\right)$
(3.2)
$\displaystyle+\sum_{i}b(i)\hat{a}(-i)u^{T}\left(s,A^{a,m}_{-i,\sqrt{T}}\right)\bigg{)},$

with the terminal condition

$\displaystyle u^{T}(1,m)=\int_{x\in{\mathbb{R}}^{K}}\max_{i}{x^{i}}\,m(dx).$

Now we want to derive a limit for (3) as $T\to\infty$. This derivation
requires us to take derivatives in the direction of $A^{a,m}_{i,\sqrt{T}}-m$
and $A^{a,m}_{-i,\sqrt{T}}-m$ in the Wasserstein space. Let us introduce the
differentiability of functions over the Wasserstein space as defined in [11,
12].

A function $u:{\mathcal{P}}_{2}({\mathbb{R}}^{K})\mapsto{\mathbb{R}}$ is said
to be Fréchet differentiable if there exists a continuous function

$\frac{\delta u}{\delta
m}:{\mathcal{P}}_{2}({\mathbb{R}}^{K})\times{\mathbb{R}}^{K}\mapsto{\mathbb{R}}$

so that for all $(m,m^{\prime})\in{\mathcal{P}}_{2}({\mathbb{R}}^{K})$, we
have that

$\displaystyle\lim_{h\to
0}\frac{u(m+h(m^{\prime}-m))-u(m)}{h}=\int\frac{\delta u}{\delta
m}(m,x)\,(m^{\prime}-m)(dx).$

Whenever $\frac{\delta u}{\delta m}$ is differentiable in $x$, we also define

$\displaystyle D_{m}u(m,x)=D_{x}\frac{\delta u}{\delta
m}(m,x)\in{\mathbb{R}}^{K}.$

Similarly to [11, 14], we can also define $D_{x}D_{m}u(m,x)$,
$D^{2}_{mm}u(m,x,y)$.

######  Definition 3.1.

A function $u:{\mathcal{P}}_{2}({\mathbb{R}}^{K})\to{\mathbb{R}}$ is said to
be $\mathcal{C}^{1}$ if $D_{m}u(m,x)$ is continuous and has at most quadratic
growth in $x$, i.e.,

$\displaystyle|D_{m}u(m,x)|\leq C(1+|x|^{2}).$

It is said to be $\mathcal{C}^{2}$ if $D_{x}D_{m}u(m,x)$ and
$D^{2}_{mm}u(m,x,y)$ are continuous, and have at most quadratic growth in $x$
and $(x,y)$ respectively.

It is shown in [11, Proposition 2.3] that $D_{m}u$ can be understood as a
derivative of $u$ along push-forward directions, meaning that for all Borel
measurable bounded vector field $\phi:{\mathbb{R}}^{K}\mapsto{\mathbb{R}}^{K}$
we have

$\lim_{h\to 0}\frac{u((Id+h\phi)_{\sharp}m)-u(m)}{h}=\int
D_{m}u(m,x)\phi(x)\,m(dx).$

Due to the expression of $A^{a,m}_{i,\sqrt{T}}$ and $A^{a,m}_{-i,\sqrt{T}}$,
we need to take derivatives in the directions
$\left(Id+\frac{e_{j}}{T}\right)$ which are constant vector fields. However,
the presence of terms $\frac{a(j)}{\hat{a}(i)}\sharp m$ in (3.1) is a
randomization among the directions of the vector fields. The following
Proposition shows that at the leading order, we can simplify these
perturbations by averaging over these different vector fields. We recall the
notational convention that for all
$m^{\prime}\in{\mathcal{P}}_{2}({\mathbb{R}}^{K})$

$\displaystyle D_{m}u(m,[m^{\prime}])$ $\displaystyle=\int
D_{m}u(m,x)\,m^{\prime}(dx)\in{\mathbb{R}}^{K}.$

######  Proposition 3.1.

Suppose $u\in\mathcal{C}^{1}({\mathcal{P}}({\mathbb{R}}^{K});{\mathbb{R}})$.
Then for all $a\in{\mathcal{P}}(\\{0,1\\}^{K})$ and $i\in[K]$, we have that

$\displaystyle\lim_{T\to\infty}\sqrt{T}\left(u(A^{a,m}_{i,\sqrt{T}})-u(m)\right)$
$\displaystyle=-{\mathcal{V}}_{a,i}^{\top}D_{m}u\left(m,[m]\right)$
$\displaystyle\lim_{T\to\infty}\sqrt{T}\left(u(A^{a,m}_{-i,\sqrt{T}})-u(m)\right)$
$\displaystyle={\mathcal{V}}_{a,-i}^{\top}D_{m}u\left(m,[m]\right),$

where

$\displaystyle{\mathcal{V}}_{a,i}:=\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}\in{\mathbb{R}}^{K},\quad{\mathcal{V}}_{a,-i}:=\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}\in{\mathbb{R}}^{K}.$

######  Remark 3.1.

Note that $-{\mathcal{V}}_{a,i}\in{\mathbb{R}}^{K}$ (resp.
${\mathcal{V}}_{a,-i}\in{\mathbb{R}}^{K}$ ) represents the increase in the
expectation of $X_{t}$ given the information that $Y=i$ (resp. $Y=-i$) and the
adversary’s strategy $a$.

###### Proof.

Let us only compute the derivative in the direction of
$A^{a,m}_{i,\sqrt{T}}-m$. By the definition of $\frac{\delta u}{\delta m}$,
denoting $\widetilde{A}_{s,\sqrt{T},m}=m+s(A^{a,m}_{i,\sqrt{T}}-m)$ we have
that

$\displaystyle\sqrt{T}(u(A^{a,m}_{i,\sqrt{T}})-u(m))$
$\displaystyle=\sqrt{T}\int_{0}^{1}\int\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},x\right)\,(A^{a,m}_{i,\sqrt{T}}-m)(dx)\,ds$
$\displaystyle=\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}\sqrt{T}\int_{0}^{1}\int\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},x-\frac{e_{j^{c}}}{\sqrt{T}}\right)-\frac{\delta
u}{\delta m}\left(\widetilde{A}_{s,\sqrt{T},m},x\right)\,m(dx)\,ds,$

and thus

$\displaystyle\lim_{T\to\infty}\sqrt{T}\left(u(A^{a,m}_{i,\sqrt{T}})-u(m)\right)=-\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}\int e_{j^{c}}^{\top}D_{m}u\left(m,x\right)\,m(dx).$

∎

We can now give the second order expansion along $T\mapsto
u(A^{a,m}_{y,\sqrt{T}})$ for all $y=\pm i$.

######  Proposition 3.2.

Suppose $u\in C^{2}({\mathcal{P}}({\mathbb{R}}^{K});{\mathbb{R}})$. Then we
have that

$\displaystyle\lim_{T\to\infty}T\left(u(A^{a,m}_{i,\sqrt{T}})-u(m)+\frac{1}{\sqrt{T}}{\mathcal{V}}_{a,i}^{\top}D_{m}u\left(m,[m]\right)\right)$
(3.3) $\displaystyle=\frac{1}{2}\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}^{\top}D_{x}D_{m}u\left(m,[m]\right)e_{j^{c}}$
$\displaystyle\,\,\,+{\frac{1}{2}}\sum_{k,j:i\in k,i\in
j}\frac{a(j)}{\hat{a}(i)}\frac{a(k)}{\hat{a}(i)}{e_{j^{c}}^{\top}}D^{2}_{mm}u\left(m,[m],[m]\right)e_{k^{c}},$

and

$\displaystyle\lim_{T\to\infty}T\left(u(A^{a,m}_{-i,\sqrt{T}})-u(m)-\frac{1}{\sqrt{T}}{\mathcal{V}}_{a,-i}^{\top}D_{m}u\left(m,[m]\right)\right)$
(3.4) $\displaystyle=\frac{1}{2}\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}^{\top}D_{x}D_{m}u\left(m,[m]\right)e_{j}$
$\displaystyle+{\frac{1}{2}}\sum_{k,j:i\notin k,i\notin
j}\frac{a(j)}{\hat{a}(-i)}\frac{a(k)}{\hat{a}(-i)}{e_{j}^{\top}}D^{2}_{mm}u\left(m,[m],[m]\right)e_{k}$

######  Remark 3.2.

The Propositions 3.1 and 3.2 show that, at the leading orders, the impact of
the scaled update $A^{a,m}_{y,\sqrt{T}}$ of $m$ on a smooth function $u$ can
be characterized by multiplication of $D_{m}u$, $D_{x}D_{m}u$, and
$D_{mm}^{2}u$ with some matrices depending only on $a$.

###### Proof.

Using the [11, Equality (25)], we have

$\displaystyle
T\left(u(A^{a,m}_{i,\sqrt{T}})-u(m)+\frac{1}{\sqrt{T}}\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}\int
e_{j^{c}}^{\top}D_{m}u\left(m,x\right)dm(x)\right)$
$\displaystyle=\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}T\int_{0}^{1}\int\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},x-\frac{e_{j^{c}}}{\sqrt{T}}\right)-\frac{\delta
u}{\delta m}\left(\widetilde{A}_{s,\sqrt{T},m},x\right)$
$\displaystyle\,\,\,\,\,\,\,+\frac{e_{j^{c}}^{\top}}{\sqrt{T}}D_{x}\frac{\delta
u}{\delta m}u\left(m,x\right)dm(x)ds.$

Let us compute the limit of integrand on the right hand side. By Taylor
expansion on $x$, it can ben seen that

$\displaystyle T\left(\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},x-\frac{e_{j^{c}}}{\sqrt{T}}\right)-\frac{\delta
u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},x\right)+\frac{e_{j^{c}}^{\top}}{\sqrt{T}}D_{x}\frac{\delta
u}{\delta m}u\left(m,x\right)\right)$
$\displaystyle=\frac{1}{2}e_{j^{c}}^{\top}D^{2}_{x}\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},\widetilde{x}_{T}\right)e_{j^{c}}-\sqrt{T}{e_{j^{c}}^{\top}}\left(D_{x}\frac{\delta
u}{\delta m}\left(\widetilde{A}_{s,T,m},x\right)-D_{x}\frac{\delta u}{\delta
m}u\left(m,x\right)\right)$

where $\widetilde{x}_{T}$ is some point on the line segment joining $x$ and
$x-\frac{e_{j^{c}}}{\sqrt{T}}$. Denoting
$\widetilde{A}_{r,s,\sqrt{T},m}=m+r(\widetilde{A}_{s,\sqrt{T},m}-m)$, the
right hand side of the above equation equals to

$\displaystyle\frac{1}{2}e_{j^{c}}^{\top}D^{2}_{x}\frac{\delta u}{\delta
m}\left(\widetilde{A}_{s,\sqrt{T},m},\widetilde{x}_{T}\right)e_{j^{c}}-s\sum_{k:i\in
k}\frac{a(k)}{\hat{a}(i)}\int_{0}^{1}\int$
$\displaystyle\sqrt{T}\bigg{(}{e_{j^{c}}^{\top}}D_{x}\frac{\delta^{2}u}{\delta
m^{2}}\left(\widetilde{A}_{r,s,\sqrt{T},m},x,x^{\prime}-\frac{e_{k^{c}}}{\sqrt{T}}\right)-{e_{j^{c}}^{\top}}D_{x}\frac{\delta^{2}u}{\delta
m^{2}}\left(\widetilde{A}_{r,s,\sqrt{T},m},x,x^{\prime}\right)\bigg{)}\,dm(x^{\prime})dx.$

Letting $T\to\infty$, it converges to

$\displaystyle\frac{1}{2}e_{j^{c}}^{\top}D^{2}_{x}\frac{\delta u}{\delta
m}\left(m,x\right)e_{j^{c}}+s\sum_{k:i\in
k}\frac{a(k)}{\hat{a}(i)}{e_{j^{c}}^{\top}}\int
D^{2}_{x,x^{\prime}}\frac{\delta^{2}u}{\delta
m^{2}}u\left(m,x,x^{\prime}\right)e_{k^{c}}\,dm(x^{\prime}),$

and hence we obtain (3.3) by integrating over $x$. Similar computation yields
to (3.4). ∎

We now use (3) to obtain a formal asymptotics for $u^{T}$ as $T\to\infty$.
Assuming $u^{T}$ converges to a $\mathcal{C}^{2}$ function
$u:[0,1]\times{\mathcal{P}}({\mathbb{R}}^{K})\to{\mathbb{R}}$, the dynamic
programming principle yields to

$\displaystyle 0$
$\displaystyle=\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}b(i)\hat{a}(i)T\left(u^{T}\left(s,A^{a,m}_{i,\sqrt{T}}\right)-u^{T}\left(s-\frac{1}{T},m\right)\right)$
$\displaystyle\quad+b(i)\hat{a}(-i)T\left(u^{T}\left(s,A^{a,m}_{-i,\sqrt{T}}\right)-u^{T}\left(s-\frac{1}{T},m\right)\right).$

Using Proposition 3.1 and 3.2 for large enough $T$, we obtain that

$\displaystyle\mathcal{O}(1)=\partial_{t}u(t,m)+\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sqrt{T}\sum_{i}b(i)\left(\hat{a}(-i){\mathcal{V}}_{a,-i}-\hat{a}(i){\mathcal{V}}_{a,i}\right)^{\top}D_{m}u\left(t,m,[m]\right)$
$\displaystyle+\frac{1}{2}{b(i)}{\hat{a}(i)}\left({\mathcal{V}}_{a,i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,i}+\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j^{c}}\right)$
(3.5)
$\displaystyle+\frac{1}{2}{b(i)}{\hat{a}(-i)}\left({\mathcal{V}}_{a,-i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,-i}+\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j}\right).$

Notice that
$A^{a,m_{\sharp\epsilon{\mathbf{1}}}}_{y,\sqrt{T}}=\left(A^{a,m}_{y,\sqrt{T}}\right)_{\sharp\epsilon{\mathbf{1}}}$
for any $y\in\\{\pm i\\}$, and the final condition satisfies
$u^{T}(1,m_{\sharp\epsilon{\mathbf{1}}})=u^{T}(1,m)+\epsilon$. Therefore by
backward induction, we have
$u^{T}(t,m_{\sharp\epsilon{\mathbf{1}}})=u^{T}(t,m)+\epsilon$ for any
$t\in[0,1]$, and also in its limit as $T\to\infty$

$\displaystyle u(t,m_{\sharp\epsilon{\mathbf{1}}})=u(t,m)+\epsilon.$

Thus, thanks to [11, Proposition 2.3], we have that

$\displaystyle{\mathbf{1}}^{\top}D_{m}u(t,m,[m])=1.$

Additionally, each component of $D_{m}u(t,m,[m])$ is clearly non-negative,
which implies that $D_{m}u(t,m,[m])\in{\mathbb{R}}^{K}$ is simplex valued.
Denoting $u_{i}(t,m)$ the $i$th component of $D_{m}u\left(t,m,[m]\right)$, we
have that

$\displaystyle\sum_{i}b(i)\left(\sum_{j:i\notin
j}{a(j)}e_{j}^{\top}-\sum_{j:i\in
j}{a(j)}e_{j^{c}}^{\top}\right)D_{m}u\left(t,m,[m]\right)$
$\displaystyle=\sum_{i}b(i)\left(\sum_{j}{a(j)}e_{j}^{\top}-\sum_{j:i\in
j}{a(j)}{\mathbf{1}}^{\top}\right)D_{m}u\left(t,m,[m]\right)$ (3.6)
$\displaystyle=\sum_{j}{a(j)}\sum_{i\in j}u_{i}(t,m)-\sum_{i}b(i)\sum_{j:i\in
j}{a(j)}=\sum_{i}(u_{i}(t,m)-b(i))\sum_{j:i\in j}{a(j)}.$

Thus, in order to have the equality (3.5), the coefficients of the $\sqrt{T}$
term must be zero, i.e.,

$\displaystyle 0$
$\displaystyle=\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}b(i)\left(\hat{a}(-i){\mathcal{V}}_{a,-i}-\hat{a}(i){\mathcal{V}}_{a,i}\right)^{\top}D_{m}u\left(t,m,[m]\right)$
$\displaystyle=\inf_{b\in{\mathcal{P}}([K])}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}(u_{i}(t,m)-b(i))\sum_{j:i\in
j}{a(j)}.$

Otherwise, the first order term explodes. Therefore the forecaster is forced
to choose the strategy $b=D_{m}u\left(t,m,[m]\right)$, and we obtain the PDE

(3.7) $\displaystyle
0=\partial_{t}u(t,m)+\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}$
$\displaystyle+\frac{1}{2}{u_{i}(t,m)}{\hat{a}(i)}\left({\mathcal{V}}_{a,i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,i}+\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j^{c}}\right)$
$\displaystyle+\frac{1}{2}{u_{i}(t,m)}{\hat{a}(-i)}\left({\mathcal{V}}_{a,-i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,-i}+\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j}\right).$

######  Remark 3.3.

(i) We say $a\in{\mathcal{P}}(\\{0,1\\}^{K})$ is a balanced strategy if
$\sum\limits_{j:i\in j}a(j)$ is independent of $i$, and denote by
$\mathcal{E}$ the set of all balanced strategies. According to (3), if we
restrict $a$ in (3.5) to be balanced, the first order term vanishes for any
$b\in{\mathcal{P}}([K])$.

(ii)The standard tool to show the convergence of $u^{T}$ to the solution of
(3.7) is to use the stability and comparison of viscosity solutions, see for
example [17, 4] in the finite dimensional cases. However, a comparison result
for viscosity solution of second order PDEs on the Wasserstein space is not
available in the literature in the generality we need, see for example [10, 3,
15] and the references therein.

(iii) Because the second derivative terms $D^{2}_{mm}u$ and $D_{x}D_{m}u$ are
expected to explode as $t\to 1$, the generator of (3.7) is expected to become
discontinuous as $t\to 1$. Thus, it is more convenient to use the equation

(3.8) $\displaystyle
0=\partial_{t}u(t,m)+\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}$
$\displaystyle+\frac{1}{2}{\hat{a}(i)}\left({\mathcal{V}}_{a,i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,i}+\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j^{c}}\right)$
$\displaystyle+\frac{1}{2}{\hat{a}(-i)}\left({\mathcal{V}}_{a,-i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,-i}+\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j}\right)$

to obtain regret bounds. Indeed, any supersolution of (3.8) is clearly a
supersolution of (3.7) and the generator of (3.8) is Lipschitz continuous on
the derivatives of $u$. Thus, one can expect a simpler proof of comparison of
viscosity solutions.

##  4\. Upper bound by smooth supersolution of the PDE

In this part, we design robust strategies of the forecaster using smooth
supersolutions of (3.7). Note that (3.7) becomes simpler if $D^{2}_{mm}u=0$.
This is the case if $u$ is linear in $m$. The following Lemma uses this idea
to generate simple supersolutions to (3.7).

######  Lemma 4.1.

Let $\phi$ be a classical solution of

(4.1)
$\begin{split}&0\geq\partial_{t}\phi(t,x)+\frac{1}{2}\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left(D^{2}_{xx}\phi\left(t,x\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)\\\
&\phi(1,x)\geq\max_{i}x^{i},\,\,\,\phi(t,x+\lambda{\mathbf{1}})=\phi(t,x)+\lambda.\end{split}$

Then, the function
$\Phi:[0,1]\times{\mathcal{P}}_{2}({\mathbb{R}}^{K})\mapsto{\mathbb{R}}$
defined by

$\Phi(t,m)=\phi(t,[m]):=\int\phi(t,x)\,m(dx)$

is a smooth supersolution to (3.7) with

(4.2)
$D_{m}\Phi\left(t,m,x\right)=D_{x}\phi(t,x),\,\,D_{x}D_{m}\Phi\left(t,m,x\right)=D^{2}_{xx}\phi(t,x),\,\,D^{2}_{mm}\Phi\left(t,m,x,y\right)=0.$

###### Proof.

Using (4.2) which can be easily verified, together with the supersolution
property of $\phi$ we have that

$\displaystyle 0$
$\displaystyle\geq\partial_{t}\phi(t,[m])+\frac{1}{2}\int\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left(D^{2}_{xx}\phi\left(t,x\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)dm(x)$
$\displaystyle\geq\partial_{t}\phi(t,[m])+\frac{1}{2}\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left(D^{2}_{xx}\phi\left(t,[m]\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)$
$\displaystyle\geq\partial_{t}\Phi(t,[m])+\frac{1}{2}\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left(D_{x}D_{m}\Phi\left(t,m,[m]\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)$
$\displaystyle\geq\partial_{t}\Phi(t,[m])+\frac{1}{2}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}$
$\displaystyle\quad\quad\Phi_{i}(t,m)\,Tr\left(D_{x}D_{m}\Phi\left(t,m,[m]\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right),$

where $\Phi_{i}(t,m)$ denotes the $i$-th coordinate of $D_{m}\Phi(t,m,[m])$.
This proves the supersolution property we want. ∎

######  Remark 4.1.

It can be easily verified that smooth supersolutions of

$\displaystyle
0=\partial_{t}\phi(t,x)+\frac{1}{2}\sup_{a\in{\mathcal{P}}(\\{0,1\\}^{K})}\sum_{i}$
$\displaystyle\quad\quad\partial_{x^{i}}\phi(t,x)\,Tr\left(D^{2}_{xx}\phi\left(t,x\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)$

cannot generate supersolutions of (3.7) simply by integrating $x$ over $m$.

We now show how we can use the Lemma 4.1 to obtain regret bounds. Fix a large
time horizon $T$. Denote $\widetilde{m}:=m^{*\frac{1}{\sqrt{T}}}$,
$t_{n}=\frac{n}{T}$, where $n$ denotes the current step. For any smooth
supersolotuion $\phi$ of (4.1), we define a strategy of the forecaster

$\displaystyle(\beta_{0}^{*},\dotso,\beta_{T-1}^{*})$

via

(4.3)
$\displaystyle\beta_{n}^{*}(m):=D_{m}\Phi\left(t_{n},\tilde{m},\left[\widetilde{m}\right]\right).$

Suppose that the initial belief is $m_{0}$, and denote random belief as
$(m_{n})_{n=1,\dotso,T}$. Then it is clear that

$\displaystyle
v_{T}(m_{0})\leq\sup_{\alpha}{\mathbb{E}}^{\beta^{*},\alpha}\left[f([m_{T}])\right],$

where $f$ is the terminal condition $f(x):=\max_{i}x^{i}$. The following
Proposition provides assumptions for such a methodology to yield to regret
bounds.

######  Proposition 4.1.

Suppose $\phi$ is a classical solution of (4.1) and

(4.4)
$\displaystyle|\partial^{2}_{tt}\phi(t,x)|\leq\frac{C}{(1-t)^{3/2}},\quad|\partial^{3}_{xxx}\phi(t,x)|+|\partial^{2}_{tx}\phi(t,x)|\leq\frac{C}{1-t},\quad\forall
x\in{\mathbb{R}}^{K},$

for some positive constant $C$. Then the strategy $\beta^{*}$ of the
forecaster defined in (4.3) yields regret bounded above by
$\sqrt{T}\phi(0,[\widetilde{m}_{0}])$ asymptotically.

###### Proof.

Our goal is to show that
$\lim\limits_{T\to\infty}\frac{1}{\sqrt{T}}\sup_{\alpha}{\mathbb{E}}^{\beta^{*},\alpha}\left[f([m_{T}])\right]-{\phi}\left(0,\left[\widetilde{m}_{0}\right]\right)\leq
0$. First we rewrite the difference as a telescopic sum

$\displaystyle\frac{1}{\sqrt{T}}\sup_{\alpha}{\mathbb{E}}^{\beta^{*},\alpha}\left[f([m_{T}])\right]-{\phi}\left(0,\left[\widetilde{m}_{0}\right]\right)=\sup_{\alpha}{\mathbb{E}}^{\beta^{*},\alpha}\left[f([\widetilde{m}_{T}])\right]-{\phi}\left(0,\left[\widetilde{m}_{0}\right]\right)$
$\displaystyle=\sup_{\alpha}\sum_{n=0}^{T-1}\left({\mathbb{E}}^{\beta^{*},\alpha}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])\right]-{\mathbb{E}}^{\beta^{*},\alpha}\left[{\phi}(t_{n},[\widetilde{m}_{n}])\right]\right).$

Conditioning on $\widetilde{m}_{n}=m$, we have that

(4.5)
$\displaystyle{\mathbb{E}}^{\beta^{*},a}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])-\phi(t_{n},[\widetilde{m}_{n}])\,|\,\widetilde{m}_{n}=m\right]$
$\displaystyle=\sum_{i}\beta^{*}_{n}(m_{n})(i)\left(\hat{a}(i)\phi\left(t_{n+1},\left[A^{a,m}_{i,\sqrt{T}}\right]\right)+\hat{a}(-i)\phi\left(t_{n+1},\left[A^{a,m}_{-i,\sqrt{T}}\right]\right)\right)-\phi(t_{n},[m]).$

Using the linear structure of $\phi(t,[m])$, it can be seen that

$\displaystyle\phi\left(t_{n+1},\left[A^{a,m}_{i,\sqrt{T}}\right]\right)-\phi(t_{n},[m])$
(4.6) $\displaystyle=\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}\int\left(\phi\left(t_{n+1},x-\frac{e_{j^{c}}}{\sqrt{T}}\right)-\phi(t_{n},x)\right)m(dx).$

For any $i\in j\subset[K]$, we have the equality

(4.7)
$\displaystyle\phi\left(t_{n+1},x-\frac{e_{j^{c}}}{\sqrt{T}}\right)-\phi(t_{n},x)$
$\displaystyle=-\frac{e_{j^{c}}}{\sqrt{T}}\partial_{x}\phi(t_{n},x)+\frac{1}{T}\left(\partial_{t}\phi(t_{n},x)+\frac{1}{2}e_{j^{c}}^{\top}\partial^{2}_{xx}\phi(t_{n},x)e_{j^{c}}\right)$
$\displaystyle\quad+\frac{1}{T}\int_{0}^{1}\partial_{t}\phi\left(t_{n}+\frac{s}{T},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{t}\phi(t_{n},x)\,ds$
$\displaystyle\quad-\frac{e_{j^{c}}}{\sqrt{T}}\int_{0}^{1}\partial_{x}\phi\left(t_{n}+\frac{s}{T},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{x}\phi\left(t_{n},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)ds$
$\displaystyle\quad+\frac{1}{T}\int_{0}^{1}(1-s)e_{j^{c}}^{\top}\left(\partial_{xx}^{2}\phi\left(t_{n},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{xx}^{2}\phi(t_{n},x)\right)e_{j^{c}}\,ds.$

Using our assumption (4.4), we can estimate the last three terms in the
equation above

$\displaystyle\left|\frac{1}{T}\int_{0}^{1}\partial_{t}\phi\left(t_{n}+\frac{s}{T},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{t}\phi\left(t_{n},x\right)ds\right|\leq
C\int_{0}^{1/T}\frac{\frac{1}{T}-s}{(1-t_{n}-s)^{3/2}}ds$
$\displaystyle\left|\frac{e_{j^{c}}}{\sqrt{T}}\int_{0}^{1}\partial_{x}\phi\left(t_{n}+\frac{s}{T},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{x}\phi\left(t_{n},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)ds\right|\leq
C\sqrt{T}\int_{0}^{1/T}\frac{\frac{1}{T}-s}{1-t_{n}-s}ds$
$\displaystyle\left|\frac{1}{T}\int_{0}^{1}(1-s)e_{j^{c}}^{\top}\left(\partial_{xx}^{2}\phi\left(t_{n},x-\frac{se_{j^{c}}}{\sqrt{T}}\right)-\partial_{xx}^{2}\phi(t_{n},x)\right)e_{j^{c}}\,ds\right|\leq\frac{C}{T^{3/2}(1-t_{n})}.$

Let us define

(4.8)
$O(T,n):=C\left(\int_{0}^{1/T}\frac{\frac{1}{T}-s}{(1-t_{n}-s)^{3/2}}ds+\sqrt{T}\int_{0}^{1/T}\frac{\frac{1}{T}-s}{1-t_{n}-s}ds+\frac{1}{T^{3/2}(1-t_{n})}\right).$

Now plugging (4.6) and (4.7) into (4.5), we obtain that

(4.9)
$\begin{split}&{\mathbb{E}}^{\beta^{*},a}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])-\phi(t_{n},[\widetilde{m}_{n}])\,|\,\widetilde{m}_{n}=m\right]\\\
&\leq\frac{1}{\sqrt{T}}\sum_{i}\beta^{*}_{n}(m_{n})(i)\left(\sum_{j,i\not\in
j}a(j)e_{j}^{\top}-\sum_{j:i\in
j}a(j)e_{j^{c}}^{\top}\right)\partial_{x}\phi(t_{n},[m])+\frac{1}{T}\times\\\
&\left(\partial_{t}\phi(t_{n},[m])+\frac{1}{2}\sum_{i}\beta_{n}^{*}(m_{n})(i)Tr\left(D^{2}_{xx}\phi\left(t_{n},[m]\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)\right)\\\ &+O(T,n).\end{split}$

The first term on the right hand side vanishes due to our choice of
$\beta^{*}$, the second term is non-positive due to the supersolution property
of $\phi$, and thus we obtain that

$\displaystyle{\mathbb{E}}^{\beta^{*},a}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])-\phi(t_{n},[\widetilde{m}_{n}])\,|\,\widetilde{m}_{n}=m\right]\leq
O(T,n).$

Summing up from $n=0$ to $T-1$, taking supremum over $\alpha\in\mathcal{A}$,
and letting $T\to\infty$, we conclude that

$\displaystyle\lim\limits_{T\to\infty}\frac{1}{\sqrt{T}}\sup_{\alpha}{\mathbb{E}}^{\beta^{*},\alpha}\left[f([m_{T}])\right]-{\phi}\left(0,\left[\widetilde{m}_{0}\right]\right)\leq\lim\limits_{T\to\infty}\sum_{n=0}^{T-1}O(T,n)=0.$

∎

######  Example 4.1.

Let us take $\phi$ to be the smooth solution of the following heat equation

$\displaystyle\begin{cases}\partial_{t}\phi+\frac{1}{2}\Delta\phi=0&\text{on
$\mathbb{R}^{K}\times[0,1)$ }\\\ \phi(1,x)=f(x)&\text{on
$\mathbb{R}^{K}\times\\{1\\}$ }.\end{cases}$

It can be easily verified as in [6, Proposition 19] that $\phi$ satisfied
(4.4). According to [24, Appendix F.1], we know that
$D^{2}_{x^{l}x^{k}}\phi(t,x)>0$ if $l=k$ and $D^{2}_{x^{l}x^{k}}\phi(t,x)<0$
if $l\not=k$. Therefore for any $i\in[K]$ and $j\subset[K]$, we have that

$\displaystyle\frac{1}{2}Tr\left(D^{2}_{xx}\phi(t,x)\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\leq\frac{1}{2}\Delta\phi(t,x),$

and hence

$\displaystyle\frac{1}{2}\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left(D^{2}_{xx}\phi\left(t,x\right)\left(\sum_{j}{a(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)\leq\frac{1}{2}\Delta\phi(t,x).$

Thus $\phi$ is a smooth supersolution of (4.1) which satisfies (4.4) according
to [24]. By Feynman-Kac formula, we have
$\phi(0,x)={\mathbb{E}}_{x}[f(N^{1},N^{2},\dotso,N^{K})]$ where $N^{i}$ is a
standard normal. Supposing $x=(0,\dotso,0)$, then by Jensen’s inequality we
have that for any $t\geq 0$

$\displaystyle
e^{t{\mathbb{E}}[f(N^{1},\dotso,N^{K})]}\leq{\mathbb{E}}[e^{tf(N^{1},\dotso,N^{K})}]\leq
K{\mathbb{E}}[e^{tN^{1}}]=Ke^{t^{2}/2},$

and hence ${\mathbb{E}}[f(N^{1},\dotso,N^{K})]\leq\frac{\log
K}{t}+\frac{t}{2}$. Choosing $t=\sqrt{2\log K}$, we obtain that
$\phi(0,0)\leq\sqrt{2\log K}$. Therefore, when initial belief is $\delta_{0}$,
in our game where both agents have partial information, the asymptotic regret
is bounded above by $\sqrt{2T\log K}$. It is smaller than the expected regret
$5.15\sqrt{TK\log K}+\sqrt{\frac{TK}{\log K}}$in the case of adversarial
bandit where both agents only observe $Y_{t}$ [9, Theorem 3.4]. The regret
bound we obtain is two times larger than the performance of multiplicative
weight algorithms obtained in [20].

######  Remark 4.2.

Our main contribution in terms of regret bound is to extend the PDE based
methodology of [24] to the version bandit problems we study. In Lemma 4.1,
this bound is obtained by considering a functional linear in $m$ in the sense
that $\Phi(t,m)=\int\phi(t,x)m(dx)$. Similar to [24], the PDE tools are
expected to yield sharper bounds by considering more sophisticated
supersolutions to (4.1).

For example, any solution of

(4.10) $\displaystyle 0$
$\displaystyle=\partial_{t}u(t,m)+\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}$
$\displaystyle+\frac{1}{2}\left({\mathcal{V}}_{a,i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,i}+\sum_{j:i\in
j}\frac{a(j)}{\hat{a}(i)}e_{j^{c}}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j^{c}}\right)$
$\displaystyle+\frac{1}{2}\left({\mathcal{V}}_{a,-i}^{\top}D^{2}_{mm}u\left(t,m,[m],[m]\right){\mathcal{V}}_{a,-i}+\sum_{j:i\notin
j}\frac{a(j)}{\hat{a}(-i)}e_{j}^{\top}D_{x}D_{m}u\left(t,m,[m]\right)e_{j}\right)$

is a supersolution of (4.1). For all $i\in[K]$ and
$a\in{\mathcal{P}}(\\{0,1\\}^{K})$, we can define the symmetric matrices

$\displaystyle\Sigma(i,a)$
$\displaystyle=\left({a(e_{i})}{\mathcal{V}}_{a,e_{i}}{\mathcal{V}}_{a,e_{i}}^{\top}+{a(-e_{i})}{\mathcal{V}}_{a,-e_{i}}{\mathcal{V}}_{a,-e_{i}}^{\top}\right)$
$\displaystyle\tilde{\Sigma}(i,a)$ $\displaystyle=\left({a(e_{i})}\sum_{j:i\in
j}\frac{a(j)}{a(e_{i})}e_{j^{c}}^{\top}e_{j^{c}}+{a(-e_{i})}\sum_{j:i\notin
j}\frac{a(j)}{a(-e_{i})}e_{j}^{\top}e_{j}\right)-\Sigma(i,a).$

By computing $v^{\top}\Sigma(i,a)v$ and $v^{\top}\tilde{\Sigma}(i,a)v$ for
$v\in{\mathbb{R}}^{K}$, one can show that these matrices are non-negative.
Thus, (4.10) can be written as the Hamilton-Jacobi-Bellman equation

(4.11) $\displaystyle 0$
$\displaystyle=\partial_{t}u(t,m)+\frac{1}{2}\sup_{i,a\in{\mathcal{P}}(\\{0,1\\}^{K})}Tr\left({\mathcal{H}}u\left(t,m\right)\Sigma\left(i,a\right)+D_{x}D_{m}u\left(t,m,[m]\right)\tilde{\Sigma}\left(i,a\right)\right)$

where in line with [14], the term

${\mathcal{H}}U(t,m):=\int D_{x}D_{m}U(t,m,x)m(dx)+\int\int
D^{2}_{mm}U(t,m,x,y)m(dx)m(dy)$

is the so-called the Wasserstien Hessian of $U(t,\cdot)$. A simple computation
shows that the value function corresponding to a controlled version of [14,
Equation (1.8)] would yield to a viscosity solution to (4.11); see [14, Remark
3.5]. Then, this value function can be used as a supersolution of (4.1) (which
would indeed depend nonlinearly on $m$). However such a methodology requires a
comparison result for viscosity solutions of (4.11) (or smoothness of the
value function) to obtain regret bounds. This comparison result and
computation of improved regret bounds via a nonlinear $\Phi$ is being
addressed by the authors on an ongoing work.

##  5\. Lower bound by smooth subsolution of the PDE

As in the last section, we construct strategies for the adversary using smooth
subsolutions of (3.7). Recall that $\mathcal{E}$ is the set of balanced
strategies defined in Remark 3.3. The proof of following lemma is almost the
same as Lemma 4.1 and thus we omit it.

######  Lemma 5.1.

Let $\phi$ be a smooth solution of

$\begin{split}&0\leq\partial_{t}\phi(t,x)+\frac{1}{2}\inf_{i}\,Tr\left(D^{2}_{xx}\phi\left(t,x\right)\left(\sum_{j}{a_{t}(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)\\\
&\phi(1,x)\leq\max_{i}x^{i},\,\,\phi(t,x+\lambda{\mathbf{1}})=\phi(t,x)+\lambda,\end{split}$

where $a_{t}\in\mathcal{E},\,t\in[0,1],m\in{\mathcal{P}}({\mathbb{R}}^{K})$
are balanced strategies. Then, the function
$\Phi:[0,1]\times{\mathcal{P}}_{2}({\mathbb{R}}^{K})\mapsto{\mathbb{R}}$
defined by

$\Phi(t,m)=\phi(t,[m])=\int\phi(t,x)\,m(dx)$

is a smooth subsolution to (3.7).

######  Remark 5.1.

Note that in Lemma 5.1, the choice of balanced strategies $a_{t}$ only depends
on time $t$.

Given balanced strategies $(a_{t})_{t\in[0,1]}$ and subsolution $\phi$ as in
Lemma 5.1, we construct strategies for the adversary in the original game
(2.1). For a large time horizon $T$. Let us denote $t_{n}=\frac{n}{T}$, where
$n$ is the current step. We define a strategy $\alpha^{*}$ of the adversary
via

$\displaystyle\alpha^{*}_{n}=a_{t_{n}},\quad n=0,\dotso,T-1.$

######  Proposition 5.1.

Suppose $(a_{t})_{t\in[0,1]}$, $\phi$ are balanced strategies and classical
solutions as in Lemma 5.1 that satisfies (4.4).Let $m_{0}$ be the initial
belief. Then the strategy $\alpha^{*}$ of the adversary defined yields regret
bounded below by
$\sqrt{T}\phi\left(0,\left[m_{0}^{*\frac{1}{\sqrt{T}}}\right]\right)$
asymptotically.

###### Proof.

The argument is almost the same as that of Proposition 4.1. Just notice that
(4.9) now becomes

$\begin{split}&{\mathbb{E}}^{b,\alpha^{*}}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])-\phi(t_{n},[\widetilde{m}_{n}])\,|\,\widetilde{m}_{n}=m\right]\\\
&\geq\frac{1}{\sqrt{T}}\sum_{i}b(i)\left(\sum_{j,i\not\in
j}\alpha^{*}_{n}(j)e_{j}^{\top}-\sum_{j:i\in
j}\alpha^{*}_{n}(j)e_{j^{c}}^{\top}\right)\partial_{x}\phi(t_{n},[m])+\frac{1}{T}\times\\\
&\left(\partial_{t}\phi(t_{n},[m])+\frac{1}{2}\sum_{i}b(i)Tr\left(D^{2}_{xx}\phi\left(t_{n},[m]\right)\left(\sum_{j}{\alpha_{n}^{*}(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)\right)\right)\right)\\\ &+O(T,n),\end{split}$

where $O(T,n)$ is defined in (4.8). The first order term on the right hand
vanishes since $\alpha^{*}_{n}$ is balanced, and second order term is
nonnegative due to the subsolution property of $\phi$. Thus we obtain that
${\mathbb{E}}^{b,\alpha^{*}}\left[{\phi}(t_{n+1},[\widetilde{m}_{n+1}])-\phi(t_{n},[\widetilde{m}_{n}])\,|\,\widetilde{m}_{n}=m\right]\geq
O(T,n)$. Then summing up from $n=0$ to $T-1$, taking infimum over
$\beta\in\mathcal{B}$, and letting $T\to\infty$, we conclude our result.

∎

######  Example 5.1.

Let us take $a_{t}$ to be the uniformly distribution over $\\{0,1\\}^{K}$ for
each $t\in[0,1]$. Then it can be easily verified that

$\displaystyle\sum_{j}{a_{t}(j)}\left({\mathbf{1}}_{i\in
j}e_{j^{c}}e_{j^{c}}^{\top}+{\mathbf{1}}_{i\notin
j}e_{j}e_{j}^{\top}\right)=\frac{1}{4}e_{[K]}e_{[K]}^{\top}+\frac{1}{4}I_{K},\quad\forall\,i\in[K].$

where $I_{K}$ stands for the identity matrix of dimension $K\times K$.

Let us take $\phi$ to be the smooth solution of the following heat equation

$\displaystyle\begin{cases}\partial_{t}\phi+\frac{1}{8}\Delta\phi=0&\text{on
$\mathbb{R}^{K}\times[0,1)$ }\\\ \phi(1,x)=f(x)&\text{on
$\mathbb{R}^{K}\times\\{1\\}$ }.\end{cases}$

It can be easily seen that such $\phi$ and $(a_{t})_{t\in[0,1]}$ satisfy all
the assumptions in Proposition 5.1. Therefore when initial belief is
$\delta_{0}$, the asymptotic asymptotic regret is bounded below by
$\sqrt{T}\phi(0,0)$. By Feynman-Kac formula,
$\phi(0,0)={\mathbb{E}}[f(N^{1},\dotso,N^{K})]$ where $N^{i}$ is gaussian
distributed with mean $0$ and variance $1/4$ for each $i=1,\dotso,K$. Then
according to [25, Theorem 3], we obtain a lower bound $\phi(0,0)\geq
0.065\sqrt{\log K}-0.35$.

## References

  * [1] J.-Y. Audibert and S. Bubeck, Regret bounds and minimax policies under partial monitoring, The Journal of Machine Learning Research, 11 (2010), pp. 2785–2836.
  * [2] J.-Y. Audibert, S. Bubeck, and G. Lugosi, Minimax policies for combinatorial prediction games, in Proceedings of the 24th Annual Conference on Learning Theory, JMLR Workshop and Conference Proceedings, 2011, pp. 107–132.
  * [3] E. Bandini, A. Cosso, M. Fuhrman, and H. Pham, Randomized filtering and Bellman equation in Wasserstein space for partial observation control problem, Stochastic Process. Appl., 129 (2019), pp. 674–711.
  * [4] G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic analysis, 4 (1991), pp. 271–283.
  * [5] E. Bayraktar, I. Ekren, and X. Zhang, Finite-time 4-expert prediction problem, Comm. Partial Differential Equations, 45 (2020), pp. 714–757.
  * [6] , Prediction against a limited adversary, J. Mach. Learn. Res., 22 (2021).
  * [7] E. Bayraktar, I. Ekren, and Y. Zhang, On the asymptotic optimality of the comb strategy for prediction with expert advice, Ann. Appl. Probab., 30 (2020), pp. 2517–2546.
  * [8] E. Bayraktar, H. V. Poor, and X. Zhang, Malicious experts versus the multiplicative weights algorithm in online prediction, IEEE Transactions on Information Theory, 67 (2021), pp. 559–565.
  * [9] S. Bubeck and N. Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems, Foundations and Trends in Machine Learning, 5 (2012), pp. 1–122.
  * [10] M. Burzoni, V. Ignazio, A. M. Reppen, and H. M. Soner, Viscosity solutions for controlled mckean–vlasov jump-diffusions, SIAM Journal on Control and Optimization, 58 (2020), pp. 1676–1699.
  * [11] P. Cardaliaguet, F. Delarue, J.-M. Lasry, and P.-L. Lions, The Master Equation and the Convergence Problem in Mean Field Games:(AMS-201), vol. 201, Princeton University Press, 2019.
  * [12] R. Carmona, F. Delarue, et al., Probabilistic theory of mean field games with applications I-II, Springer, 2018.
  * [13] N. Cesa-Bianchi and G. Lugosi, Prediction, learning, and games, Cambridge university press, 2006.
  * [14] Y. T. Chow and W. Gangbo, A partial laplacian as an infinitesimal generator on the wasserstein space, Journal of Differential Equations, 267 (2019), pp. 6065–6117.
  * [15] A. Cosso, F. Gozzi, I. Kharroubi, H. Pham, and M. Rosestolato, Master bellman equation in the wasserstein space: Uniqueness of viscosity solutions, arXiv preprint arXiv:2107.10535, (2021).
  * [16] T. M. Cover, Behavior of sequential predictors of binary sequences., tech. rep., STANFORD UNIV CALIF STANFORD ELECTRONICS LABS, 1966.
  * [17] N. Drenska and R. V. Kohn, A pde approach to the prediction of a binary sequence with advice from two history-dependent experts, Communications on Pure and Applied Mathematics, n/a.
  * [18] , Prediction with expert advice: a PDE perspective, J. Nonlinear Sci., 30 (2020), pp. 137–173.
  * [19] N. Gravin, Y. Peres, and B. Sivan, Towards optimal algorithms for prediction with expert advice, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, USA, 2016, Society for Industrial and Applied Mathematics, pp. 528–547.
  * [20] , Tight lower bounds for multiplicative weights algorithmic families, in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [21] L. Greenstreet, N. J. A. Harvey, and V. Sanches Portella, Efficient and optimal fixed-time regret with two experts, in Proceedings of The 33rd International Conference on Algorithmic Learning Theory, S. Dasgupta and N. Haghtalab, eds., vol. 167 of Proceedings of Machine Learning Research, PMLR, 29 Mar–01 Apr 2022, pp. 436–464.
  * [22] N. J. A. Harvey, C. Liaw, E. A. Perkins, and S. Randhawa, Optimal anytime regret for two experts, in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 1404–1415.
  * [23] V. A. Kobzar and R. V. Kohn, A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit, arXiv:2202.05767, (2022), p. arXiv:2202.05767.
  * [24] V. A. Kobzar, R. V. Kohn, and Z. Wang, New potential-based bounds for prediction with expert advice, vol. 125 of Proceedings of Machine Learning Research, PMLR, 09–12 Jul 2020, pp. 2370–2405.
  * [25] F. Orabona and D. Pal, Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice, arXiv:1511.02176, (2015).
  * [26] Z. Zhang, A. Cutkosky, and I. Paschalidis, PDE-Based Optimal Strategy for Unconstrained Online Learning, (2022), p. arXiv:2201.07877.