6 papers
On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics
Marnix Suilen, Guillermo A. Pérez
Robust Markov decision processes (RMDPs) extend standard Markov decision processes (MDPs) to account for uncertainty in the transition probabilities. RMDPs have an uncertainty set…
Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
Alexis de Colnet, Floris Geerts, Rihan Hai +4
Strongly simulating a quantum circuit, that is, computing an output amplitude, can be done by summing the circuit's Feynman paths: a weighted count over assignments to Boolean path…
Visibly Recursive Automata
Kévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez +1
As an alternative to visibly pushdown automata, we introduce visibly recursive automata (VRAs), composed of a set of classical automata that can call each other. VRAs are a strict…
A Theory of Hanoi Omega-Automata and Games
Emmanuel Filiot, Allen Joseph, Guillermo A. Pérez +1
The Hanoi Omega-Automata (HOA) format has established itself as the definitive standard for encoding -regular automata in modern synthesis tools. While HOA is widely adopted du…
Computing the Reachability Value of Posterior-Deterministic POMDPs
Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev +2
Partially observable Markov decision processes (POMDPs) are a fundamental model for sequential decision-making under uncertainty. However, many verification and synthesis problems…
Data-Efficient Safe Policy Improvement Using Parametric Structure
Kasper Engelen, Guillermo A. Pérez, Marnix Suilen
Safe policy improvement (SPI) is an offline reinforcement learning problem in which a new policy that reliably outperforms the behavior policy with high confidence needs to be comp…