Paper deep dive
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be $\mathsf{PSPACE}$-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this $\mathsf{PSPACE}$-completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the $\mathsf{NP}$-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove $\mathsf{PSPACE}$-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals ($\exists \mathbb{R}$)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are $\mathsf{NP}$-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.
Tags
Links
- Source: https://arxiv.org/abs/2610.15010v1
- Canonical: https://arxiv.org/abs/2610.15010v1
Trouble viewing inline? Open PDF directly →
Full Text
231,763 characters extracted from source content.
Expand or collapse full text
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs Eline M. Bovy Note: Shared first authorship, ordered alphabetically. Affiliation: Radboud University, Nijmegen, The Netherlands , Caleb Probine Affiliation: The University of Texas at Austin, Austin, USA , Marnix Suilen Affiliation: University of Antwerp , Antwerp, Belgium , Ufuk Topcu Affiliation: The University of Texas at Austin, Austin, USA and Nils Jansen Affiliation: Ruhr-University Bochum, Bochum, Germany Affiliation: Radboud University, Nijmegen, The Netherlands 2027 Abstract. Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be -complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this -completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the NP-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove PSPACE-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals ( )-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are -complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved. Keywords: POMDPs, Multi-environment, Robustness 1. Introduction Partially observable Markov decision processes (POMDPs) are a canonical model for sequential decision-making problems under partial information (Kaelbling et al., 1998). POMDPs capture problems in which a decision-maker must reason about an unknown state of the world, with applications ranging from robotics to healthcare (Kurniawati, 2022; Hauskrecht and Fraser, 2000). POMDP planning algorithms, however, rely on the restrictive assumption that a single exact model of the environment exists. Multi-environment POMDPs (ME-POMDPs) remove this assumption and instead assume a finite set of possible environment models (Bovy et al., 2025). A ME-POMDP comprises a discrete set of POMDPs with shared state, observation, and action spaces. The robust reward-maximization problem for ME-POMDPs then asks for a policy that maximizes expected reward in the worst-case environment, chosen by an adversary. Like POMDPs, ME-POMDPs admit value-iteration-based (Bovy et al., 2025) and gradient-ascent-based (Galesloot et al., 2025) algorithms for reward maximization, as well as reinforcement learning algorithms for reach-reward objectives (Hudák et al., 2026). Meanwhile, in terms of complexity, finite-horizon reward maximization is -complete in ME-POMDPs (Brice et al., 2026a), just as in standard POMDPs (Papadimitriou and Tsitsiklis, 1987), while the discounted infinite-horizon setting is already undecidable for the latter (Madani et al., 2003). Significant effort has been poured into finding more tractable subclasses of POMDPs. These classes rely on additional assumptions to reduce the computational complexity of finite-horizon reward maximization or to achieve decidability for many objectives, including infinite-horizon discounted rewards and logic objectives such as reachability and parity (Asadi et al., 2026; Belly et al., 2025). For finite-horizon rewards on single-environment models, only complexity results for general POMDPs, fully observable MDPs, and blind MDPs are known (Papadimitriou and Tsitsiklis, 1987). In the multi-environment setting, results are only known for multi-environment MDPs (Raskin and Sankur, 2014) and general ME-POMDPs (Brice et al., 2026a), as Figure 1 illustrates, leaving a large gap between single-environment subclasses of POMDPs and their extension to multiple environments. POMDPMDPBlindMDP⊆ ⊆ ⊆ -environment modelsMulti-environment modelsPSPACE-hardin NPNP-hardin PPSPACE-hardin NPNP-hardin PETR-hardin NPNP-hardin PNo restrictionsDeterministicMarkovian randomized policies Figure 1. Known complexity results for finite-horizon ME-POMDPs. Dark blue and red lines correspond to problems with deterministic dynamics and Markovian policies, respectively, while bright blue lines correspond to problems with no dynamics or policy restrictions. An annotation “ X-hard” atop a line encodes that problems above that line are hard for the complexity class X. An annotation “in X” below a line encodes that problems below the line are decidable in X. POMDPRevPOMDPSOMDPηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ -environment modelsMulti-environment modelsMulti-observation modelsMulti-observation models, fixed supportPSPACE-hardin NPNP-hardin PPSPACE-hardin NPNP-hardin PETR-hardin NPETR-hardopenNP-hardin PNo restrictionsDeterministicMarkovian randomized policies Figure 2. Overview of ME-POMDP complexity including results we present. Dark blue and red lines correspond to problems with deterministic dynamics and Markovian policies, respectively, while bright blue lines correspond to problems with no dynamics or policy restrictions. An annotation “ X-hard” atop a line encodes that problems above that line are hard for the complexity class X. An annotation “in X” below a line encodes that problems below the line are decidable in X. Contributions We investigate the complexity of finite-horizon reward maximization in multi-environment POMDPs across a large set of subclasses. We consider these subclasses in full generality without further restrictions, and also examine special cases with deterministic transition and observation dynamics, as well as restricted policy classes such as finite-memory policies. Our results establish a significantly expanded complexity landscape for ME-POMDPs in Figure 2 compared with Figure 1. Our specific contributions are as follows. (1) We show that POMDPs where all states are hidden through the same observation (Blind MDPs) and POMDPs with deterministic transition and observation functions (deterministic POMDPs) remain -complete when extended to the multi-environment setting. These results rely on both subclasses respecting a certain closure under mixture condition: Allowing the adversary to randomly choose an environment from a fixed set of POMDPs in one of these subclasses is equivalent to the agent acting in a new POMDP in that subclass. (2) We analyze a range of multi-environment models that lack the closure property above, yielding hardness results for a range of multi-observation POMDP problems. We show that simple observation uncertainty, in particular uncertainty about state labelings or the probability that the true state is revealed, leads to -completeness, as in general ME-POMDPs. We also obtain novel complexity results for many single-environment POMDP subclasses. (3) We characterize the complexity of ME-POMDPs with restricted policies. We show that numerous problems involving time-dependent Markovian policies or finite-state controllers that are -complete for POMDPs become existential theory of the reals ( )-complete for ME-POMDPs. Outline After related work and preliminaries, Section 4 details all involved subclasses. Section 5 presents the complexity results for ME-POMDPs using hidden-mixture reasoning. Hardness results for ME-POMDPs built from subclasses that are not closed under hidden mixtures are in Section 6. Results on restricted policy classes for ME-POMDPs are in Section 7. 2. Related Work A range of works provide algorithmic and complexity results for Multi-Environment MDPs (ME-MDPs). In particular, for the robust setting, in which we assume no distribution on the environments, previous work characterizes the complexity of various qualitative problems (Chatterjee et al., 2025; Bordais and Raskin, 2026; Raskin and Sankur, 2014; Suilen et al., 2024; van der Vegt et al., 2023), and provides algorithmic approaches for the reward-maximization problem (Ahluwalia et al., 2021; Steimle et al., 2021). For finite-horizon reward maximization, the problem is -complete for history-dependent policies (Le Tallec, 2007; Brice et al., 2026a) and -hard when policies are restricted to be time-dependent Markovian (Le Tallec, 2007; Li, 2026). While we study ME-POMDPs, which strictly generalize ME-MDPs, we also tighten existing ME-MDP results by showing that the reward-maximization problem with time-dependent Markovian policies is -complete, where lies between and . Single-environment POMDP complexity results provide trivial lower bounds on ME-POMDP complexity. The -hardness of POMDPs (Papadimitriou and Tsitsiklis, 1987), along with the -hardness of subclasses such as Blind MDPs (Papadimitriou and Tsitsiklis, 1987) and deterministic POMDPs (Littman, 1996), thus also holds for ME-POMDPs. The closest related work is (Brice et al., 2026a), which shows that finite-horizon reward maximization in ME-POMDPs is -complete, but it considers only general POMDPs, not subclasses. The interaction between the agent and adversary in a ME-POMDP can be encoded as a one-sided zero-sum partially observable stochastic game (POSG) (Bovy et al., 2025). As ME-POMDPs have a highly restricted adversary structure, complexity lower bounds for POSGs do not immediately transfer to ME-POMDPs. While upper bounds for POSGs naturally transfer to ME-POMDPs, existing results already separate the two, with finite-horizon reward-maximization being -complete for deterministic POSGs11 1 This fact follows from the proof of (Papadimitriou and Tsitsiklis, 1987). but -complete for deterministic ME-POMDPs, as we show. Like POSGs, extensive-form games also involve partial information and have well-known complexity results (Koller and Megiddo, 1992). However, they are strictly more general than ME-POMDPs in the structure of the adversary’s actions, and naive encodings of ME-POMDPs as imperfect-information games lead to an exponential blow-up in representation size. 3. Preliminaries The sets of real numbers and natural numbers are ℝR and ℕN, respectively. We denote the set of integers 1,…,n\1,…,n\ as [n][n]. We use Δ(B) (B) to denote the set of distributions on elements of a set B. For a distribution q∈Δ(X)q∈ (X), (q) supp(q) is the set of elements x∈Xx∈ X such that q(x)>0q(x)>0. For x∈Xx∈ X, δx∈Δ(X) _x∈ (X) is the Dirac distribution which places all probability mass on x. For a vector u we use [i]u[i] or (i)u(i) to denote the ithi^th element, and ⊤u denotes its transpose. We assume basic familiarity with standard complexity classes , P, , and , as well as the classical -complete problem 3SAT, its -complete variant QSAT (Papadimitriou, 1994), and their conjunctive normal form (CNF). We also consider the complexity class . The first-order theory of the reals over (ℝ,0,1,+,⋅,<)(R,0,1,+,·,<) is the logic used to express whether a polynomial system of (in)equalities has a solution in ℝR. The existential theory of the reals is the fragment that asks whether ∃x1,…,xn.ϕ(x1,…,xn)∃ x_1,…,x_n.φ(x_1,…,x_n) has a solution for a given quantifier-free formula ϕφ. The truth problem for this fragment defines the complexity class , with ⊆ ⊆ (Schaefer et al., 2024). 3.1. POMDPs A partially observable Markov decision process (POMDP) models an environment in which an agent takes actions to maximize reward under partial information on the true state of the world. Definition 3.1 (POMDP). A partially observable Markov decision process (POMDP) is a tuple (S,A,Z,T,O,R,b,H)(S,A,Z,T,O,R,b,H), where S is a finite set of states, A is a finite set of actions, Z is a finite set of observations, T:S×A→Δ(S)T S× A→ (S) is a transition function, O:S→Δ(Z)O S→ (Z) is an observation function, R:S×A→ℝR S× A is a reward function, b∈Δ(S)b∈ (S) is an initial state distribution, and H∈ℕH is the horizon. We write T(s,a,s′)=T(s,a)(s′)T(s,a,s )=T(s,a)(s ) and similarly, O(s,z)=O(s)(z)O(s,z)=O(s)(z). The state s0s_0 at time 00 is drawn according to b. For every t≥0t≥ 0, the observation ztz_t is drawn from O(st)O(s_t). The agent then observes ztz_t, takes an action ata_t, and the next state is drawn from T(st,at)T(s_t,a_t). An agent acts in a POMDP using a policy that maps observation histories to distributions over actions: π:∪t=0H−1Z(AZ)t→Δ(A)π _t=0^H-1Z(AZ)^t→ (A). We denote by ΠZ,A,H ^Z,A,H the set of all such history-dependent randomized policies for a given observation space, action space, and horizon. When the POMDP is clear from context, we will simply write Π . A policy π is deterministic if, for all histories h in ∪t=0H−1Z(AZ)t _t=0^H-1Z(AZ)^t, π(h)π(h) is a Dirac distribution, and we use Π _ det to denote the set of deterministic policies. A mixed policy is a distribution over deterministic policies, and the agent randomly draws one such policy before playing. In the finite-horizon setting, any mixed policy π′π has an equivalent behavioral policy π that induces the same path distribution in all POMDPs (Kuhn, 1953). The finite-horizon expected reward of a policy π in a POMDP ℳM is Vℳπ=ℳπ[∑t=0H−1R(st,at)]V_M^π=E_M^π [ _t=0^H-1R(s_t,a_t) ], where sts_t and ata_t are random variables representing the state and action respectively at time t, for t in the set 0,1,…,H−1\0,1,…,H-1\, and we use use ℳπE_M^π to denote the expectation under the measure induced by the policy π and the POMDP ℳM. 3.2. Multi-Environment POMDPs A multi-environment POMDP (ME-POMDP) comprises a finite set of POMDPs with common state, action, and observation spaces, and a common horizon, but potentially different dynamics. Definition 3.2 (ME-POMDP). A multi-environment POMDP (ME-POMDP) is a tuple (S,A,Z,(Ti)i∈[n],(Oi)i∈[n],(Ri)i∈[n],(bi)i∈[n],H)(S,A,Z,(T_i)_i∈[n],(O_i)_i∈[n],(R_i)_i∈[n],(b_i)_i∈[n],H). Each index i∈[n]i∈[n] defines a POMDP ℳi=(S,A,Z,Ti,Oi,Ri,bi,H)M_i=(S,A,Z,T_i,O_i,R_i,b_i,H). We emphasize that we define ME-POMDPs without a distribution over environments; thus, ME-POMDPs are not a subclass of POMDPs. We define the set of history-dependent policies in the same manner as we do for POMDPs. We evaluate policies in ME-POMDPs in a worst-case fashion. For a policy π in a ME-POMDP (ℳi)i∈[n](M_i)_i∈[n], we define its value as (1) V(ℳi)i∈[n]π=mini∈[n]Vℳiπ=mini∈[n]ℳiπ[∑t=0H−1R(st,at)].V_(M_i)_i∈[n]^π= _i∈[n]V^π_M_i= _i∈[n]E^π_M_i [ _t=0^H-1R(s_t,a_t) ]. A multi-observation POMDP (MO-POMDP) is a ME-POMDP in which the environments differ only in their observation functions. That is, for all i,ji,j in [n][n], we have Ti=TjT_i=T_j, Ri=RjR_i=R_j and bi=bjb_i=b_j. A MO-POMDP additionally satisfies the fixed support condition if, for all states s∈Ss∈ S and environments i,j∈[n]i,j∈[n], the set of possible observations is fixed, i.e., (Oi(s))=(Oj(s)) supp(O_i(s))= supp(O_j(s)). 3.3. Decision Problems and Encodings We study the complexity of the following decision problem. Problem 1 (Value problem). Given a ME-POMDP (ℳi)i∈[n](M_i)_i∈[n], and a rational number B, the value problem asks whether there exists a policy π such that V(ℳi)i∈[n]π≥BV_(M_i)_i∈[n]^π≥ B. The value problem for restricted policy classes is defined analogously. Problem 1 considers history-dependent randomized policies π∈Ππ∈ , unless noted otherwise. The value problem for single-environment models follows from Equation 1 with n=1n=1. We encode each ME-POMDP following the standard conventions for single-environment POMDPs (Papadimitriou and Tsitsiklis, 1987). All transition, observation, and reward functions, as well as the initial distributions, are given as tables, where each entry is a rational number encoded as a ratio of two integers given in binary. The horizon is encoded in unary. 4. Single-Environment Models In this section, we introduce POMDP subclasses we consider and the complexities of their reward-maximization problems. Figure 3 summarizes the subclasses we consider. We give complete proofs for all novel single-environment complexity results in Appendix D. 4.1. Subclasses of POMDPs Recall a POMDP is a tuple (S,A,Z,T,O,R,b,H)(S,A,Z,T,O,R,b,H). We consider the following subclasses of POMDPs, ordered by increasing restriction. Revealing POMDPs (RevPOMDPs) In a RevPOMDP, each state has a non-zero probability of revealing the true state through a unique observation (Belly et al., 2025; Asadi et al., 2026). Formally, a RevPOMDP is a POMDP where Z contains a subset ⊤s∣s∈S\ _s s∈ S\22 2 The subset of Z can be any |S||S| observations as long as the observation function maps a unique state to each observation. of observations such that ∀s∈S,O(s,⊤s)>0∧∀s′∈S,s′≠s⟹O(s′,⊤s)=0∀ s∈ S,O(s, _s)>0 ∀ s ∈ S,s ≠ s O(s , _s)=0. This definition encodes a variant of the strongly revealing POMDPs of (Belly et al., 2025) or revealing POMDPs of (Asadi et al., 2026) with state-based observations. RevPOMDPs are decidable for almost-sure, limit-sure, and quantitative reachability and parity objectives (Belly et al., 2025; Asadi et al., 2026), in contrast to general POMDPs where most objectives are undecidable (Chatterjee et al., 2010; Madani et al., 2003). Semi-Observable MDPs (SOMDPs) In a SOMDP, each state has a revealing observation and is otherwise unobservable (Basich et al., 2022). The revelation probability may vary across states, and is encoded by a likelihood function η:S→[0,1]η S→[0,1]. Formally, a SOMDP is a POMDP where the observation set comprises revealing observations for each state and a blind observation, i.e., Z=⊤s∣s∈S∪⊥Z=\ _s s∈ S\∪\ \. The observation function then must satisfy O(s)=⊤s↦η(s),⊥↦1−η(s)O(s)=\ _s η(s), 1-η(s)\ for some function η:S→[0,1]η S→[0,1]. This definition corresponds to a variant of SOMDPs with state-based observations (Basich et al., 2022). In SOMDPs, one can track the action-observation history by tracking the last observed state and all actions taken since then (Basich et al., 2022). Intermittently-Observable MDPs (IOMDPs) In an IOMDP, each state has a revealing observation and is otherwise unobservable (Chen and Liew, 2026), as in a SOMDP. However, IOMDPs additionally require the revelation probability to be constant across states. Formally, an IOMDP is a POMDP where Z=⊤s∣s∈S∪⊥Z=\ _s s∈ S\∪\ \, and the observation function satisfies O(s)=⊤s↦λ,⊥↦1−λO(s)=\ _s λ, 1-λ\ for some λ∈[0,1]λ∈[0,1]. In an IOMDP, action-observation histories are tracked by the last observed state and all actions since then. Blind MDPs (BlindMDPs) In a BlindMDP, there is only a single observation (Papadimitriou and Tsitsiklis, 1987; Madani et al., 2003; Mundhenk et al., 2000). Formally, it is a POMDP where Z=⊥Z=\ \, and for each state s, O(s,⊥)=1O(s, )=1. MDPs MDPs are a fully observable subclass of POMDPs, in which each state has a single unique observation (Puterman, 1994). Formally, an MDP is a POMDP where Z=⊤s∣s∈SZ=\ _s s∈ S\ consists of a revealing observation for each state ⊤s _s, also called a state labeling, and the observation function is deterministic with O(s,⊤s)=1O(s, _s)=1. Partial orders on subclasses In Figure 3, we arrange the above POMDP subclasses by the inclusion relation. Note that the subset inclusion of Blind MDPs depends on whether the three middle models, i.e., IOMDPs, SOMDPs, and RevPOMDPs, allow revelation probabilities of 00. Also note that allowing RevPOMDPs to include zero revelation probabilities recovers the class of all POMDPs. POMDPRevPOMDPSOMDPηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ Figure 3. Overview of the models considered in this paper. Deterministic dynamics For each subclass introduced above, we also consider a variant with deterministic transition and observation functions. Note that, when the observation function is deterministic, RevPOMDPs, SOMDPs with ηs∈(0,1] _s∈(0,1], and IOMDPs with λ∈(0,1]λ∈(0,1] all collapse to MDPs as each revelation probability becomes 11. Also, IOMDPs with λ∈[0,1]λ∈[0,1] collapse to either MDPs or Blind MDPs, as the revelation probability is constant. Subclasses not considered We focus on the subclasses above as they prove sufficient to uncover interesting complexity behavior. However, we also note that there are numerous other interesting subclasses of POMDPs which we do not characterize, such as posterior-deterministic POMDPs (Fijalkow et al., 2026), quasi-deterministic POMDPs (Besse and Chaib-draa, 2009) or observable POMDPs (Golowich et al., 2022). We leave exploration of multi-environment versions of these subclasses to future work. 4.2. Complexity of Single-Environment Models We discuss the complexity of finite-horizon reward maximization in single-environment models. The first column of Figure 2 summarizes the results. First, recall that this problem for MDPs without any restrictions is in P (Papadimitriou and Tsitsiklis, 1987), and for Blind MDPs it is -complete (Papadimitriou and Tsitsiklis, 1987; Mundhenk et al., 2000). We now show that for all models between IOMDPs and SOMDPs the problem is -complete. Proposition 4.1. The value problem for IOMDPs with λ∈(0,1]λ∈(0,1] is -hard. Proof Sketch. We reduce 3SAT to the value problem for IOMDPs. For each 3SAT instance, one can build a BlindMDP with non-positive reward such that the 3SAT instance is satisfiable if and only if the BlindMDP has zero expected reward (Mundhenk et al., 2000). To prove -hardness for IOMDPs, we use the same transition structure, but allow the agent to see the true state with probability 1/2 12. With positive probability, the agent never observes the state and, in effect, plays a sequence of actions in a BlindMDP, and we can argue that this sequence of actions also defines a satisfying assignment for the original 3SAT instance. ∎ Proposition 4.1 implies that finite-horizon reward maximization for all models in the class IOMDPλ∈(0,1] IOMDP_λ∈(0,1] is -hard. We next provide an upper bound for all models below SOMDPηs∈[0,1] SOMDP_ _s∈[0,1]. Proposition 4.2. The value problem for SOMDPs with ηs∈[0,1] _s∈[0,1] is in . Proof Sketch. We show that the optimal policy in a SOMDP can be guessed and evaluated in polynomial time. This policy is belief-based and deterministic, tracking the last observed state, the time of the last observation, and the current time. The belief in an SOMDP collapses every time a state is revealed. Until the next state revelation, all observations are blind, so the decision-maker has only the actions and number of time steps that have passed as available information. Since the actions are chosen deterministically, tracking the last revelation time and the current time step suffices to track the belief. ∎ We complete the complexity results for single-environment models without deterministic dynamics by proving that reward maximization in RevPOMDPs is -hard. Proposition 4.3. The value problem for revealing POMDPs is -hard. Proof Sketch. We reduce from QSAT. For each QSAT instance, one can build a POMDP with non-positive reward such that the QSAT instance is satisfiable if and only if the POMDP has zero expected reward (Mundhenk et al., 2000). To prove -hardness for RevPOMDPs, we use the same transition structure, but allow the agent to see the true state with probability 1/2 12. With positive probability, the agent never observes the state and, in effect, plays a sequence of actions in a POMDP, and we can argue that this sequence of actions also defines a satisfying assignment for the original QSAT instance. ∎ Deterministic Single-Environment Models Next, we discuss subclasses with deterministic dynamics. Deterministic MDPs are a subset of MDPs, and are thus decidable in P. Deterministic RevPOMDPs collapse to MDPs because they must have a positive probability of revealing each state. Therefore, every model that is a subset of RevPOMDPs lies in P for deterministic dynamics. For BlindMDPs, the reduction used to prove -hardness in (Mundhenk et al., 2000) uses deterministic transitions. As such, BlindMDPs, and any superset model, remain -hard in the deterministic case. Finally, the general deterministic POMDP (DetPOMDP) problem lies in (Littman, 1996; Bonet, 2009). 4.3. Complexity of Policy Restrictions Restricting policy classes also reduces POMDP complexity, and we next discuss the complexity of the associated decision problems. Under a time-dependent Markovian policy, an agent chooses an action using only their last observation and the current time, i.e., π:0,…,H−1×Z→Δ(A)π \0,…,H-1\× Z→ (A). We write Π _ MR for the set of time-dependent Markovian randomized policies. A policy is stationary if it only depends on the observation, and not the time step. The value problem under time-dependent Markovian policies is -complete for all POMDP subclasses besides MDPs. By (Mundhenk et al., 2000), the value problem for time-dependent Markovian policies lies in when restricted to deterministic policies, and these deterministic policies are optimal among time-dependent Markovian policies (Bagnell et al., 2003). Meanwhile, -hardness for Blind MDPs follows by observing that history-dependent and time-dependent Markovian policies coincide in this subclass. For IOMDPs with λ∈(0,1]λ∈(0,1], we can also prove -hardness using similar arguments to those used in proving -hardness for Blind MDPs. Proposition 4.4. The value problem under time-dependent Markovian policies for IOMDPs is -hard, even when λ∈(0,1]λ∈(0,1]. Proof Sketch. For both time-dependent Markovian and history-dependent policies, the agent’s policy on the event that it never observes the state is a sequence of actions. Analogously to the proof of Proposition 4.1, we can establish a correspondence between these action sequences and satisfying assignments of a 3SAT instance, which we in turn use to establish -hardness. ∎ While not shown in Figure 2, we also explore finite-state controllers (Poupart and Boutilier, 2003; Meuleau et al., 1999) for POMDPs and their multi-environment counterparts. A generalization of a time-dependent Markovian policy is a time-dependent FSC, in which an agent can use a set of memory states to store information about past actions and observations. Definition 4.5 (Time-dependent FSC). For a (ME-)POMDP with observations Z, actions A, and horizon H, a time-dependent FSC is a tuple (Q,ι,(γt)t∈0,…,H−1,(ηt)t∈0,…,H−1)(Q, ,( _t)_t∈\0,…,H-1\,( _t)_t∈\0,…,H-1\), where Q is a set of memory states, ι∈Δ(Q) ∈ (Q) is an initial memory-state distribution, γt:Q×Z→Δ(A) _t Q× Z→ (A) is a time-dependent action mapping, and ηt:Q×Z×A→Δ(Q) _t Q× Z× A→ (Q) is a time-dependent memory update mapping. A time-dependent FSC is equivalent to a standard time-independent FSC with memory nodes Q′=Q×0,…,H−1Q =Q×\0,…,H-1\ where one always updates (q,t)(q,t) to (q′,t+1)(q ,t+1). The value problem for FSCs mirrors Problem 1, but takes an additional integer |Q||Q| as input to encode the memory size the agent may use. Problem 2 (FSC value problem). Given a ME-POMDP (ℳi)i∈[n](M_i)_i∈[n], a rational number B, and a memory bound |Q||Q| polynomial in the ME-POMDP size, the FSC value problem asks whether there exists a time-dependent FSC π such that V(ℳi)i∈[n]π≥BV_(M_i)_i∈[n]^π≥ B. Lemma 4.6. For any POMDP ℳM, and fixed |Q||Q|, there exists a deterministic optimal time-dependent FSC for ℳM. Consequently, the time-dependent FSC value problem for POMDPs is -complete. Proof Sketch. We can construct a product POMDP ℳ′M with state space S×QS× Q (Junges et al., 2018). Time-dependent FSCs in the original POMDP then correspond to time-dependent Markovian policies in this product, and deterministic time-dependent Markovian policies are already optimal (Bagnell et al., 2003). Thus, we can simply guess and evaluate such policies in ℳ′M to decide the FSC value problem. -hardness follows from the time-dependent Markovian case, which we can encode by restricting |Q||Q| to be one. ∎ 5. Upper Bounds via Hidden Mixtures The complexity results for subclasses of POMDPs naturally raise the question of whether they extend to the multi-environment setting. We next provide a general method for characterizing when this extension is possible by characterizing subclass behavior under hidden mixtures. Full proofs reside in Appendix E. Many positive POMDP subclass complexity results follow due to optimal policy structure. Indeed, if one can guess a policy quickly, then a natural algorithm exists for determining the value problem. BlindMDPs and DetPOMDPs exhibit this structure. Indeed, any deterministic policy in a BlindMDP is simply an action sequence, while optimal policies in DetPOMDPs have concise tree representations (Littman, 1996). We show that BlindMDPs and DetPOMDPs share another favorable property: they are closed under hidden mixtures, and this property lets us transfer complexity results to ME-POMDPs. Informally, a subclass C is closed under hidden mixtures if allowing the adversary to randomly choose one of n POMDPs from C yields a new POMDP in C. As we show in this section, ME-POMDPs built from subclasses that (1) satisfy this hidden-mixture condition, and (2) admit structured optimal policies, also admit efficient algorithms. We first abstract the notion of a policy class. A policy class defines a set of policies for each POMDP depending on its observation, state, and action space and horizon. Let ,,S,A, and Z be sets encoding all possible state spaces, action spaces, and observation spaces.33 3 We remark that while the definition of the set of all state sets seems unrigorous, we give a more formal justification in Appendix E.4. Definition 5.1 (Policy class). A policy class is a family of policy sets Π=(ΠS,Z,A,H)S∈,A∈,Z∈,H∈ℕ _C=( _C^S,Z,A,H)_S ,A ,Z ,H such that (2) ΠS,Z,A,H⊂ΠZ,A,H∀Z∈,A∈,H∈ℕ. _C^S,Z,A,H⊂ ^Z,A,H ∀ Z ,A ,H . While state-space-dependence may seem unnecessary, it handles optimal policies for DetPOMDPs, whose representation depends on |S||S|. We next need to tie optimal policy classes for POMDP subclasses to their multi-environment counterparts. We bridge this gap by introducing hidden-mixture POMDPs. A hidden mixture of a finite set of POMDPs is a POMDP in which the environment is randomly drawn before the agent executes their policy. Fix a set (ℳi)i∈[n](M_i)_i∈[n] of POMDPs and a distribution ∈Δ([n])p∈ ([n]). In the resulting hidden mixture POMDP, the adversary uses p to draw an environment, and the dynamics unfold according to environment i. We use mixtures to define new POMDP subclasses. Definition 5.2 (Class of hidden mixture POMDPs). Given a subclass C of POMDPs, () Mix(C) is the set of POMDPs formed by mixing over a finite number of POMDPs from C. Hidden mixture POMDPs are structurally distinct from ME-POMDPs, as they assume a distribution over environments and, in the terminology of (Bordais and Raskin, 2026), have prior semantics. Hidden mixture POMDPs nonetheless serve as a powerful tool for reasoning about ME-POMDP complexity, as our next result shows. The optimal policy in a ME-POMDP built from a subclass C randomizes over a small set of policies that are optimal in () Mix(C). Proposition 5.3. Fix a class C of POMDPs, and suppose Π _C is a policy class that contains a deterministic optimal policy for every POMDP in () Mix(C). If (ℳi)i∈[n](M_i)_i∈[n] is a ME-POMDP with state, action and observation sets S,A,ZS,A,Z such that each POMDP lies in C, then there exists an optimal policy that mixes over n elements of Π(S×[n]),Z,A,H _C^(S×[n]),Z,A,H. Proof Sketch. Let (ℳi)i∈[n](M_i)_i∈[n] be a ME-POMDP with POMDPs in C where each POMDP has state, action and observation spaces S, A, and Z. The value satisfies the following chain of equalities. maxπ∈Πmini∈[n]Vℳiπ=min∈Δ([n])max∑i∈[n]π∈ΠZ,A,H[i]Vℳiπ=min∈Δ([n])max∑i∈[n]π∈ΠS×[n],Z,A,H[i]Vℳiπ=maxπ∈(ΠS×[n],Z,A,H)mini∈[n]Vℳiπ. _π∈ _i∈[n]V_M_i^π= _p∈ ([n]) _π∈ _ det^Z,A,H _i∈[n]p[i]V^π_M_i\\ = _p∈ ([n]) _π∈ _C^S×[n],Z,A,H _i∈[n]p[i]V^π_M_i= _π∈ Mix ( _C^S×[n],Z,A,H ) _i∈[n]V_M_i^π. The first and last equalities apply the min-max theorem for zero-sum matrix games (Başar and Olsder, 1998), which holds because Π _ det is finite and the number of environments is finite. The middle inequality uses the optimality of policies in Π _C for mixture POMDPs, along with the fact that each mixture POMDP has state space S×[n]S×[n]. To deduce that the optimal policy mixes over at most n policies in Π _C, we can then either use a linear programming result or appeal to Carathéodory’s theorem, as in (Brice et al., 2026a). ∎ Using Proposition 5.3, we can show that the value problem for both deterministic ME-POMDPs and ME-BlindMDPs lies in . Critically, these classes satisfy =()C= Mix(C). That is, they are closed under mixtures. Thus, by Proposition 5.3, we can solve the ME-POMDP by guessing n policies for the original subclass and verifying with a linear program (LP) that we can mix over these policies. Corollary 5.4. The value problem for ME-DetPOMDPs is in . Proof Sketch. When we mix over a set of DetPOMDPs (ℳi)i∈[n](M_i)_i∈[n], we get another DetPOMDP ℳ~ M with state space S×[n]S×[n]. By (Littman, 1996), this POMDP ℳ~ M will have an optimal policy with representation-size polynomial in n|S|n|S|, |A||A|, |Z||Z| and H. These polynomially sized policies form the set Π _C of policies for the class C of deterministic POMDPs. Thus, to determine if a ME-POMDP with deterministic dynamics has a policy with value at least B, we can guess n policies from Π _C and solve an LP, all in polynomial time. ∎ Corollary 5.5. The value problem for ME-BlindMDPs is in . Proof Sketch. Any optimal policy for a BlindMDP comprises a sequence of actions. Also, mixing over a set of BlindMDPs (ℳi)i∈[n](M_i)_i∈[n] results in another BlindMDP ℳ~ M. Thus, by the same argument as Corollary 5.4, we can guess and check a randomized policy in polynomial time. ∎ The above corollaries settle the complexity of all deterministic ME-POMDP subclasses we consider, and we additionally obtain our first instance of an -complete ME-POMDP problem with stochastic dynamics. However, the above mixture reasoning fails for subclasses such as SOMDPs, as they are not closed under mixtures. Similarly, Proposition 5.3 does not apply to restricted policy classes, as a mixture over deterministic time-dependent Markovian policies may not be a time-dependent Markovian policy. 6. Multi-Observation POMDPs We next present hardness results for subclasses where the mixture reasoning of Section 5 fails. We identify subclasses that reside in P or in the single-environment case, but become -complete when we examine the relevant multi-observation problem. In identifying these subclasses, we expand the range of -hard multi-environment problems beyond known examples such as ME-MDPs (Le Tallec, 2007). Full proofs reside in Appendix F. First, we observe that multi-observation MDPs (MO-MDPs) are -hard despite the significant structure of their observation functions. A MO-MDP comprises a set of MDPs with the same dynamics but potentially different state labelings. We demonstrate that shuffling this state labeling is sufficient to simulate partial observability and thus recover -hardness. Proposition 6.1. The value problem for MO-MDPs is -hard. Proof Sketch. In the classical proof of -hardness for POMDPs (Papadimitriou and Tsitsiklis, 1987), one transforms a QSAT instance to a POMDP in which nature randomly selects one of m clauses in the conjunctive normal form (CNF) formula at the initial time step, and then uses randomness to assign values to universal variables (Papadimitriou and Tsitsiklis, 1987). The agent cannot observe the chosen clause and must therefore use a clause-independent policy to choose existential variables so the formula remains true for any universal variable assignment. We simulate this partial observability in MO-MDPs using multiple state labelings. We first design a reference environment with the same transition structure as the above POMDP, where states corresponding to clause l emit observations in some set ZlZ_l, for l∈[m]l∈[m]. We then define m−1m-1 new environments, where, in environment k, states corresponding to clause l emit observations in the set Zl+kZ_l+k. We can then extract a clause-independent assignment strategy by examining the agents’ behavior on observations in the set Z1Z_1, since for any clause l, there exists an environment in which the corresponding states emit observations in Z1Z_1. ∎ This shuffling trick fails if we assume the observation function’s support is fixed between environments. However, as we next demonstrate, fixed-support models can still exhibit -hardness. Even with fixed supports, multi-observation semi-observable MDPs remain -complete. We again prove this result by adapting the proof of (Papadimitriou and Tsitsiklis, 1987), by letting the agent and the environment alternately choose binary variables in a CNF formula. We design an environment for each clause, and we design environment i so that satisfying clause i reveals information that helps the agent reach an accepting state. Proposition 6.2. The value problem for MO-SOMDPs with fixed support is -hard. Proof Sketch. We design an environment corresponding to each clause in a CNF formula with n variables. In particular, fix a clause i. The POMDP for clause i has 2n2n stages: odd stages correspond to variable assignment, and even stages correspond to a guessing game in which the agent can reach an accepting state. At variable assignment stages, either the environment or the agent chooses a variable assignment, as in (Papadimitriou and Tsitsiklis, 1987). At the guessing game stage, an unbiased coin is flipped, which the agent must identify to reach an accepting state. If the last variable assignment satisfied clause i, the environment reveals the state, and thus the coin value, with high probability. Conversely, if the last variable assignment did not set the clause to true, the state remains hidden with high probability. In this MO-POMDP, policies that eventually reveal the coin’s value with high probability correspond to strategies that satisfy the given QSAT instance. Conversely, given a QSAT solution, we can build a POMDP policy that reveals the information with sufficiently high probability. This multi-environment problem is also a MO-SOMDP with fixed support. At the variable assignment stages, we can reveal the true state in all environments. In the guessing game states, two observations are possible in all environments: the blind observation and the state’s unique observation. ∎ Unlike SOMDPs, however, IOMDPs have sufficient structure to avoid -hardness. In an IOMDP, every state has an equal revelation probability. This structure in turn gives MO-IOMDPs certain monotonicity properties (Chen and Liew, 2026), which allow us to solve the MO-IOMDP by identifying and solving the worst environment, i.e., the environment with the lowest revelation probability. Proposition 6.3. The value problem for MO-IOMDPs with fixed support is in . Proof Sketch. Increasing the revelation probability in an MO-IOMDP cannot decrease the reward. In particular, fix a transition function, and let πλ _λ be the optimal policy for a given revelation probability λ. By Corollary 1 in (Chen and Liew, 2026), increasing the revelation probability to λ′λ increases the expected reward for πλ _λ. Thus, to solve the MO-IOMDP problem, we merely need to guess and check an optimal policy for an IOMDP, which we can do efficiently by following the reasoning used to prove Proposition 4.2. ∎ This last result provides an instance of a MO-POMDP problem with stochastic dynamics and a non-trivial observation function that avoids -hardness. However, the associated monotonicity property is a stringent condition on the MO-POMDP. 7. Restricted Policy Classes We next demonstrate that a range of restricted policy class problems that are -complete for POMDPs are -complete when we move to the ME-POMDP setting. Full proofs reside in Appendix G. 7.1. Markovian Policies The difficulty of finding time-dependent Markovian policies for ME-POMDPs lies in reasoning about decoupled randomness. When finding time-dependent Markovian policies in POMDPs, we can assume the policy is deterministic, i.e., in Π _ det, and guess a policy in polynomial time. However, optimal ME-POMDP policies generally require randomness. One might try to solve the ME-POMDP problem by reasoning about mixtures over deterministic Markovian policies, as in Section 5. However, a mixture of deterministic Markovian policies may not be a Markovian policy, i.e., Π⊊Δ(Π∩Π) _ MR ( _ det∩ _ MR). In particular, the class of time-dependent Markovian policies requires that the randomness be decoupled across time steps, creating problems that are known across game theory and distributed systems; see, e.g. (Brice et al., 2026b; Hansen et al., 2008; Borgs et al., 2008; Celli and Gatti, 2018). For all the subclasses we consider, the time-dependent Markovian policy problem for ME-POMDPs is -hard. In a ME-BlindMDP, the agent’s strategy comprises a sequence of action distributions, one for each time step. We can establish hardness results by viewing each time step as a player on a team. That is, finding a time-dependent Markovian strategy in a ME-BlindMDP means finding a set of mixed strategies for a team to use against an adversary, where team members can not correlate their randomness. Finding optimal team strategies in such games is -hard. Proposition 7.1. The time-dependent Markovian policy problem for deterministic ME-BlindMDPs is -hard. Proof Sketch. We reduce 22-vs.-11 team matrix games with two players, known to be -hard (Brice et al., 2026b; Berthelsen and Hansen, 2022; Hansen, 2019), to ME-BlindMDPs. ∎ In the proof for ME-BlindMDPs, we store the agent’s first action in the state, which prevents the result from generalizing to ME-MDPs because the agent can then use this information at the next time step, even with a Markovian policy. However, we can resolve this issue using a state-relabeling construction. Proposition 7.2. The time-dependent Markovian policy problem for deterministic multi-environment MDPs is -hard. Proof Sketch. Similar to the proof of Proposition 7.1, we encode team matrix games in ME-MDPs. However, we add additional environments that differ in state-space labeling, preventing the agent from using state observations at the second time step to create correlations between actions at different time steps. ∎ Propositions 7.2 and 7.1 establish -hardness for all the multi-environment problems we consider. We can also prove -hardness for the multi-observation problem by changing the observation function to control the agent’s actions and simulate an adversary. Proposition 7.3. The time-dependent Markovian policy problem for multi-observation POMDPs is -hard. Proof Sketch. The proof begins with the same reduction as in the proof of Proposition 7.1. However, the environment can no longer modify the transition or reward functions. To address this difficulty, we add a component to the problem in which certain observations are revealed conditional on the agent taking a certain action in each environment. Adding this component then allows the adversary to control the environment dynamics by incentivizing the agent to take certain actions. ∎ We can also easily express the time-dependent Markovian policy problem in . Indeed, we parameterize the policy with |Z||A|H|Z||A|H variables and encode the dynamics as bilinear constraints linking ℙ[st+1=s]P[s_t+1=s] to (ℙ[st=s,at=a])a∈A,s∈S(P[s_t=s,a_t=a])_a∈ A,s∈ S. Lemma 7.4. The time-dependent Markovian policy problem for ME-POMDPs is in . Proof Sketch. This result follows from standard encodings of robust POMDP problems as non-linear constrained optimization problems, for example as in (Cubuktepe et al., 2021). Critically, because the ME-POMDP comprises a finite set of POMDPs, the -encoding is finite. ∎ 7.2. Policies with Finite Memory Next, we show a counter-intuitive relationship between memory and complexity in ME-POMDPs. For any memory size, the value problem for time-dependent FSCs in POMDPs lies in . In contrast, we show that ME-POMDPs exhibit a cutoff phenomenon, in which the complexity of the FSC problem depends on the ratio of memory size to the number of environments. We adapt the FSC value problem (Problem 2) with a fixed rational parameter α. Problem 3 (α-FSC value problem). Given a ME-POMDP (ℳi)i∈[n](M_i)_i∈[n], a rational number B, and a memory bound |Q||Q| polynomial in the ME-POMDP size that satisfies |Q|≥αn|Q|≥α n, the α-FSC value problem asks whether there exists a time-dependent FSC π such that V(ℳi)i∈[n]π≥BV_(M_i)_i∈[n]^π≥ B. Setting α=1α=1 gives the set of all FSC-problems where the memory bound is at least the number of environments. For certain subclasses of ME-POMDPs, increasing α past a certain threshold drops the complexity of the α-parameterized problem from -complete to -complete, as we show next. Blind MDPs For ME-BlindMDPs, FSC synthesis is -complete when we restrict the FSC size to exceed the number of environments, as we recover the problem with no policy constraints. Lemma 7.5. For α=1α=1, the α-FSC value problem for ME-BlindMDPs is -complete. Proof. Let n be the number of environments in the ME-BlindMDP. By Proposition 5.3, the ME-BlindMDP has an optimal policy that randomizes over n action sequences of length H. We can encode this policy in an FSC with |Q||Q| states, since by assumption |Q|≥n|Q|≥ n, so we can use the memory to index the sequence and use γt _t to encode the n action sequences. Thus, solving the memory-constrained ME-BlindMDP problem is equivalent to solving the ME-BlindMDP problem without policy constraints. The latter problem is in by Corollary 5.5, and -hard as Blind MDPs are -hard (Papadimitriou and Tsitsiklis, 1987). ∎ Lemma 7.5 raises the problem of identifying the α value at which complexity drops from to . As we show below, α=1α=1 is tight, in the sense that the FSC policy existence problem is -complete for any smaller value of α. This result follows from the fact that, when α<1α<1, we can encode -hard low-non-negative-rank feasibility problems in the time-dependent FSC problem. Theorem 7.6. For any fixed rational α∈(0,1)α∈(0,1), the α-FSC value problem for ME-BlindMDPs is -complete. Proof Sketch. We prove this result by linking the existence of time-dependent finite-state controllers to solving certain non-negative-rank-constrained feasibility problems. We first show a one-to-one correspondence between time-dependent FSC controllers with |Q||Q| states and inter-time-step joint action distributions with non-negative rank less than |Q||Q| (Vavasis, 2009). We can then build a ME-POMDP that has a non-negative value if and only if a joint action distribution exists satisfying a set of linear constraints, where each action distribution corresponds to a matrix with low non-negative rank. Finally, we adapt existing results on the complexity of non-negative rank-constrained feasibility (Majumdar, 2026) to show that deciding whether such a rank-constrained distribution exists is -hard. Critically, in adapting this result, we must carefully control the relationship between the memory size |Q||Q| and the number n of environments in the instance we build. ∎ The above results demonstrate a tradeoff between computation at planning and deployment time, whereby we can increase the memory size to reduce the complexity of the planning problem. General POMDPs For general POMDPs, the α-FSC value problem is -hard even for α=1α=1, and thus generally harder than for BlindMDPs. In effect, introducing non-trivial observation functions allows one to construct ME-POMDPs where the observations consume all the agent’s memory, so the agent cannot couple its actions across time steps at all. Proposition 7.7. For α=1α=1, the α-FSC value problem for ME-POMDPs is -complete. Proof Sketch. We use the same techniques as in Proposition 7.1. However, we add a randomly drawn state component to the environment, and we set the rewards so agent must remember this state component to avoid negative reward. This component exhausts the agent’s memory so that it must draw actions at other timesteps independently, allowing us to simulate the 2-vs.-1 matrix game. ∎ It remains an open problem whether there are lower bounds on |Q||Q| in terms of n, or other ME-POMDP parameters, such that the α-FSC value problem becomes -complete. 8. Conclusion We established a range of new complexity results for finite-horizon ME-POMDPs across subclasses of POMDPs. Our results show that some POMDP subclasses remain tractable when extended to the multi-environment setting. Future work will extend complexity characterizations to more subclasses and examine infinite-horizon and logic-based objectives. Acknowledgements. Nils Jansen was supported by the ERC Starting Grant DEUCE (101077178). Marnix Suilen was supported by Research Foundation Flanders (FWO) Junior Postdoctoral Fellowship grant 12ALH27N (IDEAS in POMDPs). Caleb Probine and Ufuk Topcu were funded in part by the Air Force Office of Scientific Research (AFOSR) under grant number FA9550-22-1-0403, and by the Office of Naval Research (ONR) under grant number N00014-24-1-2797. References Abrahamsen et al. (2022) M. Abrahamsen, A. Adamaszek, and T. Miltzow The art gallery problem is ∃ℝR-complete. Vol. 69, p. 4:1–4:70. Cited by: Definition G.3. Abrahamsen and Miltzow (2019) M. Abrahamsen and T. Miltzow Dynamic toolbox for ETRINV. CoRR abs/1912.08674. Cited by: §G.2.1, §G.2.1, Definition G.3, Lemma G.5. Ahluwalia et al. (2021) V. S. Ahluwalia, L. N. Steimle, and B. T. Denton Policy-based branch-and-bound for infinite-horizon multi-model Markov decision processes. Comput. Oper. Res. 126, p. 105108. Cited by: §2. Asadi et al. (2026) A. Asadi, K. Chatterjee, D. Lurie, and R. Saona Revealing POMDPs: qualitative and quantitative analysis for parity objectives. In AAAI, p. 36146–36154. Cited by: §1, §4.1. Bagnell et al. (2003) J. A. Bagnell, S. M. Kakade, A. Y. Ng, and J. G. Schneider Policy search by dynamic programming. In NIPS, p. 831–838. Cited by: §D.4, §4.3, §4.3. Başar and Olsder (1998) T. Başar and G. J. Olsder Dynamic noncooperative game theory. SIAM. Cited by: §E.1, §5. Basich et al. (2022) C. Basich, J. R. Peterson, and S. Zilberstein Planning with intermittent state observability: knowing when to act blind. In IROS, p. 11657–11664. Cited by: §4.1. Belly et al. (2025) M. Belly, N. Fijalkow, H. Gimbert, F. Horn, G. A. Pérez, and P. Vandenhove Revelations: A decidable class of POMDPs with omega-regular objectives. In AAAI, p. 26454–26462. Cited by: §1, §4.1. Berthelsen and Hansen (2022) M. L. T. Berthelsen and K. A. Hansen On the computational complexity of decision problems about multi-player nash equilibria. Theory Comput. Syst. 66 (3), p. 519–545. Cited by: §7.1. Bertsekas et al. (2003) D. Bertsekas, A. Nedic, and A. Ozdaglar Convex analysis and optimization. Vol. 1, Athena Scientific. Cited by: §E.1, §E.1. Besse and Chaib-draa (2009) C. Besse and B. Chaib-draa Quasi-deterministic partially observable Markov decision processes. In ICONIP (1), Lecture Notes in Computer Science, Vol. 5863, p. 237–246. Cited by: §4.1. Bonet (2009) B. Bonet Deterministic POMDPs revisited. In UAI, p. 59–66. Cited by: §4.2. Bordais and Raskin (2026) B. Bordais and J. Raskin Multi-environment MDPs with prior and universal semantics. In ICALP, LIPIcs, Vol. 374, p. 171:1–171:15. Cited by: §2, §5. Borgs et al. (2008) C. Borgs, J. Chayes, N. Immorlica, A. T. Kalai, V. Mirrokni, and C. Papadimitriou The myth of the folk theorem. In Proceedings of the fortieth annual ACM symposium on Theory of computing, p. 365–372. Cited by: §7.1. Bovy et al. (2025) E. M. Bovy, C. Probine, M. Suilen, U. Topcu, and N. Jansen Multi-environment POMDPs: discrete model uncertainty under partial observability. In NeurIPS, Cited by: §1, §2. Brice et al. (2026a) L. Brice, F. Cano, K. Chatterjee, T. A. Henzinger, and S. Muroya Multi-environment POMDPs with finite-horizon objectives. CoRR abs/2605.07537. Cited by: §B.1, §E.1, §1, §1, §2, §5. Brice et al. (2026b) L. Brice, T. A. Henzinger, and K. S. Thejaswini Dicey games: shared sources of randomness in distributed systems. In LICS, LIPIcs, Vol. 380, p. 23:1–23:26. Cited by: §G.1, §7.1, §7.1. Celli and Gatti (2018) A. Celli and N. Gatti Computational results for extensive-form adversarial team games. In AAAI, p. 965–972. Cited by: §7.1. Chatterjee et al. (2010) K. Chatterjee, L. Doyen, and T. A. Henzinger Qualitative analysis of partially-observable Markov decision processes. In MFCS, Lecture Notes in Computer Science, Vol. 6281, p. 258–269. Cited by: §4.1. Chatterjee et al. (2025) K. Chatterjee, L. Doyen, J. Raskin, and O. Sankur The value problem for multiple-environment MDPs with parity objective. In ICALP, LIPIcs, Vol. 334, p. 150:1–150:17. Cited by: §2. Chen and Liew (2026) G. Chen and S. C. Liew Intermittently observable Markov decision processes. IEEE Trans. Autom. Control. 71 (2), p. 1054–1069. Cited by: §F.3, §F.3, §F.3, Lemma F.1, §4.1, §6, §6. Cubuktepe et al. (2021) M. Cubuktepe, N. Jansen, S. Junges, A. Marandi, M. Suilen, and U. Topcu Robust finite-state controllers for uncertain POMDPs. In AAAI, p. 11792–11800. Cited by: §7.1. Ding and Rhee (2014) J. Ding and N. H. Rhee When a matrix and its inverse are nonnegative. Missouri Journal of Mathematical Sciences 26 (1), p. 98–103. Cited by: §G.3, Lemma G.7. Fijalkow et al. (2026) N. Fijalkow, A. Ghosh, R. Kniazev, G. A. Pérez, and P. Vandenhove Computing the reachability value of posterior-deterministic POMDPs. CoRR abs/2602.07473. Cited by: §4.1. Galesloot et al. (2025) M. F. L. Galesloot, R. Andriushchenko, M. Ceska, S. Junges, and N. Jansen Robust finite-memory policy gradients for hidden-model POMDPs. In IJCAI, p. 8518–8526. Cited by: §1. Golowich et al. (2022) N. Golowich, A. Moitra, and D. Rohatgi Planning in observable POMDPs in quasipolynomial time. CoRR abs/2201.04735. Cited by: §4.1. Hansen et al. (2008) K. A. Hansen, T. D. Hansen, P. B. Miltersen, and T. B. Sørensen Approximability and parameterized complexity of minmax values. In WINE, Lecture Notes in Computer Science, Vol. 5385, p. 684–695. Cited by: §7.1. Hansen (2019) K. A. Hansen The real computational complexity of minmax value and equilibrium refinements in multi-player games. Theory Comput. Syst. 63 (7), p. 1554–1571. Cited by: §G.1, §G.3, §7.1. Hauskrecht and Fraser (2000) M. Hauskrecht and H. S. F. Fraser Planning treatment of ischemic heart disease with partially observable Markov decision processes. Artif. Intell. Medicine 18 (3), p. 221–244. Cited by: §1. Hudák et al. (2026) D. Hudák, M. F. L. Galesloot, M. Tappler, M. Kurecka, N. Jansen, and M. Ceska Finite-state controllers for (hidden-model) POMDPs using deep reinforcement learning. In AAMAS, p. 1201–1210. Cited by: §1. Junges et al. (2018) S. Junges, N. Jansen, R. Wimmer, T. Quatmann, L. Winterer, J. Katoen, and B. Becker Finite-state controllers of POMDPs using parameter synthesis. In UAI, p. 519–529. Cited by: §B.1, §4.3. Kaelbling et al. (1998) L. P. Kaelbling, M. L. Littman, and A. R. Cassandra Planning and acting in partially observable stochastic domains. Artif. Intell. 101 (1-2), p. 99–134. Cited by: §1. Karmarkar (1984) N. Karmarkar A new polynomial-time algorithm for linear programming. In STOC, p. 302–311. Cited by: §E.2. Khachiyan (1980) L. G. Khachiyan Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics 20 (1), p. 53–72. Cited by: §E.2. Koller and Megiddo (1992) D. Koller and N. Megiddo The complexity of two-person zero-sum games in extensive form. Games and economic behavior 4 (4), p. 528–552. Cited by: §2. Kuhn (1953) H. W. Kuhn Extensive games and the problem of information. Contributions to the Theory of Games 2 (28), p. 193–216. Cited by: §F.1, §3.1. Kurniawati (2022) H. Kurniawati Partially observable Markov decision processes and robotics. Annu. Rev. Control. Robotics Auton. Syst. 5, p. 253–277. Cited by: §1. Le Tallec (2007) Y. Le Tallec Robust, risk-sensitive, and data-driven control of Markov decision processes. Ph.D. Thesis, Massachusetts Institute of Technology. Cited by: §2, §6. Li (2026) Y. Li Computational hardness of static distributionally robust Markov decision processes. Oper. Res. Lett. 67, p. 107465. Cited by: §2. Littman (1996) M. L. Littman Algorithms for sequential decision-making. Brown University. Cited by: §E.2, §E.2, §2, §4.2, §5, §5. Madani et al. (2003) O. Madani, S. Hanks, and A. Condon On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell. 147 (1-2), p. 5–34. Cited by: §1, §4.1, §4.1. Majumdar (2026) A. Majumdar Constrained nonnegative gram feasibility is ∃ -complete. CoRR abs/2603.19976v1. Cited by: §G.2.1, §G.2.1, §G.2.1, §G.2.1, §G.2.1, §G.2.1, §G.2.1, Lemma G.6, §7.2. Meuleau et al. (1999) N. Meuleau, K. Kim, L. P. Kaelbling, and A. R. Cassandra Solving POMDPs by searching the space of finite policies. In UAI, p. 417–426. Cited by: §4.3. Mundhenk et al. (2000) M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender Complexity of finite-horizon Markov decision process problems. J. ACM 47 (4), p. 681–720. Cited by: §B.1, §4.1, §4.2, §4.2, §4.2, §4.2, §4.3. Papadimitriou and Tsitsiklis (1987) C. H. Papadimitriou and J. N. Tsitsiklis The complexity of Markov decision processes. Math. Oper. Res. 12 (3), p. 441–450. Cited by: §D.1, §D.1, §D.3, §D.3, §F.1, §F.1, §F.1, §F.1, §F.1, §1, §1, §2, §3.3, §4.1, §4.2, §6, §6, §6, §7.2, footnote 1. Papadimitriou (1994) C. H. Papadimitriou Computational complexity. Addison-Wesley. Cited by: §3. Poupart and Boutilier (2003) P. Poupart and C. Boutilier Bounded finite state controllers. In NIPS, p. 823–830. Cited by: §4.3. Puterman (1994) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Statistics, Wiley. Cited by: §4.1. Raskin and Sankur (2014) J. Raskin and O. Sankur Multiple-environment Markov decision processes. In FSTTCS, LIPIcs, Vol. 29, p. 531–543. Cited by: §1, §2. Schaefer et al. (2024) M. Schaefer, J. Cardinal, and T. Miltzow The existential theory of the reals as a complexity class: A compendium. CoRR abs/2407.18006. Cited by: §G.2.1, §3. Shitov (2016) Y. Shitov A universality theorem for nonnegative matrix factorizations. arXiv preprint arXiv:1606.09068. Cited by: §G.2.1. Steimle et al. (2021) L. N. Steimle, V. S. Ahluwalia, C. Kamdar, and B. T. Denton Decomposition methods for solving Markov decision processes with multiple models of the parameters. IISE Trans. 53 (12), p. 1295–1310. Cited by: §2. Suilen et al. (2024) M. Suilen, M. van der Vegt, and S. Junges A PSPACE algorithm for almost-sure Rabin objectives in multi-environment MDPs. In CONCUR, LIPIcs, Vol. 311, p. 40:1–40:17. Cited by: §2. van der Vegt et al. (2023) M. van der Vegt, N. Jansen, and S. Junges Robust almost-sure reachability in multi-environment MDPs. In TACAS (1), Lecture Notes in Computer Science, Vol. 13993, p. 508–526. Cited by: §2. Vavasis (2009) S. A. Vavasis On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20 (3), p. 1364–1377. Cited by: Definition G.1, §7.2. Appendix A Statement on the use of Artificial Intelligence A.1. Expanding literature searches We used large language models to supplement search keywords for literature review. In particular, when searching for literature in areas where search terms were unclear, we used generative models to suggest keywords and search strategies that could be useful for finding papers. We then used these keywords in Google Scholar searches to see whether they yielded new papers that added context to our related work. Examples of prompts provided to ChatGPT are as follows. (1) “ What are terms for optimization subject to constraints that take the form of “A must have a non-negative factorization with dimension k” ” (2) “ Consider the following setup for a partially observable stochastic game 1. P1 has full observability 2. P1 moves only at the first time step 3. P2 then plays the rest of the game with some partial observability. Such games are naturally a subclass of extensive-form games, partially observable stochastic games (POSGs), and games on graphs. What theoretical complexity results exist for such games, and what might they have been called? ” LLM-generated text from keyword generation does not directly appear in the paper. Instead, we used the generated keywords in Google Scholar searches to expand the set of papers we examined when contextualizing our work. When generative models suggested papers, we first sourced them via Google Scholar and read them to identify the results they claimed. A.2. Identifying folklore results We also used language models to identify canonical references for folklore results. For example, it is well-known that many different formalisms for POMDPs that differ slightly are actually equivalent. For example, it is well-known that one can transform a POMDP with stochastic observations into one with deterministic observations. Literature on such folklore results, however, is difficult to find via standard search techniques. While one can easily prove these results, we used ChatGPT to try to identify proofs of such folklore results in the literature so they could be referenced. An example of a prompt used for this purpose when developing the paper is as follows. • “Can you find a POMDP paper that gives the polytime reduction from POMDPs with state-action-based observations to state-based observation functions” When ChatGPT suggested such papers, we again confirmed their existence and read them to determine what results they actually contained. The particular models used to generate the responses include GPT-5.6-Luna, GPT-5.5, and GPT-5.5-Mini. Appendix B Additional preliminaries For a vector u we use [i]u[i] or (i)u(i) to denote the ithi^th element, and ⊤u denotes its transpose. The entry-wise 11 norm of a matrix P∈ℝm×nP ^m× n is ∥P∥1,1=∑i∈[m],j∈[n]|P[i,j]| P _1,1= _i∈[m],j∈[n]|P[i,j]|, and similarly for a vector ∥1=∑i∈[n]|[i]| _1= _i∈[n]|u[i]|. We use i∈ℝne_i ^n to denote the standard basis vector with a one at entry i and zeros elsewhere, and 1 is the all-ones vector. For a pair of matrices P,Q∈ℝm,nP,Q ^m,n, ⟨P,Q⟩ P,Q is the element-wise product ∑i∈[m],j∈[n]P[i,j]Q[i,j] _i∈[m],j∈[n]P[i,j]Q[i,j]. Paths of length H Given a horizon H, we evaluate the reward on paths of the shape ρ=s0,a0,…,sH−1,aH−1ρ=s_0,a_0,…,s_H-1,a_H-1. Although the final state-action pair (sH−1,aH−1)(s_H-1,a_H-1) still induces a distribution on the successor state sHs_H, we ignore this state, as it does not contribute anything to the finite-horizon reward ∑t=0H−1R(st,at) _t=0^H-1R(s_t,a_t). Definition B.1 (Belief update). Given a belief b, an action a, and observation z, we compute the successor belief b′b using the belief update function bupd:Δ(S)×A×Z→Δ(S)b_upd (S)× A× Z→ (S), which we define as follows. b′(s′) b (s ) =bupd(b,a,z)(s′), =b_upd(b,a,z)(s ), =O(s′,z)∑s∈Sb(s)⋅T(s,a,s′)∑s′∈SO(s′,z)∑s∈Sb(s)⋅T(s,a,s′). = O(s ,z) _s∈ Sb(s)· T(s,a,s ) _s ∈ SO(s ,z) _s∈ Sb(s)· T(s,a,s ). Belief update at t=0t=0 Although we are given an initial belief, we also receive an observation of the initial state. Upon receiving this observation, we perform a belief update without action: bupd(b0,⋅,z0)(s) b_upd(b_0,·,z_0)(s) =O(s,z0)b0(s)∑s∈SO(s,z0)b0(s). = O(s,z_0)b_0(s) _s∈ SO(s,z_0)b_0(s). Additional policy types We next list some additional types of policies that we use in proofs in this appendix. Definition B.2 (Belief-based policies). A time-dependent belief-based policy maps tuples of distributions over states and time to distributions over actions. Formally, a belief-based policy is a function π:Δ(S)×0,…,H−1→Δ(A).π (S)×\0,…,H-1\→ (A). Definition B.3 (Observation-based policies). An observation-based policy maps sequences of observations to distributions over actions, i.e. π:⋃t=1HZt→Δ(A).π _t=1^HZ^t→ (A). B.1. Supporting lemmas We will repeatedly need to evaluate time-dependent Markovian policies as a subroutine in the algorithms we provide, and as such, we provide the following lemma on the evaluation of deterministic time-dependent Markovian policies in POMDPs. In particular, for an arbitrary POMDP ℳM, we can evaluate a deterministic time-dependent Markovian policy π in polynomial time, and furthermore, the representation of the expected reward of this policy is polynomial in the size of the POMDP. We remark that existing work details polynomial-time procedures for policy evaluation in POMDPs when probabilities are represented with binary fractions, and observation functions are deterministic (Mundhenk et al., 2000). For completeness, we provide the following lemma, which handles stochastic observation functions and explicitly bounds the reward’s representation size. Lemma B.4. There exists an algorithm that takes a POMDP ℳ=(S,A,Z,T,O,R,b,H)M=(S,A,Z,T,O,R,b,H) and a deterministic time-dependent Markovian policy (πt)t∈0,…,H−1( _t)_t∈\0,…,H-1\ and evaluates the expected reward ℳπ[∑t=0H−1R(st,at)]E_M^π [ _t=0^H-1R(s_t,a_t) ] in polynomial time in the representation size N of the POMDP ℳM. Furthermore, the bit lengths of the integers required to represent ℳπ[∑t=0H−1R(st,at)]E_M^π [ _t=0^H-1R(s_t,a_t) ] are bounded by a polynomial in N. Proof. Before proceeding, we argue that we can process any POMDP instance so that all rationals share a common denominator. We also argue that this procedure runs in polynomial time in the POMDP instance size. In particular, we can argue in a similar manner to the proof of Lemma 22 in (Brice et al., 2026a), and following the notation in (Brice et al., 2026a), we use N to denote the representation size of the ME-POMDP problem. We enumerate all rational numbers (qk)k∈[K](q_k)_k∈[K] in the POMDP’s representation, (3) x1/y1⏟q1,…,xK/yK⏟qK, x_1y_1_q_1,…, x_Ky_K_q_K, where K≤K is the number of rational numbers in the POMDP’s encoding which are used to represent transition functions, observation functions, rewards and initial state distributions. Clearly, we can rewrite the rational number qlq_l as (4) ql=xl∏l′∈[K]:l′≠lyl′∏l′∈[K]yl′=XlC,q_l= x_l _l ∈[K]:l ≠ ly_l _l ∈[K]y_l = X_lC, where Xl:-xl∏l′∈[K]:l′≠lyl′X_l x_l _l ∈[K]:l ≠ ly_l , and C:-∏l′∈[K]yl′C _l ∈[K]y_l . Furthermore, if the POMDP has an N-bit representation, then we have |xl|≤2|x_l|≤ 2^N and |yl|≤2|y_l|≤ 2^N for all l∈[K]l∈[K], which implies that |Xl|≤22|X_l|≤ 2^N^2 and |C|≤22|C|≤ 2^N^2. Computing each XlX_l along with the constant C comprises multiplying K≤K integers each with bit length bounded above by N. Thus, we can compute this common-denominator representation in polynomial time in the POMDP size. To evaluate the memoryless policy (πt)t∈0,…,H−1( _t)_t∈\0,…,H-1\, we first evaluate the following expressions which encode the probability of being at each state at each time. p0(s)=b(s) p_0(s)=b(s) ∀s∈S ∀ s∈ S pt+1(s)=∑s′∈Spt(s′)∑z∈ZT(s′,πt(z))(s)O(s′)(z) p_t+1(s)= _s ∈ Sp_t(s ) _z∈ ZT(s , _t(z))(s)O(s )(z) ∀s∈S,t∈0,…,H−2. ∀ s∈ S,t∈\0,…,H-2\. We can then argue, by induction, that the probabilities (pt(s))s∈S(p_t(s))_s∈ S have C2t+1C^2t+1 as a denominator. Trivially, we can represent the probability p0(s)p_0(s) as a rational with denominator C for each s∈Ss∈ S. Then, assume that pt(s)=ws(t)C2t+1p_t(s)= w_s^(t)C^2t+1 for all s∈Ss∈ S , where ws(t)∈0,…,C2t+1w_s^(t)∈\0,…,C^2t+1\ for each s. Then, for each s, we have (5) pt+1(s)=∑s′∈Sws′(t)C2t+1∑z∈Zus′πt(z)sCvs′zC=ws(t+1)C2(t+1)+1p_t+1(s)= _s ∈ S w_s ^(t)C^2t+1 _z∈ Z u_s _t(z)sC v_s zC= w_s^(t+1)C^2(t+1)+1 for some ws(t+1)∈0,…,C2(t+1)+1w_s^(t+1)∈\0,…,C^2(t+1)+1\, where T(s′,a,s)=us′as/CT(s ,a,s)=u_s as/C for each s′,s∈Ss ,s∈ S, and a∈Aa∈ A, and O(s′,z)=vs′z/CO(s ,z)=v_s z/C for each s′∈S,z∈Zs ∈ S,z∈ Z. We can also evaluate (pt(s))t∈0,…,H1(p_t(s))_t∈\0,…,H_1\ in polynomial time. First, note that C2(t+1)+1≤22(2H+1)≤233C^2(t+1)+1≤ 2^N^2(2H+1)≤ 2^3N^3, which implies that each integer ws(t)w_s^(t) has at most 333N^3 bits. To compute each of the |S|(H−1)|S|(H-1) values ws(t+1)w_s^(t+1), we need to compute ∑s′∈S,z∈Zws′(t)us′πt(a)svs′z _s ∈ S,z∈ Zw_s ^(t)u_s _t(a)sv_s z, which can clearly be done in polynomial time, since each ws′(t)w_s ^(t) has at most 333N^3 bits, and each of the u and v values has at most 2N^2 bits. The expected reward for the memoryless policy is (6) ℳπ[∑t=0H−1R(st,at)]=∑t=0H−1∑s∈S,z∈Zpt(s)O(s)(z)R(s,π(z))=∑t=0H−1∑s∈S,z∈ZC2(H−t)ws(t)C2H+1vszCκsπt(z)C,E_M^π [ _t=0^H-1R(s_t,a_t) ]= _t=0^H-1 _s∈ S,z∈ Zp_t(s)O(s)(z)R(s,π(z))= _t=0^H-1 _s∈ S,z∈ Z C^2(H-t)w_s^(t)C^2H+1 v_szC _s _t(z)C, where we assume R(s,a)=κ(s,a)/CR(s,a)= κ(s,a)C for each s∈Ss∈ S and a∈Aa∈ A. Again, we can compute the sum in polynomial time, as all of the integers in the above expression have representation length bounded by a fixed polynomial in N. We can also observe that the expected reward is equal to ξ/(C2H+3) ξ(C^2H+3) for some integer ξ, which we now bound. In particular, since the expected reward is bounded above by Hmaxs,a|R(s,a)|H _s,a|R(s,a)|, we have (7) |ξ(C2H+3)|≤Hmaxs∈S,a∈A|R(s,a)|≤Hmaxl∈K|Xl|C, | ξ(C^2H+3) |≤ H _s∈ S,a∈ A|R(s,a)|≤ H _l∈ K|X_l|C, which implies that ξ≤HC2H+2maxl∈[K]|Xl|≤H22(2H+2)22≤H25H2≤263.ξ≤ HC^2H+2 _l∈[K]|X_l|≤ H2^N^2(2H+2)2^N^2≤ H2^5HN^2≤ 2^6N^3. Thus, from the bounds on C and ξ, we deduce the polynomial bit-length condition for the policy’s expected reward. ∎ Next, we discuss a correspondence between FSCs on POMDPs and Markovian policies on a product POMDP. This correspondence is well known, and mirrors the transformation from time-independent FSC-synthesis to memoryless policy synthesis in a product POMDP (Junges et al., 2018). We give a proof here for completeness in handling the time-dependent details. Lemma B.5. Fix a POMDP ℳ=(S,A,Z,T,O,R,b,H)M=(S,A,Z,T,O,R,b,H), and a memory size |Q||Q|. In deterministic polynomial time, we can construct an extended POMDP ℳ′M such that there exists a correspondence between (1) the set of time-dependent FSCs with |Q||Q| states in the POMDP ℳM, and (2) the set of time-dependent Markovian policies in an expanded POMDP ℳ′M , such that for every time-dependent FSC with |Q||Q| states in the POMDP ℳM, there exists a time-dependent Markovian policy in an expanded POMDP ℳ′M that achieves the same reward, and vice versa. Furthermore, this policy translation procedure can be done in polynomial time in the policy’s representation size. Furthermore, if the time-dependent Markovian policy π′π in the expanded POMDP ℳ′M is deterministic, then there exists a deterministic time-dependent FSC with |Q||Q| states in ℳM with the same reward. Proof. Define a POMDP ℳ′M with (8) ℳ′=(s⊥∪S×Q⏟S′,A×Q⏟A′,Z×Q⏟Z′,T′,O′,R′,b′,H+1),M =( \s_ \∪ S× Q_S , A× Q_A , Z× Q_Z ,T ,O ,R ,b ,H+1), where we denote the augmented state space as S′S , the augmented action space as A′A and the augmented observation space as Z′Z . The state s⊥s_ is a dummy state, included to allow a random initial FSC state. The transition function encodes the original POMDP’s transition function and the memory update. T′(s⊥,(a,q))=b×δq T (s_ ,(a,q))=b× _q ∀(a,q)∈A×Q ∀(a,q)∈ A× Q T′((s,q),(a,q′))=T(s,a)×δq′ T ((s,q),(a,q ))=T(s,a)× _q ∀(a,q′)∈A×Q,(s,q)∈S×Q. ∀(a,q )∈ A× Q,(s,q)∈ S× Q. The observation function reveals the memory state and encodes the original observation function. O′(s⊥)=δ(z(∗),q(∗)) O (s_ )= _(z^(*),q^(*)) O′((s,q))=O(s)×δq∀s∈S,q∈Q. O ((s,q))=O(s)× _q ∀ s∈ S,q∈ Q. In this observation function, z(∗)z^(*) and q(∗)q^(*) are an arbitrary observation-memory-state pair. The reward function encodes the original reward function outside the dummy state, where the reward is zero. R′(s⊥,(a,q))=0 R (s_ ,(a,q))=0 ∀(a,q)∈A×Q ∀(a,q)∈ A× Q R′((s,q),(a,q′))=R(s,a) R ((s,q),(a,q ))=R(s,a) ∀(a,q′)∈A×Q,(s,q)∈S×Q. ∀(a,q )∈ A× Q,(s,q)∈ S× Q. Finally, the initial state distribution places all mass on the dummy state, i.e., b′=δs⊥b = _s_ . Clearly, we can construct ℳ′M from ℳM in polynomial time. Any FSC (Q,ι,(γt)t∈0,…,H−1,(ηt)t∈0,…,H−1)(Q, ,( _t)_t∈\0,…,H-1\,( _t)_t∈\0,…,H-1\) for the original POMDP corresponds to a time-dependent Markovian policy in ℳ′M which attains the same reward. Indeed, for each t∈0,…,H−1t∈\0,…,H-1\, let ξt:Q×Z→Δ(A×Q) _t:Q× Z→ (A× Q) denote the function such that (9) ξt((q,z))((a,q′))=γt(q,z)(a)ηt(q,z,a)(q′)∀q,q′∈Q,z∈Z,a∈A. _t((q,z))((a,q ))= _t(q,z)(a) _t(q,z,a)(q ) ∀ q,q ∈ Q,z∈ Z,a∈ A. That is, ξt _t encodes the joint distribution on actions and successor memory states given an original memory state and an observation. Clearly, we can implement ξt _t as a time-dependent Markovian policy π′π in the expanded POMDP ℳ′M by setting π0′((z(∗),q(∗)))((a(∗),q))=ι(q) π _0((z^(*),q^(*)))((a^(*),q))= (q) ∀q∈Q, ∀ q∈ Q, πt′((z,q))((a,q′))=ξt−1((q,z))((a,q′)) π _t((z,q))((a,q ))= _t-1((q,z))((a,q )) ∀q,q′∈Q,z∈Z,a∈A,t∈1,…,H, ∀ q,q ∈ Q,z∈ Z,a∈ A,t∈\1,…,H\, where a(∗)∈Aa^(*)∈ A is an arbitrary fixed action. Now, if h=q0,s0,z0,a0,…,qH−1,sH−1,zH−1,aH−1∈(Q×S×Z×A)Hh=q_0,s_0,z_0,a_0,…,q_H-1,s_H-1,z_H-1,a_H-1∈(Q× S× Z× A)^H is some trajectory in the original POMDP, then the set of trajectories (10) ℋh:=s⊥,(z(∗),q(∗)),(a(∗),q0),(s0,q0),(z0,q0),(a0,q1),…,(sH−1,qH−1),(zH−1,qH−1),(aH−1,qH)|qH+1∈Q⊂(S′×Z′×A′)H+1H_h:=\s_ ,(z^(*),q^(*)),(a^(*),q_0),(s_0,q_0),(z_0,q_0),(a_0,q_1),…,(s_H-1,q_H-1),(z_H-1,q_H-1),(a_H-1,q_H)|q_H+1∈ Q\⊂(S × Z × A )^H+1 satisfies ℙℳπ[h]=ℙℳ′π′[ℋh]P^π_M[h]=P^π _M [H_h]. As the two POMDPs give the same reward for trajectories in h and ℋhH_h respectively, we can deduce that π′π obtains the same reward in ℳ′M as π does in ℳM. Conversely, let π′π be some time-dependent Markovian policy in ℳ′M . We first set ι such that ι(q)=∑a∈Aπ0′((z(∗),q(∗)))((q,a)) (q)= _a∈ Aπ _0((z^(*),q^(*)))((q,a)) for all q∈Qq∈ Q. Then, we set, for each t∈0,…,H−1t∈\0,…,H-1\, q∈Qq∈ Q, z∈Zz∈ Z, and a∈Aa∈ A, (11) γt(q,z)(a)=∑q′∈Qπt+1′((z,q))((q′,a)). _t(q,z)(a)= _q ∈ Qπ _t+1((z,q))((q ,a)). Next, for each t∈0,…,H−1t∈\0,…,H-1\,q,q′∈Qq,q ∈ Q, z∈Zz∈ Z, and a∈Aa∈ A, we set (12) ηt(q,z,a)(q′)=πt+1′((z,q))((q′,a))γt(q,z)(a) if γt(q,z)(a)>0δq(∗) otherwise . _t(q,z,a)(q )= cases π _t+1((z,q))((q ,a)) _t(q,z)(a)& if $ _t(q,z)(a)>0$\\ _q^(*)& otherwise . cases In the above expression q(∗)q^(*) is some arbitrary fixed memory-state in Q. Clearly, we have (13) πt+1′((z,q))((q′,a))=ηt(q,z,a)(q′)γt(q,z)(a)∀q,q′∈Q,a∈A,z∈Z,t∈0,…,H−1,π _t+1((z,q))((q ,a))= _t(q,z,a)(q ) _t(q,z)(a) ∀ q,q ∈ Q,a∈ A,z∈ Z,t∈\0,…,H-1\, and thus, by the same logic as above, we can deduce that if h=q0,s0,z0,a0,…,qH,sH,zH,aH∈(Q×S×Z×A)Hh=q_0,s_0,z_0,a_0,…,q_H,s_H,z_H,a_H∈(Q× S× Z× A)^H is some trajectory in the original POMDP ℳM, then the following set of trajectories in the expanded POMDP ℳ′M has the same probability and reward under π′π . (14) ℋh:=s⊥,(z(∗),q(∗)),(a~,q0),(s0,q0),(z0,q0),(a0,q1),…,(sH,qH),(zH,qH),(aH,qH+1)|qH+1∈Q,a~∈A⊂(S′×Z′×A′)H+1.H_h:=\s_ ,(z^(*),q^(*)),( a,q_0),(s_0,q_0),(z_0,q_0),(a_0,q_1),…,(s_H,q_H),(z_H,q_H),(a_H,q_H+1)|q_H+1∈ Q, a∈ A\⊂(S × Z × A )^H+1. We can then deduce that the policy π defined by (ι,(γt)t∈0,…,H−1,(ηt)t∈0,…,H−1)( ,( _t)_t∈\0,…,H-1\,( _t)_t∈\0,…,H-1\) attains the same reward as π′π . We have now established the correspondence between the two policy classes, and we remark that each direction of the translation between the two policy classes can be done in polynomial time in the size of the policy. Furthermore, examining the proof, we see that if a time-dependent Markovian policy π′π in ℳ′M is deterministic, we can construct an FSC-based policy in ℳM with the same reward that is also deterministic. ∎ Appendix C Figures POMDPRevPOMDPSOMDPηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ -environment modelsMulti-environment modelsMulti-observation modelsMulti-observation models, fixed supportPSPACE-hardin NPNP-hardin P Figure 4. Overview of the complexity results no restrictions POMDPRevPOMDPSOMDPηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDP⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]⊆ -environment modelsMulti-environment modelsMulti-observation modelsMulti-observation models, fixed supportPSPACE-hardin NPNP-hardin P Figure 5. Overview of the complexity results determinsitic models POMDPRevPOMDPSOMDPηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDPBlindMDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]MDP⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ηs∈(0,1]_ _s∈(0,1]IOMDPλ∈(0,1]SOMDPηs∈[0,1]_ _s∈[0,1]IOMDPλ∈[0,1]⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ -environment modelsMulti-environment modelsMulti-observation modelsMulti-observation models, fixed supportETR-hardin NPETR-hardopenNP-hardin P Figure 6. Overview of the complexity results memoryless policies Appendix D Proofs for Section 4.2 D.1. Intermittently-Observable MDPs See 4.1 Proof. We reduce 3SAT to this problem. The reduction is very similar to the reduction from 3SAT to Blind MDPs as presented in (Papadimitriou and Tsitsiklis, 1987). The difference lies in the way we need to deal with state revelations, which do not occur in BlindMDPs. Fix a 3SAT instance φ , and let ℳ′=(S,A,⊥,T,O,R,b,H)M =(S,A,\ \,T,O,R,b,H) be a BlindMDP such that the following conditions hold. (Assumption 1): The rewards in the POMDP ℳ′M are less than or equal to zero. (Assumption 2): There exists a policy in ℳ′M with zero expected reward if and only if φ has a solution. Such a POMDP exists for each 3SAT instance, as one can argue by following the reasoning in (Papadimitriou and Tsitsiklis, 1987). Next, let ℳM be an IOMDP with all components equal to ℳ′M except for the observation set and function, which we modify such that the true state is revealed with probability 12 12 at each time step. We claim that there exists a policy in ℳM with non-negative reward if and only if the 3SAT instance φ is satisfiable. (⟹ ) By assumption, the IOMDP ℳM has a history-dependent π with zero reward, and we can assume this policy to be deterministic, as such policies are optimal among POMDP policies in the finite-horizon case. We now claim that there exists a policy for the POMDP ℳ′M that also achieves zero reward. Let ht⊥h _t be the t step observation history where the state is never revealed, consisting of t+1t+1 ⊥ -observations. Note that we can, without loss of generality, assume that the optimal policy is observation-based since it is deterministic. Then, let π′π be a policy for the BlindMDP ℳ′M where (15) π′(ht⊥)=π(ht⊥)∀t∈0,…,H−1.π (h _t)=π(h _t) ∀ t∈ 0,…,H-1. Evaluating the reward of π, we have πℳ[∑t=0H−1R(st,at)]≤∑s0,…,sH−1∈SHℙℳ[s0]∏t=0H−2ℙℳ[st+1|st,π(h⊥t)]∏t=0H−1ℙℳ[⊥|st](∑t=0H−1R(st,π(h⊥t)))=(12)H∑s0,…,sH−1∈SHℙℳ[s0]∏t=0H−2ℙℳ[st+1|st,π(h⊥t)](∑t=0H−1R(st,π(h⊥t)))=(12)Hπ′ℳ′[∑t=0H−1R(st,at)]E^π_M [ _t=0^H-1R(s_t,a_t) ]≤ _s_0,…,s_H-1∈ S^HP_M[s_0] _t=0^H-2P_M[s_t+1|s_t,π(h _t)] _t=0^H-1P_M[ |s_t] ( _t=0^H-1R(s_t,π(h _t)) )\\ = ( 12 )^H _s_0,…,s_H-1∈ S^HP_M[s_0] _t=0^H-2P_M[s_t+1|s_t,π(h _t)] ( _t=0^H-1R(s_t,π(h _t)) )= ( 12 )^HE^π _M [ _t=0^H-1R(s_t,a_t) ] In the first inequality, we use the fact that we can split the trajectories where the agent observes the state at least once from the trajectories where the agent never observes the state. Since all rewards are non-positive, the reward contribution from all trajectories where the agent observes the state at least once is upper bounded by zero. Therefore, we can consider the reward contribution of the trajectories where the agent never observes the state as an upper bound on the total reward. The first equality follows from the fact that the IOMDP ℳM has a revelation probability of 12 12. The last equality follows from the fact that the POMDPs ℳM and ℳ′M share a transition function, along with the definition of the policy π′π . As ℳπ[∑t=0H−1R(st,at)]E^π_M[ _t=0^H-1R(s_t,a_t)] is non-negative, we deduce the existence of a policy in ℳ′M with non-negative reward. Then, using (Assumption 2), we deduce that φ is satisfiable. (⟸ ) By (Assumption 2), there exists a policy in the BlindMDP ℳ′M which attains zero expected reward. We can deploy this policy in ℳM, playing blind and ignoring any revealing observation, and get zero reward. ∎ D.2. Semi-Observable MDPs See 4.2 Proof. Fix a SOMDP. We show that there exists an optimal policy π where the action a for each history h=z0,a0,…,zt−1,at−1,zth=z_0,a_0,…,z_t-1,a_t-1,z_t is determined by the following data. (1) t′=supu:zu≠⊥t = \u:z_u≠ \, i.e., the last revelation time44 4 Using the convention that sup(∅)=−∞ ( )=-∞.. (2) s=q:zt′=⊤q if t′≠−∞, if t′=−∞s= casesq:z_t = _q& if t ≠-∞,\\ blind& if t =-∞ cases, i.e., the last revealed state (if any). (3) t, i.e., the current time. Let (πt∗)t=0H−1(π^*_t)_t=0^H-1 be a deterministic time-dependent belief-based optimal policy for the SOMDP. We will build a policy π which attains the same value while tracking the smaller information set described above. In particular, we will define a policy (16) π:(S∪)×(0,…,H−1∪−∞)×0,…,H−1→A.π:(S∪\ blind\)×(\0,…,H-1\∪\-∞\)×\0,…,H-1\→ A. For s∈Ss∈ S, t′∈(0,…,H−1∪−∞)t ∈(\0,…,H-1\∪\-∞\) and t∈0,…,H−1t∈\0,…,H-1\, π(s,t′,t)π(s,t ,t) will encode the action to take when • The state was last revealed at t′t , • The current time is t, • The state was last revealed to be s. Meanwhile, π(,−∞,t)π( blind,-∞,t) will encode the action to take in the event when, at time t, the state has never been revealed. We will build the new policy π by inductively computing beliefs and the resulting action. Let (s,t′,u)b_(s,t ,u) seen denote the belief on the SOMDP’s state when • The state was last revealed at t′t , • The current time is u, • The state was last revealed to be s, • We take actions using π∗π^*. We can inductively define (s,t′,u)b_(s,t ,u) seen. First, we have (17) (s,t′,t′)=δs.b_(s,t ,t ) seen= _s. That is, if the state was revealed at the current timestep, the belief collapses. Then, we can iteratively update beliefs as follows. (18) a(s,t′,u)=πu∗((s,t′,u))(s,t′,u+1)(s′)=(1−η(s′))⋅∑su∈ST(su,a(s,t′,u))(s′)⋅(s,t′,u)(su)∑su+1∈S(1−η(su+1))⋅∑su∈ST(su,a(s,t′,u))(su+1)⋅(s,t′,u)(su)a_(s,t ,u) seen=π^*_u(b_(s,t ,u) seen) b_(s,t ,u+1) seen(s )= (1-η(s ))· _s_u∈ ST(s_u,a_(s,t ,u) seen)(s )·b_(s,t ,u) seen(s_u) _s_u+1∈ S(1-η(s_u+1))· _s_u∈ ST(s_u,a_(s,t ,u) seen)(s_u+1)·b_(s,t ,u) seen(s_u) In the above equation, a(s,t′,u)a_(s,t ,u) seen encodes the action the optimal policy will take at time u if the state was last observed at t′t to be s. With this recursion, we can then set (19) π(s,t′,t)=a(s,t′,t)π(s,t ,t)=a_(s,t ,t) seen To compute π(,−∞,t,0)π( blind,-∞,t,0), we simply propagate the initial belief as appropriate. In particular, let b be the initial state distribution. We define ata blind_t inductively. We set 0=bb blind_0=b, and then we use the following recursion. (20) at=πt∗(t)t+1(s′)=(1−η(s′))⋅∑st∈ST(st,at)(s′)⋅t(st)∑st+1∈S(1−η(st+1))⋅∑st∈ST(st,at)(st+1)⋅t(st)a blind_t=π^*_t(b blind_t) blind_t+1(s )= (1-η(s ))· _s_t∈ ST(s_t,a blind_t)(s )·b blind_t(s_t) _s_t+1∈ S(1-η(s_t+1))· _s_t∈ ST(s_t,a blind_t)(s_t+1)·b blind_t(s_t) We then set π(,−∞,t)π( blind,-∞,t) to ata blind_t. We now claim that π is optimal. We first argue that, for any observable history h that is possible55 5 I.e., occurring with probability greater than zero. when the policy π∗π^* is used, π∗π^* and π choose the same action. Fix an observable history h under π∗π^*, where h=z0,a0,…,zt−1at−1,zth=z_0,a_0,…,z_t-1a_t-1,z_t, and let ata_t be the action π∗π^* chooses upon observing this history. Since h is observable and π∗π^* is deterministic, we know ∀i∈0,…,t−1,πi∗(bi)=ai∀ i∈\0,…,t-1\,π^*_i(b_i)=a_i where bib_i is the belief after observing history hi=z0,a0,…,zih_i=z_0,a_0,…,z_i. Additionally, let t′t be the latest time u such that zu≠⊥z_u≠ , and let s be the state such that zt′=⊤sz_t = _s. We argue by induction that, for each l∈0,…,t−t′l∈\0,…,t-t \, we have at′+l=a(s,t′,t′+l)=π(s,t′,t′+l)a_t +l=a_(s,t ,t +l) seen=π(s,t ,t +l) and bt′+l=(s,t′,t′+l)b_t +l=b_(s,t ,t +l) seen For the base case, when l=0l=0, the state has been revealed and bt′=δs=(s,t′,t′)b_t = _s=b_(s,t ,t ) seen. Additionally, observe that (21) at′=πt′∗(δs)=a(s,t′,t′).a_t =π^*_t ( _s)=a_(s,t ,t ) seen. As stated above, the first equality holds as h is an observable history. Meanwhile, the second equality simply holds from the definition of a(s,t′,t′)a_(s,t ,t ) seen. Consider l≤t−t′−1l≤ t-t -1. For the inductive step, assume at′+l=a(s,t′,t′+l)a_t +l=a_(s,t ,t +l) seen and bt′+l=(s,t′,t′+l)b_t +l=b_(s,t ,t +l) seen. We show at′+l+1=a(s,t′,t′+l+1)a_t +l+1=a_(s,t ,t +l+1) seen: at′+l+1 a_t +l+1 =πt′+l+1∗(bt′+l+1) =π^*_t +l+1(b_t +l+1) =πt′+l+1∗(bupd(bt′+l,at′+l,zt′+l+1)) =π^*_t +l+1(b_upd(b_t +l,a_t +l,z_t +l+1)) =πt′+l+1∗(bupd((s,t′,t′+l),a(s,t′,t′+l),⊥)) =π^*_t +l+1(b_upd(b_(s,t ,t +l) seen,a_(s,t ,t +l) seen, )) =πt′+l+1∗((s,t′,t′+l+1)) =π^*_t +l+1(b_(s,t ,t +l+1) seen) =a(s,t′,t′+l+1) =a_(s,t ,t +l+1) seen Additionally, since we update the same belief bt′+l=(s,t′,t′+l)b_t +l=b_(s,t ,t +l) seen with the same action and receive the same blind observation, we may also conclude bt′+l+1=(s,t′,t′+l+1)b_t +l+1=b_(s,t ,t +l+1) seen. By the above induction, at=a(s,t′,t)a_t=a_(s,t ,t) seen By definition π will take the action a(s,t′,t)a_(s,t ,t) seen on seeing history h. Thus, on any possible history where the state is revealed at some point, π and π∗π^* give the same action. For the case of a history h=z0,a0,…zt−1,at−1,zth=z_0,a_0,… z_t-1,a_t-1,z_t where zk=⊥z_k= for all k, we can use similar arguments. In this case, we must show that ai=aia_i=a blind_i and bi=ib_i=b blind_i for all i∈0,…t−1i∈\0,… t-1\. For the base case, when i=0i=0, we have by definition b0=b=0b_0=b=b blind_0 and: a0 a_0 =π0∗(b) =π^*_0(b) =π0∗(0) =π^*_0(b blind_0) =a0 =a blind_0 For the inductive step, assume ai=aia_i=a blind_i and bi=ib_i=b blind_i. Then we have: ai+1 a_i+1 =πi+1∗(bi+1) =π^*_i+1(b_i+1) =πi+1∗(bupd(bi,ai,⊥)) =π^*_i+1(b_upd(b_i,a_i, )) =πi+1∗(bupd(i,ai,⊥)) =π^*_i+1(b_upd(b blind_i,a_i, )) =πi+1∗(bupd(i,ai,⊥)) =π^*_i+1(b_upd(b blind_i,a blind_i, )) =πi+1∗(i+1) =π^*_i+1(b blind_i+1) =ai+1 =a blind_i+1 Additionally, since we update the same belief bi=ib_i=b blind_i with the same action and receive the same blind observation, we may also conclude bi+1=i+1b_i+1=b blind_i+1. By the above induction, we can conclude that at=ata_t=a blind_t, but by definition π will take the action ata blind_t on seeing history h. Thus, on any possible history where the state is revealed at some point π and π∗π^* give the same action. We can easily deduce now that π is optimal. Indeed, let π∗ Paths^π^* denote the set of possible H-length paths under the policy π∗π^*, where a path ρ takes the form: (22) ρ=s0,z0,a0,…,sH−1,zH−1,aH−1.ρ=s_0,z_0,a_0,…,s_H-1,z_H-1,a_H-1. Note that ∑ρ∈π∗ℙπ∗[ρ]=1 _ρ∈ Paths^π^*P^π^*[ρ]=1, and Vπ∗=∑ρℙπ∗[ρ]R(ρ)V^π^*= _ρP^π^*[ρ]R(ρ), where R(ρ)R(ρ) is the reward accumulated along a path. It is thus sufficient to show that, for all ρ∈π∗ρ∈ Paths^π^*, we have ℙπ∗[ρ]=ℙπ[ρ]P^π^*[ρ]=P^π[ρ], where π is our newly constructed policy. We can easily observe this as follows ℙπ∗[s0,z0,a0,…,sH−1,zH−1,aH−1] ^π^*[s_0,z_0,a_0,…,s_H-1,z_H-1,a_H-1] =ℙ[s0]∏t=0H−1ℙ[zt|st]∏t=0H−2ℙ[st+1|st,at]∏t=0H−1ℙπ∗[at|z0,a0,…,zt1at−1,zt] =P[s_0] _t=0^H-1P[z_t|s_t] _t=0^H-2P[s_t+1|s_t,a_t] _t=0^H-1P^π^*[a_t|z_0,a_0,…,z_t_1a_t-1,z_t] =ℙ[s0]∏t=0H−1ℙ[zt|st]∏t=0H−2ℙ[st+1|st,at]∏t=0H−1ℙπ[at|z0,a0,…,zt1,at−1,zt] =P[s_0] _t=0^H-1P[z_t|s_t] _t=0^H-2P[s_t+1|s_t,a_t] _t=0^H-1P^π[a_t|z_0,a_0,…,z_t_1,a_t-1,z_t] =ℙπ[s0,z0,a0,…,sH−1,zH−1,aH−1] =P^π[s_0,z_0,a_0,…,s_H-1,z_H-1,a_H-1] In the first and last equality, we simply apply conditional probability rules. Note that we drop superscripts in the probability measure when they do not depend on the deployed policy. In the second equality, we use the following facts • As the path ρ is possible under π∗π^*, ℙπ∗[at|z0,a0,…,zt1,at−1,zt]=1P^π^*[a_t|z_0,a_0,…,z_t_1,a_t-1,z_t]=1 for each t. • Since π takes the same action as π∗π^* for any possible history, ℙπ[at|z0,a0,…,zt−1,at−1,zt]=1P^π[a_t|z_0,a_0,…,z_t-1,a_t-1,z_t]=1 for each t We now conclude that π∗π^* and π give the same reward. Next, we show that we can evaluate a policy of the proposed structure in polynomial time. First, note that we can represent the policy class using time-dependent FSCs with memory state space Q=(S∪s⊥)×(0,…,H−1∪−∞)Q=(S∪\s_ \)×(\0,…,H-1\∪\-∞\). Given a policy π:(S∪)×(0,…,H−1∪−∞)×0,…,H−1→Aπ (S∪\ blind\)×(\0,…,H-1\∪\-∞\)×\0,…,H-1\→ A, we construct time-dependent FSC policy (ι,(γt)t∈0,…,H−1,(ηt)t∈0,…,H−1)( ,( _t)_t∈\0,…,H-1\,( _t)_t∈\0,…,H-1\) such that ι =(s⊥,−∞)↦1, =\(s_ ,-∞) 1\, γt((s,t′),z) _t((s,t ),z) =π(s′,t,t)if z=⊤s′,π(s,t′,t)if z=⊥, = casesπ(s ,t,t)&if $z= _s $,\\ π(s,t ,t)&if $z= $, cases ηt((s,t′),z,a) _t((s,t ),z,a) =(s′,t)if z=⊤s′,(s,t′)if z=⊥,, = cases(s ,t)&if $z= _s $,\\ (s,t )&if $z= $, cases, where we write ⊤s∈Z _s∈ Z for the unique revealing observation of state s and ⊥∈Z ∈ Z for the blind observation. Note that this FSC is deterministic. We then use Lemma B.5 and Lemma B.4 to conclude that we can evaluate a deterministic time-dependent FSC in polynomial time. We can conclude that there exists a non-deterministic algorithm to solve this problem. In particular, we (1) Guess a policy by guessing an action for each combination of current time, last revelation time, and revealed state. (2) Evaluate the guessed policy via the FSC construction. ∎ D.3. Revealing POMDPs See 4.3 Proof. We reduce QSAT to this problem. The reduction is similar very similar to the reduction from QSAT to POMDPs as presented in (Papadimitriou and Tsitsiklis, 1987). The difference lies in the way we need to deal with state revelations, which do not occur in the POMDPs used in the QSAT reduction. Fix a QSAT instance φ , and let ℳ′=(S,A,Z,T,O,R,b,H)M =(S,A,Z,T,O,R,b,H) be a POMDP such that the following conditions hold. (Assumption 1): The rewards in the POMDP ℳ′M are less than or equal to zero. (Assumption 2): There exists a policy in ℳ′M with zero expected reward if and only if φ has a solution. Such a POMDP exists for each QSAT instance (Papadimitriou and Tsitsiklis, 1987). Next, let ℳM be an RevPOMDP with all components equal to ℳ′M except for the observation set and function, which we modify such that the true state is revealed with probability 12 12. We claim that there exists a policy in ℳM with non-negative reward if and only if the QSAT instance φ is satisfiable. (⟹ ) By assumption, the RevPOMDP ℳM has a policy π with zero reward, and we can assume this policy to be deterministic, as such policies are optimal among POMDP policies in the finite-horizon case. We now claim that there exists a policy for the POMDP ℳ′M that also achieves zero reward. Since the RevPOMDP is the POMDP extended with state revelations, the set of every non-revealing observation history in the RevPOMDP and the set of all observation histories in the POMDP are the same. Let ht,⊥πh^π_t, be a history obtained by playing π for t steps where the state is never revealed. Then, let π′π be a policy for the BlindMDP ℳ′M where (23) π′(ht,⊥π)=π(ht,⊥π)∀t∈0,…,H−1.π (h^π_t, )=π(h^π_t, ) ∀ t∈\0,…,H-1\. Evaluating the reward of π, we have πℳ[∑t=0H−1R(st,at)]≤∑s0,…,sH−1∈SHℙℳ[s0]∏t=0H−2ℙℳ[st+1|st,π(hπt,⊥)]∏t=0H−1ℙℳ[⊥|st](∑t=0H−1R(st,π(hπt,⊥)))=(12)H∑s0,…,sH−1∈SHℙℳ[s0]∏t=0H−2ℙℳ[st+1|st,π(hπt,⊥)](∑t=0H−1R(st,π(hπt,⊥)))=(12)Hπ′ℳ′[∑t=0H−1R(st,at)]E^π_M [ _t=0^H-1R(s_t,a_t) ]≤ _s_0,…,s_H-1∈ S^HP_M[s_0] _t=0^H-2P_M[s_t+1|s_t,π(h^π_t, )] _t=0^H-1P_M[ |s_t] ( _t=0^H-1R(s_t,π(h^π_t, )) )\\ = ( 12 )^H _s_0,…,s_H-1∈ S^HP_M[s_0] _t=0^H-2P_M[s_t+1|s_t,π(h^π_t, )] ( _t=0^H-1R(s_t,π(h^π_t, )) )= ( 12 )^HE^π _M [ _t=0^H-1R(s_t,a_t) ] In the first inequality, we use the fact that we can split the trajectories where the agent observes the state at least once from the the trajectories where the agent never observes the state. Since all rewards are non-positive, the reward contribution from all trajectories where the agent observes the state at least once is upper bounded by zero. Therefore, we can consider the reward contribution of the trajectories where the agent never observes the state as an upper bound on the total reward. The first equality follows from the fact that the RevPOMDP ℳM has a revelation probability of 12 12. The last equality follows from the fact that the POMDPs ℳM and ℳ′M share transition dynamics, along with the definition of the policy π′π . As ℳπ[∑t=0H−1R(st,at)]E^π_M[ _t=0^H-1R(s_t,a_t)] is non-negative, we deduce the existence of a policy in ℳ′M with non-negative reward. Then, using (Assumption 2), we know φ is satisfiable. (⟸ ) By (Assumption 2), there exists a policy in the BlindMDP ℳ′M which attains zero expected reward. We can deploy this policy in ℳM, playing blind when we receive a revealing observation, and get zero reward. ∎ D.4. Time-dependent Markovian policies in IOMDPs with non-zero revelation probabilities See 4.4 Proof. We can prove this result by adapting the argument from Proposition 4.1 to time-dependent policies. In particular, fix a 3SAT instance φ , and let ℳ′=(S,A,⊥,T,O,R,b,H)M =(S,A,\ \,T,O,R,b,H) be the same BlindMDP satisfying Assumptions 1 and 2 from the proof of Proposition 4.1. (Assumption 1): The rewards in the POMDP ℳ′M are less than or equal to zero. (Assumption 2): There exists a policy in ℳ′M with zero expected reward if and only if φ has a solution. Also, again, let ℳM be the IOMDP built from ℳ′M where the true state is revealed with probability 12 12. We claim that there exists a time-dependent Markovian policy in ℳM with non-negative reward if and only if the SAT instance φ is satisfiable. (⟹ ) By assumption, the IOMDP ℳM has a time-dependent Markovian policy (πt)t=0H−1( _t)_t=0^H-1 with non-negative reward, and we can assume this policy to be deterministic, as such policies are optimal among time-dependent Markovian policies in the finite-horizon case (Bagnell et al., 2003). We now claim that there exists a policy for the POMDP ℳM that also achieves zero reward. Indeed, let π′π be a time-dependent policy for the BlindMDP ℳ′M where (24) πt′(⊥)=πt(⊥)∀t∈0,…,H−1.π _t( )= _t( ) ∀ t∈ 0,…,H-1. By the same reasoning as in the proof of Proposition 4.1, we can argue that (25) ℳπ[∑t=0H−1R(st,at)]≤(12)Hℳ′π′[∑t=0H−1R(st,at)],E^π_M [ _t=0^H-1R(s_t,a_t) ]≤ ( 12 )^HE^π _M [ _t=0^H-1R(s_t,a_t) ], which implies that π′π attains non-negative reward in ℳ′M , and thus φ is satisfiable. (⟸ ) By (Assumption 2), there exists a history-dependent policy π′π in the BlindMDP ℳ′M which attains non-negative expected reward. Without loss of generality, we can assume this policy to be deterministic, and as such, the policy π′π is equivalent to a policy that plays a sequence of actions deterministically. Thus, there exists a time-dependent Markovian policy in the BlindMDP ℳ′M which attains non-negative expected reward. We can deploy this time-dependent Markovian policy in ℳM as well and get non-negative reward. ∎ D.5. Time-dependent FSC-based policies See 4.6 Proof. Fix a POMDP ℳ=(S,A,Z,T,O,R,b,H)M=(S,A,Z,T,O,R,b,H). By Lemma B.5, we can, in polynomial time, build a new POMDP (26) ℳ′=(S′,A′,Z′,T′,O′,R′,b′,H+1)M =(S ,A ,Z ,T ,O ,R ,b ,H+1) such that any |Q||Q|-state time-dependent FSC in ℳM has a corresponding time-dependent Markovian policy in ℳ′M with the same reward, and vice versa. From this fact, it follows that (27) maxπ∈Π(Q)ℳπ[∑t=0H−1R(st,at)]=maxπ′∈Πℳ′π′[∑t=0HR(st′,at′)] _π∈ _ FSC(Q)E_M^π [ _t=0^H-1R(s_t,a_t) ]= _π ∈ _ MRE_M ^π [ _t=0^HR(s _t,a _t) ] where Π(Q) _ FSC(Q) is the set of time-dependent-FSC-based policies with Q states. Additionally, note that by Lemma B.5, we can take any deterministic time-dependent Markovian policy in ℳ′M and convert it to a deterministic time-dependent FSC policy in ℳM. Since there exists an optimal time-dependent Markovian policy in ℳ′M that is deterministic, there also exists an optimal time-dependent FSC-based policy in ℳM that is deterministic. To decide whether the POMDP admits an FSC-based policy with |Q||Q| states and reward at least B, we can (1) Build the expanded POMDP ℳ′M . (2) Guess a deterministic time-dependent Markovian policy in ℳ′M . (3) Evaluate the policy and check whether it attains reward at least B. The first two steps can clearly be done in non-deterministic polynomial time, while the last stage can be done in polynomial time by Lemma B.4. We note that the assumption of determinism for the time-dependent Markovian policy is without loss of generality, a fact that holds due to the optimality of deterministic policies among time-dependent Markovian policies. -hardness follows from the time-dependent Markovian case, which we can encode by restricting |Q||Q| to be one. ∎ Appendix E Proofs for Section 5 E.1. Optimal ME-POMDP Policies via Hidden-Mixture POMDPs See 5.3 Proof. Let (ℳi)i∈[n](M_i)_i∈[n] be a ME-POMDP with POMDPs in C where each POMDP has state, action and observation spaces S, A, and Z. The value satisfies the following equality chain. (28) maxπ∈Πmini∈[n]Vℳiπ=min∈Δ([n])maxπ∈ΠZ,A,H∑i∈[n][i]Vℳiπ=min∈Δ([n])maxπ∈ΠS×[n],Z,A,H∑i∈[n][i]Vℳiπ=maxπ∈(ΠS×[n],Z,A,H)mini∈[n]Vℳiπ. _π∈ _i∈[n]V_M_i^π= _p∈ ([n]) _π∈ _ det^Z,A,H _i∈[n]p[i]V^π_M_i\\ = _p∈ ([n]) _π∈ _C^S×[n],Z,A,H _i∈[n]p[i]V^π_M_i= _π∈ Mix ( _C^S×[n],Z,A,H ) _i∈[n]V_M_i^π. The first and last equalities apply the min-max theorem for zero-sum matrix games (Başar and Olsder, 1998), which holds due to the finiteness of Π _ det and the finite number of environments. The middle inequality applies the optimality of policies in Π _C for mixture POMDPs, along with the fact that each mixture POMDP is a POMDP with state space S×[n]S×[n]. Similar to the proof in (Brice et al., 2026a), we can then argue that there exists an optimal policy mixing over at most n policies. To align with later algorithmic results, we give a proof based on linear programming (LP). In particular, observe that the final expression in (28) is equal to the optimal value of the following LP. (29) max∈ℝΠS×[n],Z,A,H,B∈ℝ _q _C^S×[n],Z,A,H,B B B (30) s.t. ∑π∈ΠS×[n],Z,A,H[π]=1, _π∈ _C^S×[n],Z,A,Hq[π]=1, (31) [π]≥0 [π]≥ 0 ∀π∈ΠS×[n],Z,A,H, ∀π∈ _C^S×[n],Z,A,H, (32) ∑π∈ΠS×[n],Z,A,H[π]Viπ≥B _π∈ _C^S×[n],Z,A,Hq[π]V^π_i≥ B ∀i∈[n]. ∀ i∈[n]. The variable B encodes the value of the ME-POMDP, while the vector q encodes a distribution over deterministic history-dependent policies. The constraint (32) encodes that the policy must attain value B in all environments, while the constraints (30) and (31) encode the validity of the distribution q. Note that we identify the element of the vector q corresponding to the deterministic policy π with [π]q[π]. This LP has an optimal solution since the objective is bounded above by the greatest expected reward obtained under any combination of a POMDP ℳiM_i and a deterministic policy π. We now show that the feasible set has an extreme point. For any deterministic policy π′π in the policy class, the point ′:-π′,B′:-mini∈[n]Viπ′q _π ,B _i∈[n]V_i^π is an extreme point, as the matrix defined by the active constraints at this point is of full rank. Because the feasible set has an extreme point, by convex optimization theory, this LP has an optimal solution at an extreme point (Bertsekas et al., 2003, Proposition 3.4.2). We now show that any such extreme point has at most n non-zero elements in the corresponding probability vector q. Given an extreme point (,B)(q,B), suppose there are L environments for which (32) is tight. Let ι1,…,ιL⊆[n]\ _1,…, _L\ [n] be the environments i for which ∑π∈ΠS×[n],Z,A,H[π]Viπ=B _π∈ _C^S×[n],Z,A,Hq[π]V_i^π=B. Similarly, suppose κ1,…,κR⊂ΠS×[n],Z,A,H\ _1,…, _R\⊂ _C^S×[n],Z,A,H contains the policies corresponding to the zero elements of q. Let ViV_i denote the vector in ℝΠS×[n],Z,A,HR _C^S×[n],Z,A,H such that Vi[π]=ViπV_i[π]=V_i^π for all policies π in ΠS×[n],Z,A,H _C^S×[n],Z,A,H. We must have (33) ([−Vι1⊤1−VιL⊤1⊤0κ1⊤0κR⊤0])=1+|ΠS×[n],Z,A,H|, rank ( bmatrix-V_ _1 &1\\ \\ -V_ _L &1\\ 1 &0\\ e_ _1 &0\\ \\ e_ _R &0 bmatrix )=1+| _C^S×[n],Z,A,H|, as (,B)(q,B) is an extreme point (Bertsekas et al., 2003, Proposition 3.3.3), where je_j is the jthj^th unit vector in the appropriate dimension. However, as the number of rows trivially bounds the rank, and L≤nL≤ n, we then have (34) 1+|ΠS×[n],Z,A,H|≤n+1+R,1+| _C^S×[n],Z,A,H|≤ n+1+R, which implies that R≥|ΠS×[n],Z,A,H|−nR≥| _C^S×[n],Z,A,H|-n. Thus, at an extreme point solution, at most n coordinates of q are non-zero, and we conclude that the ME-POMDP has an optimal policy that mixes over at most n elements of ΠS×[n],Z,A,H _C^S×[n],Z,A,H. ∎ E.2. Deterministic POMDPs See 5.4 Proof. When we mix over a set of deterministic POMDPs (ℳi)i∈[n](M_i)_i∈[n], we get another deterministic POMDP ℳ~ M. Indeed, let POMDP i be (35) ℳi=(S,A,Z,Ti,Oi,Ri,bi,H).M_i=(S,A,Z,T_i,O_i,R_i,b_i,H). Given a mixture distribution p, we can then construct a new deterministic POMDP (36) ℳ~=(S×[n],A,Z,T~,O~,R~,b~,H), M=(S×[n],A,Z, T, O, R, b,H), where, for all s∈Ss∈ S, i∈[n]i∈[n], we have T~((s,i),a)=Ti(s,a)×δi T((s,i),a)=T_i(s,a)× _i O~((s,i))=Oi(s) O((s,i))=O_i(s) R~((s,i),a)=Ri(s,a) R((s,i),a)=R_i(s,a) b~(s,i)=[i]bi(s). b(s,i)=p[i]b_i(s). Any policy π in the original ME-POMDP is a valid policy in ℳ~ M where (37) ℳ~π[∑t=0H−1R~(s~t,a~t)]=∑i∈[n][i]ℳiπ[∑t=0H−1Ri(st,at)].E^π_ M [ _t=0^H-1 R( s_t, a_t) ]= _i∈[n]p[i]E^π_M_i [ _t=0^H-1R_i(s_t,a_t) ]. Critically, this new POMDP ℳ~ M is also deterministic, as the transition functions (Ti)i∈[n](T_i)_i∈[n] and observation functions (Oi)i∈[n](O_i)_i∈[n] are deterministic. By Lemma 6.3 in (Littman, 1996), deterministic POMDPs have optimal policies with concise representations. In particular, (Littman, 1996) introduces a notion of a policy tree to reason about optimal policies in deterministic POMDPs. A policy tree is a tree where each node is labeled with an action, and the descendant relation encodes which subtree to follow for each possible observation (Littman, 1996). To ease exposition, we introduce a slightly more general notion in the form of a policy-directed-acyclic-graph (policy-DAG). In particular, a policy-DAG comprises H node sets (Ut)t=0H−1(U_t)_t=0^H-1, along with two sequences of functions t:Ut→A Act_t:U_t→ A for each t∈0,…,H−1t∈ 0,…,H-1, and t:Ut×Z→Ut+1 NodeUpd_t:U_t× Z→ U_t+1 for each t∈0,…,H−2, each $t∈ 0,…,H-2$, along with a mapping :Z→U0 Init:Z→ U_0 specifying an initial node for each initial observation. By Lemma 6.3 in (Littman, 1996), a deterministic POMDP with m states has an optimal policy in the form of a policy-DAG where the number |Ut||U_t| of nodes at each stage is bounded by m. We can apply Proposition 5.3 to deduce that there exists an optimal policy for the original ME-POMDP that mixes over n policy DAGs with at most n|S|n|S| nodes per time step, and this fact suggests the following non-deterministic algorithm to decide if the ME-POMDP has a policy with reward at least B. (1) Guess n policies (πj)j∈[n]( _j)_j∈[n] where each policy is a policy DAG with at most n|S|n|S| nodes in each set UtU_t. (2) Evaluate each policy πj _j in each POMDP ℳiM_i. (3) Solve an LP to determine if there exists a distribution on these policy DAGs such that the induced mixed policy attains reward at least B in the ME-POMDP The first stage of the above procedure clearly takes polynomial time, and we now argue that the last two stages do as well. We first fix notation, using N to refer to the representation size of the ME-POMDP instance. Now, fix a POMDP-index i∈[n]i∈[n], an initial state s0∈(bi)s_0∈ supp(b_i), and a policy tree πj _j with associated update functions (j),(j) Init^(j), NodeUpd^(j) and (j) Act^(j). As the POMDP ℳiM_i and policy πj _j are deterministic, there exists a unique trajectory for each initial state, and we can, in polynomial time, compute the resulting trajectory by applying the following equalities. zt=Oi(st) z_t=O_i(s_t) ∀t∈0,…,H−1, ∀ t∈\0,…,H-1\, u0=(j)(z0), u_0= Init^(j)(z_0), ut=tj(ut−1,zt) u_t= NodeUpd^j_t(u_t-1,z_t) ∀t∈0,…,H−2, ∀ t∈\0,…,H-2\, at=t(j)(ut) a_t= Act^(j)_t(u_t) ∀t∈0,…,H−1, ∀ t∈\0,…,H-1\, st+1=Ti(st,at) s_t+1=T_i(s_t,a_t) ∀t∈0,…,H−2. ∀ t∈\0,…,H-2\. We can evaluate the reward of this trajectory in polynomial time, and we can represent the reward as a rational ris(j):-pis(j)/qis(j)r_is^(j) p_is^(j)/q_is^(j) where pis(j)≤H2Hp_is^(j)≤ H2^NH and qis(j)≤2Hq_is^(j)≤ 2^NH and N is the representation-size. To evaluate the reward of the policy πj _j in POMDP ℳiM_i, we simply need to compute the expectation ∑s∈Sris(j)bi(s) _s∈ Sr_is^(j)b_i(s). By similar reasoning to Lemma B.4, we can deduce that evaluating the reward in environment i for policy j can be done in polynomial time, and furthermore, this expected reward has a polynomially-sized representation with respect to the original ME-POMDP instance size. Repeating this procedure for each environment i and policy j defines a table of values (Vi(j))i∈[n],j∈[n](V_i^(j))_i∈[n],j∈[n] where Vi(j)V_i^(j) encodes the reward of policy-DAG j in POMDP i and Vi(j)V_i^(j) is a rational number with size bounded polynomially in N. Finally, to determine whether the requisite mixture exists, we need to determine whether a distribution q exists satisfying the following linear inequalities ∑j∈[n][j]Vi(j)≥B∀i∈[n]. _j∈[n]q[j]V_i^(j)≥ B ∀ i∈[n]. We can solve this problem by solving an LP. While the corresponding LP has rational coefficients, we can convert this LP to an LP with integer coefficients that is polynomially sized in terms of the original ME-POMDP instance. We can then solve this LP in polynomial time (Khachiyan, 1980; Karmarkar, 1984). ∎ E.3. Blind MDPs See 5.5 Proof. When we mix over a set of BlindMDPs (ℳi)i∈[n](M_i)_i∈[n], we obviously obtain another BlindMDP with an expanded state space. The optimal policy for this BlindMDP is then a sequence of H actions, and thus by Proposition 5.3, there exists an optimal policy for the ME-BlindMDP which is a mixture of n such sequences. As such, there exists a non-deterministic algorithm to solve this problem. In particular, we (1) Guess n sequences of actions, each of length H, where H is the horizon of the ME-BlindMDP. (2) Evaluate each of the n sequences of actions in each BlindMDP. (3) Solve a linear program to determine if some mixture of these sequences results in a policy with reward at least B. The first step clearly runs in polynomial time, and we next argue the same for the last two steps. Each sequence of actions is equivalent to some time-dependent Markovian policy, and so we can evaluate it in polynomial time with the resulting reward having a polynomially-sized representation. Indeed, let (πj)j∈[n]( _j)_j∈[n] be the n policies. Lemma B.4 implies that, in polynomial time, we can evaluate each policy in each POMDP. From this procedure we obtain a set of reward values (Vi(j))i∈[n],j∈[n](V_i^(j))_i∈[n],j∈[n] where Vi(j)V_i^(j) encodes the reward of the jthj^th policy in the ithi^th BlindMDP, and each value Vi(j)V_i^(j) has a representation Vi(j)=ui(j)/vi(j)V_i^(j)= u_i^(j)v_i^(j) such that (38) maxi∈[n],j∈[n]max(|ui(j)|,vi(j))≤2f() _i∈[n],j∈[n] (|u_i^(j)|,v_i^(j))≤ 2^f(N) for some fixed instance-independent polynomial f()f(N) of the instance size N. To deduce that the third stage runs in polynomial time, we can then use the same argument as in the proof of Corollary 5.4. That is, deciding the third stage is equivalent to solving a linear program with integral coefficients, where the coefficients have bit-size bounded by a polynomial of the size of the original ME-BlindMDP representation. ∎ E.4. On the definition of policy classes In Section 5, we defined the notion of policy classes by invoking the notion of the set of all sets. We can make this notion rigorous by assuming that all states, actions, and observations come from some universal set. For example, we could assume that each action, state, and observation is a natural number, i.e., (39) S⊂ℕ,A⊂ℕ,Z⊂ℕ.S ,A ,Z . In this case, we can identify the set of all state sets with 2ℕ2^N, and we can use a similar argument for the sets of all action sets and observation sets. Appendix F Proofs for Section 6 F.1. Multi-Observation MDPs See 6.1 Proof. Let ∃x1∀x2…∃xn−1∀xn,F(x1,…,xn)∃ x_1∀ x_2…∃ x_n-1∀ x_n,F(x_1,…,x_n) be a quantified formula in conjunctive normal form with n variables and m clauses. We construct a MO-POMDP which has the following properties. • Each environment is an MDP. • Each environment only differs in how we label the states. • There exists a policy with value at least 00 if and only if the QSAT instance is true. Intuitively, each environment has the same transition structure as the POMDP constructed in (Papadimitriou and Tsitsiklis, 1987) to prove PSPACE-hardness, with one branch per clause. We then use the multiple observation functions to mimic partial observability. In particular, we construct an MO-POMDP with environments (ℳi)i∈[m](M_i)_i∈[m] where (40) ℳi=(S,,⏟A,Z,T,Oi,R,b,2n+1⏟H).M_i=(S, \ setTrue, setFalse\_A,Z,T,O_i,R,b, 2n+1_H). The state space comprises an acceptance state, a dead state, and three states for each clause-variable pair. In particular, we have (41) S=s,s∪⋃l∈[m],j∈[n]sTl,j,sFl,j,sAl,j.S=\s_ fail,s_ acc\∪ _l∈[m],j∈[n]\s_T_l,j,s_F_l,j,s_A_l,j\. The action space comprises two actions to encode variable assignments (42) A=,.A=\ setTrue, setFalse\. Finally, we have a unique observation for each state, i.e. (43) Z=z,z∪⋃l∈[m],j∈[n]zTl,j,zFl,j,zAl,j.Z=\z_ fail,z_ acc\∪ _l∈[m],j∈[n]\z_T_l,j,z_F_l,j,z_A_l,j\. The transition dynamics then encode the QSAT instance in a similar manner to (Papadimitriou and Tsitsiklis, 1987). We set the initial distribution b so that the initial state of the POMDP is uniformly chosen from sA1,1,…,sAm,1\s_A_1,1,…,s_A_m,1\, and this random initial state choice corresponds to a random choice of a clause. If xjx_j is an existential variable, the next state after sAl,js_A_l,j follows the agent’s action. That is, for each l∈[m]l∈[m], j∈1,3,…,n−1j∈\1,3,…,n-1\, we have T(sAl,j,)=sTl,j T(s_A_l,j, setTrue)=s_T_l,j T(sAl,j,)=sFl,j. T(s_A_l,j, setFalse)=s_F_l,j. Meanwhile, if xjx_j is a universal variable, the next state is randomly chosen from sTl,j,sFl,j\s_T_l,j,s_F_l,j\, i.e., for each l∈[m],j∈2,4,…,nl∈[m],j∈\2,4,…,n\, we have T(sAl,j,a)=sTl,j↦12,sFl,j↦12∀a∈A.T(s_A_l,j,a)= \s_T_l,j 12,s_F_l,j 12 \ ∀ a∈ A. The transitions from sFl,js_F_l,j and sTl,js_T_l,j then encode the QSAT instance. In particular, for each clause l, the variables ∪j∈[n]sAl,j,sFl,j _j∈[n]\s_A_l,j,s_F_l,j, sTl,js_T_l,j\ form a branch where a clause-satisfying variable assignment sends the process to the accepting state. More precisely, for each j≤n−1j≤ n-1, l∈[m]l∈[m], we set T(sTl,j,a)=sif xj appears in ClsAl,j+1 otherwise. T(s_T_l,j,a)= casess_ acc&if $x_j$ appears in $C_l$\\ s_A_l,j+1& otherwise. cases ∀a∈A ∀ a∈ A T(sFl,j,a)=sif ¬xj appears in ClsAl,j+1 otherwise. T(s_F_l,j,a)= casess_ acc&if $ x_j$ appears in $C_l$\\ s_A_l,j+1& otherwise. cases ∀a∈A. ∀ a∈ A. We additionally have, for each l∈[m]l∈[m], T(sTl,n,a)=sif xn appears in Cls otherwise. T(s_T_l,n,a)= casess_ acc&if $x_n$ appears in $C_l$\\ s_ fail& otherwise. cases ∀a∈A ∀ a∈ A T(sFl,n,a)=sif ¬xn appears in Cls otherwise. T(s_F_l,n,a)= casess_ acc&if $ x_n$ appears in $C_l$\\ s_ fail& otherwise. cases ∀a∈A. ∀ a∈ A. At this stage, we have merely recalled the transition structure from (Papadimitriou and Tsitsiklis, 1987), but we will next introduce the observation function. Before introducing the observation function, we first fix notation. In particular, for k∈1,…,mk∈\1,…,m\, we use φk:[m]→[m] _k:[m]→[m] to denote the function which permutes the index. That is, (44) φk(l)=l+k if l+k∈[m]l+k−m otherwise . _k(l)= casesl+k& if l+k∈[m]\\ l+k-m& otherwise . cases In environment k, for k∈[m]k∈[m], we then set the observation function to satisfy (45) Ok(sTl,j)=zTφk(l),jOk(sFl,j)=zFφk(l),jOk(sAl,j)=zAφk(l),j∀l∈[m],j∈[n].O_k(s_T_l,j)=z_T_ _k(l),j O_k(s_F_l,j)=z_F_ _k(l),j O_k(s_A_l,j)=z_A_ _k(l),j ∀ l∈[m],j∈[n]. In words, this definition of the observation function implies that, in environment k, variables corresponding to clause l emit observations corresponding to clause φk(l) _k(l). For all environments, we set Ok(s)=zO_k(s_ acc)=z_ acc and Ok(s)=zO_k(s_ fail)=z_ fail. Finally, we set the reward function to penalize reaching the dead state s_ fail. That is, we set R(s,a)=−1R(s_ fail,a)=-1 for all actions a in A, and we set the reward to be zero for all other state-action pairs. Clearly, this ME-POMDP is a MO-MDP, since the shuffling procedure only changes the labels, and for any fixed environment, each state has a unique observation. We can also clearly build this MO-MDP in polynomial time in the size of the QSAT instance. We now claim that the QSAT instance is true if and only if the MO-MDP has a policy with non-negative reward. (⟹ ) This fact follows similar logic to the original -completeness proof for POMDPs (Papadimitriou and Tsitsiklis, 1987). Indeed, suppose σ:⋃t=0n2−10,12t→0,1σ: _t=0 n2-1\0,1\^2t→\0,1\ is a winning strategy for the QSAT instance where σ(1,…,2t)σ( b_1,…, b_2t) encodes an existential assignment for each bit-history that ensures the QSAT instance is satisfied for all possible universal variable assignments. We can define a natural strategy for the MO-MDP that, for each history, (1) Translates zT⋅,⋅z_T_·,· and zF⋅,⋅z_F_·,· observations to 11 and 00 respectively. (2) Deploys the action that σ defines. Clearly, this policy reaches the acceptance state for any clause branch and for any of the random choices of the universal variables. (⟸ ) Now, assume the MO-MDP has a policy π with a non-negative reward. We can argue that this strategy is, w.l.o.g., deterministic. Indeed, let π~ π be a general history-dependent randomized strategy. This strategy has a representation as a mixed strategy, a fact that follows from (Kuhn, 1953). As such, for a deterministic history-dependent policy π∈Ππ∈ _ det, let pπp_π be the probability of π under the mixed-policy representation of π~ π. By assumption, ∑π∈Πpπℳiπ[∑t=0H−1R(st,at)]≥0 _π∈ _ detp_πE_M_i^π[ _t=0^H-1R(s_t,a_t)]≥ 0 for all environments i. Additionally, all rewards are non-positive. Thus, we can deduce that, for any environment i∈[m]i∈[m], and any deterministic policy π such that pπ>0p_π>0, we have ℳiπ[∑t=0H−1R(st,at)]≥0E_M_i^π[ _t=0^H-1R(s_t,a_t)]≥ 0. Hence, there must exist some deterministic strategy that attains zero reward in all environments. We can construct a winning strategy for the QSAT instance using the behavior of π on seeing observations in the set (46) Z~1:=⋃j∈[n]zT1,j,zF1,j,zA1,j. Z_1:= _j∈[n]\z_T_1,j,z_F_1,j,z_A_1,j\. Intuitively, because any clause can produce observations in Z~1 Z_1, the corresponding strategy must provide a valid clause-independent assignment strategy. In particular, we first construct σ:⋃t=0n2−10,12t→0,1σ: _t=0 n2-1\0,1\^2t→\0,1\ so that a sequence 1,…,2t b_1,…, b_2t is assigned the action that π takes when the corresponding history is observed. More precisely, let j(0)=zF1,j V_j(0)=z_F_1,j and j(1)=zT1,j V_j(1)=z_T_1,j for each j∈[n]j∈[n]. Then, fix an even-length bit string 1,…,j b_1,…, b_j, i.e., a string ending in a universally quantified variable. Next, inductively define a sequence of actions as follows. a1(1)=π(zA1,1) a_1^(1)=π(z_A_1,1) a1(2)=π(zA1,1,a1(1),1(1)) a_1^(2)=π(z_A_1,1,a_1^(1), V_1( b_1)) … … at(1)=π(zA1,1,a1(1),…,t−1(t−1),at−1(2),zA1,t) a_t^(1)=π(z_A_1,1,a_1^(1),…, V_t-1( b_t-1),a_t-1^(2),z_A_1,t) at(2)=π(zA1,1,a1(1),…,t−1(t−1),at−1(2),zA1,t,at(1),t(t)) a_t^(2)=π(z_A_1,1,a_1^(1),…, V_t-1( b_t-1),a_t-1^(2),z_A_1,t,a_t^(1), V_t( b_t)) We then define σ(1,…,j)σ( b_1,…, b_j) as (47) σ(1,…,j)=1 if aj+1(1)=,0 if aj+1(1)=.σ( b_1,…, b_j)= cases1& if a_j+1^(1)= setTrue,\\ 0& if a_j+1^(1)= setFalse. cases We now argue that this strategy σ is indeed winning for the QSAT instance. Fix an arbitrary clause l∈[m]l∈[m]. Let x1,…,xnx_1,…,x_n be the bit string resulting from some choice of universal variables under the strategy σ. We argue that if x1,…,xnx_1,…,x_n does not satisfy clause ClC_l, then for some environment in the MO-POMDP, the policy π gets negative reward. Indeed, first observe that, in environment (m+1)−l(m+1)-l, the lthl^th branch of the transition function produces observations in the set Z~1=⋃j∈[n]zT1,j,zF1,j,zA1,j Z_1= _j∈[n]\z_T_1,j,z_F_1,j,z_A_1,j\ while visiting states in the set ∪j∈[n]sAl,j,sFl,j,sTl,j _j∈[n]\s_A_l,j,s_F_l,j,s_T_l,j\ and following a transition structure that sends the agent to the accepting state s_ acc if they satisfy ClC_l. Now observe that the transition dynamics will follow the bit string x1,…,xnx_1,…,x_n with positive probability. Indeed, when the agent takes an action using π at existential decision states, the agent will play an action corresponding to the assignment strategy σ, and at universal states, nature will play the next bit in x1,…,xnx_1,…,x_n with probability 1/2 12. Now, by assumption, x1,…,xnx_1,…,x_n does not satisfy the clause ClC_l, and so this path will reach the dead state at the last timestep, where it gets reward −1-1, but this fact implies that the strategy π obtains negative reward in at least one environment. Ultimately, the above reasoning follows the same logic as (Papadimitriou and Tsitsiklis, 1987). The main difference appears in how we use the multi-observation structure to ensure that σ must be a satisfying assignment strategy for every clause l∈[m]l∈[m]. ∎ F.2. Multi-Observation Semi-Observable MDPs with Fixed Support See 6.2 Proof. Let ∃x1∀x2…∃xn−1∀xnF(x1,…,xn)∃ x_1∀ x_2…∃ x_n-1∀ x_nF(x_1,…,x_n) be a quantified formula with n variables, where F is in conjunctive normal form and has m clauses. We design a MO-SOMDP where there is one environment ℳi=(S,,⏟A,Z,T,Oi,R,b,3n+1⏟H)M_i=(S, \ setTrue, setFalse\_A,Z,T,O_i,R,b, 3n+1_H) for each clause i∈[m]i∈[m]. The state space S comprises an acceptance state, a dead state, and five states per variable (48) S=s,s∪⋃j∈[n]sAj,sTj(0),sTj(1),sTj(−1),sFj(0),sFj(1),sFj(−1).S=\s_ acc,s_ fail\∪ _j∈[n]\s_A_j,s_T_j^(0),s_T_j^(1),s_T_j^(-1),s_F_j^(0),s_F_j^(1),s_F_j^(-1)\. The states sAjs_A_j correspond to decision nodes where either the agent chooses a value for an existential variable, or a value for a universal variable is drawn randomly. The state triplets sTj(0),sTj(1),sTj(−1)\s_T_j^(0),s_T_j^(1),s_T_j^(-1)\ and sFj(0),sFj(1),sFj(−1)\s_F_j^(0),s_F_j^(1),s_F_j^(-1)\ then encode true and false assignments to xjx_j respectively, and the different states within these triplets encode coin flip outcomes. We have a unique observation for each state, along with a special blind observation. That is, (49) Z=z,z∪(⋃j∈[n]zAj,zTj(0),zTj(1),zTj(−1),zFj(0),zFj(1),zFj(−1))∪⊥.Z=\z_ acc,z_ fail\∪ ( _j∈[n]\z_A_j,z_T_j^(0),z_T_j^(1),z_T_j^(-1),z_F_j^(0),z_F_j^(1),z_F_j^(-1)\ )∪\ \. The transition dynamics encode variable assignment and the random coin flips. In particular, if xjx_j, for j∈[n]j∈[n], is an existential variable, then T(sAj,)=sTj(0) T(s_A_j, setTrue)=s_T_j^(0) T(sAj,)=sFj(0). T(s_A_j, setFalse)=s_F_j^(0). Meanwhile, if xjx_j is a universal variable, the next state is random, i.e., T(sAj,a)=sTj(0)↦12,sFj(0)↦12∀a∈A.T(s_A_j,a)= \s_T_j^(0) 12,s_F_j^(0) 12 \ ∀ a∈ A. From states in sTj(0),sFj(0)\s_T_j^(0),s_F_j^(0)\, the environment flips a coin, which we encode in the successor state via the superscript lying in (−1),(1)\(-1),(1)\. T(sTj(0),a)=sTj(1)↦12,sTj(−1)↦12T(sFj(0),a)=sFj(1)↦12,sFj(−1)↦12T(s_T_j^(0),a)= \s_T_j^(1) 12,s_T_j^(-1) 12 \ T(s_F_j^(0),a)= \s_F_j^(1) 12,s_F_j^(-1) 12 \ If the agent matches their action to the coin, they move to the accepting state. Meanwhile, if the agent fails to match the coin, they move to the next variable node, except on the last coin flip, when they move to the dead state. That is, for each j∈[n]j∈[n], we have T(sTj(1),)=T(sFj(1),)=T(sTj(−1),)=T(sFj(−1),)=s T(s_T_j^(1), setTrue)=T(s_F_j^(1), setTrue)=T(s_T_j^(-1), setFalse)=T(s_F_j^(-1), setFalse)=s_ acc T(sTj(1),)=T(sFj(1),)=T(sTj(−1),)=T(sFj(−1),)=sAj+1 if j<ns if j=n. T(s_T_j^(1), setFalse)=T(s_F_j^(1), setFalse)=T(s_T_j^(-1), setTrue)=T(s_F_j^(-1), setTrue)= casess_A_j+1& if j<n\\ s_ fail& if j=n. cases The initial state in each SOMDP is sA1s_A_1. That is b=δsA1b= _s_A_1. The observation changes with the environment in a manner such that satisfying variable assignment allows the agent to see the coin flip value with high probability. We tune the observability of states in the set ⋃j∈[n]sTj(1),sTj(−1),sFj(1),sFj(−1) _j∈[n]\s_T_j^(1),s_T_j^(-1),s_F_j^(1),s_F_j^(-1)\ according to the environment. First, let ϵε be a positive number to be tuned later. If variable j appears positively in clause CiC_i, then sTj(1)s_T_j^(1) and sTj(−1)s_T_j^(-1) are fully observable with high probability. That is Oi(sTj(1))=zsTj(1)↦1−ϵ,⊥↦ϵ O_i(s_T_j^(1))=\z_s_T_j^(1) 1-ε, ε\ Oi(sTj(−1))=zsTj(−1)↦1−ϵ,⊥↦ϵ. O_i(s_T_j^(-1))=\z_s_T_j^(-1) 1-ε, ε\. Conversely, if variable j does not appear positively in clause CiC_i, then the SOMDP emits the blind observation with probability 1/2 12, i.e, Oi(sTj(1))=zsTj(1)↦12,⊥↦12 O_i(s_T_j^(1))= \z_s_T_j^(1) 12, 12 \ Oi(sTj(−1))=zsTj(−1)↦12,⊥↦12. O_i(s_T_j^(-1))= \z_s_T_j^(-1) 12, 12 \. Note that in both cases, the support of Oi(sTj(1))O_i(s_T_j^(1)) is zsTj(1),⊥\z_s_T_j^(1), \, and the same condition holds for sTj(−1)s_T_j^(-1). We define the observation function in an analogous way for the states corresponding to false variable assignment sFj(1),sFj(−1)\s_F_j^(1),s_F_j^(-1)\ depending on whether or not the corresponding variable appears negatively in clause CiC_i. For every environment i, we design the observation such that all states in the set (50) s,s∪⋃j∈[n]sAj,sTj(0),sFj(0)\s_ acc,s_ fail\∪ _j∈[n]\s_A_j,s_T_j^(0),s_F_j^(0)\ are fully observable. That is, the only information possibly hidden from the agent is the result of the coin flip at each stage. Finally, we set the reward function to penalize reaching the dead state s_ fail. That is, we set R(s,a)=−1R(s_ fail,a)=-1 for all actions a in A, and we set the reward to be zero for all other state-action pairs. We now argue that the QSAT instance has a solution if and only if there exists some policy π that attains reward at least −ν-ν, where we set (51) ν:=12m(18)nϵ:=12m(18)n.ν:= 12m ( 18 )^n ε:= 12m ( 18 )^n. Note that we can represent both ν and ϵε as rationals where the denominator is 2m8n2m8^n. As such ν and ϵε have a polynomial bit representation in terms of the QSAT instance, and thus we can still implement this reduction in polynomial time. However, in Remark 1, we also discuss how to modify this transformation so that all integers used to represent the MO-SOMDP are themselves polynomially bounded in terms of the size of the QSAT instance. (⟹ ) First, assume that the QSAT instance is satisfiable with some variable assignment strategy σ. Then, let π be the corresponding MO-SOMDP policy that (1) Takes the action σ recommends at the existential decision nodes. (2) Takes action setTrue whenever a state in sTj(1),sFj(1)\s_T_j^(1),s_F_j^(1)\ is revealed, and takes action setFalse whenever a state in sTj(−1),sFj(−1)\s_T_j^(-1),s_F_j^(-1)\ is revealed. Note that the MO-SOMDP observation functions reveal the prior true-false assignments to the agent, before the hidden coin flip occurs, so that the agent can implement the action-taking strategy described in the first point. The agent can take any arbitrary action when it observes ⊥ . Now fix an environment and clause corresponding to the index i. As σ is a winning strategy for the QSAT instance, it follows that, for any positive-probability path, the agent will either reach sTj(0)s_T_j^(0) for a variable xjx_j that appears positively in CiC_i, or the agent will reach sFj(0)s_F_j^(0) for a variable xjx_j that appears negatively in CiC_i. On reaching such a state, the environment flips a coin and reveals its value with probability 1−ϵ1-ε. As such, the agent’s policy reaches s_ acc before the final time step with probability at least 1−ϵ1-ε, and the agent’s reward is at least −ϵ=−ν-ε=-ν. (⟸ ) Now, conversely, assume that a possibly randomized strategy π∗π^* exists that attains reward at least −ν-ν, and let this strategy be represented by some distribution on the set Π _ det of deterministic policies where pπp_π is the probability of π for π∈Ππ∈ _ det. We additionally assume that these deterministic policies are observation-based, i.e., they are mappings (52) π:⋃t=1HZt→A,π: _t=1^HZ^t→ A, and we use Π, _ det,obs to denote the set of observation-based deterministic policies. This assumption is w.l.o.g., as for any deterministic policy, there exists a deterministic observation-based policy which induces the same path distribution in any POMDP. We argue that the randomized strategy π∗π^* must place positive weight on a deterministic MO-SOMDP strategy that corresponds to a satisfying assignment. We first fix some notation. In particular, for each j∈[n]j∈[n], let j(0)=zFj(0) and j(1)=zTj(0). V_j(0)=z_F_j^(0) and V_j(1)=z_T_j^(0). That is, j V_j encodes a mapping to convert bits to relevant MO-SOMDP observations. We now define a mapping ξ from Π, _ det,obs to the set Σ of mappings σ:∪t=0n/2−10,12t→0,1σ: _t=0^n/2-1\0,1\^2t→\0,1\ that represent QSAT assignment strategies. In particular, for a deterministic observation-based policy π, and a bit string 1,…,2t b_1,…, b_2t, we define an assignment strategy ξ(π)ξ(π) according to (53) (ξ(π))(1,…,2t)=π(zA1,1(1),⊥,zA2,2(2),⊥,…,zA2t,2t(2t),⊥,zA2t+1). (ξ(π) )( b_1,…, b_2t)=π(z_A_1, V_1( b_1), ,z_A_2, V_2( b_2), ,…,z_A_2t, V_2t( b_2t), ,z_A_2t+1). That is, we define ξ(π)ξ(π) using the assignment strategy that π encodes on the event that the agent never sees the coin flip’s value. Note that we slightly abuse notation, as the policy outputs actions in the set ,\ setFalse, setTrue\ rather than bits, but we use the natural remapping. We next define a partition of the space of deterministic policies. First, for each i∈[m]i∈[m], define iP_i as the set of observation-based policies π such that strategy ξ(π)ξ(π) fails to ensure the clause CiC_i is satisfied. Next, define 1=1U_1=P_1, and for all i∈2,…,mi∈\2,…,m\, define i=i∖(1∪…∪i−1)U_i=P_i (P_1∪… _i-1). Finally, define 0U_0 as Π,∖(1∪…∪m) _ det,obs (P_1∪… _m). Clearly 0,…,mU_0,…,U_m forms a partition of Π, _ det,obs. Also, note that 0U_0 contains deterministic POMDP policies which map, via ξ, to QSAT strategies that satisfy all clauses for any universal variable assignment. We can now bound the probability with which policies in iU_i are played as part of the mixed strategy for each i∈[m]i∈[m]. In particular, fix π∈iπ _i as an arbitrary observation-based policy such that the corresponding QSAT assignment strategy fails to satisfy clause i for some universal variable assignment. We first lower bound the probability of reaching the dead state in environment i when following π. By definition, there exists a universal variable assignment such that, when paired with the assignment strategy ξ(π)ξ(π), clause CiC_i is not satisfied. Denote the resulting bit string 1,…,n b_1,…, b_n, where by definition 1,…,n⊧̸Ci b_1,…, b_n C_i. We now argue by induction that the agent will reach the dead state with probability at least (1/8)n( 18)^n. First, assume the history is zA1,1(1),⊥,zA2,2(2),⊥,…,zA2t−1,2t−1(2t−1),⊥,zA2tz_A_1, V_1( b_1), ,z_A_2, V_2( b_2), ,…,z_A_2t-1, V_2t-1( b_2t-1), ,z_A_2t, ending in a decision-state for a universal variable. With probability 1/2 12, the environment chooses its action matching 2t b_2t, so that the bit string continues to be produced and the clause remains unsatisfied. For the guessing stage following this assignment, the next stage has a +1+1-superscript with probability 1/2 12, and a −1-1-superscript with probability 1/2 12, and each of these states emits the blind observation ⊥ with probability 1/2 12. Thus, for the guessing game, no policy can do better than a 3/4 34 success rate, and so the agent must fail the guessing game and transition to sA2t+1s_A_2t+1 with probability at least 1/4 14. For the next case, assume the history is zA1,1(1),⊥,zA2,2(2),⊥,…,zA2t,2t(2t),⊥,zA2t+1z_A_1, V_1( b_1), ,z_A_2, V_2( b_2), ,…,z_A_2t, V_2t( b_2t), ,z_A_2t+1, ending in an existential variable. By assumption, the policy’s next bit choice matches 2t+1 b_2t+1, and the clause CiC_i remains unsatisfied. Thus, by the same logic as above, the environment moves to the state sA2t+2s_A_2t+2 with probability at least 1/4 14. By repeating this reasoning inductively, we can deduce that, when the agent follows the deterministic policy π, they will reach the dead state with probability (1/2)n/2(1/4)n≥(1/8)n( 12)^n/2( 14)^n≥ ( 18 )^n. We can use this fact to then upper bound pi:=∑π∈ipπp_U_i:= _π _ip_π. In particular, by the above argument, we have (54) ℳiπ∗[∑t=0H−1R(st,at)]≤∑π∈ipπℳiπ[∑t=0H−1R(st,at)]≤−∑π∈ipπ(18)n=−pi(18)nE_M_i^π^* [ _t=0^H-1R(s_t,a_t) ]≤ _π _ip_πE_M_i^π [ _t=0^H-1R(s_t,a_t) ]≤- _π _ip_π ( 18 )^n=-p_U_i ( 18 )^n The first inequality follows from the non-positivity of the reward, the second inequality follows from the above reasoning about iU_i, and the final equality follows by definition of pip_U_i. By assumption, we have (55) −12m(18)n=−ν≤ℳiπ∗[∑t=0H−1R(st,at)]≤−pi(18)n,- 12m ( 18 )^n=-ν _M_i^π^* [ _t=0^H-1R(s_t,a_t) ]≤-p_U_i ( 18 )^n, from which we can deduce that pi≤12mp_U_i≤ 12m. Finally, we can deduce that (56) p0=1−∑i∈[m]pi≥1−12>0.p_U_0=1- _i∈[m]p_U_i≥ 1- 12>0. That is, the randomized policy must place positive weight on policies corresponding to assignment strategies that satisfy every clause for every universal variable assignment. However, this fact holds only if there exists a policy in 0U_0, which implies the satisfiability of the QSAT instance. ∎ Remark 1. In the proof of Proposition 6.2, the rationals used in the observation function have numerators and denominators that grow exponentially in the size of the problem, as we depict in Figure 7. We remark that one can prove the same result while keeping the values of the numerators and denominators polynomially bounded, and we sketch this argument below. In particular, we discuss a procedure to build a ME-POMDP (ℳi′)i∈[m](M_i )_i∈[m] such that maxπV(ℳi′)i∈[m]π≥0 _πV_(M _i)_i∈[m]^π≥ 0 if and only if the original QSAT instance is satisfiable, and all the revelation probabilities in (ℳi′)i∈[m](M_i )_i∈[m] have numerators and denominators bounded by 2n+2m2n+2m. We first distribute the revelation probability across multiple copies of the coin flip states in the manner depicted in Figure 8. For each state of the form sTj(⋅)s_T_j^(·) or sFj(⋅)s_F_j^(·) in the original ME-POMDP, we make n+1n+1 copies, so that the agent stays in such a state for n+1n+1 time steps. In particular, if variable xjx_j appears positively in clause i, then, in environment i, the first copy of sTj(1)/sTj(−1)s_T_j^(1)/s_T_j^(-1) is revealed with probability 1−12m1- 12m, and the remaining n copies are revealed with probability 1−181- 18. With this revelation structure, the probability that the agent sees a copy of the state at least once is 1−12m18n1- 12m 18^n. Similar reasoning holds for sFj(1)/sFj(−1)s_F_j^(1)/s_F_j^(-1). Meanwhile, if variable xjx_j does not appear positively in clause i, then each of the n+1n+1 copies of sTj(1)/sTj(−1)s_T_j^(1)/s_T_j^(-1) is revealed with probability 12(n+1) 12(n+1), so that the probability of the agent seeing the state is (57) 1−(1−12(n+1))n+1≤12.1- (1- 12(n+1) )^n+1≤ 12. The above inequality follows from the fact that (1−x)r≥1−rx(1-x)^r≥ 1-rx for any x∈[0,1],r∈ℕx∈[0,1],r . Ultimately, this splitting procedure lets us simulate the reduction from Proposition 6.2 without requiring small probabilities. To handle the small threshold value ν, we also add the component shown in Figure 9 to the start of the POMDP. In particular, the agent starts in this component in every environment, which guarantees it an expected reward of at least 12m18n 12m 18^n. Adding this component to the POMDP then allows us to use 00 as the threshold for the MO-SOMDP decision problem. We now argue that this new MO-SOMDP (ℳi′)i∈[m](M _i)_i∈[m] has non-negative reward if and only if the original QSAT instance is true. The (⟹)( ) direction follows the exact same logic as the proof of Proposition 6.2. Meanwhile, the (⟸)( ) direction requires the following modifications. • When defining the mapping ξ we need to replace ⊥ with ⊥,…,⊥⏟n+1 times ,…, _n+1 times. • When reasoning about the probability of reaching the dead state, we need to observe that the probability of observing the sequence ⊥,…,⊥⏟n+1 times ,…, _n+1 times is (1−12(n+1))n+1≥12 (1- 12(n+1) )^n+1≥ 12 at each stage. sA1s_A_1sT1(0)s_T_1^(0)sT1(1)s_T_1^(1)sT1(−1)s_T_1^(-1)Reveal w.p. 1−12m18n1- 12m 18^nsF1(0)s_F_1^(0)sF1(1)s_F_1^(1)sF1(−1)s_F_1^(-1)Reveal w.p. 1/2 12sA2s_A_2sT2(0)s_T_2^(0)⋯·ssF2(0)s_F_2^(0)⋯·sss_ acc setTrue setFalse1/2 121/2 121/2 121/2 121/2 121/2 12 setFalse setTrue setFalse setTrue setTrue setFalse setTrue setFalse Figure 7. A fragment of an environment corresponding to the clause (x1∨¬x2)(x_1 x_2) for the MO-SOMDP constructed in the proof of Proposition 6.2. Lines leaving nodes correspond to actions, and small dots encode stochastic resolution of the transition dynamics. When an arrow leaves a node without a label, then all actions induce the same dynamics. Blue nodes correspond to satisfaction of the clause, while red nodes correspond to the clause not being satisfied yet. sA1s_A_1sT1(0)s_T_1^(0)sT1(1,0)s_T_1^(1,0)sT1(1,1)s_T_1^(1,1)⋯·ssT1(1,n)s_T_1^(1,n)sT1(−1,0)s_T_1^(-1,0)sT1(−1,1)s_T_1^(-1,1)⋯·ssT1(−1,n)s_T_1^(-1,n)Reveal w.p. 1−12m1- 12mReveal w.p. 1−181- 18Reveal w.p. 1−181- 18sT1(0)s_T_1^(0)sF1(1,0)s_F_1^(1,0)sF1(1,1)s_F_1^(1,1)⋯·ssF1(1,n)s_F_1^(1,n)sF1(−1,0)s_F_1^(-1,0)sF1(−1,1)s_F_1^(-1,1)⋯·ssF1(−1,n)s_F_1^(-1,n)Reveal w.p. 12(n+1) 12(n+1)Reveal w.p. 12(n+1) 12(n+1)Reveal w.p. 12(n+1) 12(n+1)sA2s_A_2s_ acc setTrue setFalse1/2 121/2 121/2 121/2 12 setFalse setTrue setFalse setTrue setTrue setFalse setTrue setFalse Figure 8. A fragment of an environment in the MO-SOMDP constructed during the “splitting” procedure described in Remark 1. s+,0s_+,0s+,1s_+,1⋯·ss+,ns_+,nR(s+,n)=1R(s_+,n)=1s−,0s_-,0s−,1s_-,1⋯·ss−,ns_-,n1−1/2m1- 12m1/2m 12m7/8 787/8 787/8 781/8 181/8 181/8 18 Figure 9. A component one can add to the start of a POMDP to increase the reward by 12m18n 12m 18^n. The agent gets a reward of 11 with small probability. From the states in the set s−,n,s+,n\s_-,n,s_+,n\, the agent transitions to the component shown in Figure 8. F.3. Multi-Observation Intermittently-Observable MDPs with Fixed Support See 6.3 Proof. First, consider the case where one of the IOMDPs is unobservable, i.e., λ=0λ=0. In this case, for all states s, (Oi(s))=⊥i supp(O_i(s))=\ _i\ where ⊥i∈Z _i∈ Z is the blind observation in environment i. As such, by the fixed support condition, there exists some observation ⊥ such that (58) Oi(s)=δ⊥∀i∈[n],s∈S.O_i(s)= _ ∀ i∈[n],s∈ S. That is, a fixed support MO-IOMDP where one environment is unobservable is equivalent to a single BlindMDP. For the remainder of the proof, we assume that the revelation probability is non-zero in all environments. We first argue that each state’s unique observation is the same across environments. As each environment i is an IOMDP with non-zero revelation probability, we can write the support of the observation function at any state s as (59) (Oi(s))=zis,⊥i, supp(O_i(s))=\z_i^s, _i\, where zisz_i^s denotes the unique observation of state s in environment i, and ⊥i _i denotes the no-revelation observation in environment i. By the fixed-support condition, for any state s and pair of environments i,ji,j, zis,⊥i=zjs,⊥j\z_i^s, _i\=\z_j^s, _j\. Thus, we can deduce that (60) ⊥i=⋂s∈Szis,⊥i=⋂s∈Szjs,⊥j=⊥j,\ _i\= _s∈ S\z_i^s, _i\= _s∈ S\z_j^s, _j\=\ _j\, i.e., the no-revelation observation is the same in all environments. The first and last equalities follow from the fact that ⊥i _i is the only observation in environment i that is common to all states, while the middle equality follows from the fixed-support condition. Since the blind observation is common to all environments, we can then deduce also that zis=zjsz_i^s=z_j^s, i.e., each state’s unique observation is constant across the environment. We can now apply the results of (Chen and Liew, 2026) which describe how the value of a policy in an IOMDP changes as we increase the revelation rate, without shuffling observations. In particular, we first recall the following monotonicity result from (Chen and Liew, 2026) for IOMDPs. Lemma F.1 (Adapted from Corollary 11 in (Chen and Liew, 2026)). Fix an underlying MDP ℳ′M , and let ℳλM_λ denote the IOMDP constructed from ℳ′M with revelation probability λ. Additionally, let πλ _λ be an optimal policy for the belief-MDP corresponding to ℳλM_λ. Finally, for an arbitrary policy π and revelation probability ν, let VνπV^π_ν be the value of policy π in IOMDP ℳνM_ν. Then, for any u≥λu≥λ, we have Vλπλ≤Vuπλ.V _λ_λ≤ V _λ_u. In words, Lemma F.1 shows that there exists an optimal policy πλ _λ for ℳλM_λ such that increasing the revelation probability above λ will increase the value that πλ _λ attains. While the result in (Chen and Liew, 2026) is given for infinite-horizon IOMDPs, one can easily apply it to finite-horizon IOMDPs as well. For example, one can encode the finite-horizon IOMDP as an infinite-horizon IOMDP where • States are augmented to include a time component, • The reward corrects the discount factor, • After the agent has taken H actions, the infinite-horizon IOMDP transitions to a dead state with zero reward. We next argue that we can decide the MO-IOMDP problem in non-deterministic polynomial time. We first upper bound the value of a given MO-IOMDP instance. Without loss of generality, we assume that the IOMDPs are ordered such that λ1≤λ2≤…≤λn _1≤ _2≤…≤ _n where λi _i is the revelation probability for ℳiM_i. By Theorem 11 in (Chen and Liew, 2026), the values of these IOMDPs reflect their revelation probabilities. That is, (61) Vℳ1∗≤Vℳ2∗≤…V_M_1^*≤ V_M_2^*≤… We can then easily upper bound the MO-IOMDP value by Vℳ1V_M_1. Indeed, for any policy π, we have (62) miniVℳiπ≤miniVℳi∗=Vℳ1∗. _iV^π_M_i≤ _iV^*_M_i=V^*_M_1. We now observe that an optimal belief-based policy for ℳ1M_1 achieves this value. Indeed, let π1 _1 be an optimal belief-based policy in ℳ1M_1. Then, by Lemma F.1, we have (63) miniVℳiπ1≥miniVℳ1π1=Vℳ1∗. _iV _1_M_i≥ _iV _1_M_1=V^*_M_1. Thus, a MO-IOMDP with fixed support has value at least B if and only if there exists a policy for the environment with the lowest revelation probability with value at least B, and this fact suggests Algorithm 1 as a simple method for solving the value problem in MO-IOMDPs. In short, we can guess and evaluate a policy in the class of optimal IOMDP policies, and by the proof of Proposition 4.2, we can implement this procedure in non-deterministic polynomial time. Algorithm 1 MO-IOMDP 1: IOMDPs ℳ1,…,ℳnM_1,…,M_n that differ in revelation probability λ, along with a value threshold B. 2: Determine the index i∗i^* of the IOMDP with the lowest revelation rate. 3: Non-deterministically guess a policy π in the class of optimal IOMDP policies 4: if ℳiπ[∑t=0H−1R(st,at)]≥BE_M_i^π[ _t=0^H-1R(s_t,a_t)]≥ B then return YES 5: end if ∎ Appendix G Proofs for Section 7 G.1. Time-Dependent Markovian Policies in ME-POMDPs See 7.1 Proof. Fix a tensor (aijk)i∈[m],j∈[n],k∈[n](a_ijk)_i∈[m],j∈[n],k∈[n]. This tensor will encode a 22-vs.-11 game, where the adversary chooses action i∈[m]i∈[m] and two players choose actions j and k independently according to a pair of mixed strategies. We build a ME-BlindMDP (ℳi)i∈[n](M_i)_i∈[n] such that (64) maxπ∈Πmini∈[m]Vℳiπ=max∈Δ([n]),∈Δ([n])min∑j∈[n],k∈[n]i∈[m]aijk[j][j] _π∈ _ MR _i∈[m]V^π_M_i= _x∈ ([n]),y∈ ([n]) _i∈[m] _j∈[n],k∈[n]a_ijkx[j]y[j] In particular, we define a deterministic BlindMDP ℳiM_i as (65) ℳi=(s0∪[n]⏟S,[n]⏟A,⊥⏟Z,T,O,Ri,δs0⏟b,2⏟H),M_i=( \s_0\∪[n]_S, [n]_A, \ \_Z,T,O,R_i, _s_0_b, 2_H), where we set T and O to satisfy (66) T(s0,j)=j∀j∈[n],O(s)=⊥∀s∈s0∪[n],T(s_0,j)=j\ \ ∀ j∈[n], O(s)= \ \ ∀ s∈\s_0\∪[n], and we set RiR_i to satisfy (67) Ri(s0,j)=0∀i∈[m],j∈[n], R_i(s_0,j)=0 ∀ i∈[m],j∈[n], (68) Ri(j,k)=aijk∀i∈[m],j∈[n],k∈[n]. R_i(j,k)=a_ijk ∀ i∈[m],j∈[n],k∈[n]. A time-dependent Markovian policy in this ME-BlindMDP comprises a pair π0 _0 and π1 _1 of distributions in Δ([n]) ([n]), and this policy will have the following value. (69) mini∈[m]j∼π0,k∼π1,s∼T(s0,j)[Ri(s,k)]=mini∈[m]j∼π0,k∼π1[Ri(j,k)]=min∑j∈[n],k∈[n]i∈[m]aijkπ0[j]π1[k]. _i∈[m]E_j _0,k _1,s T(s_0,j)[R_i(s,k)]= _i∈[m]E_j _0,k _1[R_i(j,k)]= _i∈[m] _j∈[n],k∈[n]a_ijk _0[j] _1[k]. Thus, for any fixed rational B, the ME-POMDP has value at least B in time-dependent Markovian policies if and only if the maxmin value of the 22-vs.11 team game that aijka_ijk defines is greater than B. The -hardness of the latter problem is then given by Lemma 24 in (Brice et al., 2026b). Alternatively, one can deduce the -hardness of the 22-vs.-11 game problem by observing that deciding the existence of a solution ,∈Δ([n])x,y∈ ([n]) to the system of equations (70) ∑j∈[n],k∈[n]aijk[j][k]=0∀i∈[m], _j∈[n],k∈[n]a_ijkx[j]y[k]=0 ∀ i∈[m], is -hard, as detailed in (Hansen, 2019). ∎ See 7.2 Proof. Fix a tensor (aijk)i∈[m],j∈[n],k∈[n](a_ijk)_i∈[m],j∈[n],k∈[n]. This tensor will encode a 22-vs.-11 game, where the adversary chooses action i∈[m]i∈[m] and two players choose actions j and k independently according to a pair of mixed strategies. Additionally let ℒ=0,…,n−1L=\0,…,n-1\ and ℐ=[m]I=[m]. We build a ME-MDP (ℳ(i,l))(i,l)∈ℐ×ℒ(M_(i,l))_(i,l) ×L such that (71) maxπ∈Πmin(i,l)∈ℐ×ℒVℳ(i,l)π=max∈Δ([n]),∈Δ([n])min∑j∈[n],k∈[n]i∈[m]aijk[j][k]. _π∈ _ MR _(i,l) ×LV^π_M_(i,l)= _x∈ ([n]),y∈ ([n]) _i∈[m] _j∈[n],k∈[n]a_ijkx[j]y[k]. In particular, we define a deterministic ME-MDP (ℳ(i,l))(i,l)∈ℐ×ℒ(M_(i,l))_(i,l) ×L with (72) ℳ(i,l)=(s0∪ℒ⏟S,[n]⏟A,Tl,R(i,l),δs0⏟b,2⏟H).M_(i,l)=( \s_0\ _S, [n]_A,T_l,R_(i,l), _s_0_b, 2_H). We use the trivial observation set and function, where each state emits a unique observation deterministically. We set TlT_l to satisfy (73) Tl(s0,j)=((j−1+l)modn)∀j∈[n],T_l(s_0,j)=((j-1+l) n) ∀ j∈[n], so that the state at t=1t=1 encodes a shuffled version of the agent’s initial action. We then set the reward function to encode the tensor (aijk)i∈[m],j∈[n],k∈[n](a_ijk)_i∈[m],j∈[n],k∈[n]. R(i,l)(s0,j)=0 R_(i,l)(s_0,j)=0 ∀i∈[m],l∈ℒ,j∈[n], ∀ i∈[m],l ,j∈[n], R(i,l)(j′,k)=ai(((j′−l)modn)+1)k R_(i,l)(j ,k)=a_i(((j -l) n)+1)k ∀i∈[m],j′∈ℒ,l∈ℒ,k∈[n]. ∀ i∈[m],j ,l ,k∈[n]. We remark that, due to the above transition and reward structure, the agent gets aijka_ijk when it plays actions j and k in environment i. Indeed, for any i∈[m],j,k∈[n]i∈[m],j,k∈[n], and l∈ℒl , we have (74) R(i,l)((j−1+l)modn,k)=aijkR_(i,l)((j-1+l) n,k)=a_ijk as, by basic modular arithmetic rules, (((j−1+l)modn)−lmodn)+1=j.(((j-1+l) n)-l n)+1=j. We now prove (71), and we first fix notation. A time-dependent Markovian policy in this MEMDP comprises two mappings π0 _0 and π1 _1 such that (75) πt:s0∪ℒ→Δ([n]) for t∈0,1. _t:\s_0\ → ([n]) for t∈\0,1\. By an abuse of notation, we will identify π0 _0 with π0(s0) _0(s_0) since the first state is always s0s_0. We will then use π1(j′)π^(j )_1 to denote π1(j′)∈Δ([n]) _1(j )∈ ([n]) for j′∈ℒj . To show the ≤ direction of (71), we show that nature can uniformly randomize over the ℒL component of the environment to ensure that the agent can not use state information to improve their reward. Fix a time-dependent Markovian randomized policy (π0,π1)( _0, _1), and define π~1∈Δ([n]) π_1∈ ([n]) as follows. (76) π~1=∑j′∈ℒ1nπ1(j′). π_1= _j 1n _1^(j ). We next evaluate the policy (π0,π1)( _0, _1) when nature uniformly randomizes over ℒL. That is, we evaluate ∑l∈ℒ1nV(i,l)π _l 1nV_(i,l)^π as follows. (77) ∑l∈ℒ1nj∼π0,j′∼Tl(s0,j),k∼π1(j′)[R(i,l)(j′,k)]=∑l∈ℒ1nj∼π0,k∼π1((j−1+l)modn)[R(i,l)((j−1+l)modn,k)]=∑l∈ℒ1nj∼π0k∼π1((j−1+l)modn)[aijk]=∑j∈[n]π0[j]∑k∈[n]∑l∈ℒ1nπ1(j−1+l)modn[k]aijk=∑j∈[n]π0[j]∑k∈[n]π~1[k]aijk. _l 1nE_j _0,j T_l(s_0,j),k _1^(j )[R_(i,l)(j ,k)]= _l 1nE_j _0,k _1^((j-1+l) n)[R_(i,l)((j-1+l) n,k)]\\ = _l 1nE_j _0k _1^((j-1+l) n)[a_ijk]\\ = _j∈[n] _0[j] _k∈[n] _l 1n _1^(j-1+l) n[k]\ a_ijk= _j∈[n] _0[j] _k∈[n] π_1[k]a_ijk. The first equality above uses the transition dynamics definition. The second equality uses (74). The third equality makes the expectation explicit and reorders the sums. The final equality uses the definition of π~1 π_1. Obviously, nature can do better than uniformly randomizing over ℒL by choosing the worst value of l, and so we have (78) mini∈[m]minl∈ℒV(i,l)π≤min∑l∈ℒi∈[m]1nV(i,l)π=min∑j∈[n],k∈[n]i∈[m]π0[j]π~1[k]aijk≤max∈Δ([n]),∈Δ([n])min∑j∈[n],k∈[n]i∈[m]aijk[j][k]. _i∈[m] _l V_(i,l)^π≤ _i∈[m] _l 1nV_(i,l)^π= _i∈[m] _j∈[n],k∈[n] _0[j] π_1[k]a_ijk≤ _x∈ ([n]),y∈ ([n]) _i∈[m] _j∈[n],k∈[n]a_ijkx[j]y[k]. The ≤ of (71) follows by observing that (78) holds for any time-dependent Markovian policy π. We now deduce the ≥ direction of (71). Fix ∈Δ([n]),∈Δ([n])x∈ ([n]),y∈ ([n]). We define π0 _0 and π1 _1 such that (79) π0[j]=[j]∀j∈[n]π1(j′)[k]=[k]∀k∈[n],∀j′∈ℒ. _0[j]=x[j]\ \ ∀ j∈[n] _1^(j )[k]=y[k]\ \ ∀ k∈[n],∀ j . We then observe that, by following similar steps to the (≤)(≤) direction, that for any i∈[m]i∈[m], l∈ℒl , we have j∼π0,j′∼Tl(s0,j)k∼π1j′[R(i,l)(j′,k)]=j∼,k∼[R(i,l)((j−1+l)modn,k)]=j∼,k∼[aijk]=∑j∈[n],k∈[n]aijk[j][k],E_j _0,j T_l(s_0,j)k _1^j [R_(i,l)(j ,k)]=E_j ,k [R_(i,l)((j-1+l) n,k)]=E_j ,k [a_ijk]= _j∈[n],k∈[n]a_ijkx[j]y[k], from which we can deduce the ≥ direction of (71). ∎ See 7.3 Proof. Fix a tensor (aijk)i∈[m],j∈[n],k∈[n](a_ijk)_i∈[m],j∈[n],k∈[n]. We build a MO-POMDP such that (80) maxπ∈Πmini∈[m]Vℳjπ≥0⇔max∈Δ([n]),∈Δ([n])min∑j∈[n],k∈[n]i∈[m]aijk[j][k]≥0 _π∈ _ MR _i∈[m]V_M_j^π≥ 0 _x∈ ([n]),y∈ ([n]) _i∈[m] _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0 As in the proofs of the preceding propositions, we build an environment where the agent must choose their first two actions independently. However, we must overcome the fact that the adversary can not directly edit the environment. To overcome this difficulty, we build an environment in which the adversary reveals information to the agent conditional on the agent taking a certain action. In particular, after the agent has chosen their first two actions, an environment-dependent observation is emitted, and the agent then chooses an action a∗a^* as a function of this observation. Following this stage, the agent plays a guessing game in which they must guess the value of a coin flip. If the agent chose the right value for a∗a^*, the agent sees the true coin value, whereas if the agent chose the wrong action, they see nothing, and the agent suffers a large penalty. As such, the adversarial nature can control the environment dynamics by incentivizing the agent to choose certain actions conditional on the environment. We now formally define the MO-POMDP ℳi=(S,A,Z,T,Oi,R,b,H).M_i=(S,A,Z,T,O_i,R,b,H). We set the state space to have the following structure. S= S= s0 \s_0\ ∪([n]) ∪ ([n] ) ∪([n]×[n]) ∪ ([n]×[n] ) ∪([n]×[n]×[m]) ∪ ([n]×[n]×[m] ) ∪([n]×[n]×[m]×⊥,⊤) ∪ ([n]×[n]×[m]×\ , \ ) We then set the action space to (81) A=[n]∪[m]∪1,2,A=[n]∪[m]∪\1,2\, and the observation space to (82) Z=zj|j∈[m]∪z⊤,z⊥∪z.Z=\z_j|j∈[m]\∪\z_ ,z_ \∪\z_ blind\. We set b=δs0b= _s_0 so that the environment starts in s0s_0, and we set H=5H=5. We design the transition functions to track the actions taken in each time step, and additionally encode a coin flip at the last stage. T(s0,j)=j if j∈[n]1 otherwise T(s_0,j)= casesj& if j∈[n]\\ 1& otherwise cases T(j,k)=(j,k) if k∈[n](j,1) otherwise T(j,k)= cases(j,k)& if k∈[n]\\ (j,1)& otherwise cases T((j,k),i)=(j,k,i) if i∈[m](j,k,1) otherwise T((j,k),i)= cases(j,k,i)& if i∈[m]\\ (j,k,1)& otherwise cases T((j,k,i),a~)=(j,k,i,⊤)↦12,(j,k,i,⊥)↦12∀a~∈A. T((j,k,i), a)= \(j,k,i, ) 12,(j,k,i, ) 12 \ ∀ a∈ A. The “otherwise” cases effectively ensure that the agent always chooses integers from the right set at each stage. We then design the observation function for environment i such that, at the third stage, the agent sees an observation ziz_i that is unique to that environment. The transition function definition also allows the state to encode whether or not the agent played action i in environment i. As such, we can define the observation function to reveal the coin flip result conditional on whether the agent played action i at the third stage. In particular, for any i∈[m]i∈[m], we define the observation function OiO_i in environment i as follows. Oi(s0)=z O_i(s_0)=z_ blind Oi(j)=z O_i(j)=z_ blind ∀j∈[n] ∀ j∈[n] Oi((j,k))=zi O_i((j,k))=z_i ∀j,k∈[n] ∀ j,k∈[n] Oi((,,,,,))=z O_i((j,k,l))=z_ blind ∀j,k∈[n],l∈[m] ∀ j,k∈[n],l∈[m] Oi((j,k,i,⊤))=z⊤ O_i((j,k,i, ))=z_ ∀j,k∈[n] ∀ j,k∈[n] Oi((j,k,i,⊥))=z⊥ O_i((j,k,i, ))=z_ ∀j,k∈[n] ∀ j,k∈[n] Oi((j,k,l,⊤))=z⊤↦12,z⊥↦12 O_i((j,k,l, ))= \z_ 12,z_ 12 \ ∀j,k∈[n],l∈([m]∖i) ∀ j,k∈[n],l∈([m] \i\) Oi((j,k,l,⊥))=z⊤↦12,z⊥↦12 O_i((j,k,l, ))= \z_ 12,z_ 12 \ ∀j,k∈[n],l∈([m]∖i) ∀ j,k∈[n],l∈([m] \i\) Note that, in all cases, the observation function still takes as input a state, but, for these POMDPs, the state may be a tuple of indices, hence the double-parentheses. Finally, the rewards encode (1) The game defined by aijka_ijk, and (2) The rewards from the matching problem. In particular, let M=maxijk|aijk|M= _ijk|a_ijk| represent the highest magnitude value in (aijk)i∈[m],j,k∈[n](a_ijk)_i∈[m],j,k∈[n]. We set R as follows R(s0,a~)=0 R(s_0, a)=0 ∀a~∈A ∀ a∈ A R(j,a~)=0 R(j, a)=0 ∀j∈[n],a~∈A ∀ j∈[n], a∈ A R((j,k),a~)=0 R((j,k), a)=0 ∀j,k∈[n],a~∈A ∀ j,k∈[n], a∈ A R((j,k,i),a~)=aijk R((j,k,i), a)=a_ijk ∀j,k∈[n],i∈[m],a~∈A ∀ j,k∈[n],i∈[m], a∈ A R((j,k,i,⊤),a~)=0 if a~=1−3M otherwise R((j,k,i, ), a)= cases0& if a=1\\ -3M& otherwise cases ∀j,k∈[n],i∈[m] ∀ j,k∈[n],i∈[m] R((j,k,i,⊥),a~)=0 if a~=2−3M otherwise R((j,k,i, ), a)= cases0& if a=2\\ -3M& otherwise cases ∀j,k∈[n],i∈[m] ∀ j,k∈[n],i∈[m] We now argue that (80) holds. (⟹ ) A memoryless policy in this MO-POMDP comprises a sequence (πt)t∈0,1,2,3,4( _t)_t∈\0,1,2,3,4\ of five mappings. Ignoring their behavior on observations that occur with zero probability, these policies take the form π0:z→Δ(A) _0:\z_ blind\→ (A) π1:z→Δ(A) _1:\z_ blind\→ (A) π2:zii∈[m]→Δ(A) _2:\z_i\_i∈[m]→ (A) π3:z→Δ(A) _3:\z_ blind\→ (A) π4:z⊥,z⊤→Δ(A) _4:\z_ ,z_ \→ (A) By an abuse of notation, we will identify π0(z) _0(z_ blind) with π0 _0 and use similar notation for π1 _1. We assume that under these policies the agent receives a non-negative reward in all environments, and we prove that there exist x and y to certify that the right-hand side of (80) holds. In particular, we define the following vectors where ,∈Δ([n])x,y∈ ([n]), (i)∈Δ([m])v^(i)∈ ([m]) for each i∈[m]i∈[m], and ⊤,⊥∈Δ(1,2,3)w_ ,w_ ∈ (\1,2,3\). [j]=π0[1]+∑j′∈A∖[n]π0[j′] if j=1π0[j] otherwise.x[j]= cases _0[1]+ _j ∈ A [n] _0[j ]& if j=1\\ _0[j]& otherwise. cases [k]=π1[1]+∑k′∈A∖[n]π1[k′] if k=1π1[k] otherwise.y[k]= cases _1[1]+ _k ∈ A [n] _1[k ]& if k=1\\ _1[k]& otherwise. cases (i)[i′]=π2(zi)[1]+∑l∈A∖[m]π2(zi)[l] if i′=1π2(zi)[i′] otherwise.v^(i)[i ]= cases _2(z_i)[1]+ _l∈ A [m] _2(z_i)[l]& if i =1\\ _2(z_i)[i ]& otherwise. cases ⊤[1]=π4(z⊤)[1] _ [1]= _4(z_ )[1] ⊥[1]=π4(z⊥)[1] _ [1]= _4(z_ )[1] ⊤[2]=π4(z⊤)[2] _ [2]= _4(z_ )[2] ⊥[2]=π4(z⊥)[2] _ [2]= _4(z_ )[2] ⊤[3]=∑l∈A∖1,2π4(z⊤)[l] _ [3]= _l∈ A \1,2\ _4(z_ )[l] ⊥[3]=∑l∈A∖1,2π4(z⊥)[l] _ [3]= _l∈ A \1,2\ _4(z_ )[l] We now fix an index i∈[m]i∈[m], and argue that (83) ∑j∈[n],k∈[n]aijk[j][k]≥0. _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0. In particular, we evaluate the reward in each environment. When evaluating the reward, we can ignore the state at timesteps 0,10,1, and 22. The expected reward in environment i at time 33 is given by (84) ℳiπ[R(s3,a3)]=∑i′∈[m](i)[i′]∑j∈[n],k∈[n]ai′jk[j][k].E_M_i^π[R(s_3,a_3)]= _i ∈[m]v^(i)[i ] _j∈[n],k∈[n]a_i jkx[j]y[k]. Indeed, the probability of visiting state (j,k,i′)(j,k,i ) at t=3t=3 is [j][k](i)[i′]x[j]y[k]v^(i)[i ] by definition of the transition dynamics. We can then upper bound this step’s reward as follows. (85) ℳiπ[R(s3,a3)]=(i)[i]∑j∈[n],k∈[n]aijk[j][k]+∑i′∈[m]∖i(i)[i′]∑j∈[n],k∈[n]ai′jk[j][k]≤(i)[i]∑j∈[n],k∈[n]aijk[j][k]+∑i′∈[m]∖i(i)[i′]M=(i)[i]∑j∈[n],k∈[n]aijk[j][k]+(1−(i)[i])ME_M_i^π[R(s_3,a_3)]=v^(i)[i] _j∈[n],k∈[n]a_ijkx[j]y[k]+ _i ∈[m] \i\v^(i)[i ] _j∈[n],k∈[n]a_i jkx[j]y[k]\\ ^(i)[i] _j∈[n],k∈[n]a_ijkx[j]y[k]+ _i ∈[m] \i\v^(i)[i ]M\\ =v^(i)[i] _j∈[n],k∈[n]a_ijkx[j]y[k]+(1-v^(i)[i])M In words, the above inequality chain upper bounds the benefit the agent can get in its reward at t=3t=3 by not matching the environment-specific observation. The expected reward at time 44 is given by ℳiπ[R(s4,a4)]=(i)[i](12(1−⊤[1])+12(1−⊤[2]))(−3M)+(1−(i)[i])(14(1−⊤[1])+14(1−⊥[1])+14(1−⊤[2])+14(1−⊥[2]))(−3M).E_M_i^π[R(s_4,a_4)]=v^(i)[i] ( 12(1-w_ [1])+ 12(1-w_ [2]) )(-3M)\\ +(1-v^(i)[i]) ( 14(1-w_ [1])+ 14(1-w_ [1])+ 14(1-w_ [2])+ 14(1-w_ [2]) )(-3M). Indeed, the first component of the sum handles the case where the agent chooses i to match the environment, and the observation reveals the final state. Meanwhile, the second component handles the case where the observation provides no information about the final state. We can then upper bound the expected reward at time 44 as follows. ℳiπ[R(s4,a4)]≤(1−(i)[i])(14(1−⊤[1])+14(1−⊥[1])+14(1−⊤[2])+14(1−⊥[2]))(−3M)≤−3M2(1−(i)[i])E_M_i^π[R(s_4,a_4)]≤(1-v^(i)[i]) ( 14(1-w_ [1])+ 14(1-w_ [1])+ 14(1-w_ [2])+ 14(1-w_ [2]) )(-3M)≤- 3M2(1-v^(i)[i]) Note that, in the second inequality, we use the fact that 1−⊤[1]+1−⊤[2]≥11-w_ [1]+1-w_ [2]≥ 1. We now upper bound the total reward. ℳiπ[R(s3,a3)+R(s4,a4)]≤(i)[i]∑j∈[n],k∈[n]aijk[j][k]−M2(1−(i)[i]).E_M_i^π[R(s_3,a_3)+R(s_4,a_4)] ^(i)[i] _j∈[n],k∈[n]a_ijkx[j]y[k]- M2(1-v^(i)[i]). We can combine this upper bound with the assumption that the reward is non-negative in environment i to deduce that (83) holds. First, consider the case where M=0M=0. If M=0M=0, then aijk=0a_ijk=0 for all i,j,ki,j,k and thus x and y trivially satisfy (83). Now, assume that M>0M>0, and observe that (i)[i]v^(i)[i] must be positive, as otherwise the expected reward is negative. Using the fact that the expected reward is non-negative, we deduce that (86) (i)[i]∑j∈[n],k∈[n]aijk[j][k]≥M2(1−(i)[i])≥0.v^(i)[i] _j∈[n],k∈[n]a_ijkx[j]y[k]≥ M2(1-v^(i)[i])≥ 0. Finally, using the fact that (i)[i]v^(i)[i] is positive, we conclude that ∑j∈[n],k∈[n]aijk[j][k]≥0 _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0. (⟸ ) We now assume that some ,∈Δ([n])x,y∈ ([n]) exist satisfying the inequalities ∑j∈[n],k∈[n]aijk[j][k]≥0 _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0 for all i in [m][m]. We then define the following policy (87) π0(z)= _0(z_ blind)=x π1(z)= _1(z_ blind)=y π2(zi)=δi _2(z_i)= _i π4(z⊤)=δ1 _4(z_ )= _1 π4(z⊥)=δ2. _4(z_ )= _2. Note that we abuse notation as π0(z)∈Δ(A) _0(z_ blind)∈ (A) while ∈Δ([n])x∈ ([n]) and we may have [n]⊊A[n] A. However, we can easily extend π0 _0 as required. We leave π3 _3 undefined as it does not affect the transition dynamics. Fix an environment i. The reward at t=3t=3 satisfies (88) ℳiπ[R(s3,a3)]=∑j∈[n],k∈[n]aijk[j][k]≥0E_M_i^π[R(s_3,a_3)]= _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0 where the last inequality holds by assumption. Meanwhile, the reward at t=4t=4 is zero as (i)[i]=1v^(i)[i]=1, and ⊤[1]=⊥[2]=1w_ [1]=w_ [2]=1, where w and (i)v^(i) are defined as above. ∎ See 7.4 Proof. A time-dependent Markovian policy that attains value at least B exists if and only if there exists a solution μi,νi,π _i, _i,π to the following system of bilinear inequalities and equalities. (89) νi(s,0)=bi(s) _i(s,0)=b_i(s) ∀s∈S,i∈[n], ∀ s∈ S,i∈[n], μi(s,a,t)=νi(s,t)∑z∈ZOi(s)(z)πt(z,a) _i(s,a,t)= _i(s,t) _z∈ ZO_i(s)(z) _t(z,a) ∀i∈[n],s∈S,a∈A,t∈0,…,H−1, ∀ i∈[n],s∈ S,a∈ A,t∈\0,…,H-1\, νi(s,t+1)=∑s′∈S,a∈Aμi(s′,a,t)Ti(s′,a)(s) _i(s,t+1)= _s ∈ S,a∈ A _i(s ,a,t)T_i(s ,a)(s) ∀s∈S,t∈0,…,H−2,i∈[n], ∀ s∈ S,t∈\0,…,H-2\,i∈[n], ∑aπt(z,a)=1 _a _t(z,a)=1 ∀z∈Z,t∈0,…,H−1, ∀ z∈ Z,t∈\0,…,H-1\, πt(z,a)≥0 _t(z,a)≥ 0 ∀z∈Z,t∈0,…,H−1,a∈A, ∀ z∈ Z,t∈\0,…,H-1\,a∈ A, ∑t∈0,…,H−1∑s∈S∑a∈Aμi(s,a,t)Ri(s,a)≥B _t∈\0,…,H-1\ _s∈ S _a∈ A _i(s,a,t)R_i(s,a)≥ B ∀i∈[n]. ∀ i∈[n]. For each i, the tensor ν∈ℝS×0,…,H−1ν ^S×\0,…,H-1\ encodes the probability of visiting each state at each time, and μ∈ℝS×A×0,…,H−1μ ^S× A×\0,…,H-1\ encodes the probability of visiting each state and taking each action at each time. Meanwhile, πt(z,a) _t(z,a) encodes the probability of taking action a upon seeing observation z at time t. Since we can express the value problem as such a system, inclusion in immediately follows. ∎ G.2. Finite-State Controllers in ME-BlindMDPs In this section, we prove the following theorem regarding the complexity of policy synthesis for FSCs. See 7.6 We first give a series of Lemmas on the link between non-negative matrix factorization and ME-POMDPs. We then give the final proof of Theorem 7.6 in Section G.2.2. G.2.1. Supporting results for Theorem 7.6 Definition G.1 (Non-negative matrix factorization (Vavasis, 2009)). A non-negative matrix P∈ℝm×nP ^m× n has a non-negative factorization with rank k if P can be written as the sum of k non-negative rank-one matrices. Lemma G.2. A joint action distribution on (a0,a1)(a_0,a_1) in a BlindMDP can be implemented by a |Q||Q|-state time-dependent FSC if and only if the distribution has a non-negative factorization with fewer than |Q||Q| elements. Proof. In the case of a BlindMDP, the FSC update rule at time t is equivalent to two mappings (90) γt:Q→Δ(A)ηt:Q×A→Δ(Q) _t:Q→ (A) _t:Q× A→ (Q) (⟹ ) Fix an FSC with |Q||Q| states. We can write the joint distribution of the actions (a0,a1)(a_0,a_1) at the first two timesteps as follows p(a0,a1)=∑q1∈Q∑q0∈Qp(q0)p(a0|q0)p(q1|a0,q0)p(a1|q1,q0,a0)=∑q1∈Q∑q0∈Qp(q0)p(a0|q0)p(q1|a0,q0)p(a1|q1).p(a_0,a_1)= _q_1∈ Q _q_0∈ Qp(q_0)p(a_0|q_0)p(q_1|a_0,q_0)p(a_1|q_1,q_0,a_0)= _q_1∈ Q _q_0∈ Qp(q_0)p(a_0|q_0)p(q_1|a_0,q_0)p(a_1|q_1). Note that in the second equality, we use the fact that the distribution of the action a1a_1 only depends on the memory state q1q_1 at t=1t=1. Now, let P[a0,q1]P[a_0,q_1] denote the sum ∑q0∈Qp(q0)p(a0|q0)p(q1|a0,q0) _q_0∈ Qp(q_0)p(a_0|q_0)p(q_1|a_0,q_0), and let W[a1,q1]=p(a1|q1)W[a_1,q_1]=p(a_1|q_1). Note that P and W encode two matrices in ℝ|A|×|Q|R^|A|×|Q| with non-negative entries. We can now write the joint distribution as follows (91) p(a0,a1)=∑q1∈QP[a0,q1]W[a1,q1]=(PW⊤)[a0,a1],p(a_0,a_1)= _q_1∈ QP[a_0,q_1]W[a_1,q_1]=(PW )[a_0,a_1], from which we can deduce that the joint distribution of a0a_0 and a1a_1 has a non-negative factorization with |Q||Q| components. (⟸ ) Conversely, let P∈ℝ|A|×|A|P ^|A|×|A| be a non-negative matrix such that the entry-wise 11-norm satisfies ‖P‖1,1=1||P||_1,1=1 and P has a factorization (92) P=∑l∈[k]l(l)⊤,P= _l∈[k]u^l(v^l) , where lu^l and lv^l are non-negative vectors for each l∈[k]l∈[k]. We can assume w.l.o.g.that each component matrix is non-zero so that ‖l‖1>0||u^l||_1>0 and ‖l‖1>0||v^l||_1>0. Next, observe that 1=‖P‖1,1=∑i∈[|A|],j∈[|A|]|∑l∈[k]l[i]l[j]|=∑i∈[|A|],j∈[|A|]∑l∈[k]|l[i]||l[j]|=∑l∈[k]‖l‖1||l||11=||P||_1,1= _i∈[|A|],j∈[|A|] | _l∈[k]u^l[i]v^l[j] |= _i∈[|A|],j∈[|A|] _l∈[k]|u^l[i]||v^l[j]|= _l∈[k]||u^l||_1||v^l||_1 The first, second, and last equalities follow by definition. The third equality uses the non-negativity of the elements of lu^l and lv^l. We can then write P as (93) P=∑l∈[k]‖l‖1‖l‖1l‖l‖1(l)⊤‖l‖1.P= _l∈[k]||u^l||_1||v^l||_1 u^l||u^l||_1 (v^l ) ||v^l||_1. That is, we can write P as a convex combination of k non-negative rank 11 matrices ⊤wz where w and z are distributions. We can then implement this as the following FSC with Q=[k]Q=[k]. In particular, for each l∈[k]l∈[k], we have ι(l)=‖l‖1||l||1, (l)=||u^l||_1||v^l||_1, η0(l,a)(l′)=1l=l′0 otherwise∀l′∈[k],a∈A, _0(l,a)(l )= cases1&\ l=l \\ 0& otherwise cases ∀ l ∈[k],a∈ A, γ0(l)=l‖l‖1, _0(l)= u^l||u^l||_1, γ1(l)=l‖l‖1. _1(l)= v^l||v^l||_1. Note that we abuse notation slightly by implicitly identifying distributions on the action set with distributions on [|A|][|A|]. ∎ We can prove the hardness of finding such a time-dependent FSC by appealing to non-negative factorization results. In particular, we will construct a ME-POMDP where any policy that gets a non-negative reward must have a joint distribution on a0a_0 and a1a_1 that satisfies a set of constraints, and due to the FSC constraint, this joint distribution will need to have low non-negative rank. A naive route to prove -hardness would be to apply the -hardness of non-negative matrix factorization (Shitov, 2016; Schaefer et al., 2024). However, this approach is insufficient and does not immediately lead to the desired result. A non-negative matrix factorization instance comprises a matrix W and a rank parameter r, and asks whether the matrix W has a non-negative factorization with r components. We can easily encode this decision problem as a ME-POMDP problem by designing a ME-POMDP instance such that the agent gets a non-negative reward if and only if each entry of the joint distribution on a0a_0 and a1a_1 matches an appropriate entry of W/‖W‖1,1W/||W||_1,1 where ‖W‖1,1||W||_1,1 is the entry-wise 11-norm. Clearly, the matrix W has an r-component non-negative factorization if and only if there exists an r-memory-state FSC in the ME-POMDP that attains reward at least zero. However, this reduction does not provide information about the ratios between the number of memory-states |Q||Q| and the number of environments n for which the FSC-synthesis problem is -hard. In particular, we need to carefully examine the values of W and r for which the non-negative factorization problem is -hard to establish the ratios |Q|/n|Q|/n for which the FSC-synthesis problem is -hard in ME-POMDPs. Ultimately, adapting the -hardness proof in (Majumdar, 2026) for the related problem of non-negative Gram feasibility provides an easy route to carefully control the parameters of these W and r matrices. We now present this analysis. We will reduce from the following ETR-complete problem. Definition G.3 (ETR-INV (Abrahamsen and Miltzow, 2019; Abrahamsen et al., 2022)). An ETR-INV instance comprises a set of variables x1,…,xnx_1,…,x_n, and a set of constraints C1,…,CmC_1,…,C_m, where each CjC_j is a constraint of the form (94) x+y=z,x⋅y=1,x=1x+y=z, x· y=1, x=1 for x,y,z∈x1,…,xnx,y,z∈\x_1,…,x_n\. The ETR-INV problem asks if there exists a solution to these constraints with xi∈[1/2,2]x_i∈[1/2,2]. We will also use the following ETR-complete satisfaction problem during the proof. The ETR with addition, multiplication, and inequalities (ETR-AMI) problem appears in (Abrahamsen and Miltzow, 2019) without the non-negativity constraints. However, we refer to the version used in (Majumdar, 2026), where all variables in the solution must be non-negative. Definition G.4 (ETR-AMI). An ETR-AMI instance comprises a set of variables x1,…,xnx_1,…,x_n, and a set of constraints C1,…,CmC_1,…,C_m, where each CjC_j is a constraint of the following form (95) x+y=z,x⋅y=z,x=1x+y=z, x· y=z, x=1 for x,y,z∈x1,…,xnx,y,z∈\x_1,…,x_n\. The ETR-AMI problem asks if there exists a solution to these constraints with xi∈[0,∞)x_i∈[0,∞). We first present the following lemma, which shows that we can convert an ETR-INV instance into an ETR-AMI instance with a solution in which the variables lie in the interval [0,2][0,2]. This lemma is highly similar to those presented in (Abrahamsen and Miltzow, 2019), and we present it to smooth exposition. Lemma G.5 (Adapted from (Abrahamsen and Miltzow, 2019)). Given an ETR-INV instance with n variables and m constraints, there exists an ETR-AMI instance such that (1) The ETR-AMI instance has a solution if and only if the ETR-INV instance has a solution. (2) The ETR-AMI instance has 3n+33n+3 variables, and 3+2n+m3+2n+m constraints (ignoring the implicit non-negativity constraints). (3) The solution of the ETR-AMI instance satisfies xi∈[0,2]x_i∈[0,2]. Proof. Let xix_i be the variables of the original ETR-INV instance. For each xix_i we add two auxiliary variables x¯i x_i and x¯i x_i, along with variables ⟦1⟧,⟦2⟧ 1 , 2 and ⟦1/2⟧ 1/2 to represent constants. We can then encode the original ETR-INV problem as the following ETR-AMI problem. (96) ⟦1⟧=1 1 =1 ⟦1⟧+⟦1⟧=⟦2⟧ 1 + 1 = 2 ⟦2⟧⟦1/2⟧=⟦1⟧ 2 1/2 = 1 xi+x¯i=⟦2⟧∀i∈[n] x_i+ x_i= 2 ∀ i∈[n] xi=⟦1/2⟧+x¯i∀i∈[n] x_i= 1/2 + x_i ∀ i∈[n] (Cj)j∈[m] (C_j)_j∈[m] All variables non-negative. variables non-negative. Note that we encode any constraint xy=1xy=1 in the ETR-INV instance as xy=⟦1⟧xy= 1 in the ETR-AMI instance. Clearly, any solution to the original ETR-INV instance defines a feasible solution to this ETR-AMI instance. The converse also holds, as any assignment to xix_i in the ETR-AMI problem must satisfy xi∈[1/2,2]x_i∈[1/2,2] and satisfy the constraints (Cj)j∈[m](C_j)_j∈[m]. ∎ Following (Majumdar, 2026), we show that ETR-AMI problems can be converted to constrained non-negative matrix factorization. We provide a slighlty different proof from (Majumdar, 2026) as (1) We don’t constrain the factorization to be symmetric, and (2) We define constraints differently so that we can tightly control the number of factorization constraints we add. Lemma G.6 (Adapted from (Majumdar, 2026)). Fix an integer r≥2r≥ 2, and an ETR-AMI instance with n variables and m constraints. There exists a pair of integers (fA,fB)(f_A,f_B), and two sets of matrices A(1),…,A(fA)A^(1),…,A^(f_A), B(1),…,B(fB)B^(1),…,B^(f_B) in ℝn+r,n+rR^n+r,n+r such that the ETR-AMI instance has a solution if and only if there exists a solution W∈ℝn+r,n+rW ^n+r,n+r to (97) ⟨A(ι),W⟩=0∀ι∈[fA] A^( ),W =0 ∀ ∈[f_A] (98) ⟨B(κ),W⟩=1∀κ∈[fB] B^(κ),W =1 ∀κ∈[f_B] where W has a non-negative factorization with r components. Additionally, fA+fB≤r+n+m+1f_A+f_B≤ r+n+m+1 and every entry in the matrices (A(ι)))ι∈[fA](A^( )))_ ∈[f_A] and (B(κ))κ∈[fB](B^(κ))_κ∈[f_B] is in −1,0,1,2\-1,0,1,2\. Proof. We first add the constraints (99) W[i,j]=1i=j0 otherwise∀i∈[r],j∈[r].W[i,j]= cases1&\ i=j\\ 0& otherwise cases ∀ i∈[r],j∈[r]. These constraints serve the same purpose as the anchor constraints in (Majumdar, 2026). Indeed, suppose W has the following non-negative factorization, where U(1),V(1)∈ℝr×rU_(1),V_(1) ^r× r, U(2)∈ℝn×rU_(2) ^n× r, and V(2)∈ℝr×nV_(2) ^r× n. (100) W=[U(1)U(2)][V(1)V(2)].W= bmatrixU_(1)\\ U_(2)\\ bmatrix bmatrixV_(1)&V_(2) bmatrix. The above factorization implies that U(1)V(1)=IU_(1)V_(1)=I, where I is the r×r× r identity matrix. We can then use the following fact, which generalizes Lemma 5.5 in (Majumdar, 2026). Lemma G.7 ((Ding and Rhee, 2014)). If A is non-negative and has a non-negative inverse, then A=DPA=DP, where D is a diagonal matrix with positive diagonal entries, and P is a permutation matrix. We can thus write U(1)U_(1) and V(1)V_(1) in the following forms, where (j1,…,jn)(j_1,…,j_n) is a permutation of [n][n] that encodes the permutation matrix P, and a1,…,ana_1,…,a_n is a sequence of positive real numbers. (101) U(1)=[a1j1⊤anjn⊤]V(1)=[1a1j1…1anjn].U_(1)= bmatrixa_1e_j_1 \\ \\ a_ne_j_n bmatrix V_(1)= bmatrix 1a_1e_j_1&…& 1a_ne_j_n bmatrix. We next add constraints to define the variables. In particular, we add (102) W[r+i,j]=0∀j∈2,…,r,∀i∈[n] W[r+i,j]=0 ∀ j∈\2,…,r\,∀ i∈[n] W[j,r+i]=0∀j∈2,…,r,∀i∈[n] W[j,r+i]=0 ∀ j∈\2,…,r\,∀ i∈[n] W[r+i,1]=W[1,r+i]∀i∈[n]. W[r+i,1]=W[1,r+i] ∀ i∈[n]. The first constraint enforces that only the j1thj_1^th column of U(2)U_(2) be non-zero. Similarly, the second constraint enforces that only the j1thj_1^th row of V(2)V_(2) be non-zero. That, is U(2)U_(2) and V(2)V_(2) have the following forms in any valid factorization, where (qi)i∈[n](q_i)_i∈[n] and (yi)i∈[n](y_i)_i∈[n] are non-negative real numbers. (103) U(2)=[q1j1⊤q2j1⊤qnj1⊤]V(2)=[y1j1y2j1…ynj1]U_(2)= bmatrixq_1e_j_1 \\ q_2e_j_1 \\ \\ q_ne_j_1 bmatrix V_(2)= bmatrixy_1e_j_1&y_2e_j_1&…&y_ne_j_1 bmatrix The final constraint in (102) enforces that, for each i∈[n]i∈[n], we have (104) a1yi=⟨a1j1,yij1⟩=W[1,r+i]=W[r+i,1]=⟨1a1j1,qij1⟩=1a1qi.a_1y_i= a_1e_j_1,y_ie_j_1 =W[1,r+i]=W[r+i,1]= 1a_1e_j_1,q_ie_j_1 = 1a_1q_i. With these constraints, we can then observe that, for any i,j∈[n]i,j∈[n], we have (105) W[r+i,r+j]=⟨qij1,yjj1⟩=qiyj=1a1qia1yj=a1yia1yj.W[r+i,r+j]= q_ie_j_1,y_je_j_1 =q_iy_j= 1a_1q_ia_1y_j=a_1y_ia_1y_j. Ultimately, the value a1yi=1a1qia_1y_i= 1a_1q_i will represent variable xix_i. The constraints in (102) take the same role as the constraints used in (Majumdar, 2026) to encode variables. We can finally add the constraints to encode the ETR-AMI problem. In particular, as in (Majumdar, 2026), for each constraint of the form xi+xj=xkx_i+x_j=x_k, we add the constraint (106) W[r+i,1]+W[r+j,1]=W[r+k,1].W[r+i,1]+W[r+j,1]=W[r+k,1]. For any constraint of the form xixj=xkx_ix_j=x_k we add (107) W[r+i,r+j]=W[r+k,1].W[r+i,r+j]=W[r+k,1]. For a constraint of the form xi=1x_i=1, we add (108) W[r+i,1]=1.W[r+i,1]=1. We have now specified all constraints. We now count the number of constraints, omitting the entry-wise zero constraints. In particular, for the constraints in (99), we have r non-zero equality constraints for the diagonal entries. For the constraints in (102), we have n non-zero-entry equality constraints, one for each variable. Finally, for each of the m constraints in the ETR-AMI instance, we add a linear constraint on W. Overall, the following table summarises these constraints. Source Number of constraints (99) r (102) n (106),(107),(108) m Each of the constraints counted above is linear, and we can represent it in one of the following forms. (109) ⟨A(ι),W⟩=0⟨B(κ),W⟩=1. A^( ),W =0 B^(κ),W =1. By inspecting the constraints, we can see that each entry in these matrices is in −1,0,1,2\-1,0,1,2\. Additionally, let S⊂[r+n]×[r+n]S⊂[r+n]×[r+n] denote the indices of matrix entries which we constrain to be zero in W, and let DSD^S be the indicator of these entries, i.e., (110) DS=∑(i,j)∈Sij⊤.D^S= _(i,j)∈ Se_ie_j . Since W is non-negative, we have ⟨DS,W⟩=0 D^S,W =0 if and only if W[i,j]=0W[i,j]=0 for all (i,j)∈S(i,j)∈ S. Indeed, (111) ⟨DS,W⟩=0⇔∑(i,j)∈SW[i,j]=0⇔W[i,j]=0∀(i,j)∈S. D^S,W =0 _(i,j)∈ SW[i,j]=0 W[i,j]=0\ \ ∀(i,j)∈ S. The second ⇔ holds as W must be non-negative. Note also that DSD^S has binary entries. Thus, we can encode the above constraints with matrices A(1),…,A(fA)A^(1),…,A^(f_A), B(1),…,B(fB)B^(1),…,B^(f_B) so that fA+fB≤r+n+m+1f_A+f_B≤ r+n+m+1. We now argue that the ETR-AMI instance has a solution if and only if there exists a matrix W with an r-non-negative rank factorization that satisfies the specified constraints. (⟸ ) Suppose the constraints have a solution W with non-negative factorization UVUV such that U∈ℝn+r×rU ^n+r× r and V∈ℝr×n+rV ^r× n+r. Now, set xix_i to W[r+i,1]=a1yiW[r+i,1]=a_1y_i for each i, noting that, by assumption a1yia_1y_i is non-negative. We argued earlier in the proof that W[r+i,r+j]=a1yia1yjW[r+i,r+j]=a_1y_ia_1y_j, so we can also deduce that W[r+i,r+j]=xixjW[r+i,r+j]=x_ix_j. We can now conclude that, since we imposed the constraints in (106), (107), and (108), the values x1,…,xnx_1,…,x_n must satisfy the constraints of the ETR-AMI instance. Thus, we can conclude that a solution to the ETR-AMI problem exists. (⟹ ) Suppose the ETR-AMI instance has a solution x1,…,xnx_1,…,x_n, and let x denote the vector where [i]=xix[i]=x_i for each i∈[n]i∈[n]. Then, the following matrix W is a solution to the factorization problem. W=[1r−1⊤r−1Ir−1×r−1n×r−1][1r−1⊤r−1Ir−1×r−1r−1×n]=[1r−1⊤r−1Ir−1×r−1r−1×n×r−1⊤]W= bmatrix1&0_r-1 \\ 0_r-1&I_r-1× r-1\\ x&0_n× r-1 bmatrix bmatrix1&0_r-1 &x \\ 0_r-1&I_r-1× r-1&0_r-1× n bmatrix= bmatrix1&0_r-1 &x \\ 0_r-1&I_r-1× r-1&0_r-1× n\\ x&0_n× r-1&xx bmatrix Indeed, W has a non-negative factorization with r components, and it trivially satisfies the constraints in (99) and (102). Furthermore, because x1,…,xnx_1,…,x_n represents a solution to the ETR-AMI problem, the constraints (106), (107) and (108) are satisfied. ∎ We now connect Lemmas G.5 and G.6 to demonstrate that we can reduce ETR-INV to a non-negative factorization problem with an additional simplex constraint on the factorized matrix. Lemma G.8. Given an ETR-INV instance with n variables and m constraints, and a fixed integer r≥2r≥ 2, there exists a sequence of matrices C1,…,C(f)C^1,…,C^(f) in ℝr+n′×r+n′R^r+n × r+n such that the ETR-INV instance is feasible if and only if there exists a matrix X∈ℝr+n′×r+n′X ^r+n × r+n such that • X has non-negative entries, • ‖X‖1,1=1||X||_1,1=1, i.e., the entries of X sum to 11, • ⟨C(ι),X⟩≥0 C^( ),X ≥ 0 for all ι∈[f] ∈[f], • X has a non-negative factorization with rank r, where f≤5n+m+r+10f≤ 5n+m+r+10 and n′=3n+3n =3n+3. Proof. Fix an ETR-INV instance with n variables and m constraints. Next, build an ETR-AMI instance with n′n variables and m′m constraints according to Lemma G.5, and build the associated matrices A(1),…,A(fA)A^(1),…,A^(f_A), B(1),…,B(fB)B^(1),…,B^(f_B) according to Lemma G.6. The ETR-AMI instance will have n′:=3n+3n :=3n+3 variables, and m′:=3+2n+m :=3+2n+m constraints, while fAf_A and fBf_B satisfy fA+fB≤n′+m′+r+1=3n+3+3+2n+m+r+1=5n+m+r+7f_A+f_B≤ n +m +r+1=3n+3+3+2n+m+r+1=5n+m+r+7. Additionally, assume w.l.o.g. that B(1)B^(1) encodes the constraint W[1,1]=1W[1,1]=1. We build the following linear inequality system from the above matrices. (112) ⟨A(ι)−A(ι+1),X⟩≥0 A^( )-A^( +1),X ≥ 0 ∀ι∈1,…,fA−1 ∀ ∈\1,…,f_A-1\ ⟨A(fA)−A(1),X⟩≥0 A^(f_A)-A^(1),X ≥ 0 ⟨A(1),X⟩≥0 A^(1),X ≥ 0 ⟨−A(1),X⟩≥0 -A^(1),X ≥ 0 ⟨B(κ)−B(κ+1),X⟩≥0 B^(κ)-B^(κ+1),X ≥ 0 ∀κ∈1,…,fB−1 ∀κ∈\1,…,f_B-1\ ⟨B(fB)−B(1),X⟩≥0 B^(f_B)-B^(1),X ≥ 0 ⟨B(1)−12(r+4n+4n2)⊤,X⟩≥0 B^(1)- 12(r+4n+4n^2)11 ,X ≥ 0 Note that this system involves fA+fB+3f_A+f_B+3 inequalities of the form ⟨C,X⟩≥0 C,X ≥ 0. We claim that (112) has a solution with X such that • X≥0X≥ 0, • ‖X‖1,1=1||X||_1,1=1, and • X has a non-negative factorization with r components. if and only if the original ETR-INV problem has a solution. (⟹ ) Suppose X is a solution to (112) with the desired properties. We immediately deduce that it must satisfy (113) ⟨A(ι),X⟩=0 A^( ),X =0 ∀ι∈1,…,fA ∀ ∈\1,…,f_A\ ⟨B(κ),X⟩=ν B^(κ),X =ν ∀κ∈1,…,fB ∀κ∈\1,…,f_B\ for some ν∈ℝν . Additionally, the final constraint implies, along with the fact that ‖X‖1,1=1||X||_1,1=1, implies that (114) ⟨B(1),X⟩≥⟨12(r+4n+4n2)⊤,X⟩=12(r+4n+4n2)>0, B^(1),X ≥ 12(r+4n+4n^2)11 ,X = 12(r+4n+4n^2)>0, which in turn implies that, in fact, ν>0ν>0. Now, define X~=X/ν X=X/ν. X~ X is now a matrix that satisfies (113) with ν=1ν=1, and X~ X also has an r-component non-negative factorization. However, by Lemma G.6 and Lemma G.5, we can now deduce that the original ETR-INV instance is feasible. (⟸ ) Suppose the ETR-INV instance has a solution. As a result, the constructed ETR-AMI instance has a solution x1,…,xnx_1,…,x_n where xi∈[0,2]x_i∈[0,2] for every i by Lemma G.5. As in the proof of Lemma G.6, we can now deduce that the following matrix W is a solution to (113) with ν=1ν=1, where we use x to denote the vector with the ETR-AMI solution as its elements. W=[1r−1⊤r−1Ir−1×r−1n×r−1][1r−1⊤r−1Ir−1×r−1r−1×n]=[1r−1⊤r−1Ir−1×r−1r−1×n×r−1⊤]W= bmatrix1&0_r-1 \\ 0_r-1&I_r-1× r-1\\ x&0_n× r-1 bmatrix bmatrix1&0_r-1 &x \\ 0_r-1&I_r-1× r-1&0_r-1× n bmatrix= bmatrix1&0_r-1 &x \\ 0_r-1&I_r-1× r-1&0_r-1× n\\ x&0_n× r-1&xx bmatrix We need to construct a scaling of W that lies in the simplex and satisfies (112). By counting the elements of W and using the bound on the value of the elements of x, we have (115) ‖W‖1,1≤‖Ir×r‖1,1+2||||1+‖⊤‖1,1≤r+4n+4n2.||W||_1,1≤||I_r× r||_1,1+2||x||_1+||xx ||_1,1≤ r+4n+4n^2. Also, note that ‖W‖1,1>0||W||_1,1>0 as W is non-zero. Thus, we can define X=W/‖W‖1,1X=W/||W||_1,1 and observe that ⟨B(1),X⟩=X[1,1]=1/‖W‖1,1≥1/(r+4n+4n2)≥1/2(r+4n+4n2). B^(1),X =X[1,1]=1/||W||_1,1≥ 1/(r+4n+4n^2)≥ 1/2(r+4n+4n^2). Furthermore, by linearity, X satisfies (113) for some ν, from which it follows that X is a matrix that satisfies (112). Also, because W has an r-component non-negative factorization, so does X, and trivially, X satisfies ‖X‖1,1=1||X||_1,1=1. ∎ G.2.2. Proof of Theorem 7.6 Fix a rational α∈(0,1)α∈(0,1). Fix an ETR-INV instance with n variables and m constraints, and construct an integer r such that (116) r=⌈α1−α(5n+m+10)⌉,r= α1-α(5n+m+10) , where, for a real number u, ⌈u⌉ u is the smallest integer greater than or equal to u. Note that, since α is fixed, r is bounded by (m+n)O(m+n), and the time to compute r is bounded by a polynomial in the representation size of α, which is fixed, and the size of the original ETR-INV instance. Next, build the system of constraints C(1)…C(f)C^(1)… C^(f) specified in Lemma G.8, where f≤5n+m+r+10f≤ 5n+m+r+10. We will build a ME-POMDP with an environment for each ι∈[f] ∈[f]. Note that we have (117) r≥α1−α(5n+m+10)⟹(1−α)r≥α(5n+m+10)⟹r≥α(5n+m+r+10)≥αf.r≥ α1-α(5n+m+10) (1-α)r≥α(5n+m+10) r≥α(5n+m+r+10)≥α f. From this stage, we follow the same construction as in the proof of Proposition 7.1. The only modifications we make are that • The set of environments is [f][f]. • In environment ι , the reward at state (j,k)(j,k) is Rι(j,k)=C(ι)[j,k]R_ (j,k)=C^( )[j,k]. Note that, in environment ι , the reward is (118) (j,k)∼Pπ[Rι(j,k)]=⟨Pπ,C(ι)⟩,E_(j,k) P^π[R_ (j,k)]= P^π,C^( ) , where PπP^π is the joint distribution on a0a_0 and a1a_1 induced by the time-dependent finite-state controller π. We now claim that the value of this ME-POMDP is non-negative if and only if the ETR-INV instance has a solution. (⟹ ) Suppose a time-dependent FSC policy π, with r memory states exists such that (119) ⟨Pπ,C(ι)⟩≥0∀ι∈[f]. P^π,C^( ) ≥ 0 ∀ ∈[f]. By Lemma G.2, PπP^π is a joint-distribution matrix with an r-component non-negative factorization. Then, by Lemma G.8, the original ETR-INV instance has a solution. (⟸ ) If the ETR-INV instance has a solution, then by Lemma G.8, there exists a matrix X with an r-component non-negative factorization such that X has non-negative entries, ‖X‖1,1=1||X||_1,1=1, and (120) ⟨X,C(ι)⟩≥0∀ι∈[f]. X,C^( ) ≥ 0 ∀ ∈[f]. By Lemma G.2, there exists an r-state time-dependent FSC policy such that Pπ=XP^π=X, and thus there exists a policy π such that (121) (j,k)∼Pπ[Rι(j,k)]≥0∀ι∈[f].E_(j,k) P^π[R_ (j,k)]≥ 0 ∀ ∈[f]. Finally, we claim that the ME-POMDP (1) Lies in the specified α-decision class, and (2) Can be constructed in polynomial time from the given ETR-INV instance. The constructed POMDP has f environments, and we look for an FSC with r states. It then follows from (117) that the ratio of memory-states to environments is greater than α. For the second claim, we first note that the ETR-INV to ETR-AMI instance conversion can obviously be done in polynomial time. We next note that r≤1+α1−α(5n+m+10)r≤ 1+ α1-α(5n+m+10), which means the A(ι)A^( ) and B(κ)B^(κ) matrices have polynomial size in the original ETR-INV instance size. We can clearly translate the ETR-AMI instance into these A(ι)A^( ) and B(κ)B^(κ) in polynomial time, as writing each matrix requires at most looking up data from the ETR-AMI instance and translating it to these matrices as described in the proof of Lemma G.6. Building all but one of the C(ι)C^( ) matrices described in Lemma G.8 then simply requires basic addition and subtraction between some A(ι)A^( ) and B(κ)B^(κ) matrices, all of which have values in −1,0,1,2\-1,0,1,2\. The remaining C(ι)C^( ) matrix is of the form (122) 11⊤−12(r+4n+4n2)⊤,e_1e_1 - 12(r+4n+4n^2)11 , which can clearly be built in polynomial time. Finally, once we have constructed the C(ι)C^( ) matrices, we can build the POMDP in polynomial time. Indeed, the POMDP has size defined by the following inequalities • |S|=1+r+n′≤1+(3n+3)+1+α1−α(5n+m+10)|S|=1+r+n ≤ 1+(3n+3)+1+ α1-α(5n+m+10). • |A|=|S|−1|A|=|S|-1. • |Z|=1|Z|=1. • The number of environments is f≤5n+m+r+10≤5n+m+11+α1−α(5n+m+10)f≤ 5n+m+r+10≤ 5n+m+11+ α1-α(5n+m+10). • The number of memory states satisfies r≤fr≤ f. We can clearly write the transition and observation functions in polynomial time, as all transitions/observation are deterministic. To encode the reward functions, we simply need to copy the C(ι)C^( ) matrices into the reward function as appropriate. □ G.3. Finite-State Controllers in General ME-POMDPs See 7.7 Proof. Fix a tensor (aijk)i∈[m],j∈[n],k∈[n](a_ijk)_i∈[m],j∈[n],k∈[n]. Furthermore, assume that matrices come in pairs with opposite signs. That is, (123) ∀i∈[m]∃i′∈[m]:aijk=−ai′jk∀j∈[n],k∈[n].∀ i∈[m]\ ∃ i ∈[m]: a_ijk=-a_i jk ∀ j∈[n],k∈[n]. Indeed, this class of tensors can encode the problem of deciding if there exists a solution ,∈Δ([n])x,y∈ ([n]) such that (124) ∑j∈[n],k∈[n]bijk[j][k]=0∀i∈[m] _j∈[n],k∈[n]b_ijkx[j]y[k]=0 ∀ i∈[m] for some tensor bijkb_ijk, and this problem is -complete (Hansen, 2019). We build a ME-POMDP (ℳi)i∈[m](M_i)_i∈[m] such that there exists an FSC-based policy with non-negative reward in all environments if and only if there exists ,∈Δ([n])x,y∈ ([n]) such that (125) ∑j,k∈[n]aijk[j][k]≥0∀i∈[m]. _j,k∈[n]a_ijkx[j]y[k]≥ 0 ∀ i∈[m]. In particular, we define POMDP ℳiM_i, for i∈[m]i∈[m], according to (126) ℳi=(S,[n]∪[m]⏟A,[m]∪⊥⏟Z,T,O,Ri,b,4⏟H).M_i=(S, [n]∪[m]_A, [m]∪\ \_Z,T,O,R_i,b, 4_H). We define the state space as (127) S=s0∪([n]×[m]×1,2,3).S=\s_0\∪([n]×[m]×\1,2,3\). We define the transition function in a similar manner to the proof of Proposition 7.2, but we additionally add a randomly drawn component of the environment. In particular, we define T as follows. T(s0,j)=(j,1,1)↦1m,…,(j,m,1)↦1m T(s_0,j)= \(j,1,1) 1m,…,(j,m,1) 1m \ ∀j∈[n] ∀ j∈[n] T(s0,j)=(1,1,1)↦1m,…,(1,m,1)↦1m T(s_0,j)= \(1,1,1) 1m,…,(1,m,1) 1m \ ∀j∉[n] ∀ j∉[n] T((j,l,1),a)=(j,l,2) T((j,l,1),a)=(j,l,2) ∀j∈[n],l∈[m],a∈A ∀ j∈[n],l∈[m],a∈ A T((j,l,2),a)=(j,l,3) T((j,l,2),a)=(j,l,3) ∀j∈[n],l∈[m],a∈A ∀ j∈[n],l∈[m],a∈ A We then define the observation function such that the random component of the environment is perfectly observed at time 11, i.e., O(s0)=⊥ O(s_0)= O((,,,,,))=l O((j,l,1))=l ∀j∈[n],l∈[m], ∀ j∈[n],l∈[m], O((j,l,2))=⊥ O((j,l,2))= ∀j∈[n],l∈[m], ∀ j∈[n],l∈[m], O((j,l,3))=⊥ O((j,l,3))= ∀j∈[n],l∈[m]. ∀ j∈[n],l∈[m]. We define the reward function at states in [n]×[m]×2[n]×[m]× 2 so that the agent must guess the random component of the state at t=2t=2, (128) Ri((j,l,2),a)=0 if a=l,−1 otherwise,R_i((j,l,2),a)= cases0& if a=l,\\ -1& otherwise, cases Meanwhile, the reward function at states in [n]×[m]×3[n]×[m]× 3 encodes the tensor. That is (129) Ri((j,l,3),k)=aijk if k∈[n],aij1 otherwise .R_i((j,l,3),k)= casesa_ijk& if k∈[n],\\ a_ij1& otherwise . cases We set rewards for all other states to be zero for all actions. We now argue that this ME-POMDP has a time-dependent-FSC-based policy with m states if and only if there exists ,∈Δ([n])x,y∈ ([n]) such that (125) holds. (⟹ ) Fix a policy π. Since all environments share transition and observation dynamics, the joint distribution on the memory state q2q_2 at time 22, and the observation at time 11 is constant across the environments. We define the matrix P∈ℝm×mP ^m× m to encode the distribution of q2q_2 conditioned on each possible observation at time 11. That is, (130) P[k,j]:=ℙℳiπ[q2=k|z1=j]∀k,j∈[m],P[k,j]:=P^π_M_i[q_2=k|z_1=j] ∀ k,j∈[m], where the definition of P does not depend on the choice of environment i. Note that, by definition of the observations, the observation z1z_1 at time 11 is l if and only if the state at time 11 lies in the set Sl:-(j,l,1)|j∈[n]S_l \(j,l,1)|j∈[n]\. At time 22, the state lies in the set [n]×[m]×2[n]×[m]×\2\, and so the observation is ⊥ . As such, the relationship between the action and memory-state at time 22 on any feasible path is determined by a matrix F∈ℝ|A|×mF ^|A|× m where F[k,l]F[k,l] is the probability of taking action k conditioned on the memory state being l at time 22. We use F_ trunc to denote the matrix formed by restricting F to its first m rows, so that it becomes a square matrix. With this notation fixed, we can then evaluate reward at time 22 in environment i. In particular, we have (131) ℳiπ[Ri(s2,a2)]=∑j∈[n],l∈[m]∑k∈ARi((j,l,2),k)ℙℳiπ[s2=(j,l,2),a2=k]=−∑l∈[m]∑k∈A∖lℙπℳi[s2∈(j,l,2)|j∈[n],a2=k]=−∑l∈[m]∑k∈A∖lℙπℳi[z1=l,a2=k]=−∑l∈[m]∑k∈A∖lℙπℳi[a2=k|z1=l]ℙℳiπ[z1=l]E_M_i^π[R_i(s_2,a_2)]= _j∈[n],l∈[m] _k∈ AR_i((j,l,2),k)P^π_M_i[s_2=(j,l,2),a_2=k]\\ =- _l∈[m] _k∈ A \l\P^π_M_i[s_2∈\(j,l,2)|j∈[n]\,a_2=k]\\ =- _l∈[m] _k∈ A \l\P^π_M_i[z_1=l,a_2=k]=- _l∈[m] _k∈ A \l\P^π_M_i[a_2=k|z_1=l]P_M_i^π[z_1=l] The first equality just involves expanding the expectation. The second equality follows by definition of the reward. The third equality applies the definition of the POMDP, and in particular, it applies the fact that the state is in (j,l,2)|j∈[n]\(j,l,2)|j∈[n]\ at time 22 if and only if the first observation was l. The fourth equality just applies conditional probability rules. We next argue that ℙℳiπ[a2=l|z1=l]=1P^π_M_i[a_2=l|z_1=l]=1 in all environments for all l∈[m]l∈[m]. We first note that the reward at time 22 is the same across environments, since the expression derived in (131) depends only on the probabilities of states and actions along the path. However, by the assumption encoded in (123), for any policy π, there exists an environment such that the reward at t=3t=3 is non-positive. Thus, for the policy π to have non-negative value, it must hold that π[Ri(s2,a2)]≥0E^π[R_i(s_2,a_2)]≥ 0, where we now drop the ℳiM_i subscript to emphasize that values are constant across all environments for any policy π. We also note that for every l∈[m]l∈[m], ℙ[z1=l]=1mP[z_1=l]= 1m. Thus we can deduce from (131) that (132) ∑k∈A∖lℙπ[a2=k|z1=l]=0∀l∈[m]. _k∈ A \l\P^π[a_2=k|z_1=l]=0 ∀ l∈[m]. The requirement that a2=z1a_2=z_1 then allows us to argue about the memory structure. Indeed, we have, for all k,l∈[m]k,l∈[m], (133) ℙ[a2=k|z1=l]=∑j∈[m]F[k,j]P[j,l]=1k=l0 otherwise,P[a_2=k|z_1=l]= _j∈[m]F[k,j]P[j,l]= cases1&\ k=l\\ 0& otherwise cases, which in turn implies that (134) FP=Im×m.F_ truncP=I_m× m. However, since F_ trunc and P are non-negative, it follows from (Ding and Rhee, 2014) that P is a permutation matrix. That is, the memory state at time 22 must be equal to the observation at time 11, up to some relabeling. Since the agent observes only ⊥ at times 22 and 33, the action a3a_3 at time 33 is independent of a0a_0, conditioned on the memory state q2q_2 at time 22. Thus, we have (135) ℙπ[a3=k,a0=j]=∑l∈[m]ℙπ[a3=k|q2=l]ℙπ[q2=l,a0=j],P^π[a_3=k,a_0=j]= _l∈[m]P^π[a_3=k|q_2=l]P^π[q_2=l,a_0=j], where we continue to drop the ℳiM_i from the subscript of the probability measure to emphasize when properties are independent of the environment. However, we argued above that q2q_2 must be a permutation of the observation at time 11, which is independent of the action a0a_0 and has a uniform distribution. As such, we can rewrite the joint distribution of a3a_3 and a0a_0 as (136) ℙπ[a3=k,a0=j]=∑l∈[m]ℙπ[a3=k|q2=l]1m⏟=:g[k]ℙπ[a0=j].P^π[a_3=k,a_0=j]= _l∈[m]P^π[a_3=k|q_2=l] 1m_=:g[k]P^π[a_0=j]. In a similar manner to previous proofs, we can then define two vectors ,∈Δ([n])x,y∈ ([n]) (137) [j]=ℙπ[a0=1]+∑j′∈A∖[n]ℙ[a0=j′] if j=1,ℙπ[a0=j] otherwise.x[j]= casesP^π[a_0=1]+ _j ∈ A [n]P[a_0=j ]& if j=1,\\ P^π[a_0=j]& otherwise. cases (138) [k]=g[1]+∑k′∈A∖[n]g[k′] if k=1,g[k] otherwise.y[k]= casesg[1]+ _k ∈ A [n]g[k ]& if k=1,\\ g[k]& otherwise. cases By definition of the ME-POMDP, the reward in environment i when t=3t=3 is equal to (139) ∑j∈[n],k∈[n]aijk[j][k]. _j∈[n],k∈[n]a_ijkx[j]y[k]. As we established earlier, the reward at t=2t=2 is zero. As such, for the ME-POMDP to have non-negative reward, the reward at t=3t=3 must be non-negative in all environments. However, we can then deduce the existence of the requisite x and y. (⟸ ) Suppose there exists x and y such that (140) ∑j∈[n],k∈[n]aijk[j][k]≥0∀i∈[m]. _j∈[n],k∈[n]a_ijkx[j]y[k]≥ 0 ∀ i∈[m]. Then, we can define a FSC-based policy π where • The action at time 00 is drawn from [n][n] according to x for any memory state. • At time 11, the memory is updated to store the observation z1z_1. • At time 22, the policy plays the action corresponding to the stored observation. • The action at time 33 is drawn from [n][n] according to y for any memory state. At time 22 we get zero reward in all POMDPs as we have a2=z1a_2=z_1. Meanwhile, at time 33 we have non-negative expected reward in all POMDPs as the joint distribution of a0a_0 and a3a_3 satisfies (141) ℙ[a0=j,a3=k]=[j][k].P[a_0=j,a_3=k]=x[j]y[k]. ∎