On Evaluating Policies for Robust POMDPs
Authors: Merlijn Krale
Eline M. Bovy
Maris F. L. Galesloot
Thiago D. Simão
Nils Jansen
Venue: NeurIPS 2025 poster ()
Keywords: Robust POMDPs
Policy evaluation
Planning under uncertainty
Primary area: reinforcement_learning
TL;DR: To advance evaluation of RPOMDP policies, we (1) introduce a formalization for suitable benchmarks, (2) define a new evaluation method, and (3) lift existing POMDP value bounds to RPOMDPs.

Abstract: Robust partially observable Markov decision processes (RPOMDPs) model sequential decision-making problems under partial observability, where an agent must be robust against a range of dynamics. RPOMDPs can be viewed as a two-player game between an agent, who selects actions, and nature, who adversarially selects the dynamics. Evaluating an agent policy requires finding an adversarial nature
policy, which is computationally challenging. In this paper, we advance the evaluation of agent policies for RPOMDPs in three ways. First, we discuss suitable benchmarks. We observe that for some RPOMDPs, an optimal agent policy can be found by considering only subsets of nature policies, making them easier to solve. We formalize this concept of solvability and construct three benchmarks that are only solvable for expressive sets of nature policies. Second, we describe a new method to evaluate agent policies for RPOMDPs by solving an equivalent MDP. Third, we lift two well-known upper bounds from POMDPs to RPOMDPs, which can be used to efficiently approximate the optimality gap of a policy and serve as baselines. Our experimental evaluation shows that (1) our proposed benchmarks cannot be solved by assuming naive nature policies, (2) our method of evaluating policies is accurate, and (3) the upper bounds provide solid baselines for evaluation.

On Evaluating Policies for Robust POMDPs
Merlijn Krale* Radboud University Nijmegen, The Netherlands verlijn.krale&ru. www.kkra.llrn... nl
Eline M. Bovy' Radboud University Nijmegen, The Netherlands eline. bovy@ru.
Maris F. L. Galesloot' Radboud University Nijmegen, The Netherlands maris. maris.galesleee
ml
Thiago D. Simão
Nils Jansen
Eindhoven University of Technology Eindhoven, The Netherlands
Juhr-Unnierssty Bochum & Radboud University Bochum, Germany & Nijmegen, The Netherlands n n. jajjanen@rrb.de
simao@tue.ni
Abstract
Robust partially observable Markov decision processes (RPOMDPss) model sequen- tial decision-maken manonn problems under partial observability, where an agent must be robust against range of dynamics. RPOMDPs can be viewed two-player game between an agent, who selects actions, and nature, who adversarially selects the dynamics. Evaluating an agent policy requires finding an adversarial nature policy, which is computationally challenging. In this paper, we advance the eval- uation of agent policies for RPOMDPs in three ways. First, discuss suitable benchmarks. We observe that for some RPOMDPs, an optimal agent policy can be found by considering only subsets of nature policies, making them casier to solve. We formalize this concept of solvability and construct three benchmarks that are only solvable for expressive method to evaluate agent policies for RPOMDPs by solving an equivalent MDP. Third, lift two well-known upper bounds from POMDPs to RPOMDPs. which can be used to efficiently approximate the optimality gap of policy and serve as baselines. Our experimental evaluation shows that (1) our proposed benchmarks cannot be solved by assuming naive nature policies, (2) our method of evaluating policies accurate, and (3) the upper bounds provide solid baselines for evaluation.
of nature policies. Second,
describe
Introduction
Partially observable Markov decision processes [POMDPs: 25 are ubiquitous for representing sequential decision-making problems under partial observability. POMDPs are used to represent real-world problems, such as robotics [31], infrastructure maintenance
39 38 and wildlife conser- vation 13 Yet, to model such problems, the dynamics of the problem need to be precisely known,
capture model uncertainty as two-player game between the agent, who picks actions, and nature, who adversarially picks the dynamics of the model. RMDPs can effectively represent model uncertainty arising reinforcement
which is often unrealistic 26 [57] Robust MDPs [RMDP: 23 43 53
learning (54. 11 37 or from abstraction [ 2 32), but do not account for partial observability. Robust POMDPs IRPOMDPs; 45] extend RMDPs with partial observability, and are thus more expressive. However, finding and evaluating policies for RPOMDPs is hard: existing solvers must use an extensive range of approximations to find and evaluate policies within reasonable time (53] 9.
To test such RPOMDP solvers, we require an evaluation pipeline. such as shown in Figure | To start, we need a set of benchmarks that allows us investigate the limits of the solver. Once the solver
Joint main authorship.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Estimated value
Policy under evaluation
Algorithm evaluation
Value
Benchmark models (Section S
Evaluation method (Section
Baseline algorithms (Section 5
Baseline
Baseline policies
values
Figure 1: Visualisation of the evaluation pipeline: benchmarks, an evaluation method, and baselines.
computes a policy for such benchmarks, we need an evaluation method to obtain a value for the policy. Finally, we compare this value with that of suitable baselines, and, if available, the estimated value of the policy as provided by the solver. In summary, an evaluation pipeline requires at least these three parts: benchmarks, an evaluation method, and baselines.
Most existing RPOMDP literature does not address all these parts. Firstly, the benchmarks used are often existing POMDPs extended with artificial model uncertainty [45] 9 15 42 22), and it is unclear such benchmarks are representative of RPOMDPs in general. Secondly, policy evaluation requires finding a worst-case nature policy, which can be prohibitively expensive. Existing work often either simplifies the evaluation process or reports the estimated value of the algorithm without explicitly evaluating the policy. Lastly, there are no readily computable baselines for RPOMDPs, hindering the efficient assessment of new solvers. In this paper, we aim to address all three parts of the evaluation pipeline with the following contributions:
(1) We propose novel solvability classes and corresponding benchmark problems (Section 3 We discuss the problem of defining benchmarks, and argue that suitable benchmarks should test whether a solver has considered all possible nature policies. Thus, if we can find an optimal agent policy for RPOMDP by considering only naive subsets of nature policies, then the RPOMDP is not a suitable benchmark. We formalize this intuition using the concept of solvability. Based on this concept, we define three small benchmarks for which we prove that the optimal agent policy cannot be found against naive subsets of nature policies.
robust policy evaluation method (Section 4). To evaluate agent policies, propose to compute a best-response nature policy, i.c., the worst-case nature policy against the policy under evaluation. We show that this evaluation method is less computationally expensive than finding an optimal nature policy, and we prove that the aforementioned hest-response policy is, in fact, the worst-case evaluation for fixed agent policy. Lastly, demonstrate that this evaluation method can be represented in general as an MDP with continuous state and action spaces, enabling evaluation with off-the-shelf (approximate) continuous MDP solvers.
(2) We propose
(3) We define two new efficient robust baselines (Section 5). We lift two existing POMDP approximation algorithms, QMDP (33) and the fast informed bound (FIB) [2I), to RPOMDPs, which we denote as robust QMDP (RQMDP) and robust FIB (RFIB), respectively. We prove the convergence and relative tightness of these approximations and highlight that, under conventional technical assumptions, both are tractable basclines to compute.
Finally, we conduct empirical evaluation that (1) shows that the new benchmarks cannot be solved by assuming naive nature policies, (2) validates the accuracy of our evaluation method, and (3) demonstrates the applicability of our approximations as baselines. We implement all methods in
Julia framework (based on POMDPs. jil (12) to facilitate future research; available on Zenodo [29
Preliminaries: Robust POMDPs
This section gives a comprehensive definition of RPOMDPs. We first introduce some basic notation.
We denote the set of all possible probability distributions over the (countable) set A as A(A), and all elements with non-zero probability the Iverson brackets (P) return 1 if P is true and 0) otherwise. Given convex set C, we denote the set of all extreme points as Extremes (C), and the centroid of the set, i.e., the arithmetic mean of all points in C, as Centroid (C). Lastly, given function f: X A(Y) and elements E X, y Y.
distribution
A (AA) as suрр(μ). For any predicate P.

---

(v r) denotes the probability of element y according to f(x), and y fa) denotes randomly sampled element y from fax)
Different definitions of RPOMDPs exist, as discussed in 3 We focus on a variant of their definition,
with some additional assumptions for simplicity.
Definition (RPOMDP). An RPOMDP a tuple M A,,,,, R, 7), with:
S. A and Ω (finite) sets of states, actions and observations;
4 S {f: Var R R Varl the uncertainty set, with Var a finite of decision variables;
T: + (S x A ((S) the uncertain transition function, which defines a transition
function T: S A + (S) for each assignment of decision variables u E El;;
O: + (S x A x S + ((2)) the uncertain observation function which defines an observation function O: S AxS- ((1)) for each assignment Ut;
* R: S x A + R the reward function.
by E ((S) the initial state distribution for initial belief);
7 E 1) the discount factor.
For notational convenience, we define the joint uncertain transition-observation function P: 4 (S A + (S x (2). with P(u)(s', s, a) (s (u) s, a,a,s' s'). Note that an RPOMDP with a singleton uncertainty set is a POMDP, a fully observable RPOMDP is robust
MDP [RMDP: 23 43 55] and RMDP with a singleton uncertainty set is MDP 48
Intuitively, RPOMDPs describe a zero-sum game between an agent and nature, with policies x and 6, respectively (3) The game starts in state so S as sampled from the initial state distribution by. At each timestep E N, the agent picks an action a E A according to its policy æ. Then, nature picks a decision variable assignment u4 LI according policy 0. Next, the environment transitions to state 8t-1 ~ ((u)) az), and emits an observation o₂ ~ (w))) at, 8t+1). Lastly, the agent and nature receive reward ra R(st, de), which is not observed.
Policies. Next, we introduce notation for memory-based randomized agent policies. Let C RN, with N E N. denote a memory space, Possible memory spaces include the set of beliefs (i.e. X C (S)) as used in [45)) or the set of memory nodes of a finite state controller (as used [5] Then, we define the set of agent policies
II {(o: X A(A), X x A x Ω - A(X)), where a denotes the action selection function, and the memory update function. Given a policy (a, r) II and a memory state 2; E X, the agent chooses action a₂ (zz), and updates it's internal memory state to 2++1 ~ T T(It, 0t, 0++1).
The formalization of our nature policies is based on two assumptions. First, we assume dynamic uncertainty (33 (or zero stickiness
(. which means nature can choose different decision variable assignment when revisiting state-action pair. In contrast, static uncertainty (or full stickiness) refers to the setting where nature must always choose the same decision variable assignment. Second, we assume nature has knowledge of the history of (1) the visited states, (2) the agent's memory states, and (3) the agent's actions Combining these assumptions, the set of nature policies is given as θ = {0: (S X x A) +u N E N). Note that weakening either assumption will yield more restrictive set of nature policies; thus, these assumptions provide a lower bound for any such setting.
Structural Assumptions. We make two additional structural assumptions. First, we assume the uncertainty set is (s, rectttnggula... Intuitively, nature can choose probabilities for any state-action pair independently. This means we assume that the set of decision variables Var can be partitioned into smaller sets Vara,a. such that (I) the uncertainty set is l X s.EES A Vurs,a + RJ, and (2) any decision variable in Var,,a only influences statc-action pair (3, a). This assumption is common in the RPOMDP literature and, similar the assumptions above, provides a lower bound for any non-rectangular setting. Lastly, we assume the set of joint transition- -osiitioonooseevatiion functions in P given the uncertainty set U, e., (P(u) u E Uf), is convex, closed, and graph- preperireeering.. Convexity is common assumption for tractability reasons, while closedness and graph-preservation are sufficient guarantee the existence of optimal nature policy (36). which we define below.
'This definition could trivially be extended to include uncertainty in the reward function 45
Nature does not require knowledge of observations, since these only affect the agent's memory states. 'n RPOMDP given an agent policy induces an infinite action POMDP for nature. Since nature has full observability, this can alternatively be interpreted as an RMDP with only single agent action. Thus, Theorem 2 from Meggendorfer et al. (36) applies, and we know optimal agent and nature policies exist.
3

---

0.5
S1
6.5
Solvability
P
P
50
96
Trivially
0.2
0.6
80
Center
0.1
0.6
80
0.5
R
100
Entropy
0.1
0.6
80
82
RMDP
0.1
0.6
80
===0
Stationary
0.1
0.9
80
None of the above
0.1
0.9
70
p [p.pl
84
Figure 2: Example RPOMDP with parameter values for solvability classes. We Toy* to denote the variant of this RPOMDP with the parameter values from "None of the above".
Objective. The agent's objective is to maximize its value, i.e., the infinite-horizzn expected cumu- lative discounted reward. We assume nature is adversarial, meaning it aims minimize the value. Let V == Ex - r"T, 8o ~ by] denote the value of the RPOMDP given policies π E II and 0 E O. We denote the optimal value for the agent and nature as V = mäX mingee V*,0 and V mingee max V respectively, with corresponding optimal agent- and nature policies T and 0" Va = V", then the underlying game has Nash equilibrium [46], in which case π² and 0* are called Nash policies. In this paper, we focus on the agent's 's objective Va, that is, finding and evaluating agent policies with respect to their worst-case nature policies. We note that this is related the notion of Stackelberg equilibria [46). As for POMDPs [35], solving infinite-horian discounted RPOMDPs is undecidable. Thus, in general, agent policies can be c-optimal at best.
3 Solvability Classes and Benchmark Models
In this section, we first propose the concept of solvability analyze the complexity of an RPOMDP. Next, we introduce three small RPOMDP benchmarks that are complex according to our definition. In 6 we provide empirical evaluation of the complexity of these benchmarks, which compare to standard POMDPs extended with artificial uncertainty sets.
We introduce the ToY environment (Figure 2 left). Throughout this section, will use variants of this model with different choices for the reward rh and uncertainty set [p. p. (Figure 2 right). For notational convenience, in the O states, the agent must choose between the safe action b, which will always yield a value r?, and the more risky action a. If a is selected, the agent must make another choice between and in the O states. Which action is optimal in the O and @ states depends both on the history up to that point, as this indicates in which states the agent
assume y 1. Intuitively, the agent needs to make two decisions. Firstly,
be, well the nature policy.
We highlight two different agent policies for this environment. The safe policy गं picks the safe action b in the O states regardless of the previous observation, which yields guaranteed value of rz. In contrast, the risky policy मे picks the riskier action a the states the previous observation was O and the safe action b otherwise. Furthermore, n. picks action b in the 3 states. For r? 80, T is optimal if p < 0.6 < p. and o is optimal if I 0.6 and 0.2 < ア < 0.6. Similarly, for r? = 70, T is optimal if p < 0.4 and 0.65 < We provide proof in Appendix
3.1 Solvability and O-solvable
We define the concept of solvability follows:
Definition 2. Recall that and II denote the sets of all nature- and agent policies. Define Il as the sei of agent policies that are optimal against both O well subset of nature policies O C O:
argmax min V r argmax min Va.8.
aell
8EB
#enl DE0
Then, a model M is O-solvable if 9
* 0.
Intuitively, model is O-solvable if there exists at least one optimal agent policy against the subset of nature policies e that is also optimal against all nature policies O, For such models, solvers that

---

only robust against θ could still find optimal agent policies. For some subsets θ this property may be undesirable for benchmarks, as we will discuss below. Note that O-solvability does not imply that 0" E O nor that the value against these sets is equal. Below, we define different solvability classes based on whether a model is solvable for particular 6.
Trivial solvability. We first consider the most extreme case. A model is trivially solvable if it is solvable for any set O. Such models are unsuitable as benchmarks, since they do not adequately test whether solver has considered all possible nature policies.
Example 1. TOY with uncertainty set E [0.2, 0.6] and reward = 80 is trivially solvable, since T.P. is optimal for any choice of 9.
Naive solvability. Next, consider models where the optimal value does depend on the choice of the nature policy 0, but where a naive choice of suffices. Such models are not adequate to show the capabilities of solvers to be robust against all possible nature policies, and are thus unsuitable as benchmarks. We define the following three nature policies that induce a naive solvability class:
Bemmer. which picks decision variables such that P(u) Centroid (fP(u) u E U}). For RPOMDPs constructed by extending a POMDP with model uncertainty, this nature policy often corresponds to the original POMDP.
Oyn. which picks decision variables to maximize the entropy of the probability distribution of each transition. This nature policy generally results in high uncertainty for the agent. BRMDP. which picks decision variables that are optimal in the underlying RMDP, i. c., optimal against a fully observing agent policy. In particular, this nature policy is good if partial observability has little effect on the optimal agent policy.
Thus, we call model naively solvable if it is either {fcenter {8 }-, or [fRMDe -olvvabee. This list not exhaustive; additional solvability classes can be defined as naive if so desired.
TOY with p E [0.1, 0.6] and r? = 80 is not trivially solvable, since मे. is optimal against O but is not optimal for each individual 6. For example, if if) {p + 0.13, the agent can gain higher value by choosing the risky action a in the states and action b in the states, regardless of the observation history. However, मh is optimal against all the naive policies (Comer(.) {p + 0.35), (p = (p >> 0.53, and (RMDr()) = {p +> 0.6), which means the model is naively solvable.
Example 2.
Stationary solvability. Lastly, model is stationary solvable if it is solvable for the set of stationary nature policies Stte A stationary nature policy chooses the same variable assignment for all histories, and can therefore be respresented by single variable assignment: St U. Intuitively, an RPOMDP with a stationary nature policy induces a POMDP with the same state space as the RPOMDP. In contrast to the previous solvability classes, the set of nature policies remains continuous. We are not aware of a way to exploit the stationary solvability of a model to solve it. Thus, we do not consider stationary solvable models unsuitable benchmarks.
Example 3. Consider ToY with p E [0.1, 0.9) and 80. Using similar logic as above, against all naive nature policies 0 E {OCeners Owu, ORMPP), it is optimal for the agent to lake the risky action a in the O states for one of the possible observation histories. However, for any agent policy that takes risky action in O there exists a stationary nature policy that yields a lower value than r3. Thus, n; the only optimal policy against both 5 and O meaning the model is stationary solvable and not naively solvable. In contrast, if we use the same uncertainty set with = 70, taking the risky action a in O is optimal against all stationary nature policies. while nद is optimal against the set of non-stationary policies. Therefore, the model is not stationary solvable.
3.2 Benchmarks
We introduce three novel benchmark environments that, according to our classification above, require solving against expressive nature policies. The first, denoted Toy*, is the variant of the Toy RPOMDP (Figure 2) that does not fall within any of our solvability classes, i.e., with parameter values from "None of the above". In the following, we provide
more benchmarks.
ECHO. The ECHO environment (Figure 3, left) is inspired by predictive maintenance problems. Starting in one of two distinguishable states or y, the agent picks an action a; with i E (x. v)- Based on this action, the agent transitions to the state n,, and can then take the echo (e) action to transition to state i. However, the machine has probability 8 to transition to the broken states x' or
5

---

dx
OLL
Evoi,
+
OUL OLd
Gy
0.5
0.5
p
Even
(M
Evrn
OMI
dg
By
s-Twn
== repuir, =
echo
Figure 3: Visualizations of the ECHO environment (left) and PARITY environment (right).
y' instead, which return the same observations as x and y. From these, the agent always transitions to state n', where the outcome of the echo action is determined by parameter p E lp. pl. The agent receives reward of for taking the echo action in f2 or Rty, but none in n'. Alternatively, they may take a repair (r) action in any of these states at a cost of -1, which returns the agent to Wg or Byy with probability 0.5. We make the following claim about this environment:
Theorem 1. ECHO, with p 0.01, p 0.99, å 0.1 and y 0.95, is not in any of the solvability classes defined in Section 3.1
We give a more general formulation of this theorem, as well as a proof. in Appendix |A.2.I
Intuitively, whether the agent previously played a ay.
a non-stationary nature policy can pick p depending while a stationary nature cannot. Thus, the optimal policy will sometimes repair even it is uncertain whether the machine is broken, while this is always suboptimal against stationary nature policy.
PARITY. Lastly, we consider an abstract chain environment called PARITY (NV) parameterized with N N as visualized in Figure (right). The environment consists of a chain of indistinguishable states 8q to &,, and the agent receives a reward when reaching 8N. do so, the agent can guess the parity of its current state 8,, and can choose actions with either deterministic (Even, Odd) or stochastic (s-Even, s- s-Odd) outcome. When correctly guessing the parity in state s;, the agent moves to state 8,+1 when choosing deterministic actions, and to states si+1, 81+2 814-3 with probabilities Pi E P1, P2 E P2, Pa Pa otherwise. However, the agent moves to state 5;-2 for incorrect guesses. Stochastic actions take the agent further average, but make it harder to guess correctly in the future. In addition to finite-length chains, we consider a chain of infinite length with the same dynamics, denoted PARITY(DO)) where the agent receives an immediate reward equal the number of steps they take. We show this problem can be reduced to a 9-state model in Appendix A.2.2 For this environment, we show the following with regard to solvability:
Theorem 2. PARITY with P1 = {0.2), P2 [0.1, 0.7]. P3 [0.1.0.7] and 7 2 0.73, is not naively solvable.
We provide a proof in Appendix A.2.2 Intuitively, our proof shows that optimal policies for naive subsets of nature policies take the riskier stochastic actions, which is suboptimal in the worst case. We empirically show in Section 6 that PARITY(10), with with P. = {0.1), P2 = [0.5, 0.8). P3 = [0.1, 0.4), and y = 0.95 also not naively solvable.
4 Evaluating Agent Policies in RPOMDPs
In this section, consider the problem of policy evaluation for RPOMDPs. To evaluate an agent policy π = (a, T) E II, we must consider against which nature policy to evaluate. One choice is, if it exists, evaluate against the optimal nature policy 0*, the worst-case nature policy when considering all possible agent policies. However, reasoning over all possible agent policies is often intractable, and is unnecessary if will only use 0* to evaluate a single policy. Moreover, there might be alternative nature policies that yield lower values, as the following example illustrates.
Example 4. Consider an agent policy in the ToY* environment (Figure 2 that always picks action the states, then b the states. This policy achieves a close-to- topottmall value of 662 against 0*, but is highly exploitable by a nature policy that chooses p O, achieving a value 0.

---

Since evaluation against 0 does not always give a good indication of the robustness of policy, we propose to evaluate the policy и against its own worst-case nature. which we denote as the best- response policy 0 E argmingge Vx.e. In practice, finding (approximations of) 0 is computationally cheaper than finding 0" In particular, we show that for (s, a)-rectangular and dynamic uncertainty models, the policy type of O is typically simpler than that of 0", which suggests that it is easier to find. Recalling P and Extremes (-) from the preliminaries, we state this as follows:
Theorem 3. For any agent policy π E II there exists a best-response nature policy 0 X - U such that Vx E x (1)(())) E Extremes ((P(u) u (ueu)))
We provide full proof in Appendix B Intuitively, nature does not need to consider the whole history since, due to (s, a--rettangularity can pick variable assignments that are optimal for any visited state-action pair. However, nature's 's decision should still be based on what the agent will do in the future, which depends on the agent's current memory state x E X, as the agent policy is stationary over X and the memory update r is fixed for policy π = (a, 7) E II. Moreover, since the agent policy is fixed, nature enjoys more expressive power in the variable assignments it chooses. Therefore, nature only needs to consider subset of the policy class θ to select the best-response actions.
Now, using Theorem 3 we propose a method for finding 8 In particular, since 0 is Markovian in X, we can represent our problem as a (possibly continuous-space nature MDP with state space S, X, action space An Ut and dynamics that represent both the underlying RPOMDP and the memory update of the agent. To simplify our notation, we use an expanded state space that explicitly includes the current state and agent action. that case, we define the nature MDP as follows:
Definition 3 (Nature MDP). Assume we have an RPOMDP M = (S, A, U, T, O, R. 7) and an agent policy tuple π (a, r) E II that uses a (possibly continuous) memory space X. Then, the corresponding nature MDP M, is defined as M = (Sn, An, Tn. Ra: Hn, 7), with:
Sn = S x X X A the state space;
An = {u E 44] (P(u) E Extremes ((P(u) | {})} the action space.
Tn: Sn An - (Sx)) the transition function, defined as:
Tu((s', ,²'a") (s, a), an) = =aad | x')
Eoea P(an)(s', s,)) 1x,,,)).
Rn: Sn + R the state-based reward function, with R, ((s, x, x. R(s,a).
Un E (S,,) the initial state distribution, with pa va((s, = a(a x) (s).
where Zo E X is the initial memory for policy n, i.e. Zo = bo if the policy is belief-based.
Remark 1. For any nature state Sn (s, E Sa, transitions only depend on decision variables in the set Var,,a- Thus, in practice, the action space An in the nature MDP M. can be represented using state nate-dependent action sets An (sn) of much smaller size, i.e., [An())) < Anl
The action space An of the nature MDP M is a subset of the action space of nature in the corre- sponding RPOMDP M. Therefore, the set of policies for M,, denoted θ = (0: Sn - An). are also valid nature policies for M. Let V.=.0 denote the expected reward of policy 0 E O in the nature MDP M.. Then, by construction, the following holds:
Lemma 1. Given an agent policy E πI and nature policy 0 Og. Then, the value of 0 in the nature MDP equals the value of 9 against x in the RPOMDP, i.e., V,=
V=.0
Corollary 1. There exists best-response nature policy 0% argmingge: VIT.9.
Corollary D follows from the observation that valid policies in M exactly overlap with the set of policies described in Theorem 3 This implies we can find 0 by solving, i.e., finding the optimal policy for, the nature MDP M The construction of the nature MDP generalizes the robust Markov chain construction of Galesloot et al. [55 to arbitrary memorization schemes 7 of the agent. We note that An is finite if P is a convex polytope and S, is discrete if X is discrete. Both conditions hold for the setting of Galesloot al. 15), which is why their robust policy evaluation scales to relatively large state spaces. However, the state-space of MI is continuous for belief-based policies, the action space is continuous in general, and the resulting value function of M can be discontinuous and non-convex. Thus, in practice, we may have to resort to an off-the-shel approximation method for solving M., incurring an approximation error. We note that the quality of the approximation and the scalability of solving the nature MDP directly connect to advances in solving continuous-state MDPs.
'This is commonly the case if the uncertainty set is comprised of probability intervals or the & norm, but generally not for uncertainty sets based on the la norm or the
divergence.
7

---

Efficient Approximations for Robust Agent Policies
In this section, we lift value approximation methods from POMDPs to their robust counterparts in RPOMDP. These approximations are helpful in multiple ways. Many existing POMDP algorithms, both online [59] and offline [52], use approximations as upper bounds to guide exploration and initialize value estimates. While any choice for 0 E θ is valid upper bound, using tighter upper bounds often leads to better results more quickly [30.. Furthermore, these approximations are ideal candidates to serve as baselines and provide sanity checks in evaluation, such as the one we conduct Section as they provide reasonable bounds on performance that are efficient to compute.
Recall b ASS) is an agent belief. Let 6, be the unit belief with b(s) = L, and B5 {b, E S} C (SS) be the set of all such beliefs.. Then, we define robust variants of the QMDP-bound [34] and the fast informed bound [FIB;[21), namely robust QMDP (RQMDP) and robust FIB (RFIB), as:
Definition 4. QRMDP and QREIB are the fixed point of the operators HROMDP and HREIB, defined as:
HROMDrQ = --b6e b(s)
a((,a)+
+ inf Σ MELl e'ES
| |s, ss)a) T())(d
max Q(b,, and (2) a'EA
SES
HaFmQ(b, = b(s) R(s,a) + inf wel
Σ
max
P(u)(s' (,, ((b,,,
a'EA
$ES
OEN
E'ES
We prove both these operators are contraction mappings in Appendix Of the supplemental material, guarantecing the existence and uniqueness of these fixed points. Intuitively, RFIB corresponds the worst-case value under the assumption that the agent observes the current and future states from the next timestep onwards with a one-step delay, while RQMDP corresponds to the same assumption with no delay. This matches their POMDP variants. Let QRPomdP be the fixed point of the robust Bellman equation for RPOMDPs [5]. We highlight the following property:
Theorem 4. Regarding tightness, the following inequalities on the fixed points hold:
4b E (S)), Va E A: QuMPr(b, a) 2 Qurm(b, a) 2 QRROMDr(bb a).
We provide proof in Appendix C of the supplemental material. Intuitively, the theorem follows from the fact that the operators are contraction mappings and unequal. As for their non-robust variants, both QRMDP and QRFIB depend only the Q-values for state-action pairs. Thus, precomputing the (approximate) fixed point for beliefs b. E By allows computing the bounds for any belief efficiently, tractable depends the uncertainty sets. Both convex
Whether or this precomputation optimization problems for convex uncertainty sets. In particular, the inner supremum of Equation (2) solvable with lincar program, or by using an efficient bisection method [43] Section 7.2] if the uncertainty sets are convex polytopes, while for Equation (3) it is solvable via linear relaxation of a mixed-integer program, which means both require polynomial time.
Experimental Evaluation
We empirically evaluate our benchmarks and evaluation pipeline via the following questions:
(Q1) Evaluation pipeline. How accurate is our pipeline in evaluating policies?
(Q2) Benchmarks. Can our proposed benchmarks be solved using a naive nature heuristic, or one of our efficient approximations? How does this compare to other benchmarks?
(Q3) Approximations. How do our approximations perform as baselines?
We first provide brief overview of our experimental setup, and then address (Q1) (3) We include
more details in Appendix D and provide the code to reproduce the experiments on Zenodo [29].
6.1 Experimental Setup
Implementation and algorithms. We implement our evaluation method in the Julia programming language, using a variant of the POMDPs. jl framework [12] for RPOMDPs with interval uncertainty sets. To solve these RPOMDPs, we use three separate algorithms: variant of RHSVI (5) with minor alterations, as described Appendix [.I] as well as our approximate solvers RQMDP and
RFIB from Section With RHSVI, compute both robust policies on the RPOMDP M, well as
8

---

M
RHSVI ROMDP
TOY"
Moaner Myn
MACHINK
RFIB
MRMPP
PARITY((c)
P1R
TICRR
HEAVENORHELL(S)
HEAVENORHELL(11))
MINIHALLWAY
ALOHA(10)
REPLACEMENT
HRALTHDETECTION
0.5
0.0
Relative value gap (Vam)
Relative value gap (Van)
Figure 4: The relative value gap Vap (T) = vT V for each policy π. where V=. obtained by (approximately) solving the nature MDP M On the left, policies are computed using RHSVI on the RPOMDP model M or on the naive POMDP models Mcemer. MEn: and MRMDP. On the right, policies are computed using different RPOMDP algorithms. Arrows denote outliers.
non-robust POMDP policies for the simplified models MCenter. ME and MRMDP. which correspond the naive nature policies Ocnners Ent, ORMDP in Section 3 Given an agent policy, we construct nature MDP in the POMDPs.3 jil framework, and solve it using the native Julia implementation of Monte Carlo tree search (MCTS) for continuous-state MDPs [8] For evaluation, run MCTS five times and report the lowest value; unnormalized values and standard deviation are in Appendix D.2
Metric. We test our evaluation pipeline on the abovementioned algorithms to compute the value V for each policy by solving the nature MDP. From these policy evaluations, compute relative V where V denotes the (approximate) value of the RPOMDP M
value gap: Veg = IV]
computed using RHSVI. A negative value gap indicates that our pipeline has determined a policy is suboptimal. In contrast, a positive value gap means our pipeline could not compute the worst-case value, i.e., due the error incurred from the approximation method used solve the nature MDP.
Benchmarks. We test our evaluation pipeline on three sets of benchmarks. Firstly, we use our novel benchmarks introduced in Section ToY* and ECHO, well the finite- and infinite chain environments PARITY (10) and PARITY Secondly, we lift several POMDPs from the literature into RPOMDPs: TIGER (6, MINIHALLWAY (33) and ALOHA (24, well
expanded variant of HELL 4 (also used in 45 We construct these RPOMDPs such that for any Tuu), any transition probability is less than 0.5 times higher lower than the nominal POMDP, with no alterations to the observation function. Lastly, we add partial observability to two benchmarks from the RMDP literature: HEALTHDETECTION [16] and REPLACEMENT [TO]. The former can be interpreted as an RPOMDP with little changes. For the latter, we add partial observability by adding measuring actions that reveal the state the cost of incurring negative reward (28) Appendix D.2
provides detailed descriptions of the environments and their dimensions.
6.2 Results & Analysis
We aggregate our results in two separate plots (Figure which we analyze below:
(11)
Our evaluation pipeline is accurate for smaller environments. For the smaller environments AMINH and above), our evaluation of RHSVI achieves a value gap close to zero, and the value gaps for all approximation methods are less than or equal to zero. Thus, for these environ- ments, our evaluation pipeline is likely accurate. However, for larger environments (ALOHA and HFALTHDETRCTIONN, some policies achieve positive value gaps. these cases, MCTS fails find an accurate solution for the nature MDP, leading to inaccurate policy evaluation.

---

Our novel benchmarks cannot be solved naively. For ToY", ECHO, and (OR) all the policies computed with naive nature heuristies have significant value gaps. Moreover, while RFIB yields an optimal policy for both variants of PARITY, it does not not solve Toy* or ECHO, despite their relatively small state spaces. In contrast, for all other benchmarks, at least one policy computed from a naive nature heuristic performs on par with the policy computed with RHSVI on the RPOMDP M.
(Q2)
(Q3) RFIB an adequate baseline. RFIB outperforms all naive nature heuristics for ToY*, ECIIO, and both variants of PARITY, on which it also is optimal. This confirms RFIB is useful as computationally inexpensive baseline for RPOMDPs. However, as we see for the other benchmarks, RFIB is not guaranteed to perform well on all benchmarks. In contrast to RFIB, RQMDP performs worse in general, but is still a valuable baseline for models where RFIB too expensive to compute.
7 Related Work
RPOMDP evaluation. No prior work exists that explicitly tackles the evaluation problem for RPOMDPs. However, methods that aim to solve RPOMDPs often make implicit assumptions about evaluation. Most notably, Galesloot et al. [15 proposes a pessimistic iterative planning framework that uses an evaluation method similar to the one used here. However, this work focuses on finding and evaluating finite state controllers for stationary nature policies only, while our evaluation method is more generic. More broadly, RPOMDP solvers exist that compute belief-based policies [45], history- based policies 22 4] or policies represented as finite state controllers ( [5 In all these works, the benchmarks consist of POMDPs with c-uncertainty around the original transition and observation functions, and include no discussion on why these benchmarks are picked. In particular, such variants of both TIGER and HELVEL have been used as RPOMDP benchmarks [22 41 45), while our work shows that both are naively solvable.
Related settings. Prior work has evaluated policies by sampling POMDPs from the uncertainty set [5), which, in contrast to evaluation method, does not guarantee finding the worst-case value. Furthermore, related settings include policy optimization and evaluation for finite sets of POMDPs, where model uncertainty static and not rectangular (14), value iteration with side information under distributional robustness [4)], and value iteration under varying pessimism levels (49) A Alternative settings include robustifying POMDP policies against observation perturbations 7 and robust active measuring (28 Lastly, we note that solver evaluation has been studied in different fields, including for MDPs 20 and reinforcement learning, both in general [44] [8] and for RMDPs in particular (60].
8 Conclusion & Discussion
In this paper, we consider three understudied components of the RPOMDP evaluation pipeline: (1) identifying suitable benchmarks, (2) robust policy evaluation, and (3) efficient baseline algorithms. We introduce novel methods to tackle all three problems, and empirically confirm that the resulting pipeline is sound. Future work could use our approximations to guide RPOMDP solvers, or introduce more specific approximations of the nature MDP increase scalability.
Limitations. As shown in section 6 approximation errors in solving the nature MDP may result in incorrect values. Thus, care should be taken in deciding which approximation method to use and assessing the resulting values. Furthermore, our methods and analysis in this paper are re- stricted to (s, a) a)-rectangular and convex uncertainty sets. Yet, these common assumptions for RPOMDPs 45 [5], and any non-rectan non-rectangular problem can be overapproximated (conservatively) by assuming rectangularity. We note that identifying less conservative cases of rectangularity while maintaining tractability is still an open problem in RMDPs [58 17].
Practical recommendations. For future research on RPOMDPs, we have two practical recommen- dations. Firstly, RPOMDP solvers should be tested on benchmarks that are not naively solvable, which can be tested theoretically (as done in Section 3) or empirically (as done in Section 6). Sec- ondly, RPOMDP solvers should be evaluated using a robust policy evaluation method that finds the worst-case value from a full range of possible nature policies, such as the one proposed in Section 4
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their useful comments. This work has been partially funded by the ERC Starting Grant DEUCE (101077178).
References
[1] Thom S. Badings, Alessandro Abate, Nils Jansen, David Parker, Hasan A. Poonawala, and Mariëlle Stoelinga. Sampling-basee robust control of autonomous systems with non-gaussian noise. In AAAI, pages 9669-9678. AAAI Press, 2022.
[2] Thom S. Badings, Licio Romao, Alessandro Abate, David Parker, Hasan A. Poonawala, Mariëlle Stoelinga, and Nils Jansen. Robust control for dynamical systems with non non-gaussian noise via formal abstractions. J. Artif. Intell. Res., 76:341-391, 2023.
[3] Eline M. Bovy, Marnix Suilen, Sebastian Junges, and Nils Jansen. Imprecise probabilities meet partial observability: Game semantics for robust POMDPs. In IJCAI, pages 6697-6706. ijcai.org, 2024.
[4] Darius Braziunas and Craig Boutilier. Stochastic local search for POMDP controllers, In AAAI, pages 690-696. AAAI Press The MIT Press, 2004.
[5] Brendan Burns and Oliver Brock. Sampling-baie based motion planning with sensing uncertainty. In ICRA, pages 3313-3318. IEEE, 2007.
[6] Anthony R. Cassandra, Leslie Pack Kaelbling, and Michael L. Littman. Acting optimally in partially observable stochastic domains. In AAAI, pages 1023-1028. AAAI Press / The MIT Press, 1994.
[7] Mahmoud El Chamie and Hala Mostafa. Robust action selection in partially observable Markov decision processes with model uncertainty. In CDC, pages 5586-5591. IEFE, 2018
[8] Adrien Couêtoux, Jean- MannBBapistt Hoock, Nataliya Sokolovska, Olivier Teytaud, and Nicolas Bonnard. Continuous upper confidence trees. In LION, volume 6683 of Lecture Notes in Computer Science, pages 433-445. Springer, 2011.
[9] Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, and Ufuk Topcu. Robust finite-state controllers for uncertain POMDPs. In AAAI, pages 1 11792-18800. AAAI Press, 2021.
[10] Erick Delage and Shie Mannor.
Percentile optimization for markov decision processes with parameter uncertainty. Oper: Res., 58(1)2003-2111 2010.
[11] Esther Derman, Daniel J. Mankowitz, Timothy A. Mann, and Shie Mannor. A bayesian approach to robust reinforcement learning. In UAI, volume 115 of Proceedings of Machine Learning Research, pages 648-658. AUAI Press, 2019.
[12] Maxim Egorov, Zachary N. Sunberg, Edward Balaban, Tim Allan Wheeler, Jayesh K. Gupta, and Mykel J. Kochenderfer. POMDPs.jl: A framework for sequential decision making under uncertainty. J. Mach. Learn. Res., 18:26:1-26:5, 2017.
[13] Paul L. Fackler and Robert G. Haight. Monitoring as partially observable decision problem. Resource and Energy Economics, 37:226-241, 2014.
[14] Maris F. L. Galesloot, Roman Andriushchenko, Milan Češka, Sebastian Junges, and Nils Jansen. Robust finite-memory policy gradients for hidden-mool POMDPs. In IJCAL, pages 1518-852.. ijcai.org, 2025.
[15] Maris L. Galesloot, Marnix Suilen, Thiago D. Simão, Steven Carr, Matthijs T. J. Spaan, Ufuk Topcu, and Nils Jansen. Pessimistic iterative planning with RNNs for robust POMDPs. In FCAI, volume 413 of Frontiers Artificial Intelligence and Applications, pages 4823-4831. IOS Press, 2025.
11

---

[16] Joel Goh, Mohsen Bayati, Stefanos A. Zenios, Sundeep Singh, and David Moore. Data uncertainty Markov chains: Application to cost-effectiveness analyses of medical innovations. Oper. Res., 66(3)):977715, 2018.
[17] Vineet Goyal and Julien larity. Math. Oper: Res., 48(1):203 226, 2023.
Robust markov decision processes. Beyond rectangu-
[18] Shangding Gu, Laixi Shi, Muning Wen, Ming Jin, Eric Mazumdar, Yuejie Chi, Adam Wier- man, and Costas J. Spanos. Robust gymnasium: A unified modular benchmark for robust reinforcement learning. In ICLR. OpenReview.net, 2025.
[19] Eric Hansen. Cost-effective sensing during plan execution. AAAI, pages 1029-1035. AAAI Press / The MIT Press, 1994.
[20] Arnd Hartmanns, Sebastian Junges, Tim Quatmann, and Maximilian Weininger. The revised practitioner's s guide to MDP model checking algorithms. International Journal on Software Tools for Technology Transfer, 2025.
[21] Milos Hauskrecht. Value-function approximations for partially observable markov decision processes, J. Artif. Intell. Res., 13:33-94, 2000.
[22] Hideaki Itoh and Kiyohiko Nakamura. Partially observable Markov decision processes with imprecise parameters. Artif. Intell.,
490, 2007.
[23] Garud N. Iyengar. Robust dynamic programming. Math. Oper. Res., 30(2):557-28) 2005.
[24] Wha Sook Jeon, Seung Beom Seo, and Dong Geun Jeong. POMDP- based contention resolution for framed ALOHA protocol machine-type communications. IEEE Internet Things J., ((15):33511-13223 2022.
[25] Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artif. Intell., 101(1-2):99-134 1998.
[26] Suresh Kalyanasundaram, Edwin K. Chong, and Ness Shroff. Markov decision processes with uncertain transition rates: sensitivity and robust control. In CDC, pages 3799-3804. IEEE,
2002.
[27] Merlijn Krale, Thiago D. Simão, and Nils Jansen. Act-then- measure:: Reinforcement learning for partially observable environments with active measuring. In ICAPS, pages 212-220. AAAI Press, 2023.
[28] Merlijn Krale, Thiago D. Simão, Jana Tumova, and Nils Jansen. Robust active measuring under model uncertainty. In AAAI, pages 21276-21284, AAAI Press, 2024.
[29] Merlijn Krale, Eline Bovy, Maris F. L. Galesloot, Thiago D. Simão, and Nils Jansen. Code for "On Evaluating Policies for Robust POMDPS", 2025. https:////// org/10...000 arg/10.5281/ zenodo. 17424409
[30] Merlijn Krale, Wietze Koops, Sebastian Junges, Thiago D. Simão, and Nils Jansen. Tighter falue-function approximations for pomdps. In AAMAS, pages 1200-1208. International Foun- dation for Autonomous Agents and Multiagent Systems ACM, 2025.
[31] Hanna Kurniawati, David Hsu, and Wee Sun Lee. SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Robotics: Science and Systems. The MIT Press, 2008
[32] Abolfazl Lavaei, Sadegh Soudjani, Emilio Frazzoli, and Majid Zamani. Constructing MDP abstractions using data with formal guarantees. IEEE Control. Syst. Lett., 7:460-465, 2023.
[33] Michael Littman, Anthony R. Cassandra, and Leslie P. Kaelbling. Learning policies for partially observable environments: Scaling up. In ICML, pages 362-370. Morgan Kaufmann, 1995.
[34] Michael I.. Littman, Thomas I.. Dean, and Leslie Pack Kaelbling. On the complexity of solving markov decision problems. In UAI, pages 392-402. Morgan Kaufmann, 1995.
12

---

[35] Omid Madani, Steve Hanks, and Anne Condon. On the undecidabilityy of probabilistic planning and related stochastic optimization problems. Artif. Intell., 147(1-2):5-34, 2003.
[36] Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft. Solving robust Markov decision processes: Generie, reliable, efficient. In AAAI, pages 26631-26641 AAAI Press, 2025.
[37] Janosch Moos, Kay Hansel, Hany Abdulsamad, Svenja Stark, Debora Clever, and Jan Peters. Robust reinforcement learning: A review of foundations and recent advances. Mach. Learn. Knowl. Extr, (11):276-315,, 2022.
[38] Pablo G. Morato, Konstantinos G. Papakonstantinou. Charalampos P. Andriotis, Jannie Søn- derkær Nielsen, and Philippe Rigo. Optimal inspection and maintenance planning for deteriorat- ing structural components through dynamic Bayesian networks and Markov decision processes. Structural Safery, 94:102140, 2022.
[39] Pablo G. Morato, Konstantinos G. Papakonstantinou, Charalampos P. Andriotis, and Philippe Rigo. Managing offshore wind turbines through Markov decision processes and dynamic Bayesian networks. In 13th International Conference on Structural Safety & Reliaaility (ICOS- SAR). 2022.
[40] Hideaki Nakao, Ruiwei Jiang, and Siqian Shen. Distributionally robust partially observable Markov decision process with moment-based ambiguity. SIAM J. Optim., 31(1):461-488, 2021.
[41] Yaodong Ni and Zhi-Qiang Liu. Bounded-parameter processes. In ICAPS, pages 240-247. AAAI Press, 2008
parameter partially observable Markov decision
[42] Yaodong Ni and Zhi- Shi-Qiang Liu. Bounded-paranne partially observable Markov decision processes: Framework and algorithm. Int. J. Uncertain. Fuzziness Knowl, Based Syst., 21(6): 821-864, 2013.
[43] Arna Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Oper. Res., 53(5):780-798, 2005.
[44] Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In ICLR. OpenReview.net, 2020.
[45] Takayuki Osogami.
Robust partially observable markov decision process. ICML, volume 37
of JMLR Workshop and Conference Proceedings, pages 106-115. JMLR.org, 2015.
[46] Hans Peters. Game theory: A Multi-leveled approach. Springer, 2015.
[47] Joelle Pineau, Geoffrey J. Gordon, and Sebastian Thrun. Point-based value iteration: An anytime algorithm for POMDPs. In IJCAI, pages
Morgan Kaufmann, 2003.
[48] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994.
[49] Soroush Saghafian. Ambiguous partially observable Markov decision processes: Structural results and applications. J. Econ. Theory, 178:1-35, 2018.
[50] Richard Smallwood and Edward J. Sondik. The optimal control of partially observable
Markov processes over finite horizon. Oper. Res., 21 1973.
[51] Trey Smith and Reid G. Simmons. Heuristic search value iteration for POMDPs. In UAI, pages 520-527. AUAI Press, 2004.
[52] Trey Smith and Reid G. Simmons. Point-based POMDP algorithms: Improved analysis and implementation. In UAI, pages 542-547, 2005.
[53] Marnix Suilen, Nils Jansen, Murat Cubuktepe, and Ufuk Topeu. Robust policy synthesis for uncertain POMDPs via convex optimization. In IJCAI, pages 4113-4120. ijcai.org, 2020.
13

---

[54] Marnix Suilen, Thiago D. Simão, David Parker, and Nils Jansen. Robust anytime learning of Markov decision processes. NeurlPS, 2022.
[55] Marnix Suilen, Thom S. Badings, Eline M. Bovy, David Parker, and Nils Jansen. Robust Markov decision processes: A place where AI and formal methods meet. In Principles of Verification (3), volume 15262 of Lecture Notes in Computer Science, pages 126-154. Springer, 2024.
[56] Ole Tange. GNU parallel 20241222 ("bashar") [stable], December 2024. URL https/tss://do org/ 10. 5281/zenodo. 14550073
[57] Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic robotics. Intelligent robotics and autonomous agents, MIT Press, 2005.
[58] Wolfram Wiesemann, Daniel Kuhn, and Berş Rustem. Robust Markov decision processes. Math. Oper. Res., 38(1):153-183, 2013.
[59] Nan Ye, Adhiraj Somani, David Hsu, and Wee Sun Lee. DESPOT: online POMDP planning with regularization. J. Artif. Intell. Res., 58:231-22222 2017.
[60] Adil Zouitine, David Bertoin, Pierre Clavier, Matthieu Geist, and Emmanuel Rachelson. RRLS: robust reinforcement learning suite. CoRR, abs/2406.08466, 2024.
14

---

A Solvability Classes and Benchmark Models
This section contains all proofs related to Section 3 of the main paper.
A.1 Solvability proofs
First, we show the correctness of the policies used in section Section 3 to explain the solvability classes. We restate the RPOMDP used in Section 3.1
0.5
100
$5
0.5
Solvability
P
P
V2
0.5
80
86
R T2
Trivially
0.2
0.6
80
Center
0.1
0.6
80
1
100
Entropy
0.1
0.6
80
82
P
87
RMDP
0.1
0.6
80
Stationary
0.1
0.9
80
P
R
None of the above
0.1
0.9
70
E [p.pl
200
Figure 5: Example RPOMDP with parameter values for solvability classes. We Toy* denote the model with the parameter values from the bottom line.
Let 0:00 000, 0:00 000, 1:000 = CoOa@, and 1,000 = CoDa denote the histories for which the agent nature need to make non-singleton choices. Given agent and nature policies and 0 the value function of the RPOMDP in fig. can be expressed by the following function:
V
0.5 0.5 - (a) (hh 000 (a) 100
+ 0.5 - (b) rr
+ 0.5- (1 (b)
+ +05-005-7(11)() 0(h 00 a)(p) (Th00))a) 100
+.5-- (35-05--((1))1)
A(h .)(p)) T 000 (b) 200
+ +05 (b)
0.5 7(1 (a) -0h00
01 ap) ক 7(h 000 (a) 100
0.5 T(119) (1 0(h 00 a)) 7 (h 000 (6) 200
We simplify and rewrite this function to remove the b terms:
25 25. T(h (a)
+.5 (1-
+ 2 x(1 (() (p) o00)))
+ 50 <(1 (a) (1-00))))())))))))) a)()) (1 (1000)
+ 0.5 (1- (1-r(1)))a))
+ 50 x(109)a) (a) 0(h a0))))))))))) 7(1 (a)
+ 100 (T10)( (1 0(1 (p)) (1 - > (a100)
15

---

We now further simplify the notation with a =(ho0) (a), (a),))
T (h)00) a00 = Thh (a) and pe = 0(100,,000 ap))), p0 = 0(h00 (p). (p).
25a a 00
+ 0.5r:(1 aa)
+ 25a paa s0
+ 50a (1 - p)) (1 - d )
+ 0.5rz (1 - )
+ 50a paa 00
+ 100a (1 - p1((1 )00)
25a a
+ 0.5r:
0.5rza
+ 25a 25a'1' pa
+ 50a 0 50a p
a0 + 5000pp0
+ 0.5r;
0.
+ 50a 50app"a pa 00
+ 100a 100a p
10 00
1000 pp
ry (50 0.5r )a 50a
25a + +75a p 7 00
(100 0.5ry)a 100a
100a 00 150a p000
Recall the optimal value for the agent Va max mingge V=.0 and nature V = mingee max V=,0 with corresponding optimal agent and nature policies म* and 0r, If Vf y then the underlying game has Nash equilibrium [46] in which case n² and 8* are called Nash policies. We can therefore show that an agent policy is optimal if it can guarantee the same value as a nature policy can guarantee, and vice versa. Using this logic, we consider the following two agent policies.
First, the safe policy n always picks the safe action & in the O states, so regardless of the previous observation, which yields guaranteed value of rz. The action in the states does matter after the safe action b.
v0 θ V
r7 + (50 0.5ry) 0 50 0. 20 25
0 a + 75-0 a + (100 0.5m)) 0 1- 10
0.pº -0000 0 a + 150 0 p00000
= r? + 0 - 0 --
Next, the risky policy म; picks the riskier action in these O states if it's previous observation and the safe action otherwise. Furthermore, n, picks action in the states. The value that n. can guarantee depends the bounds p.
V0 E θ V=
+ (50- 0.5ry) 0 - 50 0 p 25 0 000 + 75 0 paa
+ (100- 0.5ry) 1 - - 1.pp - 1000 1 0. 150 1 1 0
= r? + 0 - 0- 0 + 0 100 - 0.5r. 100p - 0+0
= 0.5r, + 100 - 100p
Similarly, we can look at the value certain nature policies can guarantee. We find that nature can ensure a value of at most r? when choosing nd and pd within certain intervals.
VT E IT: V=.0 + (50 0.5ry )a p 25a a 00 + 75a pa
+ (100- 0.5rg )a 100a p 100a + 150g p paa
a a 00 and pd are independent of a,, 00 and p², so VT E 11: V < rr iff:
VT E II: (50- 0.5ry)a - 50a 25a + 75a 75a 0 < 0
16

---

and
VT E II: (100 - 0.5rg)a ) 100a 100a a a. + 150a p 00 0
Given arbitrary a _ E [0, 1]. we first compute the interval for p²:
(50 0.5rz) )a 50a 50 25a a + 75a p000 <
a (50 0.5r? 50p 25a + 75p a 00)) < 0
a E [0, 1], so the inequality above holds for all π E iff:
50 0.5r. 50p
25a 75p 00 00
50 0.5r 50p 0 < 25a
75p 75ppa 00
50 0.5r; 50p S 00 (25 75pº)
000 E [0, 1], so the inequality above holds for all E IT iff:
50 0.5r; 50p² 1 0
A
50 0.5r. 50pp < 25 75p
50 - 0.5r v 50p
A
25pº < 0.5r? - 25
0.01r? p
A
pe S 0.02r? -
So we get our first interval pd [1 0.01r;, 0.02r? continue with the interval for p
1]. Given arbitrary a0
10, 1), we
00 + 150a p 00 < (100 0.5ry)a 100a p 100a a
a (100- - 0.5ry - 100p - 100a + 150p o
S
a [0, 1], so the inequality above holds for all II iff:
100 0.5r 100p
100a 00
150p 0 < 0
100 0.5r. 100p < 100a se
150p a
100 - 0.5r, - 100p < a 1000 150p
00 E [0, 1]. so the inequality above holds for all ı E II iff:
100 0.5r. 100p
<
0
A
100 0.5r 100p S 100 150p
100 0.5ry < 100p
A
50p < 0.5r?
0.005r p
A
p 0.01
So we get our second interval yd E [1 - 0.005r,, 0.01rz). We can conclude that VT II: V=.8 S ?? > 1e E [1 0.01r;, 0.02r; 1) A nd E [1 - 0.005r?, 0.01rz). We consider two values for T? in our example, i. c., 70 and 80, so we get the following intervals for pd and po:
r: 70 p E [0.3, 0.3.0.4), p0 E [0.65,0.7
r? 80 p E [0.2.066, E 00.6, 0.8]
A.1.1 Trivially solvable
Since the trivially solvable model in fig. 5 has ry = 80 and bounds E |0.2. we know that nature can guarantee value of 80 by playing p do 0.6. We therefore know that any agent policy that can guarentee a value of 80 is optimal as well. In particular, we know that n; is optimal, since:
V0 θ V
0.5r; + 100 100p
0.5 80 + 100 100p
140 100p
2 140 100 0.6
80
17

---

To show that this model is trivially solvable, we show that x is optimal for any 0 E θ In other words, for all nature policies in the set of nature policies, there is no agent policy x' that achieves higher reward than n, against that particular nature policies.
Given arbitrary 0 E O we construct the optimal agent policy x' by maximizing over the value function:
T argmax V REll
argmax xell
17 + (50 - 0.5ry)a² - 50a 25a a + 75a pa
+ (100 0.5ry) )a 100a
100a
+ 150g p a
argmax =c
80 + (50 0.5 80)a
50a
p 25a
+ 75a 00
+ (100 0.5 80)a
100a
p 100a
150a p 00
argmax xell
80 + 10a 50a p
25a
+ 75a p 00
+ 60a
100a p
100a a
150g o p a
argmax
10aa 50a
25a e
a
00 + 75a p
xEll
+ 60a 100a 100a 0 + 150g 1o
00, and pd are independent of a, 00 and y., we can compute two parts of the agent policy seprately:
argmax 0000
10aa - 50a p 25a o 00 + 75a 7 20
argmax 600 100a p 100a 00 150a p0000 00000
We begin with a and a 00:
argmax 000
110a 50a 25a a 00 + 75a 75a p -00)
arggmax 000
a (a0 50p a25 752²))
As we are maximizing, we know that a should be if 50p 00 (25 and we can set it to 0 otherwise. We show 10- 50p 00 (25 75p I 0 regardless of 00
10 50p a (25- (25
75p < 0
10 50p
< a 0 7
00 E [0, 1]. so the inequality above holds for all a iff:
10 50p% < 0
A
10 50p
< 25 75p
10 < 50p
25p 0 < 15
0.2 < p
pd 0.6
Since VO E O:: p E [0.22, 0.6), we have that choosing a is optimal. We continue with a and a so:
argmax 60a 100a p 100a a 150a 20000
argmax (a9(60- 100p a000 150p 000000
As are maximizing, we know that a should be 1 if 60 100p a a000 150pb) > 0 and can set it to 0 otherwise. We know 60 - 100p 2 0 regardless of p
60 100p 0 2 60 100 0.6
0
18

---

Since can set a000 to O, we already know that 60 100p to 1. Finally, we determine the optimal ao
a00 150p²) 2 0, so set a
a 00 (100 150p")
ス a 00 (100
150 (
= a 00.00
0
Since we subtract with (100 - 150p²) 2 0, it is optimal to set a to 0.
The agent policy that constructed x' with a 0, a 1, and a 0 is optimal against all
0 E θ, and this policy is exactly गēद Since the agent policy we compute against any nature policy 0 E θ optimal against the entire of nature polcies θ, we conclude that our trivially solvable model in fig. 5is is indeed trivially solvable.
A.1.2 Naively solvable
Like in the trivially solvable model in fig. nature can guarantee value of 80 in the center, entropy, and RMDP solvable models in fig. 5 by playing pd p = 0.6. We therefore also know π is again optimal, since it can guarantee value of 80.
The naive nature policies in the center, entropy, and RMDP solvable models are:
Beener assigns pd = pº = 0.35, as Centroid (p) = 0.35.
Bgat assigns pe = p 0.5, this creates the maximum entropy between states $7 and ss-
namely {s7 + 0.5, S8 + 0.5}.
ORMDP assigns pd = yo = 0.6, as in the fully observable model, always optimal for nature to minimize the chance of reaching state 8s, and therefore to maximize p.
All three of these naive nature policies are contained in the set of policies of the trivially solvable model, for which we have shown that गद. is optimal.
Since the agent policies we compute against Centerr, OFne, and ORMDP are optimal against the entire set of nature polcies e, we conclude that our center, entropy and RMDP solvable models in fig. are indeed center, entropy, and RMDP solvable.
We also note that the center, entropy, and RMDP solvable models in fig. 5 are not trivially solvable.
For example, n, is not optimal against the nature policy 0' with y/ p 0.1. We again construct the optimal agent policy n' by maximizing over the value function:
n' argmax V #Ell
argmax *E
80 + 10a 50a
0.1
25a 00 + 75a 0.1 800
60a
100a
0.1 100a a 00 150a 0.1 - -00)
argmax *Ill
80 + 10a
5a
25a a 00
7.5a a 00
+ 60a e - 10a 9 100a 2 a 00
+ 15a 0o
argmax
80 + 5a 17.5a a + 50a 85a a
=EII
Since are maximizing, it is optimal set a and a and 00 and 00 to 0. This n' results in
value / 0' 80 + 5 + 50- 135, whereas प.P. results in value v -80 + 50 130.
Since the optimal agent policy n' for nature policy E e not optimal against the entire set of nature policies θ, the center, entropy, and RMDP solvable models in fig, 5 are not trivially solvable.
A.1.3 Stationary solvable
Since the stationary solvable model fig. 5 has r: 80 and bounds p [0.1, 0.9), we know that nature can guarantee a value of 80 by playing any policy with y [0.2, 0.6] and pd E [0.6, 0.8). We therefore know that any agent policy that can guarentee a value of 80 optimal as well. In particular, we know that nT is optimal, since this policy always results in value of r? 80.
19

---

To show that this model is stationary solvable, we show that π is also optimal against the set of stationary nature policies @Sta, Since = guarantees value of 80, this agent policy is optimal there is stationary nature policy that can also guarentee value of 80. We know that the stationary nature policy p = pe 0.6 guarantees value of 80, so we can conclude that the stationary solvable model in fig. is indeed stationary solvable.
We also that the stationary solvable model in fig. is not trivially naively solvable, as the optimal agent policies against the nature policies Oemmer, Untt and ORMDP cannot guarantee value of 80 against the entire set of nature policies.
The naive policies in the stationary solvable models are:
OCener assigns p/ = -pº = 0.5, Centroid (p) 0.5.
Orn assigns pº = p0 0.5, as this creates the maximum entropy between states 87 and 8g.
namely {87 + 0.5, + 0.5).
BRMDP assigns pº yd 0.9, in the fully observable model, always optimal for nature to minimize the chance of reaching state sg, and therefore maximize p.
As shown in appendix A.I.2 we know that गद optimal against Ocenter and O However, म, not optimal against the entire set of nature policies, as nature can achieve a value < 80 when playing nature policy 6' with pa > 0.6:
V 0.5 r? + 100 100p
0.5 80 100 100p
140 100p
< 140 100 0.6
140 60
80
Next, we show the stationary solvable model is not RMDP solvable by constructing the optimal agent policy n' against ORMDP and showing that this agent policy cannot guarantee value of 80 against the entire set of nature policies O.
argmax 77,0RMOP *Ell
argmax *Ell
80 + 10a 50a
0.9
25a 00 + 75a 00. 00
60a
100a
0.9
100a a 00
150a 0.9 a 00)
argmax #Ell
80 + 10a
45a
25a a
00
67.5a
+ 60a e 90g
100a a + 135a a 00
argmax .ell
80 - 35a + 42.5a
+ -30 + 35a 00
Since we are maximizing, it optimal to set a a²,a², 20 000 and 00 all to This n' results in value ya Swar 80 35 + 42.5 30 +33 = 92.55 whereas n results value V* Owar 80. However, n' is not optimal against the entire set of nature policies θ, nature can achieve value of < 80
20

---

when playing nature policy 8' with pº + 2p < 1.8:
V 0' 80 + 10a 50a p 25a 00 75a p 0
+ 60a 100a
100a
150a 1500 0
80 + 10 50
1. p- 25 1 1 75 p
+0 100 1 p pp
10001-1-1 150 1. 1.
80 10 50p
25 75p + 60 - 100p 100 150p
=3 + 25p 50p
35 + 25(p + 2p')
< 35 + 25-
35 + 45
= 80
Since the stationary solvable model in fig. 5 is not center, entropy, or RMDP solvable, we can conclude it not trivially or naively solvable.
A.1.4 Not stationary solvable
Finally, we show that when we change r? to and keep the bounds on p E [0.1, the same for the stationary solvable model in fig. 5 we end up with model (the None the above model in fig. 5 that is neither stationary, nor naively, nor trivially solvable. We know that nature can guarantee value of r: 70 by playing pd E [0.3, 0.4] and yd [0.65, 0.7]. We therefore know that any agent policy that can guarantee a value of 70 is optimal as well. In particular, we know that q is optimal, since this policy always results in value of r? 70.
We again identify the three naive nature policies:
OCentr assigns pd = =p = 0.5, as Centroid (p) = 0.5.
Otm assigns p = 10 -0.5, this creates the maximum entropy between states 87 and 88.
namely {87 + 0.5, 88 + 0.5).
ORMDP assigns pd p0 0.9, in the fully observable model, it always optimal for
nature to minimize the chance of reaching state sg, and therefore to maximize p.
We first construct the optimal agent policy x' against the center and entropy nature policies, which are the same:
n argmax F.ccae
REIl
argmaxx
r7 + (50 - 0.5ry)a
50a p
25a 00 + 75a y a
+ (100 - 0.5ry)
100a
pp
100a 00 + 150g p 00
= argmaxx =ell
70 + (50 - 0.5 a
50a
0.5 25a a
00
75a 0.5 00
+ (100- 0.5 70)a
100a 0.5 100a
+ 150a 0.5 a
argmax *EIl
70 + 15a 25a
25a a
+ 17.5aa 00
+ 65a 50a
100 a
+ 75a 00
argmax Fell
70 10a + 12.5a 15a
25a
Since we are maximizing, it is optimal to set a and 00 to 1 and 00 to This n' results in value Va &eame 70 10 + 12.5 +
87.5, whereas x results in value V* Seaee 70. However, n' is not optimal against the entire set of nature policies θ nature can achieve value of < 70
21

---

when playing nature policy 0' with 4p -pp > 2.2:
V 70 + 15a 50d²p" a 75a 75a paa 00
+ 65a 100app
100a 0 150a po0lapppcc 0
70 15 1 - 50
1 pd 25 1..11.1+4 75 1 pp
+ 65 1 100 1 p- -
=70 + 15 - 50y
25 + 75p + 65 - 100p - 0+0
-125 + 25p - 100p
-255- -5p4pp pd)
125 2.2
125 55
70
The optimal agent policy n' against the center and entropy policies cannot guarantee value of 70 against the entire set of nature policies O, hence we can conclude that is not an optimal agent policy in the None of the above model in fig- and that this model is not center or entropy solvable, nor trivially solvable.
We continue with the RMDP nature policy ORMDP. We again construct the optimal agent policy T':
n' = argmax V..0mm
#EIl
argmax =Ell
r? + (50- - 0.5r:)a 50a 5
25a a + 75a pa
+ (100 0.5r;)a 100a
100a
0
150g p0aa
argmax =Ell
70 + (50 0.5 70) 50a
0.9 25a
75a 00. 0
+ (100 0.5 70)a
100
0.9
100a 00 150a 0.9 00
argmax =Ell
70 + 15a
45a
25a a
00
+ 35. 0
+ 65a 90n
100a a 00 + 135a 2
a 00
argmax =en
70 -0a + 42.5a
25a o + 35a 2 a
Since we are maximizing, it is optimal to set a a a and 00 all to 1. This T' results in value
V=',bcme Soooe = 70- - 30 + 42.5 25 + 35 = 92.55, whereas o results in value V= Acoee = 70. However, T' is not optimal against the entire set of nature policies O as nature can achieve value of < 70
when playing nature policy 0' with pd + 2p < 1.8:
vx 8
70 + 15a 50a²p"
25a 00 75 p p0a
+ 65a
100a
100a a 00 150a 00
70 + 15 50
1 pd 25 1 1+ 75 1 Do.
+65 1 100 1 p. 100 1- 150 1.pp..p111
70 + 15 - 50p
25 75p + 65 - 100p 100 150p
25 + 25p 50p
25 + 25(p 2pº)
+ 25-1.8
25 + 45
= 70
The optimal agent policy x' against the RMDP nature policies cannot guarantee a value of 70 against the entire set of nature policies θ hence we can conclude that x' is not an optimal agent policy the None of the above model in fig, and that this model is RMDP solvable.
22

---

Finally, we show the None of the above model in fig. i is not stationary solvable. We therefore construct an agent policy x that guarantees value of 75 against the set of stationary nature policies. which is better than the value xı achieves, therefore we can conclude that T is not optimal against the set of stationary nature policies.
Let n/ assign 1 to a. aaa and a and assign 0.5 to a a We get the following value:
v0 E Osu VT .0 rr (50 0.5r;)a 50a p 25a
75a 7 paaa 00
+ (100 0.5ry)a 100a. pd 100a 000 150a p0a00 00
70 + (50 0.5 70)- 1 50 1- pº 25 1. + 75 1 pp.
+ (100 0.5 70) 1 100 1. p- 100 1- 0.5 + 150 1 1.p...pp... 0.5
70 + 15 - 50y 25 + 75 pd
+ 65 - 100 pd - 50 + 75p
75 + 25p - 25p
75
Where the last step follows from the restriction stationary nature policies. n' hence guarantees higher value than T. against the set of stationary nature policies, so T is not optimal against the set of stationary nature policies.
Next we show that o is the only agent policy that can guarantee a value of 70 against the entire set of nature policies. Let n" be agent policy with a² a (0,1), 1], then we get:
44 E θ
V 0
ry + (50 Ja - 50a 25a a + 750 p0 a 00
+ (100- 0.5r,) - p 0 - 100a a
+ 150g p p
= 70 + (50 - 0.5 - 70)a 0 - 50app 25a a 00 + 75a p 0
+ (100 0.5 70)a _ 100a pe 100a a
+ 150g Pelopppee 0
70 + 15a - 50 25a a 00 + 75a p a
+ 65a 0 - 100a00 - 100a o a 00 + 150a p
= 70 + (15 - 50p
25a 00 + 75p a
a (65 100p
100g 150p 60)
Since a², a > O, the agent can only guarantee a of 70 if at least vO E A:
15 50p% 25a 00 + 75p a 00
00 65- 100p 100a + 150p a 2 0
However, when pd E (0.3, 0.4) and po E (0.65, this requitement does not hold, for example when pd 0.35 and pa z:
15- - 50p 25a 00 + 75p 00 = 15 - 50 0.35
25a 00
+ 75 0.35 00
= 15 17.5 - -25a 00
26.25
a 00
-2.5 + 1.25a 00
0
Where the last step follows from 00 E
[0, 1]. And similarly:
2
2
65- 100p e_ 100a 00
150pp 0 00 = 65 100
100a 00 + 150
00
3
3
2
65 - 66
1000
+ 100 0
2
-1
3
< 0
Hence, an agent policy can only guarantee a value of 70 by playing a", -aa=
Since T. cannot be found by considering the subset of stationary nature policies, while it is the only optimal policy against the entire set of nature policies, we can conclude that the None of the above model in fig. is not stationary solvable.
23

---

A.2 Benchmarks
Next, we provide proofs for the theorems related to our proposed benchmarks.
A.2.1
Echo machine
Let us first restate the theorem in the main text:
Theorem 1. ECHO, with 0.01, p 0.99. 5 = 0.1 and 0.95, is not in any of the solvability classes defined Section 3.7
To prove the theorem in the main text, we first prove two helping lemmas:
Lemma 2. 0.5 P, then the optimal adversarial stationary policy 0's picks p 0.5.
Proof. Let delayed denote the set of nature policies that is not stationary, but for which the choice of p only applies with a delay of timestep. which means each 9 E delayed must pick for step t based history h4-1 (..., a1-2, 01) and previous state $1-t- We show that the Nash-optimal policy in this class always picks 0.5, which means it is stationary. Moreover, since delyyed contains all stationary policies, this proves this policy is also the Nash-optimal stationary policy.
To do so, we first notice that the choice of any policy E dctayed only has an impact histories where the agent is in state x' but the agent has some belief over and x', similarly with y and y. Let he be such a history, and assume 5t = x'. In that case, denote 0(he, x) = p. haefa.y) = (he, a, L) and has (z.e) ie (o..) (h,, a, 1. g. o.). Furthermore, let V (h, s) denote the value of policy æ against given history h and state 8. In that case, the agent has the following value function for history ha
V (h(h,22))
= ग (x: (()x(r)
ha) (v V ((h2, (,),,,,1),n, + V ((hg, 1),
2
+ ( (t) hy) V ((igg 1), V ((hy, 1), x.y)
+ л(x he)m(g ha)
PV (hzzz D) (h 2/)
+ tly he)a(g hy) (hy,a, + V" (hy.r v')
We simplify this formula in three ways. Firstly, we collect all values that do not directly depend on the choice of p (i.e., the top two lines) into a constant C" Secondly, using symmetry of the model, we define V (hr,,,, x²) V (hy.v. 3/) == Vsame and V(hz.g. y') V(h (hyy,,, x²) (ar==="=))))))))) := Vair- Lastly, we denote denote (α he) = nr. and since no new information is contained in h. hy we may assume
(g h2) = [gg hy) = Tg. Then, our formula simplifies as follows:
V" (he,,z²) C + kg Th (pVamme + -1-27 Vair)) + (1 - Th) T=) p) Vame + +Vamt
We compute the partial derivatives of this function (with constant factor Ti remove for readability) as:
@v (he;z")))
= pV Vame + (1 pp) Vain - (1 - p) Vaane pVain
(1 2p) Vsame)
0v* (he,z')
Te Vsame Th Vaift (1 Tex )
Vsame)
Op
= = - 1 20 (Vain Vsame)
We find that there exists a saddle point at म.. = p = 0.5. Thus, for any history h, leading to x', we find that leyn (h,, .τ) 0.5, and the same holds for y' via symmetry of the model. Lastly, we note that the choice of p is only relevant in these two states, which means the choice of p 0.5 (or any other arbitrary choice) is optimal for other states. Thus, always picking p = 0.5 Nash-optimal for policy class e aclayod, which proves our lemma.
D
24

---

Lemma 3.
For any history he let Tax a E A denote the highest at which the agent has picked action Then, the following history-basee based nature policy is optimal:
[sup(P) Tx > Ty inn((P)
6 (he, 8)
(4)
otherwise.
Corollary 2. Let by denote some history such that the 8, E (x, v/). Then, the optimal agent policy is follows:
(he) -far x {0 otherwise
x #1--su(P)) inf(P)
Proof. The choice of 9 only matters if n', in which case either Ts = =t- or Ty = t 1. We can denote the two value function for these cases as follows:
~ (hz, n²) = a(r lg) + +y ha) pV (M x') + (1 (1-p)) p) (hz.ys 0')
V (T = )(r 1ly) + +r( heg) PVV (hy,as +') (1- (hya.r)3))
Since x' and y' have the same successor states and immediate rewards, the difference between V* (Ma,,, .²) and V* V* (hz.g. y/) depends only on the history. We see that history hz,y (and hy.z) give the agent strictly more information than ha (and h) for the former we know we are in x' (and y') ) while for the latter we could be either x or x' (and y or yy) with non-zero probability. Since more information can only allow the agent to pick better actions, we conclude ("(ha,, x²) S V* (haay. v') (and V (hy., y') S V* (lyya x') x')), and thus that the value is minimized for p = 1 sup(() for history h2 (and for p iP) for history hy). The corollary holds via the same argument.
O
Next, we show that the optimal policy is suboptimal against all stationary policies. More precisely, we give conditions for which, against the worst-case nature policy, it is only optimal to repair if the agent has detected that the machine is broken, i... if takes action dg but observes y two timesteps later, or similarly for Sy and In contrast, we give a similar condition such that, for the worst-case non-stationn non-stationary policy, repair is optimal without detecting that the machine is broken. We formalize this logic follows:
Theorem 5. In the maintenance benchmark, let be any stationary nature policy, and hy be any history such that the agent has some some non-zero probubility optimal policy against 0 chooses action π π(h; (1)) = as long as:
be in state n'. Then, the
(1 (1-8)
1 - 22 72 + 78- 8)
0.572
0.5g 11
1 0.
(5)
1- 0.5y²
Proof. Via our lemma above, we may assume = 0.5, in which case our problem is a standard talk about beliefs. (Note that if p & P, then the agent can always get strictly more information, and thus has less incentive to repair without seeing a malfunction.) We first note that if the agent has detected the machine is broken since it's last repair, then no history exists such that the probability of being in state n lies between O and 1. In that case, we may denote the two most "extreme" beliefs possible as follows. bt denotes any belief such that b(n.) b(n.)) 1 (due to symmetry, these states are interchangeable for both nature and the agent), and bj denotes the belief such that b(n') is maximized. In particular, let n denote the number of number of times the agent has observed x or since the last repair action, or the beginning of the episode if no repair action has yet occured. Then, we calculate the probability of being in state n' as follows:
POMDP for which
0.56
by bl(n') Σ
0.5"
6,
(6)
0.5
We remark that if repairing is optimal for any belief hr, then it must be optimal in bj. Thus, we consider the values for both actions g and in b1:
Q(bi,9)= = Q2 = (1 5) 5) 7 T0.50,
0.5Q,]
1- 0.5y²
Q(b,r)) Q. = -11 ((bT)())
25

---

To determine when measuring is optimal, we may look at the difference between these two values. In particular, action g optimal as long as the following holds:
(1 (1-6) 6)
0.5
Qg - Qr 1 1 0.5y²
+ Qr
1 20
(7)
- 0.5y
(8)
We note that 0,5g²
upper bound for Qr to find overapproxi- mation of when measuring optimal. For this, use the expected value given the fully observable setting, which we denote as VRMDP- We note that our theorem is trivially true repairing is not worth
for all y. Thus,
1-0.5,2
in the fully observable case, thus we may assume that VRMDP(n') >VRMDPP( 1. Then, get:
(1²) VRMDP (n2y) 72 (VVMDDP(1') + +(1 -8) (RMDD((Z))
72 (5(7VRMDr(m 1) (1 -5) 5)VRDDD(M*))
725 + (RVMDD()( 87 - 5)
--0
= 1 - +1++700 -
2 Qt
Filling this in for Qr, we find that:
(1 (1-6)
- 72
0.5g2
Q- - 1- 1-0.5
1 22 + 78 8)
0.577
Action g only optimal as long as this value is 2 O, which gives us our bound.
Theorem 6. In the maintenance benchmark. let 0 be the optimal history-based nature policy, and define ;= 1 min ( (inf(P), 1 sup(P)) Then, there exists history hi such that the agent has non-zero, but < 1, probability of being in state n' but T(h2 = as long as:
1 (1 (1- 1)?
(1-6)
97 20
1- 1-7(1 - 8)
1- 1-
Proof. Without loss of generality, assume 1 - sup(P) > inf(P), in which case lemma and it's corollarary state x² always picks action x and 8" chooses p = sup(P) == (The proof for 1- sup(P) & (P) follows via symmetry of the model.) In that case, following the same logic used the proof of 5 we define the belief with the highest probability to be in state n' as
qō
(1(n') = Σ 1-9
We define Q, and Qr before, which yields the following condition:
Q- Qg Qr a.1 (1 1-
9)?2
(1 - 2 0
97
Since Vg.7 E 1);
(1-g)? < 1. we can use a lower bound on Q, to find a sufficient condition. 1-
One such lower bound is given by taking an agent policy that never measures, which case
Q 2 Σ (-(1- 5))2m 1- 1-7(1- - 8)*
n=
which yields the condition given in the theorem.
Lastly, the proof theorem follows from the fact that the parameters satisfy the conditions of both theorem and thcorem [
26

---

A.2.2 Parity
We start by restating our theorem for convenience.
Theorem 2. PARITY(OO), with P1 = {0.2), P2 = [0.1,0.]] P3 = -0.1,0077 and y 2 0.73, is not naively solvable.
Proof. We assume that the agent always picks an action according to its current most likely parity, which is clearly optimal. Thus, we can summarize the agent's uncertainty as the using the even-odd ratio e max (naxve(eeen)) Pr(odd)). Since the agent never receives any information in PARITY, follows that any optimal policy must be cyclic. More precisely, let T. denote policy that repeatedly takes n s-actions, then normal action which resets to Then, any optimal policy must be representable as nn. for some E N.
We show that the value of To higher than that of any other nn. First, the value of To is given as:
v
Σ
(10)
If can find any choice of probabilitiess for which any policy nnzo has lower value, then done. We start with Tı, for which we pick pt = 0.2, P2 = 0.5 and pa = 0.3. In that case:
v < (1i(1 + 7) p2 27) + p3( + 7)
Σ
2n
a=0
(1I)
2.1 0.57
7
11 = 0.73. For larger values of we assume that the This value is smaller than that of for > 15 adversary starts off with the choice above, then picks p1 0.1, = 0.1, pls 0.7 as long at the agent keeps taking stochastic actions. We claim that under the second set of dynamics, e converges to the value of 10 19 = 0.526. To prove this, we invoke Banach's 's fixed point theorem 48). Denote e' as
the even-odd ratio after a single step under the dynamics above, then = 0.9e + 1. Using the T distance, find the following:
10
10
10
10
le'
0.9e + 1 = 0.9/e
S ee-
(12)
19
19
19
19
Thus, using Banachs theorem, e converges to 19.
In particular, this means that the maximum e that
will be reached is given as Gmax = 0.5 + |0.5 - 11 11 ~ 0.579. Next, we note that the expected immediate return for the stochastic actions can be given as follows:
19
E[rle] 2.1e 2(1 e) 4.1e-4 2.
(13)
For our maximum value of e, this yields an immediate return of 71 RV 0.37. Thus, for any n > 1, we write the value function as follows:
I9O
V T
nttt
211+
Σ F=1
n-1
mat
71 190
+
(a 22)
< <vo0
(14)
t=
Thus, To is optimal.
Next, we show that the expected value for is higher than that of To for all naive nature policies, which implies that xy is not the policy with the highest value. Starting with &eenter and f we find that both pick parameters p1 0.2, P2 Ps 0.4, in which case:
2.2 0.2%
y Ocaas VTL
(15)
1-7
For ORMDP, we find the parameters P1 = 0.2, = 0.7, P3 = 0.1. In contrast to the other policies, this means the most likely parity does not change after stochastic step. and the expected value is given as:
2.1 + 0.2%
(16)
1 1-7
Both values are strictly larger than - for any E [0, 1]. which proves the model is not naively solvable.
27

---

B Evaluating Agent Policies in RPOMDPs
In this appendix, we provide proof for theorem which we restate for convenience: Theorem 3. For any agent policy π E IT there exists a bext-response nature policy 0 X - U such that Vo E : (x)) E Extremes ((P(u) u uue U}).
Proof. We first write out the value function for policy x against an optimal nature policy 0;:
V (hi, 5,
E o(aa x))
inf
R(s,a) a)
a
EE P(u)(s' s,a) S'ES
E T(a' 120,0 a)v (1 a), x'eX
We notice that none of the terms this formula depend on h4 (except recursively via Vole), which means can remove this dependency. With that, rewrite the value function with simplified notation as follows:
V (s, Σ a(a x)Q 0,,,r,
DEA
n (8,0, R(s,a) a) +7 Σ
P(u)(s' P( P(
Σ 7(x' (2
J'ESOER
0 a) = arg inf Q
u)
well
Given this formula, we first show that an optimal nature policy exists with signature 0: X - u. We start by defining the following nature policy:
0x (x) = arg inf ΣΣ QT TEQ (0,,xx(s,,,,0 (s,a,
(17)
NElL
sESaEA
Recall our model assumes (x, a)- recttnnangull which implies i can be expressed such that every (s, a) pair has unique set of decision variables. Thus, there exists u E U that minimizes eq. 17 for each (s, a) independently.
We prove that this choice is optimal, using proof by contradiction. If (x) is suboptimal for x E X, then there must exist some history where its choice of is suboptimal. In particular, let be the first memory state reached where 0x makes a suboptimal choice, i.e. where choosing decision variables according to xx and then following 8 would lead to a higher value. In that case, there must be at least one state-action pair Sair, Qail S x A where the following holds:
Q" 8 (sanr, Oair 0% (Sain Gain x)) 0 (sanr. Oair: x, 0x xx)) <0
Since our model is (s, a) -eeetanng,,,,,, there exists a distinct set of decision variables that affect any state-action pair P(.,- 8, a), which we denote Var Then, denoting p Var decision variable, we define the following memory-based nature policy:
{ (p) otherwise.
0 (p) i E Var Var sam.aan
(x(x))))
Looking at eq. 17 we see that 0'xx achieves the same same Q-values as 0x for all state-action tuples (s, a) * (Sait, Gdilt) ). but achieves lower value for (saar. Qaaa). However, had defined 6x as the function that minimizes eq. (I7), so we have a contradiction. This means no state-action tuple can exist where 8 is suboptimal. which case fx can never make a first suboptimal choice as compared to 8- Thus, xx is optimal.
Next, need only show that an optimal policy exists such that Vz: 07 (a) E Extremes (P). This immidiately follows from the definition of Q= with the observation that, if x is fixed, y= is only dependent on the current choice u via it's arguments s' and T( o, a). Thus, a variable assignment that greedily maximizes the probabilities of reaching tuples (8/,)) with low expected values is both optimal and complies with our condition.
28

---

C Efficient Approximations for Robust Agent Policies
Here, we provide extended analysis and proofs of the theoretical results in section 5 Let B c A(S) be the finite set of reachable beliefs.
First, we introduce the HRFOMDe operator 45 in our notation. It will be used later in this appendix.
Definition 5. QRFONDP is the fixed point of the operator HRPOMDE, which is defined as:
HRPOMOPQ((..j) 0) bbss) R(s,a)
inf E P()(sss o s, max Q( Q(Tu(b,a,o),dl a'EA
WELl GENS.ES
(18)
where Tu is the belief update under variable assignment u E U defined as:
= b((') x Σ [MssP(u)(ss001s0
(19)
SES
Then, let us restate the definitions of the upper bounds we introduced in the main body of the paper.
Definition 4. QRMDE and QREIB the fixed point of the operators HRQMDP and Harm. defined
HROMDPQ(b.c) = > b(s)
R(s,a)+
inf well
Σ (())
max s, max Q a') and (2)
a'EA
SES
s'ES
HaFI
Σ b(s)
R(s,a) +
inf
max Σ
Σ a'EA
P(u)(s' ( s)))r
(3)
wEl
S'ES
Below, we provide the reasoning for the uniqueness and existence of fixed points through the Banach fixed point theorem [48). Then, it suffices to show that the operators are contraction mappings.
Lemma 4. The fixed point QuMor is synonymous with the fixed point of robust dynamic programming on the fully observable RMDP and lifting the resulting values into belief space.
Corollary 3. Consequently, the operator HROMDP a contraction mapping, and the existence and uniqueness the fixed point QuMPr are guaranteed through the Banach fixed point theorem 23
To prove that HRFIS is contraction, we introduce the following two well-known lemmas.
Lemma 5. Let X be compact set and f.g be functions of type X R. Then:
sup f(x) - sup g(x)) xex
S sup (f(x) - g(x)), and,
inf f(x) inf g(xx zex
S sup 15(x) - g(x)) (5(x))((x))
zex x
ZEX
is a well-established lemma that occurs relatively often. For a proof, see for instance [Lemma B.2; 30
Lemma 6 (Triangle Inequality). The triangle inequality states that, for any two real numbers u, R the following inequality holds:
lu + vl S |uc| + |o/.
Now, we are set to state the main theorem to prove that HRFI is indeed a contraction.
Theorem The operator HRFM: (B x A A RR) - (B - R) is contraction mapping terms of the infinity norm || lloc and the discount factor 0 < as Lipschitz constant.
29

---

Proof. Let b E B and a E A be any belief and action, and let Q: QQBx. x A + R and A -R be any two O-functions. Then:
[HRrDQQ0 a) HRVES Q' (b,
bb(s) b(s)
+ inf
Σ
max
Σ
P(u)(b', ( s,))
well
E'EA
SES
oEN
e'E8
Σ SES
b(s) [((s,) a) + inf
Σ
max a'EA oEN
P(u)(s', |s (bx,
well
E'ES
< Σ b(s)
inf well aEf
max E'EA
$ES
S'ES
inf
max A' oE
Σ
P(u)(s', ('a))
S'ES
5 Σ b(s)
max Σ
Σ SEES
(,,
sup NeW
e'EA oEN
#ES
Σ S'ES
max a'EA
on
S b(s) sup
max e'EA S'ES
P(u)(s', s,a)((bs,
wEld EE
SES
max A'EA
S y
b(s)
sup well
max
Σ S'ES
P(w)(s',o) s, (.a))((>,a'))
a'EA
#ES
DEN
Σ
P(s', o u, 8,
(b: a,,
EEES
$ 7 b(s) sup
Σ
max
Σ P(u)(s',o o s, Q(b,, Q'bb,, -
#ES
NEL
LEEn
a'EA
LES
S 7
b(s)
sup
Σ Lnnn
P s Q'll
#ES
WEH
L's
y 11Q
Q'11
Thus, it follows that, making of the definition of the infinity norm: (HRrmQ(b, HRrm (b(b,a)llac
max (b.a)EBxA
|HRI Q(b, a) HaEm (b, a)l <> Q'llae
Lastly, we note that for QREI the of reachable beliefs Bg considered by the operator is finite, as it contains only |Bsl = [S] unit beliefs. That is, the variable assignments u chosen by nature do lead to an explosion of the set of reachable beliefs. Therefore, computing the fixed point only requires computing iterations of the operator over Bs x A.
The following definition and theorem help establish the tightness of the heuristics. The proof largely follows that of Hauskrecht 221
Definition 6 (Monotone mapping). A mapping H: (B x A R) + (B x A R) is monotone if for any two Q, Q' and for all (b.a) E B A. we have that a) & (bb + HQQ(b a) S LIQ((b, a).
Theorem (Theorem 6, (1). Let Hi and H₂ be two contractions mappings with fixed points Q and Q defined the spaces of Q-value functions Qi and Q2, respectively. We have Q 2 Q if
30

---

Qi E Q2 and H2Q 2 HiQi = Qi,
Hg is monotone mapping.
Note that we may have Q1 C Q2, 12,i.e, Q1 may cover smaller space of Q-value functions.
Now, we are set to prove the following theorem of the main paper:
Theorem 4. Regarding tightness, the following inequalities on the fixed points hold:
vb E A(S), Va A: QUMDe a) 2 QRFII(b a) 2 QRPOMDP a).
Proof. Let us first restate that it is known that HRPOMDP is a contraction mapping 45 Furthermore, note that it can be shown that the operators H (HROmDP; HRFB, HRROMDP) are monotone map- pings, see for instance [Appendix 1.1.4; 30). Then, it follows from the following observation [21
HROMDE Q(b,a)
Σ b(s)
s, ss))) max Q(b,r, a(s,a) + inf Σ (T))(ss well s'ES
a'EA
SES
HREIS a))
Σ b(s)
R(s,a) + inf
Σ
max a'EA
P(u)(s', {,)))(bs,
well
HRPOMDDP((..
Σ b(s)
R(s.a)
+ inf uEll
ΣΣ Σ
P(u)(s', o 8, max Q (b, 0),
e'EA
sES
31

---

R
day
dx
8x
Swa
0.5
1-pa
asy
5
R 100
1-py
dy
0.5
yy
Syy'
Py
R 0
Figure 6: An example RPOMDP. We assume Pe E [0.7, 0.9] and Py E [0.7, 0.9]. We assume all states give the same observation.
D Experiments
D.I RHSVI
In this section, we give brief overview of the RHSVI solver used in our experiments. We start with brief introduction on value iteration for POMDPs, then repeat the initial formulation of RHSVI from Osogami 45 Lastly, we describe several alterations made to RHSVI.
We provide explanation of our alterations here for reproducibility. However, since only RHSVI as a baseline RPOMDP solver, we leave a complete description of the correctness and/or necessity our alterations for future work.
HSVL Since the value function for POMDPs is piecewise-ling lincar 55 can be represented as (possibly infinite) set of linear lower bounds I {a: S - R. known a-vectors. As shown [47]. this set can be approximated by iteratively performing a backup operation on a finite set beliefs B. To find such belief set, heuristic search value iteration 52] builds belief tree via sampling, guided by upper bounds on the value function. Thus, the belief set is restricted to reachable beliefs, which increases tractability. Moreover, by keeping track of upper bound, the algorithm can determine when the policy it has found e-optimal.
Robust HSVL Osogami 45 generalizes HSVI to RPOMDPs by changing the robust backup operator and belief update function to robust variants. We repeat both here in this paper's s notation. Given an uncertainty assignment u and belief-action pair (b, a), the backup operator is defined follows:
ar(b, a, (s) Σ ab, (s)
(20)
DEO
ar,o(b, O, u) E argmax
Σ ((s)P(n)((' s,a)a(s'). S.''SS
(21)
aeT
Given this, we can define the robust backup function and the corresponding worst-case nature policy (which directly defines the belief update function) as follows:
0r(b, a) argmin Σ (bs))ar(b...w)3))
(22)
wEll
SES
or (b, ar a, (b(,))).
(23)
If our uncertainty set is given by intervals, then both can be computed using linear program with at most O[[]][]]2) variables and ( + [[[l] contraints However, the support of both the belief and possible successor beliefs are often much smaller than [S]. which means the complexity mostly depends on |O] and [[] in practice.
Our implementation of RHSVI makes a number of changes from the description of 45 which we describe below:
Robust backup. First, we fix a problem with the backup procedure described above. Equation 21 implies that for each beliif-aatioon-obervaiii tuple (b, a, o), we pick any alpha-vector that yields that give the
an optimal value against (b, a) to compute our backup. This yields
For eq. 21 we implement the argmax operator via the constraint that Excs b(s)ar(b, Or (r, ()) must be least high any choice E l..
32

---

correct value for the current belief, but may lead to problems if we use the alpha-vector for different beliefs.
To illustrate this problem, consider the RPOMDP shows in fig. 6 Working backwards, the following
a-vectors can be found using the backup in states 8x and Sy and are thus valid:
ag' (s) = 100 [s = $
Oty' (s) 100 [s sy-]-
Next, we use these alpha-vectors to perform backups in the beliefs b and bay. which denote the beliefs reached from S, after action d₂ and axy. respectively. For the first, can quickly that the optimal nature policy picks {p= = 0.7, Py = 0.3), which yields a value of 70. For belief bay- there are multiple optimal variable assingments for nature, including {p> + 0.9, Py + 0.9]. We use this assignment, in which case 0zz' is a valid solution to eq. (2T). In that case, our backup returns the following a-vector:
Onyy (s)
90
5z 8 = Sy-
10
This gives us the correct value of 0.5 for bay, but yields value of 0.9 for bas which higher than the actual value of 0.7 we computed before. Thus, even though Cnyy can be found using the robust backup, is not valid underapproximation of the value function.
We discovered and empirically confirmed the problem with the backup function described above, but were unable to fully address the problem. Instead, implement ad-hoc fix that aims to ensure ar a) has the following properties:
1. Indifference to state, or (b,a) should have roughly equal values for each state in the support of the current belief.
2. Indifference to nature. (r a) should yield least the same value against suboptimal nature policies, as compared to the optimal one.
To achieve both, we first perform the robust backup described above, which yields nature policy 0* and robust value V. We then solve a second I.P find an a-vector of that yields the same value (up to a small error bound) but also has the properties above. To encode (1), we define the state exploitability of an a-vector as follows:
Definition 7. Given an a-vector a, beliefh, b, and corresponding value (a =Eves (()a(s), the state exploitability of a with respect to is defined as:
Expl(a, b) Σ b(s)aa(s)) Va(b)l
(24)
SES
Intuitively, (apl(a, b) is zero if the expected value of a is independent of the actual state of the environment, while Expl(a, b) Expl(a', b) implies a is more robust against changes in the underlying state then a'. We use Expl(a, b) as a penalty term for our LP, i.e., we aim to maximize
(Eses (s)) Še(a,, b) for some small value 8 > 0. To encode (2), we specify a number of nature policies that differ slightly from 8", and add constraints so that a; achieves at least value V against all of these.
We empirically find that the approach above yields accurate value approximations, which is sufficient for the purposes of this paper. However, our testing has been limited to the experiments described in this paper, which were not specifically aimed at testing our backup. Apart from that, have no theoretical basis to claim the approach is correct. We leave a more systematic analysis and solution to future work.
focuses on finding the value function for an RPOMDP, but does not consider the problem of constructing policy which matches this value. In contrast to POMDPs, this is not a trivial problem, for similar reasons to the ones described above.
Policy randomization. Osogami 45
To illustrate this point, consider the environment of fig. 7 with ó E [0. 1]. and with = 1 for simplicity. Here, the agent's only meaningful action is to guess whether they are state æ or y. Assuming E [1, 0). ONahh should pick p such that the value given for both actions and y is equal. this case, the agent is ambivalent about what action to pick, which means I = (az), with ag (s)
sw], is valid representation of the value function. However, policy that always picks
33

---

80
1-p
Figure 7: An RPOMDP showing the necessity of probabilities for robust policies.
action x is clearly suboptimal, since it performs poorly against {p + 0}. Thus, it not possible to create an optimal policy based on this P. From this example, we can conclude the following:
Remark 2. To construct optimal RPOMDP policies, 1 should generally include all a-vectors corresponding optimal actions for each reachable belief. In contrast, for POMDPs, any such a-vector is sufficient.
Note that we need not consider a-vectors corresponding to suboptimal actions for reachable beliefs. With this condition satisfied, policy should pick probabilities for each optimal action such that the expected value is robust against different nature policies. More precisely, we want to be robust against nature choosing different dynamics in previous timesteps, which would have led us different belief. Luckily, we have already defined the concept of state exploitability above, which aims to solve exactly this problem. Thus, define our policy aim and minimize state exploitability, which formally define as follows:
&Fapl
argmin Exple dEA(T)
(EE d(
-ET*
Eapl (s) = Σ
daard a(s)
OT
rer
Expl T
(a
()
Σ
Eapl (a)
acT
Although we have no proof that this is optimal, we show below that this choice is equivalent to minimizing particular upper bound on the value function:
Lemma 7. Let n² be an optimal policy and be policy that picks actions with different probabilities for some belief b but otherwise identical. Then:
V*a
va s Expl(b, x).
(25)
In particular, vb: Ebpl(bb π) 0, then is optimal.
Proof. Assuming our model is beep-preeserving supp(b) = supp(t'). Let 84, denote the states with the biggest difference in expected value, i.c.,
(s_.
argmax s, s,s' (b) aa (b)
Σ
{{a)[a(s)- a(s')]
(26)
Recall that b, the unit belief with b(s) = 1. Let b_ b... and b. b2, in which case
(=bb_ v*(b') < (²) = V* (b) < V (b4). Thus, we rewrite eq. 25 as follows:
F V < V (b4( VV
Σ x(a)[a(s+)- - a(s-)
0. (b)
< Exploit(b..n T),
which proves lemma.
34

---

Computational optimizations.
Next, we highlight number of significant alterations to RHSVI that we make to improve performance:
BeliefTree. Equation (23) shows that the worst-case nature policy, and thus the belief update, depends on the current set of a-vectors I'. Thus, for any found belief b, the possible successor beliefs may change over time. This problem is not addressed by Osogami [45], which suggest they do not keep track of the belief tree at all. This is valid approach, but it does not allow the reuse of belief nodes, which makes the method computationally expensive in practice. To deal with this, we use a belief tree, but periodically reset it at exponentially increasing intervals. This way, guarantee that RHSVI finds all reachable belief's (though this may take many iterations and resets in practice), while we can still use tree structure to find new beliefs and compute tighter upper bounds more efficiently.
Vector Pruning. As in HSVI, we prune a-vectors using point-wise domination with two changes. Firstly, since the complexity of both the backup- and belief update functions depend strongly on [r] we try to keep this set as small as possible by only adding new a-vectors if they are not dominated any a-vectors in I' This requires additional overhead but drastically decreases the cost of backups. Secondly, to allow us to compute random policies, we only consider domination between a-vectors that correspond to the same action. Thus, if a dominates a' but corresponds to different action, then a' does not get prumed.
Upper bounds. We initialize the upper bounds with the robust upper bounds introduced in section of the main body of the paper.
D.2 Benchmarks & Infrastructure
Infrastructure. All experiments were conducted in Julia (version 1.11.5) on the same Ubuntu machine (version 22.04.5 LTS), which has an Intel(R) Core(TM) 10-10XE CPU @ 3.00GHz and 256GB RAM (8 x 32GB DDR4-3200). We parallelize experiments across three workers [56].
Benchmark descriptions. Our new benchmarks, ToY and ECHO, well as the finite and infinite chain environments PARITY(10) and PARITY(DO), are described in section 3
For the second set of benchmarks, we lift several (classic) POMDPs from the literature into RPOMDPs: TIGER 6 (also used in 22 MINIHALLWAY B3 and ALOHA 24 as well
as an expanded variant of HEAVENORHELL (also used in 45
TIGER: The classic problem where agent has to decide between two doors to open. One door has tiger behind it, with a high negative reward associated, and one door has prize with a high reward. The agent only knows the initial state distribution; the tiger is initialized to one of the doors with uniform probability. It therefore has to find balance between noisy listening actions to gather information and deciding open one of the doors. Therefore, is intuitive that the nature policy heuristics that maximizes the entropy of the agent's belief leads to good approximation of the worst-case.
MINIHALLWAY: A small POMDP problem where the agent must navigate a corridor with noisy observations of the goal location, where a reward is located.
ALOHA(N): The agent must set the parameters of a communication protocol formulated as a POMDP, parameterized by N. A detailed description can be found in Jeon et al. 24]
HEAVENORHELL((V): An agent positioned in the middle of a corridor of length x N. At one end of the corridor, the agent can pass either through door on its left or its right, one of which yields a reward (heaven) and one a penalty (hell). The location of the reward is observable
sign at the other end of the corridor. Thus, the agent must learn to first visit this sign, then remember the location while traversing to the other side of the corridor.
We construct these RPOMDPs such that for any Tu)), any transition probability is less than 0.5 times higher or lower than the nominal POMDP, with no alterations to the observation function.
For the last set, we added partial observability to two henchmarks from the RMDP literature: HEALTHDEEEECTIN [16] and REPLACEMENT [T]]
HRALTHDEEECTION: The agent must schedule different methods of medical screening for colorectal cancer (or CRC) for a patient. The dynamics of the model are based on
35

---

Dimensions
[S]
Toy
ЕСHO
8
2
(ORITY(OO))
PARITY (10)
12
4
TIGER
HEAVENORHELL(5)
28
11
4
HEAVENORHELL(10)
48
MINIHALLWAY
13
ALOHAA(1))
30
30
REPLACEMENT
HEALTHDETECTION
378
Table
Dimensions of the RPOMDP benchmarks used in the experimental evaluation.
Algorithm Metric
RHSVI (
Center) std.
RHSVI(MEa) min.
RHSVI(
RMDP) std.
min.
std.
min.
Toy*
37.48
35.76
37.48
0.01
32.49
17.88
ECHO
19.31
0.01
19.30
0.01
21.12
0.00
PARITY(OO)
9.25
0.74
9.07
1.05
13.65
0.00
PARITY (10)
59.92
0.10
62.40
0.04
55.19
0.07
TIGER
19.35
0.01
19.35
0.01
13.12
0.02
(EAVENORHELLL(S)
24.04
0.01
-21.55
0.01
24.04
0.00
HEAVENORHELL((0)
37.35
0.01
-36.71
0.01
337.36
0.02
MINIHALLWAY ALOHA(10)
0.76
0.00
0.76
0.00
0.76
0.00
62.41
0.15
59.70
0.11
56.49
0.10
REPLACEMENT
47.64
0.76
46.69
0.82
46.58
0.50
EEECTIDDEEECTION
57788.42
36.29
5661.49
67.73
5554.34
32.23
Table 2: Detailed statistics for the evaluation of the naive nature policies. We report the worst value (min.) out of 5 runs as computed on the nature MDP using MCTS and the standard deviation (std.) of the values found by the 5 MCTS runs.
real medical data. In the original paper, the authors only consider number of existing screening protocols, which they combine with their model construct robust Markov chains. However, the model can also be interpreted as RPOMDP.
REPLACEMENT: the agent must schedule costly repairs for machine, which is represented by chain environment. To transform this model into an RPOMDP, we assume the agent cannot observe the state of the machine unless they pay measurement cost. Such active measure environments have been considered both for POMDPs [9 271 and RPOMDPs 28
We use discount factor = for TOY", of 7 0.99 for ECHO en HEAVENORHELL, and of 7 = 0.95 for all other environments.
Benchmark dimensions.
T the dimensions of the benchmarks used in the experimental
evaluation.
D.3
Error margins
In the plot in the main body of the paper, we normalize and plot the worst result among the 5 MCTS runs on the nature MDP. tables 2ables[]and]] andd 3] we provide the raw value (not normalized) of the worst evaluation out of the 5 runs, together with the standard deviation of the set of values found in the MCTS runs, for all the algorithms tested.
36

---

Algorithm
RHSVI
ROMDP
RFIB
Metric
min.
std.
min.
std.
min.
std.
Toy*
69.99
0.00
32.49
28.27
62.47
0.01
ECHO
31.10
0.00
25.45
0.01
25.44
0.01
PARITY(DO)
20.00
0.00
7.98
0.02
20.00
0.00
PARITY (10)
62.71
0.00
38.89
1.60
62.71
0.00
TIGER
19.36
0.01
200.04
7.33
14.49
1.27
HEAVENORHELL(
21.55
0.01
-63.76
0.00
-63.6
0.00
HEAVENOR(HELL((1))
36.71
0.01
-3.76
0.00
63.76
0.00
MINIHALLWAY
0.76
0.00
0.25
0.00
0.25
0.00
ALOHHA(0)
46.96
1.98
57.32
0.27
53.39
0.90
REPLACEMENT
46.16
0.15
51.96
0.37
70.877
2.02
HEALTHDETECTION 5596.72
46.17
5671.29
36.57
5660.60
64.77
Table 3: Detailed statistics for the evaluation of the new baselines and RHSVI. We report the worst value (min.) out runs computed on the nature MDP using MCTS and the standard deviation (std.) of the values found by the 5 MCTS runs.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize the results in the paper, and all claims are backed up by theoretical and/or empirical results.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper includes paragraph that discusses limitations at the conclusion.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs of theoretical results are provided in the appendix, and their intuition is presented in the main body of the paper.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: All essential information is specified in the experiments section. Additional details written down in the appendix. Additionally, the source code is provided.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and results are provided in the supplemental material and will be published.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Yes, while some of the aforementioned training and test details not apply, all essential information is in the main body of the paper.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper discusses the statistical significance of the results in the plot and how these were obtained over multiple runs. Standard errors are provided in the appendix.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
38

---

Answer: [Yes]
Justification: Our experiments do not require significant computing resources and are all performed on the same machine. We provide details in the appendix.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: btcctp::/neuriiie /t//rerurpp...e. httpiipp..pppbppieeee hctppuullcctthccccsuieee........
Answer: [Yes]
Justification: The authors have read the code of ethics and did not identify any issues.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is fundamental in nature. No direct societal impact is expected.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no high risk of misuse of the results in the paper.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The implementation of the methods in the paper builds on POMDPs. j1, which is acknowledged and referred to explicitly.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Code and benchmarks are provided the supplemental material with readme and comments in the code to explain important parts.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: N.A.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: N.A.
16. Declaration of LLM usage
39

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: N.A.
40


Reviews:
[{"review_id": "lNW4icvAMC", "reviewer": "Reviewer_BVbs", "summary": "This paper addresses the evaluation of agent policies in Robust Partially Observable Markov Decision Processes (RPOMDPs), a framework for sequential decision-making under partial observability and model uncertainty. RPOMDPs are conceptualized as two-player games where an agent selects actions, and \"nature\" adversarially chooses the system dynamics to minimize the agent's value. The core challenge lies in evaluating an agent policy, which necessitates finding a worst-case adversarial nature policy – a task that is computationally demanding.", "questions": "1. Would help if the authors can provide inputs on scalability?\n2. Can the authors provide inputs on generalisability of benchmarks beyond solvability, especially in real world problems?\n3. Are there any real world problems where this work will be useful?\n4. Can the provided approaches be extended beyond rectangular uncertainty sets?\n5. 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?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. Interesting take on RPOMDP research, focussing primarily on evaluation of policies. \n2. Considering different uncertainty sets, rectangular and convex.\n\nWeaknesses\n\n1. 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?\n2. It would seem that the current approach can have scalability issues especially with larger environments (e.g., ALOHA, HEALTHDETECTION)", "was_revised": true, "final_justification": "I was looking through the papers provided by the authors in the final response. I find the papers are either from control theory (where researchers do not exactly use POMDPs ) or theoretical papers, where the applicability is quite superficial.\n\nLeaving aside the aspect of applications, as that may not be as crucial. I find the scalability and theoretical guarantees on equilibrium are problematic. I am still not in favour of accepting the paper.", "rebuttal": "We thank the reviewer for their feedback and comments.\nWe will incorporate their feedback in the final version of the paper.\nWe first summarize our response, then we respond in detail to the weaknesses and questions stated in the review.\n\n## Summary\n\n#### Scalability\n\nRobust policy evaluation in RPOMDP is an inherently challenging problem, as it requires searching over possible nature policies.\nThanks 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.\nWe 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.\n\nWe acknowledge that policy evaluation is still challenging due to the continuous and potentially high-dimensional state-space.\nSpecifically, we address this in our paper in the following way:\n\n- we study scalability and the impact of the used approximation in our experiments (Q1),\n- we address it in our limitation section (L346), and \n- we highlight it as a potential direction for future work (L376).\n\n#### Real-world applicability\n\nThere exist many real-world problems described by RPOMDPs.\nWe argue that we need a means for thorough evaluation of (the robustness of) policies for problems described by RPOMDPs.\nFor instance, previous work evaluated their algorithms on benchmarks that we show by using our solvability categorization do not capture the complexities of RPOMDPs.\nOur paper addresses this gap in the literature.\n\n\n\n## Response to comments\n\n> 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?\n\nWe agree with the reviewer that our approximate evaluation method can lead to evaluation gaps.\nWe discuss the necessity of an approximation directly after introducing the nature MDP (L263), and its impact is mentioned in our limitations paragraph (L346-347).\nFurthermore, we devote Q1 of the experimental evaluation to study the impact of the approximation (and the resulting evaluation).\nTo briefly recap this research question, we indeed observe a few cases (e.g., Aloha, HealthDetection) with evaluation gaps.\nNevertheless, for most benchmarks, we do not see such a gap, which suggests the MCTS approximation performs adequately.\nTo 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).\n\nWe respond to the following comment and subsequent question in a single answer:\n\n> It would seem that the current approach can have scalability issues especially with larger environments (e.g., ALOHA, HEALTHDETECTION)\n\nand\n\n> Would help if the authors can provide inputs on scalability?\n\nAs 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.\nThus, the limitations to scalability are the same as those for solving high-dimensional continuous-state MDPs.\nOur evaluation method is not tied to MCTS, but allows the use of any continuous-state MDP solver.\nIn particular, this means that the scalability of our evaluation method will improve as continuous MDP solvers get better.\n\nWe 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. \n\n## Response to the remaining questions\n\n> Can the authors provide inputs on generalisability of benchmarks beyond solvability, especially in real world problems?\n\nThe main goal of the proposed benchmarks is to explain and test solvability classes.\nIn our paper, we identify a gap in the literature; the benchmarks used to test the solvers do not sufficiently represent the complexities of RPOMDPs.\nWe argue that this solvability is relevant in the real world.\nFor 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.\nIf 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.\nTo this extent, our evaluation pipeline can be used to determine whether a solver can be robust against such adversaries.\n\nWhile 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).\n\n> Are there any real world problems where this work will be useful?\n\nThere exist many real-world problems where agents need to deal with both model and state uncertainty.\nSuch 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).\nThus, we argue that we need a means for thorough evaluation of (the robustness of) policies for such problems.\nThis work is a first step in that direction.\n\n> Can the provided approaches be extended beyond rectangular uncertainty sets?\n\nOur 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.\n\nThe 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. \n\nAlthough 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.\nTherefore, if the rectangularity is unknown, it can be argued that assuming $(s,a)$-rectangularity is the most robust way to approach the problem.\n\nAt this point, to the best of our knowledge, no solvers for non-rectangular or $s$-rectangular RPOMDPs exist.\nTherefore, we focus on $(s,a)$-rectangularity uncertainty sets.\n\n\n> 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?\n\nThe 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.\nWe 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.\nAs 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.\nMoreover, Theorem 3 states that this policy only needs to be based on the agent's memory, as opposed to the full history.\nAs 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).\nThen, we need only consider nature's responses across this finite set of nodes.\n\n## References\nBellinger et al (2021): Colin Bellinger, Rory Coles, Mark Crowley, Isaac Tamblyn: Active Measure Reinforcement Learning for Observation Cost Minimization. Canadian AI 2021.\n\nCastronovo et al. (2016): Michael Castronovo, Damien Ernst, Adrien Couëtoux, Raphael Fonteneau: Benchmarking for Bayesian Reinforcement Learning. PLoS ONE 11(6):e0157088 \n\nCubuktepe 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\n\nGalesloot 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"}, {"review_id": "Qc2YzDScny", "reviewer": "Reviewer_bffU", "summary": "The authors present a set of intuitions, evaluation methods, algorithms and results on the problem of evaluating policies of agents in Robust POMDPs. They propose new environments to use as benchmarks that satisfy some intuitive (and some formal) properties desirable for the evaluation of policies, they justify why it should be enough to evaluate the policies against nature best response (and not agains nature’s optimal policy) and provide two extensions of existing value iteration algorithms applied to RPOMDPs. Finally they run the algorithms in the proposed benchmarks and discuss the results and implications.", "questions": "1. 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?\n2. Similar to the question above, the idea of naive solvability seems arbitrary (which the authors seem to agree as per their own assessment). 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?\n3. 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?\n4. 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?\n5. Is the fact that Tiger and HeavenOrHell are 'naively solvable' a problem for general evaluation of RPOMDPs?", "limitations": "The authors address briefly the limitations of their work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The problem is well motivated, and the contributions are clear.\n- The paper is novel and covers an existing gap in the RPOMDP literature.\n- The paper is clear, easy to follow and introduces interesting ideas.\n\n## Weaknesses\n- Some decisions or results in the paper are not well justified.\n- Some more discussion is needed to add nuance to the relevance of the contributions.\n- The implications and scalability of the work are not really clear.", "was_revised": true, "final_justification": "I consider the author's reply satisfactory. I still have some leftover doubts over the general applicability of their defined taxonomy, but overall it is relevant work.", "rebuttal": "We thank the reviewer for their feedback and comments.\nWe will incorporate their comments in the final version of the paper.\nBelow, we answer their questions.\n\n## Summary\n\n#### Intuition of solvability and relation to best-response \nWe do not view the solvability classes as methods to construct optimal nature policies.\nWe 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.\nThese are distinct concepts of the paper, but in our experimental evaluation, we use both concepts together.\nSpecifically, to show that (1) some commonly used benchmarks belong to naive solvability classes, and (2) our best-response evaluation is sound.\n\n#### Real-world applicability\n\nThere exist many real-world problems described by RPOMDPs.\nWe argue that we need a means for thorough evaluation of (the robustness of) policies for problems described by RPOMDPs.\nFor instance, previous work evaluated their algorithms on benchmarks that we show by using our solvability categorization do not capture the complexities of RPOMDPs.\nOur paper addresses this gap in the literature.\n\n## Questions\n\n> 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?\n\nWe 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.\n\nAside from providing theoretical insights (Section 3.2), we can empirically identify whether an RPOMDP benchmark belongs to any of the solvability classes. \nIn our evaluation (left-hand side of Figure 4), on each benchmark, we:\n- construct nature policies that are naive (e.g., based on ignoring partial observability or by taking the center of the uncertainty set),\n- 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 \n- evaluate these agent policies against the best-response nature policies.\n\nFor 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.\n\n> Similar to the question above, the idea of naive solvability seems arbitrary (which the authors seem to agree as per their own assessment). \n\nIndeed, we postulate that these are some of the solvability classes that are useful to identify.\nThis is evidenced by the fact that in our experimental evaluation, nature policies in these solvability classes work well on many existing benchmarks.\nYet, we do not claim that it is an exhaustive classification.\n\n> 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?\n\nAs we explain in more detail in the previous answer, the concept of solvability is not directly linked to the proposed evaluation method.\nWe 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).\n\nIf an RPOMDP benchmark is not naively solvable, a method that reports a different optimal value than the actual best-response value, \\emph{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.\n    \n> 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?\n\nRPOMDPs are designed to provide robust and conservative policies, as they are inspired by the \\emph{robust optimization} field. \nSuch policies are, for instance, often a requirement for safety-critical settings where the model cannot be fully specified.\nOur Echo benchmark, inspired by predictive maintenance problems, resembles such a setting.\n    \n> 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?\n\nThe scalability of our evaluation method is indeed an artefact of the Nature MDP that we construct. \nNote that prior to our work, it was unclear how to perform evaluation in RPOMDPs efficiently in general.\nFurthermore, 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.\n\n    \n> Is the fact that Tiger and HeavenOrHell are 'naively solvable' a problem for general evaluation of RPOMDPs?\n\nYes, 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.\nNote that Tiger and Heavenhell are challenging POMDP benchmarks, but, as we show, this fact does not make them challenging RPOMDP benchmarks. \nTo advance the field and establish with confidence what constitutes a good RPOMDP solver, we must have challenging benchmarks for RPOMDPs."}, {"review_id": "Wh3u4vtGHG", "reviewer": "Reviewer_sEqX", "summary": "In this work, authors present a new evaluation pipeline for RPOMDPs that itself has been an understudied problem. As authors describe RPOMDPs are naturally described as a two-agent games where agent policy picks and action and then nature policy adversarially picks the dynamics. Resulting in worst possible dynamics for a given policy. Authors describe three solvability classes for nature policy: trivial, naive and stationary. They define that such nature policies to be too easy and describe benchmarks that are _not_ in those two solvability classes. Best response (BR) is found to be a good substitute worst-case nature policy. This results in a nature MDP and is solvable using off-the-shelf tools.", "questions": "-", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Understudied problem is put into a strong theoretical and practical footing. \n- Idea of defining naive nature policies as too simple and showing that benchmark policies are not in the naive category gives theoretical grounding on the using benchmark policies instead of naive policies in comparisons. \n- Connection from RPOMDP to MARL (via best response natural policy) is brilliant, even though obvious idea. \n- Experiments also gave new information about the relative strengths of different environments and the usefulness of RFIB as an adequate baseline. \n\nWeaknesses: \n- 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. 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?", "was_revised": true, "final_justification": "I am satisfied with the authors rebuttal. I have also read other reviewers opinions and followed the discussion.", "rebuttal": "We thank the reviewer for their comments and feedback. \nWe will incorporate their comments in the final version of the paper.\nWe answer their questions below.\n\n> 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$?\n\nWe propose that these three categories represent solvability classes that are useful and intuitive to identify.\nThis is evidenced by the fact that in our experimental evaluation, nature policies in these naive solvability classes work well on many existing benchmarks.\nYet, we do not claim that it is exhaustive.\nAdditional categories of solvability can be defined as naive if so desired.\nWe will clarify this in the paper.\n\n> 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?\n\nThis depends on the type of naive policy that would be considered.\nIn 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.\nIn contrast, Parity is constructed with the particular naive nature policies in mind, and thus is more likely to become solvable given different nature policies."}, {"review_id": "46fEX3TljL", "reviewer": "Reviewer_rqdZ", "summary": "This paper constructs infrastructure for RPOMDP research. In particular, the authors design benchmarks for testing RPOMDP algorithms, baselines to compare those algorithms against, and a method for computing the performance of arbitrary policies (which is non-trivial in *R*POMDPs, because one has to find the POMDP that is worst for the policy in question). In order to do the latter efficiently, they prove a result showing that the worst-case POMDP must be an extreme element of the convex set of POMDPs that compose the RPOMDP. They show why the benchmarks they propose are better, in the sense of being less easily solved by naive methods, than common existing benchmarks.", "questions": "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?", "limitations": "Yes, but I would also propose adding a note that the benchmarks are fairly toy. You can certainly defend this, but it may be good to mention.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: This paper lays out it its aims clearly, those aims are compelling and important, and it accomplishes those aims. In my view, the prevailing feeling in RL that it's enough to study MDPs has hamstrung the field; studying RPOMDPs seems necessary for the field of RL to (safely) make contact with reality.\n\nWeaknesses: There were a few points where I was confused by the mathematical presentation.\n\nIt seems that the RPOMDP field is immature enough that we cannot really complex environments as benchmarks. I suppose that weakens this paper, since everything is still fairly toy. However, I suppose we build to harder benchmark environments when we have better solvers, and we get better solvers by having better benchmark environments. \n\nConfusions with the presentation:\n\n> \"decision variables v ∈ Vars,a only affect transitions and observations in the state-action pair ⟨s, a⟩\"\n\nI don't understand what this means.\n\n> Lastly, we assume P is convex, which is a common assumption for tractability reasons \n\nP is a function from U to probability distributions. Absent a total order over probability distributions, what does it mean to say P is convex? Do you mean the set {P(u) : u \\in U} is convex? Likewise, is Extremes(P) really Extremes({P(u) : u \\in U})?\n\n> V n = minθ∈Θ maxπ∈Π V π,θ \n\nWhy do you ever define this quantity or talk about the Nash equilibrium? In the rest of the paper, as far as I can tell, the min over environments is always inside the max over policies.\n\n> Intuitively, if a model is Θ-bar-solvable, then we can find an optimal agent policy against Θ by finding the optimal policy against only Θ-bar ⊆ Θ. \n\nI don't follow. If it's theta bar solvable, then there exist policies are that are optimal both against theta and theta bar, but it doesn't mean that all policies that are optimal against theta bar are also optimal against theta. Do you mean \"we can potentially find an optimal policy\"?\n\n> Intuitively, an RPOMDP with a stationary nature policy represents a POMDP. \n\nIsn't the objective different? If you represent an RPOMDP with a stationary nature policy as a POMDP, then a solver should attempt to optimize by taking an expectation over the uncertain feature of the state that corresponds to the nature policy. In an RPOMDP, the agent is not taking an expectation over the uncertain feature of the state (the fixed nature policy), but rather minimizing it.\n\n> Definition 3.\n\nShould R_n(<s, x, a>) = *negative* R(s, a)?\n\n> Def. 4\n\n\"b\" is not defined (although I knew what it meant).", "was_revised": true, "final_justification": "Thank you to the authors for answering my questions and addressing my concerns. I still recommend acceptance.", "rebuttal": "We thank the reviewer for their feedback and comments.\nWe will incorporate their comments in the final version of the paper.\nFirst, we answer the reviewer's question.\n\n> 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?\n\nIf nature picks permanent environment parameters, this corresponds to picking a POMDP with the exact same states as the RPOMDP, i.e., static uncertainty.\nOur 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.\nEven 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.\n\n\n\nNext, we aim to clarify some of the comments made in their review.\n\n> I don't understand what $Var_{s,a}$ means.\n\nWhen considering $s,a$-rectangularity, each uncertainty variable can only influence the transition and/or observation probabilities in one state-action pair.\nWe 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)$.\nThe 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}}$.\n\nOne 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))$.\nWe'll clarify the notation of $Var_{s,a}$ in the final version of the paper\n\n > 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}})$?\n\nIndeed, we mean the set $\\set{\\mathcal{P}(u) : u \\in \\mathcal{U}}$ is convex and $Extremes(\\set{\\mathcal{P}(u) : u \\in \\mathcal{U}})$.\nWe thank the reviewer for bringing this to our attention. \nWe will fix this in the final version of the paper.\n\n> Why do you ever define $V^n = \\min_{\\theta\\in\\Theta} \\max_{\\pi\\in\\Pi} V^{\\pi,\\theta}$ or talk about the Nash equilibrium? \n\nWe discuss the Nash equilibrium because, ultimately, it is what an RPOMDP solver aims to find, as it is considered the standard robust objective. \nWe use it to explain the solvability classes.\nWe 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.\nWe indeed use $V^n$ only in our definition of the Nash equilibrium and can simplify this notation in the final version.\n\n > Do you mean \"we can potentially find an optimal policy\"?\n\nWe 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$.\nWe will clarify this.\n\n > Isn't the objective different when an RPOMDP with a stationary nature policy represents a POMDP.\n\nIf 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.\nOur 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.\nWe never assume that the nature policy is known, and the objective for the agent always remains to maximize against the worst-case nature policy.\nWe will revise our statement to clarify this point.\n\n > Should $R_{n}(\\langle s, x, a \\rangle) = - R(s, a)$?\n\nNo, the objective in the nature MDP is computing a nature policy that minimizes the discounted reward.\nTherefore, we use the same reward function as in the original RPOMDP.\nWe 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.\nWe will make the objective in the nature MDP more explicit.\n\n > \"b\" is not defined (although I knew what it meant).\n\nWe define $b \\in \\Delta(S)$ on line 98, but we will clarify 'recall $b\\in\\Delta(S)$ is an agent belief' before Definition 4.\n\n## References\nBovy 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"}]

Author rebuttal:

Meta-review: This paper studies an underexplored problem of evaluating policies for robust partially observable Markov decision processes (RPOMDP).  The paper introduces and formalizes the concept of solvability of RPOMDP, noting that finding the optimal policy for an RPOMDP is relatively easy when one only needs to consider a small set of nature policies.  The paper then proposes benchmarks based on the solvability of RPOMDPs.  The paper also proposes a way to evaluate an RPOMDP policy by reducing it to finding the optimal policy for continuous MDP.

Overall, the reviewers highly value the contributions, giving with two Accept and two Borderline ratings.  AC has also read the manuscript and confirmed the reviewers' evaluations.

The most notable weakness is insufficiency of the discussion on the approximate nature of the approach of solving the continuous MDP.  Overall, however, the strengths outweigh the weaknesses, and the AC confidently recommends an acceptance of the paper.
Decision: Accept (poster)