acceptodds
Under review as a conference paper at ICLR 2027

Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

Abstract

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 -regular objectives, which subsume a broad class of objectives such as reachability, safety, and linear temporal logic (LTL) objectives. We show that, for -rectangular RPOMDPs with polytopic uncertainty sets, the problem of solving RPOMDPs under -regular objectives can be reduced to solving partially observable stochastic games (POSGs) under -regular objectives. Moreover, we show for the first time that reductions can be constructed in both directions, establishing the semantic equivalence between -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 -regular objectives. As a corollary, we also derive new computational complexity results for RMDPs.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Robust MDPs, Partial Observability, Stochastic Games, Omega-regular Objectives

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_EprhOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proves a linear reduction between RPOMDPs (under the assumption of (s,a)(s,a)-rectangularity with provided polytopic uncertainty sets) and POSGs (with factored prescriptions). This reduction allows complexity results from POSGs to be applied to RPOMDPs, including under ω\omega-regular objectives which are not comprehensively studied in RPOMDPs.

I recommend acceptance of this paper, due to the clear and useful contributions and strengths outlined following. I commend the clarity of the writing, which made the paper easy to follow despite some dense mathematics. Note that I have not checked the proofs in detail and I am lacking background in POSGs.

Critical strengths
  • [S1]: The paper presents a strong and novel result, allowing complexity results from POSGs to be applied to RPOMDPs.
Critical weaknesses
  • [W1]: The linear reduction between RPOMDPs and ac-POSGs only holds for POSGs where the min player uses factored prescriptions, which is not the standard formulation to my knowledge. The appendix provides a compilation to eliminate the factored prescription which is polynomial-size in general, so it would be more accurate to say that the relation between RPOMDPs and standard observation-based POSGs is polynomial in general.
Questions for authors
  • [Q1]: Is the assumption that every Vs,aV_{s,a} is given explicitly as part of the input a standard assumption in R(PO)MDP literature?
  • [Q2]: Why does the history have to be action invisible?
2 comments
AuthorsOpenReview ↗

Response to Review Eprh

We thank the reviewer for the encouraging feedback.

[Q1] Yes, vertex-set representation of uncertainty sets is a standard assumption in the literature assumed by many (although not all) works that present complexity and algorithmic results on robust (PO)MDPs. The classical works on RMDPs with (s,a)-rectangular polytopic uncertainty make this assumption (Nilim & Ghaoui, 2003; Iyengar, 2005). So does the closest related prior work of (Chatterjee et al., 2024) which proposes a one-sided reduction from (s,a)-rectangular polytopic uncertainty RMDPs to turn-based stochastic games under reward objectives. Thus, we significantly extend the landscape of known complexity results under the (s,a)-rectangular polytopic uncertainty assumption, covering general ω\omega-regular objectives and deriving reductions in both directions, both for RMDPs and RPOMDPs.
Some other works consider interval and L1L^1-uncertainty sets, e.g. (Givan et al., 2000; Ho et al., 2021), and work with the H-representation rather than vertex-representation of uncertainty sets. However, we note that interval and L1L^1-uncertainty sets are special cases and a strict subset of polytopic uncertainty sets.

[Q2] Action-invisible observation histories are the strategy information basis used by the POSG model we build on (Chatterjee et al., 2013), hence we adopt it for the ac-POSG and RPOMDP sides consistently so the equivalence lines up cleanly on both and is consistent with the literature.
We believe this assumption is without loss of generality for RMDPs, since the satisfaction of the specification depends only on the sequence of visited states. However, in RPOMDPs, allowing a strategy to observe both observations and actions may give it additional power to reason about the current state or belief. Extending our analysis to strategies that observe both observations and actions and determining whether it leads to a change in the computational complexity of our problems is an interesting direction of future work. We will add a short remark to clarify this.

[W1] The reviewer is right that our linear-time reductions are between RPOMDPs and ac-POSGs where the min-player uses factored prescriptions. The appendix's Prescription Compilation lemma (Lemma A.3) then eliminates factored prescriptions at polynomial blowup, with values and all four objectives preserved exactly. Composing the two reductions gives a direct, polynomial-time reduction from RPOMDPs to standard observation-based ac-POSGs. Thus, all our polynomial-time reductions and complexity results remain. We will clarify this in the paper.

Thank you for your responses. Based on the agreed clarifications and responses to other reviewers, I retain my recommendation of clear acceptance.

Reviewer_vFGSOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper shows how to construct turn-based partially observable stochastic game (ac-POSG) from a robust partially observable Markov decision process (RPOMDP). Further, it presents a converse translation transforming an ac-POSG into a RPOMDP. The purpose of these translations is to transfer known complexity results on ac-POSGs to RPOMDPs. The paper is of purely theoretical nature describing the underlying formalism of RPOMDPs and ac-POSGs, providing the constructions and proofs.

Post rebuttal: The authors have addressed the issue I mentioned in my review and promised to update the paper accordingly. Thus, I increase my evaluation.

Critical strengths

The paper discusses non-trivial constructions and provides new complexity results on RPOMDPs.

Critical weaknesses

Although the paper presents non-trivial mathematical results, I have two concerns. First, I am no sure if such a paper is suitable for a conference like ICLR. From the point of view of a reviewer, it is, in fact, a 47-pages long proof built around several constructions. It deserves a careful proof checking. According to my opinion, it would be much better to submit such a paper to a journal where the referee has enough time to go through the proof.

Second, it seems to me that the proof of complexity lower bound is not sound. The paper uses a non-standard definition of policies for min-player in ac-POSGs (so called factored prescriptions). Namely, the min-player does not prescribe a distribution over actions based on the observation history but jointly prescribes a collection of distributions one for each possible state corresponding to the last observation. This is a handy definition for the translation from ac-POSGs into RPOMDPs as it fits well with the formalism of RPOMDPs. As the complexity results on ac-POSGs uses the standard notion of a policy for the min-player, the paper provides Lemmata A.3 and A.4. Lemma A.3 shows a compilation of an ac-POSG with factored prescriptions to a standard ac-POSG. Conversely, Lemma A.4 shows that the standard min-player policies correspond to class-constant prescriptions (i.e., a special case of factored prescriptions). The authors even acknowledge that the policies using factored prescriptions can be strictly stronger. This makes an issue when we connect Lemma A.4 with the ac-POSG-RPOMDP translation because the translation assumes as its input an ac-POSG whose min-player's policies range over all factored prescriptions. The issue stems from the fact the translated RPOMDP can use any environment policy π\pi in the infimum defining the value of WW whereas the original ac-POSG can use only policies with class-constant prescriptions. Thus, the value of WW need not be preserved.

Questions for authors

Is it possible to fix the above mentioned issue?

5 comments
AuthorsOpenReview ↗

Response to Review vFGS

We thank the reviewer for the valuable feedback and questions. We believe that though theoretical, our paper is within the scope of ICLR; there have been many theoretical papers published at NeurIPS/ICML/ICLR with technically involved proofs, including papers on robust MDP models. While our proofs are unavoidably technically involved, in the main paper we have tried to provide proof overviews to help guide the reader and make the proofs accessible. We will expand on these on the lines suggested by reviewer FH6T.

[Q1] Regarding the proof of complexity lower bound, we would like to clarify that all our claims and proofs are correct, and that there is no soundness gap. We indeed lift the lower bounds and undecidability results from the POSGs of (Chatterjee et al., 2013) to RPOMDPs as follows. Given an ordinary POSG of (Chatterjee et al., 2013), Lemma A.4 (lines 1073-1074) translates it into what we call a “class-constant prescription POSG”, in which the same distribution is assigned to every min-state of an observation class. The translation preserves the value for all four analyses (sure, almost-sure, limit-sure, and quantitative) and any ω\omega-regular objective. Then, Theorem 3.4 translates this class-constant prescription POSG into an RPOMDP, again in a value-preserving way. Combining these two translations allows us to lift the lower bounds and undecidability results of (Chatterjee et al., 2013) on POSGs to RPOMDPs.

While this argument is presented in the "Complexity Results" paragraph in l.469-480, we agree that this paragraph is brief and that it should be expanded to clarify this, with an explicit pointer to the exact case we rely on. We propose the following revision of the paragraph to clarify this.

"Complexity Results. The reductions in Sections 3.1 and 3.2 establish equivalence between (s,a)(s,a)-rectangular polytopic RPOMDPs and ac-POSGs as defined in Sections 2 and 3. Lemma A.3 compiles the ac-POSGs of Section 3 into ordinary POSGs of (Chatterjee et al., 2013) with values and all four objectives preserved, at polynomial overhead. Together with Section 3.1, this means the upper bounds of (Chatterjee et al., 2013) apply to our RPOMDPs, since any algorithm for ordinary POSGs can be run on the compiled game to decide the original ac-POSG, and hence the equivalent RPOMDP.

For the lower bounds, given an ordinary POSG of (Chatterjee et al., 2013), Lemma A.4 (lines 1073-1074) translates it into what we call a “class-constant prescription POSG”, in which the same distribution is assigned to every min-state of an observation class. The translation preserves the value for all four analyses (sure, almost-sure, limit-sure, and quantitative) and any ω\omega-regular objective. Then, Theorem 3.4 translates this class-constant prescription POSG into an RPOMDP, again in a value-preserving way. Combining these two translations allows us to lift the lower bounds and undecidability results of (Chatterjee et al., 2013) on POSGs to RPOMDPs.

Thanks to our unified treatment across observability regimes, when both players have full observation, we have the equivalence between stochastic games and RMDPs. When the min-player has full observability, we have the equivalence between POSGs with the fully observable min-player and 1s RPOMDPs. This allows us to lift complexity results of (Chatterjee et al., 2013) to RMDPs and 1s RPOMDPs, as in Table 1.”

Reviewer_vFGSOpenReview ↗

My concern is not clarified

Thank you for clarifying the intended composition. My concern remains at its second step. Lemma A.4 preserves the value when the min-player is restricted to class-constant prescriptions, whereas Theorem 3.4 applies to ac-POSGs with the full factored prescription strategy space. The constructed RPOMDP likewise allows all corresponding environment strategies. Since the paper notes that these strategy spaces can have different values, please explain how the class-constant restriction is preserved by Theorem 3.4, or identify the specific lower-bound source instances for which the restriction is vacuous (for example, because the min-player has full observation).

To be more precise, let Π0\Pi_0 be the class-constant prescriptions and Π\Pi be all factored prescriptions. Lemma A.4 establishes that an ordinary POSG has the same value as your translated POSG restricted to Π0\Pi_0. On the other hand, Theorem 3.4 establishes equivalence between an ac-POSG and an RPOMDP using Π\Pi. So, to join Lemma A.4 and Theorem 3.4, one would need the following:

sup⁡σinf⁡π∈Π0Prσ,π(W)=sup⁡σinf⁡π∈ΠPrσ,π(W)\sup_\sigma\inf_{\pi\in\Pi_0} Pr^{\sigma,\pi}(W)=\sup_\sigma\inf_{\pi\in\Pi} Pr^{\sigma,\pi}(W)

I do not see where this is proved.

AuthorsOpenReview ↗

Further clarification

We sincerely appreciate following up on our response and the reviewer’s thorough and constructive review of our paper. Following your response, we realized that the lower bound argument in the paper and our response forgets to mention one very important aspect that we implicitly assume. We are deriving lower bounds for 1-sided RPOMDPs, which then as a special case also imply lower bounds for general (2-sided) RPOMDPs. In Table 1, all reported lower bounds for 1-s RPOMDPs and 2-s RPOMDPs are the same (the two “Open" cells in Table 1 refer to unknown upper bounds). Hence, it suffices to prove lower bounds for 1-s RPOMDPs.

The reviewer is absolutely right that the argument that we posted does not work for 2-s RPOMDPs, where the second step fails. However, the argument is correct for 1-s RPODMPs. Here, we are using Lemma A.4 only in the special case when the min-player has full observability, for which (Chatterjee et al., 2013) hardness and decidability results already hold. In the case when the min-player has full observability, each observation corresponds to a single state. Therefore, prescriptions and ordinary strategies coincide. Then, Theorem 3.4 translates POSG in which the min-player has full observability into an 1-s RPOMDP. Combining these two translations allows us to lift the lower bounds and undecidability results of (Chatterjee et al., 2013) on POSGs to RPOMDPs.

We will revise the Complexity Results paragraph to highlight this. Also, in the Appendix, we will add a new Corollary following Lemma A.4 for the special case of POSGs in which the min-player has full observability. In the proof of lower bounds, we will then refer to this new Corollary rather than the more general Lemma A.4 statement to make this point clear.

Reviewer_FH6TOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper establishes polynomial-time reductions in both directions between RPOMDPs and alternating zero-sum POSGs under ω-regular objectives. These reductions allow the authors to transfer known complexity results from POSGs to RPOMDPs for a range of satisfaction criteria. The paper also carefully addresses a technical challenge related to preserving the information structure and strategic capabilities of the players across the reductions.

Critical strengths

The main result are the polynomial-time reductions in both directions between RPOMDPs and alternating zero-sum POSGs under ω-regular objectives.

Critical weaknesses

The main limitation of the paper is the organisation of its central contribution. The manuscript mixes the statement of the main scientific result with the technical constructions required to establish it. As a consequence, the reader must reconstruct the overall argument from a sequence of intermediate reductions and lemmas.

The main text should focus on the equivalence between the considered classes of robust POMDPs and ordinary zero-sum partially observable stochastic games, stating precisely the assumptions, the properties preserved by the reductions, and the resulting complexity guarantees.

The intermediate models, including the pre-min transformation and factored prescriptions, should primarily serve as proof devices. Their purpose and necessity could be briefly explained in the main text, while their formal constructions and supporting proofs could be deferred to the appendices.

Such a reorganisation would make the central contribution more accessible and, more importantly, allow reviewers to assess its novelty, theoretical significance, and scope without having to reconstruct the logical structure of the argument themselves.

Questions for authors

Why not directly state the equivalence between RPOMDPs and alternating zero-sum POSGs under ω-regular objectives?

1 comment
AuthorsOpenReview ↗

Response to Review FH6T

We thank the reviewer for the valuable feedback.

[Q1] We agree with the reviewer that this change would improve the presentation, and propose the following restructure of Section 3 to bring the main result up front:

  • We will open Section 3 with the combined equivalence statement (Theorem 3.1 together with Theorem 3.4) as the main result: an (s,a)(s,a)-rectangular polytopic RPOMDP MM and its induced POSG GG are inter-reducible in polynomial time.
    We will clearly state the claims and assumptions: (1) The reductions work for all four analyses (sure, almost-sure, limit-sure, and quantitative), (2) for any ω\omega-regular objective, and (3) reductions are polynomial time, measured with respect to the model size and the vertex list representation of uncertainty sets.

  • We will then proceed to the reduction details and proof outlines. We believe that Section 3.1 is sufficiently self-contained and will keep it as is. For Section 3.2, we will again start with the "Key Challenge and Our Solution" paragraph to provide the intuition and outline of the reduction, followed by technical details as currently in the paper. Since the camera-ready version allows 10 pages, we will have sufficient space to implement this change.

On the reviewer's direct question, why not state the equivalence directly: the proof is naturally built as a composition of two value-preserving reductions, and we had organized the text to follow that proof order. We agree that the main result should be stated first, with the two-step construction presented afterward as the mechanism by which it is proved. We believe that the above revision will improve the presentation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.