Self-attention has emerged as a core component of modern neural architectures, yet its theoretical underpinnings remain elusive. In this paper, we study self-attention through the lens of *interacting entities*, ranging from agents in multi-agent reinforcement learning to alleles in genetic sequences, and show that a single layer linear self-attention can *efficiently* represent, learn, and generalize functions capturing pairwise interactions, including out-of-distribution scenarios. Our analysis reveals that self-attention acts as a *mutual interaction learner* under minimal assumptions on the diversity of interaction patterns observed during training, thereby encompassing a wide variety of real-world domains. In addition, we validate our theoretical insights through experiments demonstrating that self-attention learns interaction functions and generalizes across both population distributions and out-of-distribution scenarios. Building on our theories, we introduce *HyperFeatureAttention*, a novel neural network module designed to learn couplings of different feature-level interactions between entities. Furthermore, we propose *HyperAttention*, a new module that extends beyond pairwise interactions to capture multi-entity dependencies, such as three-way, four-way, or general $n$-way interactions.

Due to high dimensionality and non-convexity, real-time optimal control using full-order dynamics models for legged robots is challenging. Therefore, Nonlinear Model Predictive Control (NMPC) approaches are often limited to reduced-order models or local approximations. Sampling-based MPC has shown potential in nonconvex even discontinuous problems, but often yields suboptimal solutions with high variance, which limits its applications in high-dimensional locomotion. This work introduces DIAL-MPC (Diffusion-Inspired Annealing for Legged MPC), a sampling-based MPC framework with a novel diffusion-style annealing process. Such a process is supported by the theoretical landscape analysis of Model Predictive Path Integral Control (MPPI) and the connection between MPPI and single-step diffusion. Algorithmically, DIALMPC iteratively refines solutions online and achieves both global coverage and local convergence. In quadrupedal torquelevel control tasks, DIAL-MPC reduces the tracking error of standard MPPI by 13.4 times and outperforms reinforcement learning (RL) policies by 50 % in challenging climbing tasks without any training. In particular, DIAL-MPC enables precise real-world quadrupedal jumping with payload. To the best of our knowledge, DIAL-MPC is the first training-free method that optimizes over full-order legged dynamics in real-time.

Designing efficient algorithms for multi-agent reinforcement learning (MARL) is fundamentally challenging because the size of the joint state and action spaces grows exponentially in the number of agents. These difficulties are exacerbated when balancing sequential global decision-making with local agent interactions. In this work, we propose a new algorithm $\texttt{SUBSAMPLE-MFQ}$ ($\textbf{Subsample}$-$\textbf{M}$ean-$\textbf{F}$ield-$\textbf{Q}$-learning) and a decentralized randomized policy for a system with $n$ agents. For any $k\leq n$, our algorithm learns a policy for the system in time polynomial in $k$. We prove that this learned policy converges to the optimal policy on the order of $\tilde{O}(1/\sqrt{k})$ as the number of subsampled agents $k$ increases. In particular, this bound is independent of the number of agents $n$.

We study the problem of stabilizing an unknown partially observable linear time-invariant (LTI) system. For fully observable systems, leveraging an unstable/stable subspace decomposition approach, state-of-art sample complexity is independent from system dimension $n$ and only scales with respect to the dimension of the unstable subspace. However, it remains open whether such sample complexity can be achieved for partially observable systems because such systems do not admit a uniquely identifiable unstable subspace. In this paper, we propose LTS-P, a novel technique that leverages compressed singular value decomposition (SVD) on the ''lifted'' Hankel matrix to estimate the unstable subsystem up to an unknown transformation. Then, we design a stabilizing controller that integrates a robust stabilizing controller for the unstable mode and a small-gain-type assumption on the stable subspace. We show that LTS-P stabilizes unknown partially observable LTI systems with state-of-the-art sample complexity that is dimension-free and only scales with the number of unstable modes, which significantly reduces data requirements for high-dimensional systems with many stable modes.

We study the problem of learning to stabilize unknown noisy Linear Time-Invariant (LTI) systems on a single trajectory. The state-of-the-art guarantees that the system is stabilized before the system state reaches $2^{O(k \log n)}$ in $L^2$-norm, where $n$ is the state dimension, and $k$ is the dimension of the unstable subspace. However, this bound only holds in *noiseless* LTI systems that have a control input dimension at least as large as the dimension of unstable subspace, making it impractical in many real-life scenarios. In noisy systems, unknown noise is not only amplified by unstable system modes but also imposes significant difficulty in estimating the system dynamics or bounding the estimation errors. Furthermore, the aforementioned complexity is only achievable when the system has a number of control inputs that are at least as many as the dimension of the unstable subspace. To address these issues, we develop a novel algorithm with a singular-value-decomposition(SVD)-based analytical framework and show that the system is stabilized with the same complexity guarantee with the state-of-the-art in a noisy environment. With the SVD-based framework, we can bound the error of system identification with Davis-Kahan Theorem and design a controller that does not require the invertibility of the control matrix, making it possible to apply this algorithm in under-actuated settings. To the best of our knowledge, this paper is the first to achieve learning-to-stabilize unknown LTI system without exponential blow-up in noisy and under-actuated systems. We further demonstrate the advantage of the proposed algorithm in under-actuated settings.

We consider the problem of efficiently routing jobs that arrive into a central queue to a system of heterogeneous servers. Unlike homogeneous systems, a threshold policy, that routes jobs to the slow server(s) when the queue length exceeds a certain threshold, is known to be optimal for the one-fast-one-slow two-server system. But an optimal policy for the multi-server system is unknown and non-trivial to find. While Reinforcement Learning (RL) has been recognized to have great potential for learning policies in such cases, our problem has an exponentially large state space size, rendering standard RL inefficient. In this work, we propose ACHQ, an efficient policy gradient based algorithm with a low dimensional soft threshold policy parameterization that leverages the underlying queueing structure. We provide stationary-point convergence guarantees for the general case and despite the low-dimensional parameterization prove that ACHQ converges to an approximate global optimum for the special case of two servers. Simulations demonstrate an improvement in expected response time of up to ${\sim}30%$ over the greedy policy that routes to the fastest available server.

Many multi-agent systems in practice are decentralized and have dynamically varying dependencies. There has been a lack of attempts in the literature to analyze these systems theoretically. In this paper, we propose and theoretically analyze a decentralized model with dynamically varying dependencies called the Locally Interdependent Multi-Agent MDP. This model can represent problems in many disparate domains such as cooperative navigation, obstacle avoidance, and formation control. Despite the intractability that general partially observable multi-agent systems suffer from, we propose three closed-form policies that are theoretically near-optimal in this setting and can be scalable to compute and store. Consequentially, we reveal a fundamental property of Locally Interdependent Multi-Agent MDP’s that the partially observable decentralized solution is exponentially close to the fully observable solution with respect to the visibility radius. We then discuss extensions of our closed-form policies to further improve tractability. We conclude by providing simulations to investigate some long horizon behaviors of our closed-form policies.

Recent advances in diffusion models have demonstrated their strong capabilities in generating high-fidelity samples from complex distributions through an iterative refinement process. Despite the empirical success of diffusion models in motion planning and control, the model-free nature of these methods does not leverage readily available model information and limits their generalization to new scenarios beyond the training data (e.g., new robots with different dynamics). In this work, we introduce Model-Based Diffusion (MBD), an optimization approach using the diffusion process to solve trajectory optimization (TO) problems without data. The key idea is to explicitly compute the score function by leveraging the model information in TO problems, which is why we refer to our approach as model-based diffusion. Moreover, although MBD does not require external data, it can be naturally integrated with data of diverse qualities to steer the diffusion process. We also reveal that MBD has interesting connections to sampling-based optimization. Empirical evaluations show that MBD outperforms state-of-the-art reinforcement learning and sampling-based TO methods in challenging contact-rich tasks. Additionally, MBD’s ability to integrate with data enhances its versatility and practical applicability, even with imperfect and infeasible data (e.g., partial-state demonstrations for high-dimensional humanoids), beyond the scope of standard diffusion models. Videos and codes are available in the supplementary materials.

We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each time, an agent has access to predictions of local cost functions for the next $k$ time steps in an $r$-hop neighborhood. Our work proposes a novel online algorithm, Localized Predictive Control (LPC), which generalizes predictive control to multi-agent systems. We show that LPC achieves a competitive ratio of $1 + \tilde{O}(\rho_T^k) + \tilde{O}(\rho_S^r)$ in an adversarial setting, where $\rho_T$ and $\rho_S$ are constants in $(0, 1)$ that increase with the relative strength of temporal and spatial interaction costs, respectively. This is the first competitive ratio bound on decentralized predictive control for networked online convex optimization. Further, we show that the dependence on $k$ and $r$ in our results is near optimal by lower bounding the competitive ratio of any decentralized online algorithm.

Stabilizing an unknown dynamical system is one of the central problems in control theory. In this paper, we study the sample complexity of the learn-to-stabilize problem in Linear Time-Invariant (LTI) systems on a single trajectory. Current state-of-the-art approaches require a sample complexity linear in $n$, the state dimension, which incurs a state norm that blows up exponentially in $n$. We propose a novel algorithm based on spectral decomposition that only needs to learn ``a small part'' of the dynamical matrix acting on its unstable subspace. We show that, under proper assumptions, our algorithm stabilizes an LTI system on a single trajectory with $O(k \log n)$ samples, where $k$ is the instability index of the system. This represents the first sub-linear sample complexity result for the stabilization of LTI systems under the regime when $k = o(n)$.

We study Model Predictive Control (MPC) and propose a general analysis pipeline to bound its dynamic regret. The pipeline first requires deriving a perturbation bound for a finite-time optimal control problem. Then, the perturbation bound is used to bound the per-step error of MPC, which leads to a bound on the dynamic regret. Thus, our pipeline reduces the study of MPC to the well-studied problem of perturbation analysis, enabling the derivation of regret bounds of MPC under a variety of settings. To demonstrate the power of our pipeline, we use it to generalize existing regret bounds on MPC in linear time-varying (LTV) systems to incorporate prediction errors on costs, dynamics, and disturbances. Further, our pipeline leads to regret bounds on MPC in systems with nonlinear dynamics and constraints.

We study predictive control in a setting where the dynamics are time-varying and linear, and the costs are time-varying and well-conditioned. At each time step, the controller receives the exact predictions of costs, dynamics, and disturbances for the future $k$ time steps. We show that when the prediction window $k$ is sufficiently large, predictive control is input-to-state stable and achieves a dynamic regret of $O(\lambda^k T)$, where $\lambda < 1$ is a positive constant. This is the first dynamic regret bound on the predictive control of linear time-varying systems. We also show a variation of predictive control obtains the first competitive bound for the control of linear time-varying systems: $1 + O(\lambda^k)$. Our results are derived using a novel proof framework based on a perturbation bound that characterizes how a small change to the system parameters impacts the optimal trajectory.

We study multi-agent reinforcement learning (MARL) in a stochastic network of agents. The objective is to find localized policies that maximize the (discounted) global reward. In general, scalability is a challenge in this setting because the size of the global state/action space can be exponential in the number of agents. Scalable algorithms are only known in cases where dependencies are static, fixed and local, e.g., between neighbors in a fixed, time-invariant underlying graph. In this work, we propose a Scalable Actor Critic framework that applies in settings where the dependencies can be non-local and stochastic, and provide a finite-time error bound that shows how the convergence rate depends on the speed of information spread in the network. Additionally, as a byproduct of our analysis, we obtain novel finite-time convergence results for a general stochastic approximation scheme and for temporal difference learning with state aggregation, which apply beyond the setting of MARL in networked systems.

We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. Additionally, we specialize the result to asynchronous $Q$-learning. The resulting bound matches the sharpest available bound for synchronous $Q$-learning, and improves over previous known bounds for asynchronous $Q$-learning.

It has long been recognized that multi-agent reinforcement learning (MARL) faces significant scalability issues due to the fact that the size of the state and action spaces are exponentially large in the number of agents. In this paper, we identify a rich class of networked MARL problems where the model exhibits a local dependence structure that allows it to be solved in a scalable manner. Specifically, we propose a Scalable Actor-Critic (SAC) method that can learn a near optimal localized policy for optimizing the average reward with complexity scaling with the state-action space size of local neighborhoods, as opposed to the entire network. Our result centers around identifying and exploiting an exponential decay property that ensures the effect of agents on each other decays exponentially fast in their graph distance.

Data Center Networks (DCNs) have become more extensively applied in cloud computing in recent years. One important mission for DCNs is to satisfy the fluctuation of on-demand resources for tenants. Existing works fail to fully consider the placement techniques and the elasticity of the physical resource in the DCN at the same time during the scaling of virtual clusters (VCs). To address this, we use elasticity to measure the scaling potential of VCs in terms of both computation and communication resources. In this paper, we consider elastic scaling for existing VCs to maximize the elasticity with the constraint of communication cost in the DCN. We achieve this through a resource allocation scheme, VCS, which comes with provable optimality guarantees for single VC scaling. After that, we extend our scheme for multiple VCs scaling, and we prove that scaling multiple VCs for the over-time elasticity maximization problem is NP-hard. We propose heuristic algorithms MVCS and OMVCS for both offline and online conditions for the multiple VCs scaling. Extensive simulations demonstrate that our elastic VC scaling placement schemes outperform existing state-of-the-art methods in terms of flexibility in the DCN.

Fat trees are considered suitable structures for data center interconnection networking. Such structures are rigid, and hard to scale up and scale out. A good data center network structure should have high scalability, efficient switch utilization, and high reliability. In this paper we present a class of data center network structures based on hypergraph theory and combinatorial block design theory. We show that our data center network structures are more flexible and scalable than fat trees. Using switches of the same size, our data center network structures can connect more nodes than fat trees, and it is possible to construct different structures with tradeoffs among inter-cluster communication capacity, reliability, the number of switches used, and the number of connected nodes.

Fat trees are considered suitable structures for data center interconnection networking. Such structures are rigid, and hard to scale up and scale out. A good data center network structure should have high scalability, efficient switch utilization, and high reliability. In this paper we present a class of data center network structures based on hypergraph theory and combinatorial block design theory. We show that our data center network structures are more flexible and scalable than fat trees. Using switches of the same size, our data center network structures can connect more nodes than fat trees, and it is possible to construct different structures with trade-offs among inter-cluster communication capacity, reliability, the number of switches used, and the number of connected nodes.

Most wind power forecasting methods today take numerical weather prediction (NWP) as their inputs. Therefore, the accuracy of these forecasting methods highly depends on the accuracy of NWP. This paper involves in studying the statistical features of NWP. A total of four error patterns are pre-defined according to the statistical features of NWP. Moreover, an advanced autoregressive integrated moving average (ARIMA) simulator with error information integrated is established to adjust the NWP. Finally, a pair of comparison tests based on support vector machine (SVM) is run with raw NWP and adjusted NWP as inputs respectively. It proves that the adjusted NWP increases forecast accuracy greatly.

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) and its generalization multi-layer CTC(N) (MCTC(N)) switch. In this paper, we propose several generalizations of CTC(N), including SCTC(N, n) (sparse CTC), SMCTC(N, n) (sparse multi-layer CTC) and MSCTC(N, n) (multi-layer sparse CTC). Through analysis and simulations, we show that these generalizations maintain the same performance of their counterparts CTC(N) and MCTC(N), while reducing the cost from O(N2) to O(N log N).

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) switch, which can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in the input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that N schedulers are located in the N input ports, and they operate independently and in parallel without using any arbiter. In this paper, we present a simple fully distributed scheduling algorithm scheme and show its effectiveness by simulations.

We propose an innovative agile crossbar switch architecture called contention-tolerant crossbar, denoted by CTC(N). Unlike the conventional crossbar and the crossbar with crosspoint buffers, which require complex hardware resolvers to grant one out of multiple output requests, CTC(N) can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that $N$ schedulers are located in N input ports, and they operate independently and in parallel. Without using arbiters and/or crosspoint buffers that require additional chip area, the CTC(N) switch is more scalable than existing crossbars. We analyze the throughput of CTC(N) switch without and with internal speedup by building a queuing model. We show that, under Bernoulli i.i.d. uniform traffic, CTC(N) without internal speedup has worst-case throughput of 63%, and CTC(N) achieves 100% throughput with internal speedup 2. Our simulation results validate our theoretical analysis.

Intelligent cooperative decision-making and wireless communication are more and more used in intelligent transport systems. In this paper, According to the thought of agent-oriented collaborative and use wireless communication, we construct an intelligent transport system framework based on the agent, and set up the experimental environment to realize this construction. It achieves the vehicles individual regarding the urgent region in event agile response, simultaneously can cause outside the urgent region the vehicles individual to make the corresponding decision-making.