{'fraction_non_alphanumeric': 0.07266339591103957, 'fraction_numerical': 0.01914475415164131, 'mean_word_length': 3.837463502283447, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Average Cost Optimality Inequality for Markov Decision Processes with Borel Spaces and Universally Measurable Policies

We consider average-cost Markov decision processes (MDPs) with Borel state and action spaces and universally measurable policies. For the nonnegative cost model and an unbounded cost model with a Lyapunov-type stability character, we introduce a set of new conditions under which we prove the average cost optimality inequality (ACOI) via the vanishing discount factor approach. Unlike most existing results on the ACOI, our result does not require any compactness and continuity conditions on the MDPs. Instead, the main idea is to use the almost-uniform-convergence property of a pointwise convergent sequence of measurable functions as asserted in Egoroff's theorem. Our conditions are formulated in order to exploit this property. Among others, we require that for each state, on selected subsets of actions at that state, the state transition stochastic kernel is majorized by finite measures. We combine this majorization property of the transition kernel with Egoroff's theorem to prove the ACOI.


Introduction
We consider discrete-time Markov decision processes (MDPs) with Borel state and action spaces, under the average cost criterion where the objective is to minimize the (limsup) expected long-run average cost per unit time. Specifically, we consider the universal measurability framework, which involves lower semi-analytic (l.s.a.) one-stage cost functions and universally measurable (u.m.) policies. It is a mathematical formulation of MDPs developed to resolve measurability difficulties in dynamic programming on Borel spaces [4,5,37,38,39,41]. An in-depth study of this theoretical framework is given in the monograph [3,Part II], and optimality properties of finite-and infinitehorizon problems with discounted and undiscounted total cost criteria have been analyzed (see e.g., [3,Part II] and [26,47,50]). The average cost problem has not been thoroughly studied in this framework, however; there are only a few prior results (which we will discuss below). The primary purpose of this paper is to investigate the subject further, and our central focus will be on the average cost optimality inequality (ACOI).
The study of ACOI was initiated by Sennott [36], who proved it for countable-space MDPs; prior to [36], the ACOE (average cost optimality equation) was the research focus. Cavazos-Cadena's counterexample [6] showed that the ACOI is more general: in his example, the ACOI has a solution and yet the ACOE does not. For Borel-space MDPs, the ACOI was first established by Schäl [35] for one-stage costs that are bounded below and under, alternatively, two types of compactness and continuity conditions. Specifically, the first (resp. second) case requires that the state transition stochastic kernel is continuous with respect to (w.r.t.) setwise convergence (resp. weak convergence) and the one-stage cost function lower semicontinuous (l.s.c.) in the action variable (resp. the state and action variables). The compactness conditions on the action sets in [35] were weakened by Hernández-Lerma [18] (to inf-compactness for the first case) and by Feinberg, Kasyanov, and Zadoianchuk [13] (to K-inf-compactness for the second case; a similar, slightly stronger condition was proposed by Costa and Dufour [8] independently). Extensions of these results to unbounded one-stage costs and to ACOEs have also been studied; see the textbook accounts given in Hernández-Lerma and Lasserre [20,Chap. 10] and for more recent advances, see Vega-Amaya [43,44,45], Jaśkiewicz and Nowak [23], Feinberg et al. [12,15] and the references therein. (For related earlier researches, see also the survey by Arapostathis et al. [1].) In this paper, we prove the ACOI for two types of MDPs in the universal measurability framework: the nonnegative cost model and an unbounded cost model with a Lyapunov-type stability property. These models have been studied in the references just mentioned. As in some of those studies, to prove the ACOI, we use the vanishing discount factor approach, which treats the average cost problem as the limiting case of the discounted problems, and we adopt some boundedness conditions formulated in [13,20,35] regarding the optimal value functions of the discounted problems.
Different from those studies, however, our results require no compactness and continuity conditions on the one-stage cost function and state transition stochastic kernel. Instead, we introduce a set of new conditions of, what we call, the majorization type: among others, we require that for each state, on selected subsets of actions at that state, the state transition stochastic kernel is majorized by finite measures (see Assumptions 3.3,3.12). Our main idea is to combine these majorization properties with Egoroff's theorem, which asserts that pointwise convergence of functions is "almost" uniform convergence as measured by a given finite measure (cf. Footnote 8), and which allows us to extract arbitrarily large sets (large as measured by the majorizing finite measures) on which certain functions involved in our analyses have desired uniform convergence properties. With this technique, we obtain the ACOI for the two MDP models mentioned above (see Theorems 3.5,3.13). These results can be applied to a class of MDPs with discontinuous dynamics and one-stage costs.
For comparison, let us discuss several prior researches relevant to average-cost MDPs with u.m. policies. Dynkin and Yushkevich [10,Chap. 7.9] and Piunovskiy [31] studied the characteristic properties of canonical systems-a general form of the ACOE together with stationary policies that solve or almost solve the ACOE. ( [10,Chap. 7.9] considers an abstract model with desired measurable structures; [31] considers the universal measurability framework.) Gubenko and Shtatland used a contraction-based fixed point approach to prove the ACOE under, alternatively, a minorization condition and a majorization on the state transition stochastic kernel [17, Theorems 2, 2 ′ ] (measurability issues are assumed away in these theorems). Their majorization condition not only differs in essential ways from ours but is also too stringent to be practical (see Remark 3.4 for details). But their approach with the minorizaton condition is a fruitful one and has close connections with ergodic theory for Markov chains; in particular, their minorization condition implies that the MDP is uniformly geometrically ergodic (cf. Section 4.2). Their contraction argument was extended by Kurano [25] to a multistep-contraction argument for average-cost MDPs with u.m. policies. The main results of [17,25] on the ACOE concern the case of bounded one-stage costs.
For unbounded one-stage costs, a contraction-based fixed point approach to proving the ACOE was proposed more recently. It was originally formulated by Vega-Amaya [43], building on the result of Hernández-Lerma and Lasserre on positive Harris recurrent Markov chains, as well as on the prior research of Gordienko and Hernández-Lerma [16], which relates a class of MDPs with unbounded onestage costs to w-geometrically ergodic Markov chains. In [43] (also the recent work [45]), this fixed point approach is applied to MDPs with continuity/compactness properties. The approach was taken by Jaśkiewicz [22] to establish the ACOE for semi-Markovian decision processes (SMDPs) in the universal measurability framework. The conditions of [22,43] generalize the minorization condition of [17], and the ACOE results of [22,43] are applicable to a class of MDPs that are uniformly w-geometrically ergodic w.r.t. certain weight functions w on the state spaces (cf. the discussion in Section 4.3).
Meyn [28] studied the convergence of policy iteration for average-cost MDPs. He obtained the ACOE and the existence of an average-cost optimal stationary policy, under a set of conditions on the Markov chains induced by stationary policies that could be generated by the policy iteration algorithm, together with a continuity condition on the differential cost functions of those policies and the one-stage cost function. A large part of his analysis is based on general state-space Markov chain theory and requires no compactness/continuity conditions. However, it does not directly apply to Borel-space MDPs in the universal measurability framework due to known measurability issues in policy iteration. It is still an open problem to extend the method of [28] to average-cost MDPs with u.m. policies.
We remark that these prior studies differ significantly from our work in both the approaches taken and the results obtained. When compactness/continuity conditions are absent, a major tool used in many of those studies is ergodic theory for Markov chains, whereas, by exploiting Egoroff's theorem, our analyses and results can be applied to non-ergodic MDPs (cf. the examples in Section 4 and Appendix A.3).
Let us also mention two related results from our separate recent work. In [49], we formulated another condition of the majorization type to make use of Lusin's theorem when applying a direct method, the minimum pair approach, to study the average cost problems; this result is for countable discrete action spaces and strictly unbounded one-stage costs. In [48,Sec. 2.2] (see also Theorem 2.2), for the two MDP models considered in this paper, we gave a characterization of the structures of the optimal cost functions and optimal/ǫ-optimal policies in the average cost problems, without any extra conditions. The rest of this paper is organized as follows. In Section 2, we give background materials about Borel-space MDPs. In Section 3, we propose new majorization type conditions and prove the ACOI for two MDP models. Further discussion and illustrative examples are given in Section 4 and Appendix A.

Preliminaries
In this section, we first introduce Borel-space MDPs in the universal measurability framework. To prepare the stage for subsequent analyses, we then review several basic optimality properties for the nonnegative cost and unbounded cost models we consider, under the average and discounted cost criteria. We start with certain sets and functions that lie at the foundation of Borel-space MDPs.

Definitions of some Sets and Functions
We consider separable metrizable spaces. 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 [3,Def. 7.7]. For a Borel space X, let B(X) denote the Borel σ-algebra and P(X) the set of probability measures on B(X) (we will call them Borel probability measures). With the topology of weak convergence, P(X) is also a Borel space [3,Chap. 7.4]. Each p ∈ P(X) has a unique extension on a larger σ-algebra B p (X) generated by B(X) and all the subsets of X with p-outer measure 0, and this extension is called the completion of p (cf. [9,Chap. 3.3]). The universal σ-algebra on X is defined as U(X) := ∩ p∈P(X) B p (X). U(X)-measurable functions on X are thus measurable w.r.t. the completion of any Borel probability measure; these functions are called u.m. (universally measurable).
If X and Y are Borel spaces, a Borel or u.m. stochastic kernel on Y given X is a function q : X → P(Y ) that is measurable from the space X, B(X) or X, U(X) , respectively, to the space P(Y ), B(P(Y )) ; see [3,Def. 7.12,Prop. 7.26,Lemma 7.28]. We use the notation q(dy | x) for the stochastic kernel. When q is a continuous function, we say the stochastic kernel is continuous (a.k.a. weakly continuous or weak Feller in the literature).
An analytic set in a Polish space is the image of a Borel subset of some Polish space under a Borel measurable function (cf. [3,Prop. 7.41], [9,Sec. 13 is called l.s.a. (lower semi-analytic), if D is an analytic set and for every a ∈ R, the level set {x ∈ D | f (x) ≤ a} of f is analytic [3,Def. 7.21]. An equivalent definition is that the epigraph of f , {(x, a) | x ∈ D, f (x) ≤ a, a ∈ R}, is analytic (cf. [3, p. 186]). For comparison, f is l.s.c. (lower semicontinuous) if its epigraph is closed. A Borel measurable extended-real-valued function on a Borel space is l.s.a. and an l.s.a. function is u.m., since in a Polish space every Borel set is analytic and every analytic set is u.m. ([3, Cor. 7.42.1], [9,Thm. 13.2.6]).
The properties of analytic sets give rise to many properties of l.s.a. functions that are important for dynamic programming in Borel-space MDPs. The most critical is the Jankov-von Neumann measurable selection theorem [3,Prop. 7.49], which asserts that for an analytic set D in the product space X × Y of two Borel spaces, with proj X (D) being the projection of D on X, there exists an analytically measurable 1 function φ : proj X (D) → Y such that the graph of φ lies in D. This theorem gives rise to a measurable selection theorem for partial minimization of l.s.a. functions on product spaces [3,Prop. 7.50]. For Borel-space MDPs, these properties of analytic sets and l.s.a. functions are closely related to the validity of value iteration, the structure of the optimal value functions, and the existence of optimal or nearly optimal policies and their structures, some of which we will discuss in Sections 2.2-2.3. Due to space limit, however, we do not list these properties and will provide references where we use them in this paper. 2

Borel-space MDPs
In the universal measurability framework, a Borel-space MDP has the following elements and model assumptions (cf. [3, Chap. 8.1]): • The state space X and the action space A are Borel spaces.
• The control constraint is specified by a set-valued map A : x → A(x), where for each state x ∈ X, A(x) ⊂ A is a nonempty set of admissible actions at that state, and the graph of A(·), • State transitions are governed by q(dy | x, a), a Borel measurable stochastic kernel on X given X × A.
We consider infinite-horizon control problems. A policy consists of a sequence of stochastic kernels on A that specify for each stage, which admissible actions to apply, given the history up to that stage. In particular, a u.m. policy is a sequence π = (µ 0 , µ 1 , . . .), where for each k ≥ 0, µ k da k | x 0 , a 0 , . . . , a k−1 , x k is a u.m. stochastic kernel on A given (X × A) k × X and obeys the control constraint of the MDP: (2.1) (As Γ is analytic, the sets A(x) are u.m. [3,Lemma 7.29]; the probability of A(x k ) here is measured w.r.t. the completion of µ k (da k | x 0 , a 0 , . . . , a k−1 , x k ).) A policy π is Borel measurable if each component µ k is a Borel measurable stochastic kernel; π is then also u.m. by definition. (A Borel measurable policy, however, may not exist [4].) We define the policy space Π of the MDP to be the set of u.m. policies. We shall simply refer to these policies as policies, dropping the term "u.m.," if there is no confusion or no need to emphasize their measurability. We define several subclasses of policies in the standard way. A policy π is nonrandomized if µ k da k | x 0 , a 0 , . . . , a k−1 , x k is a Dirac measure that assigns probability one to a single action in A(x k ), for every (x 0 , a 0 , . . . , a k−1 , x k ) and k ≥ 0. A policy π is semi-Markov if for every k ≥ 0, the function (x 0 , a 0 , . . . , a k−1 , x k ) → µ k (da k | x 0 , a 0 , . . . , a k−1 , x k ) depends only on (x 0 , x k ); Markov if for every k ≥ 0, that function depends only on x k ; stationary if π is Markov and µ k = µ for all k ≥ 0. For the stationary case, we simply write µ for π = (µ, µ, . . .). A nonrandomized stationary policy µ can also be viewed as a function that maps each x ∈ X to an action in A(x), so for such µ, we will use both notations µ(x), µ(da | x) in the paper.
Because the graph Γ of the control constraint A(·) is analytic, by the Jankov-von Neumann selection theorem [3,Prop. 7.49], there exists at least one u.m. nonrandomized stationary policy. Thus the policy space Π is non-empty.
We consider the average cost criterion and the discounted cost criterion. By [3,Prop. 7.45], given a policy π ∈ Π and an initial state distribution p 0 ∈ P(X), the collection of stochastic kernels µ 0 (da 0 | x 0 ), q(dx 1 | x 0 , a 0 ), µ 1 (da 1 | x 0 , a 0 , x 1 ), q(dx 2 | x 1 , a 1 ), . . . determines uniquely a probability measure on the universal σ-algebra on (X × A) ∞ . The n-stage value function and the average cost function of π are defined, respectively, by 3 where E π x denotes expectation w.r.t. the probability measure induced by π and the initial state x 0 = x. Define the optimal average cost function by For 0 < α < 1, define the α-discounted value function of a policy π by v π α (x) := lim sup x ∈ X, and the optimal α-discounted value function by The functions J n (π, ·), J(π, ·) and v π α (·) are u.m. by [3,Prop. 7.46, Lemma 7.30 (2)]. As will be discussed in the next subsection, for the two MDP models we consider, the optimal cost functions g * and v α are l.s.a.
Let M(X) (resp. A(X)) denote the space of extended-real-valued u.m. (resp. l.s.a.) functions on X. For 0 < α ≤ 1, define dynamic programming operators T α that map v ∈ M(X) to a function on X according to 4 x ∈ X For α = 1, we simply write T for T α . By the properties of analytic sets and l.s.a. functions (cf. [3,Chap. 7]), T α and T map A(X) into A(X).
The following subclass of l.s.a. functions will be needed shortly. For a u.m. function w : X → (0, +∞), which we shall refer to as a weight function, let Note that M w (X), · w is a Banach space, and A(X) ∩ M w (X) is a closed subset of this space. 5

Some Basic Optimality Properties of Two Models
We consider two classes of MDPs. The first is the nonnegative cost model where the one-stage cost function c ≥ 0. We shall refer to this model as (PC) in what follows. For the average cost or discounted problem, it is equivalent to the case where c is bounded from below.
The second model, designated as (UC), involves unbounded costs: the function c can be unbounded from below or above, but it needs to satisfy a growth condition and moreover, there is a Lyapunov-type condition on the dynamics of the MDP. The precise definition is as follows.
Definition 2.1 (the model (UC)). There exist a u.m. weight function w(·) ≥ 1 and constants b,ĉ ≥ 0 and λ ∈ [0, 1) such that for all x ∈ X, (a) sup a∈A(x) |c(x, a)| ≤ĉ w(x); For (UC), its definition ensures that the average cost function of any policy π satisfies J(π, ·) w ≤ ℓ for the constant ℓ =ĉ b/(1 − λ). Hence the optimal average cost function also satisfies g * w ≤ ℓ and in particular, g * is finite everywhere. For (PC), g * ≥ 0 and it is possible that at some state x, g * (x) = +∞ (this possibility will be eliminated in Section 3 under further assumptions on the MDP model).
For both (PC) and (UC), the average-cost MDPs have the general optimality properties given in the next theorem, which is proved in the author's work [48,Secs. 2.2,A.2]. In this result as well as in what follows, by an ǫ-optimal or optimal policy, we mean a policy that is ǫ-optimal or optimal for all initial states. (i) The optimal average cost function g * is l.s.a.
(ii) For each ǫ > 0, there exists an (u.m.) ǫ-optimal randomized semi-Markov policy. If there exists an optimal policy for each state x ∈ X, then there exists an (u.m.) optimal randomized semi-Markov policy.
In Section 3, we will use the vanishing discount factor approach to prove the ACOI for (PC) and (UC) under additional conditions. That analysis starts with the optimality equations for the α-discounted cost criteria (α-DCOEs) given below: For α ∈ (0, 1), the optimal value function v α is l.s.a. and satisfies the α- x ∈ X.
For (PC), v α is the smallest solution of the α-DCOE in A(X), whereas for (UC), v α is the unique solution of the α-DCOE in the space A(X) ∩ M w (X). Furthermore, in both cases, for each ǫ > 0, there exists an ǫ-optimal nonrandomized stationary policy. As another preparation for Section 3, the next lemma states an implication of the ACOI on the existence and structure of average-cost optimal or nearly optimal policies. For comparison, note that in the general case where g * need not be constant, one can only assert the existence of an ǫ-optimal randomized semi-Markov policy (cf. Theorem 2.2). The proof of this lemma uses mostly standard arguments and can be found in [48,Appendix A.4].
Lemma 2.5 (a consequence of ACOI). Consider the models (PC) and (UC) with the average cost criterion. Suppose that the optimal average cost function g * is constant and finite. Suppose also that for some finite-valued h ∈ A(X), with h ≥ 0 for (PC) and h w < ∞ for (UC), the ACOI holds: Then there exist an optimal nonrandomized Markov policy and, for each ǫ > 0, an ǫ-optimal nonrandomized stationary policy. If, in addition, the infimum in the right-hand side of the ACOI is attained for every x ∈ X, then there exists an optimal nonrandomized stationary policy.

Main Results: The ACOI
In this section, we introduce our majorization condition for the (PC) and (UC) models and study the ACOI via the vanishing discount factor approach. The arguments for (PC) and (UC) are similar but differ in details, so we will discuss the two models separately. We consider (UC) first.

The (UC) Case
Letx be some fixed state and consider the relative value functions of the α-discounted problems: Take a sequence α n ↑ 1 such that for some ρ * ∈ R, (This is possible because the model conditions of (UC) imply that for each x ∈ X, Note that as n → ∞, h n ↑ h andh n ↓h.
This assumption is extracted from the analysis of the ACOI given in the book [20,Chap. 10.4], where the MDP is assumed to be uniformly w-geometrically ergodic, which ensures sup α∈(0,1) h α w < ∞. In Section 4.2 we shall discuss this w-geometric ergodicity condition as well as other types of sufficient conditions for Assumption 3.

Majorization Condition
We now introduce our majorization condition for the (UC) model. The first two parts of this condition will also be used for the (PC) model later. Let 1(·) denote the indicator function.
Assumption 3.3. In (UC), for each x ∈ X and ǫ > 0, the following hold: Note that in the above,ᾱ and ν can depend on x and ǫ. Note also that the one-stage cost function c(·) is not required to have any special properties. Assumption 3.3(i) is motivated by the theory on epi-convergence of functions, in particular, by the relation between the infima of epi-limits and pointwise limits of a sequence of functions and the implication of this relation on the validity of the ACOI in MDPs. In some circumstances, the existence of a compact subset K ǫ (x) with the property (3.5) is close to being necessary for the ACOI. We shall elaborate on this in Section 4.1 (cf. Prop. 4.1, Cor. 4.2) after we prove the ACOI, since the roles of the above conditions can be better seen then.
The choice of the subset K ǫ (x) of actions in Assumption 3.3(i) is important for the subsequent parts (ii)-(iii) of this assumption. Although (i) is trivially satisfied if we let K ǫ (x) = A(x), this makes it harder or sometimes impossible to satisfy (ii)-(iii). For instance, if A(x) = R and q(dy | x, a) is the normal distribution N (a, 1) on R, no finite measure can majorize these distributions for all a ∈ R. On the other hand, identifying a proper subset of actions that satisfies (i) is in general a difficult problem, because it requires the knowledge of the family of optimal value functions {v α }. An additional difficulty in the (UC) case is that, unlike in the (PC) case, the cost function c(x, ·) here must be bounded for each state x, preventing us from using "coercivity" of c(x, ·) to eliminate actions. (For this reason, in the illustrative example given in Appendix A.3 for the (UC) model, we is the key condition that allows us to apply Egoroff's theorem in proving the ACOI. The class of MDPs for which Assumption 3.3(ii) can hold naturally are those where for all a ∈ K ǫ (x), q(dy | x, a) has a density f x,a w.r.t. a common (σ-finite) reference measure ϕ. The pointwise supremum of the density functions, f x := sup a∈Kǫ(x) f x,a (or a measurable function that upper-bounds it), when it is integrable w.r.t. ϕ, defines a finite measure ν, with dν = f x dϕ, that has the desired majorization property (3.6).
Note that Assumption 3.3(ii) need not be satisfied by continuous state transition stochastic kernels. For example, if A(x) = [0, 1] and q(dy | x, a) = δ a (the Dirac measure at a), there is no finite measure with the desired majorization property. This, however, is not a "defect" in the majorization condition but a reflection of the difference in nature of topological and measure-theoretic properties (notice that there is also no nontrivial measure ν that can satisfy the minorization condition q(dy | x, a) ≥ ν(dy) for all a, in this example). Due to this difference, there are some inevitable limitations in the analysis technique we present in this paper, and we shall discuss this subject further in the example in Section 4.4 (cf. Remark 4.11).
Regarding Assumption 3.3(iii), roughly speaking, in the proof of the ACOI, we will use it to handle what is leftover after the application of Egoroff's theorem. Verifying this condition can be straightforward when the weight function w(·) has a simple analytical expression (e.g., when x ∈ R and w(x) = e x or x 2 ) and the properties of the integrals involved are known. For example, if w(·) is bounded from above on the union of the supports of the probability measures q(dy | x, a), a ∈ K ǫ (x), such as in the case where the union is contained in a compact set and w(·) is continuous, then Assumption 3.3(iii) is clearly satisfied. If c(·) is bounded, w(·) can be chosen to be constant and Assumption 3.3(iii) then holds trivially. Assumption 3.3(iii) is also implied by the slightly stronger condition w dν < ∞, where ν is the majorizing finite measure in Assumption 3.3(ii).
Let us end this discussion by clarifying the relation between our majorization condition and the one from Gubenko and Shtatland's early work. After proving the ACOI, we will discuss further the conditions involved in the proof and give illustrative examples in Section 4 and Appendix A.3.
Remark 3.4 (about the majorization condition in [17]). In their contraction-based fixed point approach, Gubenko and Shtatland's majorization condition [17, Sec. 3, Condition (II)] is like a sym-metric counterpart of their minorization condition, and it requires that there exists a finite measure ν on B(X) such that Note that here the same measure ν needs to majorize q(dy | x, a) for all states and admissible actions, whereas in our Assumption 3.3, ν can be different for each state. The requirement ν(X) < 2 (needed for converting T into a contraction) is too stringent and renders their condition (3.8) impractical.

Optimality Results
We now prove the ACOI for (UC) under the assumptions introduced earlier. Recall that the relative value functions {h n }, the functions h, {h n },h, {h n }, and also the scalar Theorem 3.5 (the ACOI for (UC)). Under Assumptions 3.1, 3.3 for the (UC) model, the optimal average cost function g * (·) = ρ * and with h ∈ A(X) ∩ M w (X) as given in (3.3), the pair (ρ * , h) satisfies the ACOI: Hence there exist an optimal nonrandomized Markov policy and for each ǫ > 0, an ǫ-optimal nonrandomized stationary policy.
Note that this theorem implies that ρ * does not depend on our choice of the sequence {α n } or the statex, and lim α→1 (1 − α) v α (x) = g * (the constant optimal average cost) for all x ∈ X.
This theorem can be compared with the prior ACOI result for (UC) with compactness/continuity conditions given in the book [20,Theorem 10.3.1].
In the case of bounded one-stage costs, another existing result due to Ross [33, Theorem 2] says that when A is finite, if {h α } is uniformly bounded and equicontinuous, then the ACOE holds for a continuous function h and constant g * . For comparison, treating the case of bounded one-stage costs as a special case of (UC) with w(·) ≡ 1, we have the following corollary from Theorem 3.5: Corollary 3.6. In an MDP with bounded c(·), suppose that for each x ∈ X, there is a finite measure ν on B(X) such that sup a∈A(x) q(B | x, a) ≤ ν(B) for all B ∈ B(X). Then, if {h α } is uniformly bounded, the ACOI (3.9) holds. Remark 3.7. It will be obvious from the proof of Theorem 3.5 that if we have h = lim n→∞ h n in addition, then the ACOI (3.9) holds with equality. The extra condition on the convergence of {h n } can be stringent and hard to check in practice, however. A discussion about existing results on the ACOE in the (UC) case and whether Theorem 3.5 can be strengthened to ACOE will be given in Section 4.2.
We now proceed to prove Theorem 3.5. First, we prove an important lemma, in which we combine the majorization condition with Egoroff's theorem.
be the set in the latter condition for a given x ∈ X and ǫ > 0. Then Proof. For the state x, ǫ > 0, and the set K ǫ (x) given in the lemma, let ν be the corresponding finite measure on B(X) in Assumption 3.3(ii). Recall that h n ↑ h and these functions are finite-valued and u.m. (Lemma 3.2). Therefore, by Egoroff's Theorem [9, Theorem 7.5.1], 8 for any δ > 0, there exists a u.m. set D δ ⊂ X with ν(X \ D δ ) < δ such that on the set D δ , h n converges to h uniformly as n → ∞. Consequently, for any η > 0, it holds for all n sufficiently large that By the choice of D δ and the majorization property of ν in Assumption 3.3(ii), By an alternative characterization of uniform integrability [9, Theorem 10.3.5], (3.11) together with the uniform integrability assumption in Assumption 3.3(iii) implies that for any given η > 0, it holds for all δ sufficiently small that X\D δ w(y) q(dy | x, a) ≤ η for all a ∈ K ǫ (x). Consequently, given η > 0, by choosing δ sufficiently small, we can make Combining this with (3.10), we obtain that for all n sufficiently large, Since η is arbitrary and h n ≤ h, the lemma follows by letting n → ∞ on both sides of the preceding inequality and using also the fact that since sup a∈Kǫ(x) X |h(y)| q(dy | x, a) < ∞ by Assumption 3.1 and the model condition of (UC).
Proof of Theorem 3.5. For each x ∈ X and ǫ > 0, by the α-DCOE (Theorem 2.3) and Assumption 3.3(i), for all n sufficiently large where the last inequality used the fact h n ≤ h n and that h n is u.m. (Lemma 3.2). Letting n → ∞ in both sides of (3.14), we have where the equality follows from Lemma 3.8. Since this holds for every x ∈ X and ǫ is arbitrary, the desired inequality (3.9) is proved.
To show g * (·) = ρ * , as in the analysis in [23], it suffices to show that for the pair (ρ * ,h), wherē h = lim sup n→∞ h n as we recall, the opposite inequality holds: x ∈ X. (3.15) This will yield g * (·) = ρ * because the inequality (3.15) implies that for every state x, every policy π has average cost J(π, x) ≥ ρ * , whereas the inequality (3.9) just proved implies the existence of a policy π with J(π, x) ≤ ρ * (the proofs of these two facts are standard). From the α-DCOE (3.13), we have that for all a ∈ A(x), so by taking limit supremum of both sides as n → ∞ and using also the facth n ≥ h n by definition, we have where the last equality follows from the dominated convergence theorem, in view of Lemma 3.2 and the model condition of (UC). This proves (3.15) and hence g * (·) = ρ * as discussed earlier. Finally, that h ∈ A(X) ∩ M w (X) follows from Lemma 3.2, and the existence of an optimal Markov policy and ǫ-optimal stationary policy follows from the ACOI proved above and Lemma 2.5.
The simple ACOE result mentioned in Remark 3.7 follows from the ACOI just proved and the inequality (3.15) in the proof above since h =h in that case.
We shall work under the following assumption taken from the ACOI literature: (G) For some policy π and state x, the average cost J(π, x) < ∞.
Remark 3.10. Precursors to these conditions were introduced in the early works of Sennott [36] and Schäl [35] and then evolved as the research progressed. The condition (G) is the same as that in [35] and by [35, Lemma 1.2(b)], it implies that The condition (B) was introduced by Feinberg, Kasyanov, and Zadoianchuk [13] to weaken the condition (B) in [35], which is Lemma 5]. Sennott first showed in her work on countable-space MDPs [36] that in proving the ACOI, it suffices to require the family of relative value functions to be bounded from above pointwise instead of uniformly. Let For each α ∈ (0, 1), define a function h α as Before proceeding, let us prove that these functions are l.s.a., so that we can take their integrals in the subsequent analysis. Proof. That the functions h and h α are finite-valued is clear from Assumption 3.9(B). In order to prove that they are l.s.a., let us treat the relative value functions h α , α ∈ (0, 1), as a function of (α, x). We have proved in [48, Lemma A.1, Appendix A.4] that v α (x) is an l.s.a. function of (α, x) on (0, 1) × X (this proof uses the deterministic control model corresponding to the MDP mentioned in Remark 2.4 in Section 2.3). Next, consider m α as a function of α. Since the one-stage cost c ≥ 0 in (PC), for each policy π and initial state x, the α-discounted value v π α (x) is non-decreasing as α increases. Therefore, m α = inf x∈X v α (x) is also monotonically non-decreasing as α increases. It follows that m α is a Borel measurable function of α on (0, 1) and so is −m α . Then, by [3,Lemma 7.30(4) a. in (α, x). Now, since for each α, h α is the partial minimization of h β (x) over β ∈ [α, 1), h α is an l.s.a. function of x by [3,Prop. 7.47]. Finally, since h α ↑ h as α ↑ 1, we can write h as the pointwise limit of h αn for a sequence α n ↑ 1, and therefore, h is l.s.a. by [3,Lemma 7.30(2)].

Majorization Condition
We now introduce a majorization condition for (PC). Its first two parts are the same as those of Assumption 3.3 for (UC).  .17)). An illustrative example will be given in Section 4.4.

Optimality Result
The following theorem can be compared with the existing ACOI results that require continuity/compactness conditions [13,35,44].
Remark 3.14. The countable-state finite-action MDP in Cavazos-Cadena's counterexample for ACOE [6] satisfies both assumptions of Theorem 3.13. In particular, regarding the majorization condition, in the finite-action case, Assumption 3.12(i)-(ii) hold trivially for K ǫ (x) = A(x); in that example h = 0, so Assumption 3.12(iii) also holds. This shows that without further conditions, we cannot improve the ACOI result in Theorem 3.13 to the ACOE. We now prove Theorem 3.13. The proof is similar to that of the ACOI in the (UC) case, but there are some subtle differences, one of which being that in this case, for different states, we choose possibly different sequences α n ↑ 1 and work with the corresponding relative value functions h αn . We start with a lemma similar to Lemma 3.8 for (UC); it follows from Egoroff's theorem and our majorization condition. Lemma 3.15. (PC) Let Assumptions 3.9, 3.12(ii)-(iii) hold, and let K ǫ (x) ⊂ A(x) be the set in the latter condition for a given x ∈ X and ǫ > 0. Then for any sequence α n ↑ 1, with h n = h αn , we have Proof. Note first that under Assumption 3.9, h n ↑ h < ∞ as n → ∞, and the integrals in the lemma are well-defined since h n , h are u.m. by Lemma 3.11. We follow the proof for Lemma 3.8 except for two small changes. The first change is that here, when dealing with the complement set X \ D δ after applying Egoroff's theorem, in order to obtain the bound (3.12): for all n sufficiently large, for a given η > 0 and sufficiently small δ > 0, we use the fact that h − h n ≤ h and we also use the uniform integrability condition in Assumption 3.12(iii) for the nonnegative function h, instead of the weight function w. The second change is that near the end of the proof, to show that we now use the fact that sup a∈Kǫ(x) X h(y) q(dy | x, a) < ∞, which is again implied by the uniform integrability condition on h in Assumption 3.12(iii).
Proof of Theorem 3.13. Consider an arbitrary x ∈ X and fix it in the proof below. Choose a sequence {α n } such that lim Note that ρ * ≥ lim sup n→∞ (1 − α n ) m αn . Recall also that ρ * ≤ inf y∈X g * (y) by [ c(x, a) + α n X h n (y) q(dy | x, a) . (3.23) Then similarly to the derivation of (3.14) in the proof for Theorem 3.5, we apply Assumption 3.12(i) and replace h n by h n in the right-hand side above before letting n → ∞ in both sides of (3.23). This results in the inequality where K ǫ (x) is the subset of actions in Assumption 3.12(i) for the fixed state x and ǫ > 0. Next, by (3.24) and Lemma 3.15, we have c(x, a) + X h(y) q(dy | x, a) .
Since this holds for an arbitrary x ∈ X and an arbitrary ǫ > 0, we obtain the desired ACOI. Since ρ * ≤ g * (·) [35, Lemma 1.2(b)], the ACOI just established implies that we must have g * (·) = ρ * [35, Prop. 1.3]. Finally, the existence of an average-cost optimal Markov policy and ǫ-optimal stationary policy follows from Lemma 3.11, the ACOI proved above, and Lemma 2.5. This completes the proof.

Further Discussion and Illustrative Examples
In this section, we will first explain the origin of the first part of our majorization condition (see Section 4.1). We will then discuss the boundedness condition (Assumption 3.1) on the family of relative value functions in the (UC) case, a related w-geometric ergodicity condition, as well as stronger conditions for ensuring the ACOE (see Sections 4.2-4.3). Finally, we will illustrate the application of our ACOI result for the (PC) model using an inventory control example (see Section 4.4). Due to space limit, an illustrative example for the (UC) model is given in Appendix A.3. If {f n } is a sequence of extended-real-valued functions on a metric space Y , the outer limit of their epigraphs, 10 lim sup n→∞ epi(f n ), corresponds to the epigraph of some (extended-real-valued) function on Y . This function, denoted by e-lim n f n , is called the lower epi-limit of {f n }. By definition, e-lim n f n is always l.s.c. and lies below the pointwise limit lim inf n→∞ f n , and moreover,

About Assumption 3.3(i), Epi-limits of Functions, and Their Relation with ACOIs
Thus, if we want the equality lim inf n→∞ inf y∈Y f n (y) = inf y∈Y lim inf n→∞ f n (y), we will need lim inf n→∞ inf y∈Y f n (y) = inf y∈Y e-lim n f n (y) to hold at least. The proposition below gives a necessary, sometimes sufficient, condition for the latter equality. It is similar to [32, Theorem 7.31(a)]; because [32] deals with finite-dimensional spaces only, for clarity, we include a proof of this result in Appendix A.1. If lim n→∞ inf y∈Y f n (y) exists and is finite, this condition implies (4.2) .
Let us discuss now what these results imply for the validity of the ACOI in MDPs. Consider some fixed statex ∈ X. Let Assumption 3.1 or 3.9 hold for (UC) or (PC), respectively. By redefining, if necessary, the sequence of discount factors α n in the proofs of the ACOI in Section 3, we can suppose that the corresponding relative value functions h n := h αn are such that lim n→∞ h n (x) = h(x) and also that lim n→∞ (1 − α n ) m αn exists if the model is (PC). Define functions f n on A(x) by f n (a) = c(x, a) + α n X h n (y) q(dy |x, a), a ∈ A(x).

(4.5)
While the strict inequality (4.5) does not contradict the ACOI in general, it rules out the ACOI in the following situations, which could happen in a given problem: h n ↑ h and, if the model is (PC), ρ(x) = ρ * in addition. In these cases, on the right-hand side of (4.5), we have lim inf n→∞ X h n (y) q(dy |x, a) = X h(y) q(dy |x, a) for each a by the monotone convergence theorem, so (4.5) becomes violating the ACOI at the statex. It is this observation that led us to introduce a condition like the inequality (4.4) as part of our majorization condition for the ACOI. The inequality (4.4) itself is unwieldy to verify, since, among others, it depends on the particular choice of the sequence {α n }. So we required a similar inequality to hold for all sufficiently large α instead, for each state x, and this gave rise to Assumption 3.3(i). (In the latter, the subset of actions is not required to be compact, for that is not needed in our proof of the ACOI.) Finally, note that Prop. 4.1 only deals with the first relation in (4.1) and does not guarantee equality to hold throughout (4.1), for the second inequality in (4.1) can still be strict. Likewise, Assumption 3.3(i) alone (even with a nontrivial, compact strict subset K ǫ (x) of A(x)) is in general not sufficient for the ACOI to hold. It is the two other parts of the majorization condition that gave us the rest of the help needed.

About the Assumption sup α∈(0,1) h α w < ∞ in the (UC) Case
This is Assumption 3.1. It holds if the MDP is uniformly w-geometrically ergodic, 11 as shown by [20,Lemma 10.4.2]-this result applies in our case as well, in view of Theorem 2.3 on the existence of ǫoptimal stationary policies in the α-discounted problems. Geometrically or w-geometrically ergodic 11 This means that every stationary nonrandomized policy µ induces a Markov chain on X with a unique invariant probability measure ϕµ, and the n-step transition kernel q n µ (dy | x) of this Markov chain satisfies that q n µ − ϕµ w ≤ R r n for all n ≥ 1, where and R > 0, 0 < r < 1 are constants independent of the policy µ (cf. [20,Assumption 10.2.2]). If w(·) ≡ 1, the MDP is called uniformly geometrically ergodic.
Markov chains and their application to MDPs are well-studied; see the book [20] for an in-depth discussion and a large body of the related literature. Assumption 3.1 can also hold in MDPs that do not possess ergodicity properties. A simple class of such MDPs is the "invariant" model considered by Assaf [2]: A(x) = A for all x ∈ X and the state transition stochastic kernel is q(dy | a), independent of x. In this case, if |c(x, a)| ≤ĉ w(x) for all (x, a) ∈ Γ and a weight function w(·), then (4.6) and hence sup α∈(0,1) h α w < ∞. In the special case of bounded one-stage costs, the family {h α } is uniformly bounded. For (UC) with an unbounded weight function w(·), Assumption 3.1 also holds for "partially invariant" models given in the next example.
Example 4.1 (partially invariant models). Consider a slight extension of Assaf's invariant models [2] in the case of (UC). Let b,ĉ ≥ 0 and λ ∈ [0, 1) be the constants in the model conditions of (UC), and let the weight function w(·) be l.s.a. Suppose that for some λ ′ ∈ (λ, 1), the MDP model is "invariant" on the subset of stateŝ in the sense that for all x ∈X,Â := A(x) is the same and q(dy | x, a) depends only on a. Then (4.6) holds for  It implies that under any policy π, where ℓ is some constant independent of π and x. This inequality follows from a general comparison theorem [27,Theorem 15.2.5] and can also be verified directly (in fact, ℓ = (1 − λ ′ ) −1 in this case). For each α ∈ (0, 1), let µ α be an ǫ-optimal stationary policy for the α-discounted problem (cf. Theorem 2.3). Using the inequality (4.9) together with the (UC) model condition (a) and the strong Markov property, we have The first term in (4.12) is bounded by a constant by (4.7). To bound the second term, note that E µα , and E µα x [τ ] ≤ ℓw(x) by (4.9), whereas due to the (UC) model condition, (1−α)|v α (x)| is bounded by some constant ℓx independent of α. Therefore, the second term in (4.12) is bounded by ℓℓxw(x). We thus have Combining this relation with the upper and lower bounds on v α (x) given in (4.10)-(4.11) and taking ǫ → 0, we obtain that for all α ∈ (0, 1), wherelx =ĉ ℓ + ℓℓx andl = 2bĉ/(λ ′ − λ) are constants independent of α and x. This shows that sup α∈(0,1) h α w < ∞. [2] proved the ACOE when the one-stage costs are bounded and the action space is finite. Schäl [35,Sec. 4,p. 169] showed that, for a Borel action space, if c is bounded below with sup a∈A c(x, a) < ∞ for all x ∈ X, then sup α∈(0,1) h α (x) < ∞ for all x ∈ X. Thus, in that case, the ACOI holds under our majorization condition for (PC), by Theorem 3.13. In the (UC) case, by Theorem 3.5, the ACOI also holds under our majorization condition, for both the invariant models and the partially invariant models described in the preceding example.

Remark 4.3 (ACOI for invariant and partially invariant models). For invariant models, Assaf
We will give an illustrative example in Appendix A.3 to demonstrate another way to ensure that Assumption 3.1 holds in an MDP that is not necessarily ergodic. There we will use some arguments from Example 4.1. In general, however, verifying Assumption 3.1 is a hard problem since it involves the optimal value functions {v α }. As recounted in Section 1, the ACOE was also directly obtained through a contraction-based, fixed point approach in Vega-Amaya [43,45] for MDPs under certain compactness and continuity conditions, and in Jaśkiewicz [22] for SMDPs with u.m. policies. 12 (In the special case w(·) ≡ 1, the ACOE was obtained earlier, through the fixed point approach, by Gubenko and Shtatland [17], as mentioned in the introduction.) For these ACOE results to hold in an MDP, among others, the MDP must be uniformly wgeometrically ergodic, 13 and moreover, there must exist a nontrivial σ-finite measure ϕ on X such that under any stationary nonrandomized policy µ, the induced Markov chain {x n } is ϕ-irreducible (see e.g., [20,27,29] for the definition). The existence of such a common irreducibility measure appears either in the conditions of the aforementioned results (e.g., [20,Theorem 10.3.6]) or follows as an implication of their assumptions (e.g., [22,43]).

About Geometric Ergodicity Conditions, ACOI, and ACOE in the (UC) Case
The uniform w-geometric ergodicity condition implies that for any two stationary nonrandomized policies, there must be a common irreducibility measure, but a common irreducibility measure for all stationary nonrandomized policies need not exist. This is illustrated by the following counterexample. 12 One difference between the minorization conditions in [22] and [43,45] is that the former is stated in terms of "small sets," whereas the latter "small functions" (cf. [29,Chap. 2.3]). 13 In [43,45], this follows as an implication of the conditions involved, by [43,Theorem 3.3] together with [24,Theorem 6] (see also [20,Theorem 7.3.11]). Example 4.2 (non-existence of common irreducibility measure). Let X be the unit circle and A = {0, 1, 2} = A(x) for all x ∈ X. Represent states by their angular coordinates. Let q(dy | x, a) be the uniform distribution on [ 2a 3 π, 2a 3 π + π] =: I a for a ∈ A and every x. Then the MDP is uniformly geometrically ergodic, and the maximal irreducibility measures (see [27,29] for the definition) that are possible under any nonrandomized stationary policy, are (up to equivalence) the Lebesgue measure restricted on the intervals I a , a = 0, 1, 2, on the unions of any two such intervals, and on [0, 2π]. Since the intersection of these intervals is empty, there is no common irreducibility measure for all stationary nonrandomized policies in this MDP.
This example shows that the uniform w-geometric ergodicity condition is more general than the conditions required by the fixed-point approach studied in [22,43,45], whereas Assumption 3.1 is more general than the former condition, as discussed in Section 4.2. This suggests that most likely, the ACOI in our Theorem 3.5 cannot be strengthened to ACOE without additional assumptions. However, we do not know a counterexample for ACOE under the conditions of Theorem 3.5.

An Illustrative Example for the (PC) Case
In this subsection, we use an inventory control example to illustrate the application of our ACOI result for the (PC) case. This example is adapted from an example in [35, p. 170]. The original example has compact action sets A(x) and i.i.d. random demands. We make A(x) non-compact and also allow action-dependent random demands, with which the state transition stochastic kernel need not be continuous. We will verify two major conditions for applying Theorem 3.13: our majorization condition and the condition (B), sup α∈(0,1) h α (x) < ∞, x ∈ X, which implies Assumption 3.9(B).

Two Helpful Lemmas
The condition (B) is not easy to check because it involves the optimal value functions v α , whose structures are problem-dependent and hard to characterize in general. Most of our efforts will be on verifying this condition. We will need two helpful lemmas given below. They are from [35,Lemmas 4.4,4.6], with slight modifications in the first one. Their proof arguments are outlined in [35], which utilize various stopping times. For completeness, we include a proof for the second lemma (Lemma 4.5 below) in Appendix A.1, as it is less obvious.

Single-Product Inventory System
Let X = A = R, A(x) = [x, +∞), and c(x, a) = κ(a − x) + ℓ(a) where κ : R + → R + and ℓ : R → R + . Let the states evolve according to x n+1 = a n − ξ n , where, for the nth stage: • x n and a n are the stock levels before and after placing the order, respectively; • ξ n ≥ 0 is the demand or consumption of the product, which is a random variable that does not depend on the history (x 0 , a 0 , ξ 0 , . . . , x n ) given a n ; • κ(a n − x n ) and ℓ(a n ) correspond to the ordering cost and the holding or shortage/backordering cost, respectively. We assume that for all n ≥ 0, the conditional distributions of ξ n given a n are parametrized by the values of a n (and Borel measurable in a n ), independent of n. These probability distributions will be denoted by F a , a ∈ R. In what follows, we shall write ξ n (a n ) for ξ n to emphasize the dependence on a n , and we use ξ(a) to denote a generic random variable with probability distribution F a and E[ξ(a)] to denote its expectation w.r.t. F a .
We impose two sets of conditions on the functions κ(·), ℓ(·) and the demand distributions F a . The first set is given below and will be used shortly to prove that the family {h α } is pointwise bounded under those conditions. When we consider the majorization condition later, we will add a second set of conditions.
Throughout this example, let Assumption 3.9(G) hold 14 (hence g * < ∞). Note that here κ(·) and ℓ(·) need not be l.s.c., and q(dy | x, a) need not be continuous. As a simple example, these functions can be piecewise continuous; even in this case, the compactness/continuity conditions required in [8,13,35] are violated. Proof. We follow the line of reasoning in [35,Sec. 4]. When computing upper bounds on h α (x), however, we will need to use more complex arguments because the random demands in our case are not i.i.d. as in [35].
Let us write q(dy | a) for q(dy | x, a), since state transitions in this example depend on a only. First, we use Lemma 4.5 to assert the existence of a bounded interval [L, M ] such that for somē ǫ > 0 and αǭ < 1, it holds for all α ≥ αǭ that .) The existence of such y α allows us to define a stopping time τ needed in applying Lemma 4.4 to bound h α : since for all x ′ ≤ y α , we have y α ∈ A(x ′ ) and stopping at any state x ′ ≤ y α will satisfy the condition of Lemma 4.4 on τ . This is the basic idea to bound sup α∈(0,1) h α (x). We now proceed to calculate the bounds on h α (x) for each x ∈ R and an arbitrary α ≥ αǭ. Define a stationary policy µ by Let τ := inf{n ≥ 0 | x n < L}. We will apply Lemma 4.4 with this τ and π = µ. To this end, let us bound E µ x τ −1 n=0 c(x n , a n ) + c(x τ , y α ) independently of α. The case x < L is simple: we have τ = 0 and under Assumption 4.6(i), (4.17) For x ≥ L, since κ(0) = 0 by Assumption 4.6(i), we have We apply a comparison theorem [27,Prop. 11.3.2] together with other arguments to bound E µ x [τ ], which in turn yields a bound on E µ x κ(y α − x τ ) . The derivations are given in Appendix A.2. The obtained upper bounds are as follows: for x ≥ L, where ∆ x = inf y∈[L, x∨M] E ξ(y) > 0 (cf. Assumption 4.6(iv)), and 0 < D x < ∞ is the smallest real number such that sup where the function H is finite everywhere, independent of α, and given by 22) and for x ≥ L, We can now apply Lemma 4.4 to prove sup α∈(0,1) h α (x) < ∞ for all x ∈ R. Let α ≥ αǭ. For all x ≤ L, by (4.16), X v α (y) q(dy | y α ) ≤ v α (x)+ǭ/2, so for applying Lemma 4.4, we can define a policy µǭ /2 α that satisfies (4.14) for ǫ =ǭ/2, in such a way that µǭ /2 α (x) = y α for x ≤ L. We have αv α (x τ ) ≤ m α +ǭ/2 by (4.16), so by Lemma 4.4 and the preceding proof, for all x ∈ R and α ≥ αǭ, As H(x) is independent of α, this inequality implies lim sup α↑1 h α (x) < ∞, which, under Assumption 3.9(G), is equivalent to sup α∈(0,1) h α (x) < ∞ by [13,Lemma 5].
We now tackle Assumption 3.12 (the majorization condition). Let us place two more conditions on the one-stage costs and the demand distributions:   Proof. Letǭ > 0, αǭ ∈ (0, 1), and the function H be as in the proof of Prop. 4.7. That proof showed that under Assumption 4.6, h α (x) ≤ǭ + H(x) for all x ∈ R and α ≥ αǭ. Consider now an arbitrary state x. By Assumption 4.8(i), there existsā ≥ x such that c(x, a) ≥ g * + 2ǭ + H(x) for all a ≥ā. Then, from the α-DCOE and the fact lim sup α↑1 (1 − α) m α ≤ g * , we have that for all α sufficiently large, Thus, for any ǫ > 0, Assumption 3.12(i) holds with K ǫ (x) = K := [x,ā]. Next, for the majorizing finite measure ν required in Assumption 3.12(ii), in view of Assumption 4.8(ii), we can simply let ν be a multiple of the Lebesgue measure on the bounded set E := ∪ a∈K {a − supp(F a )} and the trivial measure on the complement set E c .
Finally, given Assumption 4.8(ii) and the fact h ≤ǭ + H, for Assumption 3.12(iii) to hold, it suffices that H is bounded on bounded intervals. The expression (4.22)-(4.23) of H shows that this is the case. In particular, by Assumption 4.6(i) and (iv), if x lies in a bounded interval I, all those terms in (4.22)-(4.23) that involve the functions κ(·) and ℓ(·) must be bounded above by some constants depending on I. The remaining term is 2( ) for x ≥ L. Let I be a bounded interval in [L, ∞). By Assumption 4.6(iv), we have We also have sup x∈I D x < ∞, because by Assumption 4.6(iii), there exists some 0 < D < ∞ such that sup y≥L E ξ(y) 1(ξ(y) > D) ≤ ∆/2 ≤ ∆ x /2, ∀ x ∈ I, and this implies that D ≥ D x for all x ∈ I, since D x is by definition the smallest number satisfying (4.21). Hence sup x∈I 2(x − L + D x )/∆ x < ∞. Thus H is bounded on any bounded interval, and consequently, Assumption 3.12(iii) holds.
We have shown that the conditions in Theorem 3.13 are met and the ACOI holds. In connection with this example, let us make two final remarks regarding the structure of optimal/ǫ-optimal stationary policies and limitation of our majorization technique.
Remark 4.10. For l.s.c. models studied in e.g., [13,14,20,23,35], besides the ACOI or ACOE, one can also relate the optimal actions for discounted problems to those for the average-cost problem in the limit as the discount factor α ↑ 1. Moreover, for inventory control, if certain convexity properties are present, there exist optimal policies with particularly simple structures like the policy µ in this example, i.e., the so-called (s, S) policies and their generalizations (see e.g., [7,11,14]). For discontinuous MDP models, in general, one cannot guarantee such structural properties for the optimal or ǫ-optimal stationary policies. The proofs of Theorems 3.5 and 3.13 show that if for ǫ > 0, the set-valued map x → K ǫ (x) has an analytic graph, then in the average cost problem, there exists an ǫ-optimal nonrandomized stationary policy µ such that µ(x) ∈ K ǫ (x) for all x ∈ X. This, however, provides only a "loose" connection between some good actions in the discounted problems and those in the average cost problem, for the sets K ǫ (x) can be quite large, as shown by this example for (PC) and the example for (UC) in Appendix A.3.
Remark 4.11. Typically, the random demands in inventory control problems are allowed to be zero, as long as they are positive with positive probabilities. We do not allow this in Assumption 4.8(ii), because no finite measure can majorize the measures r a δ a with r a > 0 for all a ∈ I. This limitation is due to the nature of the measure-theoretic properties underlying our majorization condition, as discussed in Section 3.1.1. For similar problems in which q(dy | x, a) is not atomless, one possible way to proceed is to approximate the original MDP by one in which each action corresponds to some probability distribution over the feasible actions in the original problem. Then the majorization idea and the analysis technique presented in this paper may still be potentially useful for analyzing the approximating MDP, thereby shedding light on the original average cost problem. Proof of Prop. 4.1. We prove the second statement first. By the first inequality in (4.1), we need to prove lim n→∞ inf y∈Y f n (y) ≥ inf y∈Y e-lim n f n (y), and in turn, by the assumption (4.3), it is sufficient to prove that for each ǫ > 0, ℓ := lim inf j→∞ inf y∈K f nj (y) ≥ inf y∈Y e-lim n f n (y). To this end, consider a sequence {y j } in K with f nj (y j ) − inf y∈K f nj (y) → 0 as j → ∞. Since K is compact, there exists a subsequence y ji →ȳ ∈ K such that, with n ′ i := n ji and y ′ i : for all i and y ′ i →ȳ, by the definition of the lower epi-limit, we have e-lim n f n (ȳ) ≤ lim i→∞ f n ′ i (y ′ i ) = ℓ and hence inf y∈Y e-lim n f n (y) ≤ ℓ as desired. To prove the first statement, for every ǫ > 0, letȳ be any point that satisfies e-lim n f n (ȳ) ≤ inf y∈Y e-lim n f n (y) + ǫ/3.
By the definition of the lower epi-limit, there exist a subsequence {n j } and points {y j } with y j →ȳ and f nj (y j ) → e-lim n f n (ȳ) as j → ∞. Let K = {y j } j≥1 ∪ {ȳ}, which is a compact subset of Y .
Since inf y∈K f nj (y) ≤ f nj (y j ), it follows that for all j sufficiently large, inf y∈K f nj (y) ≤ e-lim n f n (ȳ) + ǫ/3 ≤ inf y∈Y e-lim n f n (y) + 2ǫ/3, whereas (4.2) implies that inf y∈Y e-lim n f n (y) ≤ inf y∈Y f nj (y) + ǫ/3 for all j sufficiently large. Hence (4.3) holds, as desired.
We now bound E µ x κ(y α − x τ ) for x ≥ L and derive the inequality (4.19). Since κ(·) is nondecreasing by Assumption 4.6(i) and by the definition of the stopping time τ and policy µ, we have Therefore, This is the desired inequality (4.19).

A.3 An Illustrative Example for the (UC) Case
This example is adapted from an inventory-production system example in the book [20, Examples 8.6.2, 10.9.3]. In the original example, the random demands at each stage are i.i.d. and for the average cost problem, the production level must always be below the expected demand so as to ensure that the w-geometric ergodicity condition of [20, Theorem 10.3.1] holds. We relax these requirements in our example so that the state transition stochastic kernel need not be continuous and the MDP need not be uniformly w-geometrically ergodic. To show that the ACOI holds in this example, most of our efforts will be on making sure that sup α∈(0,1) h α w < ∞. Regarding notation, for x, y ∈ R, denote x ∧ y = min{x, y} and x ∨ y = max{x, y}. Recall also that (x) + = max{x, 0}.
Let the state and action spaces be X = A = R + . The states evolve according to where x n is the stock level and z n the amount of production at the beginning of the nth stage, and ξ n is the random demand during that stage. As in Section 4.4.2, we let actions correspond to the stock levels after production: a n = x n + z n .
We assume that given a n , the demand ξ n depends on the value of a n and is conditionally independent of the history (x 0 , a 0 , ξ 0 , x 1 , . . . , ξ n−1 , x n ). As before, we denote the demand distributions by F a , a ∈ R + , we write ξ n (a n ) for ξ n to emphasize the dependence on a n , and we use ξ(a) to denote a generic random variable with probability distribution F a and E[ξ(a)] to denote its expectation w.r.t. The functions κ : R + → R + and m : R + → R + specify the production cost and the maintenance/holding cost, respectively, and s E a ∧ ξ(a) is the sales revenue with s being the unit sale price. This definition of c(·) is similar to the one in [20,Examples 8.6.2], except that we do not require κ(·) and m(·) to be continuous or l.s.c.
Assumption A.1 (conditions on one-stage costs). On R + , the production cost κ(·) is bounded on bounded intervals, and the maintenance or holding cost m(·) is bounded above by some polynomial function.

A.3.1 Definitions of Action Sets
We assume that beyond certain stock level L, the demand ξ(a) becomes "saturated" and follows a fixed probability distribution, no longer affected by a. Accordingly, we separate the states into three groups, {0}, (0, L), [L, +∞).
The state 0 will be special in this example. The feasible action sets A(x) are bounded intervals of the form [x, a x ], and we define them for each group of states differently, by placing different constraints on the admissible production levels z: (i) For all x ≥ L, z ∈ [0, θ] for some θ > 0 (so A(x) = [x, x + θ]). We will let the parameter θ be smaller than the mean demand, in order to satisfy the (UC) model conditions. The precise definition of θ will be given below. (ii) For 0 < x < L, z ∈ [0, θ x ] for some θ x > 0, and sup x∈(0,L) θ x < ∞. There are no other restrictions on θ x ; in particular, the production level z can exceed the expected demand E ξ(x+ z) . (Regarding measurability, it suffices that θ x is a Borel measurable function of x.) (iii) For the state 0, z ∈ [0,ā] whereā will be made large enough so that A(0) = [0,ā] contains A(x) for a large subset of states x. The precise definition of A(0) will be given below. The purpose of such a choice is to ensure sup α∈(0,1) h α w < ∞ in this example; more specifically, it will be used to ensure that {h α } can be bounded below by a multiple of the weight function w of our choice.
We now proceed to define the weight function w(·), the action set A(0), and the maximum production level θ allowed at states x ≥ L. Some conditions on the demand distributions will be needed: (iii) ξ(a) | a ≥ 0 is uniformly integrable.
These conditions will be used in the subsequent analysis to ensure that all the conditions required by Theorem 3.5 are met, except for the majorization condition. (For the latter, another condition will be added; cf. Assumption A.3.) Choice of θ and Parameters in the (UC) Model: Similarly to [20, Example 10.9.3], for states x ≥ L, we set the upper limit θ on the production levels to be such that for a ≥ L, 0 < θ < E ξ(a) (cf. Assumption A.2(i)-(ii)), and we then have that for some r > 0 (and all a ≥ L), λ := E e r(θ−ξ(a)) < 1.
Let the weight function w be w(x) = e rx .
By a direct calculation similar to that given in [20,  The (UC) model condition (b) is then satisfied, for the preceding constants λ, b and weight function w(·). In view of Assumption A.1 and the fact that the admissible production levels are uniformly bounded for all states, the (UC) model condition (a) on the one-stage cost function is also satisfied for some constantĉ. (e.g., letā = (L + θ)∨sup x∈(0,L) (x+ θ x ) < ∞). As mentioned and will be shown shortly, the purpose of this choice of A(0) is to make sure that in our subsequent analysis, h α (x) can be bounded from below independently of α.

Choice of
A.3.2 Bounding {h α } Setx = 0 in the definition of the relative value functions h α (x) = v α (x) − v α (x), α ∈ (0, 1). We prove below that under the preceding assumptions, sup α∈(0,1) h α w < ∞. LetX := [0,L]. We derive upper/lower bounds on h α (x), first for x ∈X and then for x ∈X. To calculate the upper bounds, we consider the policy π that makes no production so that z n = 0 and a n = x n always, and we bound first the expected hitting time to the statex = 0 under π. Let τ := inf{n ≥ 0 | x n = 0}.
The majorization condition (Assumption 3.3) holds easily under the preceding assumptions. In particular, for each state x ≥ 0 and ǫ > 0, with A(x) = [x, a x ], we observe the following: • Let K ǫ (x) = A(x); then Assumption 3.3(i) holds trivially. • For Assumption 3.3(ii), the required majorizing finite measure ν can be defined as where f max is an upper bound on the densities of {F a | a > 0} (cf. Assumption A.3); ϕ equals the Lebesgue measure on [0, a x ] and the trivial measure on (a x , ∞); and δ 0 is the Dirac measure at 0. This finite measure ν majorizes q(dy | x, a), a ∈ [x, a x ] and thus meets the requirement in Assumption 3.3(ii).
• Finally, notice that x 1 ∈ [0, a x ] if x 0 = x, whereas w(y) = e ry is bounded on [0, a x ]. Therefore, the uniform integrability condition required by Assumption 3.3(iii) is also trivially satisfied.
We have now verified all the conditions in Theorem 3.5 and can therefore conclude that the ACOI holds in this example.