Finite MDPs and Bellman operators

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.

Let $M\ge 0$, $0\le \gamma <1$, and let $({\rho }_j{)}_{j\ge 1}$ be any real sequence with $\mathrm{\mid }{\rho }_j\mathrm{\mid }\le M$. Then the series

${\sum }_{j=0}^{\mathrm{\infty }}{\gamma }^j{\rho }_{j+1}$

converges absolutely; write $G$ for its sum. Every partial sum and the limit satisfy

$\mid {\sum }_{j=0}^{N-1}{\gamma }^j{\rho }_{j+1}\mid \le \frac{M}{1-\gamma },\mathrm{\mid }G\mathrm{\mid }\le \frac{M}{1-\gamma }\mathrm{.}$

For every integer $N\ge 0$,

$\mid G-{\sum }_{j=0}^{N-1}{\gamma }^j{\rho }_{j+1}\mid \le \frac{M{\gamma }^N}{1-\gamma },$

where the partial sum at $N=0$ is empty and ${\gamma }^0=1$, including when $\gamma =0$.

Sutton and Barto, Reinforcement Learning: An Introduction.

For any finite set $S$, let $B(S)={\mathbb{R}}^S$, the set of real-valued functions on $S$. Define

$d_{\mathrm{\infty }}(U,V)=\{\begin{array}{ll}0,& S=\mathrm{\varnothing },\\ {\max }_{s\in S}\mathrm{\mid }U(s)-V(s)\mathrm{\mid },& S\mathrm{\ne }\mathrm{\varnothing }\mathrm{.}\end{array}$

Then $d_{\mathrm{\infty }}$ is a metric on $B(S)$ and $(B(S),d_{\mathrm{\infty }})$ is complete.

Mozgovoy, Lecture Notes on Metric Spaces and Functional Analysis.

Sutton and Barto, Reinforcement Learning: An Introduction.

• The proof is a finite-coordinate Cauchy argument. The maximum norm makes each coordinate sequence Cauchy; completeness of the real line supplies its limit; one maximum of finitely many thresholds then gives convergence in the maximum norm.
• The same argument proves completeness for the $d_1$ metric on ${\mathbb{R}}^n$. Each coordinate difference is at most $d_1$. Given rational $\epsilon >0$, choose for every coordinate a threshold at tolerance $\epsilon \mathrm{/}(2n)$, which is again a positive rational; after taking their finite maximum, monotonicity of finite sums gives $d_1(x^{(m)},y)\le n\epsilon \mathrm{/}(2n)=\epsilon \mathrm{/}2<\epsilon$. The $d_{\mathrm{\infty }}$ case is proved above. No later result on this page uses the $d_1$ observation.
• No choice is spent. The limit point is assembled coordinatewise from unique limits, each threshold is the least one that works, and a common threshold is obtained by taking the maximum of finitely many indices.
• The real completeness input is localised. The Cauchy criterion in $\mathbb{R}$ is the only completeness theorem used. Its proof obtains real completeness from the least-upper-bound property through Bolzano–Weierstrass; the finite-coordinate argument adds no other completeness assumption.

The taxicab and supremum metrics.

Monotonicity and constant-summand laws for finite sums.

Assume the Axiom of Choice. Let a finite MDP have nonempty state set $S$, and let $\pi$ be a stationary Markov policy. Put $E=S\times (\mathcal{R}\cup \{0\})$ with its discrete sigma-algebra and define, for $x=(s,\eta )\in E$ and $B\subseteq E$,

$K_{\pi }(x,B)={\sum }_{a\in A(s)}\pi (a\mid s){\sum }_{\begin{array}{c}{s}^{\mathrm{\prime }}\in S\\ \rho \in \mathcal{R}\end{array}}{1}_B(s^{\mathrm{\prime }},\rho )p(s^{\mathrm{\prime }},\rho \mid s,a)\mathrm{.}$

Then $K_{\pi }$ is a probability kernel on $E$. For each initial state $s\in S$, there is a probability law on $E^{\mathbb{N}}$ whose coordinate process starts at $(s,0)$ and is a time-homogeneous Markov chain with transition kernel $K_{\pi }$ relative to its natural filtration.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

For a finite MDP, a discount $0\le \gamma <1$, and a stationary Markov policy $\pi$, define the policy Bellman operator $T^{\pi }:{\mathbb{R}}^S\to {\mathbb{R}}^S$ by

$(T^{\pi }V)(s)={\sum }_{a\in A(s)}\pi (a\mid s)[r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V(s^{\mathrm{\prime }})](s\in S)\mathrm{.}$

If $S=\mathrm{\varnothing }$, this is the unique map from ${\mathbb{R}}^S$ to itself.

The joint reward-transition model, expected reward, transition probabilities, and stationary Markov policies.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

For a finite MDP and a discount $0\le \gamma <1$, define the Bellman optimality operator $T^{\ast }:{\mathbb{R}}^S\to {\mathbb{R}}^S$ by

$(T^{\ast }V)(s)={\max }_{a\in A(s)}[r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V(s^{\mathrm{\prime }})](s\in S)\mathrm{.}$

The maximum exists because each $A(s)$ is finite and nonempty. If $S=\mathrm{\varnothing }$, this is the unique map from ${\mathbb{R}}^S$ to itself.

The finite state-dependent action sets, expected reward, and transition probabilities.

A maximum is an attained upper bound belonging to the set.

Every finite nonempty set of real action values has an attained maximum.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

Let a finite MDP have $0\le \gamma <1$ and let $\pi$ be a stationary Markov policy. If $S=\mathrm{\varnothing }$, define $V^{\pi }$ to be the unique empty function; no path law or choice axiom is needed in this case. If $S\mathrm{\ne }\mathrm{\varnothing }$, assume the Axiom of Choice and, for each $s\in S$, use the path law started at $X_0=(s,0)$ supplied by the policy-induced reward-state chain; write $X_t=(S_t,R_t)$. The discounted return is

$G_t={\sum }_{j=0}^{\mathrm{\infty }}{\gamma }^j{R}_{t+j+1},$

and the state value under $\pi$ is $V^{\pi }(s)={\mathbb{E}}_{\pi ,s}[G_0]$, where ${\mathbb{E}}_{\pi ,s}$ is expectation under that start-state law. If $S=\mathrm{\varnothing }$, $V^{\pi }$ is the unique empty function. The reward sequence bound gives $\mathrm{\mid }{G}_t\mathrm{\mid }\le M\mathrm{/}(1-\gamma )$, so each return is measurable and integrable. This is the start-state meaning of ${\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ when that conditional expectation is defined. The definition concerns discounted infinite-horizon tasks; average-reward and undiscounted continuing models, and improper episodic tasks, are outside its scope.

The coordinate $0$ in $X_0=(s,0)$ is only a dummy initial reward; the chain's one-step kernel emits rewards in $\mathcal{R}$. Finite partial sums of the return are measurable, their pointwise limit is measurable, and the constant bound $M\mathrm{/}(1-\gamma )$ is an integrable majorant on the probability space.

The finite joint reward-transition model and its bounded reward alphabet.

The Axiom of Choice, used only in the nonempty-state path-law branch.

The policy-induced homogeneous reward-state chain and its start-state path law.

The conditional one-step transition-kernel identity defining a homogeneous Markov chain.

Absolute convergence and the uniform tail bound for bounded discounted rewards.

Finite sums and scalar multiples of measurable functions are measurable.

A measurable real-valued coordinate on a probability space is a real random variable.

A pointwise limit of measurable functions is measurable.

A measurable pointwise limit under one integrable majorant is integrable, and its expectations are the limits of the partial expectations.

Expectation of an integrable real random variable is its finite Lebesgue integral.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

Let a finite MDP and a discount $0\le \gamma <1$ be fixed. For $U\in {\mathbb{R}}^S$, define $\mathrm{\parallel }U{\mathrm{\parallel }}_{\mathrm{\infty }}=0$ if $S=\mathrm{\varnothing }$, and $\mathrm{\parallel }U{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_{s\in S}\mathrm{\mid }U(s)\mathrm{\mid }$ otherwise. For every stationary policy $\pi$ and all $V,W\in {\mathbb{R}}^S$,

$\mathrm{\parallel }{T}^{\pi }V-T^{\pi }W{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }V-W{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{.}$

The Bellman optimality operator satisfies the same inequality. Each of $T^{\pi }$ and $T^{\ast }$ has exactly one fixed point in ${\mathbb{R}}^S$. The contraction constant is the nonnegative number $\gamma$.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

The proof uses $\gamma$ itself as the contraction constant. No absolute-value reinterpretation is needed because the discounted domain already assumes $0\le \gamma <1$.

Input a finite MDP, a discount $0\le \gamma <1$, an initial value function $V_0\in {\mathbb{R}}^S$, and an integer $m\ge 0$. Set $V_{j+1}=T^{\ast }{V}_j$ for $j=0,\dots ,m-1$ and return $V_m$. This procedure returns the exact $m$th iterate and makes no finite-termination claim for convergence.

The Bellman optimality map used at each step.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

For a finite MDP, a discount $0\le \gamma <1$, and any stationary Markov policy $\pi$, the expected discounted state value defined from each initial state satisfies

$T^{\pi }{V}^{\pi }=V^{\pi }\mathrm{.}$

If $S=\mathrm{\varnothing }$, this is the equality of the unique empty functions and no choice axiom is needed. If $S\mathrm{\ne }\mathrm{\varnothing }$, assume the Axiom of Choice for the path-law definition of $V^{\pi }$.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

Choice for the nonempty-state chain construction.

Let $V^{\ast }$ be the unique fixed point of $T^{\ast }$ for a finite MDP with $0\le \gamma <1$. For every initial $V_0\in {\mathbb{R}}^S$ and every $m\in \mathbb{N}$, the exact value-iteration iterates $V_{m+1}=T^{\ast }{V}_m$ satisfy

$\mathrm{\parallel }{V}_m-V^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le {\gamma }^m\mathrm{\parallel }{V}_0-V^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }},$

with ${\gamma }^0=1$.

Sutton and Barto, Reinforcement Learning: An Introduction.

Input a finite MDP, a discount $0\le \gamma <1$, an initial deterministic policy ${\pi }_0$, and, for each state $s$, an ordered list containing each member of $A(s)$ exactly once. For $k=0,1,\dots$:

1. Associate to each deterministic policy ${\pi }_k$ the stationary Markov policy ${\widehat{\pi }}_k(a\mid s)=1$ if $a={\pi }_k(s)$ and $0$ otherwise. Compute the unique exact policy evaluation $V_k\in {\mathbb{R}}^S$ satisfying $T^{{\widehat{\pi }}_k}{V}_k=V_k$.
2. For each $s$, set

$Q_k(s,a)=r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V_k(s^{\mathrm{\prime }})\mathrm{.}$

If ${\pi }_k(s)$ attains ${\max }_{a\in A(s)}{Q}_k(s,a)$, set ${\pi }_{k+1}(s)={\pi }_k(s)$. Otherwise set ${\pi }_{k+1}(s)$ to the earliest maximizing action in the supplied list. 3. If ${\pi }_{k+1}={\pi }_k$, return $({\pi }_k,V_k)$. Otherwise continue with ${\pi }_{k+1}$.

The operator fixed point used for exact policy evaluation exists and is unique by the finite-MDP contraction theorem.

The finite MDP data and deterministic policies.

The policy evaluation map.

The greedy action values.

Existence and uniqueness of each exact policy evaluation.

Sutton and Barto, Reinforcement Learning: An Introduction.

Let a finite MDP and $0\le \gamma <1$ be fixed, and let $V^{\ast }$ denote the unique fixed point of $T^{\ast }$. If $S=\mathrm{\varnothing }$, the statewise claims below are vacuous and the policy iteration procedure returns the unique empty policy after one evaluation, without Choice. If $S\mathrm{\ne }\mathrm{\varnothing }$, assume the Axiom of Choice. For a stationary policy $\pi$, let $V^{\pi }$ be its expected discounted state value. For a deterministic policy $\sigma$, define its associated stationary policy by $\widehat{\sigma }(a\mid s)=1$ if $a=\sigma (s)$ and $0$ otherwise, and interpret $T^{\sigma }$ and $V^{\sigma }$ as $T^{\widehat{\sigma }}$ and $V^{\widehat{\sigma }}$.

$Q_V(s,a)=r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V(s^{\mathrm{\prime }})\mathrm{.}$

If a deterministic policy ${\pi }^{\mathrm{\prime }}$ chooses an action maximizing $Q_{V^{\pi }}(s,a)$ at every state, then $V^{{\pi }^{\mathrm{\prime }}}(s)\ge V^{\pi }(s)$ for every $s$. If $(T^{{\pi }^{\mathrm{\prime }}}{V}^{\pi })(s)>V^{\pi }(s)$ at any state, the value inequality is strict at some state.

For exact finite policy iteration, supply an initial deterministic policy and a finite ordered list of the actions at each state; evaluate each policy at its exact Bellman fixed point; retain the current action whenever it is already greedy; otherwise choose the earliest maximizing action in the supplied list. Every changed policy then strictly improves the value at some state and weakly improves it at every state. The procedure makes at most $N_{\mathrm{d}\mathrm{e}\mathrm{t}}-1$ changes, where $N_{\mathrm{d}\mathrm{e}\mathrm{t}}$ is the finite number of deterministic policies, and terminates at a deterministic policy whose value is $V^{\ast }$; this value dominates the value of every stationary policy.

Sutton and Barto, Reinforcement Learning: An Introduction.

Choice for the nonempty-state path-law interpretation of policy values.