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]