The paper is concerned with stochastic approximation algorithms. Our main effort is focused on recently developed set-valued stochastic approximation methods. We begin with a brief introduction on stochastic approximation. Next, recent results are reviewed. Then the rest of the paper concentrates on applications of stochastic applications of set-valued problems.

This paper presents a novel class of cyber security models based on SIR-type formulation. Our effort is on investigating optimal impulse controls arising from a cluster owner under exogenous cyber-attacks. We utilize the SIRS model from epidemiology to represent the spread of cyber-attacks within the cluster and evaluate the impact of protective measures. Within this framework, we determine the optimal defense strategy against effective hacking by formulating and solving a stochastic control problem with optimal switching. By employing dynamic programming principles, we derive a system of quasi-variational inequalities. Due to the inherent nonlinearity and complexity, a closed-form solution is not possible. We use a hybrid deep learning method to approximate the solution by simulating the optimal protection strategies. Finally, the effectiveness of the proposed hybrid deep learning method is validated by comparing it with the deep Galerkin method.

We focus on exponential stability of stochastic functional differential equations with delayed impulses. One of the notable characteristics of this paper is the dependence of both the given impulsive-free stochastic differential equation and impulsive perturbations on the past state of the system. Compared with the existing literature, we introduce new criteria for establishing exponential stability in mean square and almost surely. We provide two examples in this paper to showcase the effectiveness of our criteria.

This paper develops control design algorithms to achieve almost sure stabilization for Markovian randomly switched linear systems (RSLSs) involving uncontrollable subsystems. Under the conditions of irreducible and aperiodic Markovian switching processes, a controller design method is introduced that utilizes the stationary distribution of the Markov Chain (MC) and stabilizes the overall system almost surely. This proposed method addresses the intricacies arising from uncontrollable subsystems within the context of Markovian RSLSs, and offers a constructive solution for achieving system stability by coordinating subsystem controllers. Almost sure stability of the closed-loop system is established. In addition, a simulation case study on an IEEE 5-Bus system illustrates model development, controller design procedures, and convergence properties.

This paper studies the impact of stochastic load variations on distributed optimal load tracking and allocation (OLTA) problems in cyber-physical DC microgrids (MGs) for transportation electrification. Without load variations, the distributed optimization strategies developed in our earlier work can achieve convergence to global optimal solutions in a multi-objective optimization that balances fair load allocation and power loss reduction. Under persistent stochastic load variations, this paper develops distributed optimal strategies to track time-varying loads under noisy observations and establishes their convergence properties and error bounds. The limiting behavior of the errors characterizes the fundamental impact of the step size on irreducible errors due to conflict between attenuating observation noises and tracking load changes. Optimality conditions and algorithms for selecting the optimal step size are introduced to guide step size selection in practical applications. Simulation studies on real-world systems demonstrate the effectiveness of the proposed algorithms and validate the theoretical results.

Inverse reinforcement learning (IRL) aims to estimate the reward function of optimizing agents by observing their response (estimates or actions). This paper considers IRL when noisy estimates of the gradient of a reward function generated by multiple stochastic gradient agents are observed. We present a generalized Langevin dynamics algorithm to estimate the reward function $R(\theta)$; specifically, the resulting Langevin algorithm asymptotically generates samples from the distribution proportional to $\exp(R(\theta))$. The proposed adaptive IRL algorithms use kernel-based passive learning schemes. We also construct multi-kernel passive Langevin algorithms for IRL which are suitable for high dimensional data. The performance of the proposed IRL algorithms are illustrated on examples in adaptive Bayesian learning, logistic regression (high dimensional problem) and constrained Markov decision processes. We prove weak convergence of the proposed IRL algorithms using martingale averaging methods. We also analyze the tracking performance of the IRL algorithms in non-stationary environments where the utility function $R(\theta)$ has a hyper-parameter that jump changes over time as a slow Markov chain which is not known to the inverse learner. In this case, martingale averaging yields a Markov switched diffusion limit as the asymptotic behavior of the IRL algorithm.

This article considers a general model of distributed convex optimization with possibly local constraints, coupled equality constraints, and coupled inequality constraints, where the coupled equality constraints are affine and the coupled inequality constraints can be nonaffine. To solve this problem, we present two algorithms. The first algorithm is similar to a dual subgradient algorithm that requires a center node in the network. The main advantage of the first algorithm is that it achieves the optimal convergence rate O([1/√k]) . Moreover, it does not require additional treatment for the primal recovery. These merits are achieved by using an iterate-averaging feedback technique on the basis of the dual subgradient method. The second algorithm further removes the requirement of a center node by employing consensus tracking iterates. As a result, the second algorithm is fully distributed at the price of achieving an O([lnk/√k]) convergence rate.

The mission-critical nature of wireless networked sensing and control (WSC) systems, such as the control of industrial plants, requires stringent real-time delivery of packets. Due to inherent dynamics and uncertainties in wireless communication, real-time communication guarantees are probabilistic in nature. In this paper, a probabilistic framework is therefore proposed for per-packet real-time delivery guarantee. The notion of real-time in this paper differs from the existing work in the sense that it ensures, in an execution history of arbitrary length, every packet is successfully delivered before its deadline with a probability no less than a user-specified threshold (e.g., 99%). The framework has several novel building blocks: First, “R3 (requirement-reliability-resource) mapping” translates the upper layer probabilistic real-time communication requirement, and the lower layer links reliability into the resource (i.e., optimal number of transmission opportunities) reserved for each packet. Second, “EDF (earliest deadline first) based real-time scheduling” as well as the “admission test” and “traffic load optimization” maximize system utility while satisfying per-packet real-time communication requirements. The proposed admission test is proved to be both sufficient and necessary, and the simulation results show that the proposed framework ensures probabilistic per-packet real-time communication.

This paper introduces new models to describe pedestrian crowd dynamics in a typical unidirectional environment, such as corridors, pathways, and railway platforms. Pedestrian movements are represented in a two-dimensional space that is further divided into narrow virtual lanes. Consequently, pedestrians either move in a lane following each other or change lanes, when it is desirable. Within this framework, the motions of pedestrians are modeled as a two-dimensional and two-time-scale hybrid system. A pedestrian's movement along the crowd direction is labeled as the x direction and modeled by a real-valued process, a solution of a differential equation in continuous time, the lane change is labeled as the y direction. In contrast to the x direction dynamics, the movements in the y direction only happen at some time epoch. Although the movements are still on the same time horizon as the x direction movements, with a slight abuse of notation and for simplicity and convenience, we use discrete time as the time indicator, and model the movements by a recursive equation taking values in a finite set. Under common assumptions of crowd movements, we prove that the crowd movements in the x direction will converge to a uniform distance distribution and the convergence rate is exponential. Furthermore, by using a velocity-distance function to represent the common crowd and traffic congestion scenarios, we show that all pedestrians will asymptotically move with a uniform group speed. In the y direction, when pedestrians naturally wish to change to faster lanes, we show that the numbers in each virtual lanes converge to a balanced distribution and hence achieves asymptotic consensus as shown typically in a crowd behavior. Stability and convergence analysis is carried out rigorously by using properties of circular matrices, stability of networked systems, and stochastic approximations. Simulation studies are used to demonstrate the main properties of our modeling approach and establish its usefulness in representing pedestrian dynamics.

Predictable link reliability is required for wireless networked control, yet co-channel interference remains a major source of uncertainty in wireless link reliability. Formulated specifically for distributed predictable control of co-channel interference, the physical-ratio-K (PRK) interference model integrates the protocol model's locality and the physical model's high fidelity while addressing their weaknesses, and it transforms interference control in arbitrary networks to a problem involving coordination between close-by nodes only. To apply the PRK model in real-world settings, we design protocol PRKS that addresses the challenges of model instantiation and protocol signaling in PRK-based scheduling. In particular, PRKS uses a control-theoretic approach to instantiate the PRK model in dynamic uncertain networks, uses local signal maps to address the challenges of large interference range and anisotropic asymmetric wireless communication, and leverages the different timescales of PRK model adaptation and data transmission to decouple protocol signaling from data transmission. Through testbed-based measurement study, we show that, unlike existing scheduling protocols where link reliability is unpredictable and the ratio of links whose reliability meets application requirements can be as low as 0%, PRKS enables predictably high link reliability (e.g., 95%) for all the links in different network and environmental conditions without a priori knowledge of these conditions. Through local distributed coordination, PRKS also achieves a channel spatial reuse very close to what is enabled by the state-of-the-art centralized scheduler while ensuring the required link reliability. By ensuring the required link reliability in scheduling, PRKS also enables a lower communication delay and a higher network throughput than existing scheduling protocols.

Predictable link reliability is required for wireless networked control, yet co-channel interference remains a major source of uncertainty in wireless link reliability. Integrating the protocol model's locality and the physical model's high fidelity, the physical-ratio-K (PRK) interference model has the potential to enable distributed, predictable control of co-channel interference and thus predictable link reliability. To realize the potential of the PRK model, we design protocol PRKS that addresses the challenge of instantiating the PRK model in the presence of network and environmental uncertainties. Formulating the PRK-model-instantiation problem as a minimum-variance regulation control problem, in particular, PRKS uses a control-theoretic approach to instantiating the PRK model on the fly. Through testbed-based measurement study, we show that, unlike existing scheduling protocols where link reliability is unpredictable and the ratio of links whose reliability meets application requirements can be as low as 0%, PRKS enables predictably high link reliability (e.g., 95%) for all the links in different network and environmental conditions without a priori knowledge of these conditions. Through local, distributed coordination, PRKS also achieves a channel spatial reuse very close to what is enabled by the state-of-the-art centralized scheduler while ensuring the required link reliability. By ensuring the required link reliability in scheduling, PRKS also enables a lower communication delay and a higher network throughput than existing scheduling protocols.

Packet loss in block erasure channels creates a randomly switching networked system that impacts control performance significantly. This paper employs safety of highway vehicle platoons as a platform to study such an impact. By autonomous intervehicle coordination, a platoon can potentially enhance safety, improve highway utility, increase fuel economy, and reduce emission. By comparing different information structures that utilize radar distance sensors and wireless communication channels, we characterize some intrinsic relationships between communication resources and control performance. The findings of this paper provide useful guidelines in communication resource allocations and vehicle coordination in vehicle safety problems.

Packet loss in block erasure channels creates a randomly switching networked system that impacts control performance significantly. This paper employs safety of highway vehicle platoons as a platform to study such impact. By autonomous inter-vehicle coordination, a platoon can potentially enhance safety, improve highway utility, increase fuel economy, and reduce emission. By comparing different information structures which utilize radar distance sensors and wireless communication channels, we are able to characterize some intrinsic relationships between communication resources and control performance. The findings of this paper provide useful guidelines on communication resource allocations and vehicle coordinations in vehicle safety problems.

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network; the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. Two results are presented. First, motivated by social network applications, the asymptotic behavior of the degree distribution is analyzed. Second, a stochastic approximation algorithm is presented to track empirical degree distribution as it evolves over time. The tracking performance of the algorithm is analyzed in terms of mean square error and a functional central limit theorem is presented for the asymptotic tracking error. Also, a Hilbert-space-valued stochastic approximation algorithm that tracks a Markov-modulated probability mass function with support on the set of nonnegative integers is analyzed.

Internet traffic often exhibits a structure with rich high-order statistical properties like self-similarity and long-range dependency (LRD). This greatly complicates the problem of server performance modeling and optimization. Existing tools like queuing models in most cases only hold in mean value analysis under the assumption of simplified traffic structures. In this paper, we present a filter model to characterize the relationship among the factors of server capacity, request scheduling, and service quality for general input traffic. By the model, a server scheduler operates as an finite-duration impulse response (FIR) filter that transforms request processes into workload processes with the objective of minimizing load variation or overload probability, and meanwhile, without violating request response deadlines as defined in service-level agreements. We present a design and analysis of the filter for traffic with strong LRD in the frequency domain. Most Internet traffic has monotonically decreasing strength of variation functions over frequency. For this type of input traffic, we prove that optimal schedulers must have a convex structure. Uniform resource allocation is an extreme case of the convexity and is proved to be optimal for Poisson traffic. We integrate the convex structural principle with the Generalized Processor Sharing (GPS) discipline and show that the enhanced GPS policy improves the service quality significantly. Furthermore, we show that the presence of LRD in the input traffic results in shift of variation strength from high frequency to lower frequency bands and consequently leads to a degradation of the service quality.

For a connected network of sensors we consider deriving the linear update weights required by a 1-hop distributed linear averaging algorithm (denoted 1-DLA) such that average-consensus is reached when the sensor nodes simultaneously track, by linear stochastic approximation, a set of distinct Markov chains with time-varying regime. It is found the desired consensus is infeasible for any 1-hop 1-DLA type algorithm in this setting, which includes the consensus filter proposed in . However, assuming a symmetric communication graph we show the average-consensus can be approached with zero asymptotic error by an alternative 1-hop algorithm (denoted 4-DLA) that requires each sensor compute 4 estimates {picirc s, s0, scirc} rather than only {s} as required under 1-DLA. We demonstrate a simulation of 4-DLA and explain its advantages compared to alternative multihop algorithms.

This paper is concerned with approximation of Wonham filters. A focal point is that the underlying hidden Markov chain has a large state space. To reduce computational complexity, a two-time-scale approach is developed. Under time scale separation, the state space of the underlying Markov chain is divided into a number of groups such that the chain jumps rapidly within each group and switches occasionally from one group to another. Such structure gives rise to a limit Wonham filter that preserves the main features of the filtering process, but has a much smaller dimension and therefore is easier to compute. Using the limit filter enables us to develop efficient approximations and useful filters for hidden Markov chains. The main advantage of our approach is the reduction of dimensionality.

This paper analyzes the tracking properties of the least mean squares (LMS) algorithm when the underlying parameter evolves according to a finite-state Markov chain with infrequent jumps. First, using perturbed Liapunov function methods, mean-square error estimates are obtained for the tracking error. Then using recent results on two-time-scale Markov chains, mean ordinary differential equation and diffusion approximation results are obtained. It is shown that a sequence of the centered tracking errors converges to an ordinary differential equation. Moreover, a suitably scaled sequence of the tracking errors converges weakly to a diffusion process. It is also shown that iterate averaging of the tracking algorithm results in optimal asymptotic convergence rate in an appropriate sense. Two application examples, analysis of the performance of an adaptive multiuser detection algorithm in a direct-sequence code-division multiple-access (DS/CDMA) system, and tracking analysis of the state of a hidden Markov model (HMM) with infrequent jumps, are presented.

The aim of this paper is to develop discrete stochastic approximation algorithms that adaptively optimize the spreading codes of users in a code-division multiple-access (CDMA) system employing linear minimum mean-square error (MMSE) receivers. The proposed algorithms are able to adapt to slowly time-varying channel conditions. One of the most important properties of the algorithms is their self-learning capability-they spend most of the computational effort at the global optimizer of the objective function. Tracking analysis of the adaptive algorithms is presented together with mean-square convergence. An adaptive-step-size algorithm is also presented for optimally adjusting the step size based on the observations. Numerical examples, illustrating the performance of the algorithms in multipath fading channels, show substantial improvement over heuristic algorithms.

The aim of this paper is to present discrete stochastic approximation algorithms for adaptively optimizing the spreading code of users in a CDMA system. The proposed algorithm can adapt to slowly time varying channel conditions. The most important property of the proposed algorithm is its self-learning capability - it spend most of the computational effort at the global minimizer of the objective function. A tracking analysis of the adaptive algorithms is also presented together with square convergence analysis. Numerical examples illustrate the performance of the algorithms in multipath fading channels.

Motivated by the developments on iterate averaging of recursive stochastic approximation algorithms and asymptotic analysis of sign-error algorithms for adaptive filtering, this work develops two-stage sign algorithms for adaptive filtering. The proposed algorithms are based on constructions of a sequence of estimates using large step sizes followed by iterate averaging. Our main effort is devoted to improving the performance of the algorithms by establishing asymptotic normality of a suitably scaled sequence of the estimation errors. The asymptotic covariance is calculated and shown to be the smallest possible. Hence, the asymptotic efficiency or asymptotic optimality is obtained. Then variants of the algorithm including sign-regressor procedures and constant-step algorithms are studied. The minimal window width of averaging is also dealt with. Finally, iterate-averaging algorithms for blind multiuser detection in direct sequence/code-division multiple-access (DS/CDMA) systems are proposed and developed, and numerical examples are examined.

A bulk synchronous computation proceeds in phases that are separated by barrier synchronization. For dynamic bulk synchronous computations that exhibit varying phase-wise computational requirements, remapping at runtime is an effective approach to ensure parallel efficiency. The paper introduces a novel remapping strategy for computations whose workload changes can be modeled as a Markov chain. The use of a Markovian model allows us to treat statistical dependence and more complex structure than the usual independent identically distributed random variable assumptions. Our models are quite general and we do not need to impose conditions on the dynamics of the underlying process other than the transition probability matrix. It is shown that optimal remapping can be formulated as a binary decision process: remap or not at a given synchronizing instant. The optimal strategy is then developed for long lasting computations by employing optimal stopping rules in a stochastic control framework. The existence of optimal controls is established. Necessary and sufficient conditions for the optimality are obtained. Furthermore, a policy iteration algorithm is devised to reduce computational complexity and enhance fast convergence to the desired optimal control.

This paper is concerned with recursive algorithms for the estimation of hidden Markov models (HMMs) and autoregressive (AR) models under the Markov regime. Convergence and rate of convergence results are derived. Acceleration of convergence by averaging of the iterates and the observations are treated. Finally, constant step-size tracking algorithms are presented and examined.

This paper illustrates the use of "averaging" to improve the convergence rate of adaptive sign regressor and sign error multiuser detectors. The ingenious concept of averaging was invented by Polyak (1990) - this paper analyses the performance of averaging in the sign error and sign regressor adaptive blind multiuser detection algorithms in DS/CDMA systems.

The main objective of this paper is to analyze the (1, λ) evolution strategy by use of stochastic approximation methods. Both constant and decreasing step size algorithms are studied. Convergence and estimation error bounds for the (1, λ) evolution strategy are developed. First the algorithm is converted to a recursively defined scheme of stochastic approximation type. Then the analysis is carried out by using the analytic tools from stochastic approximation. In lieu of examining the discrete iterates, suitably scaled sequences are defined. These interpolated sequences are then studied in detail. It is shown that the limits of the sequences have natural connections to certain continuous time dynamical systems.

The asymptotic properties of a recursive adaptive beam former algorithm are studied. Both decreasing-gain and constant-gain cases are treated. For the case of decreasing gain the mean square convergence result is obtained, whereas for constant gain a sharp bound is derived, and asymptotic analysis for the normalized error is carried out. The analysis provides a clear picture of the local behaviour of the iterates near the optimal value. A sequence of scale deviations or normalized errors is shown to converge to a Gauss-Markov diffusion process which satisfies a stochastic differential equation.>