Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs
arXiv:2605.12262v1 [cs.AI] 12 May 2026
Joshua Wendland1 , Markel Zubia1 , Roman Andriushchenko2 , Maris F. L. Galesloot3 , Milan Ceska2 , Henrik von Kleist4 , Thiago D. Simão5 , Maximilian Weininger1 and Nils Jansen1,3 1 Ruhr University Bochum 2 Brno University of Technology 3 Radboud University Nijmegen 4 Harvard University 5 Eindhoven University of Technology {joshua.wendland, markel.zubia}@ruhr-uni-bochum.de Abstract We introduce missingness-MDPs (miss-MDPs), a novel subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. A miss-MDP is a POMDP whose observation function is a missingness function, specifying the probability that individual state features are missing (i.e., unobserved) at a time step. The literature distinguishes three canonical missingness types: missing (1) completely at random (MCAR), (2) at random (MAR), and (3) not at random (MNAR). Our planning problem is to compute near-optimal policies for a miss-MDP with an unknown missingness function, given a dataset of action–observation trajectories. Achieving such optimality guarantees for policies requires learning the missingness function from data, which is infeasible for general POMDPs. To overcome this challenge, we exploit the structural properties of different missingness types to derive probably approximately correct (PAC) algorithms for learning the missingness function. These algorithms yield an approximate but fully specified miss-MDP that we solve using off-the-shelf planning methods. We prove that, with high probability, the resulting policies are ε-optimal in the true miss-MDP. Empirical results confirm the theory and demonstrate superior performance of our approach over two model-free POMDPs methods.
1
Introduction
Markov decision processes (MDPs; Puterman, 1994) capture sequential decision-making under uncertainty. A typical assumption is that all state features are fully observable at all times. In practice, however, features may be missing, e.g. due to sensor failures, so decisions must be made from incomplete information. For instance, a medical doctor may diagnose a patient based on recorded measurements such as heart rate and temperature that are potentially incomplete. Our problem is to compute optimal policies for MDPs with dynamically missing state features. While the MDP structure
and historical data are given, the process governing missingness is unknown. Partially observable Markov decision processes (POMDPs; Åström, 1965) naturally capture this setting, with an observation function specifying the probability of receiving partial state information, of which missing features are a special case. However, the observation function is unknown and must, in principle, be learned from action–observation histories. Yet, learning the observation function of a POMDP is notoriously challenging: In general, it is unidentifiable from histories alone (Allman et al., 2009; Finesso, 1990; Gilbert, 1959; Tune et al., 2013), and even without requiring identifiability (i.e. merely seeking a model consistent with the data), learning remains both statistically (Krishnamurthy et al., 2016; Xiong et al., 2022; Golowich et al., 2022) and computationally intractable (Terwijn, 2002; Mossel and Roch, 2005). Our core contribution is exploiting the theory of missing data (Schafer and Graham, 2002; Buuren, 2018; Little and Rubin, 2019) to define suitable identifiability assumptions for POMDPs. We introduce missingness-MDPs (miss-MDPs) as a proper subclass of POMDPs. In miss-MDPs, the observation function is a missingness function that generates either perfect or missing information for each state feature. We classify this function as missing completely at random (MCAR), missing at random (MAR), or missing not at random (MNAR), following Rubin (1976), detailed in Section 3. We refine our problem statement: Given a miss-MDP with an unknown missingness function and a dataset of actions and observations, the goal is to compute a policy that maximizes the expected reward. We assume that the underlying MDP and, thus, the transition function are known. In the doctorpatient example, the transition function captures the change in the patient’s health status (Komorowski et al., 2018), see Figure 1. Similarly, in a robot navigation task, the probability of transitioning to a subsequent state may be known, while sensor failures can still introduce missingness and, therefore, partial observability. To obtain guarantees on the result, we approximate the unknown missingness function from the dataset, and thereby the original miss-MDP. For this approximate miss-MDP, we compute an approximately optimal policy through off-the-shelf POMDP solvers such as SARSOP (Kurniawati et al., 2008). Missingness functions are not learnable in general (Bhattacharya et al., 2020), yet we identify and,
Doctor
Agent
Policy
Miss-MDP
action
MDP
state
current belief
Belief Update
Intensive Care Unit (ICU)
observation mis. indicator
Missingness Function
Figure 1: A doctor-treating-patient example (blue annotations) of an agent interacting with a miss-MDP. The missingness function causes the heart rate feature of the state to go missing, indicated as ⊥ in the observation. The missingness indicator evaluates to 0 for missing features and to 1 otherwise.
subsequently, focus on missingness functions that are tractable to learn. In summary, our contributions are: 1. We introduce miss-MDPs, which integrate and define the semantics of missing data in a proper subclass of the more general POMDP framework (Section 3). 2. We prove that state beliefs do not always depend on the missingness function’s probabilities (Remark 1), similar to ignorability of missing data (Little and Rubin, 2019). 3. We present probably approximately correct (PAC) learning algorithms for tractable subclasses of the three missingness types. (Sections 4.1 and 4.2). 4. We prove that by using these algorithms, we approximate the ε-optimal policy for the miss-MDP under the correct assumption on the missingness function (Section 4.3). Our empirical evaluation (Section 5) confirms our theoretical results and highlights the practical advantages of our approach: (1) When using datasets of moderate size to learn the missingness function, the performance of the resulting policies converges to that of the optimal policy; and (2) our policies show superior performance in comparison to POMCP (Silver and Veness, 2010) and PPO (Schulman et al., 2017), which use the direct POMDP formulation of the missingness problem.
Related work Our work builds on a rich literature in missing data analysis, see e.g. (Tsiatis, 2006; Little and Rubin, 2019). Classical assumptions such as MCAR, MAR, and MNAR provide highlevel categories. More refined tools, such as missingness graphs, allow one to encode assumptions about the missingness in a structured way (Mohan et al., 2013; Shpitser et al., 2015), leading to highly specific learnability results (Bhattacharya et al., 2020; Nabi et al., 2020). Our setting departs from the standard missing data paradigm in several important aspects. In particular, the concept of missingness is embedded in the setting of solving POMDPs, enabling a more principled understanding of missingness in the context of sequential decision-making under uncertainty. Prior work on MDPs with missing observations has focused mainly on reinforcement learning, where missing data is treated as incidental rather than explicitly modeled. Both full observations (Chen et al., 2023) or individual features
may be missing (Shim et al., 2018; Yoon et al., 2019; Böck et al., 2022). Some approaches pre-process missingness in observations for RL agents (Wang et al., 2019), while others adopt model-based methods, often restricted to simpler settings such as MCAR (Futoma et al., 2020). Planning approaches typically neglect distinctions between MCAR, MAR, and MNAR (Liu et al., 2022; Yamaguchi et al., 2020; Futoma et al., 2020). Another line of work combines deep learning with POMDP solvers, but without explicitly modeling the missingness process (Liu et al., 2022). More principled imputation strategies—such as Bayesian multiple imputation (Lizotte et al., 2008) and expectation-maximization (Yamaguchi et al., 2020)—estimate a distribution over missing values. In contrast to imputation, our approach directly learns the missingness function and provides PAC guarantees on the resulting policy. To our knowledge, no existing work bridges missingness and POMDPs to (1) learn the missingness function with statistical guarantees, and (2) leverage it to guarantee the optimality of the resulting policies.
2
Preliminaries
A probability distribution over a finite set X is a function P µ : X → [0, 1] with x∈X µ(x) = 1. The set of such distributions is ∆(X). Writing µ = {x1 7→ p1 , . . . , xk 7→ pk } indicates that µ(x1 ) = p1 and so on. The support of distribution µ ∈ ∆(X) is supp(µ) = {x ∈ X | µ(x) ̸= 0}. Sampling a random variable x from µ is denoted by x ∼ µ. Given σ : X → ∆(Y ), we let σ(y | x) := σ(x)(y). The indicator function 1φ returns 1 if predicate φ holds and 0 otherwise. Definition 1 (POMDPs). A partially observable Markov decision process is a tuple P = (S, A, T, b0 , ϱ, Z, O, γ) with finite factored state space S = ×i=1,...,n Si and the set of feature indices I = {1, . . . , n}, finite action space A, transition function T : S × A → ∆(S), initial state distribution b0 ∈ ∆(S), reward function ϱ : S × A → R, finite factored observation space Z = ×i=1,...m Zi , observation function O : S → ∆(Z), and discount factor γ ∈ [0, 1). The observation function is action-independent without loss of generality, as we may augment the state space to incorporate the last performed action (Chatterjee et al., 2016). A trajectory in a POMDP P is a sequence of states, observa tions, and actions. A history h = z (0) , a(0) , z (1) , a(1) , . . . ∈ H ⊆ (Z ×A)∗ is the observable fragment of a trajectory, i.e., a sequence of observations and actions. A history can be summarized by a sufficient statistic known as a belief b ∈ B ⊆ ∆(S), a probability distribution over underlying states induced by a history h ∈ H. The belief update τ : B × A × Z → B computes a successor belief b′ via Bayes’ rule (Spaan, 2012). A policy π : B → ∆(A) ∈ Π maps beliefs to probability distributions over actions. The objective is to find a policy π ∈ Π that maximizes its value, representing the infinitehorizon cumulative discounted reward: VP (π) = P∞expected π t (t) (t) E t=0 γ ϱ(s , a ) . As the decision problem of finding the optimal policy is undecidable in general (Madani et al., 2003), we focus on ε-optimal policies (Hauskrecht, 2000).
3
Missingness in MDPs
This section introduces missingness-MDPs, the different types of missingness functions and ways to visualize them. Definition 2 (Miss-MDP). A missingness-MDP is a tuple P = (S, A, T, b0 , ϱ, Z, M, γ), where S, A, T , b0 , ϱ, and γ are as in a POMDP, the finite observation space is Z = ×i∈I (Si ∪ {⊥}), with ⊥ denoting missing information, and function M : S → ∆(Z) is the missingness function such that ∀s ∈ S, ∀z ∈ supp(M (s)), ∀i ∈ I either zi = si or zi = ⊥. The state space S and observation space Z share the feature indices I, and we have that Z ⊋ S as some features can go missing in Z, being replaced by the symbol ⊥. This process of “poking holes” is governed by the stochastic missingness function M . While M may take actions into account, we use an action-independent M w.l.o.g (see Section 2). Missingness indicators. Missingness functions can equivalently be described as a map to vectors of missingness indicators (Mohan et al., 2013), i.e. M : S → ∆(R), where R = {0, 1}n . A vector r ∈ R has ri = 0 if feature i is missing (zi = ⊥), and otherwise ri = 1. The function fR : Z → R maps observations to their missingness indicators. Example 1. Let P be a miss-MDP with S = {x, y}2 , Z = {x, y, ⊥}2 , and missingness function M defined as: M ((s1 , s2 )) = {(s1 , s2 ) 7→ 0.5, (s1 , ⊥) 7→ 0.5}. We have fR ((y, x)) = (1, 1) and fR ((y, ⊥)) = (1, 0). Visiting state (y, x) yields either (y, x) or (y, ⊥), each with probability 0.5. Problem statement. We are given a miss-MDP P with an unknown missingness function M , a required precision ε > 0 and confidence threshold δ > 0, and a dataset D = (h1 , . . . , hk ) of k histories hi ∈ H collected from P under an unknown but fair policy πb (i.e. it has positive probability to visit all reachable states). The goal is to c ≈ M for (1) approximate the missingness function M all reachable states and (2) use it to compute a policy π ∗ ∈ Π such that with probability at least δ, we have supπ (VP (π)) − VP (π ∗ ) ≤ ε. The resulting policy π ∗ comes with a PAC guarantee (Valiant, 1984; Ashok et al., 2019): In finite time and with probability at least δ, we return a policy that is ε-optimal. Advantages of miss-MDPs over POMDPs. For computing ε-optimal policies in POMDPs, knowledge of the observation function is required. However, for arbitrary POMDPs, learning the observation function from a dataset of histories is impossible (Gilbert, 1959; Tune et al., 2013). In contrast, miss-MDPs exhibit structure in the missingness function M that, for certain types of missingness function, allows for learning M from histories (see also the paragraph “Missingness types in focus” in Section 4). Consequently, miss-MDPs are a proper and more feasible subclass of POMDPs.
3.1
Types of missingness functions
There are three major types of missingness functions (Rubin, 1976): missing completely at random (MCAR), missing at random (MAR) and missing not at random (MNAR). We define these in the context of miss-MDPs. This way, we
connect the theory of missing data to POMDPs, which allows us to identify cases in which M can be learned from histories. The simplest type is MCAR, where the probability of features going missing is independent of the feature values of the state. In the doctor-diagnosing example (Figure 1), the temperature feature may be missing due to a loosely attached thermometer. The miss-MDP in Example 1 is MCAR. Definition 3 (MCAR). The missingness function M : S → ∆(Z) of a miss-MDP P is MCAR if and only if ∀r ∈ R, ∃pr ∈ [0, 1], ∀s ∈ S, P (fR (z) = r | z ∼ M (s)) = pr . Admittability and Ialways . We introduce a notion of admittability that indicates whether an observation z could originate from a state s. We say that z is admittable by s, denoted z ⪯ s, if and only if ∀i ∈ I, zi = ⊥ or zi = si . In Example 1, we have (b, ⊥) ⪯ (b, a) and (b, a) ⪯ (b, a) but (a, ⊥) ⪯̸ (b, a). Further, Ialways = {i ∈ I | ∀s′ ∈ S : P(z i = ⊥ | z ∼ M (s′ )) = 0} ⊆ I is the set of indices of always observed features, and Imis = I \ Ialways is its complement. Missingness probabilities in MAR depend only on observed state features – in the example of Figure 1, the observed temperature influences the missingness of the heart rate feature. We distinguish two MAR variants: a restricted one we call simple MAR (Mohan and Pearl, 2021), and the general one (Rubin, 1976). For simple MAR, a missingness probability is only influenced by the observable features that never go missing, i.e., by zi for i ∈ Ialways . For MAR, a missingness probability is only influenced by the non-missing features of a given observation, including features that may go missing. Any MCAR missingness function is also (simple) MAR. Definition 4 ((Simple) MAR). The missingness function M : S → ∆(Z) of a miss-MDP P is: • Simple MAR iff for all s, s′ ∈ S that agree on always-observed features (i.e. ∀i ∈ Ialways , si = s′i ), the missingness probability is the same for all missingness indicators r ∈ R, formally: P(fR (z) = r | z ∼ M (s)) =P(fR (z ′ ) = r | z ′ ∼ M (s′ )). • MAR iff for all s, s′ ∈ S and z ∈ Z, if z ⪯ s, s′ , the probability of its indicator r := fR (z) is equal for s and s′ : P(fR (z ′ ) = r | z ′ ∼ M (s))= P(fR (z ′′ ) = r | z ′′ ∼ M (s′ )). Example 2. We redefine M in the miss-MDP from Example 1 to be simple MAR: M ((s1 , x)) = {(s1 , x) 7→ 1}, and M ((s1 , y)) = {(s1 , y) 7→ 0.5, (⊥, y) 7→ 0.5}. Here, the missingness probability of feature 1 depends on the always observed value of feature 2. As an example of MAR, which is not simple MAR, consider: M ((s1 , x)) = {(s1 , x) 7→ 0.5, (⊥, ⊥) 7→ 0.5}, and M ((s1 , y)) = {(s1 , y) 7→ 0.25, (⊥, y) 7→ 0.25, (⊥, ⊥) 7→ 0.5}. Here, feature 2 may go missing as well. The missingness probability of feature 1 depends on the value of feature 2, only when it is observed! Definition 5 (MNAR). The missingness function M of a miss-MDP P is MNAR if and only if it is not MAR. For MNAR, missingness probabilities may depend on the values of missing features – e.g., in Figure 1 the temperature feature influences its own missingness. In particular, in self-censoring missingness functions, a feature’s missingness probability depends on its own value.
MCAR
Feature
S1
Mis. Indicator Observation
S2
R1
Z1
(simple) MAR S1
R2
Z2
S2
S1
R1
Z1
S2
R1
Z2
solved using any off-the-shelf POMDP solver. Recall that in general, it’s impossible to approximate unknown observation functions in POMDPs. Thus, we identify miss-MDPs where approximating M with guarantees is possible.
MNAR
Z1
R2
Z2
Figure 2: Example missingness graphs visualizing relations between miss-MDP elements for the three types of missingness functions.
Example 3. We adapt Example 1 to make M MNAR and self-censoring for feature 2: M ((s1 , x)) = {(s1 , x) 7→ 0.5, (s1 , ⊥) 7→ 0.5} and M ((s1 , y)) = {(s1 , y) 7→ 0.1, (s1 , ⊥) 7→ 0.9}.
3.2
Missingness graphs
Missingness graphs (m-graphs) visualize the dependencies of missingness functions. We adopt the definition from Mohan and Pearl (2021) for our miss-MDP framework. An m-graph is a causal diagram (Pearl, 1995) in the form of a directed acyclic graph. Its vertices correspond to variables, and the edges correspond to the relationships between the variables. Vertices are grouped into three categories: S -nodes represent features of the state space, Z -nodes represent the observation features, and R -nodes represent the missingness indicators.1 We omit the R -nodes for always observed features. Arrows between nodes represent a causal relationship: The parent node is a direct cause of the child node. The absence of an edge intuitively indicates that two variables do not directly influence each other; formally, it means they are conditionally independent, given other variables in the graph, according to the d-separation criteria (Pearl, 2009). Visualizing types of missingness. Figure 2 uses m-graphs to illustrate the conditional independence assumptions of different types of missingness functions. For MCAR, both R -nodes are purely stochastic, having no incoming arrows and thus not depending on any feature value. For (simple) MAR, there are two changes: Feature S2 is always observable (R2 is absent), and it affects missingness indicator R1 (red arrow). For MNAR, S2 can go missing, so R1 depends on information that can go missing. Note that m-graphs cannot represent context-specific independence assumptions, which are needed to, e.g., represent non-simple MAR functions such as the one in Example 2; but the missingness functions we focus on may all be represented by m-graphs. We provide the corresponding m-graphs for all experiments in Section D.
4
Approximating missingness-MDPs
Missingness types in focus. A necessary condition is that the missingness function can be approximated solely from observations, a property that missing data literature calls identifiability (Bhattacharya et al., 2020). Establishing new identifiability results is not the focus of this paper. Instead, we provide PAC guarantees for types that are known to be identifiable. Thus, we focus on missingness functions of type (1) MCAR, (2) simple MAR and (3) non-self-censoring MNAR with independent missingness indicators. Additionally, in Section 5, we experiment on non-identifiable MNAR. Outline. Remark 1 presents an interesting insight orthogonal to our problem: For maintaining a belief during policy execution, certain types of missingness can in fact be ignored. Sections 4.1 and 4.2 describe our algorithms for approximating missingness functions. Both are structured as follows: c, prove that They state assumptions, define how to compute M the approximation is probably approximately correct, and explain how to utilize additional knowledge on the missingness function to reduce sample complexity. Section 4.3 uses these algorithms to compute near-optimal policies. Remark 1 (Ignorability). Missing data literature defines ignorability as cases where any quantity of interest can be consistently estimated from observations alone, and it is not necessary to model the missingness process (Little and Rubin, 2019). This holds under MCAR, and also under MAR whenever the quantity depends only on the observed features. We identify a similar notion of ignorability for miss-MDPs: If the missingness function M is MAR (including MCAR), then belief updates τ can be computed without knowledge of the precise probabilities of M , since these cancel out in Bayes’ rule; see Section B for a formal proof. Thus, MAR missingness is ignorable for maintaining a belief when executing a policy in a miss-MDP. However, we stress that the missingness function is required to compute belief-based policies, since the probabilities P(b′ | b, a) of successor beliefs b′ depend on it. Occurrence counts. Both algorithms extract the number of occurrences of every observation using the dataset D = (h1 , . . . , hk ) of k histories hi ∈ H. For each hi = z (0) , a(0) , . . . , z (l) , a(l) , we denote the j-th observa(j) tion z (j) by hi . The number of occurrences of an observation Pk P|hi | z ∈ Z is: #D (z) = i=1 j=0 1h(j) =z . For a set Z ′ ⊆ Z, i P we define #D Z ′ = z∈Z ′ #D (z).
4.1 Approximating M for MCAR and simple MAR
Our goal is to compute ε-optimal policies for miss-MDPs with an unknown M . For this, we first compute an approximation c ≈ M from the given dataset D of histories. This yields an M approximated, but fully specified miss-MDP Pb, which can be
If a missingness function is of type simple MAR, we can approximate it using the approximation for simple MAR algorithm, AsMAR. The modifications to obtain the algorithm for the more restricted MCAR-type functions, AMCAR, are described at the end of the section.
1 We exclude the category of unobserved features U used in Mohan and Pearl (2021), as in our setting U = ∅, since M depends on states.
Always-observable features. Based on the dataset D, we partition the feature indices I into those that
are always observed and those that can go missing: Iˆalways = {i ∈ I | #D ({z ∈ Z | zi = ⊥}) = 0} and Iˆmis = I \ Iˆalways , respectively. Note, this partitioning is based on empirical data (Iˆalways ≈ Ialways ) and we might misclassify a feature index to be in Iˆalways even though it can go missing. c. We use the fact that M can be seen as a Computing M mapping S → ∆(R) (see paragraph “Missingness indicators”, Section 3). Consequently, for every state, we want to approximate the probability of a certain vector of missingness indicators. The simple MAR assumption tells us that the probabilities can only depend on the features in Iˆalways , meaning that M (z | s) = M (z | s′ ) when si = s′i for i ∈ Ialways . Thus, for all possible values of the always-observable features of a state s ∈ S and missingness indicator vector r ∈ R, we can r compute n the occurrence count #D (s, r) = #D (Zs ) , where Zsr = z ∈ Z | ∀i ∈ I : (i ∈ Iˆalways =⇒ zi = si ) and o c(z | s) (ri = 0 =⇒ zi = ⊥) . Using #D (s, r), we obtain M
as the fraction of observing (s, fR (z)) and the sum of counts for s and all possible missingness indicators values: #D (s, fR (z)) c(z | s) = P M . r∈R #D (s, r)
(1)
Probably approximately correct. With enough data, our approach yields an arbitrarily precise approximation of the true missingness function. We formalize this in Theorem 1 as a PAC guarantee, not only proving that it becomes ε-precise for every ε > 0, but that we can also bound the probability of an error (through unlucky sampling). Additionally, we can c adapt the claim to bound the imprecision of the resulting M for a given dataset. The proof is provided in Section C.2. Theorem 1 (PAC guarantee for AsMAR). Let P be a missingness-MDP with a simple MAR missingness function. For every precision ε and confidence threshold δ, there exists a number n∗ , such that every dataset D of n∗ histories satisfies c computed on the following: With probability at least δ, for M D according to Equation (1), for all reachable states s ∈ S c(z | s) − M (z | s)| ≤ ε. and observations z ∈ Z, we have |M Dually, for a dataset D and confidence threshold δ, there exists an ε such that with probability at least δ, for all reachable states s ∈ S and observations z ∈ Z, we have the same inequality, c(z | s) − M (z | s)| ≤ ε. i.e. |M Using additional assumptions on the missingness function. Beyond the necessary simple MAR assumption, we can exploit additional assumptions to improve the approximation of M for the same D. Consider a feature i that is always observable, but does not affect the missingness probability of other features. We can exclude such i from Iˆalways , combining the occurrence counts of states that differ only in this feature. Hence, if we assume M to be MCAR, Iˆalways reduces to an empty set. Consequently, we get that #D (s, r) is independent of s, and we effectively only count occurrences of missingness indicators, resulting in the algorithm AMCAR. We prove the correctness of these improvements in Section C.2. In Section 5, we empirically show the improved precision of c estimated from the same D with this approach. M
4.2
Approximating M with independent missingness indicators
This section presents the approximation for independent missingness indicators algorithm, AIMI. It may be applied to M of types MCAR, simple MAR as well as a subset of identifiable MNAR which satisfy the following requirements: 1. Independence of missingness indicators: The fact that one feature is missing must not influence the missingnessprobability of any other feature. Formally, for s ∈ S and z ∈ Z, P(z | z ∼ M (s)) = Πi∈I P(z i | z ∼ M (s)). 2. No self-censoring: Intuitively, a feature may not influence its own missingness probabilities. Formally, for all i ∈ I and every pair of states s, s′ ∈ S that differ only in the i-th feature (si ̸= s′i , but for all j ̸= i we have sj = s′j ) we have P(z i = ⊥ | z ∼ M (s)) = P(z i = ⊥ | z ∼ M (s′ )). 3. Positivity: Intuitively, if a feature affects the missingness probabilities of other features, we need to observe its value to learn the missingness probabilities. However, this is impossible if it always misses. Therefore, we require a positivity assumption (Hernán and Robins, 2020): For all i ∈ I and s ∈ S, we have P(z i ̸= ⊥ | z ∼ M (s)) > 0. c. We compute the occurrence count for evComputing M ery state s ∈ S, feature i ∈ I and value of a corresponding i-th missingness indicator n ri ∈ {0, 1} as #D (s, i, ri ) = i,ri i,ri #D (Zs ), where Zs = z ∈ Z | ∀j ∈ I \ {i} : (zj = o sj ) and (ri = 0 ⇐⇒ zi = ⊥) . By positivity, a large enough dataset almost surely contains observations to make the counters non-zero (i.e. for all s and i, we have #(s, i, 0) + #(s, i, 1) > 0). The probability of a non self-censoring feature i depends only on the other features j ∈ I \ {i}. Finally, using the independence assumption, we c by taking the product of the individual missingcan infer M ness probabilities of all features. c(z | s) = M
Y i∈I
#D (s, i, fR (z)i ) . #D (s, i, 0) + #D (s, i, 1)
(2)
Probably approximately correct. In Section C.3, we prove Theorem 2 that provides the same kind of guarantee as in Theorem 1; the only difference are the assumptions on the c. missingness function and the approach for calculating M Theorem 2 (PAC guarantee for AIMI). Let P be a missMDP where the missingness function satisfies independence, c computed using non-self-censoring, and positivity. Then, M Equation (2) offers the same PAC guarantees as in Theorem 1. Using additional assumptions on the missingness function. In general, AIMI maintains a counter for every combination of the feature valuations of other features j ∈ I \ {i}. If we know that a certain feature j does not affect the missingness probability of i – there is no edge between the j-th S -node and the i-th R -node – we merge the counters for all values of the j-th feature. This knowledge comes from (a) an m-graph, (b) assuming simple MAR while observing feature j goes
ICU, simple MAR
ICU, MNAR (id.)
ICU, MNAR (unid.) Algorithms AMCAR AsMAR AIMI
105
103
107 101
105
103
107 101
105
103
107
0.9
Metrics ATV WTV Value
Optimal
0.8
*
0.7 0.6
1.0 0.8 0.6 0.4 0.2 0.0 101 1.0
| |
| |
| |
Predator, MCAR
Predator, simple MAR
simple MAR 1
102
103
104
105
101 1.0
105
103
107
0.5
0.8
Normalized Value
Total Variation Normalized Value
Total Variation Normalized Value
1.0 0.8 0.6 0.4 0.2 0.0 101 1.0
1 0
Model-based
0
5
1
10
2
15
| |
0.5
| |
prior
Model-free
0.0
0.6
AMCAR AsMAR AIMI * (optimal)
ICU
Predator
POMCP PPO+Memory PPO rand
c and resulting Figure 3: Left (and top): Empirical results for the ICU and Predator benchmarks, with average/worst TV (ATV/WTV) of M policy values VP (π). Values are normalized so that 1 corresponds to the optimal policy π ∗ using the true M and 0 to the prior policy π prior . Bottom right: Comparison of normalized values on ICUsMAR and PredatorsMAR between model-based and the model-free baseline methods.
missing in D, or (c) assuming MCAR, in which case we drop the dependency on s in the counters. We prove in Section C.3 that all these modifications retain the PAC guarantees.
4.3
Computing a policy with the approximations
Here, we provide the final step of our problem statement: computing a PAC policy from the approximated miss-MDP. c We show in Section C.4 that after finitely many samples, M is accurate enough to yield an ε-optimal policy. We highlight c to precision ε is insufficient, as the errors in that learning M c M aggregate when solving the miss-MDP. Theorem 3 (Computing ε-optimal Policies). Let P be a missMDP with a missingness function that is simple MAR or that satisfies independence, no self-censoring, and positivity. Assume we can sample histories collected under a fair policy, and we know a lower bound on the smallest missingness probability p ≤ mins∈S,z∈Z M (z | s). Then, for every given precision ε and confidence threshold δ, we can in finite time compute a policy π ∗ such that with probability at least δ it is ε-optimal, i.e. (supπ VP (π)) − VP (π ∗ ) ≤ ε. Practical considerations. Theorem 3 concern asymptotic convergence to an ε-optimal policy, providing the theoretical
foundation of our approach. In practice, the required number of samples is very large, and we work with datasets that are not necessarily sufficient to provide the ε-optimality guarantees. Datasets of limited size may cause a practical problem: For an observation z with #D (s, fR (z)) = 0, for any s ∈ S we c(z | s) = 0, leading to a division by zero for s obtain M when performing the belief update τ . We circumvent this case by setting #D,κ (s, r) = #D (s, r) + κ, i.e. we add a small κ > 0 to every count. The influence of κ diminishes with an increasing dataset size |D|.
5
Experiments
We conduct an experimental evaluation to test our theoretical results and to compare our methods against several baselines. We aim to answer the following questions: Q1. Do our proposed learning algorithms adequately approximate the missingness function? Q2. How do (in)correct assumptions on the missingness function affect the approximation?
Q3. With increasing dataset size, does the value of the policy computed on the approximated miss-MDP converge to that of the optimal policy on the true miss-MDP? Q4. How does the value computed from the approximated miss-MDP compare against model-free baselines? Below, we first describe the experimental setup. Then, we analyze the results in the order of the above questions. Benchmarks. We consider two environments with varying missingness types: ICU models a doctor treating a patient, whose vital measurements are not always available (Johnson et al., 2022), and Predator, a variant of the Tag environment (Pineau et al., 2003), where a predator chases a partially hidden prey. For our benchmarks, we consider the following four missingness types: (1) MCAR, (2) sMAR, a simple MAR function, (3) MNAR (id.), an identifiable MNAR function (fulfilling the required assumptions of AIMI), and (4) MNAR (unid.), an unidentifiable MNAR function with selfcensoring. For Predator and all missingness functions, the (x, y)-coordinates of the prey always go missing jointly, i.e. the missingness indicators are dependent; for ICU, the missingness indicators are independent. As mentioned in Section D, ICU has 800 reachable states and Predator up to 1311. Setup. For a range of dataset sizes |D|, we collect data using the uniform random policy π rand with c≈ ∀a ∈ A, π rand (a | ·) = 1/|A|, and compute the estimate M M using our proposed algorithms: AMCAR, AsMAR, and c yields an approximated miss-MDP AIMI (Section 4). Each M b, for which we compute a policy π̂ using the POMDP solver P SARSOP (Kurniawati et al., 2008). We consider the following baselines: (1) optimal: the SARSOP policy π ∗ computed for the true M (the upper bound); (2) prior: the SARSOP policy π prior with an uninformed prior of M , where each feature independently goes missing with probability 0.5; (3) POMCP (Silver and Veness, 2010): generating an online POMDP planning policy π POMCP ; (4) PPO (Schulman et al., 2017): the policies π PPO+Memory and π PPO , with and without memory. We group π PPO and π POMCP as model-free baselines as they rely solely on simulation access to the miss-MDP. We provide more extensive details of the setup in Section D. Moreover, we publicly provide the code of our implementation2 . For further details on reproducibility, see Section A. Metrics. For every dataset size and method, we perform 20 independent runs and report the average together with the interquartile range (shaded area) of the following metrics: 1. To empirically assess the quality of the approximation c compared to the true M , we compute the total variaM tion (TV) of the distributions at a state s ∈ S as T V (s) = P 1 c the TV z⪯s M (z | s) − M (z | s) . We aggregate 2 P 1 across states by the average TV (ATV): /|S| s T V (s), and the worst TV (WTV): maxs T V (s). 2. We asses how the various π̂ from the algorithms perform on the true miss-MDP P by comparing their value VP (π̂) to VP (π prior ) and the optimum VP (π ∗ ). All policy values are normalized s.t. 1 and 0 correspond to the values of the optimum and prior baselines, respectively. 2
https://github.com/ai-fm/missingness-pomdps
Results. The experimental results in Figure 3 (left, top) present how the TV of the approximated missingness function c and the value of the associated policy π̂ evolve with dataset M size |D|. Figure 3 (right) compares our algorithms to several baselines for selected benchmarks. We report the best baseline performance across multiple seeds. We provide baseline results for all benchmarks as well as results for an additional PredatorMNAR (unid.) benchmark in Section D. Q1: With sufficient data, our algorithms adequately approximate the missingness function. Under the appropriate missingness assumptions, each algorithm learns the missingness function (bringing the TV near zero): AMCAR learns the exact missingness function in PredatorMCAR within 100 observations. We observe similar results for AsMAR in ICUsMAR and PredatorsMAR , and for AIMI in ICUMNAR (id.) . Q2: The assumptions on the missingness function significantly affect the quality of the approximation. Under correct assumptions on the missingness function, the TVs of c approach zero (e.g. AIMI on ICUsMAR the approximated M and ICUMNAR (id.) ). Further, relaxations on the missingness (e.g. assuming MAR despite MCAR missingness) allows the approximation of M , but may lead to significant data inefficiency (see AMCAR vs. AsMAR on PredatorMCAR ). Breaking the missingness assumptions results in converging to a poor WTV (see AIMI on all Predator benchmarks). Q3: Convergence to the optimal policy follows the quality of the approximation. With a sufficiently accurate approximation of the missingness function, the values of our method’s policies converge to the optimal policy’s π ∗ values (e.g. AIMI on ICUsMAR and ICUMNAR (id.) , AMCAR and AsMAR on PredatorMCAR , AsMAR on PredatorsMAR ). Despite the missingness of ICUMNAR (unid.) not adhering to the necessary assumptions, AIMI approximates the relevant parts of M well enough to yield a policy that is considerably close to π ∗ . Q4: Baseline methods, including PPO and POMCP, are not competitive. Figure 3 (right) compares our algorithms to several baselines. Our algorithms, under correct missingness assumptions (see AsMAR or AIMI for ICU, or AsMAR for Predator), consistently outperform policies derived from an uninformed prior over the missingness function (π prior ). Meanwhile, all model-free approaches—π PPO , π PPO+Memory , and π POMCP —significantly underperformed on both benchmarks. We attribute this gap to two factors. First, model-free methods solely access the transition function through simulation. Second, in a separate experiment without missingness, these methods successfully learned the optimal policy for the fully observable MDP. This indicates that the poor performance stems from these methods’ inability to effectively handle the specific type of partial observability of miss-MDPs. We attribute the better performance (compared to the random policy π rand ) of the model-free approaches in Predator, in contrast to ICU, to the lower stochasticity of the underlying transition function of Predator.
6
Conclusion
Miss-MDPs integrate the theory of missing data with decisionmaking under uncertainty. From data generated by a missMDP with known underlying MDP, we approximate the unknown missingness function, which – under assumptions about its type – enables the computation of ε-optimal policies. We show that incorrect assumptions about the missingness type may lead to misspecified models and suboptimal policies. Our experiments support the theory and demonstrate the practical benefits of our approach, highlighting the superiority over model-free baselines in our problem setting. Future work may lift the assumption of a known transition function and extend miss-MDPs to the more general setting of miss-POMDPs.
Acknowledgements This work was supported by the European Research Council (ERC) Starting Grant 101077178 (DEUCE), and the Czech Science Foundation grant GA23-06963S (VESCAA).
References Elizabeth S Allman, Catherine Matias, and John A Rhodes. Identifiability of parameters in latent structure models with many observed variables. Ann. Statist., 37(6A):3099–3132, 2009. Pranav Ashok, Jan Kretı́nský, and Maximilian Weininger. PAC statistical model checking for markov decision processes and stochastic games. In CAV (1), volume 11561 of Lecture Notes in Computer Science, pages 497–519. Springer, 2019. Karl Johan Åström. Optimal control of Markov processes with incomplete state information. J. Math. Anal. Appl., 10(1):174–205, 1965. Jacob Bernoulli. Ars conjectandi, opus posthumum. Accedit Tractatus de seriebus infinitis, et epistola galliceé scripta de ludo pilae reticularis. Impensis Thurnisiorum, fratrum, 1713. Rohit Bhattacharya, Razieh Nabi, Ilya Shpitser, and James M. Robins. Identification In Missing Data Models Represented By Directed Acyclic Graphs. In UAI, volume 115 of Proceedings of Machine Learning Research, pages 1149–1158, 2020. Carlos E. Budde, Arnd Hartmanns, Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft. Sound statistical model checking for probabilities and expected rewards. In TACAS (1), volume 15696, pages 167–190. Springer, 2025. Stef van Buuren. Flexible imputation of missing data. CRC Press, Taylor and Francis Group, 2018. Markus Böck, Julien Malle, Daniel Pasterk, Hrvoje Kukina, Ramin Hasani, and Clemens Heitzinger. Superhuman performance on sepsis MIMIC-III data by distributional reinforcement learning. PLOS ONE, 17(11):e0275358, November 2022. Krishnendu Chatterjee, Martin Chmelı́k, Raghav Gupta, and Ayush Kanodia. Optimal cost almost-sure reachability in POMDPs. Artificial Intelligence, 234:26–48, 2016.
Minshuo Chen, Yu Bai, H. Vincent Poor, and Mengdi Wang. Efficient RL with impaired observability: Learning to act with delayed and missing state observations. In NeurIPS, 2023. Przemyslaw Daca, Thomas A. Henzinger, Jan Kretı́nský, and Tatjana Petrov. Faster statistical model checking for unbounded temporal properties. ACM Trans. Comput. Log., 18(2):12:1–12:25, 2017. Frederik Michel Dekking, Cornelis Kraaikamp, Hendrik Paul Lopuhaä, and Ludolf Erwin Meester. A Modern Introduction to Probability and Statistics: Understanding why and how. Springer Science & Business Media, 2005. Lorenzo Finesso. Consistent estimation of the order for Markov and hidden Markov chains. University of Maryland, College Park, 1990. Joseph Futoma, Michael C. Hughes, and Finale Doshi-Velez. POPCORN: Partially Observed Prediction COnstrained ReiNforcement Learning, March 2020. Edgar J Gilbert. On the identifiability problem for functions of finite Markov chains. Sandia Corporation, 1959. Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without computationally intractable oracles. Advances in neural information processing systems, 35:1458–1473, 2022. Milos Hauskrecht. Value-function approximations for partially observable Markov decision processes. JAIR, 13:33–94, 2000. Miguel A Hernán and James M Robins. Causal Inference: What If. CRC Press, 2020. Stephanie L. Hyland, Martin Faltys, Matthias Hüser, Xinrui Lyu, Thomas Gumbsch, Cristóbal Esteban, Christian Bock, Max Horn, Michael Moor, Bastian Rieck, Marc Zimmermann, Dean Bodenham, Karsten Borgwardt, Gunnar Rätsch, and Tobias M. Merz. Early prediction of circulatory failure in the intensive care unit using machine learning. Nature Medicine, 26(3):364–373, 2020. Alistair Johnson, Lucas Bulgarelli, Tom Pollard, Steven Horng, Leo Anthony Celi, and Roger Mark. MIMIC-IV, 2022. Matthieu Komorowski, Leo A. Celi, Omar Badawi, Anthony C. Gordon, and A. Aldo Faisal. The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care. Nature Medicine, 24:1716–1720, 2018. Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In NIPS, pages 1840–1848, 2016. Hanna Kurniawati, David Hsu, and Wee Sun Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In RSS. MIT Press, 2008. Roderick Little and Donald Rubin. Statistical Analysis with Missing Data, Third Edition. Wiley Series in Probability and Statistics. Wiley, 2019. Zeyu Liu, Anahita Khojandi, Xueping Li, Akram Mohammed, Robert L Davis, and Rishikesan Kamaleswaran. A Machine Learning–Enabled Partially Observable Markov Decision
Process Framework for Early Sepsis Prediction. INFORMS Journal on Computing, 34(4):2039–2057, July 2022. Daniel J Lizotte, Lacey Gunter, Eric Laber, and Susan A Murphy. Missing data and uncertainty in batch reinforcement learning. In NeurIPS, 2008. Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell., 147(1-2):5–34, 2003. Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft. Solving robust markov decision processes: Generic, reliable, efficient. CoRR, abs/2412.10185, 2024. Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft. Solving robust markov decision processes: Generic, reliable, efficient. In AAAI, volume 39, pages 26631–26641. AAAI Press, 2025. Karthika Mohan and Judea Pearl. Graphical models for processing missing data. J. Am. Stat. Assoc., 116(534):1023– 1037, 2021. Karthika Mohan, Judea Pearl, and Jin Tian. Graphical models for inference with missing data. NeurIPS, 26, 2013. Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov models. In STOC, pages 366–375. ACM, 2005. Razieh Nabi, Rohit Bhattacharya, and Ilya Shpitser. Full law identification in graphical models of missing data: Completeness results. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 7153–7163. PMLR, 2020. Masashi Okamoto. Some inequalities relating to the partial sum of binomial probabilities. Annals of the Institute of Statistical Mathematics, 10(1):29–35, 1959. Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–688, 1995. Judea Pearl. Causality. Cambridge University Press, 2nd edition, 2009. Joelle Pineau, Geoffrey J. Gordon, and Sebastian Thrun. Pointbased value iteration: An anytime algorithm for POMDPs. In IJCAI, pages 1025–1032, 2003. Tom J. Pollard, Alistair E. W. Johnson, Jesse D. Raffa, Leo A. Celi, Roger G. Mark, and Omar Badawi. The eicu collaborative research database, a freely available multicenter database for critical care research. Scientific Data, 5(1):180178, 2018. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994. Donald B. Rubin. Inference and missing data. Biometrika, 63(3):581–592, 1976. Stuart J. Russell and Peter Norvig. Artificial Intelligence: a modern approach. Fourth Edition. Pearson Education Limited, 2022. Joseph L. Schafer and John W. Graham. Missing data: our view of the state of the art. Psychological Methods, 7(2):147–177, June 2002.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017. Hajin Shim, Sung Ju Hwang, and Eunho Yang. Joint active feature acquisition and classification with variable-size set encoding. In NeurIPS, pages 1375–1385, 2018. Ilya Shpitser, Karthika Mohan, and Judea Pearl. Missing Data as a Causal and Probabilistic Problem. In UAI, pages 802–811, 2015. David Silver and Joel Veness. Monte-carlo planning in large pomdps. In NIPS, pages 2164–2172. Curran Associates, Inc., 2010. Matthijs T J Spaan. Partially Observable Markov Decision Processes. In Marco Wiering and Martijn van Otterlo, editors, Reinforcement Learning: State-of-the-Art, pages 387–414. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Sebastiaan Terwijn. On the learnability of hidden markov models. In ICGI, volume 2484 of Lecture Notes in Computer Science, pages 261–268. Springer, 2002. Patrick J. Thoral, Jan M. Peppink, Ronald H. Driessen, Eric J. G. Sijbrands, Erwin J. O. Kompanje, Lewis Kaplan, Heatherlee Bailey, Jozef Kesecioglu, Maurizio Cecconi, Matthew Churpek, Gilles Clermont, Mihaela van der Schaar, Ari Ercole, Armand R. J. Girbes, and Paul W. G. Elbers. Sharing ICU Patient Data Responsibly Under the Society of Critical Care Medicine/European Society of Intensive Care Medicine Joint Data Science Collaboration: The Amsterdam University Medical Centers Database (AmsterdamUMCdb) Example*. Critical Care Medicine, 49(6), 2021. Anastasios A Tsiatis. Semiparametric Theory and Missing Data. Springer Series in Statistics. Springer, 2006. Paul Tune, Hung X Nguyen, and Matthew Roughan. Hidden markov model identifiability via tensors. In 2013 IEEE International Symposium on Information Theory, pages 2299–2303. IEEE, 2013. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. Yuhui Wang, Hao He, and Xiaoyang Tan. Robust reinforcement learning in POMDPs with incomplete and noisy observations. CoRR, abs/1902.05795, 2019. Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. Production and Operations Management, 31(9):3491–3504, 2022. Nobuhiko Yamaguchi, Osamu Fukuda, and Hiroshi Okumura. Model-based reinforcement learning with missing data. In CANDAR (Workshops), pages 168–171, 2020. Jinsung Yoon, James Jordon, and Mihaela van der Schaar. ASAC: active sensing using actor-critic models. In MLHC, volume 106 of Proceedings of Machine Learning Research, pages 451–473. PMLR, 2019.
A
Reproducibility
All code required for conducting experiments is included in an anonymized repository at https://anonymous.4open.science/r/
missingness-pomdps. The range of values tried per hyperparameter during development of the paper are shown in Table 1, and the final values were chosen based on best cumulative reward obtained. The final hyperparameters used for each model and algorithm are provided in the repository (see our README.md). The computing infrastructure in which the experiments have been carried out is described in Section D.2.
B
Proofs for Section 3: ignorability
Lemma 1. If a missingness function M is MAR, then ∀z ∈ Z, ∃p ∈ [0, 1], ∀s ∈ S, M (z | s) = 1z⪯s · p. Proof. Suppose that M is MAR. The lemma states that ∀z ∈ Z, ∃p ∈ [0, 1], ∀s ∈ S, M (z | s) = p if z ⪯ s and otherwise M (z | s) = 0. Since z ̸⪯ s implies that M (z | s) = 0, we only need to show that ∀z ∈ Z, ∃p ∈ [0, 1], ∀s ∈ S, z ⪯ s ⇒ M (z|s) = p, which directly follows from the MAR assumption.
Remark 2. Lemma 1 implies that the missingness function can be omitted in the belief update. Let b ∈ B be a belief, and let s′ ∈ S. Then, for any a ∈ A and z ∈ Z, it holds that b′ (s′ ) = τ (b, a, z)(s′ ) P M (z | s′ ) s∈S T (s′ | s, a)b(s) P P := ′′ ′′ s′′ ∈S M (z | s ) s∈S T (s | s, a)b(s) (By definition of belief update) P 1z⪯s′ · p s∈S T (s′ | s, a)b(s) P =P ′′ ′′ s′′ ∈S 1z⪯s · p s∈S T (s | s, a)b(s) (By Lemma 1) P 1z⪯s′ s∈S T (s′ | s, a)b(s) P . =P ′′ ′′ s′′ ∈S 1z⪯s s∈S T (s | s, a)b(s) (p cancels out) Therefore, the probabilities of M do not affect the resulting probabilities of the belief update. In particular, this means that maintaining a belief while executing a miss-MDP does not require knowledge of M . Still, we stress again that one needs M to compute an optimal policy because this requires constructing and solving the belief MDP (see (Russell and Norvig, 2022, Chapter 16.4.1)), which in turn requires knowing the probability P(b′ | b, a) of going to a successor belief b′ from a current belief b ∈ B upon playing action a ∈ A. Concretely, the probability of a successor belief b′ = τ (b, a, z) depends on the probability of z ∈ Z given b and a, which in turn depends on M , X P(b′ | b, a) = P(z | b, a)1b′ =τ (b,a,z) , z∈Z
P(z | b, a) =
X s∈S
b(s)
X
T (s′ | s, a)M (z | s′ ).
s′ ∈S
Here, no normalization occurs, and the probabilities of M do not cancel out.
C
Proofs for Section 4: probably approximately correct
This appendix is about proving that given enough data, we can approximate the missingness function to arbitrary precision ε, or the other way round: we can prove a certain precision ε for any given dataset D. In both directions, we provide a probabilistic guarantee, i.e. that the result is correct with probability at least δ. The reason the guarantee has to be probabilistic is that our knowledge relies on a sampled dataset, and, intuitively, there always is a chance that we were “unlucky” and received a very unlikely sequence of samples from which we infer a wrong approximation. Outline. First, in Section C.1 we recall standard notions from statistics literature: Bernoulli processes and the fact that building on Okamoto’s inequality, we can obtain a size for our dataset D given precision ε and confidence δ (or, analogously, obtain a precision ε given D and δ). Afterwards, Section C.2 and Section C.3 provide the proofs of Theorems 1 and 2, respectively, i.e. the guarantees for our algorithms. Moreover, they prove the guarantees for the modified algorithms when using more information about the missingness function. Finally, Section C.4 proves Theorem 3, our main result that ε-policies can be computed.
C.1
Bernoulli processes
Definition 6 (Bernoulli process Bernoulli (1713), (Dekking et al., 2005, Chapter 4.3)). A Bernoulli process is a sequence of binary random variables that are independent and identically distributed. All random variables have probability p to yield a 1, and probability 1 − p to yield a 0. Throughout this appendix, we write n for the length of the sequence of a Bernoulli process, and k for the number of successes, i.e. the number of times it yielded a 1. Moreover, we denote by p̂ = nk the empirical success probability. Okamoto’s seminal work proves the following property of estimating p through observing a Bernoulli process: Theorem 4 (Okamoto’s inequality (Okamoto, 1959, Theorem 1)). For a Bernoulli process with n repetitions and k successes and a given precision ε, we have 2
2
Pr(p̂ − p ≥ ε) ≤ e−2·n·ε and Pr(p − p̂ ≥ ε) ≤ e−2·n·ε . 2
Combining these, we get that Pr(|p̂−p| ≥ ε) ≤ 2·e−2·n·ε , in words: The probability of the estimate p̂ being more than ε 2 away from the true probability p is less than 2 · e−2·n·ε . For our guarantees, we want to be ε-precise with probability at least δ, so the probability of error should be upper bounded by 2 1 − δ.3 Thus, we require 2 · e−2·n·ε ≤ 1 − δ. Then, we can solve the inequality for ε or n: s 2 2 ln( 1−δ ) ln( 1−δ ) 2 2 · e−2·n·ε ≤ 1 − δ ⇔ ε ≥ ⇔ n≥ . 2 2·n 2·ε (3) 3
Note that in this paper, we use δ as the probability of the estimate being correct, unlike e.g. Budde et al. (2025), where δ is the probability of an error.
In other words, given two of precision ε, confidence δ, and number of repetitions n, we can infer the third. We remark that there exist other inequalities similar to Okamoto’s that yield the same result, but with tighter bounds; we refer to (Budde et al., 2025, Section 3) for a discussion. However, as our goal is only to prove the existence of a bound, we choose the conservative Okamoto bound for its easier accessibility.
C.2
PAC guarantees for AsMAR
Theorem 1 (PAC guarantee for AsMAR). Let P be a missingness-MDP with a simple MAR missingness function. For every precision ε and confidence threshold δ, there exists a number n∗ , such that every dataset D of n∗ histories satisfies c computed on the following: With probability at least δ, for M D according to Equation (1), for all reachable states s ∈ S c(z | s) − M (z | s)| ≤ ε. and observations z ∈ Z, we have |M Dually, for a dataset D and confidence threshold δ, there exists an ε such that with probability at least δ, for all reachable states s ∈ S and observations z ∈ Z, we have the same inequality, c(z | s) − M (z | s)| ≤ ε. i.e. |M Proof. Proof outline. We first show that the computation of c(z | s) is related to a Bernoulli process. Then, using every M the results of Section C.1, we can prove the claims of the theorem for individual state-observation pairs. Next, we lift this to all state-observation pairs by distributing the confidence δ. Finally, we individually explain how this yields the two claims of the theorem. c(z | s). Fix a state The Bernoulli process related to M s ∈ S and an observation z ∈ Z. Consider the following random variable: Sample a state s′ ∈ S and the corresponding observation z ′ ∈ Z. Set the random variable to 1 if ∀i ∈ I : (i ∈ Ialways =⇒ zi′ = si ) ∧ (fR (z)i = 0 =⇒ zi′ = ⊥); set the random variable to 0 if ∀i ∈ I : (i ∈ Ialways =⇒ zi′ = si ); and ignore the sampled (s′ , z ′ ) otherwise, i.e. if ∃i ∈ I : (i ∈ Ialways ∧zi′ ̸= si ). Note that the random variable is 1 exactly when the sample would be counted by #D (s, fR (z)), andP the sample is not ignored exactly when it would be counted by r∈R #D (s, r). We require that the probability of the random variable being 1 is equal among all sampled state-observation pairs (s′ , z ′ ) that are not ignored by it, and moreover we require this probability to be equal to M (z | s) = M (fR (z) | s) =: p. To prove this, we use the assumption that M is a simple MAR missingness function; thus, we know that for all s′ that agree with s on all always observable features (formally: ∀i ∈ I : (i ∈ Ialways =⇒ zi′ = si )) , we have p = M (fR (z) | s) = M (fR (z) | s′ ). We have just shown that the random variable we constructed is a Bernoulli process with success probability p = M (z | P s), with the number of repetitions n = r∈R #D (s, r) and the number of successes k = #D (s, fR (z ′ )). Note that the c in Equation (1) is exactly the empirical success definition of M probability p̂ = nk . Observe that we do not need a separate Bernoulli process for every state-observation pair: The number of repetitions P r∈R #D (s, r) is independent of the observation z, since that only affects whether it is counted as success or not. Further,
it suffices to have one random variable per combination of valuation for the features in Ialways , since all states that agree on the always observable features yield the same Bernoulli process. Moreover, we do not need to consider every observation z (as this includes observations that do not admit s), but rather only every missingness indicator vector r ∈ R. In the following, we still write “Every state-observation pair” instead of “Every pair of set of states that agree on the always observable features and missingness indicator vector”, as it is also true and more concise. Single state-observation pair. Consider the Bernoulli process just described for a fixed state-observation pair (s, z). We explain how to use the results of Section C.1 towards proving the first and second claim of the theorem: • First claim: By the third variant of Equation (3), we have that given a precision ε and confidence threshold δs,z , we can compute a necessary number of samples ns,z such that we obtain the PAC guarantee for this stateobservation pair. • Second claim: Observe that a given dataset D corresponds to a number of repetitions of every Bernoulli process. Let ns,z be the number of repetitions for the pair (s, z). Thus, using the second variant of Equation (3), we have that given D (and thus ns,z ) and a confidence threshold δs,z , we can compute a precision εs,z such that we obtain the PAC guarantee for this state-observation pair. All state-observation pairs. We can split the given confidence threshold δ uniformly over all state-observation pairs, δ i.e. for every s ∈ S, z ∈ Z, we have δs,z = |S|·|Z| . Then, by the union bound, the probability of all state-observation pairs being correctly estimated is the sum of all δs,z , which (since we distributed it uniformly) is δ. By splitting the confidence threshold in this way, we can obtain the PAC guarantee for all state-observation pairs. Second claim. We first provide the full argument for the second claim, as it is simpler. Given the dataset D and confidence threshold δ, we obtain an εs,z for all state-observation pairs. The probability that all of these are correct is at least δ. We obtain the claim by taking the maximum over these, i.e. setting ε := maxs∈S,z∈Z εs,z . Then we have that with probability at least δ, for all states s ∈ S and observations c(z | s) − M (z | s)| ≤ ε. z ∈ Z, we have |M First claim. We proceed in two steps: We explain the analogous argument to the second claim, based on an assumption on the dataset. Afterwards, we explain how this assumption on the dataset can be satisfied. Assume that for every state-observation pair (s, z), the dataset D contains at least ns,z samples, i.e. the number computed using Equation (3) inserting ε and δs,z . Then, analogously to the proof of the second claim, computing c using this dataset satisfies that with probability at least M δ, for all states s ∈ S and observations z ∈ Z, we have c(z | s) − M (z | s)| ≤ ε. |M It remains to show that there exists a number n∗ such that a sampled dataset of n∗ histories has the required property.
For this, we have to spend some of our confidence threshold δ, since we can only guarantee the property with a certain probability; there is the chance that even upon sampling n∗ histories, we are unlucky and some state-observation pair has not been sampled often enough. Thus, we split δ as follows: δD is used to guarantee the property of the dataset, and δM c c. Thus, is used to guarantee the consequential property of M δs,z above are obtained by uniformly distributing δM c, not all of δ. Then, by the union bound, the probability that D has the desired property and that the PAC guarantee holds is δD + δ M c = δ. We now need to show that there exists an n∗ such that a dataset of this size contains the required number of samples with probability at least δD . Recall that the dataset is sampled using a fair policy, which means that every state has a positive probability to be visited; thus (assuming that the length of every history is at least as large as the number of states in the miss-MDP), there exists a minimum probability m such that every state is visited with at least probability m in every history. Moreover, observe that for a state-observation pair (s, z), the number of samples for its Bernoulli process is at least the number of times s has been visited; this is because a sample is used when it agrees with s on the always observable features. Thus, for every sampled history, we have a probability of at least m to obtain at least one sample for (s, z). This lower bound on the number of samples for (s, z) is binomially distributed with success probability m (Dekking et al., 2005, Chapter 4.3). Thus, there exists a number of histories n∗ such that the probability of having at least ns,z samples for (s, z) when sampling at least nh histories is greater than δD . As before, this argument was for a single state-observation pair; thus, δD is also uniformly distributed over all state-observation pairs. Summarizing the above: There exists a number n∗ , such that with probability δD , a dataset consisting of n∗ histories contains at least ns,z samples for every state-observation pair (s, z), where ns,z is the number computed using Equation (3) c using this dataset satinserting ε and δs,z . Consequently, M isfies that with probability at least δM c, for all states s ∈ S c(z | s) = M (z | s) ± ε. and observations z ∈ Z, we have M Together, we can guarantee that probably (with probability at c least δ = δD + δM c), M is approximately correct. Proposition 1. The improvements described in Section 4.1 for using knowledge retain the PAC guarantees stated in Theorem 1. Proof. The improvements use the fact that the underlying Bernoulli process in fact does not depend on all features in Ialways . While it is correct to still split on these variables, obtaining two processes with the same true success probability, we can also merge them. More formally, observe that if feature i does not affect the missingness probability of other features, for all valuations of feature i, the corresponding Bernoulli processes have the same success probability. MCAR missingness functions are the most extreme case of this, where the given state is completely irrelevant and it suffices to have one Bernoulli process
per missingness indicator vector. As a side note: Observe that it is indeed necessary to consider every missingness indicator vector and not individual features, since the missingness probabilities need not be independent.
C.3
PAC guarantees for AIMI (Section 4.2)
Theorem 2 (PAC guarantee for AIMI). Let P be a missMDP where the missingness function satisfies independence, c computed using non-self-censoring, and positivity. Then, M Equation (2) offers the same PAC guarantees as in Theorem 1. Proof. This proof is analogous to that of Theorem 1: every missingness probability computed by Equation (2) corresponds to the empirical success probability of a Bernoulli process, which allows to apply the results from Section C.1. This proof differs in the argument why all states grouped together in the same Bernoulli process have the same success probability, and in the argument why it feasible to sample a dataset of the necessary size. By the independence assumption, we know that it suffices to learn every individual P(z i | z ∼ M (s)) for each i ∈ I. By non self-censoring, we know that this probability depends only on features in I \ {i}. Thus, the counter #(s, i, 0) counts exactly the successes of a Bernoulli process with success probability P(z i | z ∼ M (s)), and #(s, i, 1) counts the failures. It only remains to argue that a sufficient dataset can be feasibly obtained. For this, we use the assumption that no feature is missing surely. In other words, every feature has a positive probability to be observed. Thus, every reachable states has a positive probability m to be fully observed. Using this, we can repeat the argument from the proof of Theorem 1. Proposition 2. The improvements described in Section 4.1 for using knowledge retain the PAC guarantees stated in Theorem 2. Proof. (a) If we know from an m-graph that a particular feature i is not influenced by feature j, for all valuations of j the Bernoulli process has the same success probability. Thus, we can merge these Bernoulli processes and ignore feature j. (b) If we know the missingness function is simple MAR and feature j goes missing, we know that it cannot influence the missingness probability of any other feature by definition (Mohan and Pearl, 2021). Then, the proof is the same as in Case (a). (c) If the missingness function is MCAR, we know that no feature influences the missingness probability of any other feature. Thus, we can repeatedly apply the argument of Case (a) to merge all Bernoulli processes until we have one for every feature.
C.4
Computing ε-optimal policies (Section 4.3)
Theorem 3 (Computing ε-optimal Policies). Let P be a missMDP with a missingness function that is simple MAR or that satisfies independence, no self-censoring, and positivity. Assume we can sample histories collected under a fair policy, and we know a lower bound on the smallest missingness probability p ≤ mins∈S,z∈Z M (z | s). Then, for every given precision ε and confidence threshold δ, we can in finite time
compute a policy π ∗ such that with probability at least δ it is ε-optimal, i.e. (supπ VP (π)) − VP (π ∗ ) ≤ ε. Proof. Sampling the dataset. We have sampling access with a fair policy, so every state has positive probability to be visited. Thus, for any finite number n, we can almost surely obtain n samples of every state s in finite time. For the Bernoulli process underlying Equation (1), and if the missingness function is simple MAR, this suffices to guarantee that for every stateobservation pair, we can obtain the number of samples ns,z required for achieving precision ε with confidence δs,z . Similarly, for the Bernoulli process underlying Equation (2), and if the missingness function satisfies positivity, we can also obtain the required number of samples for every state-observation pair. Overall, under the assumptions of the theorem, we can almost surely obtain a dataset in finite time such that it suffices to give PAC guarantees on every state-observation pair. We remark that this does not even require spending confidence budget as we did in the proofs of Theorems 1 and 2, since there we required to get this dataset within a certain number of histories n∗ . Here, we only claim that we can get a sufficient dataset in finite time almost surely. c. The assumptions on the missingness funcObtaining M tion in the statement of the theorem match those in Theorem 1 or Theorem 2. Hence, given the dataset described in the prec in a way such that vious paragraph, we can approximate M with probability δ, it is εM -precise. Note that here we do not employ the full allowed imprecision ε, but rather a smaller εM < ε, since there will be other sources of error. c qualitatively agree. For our technical reasoning, M and M c(z | s) = 0. We we require that M (z | s) = 0 if and only if M prove both directions separately: If M (z | s) = 0, then we c(z | never observe a sample for z when given s, and thus M s) = 0, as it uses an empirical average (Equations (1) and (2)). If M (z | s) > 0, as we use a fair sampling process, we almost surely eventually observe z when given s, and consequently c(z | s) > 0. the empirical average is positive, i.e. M It remains to prove that we can in finite time conclude that c qualitatively agree. This means that we need to be M and M c(z | s) = 0, this is because indeed sufficiently certain that if M M (z | s) = 0 and not just because we haven’t sampled enough yet. For this, we use a proof technique employed in, e.g., Daca et al. (2017): We utilize knowledge of (a lower bound on) the smallest missingness probability p. Further, recall that the confidence threshold δ is distributed over all Bernoulli processes (see Sections C.2 and C.3). Thus, for each Bernoulli process, we have a confidence threshold δs,z . Okamoto’s inequality (see Section C.1) provides an upper bound on the missingness probability that is correct with probability at least δs,z . Thus, when this upper bound is less than p, we can c(z | s) = 0. conclude with sufficient confidence that M Utilizing Lemma 2. Let Pb be the approximated missingness-MDP that is exactly P except for the missingness c instead of M . We have just proven that function, which is M c is εM -precise in finite time we know that with probability δ, M and qualitatively agrees with M . Thus, it satisfies the assumptions specified in Lemma 2, which is proven below. This key technical lemma shows that the values obtained when follow-
ing a policy π in either the original P or the approximated Pb have a bounded difference.4 Formally, for every policy π, we have |VP (π) − VPb (π)| ≤ f (εM ), where f is a monotonically c. increasing function that depends on εM , the precision of M From this, we obtain two facts: Firstly, since this holds for all policies, it also holds for the supremum over all policies, and thus we can bound the difference in the values of the two missingness-MDPs: |sup VP (π) − sup VPb (π)| ≤ f (εM ). π
(4)
π
Secondly, we can apply the same reasoning to a near-optimal policy in Pb. For this, let επ < ε be a precision smaller than our overall error tolerance, and let π ∗ be an επ -optimal policy in Pb, i.e. sup(VPb (π)) − VPb (π ∗ ) ≤ επ . (5) π
We remark that Pb is a fully specified missingness-MDP, and thus a fully specified POMDP, for which solvers computing ε-optimal policies such as SARSOP (Kurniawati et al., 2008) exist. Using Lemma 2, we obtain the following inequality: |VP (π ∗ ) − VPb (π ∗ )| ≤ f (εM ).
(6)
Implications of the inequalities. Since we reason about absolute differences, we need to make case distinctions on whether supπ VP (π) − supπ VPb (π) ≥ 0 or not when applying Equation (4). If supπ VP (π) − supπ VPb (π) ≥ 0, then supπ VP (π) − supπ VPb (π) ≤ f (εM ), and by reordering we get supπ VP (π) ≤ supπ VPb (π) + f (εM ). Otherwise, we have supπ VP (π) < supπ VPb (π). Together, we can obtain that Equation (4) implies: sup VP (π) ≤ sup VPb (π) + f (εM ) π
(7)
π
Analogously, we can make a case distinction in Equation (6) and obtain that: VPb (π ∗ ) ≤ VP (π ∗ ) + f (εM )
(8)
Combining the inequalities. To conclude the proof, we use a chain of inequalities. sup VP (π) ≤ sup VPb (π) + f (εM ) π
(By Equation (7))
π
≤ VPb (π ∗ ) + επ + f (εM ) (By Equation (5)) ≤ VP (π ∗ ) + f (εM ) + επ + f (εM ) (By Equation (8)) By reordering, we obtain |sup VP (π) − VP (π ∗ )| ≤ επ + 2 · f (εM ). π
Hence, since f is a monotonically increasing function, there exists a choice of εM and επ so that επ + 2 · f (εM ) ≤ ε. c Intuitively, while the errors incurred by approximating M and by using an approximately optimal policy add up, we can bound the overall maximum error. Thus, we can choose 4
We highlight that every policy is applicable in both missingnessMDPs, as they only differ in their missingness probabilities, but agree on states, observations, and actions.
the two precisions so that the overall error criterion is met, and the policy π ∗ is ε-optimal in the original missingnessMDP (with probability δ; with the remaining probability, our c can differ by more than εM ). sampling was unlucky and M This concludes the proof. Lemma 2 (Bounding the Value-Difference between P and Pb). Let P be a missingness-MDP and Pb be a missingness-MDP that differs from P only in its missingness function, where it c instead of M . Further, assume that for all states s ∈ S uses M and observations z ∈ Z, we have M (z | s) = 0 if and only c(z | s) = 0, and moreover M (z | s) = M c(z | s) ± εM . if M Then, for every policy π we have |VP (π) − VPb (π)| ≤ f (εM ), where f is a monotonically increasing function. Proof. To uncountable MDPs. Note that both P and Pb are missingness-MDPs, and thus POMDPs. Thus, for each of them, we can construct an uncountable belief MDP with the b respectively. Intuitively, this is same value, called B or B, achieved by unrolling step-by-step the observation function and all possible beliefs that the agent can have after an action; the transition probabilities in these uncountable MDPs depend on the missingness functions. For a more extensive description, see (Russell and Norvig, 2022, Chapter 16.4.1). To finite MDPs. We consider discounted expected reward, with γ the discount factor and ϱmax := max(s,a)∈S×A ϱ(s, a) the maximum state reward. As the expected reward is a geometric series, we can bound the reward that can be obtained after n steps from above as follows: ∞ X i=n
γ i · ϱmax = γ n · ϱmax ·
∞ X i=0
γi =
γ n · ϱmax . 1−γ
For every arbitrarily small precision εγ > 0, we can thus obtain an n such that the reward after n steps is less than εγ . Let Bεγ be the finite MDP obtained from B by only considering states that are reachable within n steps, and analogously define bε . (Note that n is the same for both, since it only depends on B γ γ and ϱmax , which is the same for both of them.) The value of these finite belief MDPs differs from the value of the uncountable belief MDPs and thus the original missingness-MDPs by at most εγ . b are the same Bounding the difference. Recall that B or B except for their transition functions, which depend on M and c, respectively. Still, by assumption of the theorem M and M c qualitatively agree, i.e. M (z | s) = 0 if and only if M c(z | M b s) = 0. Hence, the graph structure of B or B is the same. Thus, the only difference are small perturbations of individual transition probabilities by at most εM . It remains to show the following: Given two finite MDPs that are the same except for small perturbations of the transition probabilities, but where the supports of the the transition functions are the same, provide a bound on the difference in their value. Such a result exists in the literature, namely in Meggendorfer et al. (2025), or more precisely in the extended version of that paper (Meggendorfer et al., 2024, Lemma 5). It remains to show that our setting indeed satisfies the assumptions of (Meggendorfer et al., 2024, Lemma 5).
• “For every closed constant-support RMDP”: Their claim applies to robust MDPs that are closed constant-support. A robust MDP is an MDP whose transitions are not probability distributions, but rather sets of possible values, see (Meggendorfer et al., 2025, Section 2). In our case, bε , instead of considering the concrete MDPs Bεγ and B γ we consider the robust MDP that arises when considering an εM -interval around every missingness probability bε M (z | s). This robust MDP contains both Bεγ and B γ as instantiations. • “For every pair of agent and environment policy”: An agent policy in this setting is exactly the agent policy in ours, so (Meggendorfer et al., 2024, Lemma 5) applies to all policies. An environment policy is the policy that chooses the instantiation of the transition function, i.e. the exact missingness probabilities from the set of all that differ by at most εM in our setting. • “Total-reward objectives:” (Meggendorfer et al., 2024, Lemma 5) concerns undiscounted total-reward or mean payoff objectives. Undiscounted total-reward generalizes discounted expected reward, using the standard construction which adds an edge transitioning with probability γ to a dedicated sink state to every transition. Thus, the lemma is applicable to the objective in our setting. • “The value function is continuous w.r.t. the environment policy”: This is the claim of (Meggendorfer et al., 2024, Lemma 5). More formally, if the environment chooses missingness probabilities differently with some deviation εM , then the deviation in the value between the two instantiations is bounded by some monotonically increasing function g(εM ). This is exactly the claim we require, since it means that for all agent policies π and all missc that are εM -close to M , we have ingness functions M |VBεγ (π) − VBbε (π)| ≤ g(εM ). γ
We also argue that g can be effectively computed, as it depends on the size of the state space, the reward function, and the minimum occurring transition probability, all of which are known to us (recall that Theorem 3 assumes knowledge of a lower bound on the minimum missingness probabilities). The concrete way of deriving the distance is provided on (Meggendorfer et al., 2024, page 17). Putting it all together. Our goal is to show that we can compute an f such that for all policies π we have: |VP (π) − VPb (π)| ≤ f (εM ). The following chain of equations proves our goal: |VP (π) − VPb (π)| = |VB (π) − VBb (π)| (Using the uncountable belief MDPs) ≤ |Bεγ (π) − VBbε (π)| + εγ γ
(Using the finite MDPs; decreasing both values by at most εγ increases the difference by at most εγ ) ≤ g(εM ) + εγ (By bounding the difference). For simplicity of presentation, we choose εγ = εM , and thus setting f (εM ) := g(εM ) + εM concludes the proof.
Figure 4: left: The Predator benchmark, where the predator (lion) is the agent trying to catch its prey (boar). Predator and prey can move in all four cardinal directions, where prey chooses an action that increases the distance to the predator (red arrows). right: The m-graphs for the predator and prey benchmark describing missingness functions of types simple MAR (gray), identifiable MNAR (gray + blue). Causal dependencies between the state features were omitted for clarity.
D
Benchmarks and Experiments
Here we describe our benchmarks. A benchmark corresponds to an environment with a particular missingness function. We provide a detailed description of the benchmarks as well as the parameters for running the experiments.
Figure 5: The m-graphs for the ICU benchmark describing missingness functions of types simple MAR (gray + blue), identifiable MNAR (gray + red) and unidentifiable MNAR (gray + red + orange). Causal dependencies between the state features were omitted for clarity.
D.1
Description
ICU. This environment, inspired by prior clinical decisionmaking models (Johnson et al., 2022; Pollard et al., 2018; Thoral et al., 2021; Hyland et al., 2020), simulates a doctor treating a patient with an infection that progresses stochastically over time. The state of the patient consists of the infection severity, the temperature, and the heart rate. The infection causally influences both the heart rate and the temperature. The doctor has an option to wait, to administer costly antibiotics that reduce the infection severity, or to order a test, which is a measuring action that may reveal the infection severity. The reward function penalizes high infection levels as well as costly interventions (ordering a test and administering antibiotics). Thus, the doctor’s objective is to maintain the patient’s
infection severity at low levels by administering antibiotics only when necessary. For ease of modeling, the state space also includes the value of the last test ordered. We evaluate three different missingness functions M , corresponding to distinct missingness functions, illustrated in the m-graph in Figure 5. In all cases, the heart rate and the infection severity may be missing, whereas temperature and the last test ordered are always observed. The success rate of the test that reveals the infection severity may depend on different features, resulting in the following missingness functions. (1) Simple MAR, where the success rate only depends on the (always observed) temperature. (2) MNAR (id.), where the success rate only depends on the (not always observed) heart rate, resulting in an identifiable MNAR function without self-censoring and satisfying the positivity assumption. (3) MNAR (unid.) is an extension of MNAR (id.), where the infection severity influences the test success rate, introducing self-censoring and thus making the function unidentifiable. The ICU environment has 800 reachable states and 1650 observations for all missingness functions. More details on feature dimensions are given in Table 2. Predator. This environment is a variant of the Tag benchmark from Pineau et al. (2003), where an agent (in our case, a predator) is tasked with chasing a partially hidden target (a prey) in a 2D grid environment. The prey senses the predator and usually moves away from it; in case multiple directions lead away from the predator, the prey chooses uniformly at random. The predator’s movement is deterministic (dictated by the policy), but moving in an intended direction may randomly fail due to terrain conditions. Predator obtains a flat reward upon catching the prey, and thus the discounting incentivizes catching the prey as soon as possible. The environment may feature three distinct biomes – plains, mountains, or jungles – that influence the predator’s observability of the prey, see Figure 4, and thus define the missingness function. We investigate the following three variants thereof. (1) MCAR, which features only one type of terrain, i.e., the prey is observed with constant probability. (2) sim-
Table 1: Hyper parameter distributions for the random search for PPO policies.
Category
Hyperparameter
Architecture Architecture PPO PPO PPO Optimizer (actor) Optimizer (critic) Optimization Optimization
Number of layers Hidden units per layer Clip range (ϵ) Entropy coefficient (λϵ ) Target KL divergence Learning rate Learning rate Minibatch size Epochs per update
1.0
ICU
ICU
1.0
1.0
ICU
Search space
Sampling
{2, 3, 4, 5} {32, 64, 128, 256, 512} [0.10, 0.30] [1e-4, 5e-2] [5e-3, 3e-2] [1e-5, 3e-4] [1e-4, 3e-3] {32, 64, 128, 256} {5, 10, 20}
Discrete uniform Discrete uniform Uniform Log-uniform Log-uniform Log-uniform Log-uniform Discrete uniform Discrete uniform
Predator
Predator
Predator
0
0
4
4
8
8
12
12
0 4
0.5
0.5
0.5
0.0
0.0
0.0
0.5
0.5
0.5
1.0
1.0
1.0
24
1.5
28
8 12
simple MAR
1.5
MNAR (ident.) MNAR (unident.)
AMCAR AsMAR AIMI * (optimal) prior
Model-free
16 20
1.5
Model-based
MCAR
POMCP PPO+Memory PPO rand
simple MAR MNAR (unident.)
Figure 6: Baseline comparison plot for all benchmarks. Table 2: Sizes of the feature dimensions of each environment. Sizes for the MCAR missingness function in the Predator environment in parenthesis.
in a model with 1765 reachable states and 3379 observations. More details on feature dimensions are given in Table 2.
D.2 ICU Feature
Size
Predator Feature Size
Infection Test Temperature Hear Rate
4 5 4 10
u v x y
5 (10) 5 (5) 5 (10) 5 (5)
ple MAR, where the environment features plains as well as mountains from which the predator has a higher chance of observing its target. (3) MNAR (unid.), where the prey has an option to hide in jungle cells, introducing self-censoring of its position. We stress that when the predator loses track of the prey, both features corresponding to x and y coordinates of the prey go missing simultaneously, modeled by dependencies between missingness indicators Rx and Ry . The dependence between the missingness indicators is one key difference from the ICU benchmark together with lower stochasticity in the transition function. The Predator environment has 626 reachable states and 1311 observations for the simple MAR and MNAR (unid.) missingness functions, including one initial state. For the MCAR missingness function we used a larger map resulting
Experimental setup
Technical Setup. For SARSOP and POMCP, we used highperformance workstations equipped with an AMD Ryzen ThreadRipper PRO 5965WX (24-core, 3.8GHz) CPU, 512 GB ECC DDR4 RAM, and a 2 TB PCIe 4.0 NVMe SSD. The PPO benchmarks were obtained on a Macbook Pro, with an M3 chip with 11 cores, 18 GB LPDDR5 RAM. Simulating trajectories. For both benchmarks, we used a discount factor of γ = 0.95. We considered dataset sizes |D| ∈ {10, 50, 100, 500, 103 , 5 · 103 , 104 , 105 , 106 , 107 }. To obtain a dataset containing |D| samples, we simulated finite trajectories until their lengths summed up to |D|. A trajectory is terminated when it reaches a terminal state (only for the Predator bechmark, whenlthe predator catches the m −3 prey) or if its length exceeds L = logγ (1−γ)·10 , where ϱmax ϱmax := max ϱ(s, a). Here, L denotes the smallest integer P∞s,a satisfying k=L γ k ·ϱmax < 10−3 , i.e. a time step after which the maximum discounted cumulative reward cannot exceed 10−3 . For each dataset size |D|, we generated 20 independent datasets of this size. Timeouts & precision. For the baselines, we used the timeout of 5 minutes when solving the POMDP (to obtain π ∗ and π prior ) and the same timeout to evaluate the resulting policy (or
PPO Baseline
The baseline policies for Proximal Policy Optimization (PPO) (Schulman et al., 2017) were computed using the implementation of the Crux.jl framework (Version 0.1.3) in Julia (Version 1.11.5). Frame Stacking. In order to provide memory to the PPO policy, the last nframes observations and actions were concatenated. At an episode start the missing frames in the history were padded with POMDP’s symbol for missingvalues. The num ber of frames was determined by nframes = logγ (ε(1 − γ)) , where γ is the respective miss-MDP’s discount factor and ε is the same precision used for evaluating policies computed via SARSOP. With a history of nframes the policy had access to a history sufficient for accurate evaluation, as stated in the next paragraph. For ICU and Predator the frames were set to nframes = 148. Training and Evaluation. All PPO policies were trained for nsteps = 106 steps with individual seeds using the Adam optimizer. The policies were evaluated using cumulative discounted return, identical to the evaluation of the other benchmarks. During evaluation actions were sampled from PPO’s action distribution. The mean performance was computed over neval = 2000 episodes. The evaluation horizon per episode was set to nframes (see above). Parameter Search and Model Selection. We performed 20 random searches for the hyper parameters, for each benchmark and corresponding missingness function (20 searches for each ICUsMAR , ICUMNAR (id.) , ICUMNAR (unid.) , . . . ). The policy and value networks always used the same architectural hyper parameters. We report the performance of the best model for each search with respect to the cumulative discounted reward. Table 1 provides the parameter distributions of the random search. The hyper parameters for all runs on each benchmark are provided in our repository.
D.4
POMCP Baseline
The baseline policies for Partially Observable Monte Carlo Planning (POMCP) (Silver and Veness, 2010) were computed using the BasicPOMCP.jl framework (Version 0.3.12) in Julia (Version 1.11.5), which implements the PO-UCT online tree search algorithm together with particle filters (resulting in POMCP) for POMDPs. Planning Setup. POMCP was used as an online, planning baseline with access to the transition and reward functions of the underlying miss-MDP. Belief updates were performed via an external belief updater, as BasicPOMCP.jl does not reuse particles from planning simulations for belief propagation. In fact, in order to make POMCP competitive against the model-based SARSOP policies, it was provided the true belief whenever its own belief collapsed due to an unseen observation. At each decision step, planning was performed from scratch based on the current belief.
0.8 Total Variation
D.3
Predator, MNAR (unid.)
1.0
0.6
Algorithms
0.4
AMCAR AsMAR AIMI
0.2 0.0 1 10
105
103
1.0 Normalized Value
π rand ). To obtain a policy π̂ by solving the corresponding Pb, we used a timeout of 3 minutes and evaluated π̂ for 2 minutes. In all cases, solving was additionally allowed to terminate upon reaching the relative precision of 10−3 .
0.5
107
Metrics ATV WTV Value
Optimal *
0.0 0.5 1.0
| |
Figure 7: Empirical results for the PredatorMNAR (unid.) benchmark.
Solver Configuration. Leaf values were estimated using rollout-based evaluation with a random rollout policy. Unless stated otherwise, we used a maximum planning depth of 20, the default exploration constant of c = 1.0, and 1000 tree queries per action. Random seeds were fixed to ensure reproducibility. Evaluation Protocol. POMCP policies were evaluated using cumulative discounted return, consistent with all other baselines. During evaluation, the planner was executed online and selected actions based on the current belief. Results were averaged over neval = 2000 episodes, using the same discount factors and episode horizons as in the remaining benchmarks.
D.5
Additional Results
We provide results for an additional PredatorMNAR (unid.) benchmark in Figure 7. Its missingness function breaks the assumptions of our algorithms AMCAR, AsMAR and AIMI. Therefore, all of the approximations of the missingness funcc converge to a non-zero total variation. As a result, the tions M c do not converge to policies computed by SARSOP using M ∗ the optimal policy (π ). Instead all policies perform similarly to π prior , the policy initialized with an uninformed prior on M and corresponds to the normalized value of zero. In Figure 6 we provide the comparison with baselines for all benchmarks, adding to Figure 3 (right).