30 citations · 45 across the 20 of their papers we have counts for
26 papers
Momba: Network Modernization Improves Multi-Objective Reinforcement Learning
Adam Štafa, Santeri Heiskanen, Petr Novotný +1
Recent advances in deep reinforcement learning (RL) have shown that improving neural network architectures can yield substantial gains in sample efficiency and asymptotic performan…
Refuting Equivalence in Probabilistic Programs with Conditioning
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +1
We consider the problem of refuting equivalence of probabilistic programs, i.e., the problem of proving that two probabilistic programs induce different output distributions. We st…
Equivalence and Similarity Refutation for Probabilistic Programs
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +1
We consider the problems of statically refuting equivalence and similarity of output distributions defined by a pair of probabilistic programs. Equivalence and similarity are two f…
Solving Long-run Average Reward Robust MDPs via Stochastic Games
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi +2
Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty. However, MDPs do not take uncertainty in transition probabilities in…
Proving Non-termination by Program Reversal
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +1
We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal o…
Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný +2
The extension of classical imperative programs with real-valued random variables and random branching gives rise to probabilistic programs. The termination problem is one of the mo…
Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes
Tomas Brazdil, Krishnendu Chatterjee, Petr Novotny +1
Markov decision processes (MDPs) are the defacto frame-work for sequential decision making in the presence ofstochastic uncertainty. A classical optimization criterion forMDPs is t…
Deciding Fast Termination for Probabilistic VASS with Nondeterminism
Tomáš Brázdil, Krishnendu Chatterjee, Antonín Kučera +2
A probabilistic vector addition system with states (pVASS) is a finite state Markov process augmented with non-negative integer counters that can be incremented or decremented duri…
On the Complexity of Value Iteration
Nikhil Balaji, Stefan Kiefer, Petr Novotný +2
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal -step payoff by iterating times a recurrence equation which…
Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives
Krishnendu Chatterjee, Adrián Elgyütt, Petr Novotný +1
Partially-observable Markov decision processes (POMDPs) with discounted-sum payoff are a standard framework to model a wide range of problems related to decision making under uncer…
Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Tomáš Brázdil, Krishnendu Chatterjee, Antonín Kučera +3
Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract…
Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs
Sheshansh Agrawal, Krishnendu Chatterjee, Petr Novotný
Probabilistic programs extend classical imperative programs with real-valued random variables and random branching. The most basic liveness property for such programs is the termin…
Efficient Algorithms for Checking Fast Termination in VASS
Tomáš Brázdil, Krishnendu Chatterjee, Antonín Kučera +2
Vector Addition Systems with States (VASS) consists of a finite state space equipped with d counters, where in each transition every counter is incremented, decremented, or left un…
Stochastic Invariants for Probabilistic Termination
Krishnendu Chatterjee, Petr Novotný, Đorđe Žikelić
Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the quali…
Optimizing Expectation with Guarantees in POMDPs (Technical Report)
Krishnendu Chatterjee, Petr Novotný, Guillermo A. Pérez +2
A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may st…
Optimizing the Expected Mean Payoff in Energy Markov Decision Processes
Tomáš Brázdil, Antonín Kučera, Petr Novotný
Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP confi…
Stability in Graphs and Games
Tomáš Brázdil, Vojtěch Forejt, Antonín Kučera +1
We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, giv…
Stochastic Shortest Path with Energy Constraints in POMDPs
Tomáš Brázdil, Krishnendu Chatterjee, Martin Chmelík +2
We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimiz…
Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs
Krishnendu Chatterjee, Hongfei Fu, Petr Novotny +1
In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: 1. qualitative ones that ask (i) whether the program termi…
Long-Run Average Behaviour of Probabilistic Vector Addition Systems
Tomas Brazdil, Stefan Kiefer, Antonin Kucera +1
We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of fin…
Optimizing Performance of Continuous-Time Stochastic Systems using Timeout Synthesis
Tomáš Brázdil, Ľuboš Korenčiak, Jan Krčál +2
We consider parametric version of fixed-delay continuous-time Markov chains (or equivalently deterministic and stochastic Petri nets, DSPN) where fixed-delay transitions are specif…
Minimizing Running Costs in Consumption Systems
Tomáš Brázdil, David Klaška, Antonín Kučera +1
A standard approach to optimizing long-run running costs of discrete systems is based on minimizing the mean-payoff, i.e., the long-run average amount of resources ("energy") consu…
Zero-Reachability in Probabilistic Multi-Counter Automata
Tomáš Brázdil, Stefan Kiefer, Antonín Kučera +2
We study the qualitative and quantitative zero-reachability problem in probabilistic multi-counter systems. We identify the undecidable variants of the problems, and then we concen…
Solvency Markov Decision Processes with Interest
Tomáš Brázdil, Taolue Chen, Vojtěch Forejt +2
Solvency games, introduced by Berger et al., provide an abstract framework for modelling decisions of a risk-averse investor, whose goal is to avoid ever going broke. We study a ne…