数理解析研究所講究録 1477 巻 2006 年 127-135

127
A learning algorithm for communicating Markov decision
processes with unknown transition matrices
哲一郎 (Tetsuichiro IKI)
Culture,Miyazaki University
Faculty of Education and東京電機大学・情報環境学部 堀口 正之 (Masayuki HORIGUCHI)
School of Information Environment, Tokyo Denki University
千葉大学・理学部 安田正實 (Masami YASUDA)
Faculty of Science, Chiba University
千葉大学・教育学部 蔵野 正美 (Masami KURANO)
Faculty of Education, Chiba University

宮崎大学・教育文化学部

伊喜Abstract
This study is concerned with finite Markov decision processes(MDPs) whose transition matrices are unknown but the state is observable exactly. We develop alearning algorithm of the reward-penalty type for the communicating case ofmulti-chain MDPs by which 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 toshow the practical effectiveness of the algorithm.
Key words: Adaptive policy, Markov decision processes, communicating case,average case, learning algorithm, reward-penalty type.

Introduction and notation

1

Markov decision processes(MDPs) whose transition probabilities are unknown to a decision maker have been investigated by many authors (cf. [4, 5, 8, 9, 14, 15]). Kurano[10]proposed a learning algorithms of the reward-penalty type(cf. [11, 16]) for the positive
case where all elements of the true transition matrices of finite MDPs are known to bepositive, by which adaptively optim al policy are constructed under the average expected
reward criterion.
In this paper, applying the idea of [10] extensively to a large class of uncertain MDPs,
we develop a learning algorithm for the communicating case of multi-chain MDPs andconstruct 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.
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
and , containing $N<$ oc anddynamic system with finite state and action spaces,$K<\infty$ elements respectively. Let
denote the parameter space of $K$ unknown stochastic, $\sum_{j\in S}q_{ij}(a)=1$ for $i,j\in$,matrices, that is $\mathbb{Q}=\{q|q=$
$S$

$A$

$\mathbb{Q}$$(q_{ij}(a) :$S$\mathrm{i},j\in S_{\}}a\in A)$$q_{ij}(a)\geqq 0$, $a\in A\}$ .

”such that the projections
The sample space is the product spaceat the t-th stage of theactionon the t-th factors , describe the state and
, let
,...
denote the set of all policies, i.e., forprocess(t 40). Let$X$ and, $P(X|Y)$ denotes, where, for any finite sets
for all$X$ givenpolicy.
A
the set of all conditional probability distribution on
is called randomized stationary if a conditional probability$\Omega=$$X_{t},$$S$$\Delta_{t}$$(S\mathrm{x} A)$$A$$\pi=(\pi_{0)}\pi_{1}$$\Pi$$\pi_{t}\in P(A|(S\mathrm{x} A)^{t}\mathrm{x} S)$$)$$\in\Pi$$Y$$t\geqq 0$$Y$$\gamma=$$\pi=(\pi_{0}, \pi_{1}, \ldots)$$(\gamma(\cdot|\mathrm{i}) :\mathrm{i}\in S)\in P(A|S)$

128

’
.
such thatfor all $t\geqq 0$ and$F$
Such a policy is simply denoted by 7. We denote by
the set of functions on with
. A randomized stationary policy 7 is called stationary if there exists
for all$f\inF$, which is denoted simply by .
a function
withfor all...,,, we assume that $P(X_{t+1}=j|X_{0},$For anyand, $\Delta_{t}=a)=q_{ij}(a)$ and, . . . . $X_{t}=$. Then, we can define the probability measureon .
, we shall consider the long-run expected average
For a given reward function on:
reward associated with
(1)$(x_{0}, a_{0}, \ldots \dot, x_{t})\in(S\mathrm{x} A)$$\pi_{t}(\cdot|x_{0}, a_{0}, \ldots, x_{t})=\gamma(\cdot|x_{t})$$\mathrm{x}S$$S$$\mathrm{i}\in S$$f(\mathrm{i})\in A$$f$$\mathrm{i}\in S$$\gamma(\{f(\mathrm{i})\}|\mathrm{i})=1$$X_{0}=\mathrm{i}$$q=(q_{\dot{x}_{J}}(a))\in \mathbb{Q}$$\pi\in \mathrm{I}\mathrm{I}$$\Delta_{0)}$$P(\Delta_{t}=a|X_{0}, \Delta_{0}., \cdot.

$X_{t}=\mathrm{i}$, , X_{t}=\mathrm{i})=\pi_{t}(a|X_{0)}\Delta_{0}$$\mathrm{i})(t\geqq 0)$$\Omega$$P_{\pi}(\cdot|X_{0}=\dot{\iota}, q)$$r$$S\mathrm{x}A$$q\in \mathbb{Q}$$\psi(\mathrm{i}, q|\pi)=\lim\inf_{Tarrow\infty}\frac{1}{T+1}E_{\pi}(\sum_{t=0}^{T}r(X_{t}, \Delta_{t})|X_{0}=\mathrm{i},$ $q)$

where $E_{\pi}(\cdot|X_{0}=i, q)$ is the expectation operator.
of Q. Then, the problem is to maximize
over allThus, denoting by
the value function, i.e.,$\psi(i, q)=\sup_{\pi\in\Pi}\psi(i, q|\pi)$ ,(2)$\mathrm{w}.\mathrm{r}.\mathrm{t}$$P_{\pi}(\cdot|X_{0}=\mathrm{i}, q)$$\psi(\mathrm{i}, q|\pi)$$\pi\in \mathrm{Y}\mathrm{I}$. Let

for any$\prime D$$\mathrm{i}\in S$

be a subset
andD.
$q\in$$\psi(\mathrm{i}, q)$will be called -optimal if
for all $i\in S$ and called adaptively
optimal for $D$ if
is -optimal for all $q\in$ D. A sequences of policiesIIis called an asymptotic sequence of adaptive policies with nearly optimal properties for7) if
for all $q\in D$ . Let $\mathbb{Q}^{+}:=\{q=(q_{ij}(a))\in \mathbb{Q}|q_{ij}(a)>$$a\inA$
for all ,and}. In [10], a learning algorithm of the reward-penalty type(cf. [11]) was given, by which an adaptively optimal policy for
was constructed byapplying value iteration and policy improvement algorithms (cf. [3, 4, 5]). In this paper,
we treat with the communicating case of multi-chain MDPs applying the idea of [10]extensively. The transition matrices $q=(q_{ij}(a))\in \mathbb{Q}$ is said communicating (cf. [1, 6,17]) if for any , $J\in S$ there exists a path from to with positive probability, i.e.,
it holds thatfor some
and $\{a_{1}.a_{2}, . . ,a_{l-1}\}\subset A$ and $2\leqq l\leqq N$ . It is easily shown that $q=(q_{ij}(a))$ is
communicating if and only if there is a randomized stationary policy
satisfying that the transition matrix
induced by defines an irreducible
Markov chain(cf. [7]) where.
for$B(S)$
Let
be the set of all functions on . The following fact is well-known(cf. [17, 18]).
Lemma 1.1 ([17, 18]). Let $q=(q_{ij}(a))\in \mathbb{Q}$ . Supposed that there exists a constant anda $v\in B(S)$ such that$v(i)$ $= \max_{a\in A}\{r(\mathrm{i}, a)+\sum_{g\in S}q_{ij}(a)v(j)\}-g$(3)
for all $i\in S$ .
$\pi^{*}\in\Pi$$\mathrm{f}(\mathrm{i})q|\pi’)$$q$$\pi^{*}$$=\mathrm{f}(\mathrm{i})q)$$\{\pi^{n}\}_{n=1}^{\infty}\subset$$q$$\lim_{narrow\infty}\psi(\mathrm{i}, q|\pi^{n})=\mathrm{f}(\mathrm{i})q)$

$0$

$i$

$\mathrm{i}\in S$$\mathbb{Q}^{+}$$j$$\mathrm{i}$$\mathrm{i}$$q_{i_{1}i_{2}}(a_{1})q_{i_{2}i_{3}}(a_{2})\cdots q_{i_{l-1}i_{l}}(a_{l-1})>0$$\{\mathrm{i}_{1}=\mathrm{i}, \mathrm{i}_{2}, \ldots, \mathrm{i}_{l}=j\}\subseteq S$$\gamma=(\gamma(\cdot|\mathrm{i}) :$\mathrm{q}(\mathrm{j})=(q_{ij}(\gamma))$i\in S)$$\gamma$$q_{ij}( \gamma)=\sum_{a\in A}q_{l\dot{f}}(a)\gamma(a|i)$$\mathrm{i},j\in S$

$S$

$g$

Then, is unique and, where $f\in F$ is -optimal andforis a maximizer in the right-hand side of (3) for all.
Let
be the set of all communicating transition matrices. In order to treat withthe communicating case with, we use the so-called vanishing discount approach
which studies the average case by considering the corresponding $(1-\tau)$ discount one
as letting. The expected total $(1-\tau)$ -discounted reward is defined by
(4)
,
for
and $\pi\in\Pi$ ,andis called a $(1-\tau)$ -discounted value function, where (1-r)$(0,1)$ is a given discount factor. For any $q=(q_{ij}(a))\in \mathbb{Q}$ and $\tau\in(0,1)$ , we define theoperator:by$g=\psi(\mathrm{i}.q)=\psi(\mathrm{i}, q|f)$$g$$\mathrm{i}\in S$$f(\dot{\iota})$$q$$\mathrm{i}\in S$$\mathbb{Q}^{*}$$q\in \mathbb{Q}^{*}$$\tauarrow$$0$$v_{\tau}(i, q| \pi)=E_{\pi}(\sum_{t=0}^{\infty}(1-\tau)^{t}r(X_{t}, \Delta_{t})|X_{0}=i,$$q)$$\mathrm{i}\in S$$q\in \mathbb{Q}$$v_{\tau}( \mathrm{i}, q)=\sup_{\pi\in\Pi}\mathrm{v}\mathrm{T}(\mathrm{i}, q|\pi)$$U_{\tau}\{q\}$

(5)

$\in$

$\mathrm{B}(\mathrm{S})arrow B(S)$$U_{\tau} \{q\}u(\mathrm{i})=\max_{a\in A}\{r(i,a)+(1-\tau)\sum_{j\in S}q_{ij}(a)u(j)\}$for all$\mathrm{i}\in S$

and $u\in B(S)$ .

129
We have the following.
Lemma 1.2 ([17, 18]). It holds that (i) the operator
modulus $(1-\tau)$ and (ii) the $(1-\tau)$ -discount value function

is a contraction with theis a unique fixed point$U_{\tau}\{q\}$of$U_{\tau}\{q\}$$v_{\tau}(i, q)$

, . .
$i$

$e_{f}$(6)$v_{\tau}=U_{\tau}\{q\}v_{\tau}$,, whereis a maximizer of theand(ii)right-hand side in (6).
In Section 2, continuity of the value function for perturbed transition matrices isproved, 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 toshow the practical effectiveness of the learning algorithm given in Section 3.
$\lim_{\tauarrow 0}\tau v_{\tau}(\mathrm{i}, q)=\psi(\mathrm{i}, q)$$v_{\tau}(\mathrm{i}, q)=v_{\tau}(\mathrm{i}, q|f_{\tau})$$f_{\tau}$

Continuity of the value function

2

First we give a key lemma for guaranteeing the validity of the vanishing discount approachto study the average case.
. Then, there exists a constant M such that
Lemma 2.1. Let q$\in S$ .
$\lim\sup_{\tauarrow 0}|v_{\tau}(i, q)-v_{\tau}(j, q)|\leqq M$(7)
for all$=(q_{ij}(a))\in \mathbb{Q}^{*}$$\mathrm{i},j$

Proof See Appendix.i$\sum_{i=1}\mu_{l}=1\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{a}11\mathrm{i}\in S\}.\mathrm{L}\mathrm{e}\mathrm{t}q=(q_{ij}(a))\in \mathbb{Q}.\mathrm{F}\lambda^{\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{a}11\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{a}\mathrm{b}\mathrm{i}1\mathrm{i}\mathrm{t}\mathrm{y}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{o}\mathrm{n}S,\mathrm{i}.\mathrm{e}.,P(g)=\{\mu=(\mu_{1},\ldots,\mu_{N})|}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{y}\tau\in(0, 1)\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{L}\mathrm{e}\mathrm{t}P(S$$\mu_{i}\geqq 0,$

which is defined by
and $a\in A$ .
for
(8)
is a
The matrix expression of (8) is $q^{\tau,\mu}=\tau e\mu+(1-\tau)q)$ where, 1). Then, we find that (6) in Lemma 1.2 cantranspose of $N$ -dimensional vector (1, 1,
be rewritten as follows.
.
for all(9)
Thus, applying Lemma 1.1, we have the following.
(0, 1) and $\mu\in P(S)$ , it holds that (i),Lemma 2.2. For any q
is given in Lemma 1,2.
optimal whereis, (ii)
q) for all iis independent of $i\in S$ , we shall put
From Lemma 2.2, since
is given in the following.
. The continuity ofis independent of. Then, we have that (i)Theorem 2.1. Let
equation:$i\in S$ and there exists a $u\in B(S)$ satisfying the average optimality$\mu=$$(\mu_{1}, \mu_{2}, \ldots, \mu_{N})\in P(S)$, we perturb

$q$

to

$q^{\tau,\mu}=(q_{ij}^{\tau,/\iota}(a))$$\mathrm{i}_{7}j\in S$$q_{ij}^{\tau,\mu}(a)=\tau\mu_{?}.\cdot+(1-\tau)q_{\mathrm{i}j}(a)$$e=(1,1, \ldots ., 1)^{\mathrm{t}}$$\ldots$$\mathrm{i}\in S$$v_{\tau}(i, q)= \max_{a\in A}\{r(i, a)+\sum_{j\in S}q_{ij}^{\mu\tau}(|a)v_{\tau}(j, q)\}-\tau\sum_{\gamma\in S}\mu_{j}v_{\tau}(j, q)$$\in \mathbb{Q}$$\in S$$\tau\sum_{j\in S}\mu_{j}v_{\tau}(j,$$\psi(i, q^{\tau,\mu})=$$\tau\in$$f_{\tau}$$q^{\tau,\mu}$$f_{\tau}$$\psi(q^{\tau,\mu}):=$$\psi(\mathrm{i}, q^{\tau,\mu})$$\psi(i, q^{\tau,\mu})$$\psi(q^{\tau,\mu})$$\tau$$\psi(\mathrm{i}, q)(:=\psi(q))$$q\in \mathbb{Q}^{*}$(10)$u(i)= \max_{a\in A}\{r(\mathrm{i}, a)+\sum_{j\in S}q_{ij}(a)u(j)\}-\psi(q)$(ii) for any $\mu\in P(S)$ ,Proof See$\psi(q^{\mu,\tau})arrow\psi(q)$as$\tauarrow 0$$(i\in S)$

,

.

.

$\mathrm{A}\mathrm{p}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{x}_{\mathrm{I}}$We note that (i) in Theorem 2.1 derives the single average optimality equation for thecommunicating MDPs, which has been given first by [1], In general, the value function(cf. [19, 20]), but (ii) in
is known to be continuous on each equivalent class ofacross the equivalentinis continuous
Theorem 2.1 gives as example in whichclasses$\mathbb{Q}$$\psi(\mathrm{i}, q)$$\psi(\mathrm{i}, q)$

$q$

130
Learning algorithms and analysis

3

IJ1 this section, we give a learning algorithm of reward-penalty type for MDPs with the, by which the adaptive policy is constructed.
ansition matrices
will be defined
For any $i\in S$ and $a\in A$ , a sequence of stopping times
at follows.
$q\in \mathbb{Q}^{*}$$\mathrm{t}\mathit{1}$$\{\sigma^{n}(\mathrm{i}, a)\}_{n=0}^{\infty}$(11)$\sigma^{0}(\mathrm{t}_{)}a)=0$,$\sigma^{n}(i, a)=\mathrm{i}\mathrm{r}1\mathrm{f}\{t|t>\sigma^{n-1}(i, a), X_{t}=i, \Delta_{t}=a\}(n\geqq 1)$.

. We note that $\in W$
happens in infinitely
the eventmeans that for any
many stages. The following is an extension of Lemma 1 in [9] to the communicating case.
Lemma 3.1. Let $\pi=$be any policy satisfying that there exists a decreasing,
sequence of positive numbers
such that (i) for eachfor all$a\in A$ and $h_{t}=$ (. Then, $P_{\pi}(W|X_{0}=\mathrm{i}, q)=1$, . . . , Jg)
and (ii)
and $i\in S$ .
for all.
Proof See
We note that as a example, the sequencesatisfies (ii) of Lemma 3.1.
$a\inA$
For each
and
, let
and
, whereis the indicator function of a set .
Let
if $N_{n}(\mathrm{i}|a)>0,0$ otherwise. Then,isthe maximum likelihood estimator of the unknown transition matrices.
For any givenby, we define,
ifotherwise. We consider the following iterative scheme which is avariant of the non-stationary value iteration scheme proposed by [3]:Let

$W:= \bigcap_{(i,a)\in S\mathrm{x}A}W(\mathrm{i}, a)$. where$(\mathrm{i}, a)\in S\mathrm{x}$$W( \mathrm{i}, a)=\bigcap_{n=1}^{\infty}\{\sigma^{n}(\mathrm{i}, a)<\infty\}$$A$$\omega$$\{X_{t}(\omega)=\mathrm{i}, \Delta_{t}(\omega)=a\}$$(\pi_{0}, \pi_{1}, \ldots)$$t$$\{\epsilon_{t}\}_{t=0}^{\infty}$$\in H_{t}$$x_{0}.,$ $a_{0}$$\geqq 0$$\pi_{t}(a|h_{t})\geqq\epsilon_{\ell}$$\sum_{t=0}^{\infty}\epsilon_{\mathrm{t}}^{N}=\infty$$q\in \mathbb{Q}^{*}$$\mathrm{A}\mathrm{p}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{x}_{\mathrm{I}}$$\{t^{-\frac{1}{N}}\}_{t=0}^{\infty}$$D$$I_{D}$$q_{i_{J}}^{n}=(q_{ij}^{n}(a)))$$q_{i\gamma}^{n}(a)=N_{\tau\iota}(\tilde{\iota},j|a)/N_{n}(\mathrm{i}|a)$$q^{0}=(q_{\mathrm{i}j}^{0}(a))\in \mathbb{Q}$$N_{n}(\mathrm{i}|a)>0$$N_{n}(\mathrm{i}|a)=$$N_{n}( \mathrm{i},j|a)=\sum_{t}^{n}=0I\{\mathrm{x}_{t}=i,\Delta_{l}=a,X_{\ell+1}=j\}$$\mathrm{i},\dot{J}\in S$$\sum_{t=0}^{n}I_{\{X_{t}=i,\Delta_{t}=a\}}$$\tilde{q}^{n}=(\tilde{q}_{l}^{n_{J}}(a))\in \mathbb{Q}$$\tilde{q}_{ij}^{n}(a)=q_{ij}^{n}(a)$$q_{ij}^{0}(a)$(12)$\tilde{v}_{0}=0,\tilde{v}_{n[perp] 1}=U_{\tau}\{\tilde{q}^{n}\}\tilde{v}_{n}(n \geqq 0)$.

For each $i\in S$ and $n(n\geqq 0)$ , letdenote an action which maximizes the right-handside of the second equation in (12). For any sequenceof positive numbers with$b_{0}=1$ , $0<b_{n+1}<1$ andfor all $n\geqq 0$ , let be any strictly increasing functionQ.
$=b_{n+1}$ for all
such that : $[0, 1]arrow[0,1]$ andHere, we define a learning algorithm based on
and . For each $n(n\geqq 0)$ , letting( $\Delta_{n}=k|X_{0},$ Ao-., ,) we propose to update
as follows:If, for each $i\in S,\tilde{a}_{n+1}(i)=a_{i}$ ,$\tilde{a}_{n+1}(\mathrm{i})$$\{b_{n}\}_{n=0}^{\infty}$$b_{n}>b_{n\neq 1}$$\phi$$n\geqq$$\phi(b_{n}\rangle$$\phi$$\tilde{a}_{n+1}$$\tilde{\pi}_{n}^{\tau}(k|\mathrm{i})=P$

(13)

,

$X_{n}=\mathrm{i}$$\phi$$\tilde{\pi}_{n}^{\tau}$.

$\tilde{\pi}_{n+1}^{\tau}(a_{i}|\mathrm{i})=1-\sum_{\alpha\neq a_{i}}\phi(\overline{\pi}_{n}^{\tau}(\alpha|i)),\tilde{\pi}_{n+1}^{\tau}(\alpha|\mathrm{i})=\phi(\tilde{\pi}_{n}^{\tau}(\alpha|\mathrm{i}))(\alpha\neq a_{i})$In (13), the probability of choosing the action at the next stage increases and that ofchoosing one of the other actions decreases, such that the algorithm (13) is a learning aigorithm of the reward-penalty type(cf. [11, 16, 21]). Note that given
II andis successively determined by (12) and (13).
We need the following condition.
Condition A. (i)
(ii)
as n
and
, a $\in A$ .
for all i
Lemma 3.2. let. Then, under Condition
the following
holds with$(ii)$
as $narrow\infty$ , (ii)as,as $narrow\infty$ , whereis the set of all actions whichmtmimize the right-hand side of (6).
$a_{\mathrm{z}}$$\tilde{\pi}_{0)}^{\tau}\tilde{\pi}^{\tau}=(\tilde{\pi}_{0}^{\tau},\tilde{\pi}_{1}^{\tau}\dot, \cdots)\in$$\tilde{\pi}_{n}^{\tau}(n\geqq 1)$$b_{n}arrow 0$$arrow\infty$$q\in \mathbb{Q}^{*}$$P_{\overline{\pi}^{\tau}}$$(\cdot|X_{0}=\mathrm{i}, q)- a.s.:(\mathrm{i})\tilde{q}^{n}arrow q$$\tilde{\pi}_{n}^{\tau}\langle A_{\tau}^{*}(\mathrm{i}|q)|H_{n}$$X_{n}=\mathrm{i})arrow 1$$\sum_{7\subset 0}^{\infty}b_{n}^{N}=$$\in S$$\tilde{\pi}_{0}^{\tau}(a|\mathrm{i})>0$$A_{2}$$v\sim n(i)arrow v_{\tau}(\mathrm{i}, q)$$A_{\tau}^{*}(i|q)$$(\mathrm{i})-(\mathrm{i}\mathrm{i}i)$$narrow\infty_{f}$131

Proof See Appendix.l

is defined in (8). Then, observing
andLet} , where{, from Lemma 3.2 we find that the results inthe discussion in Section 2 and. So, we have the[10] can be applicable to the class of perturbed transition matrices
following.
is adaptively optimal for
Theorem 3.1. Under Condition
Here we can state the following theorem for the communicating case,
is an
as n
with
Theorem 3.2. Under Condition A, a sequence.
properties
optimalnearlywithpolicies
adaptivesequencefor
asymptotic
of.
Proof, See$\tau \mathbb{Q}^{*}:=$$q^{\tau,\mu}|\mu\in P(S)$$q\in \mathbb{Q}^{*}$$q^{\tau,\mu}$$\tau \mathbb{Q}^{*}\subseteq \mathbb{Q}^{*}$$\tau \mathbb{Q}^{*}$$\tau \mathbb{Q}^{*}$$A_{f}\tilde{\pi}^{\tau}$$arrow\infty$$\tau_{n}arrow 0$$\{\tilde{\pi}^{\tau_{n}}\}_{n=1}^{\infty}$$\mathbb{Q}^{*}$$\mathrm{A}\mathrm{p}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{x}_{\mathrm{I}}$4

A numerical experiment

Hn 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, $q_{2}<1$ and reward function
matrices are parameterized with $0<p_{1}$ ,, $a\in A)$ are given in Table 4.1.
$r(\mathrm{i}, a)(\mathrm{i}\in$$q_{1},p_{2}$$S$$1\mathrm{s}^{\mathrm{e}}$$\frac{\not\supset\omega}{\not\in}2.22$. 214$\varphi w\omega^{\mathrm{i}}\sigma w\mathrm{b}2.18$$\mathrm{o}$$\underline{\mathrm{Q}j\{6\mathrm{b}}D$$‘\omega\succ_{\mathfrak{g}}$

210

1/6

1/3

1/2

2/3

1

5/6

$\mathrm{x}$$10^{6}$steps of learning algorithm

Table 4,1: parameterized transition matrices
and reward function of simulated MDPs, where
and $a\in A$ .
$\mathrm{i}_{\neg}j\in S$

We denote by$\tilde{\psi}_{n}$.
Figure 4.1: The trajectories of
The dotted line means the true optimal valueof average reward.
$\tilde{\psi}_{n}(\tau=0.01)$

the average present value until n-th time, which is defined by$\frac{1}{n}\sum_{t=0}^{n-1}r(X_{\mathrm{t}_{\rangle}}\Delta_{t})(n\geqq 1$$\psi- n=$}.
$q_{2}= \frac{3}{10,\mathrm{h}’}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{e}$$\mathrm{W}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{t}\tilde{\pi}_{0}^{\tau}(|i)=(\frac{1}{2},\frac{1}{2,\mathrm{i}},)\mathrm{f}o\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{i}\in S\mathrm{a}\mathrm{n}\mathrm{d}q_{0}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{t}1\mathrm{y}\mathrm{i}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{n}\mathrm{g}\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}i\mathrm{o}\mathrm{n}\phi \mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\phi(x)=(_{\overline{1}+x}^{x}\neg\nabla)^{\frac{11}{N}}\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}N\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}p1--\frac{2}{N5}7q=\frac{1}{2}p_{2}=\frac{3}{\mathrm{d}\mathrm{e}10},$We
number of states in . Note that it is easily checked that (i) in Condition A is satisfied
by defined above when $b_{0}=1$ and $b_{n+1}=\phi(b_{n})(n\geqq 0)$ .
Now, we make numerical experiments with the true transition matrices whose pa. The corresponding trajectories of,rameters are given byobtained by computer simulations of the learning algorithms (12)-(13) in Section
3 are given in Table 4.2 and Figure 4.1. It is shown that the optimal stationary polare,
icy of MDPs with true transition matrices such that
2.2105.
$\pi_{t}^{*}(1|1)=\pi_{t}^{*}(2|2)=\pi_{t}^{*}(2|3)=1(t \geqq 0)$ and the true optimal average reward.
listedn-step
are
each
at
of
frequency
Also, adaptive decision rules and relativealgorithm
ing
lear
the
that
show
in Table 4.3 and 4.4. The results of the above simulation
is practically effective for the communicating class of transition matrices$S$$\phi$$p_{1}=p_{2}= \frac{1}{3}$$q_{1}=q_{2}= \frac{2}{5}$$\tilde{\psi}_{n}$$p_{1}=p_{2}= \frac{1}{3}$$q_{1}=q_{2}= \frac{2}{5}$$\frac{42}{19}.=$$N(\mathrm{i},j|a)$132

Appendix
Proof of Lemma 2.1
We denote by $H_{t}:=$the history of states and actions until the t-th
step $(t.\geqq 1)$ with $H_{0}=(X_{0})$ . For each $j\in S$ , we define the stopping timeby$q\inQ^{*}$$X_{t}=j$a
firstsuch that. Thatguarantees that there exists a
randomized stationary policy
such that the Markov chain induced byis irreducible. Here, using the stationary policy given in Lemma 1.2 the policy
will be defined by
if
if,. Then we have the following:$(\mathrm{X}\mathrm{o}, \Delta_{0_{i}}\ldots , X_{t})$$\sigma^{j}$$=\sigma^{\mathrm{J}}(H_{\mathrm{f}})=$$t\geqq 0$$\gamma=(\gamma(\cdot|i\}:\mathrm{i}\in S)$$q(\gamma)$$\pi^{j}=$$f_{\mathcal{T}}$$(7\ulcorner^{\}}\pi_{1}^{J}0"\ldots)$$\pi_{\mathrm{t}}^{j}(\cdot|H_{t})=\gamma(\cdot|X_{t})$$t<\sigma^{j}(H_{t})$$\mathrm{f}\mathrm{r}(\mathrm{X}\mathrm{t})$$t\geqq\sigma^{j}(H_{t})j(t\geqq$

$0)$

(14)

$v_{\tau}( \mathrm{i}, q|\pi^{j})=E_{\gamma}(\sum_{t=0}^{\sigma^{j}1}(1-\tau)^{t}r(X_{t}, \Delta_{t})|X_{0}=\mathrm{i},$$q)$$+E_{\gamma}((1-\tau)^{\sigma^{j}}|X_{0}=i,q)v_{\tau}(j|q)(i\in S)$.

Prom irreducibility of the Markov chain induced by, it holds (cf. [7]) that(15).
oo for all$q(\gamma)$$E_{\gamma}(\sigma^{j}|X_{0}=\mathrm{i}, q)<$$\mathrm{i}\in S$

Concerning with the second term of the right-hand side in (14), since$-n(n\geqq 1)$ , we have that$\lim_{\tauarrow 0}\frac{\{1-\tau]^{n}-1}{\tau}=$

133$\lim\inf_{\tauarrow 0}\frac{1}{\tau}\{E_{\gamma}((1-\tau)^{\sigma^{j}}|X_{0}=i, q)-1\}$(16)$\geqq\sum_{n=0}^{\infty}\lim\inf_{\tauarrow 0}\frac{(1-\tau)^{n}-1}{\tau}P_{\gamma}(\sigma^{j}=n|X_{0}=\mathrm{i}, q)$$=- \sum_{n=1}^{\infty}nP7$ $(\sigma^{j}=n|X_{0}=\mathrm{i}, q)=-E_{\gamma}(\sigma^{j}|X_{0}=\mathrm{i}, q)$

On the other hand, from (14) it holds that.

$v_{\tau}(\mathrm{i}, q)-v_{\tau}(j\dot,q)\geqq v_{\tau}(\mathrm{i}, q|\pi^{\mathrm{J}})-v_{\tau}(\dot{J}, q)\geqq$$-||r||E_{\gamma}(\sigma|\mathrm{i}X_{0}=\mathrm{i}., q)+\{E_{\gamma}((1-\tau)^{\sigma^{j}}|X_{0}=\mathrm{i}, q)-1\}v_{\tau}(j_{7}q)$where$||r||= \max_{\iota\in S,a\in A}|r(\mathrm{i}_{j}a)|$.

Thus, by (14), (16) and Lemma 1.2(iii) we have that $\lim\inf_{\tauarrow 0}(v_{\tau}(i, q)-v_{\tau}(j,.q))\geqq$$- \lim\sup_{\tauarrow 0}(||r||+|\tau v_{\tau}(j, q)|)E_{\gamma}(\sigma^{j}|X_{0}=\mathrm{i}, q)=-(||r||+|\psi(j, q)|)E_{\gamma}(\sigma^{j}|X_{0}=x, q)>$Similarly, we get that
, $q)>-\infty$ , and hence, (7) follows, which completes. If we put
the proof.i
Proof of Theorem 2.1, let $u_{\tau}(j)=v_{\tau}(j, q)-v_{\tau}(i_{0}, q)$ for each $j\in S$ . Then, from (9) we get
For any fixed.
(17)$\lim\inf_{\tauarrow 0}(v_{\tau}(j, q)-v_{\tau}(i,q))\geqq-(||r||+|\psi(\mathrm{i}_{\dot{l}}q)|)E(\gamma\sigma^{i}|X_{0}=$$-\infty$ ,$\lim\sup_{\tauarrow 0}(v_{\tau}(\mathrm{i}, q)-v_{\tau}(j, q))\leqq(||r||+|\psi(\mathrm{i}, q)|)E_{\gamma}(\sigma^{i}|X_{0}=j, q)<$$j$$\infty$$M:= \max_{i_{1}\gamma\in S}(||r||+|\psi(j, q)|)E_{\gamma}(\sigma^{j}|X_{0}=\mathrm{i}, q)$$\mathrm{i}_{0}\in S$$u_{\tau}( \mathrm{i})=\max_{a\in A}\{r(\mathrm{i}, a)+\sum_{j\in S}q_{ij}^{\mu,\tau}(a)u_{\tau}(j)\}-\tau\sum_{j\in S}\mu_{j}v_{\tau}(j, q)(\mathrm{i}\in S)$

By Lemma 1.2, $\lim_{\tauarrow 0}\tau v_{r}.(j, q)=\psi(j, q)-$ Also, from Lem ma 2.1, there exists a sequence
oo for some $u\in B(S)$ and all $j\in S$ . Thus,
and $u_{\tau_{1}}(j)arrow u(j)$ as
with$(\tau_{l})$$\tau_{l}arrow 0$$l\Rightarrow$134
letting). Applying, we get (10) withoo in (17) with
Lemma 1.1, we observe thatis independent of $\mu\in P(S)$ , so that (i) and (ii) follows.1
Proof of Lemma 3.1
For notation simplicity, for any fixed
we put $P(\cdot)=P_{\pi}(\cdot|X_{0}=i, q)$ . From the(i)
MDPs
in Lemma 3.1, we have that there exists
communicating
anddefinition of thesuch that(18),(
for some with $n\leqq t\leqq n+N|H_{n}$ ), $a\in A$ .
for any $n\geqq 0$ and$l$$arrow$${\mathrm{q}$$\tau=\tau_{l}$$= \sum_{j\in S}\mu_{j}\psi(j, q)$$\psi(q)$$q\in \mathbb{Q}^{*}$$\delta>0$$P$$\Delta_{t}=a$$X_{t}=\mathrm{i}$$t$$\geqq\delta\epsilon_{n+N}^{N}$$\mathrm{i}\in S$

Let $B_{t}:=$ {$\mathrm{W}$( , $a)=t$ for some $n\geqq 1$ }. Then, we observe that, so that it holds that$\mathrm{W}(\mathrm{i}, a)=\lim\sup_{tarrow\infty}B_{t}=$$\mathrm{i}$$( \lim\inf_{tarrow\infty}B_{t}^{\mathrm{c}})^{c}$(19)$P(W( \mathrm{i}, a))=1-P(\lim\inf_{tarrow\infty}B_{t}^{\mathrm{c}})$.

For any positive integer with $L>n$ , let $l:=$, where for a real number ,is the largest integer equal to or less than . Then, we have from (19) and (ii) in
Lemma 3.1 that
{1$[ \frac{(L-n)}{N}]$

$z$

$[z]$

$z$

$P( \bigcap_{t=n}^{L}B_{t}^{c})\leqq P(\bigcap_{\alpha=0}^{l}\bigcap_{t=n+\alpha N}^{n+(\alpha+1)N-1}B_{t}^{\mathrm{c}})\leqq\{1-P(\bigcup_{t=n}^{n+N-1}B_{t})\}\cdots$$P( \bigcup_{t=lN}^{n+(t+1)N-1}B_{t}|\bigcap_{t=n}^{n+lN}B_{1}^{c})\}\leqq(1-\delta\epsilon_{n+N-1}^{N})\cdots(1-\delta\epsilon_{n+(l+1)N-1}^{N})\leqq e^{-\delta\Sigma_{i=1}^{1+1}\epsilon_{n+iN-1}^{N}}arrow$as, which implies thatfor all $n\geqq 1$ .
Thus, from (19) $P(W(i, a))=1$ , which implies $P(W)=1.\iota$
Proof of Lemma3.2
For each $i\in S$ and $a\in A$ , we show by induction thatfor some$m\geqq 1$ . By (i) of
Condition , there exists an integer $m$ for which (i) $>b_{m}$ for all $i\in S$
and $a\in A$ , such that it holds from (13) and the property of that$\phi(b_{m})=b_{\pi b+1}$ forand. For $n>1$ , it holds
from the assumption of the induction that.
Thus, from (i) of Condition , Lemma 3.1 shows that,forwhich means that
. By applying the law of large
numbers(cf. [2]), we get (i). Also, (ii) and (hi) follows clearly from
Proof of Theorem 3.2
Let. For each
, let
. Then, by the stability theorem(cf, [13]) we get
(20)
,
.
$0$

$Larrow\infty$$\lim_{Larrow\infty}P(\bigcap_{t=n}^{L}B_{t}^{\mathrm{c}})=P(\bigcap_{t=n}^{\infty}B_{t}^{c})=0$$\tilde{\pi}_{n}^{\tau}(a|\mathrm{i})\geqq b_{n+m}(n\geqq 1)$$\mathrm{A}$$\tilde{\pi}_{0}^{\tau}$$\phi$$a\neq\tilde{a}_{1}(\mathrm{i})$$\tilde{\pi}_{1}^{\tau}(a|\mathrm{i})=\phi(\tilde{\pi}_{0}^{\tau}(a|\mathrm{i}))>$$\tilde{\pi}_{1}^{\tau}(\tilde{a}_{1}(\mathrm{i})|\mathrm{i})>\tilde{\pi}_{0}^{\tau}(\tilde{a}_{1}(\mathrm{i})|i)>b_{m}>b_{m+1}$$\tilde{\pi}_{n+1}^{\tau}(a|\mathrm{i})\geqq\phi(\tilde{\pi}_{n}^{\tau}(a|i))\geqq\phi(b_{7\mathit{1}+m})=b_{7l+m+1}$$\mathrm{A}$$P_{\tilde{\pi}^{\tau}}(W|X_{0}=\mathrm{i}, q)=1$$q\in \mathbb{Q}^{*}$$\lim_{narrow\infty}N_{n}(i|a)=\infty P_{\tilde{\pi}^{\tau}}(\cdot|X_{0}=\mathrm{i}, q)- \mathrm{a}.\mathrm{s}$$(\mathrm{i}).\iota$$t\geqq 0$$q\in \mathbb{Q}^{*}$$\tilde{\delta}_{t}:=(1-\tau)\tilde{v}_{t}(X_{t})-\{r(X_{t}, \Delta_{t})+(1-\tau)\tilde{v}_{t}(X_{t+1})\}$ $\mathrm{a}\mathrm{n}\mathrm{d}\mathit{5}_{t}(j):=$$E_{\tilde{\pi}^{\tau}}(\tilde{\delta}_{t}|H_{t}, X_{t}=j, q)$$)$$\lim_{Tarrow\infty}\frac{1}{T+1}\sum_{t=0}^{T}\{\tilde{\delta}_{t}-\mathit{5}_{t}(X_{t})\}=0$

On the other hand, it holds that St{j). So, by (ii) and (iii) of Lemma 3.2,,
. Thus, from (20) it holds that

$P_{\overline{\pi}^{\tau}}(\cdot|X_{0}=\mathrm{i}, q)- \mathrm{a}.\mathrm{s}$$= \tilde{v}_{t}(j)-\sum_{a\in A}\{\{r(j, a)+(1-\tau)\sum_{k\in S}q_{jk}(a)\tilde{v}_{t}(k)\}$$\tilde{\pi}_{t}^{\tau}(a|j)\}-\tau\tilde{v}_{t}(j)$$i$$\lim_{tarrow\infty}5\mathrm{t}(\mathrm{j})=-\tau v_{\tau}(j, q)$,$P_{\overline{\pi}^{\tau}}(\cdot|X_{0}=$$q)- \mathrm{a}.\mathrm{s}$(21)$\min_{i\in S}-\tau v_{\tau}(\mathrm{i},q)\leqq$

Jim$\inf_{Tarrow\infty}\frac{1}{T+1}\sum_{t=0}^{T}\tilde{\delta}_{t}$$\leqq\lim\sup_{Tarrow\infty}\frac{1}{T+1}\sum_{t=0}^{T}\tilde{\delta}_{t}\leqq\max_{[]\in S}-\tau v_{\tau}(\mathrm{i}_{2}q)$

However,(ii) of Lemma 3.2 Jim(Jim in). Thus, applying Fatou’s Lemma, from (21) we get(22).

$\sum_{t=0}^{T}\tilde{\delta}_{t}=-\sum_{t=0}^{T}r(X_{t}., \Delta_{t})+(1-\tau)\sum_{t=0}^{T}(\tilde{v}_{t}(X_{\ell})-\tilde{v}_{t}(X_{t+1}))$$\sup_{Tarrow\infty}$$\mathrm{f}_{Tarrow\infty}$.

, so that by$\frac{1}{T+1}\sum_{t=0}^{T}\tilde{\delta}_{t}=\lim\sup_{Tarrow\infty}(\lim\inf_{Tarrow\infty})$-$\frac{1}{T+1}\sum_{t=0}^{T}r(X_{t}, \Delta_{t})$$\min_{i\in S}\tau v_{\tau}(i, q)\leqq\psi(\mathrm{i}, q|\tilde{\pi}^{\tau})\leqq\max_{[]\in S}\tau v_{\tau}(\mathrm{i}, q)$

By Lemma 1.2 and Theorem 2.1 (i),( , q)=${q), which implies from (22) thatas
. This completes the proof.
$\lim_{\tauarrow 0}\mathrm{r}\mathrm{v}\mathrm{T}$$\psi(i, q|\tilde{\pi}^{\tau})arrow\psi(q)$$\tauarrow 0$$\mathrm{i}$135
References[1] John Bather. Optimal decision proceduresfor finite Markov chains. II. Communicating systems. Advances in Appl. Probability, 5:521-540, 1973.

[2] Patrick Billingsley. Statistical inference
for Markov processes. Statistical Research
Monographs, Vol. II. The University of
Chicago Press, Chicago, 11., 1961.

[12] Arie Leizarowitz. An algorithm to identify and compute average optimal policies
in multichain Markov decision processes.
Math. Oper. Res., 28(3):553-586, 2003.
[13] Michel Loeve. Probability theory. Third
edition. D. Van Nostrand Co., Inc.,
Princeton, N.J .-Toronto, Ont.-London,

1963.

[14] P. Mandl. Estimation and control in
Markov chains. Advances in Appl. Proba[3] A. Federgruen and P. J. Schweitzer. Nonh.lity\rangle 6:40-60, 1974.
stationary Markov decision problems withconverging parameters. J. Optim. Theory[15] J. J. Martin. Bayesian decision problems
Appl., 34(2):207-241, 1981.
and Markov chains. Publications in Op[4] O. Hernandez-Lerma. Adaptive Markov
erations Research, No. 13. John Wiley &control processes, volume 79 of Applied
Sons Inc., New York, 1967.

Mathematical Sciences. Springer-Veriag,

New York, 1989.
[5] O. Hernandez-Lerma and S. I. Marcus.
Adaptive control of discounted Markov decision chains. J. Optim. Theory Appl.,
46(2):227-235, 1985.

[16] M. R. Meybodi and S. Lakshmivarahan.
optimality of a general class of learning algorithms. Info m. Sci., 28(1):1-20, 1982.
$\epsilon-$[17] Martin L. Puterman. Markov decision
processes: discrete stochastic dynamic
programming. John Wiley & Sons Inc.,[6] T. Iki, M. Horiguchi, and M. Kurano.
New York, 1994, A Wiley-Interscience
A structured pattern matrix algorithm
Publication.
for multichain markov decision processes.
(preprint), 2005.
[18] Sheldon M. Ross. Applied probability mod[7] John G. Kemeny and J. Laurie Snell. Finite Markov chains. The University Series in Undergraduate Mathematics. D.
Van Nostrand Co., Inc., Princeton, N.J.Toronto-London-New York, 1960.
[8] Masami Kurano. Discrete time Markovian
decision processes with an unknown parameter. Average return criterion, J. OP. Soc. Japan, 15:67-76, 1972.
erations${\rm Res}$els with optimization applications. HoldenDay, San Francisco, Calif., 1970.

[19] Paul J. Schweitzer. Perturbation theory
and finite Markov chains. J. Appl. Probability, 5:401-413, 1968.

[20] Eilon Solan. Continuity of the value ofcompetitive Markov decision processes. J.
Theoret. Probab., 16(4):831-845 (2004),

2003.

[9] Masami Kurano. Adaptive policies inMarkov decision processes with uncertain [21] Richard S. Sutton and Andrew G. Barto.
transition matrices. J. Inform. Optim.
Reinforcement Lear ning: An Introducu,$4(1):21-40$
1983.
Sci.,
tion. Adaptive Computation and Machine
Learning. MIT Press, Cambridge, MA,[10] Masami Kurano. Learning algorithms
1998.
for Markov decision processes. J. Appl.
Pro bab., 24(1):270-276, 1987.
Bayesian control of[22] K. M. van Hee.
Markov chains, volume 95 of Mathernat[11] S. Lakshmivarahan. Learning algorithms.
ical Centre Tracts. Mathematisch CenTheory
York,
1981.
New
Springer-Veriag,
Amsterdam, 1978
trum,
and applications.