Fuzzy Decision Processes with an Average Reward Criterion

Masami KURANO^{†}, Masami YASUDA^{‡}, Jun-ichi NAKAGAMI^{‡}

and Yuji YOSHIDA^{§}

†Faculty of Education, ^{‡}Faculty of Science, Chiba University, Chiba 263-8522, Japan. ^{§}Faculty of Economics and Business Administration, Kitakyushu University, Kitakyushu 802-8577, Japan.

Abstract

As the same framework of Fuzzy decision processes with the discounted case we will specify an average fuzzy criterion model and develop its optimization by “fuzzy max order” under appropriate conditions. The average reward is characterized, by introducing a relative value function, as a unique solution of the associated equation. Also we derive the optimality equation using the “vanishing discount factor” approach.

Keywords: Fuzzy sets; Dynamic programming; Decision theory; Average reward criterion; Relative value function; Optimality equation.

1 Introduction and notations

In the previous paper [6], Markov-type fuzzy decision processes (FDP’s, for short) with a bounded fuzzy reward are defined. We have developed its optimization under the discount reward criterion. Also, the long-run average reward of some dynamic fuzzy system has been specified in our another paper [7]. However, the optimization was not considered there. In this paper, we will specify the long-run average fuzzy reward from a fuzzy policy and develop its optimization by the so-called “fuzzy max order” on the convex fuzzy numbers under the ergodicity (contraction) condition for the fuzzy state transition and the continuity condition for the fuzzy reward relation.

By introducing the relative value functions, the average reward from any admissible stationary policy is characterized as a unique solution of the associated equation. It will be useful in the policy improvement. Moreover, using the “vanishing discount factor” approach which is well-known in the theory of Markov decision processes (for example, see [12, 14]), we derive the optimality equation under the average fuzzy reward criterion. In the reminder of this section, we will give notations and some mathematical facts.

Let E, E_{1}, E_{2} be convex compact subsets of a given Banach space. Throughout the paper we will denote a fuzzy set and a fuzzy relation by their membership functions. For the theory of fuzzy sets, refer to Zadeh [20] and Novàk [11].

A fuzzy set ũ : E → [0, 1] on E is called convex if

ũ(λx + (1 − λ)y) ≥ ũ(x) ∧ ũ(y), x, y ∈ E, λ ∈ [0, 1],

where a ∧ b := min{a, b} (c.f. [15, 16]). Also, a fuzzy relation h̃ : E_{1} × E_{2} → [0, 1] between E_{1} and E_{2} is called convex if

h̃(λx_{1} + (1 − λ)x_{2}, λy_{1} + (1 − λ)y_{2}) ≥ h̃(x_{1}, y_{1}) ∧ h̃(x_{2}, y_{2})

for x_{1}, x_{2} ∈ E_{1}, y_{1}, y_{2} ∈ E_{2} and λ ∈ [0, 1].

The α-cut (α ∈ [0, 1]) of the fuzzy set ũ is defined by

ũ_{α} := {x ∈ E | ũ(x) ≥ α} (α > 0) and ũ_{0} := cl {x ∈ E | ũ(x) > 0},

where cl denotes the closure of a set.

Let F(E) be the set of all convex fuzzy sets, ũ, on E whose membership functions are upper semi-continuous and have compact supports and the normality condition : sup_{x∈E} ũ(x) = 1. We denote by C(E) the collection of all

compact convex subsets of E and ρ_{E} the Hausdorff metric on C(E). Clearly, ũ ∈ F(E) means ũ_{α} ∈ C(E) for all α ∈ [0, 1].

Let R be the set of real numbers. We see from the definition that C(R) and F(R) are the set of all bounded closed intervals in R and all upper semi-continuous and convex fuzzy numbers on R with compact supports, respectively.

For the interval [0, M] with a fixed positive number M,

F([0, M]) = {ũ ∈ F(R) | ũ_{0} ⊂ [0, M]},

and C([0, M]) be the set of all closed convex subsets of [0, M]. For non-empty closed intervals, the Hausdorff metric on C([0, M]) is represented by δ, i.e.,

δ([a, b], [c, d]) :=| a − c | ∨ | b − d | for [a, b], [c, d] ∈ C([0, M]),

where a ∨ b = max{a, b} for real numbers a, b.

The definitions of addition and scalar multiplication on F(R) are as follows: For m̃, ñ ∈ F(R) and λ ≥ 0,

(m̃ + ñ)(x) := sup_{x_{1},x_{2}∈R: x_{1}+x_{2}=x}{m̃(x_{1}) ∧ ñ(x_{2})}

and, for the scalar multiplication, let us define

(λm̂)(x) := \{ \begin{matrix}m̂(x/λ) & if λ > 0 \\ I_{\{0\}}(x) & if λ = 0, \end{matrix} (x ∈ R)

where I_{{·}}(·) is an indicator. By using the set operation A + B := {x + y | x ∈ A, y ∈ B}, A + ∅ = A for any non-empty sets A, B ⊂ R, and λA := {λx | x ∈ A} for A ⊂ R, the following holds immediately.

(m̃ + ñ)_{α} = m̃_{α} + ñ_{α} and (λm̃)_{α} = λm̃_{α} (α ∈ [0, 1])

Lemma 1.1 ([15, Theorem 2.3]).

(i) For any ñ, m̃ ∈ F(R) and λ ∈ R, ñ + m̃ ∈ F(R) and λñ ∈ F(R).

(ii) For any s̃ ∈ F(E_{1}) and p̃ ∈ F(E_{1} × E_{2}), then sup_{x∈E_{1}} s̃(x) ∧ p̃(x, ·) ∈ F(E_{2}).

In the next section 2, we give the basic definition of FDP’s and describe the optimization problem by specifying the average fuzzy reward from any fuzzy policy. In Section 3, referring [6] we give several results for the discounted case which will be also used to derive the optimality equation by the “vanishing discount factor” method in Section 5. In Section 4, the average fuzzy reward from any stationary fuzzy policy satisfying some reasonable condition is characterized as a unique solution of the associated relational equation. The numerical example is given to illustrate the theoretical results.

2 Fuzzy Decision Processes

In this section, we will formulate FDP’s. By introducing the fuzzy max order on the convex fuzzy numbers the optimization problem could be described.

A fuzzy decision process, in this paper, is a controlled dynamic fuzzy system defined by four objects (S, A, q̃, r̃) as follows:

(i) Let S and A be a state space and an action space, which are given as convex compact subsets of some Banach space respectively. The decision process is assumed to be fuzzy itself, so that both the state of the system and the action taken at each stage are denoted by the element of F(S) and F(A), called the fuzzy state and the fuzzy action respectively.

(ii) The law of motion for the system and the fuzzy reward can be characterized by time invariant fuzzy relations q̃ ∈ F(S × A × S) and r̃ ∈ F(S × A × [0, M]), where M is a given positive number. Explicitly, if the system is in a fuzzy state s̃ ∈ F(S) and the fuzzy action ã ∈ F(A) is chosen, then it transfers to a new fuzzy state Q(s̃, ã) and a fuzzy reward R(s̃, ã) is earned, where Q, R are defined by the following:

Q(s̃, ã)(y) := sup_{(x,a)∈S×A} s̃(x) ∧ ã(a) ∧ q̃(x, a, y) (y ∈ S)  (2.1)

and

R(s̃, ã)(u) := sup_{(x,a)∈S×A} s̃(x) ∧ ã(a) ∧ r̃(x, a, u) (0 ≤ u ≤ M). (2.2)

Note that, by Lemma 1.1, it holds that Q(s̃, ã)(·) ∈ F(S) and R(s̃, ã)(·) ∈ F([0, M]) for all s̃ ∈ F(S), ã ∈ F(A).

Firstly we will define a policy based on the fuzzy state and fuzzy action as follows. Let Π := {π|π : F(S) ↦ F(A)} be the set of all maps from F(S) to F(A). Any element π ∈ Π is called a strategy. A policy, π̌ = (π_{1}, π_{2}, π_{3}, ⋯), is a sequence of strategies such that π_{t} ∈ Π for each t. Especially, the policy (π, π, π, ⋯) is a stationary policy and is denoted by π^{∞}.

A fuzzy strategy π ∈ Π is called admissible if the α-cut π(s̃)_{α} of π depends only on the scalar α and the sets s̃_{α}, that is, it would be written as

π(s̃)_{α} = π(α, s̃_{α}) for s̃ ∈ F(S).  (2.3)

For the admissible fuzzy strategy π = {π(·, ·)}, if π(α, D) is continuous in (α, D) ∈ [0, 1] × C(S), π is called continuous. We denote by Π_{A} and Π_{C}, respectively, the collections of all admissible and continuous fuzzy strategies. A policy π̌ = (π_{1}, π_{2}, ⋯) is called admissible (continuous resp.) if π_{t} ∈ Π_{A} (Π_{C}) for all t ≥ 0. To specify a performance index (or an objective function) and describe an optimal decision problem, let us consider the convergence of a sequence of fuzzy numbers and a partial order.

Definition 2.1 (c.f. [5, 10]). For ũ_{t}, ũ ∈ F(E),

lim_{t→∞} ũ_{t} = ũ

iff lim_{t→∞} sup_{α∈[0,1]} ρ(ũ_{t,α}, ũ_{α}) = 0, where ũ_{t,α} and ũ_{α} are respectively the α-cut of ũ_{t} and ũ.

For any closed interval D ∈ C([0, M]), we put D = [\underline{D}, \overline{D}], where \underline{D} and \overline{D} are the left and right end points of D respectively.

The partial order ⪯ on C([0, M]) is defined as follows : For any D_{1}, D_{2} ∈ C([0, M]). D_{1} ⪰ D_{2} means that \overline{D_{1}} ≥ \overline{D_{2}} and \underline{D_{1}} ≥ \underline{D_{2}}. Then, (C([0, M]), ⪰) becomes a complete lattice (see [2]) and the following lemma holds obviously.

Lemma 2.1. For any sequence {D_{n}}_{n=1}^{∞} ⊂ C([0, M]), it holds that

(i) sup_{n≥1} D_{n} = [sup_{n≥1} \underline{D_{n}}, sup_{n≥1} \overline{D_{n}}], and

(ii) if ∑_{n≥1}^{∞} D_{n} converges, ∑_{n≥1}^{∞} D_{n} = [∑_{n≥1}^{∞} \underline{D_{n}}, ∑_{n≥1}^{∞} \overline{D_{n}}].

Using the order on C([0, M]), let us define the partial order ⪰ on F([0, M]) which is called a max fuzzy order.

Definition 2.2. For any ñ, m̃ ∈ F([0, M]), ñ ⪰ m̃ iff ñ_{α} ⪰ m̃_{α} for all α ∈ [0, 1].

For any admissible policy π̌ = (π_{1}, π_{2}, ⋯) and an initial fuzzy state s̃ ∈ F(S), we can define a sequence of fuzzy rewards on [0, M],

{R(s̃_{t}, π_{t}(s̃_{t}))}_{t=1}^{∞},

where

s̃_{1} = s̃ and s̃_{t+1} = Q(s̃_{t}, π_{t}(s̃_{t})) for t ≥ 1.  (2.4)

Here we are concerned with two performance criteria. The first one is the total discounted fuzzy reward with a discount factor β (0 < β < 1);

ψ_{β}(π̌, s̃) := ∑_{t=1}^{∞} β^{t−1}R(s̃_{t}, π_{t}(s̃_{t})) ∈ F([0, M/(1 − β)])  (2.5)

for s̃ ∈ F(S) and π̌ = (π_{1}, π_{2}, ⋯).

The problem in the discounted case is to maximize ψ_{β}(π̌, s̃) over all admissible policy π̌ with respect to the order ⪰ on F([0, M]), which has been investigated in [6]. The second performance criteria is the long-run average fuzzy reward per unit time, which is formally defined by

Ψ(s̃, π̌) := lim_{T →∞} \frac{R_{T}}{T} ,  (2.6)

where

R_{T} := ∑_{t=1}^{T} R(s̃_{t}, π_{t}(s̃_{t})) (T ≥ 1).  (2.7)

Our problem in this paper is to show the convergence property of Ψ(s̃, π̌) and maximize Ψ(s̃, π̌) over some class of continuous policies π̌ with respect to the order ⪰ on F([0, M]), which is given in Sections 4 and 5.

3 Assumptions and preliminary results

In this section, we introduce some assumptions for the fuzzy relation q̃ and fuzzy reward r̃. And several preliminary results are given for the discounted case, which guarantee the validity of the “vanishing discount factor” approach. In order to discuss the structure of the fuzzy state transition and fuzzy reward, let us introduce some notations.

A map Q_{α} : C(S) × C(A) ↦ C(S) (α ∈ [0, 1]) is defined by

Q_{α}(D×B) := \{ \begin{matrix}\{y ∈ S | q̃(x, a, y) ≥ α for some (x, a) ∈ D × B\}, & α > 0, \\ cl\{y ∈ S | q̃(x, a, y) > 0 for some (x, a) ∈ D × B\}, & α = 0, \end{matrix}

and a map R_{α} : C(S) × C(A) ↦ C([0, M]) (α ∈ [0, 1]) by

R_{α}(D×B) := \{ \begin{matrix}\{u ∈ R_{+} | r̃(x, a, u) ≥ α for some (x, a) ∈ D × B\}, & α > 0, \\ cl\{u ∈ R_{+} | r̃(x, a, u) > 0 for some (x, a) ∈ D × B\}, & α = 0. \end{matrix}

Since R_{α}(D × B) is a closed interval for each α ∈ [0, 1], we can write it as

R_{α}(D × B) := [\underline{R}_{α}(D × B), \overline{R}_{α}(D × B)].

In this paper, we need the following two assumptions.

Assumption A (Ergodicity or contraction). There exits γ_{1} (0 < γ_{1} < 1) such that

ρ(Q_{α}(D × B), Q_{α}(D′ × B)) ≤ γ_{1}ρ(D, D′) for all B ∈ C(A).

Assumption B (Lipschitz condition). There exists a constant C such that

|\underline{R}_{α}(D × B) − \underline{R}_{α}(D′ × B)| ∨ |\overline{R}_{α}(D × B) − \overline{R}_{α}(D′ × B)| ≤ Cρ(D, D′)

for any D, D′ ∈ C(S) and B ∈ C(A).

We note that Assumption A has been given in [5, 17], under which several limit theorems for the sequence of fuzzy states have bee obtained.

We now derive the optimality equation for the discounted case. Let

V := {v : C(S) ↦ C([0, M])}.

Define a metric d_{V} on V by

d_{V} (v, w) := sup_{D∈C(S)} δ(v(D), w(D)) for v, w ∈ V.

Then, (V, d_{V}) becomes a complete metric space. Define a map U_{α}^{β} : V ↦ V (α ≥ 0) by

U_{α}^{β}v(D) := sup_{B∈C(A)}{R_{α}(D × B) + βv(Q_{α}(D × B))}  (3.1)

for v ∈ V and D ∈ C(S), where β is a discount factor and 0 < β < 1.

If we write v(D) and U_{α}^{β}v(D) respectively by v(D) = [\underline{v}(D), \overline{v}(D)] and U_{α}^{β}v(D) = [\underline{U}_{α}^{β}v(D), \overline{U}_{α}^{β}v(D)], (3.1) becomes, from Lemma 2.1,

\underline{U}_{α}^{β}v(D) = sup_{B∈C(A)}\{\underline{R}_{α}(D × B) + β\underline{v}(Q_{α}(D × B))\},  (3.2)
\overline{U}_{α}^{β}v(D) = sup_{B∈C(A)}\{\overline{R}_{α}(D × B) + β\overline{v}(Q_{α}(D × B))\}.  (3.3)

In [6], it is shown that the operator U_{α}^{β} is a contraction with modulus β. Thus, there exists a unique map v_{α,β} ∈ V such that

v_{α,β} = U_{α}^{β}v_{α,β}.  (3.4)

Let v_{α,β}(D) := [\underline{v}_{α,β}(D), \overline{v}_{α,β}(D)] for all D ∈ C(S). The property of v_{α,β} is given in the following lemma.

Lemma 3.1. Suppose that Assumptions A and B hold. Then, we have

|\underline{v}_{α,β}(D) − \underline{v}_{α,β}(D′)| ∨ |\overline{v}_{α,β}(D) − \overline{v}_{α,β}(D′)| ≤ \frac{C}{1 − βγ_{1}} ρ(D, D′)  (3.5)

for all D, D′ ∈ C(S).

Proof. Putting \underline{v}_{α,β}^{0} ≡ \{0\} ∈ V, we define the iterates \underline{v}_{α,β}^{t} by

\underline{v}_{α,β}^{t+1} = \underline{U}_{α}^{β}\underline{v}_{α,β}^{t}, (t ≥ 0)  (3.6)

Then, by the contractive property of \underline{U}_{α}^{β}, \underline{v}_{α,β}^{t}(D) → \underline{v}_{α,β}(D) uniformly for D ∈ C(S) as n → ∞. Now, we show by induction on t that

|\underline{v}_{α,β}^{t}(D) − \underline{v}_{α,β}^{t}(D′)| ≤ C ∑_{l=0}^{t−1}(βγ_{1})^{l}ρ(D, D′)  (3.7)

for all D, D′ ∈ C(S) and t ≥ 1. It holds, from Assumption B, that

|\underline{v}_{α,β}^{1}(D) − \underline{v}_{α,β}^{1}(D′)| ≤ sup_{B∈C(A)} |\underline{R}_{α}(D × B) − \underline{R}_{α}(D′ × B)| ≤ Cρ(D, D′),

which implies that (3.7) holds for t = 1. Suppose that (3.7) holds for t. Then, we have

|\underline{v}_{α,β}^{t+1}(D) − \underline{v}_{α,β}^{t+1}(D′)|

≤ sup_{B∈C(A)} |\underline{R}_{α}(D × B) − \underline{R}_{α}(D′ × B)|
+ β sup_{B∈C(A)} |\underline{v}_{α,β}^{t}(Q_{α}(D × B)) − \underline{v}_{α,β}^{t}(Q_{α}(D′ × B))|
≤ Cρ(D, D′) + β ∑_{l=0}^{t−1}(γ_{1}β)^{l} sup_{B∈C(A)} ρ(Q_{α}(D × B), Q_{α}(D′ × B))

, from Assumption B and the hypothesis of induction

≤ ∑_{l=0}^{t}(γ_{1}β)^{l}ρ(D, D′)

, from Assumption A.

This shows that (3.6) holds for t + 1. Letting t → ∞ in (3.7), we get

|\underline{v}_{α,β}(D) − \underline{v}_{α,β}(D′)| ≤ \frac{C}{1 − βγ_{1}} ρ(D, D′).  (3.8)

Similarly as the case of \underline{v}_{α,β}, we obtain that

|\overline{v}_{α,β}(D) − \overline{v}_{α,β}(D′)| ≤ \frac{C}{1 − βγ_{1}} ρ(D, D′).  (3.9)

These inequalities (3.8) and (3.9) implies (3.5). □

4 Characterization of the average fuzzy reward

This section concerns the convergence and characterization of the average fuzzy reward Ψ(s̃, π^{∞}), which formally given in (2.6).

Let π ∈ Π_{C}. For simplicity, we put

R_{T} (s̃, π^{∞}) := ∑_{t=1}^{T} R(s̃_{t}, π(s̃_{t})),  (4.1)

where

s̃_{1} := s̃ and s̃_{t+1} = Q(s̃_{t}, π(s̃_{t})) (t ≥ 1)

By using q̃ and r̃, we define maps Q_{α}^{π} : C(S) ↦ C(S) and R_{α}^{π} : C(S) ↦ C([0, M]) (π ∈ Π_{A}, α ∈ [0, 1]) by

\begin{aligned}Q_{α}^{π}(D) & := Q_{α}(D × π(α, D)) \\ R_{α}^{π}(D) & := R_{α}(D × π(α, D)) \end{aligned}

for D ∈ C(S). For any admissible fuzzy policy π ∈ Π_{A}, Q_{t,α}^{π} (t ≥ 1) is defined inductively by using the composition of maps as follows :

Q_{1,α}^{π}(D) := Q_{α}^{π}(D)

and

Q_{t+1,α}^{π}(D) := Q_{t,α}^{π}Q_{α}^{π}(D)

for t ≥ 1 and D ∈ C(S).

The following lemma can be proved analogously to those of [7, Lemma 2.1].

Lemma 4.1. Let π ∈ Π_{C}. Then :

(i) s̃_{t+1,α} = Q_{t,α}^{π}(s̃_{α}) for t ≥ 1,

(ii) R_{T} (s̃, π^{∞}) ∈ F([0, T M]) for T ≥ 1,

(iii) (R_{T} (s̃, π^{∞}))_{α} = ∑_{t=1}^{T} R_{α}(s̃_{t,α}, π(α, s̃_{t,α})) for T ≥ 1.

In order to insure the ergodicity of the process and the uniform continuity of the fuzzy reward, we introduce the condition L(π) depending on π ∈ Π_{C}.

For any continuous strategy π ∈ Π_{C}, we shall say that L(π) holds if there exist constant γ (0 < γ < 1), C > 0 and a positive integer t_{0} satisfying the following (i) and (ii) :

(i) ρ(Q_{t_{0},α}^{π}(D), Q_{t_{0},α}^{π}(D′)) ≤ γρ(D, D′),

(ii) δ(R_{α}^{π}(D), R_{α}^{π}(D′)) ≤ Cρ(D, D′).

Note that the conditions (i) and (ii) are corresponding to Assumption A and B in Section 3 respectively.

Let us denote by Π_{SC}^{∗} the set of all continuous strategies π ∈ Π_{C} satisfying the above condition L(π). The convergence of Ψ(s̃, π^{∞}) is given in the following theorem. The proof is analogous to those of [7].

Theorem 4.1. For any π ∈ Π_{SC}^{∗}, Ψ(s̃, π^{∞}) in (2.6) converges and satisfies the following :

Ψ(s̃, π^{∞}) = R(p̃^{π}, π(p̃^{π})),

where p̃^{π} ∈ F(S) is a limiting fuzzy state satisfying that

(i) lim_{t→∞} s̃_{t} = p̃^{π}, and Q_{α}^{π}(p̃_{α}^{π}) = p̃_{α}^{π} for all α ∈ [0, 1],

(ii) p̃^{π} is independent of the initial fuzzy state s̃, and

(iii) ρ(s̃_{t,α}, p̃_{α}^{π}) ≤ C^{∗}γ^{t} with γ in Assumption L(π) and some C^{∗} > 0.

Recently, Yoshida [19] has given the notion of α-recurrent set for the fuzzy relation and shown that the α-cut of the limiting fuzzy set p̃^{π} in the above lemma is characterized as the maximum α-recurrent set. Theorem 4.1 says that for any π ∈ Π_{SC}^{∗}, Ψ(s̃, π^{∞}) is independent of s̃, so we write it by Ψ(π^{∞}).

For simplicity, let, for each π ∈ Π_{SC}^{∗} and D ∈ C(S),

R_{T,α}^{π^{∞}}(D) = ∑_{t=1}^{T} R_{α}^{π}(Q_{t,α}^{π}(D)).

Note from Lemma 4.1 that R_{T} (s̃, π^{∞})_{α} = R_{T,α}^{π^{∞}}(s̃_{α}) for all T ≥ 1 and α ∈ [0, 1]. Let R_{T,α}^{π^{∞}}(D) := [\underline{R}_{T,α}^{π^{∞}}(D), \overline{R}_{T,α}^{π^{∞}}(D)]. Then, by Lemma 2.1, we have

\underline{R}_{T,α}^{π^{∞}}(D) = ∑_{t=1}^{T} \underline{R}_{α}^{π}(Q_{t,α}^{π}(D))  (4.2)

and

\overline{R}_{T,α}^{π^{∞}}(D) = ∑_{t=1}^{T} \overline{R}_{α}^{π}(Q_{t,α}^{π}(D)),  (4.3)

where

R_{α}^{π}(D′) := [\underline{R}_{α}^{π}(D′), \overline{R}_{α}^{π}(D′)]

for all D′ ∈ C(S). By Theorem 4.1 and Assumption B, we observe that R_{α}^{π}(s̃_{t,α}) → R_{α}^{π}(p̃_{α}^{π}) exponentially first as t → ∞. Thus, by (4.2) and (4.3),

\underline{h}_{α}^{π}(D) := lim_{T →∞}(\underline{R}_{T,α}^{π^{∞}}(D) − T × \underline{R}_{α}^{π}(p̃_{α}^{π}))  (4.4)

and

\overline{h}_{α}^{π}(D) := lim_{T →∞}(\overline{R}_{T,α}^{π^{∞}}(D) − T × \overline{R}_{α}^{π}(p̃_{α}^{π}))  (4.5)

converge for all D ∈ C(S). The function \underline{h}_{α} (\overline{h}_{α} resp.) is called lower (upper) relative value function, whose basic ideas are appearing in the theory of Markov processes (c.f. [12]).

Let us denote the α-cut of the discounted fuzzy reward :

ψ_{β}(π^{∞}, s̃)_{α} := [\underline{ψ}_{β}(π^{∞}, s̃)_{α}, \overline{ψ}_{β}(π^{∞}, s̃)_{α}], α ∈ [0, 1].  (4.6)

Then, for any π ∈ Π_{SC}^{∗}, the extremal points

Ψ(π^{∞})_{α} := [\underline{Ψ}_{α}(π^{∞}), \overline{Ψ}_{α}(π^{∞})]

are characterized in the following theorem, whose description is popular in the theory of Markov decision processes (cf. [1, 3, 12]).

Theorem 4.2. For any π ∈ Π_{SC}^{∗}, we have

\underline{ψ}_{β}(π^{∞}, s̃)_{α} = \underline{Ψ}_{α}(π^{∞})/(1 − β) + \underline{h}_{α}^{π}(s̃_{α}) + \underline{ε}(β, α),  (4.7)
\overline{ψ}_{β}(π^{∞}, s̃)_{α} = \overline{Ψ}_{α}(π^{∞})/(1 − β) + \overline{h}_{α}^{π}(s̃_{α}) + \overline{ε}(β, α),  (4.8)

where

|\underline{ε}(β, α)| ∨ |\overline{ε}(β, α)| → 0

uniformly for α ∈ [0, 1] as β → 1.

Proof. From Lemma 2.1, we have

\underline{ψ}_{β}(π^{∞}, s̃)_{α} = ∑_{t=1}^{∞} β^{t−1}\underline{R}_{α}^{π}(Q_{t,α}^{π}(s̃_{α}))

= ∑_{t=1}^{∞} β^{t−1}\underline{Ψ}_{α}(π^{∞}) + ∑_{t=1}^{∞} β^{t−1}(\underline{R}_{α}^{π}(Q_{t,α}^{π}(s̃_{α})) − \underline{Ψ}_{α}(π^{∞}))

= \underline{Ψ}_{α}(π^{∞})/(1 − β) + \underline{h}_{α}^{π}(s̃_{α}) + \underline{ε}(β, α),

where \underline{ε}(β, α) = ∑_{t=1}^{∞} β^{t−1}(\underline{R}_{α}^{π}(Q_{t,α}^{π}(s̃_{α})) − \underline{Ψ}_{α}(π^{∞})) − \underline{h}_{α}^{π}(s̃_{α}). As \underline{Ψ}_{α}(π^{∞}) = \underline{R}_{α}^{π}(p̃_{α}), by (4.4) and Abel theorem, it holds that \underline{ε}(β, α) → 0 uniformly for α ∈ [0, 1] as β ↑ 1, which proves (4.7). By arguments similar to the above, we can prove (4.8). This completes the proof. □

The proof of the following theorem is analogous to that of [7, Theorem 3.1].

Theorem 4.3. For any π ∈ Π_{SC}^{∗}, let \underline{h}_{α}^{π} and \overline{h}_{α}^{π} be defined as (4.4) and (4.5). Then, the following equations hold :

\underline{h}_{α}^{π}(D) + \underline{Ψ}_{α}(π^{∞}) = \underline{R}_{α}^{π}(D) + \underline{h}_{α}^{π}(Q_{α}^{π}(D))  (4.9)

and

\overline{h}_{α}^{π}(D) + \overline{Ψ}_{α}(π^{∞}) = \overline{R}_{α}^{π}(D) + \overline{h}_{α}^{π}(Q_{α}^{π}(D))  (4.10)

for all D ∈ C(S).

The following theorem is useful in policy improvement. Theorem 4.4. For any π ∈ Π_{SC}^{∗}, let \underline{h}_{α}^{π} and \overline{h}_{α}^{π} be defined as in (4.4) and (4.5). Let π′ ∈ Π_{SC}^{∗} be such that

\underline{h}_{α}^{π}(D) + \underline{Ψ}_{α}(π^{∞}) ≤ \underline{R}_{α}^{π′}(D) + \underline{h}_{α}^{π}(Q_{α}^{π′}(D))  (4.11)

and

\overline{h}_{α}^{π}(D) + \overline{Ψ}_{α}(π^{∞}) ≤ \overline{R}_{α}^{π′}(D) + \overline{h}_{α}^{π}(Q_{α}^{π′}(D))  (4.12)

for all D ∈ C(S) and α ∈ [0, 1]. Then Ψ(π^{∞}) ⪯ Ψ(π′^{∞}). Proof. Let π′ ∈ Π_{SC}^{∗} be such that (4.11) and (4.12) hold. Then, we have

\underline{h}_{α}^{π}(Q_{t,α}^{π′}(s̃_{α})) + \underline{Ψ}_{α}(π^{∞}) ≤ \underline{R}_{α}^{π′}(Q_{t,α}^{π′}(s̃_{α})) + \underline{h}_{α}^{π}(Q_{t+1,α}^{π′}(s̃_{α})) for all t ≥ 1. Summing up the above inequality for 1 ≤ t ≤ T, we get

\underline{h}_{α}^{π}(s̃_{α}) + T × \underline{Ψ}_{α}(π^{∞}) ≤ \underline{R}_{T,α}^{π′^{∞}}(s̃_{α}) + \underline{h}_{α}^{π}(Q_{T +1,α}^{π′}(s̃_{α})) for all t ≥ 1. Thus, since

\underline{Ψ}_{α}(π′^{∞}) = lim_{T →∞} \frac{1}{T} \underline{R}_{T,α}^{π′^{∞}}(s̃_{α}),

it holds that

\underline{Ψ}_{α}(π^{∞}) ≤ \underline{Ψ}_{α}(π′^{∞}).

Similarly

\overline{Ψ}_{α}(π^{∞}) ≤ \overline{Ψ}_{α}(π′^{∞}).

Therefore,

[\underline{Ψ}_{α}(π^{∞}), \overline{Ψ}_{α}(π^{∞})] ⪯ [\underline{Ψ}_{α}(π′^{∞}), \overline{Ψ}_{α}(π′^{∞})],

which shows

Ψ(π^{∞}) ⪯ Ψ(π′^{∞}).

Thus we get this theorem. □

Applying the method of the proof in Theorem 4.4, we can easily prove the following corollary. Corollary 4.1. For any π ∈ Π_{SC}^{∗}, let \underline{h}_{α}^{π} and \overline{h}_{α}^{π} be defined as in (4.4) and (4.5). Suppose that the following inequalities hold :

\underline{h}_{α}^{π}(D) + \underline{Ψ}_{α}(π^{∞}) ≥ \underline{R}_{α}^{π′}(D) + \underline{h}_{α}^{π}(Q_{α}^{π′}(D)) and

\overline{h}_{α}^{π}(D) + \overline{Ψ}_{α}(π^{∞}) ≥ \overline{R}_{α}^{π′}(D) + \overline{h}_{α}^{π}(Q_{α}^{π′}(D))

for all π′ ∈ Π_{SC}^{∗}, D ∈ C(S) and α ∈ [0, 1]. Then π^{∞} is absolutely optimal in Π_{SC}^{∗}, i.e.,

Ψ(π^{∞}) ⪰ Ψ(π′^{∞}) for all π′ ∈ Π_{SC}^{∗}.

5 The optimality equation

In this section, we derive the optimality equation and consider its validity for optimization. The proof is done by the “vanishing discounted factor” method, using Ascoli-Arzela theorem (c.f. [4, 8, 13]).

Theorem 5.1. Suppose that Assumptions A and B in Section 3 hold. Then, for any α ∈ [0, 1], there exist constants \underline{Ψ}_{α}, \overline{Ψ}_{α} and \underline{v}_{α}, \overline{v}_{α} : C(S) ↦ C([0, M]) such that

(i) [\underline{Ψ}_{α′}, \overline{Ψ}_{α′}] ⊃ [\underline{Ψ}_{α}, \overline{Ψ}_{α}] (5.1)

for any α, α′ (α′ < α) belonging to some countable subset dense in [0, 1], and

(ii) \underline{v}_{α}(D) + \underline{Ψ}_{α} = sup_{B∈C(A)}\{\underline{R}_{α}(D × B) + \underline{v}_{α}(Q_{α}(D × B))\} (5.2)

(iii) \overline{v}_{α}(D) + \overline{Ψ}_{α} = sup_{B∈C(A)}\{\overline{R}_{α}(D × B) + \overline{v}_{α}(Q_{α}(D × B))\} (5.3)

for all D ∈ C(S) and α ∈ [0, 1].

Proof. Select D_{0} ∈ C(S) arbitrary. For \underline{v}_{α,β} in Lemma 3.1, let

\underline{g}_{α,β}(D) := \underline{v}_{α,β}(D) − \underline{v}_{α,β}(D_{0}) for D ∈ C(S).

Then, noting (3.4), it holds that

\begin{aligned}& \underline{g}_{α,β}(D) + (1 − β)\underline{v}_{α,β}(D_{0}) \\ = & sup_{B∈C(A)}\{\underline{R}_{α}(D × B) + β\underline{g}_{α,β}(Q_{α}(D × B))\}. \end{aligned}  (5.4)

Since 0 ≤ (1 − β)\underline{v}_{α,β}(D_{0}) ≤ M for all β ∈ (0, 1), there exists a sequence \{β_{n}\}_{n=0}^{∞} such that β_{n} ↑ 1 and (1 − β_{n})\underline{v}_{α,β_{n}}(D_{0}) → \underline{Ψ}_{α}. By Lemma 3.1, \underline{g}_{α,β_{n}}(·), n ≥ 1, are equi-continuous and uniformly bounded, so that, applying the Ascoli-Arzela theorem ([13]), \underline{g}_{α,β_{n}}(·) → \underline{v}_{α}(·) uniformly along a subsequence (also called {β_{n}} by abuse of notation). Thus, letting n → ∞ in (5.4) for β = β_{n}, we get (5.2). Also, putting \overline{g}_{α,β}(D) := \overline{v}_{α,β}(D) − \overline{v}_{α,β}(D_{0}), the proof of (5.3) is given as same as the above. Note that we can assume, without loss of generality, that (1 − β_{n})\underline{v}_{α,β_{n}}(D_{0}) → \underline{Ψ}_{α} and (1 − β_{n})\overline{v}_{α,β_{n}}(D_{0}) → \overline{Ψ}_{α} for any rational number α in [0, 1]. Since

[\underline{v}_{α′,β}(D_{0}), \overline{v}_{α′,β}(D_{0})] ⊃ [\underline{v}_{α,β}(D_{0}), \overline{v}_{α,β}(D_{0})]

for all α, α′ (α′ < α) and β ∈ [0, 1] (c.f. [6]), (i) holds obviously. This completes the proof. □

It will be shown in Theorem 5.2 below that [\underline{Ψ}_{α}, \overline{Ψ}_{α}] given in Theorem 5.1 is corresponding to the α-cut of the maximum average fuzzy reward, so that (5.2) and (5.3) are interpreted as the optimality equations for our average fuzzy decision model. For this purpose, we need the following lemmas.

Lemma 5.1. For any ñ, m̃ ∈ F([0, M]), if ñ_{α} ⪰ (=)m̃_{α} on some subset F dense in [0, 1], then ñ ⪰ (=)m̃.

Proof. From the denseness of F, we observe that for any α ∈ [0, 1]

ñ_{α} = lim_{α′↑α with α′∈F} ñ_{α′} ⪰ (=) lim_{α′↑α with α′∈F} m̃_{α′} = m̃_{α},

which implies ñ ⪰ (=)m̃. □

Lemma 5.2 (c.f. [5, 11]). Suppose that a family of subsets {D_{α}, α ∈ [0, 1]} satisfies the following (i) and (ii) :

(i) D_{α′} ⊂ D_{α} for all α, α′(0 ≤ α′ ≤ α ≤ 1),

(ii) lim_{α′↑α} D_{α′} = D_{α} for all α ∈ [0, 1]. Then, s̃(x) := sup_{α∈[0,1]}{α ∧ I_{D_{α}}(x)}, x ∈ S, satisfies s̃ ∈ F(S) and s̃_{α} = D_{α} for all α ∈ [0, 1].

Let denote by F a countable subset on which (i) in Theorem 5.1 holds. For \underline{Ψ}_{α} and \overline{Ψ}_{α} given in Theorem 5.1, let, for any α ∈ [0, 1],

Ψ_{α}^{−} := lim_{α′↑α with α′∈F} \underline{Ψ}_{α′}, Ψ_{0}^{−} := \underline{Ψ}_{0},

Ψ_{α}^{+} := lim_{α′↑α with α′∈F} \overline{Ψ}_{α′}, Ψ_{0}^{+} := \overline{Ψ}_{0}.

Since the conditions (i) and (ii) in Lemma 5.2 hold for the family {[Ψ_{α}^{−}, Ψ_{α}^{+}]; α ∈ [0, 1]}, we can construct the fuzzy set Ψ̃ by

Ψ̃(u) := sup_{α∈[0,1]}{α ∧ 1_{[Ψ_{α}^{−},Ψ_{α}^{+}]}(u)}, u ∈ [0, ∞).

Now, we can state the following theorem.

Theorem 5.2.

(i) Ψ̃ ⪰ Ψ(π^{∞}) for any π ∈ Π_{SC}^{∗}.

(ii) If there exists a strategy π^{∗} ∈ Π_{SC}^{∗} such that

\underline{v}_{α}(D) + \underline{Ψ}_{α} = \underline{R}_{α}(D × π^{∗}(α, D)) + \underline{v}_{α}(Q_{α}(D × π^{∗}(α, D)))

and

\overline{v}_{α}(D) + \overline{Ψ}_{α} = \overline{R}_{α}(D × π^{∗}(α, D)) + \overline{v}_{α}(Q_{α}(D × π^{∗}(α, D)))

for all D ∈ C(S) and α ∈ [0, 1], then π^{∗}^{∞} is absolutely optimal in the family of continuous stationary policies, i.e.,

Ψ(π^{∗}^{∞}) ⪰ Ψ(π^{∞}) for all π ∈ Π_{SC}^{∗}.

Proof. Let π ∈ Π_{SC}^{∗}. By the optimality equations (5.2) and (5.3), we have

\underline{v}_{α}(D) + \underline{Ψ}_{α} ≥ \underline{R}_{α}^{π}(D) + \underline{v}_{α}(Q_{α}^{π}(D))  (5.5)

and

\overline{v}_{α}(D) + \overline{Ψ}_{α} ≥ \overline{R}_{α}^{π}(D) + \overline{v}_{α}(Q_{α}^{π}(D))  (5.6)

for all D ∈ C(S). By the same discussion as that in the proof of Theorem 4.4, we can prove from (5.5) and (5.6) that

[\underline{Ψ}_{α}, \overline{Ψ}_{α}] ⪰ Ψ(π^{∞})_{α} for all α ∈ [0, 1].  (5.7)

Since [Ψ_{α}^{−}, Ψ_{α}^{+}] = [\underline{Ψ}_{α}, \overline{Ψ}_{α}] for all α ∈ F, we obtain (i) of Theorem 5.2 from (5.7) and Lemma 5.1. For (ii), by the same method as the above, we can prove that Ψ̃ = Ψ(π^{∗}^{∞}). Thus, together with (i), (ii) follows. This completes the proof. □

Here we give a numerical example to illustrate the theoretical results in this section. Let S := [0, 1], A := [0, 1/2] and M := 1. Take the fuzzy relation and the fuzzy reward by

q̃(x, a, y) = (1 − 3|y − ax|) ∨ 0, x, y ∈ [0, 1], a ∈ [0, 1/2]  (5.8)

and

r̃(x, a, z) = (1 − 6|x − z|) ∨ 0, x, z ∈ [0, 1].  (5.9)

r̃ is independent of a ∈ [0, 1/2]. Obviously, they satisfy Assumption A for t_{0} = 1 and Assumption B. Let α ∈ [0, 1] and π(a) := I_{{a}} ∈ Π_{SC}^{∗} for a ∈ A. From (5.8) and (5.9), we get

Q_{α}^{π(a)}({x}) = [(ax − (1 − α)/3) ∨ 0, ax + (1 − α)/3]

for x ∈ [0, 1], a ∈ [0, 1/2]. So

Q_{α}^{π(a)}([c, b]) = [T_{1}^{a}(c), T_{2}^{a}(b)]  (5.10)

for 0 ≤ c ≤ b ≤ 1, where maps T_{i}^{a} : [0, 1] ↦ [0, 1] (i = 1, 2; a ∈ [0, 1/2]) are given by

T_{1}^{a}(x) := (ax − (1 − α)/3) ∨ 0; T_{2}^{a}(x) := ax + (1 − α)/3 for x ∈ [0, 1].

Similarly we observe that

R_{α}^{π(a)}([c, b]) = [(c − (1 − α)/6) ∨ 0, (b + (1 − α)/6) ∧ 1] for 0 ≤ c ≤ b ≤ 1.

By (5.10), a unique fixed point p̃_{α}^{π(a)} of the map Q_{α}^{π(a)} : C([0, 1]) ↦ C([0, 1]) can be found to be

p̃_{α}^{π(a)} = [0, (1 − α)/3(1 − a)] .

Applying Theorem 4.1, we get

Ψ(s̃, π(a)^{∞})_{α} = [0, (1 − α)(3 − a)/6(1 − a)] for α ∈ [0, 1].  (5.11)

In [7], the average fuzzy reward and the relative value functions \underline{h}_{α} and \overline{h}_{α} for π(1/2)^{∞} have been given as follows :

Ψ(s̃, π(1/2)^{∞})(x) = \{ \begin{matrix}1 − 6x/5 & 0 ≤ x ≤ 5/6 \\ 0 & 5/6 < x ≤ 1, \end{matrix}

\begin{aligned}& \underline{h}_{α}^{π(1/2)}(c) := \underline{h}_{α}^{π(1/2)}([c, b]) \\ = & \{ \begin{matrix}2 (1 − (1/2)^{t^{∗}}) (c + 2(1 − α)/3) − 5t^{∗}(1 − α)/6 & α < 1 \\ 2c & α = 1, \end{matrix} \end{aligned}

where t^{∗} is the smallest non-negative integer such that

(1/2)^{t^{∗}} (c + 2(1 − α)/3) − 5(1 − α)/6 < 0,

and

\overline{h}_{α}^{π(1/2)}(b) := \overline{h}_{α}^{π(1/2)}([c, b]) = \{ \begin{matrix}2b − 4(1 − α)/3 & if 0 ≤ b < (5 + α)/6 \\ b + (3α − 1)/2 & if (5 + α)/6 ≤ b ≤ 1. \end{matrix}

The graph of \underline{h}_{α}^{π(1/2)} and \overline{h}_{α}^{π(1/2)} for α = 1/2 is given in Figure 1, from which we conjecture the monotonicity of \underline{h}_{α}^{π(1/2)} and \overline{h}_{α}^{π(1/2)}.

x \overline{h}_{α}^{π(1/2)}(x) \underline{h}_{α}^{π(1/2)}(x)
Fig. 1 : The relative value functions \underline{h}_{α}^{π(1/2)} and \overline{h}_{α}^{π(1/2)} for α = 1/2.

By the definition of Section 3, we see that

Q_{α}([c, b] × [c′, b′]) = [(cc′ − (1 − α)/3) ∨ 0, (bb′ + (1 + α)/3)]

and

R_{α}([c, b] × [c′, b′]) = [(c − (1 − α)/6) ∨ 0, (b + (1 − α)/6) ∧ 1]

for [c, b] ∈ C(S), [c′, b′] ∈ C(A). Noting (5.11) for a = 1/2, let us put \underline{Ψ}_{α} = 0 and \overline{Ψ}_{α} = 5(1 − α)/6. Then, by the monotonicity of Q_{α}, R_{α}, \underline{h}_{α}^{π(1/2)} and \overline{h}_{α}^{π(1/2)}, we get the optimality equations described in (5.2) and (5.3) :

\underline{h}_{α}^{π(1/2)}([c, b]) + \underline{Ψ}_{α}
= sup_{[c′,b′]∈C(A)}\{\underline{R}_{α}([c, b] × [c′, b′]) + \underline{h}_{α}^{π(1/2)}(Q_{α}([c, b] × [c′, b′]))\}
= \underline{R}_{α}([c, b] × \{1/2\}) + \underline{h}_{α}^{π(1/2)}(Q_{α}([c, b] × \{1/2\}))  (5.12)

and

\overline{h}_{α}^{π(1/2)}([c, b]) + \overline{Ψ}_{α}
= sup_{[c′,b′]∈C(A)}\{\overline{R}_{α}([c, b] × [c′, b′]) + \overline{h}_{α}^{π(1/2)}(Q_{α}([c, b] × [c′, b′]))\}
= \overline{R}_{α}([c, b] × \{1/2\}) + \overline{h}_{α}^{π(1/2)}(Q_{α}([c, b] × \{1/2\}))  (5.13)

for all [c, b] ∈ C(S). From Theorem 5.2, π(1/2)^{∞} becomes absolutely optimal.

References

[1] Bertsekas,D.P. and Shreve,S.E., Stochastic Optimal Control : the Discrete Time Case (Academic Press, New York, 1978).

[2] Birkhoff,G., “Lattice Theory”, Amer. Math. Soc., Coll. Pub., 25 (1940).

[3] Blackwell,D., “Discrete dynamic programming”, Ann. Math. Stat. 33 (1962) 719-726.

[4] Fernándes-Gaucherand,E., “A note on Ross-Taylor theorem”, Applied Math. and Computation 64 (1994) 207-212.

[5] Kurano,M., Yasuda,M., Nakagami,J. and Yoshida,Y., “A limit theorem in some dynamic fuzzy systems”, Fuzzy Sets and Systems 51 (1992) 83-88.

[6] Kurano,M., Yasuda,M., Nakagami,J. and Yoshida,Y., “Markov-type fuzzy decision processes with a discounted reward on a closed interval”, European J. of Oper. Res., 92 (1994) pp.649–662.

[7] Kurano,M., Yasuda,M., Nakagami,J. and Yoshida,Y., “The time average reward with some dynamic fuzzy systems”, to appear in Comp. Math. Appli.

[8] Kuratowski,K., Topology I (Academic Press, New York, 1966).

[9] Puri,M.L. and Ralescu,D.A., “The concept of normality for fuzzy random variables”, Ann. Prob. 13 (1985) 1373-1379.

[10] Nanda,S., “On sequences of fuzzy numbers”, Fuzzy Sets and Systems 33 (1989) 123-126.

[11] Novàk,V., Fuzzy Sets and Their Applications (Adam Hilder, Bristol-Boston, 1989).

[12] Ross,S.M., Applied probability models with optimization applications (Holden-Say, San Francisco, 1970).

[13] Royden,H.L., Real Analysis, 2nd ed. (Macmillan, New York, 1968).

[14] Taylor,H.M., “Markovian sequential replacement processes”, Ann. Math. Statist. 38 (1965) 1677-2122.

[15] Xu,Chen-wei, “On convexity of fuzzy sets and fuzzy relations”, Information Science 59 (1992) 92-102.

[16] Yasuda,M., “A linear structure and convexity for relations in dynamic fuzzy systems”, Computers Math. Applic. 27 (1994) 23-27.

[17] Yoshida,Y., Yasuda,M., Nakagami,J. and Kurano,M., “A potential of fuzzy relations with a linear structure : The contractive case”, Fuzzy Sets and Systems 60 (1993) 283-294.

[18] Yoshida,Y., Yasuda,M., Nakagami,J. and Kurano,M., “A potential of fuzzy relations with a linear structure : The unbounded case”, Fuzzy Sets and Systems 66 (1994) 83-95.

[19] Yoshida,Y., “The recurrence of dynamic fuzzy systems”, to appear in Fuzzy Sets and Systems.

[20] Zadeh,L.A., “Fuzzy sets”, Inform. and Control 8 (1965) 338-353.