CS Paper Radar

Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics

Menno van Zutphen, Adrien Banse, Domagoj Herceg, Giannis Delimpaltadakis, Duarte Antunes

eess.SY math.DSmath.OC ·submitted 2026-10-02 07:44 UTC · v1
theory

Abstract

Finite-state interval Markov-chain (IMC) abstractions provide sound verification and performance bounds for continuous-state stochastic systems by enclosing cell-to-cell transition probabilities and costs in intervals. Finite-state Markovian abstractions are generally lossy, as state aggregation often destroys the Markov property. Recently, memory-dependent Markov-chain (MC) abstractions of stochastic systems have been developed to mitigate this by recording recently visited cells. In this paper, we develop the memory-dependent extension of IMC abstractions. Building on the insight that memory narrows the family of state distributions that could occur inside the current cell, we prove that memory tightens the local intervals, at the price of a larger abstraction. We also formulate no-memory IMC abstractions, tightening classic IMC abstraction intervals without enlarging the state space. To characterize spatial refinement relative to memory, we derive two cost-guarantee tightness upper bounds. The bounds depend, respectively, on cell size, and on the worst-case remaining distributional ambiguity after filtering over the remembered past. We then specialize our result to linear-Gaussian systems, for which we derive a closed-form upper bound on this ambiguity. Numerical examples show that the memory-dependent and no-memory constructions can produce tighter expected-cost intervals than comparable partition refined models.

Closest papers

Nearest neighbours by meaning across the whole index.

Data-Driven Factored Abstractions of Stochastic Systems

eess.SY ·2026-11-18 ·Mahdi Nazeri, Frederik Baymler Mathiesen, Sadegh Soudjani, Alessandro Abate
benchmark similarity 0.64
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

Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

cs.LO ·2026-11-16 ·Bingqing Hu, Landon Taylor, Zhen Zhang
similarity 0.60
Abstract

Abstracting a continuous-time Markov chain by grouping its states into blocks raises a fundamental question: which rates should the abstract chain use when states within a block have different exit rates and transition probabilities? We study harmonic-mean aggregation, which matches the mean waiting time and next-block distribution of a local experiment that uniformly selects a state within the block and observes its next jump. Equivalently, the abstract transition rates are averages of the concrete rates with inverse-exit-rate weights. Since the aggregation does not preserve reachability probabilities in general, we derive theoretical error bounds for time-bounded reachability. We decompose the error into a blockwise mean and centered-within-block deviations, and show that the rate mismatch has zero weighted mean. Exploiting this cancellation and differences between abstract reachability values, we obtain bounds valid at every time horizon through a linear comparison system with two quantities per block, without computing concrete reachability values. All results are formalized and proven in Lean 4.

0.35

Path Abstraction for Markov Reward Models

cs.FL cs.LO ·2026-08-25 ·Arnd Hartmanns, Robert Modderman
theory similarity 0.59
Abstract

Path abstraction originated as a technique for counterexample refinement in probabilistic model checking. Given a discrete-time Markov chain, it summarises the probabilities passing through a subset of the states onto new transitions of a smaller chain. In earlier work, we proved its correctness and that it is monotonically absorbing. In this paper, we extend path abstraction from reachability probabilities on discrete-time Markov chains to expected rewards on Markov reward models. Working in a novel free monoid view of Markov chains throughout, we prove that path abstraction preserves the Markov reward model structure when abstracting over arbitrary sets of states, and that it remains monotonically absorbing. Finally, we give a numerical recipe, accompanied by a reference implementation in PARI/GP, that computes path abstraction by solving linear equation systems. Its correctness rests on the relationship between expected rewards and expected visiting times of transitions.

0.19

Efficient control of multi-agent robust MDPs through tensor trees

eess.SY ·2026-11-10 ·Ruohan Wang, Giannis Delimpaltadakis, Luca Laurenti, Sofie Haesaert
benchmarktheory similarity 0.58
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.

0.14

TTL Approximations for a Family of CLOCK-Like Cache Replacement Policies

cs.OS cs.PF ·2026-11-18 ·Yirong Wang, Peter Desnoyers, Benny Van Houdt
top venue similarity 0.58
Abstract · Accepted and presented at IFIP Performance 2026. To appear in ACM SIGMETRICS Performance Evaluation Review

While CLOCK-like cache replacement policies are highly appealing in practice due to their frugal memory usage and implementation simplicity, analytical models for their performance remain limited. The difficulty stems from the "eviction hand" itself. As it scans sequentially for an evictee, sparing objects with survival counters along the way, it inherently entangles the state of one cached object with the next. This strong coupling heavily obscures the system's steady state. To address this gap, we introduce a time-to-live (TTL) approximation for a family of eviction policies---which we term CLOCK($K$)---that decouples individual object dynamics using a globally fixed timer. In contrast to the intrinsic coupling induced by assuming a fixed cache capacity, such a TTL proxy yields a tractable matrix-analytic solution for the steady-state miss ratio functions across a broad and highly expressive class of phase-type renewal traffic. Among other benefits, this effectively reduces the analysis per-object to solving a linear system of order $O(Kd)$, where $d$ is the phase dimension. Moreover, our model for CLOCK($K$) recovers the canonical CLOCK when $K=1$ and FIFO when $K=0$, while empirically exhibiting Schur-concavity under the Independent Reference Model (IRM). Finally, we validate the model against a suite of trace-driven simulations.

0.36

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.58
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

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.58
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

Towards a Formal Definition of Agent Memory: Basis, Span, Optimality, and the Sequential Memory Problem

cs.LG ·2026-08-12 ·Hongyao Tang
similarity 0.58
Abstract

Despite the wide deployment of memory in large-model agents, there is no unified formal account of what a memory is or when it is optimal. This paper takes a first step toward this account. The central idea is that memory is a basis, knowledge is its span, and answerability is a coverage problem: an agent stores events extracted from a material; a generation operator turns any event set into the knowledge it entails; and a query is answerable exactly when some single item in the span covers it. The optimal memory is then the capacity-constrained maximizer of expected coverage, and its value traces a utility--capacity frontier, the common yardstick on which memory systems can be compared. Next, we consider noise in the memory and discuss coverage versus precision under it: a memory may store false claims, so the write policy must infer the truth of what it stores. Drawing an analogy with biological memory, which is formed continuously through ongoing experience, we formalize the continual agent-memory problem in a sequential MDP that covers multiple levels, where memory is the state, writing is the action, and the utility settled at query time is the delayed reward that drives learning. To make the framework concrete, we instantiate it on Homer's \emph{Odyssey}, turning the frontier, the compression zone, and the divergence of coverage from precision into concrete numbers. Finally, we position existing systems within the framework, making ``how good is a memory'' measurable and recasting the open problems of constructing and learning agent memory as concrete research questions.

0.04