CS Paper Radar

Efficient control of multi-agent robust MDPs through tensor trees

Ruohan Wang, Giannis Delimpaltadakis, Luca Laurenti, Sofie Haesaert

eess.SY ·submitted 2026-11-10 07:18 UTC · v1
benchmarktheory

Abstract

This paper introduces a tensor-based framework for controller synthesis of stochastic multi-agent systems under temporal logic specifications that couple the agents, such as one agent reaching its goal only after another agent has reached its own. The agents are modeled as robust Markov decision processes (RMDPs), whose transition probabilities are only known to lie in an ambiguity set, for instance due to abstraction errors, learned models, or uncertain parameters. We show that the decoupled nature of the ambiguity sets allows one to decompose the computation of a lower bound on the satisfaction probabilities into per-agent factors, so that only the per-agent ambiguity sets need to be stored. This leads to improved memory complexity compared to monolithic approaches. We compare our approach with state-of-the-art approaches based on approximate simulation relations and with interval MDP abstractions. On a four-agent ordered reach-avoid benchmark, our approach certifies a lower bound twice as high as the simulation relation- based approach with 20 times less memory, and needs about 200 times less memory than the interval MDP abstraction, even at a resolution with about a million times more joint cells.

Closest papers

Nearest neighbours by meaning across the whole index.

DARSY: A Tool for Data-Driven Abstraction and Policy Synthesis for Stochastic Systems with Unknown Dynamics

eess.SY cs.AIcs.LO ·2026-11-19 ·Thom Badings, Ibon Gracia, Mahdi Nazeri, Morteza Lahijanian, Alessandro Abate
theorycode/data similarity 0.66
Abstract · The tool DARSY and all benchmarks are available at https://github.com/tbadings/darsy

This paper presents DARSY: a software tool for abstraction-based verification and policy synthesis in discrete-time stochastic control systems with unknown dynamics and noise distributions. DARSY requires only a simulator of the system and a Lipschitz bound on its dynamics, and needs no knowledge of dynamics or noise distributions. The tool is fully automated and constructs a finite interval Markov decision process (IMDP) abstraction from sampled transitions, whose probability intervals are obtained via statistical techniques and Lipschitz reasoning. Robust dynamic programming on this IMDP then yields a policy together with a lower bound on the probability that the unknown system satisfies a desired specification. This lower bound holds with a user-specified confidence; that is, it is probably approximately correct (PAC). The tool is implemented in Python and supports general Lipschitz-continuous system dynamics and specifications expressed in syntactically co-safe LTL (scLTL), which includes reach-avoid and finite-horizon safety specifications as special cases. Beyond standard IMDPs, DARSY implements a two-layer IMDP (2IMDP) abstraction that also bounds the probability of transitioning to aggregated state blocks, yielding smaller abstraction errors than IMDP abstractions and, as a result, tighter satisfaction guarantees. We demonstrate DARSY's broad applicability across a variety of benchmarks and specifications.

0.38

Data-Driven Factored Abstractions of Stochastic Systems

eess.SY ·2026-11-18 ·Mahdi Nazeri, Frederik Baymler Mathiesen, Sadegh Soudjani, Alessandro Abate
benchmark similarity 0.65
Abstract

Formal verification and correct-by-design policy synthesis for stochastic dynamical systems face significant scalability challenges due to the curse of dimensionality. These challenges are exacerbated when the system dynamics are unknown and abstractions must be constructed from data. This paper introduces a data-driven framework for constructing factored interval Markov decision process (fIMDP) abstractions from noisy transition observations. Assuming conditional independence of successor coordinates and known coordinate-wise Lipschitz bounds on the dynamics, the framework estimates marginal transition probabilities rather than joint probabilities, resulting in an exponential reduction in the number of probability entries to be estimated and stored. We establish finite-sample confidence guarantees that the abstraction captures the concrete transition probabilities uniformly over each abstract region, enabling certified lower bounds on satisfaction probabilities for $ω$-regular specifications. Experiments on benchmark systems, including pendulum swing-up, unicycle control, and a four-dimensional planar robot model, demonstrate improvements in certified satisfaction probability lower bounds of up to 25 percentage points compared with a state-of-the-art flat IMDP abstraction method. Our framework required up to 23x less memory and was consistently faster in constructing the abstraction.

0.27

Scenario MPC with STL Specifications and Pareto-Based Feasibility Repair

cs.RO eess.SY ·2026-09-20 ·Tianhao Wu, Yiwei Lyu
similarity 0.64
Abstract

Temporal logic is a formal language for reasoning about system behaviors over time. Signal temporal logic (STL), in particular, has been used to encode spatio-temporal requirements for control synthesis in multi-agent systems, often under the assumption that agents are cooperative and their dynamics are known. However, real-world multi-agent applications, such as autonomous driving, typically involve stochastic and uncontrollable agents. Recent work explored robust control with worst-case or probabilistic formulations, but remains limited in that it either (1) certifies strict satisfaction of STL constraints without addressing feasibility recovery, or (2) relaxes infeasible constraints with ego-centric objectives. In this paper, we propose a model predictive control (MPC) framework that treats feasibility repair as a Pareto optimization problem to explicitly characterize tradeoffs among agent objectives. We further provide a probabilistic certificate on STL violation rate to formally quantify uncertainty under stochastic and uncontrollable agents. The proposed framework is evaluated on two autonomous driving scenarios. Results show that the framework recovers feasible control with demonstrated safe behaviors.

0.16

Automata-Theoretic Verification of Interval Markov Decision Processes

cs.FL eess.SY ·2026-09-18 ·Sarvin Bahmani, Soumyajit Paul, Sven Schewe, Sadegh Soudjani, Ashutosh Trivedi
publishedtheory similarity 0.64
Abstract · 14 pages including appendices, accepted to CDC 2026

Interval Markov decision processes (IMDPs) provide a natural framework for modeling stochastic systems with uncertain transition probabilities, represented by probability intervals and resolved adversarially. Such uncertainty arises naturally, for example, when the transition model is learned from finite data or obtained through model-based reinforcement learning. In this paper, we study the automata-theoretic verification of IMDPs against rich temporal specifications, including all LTL specifications, by considering the broader class of ω-regular objectives. We show that classical automata-theoretic verification techniques extend to IMDPs, but with a sharp distinction determined by the structure of the transition intervals. For stable IMDPs, where either the upper bound is zero or the lower bound is strictly positive, verification reduces to ordinary MDP analysis and can be carried out using the standard automata used in that setting (good-for-MDP automata). For unstable IMDPs, where intervals may include zero while the upper bound is strictly positive, verification becomes game-like and requires automata whose nondeterminism can be resolved on the fly (good-for-games automata). Building on these insights, we develop algorithms for verifying ω-regular specifications over IMDPs and derive probabilistic guarantees when the interval model is learned from sampled data. The resulting framework enables principled verification of stochastic systems under probabilistic model uncertainty, connecting automata-based verification with data-driven stochastic modeling.

0.32

Generalizable Multi-Agent Planning from Signal Temporal Logic Specifications via Diffusion

cs.MA cs.AIcs.RO ·2026-08-30 ·Joe Eappen, Zikang Xiong, Shreyash S. Iyengar, Suresh Jagannathan
top venuecode/data similarity 0.62
Abstract · Accepted for publication in IEEE Robotics and Automation Letters (RA-L), 2026

Multi-agent systems in the real-world (e.g., drone swarms, autonomous cars, warehouse robots) must satisfy rich, temporal tasks while avoiding collisions. Signal Temporal Logic (STL) elegantly encodes such objectives, but current STL planning methods face critical limitations. State-of-the-art optimization-based approaches can handle arbitrary STL specifications but struggle with scalability, becoming computationally impractical as the number of agents grows. Learning-based methods efficiently handle a large number of agents with rapid planning times but fare poorly when deployment-time objectives differ from those used during training, and do not support planning tasks that require different specifications to be ascribed to different agents (i.e., heterogeneity) or team-level specifications requiring coordination of multiple agents. This fundamental trade-off between generalizability and scalability presents a challenge for realizing multi-agent STL planning algorithms in practice. To overcome this challenge, we introduce a new diffusion method for multi-agent planning with STL specifications. Using a differentiable approximation of STL, we integrate the STL gradient in the denoising process, making our approach generalizable to novel formulas whose predicates are placed anywhere within the goal region covered during training, while achieving the same scalability as existing learning-based methods. Our method supports heterogeneous specifications, and by using diffusion models, naturally enhances plan diversity, thereby significantly reducing safety-related violations (e.g., collisions) among agents. A detailed evaluation study justifies the utility of STL-guided diffusion-based multi-agent planners for constructing generalizable, scalable, and diverse plans. Videos and code are available at https://www.jeappen.com/diff-ma-stl/ and https://github.com/jeappen/diff-ma-stl .

0.59

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

cs.MA ·2026-09-08 ·Xiangwu Wang, Chengwei Cao, Hongyuan Tang
theory similarity 0.62
Abstract · 15 pages, 4 figures, including references and appendices

Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.

0.37

Learning Rational Strategies for Temporal Objectives in Multi-Agent Systems

cs.LG cs.LOcs.MA ·2026-10-15 ·Omar Adalat, Edwin Hamel-De le Court, Francesco Belardinelli
similarity 0.62
Abstract

We study rational synthesis for stochastic multi-agent systems with unknown dynamics, where each agent is equipped with its own probabilistic temporal objective specified using Probabilistic Linear Temporal Logic on Finite Traces ($\mathsf{PLTL}_f}$). We impose solution concepts (e.g., Nash equilibrium, subgame-perfect equilibrium) as constraints on the joint strategy profile, using payoffs derived from each agent's probability of satisfying its temporal objective. In particular, we formulate per-agent rational synthesis as finding a strategy profile -- if one exists -- such that (i) the designated agent's probabilistic temporal constraint is satisfied, and (ii) the profile represents a stable solution under a chosen solution concept. We give conditional convergence guarantees for tabular Nash-Q learning, certify satisfaction with simultaneous finite-sample confidence bounds, and assess strategic stability with approximate best-response checking. Our approach operates in a stochastic \emph{Multi-Agent Reinforcement Learning} (MARL) environment, where model-free learning algorithms attempt to attain extremal satisfaction probabilities for temporal objectives automatically compiled into reward automata. Our approach is empirically validated using 8 general-sum concurrent stochastic games.

0.15

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

cs.AI ·2026-10-11 ·Tomer Massas, Vadim Indelman
similarity 0.62
Abstract · 33 pages, including appendix

MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.

0.28