%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                             %
% Temporal Difference-based Adaptive policies in Neuro        %
%    Dynamic Programming                                      %
%
%    cd. NeuroMDPJan07/TD_neuroMDPs4                                                             %
%    cf. LA_for_CMDP                                          %
%                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 2007.01.08     Sec.4(Example) added
% 2007.01.12     main algorithm is revised(epsilon-forced greedy policy&Lem2.3)
% 2007.01.22     For style of MDAI
% 2007.01.28     reformatted and modified for LNCS style
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[runningheads]{llncs}
\usepackage{makeidx}  % allows for indexgeneration
\usepackage{amssymb}  %
\usepackage{amsmath}  %
%\usepackage{amsthm}  %Theorem environment are pre-defined!
\usepackage{bm}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{pst-all}
\usepackage{slashbox}
\spnewtheorem{prop}[proposition]{Proposition}{\bfseries}{\itshape}
\spnewtheorem{thm}[theorem]{Theorem}{\bfseries}{\itshape}
\spnewtheorem{lem}[lemma]{Lemma}{\bfseries}{\itshape}
\newcommand{\bQ}{\mathbb{Q}}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%
\frontmatter          % for the preliminaries
\pagestyle{headings}  % switches on printing of running heads
\mainmatter              % start of the contributions
%\addtocmark{Hamiltonian Mechanics} % additional mark in the TOC
%
%
%
% second contribution with nearly identical text,
% slightly changed contribution head (all entries
% appear as defaults), and modified bibliography
%
\title{Temporal Difference-based Adaptive policies in Neuro-dynamic Programming}
\titlerunning{TD-based Adaptive policies in Neuro-DP}
%
\author{
  T. IKI\inst{1}, M. HORIGUCHI\inst{2}, M. YASUDA\inst{3} and M. KURANO\inst{4}}
\institute{
  Faculty of Education and Culture, Miyazaki University
       Miyazaki 889-2192 Japan,
       \email{e03101u@cc.miyazaki-u.ac.jp}
\and
  General Education, Yuge National College of Maritime Technology,
       Ehime 794-2593 Japan,
       \email{horiguchi@gen.yuge.ac.jp}
\and
  Faculty of Science, Chiba University
       Chiba 263-8522 Japan,
       \email{yasuda@math.s.chiba-u.ac.jp}
\and
   Faculty of Education, Chiba University
       Chiba 263-8522 Japan
       \email{kurano@faculty.chiba-u.jp}
}% end of institute
%
\maketitle
\begin{abstract}
Based on temporal difference method in neuro-dynamic programming,
an adaptive policy for 
%a 
finite state 
Markov decision processes with the average reward
is constructed 
under the minorization condition.
We estimate the value function by a learning iteration algorithm.
% using temporal differences 
And the adaptive policy is specified as an
$\varepsilon$-forced modification of the greedy policy 
for the estimated value and the estimated transition probability matrix.
Also, a numerical experiment for ``Toymaker's problem''
is given to illustrate the validity of the adaptive policy.
\end{abstract}
%
{\it Keywords:} 
adaptive Markov decision processes,
temporal difference method,  
average reward,
minorization condition,
neuro-dynamic programming.
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction and notation}\label{Sec1}
%section 1
  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,Kura87,Mand74,Mart67} and so on.
The idea of neuro-dynamic programming 
by \cite{Bert96} seems a recent breakthrough in the practical 
application of neural networks and dynamic programming to complex 
problems of planning, optimal decision making, and intelligent control.
%�@In: Putterman(1994)
%is powerful in treating the adaptive MDPs.
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 order to decrease the amount of computation necessary for a learning
algorithm, we can use the idea of temporal-difference method(TD-method)
in neuro-dynamic programming\cite{ABB01,Bert96,BoMn00,KoBo99,SuBa98}, 
that is,
the data of the state-action process are directly used for value iteration 
and policy improvement at each learning step, by which the amount of 
computation is reduced to some extent.

In this paper, based on TD-method, we propose a way of constructing
an adaptive policy for the average reward criterion.
In fact, we will estimate the value function by the stochastic iteration algorithm
% ``will'' inserted 
that updates the value estimate iteratively using temporal differences made from
the data of state-action process and adaptively optimal policies for a class of
MDPs satisfying the minorization condition are constructed as
an $\varepsilon$-forced modification of the greedy policy for the
estimated value and transition probability matrices.
Also, a numerical experiment for ``Toymaker's problem'' in Howard\cite{Howd60} is given to illustrate the validity of 
the adaptive policy we have proposed here. 


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.



For any $\delta > 0$, let $\bQ_\delta$ denote the parameter space of $K$ 
unknown stochastic matrices, defined by
\[
  \bQ_\delta = \left\{ q =(q_{ij}(a)) \Biggm\vert q_{ij}(a) \geqq \delta,
  \sum_{j \in S} q_{ij}(a) = 1 \ \text{ for } \ i,j \in S, a \in A
  \right\}.
\]
Throughout this paper, all the tranisition matrices which we are dealing with 
are satisfying the minorization condition above(cf.\ \cite{Numm84}).

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 $\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 randomized stationary policy $\xi$ is called stationary if
there exists a function $f\in F$ with $\xi(\{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.1)}
  \psi(i,q|\pi)=
  \liminf_{T\to\infty}\frac{1}{T+1}E_{\pi}\left(
  \sum_{t=0}^{T}r(X_{t},\Delta_{t}) \Biggm| X_0=i,q
  \right)
%\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.,
\begin{equation}                                   \label{eq(1.2)}
  \psi(i,q)=\sup_{\pi\in\Pi}\psi(i,q|\pi),
%\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}$.


In Section \ref{Sec2}, several lemmas are prepared, which 
are used to prove the validity of adaptive policies. 
These notions are proposed in Section \ref{Sec3}.
A numerical experiment is given in Section \ref{Sec4}.



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

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

Let $B(S)$ be the set of all functions on $S$.
The following fact is well-known
%\citeaffixed{Pute94,Ross70}{cf.}.
(cf.\ \cite{Pute94}).
%\harvardparenthesis{non}
\begin{lem}[Puterman \cite{Pute94%,Ros70
  }]                                                \label{lem:2.1}
  Let $q=(q_{ij}(a))\in\bQ_{\delta}.$
  Supposed that there exists a constant $g$ and a $v\in B(S)$ such that
    \begin{equation}                                      \label{eq:(2.1)}
      v(i)=\max_{a\in A}\{
        r(i,a)+\sum_{j\in S}q_{ij}(a)v(j)
       \}-g
       \ \ \text{for all $i\in S$}.
    %\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 (\ref{eq:(2.1)}) for all $i\in S$.
\end{lem}

For any $q \in \bQ_\delta$, we define the map $U\{q\}: B(S) \rightarrow 
B(S)$ by
\begin{equation}                                          \label{eq:(2.2)}
   U\{q\} u(i) = \max_{a \in A} \biggl\{ r(i,a) + \sum_{j \in S} 
     \bigl( q_{ij}(a) - \delta \bigr) u(j) \biggr\}
\end{equation}

\noindent
Then, $U(q)$ is easily proved to be a contraction mapping, so that there is a fixed point.
Let $ h(q) \in B(S)$ be unique fixed point of $U(q)$. 
We have the optimality equation for the average case:
\begin{equation}                                          \label{eq:(2.3)}
   h(q) = U\{q\} h(q) \quad \mbox{for each} \quad q \in \bQ_{\delta}.
\end{equation}
\noindent
Putting $\psi^*(q) = \delta \sum_{j \in S} h(q)(j)$ in 
(\ref{eq:(2.3)}), we obtain the optimality equation:
\begin{equation}                                          \label{eq:(2.4)}
  h(q)(i) = \max_{ a \in A} \biggl\{  r(i,a) - \psi^{*}(q) 
            + \sum_{j \in S} q_{ij}(a) h(q)(j) \biggr\}
\end{equation}
for $i \in S$.
Then, by applying Lemma \ref{lem:2.1}, we have the well-known results.
\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 $A^{*}(i|q)$ is the set of optimal actions 
at state $i$ and
  $A^*(i \vert q) = 
   \aM_{ a \in A} \biggl\{  r(i,a) - \psi^{*}(q) 
            + \sum_{j \in S} q_{ij}(a) h(q)(j) \biggr\}$
%
%\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}

For any map $H: B(S) \rightarrow B(S)$, we consider the stochastic
algorithm $\{ \tilde{v}_t : t = 0,1,2,\cdots\}$ for the stochastic process 
$\{X_t\}_{t=0}^{\infty} $ on $S$, whose update equations are 
described by, for $i \in S$,
\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
   \end{array}
\end{equation}
where $\tilde{\gamma}_t(i)$ is a step size at time $t$ and 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$.

Then, we have the following.
\begin{lem}[cf. Proposition 4.5 in \cite{Bert96}]      \label{lem:2.3}
  Suppose that the following condition (i) -- (v).
  \begin{itemize}
    \item[{(i)}] $E[W_{t}(i) \vert {\cal F}_t] = 0$
                 for $i \in S$
    \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$.
    \item[{(iii)}]
      $H$ is a contraction with a unique fixed point $v^* \in B(S)$.
    \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$.
    \item[{(v)}]
      There exists a nonnegative random sequence $\theta_{t}$ that converges to
      zero with probability 1, and such that 
	  $$|u_{t}(i)|\leqq\theta_{t}(||\tilde{v}_{t}||+1)$$
	  for $i\in S$ and $t\geqq 0$.
  \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}






%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{TD-based adaptive policies}\label{Sec3}
%section 3


In this section, an adaptive policy is 
given by the learning iteration algorithm using temporal differences.


\begin{lem}                                             \label{lem:3.1}
  Let $\pi = (\pi_0, \pi_1, \cdots) \in \Pi$ satisfy that
  $ \pi_t \bigl( A^*(j \vert q) \bigm\vert X_0, \Delta_0, \cdots ,   
    \Delta_{t-1}, \\ X_t = j \bigr) \rightarrow 1 $ with 
  $P_\pi(\cdot \vert X_0=i, q)$-probability $1$ as $t \rightarrow \infty$
  for $ i,j \in S $ and $ q \in \bQ_\delta$.
  Then, the policy $\pi$ is adaptively optimal for $\bQ_{\delta}$.
\end{lem}

\noindent{\it Proof.} Let $q\in \bQ_{\delta}$ with $\delta>0$.
For simplicity, put
$P(\cdot)=P_{\pi}(\cdot|X_0=i,q)$ and $E(\cdot)=E_{\pi}(\cdot|X_{0}=i,q).$
For $t\geqq0$, let 
$$
\sigma(X_{t},X_{t+1})=h(q)(X_t)-\left(r(X_{t},\Delta_{t})+h(q)(X_{t+1})-
\psi^{*}(q)\right).
$$
Then, we have
\begin{equation}\label{eq:(3.1)}
\begin{array}{l}
E(\sigma(X_{t},X_{t+1})|X_{0},\Delta_{0},\ldots,X_{t}=j)\\
\displaystyle
=h(q)(j)-\sum_{a\in A}\left(r(j,a)+\sum_{\ell\in S}q_{j\ell}(a)h(q)(\ell)-\psi^{*}(q)\right)
%\cdot
\pi_{t}(a|X_{0}=i,\ldots,X_{t}=j).
\end{array}
\end{equation}
By assumption of Lemma \ref{lem:3.1}, $\pi_{t}(A^{*}(j|q)|X_{0},\Delta_{0},\ldots,
X_{t}=j)\to 1\ (t\to \infty)$
with $P$-probability 1.
So, by (\ref{eq:(3.1)}) it holds that
$E\left(\sigma(X_{t},X_{t+1})|X_{0},\Delta_{0},\ldots,X_{t}=j\right)\to 0$
as $t\to \infty$ with $P$-probability $1$.
Applying the dominated convergence theorem,
it follows that $E\left(\sigma(X_{t},X_{t+1})\right)\to 0$
as $t\to \infty$.
Thus, we have
\begin{align*}
&\lim_{T\to\infty}\frac{1}{T+1}\sum_{t=0}^{T}E(\sigma(X_{t},X_{t+1}))\\
=&\lim_{T\to\infty}\left(\frac{1}{T+1}E\left(\sum_{t=0}^{T}r(X_{t},\Delta_{t})\right)
-\psi^{*}(q)+\frac{1}{T+1}\left(h(q)(X_{0})-h(q)(X_{T})\right)\right)\\
=&\psi(i,q|\pi)-\psi^{*}(q)=0.
\end{align*}
By Lemma \ref{lem:2.2}, $\psi^{*}(q)=\psi(i,q)=\psi(i,q|\pi)$
which completes the proof.\qed


%%For any sequence $\{b_t\}_{t\geqq 0}$ of positive numbers with $ b_0 = 1$,
%%$ 0 < b_{t+1} <1 $ and $b_t > b_{t+1}$ for all $t \geqq 0$,
%%let $\phi $ be any strictly increasing function such that $\phi:
%%[0,1] \rightarrow [0,1]$ and $\phi_t(b_t) = b_{t+1}$ for each $t \geqq 0$.


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}=\left(q^{n}_{ij}(a))\right)$ is 
the maximum likelihood estimator of the unknown transition matrices.
For any given $q^{0}=\left(q^{0}_{ij}(a)\right)\in \bQ_{\delta}$,
we define $\tilde{q}^{n}=\left(\tilde{q}^{n}_{ij}(a)\right)\in \bQ_{\delta}$ 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}
\]

Firstly, 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$.

  %�g�ň͂�
%\newpage
\medskip

\noindent{\bf Algorithm ${\bm(*)}$:}             \label{alg:1} 
\begin{enumerate}
  \item Set $t=0$ and $\tilde{v}_0 \equiv 0$ and let $\tilde{\pi}_0 \in P(A|S)$ be
        such that $\tilde{\pi}_0(a | i) > 0 $ for all $a \in A$
        and $i \in S$.  
  \item 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 present 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$,
        \begin{equation}                        \label{update-eq}
        %$$
               \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)
        %\eqno{(3.1)}
        %$$
        \end{equation}
        where the step size 
        $\tilde{\gamma}_t$ is defined as $\tilde{\gamma}_t(i) = \gamma_t(i)$
        if $X_t = i$, and  $= 0$ otherwise, 
        for a sequence $\{ \gamma_t(i)\}$. 
  \item 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
        \begin{equation}\label{md-policy}
		\tilde{\pi}_{t+1}(a|i)=\frac{\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),
        %\eqno{(3.2)}
        \end{equation}
        where $K(i)$ denotes the number of actions in state $i$.
  \item Set $t = t +1 $ and return to step 2.
\end{enumerate}
%\vskip3mm \hrule} %�g�ň͂ޏI��� 
%\vskip10mm

To prove the validity of the adaptive policy given in {Algorithm ${(*)}$},
we need the following Condition ($*$) and Lemmas.
\medskip

\noindent{\bf Condition $\bm{(*)}$}
\begin{itemize}
\item[(i)] $\lim_{t\to\infty}\varepsilon_{t}(i)=0$ and $\sum_{t=0}^{\infty}
\varepsilon_{t}(i)=\infty$,
\item[(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}

\begin{lem}\label{lem:3.2}
Suppose that (i) of Condition ($*$) holds and $q=(q_{ij}(a))\in \bQ_{\delta}$
with $\delta>0$. Then, we have
\begin{itemize}
\item[(i)] $\lim_{t\to\infty}N_{t}(j|a)=\infty$ for all $j\in S$ and $a\in A$ with
$P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$-probability 1,
\item[(ii)] $q^{t}_{ij}(a)\to q_{ij}(a)$ as $t\to\infty$ for all $i,j\in S$
and $a\in A$ with $P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$-probability 1.
\end{itemize}
\end{lem}

\noindent{\it Proof.}
From Lemma 1 of \cite{Kura83}, (i) follows. Also, (ii) follows from the law 
of large numbers(cf.\ \cite{Bill61}).\qed

Applying Lemma \ref{lem:2.3}, we have the following.

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

\noindent{\it Proof.}
For simplicity, put $P(\cdot)=P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$.
We rewrite the update equation (\ref{update-eq}) in {Algorithm ${(*)}$}
to:
\begin{equation}\label{eq:3.4}
\tilde{v}_{t+1}(i)=(1-\tilde{\gamma}_{t}(i))\tilde{v}_{t}(i)+\tilde{\gamma_{t}}(i)
\left(U\{q\}\tilde{v}_{t}(i)+W_{t}(i)+u_{t}(i)\right)\ (t\geqq 0),
\end{equation}
where
\begin{align}\label{eq:3.5}
W_{t}(i)&=r(i,\Delta_{t})+\tilde{v}_{t}(X_{t+1})-\delta\sum_{\ell\in S}\tilde{v}_{t}(\ell)\notag\\
&~~~~~~~~~~-\sum_{a\in A}\left(r(i,a)+\sum_{j\in S}q_{ij}(a)\tilde{v}_{t}(j)-\delta\sum_{\ell\in S}
\tilde{v}_{t} ( \ell) \right)\tilde{\pi}_{t}(a|i),\\
\label{eq:3.6}
u_{t}(i)&=\sum_{a\in A}\left(r(i,a)+\sum_{j\in S}q_{ij}(a)\tilde{v}_{t}(j)-\delta\sum_{\ell\in S}
\tilde{v}_{t} ( \ell) \right)\tilde{\pi}_{t}(a|i)-U\{q\}\tilde{v}_{t}(i)\ (t\geqq 0).%modefied from (t\geqq 1)
\end{align}

%%added
It is easily seen that $W_{0}(i)=u_{0}(i)=0$ for $i\in S$.

It follows from the definition of $U\{q\}$ that
$||U\{q\}\tilde{v}_{t}||\leqq ||r||+(1-\delta)||\tilde{v}_{t}||$ with $1-\delta<1$,
so that by Proposition 4.7 of \cite{Bert96}, the sequence $\tilde{v}_{t}$ is bounded
with $P$-probability 1.
That is, there exists $M>0$ such that $||\tilde{v}_{t}||\leqq M$ for $t\geqq 1$ 
with $P$-probability 1.

By (\ref{eq:3.5}), $|W_{t}(i)|\leqq 2(||r||+M)$ for all $t\geqq 1$ and $i\in S$,
such that conditions (i)--(ii) of Lemma \ref{lem:2.3}.

For $u_{t}$ in (\ref{eq:3.6}), we have
\begin{equation}\label{eq:3.7}
|u_{t}(i)|\leqq A_{1}+A_{2}+A_{3}
\end{equation}
where
\begin{align*}
A_{1}&=\left| \sum_{a\in A}\left(r(i,a)+\sum_{j\in S}\tilde{q}_{ij}^{t-1}(a)\tilde{v}_{t}(j)
-\delta\sum_{\ell\in S}\tilde{v}_{t}(\ell)\right)
\tilde{\pi}_{t}(a|i)-U\{\tilde{q}^{t-1}\}\tilde{v}_{t}(i)\right|,\\
A_{2}&=\left| \sum_{a\in A}\left(r(i,a)+\sum_{j\in S}\tilde{q}_{ij}^{t-1}(a)\tilde{v}_{t}(j)\right)
\tilde{\pi}_{t}(a|i)\right.\\
&\hspace*{3cm}\left.-\sum_{a\in A}\left(r(i,a)+\sum_{j\in S}q_{ij}(a)\tilde{v}_{t}(j)\right)
\tilde{\pi}_{t}(a|i)\right|\\
\intertext{and}
A_{3}&=\left| U\{\tilde{q}^{t}\}\tilde{v}_{t}(i)-U\{q\}\tilde{v}_{t}(i)\right|\ \ \ 
(t\geqq 1).
\end{align*}
By the definition of $\tilde{\pi}_{t}$, $A_{1}\leqq \left(||r||+M\right)\varepsilon_{t}$
where $\varepsilon_{t}=\max_{i\in S}\{\varepsilon(i)\}$.
We also observe that
$A_2 \leqq M\max_{i\in S,a\in A}\sum_{j\in S}\left|\tilde{q}_{ij}^{t}(a)-q_{ij}(a)\right|$.
Moreover, we have
\begin{align*}
A_3&\leqq \max_{i\in S,a\in A}\left|\left(r(i,a)+\sum_{j\in S}\tilde{q}_{ij}^{t-1}
\tilde{v}_{t}(j)\right)-\left(r(i,a)+\sum_{j\in S}q_{ij}(a)\tilde{v}_{t}(j)\right)\right|\\
&=M\max_{i\in S,a\in A}\sum_{j\in S}\left|\tilde{q}_{ij}^{t-1}(a)-q_{ij}(a)\right|.
\end{align*} 
Thus, putting $\theta_{t}=\varepsilon_{t}+\max_{i\in S,a\in A}\sum_{j\in S}
\left|\tilde{q}_{ij}^{t-1}(a)-q_{ij}(a)\right|$ and $C=3M+||r||$,
it yields that $|u_{t}(i)|\leqq C\theta_{t}$ for all $t\geqq 0$.

By Lemma \ref{lem:3.2} and (i) of Condition $(*)$, it clearly holds
that $\theta_{t}\to 0$ as $t\to \infty$ with $P$-probability 1,
which implies condition (v) of Lemma \ref{lem:2.3}.
Thus, since $h(q)$ is a fixed point of $U\{q\}$, by applying Lemma \ref{lem:2.3},
the desired results follows, which completes the proof.\qed

The optimality of the adaptive policy $\tilde{\pi}$ is given in the
following.


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

\noindent{\it Proof.}
Let $q=(q_{ij}(a))\in \bQ_{\delta}$. By Theorem \ref{thm:3.1},
$\tilde{v}_{t}\to h(q)$ as $t\to \infty$
with $P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$-probability 1.
Also, from (ii) of Lemma \ref{lem:3.2},
$\tilde{q}_{ij}^{t}(a)\to q_{ij}(a)$ as $t\to \infty$
with $P_{\tilde{\pi}}(\cdot|X_{0}=i,q)$-probability 1.
So, observing Step 3 of {Algorithm ${(*)}$}, 
we have
$$
\tilde{\pi}_{t}(A^{*}(j|q)|X_{0},\Delta_{0},\ldots,\Delta_{t-1},X_{t}=j)
=\tilde{\pi}(A^{*}(j|q)|j)\to 1 \ \text{ as } t\to \infty.
$$
Thus, from Lemma \ref{lem:3.1}, it follows that
$\tilde{\pi}$ is $q$-optimal, which completes the proof.\qed

%%%%%%%%%%%%%%%%%%% sec. 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A numerical experiment}\label{Sec4}
%section 4
In this section, we consider the adaptive case of ``Toymaker's problem'' in 
Howard \cite{Howd60}, for which a numerical experiment by TD-based 
learning algorithm ({Algorithm ${(*)}$}) given in Section 3
is put in practice.
For the corresponding MDPs, there exists two states $S=\{1,2\}$, where
state 1(2) represents that he has a successful(unsuccessful) toy.
In state 1(2), he has two actions, where action 1(1) is 
``no advertising''(``no research'')  and action 2(2) is 
``advertising''(``research'').
The table of the unknown (true) stochastic matrix $q$ and reward function $r$
and the figure of transition diagrams are given Table 1 and Figure 1.

\begin{table}[htbp]\label{table:1}%[h]
\small
\begin{center}
\begin{tabular}{|c|c|cc|c|} \hline
\multirow{2}{*}{$~i~$} & \multirow{2}{*}{$~a~$} & \multicolumn{2}{c|}{$q_{ij}(a)$} & \multirow{2}{*}{$~r(i,a)~$} \\ \cline{3-4}
 &  & \multicolumn{1}{c|}{1} & 2 &  \\ \hline
\multirow{2}{*}{1} & 1 & \multicolumn{1}{c|}{~0.5~} & ~0.5~ & ~6~ \\ \cline{2-5}
 & 2 & \multicolumn{1}{c|}{0.8} & 0.2 & 4 \\ \hline
\multirow{2}{*}{2} & 1 & \multicolumn{1}{c|}{0.4} & 0.6 & \llap{$-$}3 \\ \cline{2-5}
 & 2 & \multicolumn{1}{c|}{0.7} & 0.3 & \llap{$-$}5 \\ \hline
\end{tabular}
\smallskip

\caption{Toymaker's Problem}
\label{table1}
\end{center}
\end{table} %
\begin{figure}%[h]
\begin{center}
\includegraphics[width=.8\textwidth]{Fig1-dgms.eps}
\caption{Transition diagrams in Toymaker's problem.}
\end{center}
\end{figure}

By solving the optimality equation (\ref{eq:(2.1)}), we find that
the optimal policy $f^{*}$ is such that $f^{*}(1)=f^{*}(2)=2$
and the optimal average reward $g^{*}=2$ with $v(1)-v(2)=10$.

We denote by $\tilde{g}_{t}$ the average present value obtained 
from adaptive policy $\tilde{\pi}=(\tilde{\pi}_{0},\tilde{\pi}_{1},\ldots)$
constructed through {Algorithm ${(*)}$}, which is denoted by
\begin{equation}
\tilde{g}_{t}=\frac{1}{t}\sum_{l=0}^{t-1}r(X_{l},\Delta_{l})\ \ (t\geqq 1).
\label{eq4.1}
\end{equation}
We have simulated {Algorithm ${(*)}$} to investigate the asymptotic behaviour of
$\tilde{g}_{t}\ (t\geqq 1)$ under the adaptive policy $\tilde{\pi}$.
The data for simulation have been given as follows:
\begin{enumerate}
\item[(i)] The initial policy
 $\tilde{\pi}_{0}(\cdot|i)=\left(\frac{1}{2},\frac{1}{2}\right), 
(i\in S)$ and 
%$q^{0}=\left((q^{0}_{ij}(1))=\begin{pmatrix}\frac{1}{2} & \frac{1}{2}\\[1pt]
% \frac{1}{2} & \frac{1}{2}\end{pmatrix},(q^{0}_{ij}(2))=\begin{pmatrix}\frac{1}{2} & \frac{1}{2}\\[1pt]
% \frac{1}{2} & \frac{1}{2}\end{pmatrix}\right),$
$q^{0}=\{(q^{0}_{ij}(a))\vert q^{0}_{ij}(a)=\frac{1}{2} \text{ for $i,j\in S, a\in A$}\}$,
\item[(ii)] $\varepsilon_{t}(i)=(N_{t}(i)+K(i)+1)^{-1}, 
\gamma(t)(i)=(N_{t}(i)/1000+10)^{-1}\ \ (t\geqq 1,i\in S),$
where $K(i)$ is given in (\ref{md-policy}) and $N_{t}(i)$ represents the number of visiting state $i$ until the $t$-th time.
\end{enumerate}
These data are shown to satisfy Condition $(*)$.
The results of simulations with $\delta=0.1,0.01$ are given in Table 2 and 
Figure 2, in which we observe that 
\[
\tilde{\pi}_{t}(2|1)\to 1,\tilde{\pi}_{t}(2|2)\to 1 \ \text{ and } \
\tilde{g}_{t}\to g=2 \ \text{ as } \ t\to\infty
\]
These results surely show the efficiency of the adaptive policy $\tilde{\pi}$
constructed through TD-based learning algorithm(Algorithm ($*$)).

\begin{table}[tbp]\label{table:2}
\small
\begin{center}
\begin{tabular}{|c|c|r|r|r|r|r|r|} \hline
values & \multicolumn{1}{l|}{\backslashbox{$\delta$}{$t$}} & \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{2}{*}{$\tilde{g}_{t}$} & \multicolumn{1}{c|}{0.1} & 1.436563 & 1.874825 & 1.884112 & 1.930601 & 1.971630 & 2.002304 \\ \cline{2-8}
 & \multicolumn{1}{c|}{0.01} & 1.436563 & 1.872825 & 1.883312 & 1.930441 & 1.971550 & 2.002296 \\ \hline\hline
~decision rule~ & \multicolumn{1}{l|}{\backslashbox{$\delta$}{$t$}} & \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
$\tilde{\pi}_{t}(1|1)$ & \multirow{4}{*}{0.1} & 0.998299 & 0.000275 & 0.000134 & 0.000026 & 0.000013 & 0.000001 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(2|1)$ &  & 0.001701 & 0.999725 & 0.999866 & 0.999974 & 0.999987 & 0.999999 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(1|2)$ &  & 0.002387 & 0.000729 & 0.000393 & 0.000086 & 0.000044 & 0.000005 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(2|2)$ &  & 0.997613 & 0.999271 & 0.999607 & 0.999914 & 0.999956 & 0.999995 \\ \hline
$\tilde{\pi}_{t}(1|1)$ & \multirow{4}{*}{0.01} & 0.998299 & 0.000275 & 0.000134 & 0.000026 & 0.000013 & 0.000001 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(2|1)$ &  & 0.001701 & 0.999725 & 0.999866 & 0.999974 & 0.999987 & 0.999999 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(1|2)$ &  & 0.002387 & 0.000730 & 0.000394 & 0.000086 & 0.000044 & 0.000005 \\ \cline{1-1} \cline{3-8}
$\tilde{\pi}_{t}(2|2)$ &  & 0.997613 & 0.999270 & 0.999606 & 0.999914 & 0.999956 & 0.999995 \\ \hline
\end{tabular}
\smallskip

\caption{The simulation value of $\tilde{g}_{t}$ and $\tilde{\pi}_{t}$ for $\delta=0.1,0.01$}
\end{center}
\end{table} %

\begin{figure}\label{fig:2}
\begin{center}
\includegraphics[width=10cm]{Fig2-EFtype.eps}
\end{center}
\caption{The trajectories of $\tilde{g}_{t}(\delta=1)$. The dotted line means the optimal value of
average reward.}
\end{figure}

%\newpage

%%%%%%%%%%%%%%%%%%%%%%
\nocite{ABB01}
\nocite{Bert96}
\nocite{Bill61}
\nocite{BoMn00}
\nocite{IHK07}
\nocite{IHYK06}
\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

%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{splncs}
\begin{thebibliography}{10}
\bibitem{ABB01}%[1]{ABB01}
J.~Abounadi, D.~Bertsekas, and V.~S. Borkar.
\newblock Learning algorithms for {M}arkov decision processes with average
  cost.
\newblock {\em SIAM J. Control Optim.}, 40(3):681--698, 2001.

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

\bibitem{Bill61}%[3]{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{BoMn00}%[4]{BoMn00}
V.~S. Borkar and S.~P. Meyn.
\newblock The {O}.{D}.{E}.\ method for convergence of stochastic approximation
  and reinforcement learning.
\newblock {\em SIAM J. Control Optim.}, 38(2):447--467, 2000.

\bibitem{FeSc81}%[5]{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}%[6]{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{Howd60}%[7]{Howd60}
R.~A. Howard.
\newblock {\em Dynamic programming and {M}arkov processes}.
\newblock The Technology Press of M.I.T., Cambridge, Mass., 1960.

\bibitem{IHK07}%[8]{IHK07}
T.~Iki, M.~Horiguchi, and M.~Kurano.
\newblock A structured pattern matrix algorithm for multichain markov decision
  processes.
\newblock {\it (To appear in MMOR)}, 2007.

\bibitem{IHYK06}%[9]{IHYK06}
T.~Iki, M.~Horiguchi, M.~Yasuda, and M.~Kurano.
\newblock A learning algorithm for communicating markov decision processes with
  unknown transition matrices.
\newblock {\it (submitted)}.

\bibitem{KoBo99}%[10]{KoBo99}
V.~R. Konda and V.~S. Borkar.
\newblock Actor-critic-type learning algorithms for {M}arkov decision
  processes.
\newblock {\em SIAM J. Control Optim.}, 38(1):94--123 (electronic), 1999.

\bibitem{Kura83}%[11]{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}%[12]{Kura87}
M. Kurano.
\newblock Learning algorithms for {M}arkov decision processes.
\newblock {\em J. Appl. Probab.}, 24(1):270--276, 1987.

\bibitem{Leiz03}%[13]{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{Mand74}%[14]{Mand74}
P. Mandl.
\newblock Estimation and control in {M}arkov chains.
\newblock {\em Advances in Appl. Probability}, 6:40--60, 1974.

\bibitem{Mart67}%[15]{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{Numm84}%[16]{Numm84}
E. 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.

\bibitem{Pute94}%[17]{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{SuBa98}%[18]{SuBa98}
R.~S. Sutton and A.~G. Barto.
\newblock {\em Reinforcement Learning: An Introduction}.
\newblock Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA,
  1998.

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