\documentclass[a4paper,11pt,leqno]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{bm}
\usepackage{array}
%\usepackage{arydshln}
\usepackage{multirow}
\usepackage{graphicx,color}
\usepackage{float}
\usepackage{pst-all}
%\usepackage{harvard}
\usepackage{fancybox}
%\renewcommand{\harvardand}{and}
%\citationmode{abbr}
\usepackage{lscape}
\usepackage{pstcol}
\usepackage{slashbox}

\setlength{\oddsidemargin}{-3mm}
\setlength{\textwidth}{16.5cm}
\setlength{\textheight}{23.5cm}
%\setlength{\mathindent}{20mm}
\setlength{\topmargin}{-10mm}
\setlength{\headsep}{4mm}
\setlength{\headheight}{5mm}
\setlength{\abovedisplayskip}{1pt}   % 数式環境の上部のマージン
\setlength{\belowdisplayskip}{1pt}   % 数式環境の下部のマージン
\setlength{\itemsep}{2pt}            % item 間の改行幅
\setlength{\topsep}{-6pt}                  % 最初の \item と前段落との間の空白
\setlength{\partopsep}{7pt}             % 環境を新しい段落で始めた時の空白
\setlength{\floatsep}{4pt}           % 図表と図表の間のマージン
\setlength{\dblfloatsep}{3pt}        % ↑の二段組 version
\setlength{\textfloatsep}{-5pt}       % 図表と本文の間のマージン
\setlength{\abovecaptionskip}{3pt}   % 図表の caption と図表本体の間のマージン
\setlength{\belowcaptionskip}{3pt}   % 図表の caption 下部のマージン
\renewcommand{\arraystretch}{0.95}    % table / array の行間のマージン

\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}}
\DeclareMathOperator*{\aM}{\mathrm{arg\,max}}

\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}
%\theoremstyle{defenition}

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

%\pagestyle{empty}
\usepackage{fancyhdr}
%\usepackage{mymacros}
\renewcommand{\headrulewidth}{0pt}%\vbox to 0pt{\hbox%
%to \headwidth{\dotfill}\vss}}
%\lhead{\scriptsize {\sf A learning algorithm for communicating MDPs with unknown transition matrices}}%
%\chead{}%
\lhead{}%
\rhead{\scriptsize {\texttt{\colorbox[gray]{0.4}{Draft.5. \today}}}}
%\rhead{{\scriptsize Draft 4. \today}}
%}%

  \definecolor{lightblue}{rgb}{.68, .85, .9}
  \definecolor{greengold}{rgb}{.72,.77,.42}
  \definecolor{aplicot}{rgb}{1,0.32,0}
  \definecolor{cream}{rgb}{1,.9,.8}
  \newcmykcolor{olivegreen}{0.64 0 0.95 0.4}
  \newcmykcolor{skyblue}{0.62 0 0.12 0}

%\fancyfoot{\thepage}
%%%%%%    TEXT START    %%%%%%
\begin{document}
\pagestyle{empty}
%\thispagestyle{fancy}
\begin{center}
{\large\bf Adaptive algorithm for Markov decision processes using pattern-matrix learning method}\\[5pt]
{\small 
\begin{tabular}{lllll}
伊喜哲一郎&（宮崎大学教育文化学部)&&堀口正之&（神奈川大学工学部）\\
安田正實&（千葉大学理学部）&&蔵野正美&
\end{tabular}
}
\smallskip

\begin{minipage}{.95\textwidth}
This note is concerned with adaptive algorithm for uncertain Markov decision processes(MDPs) with the average reward criterion.
As a sequel to \cite{IHYK07}, we consider the learning algorithm for investigating 
the structure of unknown transition matrices and getting adaptive policy in regularly 
communicating model where the state space is decomposed into a single communicating 
class and a transient class.
Using pattern matrix learning method, we have an asymptotic sequence of adaptive policies
with nearly average optimal properties.

\noindent{\bf Key words}:
adaptive Markov decision processes,
pattern-matrix learning algorithm,
average-optimal adaptive policy,
regularly communicating case.
\end{minipage}
\end{center}
\smallskip

%%%%%%%%%%%%%% Sec. 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf\large 1. Notation}\\
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.,\vspace{-6pt}
\begin{equation}\label{eq(1.1)}
\bQ=\{q=(q_{ij}(a))\vert q_{ij}(a)\geqq 0 , 
\textstyle\sum_{j\in S}q_{ij}(a)=1 \ \text{for}\ i,j\in S \ \text{and}\ a\in A(i)\}.\vspace{-6pt}
\end{equation}

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 $(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 randomized stationary policy $\xi$ and a stationary policy $f$ are 
defined by a usual way (cf.\ \cite{Pute94}).  

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))$, 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$.
$H_{n-1}=(X_0,\Delta_0, %X_1,
\ldots,X_{n-1})$ denotes a history until the $(n-1)$-th step.
Let $n(D)$ denotes the number of elements in a set $D$.


For a given reward function $r$ on $S\times A$, we shall consider
the long-run expected average reward:\vspace{-6pt}
\begin{equation}\label{eq(1.1)}
\textstyle  \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)\vspace{-6pt}
%\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\vspace{-6pt}
\begin{equation}\label{eq(1.3)}
 \textstyle \psi(i,q)=\sup_{\pi\in\Pi}\psi(i,q|\pi),\vspace{-6pt}
\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$.
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$.

Let $q\in \bQ$. A subset $E\subset S$ is called 
a communicating class for $q$ if %
%\begin{itemize}\label{def:comclass}
%\item[(i)] 
(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)] 
(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)] 
(i) $\Bar{E}$ is a communicating class for $q$ and
%\item[(ii)] 
(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)$.


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}.





%\harvardparenthesis{round}

%%%%%%%%%%%%%%%%%%%%%%%%%%% sec. 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent{\bf\large 2. Preliminary lemmas}%\\
% 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}\\
%  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}
%%
% \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),$\vspace{-6pt}
\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}

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:\vspace{-6pt}
%\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$},\\
%&
\begin{equation}
\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}},~(n\geqq 1)\vspace{-6pt}
\end{equation}
%&\text{
where $\min \emptyset=\infty, \sigma_{0}=0,E_{0}:=\{i_{0}\}$ and 
$T_{0}:=\Bar{E}(q)-E_{0}$.%}.
%\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)] 
(i) $P_{\tilde{\pi}}(\Bar{n}(E)<\infty\vert X_{0}=i_{0},q)=1$, and
%\item[(ii)] 
(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}
\medskip


%%%%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf \large 3. Pattern-matrix learning algorithms}\\
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)}$(cf.~\cite{IHYK07}).  

\noindent{\underline{$\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$:}}\label{alg:PMLA} 
\begin{list}{\textbullet}{\itemsep=-6pt}%
%\begin{enumerate}
  \item[1.] Set $E_{0}=\{i_{0}\}, T_{0}=S-E_{0},\tilde{v}_0(i_{0}) = 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[2.] 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[3.] 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 
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\vspace{-6pt}
		\begin{equation}
		q^{n+1}_{ij}(a)=%\begin{cases}
		\textstyle\frac{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))\vspace{-6pt}
		\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}$.\\[-12pt]
  \item[4.] For each $i\in E_{n+1},$ choose $\tilde{a}_{n+1}(i)$ which satisfies\vspace{-6pt}
        \[\textstyle\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)\}\vspace{-6pt}
        \]
		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:\vspace{-6pt} 
		\begin{equation}
		\textstyle\tilde{\pi}_{n+1}^{\tau}(a_{i}|i)=
		%\begin{cases}
		1-\sum_{a\neq a_{i}}\phi (\tilde{\pi}_{n}^{\tau}(a|i)) %&
		 \text{ if $a_{i}=\tilde{a}_{n+1}(i))$, } %\\
		=\phi(\tilde{\pi}_{n}^{\tau}(a_{i}\vert i)) %& 
		\text{ if $a_{i}\neq \tilde{a}_{n+1}(i)$ }.
		%\end{cases}
		\vspace{-6pt}
		\end{equation}
		%Moreover, put 
		Put $\tilde{v}_{n+1}=U_{\tau}\{q^{n+1}\}\tilde{v}_{n}$ on $E_{n+1}$.
  \item[5.] Set $n \leftarrow n +1 $ and return to step 3.
%\end{enumerate}
\end{list}

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

\noindent{\bf Condition ($\bm{*}$)}%\vspace{-6pt}
%\begin{equation}
~~~~$\textstyle b_n \to 0 \ \text{as $n\to\infty$ and $\sum_{n=0}^{\infty}b_{n}^{N}=\infty$}.$%
%\vspace{-6pt}
%\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$.

Combining the vanishing discount approach(cf.~\cite{IHYK07,Pute94}) as letting $\tau\to 0$
with $\textbf{PMLA} \bm{(i_0,\{b_n\},\tau)}$, we have the policy 
$\tilde{\pi}^{\tau}=(\tilde{\pi}_{0}^{\tau},%\tilde{\pi}_{1}^{\tau},
\ldots)$ 
which has nearly average-optimal properties for $\bQ^{*}(i_{0})$ as follows:
 
\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}
\medskip

%%%%%%%%%%%%%%%%%%%%%% sec. 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf\large 4. A numerical experiment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%








\begin{small}
\noindent{\bf References}\\
\noindent[1] \begin{minipage}[t]{.95\textwidth}
T.~Iki, M.~Horiguchi, M.~Yasuda, and M.~Kurano.
\newblock Adaptive {Markov} decision processes based on temporal difference
  method.
\newblock {\em 日本数学会2007年度秋季 統計数学分科会講演アブストラクト}, 125--126, 2007.
\end{minipage}

\noindent[2] \begin{minipage}[t]{.95\textwidth}
T.~Iki, M.~Horiguchi, M.~Yasuda, and M.~Kurano.
\newblock A learning algorithm for communicating {Markov} decision processes with
  unknown transition matrices.
\newblock {\em Bulletin of Information and Cybernetics}, 39:11--24, 2007.
\end{minipage}

\noindent[3] \begin{minipage}[t]{.95\textwidth}
Martin~L. Puterman.
\newblock {\em {Markov} decision processes: discrete stochastic dynamic
  programming}.
\newblock John Wiley \& Sons Inc., New York, 1994.
\newblock A Wiley-Interscience Publication.
\end{minipage}
\end{small}

\nocite{IHYK07m}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{scriptsize}
%\harvardyearparenthesis{non}
%\bibliographystyle{agsm}
%\thispagestyle{fancy}
\bibliographystyle{plain}
%\addcontentsline{toc}{chapter}{Bibliography}
\bibliography{myrefs.bib}
\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{plain}
\addcontentsline{toc}{chapter}{Bibliography}
\begin{thebibliography}{10}

\bibitem{Bath73}
J.~Bather.
\newblock Optimal decision procedures for finite {M}arkov chains. {II}.
  {C}ommunicating systems.
\newblock {\em Advances in Appl. Probability}, 5:521--540, 1973.

\bibitem{Bill61}
P.~Billingsley.
\newblock {\em Statistical inference for {M}arkov processes}.
\newblock Statistical Research Monographs, Vol. II. The University of Chicago
  Press, Chicago, Ill., 1961.

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

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

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

\bibitem{IHK05}
T.~Iki, M.~Horiguchi, and M.~Kurano.
\newblock A structured pattern matrix algorithm for multichain markov decision
  processes.
\newblock ({\it preprint}).

\bibitem{KmSn60}
J.~G. Kemeny and J.~L. Snell.
\newblock {\em Finite {M}arkov chains}.
\newblock The University Series in Undergraduate Mathematics. D. Van Nostrand
  Co., Inc., Princeton, N.J.-Toronto-London-New York, 1960.

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

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

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

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

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

\bibitem{Lo63}
M.~Lo{\`e}ve.
\newblock {\em Probability theory}.
\newblock Third edition. D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto,
  Ont.-London, 1963.

\bibitem{Mand74}
P.~Mandl.
\newblock Estimation and control in {M}arkov chains.
\newblock {\em Advances in Appl. Probability}, 6:40--60, 1974.

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

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

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

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

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

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

\bibitem{SuBa98}
R.~S. Sutton and A.~G. Barto.
\newblock {\em Reinforcement Learning: An Introducution}.
\newblock Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA,
  1998.

\bibitem{vHee78}
K.~M. van Hee.
\newblock {\em Bayesian control of {M}arkov chains}, volume~95 of {\em
  Mathematical Centre Tracts}.
\newblock Mathematisch Centrum, Amsterdam, 1978.

\end{thebibliography}

%\end{scriptsize}
%\end{slide}
\end{document}