On Evaluating Policies for Robust POMDPs

We thank the reviewer for their feedback and comments. We will incorporate their comments in the final version of the paper. First, we answer the reviewer's question.

You consider the setting where nature is adversarially picking environment parameters, and nature can change those parameters every timestep, after looking at the agent's past actions. How does that differ from the following setting: nature looks as the agent's whole policy, and then picks (permanent) environment parameters once?

If nature picks permanent environment parameters, this corresponds to picking a POMDP with the exact same states as the RPOMDP, i.e., static uncertainty. Our problem, where nature can change the parameters every timestep, i.e., dynamic uncertainty, gives nature more power than with static uncertainty, as has been shown in (Bovy et al. (2023)), and is therefore more robust. Even if nature can pick the environment parameters after observing the agent's entire policy, nature can achieve a lower reward by choosing different environment parameters at different histories.

Next, we aim to clarify some of the comments made in their review.

I don't understand what $Var_{s,a}$ means.

When considering $s,a$-rectangularity, each uncertainty variable can only influence the transition and/or observation probabilities in one state-action pair. We can therefore partition the set of uncertainty variables into smaller sets $Var_{s,a}$ that each only influence a single state-action pair $(s,a)$. The entire uncertainty set can then be written as $\mathcal{U} = \set{Var \to \mathbb{R}} = \bigtimes_{s,a}\set{Var_{s,a} \to \mathbb{R}}$.

One can think of the transition and observation functions to be of type $\mathcal{T} \colon S \times A \to (\mathcal{U} \to \Delta(S))$ and $\mathcal{O} \colon S \times A \to (\mathcal{U} \to \Delta(Z))$. We'll clarify the notation of $Var_{s,a}$ in the final version of the paper

What does it mean to say $\mathcal{P}$ is convex? Do you mean the set $\set{\mathcal{P}(u) : u \in \mathcal{U}}$ is convex? Likewise, is $Extremes(\mathcal{P})$ really $Extremes(\set{\mathcal{P}(u) : u \in \mathcal{U}})$?

Indeed, we mean the set $\set{\mathcal{P}(u) : u \in \mathcal{U}}$ is convex and $Extremes(\set{\mathcal{P}(u) : u \in \mathcal{U}})$. We thank the reviewer for bringing this to our attention. We will fix this in the final version of the paper.

Why do you ever define $V^n = \min_{\theta\in\Theta} \max_{\pi\in\Pi} V^{\pi,\theta}$ or talk about the Nash equilibrium?

We discuss the Nash equilibrium because, ultimately, it is what an RPOMDP solver aims to find, as it is considered the standard robust objective. We use it to explain the solvability classes. We also need to explain the Nash equilibrium to discuss the difference in policy types between the Nash equilibrium's nature policy and the best-response nature policy. We indeed use $V^n$ only in our definition of the Nash equilibrium and can simplify this notation in the final version.

Do you mean "we can potentially find an optimal policy"?

We mean that we can use the set of optimal agent policies against $\overline{\Theta}$ to find an optimal policy against $\Theta$, but we still need to evaluate all the agent policies to find whether these policies are optimal against $\Theta$. We will clarify this.

Isn't the objective different when an RPOMDP with a stationary nature policy represents a POMDP.

If the stationary nature policy is known, the objective reduces to optimizing the POMDP, which shares the same states as the RPOMDP, by taking an expectation over the uncertain feature of the state corresponding to the nature policy. Our statement is intended as a contrast to non-stationary nature policies, where, in combination with the RPOMDP, the POMDP has a far larger, possibly infinite, state space. We never assume that the nature policy is known, and the objective for the agent always remains to maximize against the worst-case nature policy. We will revise our statement to clarify this point.

Should $R_{n}(\langle s, x, a \rangle) = - R(s, a)$?

No, the objective in the nature MDP is computing a nature policy that minimizes the discounted reward. Therefore, we use the same reward function as in the original RPOMDP. We describe that the best-response nature policy given an agent policy $\pi$ is the $\arg\min_{\theta\in\Theta^\pi_n} V_n^{\pi\theta}$ on line 258. We will make the objective in the nature MDP more explicit.

"b" is not defined (although I knew what it meant).

We define $b \in \Delta(S)$ on line 98, but we will clarify 'recall $b\in\Delta(S)$ is an agent belief' before Definition 4.

References

Bovy et al. (2023): Eline M. Bovy, Marnix Suilen, Sebastian Junges, Nils Jansen: Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs. IJCAI 2024: 6697-6706

We thank the reviewer for their feedback and comments. We will incorporate their comments in the final version of the paper. Below, we answer their questions.

Summary

Intuition of solvability and relation to best-response

We do not view the solvability classes as methods to construct optimal nature policies. We define the solvability classes to classify challenging benchmarks, and propose a best-response evaluation method to enable robust policy evaluation given an (arbitrary) agent policy. These are distinct concepts of the paper, but in our experimental evaluation, we use both concepts together. Specifically, to show that (1) some commonly used benchmarks belong to naive solvability classes, and (2) our best-response evaluation is sound.

Real-world applicability

There exist many real-world problems described by RPOMDPs. We argue that we need a means for thorough evaluation of (the robustness of) policies for problems described by RPOMDPs. For instance, previous work evaluated their algorithms on benchmarks that we show by using our solvability categorization do not capture the complexities of RPOMDPs. Our paper addresses this gap in the literature.

Questions

The intuition behind solvability is not very obvious. While I see that it provides an argument for finding optimal policies in smaller subsets of environment parameters and ensuring global optimality, I do not really see how to use it to derive these policies, and I also do not follow how does it apply to the idea of evaluating RPOMDP policies against best response parameters. Can the authors expand on this, and justify the need for considering the given solvability definition?

We would like to clarify that the solvability classes are defined to classify RPOMDP benchmarks: we do not view them as methods to construct optimal nature policies.

Aside from providing theoretical insights (Section 3.2), we can empirically identify whether an RPOMDP benchmark belongs to any of the solvability classes. In our evaluation (left-hand side of Figure 4), on each benchmark, we:

• construct nature policies that are naive (e.g., based on ignoring partial observability or by taking the center of the uncertainty set),
• compute an (optimal) agent policy against said nature policies (if a naive nature policy is given, the problem reduces to a POMDP for the agent), and
• evaluate these agent policies against the best-response nature policies.

For instance, if the optimal agent policy against the naive nature policy has the same best-response value as the optimal RPOMDP policy (which considers the full range of potential nature policies), then we have evidence that an RPOMDP benchmark is in that solvability class.

Similar to the question above, the idea of naive solvability seems arbitrary (which the authors seem to agree as per their own assessment).

Indeed, we postulate that these are some of the solvability classes that are useful to identify. This is evidenced by the fact that in our experimental evaluation, nature policies in these solvability classes work well on many existing benchmarks. Yet, we do not claim that it is an exhaustive classification.

Furthermore, the authors propose this taxonomy of solvability in terms of the nature policies, but provide results about solvability for specific nature policies that are not necessarily the best response. How does the concept of solvability link to the proposed evaluation method?

As we explain in more detail in the previous answer, the concept of solvability is not directly linked to the proposed evaluation method. We use both concepts in our evaluation pipeline to test whether an RPOMDP benchmark is challenging (i.e., does not belong to a naive solvability class).

If an RPOMDP benchmark is not naively solvable, a method that reports a different optimal value than the actual best-response value, i.e., worst-case value given the computed agent policy, indicates that a method is not able to deal with more complex structures that may appear in RPOMDPs.

The authors touch slightly on the topic, but I would like to further understand the utility in practice of RPOMDPs. As in other minmax, zero sum game frameworks, obtained policies can be extremely conservative as some (very unlikely) particular nature parameter may force the optimal agent policy to act very suboptimally in other regions of the parameter space. As this work provides benchmarking and evaluation baselines for RPOMDPs, what problems do the authors consider it can be useful for?

RPOMDPs are designed to provide robust and conservative policies, as they are inspired by the robust optimization field. Such policies are, for instance, often a requirement for safety-critical settings where the model cannot be fully specified. Our Echo benchmark, inspired by predictive maintenance problems, resembles such a setting.

Regarding the scalability of solving the nature MDP, the authors state that MCTS fails to provide valid nature MDP solutions in larger RPOMDPs. Is there a way of addressing this, or is it an artefact of the complexity of the resulting MDPs?

The scalability of our evaluation method is indeed an artefact of the Nature MDP that we construct. Note that prior to our work, it was unclear how to perform evaluation in RPOMDPs efficiently in general. Furthermore, we are not restricted to using MCTS, and our formulation allows for robust policy evaluation in RPOMDPs to directly benefit from advances in solving continuous-state MDPs.

Is the fact that Tiger and HeavenOrHell are 'naively solvable' a problem for general evaluation of RPOMDPs?

Yes, if one only evaluates on naively solvable benchmarks, one can't be sure of how the algorithm performs on benchmarks that do not belong to these solvability classes. Note that Tiger and Heavenhell are challenging POMDP benchmarks, but, as we show, this fact does not make them challenging RPOMDP benchmarks. To advance the field and establish with confidence what constitutes a good RPOMDP solver, we must have challenging benchmarks for RPOMDPs.

We thank the reviewer for their comments and feedback. We will incorporate their comments in the final version of the paper. We answer their questions below.

How we can say that the only categories of naive solvability in Section 3.1 are these three? Can there be possible other possible policies for $\theta$?

We propose that these three categories represent solvability classes that are useful and intuitive to identify. This is evidenced by the fact that in our experimental evaluation, nature policies in these naive solvability classes work well on many existing benchmarks. Yet, we do not claim that it is exhaustive. Additional categories of solvability can be defined as naive if so desired. We will clarify this in the paper.

And if it is possible to have other policies that can be considered naive, then does it somehow interact with the Theorems in Section 3.2?

This depends on the type of naive policy that would be considered. In particular, Theorem 1 implies that Echo is not stationary solvable, which means it could only become naively solvable if you add a new 'naive' non-stationary agent policy. In contrast, Parity is constructed with the particular naive nature policies in mind, and thus is more likely to become solvable given different nature policies.

We thank the reviewer for their feedback and comments. We will incorporate their feedback in the final version of the paper. We first summarize our response, then we respond in detail to the weaknesses and questions stated in the review.

Summary

Scalability

Robust policy evaluation in RPOMDP is an inherently challenging problem, as it requires searching over possible nature policies. Thanks to Theorem 3, we know that for the best-response (read: worst-case) value, we need not consider full histories for nature but only the memory of the agent. We use this result in our formulation into a continuous-state nature MDP, which is a more manageable formulation and directly benefits from advances in that area.

We acknowledge that policy evaluation is still challenging due to the continuous and potentially high-dimensional state-space. Specifically, we address this in our paper in the following way:

• we study scalability and the impact of the used approximation in our experiments (Q1),
• we address it in our limitation section (L346), and
• we highlight it as a potential direction for future work (L376).

Real-world applicability

There exist many real-world problems described by RPOMDPs. We argue that we need a means for thorough evaluation of (the robustness of) policies for problems described by RPOMDPs. For instance, previous work evaluated their algorithms on benchmarks that we show by using our solvability categorization do not capture the complexities of RPOMDPs. Our paper addresses this gap in the literature.

Response to comments

Impact of the approximate nature of Montecarlo approaches is not mentioned. Given that approximate policies are found with MCTS type approaches, aren't there gaps in evaluation?

We agree with the reviewer that our approximate evaluation method can lead to evaluation gaps. We discuss the necessity of an approximation directly after introducing the nature MDP (L263), and its impact is mentioned in our limitations paragraph (L346-347). Furthermore, we devote Q1 of the experimental evaluation to study the impact of the approximation (and the resulting evaluation). To briefly recap this research question, we indeed observe a few cases (e.g., Aloha, HealthDetection) with evaluation gaps. Nevertheless, for most benchmarks, we do not see such a gap, which suggests the MCTS approximation performs adequately. To alleviate the problem fully, we mention that future work could design solving methods that make use of the structure of the nature MDP (L376-377).

We respond to the following comment and subsequent question in a single answer:

It would seem that the current approach can have scalability issues especially with larger environments (e.g., ALOHA, HEALTHDETECTION)

and

Would help if the authors can provide inputs on scalability?

As discussed in Section 4, our evaluation method reduces the problem to solving a continuous-state MDP, which originates from having to evaluate policies with arbitrary (possibly continuous) memory representations. Thus, the limitations to scalability are the same as those for solving high-dimensional continuous-state MDPs. Our evaluation method is not tied to MCTS, but allows the use of any continuous-state MDP solver. In particular, this means that the scalability of our evaluation method will improve as continuous MDP solvers get better.

We point out that without Theorem 3, the policy evaluation problem would involve an exhaustive search in the space of possible nature policies; a problem much harder and less scalable than our formulation of solving a continuous-state MDP.

Response to the remaining questions

Can the authors provide inputs on generalisability of benchmarks beyond solvability, especially in real world problems?

The main goal of the proposed benchmarks is to explain and test solvability classes. In our paper, we identify a gap in the literature; the benchmarks used to test the solvers do not sufficiently represent the complexities of RPOMDPs. We argue that this solvability is relevant in the real world. For example, in security problems, it is often reasonable to assume an attacker can alter their plan based on the prior observations and actions of the defender. If we model this attacker as the adversary in an RPOMDP, then such memory-based policies could not be expressed by an RPOMDP that is stationary solvable. To this extent, our evaluation pipeline can be used to determine whether a solver can be robust against such adversaries.

While our benchmarks may be abstract, we note that the Echo benchmark is inspired by predictive maintenance problems, while the use of chain environments (such as Parity) for benchmarking is relatively common in RL (Castronovo et al., 2016; Bellinger et. al., 2021).

Are there any real world problems where this work will be useful?

There exist many real-world problems where agents need to deal with both model and state uncertainty. Such problems include any type of planning in dynamic environments (as caused by, e.g., weather or other agents) or unknown environments (such as in RL, or when using approximate models). Thus, we argue that we need a means for thorough evaluation of (the robustness of) policies for such problems. This work is a first step in that direction.

Can the provided approaches be extended beyond rectangular uncertainty sets?

Our construction extends to $s$-rectangular uncertainty sets by changing the nature MDP to one where the dependency on the agent's action in the state is omitted.

The tractability of non-rectangular uncertainty sets is still an open problem in the less complicated setting of RMDPs (L349-350); it is unclear how to efficiently address the fact that nature's choices are coupled across different states.

Although it may be conservative, assuming $(s,a)$-rectangularity is the most common (L349), as it provides a lower bound even if the problem at hand does not show any form of rectangularity. Therefore, if the rectangularity is unknown, it can be argued that assuming $(s,a)$-rectangularity is the most robust way to approach the problem.

At this point, to the best of our knowledge, no solvers for non-rectangular or $s$-rectangular RPOMDPs exist. Therefore, we focus on $(s,a)$-rectangularity uncertainty sets.

Theorem 3 and its discussion mention that best response nature policy is simpler than optimal nature policy. Can authors provide more quantitative or concrete examples of how this simplicity is important in practice?

The simplicity of the best-response nature policies originates from the fact that we focus on finding the worst-case value (worst-case nature policy) given an agent policy. We motivate evaluation w.r.t. the best-response with Example 1; the (Nash)-optimal nature policy typically does not result in the worst-case value for a particular agent policy. As a consequence of focusing on the best-response nature policy, we need not consider all possible agent policies, as would be required for the (Nash-)optimal nature policy. Moreover, Theorem 3 states that this policy only needs to be based on the agent's memory, as opposed to the full history. As a concrete example, consider an agent policy represented by a finite state machine with only $N$ nodes, such as those found by Cubuktepe et al. (2021) or Galesloot et al. (2024). Then, we need only consider nature's responses across this finite set of nodes.

References

Bellinger et al (2021): Colin Bellinger, Rory Coles, Mark Crowley, Isaac Tamblyn: Active Measure Reinforcement Learning for Observation Cost Minimization. Canadian AI 2021.

Castronovo et al. (2016): Michael Castronovo, Damien Ernst, Adrien Couëtoux, Raphael Fonteneau: Benchmarking for Bayesian Reinforcement Learning. PLoS ONE 11(6):e0157088

Cubuktepe et al. (2021): Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, Ufuk Topcu: Robust Finite-State Controllers for Uncertain POMDPs. AAAI 2021: 11792-11800

Galesloot et al. (2024): Maris F. L. Galesloot, Marnix Suilen, Thiago D. Simão, Steven Carr, Matthijs T. J. Spaan, Ufuk Topcu, Nils Jansen: Pessimistic Iterative Planning for Robust POMDPs. EWRL 2024

We would like to again thank the reviewer for their feedback and comments. Since the deadline for the discussion is approaching, we would like to ask whether our rebuttal has adequately addressed the questions and concerns raised in this review.