Author name cluster

Václav Brožek

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.

5 papers

1 author row

I&C Journal 2013 Journal Article

Approximating the termination value of one-counter MDPs and stochastic games

Tomáš Brázdil
Václav Brožek
Kousha Etessami
Antonín Kučera

One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of classic one-counter automata (equivalently, pushdown automata with a 1-letter stack alphabet). A key objective for the analysis and verification of these games is the termination objective, where the players aim to maximize (minimize, respectively) the probability of hitting counter value 0, starting at a given control state and given counter value. Recently, we studied qualitative decision problems (“is the optimal termination value equal to 1? ”) for OC-MDPs (and OC-SSGs) and showed them to be decidable in polynomial time (in NP ∩ coNP, respectively). However, quantitative decision and approximation problems (“is the optimal termination value at least p”, or “approximate the termination value within ε”) are far more challenging. This is so in part because optimal strategies may not exist, and because even when they do exist they can have a highly non-trivial structure. It thus remained open even whether any of these quantitative termination problems are computable. In this paper we show that all quantitative approximation problems for the termination value for OC-MDPs and OC-SSGs are computable. Specifically, given an OC-SSG, and given ε > 0, we can compute a value v that approximates the value of the OC-SSG termination game within additive error ε, and furthermore we can compute ε-optimal strategies for both players in the game. A key ingredient in our proofs is a subtle martingale, derived from solving certain linear programs that we can associate with a maximizing OC-MDP. An application of Azumaʼs inequality on these martingales yields a computable bound for the “wealth” at which a “rich personʼs strategy” becomes ε-optimal for OC-MDPs.

Details DOI

TCS Journal 2013 Journal Article

Determinacy and optimal strategies in infinite-state stochastic reachability games

Václav Brožek

We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality ∼ ∈ { >, ≥ } and a threshold p, either Player Max has a strategy which forces the value of the game to satisfy ∼ p against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, then this game is strongly determined. This significantly generalises, e. g. , recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because the roles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as well. The other result is finding a subclass of stochastic games where Player Max has an optimal strategy in each state. The subclass is defined by the property that if v is an accumulation point of the set of all values of a game then v = 0. These results complement recent results classifying the existence of an optimal strategy for Player Min, and our general strong-determinacy theorem applies here as well. We also apply our results for Max in the context of recently studied One-Counter stochastic games. This work extends a workshop version of this paper which appeared in GandALF 2011, in particular, we prove a conjecture raised in that paper for the class of all reachability games.

Details DOI

GandALF Workshop 2011 Workshop Paper

Optimal Strategies in Infinite-state Stochastic Reachability Games

Václav Brožek

We consider perfect-information reachability stochastic games for 2 players on infinite graphs. We identify a subclass of such games, and prove two interesting properties of it: first, Player Max always has optimal strategies in games from this subclass, and second, these games are strongly determined. The subclass is defined by the property that the set of all values can only have one accumulation point – 0. Our results nicely mirror recent results for finitely-branching games, where, on the contrary, Player Min always has optimal strategies. However, our proof methods are substantially different, because the roles of the players are not symmetric. We also do not restrict the branching of the games. Finally, we apply our results in the context of recently studied One-Counter stochastic games.

PDF Details DOI

I&C Journal 2011 Journal Article

Qualitative reachability in stochastic BPA games

Tomáš Brázdil
Václav Brožek
Antonín Kučera
Jan Obdržálek

We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint ‘>0’ or ‘=1’. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in P for the ‘>0’ constraint, and in NP ∩ co - NP for the ‘=1’ constraint. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively.

Details DOI

I&C Journal 2008 Journal Article

Reachability in recursive Markov decision processes

Tomáš Brázdil
Václav Brožek
Vojtěch Forejt
Antonín Kučera

We consider a class of infinite-state Markov decision processes generated by stateless pushdown automata. This class corresponds to 1 1 2 -player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets S and T of safe and terminal stack configurations, where the membership to S and T depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given x ∈ { 0, 1 }. We show that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states. This result is a generalization of a recent theorem by Etessami and Yannakakis which says that the qualitative termination for 1-exit RMDPs (which exactly correspond to our 1 1 2 -player BPA games) is decidable in polynomial time. Interestingly, the properties of winning strategies for the extended reachability objectives are quite different from the ones for termination, and new observations are needed to obtain the result. As an application, we derive the EXPTIME-completeness of the model-checking problem for 1 1 2 -player BPA games and qualitative PCTL formulae.

Details DOI