Bounds on the fixed point of a monotone contraction operator (Q579144): Difference between revisions

This paper considers the solution to the following fixed point equation governing infinite horizon Markovian decision processes: \[ x^*_ i=\max_{k\in A(i)}[a^ k_ i+\sum^{N}_{t=1}M^ k_{it}x^*_ t]=f(x^*)_ i,\quad 1\leq i\leq N. \] The generally imposed condition is that \(\rho ([M_{ij}^{k(i)}])<1\), for all the possible probability transition matrices obtainable for any stationary pure Markov decision rule, and \(\rho\) is the spectral radius of the probability transition matrix. The main results are in Theorem 1. These results include the following: (i) The set \[ Y=\{y\in E^ N: y_ i>\sum^{N}_{t=1}M^ k_{it}y_ t,\quad \forall \quad k\in A(i),\quad 1\leq i\leq N\} \] is nonempty, and \(y>0\), \(\forall\) \(y\in Y\). (ii) f is a contraction mapping with modulus \(\lambda\) (y) for each norm \(\| u\|_ y\equiv \max_{1\leq i\leq N}[| u_ i| /y_ i]\), where \[ \lambda (y)\equiv \max_{i,k}[\Sigma_ tM^ k_{it}\quad y_ t/y_ i]<1. \] (iii) If \(x\in E^ N\), \(y\in Y\), then: \[ ^ y_ i\min_{1\leq j\leq N}\max_{k\in A(j)}\frac{P(j,k)}{Q(j,k)}\leq x^*_ i-x_ i\leq y_ i\max_{1\leq j\leq N}\max_{k\in A(j)}\frac{P(j,k)}{Q(j,k)},\quad where \] \[ P(j,k)=a^ k_ j+\sum^{N}_{t=1}M^ k_{jt}x_ t-x_ j\quad and\quad Q(j,k)=y_ j-\sum^{N}_{t=1}M_{jt}y_ t. \] The paper also introduces subgradient ideas. Thus y is a subgradient for f, if there exist numbers \(\{c_{ti}\}\), \(0\leq c_{ti}<1\), for all t, i, such that for all w, \(z\in E^ N\) \[ f(w+z)_ i\leq f(w)_ i+c_{ti}y_ i\max_{1\leq k\leq N}[z_ k/y_ k],\quad 1\leq i\leq N \] where \(t=1\) if \(\max_{k}[z_ k]\geq 0\), \(t=2\) if \(\max [z_ k]<0\). The paper then shows that if \(x\in E^ N\) \(y_ i\min_{1\leq j\leq N}\min_{t=1,2}\frac{R(j,t)}{S(j,t)}\leq x^*_ i-x_ i\leq y_ i\max_{1\leq j\leq N}\max_{t=1,2}\frac{R(j,t)}{S(j,t)},\) where \[ R(j,t)=f(x_ j)-x_ j\quad and\quad S(j,t)=y_ j(1-c_{tj}). \] Special cases of \(\{c_{tj}\}\) exist in terms of \(y\in Y\). The remainder of the paper gives some specializations, additional properties, some consideration of semi-Markov decision processes, and nonsymmetric bounds.