Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
12 results
Search Results
Item On the Poisson Equation for Countable Markov Chains: Existence of Solutions and Parameter Dependence by Probabilistic Methods(1994) Makowski, Armand M.; Shwartz, A.; ISRThis paper considers the Poisson equation associated with time- homogeneous Markov chains on a countable state space. The discussion emphasizes probabilistic arguments and focuses on three separate issues, namely (i) the existence and uniqueness of solutions to the Poisson equation, (ii) growth estimates and bounds on these solutions and (iii) their parametric dependence. Answers to these questions are obtained under a variety of recurrence conditions.Motivating applications can be found in the theory of Markov decision processes in both its adaptive and non-adaptive formulations, and in the theory of Stochastic Approximations. The results complement available results from Potential Theory for Markov chains, and are therefore of independent interest.
Item On Constrained Optimization of the Klimov Network and Related Markov Decision Processes(1991) Makowski, Armand M.; Shwartz, A.; ISRWe solve a constrained version of the server allocation problem for a Klimov network and establish that the optimal constrained schedule is obtained by randomizing between two fixed priority schemes. This generalizes work of Nain and Ross in the context of the competing queue problem, and also covers the discounted cost case.In order to establish these results we develop a general framework for optimization under a single constraint in the presence of index-like policies. This methodology is in principle of wider applicability.
Item An Analysis of Rollback-Based Simulation(1991) Lubachevsky, Boris D.; Shwartz, A.; Weiss, A.; ISRWe present and analyze a general model of rollback in parallel processing. The analysis points out three possible modes where rollback may become excessive; we provide an example of each type. We identify the parameters which determine a stability, or efficiency region for the simulation. Our analysis suggests the possibility of a dangerous "phase-transition" from stability to instability in the parameter space. In particular, a rollback algorithm may work efficiently for a small system but become inefficient for a large system. Moreover, for a given system, it may work quickly for a while and then suddely slow down.On the positive side, we give a tunable algorithm, Filtered Rollback, that is designed to avoid the failure modes. Under appropriate assumptions, we provide a rigorous mathematical proof that Filtered Rollback is efficient, if implemented on a reasonably efficient multiprocessor. In particular: we show that the average time t to complete the simulation of a system with N nodes and R events on a p -processor PRAM satisfies t = 0 ((R/p) + (R/N) log p).
The analysis is based on recent work by the authors on Branching Random Walks with a barrier.
Item Guaranteed Performance Regions for Markov Models(1991) Shimkin, N.; Shwartz, A.; ISRA user facing a multi-user resource-sharing system considers a vector of performance measures (e.g. response times to various tasks). Acceptable performance is defined through a set in the space of performance vectors. Can the user obtain a (time- average) performance vector which approaches this desired set? We consider the worst-case scenario, where other users may, for selfish reasons, try to exclude his vector from the desired set. For a Markovian model of the system, we give a sufficient condition for approachability (which is also necessary for convex sets), and construct appropriate policies. The mathematical formulation leads to an approachability theory for stochastic games.Item Analysis and Adaptive Control of a Discrete-Time Single-Senrer Network with Random Routing.(1989) Makowski, Armand M.; Shwartz, A.; ISRThis paper considers a discrete time system composed of K infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechanism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation algorithm is proposed to drive a long- run average cost to a given value. The motivation can be traced to implementation imues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions that guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems.Item Stochastic Approximations for Finite-State Markov Chains.(1989) Ma, Dye-Jyun; Makowski, Armand M.; Shwartz, A.; ISRThis paper develops an a.s. convergence theory for a class of projected Stochastic Approximations driven by finite-state Markov chains. The conditions are mild and are given explicitly in terms of the model data, mainly the Lipschitz continuity of the one- step transition probabilities. The approach used here is a version of the ODE method as proposed by Metivier and Priouret. It combines the Kushner-Clark Lemma with properties of the Poisson equation associated with the underlying family of Markov chains. The class of algorithms studied here was motivated by implementation issues for constrained Markov decision problems, where the policies of interest often depend on quantities not readily available due either to insufflcient knowledge of the model parameters or to computational difficulties. This naturally leads to the on-line estimation (or computation) problem investigated here. Several examples from the area of queueing systems are discussed.Item Analysis and Adaptive Control of a Discrete-Time Single-Server Network with Random-Routing.(1989) Makowski, Armand M.; Shwartz, A.; ISRThis paper considers a discrete-time system composed of K infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechanism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation algorithm is proposed to drive a long- run average cost to a given value. The motivation can be traced to implementation issues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions which guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems.Item Stochastic Approximations for Finite-State Markov Chains.(1987) Ma, Dye-Jyun; Makowski, Armand M.; Shwartz, A.; ISRIn constrained Markov decision problems, optimal policies are often found to depend on quantities which are not readily available due either to insufficient knowledge of the model parameters or to computational difficulties. Thia motivates the on-line estimation (or computation) problem investigated in this paper in the context of a single parameter family of finite-state Markov chains. The computation is implemented through an algorithm of the Stochastic Approximations type which recursively generates on-line estimates for the unknown value. A useful methodology is outlined for investigating the strong consistency of the algorithm and the proof is carried out under a set of simplifying assumptions in order to illustrate the key ideas unencumbered with technical details. An application to constrained Markov deciaion processes is briefly discussed.Item Adaptive Policies for a System of Competing Queues I: Convergence Results for the Long-Run Average Cost.(1986) Shwartz, A.; Makowski, Armand M.; ISRThis paper considers a system of discrete-time queues competing for the attention of a single geometric server. The problem of implementing a given Markov stationary service allocation policy g through an adaptive allocation policy ALPHA is posed and convergence of the longrun average cost under such adaptive policy ALPHA to the long run average cost under the policy g is investigated. Such a question typically arises in the context of Markov decision problems associated with this queueing system, say when some of the model parameters are not available [1, 20], or when the optimality criterion incorporates constraints [14, 21, 20]. Conditions are given so that the long-run average cost under the policy ALPHA converges to the corresponding cost under the policy g, provided a natural condition on the relative asymptotic behavior of the policies g , ALPHA holds. Applications of the results developed here are discussed in a companion paper [20]. However, the ideas of this paper are of independent interest , should prove useful in studying implementation , adaptive control issues for broad classes of Markov decision problems [12].Item Implementation Issues for Markov Decision Processes.(1986) Makowski, Armand M.; Shwartz, A.; ISRIn this paper, the problem of steering a long-run average coat functional to a prespecified value is discussed in the context of Markov decision processes wish countable statespace; this problem naturally arises in the study of constrained Markov decision processes by Lagrangian arguments. Under reasonable assumptions, a Markov stationary steering control is shown to exist, and to be obtained by fixed memoryless randomization between two Markov stationary policies. The implementability of this randomized policy is investigated in view of the fact that the randomization bias is solution to a (highly) nonlinear equation, which may not even be available in the absence of full knowledge of the model parameter values. Several proposals for implementation are made and their relative properties discussed. The paper closes with an outline of a methodology that was found useful in investigating properties of Certainty Equivalence implementations.