and sends the next input to the automaton. Category theoretic interpretation Other than the rewards, a Markov decision process can be understood in terms of Category theory. Namely, let denote the free monoid with generating set A. Let Dist denote the Kleisli category of the Giry monad. Then a functor encodes both the set S of states and the probability function P. In this way, Markov decision processes could be generalized from monoids (categories with one object) to arbitrary categories. One can call the result a context-dependent Markov decision process, because moving from one object to another in changes the set of available actions and the set of possible states. Continuous-time Markov decision process In discrete-time Markov Decision Processes, decisions are made at discrete time intervals. However, for continuous-time Markov decision processes, decisions can be made at any time the decision maker chooses. In comparison to discrete-time Markov decision processes, continuous-time Markov decision processes can better model the decision making process for a system that has continuous dynamics, i.e., the system dynamics is defined by ordinary differential equations (ODEs). Definition In order to discuss the continuous-time Markov decision process, we introduce two sets of notations: If the state space and action space are finite, : State space; : Action space; : , transition rate function; : , a reward function. If the state space and action space are continuous, : state space; : space of possible control; : , a transition rate function; : , a reward rate function such that , where is the reward function we discussed in previous case. Problem Like the discrete-time Markov decision processes, in continuous-time Markov decision processes we want to find the optimal policy or control which could give us the optimal expected integrated reward: where Linear programming formulation If the state space and action space are finite, we could use linear programming to find the optimal policy, which was one of the earliest approaches applied. Here we only consider the ergodic model, which means our continuous-time MDP becomes an ergodic continuous-time Markov chain under a stationary policy. Under this assumption, although the decision maker can make a decision at any time at the current state, they could not benefit more by taking more than one action. It is better for them to take an action only at the time when system is transitioning from the current state to another state. Under some