A useful technique for piecewise deterministic Markov decision processes

This note presents a technique that is useful for the study of piecewise deterministic Markov decision processes (PDMDPs) with general policies and unbounded transition intensities. This technique produces an auxiliary PDMDP from the original one. The auxiliary PDMDP possesses certain desired properties, which may not be possessed by the original PDMDP. We apply this technique to risk-sensitive PDMDPs with total cost criteria, and comment on its connection with the uniformization technique.     

Transient solutions of Markov processes and generalized continued fractions

In 1974 J. A. Murphy and M. R. O'Donohoe numerically approximatedthe minimal solution of the Kolmogorov forward equation forthe generalized birth and death process by use of continuedfractions. This paper generalizes this approach by suggestingan algorithm for q-matrices of lower band structure (n, 1).This is achieved by analogy with generalized continued fractions.Applications involving q-matrices of this type include, forexample, many types of queueing systems with batch processingor birth–death–catastrophe population processesin biology.     

Aggregation of Markov processes: Axiomatization

We give two simple axioms that characterize a simple functional form for aggregation of column stochastic matrices (i.e., Markov processes). Several additional observations are made about such aggregation, including the special case in which the aggregated process is Markovian relative to the original one.     

Densities for infinitely divisible random processes

Let {ξ_j(t), t ∈ [0, T]} j = 1, 2 be infinitely divisible processes with distinct Poisson components and no Gaussian components. Let X be the set of all real-valued functions on [0, T] which are not identically zero, and $\text{B}$ be the σ-ring generated by the cylinder sets of ξ_j(t), j = 1, 2. Let μ_j be the measure on $\text{B}$ induced by ξ_j(t).Necessary and sufficient conditions on the projective limits of the Levy-Khinchine spectral measures of the processes are found to make μ₂ ? μ₁, and a representation for the density $\text{dμ}{}_2\text{dμ}{}_1$ is obtained.     

Substochastic semigroups and densities of piecewise deterministic Markov processes

Necessary and sufficient conditions are given for a substochastic semigroup on L¹ obtained through the Kato-Voigt perturbation theorem to be either stochastic or strongly stable. We show how such semigroups are related to piecewise deterministic Markov process, provide a probabilistic interpretation of our results, and apply them to fragmentation equations.     

Monotonicity in multidimensional Markov decision processes for the batch dispatch problem

Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in deriving appropriate approximation techniques. We concentrate on a class of multidimensional Markov decision processes and derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct batch dispatch (MBD) problem.     

A homotopy approach for infinite horizon discounted Markov decision processes

In this paper we consider a homotopy deformation approach to solving Markov decision process problems by the continuous deformation of a simpler Markov decision process problem until it is identical with the original problem. Algorithms and performance bounds are given.     

Non-randomized policies for constrained Markov decision processes

This paper addresses constrained Markov decision processes, with expected discounted total cost criteria, which are controlled by non-randomized policies. A dynamic programming approach is used to construct optimal policies. The convergence of the series of finite horizon value functions to the infinite horizon value function is also shown. A simple example illustrating an application is presented.     

Markov chains in random environments and random iterated function systems

We consider random iterated function systems giving rise to Markov chains in random (stationary) environments. Conditions ensuring unique ergodicity and a ``pure type' characterization of the limiting ``randomly invariant' probability measure are provided. We also give a dimension formula and an algorithm for simulating exact samples from the limiting probability measure.

     

The Heckman–Opdam Markov processes

We introduce and study the natural counterpart of the Dunkl Markov processes in a negatively curved setting. We give a semimartingale decomposition of the radial part, and some properties of the jumps. We prove also a law of large numbers, a central limit theorem, and the convergence of the normalized process to the Dunkl process. Eventually we describe the asymptotic behavior of the infinite loop as it was done by Anker, Bougerol and Jeulin in the symmetric spaces setting in (Iberoamericana 18: 41–97, 2002). Partially supported by the European Commission (IHP Network HARP 2002–2006).     

Optimal filters for a hidden Markov random field model

A Markov random field (MRF) is a useful technical tool for modeling dynamics systems exhibiting some type of spatio-temporal variability. In this paper, we propose optimal filters for the states of a partially observed temporal Markov random field. We also discuss parameters estimation. This generalizes an earlier work by Elliott and Aggoun [1].     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

Harmonic moments of branching processes in random environments

We consider harmonic moments of branching processes in general random environments. For a sequence of square integrable random variables, we give some conditions such that there is a positive constant c that every variable in this sequence belong to Ac or A1c uniformly.     

Revised simplex algorithm for finite Markov decision processes

We introduce a revised simplex algorithm for solving a typical type of dynamic programming equation arising from a class of finite Markov decision processes. The algorithm also applies to several types of optimal control problems with diffusion models after discretization. It is based on the regular simplex algorithm, the duality concept in linear programming, and certain special features of the dynamic programming equation itself. Convergence is established for the new algorithm. The algorithm has favorable potential applicability when the number of actions is very large or even infinite.     

Regenerative structure of Markov chains simulated via common random numbers

A standard strategy in simulation, for comparing two stochastic systems, is to use a common sequence of random numbers to drive both systems. Since regenerative output analysis of the steady-state of a system requires that the process be regenerative, it is of interest to derive conditions under which the method of common random numbers yields a regenerative process. It is shown here that if the stochastic systems are positive recurrent Markov chains with countable state space, then the coupled system is necessarily regenerative; in fact, we allow couplings more general than those induced by common random numbers. An example is given which shows that the regenerative property can fail to hold in general state space, even if the individual systems are regenerative.     

Optimal control of one dimensional non-conservative quasi-diffusion processes

An extension of the work of P. Mandl concerning the optimal control of time-homogeneous diffusion processes in one dimension is given. Instead of a classical second order differential operator as infinitesimal generator, Feller's generalized differential operator D_mD⁺_p with a possibly nondecreasing weight function m is used. In this manner an optimal control of a wider class of one dimensional Marcov processes-including diffusions as well as birth and death processes-is realized.     

Markov decision processes with multidimensional action spaces

We study controlled Markov processes where multiple decisions need to be made for each state. We present conditions on the cost structure and the state transition mechanism of the process under which optimal decisions are restricted to a subset of the decision space. As a result, the numerical computation of the optimal policy may be significantly expedited.     

Weighted discounted Markov decision processes with perturbation

1.IntrodnctionTheweightedMarkovdecisionprocesses(MDP's)havebeenextensivelystudiedsince1980's,seeforinstance,[1-6]andsoon.ThetheoryofweightedMDP'swithperturbedtransitionprobabilitiesappearstohavebeenmentionedonlyin[7].Thispaperwilldiscussthemodelsofwe...     

On some algorithms for limiting average Markov decision processes

We consider limiting average Markov decision processes (MDP) with finite state and action spaces. We propose some algorithms to determine optimal strategies for deterministic and general MDPs. These algorithms are based on graph theory and the construction of levels in some aggregated MDP.