Computing semi-stationary optimal policies for multichain semi-Markov decision processes

We consider semi-Markov decision processes with finite state and action spaces and a general multichain structure. A form of limiting ratio average (undiscounted) reward is the criterion for comparing different policies. The main result is that the value vector and a pure optimal semi-stationary policy (i.e., a policy which depends only on the initial state and the current state) for such an SMDP can be computed directly from an optimal solution of a finite set (whose cardinality equals the number of states) of linear programming (LP) problems. To be more precise, we prove that the single LP associated with a fixed initial state provides the value and an optimal pure stationary policy of the corresponding SMDP. The relation between the set of feasible solutions of each LP and the set of stationary policies is also analyzed. Examples are worked out to describe the algorithm.

1. For simplicity of notations, we shall denote by \([V]_i\) the i-th component of the vector V; the j-th row and the k-th column of the matrix A are denoted by \(A_{j\cdot }\) and \(A_{\cdot k}\) respectively.

I am grateful to Prof. T. Parthasarathy of CMI & ISI Chennai. Some ideas presented in this paper results from a fruitful discussion with him during the International Conference & Workshop on “Game Theory and Optimization”, June 6-10, 2016 at IIT Madras. This paper is dedicated to celebrate the 75th birthday of Prof. T. Parthasarathy, who has made significant contributions to the theory of games and linear complementarity problems. I am also thankful to Prof. S. Sinha of Jadavpur University, Kolkata for many valuable suggestions. I would like to thank the two anonymous Referees for their valuable and detailed comments that has helped structure this paper better.

Authors and Affiliations

1. Mathematics Department, Government General Degree College, Ranibandh, Bankura, 722135, India

   Prasenjit Mondal

Corresponding author

Correspondence to Prasenjit Mondal.

Appendix (Proof of Theorem 1)

We use the following simple lemma to prove Theorem 1.

Lemma 11

Let \(\{a_n\}\) be a bounded sequence in \(\mathbf {R}^m\) and \(f: \mathbf {R}^m\rightarrow \mathbf {R}\) be a continuous function, then

Proof of Theorem 1

Let \(|S|=z\). For simplicity, we assume that \(|A(s)|=|A|=k\)\(\forall ~s\in S\). Let \({s_0}\in S\) be a fixed initial state. We prove that if the SMDP starts at \({s_0}\), there exists a pure stationary policy \(f^{s_0}\in \mathscr {F}^\mathscr {P}\) such that \(\phi ({s_0},f^{s_0})\ge \phi ({s_0},\pi )\) for all \(\pi \in \varPi \). This result will prove the theorem because if \(\{f^{s_0}\mid {s_0}\in S\}\) are as above, then the semi-stationary policy \(\xi ^*=(f^1,f^2,\ldots ,f^z)\) is optimal in the SMDP.

For every \(\pi \in \varPi \), consider the zk component vectors

Note that \(x_{ns'a}\) represents the average of the probabilities that the decision maker visits to a given state \(s'\) and chooses a given action \(a\in A(s')\) in m-step (\(m=0,1,2,\ldots ,n\)) when the system starts at a fixed state \(s_0\).

Let \(H^{\pi }({s_0})\) be the set of limit points of \(\{\psi _n^\pi ({s_0})\}\) as \(n\rightarrow \infty \). If \(\pi \in \mathscr {F}\), we denote \(\psi ^{\pi }({s_0})=\lim \limits _{n\rightarrow \infty }\psi _n^\pi ({s_0})\) (which exists by Lemma 1(a)). Let \(H({s_0})=\bigcup _{\pi \in \varPi }H^{\pi }({s_0})\), \(H'({s_0})=\bigcup _{\pi \in \mathscr {F}}H^{\pi }({s_0})\) and \(H''({s_0})=\bigcup _{\pi \in \mathscr {F}^{\mathscr {P}}}H^{\pi }({s_0})\) and let \(\bar{H}'({s_0})\) and \(\bar{H}''({s_0})\) denote the closure of the convex hulls of \(H'({s_0})\) and \(H''({s_0})\) respectively. If the decision maker in the SMDP uses \(\pi \in \varPi \) with initial state \({s_0}\in S\), then from (1) we have

where r and \(\tau \) are respectively the immediate reward and the mean sojourn time vectors of order zk and they are in conformity with \(\psi _n^\pi ({s_0})\).

Define \(\varTheta (a_n)=\frac{a_n^T\cdot r}{a_n^T\cdot {\tau }} \) where \( a_n\in [0,1]^{zk}\), \(a_n^T\mathbf{{1}}=1\) (1 is a vector of order zk with all coordinates equal to 1). Then \(\{a_n\}\) is a bounded sequence and both the numerator and the denominator of \(\varTheta (a_n)\) are bounded linear functions with denominator being nonzero. Thus, \(\varTheta (a_n)\) is a continuous real valued function.

When \(a_n=\psi _n^\pi ({s_0})\), from (25) using Lemma 11, we obtain

where the equality occurs if \(\pi \in \mathscr {F}\). In Derman (1964) (p. 342, theorem 1, part (a)), it was shown that: \(H({s_0})\subset \bar{H}'({s_0})=\bar{H}''({s_0})\). By this argument, \(\liminf \limits _{n\rightarrow \infty }\psi _n^\pi ({s_0})\in H({s_0})\subset \bar{H}'({s_0})=\bar{H}''({s_0})\), thus there exist nonnegative scalars \(\lambda _1,\lambda _2,\ldots ,\lambda _d\) adding upto unity (where \(d=|\mathscr {F}^{\mathscr {P}}|=zk\) and \(\mathscr {F}^{\mathscr {P}}=\{f_1,f_2,\ldots ,f_d\}\)) such that \(\liminf \limits _{n\rightarrow \infty }\psi _n^\pi ({s_0})=\sum _{l=1}^{d}\lambda _l\psi ^{f_l}({s_0})\), where \(\psi ^{f_l}({s_0})=\lim \limits _{n\rightarrow \infty }\psi _n^{f_l}({s_0})\). Thus, for all \(\pi \in \varPi \),

The above linear fractional programming problem has an optimal solution which is an extreme point of the feasible zone \(\{\lambda _l\ge 0, \forall l=1,2,\ldots ,d; \sum \limits _{l=1}^d \lambda _l=1\}\) and hence corresponds to an optimal pure stationary policy \(f^{s_0}\) such that \(\phi ({s_0},f^{s_0})\ge \phi ({s_0},\pi )~ \forall \pi \in \varPi \). This completes the proof. \(\square \)

Reprints and permissions