Editing Markov decision process (section)

===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 time|continuous dynamics]], i.e.,&nbsp;the system dynamics is defined by [[ordinary differential equation]]s (ODEs). These kind of applications raise in [[queueing system]]s, epidemic processes, and [[population process]]es.

Like the discrete-time Markov decision processes, in continuous-time Markov decision processes the agent aims at finding the optimal ''policy'' which could maximize the expected cumulated reward. The only difference with the standard case stays in the fact that, due to the continuous nature of the time variable, the sum is replaced by an integral:
:<math>\max \operatorname{E}_\pi\left[\left. \int_0^\infty\gamma^t r(s(t),\pi(s(t))) \, dt \;\right| s_0 \right]</math>
where <math>0\leq\gamma< 1.</math>

====Discrete space: 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 [[Ergodicity|ergodic]] continuous-time Markov chain under a stationary [[policy]]. Under this assumption, although the decision maker can make a decision at any time in the current state, there is no benefit in taking multiple actions. It is better to take an action only at the time when system is transitioning from the current state to another state. Under some conditions,<ref>{{Cite book |url=https://link.springer.com/book/10.1007/978-3-642-02547-1 |title=Continuous-Time Markov Decision Processes |series=Stochastic Modelling and Applied Probability |date=2009 |volume=62 |language=en |doi=10.1007/978-3-642-02547-1|isbn=978-3-642-02546-4 }}</ref> if our optimal value function <math>V^*</math> is independent of state <math>i</math>, we will have the following inequality:
:<math>g\geq R(i,a)+\sum_{j\in S}q(j\mid i,a)h(j) \quad \forall i \in S \text{ and } a \in A(i)</math>
If there exists a function <math>h</math>, then <math>\bar V^*</math> will be the smallest <math>g</math> satisfying the above equation. In order to find <math>\bar V^*</math>, we could use the following linear programming model:
*Primal linear program(P-LP)
:<math>
\begin{align}
\text{Minimize}\quad &g\\
\text{s.t} \quad & g-\sum_{j \in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,
\forall i\in S,\,a\in A(i)
\end{align}
</math>
*Dual linear program(D-LP)
:<math>
\begin{align}
\text{Maximize} &\sum_{i\in S}\sum_{a\in A(i)}R(i,a)y(i,a)\\
\text{s.t.} &\sum_{i\in S}\sum_{a\in A(i)} q(j\mid i,a)y(i,a)=0 \quad
\forall j\in S,\\
& \sum_{i\in S}\sum_{a\in A(i)}y(i,a)=1,\\
& y(i,a)\geq 0 \qquad \forall a\in A(i) \text{ and } \forall i\in S
\end{align}
</math>
<math>y(i,a)</math> is a feasible solution to the D-LP if <math>y(i,a)</math> is nonnative and satisfied the constraints in the D-LP problem. A feasible solution <math>y^*(i,a)</math> to the D-LP is said to be an optimal solution if
:<math>
\begin{align}
\sum_{i\in S}\sum_{a\in A(i)}R(i,a)y^*(i,a) \geq  \sum_{i\in S} \sum_{a\in A(i)} R(i,a) y(i,a)
\end{align}
</math>
for all feasible solution <math>y(i,a)</math> to the D-LP. Once we have found the optimal solution <math>y^*(i,a)</math>, we can use it to establish the optimal policies.

====Continuous space: Hamilton–Jacobi–Bellman equation====
In continuous-time MDP, if the state space and action space are continuous, the optimal criterion could be found by solving [[Hamilton–Jacobi–Bellman equation|Hamilton–Jacobi–Bellman (HJB) partial differential equation]]. In order to discuss the HJB equation, we need to reformulate
our problem
:<math>\begin{align} V(s(0),0)= {} & \max_{a(t)=\pi(s(t))}\int_0^T r(s(t),a(t)) \, dt+D[s(T)] \\
\text{s.t.}\quad & \frac{d s(t)}{dt}=f[t,s(t),a(t)]
\end{align}
</math>

<math>D(\cdot)</math> is the terminal reward function, <math>s(t)</math> is the system state vector, <math>a(t)</math> is the system control vector we try to find. <math>f(\cdot)</math> shows how the state vector changes over time. The Hamilton–Jacobi–Bellman equation is as follows:
:<math>0=\max_u ( r(t,s,a) +\frac{\partial V(t,s)}{\partial x}f(t,s,a)) </math>
We could solve the equation to find the optimal control <math>a(t)</math>, which could give us the optimal [[value function]] <math>V^*</math>