CS Paper Radar

Multiobjective Preexpectation Reasoning for Probabilistic Programs

Lena Verscht, Hannah Mertens, Kevin Batz, Sebastian Junges, Benjamin Lucien Kaminski, Joost-Pieter Katoen

cs.PL cs.LO ·submitted 2026-08-13 14:06 UTC · v2
theory

Abstract

Probabilistic programs with nondeterminism model planning problems in which a strategy typically resolves the nondeterminism to meet a specification. We study the multiobjective setting, meeting several specifications at once along a Pareto front, and provide a deductive, program-level account of strategy synthesis. Its core is a multiobjective preexpectation transformer mapping a tuple of postexpectations to the set of simultaneously achievable values, an element of the convex Hoare powerdomain. It conservatively extends weakest preexpectations and lifts standard loop rules. We develop rules to synthesize witnessing strategies as mixed determinizations that solve nondeterminism probabilistically. We prove the transformer and synthesis rules sound against an operational Markov decision process (MDP) semantics, without requiring a finite state space: our approach can be seen as a symbolic approach - at program level - for multiobjective optimization over infinite MDPs. We demonstrate our machinery using two case studies.

Closest papers

Nearest neighbours by meaning across the whole index.

Countable Nondeterminism in Weighted Programming with an Application to Mechanized Foundations for Probabilistic Program Verification

cs.PL cs.LO ·2026-10-29 ·Sebastian Körner, Oliver Emil Bøving, Christoph Matheja
theory similarity 0.64
Abstract

Weighted programming is a framework by Batz et al. for describing mathematical models or optimization problems as imperative programs parametrized over semirings and then analyzing them with program verification techniques like weakest precondition calculi. Applications include reasoning about expected outcomes of probabilistic programs and competitive analysis of online algorithms. We extend weighted programming with (1) countable nondeterminism and (2) user-defined additive rewards, where programs are parametrized over modules instead of semirings. The resulting framework enables reasoning about expected resource consumption of probabilistic programs and about optimal scores of combinatorial games. A technical challenge is that wp-calculi for weighted programs with (1) and (2) over arbitrary modules can be unsound, because it is well-known that continuity properties commonly used in program semantics break in the presence of countable nondeterminism. We study conditions under which a wp-style transformer for reasoning about weighted programs is sound with respect to an operational ground truth defined in terms of weighted decision processes (WDPs) - transition systems that generalize Markov decision processes by drawing transition weights and state rewards from a module. Based on those conditions, we show that a range of concrete instances of the weighted programming framework enjoy sound weakest precondition reasoning. We demonstrate the usefulness of our wp-semantics through case studies for different modules. We mechanized our extended weighted programming framework and our main soundness results in the interactive theorem prover Lean. Instantiating these results for probabilistic programming yields, to the best of our knowledge, the first mechanized proof of a fixed point characterization of minimal expected rewards in Markov decision processes with countable nondeterminism.

0.25

Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

cs.AI ·2026-08-25 ·Durgam Latha, Dion Reji, S. Akshay, Đorđe Žikelić, Shankaranarayanan Krishna
similarity 0.64
Abstract

Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.

0.16

Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability

cs.AI cs.LGcs.RO ·2026-09-09 ·Arnab Chattopadhayay, Debdipta Halder
similarity 0.59
Abstract · Total number of pages: 19, total number of figures: 5

Large language model agents produce fluent action sequences across a wide range of tasks, yet they fail in characteristic ways once the environment becomes partially observable. Ambiguous feedback pushes them into premature commitments. A single informative observation can collapse their uncertainty onto the wrong hypothesis. Policies drift as the history grows. We trace these symptoms to a common structural cause. An LLM agent, as commonly deployed, is a history-conditioned policy with no explicit belief over hidden state. We propose an architectural fix. The Belief-State Engine (BSE) is an inference module placed outside the LLM. It maintains a Bayesian posterior over the latent states of a given POMDP (Partially Observable Markov Decision Process) model, and at each decision step it exposes only that posterior to the LLM. The raw action-observation log is not shown. We set out a minimal four-axiom specification of what a belief-consistent internal state must satisfy, and prove that the LLM paired with the BSE is a sound Markov policy on the belief MDP induced by the underlying POMDP. It therefore inherits the Bellman optimality guarantees of classical POMDP theory, provided the LLM is never exposed to the raw history. We evaluate the architecture on the Tiger POMDP and a red-team attack-graph task, against six baselines: a reactive LLM, Chain-of-Thought, ReAct, a natural-language belief tracker, QMDP, and POMCP. Across both domains, the BSE-augmented agent improves task return, belief calibration, and decision consistency. Ten targeted ablations isolate the contribution of each architectural choice confirms that the effect is not specific to any one model. Code, environment specifications, prompt templates, and seed logs accompany this paper.

0.09

Type-Directed Discretization of Probabilistic Programs (Extended Version)

cs.PL ·2026-08-17 ·Katherine Wu, Jules Jacobs, Kevin Batz, Alexandra Silva
published similarity 0.58
Abstract · Extended version of OOPSLA'26 paper (with appendices)

We study exact discretization as a semantics-preserving transformation for recursive, higher-order probabilistic programs with continuous distributions. We target programs where continuous values are compared against finitely many constants, so exact inference reduces to a discrete problem. Our central technical contribution is a non-local, type-directed analysis that infers where continuous values can be partitioned into finitely many observationally relevant regions, then rewrites sampling and comparison behavior over those regions. We call this transformation Slice. Because this construction is global and type-directed, correctness requires reasoning beyond the local syntax: we formalize the transformation and prove soundness for boolean queries using a coupling-style logical relations argument over operational semantics. As an application, transformed programs can be executed by discrete engines such as Dice, Roulette, and Storm. Our empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and, on benchmarks where direct comparison is possible, it is competitive with state-of-the-art exact inference systems for continuous programs.

0.23

Co-Recursive Semantic Self-Extension: A Mathematical Foundation for Open-Ended Intelligence

cs.AI ·2026-10-22 ·Simon Hegelich, Bardh Prenkaj, Habiba Sarhan, Morteza Shahrezaye, Kolja Hegelich +2 more
similarity 0.57
Abstract

Artificial intelligence has advanced through scale, data, and computation, yet remains bounded by its representational framework. We ask what makes intelligence open-ended. Every inferential system selects meaningful distinctions, limiting what it can learn. Within a fixed purpose, performance reaches a ceiling set by its semantic domain. Teleological succession, in which purposes arise from earlier ones, faces a similar limit: Boolean-closed purpose-transformations exhaust their reachable semantic territory. We shift from purposes to inferential systems. Drawing on Kant and Gödel, we model cognitive states as partial evaluations over a formal language. Unresolved propositions may be undecided or undecidable. Reasoning can resolve the former but not the latter, leaving a frontier for extension. Non-trivial reductions of undecidable propositions expose undecidable intermediate premises whose reflective reification supports multiple decisive extensions. Finite trace-guided generation remains fallible, requiring meta-level selection and polycontextural exploration. Using Kolmogorov complexity, we show that no architecture with a fixed state description, transition mechanism, and initial condition can generate histories incorporating irreducible algorithmic information. Because physical systems are fixed in this sense, we examine collectives. Coupling finitely many finite agents does not remove the bound. Extension requires persistent external memory preserving semantic content and historical coordinates. Collective generative capacity depends on balancing overlap for transfer with difference for generation. We propose semantic self-extension as a design principle: intelligence should not merely resolve ambiguity within existing meanings, but transform unresolved structures into new spaces of meaning, generating new distinctions, questions, representations, and purposes.

0.51

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

The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting

cs.AI ·2026-08-18 ·Nazlı Nur Karabulut, Tanya Braun
published similarity 0.56
Abstract · Full version including appendix of a paper accepted at the 17th International Conference on Scalable Uncertainty Management (SUM2026) under …

Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under uncertainty. However, DecPOMDPs are known to suffer from exponential complexity in the number of agents. One way to combat this intractability in agent numbers is to look at partitions of agents that exhibit a form of symmetry among agents, allowing for a compact encoding by counting. However, a challenge arises as the policy space explodes, even though the model complexity and evaluation cost reduce to a polynomial dependence. In this paper, we redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers for so called policy-counted DecPOMDPs. Further, we present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently.

0.31

Model Checking Probabilistic Multiparty Session Types

cs.PL ·2026-11-10 ·Aleksander Junge, Leo Seojun Lee, Joseph Paulus, Nobuko Yoshida, David Parker
publishedtheory similarity 0.56
Abstract · 108 pages, full version of "Model Checking Probabilistic Multiparty Session Types" appearing at POPL 2027

Distributed systems increasingly rely on randomisation; yet, verification techniques for such systems remain separate from the programming abstractions used to build them. This paper proposes the first probabilistic extension of general multiparty session types - typing sessions bottom-up, with no global specification - deriving quantitative properties of a multiparty session from its session types alone. Our types combine probabilistic choice with nondeterministic choice that abstracts data-dependent control, and allow separated choices, where each branch of a selection or branching may involve a different participant - a combination beyond previous probabilistic multiparty session type systems. To achieve this, we develop a novel probabilistic subtyping relation and merge operator, using which we prove type soundness and session fidelity. The semantics of typing contexts separates nondeterministic resolution, probabilistic choice, and synchronisation, so that every typing context induces a finite Markov decision process. On it, we derive sound lower bounds, holding under every fair adversarial scheduler, on the probability that a session is deadlock-free and live - the first behavioural property guarantees, partial or otherwise, for a probabilistic session calculus. To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.

0.58