The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs
Authors: Johannes Müller
Guido Montufar
Venue: ICLR 2022 Poster (2022)
Keywords: POMDPs
Memoryless Policies
Critical points
State-action frequencies
Algebraic degree

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 demonstrate how the partial observability constraints can lead to multiple smooth and non-smooth local optimizers and we estimate the number of critical points.

Published as a conference paper at ICLR 2022
THE GEOMETRY OF MEMORYLESS STOCHASTIC POL- ICY OPTIMIZATION IN INFINITE -HOTIION POMDPS
Johannes Müller
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany jmuel1 1 erêmi s. www.pp......
Guido Montúfar
Department of Mathematics and Department of Statistics, UCLA, CA, USA Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany montufa @math. ucla edu
ABSTRACT
We consider the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP) with fi- nite state and action spaces with respect to either the discounted or mean reward criterion. We show that the (discounted) state-action frequencics and the expected cumulative reward are rational functions of the policy, whereby the degree is de- termined by the degree of partial observability. We then describe the optimization problem linear optimization problem in the space of feasible state-action fre- quencies subject to polynomial constraints that we characterize explicitly. This allows to address the combinatorial and geometric complexity of the optimiza- tion problem using recent tools from polynomial optimization. In particular, we estimate the number of critical points and use the polynomial programming de- scription of reward maximization to solve navigation problem in grid world.
INTRODUCTION
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., ..s,Stutton& & Barto 2018). Often in practice, the decisions need to be made based only on incomplete information of the state of the system. This setting modeled by partially observable Markov decision processes (POMDPs) introduced by Aström 19655) (for historical discussion see Monahan 1982). which have become an important model for planning under uncertainty. In this work pursue 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 (Aströ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 ct al. 1998 Murphy, 20000). 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 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 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 s by supplementing the state of the system with external memory (Littman 1993. Peshkin et al.] 1999; Icarte et al. 202T). Hence theoretical advances on memoryless policy optimization are also of interest to finite-memory policy optimization. Theoret-

---

Published as a conference paper at ICLR 2022
ical 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 [001]] Li et al. 201 Az-
izzadenesheli 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 that, even in 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 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 c 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 form polytope resp. a com- pact 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 finite union of polytopes. The set of stationary state-action distributions of POMDPs has been studied by MMntúfar et al. (2015) highlighting a decomposition into infinitely many convex subsets whose dimensions depend on the degree of observability. Although this de- composition can be used to localize optimal policies to some extent, 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 pressions and bound their degrees in terms of the observation mechanism. This yields a polynomial programming formulation of POMDPs generalizing the linear programming formulation of MDPs.
This is different to the formulation as a quadratically constrained problem by Amato et al. (2006), where the number and degree of constraints do not depend on the observability. Finally, Cohen & Parmentier (2018) described finite horizon POMDPs as a mixed integer linear program.
Grinberg& & Precup (2033) showed that the expected mean reward is 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 Puteerann 2014). In the case of POMDPs, optimal memoryless policies may need to be stochastic (ssegSingg et al.) 1994). Montúfar et al. (2015); Montúfar & Rauh (2017); Montúfar et al. (2119) obtained upper bounds on the number of actions that need to be randomized by these policies. which in the worst case 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 simpler proof of the bounds obtained by Montúfar et al. (2015).
Neyman (003) 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. Al- though this is not directly related to our work, we take a similar philosophy. We pursue a semi- algebraic description of the feasible set of discounted state-action frequencies in POMDPs, which is closely related to the general spirit of semialgebraic statistics, where this is usually referred to as the implitization problem (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 Nie & Ranestad 2009 Özlüm Çelik al. 2021).
2

---

Published as a conference paper at ICLR 2022
Contributions We obtain results for infinite-horizon POMDPs with memoryless stochastic poli- cies 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 +
2. We describe the set of feasible state-action frequencies as a basic semialgebraic set, i.e., as the solution set to system of polynomial equations and inequalities, for which we also derive closed form expressions (see Theorem [6 and Remark [8).
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 FF). This POMDP generalization of the dual linear programming formulation of MDPs (Kallenberg 1994 Puterman 2014).
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).
PRELIMINARIES
We denote the simplex of probability distributions over finite set X' by Ax. An element μ Ax is a vector with non non-negative entries μ4 = _uzz), x E X' adding to one. We denote the set of Markov
kernels from finite set X' to another finite set y by Az. An element Q A is a [X] [ row
stochastic matrix with entries Qay = Q(ylz), x E X. y E V. Given Q!)) E Ag and Q E A we denote their composition into a kernel from X' to Z by Q Q()) E A Given E Ax and Q E A we denote their composition into joint probability distribution by * Q E Axxy, (p * (z, y) = ((=))(v(z) The support of E R is the set supp(v) = fz E X: us # 0}.
A partially observable Markov decision process or shortly POMDP a tuple (S, O,A a, 3,r). We assume that S, O and A are finite sets which we call state, observation and action space respectively. We fix a Markov kernel a E A which we call transition mechanism and a kernel 33 E Ag which we call observation mechanism. Further, we consider an instantaneous reward vector r E SXA We call the system fully observable if 3 ic which case the POMDP simplifies to a Markov decision process or shortly MDP.
As policies we consider elements E A and call the Markov kernel T π B A its corresponding effective policy. A policy induces transition kernels Px E A SxA Sxx and pr E A by
(s d' d'|ss,) = a(ssas(s))))))))) (a')ss and (s = Σ (a o (aass)a(s)|ss)) s.)).
aEA
For any initial state distribution E As. policy E A defines a Markov process on S x A with transition kernel Pz which we denote by pa,a. For a discount rate 7 E (0, 1) and 7 = we define
1 T-1
(T) = Epr.. (1 (1->) Σ
y (r((s)))))
and RT( = lim Epr. T-
Σ
r(st,a)) an)
r(s
[T]
t=u
1=0
called the expected discounted reward and the expected mean reward, respectively. The goal is to maximize this function over the policy polytope AΩ. For a policy we define the value function V E R via (x) == Rē. (TT, E S, where o, is the Dirac distribution concentrated at 8. A
short calculation shows that (T) = =msa r(s, "nr,a)n""" a) = (r, ))xx) (ahavy et al. 2021 where
(1 7) Eie "p = = = a).
if E (0,
(s. a)
1im T Etd p= =, a), if
Here, 1 is an element of ASxA called expected (discounted) state-action frequency DDerman 1970). (discounted) visitation/occupancyy measure or on-policy distribution (Sutton & Barto 2018).
Denoting the state marginal of 1/5 by pT E As we have + (s, p. (3)( IT 3) s). We
recall the following well-known facts.
Mooe generally, the system is fully observable if the supports of (B(-)))bess are disjoint subsets of O.
3

---

Published as a conference paper at ICLR 2022
Proposition (Existence of state-action frequencies and rewards). Let POMDP, y E [0 and μr E As. Then n P and (T) exist for every т E A and μ E As and are continuous in 7 E (0, for fixed π and μ.
be
For y = we work under the following standard assumption in the (PO)MDP literature
Assumption 2 (Uniqueness of stationary disitributions). If = 1, we assume that for any policy A there exists a unique stationary distribution 1) E ASAA of Pa.
The following proposition shows in particular that for any initial distribution μt, the infinite time horizon aate-action frequency n, is the unique discounted stationary distribution of Pa.
or Proposition (State-action frequencies are discounted stationary). Let A,,, POMDP, y (0, 1] and p E Ag. Then 17," the unique element in ASxA satisfying the dis- counted stationarity equation 17 P Th T.P + (1 (1- * (1 o B)). Further, p. is the unique element in As satisfying p.** = rpp p7 + +1 7)
be
We denote the set of all state-action frequencies in the fully and in the partially observable case by
NH
{ng E ASxA क E {
and
Ny. {1= E Asxa A
We have seen that the expected cumulative reward function : 4 R factorises according to
4 La
T
N
RR x AT n T (r, 1h "T,""")))) SxAA
This is illustrated in Figure We make use of this decomposition in two different ways. First, in Section 3 we study the algebraic properties of the parametrization y of the set of state-action frequencies N In Section we derive description of A74 via polynomial inequalities.
Observation policies
State policies
State-action frequencies
AS
ASXA
TT
A
fa lincar
A ,9
M/ rational
17
N N
N
0
π 1ー R
1ー R rational
3J - R
rational
linear
0.5
0.5
0.5
0.5
0.5
0.5
0
Figure 1: Geometry of POMDP with two states, two actions and two observations. The top shows the observation policy polytope A o. the associated state policy polytope A (yellow) along with its subset of effective policies A (blue); and the corresponding sets of discounted state-action frequencies in the simplex Asx (a tetrahedron in this case). The bottom shows the graph of the expected cumulative discounted reward Rt as function of the observation policy the state policy t; and the discounted state-action frequencies n. We characterize the parametrization and geometry of these domains and the structure of the expected cumulative reward function.
Assumption 2 is weaker than ergedicity, for which well known criteria exist, For y < 1 the assumption is required, since the discounted stationary distributions always unique.
4

---

Published as a conference paper at ICLR 2022
3 THE PARAMETRIZATION OF DISCOUNTED STATE-ACTION FREQUENCIES
In this section we show that the discounted state-action frequencies, the value function and the expected cumulative reward of POMDPs 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 function is a rational function of degree at most k if it is the fraction of two polynomials of degree at most k. By Cramer's 's rule (see Appendix B.2), it holds that
n7 1 a) = ( (s" = ( o B)(als) (1 det - 7P=
del >11
where - 1de denotes the matrix obtained by replacing the s-row of I - -pp with μ.. Since Pr depends linearly on æ and the determinant a polynomial, this is rational function in the entries of π. For the degree, we show the following result in Appendix B.
Theorem 4 (Degree of POMDPs). Let (S, O,A,aa a, 3,r) a, ) be POMDP, μ E As be an initial dis- tribution and Y E (0,1) a discount factor. The state-action frequencies n and p", the value function V and the expected cumulative reward (T) are rational functions with common de- nominator in the entries of the policy æ. Further, if they are restricted to the subset Il S A of policies which agree with fixed policy no all states outside of O S O, they have degree at most
1( E S| ||B(ols) > 0 for some o E =O]l-
Hence, the number of states that compatible with o determines the algebraic complexity of the discounted state-action frequencies, the value function and the reward function. Various refinements of the theorem are presented in Appendix [.I] For the mean reward case and under an ergodicity assumption, Grinberg & Precup (2013) showed that the stationary distributions are a rational func- tion 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):
(Feasible state-action frequencies and value functions form semialgebraic sets). Con- sider a POMDP (S, O, A, a, r. and let μ As be an initial distribution and y (0, discount factor. The set of discounted state-action frequencies and the set of value functions are semialgebraic set.
Corollary
Proof. By Theorem 4 both sets possess rational and thus a semialgebraic parametrization and are semialgebraic by the Serski-Sei theorem (Neyman 2003).
We compute the defining linear and polynomial (in)equalities of the set of feasible state-action fre- quencies in Section g for MDPs and POMDPs respectively, which shows in particular that also in the mean case the state-action frequencies form semialgebraic set. The special properties of degree-one rational functions, which we elaborate in the Appendix [B.] imply the following results. The first one 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 sate-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 (8,A, at r) be an MDP and 7 E (0, 1). Further, let To, Ti most ie states. For any X E [0, 1] let Vx E R and nh ASxA denote the
A be two
policies that differ value function and state-action frequency belonging to the policy To + >(Ti - -oo) with respect to the discount factor 7, the initial distribution Ir and the instantaneous reward r. Then the rational degrees of X + Vx and X + TTx are at most k. If they differ on at most one state 5 E S then
VA= Vo + c(A) (Vi VVi-Ve -V) and n = v/ c(2) (oft -
v/() for all X E [0,
where
c(A) del(I - >
del(I - )
(det(I 7P1) dot([ - ~Po))) + det(T 7Po) X
dc 7Px)
pf
'A semialgebraic set is set defined by number of polynomial inequalities finite union of such sets; for details see Appendix A.2
5

---

Published as a conference paper at ICLR 2022
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 degree-one rational function in every row of the (effective) policy. Since degree-one rational functions attain their maximum in a vertex (Corollary 39), immediately obtain the existence of optimal policy which is determin- istic on every observation from which the state can be reconstructed, which has been shown using other methods by Montúfar al. (2015).
Proposition 7 (Determinism of optimal policies). Let (S,O,A, A,a, a,,,,,,,, (0,,))) be POMDP, μ E As be an initial distribution and , E (0, 1) a discount factor and let π E A be an arbitrary policy and denote the set of observations such that Ks E S B(ols) 0} S 1 by O. Then there is a policy n, which is deterministic on every E O such that (e) 2 R (T).
Proof. For E O, the reward functtin restricted to the o-component of the policy a rational function of degree at most one. By Corollary 39 (see Appendix [B.3.2), there is policy म, which is deterministic on o and satisfies ( 2 R Iterating over o E O yields the result.
On observations which can be made from more than one state, bounds on the required stochasticity were established by Montúfar & Rauh (2017); Montúfar et al. (2019).
4 THE SET OF FEASIBLE DISCOUNTED STATE-ACTION FREQUENCIES
In Corollary 5 we have seen that the state-action frequencies form semialgebraic set. Now we aim to describe its defining polynomial inequalities. In the case of full observability, the feasible state-action freqencies are known to form polytope (Derman, 1970; Altman & Shwartz 1991) which is closely linked to the dual linear programming formulation of MDPs (Hordijk & Kallen berg 1981), see also Figure We first describe the combinatorial properties of this polytope (see Appendix C.1.2) and extend the result to the partially observable case, for which we obtain explicit polynomial inequalities induced by the partial observability under mild assumption. Most proofs are postponed to Appendix[C In Section we discuss how the degree of these defining polynomials allows us upper bound the number of critical points of the optimization problem. We use the fol- lowing explicit version of the classic characterization of the state-action frequencies as polytope (see Appendix (.TI).
Proposition 8 (Characterization of N4). Let (S,A, be an MDP, μ As be an initial distri- bution and 7 E (0, 1). It holds that
N Asx E RSXA (w n)sxA (1- ES} E
(2)
where w 8, @ A ya(s)..). For E 1), AsxA can be replaced by [0, SxA in
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 T = x o 0,3 A the effective policy polytope and denote it by S.3
Note that S.8 is indeed a polytope since is the image of the polytope A under the linear mapping π + π 8 = ßr. Hence, we can write it intersection A S.P A n n C, where 41 C C R.A are an affine subspace and polyhedral cone and describe finite set of linear equalities and a finite set 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. can be approached algorithmically, e.g., by Yourier-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
show in Appendix C.2. Hence, for the purpose of obtaining closed formuulas for the effective policy polytope we make the following assumption. However, our subsequent analysis in Section o can handle any inequalities.
Assumption 10. The matrix
Ag C SxO has linearly independent columns.

---

Published as a conference paper at ICLR 2022
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 3 = (8 3) 3"" An interesting special case is when 3 is deterministic but may map several states to the same observation (this is the partially observed setting considered numerous works). this case, 3+ = diag(n ..... " "10))
where n, denotes the number of states with observation In this case, 3:0 agrees with the conditional distribution ((slo) with respect to a uniform prior over the states; however, this is not in general the case since 5 can have negative entries.
Theorem 12 (H-description of the effective policy polytope). Lel (S, a, be POMDP and let Assumption T0 hold. Then it holds that
5.P A4 Aununc=uncne
(3)
where u E E )- a subspucce C = {T E RSXA g+ 0}
is pointed polyhedral cone and D {r RSXA Ea(Bt)) 1 for all o O} affine subspace. Further, the face lattices of A and A are isomorphic.
Defining polynomial inequalities of the feasible state-action frequencies order to transfer inequalities in A to inequalities in the set of state-action frequencies N/W we use that the inverse of ग + ry" is given through conditioning (see Proposition 46 under the following assumption.
Assumption 13 (Positivity). Let p
hold entrywise for all policies т E A
This assumption holds in particular, if either a > 0 and 7 > or y 1 and μ 0 entrywise (see Appendix C.I. Assumption 13 is standard in linear programming approaches and necessary
for the convergence of policy gradient methods in MDPs (Kallenberg 1994 Mei et al. 2020). By conditioning, we can translate linear inequalities in A into polynomial inequalities in Ng.
Proposition 14 (Correspondence of inequalities), Let (,,), be an MDP, T E A and let " E AsxA denote its corresponding discounted state-action frequency for some p E As and E (0, Let e R. b E RSSA and set S = {s E S bsa + 0fror some a E A}. Then
Σ Tsa 2e 8,0
implies
ΣΣ sES
bsa Asa
II x'ES((s)
noa Σ d'
1 S'ES a'
neaa 2 0,
where the right a multi-homogeneous polynomia in the blocks (Maa )e E TR- with multi-degree 1 E NS. 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 polytope. However, the effective policy polytope is almost never of this box type (see Remark 555).
Example 15 (Blind controller). For a blind controller the linear equalities defining the effective policy polytope in A are Taja Tsza = =[aas1) - (a))2)) = 0 for all A, 82 E S. They translate into the polynomial equalities 1/saaPs DssaPss = 0 for all A, 82 E S. In the case that A =
{a1, }. we obtain
0 = n7 (Neza, + Mezar) Moza, (7 + M).a)) = Me a, 7aza2 nera Regas for all $1, 82 E S,
which is precisely the condition that all 2 x 2 minors of n vanish. Hence, in this case the set of state-action frequencies Ar..8 is given as the intersection of N of state-action frequencies of the associated MDP and the determinantal variety of rank one matrices.
The following result describes the geometry of the set of feasible state-action frequencies.
Theorem 16. Let (S, (S,O,A, ar 3,r) be a POMDP,
E As and E (0, 1] and assume that As- sumption 13 holds. Then we have Ny.3 = N n V B,, where is a variety described by multi-homogeneous polynomial equations and B is a basic semialgebraic set described by multi- homogeneous polynomial inequalities. Further, the face lattices of A and Ny.3 are isomorphic.
A polynomial p: R x... x R R is called multi- mulli-hhmogeneous with multi- (d1,...,d4, dx) (a) E N
if it is homogencous of degree dy in the j-th block of variables for 1,...,

---

Published as a conference paper at ICLR 2022
Remark 17. The variety V corresponds to the subspace U/ and the basic semialgebraic set B to the cone from 3 Further, closed form expressions for the defining polynomials can be computed using Proposition 14 (see also Remark (8). The statement about isomorphic face lattices is in the sense that $ and NTr,8 have the same number of surfaces of a given dimension with the same neighboring properties. This can be seen in Figure[, 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 semialge- braic set B from Theorem 16 are indexed by a E A, O and are given by
Σ (
Pao(1) =E sES.
8ta Usa
II ''ESo((>)
E
II Tof(+) 2 0, (4) SES.
nsta
S:S.-A
((f))((a))
where So 1s E S have |S.1|A|1S. monomials of degree |Sa] of the form IIess, (lf((s) for some f: S. + A. In particular, we can read of the multi-degree of Pao with respect to the blocks (Nea)aEA which is given by 1s. (see also Proposition 14h. A complete description of the set Nu..3 via (in (in)equalities follows from the description of N2 via linear (in)equalities given in (2). In Section 5 we discuss how the degree of these polynomials controls the complexity of the optmization problem.
Bt 03. The polynomials depend only on 3 and not on 7, 1 nor a, and
Remark 19 (Planning in POMDPs as a polynomial optimization problem). The semialgebraic de- scription of the set Ni of feasible state-action distributions allows us to reformulate the reward maximization as a polynomially constrained optimization problem with linear objective (see also Remark 59 and Algorithm [T. This reformulation allows the use of constrained optimization algo- rithms, which we demonstrate in Appendix Fon the toy example of Figure I and grid world. Note that this polynomial program is different to the quadratic program obtained by Amato et al. (2006).
5 NUMBER AND LOCATION OF CRITICAL POINTS
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 [ (see also Poupart et al. 2011] Bhandari & Russo 2019). In the following we use the geometric description of the discounted rate-actioon frequencies to study 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 [ we discuss the mean reward case and an example and describe the sublevelsets semialgebraic sets.
We regard the reward as a linear function pa over the set of feasible state-action frequencies N Under Assumption 13 + syn is injective and has full-rank Jacobian everywhere (sce Ap- pendix C.1.1). Hence, the critical points in the policy polytope A correspond to the critical points of Po 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. Writing 3 {f} E SRA p:(1)) S 0, i E /), we are interested in the number of critical points on the interior of a face,
int (F)) {n E A44,8 (yş(n) = 0 for J, (x))
fori
Note that point 77 is critical on int (F)). if and only if it critical point on the variety V, = (1 E RSSAA | P3 (7) 0 for 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 of optimizing Po(n) subject to (7) = ... Pm (17 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.I for details). Using Theorem [2] Proposition 14
and an upper bound on the algebraic degree of polynomial optimization by NNe & Ranestad (2009) yields the following result.
8

---

Published as a conference paper at ICLR 2022
(0,1), assume that is generic, that E Rx 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:
Theorem 20. Consider POMDP S.
int(F) (F) = { E A T(alo)- 0 if and only if (a, o) E 1}.
Let O = f | (a, o) E 1 for some af and set ko == Iaa (a, o) E 1 as well as do = It
3os #0}l Then, the number of critical points of the reward function on in)(F) )) at most
)
II de DEO
1)) I
Σ II
(5)
-) - 11. If a and μ. are generic, this bound can be refined by computing the polar degrees of multi-homogeneous varieties (see Proposition 27 for for a special case). The same bound holds the mean reward case 7 for I given in Remark 67
where -
-1)
By results from Montúfar & Rauh 2017) 7) POMDP has optimal memoryless stochastic policies with supp x (-1o)] To where L, ssupp ((o)-)] 1. Hence, we may restrict attention to optimization
over over.Nrt Ng. with k = " hi active inequalities (zeros in the policy), where ki = max [A| 1.. 0}.
Over these faces of the feasible set, the algebraic degree of the reward maximization problem is upper bounded by II d - ((A))))) Id. 1) due to Theorem 20
In the special case of MDPs the bound shows that for MDPs only deterministic policies can be Setting 1 == shows that there are no critical points in the interior of the policy polytope A This requires the assumption that / is invertible (see Appendix D.44). The bound in Theorem
critical points of the reward function (see Corollary 62
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).
20
Proposition 21 (Number of critical points in blind controller). Lei (S, a,,,,,,,,,,, be POMDP describing blind controller with two actions, i.e. O = {o} and A = {0I.a2) and let r, r and be generic and let y (0, 1). Then the reward function R has at most [S] critical points in the interior int ( (0, 1) of the policy polytope and hence at most |S| + 2 critical points.
In Appendix D.4
provide examples of blind controllers which have several critical points in (2) and strict maxima at the two endpoints of the interval [o, 1] = A
the interior (0.1)
respectively. Such points are called smooth and non-smooth critical points respectively.
CONCLUSION
We described geometric 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 set and 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 we use polynomial optimization theory to bound 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 grid world to demonstrate that the polynomial programming formulation can offer a computationally feasible approach the reward maximization problem.
basic semialgebraic
Our analysis focuses on infinite-horizon problems and memoryless policies with finite state, obser- vation, 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 challeng- ing problem that remains to be studied using more sophisticated algebraic tools. Possible extensions of our work include the generalization to policies with finite memories sketched in Appendix E. Further, we believe that it is interesting to explore to what extent our results can be used to identify policy classes guaranteed to contain maximizers of the reward in POMDPs.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors thank Alex Tong Lin and Thomas Merkh for valuable discussions on POMDPs, Bernd Sturmfels for sharing his expertise on algebraic degrees and Mareike Dressler, Marina Garrote- López and Kemal Rose for their discussions on polynomial optimization. The authors acknowledge support by the ERC under the European Union's 's Horizon 2020 research and innovation programme (grant agreement no 757983). JM received support from the International Max Planck Research School for Mathematics in the Sciences and the Exangelisches Studienwerk e..ligste...
REFERENCES
Eitan Altman and Adam Shwartz. Markow decision problems and state-action frequencies. SIAM journal on control and optimization, 29(4):786-809) 1991.
Christopher Amato, Daniel S Bernstein, and Shlomo Zilberstein. Solving pomdps using quadrat- ically constrained linear programs. In Proceedings of the fifth international joint conference Autonomous agents and multiagent systems, pp. 341-343, 2006.
Miguel F Anjos and Jean B Lasserre. Handbook on semidefinite, conic and polynomial optimization, volume 166. Springer Science & Business Media, 2011.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Open problem: Ap- proximate planning of POMDPs the class of memoryless policies. In Conference on Learning Theory, pp. 1639-1642, PMLR, 2016.
Kamyar Azizzadenesheli, Yisong Yue, and Animashree Anandkumar. Policy Gradient in Partially Observable Environments: Approximation and Convergence. arXiv:1810.07900, 2018.
Chanderjit Bajaj. The Algebraic Degree of Geometric Optimization Problems. Discrete & Compu-
tational Geometry, 372)1177-191, 1988.
Serguei Barannikov, Alexander Korotin, Dmitry Oganesyan, Daniil Emtsev, and Evgeny Burnaev. Barcodes as summary of loss function's 's topology. arXiv:19/2.00045 2019.
Saugata Basu. Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets. Discrete and Computational Geometry, 30(1):65-85, 2003.
Saugata Basu. Algorithms Real Algebraic Geometry: A Survey, arXiv:1409.1534 2014.
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer- Verlag, Berlin, Heidelberg, 2006.
Jonathan Baxter and Peter L Bartlett. Infinite-Horizon Policy-Gradient Estimation. Journal of
Artificial Intelligence Research, 15:319-350, 2001.
Jonathan Baxter, Peter I. Bartlett, et al. Reinforcement Learning in POMDP's via Direct Gradient Ascent. In ICML, pp. 41-48. Citeseer, 2000.
Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, 6(5): 679-684, 1957.
Jalaj Bhandari and Daniel Russo. Global Optimality Guarantees For Policy Gradient Methods.
arXiv:1906.01786 2019.
Jacek Bochnak, Michel Coste, and Frans--rannoise Roy. Real Algebraic Geometry, volume 36. Springer Science & Business Media, 2013.
Paul Breiding, Türkü Özlüm Çelik, Timothy Duff, Alexander Heaton, Aida Maraj, Anna-Laura Sattelberger, Lorenzo Venturello, and Oğuzhan Yürükk. Nonlinear Algebra and Applications. arXiv:2103.16300, 2021.
Michael J Catanzaro, Justin M Curry, Brittany Terese Fasy, Jänis Lazovskis, Greg Malen, Hans Riess, Bei Wang, and Matthew Zabka. Moduli spaces morse functions for persistence. Journal of Applied and Computational Topology, 4(3):353-385, 2020.
10

---

Published as a conference paper at ICLR 2022
Krishnendu Chatterjee, Martin Chmelik, and Mathieu Tracol. What is decidable about partially observable Markov decision processes with w-regular objectives. Journal of Computer and System Sciences, 82(5):878-95) 911, 2016. URL attpps//wwet httpp///www..c..n.d....... www.eeeeeeeetttcccoooooooo
atticcle/p11//00200000 0000000000000000000000000 6000246
Victor Cohen and Axel Parmentier. Linear Programming for Decision Processes with Partial Infor- mation. 1r 2018.
Robert Dadashi, Adrien Ali Taiga, Nicolas Le Roux, Dale Schuurmans, and Marc G Bellemare. The value function polytope in reinforcement learning. In International Conference on Machine Learming, pp. 1495- PMLR, 2019.
Guy De Ghellinck. Les problemes de decisions sequentielles. Cahiers du Centre d' d'Etudes de Recherche Opérationnelle, 2(2):161-179, 1960.
Francois d' Epenoux. A Probabilistic Production and Inventory Problem. Management Science, 10 (1):98-108, 1963.
Cyrus Derman. Finite state Markovian decision processes. Academic Press, 1970.
Joseph Leo Doob. Stochastic processes, volume 10. New York Wiley, 1953.
Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturmfels, and Rekha R. Thomas. The Eu- clidean distance degree of an algebraic variety, Foundations of Computational Mathematics, 16 119, 2016. URL https: wwwpoooo...o...ooooooooeooooooee 0w000111000/0000 0000:////10000001--2299--90
Dean Gillette. 9. stochastic games with zero stop probabilities. In Contributions the Theory of Games (AM-39), Volume III, pp. 179-188. Princeton University Press, 1958.
Yu Grigor' ev and NN Vorobjov. Counting connected components semialgebraic set in subex- ponential time. Computational Complexity, 2(2):133-186, 1992.
Yuri Grinberg and Doina Precup. Average Reward Optimization Objective In Partially Observable Domains. International Conference on Machine Leurning, pp. 320-328. PMLR, 2013.
J William Helton and Victor Vinnikov. Linear matrix inequality representation of sets. Communica- fions Pure and Applied Mathematics; A Journal Issued by the Courant Institute of Mathemat- ical Sciences, 60(5):654-674, 2007.
Hordijk and LCM Kallenberg. Linear Programming Methods for Solving Finite Markovian De- cision Problems. In DGOR, pp. 468-482. Springer, 1981.
Ronald A Howard. Dynamic programming and Markov processes. MIT Press, 1960.
Jeffrey J. Hunter. Chapter 2
generating functions. In Jeffrey J. Hunter (ed.), Mathematical Techniques of Applied Probability, pp. 24-67, Academic Press, 1983, URL https:://// // //ww:. http://t....o//ccec//eeeeeeeee/e wwtssssiiceeeeeeeeeeeeeeeeeeeees sciencedirect com/
Rodrigo Toro Icarte, Richard Valenzano, Toryn Q. Klassen, Phillip Christoffersen, Amir mas- soud Farahmand, and Sheila A. Mcllraith. The act remembering: A study in partially ob- servable reinforcement learning, 2021. URL https://openrevieet net met/forummio
uF IFkGZz9RId88
Tommi Jaakkola, Satinder Singh, and Michael Jordan. Reinforcement Learning Algo- rithm for Partially Observable Markov Decision Problems. In G. Tesauro, D. Touret- zky, and T. Leen (eds.), Advances in Neural Information Processing Systems, volume 7. MIT Press, 1995. URL URL.hntpss//pprcceddnngs neurips http://s.....pppp/////////
Colin Jones, E. C. Kerrigan, and Jan Maciejowski. Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation. Technical report, Cambridge, 2004. URL
http::/publ iirollccaaee icat iintsinns. lons eng. cam. ac. uk/327023/
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in
partially observable stochastic domains. Artificial intelligence, 101(1-2)999-134 1998.

---

Published as a conference paper at ICLR 2022
Lodewijk CM Kallenberg. Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory. Zeitschrift für Operations Research, 40(1):1-42, 1994.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11)):228-122 2013.
HT Kung. The computational complexity of algebraic numbers. In Proceedings of the fifth anmual ACM symposium Theory of computing, pp. 152-159, 1973.
Amy N. Langville and William Stewart. The Kronecker product and stochastic automata networks.
Journal of Computational and Applied Mathematics, (67(2):429 447, 2004. https:::: //
WWW. wwwencedirecct.................e com/ /tt.:///aaaa//a..//////////////0
Jean Bernard Lasserre. An introduction to polynomial and semi-algebraic optimization, volume 52.
Cambridge University Press, 2015.
Yanjie Li, Baoqun Yin, and Hongsheng Xi. Finding optimal memoryless policies POMDPs under the expected average reward criterion. European Journal of Operational Research, 21)(3); 556-567, 2011. URL http:::/t///t..... wwwp sc scwencediiicceeeeeooooccc www.teedirec.... com/ httpa//t...ccccccceeeeeeetteeeee 5037722171 015772221700048000
Michael L.. Littman. An optimization- based categorization of reinforcement learning environ- ments. In Jean-Arcady Meyer, Herbert L. Roitblat, and Stewart W. Wilson (eds.), From Ani- mals to Animats 2, pp. 262-270. MIT Press, 1993. URL hattp://wwe cs rutgers.
m. www.ttttttaateeeeeeeeeeeteeeeeee sab92. .tt.:s...iiiieeee giveout.p3
Michael L. Littman. Memoryless policies:
Theoretical limitations and practical results. In Proceed- ings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats From Animals to Animats SAB94, pp. 238 245. MIT Press, 1994.
John Loch and Satinder Singh. Using Eligibility Traces to Find the Best Memoryless Policy in Partially Observable Markov Decision Processes. In Proceedings of the Fifteenth International Conference on Machine Learning, ICML '98, pp. 323-331, San Francisco, CA, USA, 1998.
Morgan Kaufmann Publishers Inc.
Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilis- tic planning and related stochastic optimization problems. Artificial Intelligence, 147(1); 5-34, 2003, URL bttps://wwes scissciiinn sciencedi rect. com/ htt///ccinccarrrieee/e SDC04370202003788 Planning with Uncertainty and Incomplete Information.
Alan S Manne. Linear Programming and Sequential Decisions. Management Science, 6(3):259-267, 1960.
Peter McMullen and Egon Schulte. Abstract regular polytopes, volume 92. Cambridge University Press, 2002.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. International Conference on Machine Learning, pp- 6820-6829, PMLR, 2020.
George F. Monahan. A survey of partially observable Markov decision processes: Theory, models, and algorithms. Management Science, 28(1):1-16, 1982. URL http:://wwt jww.orstoroooooo org/
stable/263107)
Guido Montúfar and Johannes Rauh. Geometry of Policy Improvement. In International Conference Geometric Science of Information, pp. 282-290. Springer, 2017.
Guido Montúfar, Keyan Zahedi and Nihat Ay. Geometry and Determinism of Optimal Sta- tionary Control in Partially Observable Markov Decision Processes. 1rXiv:1503.07206 2015.
Guido Montúfar, Johannes Rauh, and Nihat Ay. Task-agnostic constraining in average reward POMDPs. In Task agnostic reinforcement learning Workshop at ICLR 2019. IC1. 2019. URL //tar 201 9, http http:tttuaaaretttaaaararorooooe
12

---

Published as a conference paper at ICLR 2022
Kevin P. Murphy. A Survey of POMDP Solution Techniques. Environment, 2, 10 2000.
Tim Netzer and Andreas Thom. Polynomials with and without determmnntaa reprrstttoonnnneeeeennttoton. Linear algebra and its applications, 437(7):157--159) 2012.
Abraham Neyman. Real Algebraic Tools in Stochastic Games. In Stochastic games and applica- tions, pp. 57-75. Springer, 2003.
Jiawang Nie and Kristian Ranestad. Algebraic Degree of Polynomial Optimization SIAM Journal on Optimization, 20(1):485-500 2009. htt.lttts.//o...gg////o/
Christos H Papadimitriou and John N Tsitsiklis. The complexity of Markov decision processes. Mathematics of operations research, 12(3):4414400 1987.
Lconid Peshkin, Nicolas Meuleau, and Leslie Pack Kaclbling. Learning Policies with External Memory. In Proceedings of the 16th International Conference Machine Learning, pp. 307- 314. Morgan Kaufmann, 1999.
Pascal Poupart, Tobias Lang, and Mare Toussaint. Analyzing and escaping local optima in plan- ning inference for partially observable domains. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 613-628. Springer, 2011.
Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
Johannes Rauh, Nihat Ay, and Guido Montúfar. continuity result for optimal memoryless planning in pomdps. 2021.
Jesus M Ruiz. Semialgebraic and semianalytic sets. Cahiers du séminaire d' d'histoire des
mathématiques, 1:59-70, 1991.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Learning without state-estimation in partially observable Markovian decision processes. In Machine Learning Proceedings 1994, pp- 284-29 292. Elsevier, 1994.
Lucca Sodomaco. The Distance Function from the Variety of partially symmetric rank-one Tensors. PhD thesis, University of Florence, Department of Mathematics and Computer Science, 2020.
Pierre-Jean Spaenlehauer. Solving huugi-h and determinantal systems: algorithms, com-
plexity, applications. PhD thesis, Université Pierre et Marie Curie (Univ. Paris 6), 2012.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy Gradient Methods for Reinforcement Learning with Function Approximation. NIPs, volume 99, pp. 1057-1063. Citeseer, 1999,
Gerald Tesauro. Temporal Difference Learning and TD-Gammon. Commun. ACM, 38(3):58-68, March 1995. URL http::/ddoo..ooooo /10.
Sascha Timme. Numerical Nonlinear Algebra. PhD thesis, Technische Universität Berlin (Ger- many), 2021.
Matthew Trager, Kathlén Kohn, and Joan Bruna. Pure and Spurious Critical Points: a Geometric Study of Linear Networks. In International Conference on Learning Representations, 2019.
Nikos Vlassis, Michael L Littman, and David Barber. On the Computational Complexity of Stochas- tic Controller Optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), (4):1-8, 2012.
Robert Vrabel. A note the matrix determinant lemma. International Journal of Pure and Applied Mathematics, 1 111(4):643-646, 2016.
Stephan Wilhelm Weis. Exponential Families with Incompatible Statistics and Their Entropy Dis- fance. Aeeedrich-Aleaaade--uiiiie Erlangen-Nümmbrrg (Germany), 2010.
13

---

Published as a conference paper at ICLR 2022
John Williams and Satinder Singh. Experimental Results Learning Stochastic Memory-
less Policies for Partially Observable Markov Decision Processes. M. Kearns, S. Solla, and D. Cohn (eds.). Advances in Neural Information Processing Systems, volume 11. MIT Press, 1999. URL http:sss//prrocee.ngss..s neurips cc/paperr1998//110
1cd3862394528876dd 0F18822977777ccaaa1222222-----32 pdf
Tom Zahavy, Brendan O'Donoguue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex MDPs. arXiv:2106.0661, 2021.
Günter M Ziegler. Lectures on Polytopes, volume 152. Springer Science & Business Media, 2012.
Piotr Zwiernik. Semialgebraic statistics and latent tree models. Monographs Statistics and
Applied Probability, 146: 146, 2016.
Karl Johan Aström. Optimal Control of Markov Processes with Incomplete State Information. Jour- nal of Mathematical Analysis and Applications, 10:174-205, 1965. URLtttps:://Lup lub.
u. se/
pdf
Türkü Özlüm Çelik, Asgar Jamneshan, Guido Montúfar, Bernd Sturmfels, and Lorenzo Ven- turello. Wasserstein distance to independence models. Journal of Symbolic Computation, 104: 855-873, 2021.
9074717122301152
14

---

Published as a conference paper at ICLR 2022
APPENDIX
The Sections A postponed proots and elaborate various remarks more detail. Appendix E we discuss possible extensions of results to memory policies and polynomial POMDPs. In Appendix [F] we provide details on the example plotted Figure and provide a plot of three dimensional state-action frequency set.
A-D D of the Appendix correspond to the Sections 2 of the main body. We present the
A Details on the Preliminaries
15
Partially observable Markov decision processes
15
A.2 Semialgebraic sets and their face lattices
17
Details on the Parametrizaton of Discounted State-Action Frequencies
17
B.
I The degree of determinantal polynomials
17
B.2 The degree of POMDPs
19
B.3 Properties of degree-one rational functions
20
Details on the Geometry of State-Action Frequencies
22
The fully observable case
23
The partially observable case
26
Details on the Optimization
30
D.I
Introduction to algebraic degrees
31 ................................
D.2
General upper bound on the number critical points
32 ................................
D.3 Number of critical points in a two-action blind controller
................................
34
D.4
Examples with multiple smooth and non-smooth critical points
................................
36
D.5
(Super)level sets of (PO)MDPs
37
Possible Extensions
38
Application to finite memory policies
38
E.2
Polynomial POMDPS
38
Examples
39
Toy example of Figure]
39
F2
Navigation in grid world
42
A three dimensional example
44
A DETAILS ON THE PRELIMINARIES
We elaborate the proofs that where ommited only sketched in the main body.
A. PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES
The statement Proposition 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
15

---

Published as a conference paper at ICLR 2022
assumptions, we recall that for a (row column) stochastic matrix P, the Cesàro mean is defined by
T
P
lim T-+00
T
t=0
and exists without any assumptions. Further, P is the projection onto the subspace of stationary distribution (Doob 1953). For E 10, the matrix
P3 == (1
Σ = (1--)(( t=
known as the Abel mean of P. where we used the Neumann series. By the Tauberian theorem, Hunter 1983).
holds that P. p for y / Gillette 1958
Proposition (Existence of state-action frequencies and rewards). Let (S, A, be POMDP, y E (0. and μr E As. Then n pr, and (x) exist for every π E A and μ E As and are continuous in r E (0, 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
7 デ (P (1 (u+ (Λ ())
for y E (0, 1) and . = (p (n o 8)). With an analogue argument, the statement follows for the state frequencies and for the reward.
For = we work under the following standard assumption in the (PO)MDP literature
Assumption 2 (Uniqueness of stationary disitributions). Y = 1, we assume that for any policy A there exists a unique stationary distribution 1j ASSA PT.
The following proposition shows in particular that for any initial distribution μ,, the infinite time horizon nate-action frequency ")" is the unique stationary distribution of PT.
Proposition (State-action frequencies are discounted stationary). Let (S,0,A, be POMDP, y (0, and E As. Then n,, is the unique element in ASxA satisfying the dis- counted stationarity equation n PT n n. u (1 -) (xt B)). Further, pr, is the unique element As satisfying pT, Yp pz TM (1 7)p
Proof. By general theory of Cesàro means, (Pf)) projects onto the space of stationary distribu-
tions and hence the Th (PT))* ) (IT B)) is stationary. Hence, by Assumption 2 mh unique stationary distribution. For 7 E (0, 1) we have
a. is the
V J (1 (T o B)) (T-
(T 1)),
which yields the claim. For the state distributions p.: the claim follows analogously or by marginal- isation.
Since the state-action frequencies satisfy this generalized stationarity condition, we sometimes refer to them as discounted stationary distributions.
Asssumption 2 is weaker than ergodicity and satisfied whenever the Markov chain with transition kernel Pr is irreducible and aperiodic for every policy л. e.g., when the transition kernel satisfies > 0. For Y E (0. 1) the assumption is not required, since the discounted stationary distributions always unique since
7 P- invertible because the spectral norm of is one.
16

---

Published as a conference paper at ICLR 2022
A.2 SEMIALGEBRAIC SETS AND THEIR FACE LATTICES
We recall the definition of semialgebraic sets, which are fundamental objects in real algebraic ge- ometry (Bochnak et al. 2013). A basic (closed) semialgebraic set a subset R defined by finitely many polynomial inequalities
= ( /p(2)) 2 O for i E T),
where finite index set and the p; are polynomials. of basic (not necessarily closed) semialgebraic sets, and a function is called semialgebraic if its graph is semialgebraic. By the Sensk--eiienbbrg theorem the range of a semialgebraic function semialgebraic. A simple algebraic set has lattice associated to it, induced by the set of active inequalities. More precisely, for subset J S we set F, = {x E (2(2) = for j E J} and C r} with the partial order of inclusion. We call the elements of F the faces of A. The faces described above are a generalization
semialgebraic set is a finite union
endow the set F = {F,
the faces of a classical polytope and special case of the faces of abstract polytope and 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 V. which satisfy the absortion laws F'V (.FAG) F and F' A (F V G) = F for all F, G.G E F. In the face lattice of basic semialgebraic set, the join and meet are given by
FAG= FnG and FVG:
n H.
HEF: F,GCH
morphism between two lattices and mapping p: F & that respects the join and the meet, i.e. such that (fF ( A =)= (fF) A (G) and ( G) ((F)) V (GG) for all F, G e F. lattice isomorphism is bijective lattice morphism where the inverse is also morphism. We say that two basic semialgebraic sets with isomorphic face lattice are combinatorially equivalent.
B DETAILS ON THE PARAMETRIZATON OF DISCOUNTED ACTTOACTION FREQUENCIES
B.1 THE DEGREE OF DETERMINANTAL POLYNOMIALS
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 sym- metric matrices. We adapt those arguments to the general case and present them here. We call p determinantal polynomial if it admits representation
p(x) = det
Ao +
Σ 1=1
A;Ai
for all x E IR",
(6)
for some Ao.... Am E Raxn, Let us use the notations
A(x) Ao +
A and B(x)
Σ A=A
Proposition 22 (Degree of monic univariate determinantal polynomials). Let A, B E Rax" and A be invertible and XI,...,>n E C denote the eigenvalues of A if repeated according to their algebraic multiplicity. Then,
p: R t det(A + tB)
a polynomial of degree
(eg(p)=1(i- (I....,, + #0} S rank(B).
The roots of p are given by 1-25 1j J} S C. further A is symmetric, then have deg(p) rank(B). B).
17

---

Published as a conference paper at ICLR 2022
Proof. Let J _ {l.....n] n) denote the set of indices j such that X * 0. For + 0 we have
p(t) (cc((c))dtttt + +1A B) x" (ct((A dot (A - + +-1 x" dct(A)xa-1((-t)
t" (-t X,) (-1)--1 II JEJ
(- (t+
jEJ
which is polynomial of degree |J]. Note that [J] is upper bounded by the complex rank of A- B. Since the rank over and R agree for real matrix, we have deg(p) S rank(A-1 = rank B). Assume now that A 11 B is symmetric, then the rank of A B coincides with the number |J| of non zero eigenvalues. Further, the rank of B and 4-111 the same.
Remark 23. Note that the degree of p can be lower than rank(B), (B), for example if
A = and B = 11 - i (1 -1).
Then we have rank B) = 1, but
1 1++1
A 1 1 (1 (1+ -
p()) det
A) + + =1
and therefore deg(p) 0. Note that in this case A-1B B has no non-zero eigenvalues.
Now show that the degree of 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 E R and consider the polynomial
p: R-R- 1 det(A - -B)).
Then either p = or if p(to) * and A1....,AA, An E C denote the eigenvalues of toB) repeated according their algebraic mudtiplicity, then p has degree
deg(p) Hi E (1, (1....,, nn 1 + *OH raak(B).
In particular, it always holds that deg(p) rank B).
Proof. Let without loss of generality p(lo) # then C A lo is invertible. By Proposition 22 the degree of q(t) = det + tB) is precisely Hi > * 0}}- Noting that p(t) = q(t - fo) yields the claim.
The following result generalizes Proposition 24 to multivariate determinantal polynomials.
Proposition 25 (Degree of determinantal polynomials). Let p: R R be determinantal poly- nomial with the representation (6) Then
deg(p) S max rran(((())) | R
Proof. Let us fix I E IR" and for t E IR set f(t) = p(tz) = det(Ao + (B(x)) By the next proposition it suffices show that deg(f) S rank ((x)). However, this is precisely the statement
of Proposition 24
Proposition 26 (Degree of polynomials). Letp: R - R be polynomial. Then there is direction x E R such that t + p(tz) is a polynomial of degree deg(p). Moreover, for any x E R", the univariate polynomial + p(tx)) has degree at most deg(p).
Proof. Let without loss of generality be non trivial. Decompose into its leading and lower order terms = P1 + P2 and choose z E R" such that pi (x) + 0. Let = deg(p). then we have Pr (tx:) p² (x) for all μ R. Since the degree of t + (2rr is at most k 1, the degree of t + p(tx) = pı (tx) + P2 (tx) is k.
'Here, (A( de AT) denotes the characteriztic polynomial of matrix C.
18

---

Published as a conference paper at ICLR 2022
Remark 27. Analogue the univariate is possible to give precise statement on the degree, which is the following. If p is not vanishing and 2o E Rn is such that p(zo) * 0. then A(zo) E R=x* is invertible. Writing A (x)).... ................................ An (z) C for the eigenvalues of A(xo) B(x) and (a:)
for the indices j such that (z(x) + O we obtain
deg(p) - max {1(()) x TER)).
B.2 THE DEGREE OF POMDPS
The general bounds the degree of determinantal polynomials directly implies Theorem 4 which we state again for the sake of convenience here.
Theorem (Degree of POMDPs). Let (S, O,,,a,,,7 be POMDP, μ E As be an initial dis- tribution and E (0. 1) discount factor. The state-action frequencies n,," and p²," the value function V and the expected cumulative reward (T) are rational functions with common de- nominator in the entries of the policy a. Further, if they restricted to the subset II C A of policies which agree with a fixed policy on all states outside of O S O, they have degree at most
{(s S B(oss) 0 for some E =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 (8,0, A, a, B,r) be a POMDP, E As be an initial distribution and yy E (0, 1) discount factor. Then the discounted state-action distributions can be expressed
90.0
11 (8, a)
for every π E A and 8 E S
((T))
where
(TT = (I B)(ss) (a(aaa)((1-1))) (1- det(I- - and ((x) = = - -p
polynomials in the entries of the policy. Further, if qs and q are restricted to the subset II S 2 of policies which agree with fixed policy
all states outside of O C O and if we set = {a E (SS) ((oo))) > O for some E O}, then they have degree at most
dog(qs.a) S max maxrank(p)) -T -0 1s(ss) S
(8)
well
and
deg(g) S max rank(p" PIT S S).
(9)
#En
Proof.
Recall that have
T (s, (I (s
Further, by Proposition 3 the state distribution is given by D7 = (1=))()))))))) Applying
Cramer's rule yields
det( 7p )z
p7 T (s) det - TpX)
where (1-7P")) denotes the matrix obtained by replacing the s-th row - -p2 with μa, which shows 7 For the estimates on the degree, note that
deg(g= (a. S deg(1 - xF + +s(ss)
Further, we can use Proposition 25 to estimate the degree over a subset C A of policies which agree with fixed policy no all states outside of O O. We obtain
deg( - Tp < max rank((T TP
))) = max rank (pT P
wlll
xell
which shows the first estimate in (8) To see the second inequality, we first assume that E S. Then (pf - -Pf)) jo has at most [S] - 1 non zero columns and hence rank at most |S| - 1. s & S, then with the same argument, the rank (p pT 0 = pT PT is at most [S] and the second estimate
in ( holds in both cases. The estimates in (9) follow with completely analoguous arguments. n1
19

---

Published as a conference paper at ICLR 2022
Remark 29. The polynomial q independent of the initial distribution μ, whereas the polynomi- als 9a.a and therefore also their degrees depend on μ. Further, Proposition 24 contains an exact expressions for the degree of the polynomials 9s,a and q depending on the eigenvalues of certain matrices.
Corollary 30 (Degree of the reward and value function). Theorem 28 also yields the rutional degree of the reward and value function. Indeed, it holds tha
(T) Σe,o r(s, a)qa,a (TT) (1 det(I 7 + 2 pt)
7
g(x)
det(1 - ppp))
where used the matrix determinant lemma (Vrabel 2016). and
det(1 - 7Pn + Tx 2 6,) 1 +
Vi (s)
det(1 yPx)
The degree of their denominator is bounded by (9) The degree of the numerator V (8) is bounded by (8) Finally, the degree of the numerator of the reward Rt, is bounded by the maximum degree of the numerators of V (T(()) (s)
over the support of p. An explicit formula for the rational degrees can be
deduced from Remark 27
Corollary 31 (Degree of curves), Let (S. (S.A.a.) r) be an MDP, E As be an initial distribution, E (0, 1) a discount factor and E RSSA Further, let no. Ti A be policies that disagree on l states. Let TIx and V,, denote the discounted state-action frequencies and the value function belonging the policy TΛ TO + X(TI -mo). Then both X +> 7la and V are rational functions of degree at most k.
B.3 PROPERTIES OF DEGREE-ONE RATIONAL FUNCTIONS
B.3.1 LINE THEOREM FOR DEGREE-ONE RATIONAL FUNCTIONS
First, we notice that certain degree-one rational functions map lines to lines which implies that they map polytopes 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 function f: Ω RM is rational function of degree at most k with common denominator if admits a representation of the form f. = pp/q for polynomials p; and of degree 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 policy is fixed all but & states, it is rational function with common denominator of degree at most k.
Proposition 34. Let Ω C TRd be corvex and f: Q > R. be rational function of degree at most one with common denominator and the representation fa(x) = p=(x=//(ax) (a)////(()ooo))))) for affine linear functions Pi, q. Then, ff maps lines to lines. More precisely, if x0 I1 Ωt then
((11)) ((xx)
q(z1)d
c: + A
(g(x1) {(x))){ + q(x0)
is strictly increasing and satisfies
f((1 AJzO + Xx1) (1 --A)((() +c(A))((11) = +(o)))((A((())))) - f(x))). (10)
Further, c is strictly convex if (g(x))) < (q(zo),, strictly concave if (q(x1)) > |a(œo)] and linear if [g(x))1 (g(x1))-
Proof. We set σy = =11 (1-A) + λrι and by explicit computation we obtain
f(xx) = p(Ix) (1 A)p(za) + Ap(z1)
(1 -1 A)g(zo) ((xa) + )g(01) f(1)).
g((x)
((xx)
((xx))
((xx)
Here, u no²
denotes the Kronecker product.
20

---

Published as a conference paper at ICLR 2022
Noting that
Aq(x1)
)g(21)
(1 (1-A)at A)o((z)) >a(x1) = c(A)
g(xx))
and
- {)g(ro)
Aq((1)
(1 N)g(vo) + Ag((n)
=1
((xx)
((xx)
((xx)
yields (00.. Finally, we differentiate and obtain
((1))
((A) ((xx)²
(11)
Since has no root in S2 it follows that ((r)) and g(x1) ) have the same sign and hence c'(A) > 0. Differentiating a second time yields
(A)
((m)) ((xx)
Using that sgn(g(>x)) sgn(g(zn)) sgn(g(>1)) yields the assertion.
Remark 35. The formula 10 holds for all IR for which 2' Xaro (1 A)Ei E
Proposition 36 (Level sets of degree one rational functions). Let Q C R be convex and f: $ R be a rational function of degree at most one. Then, La = {ir E Q f(z) = a} is the intersection of affine space with f2
Proof. For 2, E La the ray fo tty- 2) |t R} is contained in La by the line theorem.
B.3.2 EXTREME POINTS DEGREE- ONE RATIONAL FUNCTIONS
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 Ω C Rd Then we call x E Q an extreme point of S2 if æ is not the strict convex combination of other points in Ω i.e., if æ (1 A)zo + Xx for zo; 21 E Ω and X E (0, implies Hn = z. We denote the set of extreme points of f2 by extr(S2).
Proposition 38. Let Ω C IRd be convex and f: Ω + Rd be rational function of degree at most one with common denominator. Then ((2) is convex and have extr(f(I))) C. f(extr(())).
Proof. Let yo fxo)) Vı
f(1) fQ)). Then by the line theorem, the line connecting yo and
agrees with the image of the line connecting To and under f, in particular, is contained in
(S2) which shows the convexity of f()). Pick now an extreme point y f(x) E extr(f(()) If E extr(1)), there is nothing to show, so let extr Then by the Carathéodory theorem we can write x as a strict convex combination Σ Ayat, A; > O, 2 for some extreme points x;
extr((2). In particular, is possible to write J as the strict convex combination x (1 - -A)ao X by setting Zg
Dizo AzZ Now, by the line theorem we have
y (1 c(A)) + c(A)f(z1).
where c(A) E 1). 1). Since y is an extreme point, this implies f(xo) f(x1) y. In particular, this shows that y = f(x1) E (eetr(()))
Corollary 39 (Maximizers of degree-ome one rational functions). Let S C Rdd be convex and compact set and let f: Ω TR be a rational function of degree at most one with common denominator. Then If is maximized in at least one extreme point of Qt In particular, if is polytope, f is maximized in at least one vertex.
Proof. Since Ω is compact and f is continuous, ((2) a compact interval, lets say f(2) = [a, .8). By the preceding proposition we have {a, 8} extr(f(()) C f(extr(!))), ((e)()))))((((((((()(( maximized in at least one extreme point.
which shows that is
Corollary 40. Let C ddd be a polytope and f: Ω + Ih be a rational function of degree at most with common denominator. Then (P) is polytope and have vert([(P)) C. [(veer(P)).
21

---

Published as a conference paper at ICLR 2022
Proof. By the preceding proposition, f(P) is convex. Further, f(P) has finitely many extreme points since extr(f(P)) C f(ve=t()))(()))) which implies the assertion.
f(ver((P)),
Proposition 41. Let f: R be defined on the Cartesian product P Pi x x P& of polytopes, which is 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([(P)) S [(vert(P)) = [(yert(Pi) x ... x
In parlicular, in 1 this shows that is maximized in at least one veriex of P.
Proof. Let now x = (z(1), x()) E PI x x Pk be such that f(x) E cxtr(f(P)). If If e (Pr), there is nothing to show. Hence, we assume that x(() & vert(P:). Let us denote the restriction of f onto P; by g. where we keep the other components fixed to be x:(3), Then we have g(x(1) E (x))( and hence by Proposition 38 there is z(() E vert(P.) such that g(z(1) g(x(f) = fx)) Replacing (+) by g(()) and iterating over yields the claim.
Remark 42. We have seen that both the value function well as the discounted state-action fre- quencies are degree-one rational functions in the rows of the policy in the case of full observability. Hence, the extreme points of the of all value functions and of the 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 AS,A, r) be an MDP and 7. E 1). Further, let no, T1 E A be two policies that differ on at most le states. For any À E [0, 1] let VA E R$ and n E ASSA denote the value function and state-action frequency belonging to the policy To + {(x To) with respect to the discount factor y, the initial distribution μ and the instantaneous reward r. Then the rational degrees of X Vx and X 1J2 are most k. If they differ on at most one state 8 8 then
V/2 = + c(A) .V) (V1- - Vo) and T = no + +(()) (xr -
v6) for all X E [0,1].
where
c(A) = det(1 - 7PI))
det([ YPX) (det(! - 7P1) det(I ()oo) + det(! - ypo) = X x (3)
det(1 - <P1)>>
Proof. This a direct consequence of Proposition 34 and Theorem 4
Remark 43. The proposition above describes the interpolation speed X- (3) (3)() in terms of the discounted state distribution in 8. 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 = O. Note that the interpolation speed does not depend on the initial condition μ..
Remark 44. Refinements on the upper bound of the rational degree of + VA and À + 7 can be obtained using Proposition 24 Indeed, if we write 7) (x(s,a) = Usa (A)/a(A) like in Theorem 28 those degrees can be upper bounded by
deg(gea) < rank(p1 - 2o) + 1s(s) < rank(pi Po) and deg(4) S rank(pi - po),
where S S is the of states which the two policies differ; also the proof of Theorem 28 for more details on an analogue argument. Hence, the degree of the two curves + V,, and À + 7A upper bounded by rank(p) po).
C DETAILS ON THE GEOMETRY OF STATE-ACTION FREQUENCIES
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 A 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 incqualities. We discuss the special structure of those polynomials and give closed form expressions for them.
22

---

Published as a conference paper at ICLR 2022
C.I THE FULLY OBSERVABLE CASE
Let UT E Asxs denote the expected number of transitions from 8 to s' given by
(1-7)
y (s =8 8141 8111= =6) and
lim
8, 8,411 = =6))
T
t=U
t=0
respectively. Note that we have
(3, = Σ (s,0))((s(ss,))
(12)
aEA
hence 17 is the image of 17, under the linear transformation
:a AsxA + Asxs. T Σ [(ssaaa(("(s..))
(13)
AEE
5,s'ES
Therefore, we can hope to obtain a characterization of N using this mapping. In order to do so, we would like to understand the structural properties of 177 For ? = those distributions have equal marginals since we compute
Σ "s,(', Σ 3'ES
(s',8) lim T-00
pso 8) P =)) -. (14)
T
s'ES
In the discounted case, compute similarly
Σ Vg (s, -
Σ V = (1))
7)
Σ
"p'iil (st = 5)
Σ
20
y
ctlpT (s141 = s)
KES
SES
1=0
=(1 -1 -11-7)u(s)
If we perceive v.. E Asxs matrix, we have shown that
(17*))"1s ((77") ")s + (1 (1-7)),
which motivates the following definition.
We will see that the state-action frequencies is the pre-image of the following polytope under a linear map.
Definition 45 (Discounted Kirchhoff polytopes). For distribution μ As and E (0. 1] define the discounted Kirchhoff polytope (this is generalization definition by Weis 2010)
E = ( E Asxs RXS -TT 1 = I s + (1 -)
where s E R is the all one vector.
So far, we have observed that fa (n7 E E i.c., that
T A ASxA, π T
maps (Et). In order inverse is given through conditioning. The following proposition uses the ergodicity assumption. Proposition 46. Let 7 E 10 and 17 E (Et) and let As denote the state marginal of 1). Set
that this mapping is surjective (= show that its right
<--ss) { [n(-1s)=n(
= n1s, p/p())
p(((s 0 if p(s) 0,
arbitrary element in AA
then we have NF n7.
Proof. We calculate
(),)) = = [ =((((s) Ea(s]s (((s)s),a)n(($)))) 8'.0¹
>T((ass) ((ss'ss)-n =)= ( (1-))))((1-))( -
E Eu(s,s))
= ={als)p(s) - (1 (T -(1
-1- a),
The unique characterization from Proposition 3 of T yields the assertion.
23

---

Published as a conference paper at ICLR 2022
The proposition states that ditioning and is well known in the context of the dual linear programming formulation of MDPs (Kallenberg] [994). Hence, it will be convenient later work under the following assumption in which ensures that policies in A are one-to-one with state-action frequencies.
reconstruct the policy from the itate-action frequencies by
Assumption 13 (Positivity). Let p
hold entrywise for all policies π E A
Note that this positivity assumption holds in particular, if either >> 0 and > 0 or 7 < 1 and a or entrywise. Indeed, a >> 0, then the transition kernel ps is strictly positive for any policy since
Pr (s'1)))= = E(x ())ss))((ssss)) 0,
since (T o (als)) > 0 for some A. Since p7 is discounted stationary with respect pr (Proposition 3). holds that
" (s) = Σ (5'" (1- >
since (s') > 0 for some s E S. If 0 and y 1, then (s)) 2 (1- -))((s)s) > 0. As
consequence of Proposition 46 we obtain the following characterization of N/.
Proposition 8 (Characterization of NWW. Let (S,A,a,)) be an MDP, μ E As be an initial distri-
bution and y E (0, 1]. holds that Nº A 7 fm E SXA (w msxx for E S} Mo
(2)
where w = 8g @ A - >a(ss yor E (0,1), ASxA can be replaced by [0, co)5xA
Instead of proving this proposition directly, we first present the following version of it.
Proposition 47. Let (A,S, a.,) be an MDP and y E (0, 1]. It holds that No: = fa (3
Proof. By 13 and 14 it holds that (a(?)) S , and thus No S fo (3 However, by Proposition 46 for every 17 fa()t) there is policy A such that nT n and hence it holds that
(3
Proof of Proposition g
By the preceding proposition E Na is equivalent to E AsxA and = (n) E = Using the definition of EY this equivalent to
u(s', +1 Ev(o,6) [(d,,)) 7))(s
for s E S. Plugging in the definition of Sa we see that the term on the left hand side equivalent to
ΣΣ a)a(sa) = Σ ((s, = (6. @ 11.7))x4
The first term of the right hand side is precisely
ΣΣ n(s', a)a(s(s's a) =
Hence, we have that (n) E is equivalent the condition
(w,, n)sxA= = (1 - ())ss)) for all E S.
(15)
Note that
{n (wi s)sxA = (1 - -))((s) for all E S) = no + [w] 8 S)+
for an arbitrary element ?/n satisfying 15 This shows the first equation in (2). The second equation
follows from the observation that E. : (1 L. Hence, for y it holds that
(no + [w I E S) n = nno + (wwy I SES) ') (0, 20)
(no + {w I (0,
24

---

Published as a conference paper at ICLR 2022
C.1.1 DERIVATIVE OF THE DISCOUNTED SCATE-ACTION FREQUENCIES
In this section we discuss the Jacobian of the parametrization + 1f" 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 (T) = (1 201-)) (1 (1->P²) -1 (H=TT) is well defined, whenever || < <?-!_ Hence, we can extend TH onto the neighborhood { RSSA 1| " of A which enables to compute the Jacobian of y.
Proposition 48 (Jacobian of V.)) For any policy π E A and s E S, E A holds that
iss (T(T) (I - ((s.)) T) p7. - - 2 6a).
(16)
where
(p * ( (s', a = (d)
(s) @ 6s) ,'',
Hence, a(s.a) (T) is identical the (s, a)tt column of (1--P==) up to the scaling factor of p7 (s). In particular if p7 > for all E S. the Jacobian D has full rank.
Proof. Recall that for invertible matrices A(t), it holds that 0,A(()) ((t)) We compute
(1 (1-7)~10m (T)) = 0(s,a) - ( ((=
(0(,,a) - ) - (1 + +II -I-7P-))- (1saPP))
- (1) (I - -PP)) -1 0 (I -Ppr)) TM
+ (1 -1-p))" ((.a))))))T))
= (1 = -1 ((1 (1-7) 7 (s,a) ( m= + F ((s,))
Further, direct computation shows
((0)...) Pd mn (s, = 0 ((as))((ass)
= =p=pp (s,)
Using the fact that pz." the discounted stationary distribution, yields
(1 (1-7)- ())) (0 PT m² + # ((.,)) ((1 - 71 - pT a + u)) )(s,a)
(1 7- pT, 0(s,)
which shows 16 Note that (I (I- @ 5.) is precisely the (su, au)-th column of the matrix (I - P -1 Those columns are linearly independent, and so are the partial derivatives
((s.a) 1 (T)) given that the discounted stationary distribution PT vanishes nowhere.
Corollary 49 (Dimension of Ntt). Assume that p > entrywise for some policy π E (n)) Then we have
dim(A?") = dim (A |S|[|A] - 1).
Proof. By Proposition 48 the mapping V is full rank in neighborhood of and hence, we have
dim(N?)) = dim (4(( = dim(A
Let us consider a parametrized policy model 1l = { 0 E Q with differentiable parametrization 0 no- Proposition 50 (Parameter derivatives of discounted state-action frequencies). It holds that (p7
0o, 17 1 (T -1-PPT)) -1 No. 00) where (p (o) a) -7*00(s (s))),==((ass))
25

---

Published as a conference paper at ICLR 2022
Proof. This follows directly from the application of the chain rule and (6)..
Using this expression, can compute the parameter gradient with respect the discounted reward F(0)= = (TT) and recover the well known policy gradient theorem, see Sutton et al. (199)..
Definition 51 (state-action value function). We call Q ( R the state-action value function or the Q-value function of the policy æ. Corollary 52 (Policy gradient theorem). It holds that
do, ((0)
Σ Mo. S)
Σ do, mo (8,
My 20. (s, log(To(als))Q"0 Σ 8,a
Proof.
Using the preceding proposition, we compute
0g, (()) (0=00 i 0g. To, 2x*) = Σ P Σ
do (s(
Tly (s, 00 log(ro(dss) Σ 8,a
Remark 53 (POMDPs as parametrized policy models). The case of partial observability can some- times be regarded as a special case of parametrized policies. In fact the observation mechanism B induces linear map π - ı B. This interpretation together with the preceding proposition can be used to calculate policy gradients in partially observable systems.
C.1.2 THE FACE LATTICE IN THE FULLY OBSERVABLE CASE
So far, have seen that the set of state-action frequencies form polytope in the fully observable case. However, not all polytopes are equally complex and thus we aim to describe the face lattice of Ni, which describes the combinatorial properties of polytope. see Ziegler (012)).
Theorem 54 (Combinatorial equivalence of N2 and A)). Let S,,S, be an MDP and y E (0, 1]. Then π + " induces an order preserving surjective morphism between the face lattices of A and Ni; such that for every I S S x A it holds that
E x(ass) = for all (s, a) E 1 + E a(s,a)= = for all (s,a) E 1}. If additionally Assumption 13 holds, this is an isomorphism and preserves the dimension of the faces.
Proof. First, note that the faces of both A and N2 have the structure of the left and right hand side of (54) respectively, which follows from (2). Denote now the left and right hand side in (54) by F and G respectively, then need to show that Y (F) G. For F it holds that
n (s. p. (s)
for all (s. E
and hence n, E G. On the other hand for E G we can set T(|ss) == 17(-ss) whenever defined and any other element such that (a)s)) s) = for all (8,a) E I otherwise. Then we surely have ग E F and by Proposition 46 also n7
17. In the case that p > holds entrywise for all policies т E int(A (AS) the mapping 7/ + nT-l-) defines an inverse to Mr, which shows that the mapping defined in (54) is injective. The assertion 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
C.2 THE PARTIALLY OBSERVABLE CASE
In Corollary S we have seen that the discounted state-action frequencies form semialgebraic set. Now 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 optimiza- tion problem.
26

---

Published as a conference paper at ICLR 2022
Definition 9 (Effective policy polytope). We call the set of effective policies o effective policy polytope and denote it by A.
A the
Note that A
8, is indeed polytope since it is the image of the polytope 4 under the linear mapping क + π o B. Hence, we can write it as an intersection
S A nunc,
(17)
where U,C C R are an affine subspace and polyhedral cone and describe a finite set of linear equalities and finite set of linear inequalities respectively. In the following we will compute those sets explicitely under mild conditions and see that they do not carry an affine part.
C.2.1 DEFINING LINEAR INEQUALITIES OF THE EFFECTIVE POLICY POLYTOPE
Obtaining inequality descriptions of the images of polytopes under linear maps is fundamental problem that non-trivial in general. It can be approached algorithmically, e.g., by mourier-Mozker 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 polytope is finite intersection of closed half spaces H+ = {ar n x 2 a.). it suffices to characterize the image BH+ It holds that
BH+ {y range B nn BTBy a) (v ((B+)= y 2 at) ker ktr(B")+
(18)
where B is pseudoinverse and where we have used that B consists of at most one element by the injectivity of B. Let us now come back to the mapping π + π o 3 = 8T. By the "vec-trick", this map corresponds to vec(Sm/)
(I" 3) veo(T). Hence the linear map is represented by the matrix B = I 2 B. We observe that (I 2 5)+ = & B (see Langville & Stewart, 2004 Section 2.6.3). Notice that B above discussion, if 33 has linearly independent columns, then an inequality (T. n) 2 0 in the policy polytope A corresponds to an inequality (T, (B+)Tn) 2 the polytope A
@ has linearly independent columns if and only if ] does. By the
Assumption 10. The matrix 3 E AS C SxO has linearly independent columns.
Remark 11. The assumption above does not imply that the system fully observable. Recall that if / has linearly independent columns, the Moore-Penrose takes the form 8+ (8th -1 An interesting special case is when 3 is deterministic but may map several states to the same observation (this is the partially observed setting considered numerous works). In this case, g+ = diag(n, ..... (1 ):3 where denotes the number of states with observation o. In this case, Bt agrees with the conditional distribution B(slo) with respect to a uniform prior over the states; however, this is not in general the case since 3 can have negative entries.
Theorem 12 descrriiitn of the effective policy polytope). Let (S,0,A.a, 3,,,) be POMDP and let Assumption AssumptionnOOholl hold.. Then it holds that
A. S.8
(3)
where U O RSXO k= a subspace, C = {T E RSAA g 0} is pointed polyhedral cone and D (T RSSA (a(t+ 1 for all o E O} affine
subspace. Further, the face lattices of 2 and A are isomorphic.
Proof. First, recall the defining linear (in)equalities of the policy polytope A which given by
T(clo)- = (5. < TixA 20 for all E A, O and
Σ (alo) = (6, @ I for all o E O.
Hence, by the general discussion from above, namely by (8). it holds that
S.B A ker(8T) nfr 8+ 2 03 n Σ (8+ = =1 for all o E }).
27

---

Published as a conference paper at ICLR 2022
Note that the linear inequalities E (
redundant in A To this, we note that 1+1s = Lo by the injectivity of 3 and Bl0 = ss. Now we can check that
E(st)) = ΣΣ>
Bost Tsa =
Σ
B+ os
Σ
Tsa =
Σ
Bos 1.
This together with 3 A shows that
A S.P - ker(B") n (T g 0).
The reformulation of the sets and 'D for deterministic observation mechanisms follows from the preceding remark.
C.2.2 DEFINING POLYNOMIAL. INFQUALITIES OF THE FEASIBLE STATE-ACTION FREQUENCIES
Using that the inverse of IT + 17" is given through conditioning (see Proposition we can translate linear inequalities in A into polynomial inequalities in N²", More precisely, we have the following result, which can easily be extended to more general inequalities.
Proposition 14 (Correspondence of inequalities). Let a,, be an MDP, T A and let 7 E ASSA denote its corresponding discounted state-action frequency for some μ E As and (0, Let E IR, RSXA and set S == {s E S bsa + for some a E AA. Then
baa ban Tsa Ze
implies
Asa ΣΣ baa Asa
Σ Moa' S'EM(s)
II
nsa 0, S'ES a²
II
A1Ema
where the right is a multi-homoogneeus polynomia in the blocks (Asa)ae
)ae A E TRA with multi-degree
1 N further Assumption holds, the inverse implication also holds.
Proof. Let 7 E A and let 7) denote its corresponding discounted stationary distribution and p the state marginal. Assuming that the left hand side holds, we compute
ΣΣ
bsausa
II ('S((()
Σ o'
Asta'
ΣΣ aES a
bsaTsaPs
II e'ESMs)
Ps
#ES a
Σ Tea 8,a
II S'ES
II s'ES
Ps 2
Pe'
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 A involving actions of & different states yields polynomial inequality of degree k in the set of state-action frequencies Ni.. In particular, for linearly constrained policy model II C A where every constraint only addresses a single state, the set of state-action frequencies induced by these policies will still form 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 because the projection of the effective policy polytope A onto single state always gives the entire probability simplex A,, which is never the case, if there is non trivial linear constraint concerning only this state.
Theorem 16. Let (S,O,A, a. 3.r) be a POMDP, μ E As and 7 E (0, 1] and assume that As- sumption 13 holds. Then we have NY.8 = NN BV where V is a variety described by multi- multi-homogeneous polynomial equations and B is a basic semialgebraic set described by multi- homogeneous polynomial inequalities. Further, the face lattices of A and Ny.3 are isomorphic.
A polynomial p: R x... XR. R is called multi- muulti-homogeneous with multi-degree (di,...,dR) E N if is homogencous of degree d, in the j-th block of variables for 1,...,
28

---

Published as a conference paper at ICLR 2022
(In)equalities of state policies
(Injequalities of state-action frequencies
A is described by
Ng is described by
<(a|s) 2 0 Row normalization: Ee (a|s) -
n(s, a) 2
MDPs
Discounted stationarity: (we,, 7)) - (1 - ())(())
For y = 1:
Σs, aaa 1 =0
A S.8 is described in A by
N is described in N2 by
Linear (in)equalities
Polynomial (in)equalities
See Section
See Section Proposition
Closed form under Assumption 10
Closed form under Assumption
0
POMDPs
See Theorem 12
See Remark T8 for inequalities
556 See Remark 56 for equalities
Closed form for deterministic observ.:
Closed form for deterministic observ.:
See Remark 57
See Remark 57
Table I: Correspondence of the defining linear and polynomial inequalities of the (effective) state policies and the (feasible) state-action frequencies for MDPs and POMDPs respectively.
Proof. The equation Ni Ni NBBB B is a direct consequence of (3) and Proposition 14 Further, it is clear from Proposition 14 that the mapping V: A - N4t n7 induces bijection of the face lattices of A and N In order to see that the join and meet are respected, we note that for
F,G F(A 5.8 it holds that ((F A G) = (r G) = (FF) n (G) = (PP) A (G). Further, (FFF G) is face of Nr.3 containing (F) and (G) and hence by definition (FF) (G) S
((FV V G). Further, for any face of N containing (F) and (G) it holds that Vi - is
face of A containing and G and hence T T--((T) 2 F V G or equivalently ((FVG) C. L
Comparing [7 and Theorem 16 we that the linear space U corresponds to the variety V, where the cone C corresponds to the basic semialgebraic set B. In general, every linear (in)equality cutting out the effective policy polytope A from the state policy polytope A of the associated MDP corresponds to a polyomial (in)equality cutting out the feasible state-action frequencies Ny. from all state-action frequencies N1i of the corresponding MDP, see also Table This correspondence arises by relating state-action frequencies to state policies via conditioning. Hence, the problem of computing the defining polynomial inequalities of the feasible state-action frequencies reduces to computing the defining linear inequalities of the effective policy polytope. This can be done in closed form ( has linearly independent columns if it deterinistic, see Remark [8] [6 57
Remark 18. By Theorem 12 and Proposition 14 the defining polynomials of the basic semialge-
braic set B from Theorem 16 are indexed by a E A, O and are given by
Pao (n)
Σ
Bt Usa
II 3'ES.((a)
Ensel
n
(
Σ
Σ
g+
II Mef(e) 2 0, (4) SES.
os'
SES.
S:S.AA
(Ef)(((a))
where S, = {s E S 1t 0}. The polynomials depend only on 3 and not on 7, 1 nor a, and have |S.||A|IS. -1 monomials degree |Sa| of the form II Nef(s) for some S, + A. In particular, we can read the multi-degree Pao with respect to the blocks (Mea)aE. which is given by 1ss, (see also Proposition 14). A complete description of the set Neu.8 via (in)equalities follows from the description of No via linear (in)equalities given in (2). Section 5 we discuss how the degree of these polynomials controls the complexity of the optimization problem.
29

---

Published as a conference paper at ICLR 2022
Remark 56 (Defining polynomial equalities). Analogously to the defining inequalities, can compute the defining polynomial equalities in the following way. First, we need to compute a basis {b) Jee of {,.m π 1 ker(g") S RSxA, 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 (b², T)SXA= 0. Hence, by Proposition 14 the corresponding
polynomial cquality is given by
4 ()())=
Σ sES, aEA
Σ
B Us
II ''ES)Mas REE
Σ
Is'a = 0,
(19)
where S3 == {s E Di + 0 for some a E AA.
Remark (Polynomial constraints for deterministic observations). the case, where corre- sponds to a determinstic mapping we can compute all polynomial constraints in closed form. Let us assume that ((oss) = dng(s) for some mapping g: S - O and write S, == g (fo)) S S, then E A belongs to the effective policy polytope A if and only if
r(als1) = r(a(82) for all 81, 82 E Soy E A,
(20)
Note that this can be encoded in E.14((().) 1) = |A[(S) |O]) linear equations; indeed if we fix 8o E So, then (20) is equivalent
ralss) ( (alss) for all E S,
(21)
Another way to derive these linear equalities by noticing that esa E3,a form a basis of (3r) compare also Remark 56 By Proposition 14 1) E .N is equivalent to lie in No. or satisfy
Usa Mn As.0 Σ Msa'
for all So (
(22)
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 3 = 88
((a)) 2 O, where n. = SS.). Hence, the polynomial incqualities (1)) 2 0 are redundant on the cone [0, 0x)
Remark 58. In the fully observable case we have S.S| = 1 for each Hence, each of the polynomial inequalities has a single term of degree Indeed, in this case the inequalities are simply Tsa 2 0, for each a, for each s. In the case of deterministic B, we have 3 Lless//SSo For each o, a, there is an inequality E,: E.:5.-11 1f (a)) ILess 7sf(s) 2 O of degree |Sa equal to the number of states that are compatible with o.
Remark 59 (Reformulation of reward maximization as 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 Once, solution 17" is obtained, the cor- responding state policy T" A can be computed by conditioning, i.c. T(als) == //aa/ /E. Usa' Then, every x² E AΩ with 3TT = T" is an optimal policy. Such a policy can be computed by solv- ing a system of linear equations, which are 3T if 3 has linearly independent columns, it holds that πt = f We demonstrate that this offers computationally feasible approach to planning of POMPDs in Section Fon on the toy example used for Figure I and grid world.
and æ E A which is standard. In particular,
D DETAILS ON THE OPTIMIZATION
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 feasible state-action frequencies AP-.. Since under Assumption 13 the parametrization H 1) is injective and has a full-rank Jacobian everywhere (see Appendix policy polytope A correspond to the critical points of po on Nu.. (Trager et al. 2019). In general,
linear function po over the set of
C.I.I. the critical points in the
30

---

Published as a conference paper at ICLR 2022
Algorithm Polynomial programming for POMDPs
Require: a, 0,8,7,4 1 for s E S do
wº < 62 @ LA- -0-7)()));
end for
for E 0 do
Define Pan according to Equation (4) end for
Compute a basis {b'} of {5T π E RO _ C
for j E J do
Define dj according to Equation
19
end for
1f" + arg max(r, n) sbj to 17 O, (w*, (1 121-700 -7) (ISXAm)) Pao(1) 2 2., (n))))
H + (r,1))
T + (+)) E
A
n' + solution of ÖT TT'
return maximizer rj", optimal value R", optimal policy x²
critical points of this linear function can occur on every face of the semialgebraic set Na... The optimization problem thus has combinatorial and 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 Ny. {17 E SSA: pz(n)= I 0, E 7}. we are interested in the number of critical points on the interior of face
iny( = {n E N p (n)
0 for J, px(n) for i JJ.
Note that a point E int(F')) is critical, if and only if it is a critical point on the variety
V, (n E SxA p3 (n) 0 for j E J}.
For the sake of notation, let us assume that {l...., 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 po(n)) subject to (5( 0 for j = 1,... 1,...,
(23)
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 here and refer the interested reader to the excellent low level introduction by [reiding et al. (202T) and to the references therein. Let us consider the polynomial optimization problem (23). where we do not require Po to be linear. Further, denote the number of variables by n (in the case of state-action frequencies n A)) and denote the degrees of Pn, ..... Pm by do,... ..,....,m-. We call a point critical, if it satisfies the KKT conditions (Vpo(z) 0), which can be phrased as a system of polynomial equations (see Nie & Ranestad (200)) The number of complex solutions to those criticality equations, when finite, is called the algebraic degree of the problem. The algebraic degree determined by the nature of the polynomials Pu. 2m and
=i=1 X, Vp((r) 0. (z) =.... Pm (x)
captures the computational complexity of the optimization problem (Kung 1973 Bajaj 1988
A special case of (23) is when m = n and the polynomials P1, Pm are generic. Then by Bézout's theorem there are exactly d1 ... d, isolated points satisfying the polynomial constraints
and all of them are critical and hence the algebraic degree is precisely d1 ...,,, d (Timme] (02T).
the polynomials .o..... Pm define a complete intersection, i.c., the co-dimension of their induced
9hhe coordinates of critical points can be shown to be roots of some univariate polynomials whose degree equals the algebraic degree and whose coefficients rational functions of the coefficients of po,...g Pm.
31

---

Published as a conference paper at ICLR 2022
variety is + 1, the algebraic degree of (33
is upper bounded by
d1
dm
Σ
(do 1)
f0. ... (dm - 1)mm
(24)
1o
and this bound is attained for generic polynomials (Nie & Ranestad 2009 Breiding et al. 2021
For non-complete intersections, the expression (24) does not need to yield upper bound if some constraints are redundant. However, we can modify the expression to obtain a valid upper bound.
Indeed, if and
denote the dimension and co-dimension of
== { Pı = =... = Pm (x) = 0}
and if Pu is generic and the degrees are ordered, i.e., d1 2 ... 2 dm then the algebraic degree
upper bounded by
di de
Σ
(do - i.. ... (do - 1)²².
(25)
To +5,=
To see this, fix subset J {l.....
m) of cardinality c, such that V fx p2(2)) 0 for j E J}.
Then we can apply the bound from 24 and evaluate it to be
II JEJ
Σ
(do 1) II(d, 1)6,
iot E,tt,e i-=
JEJ
which is clearly upper bounded by (25). If po is linear, then dg 1 and the expression simplifies to
d1 ...d de
Σ
(d1 - 1)th (de 1)¹r
If further d, 1 for i 2 lo for some k S c, then obtain
dj
Σ
(d1 1)th (d: 1)ah
(26)
p 1i.... Pm are affine linear (and general position relative to Pı..... Pk. the algebraic degree of 23 is given by the (m kt) polar degree (V) of the variety
v= (1 1 = (1) = 0}.
see Draisma et al. (0166; Özlüm Çelik et al. 2021). This relation is particularly useful, since for state-action frequencies there always active linear equations described in (2). The po- lar degrees of certain interesting cases (Segre-Verte 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 Ozlüm Çelik et al. (2021).
Remark 60 (Genericity assumptions). In the case, where the polynomials Po. Pm generic, there might be infinitely many critical points. Indeed, even for linear program, i.e. when all polynomials
linear, there might be infinitely many and even a non-trivial face of global op- tima. This is however not the case if Po is generic. Hence, the genericity assumptions 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 ö, @ 1 - -aaas)))))) in which cases the reward function would be constant and every policy would be global optimum.
the reward
D.2 GENERAL UPPER BOUND ON THE NUMBER OF CRITICAL POINTS
E (0,1), assume that is generic, that E Sx0 is invertible, and that Assumption 13 holds. For any given I C A O consider the following set of policies, which is the relative interior of a face of the policy polytope:
Theorem 20. Consider POMDP (8,0,A,
int(F = { E A (allo)- = 0 if and only if (a, o) E ET]
Let O = f0E (a, o) E I for some a} and set ko == Ia (a. o) E T}] as well as d, = lis
3,11 / O}}. Then, the number of critical points of the reward function int(F) ) is most
)
[[db d
OEO
Euso
where 1 |S[(|A 1) II. If and μl are generic, this bound can be refined by computing the
polar degrees of multi- multi-hoooggeneus varieties (see Proposition 27 for a special case). The same bound holds in the mean reward case 7 for I given in Remark 67
32

---

Published as a conference paper at ICLR 2022
Proof. The face G of the effective policy polytope corresponding to F is given by
int(G) = A T) 0 0 (a, =1
In order describe the corresponding set of discounted state-action frequencies, we use the notation
Pao(1) =
Bos
Nsa
II
Σ Ns'
SESo
s'ESo((a)
then it holds that
N {n E N2 (Po(()) 2 for all E A,
Then, F and G correspond to the face
int(H)=
{1 E AQu Pao = 43 (a, E
(n E Pao(1)) and equality if and only if (a,o) E /].
In order to use the explicit description of N3 given in 2 we remind the reader that w. 8
1. - Then, holds that
(H) = { E [0, oo)
(T) 2 and equality if and only (a, o) E
(w Sx (1 7)p, for s E S),
where we used Proposition 8 Since the discounted state distributions are all positive by assumption, for 17 E HH) it holds 7ea 0 if and only if r(a) s) == na(as)) O. Note that T = и 3 for some E A by assumption and thus for int H) it holds that Tea = 0 if and only if
0 ralss) = Σ B(ols)=(alo),
which holds if and only if o) E for every o O with B(oss) Hence, if we write = {(s,a) a) (a, o) E I for all o E O with B(o]s) > 0}, we obtain
(H) = E RSXA
Mea and equality if and only if (s, a) J,
(w 8)xxA= (1 7)H, for S,
(ao( 0 and equality if and only if (a, E
The number of critical points over this surface is upper bounded by the number of critical points over
= = CineRs
RSA
Usa 0 for (s. a) E J,
(wr, m)sx = (1 (1-7)), for E S, S.Pao(1) for (a. o) E I].
generic. Further, we see that there are |/| non-linear constraints and hence in the notation of (26 have k 17]. Further, we can calculate to dimension and co-dimension of as follows. Note that F - V, π ++ 17" 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
Now we want to apply (26) and note that the objective Po
= dim dim F) = S - 1) - |7| = |S||A| - SS| - [7]-
The co-dimension of V is given by |S||A|| (V) = S1 [|| + || and with the notation from 26). we have e [S| + |7| 2 k. Further, it holds that deg(pao) S d, and using (26) yields upper bound
of
II d (c,0)E1
Σ
II
(d, - 10
the oE0
II
Σ
II
(d. 1)
Emewer Jeo=m (0,01EI
Eo b. o5O
33

---

Published as a conference paper at ICLR 2022
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 M/" has the extra linear condition that Esa 7a = 1, see also Proposition g Indeed, in the mean reward case we have with the notation from the proof above
int(II) = {1 E SSAA Meaa and equality if and only if (s, EJ,
(w n)sxA = 0 for & E S,
Σ Maa = 1,
sa
Pao(1) 2 0 and equality and only if (a, o) EI].
Hence, the upper bound in 5 remains valid if we set
1= dim {
SxA M/ 0 for (s, a) J, (w for E ES,
Σ Nsa 1, Pao (n) for (a. E 1
(27)
In the discounted case we obtained an explicit formulation for 1. In the mean case the value obeys case distinction depending, in particular, whether the all ones vector 1s lies in the span of the vectors wy However, the value can be computed from the above expression (27) any given specific case."
Corollary 62 (Critical points of MDPs). Consider MDP (S.A, Y E (0, 1), assume that is generic, that 3 E RSxO is invertible. and that Assumption 13 holds. Then, every critical point A of the discounted expected reward function is deterministic.
Proof. We evaluate the bound of Equation 5p. If the face is not a vertex, then the corresponding
index set A x O satisfies !7| < [[A 1) and thus in the notation from Theorem 20 it holds that I >> O. Note that d, in 5 that vanishes and so does the whole expression in (5).
for every E O and hence there is at least one factor in the product
Remark 63 (Geometry around the critical points). The key argument in the proof of Theorem 20 is that a critical point E 4 of the reward function corresponds to a critical point 1) of linear function over a multi- multi-hommggeeous 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 ( 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 2021) showed that planning in POMDPs is stable under perturbations of the observation kernel B. More precisely, consider two observation kernels B, 3' Ag satisfying [|3())s) - 3'(1ss)llvv
approachable for gradient based methods. |Rauh et al.
(oo(())) (// < for every E S. Then if π E A is an optimal policy of (S,A, O, a, 8', r), then it is a 22>/|r]lo>/ - -opotialll policy of (S, A, a,,,3,,, 3, Hence, does not fulfill the invertability assumption made in Theorem 20 an arbitrary small perturbation of it does (given that 3 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 guar- anteed to contain an optimal policy by Montúfar & Rauh (011)) might be considerably fewer for the POMDP (S, A, O, a, Sr, r)) The bound (5) could used to identify the best perturbations of given magnitude to obtain 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.
D.3 NUMBER OF CRITICAL POINTS IN A TWO-ACTION BLIND CONTROLLER
This subsection is devoted the proof of Proposition 21 that restate here for convenience.
34

---

Published as a conference paper at ICLR 2022
Proposition 21 (Number of critical points in blind controller). Ler (S,0,A, be POMDP
describing a blind controller with two actions, i.e. O = {o} and A = {a1, 02) and let r, a and μ be generic and let y (0, 1). Then the reward function R has most |S| critical points in the interior ( (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 7 E (0, 1). We associate the policy polytope A with [0, 1] and for E [0, 1] we write Tp and 17 for the associated policy and the state-action frequency. From Theorem we know that the reward function R = ʃ/g: [0. 1] IR is rational function of degree at most k = SS, which is well known to possess at most 2k 2 critical points. Hence, there are at most this many critical points 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 27 First, note that since is generic and Y < Assumption 1 sat- isfied. In this case, the combinatorial part is simple, since there are only two zero-dimensional faces of the actenaction frequencies (corresponding one-dimensional face (corresponding to the interior of the unit interval). Let us set
the endpoints of the unit interval) and one
U = {1 E SxA
(wi,, n)sxAA = (1 - 7)1s for all 8 E S),
where w == 6. @ 1 - (a(s) -) By Proposition and Example 15 the set of discounted state- action frequencies is given by
N N nD = 10,, 00) nu D1.
Like above, we associate the policy polytope 4 with [0, 1] and for E [0, 1] we write Tp and 17" 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 (n/ Ip E (0, 1)} where used that Assumption 13 holds. Further, recall that 17 (als) / P2, we have that
na(ass) > for all s E SS e A} {n p (0, 1)3 {n E A16
= { Usa > 0 for all s E E,
= =00,00)5x4 nunD;
Thus the number of critical points over [17²) | E (0, 1)} are upper bounded by the number of critical points on 2/ nD), Note that if and μ are generic, the subspace U/ is in general position. Further, its dimension is [S] - |S| = [S]. where we used |A| 2. Hence, the number of complex solutions the KKT conditions over 2/ Di are given by the k-th polar degree dz (Di), where k [S], where we also used the genericity of the reward vector. We can compute the polar degree using the formula presented by Özlüm Çelik et al. (2021) obtain
8n (Di)
k-2k+k+2
Σ
(-1)²
k - s ++1
) (k 8)s
Σ i+j=s
2k (k 1)
(k
i)!
(2 1 j)!
==0
2 t: 18-8+17 ++11 k 1 (k- - s)!
(K)
(
Σ
(-
(k
i)!
(2 1 j)!
0=0
it
We calculate the three individual terms to be
x+1)
Σ
(k 1)k
k!
(b)
(I: + 1)k²
A: -
(A: - i)!
(2 1 - j)!
2
(k - 1)!
1!
2
and
-(6 6 )
(
k
2
(K- 1)!
- kt
+
- 1) - 2k.
111
(k 2)
(k - 1)!
(k 2)!
(I: 1-)1
35

---

Published as a conference paper at ICLR 2022
and
k 1-1 1 (k- 2)
(1)
(
(k - 2)! -2)! (1K= -2) 2)
2k
+ k(k 1)
(kc 2)
(k - (k-3)1
2(k 3)1
2k + k(k ( - 2)
2
Adding those three summands we obtain
(2(D,) A.a + k2
+
13
31.
2k
1.3 + 122
2h:
2h:
k.
2
Note that there also a more structural argument to obtain this polar degree. In fact, the polar degree 6, (D1)
for > dim(Di) - 1, where Dj denotes the dual variety of Dj (Özlüm Çelik ee al. 2021). Note that in the case of x matrices Dj = D2 (Draisma et al. (016) and hence holds that (D2) 0 for / 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 (x, = degree (Di) degree(Di)
(Spaenlehauer 2012).
Note that this bound is not necessarily sharp, since it is exactly the number of complex solutions of 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.
D.4 EXAMPLES WITH MULTIPLE SMOOTH AND NON-SMOOTH CRITICAL POINTS
is the goal of this example to demonstrate that for a blind controller multiple critical points can occur in the interior (0, 1) = int (n) as well as the two endpoints of [0, 1] = A 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 01, d2 and three states 81, 82, 83 and a deterministic
transition kernel a and reward described by the graph shown in Figure
(1 5
01 -30
a22
a1, 0
02, 30
82
83
022 -5
Figure 2: Graph describing the deterministic transition kernel a and the associated instantancous rewards.
We make the usual identification [0. 1] _ A where we associate p with x (anlo)) Figure 3 the reward function is plotted on the left for the three initial conditions f 8z, 8,, 8.z- It is apparent the policy polytope A ~ [0, 1] for the two initial conditions μ ô., dag. For μ deg. there 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] critical points in the interior and at most [S] + = 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 occur for
that the reward has two critical points in the interior
36

---

Published as a conference paper at ICLR 2022
generic and The right hand side of Figure 3 shows three dimensional random projection of the set of feasible discounted state-action frequencies. By Theorem 4 they are curve x R with injective rational parametrization of degree at most |S 3.
starting at s_3
starting at s_2 starting at
Discounted reward
0.0
0.2
0.4
0.6
0.8
1.0
Probability selecting first action
Figure 3: Plot the reward function for initial distributions d, on the left and of a three-dimensional random projection of the set of feasible discounted state-action frequencies the right.
D.5 (SUPER)LEVEL SETS (PO)MDPS
D.5.1 CONNECTEDNESS OF SUPERLEVEL SETS IN MDPS
Theorem 66 (Existence of improvement paths in MDPs). For every policy A there is continuous path connecting и to an optimal policy along which the reward is monotone. If further + 17th injective, the reward is strictly monotone along this path, if a is suboptimal. In particular, the superlevel sets of MDPs are connected.
Proof. Let us fix π E A and set yo == 11" and ?h be a global optimum and d)t be the linear interpolation and Pt be the corresponding state marginal. Note that for E S it holds that either pe(s) 0 for all t E (0, 1) or pr(s) = for all t E [0, 1]. the latter case, we can set (-1s) to be an arbitrary element in A. For the other states and E (0,1) we can define the policy through conditioning by Te (a|s) = (e (s)) and will continuously extend the definition to t E f0. then the definition extends naturally. Suppose that (n()) = 0, then we now that pi (s) > 0 since otherwise (x()) = for all E [0, 1). Now for > 0 holds that
in the following. If Pu(s) > or P1 (s)
= (e(s, a)
(1 t))o(s. a) (s, tm (m a) M (s.
(x(
(1 (s) (p)(s)
(p1(s) (1())
which extends continuously to = 0. If (s) = O, then like before, (e(. does not depend on f
and we extend /. 1. Now have constructed continuous path ne, such that 17 Y) and thus
R(xe)) (r, m²) (1 () no) + Krr, m) R(mo) + + R(To)),
which is strictly increasing To is suboptimal.
remains to construct a continuous path between To and π. Note that if (s) >> 0, the policies лo and agree the state and does the linear interpolation between the two policies. Now, by Proposition 46 we see that every linear interpolation between To and has the state-action distribution V/n- Gluing the two paths, obtain a path that first leaves the state-action distribution unchanged and then increases the reward strictly up optimality.
D.5.2 THE SEMIALGGEBAICC STRUCTURE OF LEVEL AND SUPERLEVEI. SETS FOR POMDPS
Consider POMDP (S, O, r) and fix discount rate 7 E (0, 1) as well an initial condition μ E As. The levelset
Tag { 1 RT) a}
37

---

Published as a conference paper at ICLR 2022
of the reward function is the intersection of variety generated by determinantal polynomial of degree at most |S] with the policy polytope 4 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((z) ag(T)). Thus, the levelset is given by
Lg = f R f(x) - ag(x) =0}-
Analogously, a superlevel set is the intersection
ag E BOXA f(x) 2 0}
of a basic semialgebraic generated by one determinantal polynomial of degree at most [S] with the policy polytope - In particular, both the levelset and superlevel sets of POMDPs are semialge- braic sets defined by linear incqualities and equations (corresponding to the conditional probability polytope 12) and determinantal (in)equality of degree at most (S). This description
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 al. (020). By the- orem due to Lojasiewicz, level and superlevel sets possess finitely many connected (semialgebraic) components (Ruiz 1991: Basu et al., (2066) and there exist algorithmic approaches to computing the number of connected components (Grigor's 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 variety. we apply the Milnor-Thom theorem to the vari- cty V we obtain that there are at most (2( 1)) 01 -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 {1 E R (r, SxA = a} and halfspace (17 E RSSAA 1) 2 a} with the semialgebraic set N of state-action frequencies.
E POSSIBLE EXTENSIONS
E. APPLICATION TO FINITE MEMORY POLICIES
In general, it is possible to reduce POMDPs with finite memory policies to a POMDP with mem- oryless 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 x O and == Ok If the first state is 80 and the first observation that is being made is oo. then we will associate it with &n == (so. op, op....,oo) oo) E S and ōy == (oo...., on) E O respec- tively. If after steps, the current state is 5, (st, Ot-A: ..., 0;-1) and the next observation is or, then we set o; == (o........ o.). 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. remains open to explore the implications of the translation of our results to policies with internal memory with this identification.
E.2 POLYNOMIAL POMDPS
Zahavy et al. (2011) consider MDPs, where the objective is convex function of the state-action fre- quency, i.e., where (T) (( for some convex function f: RSSA + RR and coin the name of convex MDPs. In analogy, we refer to the case where f is polyomial function (PO)MDPs. In polynomial POMDPs, the problem of reward maximization is by definition an op- timization problem of a polynomial function over the set N2 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 bound- ing 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 (5) from Theorem 20 takes the form
polynomial
k II DEO
Σ
(d-
- 1)¹ II (d. 1)
O
++
&m
38

---

Published as a conference paper at ICLR 2022
The 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 quadratic objective it is the case for the Euclidean distance function (Draisma et al. 2016).
F EXAMPLES
Here, we provide examples, which illustrate our findings. In particular, we compute the defining polynomial inequalities of the feasible state-action frequencies for the example from Figure and navigation problem in grid world. We use an interior point method to solve the constrained optimization problem corresponding to the polynomial programming formulation of the respective POMPDs and see that in this offers computationally feasible approach to the reward maximization problem.
F.1 TOY EXAMPLE FIGURE
We discuss in detail toy POMDP which we used to generate the plots in Figure 1 We consider state, observation, and action spaces with two elements cach, as well as following deterministic transition mechanism a, observation mechanism B, and instantaneous reward
S { )
[01, )
B
1/2
1/2)
r(s, a) = d + 8 00
7 0.5.
A = {aI, )
(5s ag) 6sk:
The transitions, instantaneous rewards, and observations are shown in Figure As an initial distri- bution we take the uniform distribution = (6., + //2 over the states.
1
81
01
02
01, +1
$1
82
02 +1
1/2
82
1/2
d1
Figure 4: The left shows the transition graph of the toy example. The right shows the observation mechanism; the numbers on the edges indicate the observation probabilities.
Polynomial programming formulation To illustrate Theorem 16 (and Proposition 14 de- rive step-by-step the explicit polynomial program for the reward maximization in this toy example. For this, 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 asso- ciated MDP, given in general form in Proposition g frequencies as matrices
In the remainder, denote the state-action
m[(1 01) n(s1, d2) (132, a1)
n( 0z)
M11
1/22
E SRS
1221
1722
Following Proposition the linear inequalities are Mi 2 for all í. E 2), and the linear
equations are (wi, SxA = 7)14 1/4 for E
(1, 2}. whereby here
11
1 1
0
= 1
1 (1 2
/ = 2 4 (a(1)
0
0
2
0
and
0
1
0
1)
1
1
0 -1) 2
1
3 = 52 2 1 (2));)) =
=
2
2
Thus the two linear equations are
21/11 + 47/1 21/21 = 1
(28)
22/22 4721 + 27p22 1.
39

---

Published as a conference paper at ICLR 2022
It remains to compute the polynomial inequalities, which be done using Remark 18 We invert the matrix /3 and obtain
- (1) 2) R
Using the notation from Remark 18 have So {81} and Soz 82). and thus the polyno- mial incqualities are
71
1/12 2 0 Th (721 + 1/22) 21/21 (111 + 1/22)
(12 + 1222) 21/22 (711 + 7722) 2 0.
The first two inequalities can be seen to be redundant and can be discarded. Finally, note that the objective function given by
SxA = 7/1 + 122-
Hence, we have obtained the following explicit formulation of the reward maximization problem as polynomial optimization problem:
21/11 + 41/12 27/21
1
2m/1
4121
21/22
1 0
maximize 7/1 + 722 subject to
711 712 f/2 1/22 2
(29)
1117/11
2//21/112
1111/22
7127/22 + 2//17222 7727//2 2 O.
Solution with constrained and polynomial optimization tools The formulation (29 allows us use polynomial optimization algorithms, semi-definite programming (SDP) solvers, relaxation hierarchies such as the popular Sum Of Squares (SOS). Using the modeling language JuMP and the interior point solver Ipopt. we directly obtained the globally optima solution to problem (29) (rounded to three digits)
0.667
77 =
0.167 0.167
The corresponding optimal state policy r* obtained simply by conditioning on states, and any pre-image under the observation kernel is an optimal observation policy, in this case simply x² 3 3-
(
1
E
1
This policy achieves reward of (Tt") (r, )=) 0.833 (rounded three digits). The computations took 0.01s (on a 2 GHz Quad-Core Intel Core i5 processor). The command in JuMP call the optimizer Tpopt simply:
model = Model (opt:imiiie_..tt_atttrrrb @variable (model, leta[1122 1:2]>=0)
(Tpopt. Opt imi zer)
@constraint (model, 2\eta[1, 1] 4\eta[1, 2] 2eeaa 12, 1] -- 1)
@constraint (model, -2\eta(1, 21 + 4eeta 1] + 2\eta 21 1)
éconstraint (model, \etall, 11 1] 22, 1] [t, 21
\eta 1] 2] >= 0)
(mideeeeet \eta[l, 2]
2etaal, 1] 2]
- [1, 2] [2, 1] >= 0)
eNLobjective (model, Max, Neta[l, 1] + \etal2, 21) optimize (model)
For completeness, we also provide the command solve a relaxation in Python SumOf res, which is the following, although we found this to bit slower depending the selected de- gree. Here we negate the objective in order to obtain a minimization problem and square the search variables (which required to be non-negative) in order obtain polynomials of even degree:
The SOS relaxation provides certificate for global optimality in this
40

---

Published as a conference paper at ICLR 2022
el1, e12, e21, e22 ap. so.syylolsss el2 e21 e22')
prob = poly_oppe Bttly_op__aag probpprobbtt ([el1, e12, e21, e22], ell+*2 c22**2,
eqs=(+
el1*+2 + 4 e12**2 2 e21**2 - 1, 2 * e12+*2 - ** e21**2 + e22**2 1,
+ ell++2 e12x*2 + e21**2 e22**2 11,
[peqs=(ell++2 * e21**2 + 2 e21*+2 e12+*2 - ell++2 e22+*2,
e12**2 e22xx2 + +2 ell*+2 e22**2 e12**2 e21**2], deg=2)
print (prob. value)
Policy gradient methods may not find global optimum We want to demonstrate 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, used a tabular softmax policy model to represent the interior of the policy polytope A A i.e. used the following parametric policy model
exp(Ooa) Ea cxp(Ooor) for 0 ROOA
To (alo)
We computed 15 policy gradient trajectories, where we used the policy gradient theorem (see Corol- lary (52) to compute the update directions. The starting positions where generated randomly, such that the initial conditions in the policy polytope A are uniformly random. The trajectories in the policy polytope A [0, 1J² are shown in Figure which also shows a heat map of the reward function. We observe that 5 of the trajectories converge to suboptimal strict local minimum. Note that this is not artefact of the parametrization, but the fact that there is a strict local minimum and hence every naive local optimization method will suffer from this problem. The reward of the suboptimal local minimum
(1 0 E A
is 0.747 if rounded to 3 digits.
R
0.7308
12
0.6
0.6228
0.4
0.5148
0.4608
0.2
0.4068
0.3528
0.0
0,2988
0.2
T (22(2)
Figure 5: Policy gradient optimization trajectories (shown black curves) in the observation policy polytope. As expected, since the problem is non-convex and has several distinct local optimizers, the trajectories converge to different local optimizers depending on the initial policy.
Number of critical points We evaluate the bound of Theorem 20 for this toy problem. First note that in this example the observation matrix 33 is invertible with 3 (212) Further, Assump- tion 13 is satisfied for initial distributions i with full support. Hence, we can apply Theorem 20 Here, have |S| |A| 10)
and in the notation of Theorem 20 we have d, 1 and
d,, = 2. As discussed in the main body, the bound evaluates to zero if we consider the inte-
rior of the policy polytope, which corresponds to 0. This means that there
critical
41

---

Published as a conference paper at ICLR 2022
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 ((1,,1)) ), ((22, 01)]. {(a), 02)). {a2g, 02)]. The choices I {(), 01)), {(22, 01}} correspond to the two edges on the left and right of the policy polytope A as shown in the top left corner of Figure or alternatively to the two straight faces of the set Vi of state-action distributions shown in the top right corner. The bound (5) evaluates zero for those choices. This can also be seen in the bottom row in Figure [ where it is apparent that there are no critical points on the respective faces. For the choices / {(11 (2)), { 02)] the bound (5) evaluates
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 4 which correspond the two non-linear faces of Nir. is one. Nonetheless, this illustrates how the theorem allows discard most faces of the polytope and focus the search for an optimal policy on just two faces.
F.2 NAVIGATION IN A GRID WORLD
3
4
5
7
10
11
12
13
Figure 6: Depiction of grid world; the reward of R is obtained in state 1, the actions {R, L. U, corresponding to movements to the right, left, up and down; observed are the pos- sible directions that the agent can move Once the agent transitions state 1, she transfers to state 7 and 13 uniformly.
We consider the grid world depicted in Figure 6 with 13 states and 7 observations, where it the goal to reach state The four actions are {R, L,U, D} corresponding to the directions deterministic and lead to the cell right,
right, left, up and down on the grid. The transitions left, above or below the current cell, if this cell is admissible; from the goal state one tran- sitions uniformly to the states 7 and 13 independently of the chosen action. Further, sider deterministic observations, which correspond to the agent being able to observe its imme- diate four neighboring positions. This observation mechanism partitions the state space into the seven subsets (),7), (2,4, 4,9, 9, 10), (3. 8), (5), (6, 12), (11), (13), which lead to the observations 01, 02, 03, 04, oz, Og and 07 respectively. Hence, by Remark the polynomial constraints given by
MaP1 MaP? = 0
for all E
naaP2 12aP4 0
for all A
MsaP2 1/2PP8 = 0
for all E A
720PP2 12aP10 0
for all E A
TeaPs TysaPy = 0
for all E A
T/26P6 16aP12 = 0
for all E A.
42

---

Published as a conference paper at ICLR 2022
where Ps Eo nsa The linear constraints apart from 7) 2 0 can be computed to be
P1 7/h2 + 1/1 + 111 + 122 = P1
P2 7(11 1/23 + 7/4 + 1/22 112
03 7(721 + 1/3 + 7742 = F33
P1 7111 7/3 + 7/14 + 1762] M4
P5 7//111 + 1/53 + 1/54 = 145
P6 7 (734 7/6 7622 + 1/1,3) M46
PT - (p1 2 + 772 + 7/7 + + 7882 = P4T
Ps 7171 7/8 + 1781 + (al2 WM8
P9 7v1s1 + 7/3 + 7/,,2] = 14
P10 71791 7/10,3 7/1,4 + 1/1,2) M410
P11 7 (711,1 + 711,1 + 71,11 = P11
P12 7194 7/2,1 712.2 + 7/3,3) M12
P13 - (p1/2+ + 7/2,1 + 713,1 + 713.2 + 73344) = 113-
Further, the objective function is given by
(r,1)xxA= = 7/1 + 1/12 + 1/13 + 7/14-
Let us now consider the uniform distribution nt, 1/13 for E 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 2 GHz Quad-Core Intel Core i5 processor). The found solution is (rounded three digits)
R
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
ASxA C R
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
and has the objective value (r,1")sxA = 0.033. The corresponding optimal state policy r" is obtained simply by conditioning on states, and any pre-image under the observation kernel is an optimal observation policy, in this case simply π
8+a* which is (rounded to two digits)
L
U
D
01
1.00
0.00
0.00
0.00
02
0.53
0.47
0.00
0.00
03
0.48
0.52
0.00
0.00
04
0.00
1.00
0.00
0.00
A
05
0.00
0.00
0.99
0.00
06
0.00
0.00
1.00
0.00
07
0..00
0.00
0.99
0.00
This policy
1. moves right on observation 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,
43

---

Published as a conference paper at ICLR 2022
3. moves right and left with probability close to 1/2 observation 3 corresponding to the states 3 and 8,
4. moves left on observation corresponding to the state
5. moves up on observation 5 corresponding the states and 12,
6. moves up observation 6 corresponding to the states 11,
7. moves up observation 7 corresponding to the state 13.
The action choices of the policy n² are also shown in Figure 7 Note that the policy á selects the best action in the states 1,5, 6,5,6, 11, 12 and 13. Those are the states that 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 the case for the pairs (1, 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 and 4 and move right in the states 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 and under https: //qptttt....//..g com mue ler johannes/ geometzy Stometzy-POOle POMDP s ICLR- [CLR-2022
f
+
+
+
Figure 7: Depiction of the policy स, which is found using the polynomial programming formulation of the POMDP and applying the interior point method Ipopr implemented in the Julia libraries JuMP and Ipopt: an arrow into two direction indicates that the agent moves into those two directions with probability close to 1/2.
F.3 A THREE DIMENSIONAL EXAMPLE
Let us now discuss an example where the set of discounted state-action distributions is three- dimensional and not two-dimensional before. For this, we consider a generalization of the previ- ous example where [S| = 3, |A| = 2 and |0| such that
dim A dim 2 = 3 (2 =.
The observation mechanism used is
1
0
0
1 //
1
1/2
0
1/3
1/3
1/3/
Further, the action mechanism a and the initial distribution j are sampled randomly and the used discount factor is 0.5. Since the initial distribution generic and 8 is invertible, the set of state- action frequencies Ni and the set of feasible state-action frequencies Aq..3 are three-dimensional and are in fact combinatorially equivalent to the three-dimension cube A z A z [0. 1 (see Theorem 16). In Figure we plot random three-dimensional projection of the sets. More precisely. plot their one-dimnesional faces dashed and solid for the MDP and POMDP respectively. The combinatorial equivalence to the three- fire-dimensional cube can be see in this plot.
44

---

Published as a conference paper at ICLR 2022
Figure 8: A random three-dimensional projection of the set of discounted state-action frequencies of the MDP is the polytope defined by the dashed straight edges. The same random three-dimensionall projection of the set of feasible discounted state-action frequencies is the basic semialgebraic where the edges are shown by the solid lines. Both of those sets are combinatorially equivalent to three dimensional cube.
45


Reviews:
[{"review_id": "qHhY-yrZfTi", "reviewer": "Reviewer_JQge", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is well-written and I enjoyed reading, and the tools and ideas are novel. To the best of my knowledge, this appears to be the first study of the geometry of memoryless stochastic policy search for POMDPs. It would make the paper stronger if more simulation results, for example, on the geometry around the critical points, and/or compare with the case with finite-memory policies, etc. In other words, though highly nontrivial and I appreciate it, only asserting on the upper bound on the number of critical points seem not super useful. As an initial attempt, it might be also valuable to try some numerical examples to have more insights on the scenarios where the theory cannot cover. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "Here are some (relatively minor) comments:\n\n1. Terminology. I think usually in RL we refer to the \"expected (discounted) state-action frequency\" here as \"(discounted) visitation/occupancy measure\". Calling it \"frequency\" sounds a bit non-standard to me.\n2. Proposition 22, should the mapping p being from t to $det(A+t B)$ (instead of $det(A+\\lambda B)$)?\n3. I was wondering how the results in the current paper reconcile with the results in Azizzadenesheli et al., '18? It seems that in that paper, some \"Gradient dominance\" property can be established, which should lead to some global convergence results. Since it is a closely related paper, a more detailed comparison seems necessary.\n4. I was wondering whether the results in Sec. 5 can be extended to the case with $\\gamma=1$ (average reward case)? If not, what would be the technical hurdles? Some discussion might be needed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WzT83NTxguV", "reviewer": "Reviewer_ejas", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting, well written and the ideas introduced appear to be novel. I have the following comments:\n\nThe presentation is at times somewhat dry. Commentary on the implications of some of the statements would benefit the paper. In this regard, while theoretical properties are always welcome and of interest. It is not very clear what is the direct application of the author's work is. E.g., what is the practical importance of bounding the number of critical points? Can the resulting number be exploited in the construction of efficient algorithms? Can the author's illustrate this in numerical examples?", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper appears to be novel and well written. I am somewhat concerned on how interesting it might be to the community at large, due to its focus on theoretical properties with no clear direct application. In this regard, it it not entirely clear to this reviewer that ICLR is really the correct venue for this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RMp3MTwk2g7", "reviewer": "Reviewer_4HAL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents an interesting set of theoretical properties about the landscape of planning in infinite-horizon POMDPs. It is interesting to know that key quantities as visiting frequencies or expected values of POMDP can be expressed as a fractional function of polynomial equations. Most importantly, degree of polynomials is proportional to a certain measure of observability (the number of possible internal states). \n\nMy main criticism is about the implication of results. While several interesting discoveries are presented in order, it does not provide much implications to actually solving the planning problem, or deeper understandings of POMDP. The paper is also quite heavy on notation and terminologies, and thus hard to follow. IMO, applying the results to a few more interesting toy examples would have helped a lot. I liked the blind-controller example. \n\nI wonder if the authors can provide more explicit forms of the optimal policy if we consider a weaker version of partial observability. For instance, one may consider the case when a single observation comes from a single internal state w.h.p (relaxation of cardinality based measures). Another easier partially observability might be the case where the only partial observability is decided at the start of episode and non-changing or slowly-changing.", "summary_of_the_paper": "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). ", "summary_of_the_review": "The paper considers an important and challenging problem, with a set of new interesting theoretical discoveries. I think this is a right step to move forward understanding POMDPs, and could be a nice addition to literature, and thus I recommend acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6l6pH-1KUID", "reviewer": "Reviewer_TytX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \nPOMDP is a very hard problem, and so is the memoryless policy optimization problem for POMDP. This paper sheds some light on the geometry of this non-convex problem, and I appreciate the effort and the mathematical rigor. I enjoyed reading the paper. \n\nWeakness:\n\nWhile this is a hard problem, the results in this paper are far from the practice in most senses. I am not sure how the bound on the number of critic points will be helpful for policy optimization algorithms in practice. \n\nFor example,  the authors can think about whether the bound in (5) can help identify “easy” cases, i.e. problems with one or relatively few critical points. \n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "As I said, this is a hard problem and the authors obtained some interesting results. Yet, I am not sure ICLR is the best venue for this paper. Maybe a more theoretic-focused venue is more relevant. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of finding an optimal memory less policy for POMDPs.  This work makes an important theoretical contribution.  The reviewers are unanimous in recommending the acceptance of the paper.  Well done!
Decision: Accept (Poster)