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 · 2024
Read Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives by Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Pérez, Pierre Vandenhove (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12063.txt.
Introduction
Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo Pérez, and Pierre Vandenhove carve out a decidable class of decision problems under partial sight. Their paper from twenty twenty-four treats POMDPs, models where an agent acts without seeing the full state. Asking if a plan can meet a spec for sure is known to be hopeless in general. Hidden state makes the reasoning blow up.
Their fix is a revelation rule: as time runs on, the agent almost surely gains full sight of the state. Two classes arise, weakly and strongly revealing. For both, exact algorithms exist. The trick cuts the problem down to a finite belief-support process. That makes the method both simple in concept and exact in output. A wide class of such problems becomes solvable at last.
Catalog record
| CREATOR | Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Pérez, Pierre Vandenhove |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-12063
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
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 Abstract 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 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. Code — https://github.com/gaperez64/pomdps-reveal 1 Introduction Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. They were defined in the 1960s ( Åström 1965 ) for operations research and introduced in artificial intelligence by the seminal paper of Kaelbling, Littman, and Cassandra 1998 . We consider POMDPs from a model-based point of view common in planning and in formal methods. Our goal is to construct exact (as opposed to approximate) algorithms that take as an input a complete description of the POMDP and construct a strategy ensuring a given specification. A long line of work has established that most formulations of this problem are undecidable. For instance, even in the extreme case where the agent has no information and the goal is to reach a target state with arbitrarily high probability, complex convergence phenomena occur, implying strong undecidability results ( Madani, Hanks, and Condon 2003 ; Gimbert and Oualhadj 2010 ; Fijalkow 2017 ) . In this work, we are interested in constructing almost-sure strategies , meaning strategies ensuring their specifications with probability 1 . We consider the class of omega-regular objectives (all expressible as parity objectives ), which is a robust class including properties expressible in Linear Temporal Logic ( Pnueli 1977 ; Giacomo and Vardi 2013 ) . Determining whether there exists an almost-sure strategy against the subclass of CoBüchi objectives (requiring to avoid a target from some point onwards) is undecidable ( Chatterjee, Chmelik, and Tracol 2016 ; Bertrand, Genest, and Gimbert 2017 ) . There is a vast body of work towards approximate and practical solutions: for instance, using interpolation in the belief space ( Lovejoy 1991 ) , approximation of the value function ( Hauskrecht 2000 ) , or Monte Carlo tree search approaches ( Silver and Veness 2010 ) . This is orthogonal to the current paper since we focus on exact algorithms. Our starting point is a simple approach to construct almost-sure strategies: from the POMDP, we build a Markov decision process (MDP) whose states are supports of the beliefs of the POMDP. In other words, we store information about which states we can be in, but abstract away the probabilities. The belief-support MDP serves as a finite abstraction of the POMDP; one could expect that there exists an almost-sure strategy in the POMDP if and only if there exists one in the corresponding belief-support MDP. Unfortunately, this abstraction is neither sound nor complete; we present a simple counterexample in Figure 1 . q_{0},2 q_{1},1 s s,\frac{1}{2} s,\frac{1}{2} \{q_{0}\},2 \{q_{0},q_{1}\},2 Figure 1: We consider the POMDP on the LHS: there is a single signal s , so no information is ever given about the exact state we are in (a behavior the revelation mechanisms forbid!). Yet, almost surely, we reach q_{1} . The priorities indicated on states constitute a parity condition inducing the objective “eventually never visiting q_{1} ”, which clearly cannot be ensured almost surely. We represent the belief-support MDP on the RHS: the two states are \{q_{0}\} and \{q_{0},q_{1}\} , and only the state \{q_{0},q_{1}\} is visited infinitely often. To assign priorities to the states of this MDP, there are two natural candidates: “maximal priority semantics” and “minimal priority semantics”, meaning that we assign either the maximal or minimal priority from the states in the belief support. In this figure, we use the maximal priority semantics: the priority of \{q_{0},q_{1}\} is thus 2 , so the belief-support MDP is winning. This means that the analysis of the belief-support MDP is not sound in general. By tweaking the priorities in this example, one can show that both priority semantics are neither sound nor complete. The fundamental question we ask in this paper is whether there are natural sufficient conditions which make the belief-support abstraction correct . Conceptually, the failure of this abstraction is due to information loss and its accumulation over time. We introduce a revelation mechanism which restricts information loss by requiring that, almost surely, the agent has eventually full information of the current state. Intuitively, by forbidding information loss from accumulating for an unbounded amount of time, the revelation mechanism removes the convergence issues leading to undecidability. Practically, we conjecture that revelation is a commonly occurring phenomenon in partial observability; a canonical example is systems with a small probability of resetting infinitely often, and where this reset is observable. We leave to future work to investigate this question further. Other approaches to restrict information loss have been proposed; we refer to the related works (Section 6 ) for an additional discussion. Figure 2: Summary of our results: decidable subclasses of the parity objective depending on the revelation mechanism. Figure 3: Omega-regular specifications have a natural interpretation in terms of bad events that must all be trumped by future good events. Along a simulation of the POMDP, one can keep track of the number of steps from the last bad event that has not yet been trumped (i.e., lower is better). Here, we depict this value, per step (from 1 to 500 ) over 500 simulations of a revealing version of the classical tiger POMDP ( Cassandra, Kaelbling, and Littman 1994 ) . A2C, DQN, and PPO are ( MlpPolicy ) strategies obtained from the stable-baselines library ( Raffin et al. 2021 ) , trained (for a total of 10 k time steps) with default parameter values using a simple reward scheme: a good event yields a reward of 100 ; a bad one, -1 . In the simulations, the trained models are queried for deterministic action predictions. The example used will be discussed in Section 5 , Example 2 . Our contributions. • We study two properties of POMDPs based on the revelation mechanism, called weak and strong revelations . • We obtain decidability (and undecidability) results for both classes. Importantly, the decidable cases reduce to the analysis of the finite belief-support MDP. A summary of our contributions for POMDPs is provided in Figure 2 . We also briefly consider the class of two-player games of partial information , to show that our revealing mechanisms do not suffice for decidability on this larger class. • We provide a simple implementation of the algorithm as a proof of concept. We provide a comparison between