Source-linked AI summary
The Free Inference Dimension: Complexity Measure for Zero-Collision Navigation under Hypothesis Mixtures
Luiz Carlos Castro Guedes, Edward Hermann Haeusler
TL;DR
The paper asks what combinatorial capacity explains collision-free navigation by a value-mixture agent without identifying the true environment. It formalizes that capacity with the Free Inference dimension and develops a complementary PMS dimension and hybrid strategy. It reports a stable critical-density range and a fine-resolution transition band in its grid-world setting.
Problem
In nested environment families, the sharp transition between coherent and incoherent value-mixture navigation lacks a combinatorial dimension that captures trajectory-level success rather than pointwise correctness.
Source: §1 · p. 2Method
The paper defines dFI through shattering constraint cells across nesting assignments, develops an ε-relaxation, and pairs it with a PMS identification dimension and a VM-then-PMS hybrid.
Source: §1 · pp. 2–3Results
dFI is strictly below VC, while Random-Maze critical density is approximately 0.65–0.70 and fine resolution reveals a band where tolerated margin violations increase usable capacity.
Source: §9 · pp. 14–15Takeaways & Limitations
The paired dimensions describe zero-collision capacity and identification cost, while the hybrid rule offers a robustness, efficiency, and identification trade-off under structured environmental uncertainty on grid-worlds.
Source: §9 · p. 15The theory focuses on nested families; extensions to non-nested settings and multi-action trajectory-constrained control remain open.
Source: §2.1 · p. 3, §9 · p. 15
Abstract
from arXiv · showhide
Solomonoff induction frames prediction as a mixture over computable hypotheses, typically leading to identification of the true environment. In a finite meta-reinforcement learning setting with nested constraint families, in our previous work, we observe a different regime: a value-mixture (VM) agent achieves near-optimal, zero-collision navigation without identifying the true environment, a phenomenon we call Free Inference. This regime persists up to a sharp density threshold, beyond which performance degrades and posterior-mode selection (PMS) becomes preferable. We formalize this behavior via the Free Inference dimension dFI(S,N), a combinatorial measure of the environmental complexity a VM agent can handle while preserving trajectory coherence. We prove dFI is strictly smaller than the VC-dimension and relates to the Natarajan dimension up to a path-length factor, capturing the cost of non-decomposable loss. A PAC-style relaxation yields generalization bounds driven by dFI^(epsilon,delta). We also define a complementary PMS identification dimension and show that a hybrid strategy---averaging until the first collision, then switching to selection---is optimal, with links to Littlestone-type dimensions supported by grid-world experiments.
1 Introduction
The paper asks what combinatorial capacity underlies collision-free navigation by a value-mixture agent that does not identify the true environment. It defines the Free Inference dimension and develops related generalization, identification, and hybrid-strategy results.
1 Introduction
- Across nested environment families, value-mixture navigation remains collision-free without identifying the true environment up to a sharp density threshold; beyond it, navigation can become incoherent and PMS can outperform VM.The reported critical density is approximately 0.7 across grids from 10 × 5 to 100 × 50.Source: §1 · p. 2
- The Free Inference dimension dFI(S, N) measures the largest set of constraint cells that remains navigable under every N-level nesting assignment.The paper reports dFI < dVC for N ≥ 2 and an empirical coherence gap of approximately 0.3|S|.Source: §1 · p. 2
- The ε-Free Inference relaxation yields a generalization bound in which dε,δ controls the sample complexity of certifying coherent navigation on unseen nesting schemes.The bound is described as a PAC-style result.Source: §1 · p. 2
- The complementary PMS identification dimension is at most N − 1, and the hybrid “VM until first collision, then PMS” strategy is optimal in a precise sense.The paper also identifies an exponential gap between dFI = Θ(|S|) and Ldim = O(log N), and describes grid-world experiments to study dimension scaling and the bound.Source: §1 · p. 3
2 Abstract Setting
The setting uses finite, deterministic environments with shared start and goal states and nested obstacle constraints. The value-mixture agent averages candidate value functions, while Free Inference requires reaching the goal entirely within cells free in every candidate environment.
2.1 Environments and Constraints
- A structured decision environment has finite state and action spaces, deterministic transitions, asymmetric costs, and shared start and goal states.Each environment specifies obstacle and feasible sets.Source: §2.1 · p. 3
- A nested family orders obstacle sets by inclusion, and an entry-level assignment maps each constraint cell to one of N levels to generate the nested obstacle sets.There are N^|C| such assignments for a constraint-cell set C.Source: §2.1 · p. 3
2.2 Value-Mixture Agent and Free Inference
- Under uniform belief, the value-mixture agent acts greedily on the average value function, and Free Inference means reaching the goal while staying in cells free in every candidate environment.This is described as a zero-regret, zero-collision property.Source: §2.2 · pp. 3–4
- Because collision penalties dominate step costs, the averaged values veto actions unsafe in any hypothesis, but this can block the only exit from a consensus-free pocket and prevent reaching the goal.Thus local safety at each state need not ensure global trajectory coherence.Source: §2.2 · p. 4
3 The Free Inference Dimension
The Free Inference dimension is defined through a game in which a Constructor chooses constraint cells and nesting assignments, and the value-mixture agent must navigate coherently. A coherence score gives an arithmetic characterization of whether it succeeds on a fixed nested family.
3.1 The Shattering Game
- The FI-shattering game has the Constructor choose a constraint-cell set and an entry-level assignment, after which the VM agent wins exactly when Free Inference holds.A set is FI-shatterable when the agent wins for every assignment.Source: §3.1 · p. 4
- The Free Inference dimension is the maximum size of a constraint-cell set that is FI-shatterable.This parallels VC-dimension shattering but tests trajectory coherence across N-level assignments rather than pointwise realization of binary labels.Source: §3.1 · p. 4, Table 1 · p. 5
3.2 Characterization via Coherence
- For a fixed assignment, a non-negative margin along a path through the consensus feasible set certifies that the greedy mixture follows that path coherently.The coherence score is the minimum normalized margin along the widest-bottleneck path; when all actions have the same expected value, the margin is set to zero.Source: §3.2 · p. 5
- Free Inference holds on a nested family if and only if its coherence score is non-negative, yielding a computable characterization by checking the worst-case entry-level assignment.The characterization is described as not yet efficient to compute.Source: §3.2 · p. 5
4 Relationship to Classical Dimensions
This section positions dFI as a capacity measure for coherent Free Inference and contrasts it with VC, Littlestone, and Natarajan dimensions.
4.1 VC-dimension and the Coherence Gap
- For |S| > N + 2 and N ≥2, dFI(S, N) < dVC(HC1), because FI adds trajectory coherence to VC’s pointwise feasibility.The empirical coherence gap is ≈0.3 |S|, about 30% of grid capacity and a ≈43% overhead over the pointwise regime.Source: §4.1 · p. 6
4.2 Littlestone and Natarajan Dimensions
- dFI measures the maximum problem size allowing zero collisions, while col measures the maximum collision count; the two dimensions are incommensurable.The comparison is analogous to VC-dimension as capacity and Littlestone dimension as error count; Ldim(UN) = ⌊log2 N⌋, and col(S, N) ≤ N −1.Source: §4.2 · p. 6
- dFI(S, N) ≤ dNat(Hordinal, N) ≤ dFI(S, N) · Lmax, with Lmax the maximum path length from s0 to g through F ∗.The factor captures the cost of requiring Lmax pointwise conditions jointly for trajectory coherence; in grid-worlds, Lmax = O(W + H), so the gap is at most linear in grid diameter.Source: §4.2 · p. 6
5 ε-Free Inference and a PAC Relaxation
This section relaxes zero-error Free Inference into a margin-based PAC framework and examines its bounds and capacity near the density transition.
5.1 The ε-Free Inference Condition
- ε-Free Inference allows at most an ε-fraction of states on P ∗ to have negative margin, with collisions potentially restoring coherence through one-bump corrections.Strict Free Inference is the ε = 0 case; near-critical, a single collision can suffice to reach the goal.Source: §5.1 · p. 7
5.2 The PAC-Free Inference Dimension
- The PAC-Free Inference dimension dε,δ_FI is a relaxed complexity parameter satisfying dFI ≤ dε,δ_FI for ε, δ ≥0.Source: §5.2 · p. 7
5.3 Generalization Bound
- dFI controls how many tested nesting schemes are needed to certify coherent navigation on untested nestings with confidence 1−δ and tolerance ε.The proof uses uniform convergence with a Hoeffding bound adapted to the N-ary FI setting.Source: §5.3 · pp. 7–8
- The Hoeffding form held in 100% of informative configurations, including cases with empirical failure rate ˆpm ∈(0.2, 0.8).Source: §5.3 · p. 8
5.4 Graded Capacity at the Phase Transition
- For N = 10, C jumps from 0 to ≈−0.43 at coarse ∆ρ≈0.1, but resolves into a ≈0.10–0.15 band at ∆ρ=0.025.Within the band, dε,δ_FI increases with ε, and small ε increments admit larger constraint sets.Source: §5.4 · pp. 8–9
6 The PMS Identification Dimension and VM–PMS Duality
The paper defines PMS as MAP-expert action selection with belief updates after collisions, then pairs its identification cost with VM’s zero-collision capacity. An ε-aware hybrid uses VM within its supported regime and switches to PMS when collision behavior exceeds the band’s expected rate.
6 The PMS Identification Dimension and VM–PMS Duality
- PMS predicts the MAP expert’s action at each state, and a collision counts as a mistake that triggers a Bayesian belief update.The section distinguishes this posterior-mode mechanism from true Thompson Sampling, which samples a hypothesis from the posterior.Source: §6 · p. 9
- dPMS lies between ⌊log2 N⌋ and N−1: the lower bound is the optimal deterministic Littlestone mistake bound, while the upper bound occurs when each collision eliminates one environment.dPMS measures PMS’s worst-case collision count over nested families and choices of true environment.Source: §6 · p. 9
6.1 The VM–PMS Duality
- dFI and dPMS measure complementary costs: VM’s zero-collision capacity in constraint cells and PMS’s identification cost in collisions when zero-collision navigation is infeasible.The ε-relaxation supplies a gradient around dFI, where collisions remain rare but nonzero in an ε-dependent way.Source: §6.1 · p. 9
- The ε-aware hybrid keeps zero collisions below dFI and at most ε·|P*| within the transition band, switching to PMS when collisions exceed the band rate.Above the band, the first excess collision signals failure of ε-Free Inference; switching then costs at most dPMS −1 further collisions.Source: §6.1 · p. 10
7 Connections to Online Learning Theory
The paper connects Free Inference to randomized and Stackelberg–Littlestone learning, then identifies the non-adaptive environment as a key structural distinction from standard online learning.
7 Connections to Online Learning Theory
- Free Inference corresponds to zero expected mistakes in the Randomized Littlestone framing, while VM’s coherence recursion matches the Stackelberg–Littlestone tree-weight recursion.The paper identifies SSOA as the abstract counterpart of the VM action rule and its dVC > dFI separation as a finite instance of the zero-leader-regret result.Source: §7 · p. 10
- dFI = Θ(|S|), while Ldim(UN) = O(log N), an exponential capacity gap attributed to the non-adaptive adversary.The environment is committed before the episode, and visited states are determined by the agent’s trajectory.Source: §7 · p. 10
- On a 20 × 10 grid with N = 10, dFI ≈140 versus Ldim(U10) = 3, a ratio of ≈47.The paper describes the non-adaptive adversary as ≈47 times weaker in this example.Source: §7 · p. 10
8 Experimental Protocol
The experiments test how the critical density scales with family size, whether a Hoeffding generalization bound holds on held-out nestings, and whether finer density resolution reveals a continuous transition band.
8 Experimental Protocol
- The protocol uses nested Random-Maze families across six grid sizes and precomputed optimal Q-tables; Experiments A and B at N = 20 require additional training at intermediate densities.Experiment B reuses Qmix on a 100 × 50 grid with N = 20 density levels and samples training and held-out nestings.Source: §8 · p. 11, §8.2 · p. 12, §8.3 · p. 14
8.1 Experiment A: Scaling of the Critical Threshold in N
- Excluding the smallest grid, ρc rises from 0.50 at N = 2 to a plateau around 0.65–0.70, with N = 10 to N = 20 flat within resolution.The 10 × 5 grid is too sparse for the family to fail, leaving ρc pinned at 1.0.Source: §8.1 · p. 11, Table 2 · p. 12
- As N increases, intermediate environments reduce per-state Q-value disagreement, while the consensus free space still depends on the densest environment.On the 100 × 50 grid at ρ = 1.0, D(s) drops from ≈0.042 at N = 2 to ≈0.009 at N = 20; the paper interprets averaging as denoising, with diminishing returns as the density gradient fills in.Source: §8.1 · p. 12
8.2 Experiment B: Empirical Generalization Bound
- The Hoeffding bound held in 100% of 29 informative configurations, including held-out failure rates spanning 0.02–0.84.The experiments used 50 training and 50 held-out nestings; the below-threshold case had zero training and test failures at every level.Source: §8.2 · p. 13, Table 3 · p. 13
8.3 Experiment C: Fine-Resolution Phase Transition
- At fine resolution, the transition is continuous across a band of width ∆ρband ≈0.10–0.15, with the C-score changing over six successive density steps.At ρtest = 0.075, choosing ε ≈0.15 lifts the failure rate from 23% to near-zero.Source: §8.3 · p. 14, Table 4 · p. 14
9 Conclusion and Open Problems
The conclusion presents dFI and dPMS as complementary measures for when value averaging preserves collision-free navigation and when environment identification becomes useful. Grid-world results show a stable critical-density range that broadens into a transition band, while the paper identifies open extensions beyond its current scope.
9 Conclusion and Open Problems
- dFI and dPMS define three regimes: averaging below dFI, identification above relaxed capacity, and hybrid strategies near the boundary.The measures capture zero-collision capacity and PMS identification cost, respectively.Source: §9 · p. 14
- ρc ≈ 0.65–0.70 across Random-Maze families, with a fine-resolution band where small tolerated margin violations buy larger usable capacity.The band gives a graded rather than single-threshold capacity picture.Source: §9 · p. 15
- Safety tolerances can be translated into sample-complexity-controlled capacity, and non-adaptivity separates dFI = Θ(|S|) from a Littlestone scale O(log N).The hybrid rule offers a robustness, efficiency, and identification trade-off.Source: §9 · p. 15
- Open problems include non-nested families, multi-action trajectory constraints, finite-size transition scaling, and adversarial effects on critical density.The paper frames dFI as a tool for safe meta-RL under structured uncertainty on grid-worlds.Source: §9 · p. 15