K Avrachenkov
email: k.avrachenkov@inria.fr

V Gaitsgory
email: vladimir.gaitsgory@mq.edu.au

L Gamertsfelder
email: lucas.gamertsfelder@gmail.com

LP Based Upper and Lower Bounds for Cesàro and Abel Limits of the Optimal Values in Problems of Control of Stochastic Discrete Time Systems 1

In this paper, we study asymptotic properties of problems of control of stochastic discrete time systems (also known as Markov decision processes) with time averaging and time discounting optimality criteria, and we establish that the Cesàro and Abel limits of the optimal values in such problems can be evaluated with the help of a certain infinite-dimensional linear programming problem and its dual.

Introduction

In this paper, we analyze optimal values in problems of control of stochastic discrete time systems considered on long or infinite time horizons. We work with stochastic discrete time systems presented in the form of controlled stochastic recursions. It is known (see e.g., [START_REF] Bäuerle | Markov decision processes with applications to finance[END_REF][START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Kifer | Ergodic theory of random transformations[END_REF]) that a controlled stochastic recursion can be represented as a Markov Decision Process (MDP) and vice versa. It is not rare that a different point of view provides new insights into a well studied research area. Viewing MDPs as controlled stochastic recursions allows us to gain a better understanding of MDP properties in the challenging non-ergodic case.

There are many approaches to study optimal control of stochastic discrete time systems considered on long or infinite time horizons. Let us mention three such approaches that we are using in the present work. Firstly, it is the optimization of the expected discounted cost over the infinite time horizon. The expected discounted cost with a fixed discount factor can, however, be very insensitive to the long-term effects of a control, and one of common ways to study the long-term MDPs is to consider the lower or upper limit of the optimal expected discounted cost when the discount factor tends to one [START_REF] Feinberg | Average cost Markov decision processes with weakly continuous transition probabilities[END_REF][START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF][START_REF] Sznajder | Some comments on a theorem of Hardy and Littlewood[END_REF]. These are called the lower or, respectively, upper Abel limits of the optimal expected discounted cost.

Secondly it is also quite common in the MDP theory, to consider the lower or upper limits of the averages of the expected costs, the so-called lower or upper Cesàro limits, and then optimize these quantities. In the MDP literature (see e.g., [START_REF] Arapostathis | Discretetime controlled Markov processes with average cost criterion: A survey[END_REF][START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF] and references therein), this approach is referred to as a long-run average cost problem. However, as was noted in [START_REF] Flynn | On optimality criteria for dynamic programs with long finite horizons[END_REF], in contrast to the discounted criterion, the long-run average criterion disregards system dynamics on any finite length time interval. Therefore, it was proposed in [START_REF] Flynn | On optimality criteria for dynamic programs with long finite horizons[END_REF] to consider a sequence of optimal average values over finite horizons with increasing lengths. This is the third optimality criterion that we study in this work. Note that the Cesàro limit of the sequence of optimal average values may not exist in the general case, and one needs to investigate the lower and upper Cesàro limits of these sequences.

In fact, there are many more MDP optimality criteria such as average overtaking optimality, selective optimality criteria, etc. Note that in general different long-term optimality criteria can give different values or may not produce an optimal policy in some settings [START_REF] Feinberg | An ϵ-optimal control of a finite Markov chain with an average reward criterion[END_REF][START_REF] Khlopin | Tauberian theorem for value functions[END_REF][START_REF] Lehrer | A uniform tauberian theorem in dynamic programming[END_REF][START_REF] Lehrer | Discounting versus averaging in dynamic programming[END_REF][START_REF] Renault | Uniform value in dynamic programming[END_REF]. For an extensive account of various MDP optimality criteria and a historic perspective we refer an interested reader to the books [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF][START_REF] Kallenberg | Markov decision processes[END_REF][START_REF] Piunovskiy | Optimal control of random sequences in problems with constraints[END_REF][START_REF] Piunovskiy | Examples in Markov decision processes[END_REF][START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF].

Linear programming is one of the main tools for both theoretical and numerical analysis of MDPs. Various optimality criteria have been extensively studied by linear programming and other tools under conditions ensuing ergodicity or communicability of the underlying processes. For overview of many works in the ergodic setting we refer to [START_REF] Arapostathis | Discretetime controlled Markov processes with average cost criterion: A survey[END_REF][START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF]. The case with the presence of several non-communicating ergodic classes is more challenging and has received much less attention, particularly, in infinite state spaces. The authors of [START_REF] Denardo | Multichain Markov renewal programs[END_REF][START_REF] Denardo | On linear programming in a Markov decision problem[END_REF] have proposed to apply nested linear programs together with combinatorial search procedures for finding average cost optimal controls in finite MDPs. Then in [START_REF] Hordijk | Linear programming and Markov decision chains[END_REF][START_REF] Hordijk | Constrained undiscounted stochastic dynamic programming[END_REF][START_REF] Kallenberg | Linear programming and finite Markovian control problems[END_REF], also for finite MDPs, the authors have constructed a single linear programming formulation with two layers of constraints. In [START_REF] Hordijk | Linear programming formulation of mdps in countable state space: The multichain case[END_REF] the two-layer linear programming approach to average cost control problem has been extended to countable state spaces with multi-chain ergodic structure. There the authors indicated that there may exist a duality gap between the primal and dual linear programs. In [START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF], the two-layer linear programming approach has been extended to MDPs with general (non-compact) Borel state spaces, and sufficient conditions for the strong duality in the corresponding two-layer linear programs have been studied. Note that, as has been demonstrated in the recent work [START_REF] Shvartsman | Lack of equality between Abel and Cesáro limits in discrete optimal control and the implied duality gap[END_REF], the duality gap can appear in such program even in the case when the MDPs have compact state spaces.

In the first part of our work, we show that the convex closed hull of the discounted occupational measures set (obtained with fixed initial conditions) is characterized by a set of linear constraints depending on the parameter ϵ, with 1 -ϵ being the discount factor, and that the optimal expected discounted value is equal to the optimal value of an Infinite Dimensional Linear Program (IDLP) considered on this set. Also in the first part, we establish that, as the time horizon T tends to infinity, the closed convex hull of the union (over all initial conditions) of the occupational measure sets converges to the set of stationary measures defined by linear constraints, and the closed convex hull of the union of the sets of discounted occupational measures converges to this set as ϵ tends to zero (see Theorem 3.2). Let us note that already in [START_REF] Manne | Linear programming and sequential decisions[END_REF] it was conjectured and in [START_REF] Denardo | On linear programming in a Markov decision problem[END_REF] rigorously proved for finite models that only one-layer linear programming formulation is sufficient if one seeks to optimize over both the set of policies and the set of initial states.

Since, in the present work, we use the controlled stochastic recursion representation of MDP as a point of departure, the constraints of our primal programs are defined in terms of continuous test functions, which, at the first sight, looks very different from the form of constraints in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF]. We note, however, that the constraints can be reformulated in terms of bounded Borel test functions. The latter are readily shown to be equivalent to the constraints in a more common form based on the use of the transition probability kernel. As in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF], we also show that in the case of joint optimization over the sets of admissible policies and initial states, there is no duality gap, which in particular implies that both Abel limit of the expected discounted costs and the Cesàro limit of the optimal values over increasing finite horizons exist and coincide. One difference with respect to the results obtained in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF] is that we consider the convergence of the optimal values as the time horizon moves to infinity while in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF] the long-term average cost problem is considered.

The most important results of the paper are obtained in the second part of the paper, in which we consider the setting with a fixed initial state and view the linear program for the expected discounted cost as a singularly perturbed linear program [START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF][START_REF] Pervozvanskii | Theory of suboptimal decisions: Decomposition and aggregation[END_REF], with a perturbation parameter ϵ. Specifically, the IDLP problem considered on the set of stationary measures is obtained by formally taking ϵ = 0 in the perturbed problem. However, its optimal value can be strictly less than the limit of the optimal value of the perturbed IDLP problem, thus allowing one to characterize the latter as singularly perturbed (SP) problem. A way of dealing with SP problems is by augmenting the set of constraints obtained by just taking ϵ = 0 with some additional constraints and decision variables (see [START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF][START_REF] Avrachenkov | Constraint augmentation in pseudosingularly perturbed linear programs[END_REF][START_REF] Avrachenkov | Singularly perturbed linear programs and Markov decision processes[END_REF][START_REF] Gaitsgory | Averaging and linear programming in some singularly perturbed problems of optimal control[END_REF][START_REF] Pervozvanskii | Theory of suboptimal decisions: Decomposition and aggregation[END_REF]). The augmented linear problem and its dual provide upper and lower bounds for the lower and upper Cesàro and Abel limits of the optimal values (see Theorem 4.2). In addition, we establish that, if a point-wise limit of the optimal values as the horizon moves to infinity exists and is continuous with respect to the initial state, then this limit is equal to the optimal value of the augmented dual problem, and also that, if a point-wise limit of the expected discounted costs as the discount factor goes to one exists and is continuous, then this limit is equal to the optimal value of the augmented dual problem too.

We introduced an optimization problem, the optimal value of which is shown to be equal to that of the dual problem. The feasible domain of this problem contains the feasible domain of the primal IDLP problem, and the sufficient condition for the strong duality is that the closure of the latter is equal to the former (see Proposition 5.2 and Corollary 5.4). We have shown that the upper limit of the set of the occupational measures generated by the state-control trajectories emanated from a given initial point y 0 is contained in the feasible set of this problem (see Proposition 5.1), with the limit of the convex closed hull of the former being equal to the latter under the additional assumption that the pointwise limits of the optimal value functions exist and are continuous (see Corollary 5.3). We have also provided a condition for the absence of duality gap when the time average optimality can be achieved with the use of periodic generating regimes (see Proposition 5.5 and Corollary 5.6). The importance of the fact that the limit of the optimal values is (or can be) equal to the optimal value of the augmented dual problem is emphasized by sufficient and necessary conditions for the long run average optimality (see Propositions 6.2 and 6.3).

The approach that we use in the present paper was proposed in [START_REF] Borkar | Linear programming formulation of long run average optimal control problem[END_REF], where LP based upper and lower bounds for Cesàro and Abel limits of optimal values were obtained for "non-ergodic" deterministic systems evolving in continuous time. In [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF], similar results were obtained for deterministic systems evolving in discrete time under less restrictive assumptions than in [START_REF] Borkar | Linear programming formulation of long run average optimal control problem[END_REF]. For example, in contrast to [START_REF] Borkar | Linear programming formulation of long run average optimal control problem[END_REF], no assumptions about the existence of the uniform Cesàro and Abel limits and their Lipschitz continuity as functions of the initial values have been made in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF] to establish the upper bound for these limits. Many results obtained in this paper are stated and proved similarly to their deterministic counterparts obtained in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF]. However, the part of Theorem 4.2 that establishes the upper bound for the Cesàro and Abel limits of the optimal values (this being one of the most important results of the paper) is stronger than the corresponding statement in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF] (see Theorem 3.1 in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF]) since, in contrast to the latter, it is not assumed that the optimal value over the finite horizon and the optimal expected discounted cost are continuous with respect to the initial state. (Note that the line of research started in [START_REF] Borkar | Linear programming formulation of long run average optimal control problem[END_REF] has been also continued in [START_REF] Gaitsgory | Linear programming estimates for cesàro and abel limits of optimal values in optimal control problems[END_REF] and [START_REF] Gaitsgory | Lp-related representations of cesàro and abel limits of optimal value functions[END_REF], where some results for deterministic continuous time systems related to relaxations of conditions used in [START_REF] Borkar | Linear programming formulation of long run average optimal control problem[END_REF] have been obtained.)

The paper consists of ten sections. In Section 2 we first define the model and state the assumptions. Then, we recall definitions of occupational (and discounted occupational) measures generated by the state-control trajectories of system, and we reformulate optimal control problems as problems of optimization on these sets. All obtained results are stated in Sections 3 -6, and most of their proofs (as well as the results needed for these proofs) are given in Sections 7 -10.

Model and Preliminaries

We consider the discrete time stochastic control system in a form of controlled stochastic recursion

y(t + 1) = f (y(t), u(t), s(t)), t = 0, 1, 2, . . . , (2.1)
and we assume that the following conditions are satisfied everywhere in what follows:

The function f (y, u, s) : Y × Û × S → R m is bounded, continuous in (y, u) on Y × Û and Borel measurable in s on S, where Y is a compact subset of R n , Û is a compact metric space, and S is a Polish space. s(t) ∈ S, t = 0, 1, ..., is a sequence of independent, identically distributed random elements defined on a common probability space.

The controls u(t), t = 0, 1, ..., are defined by a sequence of functions π def = {π t (y), t = 0, 1, ...} that are Borel measurable selections of a multivalued map U (•) : Y ⇝ Û so that

u(t) = π t (y(t)) ∈ U (y(t)), t = 0, 1, ..., (2.2)
where U (•) is upper semicontinuous and compact-valued (that is, U (y) is compact for any y ∈ Y ).

f (y, u, s) ∈ Y for any y ∈ Y , any u ∈ U (y), and any s ∈ S (that is, the set Y is forward invariant with respect to system (2.1)).

Let Π stand for the set of sequences of measurable selections of U (•):

Π def = {π = {π t (•), t = 0, 1, ...} | π t (y) ∈ U (y) ∀ y ∈ Y, π t (•) are Borel measurable} .
For any sequence π ∈ Π (for convenience, such sequences will be referred to as control plans) and any initial condition y(0) = y 0 ∈ Y , let (y π,y 0 (•), u π,y 0 (•)) stand for the state-control trajectory obtained in accordance with (2.1) and (2.2).

Consider the following optimal control problems

1 T min π∈Π E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) def = v T (y 0 ), (2.3)
ϵ min π∈Π ∞ t=0 (1 -ϵ) t k(y π,y 0 (t), u π,y 0 (t)) def = h ϵ (y 0 ), (2.4)
where k(y, u)

: Y × Û → R is a continuous function with |k(y, u)| ≤ M ∀(y, u) ∈ Y × Û , M = const, (2.5)
and ϵ ∈ (0, 1) (that is, (1 -ϵ) is a discount factor). Note that, as follows from the proposition stated below, the minima in (2.3) and (2.4) are achieved and the optimal value functions v T (•) and h ϵ (•) are lower semicontinuous.

Proposition 2.1 Under the assumptions made above, the optimal value functions v T (•) and h ϵ (•) are lower semicontinuous and satisfy the equations:

T v T (y) = min u∈U (y) {k(y, u) + (T -1)E[v T -1 (f (y, u, s))]} ∀ y ∈ Y, T = 1, 2, ..., (2.6
)

h ϵ (y) = min u∈U (y) {ϵk(y, u) + (1 -ϵ)E[h ϵ (f (y, u, s))]} ∀ y ∈ Y. (2.7)
Also, the minima in (2.3) and (2.4) are achieved.

Proof. The proof follows Theorems 2.4.6 and 7.2.1 in [START_REF] Bäuerle | Markov decision processes with applications to finance[END_REF]. □

We will be interested in evaluating lim T →∞ v T (y 0 ) and lim ϵ→0 h ϵ (y 0 ) (these limits are commonly referred to as the Cesàro limit of the sequence of optimal values and the Abel limit of the expected discounted costs). More specifically, we will establish that lim sup T →∞ v T (y 0 ) and lim sup ϵ→0 h ϵ (y 0 ) are bounded from above by the optimal value of a certain IDLP problem, and that lim inf T →∞ v T (y 0 ) and lim inf ϵ→0 h ϵ (y 0 ) are bounded from below by the optimal value of the corresponding dual problem (see Theorem 4.2). An immediate consequence of this result is the statement that the Cesàro and Abel limits exist and are equal to each other if there is no duality gap (see Corollary 4.3).

Let us conclude this section with the introduction of some notations and definitions that will be used in the subsequent sections. Let G stand for the graph of U (•),

G def = graph(U ) = {(y, u) : u ∈ U (y), y ∈ Y } ,
and let P(G) stand for the set of probability measures defined on Borel subsets of G. (Note that, due to upper semicontinuity of U (•), the graph G is a compact subset of Y × Û .) Given a control plan π ∈ Π and an initial condition y(0) = y 0 ∈ Y , denote by γ π,y 0 ,T ∈ P(G) and γ π,y 0 ,ϵ d ∈ P(G) the probability measures defined as follows:

for any Borel Q ⊂ G, γ π,y 0 ,T (Q) = 1 T E T -1 t=0 1 Q (y π,y 0 (t), u π,y 0 (t)) , (2.8)
γ π,y 0 ,ϵ d (Q) = ϵE ∞ t=0 (1 -ϵ) t 1 Q (y π,y 0 (t), u π,y 0 (t)) , (2.9)
where 1 Q (•) is the indicator function of Q. The measures defined by (2.8) and (2.9) will be referred to as occupational measure and, respectively, discounted occupational measure generated by the control plan π. Note that from (2.8) and (2.9) it follows that

G q(y, u)γ π,y 0 ,T (dy, du) = 1 T E T -1 t=0 q(y π,y 0 (t), u π,y 0 (t)) (2.10) and G q(y, u)γ π,y 0 ,ϵ d (dy, du) = ϵE ∞ t=0
(1 -ϵ) t q(y π,y 0 (t), u π,y 0 (t)) (2.11) for any bounded Borel measurable function q on G. In fact, the definitions (2.8) and (2.9) are equivalent to that the equality (2.10) and (2.11) are valid if q(•) is an indicator function of Q. Therefore, these equalities are valid for linear combinations of indicator functions. The validity of (2.10) and (2.11) for any Borel function follows from the fact that any such function can be presented as uniform limit of linear combinations of indicator functions.

Let us denote by Γ T (y 0 ) the set of occupational measures and by Θ ϵ (y 0 ) the set of discounted occupational measures:

Γ T (y 0 ) def = π∈Π {γ π,y 0 ,T }, Θ ϵ (y 0 ) def = π∈Π {γ π,y 0 ,ϵ d }.
(2.12)

Note that, due to (2.10) and (2.11), problems (2.3) and (2.4) can be rewritten in the form

min γ∈Γ T (y 0 ) G k(y, u)γ(dy, du) = v T (y 0 ) (2.13)
and min

γ∈Θϵ(y 0 ) G k(y, u)γ(dy, du) = h ϵ (y 0 ), (2.14)
respectively.

To describe convergence properties of occupational measures, the following metric on P(G) will be used:

ρ(γ ′ , γ ′′ ) := ∞ j=1 1 2 j G q j (y, u)γ ′ (dy, du) - G q j (y, u)γ ′′ (dy, du) (2.15)
for γ ′ , γ ′′ ∈ P(G), where q j (•), j = 1, 2, . . . , is a sequence of Lipschitz continuous functions dense in the unit ball of the space of continuous functions C(G) from G to R. This metric is consistent with the weak * convergence topology on P(G), that is, a sequence γ k ∈ P(G) converges to γ ∈ P(G) in this metric if and only if lim k→∞ G q(y, u)γ k (dy, du) = G q(y, u)γ(dy, du)

for any q ∈ C(G).

REMARK. Note that P(G) is weak * compact (as implied by Banach-Alaoglu theorem; see, e.g., Theorem 3.5.16 in [START_REF] Ash | Measure, integration and functional analysis[END_REF]). Therefore, it is also compact in metric ρ defined in (2.15). Also, any weak * closed subset of P(G) is compact in this metric.

Using the metric ρ, we can define the "distance" ρ(γ, Γ) between γ ∈ P(G) and Γ ⊂ P(G) and the Hausdorff metric ρ H (Γ 1 , Γ 2 ) between Γ 1 ⊂ P(G) and Γ 2 ⊂ P(G) as follows:

ρ(γ, Γ) def = inf γ ′ ∈Γ ρ(γ, γ ′ ), ρ H (Γ 1 , Γ 2 ) def = max{ sup γ∈Γ 1 ρ(γ, Γ 2 ), sup γ∈Γ 2 ρ(γ, Γ 1 )}.
Note that, although, by some abuse of terminology, we refer to ρ H (•, •) as a metric on the set of subsets of P(G), it is, in fact, a semi-metric on this set (since ρ H (Γ 1 , Γ 2 ) = 0 implies Γ 1 = Γ 2 if Γ 1 and Γ 2 are closed, but the equality may not be true if at least one of these sets is not closed).

3 IDLP presentations of optimal control problems: Vanishing discounting as a singular perturbation

W def = γ ∈ P(G)| G E φ(f (y, u, s)) -φ(y) γ(dy, du) = 0 ∀φ ∈ C(Y ) , (3.2)
where s stands for a generic random variable that has the same distribution as s(t). Note that, as can be readily seen, the sets W (ϵ, y 0 ) and W are convex. Also they are weak * closed (due to the continuity of the functions under the integrals (3.1) and (3.2) implied by the assumptions made). Therefore, these sets are compact in metric ρ defined in (2.15) (see Remark after the definition of ρ). For convenience, W (ϵ, y 0 ) and W will be referred to as the sets of discounted stationary and stationary measures (respectively).

Consider the following two optimization problems Note that these problems belong to the class of IDLP problems since both the objective function and the constraints defining W (ϵ, y 0 ) and W are linear in γ. The problem dual to (3.3) and (3.4) can be written as follows (see [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF], [START_REF] Anderson | Linear programming in infinite-dimensional spaces[END_REF] and Section 10.1 below):

sup ψ∈C(Y ) min (y,u)∈G k(y, u) + (1 -ϵ) E ψ(f (y, u, s)) -ψ(y) + ϵ ψ(y 0 ) -ψ(y) def = µ * (ϵ, y 0 ) (3.
coΘ ϵ (y 0 ) = W (ϵ, y 0 ) ∀ ϵ ∈ (0, 1), (3.9) lim ϵ→0 ρ H ( coΘ ϵ , W ) = 0, where Θ ϵ def = y 0 ∈Y {Θ ϵ (y 0 )}, (3.10)
lim

T →∞ ρ H ( coΓ T , W ) = 0, where Γ T def = y 0 ∈Y {Γ T (y 0 )}, (3.11)
where co stands for the closed convex hulls of the corresponding sets.

Proof. The proof of the theorem is given in Section 8. Note that it is very similar to the proofs of the corresponding results in the deterministic setting; see Corollary 2 and Theorem 5.4 in [START_REF] Gaitsgory | Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time[END_REF]. □ Corollary 3.3 The optimal values of the problems (2.3), (2.4) are related to the optimal values of the IDLP problems (3.3), (3.4) by the equalities:

h ϵ (y 0 ) = k * (ϵ, y 0 ) ∀ ϵ ∈ (0, 1), (3.12) lim ϵ→0 min y 0 ∈Y h ϵ (y 0 ) = k * , (3.13) lim T →∞ min y 0 ∈Y v T (y 0 ) = k * . (3.14)
Proof. The fact that (3.12) is implied by (3.9) follows from the validity of the equalities Proof. The proof is given is Section 9. Note here only that it is based on the separation theorem (see, e.g., [START_REF] Rudin | Functional analysis[END_REF], p. 59). □

h ϵ (y 0 ) = min γ∈Θϵ(y 0 ) G k(y,
As can be seen, the set W can be obtained by formally taking ϵ = 0 in (3.1). Thus, the IDLP problem (3.3) can be considered to be "perturbed" with respect to the "reduced" IDLP problem (3.4). Let us verify that

lim sup ϵ→0 W (ϵ, y 0 ) ⊂ W. (3.18)
In fact, let γ i ∈ W (ϵ i , y 0 ), i = 1, 2, ..., ϵ i → 0 and γ i → γ. Since the functions under the integrals in the expression (3.1) for W (ϵ, y 0 ) are continuous and, therefore, bounded (due to the assumptions made), we can substitute ϵ i for ϵ and pass to the limit with i → ∞ in this expression. We will, thus, verify that γ ∈ W , which establish the validity of the inclusion (3.18). The latter implies that lim inf

ϵ→0 k * (ϵ, y 0 ) ≥ k * . (3.19)
(Note that (3.19) also follows directly from the relations (3.12) and (3.13).) Inequality (3.19) can be strict. That is, the optimal value of the IDLP problem (3.3) can be discontinuous at ϵ = 0. Problems characterized by such a discontinuity are called singularly perturbed (see [START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF], [START_REF] Avrachenkov | Constraint augmentation in pseudosingularly perturbed linear programs[END_REF], [START_REF] Avrachenkov | Singularly perturbed linear programs and Markov decision processes[END_REF], [START_REF] Gaitsgory | Averaging and linear programming in some singularly perturbed problems of optimal control[END_REF] and [START_REF] Pervozvanskii | Theory of suboptimal decisions: Decomposition and aggregation[END_REF]). In line with Corollary 3.3, the strict inequality in (3.19) may occur if the Cesàro and Abel limits of the optimal values are dependent on initial conditions (the so called "non-ergodic" case). In fact, as demonstrated by the example below, these limits may exist, be equal to each other, and be strictly greater than k * .

Example 1. Let the dynamics be one-dimensional and be described by the equation (compare with (2.1))

y(t + 1) = y(t)u(t)s(t) ∀ t = 0, 1, ... , (3.20)
where Y = [-1, 1] and U (y) = {-1, 1} (that is, the control can be either equal to 1 or to -1). Assume that s(t) takes only two values: s(t) = 1 with probability 3 4 and s(t) = -1 with probability 1 4 . Consider problem (2.3) with k(y, u) = y. It can be readily understood, that, in this example, the plan π * = {π * t (y), t = 0, 1, ...}, where, for any t = 0, 1, ...., π * t (y) = +1 for y ∈ [-1, 0] and π * t (y) = -1 for y ∈ (0, 1], (3.21) is optimal in both problem (2.3) and problem (2.4) (as this is the plan that maximizes the probability for the state variable to be negative). The optimal values of problems (2.3) and (2.4) can be evaluated to be as follows

v T (y 0 ) = - 1 2 |y 0 | + 1 T y 0 + 1 2 |y 0 | ∀ y 0 ∈ Y, (3.22) h ϵ (y 0 ) = - 1 2 |y 0 | + ϵ y 0 + 1 2 |y 0 | ∀ y 0 ∈ Y. (3.23)
(By a direct substitution, one can verify that v T (y 0 ) and V ϵ (y 0 ) def = ϵ -1 h ϵ (y 0 ), defined in accordance with (3.22)

k * (ϵ, y 0 ) = lim ϵ→0 h ϵ (y 0 ) = lim T →∞ v T (y 0 ) = - 1 2 |y 0 | (3.24) and k * = lim ϵ→0 min y ′ 0 ∈Y h ϵ (y ′ 0 ) = lim T →∞ min y ′ 0 ∈Y v T (y ′ 0 ) = - 1 2 .
Thus, inequality (3.19) is strict in this case if

|y 0 | ̸ = 1.
Since the reduced IDLP problem (3.4) does not involve the dependence on the initial condition y 0 , it is not surprising that its optimal value is not equal to (or may not even provide a good estimate for) the Cesàro and Abel limits of the optimal values in case the latter depend on y 0 . In the next section, we will introduce an IDLP problem that allows one to capture such a dependence.

Note that it is well known (and also readily verifiable) that the set of test functions used in the definitions of the sets W (ϵ, y 0 ) and W can be expanded, with the latter being representable in the form:

W (ϵ, y 0 ) = γ ∈ P(G) G (1 -ϵ) E φ(f (y, u, s)) -φ(y) + ϵ(φ(y 0 ) -φ(y)) γ(dy, du) = 0 ∀ φ ∈ B(Y ) , (3.25)
W = γ ∈ P(G) G E φ(f (y, u, s)) -φ(y) γ(dy, du) = 0 ∀ φ ∈ B(Y ) , (3.26)
where B(Y ) stands for the space of bounded Borel functions on Y . In addition (and it is readily verifiable too) the sets W (ϵ, y 0 ) and W allow the following representations:

W (ϵ, y 0 ) = γ ∈ P(G) γ 1 (Q) = (1 -ϵ) G P (Q|y, u)γ(dy, du) + ϵ1 Q (y 0 ) ∀ Borel Q ⊂ Y , (3.27)
W = γ ∈ P(G) γ 1 (Q) = G P (Q|y, u)γ(dy, du) ∀ Borel Q ⊂ Y , (3.28)
where γ 1 is the marginal of γ, that is,

γ 1 (Q) = G 1 Q (y)γ(dy, du), (3.29)
and P (dy|y, u) is the transition law associated with system (2.1), that is,

P (Q|y, u) = E[1 Q (f (y, u, s))] ∀ (y, u) ∈ G. (3.30)
REMARK. The validity of the representations (3.27) and (3.28) make the results established by Theorem 3.2 and Corollary 3.3 consistent with well known results in Markov control processes theory; see [START_REF] Altman | Constrained Markov decision processes[END_REF][START_REF] Borkar | Topics in controlled Markov chains[END_REF][START_REF] Borkar | Convex analytic methods in Markov decision processes[END_REF][START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Further topics on discrete-time Markov control processes[END_REF][START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF][START_REF] Piunovskiy | Optimal control of random sequences in problems with constraints[END_REF][START_REF] Piunovskiy | Discounted continuous-time Markov decision processes with unbounded rates: The convex analytic approach[END_REF] and references therein. Many of the latter are obtained under assumptions that are lighter than the assumptions we are using in this paper. Note that some of our assumptions can be relaxed too. For example, the assumption about compactness of the state space Y can be replaced by the assumption about the tightness of the set of occupational measures that make the results of Theorem 3.2 valid. However, to make the presentation more expository, we stick to using simpler (albeit more restrictive) assumptions.

4 Augmented IDLP problem: Upper and lower bounds for the Cesàro and Abel limits of the optimal values

If an LP problem is singular perturbed (SP), then the (independent of ϵ) LP problem that defines the limit of the optimal value as ϵ → 0 can be constructed by augmenting the reduced problem with some additional constraints and decision variables. Such an augmentation was established to be effective for the SP LP problems in finite dimensions (see [START_REF] Avrachenkov | Constraint augmentation in pseudosingularly perturbed linear programs[END_REF], [START_REF] Avrachenkov | Singularly perturbed linear programs and Markov decision processes[END_REF], [START_REF] Pervozvanskii | Theory of suboptimal decisions: Decomposition and aggregation[END_REF] as well as [START_REF] Hordijk | Linear programming and Markov decision chains[END_REF], [START_REF] Hordijk | Constrained undiscounted stochastic dynamic programming[END_REF]). For the SP IDLP problem (3.3), by formally following the construction of [START_REF] Avrachenkov | Constraint augmentation in pseudosingularly perturbed linear programs[END_REF] and [START_REF] Avrachenkov | Singularly perturbed linear programs and Markov decision processes[END_REF], one can arrive at the IDLP problem inf

(γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) def = k * (y 0 ), (4.1)
where

Ω(y 0 ) def = {(γ, ξ) ∈ P(G) × M + (G)| γ ∈ W, G (φ(y 0 ) -φ(y))γ(dy, du) + G E φ(f (y, u, s)) -φ(y) ξ(dy, du) = 0 for all φ ∈ C(Y )}, (4.2)
where M + (G) stands for the space of nonnegative finite measures defined on Borel subsets of G. This problem is obtained by augmenting the reduced problem (3.4) with additional constraints involving a new "decision variable" ξ. Note that the presence of the additional constraints imply that Ω(y 0 ) ⊂ W ∀ y 0 ∈ Y , and, therefore, the optimal values of problems (3.4) and (4.1) are related by the inequality

k * ≤ k * (y 0 ) ∀ y 0 ∈ Y.
The problem dual to the augmented IDLP problem (4.1) can be written in the form (see Section 10.2)

sup (µ,ψ,η)∈D(y 0 ) µ def = d * (y 0 ), (4.3)
where D(y 0 ) is the set of triplets (µ,

ψ(•), η(•)) ∈ IR × C(Y ) × C(Y ) that for all (y, u) ∈ G satisfy the inequalities k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) -µ ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ 0. (4.4)
Note that the optimal value of problem (4.3) can be equivalently represented as

d * (y 0 ) = sup (ψ,η)∈C(Y )×C(Y ) min (y,u)∈G {k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y)}, (4.5)
where ψ satisfies the second inequality in (4.4).

The following proposition establishes the validity of the weak duality inequality. Proof. Take any (γ, ξ) ∈ Ω(y 0 ) and (µ, ψ, η) ∈ D(y 0 ). Integrating the first inequality in (4.4) with respect to γ and taking into account that γ ∈ W , we conclude that

G k(y, u)γ(dy, du) + G (ψ(y 0 ) -ψ(y))γ(dy, du) ≥ µ.
Since (γ, ξ) ∈ Ω(y 0 ), from the second inequality in (4.4) it follows that

G (ψ(y 0 ) -ψ(y))γ(dy, du) = - G E[ψ(f (y, u, s))] -ψ(y) ξ(dy, du) ≤ 0. Therefore, G k(y, u)γ(dy, du) ≥ µ.
Taking first inf over all (γ, ξ) ∈ Ω(y 0 ) in the left-hand-side and then sup over all (µ, ψ, η) ∈ D(y 0 ) in the right-hand-side, one establishes the validity of (4.6).

Example 1 (continuation). The augmented IDLP problem (4.1) takes the form inf

(γ,ξ)∈Ω(y 0 ) G yγ(dy, du) = k * (y 0 ), (4.7)
where Ω(y 0 ) is the set of pairs (γ, ξ) ∈ P(G) × M + (G) that satisfy the equations

G 3 4 φ(yu) + 1 4 φ(-yu) -φ(y) γ(dy, du) = 0 ∀ φ ∈ C([-1, 1]), (4.8)
G (φ(y 0 ) -φ(y))γ(dy, du) = - G 3 4 φ(yu) + 1 4 φ(-yu) -φ(y) ξ(dy, du) ∀ φ ∈ C([-1, 1]), (4.9)
and where

G = Y × U = [-1, 1] × {-1, 1} in this case. The corresponding dual problem (see (4.5)) is sup (ψ,η)∈C([-1,1])×C([-1,1]) min (y,u)∈G y + (ψ(y 0 ) -ψ(y)) + 3 4 η(yu)) + 1 4 η(-yu) -η(y) = d * (y 0 ), (4.10)
where the ψ functions are assumed to satisfy the inequality

3 4 ψ(yu) + 1 4 ψ(-yu) -ψ(y) ≥ 0 ∀ y ∈ [-1, 1], ∀ u ∈ {-1, 1}. (4.11)
If a function φ is even, then 3 4 φ(yu) + 1 4 φ(-yu) -φ(y) ≡ 0 (since u is either equal to 1 or to -1). Therefore, (4.8) is satisfied for all γ ∈ P(G), while (4.9) is converted to G (φ(y 0 ) -φ(y))γ(dy, du) = 0 in this case. The latter equality implies that G |y 0 | l γ(dy, du) = G |y| l γ(dy, du) for any l = 1, 2, ..., which, in turn, implies that γ(Y y 0 ) = 1, where

Y y 0 def = {y : |y| = |y 0 |}.
Thus, the constraints (4.9) ensure that the occupational measures γ generated by the state-control trajectories satisfy the property γ(Y \Y y 0 ) = 0. This is consistent with the system's dynamics (see (3.20)), according to which the only states attended by the state trajectories are y 0 and -y 0 .

Let γ(dy, du)

def = 3 4 δ -|y 0 | (dy) + 1 4 δ |y 0 | (dy) δ κ(y) (du), ξ(dy, du) def = δ y 0 (dy)δ κ(y) (du),
where δ a stands for the Dirac measure concentrated at a, and where κ(y) is equal to 1 for y ∈ [-1, 0] and equal to -1 for y ∈ (0, 1] (that is, for an arbitrary function q(u) on U , U q(u)δ κ(y) (du) = q(1) ∀ y ∈ [-1, 0] and U q(u)δ κ(y) (du) = q(-1) ∀ y ∈ (0, 1]).

Via a direct substitution into (4.8) and (4.9), it can be verified that (γ, ξ) ∈ Ω(y 0 ) (note that it is sufficient to verify the validity of (4.8) and (4.9) only for the even and odd test functions φ(•)). Therefore,

k * (y 0 ) ≤ G yγ(dy, du) = - 1 2 |y 0 |. (4.12)
On the other hand, it can also be verified that the pair of functions ( ψ(y), η(y)),

ψ(y) def = - 1 2 |y|, η(y) def = y + 1 2 |y| , (4.13)
satisfy the relationships

min y∈[-1,1] min u∈{-1,1} y + ( ψ(y 0 ) -ψ(y)) + 3 4 η(yu)) + 1 4 η(-yu) -η(y) = - 1 2 |y 0 |, 3 4 ψ(yu)) + 1 4 ψ(-yu) -ψ(y) = 0 ∀ y ∈ [-1, 1], ∀ u ∈ {-1, 1}.
Therefore (compare the latter with (4.10) and (4.11)),

- 1 2 |y 0 | ≤ d * (y 0 ).
This inequality, along with (4.6) and (4.12), allows one to conclude that the optimal value of the IDLP problem (4.7) and the optimal value of the dual problem (4.10) are equal (that is, the strong duality equality is valid) and also that (γ, ξ) is an optimal solution of the former and ( ψ(y), η(y)) is an optimal solution of the latter. Note that the common optimal value of problems (4.7) and (4.10) coincides with the Cesàro and Abel limits (3.24).

Theorem 4.2 and Corollary 4.3 stated below establish that the optimal values of the augmented IDLP problem and its dual give upper and (respectively) lower bounds for the Cesàro and Abel limits of the optimal values, the existence and the equality of the latter being ensured if there is no duality gap. To state these results, consider the following problem sup

(µ,ψ,η)∈ D(y 0 ) µ def = d * (y 0 ), (4.14)
where (in contrast to (4.3)) the sup is over the set D(y 0 ) consisting of the triplets (µ,

ψ(•), η(•)) ∈ IR × B(Y ) × B(Y ) that for all (y, u) ∈ G satisfy the inequalities k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) -µ ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ 0. (4.15)
Problem (4.14) is a "relaxed" version of the dual problem (4.3) that corresponds to the presentation of the feasible set Ω(y 0 ) in the form (4.22). Note that the optimal value of problem (4.14) can be equivalently represented as

d * (y 0 ) = sup (ψ,η)∈B(Y )×B(Y ) inf (y,u)∈G {k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y)}, (4.16)
where ψ satisfies the second inequality in (4.15) (compare with (4.5)). Note also that

d * (y 0 ) ≤ d * (y 0 ) ≤ k * (y 0 ), (4.17)
the second inequality in (4.17) being established similarly to Proposition 4.1 (see Remark at the end of this section).

Theorem 4.2 The lower and upper Cesàro/Abel limits of the optimal value functions in problems (2.3) and (2.4) satisfy the inequalities:

d * (y 0 ) ≤ lim inf T →∞ v T (y 0 ) ≤ lim sup T →∞ v T (y 0 ) ≤ k * (y 0 ) ∀ y 0 ∈ Y, d * (y 0 ) ≤ lim inf ϵ→0 h ϵ (y 0 ) ≤ lim sup ϵ→0 h ϵ (y 0 ) ≤ k * (y 0 ) ∀ y 0 ∈ Y, (4.18)
where k * (y 0 ) is the optimal value of the augmented IDLP problem (4.1) and d * (y 0 ) is the optimal value of its dual (4.14).

Proof. The proof of the theorem is given in Section 7. □ REMARK. Theorem 4.2 is one of the main results of the paper. The estimates from below were known (see [START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF]) and, in fact, they are relatively easy to be verified (see the proof of Proposition 7.1). The proof of the estimates from above is much more involved. It is based on the use of some dynamic programming and LP related results. Note that the proof we present in this paper is similar to the proof of Theorem 3.1 in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF],

where the estimates from above were obtained in a purely deterministic setting. However, in contrast to the aforementioned theorem, we do not assume that the "before limit" optimal value functions are continuous, this requiring a more fine analysis for establishing the desired results.

Corollary 4.3 Let, for a given y 0 ∈ Y , the strong duality equality be valid:

k * (y 0 ) = d * (y 0 ). (4.19)
Then the Cesàro and Abel limits of the optimal values exist and are equal:

lim T →∞ v T (y 0 ) = lim ϵ→0 h ϵ (y 0 ) = k * (y 0 ) = d * (y 0 ). (4.20) Note that, if k * (y 0 ) = d * (y 0 ) (4.21) (as in Example 1), then, by (4.17), d * (y 0 ) = d * (y 0 ) = k * (y 0 ). That is, (4.19) is valid, with (4.20) taking the form lim T →∞ v T (y 0 ) = lim ϵ→0 h ϵ (y 0 ) = k * (y 0 ) = d * (y 0 ).
REMARK. Note that the set Ω(y 0 ) allows also the representation

Ω(y 0 ) = {(γ, ξ) ∈ P(G) × M + (G)| γ ∈ W, G (φ(y 0 ) -φ(y))γ(dy, du) + G E φ(f (y, u, s)) -φ(y) ξ(dy, du) = 0 for all φ ∈ B(Y )} (4.22)
as well as the representation

Ω(y 0 ) = {(γ, ξ) ∈ P(G) × M + (G)| γ 1 (Q) - G P (Q|y, u)γ(dy, du) = 0 ∀ Borel Q ⊂ Y, ξ 1 (Q) - G P (Q|y, u)ξ(dy, du) + γ 1 (Q) = 1 Q (y 0 ) ∀ Borel Q ⊂ Y }, (4.23)
where γ 1 and ξ 1 are marginals of γ and ξ (see comments at the end of Section 3). Problem (4.1), in which the feasible set is defined in accordance with (4.23), has been considered in [START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF], where it was shown that the corresponding dual problem has the form (4.14) (thus, the second inequality in (4.17) is just a version of the weak duality inequality). Also in [START_REF] Hernandez-Lerma | Infinite linear programming and multichain Markov control processes in uncountable spaces[END_REF], sufficient conditions for the equality (4.19) (the strong duality) to be valid have been studied. Note that the strong duality may not be true in the general case. An example, in which the Cesàro and Abel limits of the optimal values are not equal to each other, and, therefore, by Theorem 4.2, there is a duality gap, is given in [START_REF] Shvartsman | Lack of equality between Abel and Cesáro limits in discrete optimal control and the implied duality gap[END_REF].

As stated in Corollary 4.3, both the limit lim

T →∞ v T (y 0 ) def = v(y 0 ) (4.24)
and the limit lim for any y 0 ∈ Y .

ϵ→0 h ϵ (y 0 ) def = h(y 0 ) (4.
Proof. The proof of the theorem is given in Section 7. □ REMARK. Theorem 4.4 is a stochastic analog of Theorem 4.2 in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF], where a similar statement was established in a deterministic setting. In proving the theorem, we use the dynamic programming and LP related results. Similarly to (4.29), this also implies (4.28). □ Let us conclude this section with an example, in which the limit (4.24) exists for any

y 0 ∈ Y (that is, v T (•) converges to v(•) pointwisely) but the limit function v(•) is discontinuous. Example 2.
Let the dynamics be one-dimensional and be described by the equation

y(t + 1) = u(t)s(t) ∀ t = 0, 1, ... , (4.31)
with Y = [-1, 1] and with U (y) ⊂ IR defined as follows

U (y) = [-1, y] for y ∈ [-1, 0); U (0) = [-1, 1]; U (y) = [y, 1] for y ∈ (0, 1]. (4.32)
Assume that s(t) takes two values: s(t) = 1 with probability 1 2 and s(t) = 1 4 with probability 1 2 . Consider problem (2.3) with k(y, u) = y. It can be readily seen, that, in this example, the control plan π * = {π * t (y), t = 0, 1, ...}, where, for any t = 0, 1, ....,

π * t (y) = -1 for y ∈ [-1, 0] and π * t (y) = y for y ∈ (0, 1], (4.33)
is optimal in problem (2.3) (and in problem (2.4)), the corresponding optimal state-control trajectory being as follows:

u(t) = -1 ∀ t ≥ 0 and y(t) = -s(t -1) ∀ t ≥ 1 if y 0 ∈ [-1, 0]; u(t) = y(t) ∀ t ≥ 0 and y(t) = s(t -1) • • • s(0)y 0 ∀ t ≥ 1 if y 0 ∈ (0, 1]. (4.34)
The optimal value function of the problem (2.3) can be verified to be as follows:

v T (y 0 ) = - 5 8 + 1 T y 0 + 5 8 for y 0 ∈ [-1, 0] and v T (y 0 ) = 1 T 8 3 y 0 1- 5 8 T for y 0 ∈ (0, 1], (4.35) with v(y 0 ) = lim T →∞ v T (y 0 ) = - 5 8 for y 0 ∈ [-1, 0] and v(y 0 ) = lim T →∞ v T (y 0 ) = 0 for y 0 ∈ (0, 1]. (4.36)
The augmented IDLP problem (4.1) takes in this case the form inf

(γ,ξ)∈Ω(y 0 ) G yγ(dy, du) = k * (y 0 ), (4.37)
where Ω(y 0 ) is the set of pairs (γ, ξ) ∈ P(G) × M + (G) that satisfy the equations

G 1 2 φ(u) + 1 2 φ u 4 -φ(y) γ(dy, du) = 0 ∀ φ ∈ C([-1, 1]), (4.38)
G (φ(y) -φ(y 0 ))γ(dy, du) = G 1 2 φ(u) + 1 2 φ u 4 -φ(y) ξ(dy, du) ∀ φ ∈ C([-1, 1]), (4.39)
and where

G = G 1 ∪ G 2 ∪ G 3 , with G 1 def = {(y, u) | u ∈ [-1, y), y ∈ [-1, 0)}, G 2 def = {(0, u) | u ∈ [-1, +1]} and G 3 def = {(y, u) | u ∈ [y, 1], y ∈ (0, 1]}.
The optimal value of the relaxed dual problem is presentable in the form (see (4.16)):

sup (ψ,η)∈B(Y )×B(Y ) inf (y,u)∈G {y + (ψ(y 0 ) -ψ(y)) + 1 2 η(u) + 1 2 η u 4 -η(y)} = d * (y 0 ), (4.40)
where the functions ψ(•) are assumed to satisfy the inequality For

1 2 ψ(u) + 1 2 ψ u 4 -ψ(y) ≥ 0 ∀(y, u) ∈ G (4.
{y + ( ψ(y 0 ) -ψ(y)) + 1 2 η(u) + 1 2 η u 4 -η(y)} = - 5 8 for y 0 ∈ [-1, 0], inf (y,u)∈G {y + ( ψ(y 0 ) -ψ(y)) + 1 2 η(u) + 1 2 η u 4 -η(y)} = 0 for y 0 ∈ (0, 1].
y 0 ∈ [-1, 0], let γ(dy, du) def = 1 2 δ (-1,-1) (dy, du) + 1 2 δ (-1 4 ,-1) (dy, du) , ξ(dy, du) def = δ (y 0 ,-1) (dy, du), (4.45)
where δ (α,β) ∈ P(G) is the Dirac measure concentrated at a point (α, β) ∈ G. It can be readily verified that (γ, ξ) ∈ Ω(y 0 ) (with Ω(y 0 ) being defined by (4.38), (4.39)) and that

k * (y 0 ) ≤ G yγ(dy, du) = - 5 8 .
Due to (4.18), (4.36) and (4.44), the latter implies that

k * (y 0 ) = v(y 0 ) = d * (y 0 ) ∀ y 0 ∈ [-1, 0]. (4.46)
For y 0 ∈ (0, 1], take γ(dy, du)

def = δ (0,0) (dy, du), ξ(dy, du) def = δ (y 0 ,0) (dy, du).
Again, it is easy to verify that (γ, ξ) ∈ Ω(y 0 ) and that

k * (y 0 ) ≤ G yγ(dy, du) = 0.
Therefore, similarly to (4.46), we may conclude that the strong duality equality is valid:

k * (y 0 ) = v(y 0 ) = d * (y 0 ) ∀ y 0 ∈ (0, 1]. (4.47)
In addition, we also may conclude that (γ, ξ) defined in (4.45) is an optimal solution of the IDLP problem (4.37) and that ( ψ(•), η(•)) defined in (4.42) is an optimal solution of the dual problem (4.40).

5 Another representation for the dual optimal value; Periodic regime generating controls Define the set D(y 0 ) ⊂ P(G) by the equation

D(y 0 ) def = γ ∈ M(G) | ∃ ξ ∈ M + (G) such that G (φ(y) -φ(y 0 ))γ(dy, du) = G E φ(f (y, u, s)) -φ(y) ξ(dy, du) ∀ φ ∈ C(Y ) , (5.1)
where M(G) stands for the space of finite signed measures defined on Borel subsets of G. Obviously,

W ∩ D(y 0 ) = {γ | (γ, ξ) ∈ Ω(y 0 )},
and the problem (4.1) can be rewritten as follows:

inf G k(y, u)γ(dy, du) | γ ∈ W ∩ D(y 0 ) = k * (y 0 ). (5.2)
Along with the problem (5.2), let us consider the problem

min G k(y, u)γ(dy, du) | γ ∈ W ∩ D 1 (y 0 ) def = k * * (y 0 ), (5.3)
where

D 1 (y 0 ) = {γ ∈ M(G) | ∃ξ l ∈ M + (G), l = 1, 2, ..., such that G (φ(y) -φ(y 0 ))γ(dy, du) = lim l→∞ G E φ(f (y, u, s)) -φ(y) ξ l (dy, du) ∀ φ ∈ C(Y )}. (5.4)
Note that, as can be readily verified, D 1 (y 0 ) is a convex and weak * closed set, and cl(D(y 0 )) ⊂ D 1 (y 0 ) (with cl(•) standing for the weak * closure).

Proposition 5.1 The following inclusion is valid

lim sup T →∞ Γ T (y 0 ) ⊂ W ∩ D 1 (y 0 ). (5.5)
Proof. Due to (3.11), lim sup T →∞ Γ T (y 0 ) ⊂ W . Hence, we only need to prove that lim sup

T →∞ Γ T (y 0 ) ⊂ D 1 (y 0 ). (5.6)
Take an arbitrary γ ∈ lim sup T →∞ Γ T (y 0 ). By definition of lim sup, it means that there exist a sequence T l → ∞ and a sequence γ l ∈ Γ T l (y 0 ) such that γ l → γ. The fact that γ l ∈ Γ T l (y 0 ) implies that it is generated by some control plans π l with the corresponding state-control trajectory (y π l ,y 0 (•), u π l ,y 0 (•)). That is, γ l = γ π l ,y 0 ,T l , and (see (2.10))

G q(y, u)γ l (dy, du) = 1 T l E T l -1 t=0
q(y π l ,y 0 (t), u π l ,y 0 (t))

for any continuous q(y, u). Using this equality with q(y, u) = φ(y) -φ(y 0 ), we obtain

G (φ(y) -φ(y 0 ))γ l (dy, du) = 1 T l T l -1 t=0 E[φ(y π l ,y 0 (t)) -φ(y 0 )] = 1 T l T l -1 t=0 t-1 t ′ =0 E[φ(y π l ,y 0 (t ′ + 1)) -φ(y π l ,y 0 (t ′ ))] = 1 T l E   T l -1 t=T 0 t-1 t ′ =0 E[φ(f (y π l ,y 0 (t ′ ), u π l ,y 0 (t ′ ), s(t ′ )))|y π l ,y 0 (t ′ )] -φ(y π l ,y 0 (t ′ ))   .
Since E[φ(f (y π l ,y 0 (t ′ ), u π l ,y 0 (t ′ ), s(t ′ )))|y π l ,y 0 (t ′ )] = φ(y π l ,y 0 (t ′ ), u π l ,y 0 (t ′ )) a.s., with φ(y, u)

def = E[φ(f (y, u, s))], (5.7)
we obtain

G (φ(y) -φ(y 0 ))γ l (dy, du) = 1 T l E T l -1 t=0 t-1 t ′ =0 φ(y π l ,y 0 (t ′ ), u π l ,y 0 (t ′ )) -φ(y π l ,y 0 (t ′ )) . (5.8) Define ζ l ∈ C * (G) by the equation ⟨ζ l , q⟩ = 1 T l E T l -1 t=0 t-1 t ′ =0 q(y π l ,y 0 (t ′ ), u π l ,y 0 (t ′ )) ∀ q ∈ C(G).
Due to Riesz representation theorem, there exists

ξ l ∈ M + (G) such that ⟨ζ l , q⟩ = G q(y, u)ξ l (dy, du) ∀ q(•, •) ∈ C(G).
Therefore, (5.8) can be rewritten as

G (φ(y) -φ(y 0 ))γ l (dy, du) = ⟨ζ l , φ(y, u) -φ(y)⟩ = G ( φ(y, u) -φ(y)) ξ l (dy, du).
Passing to the limit with l → ∞ in this equality and having in mind that γ l → γ, we obtain (see also (5.7))

G (φ(y) -φ(y 0 ))γ(dy, du) = lim l→∞ G E φ(f (y, u, s)) -φ(y) ξ l (dy, du) for all φ ∈ C(Y )
Hence (see (5.4)), γ ∈ D 1 (y 0 ). Since γ is an arbitrary element of lim sup T →∞ Γ T (y 0 ), the validity of (5.6) is established. □ From Proposition 5.1 it follows that the optimal value of (5.3) gives a lower bound for lim inf T →∞ v T (y 0 ). This, however, does not provide an improvement for an estimate from below in (4.18) since, as established by the proposition below, the optimal value of (5.3) is equal to the optimal value of the dual problem (4.3).

Proposition 5.2

The optimal value of the problem (5.3) is equal to the optimal value of the problem (4.3):

k * * (y 0 ) = d * (y 0 ). (5.9)
Proof. The proof is given in Section 10.2. □ REMARK. The proof of Proposition 5.2 is based on the fact that the subvalue of an IDLP problem is equal to the optimal value of its dual (see, e.g., Theorem 3 in [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF]).

Corollary 5.3 Assume that, for any continuous k(y, u), the point-wise limit (4.24) exists and the limit optimal value function v(•) is continuous. Then Continuing from this point in the same way as in the proof of Proposition 3.4 (that is, using Blaschke's selection theorem [START_REF] Klein | Theory of correspondence[END_REF]) and the separation theorem [46, p. 59])), one can establish the validity of (5.10). □ Proof. The proof follows from Proposition 5.2 and from (5.2), (5.3). □ REMARK. We do not provide sufficient conditions for the validity of (5.11) in the present paper leaving investigating of this matter for the future research.

lim T →∞ ρ H ( coΓ T (y 0 ), W ∩ D 1 (y 0 )) = 0. ( 5
DEFINITION. For a given y 0 ∈ Y , we will say that a control plan π is periodic regime generating (PRG) if there exist integer T 0 ≥ 0 and T > 0 such that, for any continuous q(y, u), E[q(y π,y 0 (t), u π,y 0 (t))] = E[q(y π,y 0 (t + T ), u π,y 0 (t + T ))] ∀ t ≥ T 0 .

(5.12)

Consider the problem inf

π∈Πper(y 0 ) lim T →∞ 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) def = V per (y 0 ), (5.13)
where Π per (y 0 ) ⊂ Π stands for the set of all PRG control plans. Note that, as can be readily understood,

V per (y 0 ) ≥ lim inf T →∞ v T (y 0 ) ∀ y 0 ∈ Y.
The following statement is valid.

Proposition 5.5 If for some y 0 ∈ Y ,

V per (y 0 ) = lim inf T →∞ v T (y 0 ), (5.14)
then the limit (4.24) exists, and v(y 0 ) = k * (y 0 ).

(5.15)

Proof. Due to the assumed validity of (5.14) and due to the upper bound in (4.18),

V per (y 0 ) ≤ k * (y 0 ). Hence, if one shows that V per (y 0 ) ≥ k * (y 0 ), (5.16)
it would imply k * (y 0 ) = V per (y 0 ) = lim inf

T →∞ v T (y 0 ) ≤ lim sup T →∞ v T (y 0 ) ≤ k * (y 0 ),
which, in turn, would imply the existence of the limit (4.24) and the validity of the equality (5.15). That is, the proposition will be proved if we show that (5.16) is true. Thus, we will be aiming at proving (5.16).

Note that, as mentioned above, the IDLP problem (4.1) can be rewritten in the form (5.2). Note also that problem (5.13) can be equivalently rewritten in the form min

γ∈Γper(y 0 ) G k(y, u)γ(dy, du) = V per (y 0 ), (5.17)
where Γ per (y 0 ) is the set of occupational measures generated by the PRG control plans: γ ∈ Γ per (y 0 ) if and only if

γ(Q) = 1 T E   T 0 +T -1 t=T 0 1 Q (y π,y 0 (t), u π,y 0 (t))   ∀ Borel Q ⊂ G (5.18)
for some π ∈ Π per (y 0 ), with (y π,y 0 (•), u π,y 0 (•)) being the state-control trajectory generated by π and with T 0 , T being as in (5.12). Due to (5.2) and (5.17), the validity of (5.16) will be established if we show that

Γ per ⊂ W ∩ D(y 0 ). (5.19)
It can be readily understood that Γ per (y 0 ) ⊂ lim sup

T →∞ Γ T (y 0 ) ⊂ W
(the latter inclusion follows from (3.11)). Consequently (see (5.1)), to prove (5.19), it is sufficient to prove that, for any γ ∈ Γ per (y 0 ), there exists

ξ ∈ M + (G) such that G (φ(y) -φ(y 0 ))γ(dy, du) = G (E[φ(f (y, u, s))] -φ(y))ξ(dy, du) ∀ φ ∈ C(Y ). (5.20)
To prove that this is the case, observe that, if γ ∈ Γ per (y 0 ), then, by (5.18),

G q(y, u)γ(dy, du) = 1 T E   T 0 +T -1 t=T 0 q(y π,y 0 (t), u π,y 0 (t))  
for any continuous q(y, u). Therefore, for any continuous φ(y),

G (φ(y) -φ(y 0 ))γ(dy, du) = 1 T T 0 +T -1 t=T 0 E[φ(y π,y 0 (t)) -φ(y 0 )] = 1 T T 0 +T -1 t=T 0 E[φ(y π,y 0 (t)) -φ(y π,y 0 (T 0 ))] + E[φ(y π,y 0 (T 0 )) -φ(y 0 )] = 1 T T 0 +T -1 t=T 0   t-1 t ′ =T 0 E[φ(y π,y 0 (t ′ + 1)) -φ(y π,y 0 (t ′ ))]   + T 0 -1 t ′ =0 E[ φ(y π,y 0 (t ′ + 1)) -φ(y π,y 0 (t ′ )) ] = 1 T E   T 0 +T -1 t=T 0   t-1 t ′ =T 0 E[φ(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ )] -φ(y π,y 0 (t ′ ))     +E T 0 -1 t ′ =0 E[φ(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ )] -φ(y π,y 0 (t ′ )) . Since E[φ(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ )] = φ(y π,y 0 (t ′ ), u π,y 0 (t ′ )) a.s., with φ(y, u) def = E[φ(f (y, u, s))], (5.21)
we obtain

G (φ(y) -φ(y 0 ))γ(dy, du) = 1 T E   T 0 +T -1 t=T 0   t-1 t ′ =T 0 φ(y π,y 0 (t ′ ), u π,y 0 (t ′ )) -φ(y π,y 0 (t ′ ))     +E T 0 -1 t ′ =0
φ(y π,y 0 (t ′ ), u π,y 0 (t ′ )) -φ(y π,y 0 (t ′ )) .

(5.22)

Define ζ ∈ C * (G) by the equation ⟨ζ, q⟩ = 1 T E   T 0 +T -1 t=T 0 t-1 t ′ =T 0 q(y π,y 0 (t ′ ), u π,y 0 (t ′ ))   + E T 0 -1 t ′ =0 q(y π,y 0 (t ′ ), u π,y 0 (t ′ )) ∀ q ∈ C(G).
Due to Riesz representation theorem, there exists ξ ∈ M + (G) such that ⟨ζ, q⟩ = G q(y, u)ξ(dy, du) ∀ q ∈ C(G).

Therefore, (5.22) can be rewritten as

G (φ(y) -φ(y 0 ))γ(dy, du) = ⟨ζ, φ(y, u) -φ(y)⟩ = G ( φ(y, u) -φ(y)) ξ(dy, du).
In accordance with the definition of φ(y, u) (see (5.21)), the latter is equivalent to (5.20). This completes the proof of the proposition. □ Example 1 (continuation). Let us show that the optimal control plan π * defined in (3.21) is PRG. In fact, the use of π * leads to that, for any t ≥ 0, y π * ,y 0 (t + 1) = -y π * ,y 0 (t) with probability 3/4, y π * ,y 0 (t) with probability 1/4 if y π * ,y 0 (t) > 0, and for any t ≥ 0. Thus,

y π * ,y 0 (t + 1) = -y π * ,
E[q(y π * ,y 0 (t), u π * ,y 0 (t))] = 3 4 q(-|y 0 |, 1) + 1 4 q(|y 0 |, -1) ∀ t ≥ 1,
for any continuous q(y, u). Consequently, (5.12) is satisfied with T 0 = 1 and T = 1.

Example 2 (continuation). The optimal control plan defined by (4.33) is PRG for y 0 ∈ [-1, 0] since in this case (see (4.34))

E[q(y(t), u(t))] = 1 2 q(-1, -1) + 1 2 q(-1, - 1 4 )
∀ t ≥ 1.

However, this control plan is not PRG for y 0 ∈ (0, 1].

6 Sufficient and necessary conditions for long-run average optimality

DEFINITION. A pair ( ψ(•), η(•)) ∈ B(Y ) × B (
Y ) will be called an optimal solution of (4.14) if it satisfies the inequalities (compare with (4.15))

k(y, u) + ( ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) ≥ d * (y 0 ), E[ ψ(f (y, u, s))] -ψ(y) ≥ 0 (6.1)
for all (y, u) ∈ G. Also, (6.5) is equivalent to (6.3) (due to (6.2)). Thus (a) is proved.

If η(•) is such that (6.4) is satisfied, then the pair ( ψ(•), η(•)), where ψ(•) = v(•), satisfies (6.3). Therefore, due to (a) and due to the fact that v(•) satisfies the second inequality in (4.15) (see (7.46) below), this pair is an optimal solution of (4.14). This proves (b). □

Consider the optimal control problem inf π∈Π lim sup

T →∞ 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) def = V (y 0 ). (6.6)
As can be readily seen,

V (y 0 ) ≥ lim inf T →∞ v T (y 0 ), (6.7)
and, therefore, V (y 0 ) ≥ d * (y 0 ). (6.8)

The following proposition gives sufficient conditions for a control plan π to be optimal in (6.6) and for the equality V (y 0 ) = d * (y 0 ) (6.9) to be valid. Proposition 6.2 Let an optimal solution ( ψ(•), η(•)) of (4.14) exist. For a control plan π ∈ Π with the associated state-control trajectory (y π,y 0 (•), u π,y 0 (•)) to be optimal in problem (6.6) and for the equality (6.9) to be valid, it is sufficient that there exists an integer T 0 > 0 such that k(y π,y 0 (t), u π,y 0 (t)) + ( ψ(y 0 ) -ψ(y π,y 0 (t))) + E η(f (y π,y 0 (t), u π,y 0 (t), s(t)))|y π,y 0 (t)

-η(y π,y 0 (t)) = d * (y 0 ) a.s. ∀ t ≥ T 0 , (6.10)
and E[ ψ(y π,y 0 (t))] = ψ(y 0 ) ∀ t ≥ T 0 . (6.11)

Proof. Taking the mathematical expectation of the sum (from t = T 0 to T -1, with T ≥ T 0 + 1) of the equations in (6.10) and taking into account (6.11), one can obtain (similarly to (7.5)):

1 T E   T -1 t=T 0 k(y π,y 0 (t), u π,y 0 (t))   + 1 T E   T -1
t=T 0 E[η f (y π,y 0 (t), u π,y 0 (t), s(t)) |y π,y 0 (t)] -η(y π,y 0 (t))

  = 1 T E   T -1 t=T 0 k(y π,y 0 (t), u π,y 0 (t))   + 1 T E   T -1
t=T 0 E[η(y π,y 0 (t + 1))|y π,y 0 (t)] -η(y π,y 0 (t))

  = 1 T E   T -1 t=T 0 k(y π,y 0 (t), u π,y 0 (t))   + 1 T E   T -1
t=T 0 η(y π,y 0 (t + 1)) -η(y π,y 0 (t))

  = 1 T E   T -1 t=T 0 k(y π,y 0 (t), u π,y 0 (t))   + 1 T E [η(y π,y 0 (T )) -η(y π,y 0 (T 0 ))] = T -T 0 T d * (y 0 ).
Therefore,

1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) = T -T 0 T d * (y 0 ) + 1 T E T 0 -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) - 1 T E [η(y π,y 0 (T )) -η(y π,y 0 (T 0 ))] ,
and, consequently, lim

T →∞ 1 T E T -1 t=0
k(y π,y 0 (t), u π,y 0 (t)) = d * (y 0 ). Thus, by (6.8), π is optimal in (6.6), and (6.9) is valid. □

Let us now establish that the fulfillment of (6.10), (6.11) is also a necessary condition for a PRG control plan π to be optimal and for (6.9) to be valid. Proposition 6.3 Let an optimal solution ( ψ(•), η(•)) of (4.14) exist. If a PRG control plan π (that is, a control plan such that (5.12) is satisfied) is optimal in (6.6) and if (6.9) is valid, then (6.10) and (6.11) are satisfied for any t ≥ T 0 , where T 0 is as in (5.12).

Proof. Due to optimality of the PRG control plan π and due to (5.12), (6.9), d * (y 0 ) = lim

T →∞ 1 T E T -1 t ′ =0 k(y π,y 0 (t ′ ), u π,y 0 (t ′ )) = 1 T E t+T -1 t ′ =t
k(y π,y 0 (t ′ ), u π,y 0 (t ′ )) ∀ t ≥ T 0 . (6.12) By (6.1), the following inequalities hold true:

k(y π,y 0 (t ′ ), u π,y 0 (t ′ )) + ( ψ(y 0 ) -ψ(y π,y 0 (t ′ ))) + E η(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ ) -η(y π,y 0 (t ′ )) ≥ d * (y 0 ) a.s. ∀ t ′ = 0, 1, ... (6.13)

E[ ψ(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ )] -ψ(y π,y 0 (t ′ )) ≥ 0 a.s. ∀ t ′ = 0, 1, ... . (6.14)
Take an arbitrary t ≥ T 0 and take the mathematical expectation of the sum of the inequalities (6.13) from t ′ = t to t ′ = t + T -1. Using (6.12), one obtains t+T -1

t ′ =t E[ ψ(y 0 ) -ψ(y π,y 0 (t ′ ))] + E t+T -1 t ′ =t
E η(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ ) -η(y π,y 0 (t ′ )) ≥ 0.

(6.15) By (5.12),

E t+T -1 t ′ =t E η(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ ) -η(y π,y 0 (t ′ )) = E t+T -1 t ′ =t η(y π,y 0 (t ′ + 1)) -η(y π,y 0 (t ′ )) = E[η(y π,y 0 (t + T ))] -E[η(y π,y 0 (t))] = 0. (6.16)
Hence, from (6.15) it follows that t+T -1

t ′ =t E[ ψ(y 0 ) -ψ(y π,y 0 (t ′ ))] ≥ 0.
(6.17)

From (6.14), on the other hand, it follows that

E[ ψ(y π,y 0 (t ′ + 1)) -ψ(y π,y 0 (t ′ ))] ≥ 0 ∀ t ′ = 0, 1, ... ⇒ E[ ψ(y π,y 0 (t ′ )) -ψ(y 0 )] ≥ 0 ∀ t ′ = 0, 1, ... .
The and (6.17) imply that E[ ψ(y 0 ) -ψ(y π,y 0 (t ′ ))] = 0 ∀ t ′ = t, t + 1, ..., t + T -1, (6.18) which, in turn, implies (6.11) (since t is an arbitrary integer that is greater or equal than T 0 ).

Let us now show that the inequality (6.13) is satisfied a.s. as the equality for any t ′ = t ≥ T 0 . Assume it is not the case. Then E k(y π,y 0 (t), u π,y 0 (t)) + ( ψ(y 0 ) -ψ(y π,y 0 (t))) + E η(f (y π,y 0 (t), u π,y 0 (t), s(t)))|y π,y 0 (t)

-η(y π,y 0 (t)) > d * (y 0 ), and, consequently,

1 T E t+T -1 t ′ =t k(y π,y 0 (t ′ ), u π,y 0 (t ′ )) + 1 T E t+T -1 t ′ =t ψ(y 0 ) -ψ(y π,y 0 (t ′ )) + 1 T E t+T -1 t ′ =t E η(f (y π,y 0 (t ′ ), u π,y 0 (t ′ ), s(t ′ )))|y π,y 0 (t ′ ) -η(y π,y 0 (t ′ )) > d * (y 0 ).
By virtue of (6.16) and (6.18), this leads to

1 T E t+T -1 t ′ =t
k(y π,y 0 (t ′ ), u π,y 0 (t ′ )) > d * (y 0 ), which contradicts (6.12). This contradiction proves the required statement. □ REMARK. In accordance with Propositions 6.2 and 6.3, for a control plan π to be optimal it is sufficient and also necessary (if it is PRG) that the corresponding state-control trajectory (y π,y 0 (t), u π,y 0 (t)) satisfies the equalities (6.10), (6.11) for t ≥ T 0 (T 0 being some positive integer). Note that, by (6.3), the equality (6.10) is equivalent to (y π,y 0 (t), u π,y 0 (t)) = argmin (y,u)∈G {k(y, u) -ψ(y) + η(y, u) -η(y)} a.s. ∀ t ≥ T 0 , where η(y, u)

def = E[η(f (y, u, s))]
. This leads to u π,y 0 (t) = argmin u∈U (y π,y 0 (t)) {k(y π,y 0 (t), u) + η(y π,y 0 (t), u)} a.s. ∀ t ≥ T 0 , which, in turn, implies that the feedback control

u f (y) def = argmin u∈U (y) {k(y, u) + η(y, u)} = argmin u∈U (y) {k(y, u) + E[η(f (y, u, s))]} (6.19)
is optimal for T ≥ T 0 provided that the solution of system (2.1) obtained with the use of this control satisfies (6.11).

Example 1 (continuation). The pair of functions ( ψ(y), η(y)) defined in (4.13) is an optimal solution of the dual problem (4.10) in this case, and it can be readily verified that

E[η(f (y, u, s))] = E[η(yus)] = 3 4 η(yu) + 1 4 η(-yu) = 1 2 yu + 1 2 |y|.
Therefore, the feedback control (6.19) takes the form

u f (y) = argmin u∈{-1,1} {y + 1 2 yu + 1 2 |y|} = 1 if y ∈ [-1, 0) -1 if y ∈ (0, 1].
That is, by using formula (6.19), we obtain the optimal control plan π * (see (

u f (y) = argmin u∈[-1,y] y + 5 8 u + 5 8 = -1 if y ∈ [-1, 0), u f (y) = argmin u∈[-1,1] y + 5 8 u + 5 8 = -1 if y = 0, u f (y) = argmin u∈[y,1] y + 5 3 u = y if y ∈ (0, 1].
That is, (6.19) defines the optimal control plan π * in this example too (see (4.33)). Note that the state trajectory obtained with the use of this control plan satisfies (6.11) (see (4.34) and (4.42)).

In Example 1, the pair consisting of the first term and the second term multiplied by T in the expressions for the optimal value v T (•) (see (3.22)) coincides with the optimal solution (4.13) of the dual problem (4.10). Similarly, in Example 2, the pair consisting of the first term and the limit as T → ∞ of the second term (multiplied by T ) in the expressions for the optimal value v T (•) (see (4.35)) coincides with the optimal solution (4.42) of the dual problem (4.40).

We conclude this section with a statement that gives sufficient conditions for this to be true in the general case. (Note that all these conditions are satisfied in both Example 1 and Example 2.) Proposition 6.4 Assume that the following conditions are satisfied:

(i) The optimal value functions v T (y 0 ) is presented in the form

v T (y 0 ) = v(y 0 ) + 1 T η T (y 0 ) ∀ y 0 ∈ G; (6.20)
(ii) The equality (6.2) is valid for any y 0 ∈ Y and Proof. Firstly, note that from (2.6) it follows that inf

E[v(f (y 0 , u, s))] = v(y 0 ) ∀ u ∈ U (y 0 ), ∀ y 0 ∈ G; ( 6
(y,u)∈G {-T v T (y) + k(y, u) + (T -1)E[v T -1 (f (y, u, s))]} = 0, T = 1, 2, ... . (6.23)
By substituting (6.20) into (6.23), we obtain inf The proof of Theorem 4.2 follows from Propositions 7.1 and 7.3 that are stated and proved below.

(y,u)∈G {-T v(y) -η T (y) + k(y, u) + (T -1)E[v(f (y, u, s))] + E[η T -1 (f (y, u, s))]} = 0, T = 1,
Proposition 7.1 The following estimates are valid:

lim inf T →∞ v T (y 0 ) ≥ d * (y 0 ) ∀ y 0 ∈ Y, lim inf ϵ→0 h ϵ (y 0 ) ≥ d * (y 0 ) ∀ y 0 ∈ Y.
T ′ →∞ v T ′ (y 0 ) + β,
for all (y, u) ∈ G. From the latter, it follows that for any control plan π ∈ Π with the associated state-control trajectory (y π,y 0 (•), u π,y 0 (•)), E k(y π,y 0 (t), u π,y 0 (t)) + (ψ(y 0 ) -ψ(y π,y 0 (t))) + η(y π,y 0 (t), u π,y 0 (t)) -η(y π,y 0 (t))

≥ lim inf

T ′ →∞ v T ′ (y 0 ) + β ∀ t = 0, 1, . . . (7.2)
where η(y, u)

def = E[η(f (y, u, s))]. (7.3)
Due to the fact that ψ(•) satisfies the second inequality in (4.15), E ψ(y π,y 0 (t + 1)) -ψ(y π,y 0 (t)) = E E[ψ(y π,y 0 (t + 1))|y π,y 0 (t)] -ψ(y π,y 0 (t))

= E E ψ f (y π,y 0 (t), u π,y 0 (t), s(t)) |y π,y 0 (t) -ψ(y π,y 0 (t)) ≥ 0 ∀ t = 0, 1, . . . .

Consequently, E ψ(y π,y 0 (t)) -ψ(y 0 ) ≥ 0 ∀ t = 0, 1, . . . , (7.4) and from (7.2) it follows that E k(y π,y 0 (t), u π,y 0 (t)) + η(y π,y 0 (t), u π,y 0 (t)) -η(y π,y 0 (t))

≥ lim inf

T ′ →∞ v T ′ (y 0 ) + β ∀ t = 0, 1, . . . ,
which, in accordance with (7.3), is equivalent to

E[k(y π,y 0 (t), u π,y 0 (t))] + E E[η f (y π,y 0 (t), u π,y 0 (t), s(t)) |y π,y 0 (t)] -η(y π,y 0 (t))
≥ lim inf

T ′ →∞ v T ′ (y 0 ) + β ∀ t = 0, 1, . . . .

From these inequalities it follows that

1

T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) + 1 T E T -1 t=0
E[η f (y π,y 0 (t), u π,y 0 (t), s(t)) |y π,y 0 (t)] -η(y π,y 0 (t))

= 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) + 1 T E T -1 t=0 E[η(y π,y 0 (t + 1))|y π,y 0 (t)] -η(y π,y 0 (t)) = 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) + 1 T E T -1 t=0 η(y π,y 0 (t + 1)) -η(y π,y 0 (t)) = 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) + 1 T E [η(y π,y 0 (T )) -η(y π,y 0 (0))] ≥ lim inf T ′ →∞ v T ′ (y 0 ) + β. (7.5) Hence, 1 T E T -1 t=0 k(y π,y 0 (t), u π,y 0 (t)) + 1 T sup y∈Y η(y) -η(y 0 ) ≥ lim inf T ′ →∞ v T ′ (y 0 ) + β.
Since the above inequality holds for any control plan π ∈ Π, we may conclude that

v T (y 0 ) + 1 T sup y∈Y η(y) -η(y 0 ) ≥ lim inf T ′ →∞ v T ′ (y 0 ) + β.
By taking lim inf T →∞ in the left-hand side of this expression, one obtains a contradiction. Thus, the first inequality in (7.1) is proved.

Let us now prove the second inequality in (7.1). Assume it is not true. Then there exists β > 0 and a pair of functions (ψ(•), η(•)) ∈ B(Y ) × B(Y ), with ψ(•) satisfying the second inequality of (4.15) such that

k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) ≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β.
It follows that, for any control plan π ∈ Π with the associated state-control trajectory (y π,y 0 (•), u π,y 0 (•)), E k(y π,y 0 (t), u π,y 0 (t)) + (ψ(y 0 ) -ψ(y π,y 0 (t))) + η(y π,y 0 (t), u π,y 0 (t)) -η(y π,y 0 (t))

≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β ∀ t = 0, 1, . . . ,
where η(y, u) is as in (7.3). By (7.4), the latter implies that E k(y π,y 0 (t), u π,y 0 (t)) + η(y π,y 0 (t), u π,y 0 (t)) -η(y π,y 0 (t))

≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β ∀ t = 0, 1, . . . ,
which, in view of (7.3), can be rewritten as follows

E[k(y π,y 0 (t), u π,y 0 (t))] + E E[η f (y π,y 0 (t), u π,y 0 (t), s(t)) |y π,y 0 (t) -η(y π,y 0 (t))] ≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β.
Hence, for any ϵ ∈ (0, 1),

ϵE ∞ t=0 (1 -ϵ) t k(y π,y 0 (t), u π,y 0 (t)) + ϵ ∞ t=0 (1 -ϵ) t E [E[η(y π,y 0 (t), u π,y 0 (t), s(t))|y π,y 0 (t)] -η(y π,y 0 (t))] = ϵE ∞ t=0 (1 -ϵ) t k(y π,y 0 (t), u π,y 0 (t)) + ϵ ∞ t=0 (1 -ϵ) t E [E[η(y π,y 0 (t + 1))|y π,y 0 (t)] -η(y π,y 0 (t))] = ϵE ∞ t=0 (1 -ϵ) t k(y π,y 0 (t), u π,y 0 (t)) + ϵ ∞ t=0 (1 -ϵ) t E [η(y π,y 0 (t + 1)) -η(y π,y 0 (t))] ≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β. (7.6)
One may verify that

k t=0 (1 -ϵ) t E [η(y π,y 0 (t + 1)) -η(y π,y 0 (t))] = E -η(y 0 ) + (1 -ϵ) k η(y π,y 0 (k + 1)) + ϵ k t=1 (1 -ϵ) t-1 η(y π,y 0 (t))
for any k = 1, 2, . . .. This implies the validity of the following inequalities:

ϵ k t=0 (1 -ϵ) t E[η(y π,y 0 (t + 1)) -η(y π,y 0 (t))] ≤ ϵE |η(y 0 )| + (1 -ϵ) k |η(y π,y 0 (k + 1))| + ϵ k t=1 (1 -ϵ) t-1 |η(y π,y 0 (t))| ≤ 3ϵM η , (7.7)
where M η def = sup y∈Y |η(y)|. From (7.6) and (7.7) it follows that

ϵE ∞ t=0 (1 -ϵ) t k(y π,y 0 (t), u π,y 0 (t)) + 3ϵM η ≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β.
Since this inequality is valid for any control plan π ∈ Π, we may conclude that

h ϵ (y 0 ) + 3ϵM η ≥ lim inf ϵ ′ →0 h ϵ ′ (y 0 ) + β.
By taking lim inf ϵ→0 in the left-hand-side of the expression above, we obtain a contradiction. This proves the second inequality in (7.1). □

The proof of the estimates from above in (4.18) is based on the following lemma. Proof. Take an arbitrary γ ∈ W . It is well known that the measure γ can be represented as follows:

γ(dy, du) = π(du|y)γ 1 (dy),
where γ 1 is the marginal of γ on Y . Note that the stochastic kernel π(du|y) can be associated with a randomized stationary policy, under which the induced state-control process has the invariant probability measure γ, with γ 1 being the corresponding invariant probability measure of the state process under the policy π. That is,

γ 1 (Q) = Y P π (Q|y)γ 1 (dy), ∀ Borel Q ⊂ Y,
where P π (Q|y) = Û P (Q|y, u)π(du|y), P (Q|y, u) being defined in (3.30).

Under our assumptions about the model, v T (y), which originally was defined as the optimal value function for "non-randomized" controls, will remain such in case the randomized controls are allowed (see, e.g., Sections 3.2, 3.3 in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF] or Theorem 2(iii) in [START_REF] Feinberg | Average cost Markov decision processes with weakly continuous transition probabilities[END_REF]). Therefore, T G v T (y) γ(dy, du) = T Y v T (y) γ 1 (dy) can be interpreted as the optimal T -stage cost for the initial distribution γ 1 , and

T G v T (y) γ(dy, du) ≤ T G k(y, u) γ(dy, du) (7.10)
since the right-hand-side in the expression above represents the total cost after T stages provided that the process starts from the initial distribution γ 1 and it is controlled by the stationary policy π. By dividing (7.10) by T , we obtain (7.8).

Let us now prove (7.9). The optimal value function in the infinite horizon problem with time discounting, h ϵ (y), being defined for the class of non-randomized controls, remains such in case the randomized controls are allowed (see, e.g., Section 4.2 in [START_REF] Hernandez-Lerma | Discrete-time Markov control processes[END_REF] or Theorem 2(v) in [START_REF] Feinberg | Average cost Markov decision processes with weakly continuous transition probabilities[END_REF]). Therefore, ϵ -1 G h ϵ (y) γ(dy, du) = ϵ -1 Y h ϵ (y) γ 1 (dy) is the optimal infinite horizon cost for the initial distribution γ 1 . Since the expression ϵ -1 G k(y, u) γ(dy, du) represents the total infinite horizon discounted cost in case the process starts from the initial distribution γ 1 and the stationary control policy π is used, we may write down

ϵ -1 G h ϵ (y) γ(dy, du) ≤ ϵ -1 G k(y, u) γ(dy, du).
Multiplying the latter by ϵ, we obtain (7.9). □ REMARK. The proof above was proposed by an anonymous reviewer. It is much shorter than the original authors' proof, which was similar to the proof of Lemma 3.2 in [START_REF] Borkar | formulations of discrete time long-run average optimal control problems: The nonergodic case[END_REF]. Note that, the latter, in contrast to the former, was not based on results that establish the optimality of non-randomized controls.

Proposition 7. [START_REF] Anderson | Linear programming in infinite-dimensional spaces[END_REF] The following estimates are valid:

lim sup T →∞ v T (y 0 ) ≤ k * (y 0 ) ∀ y 0 ∈ Y, lim sup ϵ→0 h ϵ (y 0 ) ≤ k * (y 0 ) ∀ y 0 ∈ Y. (7.11)
Proof. Let us prove the first inequality in (7.11). Due to the fact that the function v T (•) is lower semicontinuous, there exists a sequence of continuous functions v l,T (•), l = 1, 2, ..., such that (see, e.g., Theorem A6.6 in [START_REF] Ash | Measure, integration and functional analysis[END_REF]). Let

v l,T (y) ≤ v l+1,T (y) ≤ v T (y) ∀ y ∈ Y, ∀ l = 1,
κ l,T (y) def
= v T (y) -v l,T (y). (7.14)
Note that, by (7.12) and (7.

ψ(y 0 ) def = d * l (T, y 0 ), where Q l (T ) is the set of pairs (ψ(•), η(•)) ∈ C(Y ) × C(Y ) that satisfy the inequalities k(y, u) -ψ(y) + E[η(f (y, u, s))] -η(y) ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ - 2M T -E[κ l,T (f (y, u, s))] ∀ (y, u) ∈ G. (7.16)
Let us show that, for an arbitrary small β > 0 and for every l = 1, 2, ..., there exists a function

η l,T,β (•) ∈ C(Y ) such that (ψ l,T,β (•), η l,T,β (•)) ∈ Q l (T ), where ψ l,T,β (•) def = v l,T (•) -β. (7.17)
Note that, if the inclusion above is established, it would imply that

v l,T (y 0 ) -β ≤ d * l (T, y 0 ). (7.18)
Let us first verify that there exists η l,T,β (•) ∈ C(Y ) such that the pair (ψ l,T,β (•), η l,T,β (•)) satisfies the first inequality in (7.16). To this end, note that the inequality (7.8) is equivalent to the inequality

G (k(y, u) -v T (y)) γ(dy, du) ≥ 0 for all γ ∈ W,
which, due to the fact that v l,T (y) ≤ v T (y) (see (7.12)), implies that G (k(y, u) -v l,T (y)) γ(dy, du) ≥ 0 for all γ ∈ W.

The latter, in turn, is equivalent to

min γ∈W G (k(y, u) -v l,T (y)) γ(dy, du) ≥ 0. ( 7.19)
The problem on the left hand side of (7.19), i.e.,

min γ∈W G (k(y, u) -v l,T (y)) γ(dy, du), (7.20)
is an IDLP problem, which is similar to (3.4) (with k(y, u) -v l,T (y) instead of k(y, u) in the objective function). The problem dual to (7.20) is of the form (compare with (3.6))

sup

η∈C(Y ) inf (y,u)∈G {k(y, u) -v l,T (y) + E[η(f (y, u, s))] -η(y)}. (7.21)
By Proposition 3.1, the optimal values of (7.20) and (7.21) are equal. Therefore, (7.19) is equivalent to

sup η∈C(Y ) inf (y,u)∈G {k(y, u) -v l,T (y) + E[η(f (y, u, s))] -η(y)} ≥ 0. (7.22) From (7.22)
it follows that, for any β > 0, there exists a function η l,T,β (•) ∈ C(Y ) such that k(y, u) -v l,T (y) + E[η l,T,β (f (y, u, s))] -η l,T,β (y) ≥ -β for all (y, u) ∈ G.

The latter implies that the pair (ψ l,T,β (•), η l,T,β (•)), where ψ l,T,β (•) := v l,T (•) -β, satisfies the first inequality in (7.16). Let us now verify that the function ψ l,T,β (•) = v l,T (•) -β satisfies the second inequality in (7.16).

In accordance with the dynamic programming principle (see (2.6)), for any T ≥ 1,

T v T (y) ≤ k(y, u) + (T -1)E[v T -1 (f (y, u, s))] ∀ (y, u) ∈ G. (7.23)
Also, as can be readily seen,

(T -1)E[v T -1 (f (y, u, s))] ≤ T E[v T (f (y, u, s))] + M ∀ (y, u) ∈ G, (7.24)
where M is as in (7.13). By (7.23) and (7.24),

T v T (y) ≤ k(y, u) + T E[v T (f (y, u, s))] + M ≤ T E[v T (f (y, u, s))] + 2M.
Consequently (having in mind (7.14)),

v l,T (y) ≤ v T (y) ≤ E[v l,T (f (y, u, s))] + 2M T + E[κ l,T (f (y, u, s))] ⇒ ψ l,T,β (y) ≤ E[ψ l,T,β (f (y, u, s))] + 2M T + E[κ l,T (f (y, u, s))].
Thus, ψ l,T,β (•) = v l,T (•) -β satisfies the second inequality in (7.16). Hence, (7.17) is valid and, consequently, (7.18) is valid too. Moreover, the latter implies that

v l,T (y 0 ) ≤ d * l (T, y 0 ) (7.25)
since β > 0 in (7.18) is arbitrary small. By Lemma 10.1,

d * l (T, y 0 ) ≤ k * l (T, y 0 ), (7.26)
where

k * l (T, y 0 ) def = inf (γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) + 2M T G ξ(dy, du) + G E[κ l,T (f (y, u, s))]ξ(dy, du) .
(Note that, to adjust the notations used above and the notations used in Lemma 10.1, one should write d * l (T, y 0 ) and k * l (T, y 0 ) as d * θ T,l (y 0 ) and k * θ T,l (y 0 ), where θ T,l (y, u) = 2M T + E[κ l,T (f (y, u, s))].) From (7.25) and (7.26) it follows that v l,T (y 0 ) ≤ k * l (T, y 0 ). (

As can be readily seen, k * l (T, y 0 ) is monotone decreasing in l (due to (7.15)). Therefore, there exists a limit lim l→∞ k * l (T, y 0 ). Let us show that lim

l→∞ k * l (T, y 0 ) = k * (T, y 0 ), (7.28)
where

k * (T, y 0 ) def = inf (γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) + 2M T G ξ(dy, du) .
Firstly, note that lim l→∞ k * l (T, y 0 ) ≥ k * (T, y 0 ) (since k * l (T, y 0 ) ≥ k * (T, y 0 ) for any l = 1, 2, ...). To show the validity of the opposite inequality, take an arbitrary small β > 0 and choose (γ

′ , ξ ′ ) ∈ Ω(y 0 ) such that G k(y, u)γ ′ (dy, du) + 2M T G ξ ′ (dy, du) ≤ k * (T, y 0 ) + β. Then k * l (y 0 , T ) ≤ Y ×U k(y, u)γ ′ (dy, du) + 2M T Y ×U ξ ′ (dy, du) + G E[κ l,T (f (y, u, s))]ξ ′ (dy, du) ≤ k * (y 0 , T ) + β + G E[κ l,T (f (y, u, s))]ξ ′ (dy, du).
Since lim l→∞ G E[κ l,T (f (y, u, s))]ξ ′ (dy, du) = 0 (by (7.15) and the Monotone Convergence Theorem; see, e.g., Theorem 1.6.2 in [START_REF] Ash | Measure, integration and functional analysis[END_REF]), it follows that

lim l→∞ k * l (y 0 , T ) ≤ k * (y 0 , T ) + β ⇒ lim l→∞ k * l (y 0 , T ) ≤ k * (y 0 , T )
(the latter being due to the fact that β is arbitrary small). Thus, (7.28) is valid, and (along with (7.12) and (7.27)) it implies that v T (y 0 ) ≤ k * (T, y 0 ). (

The function k * (T, y 0 ) is monotone decreasing in T and k * (T, y 0 ) ≥ k * (y 0 ) for any T . Therefore, there exists a limit lim T →∞ k * (T, y 0 ) ≥ k * (y 0 ). In fact, arguing as above, one can establish that lim

T →∞ k * (T, y 0 ) = k * (y 0 ).
This and (7.29) establish the validity of the first inequality in (7.11).

Let us now prove the second inequality in (7.11) (this proof being very similar to that of the first one). Since that the function h ϵ (•) is lower semicontinuous, there exists a sequence of continuous functions h l,ϵ (•), l = 1, 2, ..., such that

h l,ϵ (y) ≤ h l+1,ϵ (y) ≤ h ϵ (y) ∀ y ∈ Y, ∀ l = 1, 2, ..., and lim l→∞ h l,ϵ (y) = h ϵ (y) ∀ y ∈ Y (7.30)
and, for any l = 1, 2, ...,

max y∈Y |h l,ϵ (y)| ≤ sup y∈Y |h ϵ (y)| ≤ max y∈Y |k(y, u)| = M. (7.31)
(see Theorem A6.6 in [START_REF] Ash | Measure, integration and functional analysis[END_REF]). Let κ l,ϵ (y)

def = h ϵ (y) -h l,ϵ (y).
Note that, by (7.30) and (7.31), 0 ≤ κ l+1,ϵ (y) ≤ κ l,ϵ (y) ≤ 2M ∀ y ∈ Y, l = 1, 2, ..., and lim

l→∞ κ l,ϵ (y) = 0 ∀ y ∈ Y.
Consider the IDLP problem sup

(ψ,η)∈Q l (ϵ) ψ(y 0 ) def = d * l (ϵ, y 0 ), where Q l (ϵ) is the set of pairs (ψ(•), η(•)) ∈ C(Y ) × C(Y ) that satisfy the inequalities k(y, u) -ψ(y) + E[η(f (y, u, s))] -η(y) ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ -2M ϵ -E[κ l,ϵ (f (y, u, s))] ∀ (y, u) ∈ G. (7.32)
Let us show that, for an arbitrary small β > 0, there exists a function

η l,ϵ,β (•) ∈ C(Y ) such that (ψ l,ϵ,β (•), η l,ϵ,β (•)) ∈ Q l (ϵ), where ψ l,ϵ,β (•) def = h l,ϵ (•) -β, (7.33)
with the inclusion above implying that

h l,ϵ (y 0 ) -β ≤ d * l (ϵ, y 0 ). (7.34)
To verify (7.33), let us first show that there exists η l,ϵ,β (•) ∈ C(Y ) such that the pair (ψ l,ϵ,β (•), η l,ϵ,β (•)) satisfies the first inequality in (7.32). To this end, let us rewrite the inequality (7.9) in the form

G (k(y, u) -h ϵ (y)) γ(dy, du) ≥ 0 ∀ γ ∈ W.
By (7.30), the latter implies

G (k(y, u) -h l,ϵ (y)) γ(dy, du) ≥ 0 ∀ γ ∈ W, which is equivalent to min γ∈W G (k(y, u) -h l,ϵ (y)) γ(dy, du) ≥ 0. ( 7.35)
The problem on the left hand side of (7.35), i.e.,

min γ∈W G (k(y, u) -h l,ϵ (y)) γ(dy, du), (7.36)
is an IDLP problem, which is similar to (3.4) (with k(y, u) -h l,ϵ (y) instead of k(y, u) in the objective function). The problem dual to (7.36) is of the form (compare with (3.6))

sup

η∈C(Y ) inf (y,u)∈G {k(y, u) -h l,ϵ (y) + E[η(f (y, u, s))] -η(y)}. (7.37)
By Proposition 3.1, the optimal values of (7.36) and (7.37) are equal. Therefore, (7.35) is equivalent to

sup η∈C(Y ) inf (y,u)∈G {k(y, u) -h l,ϵ (y) + E[η(f (y, u, s))] -η(y)} ≥ 0. (7.38)
From (7.38) it follows that, for any β > 0, there exists a function

η l,ϵ,β (•) ∈ C(Y ) such that k(y, u) -h l,ϵ (y) + E[η l,ϵ,β (f (y, u, s))] -η l,ϵ,β (y) ≥ -β ∀ (y, u) ∈ G.
The latter implies that the pair (ψ l,ϵ,β (•), η l,ϵ,β (•)), where ψ l,ϵ,β (•) := h l,ϵ (•) -β, satisfies the first inequality in (7.32).

To verify that the function ψ l,ϵ,β (•) = h l,ϵ (•) -β satisfies the second inequality in (7.32), note that by (2.7) of Proposition 2.1,

h ϵ (y) ≤ ϵk(y, u) + (1 -ϵ)E[h ϵ (f (y, u, s))] ∀ (y, u) ∈ G.
The latter implies that

h ϵ (y) ≤ E[h ϵ (f (y, u, s))] + ϵ(k(y, u) -E[h ϵ (f (y, u, s))]) ∀ (y, u) ∈ G.
This, in turn, leads to

h l,ϵ (y) ≤ h ϵ (y) ≤ E[h l,ϵ (f (y, u, s)))] + 2M ϵ + E[κ l,ϵ (f (y, u, s))] ∀ (y, u) ∈ G
(since, as can be readily seen, max y∈Y |h ϵ (y)| ≤ M ). Thus, ψ l,ϵ,β (•) = h l,ϵ (•) -β satisfies the second inequality in (7.32), and, therefore, (7.34) is valid, the latter implying that

h l,ϵ (y 0 ) ≤ d * l (ϵ, y 0 ) (7.39)
(since β > 0 in (7.34) is arbitrary small).

By Lemma 10.1,

d * l (ϵ, y 0 ) ≤ k * l (ϵ, y 0 ), (7.40)
where We will prove only (7.44) (the proof of (7.45) follows exactly the same lines). Note that, from the dynamic programming principle (2.6), it follows that

k * l (ϵ, y 0 ) def = inf
T v T (y) ≤ k(y, u) + (T -1)E[v T -1 (f (y, u, s))] ∀ (y, u) ∈ G
for any T ≥ 1. Note also that by dividing the latter by T and passing to the limit as T → ∞, one obtains Note that the optimal value of problem (7.53) is the same as that of (4.3) (see (10.20) taken with θ = 0). Due to (7.46) and (7.52), the pair (ψ β (•), η β (•)), where ψ β (•) := v(•) -β, satisfies the inequalities (7.54). Consequently,

v(y) ≤ E[v(f (y, u, s))] ∀ (y, u) ∈ G. ( 7
d * (y 0 ) ≥ v(y 0 ) -β ∀ y 0 ∈ Y.
This proves (7.44), since β > 0 is arbitrarily small. Thus, (a) is proved. □ 8 Proof of Theorem 3.2

Let us prove (3.9). To this end, let us first demonstrate that the following inclusion holds: coΘ ϵ (y 0 ) ⊂ W (ϵ, y 0 ) ∀ϵ ∈ (0, 1). (8.1)

Let γ ∈ Θ ϵ (y 0 ). That is, γ is the discounted occupational measure generated by a control plan π ∈ Π: γ = γ π,y 0 ,ϵ d . The state-control trajectory (y π,y 0 (•), u π,y 0 (•)) obtained with the use of this plan satisfies the equality

E ∞ t=0 (1 -ϵ) t ψ(y π,y 0 (t)) = ψ(y 0 ) + E (1 -ϵ) ∞ t=0 (1 -ϵ) t ψ(f (y π,y 0 (t), u π,y 0 (t), s(t)))
for any ψ ∈ C(Y ). Multiplying both sides of this equality by ϵ and using (2.11), we obtain Rearranging the above, we have G (1 -ϵ)(E ψ(f (y, u, s)) -ψ(y)) + ϵ(ψ(y 0 ) -ψ(y)) γ π,y 0 ,ϵ d (dy, du) = 0, implying γ π,y 0 ,ϵ d ∈ W (ϵ, y 0 ). Hence, Θ ϵ (y 0 ) ⊂ W (ϵ, y 0 ). The validity of (8.1) follows from the fact that W (ϵ, y 0 ) is convex and compact.

To prove the converse inclusion, it is sufficient to prove that the inequality

+ (1 -ϵ)E[V ϵ (f (y, u, s))] -V ϵ (y)} = 0.
Hence,

h ϵ (y 0 ) = ϵV ϵ (y 0 ) = min (y,u)∈G {k(y, u) + (1 -ϵ) E[V ϵ (f (y, u, s))] -V ϵ (y) +ϵ V ϵ (y 0 ) -V ϵ (y) } = µ(V ϵ , ϵ, y 0 ) ≤ µ * LS (ϵ, y 0 ). (8.6)
Take an arbitrary γ ∈ W (ϵ, y 0 ) and an arbitrary ψ ∈ LS. Let {ψ n } ∞ n=1 be a bounded sequence of continuous functions such that ψ n (y) → ψ(y) point-wise on Y as n → ∞ (such a sequence exists; see, e.g., [START_REF] Ash | Measure, integration and functional analysis[END_REF]Theorem A6.6]). From Lebesgue's dominated convergence theorem (see, e.g., Theorem 1.6.9, p. 49 in [START_REF] Ash | Measure, integration and functional analysis[END_REF]) and from the definition of W (ϵ, y 0 ), it follows that

µ(ψ, ϵ, y 0 ) ≤ G k(y, u) + (1 -ϵ)(E[ψ(f (y, u, s))] -ψ(y)) + ϵ(ψ(y 0 ) -ψ(y)) γ(dy, du) = lim n→∞ G k(y, u) + (1 -ϵ)(E[ψ n (f (y, u, s))] -ψ n (y)) + ϵ(ψ n (y 0 ) -ψ n (y)) γ(dy, du) = G k(y, u)γ(dy, du).
Taking sup with respect to ψ ∈ LS in the left-hand-side and then taking min with respect to γ ∈ W (ϵ, y 0 ) in the right-hand-side allow us to conclude that µ * LS (ϵ, y 0 ) ≤ k * (ϵ, y 0 ). (8.7)

The latter and (8.6) prove (8.3). Note that (8.7) along with (3.7), (8.5) imply also that µ * LS (ϵ, y 0 ) = µ * (ϵ, y 0 ). Thus, the validity of (3.9) is established.

Let us prove (3.10). It is straightforward to verify that lim sup

ϵ→0    y 0 ∈Y W (ϵ, y 0 )    ⊂ W ⇒ lim sup ϵ→0 co    y 0 ∈Y W (ϵ, y 0 )    ⊂ W,
the second inclusion being due to the fact that W is convex and compact. By (3.9), the latter is equivalent to lim sup ϵ→0 coΘ ϵ ⊂ W. (see (3.6)). By (2.7),

k(y, u) + (1 -ϵ)E[V ϵ (f (y, u, s))] -V ϵ (y) ≥ 0 ∀ (y, u) ∈ G
for any ϵ ∈ (0, 1). After rearranging, the latter leads to The latter is valid for an arbitrary continuous k(y, u). Therefore, by the separation theorem,

k(y, u) + E[V ϵ (f (y, u, s))] -V ϵ (y) ≥ ϵE[V ϵ (f (y, u, s))] ≥ min y ′ ∈Y ϵV ϵ (y ′ ) = min y ′ ∈Y h ϵ (y ′ ) ∀ (y, u) ∈ G.
W ⊂ coΘ ϵ , (8.11)
which along with (8.8) prove (3.10).

Let us now establish the validity of (3.11). To this end, let us first show that lim sup

T →∞ Γ T ⊂ W. (8.12)
Take an arbitrary γ ∈ lim sup T →∞ Γ T . That is, there exist sequences y i 0 ∈ Y , π i ∈ Π, i = 1, 2, ..., and T i (with T i → ∞ as i → ∞) such that the corresponding sequence of occupational measures γ π i ,y i 0 ,T i ∈ Γ T i converges to γ: lim i→∞ γ π i ,y i 0 ,T i = γ. For any φ ∈ C(Y ), let φ(y, u) be defined in accordance with (5.21), that is, φ(y, u) = E[φ(f (y, u, s))]. (Note that φ ∈ C(Y ) too.) It can be readily understood (see (2.10)

) that G E[φ(f (y, u, s))]γ π i ,y i 0 ,T i i (dy, du) = G φ(y, u)γ π i ,y i 0 ,T i i (dy, du) = 1 T i E T i -1 t=0 φ y π i ,y i 0 (t), u π i ,y i 0 (t) = 1 T i E T i -1 t=0 E φ y π i ,y i 0 (t), u π i ,y i 0 (t) y π i ,y i 0 (t) = 1 T i E T i -1 t=0 E φ f y π i ,y i 0 (t), u π i ,y i 0 (t), s(t) y π i ,y i 0 (t) . (8.13) Therefore, G (E[φ(f (y, u, s))] -φ(y))γ π i ,y i 0 ,T i i (dy, du) = 1 T i E T i -1 t=0 E φ f y π i ,y i 0 (t), u π i ,y i 0 (t), s(t) y π i ,y i 0 (t) -φ y π i ,y i 0 (t) = 1 T i E T i -1 t=0 E φ y π i ,y i 0 (t + 1) y π i ,y i 0 (t) -φ y π i ,y i 0 (t) = 1 T i E T i -1 t=0 φ y π i ,y i 0 (t + 1) -φ y π i ,y i 0 (t) = 1 T i E φ y π i ,y i 0 (T i ) -φ y i 0 .
Hence,

G (E[φ(f (y, u, s))] -φ(y))γ(dy, du) = lim i→∞ G (E[φ(f (y, u, s))] -φ(y))γ π i ,y 0 i ,T i i (dy, du) = 0 ∀ φ ∈ C(Y ),
and, consequently, γ ∈ W . This proves (8.12), which implies that lim inf

T →∞ min y 0 ∈Y v T (y 0 ) ≥ k * . (8.14)
Let us now prove that lim sup

T →∞ min y 0 ∈Y v T (y 0 ) ≤ k * . (8.15)
Note that, if (8.15) is proved, then together with (8.14), it will imply the validity (3.14), which, in turn, will establish the validity of (3.11) (see Proposition 3.4).

To prove (8.15), take a sequence ϵ i , i = 1, 2, ..., with ϵ i → 0 as i → ∞. By (3.13) (that follows from (3.10), which has been already proved), there exist sequences of initial conditions y i 0 and control plans π i with the corresponding state-control trajectories (y π i ,y i 0 (•), u π i ,y i 0 (•)), such that

ϵ i E ∞ t=0 (1 -ϵ i ) t k y π i ,y i 0 (t), u π i ,y i 0 (t) = k * + ζ i , where lim i→∞ ζ i = 0. Let us use Lemma 8.1 with σ = k * + ζ i , δ = -ln(1 -ϵ i ) and g(t) = E[k(y π i ,y i 0 (t), u π i ,y i 0 (t))
]. (Lemma 8.1 and Lemma 8.2 used below are stated at the end of this section.) According to this lemma, there exist

T i ≥ c/ -ln(1 -ϵ i ), i = 1, 2, ... (c being a positive constant) such that 1 T i E T i -1 t=0 k y π i ,y i 0 (t), u π i ,y i 0 (t) < k * + ζ i + -ln(1 -ϵ i ) + 2M T i , i = 1, 2, ... .
From the expression above it follows that lim inf T →∞ min y∈Y v T (y) ≤ k * which, along with (8.14), implies that lim inf

T →∞ min y∈Y v T (y) = k * . (8.16)
In accordance with (8.16), there exist a sequence T i , i = 1, 2, ... (T i → ∞ as i → ∞) and sequences of initial conditions y i 0 and control plans π i ∈ Π with the corresponding state-control trajectories (y π i ,y i 0 (•),

u π i ,y i 0 (•)) such that 1 T i E T i -1 t=0 k y π i ,y i 0 (t), u π i ,y i 0 (t) = k * + ζ i , where lim i→∞ ζ i = 0. Let us use Lemma 8.2 with σ = k * + ζ i , δ = 1 T i and g(t) = E[k(y π i ,y i 0 (t), u π i ,y i 0 (t))]. According to this lemma, there exists T * i ∈ {0, 1, . . . , T i -1} such that 1 T E T -1 t=0 k y π i ,y i 0 (T * i + t), u π i ,y i 0 (T * i + t) ≤ k * + ζ i + 1 T i ∀ T ∈ {1, . . . , T i -T * i }, with T i -T * i → ∞ as i → ∞.
As can be readily understood,

1 T E T -1 t=0 k y π i ,y i 0 (T * i + t), u π i ,y i 0 (T * i + t) = E 1 T E T -1 t=0 k y π i ,y i 0 (T * i + t), u π i ,y i 0 (T * i + t) y π i ,y i 0 (T i ) ≥ E v T y π i ,y i 0 (T i ) ≥ min y∈Y v T (y).
Therefore,

min y∈Y v T (y) ≤ k * + ζ i + 1 T i ∀ T ∈ {1, . . . , T i -T * i }.
The latter implies (8.15), and, thus, the proof is completed. □ Lemma 8.1 Let Z * represent the set of non-negative integers and define the function g : Z * → R such that |g(t)| ≤ M for all t. Let ϵ ∈ (0, 1) and

σ def = ϵ ∞ t=0 (1 -ϵ) t g(t). (8.17)
Then, for any δ > 0, there exists a positive integer T ≥ δ

(4M +4|σ|+δ)(-ln(1-ϵ)) satisfying 1 T T -1 t=0 g(t) < σ + δ + 2M T . ( 8
σ def = 1 T T -1 t=0 g(t).
For any δ > 0, there exists

T * ∈ {0, 1, . . . , T -1} such that 1 S S-1 t=0 g(T * + t) ≤ σ + δ for all S ∈ {1, . . . , T -T * }. (8.19) Moreover, l(T ) def = T -T * → ∞ as T → ∞. (8.20)
The proofs of Lemmas 8.1 and 8.2 can be found in [START_REF] Gaitsgory | Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time[END_REF]. Note that these lemmas are discrete time versions of the continuous time results established in [START_REF] Grüne | Asymptotic controllability and exponential stabilization of nonlinear control systems at singular points[END_REF] and [START_REF] Grüne | On the relation between discounted and average optimal value functions[END_REF].

i > 0, γ i ∈ W, i = 1, 2, . . . , such that lim i→∞ ϵ i = 0 and lim i→∞ ρ(γ i , coΘ ϵ i ) ≥ α. (9.5)
Due to the fact W is compact in the metric ρ, and due to the fact (by Blaschke's selection theorem; see e.g., [START_REF] Klein | Theory of correspondence[END_REF]) the set of closed subsets of P (G) is compact in the corresponding Hausdorff metric ρ H , the sequences {γ i } and { coΘ ϵ i } have partial limits. More specifically, there exists γ ∈ W and Θ ⊂ P (G) such that, for some subsequence {i ′ } ⊂ {i},

lim i ′ →∞ ρ(γ i ′ , γ) = 0, lim i ′ →∞ ρ H ( coΘ ϵ i ′ , Θ) = 0. ( 9.6)
(Note that, being a limit in the Hausdorff metric of a sequence of convex compact sets, the set Θ is convex and compact.) By passing to the limit in (9.5), one obtains that

ρ(γ, Θ) ≥ α =⇒ γ / ∈ Θ.
for any continuous k(y, u), is established in a similar way. □

Linear programming results and proofs

Let us note again that the conditions about the model introduced in Section 2 are assumed to be satisfied in this section too (like everywhere in the consideration above).

Results and proofs referred to in Section 3

Let C * (Y ) stand for the space of continuous linear functionals on C(Y ) and let (as in Section 5) M(G) stand for the space of finite signed measures defined on Borel subsets of G. For any ϵ ∈ [0, 1), define a linear operator

A ϵ (•) : M(G) → IR × C * (Y ) as follows: for any γ ∈ M(G), A ϵ (γ) def = G γ(dy, du), a γ ϵ , (10.1)
where a γ ϵ ∈ C * (Y ) is defined by the equation:

∀ φ(•) ∈ C(Y ), a γ ϵ (φ) def = - G (1 -ϵ)(E φ(f (y, u, s)) -φ(y)) + ϵ(φ(y 0 ) -φ(y)) γ(dy, du) .
In these notations, the sets W (ϵ, y 0 ), W defined in (3.1) and (3.2) can be rewritten as follows where ⟨•, γ⟩ denotes the integral of the corresponding function over γ (problem (3.4) taking the form (10.2) when ϵ = 0). Note that, for any (µ, ψ( That is, the operator A * ϵ (•) is the adjoint of A ϵ (•). The problem dual to (10.2) is of the form (see [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF] and [START_REF] Anderson | Linear programming in infinite-dimensional spaces[END_REF]) sup Let us now prove that D is closed. Let γ l ∈ M + (G) be such that A ϵ (γ l ) -z → (0, 0), ⟨k, γ l ⟩ -β → 0 as l → ∞, (10.8) where z ∈ IR × C * (Y ) and β ∈ IR. By (10.6), γ l = λ l γl , where λ l ≥ 0 and γl ∈ L. Due to compactness of L, one may assume (without loss of generality) that γl → γ ∈ L.

W (ϵ, y 0 ) = γ ∈ M + (G) : A ϵ (γ) = (1, 0) , W = W (0, y 0 ) = γ ∈ M + (G) : A 0 (γ) = (1, 0
•)) ∈ IR × C(Y ), ⟨A ϵ (γ), (µ, ψ)⟩ = µ G γ(dy, du) + a γ ϵ (ψ) = G µ -(1 -ϵ)(E ψ(f (y, u, s)) -ψ(y)) + ϵ(ψ(y 0 ) -ψ(y)) γ(dy, du).

Define the linear operator

A * ϵ (•) : IR × C(Y ) → C(G) ⊂ M * (G) in such a way that, for any (µ, ψ(•)) ∈ IR × C(Y ), A * ϵ (µ, ψ)(y, u) def = µ -(1 -ϵ)(E ψ(f (y, u, s)) -ψ(y)) + ϵ(ψ(y 0 ) -ψ(y)) . ( 10
Note that, due to Property B, the sequence λ l is bounded. Indeed, assuming that this is not the case and there exists a subsequence {l ′ } of {l} such that λ l ′ → ∞ as l ′ → ∞ , one would obtain (via substitution of λ l ′ γl ′ into (10.8) and passing to the limit with l ′ → ∞) that

A ϵ (γ l ′ ) - 1 λ l ′ z → (0, 0), ⟨k, γl ′ ⟩ - 1 λ l ′ β → 0 as l → ∞.
⇒ A ϵ (γ) = (0, 0), ⟨k, γ⟩ = 0.

According to Property B, the latter implies that γ = 0. This contradicts to the fact that γ ∈ L. Thus, the sequence {λ l } is bounded and therefore one may assume (without loss of generality) that λ l → λ as l → ∞. Consequently, γ l → λγ as l → ∞, and, by (10.8),

A ϵ (λγ) = z, ⟨k, λγ⟩ = β ⇒ (z, β) ∈ D.
This proves that D is closed. □ REMARK. Note that the proof above is similar to the proof of the absence of the duality gap in [START_REF] Piunovskiy | Discounted continuous-time Markov decision processes with unbounded rates: The convex analytic approach[END_REF]. That is, the operator A * (•) is the adjoint of A(•). Thus, the problem dual to (10.10) is of the form (see e.g. [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF] or [START_REF] Anderson | Linear programming in infinite-dimensional spaces[END_REF]) sup Its optimal value k * sub (y 0 ) is called the subvalue of the IDLP problem (10.10) (see [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF], [START_REF] Anderson | Linear programming in infinite-dimensional spaces[END_REF]). Let us show that the optimal value of (5.3) is equal to the subvalue.

Firstly note that, as can be readily seen, 1, 0, 0, Y ×U k(y, u)γ(dy, du) ∈ H if γ ∈ W ∩ D 1 (y 0 ). Consequently, k * sub (y 0 ) ≤ min γ∈W ∩D 1 (y 0 ) Y ×U k(y, u)γ(dy, du) = k * * (y 0 ).

From the fact that k * sub (y 0 ) is defined as the optimal value in (10.14) it follows that there exists a sequence (γ l , ξ l ) ∈ M + (G) × M + (G) such that A(γ l , ξ l ) converges (in weak * topology) to (1, 0, 0), with Y ×U k(y, u)γ l (dy, du) converging to k * sub (y 0 ) as l tends to infinity. That is (see (10.9)), G γ l (dy, du) → 1, a (γ l ,ξ l ) → 0, b γ l → 0, G k(y, u)γ l (dy, du) → k * sub (y 0 ).

Without loss of generality, one may assume that γ l converges in weak * topology to a measure γ that satisfies the relationships

G γ(dy, du) = 1, b γ = 0 ⇒ γ ∈ W.
Also, a (γ,ξ l ) → 0 and G k(y, u)γ(dy, du) = k * sub (y 0 ). From the fact that a (γ,ξ l ) → 0 it follows that γ ∈ D 1 (y 0 ) (see (5.4)). That is, γ ∈ W ∩ D 1 (y 0 ). Consequently, Thus, k * * (y 0 ) = k * sub (y 0 ). To complete the proof, it is sufficient to note that the subvalue of an IDLP problem is equal to the optimal value of its dual provided that the former is bounded (see, e.g., Theorem 3 in Taking into account that (γ, ξ) ∈ Ω(y 0 ) and the second inequality in (10.17 This proves (10.22). □

11 Acknowledgement

G( 1 -

 1 Define the sets W (ϵ, y 0 ) ⊂ P(G) and W ⊂ P(G) by the equations W (ϵ, y 0 ) def = γ ∈ P(G)| ϵ)(E φ(f (y, u, s)) -φ(y)) + ϵ(φ(y 0 ) -φ(y)) γ(dy, du) = 0 ∀φ ∈ C(Y ) (3.1) and

Proposition 4 . 1

 41 The optimal values of (4.1) and (4.3) are related by the inequality d * (y 0 ) ≤ k * (y 0 ). (4.6)

Theorem 4 . 4

 44 (a) Let limit (4.24) exist for any y 0 ∈ Y (that is, v T (•) converges to a function v(•) pointwisely on Y ), and let the limit function v(•) be continuous. Then v(y 0 ) = d * (y 0 ) (4.26) for any y 0 ∈ Y . (b) Let limit (4.25) exist for any y 0 ∈ Y (that is, h ϵ (•) converges to a function h(•) point-wisely on Y ), and let the limit function h(•) be continuous. Then h(y 0 ) = d * (y 0 ) (4.27)

Corollary 4 . 5

 45 If the conditions of Theorem 4.4 (a) and/or the conditions of Theorem 4.4 (b) are satisfied, then d * (y 0 ) = d * (y 0 ) ∀ y 0 ∈ Y. (4.28) Proof. If the conditions of (a) are satisfied, then, by (4.18), d * (y 0 ) ≤ v(y 0 ) ∀ y 0 ∈ Y. (4.29) This, along with (4.17) and (4.26), implies (4.28). If the conditions of (b) are satisfied, then d * (y 0 ) ≤ h(y 0 ) ∀ y 0 ∈ Y. (4.30)

41 )

 41 Define ψ(•) and η(•) by the equations: ψ(y) for y ∈ (0, 1]. (4.42) Via the direct substitution that the function ψ(•) satisfies (4.41) and that inf (y,u)∈G

(4. 43 )

 43 Thus (see(4.36) and (4.40)), d * (y 0 ) ≥ v(y 0 ). Therefore, by (4.18), d * (y 0 ) = v(y 0 ) ∀ y 0 ∈ [-1, 1]. (4.44)

. 10 )

 10 Proof. Note that v T (y 0 ) = inf γ∈Γ T (y 0 ) G k(y, u)γ(dy, du) = min γ∈ coΓ T (y 0 ) G k(y, u)γ(dy, du). Therefore, from Theorem 4.4 (a) and from Proposition 5.2 it follows that, for any continuous k(y, u), lim T →∞ min γ∈ coΓ T (y 0 ) G k(y, u)γ(dy, du) = min γ∈W ∩D 1 (y 0 ) G k(y, u)γ(dy, du).

Corollary 5 . 4

 54 The strong duality equality (4.21) is valid ifcl(W ∩ D(y 0 )) = W ∩ D 1 (y 0 ). (5.11)

Corollary 5 . 6

 56 If the conditions of Theorem 4.4 (a) are satisfied and if the equality (5.14) is valid, then the strong duality equality (4.21) is true.

Proposition 6 . 1

 61 (a) If, for a given y 0 ∈ Y , the limit (4.24) exists and v(y 0 ) = d * (y 0 ), (6.2)then a pair ( ψ(•), η(•)) is an optimal solution of (4.14) if and only if ψ(•) satisfies the second inequality in (4.15) and inf(y,u)∈G {k(y, u) -ψ(y) + E[η(f (y, u, s))] -η(y)} = v(y 0 ) -ψ(y 0 ). (6.3) (b) Let the limit (4.24) exist and (6.2) be valid for any y 0 ∈ Y . If η(•) ∈ B(Y ) is such that inf (y,u)∈G {k(y, u) -v(y) + E[η(f (y, u, s))] -η(y)} = 0, (6.4) then the pair ( ψ(•), η(•)), where ψ(•) = v(•) is an optimal solution of problem (4.14). Proof. By (4.16), the first inequality in (6.1) is equivalent to the equality inf (y,u)∈G {k(y, u) + ψ(y 0 ) -ψ(y) + E[η(f (y, u, s))] -η(y)} = d * (y 0 ). (6.5)

. 21 ). 22 )

 2122 (iii) The function η T (•) converges in the uniform metric to a function η(•); that is lim T →∞ sup y∈Y |η T (y) -η(y)| = 0. (6Then the pair ( ψ(•), η(•)), where ψ(•) = v(•), is an optimal solution of the dual problem (4.14).

2 ,

 2 ... , which, after taking into account (6.21), leads to inf (y,u)∈G {k(y, u) -v(y) + E[η T -1 (f (y, u, s))] -η T (y)} = 0, T = 1, 2, ... . Passing to the limit with T → ∞ in the equality above implies the validity of (6.4) (due to (6.22)). The statement follows now from Proposition 6.1(b). □ 7 Proofs of Theorems 4.2 and 4.4

(7. 1 )

 1 Proof. Let us prove the first inequality in (7.1). Assume it is not true, that is, d * (y 0 ) > lim inf T →∞ v T (y 0 ). Then, there exists β > 0 and a pair of functions (ψ(•), η(•)) ∈ B(Y ) × B(Y ), with ψ(•) satisfying the second inequality in(4.15), such that k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) ≥ lim inf

Lemma 7 . 2

 72 For any natural T , G v T (y) γ(dy, du) ≤ G k(y, u) γ(dy, du) ∀ γ ∈ W. (7.8) Also, for any ϵ ∈ (0, 1), G h ϵ (y) γ(dy, du) ≤ G k(y, u) γ(dy, du) ∀ γ ∈ W. (7.9)

  2, ..., and lim l→∞ v l,T (y) = v T (y) ∀ y ∈ Y (7.12) and, for any l = 1, 2, ..., max y∈Y |v l,T (y)| ≤ sup y∈Y |v T (y)| ≤ max (y,u)∈Y ×U |k(y, u)| def = M. (7.13)

  13), 0 ≤ κ l+1,T (y) ≤ κ l,T (y) ≤ 2M ∀ y ∈ Y, l = 1, 2, ..., and lim l→∞ κ l,T (y) = 0 ∀ y ∈ Y. (7.15) Consider the following IDLP problem sup (ψ,η)∈Q l (T )

(

  γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) + 2M ϵ G ξ(dy, du) + G E[κ l,ϵ (f (y, u, s))]ξ(dy, du) .(In this case, to adjust the notations used above and the ones used in Lemma 10.1, one should write d * l (ϵ, y 0 ) and k * l (ϵ, y 0 ) as d * θ ϵ,l (y 0 ) and k * θ ϵ,l (y 0 ), where θ ϵ,l (y, u) = 2M ϵ + E[κ l,ϵ (f (y, u, s))].) From (7.39) and (7.40) it follows that h l,ϵ (y 0 ) ≤ k * l (ϵ, y 0 ).(7.41) Using the argument similar to one used above, we can show thatlim l→0 k * l (ϵ, y 0 ) = k * (ϵ, y 0 ) (7.42)wherek * (ϵ, y 0 ) def = inf (γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) + 2M ϵ G ξ(dy, du) .Subsequently, one can show that lim ϵ→0 k * (ϵ, y 0 ) = k * (y 0 ). (7.43) The validity of the second inequality in (7.11) follows from (7.41), (7.42), (7.43) (and from (7.30)). □ Proof of Theorem 4.4. If the point-wise limit (4.24) exists, then, by Theorem 4.2, the limit function v(•) satisfies the inequality v(y 0 ) ≥ d * (y 0 ) ∀ y 0 ∈ Y. Therefore, to prove the statement (a), one needs to show that v(y 0 ) ≤ d * (y 0 ) ∀ y 0 ∈ Y. (7.44) Similarly, if the point-wise limit (4.25) exists, then, by Theorem 4.2, the limit function h(•) satisfies the inequality h(y 0 ) ≥ d * (y 0 ) ∀ y 0 ∈ Y. Therefore, to prove the statement (b), one needs to show that h(y 0 ) ≤ d * (y 0 ) ∀ y 0 ∈ Y. (7.45)

. 46 )

 46 Also, by passing to the limit as T → ∞ in(7.8), one obtains G v(y) γ(dy, du) ≤ G k(y, u) γ(dy, du) ∀ γ ∈ W. (7.47) Inequality (7.47) can be rewritten in the form G (k(y, u) -v(y)) γ(dy, du) ≥ 0 for all γ ∈ W, which is equivalent to that min γ∈W G (k(y, u) -v(y)) γ(dy, du) ≥ 0. (7.48)The problem in the left hand side of the above inequality,min γ∈W G (k(y, u) -v(y)) γ(dy, du),(7.49)is an IDLP problem, whose dual is sup η∈C(Y ) inf (y,u)∈G {k(y, u) -v(y) + E[η(f (y, u, s))] -η(y)}. (7.50) By equation (3.8) of Proposition 3.1 (considered with k(y, u) -v(y) instead of k(y, u)), the optimal values of (7.49) and (7.50) are equal. Therefore, (7.48) is equivalent to sup η∈C(Y ) inf (y,u)∈G {k(y, u) -v(y) + E[η(f (y, u, s))] -η(y)} ≥ 0. (7.51) From (7.51) it follows that, for any β > 0, there exists a function η β (•) ∈ C(Y ) such that k(y, u) -v(y) + E[η β (f (y, u, s))] -η β (y) ≥ -β for all (y, u) ∈ G. (7.52) Consider now the problem sup (ψ,η)∈Q ψ(y 0 ) = d * (y 0 ), (7.53) where Q is the set of pairs (ψ, η) ∈ C(Y ) × C(Y ) that satisfy the inequalities k(y, u) -ψ(y) + E[η(f (y, u, s))] -η(y) ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ 0 for all (y, u) ∈ G. (7.54)

G

  ψ(y)γ π,y 0 ,ϵ d (dy, du) = G ϵψ(y 0 )γ π,y 0 ,ϵ d (dy, du) + G (1 -ϵ)E ψ(f (y, u, s)) γ π,y 0 ,ϵ d (dy, du).

  min γ∈ coΘϵ(y 0 ) G k(y, u)γ(dy, du) ≤ min γ∈W (ϵ,y 0 ) G k(y, u)γ(dy, du) ∀ ϵ ∈ (0, 1) (8.2) is valid for an arbitrary continuous function k(y, u). (The fact that the validity of (8.2) for any k(y, u) implies the inclusion converse to (8.1) follows from the separation theorem; see the proof of Proposition 3.4 in Section 9). Due to (2.14) and (3.15), the latter is equivalent to h ϵ (y 0 ) ≤ k * (ϵ, y 0 ). (8.3) Let LS stand for the set of bounded lower semicontinuous functions on G, and, for any ψ ∈ LS, let µ(ψ, ϵ, y 0 ) def = inf (y,u)∈G k(y, u) + (1 -ϵ) E ψ(f (y, u, s)) -ψ(y) + ϵ ψ(y 0 ) -ψ(y) . , ϵ, y 0 ) ≥ µ * (ϵ, y 0 ). (8.5) By (2.7) (see Proposition 2.1), we have min u∈U (y) {k(y, u) + (1 -ϵ)E[V ϵ (f (y, u, s))] -V ϵ (y)} = 0 ∀y ∈ Y, which implies min (y,u)∈G {k(y, u)

  u)∈G k(y, u) + E ψ(f (y, u, s)) -ψ(y)

  Consequently, since V ϵ (•) is lower semi-continuous (as established by Proposition 2.1),µ * LS ≥ min y∈Y h ϵ (y) ∀ ϵ ∈ (0, 1). (8.10)Take an arbitrary γ ∈ W and an arbitrary ψ ∈ LS. There exists a sequence of bounded continuous functions {ψ n } ∞ n=1 that converges to ψ(y) point-wisely on Y as n → ∞. From Lebesgue's dominated convergence theorem and from the definition of W , it follows thatµ(ψ) ≤ G k(y, u) + E[ψ(f (y, u, s))] -ψ(y) γ(dy, du) = lim n→∞ G k(y, u) + E[ψ n (f (y, u, s))] -ψ n (y) γ(dy, du) = G k(y, u)γ(dy, du).Taking sup with respect to ψ ∈ LS in the left-hand-side and then taking min with respect to γ ∈ W in the right-hand-side lead to the inequality µ * LS ≤ k * . This and (8.10) lead to the inequality min y∈Y h ϵ (y) ≤ k * ∀ ϵ ∈ (0, 1), which can be rewritten as follows (see (3.4) and (3.16)) min γ∈ coΘϵ G k(y, u)γ(dy, du) ≤ min γ∈W G k(y, u)γ(dy, du) ∀ ϵ ∈ (0, 1)

  ) , where 0 stands for the zero element of C * (Y ). Also, problem (3.3) takes the forms min γ∈W (ϵ,y 0 ) ⟨k, γ⟩ = k * (ϵ, y 0 ), (10.2)

  ψ), γ⟩ = G µ -(1 -ϵ)(E ψ(f (y, u, s)) -ψ(y)) + ϵ(ψ(y 0 ) -ψ(y)) γ(dy, du) = ⟨A ϵ (γ), (µ, ψ)⟩.

  (µ,ψ(•))∈IR×C(Y ) µ = µ * (ϵ, y 0 ) (10.4)s. t. -A * ϵ (µ, ψ)(y, u) + k(y, u)) ≥ 0 ∀(y, u) ∈ G.(10.5)Due to (10.3), the constraint (10.5) is equivalent tok(y, u) + (1 -ϵ)(E ψ(f (y, u, s)) -ψ(y)) + ϵ ψ(y 0 ) -ψ(y) ≥ µ ∀(y, u) ∈ G.Thus, problem(10.4) is equivalent to (3.5) for ϵ ∈ (0, 1), and it is equivalent to (3.6) when ϵ = 0.Proof of Proposition 3.1. By Theorem 6 in[START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF], to prove the proposition, it is sufficient to establish that, for any ϵ ∈ [0, 1), the set D ϵ ,D ϵ def = (A ϵ (γ), ⟨k, γ⟩ ) : γ ∈ M + (G) ⊂ IR × C * (Y ) × IR, is closed in the weak * topology of IR × C * (Y ) × IR.The proof of this is similar to the proof of Theorem 12 in[START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF]. It is based on the following two properties of the problem.Property A. The set M + (G) has a compact base. That is (see[START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF]),M + (G) = {λγ : γ ∈ L, λ ≥ 0},(10.6)whereL def = {γ ∈ M + (G) : G γ(dy, du) = 1},with L being a weak * compact subset of M(G).Property B. For γ ∈ M + (G), the equalitiesA ϵ (γ) = (0, 0)(10.7)can be valid only if γ = 0, this being readily verifiable due to the fact that a part of the relationships (10.7) is the equality: G γ(dy, du) = 0.

10. 2

 2 Results and proofs referred to in Sections 4 and 5 Define a linear operator A(•) : M(G) × M(G) → IR × C * (Y ) × C * (Y ) as follows: for any (γ, ξ) ∈ M(G) × M(G), A(γ, ξ) := G γ(dy, du), a (γ,ξ) , b γ , (10.9) where a (γ,ξ) , b γ ∈ C * (Y ) are defined for all φ(•) ∈ C(Y ) as followsa (γ,ξ) (φ) def = -G (φ(y 0 ) -φ(y))γ(dy, du) + G (E[φ(f (y, u, s))] -φ(y))ξ(dy, du) , b γ (φ) φ(f (y, u, s))] -φ(y))γ(dy, du) .In these notations, the set Ω(y 0 ) defined in (4.2) takes the formΩ(y 0 ) = (γ, ξ) ∈ M + (G) × M + (G) : A(γ, ξ) = (1, 0, 0) ,and problem (4.1) can be rewritten as follows inf (γ,ξ)∈Ω(y 0 ) ⟨k, γ⟩ = k * (y 0 ). (10.10) For any (µ, ψ(•), η(•)) ∈ IR × C(Y ) × C(Y ), we have⟨A(γ, ξ), (µ, ψ, η)⟩ = µ G γ(dy, du) + a (γ,ξ) (ψ) + b γ (η) = G (µ -(ψ(y 0 ) -ψ(y)) -(E[η(f (y, u, s))] -η(y))) γ(dy, du) -G (E[ψ(f (y, u, s))] -ψ(y))ξ(dy, du).Define now the linear operatorA * (•) : IR × C(Y ) × C(Y ) → C(G) × C(G) ⊂ M * (G) × M * (G)in such a way that, for any (µ, ψ(•), η(•)) ∈ IR × C(Y ) × C(Y ), A * (µ, ψ, η)(y, u) def = µ -(ψ(y 0 ) -ψ(y)) -(E[η(f (y, u, s))] -η(y)), -(E[ψ(f (y, u, s))] -ψ(y)) . (10.11) Thus, ⟨A * (µ, ψ, η), (γ, ξ)⟩ = G (µ -(ψ(y 0 ) -ψ(y)) -(E[η(f (y, u, s))] -η(y))) γ(dy, du) -G (E[ψ(f (y, u, s))] -ψ(y))ξ(dy, du) = ⟨A(γ, ξ), (µ, ψ, η)⟩.

(( 4

 4 µ,ψ(•),η(•))∈IR×C(Y )×C(Y ) µ = d * (y 0 ) (10.12) such that A * (µ, ψ, η)(y, u) + (k(y, u), 0) ≥ (0, 0) ∀ (y, u) ∈ G. (10.13)In accordance with(10.11), the constraint (10.13) is equivalent to (4.4), and problem (10.12) is equivalent to u)γ(dy, du)+ r : (γ, ξ) ∈ M + (G) × M + (G), r ≥ 0 ⊂ IR × C * (Y ) × C * (Y ) × IR ,and let H stand for the closure of H in the weak * topology of the space IR × C * (Y ) × C * (Y ) × IR. That is, (κ, a, b, θ) belongs to H (where a, b ∈ C * (Y ) and κ, θ ∈ IR) if and only if there exists sequences(γ l , ξ l ) ∈ M + (G) × M + (G), r l ≥ 0, l = 1, 2, ..., such that a (γ l ,ξ l ) (φ) → a(φ), b γ l (φ) → b(φ) ∀ φ(•) ∈ C(Y ) and G γ l (dy, du) → κ, Y ×U k(y, u)γ l (dy, du) + r l → θ.Consider the problem inf{θ | (1, 0, 0, θ) ∈ H} def = k * sub (y 0 ).(10.14)

k

  * * (y 0 ) = min γ∈W ∩D 1 (y 0 ) G k(y, u)γ(dy, du) ≤ G k(y, u)γ(dy, du) = k * sub (y 0 ).

Lemma 10 . 1

 101 [START_REF] Anderson | A review of duality theory for linear programming over topological vector spaces[END_REF]). That is, k * sub (y 0 ) = d * (y 0 ). □ Consider the following "perturbed" version of the IDLP problem (4.1): inf (γ,ξ)∈Ω(y 0 ) G k(y, u)γ(dy, du) + G θ(y, u)ξ(dy, du)def = k * θ (y 0 ),(10.15)where θ(y, u) ≥ 0 is a bounded Borel measurable function on Y × U . Using an argument similar to the one used above, one can verify that the problem dual to (10.15) can be written in the form sup (µ,ψ,η)∈D θ (y 0 )µ def = d * θ (y 0 ),(10.16)where D θ (y 0 ) is the set of triplets (µ,ψ(•), η(•)) ∈ IR × C(Y ) × C(Y ) that satisfy the inequalities k(y, u) + (ψ(y 0 ) -ψ(y)) + E[η(f (y, u, s))] -η(y) -µ ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ -θ(y, u) ∀ (y, u) ∈ G. (10.17) (Note that (10.15) and (10.16) coincide with (4.1) and (4.3) if θ(y, u) ≡ 0.) Consider also the problem sup(ψ,η)∈Q θ ψ(y 0 ) def = d * θ (y 0 ),(10.18)whereQ θ is the set of pairs (ψ(•), η(•)) ∈ C(Y ) × C(Y ) that satisfy the inequalities k(y, u) -ψ(y) + E[η(f (y, u, s))] -η(y) ≥ 0, E[ψ(f (y, u, s))] -ψ(y) ≥ -θ(y, u) ∀ (y, u) ∈ G. (10.19) The following relationships are valid:d * θ (y 0 ) = d * θ (y 0 ) ≤ k * θ (y 0 ). (10.20) Proof. Let us prove, first, that d * θ (y 0 ) = d * θ (y 0 ). (10.21) In fact, the inequality d * θ (y 0 ) ≤ d * θ (y 0 ) is true (since, for any pair (ψ(•), η(•)) ∈ Q θ , the triplet (µ, ψ(•), η(•)) ∈ D θ (y 0 ) with µ = ψ(y 0 )). Let us prove the opposite inequality. Let a triplet (µ ′ , ψ ′ (•), η ′ (•)) ∈ D θ (y 0 ) be such that µ ′ ≥ d * θ (y 0 ) -β, with β > 0 being arbitrarily small. Then the pair ( ψ′ (•), η ′ (•)) ∈ Q θ , with ψ′ (y) = ψ ′ (y) -ψ ′ (y 0 ) + µ ′ . Since ψ′ (y 0 ) = µ ′ , it leads to the inequality d * θ (y 0 ) ≥ µ ′ ≥ d * θ (y 0 ) -β and, consequently, to the inequality d * θ (y 0 ) ≥ d * θ (y 0 ). Thus, (10.21) is proved. Let us now prove the weak duality inequality d * θ (y 0 ) ≤ k * θ (y 0 ). (10.22) Take any (γ, ξ) ∈ Ω(y 0 ) and (µ, ψ, η) ∈ D θ (y 0 ). Integrating the first inequality in (10.17) with respect to γ and taking into account that γ ∈ W we conclude that G k(y, u)γ(dy, du) + G (ψ(y 0 ) -ψ(y))γ(dy, du) ≥ µ.

  ), we obtainG (ψ(y 0 ) -ψ(y))γ(dy, du) = -G (E[ψ(f (y, u, s))] -ψ(y))ξ(dy, du) ≤ G θ(y, u)ξ(dy, du).Therefore, G k(y, u)γ(dy, du) + G θ(y, u)ξ(dy, du) ≥ µ.

  ,y 0 (t) < 0. Since |y π * ,y 0 (t)| = |y 0 | for any t ≥ 0, we can come to the conclusion that

		y 0 (t)	with probability	1/4,
		y π * ,y 0 (t)	with probability	3/4
	if y π y π * ,y 0 (t + 1) =	-|y 0 | |y 0 |	with probability with probability	3/4, 1/4

*

  Based on the separation theorem (see e.g.[46, p. 59]), we may conclude that there exists k(y, u) ∈ C(G)

	such that
	min γ∈ Θ G	k(y, u)γ(dy, du) ≥	G	k(y, u)γ(dy, du) + β ≥ min γ∈W G	k(y, u)γ(dy, du) + β	(9.7)
	for some β > 0. From the second equality in (9.6), it follows that
		lim i ′ →∞	min γ∈ coΘϵ i ′ G	k(y, u)γ(dy, du) = min γ∈ Θ G	k(y, u)γ(dy, du).
	Consequently, from (9.7) it follows that
		min γ∈ coΘϵ i ′ G	k(y, u)γ(dy, du) ≥ min γ∈W G	k(y, u)γ(dy, du) +	β 2
	for i ′ large enough. This contradicts (9.3) considered with k(y, u) = k(y, u). Thus, the validity of (9.4) is
	established, and (3.10) is proved.
	The fact that (3.11) is valid if (3.14) is true, that is, if
		lim T →∞	min γ∈ coΓ T G

k(y, u)γ(dy, du) = min γ∈W G k(y, u)γ(dy, du)

We would like to thank Yi Zhang from the University of Liverpool for useful comments on the present work. We would also like to thank two anonymous reviewers for their constructive comments and, in particular the reviewer that suggested an alternative (much shorter than the original one) proof of Lemma 7.2.