Differentiable Exact Learning
Differentiable Exact Learning
Researchers propose the Differentiable Exact Learning framework, which couples a state-tracking neural controller with an unbounded external environment to achieve extremely long generalization on arithmetic and general simulation tasks with small data. The training data are expert behavior trajectories that hide internal states and expose only observations and actions (policy trajectory observations, PTO). The paper's differentiable finite state transducer (DFST) uses multilinear updates, supports log-parallel training, can simulate any finite-state controller, and achieves computational universality through environment interaction; the authors reproduced the results on RNNs and GRUs and distilled a recipe for extremely long generalization of a state-tracking controller plus an unbounded external environment plus PTO. Its metric-extraction protocol can recover an interpretable discrete controller from a trained DFST, and the authors prove it is equivalent to the target arithmetic and general simulation algorithms; the discrete controller obtained by taking the argmax of the transition probabilities of a Softmax DFST can be proven to exactly perform universal Turing machine simulation and binary arithmetic. The exact-learning proof relies on several assumptions, which the authors support with experiments.