Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. arXiv, 2405.02486.
Download (ext.)
https://doi.org/10.48550/arXiv.2405.02486
[Preprint]
Preprint
| Submitted
| English
Corresponding author has ISTA affiliation
Department
Abstract
We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.
The computational problem we consider is the approximation of the value within an arbitrary
additive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time.
Publishing Year
Date Published
2024-05-03
Journal Title
arXiv
Article Number
2405.02486
IST-REx-ID
Cite this
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. arXiv. doi:10.48550/arXiv.2405.02486
Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (n.d.). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. arXiv. https://doi.org/10.48550/arXiv.2405.02486
Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2405.02486.
A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” arXiv. .
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. arXiv, 2405.02486.
Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” ArXiv, 2405.02486, doi:10.48550/arXiv.2405.02486.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2405.02486