🤖 machine learning

Improved Multi-Dimensional Forecasting for Swap Regret

This paper presents improved polynomial-time forecasting algorithms that achieve sublinear swap regret for downstream agents with unknown objectives across both low-dimensional and arbitrary-dimensional outcome spaces, significantly outperforming prior bounds in terms of regret dependence on the number of actions and time while avoiding exponential runtimes.

Original authors: Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Chido Onyeze, Erald Sinanaj, Eva Tardos

Published 2026-06-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Chido Onyeze, Erald Sinanaj, Eva Tardos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a weather forecaster. Every day, you give a prediction about the weather (e.g., "It will be sunny with a 20% chance of rain"). But you aren't just predicting for yourself; you are predicting for a massive crowd of people, each with their own unique goals.

The Commuter wants to avoid traffic.
The Farmer wants to know if they need to water their crops.
The Picnic Planner wants to know if they need a tent.

Everyone looks at your forecast and makes the best decision they can based on that information. The problem is: How do you make a single forecast that is "fair" and "accurate" for everyone, even though you don't know what their specific goals are?

This paper is about building a super-forecaster that guarantees no one in the crowd will look back at the end of the year and say, "I wish I had made different choices on the days I followed that forecast."

The Core Problem: "Swap Regret"

The authors use a concept called Swap Regret. Let's break it down with a simple analogy:

Imagine you are the Commuter. You followed the forecaster's advice for 100 days. On 50 of those days, the forecaster said "Take Route A," and you did.

Low Regret: You look back and realize, "Actually, on those 50 days, if I had taken Route B instead, I would have saved 10 minutes."
Swap Regret: This is a stricter test. It asks: "Is there any other route (C, D, or E) that would have been better than Route A on all those specific days?"

If your "Swap Regret" is low, it means your decisions were robust. You didn't just get lucky; you made the right choice for the information you had, and no other option would have consistently beaten your choice.

The paper's goal is to create a forecaster that keeps this regret low for everyone in the crowd simultaneously, even if the crowd has thousands of different people with thousands of different choices.

The Old Way vs. The New Way

The Old Way (The "Brute Force" Approach):
Previous methods tried to predict perfectly for every possible scenario. Imagine trying to draw a map that covers every single possible path a driver could take.

The Problem: In a simple 2D world (like a flat map), this was already hard. In a complex, multi-dimensional world (like a 3D maze or a high-dimensional data space), the number of possible paths explodes. Old algorithms either took too long to run (exponential time) or gave up and gave a "good enough" but not great guarantee.

The New Way (The "Smart Geometry" Approach):
The authors realized they didn't need to map every single path. They needed to understand the shape of the decision-making process.

1. The Low-Dimensional Breakthrough (2D)

Think of the prediction space as a flat sheet of paper.

The Insight: The authors realized that the "zones" where people choose different actions (like "Take Route A" vs. "Take Route B") are actually simple geometric shapes (polygons).
The Trick: Instead of worrying about the whole complex polygon, they broke these shapes down into simple triangles.
The Result: Just like you can build any complex shape out of a few triangles, they showed that the forecaster only needs to keep track of a manageable number of triangles. This allowed them to create a fast, polynomial-time algorithm that guarantees the best possible performance (matching the theoretical limit) for 2D problems.

2. The High-Dimensional Breakthrough (3D and up)

Now, imagine the prediction space is a giant, multi-dimensional cube. The shapes get incredibly complex, and breaking them into triangles becomes impossible (you'd need too many).

The Insight: Instead of breaking the shapes apart, they looked at the whole picture (the "partition"). They asked: "How many different ways can this whole space be divided into decision zones?"
The Trick: They proved that even though the space is huge, the number of distinct ways people can divide it up is actually much smaller than you'd think. It's like realizing that while there are infinite ways to paint a wall, there are only a finite number of ways to paint it using a specific set of stencils.
The Result: They built an algorithm that tracks these "divisions" rather than individual shapes. While this algorithm is slower (it takes a long time to compute), it guarantees a much better result than before, scaling linearly with the complexity of the world.

The Big "What If" (The Limit)

The paper also asks a fascinating question: "Can we make this perfect, regardless of how many choices people have?"

In simple 1D problems (like predicting a single number), we know we can do this. But in higher dimensions, the authors suspect the answer is no.

They draw a connection to Calibration.

Analogy: If you say "It will rain 50% of the time," and it actually rains 50% of the time, you are "calibrated."
The Link: They show that if you could eliminate the dependence on the number of choices (k) in their high-dimensional algorithm, it would solve a massive, unsolved math problem about calibration in high dimensions. Since that math problem is considered extremely hard (and likely impossible with current methods), it suggests that their current solution (which depends on the number of choices) is probably the best we can do for now.

Summary

The Goal: Build a public forecaster that helps everyone make good decisions, even if we don't know their specific goals.
The Innovation: They used geometry to simplify the problem.
- In 2D, they broke complex shapes into triangles to make the algorithm fast and perfect.
- In High Dimensions, they counted the possible "maps" of decision zones to get a better guarantee than ever before, even if it takes longer to compute.
The Limit: They proved that getting rid of the "number of choices" factor in high dimensions would require a breakthrough in a completely different area of math (calibration), suggesting their current solution is likely near-optimal.

In short, they built a smarter, faster, and more robust "weather forecaster" for decision-makers, using the geometry of the world to cut through the complexity.

Technical Summary: Improved Multi-Dimensional Forecasting for Swap Regret

Problem Statement

The paper addresses the problem of designing a public forecasting algorithm for an arbitrary number of downstream agents with unknown objectives. In this setting, an adaptive adversary determines the "state of the world" $y_t \in C$ (where $C \subseteq \mathbb{R}^d$ is a convex, compact prediction space) at each time step $t=1, \dots, T$ . A forecaster must issue a prediction $\hat{y}_t \in C$ before observing $y_t$ . Downstream agents, possessing utility functions $u: A \times C \to [0,1]$ that are affine in the outcome, best-respond to the forecast $\hat{y}_t$ as if it were the true state.

The goal is to construct a single forecaster that guarantees sublinear Swap Regret simultaneously for all possible downstream agents, regardless of their specific utility functions or action sets. Swap Regret is a stronger metric than External Regret; it ensures that an agent who best-responds to the forecasts would not wish to have swapped their chosen action for any other fixed action on the days they took that action.

The paper specifically investigates the trade-offs between the dimension of the outcome space ( $d$ ), the number of actions available to agents ( $k$ ), the time horizon ( $T$ ), and the computational efficiency of the forecaster.

Methodology

The authors build upon the framework established by Roth and Shi (2024) and Noarov et al. (2025), which posits that downstream swap regret is controlled by the conditional bias on "best response regions." A best response region $S_{u,a}$ is the set of predictions for which action $a$ is optimal. The core strategy is to minimize the accumulated bias $\beta(S) = \|\sum_{t: \hat{y}_t \in S} (\hat{y}_t - y_t)\|_\infty$ on these regions.

The paper proposes two distinct algorithmic approaches depending on the dimensionality of the prediction space:

1. Low-Dimensional Approach (Triangulations)

For low dimensions (specifically $d=2$ , and generally constant $d$ ), the authors exploit the geometric structure of best response regions.

Geometric Characterization: They observe that for agents with $k$ actions, best response regions are convex polytopes with at most $k$ facets (plus boundary constraints).
Triangulation: Using the Upper Bound Theorem from convex geometry, they show that any such polytope can be decomposed into a bounded number of simplices (triangles in 2D). Specifically, the total number of simplices required to triangulate all $k$ best response regions is $O(k^{\lceil d/2 \rceil})$ .
Algorithm: Instead of controlling bias on all possible convex sets (which is computationally intractable), the forecaster controls bias only on the family of simplex-induced subsets of a discretized prediction grid. The number of such subsets is polynomial in the grid size.
Implementation: The algorithm instantiates the unbiased prediction algorithm of Noarov et al. (2025) on this smaller family of simplex-induced sets.

2. High-Dimensional Approach (Counting Partitions)

For arbitrary dimensions $d$ , the geometric decomposition approach becomes inefficient as the number of simplices grows exponentially.

Partition Enumeration: The authors shift perspective to control the total bias across entire best response partitions. A partition is a mapping of the discretized prediction space to the set of actions $[k]$ .
Complexity Analysis: They prove that while there are infinitely many utility functions, the number of distinct partitions realizable by affine utilities on a discretized grid is bounded. By modeling utilities as points in a parameter space $\mathbb{R}^{k(d+1)}$ and analyzing the hyperplanes defined by $u(a, \hat{y}) = u(b, \hat{y})$ , they bound the number of realizable partitions $|D_k(C_\epsilon)|$ roughly as $T^{kd^2}$ .
Multi-Objective Optimization: The total bias for a partition is encoded as the maximum of $(2d)^k$ linear loss objectives. The problem is reduced to a multi-objective optimization setting (using Lee et al., 2022) where the forecaster minimizes the maximum loss across all realizable partitions simultaneously.

Key Contributions and Results

1. Low-Dimensional Guarantees ( $d=2$ )

The paper presents a polynomial-time algorithm for $d=2$ that guarantees:
$\text{MDSR}(k) \leq \tilde{O}(\sqrt{kT})$

Improvement: This matches the optimal bound for a single agent running a no-swap-regret algorithm (Blum and Mansour, 2007) up to logarithmic factors.
Efficiency: It improves upon the previous best bound of $\tilde{O}(kT^{5/8})$ by Roth and Shi (2024), which required exponential runtime in $T$ . The new algorithm runs in polynomial time with respect to $T$ .
Generality: The result holds for any number of downstream agents and any $k$ , providing a bound on the expectation of the maximum swap regret, a stronger guarantee than bounding the maximum of expected regrets.

2. High-Dimensional Guarantees (Arbitrary $d$ )

For arbitrary dimension $d$ , assuming the forecaster knows an upper bound $k$ on the number of actions:
$\text{MDSR}(k) \leq \tilde{O}(d\sqrt{kT})$

Improvement: This improves upon the previous high-dimensional guarantee of $\tilde{O}(T^{2/3})$ by Roth and Shi (2024), which relied on the assumption that agents "smoothly" respond rather than strictly best-responding.
Trade-off: This result comes at the cost of computational efficiency; the algorithm requires enumerating an exponential number of partitions, resulting in a runtime that is not polynomial in $T$ for fixed $d$ .

3. Lower Bound and Calibration Connection

The paper investigates whether the dependence on $k$ (the number of actions) is necessary in higher dimensions.

Connection to Calibration: The authors link Maximum Downstream Swap Regret to Expected Calibration Error (ECE). They show that if a forecaster could achieve a swap regret bound of $\tilde{O}(T^{1-\delta})$ independent of $k$ in high dimensions, it would imply a breakthrough result for high-dimensional calibration (specifically, an ECE of $\tilde{O}(T^{1-\delta/2})$ ).
Implication: Since current lower bounds for high-dimensional calibration suggest such improvements are unlikely, the paper argues that the dependence on $k$ in the swap regret bound is likely unavoidable in dimensions $d > 1$ .

Significance and Claims

The paper claims to provide the first efficient algorithm that achieves near-optimal swap regret rates for downstream agents in two-dimensional outcome spaces, matching the theoretical limits known for single-agent settings. It resolves the computational inefficiency of prior high-dimensional approaches by offering a polynomial-time solution for $d=2$ .

For higher dimensions, the work establishes the first $\tilde{O}(\sqrt{T})$ dependence on the time horizon for agents who strictly best-respond, removing the need for "smooth response" behavioral assumptions used in prior work.

The authors modestly note that while their high-dimensional algorithm is theoretically sound, it is computationally inefficient. They identify the development of an oracle-efficient version for high dimensions as a primary open question. Furthermore, they suggest that removing the dependence on the number of actions $k$ in higher dimensions would require significant new progress in the theory of multidimensional calibration, implying that their current bounds are likely close to the fundamental limits of the problem.