Cornell researchers cut swap regret to √(kT) in multi-dimensional forecasting

Forecasting for multiple downstream agents with unknown objectives has long been a challenge in online learning and game theory. Prior algorithms either suffered from exponential runtime in the time horizon T or required restrictive behavioral assumptions. This paper, accepted at ACM EC 2026, introduces a new algorithm that guarantees sublinear swap regret—the standard measure of strategic consistency—for all agents simultaneously. The key innovation is a polynomial-time method for two-dimensional outcome spaces that achieves Õ(√(kT)) regret, where k is the number of actions per agent. This beats the previous best bound of Õ(kT^(5/8)) and eliminates the exponential-in-T runtime that made prior approaches impractical.

The algorithm extends naturally to higher dimensions: for any dimension d, it guarantees Õ(d√(kT)) regret when the forecaster knows an upper bound k on actions, albeit with longer runtime scaling with d. Notably, this high-dimensional guarantee improves on prior Õ(T^(2/3)) bounds and does not require additional behavioral assumptions about agent strategies. The results are especially relevant for economic and computational settings where a single forecaster must serve many agents with differing objectives—such as pricing, recommendation systems, and resource allocation. By providing efficient, worst-case guarantees, this work opens the door to more robust and practical forecasting tools.