Universal portfolios via context trees

In this paper, we consider the sequential portfolio investment problem considered by Cover [3] and extend the results of [3] to the class of piecewise constant rebalanced portfolios that are tuned to the underlying sequence of price relatives. Here, the piecewise constant models are used to partition the space of past price relative vectors where we assign a different constant rebalanced portfolio to each region independently. We then extend these results where we compete against a doubly exponential number of piecewise constant portfolios that are represented by a context tree. We use the context tree to achieve the wealth of a portfolio selection algorithm that can choose both its partitioning of the space of the past price relatives and its constant rebalanced portfolio within each region of the partition, based on observing the entire sequence of price relatives in advance, uniformly, for every bounded deterministic sequence of price relative vectors. This performance is achieved with a portfolio algorithm whose complexity is only linear in the depth of the context tree per investment period. We demonstrate that the resulting portfolio algorithm achieves significant gains on historical stock pairs over the algorithm of [3] and the best constant rebalanced portfolio.