\documentclass[reprint]{bic-art}
%
%   fig41_1.eps
%   fig42_1.eps
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 2007.03.02  minor revision

\usepackage{latexsym, amssymb, theorem, amsmath}
\usepackage{bm}  %   
\usepackage{array}
\usepackage{multirow}
\usepackage[dvips]{graphicx}  
\usepackage{float}
\usepackage{fancybox}
\usepackage{slashbox}

\newcommand{\calD}{{\mathcal D}}


\newcommand{\bQ}{\mathbb{Q}}

\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator*{\aM}{\mathrm{arg\,max}}

\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{df}{Definition}%%%%%%%%%%%[section]
\newtheorem{ex}{Example}%%%%%%%%%%%%%%[section]
\newtheorem{ass}{Assumption}%%%%%%%%%%[section]
\newtheorem{bthm}[thm]{Theorem}
\newtheorem{bdf}[df]{Definition}
\newtheorem{bcor}[cor]{Corollary}
\newtheorem{bprop}[prop]{Proposition}
\newtheorem{blem}[lem]{Lemma}
\numberwithin{equation}{section}  %%\usepackage{amsmath} 


\bicfirstauthor[Faculty of Education and Culture, Miyazaki University,
Miyazaki 889-2192 Japan, %
  % \tt  
e03101u@cc.miyazaki-u.ac.jp%
]{Tetsuichiro}{Iki}
\bicsecondauthor[General Education, Yuge National College of Maritime Technology, 
Ehime 794-2593 Japan, %
%tel +81-897-77-4678,  
%  \tt 
horiguchi@gen.yuge.ac.jp%
]{Masayuki}{Horiguchi}
\bicthirdauthor[Faculty of Science, Chiba University, %
  Chiba 263-8522 Japan, %
%  \tt 
yasuda@math.s.chiba-u.ac.jp%
]{Masami}{Yasuda}
\bicfourthauthor[Faculty of Education, Chiba University, Chiba 263-8522 Japan, %
%  \tt 
kurano@faculty.chiba-u.jp%
]{Masami}{Kurano}


\bictitle{A learning algorithm for communicating Markov decision processes 
  with unknown transition matrices}
\runningheader{A learning algorithm for communicating MDPs}
\bicvol{39}
%\bicno{99}
\bicyear{2007}

\bickeyword{
 Adaptive policy, Average case, Communicating case, Learning algorithm, Markov decision processes, 
 Reward-penalty type, Unknown transition matrix.
} 

%%%%%%    TEXT START    %%%%%%
\begin{document}
\maketitle   %-------------------------------------------

\begin{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.
\end{abstract}

\addtocounter{page}{10}

%%%%%%%%%%%%%% Sec. 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{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
\cite{Hern89, HeMa85, Kura72, Kura83, Mand74, Mart67, vanHee78}
 and so on.
The idea of Neuro dynamic programming by \cite{Bert96} 
is powerful in treating the adaptive MDPs.

However, a simple learning algorithm of the reward-penalty type,
investigated by \cite{Laks81} and \cite{MeLa82}
are more comprehensible and manageable.
\cite{Kura87} 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 \cite{Kura87} %extensively
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.

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 < \infty$ and $K < \infty$ elements respectively.
Let $\bQ$ denote the parameter space of $K$ unknown stochastic matrices, that is
\[
  \bQ=\Bigl\{ q=(q_{ij}(a)) \Bigm| q_{ij}(a)\geqq 0,\sum_{j\in S}q_{ij}(a)=1
  \ \text{for } i,j\in S, a\in A \Bigr\}.
\]

The sample space is the product space $\Omega=(S\times A)^{\infty}$ such that
the projections $X_t,\Delta_t$ on the $t$-th factors $S,A$ describe
the state and action at the $t$-th stage of the process$(t\geqq 0)$.
Let $\Pi$ denote the set of all policies, i.e., for 
$\pi=(\pi_0,\pi_1,\ldots)\in \Pi$, let $\pi_t\in P(A|(S\times A)^{t}\times S)$ for 
all $t\geqq 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 $\pi=(\pi_0,\pi_1,\ldots)$ is called randomized stationary
if a conditional probability $\gamma=(\gamma(\cdot|i):i\in S)\in
P(A|S)$ such that
$\pi_{t}(\cdot|x_0,a_0,\ldots,x_t)=\gamma(\cdot|x_t)$
for all $t\geqq 0$ and $(x_0,a_0,\ldots,x_t)\in (S\times A)^{t}\times S.$
Such a policy is simply denoted by $\gamma$.   
We denote by $F$ the set of  functions on $S$ with
$f(i)\in A$ for all $i\in S$.
A randomized stationary policy $\gamma$ is called stationary if
there exists a function $f\in F$ with $\gamma(\{f(i)\}|i)=1$ for all
$i\in S$, which is denoted simply by $f$.

We will construct a probability space as follows:
For any initial state $X_0=i, \pi \in \Pi$ and 
a transition law $q=(q_{ij}(a))\in \bQ$, let
$P(X_{t+1}=j|X_0, \Delta_0, \ldots, X_t=i, \Delta_t=a)
= q_{ij}(a)$
and 
$P(\Delta_{t}=a | X_0, \Delta_0, \ldots, X_t=i) = 
\pi_t(a|X_0, \Delta_0, \ldots, X_t=i)\ 
(t\geqq 0).$
Then, we can define the probability measure 
$P_{\pi}(\cdot | X_0=i,q)$ on $\Omega$.
%
For a given reward function $r$ on $S\times A$, we shall consider
the long-run expected average reward:
\begin{equation}
  \psi(i,q|\pi)=
  \liminf_{T\to\infty}\frac{1}{T+1}E_{\pi}\Bigl(
  \sum_{t=0}^{T}r(X_{t},\Delta_{t})\Bigm|X_0=i,q
  \Bigr)
\label{eq(1.1)}
\tag{1.1}
\end{equation}
where $E_{\pi}(\cdot|X_0=i,q)$ is the expectation operator
with respect to $P_{\pi}(\cdot|X_0=i,q)$.

Let $\calD$ be a subset of $\bQ$. Then, the problem is to maximize
$\psi(i,q|\pi)$ over all $\pi\in \Pi$ for any $i\in S$ and $q\in \calD$.
Thus, denoting the optimal value function as
\begin{equation}
  \psi(i,q)=\sup_{\pi\in\Pi}\psi(i,q|\pi),
\label{eq(1.2)}
\tag{1.2}
\end{equation}
a policy $\pi^{*}\in\Pi$ will be called $q$-optimal if
$\psi(i,q|\pi^{*})=\psi(i,q)$ for all $i\in S$
and called adaptively optimal for $\calD$ if 
$\pi^{*}$ is $q$-optimal for all $q\in \calD$.
A sequences of policies $\{\pi^{n}\}_{n=1}^{\infty}\subset \Pi$
is called an asymptotic sequence of adaptive policies
with nearly optimal properties for $\cal D$ if
\[
  \lim_{n\to \infty}\psi(i,q|\pi^{n})=\psi(i,q)
  \ \text{ for all $q\in \calD$}.
\]
In \cite{Kura87}, an adaptively optimal policy for 
$ \bQ^{+} := \{ q = (q_{ij}(a)) \in \bQ
  \bigm| q_{ij}(a)>0 \text{ for all $i,j \in S$ 
  and $a\in A$} \}$
was constructed
%a learning algorithm of the reward-penalty type
%\citeaffixed{Laks81}{cf.} 
%(cf.\ \cite{Laks81}) 
by applying the value iteration and the policy improvement algorithm
(cf.\ \cite{Laks81, FeSc81, Hern89, HeMa85}).
In this paper, we treat with the communicating case of multi-chain MDPs
applying the idea of \cite{Kura87} extensively.

A transition matrix $q=(q_{ij}(a))\in\bQ$ is said communicating 
%\citeaffixed{Bath73,IHK05,Pute94}{cf.}
(cf.\ \cite{Bath73}, %IHK05,
%Pute94}
Puterman (1994))
if for any $i,j\in 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)\cdots q_{i_{l-1}i_{l}}(a_{l-1})>0
\]
for some $\{i_1=i,i_2,\ldots,i_l=j\}\subset S$ and $\{a_1,a_2,\ldots,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 
$\gamma=(\gamma(\cdot|i):i\in S)$ satisfying that
the transition matrix $q(\gamma)=(q_{ij}(\gamma))$ induced by $\gamma$
defines an irreducible Markov chain
%\citeaffixed{KmSn60}{cf.} 
(cf.\ \cite{KmSn60})
where 
$q_{ij}(\gamma)=\sum_{a\in A}q_{ij}(a)\gamma(a|i)$ for $i,j\in S.$

Let $B(S)$ be the set of all functions on $S$.
The following fact is well-known
%\citeaffixed{Pute94,Ross70}{cf.}.
(cf.\ \cite{Pute94,Ross70}).
%\harvardparenthesis{non}
\begin{lem}[\cite{Pute94,Ross70}]
Let $q=(q_{ij}(a))\in\bQ.$
Supposed that there exists a constant $g$ and a $v\in B(S)$ such 
that, for all $i\in S$,
\begin{equation}
  v(i)=\max_{a\in A}\Bigl\{
        r(i,a)+\sum_{j\in S}q_{ij}(a)v(j)
       \Bigr\} - g.
\label{eq(1.3)}
\tag{1.3}
\end{equation}
Then, $g$ is unique and $g=\psi(i,q)=\psi(i,q|f)$ for $i\in S$,
where $f\in F$ is $q$-optimal and $f(i)$ is a maximizer in the right-hand side
of (1.3) for all $i\in S$.
\end{lem}
%\harvardparenthesis{round}

Let $\bQ^{*}$ be the set of all communicating transition matrices. 
In order to treat with the communicating case with $q\in \bQ^{*}$, 
we use the so-called vanishing discount approach which studies the average case
by considering the corresponding $(1-\tau)$-discounted one as letting
$\tau\to 0$.
The expected total $(1-\tau)$-discounted reward is defined by
\begin{equation}
  v_{\tau}(i,q|\pi)=E_{\pi}\Bigl(
    \sum_{t=0}^{\infty}(1-\tau)^{t}r(X_{t},\Delta_{t})\Bigm| X_0=i,q
    \Bigr)
\label{eq(1.4)}
\tag{1.4}
\end{equation}
for $i\in S,q\in \bQ$ and $\pi\in \Pi$,
and 
$v_{\tau}(i,q)=\sup_{\pi\in\Pi}v_{\tau}(i,q|\pi)$
is called a $(1-\tau)$-discounted value function, 
where $(1-\tau)\in (0,1)$ is a given discount factor.

For any $q=(q_{ij}(a))\in \bQ$ and $\tau \in (0,1)$,
we define the operator $U_{\tau}\{q\}:B(S)\to B(S)$ by
\begin{equation}
  U_{\tau}\{q\}u(i) = \max_{a\in A}\Bigl\{r(i,a) + (1-\tau) \sum_{j\in S}q_{ij}(a)u(j)\Bigr\}
\label{eq(1.5)}
\tag{1.5}
\end{equation}
for all $i\in S$ and $u\in B(S)$.
We have the following.

%\harvardparenthesis{non}
\begin{lem}[\cite{Pute94, Ross70}]
It holds that
\begin{itemize}
  \item[\rm (i)] the operator $U_{\tau}\{q\}$ is a contraction with
      the modulus $(1-\tau)$,
  \item[\rm (ii)] the $(1-\tau)$-discount value function $v_{\tau}(i,q)$ is a unique
      fixed point of $U_{\tau}\{q\}$, i.e.,
  \begin{equation}
         v_{\tau}=U_{\tau}\{q\}v_{\tau},
      \label{eq(1.6)}
      \tag{1.6}
  \end{equation}
  \item[\rm (iii)] $v_{\tau}(i,q)=v_{\tau}(i,q|f_{\tau})$ and 
      $\displaystyle\lim_{\tau\to 0}\tau
      v_{\tau}(i,q)=\psi(i,q),$ 
      where $f_{\tau}$ is a maximizer of the right-hand side in {\rm (1.6)}.
\end{itemize}
\end{lem} 
%\harvardparenthesis{round}

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%% sec. 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{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.
\begin{lem}
Let $q=(q_{ij}(a))\in \bQ^{*}$. Then, there exists a constant $M$ such that
\begin{equation}
  \limsup_{\tau\to 0}\bigm|v_{\tau}(i,q)-v_{\tau}(j,q) \bigm|\leqq M
  \ \ \text{for all \ $i,j\in S$}.
\label{eq(2.1)}
\tag{2.1}
\end{equation}
\end{lem}
%
\noindent{\it Proof.}
We denote by $H_{t}:=(X_0,\Delta_0,\ldots,X_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 time $\sigma^{j}$ by
\[
  \sigma^{j} = \sigma^{j}(H_t) = \text{first $t\geqq 0$ such that $X_t=j$.}
\]
That $q\in Q^{*}$ guarantees that there exists a randomized stationary policy
$\gamma=(\gamma(\cdot|i):i\in S)$ such that the Markov chain induced by
$q(\gamma)$ is irreducible.
Here, using the stationary policy $f_\tau$ given in Lemma 1.2 the policy
$\pi^{j}=(\pi^{j}_0,\pi^{j}_1,\ldots)$ will be defined by
\[
  \pi^{j}_{t}(\cdot|H_t)=
   \begin{cases}
     \gamma(\cdot|X_t) & \text{if $t<\sigma^{j}(H_t)$,}\\
     f_{\tau}(X_{t}) & \text{if $t\geqq \sigma^{j}(H_t)$}.
   \end{cases}
\]
for $ t\geqq 0$. 
Then we have the following:  For $i \in S$,
\begin{multline}
  v_{\tau}(i,q|\pi^{j})
  = E_{\gamma}\Bigl(\sum_{t=0}^{\sigma^{j}-1}(1-\tau)^{t}r(X_t,\Delta_t)
    \Bigm| X_0=i,q\Bigr)\\
   + E_{\gamma}\Bigl((1-\tau)^{\sigma^{j}}\Bigm| X_0=i,q\Bigr)v_{\tau}(j|q).
\label{eq(2.2)}
\tag{2.2}
\end{multline}
From irreducibility of the Markov chain induced by $q(\gamma)$, 
it holds
%\citeaffixed{KmSn60}{cf.} 
(cf.\ \cite{KmSn60})
that
\begin{equation}
  E_{\gamma}\Bigl(\sigma^{j}\bigm| X_0=i,q\Bigr)<\infty 
   \ \ \text{for all \ $i\in S$}.
\label{eq(2.3)}
\tag{2.3}
\end{equation}
Concerning with the second term of the right-hand side in (2.2),
since $\lim_{\tau\to 0}\frac{(1-\tau)^n-1}{\tau}=-n \ (n\geqq 1),$
we have that
 \begin{align*}   %%%%  *
  &\liminf_{\tau\to 0}\frac{1}{\tau}\Bigl\{E_{\gamma}\Bigl((1-\tau)^{\sigma^{j}}\Bigm|
  X_0=i,q\Bigr)-1\Bigr\} \\ 
  \geqq&\sum_{n=0}^{\infty}\liminf_{\tau\to0}\frac{(1-\tau)^n-1}{\tau}
  P  _{\gamma}\Bigl(\sigma^{j}=n\bigm| X_0=i,q\Bigr) \\
  =&-\sum_{n=1}^{\infty}nP_{\gamma}\Bigl(\sigma^{j}=n\bigm| X_0=i,q\Bigr)
  =-E_{\gamma}\Bigl(\sigma^{j}\bigm|X_0=i,q\Bigr). \tag{2.4}
 \end{align*}
\noindent
On the other hand, from (2.2) it holds that
\begin{align*}
  v_{\tau}(i,q)-v_{\tau}(j,q)&\geqq v_{\tau}(i,q|\pi^{j})-v_{\tau}(j,q)\\
  &\geqq -\lVert r \rVert E_{\gamma}\Bigl(\sigma^{j}\bigm| X_0=i,q\Bigr)
  +\Bigl\{E_{\gamma}\Bigl((1-\tau)^{\sigma^{j}}\bigm| X_0=i,q\Bigr)-1\Bigr\}
  v_{\tau}(j,q)
\end{align*}
where $\lVert r \rVert=\max_{i\in S,a\in A}\lvert r(i,a)\rvert$.
Thus, by (2.2), (2.4) and Lemma 1.2(iii) we have that
\begin{align*}
  \liminf_{\tau\to 0}
  \Bigl(v_{\tau}(i,q)-v_{\tau}(j,q)\Bigr)
  &\geqq -\limsup_{\tau\to 0}\Bigl(\lVert r\rVert+\lvert\tau v_{\tau}(j,q)\rvert\Bigr)E_{\gamma}\Bigl(\sigma^{j}\bigm| X_0=i,q\Bigr)\\
  &=-\Bigl(\lVert r\rVert+\lvert\psi(j,q)\rvert\Bigr)E_{\gamma}\Bigl(\sigma^{j}|X_0=i,q\Bigr)>-\infty.
\end{align*}
Similarly, 
we get that
\begin{align*}
  \liminf_{\tau\to 0}
  \Bigl(v_{\tau}(j,q)-v_{\tau}(i,q)\Bigr)
  \geqq-\Bigl(\lVert r\rVert+\lvert\psi(i,q)\rvert\Bigr)E_{\gamma}\Bigl(\sigma^{i}|X_0=j,q\Bigr)>-\infty,
\end{align*}
and hence
\begin{align*}
  \limsup_{\tau\to 0}
  \Bigl|v_{\tau}(i,q)-v_{\tau}(j,q)\Bigr|
  \leqq\Bigl(\lVert r\rVert+\lvert\psi(i,q)\rvert\Bigr)E_{\gamma}\Bigl(\sigma^{i}|X_0=j,q\Bigr)<\infty.
\end{align*}
If we put $M:=\max_{i,j\in S}\Bigl(\lVert r\rVert +\lvert\psi(j,q)\rvert\Bigr)E_{\gamma}\Bigl(
\sigma^{j}\bigm| X_0=i,q\Bigr),$ (2.1) follows, which completes the proof.\qed
\medskip

Let $P(S)$ be the set of all probability distributions on $S$, i.e.,
\[
  P(S)=\Bigl\{
  \mu = (\mu_1,\mu_2,\ldots,\mu_N)\bigm|\mu_i\geqq 0, \sum_{i=1}^{N}\mu_i=1 \ \text{for all \ $i\in S$}
  \Bigr\}.
\]
Let $q=(q_{ij}(a))\in \bQ$.
For any $\tau\in (0,1)$ and $\mu=(\mu_1,\mu_2,\ldots,\mu_N)\in P(S)$,
we perturb $q$ to $q^{\tau,\mu}=(q_{ij}^{\tau,\mu}(a))$
which is defined by
\begin{equation}
  q_{ij}^{\tau,\mu}(a)=\tau \mu_j+(1-\tau)q_{ij}(a)\ \ \text{for $i,j\in S$ and $a\in A$}.
\label{eq(2.5)}
\tag{2.5}
\end{equation}
The matrix expression of (2.5) is $q^{\tau,\mu}=\tau e\mu + (1-\tau) q,$
where $e=(1,1,\ldots,1)^{t}$ is a transpose of $N$-dimensional vector $(1,1,\ldots,1)$.
Then, we find that (1.6) in Lemma 1.2 can be rewritten as follows:
For all $i\in S$,
\begin{equation}
  v_{\tau}(i,q)=\max_{a\in A}\Bigl\{ r(i,a)+\sum_{j\in S}q_{ij}^{\mu,\tau}(a)v_{\tau}(j,q)\Bigr\}
  -\tau\sum_{j\in S}\mu_jv_{\tau}(j,q).
\label{eq(2.6)}
\tag{2.6}
\end{equation} 
Thus, applying Lemma 1.1, we have the following.
\begin{lem}
For any $q\in\bQ,\tau\in (0,1)$ and $\mu\in P(S),$ it holds that
\begin{itemize}
  \item[\rm (i)] $\displaystyle\psi(i,q^{\tau,\mu})=\tau\sum_{j\in S}\mu_{j}v_{\tau}(j,q)$  
   for all $i\in S$,\vspace{-1.5ex}
  \item[\rm (ii)] $f_{\tau}$ is $q^{\tau,\mu}$-optimal, where $f_{\tau}$ is given 
   in Lemma 1.2. 
\end{itemize}
\end{lem}
\medskip

From Lemma 2.2, since $\psi(i,q^{\tau,\mu})$ is independent of $i\in S$, we shall put
$\psi(q^{\tau,\mu}):=\psi(i,q^{\tau,\mu}).$
The $\tau$-continuity of $\psi(q^{\tau,\mu})$ is given in the following.
\begin{thm}\label{Thm2.1}
Let $q\in \bQ^{*}.$ Then, we have that
\begin{itemize}
  \item[\rm (i)]
   $\psi(i,q)(:=\psi(q))$ is independent of $i\in S$ and there exists 
    a $u\in B(S)$ satisfying the average optimality equation:
   \begin{equation}
    u(i) = 
   \max_{a\in A}\Bigl\{r(i,a)+\sum_{j\in S}q_{ij}(a)u(j)\Bigr\}-\psi(q)\ \ (i\in S),
  \label{eq(2.7)}
  \tag{2.7}
  \end{equation}
 \item[\rm (ii)] 
  for any $\mu\in P(S),\psi(q^{\mu,\tau})\to \psi(q)\ \text{as }\tau\to0.$
\end{itemize}
\end{thm}
%
\noindent{\it Proof.}
For any fixed $i_0\in S$, let $u_{\tau}(i)=v_{\tau}(i,q)-v_{\tau}(i_0,q)$
for each $i\in S$.
Then, from (2.6) we get
\begin{equation}
  u_{\tau}(i)=\max_{a\in A}\Bigl\{r(i,a)+\sum_{j\in S}q_{ij}^{\mu,\tau}(a)u_{\tau}(j)\Bigr\}
  -\tau\sum_{j\in S}\mu_{j}v_{\tau}(j,q)\ \ (i\in S).
\label{eq(2.8)}
\tag{2.8}
\end{equation}
By Lemma 1.2, $\lim_{\tau\to 0}\tau v_{\tau}(j,q)=\psi(j,q).$
Also, from Lemma 2.1, there exists a sequence $\{\tau_{l}\}$ with $\tau_{l}\to 0$ and 
$u_{\tau_{l}}(j)\to u(j)$ as $l\to \infty$ for some $u\in B(S)$ and all $j\in S$.
Thus, letting $l\to \infty$ in (2.8) with $\tau=\tau_{l},$ we get (2.7)
with $\psi(q)=\sum_{j\in S}\mu_{j}\psi(j,q)$.
Applying Lemma 1.1, we observe that $\psi(q)$ is independent of $\mu\in P(S)$,
so that (i) and (ii) follows.\qed
\medskip

We note that (i) in Theorem 2.1 derives the single average optimality equation
for the communicating MDPs, which has been given first by 
\cite{Bath73}.
In general, the value function $\psi(i,q)$ is known to be continuous on each
equivalent class of $\bQ$
(cf.\ \cite{Sc68,So03}),
but (ii) in Theorem 2.1 gives an example in which 
$\psi(i,q)$ is continuous in $q$ across the equivalent classes.

%%%%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Learning algorithms and analysis}
  In this section, we give a learning algorithm of reward-penalty
type for MDPs with the transition matrices $q\in \bQ^{*}$,
by which the adaptive policy is constructed.
%
For any $i\in S$ and $a \in A$, a sequence of stopping times
$\{\sigma^{n}(i,a)\}_{n=0}^{\infty}$ will be defined as follows.
\begin{equation}
  \sigma^{0}(i,a)=0,\sigma^{n}(i,a)=\inf\{
  t\vert t>\sigma^{n-1}(i,a),X_t=i,\Delta_t=a\}\ (n\geqq 1).
\label{eq(3.1)}
\tag{3.1}
\end{equation}
Let $ W:=\bigcap_{(i,a)\in S\times A}W(i,a),$ where 
$ W(i,a)=\bigcap_{n=1}^{\infty}
\{\sigma^{n}(i,a)<\infty\}.$
We note that $\omega\in W$ means that for any $(i,a)\in S\times A$ the event 
$\{X_{t}(\omega)=i,\Delta_{t}(\omega)=a\}$
happens in infinitely many stages.

The following is an extension of Lemma 1 in \cite{Kura83} 
to the communicating case.
\begin{lem}
  Let a policy $\pi=(\pi_0,\pi_1,\ldots)$ and
a decreasing sequence of positive numbers
$\{\varepsilon_{t}\}_{t=0}^{\infty}$
satisfy that
\begin{itemize}
 \item[\rm (i)]
  for each $t\geqq 0, 
  \pi_{t}(a|h_t) \geqq \varepsilon_{t}$ 
  with $a\in A$ and $h_t=(x_0,a_0,\ldots,x_t)\in H_t$,
 \item[\rm (ii)]
  $\displaystyle\sum_{t=0}^{\infty}\varepsilon_{t}^{N}=\infty.$
\end{itemize}
Then, $P_{\pi}(W\!\bigm|X_0=i,q)=1$ for all $q\in \bQ^{*}$ and $i \in S$.
\end{lem}
%
\noindent{\it Proof.}
For notation simplicity, for any fixed $q\in \bQ^{*}$
we put $P(\cdot)=P_{\pi}(\cdot|X_0=i,q)$.
From the definition of the communicating MDPs and (i) in Lemma 3.1, 
we have that there exists $\delta>0$ such that
\begin{equation}
  P(X_{t}=i, \Delta_{t}=a \ \text{for some $t$ with $n\leqq t 
   \leqq n + N\vert H_{n})$} 
   \geqq \delta \varepsilon_{n+N}^{N}
  \label{eq(3.2)}
  \tag{3.2}
\end{equation}
for any $n\geqq 0$ and $i\in S,a\in A$.
For any fixed $i\in S,a\in A$, 
let $B_{t} := B_t(i,a) := \{\sigma^{n}(i,a)=t\ \text{for some $n\geqq 1$} \}.$
Then, we observe that 
$W(i,a) 
  = \limsup_{t\to\infty}B_t(i,a) 
  = \Bigl(\liminf_{t\to\infty}B_{t}^{c}(i,a)\Bigr)^{c}$, 
so that it holds that
\begin{equation}
  P(W(i,a)) = 1 - P(\liminf_{t\to\infty} B_t^{c}(i,a)).
\label{eq(3.3)}
\tag{3.3}
\end{equation}
For any positive integer $L$ with $L>n$, let
$l:=\Bigl[{(L-n+1)}/{N}\Bigr]-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
\begin{align*}
  &  P\Bigl(\bigcap_{t=n}^{L}B_{t}^{c}(i,a)\Bigr) \\ 
  & \leqq  P\Bigl(\bigcap_{\alpha=0}^{l}
  \bigcap_{t=n+\alpha N}^{n+(\alpha+1)N-1}B_{t}^{c}(i,a)\Bigr)\\
  & \leqq \Bigl\{1-P\Bigl(\bigcup_{t=n}^{n+N-1}B_{t}(i,a)\Bigr)\Bigr\}\cdots
  \Bigl\{1-P\Bigl(\bigcup_{t=n+lN}^{n+(l+1)N-1}B_{t}(i,a)
  \Bigg\vert\bigcap_{t=n}^{n+lN-1}B_{t}^{c}(i,a)\Bigr)\Bigr\}\\
  & \leqq \Bigl(1-\delta\varepsilon_{n+N-1}^{N}\Bigr)
  \cdots\Bigl(1-\delta\varepsilon_{n+(l+1)N-1}^{N}\Bigr)\\
  & \leqq \exp\{-\delta\sum_{i=1}^{l+1}\varepsilon_{n+iN-1}^{N}\}
  \to 0 \ \text{as $L\to \infty$},
\end{align*}
which implies that
$\lim_{L\to \infty}P\Bigl(\bigcap_{t=n}^{L}B_{t}^{c}(i,a)\Bigr)
 =P\Bigl(\bigcap_{t=n}^{\infty}B_{t}^{c}(i,a)\Bigr)=0$ 
for all $n\geqq 1$.
Thus, from (3.3) $P(W(i,a))=1$, which implies $P(W)=1$.\qed

We note that a sequence $\{1/(t+1)^{1/N}\}_{t=0}^{\infty}$
satisfies (ii) of Lemma 3.1 as an example. 

For each $i,j\in S$ and $a\in A$, 
let $N_{n}(i,j|a)=\sum_{t=0}^{n}I_{\{X_t=i,\Delta_t=a,X_{t+1}=j\}}$
and $N_{n}(i|a)=\sum_{t=0}^{n}I_{\{X_t=i,\Delta_{t}=a\}}$,
where $I_{D}$ is the indicator function of a set $D$.
Let
\[
q^{n}_{ij}(a)=\begin{cases}
\dfrac{N_{n}(i,j|a)}{N_{n}(i|a)}& \text{if $N_{n}(i|a)>0$,}\\
0 & \text{otherwise}.
\end{cases}
\]
Then, $q^{n}_{ij}=(q^{n}_{ij}(a))$ is 
the maximum likelihood estimator of the unknown transition matrices.
For any given $q^{0}=(q^{0}_{ij}(a))\in \bQ$,
we define $\tilde{q}^{n}=(\tilde{q}^{n}_{ij}(a))\in \bQ$ by
\[
  \tilde{q}^{n}_{ij}(a)=
   \begin{cases}
    q^{n}_{ij}(a) & \text{if $N_{n}(i|a)>0$,}\\
    q^{0}_{ij}(a) & \text{otherwise}.
   \end{cases}
\]

We consider the following iterative scheme which is a variant of 
the non-stationary value iteration scheme proposed by
\cite{FeSc81}:
\begin{equation}
  \tilde{v}_{0}=0, \quad 
  \tilde{v}_{n+1}=U_{\tau}\{\tilde{q}^{n}\}\tilde{v}_{n}\ \ (n\geqq 0)
\label{eq(3.4)}
\tag{3.4}
\end{equation}
for any $\tau \in (0,1)$.
For each $i\in S$ and $n(n\geqq 0)$, let $\tilde{a}_{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}^{\infty}$ of positive numbers with
$b_0=1,0<b_{n+1}<1$ and $b_{n}>b_{n+1}$ for all $n\geqq 0$,
let $\phi$ be any strictly increasing function such that
$\phi:[0,1]\to[0,1]$ and $\phi(b_n)=b_{n+1}$ for all $n\geqq 0$.

Here, we define a learning algorithm based on
$\tilde{a}_{n+1}$ and $\phi$.
For each $n(n\geqq 0)$, letting
$\tilde{\pi}_{n}^{\tau}(a|i)=P(\Delta_n=a|X_0,\Delta_0,\ldots,X_n=i)$
we propose to update $\tilde{\pi}_{n}^{\tau}$ as follows:\\
if $\tilde{a}_{n+1}(i) = a_{i}$ for each $i\in S$, 
\begin{equation}
 \begin{array}{ll}
  \tilde{\pi}_{n+1}^{\tau}(a_i|i) & =  1-\sum_{a\neq a_i}\phi (\tilde{\pi}_{n}^{\tau} (a|i)), \\
  \tilde{\pi}_{n+1}^{\tau}(a |i) & = \phi (\tilde{\pi}_{n}^{\tau}(a |i)) \ (a \neq a_i).
 \end{array}
\label{eq(3.5)}
\tag{3.5}
\end{equation}
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 $\tilde{\pi}_{0}^{\tau},
\tilde{\pi}^{\tau}=(\tilde{\pi}_{0}^{\tau},\tilde{\pi}_{1}^{\tau},\ldots)\in\Pi$
and $\tilde{\pi}_{n}^{\tau}\ (n\geqq 1)$ is successively determined
by (3.4) and (3.5).

We need the following condition.
\bigskip

\noindent
{\bf Condition A.} \vspace{-.5ex}
\begin{itemize}
  \item[(i)] $b_n\to 0$ as $n\to \infty$ and $\sum_{n=0}^{\infty}
   b_{n}^{N}=\infty,$ \\[-2.5ex]
  \item[(ii)] $\tilde{\pi}_{0}^{\tau}(a|i)>0$ for all $i\in S, a\in A$.
\end{itemize}

Under this condition, the following lemma is proved similarly as Lemma 3 and 4
 in \cite{Kura87}, so the proof is omitted.
\begin{lem}
 Let $q\in \bQ^{*}.$ Then, under Condition A, the following (i)--(iii) holds
 with $P_{\tilde{\pi}^{\tau}}(\cdot|X_0=i,q)$-a.s.:%probability 1:
 \begin{itemize}
  \item[\rm (i)] $\tilde{q}^{n} \to q$ as $n\to \infty$, \vspace{-1.0ex}
  \item[\rm (ii)] $\tilde{v}_{n}(i)\to v_{\tau}(i,q)$ as $n\to \infty$,\vspace{-1.0ex}
  \item[\rm (iii)] $\tilde{\pi}^{\tau}_{n}(A^{*}_{\tau}(i|q)\vert H_n,X_n=i)
    \to 1$ as $n\to \infty$, 
 \end{itemize}
 where $A^{*}_{\tau}(i|q)$ is the set of all actions which maximize
 the right-hand side of {\rm (1.6)}.
\end{lem}

Let $\sideset{^{\tau}}{^{*}}\Q:=\{q^{\tau,\mu}\vert 
\mu\in P(S) \ \text{and} \ q\in \bQ^{*}\},$
where $q^{\tau,\mu}$ is defined in (2.5).
Then, observing the discussion in Section 2 and
$\sideset{^{\tau}}{^{*}}\Q\subset \bQ^{*},$ 
from Lemma 3.2 we find that
the results in \cite{Kura87} can be applicable to
the class of perturbed transition matrices $\sideset{^{\tau}}{^{*}}\Q.$
So, we have the following.
\begin{thm}
  Under Condition A, $\tilde{\pi}^{\tau}$ is adaptively optimal
  for $\sideset{^{\tau}}{^{*}}\Q.$
\end{thm}
Here we can state the following theorem for the 
communicating case.
\begin{thm}
  Under Condition A, a sequence $\{\tilde{\pi}^{\tau_{n}}\}_{n=1}^{\infty}$
  with $\tau_{n}\to 0$ as $n\to \infty$ is an asymptotic sequence of
  adaptive policies with nearly optimal properties for
  $\bQ^{*}$.
\end{thm}
\noindent{\it Proof.}
Let $q\in \bQ^{*}$.
For each $t\geqq 0$, let
\[
  \begin{split}
   \tilde{\delta}_{t}&:=(1-\tau)\tilde{v}_{t}(X_{t})-
   \{r(X_{t},\Delta_{t})+(1-\tau)\tilde{v}_{t}(X_{t+1})\}
   \ \text{and}\\
   \delta_{t}(j)&:=E_{\tilde{\pi}^{\tau}}(\tilde{\delta}_{t}\vert 
   H_t,X_t=j,q).
   \end{split}
\]
Then, by the stability theorem
%\citeaffixed{Lo63}{cf.},
(cf.\ \cite{Lo63}),
we get
\begin{equation}
  \lim_{T\to\infty} \frac{1}{T+1}\sum_{t=0}^{T}\{\tilde{\delta}_t-\delta_{t}(X_t)\}
  =0,\ P_{\tilde{\pi}^{\tau}}(\cdot|X_0=i,q)\text{-a.s.} 
\label{eq(3.6)}
\tag{3.6}
\end{equation}
On the other hand, it holds that
\[
  \delta_{t}(j)=\tilde{v}_{t}(j)
  -\sum_{a\in A}\Bigl\{r(j,a)+(1-\tau)\sum_{k\in S}q_{jk}(a)\tilde{v}_{t}(k)\Bigr\}
  \tilde{\pi}_{t}^{\tau}(a|j)-\tau\tilde{v}_{t}(j).
\]
So, by (ii) and (iii) of Lemma 3.2,
\[
  \lim_{t\to \infty}\delta_{t}(j)=-\tau v_{\tau}(j,q),\ \
  P_{\tilde{\pi}^{\tau}}(\cdot\vert X_0=i,q)\text{-a.s.} 
\]
Thus, from (3.6) it holds that
\begin{equation}
  \begin{split}
  \min_{i\in S} \{   -\tau v_{\tau}(i,q) \}
  & \leqq \liminf_{T\to\infty}\frac{1}{T+1}\sum_{t=0}^{T}\tilde{\delta}_{t}\\
  & \leqq \limsup_{T\to\infty}\frac{1}{T+1}\sum_{t=0}^{T}\tilde{\delta}_{t}
    \leqq \max_{i\in S} \{ -\tau v_{\tau}(i,q) \}.
  \end{split}
\label{eq(3.7)}
\tag{3.7}
\end{equation}
However, we have
\[
  \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_t)-\tilde{v}_{t}(X_{t+1}))
\]
by the definition. The second term in the right-hand-side is rewritten as
\[
  (1-\tau) \Bigl\{ \tilde{v}_{0}(X_0) + 
   \sum_{t=1}^{T} (\tilde{v}_{t}(X_t)-\tilde{v}_{t-1}(X_{t}) ) 
   - \tilde{v}_{T}(X_{T+1}) \Bigr\}
\]
so by (ii) of Lemma 3.2,
\[
  \limsup_{T\to \infty}\Bigl(\liminf_{T\to \infty}\Bigr)\frac{1}{T+1}\sum_{t=0}^{T}
  \tilde{\delta}_{t}
  =
  \limsup_{T\to \infty}\Bigl(\liminf_{T\to \infty}\Bigr)
  \Bigl\{ -\frac{1}{T+1}\sum_{t=0}^{T}
  r(X_t,\Delta_t)\Bigr\}
\]
respectively.
Thus, applying Fatou's Lemma, from (3.7) we get
\begin{equation}
  \min_{i\in S}\tau v_{\tau}(i,q)\leqq
  \psi(i,q|\tilde{\pi}^{\tau})\leqq \max_{i\in S}\tau v_{\tau}(i,q).
\label{eq(3.8)}
\tag{3.8}
\end{equation}
By Lemma 1.2 and Theorem 2.1 (i), 
$\lim_{\tau\to 0}\tau v_{\tau}(i,q)=\psi(q)$,
which implies from (3.8) that
$\psi(i,q|\tilde{\pi}^{\tau})\to \psi(q)$
as $\tau \to 0$.
This completes the proof.\qed

\vspace{2.5ex}
We summarize our learning algorithm for constructing 
adaptive  policy $\tilde{\pi}^{\tau}$ as follows:

\vspace{-1.5ex}
\begin{figure}[h]
\fbox{%
\hspace*{.01\textwidth}%
\begin{minipage}{0.98\textwidth}%
\begin{Bitemize}
  \item[Step 1.] Set $n=0$. Specify $\tau\; (0<\tau<1)$.
   Choose $\tilde{\pi}_{0}^{\tau}(a|i)$ which satisfies (ii) in \\
   Condition A. Select $q^{0}_{ij}(a)$ arbitrarily and define $\tilde{v}_{0}(i)=0\ (i\in S)$. 
  \item[Step 2.] If $X_n=i$, choose an action $a_i\in A(i)$ from 
   the decision rule $\tilde{\pi}_{n}^{\tau}.$\\
   Observe the next state $X_{n+1}=j$ and calculate $N_{n}(i,j|a)$ and $N_{n}(i|a)$.
  \item[Step 3.] Set\\
   \hspace*{6mm}$\displaystyle
   \tilde{q}^{n}_{ij}(a)=\begin{cases}{N_{n}(i,j|a)}/{N_{n}(i|a)}&\text{if $N_{n}(i|a)>0$}\\
   q^{0}_{ij}(a) & \text{otherwise.}
   \end{cases}
   $
  \item[Step 4.] Choose $\tilde{a}_{n+1}(i)$ which satisfies\\
   \hspace*{6mm}$\displaystyle
   \tilde{a}_{i} := \tilde{a}_{n+1}(i)\in \aM_{a\in A}\Bigl\{r(i,a)+(1-\tau)\sum_{j\in S}\tilde{q}^{n}_{ij}(a)
   \tilde{v}_{n}(j)\Bigr\}.
   $
  \item[Step 5.] Update $\tilde{\pi}_{n+1}^{\tau}(i) \ (i\in S)$ by\\
   \hspace*{6mm}$\displaystyle
   \tilde{\pi}_{n+1}^{\tau}(\alpha |i)=\phi \left(\tilde{\pi}_{n}^{\tau}(\alpha |i)\right) \ (\alpha\neq \tilde{a}_i),
   \text{ and }
   \tilde{\pi}_{n+1}^{\tau}(\tilde{a}_i|i)=1-\sum_{\alpha\neq \tilde{a}_i}
   \phi \left(\tilde{\pi}_{n}^{\tau}(\alpha |i)\right).
   $
  \item[Step 6.] Set $n=n+1$ and return to Step 2.
\end{Bitemize}
\end{minipage}
}%
\caption{Learning Algorithm for vanishing rate $\tau$.}%
\end{figure}


%%%%%%%%%%%%%%%%%%%%%% sec. 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{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\in S, a\in A)$ are given
in Table 4.1 and Figure 4.1.

\begin{table}[htbp]
\small
\begin{center}
\label{Table4.1}
\begin{tabular}{|c|c|c|c|c|c|} \hline
state & action & \multicolumn{3}{c|}{parameterized transition matrices} & reward \\ \hline
$i$ & $a$ & \hspace*{3.5mm}$j=1$\hspace*{3.5mm} & \hspace*{3.5mm}$j=2$\hspace*{3.5mm} & $j=3$ & $r(i,a)$ \\ \hline
\multirow{2}{*}{1} & 1 & $p_1$ & $1-p_1$ & 0 & 3\phantom{.}0 \\ \cline{2-6}
 & 2 & $1-p_2$ & $p_2$ & 0 & 2.5 \\ \hline
\multirow{2}{*}{2} & 1 & 0 & $q_1$ & $1-q_1$ & 2\phantom{.}0 \\ \cline{2-6}
 & 2 & $1-q_2$ & $q_2$ & 0 & 1.5 \\ \hline
\multirow{2}{*}{3} & 1 & 0 & 0 & 1 & 1\phantom{.}0 \\ \cline{2-6}
 & 2 & 0 & 1 & 0 & 0.5 \\ \hline
\end{tabular}
\caption{Data of simulated MDPs.}
\end{center}
\end{table} %
\setcounter{figure}{0}
\begin{figure}[h]
\label{Figure4.1}
 \begin{center}
  \includegraphics[width=13cm,height=5cm]{fig41_1.eps}
 \end{center}
\caption{Transition diagrams parameterized with $0<p_1,q_1,p_2,q_2<1$.}
\end{figure}

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 $\tilde{\psi}_n$ the average present value until $n$-th time,
which is defined by
\[
 \tilde{\psi}_n=\frac{1}{n}\sum_{t=0}^{n-1}r(X_t,\Delta_t) \quad (n\geqq 1).
\]
%
To calculate the quantity explicitly, 
we set $\tilde{\pi}_{0}^{\tau}(\cdot|i)=(\frac{1}{2},\frac{1}{2})$ for each $i\in 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^{0}_{ij}(a))=\Bigl\{(q^0_{ij}(1))=\begin{pmatrix}\frac{2}{5}&\frac{3}{5}&0\\[2pt]0&\frac{1}{2}&\frac{1}{2}\\[2pt]
  0&0&1\end{pmatrix},(q^0_{ij}(2))=
  \begin{pmatrix}\frac{7}{10}&\frac{3}{10}&0\\[2pt]\frac{7}{10}&\frac{3}{10}&0\\[2pt]0&1&0\end{pmatrix}
  \Bigr\}.
\]
We use a strictly increasing function $\phi$ such that
\[
  \phi(x)=\Bigl(\frac{x^N}{1+x^{N}}\Bigr)^{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 \geq 1)$.
It is easily checked that the property (i) in Condition A is satisfied with
$b_{n+1}=\phi(b_n)\ (n\geqq 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))
   =\Bigl\{(q_{ij}(1))
   =\begin{pmatrix}\frac{1}{3}&\frac{2}{3}&0\\[2pt]
     0&\frac{2}{5}&\frac{3}{5}\\[2pt]
     0&0&1
    \end{pmatrix},
     (q_{ij}(2))
   =\begin{pmatrix}\frac{2}{3}&\frac{1}{3}&0\\[2pt]
     \frac{3}{5}&\frac{2}{5}&0\\[2pt]
     0&1&0
    \end{pmatrix}
    \Bigr\}.
\]

\begin{center}%===============================================
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
values & \multicolumn{1}{c|}{\backslashbox{$\tau$}{$n$}} & \multicolumn{1}{c|}{$10^3$} & \multicolumn{1}{c|}{$5\times10^3$} & \multicolumn{1}{c|}{$10^4$} & \multicolumn{1}{c|}{$5\times10^4$} & \multicolumn{1}{c|}{$10^5$} & \multicolumn{1}{c|}{$10^6$} \\ \hline
\multirow{4}{*}{$\tilde{\psi}_n$} & \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.5 & 2.1104 & 2.1437 & 2.1569 & 2.1801 & 2.1876 & 2.2002 \\ \cline{2-8}
 \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}& 0.2 & 2.1214 & 2.1468 & 2.1585 & 2.1805 & 2.1878 & 2.2002 \\ \cline{2-8}
 \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}& 0.1 & 2.1224 & 2.1470 & 2.1586 & 2.1805 & 2.1878 & 2.2002 \\ \cline{2-8}
 \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}& 0.01 & 2.1184 & 2.1462 & 2.1581 & 2.1804 & 2.1878 & 2.2002 \\ \hline
decision rules & \backslashbox{$\tau$}{$n$} & $10^3$ & $5\times10^3$ & $10^4$ & $5\times10^4$ & $10^5$ & $10^6$ \\ \hline
\multirow{4}{*}{$\tilde{\pi}_{n}^{\tau}(1|1)$} &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.5 & 0.9003 & 0.9416 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.2 & 0.8980 & 0.9413 & 0.9535 & 0.9728 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.1 & 0.8983 & 0.9413 & 0.9535 & 0.9728 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.01 & 0.8937 & 0.9409 & 0.9533 & 0.9728 & 0.9784 & 0.9900 \\ \hline
\multirow{4}{*}{$\tilde{\pi}_{n}^{\tau}(2|2)$} &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.5 & 0.8996 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.2 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.1 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.01 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \hline
\multirow{4}{*}{$\tilde{\pi}_{n}^{\tau}(2|3)$} &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.5 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.2 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.1 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \cline{2-8}
 &  \rule{0pt}{10pt}\rule[-1pt]{0pt}{0pt}0.01 & 0.9002 & 0.9415 & 0.9536 & 0.9729 & 0.9785 & 0.9900 \\ \hline
\end{tabular}
\vspace{0.5ex}

{Table 4.2: The simulation value of $\tilde{\psi}_n$ and $\tilde{\pi}_n^{\tau }$
for each $\tau = 0.5, 0.2, 0.1, 0.01$.}
\end{center}%===============================================

\medspace
\begin{figure}[H]
\begin{center}
\includegraphics{fig42_1.eps}
\end{center}
\caption{The trajectories of $\tilde{\psi}_n(\tau =0.01)$.
The dotted line means the optimal value of average reward.}
\end{figure}

Considering the optimal average reward $\psi (q) = 42/19 \approx 2.2105$ 
and the $q$-optimal stationary policy $f^*$ with $f^*(1)=1, f^*(2)=f^*(3)=2$, 
it is seen that $\tilde{\psi}_n \rightarrow 
\psi (q) = 42/19$  and $\tilde{\pi}_{n}^{\tau}(1|1)$, $\tilde{\pi}_{n}^{\tau}(2|2)$,
$\tilde{\pi}_{n}^{\tau}(2|3) \rightarrow 1$ as $n \rightarrow \infty $ 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.

\pagebreak


\begin{thebibliography}{99}



\bibitem[Bath73]{Bather, J.}{1973}{Bather}
Optimal decision procedures for finite Markov chains. {II}.
Communicating systems.
{\em Adv. in Appl. Probab.}, 5:521--540.%, 1973.

\bibitem[Bert96]{Bertsekas, D.~P. and Tsitsiklis, J.~H.}{1996}{Bertsekas/Tsitsiklis}
{\em Neuro-Dynamic Programming.}
Athena Scientific.%, 1996.

\bibitem[Bill61]{Billingsley, P.}{1961}{Billingsley}
{\em Statistical inference for {M}arkov processes}.
The University of Chicago Press.%, 1961.

\bibitem[FeSc81]{Federgruen, A. and Schweitzer, P.~J.}{1981}{Federgruen/Schweitzer}
Nonstationary {M}arkov decision problems with converging parameters.
{\em J. Optim. Theory Appl.}, 34(2):207--241.%, 1981.

\bibitem[Hern89]{Hern{\'a}ndez-Lerma, O.}{1989}{Hern{\'a}ndez}
{\em Adaptive {M}arkov control processes}.
Springer-Verlag.%, 1989.

\bibitem[HeMa85]{Hern{\'a}ndez-Lerma, O. and Marcus, S.~I.}{1985}
{Hern{\'a}ndez/ Marcus}
Adaptive control of discounted {M}arkov decision chains.
{\em J. Optim. Theory Appl.}, 46(2):227--235.%, 1985.


\bibitem[KmSn60]{Kemeny, J.~G. and Snell, J.~L.}{1960}{Kemeny/Snell}
{\em Finite {M}arkov chains}.
D. Van Nostrand.%, 1960.

\bibitem[Kura72]{Kurano, M.}{1972}{Kurano}
Discrete-time {M}arkovian decision processes with an unknown
  parameter. {A}verage return criterion.
{\em J. Operations Res. Soc. Japan}, 15:67--76.%, 1972.

\bibitem[Kura83]{Kurano, M.}{1983}{Kurano}
Adaptive policies in {M}arkov decision processes with uncertain
  transition matrices.
{\em J. Inform. Optim. Sci.}, 4(1):21--40.%, 1983.

\bibitem[Kura87]{Kurano, M.}{1987}{Kurano}
Learning algorithms for {M}arkov decision processes.
{\em J. Appl. Probab.}, 24(1):270--276.%, 1987.

\bibitem[Laks81]{Lakshmivarahan, S.}{1981}{Lakshmivarahan}
{\em Learning algorithms}.
Springer-Verlag.%, 1981.

\bibitem[Leiz03]{Leizarowitz, A.}{2003}{Leiza^-rowitz}
An algorithm to identify and compute average optimal policies in
  multichain {M}arkov decision processes.
{\em Math. Oper. Res.}, 28(3):553--586.%, 2003.

\bibitem[Lo63]{Lo{\`e}ve, M.}{1963}{Lo{\`e}ve}
{\em Probability theory}.
D. Van Nostrand.%, 1963.

\bibitem[Mand74]{Mandl, P.}{1974}{Mandl}
Estimation and control in {M}arkov chains.
{\em Adv. in Appl. Probab.}, 6:40--60.%, 1974.

\bibitem[Mart67]{Martin, J.~J.}{1967}{Martin}
{\em Bayesian decision problems and {M}arkov chains}.
John Wiley \& Sons Inc.%, 1967.

\bibitem[MeLa82]{Meybodi, M.~R. and Lakshmivarahan, S.}{1982}{Meybodi/Lakshmivarahan}
{$\varepsilon $}-optimality of a general class of learning
  algorithms. {\em Inform. Sci.}, 28(1):1--20.%, 1982.

\bibitem[Pute94]{Puterman, M.~L.}{1994}{Puterman}
{\em Markov decision processes: discrete stochastic dynamic
  programming}.
John Wiley \& Sons Inc.%, 1994.

\bibitem[Ross70]{Ross, S.~M.}{1970}{Ross}
{\em Applied probability models with optimization applications}.
Holden-Day.%, 1970.

\bibitem[Sc68]{Schweitzer, P.~J.}{1968}{Schweitzer}
Perturbation theory and finite {M}arkov chains.
{\em J. Appl. Probability}, 5:401--413.%, 1968.

\bibitem[So03]{Solan, E.}{2003}{Solan}
Continuity of the value of competitive {M}arkov decision processes.
{\em J. Theoret. Probab.}, 16(4):831--845 (2004).%, 2003.

\bibitem[SuBa98]{Sutton, R.~S. and Barto, A.~G.}{1998}{Sutton and Barto}
{\em Reinforcement Learning: An Introducution}.
MIT Press.%, 1998.

\bibitem[vanHee78]{van Hee, K.~M.}{1978}{van Hee}
{\em Bayesian control of {M}arkov chains}.
Mathematisch Centrum.%, 1978.

\end{thebibliography}

\vspace{5mm}

\begin{flushleft}
{\it Received June 7, 2006}

{\it Revised February 25, 2007}
\end{flushleft}


\end{document}

