Florian Horn

AAAI Conference 2025 Conference Paper

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives

• Marius Belly
• Nathanaël Fijalkow
• Hugo Gimbert
• Florian Horn
• Guillermo A. Pérez
• Pierre Vandenhove

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether the agent has a strategy ensuring a given specification with probability 1. This well-studied problem is known to be undecidable already for very simple omega-regular objectives, because of the difficulty of reasoning on uncertain events. We introduce a revelation mechanism which restricts information loss by requiring that almost surely the agent has eventually full information of the current state. Our main technical results are to construct exact algorithms for two classes of POMDPs called weakly and strongly revealing. Importantly, the decidable cases reduce to the analysis of a finite belief-support Markov decision process. This yields a conceptually simple and exact algorithm for a large class of POMDPs.

Highlights Conference 2025 Conference Abstract

The Complexity of Correlated Equilibria in Extensive Form Games

• Florian Horn

Highlights Conference 2013 Conference Abstract

Boundedness games

• Nathanaël Fijalkow
• Krishnendu Chatterjee
• Thomas Colcombet
• Florian Horn
• Denis Kuperberg
• Michał Skrzypczak
• Martin Zimmermann

In this talk, I will discuss some recent developments about boundedness games. They are two-player games played over graphs, featuring counters. The first player's objective is to satisfy a parity condition and that the counter values are bounded. A lot of questions are open: what is the algorithmic complexity of deciding the winner, and does there always exist finite-memory winning strategies? In particular, as shown by Thomas Colcombet, proving the existence of finite-memory winning strategies for (some) boundedness games is the last missing item to prove the decidability of cost-MSO over infinite trees. I will give an overview of where we stand now and what are the next challenges. 13: 00 14: 30 Lunch

GandALF Workshop 2010 Workshop Paper

How do we remember the past in randomised strategies?

• Julien Cristau
• Claire David
• Florian Horn

Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.