Year: 2021

Abstract:
We consider the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP) with finite state and action spaces with respect to either the discounted or mean reward criterion. We show that the (discounted) state-action frequencies and the expected cumulative reward are rational functions of the policy, whereby the degree is determined by the degree of partial observability. We then describe the optimization problem as a linear optimization problem in the space of feasible state-action frequencies subject to polynomial constraints that we characterize explicitly. This allows us to address the combinatorial and geometric complexity of the optimization problem using recent tools from polynomial optimization. In particular, we estimate the number of critical points and use our polynomial programming description of reward maximization to solve a navigation problem in a grid world.

heading: 1 INTRODUCTION
text: Markov decision processes (MDPs) were introduced by Bellman (1957) as a model for sequential decision making and optimal planning (see, e.g., Howard, 1960; Derman, 1970; Puterman, 2014). Many algorithms in reinforcement learning rely on the ideas and methods developed in the context of MDPs (see, e.g., Sutton & Barto, 2018). Often in practice, the decisions need to be made based only on incomplete information of the state of the system. This setting is modeled by partially observable Markov decision processes (POMDPs) introduced by Åström (1965) (for a historical discussion see Monahan, 1982), which have become an important model for planning under uncertainty. In this work we pursue a geometric characterization of the policy optimization problem in POMDPs over the class of stochastic memoryless policies and its dependence on the degree of partial observability.
It is well known that acting optimally in POMDPs may require memory (Åström, 1965). A POMDP with unlimited memory policies can be modeled as a belief state MDP, where the states are replaced by probability distributions that serve as sufficient statistics for the previous observations (Kaelbling et al., 1998; Murphy, 2000). Finding an optimal policy in this class is PSPACE-complete for finite horizons (Papadimitriou & Tsitsiklis, 1987) and undecidable for infinite horizons (Madani et al., 2003; Chatterjee et al., 2016). Therefore, it is of interest to consider POMDPs with constrained policy classes. A natural class to consider are memoryless policies, also known as reactive or Markov policies, which select actions based solely on the current observations. In this case, it is useful to allow the actions to be selected stochastically, which not only allows for better solutions but also provides a continuous optimization domain (Singh et al., 1994).
Although they are more restrictive than policies with memory, memoryless policies are attractive as they are easier to optimize and are versatile enough for certain applications (Tesauro, 1995; Loch & Singh, 1998; Williams & Singh, 1999; Kober et al., 2013). In fact, finite-memory policies can be modeled in terms of memoryless policies by supplementing the state of the system with an external memory (Littman, 1993; Peshkin et al., 1999; Icarte et al., 2021). Hence theoretical advances on memoryless policy optimization are also of interest to finite-memory policy optimization. Theoretical aspects and optimization strategies over the class of memoryless policies have been studied in numerous works (see, e.g., Littman, 1994; Singh et al., 1994; Jaakkola et al., 1995; Loch & Singh, 1998; Williams & Singh, 1999; Baxter et al., 2000; Baxter & Bartlett, 2001; Li et al., 2011; Azizzadenesheli et al., 2018). However, finding exact or approximate optimal memoryless stochastic policies for POMDPs is still considered an open problem (Azizzadenesheli et al., 2016), which is NP-hard in general (Vlassis et al., 2012). One reason for the difficulties in optimizing POMDPs
is that, even in a tabular setting, the problem is non-convex and can exhibit suboptimal strict local optima (Bhandari & Russo, 2019). For memoryless policies the expected cumulative reward is a linear function of the corresponding (discounted) state-action frequencies. In the case of MDPs the feasible set of state-action frequencies is known to form a polytope, so that the optimization problem can be reduced to a linear program (Manne, 1960; De Ghellinck, 1960; d’Epenoux, 1963; Hordijk & Kallenberg, 1981). On the other hand, to the best of our knowledge, for POMDPs the specific structure of the feasibility constraints and the optimization problem have not been studied, at least not in the same level of detail (see related works below).
Related works In MDPs, the (discounted) state-action frequencies have been shown to form a polytope resp. a compact convex set in the finite resp. countable state-action cases, whereby the extreme points are given by the state-action frequencies of deterministic stationary policies (Derman, 1970; Altman & Shwartz, 1991). Further, Dadashi et al. (2019) showed that the set of state value functions in finite state-action MDPs is a finite union of polytopes. The set of stationary state-action distributions of POMDPs has been studied by Montúfar et al. (2015) highlighting a decomposition into infinitely many convex subsets whose dimensions depend on the degree of observability. Although this decomposition can be used to localize optimal policies to some extent, a description of the pieces in combination is still missing, needed to capture the properties of the optimization problem. We will obtain a detailed description in terms of finitely many polynomial constraints with closed form expressions and bound their degrees in terms of the observation mechanism. This yields the formulation of reward maximization in infinite-horizon POMDPs as a polynomial optimization problem, where Cohen & Parmentier (2018) obtained a description of finite-horizon POMDPs as a mixed integer linear program.
Grinberg & Precup (2013) showed that the expected mean reward is a rational function and obtained bounds on the degree of this function. We generalize this to the setting of discounted rewards and refine the result by relating the rational degree to the degree of observability. For both MDPs and POMDPs the expected cumulative reward is known to be a non-convex function of the policy even for tabular policy models (Bhandari & Russo, 2019). Nonetheless, for MDPs critical points can be shown to be global maxima under mild conditions. In contrast, for POMDPs or MDPs with linearly restricted policy models, it is known that non-global local optimizers can exist (Baxter et al., 2000; Poupart et al., 2011; Bhandari & Russo, 2019). However, nothing is known about the number of local optimizers. We will present bounds on the number of critical points building on our computation of the rational degree and feasibility constraints.
The structure of the expected cumulative reward has been studied in terms of the location of the global optimizers and the existence of local optimizers. Most notably, it is well known that in MDPs there always exist optimal policies which are memoryless and deterministic (see Puterman, 2014). In the case of POMDPs, optimal memoryless policies may need to be stochastic (see Singh et al., 1994). Montúfar et al. (2015); Montúfar & Rauh (2017); Montúfar et al. (2019) obtained upper bounds on the number of actions that need to be randomized by these policies, which in the worst case is equal to the number of states that are compatible with the observation. Although we do not improve these results (which are indeed tight in some cases), our description of the expected cumulative reward function leads to a simpler proof of the bounds obtained by Montúfar et al. (2015).
Neyman (2003) considered stochastic games as semialgebraic problems showing that the minmax and maxmin payoffs in an n-player game are semialgebraic functions of the discount factor. Although this is not directly related to our work, we take a similar philosophy. We pursue a semialgebraic description of the feasible set of discounted state-action frequencies in POMDPs, which is closely related to the general spirit of semialgebraic statistics (Zwiernik, 2016). Based on this we characterize the properties of the optimization problem by its algebraic degree, a concept that has been advanced in recent works on polynomial optimization (Bajaj, 1988; Catanese et al., 2006; Nie & Ranestad, 2009; Draisma et al., 2016; Özlüm Çelik et al., 2021).
Contributions We obtain results for infinite-horizon POMDPs with memoryless stochastic policies under the mean or discounted reward criteria which can be summarized as follows.
1. We show that the state-action frequencies and the expected cumulative reward can be written as fractions of determinantal polynomials in the entries of the stochastic policy matrix. We show that the degree of these polynomials is directly related to the degree of observability (see Theorem 4).
2. We describe the set of feasible state-action frequencies as a basic semialgebraic set, i.e., as the solution set to a system of polynomial equations and inequalities, for which we also derive closed form expressions (see Theorem 16 and Remark 18).
3. We reformulate the expected cumulative reward optimization problem as the optimization of a linear function subject to polynomial constraints (see Remark 19), which we use to solve a navigation problem in a grid world (see Appendix F). This is a POMDP generalization of the dual linear programming formulation of MDPs (Kallenberg, 1994; Puterman, 2014).
4. We present two methods for computing the number of critical points, which rely, respectively, on the rational degree of the expected cumulative reward function and the geometric description of the feasible set of state-action frequencies (see Theorem 20, Proposition 21 and Appendix D).

heading: 2 PRELIMINARIES
text: We use standard notation for probability distributions and Markov kernels. We denote the simplex of probability distributions on a finite set X by ∆X . An element µ ∈ ∆X is a vector in RX with non-negative entries µx = µ(x), x ∈ X adding to one. We denote the set of Markov kernels from a finite set X to another finite set Y by ∆XY . An element Q ∈ ∆XY is a |X | × |Y| row stochastic matrix with entries Qxy = Q(y|x), x ∈ X , y ∈ Y . Given Q(1) ∈ ∆XY and Q(2) ∈ ∆ Y Z we denote their composition into a kernel from X to Z by Q(2) ◦Q(1) ∈ ∆XZ . Given p ∈ ∆X and Q ∈ ∆XY we denote their composition into a joint probability distribution by p ∗ Q ∈ ∆X×Y , (p ∗ Q)(x, y) := p(x)Q(y|x). The support of a vector v ∈ RX is the set supp(v) = {x ∈ X : vx 6= 0}. A partially observable Markov decision process or shortly POMDP is a tuple (S,O,A, α, β, r). We assume that S,O and A are finite sets which we call the state, the observation and the action space respectively. We fix a Markov kernel α ∈ ∆S×AS which we call the transition mechanism and a kernel β ∈ ∆SO which we call the observation mechanism. Further, we consider an instantaneous reward vector r ∈ RS×A. We call the system fully observable if β = id1, in which case the POMDP simplifies to a Markov decision process or shortly MDP.
As policies we consider elements π ∈ ∆OA. Every policy π ∈ ∆OA defines a Markov kernel τ = τπ = π ◦ β ∈ ∆SA which we call the effective policy. Every policy defines transition kernels Pπ ∈ ∆ S×A S×A and pπ ∈ ∆SS through
Pπ(s ′, a′|s, a) := α(s′|s, a)(π ◦ β)(a′|s′) and pπ(s′|s) := ∑ a∈A (π ◦ β)(a|s)α(s′|s, a).
For any initial state distribution µ ∈ ∆S , a policy π ∈ ∆OA defines a Markov process on S ×A with transition kernel Pπ which we denote by Pπ,µ. For a discount rate γ ∈ (0, 1) and γ = 1 we define
Rµγ (π) := EPπ,µ [ (1− γ) ∞∑ t=0 γtr(st, at) ] and Rµ1 (π) := lim T→∞ EPπ,µ [ 1 T T−1∑ t=0 r(st, at) ] ,
called the expected discounted reward and the expected mean reward, respectively. For a policy π we define the value function V πγ ∈ RS via V πγ (s) := Rδsγ (π), s ∈ S, where δs is the Dirac distribution concentrated at s. A short calculation (Zahavy et al., 2021) shows that
Rµγ (π) = ∑ s,a r(s, a)ηπ,µγ (s, a) = 〈r, ηπ,µγ 〉S×A,
where
ηπ,µγ (s, a) :=
{ (1− γ) ∑∞ t=0 γ
tPπ,µ(st = s, at = a), if γ ∈ (0, 1) limT→∞ 1 T ∑T−1 t=0 Pπ,µ(st = s, at = a), if γ = 1.
(1)
Here ηπ,µγ is an element of ∆S×A called the expected (discounted) state-action frequency (Derman, 1970), (discounted) visitation/occupancy measure or on-policy distribution (Sutton & Barto, 2018). Denoting the state marginal of ηπ,µγ by ρ π,µ γ ∈ ∆S , have ηπ,µγ (s, a) = ρπ,µγ (s)(π ◦ β)(a|s). We recall the following well-known facts. 1More generally, the system is fully observable if the supports of {β(·|s)}s∈S are disjoint subsets of O.
Proposition 1 (Existence of state-action frequencies and rewards). Let (S,O,A, α, β, r) be a POMDP, γ ∈ (0, 1] and µ ∈ ∆S . Then ηπ,µγ , ρπ,µγ and Rµγ (π) exist for every π ∈ ∆OA and µ ∈ ∆S and are continuous in γ ∈ (0, 1] for fixed π and µ.
For γ = 1 we work under the following standard assumption in the (PO)MDP literature2. Assumption 2 (Uniqueness of stationary disitributions). If γ = 1, we assume that for any policy π ∈ ∆OA there exists a unique stationary distribution η ∈ ∆S×A of Pπ .
The following proposition shows in particular that for any initial distribution µ, the infinite time horizon state-action frequency ηπ,µγ is the unique discounted stationary distribution of Pπ .
Proposition 3 (State-action frequencies are discounted stationary). Let (S,O,A, α, β, r) be a POMDP, γ ∈ (0, 1] and µ ∈ ∆S . Then ηπ,µγ is the unique element in ∆S×A satisfying
ηπ,µγ = γP T π η π,µ γ + (1− γ)(µ ∗ (π ◦ β)). (2)
Further, ρπ,µγ is the unique element in ∆S satisfying ρ π,µ γ = γp T π ρ π,µ γ + (1− γ)µ.
Since the state-action frequencies satisfy this generalized stationarity condition, we sometimes refer to them as discounted stationary distributions and denote the set of all state-action frequencies in the fully and in the partially observable case by
N µγ := { ηπ,µγ ∈ ∆S×A | π ∈ ∆SA } and N µ,βγ := { ηπ,µγ ∈ ∆S×A | π ∈ ∆OA } .
We have seen that the expected cumulative reward function Rµγ : ∆ O A → R factorises according to
∆OA fβ−→ ∆SA Ψµγ−−→ N µ,βγ → R, π 7→ π ◦ β 7→ ηπ,µγ 7→ 〈r, ηπ,µγ 〉S×A. This is illustrated in Figure 1. We make use of this decomposition in two different ways. First, in Section 3 we study the algebraic properties of the parametrization Ψµγ of the set of state-action frequencies N µ,βγ . In Section 4 we derive a description of N µ,βγ via polynomial inequalities.

heading: 3 THE PARAMETRIZATION OF DISCOUNTED STATE-ACTION FREQUENCIES
text: In this section we show that in POMDPs the discounted state-action frequencies, the value function and the expected cumulative reward are rational functions and relate their rational degree, which can be interpreted as a measure of their complexity, to the degree of observability. Here, we say that a function is a rational function of degree at most k if it is the fraction of two polynomials of degree at most k. First note that by Cramer’s rule (see details in Appendix B.2), it holds that
ηπ,µγ (s, a) = (π ◦ β)(a|s)ρπ,µγ (s) = (π ◦ β)(a|s) · (1− γ) · det(I − γpTπ )µs det(I − γpTπ ) ,
where (I − γpTπ )µs denotes the matrix obtained by replacing the s-row of I − γpTπ with µ. Since pπ is linear in π and the determinant is a polynomial, this is a rational function in the entries of π. For the degree, we show the following result in Appendix B.1. Theorem 4 (Degree of POMDPs). Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1) a discount factor. The state-action frequencies ηπ,µγ and ρπ,µγ , the value function V πγ and the expected cumulative reward R µ γ (π) are rational functions with common denominator in the entries of the policy π. Further, if they are restricted to the subset Π ⊆ ∆OA of policies which agree with a fixed policy π0 on all states outside of O ⊆ O, they have degree at most∣∣{s ∈ S | β(o|s) > 0 for some o ∈ O}∣∣ . Hence the number of states that are compatible with o determines the complexity of the discounted state-action frequencies, the value function and the reward function. Various refinements of the theorem are presented in Appendix B.1. For the mean reward case and under an ergodicity assumption, Grinberg & Precup (2013) showed that the stationary distributions are a rational function of degree of most |S| of the policy. From Theorem 4 we can derive multiple implications (see also Appendix D.5.2 for implications on the optimization landscape):
2Assumption 2 is weaker than ergodicity, for which well known criteria exist. For γ < 1 the assumption is not required, since the discounted stationary distributions are always unique.
Corollary 5 (Feasible state-action frequencies and value functions form semialgebraic sets). Consider a POMDP (S,O,A, α, β, r) and let µ ∈ ∆S be an initial distribution and γ ∈ (0, 1) a discount factor. The set of discounted state-action frequencies and the set of value functions are semialgebraic sets3.
Proof. By Theorem 4, both sets possess a rational and thus a semialgebraic parametrization and are semialgebraic by the Tarski-Seidenberg theorem (Neyman, 2003).
We compute the defining linear and polynomial (in)equalities of the set of feasible state-action frequencies in Section 4 for MDPs and POMDPs respectively, which shows in particular that also in the mean case the state-action frequencies form a semialgebraic set. The special properties of degree-one rational functions, which we elaborate in the Appendix B.3, imply the following results. The first one is a refinement of Dadashi et al. (2019, Lemma 4), stating that linear interpolation between two policies that differ on a single state leads to a linear interpolation of the corresponding value functions. We generalize this to state-action frequencies, explicitly compute the interpolation speed and describe the curves obtained by interpolation between arbitrary policies. Further, our formulation extends to the mean reward case (see Remark 43). Proposition 6. Let (S,A, α, r) be a MDP and γ ∈ (0, 1). Further, let π0, π1 ∈ ∆SA be two policies that differ on at most k states. For any λ ∈ [0, 1] let Vλ ∈ RS and ηµλ ∈ ∆S×A denote the value function and state-action frequency belonging to the policy π0 + λ(π1 − π0) with respect to the discount factor γ, the initial distribution µ and the instantaneous reward r. Then the rational degrees of λ 7→ Vλ and λ 7→ ηλ are at most k. If they differ on at most one state s̃ ∈ S then
Vλ = V0 + c(λ) · (V1 − V0) and ηµλ = η µ 0 + c(λ) · (η µ 1 − η µ 0 ) for all λ ∈ [0, 1],
where
c(λ) = det(I − γp1)λ det(I − γpλ) = det(I − γp1)λ (det(I − γp1)− det(I − γp0))λ+ det(I − γp0) = λ · ρµλ(s̃) ρµ1 (s̃) .
3A semialgebraic set is a set defined by a number of polynomial inequalities or a finite union of such sets; for details see Appendix A.2.
In particular, for a blind controller with two actions the set of feasible value functions and the set of feasible state-action frequencies are pieces of curves with rational parametrization of degree at most k = |S|. By Theorem 4, the cumulative reward of (PO)MDPs is a degree-one rational function in every row of the (effective) policy. Since degree-one rational functions attain their maximum in a vertex (Corollary 39), we immediately obtain the existence of an optimal policy which is deterministic on every observation from which the state can be reconstructed, which has been shown using other methods by Montúfar et al. (2015).
Proposition 7 (Determinism of optimal policies). Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1) a discount factor and let π ∈ ∆OA be an arbitrary policy and denote the set of observations o such that |{s ∈ S | β(o|s) > 0}| ≤ 1 by O. Then there is a policy π̃, which is deterministic on every o ∈ O such that Rµγ (π̃) ≥ Rµγ (π).
Proof. For o ∈ O, the reward function restricted to the o-th component of the policy is a rational function of degree at most one. By Corollary 39 (see Appendix B.3.2), there is a policy π̃, which is deterministic on o and satisfies Rµγ (π̃) ≥ Rµγ (π). Iterating over o ∈ O yields the result.
On observations which can be made from more than one state, bounds on the required stochasticity were established by Montúfar & Rauh (2017); Montúfar et al. (2019).

heading: 4 THE SET OF FEASIBLE DISCOUNTED STATE-ACTION FREQUENCIES
text: In Corollary 5, we have seen that the state-action frequencies form a semialgebraic set. Now we aim to describe its defining polynomial inequalities. In the case of full observability, the feasible stateaction freqencies are known to form a polytope (Derman, 1970; Altman & Shwartz, 1991) which is closely linked to the dual linear programming formulation of MDPs (Hordijk & Kallenberg, 1981), see also Figure 1. We first describe the combinatorial properties of this polytope and then extend the result to the partially observable case, for which we obtain explicit polynomial inequalities induced by the partial observability under a mild assumption. Most proofs are postponed to Appendix C. In Section 5 we discuss how the degree of these defining polynomials allows us to upper bound the number of critical points of the optimization problem. We use the following explicit version of the classic result characterization of the state-action frequencies as a polytope (see Appendix C.1).
Proposition 8 (Characterization of N µγ ). Let (S,A, α, r) be a MDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1]. It holds that
N µγ = ∆S×A ∩ { η ∈ RS×A | ηTwsγ = (1− γ)µs for s ∈ S } (3)
where wsγ := δs ⊗ 1− γα(s|·, ·). For γ ∈ (0, 1), ∆S×A can be replaced by [0,∞)S×A in (3).
Now we turn towards the partially observable case and introduce the following notation.
Definition 9 (Effective policy polytope). We call the set of effective policies τ = π ◦ β ∈ ∆SA the effective policy polytope and denote it by ∆S,βA .
Note that ∆S,βA is indeed a polytope since it is the image of the polytope ∆ O A under the linear mapping π 7→ π ◦ β. Hence, we can write it as an intersection ∆S,βA = ∆SA ∩ U ∩ C, where U , C ⊆ RS×A are an affine subspace and a polyhedral cone and describe a finite set of linear equalities and a finite set of linear inequalities respectively.
Defining linear inequalities of the effective policy polytope Obtaining inequality descriptions of the images of polytopes under linear maps is a fundamental problem that is non-trivial in general. It can be approached algorithmically, e.g., by Fourier-Motzkin elimination, block elimination, vertex approaches, and equality set projection (Jones et al., 2004). In the special case where the linear map is injective, one can give the defining inequalities in closed form as we show in Appendix C.2.1. Hence, for the purpose of obtaining closed-formulas for the effective policy polytope we make the following assumption. However, our subsequent analysis in Section 4 can handle any inequalities.
Assumption 10. The matrix β ∈ ∆SO ⊆ RS×O has linearly independent columns.
Remark 11. The assumption above does not imply that the system is fully observable. Recall that if β has linearly independent columns, the Moore-Penrose takes the form β+ = (βTβ)−1βT . An interesting special case is when β is deterministic but may map several states to the same observation (this is the partially observed setting considered in numerous works). In this case, β+ = diag(n−11 , . . . , n −1 |O|)β
T , where no denotes the number of states with observation o. In this case, β+so agrees with the conditional distribution β(s|o) with respect to a uniform prior over the states; however, this is not in general the case since β+ can have negative entries.
Theorem 12 (H-description of the effective policy polytope). Let (S,O,A, α, β, r) be a POMDP and let Assumption 10 hold. Then it holds that
∆S,βA = ∆ S A ∩ U ∩ C = U ∩ C ∩ D, (4)
where U = {π◦β | π ∈ RS×O} is a subspace, C = {τ ∈ RS×A | β+τ ≥ 0} is a pointed polyhedral cone and D = {τ ∈ RS×A | ∑ a(β
+τ)oa = 1 for all o ∈ O} an affine subspace. Further, the face lattices of ∆OA and ∆ S,β A are isomorphic.
Defining polynomial inequalities of the feasible state-action frequencies In order to transfer inequalities in ∆SA to inequalities in the set of state-action frequencies N µγ , we use that the inverse of π 7→ ηπ is given through conditioning (see Proposition 46) under the following assumption. Assumption 13 (Positivity). Let ρπ,µγ > 0 hold entrywise for all policies π ∈ ∆SA.
Note that this positivity assumption holds in particular, if either α > 0 and γ > 0 or γ < 1 and µ > 0 or entrywise (see Appendix C.1). Using this conditioning principle, we can translate linear inequalities in ∆SA into polynomial inequalities inN µγ . More precisely, we have the following result.
Proposition 14 (Correspondence of inequalities). Let (S,A, α, r) be a MDP, τ ∈ ∆SA and let η ∈ ∆S×A denote its corresponding discounted state-action frequency for some µ ∈ ∆S and γ ∈ (0, 1]. Let c ∈ R, b ∈ RS×A and set S := {s ∈ S | bsa 6= 0 for some a ∈ A}. Then∑
s,a bsaτsa ≥ c implies ∑ s∈S ∑ a bsaηsa ∏ s′∈S\{s} ∑ a′ ηs′a′ − c ∏ s′∈S ∑ a′ ηs′a′ ≥ 0,
where the right is a multi-homogeneous polynomial4 in the blocks (ηsa)a∈A ∈ RA with multi-degree 1S ∈ NS . If further Assumption 13 holds, the inverse implication also holds.
The preceding proposition shows that the state-action frequencies of a linearly constrained policy model, where the constraints only address the policy in individual states form a polytope. However, the effective policy polytope is almost never of this box type (see Remark 55).
Example 15 (Blind controller). For a blind controller the linear equalities defining the effective policy polytope in ∆SA are τs1a − τs2a = τ(a|s1) − τ(a|s2) = 0 for all a ∈ A, s1, s2 ∈ S . They translate into the polynomial equalities ηs1aρs2 − ηs2aρs1 = 0 for all a ∈ A, s1, s2 ∈ S. In the case that A = {a1, a2}, we obtain
0 = ηs1a1(ηs2a1 + ηs2a1)− ηs2a1(ηs1a1 + ηs1a1) = ηs1a1ηs2a2 − ηs1a2ηs2a1 for all s1, s2 ∈ S,
which is precisely the condition that all 2 × 2 minors of η vanish. Hence, in this case the set of state-action frequencies N µ,βγ is given as the intersection of N µγ of state-action frequencies of the associated MDP and the determinantal variety D1 of rank one matrices.
Now we present a general result concerning the semialgebraic structure of the set of feasible stateaction frequencies.
Theorem 16. Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S and γ ∈ (0, 1] and assume that Assumption 13 holds. Then we have N µ,βγ = N µγ ∩ V ∩ B, where V is a variety described by multi-homogeneous polynomial equations and B is a basic semialgebraic set described by multihomogeneous polynomial inequalities. Further, the face lattices of ∆S,βA and N µ,βγ are isomorphic.
4A polynomial p : Rn1×· · ·×Rnk → R is called multi-homogeneous with multi-degree (d1, . . . , dk) ∈ Nk, if it is homogeneous of degree dj in the j-th block of variables for j = 1, . . . , k.
Remark 17. The variety V corresponds to the subspace U and the basic semialgebraic set B to the cone C from (4). Further, closed form expressions for the defining polynomials can be computed using Proposition 14 (see also Remark 18). The statement about isomorphic face lattices is in the sense that ∆S,βA and N µ,βγ have the same number of surfaces of a given dimension with the same neighboring properties. This can be seen in Figure 1, where the effective policy polytope and the set of state-action frequencies both have four vertices, four edges, and one two-dimensional face.
Remark 18. By Theorem 12 and Proposition 14, the defining polynomials of the basic semialgebraic set B from Theorem 16 are indexed by a ∈ A, o ∈ O and are given by
pao(η) := ∑ s∈So ( β+osηsa ∏ s′∈So\{s} ∑ a′ ηs′a′ ) = ∑ f : So→A ( ∑ s′∈f−1({a}) β+os′ ) ∏ s∈So ηsf(s) ≥ 0, (5)
where So := {s ∈ S | β+os 6= 0}. The polynomials depend only on β and not on γ, µ nor α, and have |So||A||So|−1 monomials of degree |So| of the form ∏ s∈So ηsf(s) for some f : So → A. In particular, we can read of the multi-degree of pao with respect to the blocks (ηsa)a∈A which is given by 1So (see also Proposition 14). A complete description of the set N µ,βγ via (in)equalities follows from the description of N µγ via linear (in)equalities given in (3). In Section 5 we discuss how the degree of these polynomials controls the complexity of the optimization problem. Remark 19 (Planning in POMDPs as a polynomial optimization problem). The semialgebraic description of the set N µ,βγ of feasible state-action distributions allows us to reformulate the reward maximization as a polynomially constrained optimization problem with linear objective (see also Remark 58 and Algorithm 1). This reformulation allows the use of polynomial optimization algorithms, which we demonstrate in Appendix F on the toy example of Figure 1 and a grid world.

heading: 5 NUMBER AND LOCATION OF CRITICAL POINTS
text: Although the reward function of MDPs is non convex, it still exhibits desirable properties from a standpoint of optimization. For example, without any assumptions, every policy can be continuously connected to an optimal policy by a path along which the reward is monotone (see Appendix D.5). Under mild conditions, all policies which are critical points of the reward function are globally optimal (Bhandari & Russo, 2019). In partially observable systems, the situation is fundamentally different. In this case, suboptimal local optima of the reward function can exist as can be seen in Figure 1 (see also Poupart et al., 2011; Bhandari & Russo, 2019). In the following we use the geometry description of the discounted state-action frequencies to bound the number and location of critical points. These are important properties of the optimization problem and have implications on the required stochasticity of optimal policies. In Appendix D we discuss the mean reward case and an example. In Appendix D.5.2 we describe the sublevelsets as semialgebraic sets.
We regard the reward as a linear function p0 over the set of feasible state-action frequencies N µ,βγ . Since under Assumption 13 π 7→ ηπ is injective and has a full-rank Jacobian everywhere (see Appendix C.1.1), the critical points in the policy polytope ∆OA correspond to the critical points of p0 on N µ,βγ (see Trager et al., 2019). In general, critical points of this linear function can occur on every face of the semialgebraic set N µ,βγ . The optimization problem thus has a combinatorial and a geometric component, corresponding to the number of faces of each dimension and the number of critical points in the relative interior of any given face. We have discussed the combinatorial part in Theorem 16 and focus now on the geometric part. WritingN µ,βγ = {η ∈ RS×A | pi(η) ≤ 0, i ∈ I}, we are interested in the number of critical points on the interior of a face,
int(FJ) = {η ∈ N µ,βγ | pj(η) = 0 for j ∈ J, pi(η) > 0 for i ∈ I \ J}. Note that a point η ∈ int(FJ) is critical, if and only if it is a critical point on the variety
VJ := {η ∈ RS×A | pj(η) = 0 for j ∈ J}. For the sake of notation we write J = {1, . . . ,m}. We can bound the number of critical points in the interior of the face by the number of critical points of the polynomial optimization problem for p0(η) subject to p1(η) = · · · = pm(η) = 0. This number is upper bounded by the algebraic degree of the problem which controls also the (algebraic) complexity of optimal policies (see Appendix D.1 for details). Using Theorem 12, Proposition 14 and an upper bound on the algebraic degree of polynomial optimization by Nie & Ranestad (2009) yields the following result.
Theorem 20. Consider a POMDP (S,O,A, α, β, r), γ ∈ (0, 1), assume that r is generic, that β ∈ RS×O is invertible, and that Assumption 13 holds. For any given I ⊆ A × O consider the following set of policies, which is the relative interior of a face of the policy polytope:
int(F ) = { π ∈ ∆OA | π(a|o) = 0 if and only if (a, o) ∈ I } .
Let O := {o ∈ O | (a, o) ∈ I for some a} and set ko := |{a | (a, o) ∈ I}| as well as do := |{s | β+os 6= 0}|. Then, the number of critical points of the reward function on int(F ) is at most(∏
o∈O dkoo
) ·
∑ ∑ o∈O io=l ∏ o∈O (do − 1)io , (6)
where l = |S|(|A| − 1) − |I|. If α and µ are generic, this bound can be refined by computing the polar degrees of multi-homogeneous varieties (see Proposition 21 for a special case). The same bound holds in the mean reward case γ = 1 for l given in Remark 61.
By results from Montúfar & Rauh (2017) a POMDP has optimal memoryless stochastic policies with | suppπ(·|o)| ≤ lo, where lo = |suppβ(o|·)| ≥ 1. Hence, we may restrict attention to optimization overN µ,βγ with k = ∑ o∈O ko active inequalities (zeros in the policy), where ko = max{|A|−lo, 0}. Over these faces of the feasible set, the algebraic degree of the reward maximization problem is upper bounded by ∏ o∈O d ko o ∑ i1+···+io=|S|(|A|−1)−k ∏ o∈O(do − 1)io due to Theorem 20.
In the special case of MDPs the bound shows that for MDPs only deterministic policies can be critical points of the reward function (see Corollary 62). Setting I := ∅ shows that there are no critical points in the interior of the policy polytope ∆OA. This requires the assumption that β is invertible (see Appendix D.4). The bound in Theorem 20 neglects the specific algebraic structure of the problem, and can be refined by considering polar degrees of determinantal varieties. This yields the following tighter upper bound for a blind controller with two actions (see Appendix D.3). Proposition 21 (Number of critical points in a blind controller). Let (S,O,A, α, β, r) be a POMDP describing a blind controller with two actions, i.e., O = {o} and A = {a1, a2} and let r, α and µ be generic and let γ ∈ (0, 1). Then the reward function Rµγ has at most |S| critical points in the interior int(∆OA) ∼= (0, 1) of the policy polytope and hence at most |S|+ 2 critical points.
In Appendix D.4 we provide examples of blind controllers which have several critical points in the interior (0, 1) ∼= int(∆OA) and strict maxima at the two endpoints of the interval [0, 1] ∼= ∆OA respectively. Such points are called smooth and non-smooth critical points respectively.

heading: 6 CONCLUSION
text: We described the geometry and algebraic properties of POMDPs and related the rational degree of the discounted state-action frequencies and the expected cumulative reward function to the degree of observability. We described the set of feasible state-action frequencies as a basic semialgebraic set, computed explicit expressions for the defining polynomials. In particular, this yields a polynomial programming formulation of POMDPs extending the linear programming formulation of MDPs. Based on this and the notion of algebraic degree from polynomial optimization theory, we bounded the number of critical points of the reward function over the polytope of memoryless stochastic policies. Our analysis also yields insights into the optimization landscape, such as the number of connected components of superlevel sets of the expected reward. Finally, we use a navigation problem in a grid world to demonstrate that the polynomial programming formulation can offer a computationally feasible approach to the reward maximization problem.
Our analysis focuses on infinite-horizon problems and memoryless policies with finite state, observation, and action spaces. Continuous spaces are interesting avenues, since they occur in real world application like robotics. The general bound on the number of critical points in Theorem 20 does not exploit the special multi-homogeneous structure of the problem, which could allow for tighter bounds as illustrated in Proposition 21 for blind controllers. Computing polar degrees is a challenging problem that remains to be studied using more sophisticated algebraic tools. Possible extensions of our work include the generalization to policies with finite memories as sketched in Appendix E.1. Further, we believe that it is interesting to explore to what extend our results can be used to identify policy classes guaranteed to contain maximizers of the reward in POMDPs.

heading: APPENDIX
text: The Sections A–D of the Appendix correspond to the Sections 2–5 of the main body. We present the postponed proofs and elaborate various remarks in more detail. In Appendix E we discuss possible extensions of our results to memory policies and polynomial POMDPs. In Appendix F we provide details on the example plotted in Figure 1 and provide a plot of a three dimensional state-action frequency set.

heading: A Details on the Preliminaries 15
text: A.1 Partially observable Markov decision processes . . . . . . . . . . . . . . . . . . . 15
A.2 Semialgebraic sets and their face lattices . . . . . . . . . . . . . . . . . . . . . . . 16

heading: B Details on the Parametrizaton of Discounted State-Action Frequencies 16
text: B.1 The degree of determinantal polynomials . . . . . . . . . . . . . . . . . . . . . . 16
B.2 The degree of POMDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
B.3 Properties of degree-one rational functions . . . . . . . . . . . . . . . . . . . . . . 19

heading: C Details on the Geometry of State-Action Frequencies 21
text: C.1 The fully observable case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
C.2 The partially observable case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

heading: D Details on the Optimization 29
text: D.1 Introduction to algebraic degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
D.2 General upper bound on the number of critical points . . . . . . . . . . . . . . . . 31
D.3 Number of critical points in a two-action blind controller . . . . . . . . . . . . . . 33
D.4 Examples with multiple smooth and non-smooth critical points . . . . . . . . . . . 35
D.5 (Super)level sets of (PO)MDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

heading: E Possible Extensions 37
text: E.1 Application to finite memory policies . . . . . . . . . . . . . . . . . . . . . . . . 37
E.2 Polynomial POMDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

heading: F Examples 37
text: F.1 Toy example of Figure 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
F.2 Navigation in a grid world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
F.3 A three dimensional example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

heading: A DETAILS ON THE PRELIMINARIES
text: We elaborate the proofs that where ommited or only sketched in the main body.

heading: A.1 PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES
text: The statement of Proposition 1 can found in the work by Howard (1960) and we quickly sketch the proof therein. In order to show that the expected state-action frequencies exist without any assumptions, we recall that for a (row or column) stochastic matrix P , the Cesàro mean is defined by
P ∗ := lim T→∞
1
T T−1∑ t=0 P t
and exists without any assumptions. Further, P ∗ is the projection onto the subspace of stationary distribution (Doob, 1953). For γ ∈ (0, 1), the matrix
P ∗γ := (1− γ) ∞∑ t=0 γtP t = (1− γ)(I − γP )−1
is known as the Abel mean of P , where we used the Neumann series. By the Tauberian theorem, it holds that P ∗γ → P ∗ for γ ↗ 1 (Gillette, 1958; Hunter, 1983). Proposition 1 (Existence of state-action frequencies and rewards). Let (S,O,A, α, β, r) be a POMDP, γ ∈ (0, 1] and µ ∈ ∆S . Then ηπ,µγ , ρπ,µγ and Rµγ (π) exist for every π ∈ ∆OA and µ ∈ ∆S and are continuous in γ ∈ (0, 1] for fixed π and µ.
Proof. The existence of the state-action frequencies as well as the continuity with respect to the discount parameter follows directly from the general theory since
ηπ,µγ = (P T π ) ∗ γ(µ ∗ (π ◦ β))
for γ ∈ (0, 1) and ηπ,µ1 = (PTπ )∗(µ ∗ (π ◦ β)). With an analogue argument, the statement follows for the state frequencies and for the reward.
For γ = 1 we work under the following standard assumption in the (PO)MDP literature5. Assumption 2 (Uniqueness of stationary disitributions). If γ = 1, we assume that for any policy π ∈ ∆OA there exists a unique stationary distribution η ∈ ∆S×A of Pπ .
The following proposition shows in particular that for any initial distribution µ, the infinite time horizon state-action frequency ηπ,µ1 is the unique stationary distribution of Pπ . Proposition 3 (State-action frequencies are discounted stationary). Let (S,O,A, α, β, r) be a POMDP, γ ∈ (0, 1] and µ ∈ ∆S . Then ηπ,µγ is the unique element in ∆S×A satisfying
ηπ,µγ = γP T π η π,µ γ + (1− γ)(µ ∗ (π ◦ β)). (2)
Further, ρπ,µγ is the unique element in ∆S satisfying ρ π,µ γ = γp T π ρ π,µ γ + (1− γ)µ.
Proof. By the general theory of Cesàro means, (PTπ ) ∗ projects onto the space of stationary distributions and hence the ηπ,µ1 = (P T π ) ∗(µ ∗ (π ◦ β)) is stationary. Hence, by Assumption 2, ηπ,µ1 is the unique stationary distribution. For γ ∈ (0, 1) we have
ηπ,µγ = (P T π ) ∗ γ(µ ∗ (π ◦ β)) = (I − γPTπ )−1(µ ∗ (π ◦ β)),
which yields the claim. For the state distributions ρπ,µγ the claim follows analogously or by marginalisation.
5Assumption 2 is weaker than ergodicity and is satisfied whenever the Markov chain with transition kernel Pπ is irreducible and aperiodic for every policy π, e.g., when the transition kernel satisfies α > 0. For γ ∈ (0, 1) the assumption is not required, since the discounted stationary distributions are always unique since I − γPπ is invertible because the spectral norm of Pπ is one.

heading: A.2 SEMIALGEBRAIC SETS AND THEIR FACE LATTICES
text: We recall the definition of semialgebraic sets, which are fundamental objects in real algebraic geometry (Bochnak et al., 2013). A basic (closed) semialgebraic set A is a subset of Rd defined by finitely many polynomial inequalities as
A = {x ∈ Rd | pi(x) ≥ 0 for i ∈ I},
where I is a finite index set and the pi are polynomials. A semialgebraic set is a finite union of basic (not necessarily closed) semialgebraic sets, and a function is called semialgebraic if its graph is semialgebraic. By the Tarski-Seidenberg theorem the range of a semialgebraic function is semialgebraic. A simple algebraic set has a lattice associated to it, induced by the set of active inequalities. More precisely, for a subset J ⊆ I we set FJ := {x ∈ A | pj(x) = 0 for j ∈ J} and endow the set F := {FJ | J ⊆ I} with the partial order of inclusion. We call the elements of F the faces of A. The faces described above are a generalization of the faces of a classical polytope and a special case of the faces of an abstract polytope and we refer to McMullen & Schulte (2002) for more details. Next, we want to endow this partially ordered set with more structure. A lattice F carries two operations, the join ∧ and the meet ∨, which satisfy the absortion laws F ∨ (F ∧G) = F and F ∧ (F ∨G) = F for all F,G ∈ F . In the face lattice of a basic semialgebraic set, the join and meet are given by
F ∧G := F ∩G and F ∨G := ⋂
H∈F : F,G⊆H
H.
A morphism between two lattices F and G is a mapping ϕ : F → G that respects the join and the meet, i.e., such that ϕ(F ∧ G) = ϕ(F ) ∧ ϕ(G) and ϕ(F ∨ G) = ϕ(F ) ∨ ϕ(G) for all F,G ∈ F . A lattice isomorphism is a bijective lattice morphism where the inverse is also a morphism. We say that two basic semialgebraic sets with isomorphic face lattice are combinatorially equivalent.

heading: B DETAILS ON THE PARAMETRIZATON OF DISCOUNTED STATE-ACTION FREQUENCIES

heading: B.1 THE DEGREE OF DETERMINANTAL POLYNOMIALS
text: Determinantal representation of polynomials play an important role in convex geometry (see for example Helton & Vinnikov, 2007; Netzer & Thom, 2012), but often the emphasis is put on symmetric matrices. We adapt those arguments to the general case and present them here. We call p a determinantal polynomial if it admits a representation
p(x) = det ( A0 +
m∑ i=1 xiAi
) for all x ∈ Rm, (7)
for some A0, . . . , Am ∈ Rn×n. Let us use the notations
A(x) := A0 + m∑ i=1 xiAi and B(x) := m∑ i=1 xiAi.
Proposition 22 (Degree of monic univariate determinantal polynomials). Let A,B ∈ Rn×n and A be invertible and let λ1, . . . , λn ∈ C denote the eigenvalues of A−1B if repeated according to their algebraic multiplicity. Then,
p : R→ R, t 7→ det(A+ tB)
is a polynomial of degree deg(p) = ∣∣{j ∈ {1, . . . , n} | λj 6= 0}∣∣ ≤ rank(B).
The roots of p are given by {−λ−1j | j ∈ J} ⊆ C. If further A−1B is symmetric, then we have deg(p) = rank(B).
Proof. Let J ⊆ {1, . . . , n} denote the set of indices j such that λj 6= 0. For x 6= 0 we have6
p(t) = det(A) det(I + tA−1B) = xn det(A) det(A−1B + t−1I) = xn det(A)χA−1B(−t−1)
= tn n∏ i=1 (−t−1 − λi) = (−1)n−|J| · ∏ j∈J (−λj) · ∏ j∈J ( t+ λ−1j ) ,
which is a polynomial of degree |J |. Note that |J | is upper bounded by the complex rank of A−1B. Since the rank over C and R agree for a real matrix, we have deg(p) ≤ rank(A−1B) = rank(B). Assume now that A−1B is symmetric, then the rank of A−1B coincides with the number |J | of non zero eigenvalues. Further, the rank of B and A−1B is the same.
Remark 23. Note that the degree of p can be lower than rank(B), for example if A = I and B = (
1 −1 1 −1
) = ( 1 1 ) (1 −1) .
Then we have rank(B) = 1, but
p(λ) = det ( 1 + λ −λ λ 1− λ ) = (1 + λ)(1− λ) + λ2 = 1
and therefore deg(p) = 0. Note that in this case A−1B = B has no non-zero eigenvalues.
Now we show that the degree of p is still bounded by rank(B) even if A is not invertible. However, we loose an explicit description of the degree in this case.
Proposition 24 (Degree of univariate determinantal polynomials). Let A,B ∈ Rn×n and consider the polynomial p : R→ R, t 7→ det(A+ tB). Then either p = 0 or if p(t0) 6= 0 and λ1, . . . , λn ∈ C denote the eigenvalues of (A + t0B)−1B repeated according to their algebraic multiplicity, then p has degree
deg(p) = ∣∣{j ∈ {1, . . . , n} | λj 6= 0}∣∣ ≤ rank(B).
In particular, it always holds that deg(p) ≤ rank(B).
Proof. Let without loss of generality p(t0) 6= 0, then C = A+ t0B is invertible. By Proposition 22, the degree of q(t) = det(C + tB) is precisely |{j | λj 6= 0}|. Noting that p(t) = q(t − t0) yields the claim.
The following result generalizes Proposition 24 to multivariate determinantal polynomials.
Proposition 25 (Degree of determinantal polynomials). Let p : Rm → R be a determinantal polynomial with the representation (7). Then
deg(p) ≤ max { rank(B(x)) | x ∈ Rm } .
Proof. Let us fix x ∈ Rm and for t ∈ R set f(t) := p(tx) = det(A0 + tB(x)). By the next proposition it suffices to show that deg(f) ≤ rank(B(x)). However, this is precisely the statement of Proposition 24.
Proposition 26 (Degree of polynomials). Let p : Rn → R be a polynomial. Then there is a direction x ∈ Rn such that t 7→ p(tx) is a polynomial of degree deg(p). Moreover, for any x ∈ Rn, the univariate polynomial t 7→ p(tx) has degree at most deg(p).
Proof. Let without loss of generality p be non trivial. Decompose p into its leading and lower order terms p = p1 + p2 and choose x ∈ Rn such that p1(x) 6= 0. Let k := deg(p), then we have p1(tx) = t
kp1(x) for all µ ∈ R. Since the degree of t 7→ p2(tx) is at most k − 1, the degree of t 7→ p(tx) = p1(tx) + p2(tx) is k.
6Here, χC(λ) = det(C − λI) denotes the characteriztic polynomial of a matrix C.
Remark 27. Analogue to the univariate case, it is possible to give a precise statement on the degree, which is the following. If p is not vanishing and x0 ∈ Rm is such that p(x0) 6= 0, then A(x0) ∈ Rn×n is invertible. Writing λ1(x), . . . , λn(x) ∈ C for the eigenvalues of A(x0)−1B(x) and J(x) for the indices j such that λj(x) 6= 0 we obtain
deg(p) = max { |J(x)| | x ∈ Rm } .

heading: B.2 THE DEGREE OF POMDPS
text: The general bounds on the degree of determinantal polynomials directly implies Theorem 4, which we state again for the sake of convenience here. Theorem 4 (Degree of POMDPs). Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1) a discount factor. The state-action frequencies ηπ,µγ and ρπ,µγ , the value function V πγ and the expected cumulative reward R µ γ (π) are rational functions with common denominator in the entries of the policy π. Further, if they are restricted to the subset Π ⊆ ∆OA of policies which agree with a fixed policy π0 on all states outside of O ⊆ O, they have degree at most∣∣{s ∈ S | β(o|s) > 0 for some o ∈ O}∣∣ . In fact, the results from the preceding pararaph imply the following sharper versions. Theorem 28 (Degree of discounted state-action frequencies of POMDPs). Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1) a discount factor. Then the discounted state-action distributions can be expressed as
ηπ,µγ (s, a) = qs,a(π)
q(π) for every π ∈ ∆OA and s ∈ S, (8)
where
qs,a(π) := (π ◦ β)(a|s) · (1− γ) · det(I − γpTπ )µs and q(π) := det(I − γpTπ ) are polynomials in the entries of the policy. Further, if qs,a and q are restricted to the subset Π ⊆ ∆OA of policies which agree with a fixed policy π0 on all states outside of O ⊆ O and if we set S := {s ∈ S | β(o|s) > 0 for some o ∈ O}, then they have degree at most
deg(qs,a) ≤ max π∈Π rank(pTπ − pTπ0) 0 s + 1S(s) ≤ |S| (9)
and deg(q) ≤ max
π∈Π rank(pTπ − pTπ0) ≤ |S| . (10)
Proof. Recall that we have ηπ,µγ (s, a) = (π ◦ β)(a|s)ρπ,µγ (s).
Further, by Proposition 3, the state distribution is given by ρπ,µγ = (1− γ)(1− γpTπ )−1µ. Applying Cramer’s rule yields
ρπ,µγ (s) = det(I − γpTπ )µs det(I − γpTπ ) ,
where (I − γpTπ )µs denotes the matrix obtained by replacing the s-th row of I − γpTπ with µ, which shows (8). For the estimates on the degree, we note that
deg(qs,a) ≤ deg(I − γpTπ )µs + 1S(s).
Further, we can use Proposition 25 to estimate the degree over a subset Π ⊆ ∆SA of policies which agree with a fixed policy π0 on all states outside of O ⊆ O. We obtain
deg(I − γpTπ )µs ≤ max π∈Π rank((I − γpTπ0) µ s − (I − γpTπ )µs ) = max π∈Π rank γ(pTπ − pTπ0) 0 s,
which shows the first estimate in (9). To see the second inequality, we first assume that s ∈ S. Then (pTπ − pTπ0) 0 s has at most |S| − 1 non zero columns and hence rank at most |S| − 1. If s /∈ S, then with the same argument, the rank of (pTπ − pTπ0) 0 s = p T π − pTπ0 is at most |S| and the second estimate in (9) holds in both cases. The estimates in (10) follow with completely analoguous arguments.
Remark 29. The polynomial q is independent of the initial distribution µ, whereas the polynomials qs,a and therefore also their degrees depend on µ. Further, Proposition 24 contains an exact expressions for the degree of the polynomials qs,a and q depending on the eigenvalues of certain matrices. Corollary 30 (Degree of the reward and value function). Theorem 28 also yields the rational degree of the reward and value function. Indeed, it holds that7
Rµγ (π) =
∑ s,a r(s, a)qs,a(π)
q(π) = (1− γ) · det(I − γpπ + rπ ⊗ µ) det(I − γpπ) − 1 + γ,
where we used the matrix determinant lemma (Vrabel, 2016), and
V πγ (s) = det(I − γpπ + rπ ⊗ δs)
det(I − γpπ) − 1 + γ.
The degree of their denominator is bounded by (10). The degree of the numerator of V πγ (s) is bounded by (9). Finally, the degree of the numerator of the reward Rµγ is bounded by the maximum degree of the numerators of V πγ (s) over the support of µ. An explicit formula for the rational degrees can be deduced from Remark 27.
Corollary 31 (Degree of curves). Let (S,A, α, r) be a MDP, µ ∈ ∆S be an initial distribution, γ ∈ (0, 1) a discount factor and r ∈ RS×A. Further, let π0, π1 ∈ ∆SA be two policies that disagree on k states. Let ηλ and Vλ denote the discounted state-action frequencies and the value function belonging to the policy πλ := π0 + λ(π1 − π0). Then both λ 7→ ηλ and λ 7→ V λ are rational functions of degree at most k.

heading: B.3 PROPERTIES OF DEGREE-ONE RATIONAL FUNCTIONS

heading: B.3.1 A LINE THEOREM FOR DEGREE-ONE RATIONAL FUNCTIONS
text: First, we notice that certain degree-one rational functions map lines to lines which implies that they map polytopes to polytopes. Further, the extreme points of the range lie in the image of the extreme points which implies that degree-one rational functions are maximized in extreme points – just like linear functions. Definition 32. We say that a function f : Ω → Rm is a rational function of degree at most k with common denominator if it admits a representation of the form fi = pi/q for polynomials pi and q of degree at most k. Remark 33. We have seen that the state-action frequencies, the reward function and the value function of POMDPs are rational functions of degree at most |S| with common denominator. In the case of MDPs and if a policy is fixed on all but k states, it is a rational function with common denominator of degree at most k. Proposition 34. Let Ω ⊆ Rd be convex and f : Ω → Rm be a rational function of degree at most one with common denominator and the representation fi(x) = pi(x)/q(x) for affine linear functions pi, q. Then, f maps lines to lines. More precisely, if x0, x1 ∈ Ω, then
c : [0, 1]→ [0, 1], λ 7→ q(x1)λ q(xλ) = q(x1)λ (q(x1)− q(x0))λ+ q(x0)
is strictly increasing and satisfies
f((1− λ)x0 + λx1) = (1− c(λ))f(x0) + c(λ)f(x1) = f(x0) + c(λ)(f(x1)− f(x0)). (11)
Further, c is strictly convex if |q(x1)| < |q(x0)|, strictly concave if |q(x1)| > |q(x0)| and linear if |q(x0)| = |q(x1)|.
Proof. We set xλ := (1− λ)x0 + λx1 and by explicit computation we obtain
f(xλ) = p(xλ)
q(xλ) = (1− λ)p(x0) + λp(x1) q(xλ) = (1− λ)q(x0) q(xλ) · f(x0) + λq(x1) q(xλ) · f(x1).
7Here, u⊗ v := uvT denotes the Kronecker product.
Noting that λq(x1)
q(xλ) =
λq(x1)
(1− λ)q(x0) + λq(x1) = c(λ)
and (1− λ)q(x0)
q(xλ) + λq(x1) q(xλ) = (1− λ)q(x0) + λq(x1) q(xλ) = 1
yields (11). Finally, we differentiate and obtain
c′(λ) = q(x0)q(x1)
q(xλ)2 . (12)
Since q has no root in Ω it follows that q(x0) and q(x1) have the same sign and hence c′(λ) > 0. Differentiating a second time yields
c′′(λ) = −2q(x0)q(x1)(q(x1)− q(x0)) · q(xλ)−3.
Using that sgn(q(xλ)) = sgn(q(x0)) = sgn(q(x1)) yields the assertion.
Remark 35. The formula (11) holds for all λ ∈ R for which xλ = λx0 + (1− λ)x1 ∈ Ω. Proposition 36 (Level sets of degree one rational functions). Let Ω ⊆ Rd be convex and f : Ω→ R be a rational function of degree at most one. Then, Lα := {x ∈ Ω | f(x) = α} is the intersection of an affine space with Ω.
Proof. For x, y ∈ Lα the ray {x+ t(y−x) | t ∈ R}∩Ω is contained in Lα by the line theorem.

heading: B.3.2 EXTREME POINTS OF DEGREE-ONE RATIONAL FUNCTIONS
text: It is well known that linear functions obtain their maxima on extreme points. We show that this is also the case for rational functions of degree at most one.
Definition 37. Let Ω ⊆ Rd. Then we call x ∈ Ω an extreme point of Ω if x is not the strict convex combination of two other points in Ω, i.e., if x = (1 − λ)x0 + λx1 for x0, x1 ∈ Ω and λ ∈ (0, 1) implies x0 = x1 = x. We denote the set of extreme points of Ω by extr(Ω).
Proposition 38. Let Ω ⊆ Rd be convex and f : Ω → Rm be a rational function of degree at most one with common denominator. Then f(Ω) is convex and we have extr(f(Ω)) ⊆ f(extr(Ω)).
Proof. Let y0 = f(x0), y1 = f(x1) ∈ f(Ω). Then by the line theorem, the line connecting y0 and y1 agrees with the image of the line connecting x0 and x1 under f , in particular, it is contained in f(Ω) which shows the convexity of f(Ω). Pick now an extreme point y = f(x) ∈ extr(f(Ω)). If x ∈ extr(Ω), there is nothing to show, so let x /∈ extr(Ω). Then by the Carathéodory theorem we can write x as a strict convex combination ∑n i=1 λixi, λi > 0, n ≥ 2 for some extreme points xi ∈ extr(Ω). In particular, it is possible to write x as the strict convex combination x = (1−λ)x0 +λx1 by setting x0 := ∑n i=2 λixi. Now, by the line theorem we have
y = (1− c(λ))f(x0) + c(λ)f(x1),
where c(λ) ∈ (0, 1). Since y is an extreme point, this implies f(x0) = f(x1) = y. In particular, this shows that y = f(x1) ∈ f(extr(Ω)).
Corollary 39 (Maximizers of degree-one rational functions). Let Ω ⊆ Rd be a convex and compact set and let f : Ω→ R be a rational function of degree at most one with common denominator. Then f is maximized in at least one extreme point of Ω. In particular, if Ω is a polytope, f is maximized in at least one vertex.
Proof. Since Ω is compact and f is continuous, f(Ω) is a compact interval, lets say f(Ω) = [α, β]. By the preceding proposition we have {α, β} = extr(f(Ω)) ⊆ f(extr(Ω)), which shows that f is maximized in at least one extreme point.
Corollary 40. Let P ⊆ Rd be a polytope and f : Ω→ Rm be a rational function of degree at most one with common denominator. Then f(P ) is a polytope and we have vert(f(P )) ⊆ f(vert(P )).
Proof. By the preceding proposition, f(P ) is convex. Further, f(P ) has finitely many extreme points since extr(f(P )) ⊆ f(extr(P )) = f(vert(P )), which implies the assertion.
Proposition 41. Let f : P → Rm be defined on the Cartesian product P = P1 × · · · × Pk of polytopes, which is a degree-one rational function with common denominator whenever all but one components are fixed. Then f(P ) has finitely many extreme points and it holds that
extr(f(P )) ⊆ f(vert(P )) = f(vert(P1)× · · · × vert(Pk)). In particular, if m = 1 this shows that f is maximized in at least one vertex of P .
Proof. Let now x = (x(1), . . . , x(k)) ∈ P1 × · · · × Pk be such that f(x) ∈ extr(f(P )). If x(i) ∈ vert(Pi), there is nothing to show. Hence, we assume that x(i) /∈ vert(Pi). Let us denote the restriction of f onto Pi by g, where we keep the other components fixed to be x(j). Then we have g(x(i)) ∈ extr(g(Pi)) and hence by Proposition 38 there is x̃(i) ∈ vert(Pi) such that g(x̃(i)) = g(x(i)) = f(x). Replacing x(i) by x̃(i) and iterating over i yields the claim.
Remark 42. We have seen that both the value function as well as the discounted state-action frequencies are degree-one rational functions in the rows of the policy in the case of full observability. Hence, the extreme points of the set of all value functions and of the set of discounted state-action frequencies are described by the proposition above. In fact we will see later that the discounted state-action frequencies form a polytope; further, one can show that the set of value functions is a finite union of polytopes (see Dadashi et al., 2019).
B.3.3 IMPLICATIONS FOR POMDPS
Proposition 6. Let (S,A, α, r) be a MDP and γ ∈ (0, 1). Further, let π0, π1 ∈ ∆SA be two policies that differ on at most k states. For any λ ∈ [0, 1] let Vλ ∈ RS and ηµλ ∈ ∆S×A denote the value function and state-action frequency belonging to the policy π0 + λ(π1 − π0) with respect to the discount factor γ, the initial distribution µ and the instantaneous reward r. Then the rational degrees of λ 7→ Vλ and λ 7→ ηλ are at most k. If they differ on at most one state s̃ ∈ S then
Vλ = V0 + c(λ) · (V1 − V0) and ηµλ = η µ 0 + c(λ) · (η µ 1 − η µ 0 ) for all λ ∈ [0, 1],
where
c(λ) = det(I − γp1)λ det(I − γpλ) = det(I − γp1)λ (det(I − γp1)− det(I − γp0))λ+ det(I − γp0) = λ · ρµλ(s̃) ρµ1 (s̃) .
Proof. This is a direct consequence of Proposition 34 and Theorem 4.
Remark 43. The proposition above describes the interpolation speed λ · ρµλ(s̃)/ρ µ 1 (s̃) in terms of the discounted state distribution in s̃. This expressions extends to the case of mean rewards – note that the determinants vanish – and the theorem can be shown to hold in this case as well, if we set 0/0 := 0. Note that the interpolation speed does not depend on the initial condition µ. Remark 44. Refinements on the upper bound of the rational degree of λ 7→ Vλ and λ 7→ ηλ can be obtained using Proposition 24. Indeed, if we write ηλ(s, a) = qsa(λ)/q(λ) like in Theorem 28 those degrees can be upper bounded by
deg(qsa) ≤ rank(p1 − p0)0s + 1S(s) ≤ rank(p1 − p0) and deg(q) ≤ rank(p1 − p0), where S ⊆ S is the set of states on which the two policies differ; see also the proof of Theorem 28 for more details on an analogue argument. Hence, the degree of the two curves λ 7→ Vλ and λ 7→ ηλ is upper bounded by rank(p1 − p0).

heading: C DETAILS ON THE GEOMETRY OF STATE-ACTION FREQUENCIES
text: The set of all state-action frequencies is known to be a polytope in the fully observable case (Derman, 1970) and we show that it is combinatorially equivalent to the conditional probability polytope ∆SA. We show that in the partially observable case the set of feasible state-action frequencies is cut out from this polytope by a finite set of polynomial inequalities. We discuss the special structure of those polynomials and give closed form expressions for them.

heading: C.1 THE FULLY OBSERVABLE CASE
text: Let νπ,µγ ∈ ∆S×S denote the expected number of transitions from s to s′ given by
(1− γ) ∞∑ t=0 γtPπ,µ(st = s, st+1 = s′) and lim T→∞ 1 T T−1∑ t=0 Pπ,µ(st = s, st+1 = s′)
respectively. Note that we have
νπ,µγ (s, s ′) = ∑ a∈A ηπ,µγ (s, a)α(s ′|s, a), (13)
hence νπ,µγ is the image of η π,µ γ under the linear transformation
fα : ∆S×A → ∆S×S , η 7→ (∑ a∈A η(s, a)α(s′|s, a) ) s,s′∈S . (14)
Therefore, we can hope to obtain a characterization ofN µγ using this mapping. In order to do so, we would like to understand the structural properties of νπ,µγ . For γ = 1 those distributions have equal marginals since we can compute∑
s′∈S νπ,µ1 (s, s ′)− ∑ s′∈S νπ,µ1 (s ′, s) = lim T→∞ 1 T ( Pπ,µ(s0 = s)− Pπ,µ(sT+1 = s) ) = 0. (15)
In the discounted case, we compute similarly∑ s′∈S νπ,µγ (s, s ′)− γ ∑ s′∈S νπ,µγ (s ′, s) = (1− γ) ( ∞∑ t=0 γtPπ,µ(st = s)− ∞∑ t=0 γt+1Pπ,µ(st+1 = s) ) = (1− γ)µ(s).
If we perceive νπ,µγ ∈ ∆S×S as a matrix, we have shown that (νπ,µγ )
T1 = γ(νπ,µγ )1+ (1− γ)µ, which motivates the following definition.
We will see that the set of state-action frequencies is the pre-image of the following polytope under a linear map. Definition 45 (Discounted Kirchhoff polytopes). For a distribution µ ∈ ∆S and γ ∈ (0, 1] we define the discounted Kirchhoff polytope (this is a generalization of a definition by Weis 2010)
Ξµγ := { ν ∈ ∆S×S ⊆ RS×S | νT1 = γν1+ (1− γ)µ } ,
where 1 ∈ RS is the all one vector.
So far, we have observed that fα(ηπ,µγ ) ∈ Ξµγ , i.e., that Ψµγ : ∆ S A → ∆S×A, π 7→ ηπ,µγ maps to f−1α (Ξ µ γ). In order to see that this mapping is surjective on f −1 α (Ξ µ γ) we show that its right inverse is given through conditioning. The following proposition uses the ergodicity assumption. Proposition 46. Let γ ∈ (0, 1] and η ∈ f−1α (Ξµγ) and let ρ ∈ ∆S denote the state marginal of η. Set
π(·|s) := { η(·|s) = η(s, ·)/ρ(s) if ρ(s) > 0 arbitrary element in ∆A if ρ(s) = 0,
then we have ηπ,µγ = η.
Proof. We calculate γ(Pπ)T η(s, a) = γ ∑ s′,a′ α(s|s′, a′)π(a|s)η(s′, a′) = γπ(a|s) ∑ s′,a′ α(s|s′, a′)η(s′, a′)
= γπ(a|s) ∑ s′ ν(s′, s) = π(a|s) (∑ s′ ν(s, s′)− (1− γ)µ(s) ) = π(a|s)ρ(s)− (1− γ)π(a|s)µ(s) = η(s, a)− (1− γ)(µ ∗ π)(s, a).
The unique characterization from Proposition 3 of ηπ,µγ yields the assertion.
The proposition states that we can reconstruct the policy from the state-action frequencies by conditioning and is well known in the context of the dual linear programming formulation of MDPs (Kallenberg, 1994). Hence, it will be convenient later to work under the following assumption in which ensures that policies in ∆SA are one-to-one with state-action frequencies. Assumption 13 (Positivity). Let ρπ,µγ > 0 hold entrywise for all policies π ∈ ∆SA.
Note that this positivity assumption holds in particular, if either α > 0 and γ > 0 or γ < 1 and µ > 0 or entrywise. Indeed, if α > 0, then the transition kernel pπ is strictly positive for any policy since
pπ(s ′|s) = ∑ a (π ◦ β)(a|s)α(s′|s, a) > 0,
since (π ◦ β)(a|s) > 0 for some a ∈ A. Since ρπ,µγ is discounted stationary with respect to pπ (Proposition 3), it holds that
ρπ,µγ (s) = γ ∑ s′ ρπ,µγ (s ′)pπ(s|s′) + (1− γ)µ(s) > 0
since ρπ,µγ (s ′) > 0 for some s′ ∈ S. If µ > 0 and γ < 1, then ρπ,µγ (s) ≥ (1 − γ)µ(s) > 0. As a consequence of Proposition 46, we obtain the following characterization of N µγ . Proposition 8 (Characterization of N µγ ). Let (S,A, α, r) be a MDP, µ ∈ ∆S be an initial distribution and γ ∈ (0, 1]. It holds that
N µγ = ∆S×A ∩ { η ∈ RS×A | ηTwsγ = (1− γ)µs for s ∈ S } (3)
where wsγ := δs ⊗ 1− γα(s|·, ·). For γ ∈ (0, 1), ∆S×A can be replaced by [0,∞)S×A in (3).
Instead of proving this proposition directly, we first present the following version of it. Proposition 47. Let (A,S, α, r) be an MDP and γ ∈ (0, 1]. It holds that N µγ = f−1α (Ξµγ).
Proof. By (14) and (15), it holds that fα(N µγ ) ⊆ Ξµγ and thus N µγ ⊆ f−1α (Ξµγ). However, by Proposition46, for every η ∈ fα(Ξµγ) there is a policy π ∈ ∆SA such that ηπ,µγ = η and hence it holds that f−1α (Ξ µ γ) ⊆ f−1α (Ξµγ).
Proof of Proposition 8. By the preceding proposition η ∈ N µγ is equivalent to η ∈ ∆S×A and ν := fα(η) ∈ Ξµγ . Using the definition of Ξµγ this equivalent to∑
s′ ν(s, s′) = γ ∑ s′ ν(s′, s) + (1− γ)µ(s)
for all s ∈ S. Plugging in the definition of fα we see that the term on the left hand side is equivalent to ∑
s′ ∑ a η(s, a)α(s′|s, a) = ∑ a η(s, a) = 〈δs ⊗ 1, η〉S×A.
The first term of the right hand side is precisely γ ∑ s′ ∑ a η(s′, a)α(s|s′, a) = 〈γα(s|·, ·), η〉S×A.
Hence, we have seen that fα(η) ∈ Ξµγ is equivalent to the condition 〈wsγ , η〉S×A = (1− γ)µ(s) for all s ∈ S. (16)
Note that
{η | 〈wsγ , η〉S×A = (1− γ)µ(s) for all s ∈ S} = η0 + {wsγ | s ∈ S}⊥
for an arbitrary element η0 satisfying (16). This shows the first equation in (3). The second equation follows from the observation that ∑ s w
s γ = (1− γ)1. Hence, for γ < 1 it holds that( η0 + {wsγ | s ∈ S}⊥ ) ∩∆S×A = ( η0 + ( {wsγ | s ∈ S} ∪ {1 )⊥) ∩ [0,∞)S×A = ( η0 + {wsγ | s ∈ S}⊥ ) ∩ [0,∞)S×A.

heading: C.1.1 DERIVATIVE OF THE DISCOUNTED STATE-ACTION FREQUENCIES
text: In this section we discuss the Jacobian of the parametrization π 7→ ηπ of the discounted state-action frequencies. One motivation for this is that this Jacobian plays an important role in the relation of critical points in the policy space and the space of discounted state-action frequencies. Note that Ψµγ(π) = (1−γ)(1−γPTπ )−1(µ∗π) is well defined, whenever ‖Pπ‖2 < γ−1. Hence, we can extend Ψµγ onto the neighborhood { π ∈ RS×A | ‖Pπ‖2 < γ−1 } of ∆SA, which enables us to compute the Jacobian of Ψµγ .
Proposition 48 (Jacobian of Ψµγ ). For any policy π ∈ ∆SA and s ∈ S, a ∈ A it holds that
∂(s,a)Ψ µ γ(π) = (I − γPTπ )−1(ρπ,µγ ∗ ∂(s,a)π) = ρπ,µγ (s)(I − γPTπ )−1(δs ⊗ δa), (17)
where (ρπ,µγ ∗ ∂(s,a)π)(s′, a′) = ρπ,µγ (s′)∂(s,a)π(a′|s′) = ρπ,µγ (s)(δs ⊗ δa)(s′, a′).
Hence, ∂(s,a)Ψµγ(π) is identical to the (s, a)-th column of (I − γPTπ )−1 up to the scaling factor of ρπ,µγ (s). In particular, if ρ π,µ γ (s) > 0 for all s ∈ S, the Jacobian DΨµγ has full rank.
Proof. Recall that for invertible matrices A(t), it holds that ∂tA(t)−1 = −A(t)−1(∂tA(t))A(t)−1. We compute
(1− γ)−1∂(s,a)Ψµγ(π) = ∂(s,a)(I − γPTπ )−1(µ ∗ π) = (∂(s,a)(I − γPTπ )−1)(µ ∗ π) + (I − γPTπ )−1∂(s,a)(µ ∗ π) = −(1− γ)−1(I − γPTπ )−1∂(s,a)(I − γPTπ )ηπ,µγ
+ (I − γPTπ )−1(µ ∗ ∂(s,a)π) = (I − γPTπ )−1 ( (1− γ)−1γ(∂(s,a)PTπ )ηπ,µγ + µ ∗ ∂(s,a)π ) .
Further, direct computation shows
((∂(s,a)P T π )η π,µ γ )(s, a) = ∂(s,a)π(a|s) ∑ s′,a′ α(s|s′, a′)π(a′|s′)ρπ,µγ (s′)
= (pTπ ρ π,µ γ ∗ ∂(s,a)π)(s, a).
Using the fact that ρπ,µγ is the discounted stationary distribution, yields
(1− γ)−1γ(∂(s,a)PTπ )ηπ,µγ + µ ∗ ∂(s,a)π = ((1− γ)−1γpTπ ρπ,µγ + µ) ∗ ∂(s,a)π = (1− γ)−1ρπ,µγ ∗ ∂(s,a)π,
which shows (17). Note that (I − γPTπ )−1(δs ⊗ δa) is precisely the (s0, a0)-th column of the matrix (I − γPTπ )−1. Those columns are linearly independent, and so are the partial derivatives ∂(s,a)Ψ µ γ(π), given that the discounted stationary distribution ρ π,µ γ vanishes nowhere.
Corollary 49 (Dimension of N µγ ). Assume that ρπ,µγ > 0 entrywise for some policy π ∈ int(∆SA). Then we have
dim(N µγ ) = dim(∆SA) = |S|(|A| − 1).
Proof. By Proposition 48 the mapping Ψµγ is full rank in a neighborhood of π and hence, we have
dim(N µγ ) = dim(Ψµγ(∆SA)) = dim(∆SA).
Let us consider a parametrized policy model ΠΘ = {πθ | θ ∈ Θ}with differentiable parametrization θ 7→ πθ. Proposition 50 (Parameter derivatives of discounted state-action frequencies). It holds that
∂θiη πθ,µ γ = (I − γPTπθ ) −1(ρπθ,µγ ∗ ∂θiπθ), where (ρπθ,µγ ∗ ∂θiπθ)(s, a) = ρπθ,µγ (s)∂θiπθ(a|s).
Proof. This follows directly from the application of the chain rule and (17).
Using this expression, we can compute the parameter gradient with respect to the discounted reward F (θ) := Rµγ (πθ) and recover the well known policy gradient theorem, see Sutton et al. (1999).
Definition 51 (state-action value function). We call Qπ := (I − γPπ)−1r ∈ RS×A the state-action value function or the Q-value function of the policy π.
Corollary 52 (Policy gradient theorem). It holds that ∂θiF (θ) = ∑ s ρπθ,µγ (s) ∑ a ∂θiπθ(a|s)Qπθ (s, a) = ∑ s,a ηπθ,µγ (s, a)∂θi log(πθ(a|s))Qπθ (s, a).
Proof. Using the preceding proposition, we compute ∂θiF (θ) = 〈ρπθ,µγ ∗ ∂θiπθ, Qπθ 〉S×A = ∑ s ρπθ,µγ (s) ∑ a ∂θiπθ(a|s)Qπθ (s, a)
= ∑ s,a ηπθ,µγ (s, a)∂θi log(πθ(a|s))Qπθ (s, a).
Remark 53 (POMDPs as parametrized policy models). The case of partial observability can sometimes be regarded as a special case of parametrized policies. In fact the observation mechanism β induces a linear map π 7→ π ◦ β. This interpretation together with the preceding proposition can be used to calculate policy gradients in partially observable systems.

heading: C.1.2 THE FACE LATTICE IN THE FULLY OBSERVABLE CASE
text: So far, we have seen that the set of state-action frequencies form a polytope in the fully observable case. However, not all polytopes are equally complex and thus we aim to describe the face lattice of N µγ , which describes the combinatorial properties of a polytope, see Ziegler (2012).
Theorem 54 (Combinatorial equivalence of N µγ and ∆SA). Let (A,S, α, r) be an MDP and γ ∈ (0, 1]. Then π 7→ ηπ,µγ induces an order preserving surjective morphism between the face lattices of ∆SA and N µγ , such that for every I ⊆ S ×A it holds that{
π ∈ ∆SA | π(a|s) = 0 for all (s, a) ∈ I } 7→ { η ∈ N µγ | η(s, a) = 0 for all (s, a) ∈ I } .
If additionally Assumption 13 holds, this is an isomorphism and preserves the dimension of the faces.
Proof. First, we note that the faces of both ∆SA and N µγ have the structure of the left and right hand side of (54) respectively, which follows from (3). Denote now the left and right hand side in (54) by F and G respectively, then we need to show that Ψµγ(F ) = G. For π ∈ F it holds that
ηπ,µγ (s, a) = ρ π,µ γ (s)π(a|s) = 0 for all (s, a) ∈ I
and hence ηπ,µγ ∈ G. On the other hand for η ∈ G we can set π(·|s) := η(·|s) whenever defined and any other element such that π(a|s) = 0 for all (s, a) ∈ I otherwise. Then we surely have π ∈ F and by Proposition 46 also ηπ,µγ = η. In the case that ρ π,µ γ > 0 holds entrywise for all policies π ∈ int(∆SA), the mapping η 7→ η(·|·) defines an inverse to Ψµγ , which shows that the mapping defined in (54) is injective. The assertion on the dimension follows from basic dimension counting, from the fact that the rank is preserved by a lattice isomorphism or by virtue of Proposition 48.

heading: C.2 THE PARTIALLY OBSERVABLE CASE
text: In Corollary 5, we have seen that the discounted state-action frequencies form a semialgebraic set. Now we aim to describe its defining polynomial inequalities. In Section 5 we will discuss how the degree of these polynomials allows us to upper bound the number of critical points of the optimization problem.
Definition 9 (Effective policy polytope). We call the set of effective policies τ = π ◦ β ∈ ∆SA the effective policy polytope and denote it by ∆S,βA .
Note that ∆S,βA is indeed a polytope since it is the image of the polytope ∆ O A under the linear mapping π 7→ π ◦ β. Hence, we can write it as an intersection
∆S,βA = ∆ S A ∩ U ∩ C, (18)
where U , C ⊆ RS×A are an affine subspace and a polyhedral cone and describe a finite set of linear equalities and a finite set of linear inequalities respectively. In Section 4 we will compute those sets explicitely under mild conditions and see that they do not carry an affine part.

heading: C.2.1 DEFINING LINEAR INEQUALITIES OF THE EFFECTIVE POLICY POLYTOPE
text: Obtaining inequality descriptions of the images of polytopes under linear maps is a fundamental problem that is non-trivial in general. It can be approached algorithmically, e.g., by Fourier-Motzkin elimination, block elimination, vertex approaches, and equality set projection (Jones et al., 2004). We discuss the special case where the linear map is injective, corresponding to the case where the associated matrix B has linearly independent columns. As a polytope is a finite intersection of closed half spaces H+ = {x | nTx ≥ α}, it suffices to characterize the image BH+. It holds that
BH+ = {y ∈ rangeB | nTB+y ≥ α} = {y | ((B+)Tn)T y ≥ α} ∩ ker(BT )⊥, (19)
where B+ is a pseudoinverse and where we have used that B+y consists of at most one element by the injectivity of B. Let us now come back to the mapping π 7→ π ◦ β = βπ. By the “vec-trick”, this map corresponds to vec(βπI) = (IT ⊗ β) vec(π). Hence the linear map is represented by the matrix B = I ⊗ β. We observe that (I ⊗ β)+ = I ⊗ β+ (see Langville & Stewart, 2004, Section 2.6.3). Notice that B = I ⊗ β has linearly independent columns if and only if β does. By the above discussion, if β has linearly independent columns, then an inequality 〈π, n〉 ≥ 0 in the policy polytope ∆OA corresponds to an inequality 〈τ, (β+)Tn〉 ≥ 0 in the polytope ∆SA. Assumption 10. The matrix β ∈ ∆SO ⊆ RS×O has linearly independent columns. Remark 11. The assumption above does not imply that the system is fully observable. Recall that if β has linearly independent columns, the Moore-Penrose takes the form β+ = (βTβ)−1βT . An interesting special case is when β is deterministic but may map several states to the same observation (this is the partially observed setting considered in numerous works). In this case, β+ = diag(n−11 , . . . , n −1 |O|)β
T , where no denotes the number of states with observation o. In this case, β+so agrees with the conditional distribution β(s|o) with respect to a uniform prior over the states; however, this is not in general the case since β+ can have negative entries.
Theorem 12 (H-description of the effective policy polytope). Let (S,O,A, α, β, r) be a POMDP and let Assumption 10 hold. Then it holds that
∆S,βA = ∆ S A ∩ U ∩ C = U ∩ C ∩ D, (4)
where U = {π◦β | π ∈ RS×O} is a subspace, C = {τ ∈ RS×A | β+τ ≥ 0} is a pointed polyhedral cone and D = {τ ∈ RS×A | ∑ a(β
+τ)oa = 1 for all o ∈ O} an affine subspace. Further, the face lattices of ∆OA and ∆ S,β A are isomorphic.
Proof. First, we recall the defining linear (in)equalities of the policy polytope ∆OA, which are given by
π(a|o) = 〈δo ⊗ δa, π〉O×A ≥ 0 for all a ∈ A, o ∈ O and∑ a π(a|o) = 〈δo ⊗ 1, π〉O×A = 1 for all o ∈ O.
Hence, by the general discussion from above, namely by (19), it holds that
∆S,βA = ker(β T )⊥ ∩ {τ | β+τ ≥ 0} ∩ { τ | ∑ a (β+τ)oa = 1 for all o ∈ O } .
Note that the linear inequalities ∑ a(β
+τ)oa = 1 are redundant in ∆SA. To see this, we note that β+1 = 1 by the injectivity of β and β1 = 1. Now we can check that∑
a (β+τ)oa = ∑ a ∑ s β+osτsa = ∑ s β+os ∑ a τsa = ∑ s β+os = 1.
This together with β(∆OA) ⊆ ∆SA shows that
∆S,βA = ∆ S A ∩ ker(βT )⊥ ∩ {τ | β+τ ≥ 0}.
The reformulation of the sets C and D for deterministic observation mechanisms β follows from the preceding remark.

heading: C.2.2 DEFINING POLYNOMIAL INEQUALITIES OF THE FEASIBLE STATE-ACTION FREQUENCIES
text: Using that the inverse of π 7→ ηπ is given through conditioning (see Proposition 46), we can translate linear inequalities in ∆SA into polynomial inequalities inN µγ . More precisely, we have the following result, which can easily be extended to more general inequalities.
Proposition 14 (Correspondence of inequalities). Let (S,A, α, r) be a MDP, τ ∈ ∆SA and let η ∈ ∆S×A denote its corresponding discounted state-action frequency for some µ ∈ ∆S and γ ∈ (0, 1]. Let c ∈ R, b ∈ RS×A and set S := {s ∈ S | bsa 6= 0 for some a ∈ A}. Then∑
s,a bsaτsa ≥ c implies ∑ s∈S ∑ a bsaηsa ∏ s′∈S\{s} ∑ a′ ηs′a′ − c ∏ s′∈S ∑ a′ ηs′a′ ≥ 0,
where the right is a multi-homogeneous polynomial8 in the blocks (ηsa)a∈A ∈ RA with multi-degree 1S ∈ NS . If further Assumption 13 holds, the inverse implication also holds.
Proof. Let τ ∈ ∆SA and let η denote its corresponding discounted stationary distribution and ρ the state marginal. Assuming that the left hand side holds, we compute∑
s∈S ∑ a bsaηsa ∏ s′∈S\{s} ∑ a′ ηs′a′ = ∑ s∈S ∑ a bsaτsaρs ∏ s′∈S\{s} ρs′
= (∑ s,a bsaτsa ) · ∏ s′∈S ρs′ ≥ c ∏ s′∈S ρs′ ,
which shows the first implication. If further Assumption 13 holds, the product over the marginals is strictly positive, which shows the other implication.
Remark 55. According to the preceding proposition, a linear inequality in the state policy polytope ∆SA involving actions of k different states yields a polynomial inequality of degree k in the set of state-action frequencies N µγ . In particular, for a linearly constrained policy model Π ⊆ ∆SA, where every constraint only addresses a single state, the set of state-action frequencies induced by these policies will still form a polytope. This shows that this type of box constraints are well aligned with the algebraic geometric structure of the problem. The linear constraints arising from partial observability never exhibit this box type structure – unless the system is equivalent to its fully observable version. This is because the projection of the effective policy polytope ∆S,βA onto a single state always gives the entire probability simplex ∆A, which is never the case, if there is a non trivial linear constraint concerning only this state.
Theorem 16. Let (S,O,A, α, β, r) be a POMDP, µ ∈ ∆S and γ ∈ (0, 1] and assume that Assumption 13 holds. Then we have N µ,βγ = N µγ ∩ V ∩ B, where V is a variety described by multi-homogeneous polynomial equations and B is a basic semialgebraic set described by multihomogeneous polynomial inequalities. Further, the face lattices of ∆S,βA and N µ,βγ are isomorphic.
8A polynomial p : Rn1×· · ·×Rnk → R is called multi-homogeneous with multi-degree (d1, . . . , dk) ∈ Nk, if it is homogeneous of degree dj in the j-th block of variables for j = 1, . . . , k.
Proof. The equationN µ,βγ = N µγ ∩V∩B is a direct consequence of (4) and Proposition 14. Further, it is clear from Proposition 14 that the mapping Ψ: ∆SA → N µγ , π 7→ ηπ,µγ induces a bijection of the face lattices of ∆S,βA andN µ,βγ . In order to see that the join and meet are respected, we note that for F,G ∈ F(∆S,βA ) it holds that Ψ(F ∧G) = Ψ(F ∩G) = Ψ(F ) ∩Ψ(G) = Ψ(F ) ∧Ψ(G). Further, Ψ(F ∨ G) is a face of N µ,βγ containing Ψ(F ) and Ψ(G) and hence by definition Ψ(F ) ∨ Ψ(G) ⊆ Ψ(F ∨ G). Further, for any face I of N µ,βγ containing Ψ(F ) and Ψ(G) it holds that Ψ−1(I) is a face of ∆S,βA containing F and G and hence Ψ −1(I) ⊇ F ∨G or equivalently Ψ(F ∨G) ⊆ I .
Remark 18. By Theorem 12 and Proposition 14, the defining polynomials of the basic semialgebraic set B from Theorem 16 are indexed by a ∈ A, o ∈ O and are given by
pao(η) := ∑ s∈So ( β+osηsa ∏ s′∈So\{s} ∑ a′ ηs′a′ ) = ∑ f : So→A ( ∑ s′∈f−1({a}) β+os′ ) ∏ s∈So ηsf(s) ≥ 0, (5)
where So := {s ∈ S | β+os 6= 0}. The polynomials depend only on β and not on γ, µ nor α, and have |So||A||So|−1 monomials of degree |So| of the form ∏ s∈So ηsf(s) for some f : So → A. In particular, we can read of the multi-degree of pao with respect to the blocks (ηsa)a∈A which is given by 1So (see also Proposition 14). A complete description of the set N µ,βγ via (in)equalities follows from the description of N µγ via linear (in)equalities given in (3). In Section 5 we discuss how the degree of these polynomials controls the complexity of the optimization problem.
Remark 56 (Defining polynomial equalities). Analogously to the defining inequalities, we can compute the defining polynomial equalities in the following way. First, we need to compute a basis {bj}j∈J of {βπ | π ∈ RO×A}⊥ ⊆ RS×A, which can easily be done using the Gram-Schmidt process. Note that the defining linear equalities of the effective policy polytope (in the policy polytope) are given by 〈bj , τ〉S×A = 0. Hence, by Proposition 14 the corresponding polynomial equality is given by
qj(η) := ∑ s∈Sj ∑ a∈A bjsaηsa ∏ s′∈Sj\{s} ∑ a′∈A ηs′a′ = 0, (20)
where Sj := {s ∈ S | bjsa 6= 0 for some a ∈ A}.
Remark 57. In the fully observable case we have |So| = 1 for each o. Hence, each of the polynomial inequalities has a single term of degree 1. Indeed, in this case the inequalities are simply ηsa ≥ 0, for each a, for each s. In the case of a deterministic β, we have β+os = 1s∈So/|So|. For each o, a, there is an inequality ∑ f : So→A |f −1(a)| ∏ s∈So ηsf(s) ≥ 0 of degree |So| equal to the number of states that are compatible with o.
Remark 58 (Reformulation of reward maximization as a polynomial program). By the theorem above and Proposition 14, reward maximization is equivalent to the maximization of a linear function subject to polynomial constraints. This enables the use of any (approximate) solution technique of polynomial optimization problems in order to solve POMDPs. Such methods have been developed for a long time and have been applied to a variety of problems (Anjos & Lasserre, 2011; Lasserre, 2015). As meta algorithm, this is presented in Algorithm 1. Once, a solution η∗ is obtained, the corresponding state policy τ∗ ∈ ∆SA can be computed by conditioning, i.e. τ(a|s) := ηsa/( ∑ a′ ηsa′). Then, every π∗ ∈ ∆OA with βπ∗ = τ∗ is an optimal policy. Such a policy can be computed by solving a system of linear equations, which are βπ = τ and π ∈ ∆OA, which is standard. In particular, if β has linearly independent columns, it holds that π∗ := β+τ . We demonstrate that this offers a computationally feasible approach to planning of POMPDs in Section F on the toy example used for Figure 1 and a grid world.
Remark 59 (Polynomial constraints for deterministic observations). In the case, where β corresponds to a determinstic mapping we can compute all polynomial constraints in closed form. Let us
Algorithm 1 Polynomial programming for POMDPs Require: α, β, γ, µ
for s ∈ S do ws ← δs ⊗ 1A − γα(s|·, ·) end for for a ∈ A, o ∈ O do
Define pao according to Equation (5) end for Compute a basis {bj}j∈J of {βπ | π ∈ RO×A}⊥ ⊆ RS×A for j ∈ J do
Define qj according to Equation (20) end for η∗ ← arg max〈r, η〉 sbj to η ≥ 0, 〈ws, η〉 = (1− γ)µs, 〈1S×A, η〉 = 1, pao(η) ≥ 0, qj(η) = 0 R∗ ← 〈r, η∗〉 τ∗ ← η∗(·|·) ∈ ∆SA π∗ ← solution of βπ = τ∗
return maximizer η∗, optimal value R∗, optimal policy π∗
assume that β(o|s) = δog(s) for some mapping g : S → O and write So := g−1({o}) ⊆ S , then τ ∈ ∆SA belongs to the effective policy polytope ∆ S,β A if and only if
τ(a|s1) = τ(a|s2) for all s1, s2 ∈ So, a ∈ A, o ∈ O. (21) Note that this can be encoded in ∑ o|A|(|So| − 1) = |A|(|S| − |O|) linear equations; indeed if we fix so ∈ So, then equation 21 is equivalent to
τ(a|s)− τ(a|so) = 0 for all s ∈ So \ {so}, a ∈ A, o ∈ O. (22)
By Proposition 14 for η ∈ N µγ it is equivalent to lie in N µ,βγ or to satisfy
ηsa ∑ a′ ηsoa′ − ηsoa ∑ a′ ηsa′ = 0 for all s ∈ So \ {so}, a ∈ A, o ∈ O. (23)
Note that in this case, there are no polynomial inequalities; this can also be seen from Remark 11 and Remark 18. Indeed, it holds that β+ = βT diag(n1, . . . , n|O|) ≥ 0, where no := |So|. Hence, the polynomial inequalities pao(η) ≥ 0 are redundant on the cone [0,∞)S×A.

heading: D DETAILS ON THE OPTIMIZATION
text: Let us quickly recall how we can reformulate the reward maximization problem as a polynomial optimization problem, which then leads us to the mighty tools of algebraic degrees. We perceive the reward maximization problem again as the maximization of a linear function p0 over the set of feasible state-action frequencies N µ,βγ . Since under Assumption 13 the parametrization π 7→ ηπ is injective and has a full-rank Jacobian everywhere (see Appendix C.1.1), the critical points in the policy polytope ∆OA correspond to the critical points of p0 onN µ,βγ (Trager et al., 2019). In general, critical points of this linear function can occur on every face of the semialgebraic set N µ,βγ . The optimization problem thus has a combinatorial and a geometric component, corresponding to the number of faces of each dimension and the number of critical points in the interior of any given face. We have discussed the combinatorial part in Theorem 16 and focus now on the geometric part. Writing N µ,βγ = {η ∈ RS×A : pi(η) ≤ 0, i ∈ I}, we are interested in the number of critical points on the interior of a face
int(FJ) = {η ∈ N µ,βγ | pj(η) = 0 for j ∈ J, pi(η) > 0 for i ∈ I \ J}.
Note that a point η ∈ int(FJ) is critical, if and only if it is a critical point on the variety
VJ := {η ∈ RS×A | pj(η) = 0 for j ∈ J}.
For the sake of notation, let us assume that J = {1, . . . ,m} from now on. We can upper bound the number of critical points in the interior of the face by the number of critical points of the polynomial optimization problem
maximize p0(η) subject to pj(η) = 0 for j = 1, . . . ,m, (24)
where the polynomials have n variables. The number of critical points of this problems is upper bounded by the algebraic degree of the problem as we discuss now.
D.1 INTRODUCTION TO ALGEBRAIC DEGREES
We try to present the results from the mighty theory of algebraic degrees that we use here and refer the interested reader to the excellent low level introduction by Breiding et al. (2021) and to the references therein. Let us consider the polynomial optimization problem (24), where we do not require p0 to be linear. Further, denote the number of variables by n (in the case of state-action frequencies n = |S||A|) and denote the degrees of p0, . . . , pm by d0, . . . , dm. We call a point critical, if it satisfies the KKT conditions (∇p0(x) + ∑m i=1 λi∇pi(x) = 0, p1(x) = · · · = pm(x) = 0), which can be phrased as a system of polynomial equations (see Nie & Ranestad, 2009). The number of complex solutions to those criticality equations, when finite, is called the algebraic degree of the problem. The algebraic degree is determined by the nature of the polynomials p0, . . . , pm and captures the computational complexity of the optimization problem (Kung, 1973; Bajaj, 1988).9 A special case of (24) is when m = n and the polynomials p1, . . . , pm are generic. Then by Bézout’s theorem there are exactly d1 · · · dn isolated points satisfying the polynomial constraints and all of them are critical and hence the algebraic degree is precisely d1 · · · dn (Timme, 2021). If the polynomials p0, . . . , pm define a complete intersection, i.e., the co-dimension of their induced variety is m+ 1, the algebraic degree of (24) is upper bounded by
d1 · · · dm ∑
i0+···+im=n−m (d0 − 1)i0 · · · (dm − 1)im , (25)
and this bound is attained for generic polynomials (Nie & Ranestad, 2009; Breiding et al., 2021). For non-complete intersections, the expression (25) does not need to yield an upper bound if some constraints are redundant. However, we can modify the expression to obtain a valid upper bound. Indeed, if l and c = n− l denote the dimension and co-dimension of
V := {x | p1(x) = · · · = pm(x) = 0} and if p0 is generic and if the degrees are ordered, i.e., d1 ≥ · · · ≥ dm, then the algebraic degree is upper bounded by
d1 · · · dc ∑
i0+···+ic=l
(d0 − 1)i0 · · · (dc − 1)ic . (26)
To see this, fix a subset J ⊆ {1, . . . ,m} of cardinality c, such that V = {x | pj(x) = 0 for j ∈ J}. Then we can apply the bound from (25) and evaluate it to be∏
j∈J dj ∑ i0+ ∑ j∈J ij=n−c (d0 − 1)i0 · ∏ j∈J (dj − 1)ij ,
which is clearly upper bounded by (26). If p0 is linear, then d0 = 1 and the expression simplifies to d1 · · · dc ∑
i1+···+ic=l
(d1 − 1)i0 · · · (dc − 1)ic .
If further di = 1 for i ≥ k for some k ≤ c, then we obtain d1 · · · dk ∑
i1+···+ik=l
(d1 − 1)i1 · · · (dk − 1)ik . (27)
If pk+1, . . . , pm are affine linear (and in general position relative to p1, . . . , pk, the algebraic degree of (24) is given by the (m− k)-th polar degree δm−k(V) of the variety
V := {η | pk+1(η) = · · · = pm(η) = 0}, 9The coordinates of critical points can be shown to be roots of some univariate polynomials whose degree
equals the algebraic degree and whose coefficients are rational functions of the coefficients of p0, . . . , pm.
see Draisma et al. (2016); Özlüm Çelik et al. (2021). This relation is particularly useful, since for state-action frequencies there are always active linear equations as described in (3). The polar degrees of certain interesting cases (Segre-Veronese varieties) have been recently computed by Sodomaco (2020, Section 5) and our proof of Proposition 21 builds on those formulas and their presentation by Özlüm Çelik et al. (2021). Remark 60 (Genericity assumptions). In the case, where the polynomials p0, . . . , pm are not generic, there might be infinitely many critical points. Indeed, even for a linear program, i.e., when all polynomials are linear, there might be infinitely many and even a non-trivial face of global optima. This is however not the case if p0 is generic. Hence, the genericity assumptions on the reward vector r and also other elements of the POMDP are not surprising. For example, they prevent the reward vector to be identical to zero or to be perpendicular on all vectors δs⊗1−γα(s|·, ·) in which cases the reward function would be constant and every policy would be a global optimum.

heading: D.2 GENERAL UPPER BOUND ON THE NUMBER OF CRITICAL POINTS
text: Theorem 20. Consider a POMDP (S,O,A, α, β, r), γ ∈ (0, 1), assume that r is generic, that β ∈ RS×O is invertible, and that Assumption 13 holds. For any given I ⊆ A × O consider the following set of policies, which is the relative interior of a face of the policy polytope:
int(F ) = { π ∈ ∆OA | π(a|o) = 0 if and only if (a, o) ∈ I } .
Let O := {o ∈ O | (a, o) ∈ I for some a} and set ko := |{a | (a, o) ∈ I}| as well as do := |{s | β+os 6= 0}|. Then, the number of critical points of the reward function on int(F ) is at most(∏
o∈O dkoo
) ·
∑ ∑ o∈O io=l ∏ o∈O (do − 1)io , (6)
where l = |S|(|A| − 1) − |I|. If α and µ are generic, this bound can be refined by computing the polar degrees of multi-homogeneous varieties (see Proposition 21 for a special case). The same bound holds in the mean reward case γ = 1 for l given in Remark 61.
Proof. The face G of the effective policy polytope corresponding to F is given by int(G) = { τ ∈ ∆S,βA | (β +τ)oa = 0⇔ (a, o) ∈ I } .
In order to describe the corresponding set of discounted state-action frequencies, we use the notation
pao(η) := ∑ s∈So β+osηsa ∏ s′∈So\{s} ∑ a′ ηs′a′  , then it holds that N µ,βγ = {η ∈ N µγ | pao(η) ≥ 0 for all a ∈ A, o ∈ O}. Then, F and G correspond to the face
int(H) = { η ∈ N µ,βγ | pao(η) = 0⇔ (a, o) ∈ I } = { η ∈ N µγ | pao(η) ≥ 0 and equality if and only if (a, o) ∈ I } .
In order to use the explicit description ofN µγ given in (3), we remind the reader that wsγ := δs⊗1− γα(s|·, ·). Then, it holds that
int(H) = { η ∈ [0,∞)S×A | pao(η) ≥ 0 and equality if and only if (a, o) ∈ I
ηTwsγ = (1− γ)µs for s ∈ S } ,
where we used Proposition 8. Since the discounted state distributions are all positive by assumption, for η ∈ int(H) it holds ηsa = 0 if and only if τ(a|s) := η(a|s) = 0. Note that τ = π ◦ β for some π ∈ ∆OA by assumption and thus for η ∈ int(H) it holds that ηsa = 0 if and only if
0 = τ(a|s) = ∑ o β(o|s)π(a|o),
which holds if and only if (a, o) ∈ I for every o ∈ O with β(o|s) > 0. Hence, if we write J := {(s, a) | (a, o) ∈ I for all o ∈ O with β(o|s) > 0}, we obtain
int(H) = { η ∈ RS×A | ηsa ≥ 0 and equality if and only if (s, a) ∈ J, ηTwsγ = (1− γ)µs for s ∈ S,
pao(η) ≥ 0 and equality if and only if (a, o) ∈ I } .
The number of critical points over this surface is upper bounded by the number of critical points over
V = {η ∈ RS×A | ηsa = 0 for (s, a) ∈ J, ηTwsγ = (1−γ)µs for s ∈ S, pao(η) = 0 for (a, o) ∈ I}.
Now we want to apply (27) and note that the objective p0 = r is generic. Further, we see that there are |I| non-linear constraints and hence in the notation of (27) have k = |I|. Further, we can calculate to dimension and co-dimension of V as follows. Note that F → V, π 7→ ηπ is a local parametrization of V (meaning it parametrizes a full dimensional subset of V), which is injective and has full rank Jacobian everywhere. Hence, we have
l = dim(V) = dim(F ) = |S|(|A| − 1)− |I| = |S||A| − |S| − |I|.
The co-dimension of V is given by |S||A|−dim(V) = |S|+ |I| and with the notation from (27), we have c = |S|+ |I| ≥ k. Further, it holds that deg(pao) ≤ do and using (27) yields an upper bound of ∏
(s,o)∈I
do · ∑
∑ (a,o)∈I jao=m ∏ (a,o)∈I (do − 1)jao = ∏ o∈O dkoo · ∑ ∑ o∈O io=m ∏ o∈O (do − 1)io .
Remark 61 (The mean reward case). Theorem 20 can be generalized to the mean reward case, i.e., to the case of γ = 1 with some adjustments. Indeed, the proof can be carried out analogously, however, the characterization of N µ1 has the extra linear condition that ∑ sa ηsa = 1, see also Proposition 8. Indeed, in the mean reward case we have with the notation from the proof above
int(H) = { η ∈ RS×A | ηsa ≥ 0 and equality if and only if (s, a) ∈ J, ηTwsγ = 0 for s ∈ S,∑
sa
ηsa = 1, pao(η) ≥ 0 and equality if and only if (a, o) ∈ I } .
Hence, the upper bound in (6) remains valid if we set l := dim { η ∈ RS×A | ηsa = 0 for (s, a) ∈ J, ηTwsγ = 0 for s ∈ S,∑
sa
ηsa = 1, pao(η) = 0 for (a, o) ∈ I } . (28)
In the discounted case we obtained an explicit formulation for l. In the mean case the value obeys a case distinction depending, in particular, on whether the all ones vector 1 lies in the span of the vectors wsγ . However, the value can be computed from the above expression equation 28 in any given specific case.
Corollary 62 (Critical points of MDPs). Consider a MDP (S,A, α, r), γ ∈ (0, 1), assume that r is generic, that β ∈ RS×O is invertible, and that Assumption 13 holds. Then, every critical point π ∈ ∆OA of the discounted expected reward function is deterministic.
Proof. We evaluate the bound of Equation (6). If the face is not a vertex, then the corresponding index set I ⊆ A×O satisfies |I| < |O|(|A| − 1) and thus in the notation from Theorem 20 it holds that l > 0. Note that do = 1 for every o ∈ O and hence there is at least one factor in the product in (6) that vanishes and so does the whole expression in (6).
Remark 63 (Geometry around the critical points). The key argument in the proof of Theorem 20 is that a critical point π ∈ ∆OA of the reward function corresponds to a critical point η of a linear function over a multi-homogeneous variety V , where the defining polynomials can be computed by the means of Proposition 8 and Proposition 14. A closer study of this variety would shed light into the geometry of the loss landscape around the critical points, which has important implications for gradient based methods.
Remark 64 (Efficient design of observation mechanisms). The bound (6) could be used to design observation mechanisms in such a way that the reward function has the least critical points, which would potentially make the system more approachable for gradient based methods. (Rauh et al., 2021) showed that planning in POMDPs is stable under perturbations of the observation kernel β. More precisely, consider two observation kernels β, β′ ∈ ∆SO satisfying ‖β(·|s) − β′(·|s)‖TV =∑ o|β(o|s) − β′(o|s)|/2 ≤ ε for every s ∈ S . Then if π ∈ ∆OA is an optimal policy of (S,A,O, α, β′, r), then it is a 2εγ‖r‖∞/(1 − γ)-optimal policy of (S,A,O, α, β, r). Hence, if β does not fulfill the invertability assumption made in Theorem 20 an arbitrary small perturbation of it does (given that β is a square matrix) and hence Theorem 20 provides an upper bound on the number of critical points of an approximate problem. Further, note that the faces, which are guaranteed to contain an optimal policy by (Montúfar & Rauh, 2017) might be considerably fewer for the POMDP (S,A,O, α, β′, r). The bound equation 6 could be used to identify the best perturbations of a given magnitude to obtain a problem with a minimal number of critical points.
Remark 65 (Design of policy models). Knowledge about the location of critical points of the reward function can be used to design policy models, which provably include those critical points and therefore also the optimal policy.

heading: D.3 NUMBER OF CRITICAL POINTS IN A TWO-ACTION BLIND CONTROLLER
text: This subsection is devoted to the proof of Proposition 21 that we restate here for convenience.
Proposition 21 (Number of critical points in a blind controller). Let (S,O,A, α, β, r) be a POMDP describing a blind controller with two actions, i.e., O = {o} and A = {a1, a2} and let r, α and µ be generic and let γ ∈ (0, 1). Then the reward function Rµγ has at most |S| critical points in the interior int(∆OA) ∼= (0, 1) of the policy polytope and hence at most |S|+ 2 critical points.
Before we present the proof of this result, we discuss how the bound on the rational degree of the reward function leads to am upper bound on the number of critical points. We consider a blind controller and restrict ourselves to the discounted case γ ∈ (0, 1). We associate the policy polytope ∆OA with [0, 1] and for p ∈ [0, 1] we write πp and ηp for the associated policy and the state-action frequency. From Theorem 4 we know that the reward function R = f/g : [0, 1] → R is a rational function of degree at most k := |S|, which is well known to possess at most 2k − 2 critical points. Hence, there are at most this many critical points in the interior (0, 1) if the reward function is not constant. Now we use the geometric description of the set of state-action frequencies and yields a refined bound.
Proof of Proposition 21. First, we note that since µ is generic and γ < 1 Assumption 13 is satisfied. In this case, the combinatorial part is simple, since there are only two zero-dimensional faces of the state-action frequencies (corresponding to the endpoints of the unit interval) and one one-dimensional face (corresponding to the interior of the unit interval). Let us set
U = {η ∈ RS×A | ηTwsγ = (1− γ)µs for all s ∈ S},
where wsγ := δs⊗1−γα(s|·, ·). By Proposition 8 and Example 15 the set of discounted state-action frequencies is given by
N µ,βγ = N µγ ∩ D1 = [0,∞)S×A ∩ U ∩ D1.
Like above, we associate the policy polytope ∆OA with [0, 1] and for p ∈ [0, 1] we write πp and ηp for the associated policy and the state-action frequency. We aim to bound the number of critical points of the reward function over (0, 1) or equivalently the number of critical over {ηp | p ∈ (0, 1)} where we used that Assumption 13 holds. Further, recall that ηp(a|s) = ηpsa/ρps , we have that
{ηp | p ∈ (0, 1)} = {η ∈ N µ,βγ | η(a|s) > 0 for all s ∈ S, a ∈ A} = {η ∈ N µ,βγ | ηsa > 0 for all s ∈ S, a ∈ A} = (0,∞)S×A ∩ U ∩ D1.
Thus the number of critical points over {ηp | p ∈ (0, 1)} are upper bounded by the number of critical points on U ∩D1. Note that if α and µ are generic, the subspace U is in general position. Further, its dimension is |S||A| − |S| = |S|, where we used |A| = 2. Hence, the number of complex solutions to the KKT conditions over U ∩ D1 are given by the k-th polar degree δk(D1), where k := |S|, where we also used the genericity of the reward vector. We can compute the polar degree using the formula presented by Özlüm Çelik et al. (2021) to obtain
δk(D1) = k−2k+k+2∑
s=0
(−1)s (
k − s+ 1 2k − (k + 1)
) (k − s)!  ∑ i+j=s
( k i ) (k − 1− i)! · ( 2 j ) (2− 1− j)!  =
2∑ s=0 (−1)s ( k − s+ 1 k − 1 ) (k − s)!  ∑ i+j=s
( k i ) (k − 1− i)! · ( 2 j ) (2− 1− j)!  . We calculate the three individual terms to be( k + 1
k − 1
) k!  ∑ i+j=0
( k i ) (k − 1− i)! · ( 2 j ) (2− 1− j)!  = (k + 1)k 2 · k! · ( k 0 ) (k − 1)! · ( 2 0 ) 1! = (k + 1)k2 2 ,
and − ( k
k − 1
) (k − 1)! ( ( k 1 ) (k − 2)! + ( 2 1 ) (k − 1)! ) = −k! ( k (k − 2)! +
2
(k − 1)!
) = −k2(k − 1)− 2k,
and ( k − 1 k − 1 ) (k − 2)! ( ( k 1 )( 2 1 ) (k − 2)! + ( k 2 ) (k − 3)! ) = (k − 2)! ( 2k (k − 2)! + k(k − 1) 2(k − 3)! ) = 2k +
k(k − 1)(k − 2) 2 .
Adding those three summands we obtain
δk(D1) = k3 + k2 + k3 − 3k2 + 2k
2 − k3 + k2 − 2k + 2k = k.
Note that there is also a more structural argument to obtain this polar degree. In fact, the polar degree δl(D1) = 0 for l > dim(D∗1) − 1, where D∗1 denotes the dual variety of D1 (Özlüm Çelik et al., 2021). Note that in the case of k × 2 matrices D∗1 = D1 (Draisma et al., 2016) and hence it holds that δl(D1) = 0 for l > dim(D1) − 1 = k (Spaenlehauer, 2012). The largest non-zero polar degree is equal to the degree of the dual variety (Draisma et al., 2016) and hence we obtain δk(D1) = degree(D∗1) = degree(D1) = k (Spaenlehauer, 2012).
Note that this bound is not necessarily sharp, since it is exactly the number of complex solutions of the criticality equations over U ∩D1. Overall, we have seen that the study of the algebraic properties of the reward function provided an upper bound on the number of critical points of the problem, which can be improved using the description of the state-action frequencies as a basic semialgebraic set and employing tools from algebraic geometry.

heading: D.4 EXAMPLES WITH MULTIPLE SMOOTH AND NON-SMOOTH CRITICAL POINTS
text: It is the goal of this example to demonstrate that for a blind controller multiple critical points can occur in the interior (0, 1) ∼= int(∆OA) as well as at the two endpoints of [0, 1] ∼= ∆OA of the policy polytope. We refer to such points as smooth and non-smooth critical points. We consider a blind controller with one observation, two actions a1, a2 and three states s1, s2, s3 and a deterministic transition kernel α and reward described by the graph shown in Figure 2.
We make the usual identification [0, 1] ∼= ∆OA, where we associate p with π(a1|o). In Figure 3, the reward function is plotted on the left for the three initial conditions µ = δs1 , δs2 , δs3 . It is apparent that the reward has two critical points in the interior of the policy polytope ∆OA ∼= [0, 1] for the two initial conditions µ = δs1 = δs3 . For µ = δs2 , there are two strict local maxima on the two endpoints of the interval. In this example, the bound from Proposition 21 ensures that there are at most |S| = 3 critical points in the interior and at most |S|+ 2 = 5 critical points in the whole policy polytope. We see that those bounds are not sharp in this specific setting. Note that this example is stable under small perturbations of the transition kernel and reward vector and hence can occur for generic α and r. The right hand side of Figure 3 shows a three dimensional random projection of the set of feasible discounted state-action frequencies. By Theorem 4 they are a curve in RS×A ∼= R6 with an injective rational parametrization of degree at most |S| = 3.

heading: D.5 (SUPER)LEVEL SETS OF (PO)MDPS

heading: D.5.1 CONNECTEDNESS OF SUPERLEVEL SETS IN MDPS
text: Theorem 66 (Existence of improvement paths in MDPs). For every policy π ∈ ∆SA, there is a continuous path connecting π to an optimal policy along which the reward is monotone. If further π 7→ ηπ is injective, the reward is strictly monotone along this path, if π is suboptimal. In particular, the superlevel sets of MDPs are connected.
Proof. Let us fix π ∈ ∆SA and set η0 := ηπ and η1 be a global optimum and ηt be the linear interpolation and ρt be the corresponding state marginal. Note that for s ∈ S it holds that either ρt(s) > 0 for all t ∈ (0, 1) or ρt(s) = 0 for all t ∈ [0, 1]. In the latter case, we can set πt(·|s) to be an arbitrary element in ∆A. For the other states and t ∈ (0, 1) we can define the policy through conditioning by πt(a|s) := ηt(s, a)/ρt(s) and will continuously extend the definition to t ∈ {0, 1} in the following. If ρ0(s) > 0 or ρ1(s) > 0, then the definition extends naturally. Suppose that ρ0(s) = 0, then we now that ρ1(s) > 0 since otherwise ρt(s) = 0 for all t ∈ [0, 1]. Now for t > 0 it holds that
πt(s, a) = ηt(s, a)
ρt(s) = (1− t)η0(s, a) + tη1(s, a) (1− t)ρ0(s) + tρ1(s) = tη1(s, a) tρ1(s) = η1(s, a) ρ1(s) ,
which extends continuously to t = 0. If ρ1(s) = 0, then like before, πt(·|s) does not depend on t and we can extend it to t = 1. Now we have constructed a continuous path πt, such that ηπt = ηt and thus R(πt) = 〈r, ηt〉 = (1− t)〈r, η0〉+ t〈r, η1〉 = R(π0) + t(R∗ −R(π0)), which is strictly increasing if π0 is suboptimal. It remains to construct a continuous path between π0 and π. Note that if ρ0(s) > 0, the policies π0 and π agree on the state s and so does the linear interpolation between the two policies. Now, by Proposition 46 we see that every linear interpolation between π0 and π has the state-action distribution η0. Gluing the two paths, we obtain a path that first leaves the state-action distribution unchanged and then increases the reward strictly up to optimality.

heading: D.5.2 THE SEMIALGEBRAIC STRUCTURE OF LEVEL AND SUPERLEVEL SETS FOR POMDPS
text: Consider a POMDP (S,A,O, α, β, r) and fix a discount rate γ ∈ (0, 1) as well as an initial condition µ ∈ ∆S . The levelset La := {π ∈ ∆OA | Rµγ (π) = a} of the reward function is the intersection of a variety generated by one determinantal polynomial of degree at most |S| with the policy polytope ∆OA. Indeed, by Theorem 4 the reward function Rµγ is the fraction f/g of two determinantal polynomials f and g of degree at most |S|. The level set consists of all policies, such that f(π) = ag(π). Thus, the levelset is given by
La = ∆ O A ∩
{ x ∈ RO×A | f(x)− ag(x) = 0 } .
Analogously, a superlevel set is the intersection ∆OA ∩ { x ∈ RO×A | f(x)− ag(x) ≥ 0 } of a basic semialgebraic generated by one determinantal polynomial of degree at most |S| with the policy polytope ∆OA. In particular, both the levelset and superlevel sets of POMDPs are semialgebraic sets defined by linear inequalities and equations (corresponding to the conditional probability polytope ∆OA) and a determinantal (in)equality of degree at most |S|. This description can be used to bounds the number of connected components, which captures important properties of the loss landscape of an optimization problem (Barannikov et al., 2019; Catanzaro et al., 2020). By a theorem due to Łojasiewicz, level and superlevel sets possess finitely many connected (semialgebraic) components (Ruiz, 1991; Basu et al., 2006) and there exist algorithmic approaches to computing the number of connected components (Grigor’ev & Vorobjov, 1992) as well as explicits upper bounds, which involve the dimension, the number of defining polynomials as well as their degrees (Basu, 2003; 2014). Those results are generalizations of the classic result due to Milnor and Thom which bounds the sum of all Betti numbers of a variety. If we apply the Milnor-Thom theorem to the variety V we obtain that there are at most |S|(2|S|−1)|O||A|−1 many connected components of V . This
bound neglects the determinantal nature of the defining polynomial and might therefore be coarse. Using an analogue approach, we can also study the level and superlevel sets of the reward function in the space of feasible state-action frequencies. Indeed, they are the intersections of the hyperplane {η ∈ RS×A | rT η = a} and halfspace {η ∈ RS×A | rT η ≥ a} with the semialgebraic set N µ,βγ of state-action frequencies.

heading: E POSSIBLE EXTENSIONS

heading: E.1 APPLICATION TO FINITE MEMORY POLICIES
text: In general, it is possible to reduce POMDPs with finite memory policies to a POMDP with memoryless policies by augmenting the state and observation space with the memory. Say we consider policies with a memory that stores the last k observations that were made. Then we could set S̃ := S × Ok−1 and Õ := Ok. If the first state is s0 and the first observation that is being made is o0, then we will associate it with s̃0 := (s0, o0, . . . , o0) ∈ S̃ and õ0 := (o0, . . . , o0) ∈ Õ respectively. If after t steps, the current state is s̃t = (st, ot−k, . . . , ot−1) and the next observation is ot, then we set õt := (ot−k, . . . , ot). An analogue strategy can be taken when the memory does consist of more than the history of observations and for example includes the history of decision. It remains open to explore the implications of the translation of our results to policies with internal memory with this identification.

heading: E.2 POLYNOMIAL POMDPS
text: Zahavy et al. (2021) consider MDPs, where the objective is a convex function of the state-action frequency, i.e., where Rµγ (π) = f(η π,µ γ ) for some convex function f : RS×A → R and coin the name of convex MDPs. In analogy, we refer to the case where f is a polyomial function as polynomial (PO)MDPs. In polynomial POMDPs, the problem of reward maximization is by definition an optimization problem of a polynomial function over the set N µ,βγ of feasible state-action frequencies. Since the feasible state-action frequencies form a basic semialgebraic set, the problem of reward maximization in polynomials is a polynomial optimization problem. Hence, the method of bounding the number of critical points as discussed in Section 5 generalizes to the case of polynomial reward criteria. If f is a polynomial of degree d, the upper bound (6) from Theorem 20 takes the form ∏
o∈O dkoo · ∑ i+ ∑ o∈O io=m (d− 1)i ∏ o∈O (do − 1)io .
The use of polar degrees does not extend in general to the case of polynomial POMDPs, since they require a linear objective function, but can still be related to the algebraic degree for a quadratic objective as it is the case for the Euclidean distance function (Draisma et al., 2016).

heading: F EXAMPLES
text: Here, we provide examples, which illustrate our findings. In particular, we compute the defining polynomial inequalities of the set of feasible state-action frequencies for the example from Figure 1 and a navigation problem in a grid world. We use polynomial optimization algorithms to solve thie polynomial programming formulation of POMPDs and see that in this offers a computationally feasible approach to the reward maximization problem.

heading: F.1 TOY EXAMPLE OF FIGURE 1
text: We discuss in detail a toy POMDP which we used to generate the plots in Figure 1. We consider state, observation, and action spaces with two elements each, as well as following deterministic transition mechanism α, observation mechanism β, and instantaneous reward r:
S = {s1, s2}, O = {o1, o2}, A = {a1, a2},
β =
( 1 0
1/2 1/2
) ,
α(si|sj , ak) = δik,
r(s, a) = δs1,sδa1,a + δs2,sδa2,a, γ = 0.5.
The transitions, instantaneous rewards, and observations are shown in Figure 4. As an initial distribution we take the uniform distribution µ = (δs1 + δs2)/2 over the states.
Polynomial programming formulation To illustrate Theorem 16 (and Proposition 14), we derive step-by-step the explicit polynomial program for the reward maximization in this toy example. For this, we first compute the defining inequalities of the set of feasible state-action frequencies. We begin with the linear constraints that define the set N µγ of state-action frequencies of the associated MDP, given in general form in Proposition 8. Further, we denote the state-action frequencies as matrices
η = ( η(s1, a1) η(s1, a2) η(s2, a1) η(s2, a2) ) = ( η11 η12 η21 η22 ) ∈ RS×A.
Following Proposition 8, the linear inequalities are ηij ≥ 0 for all i, j ∈ {1, 2}, and the linear equations are ηTwiγ = (1− γ)µi = 1/4 for i ∈ {1, 2}, whereby here
w1γ = δ1 ⊗ 1− γα(1|·, ·) = ( 1 1 0 0 ) − 1
2
( 1 0 1 0 ) = 1
2
( 1 2 −1 0 ) and
w2γ = δ2 ⊗ 1− γα(2|·, ·) = ( 0 0 1 1 ) − 1
2
( 0 1 0 1 ) = 1
2
( 0 −1 2 1 ) .
Thus the two linear equations are 2η11 + 4η12 − 2η21 = 1 −2η12 + 4η21 + 2η22 = 1.
(29)
It remains to compute the polynomial inequalities, which can be done using Remark 18. We invert the matrix β and obtain
β+ = β−1 = ( 1 0 −1 2 ) ∈ RS×O.
Using the notation from Remark 18 we have So1 = {s1} and So2 = {s1, s2}, and thus the polynomial inequalities are
η11 ≥ 0 η12 ≥ 0
−η11(η21 + η22) + 2η21(η11 + η12) ≥ 0 −η12(η21 + η22) + 2η22(η11 + η12) ≥ 0.
The first two inequalities can be seen to be redundant and can be discarded. Finally, note that the objective function is given by 〈r, η〉S×A = η11 + η22. Hence, we have obtained the following explicit formulation of the reward maximization problem as a polynomial optimization problem:
maximize η11 + η22 subject to  2η11 + 4η12 − 2η21 − 1 = 0 −2η12 + 4η21 + 2η22 − 1 = 0
η11, η12, η21, η22 ≥ 0 η11η21 + 2η21η12 − η11η22 ≥ 0 η12η22 + 2η11η22 − η12η21 ≥ 0.
(30)
Solution with constrained and polynomial optimization tools The formulation (30) allows us to use polynomial optimization algorithms, semi-definite programming (SDP) solvers, or relaxation hierarchies such as the popular Sum Of Squares (SOS). Using the JuMP and Ipopt Julia packages we directly obtained the globally optimal solution to problem (rounded to three digits) 30
η∗ = ( 0.667 0 0.167 0.167 ) .
The corresponding optimal state policy τ∗ is obtained simply by conditioning on states, and any pre-image under the observation kernel is an optimal observation policy, in this case simply π∗ = β−1τ∗,
π∗ = ( 1 0 0 1 ) ∈ ∆OA.
This policy achieves a reward of Rµγ (π ∗) = 〈r, η∗〉S×A = 0.833 (rounded to three digits). The computations took 0.01s (on a 2 GHz Quad-Core Intel Core i5 processor). The command in JuMP to call the optimizer Ipopt is simply:
model = Model(optimizer_with_attributes(Ipopt.Optimizer) @variable(model, \eta[1:2, 1:2]>=0) @constraint(model, 2\eta[1, 1] + 4\eta[1, 2] - 2\eta[2, 1] == 1) @constraint(model, -2\eta[1, 2] + 4\eta[2, 1] + 2\eta[2, 2] == 1) @constraint(model, \eta[1, 1]\eta[2, 1] + 2\eta[2, 1][1, 2]
- \eta[1, 1]\eta[2, 2] >= 0) @constraint(model, \eta[1, 2]\eta[2, 2] + 2\eta[1, 1]\eta[2, 2]
- \eta[1, 2]\eta[2, 1] >= 0) @NLobjective(model, Max, \eta[1, 1] + \eta[2, 2]) optimize!(model)
For completeness, we also provide the command to solve a relaxation in Python SumOfSquares, which is the following, although we found this to run a bit slower depending on the selected degree. Here we negate the objective in order to obtain a minimization problem and square the search variables (which are required to be non-negative) in order to obtain polynomials of even degree:
e11, e12, e21, e22 = sp.symbols(’e11 e12 e21 e22’) prob = poly_opt_prob([e11, e12, e21, e22], - e11**2 - e22**2,
eqs=[+ 2 * e11**2 + 4 * e12**2 - 2 * e21**2 - 1, - 2 * e12**2 + 4 * e21**2 + 2 * e22**2 - 1, + e11**2 + e12**2 + e21**2 + e22**2 - 1], ineqs=[e11**2 * e21**2 + 2 * e21**2 * e12**2 - e11**2 * e22**2, e12**2 * e22**2 + 2 * e11**2 * e22**2 - e12**2 * e21**2], deg=2)
prob.solve() print(prob.value)
Policy gradient methods may not find a global optimum We want to demonstrate an important problem of policy gradient methods, which is the well known possibility to get stuck in local optima, in the case of the toy example. For this, we used a tabular softmax policy model to represent the interior of the policy polytope ∆OA, i.e. used the following parametric policy model
πθ(a|o) := exp(θoa)∑ a′ exp(θoa′) for θ ∈ RO×A.
We computed 15 policy gradient trajectories, where we used the policy gradient theorem (see Corollary 52) to compute the update directions. The starting positions where generated randomly, such that the initial conditions in the policy polytope ∆OA are uniformly random. The trajectories in the policy polytope ∆OA ∼= [0, 1]2 are shown in Figure 5, which also shows a heat map of the reward function. We observe that 5 of the trajectories converge to a suboptimal strict local minimum. Note that this is not artefact of the parametrization, but of the fact that there is a strict local minimum and hence every local optimization method will suffer from this problem. The reward of the suboptimal local minimum
π = ( 1 0 1 0 ) ∈ ∆OA.
is 0.747 if rounded to 3 digits.
Number of critical points We evaluate the bound of Theorem 20 for this toy problem. First note that in this example the observation matrix β is invertible with β−1 = ( 1 0 −1 2 ) . Further, Assumption 13 is satisfied for initial distributions µ with full support. Hence, we can apply Theorem 20. Here, we have |S| = |A| = |O| = 2 and in the notation of Theorem 20 we have do1 = 1 and do2 = 2. As discussed in the main body, the bound evaluates to zero if we consider the interior of the policy polytope, which corresponds to I = ∅. This means that there are no critical points in the interior of the policy polytope, in other words, all optimal policies lie at the boundary and hence have one or more zero entries. The one-dimensional faces correspond to the index sets {(a1, o1)}, {(a2, o1)}, {(a1, o2)}, {(a2, o2)}. The choices I = {(a1, o1)}, {(a2, o1)} correspond to the two edges on the left and right of the policy polytope ∆OA as shown in the top left corner of Figure 1 or alternatively to the two straight faces of the setN µ,βγ of state-action distributions shown in the top right corner. The bound (6) evaluates to zero for those choices. This can also be seen in the bottom row in Figure 1, where it is apparent that there are no critical points on the respective faces. For the choices I = {(a1, o2)}, {(a2, o2)} the bound (6) evaluates to two. Indeed, these faces contain critical points. The bound is not sharp in this case since the actual number of critical points in any of the two faces of the policy polytope ∆OA, which correspond to the two non-linear faces of N µ,βγ is one. Nonetheless, this illustrates how the theorem allows us to discard most faces of the polytope and focus the search for an optimal policy on just two faces.

heading: F.2 NAVIGATION IN A GRID WORLD
text: We consider a grid world depicted in Figure 6 with 13 states and 7 observations. The four actions are {R,L,U,D} corresponding to the directions right, left, up and down on the grid and we denote them with {1, 2, 3, 4}. The transitions are deterministic and lead to the cell right, left, above or below the current cell, if this cell is admissible. Further, we consider deterministic observations, which correspond to the agent being able to observe its immediate four neighboring positions. This observation mechanism partitions the state space into the seven subsets {1, 7}, {2, 4, 9, 10}, {3, 8}, {5}, {6, 12}, {11}, {13}, which lead to the observations o1, o2, o3, o4, o5, o6 and o7 respectively. Hence, by Remark 59 the polynomial constraints are given
by
η7aρ1 − η1aρ7 = 0 for all a ∈ A η4aρ2 − η2aρ4 = 0 for all a ∈ A η8aρ2 − η2aρ8 = 0 for all a ∈ A
η10aρ2 − η2aρ10 = 0 for all a ∈ A η9aρ3 − η3aρ9 = 0 for all a ∈ A
η12aρ6 − η6aρ12 = 0 for all a ∈ A,
where ρs = ∑ a ηsa. The linear constraints apart from η ≥ 0 can be computed to be
ρ1 − γ(η12 + η13 + η14 + η22) = µ1 ρ2 − γ(η11 + η23 + η24 + η32) = µ2
ρ3 − γ(η21 + η33 + η42) = µ3 ρ4 − γ(η31 + η43 + η44 + η52) = µ4
ρ5 − γ(η41 + η53 + η54) = µ5 ρ6 − γ(η34 + η61 + η62 + η11,3) = µ6
ρ7 − γ(ρ1/2 + η72 + η73 + η74 + η82) = µ7 ρ8 − γ(η71 + η83 + η84 + η92) = µ8
ρ9 − γ(η81 + η93 + η10,2) = µ9 ρ10 − γ(η91 + η10,3 + η10,4 + η11,2) = µ10
ρ11 − γ(η10,1 + η11,1 + η11,4) = µ11 ρ12 − γ(η94 + η12,1 + η12,2 + η13,3) = µ12
ρ13 − γ(ρ1/2 + η12,4 + η13,1 + η13,2 + η13,4) = µ13.
Further, the objective function is given by
〈r, η〉S×A = η11 + η12 + η13 + η14.
Let us now consider the uniform distribution µs = 1/13 for s ∈ S as an initial distribution and γ = 0.999 as a discount factor. Like for the toy problem we used the interior point method Ipopt implemented in the Julia packages JuMP and Ipopt to solve this polynomial optimization problem. The solver took around 0.03s consistently (on a 2 GHz Quad-Core Intel Core i5 processor). The
found solution is (rounded to three digits)
η∗ =
 R L U D 1 0.033 0.000 0.000 0.000 2 0.044 0.033 0.000 0.000 3 0.049 0.077 0.000 0.000 4 0.066 0.049 0.000 0.000 5 0.000 0.066 0.000 0.000 6 0.000 0.000 0.033 0.000 7 0.133 0.000 0.000 0.000 8 0.075 0.117 0.000 0.000 9 0.057 0.042 0.000 0.000 10 0.033 0.024 0.000 0.000 11 0.000 0.000 0.033 0.000 12 0.000 0.000 0.017 0.000 13 0.000 0.000 0.016 0.000  ∈ ∆S×A ⊆ RS×A
and has the objective value 〈r, η∗〉S×A = 0.033. The corresponding optimal state policy τ∗ is obtained simply by conditioning on states, and any pre-image under the observation kernel is an optimal observation policy, in this case simply π∗ = β+τ∗ which is (rounded to two digits)
π∗ =
 R L U D
o1 1.00 0.00 0.00 0.00 o2 0.53 0.47 0.00 0.00 o3 0.48 0.52 0.00 0.00 o4 0.00 1.00 0.00 0.00 o5 0.00 0.00 0.99 0.00 o6 0.00 0.00 1.00 0.00 o7 0.00 0.00 0.99 0.00
 ∈ ∆ O A.
This policy
1. moves right on observation 1 corresponding to the states 1 and 7, 2. moves right and left with probability close to 1/2 on observation 2 corresponding to states
2, 4, 9 and 10, 3. moves right and left with probability close to 1/2 on observation 3 corresponding to the
states 3 and 8, 4. moves left on observation 4 corresponding to the state 5, 5. moves up on observation 5 corresponding to the states 6 and 12, 6. moves up on observation 6 corresponding to the states 11, 7. moves up on observation 7 corresponding to the state 13.
The action choices of the policy π∗ are also shown in Figure 7. Note that the policy π̂ selects the best action in the states 1, 5, 6, 11, 12 and 13. Those are the states that are either identifiable from its observation (this is the case for 5, 11 and 13) or where the optimal actions of all states leading to the same observation agree (this is the case for the pairs {1, 7} and {6, 12}). In the other states, where the corresponding observation is ambiguous, the policy randomizes among the two actions, which are optimal for the compatible states. This is for example the case for the states 2, 4, 9 and 10, which all lead to observation 2. The optimal MDP policy would move left in state 2 and 4 and move right in the states 9 and 10. The POMDP policy has to randomize between moving left and right, since otherwise the agent could never reach the goal state if starting in 7 or 13. The same consideration applies to the states 3 and 8, which both lead to observation 3. The Julia code is available in the supplements.

heading: F.3 A THREE DIMENSIONAL EXAMPLE
text: Let us now discuss an example where the set of discounted state-action distributions is threedimensional and not two-dimensional as before. For this, we consider a generalization of the previous example where |S| = 3, |A| = 2 and |O| = 3 such that
dim(∆SA) = dim(∆ O A) = 3 · (2− 1) = 3.
The observation mechanism used is
β =
( 1 0 0
1/2 1/2 0 1/3 1/3 1/3
) .
Further, the action mechanism α and the initial distribution µ are sampled randomly and the used discount factor is 0.5. Since the initial distribution is generic and β is invertible, the set of stateaction frequencies N µγ and the set of feasible state-action frequencies N µ,βγ are three-dimensional and are in fact combinatorially equivalent to the three-dimensional cube ∆SA ∼= ∆OA ∼= [0, 1]3 (see Theorem 16). In Figure 8 we plot a random three-dimensional projection of the sets. More precisely, we plot their one-dimnesional faces dashed and solid for the MDP and POMDP respectively. The combinatorial equivalence to the three-dimensional cube can be see in this plot.

Review summaries:
This paper studies the geometric property of memoryless policy optimization problem for POMDP. The main idea is to formulate the state-action visitation frequency constraint as a polynomial constraint. Then, the degrees on the polynomials are bounded, based on which the number of critical points is obtained.  

This paper studies the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP). It is shown that the (discounted) state-action frequencies and the expected cumulative reward are rational functions of the policy, and the degree is determined by the degree of partial observability. The problem is then formulated as a linear optimization with polynomial constraints. The authors then demonstrate how the partial observability constraints can lead to multiple smooth and non-smooth local optimizers and we estimate the number of critical points. 

In this work, the authors study the problem and structure of memoryless stochastic policies in POMDPs. The focus is on the discounted infinite-horizon problem over finite state-action spaces. For this problem, the authors show theoretical properties on the the problem critical points and provide methods to compute their number.

This paper studies several properties of the landscape of memoryless planning in infinite-horizon POMDPs. The primary focus of this paper is to provide formal expression of (a) state-action frequencies and (b) cumulative reward functions given a set of memoryless stochastic policies. Specifically, they show that both quantities can be expressed as rational functions of polynomial equations. The degree of polynomials used is proportional to the number of possible internal states given a set of observations (Theorem 4). Then, the authors describes the set of feasible state-action frequencies as the solution set to a system of polynomial equations and inequalities (Theorem 16). Finally, they provide the upper bound for the number of critical points in the landscape of policy optimization (Section 5).