Well-defined discounted values and optimal Bellman fixed points

Fix a starting state and a history-dependent behavior, and write $D=\{(s,a):a\in A(s)\}$ as in [F1]. For a history $h_t$ ending at state $s$ and a measurable set $E\subseteq D\times S\times [0,1]$, define ${\mathrm{\Lambda }}_t(h_t,E)={\sum }_{a\in A(s)}{\pi }_t(a\mid h_t)\int 1_E((s,a),s^{\mathrm{\prime }},\rho )K(d{s}^{\mathrm{\prime }},d\rho \mid s,a)$. For each fixed $a$, the integrand section is measurable by the product sigma-algebra, and the finite weighted sum is measurable in $h_t$ because ${\pi }_t$ is a probability kernel; its total mass is ${\sum }_a{\pi }_t(a\mid h_t)=1$. Thus ${\mathrm{\Lambda }}_t$ is a probability kernel from histories to the fixed space $D\times S\times [0,1]$. Applying [F2] to this sequence of history kernels and the initial point mass gives the full interaction path law.

For a stationary policy $\pi$, define $T_{\pi }v(s)={\sum }_{a\in A(s)}\pi (a\mid s)[r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)v(s^{\mathrm{\prime }})]$. This is a real vector by the finite sums. For any $v,w:S\to \mathbb{R}$, the absolute difference of each bracketed backup is at most $\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)\mathrm{\mid }v(s^{\mathrm{\prime }})-w(s^{\mathrm{\prime }})\mathrm{\mid }\le \gamma \mathrm{\parallel }v-w{\mathrm{\parallel }}_{\mathrm{\infty }}$. Averaging over $\pi (a\mid s)$ preserves this bound, so $\mathrm{\parallel }{T}_{\pi }v-T_{\pi }w{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }v-w{\mathrm{\parallel }}_{\mathrm{\infty }}$.

For finite real lists $(x_a)$ and $(y_a)$, if $m={\max }_a\mathrm{\mid }{x}_a-y_a\mathrm{\mid }$, then $x_a\le y_a+m$ and $y_a\le x_a+m$ for every $a$, whence $\mathrm{\mid }{\max }_a{x}_a-{\max }_a{y}_a\mathrm{\mid }\le m$. Applying this and [F7] to the definition of $T^{\ast }$ gives $\mathrm{\parallel }{T}^{\ast }v-T^{\ast }w{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }v-w{\mathrm{\parallel }}_{\mathrm{\infty }}$. The operator maps $[0,1\mathrm{/}(1-\gamma ){]}^S$ into itself because rewards are in $[0,1]$ and transition probabilities sum to one.

Each reward coordinate on the product path space is measurable and lies in $[0,1]$. The finite partial discounted sums are measurable, increase pointwise, and are bounded above by ${\sum }_{j<n}{\gamma }^j\le 1\mathrm{/}(1-\gamma )$ by [F4]. Their pointwise limit is measurable by [F3] and has the same bound. By [F5] its expectation is the limit of the finite partial expectations and is finite; thus every behavior value is well-defined and lies in the stated interval.

For a stationary policy $\pi$, let $v_n^{\pi }(s)$ be the expected sum of its first $n$ discounted rewards from $s$, with $v_0^{\pi }=0$. The finite-prefix law from step 1.1 and conditioning on the first action and joint reward/next-state outcome give $v_{n+1}^{\pi }(s)={\sum }_a\pi (a\mid s)\int [\rho +\gamma v_n^{\pi }(s^{\mathrm{\prime }})]K(d{s}^{\mathrm{\prime }},d\rho \mid s,a)$. Apply [F10] to each integral to obtain $v_{n+1}^{\pi }(s)={\sum }_a\pi (a\mid s)[r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)v_n^{\pi }(s^{\mathrm{\prime }})]=T_{\pi }{v}_n^{\pi }(s)$; the finite action distribution is evaluated by the same finite weighted-sum formula in [F10]. The joint law allows dependence between reward and next state; the integral identity does not assume independence.

Start with $v_0=0$ and set $v_{n+1}=T^{\ast }{v}_n$. Since $0\le v_1\le 1$ and $T^{\ast }$ is a $\gamma$ contraction, induction gives $\mathrm{\parallel }{v}_{n+1}-v_n{\mathrm{\parallel }}_{\mathrm{\infty }}\le {\gamma }^n$. Thus for $m>n$, $\mathrm{\parallel }{v}_m-v_n{\mathrm{\parallel }}_{\mathrm{\infty }}\le {\sum }_{j=n}^{m-1}{\gamma }^j\le {\gamma }^n\mathrm{/}(1-\gamma )$; every coordinate is Cauchy and converges by [F8], uniformly because $S$ is finite. Its limit $v^{\ast }$ is a fixed point by the finite-sum/max formula and the contraction estimate. If $w^{\ast }$ were another fixed point, step 1.3 would give $\mathrm{\parallel }{v}^{\ast }-w^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le \gamma \mathrm{\parallel }{v}^{\ast }-w^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, so $v^{\ast }=w^{\ast }$.

The finite-horizon stationary-policy values converge to $V^{\pi }$ by step 2.1 and the geometric tail bound [F4]. Passing their finite recursions from step 2.2 to the limit is valid because each sum is finite and the maximum statewise error tends to zero; hence $T_{\pi }{V}^{\pi }=V^{\pi }$. If two fixed points existed, step 1.2 would give their distance at most $\gamma$ times itself, forcing equality.

We prove by induction on $n$ that, from every starting history ending at state $s$, every history-dependent continuation has $n$-reward expected discounted return at most $v_n(s)$ from step 2.3. The base $v_0=0$ is the empty-horizon return. For the successor step, condition on the first chosen action and the joint next-state/reward outcome $(s^{\mathrm{\prime }},\rho )$. The induction hypothesis applies to the extended history ending at $s^{\mathrm{\prime }}$, so its continuation return is pointwise at most $v_n(s^{\mathrm{\prime }})$, even when its action rule used the observed reward $\rho$. For each first action, monotonicity of integration and [F10] bound the conditional expected total by $r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)v_n(s^{\mathrm{\prime }})$. Averaging over the randomized first action by the finite weighted-sum formula in [F10] is at most its finite maximum, namely $T^{\ast }{v}_n(s)=v_{n+1}(s)$. Thus the claimed upper bound holds uniformly over histories and behaviors.

For any behavior, its omitted tail after $n$ rewards is at most ${\gamma }^n\mathrm{/}(1-\gamma )$ by [F4]. Therefore its infinite-horizon value is at most $v_n(s)+{\gamma }^n\mathrm{/}(1-\gamma )$. Letting $n\to \mathrm{\infty }$ and using step 2.3 proves that every behavior value is at most $v^{\ast }(s)$.

For each $s$, let $B_s$ be the nonempty finite set of actions attaining the maximum in $T^{\ast }{v}^{\ast }(s)$. By [F9] and the finiteness of $S$, choose one member of each $B_s$ without AC; these choices define a deterministic stationary policy ${\pi }^{\ast }$. It satisfies $T_{{\pi }^{\ast }}{v}^{\ast }=T^{\ast }{v}^{\ast }=v^{\ast }$, so step 3.1 and uniqueness imply $V^{{\pi }^{\ast }}=v^{\ast }$. Together with step 3.3 this proves $v^{\ast }=V^{\ast }$ and attainment. After forcing a first action $a$ and then following ${\pi }^{\ast }$, the expected return is $r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)V^{\ast }(s^{\mathrm{\prime }})$. Any other continuation after that first action is bounded by $V^{\ast }(s^{\mathrm{\prime }})$ at each next state by step 3.3, so this is the maximal value with first action fixed to $a$, namely $Q^{\ast }(s,a)$. Its maximum over $a$ is $V^{\ast }(s)$, and it is nonnegative by [F1]. AC is used only for the path law in step 1.1.