Source-linked AI summary
Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games
Durgam Latha, Dion Reji, S. Akshay, Djordje Zikelic, Shankaranarayanan Krishna
TL;DR
The paper studies how to solve RPOMDPs with omega-regular objectives when transition probabilities are uncertain, addressing limited prior treatment of logical correctness. It reduces these RPOMDPs to POSGs and, for the first time, constructs reductions in both directions. This equivalence yields new complexity results for RPOMDPs and RMDPs.
Problem
Existing robust POMDP research largely focuses on reward objectives, while general omega-regular correctness objectives remain less developed and often require restrictive uncertainty or satisfaction assumptions.
Method
The paper establishes bidirectional polynomial-time reductions between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs under omega-regular objectives.
Results
The reductions preserve objective values and transfer complexity results for sure, almost-sure, limit-sure, and quantitative winning, with additional results for RMDPs.
Takeaways & Limitations
RPOMDPs inherit upper and lower complexity bounds from POSGs, providing a broader complexity landscape for robust models with omega-regular objectives.
Takeaways & Limitations
The results apply to (s,a)-rectangular polytopic uncertainty sets represented by explicit vertex lists and leave more general settings for future work.
Abstract
from arXiv · showhide
Robust POMDPs (RPOMDPs) generalize classical POMDPs to the setting where exact transition probabilities are not known -- rather, they are only known to belong to some uncertainty set of values. In this work, we study the problem of solving RPOMDPs with general omega-regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under omega-regular objectives can be reduced to solving partially observable stochastic games (POSGs) under omega-regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between (s,a)-rectangular RPOMDPs with polytopic uncertainty sets and POSGs. This allows us to derive a range of new computational complexity results, including both upper and lower complexity bounds, on solving RPOMDPs with different omega-regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.
1 Introduction
The paper addresses robust partially observable decision making with omega-regular correctness objectives, whose existing treatment is limited. It establishes bidirectional polynomial-time reductions between RPOMDPs and POSGs, enabling new complexity results.
- Motivation: Classical POMDPs assume known transition probabilities, whereas robust models represent probabilities through uncertainty sets.The motivation is that transition estimates inferred from data carry uncertainty.
- Motivation: Omega-regular objectives capture logical correctness properties including reach-avoid, stability, reachability, safety, Büchi, co-Büchi, and LTL specifications.Such properties are especially relevant in safety-critical control and robotics applications.
- Research gap: Prior work on robust models with omega-regular objectives is limited by assumptions such as interval uncertainty or restriction to probability-1 and limit-sure satisfaction.The paper targets broader computational analysis under general omega-regular objectives.
- Contributions: For (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, solving omega-regular objectives is polynomial-time reducible in both directions to solving POSGs.The bidirectional result establishes equivalence between the two models.
- Contributions: The equivalence transfers computational complexity results from POSGs to RPOMDPs for sure, almost-sure, limit-sure, and quantitative winning.The paper also derives new complexity results for RMDPs as a corollary.
2 Model Definition and Preliminaries
The paper defines RPOMDPs as partially observable robust decision processes with dynamic adversarial transition uncertainty and omega-regular objectives. It also formalizes POSGs, strategy semantics, and four corresponding winning analyses.
- RPOMDP model: An RPOMDP contains finite states and actions, an uncertainty set of transition functions, agent and environment observations, observation mappings, and an initial state.RMDPs have full observability for both players, while one-sided RPOMDPs expose the state fully to the environment.
- RPOMDP assumptions: The paper assumes (s,a)-rectangular polytopic uncertainty: distributions are chosen independently across state-action pairs, and each set is a polytope with explicitly listed vertices.Intervals and L1-uncertainty sets are included as standard examples; model-size claims use the explicit vertex lists.
- RPOMDP semantics: Under RPOMDP semantics, the agent selects an action from its observation history while the environment selects a complete transition assignment from the uncertainty set.The transition uses the assignment's component for the current state-action pair, and the environment may select a new assignment at each step.
- Objectives and semantics: Omega-regular objectives are measurable play sets represented by parity automata, including reachability, safety, Büchi, and co-Büchi objectives.The model evaluates strategies through the induced probability measure over supported plays.
- POSG model: A POSG is a turn-based two-player game with separate max and min states, actions, transition distributions, observations, and observation functions.Each player's strategy maps its observation history to an action distribution, using action-invisible strategies.
- Winning problems: The four analysis problems ask for sure, almost-sure, limit-sure, or thresholded quantitative satisfaction of the objective.Quantitative analysis tests whether the model value reaches a given threshold p ∈ [0,1].
3 Equivalence with Partially Observable Stochastic Games (ac-POSG)
The paper establishes linear-time, bidirectional reductions between (s,a)-rectangular polytopic RPOMDPs and alternating-control POSGs for omega-regular objectives. The reductions preserve objective satisfaction, probabilities, values, and the four analyzed winning notions.
- Reduction from RPOMDPs to ac-POSGs: The RPOMDP-to-POSG construction represents each RPOMDP state as a max-state and each state-action pair as a min-state.The max-player uses the RPOMDP actions, while effective min-actions are uncertainty-polytope vertices.
- Reduction from RPOMDPs to ac-POSGs: Randomizing over uncertainty-polytope vertices reproduces every transition distribution in the corresponding uncertainty polytope.The construction therefore captures polytopic uncertainty through the min-player’s effective actions.
- Reduction from RPOMDPs to ac-POSGs: The induced ac-POSG preserves RPOMDP omega-regular values and makes sure, almost-sure, limit-sure, and quantitative analyses inter-reducible in linear time.The parity objective assigns each constructed state the priority of its RPOMDP state component.
- Reduction from ac-POSGs to RPOMDPs: The reverse reduction addresses the timing mismatch between POSG observation and RPOMDP uncertainty commitment using a two-step construction through pre-min-transformed POSGs.The pre-min transformation inserts dummy max-states before min-states, with a forced action preserving the relevant information structure.
- Reduction from ac-POSGs to RPOMDPs: The transformations preserve objective satisfaction, plays, probabilities, values, and the four analysis problems, while preserving memoryless, finite-memory, and infinite-memory strategy classes.The RPOMDP construction is linear in the transformed game size, and the two reductions are linear in model size.
- Complexity Results: Bidirectional equivalence transfers upper and lower complexity bounds from finite ac-POSGs to polytopic RPOMDPs under omega-regular objectives.The result also yields new complexity results for RMDPs as a corollary.
4 Conclusion
The paper establishes polynomial-time equivalence between RPOMDPs and action-invisible POSGs under ω-regular objectives, in both reduction directions. This equivalence yields new complexity results for RPOMDPs and RMDPs while identifying more general settings as future work.
- Polynomial-time reductions in both directions establish equivalence between RPOMDPs and action-invisible POSGs under ω-regular objectives.
- The equivalence supports a complete complexity landscape for R(PO)MDPs with (s, a)-rectangular and polytopic uncertainty sets.
- More general uncertainty settings remain an identified direction for future work.
- The construction represents each local uncertainty set through its vertex actions at corresponding min-states.
- The induced POSG alternates max- and min-states, with deterministic transitions from max state-action pairs to intermediate states and probabilistic transitions from min-states.
A.1 Mapping Plays, Observation Histories and Strategies from M to G
This section constructs mappings between RPOMDP plays, observation histories, strategies, and induced POSG plays. The mappings preserve local uncertainty choices and next-state distributions while lifting parity objectives through repeated priorities.
- The play map Θ expands each RPOMDP transition by inserting a POSG intermediate state and resolving uncertainty with an arbitrary local-polytope vertex.
- The reverse map Υ projects POSG plays to RPOMDP plays by retaining every second state and is many-to-one.
- Agent and environment observation histories are mapped by duplicating observations across alternating POSG states, with inverse mappings recovering the original histories.
- Mapping of Strategies: Environment strategies assign distributions over uncertainty-polytope vertices, while barycenters recover RPOMDP transition distributions.
- The strategy compositions preserve next-state distributions, and the lifted parity sequence repeats each RPOMDP priority without changing its lim inf.
A.3 Value Preservation
The value-preservation proof compares corresponding cylinder probabilities under mapped strategies. It concludes that objective values and winning notions coincide between the RPOMDP and its induced POSG.
- Mapped strategies preserve the probability measure on corresponding histories and cylinder sets in both directions.
- The resulting value identity is ValM(W) = ValG(W′) for corresponding parity objectives.
- The value equality transfers sure-winning and almost-sure-winning properties between mapped strategies.
- Because parity subsumes ω-regular objectives, the value-preservation result extends to every ω-regular objective and also supports limit-sure and quantitative analyses.
A.4 Proof of Theorem 3.1
The proof first transforms an alternating POSG by inserting deterministic dummy max-states, then maps plays, observations, strategies, and priorities to establish the reduction framework.
- The pre-min transformation inserts one dummy max-state before every min-state so the max-player acts twice consecutively.
- At each dummy state, the fixed ⊤ action deterministically transitions to the corresponding min-state and carries no strategic content.
- The transformed play structure alternates original max-states and dummy states with min-states, and Γ is a bijection between original and transformed plays.
- Strategy maps Φ⋆ and Ψ⋆ are mutual inverses for both players, preserving their behavior across the transformation.
- Assigning each dummy state the priority of its corresponding min-state repeats priority values without changing parity satisfaction.
B.3 Value Preservation
The Pre-min transformation preserves objective probabilities and values between the original POSG and its transformed game. Consequently, sure-, almost-sure-, limit-sure, and quantitative winning properties transfer across the reduction.
- Strategy maps preserve objective probabilities in both directions.The corresponding fixed-strategy infima are equal, enabling value preservation.
- ValG(W) = ValG′(W ′) for parity objectives and their corresponding transformed objectives.The result follows by combining the strategy-map probability equalities with the bijection between max-player strategies.
- Sure winning is preserved exactly: σ is sure winning for W if and only if σ′ is sure winning for W ′.The correspondence uses the lifted objective W ′ = Γ(W).
- Almost-sure winning is preserved exactly under the strategy map.The fixed-strategy probability equality implies that one side has value 1 exactly when the other does.
- The same value-preservation lemma yields corresponding limit-sure and quantitative winning results.These results follow directly from the preserved fixed-strategy objective probabilities.
B.3.1 Size and Memory Preservation of the reduction
The reduction has linear size overhead, keeps observation histories within a factor of three, and preserves strategy memory classes exactly.
- |G′| = O(|G|), and the construction runs in linear time.The transformed game adds one dummy state per min-state, one action, doubled observation alphabets, and |Smin| transition edges.
- Observation histories on the two sides are within a factor of 3 in length.Inserted tagged observations increase histories by at most this constant factor, while inverse deletion only shortens them.
- The lifting maps preserve memory class exactly for memoryless, finite-memory, and infinite-memory strategies.Both directions can simulate the transformed histories online without adding persistent memory states.
B.4 Proof of Lemma 3.2
The Pre-min transformation exposes min-player choices as transition-distribution choices at dummy states, matching the environment’s role in an RPOMDP.
- Every transformed play alternates max-states and dummy states with min-states.This periodic structure makes the min-state action determine the next distribution from the preceding dummy-state context.
- The min-player’s action at a min-state selects the next transition distribution, exactly as the RPOMDP environment selects from an uncertainty set.This correspondence defines the associated polytopic RPOMDP.
- The RPOMDP uses Amax ∪ {⊤}, with effective pairs at max-states and dummy states; other pairs receive max-losing default transitions.The uncertainty set at each effective pair is defined from the convex hull of the relevant transition distributions.
- At dummy states, the polytope’s vertices encode min-actions, while convex combinations encode randomized min-player behavior.At non-dummy states, the uncertainty set is a singleton, so the environment has no substantive choice.
C.1 Mapping plays, observation histories, strategies from G′ to R(G)
The mapping from the transformed POSG to the RPOMDP removes min-states and min-actions from plays while representing their effects through polytopic environment choices.
- Λ is many-to-one: multiple transformed plays differing only in min-actions map to the same RPOMDP play.The inverse collects all such transformed plays by resolving each dummy transition with a min-action.
- Λ maps transformed plays to RPOMDP plays by removing all min-states and min-actions.Its inverse is set-valued because each dummy-state transition can be resolved by an arbitrary min-action.
- RPOMDP strategies select state-indexed action distributions, while environment strategies select complete transition assignments from the rectangular uncertainty sets.At dummy states, these assignments are convex combinations of distributions induced by min-actions.
- Agent and environment strategies are mapped between the two models using four lifting maps.Agent maps are mutual inverses, and environment compositions preserve transition distributions.
- The parity objective is preserved after removing min-states because their priorities equal those of the preceding dummy states.Thus no lim inf-relevant priority value is lost under Λ.
C.3 Value Preservation between G′ and R(G)
The reduction between the Pre-min transformed POSG G′ and RPOMDP R(G) preserves objective values and winning properties through bidirectional strategy and play mappings.
- Strategy maps preserve objective probabilities in both directions for corresponding parity objectives.The mappings preserve cylinder probabilities, hence the probability of the parity objective.
- ValG′(W ′) = ValR(G)(W R) for corresponding parity objectives.The equality follows from the two fixed-strategy value equalities and the bijectivity of Ωmax.
- Sure-winning strategies correspond exactly between G′ and R(G).For σR = Ωmax(σ), σ is sure winning for W′ if and only if σR is sure winning for WR.
- Almost-sure winning strategies correspond exactly between G′ and R(G).The equivalence follows from preservation of fixed-strategy objective probabilities.
- The reduction also preserves limit-sure winning and quantitative threshold properties for corresponding objectives.These properties follow directly from the value-preservation lemma.
C.3.1 Size and memory preservation between G′ and R(G)
The RPOMDP reduction has linear size and construction time while preserving observation structure, history scale, and strategy memory classes exactly.
- |R(G)| = O(|G′|), and the reduction is computed in linear time.The construction has |SR| = |Smax| + |Smin|, |AR| = |Amax| + 1, and at most |Smin| |Amin| + |Smax| |Amax| vertices.
- Observation alphabets are inherited unchanged from G′.The state and action reductions retain the corresponding observation-alphabet cardinalities.
- Observation histories on the two sides are linear in each other.The contraction and expansion maps delete or reinsert Smin observations according to tagged dummy observations.
- Memoryless, finite-memory, and infinite-memory strategies correspond exactly between G′ and R(G).The lifting maps preserve the number of memory states; online history contraction and expansion add no persistent memory.
C.4 Proof of Lemma 3.3
Because parity objectives subsume all omega-regular objectives, value preservation extends from parity to arbitrary omega-regular objectives and associated winning properties.
- Parity-objective value preservation implies value preservation for every omega-regular objective and its corresponding lifted objective.The associated sure-, almost-sure, limit-sure, and quantitative consequences follow from the preceding lemmas.