Convex Analytic Methods in Markov Decision Processes

Vivek S. Borkar

Department of Computer Science and Automation

Indian Institute of Science

Bangalore 560 012 Email: borkar@csa.iisc.ernet.in

1 Introduction

1.1 Background

Markov decision processes optimize phenomena evolving with time and thus are intrinsically dynamic optimization problems. Nevertheless, they can be cast as abstract ‘static’ optimization problems over a closed convex set of measures. They then become convex programming (in fact, infinite dimensional linear programming) problems for which the enormous machinery of the latter fields can be invoked and used to advantage. Logically, these are extensions of the linear programming approach to finite state finite action space problems due to Manne [23]. (Further references are given in the ‘bibliographical note’ at the end.) The attraction of this approach lies in the following:

(i) It leads to elegant alternative derivations of known results, sometimes under weaker hypotheses, from a novel perspective.

(ii) It brings to the fore the possibility of using convex/linear programming techniques for computing near-optimal strategies.

(iii) It allows one to handle certain unconventional problems (such as control under additional constraints on secondary ‘costs’) where traditional dynamic programming paradigm turns out to be infeasible or awkward.

Our primary focus will be on countable state space and ergodic (or ‘long run average’) cost, for which the theory is the most elegant. This is done in the next section. Section 3 sketches extensions, first to other cost criteria and then to general state spaces. Section 4 considers multiobjective problems, such as the problem of control under constraints. Section 5 concludes with a brief discussion, followed by a ‘bibliographical note’.

1.2 Notation

We shall consider a controlled Markov chain X_{n}, n ≥ 0, taking values in a state space S. Initially, we shall consider only countable S, without loss of generality identified with the set {0, 1, 2, ⋯}. With each i ∈ S is associated an action space U_{i}, which is a copy of a fixed compact metric space U. The transition probability P (j/i, u) for i, j ∈ S, u ∈ U_{i} will denote the probability of going from i to j, when action u is chosen. Thus P (j/i, u) ∈ [0, 1] ∀i, j, u with

∑_{j} P (j/i, u) = 1.

Note that there is no loss of generality in letting U_{i}’s be replicas of a fixed compact metric space U. If not, we could always set U = Π_{i}U_{i} and replace P (j/i, ·) by its composition with the projection U → U_{i} for each i, j. Let {Z_{n}} denote the U-valued control process. Thus {X_{n}} evolves as per

P (X_{n+1} = j/X_{m}, Z_{m}, m ≤ n) = P (j/X_{n}, Z_{n}), n ≥ 0.

We call {Z_{n}} a stationary strategy if Z_{n} = v(X_{n}) ∀n for some measurable v : S → U, and a stationary randomized strategy if for each n, Z_{n} is conditionally independent of X_{m}, Z_{m}, m < n, given X_{n} and its regular conditional law given X_{n} is f(X_{n}) for some measurable f : S → P(U). (Here and elsewhere, P(X) for a Polish space X is the Polish space of probability measures on X with the Prohorov topology. See, e.g., [12], Chapter 2.) By abuse of terminology, we may identify a stationary (resp., stationary randomized) strategy with the corresponding map v(·) (resp., f(·)). Denote by Π_{S} (resp., Π_{SR}) the set of stationary (resp., stationary randomized) strategies. Note that under either, {X_{n}} is a time-homogeneous Markov chain.

Let k : S × U → R be a continuous ‘running cost’ function, which we assume to be bounded from below. The various ‘classical’ control problems then are:

(i) Finite horizon contol

Minimize E [∑_{n=0}^{N} k(X_{n}, Z_{n})] for some N ≥ 0.

(ii) Infinite horizon discounted cost control

Minimize E [∑_{n=0}^{∞} β^{n}k(X_{n}, Z_{n})] for some ‘disscount factor’ β ∈ (0, 1).

(iii) Control up to exit time

Minimize E [∑_{n=0}^{τ} k(X_{n}, Z_{n})] for some τ = min{n ≥ 0 : X_{n} ∉ O}, O being a prescribed subset of S. (τ = ∞ if X_{n} ∈ O ∀n.)

(iv) Ergodic or long run average cost control

Minimize ‘almost surely’

lim sup_{N→∞} \frac{1}{N} ∑_{n=0}^{N−1} k(X_{n}, Z_{n}).  (1.1)

We shall focus primarily on (iv). Note that if f ∈ Π_{SR} is used and X_{0} is in the support of an ergodic distribution π ∈ P(S) for the corresponding time-homogeneous Markov chain {X_{n}}, then (1.1) will a.s. equal

∑_{i} π(i)k̄(i, f(i))

where k̄ : S × P(U) → R is defined by

k̄(i, u) = ∫ k(i, y)u(dy), (i, u) ∈ S × P(U).

This will be the starting point of our convex analytic formulation of (iv), which we take up next.

2 Ergodic Control

2.1 Ergodic occupation measures

If the chain controlled by f ∈ Π_{SR} has an invariant probability measure π ∈ P(S), we associate with the pair (π, f) the ergodic occupation measure π̂_{f} defined by:

∫_{S×U} gdπ̂_{f} = ∑_{i∈S} π(i) ∫_{U} g(i, y)f(i, dy),

for g ∈ C_{b}(S ×U)(=^{Δ} space of bounded continuous maps S ×U → R. Analogous notation will be used throughout.) Let C be a countable subset of C_{b}(S) satisfying : for any f ∈ C_{b}(S), there exist {g_{n}} in the linear span of C such that g_{n} → f in a bounded, pointwise fashion.

Lemma 2.1 π̂_{f} satisfies : ∀g ∈ C_{b}(S),

∑_{i∈S} g(i)π̂_{f}({i}, U) = ∫_{S×U} (∑_{j∈S} P (j/i, a)g(j)) dπ̂_{f}.

Conversely, if η ∈ P(S × U) satisfies

∑_{i∈S} g(i)η({i}, U) = ∫_{S×U} (∑_{j∈S} P (j/i, a)g(j)) dη  (2.1)

for g ∈ C, then η = π̂_{f} for some (π, f).

Proof The first claim is simply the invariance of π under f. For the second, note that (2.1) holds for all g ∈ C_{b}(S) if it does so for g ∈ C. Disintegrate η as η({i}, dy) = π(i)f(i, dy) with π ∈ P(S) and f : S → P(U) the appropriate regular conditional law defined π-a.s. uniquely. Identify f with an element of Π_{SR}, whence (2.1) implies that π is invariant under it. The claim follows. □

Often C = {I_{{i}}, i ∈ S} is a convenient choice for C. Let G denote the set of all ergodic occupation measures.

Lemma 2.2 G is closed convex in P(S × U).

Proof (2.1) is preserved under convergence in P(S × U). In view of Lemma 2.1, this implies that G is closed. Let ν_{j} ∈ G, 1 ≤ j < n, with ν_{j}({i}, dy) = π_{j}(i)f_{j}(i, dy) for f_{j} ∈ Π_{SR} and π_{j} ∈ P(S) invariant under respective f_{j}’s. Let a_{j} ∈ (0, 1), 1 ≤ j ≤ n, with ∑_{j} a_{j} = 1. Set ν = ∑_{j} a_{j}ν_{j}, π = ∑_{j} a_{j}π_{j}, and define f ∈ Π_{SR} by:

f(i, dy) = ∑_{j=1}^{n} [a_{j}π_{j}(i)/ (∑_{l=1}^{n} a_{l}π_{l}(i))] f_{j}(i, dy),

for i ∈ support (π), arbitrary otherwise. Then ν({i}, dy) = π(i)f(i, dy), i ∈ S. Now write (2.1) separately for each η = ν_{j}, 1 ≤ j ≤ n, multiply it through by a_{j}, and sum over j. Rearranging terms, one recovers (2.1) for ν. Thus ν ∈ G. □

We now establish a technical lemma for later use. Let ν = π̂_{f} ∈ G. Now suppose that for some j ∈ support (π) (say, j = 1), we have f(j, dy) = f(1, dy) = aφ_{1}(dy) + (1 − a)φ_{2}(dy) for some a ∈ (0, 1) and φ_{1} ≠ φ_{2} in P(U). Define f′, f′′ ∈ Π_{SR} by:

f′(i) = f′′(i) = f(i), i ≠ 1
f′(1) = φ_{1}, f′′(1) = φ_{2}.

Lemma 2.3 Both f′, f′′ above admit invariant probability measures containing ‘1’ in their support.

Proof Changing f to f′ or f′′ affects only the probabilities of transitions out of 1. Let T, T′, T′′ denote the mean return times to 1 under f, f′, f′′ resp. Then clearly T = aT′ + (1 − a)T′′. Since T < ∞, 1 > a > 0, we have T′, T′′ < ∞, implying the claim. □

Let G_{e} ⊂ G denote the set of extreme points of G.

Lemma 2.4 Every ν ∈ G_{e} is of the form ν = π̂_{f} for some f ∈ Π_{SS} and π ergodic under f.

Proof Let ν ∈ G_{e} with ν({i}, dy) = π(i)f(i, dy). For i ∉ support (π), set f(i) = some Dirac measure, without affecting ν. Let i ∈ support (π), say, i = 1. Suppose f(1, dy) = aφ_{1}(dy) + (1 − a)φ_{2}(dy) for some a ∈ (0, 1), φ_{1} ≠ φ_{2} in P(U). Define f′, f′′ as above and let π_{1}, π_{2} be ergodic probability measures under f′, f′′ resp. containing 1 in their supports. Pick b ∈ (0, 1) such that

a = bπ_{1}(1)/(bπ_{1}(1) + (1 − b)π_{2}(1)),

which is possible because π_{1}(1), π_{2}(1) > 0. Let π′ = bπ_{1}+(1−b)π_{2}, ν′({i}, dy) = π′(i)f(i, dy). A computation similar to that in Lemma 2.2 shows that ν′ satisfies (2.1) and hence ν′ = π̂′_{f} ∈ G. Also, support (π′) = support (π_{1})∪ support (π_{2}) and for i, j ∈ S,

∫ P (j/i, y)f(i, dy) = a ∫ P (j/i, y)f′(i, dy)
+(1 − a) ∫ P (j/i, y)f′′(i, dy).  (2.2)

Since π_{1} (resp., π_{2}) is ergodic under f′ (resp., f′′), any two states in its support communicate under f′ (resp., f′′) and therefore under f in view of (2.2) above. Since 1 is in support (π_{1})∩ support (π_{2}), it follows that support (π′) is a single communicating class under f. Thus π′ is an ergodic probability measure under f. If π is also ergodic, we must have π = π′ and ν = ν′. As in the proof of Lemma 2.2, one can then verify that ν′ = bν_{1} + (1 − b)ν_{2} where ν_{1}({i}, dy) = π_{1}(i)f′(i, dy) and ν_{2}({i}, dy) = π_{2}(i)f′′(i, dy). Since 0 < b < 1 and ν_{1} ≠ ν_{2}, ν ∉ G_{e}, a contradiction. Suppose π is not ergodic under f. Then π = cπ^{1} +(1−c)π^{2} for c ∈ (0, 1) and π^{1}, π^{2} ∈ P(S) which are distinct invariant probability measures under f. Then ν = cν^{1} + (1 − c)ν^{2} where ν^{j}({i}, dy) = π^{j}(i)f(i, dy), i = 1, 2 are clearly distinct elements of G. Thus ν ∉ G_{e}, a contradiction. So, (i) π must be ergodic under f, and (ii) (2.2) is impossible, i.e., f(i, dy) is Dirac for i ∈ support (π). This completes the proof. □

Let S̄ = S ∪ {∞} denote the one point compactification of S and view S ⊂ S̄ via the natural embedding. Likewise, P(S × U) ⊂ P(S̄ × U) via the natural embedding. Let Ḡ be the closure of G in P(S̄ × U) and Ḡ_{e} the set of its extreme points. The statement of the next lemma requires familiarity with Choquet’s theorem, which we recall here.

Let E be a Haussdorff locally convex topological vector space and X ⊂ E a convex compact metrizable subset. Given μ ∈ P(X), call x its barycenter if f(x) = ∫ fdμ for all continuous affine f : X → R.

Theorem 2.1 (Choquet) Each x ∈ X is the barycenter of some μ ∈ P(X) supported on the extreme points of X.

See [14], pp.140-141, for a proof. Metrizability of X ensures that the set of its extreme points is F_{σ}, hence measurable ([14], p.138), whereas compactness of X ensures that it is nonempty ([14], pp.105).

Lemma 2.5 G_{e} ⊂ Ḡ_{e} and any ν ∈ G is the barycenter of a probability measure on G_{e}.

Proof Any ν ∈ G_{e}\Ḡ_{e} must be a convex combination of two distinct elements of Ḡ at least one of which must assign strictly positive probability to {∞} × U. But then so will ν, a contradiction. Thus G_{e} ⊂ Ḡ_{e}. Now, if G is compact, G_{e} ≠ ϕ and G_{e} = Ḡ_{e}, whence the second claim follows from Theorem 2.1. If not, apply the theorem to Ḡ. Then Ḡ_{e} ≠ ϕ and ν is the barycenter of a probability measure Φ on Ḡ_{e}. If Φ(Ḡ_{e}\G_{e}) > 0, we must have ν({∞} × U) > 0, a contradiction. Thus Φ(G_{e}) = 1. □

Finally, we have:

Lemma 2.6 Each ν ∈ Ḡ is of the form : For A ⊂ S̄ × U Borel,

ν(A) = δν′(A ∩ (S × U)) + (1 − δ)ν′′(A ∩ ({∞} × U))  (2.3)

with δ ∈ [0, 1], ν′ ∈ G and ν′′ ∈ P({∞} × U).

Proof Clearly, (2.3) holds for some ν′ ∈ P(S × U). The claim is trivial for δ = 0. For δ = 1, ν′ = ν ∈ G. Thus let δ ∈ (0, 1). Let ν_{n} ∈ G, n ≥ 1, be such that ν_{n} → ν in Ḡ. Suppose

ν_{n}(i, dy) = π_{n}(i)f_{n}(i, dy), n ≥ 1.

Then for j ∈ S,

∫ P (j/·, ·)dν_{n} = ν({j} × U), n ≥ 1.

Since {j} × U is both open and closed in S̄ × U, we have

ν_{n}({j} × U) → ν({j} × U) = δν′({j} × U).

Letting S(N) = {0, 1, …, N} ⊂ S,

lim inf_{n→∞} ∫ P (j/·, ·)dν_{n} ≥ lim_{n→∞} ∫_{S(N)×U} P (j/·, ·)dν_{n}
= ∫_{S(N)×U} P (j/·, ·)dν
= δ ∫_{S(N)×U} P (j/·, ·)dν′
→ δ ∫ P (j/·, ·)dν′

as N → ∞. Combining the two,

∫ P (j/·, ·)dν′ ≤ ν′({j} × U).

Both sides add up to one when summed over j, so equality must hold for all j. Therefore ν′ ∈ G by Lemma 2.1. □

These lemmas form the backdrop for the convex programming problem we describe next.

2.2 The convex programming problem

Recall that if f ∈ Π_{SR} has an ergodic probability measure π and X_{0} ∈ support (π) a.s., then the ergodic cost a.s. equals ∫ kdπ̂_{f}. This suggests the convex programming problem:

Minimize ∫ kdμ over μ ∈ G.

Equivalently:

Minimize ∫ kdμ over {μ ∈ P(S × U): (2.1) holds }.

This displays it as an infinite dimensional linear program.

Let μ^{∗} ∈ G be such that

α =^{Δ} inf_{μ∈G} ∫ kdμ ≤ ∫ kdμ^{∗} ≤ α + ϵ

for some ϵ ≥ 0. (Note that such a μ^{∗} is guarranteed to exist for ϵ > 0.) Such a μ^{∗} is said to be ϵ-optimal (or optimal if ϵ = 0). Lemma 2.7 For ϵ ≥ 0, if there is an ϵ-optimal μ^{∗} ∈ G, then there is an ϵ-optimal \overline{μ} ∈ G_{e}. Proof By Choquet’s theorem, there exists a Φ ∈ P(G_{e}) such that

α ≤ ∫ kdμ^{∗} = ∫_{G_{e}} (∫ kdμ) Φ(dμ) ≤ α + ϵ.

Thus for some \overline{μ} ∈ support (Φ), α ≤ ∫ kd\overline{μ} ≤ α + ϵ. □

We next consider two conditions under which an optimal μ^{∗} exists. Case 1: The near-monotone case

Call k(·, ·) near-monotone if

lim inf_{i→∞} min_{u} k(i, u) > α.  (2.4)

Lemma 2.8 Under (2.4), an optimal μ^{∗} ∈ G_{e} exists. Proof Let μ_{n} ∈ G, n ≥ 1, be such that ∫ kdμ_{n} ↓ α. Viewing G ⊂ P(\overline{S} ×U) as before, drop to a subsequence if necessary and suppose that μ_{n} → \overline{μ} in P(\overline{S} × U). Write \overline{μ} = δμ′ + (1 − δ)μ′′ as in (2.3). Pick N ≥ 1, ϵ > 0 such that inf_{n} k(i, u) ≥ α + ϵ for i ≥ N. For n ≥ 1, define

k_{n}(i, u) = k(i, u)I{i ≤ N + n} + (α + ϵ)I{i > N + n}.

Then ∀ j,

α ≥ lim inf_{n→∞} ∫ k_{j}dμ_{n} = δ ∫ k_{j}dμ′ + (1 − δ)(α + ϵ).

Let j ↑ ∞ on the right to obtain

α ≥ δ ∫ kdμ′ + (1 − δ)(α + ϵ) ≥ δα + (1 − δ)(α + ϵ).

Thus δ = 1 and ∫ kdμ′ = α. The claim now follows from Lemma 2.7. □

Case 2: The stable case

Here we assume G to be compact. Since μ → ∫ kdμ is lower semicontinuous, it attains a minimum on G, hence, by Lemma 2.7, on G_{e}.

We still need to show that the ‘optimum’ is an optimum with respect to all admissible strategies. In ‘Case 1’, this is true:

Lemma 2.9 In the near-monotone case, under any admissible strategy,

lim inf_{n→∞} \frac{1}{n} ∑_{m=0}^{n−1} k(X_{m}, Z_{m}) ≥ α a.s.  (2.5)

To prove this, we introduce P(S ×U)-valued process {ν_{n}} of ‘empirical measures’, defined by

∫ fdν_{n} = \frac{1}{n} ∑_{m=0}^{n−1} f(X_{m}, Z_{m}), f ∈ C_{b}(X × U).

Lemma 2.10 ν_{n} → \overline{G} a.s.

Proof Let C = {I_{{i}}, i ∈ S} ⊂ C_{b}(S). Then by the strong law of large number for martingales ([12]), pp. 53-54),

∑_{i} g(i)ν_{n}({i}, U) − ∫_{S×U} (∑_{j} P (j/i, a)g(j)) dν_{n} → 0 a.s.  (2.6)

Since C is countable, this holds for all sample points outside a common zero probability set. Fix one such sample point. Let \overline{ν} be a limit point of \{ν_{n}\} in P(\overline{S} × U) and write \overline{ν} = δν′ + (1 − δ)ν′′ with δ ∈ [0, 1] and ν′, ν′′ ∈ P(\overline{S} × U) supported on S × U and \{∞\} × U resp. By (2.6), ν′ satisfies (2.1) whenever δ > 0. Identifying ν′ with its restriction to S × U by abuse of notation, we have ν′ ∈ G, i.e., \overline{ν} ∈ \overline{G}. □

Proof of Lemma 2.9 Consider a sample point for which Lemma 2.4 holds and let \overline{ν} be a limit point of \{ν_{n}\} as above, say, ν_{n(l)} → \overline{ν}. Then for k_{n}’s as in Lemma 2.8 above,

lim inf_{l→∞} ∫ kdν_{n(l)} ≥ ∫ k_{j}d\overline{ν} ≥ δ ∫ k_{j}dν′ + (1 − δ)(α + ϵ), j ≥ 1.

Let j ↑ ∞ on the right to obtain

lim inf_{l→∞} ∫ kdν_{n(l)} ≥ δ ∫ kdν′ + (1 − δ)(α + ϵ) ≥ δα + (1 − δ)(α + ϵ),

in view of the preceding lemma. The claim follows. □

Case 2 needs more work. For simplicity, we assume that there is a single communicating class under any f ∈ Π_{SR}. Let F_{n} = σ(X_{m}, Z_{m}, m ≤ n), n ≥ 0, for an arbitrary admissible control sequence {Z_{n}} and the corresponding chain {X_{n}}. Let τ(i) = min{n > 0 : X_{n} = i}, i ∈ S. Lemma 2.11 For any {F_{n}}-stopping time τ, the regular conditional law of X_{τ+n}, n ≥ 0, on {τ < ∞} is a.s. the law of a controlled Markov chain on S with action space U and transition probabilities P (·/·, ·). Proof This is a straighforward consequence of the easily verified fact

E [(I_{{X_{τ+n+1}=i}} − P (i/X_{τ+n}, Z_{τ+n})) /F_{τ} ] = 0 a.s.

on {τ < ∞} for i ∈ S, n ≥ 0. □

Impose the additional condition:

(†)  sup E[τ(0)^{2}/X_{0} = 0] < ∞,

where the supremum is over all admissible control strategies. Remark To see that (†) is not implied by stability alone, conside a chain on {(0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (2, 2), (0, 3), …} with transition probabilities: for j ≥ 1,

P ((i, j)/(i + 1, j)) = 1, 0 ≤ i < j,
P ((0, 0)/(0, j)) = 1,
P ((j, j)/(0, 0)) = Cj^{−3}, where C = (∑_{n} n^{−3})^{−1} .

Then E[τ(0)/X_{0} = 0] < ∞, but E[τ(0)^{2}/X_{0} = 0] = ∞. Lemma 2.12 Under (†), {ν_{n}} are a.s. tight in P(S × U). Proof Define stopping times τ_{0} = 0, τ_{n+1} = min{m > τ_{n} : X_{m} = 0}, n ≥ 0. By (†) and Lemma 2.11, it follows that

sup_{n} E[(τ_{n+1} − τ_{n})^{2}] < ∞.

By the strong law of large numbers for martingales (valid because of (†)), we then have, for N ≥ 1,

lim_{n→∞} \frac{1}{n} ∑_{i=0}^{n−1} ( ∑_{m=τ_{i}}^{τ_{i+1}−1} I_{\{X_{m}≥N\}} − E [ ∑_{m=τ_{i}}^{τ_{i+1}−1} I_{\{X_{m}≥N\}}/F_{τ_{i}} ]) = 0 a.s.

Thus

lim sup_{n→∞} ν_{n}(\{N, N + 1, …\} × U) = lim sup_{n→∞} \frac{1}{n} ∑_{m=0}^{n−1} I_{\{X_{m}≥N\}}
≤ lim sup_{n→∞} \frac{1}{n} ∑_{i=0}^{n−1} ( ∑_{m=τ_{i}}^{τ_{i+1}−1} I_{\{X_{m}≥N\}})
= lim sup_{n→∞} \frac{1}{n} ∑_{i=0}^{n−1} E [ ∑_{m=τ_{i}}^{τ_{i+1}−1} I_{\{X_{m}≥N\}}/F_{τ_{i}} ]
≤ sup E [ ∑_{m=0}^{τ(0)−1} I_{{X_{m}≥N}}/X_{0} = 0] ,

where the supremum is over all admissible strategies and the last inequality holds by Lemma 2.12. Fix a sample point for which the foregoing holds true for all N ≥ 1. A standard dynamic programming argument allows us to replace the above supremum by the supremum over Π_{SR}, which is turn equals

sup_{f∈Π_{SR}} (E[τ(0)/X_{0} = 0] ( ∑_{i≥N} π_{f}(i))) ,

with π_{f} = the unique invariant probability under f ∈ Π_{SR}. By (†), this is bounded by a constant times sup_{f∈Π_{SR}} (∑_{i≥N} π_{f}(i)). This can be made arbitrarily small by increasing N in view of the compactness (hence tightness) of G. The claim follows. □

Corollary 2.1 For the stable case, under (†), (2.5) holds.

Proof This follows as in Lemma 2.9 on observing that, outside a zero probability set, any limit point \overline{ν} = δν′ + (1 − δ)ν′′ of \{ν_{n}\} as in Lemma 2.9 must have δ = 1 by virtue of the above lemma. □

3 Extensions

3.1 Other cost criteria

Recall the infinite horizon discounted cost control problem wherein we seek to minimize E [∑_{m=0}^{∞} β^{m}k(X_{m}, Z_{m})] for a discount factor β ∈ (0, 1). This is equivalent to minimizing ∫ kdμ for the ‘discounted occupation measure’ μ ∈ P(S × U) defined by

∫ hdμ = (1 − β)E [ ∑_{m=0}^{∞} β^{m}h(X_{m}, Z_{m})] , h ∈ C_{b}(S × U).

In particular, if f ∈ Π_{SR} is being used, one can disintegrate μ as μ({i}, du) = π(i)f(i, du). Note that π ∈ P(S) is given by

π = (1 − β)ν ( ∑_{m=0}^{∞} β^{m}P (f)^{m})  (3.1)

where P (f) is the transition matrix corresponding to f and ν the law of X_{0}. (Both π and ν are displayed here as row vectors.) From (3.1), it follows that π satisfies

π = (1 − β)ν + βπP (f).  (3.2)

The corresponding μ then satisfies

∑_{i} h(i)μ({i}, U) = (1 − β) ∑_{i} h(i)ν(i) + β ∑_{i,j} ∫ h(j)P (j/i, y)μ({i}, dy).  (3.3)

That π is the unique solution in P(S) to (3.2) for given ν follows by iterating (3.2) to recover (3.1). Similarly, a μ ∈ P(S × U) satisfying (3.3) can be disintegrated as μ({i}, dy) = π(i)f(i, dy) to deduce (3.2) from (3.3), whence it follows that (3.3) characterizes μ as the discounted occupation measure under the corresponding f ∈ Π_{SR} and initial law ν. An immediate consequence of this is:

Lemma 3.1 For any admissible {Z_{n}}, the corresponding discounted occupation measure is also the discounted occupation measure for some f ∈ Π_{SR} for the same initial law.

Proof Let ν denote the initial law and π the corresponding discounted occupation measure under {Z_{n}}. Disintegrate π as

π({i}, du) = ν(i)φ_{i}(du), i ∈ S,

and identify the map Φ : i ∈ S → φ_{i}(du) ∈ P(U) with an element of Π_{SR}, denoted by Φ again. Let {X̃_{n}} be a chain governed by Φ and {Z̃_{n}} the corresponding control sequence. Let f ∈ C_{b}(S × U) and define

g(i) = E [ ∑_{m=0}^{∞} β^{m}f(X̃_{m}, Z̃_{m})/X̃_{n} = i] , i ∈ S.

Define Y_{0} = g(X_{0}) and for n ≥ 1,

Y_{n} = ∑_{m=0}^{n−1} β^{m}f(X_{m}, Z_{m}) + β^{n}g(X_{n}),

W_{n} = Y_{n+1} − Y_{n}
= β^{n}f(X_{n}, Z_{n}) + β^{n+1}g(X_{n+1}) − β^{n}g(X_{n}).

Then

E [ ∑_{m=0}^{n} β^{m}f(X_{m}, Z_{m})] − E[g(X_{0})]

= E [ ∑_{m=0}^{n} W_{m}] − β^{n+1}E[g(X_{n+1})]

= E [ ∑_{m=0}^{n} E[W_{m}/X_{j}, Z_{j}, j ≤ m]] − β^{n+1}E[g(X_{n+1})]

= E [ ∑_{m=0}^{n} β^{m} [f(X_{m}, Z_{m}) + β ∑_{j} P (j/X_{m}, Z_{m})g(j) − g(X_{m})]] − β^{n+1}E[g(X_{m+1})].

Let n → ∞ to obtain

E [ ∑_{m=0}^{∞} β^{m}f(X_{m}, Z_{m})] − E[g(X_{0})]

= E [ ∑_{m=0}^{∞} β^{m} [f(X_{m}, Z_{m}) + β ∑_{j} P (j/X_{m}, Z_{m})g(j) − g(X_{m})]]

= E [ ∑_{m=0}^{∞} β^{m} [∫ f(X_{m}, u)φ_{X_{m}}(du) + β ∑_{j} g(j) ∫ P (j/X_{m}, u)φ_{X_{m}}(du) − g(X_{m})]]

(by our construction of Φ)

= 0,

because g(i) satisfies

g(i) = ∫ f(i, u)φ_{i}(du) + β ∑_{j} g(j) ∫ P (j/i, u)φ_{i}(du), i ∈ S.

Therefore, if we choose the law of X̃_{0} to be ν, we have

E [ ∑_{m=0}^{∞} β^{m}(X_{m}, Z_{m})] = E[g(X_{0})]
= E[g(X̃_{0})]
= E [ ∑_{m=0}^{∞} β^{m}f(X̃_{m}, X̃_{m})] .

Multiplying both sides by (1 − β), the claim follows in view of our arbitrary choice of f ∈ C_{b}(S × U). □

This allows us to restrict our attention to strategies in Π_{SR} a priori. Fix ν ∈ P(S). Let μ_{f} denote the discounted occupation measure corresponding to f ∈ Π_{SR}, written as μ_{f}({i}, dy) = π_{f}(i)f(i, dy), and let G = {μ_{f} : f ∈ Π_{SR}}.

Lemma 3.2 G is compact convex in P(S × U).

Proof That it is closed convex follows along the lines of Lemma 2.2. Compactness follows from tightness, which is a straightforward consequence of the easily verified tightness of the laws of [X_{0}, X_{1}, …] in P(S^{∞}) as {Z_{n}} varies over all admissible strategies. (See, e.g., [9], pp. 26-27). □

Now, let j ∈ support (π_{f}) be such that for some f′ ≠ f′′ in Π_{SR} and a ∈ (0, 1), f′(j) ≠ f′′(j), f′(i) = f′′(i) ∀ i ≠ j and f(i) = af′(i) + (1 − a)f′′(i) ∀ i. Since the passage from f to f′ or f′′ changes only the transition probabilities for leaving state j, one still has j ∈ support (π_{f′}) ∩ support (π_{f′′}). This is the counterpart of Lemma 2.3, which allows us to establish the following along the lines of Lemma 2.4.

Lemma 3.3 Extreme points of G correspond to f ∈ Π_{SS}.

The equivalent convex programming problem is to minimize ∫ kdμ over μ ∈ G = {μ : (3.3) holds }. As in the ‘stable case’ above, existence of an optimal f ∈ Π_{SS} is now ensured.

Similar treatments for the finite horizon and exit time problems are possible, with the latter requiring a suitable additional hypothesis to ensure that the mean exit time is bounded. There is, however, one important difference with the finite horizon problem: One has to replace Π_{SS} by Π_{MS} =^{Δ} the set of Markov strategies in Lemma 3.3 and the remark that follows it, where a Markov strategy is a strategy of the form X_{n} = v(X_{n}, n) for a measurable v : S × {0, 1, …, N} → U. See [9], Chapter IV, for details.

An important caveat here is that in the foregoing, it is not obvious that an optimal f ∈ Π_{SS} (or Π_{MS} as the case may be) can be found which is optimal regardless of the choice of ν. That it can indeed be falls out naturally from the traditional dynamic programming approach, but not in the convex analytic formulation above.

There is also an alternative approach to these criteria that treats them as special cases of the ergodic problem. For the discounted problem, (3.3) turns out to be the counterpart of (2.1) for the ergodic control of a modified chain that is reset to law ν at i.i.d. times {τ_{i}} distributed geometrically with parameter β. The intricacies of this approach do not seem warranted in discrete time control problems, where the above treatment is much easier. In continuous time problems like controlled diffusions, however, such embedding into ergodic control for discounted, finite horizon and exit time problems have been effectively used in [5], [21].

Finally, note that β → 1 in (3.3) leads to (2.1). This leads to the conclusion that any limit point in P(\overline{S} ×U) of a sequence \{μ_{n}\} of discounted occupation measures corresponding to {β(n)} ⊂ (0, 1) with β(n) → 1, must be of the form δν′ + (1 − δ)ν′′, where ν′ is an ergodic occupation measure, ν′′ is supported on {∞} × U and δ ∈ [0, 1]. In both nearmonotone and stable cases, one can then use familiar arguments (from section 2) to conclude that as β → 1, optimal discounted occupation measures tend to the set of optimal ergodic occupation measures. (The latter case also needs (†), which ensures that the laws of {X_{n}} and therefore the discounted occupation measures, remain in a tight set for a prescribed initial law, regardless of the choice of {Z_{n}} and as β → 1.) A similar development is possible for the finite horizon problem in the limit as the horizon becomes infinite.

3.2 General state spaces

In this section, we briefly outline extensions to more general, viz., Polish S, concentrating on the ergodic control problem. Denote by p(x, u, dy) ∈ P(S) the transition kernel for {X_{n}} with x ∈ S, u ∈ U. This is assumed to be continuous in (x, u). A q ∈ Π_{SR} will be given by a probability kernel x ∈ S → q(x, dy) ∈ P(U), with the corresponding transition kernel given by

\overline{p}(x, q, dy) =^{Δ} ∫_{U} q(x, du)p(x, u, dy)

If η(dx) ∈ P(S) is invariant under q, define the corresponding ergodic occupation measure by

ν(dx, du) = η(dx)q(x, du).  (3.4)

The set G of ergodic occupation measures in P(S × U) is then characterized by the fact that their disintegration (3.4) satisfies

∫_{S} ∫_{U} η(dx)q(x, du)p(x, u, dy) = η(dy).  (3.5)

It is easy to deduce from this that G is closed. Also, if ν_{i}(dx, du) = η_{i}(dx)q_{i}(x, dy) ∈ G, i = 1, 2, then

ν(dx, dy) = aν_{1}(dx, dy) + (1 − a)ν_{2}(dx, dy), a ∈ (0, 1),

satisfies (3.5) with η(dx) = aη_{1}(dx) + (1 − a)η_{2}(dx) and

q(x, dy) = Λ(x)q_{1}(x, dy) + (1 − Λ(x))q_{2}(x, dy)

for Λ(x) = a\frac{dη_{1}}{dη} (x). Thus G is convex.

Assume as before that k : S × U → R is continuous and bounded from below. The definition of ‘stable case’ above extends to general S in the obvious manner. As for nearmonotonicity, the definition can be retained if S is locally compact. If not, one must allow k(·, ·) to be extended real valued and suppose that the set D_{r} = {x : inf_{a} k(x, a) ≤ r} is compact for each r > 0. The reason +∞ must be allowed as a value for k(·, ·) is as follows: By Baire category theorem, S that is not locally compact cannot be σ-compact and thus cannot equal ∪_{r}D_{r}.

Under either condition, a cost-minimizing sequence in G can be shown to be relatively sequentially compact and one can mimick the arguments of section 2 to conclude that the map μ ∈ G → ∫ kdμ attains its minimum on G, hence on G_{e}.

If S is not compact but locally compact, we can embed it homeorphically into its one point compactification \overline{S} = S ∪ \{∞\}. Define empirical measures ν_{n} ∈ P(\overline{S} × U) by

ν_{n}(A × B) = \frac{1}{n} ∑_{m=0}^{n−1} I_{\{X_{m}∈A,Z_{m}∈B\}}, n ≥ 1,

where A, B are Borel in \overline{S}, U resp. Let \overline{G} = \{μ ∈ P(\overline{S} × U) : μ = aμ_{1} + (1 − a)μ_{2} for some a ∈ [0, 1], μ_{1} ∈ G, μ_{2}({∞} × A) = 1}.

Lemma 3.4 ν_{n} → \overline{G} a.s.

This is proved as in Lemma 2.10, with C any countable convergence determining class in C_{b}(S) (see [12], Chapter 2). For the near-monotone case, Lemma 2.2 now follows as before. The stable case is harder. Assume S to be locally compact as before and let B_{1}, B_{2} be concentric closed balls of radii r_{1} < r_{2} resp. in S. Define

σ_{1} = min\{m ≥ 0 : X_{m} ∈ \overline{B_{2}^{c}}\},
τ_{1} = min{m > σ_{1} : X_{m} ∈ B_{1}},
σ_{n+1} = min\{m > τ_{n} : X_{m} ∈ \overline{B_{2}^{c}}\},
τ_{n+1} = min{m > σ_{n} : X_{m} ∈ B_{1}},

for n ≥ 1. Assume that for any open B ⊂ S, P (∪_{n≥1}{X_{n} ∈ B}) = 1 regardless of the initial condition or control strategy. (This is a ‘recurrence’ condition.) Then τ_{n}, σ_{n} < ∞ a.s. ∀ n. The counterpart of (†) now is

sup_{x∈B_{1}} sup_{Π} E[τ_{1}^{2}/X_{0} = x] < ∞,  (3.6)

where the first supremum is over Π =^{Δ} the set of all control strategies.

Let D_{N}, N ≥ 1, be a concentric family of closed balls in S with radii N ≥ 1 respectively. Now mimick the proof of Lemma 2.12 to conclude that

lim sup_{n→∞} ν_{n}(D_{N}) ≤ sup_{x∈B_{1}} sup_{Π} E [ ∑_{m=0}^{τ_{1}} I_{{X_{m}∉D_{N} }}/X_{0} = x] a.s.

= sup_{x∈B_{1}} sup_{Π_{SR}} E [ ∑_{m=0}^{τ_{1}} I_{{X_{m}∉D_{N} }}/X_{0} = x]  (3.7)

where the equality follows by a standard dynamic programming argument. Now let f_{m} → f_{∞} in Π_{SR}, x_{m} → x_{∞} in B_{1} and let X_{n}^{m}, n ≥ 1, denote the chain governed by f_{m} with X_{0}^{m} = x_{m}, m = 1, 2, ⋯, ∞. Standard arguments along the lines of [9], pp. 26-28, show that {X_{n}^{m}} → {X_{n}^{∞}} in law. By Skorohod’s theorem ([12], pp.23-24), we may view these processes as being defined on a common probability space and the convergence as being a.s. Define stopping times {τ_{m}^{n}, n ≥ 1}, m ≥ 1, correspondingly.

Then

lim inf_{m→∞} ∑_{ℓ=0}^{τ_{1}^{m}} I_{{X_{l}^{m}∉D_{N} }} ≥ ∑_{ℓ=0}^{τ_{1}^{∞}} I_{{X_{ℓ}^{∞}∉D_{N} }}

a.s. and therefore

lim inf_{m→∞} E [∑_{ℓ=0}^{τ_{1}^{m}} I_{{X_{ℓ}^{m}∉D_{N} }}] ≥ E [∑_{ℓ=0}^{τ_{1}^{∞}} I_{{X_{ℓ}^{∞}∉D_{N} }}] .

Thus the map

(x, f) → E_{f} [ ∑_{m=0}^{τ_{1}} I_{{X_{ℓ}^{m}∉D_{N} }}/X_{0} = x] ,

with E_{f}[·] denoting the expectation under f ∈ Π_{SR}, is lower semicontinuous. As N ↑ ∞, the r.h.s. ↓ 0. By Dini’s theorem, this convergence is uniform in (x, f) ∈ B_{1} × Π_{SR}. Thus the r.h.s. of (3.7) can be made arbitrarily small by choosing N sufficiently large. We have proved:

Lemma 3.5 Under (3.6), {ν_{n}} remains tight a.s. under arbitrary control strategies.

Corollary 3.1 The conclusion of Lemma 2.10 holds in the present set-up.

This follows exactly as for countable S in view of the foregoing. Given that the optimum, when it exists, is attained on G_{e} = the set of extreme points of G, we shall characterize G_{e} next, albeit for a special case. We assume in addition to local compactness the following condition: There exists a σ-finite nonnegative measure λ on S such that p(x, u, dy) << λ(dy) ∀ x, u and furthermore, if φ(x, u, y) denote the corresponding density (i.e., p(x, u, dy) = φ(x, u, y)λ(dy)), then φ(·, ·, ·) is continuous, and {φ(x, u, ·) : x ∈ S, u ∈ U} bounded equicontinuous and bounded away from zero from below uniformly an compacts. (These conditions are satisfied, e.g., for several stochastic systems in R^{d} with additive Gaussian white noise).

This has the following important consequence: If η is an invariant probability distribution under q ∈ Π_{SR}, then

η(dy) = ∫_{S} η(dx)q(x, du)φ(x, u, y)dy,

implying that η has a density w.r.t. λ given by

ψ(y) = ∫_{S} η(dx)q(x, du)φ(x, u, y) > 0.

Then any two ergodic probability distributions under q are mutually absolutely continuous, hence identical. That is, if q admits an invariant probability distribution, it is unique and the corresponding {X_{n}} ergodic. Suppose now that G is compact.

Lemma 3.6 Q =^{Δ} {η ∈ P(S) : η invariant under some q ∈ Π_{SR}} is compact in the total variation norm topology.

Proof Let η_{n} ∈ Q be invariant under q_{n} ∈ Π_{RS}, n ≥ 1. Then ν_{n}(dx, dy) =^{Δ} η_{n}(dx)q_{n}(x, dy) ∈ G ∀ n. Since G is compact, ν_{n} → ν_{∞} (say) in P(S ×U) along a subsequence, denoted by {ν_{n}} again by abuse of notation. Then η_{n} → η_{∞} in P(S). Let ψ_{n} = dη_{n}/dλ for n = 1, 2, …, ∞. Under our assumptions, {ψ_{n}(·)} are equicontinuous and bounded. By the Arzela-Ascoli theorem, we may drop to a subsequence if necessary and suppose that ψ_{n}(·) → \overline{ψ}(·) in C(S). Thus for compactly supported f ∈ C(S),

∫ f(y)ψ_{n}(y)λ(dy) → ∫ f(y)\overline{ψ}(y)λ(dy).

But

∫ f(y)ψ_{n}(y)λ(dy) = ∫ fdη_{n} → ∫ fdη_{∞}.

Thus \overline{ψ} = ψ_{∞} and ψ_{n} → ψ_{∞} in C(S). By Scheffe’s theorem ([12], pp.26), η_{n} → η_{∞} in the total variation norm. This completes the proof. □

We shall now characterize the set G_{e} for the stable case, i.e., when all f ∈ Π_{SR} are stable and the corresponding G compact. Let q_{i} ∈ Π_{SR}, i = 0, 1, 2, be such that

q_{0}(x, dy) = aq_{1}(x, dy) + (1 − a)q_{2}(x, dy), q_{1} ≠ q_{2},

with a ∈ (0, 1). Let η_{i}, ν_{i}, i = 0, 1, 2, denote the corresponding invariant distributions and ergodic occupation measures resp., with ψ_{i} = dη_{i}/dλ, i = 0, 1, 2. Finally, let Q̃ = {ψ : S → R : ψ = dη/dλ for some η ∈ Q}.

Lemma 3.7 ν_{0} ∉ G_{e}.

Proof By setting q_{i}(x, dy) = q_{0}(x, dy), i = 1, 2, for x outside a ball B_{R} ⊂ S of a sufficiently large radius R > 0, we may assume without loss of generality that q_{1}(x, dy) = q_{2}(x, dy) for x ∉ B_{R}. Let q̃ ∈ Π_{SR}, with η̃(dx) = ψ̃(x)λ(dx) the corresponding invariant measure and ν̃(dx, dy) = η̃(dx)q̃(x, dy) the corresponding ergodic occupation measure. Define q̂ ∈ Π_{SR} by

q_{0}(x, dy) = \frac{bψ_{1}(x)q_{1}(x, dy) + (1 − b)ψ̃(x)q̂(x, dy)}{bψ_{1}(x) + (1 − b)ψ̃(x)}  (3.8)

with b ∈ (0, 1). In order that this indeed define a q̃ ∈ Π_{SR}, b must be chosen so that

\frac{bψ_{1}(x)}{bψ_{1}(x) + (1 − b)ψ̃(x)} ≤ a ∀x ∈ B_{R}.

(For x ∉ B_{R}, q_{0}(x) = q_{1}(x) and any choice of b will do.) For x ∈ B_{R}, such a choice of b is possible provided

inf_{Π_{SR},x∈B_{R}}{ψ(x) : ψ ∈ Q̃} > 0.

This is indeed so by our assumptions: If not, we have ψ_{n} ∈ Q̃, x_{n} ∈ B_{R}, n ≥ 1, with ψ_{n}(x_{n}) → 0. By dropping to a subsequence if necessary and using the Arzela-Ascoli theorem, let ψ_{n}(·) → ψ_{∞}(·) in C(S), x_{n} → x_{∞} in B_{R}. Then ψ_{∞} ∈ Q̃, implying ψ_{∞}(x_{∞}) > 0, a contradiction.Thus we can choose a b ∈ (0, 1) as desired. Fix one such b. Then (3.8) defines a map q̃ → q̂, or equivalently, η̃ ∈ Q → η̂ ∈ Q, η̂ being the invariant distribution under q̂. This map is continuous in the total variation norm: If η_{n}(dx) = ψ_{n}(dx)λ(dx) → η_{∞}(dx) = ψ_{∞}(x)λ(dx) in total variation, ψ_{n}(·) → ψ_{∞}(·) in C(S) as in the proof of Lemma 3.6. Letting ψ̂_{n} denote the image of ψ_{n} under the above map for n = 1, 2, …, ∞, it is easily verified from (3.8) that ψ̂_{n} → ψ̂_{∞} pointwise and hence, by Scheffe’s theorem, ψ̂_{n}(x)λ(dx) → ψ̂_{∞}(x)λ(dx) in total variation. Since Q is compact convex, Schauder fixed point theorem guarantees a fixed point for this map. That is, there exists a q^{∗} ∈ Π_{SR} with associated invariant distribution η^{∗}(dx) = ψ^{∗}(x)λ(dx) such that

q_{0}^{∗}(x, dy) = \frac{bψ_{1}(x)q_{1}(x, dy) + (1 − b)ψ^{∗}(x)q^{∗}(x, dy)}{bψ_{1}(x) + (1 − b)ψ^{∗}(x)}

Since q_{0} ≠ q_{1}, q_{0} ≠ q^{∗}. It is easily deduced from this that for ν^{∗}(dx, dy) = η^{∗}(dx)q^{∗}(x, dy),

ν_{0} = bν_{1} + (1 − b)ν^{∗}, ν_{1} ≠ ν^{∗},

i.e., ν_{0} ∉ G_{e}. □

If G is not compact, we need the following additional condition, called the ‘stability under local perturbations’: If q(x, dy), q′(x, dy) ∈ Π_{SR} agree for x outside a bounded subset of S and one of them is stable, so is the other. Note that G is closed for the same reasons as before. Let q_{i} ∈ Π_{SR}, i = 0, 1, 2, be as before with ν_{i}, i = 0, 1, 2, defined correspondingly as before.

Theroem 3.1 ν_{0} ∉ G_{e}.

The proof is essentially the same as before : Recall from the proof of Theorem 3.1 that for any stable q ∈ Π_{SR}, it suffices to look at the subset of G corresponding to the ergodic occupation measures for q̃ ∈ Π_{SR} that agree with q outside a ball B_{R} of radius R > 0 sufficiently large. By our assumption of ‘stability under local perturbations’, all such q̃ are stable, so the same proof works.

Corollary 3.2 The conclusion of Lemma 3.3 holds under the conditions of Lemma 3.7, 3.8.

4 Multiobjective problems

4.1 Constrained control: preliminaries

The first mutliobjective problem we consider is that of minimizing one cost with other secondary costs being required to satisfy prescribed bounds. Again we stick to the ‘ergodic’ set up of section 2 and shall use the notation therein. We start with some convex analytic preliminaries.

Recall the set G of ergodic occupation measures. View it as a subset of the space of finite signed measures on S. Let H be its intersection with m ≥ 1 closed half spaces thereof. Then H is closed convex. Let H_{e} be the set of its extreme points. The following is a special case of a result of Dubins [17].

Lemma 4.1 Any ν_{0} ∈ H_{e} can be expressed as a convex combination of k points in G_{e} for some k ≤ m + 1.

Proof Suppose G is compact. Suppose the claim is false and ν_{0} is expressible as a convex combination of k = m + 2 points in G, but not less. (A similar proof works for higher k.) Then ν_{0} lies in the interior of an (m + 2)-simplex B formed by these points in G_{e}. Let M = the (m+1)-dimensional affine space (i.e., translate of a linear subspace) generated by B, and C an open ball in M centered at ν_{0} and contained in the interior of B. Then C ⊂ B ⊂ G. Now consider the intersections with M of the m hyperplanes that form the boundaries of the half spaces defining H. Since at most m of them can intersect at a time, any intersection with M of the intersections of these hyperplanes must have a codimension of at most m in M and thus cannot have a corner in the interior of C. Thus ν_{0} ∉ H_{e}, a contradition. For noncompact G, argue as above with Ḡ_{e} in place of G_{e} and observe that if ν_{0} is a strict convex combination of points in Ḡ_{e}, the latter must be in G_{e}, because ν_{0} would otherwise assign a strictly positive probability to {∞} × U, a contradiction. The rest is as before.

In case ν_{0} cannot be expressed as a convex combination of finitely many extreme points of G, a simple adaptation of the above proof works. We claim that for any j ≥ 1, we can find j linearly independent finite line segments in G which have ν_{0} at their center. If this were not so for, say, j = j_{0} + 1, then ν_{0} would be in a j_{0}-dimensional face G′ of G and therefore expressible as a convex combiantion of j_{0}+1 extreme points of G′ by Caratheodory’s theorem ([14], p.106), therefore of G. This goes against the hypothesis, proving the claim. Now take j ≥ m + 2, consider the polytope generated by the end points of these line segments, and argue as before. □

Write ν_{0} as

ν_{0}({i}, dy) = π_{0}(i)f(i, du), i ∈ S,

corresponding of f ∈ Π_{SR}. By the above lemma, ν_{0} is a linear combination of ν_{1}, ⋯, ν_{k}, k ≤ m + 1, in G_{e} with strictly positive weights. Letting δ_{x}(du) denote the Dirac measure at x, we may disintegrate ν_{j}’s as

ν_{j}({i}, du) = π_{j}(i)δ_{ξ_{ij}}(du), i ∈ S, 1 ≤ j ≤ k.

By abuse of notation, let ξ_{j} : i → δ_{ξ_{ij}} denote the corresponding stationary strategy. Also, by the ergodic decomposition of the chain, π_{0} = ∑_{i=1}^{n} a_{i}π̃_{i} where a_{i} ∈ [0, 1] with ∑ a_{i} = 1 and {π̃_{i}} are ergodic invariant probability measure under f. In particular, π̃_{i}’s have disjoint supports. We denote these by {S_{i}} respectively.

Lemma 4.2 For 1 ≤ j ≤ k, support (π_{j}) ⊂ S_{i} for some i.

Proof If not, two states in two distinct S_{i}’s would communicate with each other under the stationary policy ξ_{j}, hence under f(cf. the proof of Lemma 2.4), a contradiction. □

For i ∈ S with π_{0}(i) > 0, let N(i) = {u ∈ U : u = ξ_{ij} for some j, 1 ≤ j ≤ k, satisfying π_{j}(i) > 0}. Let n(i) = |N(i)| − 1. Then for each i, n(i) is the ‘number of randomizations at i’ for f. To understand this terminology, observe that f_{i} will be of the form

f(i, dy) = ∑_{ℓ=1}^{|N(i)|} (a′_{ℓ}π′_{ℓ}(i)ξ′_{ℓ}(i, dy)/ [ ∑_{n=1}^{|N(i)|} a_{n}π′_{n}(i)])  (4.1)

where ξ′_{l}(i, dy) are Dirac (cf. proof of Lemma 2.2) with ergodic distributions π′_{ℓ} and {a′_{j}} satisfy a′_{j} > 0, ∑_{ℓ} a′_{ℓ} = 1. Thus |N(i)| = 2 corresponds to randomizing between two choices, i.e., a single randomization, and so on. By convention, n(i) = 0 if N(i) = ϕ.

Pick i ∈ S (if any) such that π_{0}(i) > 0, n(i) > 0. Let N(i) = {u(1), u(2), ⋯, u(n(i)+1)}. Then f(i, dy) is a strict convex combination of the Dirac measures at u(j)’s. Define ψ^{ij} ∈ Π_{SR} by:

ψ^{ij}(ℓ, dy) = f(ℓ, dy), ℓ ≠ i,
= δ_{u(j)}(dy), ℓ = i,

Lemma 4.3 ν_{0} is a strict convex combination of distinct elements μ_{1}, ⋯, μ_{n(i)+1} of G, where μ_{j} is an ergodic occupation measure under ψ^{ij} for each j. Furthermore, μ_{1}, ⋯, μ_{n(i)+1} form the corners of an (n(i) + 1) simplex.

Proof If π_{0} is ergodic, the first claim follows by iterating the argument used in the proof of Lemma 2.4. If not, pick the π̃_{ℓ} for which π̃_{ℓ}(i) > 0 and apply the same argument. Suppose the second claim is false. Then ν_{0} can be expressed as a strict convex combination of elements from {μ_{1}, ⋯, μ_{n(i)+1}} in at least two distinct ways. But then (4.1) applied to the present situation allows us to write a finitely supported probability measure f(i, dy) as a strict convex combination of distinct Dirac measures in two different ways, an impossibility. The claim follows. □

Call this (n(i) + 1)-simplex the ‘perturbution simplex’ at i, denoted by Q(i).

Lemma 4.4 Let ν_{1} ≠ ν_{2} in Q(i), with

ν_{j}({l}, du) = π_{j}(l)φ_{jl}(du), l ∈ S, j = 1, 2.

Let π_{j}(l) > 0. Then φ_{1l} = φ_{2l} for l ≠ i and φ_{1i} ≠ φ_{2i}.

Proof The claim for l ≠ i is immediate from (4.1) and our definition of Q(i). That φ_{1i} ≠ φ_{2i} follows from (4.1) and the easily verifiable fact: for n > 1, b_{1}, …, b_{n} > 0, the map

[a_{s}, …, a_{n}] ∈ {[x_{1}, …, x_{n}] : 0 < x_{i} < 1 ∀ i, ∑_{i} x_{i} = 1} →

[a_{1}b_{1}/c, a_{2}b_{2}/c, …, a_{n}b_{n}/c] ∈ (0, 1)^{n},

with c = ∑_{i=1}^{n} a_{i}b_{i}, is one-one. □

Let Y (i) = the n(i)-dimensional affine space, in the space of finite signed measures on S × U, spanned by Q(i) for i as above.

Lemma 4.5 If j ≠ i satisfies π_{0}(j) > 0, n(j) > 0, then Y (i) ∩ Y (j) = {ν_{0}}.

Proof Suppose not. Then there must exist a \overline{ν} ≠ ν_{0}, \overline{ν} ∈ Q(i) ∩ Q(j). Let Z be the line segment joining ν_{0}, \overline{ν}. Then Z ⊂ Q(i) ∩ Q(j). Write a typical ν ∈ Z as

ν({l}, du) = π(l)φ_{l}(du), l ∈ S.

Note that for ν ≠ \overline{ν} in Z, support (π) ⊂ support (π_{0}). As ν moves along Z, Lemma 4.4 and the fact that Z ⊂ Q(i) implies φ_{j}(·) = f(j, ·) all along. Interchange the roles of i, j to conclude φ_{i}(·) = f(i, ·) all along, a contradiction to \overline{ν} ≠ ν_{0} in view of Lemma 4.4. The claim follows. □

Lemma 4.6 Let i_{1}, i_{2}, …, i_{r+1} be different states in S with n(i_{j}) > 0 for all j and α_{1}, α_{2}, …, α_{r} ∈ [0, 1] with ∑_{i=1}^{r} α_{i} = 1. Then

{α_{1}Q(1) + α_{2}Q(2) + ⋯ + α_{1}Q(r)} ∩ Q(i_{r+1}) = {ν_{0}}.

Proof For r = 1, this reduces to the preceding lemma. The general claim follows by induction using an argument similar to that above at each state. □

Let L(i) = Y (i) − ν_{0} when n(i) > 0. (That is, L(i) is Y (i) translated by ν_{0}.)

Corollary 4.1 dim(L(i_{1}) + ⋯ + L(i_{r})) = ∑_{n=1}^{r} dim(L(i_{n})).

This is immediate from the preceding lemma. Thus L(i_{1}) + L(i_{2}) + ⋯ + L(i_{r}) is a direct sum.

Lemma 4.7 ∑_{i} n(i) ≤ m.

Proof If not, for some {i_{1}, …, i_{l}} ⊂ S, ∑_{j=1}^{ℓ} n(i_{ℓ}) ≥ m + 1. By the foregoing, corners of Q(i_{1}), …, Q(i_{l}) together form a polytope with ∑_{m=1}^{l} n(i_{m}) ≥ m + 1 dimensional relative interior that contains ν_{0}. Now argue as in the proof of Lemma 4.1 to get a contradiction.

□

This completes the convex analytic preliminaries for the constrained control problem.

4.2 Constrained control : main results

The constrained control problem is

Minimize ∫ k_{0}dν  (4.2)

subject to

ν ∈ G, β_{i} ≤ ∫ k_{i}dν ≤ α_{i}, 1 ≤ i ≤ m,  (4.3)

where k_{i} : S × U → [0, ∞) are prescribed continuous functions and α_{i}, β_{i} prescribed nonnegative scalars for 0 ≤ i ≤ m. Let H = {ν ∈ G : β_{i} ≤ ∫ k_{i}dν ≤ α_{i}, 1 ≤ i ≤ m}, assumed nonempty. Also assume that

α_{0} =^{Δ} inf_{ν∈H} ∫ k_{0}dν < ∞.

As before, we consider two cases:

Case 1: Near-monotone case

β_{i} = 0 ∀ i, and lim inf_{j→∞} inf_{u} k_{i}(j, u) > α_{i}, 0 ≤ i ≤ m

Case 2: Stable case

G is compact and H closed, hence compact.

Since the upper inequality in (4.3) is preserved anyway under convergence in P(S × U), the closedness of H is the requirement that the lower inequality also do so. This is the case, e.g., if β_{i}’s are zero or if k_{i}’s are bounded, 1 ≤ i ≤ m.

Lemma 4.8. In either case, the minimization problem above has a solution in H_{e}.

Proof Existence of a minimizer in H follows by its compactness in Case 2 and as in Lemma 2.8 in Case 1: One repeats those arguments for each k_{j} to conclude that if {ν_{n}} ⊂ H satisfy ∫ k_{0}dν_{n} ↓ α_{0}, then {ν_{n}} is tight and every limit point ν thereof satisfies.

∫ k_{0}dν = α_{0}, ∫ k_{j}dν ≤ α_{j}, 1 ≤ j ≤ m.

The existence of a minimizer in H_{e} then follows from Choquet’s theorem as in Lemma 2.7. □

Suppose we revert to our original ‘almost sure’ formulation of the ergodic control problem and consider the constrained version thereof. That is, we seek to minimize almost surely, over all admissible {Z_{n}}, the quantity

lim sup_{n→∞} \frac{1}{n} ∑_{m=0}^{n−1} k_{0}(X_{m}, Z_{m}),

subject to: for 1 ≤ i ≤ m,

lim sup_{n→∞} \frac{1}{n} ∑_{m=0}^{n−1} k_{i}(X_{m}, Z_{m}) ≤ α_{i} a.s.,

lim inf_{n→∞} \frac{1}{n} ∑_{m=0}^{n−1} k_{i}(X_{m}, Z_{m}) ≥ β_{i} a.s..

As in section 2, this can be reduced to the problem (4.2)-(4.3) without any loss of generality by using our characterization of limit points of empirical measures in Lemma 2.10, with the proviso that we add condition (†) of section 2 to ‘Case 2’ above. We refer to this modification as ‘Case 2′’.

Theorem 4.1 In both Case 1 and Case 2′, there exists an optimal f ∈ Π_{SR} that requires at most m randomizations. Furthermore, if H has a nonempty interior in G, then these exist λ_{1}, ⋯, λ_{2m} ≥ 0 such that for all ν ∈ G and η_{1}, ⋯, η_{2m} ≥ 0, we have : If ν_{0} ∈ H_{e} is the optimal point, then

∫ k_{0}dν + ∑_{i=1}^{m} λ_{i}(α_{i} − ∫ k_{i}dν) + ∑_{i=1}^{m} λ_{m+i} (∫ k_{i}dν − β_{i})

≥ ∫ k_{0}dν_{0} + ∑_{i=1}^{m} λ_{i}(α_{i} − ∫ k_{i}dν_{0}) + ∑_{i=1}^{m} λ_{m+i} (∫ k_{i}dν_{0} − β_{i})

≥ ∫ k_{0}dν_{0} + ∑_{i=1}^{m} η_{i}(α_{i} − ∫ k_{i}dν_{0}) + ∑_{i=1}^{m} η_{m+i} (∫ k_{i}dν_{0} − β_{i}) .

Proof The existence of an optimal f ∈ H_{e} is argued above. That it requires at most m randomizations follows from Lemma 4.7 and the observation that only one of the inequalities in (4.3) can be active at a time for each i (except in the degenerate case α_{i} = β_{i}, which is handled analogously). The last claim follows from standard Lagrange multiplier theory ([22], pp.216-219). □

A similar treatment is possible for constrained problems with other (e.g., discounted) cost criteria. An important difference there is the role played by the initial distribution, usually held fixed, which cannot be wished away. Any claims of optimality will be relative to a specific initial distribution (or more generally, a convex compact set thereof).

4.3 A general multiobjective problem

The foregoing had one ‘primary’ cost function k_{0}, whose average was to be minimized subject to constraints on several ‘secondary’ costs k_{1}, ⋯, k_{m}. In traditional ‘multiobjective’ framework, one wants to treat them on a comparable footing. Since all of them cannot in general be minimized simultaneously, one seeks a ‘Pareto point’, defined next. We stick to the ergodic control framework of the preceding section.

Let k̂(ν) = [∫ k_{0}dν, ⋯, ∫ k_{m}dν] ∈ R^{m+1} denote the cost vector corresponding to ν ∈ G and define W = {k̂(ν) : ν ∈ G}, which will be a closed convex subset of R^{m+1}. On W, define a partial order ‘<’ by : x = [x_{0}, ⋯, x_{m}] < y = [y_{0}, ⋯, y_{m}] if x_{i} ≤ y_{i} for all i, with a strict inequality for at least one i. Call x^{∗} ∈ W a Pareto point if there is no z ∈ W for which z < x^{∗}, It is easy to see that a minimizer of ∑_{i=0}^{m} λ_{i}x_{i} over x = [x_{0}, ⋯, x_{n}] ∈ W for any choice of λ_{i} > 0, 0 ≤ i ≤ m, will be a Pareto point. In fact, if W is a polytope (i.e., convex hull of finitely many extreme points), then all Pareto points can be obtained thus. By our characterizaton of G_{e}, it follows that if S and U are finite, then G and hence W will have finitely many extreme points and the foregoing remark applies. More generally, a weaker claim holds, viz., the Pareto points obtained thus are dense in the set of all Pareto points. All this is a consequence of the celebrated Arrow-Barankin-Blackwell theorem [4].

More generally, Pareto points can be obtained by minimizing a ‘utility function’ U : W → R, which is any continuous function with the property : U(y) < U(x) wherever y < x. The function x → ∑_{i} λ_{i}x_{i} with α_{i} > 0 ∀i is just a special case of this. Another important case is as follows : Let k^{∗} = [min_{G} ∫ k_{0}dν, ⋯, min_{G} ∫ k_{m}dν] ∈ R^{m+1}, the so called ‘ideal point’. The nontrivial case is k^{∗} ∉ W. Let k̃ ∈ W be the unique point in W such that ||k^{∗} − k̃|| = min_{k∈W} ||k^{∗} − k||, corresponding to U(x) = ||x − k^{∗}||. It is easy to see that this will be a Pareto point. Finding k̃ is an abstract quadratic programming problem.

There is no reason why k̃ should correspond to any element of G_{e}. The following ‘approximation theorem’, however, justifies a search for good strategies among those that correspond to a randomization between finitely many points of G_{e}. Assume that k_{0}, ⋯, k_{m} are bounded.

Theroem 4.2 For any ν ∈ G, n ≥ 1, there exists a ν^{n} ∈ G such that ν^{n} is a convex combination of at most n points of G_{e} and

||k̂(ν) − k̂(ν^{n})|| = O (\frac{1}{n}) .

Proof Let ν be the barycenter of Φ ∈ P(G_{e}) and {ξ(i)} i.i.d. G_{e}-valued random variables with law Φ. Let Y (i) = [∫ k_{0}dξ(i), …, ∫ k_{m}dξ(i)] , i ≥ 1. Then {Y (i)} are i.i.d. with mean k̂(ν) and

E [||\frac{1}{n} ∑_{i=1}^{n} Y (i) − k̂(ν)||^{2}] = \frac{1}{n^{2}} · n · E[||Y (1) − k̂(ν)||^{2}] = \frac{C}{n}

for a constant C > 0. Thus for at least one sample point,

||\frac{1}{n} ∑_{i=1}^{n} Y (i) − k̂(ν)||^{2} < \frac{C}{n} .

The claim follows. □

Note, however, that this argument is not a constructive argument.

5 Concluding Remarks

The foregoing gives a reasonably self-contained account of the key aspects of the convex analytic approach to Markov decision processes. Nevertheless, it is by no means exhaustive. We briefly comment upon few important aspects thereof that were not addressed above.

(i) Dual problems

The ‘dual’ linear program to the infinite dimensional linear program over occupation measures establishes a link with the traditional dynamic programming approach. To see how this comes by, we first recall the relevant results from the theory of infinite dimensional linear programming [3].

Two topological vector spaces X, Y are said to form a dual pair if there exists a bilinear form ⟨·, ·⟩ : X ×Y → R such that the functions x → ⟨x, y⟩ for y ∈ Y separate points of X and the functions y → ⟨x, y⟩ for x ∈ X separate points of Y. Endow X with the coarsest topology required to render the former family of maps continuous, and Y with the dual topology. Let P be the positive cone in X and P^{∗} ⊂ Y the dual cone: P^{∗} = {y ∈ Y : ⟨x, y⟩ ≥ 0, x ∈ P }.

Let Z, W be another dual pair topologized in a similar manner and F : X → Z a continuous linear map. Define F^{∗} : W → X^{∗} by ⟨F x, w⟩ = ⟨x, F^{∗}w⟩, x ∈ X, w ∈ W. The primal LP problem is:

Minimize ⟨x, c⟩ s.t. F x = b, x ∈ P,

with b ∈ Z, c ∈ Y prescribed. Let α denote the infimum of ⟨x, c⟩ subject to these constraints. The dual problem is

Max ⟨b, w⟩ s.t. − F^{∗}x + c ∈ P^{∗}, w ∈ W.

Let α′ denote the supremum of ⟨b, w⟩ subject to these constraints. It is known that α ≥ α′. Let C = {x ∈ P : F x = b}, D = {(F x, ⟨x, c⟩) : x ∈ P }. The following results gives conditions for the absence of a ‘duality gap’.

Theorem 5.1 ([3], p.53) If C ≠ ϕ, D is closed and x → ⟨x, c⟩ attains its minimum on C, then α = α′.

Applying this to the linear programming formulation of ergodic control in section II, the dual problem and Theorem 5.1 lead to the following characterization of the optimal cost α:

Corollary 5.1 α = sup {a : min_{u} (k(i, u) + f(i) − ∑_{j} P (j/i, u)f(j)) ≥ a, f : S → R}.

Likewise, dualising the primal problem for discounted cost problem leads, in view of Theorem 5.1, to the following characterization of the ‘value function’ of dynamic programming, defined as

V (i) = inf_{admissible controls} E [ ∑_{m=0}^{∞} β^{m}k(X_{m}, Z_{m})/X_{0} = i] , i ∈ S :

Corollary 5.2 V (i) = sup{f(i) : inf_{u}(k(i, u) − f(i) + β ∑_{j} P (j/i, u)f(j)) ≥ 0, f : S → R}.

Similar results are possible for the finite horizon and exit time problems, as well as for general state spaces. See [20] for an extensive account of the latter.

(ii) Computational aspects

An important motivation for linear/convex programming approaches has been the prospect of using to advantage the computational machinery of these fields. Linear programming has always been a ‘third’ approach to computation in Markov decision processes, after value and policy iteration. Despite the proven convergence results and ease of formulation for the latter, linear programming remains an attractive alternative because it facilitates the use of commercial LP packages which are primed to exploit any extra structure the problem may have to offer. For constrained problems, dynamic programming approach proves quite awkward, while in the linear programming approach the constraints merely translate into additional constraints for the linear program. See [24] for an extensive account of the traditional linear programming algorithms for Markov decision processes and [1] for the corresponding development for constrained problems.

(iii) Mixed problems

There has been some interest in Markov decision processes with mixed criteria, such as criteria that combine ergodic and discounted costs. (See, e.g., [18].)

(iv) Game theoretic formulations

An interesting formulation of multiobjective problem under uncertainty treats it as a game against an antagonist, taking the ‘worst case’ approach, and seeks to drive the vector ergodic cost to a prescribed set of ‘acceptable values’ [27]. Though similar in spirit to section 4 above, this approach differs significantly in the kind of techniques used.

We conclude with a bibliographical note. Giving an extensive, even representative bibliography is a major task I do not wish to undertake. The following therefore is confined only to a few key antecedents and the immediate resources for the material presented here.

Further references can be found in [1], [9], [20], [24].

The convex/linear programming approach, as already mentioned, goes back to Manne [23]. The approach to ergodic control taken in section 2 first appeared in [7] for the irreducible case. Related results also appear in [2]. The fully general case presented here appears in [11].

The corresponding results for other cost criteria are from [6], [9]. For the general state space case, the treatment that appears here is new in principle, but closely mimicks the corresponding theory for controlled diffusions developed in [10], [13].

The constrained control problem dates back to [15], [16]. The convex analytic approch presented here is from [11], which improves upon earlier results from [8], [9], [25]. The ‘sample path’ or ‘a.s.’ variant was studied in [26], though our treatment is different. See [18] for results in the discounted cost framework. The multiobjective problem studied in subsection 4.2 is from [19], except for Theorem 4.2 which is new. Reference [19] also considers computational issues. Interesting classes of Pareto points have been identified in the discounted case in [18].

References

[1] ALTMAN, E., Constrained Markov decision processes, Reseach Report No. 2574, INRIA Sophia-Antipolis, 1994.

[2] ALTMAN, E.; SHWARTZ, A., Markov decision problems and state-action frequencies, SIAM J. Control and Optim. 29 (1991), pp.786-809.

[3] ANDERSON, E.J.; NASH, P., Linear Programming in Infinite Dimensional Spaces, John Wiley, Chichester, 1987.

[4] ARROW, K.J.; BARANKIN, E.W.; BLACKWELL, D., Admissible points of convex sets, in ‘Contributions to the Theory of Games’, H.W. Kuhn and A.W. Tucker (eds.), Princeton Uni. Press, Princeton, NJ, 1950, pp.87-91.

[5] BHATT, A.G.; BORKAR, V.S., Occupation measures for controlled Markov processes: characterization and optimality, The Annals of Prob. 24 (1996), pp.1531-1562.

[6] BORKAR, V.S., A convex analytic approach to Markov decision processes, Prob. Theory and Related Fields 78 (1988), pp.583-602.

[7] BORKAR, V.S., Control of Markov chains with long-run average cost criterion : the dynamic programming equations, SIAM J. Control and Optim. 27 (1989), pp.642-657.

[8] BORKAR, V.S., Controlled Markov chains with constraints, Sadhana : Indian Academy of Sciences Proc. in Engg. Sciences 15 (1990), pp.405-413.

[9] BORKAR, V.S., Topics in Controlled Markov Chains, Pitman Research Notes in Maths. No.240, Longman Scientific and Technical, Harlow, England, 1991.

[10] BORKAR, V.S., Controlled diffusions with constraints II, J. Math. Analysis and Appl. 176 (1993), pp.310-321.

[11] BORKAR, V.S., Ergodic control of Markov chains with constraints - the general case, SIAM J. Control and Optim. 32 (1994), pp. 176-186.

[12] BORKAR, V.S., Probability Theory : An Advanced Course, Springer Verlag, New York, 1995.

[13] BORKAR, V.S.; GHOSH, M.K.; Controlled diffusions with constraints, J. Math. Analysis and Appl. 152 (1990) pp.88-108.

[14] CHOQUET, G., Lectures on Analysis, Vol.II : Representation Theory, W.A. Benjamin, Inc., Reading, Mass., 1969.

[15] DERMAN, C., Finite State Markovian Decision Processes, Academic Press, New York, 1970.

[16] DERMAN, C.; KLEIN, M.; Some remarks on finite horizon Markovian decision models, Op. Research 13 (1965), pp. 272-278.

[17] DUBINS, L.; On extreme points of convex sets, J. Math. Analysis and Appl. 5 (1962), pp. 237-244.

[18] FEINBERG, E.; SHWARTZ, A.; Constrained discounted dynamic programming, Maths. of Op. Research 21 (1996), pp. 922-945.

[19] GHOSH, M.K.; Markov decision processes with multiple costs, Op. Research Letters 9 (1990), pp. 257-260.

[20] HERNANDEZ-LERMA, O.; LASSERRE, J.B.; Discrete-Time Markov Control Processes, Springer Verlag, New York, 1996.

[21] KURTZ, T.G., STOCKBRIDGE, R.; Existence of Markov controls and characterization of optimal Markov controls, SIAM J. Control and Optim. 36 (1998), pp. 609-653.

[22] LUENBERGER, D.G.; Optimization by Vector Space Methods, John Wiley, New York, 1969.

[23] MANNE, A., Linear programming and sequential decisions, Management Sci. 6 (1960), pp. 259-267.

[24] PUTERMAN, M.; Markov Decision Processes, John Wiley, New York, 1994.

[25] ROSS, K.W.; Randomized and past-dependent policies for Markov decision problems with multiple constraints, Op. Research 37 (1989), pp. 474-477.

[26] ROSS, K.W.; VARADARAJAN, R.; Markov decision processes with sample path constraints: the communicating case, Op. Research 37 (1989), pp. 780-790.

[27] SHIMKIN, N.; SHWARTZ, A.; Guarranteed performance regions in Markovian systems with competing decision makers, IEEE Trans. on Automatic Control 38 (1993), pp. 84-95.