# On Pentagon Equation, Tetrahedron Equation, Evolution and Integrals of
Motion.

Sergey M. Sergeev

###### Abstract

There is a sub-class of the solutions to Quantum Tetrahedron Equation related
to the algebraical Pentagon Equation. The Quantum Tetrahedron Equation defines
an evolution operator in wholly discrete three dimensional space-time. In this
paper we establish the Liouville integrability of one particular quantum
evolution model/classical integrable model on cubic lattice. The key feature
of the model is that it has two independent quantum/classical spectral curves.
In particular, on the classical level its Hamiltonian equations of motion
decouple into two independent Hirota equations.

Department of Theoretical Physics, Research School of Physics and Engineering,
Australian National University, Canberra, ACT 0200, Australia
and
Faculty of Science and Technology,
University of Canberra, Bruce ACT 2617, Australia

##  1 Introduction

We discuss in this paper some specific three-dimensional exactly integrable
model related to the algebraic Pentagon equation.

In particular, we consider the solution of the Tetrahedron equation

$R_{123}R_{145}R_{246}R_{356}\;=\;R_{356}R_{246}R_{145}R_{123}$ (1.1)

of the form

$R_{123}\;=\;S_{13}P_{23}S_{13}^{-1}\;,$ (1.2)

where $P_{23}$ is the permutation operator, while $S_{13}$ is the subject of
the algebraic Pentagon equation

$S_{12}S_{23}\;=\;S_{23}S_{13}S_{12}\;,$ (1.3)

and an auxiliary $10$-term relation (see [1] for details),

$S_{12}S_{13}^{-1}S_{14}S_{24}^{-1}S_{34}\;=\;S_{24}^{-1}S_{34}S_{14}^{-1}S_{12}S_{13}^{-1}\;.$
(1.4)

The $R$-matrix of the Tetrahedron Equation can be used for construction of the
evolution operator, its kernel is given by

$U_{\\{\;\alpha,\;\beta,\;\gamma\\}}^{\\{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}\\}}\;=\;\prod_{i,j}R_{\;\;\;\;\alpha_{i,j},\;\;\beta_{i,j},\;\;\;\;\;\;\gamma_{i,j}}^{\alpha_{i+1,j}^{\prime},\;\;\beta_{i,j}^{\prime},\;\;\gamma_{i,j+1}^{\prime}}\;.$
(1.5)

The periodical boundary conditions imply $i,j\in\mathbb{Z}_{N}$. Evolution
operator commutes with a layer-to-layer transfer-matrix constructed with the
help of $R$-matrices, usually this justifies the integrability in the case
when $R$-matrix is endowed by a set of spectral parameters.

In this paper we consider the case of the constant Pentagon and Tetrahedron
Equations related to the Weyl algebra of observables and quantum dilogarithm.
We establish the complete integrability of the model by producing explicitly
the complete set of the integrals of motion. The remarkable feature of the
model is that the complete set is produced by two independent determinants
(generating functions) rather then by one. On the classical level this means
that the model has two independent spectral curves.

##  2 Linear problems and Tetrahedral map

We commence with the formulation of an auxiliary linear problem(s) intertwined
by $R$-matrix (1.2) and allowing to derive the quantum spectral curves for the
quantum evolution operator (1.5).

A remarkable feature of $R$-matrix (1.2) is that there are two completely
different approaches to its linear problems. One is based on the linear
problem providing the algebraic Pentagon equation (1.3). This approach is
rather geometrical, but it does not provide a way to produce a set of
integrals of motion. We will give details in the appendix.

The auxiliary linear problem used in this section can be formulated as
follows. The picture below gives a combinatoric of a Tetrahedral map:

$a$$f$$d$$b$$g$$c$$e$$\mathfrak{w}_{1}$$\mathfrak{w}_{3}$$\mathfrak{w}_{2}$$\to$
$h$$f$$d$$b$$g$$c$$e$$\mathfrak{w}_{1}^{\prime}$$\mathfrak{w}_{3}^{\prime}$$\mathfrak{w}_{2}^{\prime}$
(2.1)

On this picture $a,b,\cdots,h$ denote the cells of two two-dimensional kagome
lattices111Kagome lattice is a lattice formed by three sets of parallel lines.
Kagome lattice also can be seen as a dissection of a cubic lattice by an
auxiliary plane in general position. R. J. Baxter suggested the term “kagome
lattice” inspired by the Japanese handcraft . The vertices stand for local
Weyl algebras. The left and right graphs of (2.1) present two systems of
linear equations:

$\left\\{\begin{array}[]{l}\displaystyle\ell_{1}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{f}-\boldsymbol{v}_{1}\phi_{a}+\boldsymbol{u}_{1}\phi_{b}\;=\;0\\\
\\\ \displaystyle\ell_{2}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{a}-\boldsymbol{v}_{2}\phi_{e}+\boldsymbol{u}_{2}\phi_{g}\;=\;0\\\
\\\ \displaystyle\ell_{3}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{f}-\boldsymbol{v}_{3}\phi_{d}+\boldsymbol{u}_{3}\phi_{a}\;=\;0\end{array}\right.\quad\to\quad\left\\{\begin{array}[]{l}\displaystyle\ell_{1}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{d}-\boldsymbol{v}_{1}^{\prime}\phi_{e}+\boldsymbol{u}_{1}^{\prime}\phi_{h}\;=\;0\\\
\\\ \displaystyle\ell_{2}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{f}-\boldsymbol{v}_{2}^{\prime}\phi_{d}+\boldsymbol{u}_{2}^{\prime}\phi_{b}\;=\;0\\\
\\\ \displaystyle\ell_{3}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\phi_{b}-\boldsymbol{v}_{3}^{\prime}\phi_{h}+\boldsymbol{u}_{3}^{\prime}\phi_{g}\;=\;0\end{array}\right.$
(2.2)

Here $\boldsymbol{u},\boldsymbol{v}$ stand for a local Weyl algebra,

$\mathfrak{w}_{j}\;=\;(\boldsymbol{u}_{j},\;\boldsymbol{v}_{j}\;:\;\boldsymbol{u}_{j}\boldsymbol{v}_{j}\;=\;q^{2}\boldsymbol{v}_{j}\boldsymbol{u}_{j})$
(2.3)

(the term “local” means that the Weyl elements assigned to different vertices
on the same graph commute). Auxiliary elements $\phi_{a},\cdots,\phi_{h}$
belong to a formal right module of all Weyl algebras.

The intertwining means the linear equivalence of the left and right systems of
(2.2). In particular,
$\boldsymbol{v}_{1}^{-1}\ell_{1}+\boldsymbol{u}_{3}^{-1}\ell_{3}$ and
$\ell_{2}^{\prime}$ have the same auxiliary variables and therefore they must
be proportional,

$(\boldsymbol{v}_{1}^{-1}+\boldsymbol{u}_{3}^{-1})^{-1}(\boldsymbol{v}_{1}^{-1}\ell_{1}+\boldsymbol{u}_{3}^{-1}\ell_{3})\;\equiv\;\ell_{2}^{\prime}\;.$
(2.4)

The equivalence of two linear systems (2.2) provides

$\begin{array}[]{lll}\displaystyle\boldsymbol{u}_{1}^{\prime}\;=\;\boldsymbol{v}_{3}^{-1}F\;,&\displaystyle\boldsymbol{u}_{2}^{\prime}\;=\;\boldsymbol{u}_{3}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{u}_{3}\;=\;\boldsymbol{u}_{1}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{u}_{2}\;,\\\
\\\
\displaystyle\boldsymbol{v}_{1}^{\prime}\;=\;\boldsymbol{v}_{3}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{v}_{2}\;,&\displaystyle\boldsymbol{v}_{2}^{\prime}\;=\;\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{v}_{3}\;,&\displaystyle\boldsymbol{v}_{3}^{\prime}\;=\;\boldsymbol{u}_{1}^{-1}F\;,\end{array}$
(2.5)

where $F$ remains undefined.

There are several possible choices of $F$ providing the integrability [2]. In
this paper we fix $F$ by an extra requirement: the same
$\mathfrak{w}_{j},\mathfrak{w}_{j}^{\prime}$ must satisfy the second
independent linear problem:

$\left\\{\begin{array}[]{l}\displaystyle\tilde{\ell}_{1}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{g}-\boldsymbol{v}_{1}\tilde{\phi}_{b}+\boldsymbol{u}_{1}\tilde{\phi}_{a}\;=\;0\\\
\\\ \displaystyle\tilde{\ell}_{2}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{c}-\boldsymbol{v}_{2}\tilde{\phi}_{g}+\boldsymbol{u}_{2}\tilde{\phi}_{e}\;=\;0\\\
\\\ \displaystyle\tilde{\ell}_{3}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{e}-\boldsymbol{v}_{3}\tilde{\phi}_{a}+\boldsymbol{u}_{3}\tilde{\phi}_{d}\;=\;0\end{array}\right.\quad\to\quad\left\\{\begin{array}[]{l}\displaystyle\tilde{\ell}_{1}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{c}-\boldsymbol{v}_{1}^{\prime}\tilde{\phi}_{h}+\boldsymbol{u}_{1}^{\prime}\tilde{\phi}_{e}\;=\;0\\\
\\\ \displaystyle\tilde{\ell}_{2}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{h}-\boldsymbol{v}_{2}^{\prime}\tilde{\phi}_{b}+\boldsymbol{u}_{2}^{\prime}\tilde{\phi}_{d}\;=\;0\\\
\\\ \displaystyle\tilde{\ell}_{3}^{\prime}\;\stackrel{{\scriptstyle
def}}{{=}}\;\tilde{\phi}_{c}-\boldsymbol{v}_{3}^{\prime}\tilde{\phi}_{g}+\boldsymbol{u}_{3}^{\prime}\tilde{\phi}_{h}\;=\;0\end{array}\right.$
(2.6)

Linear problems (2.2) and (2.6) are compatible, so that the map
$\mathfrak{w}_{j}\to\mathfrak{w}_{j}^{\prime}$ becomes unique:

$\begin{array}[]{lll}\displaystyle\boldsymbol{u}_{1}^{\prime}\;=\;\boldsymbol{u}_{2}+\boldsymbol{u}_{1}\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}\;,&\displaystyle\boldsymbol{u}_{2}^{\prime}\;=\;\boldsymbol{u}_{3}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{u}_{3}^{\prime}\;=\;\boldsymbol{u}_{1}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{u}_{2}\;,\\\
\\\
\displaystyle\boldsymbol{v}_{1}^{\prime}\;=\;\boldsymbol{v}_{3}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{v}_{2}\;,&\displaystyle\boldsymbol{v}_{2}^{\prime}\;=\;\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{v}_{3}\;,&\displaystyle\boldsymbol{v}_{3}^{\prime}\;=\;\boldsymbol{v}_{2}+\boldsymbol{u}_{1}^{-1}\boldsymbol{u}_{2}\boldsymbol{v}_{3}\;.\end{array}$
(2.7)

This set of formulas defines the map $\mathfrak{R}_{123}$ on a space of
functions of $\boldsymbol{u}_{j},\boldsymbol{v}_{j}$,

$(\mathfrak{R}_{123}\circ
f)(\mathfrak{w}_{1},\mathfrak{w}_{2},\mathfrak{w}_{3})\;=\;f(\mathfrak{w}_{1}^{\prime},\mathfrak{w}_{2}^{\prime},\mathfrak{w}_{3}^{\prime})\;.$
(2.8)

######  Statement 2.1.

Properties of $\mathfrak{R}$ are:

  * •

The map $\mathfrak{R}$ is the automorphism of
$\mathfrak{w}_{1}\otimes\mathfrak{w}_{2}\otimes\mathfrak{w}_{3}$ (proof by
direct verification).

  * •

The map $\mathfrak{R}_{123}$ satisfies the functional Tetrahedron equation
(proof by direct verification).

  * •

In all cases of the self-dual representation of Weyl algebra (e.g. the cyclic
$\mathbb{Z}_{N}$ representation, modular double,
$\mathbb{Z}\otimes\mathbb{T}$, etc.), when the quantum dilogarithm is well
defined, the quantum operator $R_{123}$, such that

$(\mathfrak{R}_{123}\circ f)\;=\;R_{123}\cdot f\cdot R_{123}^{-1}\;,$ (2.9)

is uniquely defined. Operator $R_{123}$ has the structure (1.2) and satisfy
the quantum Tetrahedron equation [5].

##  3 Evolution map and the integrals of motion

The evolution map appears as an extension of the “Yang-Baxter-type map” (2.1)
to the whole kagome lattice:

$a_{i,j}$$c_{i,j}$$b_{i,j-1}$$b_{i-1,j}$$c_{i,j+1}$$b_{i,j}$$c_{i+1,j}$$\mathfrak{w}_{1,i,j}$$\mathfrak{w}_{3,i,j}$$\mathfrak{w}_{2,i,j}$$\displaystyle\stackrel{{\scriptstyle\mathcal{U}}}{{\to}}$
$b_{i,\j}^{\prime}$$a^{\prime}_{i,j}$$c^{\prime}_{i+1,j}$$c^{\prime}_{i,j+1}$$a^{\prime}_{i,j+1}$$c^{\prime}_{i+1,j+1}$$a^{\prime}_{i+1,j}$$\mathfrak{w}_{1,i+1,j}^{\prime}$$\mathfrak{w}_{3,i,j+1}^{\prime}$$\mathfrak{w}_{2,i,j}^{\prime}$
(3.1)

For the whole kagome lattice, $c_{i,j}$ label the hexagonal cells, while
$a_{i,j}$ and $b_{i,j}$ label two types of triangular cells. Notations for the
cells here preserve the structure of the kagome lattice, however some cells
must coincide according to (2.1):

$a_{i,j}^{\prime}\;=\;c_{i,j}\;,\quad c_{i,j}^{\prime}\;=\;b_{i-1,j-1}\;,$
(3.2)

while the cells $a_{i,j}$ on the left disappear and cells $b_{i,j}^{\prime}$
on the right appear.

Explicit form of the evolution map follows from (2.7):

$\begin{array}[]{ll}\displaystyle\boldsymbol{u}_{1,i+1,j}^{\prime}\;=\;\left(\boldsymbol{u}_{2}+\boldsymbol{u}_{1}\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}\right)_{i,j}\;,&\displaystyle\boldsymbol{v}_{1,i+1,j}^{\prime}\;=\;\left(\boldsymbol{v}_{3}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{v}_{2}\right)_{i,j}\;,\\\
\\\
\displaystyle\boldsymbol{u}_{2,i,j}^{\prime}\;=\;\left(\boldsymbol{u}_{3}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{u}_{1}\right)_{i,j}\;,&\displaystyle\boldsymbol{v}_{2,i,j}^{\prime}\;=\;\left(\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{v}_{3}\right)_{i,j}\;,\\\
\\\
\displaystyle\boldsymbol{u}_{3,i,j+1}^{\prime}\;=\;\left(\boldsymbol{u}_{1}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\boldsymbol{u}_{2}\right)_{i,j}\;,&\displaystyle\boldsymbol{v}_{3,i,j+1}^{\prime}\;=\;\left(\boldsymbol{v}_{2}+\boldsymbol{u}_{1}^{-1}\boldsymbol{u}_{2}\boldsymbol{v}_{3}\right)_{i,j}\;.\end{array}$
(3.3)

The evolution map $\displaystyle(\mathcal{U}\circ
f)(\mathfrak{w}_{\alpha,i,j})=f(\mathfrak{w}^{\prime}_{\alpha,i,j})$, being
realised for a particular representation of the Weyl algebra,
$(\mathcal{U}\circ f)\;=\;U\cdot f\cdot U^{-1}$, is given by (1.5).

Generating functions for the integrals of motion preserved by the evolution
map are quantum spectral polynomials.

To obtain the first spectral polynomial, consider the whole set of auxiliary
linear relations for the whole kagome lattice. The type (2.2) gives

$\left\\{\begin{array}[]{l}\displaystyle\ell_{1,i,j}\;=\;\phi_{c_{i,j}}-\boldsymbol{v}_{1,ij}\phi_{a_{i,j}}+\boldsymbol{u}_{1,ij}\phi_{b_{i-1,j}}\;,\\\
\\\
\displaystyle\ell_{2,ij}\;=\;\phi_{a_{i,j}}-\boldsymbol{v}_{2,ij}\phi_{c_{i+1,j}}+\boldsymbol{v}_{2,ij}\phi_{c_{i,j+1}}\;,\\\
\\\
\displaystyle\ell_{3,ij}\;=\;\phi_{c_{i,j}}-\boldsymbol{v}_{3,ij}\phi_{b_{i,j-1}}+\boldsymbol{u}_{3,ij}\phi_{a_{i,j}}\;.\end{array}\right.$
(3.4)

Consider the periodic boundary conditions and introduce the quasi–periods,

$\phi_{c_{i+N,j}}\;=\;\lambda\phi_{c_{i,j}}\;,\quad\phi_{c_{i,j+N}}\;=\;\mu\phi_{c_{i,j}}\;,\quad\textrm{etc.}$
(3.5)

The system of linear relations (3.4) can be written in the matrix form,

$\ell_{A}\;=\;\sum_{B}L_{A,B}^{(1)}\phi_{B}$ (3.6)

where $A$ takes $3N^{2}$ values $A\in\\{(1,ij),(2,ij),(3,ij)\\}$, and $B$
takes $3N^{2}$ values $B\in\\{a_{ij},b_{ij},c_{ij}\\}$.

Define now

$J^{(1)}(\lambda,\mu)\;=\;\left(\prod_{i,j}\boldsymbol{u}_{1,ij}^{-1}\right)\cdot\det
L^{(1)}$ (3.7)

Operator $J^{(1)}(\lambda,\mu)$ is a polynomial of $\lambda,\mu$ with the
following Newton polygon (this is a particular case of $N=3$):

$\lambda$$\mu$ (3.8)

so that

$J^{(1)}(\lambda,\mu)\;=\;\sum_{a,b}\lambda^{a}\mu^{b}J^{(1)}_{a,b}$ (3.9)

The extra multiplier in (3.7) makes

$J^{(1)}_{-N,0}\;=\;1\;,$ (3.10)

this coefficient corresponds to the empty dot in (3.8).

In the similar way one can consider the linear problem (2.6),

$\left\\{\begin{array}[]{l}\displaystyle\tilde{\ell}_{1,i,j}\;=\;\tilde{\phi}_{c_{i,j+1}}-\boldsymbol{v}_{1,ij}\tilde{\phi}_{b_{i-1,j}}+\boldsymbol{u}_{1,ij}\tilde{\phi}_{a_{i,j}}\;,\\\
\\\
\displaystyle\tilde{\ell}_{2,ij}\;=\;\tilde{\phi}_{b_{i,j}}-\boldsymbol{v}_{2,ij}\tilde{\phi}_{c_{i,j+1}}+\boldsymbol{v}_{2,ij}\tilde{\phi}_{c_{i+1,j}}\;,\\\
\\\
\displaystyle\tilde{\ell}_{3,ij}\;=\;\tilde{\phi}_{c_{i+1,j}}-\boldsymbol{v}_{3,ij}\tilde{\phi}_{a_{i,j}}+\boldsymbol{u}_{3,ij}\tilde{\phi}_{b_{i,j-1}}\;,\end{array}\right.$
(3.11)

but now with the opposite quasimomenta,

$\tilde{\phi}_{c_{i+N,j}}\;=\;\lambda^{-1}\tilde{\phi}_{c_{i,j}}\;,\quad\tilde{\phi}_{c_{i,j+N}}\;=\;\mu^{-1}\tilde{\phi}_{c_{i,j}}\;,\quad\textrm{etc.}$
(3.12)

In the same way we can define its determinant,

$\tilde{\ell}_{A}\;=\;\sum_{B}L^{(2)}_{A,B}\tilde{\phi}_{B}\;,\quad
J^{(2)}(\lambda,\mu)\;=\;\left(\prod_{i,j}\boldsymbol{u}_{1,ij}^{-1}\right)\cdot\det
L^{(2)}\;.$ (3.13)

Polynomial $J^{(2)}(\lambda,\mu)$ has the same Newton polygon (3.8).

######  Statement 3.1.

Polynomials $J^{(k)}(\lambda,\mu)$, $k=1,2$, have the following properties:

  * •

They generate the integrals of motion, $\mathcal{U}\circ
J^{(k)}(\lambda,\mu)\;=\;J^{(k)}(\lambda,\mu)$.

  * •

Polynomials $J^{(1)}(\lambda,\mu)$ and $J^{(2)}(\lambda,\mu)$ have identical
perimeters.

  * •

Elements $J^{(1,2)}_{a,b}$ and from the inside of the Newton polygon are
algebraically independent.

  * •

Elements $J^{(1,2)}_{a,b}$ satisfy the algebra

$\displaystyle
J^{(k)}_{a,b}J^{(k^{\prime})}_{a^{\prime},b^{\prime}}\;=\;q^{2(a^{\prime}+N)b-2(a+N)b^{\prime}}J^{(k^{\prime})}_{a^{\prime},b^{\prime}}J^{(k)}_{a,b}\;.$
(3.14)

  * •

Thus, the set $J^{(1,2)}_{a,b}$ gives $3N^{2}+1$ invariants with $3N^{2}$
commutative independent invariants.

Thus, the Liouville integrability of the evolution is established.

Comments on the Statement. The general approach to the quantum curve method,
including the proof of (3.14), can be found in [3, 4]. However, in this paper
two different quantum curves appear, so that all items from the statement
above, especially the statements about completeness, have been verified
straightforwardly for $N\leq 4$.

Common perimeters of $J^{(1,2)}(\lambda,\mu)$ worth mentioning. The most left
side of (3.8) is given by

$J^{(1,2)}(\lambda,\mu)\;=\;\lambda^{-N}\prod_{i}\left(1-\mu\prod_{j}\boldsymbol{u}_{2,ij}\boldsymbol{u}_{3,ij}\right)+\lambda^{-N+1}\cdots\;,$
(3.15)

the bottom side is given by

$J^{(1,2)}(\lambda,\mu)\;=\;\mu^{-N}\left(\prod_{i,j}\boldsymbol{u}_{1,ij}^{-1}\boldsymbol{v}_{3,ij}\right)\,\prod_{j}\left(1-\lambda\prod_{i}\boldsymbol{v}_{1,ij}\boldsymbol{v}_{2,ij}\right)+\mu^{-N+1}\cdots\;,$
(3.16)

and the left-botton side is given by

$J^{(1,2)}(\lambda,\mu)\;=\;\lambda^{-N}\prod_{k}\left(1+\frac{\lambda}{\mu}\prod_{i+j=k}\boldsymbol{u}_{1,ij}^{-1}\boldsymbol{v}_{3,ij}\right)+\cdots$
(3.17)

One can extract very simple invariants,

$\boldsymbol{U}_{i}\;=\;\prod_{j}\boldsymbol{u}_{2,ij}\boldsymbol{u}_{3,ij}\;,\quad\boldsymbol{V}_{j}\;=\;\prod_{i}\boldsymbol{v}_{1,ij}\boldsymbol{v}_{2,ij}\;,$
(3.18)

so that

$I^{(k)}_{a,b}\;=\;\boldsymbol{U}_{0}^{-b}\boldsymbol{V}_{0}^{-a-N}J^{(k)}_{a,b}\;,$
(3.19)

is the set of integrals of motion in involution. The non-commutative pair
$\boldsymbol{U},\boldsymbol{V}$ has the meaning of a mass center of the
system.

##  4 Classical model

It is interesting to demonstrate the existence of two independent spectral
curves on the classical level.

To do it, we rewrite firstly the evolution (3.3) in the form of equations of
motion on the cubic lattice.

Let $\boldsymbol{n}=(n_{1},n_{2},n_{3})$ stand for a vertex of the cubic
lattice. Let

$\boldsymbol{e}_{1}=(1,0,0)\;,\quad\boldsymbol{e}_{2}=(0,1,0)\;,\quad\boldsymbol{e}_{3}=(0,0,1)$
(4.1)

be unit vectors. Then the local map (2.7) can be written as

$\begin{array}[]{ll}\displaystyle
u_{1,\boldsymbol{n}+\boldsymbol{e}_{1}}\;=\;\frac{u_{2,\boldsymbol{n}}v_{3,\boldsymbol{n}}+u_{1,\boldsymbol{n}}v_{2,\boldsymbol{n}}}{v_{3,\boldsymbol{n}}}\;,&\displaystyle
v_{1,\boldsymbol{n}+\boldsymbol{e}_{1}}\;=\;\frac{v_{2,\boldsymbol{n}}(v_{1,\boldsymbol{n}}+u_{3,\boldsymbol{n}})}{v_{3,\boldsymbol{n}}}\;,\\\
\\\ \displaystyle
u_{2,\boldsymbol{n}+\boldsymbol{e}_{2}}\;=\;\frac{u_{1,\boldsymbol{n}}u_{3,\boldsymbol{n}}}{v_{1,\boldsymbol{n}}+u_{3,\boldsymbol{n}}}\;,&\displaystyle
v_{2,\boldsymbol{n}+\boldsymbol{e}_{2}}\;=\;\frac{v_{1,\boldsymbol{n}}v_{3,\boldsymbol{n}}}{v_{1,\boldsymbol{n}}+u_{3,\boldsymbol{n}}}\;,\\\
\\\ \displaystyle
u_{3,\boldsymbol{n}+\boldsymbol{e}_{3}}\;=\;\frac{u_{2,\boldsymbol{n}}(v_{1,\boldsymbol{n}}+u_{3,\boldsymbol{n}})}{u_{1,\boldsymbol{n}}}\;,&\displaystyle
v_{3,\boldsymbol{n}+\boldsymbol{e}_{3}}\;=\;\frac{u_{2\boldsymbol{n}}v_{3,\boldsymbol{n}}+u_{1,\boldsymbol{n}}v_{2,\boldsymbol{n}}}{u_{1,\boldsymbol{n}}}\;.\end{array}$
(4.2)

The evolution map (3.3) is the map $t\to t+1$ of the space-like two
dimensional surface

$\boldsymbol{n}\;=\;(i,t-i-j,j)\;,\quad t-\textrm{fixed.}$ (4.3)

The Legendre transform bringing the Hamiltonian equations of motion (4.2) to
the corresponding Lagrangian equations is not quite evident. It is

$\begin{array}[]{ll}\displaystyle
u_{1,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}}\frac{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}}{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}}}\;,&\displaystyle
v_{1,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}}\frac{\tau^{(2)}_{\boldsymbol{n}}}{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}}}\;,\\\
\\\ \displaystyle
u_{2,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{3}}}\frac{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}}{\tau^{(2)}_{\boldsymbol{n}}}\;,&\displaystyle
v_{2,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{3}}}\frac{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}}{\tau^{(2)}_{\boldsymbol{n}}}\;,\\\
\\\ \displaystyle
u_{3,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}}\frac{\tau^{(2)}_{\boldsymbol{n}}}{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}}}\;,&\displaystyle
v_{3,\boldsymbol{n}}\;=\;\frac{\tau^{(1)}_{\boldsymbol{n}}}{\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}}\frac{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}}}{\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}}}\;.\end{array}$
(4.4)

As the result, the Lagrangian equations of motion decouple into two
independent Hirota equations:

$\begin{array}[]{l}\displaystyle\tau^{(1)}_{\boldsymbol{n}}\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}\;=\;\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}+\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}\tau^{(1)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}}\;,\\\
\\\
\displaystyle\tau^{(2)}_{\boldsymbol{n}}\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}\;=\;\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{1}}\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{2}+\boldsymbol{e}_{3}}+\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{3}}\tau^{(2)}_{\boldsymbol{n}+\boldsymbol{e}_{1}+\boldsymbol{e}_{2}}\;.\end{array}$
(4.5)

The algebraic curve $J^{(k)}(\lambda,\mu)=0$ becomes the spectral curve for
$\tau^{(k)}$-equation, $k=1,2$.

Acknowledgement. I would like to thank Vladimir Bazhanov and Vladimir
Mangazeev for valuable discussions. Also I acknowledge the support of the
Australian Research Council grant DP190103144.

## References

  * [1] R. M. Kashaev and S. M. Sergeev, “ _On pentagon, ten-term, and tetrahedron relations_ ”, Comm. Math. Phys. 195 (1998) 309-319
  * [2] S. M. Sergeev, “ _Quantum $2+1$ evolution model_”. J. Phys. A: Math. Gen. 32 (1999) 5693-5714
  * [3] S. M. Sergeev, “ _Coefficient Matrices of a Quantum Discrete Auxiliary Linear Problem_ ”. Journal of Mathematical Sciences 115(1) (2003) pp 2049-2057
  * [4] S. Sergeev, “ _Quantum curve in q-oscillator model_ ”. International Journal of Mathematics and Mathematical Sciences Volume 2006, Article ID 92064, Pages 1 – 31 (2006)
  * [5] R. M. Kashaev and S. M .Sergeev, _in preparation_
  * [6] A. Doliwa and S. M. Sergeev, “ _The pentagon relation and incidence geometry_ ”. J. Math. Phys. 55 (2014) 063504

There is the term “Pentagon equation” in the title of this paper, however if
fact we did not use it. In this Appendix we give some alternative way of
derivation of the Tetrahedral map (2.7) using different linear problem. This
approach is more geometric, but it does not allowed one to derive the spectral
determinants. In addition, we collect here some by-product observations which
may be interesting for the Reader.

##  Appendix A Pentagon Map

We start with the Pentagon map and underlying auxiliary linear problem [6].

Let $\boldsymbol{u},\boldsymbol{v}$ be the simple Weyl algebra,

$\boldsymbol{u}\,\boldsymbol{v}\;=\;q^{2}\,\boldsymbol{v}\,\boldsymbol{u}\;.$
(A.1)

The quantum Pentagon map is defined over the space of functions on the direct
product of two Weyl algebras,

$\biggl{(}\mathcal{S}_{12}\circ\varphi\biggr{)}(\boldsymbol{u}_{1},\boldsymbol{v}_{1},\boldsymbol{u}_{2},\boldsymbol{v}_{2})\;=\;\varphi(\boldsymbol{u}_{1}^{\prime},\boldsymbol{v}_{1}^{\prime},\boldsymbol{u}_{2}^{\prime},\boldsymbol{v}_{2}^{\prime})\qquad\forall\varphi$
(A.2)

where

$\begin{array}[]{ll}\displaystyle\boldsymbol{u}_{1}^{\prime}\;=\;\boldsymbol{v}_{2}^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{v}_{1}^{\prime}\;=\;\boldsymbol{v}_{2}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{2})\;,\\\
\\\
\displaystyle\boldsymbol{u}_{2}^{\prime}\;=\;\boldsymbol{u}_{2}(\boldsymbol{v}_{1}+\boldsymbol{u}_{2})^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{v}_{2}^{\prime}\;=\;\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{2})^{-1}\boldsymbol{v}_{2}\;.\end{array}$
(A.3)

The map $\mathcal{S}_{12}$ is the canonical one, i.e. it can be seen as a
conjugation,

$\biggl{(}\mathcal{S}_{12}\circ\varphi\biggr{)}\;=\;S_{12}\,\varphi\,S_{12}^{-1}\;.$
(A.4)

Construction of the kernel of $S_{12}$ is the subject of the choice of the
representation of the Weyl algebra and quantum dilogarithms. However, this is
not a subject of this paper. We focus here on the map (A.3) only.

The map (A.3) can be derived as the consistency condition of the following
“linear” problem. Consider triangle $ABC$,

$A$$B$$C$$\Leftrightarrow\quad\varphi_{A}\,-\,\boldsymbol{v}\,\varphi_{B}\,+\,\boldsymbol{u}\,\varphi_{C}\;=\;0\;.$
(A.5)

Let a formal linear variable $\phi_{A}$ is associated with the vertex $A$,
etc. For the whole triangle we associate the linear equation shown in the left
part of (A.5). Note the orientation of the triangle, vertex $A$ is selected,
the vertices $ABC$ are oriented clockwise.

Consider now quadrilateral $ABCD$. It can be divided into two triangles in two
ways:

$A$$B$$C$$D$$1$$2$ $\sim$$A$$B$$C$$D$$1$$2$ (A.6)

The left hand side of (A.6) implies two linear equations

$\varphi_{D}-\boldsymbol{v}_{1}\varphi_{B}+\boldsymbol{u}_{1}\varphi_{C}\;=\;0\;,\quad\varphi_{D}-\boldsymbol{v}_{2}\varphi_{A}+\boldsymbol{u}_{2}\varphi_{B}\;=\;0\;.$
(A.7)

For the right hand side of (A.6) we write the similar equations,

$\varphi_{A}-\boldsymbol{v}_{1}^{\prime}\varphi_{B}+\boldsymbol{u}_{1}^{\prime}\varphi_{C}\;=\;0\;.\quad\varphi_{D}-\boldsymbol{v}_{2}^{\prime}\varphi_{A}+\boldsymbol{u}_{2}^{\prime}\varphi_{C}\;=\;0\;,$
(A.8)

The map (A.3) appear as the equivalence requirement of (A.7) and (A.8). For
instance, excluding $\varphi_{D}$ from (A.7), one obtains

$\varphi_{A}-\boldsymbol{v}_{2}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{2})\varphi_{B}+\boldsymbol{v}_{2}^{-1}\boldsymbol{u}_{1}\varphi_{C}\;=\;0\;.$
(A.9)

This equation could be identically the left equation of (A.8), what gives the
expressions (A.3) for $\boldsymbol{v}_{1}^{\prime}$ and
$\boldsymbol{u}_{1}^{\prime}$. Similarly, excluding $\varphi_{B}$ from (A.7),
one obtains expressions for
$\boldsymbol{v}_{2}^{\prime},\boldsymbol{u}_{2}^{\prime}$.

Note that the map (A.3) is constructed as the map of a generic non-commutative
algebra of observables. By construction, it satisfies the algebraic Pentagon
relation (1.3) as well as the ten-term relation (1.4) since all these
relations can be formulated as uniquely defined maps for corresponding
auxiliary linear problems.

In particular, all maps in this paper are the canonical maps with respect to
the local Weyl algebra:

$\boldsymbol{u}_{j}\,\boldsymbol{v}_{j}\;=\;q^{2}\,\boldsymbol{v}_{j}\boldsymbol{u}_{j}\quad\Rightarrow\quad\boldsymbol{u}_{j}^{\prime}\,\boldsymbol{v}_{j}^{\prime}\;=\;q^{2}\,\boldsymbol{v}_{j}^{\prime}\,\boldsymbol{u}_{j}^{\prime}\;,$
(A.10)

while the elements with different $j$ commute. The classical limit of the
local Weyl algebra implies the conservation of the canonical form

$\sum_{j}d\log u_{j}\wedge d\log v_{j}\;=\;\sum_{j}d\log u_{j}^{\prime}\wedge
d\log v_{j}^{\prime}\;.$ (A.11)

There is a temptation to give some geometric interpretation to the map
$S_{12}$ and to Pentagon and ten-term relations using the idea that the
quadrilateral $ABCD$ for the map $S_{12}$ is a tetrahedron, the Pentagon
relation (1.3) corresponds to a dissection of a four-simplex into five
tetrahedra, and so on. However, the attempt to give geometric interpretation
failed. In what follows, we will understand the linear problems only in the
combinatorial way. For the shortness, we will use notation

$(ABC)_{j}^{\\#}\quad\Leftrightarrow\quad\phi_{A}-\boldsymbol{v}_{j}^{\\#}\phi_{B}+\boldsymbol{u}_{j}^{\\#}\phi_{C}\;=\;0\;.$
(A.12)

##  Appendix B Tetrahedral Map

The Tetrahedral map (2.7) appears as the equivalence of

$\left\\{\begin{array}[]{l}\displaystyle(DBC)_{1}\\\ \displaystyle(EAC)_{2}\\\
\displaystyle(DAB)_{3}\end{array}\right.\quad\sim\quad\left\\{\begin{array}[]{l}\displaystyle(EBC)_{1}^{\prime}\\\
\displaystyle(DAC)_{2}^{\prime}\\\
\displaystyle(EAB)_{3}^{\prime}\end{array}\right.$ (B.1)

Precise answer for
$\mathcal{R}_{123}\;:\;\boldsymbol{u}_{j},\boldsymbol{v}_{j}\;\to\;\boldsymbol{u}_{j}^{\prime},\boldsymbol{v}_{j}^{\prime}$
is

$\begin{array}[]{lll}\displaystyle\boldsymbol{u}_{1}^{\prime}\;=\;\boldsymbol{u}_{2}+\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{u}_{2}^{\prime}\;=\;\boldsymbol{u}_{3}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{u}_{1}\;,&\displaystyle\boldsymbol{u}_{3}^{\prime}\;=\;\boldsymbol{u}_{2}\boldsymbol{u}_{1}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\;,\\\
\\\
\displaystyle\boldsymbol{v}_{1}^{\prime}\;=\;\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\;,&\displaystyle\boldsymbol{v}_{2}^{\prime}\;=\;\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{v}_{3}\;,&\displaystyle\boldsymbol{v}_{3}^{\prime}\;=\;\boldsymbol{v}_{2}+\boldsymbol{u}_{2}\boldsymbol{u}_{1}^{-1}\boldsymbol{v}_{3}\;.\end{array}$
(B.2)

The reason why we repeat (2.7) here is that the map (B.2) satisfies the
functional Tetrahedron equation in the terms of free algebra of
$\boldsymbol{u}_{i},\boldsymbol{v}_{j}$, $j=1,\cdots,6$, not necessarily the
ultra-local algebra.

The linear problems (B.1) has the following combinatorics:

$1$$2$$3$$C$$B$$A$$D$$E$ (B.3)

Here $1,2,3$ are the indices of $\boldsymbol{u},\boldsymbol{v}$ in the linear
equations. Incoming edges correspond to
$\boldsymbol{u}_{j},\boldsymbol{v}_{j}$, while the outgoing edges correspond
to $\boldsymbol{u}_{j}^{\prime},\boldsymbol{v}_{j}^{\prime}$. Edge $1$ is the
intersection of planes $B$ and $C$, edge $2$ is the intersection of planes $A$
and $C$, and edge $3$ is the intersection of planes $A$ and $B$. The edges
have two “colours”, $D$ and $E$, as it is shown in (B.3).

These combinatorial rules allows one to extend the linear problems to the
whole cubic lattice.

##  Appendix C Evolution map

The evolution map is given by (3.3). Here we repeat it with the time variable
shown explicitly:

$\begin{array}[]{ll}\displaystyle\boldsymbol{u}_{1,(i+1,j)}^{(t+1)}\;=\;\left(\boldsymbol{u}_{2}+\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}\boldsymbol{u}_{1}\right)_{(i,j)}^{(t)}\;,&\displaystyle\boldsymbol{v}_{1,(i+1,j)}^{(t+1)}\;=\;\left(\boldsymbol{v}_{2}\boldsymbol{v}_{3}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\right)_{(i,j)}^{(t)}\;,\\\
\\\
\displaystyle\boldsymbol{u}_{2,(i,j)}^{(t+1)}\;=\;\left(\boldsymbol{u}_{3}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{u}_{1}\right)_{(i,j)}^{(t)}\;,&\displaystyle\boldsymbol{v}_{2,(i,j)}^{(t+1)}\;=\;\left(\boldsymbol{v}_{1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})^{-1}\boldsymbol{v}_{3}\right)_{(i,j)}^{(t)}\;,\\\
\\\
\displaystyle\boldsymbol{u}_{3,(i,j+1)}^{(t+1)}\;=\;\left(\boldsymbol{u}_{2}\boldsymbol{u}_{1}^{-1}(\boldsymbol{v}_{1}+\boldsymbol{u}_{3})\right)_{(i,j)}^{(t)}\;,&\displaystyle\boldsymbol{v}_{3,(i,j+1)}^{(t+1)}\;=\;\left(\boldsymbol{v}_{2}+\boldsymbol{u}_{2}\boldsymbol{u}_{1}^{-1}\boldsymbol{v}_{3}\right)_{(i,j)}^{(t)}\;.\end{array}$
(C.1)

The set of all auxiliary linear equations can be described by the following
set of the triples,

$(D_{i+k+j},B_{k},C_{j})_{1,(i,j)}\;,\quad(D_{i+k+j+1},A_{i},C_{j})_{2,(i,j)}\;,\quad(D_{i+k+j},A_{i},B_{k})_{3,(i,j)}\;,$
(C.2)

where we used notation of eq. (A.12), and $t\;=\;i-k+j$. Periodical boundary
conditions $i,j\in\mathbb{Z}_{N}$ require the periodicity of $D_{i+k+j}$. Note
that the coordinate $\boldsymbol{n}$ (4.1) is given by
$\boldsymbol{n}=(i,-k,j)$, see also (4.3).

One can see now, the auxiliary liner problem (C.2) at fixed time $t$ is the
set of $3N^{2}$ equations for $4N$ auxiliary linear variables. We did not find
any way to relate this system to the integrals of motion (except for $N=1$).
In particular, the combinatorics of (C.2) does not allow to interpret it as a
set of Fay’s identities.

##  Appendix D Another example of classical Pentagon map

We’d like to mention one geometric example of Pentagon and Tetrahedral maps
solving the functional Pentagon and Tetrahedron equations. This example is
purely classical, it has no Poisson structure and quantum counterpart, but it
leads to some classical integrable model on cubic lattice.

We use the framework of Euclidean geometry. Consider the flat quadrilateral
(dissected into two triangles in two ways) with the angles shown below:

$A$$B$$C$$D$$\alpha_{1}$$\beta_{1}$$\gamma_{1}$$\alpha_{2}$$\beta_{2}$$\gamma_{2}$
$\to$$A$$B$$C$$D$$\alpha_{1}^{\prime}$$\beta_{1}^{\prime}$$\gamma_{1}^{\prime}$$\alpha_{2}^{\prime}$$\beta_{2}^{\prime}$$\gamma_{2}^{\prime}$
(D.1)

Define

$u_{j}\;=\;\textrm{{\large e}}^{2\mathsf{i}\beta_{j}}\;,\quad
v_{j}\;=\;\textrm{{\large e}}^{2\mathsf{i}\gamma_{j}}\;,\quad
u_{j}^{\prime}\;=\;\textrm{{\large e}}^{2\mathsf{i}\beta_{j}^{\prime}}\;,\quad
v_{j}^{\prime}\;=\;\textrm{{\large e}}^{2\mathsf{i}\gamma_{j}^{\prime}}\;.$
(D.2)

The framework of the Euclidean geometry provides

$u_{1}^{\prime}=u_{1}v_{2}\;,\quad v_{1}^{\prime}=\frac{F}{v_{2}}\;,\quad
u_{2}^{\prime}=u_{1}u_{2}F\;,\quad v_{2}^{\prime}=\frac{v_{1}v_{2}}{F}\;,$
(D.3)

where

$F\;=\;-\,\frac{u_{1}u_{2}v_{1}v_{2}-u_{1}v_{1}v_{2}-u_{2}v_{1}v_{2}+v_{1}+v_{2}-1}{u_{1}u_{2}v_{1}v_{2}-u_{1}u_{2}v_{1}-u_{1}u_{2}v_{2}+u_{1}+u_{2}-1}\;.$
(D.4)

It can be verified straightforwardly, $S_{1,2}:u,v\to u^{\prime},v^{\prime}$
satisfies the functional Pentagon and ten-term equations, and therefore a
solution of the functional Tetrahedron equation can be constructed.

##  Appendix E Beyond the Pentagon equation

This section is an attempt to construct a generalisation of the Pentagon and
ten-term relations (1.3,1.4):

$(S_{c})_{23}(S_{b})_{13}(S_{a})_{12}\;=\;\sum_{d,e}m_{a,b,c}^{\;d,e}(S_{d})_{12}(S_{e})_{23}\;,$
(E.1)
$(\overline{S}^{\,a})_{12}(\overline{S}^{\,b})_{13}(\overline{S}^{\,c})_{23}\;=\;\sum_{d,e}\overline{m}^{\,a,b,c}_{\;\,d,e}(\overline{S}^{\,e})_{23}(\overline{S}^{\,d})_{12}\;,$
(E.2)

and

$\begin{array}[]{l}\displaystyle\sum_{b_{1},b_{2},b_{3}}\overline{m}^{\,b_{1},b_{2},b_{3}}_{\;\,c_{1},c_{2}}(S_{b_{1}})_{12}(\overline{S}^{\,a_{1}})_{13}(S_{b_{2}})_{14}(\overline{S}^{\,a_{2}})_{24}(S_{b_{3}})_{34}\;=\\\
\\\
\displaystyle\qquad\qquad=\;\sum_{b_{1},b_{2},b_{3}}m_{b_{1},b_{2},b_{3}}^{\;a_{1},a_{2}}(\overline{S}^{\,b_{3}})_{24}(S_{c_{2}})_{34}(\overline{S}^{\,b_{2}})_{14}(S_{c_{1}})_{12}(\overline{S}^{\,b_{1}})_{13}\;.\end{array}$
(E.3)

Due to these (hypothetical) relations

$R_{123}\;=\;\sum_{a}(S_{a})_{13}P_{23}(\overline{S}^{\,a})_{13}$ (E.4)

satisfy the Tetrahedron equation, and, moreover,

$R_{0123}\;=\;\sum_{a}(S_{a})_{13}P_{01}P_{23}(\overline{S}^{\,a})_{13}$ (E.5)

satisfy the $4$-simplex equation.

The formal “Pentagonal algebra” (E.1) has a remarkable feature: it implies
adjoint representations. Namely, the associativity condition for (E.1) reads

$\sum_{b_{1},b_{2},b_{3}}m_{a_{1},a_{2},a_{3}}^{\;b_{1},b_{2}}m_{b_{1},a_{4},a_{5}}^{\;c_{1},b_{3}}m_{b_{2},b_{3},a_{6}}^{\;c_{2},c_{3}}\;=\;\sum_{b_{1},b_{2},b_{3}}m_{a_{1},b_{1},b_{2}}^{\;c_{1},c_{2}}m_{a_{2},a_{4},b_{3}}^{\;b_{1},c_{3}}m_{a_{3},a_{5},a_{5}}^{\;b_{2},b_{3}}\;.$
(E.6)

The associativity condition for $\overline{m}$ is identical. The adjoint
representations are:

$\begin{array}[]{ll}\displaystyle\textrm{(I)}:&\displaystyle
m_{a,b,c}^{\;d,e}\;=\;\langle d,e|S_{c}|a,b\rangle\quad\textrm{or}\quad
m_{a,b,c}^{\;d,e}\;=\;\langle b,a|S_{c}|e,d\rangle\;,\\\ \\\
\displaystyle\textrm{(II)}:&\displaystyle m_{a,b,c}^{\;d,e}\;=\;\langle
b,c|S_{a}|d,e\rangle\quad\textrm{or}\quad m_{a,b,c}^{\;d,e}\;=\;\langle
e,d|S_{a}|c,b\rangle\;.\end{array}$ (E.7)

So far, we succeeded to find just one example for $m,\overline{m}$ satisfying
(E.6) and therefore (E.1,E.2,E.3) in the adjoint representations:

$m_{a,b,c}^{\;d,e}\;=\;\overline{m}^{\,a,b,c}_{\;\,d,e}\;=\;\delta_{a+b,d}\;\delta_{b+c,e}\;q^{2ac}\;,$
(E.8)

where $q\in\mathbb{C}$ for $a,\dots,e\in\mathbb{Z}$ and $q^{2N}\;=\;1$ for
$a,\dots,e\in\mathbb{Z}_{N}$.


# An Information-Theoretic Analysis of Bayesian Reinforcement Learning
††thanks: This work was supported in part by the Knut and Alice Wallenberg
Foundation, the Swedish Foundation for Strategic Research, and the Swedish
Research Council under contract 2019-03606.

Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael
Skoglund  Division of Information Science and Engineering (ISE)  KTH Royal
Institute of Technology<EMAIL_ADDRESS>
###### Abstract

Building on the framework introduced by Xu and Raginksy [1] for supervised
learning problems, we study the best achievable performance for model-based
Bayesian reinforcement learning problems. With this purpose, we define minimum
Bayesian regret (MBR) as the difference between the maximum expected
cumulative reward obtainable either by learning from the collected data or by
knowing the environment and its dynamics. We specialize this definition to
reinforcement learning problems modeled as Markov decision processes (MDPs)
whose kernel parameters are unknown to the agent and whose uncertainty is
expressed by a prior distribution. One method for deriving upper bounds on the
MBR is presented and specific bounds based on the relative entropy and the
Wasserstein distance are given. We then focus on two particular cases of MDPs,
the multi-armed bandit problem (MAB) and the online optimization with partial
feedback problem. For the latter problem, we show that our bounds can recover
from below the current information-theoretic bounds by Russo and Van Roy [2].

###### Index Terms:

information-theoretic bounds, Markov decision process, multi-armed bandit
problem, reinforcement learning, Bayesian regret, mutual information,
Wasserstein distance

##  I Introduction

In model-based reinforcement learning problems [3, 4], an agent interacts
sequentially with a dynamic environment by taking actions in order to maximize
its long-term performance.

This paper, as most related work in this field, focuses on systems and control
objectives that are modeled as finite time horizon _Markov decision processes_
(MDPs). At each time $t=1,\ldots,T$, the agent observes the environment state
$S_{t}$ and takes an action $A_{t}$ following a decision policy $\varphi_{t}$.
Independently of the action, the environment produces a random outcome
$Y_{t}$. The reward is obtained as a deterministic function of the system’s
outcome and the chosen action, $R_{t}=r(Y_{t},A_{t})$. The data is collected
in a history $H^{t+1}=(S_{1},A_{1},R_{1},\ldots,S_{t},A_{t},R_{t})$ and the
system evolves to a state $S_{t+1}$. The procedure then repeats until the end
of the time horizon, $t=T$.

In the Bayesian setting, the MDP model $\Phi$ is treated as a random element
of some parametric model family, which is drawn according to a prior
distribution of the environment parameters $\Theta$. The goal of the agent is
to identify a policy that yields the highest expected cumulative reward
$\mathbb{E}[\sum_{t=1}^{T}r(Y_{t},A_{t})]$ under the uncertainty of these
parameters.

The decision-making process in Bayesian reinforcement learning is typically
more computationally demanding than the frequentist approach, however this
setting presents various advantages as it facilitates regularization, handles
parameter uncertainty naturally, and provides ways to solve the exploration-
exploitation trade-off [5].

Following the work from Xu and Raginsky on Bayesian supervised learning [1],
we put aside the computational aspect to study the best achievable performance
for model-based Bayesian reinforcement learning. We define the minimum
Bayesian regret as the difference between the Bayesian cumulative reward
$R_{\phi}(\kappa_{H})$, defined as the maximum expected cumulative reward
attainable by learning from the sequentially collected data, and
$R_{\phi}(\kappa_{\Theta})$, the maximum expected cumulative reward that could
be reached if the environment parameters were known. We develop information-
theoretic upper bounds on the minimum Bayesian regret under various
assumptions for the reward function using the relative entropy and the
Wasserstein distance.

#### Structure of the paper

Section II summarizes the contributions of this paper. The notations are
introduced in Section III. Section IV presents the different models of
decision processes studied and gives the definition of the Bayesian cumulative
reward and the minimum Bayesian regret. Section V and VI are devoted to
information-theoretic upper bounds on the MBR. Finally, conclusions are
presented in Section VII.

##  II Contributions

In this work, inspired by Xu and Raginsky’s [1] framework on the study of the
best achievable performance of supervised learning problems, we propose an
analogous framework for the study of model-based reinforcement learning
problems. Our contributions in this regard can be summarized as:

  1. 1.

Developing a theoretical framework of model-based Bayesian MDPs suited for
information-theoretic studies.

  2. 2.

Proposing a definition of the minimum Bayesian regret (MBR) for reinforcement
learning problems modeled as Markov decision processes.

  3. 3.

Presenting a data processing inequality for the Bayesian cumulative reward in
Lemma 1.

  4. 4.

Formulating upper bounds on the MBR for general MDPs based on the relative
entropy (Proposition 1) and the Wasserstein distance (Proposition 2). We
present particular cases of these bounds for the case of bounded reward
functions in Corollaries 1 and 2, and the tightness of these results are
compared in Remark 3.

  5. 5.

Deriving MBR bounds for the multi-armed bandit and for the online optimization
with partial feedback problems. In this last setting, we show how our bound
recovers _from below_ results from Russo and Van Roy [2].

##  III Notations and preliminaries

Throughout the paper, random variables $X$ are written in capital letters,
their realizations $x$ in lower-case letters, and their set of outcomes
$\mathcal{X}$ in calligraphic letters. The probability distributions of a
random variable $X$ is denoted as $\mathbb{P}_{X}$. When more than one random
variable is considered, e.g., $X$ and $Y$, we use $\mathbb{P}_{X,Y}$ to denote
their joint distribution and $\mathbb{P}_{X}\mathbb{P}_{Y}$ for their product
distribution111Note that this slight abuse of notation does not mean that the
product distribution is the product of the distributions.. We write the
conditional probability distribution of $Y$ given $X$ as $\mathbb{P}_{Y|X}$,
defining a probability distribution $\mathbb{P}_{Y|X=x}$ over $\mathcal{Y}$
for each element $x\in\mathcal{X}$.

We use the underscore notation $X_{t}$ to represent a random variable at time
$t=1,\ldots,T$ and the exponent notation $X^{t}$ to denote a sequence of
random variables $X^{t}\equiv(X_{1},\ldots,X_{t})$ for $t=2,\ldots,T$. For
consistency we let $X^{1}\equiv X_{1}$.

The relative entropy between two probability distributions $\mathbb{P}$ and
$\mathbb{Q}$ is defined as
$D_{\textnormal{KL}}(\mathbb{P}\>\|\>\mathbb{Q}):=\int\log\big{(}\frac{d\mathbb{P}}{d\mathbb{Q}}\big{)}d\mathbb{P}$
if $\mathbb{P}$ is absolutely continuous with respect to $\mathbb{Q}$ and
$D_{\textnormal{KL}}(\mathbb{P}\>\|\>\mathbb{Q})\to\infty$ otherwise. The
notation $d\mathbb{P}/d\mathbb{Q}$ is the Radon-Nikodym derivative. Similarly,
the mutual information between $X$ and $Y$ is defined as
$\textup{I}(X;Y):=D_{\textnormal{KL}}(\mathbb{P}_{X,Y}\>\|\>\mathbb{P}_{X}\mathbb{P}_{Y})$,
and the conditional mutual information between $X$ and $Y$, given $Z$, as
$\textup{I}(X;Y|Z):=\mathbb{E}[\textup{I}(X;Y|Z=z)]$, where
$\textup{I}(X;Y|Z=z):=D_{\textnormal{KL}}(\mathbb{P}_{X,Y|Z=z}\>\|\>\mathbb{P}_{X|Z=z}\mathbb{P}_{Y|Z=z})$.

Finally, if two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ are
defined in a Polish space $\mathcal{X}$ with respect to a metric $\rho$, then
their Wasserstein distance of order $p\geq 1$ is
$\mathbb{W}_{p}(\mathbb{P},\mathbb{Q}):=\big{(}\inf_{\mathbb{D}\in\Pi(\mathbb{P},\mathbb{Q})}\int\rho
d\mathbb{D}\big{)}^{1/p}$, where $\Pi(\mathbb{P},\mathbb{Q})$ is the set of
all couplings of $\mathbb{P}$ and $\mathbb{Q}$; i.e., all joint distributions
on $\mathcal{X}\times\mathcal{X}$ with marginals $\mathbb{P}$ and
$\mathbb{Q}$. As this work is focused on upper bounds and since by Hölder’s
inequality $\mathbb{W}_{p}\leq\mathbb{W}_{q}$ for all $p\leq q$ [6, Remark
6.6], in what follows, we will only be using the Wasserstein distance of order
$1$, $\mathbb{W}:=\mathbb{W}_{1}$. For a discrete random variable $X$, the
Shannon entropy is defined as
$\textup{H}(X)\coloneqq\mathbb{E}[-\log(\mathbb{P}_{X}(X))]$.

##  IV Model and Definitions

In this section we first introduce formally Markov decision processes. We then
present the multi-armed bandit and the online optimization with partial
feedback problems two special cases of MDPs. After that, we describe Bayesian
cumulative reward and prove that it respects a data-processing inequality.
Finally, we define minimum Bayesian regret.

###  IV-A Markov Decision Process

In a _Markov decision process_ (MDP), at each time step $1,\ldots,T$, an agent
interacts with the environment by observing the system’s state
$S_{t}\in\mathcal{S}$ and selecting accordingly an action
$A_{t}\in\mathcal{A}$. The system then produces an outcome
$Y_{t}\in\mathcal{Y}$ which the agent associates with a scalar reward
$R_{t}\in\mathbb{R}$.

In Bayesian reinforcement learning, the environment is completely
characterized by a random variable $\Theta\in\mathcal{O}$ with probability
distribution $\mathbb{P}_{\Theta}$. Therefore, an MDP $\Phi$ is defined by a
transition kernel
$\kappa_{\textnormal{trans}}:\mathscr{S}\times(\mathcal{S}\times\mathcal{A}\times\mathcal{O})\to[0,1]$
such that
$\mathbb{P}_{S_{t+1}|S_{t},A_{t},\Theta}=\kappa_{\textnormal{trans}}(\cdot,(S_{t},A_{t},\Theta))$,
an outcome kernel
$\kappa_{\textnormal{out}}:\mathscr{Y}\times(\mathcal{S}\times\mathcal{O})\to[0,1]$
such that
$\mathbb{P}_{Y_{t}|S_{t},\Theta}=\kappa_{\textnormal{out}}(\cdot,(S_{t},\Theta))$,
an initial state prior distribution $\mathbb{P}_{S|\Theta}$ such that
$S_{1}\sim\mathbb{P}_{S|\Theta}$, and a reward function
$r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$. The reward is a deterministic
function of the system’s outcome and the chosen action, hence there is a
reward’s kernel
$\kappa_{\textnormal{reward}}:\mathcal{B}(\mathbb{R})\times(\mathcal{S},\mathcal{A},\mathcal{O})\to[0,1]$
such that
$\mathbb{P}_{R_{t}|S_{t},A_{t},\Theta}=\kappa_{\textnormal{reward}}(\cdot,(S_{t},A_{t},\Theta))$.

The task in Bayesian reinforcement learning is to learn a policy
$\varphi=\\{\varphi_{t}:\mathcal{S}\times\mathcal{H}^{t}\to\mathcal{A}\\}_{t=1}^{T}$
taking an action $A_{t}$ based on the current observation $S_{t}$ and the past
collected data $H^{t}$, where $H_{t+1}=(S_{t},A_{t},R_{t})$ that maximizes the
_cumulative expected reward_
$r_{\Phi}(\varphi)\coloneqq\mathbb{E}\big{[}\sum_{t=1}^{T}r\big{(}Y_{t},\varphi_{t}(S_{t},H^{t})\big{)}\big{]}$.

###  IV-B Static state MDP and multi-armed bandit problem

A _static state_ MDP is an MDP whose transition kernel
$\kappa_{\textnormal{trans}}$ is such that the system’s state remains
constant, i.e. $S_{t}=S$ for all $t$. We will use the notation $\Pi$ to refer
to such MDP.

A _multi-armed bandit_ (MAB) problem can be formalized as a static state MDP
whose environment parameters $\Theta$ and outcomes $Y_{t}$ are independent of
$S$. Similarly to an MDP, the task in a MAB problem is to learn a policy
$\varphi=\\{\varphi_{t}:\mathcal{S}\times\mathcal{H}^{t}\to\mathcal{A}\\}_{t=1}^{T}$
taking an action $A_{t}$ based on the past collected data $H^{t}$, where
$H_{t+1}=(A_{t},R_{t})$ that maximizes the cumulative expected reward
$r_{\Pi}(\varphi)\coloneqq\mathbb{E}\big{[}\sum_{t=1}^{T}r\big{(}Y_{t},\varphi_{t}(S,H^{t})\big{)}\big{]}$.

A variant of that problem is the _online optimization problem with partial
feedback_ studied by Russo and Van Roy [2]. This problem can also be modeled
as a static MDP $\Pi$ with a finite action space $\mathcal{A}$ where at each
time $t=1,\ldots,T$, the agent selects an action $A_{t}$ and observes a “per-
action outcome” $Y_{t,A_{t}}\in\mathcal{Y}^{\prime}$ giving rise to past
collected data $H^{t}$ with $H_{t+1}=(A_{t},Y_{t,A_{t}})$. The agent
associates the “per-action outcome” with a reward
$R_{t}=r^{\prime}(Y_{t,A_{t}})$ through a preference function
$r^{\prime}:\mathcal{Y}^{\prime}\to\mathbb{R}$. In this setting, the random
outcome $Y_{t}\in\mathcal{Y}$ is the vector formed with all the possible
outcomes, $Y_{t}\equiv\\{Y_{t,a}\\}_{a\in\mathcal{A}}$ and the reward function
$r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$ is a function such that for all
$Y_{t}\in\mathcal{Y}$ and $A_{t}\in\mathcal{A}$, we have
$r(Y_{t},A_{t})=r^{\prime}(Y_{t,A_{t}})$. In this problem, as well, the
environment parameters $\Theta$ and outcomes $Y_{t}$ are independent of $S$.

###  IV-C The Bayesian Cumulative Reward

A decision policy that maximizes the expected cumulative reward among all
policies is called a _Bayesian decision policy_. The corresponding maximum
expected cumulative reward is defined as the _Bayesian cumulative reward_.

######  Definition 1.

The _Bayesian cumulative reward_ (BCR) of a Markov decision process $\Phi$ is
defined as $R_{\Phi}\coloneqq\sup_{\varphi}r_{\Phi}(\varphi)$, where the
supremum is taken over the collection $\varphi$ of all decision rules
$\varphi_{t}:\mathcal{S}\times\mathcal{H}^{t}\to\mathcal{A}$ such that the
expectation is defined.

The notion of Bayesian cumulative reward can be generalized to allow the agent
to select an action using some knowledge $X^{t}$ such that each $X_{t+1}$ is
obtained from $(S_{t},A_{t},Y_{t},\Theta)$. In this generalized model, the
knowledge $X_{t}$ is obtained through a knowledge kernel
$\kappa_{\textnormal{know}}:\mathscr{X}\times(\mathcal{S}\times\mathcal{A}\times\mathcal{Y}\times\mathcal{O})\to[0,1]$
such that
$\mathbb{P}_{X_{t+1}|S_{t},A_{t},Y_{t},\Theta}=\kappa_{\textnormal{know}}(\cdot,(S_{t},A_{t},Y_{t},\Theta))$.
Now, let
$\varphi=\\{\varphi_{t}:\mathcal{S}\times\mathcal{X}^{t}\to\mathcal{A}\\}_{t=1}^{T}$
be a policy in this relaxed setting. Then, the _generalized Bayesian
cumulative reward_ (also written as BCR when no confusion is possible) of an
MDP $\Phi$ with knowledge kernel $\kappa_{\textnormal{know}}$ is
$R_{\Phi}(\kappa_{\textnormal{know}})\coloneqq\sup_{\varphi}r_{\Phi}(\kappa_{\textnormal{know}},\varphi)$,
where

$\displaystyle
r_{\Phi}(\kappa_{\textnormal{know}},\varphi)\coloneqq\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t},\varphi_{t}(S_{t},X^{t})\big{)}\bigg{]}$

and again the supremum is taken over the collection $\varphi$ of all decision
rules $\varphi_{t}:\mathcal{S}\times\mathcal{X}^{t}\to\mathcal{A}$ such that
the expectation above is defined.

######  Remark 1.

Given an MDP $\Phi$, let
$\mathcal{X}=\mathcal{S}\times\mathcal{A}\times\mathbb{R}$ and
$\kappa_{\textnormal{know}}$ be a kernel such that
$X_{t+1}=(S_{t},A_{t},R_{t})$ and denote this kernel
$\kappa_{\textnormal{H}}$. Note that $X_{t}=H_{t}$ and
$R_{\Phi}(\kappa_{\textnormal{H}})=R_{\Phi}$.

After defining the generalized Bayesian cumulative reward, one can study the
case where the agent has access to some processed information $Z_{t}$ obtained
from the knowledge $X^{t}$. Let $\kappa_{\textnormal{process}}$ denote a
collection of processing kernels
$\\{\kappa_{\textnormal{process,t}}:\mathscr{Z}\times(\mathcal{X}^{t})\to[0,1]\\}_{t=1}^{T}$
such that
$\mathbb{P}_{Z_{t}|X^{t}}=\kappa_{\textnormal{process,t}}\big{(}\cdot,(X^{t})\big{)}$
for each $t=1,\ldots,T$. Then the _processed Bayesian cumulative reward_ with
knowledge kernel $\kappa_{\textnormal{know}}$ and process kernels
$\kappa_{\textnormal{process}}$ is
$R_{\Phi}(\kappa_{\textnormal{know}},\kappa_{\textnormal{process}})\coloneqq\sup_{\psi}r_{\Phi}(\kappa_{\textnormal{know}},\kappa_{\textnormal{process}},\psi)$,
where

$\displaystyle
r_{\Phi}(\kappa_{\textnormal{know}},\kappa_{\textnormal{process}},\psi)\coloneqq\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t},\psi_{t}(S_{t},Z_{t})\big{)}\bigg{]}$

and the supremum is taken over the collection $\psi$ of all decision rules
$\psi=\\{\psi_{t}:\mathcal{S}\times\mathcal{Z}\to\mathcal{A}\\}_{t=1}^{T}$
such that the expectation above is defined.

###  IV-D Data processing inequality for the BCR

An important property of the Bayesian cumulative reward is the data processing
inequality (DPI), stating that no amount of processing of the knowledge random
variables can increase the cumulative reward. This is formalized in the
following lemma.

######  Lemma 1.

Let $\kappa_{\textnormal{U}}$ be a knowledge kernel associated with an MDP
$\Phi$ and $\kappa_{\textnormal{V}|\textnormal{U}}$ a collection of processing
kernels. Then, the cumulative Bayesian reward using the knowledge from $U$ is
at least as large as the processed Bayesian cumulative reward using the
processed knowledge from $V$. More precisely,

$R_{\Phi}(\kappa_{\textnormal{U}})\geq
R_{\Phi}(\kappa_{\textnormal{U}},\kappa_{\textnormal{V}|\textnormal{U}})$

###### Intuition of the proof.

The proof follows by iteratively employing [7, Lemma 3.22] in a similar
fashion to [1, Lemma 1] and taking care that the random objects in the
definitions of $R_{\Phi}(\kappa_{U})$ and $R_{\Phi}(\kappa_{U},\kappa_{V|U})$
follow the distributions described by the dynamics of the MDP $\Phi$ and their
respective actions $\varphi_{t}$ and $\psi_{t}$. The complete proof is in
appendix A. ∎

###  IV-E The Minimum Bayesian Regret (MBR)

We define the _fundamental limit of the Bayesian cumulative reward_ as the
Bayesian cumulative reward for a knowledge kernel such that $X_{t}=\Theta$,
that is when the environment parameters are known to the agent. We denote such
a kernel as $\kappa_{\Theta}$.

######  Definition 2.

The _fundamental limit of the Bayesian cumulative reward_ of a Markov decision
process $\Phi$ is defined as

$\displaystyle
R_{\Phi}(\kappa_{\Theta})\coloneqq\sup_{\\{\psi_{t}\\}_{t=1}^{T}}\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t},\psi_{t}(S_{t},\Theta)\big{)}\bigg{]},$

where the kernel $\kappa_{\Theta}$ is such that $X_{t}=\Theta$ for all
$t=1,\ldots,T$.

######  Assumption 1.

For the rest of the paper, we will assume that the supremum from Definition 2
exists and we will denote by $\psi^{\star}=\\{\psi^{\star}_{t}\\}_{t=1}^{T}$ a
policy that achieves it.

We define the gap between this limit and the Bayesian cumulative reward as the
_minimum Bayesian regret_.

######  Definition 3.

The _minimum Bayesian regret (MBR)_ of a Markov decision process $\Phi$ is
defined as

$\textnormal{MBR}_{\Phi}\coloneqq
R_{\Phi}(\kappa_{\Theta})-R_{\Phi}(\kappa_{\textnormal{H}}).$

The MBR characterizes the regret of the optimal decision policy that has
access to the collected data, but not to environment parameters, and is
therefore an algorithm-independent quantity. It can be interpreted as the
inherent difficulty of the reinforcement learning problem resulting from the
lack of knowledge about the environment parameters $\Theta$.

##  V Upper bounds on the Minimum Bayesian Regret

In this section, we start by giving an upper bound of the minimum Bayesian
regret in terms of the difference of the fundamental limit of the BCR,
$R_{\Phi}(\kappa_{\Theta})$, and the processed BCR with the optimal Bayes
parameters’ estimator $\mathbb{P}_{\Theta|H^{t}}$ as the processing kernel and
the optimal policy of $R_{\Phi}(\kappa_{\Theta})$. That is, the difference
between the best obtainable risk knowing the environment parameters $\Theta$,
and the best obtainable risk inferring the parameters with an optimal
estimator. This bound, in turn, can be developed into a bound that compares
the sum of the individual terms in the optimal trajectory of
$R_{\Phi}(\kappa_{\Theta})$ and those obtained with the processing kernels
$\mathbb{P}_{\Theta|H^{t}}$. This way, we can employ similar techniques to
those in the literature (e.g., [8, 9]) and bound the MBR in terms of the sum
of terms depending on the statistical difference between the distributions of
those two trajectories.

###  V-A The Thompson sampling regret

Consider the fundamental limit of BCR, $R_{\Phi}(\kappa_{\Theta})$, and its
optimal trajectory $\psi^{\star}$. A natural algorithm to try to solve an MDP
$\Phi$ when environment $\Theta$ is unknown is to estimate the environment
parameters with some processing kernel of the history
$\kappa_{\Theta|\textnormal{H}}$ and select an optimal action based on such
processing. An elegant scenario would be to have the additional information of
knowing which is the optimal trajectory $\psi^{\star}$ and to be able to
calculate the Bayes optimal estimator $\mathbb{P}_{\Theta|H^{t}}$ to process
the history. In fact, for a static MDP $\Pi$, this algorithm is studied in the
literature and is known as the Thompson’s sampling algorithm  [10, 11, 12, 13,
14, 2]. Therefore, the next lemma shows that the MBR is bounded from above by
the difference of $R_{\Phi}(\kappa_{\Theta})$ and the BCR of such an
algorithm,
$r_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H},\psi^{\star}})$.

######  Lemma 2.

For any MDP $\Phi$, the MBR can be upper bounded as follows,

$\textnormal{MBR}_{\Phi}\leq
R_{\Phi}(\kappa_{\Theta})-r_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}},\psi^{\star}).$

###### Proof.

The proof starts by using Lemma 1 to lower bound
$R_{\Phi}(\kappa_{\textnormal{H}})$ with
$R_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}})$. The last
inequality follows from the definition of
$R_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}})$ being the
supremum over $\psi$ of
$r_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}},\psi)$. More
precisely,

$\displaystyle\textnormal{MBR}_{\Phi}$
$\displaystyle=R_{\Phi}(\kappa_{\Theta})-R_{\Phi}(\kappa_{\textnormal{H}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}R_{\Phi}(\kappa_{\Theta})-R_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}R_{\Phi}(\kappa_{\Theta})-r_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}},\psi^{\star}).$

∎

In what follows, we will use the notations $Y^{\star}_{t}$ and $S^{\star}_{t}$
for the outcomes and states obtained from the actions derived from
$\psi^{\star}$, the kernels that describe the MDP $\Phi$, and the knowledge
kernel $\kappa_{\Theta}$. Similarly we will let $\hat{Y}_{t}$, $\hat{S}_{t}$
and $\hat{H}_{t}$ be the outcomes, states, and histories obtained from the
actions derived from $\psi^{\star}$, the kernels that describe the MDP $\Phi$
with knowledge kernel $\kappa_{\textnormal{H}}$, and processing kernels
$\kappa_{\Theta|\textnormal{H}}$. The following lemma builds on Lemma 2 and
shows how the MBR can be written as the sum of the individual differences of
the expected rewards obtained following the optimal trajectory
$(Y^{\star}_{t},S^{\star}_{t})_{t=1}^{T}$ and the trajectory of the
aforementioned algorithm $(\hat{Y}_{t},\hat{S}_{t})_{t=1}^{T}$ given the
history $\hat{H}^{t}$.

Unrolling $R_{\Phi}(\kappa_{\Theta})$ and
$r_{\Phi}(\kappa_{\textnormal{H}},\kappa_{\textnormal{H}|\Theta},\psi^{\star})$
and using the linearity of the expectation and the law of total expectation
reveals that the right-hand side term from Lemma 2 can be written as

$\sum_{t=1}^{T}\mathbb{E}\bigg{[}\mathbb{E}\Big{[}r\big{(}Y^{\star}_{t},\psi^{\star}_{t}(S^{\star}_{t},\Theta)\big{)}-r\big{(}\hat{Y}_{t},\psi^{\star}_{t}(\hat{S}_{t},\hat{\Theta}_{t})\big{)}\Big{|}\Theta,\hat{\Theta}_{t},\hat{H}^{t}\Big{]}\bigg{]}.$
(1)

######  Remark 2.

The importance of this re-formulation lays in the fact that the first term
inside the conditional expectation is distributed according to
$\mathbb{P}_{Y^{\star},S^{\star}|\Theta}$ since $(Y^{\star},S^{\star})$ are
independent of the history $\hat{H}^{t}$ when the environment parameters
$\Theta$ are known. Similarly, the second term is distributed according to
$\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}}$ since
$(\hat{Y}_{t},\hat{S}_{t})$ are independent of the sampled parameters
$\hat{\Theta}_{t}$ when the history is known. Both facts follow from the
Markov chain
$(Y^{\star}_{t},S^{\star}_{t})-\Theta-(\hat{Y}_{t},\hat{S}_{t})-\hat{H}^{t}-\hat{\Theta}_{t}$.
Therefore, conditioned on the history $\hat{H}^{t}$ and the environment
parameters $\Theta,\hat{\Theta}_{t}$, the terms in the sum of (1) are a
difference of expectations of random objects which randomness comes from
distributions on the same space, which permits us to employ known decoupling
techniques to bound these differences in terms of such distributions.

In the sequel, we use this fact to bound the MBR as the sum of terms depending
on the statistical difference between the distributions of the elements from
the optimal trajectory $(Y^{\star}_{t},S^{\star}_{t})|\Theta$ and the
trajectory described by the algorithm with the Bayes optimal parameters’
estimator $(\hat{Y}_{t},\hat{S}_{t})|\hat{H}^{t}$. More precisely, we use the
techniques from e.g. [2, 8] when the reward is sub-Gaussian, from e.g. [9, 15]
when it is Lipschitz, and from [9] to connect both settings when the reward is
bounded.

###  V-B Sub-Gaussian reward functions

We consider arbitrary reward functions
$r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$ mapping an outcome and an action
to a scalar reward. Under the assumption that the random reward
$r(\hat{Y}_{t},\psi_{t}^{\star}(\hat{S}_{t},\theta))$ is $\sigma_{t}^{2}$-sub-
Gaussian under $\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}=\hat{h}^{t}}$
for all $\theta\in\mathcal{O}$ and all $\hat{h}^{t}\in\mathcal{H}^{t}$, the
$\textnormal{MBR}_{\Phi}$ is bounded by a sum of terms related to the relative
entropy between the distribution of the elements of each step of the optimal
trajectory, i.e., $Y^{\star}_{t},S^{\star}_{t}$, and the Thompson’s sampled
trajectory, i.e., $\hat{Y}_{t},\hat{S}_{t}$. This is formalized in the
following Proposition.

######  Proposition 1.

If for all $t=1,\ldots,T$, the random reward
$r(\hat{Y}_{t},\psi_{t}^{\star}(\hat{S}_{t},\theta))$ is $\sigma_{t}^{2}$-sub-
Gaussian under $\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}=\hat{h}^{t}}$
for all $\theta\in\mathcal{O}$ and all $\hat{h}^{t}\in\mathcal{H}^{t}$, then,

$\displaystyle\textnormal{MBR}_{\Phi}\leq\sum_{t=1}^{T}\mathbb{E}\Big{[}\sqrt{2\sigma_{t}^{2}D_{\textnormal{KL}}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta}\>\|\>\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})}\Big{]}.$

###### Proof.

The proof follows from applying Donsker-Varadhan’s inequality [16, Theorem
5.2.1] to (1) using Remark 2 in a similar fashion to [2, 8]. ∎

###  V-C Lipschitz reward functions

In this subsection, we suppose that the set of outcomes and actions
$(\mathcal{Y},\mathcal{A})$ together with the metric
$\rho:(\mathcal{Y}\times\mathcal{A})\times(\mathcal{Y}\times\mathcal{A})\rightarrow\mathbb{R}_{+}$,
form a Polish metric space.

Assume that the reward function $r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$
is $L$-Lipschitz under the metric $\rho$, that is that
$|r(y,a)-r(y^{\prime},a^{\prime})|\leq L\rho((y,a),(y^{\prime},a^{\prime}))$
for all $y,y^{\prime}\in\mathcal{Y}$ and $a,a^{\prime}\in\mathcal{A}$. Under
this assumption, the Wasserstein distance can be used to upper bound the
minimum Bayesian regret.

######  Proposition 2.

Suppose that $(\mathcal{Y}\times\mathcal{A})$ is a metric space with metric
$\rho$. If the reward function $r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$
is $L$-Lipschitz under the metric $\rho$, then

$\textnormal{MBR}_{\Phi}\leq
L\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta},\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})\big{]}.$

###### Proof.

The proof follows from applying Kantorovich–Rubinstein duality [6, Remark 6.5]
to (1) using Remark 2 analogously to [9, 15]. ∎

###  V-D Bounded reward functions

We can obtain upper bounds on the minimum Bayesian regret for bounded reward
functions as particular cases of both Proposition 1 and Proposition 2. We will
consider without loss of generality reward functions bounded in $[0,1]$.

First, from Hoeffding’s lemma [17, Theorem 1], we have that if
$r:\mathcal{Y}\times\mathcal{A}\to[0,1]$ then the reward is $1/4$-sub-Gaussian
under any distribution of the arguments. This fact and Proposition 1 leads to
Corollary 1.

######  Corollary 1.

If the reward function is bounded in $[0,1]$, then, for any MDP $\Phi$,

$\displaystyle\textnormal{MBR}_{\Phi}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\bigg{[}\sqrt{\frac{1}{2}D_{\textnormal{KL}}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta}\>\|\>\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})}\bigg{]}.$

Second, we can note that a bounded $[0,1]$ function is $1$-Lispchitz under the
discrete metric (or Hamming distortion)
$\rho((y,a),(y^{\prime},a^{\prime}))\coloneqq\mathbbm{1}_{(y,a)=(y^{\prime},a^{\prime})}$
where $\mathbbm{1}$ is the indicator function. Using this fact, we can obtain
Corollary 2 from Proposition 2.

######  Corollary 2.

If the reward function is bounded in $[0,1]$, then, for any MDP $\Phi$,

$\textnormal{MBR}_{\Phi}\leq\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta},\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})\big{]}.$

######  Remark 3.

Corollary 2 provides a tighter bound than Corollary 1. Indeed, if the geometry
is ignored (i.e., the discrete metric is considered), then for all
$t=1,\ldots,T$,

$\displaystyle\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta},$
$\displaystyle\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})\big{]}$
$\displaystyle=\mathbb{E}\big{[}\textsc{{TV}}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta},\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})\big{]}$
$\displaystyle\leq\mathbb{E}\bigg{[}\sqrt{\frac{1}{2}D_{\textnormal{KL}}(\mathbb{P}_{Y^{\star}_{t},S^{\star}_{t}|\Theta}\>\|\>\mathbb{P}_{\hat{Y}_{t},\hat{S}_{t}|\hat{H}^{t}})}\bigg{]},$

where the equality follows from [6, Proof of Theorem 6.15] and inequality
follows from Pinsker’s [18, Theorem 6.5] and Bretagnolle–Huber’s result [19,
Proof of Lemma 2.1].

##  VI Upper bounds for static MDPs

In this section, we leverage the bound from Section V to obtain bounds on the
minimum Bayesian regret for static Markov decision processes. We focus here on
the case where the reward function is bounded in $[0,1]$ and leave the sub-
Gaussian and Lipschitz cases to the Appendix B, since they are analogous to
the previous section. We first present upper bounds on the MBR for the multi-
armed bandit problem. We then produce upper bounds to the online optimization
with partial feedback problem, and show how they can recover _from below_ the
results from Russo and Van Roy [2].

Similarly to Section V, we can apply Lemma 2 to upper bound the MBR for static
MDPs. In the case of a static MDP, the right-hand side of that bound can be
written as

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\bigg{[}\mathbb{E}\Big{[}r\big{(}Y_{t},\psi^{\star}_{t}(S,\Theta)\big{)}-r\big{(}Y_{t},\psi^{\star}_{t}(S,\hat{\Theta}_{t})\big{)}\Big{|}\Theta,\hat{\Theta}_{t},\hat{H}^{t}\Big{]}\bigg{]}.$

This rewriting of the bound is obtained the same way as (1): unrolling
$R_{\pi}(\kappa_{\Theta})$ and
$r_{\Pi}(\kappa_{\textnormal{H}},\kappa_{\textnormal{H}|\Theta},\psi^{\star})$,
using the linearity of the expectation, the law of total expectation and the
fact that the state $S$ does not depend on the time $t=1,\ldots,T$.

In the case where the outcomes $\\{Y_{t}\\}_{t=1,\ldots,T}$ do not depend on
the state $S$, as in a MAB problem, it is possible to rewrite the actions
taken by optimal policy $\psi^{\star}_{t}(S,\Theta)$ as
$\gamma^{\star}(\Theta)$, where the function
$\gamma^{\star}:\mathcal{O}\to\mathcal{A}$ is such that for all
$S\in\mathcal{S}$ and all $\Theta\in\mathcal{O}$, it holds that
$\psi^{\star}_{t}(S,\Theta)=\gamma^{\star}(\Theta)$. In that case, it comes
that the right-hand side term from Lemma 2 can be written as

$\sum_{t=1}^{T}\mathbb{E}\Big{[}\mathbb{E}\big{[}r(Y_{t},A^{\star})-r(Y_{t},\hat{A}_{t})\big{]}|A^{\star},\hat{A}_{t},\hat{H}^{t}\Big{]}.$
(2)

######  Remark 4.

Under this reformulation, the outcome in the first term inside the conditional
expectation is distributed according to
$\mathbb{P}_{Y_{t}|A^{\star},\hat{H}^{t}}$ and the second term is distributed
according to $\mathbb{P}_{Y_{t}|\hat{H}^{t}}$. This happens since $Y_{t}$ is
independent of the sampled environment parameters $\hat{\Theta}_{t}$, and
therefore independent of the sampled action $\hat{A}_{t}$ when the history
$\hat{H}^{t}$ is known.

###  VI-A Multi-armed bandit problem

In this subsection, we propose minimum Bayesian regret bounds for multi-armed
bandit problems $\Pi$.

The tightest bound we obtain relates the $\textnormal{MBR}_{\Pi}$ to the
Wasserstein distance between the conditional probability of the outcome given
the optimal action and the history collected following a Thompson sampling
policy, and the conditional probability of the outcome given only the history.

######  Proposition 3.

If the reward function is bounded in $[0,1]$, then for any static MDP $\Pi$,

$\textnormal{MBR}_{\Pi}\leq\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t}|\hat{H}^{t}})\big{]}.$

###### Proof.

The proof follows from applying Kantorovich–Rubinstein duality [6, Remark 6.5]
to (2) using Remark 4 in the same way as [9, 15]. ∎

Using the same arguments as in Remark 3, together with Jensen’s inequality,
one can relax the bound from Proposition 3 and relate the
$\textnormal{MBR}_{\Pi}$ to the conditional mutual information between the
outcome $Y_{t}$ and the optimal action $A^{\star}$ given the history
$\hat{H}^{t}$. This is formalized in the following corollary.

######  Corollary 3.

If the reward function is bounded in $[0,1]$, then for any static MDP $\Pi$,

$\displaystyle\textnormal{MBR}_{\Pi}$
$\displaystyle\leq\sum_{t=1}^{T}\sqrt{\frac{1}{2}\textup{I}(Y_{t};A^{\star}|\hat{H}^{t})}.$

This conditional mutual information can be interpreted as the remaining
“amount of surprise about the output $Y_{t}$” after observing the history
$\hat{H}^{t}$ that is removed when the optimal action $A^{\star}$ is revealed.

###  VI-B Online optimization with partial feedback problem

In the special case of online optimization with partial feedback, the right-
hand-side term from Lemma 2 in (2) can be formulated in a compact form using
the preference function:

$\sum_{t=1}^{T}\mathbb{E}\Big{[}\mathbb{E}\big{[}r^{\prime}(Y_{t,A^{\star}})\big{]}-\mathbb{E}\big{[}r^{\prime}(Y_{t,\hat{A}_{t}})\big{]}|A^{\star},\hat{A}_{t},\hat{H}^{t}\Big{]}.$
(3)

######  Remark 5.

In this last rewriting, the outcome in the first term inside the conditional
expectation is distributed according to
$\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}}$ and the second term is
distributed according to $\mathbb{P}_{Y_{t,\hat{A}_{t}}|\hat{H}^{t}}$. This
holds since $Y_{t}$ is independent of the sampled environment parameters
$\hat{\Theta}_{t}$, and therefore independent of the sampled action
$\hat{A}_{t}$ when the history $\hat{H}^{t}$ is known.

As the terms in (3) are a difference of expectations of random objects which
randomness comes from distributions on the same space, we can upper bound the
minimum Bayesian regret using the Wasserstein distance in terms of such
distributions following the techniques from [9, 15]. This is formalized in the
following proposition.

######  Proposition 4.

If the reward function is bounded in $[0,1]$, then for any _online
optimization problem with partial feedback_ $\Pi$,

$\textnormal{MBR}_{\Pi}\leq\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}.$

###### Proof.

The proof follows from applying Kantorovich–Rubinstein duality [6, Remark 6.5]
to (3) using Remark 5. ∎

This bound can also be relaxed following a similar procedure as Remark 3 to
relate the $\textnormal{MBR}_{\Pi}$ to the relative entropy between the
distribution of the “per-action outcome” $Y_{t,A^{\star}}$ given the optimal
action $A^{\star}$ and the history $\hat{H}^{t}$ and given the history only.

######  Corollary 4.

If the reward function is bounded in $[0,1]$, then for any _online
optimization problem with partial feedback_ $\Pi$,

$\displaystyle\textnormal{MBR}_{\Pi}\leq\sum_{t=1}^{T}\mathbb{E}\bigg{[}\sqrt{\frac{1}{2}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})}\bigg{]}.$

As the above stated Proposition 4 is derived using Lemma 2, its bound
naturally holds for the regret of the Thompson sampling algorithm, namely:

$\displaystyle R_{\Pi}(\kappa_{\Theta})-$ $\displaystyle
r_{\Pi}(\kappa_{\textnormal{H}},\kappa_{\Theta|\textnormal{H}},\psi^{\star})\leq$
$\displaystyle\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}$

We can further relax this bound to recover results from Russo and Van Roy [2].
More specifically, we can recover the general bound combining [2, Propositions
1 and 3], and the specific bound combining [2, Propositions 1 and 4], for
which it is assumed that the outcome $Y_{t}$ is perfectly revealed upon
observing $Y_{t,a}$ for any $a\in\mathcal{A}$. These claims are formalized in
Corollary 5.

######  Corollary 5.

If the reward function is bounded in $[0,1]$, then for any _online
optimization problem with partial feedback_ $\Pi$, we have the following
inequality on the bound from Proposition 4:

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}\leq\sqrt{\frac{1}{2}|\mathcal{A}|\textup{H}(A^{\star})T}.$

Under the additional assumption that the outcome $Y_{t}$ is perfectly revealed
upon observing $Y_{t,a}$ for any $a\in\mathcal{A}$, one can obtain a tighter
result:

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}\leq\sqrt{\frac{1}{2}\textup{H}(A^{\star})T}.$

###### Intuition of the proof.

For both results, the proof starts from using the same steps as Remark 3 to
relax the bound from Proposition 4. Then, both of the proofs rely on the
application of Cauchy-Schwartz’s and Jensen’s inequalities to obtain a bound
using the sum of the conditional mutual information between the optimal action
$A^{\star}$ and the “per-action outcome” $Y_{t,A_{t}}$ given the history
$\hat{H}^{t}$. One can then show that the entropy of the optimal action
$\textup{H}(A^{\star})$ upper bounds this sum of conditional mutual
information $\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})$ to obtain the
desired results. The assumption that the outcome $Y_{t}$ is perfectly revealed
upon observing $Y_{t,a}$ for any $a\in\mathcal{A}$ averts an extra use of the
Cauchy-Schwartz inequality and thus allows to avoid an explicit dependence on
the the number of actions through the multiplicative constant
$\sqrt{|\mathcal{A}|}$. The full proof can be found in Appendix B-B. ∎

##  VII Conclusion

In this paper, building on the results from [1], we introduce a framework to
study the Bayesian cumulative reward and the minimum Bayesian regret for
reinforcement learning problems in the form of Markov decision process. The
latter, is an algorithm-independent quantity and reflects the difficulty of
the reinforcement learning problem. We prove a data processing inequality for
the Bayesian cumulative reward and present upper bounds on the minimum
Bayesian regret using the Wasserstein distance and the relative entropy. We
leverage these results to the particular cases of the multi-armed bandit and
the online optimization with partial feedback problems. For this last problem,
our bound can be relaxed to recover from below the results presented in [2].

## References

  * [1] A. Xu and M. Ragniksy, “Minimum excess risk in bayesian learning,” _arXiv preprint arXiv:2012.14868_ , 2020.
  * [2] D. Russo and B. Van Roy, “An information-theoretic analysis of thompson sampling,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 2442–2471, 2016.
  * [3] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” _Advances in neural information processing systems_ , vol. 12, 1999.
  * [4] D. P. Bertsekas and J. N. Tsitsiklis, _Neuro-dynamic programming_. Athena Scientific, 1996.
  * [5] M. Ghavamzadeh, S. Mannor, J. Pineau, A. Tamar _et al._ , “Bayesian reinforcement learning: A survey,” _Foundations and Trends® in Machine Learning_ , vol. 8, no. 5-6, pp. 359–483, 2015\.
  * [6] C. Villani, _Optimal transport: old and new_. Springer, 2009, vol. 338.
  * [7] O. Kallenberg, _Probabilistic symmetries and invariance principles_ , 2nd ed. Springer, 2002.
  * [8] A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” _arXiv preprint arXiv:1705.07809_ , 2017\.
  * [9] B. Rodríguez Gálvez, G. Bassi, R. Thobaben, and M. Skoglund, “Tighter expected generalization error bounds via wasserstein distance,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [10] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3-4, pp. 285–294, 1933.
  * [11] S. L. Scott, “A modern bayesian look at the multi-armed bandit,” _Applied Stochastic Models in Business and Industry_ , vol. 26, no. 6, pp. 639–658, 2010.
  * [12] O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * [13] B. C. May, N. Korda, A. Lee, and D. S. Leslie, “Optimistic bayesian sampling in contextual-bandit problems,” _Journal of Machine Learning Research_ , vol. 13, pp. 2069–2106, 2012.
  * [14] I. Osband, D. Russo, and B. Van Roy, “(more) efficient reinforcement learning via posterior sampling,” _Advances in Neural Information Processing Systems_ , vol. 26, 2013.
  * [15] H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon, “An information-theoretic view of generalization via wasserstein distance,” in _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 577–581.
  * [16] R. M. Gray, _Entropy and information theory_. Springer Science & Business Media, 2011.
  * [17] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” in _The collected works of Wassily Hoeffding_. Springer, 1994, pp. 409–426.
  * [18] Y. Polyanskiy and Y. Wu, “Lecture notes on Information Theory,” _MIT (6.441), UIUC (ECE 563), Yale (STAT 664)_ , 2017.
  * [19] J. Bretagnolle and C. Huber, “Estimation des densités: risque minimax,” in _Séminaire de Probabilités XII_. Springer, 1978, pp. 342–363.

##  Appendix A Lemmas and extra remarks

See 1

###### Proof.

The proof starts by writing explicitly the inequality to be proven, namely

$R_{\Phi}(\kappa_{U})=\sup_{\\{\varphi_{t}\\}_{t=1}^{T}}\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t},\varphi_{t}(S_{t},U^{t})\big{)}\bigg{]}\geq\sup_{\\{\psi_{t}\\}_{t=1}^{T}}\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t}^{\prime},\psi_{t}(S_{t}^{\prime},V_{t})\big{)}\bigg{]}=R_{\Phi}(\kappa_{U},\kappa_{V|U}),$

where $Y_{t}$ and $S_{t}$ are the outcomes and states obtained from the
actions derived from $\varphi_{t}$, the kernels that describe the MDP $\Phi$,
and $\kappa_{U}$; where $Y_{t}^{\prime}$, $S_{t}^{\prime}$, and $V_{t}$ are
the outcomes, the states, and processed knowledge obtained from the actions
derived from $\psi_{t}$ and the kernels that describe the MDP $\Phi$, and
$\kappa_{U}$ and $\kappa_{V|U}$.

Now, the proof follows by iteratively employing [7, Lemma 3.22] in a similar
fashion to [1, Lemma 1]. To start, consider the kernel $\kappa_{V|U,1}$ from
$\mathcal{U}$ to $\mathcal{V}$, which are assumed to be Borel spaces. Then,
there exists a measurable function
$f_{1}:\mathcal{U}\times[0,1]\to\mathcal{V}$ such that if
$\Xi\sim\textnormal{Uniform}[0,1]$ then $f(u,\Xi)\sim\kappa_{V|U,1}(\cdot,u)$
for all $u\in\mathcal{U}$ [7, Lemma 3.22]. Then,

$\displaystyle R_{\Phi}(\kappa_{U})$
$\displaystyle=\sup_{\\{\varphi_{t}\\}_{t=1}^{T}}\mathbb{E}\bigg{[}r\big{(}Y_{1}^{\prime},\varphi_{1}(S_{1}^{\prime},U^{1}))+\sum_{t=2}^{T}r\big{(}Y_{t},\varphi_{t}(S_{t},U^{t})\big{)}\bigg{]}$
(4)
$\displaystyle\geq\sup_{\psi_{1},\\{\varphi_{t}\\}_{t=2}^{T}}\sup_{\xi_{1}\in[0,1]}\mathbb{E}\bigg{[}r\big{(}Y_{1}^{\prime},\psi_{1}(S_{1}^{\prime},f_{1}(U^{1},\xi)))+\sum_{t=2}^{T}r\big{(}\bar{Y}_{t},\varphi_{t}(\bar{S}_{t},\bar{U}^{t})\big{)}\bigg{]}$
(5)
$\displaystyle\geq\sup_{\psi_{1},\\{\varphi_{t}\\}_{t=2}^{T}}\mathbb{E}\bigg{[}r\big{(}Y_{1}^{\prime},\psi_{1}(S_{1}^{\prime},f_{1}(U^{1},\Xi)))+\sum_{t=2}^{T}r\big{(}\tilde{Y}_{t},\varphi_{t}(\tilde{S}_{t},\tilde{U}^{t})\big{)}\bigg{]}$
(6)
$\displaystyle=\sup_{\psi_{1},\\{\varphi_{t}\\}_{t=2}^{T}}\mathbb{E}\bigg{[}r\big{(}Y_{1}^{\prime},\psi_{1}(S_{1}^{\prime},V_{1}))+r\big{(}Y_{2}^{\prime},\varphi_{2}(S_{2}^{\prime},{U^{\prime}}^{2}))+\sum_{t=3}^{T}r\big{(}\tilde{Y}_{t},\varphi_{t}(\tilde{S}_{t},\tilde{U}^{t})\big{)}\bigg{]},$
(7)

where (4) follows since neither $S_{1}$ and $Y_{1}$ nor $S_{1}^{\prime}$ and
$Y_{1}^{\prime}$ depend on the actions derived from $\varphi$ or $\psi$, and
therefore $S_{1},S_{1}^{\prime}\sim\mathbb{P}_{S|\Theta}$ and
$Y_{1},Y_{1}^{\prime}\sim\mathbb{P}_{Y_{1}|S_{1},\Theta}$. Then, (5) follows
since the supremum of functions
$\varphi_{1}:\mathcal{S}\times\mathcal{U}\to\mathcal{A}$ is restricted to the
functions $\sup_{\psi}\sup_{\xi}\psi(\cdot,f_{1}(\cdot,\xi))$, and where
$\bar{Y}_{t}$, $\bar{S}_{t}$, and $\bar{U}$ denote the outcomes, states, and
knowledge obtained from the actions derived from $\psi_{1}$ and $\varphi_{t}$
for $t\geq 2$, the kernels that describe the MDP $\Phi$, and $\kappa_{U}$.
After that, (6) holds since $\Xi$ is independent of all random objects and
$\sup_{x}f(x)\geq\mathbb{E}[f(X)]$. Here, $\tilde{Y}_{t}$, $\tilde{S}_{t}$,
and $\tilde{U}^{t}$ denote the outcomes and states obtained from the actions
derived from $\psi_{1}$ and $\varphi_{t}$ for $t\geq 2$, the kernels that
describe the MDP $\Phi$, and $\kappa_{U}$. Finally, in (7) it is used that
$V_{1}=f(U^{1},\Xi)$ and therefore that $S_{2}^{\prime}=\tilde{S}_{2}$ and
$Y_{2}^{\prime}=\tilde{Y}_{2}^{\prime}$. Similarly, ${U^{\prime}}^{2}$ is the
knowledge obtained from $\psi_{1}$, the kernels that describe the MDP $\Phi$,
and $\kappa_{U}$ and $\kappa_{V|U,1}$.

Repeating the technique above focusing on
$r(Y_{2}^{\prime},\varphi_{2}(S_{2}^{\prime},{U^{\prime}}^{2}))$ and using [7,
Lemma 3.22] with the kernel $\kappa_{V|U,2}$ from $\mathcal{U}^{2}$ to
$\mathcal{V}$ one obtains that

$\displaystyle
R_{\Psi}(\kappa_{U})\geq\sup_{\\{\psi_{t}\\}_{t=1}^{2},\\{\varphi_{t}\\}_{t=3}^{T}}\mathbb{E}\bigg{[}\sum_{t=1}^{2}r\big{(}Y_{t}^{\prime},\psi_{1}(S_{t}^{\prime},V_{t}))+r\big{(}Y_{3}^{\prime},\varphi_{3}(S_{3}^{\prime},{U^{\prime}}^{3}))+\sum_{t=4}^{T}r\big{(}\tilde{Y}_{t},\varphi_{t}(\tilde{S}_{t},\tilde{U}^{t})\big{)}\bigg{]},$
(8)

where the notation is abused and $\tilde{Y}_{t}$ and $\tilde{S}_{t}$ denote
the outcomes and states obtained from the actions derived from $\psi_{1}$,
$\psi_{2}$, and $\varphi_{t}$ for $t\geq 3$, the kernels that describe the MDP
$\Phi$, and $\kappa_{U}$ and $\kappa_{V|U,1}$ for $t<3$. Also as before,
${U^{\prime}}^{3}$ is the knowledge obtained from $\psi_{t}$ for $t<3$, the
kernels that describe the MDP $\Phi$, and $\kappa_{U}$ and $\kappa_{V|U,t}$
for $t<3$.

Finally, iterating this technique results in

$R_{\Phi}(\kappa_{U})\geq\sup_{\\{\psi_{t}\\}_{t=1}^{T}}\mathbb{E}\bigg{[}\sum_{t=1}^{T}r\big{(}Y_{t}^{\prime},\psi_{t}(S_{t}^{\prime},V_{t})\big{)}\bigg{]}=R_{\Phi}(\kappa_{U},\kappa_{V|U})$
(9)

and completes the proof. ∎

######  Remark 6.

In the proof, $\psi_{1}$ may be different in both (7) and (8), since the
supremum may vary. However, $Y_{2}^{\prime}$, $S_{2}^{\prime}$, and
${U^{\prime}}^{2}$ still represent the outcome, the state, and the knowledge
obtained from the action derived from $\psi_{1}$, the kernels that describe
the MDP, and $\kappa_{U}$ and $\kappa_{V|U,1}$. The same is true for all
$Y_{t}^{\prime}$, $S_{t}^{\prime}$, and ${U^{\prime}}^{t}$ along the proof,
ensuring that the random objects in (9) are distributed as in the definition
of $R_{\Phi}(\kappa_{U},\kappa_{V|U})$.

##  Appendix B Upper bounds for static MDPs for sub-Gaussian and Lipschitz
losses

###  B-A Multi-armed bandit problems

######  Proposition 5.

If for all $t=1,\ldots,T$, the random reward $r(Y,A^{\star})$ is
$\sigma_{t}^{2}$-sub-Gaussian under
$\mathbb{P}_{Y_{t}|\hat{H}^{t}=\hat{h}^{t}}$ for all $\theta\in\mathcal{O}$
and all $\hat{h}^{t}\in\mathcal{H}^{t}$, then for any static MDP $\Pi$,

$\displaystyle\textnormal{MBR}_{\Pi}$
$\displaystyle\leq\sum_{t=1}^{T}\sqrt{2\sigma_{t}^{2}\textup{I}(Y_{t};A^{\star}|\hat{H}^{t})}.$

###### Proof.

The proof starts from applying Donsker-Varadhan’s inequality [16, Theorem
5.2.1] to (2) using Remark 4 in the same way as [2, 8]. The last inequality is
obtained using Jensen’s inequality and identifying the conditional mutual
information between the outcome $Y_{t}$ and the optimal action $A^{\star}$
given the history $\hat{H}^{t}$. Namely,

$\displaystyle\textnormal{MBR}_{\Pi}\leq\sum_{t=1}^{T}\mathbb{E}\Big{[}\mathbb{E}\big{[}r(Y_{t},A^{\star})-r(Y_{t},\hat{A}_{t})\big{]}|A^{\star},\hat{A}_{t},\hat{H}^{t}\Big{]}\leq\sum_{t=1}^{T}\mathbb{E}\Big{[}\sqrt{2\sigma^{2}_{t}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t}|A^{\star},\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t}|\hat{H}^{t}}))}\Big{]}\leq\sum_{t=1}^{T}\sqrt{2\sigma_{t}^{2}\textup{I}(Y_{t};A^{\star}|\hat{H}^{t})}.$

∎

######  Proposition 6.

Suppose that $\mathcal{Y}$ is a metric space with metric $\rho$. If the reward
function $r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$ is $L$-Lipschitz in
$\mathcal{Y}$ under the metric $\rho$, then

$\textnormal{MBR}_{\Pi}\leq
L\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t}|A^{\star}},\mathbb{P}_{Y_{t}|\hat{H}^{t}})\big{]}.$

###### Proof.

The proof follows from applying Kantorovich–Rubinstein duality [6, Remark 6.5]
to (2) using Remark 4 analogously to [9, 15]. ∎

###  B-B Online optimization with partial feedback problems

######  Proposition 7.

If for all $t=1,\ldots,T$, the random reward $r(Y,a^{\star})$ is
$\sigma_{t}^{2}$-sub-Gaussian under $\mathbb{P}_{Y|\hat{H}^{t}=\hat{h}^{t}}$
for all $a^{\star}\in\mathcal{A}$ and all $\hat{h}^{t}\in\mathcal{H}^{t}$,
then for any _online optimization problem with partial feedback_ $\Pi$,

$\displaystyle\textnormal{MBR}_{\Pi}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\Big{[}\sqrt{2\sigma_{t}^{2}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,A^{\star}}|\Theta}\>\|\>\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})}\Big{]}$

###### Proof.

The proof follows from applying Donsker-Varadhan’s inequality [16, Theorem
5.2.1] to (3) using Remark 5 in a similar fashion to [2, 8]. ∎

######  Proposition 8.

Suppose that $\mathcal{Y}$ is a metric space with metric $\rho$. If the reward
function $r:\mathcal{Y}\times\mathcal{A}\to\mathbb{R}$ is $L$-Lipschitz in
$\mathcal{Y}$ under the metric $\rho$, then for any _online optimization
problem with partial feedback_ $\Pi$

$\textnormal{MBR}_{\Pi}\leq
L\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}.$

###### Proof.

The proof follows from applying Kantorovich–Rubinstein duality [6, Remark 6.5]
to (3) using Remark 5 analogously to [9, 15]. ∎

######  Remark 7.

One can show that the entropy of the optimal action $\textup{H}(A^{\star})$
upper bounds the sum of conditional mutual information between the optimal
action $A^{\star}$ and the “per-action outcome” $Y_{t,A_{t}}$ given the
history $\hat{H}^{t}$. This result is obtained in the same way as in [2]
through the following chain of inequalities,

$\displaystyle\sum_{t=1}^{T}\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\sum_{t=1}^{T}\textup{I}(A^{\star};(Y_{t,A_{t}},A_{t})|\hat{H}^{t})\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\textup{I}(A^{\star};\\{Y_{t,A_{t}},A_{t}\\}_{t=1}^{T})\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\textup{H}(A^{\star})$

where (a) follows from [18, Theorem 2.3.5], equality (b) is given by the chain
rule and (c) is obtained from [18, Theorem 2.4.4].

See 5

###### Proof.

Under the assumption that the outcome $Y_{t}$ is perfectly revealed upon
observing $Y_{t,a}$ for any $a\in\mathcal{A}$, one can show the following
chain of inequalities:

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\bigg{[}\sqrt{\frac{1}{2}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,A_{t}}|A^{\star},\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,A_{t}}|\hat{H}^{t}})}\bigg{]}$
(10)
$\displaystyle\leq\sum_{t=1}^{T}\sqrt{\frac{1}{2}\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})}$
(11)
$\displaystyle\leq\sqrt{\frac{1}{2}T\sum_{t=1}^{T}\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})}$
(12) $\displaystyle\leq\sqrt{\frac{1}{2}T\textup{H}(A^{\star})}$

where (10) is obtained using the same arguments as in Remark 3 and, as $Y_{t}$
is perfectly revealed from observing $Y_{t,a}$ for any $a\in\mathcal{A}$, we
have that
$D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,a}|A^{\star},\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,a}|\hat{H}^{t}})=D_{\textnormal{KL}}(\mathbb{P}_{Y_{t}|A^{\star},\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t}|\hat{H}^{t}})$
. Then Jensen’s inequality leads to (11) and Cauchy-Schwartz inequality to
(12). Finally, applying Remark 7 yields the desired result.

When no information structure is assumed among the outcome
$Y_{t}\equiv\\{Y_{t,a}\\}$ for all $a\in\mathcal{A}$, inspired by the
arguments used to prove [2, Proposition 3], one can show a looser inequality,
through a chain of inequalities :

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\big{[}\mathbb{W}(\mathbb{P}_{Y_{t,A^{\star}}|A^{\star},\hat{H}^{t}},\mathbb{P}_{Y_{t,A^{\star}}|\hat{H}^{t}})\big{]}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\Bigg{[}\sum_{a\in\mathcal{A}}\mathbb{P}(A^{\star}=a|\hat{H}^{t})\sqrt{\frac{1}{2}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,a}|A^{\star}=a,\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,a}|\hat{H}^{t}})}\Bigg{]}$
(13)
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\Bigg{[}\sqrt{\frac{1}{2}|\mathcal{A}|\sum_{a\in\mathcal{A}}\mathbb{P}(A^{\star}=a|\hat{H}^{t})^{2}D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,a}|A^{\star}=a,\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,a}|\hat{H}^{t}})}\Bigg{]}$
(14)
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}\Bigg{[}\sqrt{\frac{1}{2}|\mathcal{A}|\sum_{a,b\in\mathcal{A}}\mathbb{P}(A^{\star}=a|\hat{H}^{t})\mathbb{P}(A^{\star}=b|\hat{H}^{t})D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,a}|A^{\star}=b,\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,a}|\hat{H}^{t}})}\Bigg{]}$
(15)
$\displaystyle\leq\sum_{t=1}^{T}\sqrt{\frac{1}{2}|\mathcal{A}|\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})}$
(16)
$\displaystyle\leq\sqrt{\frac{1}{2}|\mathcal{A}|T\sum_{t=1}^{T}\textup{I}(A^{\star};Y_{t,A_{t}}|\hat{H}^{t})}$
(17) $\displaystyle\leq\sqrt{\frac{1}{2}|\mathcal{A}|T\textup{H}(A^{\star})}$

where (13) follows from Remark 3, (14) is obtained using Cauchy-Schwartz
inequality, and (15) by adding the non-negative extra terms
$\frac{1}{2}|\mathcal{A}|\sum_{a\in\mathcal{A}}\mathbb{P}(A^{\star}=a|\hat{H}^{t})\sum_{b\in\mathcal{A}\setminus
a}\mathbb{P}(A^{\star}=b|\hat{H}^{t})D_{\textnormal{KL}}(\mathbb{P}_{Y_{t,a}|A^{\star}=b,\hat{H}^{t}}\>\|\>\mathbb{P}_{Y_{t,a}|\hat{H}^{t}})$
in the square root in (14). Then, (16) follows from using Jensen’s inequality
and identifying the conditional mutual information between the optimal action
$A^{\star}$ and the “per-action outcome” $Y_{t,A_{t}}$ given the history
$\hat{H}^{t}$. Lastly, Cauchy-Schwartz inequality leads to (17) and Remark 7
gives the claimed result.

∎