Discount-isotone policies for Markov decision processes (Q1106106)

Consider a discounted Markov decision process with state space \(I\subseteq {\mathbb{Z}}^ m,\) finite action sets \(K_ i\), transition probabilities \(p=p(i,j,k)\) and non-negative, bounded rewards \(r=r(i,k)\), where \(i,j\in I\), \(k\in K_ i\). Let \(K=\cup_{i\in I}K_ i\). Suppose further that I(K) is endowed with a partial order \(\succsim^*\) \((\succsim)\). Let \(Q=\{\delta_{\rho}\), \(\rho\in [0,1)\}\) be a collection of optimal, stationary policies: one for each discount factor \(\rho\). Q is called D-isotone if \(\tau\geq \rho \Rightarrow \delta_{\tau}(i)\succsim \delta_{\rho}(i)\) for all \(i\in I\), \(\tau,\rho\in [0,1)\). Some sufficient conditions are given (in the form of generalized isotonicity and submodularity requirements on r and p) for the existence of a D-isotone set in the case when \((K,\succsim)\) is a lattice. Structural and computational applications are then illustrated.