Search

Recent research indicates that Markov decision processes (MDPs) and perturbation analysis (PA) based optimization can be derived easily from two fundamental performance sensitivity formulas. With this sensitivity point of view, an event-based optimization approach, including event-based sensitivity analysis and event-based policy iteration, was proposed via an example by X. R. Cao (Discrete Event Dyn. Syst.: Theory Appl., vol. 15, pp. 169-197, 2005). This approach utilizes the special feature of a system and illustrates how the potentials can be aggregated using the special feature. The approach applies to many practical problems that do not fit well the standard MDP formulation. This note provides a mathematical formulation and proves the main results for this approach. Index Terms--Markov decision processes (MDPs), performance potentials, perturbation analysis (PA), policy gradients, policy iteration.

In this paper, we propose a new approach to the theory of finite multichain Markov decision processes (MDPs) with different performance optimization criteria. We first propose the concept of nth-order bias; then, using the average reward and bias difference formulas derived in this paper, we develop an optimization theory for finite MDPs that covers a complete spectrum from average optimality, bias optimality, to all high-order bias optimality, in a unified way. The approach is simple, direct, natural, and intuitive; it depends neither on Laurent series expansion nor on discounted MDPs. We also propose one-phase policy iteration algorithms for bias and high-order bias optimal policies, which are more efficient than the two-phase algorithms in the literature. Furthermore, we derive high-order bias optimality equations. This research is a part of our effort in developing sensitivity-based learning and optimization theory. Index Terms--Average optimality, bias optimality, discrete-event systems, Markov decision processes (MDPs), nth-bias optimality, nth potentials, policy iteration.

In a partially observable Markov decision process (POMDP), if the reward can be observed at each step, then the observed reward history contains information on the unknown state. This information, in addition to the information contained in the observation history, can be used to update the state probability distribution. The policy thus obtained is called a reward-information policy (RI-policy); an optimal RI-policy performs no worse than any normal optimal policy depending only on the observation history. The above observation leads to four different problem-formulations for POMDPs depending on whether the reward function is known and whether the reward at each step is observable. This exploratory work may attract attention to these interesting problems. Index Terms--Partially observable Markov decision process (POMDP), reward-information policy. Digital Object Identifier 10.1109/TAC.2007.894520

Perturbation realization factor is an important concept in perturbation analysis of both queueing systems and Markov systems. A perturbation realization factor measures the effect of a perturbation on the system performance. This concept is important for the performance sensitivity and performance optimization of these systems. Since the perturbations in queueing systems are continuous in nature and those in Markov systems are discrete, it is not straightforward to establish the relationship between these two types of fundamental concepts. This note solves this longstanding problem. We find a formula that links these two types of perturbation realization factors in Gordon-Newell and open Jackson networks together. The results enhance our understanding of perturbation analysis and lead to new research directions. Index Terms--Markov decision processes (MDPs), performance potential, perturbation analysis (PA), perturbation realization factor, queueing systems.

This note presents a (new) basic formula for sample-path-based estimates for performance gradients for Markov systems (called policy gradients in reinforcement learning literature). With this basic formula, many policy-gradient algorithms, including those that have previously appeared in the literature, can be easily developed. The formula follows naturally from a sensitivity equation in perturbation analysis. New research direction is discussed. Index Terms--Markov decision processes, online estimation, perturbation analysis (PA), perturbation realization, Poisson equations, potentials, reinforcement learning.

We study the structure of sample paths of Markov systems by using performance potentials as the fundamental units. With a sample path-based approach, we show that performance sensitivity formulas (performance gradients and performance differences) of Markov systems can be constructed intuitively, by first principles, with performance potentials (or equivalently, perturbation realization factors) as building blocks. In particular, we derive sensitivity formulas for two Markov chains with possibly different state spaces. The proposed approach can be used to obtain flexibly the sensitivity formulas for a wide range of problems, including those with partial information. These formulas are the basis for performance optimization of discrete event dynamic systems, including perturbation analysis, Markov decision processes, and reinforcement learning. The approach thus provides insight on on-line learning and performance optimization and opens up new research directions. Sample path based algorithms can be developed. Index Terms--Markov decision processes, performance sensitivity, perturbation analysis, perturbation realization, reinforcement learning.

Performance potentials play a crucial role in performance sensitivity analysis and policy iteration of Markov decision processes. The potentials can be estimated on a single sample path of a Markov process. In this paper, we propose two potential-based online policy iteration algorithms for performance optimization of Markov systems. The algorithms are based on online estimation of potentials and stochastic approximation. We prove that with these two algorithms the optimal policy can be attained after a finite number of iterations. A simulation example is given to illustrate the main ideas and the convergence rates of the algorithms. Index Terms--Markov decision process, potential, recursive optimization.

Recent research indicates that Markov decision processes (MDPs) can be viewed from a sensitivity point of view; and perturbation analysis (PA), MDPs, and reinforcement learning (RL) are three closely related areas in optimization of discrete-event dynamic systems that can be modeled as Markov processes. The goal of this paper is two-fold. First, we develop PA theory for semi-Markov processes (SMPs); and second, we extend the aforementioned results about the relation among PA, MDP, and RL to SMPs. In particular, we show that performance sensitivity formulas and policy iteration algorithms of semi-Markov decision processes (SMDPs) can be derived based on performance potential and realization matrix. Both the long-run average and discounted-cost problems are considered; this approach provides a unified framework for both problems, and the long-run average problem corresponds to the discounted factor being zero. The results indicate that performance sensitivities and optimization depend only on first-order statistics. Single sample path-based implementations are discussed. Index Terms--Discounted Poisson equations, discrete-event dynamic systems (DEDS), Lyapunov equations, Markov decision processes (MDPs), perturbation analysis (PA), perturbation realization, Poisson equations, policy iteration, potentials, reinforcement learning (RL).

This note studies the relationship between two important approaches in perturbation analysis (PA)--perturbation realization (PR) and weak derivatives (WDs). Specifically, we study the relation between PR and WDs for estimating the gradient of stationary performance measures of a finite state-space Markov chain. Will show that the WDs expression for the gradient of a stationary performance measure can be interpreted as the expected PR factor where the expectation is carried out with respect to a distribution that is given through the weak derivative of the transition kernel of the Markov chain. Moreover, we present unbiased gradient estimators. Index Terms--Markov chains, perturbation analysis (PA), weak derivatives (WDs).

Two fundamental concepts and quantities, realization factors and performance potentials, are introduced for Markov processes. The relations among these two quantities and the group inverse of the infinitesimal generator are studied. It is shown that the sensitivity of the steady-state performance with respect to the change of the infinitesimal generator can be easily calculated by using either of these three quantities and that these quantities can be estimated by analyzing a single sample path of a Markov process. Based on these results, algorithms for estimating performance sensitivities on a single sample path of a Markov process can be proposed. The potentials in this paper are defined through realization factors and are shown to be the same as those defined by Poisson equations. The results provide a uniform framework of perturbation realization for infinitesimal perturbation analysis (IPA) and non-IPA approaches to the sensitivity analysis of steady-state performance; they also provide a theoretical background for the PA algorithms developed in recent years. Index Terms - Perturbation analysis, Poisson equations, sample-path analysis.

The key issue for adaptive pole-placement control of linear time-invariant systems is the possible singularity of the Sylvester matrix corresponding to the coefficient estimate. However, to overcome the difficulty, the estimate is modified by several methods which are either nonrecursive and with high computational load or recursive but with random search involved. All of the previous works are done under the assumption that the system is controllable. This paper gives the necessary and sufficient condition, which is weaker than controllability, for the system to be adaptively stabilizable. First, a nonrecursive algorithm is proposed to modify the estimates, and the algorithm is proved to terminate in finitely many steps. Then, with the help of stochastic approximation, a recursive algorithm is proposed for obtaining the modification parameters; it is proved that these modification parameters turn out to be a constant vector in a finite number of steps. This leads to the convergence of the modified coefficient estimates. For both algorithms the Sylvester matrices corresponding to the modified coefficient estimates are asymptotically uniformly nonsingular; thus, the adaptive pole-placement control problem can be solved, i.e., the system can be adaptively stabilized. Index Terms - Adaptive pole-placement control, controllability, parameter modification, stochastic approximation.

Using a sample path approach, we derive a new formula for performance sensitivities of discrete-time Markov chains. A distinguished feature of this formula is that the quantities involved can be estimated by analyzing a single sample path of a Markov chain. Thus, the formula provides a new direction for sensitivity analysis and can be viewed as an extension of the perturbation realization theory to problems where infinitesimal perturbation analysis does not work well.

In this note, we consider a problem of decentralized control of service rates in a closed Jackson network under the long-run time-average expected cost criterion. We use a direct approach to solving the problem. The approach is based on an intrinsic property of the product-form solution: If the cost function is an affine function of a service rate, then the long-run average expected cost is always monotone in that service rate. This intrinsic property leads immediately to the optimality of bang-bang or threshold policies. The result extends the existing result in [5], obtained by linear programming, to more general cost functions.