---
abstract: 'We consider the linear programming approach for constrained and unconstrained Markov decision processes (MDPs) under the long-run average cost criterion, where the class of MDPs in our study have Borel state spaces and discrete countable action spaces. Under a strict unboundedness condition on the one-stage costs and a recently introduced majorization condition on the state transition stochastic kernel, we study infinite-dimensional linear programs for the average-cost MDPs and prove the absence of duality gap and other optimality results. Our results do not require a lower-semicontinuous MDP model and as such, they can be applied to countable action space MDPs where the dynamics and one-stage costs are discontinuous in the state variable. The proofs of these results make use of the continuity property of Borel measurable functions asserted by Lusin’s theorem.'
author:
- 'Huizhen Yu[^1]'
bibliography:
- 'minpair\_lp\_bib.bib'
title: 'On Linear Programming for Constrained and Unconstrained Average-Cost Markov Decision Processes with Countable Action Spaces and Strictly Unbounded Costs'
---

[**Keywords:**]{}\
Markov decision processes; Borel state space; countable action space; average cost; constraints\
minimum pair; majorization condition; infinite-dimensional linear programs; duality

Introduction
============

We consider discrete-time Markov decision processes (MDPs) with the long-run average cost criterion. Our focus will be on the linear programming (LP) approach, for a class of unconstrained and constrained MDPs that have Borel state spaces, discrete countable action spaces, and strictly unbounded one-stage costs.

LP methods for average-cost MDPs have a long history and an extensive literature (see e.g., [@DeF68; @HoK79; @HoK84; @Kar83] for some early work on finite-space MDPs, [@Bor88; @Bor94; @HoL94; @HuK97; @Las94] on countable state space and countable or compact action space MDPs, and [@HGL03; @HL94; @HL02; @KNH00; @Yam75] on Borel space MDPs; see also the books [@Alt99; @FS02; @HL96; @HL99; @Puterman94] and their references). For the special case of strictly unbounded costs we consider, where the one-stage costs are nonnegative and grow unboundedly outside certain increasing compact sets of the state-action spaces (cf. Assumption \[cond-pc-3\](SU)), there is a line of research that connects the LP approach with the minimum pair approach for average-cost MDPs (see e.g., [@HL99 Chaps. 11-12]), which is also related to the convex analytic approach [@Bor88]. The idea of the minimum pair approach is to consider average costs of all policies for all initial distributions, with the goal of finding a stationary policy and an associated initial distribution that together attain the minimum average cost. The associated initial distribution here is not an arbitrary one but an invariant probability measure induced by that stationary policy; we shall call such a pair of policy and initial distribution a “stationary minimum pair.” When the one-stage costs are strictly unbounded, under various conditions on the MDP model (to be explained below), a stationary minimum pair can be proved to exist. Finding such a pair can be formulated as a linear program in the space of stationary policies and their induced invariant probability measures. This provides a method to solve the average-cost MDP or to gain further insights about its dynamic programming-related properties, such as optimality equations, through the duality relationships in LP. This method can be applied to general multichain MDPs, which is an advantage since the chain structure of an MDP can be complicated and hard to analyze especially when the state space is uncountably infinite.

To our knowledge, Denardo [@Den70] was the first to propose this LP method for solving finite-space multichain MDPs (although he focused more on algorithms than on the minimum pair idea as a general approach). For infinite Borel space MDPs, the minimum pair approach was introduced by Kurano [@Kur89], motivated by the ideas of occupancy measures from Borkar [@Bor83; @Bor84], and it was further developed by Hernández-Lerma [@HLe93], Lasserre [@Las99], and Vega-Amaya [@VAm99] (see also [@HL99 Chap. 11]). (Kurano considered compact state and action spaces; Borkar’s work was for countable state spaces. Hernández-Lerma, Lasserre, and Vega-Amaya considered non-compact spaces with strictly unbounded costs, and obtained further results, including strong and pathwise average-cost optimality results, besides the existence of a stationary minimum pair.) Hernández-Lerma and Lasserre [@HL94] (see also the book chapters [@HL99 Chap. 12] and [@HL02]) formulated an LP framework for Borel space average-cost MDPs by using the theory of infinite-dimensional LP (Anderson and Nash [@AnN87]). They characterized the relation between the values of the primal/dual linear programs and the minimum average cost of an MDP, and proved the absence of duality gap under tightness conditions closely related to the minimum pair method. Before [@HL94], a much earlier duality result was proved by Yamada [@Yam75] for compact Euclidean state and action spaces and bounded costs, under geometric ergodicity conditions. Additional results and generalizations of some of the results of [@HL94] were given by Hernández-Lerma and González-Hernández [@HG98]. Extensions of the LP framework to constrained MDPs were subsequently studied by Kurano et al. [@KNH00] for compact spaces and by Hernández-Lerma et al. [@HGL03] for non-compact spaces.

Our work builds upon the earlier researches on Borel space constrained and unconstrained MDPs just mentioned. The action space in those prior results is more general than the countable action space we deal with in this paper. However, except for [@Yam75], they all require a lower-semicontinuous MDP model assumption—namely, they require the one-stage cost functions to be lower semicontinuous and the state transition stochastic kernels to be (weakly) continuous ([@Yam75] involves different continuity conditions; see Remark \[rmk-Yamada\] for details). This is a restriction.

Recently, to deal with Borel space MDPs without such continuity properties, we introduced in [@Yu19-minp] a majorization condition on the state transition stochastic kernel instead, for the case of countable action spaces (with the discrete topology). We obtained the existence of a stationary minimum pair and other average-cost optimality results analogous to those for lower-semicontinuous MDPs given by [@HLe93; @Kur89; @Las99; @VAm99]. The purpose of the majorization condition was to make use of Lusin’s theorem on the continuity of Borel measurable functions [@Dud02 Thm. 7.5.2]. Roughly speaking, we require the existence of finite Borel measures on the state space that can majorize certain sub-stochastic kernels created from the state transition stochastic kernel, at all admissible state-action pairs (see Assumption \[cond-pc-3\](M)). We then use those majorizing finite measures in combination with Lusin’s theorem, so as to extract arbitrarily large sets (large as measured by a given finite measure) on which certain Borel measurable functions involved in our analysis have desired continuity properties. With this technique—although its application range is currently limited to the case of countable action spaces, we are able to avoid the lower-semicontinuous model assumption and obtain results in [@Yu19-minp] that can be applied to MDPs with discontinuous dynamics and one-stage costs.

The purpose of the present paper is to study further the implications of the majorization condition and Lusin’s theorem in the LP context, for both unconstrained and constrained MDPs. Our main contributions can be summarized as follows:

1.  For unconstrained average-cost MDPs, under the strictly unbounded cost condition and the majorization condition, we prove there is no duality gap between the primal and dual linear programs in an LP formulation (see Theorem \[thm-1\]).

2.  For constrained average-cost MDPs, under conditions similar to those in (i), we first prove the existence of stationary optimal pair and stationary lexicographically optimal pair (which are analogous to stationary minimum pairs for unconstrained MDPs), and we then prove the absence of duality gap for an LP formulation (see Theorem \[thm-4.1\] and Theorem \[thm-4.2\], respectively).

In addition, we also discuss the maximizing sequences of dual linear programs and their relation with certain versions of average cost optimality equations (ACOE) (see Prop. \[prp-2\] for unconstrained MDPs and Props. \[prp-4.3\], \[prp-4.4\] for constrained MDPs). Our results for unconstrained (resp., constrained) MDPs given in this paper can be compared with some of the prior results in [@HL99 Chap. 12] and [@HL02] (resp., [@HGL03] and [@KNH00]) for lower-semicontinuous models.

While this paper focuses on the average cost criterion, the analysis we give, with minor changes, can also be applied to discounted-cost, constrained or multi-objective MDPs similar to those studied in [@FeS96; @HG00; @HR04], for finding constrained optimal or Pareto optimal policies (for a given initial distribution) using the LP approach, in the case of countable action spaces. We also mention that based on similar ideas, we introduced another majorization condition for MDPs where both the state and action spaces are Borel, in a separate recent work [@Yu20]; there we used the majorization condition instead of the commonly required continuity/compactness conditions to prove the average cost optimality inequalities via the vanishing discount factor approach.

The rest of this paper is organized as follows. Section \[sec-2\] gives background materials about the average-cost MDP model, some prior optimality results for the minimum pair approach, and an overview of linear programs in topological vector spaces. Section \[sec-3\] presents our LP formulation and duality results for unconstrained MDPs, and Section \[sec-4\] extends the results to constrained MDPs. Proofs for the theorems in Sections \[sec-3\] and \[sec-4\] are given in Section \[sec-5\].

Preliminaries {#sec-2}
=============

We start with some notations and basic definitions. For a topological space $X$, $\B(X)$ denotes the Borel $\sigma$-algebra on $X$, and $\P(X)$ denotes the set of probability measures on $\B(X)$. Nonnegative or signed measures on $\B(X)$ will be called Borel measures. A *Borel space* (a.k.a. *standard Borel space*) is a separable metrizable space that is homeomorphic to a Borel subset of some Polish space (i.e., a separable and completely metrizable space) [@bs Chap. 7]. Let $X$ and $Y$ be Borel spaces. A *Borel measurable stochastic kernel on $Y$ given $X$* is a Borel measurable function from $X$ into $\P(Y)$, where the space $\P(Y)$ is endowed with the topology of weak convergence. We denote the stochastic kernel by $q(dy \,|\, x)$. When it is continuous on $X$, we call it a *continuous stochastic kernel* (it is also called *weakly continuous* or *weak Feller* in the literature). For the space $\P(X)$ or more generally, the space of finite Borel measures on $X$, besides the topology of weak convergence just mentioned, we shall also consider other topologies in the next section when these spaces appear in infinite-dimensional linear programs.

We now introduce average-cost MDPs and the minimum pair approach, after which we will briefly review infinite-dimensional linear programs in topological vector spaces.

MDP Model, Average Cost Criterion, and Minimum Pair Approach {#sec-2.1}
------------------------------------------------------------

We consider an MDP with state space $\X$ and action space $\A$, where $\X$ is a Borel space and $\A$ is a countable space endowed with the discrete topology. The control constraint is specified by a set-valued map $A: \X \to 2^{\A}$. In particular, each state $x \in \X$ is associated with a nonempty set $A(x) \subset \A$ of admissible actions, and the graph of the map $A(\cdot)$, $$\Gamma := \{(x, a) \mid x \in \X, a \in A(x)\},$$ is assumed to be a *Borel subset* of $\X \times \A$. If an action $a \in A(x)$ is taken at state $x$, a one-stage cost $c(x,a)$ is incurred, followed by a probabilistic state transition. We assume that the state transition is governed by a *Borel measurable* stochastic kernel $q(dy \,|\, x, a)$ on $\X$ given $\X \times \A$, and that the one-stage cost function $c: \X \times \A \to [0, +\infty]$ is *nonnegative and Borel measurable*, real-valued on $\Gamma$, and taking the value $+\infty$ outside $\Gamma$.

A policy is a sequence of stochastic kernels on $\A$ that specify how to take actions at each stage, given the history up to that stage. More precisely, for infinite-horizon average cost problems that we consider, a *Borel measurable policy* is an infinite sequence $\pi : =(\mu_0, \mu_1, \ldots)$ where for each $n \geq 0$, $\mu_n\big(da_n \!\mid x_0, a_0, \ldots, a_{n-1}, x_n \big)$ is a Borel measurable stochastic kernel on $\A$ given $(\X \times \A)^{n} \times \X$ and obeys the control constraint of the MDP: $$\mu_n\big(A(x_n) \!\mid x_0, a_0, \ldots, a_{n-1}, x_n \big) = 1, \quad \forall \, (x_0, a_0, \ldots, a_{n-1}, x_n) \in (\X \times \A)^n \times \X.$$ Such a policy is called *nonrandomized* if in the above every measure on $\A$ is a Dirac measure, and it is called *stationary* if the function $(x_0, a_0, \ldots, a_{n-1}, x_n) \mapsto  \mu_n(d a_n \!\mid\! x_0,  a_0, \ldots, a_{n-1}, x_n)$ depends only on the state $x_n$, in the same way for every $n \geq 0$. In the stationary case, we can write the policy as $\pi = (\mu, \mu, \ldots)$ for a Borel measurable stochastic kernel $\mu(da \,|\, x)$ on $\A$ given $\X$ that obeys the control constraint of the MDP, and we will simply designate this policy by $\mu$.

Let $\Pi$ denote the space of Borel measurable policies, and let $\Pi_s$ be the subset of all stationary policies in $\Pi$. Given that the action space $\A$ is countable, $\Pi$ and $\Pi_s$ are nonempty (see e.g., [@Yu19-minp Sect. 2]), and the Borel measurable policies will be adequate for our purpose—henceforth, we shall simply call them policies. We also note that although $\A$ is countable, in the above and throughout the paper, we write probability measures on $\A$ using the general notation for probability measures on a possibly uncountably infinite space, for notational simplicity.

### Average Cost Criterion and Minimum Pair

In an MDP, a policy $\pi \in \Pi$ and an initial (state) distribution $\zeta \in \P(\X)$ induce a stochastic process $\{(x_n, a_n)\}_{n \geq 0}$ on the infinite product of state and action spaces, $(\X \times \A)^\infty$. The probability measure for this process is uniquely determined by the initial distribution $\zeta$, the sequence of stochastic kernels in $\pi$, and the state transition stochastic kernel $q(dy \,|\, x, a)$ [@bs Prop. 7.28]. We denote this probability measure by $\Pr^\pi_\zeta$ and the corresponding expectation operator by $\E^\pi_\zeta$. The long-run expected average cost of the policy $\pi$ for the initial distribution $\zeta$ is defined by $$J(\pi,\zeta) : = \limsup_{n \to \infty} \, n^{-1} \E^\pi_\zeta \big[ \, \textstyle{\sum_{k=0}^{n-1} c(x_k, a_k)} \, \big].$$ We shall also refer to $J(\pi, \zeta)$ as the average cost of the pair $(\pi, \zeta)$. With the minimum pair approach, we consider the average costs of all policy and initial distribution pairs, and among these pairs, we are especially interested in the types of pairs defined below.

Let $\rho^*$ be the *minimum average cost* over all policies and initial distributions: $$\rho^* : = \inf_{\zeta \in \P(\X)} \inf_{\pi \in \Pi} J(\pi, \zeta).$$

\[def-minp\] A pair $(\pi^*, \zeta^*) \in \Pi \times \P(\X)$ with $J(\pi^*, \zeta^*) = \rho^*$ is called a *minimum pair*.

\[def-sp\]

1.  For a stationary policy $\mu \in \Pi_s$ and an initial distribution $p \in \P(\X)$, if $p$ is an invariant probability measure of the Markov chain induced by $\mu$ on $\X$, we call $(\mu, p)$ a *stationary pair*. The set of all stationary pairs is denoted by $\Delta_{s}$.

2.  If $(\mu^*, p^*) \in \Delta_s$ is a minimum pair, we call it a *stationary minimum pair*.

Various terminologies are used in the literature for what we call a stationary pair $(\mu,p)$. In the references [@HGL03; @HL94; @HL99], the policy $\mu$ is called a “stable policy” if $J(\mu, p) < \infty$. In the reference [@Bor94], the probability measure $\gamma(d(x,a)) = \mu(da \,|\, x) \, p(dx)$ is called an “ergodic occupation measure”—we will discuss such measures in Section \[sec-3.1\].

### Model Assumptions and Existence of Stationary Minimum Pair

We now impose additional conditions on the MDP model. For a set $B$ in some space, let $B^c$ denote its complement; for a set $B \subset \X \times \A$, let $\proj_\X(B)$ denote the projection of $B$ on $\X$. Recall that $\Gamma = \{(x, a) \mid x \in \X, a \in A(x)\}$.

\[cond-pc-3\]

1.  For some $\pi \in \Pi$ and $\zeta \in \P(\X)$, the average cost $J(\pi,\zeta) < \infty$.

2.  There exists a nondecreasing sequence of compact sets $\Gamma_j \uparrow \Gamma$ such that $$\lim_{j \to \infty} \inf_{(x, a) \in \Gamma_j^c} c(x, a) = + \infty.$$

3.  For each compact set $K \in \{\proj_\X(\Gamma_j)\}$, there exist an open set $O \supset K$, a closed set $D \subset \X$, and a finite measure $\nu$ on $\B(\X)$ (all of which can depend on $K$) such that $$q\big((O \setminus D) \cap B  \mid x, a \big) \leq \nu(B), \qquad \forall \, B \in \B(\X), \ (x, a) \in \Gamma, \label{eq-maj-minpair}$$ where the closed set $D$ (possibly empty) is such that restricted to $D \times \A$, the state transition stochastic kernel $q(dy\,|\, x, a)$ is continuous and the one-stage cost function $c$ is lower semicontinuous.

The first two conditions in this assumption are standard: (G) excludes vacuous problems, and (SU) defines the case of strictly unbounded one-stage costs. They were used in [@HLe93; @HL99; @Las99; @VAm99] to derive average-cost optimality and LP duality results for lower-semicontinuous MDP models with strictly unbounded costs.

Condition (M) was introduced in our recent work [@Yu19-minp]. We use the majorization property required in (M) instead of the lower-semicontinuity model conditions commonly required in the literature. The set $D$ in (M) is introduced to separate a “continuous part” of the model from the rest, in order to sharpen (M), although this condition can also be used with $D = \emptyset$. Condition (M) seems natural for problems where the probability measures $\{ q(\cdot \,|\, x,a) \mid (x,a) \in \Gamma \}$ have densities on $\X \setminus D$ with respect to (w.r.t.) a common $\sigma$-finite reference measure and those density functions are bounded uniformly from above. For instance, if $\X = \R^n$ and the reference measure is the Lebesgue measure, we can take $\nu$ in (M) to be a multiple of the Legesgue measure restricted to a bounded open set that contains $K$. See [@Yu19-minp Example 3.2 and Remark 3.3] for more specific examples that illustrate situations where (M) is naturally satisfied or cannot be satisfied.

Under the preceding assumption, the following results are proved in [@Yu19-minp] by making use of Lusin’s theorem (see [@Yu19-minp Thm. 3.5] for sample-path and other optimality properties of a stationary minimum pair). They are analogous to the prior results for lower-semicontinuous MDPs [@HLe93; @HL99; @Kur89; @VAm99], and they will serve as the starting point for the analyses we present in this paper.

\[thm-2.1\] Under Assumption \[cond-pc-3\], the following hold:

-   For any pair $(\pi, \zeta) \in \Pi \times \P(\X)$ with $J(\pi, \zeta) < \infty$, there exists a stationary pair $(\bar \mu, \bar p) \in \Delta_{s}$ with $J(\bar \mu, \bar p) \leq J(\pi, \zeta)$.

-   There exists a stationary minimum pair $(\mu^*, p^*) \in \Delta_{s}$.

Linear Programs in Topological Vector Spaces {#sec-2.2}
--------------------------------------------

We now give a brief overview of topological vector spaces and infinite-dimensional linear programs in such spaces. The reader is referred to the books [@AnN87; @RoR73] for in-depth studies of these subjects, and to the book [@HL99 Chap. 12.2] for a more detailed introduction than ours. Here we shall focus on a few basic concepts and results that will be needed in this paper.

We consider topological vector spaces over the real field. A *topological vector space* is a vector space with a topology that is compatible with its algebraic structure (namely, with that topology, the addition and multiplication operations are continuous; see [@RoR73 Chap. I.3]). Let $X$ and $Y$ be two (real) vector spaces, and let $\m0$ denote the element zero for both spaces. The pair $(X, Y)$ is called a *dual pair* if there is a bilinear form $\langle \cdot, \, \cdot\rangle: X \times Y \to \R$ such that

-   for each $x \not=\m0$ in $X$, there exists some $y \in Y$ with $\langle x, \, y \rangle \not = 0$,

-   for each $y \not=\m0$ in $Y$, there exists some $x \in X$ with $\langle x, \, y \rangle \not = 0$.

For a dual pair $(X, Y)$, the coarsest topology on $X$ under which the function $|\langle \cdot, \, y\rangle|$ is continuous for every $y \in Y$ is called the *weak topology* on $X$ determined by $Y$, and denoted by $\sigma(X, Y)$. By symmetry, $(Y, X)$ is also a dual pair and $\sigma(Y, X)$, the weak topology on $Y$ determined by $X$, is likewise defined. With the respective weak topology, the space $X$ or $Y$ is a topological vector space that is separated (i.e., a Hausdorff space) and locally convex (i.e., every point in the space has a base of convex neighborhoods) [@RoR73 Chap. II.3]. Convergence in $X$ under the weak topology $\sigma(X, Y)$ can be characterized as follows: a net $\{x_i\}_{i \in \nI}$ in $X$ converges to $\bar x \in X$ if and only if $$\langle x_i, \, y \rangle \to \langle \bar x, \, y \rangle, \qquad \forall \, y \in Y.$$

We consider equality-constrained linear programs and their dual linear programs in topological vector spaces. The definitions of these programs involve several objects, which we introduce first:

-   two dual pairs of vector spaces $(X, Y)$ and $(Z, W)$, with each space endowed with its respective weak topology;

-   a linear mapping $\L : X \to Z$ that is required to be *weakly continuous* (i.e., $\L$ is continuous under the topology $\sigma(X, Y)$ for $X$ and the topology $\sigma(Z, W)$ for $Z$);

-   a convex cone $\Lambda$ in $X$ and its *dual cone* $\Lambda^*$ in $Y$ defined as $$\Lambda^* : = \big\{ y \in Y \mid \langle x, \, y \rangle \geq 0, \ \forall \, x \in \Lambda \big\}.$$

The convex cones $\Lambda$ and $\Lambda^*$ induce a partial ordering “$\leq$" on $X$ and $Y$, respectively: $$x_1 \leq x_2 \ \ \text{iff} \ \ x_2 - x_1  \in \Lambda; \qquad   y_1 \leq y_2 \ \ \text{iff} \ \ y_2 - y_1  \in \Lambda^*.$$

The linear mapping $L$ appears in the constraints of a linear program designated as the primal program (P). Associated with $\L$ is another linear mapping $\L^*$ on the space $W$, called the *adjoint* (or *transpose*) of $\L$, that maps each $w \in W$ to a linear form on $X$ and is defined by the identity relation (where $\langle x, \L^* w \rangle$ stands for $(\L^*w)(x)$): $$\langle x, \L^* w \rangle : = \langle \L x, w \rangle, \quad \forall \, x \in X, \ w \in W.$$ An important property of $\L$ and $\L^*$ is given by the following proposition:

\[prp-wcontinuity\] A linear mapping $\L: X \to Z$ is weakly continuous if and only if $\L^*(W) \subset Y$. If $\L$ is weakly continuous, so is $\L^*$.

This proposition gives a convenient way to verify whether a linear mapping is weakly continuous or not. When $\L$ is weakly continuous, with the weakly continuous mapping $\L^*: W \to Y$, one can define the dual of the primal linear program.

Let $c \in Y$ and $b \in Z$. Consider an equality-constrained primal linear program (P) and its dual linear program () defined as follows (cf. [@AnN87 Chap. 3.3]): $$\begin{aligned}
   \text{(P)} \quad \qquad \text{minimize}  \ \ \ &  \langle \, x,  c \, \rangle \notag \\
                 \text{subject to} \ \ \ & \L x = b, \quad  x \in \Lambda.  \qquad \qquad \label{eq-P0} \\
   \text{(\Pstar)} \quad \ \quad \text{maximize}  \ \ \ &  \langle \, b, w  \,\rangle \notag \\
                 \text{subject to} \ \ \ & - \L^*w + c \in \Lambda^*, \quad w \in W. \label{eq-dP0}\end{aligned}$$ Similarities between these programs and standard finite-dimensional linear programs can be seen by writing the constraints $x \in \Lambda$ and $- \L^*w + c \in \Lambda^*$ equivalently as $x \geq \m0$ and $\L^* w \leq c$, respectively.

If the program (P) or () has a feasible solution, it is said to be *consistent*; if it admits an optimal solution, it is said to be *solvable*. Let $\inf(\text{P})$ and $\sup  (\Pstar)$ denote the values of (P) and (), respectively. The elementary duality theory (cf. [@AnN87 Chap. 3.3]) asserts that if (P) and () are both consistent, then $$\sup (\Pstar) \leq \inf (\text{P}).$$ If the equality $\sup (\Pstar) = \inf (\text{P})$ holds, we say there is *no duality gap*.

There are several sufficient conditions for the absence of duality gap. For our purpose, one duality theorem—Theorem \[thm-subc\] below from [@AnN87]—will be the most important. It characterizes the relation between the value of () and the subvalue of (P), which is defined as follows.

Consider the set $H \subset Z \times \R$ defined by $$\label{eq-H}
  H : = \big\{ \big(\L x, \, \langle \, x, c \, \rangle + r \big) \, \big| \, x \in \Lambda, \ r \geq 0 \big\}.$$ Let ${\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ denote the closure of $H$ in the weak topology $\sigma(Z \times \R, \, W \times \R)$ (corresponding to the dual pair $(Z \times \R, \, W \times \R)$). We call (P) *subconsistent* if there exists some $r \in \R$ with $(b, r) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$. When (P) is subconsistent, the *subvalue* of (P) is defined by $$\text{subvalue} (\text{P}) : = \inf \big\{ r \, \big| \, \big( b, r \big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu} \, \big\}.$$ For comparison, note that $\inf (\text{P}) = \inf \big\{ r \, \big| \, \big( b, r \big) \in H  \big\}$. Note also that if $\urho$ is the subvalue of (P), then by the definition of the closure ${\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$, $\big(b,  \urho \big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ and there exists some net $\{x_i\}_{i \in \nI}$ with $x_i \in \Lambda$ for all $i$, such that $L x_i \to b$ and $\langle x_i, \, c \rangle \to \urho$, where $x_i$ need not be feasible for (P).

\[thm-subc\] (P) is subconsistent with a finite subvalue $\urho$ if and only if () is consistent with a finite value $\urho$.

We will apply this theorem in analyzing the duality relationship between the primal and dual linear programs for average-cost MDPs.

Linear Programming for Average-Cost MDPs {#sec-3}
========================================

In this section we study the LP approach for the average-cost MDP under Assumption \[cond-pc-3\]. Roughly speaking, the primal linear program (P) is formulated to find a stationary minimum pair among the stationary pairs of the average cost MDP—this is viable since under Assumption \[cond-pc-3\], the set of stationary pairs is nonempty and a stationary minimum pair exists (cf. Theorem \[thm-2.1\]). The dual linear program () is then determined by the primal program and the two dual pairs of vector spaces involved in the formulation (cf. Section \[sec-2.2\]). We present the LP formulation and our main duality results in Sections \[sec-3.1\] and \[sec-3.2\], respectively. (The proofs of the theorems are given in Section \[sec-5\].)

Our formulation of the primal linear program is the same as that given by the prior work [@HL99 Chap. 12.3]. Our dual program formulation is different, however, and it avoids a condition on the state transition stochastic kernel used in [@HL99 Chap. 12.3], without affecting the desired duality result (cf. Remark \[rem-LP\]). This LP formulation we present is one instance of a general class of formulations discussed in the prior work [@HL94 Sect. 4]; however, for the sake of completeness, we will give a detailed account of it using the terminologies introduced in Section \[sec-2.2\].

Regarding notations, in what follows, $\R_+$ denotes the set of nonnegative numbers. For $X = \X$ or $\Gamma$, $\Me(X)$ denotes the space of finite signed Borel measures on $X$, and $\Fn(X)$ the set of real-valued Borel measurable functions on $X$. We write $\Me^+(X)$ or $\Fn^+(X)$ for the subset of those nonnegative elements in $\Me(X)$ or $\Fn(X)$, and we will use similar notations for the subspaces of $\Me(X)$ or $\Fn(X)$.

For the one-stage cost function $c(\cdot)$, we will also need to work with its restriction to the set $\Gamma$ of state and admissible action pairs (on which $c(\cdot)$ is finite as we recall). For notational simplicity, we shall use the same notation $c$ or $c(\cdot)$ for the restriction of $c(\cdot)$ to $\Gamma$, and the context will make it clear which function is involved in the discussion. Likewise, for a Borel measure $\gamma$ on $\Gamma$, sometimes we will also need to work with its extension to the whole state-action space $\X \times \A$, which is simply a Borel measure concentrated on $\Gamma$, and conversely, if $\gamma$ is a Borel measure on $\X \times \A$ concentrated on $\Gamma$, sometimes we will need to consider its restriction to $\Gamma$. In such cases, for notational simplicity, we will use the same notation $\gamma$ for both measures.

Primal and Dual Linear Programs {#sec-3.1}
-------------------------------

For a Borel measure $\gamma$ on $\Gamma$, let $\hat \gamma$ denote the marginal of $\gamma$ on $\X$. To define minimization problems on stationary pairs in an MDP, let us first explain a well-known (many-to-one) correspondence between a stationary pair $(\mu, p) \in \Delta_s$ and a Borel probability measure $\gamma$ on $\Gamma$ that satisfies $$\label{eq-inv-gamma}
   \hat \gamma (B) = \int_{\Gamma}  q(B \mid x,a)  \,  \gamma(d(x,a)), \qquad \forall \, B \in \B(\X).$$ The correspondence is essentially given by $$\label{eq-gamma-mup}
\gamma(d(x,a)) = \mu(da \mid x) \, p(dx),$$ and has the property that $$\label{eq-J-gamma}
  J(\mu, p) = \int c \, d\gamma.$$ Indeed, for $(\mu, p) \in \Delta_s$, as $p$ is an invariant probability measure on $\X$ induced by $\mu$, we have $$\label{eq-inv-p}
  p(B) =  \int_{\X} \int_{\A}  q(B \mid x,a)  \, \mu(da \,|\, x) \, p(dx), \qquad \forall \, B \in \B(\X).$$ This is the same as (\[eq-inv-gamma\]) for the probability measure $\gamma$ given by (\[eq-gamma-mup\]), since the marginal of $\gamma$ is $\hat \gamma = p$ and $\mu$ obeys the control constraint of the MDP. The equality (\[eq-J-gamma\]) follows from the definition of the average cost and the stationarity of the Markov chain under $\mu$ when the initial distribution is $p$. Conversely, given a probability measure $\gamma$ satisfying (\[eq-inv-gamma\]), by [@bs Cor. 7.27.2], we can decompose $\gamma$ as in (\[eq-gamma-mup\]) with $p = \hat \gamma$ and $\mu(da \,|\, x)$ being a Borel measurable stochastic kernel on $\A$ given $\X$ that obeys the control constraint of the MDP. Then, since $\gamma$ satisfies (\[eq-inv-gamma\]), the pair $(\mu, p)$ with $p=\hat \gamma$ satisfies (\[eq-inv-p\]), which means that $p$ is invariant for the Markov chain induced by $\mu$ and hence $(\mu, p)$ is a stationary pair. The policy $\mu$ here is in general not unique; however, by stationarity, every $(\mu, p)$ from this decomposition of $\gamma$ has the same average cost (\[eq-J-gamma\]).

Due to this correspondence between $(\mu,p)$ and $\gamma$, finding a stationary minimum pair can be expressed as an optimization problem in which one minimizes $\int c \, d\gamma$ over the set of probability measures $\gamma$ that satisfy (\[eq-inv-gamma\]) (a.k.a. the set of “ergodic occupation measures” [@Bor94]).

Before expressing this optimization problem as a linear program, we also need to restrict attention to those stationary pairs that have finite average costs, so that $\infty$ does not appear in the objective function and the constraints. The following definitions are introduced for this purpose. Consider a positive weight function $w: \Gamma \to \R_+$, $$w(x,a) : = 1 + c(x,a), \qquad (x,a) \in \Gamma.$$ Let $\Me_w(\Gamma)$ be the set of finite, signed Borel measures on $\Gamma$ w.r.t. which the function $w$ is integrable: $$\Me_w(\Gamma): = \textstyle{ \big\{ \gamma \in \Me(\Gamma)  \,\big|\,  \int w \, d |\gamma| < \infty \big\}}.$$ Let $\Fn_w(\Gamma)$ be the set of Borel measurable functions $\phi$ on $\Gamma$ such that $$| \phi | \leq \ell\, w \quad \text{for some} \  \ell > 0.$$ Then every $\phi \in \Fn_w(\Gamma)$ is integrable w.r.t. all $\gamma \in \Me_w(\Gamma)$. By (\[eq-J-gamma\]) and the definition of $w(\cdot)$, if a stationary pair $(\mu, p)$ has finite average cost, then the corresponding probability measure $\gamma \in \Me_w(\Gamma)$.

We are now ready to define the primal and dual linear programs for the average-cost MDP. Let us specialize the programs (P) and () defined in Section \[sec-2.2\], by identifying the objects involved in those programs as follows:

-   The dual pair $(X, Y) = \big(\Me_w(\Gamma), \Fn_w(\Gamma)\big)$, with the bilinear form $$\langle \gamma \,,\, \phi \rangle : = \int_\Gamma \phi \, d \gamma, \qquad \gamma \in \Me_w(\Gamma), \ \phi \in \Fn_w(\Gamma).$$

-   The dual pair $(Z, W) = \big(\R \times \Me(\X), \, \R \times \Fn_b(\X) \big)$, where $\Me(\X)$ is the set of finite signed Borel measures on $\X$ as defined earlier, $\Fn_b(\X)$ is the set of bounded Borel measurable functions on $\X$, and the bilinear form on $\big( \R \times \Me(\X) \big) \times \big( \R \times \Fn_b(\X) \big)$ is defined as $$\big\langle (r, \zeta) \,,\, (\rho, h) \big\rangle : = r \rho + \int_\X h \, d \zeta, \qquad (r, \zeta) \in \R \times \Me(\X), \  (\rho, h) \in \R \times \Fn_b(\X).$$

-   The convex cone $\Lambda = \Me_w^+(\Gamma)$, the subset of nonnegative measures in $\Me_w(\Gamma)$. The dual cone of $\Lambda$ is $\Lambda^* = \Fn^+_w(\Gamma)$, the subset of nonnegative functions in $\Fn_w(\Gamma)$.

-   The objective function of the primal program (P) is $\langle \, \gamma, c \, \rangle$, and the feasible set of (P) is defined by the following constraints: $$\label{eq-P-feas}
      \gamma \in \Me_w^+(\Gamma), \qquad \gamma(\Gamma) = 1, \qquad \hat \gamma (B) = \int_{\Gamma}  q(B \mid x,a)  \,  \gamma(d(x,a)), \quad \forall \, B \in \B(\X),$$ where $\hat \gamma$ is the marginal of $\gamma$ on $\X$, as we recall. In other words, in accordance with the earlier discussion, the feasible solutions of (P) correspond to those stationary pairs with finite average costs, and the objective is to minimize the average cost over them. In the form of (P) discussed in Section \[sec-2.2\], the two equality constraints in (\[eq-P-feas\]) can be written as $$\L \gamma  = b : = (1, \m0).$$ Here $\m0$ is the trivial measure on $\X$ (i.e., $\m0(B) \equiv 0$ for all $B \in \B(\X)$), and the linear mapping $\L$ is defined as $\L:  \Me_w(\Gamma) \to \R \times \Me(\X)$ with $\L = (\L_0, \L_1)$ where, for $\gamma \in \Me_w(\Gamma)$, $$\begin{aligned}
      \L_0 \gamma  & : = \gamma(\Gamma),  \\
      (\L_1 \gamma)(B) & : = \hat \gamma (B) - \int_{\Gamma}  q(B \mid x,a)  \,  \gamma(d(x,a)), \qquad \forall \, B \in \B(\X).\end{aligned}$$

-   From the identity $\big\langle \gamma, L^*(\rho, h) \big\rangle = \big\langle L \gamma, (\rho, h) \big\rangle$, the adjoint $\L^*$ of $L$ is given by the linear mapping that maps each $(\rho, h) \in \R \times \Fn_b(\X)$ to the function $$\L^*(\rho, h)(x,a) : = \rho + h(x) - \int_\X h(y)  \, q(dy \mid x, a), \qquad (x, a) \in \Gamma.$$ Since $\L^*\big(\R \times \Fn_b(\X)\big) \subset \Fn_w(\Gamma)$, both $L$ and $L^*$ are weakly continuous ([@RoR73 Chap. II, Prop. 12 and its corollary]; see also Prop. \[prp-wcontinuity\]). The inequality constraint in the program () is $$- \L^*(\rho, h) + c \in \Fn^+_w(\Gamma).$$ We can write this constraint as $\L^*(\rho, h) \leq c$ or more explicitly, as $$\rho + h(x) - \int_\X h(y)  \, q(dy \mid x, a) \leq c(x,a), \qquad \forall \, (x, a) \in \Gamma.$$ The objective function of the dual program () is $\big\langle b, \, (\rho, h) \big\rangle = \big\langle (1, \m0) , \, (\rho, h) \big\rangle  = \rho$.

Expressed in the form introduced in Section \[sec-2.2\], the primal and dual linear programs for the average-cost MDP are: $$\begin{aligned}
   \text{(P)} \quad \qquad \text{minimize}  \ \ \ &  \langle \, \gamma, c \, \rangle \notag \\
                 \text{subject to} \ \ \ & \L\gamma = (1, \m0), \quad  \gamma \in \Me^+_w(\Gamma),   \qquad \ \ \label{eq-P}\end{aligned}$$ and $$\begin{aligned}
   \text{(\Pstar)} \quad \qquad \text{maximize}  \ \ \ &  \rho \notag \\
                 \text{subject to} \ \ \ & \L^*(\rho, h) \leq c, \quad \rho \in  \R, \ h \in \Fn_b(\X). \label{eq-dP}\end{aligned}$$ As mentioned earlier, our formulation of () is different from the one given in the book [@HL99 Chap. 12.3]. We will explain the difference and the reason for it in detail in the next subsection (see Remark \[rem-LP\]).

A few properties of (P) and () are easy to see. From the relation between stationary pairs and feasible solutions of the primal program (P), it is clear that under Assumption \[cond-pc-3\], the existence of a stationary minimum pair (cf. Theorem \[thm-2.1\](ii)) ensures that (P) is both consistent and solvable. Moreover, the proof of Theorem \[thm-2.1\](ii) (cf. [@Yu19-minp]) shows that due to the strict unbounedness of the one-stage costs, if $\{\gamma_n\}$ is a sequence of feasible solutions of (P) with $\langle \gamma_n, c \rangle \downarrow \inf(\text{P}) = \rho^*$ (such a sequence is called a *minimizing sequence* of (P)), then any subsequence of $\{\gamma_n\}$ contains a further subsequence that converges to an optimal solution of (P) in the topology of weak convergence (of probability measures). The consistency of the dual program () is trivial: since $c \geq 0$, a feasible solution is given by $\rho = 0$ and $h(\cdot) \equiv 0$. We then have $0 \leq \sup (\Pstar) \leq \inf (\text{P}) = \rho^*$ under Assumption \[cond-pc-3\].

Next, we will address the duality between (P) and (). We will also examine a connection between () and the ACOE (average cost optimality equation) for the MDP, through a *maximizing sequence* of (). Such a sequence is defined as a sequence $\{(\rho_n, h_n)\}$ of feasible solutions of () with the property that $\rho_n \uparrow \sup (\Pstar)$.

Optimality Results and Discussion {#sec-3.2}
---------------------------------

Our main result of this section is the absence of duality gap stated in part (ii) of the following theorem. It can be compared with the prior result of [@HL99 Chap. 12.3, Thm. 12.3.4] for average-cost lower-semicontinuous MDPs. In our case, without lower-semicontinuity model assumptions, we will use Lusin’s theorem together with the majorization property in Assumption \[cond-pc-3\](M) to prove it.

\[thm-1\] Under Assumption \[cond-pc-3\], the linear programs (P) and () in (\[eq-P\])-(\[eq-dP\]) satisfy the following:

-   \(P) is consistent and solvable, and () is consistent.

-   There is no duality gap: $\inf (\text{P})  = \sup (\Pstar) = \rho^*$.

\[rem-thm1-proof\] Besides the differences in assumptions as mentioned above, another difference between our proof of the absence of duality gap and the proof given in the prior work [@HL99 Chap. 12.3C] is the following. The approach of the latter proof is to show that the set $H$ defined by (\[eq-H\]) is weakly closed (i.e., $H = {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$). This is a sufficient condition for the absence of duality gap, but it requires one to show that every point of ${\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ is in $H$. Our proof uses the duality between the subvalue $\urho$ of (P) and the value of () asserted in [@AnN87 Thm. 3.3] (cf. Theorem \[thm-subc\]). With this it suffices to show that a single point of ${\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$, namely, the point $\big(b, \urho\big) = \big((1,\m0), \urho\big)$, is in $H$. Thus our proof is simpler in this respect.

We can also prove that $H$ is weakly closed under our assumptions. This requires some minor changes in the proof arguments used in [@Yu19-minp], which we will also use to prove Theorem \[thm-1\] (in particular, we only need to change slightly the finite measures used when applying Lusin’s theorem). Nonetheless, it will take some space to explain the details of those changes, and this is another reason that we choose to use the duality theorem [@AnN87 Thm. 3.3] instead in our proof.

\[rmk-Yamada\] Yamada proved an absence of duality gap result [@Yam75 Thm. 3] for compact Euclidean state and action spaces, under certain continuity and ergodicity conditions on the MDP. His continuity conditions are different from the lower-semicontinuous model assumption we mentioned, but they can be related to our model assumptions. So let us explain in more detail how our assumptions and duality result compare with his. Among others, Yamada assumed that $c(x,a)$ is continuous in $a$ for each fixed $x$, and $q(dy \,|\, x,a)$ has a density $p(y \,|\, x,a)$ w.r.t. the Lebesgue measure, where $p(y \,|\, x,a)$ is continuous in $(y,a)$ for each fixed $x$ [@Yam75 (A2) and (A3)]. In our case, since the action space has the discrete topology, trivially, $c(x,a)$ and $q(dy\,|\, x,a)$ are continuous in $a$ for each fixed $x$, so there are similarities to Yamada’s conditions. Our majorization condition (M) is, however, entirely different from Yamada’s geometric ergodicity condition [@Yam75 (A1) and (A4)], in which he required the density function $p(y \,|\, x,a)$ to be bounded away from zero uniformly for all $(x,a) \in \Gamma$. Using this condition together with the continuity and other assumptions, he proved the absence of duality gap result [@Yam75 Theorem 3]. Both his conditions and his proof arguments are very different from ours.

\[rem-LP\] In defining (), we have chosen the space $\Fn_b(\X)$ of *bounded* Borel measurable functions to form the dual pair with the space $\Me(\X)$ of *finite* Borel measures. With this choice, () is in general not solvable (i.e., an optimal solution may not exist), since the inequality $$\rho^* + h(x) \leq c(x,a) + \int_\X h(y) \, q(dy \mid x,a), \qquad \forall \, (x,a) \in \Gamma,$$ need not admit a bounded solution $h$.

As mentioned earlier, our LP formulation is only an instance of the class of formulations discussed in [@HL94 Sect. 4]. A different dual program () is studied in [@HL99 Chap. 12.3]. It involves, instead of $\big(\R \times \Me(\X), \R \times \Fn_{b}(\X)\big)$, the dual pair $\big(\R \times \Me_{w_0}(\X), \R \times \Fn_{w_0}(\X)\big)$, where the two spaces $\Me_{w_0}(\X)$ and $\Fn_{w_0}(\X)$ are defined similarly to $\Me_w(\Gamma)$ and $\Fn_w(\Gamma)$, respectively: with $w_0(x) : = 1 + \inf_{a \in A(x)} c(x,a)$, $x \in \X$, $$\Me_{w_0}(\X) : =  \textstyle{ \big\{ p \in \Me(\X)  \,\big|\,  \int w_0 \, d |p| < \infty \big\}}, \quad \Fn_{w_0}(\X)\ : = \big\{ h \in \Fn(\X) \, \big| \, | h | < \ell \, w_0  \  \text{for some} \  \ell > 0\}.$$ This choice leaves more room for () to admit an optimal solution. However, a disadvantage is that to ensure the weak continuity of the linear mapping $L$, an additional condition on the state transition stochastic kernel is required (cf. [@HL99 Chap. 12.3A, Assumption 12.3.1]): for some constant $k > 0$, $$\label{eq-excond-q}
   \int_\X \inf_{a' \in A(y)}\!c(y,a') \, q(dy \mid x,a) \, \leq \, k \big(1 + c(x,a) \big), \qquad \forall \, (x,a) \in \Gamma.$$ Yet, since the costs are strictly unbounded, this condition (\[eq-excond-q\]) is neither needed for the existence of a minimum pair, nor needed for the absence of duality gap between (P) and ().

Also, the use of the dual pair $\big(\R \times \Me_{w_0}(\X), \R \times \Fn_{w_0}(\X)\big)$ alone cannot guarantee that () has an optimal solution, for which one would still need to make additional assumptions about the functions $h_n$ in a maximizing sequence $\{(\rho_n, h_n)\}$ for ()(cf. [@HL99 Chap. 12.4B, Thm. 12.4.2]). This makes it less appealing to us to have the dual pair $\big(\R \times \Me_{w_0}(\X), \R \times \Fn_{w_0}(\X)\big)$ with its extra condition (\[eq-excond-q\]) in the LP formulation.

For these reasons, we have formulated () differently. Accordingly, we treat the result on ACOE given in the next proposition not as the property of a dual optimal solution, which may not exist, but as a potential consequence of the results from the LP approach.

As just noted, the dual program () in our formulation need not admit an optimal solution. However, because there is no duality gap, one can still obtain a version of ACOE for the MDP from a maximizing sequence $\{(\rho_n, h_n)\}$ of (), under certain conditions on $\{h_n\}$, using essentially the same arguments as those for [@HL99 Chap. 12.4B, Thm. 12.4.2(c)]. We include the result in the proposition below, for the sake of completeness. Here we consider nonnegative functions $h_n$ (such maximizing sequences exist since adding a constant to $h_n$ does not affect the feasibility and the value of the objective function of the solution $(\rho_n, h_n)$). The limiting function $h^* = \limsup_{n \to \infty} h_n$ is then bounded below. We also consider a case where the family $\{h_n\}$ is pointwise bounded, similarly to [@HL99 Chap. 12.4B, Thm. 12.4.2(c)]. We note that in general, the ACOE (\[eq-ae-acoe\]) given below *need not hold for all $x \in \X$* (see e.g., [@Yu19-minp Example 3.1]).

\[prp-2\] Suppose Assumption \[cond-pc-3\] hold. Let $(\mu^*, p^*)$ be a stationary minimum pair, and let $\{(\rho_n, h_n)\}$ be a maximizing sequence of the dual program (). With $h^* = \limsup_{n \to \infty} h_n$, consider either one of the following cases:

-   $h_n \geq 0$ for all $n \geq 0$, $\int h^* \, d p^* < + \infty$, and $\int_\X \sup_{n \geq 0} h_n(y) \, q(dy \,|\, x, a) < + \infty$ for all $(x, a) \in \Gamma$;

-   $\sup_{n \geq 0} | h_n| \leq \ell \tilde w$ for some $\tilde w \in \Me^+_{\tilde w} (\X)$ and $\ell > 0$, and $\int \tilde w \, d p^* < \infty$, $\int_\X \tilde w(y) \, q(dy \,|\, x, a) < + \infty$ for all $(x, a) \in \Gamma$.

Then the function $h^*$ is finite $p^*\!$-almost everywhere in case (i) and finite everywhere in case (ii). We have $$\rho^* + h^*(x) \leq  c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma,$$ and for $p^*$-almost all $x \in \X$, $$\begin{aligned}
 \label{eq-ae-acoe}
 \rho^* + h^*(x) & = \inf_{a \in A(x)} \left\{ c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}  \\
   & =   \int_{A(x)}  \left\{ c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}  \mu^*(da \mid x).    \label{eq-ae-acoe2}\end{aligned}$$

\[rmk-nonrandom-pol\] We discuss briefly a relation between the above ACOE and nonrandomzed stationary optimal policies for the average-cost MDP. From (\[eq-ae-acoe\])-(\[eq-ae-acoe2\]) and the fact that $(\mu^*, p^*)$ is a stationary pair, one can deduce that there exist a subset $\hat \X \subset \X$ with $p^*(\hat \X) = 1$ and $h^*$ being finite on $\hat \X$, and a nonrandomized stationary policy, i.e., a Borel measurable function $f: \X \to \A$ with $f(x) \in A(x)$ for all $x \in \X$, such that (i) $f$ attains the minimum in the ACOE (\[eq-ae-acoe\]) on $\hat \X$: $$\label{eq-ae-acoe3}
   \rho^* + h^*(x)  = c(x, f(x)) + \int_\X h^*(y) \, q(dy \mid x, f(x)), \qquad \forall \, x \in \hat \X,$$ and (ii) the set $\hat \X$ is absorbing under $f$, namely, $q(\hat \X \, |\, x, f(x)) = 1$ for all $x \in \hat \X$. More specifically, let $\X'$ be the set on which (\[eq-ae-acoe\]) and (\[eq-ae-acoe2\]) hold and $h^*$ is finite. First, one can construct a set $\hat \X \subset \X'$ with $p^*(\hat \X) = 1$ that is absorbing under the policy $\mu^*$, by applying the same proof of [@MeT09 Prop. 4.2.3(ii)] to the stationary Markov chain on $\X$ induced by $\mu^*$ with the initial distribution $p^*$. One can then use (\[eq-ae-acoe\])-(\[eq-ae-acoe2\]) to construct the desired nonrandomized Borel measurable policy $f$ on $\hat \X$, either directly by using the fact that the action space is countable in our case, or by using the Blackwell and Ryll-Nardzewski theorem [@BlR63 Thm. 2] as discussed in [@HL94 Remark 4.6].

This gives the desired nonrandomized policy $f$ and absorbing set $\hat \X$. Then, consider the states in $\hat \X$. From (\[eq-ae-acoe3\]), one can use standard arguments to show that, under certain conditions, the policy $f$ is average-cost optimal for all initial states $x \in \hat \X$. In particular, it is straightforward to show $f$ is optimal on $\hat \X$ in the case $h^* \geq 0$, whereas if $h^* \in \Me_{\tilde w} (\X)$, the optimality of $f$ on $\X$ can be established under further conditions that ensure $\E_x^f \big[ | h^*(x_n)| \big] < \infty$ for $n \geq 0$ and $\liminf_{n \to \infty} n^{-1} \E_x^f \big[ h^*(x_n) \big] \geq 0$ for all $x \in \hat \X$. (For derivation details, see e.g., the related discussions in [@HL94 Sect. 3] and [@HL96 Chap. 5.2] on canonical triplets.)

Extension to Constrained Average-Cost MDPs {#sec-4}
==========================================

In this section, we extend our results for an unconstrained average-cost MDP to a constrained one. Let the state and action spaces and the state transition stochastic kernel of the MDP be the same as before. Consider multiple one-stage cost functions on $\X \times \A$: $c_0, c_1, \ldots, c_d$. We assume that these functions are nonnegative and Borel measurable, finite on $\Gamma$, and taking the value $+\infty$ outside $\Gamma$. The goal is to minimize the average cost w.r.t. $c_0$, while keeping the average costs w.r.t. $c_1, \ldots, c_d$ within given limits.

More specifically, let $\kappa : = (\kappa_1, \ldots, \kappa_d) \geq 0$ be prescribed upper limits on the average costs in the constraints. For a policy $\pi$ and initial distribution $\zeta$, let $J_i(\pi, \zeta)$ denote the average cost of this pair w.r.t. $c_i$, $i = 0, 1, \ldots, d$. Define the feasible set of policy and initial distribution pairs by $$\S : = \big\{  (\pi, \zeta) \in   \Pi \times \P(\X) \, \big| \, J_0(\pi, \zeta) < \infty, \ J_i(\pi, \zeta) \leq \kappa_i, \, i = 1, \ldots, d \, \big\}.$$ Define the optimal average cost of this constrained problem to be $$\rho_c^* : = \inf_{(\pi, \zeta) \in \S} J_0(\pi, \zeta).$$

As before, within the feasible set $\S$, we are especially interested in those stationary pairs. Analogous to the minimum pairs and stationary minimum pairs for an unconstrained MDP, let us define optimal pairs and stationary optimal pairs for the constrained MDP. (What we call optimal pairs are called “constrained optimal pairs” in the prior work [@KNH00].)

\[def-cmdp-minp\]

1.  We call $(\pi^*, \zeta^*) \in \Pi \times \P(\X)$ an *optimal pair* for the constrained MDP if $$(\pi^*, \zeta^*) \in \S \quad \text{and} \quad J_0(\pi^*, \zeta^*)  = \rho^*_c.$$

2.  We call an optimal pair $(\pi^*, \zeta^*)$ *lexicographically optimal* if for each $(\pi, \zeta) \in \S$, either $J_i(\pi^*, \zeta^*) = J_i(\pi, \zeta)$ for all $ 0 \leq i \leq d$, or for some $\bar d \leq d$, $$J_i(\pi^*, \zeta^*) = J_i(\pi, \zeta) \ \ \  \forall \, i \leq \bar d -1, \qquad  J_{\bar d}(\pi^*, \zeta^*) < J_{\bar d}(\pi, \zeta). \qquad \quad$$

\[def-cmdp-sminp\] If a stationary pair $(\mu^*, p^*) \in \Delta_s$ is (lexicographically) optimal for the constrained MDP, we call it a *stationary (lexicographically) optimal pair*.

In what follows, we first adapt the strict unboundedness condition (SU) and the majorization condition (M) to accommodate multiple one-stage cost functions in the constrained MDP, and under those modified conditions we show that stationary optimal pairs exist (Section \[sec-4.1\]). We then formulate primal/dual linear programs for the constrained MDP and present duality results that are analogous to the ones for unconstrained problems (Section \[sec-4.2\]). The proofs of the theorems of this section are collected in Section \[sec-4.3\].

Model Assumptions and Existence of Stationary Optimal Pairs {#sec-4.1}
-----------------------------------------------------------

We impose the following conditions on the constrained MDP model:

\[cond-su-cmdp\]

1.  The feasible set $\S \not=\emptyset$.

2.  There exists a nondecreasing sequence of compact sets $\Gamma_j \uparrow \Gamma$ such that for some $0 \leq i \leq d$, $$\lim_{j \to \infty} \inf_{(x, a) \in \Gamma_j^c} c_i(x, a) = + \infty.$$

3.  For each compact set $K \in \{\proj_\X(\Gamma_j)\}$, there exist an open set $O \supset K$, a closed set $D \subset \X$, and a finite measure $\nu$ on $\B(\X)$ (all of which can depend on $K$) such that $$q\big((O \setminus D) \cap B  \mid x, a \big) \leq \nu(B), \qquad \forall \, B \in \B(\X), \ (x, a) \in \Gamma, \notag$$ where the closed set $D$ (possibly empty) is such that restricted to $D \times \A$, the state transition stochastic kernel $q(dy\,|\, x, a)$ is continuous and all the one-stage cost functions $c_i$, $0 \leq i \leq d$, are lower semicontinuous.

This assumption is similar to Assumption \[cond-pc-3\] for the unconstrained problem. Condition (G) is to exclude vacuous problems. Condition (SU) is the same as that considered in [@HGL03] for the constrained MDP, and it differs from Assumption \[cond-pc-3\](SU) in that here we require *some* one-stage cost function in the constrained problem to be strictly unbounded. Condition (M) is almost identical to Assumption \[cond-pc-3\](M) except that here the closed set $D$ must be such that on it, *every* one-stage cost function in the constrained problem is lower semicontinuous in the state variable. As before, having a nonempty set $D$ in the majorization condition (M) sharpens this condition by allowing us to treat a “continuous” part of the model separately from the rest.

Theorem \[thm-4.1\] below extends our earlier results for MDPs [@Yu19-minp Prop. 3.2, Thm. 3.3] (cf. Theorem \[thm-2.1\]) to constrained MDPs. In particular, its part (i) can be compared with Theorem \[thm-2.1\](i), and its parts (ii)-(iii) with Theorem \[thm-2.1\](ii). The proof will only be outlined in Section \[sec-4.3\], as it is mostly based on the arguments given in [@Yu19-minp]—roughly speaking, the present majorization condition allows us to apply the reasoning in [@Yu19-minp] to every one-stage cost function $c_i$ in the constrained MDP.

Parts (i)-(ii) of this theorem are also comparable with the results of [@HGL03 Thm. 3.2] and [@KNH00 Lemma 1.1 and the solvability part of Lemma 2.3] for constrained lower-semicontinuous MDPs. Part (iii) concerns lexicographically optimal solutions of the constrained MDP, which can be related to solutions for multi-objective MDPs similar to those discussed in [@HR04].

\[thm-4.1\] Under Assumption \[cond-su-cmdp\], the following hold:

-   For any pair $(\pi, \zeta) \in \S$, there exists a stationary pair $(\bar \mu, \bar p) \in \Delta_{s} \cap \S$ with $$J_i(\bar \mu, \bar p) \leq J_i(\pi, \zeta),  \qquad \forall \, i = 0, \ldots, d.$$

-   There exists a stationary optimal pair $(\mu^*, p^*) \in \Delta_{s} \cap \S$.

-   There exists a stationary lexicographically optimal pair $(\mu^*, p^*) \in \Delta_{s} \cap \S$.

It is known that even in a finite-state-and-action MDP, for a given initial state or distribution, there need not exist a stationary optimal policy for the constrained average cost problem. See [@HoK84 Sect. 4, p. 284] for an interesting counterexample (involving a multichain MDP) that is due to Derman [@Der63]. The difference between this known fact and the existence of a stationary optimal pair in Theorem \[thm-4.1\] is that in the constrained MDP here, the initial distribution is not given and there is freedom of choosing it to optimize the average costs.

Suppose that in part (ii) or (iii) of Theorem \[thm-4.1\], the policy $\mu^*$ induces on $\X$ a *positive Harris recurrent* Markov chain (see e.g., [@MeT09 Chap. 10.1] for definition). Then, by the ergodic properties of such Markov chains and by the same proof of [@Yu19-minp Thm. 3.5(b)], we have that for all initial distributions $\zeta$, $\P_\zeta^{\mu^*}$-almost surely, $$\lim_{n \to \infty} n^{-1} \textstyle{\sum_{k=0}^{n-1}} \, c_i(x_k, a_k) = J_i(\mu^*, p^*),  \qquad i = 0, 1, \ldots, d.$$ In other words, almost surely, on each sample path, the pathwise average costs of the policy $\mu^*$ w.r.t. $c_i$, $i = 1, 2, \ldots d$, are also within the prescribed limits $\kappa_i$, while its pathwise average cost w.r.t. $c_0$ equals $\rho_c^*$ as well.

Linear Programming Formulation and Optimality Results {#sec-4.2}
-----------------------------------------------------

Similarly to the unconstrained case, for the constrained MDP, the primal linear program (P) is formulated to minimize the average cost over feasible stationary pairs, by utilizing the correspondence between a stationary pair and a probability measure that satisfies (\[eq-inv-gamma\]) discussed at the beginning of Section \[sec-3.2\]. Under Assumption \[cond-su-cmdp\], the existence of a stationary optimal pair given by Theorem \[thm-4.1\] ensures that such a pair can be obtained by solving the primal program (P). The dual linear program () is, as before, determined by (P) and two dual pairs of vector spaces we choose.

We now define precisely (P) and () for the constrained MDP, by identifying the spaces and linear mappings involved in the general LP formulation given in Section \[sec-2.2\]. To define the primal linear program (P), we consider the dual pair of vector spaces $$\big(\Me_w(\Gamma) \times \R^d, \, \Fn_{w}(\Gamma) \times \R^d\big)$$ where the weight function $w : \Gamma \to \R_+$ is given by $$w(x,a) = 1 + \sup_{0 \leq i \leq d} c_i(x,a), \qquad (x,a) \in \Gamma.$$ The bilinear form associated with this dual pair is defined as the sum of the bilinear forms associated with the two dual pairs, $\big(\Me_w(\Gamma), \, \Fn_w(\Gamma) \big)$ and $(\R^d, \, \R^d)$; i.e., $$\begin{aligned}
 \label{eq-cmdp-bilinear}
\big\langle (\gamma, \alpha) \,,\, (\phi, \alpha') \rangle  & : = \langle \gamma, \, \phi \rangle + \langle \alpha, \, \alpha' \rangle = \int_\Gamma \phi \, d \gamma + \sum_{i=1}^d \alpha_i \alpha_i' \end{aligned}$$ for $(\gamma, \alpha) \in \Me_w(\Gamma) \times \R^d$ and $(\phi, \alpha') \in \Fn_w(\Gamma) \times \R^d$.

The feasible set of (P) corresponds to the subset of stationary pairs that are feasible for the constrained MDP, and it is defined by the following constraints: $$\begin{aligned}
      \gamma \in \Me_w^+(\Gamma), \qquad \gamma(\Gamma) = 1, \qquad
    \hat \gamma (B)  = \int_{\Gamma}  q(B \mid x,a)  \,  \gamma(d(x,a)), \qquad \forall \, B \in \B(\X),\end{aligned}$$ and $$\big( \langle \gamma, \, c_1 \rangle, \, \cdots, \, \langle \gamma, \, c_d \rangle \big) + \alpha = \kappa, \qquad \alpha \geq 0.$$ Note that if $\gamma$ is a probability measure associated with some stationary pair $(\mu, p) \in \S$ via (\[eq-gamma-mup\]), then $\gamma$ is feasible for (P); in particular, $\langle \gamma, w \rangle \leq 1 + \sum_{i=1}^d \langle \gamma, c_i \rangle < \infty$, so $\gamma \in \Me_w^+(\Gamma)$. The objective of (P) is to minimize the average cost $\langle \gamma, c_0 \rangle$. We can state the primal program (P) in the form introduced in Section \[sec-2.2\] as follows: $$\begin{aligned}
   \text{(P)} \quad \qquad \text{minimize}  \ \ \ &  \langle \, \gamma, c_0 \, \rangle \notag \\
                 \text{subject to} \ \ \ & \L(\gamma, \alpha) = (1, \m0, \kappa), \quad  \gamma \in \Me^+_w(\Gamma), \ \ \alpha \geq 0  \quad \ \ \label{eq-cmdp-P}\end{aligned}$$ where the linear mapping $\L:  \Me_w(\Gamma) \times \R^d \to \R \times \Me(\X) \times \R^d$ is given by $\L = (\L_0, \L_1, \L_2)$ with $$\begin{aligned}
  \L_0 (\gamma,\alpha)  & : = \gamma(\Gamma),  \\
  \L_1 (\gamma, \alpha)(B) & : = \hat \gamma (B) - \int_{\Gamma}  q(B \mid x,a)  \,  \gamma(d(x,a)), \qquad \forall \, B \in \B(\X), \\
  \L_2 (\gamma, \alpha) & : = \big( \langle \gamma, \, c_1 \rangle, \, \cdots, \, \langle \gamma, \, c_d \rangle \big) + \alpha,\end{aligned}$$ for $\gamma \in \Me_w(\Gamma)$ and $\alpha = (\alpha_1, \ldots, \alpha_d) \in \R^d$.

To define the dual linear program (), we consider the dual pair of vector spaces $$\big(\R \times \Me(\X) \times \R^d, \, \R \times \Fn_b(\X) \times \R^d \big),$$ with the bilinear form defined as the sum of the bilinear forms for the three dual pairs, $(\R,\, \R)$, $\big(\Me(\X), \, \Fn_b(\X)\big)$, and $(\R^d,\, \R^d)$, similar to (\[eq-cmdp-bilinear\]). From the definition of $\L$, the adjoint mapping $\L^*$ can be identified: it is the linear mapping $\L^*= (\L_1^*, \L_2^*)$ on $\R \times \Fn_b(\X) \times \R^d$ given by $$\begin{aligned}
   \L^*_1(\rho, h, \beta) (x,a)& : = \rho + h(x) - \int_\X h(y) \, q(dy \mid x, a) + \sum_{i =1}^d \beta_i c_i(x,a), \qquad (x,a) \in \Gamma,\\
   \L^*_2(\rho, h, \beta) & : = \beta,\end{aligned}$$ for $(\rho, h, \beta) \in \R \times \Fn_b(\X) \times \R^d$. Clearly, $L^*(\R \times \Fn_b(\X) \times \R^d) \subset \Fn_w(\Gamma) \times \R^d$, so both linear mappings $\L$ and $\L^*$ are weakly continuous ([@RoR73 Chap. II, Prop. 12 and its corollary]; cf. Prop. \[prp-wcontinuity\]). The objective function of () is $$\big\langle (1, \m0, \kappa), \, (\rho, h, \beta) \big\rangle = \rho + \sum_{i=1}^d \beta_i \kappa_i.$$

Let us state the dual program () in the form introduced in Section \[sec-2.2\]: $$\begin{aligned}
   \text{(\Pstar)} \quad \qquad \text{maximize}  \ \ \ &  \rho + \sum_{i=1}^d \beta_i \kappa_i \notag \\
                 \text{subject to} \ \ \ & \L^*(\rho, h, \beta) \leq (c_0, 0), \quad \rho \in  \R, \ h \in \Fn_b(\X), \ \beta \in \R^d. \label{eq-cmdp-dP}\end{aligned}$$ Note that the inequality constraint in (\[eq-cmdp-dP\]) is the same as the cone constraint $ - \L^*(\rho, h, \beta) + \big( c_0, \, 0 \big) \in \Fn^+_w(\Gamma) \times \R_+^d$ (cf. Section \[sec-2.2\]), and it can be expressed more explicitly as $$\begin{aligned}
\rho + h(x) - \int_\X h(y) \, q(dy \mid x, a) + \sum_{i=1}^d  \beta_i c_i(x,a) & \ \leq \ c_0(x, a), \qquad \forall \, (x,a) \in \Gamma, \label{eq-cmdp-dual-cstr1}\\
\beta & \ \leq \ 0. \label{eq-cmdp-dual-cstr2}\end{aligned}$$

The next theorem about the primal/dual programs (P) and () is an extension of Theorem \[thm-1\] to the constrained MDP. The solvability of (P) is a consequence of the existence of a stationary optimal pair given in Theorem \[thm-4.1\](ii) (the proof of which also shows that any minimizing sequence of (P) has a subsequence that converges to an optimal solution of (P) in the topology of weak convergence, similarly to the unconstrained case). The absence of duality gap is the main result of this section. Its proof, outlined in Section \[sec-4.3\], uses essentially the same proof arguments for Theorem \[thm-1\](ii), which handle the discontinuous MDP models by making use of Lusin’s theorem together with the majorziation property in Assumption \[cond-su-cmdp\](M).

\[thm-4.2\] Under Assumption \[cond-su-cmdp\], the following hold for the linear programs (P) and () given in (\[eq-cmdp-P\]) and (\[eq-cmdp-dP\]):

-   \(P) is consistent and solvable, and () is consistent.

-   There is no duality gap: $\inf (\text{P})  = \sup (\Pstar) = \rho^*_c$.

This theorem is comparable with the prior results [@HGL03 Thm. 4.4] and [@KNH00 Lemma 2.3] on the LP approach for constrained lower-semicontinuous MDPs ([@KNH00] considers compact spaces, and [@HGL03] non-compact spaces). Besides the differences in model assumptions, our formulation of the dual program () also differs from that in [@HGL03]. The main difference lies in the choice of the spaces $\Me(\X)$ and $\Fn_{b}(\X)$ for (). As in the unconstrained case, our motivation for this choice is to avoid an extra condition on the state transition stochastic kernel used in [@HGL03], which is the same condition (\[eq-excond-q\]) from [@HL99 Chap. 12.3] that we discussed earlier in Remark \[rem-LP\]. For the same reason as explained in Remark \[rem-LP\], the dual program () as we formulated above need not admit an optimal solution.

For completeness, in the rest of this section, we discuss some solution properties of the dual program (). Recall that a sequence of feasible solutions $(\rho_n, h_n, \beta_n)$ of () is called a maximizing sequence if $\rho_n \uparrow \sup (\Pstar)$. We first examine the boundedness property of $\{\beta_n\}$. Denote by $\beta_{n,j}$ the $j$th component of $\beta_n$. Let us separate the constraints of the MDP into two categories: $$\J^{(0)} : = \big\{ i \mid 1 \leq i \leq d, \ \exists\, (\pi, \zeta) \in \S \ s.t.\ J_i(\pi, \zeta) < \kappa_i \big\}, \qquad \J^{(1)} : = \{ 1, 2, \ldots, d\} \setminus \J^{(0)}. \quad$$ When $\S \not= \emptyset$, $\J^{(1)}$ consists of all those $i$ such that w.r.t. $c_i$, every feasible pair in $\S$ has the same maximally allowed average cost $\kappa_i$.

\[prp-4.3\] Suppose Assumption \[cond-su-cmdp\] hold. Let $\{(\rho_n, h_n, \beta_n)\}$ be a maximizing sequence of the dual program (). Let $(\mu^*, p^*)$ be any stationary optimal pair for the constrained MDP. Then the following hold:

-   The sequence $\{\beta_{n,j}\}_{n \geq 0}$ is bounded for every $j \in \J^{(0)}$.

-   For $1 \leq j \leq d$, $\lim_{n \to \infty} \beta_{n,j} = 0$ if $J_j(\mu^*, p^*) < \kappa_j$.

-   Suppose there exists $(\pi, \zeta) \in \Pi \times \P(\X)$ such that $$J_j(\pi, \zeta) < \kappa_j \quad \forall \, j \in \J^{(1)}, \qquad J_j(\pi, \zeta) < \infty \quad \forall \, j \in \J^{(0)} \cup \{ 0\}.$$ Then the sequence $\{\beta_{n}\}_{n \geq 0}$ is bounded.

An optimal solution $(\gamma^*, \alpha^*)$ of (P) corresponds to a stationary optimal pair $(\mu^*, p^*)$ with $\alpha^*_j = \kappa_j - J_j(\mu^*, p^*)$ for $1 \leq j \leq d$ (this follows from the correspondence relationship explained at the beginning of Section \[sec-3.2\]). So Prop. \[prp-4.3\](ii) entails the complementarity relation $\langle \alpha^*, \, \beta^* \rangle = 0$ for an optimal solution $(\gamma^*, \alpha^*)$ of (P), if we define $\beta^* = (\beta^*_1, \ldots, \beta^*_d)$ as follows: $\beta^*_j = \lim_{n \to \infty} \beta_{n,j}$ if this limit exists, and assign $\beta^*_j$ an arbitrary number otherwise.

Proposition \[prp-4.3\](iii) gives a sufficient condition under which the $\J^{(1)}$-components of $\{\beta_n\}$ are also bounded—note that this condition involves *non-feasible* policy and initial distribution pairs and is different from the Slater condition $\J^{(1)} = \emptyset$. One exceptional case where Prop. \[prp-4.3\](iii) is inapplicable is when $\kappa_i = 0$ for all $1 \leq i \leq d$.

When $\{\beta_{n}\}_{n \geq 0}$ is bounded, as when the condition of Prop. \[prp-4.3\](iii) holds, we can choose a subsequence of the maximizing sequence $\{(\rho_n, h_n, \beta_n)\}$ so that $\beta_n$ converges. The subsequence is obviously also a maximizing sequence for (). Then, with additional assumptions on the sequence of functions $h_n$, we can derive an optimality equation for the constrained MDP that is analogous to the ACOE (\[eq-ae-acoe\]) in Prop. \[prp-2\] for the unconstrained MDP. We state this result in the next proposition. It is comparable with the result of [@HGL03 Thm. 5.2(b)] for constrained lower-semicontinuous MDPs; in the latter reference, (\[eq-cmdp-ae-acoe\]) is called the “constrained optimality equation.”

\[prp-4.4\] Suppose Assumption \[cond-su-cmdp\] hold. Let $(\mu^*, p^*)$ be a stationary optimal pair for the constrained MDP. Let $\{(\rho_n, h_n, \beta_n)\}$ be a maximizing sequence of the dual program (). Assume that $\{\beta_n\}$ converges to some finite $\beta^*$, and let $$c^*(x,a) : = c_0(x,a) - \textstyle{\sum_{i=1}^d} \, \beta^*_i c_i(x,a), \qquad \tilde{\rho}^* : = \rho^*_c - \sum_{i=1}^d \beta^*_i \kappa_i.$$ With $h^* : = \limsup_{n \to \infty} h_n$, assume any one of the following cases holds:

-   $h_n \geq 0$ for all $n \geq 0$, $\int h^* \, d p^* < + \infty$, and $\int_\X \sup_{n \geq 0} h_n(y) \, q(dy \mid x, a) < + \infty$ for all $(x, a) \in \Gamma$;

-   $\sup_{n \geq 0} | h_n| \leq \ell \tilde w$ for some $\tilde w \in \Me^+_{\tilde w} (\X)$ and $\ell > 0$, and $\int \tilde w \, d p^* < \infty$, $\int_\X \tilde w(y) \, q(dy \,|\, x, a) < + \infty$ for all $(x, a) \in \Gamma$.

Then $h^*$ is finite $p^*\!$-almost everywhere, finite everywhere in case (ii), and satisfies $$\label{eq-cmdp-dsol}
  \tilde{\rho}^* + h^*(x) \leq c^*(x,a) +  \int_\X h^*(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma.$$ Furthermore, for $p^*$-almost all $x \in \X$, $$\begin{aligned}
 \label{eq-cmdp-ae-acoe}
 \tilde{\rho}^* + h^*(x) & = \inf_{a \in A(x)} \left\{ c^*(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}  \\
   & = \int_{a \in A(x)} \left\{ c^*(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}  \mu^*(da \mid x). \label{eq-cmdp-ae-acoe2}\end{aligned}$$

Proofs {#sec-5}
======

This section collects the proofs of the theorems given in Sections \[sec-3\] and \[sec-4\].

Proofs for Section \[sec-3\]
----------------------------

Let us first recall a few definitions and facts about probability measures on a metrizable space $X$. Let $\C_b(X)$ denote the set of real-valued, bounded continuous functions on $X$. By definition, a sequence of probability measures $p_n \in \P(X)$ *converges weakly* to some $p \in \P(X)$, denote $p_n \wto p$, if $\int f  d p_n \to \int f  dp$ for all $f \in \C_b(X)$. If $\mathcal{E}$ is a family of probability measures in $\P(X)$ such that for any $\epsilon > 0$, there is a compact set $K \subset X$ with $p(K) > 1 - \epsilon$ for all $p \in \mathcal{E}$, we say that $\mathcal{E}$ is *tight*.

By Prohorov’s theorem [@Bil68 Thm. 6.1], any sequence in a tight family $\mathcal{E}$ has a further subsequence that converges weakly to a probability measure in $\P(X)$. We will use this fact many times in the present section as well as in Section \[sec-4\], for some family $\mathcal{E} \subset \P(\Gamma)$ that satisfies $\sup_{\gamma \in \mathcal{E}} \langle \gamma, \, c \rangle < \infty$. By the strict unboundedness condition on $c$ given in Assumption \[cond-pc-3\](SU), such a family $\mathcal{E}$ must be tight (as can be seen easily from condition (SU) and the definition of tightness).

### Proof of Theorem \[thm-1\]

The consistency of (P) and () and the solvability of (P) were already discussed in Section \[sec-3.1\], where we also showed that under Assumption \[cond-pc-3\], $0 \leq \sup (\Pstar) \leq \inf (\text{P}) = \rho^*$.

We now prove that there is no duality gap between (P) and (). Our approach is to use [@AnN87 Thm. 3.3] (cf. Theorem \[thm-subc\] in Section \[sec-2.2\]), which asserts the equality between the subvalue of (P) and the value of () when they are finite. Specifically, recall from Section \[sec-2.2\] that the subvalue of (P) is defined as $$\urho : = \inf \big\{ r \mid \big( (1, \m0), r \big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu} \big\},$$ where the set $H \subset \R \times \Me(\X) \times \R$ is given by $$H : = \big\{ \big(L \gamma, \, \langle \, \gamma, c \, \rangle + r \big) \, \big| \, \gamma \in \Me_w^+(\Gamma), \ r \geq 0 \big\},$$ and ${\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ is the closure of $H$ in the weak topology $\sigma \big(\R \times \Me(\X) \times \R, \, \R \times \Fn_b(\X) \times \R \big)$. Since (P) and () are consistent, $\sup (\Pstar)$ is finite and equals the subvalue $\urho$ by [@AnN87 Thm. 3.3] (cf. Theorem \[thm-subc\]). So, to show $\inf(\text{P}) = \sup (\Pstar)$, we need to prove $\rho^* = \urho$. In what follows, we will prove that $$\big((1, \m0), \, \urho \, \big) \in H,$$ by constructing a stationary pair whose average cost is no greater than $\urho$. This will give us $\rho^* = \urho$ (since it implies $\urho \geq \rho^*$, whereas $\rho^* \geq \urho$). The proof will proceed in four steps, with the first three steps making preparations for the last one.

[**Step (i):**]{} From the definition of $\urho$, it follows that $\big((1, \m0), \urho\big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ and moreover, there exist a direct set $\nI$ and a net $\{\gamma_i\}_{i \in \nI}$ in $\Me_w^+(\Gamma)$ with $$\big(L \gamma_i \,, \, \langle \, \gamma_i, c \, \rangle \big) \to \big((1, \m0), \urho \,\big)$$ in the $\sigma \big(\R \times \Me(\X) \times \R, \, \R \times \Fn_b(\X) \times \R \big)$ topology. This means that $$\begin{aligned}
   \gamma_i(\Gamma) & \to 1,   \label{eq-thm1-prf1} \\
  \int_\X h(x) \, \hat \gamma_i(dx) - \int_{\Gamma} \int_\X h(y) \, q(dy \mid x, a) \, \gamma_i(d(x,a)) & \to 0, \qquad \forall \, h \in \Fn_b(\X),  \label{eq-thm1-prf2} \\
   \langle \, \gamma_i, c \, \rangle & \to \urho.  \label{eq-thm1-prf3}\end{aligned}$$ In view of (\[eq-thm1-prf1\]), there exists $\bar i \in \nI$ such that for all $i \geq \bar i$, $\gamma_i(\Gamma) > 0$. Then, since all $\gamma_i$ are nonnegative measures and $\gamma_i(\Gamma) \to 1$, by restricting attention to $\gamma_i, i \geq \bar i$, and considering the normalized measures $\gamma_i(\cdot)/\gamma_i(\Gamma)$ instead of $\gamma_i$, we can redefine the net $\{\gamma_i\}_{i \in \nI}$ in the above so that every $\gamma_i$ is a probability measure on $\B(\Gamma)$: $$\gamma_i(\Gamma) = 1, \qquad \forall \,  i \in \nI.$$

[**Step (ii):**]{} Next, from the net $\{\gamma_i\}_{i \in \nI}$, we will extract a *sequence* of probability measures with the property that the convergence in (\[eq-thm1-prf2\]) holds for a *countable subset* of the functions in $\Fn_b(\X)$. We start by defining this subset. It consists of two countable families of functions, $\hat \C_b(\X)$ and $\hat \Fn_b(\X)$. The set $\hat \C_b(\X)$ involves continuous bounded functions that will be used to determine if two probability measures on $\X$ are equal. The set $\hat \Fn_b(\X)$ involves indicator functions of certain sets in $\X$ that will be important in the subsequent proof to handle the discontinuities in the MDP model by using Lusin’s theorem and the majorization property in Assumption \[cond-pc-3\](M). The construction of $\hat \Fn_b(\X)$ will use the arguments we used in the proof of [@Yu19-minp Thm. 3.5(a)]. The precise definitions of these two sets are as follows.

Recall that $\C_b(\X)$ is the set of (real-valued) bounded continuous functions on $\X$. Since $\X$ is metrizable, by [@Par67 Thm. 6.6], there exists a countable set $$\hat \C_b(\X) :  = \{h_1, h_2, \ldots\} \subset \C_b(\X)$$ such that in $\P(\X)$, a sequence of probability measures $p_n \wto p \in \P(\X)$ if and only if $$\textstyle{ \int h \, d p_n \, \to \, \int h \, dp}, \qquad \forall \, h \in \hat \C_b(\X).$$ Then by [@Dud02 Prop. 11.3.2], for any $p,p' \in \P(\X)$, $$\label{eq-detclass}
  p = p' \qquad \Longleftrightarrow \qquad  \textstyle{\int h \, d p \, = \, \int h \, dp'}, \qquad \forall \, h \in \hat \C_b(\X).$$ The countable set $\hat \C_b(\X)$ is the first family of functions we will need.

We now define the other countable family $\hat \Fn_b(\X)$ of indicator functions mentioned earlier. The definition of this set involves some new notations and Lusin’s theorem.

Let $\Z_+$ denote the set of all positive integers. For $m \in \Z_+$, define the truncated one-stage cost function $c^m(\cdot) : = \min \{c(\cdot), m\}$ on $\X \times \A$ (later, a technical argument in Step (iv) of our proof will involve these $c^m$ functions). For each $j \in \Z_+$, corresponding to the compact set $\Gamma_j$ in Assumption \[cond-pc-3\](SU), let $(O_j, D_j, \nu_j)$ be the open set, the closed set, and the finite measure, respectively, in Assumption \[cond-pc-3\](M) for $K = \proj_\X(\Gamma_j)$. Let $F_j : = \proj_\A(\Gamma_j)$, the projection of $\Gamma_j$ on $\A$. Then the set $F_j$ is compact, and since $\A$ is countable and discrete, this means that the set $F_j$ is finite.

\[lem-lusin\] For each $j,m \in \Z_+$ and $\ell \in \Z_+$, there exist closed subsets $B^1_{j,m,\ell}$ and $B^2_{j,\ell}$ of $\X$ such that the following hold:

1.  $\nu_j \big(\X \setminus B^1_{j,m,\ell} \big) \leq \ell^{-1}$ and $\nu_j \big(\X \setminus B^2_{j,\ell} \big) \leq \ell^{-1}$;

2.  restricted to the set $B^1_{j,m,\ell} \times F_j$, the function $c^m(\cdot)$ is continuous, and restricted to the set $B^2_{j,\ell} \times F_j$, the state transition stochastic kernel $q(dy \,|\, \cdot,\cdot)$ is continuous.

This lemma is a consequence of Lusin’s theorem (see [@Dud02 Thm. 7.5.2]), which asserts that if $f$ is a Borel measurable function from a topological space $X$ into a separable metric space $S$ and $\nu$ is a closed regular finite Borel measure on $X$, then for any $\delta > 0$, there is a closed set $B$ such that $\nu(X \setminus B) < \delta$ and the restriction of $f$ to $B$ is continuous.

We apply this theorem with $X = \X$ and $\nu = \nu_j$ for each $j$ in the lemma. Since $\X$ is a metrizable topological space, every finite Borel measure is closed regular by [@Dud02 Thm. 7.1.3], and therefore, the finite measure $\nu_j$ in the lemma meets the condition in Lusin’s theorem.

For each $j, m, \ell \in \Z_+$, to find the desired closed set $B^1_{j,m,\ell}$, we apply Lusin’s theorem with $X = \X$, $S = \R$, $\nu = \nu_j$ and $\delta = \ell^{-1}/|F_j|$, and with the function $f(\cdot) = c^m(\cdot, a)$ for each action $a \in F_j$. This gives us, for each $a \in F_j$, a closed set $E_a$ such that $\nu_j(\X \setminus E_a) < \delta$ and restricted to $E_a$, $c^m(\cdot, a)$ is continuous. Then the closed set $B^1_{j,m,\ell} : = \cap_{a \in F_j} E_a$ has the desired property that $\nu_j \big(\X \setminus B^1_{j,m,\ell} \big) \leq \ell^{-1}$ and restricted to $B^1_{j,m,\ell} \times F_j$, $c^m(\cdot, \cdot)$ is continuous.

For each $j, \ell \in \Z_+$, the desired closed set $B^2_{j,\ell}$ is constructed similarly, by applying Lusin’s theorem to the state transition stochastic kernel $q(dy \,|\, x, a)$, which is a $\P(\X)$-valued Borel measurable function on $\X \times \A$. Specifically, we let $X = \X$, $S = \P(\X)$, $\nu = \nu_j$, and $\delta = \ell^{-1}/|F_j|$. (Since $\X$ is separable and metrizable, by [@bs Prop. 7.20], $\P(\X)$ is also a separable metrizable space and hence meets the condition for the space $S$ in Lusin’s theorem.) We apply Lusin’s theorem to $f(\cdot) =  q(dy \,|\, \cdot, a)$ for each $a \in F_j$ to obtain a closed set $E_a$ such that $\nu_j(\X \setminus E_a) < \delta$ and restricted to $E_a$, $q(dy \,|\, \cdot, a)$ is continuous. We then let the desired set $B^2_{j,\ell} = \cap_{a \in F_j} E_a$.

We group $(O_j, D_j, \nu_j, B^1_{j,m,\ell})$, $(O_j, D_j, \nu_j, B^2_{j,\ell})$ in the preceding proof into two countable collections $\W_1$ and $\W_2$: $$\W_1 := \big\{ (O_j, D_j, \nu_j, B^1_{j,m,\ell}) \mid j,m,\ell \in \Z_+ \big\}, \qquad   \W_2 := \big\{ (O_j, D_j, \nu_j, B^2_{j,\ell}) \mid j,\ell \in \Z_+ \big\}.$$ Let $\ind_E$ denote the indicator function for a set $E$. Finally, define a countable set $\hat \Fn_b(\X)$ of indicator functions on $\X$ by $$\label{eq-def-indfn}
    \hat \Fn_b(\X) : = \big\{ \ind_E(\cdot) \mid  E = (O \setminus D) \cap B^c \ \, \text{for some} \ \, (O, D, \nu, B) \in \W_1 \cup \W_2 \big\}.$$ Note that the sets $E$ in (\[eq-def-indfn\]) are open sets (since $O$ is open and $D, B$ are closed); this fact will be useful later.

We now extract a desirable sequence from the net $\{\gamma_i\}_{i \in \nI}$:

\[lem-net2seq\] There exists a sequence $\{\gamma_n\}_{n \geq 0} \subset \{\gamma_i\}_{i \in \nI}$ such that $$\begin{aligned}
  \int_\X h(x) \, \hat \gamma_n(dx) - \int_{\Gamma} \int_\X h(y) \, q(dy \mid x, a) \, \gamma_n(d(x,a)) & \to 0, \qquad \forall \, h \in \hat \C_b(\X) \cup \hat \Fn_b(\X),  \label{eq-thm1-prf2a} \\
   \langle \, \gamma_n, c \, \rangle  & \to \urho.  \label{eq-thm1-prf3a}\end{aligned}$$

Let us order the functions in the countable set $\hat \C_b(\X) \cup \hat \Fn_b(\X)$ as $h_1, h_2, \ldots$. Choose any $\bar i_0 \in \nI$ and let $\gamma_n = \gamma_{\bar i_0}$ for $n = 0$. For each $n \geq 1$, by (\[eq-thm1-prf2\])-(\[eq-thm1-prf3\]), there exists $\bar i_n \in \nI$, $\bar i_n \geq \bar i_{n-1}$ such that for all $i \geq \bar i_n$, $$\begin{aligned}
 \left| \, \int_\X h(x) \, \hat \gamma_i(dx) - \int_{\Gamma} \int_\X h(y) \, q(dy \mid x, a) \, \gamma_i(d(x,a)) \, \right| & \leq  n^{-1}, \qquad \forall \,  h \in \big\{ h_1, h_2, \, \ldots, h_n \big\},  \\
 \urho - n^{-1} \leq  \langle \, \gamma_i, c \, \rangle  & \leq \urho+ n^{-1}.  \end{aligned}$$ Let $\gamma_n = \gamma_{\bar i_n}$. The resulting sequence $\{\gamma_n\}_{n \geq 0}$ satisfies (\[eq-thm1-prf2a\])-(\[eq-thm1-prf3a\]).

[**Step (iii):**]{} Henceforth, we work with the sequence $\{\gamma_n\}$ of probability measures given by Lemma \[lem-net2seq\]. The relation (\[eq-thm1-prf3a\]) together with Assumption \[cond-pc-3\](SU) implies that $\{\gamma_n\}$ is a tight family of probability measures on $\B(\Gamma)$. So by Prohorov’s theorem [@Bil68 Thm. 6.1], it has a subsequence that converges weakly to some probability measure $\bar \gamma$ on $\B(\Gamma)$. To simplify notation, let us use the same notation $\{\gamma_n\}$ to denote the convergent subsequence. Thus $\gamma_n \wto \bar \gamma$.

By [@bs Cor. 7.27.2], the probability measure $\bar \gamma$ can be decomposed into its marginal $\bar p$ on $\X$ and a stochastic kernel $\bar \mu$ on $\A$ given $\X$ that obeys the control constraint of the MDP; i.e., $$\bar \gamma(d(x,a)) = \bar \mu(da \mid x) \, \bar p(dx).$$ This gives us a stationary policy $\bar \mu$. Before we investigate the property of the pair $(\bar \mu, \bar p)$ in the next step, we need the following majorization property:

\[lem-su-mp\] For every $(O, D, \nu, B) \in \W_1 \cup \W_2$, $$\limsup_{n \to \infty} \, \hat \gamma_{n} \big((O \setminus D)\cap B^c \big) \leq \nu(B^c), \qquad   \bar p\big( (O \setminus D)\cap B^c \big) \leq \nu(B^c).$$

For $(O, D, \nu, B) \in \W_1 \cup \W_2$, let $E = (O \setminus D) \cap B^c$ and since the indicator function $\ind_E \in \hat \Fn_b(\X)$, we have, by (\[eq-thm1-prf2a\]) in Lemma \[lem-net2seq\], that $$\epsilon_n : = \textstyle{\big| \, \hat \gamma_n(E) - \int_{\Gamma} q(E \mid x, a) \, \gamma_n(d(x,a)) \, \big|} \to 0.$$ We also have, by Assumption \[cond-pc-3\](M), $$\int_{\Gamma} q(E \mid x, a) \,  \gamma_n(d(x,a)) \leq \int_{\Gamma} \nu(B^c) \, \gamma_n(d(x,a)) = \nu(B^c).$$ Hence $\hat \gamma_n ( E) \leq \nu(B^c) + \epsilon_n$ for all $n \geq 0$; consequently, $\limsup_{n \to \infty} \!\hat \gamma_{n} (E) \leq \nu(B^c)$.

Now $\hat \gamma_n \wto \bar p$ (since $\gamma_n \wto \bar \gamma$) and $E$ is an open set (since $O$ is open and $D, B$ are closed). Therefore, by [@Dud02 Thm. 11.1.1] and the first part of the proof, $\bar p(E) \leq \liminf_{n \to \infty} \!\hat \gamma_n (E) \leq \nu(B^c)$.

[**Step (iv):**]{} We are now ready to prove that $\big((1,\m0), \urho \big) \in H$.

\[lem-sp-subv\] The pair $(\bar \mu, \bar p)$ is a stationary pair with $J(\bar \mu, \bar p) = \langle \bar \gamma, \, c \rangle \leq \urho$.

We will only outline the proof, because the arguments for this lemma are essentially the same as those we used in an earlier work to prove the existence and pathwise optimality properties of stationary pairs [@Yu19-minp Sect. 4.1 and Sect. 4.3.1]. By Lemma \[lem-net2seq\], it suffices to prove the inequality $$\label{eq-lemdp-prf1}
   \langle \bar \gamma, \, c \rangle \leq \lim_{n \to \infty}  \langle \, \gamma_n, c \, \rangle  = \urho$$ and to prove that for all $h \in \hat \C_b(\X)$, $$\label{eq-lemdp-prf2}
   \lim_{n \to \infty}  \int_{\Gamma} \int_{\X} h (y) \, q(dy \mid x, a) \, \gamma_{n} (d(x,a)) = \int_{\Gamma} \int_{\X} h(y) \, q(dy \mid x, a) \, \bar \gamma (d(x,a)).$$ To see the sufficiency of (\[eq-lemdp-prf1\]) and (\[eq-lemdp-prf2\]), note that (\[eq-lemdp-prf2\]), together with (\[eq-thm1-prf2a\]) in Lemma \[lem-net2seq\] and the fact $\lim_{n \to \infty} \int h \, d \hat \gamma_n =  \int h \, d \bar p$ for all $h \in \hat \C_b(\X)$ (since $\hat \gamma_n \wto \bar p$), will imply that $$\int_{\Gamma} \int_{\X} h(y) \, q(dy \mid x, a) \, \bar \gamma (d(x,a)) = \int_\X h \,  \bar p(dx), \qquad \forall \, h \in \hat \C_b(\X).$$ In turn, this will imply that $\bar p$ is identical to the probability measure $\int_{\Gamma} q(\cdot \mid x, a) \, \bar \gamma (d(x,a))$ (cf. (\[eq-detclass\])), thus proving that $\bar p$ is an invariant probability measure for the Markov chain induced by the policy $\bar \mu$ and hence $(\bar \mu, \bar p)$ is a stationary pair. Then the first relation (\[eq-lemdp-prf1\]) will give us the desired inequality $J(\bar \mu, \bar p) = \langle \bar \gamma, \, c \rangle  \leq \urho$.

[**Proving (\[eq-lemdp-prf1\]):**]{} The proof of (\[eq-lemdp-prf1\]) is essentially the same as that given in [@Yu19-minp Sect. 4, proofs of Lemmas 4.3 and 4.9]. Below, we sketch the main proof arguments (see the proofs in [@Yu19-minp] for the details of each step):

1.  To show (\[eq-lemdp-prf1\]), it suffices to show that for each $m \in \Z_+$, $$\label{eq-lemdp-prf3}
       \int c^m  \, d \bar \gamma  \, \leq \, \liminf_{n \to \infty} \int c^m  \, d  \gamma_n.$$ (In the above, the probability measures $\bar \gamma$ and $\gamma_n$ are extended from $\Gamma$ to $\X \times \A$, and $c^m$ is the truncated one-stage cost function $\min \{c(\cdot), m\}$, as we recall.)

2.  Fix $m$. To prove (\[eq-lemdp-prf3\]), consider arbitrarily small $\epsilon = \delta = \ell^{-1}$, for some arbitrarily large $\ell \in \Z_+$. The tightness of $\{\gamma_n\}$ and the fact that $\gamma_n \wto \bar \gamma$, together with Assumption \[cond-pc-3\](SU), allow us to choose $j \in \Z_+$ large enough so that for the compact set $\Gamma_j$ in Assumption \[cond-pc-3\](SU), we have $\gamma_n(\Gamma_j^c) \leq \epsilon$ for all $n$ and $\bar \gamma(\Gamma_j^c) \leq \epsilon$. This in turn allows us to bound $\int_{\Gamma_j^c} c^m  d \gamma_n$ and $\int _{\Gamma_j^c} c^m  d \bar \gamma$ by $m  \epsilon$, an negligible term when we take $\epsilon \to 0$. Consequently, to prove (\[eq-lemdp-prf3\]), we can focus on the integrals of $c^m$ on the compact set $\Gamma_j$ and on bounding the difference $$\label{eq-lemdp-prf4}
       \int_{\Gamma_j} c^m  d \gamma_n - \int _{\Gamma_j} c^m  d \gamma.$$

3.  We now handle the term (\[eq-lemdp-prf4\])—this is where we apply Lusin’s theorem and the majorization property given in Assumption \[cond-pc-3\](M). Corresponding to $\Gamma_j$, let us choose the element $(O, D, \nu, B) : = (O_j, D_j, \nu_j, B^1_{j,m,\ell}) \in \W_1$ (cf. the definition of the set $\W_1$ given in Step (ii)). By the definition of the set $B^1_{j,m,\ell}$ (cf. Lemma \[lem-lusin\] in Step (ii)), the function $c^m$ is continuous on the closed set $B \times F_j$ and $\nu(B^c) \leq \delta = \ell^{-1}$. We handle the continuous part of $c^m$ separately from the rest of $c^m$. For the continuous part, we apply the Tietze–Urysohn extension theorem [@Dud02 Thm. 2.6.4] to extend the restriction of $c^m$ to the closed set $(D \cup B) \times F_j$ (on which $c^m$ is lower semicontinuous in view of the property of $D$ given in Assumption \[cond-pc-3\](M)) to a nonnegative lower semicontinuous function $\tilde c^m$ on the entire space $\X \times \A$. Since $\gamma_n \wto \bar \gamma$, by [@HL96 Prop. E.2], $$\liminf_{n \to \infty} \int \tilde c^m d \gamma_n \geq \int \tilde c^m \, d \bar \gamma.$$ We then handle the difference between $c^m$ and $\tilde c^m$. These two functions differ only outside the set $(D \cup B) \times F_j$. By using the fact $\nu(B^c) \leq \delta$, the majorization property given in Lemma \[lem-su-mp\], and the bounds $\int_{\Gamma_j^c} c^m d \gamma_n \leq m \epsilon$, $\int _{\Gamma_j^c} c^m d \bar \gamma \leq m  \epsilon$ from Step 2, we can calculate that $$\limsup_{n \to \infty} \left| \int_{\X \times \A} ( c^m - \tilde c^m)  d \gamma_n  \right| \leq m \, (\delta +\epsilon), \qquad \ \ \left| \int_{\X \times \A} ( c^m - \tilde c^m)  d \bar \gamma  \right| \leq m \, (\delta +\epsilon).$$

4.  Finally, putting all the pieces together gives us the inequality $$\liminf_{n \to \infty} \int c^m \, d \gamma_{n} \geq \int c^m \, d \bar \gamma - 2m \, ( \delta + \epsilon).$$ By letting $\ell \to \infty$ so that $\delta, \epsilon \to 0$, the desired relation (\[eq-lemdp-prf3\]) follows for all $m \in \Z_+$ and this implies (\[eq-lemdp-prf1\]).

[**Proving (\[eq-lemdp-prf2\]):**]{} The proof of (\[eq-lemdp-prf2\]) is similar to the above and essentially the same as that given in [@Yu19-minp Sect. 4, proofs of Lemmas 4.4 and 4.10]. We outline the main arguments below (see [@Yu19-minp] for detailed derivations):

1.  Consider an arbitrary $h \in \hat C_b(\X)$. Let $\epsilon = \delta = \ell^{-1}$, for some arbitrarily large $\ell \in \Z_+$. Proceed as in Step 2 of the proof of (\[eq-lemdp-prf1\]) to choose $j \in \Z_+$ large enough so that for the compact set $\Gamma_j$ in Assumption \[cond-pc-3\](SU), we have $\gamma_n(\Gamma_j^c) \leq \epsilon$ for all $n$ and $\bar \gamma(\Gamma_j^c) \leq \epsilon$.

2.  Define a function $\phi(x,a) : = \int_\X h(y) q(dy \, |\, x,a)$ on $\X \times \A$. Corresponding to the chosen $j$ and $\ell$, choose the element $(O,D,\nu,B) : = (O_j, D_j, \nu_j, B^2_{j,\ell}) \in \W_2$. By the definition of the set $B^2_{j,\ell}$ (cf. Lemma \[lem-lusin\] in Step (ii)), $\nu(B^c) \leq \delta = \ell^{-1}$ and on the closed set $B \times F_j$, $q(dy \,|\, \cdot, \cdot)$ is continuous. Then, since $q(dy \,|\, \cdot, \cdot)$ is also continuous on the closed set $D \times \A$ (cf. Assumption \[cond-pc-3\](M)) and $h$ is a continuous function, we have, by [@bs Prop. 7.30], that the function $\phi$ is continuous on the closed set $(D \cup B) \times F_j$. We now treat the continuous part of $\phi$ separately: by the Tietze–Urysohn extension theorem [@Dud02 Thm. 2.6.4], the restriction of $\phi$ to $(D \cup B) \times F_j$ can be extended to a bounded continuous function $\tilde \phi$ on the entire space $\X \times \A$, with $\| \tilde \phi \|_\infty \leq \| \phi\|_\infty \leq \| h \|_\infty$. Since $\gamma_n \wto \bar \gamma$, we have $$\lim_{n \to \infty} \int \tilde \phi \, d \gamma_n = \int \tilde \phi \, d \bar \gamma.$$ We then handle the difference between $\phi$ and $\tilde \phi$. These two functions differ only outside the set $(D \cup B) \times F_j$. By using the fact $\nu(B^c) \leq \delta$, the majorization property given in Lemma \[lem-su-mp\], and the bounds $\gamma_n(\Gamma_j^c) \leq \epsilon$, $\bar \gamma(\Gamma_j^c) \leq \epsilon$ from Step 1, we can calculate that $$\limsup_{n \to \infty} \left| \int_{\X \times \A} ( \phi - \tilde \phi ) \, d \gamma_n  \right| \leq 2 \|h\|_\infty \cdot (\delta +\epsilon), \qquad \ \ \left| \int_{\X \times \A} ( \phi - \tilde \phi ) \, d \bar \gamma  \right| \leq 2 \|h\|_\infty \cdot (\delta +\epsilon).$$

3.  Finally, putting all the pieces together gives us the bound $$\limsup_{n \to \infty} \left| \int  \phi  \, d \gamma_n  -  \int \phi \, d \bar \gamma  \right| \leq 4 \|h\|_\infty \cdot (\delta +\epsilon).$$ By letting $\ell \to \infty$ so that $\delta, \epsilon \to 0$, the desired relation (\[eq-lemdp-prf2\]) follows.

The lemma now follows from (\[eq-lemdp-prf1\])-(\[eq-lemdp-prf2\]), as discussed earlier.

By Lemma \[lem-sp-subv\], $\big((1,\m0), \, \urho \big) = \big(\L \bar \gamma, \, \langle \bar \gamma, \, c \rangle + \bar r \big)$ for $\bar r = \urho - \langle \bar \gamma, \, c \rangle  \geq 0$. Thus $\big((1,\m0), \, \urho \big) \in H$ and consequently, $\urho=\rho^*$. This completes the proof of Theorem \[thm-1\].

### Proof of Prop. \[prp-2\]

The proof is similar to that of [@HL99 Chap. 12.4B, Thm. 12.4.2(c)]. Suppose we have shown that $$\label{eq-prp2-prf1}
   \rho^* + h^*(x) \leq c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma,$$ and suppose also that $$\label{eq-prp2-prf2}
     \int | h^*|  \, d p^* < \infty.$$ Then, since $(\mu^*, p^*)$ is a stationary minimum pair, we have $$\begin{aligned}
 \rho^* & = \int_\X \int_\A c(x,a) \, \mu^*(da \mid x) \, p^*(dx),   \\
  - \infty < \int_\X h^*(x) \, d p^* & = \int_\X \int_\A \int_\X h^*(y) \, q(dy \mid x, a) \, \mu^*(da \mid x) \, p^*(dx) < + \infty,
 \end{aligned}$$ and hence $$\int_\X \int_\A \left\{ \rho^* + h^*(x) - c(x,a) - \int_\X h^*(y) \, q(dy \mid x, a) \right\} \, \mu^*(da \mid x) \, p^*(dx) = 0.$$ This together with (\[eq-prp2-prf1\]) implies that for $p^*\!$-almost all $x \in \X$, $$\rho^* + h^*(x) - \int_\A \left\{ c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\} \, \mu^*(da \mid x) = 0,$$ which in turn implies that for $p^*\!$-almost all $x \in \X$, $$\begin{aligned}
   \rho^* + h^*(x) & = \int_\A \left\{ c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\} \, \mu^*(da \mid x) \notag \\
       & \geq \inf_{a \in A(x)} \left\{ c(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}. \label{eq-prp2-prf3}\end{aligned}$$ Then, by (\[eq-prp2-prf1\]), equality must hold in (\[eq-prp2-prf3\]), and this gives the desired ACOE (\[eq-ae-acoe\]) and (\[eq-ae-acoe2\]).

We now verify that in the two cases given in the proposition, (\[eq-prp2-prf1\]) and (\[eq-prp2-prf2\]) hold. In both cases, (\[eq-prp2-prf2\]) holds by assumption. Regarding (\[eq-prp2-prf1\]), since $\{(\rho_n, h_n)\}$ is a maximizing sequence of (), $\rho_n \uparrow \rho^*$ by Theorem \[thm-1\], and for all $n \geq 0$, $$\label{eq-prp2-prf4}
  \rho_n + h_n(x) \leq c(x,a) + \int_\X h_n(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma.$$ Then, in case (i), for each $(x,a) \in \Gamma$, the assumption $\int_\X \sup_n h_n(x) \, q(dy \,|\, x, a) < + \infty$ implies that $$\label{eq-prp2-prf5}
  \limsup_{n \to \infty} \int_\X h_n (x) \, q(dy \mid x, a) \leq \int_\X \limsup_{n \to \infty} h_n (x) \, q(dy \mid x, a)$$ by Fatou’s lemma. Letting $n \to \infty$ and taking limit superior on both sides of (\[eq-prp2-prf4\]), we obtain (\[eq-prp2-prf1\]). Likewise, in case (ii), since $\sup_{n \geq 0} |h_n| \leq \ell \tilde w$ for some constant $\ell > 0$ and $\int_\X \tilde w(y) \, q(dy \,|\, x, a) < + \infty$ for all $(x, a) \in \Gamma$, we also have (\[eq-prp2-prf5\]) by Fatou’s lemma. The relation (\[eq-prp2-prf1\]) then follows by letting $n \to \infty$ in (\[eq-prp2-prf4\]), as in case (i). This completes the proof of Prop. \[prp-2\].

Proofs for Section \[sec-4\] {#sec-4.3}
----------------------------

### Proof of Theorem \[thm-4.1\] (Outline)

The proof of Theorem \[thm-4.1\] is similar to that of Theorem \[thm-2.1\] on the property of stationary pairs and the existence of a stationary minimum pair for an unconstrained MDP. The latter proof is given in our prior work [@Yu19-minp Sect. 4.1, proofs of Prop. 3.2 and Thm. 3.3], and some of the main arguments we have also mentioned earlier in the proof of Lemma \[lem-sp-subv\]. Therefore, to avoid repetition, we will only outline the proof of Theorem \[thm-4.1\] below. We will first state some results we obtained previously in the unconstrained MDP context, and we will then directly apply those results to the present case of constrained MDPs.

In [@Yu19-minp], given a policy and initial distribution pair $(\pi, \zeta)$ with $J(\pi, \zeta) < \infty$, we consider the occupancy measures of the policy $\pi$: $$\label{eq-thm4.1-prf0}
 \gamma_n(B) : = \tfrac{1}{n} \, \textstyle{\sum_{k=1}^n} \, \Pr^\pi_\zeta \big\{ (x_k, a_k) \in B \big\}, \qquad B \in \B(\Gamma).$$ Under the strict unboundedness condition in Assumption \[cond-pc-3\](SU), $\{\gamma_n\}$ is tight, so from any subsequence of $\{\gamma_{n}\}$, we can extract a further subsequence $\{\gamma_{n_k}\}$ with $\gamma_{n_k} \wto \bar \gamma \in \P(\Gamma)$. It is then proved in [@Yu19-minp Sect. 4.1] that under the majorization condition (M) and the strict unboundedness condition (SU) in Assumption \[cond-pc-3\], the limiting probability measure $\bar \gamma$ has the following properties:

-   $\bar \gamma$ corresponds to a stationary pair $(\bar \mu, \bar p)$; i.e., $\bar \gamma (d(x,a)) = \bar \mu(da \,|\, x) \, \bar p(dx)$ and $\bar p$ is the invariant distribution of the Markov chain induced by the stationary policy $\bar \mu$ on $\X$.

-   The average cost of the pair $(\bar \mu, \bar p)$ satisfies $$\label{eq-thm4.1-prf1}
      J(\bar \mu, \bar p) = \langle \bar \gamma, \, c \rangle \leq \liminf_{k \to \infty} \, \langle \gamma_{n_k}, \, c \rangle.$$

Similarly, in [@Yu19-minp], when proving the existence of a stationary minimum pair, we start with a sequence of stationary pairs $(\mu_n, p_n)$ with $J(\mu_n, p_n) \downarrow \rho^*$, and instead of the occupancy measures in (\[eq-thm4.1-prf0\]), we define $\gamma_n$ to be $$\label{eq-thm4.1-prf2}
   \gamma_n (d(x,a)) : = \mu_n(da \,|\, x) \, p_n(dx).$$ We then proceed similarly to the above case to extract a weakly convergent subsequence of $\{\gamma_n\}$ and prove that the limiting probability measure $\bar \gamma$ has the same properties (a)-(b) as given above.

We now explain how we can apply these results to prove Theorem \[thm-4.1\] for the constrained MDP. To prove Theorem \[thm-4.1\](i), we consider $\{\gamma_n\}$ defined by (\[eq-thm4.1-prf0\]) for a pair $(\pi, \zeta) \in \S$. By the feasibility of $(\pi, \zeta)$, its average costs are all finite: $$J_i(\pi,\zeta) = \limsup_{n \to \infty} \, \langle \gamma_n, \, c_i \rangle  < \infty, \qquad \forall \, i = 0, 1, \ldots, d.$$ Since at least one of the one-stage cost functions $c_0, c_1, \ldots, c_d$ is strictly unbounded by Assumption \[cond-su-cmdp\](SU), this implies that $\{\gamma_n\}$ is a tight family of probability measures. We then proceed as discussed above to obtain the limiting probability measure $\bar \gamma$ from a weakly convergent subsequence $\{\gamma_{n_k}\}$ of $\{\gamma_n\}$.

Next, using the majorization condition in Assumption \[cond-su-cmdp\](M), together with Assumption \[cond-su-cmdp\](SU), it follows as before that $\bar \gamma$ has the property (a) and gives us a stationary pair $(\bar \mu, \bar p)$. Moreover, since Assumption \[cond-su-cmdp\](M) is the same as Assumption \[cond-pc-3\](M) holding for every one-stage cost function $c_i$ in the constrained MDP, (\[eq-thm4.1-prf1\]) in the property (b) above now holds with the function $c$ replaced by every $c_i$; that is $$J_i(\bar \mu, \bar p) = \langle \bar \gamma, \, c_i \rangle \leq \liminf_{k \to \infty} \, \langle \gamma_{n_k}, \, c_i \rangle, \qquad \forall \, i = 0, 1, \ldots, d.$$ Then, since $J_i(\pi, \zeta) = \limsup_{n \to \infty} \langle \gamma_{n}, \, c_i \rangle \geq \liminf_{k \to \infty} \, \langle \gamma_{n_k}, \, c_i \rangle$, it follows that $$J_i(\bar \mu, \bar p) \leq J_i(\pi, \zeta), \qquad \forall \, i = 0, 1, \ldots, d.$$ This proves Theorem \[thm-4.1\](i).

To prove Theorem \[thm-4.1\](ii), which asserts the existence of a stationary optimal pair, we consider a sequence of stationary pairs $(\mu_n, p_n) \in \S$ with $J_0(\mu_n, p_n) \downarrow \rho_c^*$ (there exists such a sequence by the part (i) just proved). Let $\gamma_n$ be defined as in (\[eq-thm4.1-prf2\]). Then, since $J_i(\mu_n, p_n) = \langle \gamma_n, \, c_i \rangle$ for all $0 \leq i \leq d$, we have $$\sup_{n \geq 0} \, \langle \gamma_n, \, c_i \rangle < \infty, \qquad   \forall \, i = 0, 1, \ldots, d.$$ Since one of the one-stage cost functions $c_i$ is strictly unbounded under our assumption, as in the proof of the part (i), we can extract a convergent subsequence $\{\gamma_{n_k}\}$ of $\{ \gamma_n\}$. Then from its limiting probability measure $\gamma^*$, we can obtain a stationary pair $(\mu^*, p^*)$ such that for all $i = 0, 1, \ldots, d$, $$\label{eq-thm4.1-prf3}
 J_i(\mu^*, p^*) = \langle \gamma^*, \, c_i \rangle \leq \liminf_{k \to \infty} \, \langle \gamma_{n_k}, \, c_i \rangle.$$ Since $\langle \gamma_{n_k}, \, c_i \rangle =J_i(\mu_{n_k}, p_{n_k})$, this implies that $$J_0(\mu^*, p^*) \leq \rho_c^*, \qquad J_i(\mu^*, p^*) \leq \kappa_i, \qquad \forall \,  i = 1, 2, \ldots, d,$$ and hence $(\mu^*, p^*)$ is a stationary optimal pair for the constrained MDP.

We now prove Theorem \[thm-4.1\](iii), which asserts the existence of a stationary lexicographically optimal pair. First, let us define recursively sets $\S^*_i$ and scalars $\kappa^*_i$ as follows: Let $$\kappa^*_0 = \rho_c^*, \qquad \S^*_0 = \big\{ (\pi, \zeta) \in \S \mid J_0(\pi, \zeta) = \rho_c^* \big\},$$ and for $1 \leq i \leq d$, let $$\kappa^*_i = \inf \big\{ J_i(\pi, \zeta) \, \big| \,  (\pi, \zeta) \in \S^*_{i-1} \big\}, \qquad  \S^*_i = \big\{ (\pi, \zeta) \in \S^*_{i-1} \mid J_i(\pi, \zeta) = \kappa^*_i \big\}.$$ The set $\S^*_d$ consists of all the lexicographically optimal pairs, so to prove Theorem \[thm-4.1\](iii), we need to show $\Delta_s \cap \S^*_d \not=\emptyset$. By Theorem \[thm-4.1\](ii) just proved, $\Delta_s \cap \S^*_0 \not= \emptyset$. Let us prove by induction that $\Delta_s \cap \S^*_i \not= \emptyset$ for all $i \leq d$.

Assume that for some $j \leq d$, $\S^*_{j-1} \not= \emptyset$. Then $\kappa^*_j$ is well-defined, and there exists a sequence of policy and initial distribution pairs $(\pi_n, \zeta_n) \in \S^*_{j-1}$ with $$J_j(\pi_n, \zeta_n) \downarrow \kappa^*_j.$$ By Theorem \[thm-4.1\](i) proved earlier, for each $(\pi_n, \zeta_n)$, there is a stationary pair $(\mu_n, p_n)$ with $$J_i( \mu_n, p_n) \leq J_i(\pi_n, \zeta_n), \qquad \forall \, i = 0, 1, \ldots, d.$$ This together with the fact $(\pi_n, \zeta_n) \in \S^*_{j-1}$ implies that $(\mu_n, p_n) \in \S^*_{j-1}$. Consider now the sequence $\{(\mu_n, p_n)\}$ of stationary pairs thus constructed. Exactly the same proof arguments for establishing the part (ii) can be applied here, and they yield that there exists a stationary pair $(\mu^*, p^*)$ that satisfies (\[eq-thm4.1-prf3\]). Therefore, $$J_i(\mu^*, p^*)  = \kappa_i^*, \qquad i = 0, 1, \ldots, j,$$ and consequently, $(\mu^*, p^*) \in \S^*_j$. This proves that $\Delta_s \cap \S^*_j \not= \emptyset$; then, by induction, $\Delta_s \cap \S^*_d \not= \emptyset$. Hence there is a stationary lexicographically optimal pair for the constrained MDP.

This completes the proof of Theorem \[thm-4.1\].

### Proof of Theorem \[thm-4.2\] (Outline)

The consistency and solvability of (P) follow from Theorem \[thm-4.1\](i)-(ii). The consistency of () is trivial (e.g., let $\rho=0, h(\cdot) \equiv0$, $\beta = 0$). Thus, $0 \leq \sup (\Pstar) \leq \inf (\text{P}) = \rho_c^*$.

We now prove the absence of duality gap. This proof is similar to that of Theorem \[thm-1\](ii) for the unconstrained MDP case. Since the value of () is finite, by [@AnN87 Thm. 3.3] (cf. Theorem \[thm-subc\]), the value of () equals the subvalue $\urho$ of (P). Therefore, to prove there is no duality gap is to prove $\urho = \rho_c^*$. For this, it suffices to show $$\big((1, \m0, \kappa), \urho \big) \in H,$$ where the set $H$ is as defined in (\[eq-H\]) and, for the case here, is given by $$H : = \big\{ \big(L (\gamma, \alpha), \, \langle \, \gamma, \, c_0 \, \rangle + r \big) \, \big| \, \gamma \in \Me_w^+(\Gamma), \ \alpha \in \R_+^d, \ r \geq 0 \big\}.$$ Recall that by definition the subvalue $\urho = \inf \big\{ r \mid \big( (1, \m0, \kappa), r \big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu} \big\}$ (cf. Section \[sec-2.2\]).

To prove $\big((1, \m0, \kappa), \urho \big) \in H$, we will construct a stationary pair $(\bar \mu, \bar p) \in \S$ with $J_0(\bar \mu, \bar p) \leq \urho$, and the proof proceeds in four steps as in the proof of Theorem \[thm-1\](ii). Let us outline these steps, explaining briefly some minor changes in the details of the arguments.

[**Step (i):**]{} From the definition of $\urho$, it follows that $\big((1, \m0, \kappa), \urho \big) \in {\mkern 1mu\overline{\mkern-2.7muH\mkern-1.3mu}\mkern 1.5mu}$ and there exist a direct set $\nI$ and a net $\{(\gamma_i, \alpha_i)\}_{i \in \nI}$ in $\Me_w^+(\Gamma) \times \R_+^d$ such that $$\begin{aligned}
    \gamma_i(\Gamma) & \to 1,   \label{eq-thm4.2-prf1} \\
  \int_\X h(x) \, \hat \gamma_i(dx) - \int_{\Gamma} \int_\X h(y) \, q(dy \mid x, a) \, \gamma_i(d(x,a)) & \to 0, \qquad \forall \, h \in \Fn_b(\X),  \label{eq-thm4.2-prf2} \\
\big( \langle \gamma_i, \, c_1 \rangle, \, \cdots, \, \langle \gamma_i, \, c_d \rangle \big) + \alpha_i & \to \kappa,  \label{eq-thm4.2-prf2b} \\
 \langle \, \gamma_i, c_0 \, \rangle & \to \urho.  \label{eq-thm4.2-prf3}\end{aligned}$$ As before, in view of (\[eq-thm4.2-prf1\]) and the fact $\gamma_i \in \Me_w^+(\Gamma)$, by redefining the net $\{(\gamma_i, \alpha_i)\}_{i \in \nI}$ if necessary, we may assume that every $\gamma_i$ in the above is a probability measure on $\B(\Gamma)$.

[**Step (ii):**]{} Similarly to Lemma \[lem-net2seq\], we extract a *sequence* $\{(\gamma_n, \alpha_n)\}_{n \geq 0} \subset \{(\gamma_i, \alpha_i)\}_{i \in \nI}$ such that $$\begin{aligned}
  \int_\X h(x) \, \hat \gamma_n(dx) - \int_{\Gamma} \int_\X h(y) \, q(dy \mid x, a) \, \gamma_n(d(x,a)) & \to 0, \qquad \forall \, h \in \hat \C_b(\X) \cup \hat \Fn_b(\X),  \label{eq-thm4.2-prf2a} \\
  \big( \langle \gamma_n, \, c_1 \rangle, \, \cdots, \, \langle \gamma_n, \, c_d \rangle \big) + \alpha_n & \to \kappa,  \label{eq-thm4.2-prf2ab} \\
   \langle \, \gamma_n, c_0 \, \rangle  & \to \urho,  \label{eq-thm4.2-prf3a}\end{aligned}$$ where $\hat \C_b(\X)$ and $\hat \Fn_b(\X)$ in (\[eq-thm4.2-prf2a\]) are two chosen *countable* subsets of $\Fn_b(\X)$, the properties of which are needed in the subsequent two steps of our proof. In particular, the set $\hat \C_b(\X)$ is the countable set of bounded continuous functions with the property (\[eq-detclass\]), the same set as defined in the proof of Theorem \[thm-1\](ii). The countable set $\hat \Fn_b(\X)$ is also defined by the equation (\[eq-def-indfn\]) in that proof: $$\hat \Fn_b(\X) : = \big\{ \ind_E(\cdot) \mid  E = (O \setminus D) \cap B^c \ \, \text{for some} \ \, (O, D, \nu, B) \in \W_1 \cup \W_2 \big\}.$$ However, we define the set $\W_1$ slightly differently here, to take into account the multiple one-stage cost functions in the constrained MDP. Specifically, in the definition of $\W_1$ (cf. Lemma \[lem-lusin\] and the definitions preceding this lemma), we make the following changes. We now use the sets and finite measures $(O,D,\nu)$ involved in Assumption \[cond-su-cmdp\](M) instead of Assumption \[cond-pc-3\](M). We choose the sets $B^1_{j,m,\ell}$ for each $j, m, \ell \in \Z_+$ such that besides the property in Lemma \[lem-lusin\](i), we have that restricted to $B^1_{j,m,\ell} \times F_j$, *all* the $(d+1)$ truncated one-stage cost functions, $c_i^m$, $i = 0, 1, \ldots, d$, are continuous (where $c_i^m(\cdot) = \min\{ c_i(\cdot), m\}$). This is possible by Lusin’s theorem (since we have only a finite number of these cost functions, we can apply Lusin’s theorem to each one of them and then combine the results).

[**Step (iii):**]{} This step is the same as before. The relations (\[eq-thm4.2-prf2ab\])-(\[eq-thm4.2-prf3a\]) together with Assumption \[cond-su-cmdp\](SU) imply that $\{\gamma_n\}$ is a tight family of probability measures and therefore has a weakly convergent subsequence $\{\gamma_{n_k}\}$. Consider the corresponding subsequence $\{(\gamma_{n_k}, \alpha_{n_k})\}$; for notational simplicity, we will drop the subscript $k$ by redefining $\{(\gamma_n, \alpha_n)\}$ to be this subsequence. Now, denote the limit of $\{\gamma_n\}$ by $\bar \gamma$, and decompose $\bar \gamma$ as $\bar \gamma(d(x,a)) = \bar \mu(da \,|\, x) \, \bar p(dx)$, where $\bar p$ is the marginal of $\bar \gamma$ on $\X$ and $\bar \mu$ is a stationary policy. Then, using Assumption \[cond-su-cmdp\](M) instead of Assumption \[cond-pc-3\](M), we have that Lemma \[lem-su-mp\] holds as before, which gives us the desired majorization properties for $\hat \gamma_n$ and $\bar \gamma$ that we will need in the next, last step.

[**Step (iv):**]{} This step is almost the same as before, except that we apply those arguments in the proof of (\[eq-lemdp-prf1\]) to *every* cost function $c_i$, $0 \leq i \leq d$, in the present constrained problem. Then, similar to Lemma \[lem-sp-subv\], we obtain that the pair $(\bar \mu, \bar p)$ is a stationary pair and satisfies that $$J_i(\bar \mu, \bar p)  = \langle \bar \gamma, \, c_i \rangle \leq \liminf_{n \to \infty} \, \langle \gamma_{n}, c_i \rangle, \qquad \forall \, i = 0, 1, \ldots, d.$$ Combining this with (\[eq-thm4.2-prf2ab\]) and (\[eq-thm4.2-prf3a\]) (recall also $\alpha_n \geq 0$), we obtain $$J_0(\bar \mu, \bar p) \leq \urho, \qquad J_i(\bar \mu, \bar p) \leq \kappa_i , \qquad \forall \, i = 0, 1, \ldots, d.$$ Therefore, if we let $$\bar r : = \urho - J_0(\bar \mu, \bar p) \geq 0, \qquad \bar \alpha : = \kappa - \big(J_1(\bar \mu, \bar p), \, \ldots, \, J_d(\bar \mu, \bar p) \big) \geq 0,$$ then $$\big((1, \m0, \kappa), \urho \big) = \big( \L( \bar \gamma, \bar \alpha), \, \langle \bar \gamma, \, c_0 \rangle + \bar r \big) \in H.$$ This implies $\urho = \rho^*_c$ (since it implies $\rho^*_c \leq \urho$, whereas $\urho \leq \rho^*_c$). Hence there is no duality gap between (P) and ().

### Proofs of Props. \[prp-4.3\] and \[prp-4.4\]

\(i) Consider any $j \in \J^{(0)}$ and some pair $(\pi, \zeta) \in \S$ with $J_j(\pi, \zeta) < \kappa_j$. By Theorem \[thm-4.1\](i), there exists a stationary pair $(\bar \mu, \bar p) \in \S$ with $J_i(\bar \mu, \bar p) \leq J_i(\pi, \zeta)$ for all $0 \leq i \leq d$. Then $J_j(\bar \mu, \bar p) < \kappa_j$.

Now for each $n \geq 0$, since $(\rho_n, h_n, \beta_n)$ is feasible for (), we have from (\[eq-cmdp-dual-cstr1\])-(\[eq-cmdp-dual-cstr2\]) that $\beta_n \leq 0$ and for all $(x,a) \in \Gamma$, $$\rho_n + h_n(x) \leq c_0(x,a) - \sum_{i=1}^d \beta_{n,i} c_i(x,a) + \int_{\X} h_n(y) \, q(dy \mid x, a),$$ and therefore, by adding $\sum_{i=1}^d \beta_{n,i} \kappa_i$ to both sides, $$\label{eq-prp4.3-prf0}
 \rho_n +  \sum_{i=1}^d \beta_{n,i} \kappa_i + h_n(x) \leq  c_0(x,a) + \sum_{i=1}^d \beta_{n,i} \big( \kappa_i  - c_i(x,a) \big) + \int_{\X} h_n(y) \, q(dy \mid x, a).$$ Integrate both sides of (\[eq-prp4.3-prf0\]) w.r.t. the probability measure $\bar \gamma(d(x,a)) = \bar \mu(da \,|\, x) \, \bar p(dx)$. Notice that $\int h_n \, d \bar p = \int_{\Gamma} \int_{\X} h_n(y) \, q(dy \,|\, x, a) \, \bar \gamma(d(x,a))$ since $(\bar \mu, \bar p)$ is a stationary pair. We thus obtain $$\rho_n + \sum_{i=1}^d \beta_{n,i} \kappa_i \leq J_0(\bar \mu, \bar p) + \sum_{i=1}^d \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big). \label{eq-prp4.3-prf0a}$$ Take $n \to \infty$. Since $\{(\rho_n, h_n, \beta_n)\}$ is a maximizing sequence for (), $\rho_n +  \sum_{i=1}^d \beta_{n,i} \kappa_i \to \rho^*_c$ by Theorem \[thm-4.2\](ii). It then follows from (\[eq-prp4.3-prf0a\]) that $$\begin{aligned}
    \rho_c^* - J_0(\bar \mu, \bar p) & \leq \liminf_{n \to \infty} \, \sum_{i=1}^d \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big) \label{eq-prp4.3-prf1} \\
       &  \leq \liminf_{n \to \infty}  \, \beta_{n,j} \big( \kappa_j - J_j(\bar \mu, \bar p) \big), \label{eq-prp4.3-prf2}\end{aligned}$$ where we used the fact $ \kappa_i - J_i(\bar \mu, \bar p) \geq 0$ and $\beta_{n,i} \leq 0$ for all $i$ to derive (\[eq-prp4.3-prf2\]). Since $\kappa_j - J_j(\bar \mu, \bar p) > 0$, (\[eq-prp4.3-prf2\]) implies $\liminf_{n \to \infty} \beta_{n,j} > - \infty$. Hence the sequence $\{\beta_{n,j}\}_{n \geq 0}$ is bounded.

\(ii) In this case, suppose $j$ is such that $J_j(\mu^*, p^*) < \kappa_j$. Then $j \in \J^{(0)}$ and (\[eq-prp4.3-prf2\]) holds with $(\bar \mu, \bar p) = (\mu^*, p^*)$ and with its left-hand side equal to $\rho_c^* - J_0(\mu^*, p^*) = 0$. This yields $\lim_{n \to \infty} \beta_{n,j} = 0$.

\(iii) In this case, by assumption there is some pair $(\bar \pi, \bar \zeta) \in \Pi \times \P(\X)$ satisfying $$J_j(\bar \pi, \bar \zeta) < \kappa_j \quad \forall \, j \in \J^{(1)}, \qquad J_j(\bar \pi, \bar \zeta) < \infty \quad \forall \, j \in \J^{(0)} \cup \{ 0\}.$$ As in part (i), let us consider a stationary pair $(\bar \mu, \bar p)$ with $J_i(\bar \mu, \bar p) \leq J_i(\bar \pi, \bar \zeta)$ for all $0 \leq i \leq d$. Such a pair exists by Theorem \[thm-4.1\](i), since we can apply this theorem with a different feasible set $\S'$ instead of $\S$ and in $\S'$ we can use $J_i(\bar \pi, \bar \zeta)$ as the upper limits on the average costs w.r.t. $c_i$ for $1 \leq i \leq d$, for instance.

The average costs of this stationary pair $(\bar \mu, \bar p)$ thus satisfy $$J_j(\bar \mu, \bar p) < \kappa_j \quad \forall \, j \in \J^{(1)}, \qquad J_j(\bar \mu, \bar p) < \infty \quad \forall \, j \in \J^{(0)} \cup \{ 0\}. \label{eq-prp4.3-prf3}$$ We also have, as in part (i), that (\[eq-prp4.3-prf1\]) holds for this pair $(\bar \mu, \bar p)$. Now, as we proved in part (i), $\{\beta_{n,i}\}_{n \geq 0}$ is bounded for every $i \in \J^{(0)}$. This together with the second relation in (\[eq-prp4.3-prf3\]) implies that the term $$\limsup_{n \to \infty} \sum_{ i \in \J^{(0)}} \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big)$$ is finite. From (\[eq-prp4.3-prf1\]), we have the inequality $$\begin{aligned}
  \rho_c^* - J_0(\bar \mu, \bar p) & \leq \liminf_{n \to \infty} \, \sum_{i=1}^d \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big) \notag \\
        & \leq   \limsup_{n \to \infty} \sum_{ i \in \J^{(0)}} \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big)  + \, \liminf_{n \to \infty} \sum_{ i \in \J^{(1)}} \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big). \label{eq-prp4.3-prf4}\end{aligned}$$ In (\[eq-prp4.3-prf4\]), since the term on the left-hand side and the first term on the right-hand side are both finite, the second term on the right-hand side must satisfy $$\liminf_{n \to \infty} \sum_{ i \in \J^{(1)}} \beta_{n,i} \big( \kappa_i - J_i(\bar \mu, \bar p) \big) > - \infty.$$ Then, since $\beta_n \leq 0$, in view of the first relation in (\[eq-prp4.3-prf3\]), the preceding inequality implies that $\{\beta_{n,i}\}_{n \geq 0}$ must be bounded for every $i \in \J^{(1)}$. Combining this with the result of part (i), we obtain that for every $i = 1, 2, \ldots, d$, the sequence $\{\beta_{n,i}\}_{n \geq 0}$ is bounded. Hence $\{\beta_n\}$ is bounded.

The proof arguments are similar to those of [@HGL03 Thm. 5.2(b)] for constrained MDPs and those of Prop. \[prp-2\] for unconstrained MDPs. By the inequality (\[eq-prp4.3-prf0\]), for each $n \geq 0$, $$\quad \rho_n +  \sum_{i=1}^d \beta_{n,i} \kappa_i + h_n(x) \leq  c_0(x,a) + \sum_{i=1}^d \beta_{n,i} \big( \kappa_i  - c_i(x,a) \big) + \int_{\X} h_n(y) \, q(dy \mid x, a), \ \ \  \forall \, (x,a) \in \Gamma.$$ Let $n \to \infty$. Since $\rho_n + \sum_{i=1}^d \beta_{n,i} \kappa_i \to \rho_c^*$ by Theorem \[thm-4.2\](ii) and $\beta_n \to \beta^* \leq 0$ by assumption, we obtain $$\rho_c^* + \limsup_{n \to \infty} h_n(x) \leq c_0(x,a) +  \sum_{i=1}^d \beta^*_{i} \big( \kappa_i  - c_i(x,a) \big) + \limsup_{n \to \infty} \int_{\X} h_n(y) \, q(dy \mid x, a), \ \ \ \forall \, (x,a) \in \Gamma.$$ This implies the desired inequality (\[eq-cmdp-dsol\]) if it is true that $$\label{eq-prp4.4-prf1}
  \limsup_{n \to \infty} \int_{\X} h_n(y) \, q(dy \mid x, a) \leq \int_{\X} \limsup_{n \to \infty}  h_n(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma.$$ Now, in either one of the two cases of $\{h_n\}$ in the proposition, the inequality (\[eq-prp4.4-prf1\]) follows from Fatou’s Lemma (cf. the proof of Prop. \[prp-2\]). Therefore, the inequality (\[eq-cmdp-dsol\]) is proved; i.e., $$\label{eq-prp4.4-prf2}
  \rho^*_c + h^*(x) \leq c_0(x,a) + \sum_{i=1}^d \beta^*_{i} \big( \kappa_i  - c_i(x,a) \big) +  \int_\X h^*(y) \, q(dy \mid x, a), \qquad \forall \, (x,a) \in \Gamma.$$

Next, integrate both sides of (\[eq-prp4.4-prf2\]) w.r.t. the probability measure $\gamma^*(d(x,a)) = \mu^*(da \,|\, x) \, p^*(dx)$, where the integrability is ensured by our assumption $\int |h^*| \, d p^* < \infty$ together with the invariance property of $p^*$, as in the proof of Prop. \[prp-2\]. Then, similarly to the derivation of (\[eq-prp4.3-prf0a\]) in the proof of Prop. \[prp-4.3\](i), we obtain that $$\rho_c^* \leq J_0(\mu^*, p^*) + \sum_{i=1}^d \beta^*_{i} \big( \kappa_i - J_i(\mu^*, p^*) \big).$$ Since $J_0(\mu^*, p^*) = \rho_c^*$ and the second term in the right-hand side above is nonpositive, equality must hold in the above inequality, and this result can be equivalently expressed as $$\int_\X \int_\A \left\{  \rho^*_c + h^*(x) - c_0(x,a) - \sum_{i=1}^d \beta^*_{i} \big( \kappa_i  - c_i(x,a) \big) -  \int_\X h^*(y) \, q(dy \mid x, a) \right\} \mu^*(da \mid x) \, p^*(dx) = 0.$$ Similarly to the proof of Prop. \[prp-2\], the preceding equality together with the inequality (\[eq-prp4.4-prf2\]) implies that for $p^*\!$-almost all $x \in \X$, $$\begin{aligned}
 \rho^*_c - \sum_{i=1}^d \beta^*_{i} \kappa_i +  h^*(x) & = \int_{a \in A(x)} \left\{ c_0(x,a) - \sum_{i=1}^d \beta^*_{i}  c_i(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\} \mu^*(da \mid x) \\
 & = \inf_{a \in A(x)} \left\{ c_0(x,a) - \sum_{i=1}^d \beta^*_{i}  c_i(x,a) + \int_\X h^*(y) \, q(dy \mid x, a) \right\}.\end{aligned}$$ This gives the desired ACOE (\[eq-cmdp-ae-acoe\]) and (\[eq-cmdp-ae-acoe2\]).

Acknowledgments {#acknowledgments .unnumbered}
===============

The author would like to thank Professor Eugene Feinberg for helpful discussion. This research was supported by grants from DeepMind and Alberta Innovates—Technology Futures.

[^1]: RLAI Lab, Department of Computing Science, University of Alberta, Canada (`janey.hzyu@gmail.com`)
