Abstract
This paper presents a simplified analysis of Thomas Cover’s Universal Portfolio algorithm, extending the theoretical framework to include fixed percentage transaction costs. By employing a geometric argument, the authors demonstrate that the universal strategy remains competitive with the best constant rebalanced portfolio (CRP) in hindsight. Furthermore, a randomized implementation is introduced to address the computational bottlenecks of the original deterministic algorithm, and its utility is demonstrated in the context of statistical language modeling.
Introduction
In the field of quantitative finance, a Constant Rebalanced Portfolio (CRP) is a strategy that maintains a fixed distribution of wealth across a set of assets. For instance, a 50/50 split between two stocks requires selling the outperforming asset and buying the underperforming one at each time step to maintain the ratio. While individual stocks may fluctuate, a well-chosen CRP can achieve exponential growth.
The challenge lies in selecting the optimal CRP without prior knowledge of future market movements. Thomas Cover’s "Universal Portfolio" (1991) addressed this by proposing an online strategy that competes with the best CRP determined in hindsight. However, the original formulation faced two significant hurdles: extreme computational complexity and the omission of transaction costs (commissions).
The Universal Portfolio Algorithm
The Universal Portfolio operates by "investing" an equal amount of money into every possible CRP. The total wealth of the universal strategy at any time is the average wealth of all these individual CRP strategies. Mathematically, this involves integrating over the simplex of all possible asset distributions.
Simplified Geometric Analysis
Blum and Kalai provide a more intuitive proof for the performance of this algorithm. Their analysis hinges on a "nearness" principle: portfolios that are close to the optimal CRP in the distribution space will perform similarly to it. By showing that a significant fraction of the total "volume" of the portfolio space is sufficiently close to the optimal one, they guarantee that the average performance (the Universal Portfolio) will not lag too far behind the best possible hindsight strategy.
Specifically, they prove 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 trading periods and $m$ is the number of assets.
Incorporating Transaction Costs
A major contribution of this work is the extension of the theory to include a fixed percentage commission $c$. In real-world trading, frequent rebalancing can be prohibitively expensive.
The authors demonstrate that the universal strategy still achieves the same exponential growth rate as the best CRP even with commissions. They introduce an elegant mathematical interpretation where adding a transaction cost $c$ is equivalent to a "time dilation" effect, essentially treating $n$ periods as $(1+c)n$ periods in the performance bounds. This results in a bound of $1/((1+c)n+1)^{m-1}$.
Randomized Implementation
The original deterministic algorithm required calculating high-dimensional integrals, which scales poorly ($O(n^{m-1})$) as the number of assets increases. To make the strategy practical, Blum and Kalai propose a randomized approximation. Instead of integrating over the entire simplex, the algorithm samples $N$ portfolios at random and tracks their performance. This sampling approach allows the algorithm to scale to portfolios with many assets while maintaining high probabilistic guarantees of performance.
Applications in Language Modeling
The mathematical framework of Universal Portfolios extends beyond finance. The authors show that the problem of finding the optimal mixture of statistical language models (e.g., combining unigram, bigram, and trigram models) is isomorphic to the portfolio problem.
In this context, the Universal Portfolio algorithm can find the optimal mixture of models on the fly. The performance loss in terms of log-probability is bounded by $O(\log n)$, providing a robust method for combining predictions from multiple sources without knowing which will be most accurate in advance.
Empirical Results and Conclusion
Testing on 22 years of historical NYSE data, the authors confirmed that the Universal Portfolio significantly outperforms individual stocks and remains effective even when rebalancing is adjusted for commissions. While more recent algorithms like Exponentiated Gradient (EG) may offer better empirical performance in some scenarios, this paper provides the foundational theoretical guarantees for transaction costs and a practical path forward via randomization.
The work of Blum and Kalai bridges the gap between theoretical online learning and practical financial engineering, offering a robust framework for competitive investment and sequence prediction.
Based on: Blum, A., & Kalai, A. (1999). Universal Portfolios With and Without Transaction Costs. Machine Learning, 35, 193–205.
Summary updated