High-Dimensional Prediction for Sequential Decision Making

High-Dimensional Prediction for Sequential Decision Making

Speakers: Ramya Ramalingam, PhD Student, University of Pennsylvania; Georgy Noarov; Aaron Roth; Stephan Xie

Conference: ICML 2025

YouTube: https://slideslive.com/39044056

Overview

This talk introduces a novel framework for high-dimensional prediction in sequential decision-making, particularly in online adversarial environments. Presented by Ramya Ramalingam, a PhD student at the University of Pennsylvania, alongside co-authors Georgy Noarov, Aaron Roth, and Stephan Xie, the work addresses a fundamental challenge in modern machine learning systems: how to generate predictions that are not only accurate but also trustworthy and useful for downstream agents making critical decisions based on these forecasts. The core innovation lies in moving beyond traditional notions of calibration, which become computationally and statistically intractable in high-dimensional settings, towards a more generalized and efficient concept termed event unbiasedness.

The problem setting involves a system that receives a sequence of incoming data over time, using it to forecast future states of the world represented by high-dimensional vectors. These predictions are then passed to one or more agents who use them to inform their actions, aiming to maximize their utility. The central goal of this research is to ensure that agents can reliably act on these predictions as if they were perfectly accurate, thereby achieving strong downstream performance guarantees. This is crucial in applications ranging from online routing, where predictions of network congestion inform route choices, to complex combinatorial optimization problems with exponentially large action spaces.

The significance of this work stems from its ability to bridge the gap between predictive accuracy and decision-theoretic utility in complex, real-world scenarios. By proposing event unbiasedness, the authors offer a computationally efficient alternative to traditional calibration, unlocking powerful guarantees for a wide array of downstream tasks. This framework promises to enhance the reliability and performance of AI systems operating in dynamic environments, providing a robust foundation for building predictive models that truly empower intelligent agents.

Background

▶ Watch: Introduction to high-dimensional sequential prediction (0:00)

The pervasive challenge in online adversarial environments is to make predictions about future states that are not only accurate but also actionable and trustworthy for downstream decision-making agents. Imagine a scenario like the online routing problem, a motivating example presented in the talk: the "state of the universe" could be a high-dimensional vector representing latencies across a vast road network, while an agent's "action" might be choosing an optimal path from home to work. If an agent knew the true state of the network every day, their task would be simple: best-respond by selecting the path that maximizes their utility (e.g., minimizes travel time). However, in the absence of perfect information, agents must rely on predictions, denoted as S_hat. The objective then becomes to generate S_hat such that agents can best-respond to these predictions and achieve a utility outcome similar to what they would have achieved had they known the true state S.

A well-established condition for making predicted outcomes indistinguishable from true outcomes, at least on average, is calibration. Formally, online calibration requires that if the full sequence of predictions is partitioned into subsequences based on specific predictions made, then these predictions should be unbiased with respect to the true sequence of states across all such subsequences. Calibrated forecasts are known to possess extremely powerful decision-theoretic properties, as they ensure that best-response functions are optimal over the entire collection of utility functions that are linear in the state argument. This makes calibration a highly desirable property for predictive models feeding into decision systems.

However, the efficacy of traditional calibration diminishes drastically when the dimensionality of the state vector increases. The core difficulty lies in the exponential growth of potential prediction values. As the state vector becomes high-dimensional, the number of distinct conditioning events required for fine-grained calibration explodes, rendering the task statistically and computationally intractable. Collecting enough data for each specific prediction value to ensure unbiasedness becomes impossible, and the computational overhead of maintaining calibration across an exponentially growing set of conditions becomes prohibitive. This limitation has historically hindered the application of calibration to complex, high-dimensional prediction problems prevalent in modern AI/ML systems, where state representations often involve thousands or millions of features. The existing problem, therefore, is a fundamental trade-off: the desire for strong decision-theoretic guarantees offered by calibration versus the computational and statistical realities of high-dimensional data. This work aims to circumvent this issue by redefining the scope of unbiasedness.

Key Findings

▶ Watch: Challenges of online calibration in high dimensions (2:00)

The central insight of this research is that while traditional calibration demands unbiasedness over an extremely fine-grained set of conditioning events (i.e., conditioning on all possible predictions), this level of granularity is often unnecessary when the primary interest lies in how decisions affect agent utility. The authors propose that it is sufficient to satisfy this unbiasedness property on a much smaller, carefully chosen collection of events, specifically those that are polynomial in the dimensionality of the state vector. This key idea leads to the definition of event unbiasedness, a coarser and more generalized notion of calibration that is efficiently achievable.

The core contribution is an algorithm that achieves a bias which scales logarithmically with the dimensionality of the state vector (D), the size of the event family (|F|), and the square root of the incidence of the event (essentially, the expected number of times an event appears in the transcript). Crucially, the runtime of this algorithm is polynomial in the number of events, making it practical for event families of polynomial size. This provides a significant efficiency improvement over traditional calibration methods in high-dimensional settings.

The power of event unbiasedness is demonstrated through its applicability to a diverse set of problems, yielding strong guarantees:

• Online Combinatorial Optimization: The framework enables real-time forecasts for problems like online routing. By designing a relatively small event family, the algorithm can achieve conditional regret guarantees that scale with sqrt(T), even for agents with exponentially large action spaces with respect to the state vector dimension. This generalizes existing notions of regret, including external, internal, swap, and groupwise regret, by allowing conditioning on subsequences that can even depend on the prediction itself.
• Online Multi-Calibration: For single-dimensional forecasting, event unbiasedness, when combined with snapping predictions to a discretized grid, provides a new efficient method for online multi-calibration. It achieves a calibration error on the order of T^(2/3), which is a novel result and matches the best efficient rate for vanilla online calibration, a significantly simpler problem. This represents the first efficient online multi-calibration algorithm with this specific rate.
• Multi-Agent Coordination and Other Applications: The framework also extends to ensuring no swap regret for multiple downstream agents simultaneously, facilitating online uncertainty quantification for multi-class classification, generating conformal-style prediction sets with conditional coverage, and enabling prior-free mechanism design and agreement protocols.

In essence, the key findings revolve around the introduction of event unbiasedness as a practical and powerful alternative to traditional calibration, providing a unified framework to achieve a wide range of strong decision-theoretic guarantees in high-dimensional, online settings with provable efficiency.

Technical Deep Dive

▶ Watch: Defining 'Event Unbiasedness' for efficient prediction (3:05)

The technical foundation of this work lies in the formal definition of "events" and how an algorithm can maintain unbiasedness with respect to a defined family of such events. The setting involves a sequence of rounds where, at each round T, the system observes a new context X_T. Based on X_T and potentially past observed states S and contexts, an event unbiased algorithm predicts a new state S_hat_T. This prediction is then provided to downstream agents, who use it to determine their actions. Finally, the true state S_T is observed, and the process repeats.

An event E is formally defined as a mapping from a (context, prediction) pair (X, S_hat) to a value between zero and one, i.e., E: (X, S_hat) -> [0, 1]. This value essentially defines the "inclusion" or "exclusion" of a specific round into a subsequence. If E(X_T, S_hat_T) is 1, the event is active for that round; if 0, it's inactive. Values between 0 and 1 allow for probabilistic or fractional inclusion. The key is that an event selects a subsequence of rounds over the full transcript based on specific criteria that can depend on both the context observed and the prediction made.

The bias of a specific event E is then defined as the maximum bias between the predicted and true states over all coordinates of the high-dimensional vector, calculated over the subsequence of days for which that specific event E is active. More precisely, for an event E and a coordinate j, the bias could be quantified as |E[S_hat_T[j] | E is active] - E[S_T[j] | E is active]|. The overarching goal of the event unbiased algorithm is to keep this bias low for any arbitrary definition-defined set of events.

The main result is an algorithm that achieves a bias scaling with O(log(D |F|) sqrt(incidence)), where:

• D is the dimensionality of the state vector.
• |F| is the size of the event family (the number of distinct events being tracked).
• incidence refers to the expected size of an event, or the number of times it appears in the transcript. This term captures how frequently an event is active.

Crucially, the runtime of this algorithm is polynomial in |F|. This efficiency is key, as it allows for tracking a polynomially sized family of events without incurring the exponential computational cost associated with full calibration in high dimensions. The transcript does not detail the specific algorithmic mechanics (e.g., a specific online learning algorithm like Follow the Perturbed Leader or Hedge variants adapted for this setting), but the stated scaling properties are central to its practical utility.

The power of event unbiasedness stems from the careful design of the event family. Different choices of event families lead to different decision-theoretic guarantees:

• Conditional Regret for Online Combinatorial Optimization: For problems like online routing, the state S might be a vector of n latencies, and an agent's action space (e.g., all possible paths) could be exp(n). Traditional regret notions often struggle here. The framework tackles this by constructing a relatively small event family F such that unbiasedness over F translates directly into Xi conditional regret. This means achieving external regret on each subsequence Xi within the family. What makes this particularly powerful is that these subsequences Xi are allowed to depend on the predictions themselves. For example, an event could be "the prediction suggests taking highway A" or "it's the weekend and the predicted congestion is high." This generalizes most existing regret notions. The algorithm guarantees sqrt(T) regret over this potentially exponentially large action space.

• Online Multi-Calibration: This is a stronger form of calibration that demands calibrated forecasts conditioned on a sequence of given groups, which are subsets of the context space. For single-dimensional forecasting, the approach involves asking for event unbiasedness with respect to a small collection of events, followed by snapping these predicted points to their closest neighbor in a discretized grid. This combination yields a calibration error (measured in the L1 norm) of O(T^(2/3)). This rate is significant because it is the first efficient online multi-calibration algorithm to achieve it, matching the best efficient rate known for vanilla online calibration, a much simpler problem. Existing algorithms for higher-dimensional calibration typically achieve much worse rates, often T^(T/(T+1)), which grows very large with T.

The ability to define custom event families provides a versatile tool for tailoring predictive systems to specific decision-making goals and fairness constraints, moving beyond a one-size-fits-all approach to calibration.

Experimental Setup & Results

▶ Watch: Application: Online routing with conditional regret (6:00)

This talk primarily focuses on the theoretical framework, algorithmic properties, and the derived theoretical guarantees rather than presenting specific empirical results from a controlled experimental setup involving particular datasets, hardware, or detailed ablations. The "results" discussed are primarily the provable bounds and performance guarantees achieved by the proposed event unbiased algorithm under various conditions.

The key results can be summarized as follows:

• Bias Guarantees: The core algorithm guarantees a maximum bias that scales logarithmically with the state dimensionality (D) and the size of the event family (|F|), and with the square root of the event incidence. Specifically, the bias is O(log(D |F|) sqrt(incidence)). This theoretical bound is crucial as it demonstrates the computational tractability and statistical efficiency of the approach in high-dimensional settings, where traditional calibration fails.
• Runtime Complexity: The algorithm's runtime is polynomial in the number of events (|F|). This ensures that if the event family is polynomially sized (as is typically desired), the algorithm remains efficient.
• Online Combinatorial Optimization: For problems in this class, the framework guarantees Xi conditional regret that scales with O(sqrt(T)), where T is the number of rounds. This is achieved over potentially exponentially large action spaces, a significant achievement for online decision-making. The ability to achieve this with a carefully designed, relatively small event family underscores the efficiency of the approach.
• Online Multi-Calibration: For single-dimensional forecasting, the method provides an efficient online multi-calibration algorithm with a calibration error (L1 norm) of O(T^(2/3)). This rate is noteworthy because it is the first time such a rate has been achieved efficiently for multi-calibration, and it matches the best known efficient rate for the simpler problem of vanilla online calibration. This result highlights a substantial improvement over existing higher-dimensional calibration algorithms, which often yield much larger error rates (e.g., T^(T/(T+1))).

While the talk does not delve into specific datasets like ImageNet, CIFAR-10, or specific hardware like NVIDIA A100 GPUs or Google TPUs, the theoretical guarantees presented are foundational. They establish the algorithm's performance characteristics in terms of bias, regret, and calibration error, which are critical for understanding its potential applicability and efficiency in real-world systems. The absence of specific experimental benchmarks is common in talks presenting novel theoretical frameworks and their derived properties, with empirical validation often following in subsequent work or more detailed publications.

Practical Implications

▶ Watch: Event unbiasedness unifies various conditional regret notions (7:00)

The framework of event unbiasedness holds significant practical implications for various stakeholders involved in developing, deploying, and utilizing AI/ML systems for sequential decision making:

• For Practitioners and Infrastructure Teams: The ability to provide trustworthy predictions with strong, provable guarantees in high-dimensional, online adversarial environments is a game-changer. Infrastructure teams can now deploy predictive services with greater confidence, knowing that the predictions will lead to predictable and bounded outcomes for downstream agents. This reduces the risk associated with deploying ML models in critical systems where miscalibrated or biased predictions could lead to suboptimal decisions, inefficiencies, or even fairness issues. The polynomial runtime with respect to the event family size means these guarantees can be achieved efficiently, making the approach scalable for production systems.

• For Model Builders and Data Scientists: This work offers a powerful lens for designing and evaluating predictive models. Beyond traditional metrics like accuracy or F1-score, model builders can now explicitly optimize for decision-theoretic utility and unbiasedness over specific, relevant events. This encourages a more holistic approach to model development, where the downstream impact of predictions is considered from the outset. For instance, in an online routing system, model builders can ensure that their congestion forecasts are unbiased not just overall, but specifically for "rush hour periods" or "highway segments," which are critical decision contexts for drivers. The flexibility to define custom event families allows for tailoring predictive models to specific business objectives or regulatory requirements, such as ensuring fairness across different demographic groups (e.g., groupwise regret).

• For Deployers and System Architects: The framework provides tools for addressing complex multi-agent coordination problems and systems with exponentially large action spaces. In scenarios where multiple agents rely on a shared predictive system (e.g., multiple drivers using the same traffic prediction service), event unbiasedness can ensure no swap regret across these agents, leading to more stable and equitable system-wide outcomes. For systems dealing with combinatorial optimization, the ability to achieve sqrt(T) conditional regret for exponentially large action sets means that complex decision problems can be tackled efficiently, allowing for robust performance even when agents have vast choices. This capability is crucial for applications in logistics, resource allocation, and dynamic pricing.

Tradeoffs and Limitations:

While powerful, the practical application of event unbiasedness comes with certain tradeoffs and considerations:

1. Event Family Design: The efficacy of the framework heavily relies on the careful and thoughtful design of the event family. Choosing the "right" events is crucial for achieving specific guarantees and addressing particular concerns (e.g., fairness, specific performance conditions). This requires domain expertise and a clear understanding of the downstream decision problem. A poorly chosen or overly sparse event family might not capture all relevant biases, while an excessively large family, though polynomially bounded, could still incur significant computational overhead.
2. Computational Cost for Large Event Families: Although the runtime is polynomial in the number of events, for extremely large polynomial families, the computational cost can still be substantial. This highlights a practical constraint on the complexity and granularity of the events that can be efficiently tracked.
3. Multi-Step Prediction Complexity: As noted in the Q&A, extending the framework to multi-step predictions (forecasting multiple future states simultaneously) would likely increase the number of events requiring calibration. This could lead to higher computational demands, requiring careful management of the event family size.
4. Implicit Algorithm Details: The talk focuses on the theoretical properties and outcomes of the algorithm rather than its explicit implementation details. Practitioners adopting this framework would need to refer to the full paper for specific algorithmic constructs (e.g., how the online learning procedure is instantiated to maintain unbiasedness across events).

In summary, event unbiasedness offers a robust and theoretically grounded approach to building more trustworthy and useful predictive systems in high-dimensional, dynamic environments. Its practical implications span improved system reliability, enhanced model design, and more effective coordination of complex multi-agent systems, albeit with the critical requirement of judicious event family selection.

Key Takeaways

• Event unbiasedness is a novel, generalized notion of calibration designed for high-dimensional predictive forecasting in sequential decision-making.
• It addresses the computational and statistical intractability of traditional calibration in high-dimensional settings by focusing on unbiasedness over a polynomial-sized family of relevant events rather than all possible predictions.
• The proposed algorithm achieves a bias that scales logarithmically with state dimensionality and event family size, with a runtime polynomial in the number of events, making it efficient and scalable.
• The framework enables strong decision-theoretic guarantees across diverse applications, including conditional regret for online combinatorial optimization (even with exponentially large action spaces) and no swap regret for multiple downstream agents.
• It provides the first efficient online multi-calibration algorithm for single-dimensional forecasting, achieving a competitive T^(2/3) calibration error rate, matching the best known rate for vanilla online calibration.
• This work significantly enhances the trustworthiness and utility of AI/ML predictions, allowing downstream agents to reliably act on forecasts and achieve provable performance guarantees in dynamic, adversarial environments.

About the Speaker(s)

Ramya Ramalingam is a PhD student at the University of Pennsylvania. Her research interests, as demonstrated by this talk, lie in the areas of machine learning theory, particularly in developing robust and trustworthy predictive frameworks for sequential decision-making in online and adversarial environments.

The work presented is a collaborative effort with Georgy Noarov, Aaron Roth, and Stephan Xie. Aaron Roth is notably Ramya's advisor, suggesting a strong academic lineage and expertise in the theoretical underpinnings of machine learning and algorithmic fairness. While specific affiliations for Noarov and Xie are not detailed in the transcript, their contribution is integral to the development of this sophisticated framework.