Controlled Markov Fields with Finite State Space on Graphs

From MaRDI portal





The following problem is considered. Let \(\Gamma=(V,B)\) be a finite undirected graph with set of vertices \(V\) and set of edges \(B\). The neighborhood of vertex \(k\) is the set \(N(k)=\{j: (k,j) \in V\} \cup \{k\}\). Let vectors \(\xi^t=(\xi_k^t, k \in V)\) and \(\xi_K^t=(\xi_k^t, k \in K)\) denote the random field on the graph at time instant \(t=0,1,2,\dots\) and its marginal description on some \(K \subseteq V\), respectively. Transition probabilities of the considered Markov field depend only on the local information, i.e. \[ P\{\xi_k^{t+1}=x_k^{t+1}\mid \xi^{t}=x^{t},\dots,\xi^{0}=x^{0}\}= P\{\xi_k^{t+1}=x_k^{t+1}\mid \xi_{N(k)}^{t}=x_{N(k)}^{t}\}, \] and are synchronous, i.e. \[ P\{\xi_K^{t+1}=x_K^{t+1} \mid \xi^{t}=x^{t}\}= \prod_{k \in K} P\{\xi_k^{t+1}=x_k^{t+1}\mid \xi_{N(k)}^{t}=x_{N(k)}^{t}\}. \] This definition is generalized to the case of controlled Markov field with finite sets of actions \(U_i\) at each vertex \(i\). It is assumed that at any time \(t=0,1,2,\dots\) the decision \(\Delta_i^t\) for vertex \(i\) is made on the basis of \(x_{N(i)}^0,\dots,x_{N(i)}^t\) only, the sequence \(\Delta_i^t(x_{N(i)}^0,\dots,x_{N(i)}^t)\) is called local strategy for vertex \(i\). Then it is assumed that the control of the time dependent random field \(\xi\) is governed via modified transition probabilities \[ P\{\xi^{t+1}=x^{t+1} \mid \xi^{t}=y, \{(\Delta_i^t(x_{N(i)}^0,\dots,x_{N(i)}^t)):i\in V \}=u\}. \] If at the time \(t\) the system is in the state \(\xi^t=x^t\) and a decision for action \(u^t\) is made, a one-step cost \(r(x^t,u^t)\geq 0\) is incurred in the system. The goal is to minimize the asymptotic average expected costs. It is proved that in the class of local strategies there exist deterministic strategies which achieve minimal asymptotic average expected costs. If the cost structure is separable, these strategies are even globally optimal. A computational example concerning cyclic queues is considered.











This page was built for publication: Controlled Markov Fields with Finite State Space on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5711153)