Research map / Learning theory and algorithms / Prediction and decision losses

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

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces weakly and strongly revealing POMDPs, where information is eventually revealed almost surely, and shows that almost-sure parity analysis reduces to a finite belief-support MDP, yielding EXPTIME-complete algorithms.

Problem

Deciding almost-sure omega-regular (parity) objectives in POMDPs is undecidable in general because uncertainty accumulates; the belief-support abstraction is unsound and incomplete without restrictions on information loss.

Approach

A revelation mechanism requires that almost surely the agent eventually observes the exact current state; under weakly or strongly revealing conditions, the belief-support MDP becomes a sound and complete abstraction for parity objectives with priorities in {0,1,2} (and strongly revealing for all parity objectives), and the same ideas give an optimistic semantics for all POMDPs.

Key results

• Weakly revealing POMDPs with parity priorities in {0,1,2} are EXPTIME-complete for almost-sure strategies.
• Almost-sure parity with priorities {1,2,3} is undecidable already for weakly revealing POMDPs.
• Deciding whether a POMDP is weakly revealing is EXPTIME-complete.

Surprising findings

• The belief-support MDP abstraction is unsound for Büchi objectives without revealing assumptions.
• Deep RL baselines (A2C, DQN, PPO) could not match the belief-support algorithm on the revealing tiger example.

Limitations

• Algorithm is exponential in the number of POMDP states due to belief-support MDP size.
• Undecidable for priorities {1,2,3} and for two-player CoBüchi games even under strong revelation.
• Revealing assumption is restrictive and may not hold in many practical POMDPs.

Experimental setup

Benchmarks: revealing tiger POMDP

Metrics: steps since last untrumped bad event

Baselines: A2C DQN PPO

Builds on: belief-support MDP parity objectives probabilistic automata

Closest papers by meaning

• Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives (AAAI 2026 · similarity 0.92)
• rho-POMDPs have Lipschitz-Continuous epsilon-Optimal Value Functions (NeurIPS 2018 · similarity 0.90)
• Multi-Environment POMDPs with Finite-Horizon Objectives (NeurIPS 2026 · similarity 0.90)
• Belief-State Query Policies for User-Aligned POMDPs (NeurIPS 2024 · similarity 0.88)
• Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.88)
• Omega-Regular Decision Processes (AAAI 2024 · similarity 0.88)