PaperlayerView exact revision on arXiv

Source-linked AI summary

What Information Buys in Active Inference

Melih Kandemir, Mustafa Mert Çelikok

arXiv:2610.19046v1cs.LGstat.ML

TL;DR

The paper asks when information gain is advantageous over confidence-set exploration for agents that learn and act through state abstractions. It compares calibrated AIF’s reward-agnostic width with Bayes-UCBVI’s value-specific widths, finding an advantage when goals are chosen from the agent’s data, but not when rewards are fixed.

  • Problem

    The paper asks when information gain is advantageous or disadvantageous, in regret, compared with confidence sets for agents that explore and learn through a state abstraction.

    Source: §1 · p. 2

  • Method

    Calibrated AIF uses reward-independent novelty to remain optimistic for every reward, with a width comparable to an ℓ1 confidence-set radius.

    Source: §1 · p. 3

  • Results

    Under adaptive rewards chosen from the agent’s data, Bayes-UCBVI incurs regret Ω(K/ln K), while calibrated AIF remains optimistic for all rewards; for fixed rewards, calibration does not improve on visit-count bounds.

    Source: §1 · p. 3, §6 · p. 12

  • Takeaways & Limitations

    Calibrated information gain acts as a reward-agnostic ℓ1 confidence set, advantageous over value-specific widths when goals come from the agent’s data, but not when rewards are fixed.

    Source: §1 · p. 4

    The adaptive-goal comparison concerns goal-memoryless agents, whose last-step action choices are restricted to records for the current state and fresh randomness.

    Source: §2.2 · p. 6

Abstract

from arXiv · show

Information-theoretic exploration is of primary interest in methodological studies of reinforcement learning (RL) and computational cognitive neuroscience, while the established RL theory builds regret guarantees on confidence sets. This situation leaves open the conditions under which the information-driven exploration found in nature is more advantageous than the exploration of the established RL theory. We put the state-of-the-art methods of these two paradigms, Active Inference (AIF) and Bayes-UCBVI, on an equal footing: both act through the same state abstraction of a tabular MDP with $S$ states, and their greedy forms differ only in the exploration term. We find that AIF's information gain decays too fast to serve as a confidence width, locking greedy agents that explore by it out of the optimal action. Calibrating the information gain by a square root yields calibrated AIF, which attains regret of order $\sqrt T$ for an exact abstraction, but no better guarantee than Bayes-UCBVI for a fixed reward. When an adversary chooses rewards from the agent's data, Bayes-UCBVI's value-specific widths lock out, whereas calibrated AIF pays a factor $\sqrt S$, which no goal-memoryless agent avoids on some MDP whose start states the adversary also chooses. Calibrated information gain thus acts as a reward-agnostic $\ell_1$ confidence set, preferable to value-specific widths when rewards are chosen from the agent's data, not when they are fixed.

1. Introduction

The paper asks when information-driven exploration is more advantageous than confidence-based exploration for agents acting and learning through state abstractions. It compares Active Inference (AIF) with Bayes-UCBVI and analyzes fixed rewards, data-adaptive goals, and learned abstractions.

1. Introduction

  • AIF couples action selection with world-model learning through expected free energy, which scores actions by expected reward and expected information.The paper frames this as a question of when information gain helps or hurts regret relative to confidence sets for agents using state abstractions.Source: §1 · pp. 1–2
  • The comparison puts AIF and Bayes-UCBVI on the same abstraction and transition posterior, isolating information versus value as the exploration currency.The paper also compares AIF with CaI and UCBVI.Source: §1 · p. 2
  • For fixed rewards, raw information gain decays as N^-1 and can cause linear regret, while calibrated AIF’s square-root novelty yields a valid width but no advantage over Bayes-UCBVI’s bound.The value shortfall decays as N^-1/2; calibrated AIF’s regret bound is worse than Bayes-UCBVI’s value-specific quantile by a factor √Γϕ.Source: §1 · p. 2
  • Under adaptive goals, calibrated information gain is optimistic across reward functions, while Bayes-UCBVI’s value-specific widths can lock out when goals are chosen from the agent’s data.Every agent faces an S^1/4 regret factor on some MDP; goal-memoryless agents such as AIF face a factor S, up to logarithmic factors.Source: §1 · pp. 3–4
  • When abstractions are learned, information about observation emissions can favor worse actions, and predicting an abstraction’s own labels can preserve a coarse, poor abstraction.GOLF instead uses value as a shared target and attains e O(T) regret in realizable block MDPs with latent rewards, including adaptive latent goals.Source: §1 · p. 4

2. Episodic Control Under an Abstraction

The section sets up finite-horizon episodic control when agents act through a state abstraction, then defines abstraction error and the goal settings used for regret comparisons.

2. Episodic Control Under an Abstraction

  • In the finite-horizon episodic MDP, the agent does not know the transition kernel and measures regret against an agent that knows it and follows an optimal policy.The agent commits to a policy before each episode, using past observations.Source: §2 · p. 4
  • Valid confidence widths compensate for underestimation of next-step value and keep computed values optimistic by backward induction.Bayes-UCBVI uses a Dirichlet posterior and quantile-gap width; its gap decays at the n̄^-1/2 rate, and no valid width at a fixed count decays faster.Source: §2 · p. 5

2.1. State Abstraction and Its Cost

  • An abstraction maps ground states into fewer abstract states, and its representation scale bounds the per-episode loss from treating each block as one state.An exact abstraction has zero representation scale; optimism makes abstraction error an additive regret cost, and UCBVI-CH matches the minimax rate up to H and logarithmic factors.Source: §2.1 · pp. 5–6
  • Running UCBVI or Bayes-UCBVI on abstract data preserves high-probability regret bounds, with representation error contributing an additive term.When the abstraction is exact and the agent is given the abstract reward, the abstract data form an episodic MDP.Source: §2.1 · p. 6

2.2. Goals

  • Goals are episode-specific reward functions; an adaptive adversary chooses them from interaction history, while an oblivious adversary fixes goals and start states in advance.The goal-memoryless condition restricts last-step action choices at states where all actions have equal reward; the stated upper bound and lock-out argument do not cover UCBVI under adaptive goals.Source: §2.2 · p. 6

3. What Information Gain Costs Under a Fixed Reward Function

The section compares information-driven and value-based exploration on the same abstract transition posterior. Raw novelty decays too quickly to act as a confidence width, while calibrated information gain supplies a valid width for exact abstractions.

3.1. AIF and CaI on an Abstraction

  • With a fixed abstraction, AIF and Bayes-UCBVI hold the same transition posterior, and their greedy forms differ in the exploration term.AIF’s state term contains novelty once, while its parameter-information term counts novelty again; calibrated AIF drops the state term and acts greedily.Source: §3.1 · pp. 7–8

3.2. Raw Information Gain Has the Wrong Order

  • Novelty decays as n̄^-1, while valid widths must cover next-step-value underestimation at order n̄^-1/2, so no constant factor repairs the mismatch.The novelty falls below the required threshold once n̄ ≥ 64X^2/(νH^2).Source: §3.2 · p. 8
  • Greedy AIF variants using raw information gain can lock out the optimal action and incur linear regret, even with the reward known.The AIF state term can incur linear regret even when both the transition kernel and reward are known.Source: §3.2 · p. 9

3.3. Calibrated AIF

  • Calibration uses the square root of novelty, scaled by the value-function span, to make information gain a valid width.The exchange rate grows with the visit count, unlike a fixed precision that cannot convert nats into reward.Source: §3.3 · p. 9
  • Calibrated AIF is optimistic for an exact abstraction and has a regret bound that depends on the accrued novelty budget and adds representation error for an inexact abstraction.The bound is stated with probability at least 1−δ.Source: §3.3 · pp. 9–10
  • Calibrated AIF’s bound exceeds Bayes-UCBVI’s by √Γϕ and its variance-aware exact-abstraction bound by √(HΓϕ).The comparison is for the stated bounds, not a claim that calibrated AIF is better under a fixed reward.Source: §3.3 · p. 10

4. Adaptive Goals

Adaptive goals expose a gap between value-specific and reward-agnostic exploration: calibrated AIF with a uniform prior is optimistic for every goal, while Bayes-UCBVI’s quantiles can fail for goals chosen from data. The paper also contrasts this setting with fixed goals and with agents that use past goals as data.

Adaptive goals

  • Calibrated AIF controls deviations of the whole transition row, whereas a value-specific width controls only the projection needed for a particular value function.The square root of novelty bounds posterior deviation for every value function at once; under a uniform prior, novelty is of the order X/n̄.Source: §4 · p. 10
  • The theorem gives a lower bound for every agent and a larger lower bound for goal-memoryless agents on a Gaussian family of MDPs.The stated setting has horizon 2, two actions, and an adversary choosing goals and start states from the transition law and history.Source: §4 · p. 10
  • An agent that uses past goals as data and knows the adversary’s strategy has an expected-regret upper bound on the Gaussian family.The bound is stated as 2Y^1/4√(MK ln(1 + 16K)).Source: §4 · p. 10
  • Goals fixed before the first episode, including a single fixed goal, cost no extra regret in the stated comparison.The result concerns goals and start states chosen by an oblivious adversary.Source: §4 · p. 11
  • Bayes-UCBVI’s value-specific quantiles can lock out for data-dependent goals, while calibrated AIF with a uniform prior is optimistic for every goal at once.A value-specific quantile is accurate for each fixed goal, but not for a goal chosen after the data.Source: §4 · pp. 10–11

5. Learned Abstractions

For learned abstractions, the paper compares observation- and label-based selection with selection based on a shared value-function target. It proposes an enactive agent and identifies failure modes for AIF and latent-predictive selection.

Learned Abstractions

  • The setup assumes a realizable block MDP with a candidate abstraction whose latent kernel and emission generate the transitions, and rewards depend on the latent state.The agent scores each candidate by its prediction of a target.Source: §5 · p. 11
  • The enactive agent selects abstractions using a value-function target shared by candidates and acts greedily for the most optimistic retained function.It uses squared Bellman residuals relative to the best predictor of that same target; under a newly revealed goal, it relabels past data and recomputes its version space.Source: §5 · p. 11
  • The paper builds a function class from candidate abstractions and shows that, with latent rewards, it is closed under Bellman backups, with observations entering through ln |Φ|.This lets the coverability analysis of Xie et al. (2023) apply.Source: §5 · p. 12
  • AIF’s information gain about emissions can favor an action with many distinct observations over a better action, causing linear regret when S ≥ 2K + 2.This result is for a block MDP with latent rewards and a given decoder.Source: §5 · p. 12
  • A latent-predictive agent can favor a coarse abstraction that merges states with different best actions, yielding regret Ω(HK), while GOLF on the same candidate set has a sublinear bound.Labels generated by acting through the coarse abstraction cannot refute it; the stated GOLF bound is eO(H^2√…).Source: §5 · p. 12

6. Conclusion

The conclusion distinguishes fixed-reward exploration from adaptive-goal exploration: raw information gain is too weak for fixed rewards, while calibrated information gain is useful across data-chosen goals. It also identifies unresolved questions about adaptive goals and learned abstractions.

Conclusion

  • For fixed rewards, raw information gain incurs linear regret, and calibrated information gain does not improve on the bound attainable with visit counts.The conclusion states that information gain decays faster than the value shortfall it must cover.Source: §6 · p. 12
  • Under adaptive goals, calibrated information gain makes the agent optimistic for every goal, while Bayes-UCBVI’s value-specific widths can lock out.The conclusion characterizes calibrated information gain as an ℓ1 confidence set and says goal-memoryless agents pay a factor S^1/4, up to logarithmic factors.Source: §6 · p. 12
  • The conclusion leaves open whether the adaptive-goal price holds with fixed starts, at every horizon, on every MDP, and for agents that use past goals as data.It also asks whether agents can attain the factor S^1/4 without knowing the adversary’s strategy.Source: §6 · p. 12
  • The convergence and attractors of coupled goal-policy dynamics remain unknown when agents move their goals toward the attractors induced by the MDP and exploration rule.The conclusion suggests a two-time-scale analysis with goals adapting more slowly than the policy.Source: §6 · p. 12

7. AI Disclosure

The disclosure describes AI assistance in literature review, drafting, and research development, while attributing the paper’s structure and approach to the authors. The appendix notation table collects symbols shared across the main text and appendices.

7. AI Disclosure

  • The authors say AI assisted literature follow-up and revision, while the abstract and much of the introduction were authored by them.They report post-hoc fact checking of AI-generated literature-survey text and repeated checks of the final product.Source: §7 · p. 13
  • The authors attribute the equal-footing comparison and the decision to investigate adaptive goals to their work with AI agents.They report that AI agents produced counterexamples, while authors scrutinized intermediate decisions and shaped the search for theoretical claims.Source: §7 · p. 13

Appendix A. Notation

  • Table 2 collects notation shared by the main text and appendices, with some proof-local quantities defined where they occur.The appendix lists notation for information theory, Active Inference, goals, and learned abstractions.Source: Appendix A · pp. 21–22, Table 2 · p. 21

Appendix B. Conditions of Table 1

Appendix B specifies the assumptions and probability conventions behind Table 1’s bounds. The conditions differ across fixed rewards, adaptive goals, and learned abstractions.

Conditions of Table 1

  • Table 1 reports upper bounds with probability 1 −δ except row 10, while lower bounds are in expectation except rows 6, 12, and 16, which have stated probability guarantees.Rows 9 and 10 also average over a prior; row 6 is deterministic.Source: Appendix B · pp. 22–23

Fixed reward function

  • For fixed rewards, several rows require specified horizon, state, action, or episode thresholds, and rows 1, 6, 9, and 14 are minimax statements because their hard MDP depends on K.Rows 2 and 3 require T ≥ H^4X^3A and T ≥ H^3X^3A, respectively.Source: Appendix B · p. 23

Adaptive goals and learned abstractions

  • Rows 9–13 assume exact abstractions and goals revealed before each episode, while rows 14–17 concern realizable block MDPs with latent rewards.For rows 9–12, goals are history-dependent; row 13 fixes goals and start states before the first episode.Source: Appendix B · p. 23

Adaptive goals

  • Under adaptive goals, rows 9 and 10 use a Gaussian family with horizon 2 and X = 2Y + 1, while row 12 requires X ≥ X0 = O(ln(n0/δ)).Rows 9 and 10 let the adversary choose start states and use the transition law; row 9 concerns goal-memoryless agents.Source: Appendix B · p. 23

Learned abstractions

  • For learned abstractions, row 14 takes A = 2, H ≥ 3, and K ≥ S; row 15 requires S ≥ 12 and β < 0.09/∆, while row 17 assumes a fixed start state.Row 16 concerns agents scoring candidates by their own-label likelihood and applies after k0 = O(H ln(HK/δ)) episodes.Source: Appendix B · p. 23

Appendix C. Further Related Work

Appendix C relates the paper’s analysis to work on exploration, adaptive goals, and abstraction learning. Appendix D specifies the agents and generative models used in the comparisons.

Appendix C. Further Related Work

  • Information-gain and ensemble-disagreement bonuses lack regret guarantees in deep RL, and Theorem 2 applies to their tabular counterparts because both measure information or posterior variance.The appendix connects calibrated widths to Dirichlet quantile bounds and notes a Gaussian-process analogue: information gain is quadratic in posterior standard deviation, while GP-UCB width is linear.Source: Appendix C · pp. 23, 25
  • Prior adversarial-reward results compare against a best fixed policy and reveal rewards after episodes, whereas this paper reveals each goal beforehand and compares with that goal’s optimum.The cited settings are not nested; here the adversary may choose goals from the agent’s samples.Source: Appendix C · pp. 23–24
  • The paper relates representation selection to self-prediction and value-equivalence, showing that own-label likelihood can favor an abstraction merging states with different best actions.In block MDPs with latent rewards, Theorem 5 incurs ln |Φ| rather than the cited hard-selection factor √|Φ|.Source: Appendix C · pp. 24–25

D.1. Baseline Algorithms and Cited Bounds

  • The appendix specifies variants of AIF and CaI and restates the value-based baselines, including Bayes-UCBVI’s posterior-quantile optimism and UCBVI-BF’s Bernstein–Freedman bonus.Bayes-UCBVI uses a Dirichlet posterior over transitions; UCBVI-BF combines empirical variance, a range correction, and an optimism-certifying term.Source: Appendix C · p. 25, §D.1 · p. 26

D.2. Generative Models

  • The generative models represent abstract states as latent states; with learned abstractions, candidates have transition and emission rows and are scored by marginal likelihood.For a fixed abstraction, the emission factor drops out of the posterior over transitions; the paper cautions that abstraction-map ratios are not likelihood ratios.Source: §D.2 · pp. 28–29

D.2.1. ACTIVE INFERENCE

  • AIF’s expected-free-energy objective combines expected reward and information, while its state entropy term contains transition novelty once and may retain non-vanishing aleatoric entropy.The analyzed variant adds novelty separately, counting it twice; the paper notes this choice does not change its results.Source: §D.2.1 · p. 30

D.2.2. CONTROL AS INFERENCE

This section derives control-as-inference planning and lists the analyzed algorithms. It also states how abstraction error accumulates across an episode.

D.2.2. CONTROL AS INFERENCE

  • Control as inference places reward in the likelihood of an optimality variable, yielding soft backups under the structured variational family.Without that structured constraint, the optimal dynamics factor uses a geometric mean rather than the posterior-mean transition kernel.Source: §D.2.2 · p. 30
  • In the learned-abstraction model, the episode predictive law is a mixture of products, and the authors derive no CaI planner for that model.The table of analyzed agents uses a shared abstract space and posterior for AIF, calibrated AIF, and CaI.Source: §D.2.2 · p. 30, §D.3 · p. 31, Table 4 · p. 31

D.3. Algorithms

  • The analyzed AIF softmax assigns every action probability at least e^(-βr0H/A), giving linear regret at every fixed β.Making this probability floor vanish requires β → ∞, which removes AIF’s epistemic terms from the action rule.Source: §D.3 · p. 32

E.1. Representation Error

  • Abstraction transition errors compound over remaining steps, producing an H^2 factor in the representation-error bound.The projected process {ϕ(sτ)} is generally not Markov.Source: §E.1 · p. 33

E.2. Proof of Theorem 1

The proof analyzes regret from acting through an abstraction, separating abstraction bias from regret in the abstract MDP and establishing a deterministic lower bound proportional to representation error. It also shows that exact abstractions recover the abstract-MDP setting, while abstraction-induced indistinguishability can lead to linear regret.

PART (A), UCBVI-CH

  • UCBVI-CH retains approximate optimism despite non-identically distributed abstract transitions, with the proof bounding optimal-value bias and policy-evaluation gap by εrep(ϕ) each.Its three-way decomposition isolates those terms from regret in the abstract MDP.Source: §E.2 · p. 34, PART (A), UCBVI-CH · p. 36

PART (B), BAYES-UCBVI

  • Bayes-UCBVI’s proof establishes approximate optimism and a direct regret bound for Dirichlet-optimistic agents, but its range-based analysis costs a factor H versus the variance-aware analysis.The paper leaves open whether the variance-aware analysis survives misspecification because its concentration steps involve data-dependent values under non-identical sampling.Source: PART (B), BAYES-UCBVI · pp. 38–39

PART (C), EXACT ABSTRACTIONS

  • When ηR = ηP = 0, abstract data follow Mϕ exactly, so UCBVI or Bayes-UCBVI regret bounds apply there with S replaced by X.With zero representation error, the optimal-value bias and policy-evaluation gap vanish, making regret in Mϕ equal regret in M.Source: PART (C), EXACT ABSTRACTIONS · p. 40

E.3. The Cost of Acting Through an Abstraction

  • For every H ≥ 4 under the stated η condition, an S = 4, A = 2 MDP makes every agent observing only ϕ incur deterministic regret at least εrep(ϕ)K/32.The abstraction merges states with different best actions, causing the agent to choose incorrectly half the time.Source: §E.3 · p. 40
  • Because pool transitions make the ground state uniform and observations have the same law under either state, an abstraction-based agent chooses correctly with probability 1/2, entering the goal at rate δ0 rather than the optimal 2δ0.With m transitions left, the corresponding values are v(H − 2; δ0) for the agent and v(H − 2; 2δ0) for the optimal policy.Source: §E.3 · p. 40
  • The lower bound follows by comparing the goal-entry probabilities over the remaining H − 2 steps, with each value summand bounded below using δ0.The proof uses 1 − (1 − δ0)^j ≥ 1 − e^(−jδ0) ≥ jδ0 − 1/2(jδ0)^2 ≥ 3/4 jδ0.Source: §E.3 · pp. 40–41
  • Every admissible policy has deterministic regret at least ε_rep(ϕ)K/32 when each episode starts at s0.The proof derives a per-episode gap of at least ε_rep(ϕ)/32; the bound holds for every agent in the class.Source: §E.3 · p. 41

E.4. The Price of an Unstructured Class and Proof of Corollary 1

The section establishes regret costs for acting through an abstraction, including lower bounds for unstructured classes, and analyzes how novelty compares with valid confidence widths. It also identifies count and variance conditions relevant to the novelty-width comparison.

E.4. The Price of an Unstructured Class and Proof of Corollary 1

  • Every agent in the unstructured family has worst-case expected regret at least HST/300, while an agent that knows the decoder has eO(H√T) regret.The family consists of realizable block MDPs with at most five latent states and latent rewards.Source: §E.4 · pp. 41–42
  • The corollary combines a representation lower bound ε̄K/32 with an exploration lower bound HXT/300 on some member of the class.The representation term comes from an abstraction that merges states with different best actions; the exploration term holds even for the identity abstraction.Source: §E.4 · pp. 41, 43
  • Beyond T* = cH^3SAL^2, the ground-state bound is below ε̄K/64, while below T* acting through the abstraction can be beneficial.The comparison orders guarantees rather than the regrets themselves.Source: §E.4 · p. 43

F.1. Exact Identity and Bounds for Novelty

  • For Dirichlet posteriors with each category’s α_i ≥ 1, novelty is, up to a factor of 6, the number of categories with mass minus one per unit of posterior mass.The exact identity expresses novelty as the expected divergence of a posterior draw from its mean distribution.Source: §F.1 · pp. 43–44

F.2. Proof of Lemma 1

  • Once n̄ ≥ 64X^2/(νH^2), novelty is of the order of the square of any valid width, rather than the width itself.The comparison concerns validity at a fixed count.Source: §F.2 · p. 45
  • The lower-tail argument is for counts fixed in advance; at data-dependent counts its probability can be smaller, and the result’s second part requires a variance condition.The condition concerns the next-step value being constant on the support of the posterior transition distribution.Source: §F.2 · p. 45

F.3. Proof of Theorem 2

The proofs exhibit regret from insufficiently calibrated novelty, AIF’s persistent state term, and softmax exploration, while also bounding the cumulative novelty budget. They specify the settings and mechanisms behind these results.

F.3. Proof of Theorem 2

  • When n0 grows with K as in Bayes-UCBVI, Proposition 4 yields E R_K = Ω(K/ln K) at constant λ and r0 on a K-dependent MDP.The construction is an exact-abstraction MDP.Source: §F.3 · pp. 45–46

Appendix F.2. The Paley–Zygmund inequality therefore gives P

  • At λ=1, a 2^-64 run of 64 risky episodes reaching b leaves the risky index 0.191 below the safe index 1/4, yielding E R_K ≥ 2^-64(K−64)/4.The same lock-out mechanism applies to an exponent-1/2 bonus at constant weight.Source: Appendix F.2 · p. 48

F.4. Proof of Proposition 1

  • Softmax AIF and CaI assign every action probability at least e^-βr0H/A, yielding E R_K ≥ KΔe^-βr0H/A when every start state has a gap-Δ action.The probability floor holds for every prior count n0.Source: §F.4 · pp. 48–49

F.5. AIF’s State Term

  • Under exact perception, AIF’s state term is at most ln(X + 1) and converges to the true next-state entropy, which remains positive unless the transition law is deterministic.This persistent term can therefore remain even as row counts grow.Source: §F.5 · p. 49
  • Even with P* and R*, AIF prefers a branch losing (H−1)Δ per episode and incurs E R_K ≥ K(H−1)Δ/2.CaI, which lacks the state term, prefers the optimal branch for every β > 0.Source: §F.5 · pp. 49–50

F.6. The Novelty Budget

  • With Bayes-UCBVI’s prior, novelty accrued on each row is at most Γϕ(1 + ln K) ≤ X(1 + ln K), so the novelty budget grows logarithmically in T.The argument applies on any trajectory, whatever policy generated it.Source: §F.6 · p. 50

F.7. Proofs of Lemma 7 and Theorem 3

These proofs characterize regret bounds and optimism guarantees for novelty-based and value-specific indices, including calibrated AIF’s optimism across goals and the limits of indices when goals are chosen after observing data.

F.7. Proofs of Lemma 7 and Theorem 3

  • Calibrated AIF’s bound exceeds Bayes-UCBVI’s by √Γϕ and the variance-aware exact-abstraction bound by √(HΓϕ), because novelty measures uncertainty in the whole transition row.For a row with m positive-mass categories, novelty lies between (m − 1)/(6n̄) and (m − 1)/(n̄ + 1), within constant factors of a count bonus and uniform over value functions.Source: §F.7 · p. 52

Appendix G. Proofs for Section 4

  • For goal-memoryless agents, decisions across goals amount to an ℓ1 estimate of the transition law, letting an adversary choose a goal aligned with its error.Agents that use past goals as data can learn from them; the described lower-bound adversary instead leaves projection signs unresolved until about K/Y samples, causing each episode to cost a constant fraction of the projection’s value.Source: Appendix G · p. 53

G.1. Optimism for Every Goal and the First Claim of Theorem 4(c)

  • Calibrated AIF with a uniform prior is optimistic for every goal sequence on Eℓ1, while its regret bound holds for each adversary separately.For H = 2, the regret bound also holds on Eℓ1 for all goal sequences at once.Source: §G.1 · pp. 53–54

G.2. Lock-Out of Value-Specific Quantiles and the Price of Simultaneous Optimism

  • With probability at least 1 − e^{−(X−1)/32}, Bayes-UCBVI locks out of the optimal action under a history-based goal sequence and loses at least √ℓ1/(4n1) per later episode.The construction applies for exact abstractions, sufficiently large X, and A = H = 2; the stated lock-out result is not claimed for UCBVI.Source: §G.2 · pp. 55–56
  • Any index optimistic for all goals at once must overestimate some goal by order (H − 1)√(X/n), matching calibrated AIF’s uniform-prior width.The argument turns a goal-uniform index into an ℓ1 estimate of the successor law, so a small overestimate would imply an estimator that is too accurate.Source: §G.2 · p. 56
  • The proof tests each paired successor’s sign: a wrong sign forces combined absolute estimation error of at least ε/m, and the sample-pair count controls the error probability.The pair count is Bin(n, 1/m), and when it is at most 2n/m the sign error probability is at least 1/8; the expected number of wrong signs is therefore at least m/8.Source: §G.2 · pp. 56–57
  • The sign-testing argument yields a probability of at least 1/16 that the estimated successor distribution has L1 error at least ε/16.If the error event intersects E, then W ≥ ε/32 = X/n/256; multiplying by H − 1 gives the lemma’s bound.Source: §G.2 · p. 57
  • At a fixed count, the lemma applies to calibrated AIF on Proposition 7’s MDP, while Bayes-UCBVI underestimates a goal chosen after the data.Calibrated AIF’s index depends on the observed successors and the adversary’s independent randomness, and is optimistic for all goals on Theorem 4(c)’s event.Source: §G.2 · p. 57

G.3. Proof of Theorem 4(b)

The proof establishes a regret lower bound for goal-memoryless agents, using concentration and tape tools to analyze how observations across phases inform behavior at each start state. A phased adversary limits information about a hidden sign, leaving substantial expected loss that is aggregated across blocks under the stated conditions.

G.3. Proof of Theorem 4(b)

  • For goal-memoryless agents, prior-block information is independent of the current start-state transition law, and action probabilities depend on its observed samples, goal, and fixed randomness.This reduction supports applying the single-start-state argument block by block.Source: §G.3 · pp. 58–59
  • Each start-state block incurs expected regret at least (H − 1)√(Y K′)/16000, yielding an aggregate lower bound across the M blocks.Here K′ = K/M, and the bound is averaged over the Gaussian prior on transition laws.Source: §G.3 · p. 60
  • A threshold rule lets the adversary choose goals that cause at least (H − 1)∆k/4 expected regret per episode, where ∆k measures threshold error.The thresholds induce an estimate of P; Lemma 9 ensures its ℓ1 error is at least ε/64 simultaneously for all k and sample counts n, with probability at least 3/4.Source: §G.3 · pp. 57, 61

G.4. Concentration Tools

  • The appendix states standard sub-Gaussian concentration facts and represents transition samples as an i.i.d. tape of labeled successor-pair signs.The agent and adversary determine when entries are read, while fixed tape entries retain their stated properties regardless of that rule.Source: §G.4 · p. 62
  • The sphere-projection argument reduces a fixed-vector projection to a one-dimensional sphere coordinate and derives its tail control from that coordinate’s density.The lemma assumes the sphere lies in a subspace of dimension at least four.Source: §G.4 · p. 64
  • Lemma 16 bounds increment noise uniformly: it controls the norm below, projection onto a fixed low-dimensional subspace, and correlation with vectors in that subspace.These bounds hold simultaneously for all coefficient vectors with probability at least 1 − δ over the signs.Source: §G.4 · p. 64

G.5. Proof of Theorem 4(a)

  • The adversary uses phases with free samples and cap-conditioned goal directions; the proof’s side-information augmentation preserves the lower bound for the original adversaries.It reduces to one start state, then argues the adversary can privately simulate the free samples and compute its directions from the transition law and history.Source: §G.5 · pp. 66–67
  • On an event with P(T^c) ≤ C/m, every phase has ||w_f||^2 ≥ m/2, so none is neutral.The proof also bounds cap correlations by 2z0 and shows the constructed directions are not clipped on this event.Source: §G.5 · pp. 68–70
  • For increment combinations, the projection onto prior cap directions is at most 0.11 + η.The proof bounds the contribution from the mean increments using Lemma 17 and the noise contribution using Lemma 16’s B3.Source: §G.5 · p. 69
  • For a non-neutral phase, the posterior sign imbalance is bounded by δK + af, where af is the posterior mass outside Gf.The proof also bounds the expected mass outside Gf by C/m; on Gf, the posterior probabilities of paired parameters differ by at most the factor e^δK.Source: §G.5 · p. 71
  • The observation laws under the two coupled parameter distributions have expected total variation distance at most 0.21.The proof uses a KL bound for one sample, extends it to at most L samples by the chain rule and convexity, then applies Pinsker’s and Jensen’s inequalities.Source: §G.5 · p. 71
  • Each episode in a phase costs at least D0/6 in expectation, and the phases contain at least K/2 episodes.The proof obtains this using a lower bound on the posterior sign uncertainty, with a C/m term also covering histories with a neutral phase.Source: §G.5 · p. 72
  • The proof concludes with a regret lower bound of Y^1/4 sqrt(MK/ln Y)/3700, with m = Y/2.The preceding block-level expression is m^1/4 sqrt(MK/ln m)/3072.Source: §G.5 · p. 72

G.6. Agents That Use Past Goals as Data

Across adaptive goals, fixed-in-advance goals, and learned abstractions, the results distinguish when past goals help and when observation-based abstraction selection can fail. They also show that a decoder-free predictive score may favor a coarse abstraction that cannot reveal its own error.

G.6. Agents That Use Past Goals as Data

  • For adaptive goals and start states, every goal-memoryless agent incurs regret at least MYK/6000 for some adversary when Y ≥600 ln(3K) and K ≥MY.An agent using past goals as data attains at most a factor Y^1/4 on the hypercube family; whether it incurs any factor remains open.Source: §G.6 · p. 72
  • An agent that uses past goals as data can attain regret at most the stated upper bound against every adversary, after minimax converts adversary-specific agents into one agent for all adversaries.The construction rounds goals and uses the minimax theorem; the appendix notes that the constants are unoptimized and the separation appears only for very large Y.Source: §G.6 · pp. 72, 74

G.7. Goals Fixed in Advance

  • For goals and start states fixed before the first episode, UCBVI-CH has the bound of Proposition 9, while goals chosen from observed transitions invalidate the proof’s independence condition.The stated scope is horizon 2, with bounds in expectation over the prior; the fixed-goal price also requires the adversary to choose start states.Source: §G.7 · p. 75

H.1. AIF’s Selection by Observations

  • Posterior averaging predicts ground states consistently, with at most ln |Φ| nats of log-loss beyond the true abstraction’s Bayesian prediction, but its emission information still directs exploration.A candidate-dependent self-prediction target has no known regret guarantee in the cited discussion.Source: §H.1 · pp. 75, 77
  • AIF’s emission information can make it prefer a worse action, yielding regret at least (∆/2) min{K, ⌊(S −2)/2⌋}; calibrated AIF and CaI have the same regret law across S on this instance.The emission novelty from sparsely sampled blocks drives the preference; the enactive agent has regret e O(√T) for every S.Source: §H.1 · p. 76
  • A latent-predictive agent can confirm a coarse abstraction and incur regret at least H(K −k0)/128, whereas GOLF on the candidate set has regret e O(H2√T).The coarse abstraction merges states with different best actions; its labels and actions fit an episodic MDP, so acting through it cannot expose the error.Source: §H.1 · pp. 76–77

H.2. Proof of Proposition 12

The proof bounds the cost of averaging predictions across candidate abstractions and converts it into cumulative prediction error. It also bounds the oracle’s divergence under the exact-abstraction assumption.

H.2. Proof of Proposition 12

  • Posterior-averaged predictions incur cumulative log-loss at most ln |Φ| beyond predictions using the true abstraction’s Bayesian model.The posterior over abstractions is updated from their likelihoods, and the averaged prediction is their posterior-weighted mixture.Source: Proposition 12 (The selection cost of… · p. 77
  • The cumulative L1 prediction error is bounded by √(2T DT) plus the stated selection-cost term.This follows by comparing the averaged prediction with the true conditional transition law and applying the bound on cumulative predictive divergence.Source: Proposition 12 (The selection cost of… · pp. 77–78
  • For any history-measurable value function with range H, the cumulative error of averaged predictions in that value function is also bounded, up to factor H/2.Source: Proposition 12 (The selection cost of… · p. 78
  • Under Assumption 1, the oracle’s cumulative predictive divergence is O((X2A+S)H ln T).The bound combines transition-row and emission-row contributions to the exact abstraction’s divergence.Source: Proposition 12 (The selection cost of… · p. 78

H.3. Proofs of Theorem 5 and Propositions 10 and 11

These proofs establish regret control for value-based abstraction learning and analyze failures of observation-based curiosity and latent prediction. Their results depend on exact abstraction, latent-reward structure, and the stated learning settings.

H.3. Proofs of Theorem 5 and Propositions 10 and 11

  • GOLF’s version-space analysis uses a Bellman-residual radius based on the covering number of the value-function class, and its proof extends to history-selected latent goals.The proof establishes concentration, optimism, and coverability for each goal in a finite cover, then applies the resulting bound to the selected goal.Source: §H.3 · pp. 80–81
  • On the known-decoder instance, AIF’s emission novelty makes it choose the worse action for up to min{K, ⌊(S −2)/2⌋} episodes, with regret at least (∆/2) min{K, ⌊(S −2)/2⌋}.Each exploratory action adds observations to sparsely sampled emission rows; calibrated sensory bonuses can preserve the preference when g(0.09) > ∆.Source: §H.3 · pp. 81–82
  • For calibrated AIF and CaI, the action and regret laws are identical across S on this instance, while the enactive agent’s regret is O(H2√T), independently of S.Source: §H.3 · p. 82
  • Latent prediction can select the coarse abstraction ψ, after which every episode incurs regret at least H/128 and total regret is at least H(K −k0)/128.GOLF on the same candidate set has regret O(H2√T); ψ merges states whose best actions differ, while its induced labels and actions follow an episodic MDP.Source: §H.3 · p. 83

Related papers

Loading 2610.19046v1…