An Online Portfolio Selection Algorithm With Regret Logarithmic In Price Variation

We present a novel efficient algorithm for portfolio selection which theoretically attains two desirable properties: Worst-case guarantee: the algorithm is universal in the sense that it asymptotically performs almost as well as the best constant rebalanced portfolio determined in hindsight from the realized market prices. Furthermore, it attains the tightest known bounds on the regret, or the log-wealth difference relative to the best constant rebalanced portfolio. We prove that the regret of the algorithm is bounded by O(logQ), where Q is the quadratic variation of the stock prices. This is the first improvement upon Cover's (1991) seminal work that attains a regret bound of O(logT), where T is the number of trading iterations. Average-case guarantee: in the Geometric Brownian Motion (GBM) model of stock prices, our algorithm attains tighter regret bounds, which are provably impossible in the worst-case. Hence, when the GBM model is a good approximation of the behavior of market, the new algorithm has an advantage over previous ones, albeit retaining worst-case guarantees. We derive this algorithm as a special case of a novel and more general method for online convex optimization with exp-concave loss functions.