On the equivalence of learnability and ergodicity

April 24, 2021

Ergodic state-action sequences are learnable:

If a process \(X(t) = \{(s(t),a(t))\}\) evolving in a compact state-space \(X\) is ergodic then its statistical properties may be deduced from a sufficiently long sequence of observations. Moreover, if we make the reasonable assumption that the observations are discretised and coarse-grained then the observable state-space \(\widehat{X}\) is finite.

By the universal approximation theorem for neural networks, there exists a sufficiently deep and wide neural network which may approximate the discretised process \(X_N \in \widehat{X}^N\) arbitrarily well.

Learnable state-action sequences are ergodic:

If a process \(X(t) = \{(s(t),a(t))\}\) is learnable then its statistical properties may be inferred from a sufficiently large number of observations. Moreover, in order for the resulting scientific model to be cross-validated the experiments must be repeatable and therefore \(X(t)\) is ergodic.

Note: This theorem may be generalised and extended in several different ways.

References:

\(1.\) Pauli Space. Ergodic processes and the scientific method. 2021.

\(2.\) Pauli Space. Learnability and PAC-learnability. 2021.

\(3.\) G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst., 2(4):303–314, 1989.

\(4.\) R. S. Sutton and A. G. Barto, Reinforcement Learning. The MIT Press, 1998.

On the equivalence of learnability and ergodicity - April 24, 2021 - Pauli Space