A Model-Free Universal AI

Abstract

In general reinforcement learning, all established optimal agents, including AIXI, are model-based, explicitly maintaining and using environment models. This paper introduces Universal AI with Q-Induction (AIQI), the first model-free agent proven to be asymptotically $\epsilon$-optimal in general RL. AIQI performs universal induction over distributional action-value functions, instead of policies or environments like previous works. Under a grain of truth condition, we prove that AIQI is strong asymptotically $\epsilon$-optimal and asymptotically $\epsilon$-Bayes-optimal. We also apply our novel proof techniques to show asymptotic $\epsilon$-optimality of Self-AIXI without any ad-hoc assumptions. Our results significantly expand the diversity of known universal agents.

42nd Conference on Uncertainty in Artificial Intelligence (UAI 2026)

Topics & keywords