Author name cluster

Maximilian Weininger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

AAMAS Conference 2026 Conference Paper

Perception-Based Beliefs for POMDPs with Visual Observations

Miriam Schäfers
Merlijn Krale
Thiago D. Simão
Nils Jansen
Maximilian Weininger

Partially observable Markov decision processes (POMDPs) are a principled planning model for sequential decision-making under uncertainty. Yet, real-world problems with high-dimensional observations—such as camera images—remain intractable for traditional belief- and filtering-based solvers. To tackle this problem, we introduce the Perception-based Beliefs for POMDPs framework (PBP), which complements such solvers with a perception model. This model takes the form of an image classifier which maps visual observations to probability distributions over states. PBP incorporates these distributions directly into belief updates, so the underlying solver does not need to reason explicitly over high-dimensional observation spaces. We show that the belief update of PBP coincides with the standard belief update if the image classifier is exact. Moreover, to handle classifier imprecision, we incorporate uncertainty quantification and introduce two methods to adjust the belief update accordingly. We implement PBP using two traditional POMDP solversandempiricallyshowthat(1)itoutperformsexistingend-toend deep RL methods and (2) uncertainty quantification improves robustness of PBP against visual corruption.

PDF

EWRL Workshop 2025 Workshop Paper

Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs

Joshua Wendland
Markel Zubia
Roman Andriushchenko
Maris F. L. Galesloot
Milan Ceska
Henrik von Kleist
Thiago D. Simão
Maximilian Weininger

We introduce *missingness-MDPs* (miss-MDPs); a subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. Miss-MDPs capture settings where, at each step, the current state may go partially missing, that is, the state is not observed. Missingness of observations occurs dynamically and is caused by a *missingness function*, which governs the underlying probabilistic missingness process. Miss-MDPs distinguish the three types of missingness processes as a restriction on the missingness function: missing completely at random (MCAR), missing at random (MAR), and missing not at random (MNAR). Our goal is to compute a policy for a miss-MDP with an *unknown missingness function*. We propose algorithms that, by using a retrospective dataset and based on the different types of missingness processes, approximate the missingness function and, thereby, the true miss-MDP. The algorithms can approximate a subset of MAR and MNAR missingness functions, and we show that, for these, the optimal policy in the approximated model is $\varepsilon$-optimal in the true miss-MDP. The empirical evaluation confirms these findings. Additionally, it shows that our approach becomes more sample-efficient when exploiting the type of the underlying missingness process.

PDF

AAAI Conference 2025 Conference Paper

Solving Robust Markov Decision Processes: Generic, Reliable, Efficient

Tobias Meggendorfer
Maximilian Weininger
Patrick Wienhöft

Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In *robust* MDP (RMDP), every action is associated with an *uncertainty set* of probability distributions, modelling that transition probabilities are not known precisely. Based on the known theoretical connection to stochastic games, we provide a framework for solving RMDPs that is generic, reliable, and efficient. It is *generic* both with respect to the model, allowing for a wide range of uncertainty sets, including but not limited to intervals, L1- or L2-balls, and polytopes; and with respect to the objective, including long-run average reward, undiscounted total reward, and stochastic shortest path. It is *reliable*, as our approach not only converges in the limit, but provides precision guarantees at any time during the computation. It is *efficient* because -- in contrast to state-of-the-art approaches -- it avoids explicitly constructing the underlying stochastic game. Consequently, our prototype implementation outperforms existing tools by several orders of magnitude and can solve RMDPs with a million states in under a minute.

PDF Details DOI

GandALF Workshop 2025 Workshop Paper

Sound Value Iteration for Simple Stochastic Games

Muqsit Azeem
Jan Kretinsky
Maximilian Weininger

Algorithmic analysis of Markov decision processes (MDP) and stochastic games (SG) in practice relies on value-iteration (VI) algorithms. Since basic VI does not provide guarantees on the precision of the result, variants of VI have been proposed that offer such guarantees. In particular, sound value iteration (SVI) not only provides precise lower and upper bounds on the result, but also converges faster in the presence of probabilistic cycles. Unfortunately, it is neither applicable to SG, nor to MDP with end components. In this paper, we extend SVI and cover both cases. The technical challenge consists mainly in proper treatment of end components, which require different handling than in the literature. Moreover, we provide several optimizations of SVI. Finally, we evaluate our prototype implementation experimentally to demonstrate its potential on systems with probabilistic cycles.

PDF Details DOI

I&C Journal 2022 Journal Article

Comparison of algorithms for simple stochastic games

Jan Křetínský
Emanuel Ramneantu
Alexander Slivinskiy
Maximilian Weininger

Simple stochastic games are turn-based 2½-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms – value iteration, strategy iteration and quadratic programming – both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3. 0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.

Details DOI

I&C Journal 2022 Journal Article

Value iteration for simple stochastic games: Stopping criterion and learning algorithm

Julia Eisentraut
Edon Kelmendi
Jan Křetínský
Maximilian Weininger

The classical problem of reachability in simple stochastic games is typically solved by value iteration (VI), which produces a sequence of under-approximations of the value of the game, but is only guaranteed to converge in the limit. We provide an additional converging sequence of over-approximations, based on an analysis of the game graph. Together, these two sequences entail the first error bound and hence the first stopping criterion for VI on simple stochastic games, indicating when the algorithm can be stopped for a given precision. Consequently, VI becomes an anytime algorithm returning the approximation of the value and the current error bound. We further use this error bound to provide a learning-based asynchronous VI algorithm; it uses simulations and thus often avoids exploring the whole game graph, but still yields the same guarantees. Finally, we experimentally show that the overhead for computing the additional sequence of over-approximations often is negligible.

Details DOI

Highlights Conference 2021 Conference Abstract

Comparison of Algorithms for Simple Stochastic Games

Maximilian Weininger

Simple stochastic games are turn-based 2. 5-player zero-sum games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this work, we compare the three known classes of algorithms — value iteration, strategy iteration and quadratic programming — both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3, thereby providing the first implementation of quadratic programming for solving simple stochastic games. This is joint work with Jan Kretinsky, Emanuel Ramneantu and Alexander Slivinskiy. It has been published at GandALF 2020 (https: //arxiv. org/abs/2009. 10882v1) and the respective presentation (https: //www. youtube. com/watch? v=kEvJg7xJOv4) won the best video award.

Details

GandALF Workshop 2021 Workshop Paper

Stochastic Games with Disjunctions of Multiple Objectives

Tobias Winkler
Maximilian Weininger

Stochastic games combine controllable and adversarial non-determinism with stochastic behavior and are a common tool in control, verification and synthesis of reactive systems facing uncertainty. Multi-objective stochastic games are natural in situations where several - possibly conflicting - performance criteria like time and energy consumption are relevant. Such conjunctive combinations are the most studied multi-objective setting in the literature. In this paper, we consider the dual disjunctive problem. More concretely, we study turn-based stochastic two-player games on graphs where the winning condition is to guarantee at least one reachability or safety objective from a given set of alternatives. We present a fine-grained overview of strategy and computational complexity of such disjunctive queries (DQs) and provide new lower and upper bounds for several variants of the problem, significantly extending previous works. We also propose a novel value iteration-style algorithm for approximating the set of Pareto optimal thresholds for a given DQ.

PDF Details DOI

Highlights Conference 2020 Conference Abstract

Approximating Values of Generalized-Reachability Stochastic Games

Maximilian Weininger

Simple stochastic games are turn-based 2. 5-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In the presentation, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound.

PDF Details

GandALF Workshop 2020 Workshop Paper

Comparison of Algorithms for Simple Stochastic Games

Jan Křetínský
Emanuel Ramneantu
Alexander Slivinskiy
Maximilian Weininger

Simple stochastic games are turn-based 2. 5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms – value iteration, strategy iteration and quadratic programming – both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3. 0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.

PDF Details DOI