- 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 -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 -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 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
Thank you for your responses. Based on the agreed clarifications and responses to other reviewers, I retain my recommendation of clear acceptance.
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 ω-regular objectives and deriving reductions in both directions, both for RMDPs and RPOMDPs.
Some other works consider interval and L1-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 L1-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.