Linear Programming for Decision Processes with Partial Information

Markov Decision Processes (MDPs) are stochastic optimization problems that model situations where a decision maker controls a system based on its state. Partially observed Markov decision processes (POMDPs) are generalizations of MDPs where the decision maker has only partial information on the state of the system. Decomposable POMDPs are specific cases of POMDPs that enable one to model systems with several components. Such problems naturally model a wide range of applications such as predictive maintenance. Finding an optimal policy for a POMDP is PSPACE-hard and practically challenging. We introduce a mixed integer linear programming (MILP) formulation for POMDPs restricted to the policies that only depend on the current observation, as well as valid inequalities that are based on a probabilistic interpretation of the dependence between variables. The linear relaxation provides a good bound for the usual POMDPs where the policies depend on the full history of observations and actions. Solving decomposable POMDPs is especially challenging due to the curse of dimensionality. Leveraging our MILP formulation for POMDPs, we introduce a linear program based on ``fluid formulation'' for decomposable POMDPs, that provides both a bound on the optimal value and a practically efficient heuristic to find a good policy. Numerical experiments show the efficiency of our approaches to POMDPs and decomposable POMDPs.


Introduction
Many real-world problems where a decision maker controls a stochastic system evolving over time can be modeled as Partially Observed Markov Decision Processes (POMDPs). In such problems, at each timestep, the system is in a state s in some finite state space X S . The decision maker does not observe s, but has access to an observation o that belongs to some finite observation space X O , and is randomly emitted with probability p(o|s). Based on this observation, the decision-maker chooses an action a from some finite action space X A . The system then transits randomly to a new state s ′ in X S with probability p(s ′ |s, a) and the decision maker obtains an immediate reward r(s, a, s ′ ). The goal of the decision maker is to find a policy δ t a|o , which represents a conditional probability of taking action a in X A given current observation o in X O at time t, maximizing the expected total reward over a finite horizon T where S t and A t are random variables representing the state and the action at time t and the expectation over δ is taken with respect to the distribution P δ induced by the policy δ chosen in the set of policies ∆. In the POMDP literature, the decision maker has perfect-recall, i.e., the decision is taken given all history of observation and actions at each time step. Hence the policy lies in a greater set of policies ∆ P R ⊃ ∆. Hence Problem (1) provides a lower bound on POMDP with perfect-recall. While POMDP problem with perfect-recall is PSPACE-hard Papadimitriou and Tsitsiklis [1987], we restrict to Problem (1) in this work, which is NP-hard Mauá et al. [2012]. POMDPs are a generalization of the well-known Markov Decision Processes (MDPs). POMDPs are based on Hidden Markov Models (HMMs), which give a higher power of modeling than the usual Markov Chains (Baum and Petrie [1966]) on which MDPs are based. They appear naturally in the context of predictive maintenance, where a machine evolves over time and at each time step the decision maker decides to replace or not the machine. The decision maker does not have access to the machine's wear and takes his action while observing output signals. Therefore, the goal is to find an optimal replacement policy (which can be time dependent) minimizing the total expected cost over a finite time horizon. Like MDPs, POMDPs suffer from the curse of dimensionality. Indeed, when the state space X S is large, the usual exact methods such as dynamic programming become computationally intractable (Puterman [1994]). Leveraging the well-known linear formulation of d'Epenoux [1963] for MDPs, Bertsimas and Mišić [2016] propose a tractable heuristic to approximately solve MDPs when the system is composed of several components evolving independently and the state space can be written as the Cartesian product of the individual state space of each component. Such problems are called decomposable MDPs. We introduce the notion of decomposable POMDPs, a generalization where each component evolves independently and individually as a POMDP. For example, in the case of predictive maintenance, a machine is composed of several equipments and each equipment can be modeled individually as a POMDP. Unfortunately, there is no tractable linear program on which we can leverage to generalize the approach of Bertsimas and Mišić [2016]. A good reason for that is PSPACE-hardness of POMDP Problem (Papadimitriou and Tsitsiklis [1987]). The first exact algorithms for POMDP use dynamic programming (Sondik [1973]) and consider the POMDP as a MDP where we replace the current state by a belief state, which corresponds to the probability of being in state s at time t. However, such methods become computationally expensive even for small state spaces and small observation spaces. More recently, new policy-based solution methods leverage bounds to search efficiently in the policy space (Kaelbling et al. [1998]). Particularly, the finite-state controller algorithms (Poupart and Boutilier [2004]) combine a policy iteration algorithm that enumerates and evaluates policies on the observables history (represented as a new random variable) and gradient ascent method to find local optima, restricting the policy space. Leveraging policy search, Aras et al. [2007] proposed an exact mixed-integer linear program for POMDP problem. However, such a formulation is intractable even for small horizon time. In this paper, we consider exact and approximate linear formulations for Problem (1). Our contributions are as follows : 1. We propose a mixed-integer linear program (MILP) that exactly solves Problem (1). This formulation generalizes the dual linear program for MDP of d'Epenoux [1963].
2. We introduce an extended formulation with new valid inequalities that improve the resolution of our mixed-integer linear program. Such inequalities come from a probabilistic interpretation of the dependence between random variables. Experiments show their efficiency.
3. We show that the linear relaxation of our MILP provides an upper bound on the usual POMDP with perfect-recall.
4. In the case of decomposable POMDPs, leveraging the MILP previously mentioned, we propose a heuristic that repeatedly solves linear approximations. It extends to POMDPs to the fluid formulation introduced by Bertsimas and Mišić [2016], and strengthens it with valid inequalities.

Numerical experiments show the efficiency of our approach.
The paper is organized as follows. Section 2 presents our MILP formulation for Problem (1), and introduces our valid inequalities. We also present the link between our formulation and the usual POMDP with perfect-recall. In Section 3, we define decomposable POMDPs, we present our tractable linear program giving an upper bound on the optimal value, and use it in a heuristic. In Section 4, we present the numerical results. The proofs of the main results are available in Appendix A.

Mixed Linear Programming for Partially Observed Markov Decision Processes
In this section, we present an MILP that exactly models Problem (1). Given N in N we use the notation [N ] for {1, . . . , N }.

Problem settings
Let X S , X O , and X A be three finite sets corresponding respectively to the state space, the observation space and the action space. For a state s ∈ X S and an observation o ∈ X O , let p(o|s) be the conditional probability of observing o given state s Similarly, we define the probability of transition from state s ∈ X S to s ′ ∈ X S while taking action a ∈ X A p(s ′ ) = P S 1 = s ′ , and, p(s ′ |s, a) = P S t+1 = s ′ |S t = s, A t = a ∀t ∈ [T ].
We define an immediate reward function r : X S × X A × X S → R, which associates to a transition (s, a, s ′ ) a reward r(s, a, s ′ ). The goal is to solve Problem (1), where and P δ and E δ denote the probability distribution and expectation induced by policy δ on (S t , O t , A t ) t . We define the set of deterministic policies ∆ 0 as Note that ∆ is the convex hull of ∆ 0 . Any policy in ∆\∆ 0 is a randomized policy.

A mixed-integer linear program
It is well-known that there always exists an optimal deterministic policy for MDPs Puterman [1994]. This result can be extended to POMDPs. Lemma 4.3 in Liu [2014] ensures that there always exists an optimal deterministic policy for Problem (1). Equivalently, We introduce a collection of variables µ = (µ t s ) s , (µ t sa ) s,a , (µ t soa ) s,o,a t and the following mixedinteger linear program (MILP).
We show in Appendix that a feasible solution µ of Problem (2) can be interpreted as a probability distribution over the random variables, i.e, µ t s , µ t sa and µ t soa respectively represent the probabilities Let v * and z * respectively denote the optimal values of Problem (1) and Problem (2). The following theorem ensures that MILP (2) models Problem (1).
Theorem 1. Let (µ, δ) be a feasible solution of Problem (2). Then µ is equal to the distribution P δ induced by δ, and (µ, δ) is an optimal solution of Problem (2) if, and only if δ is an optimal deterministic policy of Problem (1). Furthermore, v * = z * .

Valid inequalities
The difficulty of POMDP comes from the fact that which induces non-linearities. A corollary of these independences is that Theorem 1 ensures that these independences are satisfied by the distribution µ corresponding to an integer solution (µ, δ) of MILP (2). If the component µ of a solution (µ, δ) of the linear relaxation of MILP (2) can still be interpreted as a distribution, independences (3) and (4) are unfortunately no longer satisfied according to this distribution. We now introduce an extended formulation and valid inequalities that enable to restore independences (4). We introduce new variables µ t s ′ a ′ soa that can be interpreted as the probabilities Consider the following equalities where Note that p(s|s ′ , a ′ , o ′ ) does not depend on the policy δ and can be easily computed using Bayes rules. Therefore, constraints in (5) are linear.
Proposition 2. Equalities (5) are valid for Problem (2), and there exists solution µ of the linear relaxation of (2) that does not satisfy constraints (5).
Hence, constraints (5) strengthen the linear relaxation. Numerical experiments in Section 4 show the efficiency of such valid inequalities.
Remark 1. Our extended formulation with valid inequalities has many more constraints than the initial one. Its linear relaxation therefore takes longer to solve. △

Link with perfect-recall
In the previous section, we assumed the decision maker forgets all history of information. It would be interested to measure the policy obtained by solving Problem (2) against the POMDP with perfect-recall. Let v * P R be the optimal value of perfect-recall POMDP, i.e., by optimizing the expectation of (1) over ∆ P R . Let z * LR be the value of the linear relaxation of MILP (2). (2) is an upper bound on the POMDP value with perfect-recall :

Theorem 3. The linear relaxation of MILP
The proof is based on the influence diagram representation of POMDP problem. The authors in Parmentier et al. [2019, e.g. Theorem 14] prove that the linear realaxation of our MILP is equivalent to the MDP relaxation of POMDP. Therefore, the integrity gap obtained by solving MILP (2) bounds the gap with the value of perfect-recall POMDP. By adding equalities (5), we obtain a better gap.

Decomposable Partially Observed Markov Decision Processes
Due to the curse of dimensionality, some applications have exponentially large X S and cannot be solved using MILP (2). In this section, we propose a tractable heuristic for POMDPs with large but decomposable state space X S .

Problem settings
We now introduce the notion of decomposable POMDP. We consider a system that can be decomposed into M components, so that the system state space X S and observation space X O can be written as the Cartesian product of individual state spaces X m S and observation spaces To sum things up, a decomposable POMDP is a POMDP with state space The goal is still to find a policy maximizing the total expected reward

Linear formulation
As a decomposable POMDP is a POMDP, we can solve Problem (7) using MILP (2). However, the number of constraints and variables grows exponentially with M , and even the linear relaxation of MILP (2) We show in Appendix that (τ t,m s ) s , (τ t,m sa ) s,a , (τ t,m soa ) soa , and (τ t a ) a can still be interpreted as probability distributions on X S , X S,m × X A , X S,m × X O,m × X A , and X A , which coincide when marginalized on the intersection of their domains. However, there is no guarantee that there exists a joint distribution on (X S × X O × X A ) T from which they can be derived as marginal distributions. Let v * M and z * M be respectively the optimal values of Problem (7) and Problem (8). (7), and v * M ≤ z * M . This inequality is not an equality in general, as we will see in the numerical experiments. Linear formulation (8) is a generalization to decomposable POMDPs of the "fluid" formulation proposed by Bertsimas and Mišić [2016] for decomposable MDPs.

Theorem 4. Problem (8) is a relaxation of Problem
The quality of the bound z * M can be improved by generalizing the valid inequalities introduced in Section 2.3. We introduce new variables τ t,m s ′ a ′ soa that can be interpreted as the probability P(S m t−1 = s ′ , A t−1 = a ′ , S m t = s, O m t = o, A t = a). Consider the following linear inequalities.
Since decomposable POMDPs are POMDPs, we would like to compare our policies with optimal value of POMDP with perfect-recall. Let v * P R be the optimal value of POMDP with perfect-recall, i.e., the value of the expectation in (7) by optimizing over ∆ P R .
Theorem 6. The linear formulation (8) gives an upper bound on the POMDP value with perfect-recall, i.e., v * P R ≤ z * M .

Heuristic
Consider an optimal solution τ of Problem (8). Solution τ is achievable if there exists a policy δ ∈ ∆ such that The following proposition generalizes Proposition 3 of Bertsimas and Mišić [2016].
Proposition 7. Let τ be an optimal solution of Problem (8). If τ is achievable, then In the remainder of this section, we assume that the decision maker observes the initial observationõ in X O . This assumption imposes conditioning all probabilities on the event O 1 =õ in Problem (7) and Problem (8). Therefore, it suffices to replace p m (o|s) by 1õm(o) at time t = 1 where 1 y (x) is the indicator function of y evaluated in x.
Theorem 8. Let τ be an optimal solution of Problem (8) with an initial observationõ ∈ X O . Suppose that τ is achievable and let δ be the policy achieving τ . We define the initial policy δ Then the policy (δ 1 , δ 2 , . . . , δ T ) is optimal for Problem (7).
Under condition (10), Theorem 8 says that we can take an optimal deterministic action at time t = 1. However, an optimal solution τ of Problem (8) is not always achievable. Nevertheless, a feasible solution of Problem (8) satisfying the valid inequalities (9) respects the transition of all independent components and almost all independences between random variables. Therefore, τ may be close to being achievable. Consequently, we propose a heuristic similar to the algorithm presented in Bertsimas and Mišić [2016], that repeatedly solves Problem (8) and selects action argmax a∈X A τ 1 a (that depends on initial observationõ). Algorithm 1 states our heuristic policy, which we expect to provide good performances.
Note that each iteration of Algorithm 1 solves a linear program with a polynomial number of constraints and variables. Numerical experiments in Section 4 show the efficiency of this heuristic.

Numerical experiments
We now provide experiments showing the practical efficiency of our approaches to POMDPs and decomposable POMDPs. All linear programs have been implemented in Julia with JuMP interface and solved using Gurobi 7.5.2. Experiments have been run on a server with 192Gb of RAM and 32 cores at 3.30GHz.  (5) 1.29 0.62 TL Table 1: POMDP results using MILP (2) with and without (5), with a time limit TL=3600s

Instances
Each instance is generated by first choosing X S , X O , X A , and finally M when we consider decomposable MDPs. We then randomly generate the initial probability p m (s), the transition probability p m (s ′ |s, a), the emission probability p m (o|s) and the immediate reward function r m (s, a, s ′ ) for all m ∈ [M ].
Remark 2. In our numerical experiments, we use instances with short horizons T in {5, 10, 20}. This is not a limitation in practice, as the length T of the horizon is not the main challenge when designing heuristics for decision processes. Bertsimas and Mišić [2016] solve large or infinite horizon instances of decomposable MDPs using rolling horizon approaches. They obtain good performances by solving at each time steps problems on a horizon T = 10. Similar rolling techniques can be used to adapt Algorithm 1 to large or infinite horizon decomposable POMDPs. △

Simulated experiments on single POMDP
We solve Problem (2) with and without valid equalities (5). Algorithms were stopped after a Time Limit (TL) of 600s. Table 1 shows the efficiency of MILP (2) to solve (1). The first four columns indicate the size of state space X S , observation space X O , action space X A and time horizon T . The fifth column indicates the mathematical program used to solve Problem (2) with or without constraints (5). In the last three columns, we report the integrity gap, the final gap and the computation time for each instance.

Simulated experiments on decomposable POMDPs
We now compare two heuristics to solve decomposable POMDPs: Algorithm 1 solving Problem (8) without valid inequalities (9), and a greedy algorithm, which infers the most probable state and takes the action maximizing the expected immediate reward of the next state. On each instance, we compute an upper bound z * M,k on the optimal value by solving Problem (8) with constraints (9). We test our two heuristics under K = 100 different scenarios. Table 2 summarizes the results obtained. The first five columns describe the instance. They indicate the sizes of state space X S , observation space X O , and action space X A , the horizon time T , and the number of components M . The sixth column indicates the heuristic used. The next column provides the average computation time needed at each time step to take a decision. When using Algorithm 1, this is the time needed to solve MILP (8). Finally, column "Av. gap (%)" provides the gap between the upper bound z * M,k and total reward R k,h obtained using the heuristic on average on the K scenarios.  Note that when the number of components grows, Algorithm 1 outperforms the standard greedy algorithm.
Proof of Theorem 1. Let (µ, δ) be a feasible solution of Problem (2). We prove by induction on t that µ t s = P δ S t = s , µ t sa = P δ S t = s, A t = a and µ t soa = P δ S t = s, O t = o, A t = a . At time t = 0, the statement is immediate. Suppose that it holds up to t − 1. Constraints (2c) and induction hypothesis ensure that where the last equality comes from the law of total probability. Since δ t a|o are binary, constraints (2e), (2f) and (2g) ensure that : Finally, constraints (2d) ensure that µ t sa = P δ (S t = s, A t = a). Therefore, any feasible solution µ of (2) is equal to the distribution P δ . Consequently, which implies that δ is optimal if and only if (µ, δ) is optimal for Problem (2) and v * = z * .

A.1 Decomposable Partially Observed Markov Decision Processes
Proof of Theorem 4. We prove that an optimal solution (µ, δ) of Problem (2) This solution is indeed a feasible solution of Problem (8).
Proof of Proposition 7. We prove that we can build a feasible solution of Problem (2) for M components. We build such a solution by induction on t. For t = 1, we define µ 1 s = M m=1 τ 1,m s , µ 1 so = p(o|s)µ 1 s , µ 1 soa = δ 1 a|o µ 1 so and µ 1 sa = o∈X O µ 1 soa . We define the following induction equation : It is easy to observe that all constraints of problem (2) are satisfied. Therefore, we build a feasible solution of Problem (2) with the same expected reward. Since Problem (7) can be exactly solved by Problem (2) by considering the complete system and the probabilities over X S and X O . Using Proposition (4), there is equality z M = v M .