Learning with Simulators: No Regret in a Computationally Bounded World
For learning theorists, this work broadens the PAC model to handle strongly dependent data by leveraging simulators, offering a new theoretical foundation for computationally bounded learning.
This paper introduces the framework of simulatable processes, where the learner has access to a simulator approximating the data distribution, and shows that this recovers learning guarantees (error bounds depending on VC dimension) comparable to the classical i.i.d. setting. The framework also yields a single algorithm that learns any VC class under all processes samplable in bounded polynomial time, with regret controlled by time-bounded Kolmogorov complexity.
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.