PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Universal Prediction under Interaction

Richard Cornelius Suwandi

arXiv:2610.33842v1cs.LGstat.ML

TL;DR

The paper asks how prediction guarantees survive when an agent’s planning changes where its learned predictor is evaluated. It analyzes transfer through task evidence and policy coverage, and finds that interaction can preserve a multiplicative worst-case penalty even for computable predictors. It also gives bounded-return and mentor-deferral guarantees under explicit approximation and coverage conditions.

  • Problem

    When planning changes which situations a learned predictor encounters, it is unclear which approximation guarantees transfer to the decisions made using that predictor.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes finite-horizon causal mixtures using task evidence, policy occupancy, bounded-return planning, and conditional KL bounds for mentor deferral.

    Source: §1 · p. 2, §5 · p. 14

  • Results

    A fixed universal causal mixture admits a matching multiplicative prediction-error lower bound on infinitely many computable environments, and computability alone does not remove the penalty.

    Source: §8 · p. 17

  • Takeaways & Limitations

    The guarantees apply to any predictor architecture satisfying the stated population approximation and coverage conditions, while planning also requires the specified policy-class and planning-error conditions.

    Source: §7 · p. 16

    The results do not certify that a particular network attains the population KL assumption, and planning guarantees additionally require suitable policy and shared-return conditions.

    Source: §7 · p. 16

Abstract

from arXiv · show

Bayesian mixtures, and Solomonoff induction in particular, provide an idealized model of prediction learned by minimizing population log loss, and they underlie universal agents such as AIXI. An agent that plans with an approximation of such a predictor decides where that predictor is evaluated, and a planner can be drawn toward branches on which its model is optimistic. We study which approximation guarantees survive this feedback. For normalized finite-horizon causal mixtures, the transfer coefficient factors into a policy likelihood ratio and task evidence available before each prediction, so task rarity and action-branch rarity can compound. Within one fixed universal mixture, infinitely many computable environments admit excess prediction error of order $\kappa\eta\,2^{K(\mu)}$, where $\eta$ is the training KL budget and $\kappa$ measures policy coverage. This order is sharp, and for each target a computable predictor attains it at a suitable finite horizon, so computability alone does not remove the penalty. For bounded returns, value error is controlled by the probability of entering a poorly covered branch plus a square-root term in $\eta$. Both terms are necessary, and finite maximum coverage ratios are not required. Motivated by the mentor override of Golden Handcuffs, we derive margins for preserving deferral decisions and conditional KL budgets with an unavoidable inverse-history-probability penalty, and a counterexample separates agreement of deferral decisions from task-wise event avoidance. The guarantees apply to any predictor architecture that meets explicit population approximation and coverage conditions, which gives concrete targets for implementing idealized universal agents.

1 Introduction

The paper studies how approximation error transfers to decisions when an agent’s planning changes which situations its predictor encounters. It characterizes the roles of task evidence, policy coverage, bounded-return planning, and mentor deferral, and positions these guarantees relative to prior work.

1 Introduction

  • Prediction error can compound across task rarity and rarely explored action branches, but task rarity matters only through evidence available before each evaluated prediction.Indistinguishability throughout the relevant histories removes the prior-mass multiplier.Source: §1 · p. 2
  • A joint occupancy coefficient tracks task evidence and policy likelihood ratios; within one fixed universal mixture, infinitely many computable environments attain a matching multiplicative prediction-error lower bound.A finite-table approximation preserves this order for computable predictors selected separately for each target and horizon.Source: §1 · p. 2
  • For bounded returns, value error is controlled by the probability of entering poorly covered branches plus a square-root term in the approximation budget; neither term can be removed.The bound can remain useful when every maximum occupancy ratio is infinite.Source: §1 · p. 2
  • The paper derives margins for preserving finite-horizon mentor-deferral decisions and conditional KL budgets, while a counterexample separates override agreement from task-wise event avoidance.The inverse-history-probability cost of conditioning is unavoidable.Source: §1 · p. 2
  • The guarantees combine classical KL, change-of-measure, conditional-mean, and bounded-return tools, while identifying interactive quantities and proving their compounding unavoidable within a universal mixture.They apply to any architecture meeting the stated population approximation, coverage, and planning assumptions.Source: §1 · p. 2

1.1 Related work

  • Prior universal-prediction work studies computable alternatives and approximation criteria, but those criteria do not certify the paper’s population-KL assumption for deployed predictors.The paper asks what follows once that guarantee is available.Source: §1.1 · p. 3
  • Unlike MC-AIXI’s approximation analysis, this setting tracks task-mixture rarity and behavior-to-deployment occupancy separately; it also keeps the response model distinct from the policy.The guarantees are population-KL consequences, not finite-sample rates or calibrated uncertainty estimates.Source: §1.1 · p. 3
  • For approximate Golden Handcuffs, the paper analyzes finite-horizon deferral and conditional guarantees at observed histories; extending its results to semimeasures requires choosing a decision model.The setup uses normalized trajectory laws and a shared bounded return.Source: §1.1 · p. 3

2 Finite-horizon causal setup

The setup defines finite-horizon causal environment models, policies, and their trajectory laws, then forms a Bayesian mixture over environments. It measures learned-model approximation by population trajectory KL under a behavior policy and explains why coverage of full histories matters for transferring that guarantee.

2 Finite-horizon causal setup

  • A finite-horizon trajectory records actions and percepts, with a causal model assigning normalized response probabilities at each history-action pair and a policy assigning action probabilities from history.The agent does not observe the hidden task label.Source: §2 · pp. 3–4
  • The causal mixture uses prior-weighted environment likelihoods to form posterior predictive conditionals; reusing prior weights at each step would generally define a different model.With a common policy, its action factors cancel from the task posterior, and the posterior conditionals telescope to the mixture trajectory law.Source: §2 · p. 4
  • Approximation is bounded by population KL between trajectory laws under a behavior policy, and the occupancy ratios are defined on full histories rather than compressed states.The assumption concerns population laws, not empirical training loss; learned models and selected policies are held fixed when applying the results.Source: §2 · p. 4

2.1 Interpreting the approximation assumption

  • The trajectory-KL assumption bounds excess population response log loss relative to the ideal mixture, which minimizes that loss over normalized causal predictors.Zero excess loss forces agreement only on pairs with positive training occupancy; unvisited pairs remain unconstrained and motivate the coverage quantities.Source: §2.1 · pp. 4–5
  • Transcript-model loss instantiates the assumption only with finite response alphabets and specified interaction data; empirical loss, unrelated-text perplexity, or task-informed demonstrations do not certify it.A directly generated action policy does not have its response-model KL controlled by its action-prediction loss.Source: §2.1 · p. 5

3 Joint rarity of tasks and policies

The section studies how task rarity and policy coverage jointly govern transfer of prediction error under interaction. It identifies when those costs compound and shows that the resulting penalty can be sharp even inside one fixed universal mixture.

3 Joint rarity of tasks and policies

  • The joint occupancy coefficient Γ controls target-task prediction error when the coefficient is finite.The bound assumes the stated training approximation condition.Source: §3 · p. 6

3.1 The evidence factorization

  • Γ factors into the policy likelihood ratio and the evidence for the task available before each prediction.Task prior mass enters through that accumulated evidence, and the coarse product is tight only when both maxima occur at the same pair.Source: §3.1 · p. 7
  • If environments remain indistinguishable before every evaluated prediction, Γ is bounded by policy coverage alone; full task revelation at a maximally covered pair instead gives κπ/wµ.The first case avoids a task-prior penalty, while the second pays the product of task rarity and policy rarity.Source: §3.1 · p. 7
  • Revealing the task after a rare action can still make Γ equal to 1/(wϵ), because later predictions encounter both task evidence and action-branch rarity.The example places task revelation after the rare action and incurs excess error of order Γη.Source: §3.1 · p. 7

3.2 Sharpness inside one universal causal mixture

  • Within one fixed universal causal mixture, infinitely many computable environments attain excess prediction error of order κπη2^K(µ), matching the upper-bound order up to constants.The construction aligns the policy and task penalties on the same prediction pairs.Source: §3.2 · pp. 8–9
  • For each target, a computable predictor can attain this lower-bound order at a suitable finite horizon, so computability alone does not remove the penalty.The predictor may depend on the target, horizon, η, and ϵ; no description-length or runtime bound is asserted.Source: §3.2 · pp. 9–10

4 From prediction to planning

The section translates prediction error into bounded-return planning guarantees while accounting for poor policy coverage. It shows that both rare-branch probability and near-tie error matter, and that a positive policy-value gap can preserve optimal value.

4 From prediction to planning

  • With exact planning and both occupancy coefficients at most κ, the value-error bound is min{1, √(2 ln 2 κη)}.For a restricted policy class, attainment of the optimal policy is an assumption.Source: §4 · pp. 10–11

4.1 Planning with rare coverage failures

  • Bounded-return value error can be controlled by the probability of entering poorly covered branches plus a square-root term, without requiring a finite maximum occupancy ratio.The bound charges coverage failure once per episode rather than accumulating occupancy across rounds.Source: §4.1 · p. 11

4.2 Counterexamples and failure modes

  • Exact on-policy prediction does not control comparator value when behavior misses counterfactual actions; a planner can also select an exponentially rare, optimistic action sequence.The sequence 0L has behavioral probability 2^-L despite description length at most K(L)+O(1).Source: §4.2 · p. 12
  • Zero Bayesian value loss does not guarantee task-wise policy stability: the learned planner can lose 1 in one environment and gain 1 in another.Both deterministic policies have coverage coefficient 2 in the example.Source: §4.2 · p. 12
  • Both terms in the coverage-failure bound are necessary: uncovered branches can cause value error even at η=0, and near ties force square-root decision loss.The square-root dependence cannot be improved without a decision gap.Source: §4.2 · p. 12

4.3 A positive policy-value gap

  • For a finite policy class with positive value gap, a certified error bound below that gap rules out positive regret and preserves optimal value, not a particular policy among ties.More generally, the bound is at most min{B, B^2/∆Π}.Source: §4.3 · p. 13

5 Application to approximate mentor deferral

The section derives margins for preserving mentor-deferral decisions under predictor approximation, then localizes guarantees to observed histories. It also shows that agreement on deferral does not ensure task-wise event avoidance.

5 Application to approximate mentor deferral

  • The conservative learned rule defers whenever the ideal rule does if its threshold is raised by (L + 1)b.The value-error certificate scales with the return-range factor L + 1.Source: §5 · p. 13
  • A larger subjective loss range permits a larger value error, while a uniform certificate over the policy class can be demanding or vacuous.The certificate must control every policy relevant to the optimized score, including poorly covered candidates.Source: §5 · p. 13

5.1 Conditional continuation guarantees

  • A deterministic rule can adaptively request certificates at first-request histories because prefix-free histories share the training KL budget, but nested requests cannot reuse it.For a prefix-free collection, descendant pairs are disjoint in the chain-rule sums.Source: §5.1 · p. 14
  • The inverse-history-probability penalty is unavoidable: episode KL can tend to zero while conditional value error at a rare history remains 1/2.In the two-round example, the episode KL is pd and the conditional KL at history 1 is d.Source: §5.1 · p. 14
  • At a history h, the deferral decision is preserved when |Fξ(h) − θ(h)| > (L + 1)bh + ζh.Using only the episode budget gives the weaker η/pβ(h) certificate, and histories with zero training probability have no such guarantee.Source: §5.1 · pp. 14–15

5.2 Agreement of overrides does not imply event avoidance

  • Deferral can agree while task-wise safety differs: as training KL tends to zero, failure probability is zero under the ideal action and one under the learned action.Both policies have coverage coefficient two in the example.Source: §5.2 · p. 15
  • The event bound compares models under the same policy, not failure probabilities of different policies in the true task; a nonzero additive bound does not ensure event avoidance.Extending Golden Handcuffs also requires its semimeasure and discounting conventions, repeated mentor selection, and guarantees for actions between overrides.Source: §5.2 · p. 15

6 Implications for learned agents

The implications are conditional on the normalized finite-horizon model, its approximation assumption, and the stated coverage conditions. They describe worst-case transfer limits and margins for learned-agent evaluation and deferral.

6 Implications for learned agents

  • These are worst-case transfer statements within the normalized finite-horizon model, not explanations of trained-network behavior or evidence that moving data between sources improves performance.Their conclusions require assumption (4) and the relevant coverage conditions.Source: §6 · p. 15
  • For a history h with pβ(h) > 0, the conditional budget can be as large as η/pβ(h), and this inverse-probability factor is tight.On a prefix-free collection, the same training KL is shared across histories.Source: §6 · p. 15
  • Deferral agreement requires |Fξ − θ| > (L + 1)b + ζ; agreement alone does not ensure event avoidance.The example retains failure probability zero under the ideal action and one under the learned action as training KL tends to zero.Source: §6 · p. 15
  • A policy selected by planning under ρ can incur loss on branches rare under behavior; one example has η = 0 under β yet the learned planner loses 2/5.A separate example gives episode KL equal to 2−L(log2 3)/2 for the selected action string.Source: §6 · pp. 15–16
  • Excess prediction error can be of order κπη 2^K(µ) for infinitely many computable environments within one fixed universal mixture.The task-evidence and policy-likelihood factors compound once the task is identifiable on a branch rare under behavior.Source: §6 · p. 16
  • Task-family weight and within-episode policy coverage affect separate factors: Γ(µ, πj; β) ≤ 1/(λqµγj).Raising λ puts more episodes on a task family, while raising γj changes action sequences within those episodes.Source: §6 · p. 16

7 Scope, limitations, and open problems

The guarantees are conditional on explicit planning, coverage, and model assumptions, and several quantities may worsen with horizon. The analysis also leaves open questions about resource bounds, loss-sensitive coverage, repeated overrides, and AIXI conventions.

Scope and assumptions

  • Planning guarantees require a suitable policy class, bounded planning error, and the shared return; a different learned evaluator adds error outside the bounds.Coverage is measured on full histories, so compressed-state coverage is not a substitute.Source: §7 · p. 16

Evaluation

  • Finite rational testbeds permit exact occupancy and policy-value evaluation, but cannot by themselves certify the universal setting.They can measure how close trained predictors come to the identified worst cases.Source: §7 · p. 16

Scope and assumptions

  • The proofs use normalized trajectory laws and bounded returns, so they do not automatically apply to raw Solomonoff semimeasures.An AIXI-oriented extension must specify its semimeasure, termination or missing-mass treatment, reward convention, and horizon or discounting.Source: §7 · p. 16
  • The planning comparator is the optimal Bayesian policy in the same class, not a clairvoyant policy that knows the true environment.Predictive convergence on visited histories does not establish the value of unvisited actions.Source: §7 · p. 16

Horizon and data

  • The quantities η, κπ, and Γ can grow with horizon, and finite-sample estimates require separate assumptions, especially for adaptive data.A fixed uniformly computable predictor cannot have bounded population trajectory KL at all horizons against a normalized mixture containing every computable deterministic sequence.Source: §7 · pp. 16–17

Open problems

  • Open questions include which runtime, representation-size, or learning-procedure restrictions change the worst-case penalty, and whether loss-sensitive coverage can improve Γ.Γ is optimal for arbitrary local losses but may overstate the cost for a particular return.Source: §7 · p. 17
  • Repeated overrides still require control of intervening actions, and score agreement alone does not establish task-wise event avoidance.An AIXI extension also requires the semimeasure and value conventions described above.Source: §7 · p. 17

8 Conclusion

The conclusion identifies how task evidence and policy occupancy jointly govern prediction-error transfer, with a matching worst-case penalty in a fixed universal mixture. It also gives bounded-return and mentor-deferral guarantees under explicit population assumptions.

Conclusion

  • The joint occupancy coefficient separates the policy likelihood ratio from task evidence available before each prediction; indistinguishability throughout relevant histories removes the prior-mass multiplier.A fixed universal causal mixture admits a matching multiplicative lower bound on infinitely many computable environments, and computability alone does not remove the penalty.Source: §8 · p. 17
  • For bounded-return planning, a coverage-failure probability can replace an infinite maximum ratio, while conditional continuation bounds quantify the added cost of assessing a rare observed history.The results give margins for preserving mentor-deferral decisions, but a counterexample separates those decisions from task-wise event avoidance.Source: §8 · p. 17
  • The guarantees apply to agents meeting the population assumptions; verifying them for trained agents and extending the analysis to AIXI semimeasure-based decisions remain next steps.Source: §8 · p. 17

A Supporting results

The appendix shows how discarded history creates an irreducible prediction cost for compressed representations. That cost is measured by conditional information and depends on the behavior distribution.

A.1 The prediction cost of discarded context

  • A predictor using a deterministic history representation incurs excess log loss when that representation discards information needed to predict responses.The appendix treats this information loss independently of how a network implements the predictor.Source: §A.1 · p. 19
  • The smallest trajectory KL among predictors using a fixed representation equals Iβ(ϕ), so the approximation assumption requires η ≥ Iβ(ϕ).Zero penalty means the representation and chosen action suffice for prediction on the training distribution.Source: §A.1 · p. 19
  • In a two-round example, discarding the first of two identical fair-bit percepts costs one bit of KL, while retaining it reduces the minimum to zero.Zero penalty does not establish sufficiency on histories the behavior policy never visits; the compressed conditional depends on β because training frequencies pool histories.Source: §A.1 · p. 19

A.2 Average-case prediction and clipped transfer

The appendix extends prediction transfer to average-case and clipped-occupancy forms, then considers simultaneous prior and policy shifts. These results retain distinctions between training and test distributions and between average and task-wise errors.

A.2 Average-case prediction and clipped transfer

  • Under the approximation assumption and finite κπ, average excess prediction loss is at most (ln 2)κπη.The causal average-case identity compares predictors under the same policy, not losses under different model-optimal policies.Source: §A.2 · p. 20
  • The average-versus-task-wise robustness gap persists under interaction, with both average and task-wise excess scaling with the policy coefficient.Source: §A.2 · p. 20
  • A clipped transfer bound can replace the (ln 2)Γη approximation term, and its residual counts occupancy across rounds rather than once per episode.When Γ is finite, choosing the clipping threshold c = Γ recovers the earlier bound.Source: §A.2 · p. 20

A.3 Simultaneous prior and policy shift

  • With a shifted test prior, the excess-error baseline is the test-prior mixture; even an exact learned mixture can incur excess when the prior changes.With one available action, the result recovers the finite-horizon form of Li and Teng [2026, Theorem 5].Source: §A.3 · p. 21

A.4 Episode-level allocation of training data

Episode-level policy allocation makes rollout coverage explicit while separating it from task-family allocation. The section also identifies when task rarity and interaction rarity affect guarantees, and what the coverage assumptions do not establish.

A.4 Episode-level allocation of training data

  • Sampling a rollout policy once per episode yields a common history-dependent behavior policy, whose trajectory probabilities telescope to establish Proposition 9’s allocation identity.Conditioning on the observed history generally differs from resampling the rollout policy independently at each step.Source: §A.4 · p. 21
  • Family mass alone does not give an individual task coefficient of 1/(λγj); that coefficient instead controls the family mixture’s excess relative to ξq.The section defines the task-family prior as w = λq + (1 − λ)v and gives a family-average bound relative to ξq.Source: §A.4 · p. 22
  • Task allocation and interaction allocation are distinct: task-family frequency raises λ, while collecting episodes under a rollout policy raises γj.Adding task descriptions alone need not expose responses to alternative action sequences; changing the data distribution can also change attainable approximation error, so reallocation need not monotonically improve a trained predictor.Source: §A.4 · p. 22
  • Pessimistic planning can compare against a covered policy without comparable coverage of every candidate, whereas Theorem 4 bounds plug-in planning using coverage-failure probabilities for both policies.Theorem 4 does not provide the calibrated confidence set required by pessimism.Source: §A.4 · p. 22

A.5 An explicit finite-class instance

A two-stage, two-environment construction makes joint task and action-branch rarity explicit. Its early-revelation structure also gives the dependence established inside a fixed universal mixture.

A.5 An explicit finite-class instance

  • The construction uses two stages and two environments, with target task mass w, and provides a finite-class lower bound for joint rarity.The target environment outputs 1 deterministically at the first step, while the other outputs 0; both produce a fair bit at the second step under either action.Source: §A.5 · p. 22
  • The exceptional pair has training occupancy wϵ but target deployment occupancy one, combining a target task of mass w with behavior that chooses r with probability ϵ.The target environment reveals its identity at the first step; the behavior then chooses r with probability ϵ, while deployment always chooses r.Source: §A.5 · p. 22
  • The task-wise excess in the construction is exactly 2δ^2.The first-step predictor is unchanged, and the target and mixture conditionals agree at the second step.Source: §A.5 · p. 22
  • This early-revelation construction gives the same dependence as Theorem 2, with constants depending on the reference machine, inside one fixed universal mixture.The explicit construction is at horizon two.Source: §A.5 · p. 23

B An infinite-horizon computability obstruction

The section establishes a population-KL obstruction for a fixed computable predictor, even in a passive binary setting. A diagonal construction produces a computable deterministic sequence, while the result leaves several finite-horizon and restricted-class settings open.

B An infinite-horizon computability obstruction

  • A fixed computable predictor cannot have uniformly bounded universal KL against a normalized mixture giving positive weight to every computable deterministic binary sequence.The proposition states that some constant w > 0 witnesses the obstruction for every horizon H.Source: B An infinite-horizon computability… · p. 23
  • The diagonal construction chooses each next bit so that the predictor assigns it probability at most 5/8, producing a computable deterministic sequence.It uses rational approximations to the predictor’s probabilities and does not require deciding equality of computable real numbers.Source: B An infinite-horizon computability… · p. 23
  • The obstruction already holds without interaction, but does not rule out horizon-dependent predictors, finite-horizon guarantees, or restricted computable environment classes.Source: B An infinite-horizon computability… · p. 23

Related papers

Loading 2610.33842v1…