In the world of online learning and algorithmic trading, the gold standard has long been minimizing external regret—the difference between your performance and the performance of the best fixed strategy in hindsight. But what if that isn't enough? What if you want to ensure that every specific decision you made was "locally" optimal?
In their 2005 paper, "Internal Regret in On-Line Portfolio Selection," Gilles Stoltz and Gábor Lugosi extend a sophisticated game-theoretic concept called internal regret to the financial domain. They demonstrate that by solving a "harder" regret problem, we can build investment strategies that are more stable and perform better on real-world data than traditional benchmarks.
TL;DR
This paper adapts the game-theoretic notion of "internal regret" to online portfolio selection, moving beyond simple hindsight comparisons. The authors introduce new strategies like B1EXP that minimize this stricter regret metric, resulting in investment algorithms that are more robust to parameter tuning and consistently outperform standard methods like the Exponentiated Gradient (EG) on historical stock data.
What Problem Does This Paper Address?
Most online portfolio algorithms aim to minimize external regret. If you invested in a mix of stocks and ended up with less money than if you had just put everything into Apple on day one, that difference is your external regret.
However, external regret is a coarse metric. Internal regret is much stricter. It asks: "Every time I invested in Stock A, would I have been better off investing that specific portion in Stock B instead?"
If an algorithm has no internal regret, it means there is no simple "swap rule" (e.g., "always buy Google instead of Intel") that would have improved the outcome. While it is well-known that minimizing internal regret automatically minimizes external regret, doing so in the context of portfolio selection—where the "experts" are continuous distributions of assets and the loss functions are non-linear (logarithmic wealth)—is mathematically challenging.
Methods
The authors bridge the gap between discrete game theory and continuous portfolio selection using several novel approaches:
- The Conversion Trick: They utilize a game-theoretic "fixed-point" lemma. By treating pairs of assets as "fictitious experts," 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 to find the optimal asset distribution.
- B1EXP & B1POL: These are the primary new algorithms. B1EXP uses exponential weighting (similar to the Hedge algorithm) applied to asset pairs, while B1POL uses polynomial weights.
- GBH (Generalized Buy-and-Hold): A strategy that applies the internal regret framework to the simplest possible benchmark: the buy-and-hold strategy.
- Generalized Universal Portfolio: They extend Thomas Cover’s famous "Universal Portfolio" to a continuum of modified strategies, providing a theoretical (though computationally expensive) upper bound on generalized internal regret.
Datasets
The authors evaluate their algorithms using a classic benchmark in the field:
- NYSE Historical Data: A dataset consisting of daily wealth ratios for 36 stocks on the New York Stock Exchange, spanning several decades.
- Experimental Setup: They tested the algorithms on random subsets (e.g., "three stocks" or "ten stocks") and compared performance across both daily rebalancing and monthly rebalancing (simulated using 20-day blocks).
Key Insights and Ideas
- Stability is Key: The authors argue that the "no-internal-regret" property is fundamentally linked to stability. Because these algorithms account for all possible pairwise swaps, they are less likely to make erratic, high-variance bets on a single asset.
- Robustness to Hyperparameters: A major "aha moment" in the experimental section 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 can collapse.
- Harder Constraints, Better Results: Counter-intuitively, forcing an algorithm to satisfy the much stricter requirement of zero internal regret leads to better empirical returns on real stock data, likely because real markets aren't perfectly adversarial.
Key Results
- 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. Its worst-case logarithmic wealth ratio is $O(N \sqrt{n \ln N})$.
- Empirical Superiority: In head-to-head tests on NYSE data, 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.
- Transaction Costs: The paper shows that the GBH strategy is particularly effective when transaction costs are high, as it naturally stays closer to a buy-and-hold distribution while still providing internal regret guarantees.
Limitations and Future Work
- Computational Overhead: While B1EXP is practical (requiring an $N \times N$ matrix inversion per step), the "Generalized Universal Portfolio" described in Section 7.2 has exponential complexity relative to the number of stocks, making it purely a theoretical benchmark.
- Boundedness Assumption: The theoretical proofs rely on the assumption that market returns are bounded ($m \le x_{i,t} \le M$). In extreme "black swan" events or market crashes, these bounds might be violated, potentially affecting the regret guarantees.
- Future Directions: The authors suggest that further research could explore more complex "departure functions" (beyond simple pairwise swaps) to see if even more sophisticated notions of regret lead to even better trading strategies.
Summary updated