Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability

We would like to thank the reviewer for their helpful comments, suggestions, and questions. Based on those, we plan to make the following changes to our paper:

• Include a more detailed discussion on the effects of assumptions made on the reward function.
• Clarify the rationale behind Table 4 in the experimental evaluation.
• Include new experimental results to provide more empirical guidance on expected runtimes in terms of model size.
• Incorporate all other suggestions and directions for future work.

We first address the comments.

C1. One assumption that I think needs to be mentioned is that the reward function needs to use the same units between models.

We acknowledge that scaling in the reward functions of different experts/models is an interesting problem. For example, one could design multi-environment POMDP solvers that extract the qualitative behavior from different environments without being affected by the rewards. While 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.

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.

We agree that the quality of the robust policy depends on the differences between the environments. If environments differ a lot, the robust policy will be more conservative than if environments are more similar.

Although 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. Such multi-objective problems are nonetheless an interesting and relevant direction for future work.

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.

We understand the confusion highlighted by the reviewer and thank them for bringing this issue to our attention. We 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. We will clarify the rationale behind Table 4 and the values compared in the table.

Next, we answer the questions.

Q1. Do you have a proof or empirical evaluation for showing that AB-HSVI converges over time?

In summary: We believe that there are promising directions for proving convergence using similar methods as for partially observable stochastic games.

Standard 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.

To prove the convergence of HSVI in a POSG setting, the authors of [1] augmented the standard HSVI approximation algorithm. The first augmentation is a new upper bound with Lipschitz continuity. The second augmentation is a modified convergence condition for the forward belief search. These modifications facilitate a proof that, informally, convergence of HSVI at a point implies convergence in a neighborhood of that point.

We believe that applying these modifications to AB-HSVI provides a promising path to show uniform convergence of the value function in AB-HSVI.

Q2. Have you evaluated any other problems or done additional evaluation on the computation cost of changing the individual factors?

Note: This is a similar answer to the one we give to Reviewer 3 (sP8H) Q1 and Q2, which we repeat here for readability.

Tables 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. To 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. We conducted multiple experiments with these fixed rock positions, varying the number of rocks, the number of good rocks, and the grid size. With these experiments, we will improve the empirical guidance for:

1. The influence of only increasing the state space while keeping similar environments.
2. The influence of different environments with the same state, action, and number of environments.

For 1., we see that the increase in computation time still depends on the type of consistent environments. For 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. On 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$.

For 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. We will include these additional experiments and discussion in the final version of the paper.

References

[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)

We would like to thank the reviewer for their helpful comments, suggestions, and questions. Based on those, we plan to make the following changes to our paper:

• 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.
• Include new experimental results to provide more empirical guidance on expected runtimes in terms of model size.
• Incorporate all other suggestions and directions for future work.

We first address the weaknesses that do not have a corresponding question.

W2/W3. Results are reported on randomly generated environments without variance, error bars, or confidence intervals, limiting the interpretation of empirical robustness. There is no in-depth discussion of how randomness in benchmark generation may affect results.

Note: This is the same answer as we give to Reviewer 1 (aQSA) Q3, which we repeat here for readability.

In summary: No benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial. Nevertheless, we provide additional experiments on variations of the RockSample problem.

First, we would like to note that there are no existing benchmarks for ME-POMDPs. Removing the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial. For example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. The environment where all rocks are bad is trivially the worst-case environment.

To create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization. We 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).

Creating challenging problem instances is difficult. For 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. For this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.

Even 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. To demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks. The number of states, actions, and environments is fixed across the instances. The 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.

We will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.

Next, we answer the questions.

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? How well does the approach scale as the state, action, or environment space increases?

We 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]. For finite-horizon reward maximization, the problem is at least PSPACE-hard [3], but the exact theoretical complexity of solving ME-POMDPs is still open.

Although 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. To 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. We conducted multiple experiments with these fixed rock positions, varying the number of rocks, the number of good rocks, and the grid size. With these experiments, we will improve the empirical guidance for:

1. The influence of only increasing the state space while keeping similar environments.
2. The influence of different environments with the same state, action, and number of environments.

For 1., we see that the increase in computation time still depends on the type of consistent environments. For 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. On 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$.

For 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. We will include these additional experiments and discussion in the final version of the paper.

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?

The only available robust POMDP solvers assume $(s,a)$-rectangularity, which is an independence assumption between the uncertainty of different state-action pairs. This is a property that the general multi-environment problems that we consider do not have. Consequently, none of the problems we evaluate on are $(s,a)$-rectangular. Making 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. The computed optimal agent policy will then also be significantly more conservative than necessary for the multi-environment problem. This makes a comparison with robust POMDP solvers ineffective.

We further remark that assuming $(s,a)$-rectangularity does not make the problem necessarily easier to solve. In [4], robust optimization is employed to solve robust POMDPs, but due to the non-convexity of the underlying optimization problem, iterative approximations are required.

Q4. On line 19, the equation $H + 1 = H$ requires clarification. On line 99, the superscript * is not defined.

• Line 93 indicates that $H + 1 = \infty$, as in this case, $H = \infty$.
• For a finite set $X$, we denote by $X^\*$ the set of finite sequences of elements from $X$. That is, $\*$ indicates the Kleene-star operator.

We will add these corrections and clarifications to the paper.

References

[1] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004

[2] Omid Madani, Steve Hanks, Anne Condon: On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems. AAAI/IAAI 1999

[3] Christos H. Papadimitriou, John N. Tsitsiklis: The Complexity of Markov Decision Processes. Math. Oper. Res. 12(3): 441-450 (1987)

[4] Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, Ufuk Topcu: Robust Finite-State Controllers for Uncertain POMDPs. AAAI 2021

Thanks for the rebuttal. However, the author did not respond to the Weakness 1.

We would like to thank the reviewer for their helpful comments, suggestions, and questions. Based on those, we plan to make the following changes to our paper:

• Clarify the results presented in Table 3.
• 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.
• Incorporate all other suggestions and directions for future work, paying particular attention to accessibility and readability. We will also highlight the limitations.

We first clarify the meaning of the indicated symbols:

• $\bot$ and $\top$ are fresh symbols used throughout model definitions to denote auxiliary states/observations.
• $y$ is used to indicate a solution to the dual linear program.

We will clarify these symbols in the final version of the paper.

Next, we answer the questions.

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?

Solving a ME-POMDP via a larger POMDP does not lead to robust policies. When we write a ME-POMDP $M$ as a larger POMDP $M'$, we must define an initial distribution (initial belief) in this larger POMDP $M'$. By 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.

A 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. Indeed, we can encode zero-sum matrix games via ME-POMDPs. We provide an example of this encoding in Proposition 1 of the paper, which is available in the supplementary material. We note that for this PO-MEMDP (which is, in turn, a ME-POMDP), the optimal strategy is randomized. We also note that when we do not specify an initial belief for the POMDP, we obtain an AB-POMDP. We explore that approach to solving ME-POMDPs in Table 3.

Q2. What does the comparison in Table 3 between ME-POMDPs and AB-POMDPs, both solved with AB-HSVI, entail?

The results in Table 3 are to compare the naive implementation as suggested in your other question. When 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. When, 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. We will clarify the rationale behind the comparison in Table 3 in the paper.

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?

Regarding the inputs to the fully-observing players' inputs, we note that this assumption is standard for one-sided POSGS [1]. However, 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.

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?

Note: This is the same answer as we give to Reviewer 1 (aQSA) Q3, which we repeat here for readability.

In summary: No benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial. Nevertheless, we provide additional experiments on variations of the RockSample problem.

First, we would like to note that there are no existing benchmarks for ME-POMDPs. Removing the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial. For example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. The environment where all rocks are bad is trivially the worst-case environment.

To create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization. We 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).

Creating challenging problem instances is difficult. For 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. For this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.

Even 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. To demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks. The number of states, actions, and environments is fixed across the instances. The 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.

We will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.

References

[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)

[2] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004

We would like to thank the reviewer for their helpful comments, suggestions, and questions. Based on those, we plan to make the following changes to our paper:

• Add details on optimization techniques for AB-HSVI.
• 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.
• Incorporate all other suggestions and directions for future work.

We now answer the questions.

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?

We implement two optimization techniques already: sparse representations for vectors and matrices, and pruning of $\alpha$-vectors. We use sparse matrices to represent the beliefs and $\alpha$-vectors. This optimization is most effective when, during execution, we can infer that a certain environment is impossible. For 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. A sparse representation avoids explicitly storing that part of the matrix. Another optimization we implement in AB-HSVI is the pruning of $\alpha$-vectors that are dominated by a single other $\alpha$-vector. Using additional pruning methods could improve the efficiency of the algorithm. Additional 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].

We will add details on the optimization techniques already used, as well as the additional directions for further optimization, to the paper.

Q1a. Could one prune redundant or clearly dominated environments from the set before solving?

Pruning environments before solving can be done when an environment is a submodel of another environment. Examples of situations where such pruning can be performed are:

• When the transition and observation functions are the same, but one of the reward functions has larger rewards at every state-action pair.
• When one environment has a sink state, while another environment can continue to accumulate reward.

We did not consider such optimizations in the current work, and thank the reviewer for the interesting suggestion for future improvement.

Q1b. Could the core idea of adversarial belief be integrated with more scalable online planning methods, such as POMCP?

A key requirement in online planning methods such as POMCP is that there is a model to simulate. In 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. If 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.

One 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.

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?

In 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.

However, we acknowledge that even these methods are intractable for large mere POMDPs already, and that there are indeed interesting directions for the future. One possible approach to lessen the computational burden is to use policy-gradient methods in a game setting [3,4]. Such methods could prove interesting both from a computational efficiency perspective and a theoretical perspective.

Q3. Could you comment on how representative you believe the single runs on the randomly generated instances for each problem configuration are?

In summary: No benchmarks exist for ME-POMDPs, and a straightforward adaptation of existing POMDP benchmarks is not trivial. Nevertheless, we provide additional experiments on variations of the RockSample problem.

First, we would like to note that there are no existing benchmarks for ME-POMDPs. Removing the initial belief from a POMDP benchmark model often does not result in an interesting problem, as the worst-case environment can be trivial. For example, in the original RockSample problem, the initial distribution defines how many rocks are good and bad. The environment where all rocks are bad is trivially the worst-case environment.

To create challenging, non-trivial problems for evaluating AB-HSVI, we employed randomization. We 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).

Creating challenging problem instances is difficult. For 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. For this classification, we considered a problem instance trivial if it could be solved within $30$ seconds.

Even 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. To demonstrate this, we ran some additional experiments on RockSample instances where the only change was the position of the rocks. The number of states, actions, and environments is fixed across the instances. The 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.

We will clarify the use of randomization in our paper and include these experiments to further highlight the effects of the specific model on runtime.

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?

AB-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]. We 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. In 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. Similarly, 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.

References

[1] Pascal Poupart, Craig Boutilier: Value-Directed Compression of POMDPs. NIPS 2002

[2] Tyler J. Becker, Zachary Sunberg: Bridging the Gap between Partially Observable Stochastic Games and Sparse POMDP Methods. AAMAS 2025

[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)

[4] Constantinos Daskalakis, Dylan J. Foster, Noah Golowich: Independent Policy Gradient Methods for Competitive Reinforcement Learning. NeurIPS 2020

[5] Trey Smith, Reid G. Simmons: Heuristic Search Value Iteration for POMDPs. UAI 2004

[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)

[7] Qinghua Liu, Csaba Szepesvári, Chi Jin: Sample-Efficient Reinforcement Learning of Partially Observable Markov Games. NeurIPS 2022

[8] Awni Altabaa, Zhuoran Yang: On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games. NeurIPS 2024

[9] Xiangyu Liu, Kaiqing Zhang: Partially Observable Multi-agent RL with (Quasi-)Efficiency: The Blessing of Information Sharing. ICML 2023