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]

Approximating model predictive control (MPC) policy using expert-based supervised learning techniques requires labeled training datasets sampled from the MPC policy. This is typically obtained by sampling the feasible state space and evaluating the control law by solving the numerical optimization problem offline for each sample. Although the resulting approximate policy can be cheaply evaluated online, generating large training samples to learn the MPC policy can be time-consuming and prohibitively expensive. This is one of the fundamental bottlenecks that limit the design and implementation of MPC policy approximation. This technical article aims to address this challenge, and proposes a novel sensitivity-based data augmentation scheme for direct policy approximation. The proposed approach is based on exploiting the parametric sensitivities to cheaply generate additional training samples in the neighborhood of the existing samples. [ABSTRACT FROM AUTHOR]

Reinforcement learning aims to find policies that maximize an expected cumulative reward in Markov decision processes with unknown transition probabilities. Policy gradient (PG)-algorithms use stochastic gradients of the value function to update the policy. A major drawback of PG-algorithms is that they are limited to episodic tasks (multiple finite-horizon trajectories) unless stringent stationarity assumptions are imposed on the trajectories. Hence, they need restarts and cannot be fully implemented online, which is critical for systems need to adapt to new tasks and/or environments in deployment. Moreover, the standard stationary formulation ignores transient behaviors. This motivates our study of discounted MDPs of infinite horizon without restarts. However, it is unknown if in this case following stochastic PG-type estimates would improve the policy. The main result of this work is to establish that when policies belong to a reproducing kernel Hilbert space (RKHS), and the kernel is selected properly, then these PG-estimates are ascent directions for the value function conditioned to any arbitrary initial point. This allows us to prove convergence of our online algorithm to the local optima. A numerical example shows that an agent running our online algorithm learns to navigate and succeeds in a surveillance task that requires looping between two goal locations. This example corroborates our theoretical findings about the ascent directions of subsequent stochastic gradients. It also shows how our online algorithm guides the agent through a continuing cyclic trajectory that does not comply with the standard stationarity assumptions in the literature for non-episodic training. [ABSTRACT FROM AUTHOR]

This article is concerned with the distributed Kalman filtering problem for discrete-time linear systems whose measurement information comes from a set of sensor nodes that can communicate with their direct neighbors. Two algorithms for distributed Kalman filtering are proposed, where the first algorithm is based on single-node measurement and the second algorithm is based on neighboring-node measurements. In order to improve the performance, a novel criterion is introduced to the algorithm design, where in the criterion, the proximity of matrix’s trace is used to determine the proximity of positive semidefinite matrix. We prove that all the proposed algorithms for distributed Kalman filtering are unbiased. Numerical examples are provided to demonstrate the correctness of the proposed theoretical method and the performance of the proposed new design technique. [ABSTRACT FROM AUTHOR]

This article is about the data-driven computation of optimal control for a class of control affine deterministic nonlinear systems. We assume that the control dynamical system model is not available, and the only information about the system dynamics is available in the form of time-series data. We provide a convex formulation for the optimal control problem (OCP) of the nonlinear system. The convex formulation relies on the duality result in the dynamical system’s stability theory involving density function and Perron–Frobenius operator. We formulate the OCP as an infinite-dimensional convex optimization program. The finite-dimensional approximation of the optimization problem relies on the recent advances made in the Koopman operator’s data-driven computation, which is dual to the Perron–Frobenius operator. Simulation results are presented to demonstrate the application of the developed framework. [ABSTRACT FROM AUTHOR]

Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov decision process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first-order method and, therefore, it may take a large number of iterations to converge to the optimal solution. Successive relaxation is a popular technique that can be applied to solve a fixed point equation. It has been shown in the literature that under a special structure of the MDP, successive overrelaxation technique computes the optimal value function faster than standard value iteration. In this article, we propose a second-order value iteration procedure that is obtained by applying the Newton–Raphson method to the successive relaxation value iteration scheme. We prove the global convergence of our algorithm to the optimal solution asymptotically and show the second-order convergence. Through experiments, we demonstrate the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

Timed extended reachability graphs (TERG) of time Petri nets abstract the temporal specifications and represent the feasible trajectories under the earliest firing policy. One drawback of such graphs is the rapid increase in the number of states with respect to time specifications. For this reason, approximations of TERG that remove some states have been studied in recent works. In this article, we improve the approximation of a TERG. New objects—called vertices—are defined to manipulate the time constraints and algorithms are proposed to cluster nearby vertices. A metric based on the time constraints is defined for this purpose and a cluster TERG of reduced size is obtained. [ABSTRACT FROM AUTHOR]

This article addresses the problem of learning the optimal control policy for a nonlinear stochastic dynamical. This problem is subject to the “curse of dimensionality” associated with the dynamic programming method. This article proposes a novel decoupled data-based control (D2C) algorithm that addresses this problem using a decoupled, “open-loop–closed-loop,” approach. First, an open-loop deterministic trajectory optimization problem is solved using a black-box simulation model of the dynamical system. Then, closed-loop control is developed around this open-loop trajectory by linearization of the dynamics about this nominal trajectory. By virtue of linearization, a linear quadratic regulator based algorithm can be used for this closed-loop control. We show that the performance of D2C algorithm is approximately optimal. Moreover, simulation performance suggests a significant reduction in training time compared to other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

In this article, we propose a symplectic algorithm for the stable manifolds of the Hamilton–Jacobi equations combined with an iterative procedure in [N. Sakamoto and A. J. van der Schaft, “Analytical approximation methods for the stabilizing solution of the Hamilton–Jacobi equation,” IEEE Trans. Autom. Control, 2008]. Our algorithm includes two key aspects. The first one is to prove a precise estimate for radius of convergence and the errors of local approximate stable manifolds. The second one is to extend the local approximate stable manifolds to larger ones by symplectic algorithms, which have better long-time behaviors than general-purpose schemes. Our approach avoids the case of divergence of the iterative sequence of approximate stable manifolds and reduces the computation cost. We illustrate the effectiveness of the algorithm by an optimal control problem with exponential nonlinearity. [ABSTRACT FROM AUTHOR]

This article develops a novel passive stochastic gradient algorithm. In passive stochastic approximation, the stochastic gradient algorithm does not have control over the location where noisy gradients of the cost function are evaluated. Classical passive stochastic gradient algorithms use a kernel that approximates a Dirac delta to weigh the gradients based on how far they are evaluated from the desired point. In this article, we construct a multikernel passive stochastic gradient algorithm. The algorithm performs substantially better in high dimensional problems and incorporates variance reduction. We analyze the weak convergence of the multikernel algorithm and its rate of convergence. In numerical examples, we study the multikernel version of the passive least mean squares algorithm for transfer learning to compare the performance with the classical passive version. [ABSTRACT FROM AUTHOR]

Through the combination of contraction mapping and pseudospectral method, we propose a successive approximation technique to approximate the solution of a class of regulator equations with periodic exosystems and hyperbolic zero dynamics. In this scheme, the initial points of flows on the zero-error constrained manifolds are approximated successively as the fixed point of a contractive integral mapping. Accordingly, flows are obtained by utilizing the scaled Fourier–Gauss–Radau collocation method. Appropriate error analysis, in association with both regulation error and the error resulting from the approximate solution of the center manifold equation, is provided. Our analysis shows that the regulation error becomes negligible as we start the approximation process at an adequately large order and maintain it for a proper number of iterations. [ABSTRACT FROM AUTHOR]

This article considers the optimal control problem for path-constrained switched systems with guaranteed feasibility. First, a method is proposed to reduce continuous path constraints of the switched systems into discrete abstract constraints in terms of the switch time vector and the input. Second, differentiability of the optimal value function, i.e., the cost function optimized over the input, is analyzed by using perturbation analysis theory. For a given switch time vector, the derivative of the optimal value function is proved equal to the derivative of the cost function evaluated at the optimal input provided that there is a unique optimal input in the optimal set of the cost function for continuous inputs. Third, a bilevel algorithm is proposed to find optimal switch times and the optimal input with guaranteed satisfaction of path constraints over the entire time horizon. At the inner level, the input is optimized by iteratively solving dynamic optimization problems of path-constrained switched systems with fixed switch time vector, and at the outer level, the fixed switch time vector is optimized by sequentially solving quadratic programs related to the optimal value function of switch time vectors. Fourth, it is rigorously proven that the bilevel algorithm terminates within a finite number of iterations. Finally, a numerical example is provided to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We propose a two-layer, semidecentralized algorithm to compute a local solution to the Stackelberg equilibrium problem in aggregative games with coupling constraints. Specifically, we focus on a single-leader, multiple-follower problem, and after equivalently recasting the Stackelberg game as a mathematical program with complementarity constraints (MPCC), we iteratively convexify a regularized version of the MPCC as the inner problem, whose solution generates a sequence of feasible descent directions for the original MPCC. Thus, by pursuing a descent direction at every outer iteration, we establish convergence to a local Stackelberg equilibrium. Finally, the proposed algorithm is tested on a numerical case study, a hierarchical instance of the charging coordination problem of plug-in electric vehicles. [ABSTRACT FROM AUTHOR]

This article is concerned with the multiagent optimization problem. A distributed randomized gradient-free mirror descent (DRGFMD) method is developed by introducing a randomized gradient-free oracle in the mirror descent scheme where the non-Euclidean Bregman divergence is used. The classical gradient descent method is generalized without using subgradient information of objective functions. The proposed algorithms are the first distributed non-Euclidean zeroth-order methods, which achieve an approximate $O(\frac{1}{\sqrt{T}})$ $T$ -rate of convergence, recovering the best known optimal rate of distributed nonsmooth constrained convex optimization. Moreover, a decentralized reciprocal weighted averaging (RWA) approximating sequence is first investigated, the convergence for RWA sequence is shown to hold over time-varying graph. Rates of convergence are comprehensively explored for the algorithm with RWA (DRGFMD-RWA). The technique on constructing the decentralized RWA sequence provides new insight in searching for minimizers in distributed algorithms. [ABSTRACT FROM AUTHOR]

A fundamental component of the game-theoretic approach to distributed control is the design of local utility functions. Relative to resource allocation problems that are additive over the resources, Part I showed how to design local utilities so as to maximize the associated performance guarantees (Paccagnan, et al., 2020), which we measure by the price of anarchy. The purpose of this article is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases, we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated with state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching. [ABSTRACT FROM AUTHOR]

This article studies the robustness of policy iteration in the context of continuous-time infinite-horizon linear quadratic regulator (LQR) problem. It is shown that Kleinman's policy iteration algorithm is small-disturbance input-to-state stable, a property that is stronger than Sontag's local input-to-state stability but weaker than global input-to-state stability. More precisely, whenever the error in each iteration is bounded and small, the solutions of the policy iteration algorithm are also bounded and enter a small neighborhood of the optimal solution of the LQR problem. Based on this result, an off-policy data-driven policy iteration algorithm for the LQR problem is shown to be robust when the system dynamics are subject to small additive unknown bounded disturbances. The theoretical results are validated by a numerical example. [ABSTRACT FROM AUTHOR]

This article deals with a distributed Mixed-Integer Linear Programming (MILP) setup arising in several control applications. Agents of a network aim to minimize the sum of local linear cost functions subject to both individual constraints and a linear coupling constraint involving all the decision variables. A key, challenging feature of the considered setup is that some components of the decision variables must assume integer values. The addressed MILPs are NP-hard, nonconvex, and large-scale. Moreover, several additional challenges arise in a distributed framework due to the coupling constraint, so that feasible solutions with guaranteed suboptimality bounds are of interest. We propose a fully distributed algorithm based on a primal decomposition approach and an appropriate tightening of the coupling constraint. The algorithm is guaranteed to provide feasible solutions in finite time. Moreover, asymptotic and finite-time suboptimality bounds are established for the computed solution. Monte Carlo simulations highlight the extremely low suboptimality bounds achieved by the algorithm. [ABSTRACT FROM AUTHOR]

We consider the problem of sensor and actuator (SaA) placement to minimize an infinite-horizon linear quadratic Gaussian (LQG) cost for a discrete-time Gauss–Markov system. Due to financial, topology, and bandwidth limitations, only a subset of SaAs can be selected for placement. Different from existing literature, which successively iterates partial selection to reach a suboptimal solution, this article focuses on a joint placement and encounters fundamental difficulty in the sense that joint SaA placement introduces a term in the LQG cost that is difficult to be convexified. A branch-and-bound algorithm is introduced to search for solutions to an approximate problem obtained by relaxing the Boolean constraints. By deriving a compact search space where any optimal solution belongs to or resides, we derive lower and upper bounds to the optimal solution in each subregion of the search space, and subsequently refine the search space. A suboptimal solution to the original problem is obtained from integer rounding and the optimality gap is further analyzed. Numerical examples are provided to illustrate the effectiveness of the proposed algorithm. This algorithm has significant reduction of iteration numbers compared with the brute-force enumeration especially when the number of states is not large but the number of placement choices is large. In addition, an improvement of LQG cost is obtained compared with the successively iterating partial selection methods, a canonical algorithm for SaA placement in the literature. [ABSTRACT FROM AUTHOR]

Emerging applications of control, estimation, and machine learning, from target tracking to decentralized model fitting, pose resource constraints that limit which of the available sensors, actuators, or data can be simultaneously used across time. Therefore, many researchers have proposed solutions within discrete optimization frameworks where the optimization is performed over finite sets. By exploiting notions of discrete convexity, such as submodularity, the researchers have been able to provide scalable algorithms with provable suboptimality bounds. In this article, we consider such problems but in adversarial environments, where in every step a number of the chosen elements in the optimization is removed due to failures/attacks. Specifically, we consider for the first time a sequential version of the problem that allows us to observe the failures and adapt, while the attacker also adapts to our response. We call the novel problem robust sequential submodular maximization (RSM). Generally, the problem is computationally hard and no scalable algorithm is known for its solution. However, in this article, we propose robust and adaptive maximization (RAM), the first scalable algorithm. RAM runs in an online fashion, adapting in every step to the history of failures. Also, it guarantees a near-optimal performance, even against any number of failures among the used elements. Particularly, RAM has both provable per-instance a priori bounds and tight and/or optimal a posteriori bounds. Finally, we demonstrate RAM's near-optimality in simulations across various application scenarios, along with its robustness against several failure types, from worst-case to random. [ABSTRACT FROM AUTHOR]

In this article, we describe an approximate dynamic programming (ADP) approach to compute lower bounds on the optimal value function for a discrete time, continuous space, and infinite horizon setting. The approach iteratively constructs a family of lower bounding approximate value functions by using the so-called Bellman inequality. The novelty of our approach is that, at each iteration, we aim to compute an approximate value function that maximizes the point-wise maximum taken with the family of approximate value functions computed thus far. This leads to a nonconvex objective, and we propose a gradient ascent algorithm to find stationary points by solving a sequence of convex optimization problems. We provide convergence guarantees for our algorithm and an interpretation for how the gradient computation relates to the state-relevance weighting parameter appearing in related ADP approaches. We demonstrate through numerical examples that, when compared to the existing approaches, the algorithm we propose computes tighter suboptimality bounds with comparable computation time. [ABSTRACT FROM AUTHOR]

Despite the increasing interest in multiagent reinforcement learning (MARL) in multiple communities, understanding its theoretical foundation has long been recognized as a challenging problem. In this article, we address this problem by providing a finite-sample analysis for decentralized batch MARL. Specifically, we consider a type of mixed MARL setting with both cooperative and competitive agents, where two teams of agents compete in a zero-sum game setting, while the agents within each team collaborate by communicating over a time-varying network. This setting covers many conventional MARL settings in the literature. We then develop batch MARL algorithms that can be implemented in a decentralized fashion, and quantify the finite-sample errors of the estimated action-value functions. Our error analysis captures how the function class, the number of samples within each iteration, and the number of iterations determine the statistical accuracy of the proposed algorithms. Our results, compared to the finite-sample bounds for single-agent reinforcement learning, involve additional error terms caused by decentralized computation, which is inherent in our decentralized MARL setting. This article provides the first finite-sample analysis for batch MARL, a step toward rigorous theoretical understanding of general MARL algorithms in the finite-sample regime. [ABSTRACT FROM AUTHOR]

This article compiles several aspects of the dynamics of stochastic approximation algorithms with Markov iterate-dependent noise when the iterates are not known to be stable beforehand. We achieve the same by extending the lock-in probability (i.e., the probability of convergence of the iterates to a specific attractor of the limiting ordinary differential equation (o.d.e.) given that the iterates are in its domain of attraction after a sufficiently large number of iterations (say) $n_0$) framework to such recursions. Specifically, with the more restrictive assumption of Markov iterate-dependent noise supported on a bounded subset of the Euclidean space, we give a lower bound for the lock-in probability. We use these results to prove almost sure convergence of the iterates to the specified attractor when the iterates satisfy an asymptotic tightness condition. The novelty of our approach is that if the state space of the Markov process is compact, we prove almost sure convergence under much weaker assumptions compared to the work by Andrieu et al., which solves the general state-space case under much restrictive assumptions by providing sufficient conditions for stability of the iterates. We also extend our single-timescale results to the case where there are two separate recursions over two different timescales. This, in turn, is shown to be useful in analyzing the tracking ability of general adaptive algorithms. Additionally, we show that our results can be used to derive a sample complexity estimate of such recursions, which then can be used for step-size selection. [ABSTRACT FROM AUTHOR]

We consider the stochastic generalized Nash equilibrium problem (SGNEP) with expected-value cost functions. Inspired by Yi and Pavel (2019), we propose a distributed generalized Nash equilibrium seeking algorithm based on the preconditioned forward–backward operator splitting for SGNEPs, where, at each iteration, the expected value of the pseudogradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of the proposed algorithm if the pseudogradient mapping is restricted (monotone and) cocoercive. [ABSTRACT FROM AUTHOR]

The objective of this article is to introduce a novel data-driven iterative linear quadratic (LQ) control method for solving a class of nonlinear optimal tracking problems. Specifically, an algorithm is proposed to approximate the Q-factors arising from LQ stochastic optimal tracking problems. This algorithm is then coupled with iterative LQ-methods for determining local solutions to nonlinear optimal tracking problems in a purely data-driven setting. Simulation results highlight the potential of this method for field applications. [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]

We study gradient methods for solving distributed convex optimization problems over a network when the communication bandwidth between the nodes is limited, and so information that is exchanged between the nodes must be quantized. This imperfect communication poses a fundamental challenge, and if not properly accounted for may prevent the convergence of these algorithms. Our first contribution in this article is to propose a modified consensus-based gradient method for solving such problems using random (dithered) quantization. This algorithm can be interpreted as a distributed variant of a two-time-scale stochastic approximation algorithm. We then study the convergence and derive upper bounds on the rates of convergence of the proposed method as a function of the bandwidth available between the nodes and the underlying network topology for both convex and strongly convex objective functions. Our results complement existing literature, where such convergence and explicit formulas of the convergence rates are missing. Finally, we provide numerical simulations to compare the convergence properties of the distributed gradient methods with and without quantization for solving the well-known regression problems over networks, for both quadratic and absolute loss functions. [ABSTRACT FROM AUTHOR]

Distributed bandit online convex optimization with time-varying coupled inequality constraints is considered, motivated by a repeated game between a group of learners and an adversary. The learners attempt to minimize a sequence of global loss functions and at the same time satisfy a sequence of coupled constraint functions, where the constraints are coupled across the distributed learners at each round. The global loss and the coupled constraint functions are the sum of local convex loss and constraint functions, respectively, which are adaptively generated by the adversary. The local loss and constraint functions are revealed in a bandit manner, i.e., only the values of loss and constraint functions are revealed to the learners at the sampling instance, and the revealed function values are held privately by each learner. Both one- and two-point bandit feedback are studied with the two corresponding distributed bandit online algorithms used by the learners. We show that sublinear expected regret and constraint violation are achieved by these two algorithms, if the accumulated variation of the comparator sequence also grows sublinearly. In particular, we show that $\mathcal {O}(T^{\theta })$ expected static regret and $\mathcal {O}(T^{7/4-\theta })$ constraint violation are achieved in the one-point bandit feedback setting, and $\mathcal {O}(T^{\max \lbrace \kappa,1-\kappa \rbrace })$ expected static regret and $\mathcal {O}(T^{1-\kappa /2})$ constraint violation in the two-point bandit feedback setting, where $\theta \in (3/4,5/6]$ and $\kappa \in (0,1)$ are user-defined tradeoff parameters. Finally, the tightness of the theoretical results is illustrated by numerical simulations of a simple power grid example, which also compares the proposed algorithms to algorithms existing in the literature. [ABSTRACT FROM AUTHOR]

Economic model predictive control (EMPC) has recently become popular because of its ability to control constrained nonlinear systems while explicitly optimizing a prescribed performance criterion. Large performance gains have been reported for many applications and closed-loop stability has been recently investigated. However, computational performance still remains an open issue and only few contributions have proposed real-time algorithms tailored to EMPC. We perform a step towards computationally cheap algorithms for EMPC by proposing a new positive-definite Hessian approximation which does not hinder fast convergence and is suitable for being used within the real-time iteration (RTI) scheme. We provide two simulation examples to demonstrate the effectiveness of RTI-based EMPC relying on the proposed Hessian approximation. [ABSTRACT FROM AUTHOR]

In this article, we introduce a class of novel distributed algorithms for solving stochastic big-data convex optimization problems over directed graphs. In the addressed set-up, the dimension of the decision variable can be extremely high and the objective function can be nonsmooth. The general algorithm consists of two main steps: a consensus step and an update on a single block of the optimization variable, which is then broadcast to neighbors. Three special instances of the proposed method, involving particular problem structures, are then presented. In the general case, the convergence of a dynamic consensus algorithm over random row stochastic matrices is shown. Then, the convergence of the proposed algorithm to the optimal cost is proven in expected value. Exact convergence is achieved when using diminishing (local) stepsizes, whereas approximate convergence is attained when constant stepsizes are employed. The convergence rate is shown to be sublinear and an explicit rate is provided in the case of constant stepsizes. Finally, the algorithm is tested on a distributed classification problem, first on synthetic data and, then, on a real, high-dimensional, text dataset. [ABSTRACT FROM AUTHOR]

Asynchronous stochastic approximations (SAs) are an important class of model-free algorithms, tools, and techniques that are popular in multiagent and distributed control scenarios. To counter Bellman's curse of dimensionality, such algorithms are coupled with function approximations. Although the learning/control problem becomes more tractable, function approximations affect stability and convergence. In this article, we present verifiable sufficient conditions for stability and convergence of asynchronous SAs with biased approximation errors. The theory developed herein is used to analyze policy gradient methods and noisy value iteration schemes. Specifically, we analyze the asynchronous approximate counterparts of the policy gradient (A2PG) and value iteration (A2VI) schemes. It is shown that the stability of these algorithms is unaffected by biased approximation errors, provided that they are asymptotically bounded. With respect to convergence (of A2VI and A2PG), a relationship between the limiting set and the approximation errors is established. Finally, experimental results that support the theory are presented. [ABSTRACT FROM AUTHOR]

This article studies a class of multirobot coordination problems where a team of robots aim to reach their goal regions with minimum time and avoid collisions with obstacles and other robots. A novel numerical algorithm is proposed to identify the Pareto optimal solutions where no robot can unilaterally reduce its traveling time without extending others’. The consistent approximation of the algorithm in the epigraphical profile sense is guaranteed using set-valued numerical analysis. Experiments on an indoor multirobot platform and computer simulations show the anytime property of the proposed algorithm, i.e., it is able to quickly return a feasible control policy that safely steers the robots to their goal regions and it keeps improving policy optimality if more time is given. [ABSTRACT FROM AUTHOR]

This article studies the constrained switching (linear) system which is a discrete-time switched linear system whose switching sequences are constrained by a deterministic finite automaton. The stability of a constrained switching system is characterized by its constrained joint spectral radius that is known to be difficult to compute or approximate. Using the semitensor product of matrices, the matrix-form expression of a constrained switching system is shown to be equivalent to that of a lifted arbitrary switching system. Then, the constrained joint/generalized spectral radius of a constrained switching system is proven to be equal to the joint/generalized spectral radius of its lifted arbitrary switching system which can be approximated by off-the-shelf algorithms. [ABSTRACT FROM AUTHOR]

Controlled interacting particle systems such as the ensemble Kalman filter (EnKF) and the feedback particle filter (FPF) are numerical algorithms to approximate the solution of the nonlinear filtering problem in continuous time. The distinguishing feature of these algorithms is that the Bayesian update step is implemented using a feedback control law. It has been noted in the literature that the control law is not unique. This is the main problem addressed in this article. To obtain a unique control law, the filtering problem is formulated here as an optimal transportation problem. An explicit formula for the (mean-field type) optimal control law is derived in the linear Gaussian setting. Comparisons are made with the control laws for different types of EnKF algorithms described in the literature. Via empirical approximation of the mean-field control law, a finite- $N$ controlled interacting particle algorithm is obtained. For this algorithm, the equations for empirical mean and covariance are derived and shown to be identical to the Kalman filter. This allows strong conclusions on convergence and error properties based on the classical filter stability theory for the Kalman filter. It is shown that, under certain technical conditions, the mean squared error converges to zero even with a finite number of particles. A detailed propagation of chaos analysis is carried out for the finite- $N$ algorithm. The analysis is used to prove weak convergence of the empirical distribution as $N\rightarrow \infty$. For a certain simplified filtering problem, analytical comparison of the mse with the importance sampling-based algorithms is described. The analysis helps explain the favorable scaling properties of the control-based algorithms reported in several numerical studies in recent literature. [ABSTRACT FROM AUTHOR]

In this article the problem of ellipsoidal bounding of convex set-valued data, where the convex set is obtained by the p-sum of finitely many ellipsoids, for any real p ≥ 1 is studied. The notion of p-sum appears in the Brunn–Minkowski–Firey theory in convex analysis, and generalizes several well-known set-valued operations, such as the Minkowski sum of the summand convex sets (here, ellipsoids). We derive an outer ellipsoidal parameterization for the p-sum of a given set of ellipsoids, and compute the tightest such parameterization for two optimality criteria: minimum trace and minimum volume. For such optimal parameterizations, several known results in the system-control literature are recovered as special cases of our general formula. For the minimum volume criterion, our analysis leads to a fixed point recursion over a scalar that parameterizes the shape matrix of the outer ellipsoid. This recursion is proved to be contractive, and found to converge fast in practice. We apply these results to compute the forward reach sets for a linear control system subject to different convex set-valued uncertainty models for the initial condition and control, generated by varying p ∈ [1,∞]. Our numerical results show that the proposed fixed point algorithm offers more than two orders of magnitude speed-up in computational time for p = 1, compared to the existing semidefinite programming approach without significant effect on the numerical accuracy. For p > 1, the reach set computation results reported here are novel. Our results are expected to be useful in real-time safety critical applications, such as decision making, for collision avoidance of autonomous vehicles, where the computational time scale for reach set calculation needs to be much smaller than the vehicular dynamics time scale. [ABSTRACT FROM AUTHOR]

This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact minimizer in the presence of the nonsmooth term. Moreover, for the more general class of problems with agent specific nonsmooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and nonsmooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly convex objectives and different local non smooth terms. [ABSTRACT FROM AUTHOR]

We study distributed big-data nonconvex optimization in multiagent networks. We consider the (constrained) minimization of the sum of a smooth (possibly) nonconvex function, i.e., the agents’ sum-utility, plus a convex (possibly) nonsmooth regularizer. Our interest is on big-data problems in which there is a large number of variables to optimize. If treated by means of standard distributed optimization algorithms, these large-scale problems may be intractable due to the prohibitive local computation and communication burden at each node. We propose a novel distributed solution method where, at each iteration, agents update in an uncoordinated fashion only one block of the entire decision vector. To deal with the nonconvexity of the cost function, the novel scheme hinges on successive convex approximation techniques combined with a novel blockwise perturbed push-sum consensus protocol, which is instrumental to perform local block-averaging operations and tracking of gradient averages. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Finally, numerical results show the effectiveness of the proposed algorithm and highlight how the block dimension impacts on the communication overhead and practical convergence speed. [ABSTRACT FROM AUTHOR]

Given a linear dynamical system affected by stochastic noise, we consider the problem of selecting an optimal set of sensors (at design time) to minimize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter, subject to certain selection budget constraints. We show the fundamental result that there is no polynomial-time constant-factor approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity (or supermodularity) of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering. We then study the problem of attacking (i.e., removing) a set of installed sensors, under predefined attack budget constraints, to maximize the trace of the steady-state a priori or a posteriori error covariance of the Kalman filter. Again, we show that there is no polynomial-time constant-factor approximation algorithm for this problem and show specifically that greedy algorithms can perform arbitrarily poorly. [ABSTRACT FROM AUTHOR]

This article addresses the problem of seeking a common fixed point for a finite collection of nonexpansive operators over time-varying multi-agent networks in real Hilbert spaces. Each operator is assumed to be only privately and approximately known to each individual agent, and all agents need to cooperate to solve this problem by local communications over time-varying networks. To handle this problem, inspired by the centralized inexact Krasnoselski –Mann iteration, we propose a distributed algorithm, called distributed inexact averaged operator algorithm (DIO). It is shown that the DIO can converge weakly to a common fixed point of the family of nonexpansive operators. Moreover, under the assumption that all operators and their own fixed point sets are (boundedly) linearly regular, it is proved that the distributed averaged operator algorithm converges with a rate O(γlog16(4k)) for some constant γ ∈ (0,1), where k is the iteration number. To reduce computational complexity, a scenario, where only a random part of coordinates of each operator is computed at each iteration, is further considered. In this case, a corresponding algorithm, named distributed block-coordinate inexact averaged operator algorithm, is developed. The algorithm is proved to be weakly convergent to a common fixed point of the group of considered operators almost surely, and, with the extra assumption of (bounded) linear regularity, the distributed block-coordinate averaged operator algorithm is convergent in the mean square sense with a rate O(ηlog4(4k)) for some constant η ∈ (0,1). Furthermore, it is shown that the same convergence rates can still be guaranteed under a more relaxed (bounded) power regularity condition. A couple of examples are finally presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

It is well known that the nonlinear filtering (NLF) problem has important applications in both military and civil industries. The central question is to solve the posterior conditional density function of the states, which satisfies the Kushner or the Duncan–Mortensen–Zakai (DMZ) equation after suitable change of probability measure. In this article, we shall follow the so-called Yau–Yau's algorithm to split the solution of the DMZ equation into on- and off-line part, where the off-line part is to solve the forward Kolmogorov equation (FKE) with the initial conditions to be the orthonormal bases in some suitable function space. Instead of the generalized Hermite function investigated by the second and the third author of this article, we shall explore the generalized Legendre polynomials. The Legendre spectral method (LSM) is used to numerically solve the FKE. Under certain conditions, the convergence rate of LSM is twice faster than that of the Hermite spectral method. Two two-dimensional numerical experiments of NLF problems (time-invariant and time-varying cases) have been numerically solved to illustrate the feasibility of our algorithm. Our algorithm outperforms the extended Kalman Filter and particle filter in both real-time manner and accuracy. [ABSTRACT FROM AUTHOR]

Opacity is an important information-flow security property in the analysis of cyber-physical systems. It captures the plausible deniability of the system's secret behavior in the presence of an intruder that may access the information flow. Existing works on opacity only consider nonmetric systems by assuming that the intruder can always distinguish between two different outputs precisely. In this article, we extend the concept of opacity to systems whose output sets are equipped with metrics. Such systems are widely used in the modeling of many real-world systems whose measurements are physical signals. A new concept called approximate opacity is proposed in order to quantitatively evaluate the security guarantee level with respect to the measurement precision of the intruder. Then, we propose a new simulation-type relation, called approximate opacity-preserving simulation relation, which characterizes how close two systems are in terms of the satisfaction of approximate opacity. This allows us to verify approximate opacity for large-scale, or even infinite, systems using their abstractions. We also discuss how to construct approximate opacity-preserving symbolic models for a class of discrete-time control systems. Our results extend the definitions and analysis techniques for opacity from nonmetric systems to metric systems. [ABSTRACT FROM AUTHOR]

We investigate a linear-quadratic-Gaussian (LQG) control and sensing codesign problem, where one jointly designs sensing and control policies. We focus on the realistic case where the sensing design is selected among a finite set of available sensors, where each sensor is associated with a different cost (e.g., power consumption). We consider two dual problem instances: sensing-constrained LQG control, where one maximizes a control performance subject to a sensor cost budget, and minimum-sensing LQG control, where one minimizes a sensor cost subject to performance constraints. We prove that no polynomial time algorithm guarantees across all problem instances a constant approximation factor from the optimal. Nonetheless, we present the first polynomial time algorithms with per-instance suboptimality guarantees. To this end, we leverage a separation principle, which partially decouples the design of sensing and control. Then, we frame LQG codesign as the optimization of approximately supermodular set functions; we develop novel algorithms to solve the problems; and we prove original results on the performance of the algorithms and establish connections between their suboptimality and control-theoretic quantities. We conclude the article by discussing two applications, namely, sensing-constrained formation control and resource-constrained robot navigation. [ABSTRACT FROM AUTHOR]

This article develops a fully decentralized multiagent algorithm for policy evaluation. The proposed scheme can be applied to two distinct scenarios. In the first scenario, a collection of agents have distinct datasets gathered by following different behavior policies (none of which is required to explore the full state space) in different instances of the same environment and they all collaborate to evaluate a common target policy. The network approach allows for efficient exploration of the state space and allows all agents to converge to the optimal solution even in situations where neither agent can converge on its own without cooperation. The second scenario is that of multiagent games, in which the state is global and rewards are local. In this scenario, agents collaborate to estimate the value function of a target team policy. The proposed algorithm combines off-policy learning, eligibility traces, and linear function approximation. The proposed algorithm is of the variance-reduced kind and achieves linear convergence with O(1) memory requirements. The linear convergence of the algorithm is established analytically and simulations are used to illustrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

In this article, we present two algorithms for identification of continuous-time linear time-invariant systems in frequency domain. These algorithms are constructed in terms of continuous rational orthogonal basis functions. First, a two-stage algorithm is developed through one-by-one selection of poles for the basis functions, and such consecutive selection is easy to realize. Next, a direct algorithm is proposed to select poles for the rational orthogonal basis functions. Different poles result in different bases and these selections guarantee that better approximations can be reached. For different systems, there are different sequences of poles selected for basis functions, which shows the adaptivity of the proposed algorithms. A numerical example is given to show that the proposed algorithms are useful. Also, in this example, comparison is made with the method that uses rational orthogonal basis functions in which all poles of the basis functions are true poles of the original system. [ABSTRACT FROM AUTHOR]

This article considers a distributed Nash equilibrium seeking problem, where the players only have partial access to other players’ actions, such as their neighbors’ actions. Thus, the players are supposed to communicate with each other to estimate other players’ actions. To solve the problem, a leader–following consensus gradient-free distributed Nash equilibrium seeking algorithm is proposed. This algorithm utilizes only the measurements of the player’ local cost function without the knowledge of its explicit expression or the requirement on its smoothness. Hence, the algorithm is gradient-free during the entire updating process. Moreover, the analysis on the convergence of the Nash equilibrium is studied for the algorithm with both diminishing and constant step-sizes, respectively. Specifically, in the case of diminishing step-size, it is shown that the players’ actions converge to the Nash equilibrium almost surely, while in the case of fixed step-size, the convergence to the neighborhood of the Nash equilibrium is achieved. The performance of the proposed algorithm is verified through numerical simulations. [ABSTRACT FROM AUTHOR]

This article proposes a novel information-theoretic joint probabilistic data association filter for tracking unknown number of targets. The proposed information-theoretic joint probabilistic data association algorithm is obtained by the minimization of a weighted reverse Kullback–Leibler divergence to approximate the posterior Gaussian mixture probability density function. Theoretical analysis of mean performance and error covariance performance with ideal detection probability is presented to provide insights of the proposed approach. Extensive empirical simulations are undertaken to validate the performance of the proposed multitarget tracking algorithm. [ABSTRACT FROM AUTHOR]

In this article, we propose a region-based self-triggered control (STC) scheme for nonlinear systems. The state space is partitioned into a finite number of regions, each of which is associated to a uniform interevent time. The controller, at each sampling time instant, checks to which region does the current state belong, and correspondingly decides the next sampling time instant. To derive the regions along with their corresponding interevent times, we use approximations of isochronous manifolds, a notion first introduced in Anta and Tabuada (2012). This article addresses some theoretical issues of Anta and Tabuada (2012) and proposes an effective computational approach that generates approximations of isochronous manifolds, thus enabling the region-based STC scheme. The efficiency of both our theoretical results and the proposed algorithm is demonstrated through simulation examples. [ABSTRACT FROM AUTHOR]

We develop a stochastic approximation-type algorithm to solve finite state/action, infinite-horizon, risk-aware Markov decision processes. Our algorithm has two loops. The inner loop computes the risk by solving a stochastic saddle-point problem. The outer loop performs Q-learning to compute an optimal risk-aware policy. Several widely investigated risk measures (e.g., conditional value-at-risk, optimized certainty equivalent, and absolute semideviation) are covered by our algorithm. Almost sure convergence and the convergence rate of the algorithm are established. For an error tolerance ε > 0 for optimal Q-value estimation gap and learning rate k ∈ (1/2,1], the overall convergence rate of our algorithm is Ω((ln(1/δε)/ε2)1/k + (ln(1/ε))1/(1−k)) with probability at least 1−ε. [ABSTRACT FROM AUTHOR]

In this article, we examine a novel generic network cost minimization problem, in which every node has a local decision vector to optimize. Each node incurs a cost associated with its decision vector, while each link incurs a cost related to the decision vectors of its two end nodes. All nodes collaborate to minimize the overall network cost. The formulated network cost minimization problem has broad applications in distributed signal processing and control, in which the notion of link costs often arises. To solve this problem in a decentralized manner, we develop a distributed variant of Newton's method, which possesses faster convergence than alternative first-order optimization methods such as gradient descent and alternating direction method of multipliers. The proposed method is based on an appropriate splitting of the Hessian matrix and an approximation of its inverse, which is used to determine the Newton step. Global linear convergence of the proposed algorithm is established under several standard technical assumptions on the local cost functions. Furthermore, analogous to classical centralized Newton's method, a quadratic convergence phase of the algorithm over a certain time interval is identified. Finally, numerical simulations are conducted to validate the effectiveness of the proposed algorithm and its superiority over other first-order methods, especially when the cost functions are ill-conditioned. Complexity issues of the proposed distributed Newton's method and alternative first-order methods are also discussed. [ABSTRACT FROM AUTHOR]

Temporal logic provides a rigorous and expressive way to model specifications for cyber-physical systems (CPS). Such systems, which are playing increasingly important roles in various domains, are also subject to malicious attacks initiated by intelligent adversaries. Malicious attacks may prevent the system from satisfying the desired specification. In this article, we introduce a control synthesis method to minimize deviations from the desired specification due to adversaries. We consider the scenario where the adversary has limited capability of observing the controller's strategy. We synthesize a minimum violation control strategy for a finite-state stochastic game under cosafe linear temporal logic constraints. We formulate a mixed-integer nonlinear program for computing the optimal controller strategy and present two algorithms. First, we propose an exact algorithm that computes the optimal control strategy with probability one but without guarantees on the convergence rate. Second, we present an approximate algorithm that computes a suboptimal control strategy. The approximate algorithm converges faster compared to the exact algorithm; however, it only returns an optimal solution when the adversary has full observation over the controller's strategy. A numerical case study is presented to evaluate the proposed framework. [ABSTRACT FROM AUTHOR]

In this article, we consider an online distributed composite optimization problem over a time-varying multiagent network that consists of multiple interacting nodes, where the objective function of each node consists of two parts: a loss function that changes over time and a regularization function. This problem naturally arises in many real-world applications ranging from wireless sensor networks to signal processing. We propose a class of online distributed optimization algorithms that are based on approximate mirror descent, which utilizes the Bregman divergence as a distance-measuring function that includes the Euclidean distances as a special case. We consider two standard information feedback models when designing the algorithms, that is, full-information feedback and bandit feedback. For the full-information feedback model, the first algorithm attains an average regularized regret of order O(1/√T) with the total number of rounds T. The second algorithm, which only requires the information of the values of the loss function at two predicted points instead of the gradient information, achieves the same average regularized regret as that of the first algorithm. Simulation results of a distributed online regularized linear regression problem are provided to illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]