Internal Regret in On-Line Portfolio Selection

Gilles Stoltz, Gábor Lugosi

Abstract

Traditional online portfolio selection focuses on minimizing external regret—the difference in performance against the best fixed strategy in hindsight. This paper introduces a more stringent criterion: internal regret. By ensuring that no simple "swap rule" could have improved past decisions, internal-regret-minimizing algorithms like B1EXP achieve greater stability and robustness. We present theoretical bounds for these strategies and demonstrate their empirical superiority on historical NYSE stock data, particularly in their resilience to hyperparameter selection.

Introduction

In the domain of online learning and algorithmic trading, the gold standard has long been the minimization of external regret. This metric measures the difference between an algorithm's performance and that of the best fixed strategy chosen in hindsight. However, Stoltz and Lugosi (2005) argue that external regret is a coarse measure. They extend the game-theoretic concept of internal regret to portfolio selection, creating a stricter requirement: every specific decision must be "locally" optimal.

An algorithm with no internal regret ensures that there is no simple "swap rule" (e.g., "always buy Stock B instead of Stock A") that would have improved the outcome. While minimizing internal regret automatically minimizes external regret, achieving this in portfolio selection—where experts are continuous distributions and loss functions are non-linear—presents significant mathematical challenges.

Methods and Algorithms

The authors bridge the gap between discrete game theory and continuous portfolio selection using a "conversion trick." By treating pairs of assets as "fictitious experts" and utilizing a fixed-point lemma, they transform standard external-regret-minimizing algorithms into internal-regret-minimizing ones. This involves solving a system of linear equations via Gaussian elimination at each time step.

Key strategies introduced include:

  • B1EXP: An exponential weighting algorithm applied to asset pairs.
  • B1POL: A variant using polynomial weights.
  • Generalized Buy-and-Hold (GBH): A strategy that applies the internal regret framework to a buy-and-hold benchmark, proving effective under high transaction costs.

To illustrate the adaptive behavior of these strategies, consider a three-asset scenario with shifting loss regimes. As shown in the table below, the optimal asset changes across three distinct periods.

Loss regimes for a three-asset toy example where the optimal asset shifts from A to B to C.

The internal-regret-minimizing algorithm responds by smoothly reallocating wealth. As seen in the figure below, the weight of asset B increases when its losses are lowest (Regime 2) and decreases as other assets become more favorable.

Evolution of the weight assigned to asset B, demonstrating smooth adaptation to changing market regimes.

Empirical Evaluation

The authors evaluated their algorithms using the classic NYSE historical dataset, consisting of daily wealth ratios for 36 stocks over several decades.

Key Results

  • Robustness to Hyperparameters: A significant finding is that B1EXP is far less sensitive to the learning rate ($\eta$) than the standard Exponentiated Gradient (EG) algorithm. Even with a poorly chosen $\eta$, B1EXP maintains competitive performance, whereas EG’s performance often collapses.
  • Performance Superiority: In head-to-head tests, B1EXP outperformed the EG algorithm in the vast majority of trials. For example, in monthly rebalancing with ten stocks, B1EXP outperformed EG in 94 out of 100 random samples.
  • Theoretical Bounds: The authors prove that B1EXP achieves a cumulative internal regret of $O(\sqrt{n \ln N})$, where $n$ is time and $N$ is the number of assets.

Conclusion

The "no-internal-regret" property is fundamentally linked to stability. By accounting for all possible pairwise swaps, these algorithms are less likely to make erratic, high-variance bets on single assets. Forcing an algorithm to satisfy the stricter requirement of zero internal regret leads to better empirical returns on real stock data, suggesting that real markets reward the robustness inherent in this game-theoretic approach.

Summary updated

BibTeX
@inproceedings{stoltz2003internal,
  author = {Gilles Stoltz and Gábor Lugosi},
  title = {{Internal Regret in On-Line Portfolio Selection}},
  booktitle = {Conference on Learning Theory},
  year = {2003},
  doi = {10.1007/978-3-540-45167-9\_30},
}
Figure