# Markov reward process

A Markov reward process is a [Markov chain](https://www.edgepedia.org/markov-chain) with numerical rewards attached to its states or transitions, together with a discount factor; it models a stochastic system whose behavior is scored over time but not controlled.<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup> In reinforcement learning it is the mathematical model of policy evaluation: once a policy is fixed and the agent no longer chooses actions, the decision problem collapses into evaluating such a process.<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup> In performance and reliability engineering the same construction appears as the Markov reward model, a continuous-time Markov chain with a reward rate attached to each state.<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup>

| Key fact | Detail |
|---|---|
| Formal definition | A tuple (S, P, R, γ): finite state space S, transition model P(s′\|s), reward function R: S → ℝ, and discount factor γ between 0 and 1<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup> |
| Return | \( G_t = \sum_{i=t}^{H-1} \gamma^{i-t} r_i \), the discounted sum of rewards from time t to the horizon H<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup> |
| Bellman equation | \( V = r + \gamma P V \), with closed-form solution \( V = (I - \gamma P)^{-1} r \) for a finite discounted process<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup> |
| Relation to MDPs | Fixing a policy π in an MDP produces a Markov reward process with transition matrix P(π) and rewards r(π)<sup>[4](https://jmlr2020.csail.mit.edu/papers/volume22/20-445/20-445.pdf)</sup> |
| Engineering form | A continuous-time Markov chain with a reward rate per state; upstates may carry reward rate 1 and down states 0 in a reliability model<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup> |
| Measures | Expected steady-state reward rate, expected instantaneous reward rate, and the distribution of accumulated or time-averaged reward over a finite interval<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup> |
| Expressivity limit | Scalar Markovian rewards cannot express most instances of multi-objective, risk-sensitive, and modal reinforcement learning tasks<sup>[5](https://proceedings.mlr.press/v216/skalse23a.html)</sup> |

## Formal structure

The standard discrete-time definition takes a finite state space S, a transition probability model P specifying P(s′\|s), a reward function R mapping states to real numbers, and a discount factor γ in [0, 1).<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup> Each transition from a state s to a successor s′ carries a reward depending on the current state, so an episode of the process is a sequence (s₀, r₀, s₁, r₁, s₂, r₂, ...). Rewards may be deterministic or stochastic; under the usual stationarity assumption, only the expected reward R(s) = E[r₀ \| s₀ = s] matters, and R can be represented as a vector of dimension \|S\|.<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup>

The horizon H is the number of time steps in an episode and may be finite or infinite. The return G_t accumulates rewards from time t onward, weighting a reward received i − t steps later by γ^(i−t).<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup> Discounting has both a computational and a behavioral role. With an infinite horizon and γ = 1, the return can diverge even when all rewards are bounded, making the value function infinite and the problem unsolvable by computer; setting γ < 1 exponentially down-weights future rewards. When γ = 0 only the immediate reward matters, and when γ = 1 future rewards count as much as present ones. For a finite horizon with bounded rewards, γ = 1 is admissible because returns are always finite.<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup>

## Value function and the Bellman equation

The state value function V_t(s) is the expected return starting from state s at time t: V_t(s) = E[G_t \| s_t = s]. With an infinite horizon and stationary transitions and rewards, V_i(s) = V_j(s) for all i and j, so a single time-independent V(s) is defined.<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup>

Conditioning on the next state gives the Bellman expectation equation, \( V = r + \gamma P V \): the value of a state is its expected immediate reward plus the discounted value of its successor. For a finite discounted process this linear system solves in closed form as \( V = (I - \gamma P)^{-1} r \).<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup> Uniqueness of the discounted value function follows from the contraction property of the Bellman operator, and the value can also be read as a discounted, occupancy-weighted sum of future rewards.<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup> Three practical routes to computing V are [Monte Carlo](https://www.edgepedia.org/monte-carlo) simulation of episodes, the analytic linear-algebra solution, and iterative methods.<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup>

## Place among Markov decision processes

A [Markov decision process](https://www.edgepedia.org/markov-decision-process) adds actions to the Markov reward process: the reward at time i depends on both the state and the chosen action, and transitions follow P(s′\|s, a).<sup>[3](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)</sup> Fixing a stationary randomized policy π reduces the MDP to a Markov reward process whose transition matrix is P(π) with entries \( p_s(\pi) = \sum_{a} \pi_{s,a} \cdot p_{s,a} \) and whose reward vector is \( r_s(\pi) = \sum_{a} \pi_{s,a} \cdot \bar{r}_{s,a} \); its total expected discounted reward from initial distribution p₀ is \( \bar{r}_0 (I - \gamma P(\pi))^{-1} r(\pi) \).<sup>[4](https://jmlr2020.csail.mit.edu/papers/volume22/20-445/20-445.pdf)</sup> This reduction is why policy evaluation in reinforcement learning is exactly value computation for a Markov reward process.<sup>[1](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)</sup>

The lineage is old. [Ronald A. Howard](https://www.edgepedia.org/ronald-a-howard)'s 1960 monograph *Dynamic Programming and Markov Processes* includes a chapter titled "Markov Processes with Rewards" and develops the reward process with discounting, earning-rate equations, and the policy-iteration method on that basis.<sup>[6](https://books.google.com/books/about/Dynamic_programming_and_Markov_processes.html?id=fXJEAAAAIAAJ)</sup>

## Markov reward models in system evaluation

In dependability and performance engineering the same object is called a Markov reward model. These models describe a system's behavior with a continuous-time Markov chain and attach a reward rate to each state. The reward rate encodes what the analyst wants to measure: in a reliability or availability model, upstates may carry reward rate 1 and down states reward rate 0; in a queueing model, the reward rate of a state may be the number of jobs of a certain type in that state; in a combined performance-reliability model, it may be the computational capacity or a related performance measure.<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup> NASA's technical report motivates the construction for fault-tolerant aerospace computers, where reliability and the ability to complete critical workloads within a defined real-time interval must be modeled together.<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup>

The framework supports several families of measures. Expected steady-state and expected instantaneous reward rates are the basic quantities; more generally, the distribution of accumulated reward or time-averaged reward over a finite interval can be determined from the model's solution, which matters when the workload can be characterized deterministically or by distributions.<sup>[2](https://ntrs.nasa.gov/citations/19920004526)</sup> Reibman, Smith, and Kishor Trivedi, in a 1989 survey in the *European Journal of Operational Research*, derived instantaneous and cumulative measures of Markov and Markov reward model behavior and compared the complexity of competing algorithms, noting that such models are common tools for fault-tolerant system reliability prediction.<sup>[7](https://www.sciencedirect.com/science/article/pii/0377221789903354)</sup> In the stochastic reward model literature, when the structure-state process is a continuous-time homogeneous Markov chain the model is termed a Markov reward model, and such models are commonly used for combined performance and dependability analysis of fault-tolerant systems.<sup>[8](https://www.sciencedirect.com/science/article/abs/pii/S0026271497000450)</sup>

Numerical methods carry the load. The randomization method computes the expected transient reward rate at time t and the expected time-averaged reward rate over [0, t] for rewarded continuous-time Markov chains, is numerically stable with good error control, but becomes expensive for large stiff models; exploiting quasistationarity reduces that cost.<sup>[9](https://www.researchgate.net/publication/3044786_Transient_analysis_of_some_rewarded_Markov_models_using_randomization_with_quasistationarity_detection)</sup> [Sensitivity analysis](https://www.edgepedia.org/sensitivity-analysis) has its own literature: Van Dijk and Puterman examined how perturbations in the data of a discrete-time Markov reward process affect three quantities—the total expected reward over a finite horizon, the infinite-horizon expected discounted and average rewards, and the expected total reward accumulated up to a first-passage time—and derived absolute-error bounds for each, demonstrating the results on queueing systems, both finite and infinite, such as M/M/1/S.<sup>[10](https://www.cambridge.org/core/journals/advances-in-applied-probability/article/abs/perturbation-theory-for-markov-reward-processes-with-applications-to-queueing-systems/418639DD06032EF07077F5C35ECA1116)</sup>

## Rewards in model checking tools

Probabilistic model checkers implement reward structures directly. In PRISM, a model can be augmented with real values associated with states or transitions, specified in `rewards ... endrewards` blocks; a guard assigns a reward to every satisfying state, and multiple matching items sum. PRISM supports multiple named reward structures in one model, for example one counting total time and another counting failures.<sup>[11](https://www.prismmodelchecker.org/manual/ThePRISMLanguage/CostsAndRewards)</sup> The tool then evaluates properties about expected rewards with the `R` operator: reachability rewards accumulate reward until a target is met, cumulative rewards accumulate up to a time bound, instantaneous rewards read the reward at a fixed time, and steady-state rewards give the long-run average. For CTMCs, a state reward is interpreted as a rate, so t time units spent in a state with reward r accumulate r × t; a typical use is a reward of 1 per state meaning time, so that `R<=9.5 [ F z=2 ]` asserts the expected time to reach a condition is at most 9.5.<sup>[12](https://www.prismmodelchecker.org/manual/PropertySpecification/Reward-basedProperties)</sup>

## What a Markovian reward can express

The scalar, state-dependent reward of a Markov reward process has known limits. Skalse and Alessandro Abate, writing in the proceedings of the Thirty-Ninth Conference on [Uncertainty](https://www.edgepedia.org/uncertainty) in Artificial Intelligence, studied the expressivity of scalar Markovian reward functions and derived necessary and sufficient conditions for when tasks in three classes, multi-objective, risk-sensitive, and modal reinforcement learning, can be expressed with such a reward; they found that scalar Markovian rewards cannot express most instances in each class.<sup>[5](https://proceedings.mlr.press/v216/skalse23a.html)</sup> This motivates the non-Markovian extensions studied elsewhere, in which rewards depend on the execution history rather than only the current state.<sup>[5](https://proceedings.mlr.press/v216/skalse23a.html)</sup>

## References

1. [Markov Reward Processes, Chapter 3 of *Reinforcement Learning: A Mathematical Introduction*](https://wanghemath.github.io/Book-MathRL/chapters/chapter-03-markov-reward-processes.html)
2. [Markov reward processes, NASA Technical Reports Server NTRS 19920004526](https://ntrs.nasa.gov/citations/19920004526)
3. [CS234 Lecture 2 notes, Stanford University](https://web.stanford.edu/class/archive/cs/cs234/cs234.1224/CS234Win2019/slides/lnotes2.pdf)
4. [Robust Markov Decision Processes, Journal of Machine Learning Research 22 (2021)](https://jmlr2020.csail.mit.edu/papers/volume22/20-445/20-445.pdf)
5. [Skalse, J. & Abate, A. (2023). On the limitations of Markovian rewards to express multi-objective, risk-sensitive, and modal tasks. UAI 2023, PMLR 216:1974–1984](https://proceedings.mlr.press/v216/skalse23a.html)
6. [Ronald A. Howard (1960). Dynamic Programming and Markov Processes, MIT Press](https://books.google.com/books/about/Dynamic_programming_and_Markov_processes.html?id=fXJEAAAAIAAJ)
7. [Reibman, A., Smith, R., Trivedi, K. (1989). Markov and Markov reward model transient analysis: An overview of numerical approaches. European Journal of Operational Research 40(2):257–267](https://www.sciencedirect.com/science/article/pii/0377221789903354)
8. [Performance/dependability modelling using stochastic reward models: transient behaviour](https://www.sciencedirect.com/science/article/abs/pii/S0026271497000450)
9. [Carrasco, J. A. Transient analysis of some rewarded Markov models using randomization with quasistationarity detection](https://www.researchgate.net/publication/3044786_Transient_analysis_of_some_rewarded_Markov_models_using_randomization_with_quasistationarity_detection)
10. [Van Dijk, N. M. & Puterman, M. L. Perturbation theory for Markov reward processes with applications to queueing systems. Advances in Applied Probability](https://www.cambridge.org/core/journals/advances-in-applied-probability/article/abs/perturbation-theory-for-markov-reward-processes-with-applications-to-queueing-systems/418639DD06032EF07077F5C35ECA1116)
11. [PRISM Manual: The PRISM Language / Costs And Rewards](https://www.prismmodelchecker.org/manual/ThePRISMLanguage/CostsAndRewards)
12. [PRISM Manual: Property Specification / Reward-based Properties](https://www.prismmodelchecker.org/manual/PropertySpecification/Reward-basedProperties)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Stochastic processes › Markov chains and processes › Discrete-time Markov chains › Markov-additive and associated processes*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license