MARKOV DECISION PROCESSES

Lester E. Dubins University of California

Berkeley, CA 94720

Ashok P. Maitra University of Minnesota Minneapolis, MN 55455

William D. Sudderth University of Minnesota Minneapolis, MN 55455

May 28, 2000

Chapter 1

Invariant Gambling Problems and Markov Decision Processes

Abstract

Markov decision problems can be viewed as gambling problems that are invariant under the action of a group or semi-group. It is shown that invariant stationary plans are almost surely adequate for a leavable, measurable, invariant gambling problem with a nonnegative utility function and a finite optimal reward function. This generalizes results about stationary plans for positive Markov decision models as well as measurable gambling problems.

1.1 Introduction

This paper introduces the notion of a gambling problem that is invariant, in a sense to be specified below, under the action of a group or a semigroup of transformations.

Our primary stimulus has been to understand more fully the relationship of Markov decision processes to gambling theory. It has long been known that these two theories are closely related (cf. Chapter 12 of Dubins and Savage (1965)) and perhaps each contains the other. However, it has not been possible to translate theorems about stationary plans, for example, directly from one theory to the other. It will be explained below how Markov decision processes may be viewed as invariant gambling problems. Subsequent sections will show how stationarity results in gambling theory (Dubins and Sudderth (1979)) are extended to invariant gambling problems and , in particular, to Markov decision problems. Our main interest here is in the reward structures. A comparative study of the measurable structures of the two theories was made by Blackwell (1976).

A secondary stimulus to us is the fact that there are a number of gambling problems which possess a natural group theoretic structure. Group invariance techniques have found many applications in statistical decision theory (cf. Eaton (1989) and the references therein) and could prove useful in Markov decision theory as well.

We will begin with a review of measurable gambling theory, and then introduce invariance.

1.2 Measurable Gambling Problems

Let F be a Borel set, that is, a Borel subset of a complete separable metric space. Let ℙ(F) be the set of probability measures on the Borel sigma-field of subsets of F. Then ℙ(F), equipped with its customary weak topology, is again a Borel set. A gambling house on F is a subset Γ of F × ℙ(F) such that each section Γ(x) of Γ at x ∈ F is nonempty. A strategy σ is a sequence σ_{0}, σ_{1}, … such that σ_{0} ∈ ℙ(F), and , for each n ≥ 1, σ_{n} is a universally measurable function from X^{n} into ℙ(F). A strategy is available in Γ at x if σ_{0} ∈ Γ(x) and σ_{n}(x_{1}, x_{2}, …, x_{n}) ∈ Γ(x_{n}) for every n ≥ 1 and x_{1}, x_{2}, …, x_{n} ∈ X.

Each strategy σ determines a unique probability measure, also denoted by σ, on the Borel subsets of the history space H = F^{N}, where N is the set of positive integers and H is given the product topology. Let X_{1}, X_{2}, … be the coordinate process on H; then, under the probability measure σ, X_{1} has distribution σ_{0} and , for n ≥ 1, X_{n+1} has conditional distribution σ_{n}(x_{1}, x_{2}, …, x_{n}) given X_{1} = x_{1}, X_{2} = x_{2}, …, X_{n} = x_{n}.

A measurable gambling problem is a triple (F, Γ, u), where F, the fortune space, is a nonempty Borel set, Γ is a gambling house on F which is an analytic subset of F × ℙ(F), and u, the utility function, is upper analytic which means that {x : u(x) > a} is an analytic subset of F for every real a. Such structures with Γ and u both Borel were introduced by Strauch (1967); the extension to analytic Γ and upper analytic u is due to Meyer and Traki (1973).

In the theory of gambling (Dubins and Savage (1965)) there are two natural approaches to a gambling problem. In leavable problems, the gambler is allowed to stop playing at any time, whereas in nonleavable problems, the gambler is compelled to continue playing forever.

Consider first a leavable problem and define a stop rule t to be a universally measurable function from H into {0, 1, … } such that whenever t(h) = k and h and h′ agree in their first k coordinates, then t(h′) = k. A gambler with initial fortune x selects a strategy σ available at x and a stop rule t. The pair π = (σ, t) is a policy available at x. The expected reward to a gambler who selects the policy π is

u(π) = ∫ u(X_{t}) dσ,

where X_{0} = x. We will usually assume in this paper that u is nonnegative and we will always assume u(π) is well-defined and finite for all available π. The optimal reward function for this leavable problem is

U(x) = sup u(π),

where the supremum is taken over all policies π available at x.

It is also of interest to consider how well the gambler can do when playing time is restricted to at most n days, and we define U_{n}(x) = sup u(π) over all policies π = (σ, t) available at x such that t ≤ n for positive integers n and set U_{0} = u. The functions U_{n} can be calculated by backward induction as we will now explain. First define the operator S by

(Sϕ)(x) = sup{∫ ϕ dγ : γ ∈ Γ(x)}  (1.1)

for universally measurable functions ϕ on X such that ∫ ϕ dγ is well-defined for all available γ. Then

U_{n+1} = (SU_{n}) ∨ u ,  n = 0, 1, …,  (1.2)

where a ∨ b is the maximum of a and b. For ϕ upper analytic, Sϕ is also (Meyer and Traki (1973); see also Dubins and Sudderth (1979)). Thus every U_{n} is upper analytic. Furthermore,

U = lim U_{n}.  (1.3)

(See Section 2.15 of Dubins and Savage (1965) and also Maitra, Purves, and Sudderth (1990).) Hence, U is upper analytic as well.

If the gambling problem is nonleavable, then a gambler with initial fortune x selects a strategy σ available at x and receives the reward

u(σ) = lim sup_{t} ∫ u(X_{t}) dσ ,

where the lim sup is over the directed set of stop rules t. In many cases, for example when u is bounded or when the sequence u(X_{n}) is monotone increasing or decreasing,

u(σ) = ∫ {lim sup_{n} u(X_{n})} dσ.  (1.4)

(cf. Theorems 4.2.2 and 4.2.7 in Maitra and Sudderth (1996).) The optimal reward function for the nonleavable problem is

V (x) = sup{u(σ) : σ available at x}.

The function V can be calculated by a transfinite recursive scheme based on the operator T defined for lower bounded upper analytic functions u by

(T u)(x) = sup{∫ u(X_{t}) dσ : σ available at x, t ≥ 1}.

It turns out that T u = SU, where U is the optimal reward function for the leavable problem defined above (Maitra and Sudderth(1996, Theorem 4.8.12). Now let V_{0} = T u and , for each countable ordinal α > 0, let

V_{α} = \begin{cases}T (u ∧ V_{α−1}), & if α is a successor, \\ inf_{β<α} V_{β}, & if α is a limit ordinal. \end{cases}

(Here a ∧ b is the minimum of a and b.) Then

V = inf_{α} V_{α} ,

where the infimum is over all countable ordinals α, and V is also upper analytic (Dubins, Maitra, Purves,and Sudderth (1989), see also Maitra and Sudderth (1996)).

A gambling house Γ is said to be leavable if the point-mass δ(x) ∈ Γ(x) for every x ∈ X. If Γ is leavable, then U and V are the same (Corollary 3.2.2, Dubins and Savage (1965)).

1.3 Invariant Gambling Problems

Let (F, Γ, u) be a measurable gambling problem and suppose that G is a topological group or semigroup with identity that acts on the fortune space F. This means that there is a Borel mapping a : G × F → F, which we write a(g, x) = gx, such that ex = x for e the identity element of G and g_{1}(g_{2}x) = (g_{1}g_{2})x. For a group the mapping x → gx is necessarily one-to-one for every g ∈ G. We assume that these mappings are one-to-one in the case when G is only a semi-group. We also assume that G is a Polish space; that is, the topology on G is second countable and completely metrizable. The gambling problem will be called invariant (under G) if Conditions 1 and 2 below are satisfied.

To formulate the first condition, we associate to each probability measure γ ∈ ℙ(F) and each g ∈ G a measure gγ ∈ ℙ(F) defined by

∫ ϕ(x) (gγ)(dx) = ∫ ϕ(gx) γ(dx)

for bounded measurable functions ϕ on F. For a set Δ ⊆ ℙ(F) and g ∈ G, let

gΔ = {gγ : γ ∈ Δ}.

Condition 1 For all x ∈ F and g ∈ G, gΓ(x) = Γ(gx).

To state the second condition, let A be the group of positive, affine transformations of the real line. That is, A consists of all mappings r → ar + b for some a > 0 and b ∈ ℝ. Give A the topology it inherits when considered as a subset of the plane.

Condition 2 There is a Borel measurable mapping w : G → A such that u(gx) = w(g)(u(x)) for every x ∈ F and g ∈ G.

According to Savage’s theory of utility (see Theorems 5.3.2 and 5.3.3 in Savage (1954)), if u is a utility function, then ũ is also if and only if ũ is a positive affine transformation of u. Thus Condition 2 says that for every g ∈ G, the function u_{g}(x) = u(gx) is a utility function.

Lemma 1 If the function u is not constant, then w is a homomorphism from G into A.

Proof. For g_{1}, g_{2} ∈ G and x ∈ F, w(g_{1}g_{2})(u(x)) = u(g_{1}g_{2}x) = w(g_{1})(w(g_{2})(u(x))). Now use the fact that if two affine transformations agree on two points, then they agree everywhere.

As the case of a constant utility function u is uninteresting, we will assume from now on that w is a homomorphism.

Two notions of an invariant function will be used below. Let ψ be a function with domain F and suppose that G acts on the range of ψ. Then ψ will be called simply invariant if ψ(gx) = gψ(x) for all g ∈ G, x ∈ F. Thus Condition 1 says that the house Γ is invariant. To define the other notion, let w be the mapping given by Condition 2 and let ϕ be a mapping from F to the real numbers. Call ϕ w-invariant (under G) if ϕ(gx) = w(g)(ϕ(x)) for all x ∈ F and g ∈ G. So Condition 2 says that the utility function u is w-invariant.

Lemma 2 If ϕ is w-invariant and Sϕ is well-defined, then Sϕ is w-invariant also.

Proof. For x ∈ F and g ∈ G,

(Sϕ)(gx) = sup{∫ ϕ(x) γ(dx) : γ ∈ Γ(gx)}
= sup{∫ ϕ(x) (gγ)(dx) : γ ∈ Γ(x)}
= sup{∫ ϕ(gx) γ(dx) : γ ∈ Γ(x)}
= sup{∫ w(g)(ϕ(x)) γ(dx) : γ ∈ Γ(x)}
= w(g)(sup{∫ ϕ(x) γ(dx) : γ ∈ Γ(x)})
= w(g)(Sϕ(x)).

Corollary 3 The functions U_{n}, n ≥ 1, and U are w-invariant, as is the function V when u is bounded below.

Proof. It is easy to check that that suprema, infima, and pointwise limits of w-invariant functions are again w-invariant. Hence the corollary is a consequence of the lemma and the recursive schemes for calculating U_{n}, U, and V sketched in the previous section.

Example 1 Positive Dynamic Programming. Suppose that S is a nonempty Borel set, ℝ is the set of real numbers, and that F = S × ℝ. Thus a fortune x is a pair (s, c) whose first coordinate s is regarded as the state and whose second coordinate c as the cash accumulated up to the present time. The additive group G_{0} of real numbers acts on F thus

g(s, c) = (s, c + g) , g ∈ G_{0}.

Assume that Condition 1 holds. Then, in particular,

Γ(s, c) = cΓ(s, 0) , c ∈ ℝ.

Thus, if γ ∈ Γ(s, 0) and the random pair (s_{1}, r_{1}) has distribution γ, then cγ ∈ Γ(s, c) and (s_{1}, r_{1}+c) has distribution cγ. Let the utility function be u(s, c) = c. Condition 1 is immediate and, for each g, the affine transformation w(g) is translation by g.

Suppose that a gambler has initial fortune x = (s, 0). The gambler’s successive fortunes can be written as x_{1} = (s_{1}, r_{1}), x_{2} = (s_{2}, r_{1} + r_{2}), …, x_{n} = (s_{n}, r_{1} + r_{2} + ⋯ + r_{n}), …, and u(x_{n}) = r_{1} + r_{2} + ⋯ + r_{n}. The utility of a strategy σ is

u(σ) = lim sup_{t} ∫ (∑_{i=1}^{t} r_{i}) dσ.

Positive dynamic programming corresponds to the special case where, for every s ∈ S and γ ∈ Γ(s, 0), γ{(s_{1}, r_{1}) : r_{1} ≥ 0} = 1. In this case, the gambler’s fortune is almost sure to increase in utility at every stage and the utility of σ becomes

u(σ) = ∫ (∑_{i=1}^{∞} r_{i}) dσ.

It is natural in the case of positive dynamic programming to restrict the fortune space to be S ×[0, ∞) and to take G to be the semigroup of nonnegative real numbers under addition.

Negative dynamic programming can be formulated by analogy with Example 1. However, the situation is more complicated in the case of discounted dynamic programming and we are indebted to David Heath for the crucial idea in the formulation below.

Example 2 Discounted Dynamic Programming. Let 0 < β < 1 be the discount factor and let F = S×ℝ×ℕ, where S is a nonempty Borel set, ℝ the set of real numbers, and ℕ the set of nonnegative integers. A fortune x is now a triple (s, c, n), where the new coordinate n represents the number of days of play. A gamble γ ∈ Γ(x) determines the distribution of the next fortune x_{1} = (s_{1}, β^{−1}c+r, n+1) where s_{1} is the new state and r is the reward earned at the current stage of play. The utility function is u(x) = u(s, c, n) = β^{n}c.

To get the idea, consider an initial fortune x = (s, c, 0). The successive fortunes of a gambler can be written as x_{1} = (s_{1}, β^{−1}c + r, 1), …, x_{n} = (s_{n}, β^{−n}c + β^{−(n−1)}r_{1} + ⋯ + r_{n}, n), …. The utility of x_{n} is u(x_{n}) = c + βr_{1} + ⋯ + β^{n}r_{n}.

Suppose that the daily reward is bounded by a constant b in the sense that, for every s ∈ S and γ ∈ Γ(s, 0, 0), γ{(s_{1}, r_{1}, 1) : |r_{1}| ≤ b} = 1. Then the utility of a strategy σ available at (s, 0, 0) can be written

u(σ) = ∫ (∑_{i=1}^{∞} β^{i}r_{i})dσ.

The additive group of reals ℝ and the additive semigroup ℕ both act on F as follows:

g(s, c, n) = (s, c + β^{−n}g, n) , g ∈ ℝ
m(s, c, n) = (s, c, n + m) , m ∈ ℕ.

Condition 2 holds with w(g)(y) = y + g and w(m)(y) = β^{m}y. Condition 1 is assumed to hold for every g and m, or, equivalently, for the semigroup G of transformations on F that they generate.

Here is a simple class of examples on the real line.

Example 3 Proportional Houses. Let F = [0, ∞) and let G be the group of strictly positive real numbers under multiplication. The action of G on F is just the usual multiplication. Condition 1 now says that a gambler’s opportunities are proportional to the size of his fortune. In particular, Γ(x) = xΓ(1) for x ≥ 0. (A famous special case is the red-and-black casino where Γ(x) = {wδ(x + s) + (1 − w)δ(x − s) : 0 ≤ s ≤ x}.) A utility function that satisfies Condition 2 is u(x) = log x. Now u(gx) = log g + log x so that the affine function w(g) is translation by log g. By Corollary 2, the optimal n-day return is w-invariant and, hence, U_{n}(x) = U_{n}(x · 1) = w(x)(U_{n}(1)) = U_{n}(1) + log x. In fact, it is easy to show, by backward induction, that U_{n}(x) = nU_{1}(1) + log x. It therefore follows from (1.3) that either U(x) = log x or U(x) = ∞ according to whether U_{1}(1) = 0 or U_{1}(1) > 0.

1.4 Invariant Selectors

A Γ-selector is a function γ : F → ℙ(F) such that γ(x) ∈ Γ(x) for every x ∈ F. The von Neumann selection theorem guarantees the existence of a universally measurable Γ-selector γ. Such a selector determines a stationary family of strategies γ^{∞} which uses the gamble γ(x) whenever the current fortune is x. A selector γ is invariant if γ(gx) = gγ(x) for all x ∈ F, g ∈ G and, in this case, the corresponding stationary family is also called invariant. In the next section, we address the question of when invariant stationary families are adequate. This section is devoted to the preliminary problem of the construction of measurable, invariant selectors. For brevity, we often write “u.m.” for “universally measurable” below.

Assume first that G is a group. (We will consider the case of a semigroup at the end of the section.) Define R to be the equivalence relation

R = {(x, y) ∈ F × F : (∃g ∈ G)(gx = y)}.

The equivalence class of an x ∈ F is its orbit [x] = Gx. An orbit selector is a function ϕ : F → F such that (i) ϕ(x) ∈ [x] for every x, and (ii) ϕ(x) = ϕ(y) whenever xRy.

For the construction of a measurable, invariant Γ-selector, we will need a measurable orbit selector. The following condition guarantees its existence.

Condition 3 There is a sequence {E_{n}} of Borel subsets of F such that xRy ↔ (∀n)(x ∈ E_{n} ↔ y ∈ E_{n}).

The equivalence relation R is said to be smooth when Condition 3 holds.

Lemma 4 If R is smooth, then R admits a Borel measurable orbit selector.

Proof. By Theorem 5.2.1 in Becker and Kechris (1996), there is a Polish topology on F with the same Borel sets as the original topology and such that the action (g, x) → gx is continuous. So we can assume without loss of generality that the action is continuous. The existence of a Borel orbit selector then follows from results of Burgess (1979) or Srivastava (1998).

It can be shown that if R is Borel and admits even a universally measurable orbit selector, then R is smooth (Harrington et al, 1990). Thus Condition 3 is necessary as well as sufficient for the existence of a Borel orbit selector.

One additional condition is needed. For each x ∈ F, the stabilizer subgroup of x is defined to be G_{x} = {g ∈ G : gx = x}.

Condition 4 For every x ∈ F, the stabilizer subgroup G_{x} is either the singleton {e} or the whole group G.

Notice that this condition is satisfied by the proportional houses of Example 3. Indeed, for these houses, G_{0} = G and G_{x} = {1}, for x ≠ 0.

Lemma 5 Under Condition 4, there is a unique Borel function f : R → G such that, for all x, y ∈ F, (i)f(x, x) = e and (ii)f(x, y)x = y whenever y ∈ [x].

Proof. If G_{x} = {e} and y ∈ [x], then there is a unique g ∈ G such that gx = y and we take f(x, y) = g. If G_{x} = G, then [x] is a singleton and we take f(x, x) = e. Then f is Borel because its graph is

{(x, y, g) ∈ R × G : gx = y, x ≠ y} ∪ {(x, x, e) ∈ R × G : x ∈ F },

a Borel subset of R × G

Here is the basic lemma on the construction of invariant Γ-selectors.

Lemma 6 Suppose that G is a group and that Conditions 3 and 4 hold. Let η be a u.m. Γ-selector, ϕ be a Borel measurable orbit selector, and let f be the function of Lemma 4. Then the mapping γ : F → ℙ(F) defined by

γ(x) = f(ϕ(x), x)η(ϕ(x)) , x ∈ F

is a u.m. invariant Γ-selector. Conversely, every u.m. invariant Γ-selector satisfies this equality for some u.m. Γ-selector η.

Proof. For x ∈ F, and g ∈ G,

γ(gx) = f(ϕ(gx), gx)η(ϕ(gx))
= f(ϕ(x), gx)η(ϕ(x))
= gf(ϕ(x), x)η(ϕ(x))
= gγ(x).

This proves the first assertion.

Now suppose that γ is a u.m. invariant Γ-selector. Let ϕ be any Borel orbit selector and let η = γ. Then

γ(x) = γ(f(ϕ(x), x)ϕ(x)) = f(ϕ(x), x)γ(ϕ(x)) = f(ϕ(x), x)η(ϕ(x)).

Suppose now that G is a semigroup with identity, but not necessarily a group. Call a subset C of F closed under G if (i) x ∈ C and g ∈ G imply that gx ∈ C and (ii) g ∈ G and gx ∈ C imply that x ∈ C. The orbit [x] of x ∈ F is defined to be the smallest set closed under G and containing x. It is easy to check that

R = {(x, y) ∈ F × F : y ∈ [x]}

is an equivalence relation on F which is the same as the one previously defined when G is a group. We will not attempt here to develop a general theory for semigroups, but will instead limit ourselves to a special class of invariant problems which includes dynamic programming models and for which invariant selectors are readily available.

The semigroup G is called special if (i) there exists a Borel measurable orbit selector ϕ, (ii) for every x ∈ F and y ∈ [x], there is a g = f(x, y) such that f(x, y)ϕ(x) = y, and (iii) the function f : R → G is Borel measurable. Under Conditions 3 and 4, a group G is a special semigroup.

Lemma 7 If G is special and η is a u.m. Γ-selector, then

γ(x) = f(ϕ(x), x)η(ϕ(x)) , x ∈ F

is a u.m. invariant Γ-selector.

Proof. The proof is the same as for the first half of Lemma 5.

For dynamic programming models as in Example 1, the orbit of any fortune x = (s, c) is the set of all fortunes with the same first coordinate and we can take ϕ(x) = (s, 0). Then f(ϕ(x), x) = c and γ(x) = cη(ϕ(x)).

1.5 Invariant Stationary Families of Strategies

Each u.m. Γ-selector γ determines a stationary family of strategies σ̄(x) = γ^{∞}(x), x ∈ F, where for each x, σ̄(x) is the strategy given by

σ̄(x)_{0} = γ(x) ,  σ̄(x)_{n}(x_{1}, …, x_{n}) = γ(x_{n})

for all n ≥ 1 and all x, x_{1}, …, x_{n} ∈ F. The stationary family γ^{∞} is called invariant if the selector γ is invariant.

Dubins and Savage (1965) first posed the problem as to the existence of good stationary families. They obtained a positive result for F finite and Γ leavable which was extended to the countable case by Ornstein (1969). A number of authors (cf. Barbosa-Dantas (1966), Dellacherie and Meyer (1983), Dubins and Sudderth (1979), Frid (1976), Schäl and Sudderth (1987), and Sudderth (1969)) used the techniques of Ornstein to get results about good stationary families in Borel measurable settings. Perhaps all or most of these results can be extended to give results about good invariant stationary families for invariant problems. We present two such extensions in this section and mention some questions that remain open.

Assume that the gambling problem (F, Γ, u) is invariant under a special semi-group G. Assume also that Γ is leavable so that, in particular, the two optimal reward functions U and V are the same.

The assumption that Γ is leavable is necessary for the existence of good stationary families except in the case when F is finite and every set of gambles Γ(x), x ∈ F, is finite (Dubins and Savage (1965), see also Maitra and Sudderth (1996)). This assumption can be made without loss of generality for positive dynamic programming problems because, with positive daily rewards, a player gains nothing by terminating the game. This is not the case for negative dynamic programming problems where, as is well-known, good stationary plans need not exist even when the state space is finite (Strauch (1966)).

Recall that to each g ∈ G is associated an affine mapping w(g) which we can write as

w(g)(r) = a_{g}r + b_{g}, r ∈ ℝ,

for some a_{g} > 0, b_{g} ∈ ℝ. We say that the action of G is additive if a_{g} = 1 for every g ∈ G and we call the action multiplicative if b_{g} = 0 for every g ∈ G.

Here is an extension of Theorem 2.3 of Sudderth (1969) to the invariant case.

Theorem 8 Suppose that the function U −u is bounded and that the action of G is additive. Then, for each ϵ > 0 and probability measure α ∈ ℙ(F), there is a u.m. invariant Γ-selector γ such that

α{x ∈ F : u(γ^{∞}(x)) ≥ U(x) − ϵ } = 1.

Here is a similar extension of Proposition 7.1 of Dubins and Sudderth (1979).

Theorem 9 Assume u ≥ 0 and that the action of G is multiplicative. Then, given 0 < ϵ < 1, there is a u.m. invariant Γ-selector γ such that

α{x ∈ F : u(γ^{∞}(x)) ≥ (1 − ϵ)U(x)} = 1.

We will explain in the next section how the proof of Dubins and Sudderth (1979) can be modified for Theorem 9. A similar modification of the proof in Sudderth (1969) works for Theorem 8.

Theorem 8 implies the corresponding result of Barbosa-Dantas (1966) for positive dynamic programming problems with bounded optimal reward function. However, neither Theorem 8 nor Theorem 9 includes the result of Frid (1976) for positive dynamic programming problems with unbounded optimal reward function. (Theorem 9 does not apply because the action of the semi-group G in Example 1 is additive rather than multiplicative.) It would be interesting to have an extension of Frid’s result to a more general invariant setting.

Dubins and Savage (1965) showed that an optimal stationary family of strategies exists for any gambling problem with F finite and Γ(x) finite for all x. The analogous result holds for dynamic programming problems with finite state space and finite action sets. A common generalization would be that there is an optimal invariant stationary family for invariant gambling problems with a finite set of orbits and finite Γ(x) , x ∈ F. We do not know whether this is true.

1.6 The Proof of Theorem 9

For a proof of Theorem 9, we will show how to make the necessary changes in the arguments given for Proposition 7.1 in Dubins and Sudderth (1979). We will make reference to results in that paper by adding an asterisk. For example, Proposition 7.1^{∗} will denote Proposition 7.1 of Dubins and Sudderth (1979).

Throughout this section we fix a Borel measurable orbit selector ϕ as constructed in Section 4. Also, for γ ∈ ℙ(F), and ψ a γ-integrable function, we will often write γψ for the integral ∫ ψ dγ.

Lemma 10 (cf. Lemma 6.4^{∗}) For each ϵ > 0, there is a u.m. invariant Γ-selector γ such that

γ(x)u ≥ (1 − ϵ)U_{1}(x) for all x  (1.5)

and

γ(x) = δ(x) ⇒ u(x) = U_{1}(x).  (1.6)

Proof. By Lemma 6.4^{∗}, there is a u.m. Γ-selector η that satisfies (1.5) and (1.6), but η need not be invariant. So define

γ(x) = f(ϕ(x), x)η(ϕ(x))

as in Lemmas 6 and 7. Then γ is u.m. and invariant by those lemmas. To verify (1.5), let y = ϕ(x) and g = f(y, x) so that x = gy. Then

γ(x)u = γ(gy)u = (gγ(y))u = ∫ u(gz) γ(y)(dz) = w(g)(∫ u(z) γ(y)(dz))
≥ w(g)((1 − ϵ)U_{1}(y)) = (1−ϵ)w(g)(U_{1}(y)) = (1 − ϵ)U_{1}(gy) = (1 − ϵ)U_{1}(x).

The second equality is by the invariance of γ and the next to last is by the w-invariance of U_{1} as in Corollary 2.

For (1.6), suppose γ(x) = δ(x), where x = gy as above. Then

gδ(y) = δ(gy) = γ(gy) = gγ(y).

Hence, δ(y) = γ(y) because the mapping x → gx is one-to-one by assumption. But y = ϕ(x) and γ(y) = η(y). Now η satisfies condition (1.6). So we have u(y) = U_{1}(y) and

u(x) = w(g)(u(y)) = w(g)(U_{1}(y)) = U_{1}(x).

Define the set Y = ϕ(X). Then Y is Borel because Y = {x ∈ F : ϕ(x) = x}. Also Y intersects each orbit [x] in the singleton {ϕ(x)}.

Corollary 11 (cf. Corollary 6.1^{∗}) For each ϵ > 0 and α ∈ ℙ(F), there is an invariant Borel Γ-selector γ such that

γ(x)u ≥ (1 − ϵ)U_{1}(x)  (1.7)

for α-almost every x.

Proof. Use Lemma 10 to get an invariant u.m. Γ-selector γ̄ such that (1.5) holds when γ is replaced by γ̄. Define α′ to be the probability measure αϕ^{−1} so that, in particular, α′(Y) = α(ϕ^{−1}(Y)) = 1. Because γ̄ is u.m. and Γ is leavable, there is a Borel Γ-selector γ′ such that α′{y ∈ Y : γ′(y) = γ̄(y)} = 1. Define

γ(x) = f(ϕ(x), x)γ′(ϕ(x)), x ∈ F.

Then γ is Borel measurable because f, ϕ, and γ′ are. Also γ is an invariant Γ-selector by Lemma 6 or Lemma 7. Note that γ′(ϕ(x)) = γ̄(ϕ(x)) ⇒ γ(x) = γ̄(x) as γ̄ is invariant. Hence,

α({x ∈ F : γ(x) = γ̄(x)}) ≥ α({x ∈ F : γ′(ϕ(x)) = γ̄(ϕ(x))}
= α′({y ∈ Y : γ′(y) = γ̄(y)}
= 1.

Thus (1.7) holds for γ α-almost surely since it holds for γ̄.

The next result is that a gambler can get uniformly close (in the multiplicative sense ) to the optimal n-day return U_{n} using an invariant stationary family of strategies. The same is not true for the optimal reward function U even if the gambler uses a stationary family that is not invariant (Blackwell and Ramakrishnan, 1988).

Lemma 12 (cf. Proposition 6.1^{∗}) For n ≥ 1 and ϵ > 0, there is a u.m. invariant Γ-selector such that

u(γ^{∞}(x)) ≥ (1 − ϵ)U_{n}(x)

for all x ∈ F.

Proof. Choose β so that 0 < β < 1 and β^{n} > 1 − ϵ. By Lemma 10, we can find u.m. invariant Γ-selectors γ_{k}, k = 1, …, n such that

γ_{k}(x)U_{k−1} ≥ β^{1/2}U_{k}(x), x ∈ F.

Let k(x) be the least natural number k ≤ n such that

β^{k}U_{k}(x) = max_{0≤j≤n} β^{j}U_{j}(x).

Since the U_{k}’s are w-invariant and u.m., it follows that k(x) is u.m. and invariant. Consequently, γ defined by

γ(x) = \begin{cases}γ_{k(x)}(x), & k(x) = 1, …, n \\ δ(x), & k(x) = 0 \end{cases}

is a u.m. invariant Γ-selector. Proposition 5.1^{∗} now applies to yield the desired result.

To overcome certain measurability difficulties, Dubins and Sudderth found it useful to replace the original gambling problem in their paper by a simpler Borel problem. The next two lemmas enable us to do the same.

Lemma 13 Given u ≥ 0, u.m., and w-invariant, and α ∈ ℙ(F), there is a Borel w-invariant function v on F such that 0 ≤ v ≤ u and v = u α-almost surely.

Proof. As in the proof of Corollary 11, let α′ = αϕ^{−1} so that α′(Y) = 1. Choose a Borel function v′ : Y → [0, ∞) such that 0 ≤ v′ ≤ u on Y and α′({y ∈ Y : v′(y) = u(y)}) = 1. Recall from Section 4 that each x ∈ F can be written as x = f(ϕ(x), x)ϕ(x) for a unique group element f(ϕ(x), x) and set

v(x) = w(f(ϕ(x), x))(v′(ϕ(x)), x ∈ F.

Then v is Borel measurable because all of the functions appearing in its definition are Borel. To check that v is w-invariant, let x ∈ F, g ∈ G and calculate:

v(gx) = w(f(ϕ(gx), gx))(v′(ϕ(gx)))
= w(f(ϕ(x), gx))(v′(ϕ(x)))
= w(gf(ϕ(x), x))(v′(ϕ(x)))
= w(g)(w(f(ϕ(x), x))(v′(ϕ(x))))
= w(g)(v(x)).

Here the invariance of ϕ is used for the second equality and Lemma 1 for the next to last equality.

Next note that v′(ϕ(x)) = u(ϕ(x)) ⇒ v(x) = u(x), since u is w-invariant. Now α′({x ∈ F : v′(ϕ(x)) = u(ϕ(x))}) = 1. So it follows that v = u αalmost surely. Finally, v(x) = w(f(ϕ(x), x))(v′(ϕ(x)) ≤ w(f(ϕ(x), x))(u(ϕ(x))) = u(x).

A leavable house Γ′ is (Borel) countably parametrized if there exist Borel Markov kernels γ_{1}, γ_{2}, … such that Γ′(x) = {γ_{1}(x), γ_{2}(x), … } for every x ∈ F. The house Γ′ is clearly invariant if each of the functions γ_{k} is invariant.

Lemma 14 (cf. Lemma 7.1^{∗}) For each α ∈ ℙ(F), there is an invariant, countably parametrized subhouse Γ′ of Γ and a nonnegative Borel function u′ on F such that

(i) u′ ≤ u on F, and

(ii) U′ ≥ U α-almost surely,

where U′ is the optimal reward function for (F, Γ′, u′).

Proof. Repeat the proof of Lemma 7.1^{∗} using Corollary 11 instead of Corollary 6.1^{∗} so that the Γ-selectors γ_{k} turn out to be both invariant and Borel measurable. To get the function u′, use Lemma 13.

In view of Lemma 14 it now suffices to prove Theorem 9 under the additional assumptions that Γ is countably parametrized and u is Borel. These assumptions will be in force for the remainder of the proof.

Lemma 15 (cf. Lemma 7.2^{∗}) The functions U_{1}, U_{2}, …, U are Borel measurable. For each ϵ > 0 and n ≥ 1, there is an invariant, Borel Γ-selector γ such that u(γ^{∞}(·)) is w-invariant, Borel measurable, and

u(γ^{∞}(x)) ≥ (1 − ϵ/2)U_{n}(x) for all x.  (1.8)

Hence, for each α ∈ ℙ(F), there exists such a Borel Γ-selector γ for which

u(γ^{∞}(x)) ≥ (1 − ϵ)U(x)  (1.9)

with α-probability at least 1 − ϵ.

Proof. The first assertion is easy to prove because Γ is countably parametrized (see Theorem 4.1 of Sudderth (1969)). Next choose β ∈ (0, 1) such that β^{n} > 1 − ϵ/2. Then the Γ-selector γ given by Lemma 12 is invariant and satisfies (1.8). Also, because the functions U_{1}, U_{2}, … are Borel, it is clear from the construction in the proof of Lemma 12 that γ is Borel. The function u(γ^{∞}(·)) is the V for the invariant house Γ′ where Γ′(x) = {γ(x)}, x ∈ F. Thus u(γ^{∞}(·)) is w-invariant by Corollary 3. It is not clear that the function u(γ^{∞}(·)) is Borel, but the argument for Lemma 7.2^{∗} shows that γ can be chosen so that this is true. Since U_{n} ↑ U, the final assertion follows from (1.8).

Consider now a leavable, Borel, stop-or-go house Σ, which means that, for some Borel Markov kernel η and all x, Σ(x) = {η(x), δ(x)}. Assume also that η is invariant and let W be the optimal reward function for the invariant problem (F, Σ, u).

Lemma 16 The stationary family γ^{∞}, where

γ(x) = \begin{cases}η(x), u(x) < W (x) \\ δ(x), u(x) = W (x), \end{cases}

is Borel measurable, invariant, and optimal for (F, Σ, u).

Proof. The house Σ is Borel and countably parametrized. Hence, W is Borel by Lemma 15 and w-invariant by Corollary 3. It follows that γ is Borel and invariant. The optimality of γ^{∞} is a consequence of Proposition 4.1^{∗}.

The idea of the remainder of the proof, based on ideas of Ornstein (1969), is to find a Borel invariant stop-or-go subhouse of the original Γ whose optimal reward function is almost surely as large as (1 − ϵ)U. Theorem 9 will then follow from Lemma 16.

The construction of the stop-or-go house is in a countable number of steps and each step will use the following operation.

To each stop-or-go house Σ, associate the house Γ · Σ defined by

(Γ · Σ)(x) = \begin{cases}Σ(x), if Σ(x) contains two elements \\ Γ(x), otherwise. \end{cases}

Plainly, Σ ⊆ Γ ⇒ Σ ⊆ Γ · Σ ⊆ Γ and Σ ⊆ Σ′ ⇒ Γ · Σ′ ⊆ Γ · Σ.

If η is Borel measurable and Σ(x) = {η(x), δ(x)} for all x, then Σ is Borel and countably parametrized, as is Γ·Σ. So, by Lemma 15, the optimal return function W for Σ is Borel measurable, as is the optimal return function R for Γ · Σ.

Lemma 17 (cf. Lemma 7.5^{∗}) Suppose Σ is a leavable, invariant, Borel, stop-or-go subhouse of Γ, α ∈ ℙ(F), and ϵ > 0. Then there is a leavable, invariant, Borel, stop-or-go house Σ′ such that

(i) Σ ⊆ Σ′ ⊆ Γ,
(ii) α[W′ ≥ (1 − ϵ)R] ≥ 1 − ϵ, and
(iii) R′ ≥ (1 − ϵ)R,

where W′ and R′ are the optimal return functions for Σ′ and Γ · Σ′, respectively.

Proof. The house Γ · Σ is invariant, and hence, by Lemma 15, there is an invariant, Borel Γ · Σ-selector γ such that u(γ^{∞}(·)) is Borel, w-invariant, and α(S) > 1 − ϵ, where S = {x : u(γ^{∞}(x)) ≥ (1 − ϵ^{2}/2)R(x)}. Set T = {x : u(γ^{∞}(x)) ≥ (1 − ϵ)R(x)}. Then the set T is Borel and, because the functions u and R are w-invariant and the action of G is multiplicative, T also has the property that x ∈ T ⇔ gx ∈ T for all x ∈ F, g ∈ G. Now define the house Σ′ by

Σ′(x) = \begin{cases}\{η(x), δ(x)\}, if x ∈ T and Σ(x) = \{δ(x)\}, \\ Σ(x), if Σ(x) contains two elements, \\ \{δ(x)\}, otherwise. \end{cases}

The proof that Σ′ has the desired properties, with the exception of invariance, is exactly the same as in the proof of Lemma 7.5^{∗}. The proof that Σ′ is invariant is straightforward if one uses the property of T mentionned above and our standing assumption that the mappings x → gx are one-to-one.

The assumption that G acts multiplicatively was used in the proof above for Lemma 17, but is used nowhere else in the proof of Theorem 9.

Lemma 18 (cf. Lemma 7.6^{∗}) Let α ∈ ℙ(F) and ϵ > 0. There is a sequence Σ_{0} ⊆ Σ_{1} ⊆ ⋯ of leavable, invariant, Borel stop-or-go subhouses of Γ whose optimal return functions W_{0}, W_{1}, … satisfy

α[W_{n} ≥ (1 − ϵ)U] ↑ 1.

Proof. The proof is the same as that of Lemma 7.6^{∗} except that Lemma 17 is used instead of Lemma 7.5^{∗}.

Define the house Σ by setting

Σ(x) = ∪_{n}Σ_{n}(x), x ∈ F,

where the Σ_{n} are from Lemma 18. Then Σ is a leavable, invariant, stop-or-go subhouse of Γ whose optimal return function W satisfies α[W ≥ (1 − ϵ)U] = 1. Theorem 9 now follows from Lemma 16.

1.7 Acknowledgement

The research of Sudderth was partially supported by National Science Foundation Grant DMS 97-03285.

Bibliography

Barbosa-Dantas [1] C.A. Barbosa-Dantas, The Existence of Stationary Optimal Plans, Ph.D. Dissertation, University of California, Berkeley, 1966.

Becker [2] H. Becker and A.S. Kechris, The Descriptive Set Theory of Polish Group Actions, LMS Lecture Notes, Cambridge University Press, 1996.

Blackwell [3] D. Blackwell, “ The stochastic processes of Borel gambling and dynamic programming,” Annals of Statistics 4, 370-374, 1976.

B-R [4] D. Blackwell and S. Ramakrishnan, “Stationary plans need not be uniformly optimal for leavable, Borel gambling problems,” Proceedings of the American Mathematical Society 102, 1024-1027, 1988.

Burgess [5] J.P. Burgess, “A selection theorem for group actions,” Pacific Journal of Mathematics 80, 333-336, 1979.

Dellacherie [6] C. Dellacherie and P.A. Meyer, Probabilités et Potentiel, Chapitres IX à XI, Hermann, Paris, 1983.

DMPS [7] L. Dubins, A. Maitra, R. Purves, and W. Sudderth, “Measurable, nonleavable gambling problems,” Israel Journal of Mathematics 67, 257-271, 1989.

DubinsSavage [8] L.E. Dubins and L.J. Savage, How to Gamble If You Must: Inequalities for Stochastic Processes, McGraw, New York, 1965.

DubinsSud [9] L.E. Dubins and W.D. Sudderth, “On stationary strategies for absolutely continuous houses,” Annals of Probability 7, 461-476, 1979.

Eaton [10] M. Eaton, Invariance Applications in Statistics, Regional Conference Series in Probability and Statistics I, Institute of Mathematical Statistics, Hayward, California, 1989.

Frid [11] E.B. Frid, “On a problem of D. Blackwell from the theory of dynamic programming,” Theory of Probability and Applications 15, 719-722, 1976.

Harrington [12] L. Harrington, A.S. Kechris, and A. Louveau, “A Glimm-Effros dichotomy for Borel equivalence relations,” Journal of the American Mathematical Society 3 903-928, 1990.

MPS [13] A. Maitra, R. Purves, and W. Sudderth, “Leavable gambling problems with unbounded utilities,” Transactions of the American Mathematical Society 333, 543-567, 1990.

MS [14] A. Maitra and W. Sudderth, Discrete Gambling and Stochastic Games, Springer-Verlag, New York, 1996.

Meyer [15] P.A. Meyer and M. Traki, “Réduites et jeux de hasard,” Séminaire de Probabilité XII, Lecture Notes in Mathematics 321, Springer-Verlag, Berlin, 155-171, 1973.

Ornstein [16] D. Ornstein, “On the existence of stationary optimal strategies,” Proceedings of the American Mathematical Society 20, 563-569, 1969.

Savage [17] L.J. Savage, The Foundations of Statistics, Wiley, New York, 1954.

SS [18] M. Schäl and W. Sudderth, “Stationary policies and Markov policies in Borel dynamic programming,” Probability Theory and Related Fields 74, 91-111, 1987.

Srivastava [19] S.M. Srivastava, A Course on Borel Sets, Springer-Verlag, Berlin, 1998.

Strauch [20] R.E. Strauch, “Negative dynamic programming,” Annals of Mathematical Statistics 37, 871-890, 1966.

Strauch2 [21] R.E. Strauch, “Measurable gambling houses,” Transactions of the American Mathematical Society 126, 64-72, 1967.

Sud [22] W.D. Sudderth, “On the existence of good stationary strategies,” Transactions of the American Mathematical Society 135, 399-414, 1969.