Algorithms for solving nonlinear fixed-point equations---such as average-reward Q-learning and TD-learning---often involve semi-norm contractions. Achieving parameter-free optimal convergence rates for these methods via Polyak–Ruppert averaging has remained elusive, largely due to the non-monotonicity of such semi-norms. We close this gap by (i.) recasting the averaged error as a linear recursion involving a nonlinear perturbation, and (ii.) taming the nonlinearity by coupling the semi-norm's contraction with the monotonicity of a suitably induced norm. Our main result yields the first parameter-free ~O(1/√t) optimal rates for Q-learning in both average-reward and exponentially discounted settings, where t denotes the iteration index. The result applies within a broad framework that accommodates both synchronous and asynchronous updates, single-agent and distributed deployments, and data streams obtained from either simulators or along Markovian trajectories.

Integer-order calculus fails to capture the long-range dependence (LRD) and memory effects found in many complex systems. Fractional calculus addresses these gaps through fractional-order integrals and derivatives, but fractional-order dynamical systems pose substantial challenges in system identification and optimal control tasks. In this paper, we theoretically derive the optimal control via linear quadratic regulator (LQR) for fractional-order linear time-invariant (FOLTI) systems and develop an end-to-end deep learning framework based on this theoretical foundation. Our approach establishes a rigorous mathematical model, derives analytical solutions, and incorporates deep learning to achieve data-driven optimal control of FOLTI systems. Our key contributions include: (i) proposing a novel method for system identification and optimal control strategy in FOLTI systems, (ii) developing the first end-to-end data-driven learning framework, Fractional-Order Learning for Optimal Control (FOLOC), that learns control policies from observed trajectories, and (iii) deriving theoretical bounds on the sample complexity for learning accurate control policies under fractional-order dynamics. Experimental results indicate that our method accurately approximates fractional-order system behaviors without relying on Gaussian noise assumptions, pointing to promising avenues for advanced optimal control.

Deep generative models, particularly diffusion models, have achieved remarkable success but face significant challenges when trained on real-world, long-tailed datasets- where few "head" classes dominate and many "tail" classes are underrepresented. This paper develops a theoretical framework for long-tailed learning via diffusion models through the lens of deep mutual learning. We introduce a novel regularized training objective that combines the standard diffusion loss with a mutual learning term, enabling balanced performance across all class labels, including the underrepresented tails. Our approach to learn via the proposed regularized objective is to formulate it as a multi-player game, with Nash equilibrium serving as the solution concept. We derive a non-asymptotic first-order convergence result for individual gradient descent algorithm to find the Nash equilibrium. We show that the Nash gap of the score network obtained from the algorithm is upper bounded by $\mathcal{O}(\frac{1}{\sqrt{T_{train}}}+\beta)$ where $\beta$ is the regularizing parameter and $T_{train}$ is the number of iterations of the training algorithm. Furthermore, we theoretically establish hyper-parameters for training and sampling algorithm that ensure that we find conditional score networks (under our model) with a worst case sampling error $\mathcal{O}(\epsilon+1), \forall \epsilon>0$ across all class labels. Our results offer insights and guarantees for training diffusion models on imbalanced, long-tailed data, with implications for fairness, privacy, and generalization in real-world generative modeling scenarios.

We develop provably safe and convergent reinforcement learning (RL) algorithms for control of nonlinear dynamical systems, bridging the gap between the hard safety guarantees of control theory and the convergence guarantees of RL theory. Recent advances at the intersection of control and RL follow a two-stage, safety filter approach to enforcing hard safety constraints: model-free RL is used to learn a potentially unsafe controller, whose actions are projected onto safe sets prescribed, for example, by a control barrier function. Though safe, such approaches lose any convergence guarantees enjoyed by the underlying RL methods. In this paper, we develop a single-stage, sampling-based approach to hard constraint satisfaction that learns RL controllers enjoying classical convergence guarantees while satisfying hard safety constraints throughout training and deployment. We validate the efficacy of our approach in simulation, including safe control of a quadcopter in a challenging obstacle avoidance problem, and demonstrate that it outperforms existing benchmarks.

Since the start of the COVID-19 pandemic, social distancing has been key to curb the spread of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). Social distancing policies have largely been made based on reported case data, which are often underreported. There is little to no understanding of how underreporting in case data may affect the performance of social distancing policies designed using such data. This article aims to fill this gap. We evaluate three policy-making rationales (called “controllers”): a flattening-the-curve (FC) controller that maximizes allowable transmission rate while ensuring hospital capacity is not exceeded, a time-limited-intervention (TLI) controller to minimize the number of infectious people with policies of fixed durations, and a minimizing-health-and-economic-costs-with-reinforcement-learning (MC-RL) controller to minimize weighted public health and economic costs. Each controller is applied in six scenarios where there is no underreporting, underreporting without correcting it, and underreporting with corrections. It is found that both the recommended policies by a controller and the resulting disease trajectories would be different under different scenarios, in which direction underreporting affects policies and disease trajectories depending on three factors: time elapsed since start of pandemic, local hospital capacity, and disease severity. Our findings demonstrate the high stakes of ignoring the underreporting issue or simply upscaling the case data: policies designed cannot achieve preset control objectives and could bring unexpected public health and economic outcomes.

Understanding convergence of SGD-based optimization algorithms can help deal with enormous machine learning problems. To ensure last-iterate convergence of SGD and momentum-based SGD (mSGD), the existing studies usually constrain the step size $\epsilon_{n}$ to decay as $\sum_{n=1}^{+\infty}\epsilon_{n}^{2}<+\infty$, which however is rather conservative and may lead to slow convergence in the early stage of the iteration. In this paper, we relax this requirement by studying an alternate step size for the mSGD. First, we relax the requirement of the decay on step size to $\sum_{n=1}^{+\infty}\epsilon_{n}^{2+\eta_{0}}<+\infty\ (0\le\eta_{0}<1/2)$. This implies that a larger step size, such as $\epsilon_{n}=\frac{1}{\sqrt{n}}$ can be utilized for accelerating the mSGD in the early stage. Under this new step size and some common conditions, we prove that the gradient norm of mSGD for non-convex loss functions asymptotically decays to zero. In addition, we show that this step size can indeed help make the convergence into a neighborhood of the stationary points quicker in the early stage. In addition, we establish the convergence of mSGD under a constant step size $\epsilon_n\equiv\epsilon>0$ by removing the common requirement in the literature on the strong convexity of the loss function. Some experiments are given to illustrate the developed results.

In applications such as participatory sensing and crowd sensing, self-interested agents exert costly effort towards achieving an objective for the system operator. We study such a setup where a principal designs a sequence of contracts to incentivize multiple agents of different types to achieve a global objective. The agents can collude with each other to derive rent, since the principal cannot observe the efforts exerted directly, but only the outcome of the task which is a noisy function of the effort. The type of each agent influences the effort cost and task output. For a duopoly in which agent payments are coupled, we show that i) if the principal and the agents interact finitely many times, the agents can derive rent by colluding even if the principal knows the types of the agents, and ii) if the principal and the agents interact infinitely often, the principal can disincentivize agent collusion through a dynamic data-driven contract.

Recent years have bore witness to the proliferation of distributed filtering techniques, where a collection of agents communicating over an ad-hoc network aim to collaboratively estimate and track the state of a system. These techniques form the enabling technology of modern multi-agent systems and have gained great importance in the engineering community. Although most distributed filtering techniques come with a set of stability and convergence criteria, the conditions imposed are found to be unnecessarily restrictive. The paradigm of stability and convergence in distributed filtering is revised in this manuscript. Accordingly, a general distributed filter is constructed and its estimation error dynamics is formulated. The conducted analysis demonstrates that conditions for achieving stable filtering operations are the same as those required in the centralized filtering setting. Finally, the concepts are demonstrated in a Kalman filtering framework and validated using simulation examples.

The main goal of this study is to extract a set of brain networks in multiple time-resolutions to analyze the connectivity patterns among the anatomic regions for a given cognitive task. We suggest a deep architecture which learns the natural groupings of the connectivity patterns of human brain in multiple time-resolutions. The suggested architecture is tested on task data set of Human Connectome Project (HCP) where we extract multi-resolution networks, each of which corresponds to a cognitive task. At the first level of this architecture, we decompose the fMRI signal into multiple sub-bands using wavelet decompositions. At the second level, for each sub-band, we estimate a brain network extracted from short time windows of the fMRI signal. At the third level, we feed the adjacency matrices of each mesh network at each time-resolution into an unsupervised deep learning algorithm, namely, a Stacked De- noising Auto-Encoder (SDAE). The outputs of the SDAE provide a compact connectivity representation for each time window at each sub-band of the fMRI signal. We concatenate the learned representations of all sub-bands at each window and cluster them by a hierarchical algorithm to find the natural groupings among the windows. We observe that each cluster represents a cognitive task with a performance of 93% Rand Index and 71% Adjusted Rand Index. We visualize the mean values and the precisions of the networks at each component of the cluster mixture. The mean brain networks at cluster centers show the variations among cognitive tasks and the precision of each cluster shows the within cluster variability of networks, across the subjects.

This paper presents a dynamic pricing and energy management framework for electric vehicle (EV) charging service providers. To set the charging prices, the service providers faces three uncertainties: the volatility of wholesale electricity price, intermittent renewable energy generation, and spatial-temporal EV charging demand. The main objective of our work here is to help charging service providers to improve their total profits while enhancing customer satisfaction and maintaining power grid stability, taking into account those uncertainties. We employ a linear regression model to estimate the EV charging demand at each charging station, and introduce a quantitative measure for customer satisfaction. Both the greedy algorithm and the dynamic programming (DP) algorithm are employed to derive the optimal charging prices and determine how much electricity to be purchased from the wholesale market in each planning horizon. Simulation results show that DP algorithm achieves an increased profit (up to 9%) compared to the greedy algorithm (the benchmark algorithm) under certain scenarios. Additionally, we observe that the integration of a low-cost energy storage into the system can not only improve the profit, but also smooth out the charging price fluctuation, protecting the end customers from the volatile wholesale market.

This paper presents a multi-stage approach to the placement of charging stations under the scenarios of different electric vehicle (EV) penetration rates. The EV charging market is modeled as the oligopoly. A consumer behavior based approach is applied to forecast the charging demand of the charging stations using a nested logit model. The impacts of both the urban road network and the power grid network on charging station planning are also considered. At each planning stage, the optimal station placement strategy is derived through solving a Bayesian game among the service providers. To investigate the interplay of the travel pattern, the consumer behavior, urban road network, power grid network, and the charging station placement, a simulation platform (The EV Virtual City 1.0) is developed using Java on Repast.We conduct a case study in the San Pedro District of Los Angeles by importing the geographic and demographic data of that region into the platform. The simulation results demonstrate a strong consistency between the charging station placement and the traffic flow of EVs. The results also reveal an interesting phenomenon that service providers prefer clustering instead of spatial separation in this oligopoly market.

We purpose and analyze an off-line randomized sensor selection strategy for sequential hypothesis testing problem constrained with sensor measurement costs. Within the framework of Wald's approximation, the sequential probability ratio test (SPRT) with sensor selection is designed for minimizing the expected total measurement cost subject to reliability and sensor usage constraints. In the case of symmetric hypotheses, we introduce a quantity, called efficiency, of a sensor and show that it is critical to the sensor selection in SPRT. Furthermore, an algorithm with linear time complexity is proposed to obtain the optimal sensor selection probabilities.

System integration is the elephant in the china store of large-scale cyber-physical system (CPS) design. It would be hard to find any other technology that is more undervalued scientifically and at the same time has bigger impact on the presence and future of engineered systems. The unique challenges in CPS integration emerge from the heterogeneity of components and interactions. This heterogeneity drives the need for modeling and analyzing cross-domain interactions among physical and computational/networking domains and demands deep understanding of the effects of heterogeneous abstraction layers in the design flow. To address the challenges of CPS integration, significant progress needs to be made toward a new science and technology foundation that is model based, precise, and predictable. This paper presents a theory of composition for heterogeneous systems focusing on stability. Specifically, the paper presents a passivity-based design approach that decouples stability from timing uncertainties caused by networking and computation. In addition, the paper describes cross-domain abstractions that provide effective solution for model-based fully automated software synthesis and high-fidelity performance analysis. The design objectives demonstrated using the techniques presented in the paper are group coordination for networked unmanned air vehicles (UAVs) and high-confidence embedded control software design for a quadrotor UAV. Open problems in the area are also discussed, including the extension of the theory of compositional design to guarantee properties beyond stability, such as safety and performance.

We consider an anytime control algorithm for the situation when the processor resource availability is time-varying. The basic idea is to calculate the components of the control input vector sequentially to maximally utilize the processing resources available at every time step. Thus, the system evolves as a discrete time hybrid system with the particular mode active at any time step being dictated by the processor availability. We extend our earlier work to consider the sequence in which the control inputs are calculated as a variable. In particular, we propose stochastic decision rules in which the inputs are chosen according to a Markov chain. For the LQG case, we present a Markovian jump linear system based formulation that provides analytical performance and stability expressions. For more general cases, we present a receding horizon control based implementation and illustrate the increase in performance through simulations.

We consider the effect of network throughput on the convergence of a specific class of distributed averaging algorithms, called consensus algorithms. These algorithms rely on iterative computation of the desired average by message passing among the nodes. It is thus assumed that the rate of convergence should benefit from greater network connectivity. However, one must also account for the additional network resources that establishing such a connectivity would entail. In this paper, we study this problem in the context of randomly-placed consensus-seeking nodes that are connected through a dense wireless network, i.e., whose capacity is interference-limited. By analyzing the outage of each communication link along with results from mixing times of Markov chains, we obtain scaling laws for the mixing times of fastest-converging consensus topologies over such networks.

It is known that noiseless feedback does not increase the capacity of memoryless channels. However, such feedback can considerably increase the reliability or reduce the coding complexity of schemes that approach capacity. One might hope for the same to be (at least partially) true of noisy feedback. This paper develops a new class of coding schemes for additive white noise channels with feedback corrupted by additive white noise, focusing much of the results and discussion on the Gaussian case. These schemes are variants of the well-known Schalkwijk-Kailath (SK) coding scheme and are based upon simple techniques from stochastic approximation. Specifically, instead of the classic Robbins-Munro approach to stochastic approximation originally used in the SK scheme, we employ more recent techniques from Kushner. The resulting schemes enable a tradeoff between transmission rate and error performance in the presence of noisy feedback even as the number of iterations becomes large.

In this paper, we consider the scenario where many sensors co-operate to estimate a process. Only one sensor can take a measurement at any time step. We wish to come up with optimal sensor scheduling algorithms. The problem is motivated by the use of sonar range-finders used by the vehicles on the Caltech multi-vehicle wireless testbed. We see that this problem involves searching a tree in general and propose and analyze two strategies for pruning the tree to keep the computation limited. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. We also study a technique that employs choosing the sensors randomly from a probability distribution which can then be optimized. The performance of the algorithms are illustrated with the help of numerical examples.

We examine the problem of distributed estimation when only one sensor can take a measurement per time step. We solve for the optimal recursive estimation algorithm when the sensor switching schedule is given. We then consider the effect of noise in communication channels. We also investigate the problem of determining an optimal sensor switching strategy. We see that this problem involves searching a tree in general and propose two strategies for pruning the tree to minimize the computation. The first is a sliding window strategy motivated by the Viterbi algorithm, and the second one uses thresholding. The performance of the algorithms is illustrated using numerical examples.