Search

Most existing stochastic models on age of information (AoI) focus on a single shared server serving status update packets from $N>1$ sources where each packet update stream is Poisson, i.e., single-hop scenario. In the current work, we study a two-hop edge computing system for which status updates from the information sources are still Poisson but they are not immediately available at the shared edge server, but instead they need to first receive service from a transmission server dedicated to each source. For exponentially distributed and heterogeneous service times for both the dedicated servers and the edge server, and bufferless preemptive resource management, we develop an analytical model using absorbing Markov chains (AMC) for obtaining the distribution of AoI for any source in the system. Moreover, for a given tagged source, the traffic arriving at the shared server from the $N-1$ un-tagged sources, namely the interference traffic, is not Poisson any more, but is instead a Markov modulated Poisson process (MMPP) whose state space grows exponentially with $N$. Therefore, we propose to employ a model reduction technique that approximates the behavior of the MMPP interference traffic with two states only, making it possible to approximately obtain the AoI statistics even for a very large number of sources. Numerical examples are presented to validate the proposed exact and approximate models., Comment: 9 pages, 4 figures

Coordinating communication and control is a key component in the stability and performance of networked multi-agent systems. While single user networked control systems have gained a lot of attention within this domain, in this work, we address the more challenging problem of large population multi-team dynamic games. In particular, each team constitutes two decision makers (namely, the sensor and the controller) who coordinate over a shared network to control a dynamically evolving state of interest under costs on both actuation and sensing/communication. Due to the shared nature of the wireless channel, the overall cost of each team depends on other teams' policies, thereby leading to a noncooperative game setup. Due to the presence of a large number of teams, we compute approximate decentralized Nash equilibrium policies for each team using the paradigm of (extended) mean-field games, which is governed by (1) the mean traffic flowing over the channel, and (2) the value of information at the sensor, which highlights the semantic nature of the ensuing communication. In the process, we compute optimal controller policies and approximately optimal sensor policies for each representative team of the mean-field system to alleviate the problem of general non-contractivity of the mean-field fixed point operator associated with the finite cardinality of the sensor action space. Consequently, we also prove the $\epsilon$--Nash property of the mean-field equilibrium solution which essentially characterizes how well the solution derived using mean-field analysis performs on the finite-team system. Finally, we provide extensive numerical simulations, which corroborate the theoretical findings and lead to additional insights on the properties of the results presented., Comment: Submitted to IEEE for possible publication

In this paper, we study the problem of robust cooperative multi-agent reinforcement learning (RL) where a large number of cooperative agents with distributed information aim to learn policies in the presence of \emph{stochastic} and \emph{non-stochastic} uncertainties whose distributions are respectively known and unknown. Focusing on policy optimization that accounts for both types of uncertainties, we formulate the problem in a worst-case (minimax) framework, which is is intractable in general. Thus, we focus on the Linear Quadratic setting to derive benchmark solutions. First, since no standard theory exists for this problem due to the distributed information structure, we utilize the Mean-Field Type Game (MFTG) paradigm to establish guarantees on the solution quality in the sense of achieved Nash equilibrium of the MFTG. This in turn allows us to compare the performance against the corresponding original robust multi-agent control problem. Then, we propose a Receding-horizon Gradient Descent Ascent RL algorithm to find the MFTG Nash equilibrium and we prove a non-asymptotic rate of convergence. Finally, we provide numerical experiments to demonstrate the efficacy of our approach relative to a baseline algorithm., Comment: Accepted for publication in L4DC 2024

In this paper, we revisit the two-player continuous-time infinite-horizon linear quadratic differential game problem, where one of the players can sample the state of the system only intermittently due to a sensing constraint while the other player can do so continuously. Under these asymmetric sensing limitations between the players, we analyze the optimal sensing and control strategies for the player at a disadvantage while the other player continues to play its security strategy. We derive an optimal sensor policy within the class of stationary randomized policies. Finally, using simulations, we show that the expected cost accrued by the first player approaches its security level as its sensing limitation is relaxed., Comment: Accepted to IEEE L-CSS

This paper introduces a new method to achieve stable convergence to Nash equilibrium in duopoly noncooperative games. Inspired by the recent fixed-time Nash Equilibrium seeking (NES) as well as prescribed-time extremum seeking (ES) and source seeking schemes, our approach employs a distributed sliding mode control (SMC) scheme, integrating extremum seeking with sinusoidal perturbation signals to estimate the pseudogradients of quadratic payoff functions. Notably, this is the first attempt to address noncooperative games without relying on models, combining classical extremum seeking with relay components instead of proportional control laws. We prove finite-time convergence of the closed-loop average system to Nash equilibrium using stability analysis techniques such as time-scaling, Lyapunov's direct method, and averaging theory for discontinuous systems. Additionally, we quantify the size of residual sets around the Nash equilibrium and validate our theoretical results through simulations., Comment: 8 pages and 2 figures. arXiv admin note: substantial text overlap with arXiv:2404.07287

We consider a communication system where a group of users, interconnected in a bidirectional gossip network, wishes to follow a time-varying source, e.g., updates on an event, in real-time. The users wish to maintain their expected version ages below a threshold, and can either rely on gossip from their neighbors or directly subscribe to a server publishing about the event, if the former option does not meet the timeliness requirements. The server wishes to maximize its profit by increasing subscriptions from users and minimizing event sampling frequency to reduce costs. This leads to a Stackelberg game between the server and the users where the sender is the leader deciding its sampling frequency and the users are the followers deciding their subscription strategies. We investigate equilibrium strategies for low-connectivity and high-connectivity topologies.

We consider a communication system consisting of a server that tracks and publishes updates about a time-varying data source or event, and a gossip network of users interested in closely tracking the event. The timeliness of the information is measured through the version age of information. The users wish to have their expected version ages remain below a threshold, and have the option to either rely on gossip from their neighbors or subscribe to the server directly to follow updates about the event if the former option does not meet the timeliness requirements. The server wishes to maximize its profit by increasing the number of subscribers and reducing costs associated with the frequent sampling of the event. We model the problem setup as a Stackelberg game between the server and the users, where the server commits to a frequency of sampling the event, and the users make decisions on whether to subscribe or not. As an initial work, we focus on directed networks with unidirectional flow of information and obtain the optimal equilibrium strategies for all the players. We provide simulation results to confirm the theoretical findings and provide additional insights.

Given a training set in the form of a paired $(\mathcal{X},\mathcal{Y})$, we say that the control system $\dot x = f(x,u)$ has learned the paired set via the control $u^*$ if the system steers each point of $\mathcal{X}$ to its corresponding target in $\mathcal{Y}$. If the training set is expanded, most existing methods for finding a new control $u^*$ require starting from scratch, resulting in a quadratic increase in complexity with the number of points. To overcome this limitation, we introduce the concept of $\textit{ tuning without forgetting}$. We develop $\textit{an iterative algorithm}$ to tune the control $u^*$ when the training set expands, whereby points already in the paired set are still matched, and new training samples are learned. At each update of our method, the control $u^*$ is projected onto the kernel of the end-point mapping generated by the controlled dynamics at the learned samples. It ensures keeping the end-points for the previously learned samples constant while iteratively learning additional samples.

Large language models (LLMs) have been driving a new wave of interactive AI applications across numerous domains. However, efficiently serving LLM inference requests is challenging due to their unpredictable execution times originating from the autoregressive nature of generative models. Existing LLM serving systems exploit first-come-first-serve (FCFS) scheduling, suffering from head-of-line blocking issues. To address the non-deterministic nature of LLMs and enable efficient interactive LLM serving, we present a speculative shortest-job-first (SSJF) scheduler that uses a light proxy model to predict LLM output sequence lengths. Our open-source SSJF implementation does not require changes to memory management or batching strategies. Evaluations on real-world datasets and production workload traces show that SSJF reduces average job completion times by 30.5-39.6% and increases throughput by 2.2-3.6x compared to FCFS schedulers, across no batching, dynamic batching, and continuous batching settings., Comment: Accepted at AIOps'24

This paper proposes a novel approach for locally stable convergence to Nash equilibrium in duopoly noncooperative games based on a distributed event-triggered control scheme. The proposed approach employs extremum seeking, with sinusoidal perturbation signals applied to estimate the Gradient (first derivative) of unknown quadratic payoff functions. This is the first instance of noncooperative games being tackled in a model-free fashion integrated with the event-triggered methodology. Each player evaluates independently the deviation between the corresponding current state variable and its last broadcasted value to update the player action, while they preserve control performance under limited bandwidth of the actuation paths and still guarantee stability for the closed-loop dynamics. In particular, the stability analysis is carried out using time-scaling technique, Lyapunov's direct method and averaging theory for discontinuous systems. We quantify the size of the ultimate small residual sets around the Nash equilibrium and illustrate the theoretical results numerically on an example.

We consider the problem of task offloading in multi-access edge computing (MEC) systems constituting $N$ devices assisted by an edge server (ES), where the devices can split task execution between a local processor and the ES. Since the local task execution and communication with the ES both consume power, each device must judiciously choose between the two. We model the problem as a large population non-cooperative game among the $N$ devices. Since computation of an equilibrium in this scenario is difficult due to the presence of a large number of devices, we employ the mean-field game framework to reduce the finite-agent game problem to a generic user's multi-objective optimization problem, with a coupled consistency condition. By leveraging the novel age of information (AoI) metric, we invoke techniques from stochastic hybrid systems (SHS) theory and study the tradeoffs between increasing information freshness and reducing power consumption. In numerical simulations, we validate that a higher load at the ES may lead devices to upload their task to the ES less often., Comment: Submitted to IEEE for possible publication

Closed-loop control of nonlinear dynamical systems with partial-state observability demands expert knowledge of a diverse, less standardized set of theoretical tools. Moreover, it requires a delicate integration of controller and estimator designs to achieve the desired system behavior. To establish a general controller synthesis framework, we explore the Decision Transformer (DT) architecture. Specifically, we first frame the control task as predicting the current optimal action based on past observations, actions, and rewards, eliminating the need for a separate estimator design. Then, we leverage the pre-trained language models, i.e., the Generative Pre-trained Transformer (GPT) series, to initialize DT and subsequently train it for control tasks using low-rank adaptation (LoRA). Our comprehensive experiments across five distinct control tasks, ranging from maneuvering aerospace systems to controlling partial differential equations (PDEs), demonstrate DT's capability to capture the parameter-agnostic structures intrinsic to control tasks. DT exhibits remarkable zero-shot generalization abilities for completely new tasks and rapidly surpasses expert performance levels with a minimal amount of demonstration data. These findings highlight the potential of DT as a foundational controller for general control applications., Comment: Submitted to CDC 2024

Hydrogen-electrical (HE) microgrids are increasingly assuming an important role on the pathway toward decarbonization of energy and transportation systems. This paper studies networked HE microgrids planning (NHEMP), considering a critical but often-overlooked issue, i.e., the demand-inducing effect (DIE) associated with infrastructure development decisions. Specifically, higher refueling capacities will attract more refueling demand of hydrogen-powered vehicles (HVs). To capture such interactions between investment decisions and induced refueling demand, we introduce a decision-dependent uncertainty (DDU) set and build a trilevel stochastic-robust formulation. The upper-level determines optimal investment strategies for HE microgrids, the lower-level optimizes the risk-aware operation schedules across a series of stochastic scenarios, and, for each scenario, the middle-level identifies the "worst" situation of refueling demand within an individual DDU set to ensure economic feasibility. Then, an adaptive and exact decomposition algorithm, based on Parametric Column-and-Constraint Generation (PC&CG), is customized and developed to address the computational challenge and to quantitatively analyze the impact of DIE. Case studies on an IEEE exemplary system validate the effectiveness of the proposed NHEMP model and the PC&CG algorithm. It is worth highlighting that DIE can make an important contribution to the economic benefits of NHEMP, yet its significance will gradually decrease when the main bottleneck transits to other system restrictions.

In this paper, we investigate the impact of introducing relative entropy regularization on the Nash Equilibria (NE) of General-Sum $N$-agent games, revealing the fact that the NE of such games conform to linear Gaussian policies. Moreover, it delineates sufficient conditions, contingent upon the adequacy of entropy regularization, for the uniqueness of the NE within the game. As Policy Optimization serves as a foundational approach for Reinforcement Learning (RL) techniques aimed at finding the NE, in this work we prove the linear convergence of a policy optimization algorithm which (subject to the adequacy of entropy regularization) is capable of provably attaining the NE. Furthermore, in scenarios where the entropy regularization proves insufficient, we present a $\delta$-augmentation technique, which facilitates the achievement of an $\epsilon$-NE within the game.

We address in this paper Reinforcement Learning (RL) among agents that are grouped into teams such that there is cooperation within each team but general-sum (non-zero sum) competition across different teams. To develop an RL method that provably achieves a Nash equilibrium, we focus on a linear-quadratic structure. Moreover, to tackle the non-stationarity induced by multi-agent interactions in the finite population setting, we consider the case where the number of agents within each team is infinite, i.e., the mean-field setting. This results in a General-Sum LQ Mean-Field Type Game (GS-MFTGs). We characterize the Nash equilibrium (NE) of the GS-MFTG, under a standard invertibility condition. This MFTG NE is then shown to be $\mathcal{O}(1/M)$-NE for the finite population game where $M$ is a lower bound on the number of agents in each team. These structural results motivate an algorithm called Multi-player Receding-horizon Natural Policy Gradient (MRPG), where each team minimizes its cumulative cost independently in a receding-horizon manner. Despite the non-convexity of the problem, we establish that the resulting algorithm converges to a global NE through a novel problem decomposition into sub-problems using backward recursive discrete-time Hamilton-Jacobi-Isaacs (HJI) equations, in which independent natural policy gradient is shown to exhibit linear convergence under time-independent diagonal dominance. Experiments illuminate the merits of this approach in practice.

Strategic information disclosure, in its simplest form, considers a game between an information provider (sender) who has access to some private information that an information receiver is interested in. While the receiver takes an action that affects the utilities of both players, the sender can design information (or modify beliefs) of the receiver through signal commitment, hence posing a Stackelberg game. However, obtaining a Stackelberg equilibrium for this game traditionally requires the sender to have access to the receiver's objective. In this work, we consider an online version of information design where a sender interacts with a receiver of an unknown type who is adversarially chosen at each round. Restricting attention to Gaussian prior and quadratic costs for the sender and the receiver, we show that $\mathcal{O}(\sqrt{T})$ regret is achievable with full information feedback, where $T$ is the total number of interactions between the sender and the receiver. Further, we propose a novel parametrization that allows the sender to achieve $\mathcal{O}(\sqrt{T})$ regret for a general convex utility function. We then consider the Bayesian Persuasion problem with an additional cost term in the objective function, which penalizes signaling policies that are more informative and obtain $\mathcal{O}(\log(T))$ regret. Finally, we establish a sublinear regret bound for the partial information feedback setting and provide simulations to support our theoretical results.

This article explains the distinctions between robustness and resilience in control systems. Resilience confronts a distinct set of challenges, posing new ones for designing controllers for feedback systems, networks, and machines that prioritize resilience over robustness. The concept of resilience is explored through a three-stage model, emphasizing the need for a proactive preparation and automated response to elastic events. A toy model is first used to illustrate the tradeoffs between resilience and robustness. Then, it delves into contextual dualism and interactionism, and introduces game-theoretic paradigms as a unifying framework to consolidate resilience and robustness. The article concludes by discussing the interplay between robustness and resilience, suggesting that a comprehensive theory of resilience and quantification metrics, and formalization through game-theoretic frameworks are necessary. The exploration extends to system-of-systems resilience and various mechanisms, including the integration of AI techniques and non-technical solutions, like cyber insurance, to achieve comprehensive resilience in control systems. As we approach 2030, the systems and control community is at the opportune moment to lay scientific foundations of resilience by bridging feedback control theory, game theory, and learning theory. Resilient control systems will enhance overall quality of life, enable the development of a resilient society, and create a societal-scale impact amid global challenges such as climate change, conflicts, and cyber insecurity.

Dimensionality reduction is crucial for controlling nonlinear partial differential equations (PDE) through a "reduce-then-design" strategy, which identifies a reduced-order model and then implements model-based control solutions. However, inaccuracies in the reduced-order modeling can substantially degrade controller performance, especially in PDEs with chaotic behavior. To address this issue, we augment the reduce-then-design procedure with a policy optimization (PO) step. The PO step fine-tunes the model-based controller to compensate for the modeling error from dimensionality reduction. This augmentation shifts the overall strategy into reduce-then-design-then-adapt, where the model-based controller serves as a warm start for PO. Specifically, we study the state-feedback tracking control of PDEs that aims to align the PDE state with a specific constant target subject to a linear-quadratic cost. Through extensive experiments, we show that a few iterations of PO can significantly improve the model-based controller performance. Our approach offers a cost-effective alternative to PDE control using end-to-end reinforcement learning.

We consider information update systems on a gossip network, which consists of a single source and $n$ receiver nodes. The source encrypts the information into $n$ distinct keys with version stamps, sending a unique key to each node. For decryption in a $(k, n)$-Threshold Signature Scheme, each receiver node requires at least $k+1$ different keys with the same version, shared over peer-to-peer connections. We consider two different schemes: a memory scheme (in which the nodes keep the source's current and previous encrypted messages) and a memoryless scheme (in which the nodes are allowed to only keep the source's current message). We measure the ''timeliness'' of information updates by using the version age of information. Our work focuses on determining closed-form expressions for the time average age of information in a heterogeneous random graph. Our work not only allows to verify the expected outcome that a memory scheme results in a lower average age compared to a memoryless scheme, but also provides the quantitative difference between the two. In our numerical results, we quantify the value of memory and demonstrate that the advantages of memory diminish with infrequent source updates, frequent gossipping between nodes, or a decrease in $k$ for a fixed number of nodes.

No-regret learning has a long history of being closely connected to game theory. Recent works have devised uncoupled no-regret learning dynamics that, when adopted by all the players in normal-form games, converge to various equilibrium solutions at a near-optimal rate of $\widetilde{O}(T^{-1})$, a significant improvement over the $O(1/\sqrt{T})$ rate of classic no-regret learners. However, analogous convergence results are scarce in Markov games, a more generic setting that lays the foundation for multi-agent reinforcement learning. In this work, we close this gap by showing that the optimistic-follow-the-regularized-leader (OFTRL) algorithm, together with appropriate value update procedures, can find $\widetilde{O}(T^{-1})$-approximate (coarse) correlated equilibria in full-information general-sum Markov games within $T$ iterations. Numerical results are also included to corroborate our theoretical findings.

We introduce controlgym, a library of thirty-six industrial control settings, and ten infinite-dimensional partial differential equation (PDE)-based control problems. Integrated within the OpenAI Gym/Gymnasium (Gym) framework, controlgym allows direct applications of standard reinforcement learning (RL) algorithms like stable-baselines3. Our control environments complement those in Gym with continuous, unbounded action and observation spaces, motivated by real-world control applications. Moreover, the PDE control environments uniquely allow the users to extend the state dimensionality of the system to infinity while preserving the intrinsic dynamics. This feature is crucial for evaluating the scalability of RL algorithms for control. This project serves the learning for dynamics & control (L4DC) community, aiming to explore key questions: the convergence of RL algorithms in learning control policies; the stability and robustness issues of learning-based controllers; and the scalability of RL algorithms to high- and potentially infinite-dimensional systems. We open-source the controlgym project at https://github.com/xiangyuan-zhang/controlgym., Comment: 25 pages, 16 figures

We study the weighted average consensus problem for a gossip network of agents with vector-valued states. For a given matrix-weighted graph, the gossip process is described by a sequence of pairs of adjacent agents communicating and updating their states based on the edge matrix weight. Our key contribution is providing conditions for the convergence of this non-homogeneous Markov process as well as the characterization of its limit set. To this end, we introduce the notion of "$w$-holonomy" of a set of stochastic matrices, which enables the characterization of sequences of gossiping pairs resulting in reaching a desired consensus in a decentralized manner. Stated otherwise, our result characterizes the limiting behavior of infinite products of (non-commuting, possibly with absorbing states) stochastic matrices.

The paper deals with the analysis of a discrete-time networked competitive bivirus susceptible-infected-susceptible (SIS) model. More specifically, we suppose that virus 1 and virus 2 are circulating in the population and are in competition with each other. We show that the model is strongly monotone, and that, under certain assumptions, it does not admit any periodic orbit. We identify a sufficient condition for exponential convergence to the disease-free equilibrium (DFE). Assuming only virus 1 (resp. virus 2) is alive, we establish a condition for global asymptotic convergence to the single-virus endemic equilibrium of virus 1 (resp. virus 2) -- our proof does not rely on the construction of a Lyapunov function. Assuming both virus 1 and virus 2 are alive, we establish a condition which ensures local exponential convergence to the single-virus equilibrium of virus 1 (resp. virus 2). Finally, we provide a sufficient (resp. necessary) condition for the existence of a coexistence equilibrium.

In uniform-price markets, suppliers compete to supply a resource to consumers, resulting in a single market price determined by their competition. For sufficient flexibility, producers and consumers prefer to commit to a function as their strategies, indicating their preferred quantity at any given market price. Producers and consumers may wish to act as both, i.e., prosumers. In this paper, we examine the behavior of profit-maximizing prosumers in a uniform-price market for resource allocation with the objective of maximizing the social welfare. We propose a scalar-parameterized function bidding mechanism for the prosumers, in which we establish the existence and uniqueness of Nash equilibrium. Furthermore, we provide an efficient way to compute the Nash equilibrium through the computation of the market allocation at the Nash equilibrium. Finally, we present a case study to illustrate the welfare loss under different variations of market parameters, such as the market's supply capacity and inelastic demand., Comment: Corrected typos in the figures

In this work, we consider dynamic influence maximization games over social networks with multiple players (influencers). The goal of each influencer is to maximize their own reward subject to their limited total budget rate constraints. Thus, influencers need to carefully design their investment policies considering individuals' opinion dynamics and other influencers' investment strategies, leading to a dynamic game problem. We first consider the case of a single influencer who wants to maximize its utility subject to a total budget rate constraint. We study both offline and online versions of the problem where the opinion dynamics are either known or not known a priori. In the singe-influencer case, we propose an online no-regret algorithm, meaning that as the number of campaign opportunities grows, the average utilities obtained by the offline and online solutions converge. Then, we consider the game formulation with multiple influencers in offline and online settings. For the offline setting, we show that the dynamic game admits a unique Nash equilibrium policy and provide a method to compute it. For the online setting and with two influencers, we show that if each influencer applies the same no-regret online algorithm proposed for the single-influencer maximization problem, they will converge to the set of $\epsilon$-Nash equilibrium policies where $\epsilon=O(\frac{1}{\sqrt{K}})$ scales in average inversely with the number of campaign times $K$ considering the average utilities of the influencers. Moreover, we extend this result to any finite number of influencers under more strict requirements on the information structure. Finally, we provide numerical analysis to validate our results under various settings., Comment: This work has been submitted to IEEE for possible publication

We introduce the receding-horizon policy gradient (RHPG) algorithm, the first PG algorithm with provable global convergence in learning the optimal linear estimator designs, i.e., the Kalman filter (KF). Notably, the RHPG algorithm does not require any prior knowledge of the system for initialization and does not require the target system to be open-loop stable. The key of RHPG is that we integrate vanilla PG (or any other policy search directions) into a dynamic programming outer loop, which iteratively decomposes the infinite-horizon KF problem that is constrained and non-convex in the policy parameter into a sequence of static estimation problems that are unconstrained and strongly-convex, thus enabling global convergence. We further provide fine-grained analyses of the optimization landscape under RHPG and detail the convergence and sample complexity guarantees of the algorithm. This work serves as an initial attempt to develop reinforcement learning algorithms specifically for control applications with performance guarantees by utilizing classic control theory in both algorithmic design and theoretical analyses. Lastly, we validate our theories by deploying the RHPG algorithm to learn the Kalman filter design of a large-scale convection-diffusion model. We open-source the code repository at \url{https://github.com/xiangyuan-zhang/LearningKF}., Comment: arXiv admin note: text overlap with arXiv:2301.12624