Authors: Yegon Kim, Juho Lee (Graduate School of AI, KAIST).
URL: https://arxiv.org/pdf/2602.23242
Abstract (verbatim gist): Prior universal optimal agents in general RL (including AIXI) are model-based—they infer and use an explicit environment model. This paper introduces Universal AI with Q-Induction (AIQI), an ε-greedy on-policy agent that performs universal induction over return-predictors (objects akin to distributional Q-values), not over policies or environments. Under a grain of truth condition (self-referential, as in prior universal-AI work), AIQI is proved strong asymptotically ε-optimal and asymptotically ε-Bayes-optimal in the mixture environment ξ. The paper also proves AIQI is not self-optimizing off-policy (Theorem 4.10), contrasting with AIXI’s self-optimization story.
AIQI ((\hat\pi_{\psi}^{H,M,N,\tau})) maintains a Bayesian mixture (\psi) over phase-(n) return-predictors (\phi \in \mathcal{P}_n). Each (\phi) predicts the next discretized (H)-step return (z_t \in \mathcal{Z} = {0, 1/M, \ldots, (M-1)/M}) from an periodically augmented history: returns (z_i) are inserted only at indices (i \equiv n \pmod N) (with (N \ge H)) so that all rewards needed to compute past augmented returns are already observed—a construction that avoids the circularity of needing future rewards to label past returns.
The unified predictor (\psi(z_t \mid h_{<t}, a_t)) routes to the mixture (\psi_n) for phase (n = t \bmod N) on the valid augmentation (\mathrm{aug}n(h{<t})).
Action selection: For each (a), form an estimated Q-value as the posterior mean of the discretized return, [ \hat Q(h_{<t}, a) = \sum_{z \in \mathcal{Z}} z \cdot \psi(z \mid h_{<t}, a), ] then ε-greedy exploration: with prob. (1-\tau) play (\arg\max_a \hat Q(h_{<t}, a)), else uniform random action.
No planning / no world model: AIQI does not roll forward an environment model; it evaluates return predictions under the on-policy trajectory and improves greedily—conceptually distributional Monte Carlo control with a universal predictor class.
Grain of truth (Definition 3.4): For true environment (\nu), each mixture (\psi_n) must place positive prior mass on the true conditional return law (\phi^*) induced by AIQI’s own policy (\hat\pi) under (\nu^{\hat\pi})—the standard self-referential “reflective” fix (authors cite reflective oracles as one route to a nontrivial class).
Main results: Theorem 4.6 — for suitable (H = H(\eta)) (effective horizon), large enough (M), (N \ge H + \log_\gamma(\cdot)), small (\tau), and grain-of-truth (\psi), AIQI is strong asymptotically ε-optimal on (\mathcal{M}). Theorem 4.8 — same policy is asymptotically ε-optimal in the mixture (\xi) (ε-Bayes-optimal analogue). Theorem 4.10 — under natural computable predictor classes, AIQI is not ε-self-optimizing from arbitrary historic policies even when a self-optimizing policy exists.
Positioning vs AIXI / Self-AIXI: AIXI is model-based Bayes-optimal planning in (\xi); Self-AIXI replaces planning with a policy mixture but still uses an environment mixture. AIQI is model-free at the object level: induction targets return distributions directly.
| Symbol | Meaning |
|---|---|
| (\mathcal{A}, \mathcal{O}, \mathcal{R} \subseteq [0,1]) | Finite action, observation, reward sets |
| (\mathcal{E} = \mathcal{O} \times \mathcal{R}), (\mathcal{H} = (\mathcal{A} \times \mathcal{E})^*) | Percepts, histories |
| (\nu : \mathcal{H} \times \mathcal{A} \to \Delta_{\mathcal{E}}), (\pi : \mathcal{H} \to \Delta_{\mathcal{A}}) | Environment, policy |
| (\nu^\pi) | Law on histories induced by (\pi) interacting with (\nu) |
| (\gamma \in (0,1)) | Discount; (R_t = (1-\gamma)\sum_{k=0}^\infty \gamma^k r_{t+k}) (full return, in ([0,1])) |
| (R_{t,H}) | (H)-step truncated return; (z_t) discretization of (R_{t,H}) to grid (\mathcal{Z}) |
| (H(\eta)) | Effective horizon: smallest (H) with tail mass (\le \eta) |
| (N \ge H) | Augmentation period; phases (n \in {0,\ldots,N-1}) |
| (\tilde\Omega^{(n)}), (\mathrm{aug}_n) | Augmented outcome space / valid augmentation map |
| (\phi) | Phase-(n) return-predictor: (\tilde{\mathcal{H}}^{(n)}{i-1} \times \mathcal{A} \to \Delta{\mathcal{Z}}) at return positions |
| (\psi_n) | Mixture return-predictor over (\mathcal{P}_n) with prior (\omega_n(\phi)) |
| (\psi) | Unified predictor combining ({\psi_n}) by (t \bmod N) |
| (\hat Q, \hat\pi) | AIQI estimated Q-values and ε-greedy policy (Definition 3.3) |
| (\delta_\psi, \delta_Q, \delta_1, \delta_\infty) | Return-predictor error, Q-error, one-step gap, global optimality gap |
- Mixture environment (\xi) (Definition 2.2): same as standard AIXI setup — (\xi(e_{1:t} | a_{1:t}) = \sum_\nu w(\nu), \nu(e_{1:t} | a_{1:t})).
- AIXI (Definition 2.3): (\pi^*\xi(h{<t}) \in \arg\max_a Q^*\xi(h{<t}, a)) — model-based reference.
- Mixture return-predictor (Definition 3.1): Bayesian mixture over (\phi \in \mathcal{P}_n) with online posterior weights.
- Unified return-predictor (Definition 3.2): (\psi(z_t \mid h_{<t}, a_t) = \psi_n(z_t \mid \mathrm{aug}n(h{<t}), a_t)) for (n = t \bmod N).
- AIQI (Definition 3.3): ε-greedy policy from (\hat Q) computed from (\psi); Algorithm 1 = loop over actions, Monte Carlo–style mean of discretized return, explore/exploit.
- Grain of truth (Definition 3.4): (\phi^*) for true (\nu^{\hat\pi}) lies in the support of each relevant mixture (self-referential).
- Strong asymptotic ε-optimality (Definition 3.5): (\limsup_{t\to\infty} \big(V^*\nu(h{<t}) - V^\pi_\nu(h_{<t})\big) \le \varepsilon) holds (\nu^\pi)-a.s. for all (\nu \in \mathcal{M}).
- Lemma 4.1: TV convergence (D(q_n, \tilde\nu_n^\pi \mid \mathrm{aug}n(h){<t}) \to 0) (merging-style) under grain of truth, with auxiliary (q_n) tying mixture to pushforward law (\tilde\nu_n^\pi = \nu^\pi \circ \mathrm{aug}_n^{-1}).
- Lemma 4.2 (return-predictor convergence): Strong bound on sums of (\delta_\psi) over counterfactual suffixes (key technical device; needs (N > H) buffer so augmentation stays well-defined for those futures).
- Lemma 4.3: (\delta_Q) inherits similar bounds + discretization (M^{-1}) + horizon slack (\eta).
- Lemma 4.4: One-step optimality gap (\delta_1) small (up to exploration (\tau) slack).
- Lemma 4.5: Telescoping bound: global gap (\delta_\infty) controlled by future one-step gaps (\delta_1) along a chain of counterfactual argmax-Q differences (Bellman-style propagation).
- Lemma 4.7: Strong asymptotic ε-optimality on (\mathcal{M}) lifts to mixture (\xi) (ε-optimal w.r.t. (\xi) almost surely under stated measures).
- Theorem 4.6: Parameter recipe ((\tau, M, H(\eta), N) scaling with (\varepsilon, \gamma)) + grain of truth (\Rightarrow) strong asymptotic ε-optimality on (\mathcal{M}).
- Theorem 4.8: Same (\Rightarrow) asymptotic ε-Bayes-optimality in (\xi) (parallel to AIXI’s role as Bayes-optimal in (\xi), but asymptotic and ε).
- Theorem 4.10: Not self-optimizing off-policy: even when an exact self-optimizing policy exists, AIQI can fail ε-self-optimization from history generated by wrong (\pi') (predictor may lock to historic policy’s return law).
- Algorithm 1: Tabular-style loop; maintain history; for each step compute (\hat Q(\cdot, a)) for all (a), ε-greedy act, observe percept, append. §D (per paper) reports experiments with a computable approximation of AIQI.
What can be implemented in principle:
- Finite or structured (\mathcal{P}_n): Online Bayesian sequence prediction for discretized returns on the periodically augmented symbol stream (e.g. variable-order Markov / CTW-style predictors over an augmented alphabet (\mathcal{A} \times \mathcal{Z} \times \mathcal{E}) with periodic (\mathcal{Z}) symbols).
- ε-greedy control over (\hat Q) as defined; tune (H), (M), (N), (\tau) per resource budget.
- Horizon / discretization tradeoffs: Larger (M) refines return grid; (H(\eta)) controls bias vs. variance of truncated-return targets.
What remains idealized:
- Full universality (all computable return-predictors / environments with Solomonoff-style priors) inherits incomputability like AIXI.
- Grain of truth for the true AIQI policy is a fixed-point / reflective condition — not automatic for arbitrary finite classes.
- Optimality is asymptotic and ε; constants in parameter scaling can be impractical for real agents.
- Off-policy / historic data: Theorem 4.10 warns do not expect AIQI-style self-optimization from passive logs.
Engineering reading: Blueprint = (periodic augmented history) + (Bayesian mixture over return predictors) + (posterior-mean Q̂) + (ε-greedy on-policy updates) — a principled model-free universal analogue to classical MC control, with GRL-level guarantees only under grain of truth and on-policy interaction.
| This paper | Relation | See analysis |
|---|---|---|
| AIXI, mixture (\xi), Bayes-optimality | AIQI matches asymptotic ε-Bayes-optimality in (\xi) (Thm. 4.8) while avoiding explicit environment modeling in the decision rule | NeurIPS 2023 Self-AIXI — Self-AIXI still uses (\xi); compare model-free return induction vs policy mixture + (\xi) |
| Self-AIXI “sensible off-policy” | AIQI’s analysis stresses counterfactual return-prediction bounds to avoid ad-hoc off-policy assumptions on-policy | 01-neurips-2023.md (Thm. 16 discussion) |
| MC-AIXI, CTW, planning | Table 1: classical universal agents are model-based; AIQI is model-free and general-RL optimal in the ε-asymptotic sense | pyaixi |
| Distributional RL | Return predictors are distributional objects (Bellemare et al. line cited) | arXiv 2502.15820, arXiv 2511.22226, arXiv 2505.21170 — empirical / algorithmic cousins without GRL optimality proofs |
| CRCA / repo | Useful if we prototype bounded (\mathcal{P}_n) predictors or compare template agents to mixture-of-predictors control | aixi/README.md, aixi/IMPLEMENTATION_PLAN.md |
- “Model-free” here means no explicit environment kernel in the action-selection loop; the agent still learns a predictive model of returns (a value-model), so the boundary with “model-based” in deep RL parlance is semantic — the paper’s contrast is with AIXI-style world models.
- Deterministic policies and strong asymptotic optimality: The paper recalls Lattimore & Hutter (2011): deterministic policies (including AIXI) need not be strong asymptotically optimal for small ε; AIQI’s stochastic exploration is essential to the strong ε-optimality target (Definition 3.5).
- Self-optimization: Unlike AIXI’s classical self-optimization result, AIQI is explicitly not a general self-optimizer from off-policy histories (Thm. 4.10) — important for deployment narratives involving batch or human-driven data.