sec-rivest-schapire-diversity

5.4.1 Diversity representations: learning tests instead of states

Rivest and Schapire give a particularly revealing alternative to literal state reconstruction [ Rivest and Schapire , 1994 ] . Let \(B^*\) be the free monoid of action strings and let \(P\) be a family of Boolean predicates on the state set \(X\). A test is a pair \(ap\in B^*P\), with semantics

\[ \operatorname {val}(ap)(x)=p\bigl(\delta (x,a)\bigr). \]

Two tests are equivalent when they have the same value at every state. The diversity

\begin{equation} D=\left|B^*P/{\equiv }\right|, \qquad ap\equiv a'p' \Longleftrightarrow \operatorname {val}(ap)=\operatorname {val}(a'p'), \end{equation}

5.6

measures the number of distinct observable tests, not the number of global states. Prefixing a test by an action descends to this quotient and produces an update graph. The values of the quotient tests at the current state, together with that graph, suffice to simulate every admitted experiment.

The Rubik’s Cube example makes the point vivid. The modeled environment had about \(10^{19}\) global states but diversity \(54\); their implementation learned the test representation while visiting only a minute fraction of the state space. What was compact was not a list of cube configurations. It was a generating family of observations together with the action-induced rules for transforming them.

Proposition 5.7 Categorical test-quotient construction

Let \(\mathcal C\) be a category, \(X\in \mathcal C\), \(\Omega \) an observation object, \(G\subseteq \mathcal C(X,X)\) a family of action generators, and \(P\subseteq \mathcal C(X,\Omega )\) a family of observations. Let \(\mathbb A\) be the submonoid of endomorphisms generated by \(G\), and let

\[ \mathcal T=\{ p\circ a\mid a\in \mathbb A,\ p\in P\} \subseteq \mathcal C(X,\Omega ). \]

For any congruence \(\sim \) on \(\mathcal T\) preserved by precomposition with the generators, each \(g\in G\) induces a well-defined update \(U_g([t])=[t\circ g]\) on \(\mathcal T/{\sim }\). Hence a finite separating quotient \(\mathcal T/{\sim }\), its generator updates, and its current evaluation form a compact predictive presentation of the admitted experiments.

Proof ▼

If \(t\sim t'\), preservation by precomposition gives \(t\circ g\sim t'\circ g\), so \(U_g\) is independent of representatives. Iterating the \(U_g\)’s evaluates every word in the generated action monoid. Separation says that no distinction visible to the admitted tests is lost.

This proposition suggests the categorical generalization that the original construction leaves implicit. Replace the one-object action monoid by a typed action category or algebraic theory. Its actions act contravariantly on observable predicates by precomposition, producing a test presheaf; quotient that presheaf by the observational congruence detected in interaction. The learning target is then a compact presentation of the resulting action on tests. In theory-bearing UOCL, one may go further and learn generators and relations for both the action theory and its test module. This avoids constructing a global state model unless some later query actually requires one.

Boundary

Low diversity is relative to the chosen actions and observations. A compact test quotient can be sufficient for prediction while omitting distinctions needed for control, causality, safety, or transport. UOCL must therefore record the query doctrine under which the quotient is separating.