Monadic Comonad for Markov Decision Processes

The Spivak–Myers comonad on makes dynamical systems into its coalgebras. Twisting its directions by a strong monad makes the transitions effectful, and at the right shapes the coKleisli morphisms are exactly Markov decision processes. This note records the comonad and the reading of its coKleisli category.

The monadic comonad

For a strong monad on define on a polynomial by

Positions are untouched; each direction set is wrapped by .

Proposition. is a comonad

is a comonad on , with counit built from the monad unit and comultiplication built from the monad multiplication , both applied on directions with positions fixed. The identity monad recovers the Spivak–Myers dynamics comonad, whereas a general threads an effect through every state transition.

Its coKleisli category is MDPs

The coKleisli category keeps the objects of and sets .

Proposition. coKl(W) is the category of -MDPs

At the state and the interface a coKleisli morphism unpacks into a readout together with an effectful update . When is the distribution monad this is exactly a Markov decision process, carrying states, actions, observations, and stochastic transitions. Thus is the category of -MDPs, composing transitions through .

Remark. An effectful container comonad

is a comonad whose positions are shapes and whose directions are -wrapped, so it sits beside the container/polynomial reading of data structures. That reading asks which containers are monads, whereas the object of interest here is a comonad whose coalgebras are effectful transition systems. It is an effectful generalisation of the Spivak–Myers Poly comonad.

References

• N. Niu and D. I. Spivak, Polynomial Functors: A Mathematical Theory of Interaction (2024)
• D. J. Myers, Categorical Systems Theory (book, 2022)