Finite discounted MDP with bounded real rewards

Let $S$ be a nonempty finite set, let $A(s)$ be a nonempty finite set for each $s\in S$, and let $D=\{(s,a):s\in S,a\in A(s)\}$. Here finite means bijective with a natural number. Put $S_0=\mathrm{\mid }S\mathrm{\mid }$ and $A_0={\max }_{s\in S}\mathrm{\mid }A(s)\mathrm{\mid }$. Fix a discount $0\le \gamma <1$. Give $S$ and $D$ their discrete sigma-algebras and give $[0,1]$ its Borel sigma-algebra. A bounded-reward finite discounted Markov decision process is a probability kernel $K$ from $D$ to $S\times [0,1]$. At pair $(s,a)$, $K(\cdot \mid s,a)$ is the joint law of the next state and the reward; these two coordinates need not be independent. Define the state-transition probabilities and expected rewards by

$P(s^{\mathrm{\prime }}\mid s,a)=K(\{s^{\mathrm{\prime }}\}\times [0,1]\mid s,a),r(s,a)={\int }_{S\times [0,1]}\rho K(d{s}^{\mathrm{\prime }},d\rho \mid s,a)\mathrm{.}$

A history-dependent behavior is a sequence of probability kernels from observed-history spaces $H_t$ to the finite action alphabet $\mathcal{A}={\bigcup }_{s\in S}A(s)$, assigning probability zero to actions outside $A(s_t)$ at every history ending in state $s_t$. Here $H_t$ consists of histories $(s_0,a_0,R_1,s_1,\dots ,a_{t-1},R_t,s_t)$, with discrete sigma-algebras on finite state/action coordinates and the Borel sigma-algebra on each reward coordinate; it has the resulting finite-product sigma-algebra. A stationary Markov policy assigns one distribution on $A(s)$ to each state, independently of earlier history. During interaction, after choosing $a_t$ in state $s_t$, the next pair $(s_{t+1},R_{t+1})$ is drawn from $K(\cdot \mid s_t,a_t)$.

Finite state/action sets, admissible pairs, and the joint next-state/reward convention; this item replaces its finite reward-alphabet restriction by a Borel law on the unit interval.

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

The Borel sigma-algebra is generated by the open sets of a topological space.

The product sigma-algebra is generated by measurable rectangles.

The state-reward sample space is a Cartesian product.

Expectation is the Lebesgue integral of a measurable random variable.

The reward-coordinate projection is measurable: the inverse image of a Borel set $B\subseteq [0,1]$ is the measurable rectangle $S\times B$. Since $0\le \rho \le 1$, monotonicity of the nonnegative integral gives $0\le \int \rho dK\le \int 1dK=K(S\times [0,1])=1$.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Sutton and Barto, Reinforcement Learning: An Introduction.