Overview
This work investigates the relationship between Bayesian updates and coalgebraic determinisation, specifically demonstrating that unifilarisation, as applied to stochastic Mealy machines, corresponds to a form of coalgebraic determinisation. The study extends the classical powerset construction, a determinisation procedure for nondeterministic finite automata, into a more generalized coalgebraic setting.
Research Context
The powerset construction serves as a fundamental method for determinising nondeterministic finite automata. In a coalgebraic framework, this construction has been generalized to 'structured coalgebras,' which are coalgebras augmented with additional data. For stochastic Moore machines, a specific type of structured coalgebra leveraging the distribution monad, the determinisation construction yields a semantics that assigns a distribution over the current output for each finite input word. However, this semantics is considered too coarse for scenarios where intermediate observations are critical, such as in the context of agents engaged in Partially Observable Markov Decision Processes (POMDPs) within control theory and reinforcement learning. In these situations, agents are required to condition on all observed data to inform future planning, not solely on the final output. The category-theoretic community has addressed this requirement through a procedure known as 'unifilarisation.' In the context of this research, unifilarisation transforms a stochastic Mealy machine into a new machine whose states represent priors over the original state space, with transitions defined by Bayesian filtering.
Approach
The research establishes that unifilarisation can be understood as an instance of coalgebraic determinisation. To achieve this, the study focuses on Mealy machines constructed over monads that possess additional structural properties, generalizing the concept of a distribution's support. Within this specific setting, the authors show that the general determinisation procedure naturally gives rise to unifilarisation.
Findings
The central finding is that unifilarisation, in the context of stochastic Mealy machines operating over monads with support-generalizing structures, directly emerges from the general framework of coalgebraic determinisation. This implies that the sophisticated conditioning on intermediate observations achieved by unifilarisation can be framed within the established theory of coalgebraic determinisation.
Further, the research compares the resulting final coalgebra semantics derived from this approach with the previously established Moore-style semantics. While the Moore-style semantics associates each finite input word with only a distribution on current outputs, the newly derived semantics, which incorporates unifilarisation, yields 'causal stochastic behaviours.' These behaviours are characterized as families that map input words to distributions on output words. A key constraint for these causal stochastic behaviours is that outputs must not depend on future inputs, thereby maintaining causality.
Why This Matters
The established connection between unifilarisation and coalgebraic determinisation addresses a recognized limitation in the semantics for stochastic Moore machines, particularly for applications requiring conditioning on intermediate observations. This refinement is pertinent for theoretical models underpinning agents in POMDPs, control theory, and reinforcement learning, where planning decisions necessitate a comprehensive understanding of past observations, not just final outputs. The provision of causal stochastic behaviours offers a more granular and appropriate semantic representation for systems where the sequence and dependency of observations are critical for future actions.