3 Search Results for "Jensen, David"


Document
Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration

Authors: Marianne Akian, Stéphane Gaubert, Ulysse Naepels, and Basile Terver

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii-Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an ε-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in O(|log(ε)|) where the constant in the O(⋅) is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in O(ε^{-1}|log(ε)|) obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a O(ε^{-1}) bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii-Mann iteration with respect to Hilbert’s semi-norm.

Cite as

Marianne Akian, Stéphane Gaubert, Ulysse Naepels, and Basile Terver. Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{akian_et_al:LIPIcs.MFCS.2023.10,
  author =	{Akian, Marianne and Gaubert, St\'{e}phane and Naepels, Ulysse and Terver, Basile},
  title =	{{Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.10},
  URN =		{urn:nbn:de:0030-drops-185448},
  doi =		{10.4230/LIPIcs.MFCS.2023.10},
  annote =	{Keywords: Stochastic mean-payoff games, concurrent games, entropy games, relative value iteration, Krasnoselskii-Mann fixed point algorithm, Hilbert projective metric}
}
Document
A Generic Strategy Improvement Method for Simple Stochastic Games

Authors: David Auger, Xavier Badin de Montjoye, and Yann Strozecki

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We present a generic strategy improvement algorithm (GSIA) to find an optimal strategy of simple stochastic games (SSG). We prove the correctness of GSIA, and derive a general complexity bound, which implies and improves on the results of several articles. First, we remove the assumption that the SSG is stopping, which is usually obtained by a polynomial blowup of the game. Second, we prove a tight bound on the denominator of the values associated to a strategy, and use it to prove that all strategy improvement algorithms are in fact fixed parameter tractable in the number r of random vertices. All known strategy improvement algorithms can be seen as instances of GSIA, which allows to analyze the complexity of converge from below by Condon [Condon, 1993] and to propose a class of algorithms generalising Gimbert and Horn’s algorithm [Gimbert and Horn, 2008; Gimbert and Horn, 2009]. These algorithms terminate in at most r! iterations, and for binary SSGs, they do less iterations than the current best deterministic algorithm given by Ibsen-Jensen and Miltersen [Ibsen-Jensen and Miltersen, 2012].

Cite as

David Auger, Xavier Badin de Montjoye, and Yann Strozecki. A Generic Strategy Improvement Method for Simple Stochastic Games. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.MFCS.2021.12,
  author =	{Auger, David and Badin de Montjoye, Xavier and Strozecki, Yann},
  title =	{{A Generic Strategy Improvement Method for Simple Stochastic Games}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.12},
  URN =		{urn:nbn:de:0030-drops-144524},
  doi =		{10.4230/LIPIcs.MFCS.2021.12},
  annote =	{Keywords: Simple Stochastic Games, Strategy Improvement, Parametrized Complexity, Stopping, Meta Algorithm, f-strategy}
}
Document
Leveraging relational autocorrelation with latent group models

Authors: Jennifer Neville and David Jensen

Published in: Dagstuhl Seminar Proceedings, Volume 5051, Probabilistic, Logical and Relational Learning - Towards a Synthesis (2006)


Abstract
The presence of autocorrelation provides strong motivation for using relational techniques for learning and inference. Autocorrelation is a statistical dependency between the values of the same variable on related entities and is a nearly ubiquitous characteristic of relational data sets. Recent research has explored the use of collective inference techniques to exploit this phenomenon. These techniques achieve significant performance gains by modeling observed correlations among class labels of related instances, but the models fail to capture a frequent cause of autocorrelation---the presence of underlying groups that influence the attributes on a set of entities. We propose a latent group model (LGM) for relational data, which discovers and exploits the hidden structures responsible for the observed autocorrelation among class labels. Modeling the latent group structure improves model performance, increases inference efficiency, and enhances our understanding of the datasets. We evaluate performance on three relational classification tasks and show that LGM outperforms models that ignore latent group structure when there is little known information with which to seed inference.

Cite as

Jennifer Neville and David Jensen. Leveraging relational autocorrelation with latent group models. In Probabilistic, Logical and Relational Learning - Towards a Synthesis. Dagstuhl Seminar Proceedings, Volume 5051, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{neville_et_al:DagSemProc.05051.10,
  author =	{Neville, Jennifer and Jensen, David},
  title =	{{Leveraging relational autocorrelation with latent group models}},
  booktitle =	{Probabilistic, Logical and Relational Learning - Towards a Synthesis},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5051},
  editor =	{Luc De Raedt and Thomas Dietterich and Lise Getoor and Stephen H. Muggleton},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05051.10},
  URN =		{urn:nbn:de:0030-drops-4201},
  doi =		{10.4230/DagSemProc.05051.10},
  annote =	{Keywords: Statistical relational learning, probabilistic relational models, latent variable models, autocorrelation, collective inference}
}
  • Refine by Author
  • 1 Akian, Marianne
  • 1 Auger, David
  • 1 Badin de Montjoye, Xavier
  • 1 Gaubert, Stéphane
  • 1 Jensen, David
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Hilbert projective metric
  • 1 Krasnoselskii-Mann fixed point algorithm
  • 1 Meta Algorithm
  • 1 Parametrized Complexity
  • 1 Simple Stochastic Games
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2006
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail