\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 Markov decision processes based on temporal difference method}\\[5pt]
{\small 
\begin{tabular}{lllll}
伊喜哲一郎&（宮崎大学教育文化学部)&&堀口正之&（弓削商船高専総合教育科）\\%{\it %Department of Information Environment Engineering,
安田正實&（千葉大学理学部）&&蔵野正美&（千葉大学教育学部）
\end{tabular}
}%{\it Faculty of Education, Chiba University}}
\smallskip

\begin{minipage}{.95\textwidth}
We consider an adaptive model for uncertain Markov decision processes(MDPs) 
with the average reward criterion.
In our previous work \cite{IHYK06}, the adaptive policies are
constructed by applying the methods of value iteration, cooperated
with the policy improvement(cf.\ \cite{Pute94}), 
in which the corresponding value function is approximated 
through the expectation with respect to the estimated transition 
matrices at each learning step.   
In this paper, under the minorization condition, we construct an adaptive policy
based on temporal difference method in neuro-dynamic programming.
By the stochastic iteration algorithm, the estimated value function
is updated using temporal difference and adaptive policy are constructed
as an $\varepsilon$-forced modification of the greedy policy for
the estimates of value function and transition probability matrices.

\noindent{\bf Key words}:
Adaptive Markov decision processes, neuro-dynamic programming,
temporal difference, average case.
\end{minipage}
\end{center}


%%%%%%%%%%%%%% Sec. 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf\large 1. Introduction and notation}\\
%We 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$, which consist of finite $N$ and $K$ elements respectively.
For any $\delta > 0$, let $\bQ_\delta$ denote the parameter space of $K$ 
unknown stochastic matrices, defined by\vspace{-6pt}
\begin{equation} \label{mino}
\textstyle  \bQ_\delta = \bigl\{ q =(q_{ij}(a)) \bigm\vert q_{ij}(a) \geqq \delta,
  \sum_{j \in S} q_{ij}(a) = 1 \ \text{ for } \ i,j \in S, a \in A
  \bigr\}.\vspace{-6pt}
\end{equation}
%Throughout this paper, all the transition matrices which we are dealing with 
%are satisfying the minorization condition above(cf.\ \cite{Numm84}).
A transition matrix of this class $\bQ_{\delta}$ is %called that
the minorization condition (named after \cite{Numm84}) %is satisfied 
and is assumed throughout the paper.
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 there exist a conditional probability $\xi=(\xi(\cdot|i):i\in S)\in
%P(A|S)$ such that
%$\pi_{t}(\cdot|x_0,a_0,\ldots,x_t)=\xi(\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 $\xi$.   
%We denote by $F$ the set of  functions on $S$ with
%$f(i)\in A$ for all $i\in S$.
%A policy $\pi$ is called stationary
%if there exists a $f\in F$ such that a conditional probability 
%$\pi_{t}(f(x_t)|x_0,a_0,\ldots,x_t)=1$
%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 $f$.
A randomized stationary policy $\xi$ and a stationary policy $f$ are 
defined by a usual way (cf.\ \cite{IHYK06,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$.

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)$.



Then, for any fixed $\delta > 0$, the problem is to maximize 
$ \psi(i, q \vert \pi ) $ over all $\pi \in \Pi$ for $ i \in S$
and $ q \in \bQ_{\delta}$.
Thus, for $q\in \bQ_{\delta}$ denoting by $\psi(i,q)$ the value function, i.e.,\vspace{-6pt}
\begin{equation}\label{eq(1.2)}
\textstyle  \psi(i,q)=\sup_{\pi\in\Pi}\psi(i,q|\pi),\vspace{-6pt}
%\tag{1.2}
\end{equation}
$\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 if 
$\pi^{*}$ is $q$-optimal for all $q\in \bQ_{\delta}$.





%\harvardparenthesis{round}

%%%%%%%%%%%%%%%%%%%%%%%%%%% sec. 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf\large 2. Preliminary lemmas}\\
Let $B(S)$ be the set of all functions on $S$.
For any $q \in \bQ_\delta$, we define the map $U\{q\}: B(S) \rightarrow 
B(S)$ by\vspace{-6pt}
\begin{equation}\label{eq:(2.2)}
\textstyle   U\{q\} u(i) = \max_{a \in A} \bigl\{ r(i,a) + \sum_{j \in S} 
     \bigl( q_{ij}(a) - \delta \bigr) u(j) \bigr\}\vspace{-6pt}
\end{equation}
Let $ h(q) \in B(S)$ be unique fixed point of $U(q)$. 

\begin{lem}\label{lem:2.2}
  Let $q \in \bQ_\delta$. Then, $\psi^*(q) = \psi(i,q)$ 
(independent of \ $i \in S$) and if $f(i)\in A^{*}(i|q)$ for all $i\in S$,
$f$ is $q$-optimal, where $\psi^*(q) = \delta \sum_{j \in S} h(q)(j)$ and $A^{*}(i|q)$ is the set of optimal actions 
at state $i$ and
  $A^*(i \vert q) = 
   \aM_{ a \in A} \bigl\{  r(i,a) - \psi^{*}(q) 
            + \sum_{j \in S} q_{ij}(a) h(q)(j) \bigr\}$.
%
%\biggl\{ a \in A \biggm\vert \mbox{ \mbox{the elements of}\, $a$ maximize 
%   the right-hand side of (\ref{eq:(2.4)})} \biggr\}$
\end{lem}
\medskip

For any map $H: B(S) \rightarrow B(S)$, we consider the stochastic
algorithm $\{ \tilde{v}_t \}$ for $\{X_t\}_{t=0}^{\infty} $ on $S$, whose update equations are 
described by, for $i \in S$,\vspace{-6pt}
\begin{equation}\label{eq:(2.5)}
%   \begin{array}{l}
      \tilde{v}_0(i) \equiv 0, %\\
      \tilde{v}_{t+1}(i) = \bigl( 1- \tilde{\gamma}_t(i)\bigr)\tilde{v}_t(i) 
          + \tilde{\gamma}_t(i) 
            \Bigl( H\tilde{v}_t(i) + W_{t}(i) +u_{t}(i)\Bigr),  \quad t \geqq 0
            \vspace{-6pt}
%   \end{array}
\end{equation}
where $\tilde{\gamma}_t(i)$ is defined for 
a given sequence $\{\gamma_t(i)\}$ by
$\tilde{\gamma}_t(i) = \gamma_t(i)$ if $ X_t = i$ and $ =0$ otherwise.
Also, $\{W_{t}(i)\}$ and $\left\{u_{t}(i)\right\}$ are  random noise terms 
depending on $i \in S$.

\begin{lem}[cf. Proposition 4.5 in \cite{Bert96}]      \label{lem:2.3}
  Suppose that the following condition (i) -- (v) are assumed to hold.
%  \begin{itemize}
 \textit{(i)} %   \item[{(i)}] 
$E[W_{t}(i) \vert {\cal F}_t] = 0$
                 for $i \in S$
 \textit{(ii)} %    \item[{(ii)}] 
There exist $A,B > 0$ such that
%      $$
$         E\bigl[W_{t}(i)^2 \bigm\vert {\cal F}_t \bigr] 
         \leqq A + B \| \tilde{v}_t\|^2
$%      $$
      for $t\geqq 0$ and $i\in S$.
 \textit{(iii)} %    \item[{(iii)}]
      $H$ is a contraction operator with a unique fixed point $v^* \in B(S)$.
 \textit{(iv)} %    \item[{(iv)}]
      $\tilde{\gamma}_{t}(i) \geqq 0$, $\sum_{t=0}^{\infty} \tilde{\gamma}_t(i) = \infty$
      and $\sum_{t=0}^{\infty} \tilde{\gamma}_t(i)^2 < \infty$
      for $t \geqq 0$, $ i\in S$.
 \textit{(v)} %    \item[{(v)}]
      There exists a nonnegative random sequence $\{\theta_{t}\}$ such that 
%	  $$
$|u_{t}(i)|\leqq\theta_{t}(||\tilde{v}_{t}||+1)$
%$$
	  for $i\in S$ and $t\geqq 0$ and $\{\theta_{t}\}$ converges to
      zero with probability 1. 
%  \end{itemize}
  Then, $\tilde{v}_t$ in (\ref{eq:(2.5)}) converges to $v^*$ with
  probability 1, where $||\cdot||$ is a supremum norm and
  ${\cal F}_t$ is a minimal $\sigma$-field generated by 
  $\bigl\{ X_\ell ( \ell \leqq t) , W_\ell ( \ell \leqq t-1),U_{\ell}(\ell\leqq t-1) \bigr\}$. 
\end{lem}
\medskip


%%%%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf \large 3. Temporal difference-based adaptive policies}\\
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$,}\\
                   {N_{n}(i,j|a)}/{N_{n}(i|a)} \text{ if $N_{n}(i|a)>0$,}
                   %0 & \text{otherwise}.
                   =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_{\delta}$,
we define $\tilde{q}^{n}=(\tilde{q}^{n}_{ij}(a))\in \bQ_{\delta}$ by
%\[
$  \tilde{q}^{n}_{ij}(a)=
%   \begin{cases}
    q^{n}_{ij}(a)$ if $N_{n}(i|a)>0$,
    $=q^{0}_{ij}(a) \text{ otherwise}.$
%   \end{cases}
%\]
The adaptive policy is constructed in the following 
TD-based learning algorithm ``{Algorithm ($*$)}'' %with the sequence $\{q_{t}(i)\}_{t=0}^{\infty}$
%with $i\in S$ and $0<q_{t}(i)<1$.  
with the sequences $\{\varepsilon_{t}(i)\}_{t=0}^{\infty}$ for each $i\in S$ 
such that $0<\varepsilon_{t}(i)<1$ for $t\geqq 0$ and $i\in S$.

  %枠で囲む
%\newpage
%\medskip
\noindent{\bf Algorithm ${\bm{(*)}}$:}\label{alg:1}\vspace{-6pt} 
\begin{list}{\textbullet}{\itemsep=-6pt}%
  \item[step 1.] Set $t=0$ and $\tilde{v}_0 \equiv 0$ and let $\tilde{\pi}_0 \in P(A|S)$ 
        with  $\tilde{\pi}_0(a | i) > 0 $ for all $a \in A$
        and $i \in S$.  
  \item[step 2.] Suppose that $\tilde{\pi}_t \in 
        P\bigl(A \bigm| (S\times A)^t \times S \bigr)$ 
        and $\tilde{v}_t \in B(S)$ are given and $\Delta_t$ is chosen
        according to $\tilde{\pi}_t$.  
		Observe the next state $X_{t+1}=j$ selected according to 
		the state $X_t=i$ and $\Delta_{t}$.\\ 
		At the stage $t+1$, determine
        $\tilde{v}_{t+1} \in B(S)$ by the TD-based update equation:
        for $i \in S$,\vspace{-6pt}
        \begin{equation}                        \label{update-eq}
        %$$
\textstyle     \tilde{v}_{t+1}(i) = \bigl(1 - \tilde{\gamma}_t(i) \bigr)
               \tilde{v}_t(i) +  \tilde{\gamma}_t(i) 
               \bigl( r(i, \Delta_t) + \tilde{v}_t(X_{t+1}) - 
               \delta \sum_{\ell \in S} \tilde{v}_t(\ell)    \bigr)\vspace{-6pt}
        %\eqno{(3.1)}
        %$$
        \end{equation}
        where the step size 
        $\tilde{\gamma}_t$ is defined as in (\ref{eq:(2.5)}) %$\tilde{\gamma}_t(i) = \gamma_t(i)$
        %if $X_t = i$, and  $= 0$ otherwise, 
        for a sequence $\{ \gamma_t(i)\}$. 
  \item[step 3.] Let $\tilde{a}_{t+1}(i) \in \aM_{a \in A} 
        \bigl\{ r(i,a) + 
         \sum_{j \in S} \tilde{q}_{ij}^{t}(a) \tilde{v}_{t+1}(j)
        \bigr\}$ for each $i \in S$. Then the policy $\tilde{\pi}_{t+1}$ 
        is given by\vspace{-6pt}
        \begin{equation}\label{md-policy}
		\tilde{\pi}_{t+1}(a|i)=%\frac{\varepsilon_{t}(i)}{K(i)-1} \text{ if }
        \varepsilon_{t}(i)/(K(i)-1) \text{ if }
		a\neq \tilde{a}_{t+1}(i), =1-\varepsilon_{t}(i) 
		\text{ if } a=\tilde{a}_{t+1}(i),\vspace{-6pt}
        %\eqno{(3.2)}
        \end{equation}
        where $K(i)$ denotes the number of actions in state $i$.
  \item[step 4.] Set $t = t +1 $ and return to step 2.
\end{list}
%\vskip3mm \hrule} %枠で囲む終わり 
%\vskip10mm
\vspace{-6pt}

\noindent{\bf Condition $\bm{(*)}$}
%\begin{itemize}
~~~%\item[(i)] 
(i) $\lim_{t\to\infty}\varepsilon_{t}(i)=0$ and $\sum_{t=0}^{\infty}
\varepsilon_{t}(i)=\infty$,
%\item[(ii)] 
~(ii) $\gamma_{t}(i)\geqq0,\sum_{t=0}^{\infty}\gamma_{t}(i)=\infty$ and
$\sum_{t=0}^{\infty}\gamma_{t}(i)^{2}<\infty$ for all $i\in S.$
%\end{itemize}
\medskip

\begin{thm}\label{thm:3.1}
Suppose that Condition ($*$) holds and $q=(q_{ij}(a))\in \bQ_{\delta}$ with
$\delta>0$. Then, $\tilde{v}_{t}(i)\to h(q)(i)$ as $t\to \infty$
with $P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$-probability 1.
\end{thm} 
\medskip

\begin{thm}
Let $\delta>0$ be arbitrary.
Suppose that Condition ($*$) holds. Then,
$\tilde{\pi}$ is adaptively optimal for $\bQ_{\delta}$.
\end{thm}

\medskip

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

\begin{small}
\noindent{\bf References}\\
\noindent[1] \begin{minipage}[t]{.95\textwidth}
D.P. Bertsekas and J.H. Tsitsiklis.
\newblock {\em Neuro-Dynamic Programming}.
\newblock Athena Scientific, Massachusetts, Belmont, 1996.
\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 {\it (to appear in Bulletin of Information and Cybernetics)}.
\end{minipage}

\noindent[3] \begin{minipage}[t]{.95\textwidth}
Esa Nummelin.
\newblock {\em General irreducible {M}arkov chains and nonnegative operators},
  volume~83 of {\em Cambridge Tracts in Mathematics}.
\newblock Cambridge University Press, Cambridge, 1984.
\end{minipage}

\noindent[4] \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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\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}