Steady-State Policy Synthesis in Multichain Markov Decision Processes

1 Introduction

There has been a focus in recent years on the verification of autonomous systems by leveraging techniques used for decades in the model checking of software [Fisher et al., 2013]. While this verification step is crucial for the development of robust autonomous capabilities, a promising complementary approach is to design these capabilities in such a way that the search for a correct design is driven by the same specifications used for verification. This methodology is often called correct-by-design construction [Haesaert et al., 2015] or formal/controller synthesis [Kress-Gazit et al., 2018]. Our contribution is in the same vein and entails the search for policies which satisfy constraints on the steady-state distribution of the resulting agent as it interacts with its environment for an indefinite period of time following said policies. It is worth noting that progress in this area has interesting applications to problems where steady-state distributions are commonly used. This includes the derivation of maintenance plans for various systems such that asymptotic failure rate is minimized [Boussemart and Limnios, 2004] [Boussemart et al., 2002] as well as to problems in constrained routing where average delay and packet loss metrics must be enforced [Lazar, 1983] [Skwirzynski, 1981].

Steady-State Policy Synthesis (SSPS) is framed in the context of constrained Markov Decision Processes (MDP) that model the agent-environment dynamics. This framework has long been studied in the stochastic dynamic control and operations research literature to handle multi-objective decisionmaking in the presence of uncertainty. The pioneering work of Derman [Derman, 1970] and Altman [Altman, 1999] developed a constrained optimization framework to dynamic control problems based on linear programming for both the discounted and total reward, as well as the expected average reward formulations. The vast majority of existing work, however, have focused on ergodic or unichain structures. This was pointed out recently by Altman in [Altman et al., 2019], where it is stated that "...the existing theory for solving such problems requires strong assumptions on the ergodic structure of the problem". Under such assumptions, averagereward constrained MDPs have been shown to admit efficient solutions owing to an established one-to-one correspondence between the optimal solutions of a formulated linear program (LP) and the optimal policies of the MDP. The notable work of Kallenberg in [Kallenberg, 1983] has laid the groundwork for Markovian control problems and their characterizations in multichain settings and the construction of optimal policies based on linear programming under several optimality criteria. However, the algorithms developed to construct an optimal policy for general multichain structures were shown to be computationally prohibitive for the expected average reward formulation.

Summary of contributions. In this paper, we make three main contributions. First, we introduce the Multichain Steady-State Policy Synthesis over Edge Preserving Policies (MaStEr) problem as a generalization of the SSPS and steadystate control problems studied in [Velasquez, 2019] and [Akshay et al., 2013], respectively. In particular, given a multichain MDP, we seek a policy in a predefined class of policies that maximizes an expected reward signal while enforcing steady-state specifications on the behavior of such a policy. In sharp contrast to [Akshay et al., 2013], we dispense with the strong assumption about the ergodicity of the underlying MDP, which requires that every stationary deterministic policy induces an ergodic (i.e., recurrent and aperiodic) Markov chain. Further, unlike [Velasquez, 2019], we neither search for a policy that induces a recurrent Markov chain consisting of all the states within the given MDP, nor require the existence of such a chain. For example, it may very well be the case that such a recurrent chain does not exist if some states are inevitably transient. As our second contribution, we develop a scalable multi-step approach to synthesize a policy that provably meets the asymptotic steady-state specifications through the use of a novel linear programming formulation. Our third contribution lies in deriving important theoretical results, including sufficient conditions for the existence of a one-to-one correspondence between the feasible solutions of the proposed LP and the steady-state distributions of the Markov chains induced by the synthesized policies, and in turn establishing provable performance and behavior guarantees for the derived policy. To the best of our knowledge, this is the first work to allow synthesis of stationary steady-state policies with verifiable behavior in multichain MDPs.

2 Background

In this section, we introduce preliminary definitions and notation used throughout the paper. The vector e denotes the vector (of appropriate dimension) of all ones and T the transposition operator. Given a vector x and index set V , the vector xV := [xv], v ∈ V . By |S|, we denote the cardinality of a set S. For an integer n > 0, the set [n] := {1, . . . , n}, and A\B denotes the set difference of sets A and B.

Definition 1 (Markov Chain). A Markov chain is a stochastic model given by a tuple M = (S, T, β), where S is the state space, T the transition function T : S × S → [0, 1] with T(s′ |s) denoting the probability of transitioning from state s to state s′ , and β the initial state distribution. With slight abuse of notation, the transition function can also be thought of as a matrix T ∈ [0, 1]|S|×|S| , where the (s, s′ ) entry T(s, s′ ) = T(s′ |s). Its use will be clear from the context.

Given a Markov chain M = (S, T, β), a state s ∈ S is said to be transient if there is a non-zero probability of never returning to s given that we start in s. A set of transient states is termed a transient set. We define an isolated component I as a set of states in M that can never be visited, that is, βI = 0 and I is not reachable from any state in S \ I, i.e., ∑s′∈I T (s′ |s) = 0, ∀s ∈ S \ I.

Definition 2 (Markov Decision Process (MDP)). An MDP represented by the tuple M = (S,A, T,R, β) is a probabilistic automaton, in which S denotes the state space, A the set of actions, T : S × A × S → [0, 1] the transition function with T(s′ |s, a) denoting the probability of transitioning from state s to state s′ under action a, R : S × A × S → R a reward obtained when action a is taken in state s and we end up in state s′ , and β the initial distribution. We often use the alternative reward function R : S × A → R, where R(s, a) := ∑s′∈S T(s′ |s, a)R(s, a, s′ ). By A(s) ⊆ A, we denote the set of actions available in state s.

Definition 3 (Terminal Strongly Connected Component (TSCC)). Consider the digraph formed by an arbitrary Markov chain or MDP M with state space S and initial distribution β. A Terminal Strongly Connected Component (TSCC) S′ ⊆ S is a strongly connected component reachable from some initial state s, β(s) > 0 and with no outgoing transitions to any state in S \ S′ . We denote by r(M) = ⋃k∈[m] rk(M) the set of states in the m TSCCs of M, with rk(M) ⊆ S denoting the kth TSCC. The complement set is denoted by ¯ r(M) := S \ r(M). In the case of Markov chains, this is the set of transient or isolated states.

Definition 4 (Markov Chain Induced by a Policy). The tuple Mπ = (S, Tπ, β) is the Markov chain induced by a policy π : S × A → [0, 1] in an underlying MDP M = (S, A, T, R, β), where Tπ(s′ |s) = ∑s∈A(s) T(s′ |s, a)π(a|s) and π(a|s) is the probability of taking action a in state s.

Definition 5. An MDP M is called unichain if the Markov chain Mπ induced by any admissible deterministic policy π is unichain, that is, consists of exactly one closed recurrent set and possibly some transient states. An MDP is said to be multichain if it is not unichain.

Definition 6. Given an MDP M and policy π, the steadystate distribution Pr∞π : S ×A→ [0, 1] over the state-action pairs (also known as the occupation measure) is the longterm proportion of time spent in state-action pair (s, a) as the number of transitions approaches ∞, i.e.,

where St and At are the state and action at time t. Also, Pr∞π (s) := ∑a∈A(s) Pr∞π (s, a) is the steady-state probability of being in state s ∈ S.

Definition 7 (Steady-State Specification [Velasquez, 2019]). Given an MDP M = (S,A, T,R, β) and a set of labels L = {L1, . . . ,LnL }, where Li ⊆ S, a set of steady-state specifications is given by Φ∞L = {(Li, [li, ui])}nL i=1 . Given a policy π, the specification (Li, [l, u]) ∈ Φ∞L is satisfied if and only if ∑s∈Li Pr∞π (s) ∈ [l, u]; that is, if the steadystate probability of being in a state s ∈ Li in the Markov chain Mπ falls within the interval [l, u]. An MDP M = (S,A, T,R, β,L,Φ∞L ) augmented with the label set L and specifications Φ∞L is termed a labeled MDP (LMDP).

Lemma 1. [Kallenberg, 1983] Given an MDP M = (S,A, T,R, β) and policy π ∈ ΠS, where ΠS is the set of stationary policies, the steady-state distribution Pr∞π := {Pr∞π (s, a)}s,a of the Markov chain Mπ is given by (2), where T ∞ π := limn→∞ 1n ∑nt=1 T tπ is the Ces`aro limit.

3 RelatedWork

The problem of arbitrating control in discrete-time MDPs has been studied for many decades, with LP solutions based on occupation measures being proposed in [Manne, 1960; De Ghellinck, 1960] for unichain MDPs. While such LPs can easily handle steady-state constraints in unichain settings, serious issues arise when a similar approach is used for multichain MDPs, as described in the pioneering work [Kallenberg, 1983]. In particular, it was shown that there is not a one-to-one correspondence between the feasible solutions of the augmented LP and the stationary policies. Instead, the space of feasible solutions is partitioned into equivalence classes of various feasible solutions mapping to the same policy. The key deficiency is that the steady-state distribution of the Markov chain induced by the synthesized policy does not match the optimal solution to the LP in general, and so the derived policy does not always meet the steady-state specification constraints.

To work around these difficulties, existing works either impose severe restrictions on the input MDP, or allow the production of troublesome non-stationary policies. One common restriction excludes multichain MDPs altogether. The most restrictive requirement can be found in [Akshay et al., 2013] and the reinforcement learning algorithms of [Bhatnagar and Lakshmanan, 2012], which assume that the input MDP is ergodic or irreducible, respectively. These MDPs guarantee that the Markov chain induced by any stationary and deterministic solution policy is itself ergodic or irreducible, thereby ensuring a valid solution to the steady-state equations. The authors proceed to find policies in such MDPs which satisfy a set of steady-state specifications. Though the steady-state control problem defined therein is described in the full generality of Markovian and history-dependent policies, an equivalence between the two is established and the solutions proposed focus on the latter. The works of [Ross, 1989; Altman, 1999; Feinberg, 2009] contain a slight relaxation in that unichain MDPs are allowed. Nonetheless, the strict underlying requirement of a single recurrent class remains.

The unichain MDP assumption is dissolved in [Velasquez, 2019], where the SSPS problem is introduced as a generalization of steady-state control. The solution proposed finds a policy which induces a recurrent Markov chain and maximizes the average reward objective while satisfying a set of steady-state specifications, if one exists. The work in [Velasquez, 2019], however, cannot reason about multichain MDPs, as it requires the existence of a policy which induces a strongly connected Markov chain containing all states in the MDP and optimizes over such policies. Therefore, this effort fails to produce a policy in the most general setting.

To eliminate restrictions on the input MDP, another line of work allows non-stationary policies as output. The first example of this appears in [Kallenberg, 1983], where the proposed algorithm produces a policy with a different decision rule for each time step. Not only is the policy impractical to apply, but the algorithm itself is computationally intractable.

In contrast to the aforementioned methods, our approach is computationally tractable, works with the most general MDPs, and always produces a stationary policy.

4 Multichain Steady-State Policy Synthesis

We begin with a simple motivating example. Suppose some autonomous agent is stranded on three connected frozen islands as pictured in Figure 1. The agent's mission is to build a canoe to escape the islands while maximizing the amount of time it spends fishing for sustenance. The agent begins on the larger island of size n × n/2 with an initial uniform distribution over those states, i.e., β(s) = 2/n2 for every state belonging to the large island. Once the agent transitions into one of the two smaller islands, it can never go back. In these smaller islands, one quarter of the land consists of logs which can be used to build a canoe, and there is one fishing site as well. For each island, we have (Llog1, [0.25, 1]), (Llog2, [0.25, 1]), (Lcanoe1, [0.05, 1.0]), (Lcanoe2, [0.05, 1.0]), (Lfish1, [0.1, 1.0]), (Lfish2, [0.1, 1.0]), R(·, ·,Lfish1) = R(·, ·,Lfish2) = 1, R(·, ·, S\(Lfish1∪Lfish2)) = 0. Since these islands are frozen, the agent has a chance of slipping whenever it moves, causing a transition into one of three possible states. Namely, if the agent chooses to go right (left), there is a 90% chance that it will transition to the right (left), and the chance of transitioning to either of the states above or below it is 5%. Similarly, if the agent chooses to up (down), it will end up in the states above (below) it with 90% chance, and in the states to the right and left of it with chance 5% each. This Frozen Island scenario is similar to those found in OpenAI Gym's FrozenLake environment [Brockman et al., 2016].

In this example, the feasible set of the LP of [Velasquez, 2019] will be empty. While the LP of [Kallenberg, 1983] returns a solution, the corresponding policy may not satisfy the specified constraints. We will demonstrate this deficiency by using a simple example.

Example 1. Consider the MDP defined in Figure 2 with rewards R(s5, a3) = R(s8, a1) = 1 and zero otherwise. One optimal solution x∗ to LP (4.7.6) in [Kallenberg, 1983] expressed in terms of state-action variables xsa, s ∈ S, a ∈ A(s) has x∗s5a3 = 0.5, x∗s6a2 = 0.25, x∗s8a1 = 0.25, yielding a policy π with Pr∞π (s5, a3) = 0.4173, Pr∞π (s6, a2) = 0.2724 and Pr∞π (s8, a1) = 0.2724. For the remaining state-action pairs, x∗sa and Pr∞π (s, a) are both less than 10-10 . Clearly, Pr∞π ̸= x∗ , so any desired specifications for Pr∞π (encoded as constraints on the variables xsa) are generally not met.

Definition 8 (Edge-Preserving Policies). Given an MDPM, we define the 'Edge-Preserving' set of policies ΠEP as the set of stationary policies that exercise all existing transitions in the TSCCs r(M) of Mand such that r(Mπ) = r(M), i.e.,

Note that the condition r(Mπ) = r(M) in Definition 8 implies that ¯ r(M) consists of transient or isolated states in Mπ for any π ∈ ΠEP.

Example 2. Figure 2 (left) shows a multichain MDP with two TSCCs designated by different colors. Figure 2 (right) shows the Markov chain Mπ induced by an edge-preserving policy π ∈ ΠEP. As shown, π preserves all edges in the TSCCs of the MDP, however, the policy π does not necessarily exercise all transitions in the transient states. InMπ, state s1 is isolated and s2 is transient.

We can readily define MaStEr as the problem of finding a policy in ΠEP that maximizes the average expected reward and satisfies a given set of steady-state constraints.

Definition 9 (MaStEr). Given an LMDP M = {S,A, T,R, β,L,Φ∞L }, we define MaStEr as the problem of finding a stochastic policy π ∈ ΠEP that maximizes the objective in (4) and satisfies the steady-state specifications Φ∞L , i.e., solves

In order to solve the MaStEr problem, we first determine the TSCCs r(M) of M and the complement set ¯ r(M) using standard techniques from graph theory [Tarjan, 1971]. These are then used to define the LP (5) from which the solution policy is derived.

Constraint (i) ensures that x is a stationary distribution [Altman, 1999] [Puterman, 1994]; constraint (ii), which is described in [Kallenberg, 1983] [Puterman, 1994], enforces consistency in the expected average number of visits yfa for any transient state-action f ∈ ¯ r(M), a ∈ A(f); constraints (iii), (iv) encode valid absorption probabilities pfk ensuring that from any state f ∈ ¯ r(M), the process will be ultimately absorbed into the recurrent components rk(M), k ∈ [m]; constraint (v) preserves the non-recurrence of the states f ∈ ¯ r(M) by forcing zero steady-state occupancy; the strict positivity constraints (vi) preserve the transitions in the TSCCs for yielding edge-preserving policies; finally, constraints (vii) encode the steady-state specifications.

Theorem 1. Given an LMDPM, let (x, y, p) ∈ Q and π be defined as in (6), where Q is the feasible set of solutions to LP (5), xs := ∑a∈A(s) xsa, ys = ∑a∈A(s) ysa, Ex := {s ∈ S : xs > 0} and Ey := {s ∈ S : ys > 0}. Then, we have π ∈ ΠEP.

Proof. Let f ∈ ¯ r(M). From constraint (v), we have xf = 0. Two cases arise. If f /∈ Ey, then yf = 0. It follows from constraint (ii) and (6) that βf = 0 and Tπ(f|f ′ ) = 0, ∀f ′ ∈ Ey as evidenced by

Therefore, f ∈ ¯ r(Mπ). Now, consider the case where f ∈ Ey and assume, for the sake of contradiction, that f ∈ r(Mπ). Hence, f ∈ F ⊆ r(M), for some TSCC F. Summing (7) over states f ′ ∈ F, we get that βf ′ = 0, ∀f ′ ∈ F. From (7), we also have Tπ(f|f ′ ) = 0, ∀f ′ ∈ (¯ r(M) \ F) ∩ Ey. Therefore, F ⊆ ¯ r(Mπ), yielding a contradiction. Hence, f ∈ ¯ r(Mπ). We conclude that ¯ r(M) ⊆ ¯ r(Mπ).

Consider s ∈ rk(M) for some k ∈ [m] and assume, for the sake of contradiction, that s ∈ ¯ r(Mπ). From the positivity constraint (vi), we have that s ∈ rk(M) ∩ Ex. Since s ∈ ¯ r(Mπ), the column of the matrix T ∞ π corresponding to state s is zero. Hence, from constraint (i), we have xs = 0, i.e., s /∈ Ex, yielding a contradiction. Hence, rk(M) ⊆ r(Mπ), ∀k ∈ [m]. Since we have already shown that ¯ r(M) ⊆ ¯ r(Mπ), we conclude that r(Mπ) = r(M). The second requirement in (3) now follows from constraint (vi) and the definition of π in (6). Therefore, π ∈ ΠEP.

We can readily state the following theorem establishing the correctness of the proposed LP.

Theorem 2. Given an LMDP M = (S, A, T, R, β, L, Φ∞L ), the linear program in (5) is feasible iff there exists a policy π ∈ ΠEP such that the Markov chain Mπ = (S, Tπ) satisfies the specifications Φ∞L . Further, given an optimal solution x∗ , y∗ of (5), the policy π∗ as defined in (6) is optimal in the class of policies ΠEP and meets the specifications Φ∞L .

Proof. ( =⇒ ) Let (x, y, p) ∈ Q denote a feasible solution to (5) and let π be defined as in (6). We will show that Pr∞π (s, a) = xsa, s ∈ S, a ∈ A(s), which implies that Mπ meets the specifications Φ∞L per constraint (vii). By Theorem 1, π ∈ ΠEP. Therefore, ¯ r(Mπ) = ¯ r(M), implying Pr∞π (f, a) = 0 = xfa, f ∈ ¯ r(M), a ∈ A(f), where the second equality follows from constraint (v).

First, note that from (7), we have yf = βf + ∑f ′ yf ′Tπ(f|f ′ ) for f ∈ ¯ r(M). This can be written as

where Zπ = [Tπ(f ′ , f)] ∈ [0, 1]|¯ r(M)|×|¯ r(M)| defines the transitions between states in ¯ r(M) under policy π.

Second, recall that π ∈ ΠEP and so the set rk(M) for any k ∈ [m] is a TSCC of Mπ. For every k ∈ [m], we have

where the first equality follows from (ii) and the fact that rk(M) is only reachable from states in rk(M) ∪ ¯ r(M). The second equality follows by breaking the summation over the union of the sets rk(M) and ¯ r(M) and the fact that rk(M) is closed. Combining (8) and (9), we get

where Lπ,k is the submatrix of Tπ of transitions from ¯ r(M) to rk(M). Given the definition of Pr∞π (s) in Lemma 1 and the known form of T ∞ π [Puterman, 1994], we recognize that the right hand side of (10) is exactly equal to βT ¯ r(M)Pπ,k, where Pπ,k = [pfk], f ∈ ¯ r(M) are the absorption probabilities from ¯ r(M) to rk(M) under policy π [Feller, 1968; Kallenberg, 1983]. We conclude that ∑s∈rk(M) xs = ∑s∈rk(M) Pr∞π (s). Finally, xTrk(M)Tπ,k = xTrk(M) from constraint (i) and (6), where Tπ,k is the submatrix of Tπ corresponding to transitions between states in rk(M). Hence, by the ergodic Theorem for unichain components [Altman, 1999], the solution is unique for each component rk(M), k ∈ [m] so x = Pr∞π , the unique steady-state distribution.

( ⇐= ) Suppose there exists such a policy π as in the statement of Theorem 2. Then Pr∞π is well-defined as in Lemma 1. Hence, we can set xsa = Pr∞π (s, a), s ∈ S, a ∈ A(s). Recall that ¯ r(Mπ) = ¯ r(M) since π ∈ ΠEP, so we set xsa = Pr∞π (s, a) = 0, s ∈ ¯ r(M). The variables yfa, f ∈ ¯ r(M) and pfk can be set as in (8) and (10). It can be easily verified that the variables ysa, s ∈ rk(M) can now be defined in terms of xsa, yfa, pfk, T(s′ |s, a) and β such that the corresponding constraints are satisfied. The optimality of π∗ follows from the optimality of (x∗ , y∗ ), Theorem 1 and the established equality Pr∞π∗ = x∗ .

5 Numerical Results

We first run our proposed LP (5) to calculate the steady-state distribution Pr∞π (s) for the Frozen Island example shown in Figure 1. The values for the two recurrent sets (the two islands) are shown in Figure 3. The heat map provides insight into the way in which the agent meets the specifications. Once entering the islands, the agent spends a large proportion of its time in states s33, s36, s48, s49, s61, and s64, in the sense of average expected number of visits. The agent satisfies constraints (Llog1, [0.25, 1]) and (Llog2, [0.25, 1]) largely by visiting states s36 and s61, respectively. Likewise, the agent meets constraints (Lcanoe1, [0.05, 1.0]), (Lcanoe2, [0.05, 1.0]) (Lfish1, [0.1, 1.0]), (Lfish2, [0.1, 1.0]) by visiting states s33, s49, s48, and s64, respectively. While satisfying the constraints, the agent maximizes the accumulated reward by visiting state s48 over 25% of the time.

Figure 4 (left) shows the values of Pr∞π (s) along with the optimal values x∗s obtained from LP (5), demonstrating that the steady-state distribution matches that estimated by the LP for every state. This holds also for all state-action pairs, i.e., Pr∞ = x∗ . This condition is critical to the proof of Theorem 2, and ensures that the policy is both optimal and meets the steady-state specifications. For comparison, we solve LP (4.7.6) from [Kallenberg, 1983] to obtain optimal values x∗ , y∗ , then form the corresponding policy π. Results are shown in Figure 4 (right). As with Example 1, the produced policy fails to yield a steady-state distribution equal to x∗ .

Table 1 demonstrates the consequences when Pr∞π ̸= x∗ .

For each specification (Li, [l, u]) ∈ Φ∞L , Table 1 shows eT x∗Li and Pr∞π (Li) := ∑s∈Li Pr∞π (s). For the proposed LP, all of the specifications are met. However, for Kallenberg's formulation, although x∗Llog1 and x∗Lcanoe1 meet the specification, the policy yields steady-state distributions Pr∞π (Llog1) and Pr∞π (Lcanoe1) which violate the specifications (the violations are highlighted with bold red text). Additionally, we show the optimal reward R∗ output by the LP, as well as the average expected reward of the obtained policy R∞ π := ∑s∈S ∑a∈A(s) Pr∞π (s, a)R(s, a). Although R∗ obtained by Kallenberg's formulation is larger than that of the proposed LP, the proposed LP produces a policy which gives a larger R∞.

Finally, we execute the policies to verify the validity of the formulations and to further demonstrate the failure of Kallenberg's formulation to meet specifications and yield optimal rewards. Define St and At as the state and action, respectively, of the Frozen Island example at time t assuming initial distribution β and policy π. The average number of visits fπ,n and average reward gπ,n up to time n are defined as

For fπ,n(L) and gπ,n, we take an ensemble average over 5000 paths. In Figure 5 (left), the solid and dotted lines show the average number of visits to the states labeled as logs, the dashed and dash-dotted lines indicate the steady-state distributions, and the square markers show the specification lower bound for the logs. For the proposed LP, fπ,n(Llog1) converges to Pr∞π (Llog1) and meets the specification. For Kallenberg's policy, although fπ,n(Llog1) converges to Pr∞π (Llog1), it fails to meet the specifications for the reason described earlier. In Figure 5 (right), the solid and dotted lines show the average reward, and the dashed and dash-dotted lines indicate the reward which was output by the LP. While the proposed LP converges to the LP reward, as described earlier, Kallenberg's formulation converges to a different reward.

We also demonstrate the scalability of the proposed LP by running CPLEX 12.8 simulations on a standard desktop computer with 128GB of RAM for random instances of the Frozen Island problem. See Table 2 for runtime results.

6 Conclusion

The multichain SSPS problem was defined for deriving policies that satisfy constraints on the steady-state behavior of the agent. A linear programming solution was proposed and its correctness proved for the class of edge-preserving policies. Simulations of the resulting policies demonstrate that our approach overcomes limitations in the literature.