From Perturbation Analysis to Markov Decision Processes and Reinforcement Learning

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(), neuro-dynamic programming, etc., are efficient ways of estimating the performance potentials and related quantities based on sample paths. The sensitivity point of view of PA, MDP, and RL brings in some new insight to the area of learning and optimization. In particular, gradient-based optimization can be applied to parameterized systems with large state spaces, and gradient-based policy iteration can be applied to some nonstandard MDPs such as systems with correlated actions, etc. Potential-based on-line approaches and their advantages are also discussed.     

Numerical computation of H∞ optimal performance

We present new algorithms for computing theH optimal performance for a class of single-input/single-output (SISO) infinite-dimensional systems. The algorithms here only require use of one or two fast Fourier transforms (FFT) and Cholesky decompositions; hence the algorithms are particularly simple and easy to implement. Numerical examples show that the algorithms are stable and efficient and converge rapidly. The method has wide applications including to theH optimal control of distributed parameter systems. We illustrate the technique with applications to some delay problems and a partial differential equation (PDE) model. The algorithms we present are also an attractive approach to the solution of high-order finite-dimensional models for which use of state space methods would present computational difficulties.     

Compositional checking of satisfaction

We present a compositional method for deciding whether a process satisfies an assertion. Assertions are formulas in a modal -calculus, and processes are drawn from a very general process algebra inspired by CCS and CSP. Well-known operators from CCS, CSP, and other process algebras appear as derived operators. The method iscompositional in the structure of processes and works purely on the syntax of processes. It consists of applying a sequence ofreductions, each of which only takes into account the top-level operator of the process. A reduction transforms a satisfaction problem for a composite process into equivalent satisfaction problems for the immediate subcomponents. Using process variables, systems with underfined subcomponents can be defined, and given an overall requirement to the system,necessary and sufficient conditions on these subcomponents can be found. Hence the process variables make it possible to specify and reason about what are often referred to ascontexts, environments, andpartial implementations. Since reductions are algorithms that work on syntax, they can be considered as forming a bridge between traditional noncompositional model checking and compositional proof systems.     

Uncertain jumping systems with strong and weak functional delays

This paper provides complete results on the stability behavior of a class of uncertain dynamical systems with jumping parameters and functional time-delays. The jumping parameters are modeled as a continuous-time, discrete-state Markov process. The parametric uncertainties are norm-bounded appearing in all system matrices and the delay factor depends on the mode of operation. Notions of weak and strong stochastic stability for the jumping system are developed depending on the available information using a prescribed -performance. Memoryless and delayed-state feedback are considered to guarantee the closed-loop stability. All the results are cast into linear matrix inequalities format. A numerical example is given to illustrate the developed results.     

Virtual Private/Overlay Network Design With Traffic Concentration and Shared Protection

In this paper different algorithms are presented and evaluated for designing Virtual Private/Overlay Network (VPNs/VONs) over any network that supports resource partitioning e.g. ATM (Asynchronous Transfer Mode), MPLS (Multi Protocol Label Switching), or SDH/SONET (Synchronous Digital Hierarchy/Synchronous Optical Networking). All algorithms incorporate protection as well. The VPNs/VONs are formed by full mesh demand sets between VPN/VON endpoints. The service demands of VPNs/VONs are characterized by the bandwidth requirements of node-pairs (pipe-model).We investigated four design modes with three pro-active path based shared protection path algorithms and four heuristics to calculate the pairs of paths. The design mode determines the means of traffic concentration. The protection path algorithms use Dijkstras shortest path calculation with different edge weights. The demands are routed one-by-one, therefore the order in which they are processed matters.To eliminate this factor we used three heuristics (simulated allocation, simulated annealing, threshold accepting). We present numerical results obtained by simulation regarding the required total amount of capacity, the number of reserved edges, and the average length of paths.Péter Hegyi received MSc (2004) degree from the Budapest University of Technology and Economics, Hungary, where he is currently a PhD student at the Department of Telecommunications and Media Informatics. His research interests focus on design of intra- and inter-domain multilayer grooming networks and routing with protection. He has been involved in a few related projects (IKTA, ETIK, NOBEL).Markosz Maliosz is a researcher in the High Speed Networks Laboratory, Department of Telecommunication and Media Informatics at the Budapest University of Technology and Economics, where he received his MSc degree in Computer Science (1998). He has participated in projects concerning telecommunication services, network device control, Voice and Video over IP. His current research areas are Virtual Private Networking and traffic engineering in optical networks.Ákos Ladányi is a student at the Department of Telecommunications and Media Informatics at the Budapest University of Technology and Economics. His research interests focus on routing, network resilience, and combinatorial optimization.Tibor Cinkler has received MSc(94) and PhD(99) degrees from the Budapest University of Technology and Economics, Hungary, where he is currently Associate Professor at the Department of Telecommunications and Media Informatics. His research interests focus on routing, design, configuration, dimensioning and resilience of IP,MPLS, ATM, ngSDH and particularly of WR-DWDMbased multilayer networks. He is the author of over 60 refereed scientific publications and of 3 patents.     

Analysis of local operators applied to discrete tracking problems

This article investigates various local operators in a discrete (1, )-setting applied to tracking problems, a specific class of non-stationary problems. In the first instance, the influence of operator properties on the tracking performance is examined. Both the enforcement of bigger steps and, especially, directed mutations are found to increase the tracking accuracy considerably. For the examination of highly time restricted problems, a correlation between the population size and the severity of the problem dynamics is assumed. Relatively large population sizes are found to be advantageous if the number of evaluations has a big influence on the severity. All results are obtained using a fixpoint analysis of a worst-case model as well as simulations within a two-dimensional Markov model.     

Semi-Markov decision problems and performance sensitivity analysis

Recent research indicates that Markov decision processes (MDPs) can be viewed from a sensitivity point of view; and the 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 the PA theory for semi-Markov processes (SMPs); and then 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 can be derived based on the 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.     

Maximum queue size and hashing with lazy deletion

We answer questions about the distribution of the maximum size of queues and data structures as a function of time. The concept of maximum occurs in many issues of resource allocation. We consider several models of growth, including general birth-and-death processes, the M/G/ model, and a non-Markovian process (data structure) for processing plane-sweep information in computational geometry, called hashing with lazy deletion (HwLD). It has been shown that HwLD is optimal in terms of expected time and dynamic space; our results show that it is also optimal in terms of expectedpreallocated space, up to a constant factor.We take two independent and complementary approaches: first, in Section 2, we use a variety of algebraic and analytical techniques to derive exact formulas for the distribution of the maximum queue size in stationary birth-and-death processes and in a nonstationary model related to file histories. The formulas allow numerical evaluation and some asymptotics. In our second approach, in Section 3, we consider the M/G/ model (which includes M/M/ as a special case) and use techniques from the analysis of algorithms to get optimal big-oh bounds on the expected maximum queue size and on the expected maximum amount of storage used by HwLD in excess of the optimal amount. The techniques appear extendible to other models, such as M/M/1.Research was also done while the author was at Princeton University, supported in part by a Procter Fellowship.Research was also done while the author was on sabbatical at INRIA in Rocquencourt, France, and at Ecole Normale Supérieure in Paris, France. Support was provided in part by National Science Foundation Research Grant DCR-84-03613, by an NSF Presidential Young Investigator Award with matching funds from an IBM Faculty Development Award and an AT&T research grant, by a Guggenheim Fellowship, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-83-K-0146 and ARPA Order 6320, Amendment 1.     

Modular visions: Referents, context and strategies for database open media works

The processes of constructing meaning in digital database environments entail a paradigm shift from previous models of audio-visual communication. Media emerging from the Electro-mechanical era (film/TV/video) present fixed spatio-temporal linearity and material conditions which objectify and render passive viewer and process. The problematic aspects of cinematic communication were addressed by Latin American filmmakers of the Third Cinema movement. Their concerns and approach presaged and assisted an understanding of the radical redefinition of audio-visual communication possible with digital databases. The conceptual and aesthetic aspirations of Third Cinema artists such as Julio Garcia Espinosa and Fernando Solanas were ultimately contradictory to linear media and find their fitting medium in digital modular construction. The materiality of database expression lacks an intrinsic temporal or spatial state and permits a more dynamic and multidirectional set of power relationships between author/s, piece, viewer/s. Other important referents for contextualising database art are modern art practitioners that rejected linear representational space and fractured the centrality of authorship. The author's own work, ...two, three, many Guevaras, an exploratory database environment, embraces the redefinition of process as artistic expression, the empowerment of interacting generative forces, and serves to illustrate the revolutionary potential of the new media.     

Estimation comparison on busy period for a controllable M/G/1 system with bicriterion policy

We propose an estimator for the expected busy period (denoted by β) of a controllable M/G/1 queueing system in which the server applies a bicriterion 〈p, N〉 policy during his idle period. Using this estimator, we construct new confidence intervals for β, which are based on five bootstrap methods; standard bootstrap (SB), percentile bootstrap (PB), bootstrap pivotal (BP), bias-corrected percentile bootstrap (BCPB), bias-corrected and accelerated bootstrap (BCa). A numerical simulation study is conducted in order to demonstrate performance of the proposed estimator $\hat{\beta }$ and bootstrap confidence intervals for β. From the simulation results, we show that $\hat{\beta }$ is a consistent estimator for β, which agrees with the theoretical results. In addition, we also investigate the accuracy of the five bootstrap confidence intervals by calculating the coverage percentage and the relative coverage (defined as the ratio of coverage percentage to average length of confidence interval). Detailed discussions of simulation results for three queueing models are presented.     

Global culture, local cultures and the internet: The Thai example

This paper addresses the questions of whether and, if so, how and to what extent the Internet brings about homogenisation of local cultures in the world. It examines a particular case, that of Thai culture, through an investigation and interpretation of a Usenet newsgroup, soc.culture.thai. Two threads of discussion in the newsgroup are selected. One deals with criticisms of the Thai government and political leaders, and the other focuses on whether the Thai language should be a medium, or perhaps the only medium, of communication in the newsgroup. It is found that, instead of erasing local cultural boundaries, creating a worldwide monolithic culture, the Internet reduplicates the existing cultural boundaries. What the Internet does, on the contrary, is to create an umbrella cosmopolitan culture which is necessary for communication among people from disparate cultures. That culture, however, is devoid of thick backgrounds, in Michael Walzer's sense.     

Perturbation realization, potentials, and sensitivity analysis ofMarkov processes

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     

A functional programming approach to the specification and verification of concurrent systems

Networks of communicating processes can be viewed as networks of stream transformers and programmed in a lazy functional language. Thus the correctness of concurrent systems can be reduced to the correctness of functional programs. In this paper such correctness is proved formally in the-calculus extended with recursion equations for functional programs. The-calculus is chosen since it allows the definition of properties by least fixed points (induction) as well as by greatest fixed points (coinduction), and since greatest fixed points are useful for formalising properties, such as fairness, of infinitely proceeding programs. Moreover, non-deterministic processes are represented as incompletely specified deterministic processes, that is, as properties of stream transformers. This method is illustrated by proving the correctness of the alternating bit protocol.     

The Eigenvalue Problem for the 2D Laplacian in ℋ-Matrix Arithmetic and Application to the Heat and Wave Equation

A class of matrices (-matrices) has recently been introduced by Hackbusch for approximating large and fully populated matrices arising from FEM and BEM applications. These matrices are data-sparse and allow approximate matrix operations of almost linear complexity. In the present paper, we choose a special class of -matrices that provides a good approximation to the inverse of the discrete 2D Laplacian. For these 2D -matrices we study the blockwise recursive schemes for block triangular linear systems of equations and the Cholesky and LDL^T factorization in an approximate arithmetic of almost linear complexity. Using the LDL^T factorization we compute eigenpairs of the discrete 2D Laplacian in -matrix arithmetic by means of a so-called simultaneous iteration for computing invariant subspaces of non-Hermitian matrices due to Stewart. We apply the -matrix techniques to approximate the solutions of the high-frequency 2D wave equation for smooth initial data and the 2D heat equation for arbitrary initial data by spectral decomposition of the discrete 2D Laplacian in, up to logarithmic factors, optimal complexity.     

Querying high-dimensional data in single-dimensional space

In this paper, we propose a new tunable index scheme, called iMinMax( ), that maps points in high-dimensional spaces to single-dimensional values determined by their maximum or minimum values among all dimensions. By varying the tuning knob, , we can obtain different families of iMinMax structures that are optimized for different distributions of data sets. The transformed data can then be indexed using existing single-dimensional indexing structures such as the B ⁺ -trees. Queries in the high-dimensional space have to be transformed into queries in the single-dimensional space and evaluated there. We present efficient algorithms for evaluating window queries as range queries on the single-dimensional space. We conducted an extensive performance study to evaluate the effectiveness of the proposed schemes. Our results show that iMinMax( ) outperforms existing techniques, including the Pyramid scheme and VA-file, by a wide margin. We then describe how iMinMax could be used in approximate K-nearest neighbor (KNN) search, and we present a comparative study against the recently proposed iDistance, a specialized KNN indexing method.Received: 21 May 2000, Revised: 14 March 2002, Published online: 8 April 2004Edited by: M. Kitsuregawa.     

T-Efficient Calculation of the ε-Solutions to Problems of Calculus and Applied Mathematics. II

An approach to the construction of algorithms that are efficient for complexity and that calculate -solutions to computation and applied mathematics problems is described in the first part of the present paper. This approach is applied for creation of T-efficient algorithms used to solve some classes of nonlinear integral equations, ordinary differential equations, and global optimization.     

T-Efficient Calculation of the ∈-Solutions to Problems of Calculus and Applied Mathematics. I

An approach to construction of the efficient by complexity algorithms for calculation of -solutions is presented for problems of calculus and applied mathematics. The reserves which can be used in this approach are revealed. The present approach is illustrated by two classes of problems: approximation of functions and numerical integration.     

Modal Pure Type Systems

We present a framework for intensional reasoning in typed -calculus. In this family of calculi, called Modal Pure Type Systems (MPTSs), a propositions-as-types-interpretation can be given for normal modal logics. MPTSs are an extension of the Pure Type Systems (PTSs) of Barendregt (1992). We show that they retain the desirable meta-theoretical properties of PTSs, and briefly discuss applications in the area of knowledge representation.