Improved Multi-Dimensional Forecasting for Swap Regret

arXiv:2606.29533v1 Announce Type: cross Abstract: We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a single forecaster that guarantees sublinear swap regret for all downstream agents simultaneously. For two-dimensional outcome spaces, we give a polynomial time algorithm that guarantees ilde{O}(sqrt{kT}) swap regret for any downstream agent with k actions. This improves over the previously known bound of ilde{O}(kT^{5/8}) and avoids the exponential in T runtime of prior algorithms in this setting. Our algorithm extends nicely to other low dimensional environments, retaining ilde{O}(sqrt{T}) downstream swap regret while the exponent of k in the regret bound and the exponent of T in the running time both grow with dimension. For arbitrary dimension d, we give a forecasting algorithm that guarantees ilde{O}(dsqrt{kT}) swap regret, assuming the forecaster knows an upper bound k on the number of actions available to any downstream agent, albeit with a much longer runtime. This improves upon previous high dimensional guarantees that had ilde{O}(T^{2/3}) dependence and required additional behavioral assumptions.

Source: arXiv cs.LG | 2026-06-30