Finite Markov decision process with joint reward-transition law

Let $S$ be a finite set, possibly empty, let $\mathcal{R}$ be a finite subset of $\mathbb{R}$, and for each $s\in S$ let $A(s)$ be a finite nonempty set. Here finite means bijective with a natural number, and the discrete sigma-algebra on a set is its power set. Write $D=\{(s,a):s\in S,a\in A(s)\}$. A finite Markov decision process (MDP) consists of these sets and numbers $p(s^{\mathrm{\prime }},\rho \mid s,a)\in [0,1]$, indexed by $(s,a)\in D$, $s^{\mathrm{\prime }}\in S$, and $\rho \in \mathcal{R}$, with

${\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}p(s^{\mathrm{\prime }},\rho \mid s,a)=1((s,a)\in D)\mathrm{.}$

Equip each set used here, including $D$, with its power-set (discrete) sigma-algebra. Thus $p$ is the point-mass form of a probability kernel from $D$ to $S\times \mathcal{R}$: each input assigns a probability measure on $S\times \mathcal{R}$, and every event section is measurable. The joint law allows the next state and reward to be dependent. Define the expected reward and state-transition probabilities by

$r(s,a)={\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}\rho p(s^{\mathrm{\prime }},\rho \mid s,a),P(s^{\mathrm{\prime }}\mid s,a)={\sum }_{\rho \in \mathcal{R}}p(s^{\mathrm{\prime }},\rho \mid s,a)\mathrm{.}$

If $\mathcal{R}\mathrm{\ne }\mathrm{\varnothing }$, put $M={\max }_{\rho \in \mathcal{R}}\mathrm{\mid }\rho \mathrm{\mid }$; if $\mathcal{R}=\mathrm{\varnothing }$, put $M=0$. A stationary Markov policy is a family of probabilities $\pi (a\mid s)\ge 0$ with ${\sum }_{a\in A(s)}\pi (a\mid s)=1$ for every $s\in S$. A deterministic policy is a function $\pi$ with $\pi (s)\in A(s)$ for every $s$. When $S=\mathrm{\varnothing }$, these families and policies are the unique empty functions and all statewise formulas are vacuous.

A probability kernel assigns a probability measure at every input and has measurable event sections.

A set is finite when it is bijective with some natural number.

A Cartesian product pairs each element of A with an element of B.

A sum over a finite set is defined by any enumeration, with permutation invariance ensuring a unique value.

A maximum is an element of the set that bounds every element above.

Every nonempty finite set of real numbers has an attained maximum.

Absolute value is multiplicative and satisfies the triangle inequality.

The absolute value of a finite sum is at most the sum of the absolute values.

Finite sums preserve termwise inequalities and commute with scaling.

Sutton and Barto, Reinforcement Learning: An Introduction.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.

For nonempty $S$, each $A(s)$ is nonempty, so the normalization for an admissible pair forces $\mathcal{R}$ to be nonempty. For every admissible $(s,a)$, $P(s^{\mathrm{\prime }}\mid s,a)\ge 0$ and

${\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)={\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}p(s^{\mathrm{\prime }},\rho \mid s,a)=1,$

so $P(\cdot \mid s,a)$ is a probability distribution. Also, $\mathrm{\mid }\rho \mathrm{\mid }\le M$ and $p\ge 0$ give

$\mathrm{\mid }r(s,a)\mathrm{\mid }\le {\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}\mathrm{\mid }\rho \mathrm{\mid }p(s^{\mathrm{\prime }},\rho \mid s,a)\le M{\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}p(s^{\mathrm{\prime }},\rho \mid s,a)=M\mathrm{.}$

Thus both derived marginals are well defined and the expected reward is bounded by the maximum absolute reward. The separate marginals are derived from the joint law; specifying unrelated reward and transition marginals would not preserve their possible dependence.