KR2023Proceedings of the 20th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 2-8, 2023.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-02-7

Sponsored by
Published by

Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization

Strategic Abilities of Forgetful Agents in Stochastic Environments

  1. Francesco Belardinelli(Imperial College, London, UK)
  2. Wojciech Jamroga(Interdisc. Centre on Security, Reliability and Trust, SnT, University of Luxembourg, Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland)
  3. Munyque Mittelmann(University of Naples ``Federico II'')
  4. Aniello Murano(University of Naples ``Federico II'')


  1. Probabilistic reasoning and learning
  2. KR and autonomous agents and multi-agent systems
  3. Reasoning about actions and change, action languages
  4. Reasoning about knowledge, beliefs, and other mental attitudes


In this paper, we investigate the probabilistic variants of the strategy logics ATL and ATL* under imperfect information. Specifically, we present novel decidability and complexity results when both the model transitions and the strategies played by agents are stochastic. That is, the semantics of the logics are based on multi-agent, stochastic transition systems with imperfect information, which combine two sources of uncertainty, namely, the partial observability agents have on the environment, and the likelihood of transitions to occur from a system state. Since the model checking problem is undecidable in general in this setting, we restrict our attention to agents with memoryless (positional) strategies. The resulting setting captures the situation in which agents have qualitative uncertainty of the local state and quantitative

uncertainty about the occurrence of future events. We illustrate the

usefulness of this setting with meaningful examples.