Finite-state discounted generator Bellman system

Let $S=\{1,\dots ,n\}$ be a nonempty finite state set, let each state $i$ have a nonempty finite ordered action set $A_i$, and let $c>0$. For $a\in A_i$, choose real coefficients $q_{ij}^a$ satisfying $q_{ij}^a\ge 0(j\mathrm{\ne }i),{\sum }_{j=1}^n{q}_{ij}^a=0,$ and a reward $r_i^a\in \mathbb{R}$. The row $q_i^a$ is a conservative generator row. A deterministic policy is a map $\pi$ with $\pi (i)\in A_i$. Its policy matrix and reward vector are $A_{ij}^{\pi }=c{\delta }_{ij}-q_{ij}^{\pi (i)},r_i^{\pi }=r_i^{\pi (i)}\mathrm{.}$ The discounted finite-state Bellman system is $c{V}_i-{\max }_{a\in A_i}({\sum }_{j=1}^n{q}_{ij}^a{V}_j+r_i^a)=0,i\in S\mathrm{.}$ The policy evaluation equation for $\pi$ is $A^{\pi }V=r^{\pi }$.

Here ${\delta }_{ij}$ is $1$ when $i=j$ and $0$ otherwise.

For any $\lambda >{\max }_{i,a}(-q_{ii}^a)$, define, for each $i$ and $a\in A_i$, $p_{ij}^a={\delta }_{ij}+q_{ij}^a\mathrm{/}\lambda$. Each such row has nonnegative entries and sums to one. Substituting $q_{ij}^a=\lambda (p_{ij}^a-{\delta }_{ij})$ gives the equivalent system $V_i={\max }_{a\in A_i}(\gamma {\sum }_j{p}_{ij}^a{V}_j+\frac{r_i^a}{c+\lambda }),\gamma =\frac{\lambda }{c+\lambda }<1.$ This is a finite discrete-time discounted Bellman system with state-dependent action sets; no stochastic process representation is needed by the policy-iteration proof.