%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                             %
% A pattern-matrix learning algorithm for adaptive MDPs:             %
% The regularly communicating case                            %
%                                                             %
%    cf. LA_for_CMDP7f3.tex                                   %
%                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 2007.08.20     Typed by HORIGUCHI
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{bm}
\usepackage{array}
\usepackage{arydshln}
\usepackage{slashbox}
\usepackage{multirow}
\usepackage{graphicx,color}
\usepackage{float}
%\usepackage{pst-all}
% \usepackage[square]{harvard}
% \renewcommand{\harvardand}{and}
% \citationmode{abbr}

\setlength{\oddsidemargin}{0pt}
\setlength{\textwidth}{15.8cm}
\setlength{\textheight}{22.5cm}
%\setlength{\mathindent}{20mm}
\setlength{\topmargin}{-3mm}
\setlength{\headsep}{5mm}
\setlength{\headheight}{3mm}


\pagestyle{plain}

\newcommand{\calB}{{\mathcal B}}
\newcommand{\calD}{{\mathcal D}}
\newcommand{\calK}{{\mathcal K}}
\newcommand{\calS}{{\mathcal S}}


\newcommand{\bB}{\mathbb{B}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bK}{\mathbb{K}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bX}{\mathbb{X}}
\newcommand{\bY}{\mathbb{Y}}



\DeclareMathOperator{\E}{\overline{\mathbb{E}}}
\DeclareMathOperator{\wE}{\tilde{\mathbb{E}}}
\DeclareMathOperator{\bP}{\mathbb{P}}
\DeclareMathOperator{\Q}{\mathbb{Q}}

\newcommand{\calF}{{\mathcal F}}
\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\renewcommand{\appendixname}{Appendix}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\theoremstyle{definition}
\newtheorem{df}{Definition}%%%%%%%%%%%[section]
\newtheorem{ex}{Example}%%%%%%%%%%%%%%[section]
\newtheorem{ass}{Assumption}%%%%%%%%%%[section]
\newtheorem*{app}{Appendix}
\newtheoremstyle{break}% name
  {9pt}%      Space above, empty = `usual value'
  {9pt}%      Space below
  {\itshape}% Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {\newline}% Space after thm head: \newline = linebreak
  {}%         Thm head spec
\theoremstyle{break}
\newtheorem{bthm}[thm]{Theorem}
\newtheorem{bdf}[df]{Definition}
\newtheorem{bcor}[cor]{Corollary}
\newtheorem{bprop}[prop]{Proposition}
\newtheorem{blem}[lem]{Lemma}
\newtheorem*{CA}{Condition A}
\renewcommand{\qed}{\hbox{\rule[-2pt]{3pt}{6pt}}}

%\numberwithin{equation}{thm}
\numberwithin{equation}{section}%
\numberwithin{table}{section}%
%\theoremstyle{defenition}

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}
\newtheorem*{assa}{Assumption A}
\def\Topspc{\rule{0pt}{14pt}}
\def\Btmspc{\rule[-8pt]{0pt}{0pt}}

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

%\pagestyle{empty}
\usepackage{fancyhdr}
%\usepackage{mymacros}
\pagestyle{plain}
\renewcommand{\headrulewidth}{0.5pt}%\vbox to 0pt{\hbox%
%to \headwidth{\dotfill}\vss}}
\lhead{\scriptsize {\sf A pattern-matrix learning algorithm for adaptive MDPs: The regularly communicating case.}}%
\chead{}%
%\rhead{\scriptsize {\texttt{\colorbox[gray]{0.7}{Draft.2. \today}}}
\rhead{\scriptsize {T.\ Iki.\ et al.}%
}%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

% \title{A pattern-matrix learning algorithm for adaptive MDPs: %
% The regularly communicating case}%
% \author{\small
%   T. IKI\\
%   \textit{\small Faculty of Education and Culture, Miyazaki University
%        Miyazaki 889-2192 Japan}\\
% \small  M. HORIGUCHI\\
%   {\it \small General Education, Yuge National College of Maritime Technology,
%        Ehime 794-2593 Japan}\\
% \small  M. YASUDA\\
%   {\it\small Faculty of Science, Chiba University
%        Chiba 263-8522 Japan}\\
% \small  M. KURANO\\
%   {\it\small Faculty of Education, Chiba University
%        Chiba 263-8522 Japan}
% }

% \date{}
\begin{center}
{\Large\bf A pattern-matrix learning algorithm for adaptive MDPs: %
The regularly communicating case}\\[5pt]
\end{center}
\begin{flushright}
{\small 
宮崎大学・教育文化学部　伊喜　哲一郎(Tetsuichiro IKI)\\
{ Faculty of Education and Culture, Miyazaki University}\\[2pt]
弓削商船高等専門学校・総合教育科　堀口　正之(Masayuki HORIGUCHI)\\
{ %Department of Information Environment Engineering,
General Education, Yuge National College of Maritime Thechnology}\\[2pt]
千葉大学・理学部　安田正實（Masami YASUDA）\\
Faculty of Science, Chiba University\\[2pt]
千葉大学・教育学部　蔵野　正美(Masami KURANO)\\
{ Faculty of Education, Chiba University}
}
\end{flushright}


%\maketitle % -----------------------------------------

\begin{abstract}
In this note, as a sequel to our previous work\cite{IHYK07}, 
we are concerned with adaptive models for uncertain Markov decision
processes with regularly communicating structure where the state space
is decomposed into a single communicating class and a absolutely
transient class.

We give a pattern-matrix learning algorithm which finds the regularly communicating
structure, by which an asymptotic sequence of adaptive properties with
nearly average-optimal properties is constructed.
A numerical experiment is given.
\end{abstract}

{\it Keywords:} 
adaptive Markov decision processes,
pattern-matrix learning algorithm,
average-optimal adaptive policy,
regularly communicating case.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction and notation}\label{Sec1}
In our previous work\cite{IHYK07}, 
we considered the adaptive Markov decision processes(MDPs)
in which the state space is a single communicating class
and constructed an average-optimal adaptive policy 
of reward-penalty types(cf.\ \cite{Kura87,Laks81})
by applying the perturbation theory(cf.\ \cite{Sc68}). 

In this note, as a sequel to \cite{IHYK07},
we are concerned with adaptive models for uncertain MDPs
with regularly communicating structure where the state space
is assumed to be decomposed into a single communicating class and
a transient class(cf.\ \cite{Bath73,IHK07,Leiz03}).
In this case, the corresponding adaptive policy will be compelled
to learn the pattern of the structure.

Here, we give a pattern-matrix learning algorithm for regularly 
communicating structure, by which an asymptotic sequence of adaptive 
properties
with nearly average-optimal properties is constructed by extending
the results of \cite{IHYK07}.

For general discussions of adaptive MDPs, refer to
\cite{Hern89,HeMa85,Mand74,Mart67,vHee78}
and for an approach by the neuro-dynamic programming
refer to \cite{Bert96,IHYK07b,SuBa98}.

In the reminder of this section, we formulate the adaptive MDPs with
uncertain transition matrices.

Consider a controlled dynamic system with finite state space
$S=\{1,2,\ldots,N\}$, containing $N<\infty$ elements.
For each $i\in S$, the finite set $A(i)$ denotes the set of available actions
at state $i$.
Let $\bQ$ denote the parameter space of unknown transition matrices, i.e.,
\begin{equation}\label{eq(1.1)}
\bQ=\{q=(q_{ij}(a))\vert q_{ij}(a)\geqq 0 , 
\sum_{j\in S}q_{ij}(a)=1 \ \text{for}\ i,j\in S \ \text{and}\ a\in A(i)\}.
\end{equation}

%%%%%%%%%%%%%% In: LA_for_CMDP %%%%%%%%%%%%%%%%%%%%%%%%%%
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}\label{eq(1.2)}
  \psi(i,q|\pi)=
  \liminf_{T\to\infty}\frac{1}{T+1}E_{\pi}\left(
  \sum_{t=0}^{T}r(X_{t},\Delta_{t})\Bigm|X_0=i,q
  \right)
\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}\label{eq(1.3)}
  \psi(i,q)=\sup_{\pi\in\Pi}\psi(i,q|\pi),
\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$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $q\in \bQ$. A subset $E\subset S$ is called 
a communicating class for $q$ if 
\begin{itemize}\label{def:comclass}
\item[(i)] for any $i,j\in E$, there exists a path in $E$
from $i$ to $j$ with positive probability, rewritten by ``$i\to j$'', i.e.,
it holds that
\begin{equation}\label{communicating}
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
\end{equation}
for some $\{i_{1}=i,i_{2},\ldots,i_{l}=j\}\subset E$ and
$a_{k}\in A(i_{k})$ and $2\leqq l \leqq N,$ and
\item[(ii)] $E$ is closed, i.e., $\sum_{j\in E}q_{ij}(a)=1$ for $i\in E, a\in A(i)$.
\end{itemize}

The transition matrix $q\in \bQ$ is said to be regularly communicating if
there exists an $\Bar{E} \subsetneqq S$ such that
\begin{itemize}\label{def:rgcom}
\item[(i)] $\Bar{E}$ is a communicating class for $q$ and
\item[(ii)] $T=S-\Bar{E}$ is an absolutely transient class, i.e.,
\begin{equation}\label{abtransient}
P_{\pi}(X_{t}\in \Bar{E} \ \text{for some}\ t\geqq 1\vert X_{0}\in T)=1
\end{equation}
for all $\pi\in \Pi$
\end{itemize}
For a regularly communicating $q\in \bQ,$ this corresponding
communicating class $\Bar{E}$ will be denoted by $\Bar{E}(q)$
depending on $q\in \bQ$.
For any $i_{0}\in S$, we denote by $\bQ^{*}(i_0)$ the set of
regularly communicating $q\in \bQ$ with $i_{0}\in \Bar{E}(q)$.

Let $n(D)$ denotes the number of elements in a set $D$.
For any $q\in \bQ^{*}(i_0)$, the pattern-matrix $M(q)$
(cf.\ \cite{IHK07}) corresponding with $q$ is 
generally represented as follows:
\[
M(q)=\left(
\begin{array}{cc}
\multicolumn{1}{c;{2pt/2pt}}{E} & \multicolumn{1}{c}{O}\\\hdashline[2pt/2pt]
\multicolumn{1}{c}{R} & \multicolumn{1}{;{2pt/2pt}c}{K}
\end{array}
\right)
\]
where $E$ is an $n(\Bar{E}(q))\times n(\Bar{E}(q))$-matrix and
$R$ is an $n(S-\Bar{E}(q))\times n(\Bar{E}(q))$-matrix whose elements of both
$E$ and $R$ are all $1$ and that $i\to j$ means that
the $(i,j)$ element of $M(q)$ is $1$.

The adaptive policy for $q\in Q^{*}(i_{0})$ will be necessary
to find the pattern-matrix $M(q)$, whose algorithm will be called
the pattern-matrix learning one.




%Let $i_{0}\in S_{0}$. 
The sequence of policies 
$\{\tilde{\pi}^{n}\}_{n=0}^{\infty}\subset\Pi$ is called 
an asymptotic sequence of adaptive policies with nearly optimal properties
for $\calD \subset \bQ$ and $E \subset S$ if
\begin{equation}\label{def:nrly-op}
\lim_{n\to \infty}\psi(i,q\vert \tilde{\pi}^{n})=\psi(i,q)
\end{equation}
for all $q\in \calD$ and $i\in E$.

In %Kurano
\cite{Kura87}, an adaptively optimal policy for %$S$ and
\begin{equation}\label{def:minorztn}
\bQ^{+}:=\{q=(q_{ij}(a))\in \bQ\vert q_{ij}(a)>0 \ \text{for all} \ i,j\in S
\ \text{and}\ a\in A(i)\},
\end{equation}
was constructed by applying the value iteration and policy improvement algorithm
(cf.\ \cite{FeSc81}) which was extensively applied to the communicating case of
multi-chain MDPs in Iki et.\ al.\ \cite{IHYK07}.

In this note, using the method of pattern-matrix learning we will construct 
an asymptotic sequence of adaptive policies with nearly optimal properties
for $\bQ^{*}(i_{0})$ with $i_{0}\in S$, which is thought of as a wider class 
for uncertain MDPs than the communicating case treated in \cite{IHYK07}.
In order to treat with the regularly communicating case with 
$q\in \bQ^{*}(i_{0})$, 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LA_for_CMDP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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}\label{def:dsctrwd}
  v_{\tau}(i,q|\pi)=E_{\pi}\left(
    \sum_{t=0}^{\infty}(1-\tau)^{t}r(X_{t},\Delta_{t})\vert X_0=i,q
    \right)
\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.

Let $B(S)$ be the set of all functions on $S$.
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}\label{def:oprtr}
  U_{\tau}\{q\}u(i) = \max_{a\in A}\left\{r(i,a) + (1-\tau) \sum_{j\in S}q_{ij}(a)u(j)\right\}
\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}\label{eq:fxdpoint}
         v_{\tau}=U_{\tau}\{q\}v_{\tau},
  \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 (\ref{eq:fxdpoint}).
\end{itemize}
\end{lem} 
%\harvardparenthesis{round}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In Section 2, some elementary lemmas are given which show the effectiveness of
pattern-matrix leaning algorithm developed in the sequel.
Section 3 is devoted to the construction of adaptive policies 
with nearly average-optimal properties for $\bQ^{*}(i_0)$.
A numerical experiment is given in Section 4.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary lemmas}\label{Sec2}
%section 2

In this section, several lemmas are given which are used in Section
\ref{Sec3}.

Let $i_{0} \in S.$ For any $q\in \bQ^{*}(i_{0})$ and $E\subsetneqq \Bar{E}(q)$,
we define the sequence $J_{k}(E)\ (k=1,2,\ldots)$ iteratively by
\begin{equation}\label{eq:(2.1)}
\begin{split}
&J_{1}(E)=\{i\in E\vert \sum_{j\in \Bar{E}(q)-E}q_{ij}(a)>0\ 
\text{for some}\ a\in A(i)\}\\
&\text{and}\\
&J_{k}(E)=\{i\in E-\bigcup_{l=1}^{k-1}J_{l}(E)\vert\sum_{j\in J_{k-1}(E)} q_{ij}(a)>0\ 
\text{for some} \ a\in A(i)\}\  (k\geqq 2).
\end{split}
\end{equation}

Letting $K(\Bar{E}(q))=\{(i,a,j)\vert p_{ij}(a)>0, i,j\in\Bar{E}(q) \ 
\text{and}\ a\in A(i)\}$,
put $\delta:=\min p_{ij}(a)$ where the minimum is taken over 
$(i,a,j)\in K(\Bar{E}(q))$. 
Then, from the definition of communicating class $\Bar{E}(q)$,
the following can be easily shown.

\begin{lem}\label{lem:2.1}
For any $q\in \bQ^{*}(i_0)$ with $i_{0}\in S$ and 
$E \subsetneqq \Bar{E}(q),$
there exists $l(E)\ (1\leqq l(E) \leqq N)$ for which
$J_{k}(E)\neq \emptyset \ (k=1,2,\ldots,l(E))$ and 
$J_{l(E)+1}(E)=\emptyset.$ 
\end{lem}

\begin{lem}\label{lem:2.2}
Let $q\in \bQ^{*}(i_0)$ with $i_{0}\in S$.
Let a policy $\tilde{\pi}=(\tilde{\pi}_{0},\tilde{\pi}_{1},\ldots)$ and
a decreasing sequence of positive numbers $\{\varepsilon_{t}\}_{t=0}^{\infty}$
satisfy that for each $t\geqq 0$ $\tilde{\pi}_{t}(a\vert h_{t})\geqq \varepsilon_{t}$
with $a\in A(x_{t})$ and $h_{t}=(x_{0},a_{0},x_{1},\ldots,x_{t})\in H_{t}.$
Then, it holds that for any $E \subsetneqq \Bar{E}(q),$
\begin{equation}\label{eq:(2.2)}
P_{\tilde{\pi}}(X_{t+l}\in \Bar{E}(q)-E\ \text{for some}\ l(1\leqq l \leqq N)\vert 
X_{t}\in E)\geqq (\delta \varepsilon_{t+N})^{N}.
\end{equation}
\end{lem}

\noindent{\it Proof.} 
By Lemma 2.1, it holds that 
\begin{align*}
\text{the left-hand side of (\ref{eq:(2.2)}}) &\geqq 
(\varepsilon_{t}\delta)(\varepsilon_{t+1}\delta)\cdots(\varepsilon_{t+l(E)}\delta)\\
&\geqq (\delta\varepsilon_{t+N})^N,
\end{align*}
which completes the proof.\qed
\medskip

For $q\in \bQ^{*}(i_0)$ with $i_0\in S$, a sequence of 
stopping times $\{\sigma_{t}\}$ and subsets $\{E_{\sigma_{t}}\}\subset \Bar{E}(q)$
will be defined as follows:
\begin{equation}\label{eq:(2.3)}
\begin{split}
&E_{0}:=\{i_{0}\}, T_{0}:=\Bar{E}(q)-E_{0},%\\
%&
\sigma_{1}:=\min\{t \vert X_{t}\in T_{0},t>0\}, \\
&
E_{\sigma_{1}}=E_0\cup\{X_{\sigma_{1}}\}, T_{\sigma_{1}}:=\Bar{E}(q)-E_{\sigma_{1}}, 
\\
&\text{and iteratively for $n=2,3,\ldots$},\\
&\sigma_{n}:=\min\{t\vert X_{t}\in T_{\sigma_{n-1}},t>\sigma_{n-1}\}, %\\
%&
E_{\sigma_{n}}=E_{\sigma_{n-1}}\cup\{X_{\sigma_{n}}\}, 
T_{\sigma_{n}}=\Bar{E}(q)-E_{\sigma_{n}},\\
&\text{where $\min \emptyset=\infty$}.
\end{split}
\end{equation} 

For any $E\subset \Bar{E}(q)$, let $\Bar{n}(E)=\min\{n\geqq 1|E_{\sigma_{n}}=\Bar{E}(q)\}$.
If $\Bar{n}(E)<\infty$, we can find the pattern-matrix $M(q).$
Here, we have the following.

\begin{lem}\label{lem:2.3}
Let $q\in \bQ^{*}(i_0)$ with $i_{0}\in S$ and $\tilde{\pi}$ satisfy
condition in Lemma 2.2 with $\sum_{t=0}^{\infty}\varepsilon_{t}^{N}=\infty$.
Then, for any $E\subsetneqq \Bar{E}(q)$ it holds that
\begin{itemize}
\item[(i)] $P_{\tilde{\pi}}(\Bar{n}(E)<\infty\vert X_{0}=i_{0},q)=1$, and
\item[(ii)] for any $k\leqq \Bar{n}(E), 
P_{\tilde{\pi}}(\sigma_{k}<\infty\vert X_{0}=i_{0},q)=1.$ 
\end{itemize}
\end{lem}

\noindent{\it Proof.} 
For any $E\subsetneqq \Bar{E}(q)$, from Lemma \ref{lem:2.2} and
$\sum_{t=0}^{\infty}\varepsilon_{t}^{N}=\infty$
it follows that 
\begin{equation}\label{eq:(2.4)}
P_{\tilde{\pi}}(X_{t+l}\in E \ \text{for all}\ l\geqq 1\vert X_{t}\in E,q)\leqq\prod_{l=1}^{\infty}(1-\delta^{N}\varepsilon_{t+lN}^N)
\leqq e^{-\delta^{N}}\sum_{l=1}^{\infty}\varepsilon_{t+lN}^{N}=0.
\end{equation}
So, taking $E=E_{0}$ in (\ref{eq:(2.4)}), we have
\begin{align*}
P_{\tilde{\pi}}(\sigma_{1}<\infty\vert X_{0}\in E_{0},q)
&=1-P_{\tilde{\pi}}(\sigma_{1}=\infty\vert X_{0}\in E_{0},q)\\
&=1-P_{\tilde{\pi}}(X_{t}\in E_{0} \ \text{for all}\ t\geqq 1\vert X_{0}\in E_{0},q)\\
&=1.
\end{align*}

For (ii), inductively on $k\ (k=2,3,\ldots)$, if $E_{\sigma_{k-1}}\subsetneqq \Bar{E}(q)$,
we have from (\ref{eq:(2.4)}) that
\begin{equation}\label{eq:2.5}
\begin{split}
&P_{\tilde{\pi}}(\sigma_{k}<\infty\vert X_{0}\in E_{0},q)\\
&=\sum_{l=1}^{\infty}P_{\tilde{\pi}}(\sigma_{k-1}=l\vert X_0\in E_{0},q)\cdot P_{\tilde{\pi}}(X_{t+l}\in \Bar{E}(q)-E_{l}\ \text{for some}\ 0<t<\infty \vert X_{l}\in E_{l},q)\\
&=\sum_{l=1}^{\infty}P_{\tilde{\pi}}(\sigma_{k-1}=l\vert X_0\in E_{0},q)\\
&=P_{\tilde{\pi}}(\sigma_{k-1}<\infty\vert X_{0}\in E_{0},q)\\
&=1.
\end{split}
\end{equation}
Obviously, (i) follows from (ii), which completes the proof.\qed

We note that a sequence $\{(1+t)^{-N}\}_{t=0}^{\infty}$ satisfies
Assumption concerning $\{\varepsilon_{t}\}_{t=0}^{\infty}$
given in Lemma \ref{lem:2.3}.




%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Pattern-matrix learning algorithms}\label{Sec3}
In this section, we give a pattern-matrix learning algorithm by which
an asymptotic sequence of adaptive policies with nearly average-optimal
properties for $\bQ^{*}(i_{0})$ with $i_{0}\in S$ is given.

For any sequence $\{b_{n}\}_{n=0}^{\infty}$ of positive numbers with
$b_{0}=1, 0<b_{n}<1$ and $b_{n}>b_{n+1}$ for all
$n\geqq 1,$
let $\phi$ be any strictly increasing function that 
$\phi:[0,1]\to[0,1]$ and $\phi(b_{n})=b_{n+1}$
for all $n\geqq 0$.

Here, we consider the following iterative scheme called 
a pattern-matrix learning algorithm with $i_{0}\in S, \{b_n\}$ and 
$\tau\in (0,1)$, denoted by $\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$.  
\medskip

\noindent{\underline{$\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$:}}\label{alg:PMLA} 
\begin{enumerate}
  \item Set $E_{0}=\{i_{0}\}, T_{0}=S-E_{0},\tilde{v}_0(i) = 0\ (i\in E_{0})$,
		$X_0=i_0$ and $\tilde{\pi}_{0}^{\tau}(a\vert X_{0})=n(A(i_{0}))^{-1}$
		for $a\in A(i_{0}).$
  \item Suppose that $E_{n}\subset S, T_{n}=S-E_{n}$ and $\{\tilde{v}_{n}(i):i\in E_{n}\}$
		are given. Moreover, suppose that the $n$-th decision rule
		$\tilde{\pi}_{n}^{\tau}(a|i)=\textit{Prob.}(\Delta_{n}=a \vert H_{n-1}, \Delta_{n-1},X_n=i)\ 
		(i\in E_{n},a\in A(i))$ are given, where $H_{n-1}=(X_0,\Delta_0,X_1,
		\ldots,X_{n-1})$ is a history until the $(n-1)$-th step.
  \item Choose an action $\Delta_{n+1}\in A(X_{n})$ from $\tilde{\pi}_{n}(\cdot\vert H_{n})$.
		Then, according to the value of $X_{n+1}$,
		we put $E_{n+1}=E_{n}\cup \{X_{n+1}\} $ if $X_{n+1}\in T_{n}$
		and $E_{n+1}=E_{n}$ if $X_{n}\in E_{n}$.
		
		Calculate $N_{n+1}(i,j\vert a)=\sum_{t=0}^{n}I_{\{X_{t}=i,\Delta_{t}=a,X_{t+1}=j\}}$
		and $N_{n+1}(i\vert a)=\sum_{t=0}^{n}I_{\{X_{t}=i,\Delta_{t}=a\}}$
		for $i,j\in E_{n+1}$ and $a\in A(i)$.
        
		Set $q^{n+1}=(q_{ij}^{n+1}(a))$ by
		\begin{equation}
		q^{n+1}_{ij}(a)=\begin{cases}
		\dfrac{N_{n+1}(i,j\vert a)}{N_{n+1}(i,a)} & \text{if $N_{n+1}(i\vert a)>0,$}\\
		q^{0}_{j} & \text{otherwise},
		\end{cases}
		(i,j\in E_{n+1}, a\in A(i))
		\end{equation}
		where $q^{0}=(q^{0}_{j}:j\in E_{n+1})$ is any distribution on $E_{n+1}$
		with $q^{0}_{j}>0$ for all $i\in E_{n+1}$.
  \item For each $i\in E_{n+1},$ choose $\tilde{a}_{n+1}(i)$ which satisfies
        \[\tilde{a}_{n+1}(i)\in \aM_{a\in A(i)}
        \{r(i,a)+(1-\tau)\sum_{j\in E_{n+1}}q^{n+1}_{ij}(a)\tilde{v}_{n}(j)\}
        \]
		and update $\tilde{\pi}_{n+1}^{\tau}(a\vert i)=\textit{Prob.}
		(\Delta_{n+1}=a\vert H_{n},\Delta_{n+1},X_{n+1}=i)$ as follows: 
		\begin{equation}
		\tilde{\pi}_{n+1}^{\tau}(a_{i}|i)=
		\begin{cases}
		1-\sum_{a\neq a_{i}}\phi (\tilde{\pi}_{n}^{\tau}(a|i)) & (a_{i}=\tilde{a}_{n+1}(i))\\
		\phi(\tilde{\pi}_{n}^{\tau}(a_{i}\vert i)) & (a_{i}\neq \tilde{a}_{n+1}(i)).
		\end{cases}
		\end{equation}
		Moreover, put $\tilde{v}_{n+1}=U_{\tau}\{q^{n+1}\}\tilde{v}_{n}$ on $E_{n+1}$.
  \item Set $n \leftarrow n +1 $ and return to step 3.
\end{enumerate}

We need the following condition on $\{b_n\}$.
\medskip

\noindent{\bf Condition ($\bm{*}$)}\\
\begin{equation}
b_n \to 0 \ \text{as $n\to\infty$ and $\sum_{n=0}^{\infty}b_{n}^{N}=\infty$}.
\end{equation}

The following theorem says that the policy 
$\tilde{\pi}^{\tau}=(\tilde{\pi}_{0}^{\tau},\tilde{\pi}_{1}^{\tau},\ldots)$
constructed by \\
$\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$ has 
nearly average-optimal properties for $\bQ^{*}(i_{0})$ when $\tau\to 0$.

\begin{thm}\label{thm:3.1}
Under condition $(*)$, 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 average-optimal properties for $\bQ^{*}(i_0).$
\end{thm}

\noindent{\it Proof.}
Under condition $(*)$, the policy 
$\tilde{\pi}^{\tau}=(\tilde{\pi}_{0}^{\tau},\tilde{\pi}_{1}^{\tau},\ldots)$
constructed in \\
$\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$ satisfies
assumptions in Lemma \ref{lem:2.3}.
So, by Lemma \ref{lem:2.3} we observe that
$\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$ finds the pattern $\Bar{E}(q)$
with $P_{\tilde{\pi}^{\tau}}(\cdot\vert X_0=i_0,q)$-probability 1, i.e.,
\[
E_n=\Bar{E}(q) \ \text{for all $n\geqq \Bar{n}(E_{0})$},
\]
where $\Bar{n}(E_{0})$ is given in Lemma \ref{lem:2.3}.

Thus, a learning algorithm for communicating MDPs on 
$\Bar{E}(q)$ for $q\in \bQ(i_0)$, which was developed in \cite{IHYK07}
using the vanishing discount approach(Lemma 1.1),
are applicable to the pattern-matrix learning case, 
which completes the proof.\qed





%%%%%%%%%%%%%%%%%%% sec. 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A numerical experiment}\label{Sec4}
In this section, we give a simulation result for
pattern-matrix learning algorithm.

Consider the six-state MDPs with $S=\{1,2,3,4,5,6\}$, where
data  for simulation are given % and $A(1)=A(2)=
%A(3)=A(4)=A(6)=\{1,2\},A(5)=\{1,2,3\}$and $A(8)=\{1,2,3\},$ 
%whose transition probability matrix and rewards are given 
in Table 4.1. %\ref{table:4.1}.
%\setcounter{table}{0}

\begin{table}[H]\label{table:4.1}
\caption{Data of simulated MDPs}\begin{center}
\small
\begin{tabular}{|c|c|cccccc|c|} \hline
state & action & \multicolumn{6}{c|}{transition probabilities $q_{ij}(a)$} & reward \\ \hline
$i$ & $a\in A(i)$ & \multicolumn{1}{c|}{$j=1$} & \multicolumn{1}{c|}{$j=2$} & \multicolumn{1}{c|}{$j=3$} & \multicolumn{1}{c|}{$j=4$} & \multicolumn{1}{c|}{$j=5$} & $j=6$ & $r(i,a)$ \\ \hline
\multirow{2}{*}{1} & 1 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & 0 & 9\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{$\frac{1}{4}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & 0 & 10\Topspc\Btmspc \\ \hline
\multirow{2}{*}{2} & 1 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & $\frac{1}{4}$ & 5\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{1} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & 0 & 2\Topspc\Btmspc \\ \hline
\multirow{2}{*}{3} & 1 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{2}{5}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{3}{5}$} & 0 & 7\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & $\frac{1}{2}$ & 8\Topspc\Btmspc \\ \hline
\multirow{2}{*}{4} & 1 & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & 0 & 2\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & \multicolumn{1}{c|}{$\frac{1}{2}$} & 0 & 12\Topspc\Btmspc \\ \hline
\multirow{3}{*}{5} & 1 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & $\frac{1}{4}$ & 6\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & 0 & 2.5\Topspc\Btmspc \\ \cline{2-9}
 & 3 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & 0 & 2.25\Topspc\Btmspc \\ \hline
\multirow{2}{*}{6} & 1 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{4}$} & $\frac{1}{4}$ & 14\Topspc\Btmspc \\ \cline{2-9}
 & 2 & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{$\frac{1}{2}$} & \multicolumn{1}{c|}{0} & \multicolumn{1}{c|}{0} & $\frac{1}{2}$ & 8\Topspc\Btmspc \\ \hline
\end{tabular}
\end{center}
\end{table} %

We denote by $\tilde{\psi}_n$ the average present value until $n$-th time,
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 $E_{0}=\{2\}$.
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$.

The pattern matrix $M(q)$ and reordered matrix
$\overline{M}$ corresponding to communicating states are easily computed,
which are shown as follows.

\begin{table}[H]
\begin{tabular}{crl}
\multirow{7}{*}{$M=$}
 && {\scriptsize \;\;\;\;\;\, 1 $\;\; $ 2 $\;\; $  3 $\;\>\, $  4 %
$\;\;\, $  5 $\;\>\, $  6} \\
&{\scriptsize 1} & \multirow{2}{*}{$\left(
\begin{array}{cccccc} 1 &  1 & 1 & 1 & 1 & 0  \\ 
0 & 1 & 1 & 0 & 1 & 1  \\
0 & 1 & 1 & 0 & 1 & 1  \\
1 & 1 & 1 & 1 & 1 & 0  \\
0 & 1 & 1 & 0 & 1 & 1  \\
0 & 1 & 1 & 0 & 1 & 1  \\
\end{array}\right),$}\\
&{\scriptsize 2}\\
&{\scriptsize 3}\\
&{\scriptsize 4}\\
&{\scriptsize 5}\\
&{\scriptsize 6}\\
\end{tabular}
\begin{tabular}{crl}
\multirow{7}{*}{$\overline{M}=$}
 && {\scriptsize \;\;\;\;\;\, 2 $\;\; $ 3 $\;\; $  5 $\;\>\, $  6 %
$\;\;\, $  1 $\;\>\, $  4} \\
&{\scriptsize 2} & \multirow{2}{*}{$\left(
\begin{array}{cccccc} 1 & 1 & 1 & 1 & 0 & 0  \\ 
1 & 1 & 1 & 1 & 0 & 0  \\
1 & 1 & 1 & 1 & 0 & 0  \\
1 & 1 & 1 & 1 & 0 & 0  \\
1 & 1 & 1 & 1 & 1 & 1  \\
1 & 1 & 1 & 1 & 1 & 1  \\
\end{array}\right).$}\\
&{\scriptsize 3}\\
&{\scriptsize 5}\\
&{\scriptsize 6}\\
&{\scriptsize 1}\\
&{\scriptsize 4}\\
\end{tabular}
\end{table}

\begin{figure}[H]
\begin{center}
\includegraphics[width=.77\textwidth]{Example_transition.eps}
\end{center}
\caption{Transition diagrams of numerical experiment. The first quantity in brackets near the arc is action number and the second one is its transition probability if the action is chosen.}
\end{figure}

Now, we make numerical experiments with vanishing parameter $\tau=0.1$ and $0.01$ and 
show the results given in Table 4.2.\ and Fig.\ 4.2.%\ref{table:4.2}. 


%\begin{center}%===============================================
{\vspace{-0.5ex}
\begin{table}[H]\label{table:4.2}
\caption{The simulation value of $\tilde{\psi}_n$ and $\tilde{\pi}_n^{\tau }$
for each $\tau = 0.1, 0.01$.}
\begin{center}
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline
values & \backslashbox{$\tau$}{$n$} & $10^3$ & $5\times10^3$ & $10^4$ & $5\times10^4$ & $10^5$ & $10^6$ & $10^7$ \\ \hline
\multirow{2}{*}{$\tilde{\psi}_n$} & 0.10 & 6.403347 & 6.672316 & 6.827892 & 6.965801 & 7.013102 & 7.158738 & 7.282986 \\ \cline{2-9}
 & 0.01 & 6.365634 & 6.651570 & 6.816118 & 6.963271 & 7.011827 & 7.158618 & 7.282973 \\ \hline
decision & \backslashbox{$\tau$}{$n$} & $10^3$ & $5\times10^3$ & $10^4$ & $5\times10^4$ & $10^5$ & $10^6$ & $10^7$ \\ \hline
\multirow{2}{*}{$\tilde{\pi}_{n}^{\tau}(1|2)$} & 0.10 & 0.661198 & 0.755328 & 0.783315 & 0.835058 & 0.853137 & 0.899994 & 0.931870 \\ \cline{2-9}
 & 0.01 & 0.493097 & 0.749621 & 0.780978 & 0.834723 & 0.852989 & 0.899984 & 0.931870 \\ \hline
\multirow{2}{*}{$\tilde{\pi}_{n}^{\tau}(2|3)$} & 0.10 & 0.685394 & 0.758424 & 0.784669 & 0.835262 & 0.853228 & 0.900001 & 0.931871 \\ \cline{2-9}
 & 0.01 & 0.685111 & 0.758380 & 0.784649 & 0.835259 & 0.853226 & 0.900000 & 0.931871 \\ \hline
\multirow{2}{*}{$\tilde{\pi}_{n}^{\tau}(1|5)$} & 0.10 & 0.422566 & 0.527159 & 0.574120 & 0.671281 & 0.706794 & 0.800024 & 0.863743 \\ \cline{2-9}
 & 0.01 & 0.422566 & 0.527159 & 0.574120 & 0.671281 & 0.706794 & 0.800024 & 0.863743 \\ \hline
\multirow{2}{*}{$\tilde{\pi}_{n}^{\tau}(1|6)$} & 0.10 & 0.686510 & 0.758602 & 0.784748 & 0.835274 & 0.853233 & 0.900001 & 0.931871 \\ \cline{2-9}
 & 0.01 & 0.686510 & 0.758602 & 0.784748 & 0.835274 & 0.853233 & 0.900001 & 0.931871 \\ \hline
\end{tabular}
\end{center}
\end{table} %
%\end{center}%===============================================

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

Considering the optimal average reward $\psi (i,q) = 91/12 \approx 7.583 (i\in \Bar{E}(q))$ 
and the $q$-optimal stationary policy $f^*$ for $\Bar{E}(q)$ is %given by 
$f^*(2)=1, f^*(3)=2,f^*(5)=1,f^*(6)=1$, 
it is seen that $\tilde{\psi}_n \rightarrow 
\psi (i,q) = 91/12$  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 Fig.\ 4.2.   
The results of the above simulation show that the pattern-matrix learning algorithm 
is practically effective 
for the communicating class of transition matrices.


%\begin{acknowledgements}
%If you'd like to thank anyone, place your comments here
%and remove the percent signs.
%\end{acknowledgements}

% BibTeX users please use one of
%\bibliographystyle{spbasic}      % basic style, author-year citations
%\bibliographystyle{spmpsci}      % mathematics and physical sciences
%\bibliographystyle{spphys}       % APS-like style for physics
%\bibliography{}   % name your BibTeX data base

%\newpage

%%%%%%%%%%%%%%%%%%%%%%
% \nocite{Bert96}
% \nocite{Bill61}
% \nocite{BoMn00}
% \nocite{IHK07}
% \nocite{FeSc81}
% \nocite{Hern89}
% \nocite{Howd60}
% \nocite{KoBo99}
% \nocite{Kura83}
% \nocite{Kura87}
% \nocite{Leiz03}
% \nocite{Mand74}
% \nocite{Numm84}
% \nocite{Mart67}
% \nocite{Pute94}
% \nocite{SuBa98}

%\pagebreak
%%%%%%%%%%%%%%%%%%%%

%\harvardparenthesis{round}
\bibliographystyle{plain}%{agsm}
\bibliography{myrefs.bib}
\end{document}

\addcontentsline{toc}{chapter}{Bibliography}
\begin{thebibliography}{xx}

\harvarditem{Bather}{1973}{Bath73}
Bather, J.  \harvardyearleft 1973\harvardyearright , `Optimal decision
  procedures for finite {M}arkov chains. {II}. {C}ommunicating systems', {\em
  Advances in Appl. Probability} {\bf 5},~521--540.

\harvarditem{Bertsekas \harvardand\ Tsitsiklis}{1996}{Bert96}
Bertsekas, D. \harvardand\ Tsitsiklis, J.  \harvardyearleft
  1996\harvardyearright , {\em Neuro-Dynamic Programming}, Athena Scientific,
  Massachusetts, Belmont.

\harvarditem{Federgruen \harvardand\ Schweitzer}{1981}{FeSc81}
Federgruen, A. \harvardand\ Schweitzer, P.~J.  \harvardyearleft
  1981\harvardyearright , `Nonstationary {M}arkov decision problems with
  converging parameters', {\em J. Optim. Theory Appl.} {\bf 34}(2),~207--241.

\harvarditem{Hern{\'a}ndez-Lerma}{1989}{Hern89}
Hern{\'a}ndez-Lerma, O.  \harvardyearleft 1989\harvardyearright , {\em Adaptive
  {M}arkov control processes}, Vol.~79 of {\em Applied Mathematical Sciences},
  Springer-Verlag, New York.

\harvarditem{Hern{\'a}ndez-Lerma \harvardand\ Marcus}{1985}{HeMa85}
Hern{\'a}ndez-Lerma, O. \harvardand\ Marcus, S.~I.  \harvardyearleft
  1985\harvardyearright , `Adaptive control of discounted {M}arkov decision
  chains', {\em J. Optim. Theory Appl.} {\bf 46}(2),~227--235.

\harvarditem{Iki, Horiguchi \harvardand\ Kurano}{2007}{IHK07}
Iki, T., Horiguchi, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007\harvardyearright , `A structured pattern matrix algorithm for multichain
  markov decision processes', {\em Mathematical Methods of Operations
  Research,} {\bf electronic version}.

\harvarditem{Iki, Horiguchi, Yasuda \harvardand\ Kurano}{2007{\em a}}{IHYK07}
Iki, T., Horiguchi, M., Yasuda, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007{\em a}\harvardyearright , `A learning algorithm for communicating markov
  decision processes with unknown transition matrices.', {\em {\it (to appear
  in Bulletin of Information and Cybernetics)}} .

\harvarditem{Iki, Horiguchi, Yasuda \harvardand\ Kurano}{2007{\em b}}{IHYK07b}
Iki, T., Horiguchi, M., Yasuda, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007{\em b}\harvardyearright , `Temporal difference-based adaptive policies
  in neuro-dynamic programming.', {\em Vicenc Torra, Yasuo Narukawa, Yuji
  Yoshida (Eds.), 4th International conference on Proceedings of Modeling
  Decisions for Artificial Intelligence (MDAI) 2007 (CD-ROM Proceedings, ISBN
  978-84-00-08539-1),} pp.~112--122.

\harvarditem{Kurano}{1987}{Kura87}
Kurano, M.  \harvardyearleft 1987\harvardyearright , `Learning algorithms for
  {M}arkov decision processes', {\em J. Appl. Probab.} {\bf 24}(1),~270--276.

\harvarditem{Lakshmivarahan}{1981}{Laks81}
Lakshmivarahan, S.  \harvardyearleft 1981\harvardyearright , {\em Learning
  algorithms}, Springer-Verlag, New York.
\newblock Theory and applications.

\harvarditem{Leizarowitz}{2003}{Leiz03}
Leizarowitz, A.  \harvardyearleft 2003\harvardyearright , `An algorithm to
  identify and compute average optimal policies in multichain {M}arkov decision
  processes', {\em Math. Oper. Res.} {\bf 28}(3),~553--586.

\harvarditem{Mandl}{1974}{Mand74}
Mandl, P.  \harvardyearleft 1974\harvardyearright , `Estimation and control in
  {M}arkov chains', {\em Advances in Appl. Probability} {\bf 6},~40--60.

\harvarditem{Martin}{1967}{Mart67}
Martin, J.~J.  \harvardyearleft 1967\harvardyearright , {\em Bayesian decision
  problems and {M}arkov chains}, Publications in Operations Research, No. 13,
  John Wiley \& Sons Inc., New York.

\harvarditem{Puterman}{1994}{Pute94}
Puterman, M.~L.  \harvardyearleft 1994\harvardyearright , {\em Markov decision
  processes: discrete stochastic dynamic programming}, John Wiley \& Sons Inc.,
  New York.
\newblock A Wiley-Interscience Publication.

\harvarditem{Ross}{1970}{Ross70}
Ross, S.~M.  \harvardyearleft 1970\harvardyearright , {\em Applied probability
  models with optimization applications}, Holden-Day, San Francisco, Calif.

\harvarditem{Schweitzer}{1968}{Sc68}
Schweitzer, P.~J.  \harvardyearleft 1968\harvardyearright , `Perturbation
  theory and finite {M}arkov chains', {\em J. Appl. Probability} {\bf
  5},~401--413.

\harvarditem{Sutton \harvardand\ Barto}{1998}{SuBa98}
Sutton, R.~S. \harvardand\ Barto, A.~G.  \harvardyearleft 1998\harvardyearright
  , {\em Reinforcement Learning: An Introduction}, Adaptive Computation and
  Machine Learning, MIT Press, Cambridge, MA.

\harvarditem{van Hee}{1978}{vHee78}
van Hee, K.~M.  \harvardyearleft 1978\harvardyearright , {\em Bayesian control
  of {M}arkov chains}, Vol.~95 of {\em Mathematical Centre Tracts},
  Mathematisch Centrum, Amsterdam.

\end{thebibliography}
\end{document}

\begin{thebibliography}{xx}

\harvarditem{Bather}{1973}{Bath73}
Bather, J.  \harvardyearleft 1973\harvardyearright , `Optimal decision
  procedures for finite {M}arkov chains. {II}. {C}ommunicating systems', {\em
  Advances in Appl. Probability} {\bf 5},~521--540.

\harvarditem{Bertsekas \harvardand\ Tsitsiklis}{1996}{Bert96}
Bertsekas, D. \harvardand\ Tsitsiklis, J.  \harvardyearleft
  1996\harvardyearright , {\em Neuro-Dynamic Programming}, Athena Scientific,
  Massachusetts, Belmont.

\harvarditem{Federgruen \harvardand\ Schweitzer}{1981}{FeSc81}
Federgruen, A. \harvardand\ Schweitzer, P.~J.  \harvardyearleft
  1981\harvardyearright , `Nonstationary {M}arkov decision problems with
  converging parameters', {\em J. Optim. Theory Appl.} {\bf 34}(2),~207--241.

\harvarditem{Hern{\'a}ndez-Lerma}{1989}{Hern89}
Hern{\'a}ndez-Lerma, O.  \harvardyearleft 1989\harvardyearright , {\em Adaptive
  {M}arkov control processes}, Vol.~79 of {\em Applied Mathematical Sciences},
  Springer-Verlag, New York.

\harvarditem{Hern{\'a}ndez-Lerma \harvardand\ Marcus}{1985}{HeMa85}
Hern{\'a}ndez-Lerma, O. \harvardand\ Marcus, S.~I.  \harvardyearleft
  1985\harvardyearright , `Adaptive control of discounted {M}arkov decision
  chains', {\em J. Optim. Theory Appl.} {\bf 46}(2),~227--235.

\harvarditem{Iki, Horiguchi \harvardand\ Kurano}{2007}{IHK07}
Iki, T., Horiguchi, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007\harvardyearright , `A structured pattern matrix algorithm for multichain
  markov decision processes', {\em Mathematical Methods of Operations
  Research,} {\bf electronic version}.

\harvarditem{Iki, Horiguchi, Yasuda \harvardand\ Kurano}{2007{\em a}}{IHYK07}
Iki, T., Horiguchi, M., Yasuda, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007{\em a}\harvardyearright , `A learning algorithm for communicating markov
  decision processes with unknown transition matrices.', {\em {\it (to appear
  in Bulletin of Information and Cybernetics)}} .

\harvarditem{Iki, Horiguchi, Yasuda \harvardand\ Kurano}{2007{\em b}}{IHYK07b}
Iki, T., Horiguchi, M., Yasuda, M. \harvardand\ Kurano, M.  \harvardyearleft
  2007{\em b}\harvardyearright , `Temporal difference-based adaptive policies
  in neuro-dynamic programming.', {\em Vicenc Torra, Yasuo Narukawa, Yuji
  Yoshida (Eds.), 4th International conference on Proceedings of Modeling
  Decisions for Artificial Intelligence (MDAI) 2007 (CD-ROM Proceedings, ISBN
  978-84-00-08539-1),} pp.~112--122.

\harvarditem{Kurano}{1987}{Kura87}
Kurano, M.  \harvardyearleft 1987\harvardyearright , `Learning algorithms for
  {M}arkov decision processes', {\em J. Appl. Probab.} {\bf 24}(1),~270--276.

\harvarditem{Lakshmivarahan}{1981}{Laks81}
Lakshmivarahan, S.  \harvardyearleft 1981\harvardyearright , {\em Learning
  algorithms}, Springer-Verlag, New York.
\newblock Theory and applications.

\harvarditem{Leizarowitz}{2003}{Leiz03}
Leizarowitz, A.  \harvardyearleft 2003\harvardyearright , `An algorithm to
  identify and compute average optimal policies in multichain {M}arkov decision
  processes', {\em Math. Oper. Res.} {\bf 28}(3),~553--586.

\harvarditem{Mandl}{1974}{Mand74}
Mandl, P.  \harvardyearleft 1974\harvardyearright , `Estimation and control in
  {M}arkov chains', {\em Advances in Appl. Probability} {\bf 6},~40--60.

\harvarditem{Martin}{1967}{Mart67}
Martin, J.~J.  \harvardyearleft 1967\harvardyearright , {\em Bayesian decision
  problems and {M}arkov chains}, Publications in Operations Research, No. 13,
  John Wiley \& Sons Inc., New York.

\harvarditem{Puterman}{1994}{Pute94}
Puterman, M.~L.  \harvardyearleft 1994\harvardyearright , {\em Markov decision
  processes: discrete stochastic dynamic programming}, John Wiley \& Sons Inc.,
  New York.
\newblock A Wiley-Interscience Publication.

\harvarditem{Ross}{1970}{Ross70}
Ross, S.~M.  \harvardyearleft 1970\harvardyearright , {\em Applied probability
  models with optimization applications}, Holden-Day, San Francisco, Calif.

\harvarditem{Schweitzer}{1968}{Sc68}
Schweitzer, P.~J.  \harvardyearleft 1968\harvardyearright , `Perturbation
  theory and finite {M}arkov chains', {\em J. Appl. Probability} {\bf
  5},~401--413.

\harvarditem{Sutton \harvardand\ Barto}{1998}{SuBa98}
Sutton, R.~S. \harvardand\ Barto, A.~G.  \harvardyearleft 1998\harvardyearright
  , {\em Reinforcement Learning: An Introduction}, Adaptive Computation and
  Machine Learning, MIT Press, Cambridge, MA.

\harvarditem{van Hee}{1978}{vHee78}
van Hee, K.~M.  \harvardyearleft 1978\harvardyearright , {\em Bayesian control
  of {M}arkov chains}, Vol.~95 of {\em Mathematical Centre Tracts},
  Mathematisch Centrum, Amsterdam.

\end{thebibliography}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
