Continuous time Discounted Jump Markov Decision Processes a Discreteevent Approach

• Access throughyour institution

Stochastics and Statistics

Convergence of controlled models and finite-state approximation for discounted continuous-time Markov decision processes with constraints

Abstract

In this paper we consider the convergence of a sequence $\{{\mathcal{M}}_n\}$ of the models of discounted continuous-time constrained Markov decision processes (MDP) to the "limit" one, denoted by ${\mathcal{M}}_{\infty }$ . For the models with denumerable states and unbounded transition rates, under reasonably mild conditions we prove that the (constrained) optimal policies and the optimal values of $\{{\mathcal{M}}_n\}$ converge to those of ${\mathcal{M}}_{\infty }$ , respectively, using a technique of occupation measures. As an application of the convergence result developed here, we show that an optimal policy and the optimal value for countable-state continuous-time MDP can be approximated by those of finite-state continuous-time MDP. Finally, we further illustrate such finite-state approximation by solving numerically a controlled birth-and-death system and also give the corresponding error bound of the approximation.

Introduction

Constrained Markov decision processes (MDP) form an important class of stochastic control problems with applications in many areas such as telecommunication networks and queueing systems; see, for instance, Guo and Hernández-Lerma, 2009, Hordijk and Spieksma, 1989, Sennott, 1991. As is well known, the main purpose of studies on constrained MDP is on the existence and computation of optimal policies, see, for instance, the literature on the discrete-time MDP by Feinberg and Shwartz, 1999, Feinberg, 2000, Hordijk and Spieksma, 1989, Hernández-Lerma and González-Hernández, 2000, Hernández-Lerma et al., 2003, Sennott, 1991, and the works on continuous-time MDP by Guo, 2007, Guo and Hernández-Lerma, 2003, Guo and Hernández-Lerma, 2009, Guo and Piunovskiy, 2011. On the other hand, from a theoretical and practical point of view, it is of interest to analyze the convergence of optimal values and optimal policies for constrained MDP, and such convergence problems have been considered, see, for instance, Altman, 1999, Zadorojniy and Shwartz, 2006, Alvarez-Mena and Hernández-Lerma, 2002 and so on. Alvarez-Mena and Hernández-Lerma (2006) also consider the convergence problem as in Alvarez-Mena and Hernández-Lerma (2002) for the case of more than one controller. To the best of our knowledge, however, these existing works for the convergence problems are on the constrained discrete-time MDP. Most recently, the convergence problem of controlled models for unconstrained continuous-time MDP has also been considered by Prieto-Rumeau and Lorenzo, 2010, Prieto-Rumeau and Hernández-Lerma, 2012 using an approximation of the optimality equations. However, the similar convergence problem for constrained continuous-time MDP has not been considered.

This paper studies the convergence problem for constrained continuous-time MDP. More precisely, in this paper we consider a sequence $\{{\mathcal{M}}_n\}$ of the models of the constrained continuous-time MDP with the following features: (1) the state space is denumerable, but action space is general; (2) the transition rates and all reward/cost functions are allowed to be unbounded; and (3) the optimality criterion is the expected discounted reward/cost, while some constraints are imposed on similar discounted rewards/costs. We aim to give suitable conditions imposed on the models $\{{\mathcal{M}}_n\}$ , under which the optimal policies and the optimal values of $\{{\mathcal{M}}_n\}$ converge to those of the limit model ${\mathcal{M}}_{\infty }$ of the sequence $\{{\mathcal{M}}_n\}$ , respectively.

In general, the approaches to study continuous-time MDP can be roughly classified into two groups: the indirect method and the direct method. For the indirect method, the idea is to convert the continuous-time MDP into equivalent discrete-time MDP. This approach has been justified by Feinberg, 2004, Feinberg, 2012, and Piunovskiy and Zhang (2012). On the other hand, the most common direct method to investigate constrained continuous-time MDP is to establish an equivalent linear program formulation of the original constrained problem, see Guo and Piunovskiy (2011). In this paper, we follow this direct approach without involving discrete-time MDP. First, as in Guo and Piunovskiy (2011), we transform the optimality problem in constrained continuous-time MDP into an equivalent optimality problem over a class of some probability measures by introducing an occupation measure of a policy. Then, we analyze the asymptotic characterization of the occupation measure and the expected discounted rewards/costs, which are used to prove that the optimal values and optimal policies of the sequence $\{{\mathcal{M}}_n\}$ converge to those of ${\mathcal{M}}_{\infty }$ . Finally, we apply our results to the approximations of the optimal policies and the optimal value of finite-state continuous-time MDP to those of countable-state continuous-time MDP. More precisely, for a model ${\mathcal{M}}_{\infty }^{\prime }$ of constrained countable-state continuous-time MDP satisfying the usual conditions as in Guo and Hernández-Lerma, 2009, Guo and Piunovskiy, 2011, we can construct a sequence of models $\{{\mathcal{M}}_n^{\prime }\}$ of constrained continuous-time MDP with finite states such that every accumulation point of a sequence of optimal policies of $\left\{{\mathcal{M}}_n^{\prime }\right\}$ is optimal for ${\mathcal{M}}_{\infty }^{\prime }$ and that the sequence of the optimal values of $\left\{{\mathcal{M}}_n^{\prime }\right\}$ converge to the optimal value of ${\mathcal{M}}_{\infty }^{\prime }$ . Furthermore, we further illustrate such finite-state approximation by solving numerically a controlled birth-and-death system, and also give the corresponding error bound of the approximation. The motivation of providing such approximation is from the following facts: (i) there exist many methods to solve the optimal value and optimal policies for unconstrained continuous-time MDP with finite sates, for example, the value iteration algorithm and the policy iteration algorithm by Guo and Hernández-Lerma, 2009, Puterman, 1994, the approximation dynamic programming technique by Cervellera and Macciò (2011), and so on. However, these methods, which are all based on the optimality equation, are not applied to constrained continuous-time MDP since the optimality equation no longer exists for the constrained MDP; (ii) the optimal value and optimal policies for finite-state constrained continuous-time MDP with finite actions can be computed by the well known linear programming in Guo and Piunovskiy, 2011, Puterman, 1994, whereas in general the optimal value and optimal policies cannot be computed for countable-state continuous-time MDP because the number of states in such MDP is infinite.

The rest of this paper is organized as follows. In Section 2, we introduce the models of constrained continuous-time MDP and the convergence problems. In Section 3, we state our main results, which are proved in Section 6, after technical preliminaries given in Section 5. An application of the main results to finite state approximation and a numerable example are given in Section 4. Finally, we finish this article with a conclusion in Section 7.

Section snippets

The models

In this section we introduce the models and convergence problems we are concerned with.

Notation. If X is a Polish space, we denote by $\mathcal{B}(X)$ its Borel $\sigma$ -algebra, by $D^c$ the complement of a set $D\subseteq X$ (with respect to X), by $\mathcal{P}(X)$ the set of all probability measures on $\mathcal{B}(X)$ , endowed with the topology of weak convergence. For a finite set D, we denote by $|D|$ the number of its elements. Let $\mathbb{N}≔\{1\text{,}2\text{,}\dots \}$ and $\bar{\mathbb{N}}≔\mathbb{N}\bigcup \{\infty \}$ .

Consider the sequence of models $\{{\mathcal{M}}_n\}$ for constrained continuous-time MDP: ${\mathcal{M}}_n≔\left\{S_n\text{,}(A_n(i)\text{,}i\in S_n)\text{,}{q}_{}\right\}$

The main results

In this section, we state our main results. Their proofs are postponed to Section 6 below.

First, for the existence of an optimal policy ${\pi }_n^{\ast }$ of ${\mathcal{M}}_n$ , we need the following conditions:

Assumption 3.1

(a)

For each $n\in \bar{\mathbb{N}}$ and $i\in S_n\text{,}{A}_n(i)$ is compact.

(b)

The discount factor $\alpha$ satisfies that $\alpha >\rho$ , with $\rho$ as in Assumption 2.1.

(c)

${\sup }_{n\in \bar{\mathbb{N}}}\left\{{\sum }_{i\in S_n}{\omega }^2(i){\gamma }_n(i)\right\}<\infty$ , and ${\sum }_{j\in S_n}{q}_n(j|i\text{,}a){\omega }^2(j)⩽{\kappa }_1{\omega }^2(i)+{\kappa }_2$ for all $n\in \bar{\mathbb{N}}$ and $(i\text{,}a)\in K_n$ , with some constants $0<{\kappa }_1<\alpha$ and $0⩽{\kappa }_2$ .

(d)

$|c_n^l(i\text{,}a)|⩽M\omega (i)$ for all $(i\text{,}a)\in K_n\text{,}0⩽l⩽p$ and $n\in \bar{\mathbb{N}}$ , with some constant $M>0$ .

(e)

The

Applications

In this section, we apply Theorem 3.1 to a finite-state approximation in Section 4.1, that is, we will show that an optimal policy and the optimal value for a countable-state constrained continuous-time MDP can be approximated by those of solvable finite-state continuous-time MDP. Furthermore, we illustrate such approximation by a controlled birth-and-death system in Section 4.2.

Occupation measures and preliminary results

In order to prove Theorem 3.1 above, we introduce the concept of an occupation measure.

Definition 5.1

For each $n\in \bar{\mathbb{N}}$ and policy $\pi \in {\Pi }_n$ , the occupation measure of $\pi$ associated to ${\mathcal{M}}_n$ is a p.m. on $S_n\times A_n$ , denoted by ${\eta }_n^{\pi }$ , is defined by ${\eta }_n^{\pi }(\{i\}\times \Gamma )≔\alpha {\int }_0^{\infty }{e}^{-\alpha t}{E}_{{\gamma }_n}^{\pi }[I_{\{i\}\times \Gamma }(x_t\text{,}{a}_t)]\mathit{dt}\{i\}\times \Gamma \in \mathcal{B}(S_n\times A_n)\text{,}$

which is concentrated on $K_n$ .

Under Assumption 2.1, Assumption 3.1(b–d), by (2.3), (3.1), (5.1), we have $V_n^l(\pi )=\frac{1}{\alpha }{\displaystyle \sum _{j\in S_n}}{\int }_{A_n(j)}{c}_n^l(j\text{,}a){\eta }_n^{\pi }(j\text{,}\mathit{da})\text{,}\mathrm{for}0⩽l⩽p\text{,}\pi \in {\Pi }_n\text{,}n\in \bar{\mathbb{N}}\text{.}$

Then, the following theorem collects some properties of occupation

Proof of Theorem 3.1

The proof of Theorem 3.1 is based on the following proposition, which is similar to Lemma 5.1 in Alvarez-Mena and Hernández-Lerma (2002) for discrete-time MDP. We will prove it here for the sake of completeness.

Proposition 6.1

Under Assumption 2.1, Assumption 3.1, Assumption 3.2, Assumption 3.3, the following assertions hold.

(i)

For each $\eta \in {\mathbf{F}}_{\infty }$ , there exist an integer N and ${\eta }_n\in {\mathbf{F}}_n$ for each $n⩾N$ , such that ${\eta }_n\to \eta$ weakly.

(ii)

There exists an integer N such that ${\mathbf{F}}_n$ for each $n⩾N$ . If ${\eta }_n\in {\mathbf{O}}_n$ for all $n⩾1$ , and ${\eta }_{\infty }$ is an accumulation

Conclusion

The convergence problems for the two sequences of optimal policies and the optimal values of the models $\{{\mathcal{M}}_n\}$ of discounted continuous-time MDP with unbounded transition rates and multiple-objective constraints, are studied in this paper. Suitable conditions for the convergence of the optimal values and optimal policies of $\{{\mathcal{M}}_n\}$ to those of the so-called "limit" model of $\{{\mathcal{M}}_n\}$ are given. The main technique in this paper are based on the asymptotic properties of occupation measures of policies,

Acknowledgements

This research was partially supported by the NSFC and GDUPS. We also thank the anonymous referees for constructive comments.

References (24)

• et al.

  A comparison of global and semi-local approximation in T-stage stochastic optimization

  European Journal of Operational Research

  (2011)

• E. Altman

  Constrained Markov decision processes

  (1999)

• J. Alvarez-Mena et al.

  Convergence of the optimal values of constrained Markov control processes

  Mathematical Methods of Operations Research

  (2002)

• J. Alvarez-Mena et al.

  Existence of Nash equilibria for constrained stochastic games

  Mathematical Methods of Operations Research

  (2006)

• W.J. Anderson

  Continuous-time Markov chains

  (1991)

• E.A. Feinberg

  Constrained discounted Markov decision processes and Hamiltonian cycles

  Mathematics of Operations Research

  (2000)

• E.A. Feinberg

  Continuous time discounted jump Markov decision processes: A discrete-event approach

  Mathematics of Operations Research

  (2004)

• E.A. Feinberg

  Reduction of discounted continuous-time MDPs with unbounded jump and reward rates to discrete-time total-reward MDPs

  Control

  (2012)

• E.A. Feinberg et al.

  Constrained dynamic programming with two discount factors: Applications and an algorithm

  Institute of Electrical and Electronics Engineers. Transactions on Automatic Control

  (1999)

• X.P. Guo

  Constrained optimization for average cost continuous-time Markov decision processes

  Institute of Electrical and Electronics Engineers. Transactions on Automatic Control

  (2007)

X.P. Guo et al.

Constrained continuous-time Markov control processes with discounted criteria

Stochastic Analysis and Applications

(2003)

X.P. Guo et al.

Continuous-time Markov decision processes

(2009)

Cited by (17)

Recommended articles (6)

View full text

Copyright © 2014 Elsevier B.V. All rights reserved.

peraltaalke1982.blogspot.com

Source: https://www.sciencedirect.com/science/article/abs/pii/S0377221714002768

Share this post