Finite MDPs and Bellman operators — Examples

Take the finite MDP with $S=\{s\}$, $A(s)=\{a\}$, reward alphabet $\mathcal{R}=\{1\}$, and $p(s,1\mid s,a)=1$. At $\gamma =1$, the first $N$ terms of the return sum to $N$, so the undiscounted return diverges. The formal backup $F:\mathbb{R}\to \mathbb{R}$, $F(v)=1+v$, has no real fixed point and is not a contraction with any constant $0\le q<1$ in the usual metric $d_{\mathbb{R}}(v,w)=\mathrm{\mid }v-w\mathrm{\mid }$.

The finite MDP data and joint reward-transition convention.

Sutton and Barto, Reinforcement Learning: An Introduction.

The diagram uses a circle for the state and a rectangle for the action. The arrow from the state to the action indicates the sole policy choice; the return arrow is the transition with joint mass $p(s,1\mid s,a)=1$. The value of $\gamma$ is specified in the example statement and is not encoded by the graph. The verification does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[circle,draw] (s) at (0,0) {$s$};
  \node[rectangle,draw] (a) at (2,0) {$a$};
  \draw[->] (s) -- node[above] {choose $a$} (a);
  \draw[->] (a) to[bend left=35] node[below] {$p(s,1\mid s,a)=1$} (s);
\end{tikzpicture}

Let $S=\{s\}$, $A(s)=\{a,b\}$, and $\gamma =1\mathrm{/}2$. Both actions return deterministically to $s$, with reward $1$ under $a$ and reward $3$ under $b$. View the deterministic policies choosing $a$ and $b$ as stationary policies assigning probability one to those actions; their unique policy Bellman fixed points are $2$ and $6$, respectively. More generally, for a stationary policy with $\theta :=\pi (b\mid s)\in [0,1]$, its fixed point is $2+4\theta$. After adding $2$ to both rewards, the deterministic-policy fixed points are $6$ and $10$, and the fixed point for the same stochastic policy is $6+4\theta$. Thus every policy value shifts by $2\mathrm{/}(1-\gamma )=4$, the difference between the two deterministic-policy values remains $4$, and $b$ maximizes the Bellman optimality backup at the optimal fixed point in both models.

The one-state joint reward-transition model.

The policy evaluation formula.

The greedy action-value formula.

Uniqueness of the displayed Bellman fixed points.

Sutton and Barto, Reinforcement Learning: An Introduction.

The diagram shows the original MDP only: circles are states, rectangles are actions, state-to-action arrows show the two action choices, and return arrows are labeled by their joint transition masses. The shifted MDP changes the two reward labels from $1,3$ to $3,5$ while leaving both transition probabilities equal to one. The verification does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[circle,draw] (s) at (0,0) {$s$};
  \node[rectangle,draw] (a) at (-2,1.4) {$a$};
  \node[rectangle,draw] (b) at (2,1.4) {$b$};
  \draw[->] (s) -- node[above left] {choose $a$} (a);
  \draw[->] (a) to[bend left=22] node[left] {$p(s,1\mid s,a)=1$} (s);
  \draw[->] (s) -- node[above right] {choose $b$} (b);
  \draw[->] (b) to[bend right=22] node[right] {$p(s,3\mid s,b)=1$} (s);
\end{tikzpicture}

Let $S=\{s\}$, $A(s)=\{a\}$, $\gamma =1\mathrm{/}2$, with a deterministic self-loop reward $1$, and initialize $V_0(s)=0$. Then $V^{\ast }(s)=2$ and $V_m(s)=2(1-2^{-m})$, so

$\mathrm{\parallel }{V}_m-V^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}=2^{1-m}={\gamma }^m\mathrm{\parallel }{V}_0-V^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$

for every $m\ge 0$; the general value-iteration error bound is attained at every iteration.

The one-state deterministic MDP data.

The one-state Bellman backup.

The finite-iterate value-iteration procedure.

The general contraction error estimate.

Sutton and Barto, Reinforcement Learning: An Introduction.

The diagram shows the one-state model used by the value-iteration calculation. The circle is the state, the rectangle is its sole action, and the labeled return arrow is the deterministic transition with reward $1$. The discount and initial value are specified in the example statement; the verification does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[circle,draw] (s) at (0,0) {$s$};
  \node[rectangle,draw] (a) at (2,0) {$a$};
  \draw[->] (s) -- node[above] {choose $a$} (a);
  \draw[->] (a) to[bend left=35] node[below] {$p(s,1\mid s,a)=1$} (s);
\end{tikzpicture}

Let $S=\{s\}$, $A(s)=\{a,b\}$, $\gamma =1\mathrm{/}2$, and let both actions give reward $0$ and return deterministically to $s$. Start exact policy iteration from the deterministic policy ${\pi }_0(s)=a$. The policy value is $0$, and both actions are greedy. The tie-retaining procedure keeps $a$ and stops after its first evaluation; a rule that always switches to the other maximizing action alternates forever between $a$ and $b$.

The one-state MDP and its two action laws.

The exact policy evaluation map.

The greedy action-value formula.

The exact policy-iteration tie-retention rule.

Sutton and Barto, Reinforcement Learning: An Introduction.

The diagram uses a circle for the state and rectangles for the available action nodes. Arrows from the state to each action show the available choices, not a single policy; arrows back to the state show each deterministic transition, labeled with probability and reward. The example separately specifies the initial policy and the alternative switching rule, and the verification does not rely on the drawing.