---
OA_place: repository
OA_type: green
_id: '21717'
abstract:
- lang: eng
text: Robust Markov Decision Processes (RMDPs) generalize classical MDPs that consider
uncertainties in transition probabilities by defining a set of possible transition
functions. An objective is a set of runs (or infinite trajectories) of the RMDP,
and the value for an objective is the maximal probability that the agent can guarantee
against the adversarial environment. We consider (a) reachability objectives,
where given a target set of states, the goal is to eventually arrive at one of
them; and (b) parity objectives, which are a canonical representation for ω-regular
objectives. The qualitative analysis problem asks whether the objective can be
ensured with probability 1. In this work, we study the qualitative problem for
reachability and parity objectives on RMDPs without making any assumption over
the structures of the RMDPs, e.g., unichain or aperiodic. Our contributions are
twofold. We first present efficient algorithms with oracle access to uncertainty
sets that solve qualitative problems of reachability and parity objectives. We
then report experimental results demonstrating the effectiveness of our oracle-based
approach on classical RMDP examples from the literature scaling up to thousands
of states.
acknowledgement: This work was supported by ERC CoG 863818 (ForMSMArt) and Austrian
Science Fund (FWF) 10.55776/COE12. We also thank Hossein Zakerinia for his helpful
feedback.
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ehsan
full_name: Kafshdar Goharshadi, Ehsan
id: 103b4fa0-896a-11ed-bdf8-87b697bef40d
last_name: Kafshdar Goharshadi
orcid: 0000-0002-8595-0587
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
orcid: 0009-0007-5253-9170
- first_name: Ali
full_name: Shafiee, Ali
id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
last_name: Shafiee
citation:
ama: 'Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. Qualitative analysis
of ω-regular objectives on robust MDPs. In: Proceedings of the 40th AAAI Conference
on Artificial Intelligence. Vol 40. Association for the Advancement of Artificial
Intelligence; 2026:36137-36145. doi:10.1609/aaai.v40i43.40931'
apa: 'Asadi, A., Chatterjee, K., Goharshady, E., Karrabi, M., & Shafiee, A.
(2026). Qualitative analysis of ω-regular objectives on robust MDPs. In Proceedings
of the 40th AAAI Conference on Artificial Intelligence (Vol. 40, pp. 36137–36145).
Singapore, Singapore: Association for the Advancement of Artificial Intelligence.
https://doi.org/10.1609/aaai.v40i43.40931'
chicago: Asadi, Ali, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, and
Ali Shafiee. “Qualitative Analysis of ω-Regular Objectives on Robust MDPs.” In
Proceedings of the 40th AAAI Conference on Artificial Intelligence, 40:36137–45.
Association for the Advancement of Artificial Intelligence, 2026. https://doi.org/10.1609/aaai.v40i43.40931.
ieee: A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, and A. Shafiee, “Qualitative
analysis of ω-regular objectives on robust MDPs,” in Proceedings of the 40th
AAAI Conference on Artificial Intelligence, Singapore, Singapore, 2026, vol.
40, no. 43, pp. 36137–36145.
ista: 'Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. 2026. Qualitative
analysis of ω-regular objectives on robust MDPs. Proceedings of the 40th AAAI
Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
vol. 40, 36137–36145.'
mla: Asadi, Ali, et al. “Qualitative Analysis of ω-Regular Objectives on Robust
MDPs.” Proceedings of the 40th AAAI Conference on Artificial Intelligence,
vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026,
pp. 36137–45, doi:10.1609/aaai.v40i43.40931.
short: A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, A. Shafiee, in:, Proceedings
of the 40th AAAI Conference on Artificial Intelligence, Association for the Advancement
of Artificial Intelligence, 2026, pp. 36137–36145.
conference:
end_date: 2026-01-27
location: Singapore, Singapore
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2026-01-20
date_created: 2026-04-12T22:01:50Z
date_published: 2026-03-14T00:00:00Z
date_updated: 2026-05-04T11:38:56Z
day: '14'
department:
- _id: KrCh
- _id: GradSch
doi: 10.1609/aaai.v40i43.40931
ec_funded: 1
external_id:
arxiv:
- '2505.04539'
intvolume: ' 40'
issue: '43'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.04539
month: '03'
oa: 1
oa_version: Preprint
page: 36137-36145
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 40th AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: Qualitative analysis of ω-regular objectives on robust MDPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 40
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21722'
abstract:
- lang: eng
text: 'Partially observable Markov decision processes (POMDPs) are a central model
for uncertainty in sequential decision making. The most basic objective is the
reachability objective, where a target set must be eventually visited, and the
more general parity objectives can model all omega-regular specifications. For
such objectives, the computational analysis problems are the following: (a) qualitative
analysis that asks whether the objective can be satisfied with probability 1 (almost-sure
winning) or probability arbitrarily close to 1 (limit-sure winning); and (b) quantitative
analysis that asks for the approximation of the optimal probability of satisfying
the objective. For general POMDPs, almost-sure analysis for reachability objectives
is EXPTIME-complete, but limit-sure and quantitative analyses for reachability
objectives are undecidable; almost-sure, limit-sure, and quantitative analyses
for parity objectives are all undecidable. A special class of POMDPs, called revealing
POMDPs, has been studied recently in several works, and for this subclass the
almost-sure analysis for parity objectives was shown to be EXPTIME-complete. In
this work, we show that for revealing POMDPs the limit-sure analysis for parity
objectives is EXPTIME-complete, and even the quantitative analysis for parity
objectives can be achieved in EXPTIME.'
acknowledgement: "This work was partially supported by the ANRT under the French CIFRE
Ph.D program in collaboration between NyxAir and Paris-Dauphine University (Contract:
CIFRE N° 2022/0513), by the French Agence Nationale de la Recherche (ANR) under
reference ANR-21-CE40-\r\n0020 (CONVERGENCE project), by Austrian Science Fund (FWF)
10.55776/COE12, and by the ERC CoG 863818 (ForM-SMArt) grant."
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: David
full_name: Lurie, David
id: 579a6c20-34cf-11f1-acbd-8c2f19cdb4da
last_name: Lurie
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
citation:
ama: 'Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. Revealing POMDPs: Qualitative
and quantitative analysis for parity objectives. In: Proceedings of the AAAI
Conference on Artificial Intelligence. Vol 40. Association for the Advancement
of Artificial Intelligence; 2026:36146-36154. doi:10.1609/aaai.v40i43.40932'
apa: 'Asadi, A., Chatterjee, K., Lurie, D., & Saona Urmeneta, R. J. (2026).
Revealing POMDPs: Qualitative and quantitative analysis for parity objectives.
In Proceedings of the AAAI Conference on Artificial Intelligence (Vol.
40, pp. 36146–36154). Singapore, Singapore: Association for the Advancement of
Artificial Intelligence. https://doi.org/10.1609/aaai.v40i43.40932'
chicago: 'Asadi, Ali, Krishnendu Chatterjee, David Lurie, and Raimundo J Saona Urmeneta.
“Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives.”
In Proceedings of the AAAI Conference on Artificial Intelligence, 40:36146–54.
Association for the Advancement of Artificial Intelligence, 2026. https://doi.org/10.1609/aaai.v40i43.40932.'
ieee: 'A. Asadi, K. Chatterjee, D. Lurie, and R. J. Saona Urmeneta, “Revealing POMDPs:
Qualitative and quantitative analysis for parity objectives,” in Proceedings
of the AAAI Conference on Artificial Intelligence, Singapore, Singapore, 2026,
vol. 40, no. 43, pp. 36146–36154.'
ista: 'Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. 2026. Revealing POMDPs:
Qualitative and quantitative analysis for parity objectives. Proceedings of the
AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
vol. 40, 36146–36154.'
mla: 'Asadi, Ali, et al. “Revealing POMDPs: Qualitative and Quantitative Analysis
for Parity Objectives.” Proceedings of the AAAI Conference on Artificial Intelligence,
vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026,
pp. 36146–54, doi:10.1609/aaai.v40i43.40932.'
short: A. Asadi, K. Chatterjee, D. Lurie, R.J. Saona Urmeneta, in:, Proceedings
of the AAAI Conference on Artificial Intelligence, Association for the Advancement
of Artificial Intelligence, 2026, pp. 36146–36154.
conference:
end_date: 2026-01-27
location: Singapore, Singapore
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2026-01-20
corr_author: '1'
date_created: 2026-04-12T22:01:52Z
date_published: 2026-03-14T00:00:00Z
date_updated: 2026-05-04T11:44:14Z
day: '14'
department:
- _id: KrCh
doi: 10.1609/aaai.v40i43.40932
ec_funded: 1
external_id:
arxiv:
- '2511.13134'
intvolume: ' 40'
issue: '43'
language:
- iso: eng
main_file_link:
- url: https://doi.org/10.48550/arXiv.2511.13134
month: '03'
oa_version: Preprint
page: 36146-36154
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Revealing POMDPs: Qualitative and quantitative analysis for parity objectives'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 40
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '21281'
abstract:
- lang: eng
text: "A strategy profile in a multi-player game is a Nash equilibrium if no player
can unilaterally deviate to achieve a strictly better payoff. A profile is an
ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating
from their strategy. In this work, we use ε-Nash equilibria to approximate the
computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer
stochastic games played on graphs, where players are restricted to stationary
strategies - strategies that use randomness but not memory.\r\nThe problem of
deciding the constrained existence of stationary Nash equilibria - where each
player’s payoff must lie within a given interval - is known to be ∃ℝ-complete
in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to
stationary ε-Nash equilibria and present an algorithm that solves the following
promise problem: given a game with a Nash equilibrium satisfying the constraints,
compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies
the constraints up to an ε additive error. Our algorithm runs in FNP^NP time.\r\nTo
achieve this, we first show that if a constrained Nash equilibrium exists, then
one exists where the non-zero probabilities are at least an inverse of a double-exponential
in the input. We further prove that such a strategy can be encoded using floating-point
representations, as in the work of Frederiksen and Miltersen (2013), which finally
gives us our FNP^NP algorithm. \r\nWe further show that the decision version of
the promise problem is NP-hard. Finally, we show a partial tightness result by
proving a lower bound for such techniques: if a constrained Nash equilibrium exists,
then there must be one where the probabilities in the strategies are double-exponentially
small."
acknowledgement: "This work is a part of project VAMOS that has received funding from
the European\r\nResearch Council (ERC), grant agreement No 101020093.\r\n"
alternative_title:
- LIPIcs
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Leonard
full_name: Brice, Leonard
last_name: Brice
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: K. S.
full_name: Thejaswini, K. S.
id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
last_name: Thejaswini
citation:
ama: 'Asadi A, Brice L, Chatterjee K, Thejaswini KS. ε-stationary Nash equilibria
in multi-player stochastic graph games. In: 45th Annual Conference on Foundations
of Software Technology and Theoretical Computer Science. Vol 360. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025:9:1-9:17. doi:10.4230/lipics.fsttcs.2025.9'
apa: 'Asadi, A., Brice, L., Chatterjee, K., & Thejaswini, K. S. (2025). ε-stationary
Nash equilibria in multi-player stochastic graph games. In 45th Annual Conference
on Foundations of Software Technology and Theoretical Computer Science (Vol.
360, p. 9:1-9:17). Pilani, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/lipics.fsttcs.2025.9'
chicago: Asadi, Ali, Leonard Brice, Krishnendu Chatterjee, and K. S. Thejaswini.
“ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” In 45th
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, 360:9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/lipics.fsttcs.2025.9.
ieee: A. Asadi, L. Brice, K. Chatterjee, and K. S. Thejaswini, “ε-stationary Nash
equilibria in multi-player stochastic graph games,” in 45th Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, Pilani,
India, 2025, vol. 360, p. 9:1-9:17.
ista: 'Asadi A, Brice L, Chatterjee K, Thejaswini KS. 2025. ε-stationary Nash equilibria
in multi-player stochastic graph games. 45th Annual Conference on Foundations
of Software Technology and Theoretical Computer Science. FSTTCS: Conference on
Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol.
360, 9:1-9:17.'
mla: Asadi, Ali, et al. “ε-Stationary Nash Equilibria in Multi-Player Stochastic
Graph Games.” 45th Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, vol. 360, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, p. 9:1-9:17, doi:10.4230/lipics.fsttcs.2025.9.
short: A. Asadi, L. Brice, K. Chatterjee, K.S. Thejaswini, in:, 45th Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17.
conference:
end_date: 2025-12-19
location: Pilani, India
name: 'FSTTCS: Conference on Foundations of Software Technology and Theoretical
Computer Science'
start_date: 2025-12-17
corr_author: '1'
date_created: 2026-02-17T08:27:14Z
date_published: 2025-12-09T00:00:00Z
date_updated: 2026-02-19T09:39:15Z
day: '09'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
doi: 10.4230/lipics.fsttcs.2025.9
ec_funded: 1
external_id:
arxiv:
- '2508.15356'
file:
- access_level: open_access
checksum: a66343e3ccc4a9cc5bc699c03d5764ff
content_type: application/pdf
creator: dernst
date_created: 2026-02-18T09:13:25Z
date_updated: 2026-02-18T09:13:25Z
file_id: '21316'
file_name: 2025_FSTTCS_Asadi.pdf
file_size: 1054007
relation: main_file
success: 1
file_date_updated: 2026-02-18T09:13:25Z
has_accepted_license: '1'
intvolume: ' 360'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 9:1-9:17
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 45th Annual Conference on Foundations of Software Technology and Theoretical
Computer Science
publication_identifier:
isbn:
- '9783959774062'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: ε-stationary Nash equilibria in multi-player stochastic graph games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 360
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '20297'
abstract:
- lang: eng
text: "A standard model that arises in several applications in sequential decision-making
is partially observable Markov decision processes (POMDPs) where a decision-making
agent interacts with an uncertain environment. A basic objective in POMDPs is
the reachability objective, where given a target set of states, the goal is to
eventually arrive at one of them.\r\n\r\nThe limit-sure problem asks whether reachability
can be ensured with probability arbitrarily close to 1. In general, the limit-sure
reachability problem for POMDPs is undecidable. However, in many practical cases,
the most relevant question is the existence of policies with a small amount of
memory. In this work, we study the limit-sure reachability problem for POMDPs
with a fixed amount of memory. We establish that the computational complexity
of the problem is NP-complete."
acknowledgement: This research was partially supported by Austrian Science Fund (FWF)
10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR)
under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt)
grant.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Ali
full_name: Shafiee, Ali
id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
last_name: Shafiee
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. In: The 41st Conference
on Uncertainty in Artificial Intelligence. Vol 286. ML Research Press; 2025:238-247.'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Shafiee, A. (2025).
Limit-sure reachability for small memory policies in POMDPs is NP-complete. In
The 41st Conference on Uncertainty in Artificial Intelligence (Vol. 286,
pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.'
chicago: Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee.
“Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.”
In The 41st Conference on Uncertainty in Artificial Intelligence, 286:238–47.
ML Research Press, 2025.
ieee: A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure
reachability for small memory policies in POMDPs is NP-complete,” in The 41st
Conference on Uncertainty in Artificial Intelligence, Rio de Janeiro, Brazil,
2025, vol. 286, pp. 238–247.
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty
in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
PMLR, vol. 286, 238–247.'
mla: Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs
Is NP-Complete.” The 41st Conference on Uncertainty in Artificial Intelligence,
vol. 286, ML Research Press, 2025, pp. 238–47.
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference
on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.
conference:
end_date: 2025-07-25
location: Rio de Janeiro, Brazil
name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2025-09-09T08:21:45Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
arxiv:
- '2412.00941'
file:
- access_level: open_access
checksum: 1a37ebe7ba73ab6985765bf0d17a0acc
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T08:19:41Z
date_updated: 2025-09-09T08:19:41Z
file_id: '20315'
file_name: 2025_UAI_AsadiAli.pdf
file_size: 307458
relation: main_file
success: 1
file_date_updated: 2025-09-09T08:19:41Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 238-247
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Limit-sure reachability for small memory policies in POMDPs is NP-complete
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '20299'
abstract:
- lang: eng
text: "Deterministic Markov Decision Processes (DMDPs) are a mathematical framework
for decision-making where the outcomes and future possible actions are deterministically
determined by the current action taken. DMDPs can be viewed as a finite directed
weighted graph, where in each step, the controller chooses an outgoing edge. An
objective is a measurable function on runs (or infinite trajectories) of the DMDP,
and the value for an objective is the maximal cumulative reward (or weight) that
the controller can guarantee. We consider the classical mean-payoff (aka limit-average)
objective, which is a basic and fundamental objective.\r\n\r\nHoward's policy
iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives.
Although Howard's algorithm performs well in practice, as experimental studies
suggested, the best known upper bound is exponential and the current known lower
bound is as follows: For the input size I, the algorithm requires (math formular)
iterations, where (math formular) hides the poly-logarithmic factors, i.e., the
current lower bound on iterations is sub-linear with respect to the input size.
Our main result is an improved lower bound for this fundamental algorithm where
we show that for the input size I, the algorithm requires (math formular) iterations."
acknowledgement: "This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and Austrian Science Fund (FWF) 10.55776/COE12.\r\n"
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jakob
full_name: De Raaij, Jakob
last_name: De Raaij
citation:
ama: 'Asadi A, Chatterjee K, De Raaij J. Lower bound on Howard policy iteration
for deterministic Markov Decision Processes. In: The 41st Conference on Uncertainty
in Artificial Intelligence. Vol 286. ML Research Press; 2025:223-232.'
apa: 'Asadi, A., Chatterjee, K., & De Raaij, J. (2025). Lower bound on Howard
policy iteration for deterministic Markov Decision Processes. In The 41st Conference
on Uncertainty in Artificial Intelligence (Vol. 286, pp. 223–232). Rio de
Janeiro, Brazil: ML Research Press.'
chicago: Asadi, Ali, Krishnendu Chatterjee, and Jakob De Raaij. “Lower Bound on
Howard Policy Iteration for Deterministic Markov Decision Processes.” In The
41st Conference on Uncertainty in Artificial Intelligence, 286:223–32. ML
Research Press, 2025.
ieee: A. Asadi, K. Chatterjee, and J. De Raaij, “Lower bound on Howard policy iteration
for deterministic Markov Decision Processes,” in The 41st Conference on Uncertainty
in Artificial Intelligence, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 223–232.
ista: 'Asadi A, Chatterjee K, De Raaij J. 2025. Lower bound on Howard policy iteration
for deterministic Markov Decision Processes. The 41st Conference on Uncertainty
in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
PMLR, vol. 286, 223–232.'
mla: Asadi, Ali, et al. “Lower Bound on Howard Policy Iteration for Deterministic
Markov Decision Processes.” The 41st Conference on Uncertainty in Artificial
Intelligence, vol. 286, ML Research Press, 2025, pp. 223–32.
short: A. Asadi, K. Chatterjee, J. De Raaij, in:, The 41st Conference on Uncertainty
in Artificial Intelligence, ML Research Press, 2025, pp. 223–232.
conference:
end_date: 2025-07-25
location: Rio de Janeiro, Brazil
name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2025-09-09T06:31:20Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
arxiv:
- '2506.12254'
file:
- access_level: open_access
checksum: 4180c81bb6ed3b4f5c7a8e48d06520c6
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T06:27:59Z
date_updated: 2025-09-09T06:27:59Z
file_id: '20313'
file_name: 2025_UAI_Asadi.pdf
file_size: 317097
relation: main_file
success: 1
file_date_updated: 2025-09-09T06:27:59Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 223-232
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bound on Howard policy iteration for deterministic Markov Decision Processes
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2025'
...
---
_id: '17098'
abstract:
- lang: eng
text: Turn-based discounted-sum games are two-player zero-sum games played on finite
directed graphs. The vertices of the graph are partitioned between player 1 and
player 2. Plays are infinite walks on the graph where the next vertex is decided
by a player that owns the current vertex. Each edge is assigned an integer weight
and the payoff of a play is the discounted-sum of the weights of the play. The
goal of player 1 is to maximize the discounted-sum payoff against the adversarial
player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems
that belong to this complexity class and the existence of a polynomial-time algorithm
is a major open question. Since breaking the general exponential barrier has been
a challenging problem, faster parameterized algorithms have been considered. If
the discount factor is expressed in unary, then discounted-sum games can be solved
in polynomial time. However, if the discount factor is arbitrary (or expressed
in binary), but the weights are in unary, none of the existing approaches yield
a sub-exponential bound. Our main result is a new analysis technique for a classical
algorithm (namely, the strategy iteration algorithm) that present a new runtime
bound which is [EQUATION] for game graphs with n vertices and absolute weights
of at most W. In particular, our result yields a deterministic sub-exponential
bound for games with weights that are constant or represented in unary.
acknowledgement: "This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.\r\n"
article_number: '6'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
citation:
ama: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential
algorithm for discounted-sum games with unary weights. In: 39th Annual ACM/IEEE
Symposium on Logic in Computer Science. Association for Computing Machinery;
2024. doi:10.1145/3661814.3662080'
apa: 'Asadi, A., Chatterjee, K., Svoboda, J., & Saona Urmeneta, R. J. (2024).
Deterministic sub-exponential algorithm for discounted-sum games with unary weights.
In 39th Annual ACM/IEEE Symposium on Logic in Computer Science. Tallinn,
Estonia: Association for Computing Machinery. https://doi.org/10.1145/3661814.3662080'
chicago: Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona
Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with
Unary Weights.” In 39th Annual ACM/IEEE Symposium on Logic in Computer Science.
Association for Computing Machinery, 2024. https://doi.org/10.1145/3661814.3662080.
ieee: A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic
sub-exponential algorithm for discounted-sum games with unary weights,” in 39th
Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia,
2024.
ista: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic
sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual
ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science,
6.'
mla: Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum
Games with Unary Weights.” 39th Annual ACM/IEEE Symposium on Logic in Computer
Science, 6, Association for Computing Machinery, 2024, doi:10.1145/3661814.3662080.
short: A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual
ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery,
2024.
conference:
end_date: 2024-07-11
location: Tallinn, Estonia
name: 'LICS: Logic in Computer Science'
start_date: 2024-07-08
corr_author: '1'
date_created: 2024-06-03T07:43:15Z
date_published: 2024-07-08T00:00:00Z
date_updated: 2025-09-08T07:44:29Z
day: '08'
department:
- _id: KrCh
doi: 10.1145/3661814.3662080
ec_funded: 1
external_id:
arxiv:
- '2405.02479'
isi:
- '001275042100006'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2405.02479
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
eissn:
- 1043-6871
isbn:
- '9798400706608'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic sub-exponential algorithm for discounted-sum games with unary
weights
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '17099'
abstract:
- lang: eng
text: "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.\r\nThe
computational problem we consider is the approximation of the value within an
arbitrary\r\nadditive 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."
acknowledgement: "This research was partially supported by ERC CoG 863818 (ForM-SMArt),
Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la
Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)"
alternative_title:
- LIPIcs
article_number: '5'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
In: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.FSTTCS.2024.5'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (2024).
Concurrent stochastic games with stateful-discounted and parity objectives: Complexity
and algorithms. In 44th IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (Vol. 323). Gujarat, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5'
chicago: 'Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub
Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives:
Complexity and Algorithms.” In 44th IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Vol. 323. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5.'
ieee: 'A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent
stochastic games with stateful-discounted and parity objectives: Complexity and
algorithms,” in 44th IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Gujarat, India, 2024, vol. 323.'
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
44th IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer
Science, LIPIcs, vol. 323, 5.'
mla: 'Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and
Parity Objectives: Complexity and Algorithms.” 44th IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, vol.
323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSTTCS.2024.5.'
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-12-18
location: Gujarat, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2024-12-16
corr_author: '1'
date_created: 2024-06-03T07:44:27Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2025-12-02T13:40:52Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2024.5
ec_funded: 1
external_id:
arxiv:
- '2405.02486'
isi:
- '001537516500005'
file:
- access_level: open_access
checksum: 5b544ab4692b93300b404435c036ddd4
content_type: application/pdf
creator: dernst
date_created: 2025-01-08T09:49:31Z
date_updated: 2025-01-08T09:49:31Z
file_id: '18777'
file_name: 2024_LIPIcs_Asadi.pdf
file_size: 847960
relation: main_file
success: 1
file_date_updated: 2025-01-08T09:49:31Z
has_accepted_license: '1'
intvolume: ' 323'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959773553'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Concurrent stochastic games with stateful-discounted and parity objectives:
Complexity and algorithms'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 323
year: '2024'
...