Solomonoff induction learns from partial computable predictions
Solomonoff Induction with Reflective Oracles
Computational Complexity
Summary
Predicting the future often involves guessing the rules that generate data. This paper studies a version of Solomonoff induction—a method for prediction—that can handle its own uncertainty using something called reflective oracles. The authors show this predictor can learn even when other prediction methods only describe part of what’s happening. They also demonstrate fairness properties in the predictions and explore whether all prediction rules can be computed from the predictor’s own outputs.
What this means in practice
- •For algorithm designers: Design predictive algorithms that remain optimal even when competitors model only partial aspects of data sources.
- •For ai safety engineers: Use reflective oracle frameworks to build predictors capable of reasoning about their own predictions and biases.
A theory result. No direct application yet.
Authors
Damini Kusum
Abstract
We study predictive properties of a reflective variant of Solomonoff induction formulated using reflective oracles (Fallenstein et al. 2015, Wyeth et al. 2025). We show that the resulting optimal predictor succeeds against computable predictive strategies that specify only part of the data-generating process. The argument relies on the fact that hypotheses computable from the predictor's own conditional probabilities remain within the reflective hypothesis class. In particular, the predictor learns incomplete models specified by computable interval restrictions on next-bit probabilities. We also establish weighted forms of unbiasedness and calibration. Finally, we discuss whether an optimal predictor's conditional probabilities suffice to compute every hypothesis in the reflective class.