Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability
Authors: Eline M. Bovy
Caleb Probine
Marnix Suilen
ufuk topcu
Nils Jansen
Venue: NeurIPS 2025 poster ()
Keywords: POMDPs
Robustness
Multi-environment
Primary area: theory
TL;DR: We characterize and provide algorithms for multi-environment POMDPs.

Abstract: Multi-environment POMDPs (ME-POMDPs) extend standard POMDPs with discrete model uncertainty. ME-POMDPs represent a finite set of POMDPs that share the same state, action, and observation spaces, but may arbitrarily vary in their transition, observation, and reward models. Such models arise, for instance, when multiple domain experts disagree on how to model a problem. The goal is to find a single policy that is robust against any choice of POMDP within the set, *i.e.*, a policy that maximizes the worst-case reward across all POMDPs. We generalize and expand on existing work in the following way. First, we show that ME-POMDPs can be generalized to POMDPs *with sets of initial beliefs*, which we call *adversarial-belief POMDPs* (AB-POMDPs). Second, we show that any arbitrary ME-POMDP can be reduced to a ME-POMDP that only varies in its transition and reward functions or only in its observation and reward functions, while preserving (optimal) policies. We then devise exact and approximate (point-based) algorithms to compute robust policies for AB-POMDPs, and thus ME-POMDPs. We demonstrate that we can compute policies for standard POMDP benchmarks extended to the multi-environment setting.

Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability
Eline M. Bovy" Radboud University Nijmegen, The Netherlands eline. bovyrru nnl
Caleb Probine"
The University of Texas at Austin Austin, TX, USA
cprobinedutexas. edu
Marnix Suilen University Antwerp -orpp--r Flanders Make Antwerp, Belgium marni..suilenuuanteee be
Ufuk Topeu
The University of Texas at Austin Austin, TX, USA
utopcudutexas.cm edu
Nils Jansen
Ruhr-University Bochum & Radboud University Bochum, Germany & Nijmegen, The Netherlands n. j jasenn@ubb.de
Abstract
Multi-enviromment POMDPs (ME-POMDPS) extend standard POMDPs with dis- crete model uncertainty. ME-POMDPs represent a finite set of POMDPs that share the same state, action, and observation spaces, but may arbitrarily vary their transition, observation, and reward models. Such models arise, for instance, when multiple domain experts disagree on how to model a problem. The goal is to find single policy that is robust against any choice of POMDP within the set, i.e., a policy that maximizes the worst-case reward across all POMDPs. We generalize and expand existing work in the following way. First, show that ME-POMDPs can be generalized to POMDPs with sets of initial beliefs, which call adversarial-beiin beeief POMDPs AA--POMPP4 Second, we show that any arbitrary ME-POMDP can be reduced to a ME-POMDP that only varies its tran- sition and reward functions only in its observation and reward functions, while preserving (optimal) policies. We then devise exact and approximate (point-based) algorithms to compute robust policies for AB-POMDPs, and thus ME-POMDPs. We demonstrate that we can compute policies for standard POMDP benchmarks extended the multi-environment setting.
Introduction
Partially observable Markov decision processes (POMDPs) 25 are important models for sequential decision-making under uncertainty. With numerous real-world applications, from robotics 47
to
healthcare 21 49
many algorithms to compute optimal policies have been proposed
32
39
Planning algorithms that compute policies for POMDPs rely on knowing the exact parameters of the underlying transition and observation dynamics, assumption that is often prohibitive in practice. Consider, for instance, a setting where a POMDP model constructed by domain experts. common
Shhreed first authorship. ordered alphabetically.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

POMDP
ME-POMDP
AB-POMDP
OS-POSG
Delinition
Delinition
Thm. 2
Delinitio R
Thm. 1
Delinitio
Thm. 4
Thm. 3
MO-POMDP
PO-MEMDP
Figure I: ME-POMDPs are rich class of models between POMDPs and one-sided POSGs. Arrows from class A to class B indicate that we can transform models in class A to models in class B. The transformed model size is polynomial in the original model size for all arrows not marked by *. Unmarked arrows are trivial reductions. We define MO-POMDPs and PO-MEMDPs in Section
example is the preservation of endangered bird species, akin to Chades et al. 8 Multiple experts may disagree on parts of the model, leading to discrete sets of different transition and observation functions, and thus, a discrete set of POMDPs which we call a multi-enviromment POMDP (ME- POMDP). Without expressing any preference for one expert over another, i.e., assuming prior over the models in the ME-POMDP, a policy needs to be robus/ against all possible dynamics. That is, the policy needs to be optimized against the worst-case POMDP. We study ME-POMDPs and develop exact and approximate methods to compute optimal policies that maximize worst-case reward.
While multi-environment models have been studied extensively in the fully observable case, under the name of nuvti-enniromment MDPs (MEMDPs) 9 35| existing algorithms do not apply to the partially observable case. MEMDPs continuous uncertainty known as robust MDPs 2 24 50) Robust POMDPs [RPOMDPs: 5 B1 are the generalization of robust MDPs the partially observable setting. While ME-POMDPs are, in theory, contained in RPOMDPs, algorithms for RPOMDPs rely on structural and semantic assumptions such convexity, rectangularity, and dynamic uncertainty (5 24 50) we discuss later.
the discrete version of broader class of models with
These assumptions make their application to ME-POMDPs unsuitable or overly conservative.
We study ME-POMDPss and devise algorithms compute robust policies against any adversarial choice of POMDP in the ME-POMDP. We avoid overt conservativeness that appears when existing RPOMDP approaches are applied ME-POMDPs. To summarize:
Contributions
1. Multi EavtriEnvirromenttt and Adversarial Belief POMDPs We generalize and expand the theory of mulii-enviromment POMDPs. We introduce udversurial-belleff POMDPs (AB-POMDPs): POMDPs where the initial belief is adversarially chosen from a set of possible initial beliefs. We prove that AB-POMDPs
a special case of one-sided partially observable stochastic games (POSGs) (22). and show how any multi-environmee can be modeled as an adversarial-belice POMDP. We also show that we can reduce any ME-POMDP to restricted version where either the models do not differ in transitions, i.e., a multi-observation POMDP (MO-POMDP), or do not differ in observation functions, i.e., a MEMDP (PO- (PO-MEMDP). We outline these relationships in Figure [ 2. Exact and approximate algorithms for AB-POMDPs We prove that we can combine value iteration methods for POMDPs with linear programming to solve AB-POMDPs and thus ME-POMDPs. Specifically, we augment heuristic search value iteration (HSVI) with linear programming to get AB-HSVI, point-based method for approximating value functions in adversarial-bele belief POMDPs. We evaluate AB-HSVI on standard benchmarks extended to the multi-enviromme setting and discuss how solving ME- POMPSs trades expected reward for computation time compared to a naive, non-robust baseline.
POMDP
2
Related Work
Discrete model uncertainty has primarily been studied in the fully observable setting of multi- environment MDPs [MEMDPs; 35). A large body of work assumes a distribution on the MEMDP's environments and provides algorithms for finding optimal policies 12 4 Recent work also studies reinforcement learning in MEMDPs where the environment distribution is unknown [2] contrast, we do not assume such a distribution exists, and instead focus on computing policies that are robus! against all possible environments. For MEMDPs, the robust setting has been considered for qualitative objectives [10 35
27 28 5
46 48 and integer programming has been used find
policies for robust reward maximization
42 Robust MDPs 24 50) also capture the robust setting

---

but tend to assume continuous, compact, and convex model uncertainty. Moreover, most robust MDP algorithms require uncertainty to be independent across states or state-action pairs, an assumption known as rectangularity. The discrete uncertainty used in MEMDPs and our setting is inherently non-rectangular. See Suilen et al. 45 for a detailed discussion of rectangularity assumptions.
We combine discrete model uncertainty with partial observability. Robust POMDPs IRPOMDPs; 31 extend robust MDPs with partial observability, but again rely on the assumption of convex 30
31 44. Two RPOMDP papers address discrete settings 23 36 however, these works assume the underlying model can change at each timestep, i.e., dynamic uncertainty. In contrast, when we consider the worst-case coss model, we constrain the model to be consistent across timesteps. The work [I5] develops subgradient descent algorithms for robust reward maximization in hidden-mode model POMDPs, a type of ME- ME-POMDP In contrast, our algorithms are aalue-iteration-bat -based, and we provide thorough characterizations of the relationships between different subclasses of multi-environment POMDPs, and their relationships to POSGs.
and rectangular uncertainty sets [3 16
Work on unsupervised environment design, e.g., 14 29 ME-POMDPs, as a model when designing reinforcement learning agents. In contrast to these works, which provide gradient-based learning approaches for minimizing regret, we give value-iteration- based planning methods for designing robust policies.
uses underspecified POMDPs, equivalent to
3 Preliminaries
A probability distribution on finite set X is mapping μ:: X - [0, such that Σxex (zx) 1. We denote the set of distributions on X by A(X). Given two distributions μx and Jyy on sets X and
Y. respectively, we denote their product distribution on X x Y by μx x py. For x E X. 8g is the Dirac distribution that satisfies (z) 1. We denote the set of integers {l...., n by [n]. The set of finite sequences with elements in a set C C". We use 1 and T for dummy states and observations.
We now introduce partially observable Markov decision processes (POMDPs). We consider expected cumulative reward maximization over both finite and discounted infinite horizons. For brevity, we compress these two settings into single definition.
Definition (POMDP) A partially observable Markov decision process (POMDP) is a tuple M T, O, R, b, H) where S. A, and Z are finite sets of states, actions, and observations, T: S x A + ASS) is a transition function, O: S A + A(Z) is an observation function, R: S A + R is a reward function, b E (SS) is an initial state distribution, E [0, 1) is a discount factor, and E NU {oo} is a horizon.
When H = oc, we restrict E [0, 1). For the case where + = 1, we require that the horizon H be finite, Additionally, for the case where H oc, we define H + 1 H, such that H/ 1 oo. Unless we specify otherwise, we assume all actions are available in all states.
A fully observable Markov decision process is a POMDP where Z = S and O is the deterministic
identity mapping, i.e., Vs E S, E A: O(s, a) = 8g. A policy π in a POMDP maps a history of actions and observations a distribution over the actions, i.e., T: (Ax x Z) + A(A). We denote the set of policies in a POMDP M by II.- We remark that one may differentiate between two classes of history-dependert randomized policies. A behavioral policy is mapping :: (A x Z)* + A(A), while a mixed policy is a distribution over deterministic behavioral policies.
A belief b E A(S) describes the probability of being in a state given the initial state distribution and a history. We can define belief-based behavioral and mixed policies n: A(S) + A(A) and :: (SA A). Unless otherwise mentioned, we use history-based behavioral policies.
The value of policy in a POMDP M is Vă= EE H E where r; is the reward at time t.
policy '² optimal if for all म, we have VM 2 VM- We denote the optimal value as VM+ VM-
3.1 Solving POMDPs
Standard POMDP methods use piecewise- -inear convex (PWLC) representations of value functions through set of linear functions, known a-vectors 25 Each vector S - R. represents
We remark that
S was contemporaneous and leave an empirical evaluation against it as future work.
3

---

deterministic policy and maps states to the values of following that policy when we initialize the POMDP at that state. In the finite- horiz-n setting, a-vectors represent t-step distory-basee policies, and we compute a new set of a-vectorss r3 for each timestep & S H.
r1 = (a: S R (s)) R(s, Va E A);
(1)
r = fa: S + R a(s) R(s.a) + Σ ()xx) T(s, ((s.a)(s)0((s)
(2)
aa........... E A (T.
The upper envelope of the a-vectors in П3 forms a PWLC function that corresponds to the optimal value function V for horizon 1. The optimal value given initial state distribution by is given by (bbb) = max Eees (s)))
In the infinite-horizon discounted setting, a-vectors represent relief-basee policies. Instead of com- puting multiple sets, we iteratively expand single set I. The upper envelope of I' can approximate the optimal value function arbitrarily closely. For some initial set of a-vectors r, we can compute new a-vector for each (a, az
O2zz2) E AAx T similar to the finite-horizon setting as follows.
ass) R(s, a) + E (s'a))sxz T(s, as (O(ss ())=)a(()')
In both settings, we can prune a-vectors from I' that are pointwise dominated by a single other a-vector 38 Pruming can be performed at any iteration, since pointwise dominated a-vectors will never contribute to the upper envelope of I or future iterations of r.
Heuristic search value iteration Various approximate POMDP solvers based on a-vectors, defining different ways to expand N to efficiently approximate the optimal value function, such as In particular, heuristic search value iteration [HSVI: keeps track of both upper and lower bound, i.e., a set of belief value tuples and a set of a--eectos, respectively, of the optimal value function. HSVI performs a depth-first search from an initial state distribution, updating the bounds along the way. The depth-first search selects actions optimistically with respect to the upper bound, and observations leading to the belief with the largest uncertainty, i.e., the largest gap between the upper and lower bound. The depth-fine first search continues until the belief at depth has gap of at most e e.y's with e > predefined error. After each depth-first search, the gap between the upper and lower bounds at the initial state distribution is computed. If the gap exceeds e, we continue with another depth-first search. The upper and lower bounds are initialized before the first depth-fire first search. HSVI computes the initial upper bound with the Fast Informed Bound [FIB; 20 and the initial lower bound with an a-vector for each policy that always plays the same action
3.2 One-sided Partially Observable Stochastic Games
Next, we introduce the specific form of partially observable stochastic games (POSGs) we consider in this paper. As with POMDPs, we again consider both finite horizon and discounted infinite horizon settings, and the same restrictions on and H apply.
Definition 2 (POSG) A one-sided partially observable stochastic game (POSG) is tuple G (S, As,A,, Z,T,O O, R, b, y, H) where S is a finite set of states. A1 is a finite action set for the partially observing player, A2 a finite action set for the fully observing player, 7 is a finite set of observations, T: S:S* x A₁ x A + A(S) is the transition function, O: S x A x A -> ((7) is the observation function, R: S x A x A2 The is the reward function, b E A(S) is initial state distribution, and E [0, 1] and H E NU } are the discount factor and horizon respectively.
We consider concurrent POSGs, as studied in Horák et al. 22 A policy for the partially observing player is a mapping n (A, x Z)* + A(Ar). while a policy for the fully observing player is a mapping :2: (S x A x A₂ Z)* X - (A2)). We write IT's and IT2 to denote the sets of policies for the partially observing and fully observing players, respectively.
A pair of policies (T)) defines distribution state-action trajectories in POSG. We define the value of a policy π, for the partially observing player by the worst-case expected reward V/z"
min E Σ >rr)) where rt is again the reward time t. The value of the game is V = max,, V Existing algorithms for one-sided POSGs work by adapting exact and pasnt-based value iteration techniques for POMDPs (22].
4

---

4 Adversarial-Belle and Multi-Enviromment POMDPs
We now formally introduce adversarial-belief POMDPs (AB-POMDPs) and multi-environment POMDPs (ME-POMDPs), and show the relations between those models and POSGs.
4.1
Adversarial-Beliet POMDPs
Adversarial-belie/ POMDPs are POMDPs where we replace the initial belief with set of beliefs.
Definition 3 (AB-POMDP) An adversarial-belief POMDP is a tuple M (S, A, Z,,, R, B, 7, H) where we define S, A, 2,, O, R, and H as for POMDPs, and B C (SS) is a set of beliefs.
In AB-POMDP, the objective is to maximize the expected reward in the POMDP under the worst-case initial belief in B. For an AB-POMDP M and belief b E B. we write M, = (S, A, Z,T,O, R, Y, H) for the POMDP obtained when initializing the AB-POMDP with belief b.
Problem Given an AB-POMDP M, solve VM- max minge VM.-
When the set of beliefs is the set (Q) some subset of states Q, any AB-POMDP is equivalent to a zero-sum one-sided POSG, and we codify this result in Theorem 1. In particular, for an AB- POMDP, Theorem gives recipe to construct a POSG that allows us find optimal policies for the AB-POMDP. In this POSG, the partially observing player is the agent, and they have the same actions and observations as the original AB-POMDP. We replace the set of beliefs with a second player whose action set is the set of states Q We shall refer to the partially observing player as the agent, and the fully observing player as nature. By choosing an appropriate distribution over states, nature can choose a distribution in A A(Q) against which the agent's policy is evaluated. The optimal policy for the agent this POSG gives an optimal policy in the original AB-POMDP.
Theorem Let M = (S, A, T, O, R. AQQ) 7, H) be an AB-POMDP. We define the associated
oie-sided POSG 9 ((S x (1,2)) U (1) A, A. Q. (T), R, H
R,,1,
1) where
T(3 a, 9) = (T(s,a) x 82
[d(q.1)
$=1,
==(8))) Ó(3,a,9) = (((s,))
-
$ == 3 = 1),
8 (s.
and R(S, a) 0f Land R($.a.g) R(s.03/y when s= [s. for all & (S x {1,2)) U {1}.a E A, and E EQQ Additionally, assume that the agent's action set in the POSG at 1 is a singleton set } where E A. Then, the value of the AB-POMDP M and POSG & are equal, and for any policy o E IT' the policy n in the AB-POMDP given by
T(a1, 21...., On. 2n) = o(. T,01, 21,..., an. 2n
for (a1, 21, Og 2n) E (A x Z)", satisfies VM = minseA()) VM. = VVg
The proof of Theorem I is in Appendix A.I and follows by establishing mappings between the policy spaces of the AB-POMDP and POSG that preserve value. We add 1/y reward-correction to compensate for the extra step added to the beginning of the game. We expand the state space to ensure the stage-one observation is the dummy observation T. Finally, we restrict the agent's action at I so they can not use the initial action as an extra source of randomness to mix over behavioral policies. We can bypass this assumption in fnite-horizon settings by applying Kuhn's Theorem (26).
4.2 Multi-Enviromment POMDPs
We now introduce ME-POMDPs and show they are special case of AB-POMDPS.
Definition 4 (ME-POMDP) M = (S,A, Z, n, (Ti)ee (irhig {Ri Bienn (b.hiei) H), tuple, a multi-environment POMDP where S, A, Z,y Y and H are as in POMDPs, i.e., finite sets of states, actions, and observations, a discount factor, and horizon. We have n E N environments and for index i [m), T; : x A + A(S) a transition function, Oc: x A + A(Z) is an observation function, R3 S x A + R is a reward function, and by ASS) is an initial state distribution.
For fixed E [n]. the tuple M. = (S, A, Z, Tú, Or, R2, b, 7, H) defines the i-th POMDP in the ME-POMDP. The objective is to maximize the worst-case reward across the environments.
5

---

Problem 2 Given ME-POMDP . solve VM= = max min VM.
In defining ME-POMDP, we assume that the reward functions {R; (efn) exist on an appropriate scale. For example, if we define a ME-POMDP from expert opinions where one expert uses large rewards to define their environment, the robust policy may be biased toward said environment. One must avoid such cases, for example, by ensuring experts calibrate rewards using the same scale.
We can solve ME-POMDPs using AB-POMDPs. For a ME-POMDP, Theorem 2 gives recipe to construct an AB-POMDP so that optimal AB-POMDP policies are optimal in the original ME- POMDP. We construct an AB-POMDP where the state space is the product of the original state space and variable for the environment. The adversary choosing a belief in this AB-POMDP corresponds to the adversary selecting an environment in the ME-POMDP. We formalize this reduction as follows.
Theorem For a ME-POMDP M = (S. A, Z, n, (Te)) (O:hetm) (Re)e {bx [et))))) 7, H). define the associated adversarial-bellef POMDP M ((S x [m] x {1,2]) U ([1) x [n]), A, Z U H + 1) where for all (5 [n] (1,2)) U ({1) [n]) and (T), T, Ô, RG (([1) x [n]),,,
a E A, we define
bb x 8; x 61
8= (1,1),
f
sōt (s,
8 == (L, V = (8, 1);
T(, a)
Ō(8,a)
(s, a) 6, x 82
8 (s,
$ == (s,i,2),
and R($,a)= = 0f = (1, and R(s.a) R,(n0)ly when 8 (s) Additionally, assume that the agent's 's action set in the AB-POMMP at states in {1} x [m] is a singleton set (0) where & E A. Then, for any policy a E Ma the policy in the ME-POMDP given by
< 21, ,nn 2n) = 00, T,01, 21, ................................ ,n,,, 2n) V(a, 21, On zn) E (A x Z)*
satisfies minge|1] VM, = -iine Va Also, the values are equal, i.e. VM = MM
The proof of Theorem is nearly identical to that of Theorem 1 elaborate in Appendix A.1
4.3 Restricted Models and Reductions
ME-POMDPs may differ in their transition, observation, and reward functions. By requiring all environments to either share transition observation function, get restricted models. When the observation function O, does not change with the environment, we label the model as a partially observable multi-environnen
MDP (PO-MEMIPP), i.e., multi-environment MDP (MEMDP) extended with an observation function. PO-MEMDPs are equivalent to hidden-model POMDPs [5)
We can transform an AB-POMDP where the belief set B is the set of distributions over state subset into a PO-MEMDP, while preserving optimal policies, and Theorem 3 encodes this transformation. Given B = (()) for state subset Q and policy प, the worst-case belief is dn for some & E Q, and defines an initial state. The PO-MEMDP encodes these possible initial states.
Theorem 3 Given AB-POMDP M = (S, O. A(Q), H) where the belief set is A(Q) for a set of states Q S. S. define an associated PO-MEMDP M ((S x (1,2}) {t
JU (T), QQ1, (Tabee O Ri 1,,5,,,,, y, H + 1), where T, Ô and ft are as follows.
f,(3,0)= ((16,,)) a)) x
bōg x5 61
$-,,
Ō(3 =
{ōt (s(,,))
8 ==1v8- = (s, 1),
82
s = (s.j),
s= 2).
Meanwhile, R(S,a)= = R(a.a)// if & (s.j) for some 8 E S,j {1,2) and R(L, a) 0. Also, assume that the agent's 's action set in the PO-MEMDP at 1 is a singleton set (0} where Q E A. Then, for any policy o E II IM the policy in the AB-POMDP given by
T 21. ,n, 2n) = o0,
un, zn)
Va1 21, an, mn) E (A x 2)*
satisfies minGEA(Q) VM,, = min M, and the values are equal, that is, V* = Vi--
The proof of Theorem 3 aggain follows the same techniques as Theorem D as we show Appendix A.1 Note that we slightly abuse notation by indexing ME-POMDP models with states q Q.

---

Theorem 3 shows that AB-AAB-PPOA are equivalent to ME-POMDPs as PO-MEMDPs are subset of ME-POMDPs. Additionally, Theorem 3 shows that we can represent any ME-POMDP with polynomial larger model with multiple transition functions, i.e., a PO-MEMDP.
When the transitions T and initial distribution b do not change across the environments, ie., (T; bx) (T', bÿ) for all i E [r2], we refer to the model as multi-observation POMDP (MO-POMDP). By Theorem for any PO-MEMDP, we can construct a MO-POMDP with the same optimal policy.
Theorem Given a PO-MEMDP M (S, A, Z, [m], (Ti)een)) O, O.(Ra (bx) 7, H), define MO-POMDP M (Six), A, Z, [m], (O:)eE))) (Ra He(n), bi ... x bay 7, H) such = 0 a), and
that T(1....., 8n, a) = a)()),a) x ... x Tn(sn: a), (s(
(s Sny a) = R,(5; a). The policy sets satisfy IIM = Ig and for all π E IIM we have minge(x) VM. minie[n] V
The resulting MO-POMDP simulates all environments in the state space. Changing the enviromment changes the copy of the state that generates observations and rewards, and thus, for policy æ and environment i, the two models have the same reward. The full proof of Theorem i in Appendix I
Theorem Sacooremerqquine requires multiple reward functions the MO-POMDP, and we prove that these are, in fact, necessary for the finite-horizon case in Appendix A.2 An illustrative example of the utility of ME-POMDPs, MO-POMDPs, and PO-MEMDPs, adapted from g can be found in Appendix B
5 Algorithms for AB-POMDPS
We provide algorithms to solve AB-POMDPs by combining value iteration and linear programming. AB-POMDPs are equal POMDPs up how we specify the initial belief. We show that given serewwise-linert convex value function for the POMDP, we can compute the value of the AB-POMDP by minimizing the value function. This problem linear program (LP). Additionally, we can use the dual LP solution to construct a policy for the agent that attains the value.
5.1 Computing Policies by Solving Linear Programs
When the value function has a piecewise-lineal convex representation through set I' of a-vectors, and the belief set B is of the form (QQ) for some subset of states Q S S. we can minimize the value function by solving linear program. Indeed, minimize the value function for beliefs in B by solving minse (Q) ma a b, and this problem can be expressed in the LP in 33)
The resulting value is the value that nature guarantees by playing belief b. i.e., no matter the policy the agent plays, if nature plays b, the reward will not be greater than v. Minimizing the value function upper bounds the AB-POMDP's value, but it remains to show that a policy exists attaining this bound.
We construct a policy for the agent that attains this value by solving the dual LP, presented in (4) Each a-vector corresponds to a deterministic history-dependent policy. In the policy corresponding to the solution y (4), the agent draws an a-vector according to y and plays the corresponding history-dependent policy. The resulting value e is the value that the agent can guarantee by playing the policy corresponding to y, i.e., no matter the initial belief nature plays, if the agent plays y, the reward will not be less than v. In Theorem 5 we show that the policy we construct from the solution to the LP (4) is optimal.
Theorem Let =
H) be an AB-POMDP, let be a finite set of a-vectors such that max b is the value function for this AB AB-POMDP, and let Pol: I - IIM
min OER
U,
(3)
max MER ,EE
U,
(4)
s.t. Va ::: Σ .E (ss)b(s) SU,
As Q: Ener ass)((a) 2 v.
s.t.
V8 E Q b(8)) 2 0,
Va TT: v(a) 20,
Σ EEQ b(s) = 1.
Σ ael y(a) =
7

---

be mapping that returns a determinislic history-dependent policy n such that V-Po((a) a b. If Mr
y E TR. is the solution to LP 4 then the policy for the agent where they draw an a-vector randomly according to and play the corresponding dererddde policy is an optimal policy for M.
The result above shows that solving an adversarial-belicf POMDP reduces to solving a zero-sum game where nature plays beliefs and the agent plays a-vectors. Indeed, the LPs above encode the problem of solving a static zero-sum game []. Both LPs correspond to minimizing a piecewise- linear convex function over compact set, so solutions exist. Theorem 5 proof simply applies the definition of the LPs, and we detail this proof in Appendix A.3
We remark that while Theorem 5 describes procedure to construct mixed policy, that is, a mixture of deterministic policies, we can construct a behavioral policy IIM with the same value, following Kuhn's s theorem 26]. and we detail this construction in Appendix[A.4
We additionally remark that if max.eT a under-approximates the value function, we can still construct a policy that attains the value min)e max.er b, as long as Pol exists and satisfies
V-Pol(a) 2a a...u b. We discuss implementing the Pol mapping in Appendix A.5
5.2 Adversarial-Belie HSVI
Since AB-POMDPs are equal POMDPs up to the initial belief, we can use well- known POMDP methods to generate the a- vectors that form (an approximation of) the value function. For example, for a finite- horizon H, we can compute I Hr according
Algorithm 1 AB-HSVI
Input: E [0, 1). c)
Initialize T with Fast Informed Bound
Initialize I' with "always play action a" a-vector Va E A
worst-case state distribution in I using LP while Gap(Tr, b, 2 do
to Equations [ and 2 HH represents all deterministic history-basee policies of length H and does not require specifying the initial state distribution. We can, there- fore, compute the optimal value and robust agent and nature policies by applying the LPs 3 and to Tw. Note that can prune dominated veveors in I' without influencing the result of the LPs.
T, [ + one iteration of HSVI(Y, b,b, 7,
b <- worst-case state distribution in I using LP
end while
To construct more efficient algorithm, we can generate a-vectors that approximate the optimal value function in the infinite-horizon setting using approximate -reetor-based POMDP methods such as HSVI. As explained in Section 3] HSVI provably converges to a gap between upper and lower bounds on the optimal value function of less than predefined at given initial state distribution. If we use an arbitrary initial state distribution and run HSVI as-is, the algorithm converges for that state distribution, but there are guarantees for the apper-lower-bound gap at other distributions. However, the lower bound is still a sound under-approximation of the value function.
We use this observation to construct more sophisticated solution, which we call adversarial- HSVI (AB-HSVI, Algorithm Tp. We compute the worst-case initial state distribution between each depth-first search using LP 3 and start the next depth-first search from this distribution. Essentially, this procedure restarts HSVI, initializing with the upper and lower bounds of the previous iteration. This algorithm terminates once the worst-case initial state distribution has gap between the upper and lower bounds of less than 6, giving us a tighter approximation.
Experimental Evaluation
The implementation of the LPs and along with AB-HSVI (Algorithm [) forms a solution method for ME-POMDPs, and we answer the following research questions regarding this method.
(Q1) Scalability: What is the computational cost of solving AB-POMDPs?
(Q2) Baseline comparison: What is the added difficulty of robustness against adversarial beliefs
compared to naive baseline of solving individual POMDPs?
(Q3) Model formulation: Does the model type, i.e., whether the problem is formulated as a ME-POMDP, PO-MEMDP, MO-POMDP or AB-POMDP, influence the performance?
As no benchmarks exist for POMDPS, we introduce two benchmarks for our experimental evaluation. The first benchmark is based on the endangered bird preservation case study presented in
8

---

Table I: Lower bound value, time of convergence, and left-over gap between upper and lower bound of the Bird problem for various problem sizes and model types.
Properties
PO-MEMDP
MO-POMDP
ME-POMDP
Model
S
n
[2|
Vea
Conv (s)
Gap
Veu
Cony (s)
Gap
Ven
Conv (s)
Gap
3,,,3
3
3
68.26
58.50
70,44
84.98
69.62
2039.31
3.3,3,4
3
44.44
4.33
54.85
2976.33
6
44.79
6.02
B.3,3,5
3
3
2
74.58
3104.30
< 6
80.01
21.08
< c
74.59
0.61
3,3,4,3
3
4
2
20.48
7.80
24.09
118.82
<<
22.56
5.81
3
5
31.23
11.63
31.85
175.99
32.73
9.74
3,,
4
3
2
63.91
19.57
73.49
2.51
55.96
28.56
3,,,
5
3
2
35.57
6.76
36.04
5.30
35.84
6.77
Appendix B which we shall refer to as the Bird problem. We extend the model to ME-POMDPs, PO- MEMDPs, and MO-POMDPs, using randomization to generate transition and observation functions to obtain non-trivial problem instances. In particular, we parameterize the number of states |S] 2 2, actions |A|, and experts n. We denote instances of this benchmark as (s).A,,)),
We exclusively use randomization create challenging ME-POMDP problem instances. Even with randomization, creating challenging environments difficult. When generating 100 random models for the Bird problems with 3 states, 3 actions, and 3 experts, we only found 35 out of 100 non-trivial PO-MEMDPs, where a model is trivial if we can solve in less than 30 seconds.
Remark 1
For the second benchmark, we extend RockSample 40 to ME-POMDPs. We parameterize the grid size m, good rocks g. and total number of rocks f, and denote instances of this benchmark as RSm.g,t- We consider randomized and relatively fixed rock positions. We denote the RockSample instances with fixed rock positions as RS m.g.t. See Appendix C for full details on the benchmarks construction.
We set time limit tl of 3600 seconds, discount factor y 0.95, and set HSVI's gap threshold to c 0.1 Rmin where Rmuin is the minimum problem reward. We use sparse matrices and prune fully dominated aevetoors. We run experiments computer with Intel Core i9- 10980XE 3.00GHz processor and 256GB of RAM. We use Gurobi 18 to solve LPs. All code is available at [6]
Results and Discussion
(Q1) Scalability Tables and show the results of rumning AB-HSVI the Bird problem and Rampee In both problems, the convergence times and gaps increase with the number of environments. The RockSample problems generally converge faster than Bird problems, likely due to RockSample's terminal state. We note that the structure of the environments has a great effect on the difficulty of the problems. In Figure 2 whether they are close or far to the agent's 's initial position, have a significant influence on AB-HSVI's convergence time. The relationship between environment configuration and solve time explains why, for the Bird problem, the convergence times and gaps are not monotonic in the problem size.
we show that the relative positions of the rocks, iee.,
(Q2) Baseline comparison We compare AB-HSVI with the values and time required to solve all individual environments (i.e., standard POMDPs) on RockSample. We summarize the results in Figure 4 and give details in Appendix [ The time increase for the ME-POMDP computation, shown in Table 3 primarily scales with the number of environments. We also note that robust values achieve an expected reward that is close the rewards in individual models, and the robust value far exceeds the worst case of playing the optimal policy for an incorrectly assumed environment.
(Q3) Model formulation For a Bird problem ME-POMDP, Table I shows how solve time and value vary when we either (1) fix observation functions to get a PO-MEMDP, or (2) fix transitions to get a MO-POMDP. AB-HSVI tends to converge more quickly and return higher values for showing that uncertain observation functions are easier to handle than uncertain transitions.
We can formulate problems as either AB-POMDPs or ME-POMDPs, and we compare these formu- lations for RockSample in Figure 3 In all but two instances, AB-POMDPs converge faster than ME-POMMPss Also, gaps between convergence times increase with the number of environments. Finally, we note that AB-POMDPs report slightly higher values than ME-POMPPs, but the difference is less than the error Details on the two formulations and the results are in Appendices
C and D

---

Table 2: Lower bound value, time of convergence, and left-over gap between upper and lower bound of the RockSample problem for various problem sizes with rocks nearby or far away.
Properties
Rocks nearby
Rocks away
Model
S
|A|
[2|
Vea
Conv (s)
Gap
Vea
Conv (s) Gap
RS
9
7
3
16.53
11.70
16.53
11.70
<
1S
19
16.14
52.74
c
14.68
169.95
<
RS
33
7
3
15.48
130.77
< c 13.02
1588.97
< 6
RS
51
7
3
15.40
331.37
< 11.03
1.46
RS
73
7
3
14.52
640.40
<
RS7,1,2
99
3
14.54
1280.66
<
1,5
9
3
15.90
115.11
< 15.90
115.11
<6
RS5,1.3
19
8
3
15.41
269.10
< 14.34
1072.32
<6
RS
33
8
3
15.14
787.82
< 11.11
2.73
RS RS
51
3
14.80
1793.75
<
8.15
5.34
RS
73
14.31
2556.11
RS7,1
99
8
3
13.30
2.25
Convergence timie
1500
Nearby
Convergence time
AR-POMDP
Far away
ME-POMDP
1000
2000
500
1000
RSS 2.12
1,12
RS 1.2
RS
1.
RSC
R. RS RS 1.4 RS1,1.3
RS RS5, RSA
Figure 2: Convergence time of RockSample in- stances with rocks nearby vs. far away.
Figure 3: Convergence time of RockSample prob- lems modeled as AB-POMDPs vs. ME-POMDPs.
30
Table 3: Conver- gence time increase from summed individ- ual POMDPs to ME- POMDP in Figure
Individual POMDPs
25
ME POMDP
Value (higher is bettes)
20
Worst incorrect POMDP
15
10-
Model
Factor
RSa,1.2
2.11
RS3,1.3
17.68
RSa,1,4
65.09
RS3,2.3
5.49
-5
RSS.1.2
RSS.1.
RSS,1.4
RSS.2.3
RSA.1.2
RSS.1.2
RSA
RS4.1.2
2.15
RS5,1.2
4.84
Figure 4: Lower bound values of POMDPs a ME-POMDP, the ME-
RS
2.50
POMDP, and worst-case missassumed POMDP for RockSample instances.
7 Conclusion
We presented new results on multi-environment POMDPs, iee. discrete sets of POMDPs for which we need to compute single policy that maximizes the worst-case expected reward. We introduced adversarial-beliet POMDPs as an overarching model and showed how these AB-POMDPs are special case of partially observable stochastic games. Leveraging the understanding of ME-POMDPs as A--POMMPss, we developed exact and point-based algorithms for computing policies ME- POMDPs. Future work will investigate more efficient algorithms by leveraging the structure in ME-POMDPs and AB-POMDPs, or by using additional HSVI optimization techniques such as tracking previously explored beliefs and using compact state space representations 33
The main limitation of this work is the scalability of AB-HSVI, particularly. the substantial increase in convergence time with the number of environments, We believe that exploring policy-gradient or online-planning methods for ME-POMDPs a critical next step to ensuring their applicability, and we believe that our theoretical results provide foundation for this work.
Limitations
10

---

8 Acknowledgements
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). This work has also been partially supported by the Air Force Office of Scientific Research (AFOSR) under grant number FA9550-22-I6 0403, and by the Office of Naval Research (ONR) under grant number N00014-24-122797, It has also been supported by the FWO "SynthEx" project (G0AH524N).
References
[1] Vinayak S. Ahluwalia, Lauren N. Steimle, and Brian T. Denton. Policy-based branch-ane and-boundd for infinite-horizon multi-model Markov decision processes. Comput. Oper. Res., 126: 10:::05100 1088 2021.
[2] Thom S. Badings, Thiago D. Simão, Marnix Suilen, and Nils Jansen. Decision-making under uncertainty: beyond probabilities. Int. J. Softw. Tools Technol. Transf., 25(3):375-391, 2023.
[3] Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
[4] Tyler J. Becker and Zachary Sunberg. Bridging the gap between partially observable stochastic games and sparse POMDP methods. CoRR, abs/2405.18703, 2024.
[5] 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, 2024.
[6] Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, and Nils Jansen. Code for the AB-HSVI algorithm and the experiments in the paper: "Multi-ennironment POMDPs: Discrete model uncertainty under partial observability" (NeurIPS 2025), 2025. URL https://doi htg/10.5281/zenne
17425571
[7] Peter Buchholz and Dimitri Scheftelowitsch. Computation of weighted sums of rewards for concurrent MDPs. Math. Methods Oper. Res., 89(1):1442, 2019.
[8] ladine Chades, Josie Carwardine, Tara G. Martin, Samuel Nicol, Régis Sabbadin, and Olivier Buffet. MOMDPs: A solution for modelling adaptive management problems. In AAAI, pages 267-273, 2012.
[9] Krishnendu Chatterjee, Martin Chmelík, Deep Karkhanis, Petr Novotný, and Amélie Royer. Multiple-enviromment Markov decision processes: Efficient analysis and applications. ICAPS, pages 48-56- 2020.
[10] Krishnendu Chatterjee, Laurent Doyen, Raskin Jean-François, and Ocan Sankur. The value problem for multiple-environmeent MDPs with parity objectives. CoRR, abs/2504.15966 2025.
[11] Fan Chen, Yu Bai, and Song Mei. Partially observable RL with B-stability: Unified structural condition and sharp sample-efficien algorithms. In ICLR, 2023.
[12] Fan Chen, Constantinos Daskalakis, Noah Golowich, and Alexander Rakhlin. Near-optimal learning and planning in separated latent MDPs. In COLT, volume 247, pages 995-1067, 2024.
[13] Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, and Ufuk Topcu. Robust finite-state controllers for uncertain POMDPs. In AAAI, pages 11792-11800, 2021.
[14] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre M. Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In NewrIPS, 2020.
[15] Maris F. L. Galesloot, Roman Andriushchenko, Milan Ceska, Sebastian Junges, and Nils Jansen. Robust finite-memory policy gradients for hidden-mode POMDPs. In IJCAI, pages 8518 8526. ojcai.org, 2025.
11

---

[16] Maris F. 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 ECAI, 2025. To appear.
[17] Marek Grzes, Pascal Poupart, Xiao Yang. and Jesse Hoey. Energy efficient execution of POMDP policies. IEEE Trans. Cybern., 45(1 1):2484-2249 2015.
[18] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www gurobi com
[19] Milos Hauskrecht. Incremental methods for computing bounds in partially observable Markov decision processes. In AAAI/IAA,, pages 734-739. AAAI Press / The MIT Press, 1997.
[20] Milos Hauskrecht. Value-function approximations for partially observable Markov decision processes. J. Artif. Intell. Res., 13:33-94, 2000.
[21] Milos Hauskrecht and Hamish Fraser. Modeling treatment of ischemic heart disease with partially observable Markov decision processes. In AMIA, 1998.
[22] Karel Horák, Branislav Bosanský. Vojtech Kovarík, and Christopher Kiekintveld. Solving zero-sum one-sided partially observable stochastic games. Artif. Intell., 316:103838, 2023.
[23] Hideaki Itoh and Kiyohiko Nakamura. Partially observable Markov decision processes with imprecise parameters. Artif. Intell., 171(8-9):453 (188-)94433-4900 2007.
[24] Garud N. Iyengar. Robust dynamic programming. Math. Oper: Res., 30(2):557-280, 2005.
[25] Leslie Pack Kaelbling, Michael L. Littman, and Anthony Cassandra. Planning and acting in partially observable stochastic domains. Artif. Intell., 101(1-2):99-134, 1998.
[26] Harold Kuhn. Extensive games and the problem of information. Contributions to the Theory of Games, 2(28):193-216, 1953.
[27] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Reinforcement learning in reward-mixing MDPs. In Neur/PS, pages 2253-2264 2021.
[28] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent MDPs: Regret guarantees and lower bound. In NewrlPS, pages 24523-24555 2021.
[29] Nathan Monette, Alistair Letcher, Michael Beukman, Matthew Thomas Jackson, Alexander Rutherford, Alexander David Goldie, and Jakob N. Foerster. An optimisation framework for unsupervised environment design. CoRR, 0os/2505.20657) 2025.
[30] 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,
[31] Takayuki Osogami. Robust partially observable Markov decision process. In ICML, volume 37, pages 106-115, 2015.
[32] Joelle Pineau, Geoffrey J. Gordon, and Sebastian Thrun. Point-based value iteration: An anytime algorithm for POMDPs. In IJCAI, pages 1025-1032, 2003.
[33] Pascal Poupart and Craig Boutilier. Value-directed compression POMDPs. In NIPS, pages 1547-1554, 2002.
[34] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
[35] Jean-François Raskin and Ocan Sankur. Multiple-environmennt Markov decision processes. In FSTTCS, volume 29 of LIPIcs, pages 531-543 2014.
[36] Soroush Saghafian. Ambiguous partially observable Markov decision processes: Structural results and applications. J. Econ. Theory, 178:1-35, 2018.
12

---

[37] Yannik Schnitzer, Alessandro Abate, and David Parker. Certifiably robust policies for uncertain parametric environments. TACAS (3), volume 15698 of Lecture Notes Computer Science, pages 63-83. Springer, 2025.
[38] Guy Shani, Joelle Pineau, and Robert Kaplow. A survey of point-based POMDP solvers, Auton. Agents Multi Agent Syst. 27(1): 2013.
[39] Richard D. Smallwood and Edward J. Sondik. The optimal control of partially observable
Markov processes
finite horizon. Oper. Res., 21 1973.
[40] Trey Smith and Reid G. Simmons. Heuristic search value iteration for POMDPs. In UAI, pages 520-527, 2004.
[41] Trey Smith and Reid G. Simmons. Point-based POMDP algorithms: Improved analysis and implementation. In UAI, pages 542-547, 2005.
[42] Lauren N. Steimle, Vinayak S. Ahluwalia, Charmee Kamdar, and Brian T. Denton. Decomposi- tion methods for solving Markov decision processes with multiple models of the parameters. IISE Trans., 53(12):1295-133
2021.
[43] Lauren N. Steimle, David L. Kaufman, and Brian T. Denton, Multi-model Markov decision processes. IISE Trans., 53(10): 124-1139, 2021.
[44] Marnix Suilen, Nils Jansen, Murat Cubuktepe, and Ufuk Topcu. Robust policy synthesis for uncertain POMDPs via convex optimization. In IJCAI, pages 41 4113-4120, 2020.
[45] Marnix Suilen, Thom S. Badings, Eline M. Bovy, David Parker, and Nils Jansen. Robust Markow decision processes: place where Al and formal methods meet. In Principles of Verification
(3), volume 15262 of Lecture Notes in Computer Science, pages 126-154, 2024.
[46] Marnix Suilen, Marck van der Vegt, and Sebastian Junges, A PSPACE algorithm for almost-sure Rabin objectives in multi-envirrnment MDPs. In CONCUR, volume 311 of L/Plcs, pages 40:1-40:17, 2024.
[47] Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probubilistic robotics. MIT Press, 2005.
[48] Marck van der Vegt, Nils Jansen, and Sebastian Junges. Robust almost-sure reachability in multi-environment MDPs. In TACAS (I), volume 13993 of Lecture Notes in Computer Science, pages 508 526, 2023.
[49] Athanassios Vozikis, J. E. Goulionis, and V. Benos. The partially observable Markov decision processes in healthcare: application to patients with ischemic heart disease (IHD). Oper. Res., 12(1):3-14, 2012.
[50] Wolfram Wiesemann, Daniel Kuhn, and Berş Rustem. Robust Markov decision processes. Math. Oper. Res., 31()3:153113318 2013.
[51] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D. Lee. PAC reinforcement learning for predictive state representations. ICLR, 2023.
13

---

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: Yes, the theoretical characterizations in the first contribution are formalized theorem statements in Section 4 Regarding the algorithmic contributions, detail the
algorithm in Section while we detail the empirical properties of the algorithm in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All theorems are stated with their assumptions. The limitations of the algorithm, such as the scalability, discussed in the experiment section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: We state the assumptions in all theorems in the main text, and we give full proofs in the appendix, which we will submit with the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code is included in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

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?
Question:
Answer: [Yes]
Justification: Yes, upon publication, we will make the implementation publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips. ctapps.cc/uubii//uuiic guwdes/ddeeeee CodeeSumieieeeeeeeeeee ssi onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
The hyperparameters are discussed in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
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: [No]
Justification: The algorithm is deterministic. It does not use any randomization during runtime, and hence will produce the same result upon running it twice. Note, we do use randomization to generate the models that we run our algorithm on, but then the models are fixed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources are discussed in the experminents section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurt httpp//pccppc..ccccceeeeeeeeeeee
Answer: [Yes]
Justification: This research is theoretical, and does not have direct path to harmful applications consequences. We do any data drawn from humans.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Again, this research is theoretical, and does not have direct path to harmful applications or consequences, so we do not discuss societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks by virtue its theoretical nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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: Where we use existing algorithms and models, we cite them appropriately.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
latasets.paperssi
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve human subjects/ccrowdsourcinng.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve human subjects/crowdssurrinng.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
20

---

A Complete Proofs
A.1 Proofs from Section 4
Proof of Theorem 1 We prove Theorem 1 by constructing mappings between the policy spaces for the adversarial-belief POMDP (AB-POMDP) M and the partially observable stochastic game (POSG) & that preserve value.
We first recall the policy spaces for M and G. Let 1lM define the policy space for the AB-POMDP M, and let M be the policy space for the agent in the POSG G. Recall that a policy æ E II is a mapping
T: (Ax 2) + ((4),
(5)
while a policy a Ill. is a mapping
a: (A x (Zu(T)))) + ((A).
(6)
We note that due to the restriction on the agent's actions at the initial state, the initial action given by deterministic and always evaluates to Q. That is, (c) = O where is the empty history.
We claim that for any policy in the AB-POMDP, we can construct corresponding policy in the POSG with the same reward, and vice versa.
To prove the first direction the above statement, define a mapping f: II - I1 as follows
TT22, 22
Ans 2x) n 2 2, Az2 # T A.... A on # T,
(()) 02,
022 22, ..... Ung Zn))
T())
= 1,
60
otherwise.
We note that this definition implies f())(c) 6g. and thus f(r) is consistent with G. The first two cases define the policies for feasible trajectories in the game, only the first observation will be T. The last case handles the initial action, and ensures the policy is well-defined.
We claim that and ((x) have the same value. That is,
min VM. min V ((((), BEA(Q)
m2Ell3
where we use V/T.. to denote the agent's expected reward in the game G when the agent and nature play policies and n2 respectively. This fact follows from the structure of the game. Indeed, the structure of the game 9 is such that at the initial state 1, nature's action defines an initial state in S x 21, States in S x {1,2} are then closed under transitions in the game G, and have identical dynamics to M up to the flag in {1, 2}. with nature's 's actions having no effect. For completeness, we carry out this reasoning in its entirety below.
We first compute Vgg (m))))
(2=(1.1) denote the reward that the agent receives from stage 2 onward when &2 = (q. 1) for some q S. We use 8 denote the state in the game G at time f, and for all t 2 2, we note that by definition of G, 8, will be of the form (s,, 44) for some s, S and i, (1,
(=)=(g.)) (1,))
where let V (=),Ta
can apply the definition of the game and the policy (TT) to obtain
H+1
V (2
9
(q.1)
E
1-1 R(, 0:)182 (g.
(9)
where
8411 T(Se, 01,
Vt > 2,
(10)
a++1 [(z) 21,,,,,,,...... 21)
VL 2 2,
(11)
T1+1 (2(h
Vt 2,
(12)
2 ~ Õ at))))
2.
(13)
For each t 2 3, we have & = (st, 2) for some E S, by definition of f, and for all t 2 2, we have 8141 T(t,, ax), again by definition of f'. By assumption, $2 q. We then note that, by definition
21

---

of G, and the fact that &2 E S x (1), that 21 T. and by definition of f(T) we also have a1 = O, and hence we have ((T)(a), 21, 02 ..... 0r 2.,2) [a2, ....... Gr 2,), and f())(a), 21) (e). For
ae) = ( a). Finally, expanding the reward, we have R(3,, ax) = a))/ for all / 2 2. Thus, we can rewrite the expectation as
t 2 2, we have 24 ~ (((41, =
H+
= E
Σ
7
R(st, az)ls2
(14)
where
81+1 ~ T(st.
Vt 2 2,
(15)
a2 ~ T(E);
(16)
a++1 ~ T[ 22, at, 21)
vt 2 2, V 2.
(17)
2t (s at)
(18)
However, up to relabeling states and timesteps such that 5/ = s1+1. oj ac+1 and 2/ = 21+1 this expectation is exactly
H
E
Σ
R(s d,)]si =
(19)
where
1/11 T(s at)
3 1,
(20)
a¹ ~ T()), 4/41 ~ 2/ 2 0(((+1:0()
(21)
a, 2t)
V 2 1,
(22)
1 1.
(23)
This expectation is then equal to MM,." and thus we deduce
(=).
(2-11)1)
V Mag"
(24)
We now compute the agent's 's total reward in G. By 224. and the fact that the reward from the first stage is always 0 for the agent, we have
EP(5s (g,1)) 1)] Vg (x),77 12=(0.1)
(25)
9EQ
and by the definition of the game G. we have IP [82 = (q. 1)] = P[ (L) ql.
Finally, to prove that (8) holds, we construct nalue-preserving mappings from A(Q) to I and vice versa. This fact holds as the agent's reward only depends on nature's policy through the actions at I, and so each belief is associated with class of policies that have that belief as the initial action
distribution for the nature player. Define, for given belicf e A(Q), a policy -!! 11 with
b (h) - p otherwise,
{
h 1=1,
(26)
where p E Q is arbitrary. We have, by definition of (b) that
vgl v
(0)
Σ b(g) QEQ
1=
Σb(0) VM.,, VM, 9EQ
(27)
Thus, for any belief there exists a policy for nature that attains the same value in the POSG as the belief b would induce in the AB-POMDP. Similarly, given policy T2 II2 if we define 2 (2),,, we have
V
Σ (g)
VM.
Σ
P [T) = 9l Vgl (x)
sg (q.1) = ve (x)
(28)
QEQ
With this equality, conclude (8) holds.
22

---

We have proven that for any agent policy in M, we can construct an agent policy f in g with the same value. This fact establishes one direction of the equality of the value of M and that
max VG 2 max VM-
(29)
e g
#Elly
Mapping f is not bijection, but for each POSG policy mT' construct a policy o' !T' such that a' & Range([), and o' has the same value o, and proving this fact will complete the proof.
Given o, define E IIM such that
4 (a1, 21,..., Ons 2n) (0, T1,,, .1....,
................................ On kn) V(a O, za) E (A Z)", (30)
Note that we, by an abuse of notation, use this definition to communicate that g-(c) = o(0, T). We can then write as
(c) = -og 00. T) = (c).
(31)
(32)
00, T, ,2, 22, On: zn) = { Yo (az, 22, ..,...,,,, an, zn)
22 + A A an #T,
(33)
(r(a2, 22 22...., Ons 2n)
otherwise,
a 21, Un 2n) = w(a1, .1,.... an;; kn); Vas + O 21 + T,
(34)
where r and some mappings from (A (Z (ZU to (A) determined by a. By 8
have that v=((-=) Var However, by definition of g, 01 = O 21 = T, and 2; E Z for all 2 2. Hence, a and f(g.) will agree for any feasible path. Thus, we conclude that fact
V/ (o Vg.
(35)
We can now deduce that, for any POSG policy, there exists an AB- AB-POMDP policy with the same value, thus establishing the other direction in the value equality between g and M. Indeed, the policy fqx) is the required of which has the same value as o, but lies in the range of f. Additionally, if we
set â Go. have
V
(36)
which completes the proof of Theorem !
We also give proofs of Theorems 2 and however, these proofs are highly similar to Theorem so
we only highlight key differences.
Proof of Theorem
Let I define the policy space for the multi-environment POMDP (ME-POMDP), and let I1 be the policy space for the agent in the AB-POMDP. policy π E IIM a mapping
:: (A 2)" + AA,
(37)
while a policy a E UM is a mapping
(Ax (ZU AA.
(38)
We define the same mapping f 11. + IIm as in Theorem ! That is,
T 22.... Ony 2n)
n 2 F T A.... A nn + T,
f(z)(a1, 22, a2 22. ... On 2n) =
T(C)
n = 1, otherwise.
d0
(39)
For fixed pair of policies, n and ((T),, we claim that (()) b E A([1} In]). is
VM. The value of f(T), for belief
M
Σ b(r (x)
(40)
Marl
sE(m)
23

---

and as the belief set is the set of distributions on set of states,
min
B Vd ((r) kE(D) (. DEA((L)x(N)
Σ
min
Σ be10 V min V (())
(41)
vE(m) Mas...)
sE(m]
The second equality simply uses the fact that if we minimize a function Eis Gaz; for (r:) in the of distributions [n|., the minimum the smallest element in (ci)
We can write the value for a fixed initial state as
M+
(x))
E
Σ
R(3,, as)
(42)
Ma
2=
where
81 (1, 1),
(43)
81+1 ((5,, 0t)
V/ 1,
(44)
AA WE 1,
1 ~ f(x²((1)))) (a), 21, 02 22, Oe, 2x)
(45)
(($+11,
2N 1.
(46)
We ignore the first timestep reward as is Using the definition of the AB-POMDP M, we can evaluate (m)
Ma Let & denote the state in the AB-POMDP at time t. We have 82 = (82, i, 1)
where 82 ~ be. For all t 2 3, we then have & = (s,,2, where 8141 ~ T((s;, az). By construction
of the AB-POMIP, we have 01 = Q and 2 ~ ( 01) = ( i, 1), = 8T, so again, we have (T) 21, 02, ..... Ge, 2x) (aa; 22. ,2,...,,.. 21, and [() T) (e). For all
we have 2t a1) Ó((s+11, ax) 01(s+11, at). Finally, we have R(Se, at) =
R((s,, a.) = Ra(ss, /7 for all t 2 2. Thus, we can write the value as
H+1
/
Mar1.
=
Σ
(47)
1=2
where
$2 ~ byt
(48)
81+1 (((s, at)
Vt 2 2,
(49)
a2 ~ T(E)
(50)
0++1 T 22............ a2 2)
Vt 2 2,
(51)
2, ~ (,($111,a)
Vt 2 2.
(52)
Finally, by the same state and timestep relabeling approach used in Theorem obtain
f((()) ME(L.))
VMM
(53)
Thus, we have
min ((
Σ b(L
v+(()) MarL.n
= min
= min VM,
(54)
iE[m)
iE(n)
xE(m)
That is, the mapping f preserves the value of the policy between the ME-POMDP and the AB- POMDP, and so we have proven VM 2 VM.
For the reverse direction, we can again use the same argument as in Theorem Indeed, we can take any policy E ITM and decompose it into policies qo, r and w where do is a policy in the ME-POMDP such that
go (a1, 21, ......... Grs 21) a00 T, 010 31, ae 21)
((1122..... ar 21) E (A Z)
(55)
As the policies f(go) and a agree on all feasible histories in the AB-POMDP M, we deduce that
(4=)
MM
(56)
M
24

---

From this statement, we deduce that Vi = VM,, and we have also implicitly proven, via the fact that VM
Vg. that the mapping from 1a to IIM given in Theorem preserves the value.
Proof of Theorem 3
The proof of this theorem follows the same framework as Theorems and That is,
1. We define a mapping f IIM + I as in Theorem
2. We prove that V = v=((=) for each π E Il.-
3. We prove that, for each II j the policy do defined by
do (a1: ;1,...,,0; 0t, 2x) = o (0, T, (11 F1, (t, v(a1; .1,...;. 01, (t, #t) (Ax x 2)' satisfies VM- VM
((x) Ma and we conclude that VMM Vaa along with the fact that
the mapping + 9o preserves value.
By assumption, the belief set B is the set distributions over Q, and so, for a policy ι E Ilm.
min bEA(Q)
M,
by min DEA(Q)
Σ
VM
min V
(57)
QEQ
QEQ
Thus, the value of policy in the AB-POMDP M the worst-case value when we take worst-case across the initial state.
However, this differentiation in the initial state is exactly how define the partially observable MEMDP (PO-MEMDP) M. Indeed, for the same mapping f IM MM as in the previous
theorems, we can evaluate (=)(m) follows. Let & denote the sequence of states in the PO-MEMDP
M, M. For environment, q. we have $2 (g. 1). by definition of T, and for all 2 3, we have 8, (s,, 2). where $t-1 ~ T(st, at), again by definition of T. We have 21 ~ Ö 0) = Ó(q 1). 0) = 8T and for all t 2 2, we have 2, ~ (3++1, ax) = ((((+1,, 2), at) Os5+1, az). We additionally have, as in Theorem 1 ( ø1, 02 .2....,,. 21) = [a2, 22..... at, 21), as 01 = and 21 T, and we also have (=) 21) = x()). Finally, we have that R(31, a1) = and for all 2 R(S;, a.) = R(((2, 4), = R(s,, aty/y. Thus, we have
#+1
Σ
7
R(ser
(58)
Mr
where
82
(59)
St+1 ~ a(s;
Vt 2 2
(60)
21 (8
1I 2 2
(61)
02 ~ x())
(62)
0++1 πl (a) 21
O2₁ 2,)
VI 2 2.
(63)
We can then again use the same relabelling steps as in the proofs of Theorems
I and
to conclude
(())
V
(64)
Mg
We can then deduce the same value equivalence result, that is
min ((x) (m) Mi
min VM,,,
(65)
QEQ M,
gEQ
We then complete the same proof for step three as we used in the proofs of Theorems and
Proof of Theorem 4
25

---

As the PO-MEMDP M and multi-obseree observation POMDP (MO-POMDP) M share action and observa- tion spaces, they have the same policy spaces.
Fix an arbitrary policy т E M and environment i. It sufficient to show VM:
V M,
The proof then follows immediately by looking at the reward in the MO-POMDP. Denote the MO-POMDP state time by
(66)
By definition of the MO-POMDP have
H
H
E
Re(Se, az)
= E
(67)
M;
where
81,1 ~ bi
(68)
$1,1+1 a1)
w21
(69)
2t ~ ((L(+1,,
221
(70)
a1 T())
(71)
a++1 ~ T(1,, 21, ag, 2()
Vt 2 1.
(72)
However, up to labelling of the state random variable, this expectation is exactly VM
A.2 Multiple Reward Functions are Necessary for Theorem
We next show that the presence of multiple reward functions is necessary for MO-POMDPs to simulate PO-MEMDPs and hence ME-POMDPs in the finite-horizon case. Previous reductions have shown that we can construct policies for one class, such as ME-POMDPs, by copying optimal policies from another class, such as PO-MEMDPs. We argue that such reduction exists for MO-POMDPs when the reward does not vary with the environment. This argument appeals to the case where the environment has single observation. With single observation function, the multiple observation functions must be trivial, mapping all state-action pairs to one observation. Thus, as the reward function does not change with the environment, the MO-POMDP becomes POMDP and has a history-dependent deterministic optimal policy. Meanwhile, PO-MEMDPs exist with a single observation and randomized optimal policies. Hence, there exist PO-MEMDPS such that no MO-POMDP produces a correct optimal policy. We formalize this argument in the following proposition.
Proposition 1 Consider the PO-MEMDP M ({s), fai, a2), (=),2, (Tiheep)) 0, (R.)ep) 8,, 1, where
Ri (1), = 1,
(73)
(1,) 1,
(74)
Re(s, = -1,
(75)
R2(s, 02) 1,
(76)
and Т, and O defined appropriately. There does not exist MO-POMDP M
A A, 2, T, [O.henn), RR, b, 7, 1) with an isomorphic observation and action space to M, such that all optimal policies for M are optimal for M.
Proof: The proof of this statement is mostly described in the preceding paragraph, but we elaborate it for completeness.
The PO-MEMDP M is a 2 x 2 matrix game, and has as a unique optimal policy
[a
with probability 1/2 a2 with probability 1/2.
x =<())
(77)
26

---

As the horizon of M is 1, the policy class comprises distributions on actions, and does not depend on the observation.
The policies in IT A are also distribution over actions. However, as there is a single reward function, the reward of any policy is just the expected reward when we take the expectation over the action and the initial state. Thus, there exists an optimal policy for M that takes an action deterministically.
The above argument is similar the remark in 4 that one can not use POMDPs solve POSGs due to the different types of optimal policies they possess.
do in Theorem 2 for the reduction from ME-POMDPs to AB-POMDPs, the observations at these timesteps would still need to be trivial to enable translation of MO-POMDP policies to the PO-MEMIPP Thus, even with these added timesteps, the policy would not depend on observations, and a policy would consist of distribution of action sequences. There would then exist an optimal policy that deterministically follows an action sequence that attains the maximum expected reward.
We remark that even if added finite number of extra steps to the MO-POMDP,
We additionally remark that Proposition can also be proven when replace the PO-MEMDP M with a PO-MEMDP M that has multiple transition functions instead of multiple reward functions, but still, single observation. Indeed, we simply add extra step to M, and define two extra states 81 and 82, such that the multiple transition functions change which action from {a,, a2} leads to which state. We then define reward of +11 for one of these states and reward of -1 for the other, such that each action always leads to a reward of +1 in one environment and reward of - in the other. These environments create the same problem in Proposition | where the environment swaps the reward associated with each action, and so we require random optimal strategies.
A.3 Proofs from Section 5.1
Let â be the randomized policy we describe in Theorem 5 and let v² be the optimal value of For any b E (Q)) we have
Proof of Theorem
5
V
Σ V Ms
Pol(a)
Ev(a) aer
[s(s)((s) Eo*b(s) u
(78)
aer
SES
The first equality uses the definition of म. The second equality uses the assumption on Pol. The third equality uses the feasibility of and the fact that b only has support in Q. The final equality uses the fact that b is a distribution. Thus we deduce V v². However, by the duality of the LPs (3) and 4 2" is also the optimal value of 3 and so 2* is an upper bound on the value of any policy. Hence, we conclude that attains the optimal value of the AB-POMDP.
A.4 Constructing Behavioral Policies from Mixed Policies
Theorem 5 gives a recipe for constructing a mixed policy an AB-POMDP which attains the value. In this section, recall Kuhn's theorem (26 to give an explicit construction of an equivalent behavioral AB-POMDP policy.
Suppose a finite set P (II..... } of deterministic history-dependent policies is given, and let { be a distribution over these policies that defines a mixed policy т.
We can construct a behavioral policy by randomizing over the deterministic policies in P that could have generated the current history. For a given finite-length history h4 = (0), 21,-.., 0e, 21) in (A x Z)", define T(a1, ..,.... Ge, 21) with
T(a1, 21...., ar, 21) = {i E [m] |vk E it -- 1]: (e(a1, ((aa,,,,,.... 21,..., ag. 2x) = ax+1).
(79)
T(h2) contains the indices of the deterministic policies in P that could possibly generate a history hi- Define a behavioral policy as in (66 by
E Eie Enerch Pi
T(h) + 0 otherwise,
TP (he)(a) =
(80)
where @ is fixed action in A.
27

---

The policies т and Tp.p have the same value for any POMDP. Indeed, the result in 26 implies that the distribution on finite-lenghh histories is the same.
Proposition 2 ((26)) Let P = 1I....., Fm, and { define mixed policy n, and let T. be the behavioral policy in (80). Then any funite length path ($1, a1 21, at 26) has the same probability under the mixed policy and the behavioral policy Tp.
The proof of this statement follows by expanding the conditional probabilities that define the path. Thus, for any finite S H we have
R(ss, an) = ERPP
Σ 7 1- B(st,a))
Es
Σ
(81)
In the infinite-horizon case, we have
lim ET
Σ 1 R(s,, an)
lim E ETp.
Σ
/ R(Se,a)) ar)
1-000
10000
[==
R(se, an)
E
lim 1000
2-1 R(se, ac)
= ETP
lim 1000 1=1
[=1
(- R( an)
Ex
(-1 R(s,, 0z)
= ETPE
(82)
We can swap limits and expectations here the inner random variable is always bounded between 4/1-y and 1/1-9, where is a lower bound on rewards and U is an upper bound [34]. Thus, we conclude that the two policies have the same expected infinite-horizon reward.
A.5 Constructing Mixed Policies from Approximate Value Functions
We must validate that the approximate value function and the associated a-vectors satisfy the assumptions of Theorem 5 that for each a E I, there exists a policy π such that
M, 2 a b vb A(S).
(83)
Throughout this section, will use
P(s', 20,2 = T(s, (s))ss)ss
(84)
as shorthand for the probability of transitioning next state s' and seeing observation when the agent takes action a at state
In a point- backup, we start with an initial set of a-vectors, and then we define each new a-vector with an action and a mapping from each observation some previously generated a-vector a.. That is,
((s) = R(s,)) +y
Σ P(s',22s, s'E8,2E2
(85)
For each a-vector, we can define two functions Act l' A and Next x Z + I' that return the action and a-vectors that defined it. For a-vectors that are not the initial a-vector, we define Act and Next such that Act(a)
and Next(a, 2) a, in 85
For the initial set of cevectors, define an a-vector aa,u for each action a, that represents the policy that deterministically plays action a at every time step, as in [4]. To compute the a-vector a, we start with the a-vector that assigns the reward of the worst-case state for each action to each state, that is
0s. min R(s(aa)
(86)
1 1-7
We then improve each 0a,0 by applying the following value iteration until the desired convergence.
(s,0(8) + R(s, + Σ (s),oo))))))'')..
(87)
28

---

By starting this iteration with the worst-case state underapproximation, HSVI ensures that 0a is correct underapproximation regardless of the number of iterations 0,20- We set
Act(O,,0) = Next(a 2) = Qa,0
1/2 E Z.
(88)
We note that with this a-vector definition we have, for any initial state, that
(s))(s) (cc=Act(a..o)
R--R(s ae][8i
(89)
and hence this a-vector lower bounds the value of the policy of always playing Act(o...).
We can use these mappings define a policy by tracking current a-vector state. Indeed, Algorithm gives recursive definition of policy using the Act and Next functions. This method of extracting policies corresponds to the sinite-state machine policy design [1 20
Algorithm 2 Extracting policies from a-vectors.
procedure EXECUTE(h = (a1, 21, des 2t), a)
if t then return (ct(a)
else
return EXECUTE(h = (a2, 22,..., Nex.tt 21))
end if end procedure
The policy we define in Algorithm satisfies the requirements for Theorem 5 Indeed, we have the following proposition.
Let Pol - II be the mapping given by Algorithm Ttht defines how to extract policy from a of a-vectors. Then for all E T, 80 E S, we have a (80) a b S Vi for all b E A(Q).
Proposition 3
Pol(a) (8o), and so
VM
This lemma specializes Proposition 9.7 in [22] which describes how to recover policies from approximate value functions in one-sided POSGs. The resulting proof is simpler than in 22 as the result we give only needs to hold for POMDPs.
Proof of Proposition 3 We go by induction on the order in which we generate the a-vectors. Let I'k be the first & Z | generated a-vectors.
For the base case, when & = |.A,, I's contains the initial a-vectors {an.ala E A). By the definition of Pol, Pol(a...) is simply the policy which always takes action Act(aa,0) a, and by 89 we have, for all sg. that
0s,0(50) S Vi
Po)(a...)) (su).
(90)
Now, & be arbitrary, and suppose that, for all a E TR, 80 S, we have V Poll(a) (8o) 2 a(so). Let 0'++1 be the a-vector generated next. When the agent plays Pol(ax+1), we play Act(ax+1). 1), observe some z, and then play Pol col(Next(0x+1: follows
2)) from the next state. Thus, we can express the reward as
Pol((a--))(s) (so) = R(so, a) +y VM
Σ 2'ES,2EZ
P(s', 2/s0, a) (o
(91)
V Pol(Nex(or (5) Next(an=1, for
Applying the inductive assumption, we then have all z, Next(ax++1, Tæ. and so we obtain
V (ol((a)))) (so) > R(su. a) +7
Σ S'E8,EEZ
2ls., [dd,://0.o)Nex((4111))))
(92)
and by definition of 0441 through the backup we deduce that VM Pol( 2 (84)) As 80 was arbitrary, we now have that the hypothesis holds for the entire 0k+1 Since I l'411 I' (a4+1)
29

---

the hypothesis holds for all vectors in FR+1- By the principle of mathematical induction, we then conclude that the lemma holds for all a-vectors in
We remark that, as 22 this procedure still works when pointwise dominated vectors are pruned. However, we must update the Next function in this case. Indeed, we define Next as an operator that returns some a- vecttr that dominates the output of Next, L.e.
Ne (s) 2 Next(a, (s) S,
(93)
and we define a corresponding policy in Algorithm
Algorithm 3 Extracting policies from vevetoors with pruning.
procedure EXBCUTE(h (a1, 2...... oes 21), a)
if' = then return Act(a)
else
return EXECUTE(h (a2, 22...., ae, 21 2.)) 21))
end if end procedure
version of Proposition 3 still holds when we execute policies using Algorithm 3 but the analysis
needs to be modified. The proof we give follows Proposition 9.7 in [22] again with simplifications due to the simpler setting of POMDPs.
Proposition 4 ((22) Let Pol r II be the mapping given by Algorithm
that defines how to
extract a policy from a prumed set of a-vectors. Then for all a E T, 8p E S. we have a<(su) I
y-Pal(a) (so).
M
Proof of Proposition 4
122
Let U max R(s, a), L = min.es.oe. R(s, a), and K U L. U is upper bound on the reward, while L a lower bound on the reward.
Let Poly(a) define a policy such that, for the first j actions, we follow Algorithm 3 and for the remaining timesteps, we use some fixed action E A. We will first show that the reward of the policy (ol)(a:) starting from 8o is approximately lower-bounded by as0)), where the approximation error decreases geometrically in j. We then take limit j to prove that a(s)) lower-bounds the reward of Pol(a).
We first show by induction, that for all I, S, and j E E:0 we have
Vi Pol, (a) (5o) 2 a(s)) 1- K.
(94)
We first note that any a-vector is bounded above by U/(1 - 7). This fact obviously holds for the initial a-vectors. For any subsequent a-vectors, we have by induction that
U
U
( R(s,a)+
Σ 2(s', SU) ( 1-7 1
(95)
1-7"
''S
where the induction is with respect to the order in which we generate a-vectors.
For the main induction, that is 94 we have our base case
Poloaa) (sv) Em,=0
R(ss,
Σ L= Σ Σe
Σ -
(1) 1-7
U
E1 + a(ss) a(so) K. (96)
Σ
The inequalities follow from the definitions of and U along with the fact that the a-vectors are bounded by 1/1-7.
30

---

Inducting on j. for an arbitrary a E I we then have
(Pool [a) (50) (s0) R(so, a) +
Σ
P(s', 2/50, VM -ol, (Nex(a))))))))) (5))
VM
70 K
2 R(so:a) +7
Σ
P(s', 2/50, a)
(Nex((a,))('))
1 ?
e'E8,EE2
90-1
2 a)
Σ 2'E8,EE
P(s', 2/50, a) (exx(a,2)(s)))
1 1-7 K
7 (97)
= a((0)
1-7 K.
The first equality is just expanding one step of the value. The first inequality uses the inductive assumption Vi (=Pol;- (s') 2 a(s') -Ky''/1- The second inequality uses the definition of Next. The final equality uses the definition of a through the backup.
We can then use a similar bound between V/M (a) and VM y-Pol(a), Indeed, as these policies share actions for the first j timesteps, and rewards are bounded, we have
73
M
(-Pll(a)
(so)
2 VM
(-Pol,(a)) (so)
1-7 K,
(98)
and combining the inequalities
97 and 98 we get
27d
po)(
(5o) 2 a
K,
(99)
M
and we can take a limit in j to conclude that we have the desired inequality.
D
B Endangered Birds Preservation Model
Consider a population of endangered bird species, in [8). The progression of the population is influenced by natural causes, such as feral cats hunting the endangered birds. We model the population of endangered birds under different actions to influence the progression of the population. At any time, we classify the population as being either low (s1), middle (sM) or high ($ although assume we can only observe whether the population is high (oн) or low (O1). We consider two possible actions to influence the progression of the population level: control the feral cats (C), or do nothing (DN). The goal is increase the population level to high and keep it there without wasting resources. For this purpose, we associate a reward to each state-action pair: R(81., C) =
-5, R(SL, DN) 0, R(SM; C) = 0, R(SMs DN) 5, R(SH C) 5, and R(SH; DN) 10.
To define the probabilities in our model, we consider domain experts who define the transition and observation functions. For simplicity, we assume the experts all agree the effect of doing nothing on the progression of the population of birds. See the table in Figure 5 for the different transition and observation probabilities the experts claim, where Pan 1 (Por. PaM ) Jnn
1 - (4er + (sar), ), W = 1 (Way. + Was)). ) and O(sM, a, O1) = 21, Oss a, OH = 21 for E [C.DN].
Expert, believes that controlling the feral cats not very effective when the bird population is low, but becomes more effective as the bird population increases. Additionally, Expert, believes middle population level of the birds is just as likely to be interpreted as a high level and as a low level. Although Experte agrees with Expert controlling feral cats is most effective when the bird population is low, and becomes as effective as doing nothing as the bird population increases. Based on these two experts, this problem can naturally be modeled as a PO-MEMDP, since we only have multiple transition functions.
the observation probability, Expertz believes that
Another expert, Experty, agrees with Expert, on the effectiveness of controlling the feral cats but believes that a middle population level of birds is more likely to be interpreted as high than low. If we only have Expert, and Experts, this problem can naturally be modeled as MO-POMDP, since we only have multiple observation functions. If instead, we have all three experts, this problem should be modeled as ME-POMDP as we have both multiple transition and multiple observation functions.
31

---

Pon.
unk.
Expert
Expertz
Expertz
Post
Wost
Qai
Pet
0.6
0.2
0.6
Pam
0.35
0.6
0.35
0.8
Asp
C
Qs
0.1
0.1
0.1
MM
H
DN
0.1
Qam
0.5
0.75
0.5
Gast
Wal
0
0.05
0
0.8
DN
0.1
DN
0.8
Wast
0.1
0.15
0.1
0.155
0.15
21
0.5
0.5
0.4
0.05
00.0
Figure A visualisation of the Bird problem (left) with three experts (right). An action and corresponding transition distribution is represented by solid line labeled by the action to small node and dashed lines from the small node the successor states labeled by the transition probabilities.
C Detailed Benchmark Descriptions
C.1 Bird problem
We extend the endangered bird preservation example in Appendix B arbitrary ME-POMDPs, PO-MEMDPs, and MO-POMDPs. In particular, we parameterize the number of states |S| 2 2. actions |A], and experts n. Each problem has low and high population level state 87, 8f1 81 S. and all other states represent population levels ordered between low and high. Regardless of the action, s is always observed all other states are observed as either high or low populations with distinct observation probabilities. Each action can be taken from each state and transitions the same state and the two states with the closest population levels. In case of s,, these closest population levels are the two population levels above SL, and similar for 8y the two population levels below sμ. For all other states, the two closest population levels are the levels one above and one below the current state. We randomly define |A] probability distributions over min([S), 3) elements with each probability a multiple of 0.05. We order these |A| probability distributions inverse lexographically. meaning the probability distribution that assigns the most probability to the lowest state, i.e., the state representing the lowest population level, is first in the ordering. The first probability distribution is therefore considered the least effective, whereas the last is considered the most effective.
low population, sy is always observed as a high population, and
Each expert defines an ordering over the actions for each state. This ordering represents which action each expert considers the most effective. We randomly generate the orderings, ensuring that each expert has a different effectiveness ordering for at least one state. The probability distribution of an action in an environment hence given by the probability distribution corresponding to the effectiveness ranking the expert assigns to that action.
We also randomly generate, for each expert, |S|- probability distributions over the observations or, and oH, again with each probability a factor of 0.05. We order these probability distributions lexographically, so the first probability distribution gives the most probability og. Each observation probability distribution is then linked to the in-between population level states with the same rank in the ordering.
The reward for each vate-actionn pair is computed as the reward for the population level of the state minus the cost of the action. Each problem contains the do nothing action (DN) and | 1 other actions. The DN action free, all other actions add a reward of -5. The population level reward is i where is the rank of the population level.
Depending on the model type we want to generate, we generate one or n orderings over actions for each state and one observation probability distributions for J.S] - 2 states.
32

---

Agent
Figure 6: Visualization of relative fixed rock positions. Blue circles indicate the nearby positions, red circles the far away positions. The dashed circles are only considered with the three-rock version of the RockSample problem instances.
C.2 RockSample
The second problem is based on RockSample [40]. The RockSample problem consists of an m m grid with rocks at known positions. Each rock either good or bad, but the agent does not know the state of the rocks. The agent starts in the bottom left corner, cardinal directions and can exit the grid at the rightmost positions. When the same position as a rock, the agent can sample the rock. A good rock gives a reward of 10, and a bad rock reward of -10. After sampling a good rock, becomes bad. To learn the state rock, the agent can check a rock. The probability that this check action gives the agent the correct state depends the distance between the agent and the rock.
move through the grid in the
In the original RockSample problem, the agent starts with belief that each rock has 50% chance of being a good rock. We instead assume there are g good rocks and f. 9 bad rocks. We consider problem instances with randomly generated rock positions, well with relative fixed rock positions nearby or far away. For the RockSample instances with relative fixed positions, we consider either 2 or 3 rocks. The nearby rock positions are the three adjacent positions from the agent's 's starting positions, dropping the diagonal adjacent position for the two-rock version. The far-away rock positions the three corners that the agent does not start in, dropping the rock in the top right corner for the two-rock version. The far-away rock positions change with the grid size, and are therefore relatively fixed. See Figure for visualization of the relative fixed rock positions.
We can define our version of the RockSample problem either as an AB-POMDP or a ME-POMDP.
To model our version of RockSample as an AB-POMDP, we only need to replace the initial belief of the original problem by the set of states where g of the rocks are good and the agent is in the bottom left corner. We can simplify this model slightly by removing the unreachable states in which more than g rocks good.
To model our version of RockSample as a ME-POMDP, we can simplify the state space to only keep track of the good rocks instead of all t rocks. We then add (9) environments, i.e., environment for each combination of good rocks and bad rocks. The state space can be used to keep track of the state of each good rock, whereas the environment maps the good rock state Since the transition and observation functions depend on the state of each rock and therefore on the environment, need model this ME-POMDP. The initial state in each environment is the state where all good rocks are still good and the agent is in the bottom left corner.
actual rock.
D Experimental Details
Table shows the variation in convergence time and value for RockSample for environments with randomized rock positions. Table
similar trends to Table whereby we see a significant increase in convergence time as we increase the number of environments. However, due to random- ization of the rock positions in the instances, convergence time does not increase monotonically with the number of states, as can be seen by the convergence time decrease of instance RS compared to instance RS5.122
33

---

Table 4: Lower bound value, convergence time, and gap for various RockSample problems.
Table 5: Value and convergence time for RockSample problems modeled as AB- POMDPs and ME-POMDPs.
Properties
AB- HSVI
AB-POMDP
ME-POMDP
Model
[S|
A
Vest
Conv (s)
Gap
Model
Vet
Conv (s)
Veu
Conv (s)
RS
19
2
7
3
15.55
41.68
RSa.1.3
19
8
3
14.17
774.99
RS3,1,2
15.55
38.76
15.55
41.68
RSa.1.4
19
3
14.37
2840.85
RSa,1,3
14.37
878.39
14.17
774.99
RS3.1.5
19
10
3
10.94
5.16
RSa.1.4
14.63
3064.78
14.37
2840.85
RS3,2,3
37
8
3
22.56
891.43
RSa.2.3
22.92
1269.64
22.56
891.43
RS3.2.4
37
9
3
11.38
12.73
RS4,1.2
14.40
267.28
14.40
215.40
RSs,1,
13.51
1355.12
13.51
1252.50
RS4,1.2
7
14.40
215.40
<
RSa,1,2
14.09
949.19
14.09
1008.00
RSs.1.2
51
7
3
13.51
1252,50
6
RSa,1.2
73
2
7
3
14.09
1008.00
<
RS7.1.2
99
7
3
10.02
3,43
Table 6: The cost of robustness in RockSample. For each POMDP M,, we report the value VM; the time to solve all POMDPs, and the best and worst-case value under misspecified environment, which we denote by V and V, respectively, For the ME-POMDP we report the robust value V, the computation time, and the computation time factor.
Individual POMDPs
Incorrect
ME-POMDP
Model
M
V-
M
Time
V
V
V
Time
Factor
RSa.1.2
16,31
17.65
19.67
-0.84
-1.35
15.55
41.68
2.11
RSa.1.3
17.17
15.88
17.60
43.82
-0.41
-0.88
14.17
774.99
17.68
RS3,1,4
17.17
17.65
17.60
18.07
43.65
-0.45
-1.35
14.37
2840.85
65.09
RS3,2,3
26.22
25.81
23.75
163.61
9.07
5.70
22.56
891.43
5.49
RS4,1,2
16.76
15.09
100.22
-0.39
-1.29
14.40
215.40
2.15
RSa,1.2
15.13
14.78
258.66
-1.16
-1.51
13.51
1252.50
4.84
RSa,1,2
14.78
16.01
403.18
-1.51
-2.04
14.09
1008.00
2.50
Table 5 shows the variation in convergence time and value between modeling RockSample as an AB- 1B-POMDP or ME-POMDP,
explained in Appendix C for the Rocksample instances of Table
that converged within the time limit. Table [ contains the data that defines Figure 3 which we discuss in Section 6 In particular, note that in all but two models, the ME-POMDP formulation, which has multiple environments, converges faster the AB-POMDP formulation, which has a single environment. We hypothesize that this difference occurs because, in the ME-POMDP formulation, once an environment has a zero-probability, all beliefs in that environment can be ignored by single check, whereas in the AB-POMDP formulation all zero-probability environment-state combinations must be checked separately.
6 the value of solving ME-POMDP and the time required, compared to the naive baseline solving the individual POMDPs, i.e., the environments of the ME-POMDP, Note that Tableinconttins the data that defines Figure and Table which we discuss in Section 0 The robust value achieved by the ME-POMDP lies close to the optimal values each individual POMDP, and far outperforms both the best and worst-case value achieved by assuming incorrect environment as the true underlying environment, and playing the optimal policy accordingly. However, we also note that solving the ME-POMDP requires The factor with which the convergence time increases scales with the number of environments.
time than the of solving all individual POMDPs.
Table 7 compares the value and convergence time for the RockSample problem when we either place the rocks near or far from the agent's initial position. Table extendss Table with results for the case
when we have 2 good rocks, and these results corroborate the trends seen Section 6
We also depict the scaling of the solution times with the number of environments Figure for instances where the rocks are placed close to the agent's 's initial position.
34

---

Table 7: Lower bound value, time of convergence, and left-over gap between upper and lower bound of the RockSample problem for various problem sizes with rocks nearby or far away.
Properties
Rocks nearby
Rocks far away
Model
|S|
n
|A
Z
Veu
Conv (s)
Gap
Vea
Conv (s)
Gap
Factor
RSS 1,2
9
2
16.53
11.70
<
16.53
11.70
RS 3,1
19
2
7
16.14
52.74
< 14.68
169.95
3.22
RS
33
2
15.48
130.77
13.02
1588.97
12.15
R
2
15.40
331.37
<
11.03
1.46
RS
73
2
14.52
640.40
<6 6
RSS,12
99
2
7
14.54
1280.66
<6
RS
9
3
8
15,90
115.11
<6 15.90
115.11
6 2.73
RSS
19
3
8
15,41
269.10
<6 14.34
1072.32
3.98
RSS.1.3
33
3
8
15.14
787.82
<6 11.11
RSS,1.3
51
3
14.80
1793.75
8.15
5.34
RSS,133
73
3
14.31
2556.11
<6 2.25
RSS,1,3
99
3
8
13.30
RSL
17
3
22.59
443.88
<
22.59
443.88
< é
RS3,2,3
37
3
8
22.32
1105.12
<
19.50
3212.43
2.91
RSS,2,3
65
3
8
22.01
2389.88
<
13.15
6.64
5,2,3
101
3
16.56
7.29
4000
rocks, good
3 rocks, good
3000
3 rocks, good
Convergence time
2000
1000
0-
20
40
60
80
100
Number of states
Figure 7: Variation of convergence time with the number of states in the RockSample instances with fixed rock positions nearby.
35


Reviews:
[{"review_id": "tfm3yxpjSr", "reviewer": "Reviewer_aQSA", "summary": "This paper addresses the problem of robust planning in POMDPs under discrete model uncertainty, i.e., Multi-Environment POMDPs (ME-POMDPs), where the goal is to compute a single policy that maximizes the worst-case expected reward across a finite set of possible models. They make a theoretical contribution by introducing Adversarial-Belief POMDPs (AB-POMDPs), proving that ME-POMDPs can be reduced to this instance. Algorithmically, they propose the Adversarial-Belief Heuristic Search Value Iteration (AB-HSVI), which integrates linear programming into the popular HSVI point-based solver to adversarially select the belief for value function updates. The effectiveness and scalability of this approach are demonstrated through experiments on POMDP benchmarks.", "questions": "1. The scalability of AB-HSVI with respect to the number of environments n and the state-space size |S| appears to be the main bottleneck. While the current work provides a crucial theoretical and algorithmic foundation, have you considered any techniques to mitigate this for larger problems? For instance:\n- Could one potentially prune redundant or clearly dominated environments from the set before solving to reduce n?\n- Could the core idea of adversarial belief selection be integrated with more scalable online planning methods, such as POMCP, where a complete value function is not maintained?\n2. The paper focuses on a classic, point-based solver. The theoretical formulation of ME-POMDPs and AB-POMDPs, however, seems general and valuable. Do you see a path to applying these core ideas in settings where PWLC value functions are intractable? For example, could this be formulated as a two-player zero-sum game solvable with deep reinforcement learning methods, where one agent (the policy) plays against another (an adversary selecting the environment/belief)?\n3. The experimental results are reported on a single, randomly generated instance for each problem configuration. This makes it difficult to assess the general performance and variance of the algorithm. Could you comment on how representative you believe these single runs are? For the final version of the paper, I would encourage reporting results averaged over multiple random seeds (e.g., 5-10 runs per configuration), including standard deviations, to provide a more robust empirical validation.\n4. The paper provides a proof connecting AB-POMDPs to one-sided POSGs. Does this theoretical connection provide more than just a formal link? For instance, could specific insights or algorithms from the rich POSG literature be leveraged to develop alternative or more efficient solution methods for AB-POMDPs in the future?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper addresses a well-defined and practically important problem. The assumption that exact model parameters for a POMDP are known is often a bottleneck for real-world applications. The ME-POMDP formulation is an intuitive and relevant model for handling discrete model uncertainty, and the paper's focus on robust, worst-case optimization is appropriate for high-stakes decision-making.\n2. The paper presents theoretical analysis. The introduction of AB-POMDPs as a unifying framework looks sound. The theorems that formally establish reductions and equivalences between ME-POMDPs, AB-POMDPs, and one-sided POSGs (Theorems 1-4) can be a good contribution.\n3. The proposed AB-HSVI is a technically sound approximate solution method, which builds upon the foundation of HSVI, a popular and effective POMDP algorithm. The integration of a linear program to find the worst-case belief is a direct and elegant way to handle the adversarial nature of the problem within the value iteration framework.\n\n\nWeaknesses\n1. While the experiments analyze scalability, they also confirm that it is a primary limitation. The computational time increases significantly with the number of environments or the problem size. For problems with large state/action space or a large number of potential environments, the current approach may be intractable.\n2. The proposed method is rooted in traditional POMDP solvers that rely on maintaining an explicit PWLC value function (a set of alpha-vectors). This representation can become a bottleneck in POMDPs with very large state or observation spaces, which is where modern deep reinforcement learning methods are often applied. The paper does not discuss how these ideas might be extended to work with nonlinear function approximators (e.g., neural networks), or online planing (e.g., POMCP), which limits its applicability to problems outside the scope of classic point-based solvers.\n3. They correctly note in the checklist that their algorithm is deterministic. However, the problem instances themselves are generated via randomization. The empirical results would be stronger if, for each configuration (e.g., RS_3,1,3), the authors had generated a small number of random instances (e.g., 5-10) and reported the mean and standard deviation of the results. This would provide a better sense of the method's performance consistency across different models of the same size, rather than just on a single random instance.", "was_revised": true, "final_justification": "I have read other reviews and rebuttals, I think most of my concerns are addressed.", "rebuttal": "We would like to thank the reviewer for their helpful comments, suggestions, and questions.\nBased on those, we plan to make the following changes to our paper:\n- Add details on optimization techniques for AB-HSVI.\n- Clarify the use of randomization to find non-trivial benchmarks and include the additional experimental results discussed below to further highlight the effects of specific models on runtime.\n- Incorporate all other suggestions and directions for future work.\n\nWe now answer the questions.\n\n> Q1. *Have you considered any techniques to mitigate the bottleneck of the number of environments and the state-space size in AB-HSVI for larger problems?*\n\nWe implement two optimization techniques already: sparse representations for vectors and matrices, and pruning of $\\alpha$-vectors.\nWe use sparse matrices to represent the beliefs and $\\alpha$-vectors.\nThis optimization is most effective when, during execution, we can infer that a certain environment is impossible. \nFor example, a transition may be observed while not being possible in one of the environments, in which an entire part of the matrix will remain zero for the rest of the exploration.\nA sparse representation avoids explicitly storing that part of the matrix.\nAnother optimization we implement in AB-HSVI is the pruning of $\\alpha$-vectors that are dominated by a single other $\\alpha$-vector.\nUsing additional pruning methods could improve the efficiency of the algorithm.\nAdditional directions to improve AB-HSVI's scalability include keeping track of and reusing previously explored beliefs, and the use of compact representation techniques for the state space, such as Value-directed Compression (VDC) [1].\n\nWe will add details on the optimization techniques already used, as well as the additional directions for further optimization, to the paper.\n\n> Q1a. *Could one prune redundant or clearly dominated environments from the set before solving?*\n\nPruning environments before solving can be done when an environment is a submodel of another environment.\nExamples of situations where such pruning can be performed are:\n- When the transition and observation functions are the same, but one of the reward functions has larger rewards at every state-action pair.\n- When one environment has a sink state, while another environment can continue to accumulate reward.\n\nWe did not consider such optimizations in the current work, and thank the reviewer for the interesting suggestion for future improvement.\n\n\n> Q1b. *Could the core idea of adversarial belief be integrated with more scalable online planning methods, such as POMCP?*\n\nA key requirement in online planning methods such as POMCP is that there is a model to simulate. \nIn multi-environment POMDPs, it is unclear which environment to simulate, and we need to either choose a POMDP to sample from or assume a distribution over these POMDPs.\nIf we were to select an initial environment distribution to sample from and update the distribution along the way, we are changing the environment we are sampling from, essentially breaking the assumption that the environment is fixed once nature chooses it.\n\nOne promising direction, however, comes from the recent work on online planning methods for POSGs [2], which, in combination with our ME-POMDP to POSG reduction, suggests that we could explore the use of adversarial beliefs in POMCP.\n\n\n> Q2. *Do you see a path to applying the core ideas of ME-POMDPs and AB-POMDPs in settings where PWLC value functions are intractable?*\n\n\nIn this work, we solve multi-environment POMDPs by constructing piecewise linear convex value functions, and we attempt to lessen the computational burden by providing point-based approximation methods.\n\nHowever, we acknowledge that even these methods are intractable for large mere POMDPs already, and that there are indeed interesting directions for the future.\nOne possible approach to lessen the computational burden is to use policy-gradient methods in a game setting [3,4].\nSuch methods could prove interesting both from a computational efficiency perspective and a theoretical perspective.\n\n> Q3. *Could you comment on how representative you believe the single runs on the randomly generated instances for each problem configuration are?*\n\n\n**In summary:**\nNo benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial.\nNevertheless, we provide additional experiments on variations of the RockSample problem.\n\nFirst, we would like to note that there are no existing benchmarks for ME-POMDPs.\nRemoving the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial.\nFor example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. \nThe environment where all rocks are bad is trivially the worst-case environment.\n\nTo create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization.\nWe only use this approach to substitute for the hand-design of models, and thus our experiments are comparable to standard POMDP experiments, where one also evaluates a single instance of each problem (see, for instance, [5], where RockSample was introduced and also used in multiple separate configurations).\n\nCreating challenging problem instances is difficult.\nFor example, for the Bird problems with $3$ states, $3$ actions, and $3$ experts, generating models with random seeds $0$ to $99$, we only got $35$ out of $100$ non-trivial PO-MEMDPs, $34$ non-trivial ME-POMDPs, and only $16$ non-trivial MO-POMDPS.\nFor this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.\n\nEven though we can generate multiple non-trivial variants of a problem instance, the values and running times are highly dependent on the environments, and these variants are therefore better considered as distinct problems rather than variants that we should compare.\nTo demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks.\nThe number of states, actions, and environments is fixed across the instances.\nThe running time between two such variants of a problem instance varied by factors between $3$ and $10$, and we expect this gap to further increase with a larger state space.\n\nWe will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.\n\n\n> Q4. *Could specific insights or algorithms from the rich POSG literature be leveraged to develop alternative or more efficient solution methods for AB-POMDPs in the future?*\n\nAB-HSVI uses classical $\\alpha$-vector techniques,  and could be considered a specialized ME-POMDP analogue to the HSVI-type algorithms used in POSG papers such as [6].\nWe expect that other POSG methods can be adapted to the multi-environment setting, and we believe these adaptations to be an interesting avenue for future work.\nIn particular, various works study the problem of reinforcement learning for partially-observable Markov games [7,8,9], which would be interesting to explore in the special case of ME-POMDPs.\nSimilarly, as discussed for Q1b, recent work establishes online planning algorithms for POSGs, and it would be interesting to explore simplifications of these methods for ME-POMDPs.\n\n#### References\n\n[1] Pascal Poupart, Craig Boutilier: Value-Directed Compression of POMDPs. NIPS 2002\n\n[2] Tyler J. Becker, Zachary Sunberg: Bridging the Gap between Partially Observable Stochastic Games and Sparse POMDP Methods. AAMAS 2025\n\n[3] Maris F. L. Galesloot, Roman Andriushchenko, Milan Ceska, Sebastian Junges, Nils Jansen: rfPG: Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs. arXiv preprint arXiv:2505.09518 (2025)\n\n[4] Constantinos Daskalakis, Dylan J. Foster, Noah Golowich: Independent Policy Gradient Methods for Competitive Reinforcement Learning. NeurIPS 2020\n\n[5] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004\n\n[6] Karel Horák, Branislav Bosanský, Vojtech Kovarík, Christopher Kiekintveld: Solving zero-sum one-sided partially observable stochastic games. Artif. Intell. 316: 103838 (2023)\n\n[7] Qinghua Liu, Csaba Szepesvári, Chi Jin: Sample-Efficient Reinforcement Learning of Partially Observable Markov Games. NeurIPS 2022\n\n[8] Awni Altabaa, Zhuoran Yang: On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games. NeurIPS 2024\n \n[9] Xiangyu Liu, Kaiqing Zhang: Partially Observable Multi-agent RL with (Quasi-)Efficiency: The Blessing of Information Sharing. ICML 2023"}, {"review_id": "p6WuFB5a9I", "reviewer": "Reviewer_g1P2", "summary": "This paper is about multi-environment POMDPs (ME-POMDPs), a version of POMDPs, in which the transition model, observation model or reward function is uncertain, in that there are a finite number of possible models. It is concerned with the setting without prior knowledge about which environment is active and tries to find policies that maximize the value in the worst case. This is achieved using an algorithm that transforms ME-POMDPs into so-called adversarial-belief POMDPs (AB-POMDPs) and solves the resulting AB-POMDPs using linear programming. The algorithm is evaluated on two benchmarks and compared to a baseline that solves the individual POMDP models without taking robustness into account.", "questions": "- Can't we write any ME-POMDP as a single POMDP, which includes an unobserved discrete variable indicating the true model, which does not change during an episode? If that is the case: What makes the current approach more efficient than the naive approach of solving that POMDP directly? And why was the naive approach not considered as a baseline?\n- I understood the solution technique is to turn an ME-POMDP into an AB-POMDP and then solve that using AB-HSVI. If that is the case, then how do I interpret the comparison in Table 3 between ME-POMDPs and AB-POMDPs, both solved with AB-HSVI?\n- In a POSG, why does the fully observing player's policy take the history of states, both players actions and observations as the input?\n- In response to checklist item 7 (statistical significance), the authors state \"The algorithm is deterministic. It does not use any randomization during runtime, and hence will produce the same result upon running it twice. Note, we do use randomization to generate the models that we run our algorithm on, but then the models are fixed.\" This argument is not convincing to me. Wouldn't we still want to know if the algorithm performs well on some distribution of models rather than on a single randomly generated model?", "limitations": "The paper does not discuss any limitations or potential societal impacts. In my opinion, a discussion of societal impacts is not necessary for this kind of basic theoretical research, but a discussion of limitations would be appreciated to put the approach into context.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I appreciate that the authors have tried to present very technically dense material in a readable fashion. I found the introduction well-written and it seems to cover relevant related work. The section on POMDPs and alpha vectors provides useful background for readers not familiar with these concepts. However, after the introduction, the paper often feels less clear and I was at times confused about some points that seem quite central to the paper (see questions below), concerning both the results and the method. Furthermore, the paper lacks visualizations, intuitive explanations, or defnitions of some of the notation. For these reason, the rest of my review consists mostly of suggestions for how the paper could be made clearer and more accessible and of clarification questions.\n\n1. The paper contains no figures at all. This is in some sense understandable for a theory paper, but I think the authors miss a few opportunities to present their work in a more accessible fashion. For example, the results would be more easily digestible if they were shown using a few clear figures instead of a whole page of tables. Also, a graphic illustrating the relationship between ME-POMDPs, PO-MEMDPs, MO-POMDPs and AB-POMDPs would be highly appreciated, as it was easy to lose track of how the concepts fit together.\n2. I did not check the proofs in detail, as that is outside my area of expertise, but it seems to me that the theorems in Section 4 and 5 could benefit from some more intuitive descriptions. Before or after going into mathematical jargon, it would be nice to provide some intuition about what is actually being stated in natural language. \n3. Symbols or equations are sometimes used before being properly defined or introduced. I will give a few examples, but this is not an exhaustive list. In Theorem 1, some of the symbols are not explained (e.g. ⊥, ⊤). On page 7, $y$ is used before being defined. The linear programs (3) and (4) are already referenced in Section 5.1, but are defined only Section 5.2, which in turn refers to \"the LPs of Section 5.1\".\n4. The discussion of the results is very sparse and not easy to follow. See also my questions below.\n    a. Section \"Q1. Scalability.\" offers no discussion of the three different times of models (PO-MEMDP, MO-POMDP, and ME-POMDP).\n    b. Statements like \"the randomly generated environments have a great effect on the difficulty of the problems\" would benefit from concrete pointers to numbers particular tables.\n\nMinor points:\n- The notation (A x Z)* for the history of states and observations makes sense but could be made more explicit that that is what is means, because in other contexts the authors use the star to indicate an optimal policy.\n- Ordering the references by occurence would make for easier reading", "was_revised": true, "final_justification": "I appreciate the detailed responses by the authors to all of my questions and the outline for how the authors plan to improve the papers readability. The authors' explanation that there are no existing benchmarks for the multi-model POMDP setting was convincing to me and I think this paper will be a valuable contribution to the literature, which is why I have increased my score by one point. I would like to point out that I was not able to verify any of the proofs, and I have therefore kept my rather low confidence rating.", "rebuttal": "We would like to thank the reviewer for their helpful comments, suggestions, and questions.\nBased on those, we plan to make the following changes to our paper:\n- Clarify the results presented in Table 3.\n- Clarify the use of randomization to find non-trivial benchmarks and include additional experimental results to further highlight the effects of specific models on runtime.\n- Incorporate all other suggestions and directions for future work, paying particular attention to accessibility and readability. We will also highlight the limitations.\n\nWe first clarify the meaning of the indicated symbols:\n- $\\bot$ and $\\top$ are fresh symbols used throughout model definitions to denote auxiliary states/observations.\n- $y$ is used to indicate a solution to the dual linear program.\n\nWe will clarify these symbols in the final version of the paper.\n\nNext, we answer the questions.\n\n> Q1 *Can't we write any ME-POMDP as a single POMDP with an unobserved and discrete variable indicating the true environment? If so, what makes the current approach more efficient than solving that POMDP directly? And why was this naive approach not considered as a baseline?*\n\nSolving a ME-POMDP via a larger POMDP does not lead to robust policies.\nWhen we write a ME-POMDP $M$ as a larger POMDP $M'$, we must define an initial distribution (initial belief) in this larger POMDP $M'$.\nBy defining this initial distribution, we define an initial distribution over the environments, and a policy found for this initial distribution will not be robust to other initial distributions.\n\nA simple way to show that an ME-POMDP is not equivalent to a larger POMDP is by noting that deterministic policies are optimal for finite-horizon POMDPs, but **not** for finite-horizon ME-POMDPs. \nIndeed, we can encode zero-sum matrix games via ME-POMDPs.\nWe provide an example of this encoding in Proposition 1 of the paper, which is available in the supplementary material. \nWe note that for this PO-MEMDP (which is, in turn, a ME-POMDP), the optimal strategy is randomized.\nWe also note that when we do not specify an initial belief for the POMDP, we obtain an AB-POMDP.\nWe explore that approach to solving ME-POMDPs in Table 3.\n\n\n> Q2. *What does the comparison in Table 3 between ME-POMDPs and AB-POMDPs, both solved with AB-HSVI, entail?*\n\nThe results in Table 3 are to compare the naive implementation as suggested in your other question.\nWhen we transform the ME-POMDP into an explicit POMDP with an unknown initial belief, we can run our AB-HSVI algorithm with a single environment, but it will always have to take the entire state space into account.\nWhen, instead, we keep the multiple environments, parts of the state space can be discarded once that environment has a probability of zero, leading to a more efficient computation.\nWe will clarify the rationale behind the comparison in Table 3 in the paper.\n\n\n> Q3. *In a POSG, why does the fully observing player's policy take the history of states, both players' actions, and observations as the input?*\n\nRegarding the inputs to the fully-observing players' inputs, we note that this assumption is standard for one-sided POSGS [1].\nHowever, we note that, in our reductions, the fully-observing player only acts at the initial dummy state. Thus, their strategy does not rely on their observing actions, observations, or states.\n\n\n\n> Q4. *Wouldn't we still want to know if the algorithm performs well on some distribution of models rather than on a single randomly generated model?*\n\n*Note: This is the same answer as we give to Reviewer 1 (aQSA) Q3, which we repeat here for readability.*\n\n**In summary:**\nNo benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial.\nNevertheless, we provide additional experiments on variations of the RockSample problem.\n\nFirst, we would like to note that there are no existing benchmarks for ME-POMDPs.\nRemoving the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial.\nFor example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. \nThe environment where all rocks are bad is trivially the worst-case environment.\n\nTo create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization.\nWe only use this approach to substitute for the hand-design of models, and thus our experiments are comparable to standard POMDP experiments, where one also evaluates a single instance of each problem (see, for instance, [2], where RockSample was introduced and also used in multiple separate configurations).\n\nCreating challenging problem instances is difficult.\nFor example, for the Bird problems with $3$ states, $3$ actions, and $3$ experts, generating models with random seeds $0$ to $99$, we only got $35$ out of $100$ non-trivial PO-MEMDPs, $34$ non-trivial ME-POMDPs, and only $16$ non-trivial MO-POMDPS.\nFor this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.\n\nEven though we can generate multiple non-trivial variants of a problem instance, the values and running times are highly dependent on the environments, and these variants are therefore better considered as distinct problems rather than variants that we should compare.\nTo demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks.\nThe number of states, actions, and environments is fixed across the instances.\nThe running time between two such variants of a problem instance varied by factors between $3$ and $10$, and we expect this gap to further increase with a larger state space.\n\nWe will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.\n\n\n#### References\n\n[1] Karel Horák, Branislav Bosanský, Vojtech Kovarík, Christopher Kiekintveld: Solving zero-sum one-sided partially observable stochastic games. Artif. Intell. 316: 103838 (2023)\n\n[2] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004"}, {"review_id": "5osWPCJfkj", "reviewer": "Reviewer_sP8H", "summary": "This paper addresses robust policy planning in ME-POMDPs, where multiple POMDPs defined over the same state, action, and observation spaces differ in their dynamics and reward functions. The authors extend the theoretical framework by introducing AB-POMDPs, which generalize ME-POMDPs by allowing the initial belief to be adversarially selected from a set. The main theoretical contribution is showing that any ME-POMDP can be efficiently reduced to an AB-POMDP, and both can be formulated as special cases of one-sided POSGs. The paper develops both exact and approximate (point-based) algorithms for robust policy computation, notably extending HSVI with linear programming to handle adversarial initial beliefs.", "questions": "1. The experimental tables show that convergence time can grow rapidly with the number of environments and problem size, sometimes resulting in incomplete runs. Can the authors provide theoretical or empirical guidance on the expected runtime as a function of the number of environments, states, and actions?\n2. How well does the approach scale as the state, action, or environment space increases?\n3. How do the proposed algorithms perform empirically compared to robust POMDP methods that use continuous or convex uncertainty sets, or alternative robust optimization frameworks?\n4. On line 19, the equation \"$H+1=H$\" requires clarification. On line 99, the superscript $\\star$ is not defined.", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**: This paper demonstrates notable theoretical depth and clarity by providing a rigorous formalization of ME-POMDPs and AB-POMDPs, including precise definitions, clear reductions, and systematic connections to POSGs. The foundational theoretical results are well-motivated, and the approach of reducing robust planning problems to standard constructs such as POSGs and restricted POMDP variants enables both conceptual clarity and algorithmic leverage.\n\n**Weaknesses**\n1. The paper does not provide a theoretical analysis of time or space complexity with respect to key parameters (e.g., state/action space size, number of environments, planning horizon).\n2. Results are reported on randomly generated environments without variance, error bars, or confidence intervals, limiting the interpretation of empirical robustness.\n3. There is no in-depth discussion of how randomness in benchmark generation may affect results, nor is there a systematic exploration of whether variations between random seeds could lead to significantly different conclusions.", "was_revised": true, "final_justification": "Based on the experimental results supplemented by the authors, I believe this paper has the potential to be accepted. However, since my research focuses more on theoretical results, my confidence level is 1, so as not to overly influence the final decision.", "rebuttal": "We would like to thank the reviewer for their helpful comments, suggestions, and questions.\nBased on those, we plan to make the following changes to our paper:\n- Clarify the use of randomization to find non-trivial benchmarks and include additional experimental results to further highlight the effects of specific model instances on runtime.\n- Include new experimental results to provide more empirical guidance on expected runtimes in terms of model size.\n- Incorporate all other suggestions and directions for future work.\n\nWe first address the weaknesses that do not have a corresponding question.\n\n> W2/W3. *Results are reported on randomly generated environments without variance, error bars, or confidence intervals, limiting the interpretation of empirical robustness. \nThere is no in-depth discussion of how randomness in benchmark generation may affect results.*\n\n\n*Note: This is the same answer as we give to Reviewer 1 (aQSA) Q3, which we repeat here for readability.*\n\n**In summary:**\nNo benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial.\nNevertheless, we provide additional experiments on variations of the RockSample problem.\n\nFirst, we would like to note that there are no existing benchmarks for ME-POMDPs.\nRemoving the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial.\nFor example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. \nThe environment where all rocks are bad is trivially the worst-case environment.\n\nTo create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization.\nWe only use this approach to substitute for the hand-design of models, and thus our experiments are comparable to standard POMDP experiments, where one also evaluates a single instance of each problem (see, for instance, [1], where RockSample was introduced and also used in multiple separate configurations).\n\nCreating challenging problem instances is difficult.\nFor example, for the Bird problems with $3$ states, $3$ actions, and $3$ experts, generating models with random seeds $0$ to $99$, we only got $35$ out of $100$ non-trivial PO-MEMDPs, $34$ non-trivial ME-POMDPs, and only $16$ non-trivial MO-POMDPS.\nFor this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.\n\nEven though we can generate multiple non-trivial variants of a problem instance, the values and running times are highly dependent on the environments, and these variants are therefore better considered as distinct problems rather than variants that we should compare.\nTo demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks.\nThe number of states, actions, and environments is fixed across the instances.\nThe running time between two such variants of a problem instance varied by factors between $3$ and $10$, and we expect this gap to further increase with a larger state space.\n\nWe will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.\n\n\nNext, we answer the questions.\n\n> Q1/Q2. *Can the authors provide theoretical or empirical guidance on the expected runtime as a function of the number of environments, states, and actions? \nHow well does the approach scale as the state, action, or environment space increases?*\n\nWe first note that, from a theoretical perspective, we can guarantee little, as ME-POMDPs already contain POMDPs as a special case, and finding optimal policies that maximize the expected discounted reward is undecidable for POMDPs [2]. \nFor finite-horizon reward maximization, the problem is at least PSPACE-hard [3], but the exact theoretical complexity of solving ME-POMDPs is still open.\n\nAlthough Tables 1 and 2 are intended to give empirical guidance on the influence of increased state, action, and environment spaces, we also acknowledge that this guidance is limited due to the strong influence of the different environments.\nTo improve the empirical guidance, we ran additional experiments on RockSample instances where the relative position of the rocks is fixed either near or far from the agent's starting position.\nWe conducted multiple experiments with these fixed rock positions, varying the number of rocks, the number of good rocks, and the grid size.\nWith these experiments, we will improve the empirical guidance for:\n1. The influence of only increasing the state space while keeping similar environments.\n2. The influence of different environments with the same state, action, and number of environments.\n\nFor 1., we see that the increase in computation time still depends on the type of consistent environments.\nFor example, when we have only two rocks that are placed adjacent to the agent's starting position, we see a runtime increase factor between $2$ and $3$ per grid size increase.\nOn the other hand, when we have three rocks that are placed in the corners of the grid, we see a runtime increase factor of about $10$.\n\nFor 2. (as also stated in our response to W2/3), we observe that two variants of a problem instance differing only in their environments exhibit a running time variation of a factor between 3 and 10. We expect this gap to widen further with an increase in the state space.\nWe will include these additional experiments and discussion in the final version of the paper.\n\n> Q3. *How do the proposed algorithms perform empirically compared to robust POMDP methods that use continuous or convex uncertainty sets, or alternative robust optimization frameworks?*\n\nThe only available robust POMDP solvers assume $(s,a)$-rectangularity, which is an independence assumption between the uncertainty of different state-action pairs.\nThis is a property that the general multi-environment problems that we consider do not have.\nConsequently, none of the problems we evaluate on are $(s,a)$-rectangular.\nMaking a non-rectangular model $(s,a)$-rectangular would give the adversary significantly more power, as it can choose a separate worst-case distribution for each state-action pair.\nThe computed optimal agent policy will then also be significantly more conservative than necessary for the multi-environment problem.\nThis makes a comparison with robust POMDP solvers ineffective.\n\nWe further remark that assuming $(s,a)$-rectangularity does not make the problem necessarily easier to solve.\nIn [4], robust optimization is employed to solve robust POMDPs, but due to the non-convexity of the underlying optimization problem, iterative approximations are required.\n\n> Q4. *On line 19, the equation $H + 1 = H$ requires clarification. On line 99, the superscript \\* is not defined.*\n\n- Line 93 indicates that $H + 1 = \\infty$, as in this case, $H = \\infty$.\n- For a finite set $X$, we denote by $X^\\*$ the set of finite sequences of elements from $X$.\nThat is, $\\*$ indicates the Kleene-star operator.  \n\nWe will add these corrections and clarifications to the paper.\n\n\n#### References\n\n[1] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004\n\n[2] Omid Madani, Steve Hanks, Anne Condon:\nOn the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems. AAAI/IAAI 1999\n\n[3] Christos H. Papadimitriou, John N. Tsitsiklis: The Complexity of Markov Decision Processes. Math. Oper. Res. 12(3): 441-450 (1987)\n\n[4] Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, Ufuk Topcu:\nRobust Finite-State Controllers for Uncertain POMDPs. AAAI 2021"}, {"review_id": "teZBLivGV9", "reviewer": "Reviewer_xCNX", "summary": "This paper addresses finding a robust policy when there are a finite different models for a POMDP, where each model can have different transition, observation, and reward models. To solve this, they are optimizing for the policy that maximizes the expected value of the worst-case model. They show that solving this problem is equivalent to playing a partially observable adversarial game where the fully observable agent’s policy is to minimize the performance of the partially observable agent by selecting the model. They also provide a process of converting the set of models into a Multi-Environment POMDP, where the set of models is encoded into the problem and belief state. As such, the adversarial agent is selecting a belief state. They introduce an algorithm, Adversarial-Belief HSVI, for solving for the robust policy and evaluate this algorithm on two different domains.", "questions": "1.\tDo you have a proof or empirical evaluation for showing that AB-HSVI converges over time?\n2.\tHave you evaluated any other problems or done additional evaluation on the computation cost of changing the individual factors?", "limitations": "The main limitations are discussed; however, having a limitation section would be beneficial.", "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\n* The main contribution of this paper is the framework and theoretical results that are clear and sound, to the best of my knowledge.\n* The paper clearly distinguishes itself from the existing work on robust policies, providing a convincing argument on its novelty.\n* The methodology of the empirical evaluation is clear and reproducible. \n\n**Weaknesses:**\n\n* The paper currently does not have a proof or empirical evaluation showing that the AB-HSVI algorithm converges. It is clear that it does, just that explicitly including it would strengthen the paper.\n* While the empirical evaluation effectively shows the behavior of the AB-HSVI algorithm and solving for the robust policy using the ME-POMDP, it is hard to say when solving for the robust policy is feasible.\n* It would have been nice if a more substantial ablation study had been performed to evaluate the approximate computational complexity of the individual variables (number of experts, amount of disagreement between the models, etc.) \n\n**Other Comments:**\n\n* One assumption that I think needs to be mentioned is that the reward function needs to use the same units between models. Otherwise, comparing the expected value between the models is not a meaningful metric. For example, an expert could increase the survival cost in Rocksample such that their model dominates the set of models, causing the robust policy to have the agent exit as fast as possible.\n* The performance and the magnitude of the differences between the models would impact the quality of the robust policy. For example, if the POMDP encodes a multi-objective problem where experts disagree on the objective, the robust policy is unlikely to achieve either objective.\n* Table 4’s comparison of the robust policy compared to the optimal policy for each individual model is interesting but causes more confusion than benefits for the main paper. Since the robust policy solves a different problem, the only conclusion that can be drawn is that solving the optimal policy for an individual model will outperform the robust policy. Rather, it creates more confusion, suggesting that the robust policy is somehow one of these optimal policies.", "was_revised": true, "final_justification": "The authors have addressed all questions and concerns raised by me and the other reviewers. To the best of my knowledge, the presented theory is sound. While additional theoretical analysis of their algorithm would further strengthen the work, the authors acknowledge the main weakness of their approach (computational cost) and have addressed it with sufficient empirical evaluation. Their empirical results are solid, and the additional experiments being added will provide valuable insight into their approach. Overall, this paper makes a meaningful contribution to the literature and would be a valuable addition to the conference.", "rebuttal": "We would like to thank the reviewer for their helpful comments, suggestions, and questions.\nBased on those, we plan to make the following changes to our paper:\n- Include a more detailed discussion on the effects of assumptions made on the reward function.\n- Clarify the rationale behind Table 4 in the experimental evaluation.\n- Include new experimental results to provide more empirical guidance on expected runtimes in terms of model size.\n- Incorporate all other suggestions and directions for future work.\n\nWe first address the comments.\n\n> C1. *One assumption that I think needs to be mentioned is that the reward function needs to use the same units between models.*\n\nWe acknowledge that scaling in the reward functions of different experts/models is an interesting problem. \nFor example, one could design multi-environment POMDP solvers that extract the qualitative behavior from different environments without being affected by the rewards.\nWhile such scaling problems may also be seen as a modeling problem, we will make sure that we add a discussion of this assumption to the paper.\n\n\n> C2. *The performance and the magnitude of the differences between the models would impact the quality of the robust policy. For example, if the POMDP encodes a multi-objective problem where experts disagree on the objective, the robust policy is unlikely to achieve either objective.*\n\nWe agree that the quality of the robust policy depends on the differences between the environments.\nIf environments differ a lot, the robust policy will be more conservative than if environments are more similar.\n\nAlthough our approach works for environments with completely contradicting reward functions, our goal is always to find a robust policy with respect to these reward functions, which does not require satisfying different objectives in different environments.\nSuch multi-objective problems are nonetheless an interesting and relevant direction for future work.\n\n\n\n\n\n> C3. *Table 4’s comparison of the robust policy compared to the optimal policy for each individual model creates confusion, suggesting that the robust policy is somehow one of these optimal policies.*\n\n\nWe understand the confusion highlighted by the reviewer and thank them for bringing this issue to our attention.\nWe believe the comparison in Table 4 is important to give insight into the computational cost of being robust versus the potential loss of value of naive approaches, such as using a policy that is optimal for one of the environments without taking the other environments into account.\nWe will clarify the rationale behind Table 4 and the values compared in the table.\n\n\n\nNext, we answer the questions.\n\n> Q1. *Do you have a proof or empirical evaluation for showing that AB-HSVI converges over time?*\n\n\n\n**In summary:** We believe that there are promising directions for proving convergence using similar methods as for partially observable stochastic games.\n\nStandard HSVI convergence proofs fail in our setting because they rely on a constant initial belief, whereas we change the initial belief throughout AB-HSVI. We believe that it will be sufficient to prove a form of a uniform convergence result for the value-function upper and lower bounds to show that we have convergence at all initial belief points.\n\nTo prove the convergence of HSVI in a POSG setting, the authors of [1] augmented the standard HSVI approximation algorithm. \nThe first augmentation is a new upper bound with Lipschitz continuity.\nThe second augmentation is a modified convergence condition for the forward belief search.\nThese modifications facilitate a proof that, informally, convergence of HSVI at a point implies convergence in a neighborhood of that point.\n\nWe believe that applying these modifications to AB-HSVI provides a promising path to show uniform convergence of the value function in AB-HSVI.\n\n\n> Q2. *Have you evaluated any other problems or done additional evaluation on the computation cost of changing the individual factors?*\n\n\n*Note: This is a similar answer to the one we give to Reviewer 3 (sP8H) Q1 and Q2, which we repeat here for readability.*\n\nTables 1 and 2 provide empirical guidance on the influence of increased state, action, and environment spaces, but we also acknowledge that this guidance is limited due to the strong influence of the different environments.\nTo improve the empirical guidance, we ran additional experiments on RockSample instances where the relative position of the rocks is fixed either near or far from the agent's starting position.\nWe conducted multiple experiments with these fixed rock positions, varying the number of rocks, the number of good rocks, and the grid size.\nWith these experiments, we will improve the empirical guidance for:\n1. The influence of only increasing the state space while keeping similar environments.\n2. The influence of different environments with the same state, action, and number of environments.\n\nFor 1., we see that the increase in computation time still depends on the type of consistent environments.\nFor example, when we have only two rocks that are placed adjacent to the agent's starting position, we see a runtime increase factor between $2$ and $3$ per grid size increase.\nOn the other hand, when we have three rocks that are placed in the corners of the grid, we see a runtime increase factor of about $10$.\n\nFor 2., we observe that two variants of a problem instance differing only in their environments exhibit a running time variation of a factor between 3 and 10. We expect this gap to widen further with an increase in the state space.\nWe will include these additional experiments and discussion in the final version of the paper.\n\n#### References\n\n[1] Karel Horák, Branislav Bosanský, Vojtech Kovarík, Christopher Kiekintveld: Solving zero-sum one-sided partially observable stochastic games. Artif. Intell. 316: 103838 (2023)"}]

Author rebuttal:

Meta-review: All reviews of this work leaned towards acceptance, with two recommendations to accept [g1P2,xCNX] and two recommendations for borderline acceptance [aQSA,sP8H].

Reviewers appreciated the work along several aspects:

+ The problem was considered well-defined and practically important and a known bottleneck for real-world applications [aQSA]
+ The approach was considered to have a convincing argument for novelty [xCNX]
+ The method formulation was considered intuitive and relevant for handling discrete model uncertainty [aQSA]
+ The solution method was considered clear [xCNX] and technically sound [aQSA,xCNX] and well motivated [sP8H] and the theoretical depth was appreciated [sP8H]
+ The focus on robust worst-case optimisation was appreciated [aQSA]
+ The theoretical analysis was considered sound [aQSA]
+ The empirical evaluation metholdology was considered clear and reproducible [xCNX]

A number of concerns were raised in the reviews, including computational complexity and impact of the randomly generated problems, which the authors responded to in the rebuttals:

- Computation time and intractability for large state/action spaces or numerous potential environments was a concern [aQSA]; similarly, theoretical analysis of time or space complexity was desired [sP8H], and discussion of computation cost of changing individual factors [xCNX]; authors did not provide a full analysis but provided some discussion and commented on runtime in a RockSample environment
- Proof or empirical evaluations showing the algorithm converges was desired [xCNX]; authors did not provide a proof but gave discussion of a path towards showing it.
- Feasibility of solving for the robust policy was considered unclear [xCNX]
- A more substantial ablation study was desired [xCNX]
- Maintaining an explicit PWLC value function representation was considered a bottleneck, and discussion of extending to nonlinear function approximations was desired [aQSA]
- Reporting of means and standard deviations across randomly generated problems was desired [aQSA,Sp8H], and similarly, performance on a distribution of models was desired [g1P2], and discussion of how randomness in benchmark generation may affect results was desired [sP8H]; authors argued the randomisation is nontrivial and results should be treated as distinct problems.
- Mitigation of the scalability bottleneck by pruning or online planning methods was raised as a possibility [aQSA]; authors provided some discussion on optimisation techniques already used, considered some pruning approaches future work, and discussed obstacles and possibilities of online planning.
- Applying the core ideas in settings where PWLC value functions are intractable was raised [aQSA]; authors commented on this as a direction of future work.
- Performance versus robust POMDPs involving continuous or convex uncertainty sets was questioned [sP8H]; authors commented available robust POMDP solvers would need a rectangularity assumption not available in the authors' problems making such solvers ineffective.
- A question of further impact of the theoretical connections between AB-POMDPs and one-sides POSGs was raised [aQSA]; authors considered this future work.
- Questions were raised on whether one could use a naive approach solving a POMDP with additional unobserved variables directly; and on meaning of the comparison in Table 3. Authors clarified the naive approach would not yield robust policies, and clarified the rationale of Table 3.
- Clarifying assumptions of same units between models in the reward function was raised [xCNX]; authors planned to discuss it.
- Clarifying the impact of differences between models (e.g. if they disagree on the objective) was desired [xCNX]; authors briefly discussed this but seemed to leave it for future work.
- The message of Table 4 was considered unclear due to the roles of the robust versus optimal policy [xCNX]; authors planned to clarify it.
- Several concerns on readability were raised [g1P2] including clarity of the parts after the introduction, lack of figures, lack of intuitive descriptions of theorems in sections 4 and 5, lack of explanation of some symbols, and sparsity of discussion of the results. Authors promised to clarify the relevant parts of the paper.


After the rebuttals, [aQSA] considered most of their concerns addressed. Reviewer [g1P2] also seemed to feel the concerns were mostly addressed but noted that the proposed changes were hard to judge without detail; authors the provided some plans for the detail. Reviewer [xCNX] considered all the questions and concerns addressed. Reviewer [sP8H] seemed to think concerns were addressed.

Overall, it seems although there are remaining concerns of e.g. computational complexity, there is enough appreciation of the current content that the work may be suitable for presentation at NeurIPS.
Decision: Accept (poster)