Search

Sample complexity bounds are a common performance metric in the reinforcement learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilon-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent min–max lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Q-learning algorithm with an optimized step-size sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors. [ABSTRACT FROM AUTHOR]

Value functions derived from Markov decision processes arise as a central component of algorithms as well as performance metrics in many statistics and engineering applications of machine learning. Computation of the solution to the associated Bellman equations is challenging in most practical cases of interest. A popular class of approximation techniques, known as temporal difference (TD) learning algorithms, are an important subclass of general reinforcement learning methods. The algorithms introduced in this article are intended to resolve two well-known issues with TD-learning algorithms. Their slow convergence due to very high central limit theorem variance, and the fact that, for the problem of computing the relative value function, consistent algorithms exist only in special cases. First we show that the gradients of these value functions admit a representation that lends itself to algorithm design. Based on this result, a new class of differential TD-learning algorithms is introduced. For Markovian models on Euclidean space with smooth dynamics, the algorithms are shown to be consistent under general conditions. Numerical results show dramatic variance reduction in comparison to standard methods. [ABSTRACT FROM AUTHOR]

The distributed computation of Nash equilibria is assuming growing relevance in engineering where such problems emerge in the context of distributed control. Accordingly, we present schemes for computing equilibria of two classes of static stochastic convex games complicated by a parametric misspecification, a natural concern in the control of large-scale networked engineered system. In both schemes, players learn the equilibrium strategy while resolving the misspecification: 1) Monotone stochastic Nash games: We present a set of coupled stochastic approximation schemes distributed across agents in which the first scheme updates each agent's strategy via a projected (stochastic) gradient step, whereas the second scheme updates every agent's belief regarding its misspecified parameter using an independently specified learning problem. We proceed to show that the produced sequences converge in an almost sure sense to the true equilibrium strategy and the true parameter, respectively. Surprisingly, convergence in the equilibrium strategy achieves the optimal rate of convergence in a mean-squared sense with a quantifiable degradation in the rate constant; 2) Stochastic Nash–Cournot games with unobservable aggregate output: We refine 1) to a Cournot setting where we assume that the tuple of strategies is unobservable while payoff functions and strategy sets are public knowledge through a common knowledge assumption. By utilizing observations of noise-corrupted prices, iterative fixed-point schemes are developed, allowing for simultaneously learning the equilibrium strategies and the misspecified parameter in an almost sure sense. [ABSTRACT FROM PUBLISHER]

This paper concerns state estimation problems in a mean field control setting. In a finite population model, the goal is to estimate the joint distribution of the population state and the state of a typical individual. The observation equations are a noisy measurement of the population. The general results are applied to demand dispatch for regulation of the power grid, based on randomized local control algorithms. In prior work by the authors it is shown that local control can be designed so that the aggregate of loads behaves as a controllable resource, with accuracy matching or exceeding traditional sources of frequency regulation. The operational cost is nearly zero in many cases. The information exchange between grid and load is minimal, but it is assumed in the overall control architecture that the aggregate power consumption of loads is available to the grid operator. It is shown that the Kalman filter can be constructed to reduce these communication requirements, and to provide the grid operator with accurate estimates of the mean and variance of quality of service (QoS) for an individual load. [ABSTRACT FROM AUTHOR]

This technical note extends the feedback particle filter (FPF) methodology and algorithms to the problem of filtering a continuous-time Markov chain. The main contribution is the development of a feedback control-based transformation of the Wonham filter, where the control input is realized via a time-modulated Poisson counter process. A complete characterization of the feedback mechanism that defines the FPF is obtained, which leads to tractable algorithms for the nonlinear filtering problem even for large state spaces. Numerical examples are introduced to help illustrate the application of these techniques. [ABSTRACT FROM PUBLISHER]

Renewable energy sources such as wind and solar power have a high degree of unpredictability and time-variation, which makes balancing demand and supply challenging. One possible way to address this challenge is to harness the inherent flexibility in demand of many types of loads. Introduced in this paper is a technique for decentralized control for automated demand response that can be used by grid operators as ancillary service for maintaining demand-supply balance. A randomized control architecture is proposed, motivated by the need for decentralized decision making, and the need to avoid synchronization that can lead to large and detrimental spikes in demand. An aggregate model for a large number of loads is then developed by examining the mean field limit. A key innovation is a linear time-invariant (LTI) system approximation of the aggregate nonlinear model, with a scalar signal as the input and a measure of the aggregate demand as the output. This makes the approximation particularly convenient for control design at the grid level. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to show how insight obtained from a mean-field model can be used to create an architecture for approximate dynamic programming (ADP) for a certain class of games comprising of a large number of agents. The general technique is illustrated with the aid of a mean-field oscillator game model introduced in our prior work. The states of the model are interpreted as the phase angles for a collection of nonhomogeneous oscillators, and in this way the model may be regarded as an extension of the classical coupled oscillator model of Kuramoto. The paper introduces ADP techniques for design and adaptation (learning) of approximately optimal control laws for this model. For this purpose, a parameterization is proposed, based on an analysis of the mean-field PDE model for the game. In an offline setting, a Galerkin procedure is introduced to choose the optimal parameters while in an online setting, a steepest descent algorithm is proposed. The paper provides a detailed analysis of the optimal parameter values as well as the Bellman error with both the Galerkin approximation and the online algorithm. Finally, a phase transition result is described for the large population limit when each oscillator uses the approximately optimal control law. A critical value of the control penalty parameter is identified: above this value, the oscillators are incoherent; and below this value (when control is sufficiently cheap) the oscillators synchronize. These conclusions are illustrated with results from numerical experiments. [ABSTRACT FROM AUTHOR]

The feedback particle filter introduced in this paper is a new approach to approximate nonlinear filtering, motivated by techniques from mean-field game theory. The filter is defined by an ensemble of controlled stochastic systems (the particles). Each particle evolves under feedback control based on its own state, and features of the empirical distribution of the ensemble. The feedback control law is obtained as the solution to an optimal control problem, in which the optimization criterion is the Kullback-Leibler divergence between the actual posterior, and the common posterior of any particle. The following conclusions are obtained for diffusions with continuous observations: 1) The optimal control solution is exact: The two posteriors match exactly, provided they are initialized with identical priors. 2) The optimal filter admits an innovation error-based gain feedback structure. 3) The optimal feedback gain is obtained via a solution of an Euler-Lagrange boundary value problem; the feedback gain equals the Kalman gain in the linear Gaussian case. Numerical algorithms are introduced and implemented in two general examples, and a neuroscience application involving coupled oscillators. In some cases it is found that the filter exhibits significantly lower variance when compared to the bootstrap particle filter. [ABSTRACT FROM AUTHOR]

It is known that state-dependent, multi-step Lyapunov bounds lead to greatly simplified verification theorems for stability for large classes of Markov chain models. This is one component of the “fluid model” approach to stability of stochastic networks. In this paper we extend the general theory to randomized multi-step Lyapunov theory to obtain criteria for stability and steady-state performance bounds, such as finite moments. These results are applied to a remote stabilization problem, in which a controller receives measurements from an erasure channel with limited capacity. Based on the general results in the paper it is shown that stability of the closed loop system is assured provided that the channel capacity is greater than the logarithm of the unstable eigenvalue, plus an additional correction term. The existence of a finite second moment in steady-state is established under additional conditions. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to understand phase transition in noncooperative dynamic games with a large number of agents. Applications are found in neuroscience, biology, and economics, as well as traditional engineering applications. The focus of analysis is a variation of the large population linear quadratic Gaussian (LQG) model of Huang 2007, comprised here of a controlled N-dimensional stochastic differential equation model, coupled only through a cost function. The states are interpreted as phase angles for a collection of heterogeneous oscillators, and in this way the model may be regarded as an extension of the classical coupled oscillator model of Kuramoto. A deterministic PDE model is proposed, which is shown to approximate the stochastic system as the population size approaches infinity. Key to the analysis of the PDE model is the existence of a particular Nash equilibrium in which the agents ‘opt out’ of the game, setting their controls to zero, resulting in the ‘incoherence’ equilibrium. Methods from dynamical systems theory are used in a bifurcation analysis, based on a linearization of the partial differential equation (PDE) model about the incoherence equilibrium. A critical value of the control cost parameter is identified: above this value, the oscillators are incoherent; and below this value (when control is sufficiently cheap) the oscillators synchronize. These conclusions are illustrated with results from numerical experiments. [ABSTRACT FROM PUBLISHER]

This paper is concerned with model reduction for complex Markov chain models. The Kullback–Leibler divergence rate is employed as a metric to measure the difference between the Markov model and its approximation. For a certain relaxation of the bi-partition model reduction problem, the solution is shown to be characterized by an associated eigenvalue problem. The form of the eigenvalue problem is closely related to the Markov spectral theory for model reduction. This result is the basis of a heuristic proposed for the m-ary partition problem, resulting in a practical recursive algorithm. The results are illustrated with examples. [ABSTRACT FROM AUTHOR]

This paper concerns control and performance evaluation for stochastic network models. Structural properties of value functions are developed for controlled Brownian motion (CBM) and deterministic (fluid) workload-models, leading to the following conclusions: Outside of a null-set of network parameters, the following hold. i) The fluid value-function is a smooth function of the initial state. Under further minor conditions, the fluid value function satisfies the derivative boundary conditions that are required to ensure it is in the domain of the extended generator for the CBM model. Exponential ergodicity of the CBM model is demonstrated as one consequence. ii) The fluid value-function provides a shadow function for use in simulation variance reduction for the stochastic model. The resulting simulator satisfies an exact large deviation principle, while a standard simulation algorithm does not satisfy any such bound. iii) The fluid value-function provides upper and lower bounds on performance for the CBM model. This follows from an extension of recent linear programming approaches to performance evaluation. [ABSTRACT FROM AUTHOR]

The article discusses the advantages of college-wide interdisciplinary and interdepartmental control systems laboratory. The College of Engineering Control Systems Laboratory at the University of Illinois in Chicago provides basic instruction in feedback control to more than 700 students from the departments of Aerospace Engineering, Electrical and Computer Engineering, General Engineering, and Mechanical and Industrial Engineering. Two aspects of control history that have contributed to the success of control in practice are the application of a broad range of mathematical methods and a flexible approach to modeling to facilitate control design. Undergraduate students in control courses in the university learn how to obtain linear models based on linearization, time-domain experiments combined with first principle analysis, and frequency-domain experiments. Several basic features of control systems can be understood by careful investigation of the dc motor. The existing U.S. paradigm of individual departmental laboratories is increasingly difficult to justify due to the interdisciplinary nature of modern control engineering, the high cost and rapid obsolescence of technology, and the demands on faculty time.

Control-synthesis techniques are developed for demand-driven production systems. The resulting policies are time- optimal for a deterministic model, and approximately time-optimal for a stochastic model. Moreover, they are easily adapted to take into account a range of issues that arise in a realistic, dynamic environment. In particular, control synthesis techniques are developed for models in which resources are temporarily unavailable. This may be due to failure, maintenance, or an unanticipated change in demand. These conclusions are based upon the following development. [ABSTRACT FROM AUTHOR]

Studies the identification and adaptive control of time-varying linear systems. Development of lower bounds to the mean squared error for estimates and performance; Identification of conditions for stability of the system; Existence of a steady-state solution to the system equations.

Presents a study which addresses the average cost optimal control problem for Markov decision processes with unbounded costs. Finding that the policy iteration algorithm generates a sequence of policies which are c-regular; Requirements of this result; Provision of elementary criteria for the existence of optimal policies for Markov decision processes; Effects of the results when specialized to specific applications.