Controlled Markov Fields with Finite State Space on Graphs
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.
- Controlled semi-Markov fields with graph-structured compact state space
- Local control of Markovian processes of interaction on a graph with a compact set of states
- A problem of control of Markovian processes on a graph
- scientific article; zbMATH DE number 1424150
- Controlled semi-Markovian fields on a graph
- Discrete time tandem networks of queues
- Finite state Markovian decision processes
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 3858110 (Why is no real title available?)
- scientific article; zbMATH DE number 4088693 (Why is no real title available?)
- scientific article; zbMATH DE number 3892344 (Why is no real title available?)
- Simultaneity in discrete-time single server queues with Bernoulli inputs
- A problem of control of Markovian processes on a graph
- Local control of Markovian processes of interaction on a graph with a compact set of states
- Controlled semi-Markovian fields on a graph
- A model of infectious disease spread with hidden carriers
- Phase transitions for controlled Markov chains on infinite graphs
- scientific article; zbMATH DE number 4070787 (Why is no real title available?)
- Controlled Random Fields on an Oriented Graph
- On Markov stochastic processes with local interaction for solving some applied problems
- Controlled Markov Chains, Graphs, and Hamiltonicity
- Controlled semi-Markov fields with graph-structured compact state space
- Mathematical modeling of distributed catastrophic and terrorist risks
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)