Approximating Values of Generalized-Reachability Stochastic Games

Abstract: Simple stochastic games are turn-based 2½-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In this paper, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound.

02/02/2021

Approximating Values of Generalized-Reachability Stochastic Games

Pranav Ashok, Krishnendu Chatterjee, Jan Kretinsky, Maximilian Weininger, Tobias Winkler

Comments

Similar Papers

Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Games

Brian Hu Zhang, Tuomas Sandholm

Keywords Abstract Paper

What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?

Chi Jin, Praneeth Netrapalli, Michael Jordan

Keywords Abstract Paper

Optimization - Non-convex

Computing Quantal Stackelberg Equilibrium in Extensive-Form Games

Jakub Černý, Viliam Lisý, Branislav Bošanský, Bo An

Keywords Abstract Paper

On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games

Zhengyang Liu, Jiawei Li, Xiaotie Deng

Keywords Abstract Paper

Temporal Induced Self-Play for Stochastic Bayesian Games

Weizhe Chen, Zihan Zhou, Yi Wu, Fei Fang

Keywords Abstract Paper

Agent-based and Multi-agent Systems, Multi-agent Learning, Applications of Reinforcement Learning

The Gambler's Problem and Beyond

Baoxiang Wang, Shuai Li, Jiajin Li, Siu On Chan

Keywords Abstract Paper

the gambler's problem, reinforcement learning, fractal, self-similarity, Bellman equation

Safe Search for Stackelberg Equilibria in Extensive-Form Games

Chun Kai Ling, Noam Brown

Keywords Abstract Paper

Group testing and local search: is there a computational-statistical gap?

Fotis Iliopoulos, Ilias Zadik

Keywords Abstract Paper

Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results

Gabriele Farina, Andrea Celli, Nicola Gatti, Tuomas Sandholm

Keywords Abstract Paper

Theory, Game Theory and Computational Economics

Taming GANs with Lookahead-Minmax

Tatjana Chavdarova, Matteo Pagliardini, Sebastian Stich and François Fleuret, Martin Jaggi

Keywords Abstract Paper

Generative Adversarial Networks, Minmax

Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos

Keywords Abstract Paper

New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice

Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang

Keywords Abstract Paper

Neural Auto-Curricula in Two-Player Zero-Sum Games

Xidong Feng, Oliver Slumbers, Ziyu Wan and Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, Yaodong Yang

Keywords Abstract Paper

deep learning, optimization, reinforcement learning and planning, meta learning

Robust Learning-Augmented Caching: An Experimental Study

Jakub Chłędowski, Adam Polak, Bartosz Szabucki, Konrad Zolna

Keywords Abstract Paper

Applications

Stochastic Hamiltonian Gradient Methods for Smooth Games

Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau and Pascal Vincent, Simon Lacoste-Julien, Ioannis Mitliagkas

Keywords Abstract Paper

Optimization - Non-convex

A Distributional Framework For Data Valuation

Amirata Ghorbani, Michael Kim, James Zou

Keywords Abstract Paper

Learning Theory

A Stochastic Derivative Free Optimization Method with Momentum

Eduard Gorbunov, Adel Bibi, Ozan Sener and El Houcine Bergou, Peter Richtarik

Keywords Abstract Paper

derivative-free optimization, stochastic optimization, heavy ball momentum, importance sampling

Timed games and deterministic separability

Lorenzo Clemente, Sławomir Lasota and Radosław Piórkowski

Keywords Abstract Paper

Timed automata, separability problems, timed games

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

Nicolas Loizou, Hugo Berard, Gauthier Gidel and Ioannis Mitliagkas, Simon Lacoste-Julien

Keywords Abstract Paper

optimization

Evolution Strategies for Approximate Solution of Bayesian Games

Zun Li, Michael P. Wellman

Keywords Abstract Paper

A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games

Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel

Keywords Abstract Paper

Approximately solving mean field games via entropy-regularized deep reinforcement learning

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Tatjana Chavdarova, Matteo Pagliardini, Sebastian Stich and
François Fleuret, Martin Jaggi

Keywords Paper

Keywords Paper

Keywords Paper

Xidong Feng, Oliver Slumbers, Ziyu Wan and
Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, Yaodong Yang

Keywords Paper

Keywords Paper

Nicolas Loizou, Hugo Berard, Alexia Jolicoeur-Martineau and
Pascal Vincent, Simon Lacoste-Julien, Ioannis Mitliagkas

Keywords Paper

Keywords Paper

Eduard Gorbunov, Adel Bibi, Ozan Sener and
El Houcine Bergou, Peter Richtarik

Keywords Paper

Keywords Paper

Nicolas Loizou, Hugo Berard, Gauthier Gidel and
Ioannis Mitliagkas, Simon Lacoste-Julien

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

David Mguni, Yutong Wu, Yali Du and
Yaodong Yang, Ziyi Wang, M. Li, Ying Wen, Joel Jennings, Jun Wang

Keywords Paper

Laurent Meunier, Meyer Scetbon, Rafael Pinot and
Jamal Atif, Yann Chevaleyre

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Tanner Fiez, Lillian Ratliff, Eric Mazumdar and
Evan Faulkner, Adhyyan Narang

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper