3 Search Results for "Brozek, Vaclav"

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2024.133

Finite-Memory Strategies for Almost-Sure Energy-MeanPayoff Objectives in MDPs

Authors: Mohan Dantam and Richard Mayr

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We consider finite-state Markov decision processes with the combined Energy-MeanPayoff objective. The controller tries to avoid running out of energy while simultaneously attaining a strictly positive mean payoff in a second dimension. We show that finite memory suffices for almost surely winning strategies for the Energy-MeanPayoff objective. This is in contrast to the closely related Energy-Parity objective, where almost surely winning strategies require infinite memory in general. We show that exponential memory is sufficient (even for deterministic strategies) and necessary (even for randomized strategies) for almost surely winning Energy-MeanPayoff. The upper bound holds even if the strictly positive mean payoff part of the objective is generalized to multidimensional strictly positive mean payoff. Finally, it is decidable in pseudo-polynomial time whether an almost surely winning strategy exists.

Cite as

Mohan Dantam and Richard Mayr. Finite-Memory Strategies for Almost-Sure Energy-MeanPayoff Objectives in MDPs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 133:1-133:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dantam_et_al:LIPIcs.ICALP.2024.133,
  author =	{Dantam, Mohan and Mayr, Richard},
  title =	{{Finite-Memory Strategies for Almost-Sure Energy-MeanPayoff Objectives in MDPs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{133:1--133:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.133},
  URN =		{urn:nbn:de:0030-drops-202762},
  doi =		{10.4230/LIPIcs.ICALP.2024.133},
  annote =	{Keywords: Markov decision processes, energy, mean payoff, parity, strategy complexity}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2010.108

One-Counter Stochastic Games

Authors: Tomás Brázdil, Václav Brozek, and Kousha Etessami

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract

We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on the transition graph of classic one-counter automata. We study primarily the termination objective, where the goal of one player is to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives that are closely related to some well-studied objectives for stochastic games with rewards. Examples of problems we address include: does player 1 have a strategy to ensure that the counter eventually hits 0, i.e., terminates, almost surely, regardless of what player 2 does? Or that the $liminf$ (or $limsup$) counter value equals $infty$ with a desired probability? Or that the long run average reward is $>0$ with desired probability? We show that the qualitative termination problem for OC-SSGs is in $NP$ intersect $coNP$, and is in P-time for 1-player OC-SSGs, or equivalently for one-counter Markov Decision Processes (OC-MDPs). Moreover, we show that quantitative limit problems for OC-SSGs are in $NP$ intersect $coNP$, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.

Cite as

Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 108-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2010.108,
  author =	{Br\'{a}zdil, Tom\'{a}s and Brozek, V\'{a}clav and Etessami, Kousha},
  title =	{{One-Counter Stochastic Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{108--119},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.108},
  URN =		{urn:nbn:de:0030-drops-28571},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.108},
  annote =	{Keywords: one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1837

Qualitative Reachability in Stochastic BPA Games

Authors: Tomas Brazdil, Vaclav Brozek, Antonin Kucera, and Jan Obdrzalek

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

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 $\textbf{NP} \cap \textbf{co-NP}$. 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.

Cite as

Tomas Brazdil, Vaclav Brozek, Antonin Kucera, and Jan Obdrzalek. Qualitative Reachability in Stochastic BPA Games. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 207-218, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.STACS.2009.1837,
  author =	{Brazdil, Tomas and Brozek, Vaclav and Kucera, Antonin and Obdrzalek, Jan},
  title =	{{Qualitative Reachability in Stochastic BPA Games}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{207--218},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1837},
  URN =		{urn:nbn:de:0030-drops-18375},
  doi =		{10.4230/LIPIcs.STACS.2009.1837},
  annote =	{Keywords: Stochastic games, Reachability, Pushdown automata}
}

Refine by Author
1 Brazdil, Tomas
1 Brozek, Vaclav
1 Brozek, Václav
1 Brázdil, Tomás
1 Dantam, Mohan
Show More...

Refine by Classification
1 Mathematics of computing → Probability and statistics
1 Theory of computation → Random walks and Markov chains

Refine by Keyword
1 Markov decision process
1 Markov decision processes
1 Pushdown automata
1 Reachability
1 Stochastic games
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2009
1 2010
1 2024