A LEARNING ALGORITHM FOR COMMUNICATING MARKOV DECISION PROCESSES WITH UNKNOWN TRANSITION MATRICES

by

Tetsuichiro ���, Masayuki ���������,  Masami ������

and Masami ������

Reprinted from the Bulletin of Informatics and Cybernetics Research Association of Statistical Sciences,Vol.39

[figure]

FUKUOKA, JAPAN

Bulletin of Informatics and Cybernetics, Vol. 39, 2007

A LEARNING ALGORITHM FOR COMMUNICATING MARKOV DECISION

PROCESSES WITH UNKNOWN TRANSITION MATRICES

By

Tetsuichiro ���^{∗}, Masayuki ���������^{†},  Masami ������^{‡}

and Masami ������^{§}

Abstract

This study is concerned with finite Markov decision processes (MDPs) whose state are exactly observable but its transition matrix is unknown. We develop a learning algorithm of the reward-penalty type for the communicating case of multi-chain MDPs. An adaptively optimal policy and an asymptotic sequence of adaptive policies with nearly optimal properties are constructed under the average expected reward criterion. Also, a numerical experiment is given to show the practical effectiveness of the algorithm.

Key Words and Phrases: Adaptive policy, Average case, Communicating case, Learning algorithm, Markov decision processes, Reward-penalty type, Unknown transition matrix.

1. Introduction and notation

In the real world, there are many requests to solve uncertain models. Adaptive models for uncertain Markov decision processes (MDPs) have been considered by many authors as Hernández (1989), Hernández/ Marcus (1985), Kurano (1972), Kurano (1983), Mandl (1974), Martin (1967), van Hee (1978) and so on. The idea of Neuro dynamic programming by Bertsekas/Tsitsiklis (1996) is powerful in treating the adaptive MDPs.

However, a simple learning algorithm of the reward-penalty type, investigated by Lakshmivarahan (1981) and Meybodi/Lakshmivarahan (1982) are more comprehensible and manageable. Kurano (1987) proposed a learning algorithms of the reward-penalty type where all elements of the true transition matrices of finite MDPs are known to be positive and constructed adaptively optimal policy under the average expected reward criterion.

In this paper, applying the idea of Kurano (1987) to a wider class of uncertain MDPs, we develop a learning algorithm for the communicating case of multi-chain MDPs and construct an adaptively average optimal policy for a class of perturbed communicating MDPs. For general communicating MDPs, an asymptotic sequence of adaptive policies with nearly optimal properties is constructed by using the results of perturbed case.

∗ Faculty of Education and Culture, Miyazaki University, Miyazaki 889-2192 Japan,

e03101u@cc.miyazaki-u.ac.jp † General Education, Yuge National College of Maritime Technology, Ehime 794-2593 Japan,

horiguchi@gen.yuge.ac.jp ‡ Faculty of Science, Chiba University, Chiba 263-8522 Japan, yasuda@math.s.chiba-u.ac.jp § Faculty of Education, Chiba University, Chiba 263-8522 Japan, kurano@faculty.chiba-u.jp

In the reminder of this section, we will formulate finite MDPs whose transition matrices are unknown but the state at each stage is observable exactly. Consider a controlled dynamic system with finite state and action spaces, S and A, containing N < ∞ and K < ∞ elements respectively. Let ℚ denote the parameter space of K unknown stochastic matrices, that is

ℚ = {q = (q_{ij}(a)) | q_{ij}(a) ≧ 0, ∑_{j∈S} q_{ij}(a) = 1 for i, j ∈ S, a ∈ A}.

The sample space is the product space Ω = (S × A)^{∞} such that the projections X_{t}, Δ_{t} on the t-th factors S, A describe the state and action at the t-th stage of the process(t ≧ 0). Let Π denote the set of all policies, i.e., for π = (π_{0}, π_{1}, …) ∈ Π, let π_{t} ∈ P (A|(S ×A)^{t} ×S) for all t ≧ 0, where, for any finite sets X and Y, P (X|Y) denotes the set of all conditional probability distribution on X given Y. A policy π = (π_{0}, π_{1}, …) is called randomized stationary if a conditional probability γ = (γ(·|i) : i ∈ S) ∈ P (A|S) such that π_{t}(·|x_{0}, a_{0}, …, x_{t}) = γ(·|x_{t}) for all t ≧ 0 and (x_{0}, a_{0}, …, x_{t}) ∈ (S × A)^{t} × S. Such a policy is simply denoted by γ. We denote by F the set of functions on S with f(i) ∈ A for all i ∈ S. A randomized stationary policy γ is called stationary if there exists a function f ∈ F with γ({f(i)}|i) = 1 for all i ∈ S, which is denoted simply by f.

We will construct a probability space as follows: For any initial state X_{0} = i, π ∈ Π and a transition law q = (q_{ij}(a)) ∈ ℚ, let P (X_{t+1} = j|X_{0}, Δ_{0}, …, X_{t} = i, Δ_{t} = a) = q_{ij}(a) and P (Δ_{t} = a|X_{0}, Δ_{0}, …, X_{t} = i) = π_{t}(a|X_{0}, Δ_{0}, …, X_{t} = i) (t ≧ 0). Then, we can define the probability measure P_{π}(·|X_{0} = i, q) on Ω. For a given reward function r on S × A, we shall consider the long-run expected average reward:

ψ(i, q|π) = lim inf_{T →∞} \frac{1}{T + 1}E_{π}(∑_{t=0}^{T} r(X_{t}, Δ_{t}) | X_{0} = i, q)  (1.1)

where E_{π}(·|X_{0} = i, q) is the expectation operator with respect to P_{π}(·|X_{0} = i, q).

Let D be a subset of ℚ. Then, the problem is to maximize ψ(i, q|π) over all π ∈ Π for any i ∈ S and q ∈ D. Thus, denoting the optimal value function as

ψ(i, q) = sup_{π∈Π} ψ(i, q|π),  (1.2)

a policy π^{∗} ∈ Π will be called q-optimal if ψ(i, q|π^{∗}) = ψ(i, q) for all i ∈ S and called adaptively optimal for D if π^{∗} is q-optimal for all q ∈ D. A sequences of policies {π^{n}}_{n=1}^{∞} ⊂ Π is called an asymptotic sequence of adaptive policies with nearly optimal properties for D if

lim_{n→∞} ψ(i, q|π^{n}) = ψ(i, q) for all q ∈ D.

In Kurano (1987), an adaptively optimal policy for ℚ^{+} := {q = (q_{ij}(a)) ∈ ℚ | q_{ij}(a) > 0 for all i, j ∈ S and a ∈ A} was constructed by applying the value iteration and the policy improvement algorithm (cf. Lakshmivarahan (1981), Federgruen/Schweitzer (1981), Hernández (1989), Hernández/ Marcus (1985)). In this paper, we treat with the communicating case of multi-chain MDPs applying the idea of Kurano (1987) extensively.

A transition matrix q = (q_{ij}(a)) ∈ ℚ is said communicating (cf. Bather (1973), Puterman (1994)) if for any i, j ∈ S there exists a path from i to j with positive probability, i.e., it holds that

q_{i_{1}i_{2}}(a_{1})q_{i_{2}i_{3}}(a_{2}) ⋯ q_{i_{l−1}i_{l}}(a_{l−1}) > 0

for some {i_{1} = i, i_{2}, …, i_{l} = j} ⊂ S and {a_{1}, a_{2}, …, a_{l−1}} ⊂ A and 2 ≦ l ≦ N. It is easily shown that q = (q_{ij}(a)) is communicating if and only if there is a randomized stationary policy γ = (γ(·|i) : i ∈ S) satisfying that the transition matrix q(γ) = (q_{ij}(γ)) induced by γ defines an irreducible Markov chain (cf. Kemeny/Snell (1960)) where q_{ij}(γ) = ∑_{a∈A} q_{ij}(a)γ(a|i) for i, j ∈ S.

Let B(S) be the set of all functions on S. The following fact is well-known (cf. Puterman (1994), Ross (1970)).

Lemma 1.1 (Puterman (1994), Ross (1970)) Let q = (q_{ij}(a)) ∈ ℚ. Supposed that there exists a constant g and a v ∈ B(S) such that, for all i ∈ S,

v(i) = max_{a∈A}{r(i, a) + ∑_{j∈S} q_{ij}(a)v(j)} − g.  (1.3)

Then, g is unique and g = ψ(i, q) = ψ(i, q|f) for i ∈ S, where f ∈ F is q-optimal and f(i) is a maximizer in the right-hand side of (1.3) for all i ∈ S.

Let ℚ^{∗} be the set of all communicating transition matrices. In order to treat with the communicating case with q ∈ ℚ^{∗}, we use the so-called vanishing discount approach which studies the average case by considering the corresponding (1 − τ)-discounted one as letting τ → 0. The expected total (1 − τ)-discounted reward is defined by

v_{τ} (i, q|π) = E_{π}(∑_{t=0}^{∞}(1 − τ)^{t}r(X_{t}, Δ_{t}) | X_{0} = i, q)  (1.4)

for i ∈ S, q ∈ ℚ and π ∈ Π, and v_{τ} (i, q) = sup_{π∈Π} v_{τ} (i, q|π) is called a (1 − τ)-discounted value function, where (1 − τ) ∈ (0, 1) is a given discount factor.

For any q = (q_{ij}(a)) ∈ ℚ and τ ∈ (0, 1), we define the operator U_{τ} {q} : B(S) → B(S) by

U_{τ} {q}u(i) = max_{a∈A}{r(i, a) + (1 − τ) ∑_{j∈S} q_{ij}(a)u(j)}  (1.5)

for all i ∈ S and u ∈ B(S). We have the following.

Lemma 1.2 (Puterman (1994), Ross (1970)) It holds that

(i) the operator U_{τ} {q} is a contraction with the modulus (1 − τ),

(ii) the (1 − τ)-discount value function v_{τ} (i, q) is a unique fixed point of U_{τ} {q}, i.e.,

v_{τ} = U_{τ} {q}v_{τ} ,  (1.6)

(iii) v_{τ} (i, q) = v_{τ} (i, q|f_{τ}) and lim_{τ→0} τv_{τ} (i, q) = ψ(i, q), where f_{τ} is a maximizer of the

right-hand side in (1.6).

In Section 2, continuity of the value function for perturbed transition matrices is proved, by which an adaptively optimal policy for the perturbed communicating MDPs is constructed through a learning algorithm of reward-penalty type in Section 3. Also, Section 3 is devoted to the construction of an asymptotic sequence of adaptive policies with nearly optimal properties. In Section 4, a numerical experiment is implemented to show the practical effectiveness of the learning algorithm given in Section 3.

2. Continuity of the value function

First we give a key lemma for guaranteeing the validity of the vanishing discount approach to study the average case.

Lemma 2.1 Let q = (q_{ij}(a)) ∈ ℚ^{∗}. Then, there exists a constant M such that

lim sup_{τ→0} | v_{τ} (i, q) − v_{τ} (j, q) |≦ M for all i, j ∈ S.  (2.1)

Proof. We denote by H_{t} := (X_{0}, Δ_{0}, …, X_{t}) the history of states and actions until the t-th step(t ≧ 1) with H_{0} = (X_{0}). For each j ∈ S, we define the stopping time σ^{j} by

σ^{j} = σ^{j}(H_{t}) = first t ≧ 0 such that X_{t} = j.

That q ∈ Q^{∗} guarantees that there exists a randomized stationary policy γ = (γ(·|i) : i ∈ S) such that the Markov chain induced by q(γ) is irreducible. Here, using the stationary policy f_{τ} given in Lemma 1.2 the policy π^{j} = (π_{0}^{j}, π_{1}^{j}, …) will be defined by

π_{t}^{j}(·|H_{t}) = \begin{cases}γ(·|X_{t}) & if t < σ^{j}(H_{t}), \\ f_{τ} (X_{t}) & if t ≧ σ^{j}(H_{t}). \end{cases}

for t ≧ 0. Then we have the following: For i ∈ S,

v_{τ} (i, q|π^{j}) = E_{γ}( ∑_{t=0}^{σ^{j}−1}(1 − τ)^{t}r(X_{t}, Δ_{t}) | X_{0} = i, q)

+ E_{γ}((1 − τ)^{σ^{j}} | X_{0} = i, q)v_{τ} (j|q). (2.2)

From irreducibility of the Markov chain induced by q(γ), it holds (cf. Kemeny/Snell (1960)) that

E_{γ}(σ^{j} | X_{0} = i, q) < ∞ for all i ∈ S.  (2.3)

Concerning with the second term of the right-hand side in (2.2), since lim_{τ→0} \frac{(1−τ)^{n}−1}{τ} = −n (n ≧ 1), we have that

lim inf_{τ→0} \frac{1}{τ} \{E_{γ}((1 − τ)^{σ^{j}} | X_{0} = i, q) − 1\}

≧ ∑_{n=0}^{∞} lim inf_{τ→0} \frac{(1 − τ)^{n} − 1}{τ}P_{γ}(σ^{j} = n | X_{0} = i, q)

= − ∑_{n=1}^{∞} nP_{γ}(σ^{j} = n | X_{0} = i, q) = −E_{γ}(σ^{j} | X_{0} = i, q).  (2.4)

On the other hand, from (2.2) it holds that

v_{τ} (i, q) − v_{τ} (j, q) ≧ v_{τ} (i, q|π^{j}) − v_{τ} (j, q)

≧ −∥r∥E_{γ}(σ^{j} | X_{0} = i, q) + {E_{γ}((1 − τ)^{σ^{j}} | X_{0} = i, q) − 1}v_{τ} (j, q)

where ∥r∥ = max_{i∈S,a∈A}|r(i, a)|. Thus, by (2.2), (2.4) and Lemma 1.2(iii) we have that

lim inf_{τ→0}(v_{τ} (i, q) − v_{τ} (j, q)) ≧ − lim sup_{τ→0}(∥r∥ + |τv_{τ} (j, q)|)E_{γ}(σ^{j} | X_{0} = i, q)
= −(∥r∥ + |ψ(j, q)|)E_{γ}(σ^{j}|X_{0} = i, q) > −∞.

Similarly, we get that

lim inf_{τ→0}(v_{τ} (j, q) − v_{τ} (i, q)) ≧ −(∥r∥ + |ψ(i, q)|)E_{γ}(σ^{i}|X_{0} = j, q) > −∞,

and hence

lim sup_{τ→0}|v_{τ} (i, q) − v_{τ} (j, q)| ≦ (∥r∥ + |ψ(i, q)|)E_{γ}(σ^{i}|X_{0} = j, q) < ∞.

If we put M := max_{i,j∈S}(∥r∥ + |ψ(j, q)|)E_{γ}(σ^{j} | X_{0} = i, q), (2.1) follows, which completes the proof. ⊓ ⊔

Let P (S) be the set of all probability distributions on S, i.e.,

P (S) = {μ = (μ_{1}, μ_{2}, …, μ_{N}) | μ_{i} ≧ 0, ∑_{i=1}^{N} μ_{i} = 1 for all i ∈ S}.

Let q = (q_{ij}(a)) ∈ ℚ. For any τ ∈ (0, 1) and μ = (μ_{1}, μ_{2}, …, μ_{N}) ∈ P (S), we perturb q to q^{τ,μ} = (q_{ij}^{τ,μ}(a)) which is defined by

q_{ij}^{τ,μ}(a) = τμ_{j} + (1 − τ)q_{ij}(a) for i, j ∈ S and a ∈ A.  (2.5)

The matrix expression of (2.5) is q^{τ,μ} = τeμ + (1 − τ)q, where e = (1, 1, …, 1)^{t} is a transpose of N-dimensional vector (1, 1, …, 1). Then, we find that (1.6) in Lemma 1.2 can be rewritten as follows: For all i ∈ S,

v_{τ} (i, q) = max_{a∈A}{r(i, a) + ∑_{j∈S} q_{ij}^{μ,τ} (a)v_{τ} (j, q)} − τ ∑_{j∈S} μ_{j}v_{τ} (j, q).  (2.6)

Thus, applying Lemma 1.1, we have the following.

Lemma 2.2 For any q ∈ ℚ, τ ∈ (0, 1) and μ ∈ P (S), it holds that

(i) ψ(i, q^{τ,μ}) = τ ∑_{j∈S} μ_{j}v_{τ} (j, q) for all i ∈ S,

(ii) f_{τ} is q^{τ,μ}-optimal, where f_{τ} is given in Lemma 1.2.

From Lemma 2.2, since ψ(i, q^{τ,μ}) is independent of i ∈ S, we shall put ψ(q^{τ,μ}) := ψ(i, q^{τ,μ}). The τ-continuity of ψ(q^{τ,μ}) is given in the following.

Theorem 2.1 Let q ∈ ℚ^{∗}. Then, we have that

(i) ψ(i, q)(:= ψ(q)) is independent of i ∈ S and there exists a u ∈ B(S) satisfying the average optimality equation:

u(i) = max_{a∈A}{r(i, a) + ∑_{j∈S} q_{ij}(a)u(j)} − ψ(q) (i ∈ S),  (2.7)

(ii) for any μ ∈ P (S), ψ(q^{μ,τ}) → ψ(q) as τ → 0.

Proof. For any fixed i_{0} ∈ S, let u_{τ} (i) = v_{τ} (i, q) − v_{τ} (i_{0}, q) for each i ∈ S. Then, from (2.6) we get

u_{τ} (i) = max_{a∈A}{r(i, a) + ∑_{j∈S} q_{ij}^{μ,τ} (a)u_{τ} (j)} − τ ∑_{j∈S} μ_{j}v_{τ} (j, q) (i ∈ S).  (2.8)

By Lemma 1.2, lim_{τ→0} τv_{τ} (j, q) = ψ(j, q). Also, from Lemma 2.1, there exists a sequence {τ_{l}} with τ_{l} → 0 and u_{τ_{l}}(j) → u(j) as l → ∞ for some u ∈ B(S) and all j ∈ S. Thus, letting l → ∞ in (2.8) with τ = τ_{l}, we get (2.7) with ψ(q) = ∑_{j∈S} μ_{j}ψ(j, q). Applying Lemma 1.1, we observe that ψ(q) is independent of μ ∈ P (S), so that (i) and (ii) follows.

⊓ ⊔

We note that (i) in Theorem 2.1 derives the single average optimality equation for the communicating MDPs, which has been given first by Bather (1973). In general, the value function ψ(i, q) is known to be continuous on each equivalent class of ℚ (cf. Schweitzer (1968), Solan (2003)), but (ii) in Theorem 2.1 gives an example in which ψ(i, q) is continuous in q across the equivalent classes.

3. Learning algorithms and analysis

In this section, we give a learning algorithm of reward-penalty type for MDPs with the transition matrices q ∈ ℚ^{∗}, by which the adaptive policy is constructed. For any i ∈ S and a ∈ A, a sequence of stopping times {σ^{n}(i, a)}_{n=0}^{∞} will be defined as follows.

σ^{0}(i, a) = 0, σ^{n}(i, a) = inf{t|t > σ^{n−1}(i, a), X_{t} = i, Δ_{t} = a} (n ≧ 1).  (3.1)

Let W := ⋂_{(i,a)∈S×A} W (i, a), where W (i, a) = ⋂_{n=1}^{∞}{σ^{n}(i, a) < ∞}. We note that ω ∈ W means that for any (i, a) ∈ S × A the event {X_{t}(ω) = i, Δ_{t}(ω) = a} happens in infinitely many stages.

The following is an extension of Lemma 1 in Kurano (1983) to the communicating case.

Lemma 3.1 Let a policy π = (π_{0}, π_{1}, …) and a decreasing sequence of positive numbers {ε_{t}}_{t=0}^{∞} satisfy that

(i) for each t ≧ 0, π_{t}(a|h_{t}) ≧ ε_{t} with a ∈ A and h_{t} = (x_{0}, a_{0}, …, x_{t}) ∈ H_{t},

(ii) ∑_{t=0}^{∞} ε_{t}^{N} = ∞.

Then, P_{π}(W | X_{0} = i, q) = 1 for all q ∈ ℚ^{∗} and i ∈ S.

Proof. For notation simplicity, for any fixed q ∈ ℚ^{∗} we put P (·) = P_{π}(·|X_{0} = i, q). From the definition of the communicating MDPs and (i) in Lemma 3.1, we have that there exists δ > 0 such that

P (X_{t} = i, Δ_{t} = a for some t with n ≦ t ≦ n + N|H_{n}) ≧ δε_{n+N}^{N}  (3.2)

for any n ≧ 0 and i ∈ S, a ∈ A. For any fixed i ∈ S, a ∈ A, let B_{t} := B_{t}(i, a) := {σ^{n}(i, a) = t for some n ≧ 1}. Then, we observe that W (i, a) = lim sup_{t→∞} B_{t}(i, a) =

(lim inf_{t→∞} B_{t}^{c}(i, a))^{c}, so that it holds that

P (W (i, a)) = 1 − P (lim inf_{t→∞} B_{t}^{c}(i, a)).  (3.3)

For any positive integer L with L > n, let l := [(L − n + 1)/N] − 1, where for a real number z, [z] is the largest integer equal to or less than z. Then, we have from (3.3) and (ii) in Lemma 3.1 that

P ( ⋂_{t=n}^{L} B_{t}^{c}(i, a))

≦ P ( ⋂_{α=0}^{l} ⋂_{t=n+αN}^{n+(α+1)N−1} B_{t}^{c}(i, a))

≦ {1 − P ( ⋃_{t=n}^{n+N−1} B_{t}(i, a))} ⋯ {1 − P ( ⋃_{t=n+lN}^{n+(l+1)N−1} B_{t}(i, a)| ⋂_{t=n}^{n+lN−1} B_{t}^{c}(i, a))}

≦ (1 − δε_{n+N−1}^{N}) ⋯ (1 − δε_{n+(l+1)N−1}^{N})

≦ exp{−δ ∑_{i=1}^{l+1} ε_{n+iN−1}^{N}} → 0 as L → ∞,

which implies that lim_{L→∞} P (⋂_{t=n}^{L} B_{t}^{c}(i, a)) = P (⋂_{t=n}^{∞} B_{t}^{c}(i, a)) = 0 for all n ≧ 1. Thus, from (3.3) P (W (i, a)) = 1, which implies P (W) = 1. ⊓ ⊔

We note that a sequence {1/(t+1)^{1/N}}_{t=0}^{∞} satisfies (ii) of Lemma 3.1 as an example. For each i, j ∈ S and a ∈ A, let N_{n}(i, j|a) = ∑_{t=0}^{n} I_{{X_{t}=i,Δ_{t}=a,X_{t+1}=j}} and

N_{n}(i|a) = ∑_{t=0}^{n} I_{{X_{t}=i,Δ_{t}=a}}, where I_{D} is the indicator function of a set D. Let

q_{ij}^{n}(a) = \begin{cases}\frac{N_{n}(i, j|a)}{N_{n}(i|a)} & if N_{n}(i|a) > 0, \\ 0 & otherwise. \end{cases}

Then, q_{ij}^{n} = (q_{ij}^{n}(a)) is the maximum likelihood estimator of the unknown transition matrices. For any given q^{0} = (q_{ij}^{0}(a)) ∈ ℚ, we define q̃^{n} = (q̃_{ij}^{n}(a)) ∈ ℚ by

q̃_{ij}^{n}(a) = \begin{cases}q_{ij}^{n}(a) & if N_{n}(i|a) > 0, \\ q_{ij}^{0}(a) & otherwise. \end{cases}

We consider the following iterative scheme which is a variant of the non-stationary value iteration scheme proposed by Federgruen/Schweitzer (1981):

ṽ_{0} = 0, ṽ_{n+1} = U_{τ} {q̃^{n}}ṽ_{n} (n ≧ 0)  (3.4)

for any τ ∈ (0, 1). For each i ∈ S and n(n ≧ 0), let ã_{n+1}(i) denote an action which maximizes the right-hand side of the second equation in (3.4). For any sequence {b_{n}}_{n=0}^{∞} of positive numbers with b_{0} = 1, 0 < b_{n+1} < 1 and b_{n} > b_{n+1} for all n ≧ 0, let ϕ be any strictly increasing function such that ϕ : [0, 1] → [0, 1] and ϕ(b_{n}) = b_{n+1} for all n ≧ 0.

Here, we define a learning algorithm based on ã_{n+1} and ϕ. For each n(n ≧ 0), letting π̃_{n}^{τ}(a|i) = P (Δ_{n} = a|X_{0}, Δ_{0}, …, X_{n} = i) we propose to update π̃_{n}^{τ} as follows: if ã_{n+1}(i) = a_{i} for each i ∈ S,

\begin{aligned}π̃_{n+1}^{τ}(a_{i}|i) & = 1 − ∑_{a≠a_{i}} ϕ(π̃_{n}^{τ}(a|i)), \\ π̃_{n+1}^{τ}(a|i) & = ϕ(π̃_{n}^{τ}(a|i)) (a ≠ a_{i}). \end{aligned}  (3.5)

In (3.5), the probability of choosing the action a_{i} at the next stage increases and that of choosing one of the other actions decreases, such that the algorithm (3.5) is a learning algorithm of the reward-penalty type (cf. Lakshmivarahan (1981), Meybodi/Lakshmivarahan (1982), Sutton and Barto (1998)). Note that given π̃_{0}^{τ} , π̃^{τ} = (π̃_{0}^{τ} , π̃_{1}^{τ} , …) ∈ Π and π̃_{n}^{τ} (n ≧ 1) is successively determined by (3.4) and (3.5).

We need the following condition.

Condition A.

(i) b_{n} → 0 as n → ∞ and ∑_{n=0}^{∞} b_{n}^{N} = ∞,

(ii) π̃_{0}^{τ} (a|i) > 0 for all i ∈ S, a ∈ A.

Under this condition, the following lemma is proved similarly as Lemma 3 and 4 in Kurano (1987), so the proof is omitted.

Lemma 3.2 Let q ∈ ℚ^{∗}. Then, under Condition A, the following (i)–(iii) holds with P_{}_{π̃^{τ}} (·|X_{0} = i, q)-a.s.:

(i) q̃^{n} → q as n → ∞, (ii) ṽ_{n}(i) → v_{τ} (i, q) as n → ∞, (iii) π̃_{n}^{τ}(A_{τ}^{∗}(i|q)|H_{n}, X_{n} = i) → 1 as n → ∞,

where A_{τ}^{∗}(i|q) is the set of all actions which maximize the right-hand side of (1.6).

Let ^{τ} ℚ^{∗} := {q^{τ,μ}|μ ∈ P (S) and q ∈ ℚ^{∗}}, where q^{τ,μ} is defined in (2.5). Then, observing the discussion in Section 2 and ^{τ} ℚ^{∗} ⊂ ℚ^{∗}, from Lemma 3.2 we find that the results in Kurano (1987) can be applicable to the class of perturbed transition matrices τ ℚ^{∗} . So, we have the following.

A learning algorithm for communicating MDPs 19

Theorem 3.1 Under Condition A, π̃^{τ} is adaptively optimal for ^{τ} ℚ^{∗} . Here we can state the following theorem for the communicating case. Theorem 3.2 Under Condition A, a sequence {π̃^{τ_{n}}}_{n=1}^{∞} with τ_{n} → 0 as n → ∞ is an asymptotic sequence of adaptive policies with nearly optimal properties for ℚ^{∗}. Proof. Let q ∈ ℚ^{∗}. For each t ≧ 0, let

\begin{aligned}δ̃_{t} & := (1 − τ)ṽ_{t}(X_{t}) − \{r(X_{t}, Δ_{t}) + (1 − τ)ṽ_{t}(X_{t+1})\} and \\ δ_{t}(j) & := E_{}_{π̃^{τ}} (δ̃_{t}|H_{t}, X_{t} = j, q). \end{aligned}

Then, by the stability theorem (cf. Loève (1963)), we get

lim_{T →∞} \frac{1}{T + 1} ∑_{t=0}^{T}\{δ̃_{t} − δ_{t}(X_{t})\} = 0, P_{}_{π̃^{τ}} (·|X_{0} = i, q)-a.s.  (3.6)

On the other hand, it holds that

δ_{t}(j) = ṽ_{t}(j) − ∑_{a∈A}{r(j, a) + (1 − τ) ∑_{k∈S} q_{jk}(a)ṽ_{t}(k)}π̃_{t}^{τ} (a|j) − τṽ_{t}(j).

So, by (ii) and (iii) of Lemma 3.2,

lim_{t→∞} δ_{t}(j) = −τv_{τ} (j, q), P_{}_{π̃^{τ}} (·|X_{0} = i, q)-a.s.

Thus, from (3.6) it holds that

min_{i∈S}\{−τv_{τ} (i, q)\} ≦ lim inf_{T →∞} \frac{1}{T + 1} ∑_{t=0}^{T} δ̃_{t}

≦ lim sup_{T →∞} \frac{1}{T + 1} ∑_{t=0}^{T} δ̃_{t} ≦ max_{i∈S}\{−τv_{τ} (i, q)\}.

(3.7)

However, we have

∑_{t=0}^{T} δ̃_{t} = − ∑_{t=0}^{T} r(X_{t}, Δ_{t}) + (1 − τ) ∑_{t=0}^{T}(ṽ_{t}(X_{t}) − ṽ_{t}(X_{t+1}))

by the definition. The second term in the right-hand-side is rewritten as

(1 − τ){ṽ_{0}(X_{0}) + ∑_{t=1}^{T}(ṽ_{t}(X_{t}) − ṽ_{t−1}(X_{t})) − ṽ_{T} (X_{T +1})}

so by (ii) of Lemma 3.2,

lim sup_{T →∞}(lim inf_{T →∞})\frac{1}{T + 1} ∑_{t=0}^{T} δ̃_{t} = lim sup_{T →∞}(lim inf_{T →∞})\{−\frac{1}{T + 1} ∑_{t=0}^{T} r(X_{t}, Δ_{t})\}

respectively. Thus, applying Fatou’s Lemma, from (3.7) we get

min_{i∈S} τv_{τ} (i, q) ≦ ψ(i, q|π̃^{τ}) ≦ max_{i∈S} τv_{τ} (i, q).  (3.8)

By Lemma 1.2 and Theorem 2.1 (i), lim_{τ→0} τv_{τ} (i, q) = ψ(q), which implies from (3.8) that ψ(i, q|π̃^{τ}) → ψ(q) as τ → 0. This completes the proof. ⊓ ⊔

We summarize our learning algorithm for constructing adaptive policy π̃^{τ} as follows:

Step 1. Set n = 0. Specify τ (0 < τ < 1). Choose π̃_{0}^{τ} (a|i) which satisfies (ii) in
Condition A. Select q_{ij}^{0}(a) arbitrarily and define ṽ_{0}(i) = 0 (i ∈ S).
Step 2. If X_{n} = i, choose an action a_{i} ∈ A(i) from the decision rule π̃_{n}^{τ}.
Observe the next state X_{n+1} = j and calculate N_{n}(i, j|a) and N_{n}(i|a).
Step 3. Set

q̃_{ij}^{n}(a) = \begin{cases}N_{n}(i, j|a)/N_{n}(i|a) & if N_{n}(i|a) > 0 \\ q_{ij}^{0}(a) & otherwise. \end{cases}

Step 4. Choose ã_{n+1}(i) which satisfies

ã_{i} := ã_{n+1}(i) ∈ arg max_{a∈A}{r(i, a) + (1 − τ) ∑_{j∈S} q̃_{ij}^{n}(a)ṽ_{n}(j)}.

Step 5. Update π̃_{n+1}^{τ}(i) (i ∈ S) by

π̃_{n+1}^{τ}(α|i) = ϕ (π̃_{n}^{τ}(α|i)) (α ≠ ã_{i}), and π̃_{n+1}^{τ}(ã_{i}|i) = 1 − ∑_{α≠ã_{i}} ϕ (π̃_{n}^{τ}(α|i)) .

Step 6. Set n = n + 1 and return to Step 2.

Figure 3.1: Learning Algorithm for vanishing rate τ.

4. A numerical experiment

In this section, we give a simulation result for learning algorithm in Section 3. Consider the three state MDPs with S = {1, 2, 3} and A = {1, 2}, whose transition

matrices are parameterized with 0 < p_{1}, q_{1}, p_{2}, q_{2} < 1 and reward function r(i, a) (i ∈ S, a ∈ A) are given in Table 4.1 and Figure 4.1.

state action parameterized transition matrices reward
i  a  j = 1  j = 2  j = 3  r(i, a)
1  1  p_{1}  1 − p_{1}  0  3 0
2  1 − p_{2}  p_{2}  0  2.5
2  1  0  q_{1}  1 − q_{1}  2 0
2  1 − q_{2}  q_{2}  0  1.5
3  1  0  0  1  1 0
2  0  1  0  0.5

Table 4.1: Data of simulated MDPs.

From this table and figure, we observe that the transition matrix q has a property of communicating provided that 0 < p_{1}, q_{1}, p_{2}, q_{2} < 1. We denote by ψ̃_{n} the average

Figure 4.1: Transition diagrams parameterized with 0 < p_{1}, q_{1}, p_{2}, q_{2} < 1.

present value until n-th time, which is defined by

ψ̃_{n} = \frac{1}{n} ∑_{t=0}^{n−1} r(X_{t}, Δ_{t}) (n ≧ 1).

To calculate the quantity explicitly, we set π̃_{0}^{τ} (·|i) = (\frac{1}{2}, \frac{1}{2}) for each i ∈ S and q_{0} with p_{1} = \frac{2}{5}, q_{1} = \frac{1}{2}, p_{2} = \frac{3}{10}, q_{2} = \frac{3}{10}, i.e.,

q^{0} = (q_{ij}^{0}(a)) = \{(q_{ij}^{0}(1)) = (\begin{matrix}\frac{2}{5} & \frac{3}{5} & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 \end{matrix}) , (q_{ij}^{0}(2)) = (\begin{matrix}\frac{7}{10} & \frac{3}{10} & 0 \\ \frac{7}{10} & \frac{3}{10} & 0 \\ 0 & 1 & 0 \end{matrix})\}.

We use a strictly increasing function ϕ such that

ϕ(x) = (\frac{x^{N}}{1 + x^{N}} )^{1/N}

where N denotes the number of states in S. Let {b_{n}} be such that b_{0} = 1 and b_{n} = n^{−1/N} (n ≥ 1). It is easily checked that the property (i) in Condition A is satisfied with b_{n+1} = ϕ(b_{n}) (n ≧ 0).

Now, we make numerical experiments with the true transition matrices whose parameters are given by p_{1} = p_{2} = \frac{1}{3}, q_{1} = q_{2} = \frac{2}{5}, i.e.,

q = (q_{ij}(a)) = \{(q_{ij}(1)) = (\begin{matrix}\frac{1}{3} & \frac{2}{3} & 0 \\ 0 & \frac{2}{5} & \frac{3}{5} \\ 0 & 0 & 1 \end{matrix}) , (q_{ij}(2)) = (\begin{matrix}\frac{2}{3} & \frac{1}{3} & 0 \\ \frac{3}{5} & \frac{2}{5} & 0 \\ 0 & 1 & 0 \end{matrix})\}.

values  [figure: τ; n] 10^{3} 5 × 10^{3} 10^{4} 5 × 10^{4} 10^{5}  10^{6}
ψ̃_{n}  0.5  2.1104 2.1437 2.1569 2.1801 2.1876 2.2002
0.2  2.1214 2.1468 2.1585 2.1805 2.1878 2.2002
0.1  2.1224 2.1470 2.1586 2.1805 2.1878 2.2002
0.01  2.1184 2.1462 2.1581 2.1804 2.1878 2.2002
decision rules [figure: τ; n] 10^{3} 5 × 10^{3} 10^{4} 5 × 10^{4} 10^{5}  10^{6}
π̃_{n}^{τ}(1|1)  0.5  0.9003 0.9416 0.9536 0.9729 0.9785 0.9900
0.2  0.8980 0.9413 0.9535 0.9728 0.9785 0.9900
0.1  0.8983 0.9413 0.9535 0.9728 0.9785 0.9900
0.01  0.8937 0.9409 0.9533 0.9728 0.9784 0.9900
π̃_{n}^{τ}(2|2) 0.5 0.8996 0.9415 0.9536 0.9729 0.9785 0.9900
0.2  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
0.1  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
0.01  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
π̃_{n}^{τ}(2|3) 0.5 0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
0.2  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
0.1  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900
0.01  0.9002 0.9415 0.9536 0.9729 0.9785 0.9900

Table 4.2: The simulation value of ψ̃_{n} and π̃_{n}^{τ} for each τ = 0.5, 0.2, 0.1, 0.01.

Figure 4.2: The trajectories of ψ̃_{n}(τ = 0.01). The dotted line means the optimal value of average reward.

Considering the optimal average reward ψ(q) = 42/19 ≈ 2.2105 and the q-optimal stationary policy f^{∗} with f^{∗}(1) = 1, f^{∗}(2) = f^{∗}(3) = 2, it is seen that ψ̃_{n} → ψ(q) = 42/19 and π̃_{n}^{τ}(1|1), π̃_{n}^{τ}(2|2), π̃_{n}^{τ}(2|3) → 1 as n → ∞ hold from the above Table 4.2 and Figure 4.2. The results of the above simulation show that the learning algorithm is practically effective for the communicating class of transition matrices.

References

Bather, J. (1973). Optimal decision procedures for finite Markov chains. II. Communi-

cating systems. Adv. in Appl. Probab., 5:521–540. Bertsekas, D. P. and Tsitsiklis, J. H. (1996). Neuro-Dynamic Programming. Athena

Scientific. Billingsley, P. (1961). Statistical inference for Markov processes. The University of

Chicago Press. Federgruen, A. and Schweitzer, P. J. (1981). Nonstationary Markov decision problems

with converging parameters. J. Optim. Theory Appl., 34(2):207–241. Hernández-Lerma, O. (1989). Adaptive Markov control processes. Springer-Verlag. Hernández-Lerma, O. and Marcus, S. I. (1985). Adaptive control of discounted Markov

decision chains. J. Optim. Theory Appl., 46(2):227–235. Kemeny, J. G. and Snell, J. L. (1960). Finite Markov chains. D. Van Nostrand. Kurano, M. (1972). Discrete-time Markovian decision processes with an unknown pa-

rameter. Average return criterion. J. Operations Res. Soc. Japan, 15:67–76. Kurano, M. (1983). Adaptive policies in Markov decision processes with uncertain tran-

sition matrices. J. Inform. Optim. Sci., 4(1):21–40. Kurano, M. (1987). Learning algorithms for Markov decision processes. J. Appl.

Probab., 24(1):270–276. Lakshmivarahan, S. (1981). Learning algorithms. Springer-Verlag. Leizarowitz, A. (2003). An algorithm to identify and compute average optimal policies

in multichain Markov decision processes. Math. Oper. Res., 28(3):553–586. Loève, M. (1963). Probability theory. D. Van Nostrand. Mandl, P. (1974). Estimation and control in Markov chains. Adv. in Appl. Probab., 6:40–

60. Martin, J. J. (1967). Bayesian decision problems and Markov chains. John Wiley &

Sons Inc. Meybodi, M. R. and Lakshmivarahan, S. (1982). ε-optimality of a general class of

learning algorithms. Inform. Sci., 28(1):1–20. Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic pro-

gramming. John Wiley & Sons Inc. Ross, S. M. (1970). Applied probability models with optimization applications. Holden-

Day. Schweitzer, P. J. (1968). Perturbation theory and finite Markov chains. J. Appl. Proba-

bility, 5:401–413. Solan, E. (2003). Continuity of the value of competitive Markov decision processes. J.

Theoret. Probab., 16(4):831–845 (2004). Sutton, R. S. and Barto, A. G. (1998). Reinforcement Learning: An Introducution.

MIT Press. van Hee, K. M. (1978). Bayesian control of Markov chains. Mathematisch Centrum.

24 T. Iki, M. Horiguchi, M. Yasuda, and M. Kurano

Received June 7, 2006 Revised February 25, 2007