24 FOLLOW THE WINNER
wealth over the continuum of portfolio strategies. Note that S
n
(b) = e
nW
n
(b)
, which
means that the portfolio grows at an exponential rate of W
n
(b).
Formally, its update scheme (Cover and Ordentlich 1996, Definition 1) can
be interpreted as a historical performance-weighted average of all valid constant
rebalanced portfolios,
b
t+1
=
m
bS
t
(b)dμ(b)
m
S
t
(b)dμ(b)
.
Note that at the beginning of period t +1, one CRP manager’s wealth (historical
performance) equals S
t
(b)dμ(b). Incorporating the initial wealth of S
0
= 1, the final
cumulative wealth is the weighted average of CRP managers’ wealth (Cover and
Ordentlich 1996, Eq. (24)):
S
n
(UP) =
m
S
n
(b)dμ(b). (4.1)
One special case is that μ equals a uniform distribution; the portfolio update reduces
to Cover’s UP (Cover 1991, Eq. (1.3)). Another special cases is Dirichlet
1
2
,...,
1
2
weighted UP (Cover and Ordentlich 1996), which is proved to be a more optimal
allocation.
Alternatively, if a loss function is defined as the negative logarithmic function
of portfolio return, Cover’s UP is actually an exponentially weighted average fore-
caster (Cesa-Bianchi and Lugosi 2006). The regret (Cover 1991) achieved by Cover’s
UP is O(m log n), and its time complexity is O(n
m
), where m denotes the number
of stocks and n refers to the number of periods. Cover and Ordentlich (1996) proved
that the
1
2
,...,
1
2
weighted UP has the same scale of regret bound, but a better
constant term (Cover and Ordentlich 1996, Theorem 2).
As Cover’s UP is based on an ideal market model, one research direction is to
extend the algorithm to handle various realistic assumptions. Cover and Ordentlich
(1996) considered side information, including experts’ opinions and fundamental
data. Cover and Ordentlich (1998) extended the algorithm to handle short selling and
margin, and Blum and Kalai (1999) took account of transaction costs.
Another research direction is to generalize Cover’s UP with different base classes,
rather than the CRP strategy. Jamshidian (1992) generalized the algorithm for con-
tinuous time markets and presented its long-term performance. Vovk and Watkins
(1998) applied the aggregating algorithm (AA) (Vovk 1990) to a finite number of
arbitrary investment strategies, of which Cover’s UP becomes a specialized case
when applied to an infinite number of CRPs. Ordentlich and Cover (1998) analyzed
the minimal ratio of final wealth achieved by any nonanticipating investment strategy
to that of BCRP and presented a strategy to achieve such an optimal ratio. Cross and
Barron (2003) generalized Cover’s UP from the CRP strategy class to any parameter-
ized target class and proposed a computation favorable universal strategy. Akcoglu
et al. (2005) extended Cover’s UP from a parameterized CRP class to a wide class
of investment strategies, including trading strategies operating on a single stock and
portfolio strategies operating on the whole stock market. Kozat and Singer (2011)
proposed a similar universal algorithm based on the class of semiconstant rebalanced
T&F Cat #K23731 — K23731_C004 — page 24 — 9/28/2015 — 21:07