Sergio Calo, Anders Jonsson, Gergely Neu, Ludovic Schwartz and Javier Segovia-Aguas (2025), Advances in Neural Information Processing Systems 38 (NeurIPS 2025).
Key takeaways
From the reading, NOTE-763.
- A kernel-free LP (Proposition 1). The coherence constraints of LIT-962’s LP, which multiply by P_X(x’|x), are equivalent to Σ_{y’} µ(x,y,x’,y’) = ν_X(x,x’) λ_X(y|x) for some conditional λ_X, and likewise for Y. Here ν_X is the discounted occupancy of consecutive state pairs, which can be sampled.
- A guarantee from samples (Theorem 1). SOMCOT reaches |⟨µ̄_K − µ*, c⟩| ≤ ε with probability 1−δ once K = O((|X||Y|(|X|+|Y|) + (|X|+|Y|)log(1/δ))/((1−γ)²ε²)). It uses one sampled transition per chain per step and Θ(|X|²|Y|²) computation per step, with no problem-dependent constants. The authors call it “the first result of its kind”. The claim that the ε⁻² rate is optimal is argued, not proved.
- The sampling model is narrower than the title. The theorem assumes independent draws from ν_X and ν_Y. Exact draws need a run of geometric length from the fixed initial state, so restarts are needed. Correlated pairs from one long trajectory are “abuse” the authors “expect” the method to survive. Every experiment uses independent draws.
- What must be known. The finite state spaces (the primal variable is a full table over pairs of state pairs), the states themselves in each sample, and the ground cost on every state pair. Only the kernels may be unknown.
- Uses shown. The averaged conditionals λ_X and λ_Y act as an encoder–decoder that recovers latent block structure. In a parametric family, the distance is smallest at the true model, including in a discretised pendulum that is not Markov. Tuning is “a grueling task”.
Standing in the record
Filed on 2026-10-12 from the owner’s papers-feed for QUESTION-008, and read
on 2026-10-14 in NOTE-763. The filing said the paper “would make
approximate bisimulation measurable for systems whose update structure is
not known”. The reading supports that only where the states are
observed: the kernel can be unknown, but the states cannot be latent.
The record’s fidelity notion (TERM-033) compares observed responses with
no shared latent state, which is the case the estimator does not cover.
The guarantee also assumes sampling with restarts, and the chains have no
actions. The estimation result is filed as THEORY-280, with no
answers: relation, since the question is Deferred. It rests on LIT-962
(THEORY-247) for the identification of the transport distance with
the bisimulation metric. The anthology-candidate flag stays: the
representation-learning and model-selection uses in §§5–6 are
machine-learning practice, and belong in the anthology if anywhere.