Reference Towards Foundations of Categorical Cybernetics [towards-cybercat]

Abstract

We propose a categorical framework for processes which interact bidirectionally with both an environment and a “controller”. Examples include open learners, in which the controller is an optimiser such as gradient descent, and an approach to compositional game theory closely related to open games, in which the controller is a composite of game-theoretic agents. We believe that “cybernetic” is an appropriate name for the processes that can be described in this framework. 

@article
{towards-cybercat, title={Towards Foundations of Categorical Cybernetics}, volume={372}, ISSN={2075-2180}, DOI={10.4204/EPTCS.372.17}, url={https://arxiv.org/abs/2105.06332}, journal={Electronic Proceedings in Theoretical Computer Science}, author={Capucci, Matteo and Gavranović, Bruno and Hedges, Jules and Rischel, Eigil Fjeldgren}, year={2022}, month={Nov}, pages={235–248} }

Backlinks

Open games in Monoidal categories [efr-CA6T]

Definition [efr-EGK8]

Let \mathcal {C} be a monoidal category. A selection relation on an object A \in \mathcal {C} is a relation \epsilon \subseteq \mathcal {C}(I,A) \times \mathcal {C}(A,I). We write \epsilon (a,k) for the statement (a,k) \in \epsilon .

Selection relations are ordered by inclusion, and so form a (posetal) category, which we denote \mathbb {S}_\mathcal {C}(A). Given f: A \to B, we define the pushforward on selection relations by f_*\epsilon = \{(fx,k) \mid (x, kf) \in \epsilon \}. In other words, f_*\epsilon (y,k) if and only if there exists x: I \to X so that fx = y and \epsilon (x, kf).

It is clear that pushforward is monotone, so that this defines a functor \mathbb {S}_\mathcal {C} : \mathcal {C} \to \mathsf {Cat}

Remark [efr-YKR3]

Of course, there is an equally good "pull-back" operation on selection relations given by \{(x,kf) \mid (fx, k) \in \epsilon \} (this is the pushforward in \mathbb {S}_{\mathcal {C}^\mathrm {op}}). These are adjoint representatives of the same profunctor, which should arguably be regarded as the primary object of interest---that is, we could work with a functor \mathcal {C} \to \mathsf {\mathbb Cat}, the category of categories and profunctors, where we say two selection relations \epsilon \in \mathbb {S}_X, \epsilon ' \in \mathbb {S}_Y are related by f :X \to Y if \epsilon (x, kf) \Rightarrow \epsilon '(fx, k).

However, we will stick with the pushforward definition for now, since it is conceptually simpler and good enough for our purposes.

Example [efr-BNB2]
  1. Let \mathcal {C} = \mathsf {Optic}(\mathsf {Set}). There is a selection function \mathrm {argmax}_X \in \mathbb {S}({\mathbb {R} \choose X}) defined by \mathrm {argmax}(x,f) if and only if x is a maximum of f. (Identifying maps I \to {\mathbb {R} \choose X} with points x \in X, and maps {\mathbb {R} \choose X} \to I with functions X \to \mathbb {R})
  2. In the same category, for each r \in \mathbb {R}, there is a selection function given by \epsilon (x,f) \Leftrightarrow f(x) \geq r. This corresponds to satisficing at the value r (Reference [simon-environment-satisficing])---that is, selecting any strategy which achieves this value or greater.
  3. For \mathcal {C} = \mathsf {Optic}(\mathcal {C}'), with \mathcal {C}' semiCartesian, there is a selection function \epsilon (x,k) \Leftrightarrow kx = x (using the same identification as above). The agents with this selection function are called predicting agents in Reference [bolt-hedges-winschel-predicting]. These agents attempt to predict the value the environment will return to them.
  4. For \mathcal {C} = \mathsf {Bun}^\mathrm {fop}, the fiberwise opposite of manifolds and smooth bundles---that is, the category of lenses between smooth manifolds---there is a selection function on the tangent bundle TX given by \epsilon (x,k) if and only if k(x) = 0---that is, if x is a fixpoint of the dynamical system identified by k: X \to TX.
  5. Let \mathcal {A} \to \mathcal {C} be a dynamical systems theory and work in the category of lenses. Suppose the monoidal structure on \mathcal {A} is Cartesian, so that a lens I \to {A \choose X} is the same as a map * \to X. Note that I = T(*) has a distinguished section given by the identity. Then there is a selection function on each object TX where a lens I \to TX, given by x: * \to X, is in equilibrium with respect to a lens TX \leftrightarrows I if x is a trajectory between those systems---that is, if it is an equilibrium state of the smooth dynamical system TX \leftrightarrows I. This subsumes the two previous examples.

Definition The Nash Product [efr-PTAE]

Let \epsilon \in \mathbb {S}(X), \epsilon ' \in \mathbb {S}(Y) be selection relations. Their Nash product \epsilon \boxtimes \epsilon ' \in \mathbb {S}(X \otimes Y) is given by \{(x \otimes y, k) \mid \epsilon (x,k(1_X \otimes y)), \epsilon '(y, k(x \otimes 1_Y))\}

Let us unpack this very dense definition. Given a context k: X \otimes Y \to I, a strategy I \to X \otimes Y is in equilibrium if:

  1. It decomposes as a tensor product of x: I \to X, y: I \to Y.
  2. Composing k with y, we obtain a map X \to I. This is the context of the first player assuming the second player plays y. x must be an equilibrium strategy for this map. Simultaneously, y must be an equilibrium for the analogous composite of k and x.

Example [efr-5E1V]

Consider the selection relation \mathrm {argmax}_X \boxtimes \mathrm {argmax}_Y on {\mathbb {R} \times \mathbb {R} \choose X \times Y}. A point (x,y) is an equilibrium for a function k: X \times Y \to \mathbb {R}^2 if and only if x maximizes k_1(-,y) and y maximizes k_2(x,-). In other words, if x,y is a Nash equilibrium (Reference [nash-noncoop-games]) in the usual sense for the game with payoff matrix k.

Proposition [efr-Z2BR]

The Nash product \mathbb {S}(X) \times \mathbb {S}(Y) \to \mathbb {S}(X \otimes Y), along with the map * \to \mathbb {S}(I) given by the full set S(I) \times S(I) equips \mathbb {S} with a lax monoidal structure.

Proof

It is trivial to verify associativity and unitality of the monoidal structure. The only hard part is to verify that \boxtimes is actually a natural transformation. To that end, let f: X \to Y and g: X' \to Y' be morphisms of \mathcal {C}. Let \epsilon \in \mathbb {S}(X), \epsilon ' \in \mathbb {S}(Y).

First consider the statement (f \otimes g)_*(\epsilon \boxtimes \epsilon ')(s,k). This holds if and only if s: I \to X \otimes Y factors as (f \otimes g)s' so that (\epsilon \boxtimes \epsilon ')(s', k(f \otimes g)). This in turn means s' = x \otimes x' and \epsilon (x, k(f \otimes f')(1_X \otimes x')) and analogously for \epsilon '.

Now consider the statement f_*\epsilon \boxtimes g_*\epsilon '. This means that s factors as y \otimes y' so that f_*\epsilon (y, k(1_Y \otimes y')) and analogously for y', which in turn means that y factors as fx so that \epsilon (x, k(1_Y \otimes y')f). Using the axioms of a monoidal category, it is straightforward to see that these two requirements on x, x' are equivalent, hence we have our naturality.

Corollary [efr-UI90]

Since \mathbb {S} is lax monoidal, its Grothendieck construction \int \mathbb {S}_\mathcal {C} acquires a monoidal structure (Reference [moeller-vasilakopoulou]). We write this category \mathcal {C}_\mathbb {S}---explicitly, it is given as follows:

  1. The objects are pairs (X,\epsilon ) where X \in \mathcal {C} and \epsilon \in \mathbb {S}(X) is a selection relation on it
  2. The morphisms are morphisms f: X \to Y so that, for every x: I \to X, k: Y \to I, \epsilon (x, kf) \Rightarrow \epsilon (fx, k)
  3. The monoidal structure is given by (X,\epsilon ) \otimes (Y,\epsilon ') = (X \otimes Y, \epsilon \boxtimes \epsilon ')

Now we are ready to make the slick definition of open games.

Definition [efr-1WGM]

Let \mathcal {C} be a semiCartesian symmetric monoidal category. The symmetric monoidal double category of open games in \mathcal {C} is \widetilde {\mathsf {Game}}(\mathcal {C}) = \mathsf {\mathbb Para}_{\mathsf {Optic}(\mathcal {C})_\mathbb {S}}(\mathsf {Optic}(\mathcal {C})).

Note that in this case, \mathsf {Optic}(\mathcal {C})(I, {A \choose X}) = \mathcal {C}(I,X), and \mathsf {Optic}(\mathcal {C})({A \choose X},I) = \mathcal {C}(X,A). Thus a selection function decides, for each payoff function X \to A, which of the states I \to X are suitable equilibria.

Before we proceed to the case of stochastic lenses, we will pause briefly to make a small modification to the preceding theory as presented in Reference [towards-cybercat]. In a game with forwards play function \Sigma \times X \to Y, there are two ways to talk about the player's "choice"---we may say that the player chooses a strategy \sigma \in \Sigma , which then has some effect. Or we may say that the choice is really the y \in Y, and the strategy \sigma is the "precommitment" of choosing what to do given each possible x \in X.

Once we introduce randomness---working in Kl(\Delta ), for example---we see that there are two distinct ways for a player to make a random choice: first, his strategy I \to \Delta (\Sigma ) may be stochastic---that is, he is choosing a random strategy. Or the morphism \Sigma \times X \to \Delta (Y) may be stochastic---this means each strategy \sigma contains a specification of how to randomly choose y given each possible x.

In the case where X = *, the distinction is between taking \Sigma = Y and letting the play function be the identity, and taking \Sigma = \Delta (Y) and letting the play function be the sampling map which stochastically draws an element from a distribution.

We take the view that the latter is the proper presentation of this game---this goes along with the terminology in the classical game theory literature, which would certainly regard a distribution on the set of possible moves as a (mixed) strategy. Having represented our games like this, we may restrict ourselves to considering deterministic maps I \to \Sigma as strategies. This also fixes the awkwardness in the definition of the Nash product, since now every strategy in \Sigma _1 \otimes \Sigma _2 decomposes uniquely as a pair of strategies.

We quickly modify the preceding definitions to make sense of this. Note that we also modify the reparametrization maps to be deterministic (in the base).

Definition Open games in a stochastic module [efr-6I8U]

Let \mathcal {D} be a symmetric monoidal stochastic module fibration over the Markov category \mathcal {C}. Recall that \mathsf {SLens}(\mathcal {D}) acquires a symmetric monoidal structure. Denote as usual \mathsf {SLens}(\mathcal {D})|_\mathrm {det} = \mathsf {SLens}(\mathcal {D}) \times _{\mathcal {C}} \mathcal {C}_\mathrm {det}. Note that this is stable under the monoidal product, and acts on \mathsf {SLens}(\mathcal {D}) via the inclusion.

Then the category of open games in \mathcal {D} is the category \widetilde {\mathsf {Game}} = \mathsf {Para}_{(\mathsf {SLens}(\mathcal {D})|_\mathrm {det})_\mathbb {S}}(\mathsf {SLens}(\mathcal {D})).

When \mathcal {D} \to \mathcal {C} is a Markov prefibration, we overload the notation by writing \widetilde {\mathsf {Game}}(\mathcal {D}) = \mathsf {Game}(\mathcal {D}|_\mathrm {det}).

We now introduce the notion of strategic equivalence, which identified two open games if they have the same equilibria for every costate \overline {\Sigma } \to I which can actually occur as a result of pasting the game \overline {\Sigma } \otimes \bar {X} \to \bar {Y} into some larger diagram.

Definition Context [efr-K0Y8]

Let X,Y be objects of a symmetric monoidal category \mathcal {C}. A context for X,Y is a tuple M \in \mathcal {C}, s: I \to X \otimes M, k: Y \otimes M \to I. We denote the set of contexts \mathrm {Ctx}(X,Y).

Given a morphism f: P \otimes X \to Y, and a context c = (M,s,k), the costate k(f \otimes 1_M)(1_{P} \otimes s) will be called the induced costate.

Remark [efr-I1K5]

The preceding definition clearly works in a non-symmetric monoidal category as well. In this case, arguably, a context should be defined to consist of maps I \to M_1 \otimes X \otimes M_2, M_1 \otimes Y \otimes M_2 \to I. However, the problem with this from our point of view is that it doesn't allow the definition of a costate on P given a parametrized map (since one cannot commute the P past the M_1), which is what we're interested in.

It is also worth observing that contexts are essentially the same thing as optics {I \choose I} \to {Y \choose X}. We have not specified an equivalence relation on contexts (we do not need it,) but it is easy to see that for any parametrized map, two contexts that are sliding equivalent give the same induced costate.

Definition Strategic Equivalence [efr-R46X]

Let \mathcal {D} be a monoidal stochastic module fibration over a Markov category \mathcal {C}, and consider a 2-cell \alpha : G_1 \to G_2: \bar {X} \to \bar {Y} \in \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})).

We say this is a strategic equivalence if the underlying map \Sigma _1 \to \Sigma _2 in \mathcal {C} is an isomorphism, and for every context c \in \mathrm {Ctx}(\bar {X},\bar {Y}), the induced costate k on \overline {\Sigma _2} has the same equilibria (under this isomorphism) as the composite costate k\alpha on \overline {\Sigma _1}

Note that a game up to strategic equivalence is determined by a relation between strategies I \to \Sigma and contexts. This brings us closer to Hedges' original definition of open game from Reference [hedges-etal-comp-gametheory]. The chief difference is that a game in our sense is prevented from "inspecting" the context Y \to \bar {Y} for those y \in Y which are not in the image of X \times \Sigma \to Y, in the sense that whether a given strategy is in equilibrium or not cannot depend on this (since we only see a certain costate on \Sigma ).

Proposition [efr-HLIX]

Strategic equivalence is compatible with composition and tensor in \widetilde {\mathsf {Game}}(\mathsf {SLens}(\mathcal {D})).

Proof

Let \alpha : (G_1 \to G_1'): \bar {X} \to \bar {Y}, \beta : (G_2 \to G_2') : \bar {Y} \to \bar {Z} be strategic equivalences. By 2-cell composition there is a map G_2G_1 \to G_2'G_1', which we must show is a strategic equivalence.

Let c = s,k be a context in \mathrm {Ctx}(\bar {X},\bar {Z}). Now a pair of strategies \sigma _1, \sigma _2 for G_1,G_2 are in Nash equilibrium for the costate induced by this context if and only if \sigma _1 is in equilibrium for the costate induced by the context s: I \to \bar {X} \otimes \bar {M}, k(p_2(\sigma _2) \otimes 1_{\bar {M}}), where p_2 is the play function of G_2, and the analogous condition holds for \sigma _2.

But if \alpha ,\beta are equivalences, this is clearly equivalent to asking that \sigma _1,\sigma _2 be in Nash equilibrium for the costate induced by c on \overline {\Sigma _1'} \otimes \overline {\Sigma _2}'. This concludes the proof.

Definition [efr-U99C]

We denote by \mathsf {Game}(\mathsf {SLens}(\mathcal {D})) the symmetric monoidal category of strategic equivalence classes of open games.

Note that this category of open games retains a 2-categorical structure, given by deterministic maps \Sigma _1 \to \Sigma _2 which preserve equilibria in every context. However, we will leave a deeper investigation of this structure for future work.

The Para Construction as a double category [efr-002H]

In many different situations, we want to understand some morphism as parametrized by some data. For example, in machine learning one tries to find a function f: X \to Y with some desirable behaviour by choosing a parametrization F: P \times X \to Y and searching for some p \in P so that F(p,-) has this behaviour (for example by gradient descent on p).

In situations where we want to understand F as being built up as a composite of multiple functions (for example, the layers of a neural network), it is convenient to introduce a category of parametrized morphisms, where the composition combines the parameter spaces of each composite map. We can do this in a general setting with the following definition:

Definition [efr-002G]

Let \mathcal {M} be a monoidal category, and let \bullet : \mathcal {M} \times \mathcal {C} \to \mathcal {C} be an action of \mathcal {M} on another category \mathcal {C}. Then the \mathsf {Para} construction is the category \mathsf {Para}_\mathcal {M}(\mathcal {C}) where

  1. Objects are objects of \mathcal {C}
  2. Morphisms A \to B are tuples P \in \mathcal {M}, P \bullet A \to B up to the natural notion of isomorphism.
  3. Composition is by tensoring the parameter objects and composing.

The fact that the parametrization object may live in a different category than the domain and codomain objects, which initially seems like a superfluous generalization, is in fact highly useful. For example, we will often want to consider parametrized morphisms where the parameter space is decorated with some additional data, for example a probability distribution. In most such cases, the category of spaces decorated with such data will act on the category of spaces without such data (simply by forgetting the data and tensoring), and hence we can realize such parametrized morphisms as examples of this \mathsf {Para} construction. We may also want only Euclidean parameter space (so that we can run gradient descent simply), but allow the parametrized morphism to go between more general manifolds.

\mathsf {Para}, and generalizations of it, have been introduced many times. One of the earliest occurrences is by Hermida and Tennent, Reference [hermida-monoidal-indeterminates], in the special case of a symmetric monoidal category acting on another such via a functor i: \mathcal {C} \to \mathcal {D} (by a result of Capucci and Gavranović, Reference [actegories-amthematician-capucci-gavranovic], every "structure-preserving" action of a symmetric monoidal category on another has this form). Hermida and Tennent actually give a very intuitive universal property of \mathsf {Para}_\mathcal {C}(\mathcal {D}): it is freely generated by adding a morphism I \to i(C) for each C \in \mathcal {C}, subject to the equations that this must be a monoidal natural transformation. This type of idea actually goes all the way back to Pavlović in Reference [pavlovic-categorical-names].

The notation \mathsf {Para} was introduced inReference [backprop-as-functor], where the special case of parametrized morphisms of euclidean spaces was used to study gradient descent. In Reference [towards-cybercat], a bicategorical variant (replacing the quotient by isomorphism in the above variant in the obvious way) is introduced.

Example [efr-MN7C]

Let \mathcal {C} be a monoidal category, and let S: \mathcal {C} \to \mathsf {Set} be any functor. Recall that \int S is the category whose objects are pairs (X \in \mathcal {C}, s \in S(X)) and whose morphisms (X,s) \to (Y,s') are f: X \to Y so that S(f)(s) = s'. If S is lax monoidal (for (\mathsf {Set},\times ),) \int S acquires a lax monoidal structure making the forgetful functor \int S \to \mathcal {C} strong (even strict) monoidal.

With the action induced by this functor, the bicategory \mathsf {Para}_{\int S}(\mathcal {C}) has morphisms given by maps M \otimes X \to Y, m \in S(M), and maps given by reparametrizations which preserve the decoration m.

For example, let \mathcal {C} be a Markov category and let S(X) = \mathcal {C}(I,X). Then morphisms are parametrized maps equipped with a measure on the parameter space.

Example [efr-WEST]

If \mathbb {C} = \mathsf {Set} regarded as a discrete 2-category, as noted, a pseudomonoid action is just a monoid action in the ordinary sense---that is, a monoid M, a set X and a function m \cdot x so that m \cdot (n \cdot x) = (mn) \cdot x. The para construction is then the action category, whose objects are the points of X and whose morphisms x \to y are elements m so that m \cdot x = y (with multiplication as composition).

Example [efr-QH7O]

Let \operatorname {\mathsf {Ab} - \mathsf {Cat}} be the 2-category of \mathsf {Ab}-enriched categories, functors and natural transformations. Recall that a ring R is the same as a one-object category enriched in \mathsf {Ab}, and it admits a monoidal structure if and only if it is commutative (this is not particular to \mathsf {Ab}-enriched categories). An enriched R-action on an \mathsf {Ab}-category \mathcal {C} is then an R-module structure on each hom-set so that composition is R-linear in each variable.

[efr-KL7V]

If a category has coproducts, then \mathsf {Set} acts on it via S \cdot X = \coprod _{s \in S}X. (This is the \mathsf {Set}-enriched case of what in enriched categories is called a copower or tensor, the dual of the power objects from Example [efr-K3YI]). The morphisms of \mathsf {Para}_\mathsf {Set}(\mathcal {C}) are pairs (I \in \mathsf {Set}, (f_i: X \to Y \in \mathcal {C})_{i \in I}), which compose in the obvious way.

Note that this definition clearly makes sense even if \mathcal {C} does not actually have coproducts. This is an example of another construction which has been called \mathsf {Para}, which takes a monoidal category \mathcal {V} and a \mathcal {V}-enriched category \mathcal {C} and constructs a double category where the morphisms are pairs (J \in \mathcal {V}, J \to \mathcal {C}(X,Y)). It is not hard to see that this also extends to a double category in the same way, but we do not presently know the correct definition of internal enriched object that would replace pseudomonoid actions to replicate our general theory for this case. (note that the literature contains a notion of internal enriched category, Reference [internal-enriched], but these are categories enriched over internal monoidal categories---that is, the ambient category \mathcal {E} is a 1-category and the categorical structure of the base of enrichment \mathcal {V} is formulated on top of this, not as part of the structure of the objects of the category \mathcal {E})

There is a very natural double categorical version of \mathsf {Para}, where the vertical morphisms are just the unparametrized morphisms of \mathcal {C}, and the 2-cells with this boundary:

are morphisms M \to N (if f is parametrized by M, g by N) so that the square
commutes.

This notion is not original---we learned of it from Matteo Capucci---but it seems to have remained somewhat on the level of folklore. Our main goal for this section will be to construct this (pseudo) double category, and show that it is functorial---that is, given a homomorphism of actions, there is an induced functor between double categories. In fact, we will show that this construction works in any 2-category. Later we will apply it to a pseudomonoid action in (strict) double categories to construct a pseudocategory internal to double categories---our triple category of bimachines.

Theorem [efr-55CC]

Let \mathcal {M} be a monoidal category, and let \mathcal {C} be a category with an \mathcal {M}-action.

Then there is a pseudo double category \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C}), with

  1. \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C})_0 = \mathcal {C}
  2. \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C})_1 = \mathcal {M} \times \mathcal {C} \downarrow \mathcal {C}, with domain and codomain given by the two projections to \mathcal {C}
  3. The identities map \mathcal {C} \to \mathcal {M} \times \mathcal {C} \downarrow \mathcal {C} is given by (I, 1_\mathcal {C}, 1_\mathcal {C}, \lambda ), where \lambda : I \cdot - \to - is the left unitor of \mathcal {M}.
  4. The horizontal composition map is the composition in \mathsf {Para}: given M \cdot X \to Y, N \cdot Y \to Z, their composite is given by (N \otimes M) \cdot X \cong N \cdot (M \cdot X) \to N \cdot Y \to Z. The horizontal composition of 2-cells is defined analogously.

Moreover, if \mathcal {C} \to \mathcal {D} is strict homomorphism of \mathcal {M}-modules, there is an induced pseudofunctor \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C}) \to \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {D}). If \mathcal {N} \to \mathcal {M} is a strict monoidal functor, then regarding \mathcal {C} as an \mathcal {N}-module along this map, there is an induced pseudofunctor \mathsf {\mathbb Para}_\mathcal {N}(\mathcal {C}) \to \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C}). These combine into a 2-functor \mathsf {Act}_s \to \mathsf {PsDbl}_s between the 2-category of actions and strictly linear functors and the category of pseudo double categories and strict double functors. This functor preserves (strict) limits.

Proof

Note that every actegory \mathcal {M} \curvearrowright \mathcal {C} is equivalent to a strict action of a strict monoidal category \mathcal {M}_s \curvearrowright \mathcal {C}_s (in the sense that there exists \mathcal {M}_s \xrightarrow {\sim } \mathcal {M} strong monoidal equivalence and \mathcal {C}_s \xrightarrow {\sim } \mathcal {C} an equivalence such that these maps together form a map of actegories). It follows that it suffices to show unitality and associativity for our composition in the strict case (since these are plainly preserved by equivalence).

Let \mathcal {M} \curvearrowright \mathcal {C}, \mathcal {M}' \curvearrowright \mathcal {C}', F: \mathcal {M} \to \mathcal {M}' be a strict monoidal functor, and let G: \mathcal {C} \to \mathcal {C}' be a linear functor "over F", that is a (strict) \mathcal {M}-linear functor when \mathcal {C}' is viewed as a \mathcal {M}-actegory along F. Then the induced functor \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C}) \to \mathsf {\mathbb Para}_{\mathcal {M}'}(\mathcal {C}') is given by G on the vertical category, and on the horizontal category by (M,X,X',\phi : M \cdot X \to X') \mapsto (F(M), G(X), G(X'), F(M) \cdot G(X) \simeq G(M \cdot X) \to G(X')) where the isomorphism is the linearity---noting that the M-action on \mathcal {C}' is precisely acting by F(M).

By naturality of the lineator it is straightforward to see that this is a functor, and it clearly preserves domain and codomain. It preserves units (strictly!) by the compatibility between the unitor and lineator. It remains to see that this preserves composition. For brevity, denote the induced functor H from here.

It suffices to verify this for strict actions. So the composite of M \cdot X \to Y, N \cdot Y \to Z is given by the composite (N \otimes M) \cdot X = N \cdot M \cdot X \to N \cdot Y \to Z.

Given two such composable maps, call them f,g, the two objects H(fg), H(f)H(g) are given by (F(M \otimes N), G(X), G(Z), \beta ), (F(M) \otimes F(N), G(X), G(Z), \alpha ) ,where \alpha , \beta are respectively the maps across the top and bottom of this diagram:

This proves that H preserves the composition strictly, as desired. (The rightmost triangle commutes by definition, and the leftmost rectangle is a lineator coherence)

Since the strict limits in \mathsf {PsDbl}_s and \mathsf {Act}_s are computed levelwise, it suffices to observe that the slice category also preserves limits, being a weighted limit itself.

Remark [efr-HUEE]

Note that \mathsf {\mathbb Para}_\mathcal {M}(\mathcal {C}) comes equipped with a strict functor to B\mathcal {M} (viewed as a double category). In fact, one can recover the action \cdot : \mathcal {M} \times \mathcal {C} \to \mathcal {C} from this data: the object M \cdot X is characterized up to isomorphism by its universal property: parametrized maps M \cdot X \nrightarrow Y with parameter N are in bijection with maps X \to Y parametrized by N \otimes M.

Open Games with external choice in Markov Fibrations › Introduction [efr-7EHV]

Game theory is a field of economics which studies mathematical models of human decisionmaking. Classically, game theory is particularly interested in the behavior resulting from individual agents optimizing simple objectives (such as the expected value of some real-valued function of each players' decision) when multiple such players interact. Although the analysis of games, obviously, has a long prehistory, the field was put on its modern theoretical footing by Von Neumann in 1928 (Reference [neumann-games], see also Reference [neumann-morgenstern-games] for a more thorough treatment from this era). The basic problem studied here is this: given two finite sets \Sigma _1, \Sigma _2 of strategies---that is, the choices available to the two players---and a function f: \Sigma _1 \times \Sigma _2 \to \mathbb {R} which assigns to a pair of such choices a score, which player 1 seeks to maximize and player 2 seeks to minimize, what can be said about the rational decisionmaking of each player?

Suppose each player has access to some source of randomness, so that they may each choose a distribution on their respective strategy set to play. This is called a mixed strategy. Suppose player 2 has the opportunity to move knowing the distribution chosen by player 1 (but not the value drawn from it), and suppose he prefers to minimize the expected outcome of the game. Writing f(\mu _1,\mu _2) for E_{x \sim \mu _1, y \sim \mu _2}f(x,y) for brevity, if player 1 selects the distribution \mu _1, clearly player 2 must select the distribution \mathrm {argmin}_{\mu _2} f(\mu _1,\mu _2). Knowing this, player 1 will select the distribution \mathrm {argmax}_{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2), and the expected score of the game will be \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2).

If the selection happens in the other order, of course, the result will be \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2). Clearly choosing knowing your opponent's (mixed) strategy can not be a disadvantage compared to choosing with no information, and so we have \min _{\mu _2} \max _{\mu _1} f(\mu _1,\mu _2) \leq \max _{\mu _1} \min _{\mu _2} f(\mu _1,\mu _2). Von Neumann's great minimax theorem is that these values agree, and this implies that by choosing as if your opponent would know your (mixed) strategy, you obtain a result as good as you could have obtained if you knew your opponents' strategy---hence neither player could improve their outcome, even if they had the advantage of greater information.

This is a strong argument for the optimality of such decisions. The key assumption is that the players are perfectly opposed, that is, player 2 seeks to minimize precisely the value that player 1 seeks to maximize. Nash in Reference [nash-noncoop-games] extended the theory to the more general class of games where players simply each have their own utility function, although it should be noted that Nash merely proved the existence of equilibria---that is, strategy sets where no player can improve their situation by switching strategies. It is computationally intractable (Reference [nash-complexity]) to identify Nash equilibria in an arbitrary game, and so to apply the theory we're forced to analyze each game in an ad hoc way.

We will not go intro a serious review of game theory here, we mention the above details mainly to contextualize our future definitions. For a modern reference on game theory see eg Reference [game-theory-maschler-textbook], or Reference [osborne-intro-gametheory] for a textbook treatment.

In his thesis (Reference [hedges-towards-compositional-thesis]), Hedges introduced a novel approach to game theory which he named compositional game theory, studying objects called open games. The idea of open games is to describe a type of "partial" game which has an interface to the world---some part of the payoff function being dependent on an undetermined environment, into which hole can be inserted another game. This is the sense in which they are open. Based on these, one can build a complex game up out of simpler subparts, as well as leverage a string diagramattical syntax to analyze games.

The original definition of open game cannot help but seem somewhat ad hoc. It was quickly realized that a large part of the definition can be understood to say that a game is a function \Sigma \to \mathsf {Lens}({S \choose X},{R \choose Y}) from a strategy set into a set of lenses, and this part of the game composes by lens composition.

The additional data of an open game is a so-called equilibrium relation, which determines which strategies are equilibria in a given situation (each strategy really represents a set of strategies, one for each player). In Reference [towards-cybercat], the author, Capucci, Gavranovic and Hedges demonstrated that this can be further simplified by realizing an open game as a parametrized map in lenses---a morphism in \mathsf {Para}(\mathsf {Lens}(\mathcal {C})) (in fact, one often wants to consider \mathsf {Optic}(\mathcal {C}) for, for example, Markov categories \mathcal {C}, to account for mixed strategies) along with a notion of equilibrium relation defined on the parameter object {\Omega \choose \Sigma }. We will begin this chapter by recapping this idea.

On a conceptual level, there is a natural operation on games, called external choice, which assigns to two open games {A_1 \choose X_1} \to {B_1 \choose Y_1}, {A_2 \choose X_2} \to {B_2 \choose Y_2} a new game, whose environment begins by making a choice between one of these games, lets that one happen, then provides some payoff for it at the end. The natural type for the interface of this operation is {A_1 \choose X_1} + {A_2 \choose X_2} \to {B_1 \choose Y_1} + {B_2 \choose Y_2}, but unfortunately the category of optics doesn't have coproducts. The category of lenses can be extended with coproducts (into dependent lenses), but the analysis of mixed strategies makes probability an absolute necessity for a useful theory of games.

The introduction of Markov fibrations provides a solution to this problem, and in the second half of this chapter, we provide such an external choice operation on open games. Although the approach based on Markov fibrations is novel, the approach to defining the external choice operator is otherwise very similar to one appearing in presently unpublished work by the author, Braithwaite, Hedges and Videla (this paper used a more specialized approach to adding coproducts to \mathsf {Optic}).

Markov Fibrations and Stochastic Lenses › Introduction [efr-X0ZV]

Let Kl(\Delta ) denote the Kleisli category of the discrete (countable) distribution monad on \mathsf {Set}. This is a simple setting for working with probability theory---sufficient for many applications. In order to study compositional Bayesian game theory (Reference [hedges-etal-bayesian-games], Reference [towards-cybercat]) one studies the category \mathsf {Optic}(Kl(\Delta )) of optics in Kl(\Delta ). These have the right level of expressivity to talk about players taking random actions, and where payoff depends stochastically on players' decisions.

In \mathsf {Optic}(Kl(\Delta )), {R \choose X} + {R \choose Y} \cong {R \choose X+Y}. Games with this codomain naturally describe the situation of a player who has a binary choice between X or Y. We call coproducts of this form the "good" coproducts---note that also {* \choose *} + {\emptyset \choose *} = {\emptyset \choose 2}, but this is considered somewhat pathological, since it relies on the nonexistence of any morphism {\emptyset \choose X} \to {A \choose Y} when A and X are nonempty.

In order to describe this structure on \mathsf {Optic}(Kl(\Delta )), it would be useful if it had all coproducts. Unfortunately this is not the case. \mathsf {Optic}(\mathsf {Set}) = \mathsf {Lens}(\mathsf {Set}) has a well-known extension with all coproducts, given by the fiberwise opposite of the fibration \mathsf {Fam}(\mathsf {Set}) \to \mathsf {Set} (this is Proposition [efr-VTPS] in the case \mathcal {C} = \mathsf {Set}). Extending this to stochastic maps would be the obvious way of constructing such a category of "dependent optics".

Consider a category Kl(\Delta )^\to defined as follows. Its objects are the objects of \mathsf {Set}^\to ---that is, they are indexed families of sets. A map in Kl(\Delta )^\to is a stochastic map in the base X \to Y \in Kl(\Delta ), and a stochastic map on the total spaces \bar {X} \to \bar {Y} which is compatible with it. Note that if \bar {X} \to X is surjective, the map on the base is fully determined by the map on the fibers, which must merely satisfy the condition that the distribution of the indexing point in Y depends only on the indexing point in X, not the specific point in the fiber \bar {X}_x.

We claim Kl(\Delta )^\to is a reasonable notion of "stochastic charts". Recall that by "chart" we mean something like "lenses where both maps go forward". If stochastic lenses are supposed to include optics as the full subcategory spanned by the "non-dependent" objects, then the charts should include "co-optics"---that is, maps between X' \otimes X \to X and Y' \otimes Y \to Y should be given by the coend \int ^M \operatorname {\mathrm {Hom}}(X, M \otimes Y) \times \operatorname {\mathrm {Hom}}(X' \otimes M, Y')

And in fact this is the case: Clearly there is a map from this coend to maps in Kl(\Delta )^\to . By taking M = X \otimes Y and conditioning on Y, we see this is surjective. Finally, by restricting to the support of the forwards part inside X \otimes Y, we obtain a representative for each element of the coend which is uniquely determined by X \to Y and X' \times X \to Y' (since the conditional is well-defined on the support).

Note: This relies both on the fact that Kl(\Delta ) has conditionals, and on the existence of supports. We've previously seen these defined in abstract Markov categories (Definition [efr-AB57])--supports in Kl(\Delta ) of a morphism p: A \to B are simply given by those b so that p(b | a) > 0. Note that the existence of both conditionals and supports is a very strong assumption---the only categories we are aware of with both properties are those whose probability distributions have a discrete character, like Kl(\Delta ) and \mathsf {FinStoch}. Neither will be essential to the theory, but both will play a role in certain theorems---we will see more of this later.

The goal of the theory of Markov fibrations is to give a notion of "fiberwise opposite" which can be applied to the codomain functor Kl(\Delta )^\to \to Kl(\Delta ) to give a reasonable notion of "stochastic lenses". In particular, we should recover the usual category of optics in the previous case.

It is clear that the codomain functor is not a (Grothendieck) fibration, since this would require Kl(\Delta ) to have pullbacks, which can only hold for a Cartesian Markov category. However, we can do some things. Namely, given a Cartesian (pullback) square in \mathsf {Set}

and a map {\bar {X} \choose X} \to {\bar {B} \choose B} where the base map X \to B is deterministic, for each deterministic factorizing map X \to A there is a unique lift \bar {X} \to \bar {A}. In other words, the pullback over \mathsf {Set} \hookrightarrow Kl(\Delta ) is a fibration---in fact, it is simply the family fibration \mathsf {Fam}(\mathsf {Kl}(\Delta )).

Furthermore, if \bar {X} \to \bar {B} is itself deterministic, there is such a unique lift even without assuming that the factorization X \to A is deterministic.

Moreover, we can factor any map in Kl(\Delta )^\to as such an induced map followed by a map over a deterministic base, as follows:

This gives us a hope that we can, in some way, control the category Kl(\Delta )^\to using the pullback over \mathsf {Set}, which is a fibration, and some information somehow given by these extra maps. Note also that the diagram above is equivalent to giving: a span X \leftarrow M \to Y and a section X \to M, which all lives in the base, and a map p^*\bar {X} \to p^{'*}\bar {Y} in the fiber over M. Thus it would seem to be very amenable to fiberwise dualization.

Analogous to our argument above that "co-optics" are equivalent to maps in Kl(\Delta )^\to , we can do the following:

Suppose given two tuples (M_0,p_0,p_0',s_0,\phi _0), (M_1,p_1,p_1',s_1,\phi _1) as above. Suppose there exists a map f: M_0 \to M_1 over X,Y, so that f s_0 = s_1. Then there is a canonical map p_0^*\bar {X} \to p_1^*\bar {X} over f, because pullbacks commute. If the triangle

moreover commutes, then these two triples represent the same map in Kl(\Delta )^\to

These equivalence relations correspond to "sliding" for deterministic morphisms M \to M'. Note that the condition here can be checked just on the fibration Kl(\Delta )^\to \times _{Kl(\Delta )} \mathsf {Set} \to \mathsf {Set}.

To obtain the full set of sliding equations, we will need to use stochastic maps M \to M', and thus leave that fibration behind. However, we are tantalizingly close to realizing Kl(\Delta )^\to as being presented by some sort of additional structure on the fibration \mathsf {Fam}(\mathsf {Kl}(\Delta )). (For a general monad T acting on C, the category \mathsf {Optic}_{\mathcal {C}}(Kl(T),Kl(T)), of effectful optics up to sliding of pure morphisms, was studied by Riley in Reference [riley-optics], section 4.9, and by Hedges in Reference [hedges-blog-optics-effect])

In this chapter we will indeed provide such a structure, and analyze it. In § [efr-2IMZ], we'll axiomatise the lifting property of Kl(\Delta )^\to discussed above into a property we call a Markov prefibration (Definition [efr-0019]). In § [efr-GO6R], we exhibit a free Markov prefibration associated to a fibration---its morphisms are precisely spans of the form seen above. Naturally, given a prefibration \mathcal {D} \to \mathcal {C}, its underlying fibration on \mathcal {C}_\mathrm {det} becomes an algebra for the monad of this adjunction. In § [efr-U4RA], we characterize the class of prefibrations which are presented by their underlying algebra in this way---these are the Markov fibrations (Definition [efr-HVUT]). Since the monad commutes with fiberwise opposites, this yields a notion of fiberwise opposite for Markov fibrations.

Following this, we review a few properties of the theory of Markov fibrations, including the existence of coproducts in the fibration (Proposition [efr-QAV2]), the stability of Markov fibrations under limits (§ [efr-HWAZ]), and induced monoidal structures (§ [efr-LTEL]). Combining these, we can prove:

Theorem [efr-OSH4]

There exists a (strong) symmetric monoidal functor \mathsf {Optic}(Kl(\Delta )) \to \mathsf {SLens}(Kl(\Delta )^\to ) which

  1. Is fully faithful.
  2. Preserves the good coproducts.
  3. So that the image has all coproducts, and every object of the image is a coproduct of objects in \mathsf {Optic}(Kl(\Delta ))
  4. And so that moreover the monoidal structure on the image is distributive

Markov Fibrations › Introduction [efr-HQ73]

In applying category theory to fields as diverse as game theory (Reference [hedges-etal-comp-gametheory],Reference [hedges-etal-bayesian-games], Reference [hedges-etal-graph-games]), machine learning (Reference [bruno-etal-categorical-learning-2021], Reference [bruno-thesis-fundamental-components]), dynamical systems (Reference [myers-cst], Reference [lynch-myers-rischel-staton-stoch-clocks]), and server design (Reference [videla-capucci-servers]), people have found it useful to study categories whose morphisms describe processes or functions that take place in two "stages", where the second is dependent on the first, but composes in the other direction---so-called lenses. In many of these domains, stochastic phenomena play a role. There is a useful generalization of lenses to categories of stochastic maps---the so-called optics of Riley, Reference [riley-optics]---but this does not accommodate another useful generalization, so called dependent lenses where not only the backwards process but the set it takes values in is indexed over the base. It has been a long-standing problem to develop a suitable common generalization, "dependent optics", of these two ideas. In this thesis, we solve this problem by developing a theory of Markov fibrations (§ [efr-O088]).

A Markov fibration is a weakening of the notion of (Grothendieck) fibration to include (subject to some assumptions) Markov categories of indexed families of objects (given by deterministic functions E \to X) and compatible stochastic maps (given by commutative squares). The main point of Markov fibrations is that they admit fiberwise opposites, which generalize the fiberwise opposites of ordinary categories. Just as the fiberwise opposite of the codomain fibration of a finitely complete category describes dependent lenses (see § [efr-ZCTD]), the fiberwise opposite of these codomain Markov fibrations give a good notion of stochastic lens (see Theorem [efr-K6NM]).

We will apply our theory chiefly to two problems. First, we will use them to generalize open games (Hedges, Reference [hedges-towards-compositional-thesis]) to a larger class of interfaces (namely, indexed families of sets) while at the same time considering possibly-stochastic maps. This will allow us to construct the so-called external choice operator on open games, which describes branching.

Secondly, we will generalize Myers' categorical dynamical systems theory to allow for stochastic maps in the base. When combined with another generalization of these systems, to general parametrized lenses, this gives a more natural way of modeling certain stochastic dynamical systems, such as those associated to the training dynamics of machine learning models, see eg Example [efr-IMZ3].

A brief introduction to lenses

If \mathcal {C} is a category with finite products, the category \mathsf {Lens}(\mathcal {C}) of lenses in \mathcal {C} has objects pairs \binom {A}{X} of objects in \mathcal {C}, and morphisms \binom {A}{X} \leftrightarrows \binom {B}{Y} given by pairs f: X \to Y, f^\#: B \times X \to A. (Note that it is of course the morphisms, not the objects, that are called lenses). One way to generalize this is to ask for \mathcal {C} to have pullbacks, and consider an object given by a more general map A \to X, and let a map be f: X \to Y, f^\#: B \times _Y X \to A (so that the triangle over X commutes). (Note that this recovers the "simple lenses" when the objects are of the form A \times X \to X). Under the interpretation of a map A \to X as a family of objects A_x indexed over the elements of X, we see this as a "dependent lens" (since A is a "dependent type"). There are various variations of this idea, which ultimately all fit the pattern of taking a Grothendieck fibration \mathcal {D} \to \mathcal {C} and forming the fiberwise opposite---for the dependent lenses as above, this is the codomain fibration \mathcal {C}^\to \to \mathcal {C}.

Meanwhile, another wide-ranging generalization of \mathsf {Lens}(\mathcal {C}) are the optics of Riley (Reference [riley-optics]). For \mathcal {C} a monoidal category, the objects of \mathsf {Optic}(\mathcal {C}) are again pairs \binom {A}{X} of objects, but now the morphisms are elements of the coend \int ^{M \in \mathcal {C}}\mathcal {C}(X, M \otimes Y) \times \mathcal {C}(M \otimes B, A). That is, to give an optic \binom {A}{X} \leftrightarrows \binom {B}{Y} is to give an object M \in \mathcal {C} and morphisms l: X \to M \otimes Y, r: M \otimes B \to A, up to the equivalence relation generated by, whenever s: N \to M, l: X \to N \otimes Y, r: M \otimes B \to A, identifying the two optics given by (M, (s \otimes 1_Y) \circ l, r) and (N, l, r \circ (s \otimes 1_B)). One can show that, in the case where \mathcal {C} is a Cartesian monoidal category, this set can be identified with the set of (simple) lenses.

A vector field on a smooth manifold X is simply a (smooth) section of the tangent bundle TX. A section is a bundle map from the trivial bundle X \to X. This gives the idea of considering a parametrized dynamical system as consisting of a map X \to A to some other smooth manifold, a bundle E \to A (the points of E are the parameters) and a bundle map E \times _A X \to TX. As we will see, such a bundle map is exactly a dependent lens in a category of bundles. Building on this idea, Myers (Reference [myers-cst]) described a highly abstract theory of open dynamical systems, given by lenses out of tangent bundles (where the notion of space, bundle and tangent bundle are generalized to any fibration).

It has been observed that, although a lens from the tangent bundle TS \leftrightarrows A may indeed be said to describe an open dynamical system with state space S, the same can be said for a lens of type TS \otimes A \leftrightarrows I---although a dynamical system of a different kind (essentially, the first type are the Moore machines, the second the Mealy machines---see the introduction to § [efr-000D] for more on this). It is natural to consider parametrized maps TS \otimes A \leftrightarrows B as a common generalization of these two concepts---and in fact, special cases of this idea, lenses parametrized by tangent bundles, have already been considered many times, for example in the semantics of gradient descent (see Reference [bruno-etal-categorical-learning-2021], Reference [towards-cybercat], Reference [backprop-as-functor]).

Since parametrized maps compose in an obvious way, we now have three different notions of morphisms between bundles---lenses, charts, and "generalized systems". These should form some sort of symmetric monoidal triple category, but the right axiomatisation of this concept is somewhat elusive.

Lenses, in their various incarnations, have been widely used in applied category theory. For example, Hedges and his collaborators have developed a compositional approach to game theory (Reference [hedges-string-games], Reference [hedges-etal-comp-gametheory], Reference [hedges-etal-institutions], Reference [hedges-etal-graph-games], others). Recent work by Hedges and Sakamoto bring this idea to reinforcement learning (Reference [sakamoto-reinforcement-lenses]). We briefly mentioned Myers' categorical systems theory above, and we will see much more of it later. As we discussed above, there is also a literature using lenses to study gradient descent in an abstract sense. This is without even mentioning their original role in the theory of functional programming (this is the origin of the somewhat confusing term lens), or their prehistory in Gödel's dialectica interpretation---see eg Reference [jules-lenses-blogpost] for a survey of this.

Dependent Optics

An open game, in the sense of Hedges, has as its interface two objects in the category of lenses (of sets) \binom {S}{X}, \binom {R}{Y} (that is, two pairs of sets). An open game with this interface consists of a set \Sigma of strategies equipped with a function \Sigma \to \mathsf {Lens}(\mathsf {Set})(\binom {S}{X},\binom {R}{Y}), and a subset Eq(x, k) \subset \Sigma of equilibrium strategies for each x \in X and k: Y \to R---note that such an x is exactly a lens \binom {*}{*} \leftrightarrows \binom {S}{X}, and such a k is exactly a lens \binom {R}{Y} \to \binom {*}{*}. This view of open games makes the composition rule much simpler to define, although we will not delve into the details here, see eg Reference [hedges-etal-comp-gametheory]. The idea is that the open game represents the strategies and preferences of a player or set of players---\sigma \in \Sigma are the possible strategies, x \in X is the information revealed to the player before they make their decision of which moves to make, the resulting y \in Y is the choice the player "sends" in response to x, and the r \in R is the "utility", the value they eventually learn, depending on their choice y, which they have some preferences over.

The above description gives a theory of deterministic games, but of course, it is completely essential for game theory to model both random decisions (mixed strategies) and decisions made under uncertainty. This motivates the replacement of lenses in this definition with optics in a category of probability kernels (the form of the equilibrium relation must be modified as well, see Reference [hedges-etal-bayesian-games], Reference [towards-cybercat])

In the abstract study of open games, it is desirable to define a "choice" operation \oplus on the objects (the pairs of sets) so that maps into \binom {R}{X} \oplus \binom {R'}{X'} represent players who are faced with some binary choice between X and X', after which play may proceed for a time in one of two branches. However, this is immediately problematic because the category of lenses do not have coproducts---inside the category of dependent lenses, however, we can form the coproduct simply as R \times X + R' \times X' \to X + X'---that is, we get a family which is R over X, and R' over X'. This indeed does the job, but for game theory the extension to stochastic maps---optics---is absolutely essential. This motivates the search for a theory of dependent optics, a common generalization of optics and dependent lenses.

There have been a number of attempts at this---see eg Reference [fibre-optics-2021], Reference [hedges-braithwaite-dep], Reference [milewski-polylens], Reference [vertechi-dep-optics]. While these efforts have to some extent succeeded in describing a theory that is general enough to contain the desired examples, it is generally very ad hoc. The construction of optics as a special case of Vertechi's dependent optics (Reference [vertechi-dep-optics]) gives them as fibre optics with the indexing bicategory being (the delooping of) a monoidal category \mathcal {M}, but embeds lenses using a bicategory of spans. Thus simple lenses admit two distinct encodings in this theory. Moreover, Vertechi's example of dependent monoidal optics fails to describe a supercategory of \mathsf {Optic}(\mathcal {C}) when applied to Markov categories, and are thus not suitable for, for example, game theory.

Categorical Cybernetics

The observation that both open games and machine learning systems can be fruitfully described using lenses, naturally led to the idea that this could be used to develop a more thorough analogy between the two. After all, a machine learning system is also a player in a kind of game (with the objective of minimizing loss). Hedges coined the phrase categorical cybernetics to describe this locus of ideas (Reference [towards-cybercat], also used in Reference [sakamoto-reinforcement-lenses]).

Myers' categorical systems theory also describes dynamical systems as lenses. However, where a cybernetic system in the sense of Reference [towards-cybercat] is a parametrized lens \Sigma \otimes {\bar {X} \choose X} \leftrightarrows {\bar {Y} \choose Y}, and thus has two different inputs - x \in X, which is the information on which basis they are allowed to choose their decision y \in Y, and y^\sharp \in \bar {Y}, which is their "utility", the information they are allowed to care about.

It is straightforward to describe the machine learning part of the categorical cybernetics analogy in terms of Myers' theory---a "learner" is simply a lens of the above form with \Sigma replace with a tangent bundle TS. This idea (described in these terms, although not with the analogy to machine learning) has already been described by Reference [energy-driven-systems]. However, for game theory, it is necessary that the output of a given system can be stochastically chosen (a player must be able to randomize their strategy). At the same time, for a machine learning system, the x \in X is usually some sort of sample from a training distribution---ie, it is random. Hence to really describe the training dynamics of machine learning systems using this theory, we are again naturally drawn to consider systems theories (that is, fibrations) which have stochastic maps in the base, not merely the fiber.

Overview and contributions

We begin the thesis in § [efr-POD2] with a review of some preliminary material. This chapter can largely be skipped for readers already familiar with the material (Markov categories, double categories, lenses and optics, fibrations, and categorical dynamical systems theory). The chapter on Markov categories introduces a few novel auxiliary notions, but these can be referred back to as necessary (they are primarily regularity conditions which hold in most Markov categories of interest).

In § [efr-O088], we give the main technical contribution of the thesis by developing a theory of Markov fibrations. Their fiberwise opposites generalize both the fiberwise opposites of codomain fibrations (dependent lenses in a classical sense) and optics in Markov categories. Theorem [efr-K6NM] provides the statement of the latter (the former is straightforward). We also give a description of monoidal structures on Markov fibrations (which pass to monoidal structures on the resulting categories of optics).

In § [efr-000D], we give a construction of the double category of parametrized morphisms for a category action (or actegory)---in fact, we do this internally to any 2-category. This has the advantage of allowing us to construct more highly-structured versions of this double category by carrying out the construction internally to higher-structured actions. (Bicategorical versions of \mathsf {Para} are a relatively old idea, and the double categorical version is a straightforward extension which has existed for some time as folklore, but the fully-internal construction here is novel).

In § [efr-GFG0], we apply Markov fibrations to compositional game theory, and solve a longstanding problem by giving a category of stochastic open games with a general "external choice" operator. This construction is largely abstract over the particular category, and so can be applied to different Markov fibrations to describe games defined with different notions of stochasticity. We also review some previous work with Capucci, Hedges, and Gavranovic on abstract constructions of categories of open games (Reference [towards-cybercat]).

In § [efr-ZRUZ], we describe how to extend Myers' categorical systems theory to Markov fibrations, to give theories of systems which may have stochastic maps not merely in the fiber (as was already described by Myers in Reference [myers-cst]) but also in the base. We also leverage our construction from § [efr-000D] to give a description of a symmetric monoidal triple category whose three types of morphisms, are lenses, charts, and what we call bisystems, that is morphisms TS \otimes A \leftrightarrows B - these are open dynamical systems which have two directions of interaction with the environment. We also describe a particular systems theory of smooth manifolds and smooth stochastic maps between them.

Acknowledgements [efr-0008]

I would like to extend a great thanks to the Mathematically Structured Programming group at the University of Strathclyde, my fellow PhD students in particular, for making my time there such a great one. A good chunk of this work was completed while I worked at the Compositional Systems Laboratory at the Tallinn University of Technology---I owe everyone there a great thanks as well.

For conversations which contributed to this work, and to my mathematical development in general, I would like to thank Dylan Braithwaite, Matteo Capucci, Elena di Lavore, Tobias Fritz, Davidad, Tomáš Gonda, Bruno Gavranović, Diana Kessler, Owen Lynch, Jade Master, David Jaz Myers, Riu Nakamura, Chad Nester, Evan Patterson, Paolo Perrone, Mario Roman, Brandon Shapiro, Toby Smithe, Pawel Sobocinski, David Spivak, and Andre Videla. A special thanks to Dylan, Matteo, and Bruno, for serving their time with me in the dependent optics mines.

To Neil Ghani, Radu Mardare, and Jules Hedges, a massive thanks for serving as my advisors during the somewhat tumultuous process that was the production of this thesis.

Finally, I thank my wonderful family. Now you can stop asking me about it.

The \mathsf {Para} construction in generic 2-categories › Introduction [efr-003P]

Myers' theory of categorical systems theory (see § [efr-0023]) gives a rich categorical structure to a wide variety of types of dynamical system. The central idea can be summarized by saying that there are two different, but tightly related, notions of morphism at play in dynamical systems. Open dynamical systems themselves involve a bidirectional information flow, captured by the notion of lens {X' \choose X} \leftrightarrows {Y' \choose Y}, and composition of such lenses describes the composition of subsystems into systems. But morphisms between systems are unidirectional, captured by the notion of chart {X' \choose X} \rightrightarrows {Y' \choose Y},. Algebraically, the relationship between these two notions is that they assemble into a double category, which indexes the category of systems.

There is another double category involving lenses which has been considered in the categorical study of systems. That is the double category of parametrized morphisms, applied to the monoidal category of lenses. These have been studied as an abstraction for gradient descent in several papers, see eg Reference [bruno-etal-categorical-learning-2021], Reference [bruno-thesis-fundamental-components], (the idea goes back to Reference [backprop-as-functor]). Given any action of a monoidal category \mathcal {M} on another category \mathcal {C} (most simply, if \mathcal {C} is monoidal it acts on itself,) we obtain a category of parametrized morphisms f: X \cdot P \to Y (where P \in \mathcal {M}, X, Y \in \mathcal {C},) and these turn out to be extremely useful. We will mention two applications:

  1. A parametrized lens {P \choose P} \otimes {X \choose X} \to {Y \choose Y} is essentially what is called a learner in Reference [backprop-as-functor]---it contains the information necessary to compute a new parameter value p' given an existing p \in P and a sample pair x \in X, y \in Y, as well as the additional information required to compose such things. Thus the functoriality of backpropagation can be derived from two facts: the reverse derivative defines a monoidal functor \mathsf {Euc} \to \mathsf {Lens}(\mathsf {Euc}), and the construction \mathsf {Para}(-), taking a category to its category of parametrized maps, is itself functorial. This viewpoint has been significantly developed in Reference [bruno-etal-categorical-learning-2021] and other papers.
  2. An open game, in the sense of Hedges Reference [hedges-etal-comp-gametheory], is almost the same thing as a parametrized lens {\Sigma ' \choose \Sigma } \otimes {S \choose X} \leftrightarrows {R \choose Y}, equipped with a subset E \subset \Sigma \times \mathsf {Set}(\Sigma ,\Sigma '). Given a context for the game---that is, a state x \in X (describing the state of information when the decision is made) and a continuation Y \to R (describing how decisions y \in Y map to outcomes r \in R,) we obtain a function k: \Sigma \to \Sigma ', and we say \sigma \in \Sigma is an equilibrium strategy if (\sigma ,k) \in E. Since \mathsf {Set}(\Sigma ,\Sigma ') = \mathsf {Lens}(\mathsf {Set})({\Sigma ' \choose \Sigma },I), and \Sigma = \mathsf {Lens}(\mathsf {Set})(I,{\Sigma ' \choose \Sigma }), this neatly captures the extra data of an open game in terms of the category of lenses. The potential of this idea as a generalized approach to "cybernetic systems" is explored in Reference [towards-cybercat].

In this chapter, we will develop the theory of the category \mathsf {Para} of parametrized maps. We will begin by reviewing the existing literature briefly. We will describe a double categorical version of this category---this does not seem to have appeared in the literature yet, although it has been folklore for at least a few years (and there is nothing complicated about this construction, certainly). The remainder of this chapter will be dedicated to lifting this construction to a generic 2-category \mathbb {C} (with the above being the specialization to \mathbb {C} = \mathsf {Cat} ). We will derive this lifting using the machinery of 2-category theory. We will see how this generalization accounts for much structure which can be seen to exist on \mathsf {Para}, such as its symmetric monoidal structure (assuming \mathcal {M},\mathcal {C} are symmetric monoidal). But the true application of this will be in § [efr-ZRUZ], where we use this to construct a triple category of open dynamical systems.

The definition of the double category \mathsf {\mathbb Para} involves two types of categorical structure with which the reader may be unfamiliar---actegories, which are the input to the construction, and pseudo double categories, which are the output. Since we will shortly introduce the abstract internal versions of these, internal pseudomonoid actions and internal pseudocategories, we will not give a separate introduction here. The reader who is unfamiliar with these should refer to Reference [actegories-amthematician-capucci-gavranovic] for actegories, and Reference [shulman-monfibs] for (pseudo) double categories. A reader who simply needs a definition may look at Definition [efr-OFNV] and Example [efr-ZRUY].