# On Universal Portfolios with Continuous Side Information

Alankrita Bhatt∗
UC San Diego
<EMAIL_ADDRESS>J. Jon Ryu
UC San Diego
<EMAIL_ADDRESS>Both authors contributed equally to this work. Young-Han
Kim
UC San Diego/Gauss Labs Inc.
<EMAIL_ADDRESS>
###### Abstract

A new portfolio selection strategy that adapts to a continuous side-
information sequence is presented, with a universal wealth guarantee against a
class of state-constant rebalanced portfolios with respect to a state function
that maps each side-information symbol to a finite set of states. In
particular, given that a state function belongs to a collection of functions
of finite Natarajan dimension, the proposed strategy is shown to achieve,
asymptotically to first order in the exponent, the same wealth as the best
state-constant rebalanced portfolio with respect to the best state function,
chosen in hindsight from observed market. This result can be viewed as an
extension of the seminal work of Cover and Ordentlich (1996) that assumes a
single state function.

##  1 Introduction

We study the classical problem of portfolio selection, formally defined as
follows. Suppose that there exist $m\geq 2$ stocks in a stock market and let
${\mathbf{x}}_{t}=(x_{t1},\ldots,x_{tm})\in\mathbb{R}_{\geq 0}$ denote a
market vector at time $t$, which encodes the _price relatives_ of stocks on
that day. That is, for each stock $i\in[m]\mathrel{\mathop{\mathchar 58\relax
missing}}=\\{1,\ldots,m\\}$, $x_{ti}\geq 0$ is the ratio of the end price to
the start price on day $t$. Concretely, an investment strategy $a$, at each
day $t$, outputs a nonnegative weight vector
$a(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1})\in\Delta^{m-1}$ over the stocks $[m]$, upon which the investor
distributes her wealth accordingly; hereafter, we use
$\mathcal{B}\mathrel{\mathop{\mathchar 58\relax
missing}}=\Delta^{m-1}\mathrel{\mathop{\mathchar 58\relax
missing}}=\\{(\theta_{1},\ldots,\theta_{m})\in\mathbb{R}_{\geq
0}^{m}\mathchoice{\colon}{\colon}{\mathchar 58\relax\mspace{1.0mu}}{\mathchar
58\relax}\sum_{i=1}^{m}\theta_{i}=1\\}$ to denote the standard $m$-simplex.
That is, the multiplicative wealth gain on day $t$ (i.e., the ratio of wealth
on day $t$ to the wealth on day $t-1$) is
$\sum_{j\in[m]}a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1})x_{tj}$. Thus, her cumulative wealth gain after $n$ days becomes

$\displaystyle S_{n}(a,{\mathbf{x}}^{n})$
$\displaystyle\mathrel{\mathop{\mathchar 58\relax
missing}}=\prod_{t=1}^{n}\sum_{j\in[m]}a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathbf{x}}^{t-1})x_{tj}=\sum_{y^{n}\in[m]^{n}}\Bigl{(}\prod_{t=1}^{n}a(y_{t}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathbf{x}}^{t-1})\Bigr{)}{\mathbf{x}}(y^{n}),$
(1)

where ${\mathbf{x}}(y^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=x_{1y_{1}}\cdots x_{ny_{n}}$ denotes the wealth gain of an extreme
investment strategy that puts all money to the stock $y_{t}$ on day $t$, and
the second equality follows from the distributive law.

An investor’s goal is to design an investment strategy that maximizes her
cumulative wealth $S_{n}(a,{\bf x}^{n})$. For a stock market where ${\bf
x}^{n}$ are i.i.d. , it is known that the log-optimal portfolio
$\bm{\theta}^{\star}$ that maximizes
$\operatorname{\mathsf{E}}[\log\bm{\theta}^{T}{\bf X}]$ is asymptotically and
competitively optimal. A similar result is well-established for stationary
ergodic markets, see, e.g., (Cover and Thomas, 2006, Chapter 16). The log-
optimal portfolio theory with stochastic market assumptions, however, is
unrealistic, as modeling a stock market could be harder than predicting the
market.

As a more realistic alternative, Cover (1991) presented _universal portfolios_
that asymptotically achieve the best wealth, to first order in the exponent,
attained by a certain class of reference portfolios, with _no statistical
assumptions_ on the stock market. For the reference class, Cover considered a
class of constant rebalanced portfolios (CRPs), where a CRP parameterized by a
weight vector $\bm{\theta}\in\mathcal{B}$ is defined to redistribute its
wealth according to $\bm{\theta}$ on every day. Note that CRPs are optimal in
an i.i.d. stock market when the distribution is known.

Later, Cover and Ordentlich (1996) extended the theory to a setup where a
discrete side information sequence is causally available to an investor; in
practice, the side information sequence can be thought to encode an external
information that may help predict the stock market. They proposed a variation
of Cover’s universal portfolios that asymptotically achieves the best wealth
attained by a class of _state-wise_ CRPs that may play different weight
vectors according to the side information.

Taking one step further, in this paper, we consider a more challenging
scenario in which a side information sequence $z^{n}\in\mathcal{Z}^{n}$ is
continuous-valued, which could even be the (truncated) market history itself.
A reference portfolio we aim to compete with is parameterized by a state-wise
CRP and a _state function_ $g\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar 58\relax}\mathcal{Z}\to[S]$ for some $S\geq
2$ and plays the state-wise CRP according to the state sequence
$g(z^{n})\mathrel{\mathop{\mathchar 58\relax missing}}=g(z_{1})\ldots
g(z_{n})$, where we assume a class of state functions $\mathcal{G}$ from which
$g$ is drawn; note that larger the $\mathcal{G}$, the richer the reference
class. This flexibility in the class $\mathcal{G}$ and the choice of
continuous side information sequence may hugely enlarge the capacity of the
competitor class since it can capture a variety of investment strategies. As a
simple example, consider a portfolio strategy that selects the state based on
whether the price relative of the first stock yesterday ${\bf
x}_{t,1}\geq\beta$ or not for a (variable) threshold $\beta$. This falls into
this enlarged class with $z_{t}={\bf x}_{t-1}$.

As the main result, we propose a new investment strategy that asymptotically
achieves the same wealth attained by the best state-constant rebalanced
portfolios with a state function drawn from a class of functions of finite
Natarajan dimension, under a mild regularity condition on the stochasticity of
the side information sequence $Z^{n}$. The proposed strategy is based on a
generalization of a universal probability assignment scheme recently proposed
by Bhatt and Kim (2021). Note that we assume no transaction costs and that the
investor’s actions do not affect the market.

The rest of the paper is organized as follows. In Section 2, we review
universal portfolios without and with discrete side information, highlighting
the connection between universal compression (or probability assignment) and
universal portfolios. Section 3 described the proposed algorithm and a crude
approximation algorithm for its simulation, together with some concrete
examples of side information sequence. We present the proof of the main
theorem in Section 4. We conclude with discussing related work in Section 5.
All deferred proofs can be found in the Appendix.

##  2 A Review of Universal Portfolio Theory

###  2.1 Universal Portfolios

In his seminal work, Cover (1991) set an ambitious goal that aims to design an
investment strategy $b$ to compete with the best strategy in a class
$\mathcal{A}$ of investment strategies for any stock market ${\bf x}^{n}$, in
the sense that it minimizes the worst-case regret

$\mathsf{Reg}^{\mathsf{port}}_{n}(b,\mathcal{A})\mathrel{\mathop{\mathchar
58\relax missing}}=\sup_{{\bf
x}^{n}}\sup_{a\in\mathcal{A}}\log\frac{S_{n}(a,{\bf x}^{n})}{S_{n}(b,{\bf
x}^{n})}.$

We call a portfolio $b$ _universal with respect to $\mathcal{A}$_ if
$\mathsf{Reg}^{\mathsf{port}}_{n}(b,\mathcal{A})=o(n)$, i.e., in words, $b$
achieves the same exponential wealth growth rate attained by the best strategy
in $\mathcal{A}$ chosen in hindsight with observed market.

Remarkably, Cover constructed a universal portfolio with respect to the class
of CRPs and established its universality. Cover’s theory is based on the key
observation that competing against CRPs in portfolio optimization is
equivalent to competing against i.i.d. Bernoulli models in log-loss prediction
problem. In what follows, we describe this relationship in a general form
beyond between i.i.d. probabilities and CRPs.

For any sequential probability assignment scheme
$q(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{t-1})\in\mathcal{B}$
(where $y_{i}\in[m]$) the _probability induced portfolio_ $a=\phi(p)$ is
defined as

$a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1})\mathrel{\mathop{\mathchar 58\relax
missing}}=\frac{\sum_{y^{t-1}\in[m]^{t-1}}p(y^{t-1}j){\bf
x}(y^{t-1})}{\sum_{y^{t-1}\in[m]^{t-1}}p(y^{t-1}){\bf x}(y^{t-1})}.$

Note that if $p$ is an i.i.d. probability, i.e.,
$p(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{t-1})=\bm{\theta}\in\mathcal{B}$,
it is easy to check from the expression (2.1) that the corresponding portfolio
$\phi(p)$ is the CRP parameterized by $\bm{\theta}$; thus the class of CRPs
$\mathcal{A}^{\mathsf{CRP}}$ is $\phi(\mathcal{P}^{\otimes})$, where we use
$\mathcal{P}^{\otimes}$ to denote the class of i.i.d. probabilities.

A peculiar property of a probability induced portfolio $a=\phi(p)$ is that the
daily gain can be written as

$\sum_{y_{t}\in[m]}a(y_{t}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1}){\bf x}_{t}(y_{t})=\frac{\sum_{y^{t}}p(y^{t}){\bf
x}(y^{t})}{\sum_{y^{t-1}}p(y^{t-1}){\bf x}(y^{t-1})},$

and thus by telescoping, the cumulative wealth gain (1) becomes

$\displaystyle S_{n}(\phi(p),{\bf x}^{n})=\sum_{y^{n}\in[m]^{n}}p(y^{n}){\bf
x}(y^{n}).$ (3)

In view of this expression, a probability induced portfolio can be interpreted
as a _fund-of-funds_ , i.e., a mixture of the extremal portfolios with weights
$p(y^{n})$.

As alluded to earlier, there is an intimate connection between the portfolio
optimization with respect to a class of probability induced portfolios and the
corresponding log-loss prediction problem. In the log-loss prediction problem,
given a class of probabilities $\mathcal{P}$, we define the worst-case regret
of a probability $q$ with respect to $\mathcal{P}$ as

$\displaystyle\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P})=\sup_{y^{n}}\sup_{p\in\mathcal{P}}\log\frac{p(y^{n})}{q(y^{n})}$
(4)

and call a probability $q$ _universal_ with respect to $\mathcal{P}$ if
$\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P})=o(n)$. The following
proposition shows that the portfolio optimization with respect to
$\phi(\mathcal{P})$ is no more difficult than the corresponding log-loss
prediction problem with respect to $\mathcal{P}$.

######  Proposition 1.

For any probability $q$ and any class of probability assignments
$\mathcal{P}$, we have

$\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q),\phi(\mathcal{P}))\leq\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P}).$

###### Proof.

We first recall (3) that the cumulative wealth of the probability induced
portfolio $\phi(p)$ is written as
$S_{n}(\phi(p),{\mathbf{x}}^{n})=\sum_{y^{n}}p(y^{n}){\mathbf{x}}(y^{n})$.
Hence, for any probability $q$, we can write

$\displaystyle\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q),\phi(\mathcal{P}))$
$\displaystyle=\sup_{{\bf
x}^{n}}\sup_{p\in\mathcal{P}}\frac{S_{n}(\phi(p),{\mathbf{x}}^{n})}{S_{n}(\phi(q),{\mathbf{x}}^{n})}$
$\displaystyle=\sup_{{\bf
x}^{n}}\sup_{p\in\mathcal{P}}\frac{\sum_{y^{n}}p(y^{n}){\mathbf{x}}(y^{n})}{\sum_{y^{n}}q(y^{n}){\mathbf{x}}(y^{n})}$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(a)}$\hss}}}}{{\leq}}\sup_{p\in\mathcal{P}}\max_{y^{n}}\frac{p(y^{n})}{q(y^{n})}=\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P}),$

where $(a)$ follows by Lemma 2 below. ∎

######  Lemma 2 (Cover and Thomas (2006), Lemma 16.7.1).

Let $a_{1},\ldots,a_{n},b_{1},\ldots,b_{n}$ be nonnegative real numbers. Then,
defining $0/0=0$, we have

$\displaystyle\frac{\sum_{i=1}^{n}a_{i}}{\sum_{i=1}^{n}b_{i}}\leq\max_{j=1,\ldots,n}\frac{a_{j}}{b_{j}}.$

A direct implication of this statement is that if a probability assignment $q$
is universal with respect to $\mathcal{P}$ for the log-loss prediction
problem, then the induced portfolio $\phi(q)$ is universal with respect to
$\phi(\mathcal{P})$. If we consider the class of all i.i.d. probabilities
$\mathcal{P}^{\otimes}$, it is well known that the Laplace probability
assignment $q_{\mathsf{L}}(y^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=\int_{\mathcal{B}}\mu(\bm{\theta})p_{\bm{\theta}}(y^{n})\mathop{}\\!\mathrm{d}\bm{\theta}$
is universal for $\mathcal{P}^{\otimes}$, where $\mu(\bm{\theta})$ is the
uniform density over $\mathcal{B}$ and $p_{\bm{\theta}}(y^{n})$ is the i.i.d.
probability with parameter
$\bm{\theta}=(\theta_{1},\ldots,\theta_{m})\in\mathcal{B}$, i.e.,
$p_{\bm{\theta}}(y^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=\prod_{i=1}^{n}\theta_{y_{n}}=\prod_{j=1}^{m}\theta_{j}^{k_{j}}$
with
$k_{i}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\{t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}y_{t}=i\\}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$.111We
remark that while the Krichevsky–Trofimov (KT) probability assignment
$q_{\mathsf{KT}}$ is universal with an optimal constant in the regret, we
consider $q_{\mathsf{L}}$ for simplicity throughout this paper.  Indeed, we
have:

######  Lemma 3 (Cesa-Bianchi and Lugosi (2006), Chapter 9).

$\sup_{\bm{\theta}\in\mathcal{B}}\sup_{y^{n}\in[m]^{n}}\log\frac{p_{\bm{\theta}}(y^{n})}{q_{\mathsf{L}}(y^{n})}\leq
m\log n.$

Hence, $\phi(q_{\mathsf{L}})$ is a universal portfolio for
$\mathcal{A}^{\mathsf{CRP}}=\phi(\mathcal{P}^{\otimes})$—this is Cover’s
universal portfolio. We remark that the universal portfolio
$\phi(q_{\mathsf{L}})$ can be expressed as

$\phi(q_{\mathsf{L}})(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1})=\frac{\int_{\mathcal{B}}\bm{\theta}S_{t-1}(\bm{\theta},{\bf
x}^{t-1})\mu(\bm{\theta})\mathop{}\\!\mathrm{d}\bm{\theta}}{\int_{\mathcal{B}}S_{t-1}(\bm{\theta},{\bf
x}^{t-1})\mu(\bm{\theta})\mathop{}\\!\mathrm{d}\bm{\theta}},$

and is thus also known as the $\mu$-weighted portfolio.

###  2.2 Universal Portfolios with Discrete Side Information

Let us now consider a scenario at each time $t$, the investor is additionally
given a discrete side information $w_{t}\in[S]$ for some $S\geq 1$ and chooses
a portfolio $a(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1};w^{t})\in\mathcal{B}$, as considered by Cover and Ordentlich (1996).
Since the investor’s multiplicative wealth gain is
$\sum_{y\in[m]}a(y\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1};w^{t}){\bf x}_{t}(y)$, similar to the no-side-information setting,
the cumulative wealth factor is

$\displaystyle S_{n}(a,{\mathbf{x}}^{n};w^{n})$
$\displaystyle\mathrel{\mathop{\mathchar 58\relax
missing}}=\prod_{t=1}^{n}\sum_{j\in[m]}a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathbf{x}}^{t-1};w^{t})x_{tj}$
(5)

and we define the worst-case regret as

$\mathsf{Reg}^{\mathsf{port}}_{n}(b,\mathcal{A};w^{n})\mathrel{\mathop{\mathchar
58\relax missing}}=\sup_{a\in\mathcal{A}}\sup_{{\bf
x}^{n}}\log\frac{S_{n}(a,{\bf x}^{n};w^{n})}{S_{n}(b,{\bf x}^{n};w^{n})}$

for a class $\mathcal{A}$ of portfolios that also adapt to $w^{n}$.
Concretely, as a natural extension of CRPs, we consider a class of state-
constant rebalanced portfolios (state-CRPs), denoted as
$\mathcal{A}_{S}^{\mathsf{CRP}}$, where a state-CRP parameterized by a
$S$-tuple $(\bm{\theta}_{1},\ldots,\bm{\theta}_{S})\in\mathcal{B}^{S}$ plays a
portfolio $\bm{\theta}_{w_{t}}$ at each time $t$.

Paralleling the connection between probability and portfolio in the no-side-
information case, we can also define a probability induced portfolio in this
setting. In the log-loss prediction with a causal side information sequence, a
learner is asked to assign a probability
$p(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{t-1};w^{t})$
over $[m]$ based on the causal information, i.e., past sequence $y^{t-1}$ and
the side information sequence $w^{t}$. Here, we use
$p(y^{n}\|w^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=\prod_{t=1}^{n}p(y_{t}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{t-1};w^{t})$
to denote the joint probability over $y^{n}$ given $w^{n}$. The probability
induced portfolio $a=\phi(p)$ is then defined as

$a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1};w^{t})\mathrel{\mathop{\mathchar 58\relax
missing}}=\frac{\sum_{y^{t-1}}p(y^{t-1}j\|w^{t}){\bf
x}(y^{t-1})}{\sum_{y^{t-1}}p(y^{t-1}\|w^{t-1}){\bf x}(y^{t-1})},$

and as in the no-side information setting, we can write

$S_{n}(\phi(p),{\bf x}^{n};w^{n})=\sum_{y^{n}}p(y^{n}\|w^{n}){\bf x}(y^{n}).$

For example, the class of $S$-state-CRPs $\mathcal{B}_{S}^{\mathsf{CRP}}$ is
induced by the class of all $S$-state i.i.d. probabilities
$\mathcal{P}_{S}^{\otimes}$, i.e.,
$\mathcal{B}_{S}^{\mathsf{CRP}}=\phi(\mathcal{P}_{S}^{\otimes})$. To see this,
note that every $S$-state-CRP parameterized by $\bm{\theta}_{1\mathchar
58\relax S}=(\bm{\theta}_{1},\ldots,\bm{\theta}_{S})$ is the portfolio induced
by the state-wise i.i.d. probability assignment $p_{\bm{\theta}_{1\mathchar
58\relax S}}(y^{n}\|w^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=\prod_{t=1}^{n}p_{\bm{\theta}_{w_{t}}}(y_{t})$.

Moreover, as stated in Proposition 1, solving the log-loss prediction problem
suffices for the probability optimization with side information with respect
to a class of probability induced portfolios.

######  Proposition 4.

For any probability assignment $q$ and any class of probability assignment
schemes $\mathcal{P}$ with side information sequence $w^{n}$, we have
$\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q),\phi(\mathcal{P});w^{n})\leq\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P};w^{n})$,
where we define

$\mathsf{Reg}^{\mathsf{prob}}_{n}(q,\mathcal{P};w^{n})\mathrel{\mathop{\mathchar
58\relax
missing}}=\sup_{p\in\mathcal{P}}\max_{y^{n}}\log\frac{p(y^{n}\|w^{n})}{q(y^{n}\|w^{n})}.$

Note that for the class of $S$-state-wise i.i.d. distributions
$\mathcal{P}_{S}^{\otimes}$, the state-wise extension of the Laplace
probability assignment $q_{\mathsf{L};S}$ that assigns

$\displaystyle q_{\mathsf{L};S}(y^{n}\|w^{n})\mathrel{\mathop{\mathchar
58\relax missing}}=\prod_{s=1}^{S}q_{\mathsf{L}}(y^{n}(s;w^{n})),$ (7)

where $y^{n}(s;w^{n})=(y_{i}\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar 58\relax}w_{i}=s,i\in[n])$, is universal,
and so $\phi(q_{\mathsf{L};S})$ is universal for
$\mathcal{A}_{S}^{\mathsf{CRP}}=\phi(\mathcal{P}_{S}^{\otimes})$—this is Cover
and Ordentlich’s universal portfolio.

##  3 Main Results

###  3.1 Universal Portfolios with Continuous Side Information

We now consider our main setting where a side information sequence
$z^{n}\in\mathcal{Z}^{n}$ is continuous-valued. For example, in this setup,
one may take $z_{t}$ as a suffix of the market history ${\bf x}_{t-k}^{t-1}$
for some $k\geq 1$. As described earlier in the introduction, we aim to design
a universal portfolio that competes against a class of state-CRPs that adapts
to the sequence $g(w^{n})$, where $g$ is a state function
$g\mathchoice{\colon}{\colon}{\mathchar 58\relax\mspace{1.0mu}}{\mathchar
58\relax}\mathcal{Z}\to[S]$ assumed to belong to a class of functions
$\mathcal{G}$. Note that a singleton $\mathcal{G}=\\{g\\}$ recovers the
setting of Cover and Ordentlich (1996). Our goal is to design a portfolio that
is universal for a largest possible $\mathcal{G}$ with a minimal assumption on
the side information sequence. In this paper, we will assume that the
_Natarajan dimension_ (Shalev-Shwartz and Ben-David, 2014) of $\mathcal{G}$,
denoted as $\mathrm{Ndim}(\mathcal{G})$, is finite. The Natarajan dimension
can be seen as a generalization of the classic VC dimension, when the function
class under consideration is not binary.

Leveraging the established connection between probability and portfolio, we
continue to view the class of state-wise CRPs
$\mathcal{B}_{S}^{\mathsf{CRP}}=\phi(\mathcal{P}_{S}^{\otimes})$ as the class
of portfolios induced by $\mathcal{P}_{S}^{\otimes}$ and describe the problem
in an abstract setting. For a class of probability induced portfolios with
(discrete) side information $\mathcal{A}=\phi(\mathcal{P})$ and a class of
state functions $\mathcal{G}$, our goal is to design a strategy $b$ that
achieves a sublinear worst-case regret

$\mathsf{Reg}^{\mathsf{port}}_{n}(b;\mathcal{A},\mathcal{G};{\bf
x}^{n},z^{n})\mathrel{\mathop{\mathchar 58\relax
missing}}=\sup_{g\in\mathcal{G}}\sup_{a\in\mathcal{A}}\log\frac{S(a,{\bf
x}^{n};g(z^{n}))}{S(b,{\bf x}^{n};z^{n})}.$

Similar to the universal portfolios with discrete side information, a
universal portfolio can be readily induced by a universal probability with
respect to a continuous side information sequence with an unknown state
function, based on the following statement.

######  Proposition 5.

For any ${\bf x}^{n}$ and $z^{n}$, we have

$\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q);\phi(\mathcal{P}),\mathcal{G};{\bf
x}^{n},z^{n})\leq\mathsf{Reg}^{\mathsf{prob}}_{n}(q;\mathcal{P},\mathcal{G};z^{n}),$

where

$\mathsf{Reg}^{\mathsf{prob}}_{n}(q;\mathcal{P},\mathcal{G};z^{n})\mathrel{\mathop{\mathchar
58\relax
missing}}=\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}}\max_{y^{n}}\log\frac{p(y^{n}\|g(z^{n}))}{q(y^{n}\|z^{n})}.$

In this work, we specifically plug-in an extended version of the universal
probability assignment $q_{\mathcal{G}}^{*}$ proposed by Bhatt and Kim (2021),
which was designed for $m=2,S=2$ with regret guarantee established when
$y^{n}$ is random and the side information sequence $Z^{n}$ is i.i.d. . We
will extend their scheme for arbitrary $m$ and $S$ with a guarantee for
adversarial $y^{n}$ and non-i.i.d. $Z^{n}$.

Below, we further assume that a side information sequence $Z^{n}$ is
stochastic with distribution $P_{Z^{n}}$ which may be arbitrarily correlated
with the stock market ${\bf X}^{n}$; the universality is established with
respect to the expected worst-case regret

$\overline{\mathsf{Reg}}^{\mathsf{port}}_{n}(b;\mathcal{A},\mathcal{G})\mathrel{\mathop{\mathchar
58\relax
missing}}=\operatorname{\mathsf{E}}\bigl{[}\mathsf{Reg}^{\mathsf{port}}_{n}(b;\mathcal{A},\mathcal{G};{\bf
X}^{n},Z^{n})\bigr{]},$

where the expectation is over a joint distribution ${\mathbf{P}}_{{\bf
X}^{n},Z^{n}}$. We remark that it is unclear whether the required stochastic
assumptions on $Z^{n}$ in Theorem 6 are an artifact of our analysis or whether
they can be completely removed and universality can be established for
individual sequences $z^{n}$. We leave this question for future work; see also
Section 5.

##### Proposed Strategy

Firstly, for any $\tilde{n}\in\mathbb{N}$ and any
${\tilde{z}}^{\tilde{n}}\in\mathcal{Z}^{\tilde{n}}$, let
$\\{{\tilde{g}}_{1},\dotsc,{\tilde{g}}_{\ell}\\}\subset\mathcal{G}$ be a
_minimal empirical covering_ of $\mathcal{G}$ with respect to
${\tilde{z}}^{\tilde{n}}$, i.e., a set of functions such that
$\\{{\tilde{g}}_{i}({\tilde{z}}^{\tilde{n}})\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}i\in[\ell]\\}=\\{g({\tilde{z}}^{\tilde{n}})\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar 58\relax}g\in\mathcal{G}\\}$ with the
minimum possible size $\ell=\ell({\tilde{z}}^{\tilde{n}})$. Then, we define a
mixture probability assignment

$q_{\mathcal{G};{\tilde{z}}^{\tilde{n}}}(y^{i}\|z^{i})\mathrel{\mathop{\mathchar
58\relax
missing}}=\frac{1}{\ell}\sum_{j=1}^{\ell}q_{\mathsf{L};S}(y^{i}\|{\tilde{g}}_{j}(z^{i}))$

with respect to the empirical covering, and define the induced sequential
probability assignment

$q_{\mathcal{G};{\tilde{z}}^{\tilde{n}}}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};z^{i})\mathrel{\mathop{\mathchar
58\relax
missing}}=\frac{q_{\mathcal{G};{\tilde{z}}^{\tilde{n}}}(y^{i}\|z^{i})}{q_{\mathcal{G};{\tilde{z}}^{\tilde{n}}}(y^{i-1}\|z^{i-1})}.$

The proposed probability assignment $q_{\mathcal{G}}^{*}$ is then defined as
follows. First, we split the $n$ time steps into $\lceil\log_{2}n\rceil$
epochs: starting from $j=1$, define the $j$-the epoch to consist of the time
steps $2^{j-1}+1\leq i\leq 2^{j}$. So, the first epoch consists of $z_{2}$,
the second epoch consists of $z_{3}^{4}$, the third epoch consists of
$z_{5}^{8}$ and so on. Then,

  * $\bullet$

For $i=1$,
$q_{\mathcal{G}}^{*}(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}z_{1})\mathrel{\mathop{\mathchar
58\relax missing}}=1/m$;

  * $\bullet$

For $i\geq 2$, if $2^{j-1}+1\leq i\leq 2^{j}$, i.e., if the time step $i$
falls within the $j$-th epoch, then

$\displaystyle
q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};z^{i})\mathrel{\mathop{\mathchar
58\relax
missing}}=\frac{q_{\mathcal{G};z^{2^{j-1}}}(y_{2^{j-1}+1}^{i}\|z_{2^{j-1}+1}^{i})}{q_{\mathcal{G};z^{2^{j-1}}}(y_{2^{j-1}+1}^{i-1}\|z_{2^{j-1}+1}^{i-1})},$

where we define $q_{\mathcal{G};z^{2^{j-1}}}(\emptyset\|\emptyset)=1$ by
convention.

Concretely, the probability assigned over $y^{n}$ given $z^{n}$ for some
$n\in(2^{J-1},2^{J}]$ is

$\displaystyle q_{\mathcal{G}}^{*}(y^{n}\|z^{n})$
$\displaystyle=\prod_{i=1}^{n}q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};z^{i})$
$\displaystyle=q_{\mathcal{G};\emptyset}(y_{1}\|z_{1})q_{\mathcal{G};z_{1}}(y_{2}\|z_{2})q_{\mathcal{G};z^{2}}(y_{3}^{4}\|z_{3}^{4})\cdots
q_{\mathcal{G};z^{2^{J-1}}}(y_{2^{J-1}+1}^{n}\|z_{2^{J-1}+1}^{n}).$ (9)

Finally, we obtain a sequential portfolio $a=\phi(q_{\mathcal{G}}^{*})$ via
the expression (2.2).

While the main focus of this paper is to construct a provably universal
portfolio with continuous side information, we also include a discussion on
its simulation in Appendix C.

###  3.2 Performance Guarantee and Examples

Given a class of $S$-state functions $\mathcal{G}$, we need to impose a
structural condition on the side information sequence $Z^{n}\sim P_{Z^{n}}$ as
a stochastic process. For any binary function class
$\mathcal{H}\subset\\{\mathcal{Z}\to\\{0,1\\}\\}$, we define

$\displaystyle\rho_{\mathcal{H}}(Z^{n})=\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n}\bigl{(}h(Z_{i})-\operatorname{\mathsf{E}}[h(Z_{i})]\bigr{)}\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing},$
(10)

which is a well-studied quantity in the empirical process theory.
Specifically, we are interested in the binary function class
$\mathds{1}_{\\{\mathcal{G}\times\mathcal{G}\\}}\mathrel{\mathop{\mathchar
58\relax missing}}=\\{h\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}\mathcal{Z}\to\\{0,1\\}\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar 58\relax}h(z)=\mathds{1}_{\\{(g(z)\neq
g^{\prime}(z))\\}}\text{ for $g,g^{\prime}\in\mathcal{G}$}\\}$. With a slight
abuse of notation, we use $\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})$ to
denote $\rho_{\mathds{1}_{\\{\mathcal{G}\times\mathcal{G}\\}}}(Z^{n})$.

Now we can state our main result.

######  Theorem 6 (Asymptotic universality).

For any collection of functions $\mathcal{G}$ of finite Natarajan dimension
and any stationary stochastic process $Z^{n}$ such that

$\displaystyle\operatorname{\mathsf{E}}[\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})]=o\Bigl{(}\frac{n}{\log^{2}n}\Bigr{)},$
(11)

the induced portfolio $\phi(q_{\mathcal{G}}^{*})$ satisfies

$\lim_{n\to\infty}\frac{1}{n}\overline{\mathsf{Reg}}^{\mathsf{port}}(\phi(q_{\mathcal{G}}^{*}),\mathcal{A}_{S}^{\mathsf{CRP}},\mathcal{G})=0.$

In Theorem 6, the condition
$\operatorname{\mathsf{E}}[\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})]\ll\frac{n}{\log^{2}n}$
on the marginal distribution $P_{Z^{n}}$ is crucial in ensuring consistency of
the portfolio $\phi(q_{\mathcal{G}}^{*})$. We now provide a few example cases
of side information sequences $Z^{n}$ where this requirement is satisfied.

######  Example 7 (i.i.d. processes).

When the joint distribution $P_{{\bf X}^{n},Z^{n}}$ is such that $Z^{n}$ is
i.i.d. , it is well known that
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]\leq
C\sqrt{\text{VCdim}(\mathcal{H})n}$ (where $C$ is an absolute constant) for
any binary class $\mathcal{H}$ and distribution $P_{Z^{n}}$; see Vershynin
(2018, Theorem 8.3.23). Following the same logic222The only change to be made
in the proof is in the growth function—rather than
$\left(\frac{en}{d}\right)^{d}$, the growth function in this case is
$\leq(S^{2}n)^{2d}$ by Natarajan’s Lemma; see Section 4.1., it can be shown
that
$\operatorname{\mathsf{E}}[\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})]\leq
C\sqrt{(d\log S)n}$ and consequently $\overline{\mathsf{Reg}}^{\mathsf{port}}$
is sublinear; in fact
$\overline{\mathsf{Reg}}^{\mathsf{port}}=\widetilde{O}(\sqrt{n})$.

######  Example 8 ($\beta$-mixing processes).

The quantity $\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]$ has also
been studied for classes beyond i.i.d. sequences—in particular, Yu (1994)
studied the case when $Z^{n}$ is _$\beta$ -mixing_, which we now define. For
the sigma-fields $\sigma_{l}\mathrel{\mathop{\mathchar 58\relax
missing}}=\sigma(Z_{1},\dotsc,Z_{\ell})$ and
$\sigma_{l+k}^{\prime}\mathrel{\mathop{\mathchar 58\relax
missing}}=\sigma(Z_{\ell+k},Z_{\ell+k+1},\dotsc,)$, we define

$\displaystyle\beta_{k}\mathrel{\mathop{\mathchar 58\relax
missing}}=\frac{1}{2}\sup\\{\operatorname{\mathsf{E}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}P(B\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\sigma_{l})-P(B)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}B\in\sigma^{\prime}_{\ell+k},\ell\geq 1\\}$

and if $\beta_{k}=O(k^{-r_{\beta}})$ as $k\to\infty$, $r_{\beta}$ is called
the _$\beta$ -mixing exponent_. Note that a larger $r_{\beta}$ guarantees
faster mixing. We can then restate the main result of Yu (1994) for the case
when $\mathcal{H}$ has a finite VC dimension (Shalev-Shwartz and Ben-David,
2014, Chapter 5).

######  Theorem 9 (Yu, 1994, Corollary 3.2 and Remark (i)).

Assume that a class of binary functions $\mathcal{H}$ is of finite VC
dimension. Let $Z^{n}$ be a stationary $\beta$-mixing sequence with
$\beta$-mixing exponent $r_{\beta}\in(0,1]$. Then, for any given
$s\in(0,r_{\beta})$, we have

$n^{s/(1+s)}\frac{\rho_{\mathcal{H}}(Z^{n})}{n}\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{p}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{p}$\hss}}}}{{\longrightarrow}}0\quad\text{as
$n\to\infty$},$

where $\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{p}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{p}$\hss}}}}{{\longrightarrow}}$ denotes
convergence in probability.

Note that (9) immediately implies that
$\frac{1}{n}\mathsf{Reg}^{\mathsf{port}}\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{p}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{p}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{p}$\hss}}}}{{\longrightarrow}}0$, i.e.,
$\phi(q_{\mathcal{G}}^{*})$ is universal in probability. Converting (9) into a
guarantee for convergence in expectation as required in (11) needs an
additional argument. In particular, we can show that
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]=O(n^{(3+r_{\beta})/(3+2r_{\beta}}))$;
see Appendix A.2 for a detailed proof.

######  Example 10 (Market history $z_{t}={\mathbf{x}}^{t-1}_{t-k}$).

A canonical example of side information is the market history $z_{t}={\bf
x}^{t-1}$ or a truncated version of it with memory size $k$, i.e., $z_{t}={\bf
x}^{t-1}_{t-k}$. In this case, if the stock market $({\bf x}_{t})$ itself is
$k$-th order Markov, then under an additional mild regularity condition, we
can show a faster rate
$\overline{\mathsf{Reg}}^{\mathsf{port}}\leq\widetilde{O}(\sqrt{n})$ than that
implied by the previous example; see Appendix B for the statement.

##  4 Proofs

In this section, we prove Theorem 6. We first note that the probability
assignment $q_{\mathcal{G}}^{*}$ used to derive the proposed portfolio
guarantees the following regret bound.

######  Theorem 11.

For the probability assignment $q_{\mathcal{G}}^{*}$, if the Natarajan
dimension $\mathrm{Ndim}(\mathcal{G})=d$ of $\mathcal{G}$ is finite and
$Z^{n}\sim P_{Z^{n}}$ is stationary, we have333Here, $\log n$ is assumed to be
an integer for simplicity, which can be easily rectified at the cost of an
absolute constant factor in the regret; see Section 4.1.

$\displaystyle\operatorname{\mathsf{E}}\Bigl{[}\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}_{S}^{\otimes}}\sup_{y^{n}\in[m]^{n}}\log\frac{p(y^{n}\|g(Z^{n}))}{q_{\mathcal{G}}^{*}(y^{n}\|Z^{n})}\Bigr{]}\leq
S(d+m)(\log^{2}n)+2.5Sm\sum_{j=0}^{\log
n-1}j\operatorname{\mathsf{E}}[\rho_{\mathcal{G}\times\mathcal{G}}(Z^{2^{j}})].$

We will first prove Theorem 11 and Theorem 6 then follows almost as a
corollary of Theorem 11 via the established connection between a probability
and the induced portfolio in Proposition 5.

###  4.1 Proof of Theorem 11

Note that the key building block of the proposed probability assignment scheme
$q_{\mathcal{G}}^{*}$ is $q_{{\tilde{z}}^{n}}(y^{i}\|z^{i})$ defined in (3.1),
the uniform mixture based on a minimal empirical covering of $\mathcal{G}$
with respect to ${\tilde{z}}^{n}$. The proof consists of three steps. In Step
1, we first consider the simplest case where the whole side information
sequence $z^{n}$ is provided _noncausally_ by an oracle, where we can use
$z^{n}$ as ${\tilde{z}}^{n}$ to build the empirical covering. We then analyze
the performance of $q_{{\tilde{z}}^{n}}(y^{i}\|z^{i})$ for an arbitrary
auxiliary sequence ${\tilde{z}}^{n}$ in Step 2. Finally, in Step 3, we analyze
$q_{\mathcal{G}}^{*}$ based on the analysis of
$q_{{\tilde{z}}^{n}}(y^{i}\|z^{i})$.

#### Step 1. Side Information Given Noncausally

Suppose that $z^{n}$ is available noncausally so that it can be used to
construct a minimal empirical covering in $q_{z^{n}}(y^{i}\|z^{i})$ for
$i\in[n]$. First, note that since
$\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\{(g(z^{n})\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}g\in\mathcal{G}\\}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
S^{n}$, we can construct an empirical covering $\\{g_{1},\ldots,g_{\ell}\\}$
of $\mathcal{G}$ with respect to $z^{n}$ with $\ell\leq S^{n}$. Assuming
Ndim$(\mathcal{G})=d<\infty$, however, we can even do so with
$\ell\leq(S^{2}n)^{d}$ by Natarajan’s Lemma (Shalev-Shwartz and Ben-David,
2014, Lemma 29.4). Hence, for the mixture probability assignment
$q_{{\tilde{z}}^{n}}(y^{i}\|z^{i})$ defined in (3.1) with
${\tilde{z}}^{n}\leftarrow z^{n}$, i.e.,

$q_{z^{n}}(y^{i}\|z^{i})=\frac{1}{\ell}\sum_{j=1}^{\ell}q_{\mathsf{L};S}(y^{i}\|g_{j}(z^{i})),$

it readily follows that for any $g\in\mathcal{G}$,

$\displaystyle\sup_{p\in P_{S}^{\otimes}}\sup_{y^{n}\in[m]^{n}}\log$
$\displaystyle\frac{p(y^{n}\|g(z^{n}))}{q_{z^{n}}(y^{n}\|z^{n})}\leq
d\log(S^{2}n)+Sm\log n$ (13)

by invoking that $\ell\leq(S^{2}n)^{d}$ and applying the regret bound for the
$m$-ary Laplace probability assignment in Lemma 3 for each state.

#### Step 2. Auxiliary Side Information Given Noncausally

We now analyze the mixture probability $q_{{\tilde{z}}^{n}}(y^{n}\|z^{n})$ for
an arbitrary auxiliary sequence ${\tilde{z}}^{n}$, possibly being different
from $z^{n}$. Intuitively, the sequence ${\tilde{z}}^{n}$ will also reduce the
class $\mathcal{G}$ to at most $(S^{2}n)^{d}$ functions, and if $z^{n}$ and
${\tilde{z}}^{n}$ are “not too far apart”, the two reductions each obtained by
$z^{n}$ and ${\tilde{z}}^{n}$ may be also close. The following lemma provides
the performance of the mixture probability $q_{{\tilde{z}}^{n}}(y^{n}\|z^{n})$
with respect to the auxiliary sequence ${\tilde{z}}^{n}$, capturing the
expected gap from the intuition by the Hamming distance (denoted by
$\operatorname{d_{H}}$) between $g(z^{n})$ and ${\tilde{g}}(z^{n})$.

######  Lemma 12.

For any ${\tilde{z}}^{n}$, $z^{n}$, and $g\in\mathcal{G}$ with
$\mathrm{Ndim}(\mathcal{G})=d<\infty$, we have

$\displaystyle\sup_{p\in\mathcal{P}_{S}^{\otimes}}\sup_{y^{n}\in[m]}\log\frac{p(y^{n}\|g(z^{n}))}{q_{{\tilde{z}}^{n}}(y^{n}\|z^{n})}$
$\displaystyle\leq d\log(S^{2}n)+Sm(\log
n)(1+2.5d_{H}(g(z^{n}),{\tilde{g}}(z^{n})))$ $\displaystyle\leq S(\log
n)(d+m+2.5m\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))).$ (14)

Note that setting $\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))=0$
recovers (13) as expected.

###### Proof.

Let $p_{\bm{\theta}_{1\mathchar 58\relax S}}$ be a state-wise i.i.d.
probability assignment characterized by $\bm{\theta}_{1\mathchar 58\relax
S}=(\bm{\theta}_{1},\ldots,\bm{\theta}_{S})\in\mathcal{B}^{S}$, where
$\bm{\theta}_{i}=(\theta_{i1},\theta_{i2},\dotsc,\theta_{im})\in\mathcal{B}$
for each $i\in[S]$. For any state function $g\in\mathcal{G}$, by definition of
the empirical covering, there exists a function
${\tilde{g}}\in\\{{\tilde{g}}_{1},\dotsc,{\tilde{g}}_{\ell}\\}$ such that
${\tilde{g}}({\tilde{z}}^{n})=g({\tilde{z}}^{n})$. Hence, we first have

$\displaystyle\log\frac{p_{\bm{\theta}_{1\mathchar 58\relax
S}}(y^{n}\|g(z^{n}))}{q_{{\tilde{z}}^{n}}(y^{n}\|z^{n})}\leq
d\log(S^{2}n)+\log\frac{p_{\bm{\theta}_{1\mathchar 58\relax
S}}(y^{n}\|g(z^{n}))}{q_{\mathsf{L};S}(y^{n}\|{\tilde{g}}(z^{n}))}.$ (15)

It only remains to analyze $q_{\mathsf{L};S}(y^{n}\|{\tilde{g}}(z^{n}))$. For
each $i\in[S]$ and $j\in[m]$, we define $n_{i}\mathrel{\mathop{\mathchar
58\relax
missing}}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}g(Z_{t})=i\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$ and
$k_{ij}\mathrel{\mathop{\mathchar 58\relax
missing}}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}g(Z_{t})=i,y_{t}=j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$.
Moreover let $\tilde{n}_{i},{\tilde{k}}_{ij}$ be defined in a similar way as
$\tilde{n}_{i}\mathrel{\mathop{\mathchar 58\relax
missing}}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}{\tilde{g}}(Z_{t})=i\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$
and ${\tilde{k}}_{ij}\mathrel{\mathop{\mathchar 58\relax
missing}}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}{\tilde{g}}(Z_{t})=i,y_{t}=j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$).
We can then write

$p_{\bm{\theta}_{1\mathchar 58\relax
S}}(y^{n}\|g(z^{n}))=\prod_{s=1}^{S}\theta_{s1}^{k_{s1}}\dotsc\theta_{sm}^{k_{sm}}.$

Further, we note that we can explicitly write the expression for the Laplace
probability assignment as

$\displaystyle
q_{\mathsf{L}}(y^{n})=\left(\binom{n+m-1}{m-1}\binom{n}{k_{1},\dotsc,k_{m}}\right)^{-1},$

where
$k_{i}=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\{t\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}y_{t}=i\\}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$, and
thus its state-wise extension as

$\displaystyle q_{\mathsf{L};S}(y^{n}\|{\tilde{g}}(z^{n}))$
$\displaystyle=\Bigl{(}\prod_{s=1}^{S}\binom{\tilde{n}_{s}+m-1}{m-1}\binom{\tilde{n}_{s}}{{\tilde{k}}_{s1},\dotsc,{\tilde{k}}_{s,m-1}}\Bigr{)}^{-1}.$

Now, consider

$\displaystyle\log\frac{p_{\bm{\theta}_{1\mathchar 58\relax
S}}(y^{n}\|g(z^{n}))}{q_{\mathsf{L};S}(y^{n}\|{\tilde{g}}({\tilde{z}}^{n}))}$
$\displaystyle=\sum_{i=1}^{S}\log\binom{\tilde{n}_{i}+m-1}{m-1}\binom{\tilde{n}_{i}}{{\tilde{k}}_{i1},\dotsc,{\tilde{k}}_{i,m-1}}\theta_{i1}^{k_{i1}}\dotsc\theta_{im}^{k_{im}}$
$\displaystyle\leq Sm\log
n+\sum_{i=1}^{S}\log\frac{\binom{\tilde{n}_{i}}{{\tilde{k}}_{i1},\dotsc,{\tilde{k}}_{i,m-1}}}{\binom{n_{i}}{k_{i1},\dotsc,k_{i,m-1}}}$
(16) $\displaystyle=Sm\log
n+\sum_{i=1}^{S}\log\frac{\tilde{n}_{i}!}{n_{i}!}+\sum_{i=1}^{S}\sum_{j=1}^{m}\log\frac{k_{ij}!}{{\tilde{k}}_{ij}},$
(17)

where (16) follows since

$\binom{n_{i}}{k_{i1},\dotsc,k_{i,m-1}}\theta_{i1}^{k_{i1}}\dotsc\theta_{im}^{k_{im}}\leq
1.$

Now, since for all $i\in[S]$ and $j\in[m]$, we have
$\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}n_{i}-\tilde{n}_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))$
and
$\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}k_{ij}-{\tilde{k}}_{ij}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))$,
we have that $\tilde{n}_{i}\leq
n_{i}+\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))$ and consequently
$\frac{\tilde{n}_{i}!}{n_{i}!}\leq\frac{(n_{i}+\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n})))!}{n_{i}!}$.
Thus, we can invoke the exact same calculations as in (Bhatt and Kim, 2021,
Propositions 5 and 6) to bound the second and third terms in (17) as

$\displaystyle\log\frac{p_{\bm{\theta}_{1\mathchar 58\relax
S}}(y^{n}\|g(z^{n}))}{q_{\mathsf{L};S}(y^{n}\|{\tilde{g}}({\tilde{z}}^{n}))}$
$\displaystyle\leq Sm\log
n+S(m+3)\operatorname{d_{H}}(g(z^{n}),{\tilde{g}}(z^{n}))\log n$
$\displaystyle\leq Sm(\log n)(1+2.5d_{H}(g(z^{n}),{\tilde{g}}(z^{n}))),$ (18)

since $m\geq 2$. Plugging this into (15) establishes the first bound. The
second bound follows by observing $\log(S^{2}n)\leq S\log n$. ∎

When $Z^{n}$ is stationary as a stochastic process and if ${\tilde{Z}}^{n}$ is
a statistical copy of $Z^{n}$, the following lemma shows that the Hamming
distance can be bounded by $\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})$, which
can be controlled in expectation as $o(n/\log^{2}n)$ under mild regularity
conditions on $P_{Z^{n}}$ and $\mathcal{G}$.

######  Lemma 13.

If $Z^{n}$ is stationary,
${\tilde{Z}}^{n}\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(d)}$\hss}}}}{{=}}Z^{n}$, and
${\tilde{g}}({\tilde{Z}}^{n})={\tilde{g}}({\tilde{Z}}^{n})$, then

$\operatorname{d_{H}}(g(Z^{n}),{\tilde{g}}(Z^{n}))\leq\rho_{\mathcal{G}\times\mathcal{G}}(Z^{n})+\rho_{\mathcal{G}\times\mathcal{G}}({\tilde{Z}}^{n}).$

###### Proof.

Note that for any $Z^{n}$ and ${\tilde{Z}}^{n}$, we can write

$\displaystyle\operatorname{d_{H}}(g(Z^{n}),{\tilde{g}}(Z^{n}))$
$\displaystyle=\operatorname{d_{H}}(g(Z^{n}),{\tilde{g}}(Z^{n}))-\operatorname{d_{H}}(g({\tilde{Z}}^{n}),{\tilde{g}}({\tilde{Z}}^{n}))$
(19)
$\displaystyle\leq\sup_{g_{1},g_{2}}\left\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing\operatorname{d_{H}}(g_{1}(Z^{n}),g_{2}(Z^{n}))-\operatorname{d_{H}}(g_{1}({\tilde{Z}}^{n}),g_{2}({\tilde{Z}}^{n}))\right\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing$
$\displaystyle\leq\sup_{g_{1},g_{2}}\left\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing\operatorname{d_{H}}(g_{1}(Z^{n}),g_{2}(Z^{n}))-n\operatorname{\mathsf{P}}(g_{1}(Z_{1})\neq
g_{2}(Z_{2}))\right\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing$
$\displaystyle\quad+\sup_{g_{1},g_{2}}\left\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing\operatorname{d_{H}}(g_{1}({\tilde{Z}}^{n}),g_{2}({\tilde{Z}}^{n}))-n\operatorname{\mathsf{P}}(g_{1}({\tilde{Z}}_{1})\neq
g_{2}({\tilde{Z}}_{1}))\right\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing$
$\displaystyle=\rho_{\mathcal{G}\times\mathcal{G}}(z^{n})+\rho_{\mathcal{G}\times\mathcal{G}}({\tilde{z}}^{n})$
(20)

where (19) follows since
$\operatorname{d_{H}}(g({\tilde{Z}}^{n}),{\tilde{g}}({\tilde{Z}}^{n}))=0$ by
design and (20) follows since by stationarity of
$Z^{n}\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(d)}$\hss}}}}{{=}}{\tilde{Z}}^{n}$, we have
$n\operatorname{\mathsf{P}}(g_{1}(Z_{1})\neq
g_{2}(Z_{1}))=n\operatorname{\mathsf{P}}(g_{1}({\tilde{Z}}_{1})\neq
g_{2}({\tilde{Z}}_{1}))=\sum_{i=1}^{n}\operatorname{\mathsf{P}}(g_{1}({\tilde{Z}}_{i})\neq
g_{2}({\tilde{Z}}_{i}))=\sum_{i=1}^{n}\operatorname{\mathsf{E}}[\mathds{1}_{\\{g_{1}({\tilde{Z}}_{i})\neq
g_{2}({\tilde{Z}}_{i})\\}}]$. Finally, substituting (20) into (18) yields the
lemma. ∎

#### Step 3. Side Information Given Causally

In view of Lemma 13, provided that $Z^{n}$ is stationary, we can _bootstrap_
the history sequence to construct such an auxiliary sequence, which motivates
the epoch-based construction of $q_{\mathcal{G}}^{*}$. That is, we split the
$n$ time steps into $\log n$ epochs444For simplicity, we assume that $\log n$
is an integer; if not, we may “extend” the horizon of the game from $n$ to
$2^{\lceil\log n\rceil}<2n$, and follow the same analysis incurring at most a
constant factor extra in the regret bound., and define the $j$-the epoch to
consist of the time steps $2^{j-1}+1\leq i\leq 2^{j}$ starting from $j=1$,
while we define
$q_{\mathcal{G}}^{*}(\cdot\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Z_{1})=1/m$
for the 0-th epoch. For $i\geq 2$, if the time step $i$ falls within the
$j$-th epoch, i.e., $2^{j-1}+1\leq i\leq 2^{j}$, then

$\displaystyle
q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};Z^{i})=\frac{q_{Z^{2^{j-1}}}(y_{2^{j-1}+1}^{i}\|Z_{2^{j-1}+1}^{i})}{q_{Z^{2^{j-1}}}(y_{2^{j-1}+1}^{i-1}\|Z_{2^{j-1}+1}^{i-1})}$
(21)

where we can recall the definition of $q_{Z^{2^{j-1}}}$ from (3.1). For any
$p\in\mathcal{P}_{S}^{\otimes}$, we then have

$\displaystyle\sum_{i=1}^{n}\log\frac{p(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}g(Z_{i}))}{q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};Z^{i})}$
$\displaystyle\leq\sum_{i=2}^{n}\log\frac{p(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}g(Z_{i}))}{q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};Z^{i})}+\log
m$ $\displaystyle=\sum_{j=1}^{\log
n}\sum_{i=2^{j-1}+1}^{2^{j}}\log\frac{p(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}g(Z_{i}))}{q_{\mathcal{G}}^{*}(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};Z^{i})}$
$\displaystyle=\sum_{j=1}^{\log
n}\log\frac{p(y_{2^{j-1}+1}^{2^{j}}\|g(Z_{2^{j-1}+1}^{2^{j}}))}{q_{Z^{2^{j-1}}}(y_{2^{j-1}+1}^{2^{j}}\|Z_{2^{j-1}+1}^{2^{j}})}$
(22) $\displaystyle\leq S(d+m)(\log^{2}n)+2.5Sm\sum_{j=0}^{\log
n-1}jd_{H}(g(Z_{1}^{2^{j}}),g(Z_{2^{j}+1}^{2^{j+1}})),$ (23)

where (22) follows by (21) and (23) follows from Lemma 12. Finally, taking
supremum over $y^{n},p$ and $g$ and expectation over $Z^{n}$ leads to the
desired inequality by Lemma 13.∎

###  4.2 Proof of Theorem 6

By Proposition 5 and Theorem 11, we have

$\displaystyle\overline{\mathsf{Reg}}^{\mathsf{port}}(\phi(q_{\mathcal{G}}^{*}),\mathcal{A}_{S}^{\mathsf{CRP}},\mathcal{G})$
$\displaystyle=\operatorname{\mathsf{E}}[\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q_{\mathcal{G}}^{*}),\mathcal{A}_{S}^{\mathsf{CRP}},\mathcal{G};{\bf
X}^{n},Z^{n})]$
$\displaystyle\leq\operatorname{\mathsf{E}}[\mathsf{Reg}^{\mathsf{prob}}_{n}(q;\mathcal{P},\mathcal{G};Z^{n})]$
$\displaystyle=\operatorname{\mathsf{E}}\Bigl{[}\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}}\max_{y^{n}}\log\frac{p(y^{n}\|g(Z^{n}))}{q(y^{n}\|Z^{n})}\Bigr{]}$
$\displaystyle\leq S(d+m)(\log^{2}n)+2.5Sm\sum_{j=0}^{\log
n-1}j\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})],$

where we omit the subscript in $\rho_{\mathcal{G}\times\mathcal{G}}(\cdot)$
for brevity. Since the first term in the bound is sublinear in $n$ when $d$
and $S$ are fixed, it then suffices to show that

$\displaystyle\sum_{j=0}^{\log
n-1}j\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})]=o(n).$ (24)

Using the change of variables $n^{\prime}=\log n$, observe

$\displaystyle\sum_{j=0}^{\log
n-1}j\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})]$
$\displaystyle=\frac{1}{n^{\prime}}\sum_{j=0}^{n^{\prime}-1}j\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})]\frac{n^{\prime}}{2^{n^{\prime}}}\leq\frac{1}{n^{\prime}}\sum_{j=0}^{n^{\prime}-1}\frac{j^{2}}{2^{j}}\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})],$

where the inequality follows since
$\frac{n^{\prime}}{2^{n^{\prime}}}\leq\frac{j}{2^{j}}$ for all $j\leq
n^{\prime}$. Now, since $\frac{(\log
n)^{2}}{n}\operatorname{\mathsf{E}}[\rho(Z^{n})]=\frac{n^{\prime
2}}{2^{n^{\prime}}}\operatorname{\mathsf{E}}[\rho(Z^{2^{n^{\prime}}})]\to 0$
as $n\to\infty$ is assumed, we also have
$\frac{1}{n^{\prime}}\sum_{j=0}^{n^{\prime}-1}\frac{j^{2}}{2^{j}}\operatorname{\mathsf{E}}[\rho(Z^{2^{j}})]\to
0$ as $n^{\prime}\to\infty$, by the Cesàro mean Theorem. A final change of
variables concludes the proof. ∎

##  5 Related Work and Discussion

Portfolio selection has been a closely studied topic in information theory
since the seminal work of Cover (1991) and Cover and Ordentlich (1996), both
of which established close connections between portfolio selection and the
classically studied information theoretic problem of universal compression
(Rissanen, 1996; Ziv and Lempel, 1978; Merhav and Feder, 1998; Xie and Barron,
2000). A number of variations have been considered since, for example
incorporating transaction costs (Blum and Kalai, 1999; Uziel and El-Yaniv,
2020) using other probability assignments than i.i.d. (Kozat et al., 2008;
Tavory and Feder, 2010), and considering space complexity issues (Tavory and
Feder, 2008).

Cross and Barron (2003) and Györfi et al. (2006) proposed portfolio selection
techniques incorporating continuous side information; however, the competitor
classes considered in both are disparate from ours making the problems
different.

As demonstrated, portfolio selection with side information is closely related
to sequential prediction with side information and log-loss. This problem has
attracted recent interest (Rakhlin and Sridharan, 2015; Bilodeau et al., 2020;
Fogel and Feder, 2017; Bhatt and Kim, 2021), with the first two focused on
obtaining fundamental limits via the sequential complexities approach of
Rakhlin et al. (2015). More recently, the preprint of Bilodeau et al. (2021)
proposed a mixture-based conditional density estimator, which specifically
achieves
$\operatorname{\mathsf{E}}[\mathsf{Reg}^{\mathsf{prob}}]=O(\log^{2}n)$ for the
binary probability assignment problem with i.i.d. side information with a VC
class, which tightens the regret $\tilde{O}(\sqrt{n})$ established in (Bhatt
and Kim, 2021). Therefore, it is natural to consider applying the probability
assignment of Bilodeau et al. (2021) in hoping to relax the technical
condition (11). We note, however, that analyzing their method in our setting
of non-i.i.d. side information sequences seems to involve a significant amount
of additional work. More precisely, their analysis needs to be extended to (1)
individual-sequence $y^{n}$ and (2) stationary ergodic side information with a
dependence of the regret on $\rho_{\mathcal{H}}(Z^{n})$ similar to that of the
method of Bhatt and Kim (2021). In their words, we would need to relax the
assumption of the data being _well-specified_.

At a high level, they use a similar covering approach (with respect to the
Hellinger metric over distributions) as well as a _smoothing_ of probabilities
in order to avoid unbounded likelihood ratios (we, in contrast, have used the
Laplace/KT probability assignment). Using a similar epoch-based analysis they
establish regret bounds in (Bilodeau et al., 2021, Appendix D) by first upper
bounding the KL divergence in terms of the Hellinger divergence and then
leveraging local Rademacher complexities in conjunction with an inequality of
Bousquet (2002). In order to extend their method to individual-sequence
$y^{n}$ and stationary ergodic $Z^{n}$, one would need to either extend the
aforementioned inequality to these cases, or to bypass the step of upper-
bounding the KL divergence in terms of the Hellinger divergence altogether. We
leave these directions of extension for future work.

##  Appendix A Deferred Proofs

###  A.1 Proof of Propostions 4 and 5

It suffices to prove Proposition 5, since Proposition 4 follows from it by
taking $z^{n}=w^{n}$ and taking
$\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{G}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=1$
with the function $g\in\mathcal{G}$ being simply $g(z)=z$.

Recall that for a probability assignment
$q(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};z^{i})$, we
have the probability induced portfolio $a=\phi(q)$ defined as

$a(j\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1};z^{t})\mathrel{\mathop{\mathchar 58\relax
missing}}=\frac{\sum_{y^{t-1}}q(y^{t-1}j\|z^{t}){\bf
x}(y^{t-1})}{\sum_{y^{t-1}}q(y^{t-1}\|z^{t-1}){\bf x}(y^{t-1})},$

where recall for
$t\in[n],q(y^{t}\|z^{t})=\prod_{i=1}^{t}q(y_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}y^{i-1};z^{i})$.
We then have

$\sum_{y_{t}\in[m]}a(y_{t}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
x}^{t-1};z^{t}){\bf x}_{t}(y_{t})=\frac{\sum_{y^{t-1}}q(y^{t}\|z^{t}){\bf
x}(y^{t})}{\sum_{y^{t-1}}q(y^{t-1}\|z^{t-1}){\bf x}(y^{t-1})},$

and consequently using a telescoping argument,

$S_{n}(\phi(q),{\bf x}^{n};z^{n})=\sum_{y^{n}\in[m]^{n}}q(y^{n}\|z^{n}){\bf
x}(y^{n}).$

From this we can see that

$\displaystyle\mathsf{Reg}^{\mathsf{port}}_{n}(\phi(q);\phi(\mathcal{P}),\mathcal{G};{\bf
x}^{n},z^{n})$
$\displaystyle=\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}}\log\frac{S_{n}(\phi(p),{\bf
x}^{n};g(z^{n}))}{S_{n}(\phi(q),{\bf x}^{n};z^{n})}$
$\displaystyle=\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}}\log\frac{\sum_{y^{n}\in[m]^{n}}p(y^{n}\|g(z^{n})){\bf
x}(y^{n})}{\sum_{y^{n}\in[m]^{n}}q(y^{n}\|z^{n}){\bf x}(y^{n})}$
$\displaystyle\leq\sup_{g\in\mathcal{G}}\sup_{p\in\mathcal{P}}\max_{y^{n}\in[m]^{n}}\frac{p(y^{n}\|g(z^{n}))}{q(y^{n}\|z^{n})}$
(25)
$\displaystyle=\mathsf{Reg}^{\mathsf{prob}}_{n}(q;\mathcal{P},\mathcal{G};z^{n}),$

where (25) follows from Lemma 2.∎

###  A.2 Proof for
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]=o(\frac{n}{\log n})$ in
Example 8

Let $Z^{n}$ be a $\beta$-mixing process with $\beta$-mixing coefficient
$\beta_{k}$ and $\beta$-mixing exponent $r>0$, i.e., $\beta_{k}=O(k^{-r})$ as
$k\to\infty$. Indeed, under this assumption, we can show a stronger result
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]=O(n^{\frac{3+r}{3+2r}})$
following a similar argument as in Karandikar and Vidyasagar (2002) and
Hanneke and Yang (2019).

Pick $k\geq 1$ which divides $n$ for simplicity; the divisibility can be
easily lifted by elongating the game from $n$ steps to the next number
divisible by $k$. We will choose $k$ as a function of $n$ at the end of proof.
We define the nonoverlapping $k$ subsequences $Z^{(1)},\dotsc,Z^{(k)}$ of
length $n/k$ as

$\displaystyle{Z^{(1)}}_{1}^{n/k}$
$\displaystyle=Z_{1},Z_{k+1},Z_{2k+1}\dotsc,Z_{(n/k-1)+1},$
$\displaystyle{Z^{(2)}}_{1}^{n/k}$
$\displaystyle=Z_{2},Z_{k+2},Z_{2k+2}\dotsc,Z_{(n/k-1)k+2},$
$\displaystyle\vdots$ $\displaystyle{Z^{(k)}}_{1}^{n/k}$
$\displaystyle=Z_{k},Z_{2k},Z_{3k}\dotsc,Z_{(n/k)k}.$

We will invoke the classical result on $\beta$-mixing processes that states
that

$\displaystyle
d_{\mathsf{TV}}\biggl{(}P_{{Z^{(j)}}_{1}^{n/k}},\prod_{i=1}^{n/k}P_{Z^{(j)}_{i}}\biggr{)}\leq\left(\frac{n}{k}-1\right)\beta_{k}$
(26)

for each $j\in[k]$, where $d_{\mathsf{TV}}(\cdot,\cdot)$ denotes the total
variation distance; see, for example, (Hanneke and Yang, 2019, Lemma 1) and
the references therein.

Now, we consider

$\displaystyle\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]$
$\displaystyle=\operatorname{\mathsf{E}}\Bigl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n}(h(Z_{i})-E[h(Z_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\Bigr{]}$
$\displaystyle\leq\operatorname{\mathsf{E}}\biggl{[}\sum_{j=1}^{k}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(j)}_{i})-\operatorname{\mathsf{E}}[h(Z^{(j)}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}$
$\displaystyle=\sum_{j=1}^{k}\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(j)}_{i})-\operatorname{\mathsf{E}}[h(Z^{(j)}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}.$
(27)

Let $Z^{\prime}_{1},\dotsc,Z^{\prime}_{n/k}$ be an i.i.d. process with the
same marginal distribution of the stationary process $Z^{n}$, i.e.,
$P_{Z^{\prime}_{1}}=P_{Z_{1}}$. Continuing from the summand in (27), we then
have

$\displaystyle\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(1)}_{i})-\operatorname{\mathsf{E}}[h(Z^{(1)}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}$
(28)
$\displaystyle=\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(1)}_{i})-h(Z^{\prime}_{i})+h(Z^{\prime}_{i})-\operatorname{\mathsf{E}}[h(Z^{(1)}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}$
$\displaystyle=\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(1)}_{i})-h(Z^{\prime}_{i})+h(Z^{\prime}_{i})-\operatorname{\mathsf{E}}[h(Z^{\prime}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}$
(29)
$\displaystyle\leq\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(1)}_{i})-h(Z^{\prime}_{i}))\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}+\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{\prime}_{i})-E[h(Z^{\prime}_{i})])\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}$
(30)
$\displaystyle\leq\operatorname{\mathsf{E}}\biggl{[}\sup_{h\in\mathcal{H}}\Bigl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{i=1}^{n/k}(h(Z^{(1)}_{i})-h(Z^{\prime}_{i}))\Bigr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\biggr{]}+C\sqrt{\frac{dn}{k}}$
(31)
$\displaystyle\leq\frac{n}{k}\sup_{h\in\mathcal{H}}\operatorname{\mathsf{E}}\Biggl{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\frac{k}{n}\sum_{i=1}^{n/k}h(Z^{(1)}_{i})-\frac{k}{n}\sum_{i=1}^{n/k}h(Z^{\prime}_{i})\Biggr{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}+C\sqrt{\frac{dn}{k}}$
$\displaystyle\leq\frac{n}{k}d_{\mathsf{TV}}\biggl{(}P_{{Z^{(j)}}_{1}^{n/k}},\prod_{i=1}^{n/k}P_{Z^{(j)}_{i}}\biggr{)}+C\sqrt{\frac{dn}{k}}$
(32) $\displaystyle\leq\frac{n^{2}\beta_{k}}{k^{2}}+C\sqrt{\frac{dn}{k}}.$
(33)

Here, (29) follows since the marginal distribution
$Z^{\prime}_{i}\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(d)}$\hss}}}}{{=}}Z^{(1)}_{i}$, (31) follows
since the distribution $Z^{\prime n}$ is i.i.d. and from (Vershynin, 2018,
Theorem 8.3.23), (32) follows from the following variational form of the total
variation distance $d_{\mathsf{TV}}(P,P^{\prime})$ between two measures $P$
and $P^{\prime}$ defined over the same measure space, i.e.,

$d_{\mathsf{TV}}(P,P^{\prime})=\sup_{f\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}f\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
1}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\operatorname{\mathsf{E}}_{X\sim
P}[f(X)]-\operatorname{\mathsf{E}}_{X\sim
P^{\prime}}[f(X)]\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|},$

and lastly (33) follows from (26). Substituting (33) into (27) yields that

$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]\leq\frac{n^{2}\beta_{k}}{k}+C\sqrt{dnk}\leq\frac{C^{\prime}n^{2}k^{-r}}{k}+C\sqrt{dnk}$

for $k$ sufficiently large with some $C^{\prime}>0$, where we use the
definition of the $\beta$-mixing exponent $r$ in the second inequality.
Finally, choosing $k=O(n^{\frac{3}{3+2r}})$ yields the claimed rate
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]=O(n^{\frac{3+r}{3+2r}})$.
∎

##  Appendix B A Detailed Discussion on Example 10

For the side information $z_{t}={\bf x}_{t-k}^{t-1}$ in Example 10, if the
market $({\bf X}_{t})$ itself is $k$-th order Markov, then we can establish
the following guarantee.

######  Lemma 14.

Let ${\bf X}^{n}$ be a stationary $k$-th order Markov process and let
$Z_{t}={\bf X}^{t-1}_{t-k}\in(\mathbb{R}_{+}^{m})^{k}$. Suppose that (1) the
density of $Z_{0}={\bf X}_{-k}^{-1}$ exists and is bounded and supported over
a bounded, convex set $E\subset(\mathbb{R}^{m}_{+})^{k}$ with nonempty
interior and (2) there exist $b>0$ and $\epsilon>0$ such that the time-
invariant conditional density satisfies

$p_{{\bf X}_{t-k+1}^{t}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\bf
X}_{t-k}^{t-1}}(z^{\prime}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}z)\geq
b1_{B(z,\epsilon)}(z^{\prime})$

for any $z\in(\mathbb{R}_{+}^{m})^{k}$, where $B(z,\epsilon)$ denotes the open
ball of radius $\epsilon$ centered at $z\in(\mathbb{R}_{+}^{m})^{k}$ with
respect to Euclidean distance. Then, we have
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}(Z^{n})]=\widetilde{O}(\sqrt{n})$.

###### Proof.

This is a direct consequence of (Bertail and Portier, 2019, Proposition 11),
which establishes an upper bound on
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}({Z^{\prime}}^{n})]$ for a
_Metropolis–Hastings_ (MH) walk ${Z^{\prime}}^{n}$. First, note that $Z^{n}$
forms a Markov chain due to the $k$-th order Markovity of ${\bf X}^{n}$. To
apply the proposition over the Markov chain $Z^{n}$, we set the proposal
distribution $q$ in the MH algorithm to be the actual transition kernel of the
Markov chain ${Z}^{n}$, so that the MH walk becomes the process $Z^{n}$ of our
interest. Then, under the assumptions above, we can apply the result of
Bertail and Portier and conclude that
$\operatorname{\mathsf{E}}[\rho_{\mathcal{H}}({Z}^{n})]=\tilde{O}(\sqrt{n})$
for a VC-class $\mathcal{H}$. ∎

##  Appendix C Simulation Based on Monte Carlo Approximation

The (maybe the only) downside of the universal portfolio algorithms is their
computational complexity. It is not hard to see that the _exact_ computation
of Cover’s universal portfolio requires, on the $T$-th day of investment over
$m$ stocks, $O(T^{m})$ time complexity, and the computation quickly become
infeasible for a long investment period; see (Cover and Ordentlich, 1996) for
a detailed argument. An efficient implementation of universal portfolios is a
decades-old open problem and still remains as an active area of research (Luo
et al., 2018; van Erven et al., 2020). Hence, in this paper, we consider a
Monte Carlo simulation of the universal portfolio algorithms based on the
cumulative wealth expression of a probability induced portfolio (3). While it
is a very crude approximation for large $m$, $S$, or
$\mathrm{Ndim}(\mathcal{G})$, this at least provides a way to demonstrate the
performance of the ideas.

First, note that from (3), the cumulative wealth achieved by Cover’s universal
portfolio $\phi(q_{\mathsf{L}})$ can be written as

$S_{n}(\phi(q_{\mathsf{L}}),{\mathbf{x}}^{n})=\sum_{y^{n}\in[m]^{n}}q_{\mathsf{L}}(y^{n}){\mathbf{x}}(y^{n})=\int_{\mathcal{B}}S_{n}(\bm{\theta},{\mathbf{x}}^{n})\mu(\bm{\theta})\mathop{}\\!\mathrm{d}\bm{\theta},$

since the Laplace probability assignment
$q_{\mathsf{L}}(y^{n})=\int_{\mathcal{B}}\mu(\bm{\theta})p_{\bm{\theta}}(y^{n})\mathop{}\\!\mathrm{d}\bm{\theta}$
is a mixture with respect to a uniform density $\mu(\bm{\theta})$ over the
simplex $\mathcal{B}$. Hence, if we draw $N$ CRPs
$\bm{\theta}_{1},\ldots,\bm{\theta}_{N}$ from $\mu$ and _buy-and-hold_
uniformly over the CRPs, we will attain approximately similar wealth and the
approximation will get better as $N$ becomes larger. Note, however, that this
naive approximation requires $N=\Omega(\frac{1}{\epsilon^{m}})$ to achieve an
approximation error $\epsilon$ and thus may not be feasible when the number of
stocks $m$ is large.

A similar crude approximation can be performed for the universal portfolio
$\phi(q_{\mathsf{L};S})$ with discrete side information $w^{n}$, since

$\displaystyle S_{n}(\phi(q_{\mathsf{L};S}),{\mathbf{x}}^{n};w^{n})$
$\displaystyle=\sum_{y^{n}\in[m]^{n}}q_{\mathsf{L};S}(y^{n}\|w^{n}){\mathbf{x}}(y^{n})=\prod_{s=1}^{S}S_{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathbf{x}}^{n}(s;w^{n})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}(\phi(q_{\mathsf{L}}),{\mathbf{x}}^{n}(s;w^{n})),$

where
${\mathbf{x}}^{n}(s;w^{n})=({\mathbf{x}}_{i}\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar 58\relax}w_{i}=s,i\in[n])$, since
$q_{\mathsf{L};S}(y^{n}\|w^{n})=\prod_{s=1}^{S}q_{\mathsf{L}}(y^{n}(s;w^{n}))$.
That is, we can crudely approximate the performance of
$\phi(q_{\mathsf{L};S})$ by simply drawing many state-wise CRPs
$\bm{\theta}_{1\mathchar 58\relax S}$ according to
$\mu(\bm{\theta}_{1\mathchar 58\relax S})\mathrel{\mathop{\mathchar 58\relax
missing}}=\mu(\bm{\theta}_{1})\cdots\mu(\bm{\theta}_{S})$ and running the buy-
and-hold strategy.

We can now consider an approximation of the proposed strategy
$\phi(q_{\mathcal{G}}^{*})$. By the epoch-wise construction of
$q_{\mathcal{G}}^{*}$ as explicitly shown in (9), the cumulative wealth can be
also factorized as

$\displaystyle S_{n}(\phi(q_{\mathcal{G}}^{*}),{\mathbf{x}}^{n};z^{n})$
$\displaystyle=\prod_{j=1}^{J}\sum_{y_{2^{j-1}+1}^{2^{j}}\in[m]^{2^{j-1}}}q_{\mathcal{G};z^{2^{j-1}}}(y_{2^{j-1}+1}^{2^{j}}\|z_{2^{j-1}+1}^{2^{j}}){\mathbf{x}}_{2^{j-1}+1}^{2^{j}}(y_{2^{j-1}+1}^{2^{j}})$
$\displaystyle=\prod_{j=1}^{J}S_{2^{j-1}}(\phi(q_{\mathcal{G};z^{2^{j-1}}}),{\mathbf{x}}_{2^{j-1}+1}^{2^{j}};z_{2^{j-1}+1}^{2^{j}}).$

where we assume $n=2^{J}$ for simplicity. Here, for each $j\in[J]$, if
$\\{{\tilde{g}}_{1},\ldots,{\tilde{g}}_{\ell_{j}}\\}$ is a minimal empirical
covering of $\mathcal{G}$ with respect to $z^{2^{j-1}}$, we can write

$\displaystyle
S_{2^{j-1}}(q_{\mathcal{G};z^{2^{j-1}}},{\mathbf{x}}_{2^{j-1}+1}^{2^{j}};z_{2^{j-1}+1}^{2^{j}})$
$\displaystyle=\frac{1}{\ell_{j}}\sum_{k=1}^{\ell_{j}}S_{2^{j-1}}(\phi(q_{\mathsf{L};S}),{\mathbf{x}}_{2^{j-1}+1}^{2^{j}};{\tilde{g}}_{k}(z_{2^{j-1}+1}^{2^{j}})).$

For each state function ${\tilde{g}}_{k}$, the summand is the cumulative
wealth of the UP with the side information
${\tilde{g}}_{k}(z_{2^{j-1}+1}^{2^{j}})$ and thus can be approximated by the
same argument from the previous paragraph.

This leads to the following Monte Carlo simulation of the proposed algorithm.
Let $N$ be the number of Monte Carlo samples used in the approximation.

For each epoch $j=1,2,\ldots$: 1. Find an empirical covering
$\\{{\tilde{g}}_{1},\ldots,{\tilde{g}}_{\ell_{j}}\\}\subseteq\mathcal{G}$ with
respect to $z^{2^{j-1}}$. 2. For each $k\in[\ell_{j}]$, draw $N$ state-wise
CRPs $(\bm{\theta}_{1\mathchar 58\relax S,i}^{(k)})_{i=1}^{N}$ from
$\mu(\bm{\theta}_{1\mathchar 58\relax S})$ at random. 3. During the $j$-th
investment epoch, i.e., $t\in(2^{j-1},2^{j}]$, run the buy-and-hold strategy
uniformly over all sampled CRPs $(\bm{\theta}_{1\mathchar 58\relax
S,i}^{(k)})_{i=1}^{N}$ for each $k\in[\ell_{j}]$. 4. At the end of the epoch,
sell all stocks.

We stress that this only simulates the cumulative wealth of the universal
portfolio algorithm by directly estimating the cumulative wealth expression,
rather than approximating actions of the algorithm for each round. Note that a
more sophisticated Monte Carlo Markov Chain based approximation for Cover’s
universal portfolio was proposed and analyzed by Kalai and Vempala (2002). It
is left as a future direction to extend their method for our algorithm with
continuous side information.

In the following, we study a simple example for concreteness, which admits an
easy construction of minimal empirical coverings. Note that, for a richer
class of state functions, finding a minimal empirical covering may be another
computational bottleneck.

######  Example 15.

As a simple case of the canonical side information considered in Example 10,
we choose the price relative of the stock 1 on the previous day as the
continuous side information, i.e., $z_{t}={\bf x}_{t-1,1}$, and a class of 1D
threshold functions $\mathcal{G}=\\{x\mapsto g_{a}(x)=1\\{x\geq
a\\}\mathchoice{\colon}{\colon}{\mathchar 58\relax\mspace{1.0mu}}{\mathchar
58\relax}a>0\\}$ of $\mathrm{Ndim}(\mathcal{G})=1$. Note that we consider a
binary state space ($S=2$). In this case, it is easy to show that
$\\{g_{x_{0,1}},\ldots,g_{x_{t-1,1}}\\}$ is a minimal empirical covering given
$z^{t}=(x_{i,1})_{i=0}^{t-1}$.

In general, we can consider $z_{t}={\bf x}_{t-1}$ with a class of product of
1D threshold functions $\mathcal{G}=\\{x\mapsto
g_{\mathbf{a}}({\mathbf{x}})=(1\\{x_{1}\geq a_{1}\\},\ldots,1\\{x_{m}\geq
a_{m}\\})\mathchoice{\colon}{\colon}{\mathchar
58\relax\mspace{1.0mu}}{\mathchar
58\relax}\mathbf{a}=(a_{1},\ldots,a_{m})\in\mathbb{R}_{++}^{m}\\}$ of
$\mathrm{Ndim}(\mathcal{G})\leq m\log m$ (Shalev-Shwartz and Ben-David, 2014,
Lemma 29.6) and $S=2^{m}$. Given $z^{t}={\bf x}^{t-1}$, $\\{g_{{\bf
x}_{0}},\ldots,g_{{\bf x}_{t-1}}\\}$ is a minimal empirical covering.

We briefly demonstrate how the proposed portfolio performs on two real stocks.
We collected the 6-year period from Jan-01-2012 to Dec-31-2017 (total 1508
trading days) of two stocks Ford (F) and Macy’s (M). Over the period, Ford
went up by a factor of 1.11, while Macy’s went down by a factor of 0.77. The
best CRP in hindsight, which turns out to be the buy-and-hold of Ford,
achieves a growth factor of 1.11. The uniform CRP achieves a growth factor of
0.99. While the universal portfolio without side information achieves a growth
factor of only, the proposed algorithm with the yesterday’s prices and the
class of thresholding functions achieves a growth factor of 1.15.

We note that there can exist more sophisticated, carefully chosen side
information and state-function classes that may exhibit better performance in
practice than the simple example above. We leave the problem of constructing
good continuous side information and extensive experiments as future work.

## References

  * Bertail and Portier (2019) Patrice Bertail and François Portier.  Rademacher complexity for Markov chains: Applications to kernel smoothing and Metropolis–Hastings.  _Bernoulli_ , 25(4B):3912–3938, 2019.
  * Bhatt and Kim (2021) Alankrita Bhatt and Young-Han Kim.  Sequential prediction under log-loss with side information.  In _Algo. Learn. Theory_ , pages 340–344. PMLR, 2021.
  * Bilodeau et al. (2020) Blair Bilodeau, Dylan Foster, and Daniel Roy.  Tight bounds on minimax regret under logarithmic loss via self-concordance.  In _Proc. Int. Conf. Mach. Learn._ , pages 919–929. PMLR, 2020.
  * Bilodeau et al. (2021) Blair Bilodeau, Dylan J Foster, and Daniel M Roy.  Minimax rates for conditional density estimation via empirical entropy.  _arXiv preprint arXiv:2109.10461_ , 2021.
  * Blum and Kalai (1999) Avrim Blum and Adam Kalai.  Universal portfolios with and without transaction costs.  _Mach. Learn._ , 35(3):193–205, 1999.
  * Bousquet (2002) Olivier Bousquet.  _Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms_.  PhD thesis, École Polytechnique: Department of Applied Mathematics Paris, France, 2002.
  * Cesa-Bianchi and Lugosi (2006) Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge University Press, 2006.
  * Cover (1991) Thomas M Cover.  Universal portfolios.  _Math. Financ._ , 1(1):1–29, 1991.
  * Cover and Ordentlich (1996) Thomas M Cover and Erik Ordentlich.  Universal portfolios with side information.  _IEEE Trans. Inf. Theory_ , 42(2):348–363, 1996\.
  * Cover and Thomas (2006) Thomas M Cover and Joy A Thomas.  _Elements of information theory_.  John Wiley & Sons, 2006.
  * Cross and Barron (2003) Jason E Cross and Andrew R Barron.  Efficient universal portfolios for past-dependent target classes.  _Math. Financ._ , 13(2):245–276, 2003.
  * Fogel and Feder (2017) Yaniv Fogel and Meir Feder.  On the problem of on-line learning with log-loss.  In _Proc. IEEE Int. Symp. Inf. Theory_ , pages 2995–2999. IEEE, 2017.
  * Györfi et al. (2006) László Györfi, Gábor Lugosi, and Frederic Udina.  Nonparametric kernel-based sequential investment strategies.  _Math. Financ._ , 16(2):337–357, 2006.
  * Hanneke and Yang (2019) Steve Hanneke and Liu Yang.  Statistical learning under nonstationary mixing processes.  In _Int. Conf. Artif. Int. Statist._ , pages 1678–1686. PMLR, 2019\.
  * Kalai and Vempala (2002) Adam Tauman Kalai and Santosh Vempala.  Efficient algorithms for universal portfolios.  _J. Mach. Learn. Res._ , pages 423–440, 2002.
  * Karandikar and Vidyasagar (2002) Rajeeva L Karandikar and Mathukumalli Vidyasagar.  Rates of uniform convergence of empirical means with mixing processes.  _Stat. Probab. Lett._ , 58(3):297–307, 2002.
  * Kozat et al. (2008) Suleyman S Kozat, Andrew C Singer, and Andrew J Bean.  Universal portfolios via context trees.  In _Proc. IEEE Int. Conf. Acoust. Speech Signal Process._ , pages 2093–2096. IEEE, 2008.
  * Luo et al. (2018) Haipeng Luo, Chen-Yu Wei, and Kai Zheng.  Efficient online portfolio with logarithmic regret.  In _Adv. Neural Inf. Proc. Syst._ , pages 8245–8255, 2018.
  * Merhav and Feder (1998) Neri Merhav and Meir Feder.  Universal prediction.  _IEEE Trans. Inf. Theory_ , 44(6):2124–2147, 1998.
  * Rakhlin and Sridharan (2015) Alexander Rakhlin and Karthik Sridharan.  Sequential probability assignment with binary alphabets and large classes of experts.  _arXiv preprint arXiv:1501.07340_ , 2015.
  * Rakhlin et al. (2015) Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  _Probability Theory and Related Fields_ , 161(1-2):111–153, 2015.
  * Rissanen (1996) Jorma J Rissanen.  Fisher information and stochastic complexity.  _IEEE Trans. Inf. Theory_ , 42(1):40–47, 1996\.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Tavory and Feder (2010) Ami Tavory and Meir Feder.  Universal portfolio algorithms in realistic-outcome markets.  In _Proc. IEEE Inf. Theory Workshop_ , pages 1–5. IEEE, 2010.
  * Tavory and Feder (2008) Arni Tavory and Meir Feder.  Finite memory universal portfolios.  In _Proc. IEEE Int. Symp. Inf. Theory_ , pages 1408–1412. IEEE, 2008.
  * Uziel and El-Yaniv (2020) Guy Uziel and Ran El-Yaniv.  Long-and short-term forecasting for portfolio selection with transaction costs.  In _Int. Conf. Artif. Int. Statist._ , pages 100–110. PMLR, 2020\.
  * van Erven et al. (2020) Tim van Erven, Dirk van der Hoeven, Wojciech Kotłowski, and Wouter M Koolen.  Open problem: Fast and optimal online portfolio selection.  In _Conf. Learn. Theory_ , pages 3864–3869. PMLR, 2020.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Xie and Barron (2000) Qun Xie and Andrew R Barron.  Asymptotic minimax regret for data compression, gambling, and prediction.  _IEEE Trans. Inf. Theory_ , 46(2):431–445, 2000\.
  * Yu (1994) Bin Yu.  Rates of convergence for empirical processes of stationary mixing sequences.  _Ann. Probab._ , pages 94–116, 1994.
  * Ziv and Lempel (1978) Jacob Ziv and Abraham Lempel.  Compression of individual sequences via variable-rate coding.  _IEEE Trans. Inf. Theory_ , 24(5):530–536, 1978\.