Understanding Cover’s Universal Portfolio Dec 6, 2023

The setup #

There are $m$ assets and $T$ trading periods. All that matters about period $t$ is the vector of price relatives

$$x_t = (x_{t,1}, \dots, x_{t,m}), \qquad x_{t,i} = \frac{p_{t,i}}{p_{t-1,i}} \ge 0,$$

the factor by which asset $i$’s price moves from one close to the next. A portfolio is a point of the simplex $\Delta_m = \{ b \in \mathbb{R}^m : b_i \ge 0, \ \sum_i b_i = 1 \}$, the fraction of current wealth held in each asset. If you hold $b$ during period $t$, your wealth is multiplied by $b \cdot x_t = \sum_i b_i x_{t,i}$.

A constant-rebalanced portfolio (CRP) uses the same $b$ every period. That is not buy-and-hold: as prices move the weights drift, and each period you trade back to $b$, selling some of what went up and buying some of what went down. Starting from one dollar, its wealth after $T$ periods is

$$S_T(b) = \prod_{t=1}^{T} b \cdot x_t .$$

The vertices of the simplex are CRPs too: $b = e_i$ is simply “hold asset $i$”. The benchmark is the best CRP in hindsight,

$$b^* = \arg\max_{b \in \Delta_m} S_T(b), \qquad S_T^* = S_T(b^*) \ \ge\ \max_i S_T(e_i),$$

so beating $S_T^*$ means beating the best single stock as well. Of course $b^*$ depends on the whole future, so nobody can actually play it. The question is how close a strategy that only sees the past can get.

Volatility pumping: money from assets that go nowhere #

The reason rebalancing can beat every stock is the gap between arithmetic and geometric growth. Wealth compounds multiplicatively, so what matters is $\mathbb{E} \log(b \cdot x)$, and for small log-returns with mean $\mu$ and variance $\sigma^2$ the growth rate of a single asset is roughly $\mu$ while its arithmetic mean return is $\mu + \sigma^2/2$. That half-variance is drag you pay for volatility. Mixing assets and rebalancing reduces the variance of the portfolio below that of its components (as long as they are not perfectly correlated), so it recovers part of the drag.

The classic example makes this stark. Take cash ($x_{t,1} = 1$ always) and a stock that doubles, then halves, then doubles, forever:

$$x_1 = (1, 2), \quad x_2 = (1, \tfrac12), \quad x_3 = (1, 2), \quad \dots$$

Both assets stagnate: after every pair of periods the stock is back where it started, and cash never moves. Now rebalance to half and half. In an up period wealth is multiplied by $\tfrac12 \cdot 1 + \tfrac12 \cdot 2 = \tfrac32$, in a down period by $\tfrac12 + \tfrac12 \cdot \tfrac12 = \tfrac34$, so every pair of periods multiplies wealth by $\tfrac32 \cdot \tfrac34 = \tfrac98$. Over $T$ periods that is $(9/8)^{T/2}$: exponential growth from two assets that each end where they started. More generally, with weight $b$ on the stock, each pair of periods gives $(1+b)(1-b/2) = 1 + b/2 - b^2/2$, which is maximised at $b^* = \tfrac12$, so $\tfrac98$ is the best a CRP can do here.

This is neither a “mean-reversion” nor a “momentum” bet. Every CRP is mean-reverting at the level of trades (it sells winners), but you then let the CRPs that happen to suit the market run, which is the momentum part, and that is exactly what Cover’s algorithm does.

Real data shows the same thing. In Cover’s 1991 paper, Iroquois Brands and Kin Ark, two volatile NYSE stocks, grew by factors of 8.92 and 4.13 over 22 years ending in 1985. The best CRP in hindsight, $b^* = (0.55, 0.45)$, grew by 73.6, and the universal portfolio below, which never saw the future, grew by 38.7.

The universal portfolio #

We cannot know $b^*$, but we can hedge over all of them. Put a prior $\mu$ on the simplex (uniform, to start with) and at time $t+1$ hold the wealth-weighted average of all CRPs:

$$\hat b_{t+1} = \frac{\int_{\Delta_m} b \, S_t(b) \, d\mu(b)}{\int_{\Delta_m} S_t(b) \, d\mu(b)}, \qquad \hat b_1 = \int b \, d\mu(b), \qquad S_0 \equiv 1 .$$

A CRP’s weight is proportional to how much money it has made so far, so this is a Bayesian posterior mean, with $S_t(b)$ playing the role of the likelihood. No step size, no window, no tuning.

The wealth of this strategy has a closed form. Since $\hat b_{t+1} \cdot x_{t+1} = \int S_t(b) \, (b \cdot x_{t+1}) \, d\mu / \int S_t \, d\mu = \int S_{t+1} \, d\mu / \int S_t \, d\mu$, the product telescopes:

$$\hat S_T = \prod_{t=1}^{T} \hat b_t \cdot x_t = \int_{\Delta_m} S_T(b) \, d\mu(b).$$

So the universal portfolio’s wealth is the average wealth of all CRPs. That gives a second, more physical description: split your dollar among a continuum of fund managers, manager $b$ getting $d\mu(b)$, let each run CRP $b$ forever, and never move money between them. This buy-and-hold over CRPs is the same strategy, period by period.

Now the trick is visible. An average is at least as large as the contribution of the best region, and $S_T(b)$ grows exponentially, so the average is dominated by the CRPs near $b^*$. What we lose is only the prior mass that sits close enough to $b^*$, and that turns out to be polynomial in $T$, not exponential.

The regret bound #

Define the regret as the log-wealth gap, $R_T = \log S_T^* - \log \hat S_T$.

Theorem (Cover and Ordentlich 1996). With the uniform prior on $\Delta_m$, for every $T$ and every sequence $x_1, \dots, x_T$,

$$\frac{S_T^*}{\hat S_T} \le \binom{T+m-1}{m-1} \le (T+1)^{m-1}, \qquad\text{so}\qquad R_T \le (m-1) \log(T+1).$$

The regret grows only logarithmically, so the per-period regret $R_T / T \le (m-1)\log(T+1)/T \to 0$: the universal portfolio has the same exponential growth rate as the best CRP in hindsight, on every sequence. It does not say that $\hat S_T \ge S_T^*$, or even that it beats the best stock in any given finite window, only that it falls short by a factor that grows polynomially while $S_T^*$ itself can grow exponentially.

Connections: Kelly betting and universal coding #

Kelly / log-optimal growth. If the $x_t$ are i.i.d. from some distribution $F$, Kelly’s log-optimal portfolio maximises $W(b) = \mathbb{E}_F \log(b \cdot x)$, and the best constant portfolio has growth rate $W^* = \max_b W(b)$. Knowing $F$, you would play the maximiser $b_F$ and by the law of large numbers $\frac1T \log S_T(b_F) \to W^*$. But $S_T^* \ge S_T(b_F)$ on every sample path, so

$$\frac1T \log \hat S_T \ \ge\ \frac1T \log S_T(b_F) - \frac{(m-1)\log(T+1)}{T} \ \longrightarrow\ W^* \quad \text{a.s.}$$

The universal portfolio reaches Kelly’s growth rate without knowing $F$, and without even assuming that a distribution exists.

Universal coding. Take a “horse race” market where in each period exactly one asset pays off, $x_t = e_{j_t}$. Then $S_T(b) = \prod_i b_i^{n_i}$ is the probability that the i.i.d. distribution $b$ assigns to the sequence $j_1, \dots, j_T$, the best CRP is the maximum-likelihood distribution, and $\hat S_T = \int \prod_i b_i^{n_i} \, d\mu(b)$ is the Bayesian mixture probability. Regret is then exactly the code length, in nats, that the mixture code loses against the best i.i.d. code chosen in hindsight. The portfolio update becomes a sequential predictor. With the uniform prior it is Laplace’s rule $\hat b_{t+1,i} = (n_i + 1)/(t + m)$. With the Dirichlet(1/2) prior it is $\hat b_{t+1,i} = (n_i + \tfrac12)/(t + \tfrac m2)$, the Krichevsky–Trofimov estimator, whose redundancy of $\frac{m-1}{2}\log T + O(1)$ is the classic universal-coding result. Cover and Ordentlich show that this horse-race market is the least favourable case: the general bounds are exactly the worst-case redundancies of these mixture codes. Investing well and compressing well are the same problem.

Try it #

Below, two stocks with independent, roughly driftless log-returns. The top plot is the final wealth $S_T(b)$ of every CRP. Its two endpoints are the stocks themselves, and the hump in between is the rebalancing bonus. The dashed line is the universal portfolio, which is just the average height of that curve. Raise the volatility and the hump grows, roughly like $T\sigma^2/4$ in log-wealth for an even split. Raise $T$ and watch the regret: it creeps up like $\log T$ while the wealth itself moves exponentially. Then press New market a few times. Quite often one stock simply runs away, $b^*$ lands at 0 or 1, and the universal portfolio trails it. At these settings a stock’s random walk ($\sigma\sqrt T \approx 1.3$ in log-wealth) is larger than the rebalancing bonus ($T\sigma^2/4 \approx 0.45$). The guarantee still holds in every case, because it is a promise about the gap to the best CRP, not about winning.

The code #

Here is the whole algorithm for two assets, with the integral over $b$ replaced by a fine midpoint grid on $[0,1]$. It runs four markets: the double-or-halve example, a random two-stock market with the uniform and the Dirichlet(1/2) prior, and the boundary case where the uniform bound is nearly tight. It also checks the telescoping identity: the wealth obtained by actually trading $\hat b_t$ period by period matches the prior average of $S_T(b)$.

import numpy as np

K = 2000
grid = (np.arange(K) + 0.5) / K   # midpoints of [0,1]: b = weight on asset 1

def crp_log_wealth(x, grid):
    """log S_t(b) for every t and every b on the grid, shape (T, K)."""
    per_step = np.log(np.outer(x[:, 0], grid) + np.outer(x[:, 1], 1 - grid))
    return np.cumsum(per_step, axis=0)

def universal(x, grid, prior):
    """Play Cover's portfolio day by day; return log wealth and the b_hat path."""
    logS = crp_log_wealth(x, grid)
    prev = np.zeros(len(grid))            # log S_0(b) = 0 for every b
    log_wealth, path = 0.0, []
    for t in range(len(x)):
        w = prior * np.exp(prev - prev.max())   # posterior weight ~ prior * S_{t-1}(b)
        b_hat = (grid * w).sum() / w.sum()      # wealth-weighted average of all CRPs
        path.append(b_hat)
        log_wealth += np.log(b_hat * x[t, 0] + (1 - b_hat) * x[t, 1])
        prev = logS[t]
    return log_wealth, np.array(path), logS

def report(name, x, prior=None, bound=None):
    T = len(x)
    prior = np.ones(K) if prior is None else prior
    prior = prior / prior.sum()
    log_up, path, logS = universal(x, grid, prior)
    # best CRP in hindsight: grid search, plus the two endpoints b = 0, 1
    cands = np.concatenate([[0.0], grid, [1.0]])
    final = np.concatenate([[np.log(x[:, 1]).sum()], logS[-1],
                            [np.log(x[:, 0]).sum()]])
    i = np.argmax(final)
    b_star, log_star = cands[i], final[i]
    # telescoping check: wealth of the played strategy = prior-average of S_T(b)
    m = logS[-1].max()
    log_mix = m + np.log((prior * np.exp(logS[-1] - m)).sum())
    print(f"--- {name}  (T = {T})")
    print(f"  asset 1 buy-and-hold : {np.prod(x[:, 0]):10.4g}")
    print(f"  asset 2 buy-and-hold : {np.prod(x[:, 1]):10.4g}")
    print(f"  best CRP  b* = {b_star:.3f} : {np.exp(log_star):10.4g}")
    print(f"  universal portfolio  : {np.exp(log_up):10.4g}"
          f"   (mixture of CRPs: {np.exp(log_mix):.4g})")
    regret = log_star - log_up
    if bound is None:
        bound = np.log(T + 1)
    print(f"  regret log S* - log S_up = {regret:.3f}  <=  bound {bound:.3f}")
    print(f"  per-period regret       = {regret / T:.5f}")
    print(f"  final b_hat = {path[-1]:.3f}")

# 1) Cash plus a stock that doubles, then halves, forever. Both are flat.
T = 40
stock = np.where(np.arange(T) % 2 == 0, 2.0, 0.5)
x = np.column_stack([stock, np.ones(T)])
report("cash + double/halve stock", x)

# 2) Two volatile, driftless, independent stocks.
rng = np.random.default_rng(1991)
T = 1000
logret = rng.normal([0.0, 0.0], [0.08, 0.08], size=(T, 2))
x = np.exp(logret)                       # price relatives x_t = p_t / p_{t-1}
report("two random stocks, uniform prior", x)

# 3) Same market with the Dirichlet(1/2, 1/2) prior of Cover & Ordentlich.
jeffreys = 1 / np.sqrt(grid * (1 - grid))
report("two random stocks, Dirichlet(1/2) prior", x, prior=jeffreys,
       bound=0.5 * np.log(T + 1) + np.log(2))

# 4) Worst case for the uniform prior: asset 1 beats asset 2 every single day,
#    so b* = 1 sits on the boundary and the bound is almost attained.
T = 1000
x = np.column_stack([np.full(T, 2.0), np.ones(T)])
report("asset 1 always doubles, asset 2 flat", x)

What to expect: in the double-or-halve market both assets end at 1.0 and the best CRP ($b^* = 0.5$) at $(9/8)^{20} \approx 10.5$, while the universal portfolio reaches about 6.0 with no knowledge of the pattern. On the random market (seed 1991) the two stocks end at about 4.0 and 2.2, and the universal portfolio at about 8.6 beats both, with a regret of 0.41 nats against a ceiling of 6.9. In the last market the regret is 6.22, close to the ceiling of 6.91 and to the exact value $\log\frac{T+1}{2} \approx 6.22$.

Caveats #

• Computation. The update is an integral over an $(m-1)$-dimensional simplex. A grid is fine for two or three assets but grows exponentially with $m$. Kalai and Vempala (2002) showed how to sample from the wealth-weighted distribution over CRPs with a random walk, which gives an implementation polynomial in $m$ and $T$. This works because $S_t(b)$ is log-concave in $b$.
• Transaction costs. All of the above assumes free rebalancing. Every CRP trades every period, and a real implementation has to pay for that.
• Time scale. $R_T / T \to 0$ is a statement about exponents. With $m$ assets the uniform prior can cost a factor of up to $(T+1)^{m-1}$, which is enormous for moderate $m$ and $T$. The rebalancing bonus has to be large compared to that before the universal portfolio gets ahead of the best stock. In practice it pays off with a few volatile, weakly correlated assets over long horizons.
• The benchmark. “Universal” is relative to the class of CRPs. It is a strong benchmark (the best CRP beats the best stock, and is Kelly-optimal for i.i.d. markets), but it is not the best possible strategy for a market with structure, say, trends that a predictive model could exploit.

Here is the colab where I first tested the ideas: colab

References #

• 20. 13. Cover. Universal Portfolios. Mathematical Finance, 1(1):1–29, 1991. doi:10.1111/j.1467-9965.1991.tb00002.x
• 20. 13. Cover and E. Ordentlich. Universal Portfolios with Side Information. IEEE Transactions on Information Theory, 42(2):348–363, 1996.
• 1. Kalai and S. Vempala. Efficient Algorithms for Universal Portfolios. Journal of Machine Learning Research, 3:423–440, 2002.
• 10. 12. Kelly, Jr. A New Interpretation of Information Rate. Bell System Technical Journal, 35(4):917–926, 1956.
• 18. Krichevsky and V. Trofimov. The Performance of Universal Encoding. IEEE Transactions on Information Theory, 27(2):199–207, 1981.