Search

Stochastic learning and optimizatio , Stochastic learning and optimizatio , کتابخانه دیجیتال جندی شاپور اهواز

Although the two sensitivity formulas for Markov chains can be derived easily from the Poisson equation, this mathematical derivation lacks structural insights needed for deriving similar sensitivity formulas for other non-standard problems.

In Chapter 2, we introduced the basic principles of PA and derived the performance derivative formulas for queueing networks and Markov and semi-Markov systems with these principles. In Chapter 3, we developed sample-path-based (on-line learning) algorithms for estimating the performance derivatives and sample-path-based optimization schemes. In this chapter, we will show that the performance sensitivity based view leads to a unified approach to both PA and Markov decision processes (MDPs).

Adaptive control and identification theory for stochastic systems was developed in the last few decades and is now very mature. Many excellent textbooks exist, see e.g., [9, 165, 192, 193, 206]. There has been a continuing discussion of what adaptive control is. In general, the problems studied in this area involve systems whose structures and/or parameters are unknown and/or are time-varying, However, to precisely define adaptive control is not an easy job [9, 206].

In Chapter 3, we showed that potentials and performance gradients can be estimated with a sample path of a Markov chain, and the estimated potentials and gradients can be used in gradient-based performance optimization of Markov systems. In this chapter, we show that we can use sample-path-based potential estimates in policy iteration to find optimal policies. We focus on the average-reward optimality criterion and ergodic Markov chains.

Time aggregation based optimal control model is proposed in the paper, by using Lebesgue sampling technique. Time aggregation approach in MDP (Markov decision processes) theory is applied to handle the problem, then policy iteration can be implemented. Both analytical solution and sample path based optimization algorithms are given. Compared with periodic sampling based approach, Lebesgue sampling based approach can be applied to practical control systems to obtain improvement in system performance and reduction in resource utilization.

As shown in Chapter 2, performance derivatives for Markov systems depend heavily on performance potentials. In this chapter, we first discuss the numerical methods and sample-path-based algorithms for estimating performance potentials, and we then derive the sample-path-based algorithms for estimating performance derivatives. In performance optimization, the process of estimating the potentials and performance derivatives from a sample path is called learning.

Summary form only given. In many modern engineering systems, control actions are taken only when some events occur. In networking admission control, an action (accept or reject) is taken only when a new packet arrives; in power control of wireless communication where a mobile device travels among regions with different transmission environments, a decision (transmission rate) is made only when the mobile device enters a new region; in an inventory problem with delayed information, decision depends on the partially observed information which can also be viewed as events; in a flexible manufacturing system, actions (which work piece to process next) are taken only when a work piece is completed. The traditional Markov decision process (MDP) model does not fit these problems well and may unnecessarily suffer from the curse-of-dimensionality issue. Performance optimization of such problems can be solved by an event-based approach. This approach involves three main topics: 1) the formulation of events and event-based policies; 2) the sensitivity based view for performance optimization; and 3) computational savings, learning and on-line implementation. The paper presents a brief introduction to the above topics and discusses pros and cons of this new approach

Sensitivity analysis plays an important role in performance optimization of stochastic systems. It provides a unified view to different areas such as perturbation analysis, Markov decision processes, and reinforcement learning. Furthermore, with the sample path based construction of sensitivity this approach leads to some new research directions such as the event-based optimization approach (Cao, 2005). The previous results are on discrete-time Markov chains (Cao, 2004) and in this paper, we extend the sample path based construction approach to continuous-time Markov processes. The complexity involved is that in continuous-time Markov processes the transition rate also changes in addition to the changes in the transition probability matrix

This paper addresses the problem of modelling and analysing an interior node in IETF's DiffServ services model. Specifically it is concerned with the performance of the DiffServ assured forwarding service category in presence of a premium service class. In this model, the network node shares its outgoing link capacity between a premium service representing the expedited forwarding (EF) per-hop behavior, and two classes of assured service, that represent two classes of the assured forwarding (AF) per-hop behavior. It this paper, the traffic is modelled as Markov modulated fluid sources, and we focus on a system where out of profile traffic is dropped at the edge of the network thus both AF queues support only one drop precedence. Using a decomposition approach, approximations, and spectral analysis, we are able to derive upper and lower bounds on the tail of the distribution of the buffer content for both AF classes given a generalized processor sharing scheduling is used to differentiate the two classes. Such approximate analysis of the interaction between traffic classes can help to achieve a better understanding of this type of networks; enables the provision of throughput differentiation as defined by the AF PHB through the GPS scheduler while quantifying delay; and finally helps simplify greatly the design of bandwidth brokers that do not rely on long term bandwidth (over) provisioning.

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 sensitivities of Markov systems can be constructed by using performance potentials (or equivalently, perturbation realization factors) as building blocks. We propose an intuitive approach to derive, by first principles, formulas for performance derivatives and performance differences for two Markov chains. These formulas are the basis for performance optimization of discrete event dynamic systems, including perturbation analysis, Markov decision processes, and reinforcement learning.

Learning and optimization of stochastic systems is a multi-disciplinary area that attracts wide attentions from researchers in control systems, operations research and computer science. Areas such as perturbation analysis (PA), Markov decision process (MDP), and reinforcement learning (RL) share the common goal. In this paper, we offer an overview of the area of learning and optimization from a system theoretic perspective. We show how these seemly different disciplines are closely related, how one topic leads to the others, and how this perspective may lead to new research topics and new results, and how the performance sensitivity formulas can serve as the basis for learning and optimization.

One of the key issues in the next generation wireless cellular networks is to support multiple services, in which call admission control policy has to guarantee the different quality of service (QoS) requirement from diverse applications, and at the same time ensure the scarce bandwidth be utilized efficiently. In this paper, we first build upon our proposal dual threshold bandwidth reservation (DTBR) scheme to integrate more realistic, variable data traffic, and them proceed to analyze the DTBR scheme using two-dimensional Markov process. Both analysis and simulation results indicate that, by keeping target handoff voice call dropping probability, adoption of elastic data traffic model can reduce handoff voice call dropping probability and improve overall system award; by adjusting the threshold values in the DTBR, we demonstrate that it is capable of satisfying different QoS requirements for voice and data traffic while achieving the maximum utility.

One of the key challenges in the design of bandwidth allocation policies for a multi-services mobile cellular network is to guarantee the potentially different quality of service (QoS) requirement from diverse applications, while at the same to ensure that the scarce bandwidth be utilized efficiently. Complete sharing (CS) and dynamic partition (DP) schemes have been shown as viable techniques for managing the bandwidth. However, there has been no study that compares their respective performance, which is the focus of this paper. Specifically, in this paper, through both analysis and simulation, we demonstrate that both schemes can achieve comparable performance by proper manipulation of control parameters. The tradeoff is that DP scheme can more easily achieve the target QoS requirement, at the expense of over-provisioning, thus can potentially lead to less channel efficiency when comparing to a CS based scheme.

Research indicates that perturbation analysis (PA), Markov decision processes (MDP), and reinforcement learning (RL) are three closely-related areas in discrete event dynamic system optimization. In particular, it was shown that policy iteration in fact chooses the policy that has the steepest performance gradient (provided by PA) for the next iteration. This sensitivity point of view of MDP leads to some new research topics. We propose to implement policy iteration based on performance gradients. This approach is particularly useful when the actions at different states are correlated and hence the standard policy iteration cannot apply. We illustrate the main ideas with an example of an M/G/1/N queue and identify some further research topics.

Link layer error control is one of the important technologies in mobile systems. In this paper, adaptive error control investigated using a modified Markov decision process (MDP) model is discussed. An adaptive error control strategy, where the MAC frame length adapts to the varying channel condition, was developed. The proposed algorithm implemented online, achieves better average link layer throughput in a dynamic data channel. The simulation example provided shows that the algorithm can improve the throughput of the wireless data channel by 23%.

The paper presents a formal study on the optimal layer bandwidth allocation for non-cumulative layered video or multiple description coding based broadcasting over broadband wireless networks. We first formulate the optimal bandwidth allocation problem with the objective of maximizing goodput, the total bandwidth delivered to all the receivers in a session. We show that this problem, in its most general form, is computationally intractable. We then propose three practically effective heuristic algorithms for wireless broadcast environments, namely, merge-based allocation (MBA), multi-granular allocation (MGA), and cumulative layering based allocation (CLA). Numerical results show that all three heuristic algorithms significantly outperform non-adaptive allocation algorithms.

One of the key challenges in the design of bandwidth allocation policies for a multi-service mobile cellular network is to guarantee the potentially different quality of service (QoS) requirements from diverse applications, while at the same ensuring that the scarce bandwidth be utilized efficiently. Complete sharing (CS) and dynamic partition (DP) schemes have been shown as viable techniques for managing the bandwidth. However, there has been no study that compares their respective performance, which is the focus of our paper. Specifically, through both analysis and simulation, we demonstrate that both schemes can achieve comparable performance by proper manipulation of control parameters. The tradeoff is that the DP scheme can more easily achieve the target QoS requirement at the expense of over-provisioning, thus can potentially lead to less channel efficiency when compared to a CS based scheme.

In layered video broadcasting, if adaptation is performed only by receivers, significant mismatches between a receiver's expected bandwidth and the actually delivered bandwidth could occur as the adaptation unit is a coarse-grained layer. The paper shows that fine-grained sender adaptation, as a complement to receiver adaptation, can significantly decrease these mismatches. A formal study on optimal session and layer bandwidth allocations for sender adaptation in a broadband cellular network is carried out. The most fundamental issues associated with layered video broadcasting, including system utility and the overhead of layering, are considered. A polynomial-time algorithm is derived for optimal allocation. Experimental results show that it can significantly improve the system utility compared to static allocation algorithms.

We develop recursive algorithms for multichannel blind identification with both statistic and deterministic models. In these algorithms, the estimates are continuously improved while receiving new signals. Therefore, the algorithms can track channel continuously and thus are amenable to real applications such as wireless communications. The computation at each step involves only a small amount of computation. Key words: Blind equalization, stochastic approximation.

The traditional MDP deals with the cost function which only depends on the state and the corresponding action. In the real world however, there are many applications where the cost incurred depends on the particular transition as well, which makes the traditional MDP solution infeasible for these problems. We apply the performance potential theory as an optimization tool for MDP. In particular the notion of the expanded Markov chain is introduced to map this problem to a general form. Both computation-based and sample-path-based algorithms are developed for potential derivation. We address ourselves to the complexity-reduction techniques. Finally, we apply these techniques to the "join the shortest queue" application, which is a significant component in the analysis of communication systems.

The author formulates the trajectory prediction problem by using automaton and language theory. He shows that the automaton method and the perturbation analysis method, which have been developed independently and so far appear to have little relation to each other, can support each other: the former can be used to formulate formally the concept of the latter, and the latter provides an application area for the former. The author defines the predictability of the trajectories of a DES (discrete-event system) based on the trajectories of another DES. The predictability is explained by the projection of a language onto another language. Examples are given to show the application of this concept. It is concluded that the concept introduced here can be viewed as an extension of the controllability and observability theory of DES as well as a generalization of the perturbation analysis theory. >

The goals of perturbation analysis (PA), Markov decision processes (MDPs), and reinforcement learning (RL) are common: to make decisions to improve the system performance based on the information obtained by analyzing the current system behavior. In this paper, we study the relations among these closely related fields. We show that MDP solutions can be derived naturally from performance sensitivity analysis provided by PA. Performance potential plays an important role in both PA and MDPs; it also offers a clear intuitive interpretation for many results. Reinforcement learning, TD(A), neuro-dynamic programming, etc, are efficient ways of estimating the performance potentials and related quantities based on sample paths. This new view of PA, MDPs and RL leads to the gradient-based policy iteration method that can be applied to some nonstandard optimization problems such as those with correlated actions. Sample path-based approaches are also discussed.

This chapter presents some recent results in the area of optimization and Markov decision processes (MDPs). The work starts with performance sensitivity analysis of Markov processes. It is a continuation of the research in the past two decades on the optimization of discrete event dynamic systems, especially the theory of perturbation analysis (PA). We approach the MDP problem from a sensitivity point of view. This new perspective leads to some new insights and offers a clear and concise explanation for the basic concepts and results in MDPs.

We propose a new approach to the single-sample-path-based sensitivity analysis of Markov chains. The approach is based on a fundamental concept: performance potentials. Like the potential energy in physics, only the differences between potentials are important. We show that the differences of potentials can be determined by using the group inverse of I-P, where I is the identity matrix and P the transition matrix of the Markov chain. Potentials reflect the system performance in transient periods and can be used to determine the performance sensitivity with respect to a change of the transition matrix. The results provide a general and efficient approach to the single-sample-path-based sensitivity analysis for many engineering systems, for which the standard perturbation analysis does not work well.

This paper presents a unified algorithm of blind source separation based on the "Independent Component Analysis"(ICA) principle. The algorithm can separate all sources provided there is at most one Gaussian distributed source. The key point is to find a matrix by which the estimates of the original signals are pairwise independent in the absence of noises. If the observed signals are corrupted by noises, minimum-variance unbiased estimates are obtained. In comparison with the algorithm proposed previously by the authors, this algorithm has a parallel pipeline structure, and will not need a preset threshold if both of the 3rd- and 4th-order cumulants of any non-Gaussian distributed source are not zero. This algorithm has significant advantages over existing algorithms.

In the blind source separation problem it is usually assumed that the source signals are mutually independent. It has been realized that this assumption is not necessary. In this paper, we provide some general conditions under which the source signals can be recovered from their linear mixtures. We first define two concepts, the mutually M-th order independence and the pairwise M-th order independence, on a set of random variables. Then we prove that if the source signals are mutually M-th order independent, then those source signals, each of which has at least one nonzero m-th order cumulant for 3/spl les/m/spl les/M, can be separated. This conclusion is in spirit similar to, but more general than, that proposed by Tong et al. (1993). The constructive proof suggests an algorithm for the blind separation of sources which are mutually M-th order independent. Simulation examples are presented to illustrate the results.

In this paper we study the sensitivities of the performance measures in discrete event dynamic systems. The model used is closed queueing networks with exponential service requirements and load-dependent service rates. The performance measures have two general forms: customer average and time average. We derive formulae for the elasticities of the performance measures with respect to the system parameters and develop efficient algorithms for the calculation of these formulae. We show that the steady-state probabilities of the network with one less customer can be determined by the steady-state performance of the original network. We also develop recursive procedures for the online estimation of the elasticities, as well as the steady-state probabilities of the network consisting of one less customer. The estimation procedures require no knowledge of the system parameters and are based on a single sample path of the underlying stochastic process. >

A set-theory framework on the channel assignment problem is presented in this paper. This framework provides a uniform interpretation for the two classes of channel assignment approaches: (1) the centralized assignment based on a predetermined "channel separation matrix", being employed in cellular frequency planning, and (2) the distributed assignment based on actual interference measurements, typically used in cordless telephony. Based on the insights gained, we further propose several algorithms that can be applied to both approaches. A set of simulations is presented to compare our algorithms with some existing centralized assignment algorithms. It is found that our method performs well with a simple procedure that can be easily applied in a distributed fashion for dynamic channel assignment which is an important subject in radio resource management for the emerging personal communications.

Using a simple Markov chain as an example, the author introduces a novel single-sample-path-based estimation method, ensemble-average importance sampling (EAIS). The EAIS is shown to be much more efficient than the time-average likelihood-ratio method and has less variance. It does not resort to regenerative structure. >

Many communication systems are distributed in nature where each geographically separated node has to make its own decisions. In addition, the actions in such systems depend on events, such as packet arrivals. In this paper, the authors study the optimization problem for such systems. Their method is based on the notion of potential. They show that by including the events into the states, the event-dependent systems can be modeled by the standard Markov decision process, and by introducing "aggregated potentials" the dimension of the problem can be reduced. They also propose a distributed approach to the problem, in which each node can estimate the "local potential", and it only requires to transfer the estimated values of these local potentials among nodes, no state information has to be transferred.

Performance potential theory has proved to be a promising tool in optimizing the infinite-horizon Markov decision problem (MDP). So far, the research in this area is implicitly focused on a simple system with a single controller. In this paper, we consider the distributed controlled Markov chain, where the system consists of several individual control units and it evolves under the combined control of these nodes. Motivated by practical background, we investigate a structure of MDP with event-dependent decisions. We explore a notion of expanded Markov chain to map this problem to a traditional MDP model. In particular, we address ourselves to the complexity-reduction techniques to deal with the enlarged state space. For the distributed system where a particular node can only access partial system information, we develop some algorithms for decentralized potential estimation and policy iteration.

We introduce an analytical model to obtain the performance bounds for a single hop optical network based on WDM. We model the network under saturation traffic loading while ignoring the specific channel access scheme as a multi-class closed queueing network (BCMP network), for which a product-form solution for the steady-state probabilities exists. Therefore the exact solutions can be derived. In addition, we study the effect on the system performance of the number of stations in the network, the number of transmitters/receivers at each station, and the traffic distribution pattern.

The concept of voice and telephony over ATM (VTOA) has been widely studied. Although ATM benefits voice communications in many aspects, its packet-switched nature impairs the speech quality. We evaluate the speech quality with a focus on the impact of the cell delay variation (CDV). We build an experimental system to do the evaluations. We also define a new parameter, named cell delay variation accumulation length (CDVAL), to measure the impact of CDV on the speech quality. We observe that the speech quality mainly depends on the value of the CDVAL, but does not strongly depend on the other items, including the distribution of cell end-to-end delay, the position and even the number of the intermittence caused by the CDV. We find that there exists an acceptable threshold of the CDVAL. According to our experiments, to keep the speech in "good" quality (MOS/spl cong/3.5), the CDVAL value must be less than 3 ms without any speech cell loss; such a threshold drops to 2 ms if 5% of the speech cells are lost. The results indicate that a buffer is necessary for CDV compensation at the far end devices in VTOA. The results are also very helpful for the proper design of the network architecture and control algorithms, and is especially important for the design of the CDV compensation schemes, when ATM networks are used to provide voice and telephony services.

We propose and evaluate a three-phase scheduling algorithm for input-queuing ATM switches, and we term it the WRRLA algorithm. The WRRLA algorithm is an improvement over the conventional weighted round robin (WRR) algorithm by simply combining it together with the look ahead (LA) technique. In a WRRLA scheduling operation, the WRR algorithm is first applied to schedule the time-sensitive traffic in order to guarantee their quality of service, and then the LA technique is applied to schedule the data traffic in order to increase the throughput of the ATM switches. Simulation results show that the WRRLA algorithm achieves good performance in a simple architecture, less scheduling computation, higher efficiency (throughput) and lower delay bounds. Moreover, the WRRLA compares favorably with other famous scheduling algorithms, such as parallel iterative matching (PIM) and WRR.

Motivated by the needs of online optimization of real world engineering systems, we study the single sample path based algorithms for Markov decision problems (MDPs). We give a simple example to explain the advantages of the sample path based approach over the traditional computation based approach: matrix inversion is not required; some transition probabilities do not have to be known; it may save storage space; and it gives the flexibility of iterating the actions for a subset of the state space in each iteration. The effect of the estimation errors and the convergence property of the sample path based approach are studied. Finally, we propose a "fast" algorithm which updates the policy whenever the system reaches a particular set of states; the algorithm converges to the true optimal policy with probability one under some conditions.

The performance evaluation of ATM switches is of paramount importance in designing an ATM network. We focus on the evaluation of the cell loss rate (CLR) in nonblocking ATM switches using computer simulations. In particular, we investigate the potential of using importance sampling techniques as a "superfast" alternative to conventional Monte Carlo simulation in finding the CLR in nonblocking ATM switches. We propose a "split switch" method to decouple the input and output queue behaviour, along with the notion of regenerative cycles to achieve fast and accurate results. Numerical results demonstrate that a considerable computation cost can be saved using these proposed importance sampling techniques while maintaining a high degree of accuracy.

The performance evaluation of ATM switches is of paramount importance in the design and analysis of ATM networks. In this paper, we focus on the evaluation of the cell loss rate (CLR) and cell delay probability (CDP) in nonblocking ATM switches using computer simulations. In particular, we investigate the potential of using importance sampling techniques as an "superfast" alternative to conventional Monte Carlo simulation in finding the CLR and CDP in nonblocking ATM switches. We propose a "split switch" method to decouple the input and output queue behaviors, along with the notion of regenerative cycles. Numerical results will demonstrate that considerable computation cost can be saved using the proposed importance sampling techniques while maintaining a high degree of accuracy.