Steady-State Planning in Expected Reward Multichain MDPs

The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some well-defined logic. While many such logics have been proposed with varying degrees of expressiveness and complexity in their capacity to capture desirable agent behavior, their value is limited when deriving decision-making policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steady-state behavior of an agent, which captures the proportion of time an agent spends in each state as it interacts for an indefinite period of time with its environment. This is sometimes called the average or expected behavior of the agent and the associated planning problem is faced with significant challenges unless strong restrictions are imposed on the underlying model in terms of the connectivity of its graph structure. In this paper, we explore this steady-state planning problem that consists of deriving a decision-making policy for an agent such that constraints on its steady-state behavior are satisfied. A linear programming solution for the general case of multichain Markov Decision Processes (MDPs) is proposed and we prove that optimal solutions to the proposed programs yield stationary policies with rigorous guarantees of behavior.


Introduction
The proliferation and mass adoption of automated solutions in recent years has led to an increased concern in the verification, validation, and trust of the prescribed agent behavior (Schwarting, Alonso-Mora, & Rus, 2018). This motivates the need for traditional techniques which can yield guarantees of behavior. The study of such techniques has largely been the focus of areas such as formal synthesis and planning, where it is common to derive decision-making policies for agents acting in an environment such that some given formal specification is satisfied. The majority of prior art in this area entails the coupling of some formal logic with the model of agent-environment dynamics in order to find optimal The use of the foregoing logics has facilitated the growth of solutions to the aforementioned planning problems and are a good conduit for verifying, explaining, and yielding provably correct agent behavior and, consequently, establishing a measure of trust. However, these logics are either insufficient to reason about the asymptotic behavior that is captured by the steady-state distribution of the agent as it follows some decision-making policy, or existing solutions to the corresponding planning problems make strong assumptions on the underlying model of the system. Solutions to these challenges have gained traction in recent years. Indeed, there has been increased interest in what we refer to as the steady-state planning problem of computing decision-making policies that satisfy constraints on the resulting steady-state behavior. In particular, progress has been made in easing the restrictions required on the agent-environment dynamics model, usually expressed in the form of a Markov Decision Process (MDP), in order to derive a solution policy. In this paper, we advance the state-of-the-art in steady-state planning by establishing the first solution to steady-state planning in multichain MDPs such that the resulting stationary policy satisfies constraints imposed on the steady-state distribution of the agent. Our approach also dissolves assumptions of ergodicity or recurrence of the underlying MDP which are often made in the literature when reasoning about steady-state distributions.
Steady-state planning has applications in several areas, such as deriving maintenance plans for various systems, including aircraft maintenance, where the asymptotic failure rate of components must be kept below some small threshold (Boussemart & Limnios, 2004;Boussemart, Limnios, & Fillion, 2002). Optimal routing problems for communication networks have also been proposed in which data throughput must be maximized subject to constraints on average delay and packet drop metrics (Lazar, 1983). This includes constraints on steady-state network behavior, which include steady-state network frequency and steady-state phase or timing errors (Skwirzynski, 1981). There is also the potential of leveraging solutions in the steady-state planning problem space to the design of intelligent space satellites. Indeed, this is an area where the steady-state distribution of debris following some orbit can be computed to reason about the probability of a satellite colliding with said debris. Such information has been used to determine human-driven control policies for tasks such as debris mitigation or debris removal (Tian, 2019), sometimes via remote-controlled robots (Baiocchi, 2010) that are amenable to automated approaches.
The steady-state planning problem has been studied under various names, including steady-state control (Akshay, Bertrand, Haddad, & Hélouët, 2013), average-or expectedreward constrained MDPs (Altman, 1999), and steady-state policy synthesis (Velasquez, 2019). As pointed out by Altman, Boularouk, and Josselin (2019), solutions to this problem often require strong assumptions on the ergodicity of the underlying MDP. These assumptions facilitate the search for efficient algorithms by leveraging the one-to-one correspondence between the optimality of solutions to various mathematical programs and the optimality of policies derived thereof. This has been studied at length in the works of Derman (1970), Kallenberg (1983), Puterman (1994), and Altman (1999), who have derived mathematical programs for discounted, total, and expected reward formulations of constrained MDPs. In particular, the work of Kallenberg laid the foundation for Markovian control within the context of multichain constrained MDPs. However, it was noted that deriving optimal policies for the expected-reward formulation was intractable by their approach and there was no guarantee of agent behavior in terms of satisfying steady-state constraints.
Summary of contributions. We make four main contributions. First, we introduce the Steady-State Policy Synthesis (SSPS) problem of finding a policy from a predefined subset of stationary policies in a multichain MDP that maximizes an expected reward signal while enforcing asymptotic behavior that is correct-by-construction (Nilsson, Hussien, Balkan, Chen, Ames, Grizzle, Ozay, Peng, & Tabuada, 2015) -in the sense that our policies yield provably correct behavior that satisfies the imposed specifications on the steady-state distribution of the Markov chain induced by said policies. Our framework generalizes the steady-state planning problems studied by Akshay et al. (2013) and Velasquez (2019), as we do not impose any restrictions on the underlying MDP. In particular, we dispense with the strong assumption made by Akshay et al. (2013) about the ergodicity of the MDP, according to which every deterministic policy necessarily induces an ergodic Markov chain (i.e., one that is recurrent and aperiodic). In sharp contrast to the work of Velasquez (2019), we do not restrict our search to stochastic policies that induce an irreducible Markov chain (i.e., one in which all states form one communicating class). In general, such a chain may not even exist -normally, many states in a given MDP are inevitably transient. Our search space consists of subsets of the stationary policies that we term edge-or class-preserving, which, apart from a transient phase, restrict the long-term play in the terminal components of the given MDP. We introduce two distinct notions for class preservation that yield policies with different characteristics. These notions will be made precise in Section 4.
As our second contribution, we develop a scalable approach to synthesize policies that provably meet said asymptotic specifications through novel linear programming formulations. While a tractable solution to the SSPS problem has heretofore remained elusive and existing solutions require an enormous amount of calculations with no provable guarantees (Kallenberg, 1983), two key ideas underlie our ability to tackle the associated combinatorial difficulties. The first idea is the aforementioned restriction of the domain to edge-or class-preserving policies, which can be provably obtained from solutions to simple linear programs (LPs). The second idea is to encode constraints on the limiting distributions of the corresponding Markov chains in formulated LPs, whose solutions yield optimal policies maximizing the expected average reward while meeting desired asymptotic specifications on the limit points of the expected state-action frequencies. These LPs are crafted to capture designated state classifications, absorption probabilities in closed communicating components, and recurrence constraints within such components, along with the steady-state specifications.
Our third contribution lies in deriving key theoretical results establishing provable performance and behavior guarantees for the derived policies. Contracting or transient MDP models that use the expected total reward as the optimality criterion are commonplace in constrained MDPs since optimal stationary policies with regard to this criterion can always be found via mathematical programming in view of a well-established one-to-one correspondence between stationary policies and feasible solutions to such programs (Altman, 1998;Feinberg, 2000;Wu & Durfee, 2010;Petrik & Zilberstein, 2009). The notoriously more difficult and equally important expected average reward criterion is much less understood considering that such correspondence ceases to exist for general multichain MDPs. In this paper, we tap into this long-standing dilemma and establish such one-to-one correspondence for classes of stationary policies that are edge-or class-preserving. Theorems 1, 2, 3 and 4 establish the correctness of linear programs yielding optimal policies from said classes. The proof of these theorems rest on few intermediate results. In particular, Lemma 3 characterizes the Markov chains induced by the policies of interest, while Lemma 7 establishes the feasibility of the steady-state distributions induced by these policies. Lemma 6 gives a sufficient condition for the existence of a one-to-one correspondence between feasible solutions to the linear programs and the stationary policies derived from these solutions. Theorem 5 establishes an existence condition of policies found on a more relaxed notion of class preservation, which inspires a constructive approach in Algorithm 1 to compute such policies. Theorem 8 gives a generic sufficient condition for the existence of an optimal stationary policy meeting the desired specifications beyond class-preserving ones.
As our fourth contribution, we introduce an alternative type of specifications applicable in transient states. By augmenting our LPs with appropriate constraints, the synthesized policies provably meet specifications on the expected number of visitations to transient states simultaneously with the foregoing steady-state specifications on the asymptotic frequency with which recurrent states are visited (Proposition 1).
We verify the theoretical findings of our work using a comprehensive set of numerical experiments performed in various environments. The results demonstrate the correctness of the proposed LPs in yielding policies with provably correct behavior and the scalability of the proposed solutions to large problem sizes.
This article brings in and substantially extends the scope of our recent work (Atia et al., 2020), which considered policy synthesis over edge-preserving policies. Such policies constitute only a small subset of the policies considered herein. A particularly appealing characteristic of the newly introduced policies is their greater ability to avert MDP transitions of low return without violating the asymptotic constraints. In turn, they yield larger expected rewards relative to their edge-preserving counterparts -in some cases, we show that this gain can be substantial. Further, we derive general characterizations of optimality over a larger class of policies obtained in terms of the MDP reward signal. In addition, this article advances the aforementioned form of transient specifications that a policy can provably meet together with the steady-state ones. We provide a complete presentation of the steady-state planning problem through linear programming formulations over differ-ent families of policies, mathematical analyses establishing correctness of such formulations with optimality guarantees, and a comprehensive set of numerical experiments in diverse environments to support the theoretical findings.
To the best of our knowledge, this work is the first to allow synthesis of stationary policies with provably correct steady-state behavior in general multichain MDPs.
Organization: The paper is organized as follows. Notation and preliminaries are covered in Section 2. Related work in steady-state planning is summarized in Section 3. The SSPS problem is formalized in Section 4. We describe our linear programming approach and present the results of our theoretical analysis in Section 5. Transient specifications and extensions to a larger class of policies are presented in Section 6. Numerical experiments are presented in Section 7 to validate our approach and demonstrate its scalability to large problems. Concluding remarks are presented in Section 8. In Appendix A, we present statements and proof of technical lemmas. The proof of the main results are deferred to Appendix B.

Preliminaries and Notation
We introduce some notation and preliminary definitions used throughout the paper. For a matrix A, a ij and A(i, j) are used interchangeably to denote the element in its i th row and j th column. The vectors e and e s denote the vectors (of appropriate dimension) of all ones, and all zeros except for the s th entry, respectively. Given a vector x and index set V , the vector x V is the vector with entries x v , v ∈ V , where x v is the entry corresponding to index 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. The symbols ∃ and ∃! mean "there exists" and "there exists a unique", respectively, and is the transpose operator.
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 β : S → [0, 1] 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 T (s, s ) = T (s |s). The use of T will be clear from the context. (Norris, 1997;Privault, 2018): Given a finite Markov chain M = (S, T, β), we say state s is accessible from state s if (T t )(s, s ) > 0, for some t > 0, where T t is the t−step transition matrix, i.e., if there is a positive probability of transitioning to state s starting from state s in some number of steps. Two states are said to communicate if they are both accessible from each other. Communication is an equivalence relation which partitions the Markov chain M into communicating classes such that only members of the same class communicate with each other. A class is closed if the probability of escaping the class is zero. A state s ∈ S is said to be transient if, starting from s, there is a nonzero probability of never returning to s. A set of transient states is termed a transient set. Non-transient states are called recurrent, that is, state s is recurrent if, starting from s, the probability of returning to state s after some number of steps is one. A Markov chain for which there is only one communicating class consisting of the entire state space is called irreducible, whereas a Markov chain that has a single closed communicating class and (possibly) some transient states is termed unichain. A state is periodic with period k if any return to state s must occur in multiples of k time steps, where k is some integer greater than 1. An example illustrating the classification of states in a Markov chain is shown in Figure 1.

Classification of states
Transience and recurrence describe the likelihood of returning to a state conditioned on starting from that state, regardless of the initial state distribution β. Given β, we also define an isolated component I as a maximal set of states in M that can never be visited, that is, β I = s∈I β s = 0, where β s is the initial probability of being in state s, and I cannot be reached from any state in S \ I, i.e., s ∈I T (s |s) = 0, ∀s ∈ S \ I. In Figure  1, the set of states {s 3 , s 4 } is isolated. The term 'reachable' refers to states that are not isolated.
Definition 2 (Markov decision process (MDP)). An MDP is a tuple M = (S, A, T, R, β), 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 β : S → [0, 1] the initial distribution. By A(s) ⊆ A, we denote the set of actions available in state s.
Definition 3 (Transition graph). We define the transition graph of an MDP M = (S, A, T, R, β) as the directed graph whose vertex set is the state space S, and in which there is a directed edge from vertex s to vertex s if there exists an action a ∈ A(s) such that T (s |s, a) > 0. The transition graph of a Markov chain M = (S, T, β) is the directed graph with vertex set S, and which has a directed edge from vertex s to vertex s if T (s |s) > 0.
Definition 4 (Terminal strongly connected component (TSCC)). Consider the transition graph of a Markov chain or MDP M with state space S and initial distribution β. A strongly connected component (SCC) of the digraph is a maximal subset of vertices C, where for every pair of vertices s, s ∈ C, there is a directed path 1 from s to s and a directed path from s to s (Tarjan, 1972). A Terminal Strongly Connected Component (TSCC) S ⊆ S is an SCC reachable from some initial state s, β s > 0 and with no outgoing transitions to any state in S \S . A TSCC is also called a bottom SSC (Courcoubetis & Yannakakis, 1995). We denote by  Definition 5 (Stationary policy). Given MDP M = (S, A, T, R, β), a stationary policy π : S → ∆ A is a mapping of states to probability distributions over the space of actions A, where ∆ A is the probability simplex over A. The policy π specifies the conditional probability π(a|s) that action a is taken in state s. The set of all stationary policies is denoted Π S . Definition 6 (Markov chain induced by policy). The tuple M π = (S, T π , β) is the Markov chain induced by a policy π in an underlying MDP M = (S, A, T, R, β), where Definition 7 (Unichain and multichain MDP). An MDP is called unichain (Puterman, 1994;Altman, 1999) if every stationary deterministic policy induces a Markov chain that is unichain, that is, consists of exactly one recurrent set and possibly some transient states 2 . An MDP is said to be multichain if it is not unichain. See Figure 2 and its caption for an example.
multiple recurrent classes, then in general there will be many stationary distributions. For example, for the Markov chain of Figure 2(c), one can verify that the distribution Pr ∞ (s 1 ) = Pr ∞ (s 2 ) = 0, Pr ∞ (s 3 ) = 1 and the distribution Pr ∞ (s 1 ) = Pr ∞ (s 3 ) = 0, Pr ∞ (s 2 ) = 1 both satisfy (2) and (3), thus they are both stationary distributions of the Markov chain. Note that a stationary distribution may not be representative of the true steady-state behavior of the system (c.f. Definition 10 and the following example).
Definition 9 (Stationary matrix of a Markov chain). Given a Markov chain M = (S, T, β), the stationary matrix T ∞ is given by the Cesàro limit 3 (Puterman, 1994) Given a finite multichain Markov chain M = (S, T, β) with transient set F and recurrent (i.e., non-transient) components E k , k ∈ [m], the transition matrix T can be expressed in the canonical form (Puterman, 1994 where the matrices T k correspond to transitions between states in E k , L k to transitions from states in F to states in E k , k ∈ [m], and Z to transitions between states in F . Similarly, we use T π,k , L π,k , k = 1, . . . , m, and Z π to denote the corresponding submatrices of the transition matrix T π of the Markov chain M π induced by policy π. Also (Puterman, 1994;Kallenberg, 1983), where, η s = lim n→∞ 1 n n t=1 T t (s , s), is the long term proportion of time the chain spends in s from initial states s ∈ E k , s∈E k η s = 1, p s k is the absorption probability from the transient state s ∈ F into the recurrent class E k , k ∈ [m], and m k=1 p s k = 1, ∀s ∈ F . In this paper, we are interested in the asymptotic behavior of an agent's policy in an MDP, as captured by the steady-state distribution of the induced Markov chain defined next.
Definition 10 (Steady-state distribution). 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 (Altman, 1999, Chapter 4), is the long-term proportion of time spent in state-action pair (s, a) as the number of transitions approaches ∞, i.e., Pr(S t = s, A t = a|β, π), s ∈ S, a ∈ A(s) if the limit exists, where S t and A t 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. The steady-state distribution is a stationary distribution of the Markov chain induced by the policy π.
Definition 11. Given an MDP M = (S, A, T, R, β) and a set of policies Π ⊆ Π S , we define as the set of occupation measures induced by policies in Π, where Pr ∞ π is defined in (7).
Definition 12 (Steady-state specifications and constraints (Velasquez, 2019)). Given an MDP M = (S, A, T, R, β) and a set of labels L = {L 1 , . . . , L n L }, where L i ⊆ S, a set of steady-state specifications is given by L is satisfied if and only if the steady-state constraint is satisfied; that is, if the steady-state probability of being in a state s ∈ L i in the Markov chain M π falls within the interval [l i , u i ].
Definition 14 (Expected average reward). Given an MDP M = (S, A, T, R, β), the expected average reward R ∞ π (β) of a policy π is defined as where R(s, a) := s ∈S T (s |s, a)R(s, a, s ), and the expectation is w.r.t. the probability measure induced by the initial distribution β and the policy π over the state-action trajectories.
It follows from the definition of the expected average reward in (10) and the steady-state distribution (7) that for a stationary policy π (Krass & Vrieze, 2002;Altman, 1999) where Pr ∞ π (s, a) is given in (9). The primary focus of this paper in the context of steady-state planning is to find stationary policies that maximize the expected average reward (10) while satisfying specifications Φ ∞ L on the steady-state distribution (see Definition 12). We restrict the search to certain classes of stationary policies which will be introduced and defined precisely in Section 4. Our solution approach to this constrained MDP problem is based on linear programming formulations, which optimize a linear objective function capturing the expected reward, subject to linear equality and inequality constraints. Such constraints encode restrictions on the steady-state distributions induced by policies of interest, as well as desired steady-state specifications on the long-term frequencies for state-actions pairs. The decision variables of the LPs correspond to the occupation measures, and policies are obtained from their optimal solutions. We establish a one-to-one correspondence between optimal solutions of said LPs and optimal policies of the constrained MDP problem.

Related Work
Research related to steady-state planning often comes from the field of average-or expectedreward constrained MDPs and has its roots in mathematical programming (Bertsekas, 2005). Many solutions proposed in this area utilize linear programming formulations to derive policies (Altman, 1999). We illustrate these formulations in order of increasing complexity and elucidate the key differences between the formulations in the literature and our own. First, let us consider the simple problem of deriving a policy for an agent which seeks to maximize expected reward without any constraints on its steady-state distribution.
In the unichain MDP case, one may synthesize a policy by solving a linear program (LP) of the form (Manne, 1960;De Ghellinck, 1960) max s∈S a∈A(s) x sa s ∈S T (s |s, a)R(s, a, s ) subject to s∈S a∈A(s) The policy can be derived from the occupation measures given by x sa through a simple calculation. It is worth noting that this combination of occupation measures and linear programming has enabled significant progress in the area of planning within stochastic shortest paths MDPs, where several occupation measure heuristics have been defined to find decision-making policies that maximize the probability of reaching a set of goal states while satisfying multiple cost constraints (Trevizan, Thiébaux, Santana, & Williams, 2016Trevizan, Thiébaux, & Haslum, 2017;Baumgartner, Thiébaux, & Trevizan, 2018). While the LP in (12) always produces valid solutions for unichain MDPs, this is not necessarily the case for multichain MDPs due to the fact that there may be more than one ergodic set (Puterman, 1994). This issue is rectified by modifying LP (12) to obtain (Denardo & Fox, 1968;Kallenberg, 1983) max s∈S a∈A(s) x sa ∈ [0, 1], y sa ≥ 0 ∀s ∈ S, a ∈ A(s).
The new y sa variables guide policy formation on the transient states. Both LP (12) and LP (13) yield stationary stochastic policies. Furthermore, there always exists at least one optimal deterministic policy, which can easily be derived from the stochastic policy solution obtained from the LPs (Puterman, 1994). For producing control policies with steady-state specifications, LPs (12) and (13) are extended to include linear steady-state constraints on the occupation measures. When applied to unichain MDPs, the constrained version of LP (12) encounters minor difficulties, in that there may not be an optimal deterministic policy (Altman, 1999). Nonetheless, the LP always produces an optimal stochastic stationary policy. In fact, there exists an optimal policy having at most n L "randomizations", i.e. having at most |S| + n L state-action pairs with non-zero probability of being selected (Ross, 1989).
On the other hand, serious issues arise when LP (13) is augmented with steady-state constraints and solved for multichain MDPs, as described in the pioneering work of 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 specifications (see Example 1 in Section 4.1). This issue is not easily remedied, since the optimal solution may not be achievable by any stationary policy, or identifying such a policy would generally require combinatorial search. We refer the reader to the paper by Krass and Vrieze (2002) for an overview.
In order to mitigate the preceding problem of integrating steady-state constraints, various assumptions have been made in the literature on the structure of the underlying MDP. Multichain MDPs are also frequently excluded from the conversation altogether. The assumption that the MDP is ergodic, and therefore every policy induces an ergodic Markov chain, has been used by Akshay et al. (2013) to ensure that steady-state equations and constraints on the same are satisfied. This assumption is relaxed to some extent by Ross (1989), Altman (1999), Feinberg (2009), where unichain MDPs are allowed. The assumption of either an ergodic or a unichain MDP requires that no stationary deterministic policy induce more than a single recurrent class, thus severely limiting the applicability of these methods. These assumptions are removed in the recent work of Velasquez (2019), where neither ergodic nor recurrence assumptions are made on the underlying MDP. However, the solution proposed therein finds an irreducible Markov chain in the underlying MDP, if one exists, and is therefore suitable for communicating MDPs where, for any two states s and s , there exists a deterministic stationary policy such that s can reach s in a finite number of steps (Puterman, 1994). This solution, however, is too restrictive, thus not suitable for reasoning over general multichain MDPs.
Another approach taken to address these challenges is to simply allow solutions to take the form of non-stationary policies. In the work of Kallenberg (1983), this is accomplished by a computationally expensive approach producing a potentially different policy in each time step. Another approach, proposed by Krass and Vrieze (2002), starts by using one policy, and then switches to a second "tail" stationary policy. The time at which the switch occurs is determined by a lottery performed at each time step, and once the switch occurs the tail policy continues to be used indefinitely (thus the policy is "ultimately" stationary once the switch occurs). However, this approach has three key limitations. First, the constraints must take the form of a target frequency vector, which imposes an equality constraint on the steady-state distribution over all states. Second, the lottery system does not guarantee that the switch will occur in a finite number of steps, thus meaning that the policy is not guaranteed to be ultimately stationary. Third, the policy depends on a marker to track whether or not the switch has occurred. This marker is not part of the MDP, and therefore the MDP machinery must be modified to include a so-called marker-augmented history. As an alternative, the authors also propose a way to extend the given MDP with additional states, such that the problem can be solved using a stationary policy applied to the extended MDP. However, this approach still cannot produce a stationary policy to solve the original problem.
While most methods for solving constrained MDPs revolve around the use of mathematical programs, some reinforcement learning approaches have also been proposed for optimizing the average-reward objective and, to a lesser extent, for solving constrained instances of average-reward MDPs. Some noteworthy examples include the constrained actor-critic method proposed by Bhatnagar and Lakshmanan (2012), wherein a Lagrangian relaxation of the problem is used to incorporate steady-state costs into the objective function being optimized by the constrained actor-critic algorithm. A similar Lagrangian Q-learning approach is proposed by Lakshmanan and Bhatnagar (2012). Both of these reinforcement learning methods assume that every Markov chain induced by a policy is irreducible, which allows only a single recurrent class as with ergodic and unichain assumptions described earlier. The Lagrangian approach has also been applied to specific stochastic policy linear programming formulations relevant to aircraft maintenance problems where the asymptotic failure is to be kept below some small threshold (Boussemart & Limnios, 2004;Boussemart et al., 2002).
In contrast to the foregoing efforts, our approach is computationally tractable, works with the most general multichain MDPs, and always produces a stationary policy that satisfies the given steady-state specifications, if one exists. Additionally, none of the aforementioned methods consider constraints on the expected visits to transient states, as we are considering in our work.

Steady-State Policy Synthesis: Problem Formulation
In this section, we introduce the Steady-State Policy Synthesis (SSPS) problem of finding a stationary policy from predefined classes of policies (edge-and class-preserving) that maximizes the expected average reward subject to steady-state specifications. In contrast to prior work, we do not impose restrictions on the underlying MDP. Before we present our formulation, we briefly discuss the challenges underlying policy synthesis under the average reward optimality criterion and demonstrate the limitations of existing formulations in this context. Subsequently, we specify our search domain of policies and define the SSPS problem of synthesizing optimal policies from this domain.

Challenges and Limitations
We motivate this section with a simple example. Suppose an autonomous agent is marooned on a set of three connected frozen islands as shown in Figure 3. The agent's goal is to maximize the amount of time it spends fishing for sustenance while at the same time building a canoe to escape the islands. The agent has an equal chance of starting in any state belonging to the larger island of size n × n/2, i.e., we have β s = 2/n 2 for each state s in the island. Once the agent moves to one of the two smaller islands, it is unable to return to the larger island. One quarter of the land in the small islands contains logs which can be used to build a canoe, and each of these islands contains one fishing site as well.
and reward R(·, ·, S \ (L fish1 ∪ L fish2 )) = 0. Because the islands are covered in ice, the agent has a chance of slipping in three possible directions whenever it moves. Specifically, if the agent attempts to go right (left), it has a 90% chance of transitioning to the right (left), and there is a 5% chance of transitioning instead to either of the states above or below it. Similarly, if the agent tries to go up (down), it moves to the states above (below) it with 90% chance, and to the states to the right and left of it with chance 5% each. This Frozen Island scenario is motivated by that found in OpenAI Gym's FrozenLake environment (Brockman et al., 2016).
For this example, the LP by Velasquez (2019) is infeasible since there exists no policy that induces an irreducible Markov chain, that is, one where all states in S belong to one recurrent class. The LP by Kallenberg (1983) in (13) will return a solution (x, y), from which the stationary policy π := π(x, y) is computed as follows where x s := a∈A(s) x sa , y s = a∈A(s) y sa , E x := {s ∈ S : x s > 0} and E y := {s ∈ S : y s > 0}. However, in general the steady-state distribution induced by the policy (14) will not satisfy the specified constraints. This deficiency is best demonstrated via a simple example. The reader is also referred to Example 1 of Krass and Vrieze (2002).

Stationary policies
The previous example underscores the main challenge underlying steady-state planning in constrained Markov decision models with the average reward criterion: solutions to formulated programs and stationary policies are not in one-to-one correspondence. In other words, given a feasible LP solution (x, y), the steady-state distribution Pr ∞ π induced by the policy π(x, y) derived from that solution is not equal to x in general. As a result, unlike unichain MDPs (Altman, 1999), steady-state specifications encoded as constraints on the state-action variables are generally not met by π. Figure 5 (Left) illustrates the one-toone correspondence between LP solutions and stationary policies found in unichain MDPs. Figure 5 (Right) illustrates the lack of such correspondence in multichain MDPs, where instead, equivalence classes of feasible LP solutions (yellow circles) map to the same policy (Kallenberg, 1983;Puterman, 1994).

Problem Setup
The previous example motivates the work of this paper in which we develop an approach to synthesizing policies with provably correct asymptotic behavior based on the notions of edge preservation and class equivalence. First, we will define sets of policies under which certain class structures are preserved and give an example of such policies, then define the SSPS problem of finding an optimal policy from such classes.
Definition 15 (Edge-preserving policies). Given an MDP M, we define the set of Edge-Preserving (EP) policies Π EP as the set of stationary policies that play every action available at states in the TSCCs r(M) of M and for which r(M π ) = r(M), i.e., Hence, for every state s ∈ r(M) (see Definition 4), an EP policy assigns a non-zero probability to every action in A(s), and every state inr(M) is either transient or isolated in the Markov chain induced by the policy. For example, the uniform policy which has π(a|s) = 1/|A(s)|, ∀s ∈ S is in Π EP . Note that other policies in Π EP could assign a very small probability (as long as it is non-zero) to non-rewarding transitions in r(M). Using an open set definition in (15) simplifies the exposition and the subsequent theoretical analysis, however, it does not guarantee that an optimal policy from the set always exists. We discuss and analyze variations of the problem formulation to address this issue at length in Section 5.4.4.
Next, we introduce two sets of policies whose definitions rest on two distinct notions of class preservation.
Definition 16 (Class-preserving policies). Given an MDP M with TSCCs r k (M), k = 1, . . . , m, we define the set of Class-Preserving (CP) policies Π CP as the set of stationary policies that induce Markov chains with the same TSCCs as those of M, i.e., Note that the condition r(M π ) = r(M) in Definitions 15 and 16 implies thatr(M) consists of transient or isolated states in M π for any π in Π EP or Π CP . Per (16), a CP policy preserves the recurrence of all states in the TSCCs of the MDP but, unlike EP policies, its support need not be the entire set of actions available at said states. Therefore, CP policies can conceivably achieve larger rewards than EP policies by averting non-rewarding transitions.
Definition 17 (Class-preserving up to unichain). Given an MDP M with TSCCs r k (M), k = 1, . . . , m, we define the set of Class-Preserving-up-to-Unichain (CPU) policies Π CPU as that is, the set of stationary policies that induce Markov chains M π in which the TSCCs of the MDP M are reachable and unichain (i.e., each contains exactly one non-isolated, recurrent component) and the recurrent states are a subset of the recurrent states of M (Recalling that the notation ∃! in (17) refers to the existence of a unique set).
This definition captures a more relaxed notion of class preservation than (16) for CP policies in that it relaxes the requirement that all states in the TSCCs of M be recurrent and reachable in the Markov chain M π induced by the policy π, to the milder requirement that in M π there exists a unique reachable recurrent class in each of the TSCCs of M.
The aforementioned definitions are best illustrated by an example. Figure 5(b) illustrates a Markov chain induced by an EP policy, i.e., one that plays every action available in the TSCCs of the MDP of Figure 5 s 4 ). Similarly, the set composed of states s 6 , s 7 , s 8 , s 9 is unichain with one recurrent component (s 8 and s 9 ) and two transient states (s 6 and s 7 ).
The classes of policies defined in (15), (16) and (17) satisfy the following relations.
We remark that the inclusions in Lemma 2 are generally strict, except for some special MDPs. Specifically, given a general MDP M, there may exist a policy π ∈ Π CP for which r(M π ) = r(M) and π(a|s) = 0 for some a ∈ A(s), s ∈ r(M), in which case π / ∈ Π EP . Similarly, since a unichain may contain some transient states, Π CP is generally a proper subset of Π CPU .
Problem Definition. We can readily define the class of problems SSPS(Π), parametrized by a predefined set of stationary policies Π, of finding a policy in the set Π that maximizes the expected average reward while satisfying a given set of steady-state specifications.
Definition 18 (Steady-state policy synthesis (SSPS)). Given an LMDP M = (S, A, T, R, β, L, Φ ∞ L ) and a domain of policies Π ⊆ Π S , the SSPS(Π) problem is to find an optimal stochastic policy π ∈ Π that maximizes the expected average reward defined in (10) and satisfies the steady-state specifications Φ ∞ L (Definition 12), i.e., If the maximum in (18) cannot be attained over the domain Π, we define SSPS(Π) as the problem of finding a policy π ∈ Π that satisfies the specifications Φ ∞ L and whose expected average reward R ∞ π (β) ≥ sup π ∈Π R ∞ π (β) − , for some arbitrarily small > 0 (See Section 5.4.4).
In this paper, we present solutions to SSPS(Π EP ), SSPS(Π CP ) and SSPS(Π CPU ), where Π in (18) is set to Π EP , Π CP , and Π CPU , respectively 4 . To this end, we first determine the TSCCs r(M) of M and the complement setr(M) using standard techniques from graph theory (Tarjan, 1972). These are then used to define an LP from which the solution policy is derived.

Linear Programming Based Solutions
In this section, we present our linear-programming-based solution to the SSPS problem (18) over edge-and class-preserving policies. We formulate linear programs that encode constraints on the limiting distributions of said policies to solve SSPS(Π EP ) and SSPS(Π CP ). The optimal solutions to the formulated programs provably yield optimal edge-and classpreserving policies that meet the desired specifications. The encoded constraints are also at the center of an iterative algorithm described in Section 5.3 to generate CPU policies for SSPS(Π CPU ). Our main results on SSPS in edge-and class-preserving policies are presented in Sections 5.1, 5.2 and 5.3. To simplify the exposition, all proofs are deferred to the appendix.
We present three main programs. The first, used for the synthesis of optimal EP policies, is the most constrained as it encodes the requirement that every action in the terminal components must be played with non-zero probability. While this condition is not necessary in order to ensure one-to-one correspondence between the feasible solutions and the induced steady-state distributions, it results in a simple program whose solution provably yields an optimal EP policy that meets the specifications. The second program relaxes this condition to the milder requirement that every state in the terminal components is visited infinitely often (which may not require playing every action available), but at the expense of additional complexity. Specifically, its solution yields an optimal policy that meets the specifications from the class of CP policies (a superset of EP policies) but uses more complex flow constraints to encode said requirement. The third program is the least constrained and is used to synthesize a policy from the larger class of CPU policies. While its solution is not guaranteed to yield a CPU policy, we derive a characterization of its optimal solution, which inspires a greedy algorithm to construct such policy. We augment the program by iteratively adding constraints until convergence. The algorithm is guaranteed to converge in a finite number of steps to a (possibly) suboptimal CPU policy that meets the specifications.
By encoding constraints on the limiting distribution of the Markov chain induced by a stationary policy derived from an LP solution, the policy is ultimately absorbed in the TSCCs of the MDP. This restricts the long-term play to the TSCCs, which once reached, cannot be escaped. By imposing strict positivity on state-action pairs or flow constraints in the TSCCs, we further ensure that these components are unichain, and in turn, the long-term frequencies induced by the policy match the solution from which the policy is generated.

SSPS(Π EP ) -Synthesis over Edge-Preserving Policies
In this section, we formulate a linear program to solve SSPS(Π EP ) defined in (18), which seeks to maximize the expected average reward subject to specification constraints over the class of policies Π EP in (15).
Given MDP M, define Q 0 to be the set of vectors x, y satisfying We can readily formulate LP 1 (20) to synthesize optimal EP policies, which incorporates two additional constraints beside the constraints in (19).
Constraints (i ) -(iii ) constrain the limiting distributions of Markov chains induced by the policies of interest, and are thus part of the constraint set of all programs we formulate in this work. In particular, they capture the structure of the stationary matrix T ∞ corresponding to the classifications r(M) andr(M) (See Definition 4). Constraint (i ) ensures that x is a stationary distribution (Altman, 1999;Puterman, 1994); constraint (ii ), which is described in (Kallenberg, 1983, Chapter 4) and (Puterman, 1994, Sec 9.3), enforces consistency in the expected average number of visits y f a for any transient state-action pair f ∈r(M), a ∈ A(f ); constraint (iii ) preserves the non-recurrence of the states f ∈r(M) by forcing zero steady-state probability. Constraint (iv ) encodes the steady-state specifications. The strict positivity constraint (v ) preserves the transitions in the TSCCs to yield EP policies. In practice, we transform the strict inequalities to bounded ones by introducing an arbitrarily small constant on the right-hand side, thereby ensuring an optimal solution always exists (See Section 5.4.4). Enforcing constraints on the occupation measures ensures that, from any state f ∈r(M), the process will be ultimately absorbed into the TSCCs r k (M), k ∈ [m].
The next theorem guarantees that every feasible solution to LP 1 yields an EP policy.
We can readily state the following theorem establishing the correctness of LP 1 . It guarantees that the policy synthesized from an optimal solution to (20) (if one exists) is not only in Π EP , but also is optimal among all such policies and meets the steady-state specifications, i.e., solves SSPS(Π EP ). (20) 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 (20), the policy π * := π(x * , y * ) as defined in (14) is optimal in the class of policies Π EP and meets the specifications Φ ∞ L .

SSPS(Π CP ) -Synthesis over Class-Preserving Policies
The strict positivity constraint (v ) of LP 1 forces the policy to play every action in the TSCCs of the MDP M (by assigning non-zero probability to every action available), which may be restrictive and often unnecessary. Indeed, as we show, in order to ensure one-to-one correspondence between the optimal solutions of a formulated LP and the optimal policies of the constrained MDP derived from these solutions, it suffices to preserve the recurrence or the unichain property of these components.
To address this restriction, we introduce flow constraints in LP 2 given in (21) (replacing constraint (v )) to ensure the recurrence of the components r k (M), k ∈ [m], in the induced chain. It helps to introduce some notation in order to express such constraints. We define the transition relation of an MDP by T rel = {(s, s ) ∈ S×S|s = s ∧∃a ∈ A(s), T (s |s, a) > 0} (Velasquez, 2019). This corresponds to the graph structure of the MDP. For each TSCC r k (M), we further define its graph structure as T rel k = T rel ∩ r k (M) × r k (M). We can now add flow constraints in order to ensure that, for the Markov chain induced by the solution policy, each set r k (M) will remain a recurrent class without necessarily having to take every action available in that set. (21) is such that every state in r k (M) can reach and is reachable from every other state in r k (M). For each k ∈ [m], constraint (vi ) induces an initial flow out of a randomly chosen state s i ∈ r k (M) and into its neighbors s , that is proportional to the transition probability T π (s |s i ) in the Markov chain induced by the solution policy; constraint (viii ) establishes the flow capacity between states in a similar manner; (x ) ensures that the incoming flow into every state in r k (M) is greater than the outgoing flow; finally, constraint (xii ) ensures that there is incoming flow into every state in r k (M). These constraints ensure that every state in r k (M) is reachable from s i , whereas constraints (vii ), (ix ), (xi ), (xiii ) address the foregoing in the reverse graph structure of the MDP, thereby ensuring that s i is reachable from all states in r k (M). We remark that the feasible set in (21) is a superset of that in (20) since the flow constraints (vi )-(xiv ) are implied by (v ), hence LP 2 is less-constrained than LP 1 .
We can readily state the following two theorems establishing the correctness of LP 2 , which are the counterparts of Theorem 1 and 2. In particular, Theorem 3 guarantees that the solution to LP 2 is a CP policy, while Theorem 4 establishes that the policy (14) derived from the optimal solution to LP 2 in (21) solves SSPS(Π CP ), i.e., is optimal among the class of CP policies and meets the steady-state specifications.
Theorem 3. Given an LMDP M, let (x, y) ∈ Q 2 and π be defined as in (14), where Q 2 is the feasible set of solutions to LP 2 (21). Then, π ∈ Π CP .  (21) is feasible iff there exists a policy π ∈ Π CP , where Π CP is defined in (16), such that the Markov chain M π = (S, T π , β) satisfies the specifications Φ ∞ L . Further, given an optimal x * , y * of (21), the policy π(x * , y * ) defined in (14) is optimal in the class of policies Π CP and meets the specifications Φ ∞ L .

SSPS(Π CPU ) -Synthesis over Class-Preserving up to Unichain Policies
In this section, we discuss policy synthesis over the larger set of policies Π CPU . We provide a sufficient condition under which we can identify an optimal policy π ∈ Π CPU that meets the specifications. Based on this result, we develop an iterative algorithm to construct a policy in Π CPU that provably meets the desired specifications. Next, we give a sufficient condition for SSPS(Π CPU ), characterized in terms of the set of optimal solutions to LP 3 in (22). Note that the feasible set of LP 3 is the intersection of the set Q 0 in (19) and the set of variables satisfying the steady-state specifications, that is, without the positivity or flow constraints in (20) and (21), respectively.
Recall that a strongly connected digraph is one in which it is possible to reach any node starting from any other node by traversing the directed edges in the directions in which they point. Theorem 5 states that the policy π in (14), derived from an optimal solution to LP 3 in (22), solves SSPS(Π CPU ) if the directed subgraphs corresponding to the support of the optimal solution in the TSCCs of M are strongly connected. In Theorem 5, we define the digraph associated with the support of a given solution x as the graph whose vertices are all states s with x s > 0 and whose edges correspond to actions a for which x sa > 0.
Theorem 5. Given LMDP M, let Q * be the set of optimal solutions of LP 3 (22) and X * := {x : (x, y) ∈ Q * for some y}. Given , then the policy π in (14) is optimal in the class of policies Π CPU and meets the specifications in Φ ∞ L . Corollary 1. If the condition in the statement of Theorem 5 holds for all x ∈ X * , then LP 3 (22) solves SSPS(Π CPU ).

Generation of policies in Π CPU
Inspired by Theorem 5, we devise a row-generation-based algorithm to search for a policy π ∈ Π CPU as shown in Algorithm 1. First, LP 3 (22) is solved. If the digraph corresponding to the support of the obtained solution is strongly connected for each of the TSCCs of LMDP M, the policy in (14) is computed and the search stops. However, if the solution does not correspond to a strongly connected digraph in some TSCC, then there must exist a non-empty set of states with no outgoing edges to the rest of the states in that TSCC. Hence, for some k ∈ [m] we find a cut, that is, a set of states C that has no outgoing edges to the complement set r k (M) \ C. The constraint in (23) corresponding to this cut is added to include the edges in the support, where A = {a ∈ A(s) : T (s |s, a) > 0, s ∈ r k (M) \ C}. The constraint forces the addition of missing edges across this cut in a greedy manner (by forcing the sum of the state-action variables corresponding to these edges to be non-zero) to eventually produce a strongly connected digraph. The process is repeated until a strongly connected solution is found.
) forms a SCC for every k ∈ [m] then compute π using (14) isSConnected = T rue else find a cut and update C and A end if end while

Additional Insights
This section provides additional remarks and examples to shed more light on the linear programming formulations. The section may be skipped without loss of continuity.

Non-surjective mapping
All occupation measures induced by the policies of interest are elements of Q 0 (19), that is, Pr ∞ π ∈ X 0 := {x : (x, y) ∈ Q 0 for some y} if π ∈ Π CPU , which is affirmed by Lemma 7 stated in Appendix A. However, in general, P ∞ (Π CPU ) ⊂ X 0 , i.e., the set P ∞ (Π CPU ) is a proper subset of X 0 . In mathematical terms, the mapping (9) between the set of policies Π CPU and the set X 0 is injective but non-surjective. In turn, there may exist elements of X 0 that are unpaired with policies in Π CPU . This is illustrated by the following example.

Insufficient constraint set
The set Q 0 correctly encodes constraints on the limiting distributions of Markov chains induced by policies in Π CPU (with the state classification corresponding to r(M) andr(M)). However, the lack of one-to-one correspondence between feasible solutions and policies (see The steady-state distribution of the policy (14) derived from an optimal solution (x * , y * ) to LP 0 is generally not equal to x * . In turn, specifications encoded as constraints on the state-action variables as in (22) will not necessarily be met by the policy. This is best illustrated via a simple example.

Remarks on SSPS(Π CPU )
1) Note that, in the previous example, the derived policy π / ∈ Π CPU . However, if π := π(x * , y * ) ∈ Π CPU , where (x * , y * ) is an optimal solution to (22), then π will be optimal over Π CPU ⊇ Π CP i.e., solves SSPS(Π CPU ). This follows from the optimality of (x * , y * ) and Lemma 6 in the appendix, which gives a sufficient condition for the existence of a one-to-one correspondence between the elements of Q 0 and the steady-state distribution of policy (14).
2) In general, if we dispense with the flow constraints in (21), we have no guarantee that the TSCCs r k (M) will be unichain in M π under such π. For example, M π induced by the policy π given in Example 3 has r 1 (M π ) = {2}, r 2 (M π ) = {3}, i.e., π / ∈ Π CPU . However, if the rewards in this example are modified such that R(s 1 , a 1 ) = R(s 2 , a 1 ) while keeping all other rewards unchanged, then π ∈ Π CPU . Therefore, under certain sufficient conditions on the reward vector, LP 3 in (22) solves SSPS(Π CPU ).

Existence of Optimal Policies
Modified LP. The feasible set Q 1 for LP 1 is not compact given the strict inequalities of constraint (v ) in (20). Therefore, the maximum in (20) may not always be attained on the set. This can be easily remedied by replacing the strict inequalities with bounded ones via introducing an arbitrarily small constant > 0 on the right-hand side. Even when such requirement is not made explicit, a constant is dictated by the numerical precision of the LP solvers. We define LP 1 ( ) similar to (20), with constraints (v ) replaced with the bounded inequalities in (v) for some > 0, Theorem 6 stated next is analogous to Theorem 2 with the modified program LP 1 ( ); it establishes that every feasible solution of LP 1 ( ) yields a policy that is in Π EP , and conversely, for every EP policy that meets the steady-state specifications, there exists an > 0 such that its steady-state distribution is LP 1 ( )-feasible. Moreover, the policy obtained from the optimal solution to LP 1 ( ) solves SSPS(Π EP ), that is, its expected average reward can be made arbitrarily close to the supremum over the set Π EP as → 0.
(3) Let x * , y * be an optimal solution to LP 1 ( ) and π * := π(x * , y * ) the corresponding policy in (14). Then, A similar result holds for CP policies if the maximum in (21) cannot be attained over the feasible set by transforming constraints (x )-(xiii ) to bounded ones. The generalization is straightforward, thus omitted for brevity.
Compact policy set -policies with bounded support. The foregoing existence issue stems from the open set definition of Π EP in (15), a result of which is that an optimal policy from the set (i.e., one that maximizes the average reward) may not always exist. Therefore, we introduce a slightly modified definition next, in which we force a lower bound on the values a policy assumes on its support, i.e., require that π(a|s) ≥ δ, for some arbitrarily small constant δ > 0. We formally introduce the definition of the compact set of policies, then state a result analogous to Theorem 2 based on this definition for completeness.
(2) Let x * , y * be an optimal solution to LP 1 (δ) and R * (δ) the average reward of the corresponding policy in (14). Then, According to Theorem 7, every feasible solution to LP 1 (δ) yields a policy in Π EP (δ). Also, the gap between the optimal expected average reward over the set Π EP (δ) and the optimal reward of LP 1 (δ) approaches zero as δ → 0.

Extensions
In this section, we explore extensions beyond class-preserving policies, as well as an alternative type of specifications applicable to transient states.

Beyond Class-Preserving Policies
In this section, we derive an alternative condition given in Theorem 8 under which LP 3 in (22) is guaranteed to yield a stationary policy whose steady-state distribution meets the desired specifications. The policy generated need not be in Π CPU . The proof of Theorem 8 follows from the sufficient and necessary optimality conditions of program (22) (Bertsimas & Tsitsiklis, 1997). The condition is characterized in terms of the rewards vector R = [R(s, a)], s ∈ S, a ∈ A(s). First, we introduce the following definition.
Definition 20 (Cone of feasible directions). The cone V (x, y), where (x, y) is any feasible solution to LP (22), is defined as Theorem 8. Given LMDP M, let (x, y) be a feasible solution of (22). If R = [R(s, a)], s ∈ S, a ∈ A is an interior point of the dual cone where , denotes the inner product, then the policy π in (14) meets the specifications Φ ∞ L . Further, π is the unique optimal policy in the class of policies for whichr(M) ⊆r(M π ).
We remark that the policy could be outside of Π CPU , but preserves the transience (or isolation) of the states inr(M). While the statement of Theorem 8 imposes a conservative assumption on the rewards vector which may be generally hard to verify, it opens up possibilities for further research on steady-state planning over larger sets of policies (beyond Π EP , Π CP and Π CPU considered in this paper) -in this case, sets of policies that preserve the transience ofr(M). Ultimately, one would hope to tackle SSPS(Π) for arbitrary sets of stationary policies Π. These are directions for future investigation.

Transient Specifications
In Definition 12, we introduced specifications on the steady-state distribution. However, such specifications are only useful in the recurrent sets where states are visited infinitely often. A transient state f ∈r(M π ) on the other hand will only be visited a finite number of times, i.e., Pr ∞ π (f ) = 0 for any stationary policy π ∈ Π S . In this section, we present an alternative specification type which can be applied to transient states.
We first describe a suitable property of transient states against which specifications can be applied. We then define transient specifications based on this property.
Definition 21 (Expected number of visits (Kemeny & Snell, 1963)). Given an MDP M and policy π ∈ Π S , the expected total number of times that state f ∈r(M π ) is visited under policy π is that is, if the expected number of visits to transient states f ∈ L i in the Markov chain M π falls within the interval [l i , u i ].
Suppose that we have a set of labels L tr over transient states, and a set of transient specifications Φ tr L tr . We can augment the LMDP found in Definition 12 to incorporate these transient specifications as follows. Let L ∞ be the set of steady-state labels, and let Φ ∞ L ∞ be corresponding steady-state specifications. We define a complete set of labels L = (L ∞ , L tr ) and specifications Φ L = (Φ ∞ L ∞ , Φ tr L tr ), and define an LMDP as M = (S, A, T, R, β, L, Φ L ). Our next result regarding y and ζ π for the transient states gives a sufficient condition for the policy to meet the transient specification.
We remark that this is analogous to Lemma 6 stated in the appendix, which establishes that if we have a point (x, y) ∈ Q 0 for which (14) yields a CPU policy, then Pr ∞ π = x. Given this characterization, we can augment LP 1 (20) and LP 2 (21) with constraint (xv ) to synthesize policies subject to transient specifications.

Numerical Results
In this section, we present a set of numerical results to corroborate the findings of the theoretical analysis. In Section 7.1, we verify the steady-state behavior of the policies derived from the proposed LPs using the Frozen Islands example of Figure 3, followed by a study of their behavior in the presence of additional transient specifications in Section 7.2. In Section 7.3, we present the results of a study which shows that the empirical steadystate distributions and average number of state visitations induced by the derived policies converge to values that meet the desired specifications. In Section 7.4, we evaluate the average reward achieved by said policies and examine the impact of various restrictions in their respective LPs on the optimal values of the objective using the Toll Collector example of Figure 13. A case study is also presented featuring the progress of the iterative Algorithm 1 for generating a CPU policy. A natural generalization of the specifications to the product space of state-action pairs is presented in Section 7.5. We present two numerical experiments to support the theoretical findings of Section 5.4.4 in Section 7.6. Finally, we examine the scalability of the proposed formulations in Section 7.7, where we present the runtime results for problems with increasing size conducted in various environments.

Steady-State Specifications
In this section, we demonstrate the correct-by-construction behavior of the policies proposed. As an illustrative example, we first examine the behavior of a policy in Π EP using the Frozen Island example shown in Figure 3. We run our proposed LP 1 (20) to calculate the steady-state distribution Pr ∞ π (s), and show the values for the two TSCCs (the two small islands) in Figure 6.
The heat map gives insight into the means by which the agent satisfies the specifications. After the agent enters an island, it spends a large amount of time in states s 33 , s 36 , s 48 , s 49 , s 61 , and s 64 , in the sense of asymptotic frequency of visits as given by Pr ∞ π (s). The agent also frequently visits states s 36 and s 61 to satisfy the steady-state specifications (L log1 , In addition to visiting the aforementioned states to satisfy the constraints, the agent also visits state s 48 over 25% of the time to maximize its expected reward (recall that R(·, ·, s 48 ) = R(·, ·, s 64 ) = 1).
The right three plots of Figure 7 show the values of Pr ∞ π (s) along with the optimal values x * s obtained from LP 1 (20) for SSPS(Π EP ), LP 2 for SSPS(Π CP ), and Algorithm 1 for  SSPS(Π CPU ). In each of these, the steady-state distribution matches the one estimated by the LP for every state. This in fact holds for all state-action pairs as well, i.e., Pr ∞ = x * . This condition is essential to the proof of Theorems 2, 4 and 5 and ensures that the policy is both optimal and satisfies the steady-state specifications. We calculate the policy corresponding to the optimal solution of LP (4.7.6) by Kallenberg (1983) given in (13) with the additional specification constraints for comparison. As shown in Figure 7 (left), the derived policy fails to give a steady-state distribution equal to x * . In addition, we obtain a policy from the solution to LP (3.5) by Altman (1999) of a discounted reward MDP (with the additional specification constraints) using a discount factor γ = 0.9999. As observed in the second from the left plot of Figure 7, the steady-state distribution of the derived policy does not match x * . In Table 1 Table 1 shows the values of e x * L i := s∈L i x * s and Pr ∞ π (L i ) := s∈L i Pr ∞ π (s), demonstrating that all of the specifications are met for the proposed methods. For Kallenberg's and the discounted formulations, however, although x * L log1 and x * L canoe1 satisfy the specification, the policy yields steady-state distributions Pr ∞ π (L log1 ) and Pr ∞ π (L canoe1 ) which violate the specifications (these violations are highlighted with bold red text). In other words, e x * L canoe1 = Pr ∞ π (L canoe1 ) and e x * L log1 = Pr ∞ π (L log1 ) for the Kallenberg and discounted formulations. The table also shows the optimal reward R * given by our proposed methods, as well as the expected average reward yielded by the policy, i.e., R ∞ π := s∈S a∈A(s) Pr ∞ π (s, a)R(s, a). While R * obtained by Kallenberg's formulation is larger than that of the EP and CP methods, the proposed LPs produce policies   which yield larger values of R ∞ . Additionally, as the discount factor γ approaches 1, the discounted reward does not converge to the expected reward. The policies obtained from the discounted reward formulation achieve larger rewards R ∞ by violating the steady-state constraints and spending larger proportions of time in the rewarding fishing sites.

Synthesis for Transient Specifications
In this section, we demonstrate the behavior of the policies derived subject to transient specifications following the framework described in Section 6.2. We again compare the policies derived from our proposed formulations to that of Kallenberg with regard to meeting such specifications for the Frozen Islands example of Figure 3. The labels over states in r(M) are set to L tools = {s 7 , s 13 , s 23 }, L gas = {s 10 , s 16 }, and L supplies = {s 2 , s 15 , s 29 } as shown in Figure 9 (left). The agent sets out to collect some tools, fill up enough gas, and pick up the required fishing supplies before transitioning to one of the smaller islands which correspond to TSCCs. This is reflected in the transient specifications (L tools , [10, N tr ]), (L gas , [12, N tr ]), (L supplies , [15, N tr ]) ∈ Φ tr L . These specifications bound the expected total number of visitations to certain states inr(M), where N tr = 200. Figure 8 presents the values of the expected total number of times a state s ∈r(M) is visited under policy π, denoted by ζ π (s), along with the optimal values y * s , obtained from Kallenberg's LP, LP 1 (20), LP 2 (21), and Algorithm 1. As shown, the results match the expected number of visitations for the proposed methods for every state.
For each transient specification Table 2 shows e y * L i := f ∈L i y * f and the expected total number of visitations achieved by the policy in corresponding states ζ π (L i ) := f ∈L i ζ π (f ). As shown, LP 1 , LP 2 and Algorithm 1 yield policies that satisfy the given specifications, while the policy derived from the Kallenberg LP does not. The last column shows the expected total number of visitations achieved by the policy on the larger (transient) island, where ζ π (r(M)) = f ∈r(M) ζ π (f ). Figure 9 (right) shows a heat map for the expected number of visits to the transient states, i.e. the large island. The policy is calculated using LP 1 (20). In addition to the constraints (L tools , [10, N tr ]), (L gas , [12, N tr ]), and (L supplies , [15, N tr ]), we also add the constraint (r(M) \ (L tools ∪ L gas ∪ L supplies ) , [0, 10]) to reduce the amount of time spent in transient states with no resources. As shown, the agent meets the specifications largely by visiting states s 13 , s 16 , and s 29 to collect tools, gas, and supplies, respectively.    Figure 10: Execution of policy, showing (left) average visits and (right) average reward up to time n.

Empirical Study
In this section, we simulate the policies derived from our LPs to show the validity of our formulations and to further demonstrate the failure of the Kallenberg formulation to yield optimal rewards and meet specifications.
Let S t and A t denote the state and action, respectively, of the Frozen Island example at time t assuming policy π and initial distribution β. The average number of visits f π,n and average reward g π,n up to time n are defined as f π,n (L) = 1 n n t=1 1 L (S t ), 1 L (s) = 1 s ∈ L 0 s / ∈ L (32) We take an ensemble average over 5000 paths. First, we solve LP (4.7.6) of Kallenberg (1983). In Figure 10 (left), the solid green line shows the average number of visits to the states in L log1 = {s 34 , s 36 , s 38 , s 43 }, and the horizontal dashed green line indicates the steady-state distribution. The square markers show the lower bound of the specification on the logs. While the value of f π,n (L log1 ) converges to the steady-state distribution, the policy fails to meet the steady-state specification. This follows from the fact that Pr ∞ π = x * . Next, we produce an EP policy by executing LP 1 (20), using no transient specifications. The average number of visits to the states in L log1 is shown as a solid red line in Figure 10 (left). Not only does the average number of visits converge to the corresponding steady-state distribution (dashed black line), but the specification is met. We observe similar results for CP and CPU policies as well.
In Figure 10 (right), the solid green and red lines show the average reward for the Kallenberg LP and our proposed LP 1 , respectively. The dashed green line indicates R * for Kallenberg's formulation. As can be seen, for similar reasons as before, the average reward converges to a reward other than that output by the LP. On the other hand, LP 1 converges to the corresponding LP reward R * (black dashed line).
The vertical green and red dashed lines in Figure 10 indicate the average time of entry into r(M) for LP 1 and Kallenberg's LP, respectively, where the time of entry φ π is given by In both cases, the agent spends an unduly amount of time in the transient states before transitioning to a recurrent set, which may be undesirable. To reduce the amount of time spent in the transient states, we next introduce a transient specification (r(M), [0, N tr ]) and rerun LP 1 . The constant N tr is used to control the time of entry into the recurrent sets. The results are shown for N tr = 5 (blue lines) and N tr = 500 (yellow lines). In both cases, convergence of the average visits to Pr ∞ π (L log1 ) occurs at a much faster rate, leading to a much faster accumulation of reward.
We now comment further on the simulation for N tr = 5. The policy produced by LP 1 separates the first small island into two main subsets. The agent tends to visit state s 33 repeatedly after entering the first small island, leading to an above average number of visits to log1 states. This results in an initial "overshoot" of Pr ∞ π (L log1 ). This effect is not seen for N tr = 500 due to the averaging effect of f π,n (L). Likewise, the policy tends to delay the entry of the agent into state s 48 where rewards are accumulated. This delay is especially noticeable in g π,n for N tr = 5 due to the logarithmic time scale.
In the same vein, we explore the simulated behavior of our policies in terms of the number of visits to transient states, where the number of visits h π,n (L) to states in L ⊆r(M) up to time n is defined as h π,n (L) = n t=1 1 L (S t ).
In Figure 11, we show the number of visits to the transient states for the same policies as shown in Figure 10. For the policies produced by LP 1 , h π,n (r(M)) converges to the optimal y * r(M) . On the other hand, as described in Section 7.2, for the Kallenberg formulation we have ζ π = y * and so the derived policy fails to converge to y * r(M) .

Comparison of Policies
Recall that policies in Π EP exercise all transitions in the TSCCs of an MDP. By contrast, policies in Π CP and Π CPU are less restrictive in that they only preserve the state classification and the unichain property of these components, respectively. In turn, they often yield larger expected rewards while simultaneously satisfying desired specifications. In this section, we verify the correctness of such policies and compare their optimal rewards.  Figure 12 illustrates the Markov chains induced by policies in Π EP , Π CP , and Π CPU , respectively, for the MDP shown in its first column. The policies are obtained from the optimal solutions of the corresponding LPs. As observed, the Markov chain induced by the EP policy (Column 2) contains all transitions in the TSCCs of the underlying MDP. The self loops of states s 3 ,s 5 , and s 9 are missing in the Markov chain induced by the CP policy without affecting the recurrence of each of the TSCCs. In the case of the Markov chain induced by the CPU policy, the state s 3 is transient in the TSCC {s 3 , s 4 , s 5 }, but all TSCCs of M remain unichain in the induced Markov chain. That is, each TSCC contains exactly one recurrent component.
In order to compare the performance of our EP, CP, and CPU policies, we define the Toll Collector example given by the LMDP M of Figure 13. In this problem, an agent must choose one of m cities to visit, each of which corresponds to a TSCC of M. The k-th city consists of n k , k ∈ [m] counties represented as vertices and roads connecting these counties represented by edges. The roads with toll booths yield a positive reward for collecting a toll. However, the agent needs to spend some time on roads without toll booths in order to build them. We consider an instance of the Toll Collector problem for which m = 3 and the number of states per TSCC n k = n, ∀k. To highlight the gap between the optimal rewards of the different policies, we define the labels L k = {s ∈ r k (M) : R(s, a, s ) = 0, ∀a ∈ A(s), s ∈ r k (M)} and Φ ∞ L = (L k , [l, 1]), respectively, ∀k ∈ [m]. As such, per Φ ∞ L , the steady-state probability of states with no rewardful transitions is forced to be bounded below by l. We will use this steady-state specification with various values of l to show that, for lower values of l, there is a significant gap in expected rewards observed by the various policies. As this l value is increased, the gap can be shown to diminish. For each state s i in r k (M), there are n k − 1 actions, each of which causes a transition to another state in r k (M) with probability 1. The reward function is defined such that, in each TSCC, there is a positive reward by taking the action that leads from some state s i to its neighbor s i+1 and vice-versa. That is, R(s i , ·, s i+1 ) = R(s i+1 , ·, s i ) = 1 for some i. These rewards are designated with red solid circles in each TSCC. All other rewards are 0. The initial distribution β is uniform over S. The labels and steady-state specifications are given by L k = {s ∈ r k (M) : R(s, a, s ) = 0, ∀a ∈ A(s), s ∈ r k (M)} and Φ ∞ L = (L k , [l, 1]), respectively, for all k ∈ [m].  Figure 14 (left) compares the optimal rewards achieved by the different policies as a function of the total number of states in the TSCCs (i.e., 3n) when l = 0. As the number of states increases, the gap between the average reward of the EP policies and their CP and CPU counterparts increases. In this scenario, the EP policies incur a quadratic loss relative to CPU policies since they are forced to exercise all existing transitions equally and there are O(n 2 k ) such transitions in the k-th TSCC. On the other hand, an optimal CPU policy preserves the unichain property while exercising exclusively the two transitions with positive reward in each TSCC. A smaller loss is incurred by CP policies since they are only required to preserve the recurrence of the TSCCs and can thus restrict themselves to visiting the outer perimeter of each TSCC. In doing so, the CP policies incur a linear loss when compared to the CPU policies because they must visit every state in a TSCC infinitely often in order to preserve the recurrent classification of these states. Figure 14 (right) illustrates the average rewards as a function of the lower bound l for the three types of policies when the number of states in each TSCC is n = 25. When l increases, the average reward gap between the different policies diminishes since the agent has to spend more time in states with no rewards to meet the desired specifications.

Operation of Algorithm 1
In this subsection, we present in detail the operation of the proposed Algorithm 1 to generate a CPU policy. Consider the LMDP given in Figure 15. For each iteration, LP (22) is solved and the digraph of the support of the solution in each TSCC is shown (colored nodes). In the first iteration, for the first TSCC, states s 4 and s 5 form a SCC, while s 3 does not belong to the support of the solution. For both the second and third TSCCs, all respective states belong to the support but they do not form a SCC, thus we can find cut(s) (as can be seen at the bottom of the figure of the second iteration). In the second iteration, the dotted edges are added which results in one SCC for the second TSCC (no additional constraints are needed) but not for the third TSCC. Thus, we consider additional cuts as shown at the bottom of the figure of the third iteration. In the last iteration, the stopping criteria is met (the digraph in each of the three TSCCs is strongly connected). The final Markov chain induced by the CPU policy derived from the solution to the LP of the third iteration is shown on the right side of Figure 15. States {s 3 , s 4 , s 5 } form a unichain component, states {s 6 , s 7 , s 8 , s 9 } form a recurrent component, and states {s 10 , s 11 , s 12 , s 13 , s 14 , s 15 } belong to a TSCC where all edges are preserved. In each iteration, we illustrate the support of the optimal solution for the TSCCs of M (middle columns) along with the edges (state-action pairs) for a given cut. After three iterations, the support of the optimal solution corresponds to SCCs in each of the TSCCs. Every TSCC of M is a unichain component in the Markov chain M π induced by the resulting policy (last column).

Specifications on State-Action Pairs
Up to this point, we have defined steady-state and transient specifications over states. However, the framework proposed can be used to synthesize policies with provably correct behavior on the level of state-action pairs as well. As an example, consider the LMDP

Steady-State Transient
Pr ∞ π (s 4 , a 1 ) Pr ∞ π (s 6 , a 2 ) Pr ∞ π (s 10 , a 1 ) ζ π (s 2 , a 1 ) ζ π (r(M)) EP 0. 11 [20,50]). We also set the average total number of visitations N tr = 50. Table 3 shows the steady-state distributions Pr ∞ π (s, a) and the expected number of visitations ζ π (s, a) for the labeled sets, as well as the total number of visitations ζ π (r(M)) to the setr(M) for EP, CP and CPU policies. As shown, the policies meet both steady-state and transient specifications defined over the product space S × A.

Modified LP and Policy Set
Impact of in LP 1 ( ). In this section, we use the MDP example of Figure 15 to investigate the impact of the parameter > 0 on the total reward induced by an optimal EP policy. In particular, we solve LP 1 ( ) with descending values of and compute the optimal reward R * ( ). As shown in Figure 16, R * ( ) increases monotonically as we decrease with diminishing return, and converges to nearly 0.36 as → 0. For values of below 10 −4 , the change in average reward if we further decrease is insignificant. Therefore, in our experiments we have set = 10 −4 . Policies with bounded support. Here, we verify the result of Theorem 7. Consider the example of Fig. 2 where R(s 2 , a 1 ) = R(s 3 , a 1 ) = R(s 3 , a 2 ) = 0.1 and R(s 2 , a 2 ) = 0.5.

Scalability
We demonstrate the scalability of the proposed formulations using two sets of experiments. The first set of experiments are performed on a standard desktop with 16GB of RAM using the Matlab CVX package for convex optimization (Grant & Boyd, 2014. We also perform a second set of experiments on a standard desktop of 128GB of RAM using the commercial CPLEX Optimizer, which provides a higher-precision mathematical solver for large-scale linear programming. For the first set of experiments, we experiment with instances of increasing size of the Toll Collector problem (Figure 13), the Frozen Islands environment ( Figure 3) and random partition graphs from the NetworkX library (Hagberg, Swart, & S Chult, 2008). The Toll Collector problem uses an MDP with three TSCCs, each of size n, while the Frozen Islands environment consists of an n × n grid. We also experiment with random MDPs constructed from n-node directed Gaussian partition graphs generated using the NetworkX toolbox (Hagberg et al., 2008). For such graphs, the cluster sizes are drawn from a normal distribution with mean and variance n/5, and two nodes within the same cluster are connected with probability p in , while two nodes in different clusters are connected with probability p out (Brandes, Gaertler, & Wagner, 2003). For these partition graphs, the state space corresponds to the vertex set, the number of actions is equal to the maximum node outdegree and the transitions are deterministic. The initial distribution is uniform over the setr(M) and the rewards are selected such that only the first action from every state yields a positive reward, i.e., R(s ∈ r(M), a 1 , ·) = 1 and 0 otherwise. An instance of an MDP constructed from a 40-node Gaussian partition graph is illustrated in Figure 18. The specifications for the three environments are given in the caption of Table 4.
For each example, we generate EP, CP and CPU policies using LP 1 , LP 2 and Algorithm 1, respectively, and report on the runtime as we increase n. All instances were verified to meet the given specifications. The results are summarized in Table 4 demonstrating the scalability of the proposed formulations. As shown, LP 2 incurs the largest runtime as it incorporates additional variables in the flow constraints to enforce the recurrence of the TSCCs.

States in ҧ ( )
States in ( ) Figure 18: A NetworkX random 40-node digraph used to generate a LMDP for the third example of Table 4.
To further examine the scalability of the LPs underlying the different policies to much larger problem sizes, additional experiments are conducted using the CPLEX 12.8 solver. We run simulations of the LP in (22), LP 1 (with the positivity constraints) and LP 2 (with the flow constraints) for random instances of the Frozen Islands problem. The runtime results are reported in Table 5. For a 64 × 64 and a 128 × 128 grid, LP 2 (the most complex) is solved in about 20 seconds and 15 minutes, respectively, demonstrating the effectiveness of the developed formulations even for MDPs with over ten thousand states.

Conclusion
A framework for steady-state policy synthesis in general MDPs was developed to derive policies that satisfy constraints on the steady-state behavior of an agent. Linear programming solutions were proposed and their correctness proved for classes of edge-preserving and class-preserving policies. The framework also enables policies that meet specified constraints on the expected number of times the agent visits transient states. Numerical simulations of the resulting policies demonstrate that our approach overcomes limitations in the literature.
The article provides the first solution to the highly understudied problem of steadystate planning over stationary policies in constrained expected average reward multichain MDPs. The policies derived come with rigorous guarantees on the asymptotic long-term  Table 4: Average runtime results (in seconds) for 20 instances of the Toll Collector, Frozen Islands, and Gaussian partition graphs of increasing problem size n. The Toll Collector MDP consists of three TSCCs, each of size n. The detailed LMDP parameters are given in the caption of Figure 13 with a steady-state specification lower bound l = 0.05. The three-island problem described in Figure 3 forms an n × n grid.  Table 5: Average runtime (in seconds) of 20 instances per LP for the three-island problem described in Figure 3. These islands combined form an n × n grid. In each of the smaller islands, logs are randomly distributed over 1/4 of the states and a canoe (fishing rod) is placed in the top-left (bottom-right) tile. For these experiments, we have the constraints (L log1 ∪L log2 , [0.3, 1]), (L canoe1 ∪L canoe2 , [0.05, 1]) and reward function R(·, ·, L fish1 ∪L fish2 ) = 1, R(·, ·, S \ L fish1 ∪ L fish2 ) = 0.
behavior of agents. The research findings have bearing on the fields of explainable, safe and trustworthy AI, where there is increased concern about explaining AI decisions, ensuring safety constraints are met, and building trust in the behavior of autonomous agents.
FA8750-20-3-1004, the Air Force Office of Scientific Research through Award 20RICOR012, and the National Science Foundation through CAREER Award CCF-1552497 and Award CCF-2106339.

Appendix A. Technical Lemmas
Proof of Lemma 2 Let π ∈ Π EP . Hence, r(M π ) = r(M) according to (15). Consider the set of states r k (M) in a TSCC of M, for some k ∈ [m]. We will show that this set is also a TSCC of M π .
To this end, we first show that they form a SCC in the transition graph of M π . Since π ∈ Π EP , then π(a|s) > 0, ∀s ∈ r(M), a ∈ A(s). Hence, every action a ∈ A(s) available in state s ∈ r k (M) is played with non-zero probability. From (1), for a pair of states s, s ∈ r k (M), T π (s |s) > 0 if ∃a ∈ A(s) such that T (s |s, a) > 0. Thus, for every directed path between a pair of nodes in r k (M) in the transition graph of M, there is a similar path between the same nodes in the transition graph of M π . Therefore, the states r k (M) also form a SCC in the transition graph of M π . Also, the set r k (M) is reachable in M π since r k (M) ⊆ r(M π ). Finally, there are no outgoing edges to states in S \ r k (M π ) since the edge set of the transition graph of M π is a subset of the edge set of the transition graph of M. We conclude that r k (M π ) = r k (M), ∀k ∈ [m]. From the definition of the set of CP policies in (16), it follows that π ∈ Π CP , proving that Π EP ⊆ Π CP . The two conditions in (16) are special cases of the more general requirements in (17), hence Π CP ⊆ Π CPU .
The following lemma gives a characterization of the Markov chain state classification induced by a policy (14) derived from a feasible point of the constrained set Q 0 in (19).
(b) If s ∈ r k (M) ∩ E x for some k ∈ [m], then s ∈ r(M π ). As a consequence, if s ∈ r k (M) ∩r(M π ), then s ∈ E x , i.e., x s = 0.

Proof of Lemma 3
First, we show part ( and the fact that f is only reachable from states inr(M), Note that the second equality above follows from the definition of π in (14) for a state f / ∈ E x . Two cases arise. If f / ∈ E y , then y f = 0. Hence, β f = 0 and T π (f |f ) = 0, ∀f ∈ E y . Thus, we have shown that every state f in E y ∩r(M) can only be reached from states in E y ∩r(M), and that all such states have zero initial probability. Thus, every such state is either isolated or resides in an isolated component. Therefore, f ∈r(M π ), wherer(M π ) consists of transient or isolated states. Now consider the other case where f ∈ E y , i.e., y f > 0. Assume, for the sake of contradiction, that f ∈ r(M π ). Hence, f ∈ F , for some TSCC F (this subsumes the case where f is absorbing with |F | = 1). Then, it must be that F ⊆r(M) since f is not reachable from states S \r(M) even under an EP policy. Summing (36) over the set F , we have where the second equality is due to the closure of the set F , implying that j∈F T π (j|f ) = 1 for f ∈ F . It follows that β f = 0, ∀f ∈ F , and T π (f |f ) = 0, ∀f ∈ (r(M) \ F ) ∩ E y . Therefore, F ⊆r(M π ), yielding a contradiction. Hence, f ∈r(M π ). We conclude that r(M) ⊆r(M π ). Next, we prove part (b) which states that every state s in a TSCC of M for which x s > 0 is both recurrent and non-isolated in M π . Consider a state s ∈ r k (M) ∩ E x for some k ∈ [m], so x s > 0. Assume, for the sake of contradiction, that s ∈r(M π ), i.e., the state s is either transient or isolated. If s is transient, then the column of the matrix T ∞ π corresponding to state s is zero. Therefore, from constraint (i ) in (19), we have x s = 0, i.e., s / ∈ E x , yielding a contradiction. If s ∈ F for some isolated component F , then by summing constraint (ii ) over states s ∈ F , and using the fact that β f = 0, ∀f ∈ F and that s ∈ F is only reachable from states in the isolated set F . Since s ∈F T (s |f, a) = 1, ∀f ∈ F, a ∈ A(f ), by the closure of F , we get that s ∈F x s = 0 by interchanging the order of the sums, i.e., s ∈ E x , also yielding a contradiction. Hence, s ∈ r(M π ). The second clause of Lemma 3 (b) remains to be proved, i.e., s ∈ r k (M) ∩r(M π ) =⇒ x s = 0. Consider s ∈ r k (M) ∩r(M π ). Thus, s / ∈ r(M π ), so it follows from the result we have just shown that s ∈r(M) ∪ E x . However, since s ∈ r k (M) for some k, then s / ∈r(M). Hence, s ∈ E x .
Next, we state and prove two lemmas that will be useful in the proof of Lemma 6, which establishes a sufficient condition for the existence of a one-to-one correspondence between a feasible point in Q 0 and the steady-state distribution of the Markov chain induced by the policy in (14) derived from this solution.
Lemma 4. Given MDP M, if (x, y) ∈ Q 0 , where Q 0 is the set of points in (19), then x is a stationary distribution of the Markov chain M π induced by the policy π in (14).

Proof of Lemma 4
First, consider s ∈r(M), and define X 0 := {x : (x, y) ∈ Q 0 for some y}. Since x ∈ X 0 , we have x s = 0 by constraint (iii ). Also, s∈S x s T π (s |s) = s∈r(M) where the first equality holds since s ∈r(M) is only reachable from states s ∈r(M) even when all edges defining possible transitions in the MDP are preserved. Next, consider s ∈ S \r(M). We have The first equality follows from the fact that x ∈ X 0 , the second from the definition of π in (14), and the last from the definition of T π in (1) and that x s = 0, ∀s ∈ S \ E x . Finally, x e = 1, by summing constraints (ii ) over all s ∈ S.

Proof of Lemma 5
To show (40), note that, since π ∈ Π CPU , we have that r k (M π ) ⊆ r k (M), k ∈ [m], where r k (M π ) ⊂ r(M π ) denotes the k-th TSCC of M π . Since (x, y) ∈ Q 0 , by summing constraints (ii ) in (19) over the set r k (M π ), we get where we used the fact that r k (M π ) is only reachable from states in r k (M π ) ∪r(M π ). By breaking the summation in the last term on the RHS of (41) over states s in the union of the disjoint sets r k (M π ) andr(M π ) and interchanging the order of the summations over s and s , the last term in (41)  T π (s|s ) , where the first term on the RHS of the equality (42) follows from the closure of r k (M π ) (which implies that s∈r k (Mπ) T (s|s , a) = 1 for s ∈ r k (M π )), and the second term from the definition of the policy in (14) for states in E x (noting that s ∈r(M π ) implies x s = 0). Replacing (42) in (41), we get that We proceed to further simplify the second term on the RHS of (43). Since x s = 0, ∀s ∈ r(M π ), it follows from constraint (ii ) of (19) and (14)  In matrix form, this can be rewritten as where Z π = [z s s ] ∈ [0, 1] |r(Mπ)|×|r(Mπ)| , with z s s := T π (s|s ). Hence, the second summation in (43) can be written as where L π,k is the submatrix of T π of transitions fromr(M π ) to r k (M) under policy π as in (5). From (43) and (46), Since the vector P π,k is the scaled (by the inverse of η s ) s-th column of the submatrix of the matrix T ∞ π defining transitions fromr(M π ) to r k (M π ), we have (Feller, 1968;Puterman, 1994), which proves the identity (40) of Lemma 5. We can readily state the next Lemma which establishes the aforementioned sufficiency condition.
Before we prove Lemma 6, we remark that this result also holds for policies in Π EP and Π CP since these are subsets of Π CPU per Lemma 2.
We show that the steady-state distribution induced by every CPU policy is in X 0 . To this end, let x ∈ P ∞ (Π CPU ), i.e., ∃π ∈ Π CPU : Pr ∞ π = x, where Pr ∞ π is as defined in Lemma 1. Therefore, x is a stationary distribution of the Markov chain M π , in which r k (M π ), k ∈ [m] are TSCCs and statesr(M π ) are either transient or isolated. Hence, x = x T π . Therefore, where the last equality follows since Pr ∞ π (s, a) = Pr ∞ π (s)π(a|s). Thus, the steady-state distribution x satisfies constraint (i ) in (19). From the definition of Π CPU in (17) The variables y f a , f ∈r(M π ), a ∈ A(f ), can be set as in (45), i.e., choose y f a = β r(Mπ) (I − Z π ) −1 e f π(a|f ), f ∈r(M π ), a ∈ A(f ), where Z π is the submatrix of T π defined in (5), which satisfies the constraints (ii ) as we have already shown in (44). The remaining variables y sa , s ∈ r k (M π ), a ∈ A(s), can now be chosen in terms of x sa , y f a , T (s |s, a) and β such that the corresponding constraints (ii ) are satisfied. Thus, for the given x, we have shown the existence of a feasible y such that (x, y) ∈ Q 0 . Therefore, x ∈ X 0 .

Appendix B. Proof of Main Theorems
Proof of Theorem 1 Since (x, y) is a feasible point of LP 1 , we have that (x, y) ∈ Q 0 per (20). From Lemma 3 (a),r(M) ⊆r(M π ), thus r(M) ⊇ r(M π ). Consider a state s ∈ r(M). Then, s ∈ r k (M) for some k ∈ [m]. From the positivity constraint (v ) of LP 1 , we also have that x s > 0, i.e., s ∈ E x . Since s ∈ r k (M) ∩ E x , it follows that s ∈ r(M π ) by Lemma 3 (b). Therefore, r(M) ⊆ r(M π ). We conclude that r(M π ) = r(M). From constraint (v ), x sa > 0, ∀s ∈ r(M), a ∈ A(s). It follows from the definition of π in (14) for states s ∈ E x that π(a|s) > 0, ∀s ∈ r(M), a ∈ A(s). We have shown that π satisfies both requirements in (15), hence π ∈ Π EP .

Proof of Theorem 4
The proof follows the same reasoning as that of Theorem 2.

Proof of Theorem 5
Assume (x, y) ∈ Q * . We have that V + k (x) ⊆ r k (M π ) for π in (14) by Lemma 3 (b). Further, consider s ∈ r k (M) ∩ E x . By constraint (i ) and the definition of π in (14), T π (s|s ) = 0, ∀s ∈ V + k (x). For the sake of contradiction, assume s ∈ r(M π ). Hence, s ∈ F ⊆ r k (M) for some TSCC F of M π . Summing constraints (ii ) over the set F , we get that β s = 0, ∀s ∈ F and T π (s|s ) = 0, s ∈r(M), s ∈ F . Hence, s ∈r(M π ), yielding a contradiction. We conclude that V + k (x) = r(M π ) ∩ r k (M). Therefore, if for every k ∈ [m] we have that the subgraph (V + k (x), E + k (x)) is strongly connected, then V + k (x) is a SCC in M π , for π in (14). Hence, V + k (x) is the unique TSCC r k (M π ) in the set r k (M), i.e., π ∈ Π CPU . The result now follows from Lemma 6.

Proof of Theorem 6
(1) Every feasible solution of LP 1 ( ) is also LP 1 -feasible. Hence, the result follows as an immediate consequence of Theorem 1.
(3) Let n → 0, n ∈ N, be a monotonically decreasing sequence, π * n the EP policy in (14) corresponding to an optimal solution to LP 1 ( n ), and R n := R ∞ π * n (β). The sequence (R n ) n∈N is monotonically non-decreasing since R n ≥ R m whenever n < m . Further, from (11), we have that the sequence is bounded above since sup π∈Π EP R ∞ π (β) ≤ r max , where r max := max s∈S,a∈A(s) R(s, a). Since the sequence (R n ) n∈N is both increasing and bounded, it converges to the limit sup n R n by the monotone convergence theorem (Royden & Fitzpatrick, 2010). We are only left to show that sup n R n = sup π∈Π EP R ∞ π . To this end, assume for the sake of contradiction that sup n R n < sup π∈Π EP R ∞ π . Since the RHS of the inequality is the least upper bound on the average reward of EP policies, then for any δ > 0, ∃π ∈ Π EP : R ∞ π > sup π∈Π EP R ∞ π − δ. We can choose δ small enough such that R ∞ π > sup n R n . From part (2) above, ∃ > 0, such that Pr ∞ π is LP 1 ( )-feasible for all ≤ . Hence, from the definition of π * n , we get that sup n R n ≥ R ∞ π , yielding a contradiction.

Proof of Theorem 8
The cone V (x, y) in (29) is the cone of feasible directions from a feasible point (x, y), i.e., directions v = (h, z) along which ∃λ > 0 such that (x, y) + λ(h, z) is feasible. The sets u(x), l(x), n(x) and m(y) denote the sets of active (upper and lower) specification and non-negativity (of state-action variables x and y) constraints, respectively. Since the rewards vector R is an interior point of the dual cone V * (x, y) designated in the statement of Theorem 8, moving away from (x, y) along any feasible direction can only reduce the value of the objective, i.e., s∈S a∈A(s) R(s, a)h sa < 0. Hence, (x, y) is the unique optimal solution to (22). We have already shown that the set of occupation measures induced by policies for whichr(M) ⊆r(M π ) is contained in the feasible set of (22). Since π in (14) is one such policy by Lemma 3 (a), we have Pr ∞ π = x and π meets the specifications Φ ∞ L . The uniqueness of π in this class of policies follows from the established uniqueness of the optimal solution x.