Universal Portfolios With and Without Transaction Costs

Avrim Blum, Adam Kalai

This 1999 paper by Avrim Blum and Adam Kalai provides a significant update to Thomas Cover’s seminal work on "Universal Portfolios." The authors offer a much simpler geometric proof for the algorithm's performance, extend the theory to include transaction costs (commissions), and introduce a randomized implementation that makes the strategy computationally feasible for real-world use.

TL;DR

The authors simplify the analysis of Universal Portfolios—an investment strategy that competes with the best "constant rebalanced portfolio" in hindsight—and prove it remains effective even with transaction costs. They also introduce a fast, randomized version of the algorithm and demonstrate its surprising utility in statistical language modeling.

What Problem Does This Paper Address?

In quantitative finance, a Constant Rebalanced Portfolio (CRP) is a strategy that maintains a fixed distribution of wealth across assets (e.g., always keeping 50% in Stock A and 50% in Stock B). While simple, a CRP can exponentially outperform any individual stock in a volatile market.

The "Universal Portfolio" algorithm, introduced by Thomas Cover in 1991, is an online strategy that aims to perform nearly as well as the best CRP chosen in hindsight, without knowing the future. However, Cover’s original work had two major hurdles:

  1. Computational Complexity: The original implementation required calculating high-dimensional integrals, making it too slow for portfolios with many assets.
  2. Transaction Costs: The original theory assumed trading was free. In reality, commissions can quickly eat up the gains from frequent rebalancing.

Blum and Kalai tackle both of these issues while providing a more intuitive mathematical framework.

Methods

The core idea of a Universal Portfolio is to "invest" an equal amount of money into every possible CRP and let them run independently. Your total wealth is the average of all these strategies.

  • Simplified Analysis: The authors use a geometric argument based on the "volume" of portfolios. They show that because portfolios "near" the optimal one perform similarly, and because a significant fraction of the portfolio space is "near" the optimal one, the average performance is guaranteed to be strong.
  • Handling Commissions: They extend the model to include a fixed percentage commission ($c$). They prove that the universal strategy still achieves the same exponential growth rate as the best CRP, though the performance bound is slightly loosened (essentially treating $n$ periods as $(1+c)n$ periods).
  • Randomized Approximation: Instead of integrating over the entire space of possible portfolios, they propose sampling $N$ portfolios at random. By tracking only these $N$ samples, the algorithm becomes much faster while maintaining high probabilistic guarantees of performance.

Datasets

The authors evaluate their algorithm using 22 years of historical NYSE data. Specifically, they look at sets of stocks including:

  • Arco, Espey, and Exxon.
  • Alcoa, Amerb, and Arco.

These datasets were standard benchmarks in the late 90s for testing online investment algorithms.

Key Insights and Ideas

  • The "Nearness" Principle: The most elegant insight is that you don't need to find the exact best portfolio. A "shrunken simplex" of portfolios around the optimal one provides enough "volume" to ensure the average (the Universal Portfolio) stays competitive.
  • Commissions as Time Dilatation: Adding a transaction cost $c$ mathematically mirrors an increase in the number of trading periods. This provides a clean way to incorporate friction into the theoretical bounds.
  • Cross-Domain Utility: The authors show that the math of portfolios is identical to the math of mixing language models. If you have several different models (unigram, bigram, etc.), the Universal Portfolio algorithm can find the optimal mixture of these models on the fly, with a performance loss of only $O(\log n)$ in log-probability.

Key Results

  • Performance Bounds: The paper proves that the ratio of the Universal Portfolio's wealth to the best CRP's wealth is at least $1/(n+1)^{m-1}$ (where $n$ is the number of days and $m$ is the number of assets). With commissions, this becomes $1/((1+c)n+1)^{m-1}$.
  • Empirical Success: On the NYSE data, the algorithm significantly outperformed the average stock price.
  • Practicality: The randomized version allows the algorithm to scale to many more assets than the original $O(n^{m-1})$ deterministic version.
  • Language Modeling: They proved that the log-probability assigned to a sequence of words by their "universal mixture" is nearly as high as that of the best mixture determined in hindsight.

Limitations and Future Work

  • Rebalancing Frequency: While the theory holds for any $n$, the authors note that rebalancing too often (e.g., daily) with high commissions still hurts. In their experiments, they found rebalancing monthly was more practical.
  • Comparison to EG Algorithms: The authors acknowledge that the "Exponentiated Gradient" (EG) algorithm often performs better in practice, even though it lacked the same rigorous theoretical guarantees for transaction costs at the time of writing.
  • Fixed Commissions: The model assumes a fixed percentage cost. It doesn't account for more complex fee structures like flat fees or tiered pricing.

Summary updated

Abstract

A constant rebalanced portfolio is an investment strategy which keeps the same distribution of wealth among a set of stocks from period to period. Recently there has been work on on-line investment strategies that are competitive with the best constant rebalanced portfolio determined in hindsight (Cover, 1991, 1996; Helmbold et al., 1996; Cover & Ordentlich, 1996a, 1996b; Ordentlich & Cover, 1996). For the universal algorithm of Cover (Cover, 1991),we provide a simple analysis which naturallyextends to the case of a fixed percentage transaction cost (commission ), answering a question raised in (Cover, 1991; Helmbold et al., 1996; Cover & Ordentlich, 1996a, 1996b; Ordentlich & Cover, 1996; Cover, 1996). In addition, we present a simple randomized implementation that is significantly faster in practice. We conclude by explaining how these algorithms can be applied to other problems, such as combining the predictions of statistical language models, where the resulting guarantees are more striking.
BibTeX
@inproceedings{blum1997universal,
  author = {Avrim Blum and Adam Kalai},
  title = {{Universal Portfolios With and Without Transaction Costs}},
  booktitle = {Conference on Learning Theory},
  year = {1997},
  doi = {10.1145/267460.267518},
}

Loading related content...

Figure