Learning with Simulators: No Regret in a Computationally Bounded World

Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin

TL;DR

This paper introduces a novel framework called simulatable processes to break through a foundational barrier in machine learning theory: the assumption that data must be independent and identically distributed (i.i.d.). By giving the learner access to a data simulator, the authors prove that it is possible to achieve optimal, VC-dimension-dependent learning guarantees even for highly dependent sequential data. Furthermore, they demonstrate that if nature is computationally bounded, a single universal algorithm can successfully learn against any polynomial-time samplable process.

What Problem Does This Paper Address?

The bedrock of classical learning theory (like the PAC framework) is the assumption of independence—the idea that your training data points don't influence one another. However, real-world data is full of rich, complex dependencies over time: today's weather affects tomorrow's, and an LLM's next token depends heavily on the entire preceding prompt.

When we try to learn under arbitrary dependencies using standard online learning, we run into severe roadblocks. Robustness against adversarial, dependent data comes at a massive cost: even simple function classes (like thresholds) become completely unlearnable, or require exponential computational time.

The authors address this gap by proposing a philosophical shift inspired by the natural sciences and modern generative AI: while the world's data-generating processes are complex and dependent, they are often governed by efficient mechanisms that we can simulate (e.g., climate models, physics simulators, or generative models). They ask: If a learner has access to a simulator that approximates the data-generating process, can we recover the statistical and computational efficiency of classical learning theory?

Methods

The authors formalize a framework where the learner can query a simulator ($P$) that is close in Kullback-Leibler (KL) divergence to the true data-generating distribution ($P^*$). They analyze two distinct types of simulator access:

  1. Unconditional Simulators: The learner can only sample full, independent trajectories of data. To handle this, they propose Algorithm 1 (MultiCover). It draws samples from a mixture of the simulator's marginals to construct a multi-scale "improper cover" of the Vapnik-Chervonenkis (VC) function class, and then applies an exponential weights algorithm over this cover.
  2. Conditional Simulators: A more powerful oracle where the learner can sample the next data point given a specific prefix history ($P(\cdot | x_{1:t})$)—akin to how autoregressive language models generate text. For this, they design Algorithm 2 (Log-MGF relaxation with epoching). This algorithm uses a minimax relaxation technique to directly control the moment generating function (MGF) of the regret, combined with an "epoching" strategy that prevents approximation errors from compounding over time.

For the grand challenge of learning against an unknown but computationally bounded nature, the authors use tools from algorithmic information theory. They construct a universal simulator based on time-bounded Kolmogorov complexity that mathematically "dominates" any process samplable in polynomial time.

Datasets

No empirical datasets were used in this work; this is a purely theoretical paper focused on proving statistical and computational learning guarantees.

Key Insights and Ideas

  • Bypassing the Littlestone Barrier: In adversarial online learning, learnability is dictated by the Littlestone dimension, which is often infinite for simple classes. This paper shows that simulator access drops the statistical complexity back down to the VC dimension, effectively matching the statistical ease of the i.i.d. setting.
  • The Conditional Superpower: There is a massive computational and statistical chasm between unconditional and conditional simulators. Conditional sampling allows the learner to transition from exponential-time realizable learning to efficient, polynomial-time agnostic learning (where the ground truth doesn't have to perfectly reside in the hypothesis class).
  • Learning Without Mixing: Historically, learning from dependent sequences (like Markov chains) required assuming the chain "mixes" quickly (i.e., forgets its past). By leveraging conditional simulators, this framework completely bypasses mixing-time assumptions, enabling learning even in non-mixing Linear Dynamical Systems (LDS) and Glauber dynamics.
  • Predicting vs. Learning the Process: Under widely held cryptographic assumptions, it is impossible to explicitly learn or evaluate the density of a universal distribution. However, this paper provides an elegant workaround: we don't need to learn the simulator's internal density to predict well under it; approximate sampling is entirely sufficient.

Key Results

The paper maps out a complete taxonomy of the statistical (regret) and computational (runtime) trade-offs between unconditional and conditional simulators, as summarized in Table 1:

Summary of regret and runtime bounds under unconditional and conditional simulators.
  • Conditional Agnostic Learning: With a conditional simulator, Algorithm 2 achieves an optimal agnostic regret bound of $O(\sqrt{dT(1 + \text{KL}(P^* \parallel P))})$ in $\text{poly}(T)$ time.
  • Unconditional Hardness: The authors prove a tight lower bound showing that in the agnostic setting, learning with only unconditional samples is statistically impossible, resulting in linear $\Omega(T)$ regret.
  • Universal Learning: If nature generates data using any unknown polynomial-time process $p(T)$, a single algorithm can achieve sublinear regret in $\text{poly}(T^d, p(T))$ time, with the rate gracefully controlled by the process's time-bounded Kolmogorov complexity.

Limitations and Future Work

  • Realizability in Bounded Nature: The universal algorithm designed to compete against any polynomial-time samplable process currently requires a realizable setup (the true labeling function must fall exactly within the VC class). Extending this universal guarantee to the agnostic setting remains an open challenge.
  • Site Observability Constraints: When applying the framework to Glauber dynamics (Ising models), the authors assume "site observability"—meaning the learner knows which node the system attempted to update, even if the state didn't change. Eliminating this assumption is a noted direction for future work.
  • The Cryptographic Bottleneck of Universal Sampling: While the universal algorithm is polynomial-time relative to the simulator, actually implementing conditional sampling from a universal Kolmogorov distribution is cryptographically hard (equivalent to breaking one-way functions). Therefore, practical applications must rely on domain-specific simulators (like LDS or autoregressive models) rather than the universal wrapper.

Summary updated

Abstract

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.
BibTeX
@inproceedings{voitovych2026learning,
  author = {Sasha Voitovych and Abhishek Shetty and Noah Golowich and Alexander Rakhlin},
  title = {{Learning with Simulators: No Regret in a Computationally Bounded World}},
  booktitle = {Conference on Learning Theory},
  year = {2026},
}
Figure