%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                             %
% An interval Bayesian Method for Uncertain MDPs(Draft)       %
%                                                             %
%                                                             %
%                                                             %
%                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 2008.09.22     Typed by HORIGUCHI
% 2008.10.07 revised
% 2008.10.15 revised
% 2008.11.08 revised (RIMS�̃��W�������ĕҏW�ς�)
% 2009.01.15 revised (RIMS�u���^�����ĕҏW)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,leqno]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{multicol}
\usepackage{bm}
\usepackage{array}
\usepackage{arydshln}
\usepackage{slashbox}
\usepackage{multirow}
\usepackage{graphicx}%,color}
\usepackage{float}
%\usepackage{pst-all}
%\usepackage[square]{harvard}
\usepackage{fancybox}
%\renewcommand{\harvardand}{and}
%\citationmode{abbr}

\usepackage[svgnames,usenames]{pstricks}
\usepackage{pst-3dplot,pstricks-add}
\usepackage{multido}
%\parindent=0pt

\makeatletter
\def\psxyzlabel#1{\small\expandafter\@stripDecimals#1..\@nil}
\makeatother

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


\pagestyle{plain}

\newcommand{\calB}{{\mathcal B}}
\newcommand{\calD}{{\mathcal D}}
\newcommand{\calK}{{\mathcal K}}
\newcommand{\calL}{{\mathcal L}}
\newcommand{\calM}{{\mathcal M}}
\newcommand{\calQ}{{\mathcal Q}}
\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 Interval Bayesian Method for MDPs.(Iki, Horiguchi, Yasuda, Kurano)}}%
\chead{}%
\rhead{\scriptsize {\texttt{\colorbox[gray]{0.7}{RIMS�����W��, 2008.11.10-12}}}
%\rhead{\scriptsize {T.\ Iki.\ et al.}%
}%

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

%\title{�s�m�����̉��ł̃}���R�t����ߒ��ɑ΂����ԃx�C�Y��@\\
%(An Interval Bayesian Method for uncertain MDPs)%
%}%
%\title{���ڊm���s�񂪖��m�̏ꍇ�̃}���R�t����ߒ��ɂ�����\\��ԃx�C�Y��@}
%\author{\small
%  �Ɋ�N��Y(T. IKI)\\
%  \textit{\small Faculty of Education and Culture, Miyazaki University
%       Miyazaki 889-2192 Japan}\\
%\small  �x�����V(M. HORIGUCHI)\\
%  {\it \small Faculty of Engineering, Kanagawa University,
%       Kanagawa 221-8686 Japan}\\
%\small  ���c����(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{}



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

\begin{center}
{\Large\bf �s�m�����̉��ł̃}���R�t����ߒ��ɑ΂����ԃx�C�Y��@\\
(An Interval Bayesian Method for uncertain MDPs)}\\[5pt]
\end{center}
\begin{flushright}
{\small 
�{���w�E���當���w���@�Ɋ�@�N��Y(Tetsuichiro IKI)\\
{ Faculty of Education and Culture, Miyazaki University}\\[2pt]
�_�ސ��w�E�H�w���@�x���@���V(Masayuki HORIGUCHI)\\
{ Faculty of Engineering, Kanagawa University}\\[2pt]
��t��w�E���w���@���c�@�����iMasami YASUDA�j\\
Faculty of Science, Chiba University\\[2pt]
����@����(Masami KURANO)\\
}
\end{flushright}


% \begin{abstract}
% �x�[�^���z�A�K���}���z�A�������z�i�f�B���N�����z�j�Ɋւ��鐫�����܂Ƃ߂�(cf.\ Wilks(1962))

% Uncertain MDPs�̊ȒP�ȗ���l������(cf.\ Martin(1967)). 
% �������z�̃x�C�W�A����Application�AMarkov set-chain�ւ̓K�p�Ȃ�
% \end{abstract}

% {\it Keywords:} 
% Bayesian inference, uncertain transition matrices,
% Diriclet distribution, interval method

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{�͂��߂�}

���ڊm���s�񂪖��m�̃}���R�t����ߒ�(Markov Decision Processes, MDPs)��
��͂�, �Ŗސ���@��p����ꍇ(cf.~\cite{DS80,Hern89,IHYK07,Mand74})��
�x�C�Y����@��p����ꍇ(cf.~\cite{Hern89,Mart67,vHee78})������.
�x�C�Y����@�ɂ����Ă�, ���O���z�������ɐݒ肷�邩����̖��ł���.
���̐ݒ�ɂ�����, �_��ƗZ�ʐ��ɕx�񂾊挒�ȃ��f�����\�����邱�Ƃ�
�������ւ̉��p�ɂ����ďd�v�ł���.


�{�_���ł�De Robertis and Hartigan\cite{RoHa81}��
�񏥂������O���x��Ԃɂ���ԃx�C�Y�@�̍l������K������, ���ڊm��
�s�񂪖��m��MDPs�̉�͂����݂�.
���̂��߂�, ���m�̐��ڊm���s��������ԂŐ��肵���ꍇ��
���f���Ƃ���, ��Ԑ���MDPs(Interval estimated MDPs)��莮����
���̉�͂��s��.
���̉�͌��ʂ��󂯂�, ���O������ԃx�C�Y�@\cite{RoHa81}�ɂ��ƂÂ�
�������瓾��ꂽ��Ԃ�p�������f���Ƃ���, ��ԃx�C�YMDPs(Interval Bayesian estimated MDPs)
���\������.

�}���R�t�A���̐��ڊm���s��̋�ԃx�C�Y�����, ��{�I�ɂ�, �������z��
���N�m���̋�Ԑ���ɋA�������̂�, ����Ɋւ���v�Z�@�Ƃ������̐��l���
�^����.
Kurano et~al\cite{KSHH98,KYN02}�ōl�@���ꂽ ``Controlled Markov
set-chain model'' ��, ���ڊm���s�����ԂłƂ炦��l�����ɂ����Ă�
�{�_���Ɠ����ł��邪, �O�҂ɂ����Ă͊e���Ő��ڊm���s�񂪋�ԓ���
�ϓ����邱�Ƃ��\�ȏꍇ����舵���Ă���.
��Ԑ���MDPs�ł�, �S�ߒ���ʂ��Đ��ڊm���s��͈��ł���ꍇ������.

\section{�L���Ɗ�{����}

�����ł�, �������̋L���Ƒ����߂ŗp�������{����^���Ă���.

$\bR,\bR^{n},\bR^{m\times n}$�����ꂼ�����, $n$��������x�N�g��,
$m\times n$�^���s��̑S�̂�\��.
$\bR=\bR^{1\times 1},\bR^{n}=\bR^{n\times 1}$�Ƃ���.
�܂�, $\bR_{+},\bR_{+}^{n},\bR_{+}^{m\times n}$�͂��ꂼ��
$\bR,\bR^{n},\bR^{m\times n}$�̊e�������񕉂ł���悤�Ȃ��̂̏W���Ƃ���.
$\bR^{m\times n}$�̔�����$\preceq,\prec$�͎��Œ�߂�:
$\bR^{m\times n}\ni A=(a_{ij}), B=(b_{ij})$�ɑ΂���
\begin{equation}\label{Porder}
%\begin{cases}
A\preceq B  \text{($a_{ij}\leqq b_{ij}\ (1\leqq i\leqq m, 1\leqq j \leqq n)$�̂Ƃ�), }
A\prec B  \text{($A\preceq B$ ���� $A\neq B$�̂Ƃ�)} 
%\end{cases}
\end{equation}
�Ƃ���.
$\underline{A}\preceq \overline{A}$�Ȃ�$\underline{A}=(\underline{a}_{ij}),
\overline{A}=(\overline{a}_{ij})\in \bR_{+}^{m\times n}$�ɑ΂���
���$\langle \underline{A}, \overline{A} \rangle$�����Œ�߂�:
\begin{equation}\label{def:itvl}
\langle \underline{A}, \overline{A} \rangle=
\bigl\{Q=(q_{ij})\in \bR_{+}^{m\times n} 
\Big\vert \underline{a}_{ij}\leqq q_{ij} \leqq \overline{a}_{ij},
q_{ij}\geqq 0, \sum_{j=1}^{n} q_{ij}=1\ 
(1\leqq i \leqq m, 1\leqq j \leqq n)    \bigr\}.
\end{equation}
$n\times n$�^�̊m���s��̋�ԏW���S�̂�$\calM_{n}=\left\{\langle \underline{Q}, \overline{Q} \rangle\big\vert
\langle \underline{Q}, \overline{Q} \rangle\neq \emptyset, 
\underline{Q}\preceq \overline{Q}, \underline{Q}, \overline{Q} \in \bR_{+}^{n\times n}\right\}$�ŕ\��.
% \begin{equation}\label{def:mn}%(2.3)
% \calM_{n}=\left\{\langle \underline{Q}, \overline{Q} \rangle\big\vert
% \langle \underline{Q}, \overline{Q} \rangle\neq \emptyset, 
% \underline{Q}\preceq \overline{Q}, \underline{Q}, \overline{Q} \in \bR_{+}^{n\times n}\right\}
% \end{equation}
$\calM_{n}\ni \calQ_{1},\calQ_{2}$�ɑ΂����$\calQ_{1}\calQ_{2}$��
$\calQ_{1}\calQ_{2}=\left\{Q_{1}Q_{2}\big\vert Q_{1}\in \calQ_{1}, Q_{2}\in \calQ_{2}\right\}
$�ƒ�߂�.
% \begin{equation}\label{def:prd}
% \calQ_{1}\calQ_{2}=\left\{Q_{1}Q_{2}\big\vert Q_{1}\in \calQ_{1}, Q_{2}\in \calQ_{2}\right\}
% \end{equation}
�܂�, $\calQ\in \calM_{n}$�ɑ΂��鑽�d�ς͒����I�ɒ�`�����: $\calQ^{k}=\calQ^{k-1}\calQ\ (k\geqq 2).
$
% \begin{equation}\label{def:prd2}
% \calQ^{k}=\calQ^{k-1}\calQ\ (k\geqq 2).
% \end{equation}

$ C(\bR_{+})$��$\bR_{+}$�̗L�E��Ԃ̑S�̂Ƃ���.
�܂�, $ C(\bR_{+})^{n}$��$ C(\bR_{+})$�̗v�f�𐬕��Ɏ���
$n$������x�N�g���̑S�̂Ƃ���:
$ C(\bR_{+})^{n}=\left\{D=(D_{1},D_{2},\ldots,D_{n})'\big\vert
D_{i}\in  C(\bR_{+}) \ (1\leqq i \leqq n)\right\}.
$
% \begin{equation}\label{def:Cn}
%  C(\bR_{+})^{n}=\left\{D=(D_{1},D_{2},\ldots,D_{n})'\big\vert
% D_{i}\in  C(\bR_{+}) \ (1\leqq i \leqq n)\right\}
% \end{equation}
������, $\bm{d}'$�̓x�N�g��$\bm{d}$�̓]�u��\��.
$ C(\bR_{+})^{n}$��̎Z�@(���@,�X�J���[�{)�͎��Œ�߂�:\\
$D=(D_1,D_2.\ldots,D_{n})',E=(E_{1},E_{2},\ldots,E_{n})'\in  C(\bR_{+})^{n},
h\in \bR_{+}^{n},\lambda\in \bR_{+}$�ɑ΂���,
\begin{equation}\label{def:ar}
D+E=\{d+e\vert d\in D,e\in E\},
h+D=\{h+d\vert d\in D\},
\lambda D=\{\lambda d|d\in D\}.
\end{equation}
$D=([\underline{d}_{1},\overline{d}_{1}],[\underline{d}_{2},\overline{d}_{2}],\ldots, 
[\underline{d}_{n},\overline{d}_{n}])'\in  C(\bR_{+})^{n}$��
$D=[\underline{d},\overline{d}]$�ƋL��.
������, $\underline{d}=(\underline{d}_{1},\underline{d}_{2},\ldots,\underline{d}_{n})\in 
\bR_{+}^{n},
\overline{d}=(\overline{d}_{1},\overline{d}_{2},\ldots,\overline{d}_{n})\in 
\bR_{+}^{n}$�Ƃ���.
$D=(D_{1},D_{2},\ldots, D_{n})'\in  C(\bR_{+})^{n}$�ƕ����W��$G\subset \bR_{+}^{1\times n}$
�ɑ΂���, ���̐�$GD$��$GD=\{gd\vert g=(g_{1},g_{2},\ldots,g_{n})\in G, d=(d_{1},d_{2},\ldots,d_{n})'\in D, 
d_{i}\in D_{i}\ (1\leqq i \leqq n)\}
$�ƒ�߂�.
% \begin{equation}
% GD=\{gd\vert g=(g_{1},g_{2},\ldots,g_{n})\in G, d=(d_{1},d_{2},\ldots,d_{n})'\in D, 
% d_{i}\in D_{i}\ (1\leqq i \leqq n)\}
% \end{equation}

�������藧��.
\begin{lem}(\cite{Hart98,KSHH98})\label{lem:2.1}
%\begin{itemize}
%\item[(i)] 
(i) �C�ӂ�$\calQ \in \calM_{n}$��$n\times n$�����x�N�g�����$\bR^{n\times n}$��
�ʑ��ʑ̂ł���.
%\item[(ii)] 
(ii) �R���p�N�g�ʕ����W��$G\subset \bR_{+}^{1\times n}$��
$D=(D_{1},D_{2},\ldots,D_{n})\in  C(\bR_{+})^{n}$�ɑ΂���$GD\in  C(\bR_{+})$�ł���.
%\end{itemize}
\end{lem}
\smallskip

$ C(\bR_{+})$��̔�����$\preceq,\prec$�����Œ�߂�:
$[c_1,c_2],[d_1,d_2]\in  C(\bR_{+})$�ɑ΂���
\begin{equation}\label{def:po1}
\begin{cases}
[c_1,c_2]\preceq [d_1,d_2] & \text{ ($c_{i}\leqq d_{i}\ (i=1,2)$�̂Ƃ�) }\\
[c_1,c_2]\prec [d_1,d_2] & \text{ ($[c_1,c_2]\preceq [d_1,d_2]$����$[c_1,c_2]\neq [d_1,d_2]$�̂Ƃ�) }
\end{cases}
\end{equation}
�Ƃ���.
$ C(\bR_{+})^n$��̔�����$\preceq,\prec$��$ C(\bR_{+})$��̔�������p����
���ɂ���߂�:
$\bm{v}=(v_{1},v_{2},\ldots,v_{n})',\bm{w}=(w_{1},w_{2},\ldots,w_{n})'\in C(\bR_{+})^{n}$
�ɑ΂���
\begin{equation}\label{def:pon}
%\begin{cases}
\bm{v}\preceq\bm{w} \text{ ($v_{i}\preceq w_{i}\ (1\leqq i \leqq n)$�̂Ƃ�), }
\bm{v}\prec\bm{w} \text{ ($\bm{v}\prec \bm{w}$����$\bm{v}\neq\bm{w}$�̂Ƃ�) }
%\end{cases}
\end{equation}

$\bR_{+}^{n}$��2�̗L�E�W��$D_{1},D_{2}$�̋����Ƃ��ăn�E�X�h���t����$\rho$���l����:
\begin{equation}\label{def:HD}%%(2.11)
\rho(D_1,D_2)=\max\{\sup_{x\in D_{1}}\inf_{y\in D_{2}}\lVert x-y \rVert,
\sup_{y\in D_{2}}\inf_{x\in D_{1}}\lVert x-y \rVert\}.
\end{equation}
������, $\lVert \cdot \rVert$��$\bR^{n}$�ɂ����郆�[�N���b�h�����Ƃ���.

����, ���߈ȍ~�̋c�_�̏����Ƃ��ėL����ԃ}���R�t����ߒ��ɂ��ďq�ׂ�.
���錈��ߒ��̏�ԋ�Ԃ�$S=\{1,2,\ldots,n\}$, �s����Ԃ�
$A=\{1,2,\ldots,k\}$�Ƃ���.
���̏W�����`����:
\begin{align}
P(S):=&\{p=(p_{1},p_{2},\ldots,p_{n})\in \bR_{+}^{n}\big\vert \sum_{i\in S} p_{i}=1\},\\
P(S\vert S):=&\{q=(q_{ij}:i,j\in S)\in \bR_{+}^{n\times n}\big \vert
\sum_{j\in S}q_{ij}=1\ (i\in S)\},\\
P(S\vert S\times A):=&\{Q=(q_{ij}(a):i,j\in S,a\in A)\in \bR_{+}^{kn \times n}\vert 
q_{i\, \cdot} (a)\in P(s)\ (i\in S, a\in A)\}.
\end{align}

�L���W��$D$��̔񕉎����l�֐��̑S�̂�$B_{+}(D)$�ŕ\��.
$D$���L���W���̂Ƃ�$B_{+}(D)$��$\bR_{+}^{n}$�𓯈ꎋ����.
������ $n=\lvert D \rvert$�ł���Ƃ���.
$Q=(q_{ij}(a))\in P(S\vert S\times A)$��$\bm{r}=(r(i,a))\in B_{+}(S\times A)$�ɑ΂���,
�ʏ�̃}���R�t����ߒ�MDPs$\{S,A,Q,\bm{r}\}$���l��(cf.~\cite{Pute94}), �����ł�
�ȒP�̂��߂Ɋm��I(deterministic)�Œ��(stationary)�Ȑ���݂̂��l����.
$S$����$A$�ւ̎ʑ�$f$�̑S�̂�$F$�ŕ\��.
�C�ӂ�$f\in F$�ɑ΂���, ������$\beta\ (0<\beta < 1)$�ɂ���Ċ�������ꂽ
�����җ����x�N�g��$\phi(f\vert Q)\in \bR_{+}^{n}$��
�m���s��$Q\in P(S\vert S\times A)$�̊֐��Ƃ��Ď��Œ�߂�:
\begin{equation}\label{def:value}
\phi(f\vert Q)=\sum_{t=0}^{\infty}(\beta Q(f))^{t}\bm{r}(f),
\end{equation}
������, $\bm{r}(f)=(r(1,f(1)),r(2,f(2)),\ldots, r(n,f(n)))'\in \bR_{+}^{n},
Q(f)=(q_{ij}(f(i)))\in P(S\vert S).$
�e$f\in F$�ɑ΂��Ďʑ�$L(f):\bR_{+}^{n}\to \bR_{+}^{n}$�����Œ�߂�:
\begin{equation}\label{def:Lf}
L(f)\bm{x}=\bm{r}(f)+\beta Q(f)\bm{x}, \ \bm{x}=(x_{1},x_{2},\ldots,x_{n})'\in \bR_{+}^{n}.
\end{equation}
���̂Ƃ�, ���̊�{��肪�m���Ă���.

\begin{lem}(cf.~\cite{Pute94})\label{lem:2.2}
%\begin{itemize}
%\item[(i)] 
(i) $L(f)$�͒P����������яk���ʑ��ł���. ���Ȃ킿, 
%\begin{align*}
$
\bm{x}\leqq \bm{x}'$ �Ȃ�� $L(f)\bm{x}\leqq L(f)\bm{x}' $(componentwise), 
$\lVert L(f)\bm{x}-L(f)\bm{x}'\rVert \leqq \beta \lVert \bm{x}-\bm{x}'\rVert 
\ (\bm{x},\bm{x}'\in \bR_{+}^{n})$�����藧��.
%\end{align*}
������, $\lVert\cdot \rVert$��$\sup$�m�����Ƃ���.
%\item[(ii)] 
(ii) $\phi(f\vert Q)$��$L(f)$�̗B��̕s���_�ł���.
���Ȃ킿
�C�ӂ�$\bm{x}\in \bR_{+}^{n}$�ɑ΂���
$
L(f)^{t}\bm{x}\to\phi(f\vert Q)\ (t\to \infty)
$
�����藧��.
%\end{itemize}
\end{lem}

\section{��Ԑ���MDPs�ƃp���[�g�œK}
�{�߂ł�, MDPs$\{S,A,Q,\bm{r}\}$�̐��ڊm���s��$Q$�����$\calQ=\langle\underline{Q},\overline{Q} \rangle$
�Ő��肵���ꍇ���l�@����.
������,
\begin{align}\label{assumption}%(3.1),(3.2)
\underline{Q}&=(\underline{q}_{ij}(a):i,j\in S, a\in A)\in \bR_{+}^{kn \times n},
\overline{Q}=(\overline{q}_{ij}(a):i,j\in S, a\in A)\in \bR_{+}^{kn \times n},\\
\calQ&=\langle \underline{Q},\overline{Q}\rangle
=\left\{Q\in P(S\vert S\times A) \big\vert \underline{Q}\leqq Q \leqq \overline{Q}\right\}
\end{align}
�Ƃ���.
���ڊm���s��$Q$��$\calQ=\langle \underline{Q},\overline{Q}\rangle$�Ő��肵�����胂�f����
��Ԑ���MDPs$\{\calQ\}$(Interval estimated MDPs $\{\calQ\}$)�ƌĂ�.
�ȉ�, ��Ԑ���MDPs�̗����֐����`�����̍œK���ɂ��ċc�_����.

$f\in F$�ɑ΂��銄�����ꂽ������-�W���x�N�g��$\phi(f\vert \calQ)$�����Œ�߂�:
\begin{equation}\label{value:calQ}
\phi(f\vert \calQ)=\bigl\{\phi(f\vert Q)\big\vert Q\in \calQ\bigr\} \subset \bR_{+}^{n}.
\end{equation}
������, $\phi(f\vert Q)$�͎�(\ref{def:value})�ŗ^�����Ă���.
������, $\phi(f\vert \calQ)\in  C(\bR_{+})^{n}$�ł��邱�Ƃ�������.
$\calL$��$ C(\bR_{+})^{n}$����$ C(\bR_{+})^{n}$�ւ̎ʑ��Ŏ��̂悤�ɒ�߂�:
\begin{equation}\label{def:cLf}%(3.4)
\calL(f)\bm{v}=r(f)+\beta\calQ(f)\bm{v}, \ \bm{v}\in C(\bR_{+})^{n},
\end{equation}
������, ��(\ref{def:cLf})�ɂ�����$\calQ(f)=\langle \underline{Q}(f),\overline{Q}(f)\rangle,
\underline{Q}(f)=(\underline{q}_{ij}(f(i)))\in \bR_{+}^{n\times n},
\overline{Q}(f)=(\overline{q}_{ij}(f(i)))\in \bR_{+}^{n\times n}$�ł���.
Lemma \ref{lem:2.1}�ɂ��$\calL(f) \bm{v} \in  C(\bR_{+})^{n}\ (\bm{v}\in  C(\bR_{+})^{n})$�ł��邱�Ƃ�������Ă��邱�Ƃɒ��ӂ���.
�����, $\underline{L}(f): \bR_{+}^{n}\to \bR_{+}^{n},
\overline{L}(f): \bR_{+}^{n}\to \bR_{+}^{n}$�����Œ�߂�:
$\bm{x}=(x_{1},x_{2},\ldots,x_{n})'\in \bR_{+}^{n}$�ɑ΂���
%\begin{align}%(3.5),(3.6)
\begin{equation}
\underline{L}(f) \bm{x} = \bm{r}(f)+\beta \min_{Q\in \calQ(f)}Q\bm{x}, %\label{def:LwLf},
\overline{L}(f) \bm{x} = \bm{r}(f)+\beta \max_{Q\in \calQ(f)}Q\bm{x}.%\label{def:UpLf}.
\end{equation}
%\end{align}
���̂Ƃ�, �������藧��.
\begin{lem}\label{lem:3.1}
�C�ӂ�$f\in F$�ɑ΂���, �������藧��:
%\begin{itemize}
%\item[(i)] 
(i) $\calL(f)$�͒P���������k���ʑ��ł���.
%\item[(ii)] 
(ii) $\underline{L}(f),\overline{L}(f)$��, �Ƃ��ɒP������
����$\sup$�m�����Ɋւ��ďk���ʑ��ł���.
%\end{itemize}
\end{lem}

\noindent{\it Proof.} \cite{KSHH98}�̒藝3.1���Q��. \qed
\medskip

Lemma \ref{lem:2.2}��Lemma \ref{lem:3.1}��K�p���Ď��𓾂�.

\begin{thm}\label{thm:3.1}
�C�ӂ�$f\in F$�ɑ΂��Ď������藧��:
%\begin{itemize}
%\item[(i)] 
(i) $\phi(f\vert \calQ)\in  C(\bR_{+})^{n}$����
$\phi(f\vert \calQ)$��$\calL(f)$�̗B��̕s���_�ł���.
�����, �C�ӂ�$\bm{v}\in  C(\bR_{+})^{n}$�ɑ΂���
$
\calL(f)^{\ell} \bm{v} \to \phi(f \vert \calQ) \ (\ell \to \infty).
$
%\item[(ii)] 
(ii) $\phi(f\vert \calQ)=[\underline{\phi}(f),\overline{\phi}(f)]$�Ƃ���Ƃ�,
$\underline{\phi}(f),\overline{\phi}(f)$�͂��ꂼ��
$\underline{L}(f),\overline{L}(f)$�̗B��̕s���_�ł���.
%\end{itemize}
\end{thm}

\noindent{\it Proof.} %\cite{KSHH98}�̌n3.1�ƕ��4.1���Q��. \qed 
�C�ӂ�$Q\in \calQ$�ɑ΂���,
$
\phi(f\vert Q)=\bm{r}(f)+\beta Q(f)\phi(f\vert Q) \leqq \overline{L}(f)\phi(f\vert Q)
$
������,
$
\phi(f\vert Q)\leqq \overline{L}(f)^{\ell} \phi(f\vert Q)\to \overline{\phi}(f)\ \ (\ell \to \infty).
$
���l�ɂ���,
$
\phi(f\vert Q)\geqq \underline{L}(f)^{\ell} \phi(f\vert Q)\to \underline{\phi}(f)\ \ (\ell \to \infty).
$
�̂�, $\underline{\phi}(f)\leqq \phi(f\vert Q) \leqq \overline{\phi}(f)$�𓾂�.
���炩��, $\underline{\phi}(f),\overline{\phi}(f)\in \phi(f\vert\calQ)$����
$\phi(f\vert Q)$��$Q\in \calQ$�Ɋւ��ĘA��(cf.~\cite{So03})�ł��邩��
$\phi(f\vert \calQ)=[\underline{\phi}(f),\overline{\phi}(f)]$�����藧��.
�����(ii)�������ꂽ.

$\calL(f)$�̕s���_��$\bm{u}(f)\in  C(\bR_{+})^{n}$�Ƃ���.
�C�ӂ�$\bm{v}=[\underline{v},\overline{v}]\in  C(\bR_{+})^{n}$�ɑ΂��Ď������藧��:
$
\calL(f)\bm{v}=[\underline{L}\, \underline{v},\overline{L}\, \overline{v}].
$
�̂�, $\ell \geqq 1$�ɑ΂���$\calL(f)^{l\ell}\bm{v}=[\underline{L}^{\ell}\underline{v},
\overline{L}^{\ell}\overline{v}]$. 
������, $\ell \to \infty$�Ƃ��邱�Ƃ�
$
\bm{u}(f)=[\underline{\phi}(f),\overline{\phi}(f)]
$
�𓾂�. (ii)���$\bm{u}(f)=\phi(f\vert \calQ)$�ƂȂ�(i)�������ꂽ.
\qed
\medskip

$f^{*}\in F$���p���[�g�œK�ł���Ƃ�,
$
\phi(f^{*}\vert \calQ) \prec \phi(f\vert \calQ)
$
�Ȃ�$f\in F$�����݂��Ȃ��ꍇ������.

\begin{lem}\label{lem:3.2}
$f,g\in F$�ɑ΂���, $\phi(f\vert \calQ) \prec \calL(g)\phi(f\vert \calQ)$�Ȃ��
$\phi(f\vert \calQ) \prec \phi(g\vert \calQ).$
\end{lem}

\noindent{\it Proof.}
$\calL(g)$�̒P������ Theorem 3.1 ����
$\phi(f\vert \calQ) \prec \calL(g)\phi(f\vert \calQ) \prec \calL(g)\calL(g)\phi(f\vert \calQ)
\prec \cdots \\
\prec (\calL(g))^{n}\phi(f\vert \calQ) \to \phi(g\vert \calQ)~(n\to \infty).
%\ \ \text{from Theorem 3.1}
$%\end{align*}
�]����, $\phi(f\vert \calQ) \prec \phi(g\vert \calQ)$�������ꂽ. \qed
\medskip



$D\subset  C(\bR_{+})^{n}$�ɑ΂��ē_$\bm{v}\in D$��$D$��{\em{�L���_}}(efficient point)
�ł���Ƃ�, $\bm{v}\prec \bm{u}$�Ȃ�$\bm{u}\in D$�����݂��Ă��Ȃ��ꍇ������.
$D$�̗L���_�̑S�̂�$\mathrm{eff}(D)$�ŕ\��.
��(\ref{assumption})��$\underline{Q},\overline{Q}$�̐����x�N�g��
%\begin{align*}%
$\underline{Q}_{i,a}=(\underline{q}_{i1}(a),\underline{q}_{i2}(a),
\ldots,\underline{q}_{in}(a)),
\overline{Q}_{i,a}=(\overline{q}_{i1}(a),\overline{q}_{i2}(a),
\ldots,\overline{q}_{in}(a))$
%\end{align*}
�ɑ΂���$\calQ_{i,a}=\langle \underline{Q}_{i,a}, \overline{Q}_{i,a}\rangle
\ (i\in S, a\in A)$�Ƃ���.
$\bm{u}\in  C(\bR_{+})^{n}$�ɑ΂��Ď����߂�:
\begin{equation}\label{def:Lu}
\calL(\bm{u}):=(\calL(\bm{u})_{1},\calL(\bm{u})_{2},\ldots,\calL(\bm{u})_{n})',
\end{equation}
������, $\calL(\bm{u})_{i}:=\mathrm{eff}(\{r(i,a)+\beta\calQ_{i,a}\bm{u}\vert a\in A\})
\ (i\in S)$�ł���.

���̂Ƃ�, Lemma \ref{lem:3.2}��p���Ď����������.
\begin{thm}\label{thm:3.2}
$f^{*}$���p���[�g�œK�ł��邽�߂̕K�v�\��������,
$\phi(f^{*}\vert \calQ)$�����̍œK��܎��̍ő���ƂȂ邱�Ƃł���.
\begin{equation}\label{opt:inc}
\bm{u}\in \calL(\bm{u}), \bm{u}\in  C(\bR_{+})^{n}.
\end{equation}
\end{thm}

\noindent{\it Proof.} %�ؖ���\cite{Furu80,KYN02}�Ɠ��l�̕��@�Ŏ������Ƃ��ł���.\\
($\Rightarrow$) $f^{*}\in F$��Pareto-optimal�Ƃ���. 
���̂Ƃ�, Theorem \ref{thm:3.1}����$\phi(f^{*}\vert\calQ)$��$\calL(f^{*})$�̕s���_�ł���.
�����, $\phi(f^{*}\vert \calQ)\in \calL(\phi(f^{*}\vert \calQ))$�ł���.
������,����,����$\bm{u}\in  C(\bR_{+})^{n}$�����݂��� 
$\bm{u}\in \calL(\bm{u})$����$\phi(f^{*}\vert \calQ)\prec \bm{u}$
�ł�����̂����݂����Ƃ���.
���Ȃ킿, $\exists g\in F, \exists i_{0}\in S$ s.t.
%\begin{align*}
$\phi(f^{*}\vert \calQ)_{i_{0}} \prec \bm{u}_{i_{0}}= r(i_{0},g(i_{0}))+
\beta \calQ_{i_{0},g(i_{0})}\bm{u}=\phi(g\vert \calQ)_{i_{0}},
\phi(f^{*}\vert \calQ)_{i} \preceq \bm{u}_{i}= r(i,g(i))+\beta \calQ_{i,g(i)}\bm{u}=
\phi(g\vert \calQ)_{i}\ \ (i\neq i_{0},i\in S).$
%\end{align*}
������, $\bm{a}_{i}$��$\bm{a}\in  C(\bR_{+})^{n}$�̑�$i$������\��.
�����, $f^{*}$��Pareto-optimal�ł��邱�Ƃɖ�������.\\
($\Leftarrow$)
$\phi(f^{*}\vert \calQ)$��$\bm{u}\in \calL{\bm{u}}$
�̍ő���ł��邪Pareto-optimal�łȂ��Ƃ���.
���̂Ƃ�, $\exists g\in F$ s.t. $\phi(f^{*}\vert \calQ)\prec \phi(g\vert \calQ)$�ł���.
����, $\exists i\in S$ s.t. $\phi(f^{*}\vert \calQ)_{i} \prec \phi(g\vert \calQ)_{i}$�ł���.
��ʂ�, $\phi(f\vert \calQ)_{i}\in  C(\bR_{+})$�ł�����, $f\in F$�͍��X�L���ł��邩��
$\phi(g\vert \calQ)_{i}\preceq \phi(\overline{g}\vert \calQ)_{i}\ \ (i\in S)$�ƂȂ�
$\overline{g}$�����݂���.
���Ȃ킿
$
\phi(f^{*}\vert \calQ)\prec \phi(g\vert \calQ)\preceq \phi(\overline{g}\vert \calQ)
$
�����藧��.������,
$\phi(\overline{g}\vert \calQ)\notin \calL(\phi(\overline{g}\vert \calQ))$
�ł���Ɖ��肷���, �L���_�̒�`����$\exists i_{0}\in S$��$\exists a_{0}\in A$�ɑ΂���
\begin{equation}\label{not:eff}
\phi(\overline{g}\vert \calQ)_{i_{0}}\prec r(i_{0},a_{0})+\beta \calQ_{i_{0},a_{0}}
\phi(\overline{g}\vert \calQ)_{i_{0}}
\end{equation}
�����藧��.������
$
f^{(1)}(i)=
a_{0}  \text{ (if $i=i_{0}$), }
\overline{g}(i) \text{ (if $i\neq i_{0}, i\in S$) }
$
�Ƃ����, Lemma \ref{lem:3.2}����
$
\phi(\overline{g}\vert \calQ)\prec \phi(f^{(1)}\vert \calQ)
$
�𓾂�.
$\phi(f^{*}\vert \calQ)\prec \phi(f^{(1)}\vert \calQ)$
�ł�����, $\phi(f^{(1)}\vert \calQ)\notin \calL(\phi(f^{(1)}\vert \calQ))$�ł����
��(\ref{not:eff})�Ɠ��l�ɂ���$\exists f^{(2)}\in F$ s.t. 
$\phi(f^{(1)}\vert \calQ)\prec \phi(f^{(2)}\vert \calQ)$.
$f\in F$�͍��X�L��������,
$\exists f^{(k)}\in F$ s.t. 
$\phi(f^{*}\vert \calQ)\prec 
\phi(f^{(1)}\vert \calQ)\prec \cdots \prec \phi(f^{(k)}\vert \calQ)$ and 
$\phi(f^{(k)}\vert \calQ)\in \calL(\phi(f^{(k)}\vert \calQ))$
�����藧��.
�����, $\phi(f^{*}\vert \calQ)$��$\bm{u}\in \calL(\bm{u})$�̍ő���ł��邱�Ƃɖ�������.
\qed

\medskip



\section{�f�B���N�����z}
�}���R�t�A���̐��ڊm���s��̋�ԃx�C�Y�����,�s��̍s�����ɒ��ڂ����,
�������z�̐��N�m���̋�Ԑ���ɋA�������.
������,���߈ȍ~�ɗp�������ԃx�C�Y�@�ɂ�鐄�ڊm���̎��O�E�����͂̂��߂�
�f�B���N�����z(�������x�[�^���z)�Ɋւ��邢�����̐���������.

�K���}�֐�$\Gamma(x)\ (x>0)$�ƃx�[�^�֐�$B(x,y)\ (x,y>0)$�����ꂼ�ꎟ�̂悤�ɕ\�����Ƃɂ���. 
\[\displaystyle\Gamma(x)=\int_{0}^{\infty} t^{x-1}e^{-t}\,dt~~(x>0),
\displaystyle B(x,y)=\int_{0}^{1}t^{x-1}(1-t)^{y-1}\,dt~~(x,y>0).\]

%\noindent{\bf �f�B���N�����z(\cite{Wlks62})}:\\
$k$-�ϐ��f�B���N�����z%($k$-variable Dirichlet distribution)$\tilde{D}(\nu_{1},\ldots,\nu_{k};\nu_{k+1})$
��p.d.f.��
���̂悤�ɒ�`����:
\begin{equation}\label{diric}
f(x_1,\ldots,x_{k})=\dfrac{\Gamma(\nu_{1}+\cdots+\nu_{k+1})}{\Gamma(\nu_{1})\cdots\Gamma(\nu_{k+1})}
x_{1}^{\nu_{1}-1}\cdots x_{k}^{\nu_{k}-1}(1-x_{1}-x_{2}-\cdots-x_{k})^{\nu_{k+1}-1}.
\end{equation}
�A��, 
$x_{1},\ldots,x_{k}$��$k$�������ʑ�
$S_{k}:=\{(x_{1},\ldots,x_{k}):
x_{i}\geqq 0, i=1,\ldots,k,\sum_{i=1}^{k}x_{i}\leqq 1\}$
�̊e�����ł���, $f$��$S_{k}$��̓_�ȊO�ł�$0$, $\nu_{i}\in \bR$��$\nu_{i}>0~(i~1,2,\ldots,k+1)$�Ƃ���.
\begin{equation}\label{def:dirichlet}
\tilde{D}(\nu_{1},\ldots,\nu_{k};\nu_{k+1})=\displaystyle\idotsint_{S_{k}} f(x_1,\ldots,x_k)\, dx_{1}\cdots dx_{k}
\end{equation}
�ƕ\��.
�f�B���N���ϕ�,���Ȃ킿,�f�B���N�����z�̒萔�W������������ϕ��֐������Ɋւ���
\begin{equation}
\begin{split}
&D(\nu_{1},\nu_{2},\ldots,\nu_{k};\nu_{k+1})\\
&:=\idotsint_{S_{k}}x_{1}^{\nu_1-1}x_{2}^{\nu_{2}-1}\cdots x_{k}^{\nu_{k}-1}(1-x_{1}-x_{2}-\cdots -x_{k})^{\nu_{k+1}-1}\, dx_{1}dx_{2}\cdots dx_{k}\\
&=\dfrac{\Gamma(\nu_{1})\cdots\Gamma(\nu_{k+1})}{\Gamma(\nu_{1}+\cdots+\nu_{k+1})}
=\prod_{n=1}^{n=k}B\Bigl(\nu_{n},\sum_{l=n+1}^{k+1}\nu_{l}\Bigr)
\end{split}
\end{equation}
�𓾂�.
\medskip

\noindent
$0<\lambda<1$�ɑ΂���,
\begin{equation}
\begin{split}
&D(\nu_{1},\ldots,\nu_{k};\nu_{k+1}\vert \lambda)\\
&:=\idotsint_{S_{k}\cap \{0< x_{1} \leq \lambda \}} x_{1}^{\nu_{1}-1}\cdots
x_{k}^{\nu_{k}-1}(1-x_{1}-\cdots-x_{n})^{\nu_{k+1}-1}\, dx_{1}\cdots dx_{k}\ (k\geqq 1)
\end{split}
\end{equation}
�Ƃ���.
����
$B(\alpha,\beta\vert\lambda):=D(\alpha;\beta\vert \lambda)\ (\alpha,\beta>0)
$�ƕ\���Ƃ�,
\begin{align}\label{D:lambda}
& D(\nu_{1},\ldots,\nu_{k};\nu_{k+1}\vert\lambda)\\
&=B(\nu_{1},\nu_{2}+\cdots+\nu_{k+1}\vert\lambda)
B(\nu_{2},\nu_{3}+\cdots+\nu_{k+1})B(\nu_{3},\nu_{4}+\cdots+\nu_{k+1})\cdots B(\nu_{k},\nu_{k+1})\notag
\end{align}
�����藧��.������, $m,n$�𐳂̐����Ƃ���Ƃ�
\begin{equation}
\displaystyle B(m,n\vert\lambda)=\int_{0}^{\lambda}x^{m-1}(1-x)^{n-1} dx
=\sum_{i=0}^{n-1}\binom{n-1}{i}(-1)^i\lambda^{m+i}\dfrac{1}{m+i}~~(m,n>0)
\end{equation}
�𓾂�.
% �܂�, 
% \begin{equation}
% \dfrac{d}{d\lambda}B(m,n\vert\lambda)=\lambda^{m-1}(1-\lambda)^{n-1}
% \end{equation}
% �ł��邱�Ƃ����ӂ��Ă�����.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{��ԃx�C�Y�@�ɂ�鎖�O�E������}\label{Sec2}
%section 2
�����ł�, De Robertis \& Hartigan\cite{RoHa81}�ɂ�鎖�O���x��Ԃ�p������ԃx�C�Y�@����}���R�t����ߒ��̐��ڊm���s��
�̋�Ԑ���֓K�p��,��Ԑ���MDPs���\�����鎖���Ԃɂ��čl�@����.

$P(S)=P_{n}=\{p=(p_{1},p_{2},\ldots,p_{n}) \vert p_{i}\geq 0, \sum_{i=1}^{n}p_{i}=1\}$�Ƃ���.
$L(\cdot)$��$P_{n}$��̃��x�[�O���x(\emph{lower bound measure}),
$U(\cdot):=kL(\cdot)$~~(\emph{upper bound measure})�𑪓x$L$�� $k(k>0)$�Ɋւ����ᑪ�x(proportional measure)
�Ƃ�,���O���x��Ԃ�$[L,kL]=[dp,kdp]$�Ƃ���.
�f�[�^ $\sigma=(\sigma_1,\sigma_2,\ldots,\sigma_n)$��
�����Ԃɂ�����$\hat{\sigma}:=\sum_{k=1}^{n}\sigma_{k}$���
�Ɨ����s�����ł��ꂼ����$i$��
$\sigma_{i}$��N�������Ƃ�\��.
���$i$ �̐��N�m����$p_{i}$�ł���Ƃ�,
$p=(p_{1},\ldots,p_{n})\in P_{n}$�ɑ΂���f�[�^$\sigma$��p.d.f.�͑������z�ŕ\�����
\begin{equation}
f(\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\vert p)=
\dfrac{(\sigma_{1}+\cdots+\sigma_{n})!}{\sigma_{1}!\cdots\sigma_{n}!}p_{1}^{\sigma_{1}}
p_{2}^{\sigma_{2}}\cdots p_{n}^{\sigma_{n}}
\end{equation}
�ƂȂ�.
% �����, $\sigma_{i} \ (i\in S) $���p�����[�^�ƍl�����
% �f�B���N�����z$\tilde{D}(\sigma_{1}+1,\sigma_{2}+1,\ldots, \sigma_{n-1}+1;\sigma_{n}+1)$��p.d.f.�ł���.

�f�[�^$\sigma$�ɂ����鎖�㑪�x��Ԃ�$[L_{\sigma},U_{\sigma}]=
[L_{\sigma},kL_{\sigma}]$�Ƃ���.���̊��ɏ��$i$�֐��ڂ���m��$p_{i}$�̂���,
�܂�, $p_{1}$�Ɋւ��鎖�㑪�x���
\[\displaystyle\left\{\dfrac{\int_{P_{n}}p_{1}Q(dp)}{\int_{P_n}Q(dp)}
\Bigg\vert L_{\sigma}\leqq Q \leqq U_{\sigma}\right\}\]
�ɂ��Ē��ׂ�.
�_��\cite{RoHa81}����,��̎��㑪�x���
$[\underline{\lambda},\overline{\lambda}]$�͎��̕������̈�ӂ̉��ł���.
\begin{align}
U_{\sigma}(p_{1}-\underline{\lambda})^{-}+L_{\sigma}(p_{1}-\underline{\lambda})^{+}=0\label{eq:lowlam}\\
U_{\sigma}(p_{1}-\overline{\lambda})^{+}+L_{\sigma}(p_{1}-\overline{\lambda})^{-}=0\label{eq:uplam}
\end{align}
������, $x^{+}=\max\{0,x\},x^{-}=x-x^{+}=\min\{0,x\}$�ł���.

$\hat{\sigma}=\sigma_{1}+\sigma_{2}+\cdots+\sigma_{n},
s=\sigma_{1}+1,t=\hat{\sigma}-\sigma_{1}+n-1$�Ƃ�����,
��(\ref{eq:lowlam})�Ǝ�(\ref{eq:uplam})�͌���,
% \noindent
% \fbox{%
% \parbox{.9\textwidth}%
{\begin{align}%
K(s,t,\lambda):=\left(\dfrac{s}{s+t}-\lambda \right)B(s,t)+(k-1)\left(B(s+1,t\vert\lambda)
-\lambda B(s,t\vert\lambda) \right)=0\label{eq:Kpql}\\%
G(s,t,\lambda):=k\left(\dfrac{s}{s+t}-\lambda \right)B(s,t)-(k-1)\left(B(s+1,t\vert\lambda)
-\lambda B(s,t\vert\lambda) \right)=0\label{eq:Gpql}%
\end{align}}%}\\%
�̕������̉��Ƃ��ĕ\�����. �������$(\hat{\sigma}+n)$���������ɂ��������̉��ł���.

% \noindent
% \fbox{%
% \parbox{\textwidth}%
% {\begin{equation}%
% \label{eq:Gpql}%
% G(p,q,\lambda):=k\left(\dfrac{p}{p+q}-\lambda \right)B(p,q)-(k-1)\left(B(p+1,q\vert\lambda)
% -\lambda B(p,q\vert\lambda) \right)=0
% \end{equation}}}%

% ���l��, lower bound $\underline{\lambda}$ �ɂ��Ē��ׂ�Ǝ�(\ref{integral:1})���,
% \begin{multline}
% k\idotsint\limits_{0\leq p_{1}\leq \lambda,p\in P_{n}}p_{1}^{\sigma_{1}+1}p_{2}^{\sigma_{2}}\cdots p_{n}^{\sigma_{n}}dp
% -k\lambda \idotsint\limits_{0\leq p_{1}\leq \lambda,p\in P_{n}}p_{1}^{\sigma_{1}}p_{2}^{\sigma_{2}}\cdots p_{n}^{\sigma_{n}}dp\\
% +\idotsint\limits_{\lambda\leq p_{1}\leq 1,p\in P_{n}} p_{1}^{\sigma_{1}+1}p_{2}^{\sigma_{2}}\cdots p_{n}^{\sigma_{n}}dp
% -\lambda\idotsint\limits_{\lambda\leq p_{1}\leq 1,p\in P_{n}}p_{1}^{\sigma_{1}}p_{2}^{\sigma_{2}}\cdots p_{n}^{\sigma_{n}}dp=0
% \end{multline}
% ����
% \begin{multline}
% k D(\sigma_{1}+2,\sigma_{2}+1,\ldots,\sigma_{n-1}+1;\sigma_{n}+1\vert \lambda)
% -k\lambda D(\sigma_{1}+1,\sigma_{2}+1,\ldots,\sigma_{n-1}+1;\sigma_{n}+1\vert \lambda)\\
% + \left( D(\sigma_{1}+2,\sigma_{2}+1,\ldots,\sigma_{n-1}+1;\sigma_{n}+1)
% - D(\sigma_{1}+2,\sigma_{2}+1,\ldots,\sigma_{n-1}+1;\sigma_{n}+1\vert \lambda) \right)\\
% -\lambda\left( D(\sigma_{1}+1,\sigma_{2}+1, \ldots, \sigma_{n-1}+1;\sigma_{n}+1)
% - D(\sigma_{1}+1,\sigma_{2}+1, \ldots, \sigma_{n-1}+1;\sigma_{n}+1\vert \lambda) \right)\\
% =0
% \end{multline}
% �ƕ\����Ă���,��(\ref{eq:DB1})��(\ref{eq:DB2})���
% \begin{multline}
% kB(\sigma_{1}+2,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert\lambda)
% -k\lambda B(\sigma_{1}+1,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert \lambda)\\
% +B(\sigma_{1}+2,\sigma_{2}+\cdots+\sigma_{n}+n-1)
% -B(\sigma_{1}+2,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert\lambda)\\
% -\lambda B(\sigma_{1}+1,\sigma_{2}+\cdots+\sigma_{n}+n-1)
% +\lambda B(\sigma_{1}+1,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert \lambda)=0
% \end{multline}
% �ƂȂ�.���������
% \begin{multline}
% B(\sigma_{1}+2,\sigma_{2}+\cdots+\sigma_{n}+n-1)
% -\lambda B(\sigma_{1}+1,\sigma_{2}+\cdots+\sigma_{n}+n-1)\\
% +(k-1)B(\sigma_{1}+2,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert\lambda)
% -(k-1)\lambda B(\sigma_{1}+1,\sigma_{2}+\cdots+\sigma_{n}+n-1\vert \lambda)=0
% \end{multline}
% �ƂȂ邩�� lower bound $\underline{\lambda}$ �Ɋւ��鎟�̂悤�ȕ������𓾂邱�Ƃ��ł���:\\
% \noindent
% \fbox{%
% \parbox{\textwidth}%
% {\begin{equation}%
% \label{eq:Kpql}%
% K(p,q,\lambda):=\left(\dfrac{p}{p+q}-\lambda \right)B(p,q)+(k-1)\left(B(p+1,q\vert\lambda)
% -\lambda B(p,q\vert\lambda) \right)=0
% \end{equation}}}%

\begin{thm}
�f�[�^$\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{n}),
\hat{\sigma}=\sum_{i=1}^{n}\sigma_{i}$�Ƃ���.
���O���x��Ԃ�$[L,kL]$�Ƃ���Ƃ�,
$p=(p_{1},p_{2},\ldots,p_{n})$��$p_{i}$�ɂ��Ă̎��㑪�x���
$[\underline{\lambda},\overline{\lambda}]$�͎��̂��ꂼ��̕������̈�ӂ̎������ł���.
\begin{align*}
K(\sigma_{i}+1,\hat{\sigma}+n-\sigma_{i}-1,\lambda)=0,
G(\sigma_{i}+1,\hat{\sigma}+n-\sigma_{i}-1,\lambda)=0.
\end{align*}
\end{thm}





%%%%%%%%%%%%%%%%%%%%% sec. 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%% sec. 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A numerical experiment}\label{Sec4}
�O�߂܂ł̑������z�Ɋւ��ď�Ԃ̌�$n=3$�̂Ƃ����l����.
$P_{3}=\{p=(p_{1},p_{2},p_{3})\vert \sum_{i=1}^{3}p_{i}=1,p_{i}\geq 1,i=1,2,3\}$�Ƃ���,
$k=2$�Ƃ���,
���Ȃ킿���O���x��Ԃ�$[L,2L]$�Ƃ���.
���錈�܂�����Ԃ���$\hat{\sigma}=6$��̎��s���Ȃ���,
6��,���1��3��,���2��1��,���3��2�񐄈ڂ����Ƃ���.
�����, $\sigma_{1}=3,\sigma_{2}=1,\sigma_{3}=2$�ł���,
%\begin{align*}
$\hat{\sigma}=\sigma_{1}+\sigma_{2}+\sigma_{3}=6,
s=\sigma_{1}+1=4,
t=\sigma_{2}+\sigma_{3}+(n-1)=5$
%\end{align*}
�̃f�[�^�������Ă���Ƃ���.
 Theorem 5.1 ���, $\overline{\lambda}$�Ɋւ���%��������
% \begin{equation}
% 2\left(\dfrac{4}{6+3}-\lambda \right)B(4,5)-\left(\sum_{i=0}^{4}\binom{4}{i}
% (-1)^{i+1}\lambda^{5+i}\left( \dfrac{1}{(4+i)(5+i)}\right) \right)=0
% \end{equation}
% ���
9��������
$8-18\lambda+\lambda^{5}(126-336\lambda+360\lambda^2-180\lambda^3+35\lambda^4)=0
$��������,��$\overline{\lambda}\fallingdotseq 0.489$�𓾂�.
�܂�, $\underline{\lambda}$�Ɋւ���%��������
% \begin{equation}
% \left(\dfrac{4}{6+3}-\lambda \right)B(4,5)+\left(\sum_{i=0}^{4}\binom{4}{i}
% (-1)^{i+1}\lambda^{5+i}\left( \dfrac{1}{(4+i)(5+i)}\right) \right)=0
% \end{equation}
% ���, 
������$
4-9\lambda-\lambda^{5}(126-336\lambda+360\lambda^2-180\lambda^3+35\lambda^4)=0
$��������,���Ƃ���$\underline{\lambda}\fallingdotseq 0.400$�𓾂�.
�����$p_{1}$�̎��㑪�x��Ԃ�$[0.400,0.489]$�ƍl������.

% ���l�ɂ���,��Ԑ�$N=3$,������$\hat{\sigma}$�����낢��ω��������Ƃ���
% $p_{1},p_{2},p_{3}$�̎��㑪�x��Ԃ��܂Ƃ߂�.
% $\sigma_{1},\sigma_{2},\sigma_{3}$�͂��ꂼ����$i$�ł̊ϑ��l(��)�Ƃ���.
% \medskip

% \begin{figure}[h]
% \begin{minipage}{.48\textwidth}
% \noindent $\hat{\sigma}=6\text{(������)},\sigma_{1}=3,\sigma_{2}=1,\sigma_{3}=2$�̂Ƃ�,\\
% \begin{tabular}{|c|c|c|}
% \hline
% \Topspc\Btmspc $p_{1}=[\underline{p}_{1},\overline{p}_{1}]$ &
% $p_{2}=[\underline{p}_{2},\overline{p}_{2}]$ &
% $p_{3}=[\underline{p}_{3},\overline{p}_{3}]$ \\
% \hline
% \Topspc\Btmspc $[0.400,0.489]$ & $[0.187,0.260]$ & $[0.292,0.376]$\\
% \hline
% \end{tabular}
% \end{minipage}
% \begin{minipage}{.48\textwidth}
% \noindent $\hat{\sigma}=15,\sigma_{1}=7,\sigma_{2}=3,\sigma_{3}=5$�̂Ƃ�,\\
% \begin{tabular}{|c|c|c|}
% \hline
% \Topspc\Btmspc $p_{1}=[\underline{p}_{1},\overline{p}_{1}]$&
% $p_{2}=[\underline{p}_{2},\overline{p}_{2}]$&
% $p_{3}=[\underline{p}_{3},\overline{p}_{3}]$\\
% \hline
% \Topspc\Btmspc $[0.413,0.476]$ & $[0.197,0.249]$ & $[0.304,0.364]$\\
% \hline
% \end{tabular}
% \end{minipage}
% \medskip

% \begin{minipage}{.48\textwidth}
% \noindent $\hat{\sigma}=30,\sigma_{1}=16,\sigma_{2}=5,\sigma_{3}=9$�̂Ƃ�,\\
% \begin{tabular}{|c|c|c|}
% \hline
% \Topspc\Btmspc $p_{1}=[\underline{p}_{1},\overline{p}_{1}]$&
% $p_{2}=[\underline{p}_{2},\overline{p}_{2}]$&
% $p_{3}=[\underline{p}_{3},\overline{p}_{3}]$\\
% \hline
% \Topspc\Btmspc $[0.491,0.539]$ & $[0.164,0.201]$ & $[0.281,0.325]$\\
% \hline
% \end{tabular}
% \end{minipage}
% \begin{minipage}{.48\textwidth}
% \noindent $\hat{\sigma}=50,\sigma_{1}=24,\sigma_{2}=9,\sigma_{3}=17$�̂Ƃ�,\\
% \begin{tabular}{|c|c|c|}
% \hline
% \Topspc\Btmspc $p_{1}=[\underline{p}_{1},\overline{p}_{1}]$&
% $p_{2}=[\underline{p}_{2},\overline{p}_{2}]$&
% $p_{3}=[\underline{p}_{3},\overline{p}_{3}]$\\
% \hline
% \Topspc\Btmspc $[0.453,0.491]$ & $[0.174,0.204]$ & $[0.322,0.358]$ \\
% \hline
% \end{tabular}
% \end{minipage}
% \caption{���l������(��Ԑ�$N=3$)}
% \end{figure}
% \medskip

$k=1$,���Ȃ킿,���O���x��ԂƂ��ă��x�[�O���x���l�����Ƃ�,���㑪�x��Ԃ����߂����������
$p_{i}=[\underline{p}_{i},\overline{p}_{i}]=\frac{\sigma_{i}+1}{\hat{\sigma}+n}
$
��1�_�ŕ\�����.�����,��l���O���z���l�����Ƃ��̊ϑ��l$(\sigma_{1},\sigma_{2},\sigma_{3})$�ɂ��
�f�B���N�����z(�������x�[�^���z)�̃p�����[�^$p_{i}$�̎��㕪�z�ł̊��Ғl�ɓ�����.

%\include{INC_ExampleDSPolicy}

�����, ���l�������s�����㑪�x��Ԃ����Ƃɂ���Markov set-chain�̖���
�����Ă݂�(cf. \cite{HrWeb}).
��Ԑ�$n=3,S=\{1,2,3\}$, policy�͌Œ�(deterministic stationary policy)�Ƃ���
�������$x_{1}=1$�����20���̏��$x_{20}$���ϑ�����܂ł̂�����,
���ꂼ��̏�Ԃ��玟�̊��ɐ��ڂ����p�x�𒲂ׂ��Ƃ���,
Table 6.1 ����̂悤�ȍs��ł������Ƃ���.
�Ⴆ��,���2����̐��ڂł�, ���̍s��̑�2�s�ڂ�����,
$6$��̎��s�����Ŏ��̊��ɂ��ꂼ����1��$\sigma_{1}=1$��,
���2��$\sigma_{2}=3$��,���3��$\sigma_{3}=3$��̐��ڂ��ϑ������Ƃ���.

�e���$i$�ɂ�����$p_{i1},p_{i2},p_{i3}$�̎��㑪�x��Ԃ�,
�{����Theorem 5.1����ȉ��̂悤�ɓ�����(Table 6.1).
$\sigma_{1},\sigma_{2},\sigma_{3}$�͂��ꂼ����$i$�ł̊ϑ��l(���ډ�)�Ƃ���.
%\medskip

\begin{table}[h]
\begin{small}
\caption{Intervals of posterior measures}
%\begin{center}

\begin{minipage}{.48\textwidth}
\begin{center}
��Ԃ̊ϑ��x��:$\begin{pmatrix}
3 & 1 & 2\\
1 & 3 & 2\\
1 & 2 & 4
\end{pmatrix}
$
\end{center}
\end{minipage}
\begin{minipage}{.48\textwidth}
\noindent ���1, 
$\hat{\sigma}=6\text{(������)},\sigma_{1}=3,\sigma_{2}=1,\sigma_{3}=2$�̂Ƃ�:\\
\begin{tabular}{|c|c|c|}
\hline
\Topspc\Btmspc $\hat{p}_{11}=[\underline{p}_{11},\overline{p}_{11}]$ &
$\hat{p}_{12}=[\underline{p}_{12},\overline{p}_{12}]$ &
$\hat{p}_{13}=[\underline{p}_{13},\overline{p}_{13}]$ \\
\hline
\Topspc\Btmspc $[0.400,0.489]$ & $[0.187,0.260]$ & $[0.292,0.376]$\\
\hline
\end{tabular}
\end{minipage}
\medskip

\begin{minipage}{.48\textwidth}
\noindent ���2, $\hat{\sigma}=6,\sigma_{1}=1,\sigma_{2}=3,\sigma_{3}=2$�̂Ƃ�:\\
\begin{tabular}{|c|c|c|}
\hline
\Topspc\Btmspc $\hat{p}_{21}=[\underline{p}_{21},\overline{p}_{21}]$ &
$\hat{p}_{22}=[\underline{p}_{22},\overline{p}_{22}]$ &
$\hat{p}_{23}=[\underline{p}_{23},\overline{p}_{23}]$ \\
\hline
\Topspc\Btmspc  $[0.187,0.260]$ & $[0.400,0.489]$ & $[0.292,0.376]$\\
\hline
\end{tabular}
\end{minipage}
\begin{minipage}{.48\textwidth}
\noindent ���3, $\hat{\sigma}=7,\sigma_{1}=1,\sigma_{2}=2,\sigma_{3}=4$�̂Ƃ�:\\
\begin{tabular}{|c|c|c|}
\hline
\Topspc\Btmspc $\hat{p}_{31}=[\underline{p}_{31},\overline{p}_{31}]$&
$\hat{p}_{32}=[\underline{p}_{32},\overline{p}_{32}]$&
$\hat{p}_{33}=[\underline{p}_{33},\overline{p}_{33}]$\\
\hline
\Topspc\Btmspc $[0.168,0.235]$ & $[0.262,0.334]$ & $[0.458,0.542]$\\
\hline
\end{tabular}
\end{minipage}
%\end{center}
\end{small}
\end{table}
\medskip

% $\calQ=\langle \underline{Q},\overline{Q}\rangle=\{Q\in P(S\vert S\times A)\vert
% \underline{Q}\leqq Q \leqq \overline{Q}\}$�Ƃ���Ƃ�,
% $\calQ$�� Lemma 2.1���ʑ��ʑ̂ł��邩��,����[�_�̏W��
% $\{Q^{(1)},Q^{(2)},\ldots,Q^{(l)}\}$�ɂ����$\calQ=\mathrm{conv}\{Q^{(1)},Q^{(2)},\ldots,Q^{(l)}\}$
% �ƕ\�����Ƃ��ł���.
% $\calQ \ni Q=(q_{ij})$�ɂ���,�e$i$�s�ڂ��Ƃɐ��ڊm���s��̏���
% $\sum_{j=1}^{3}q_{ij}=1\ (i=1,2,3)$���݂����[�_���ׂ�. 
$\calQ=\langle \underline{Q},\overline{Q}\rangle$�̑�$i$�s�ڂɊւ���ʑ��ʑ̂�$\hat{q}_{i}\ (i=1,2,3)$�Ƃ����Ƃ�,����
�[�_�̏W��$\mathrm{ext}(\hat{q}_{i})$�͂��ꂼ��ȉ��̂悤�ɂȂ�:
$\mathrm{ext}(\hat{q}_{1})=\{(0.437,0.187,0.376),(0.4,0.224,0.376),(0.448,0.26,0.292),
(0.489,0.219,\\
0.292),
(0.4,0.26,0.34),(0.489,0.187,0.324)\},$
$\mathrm{ext}(\hat{q}_{2})=\{(0.187,0.437,0.376),(0.224,0.4,0.376),(0.26,\\
0.448,0.292),
(0.219,0.489,0.292),
(0.26,0.4,0.34),(0.187,0.489,0.324)\},$
$\mathrm{ext}(\hat{q}_{3})=\{(0.196,0.262,0.542),\\
(0.168,0.29,0.542),(0.208,0.334,0.458),
(0.235,0.307,0.458),
(0.168,0.334,0.498),(0.235,0.262,0.503)\}$
�𓾂�.
% $\calQ$�̒[�_�W����, $\hat{q}_{1},\hat{q}_{2},\hat{q}_{3}$�̒[�_���炻�ꂼ��
% ����I��ō�鐄�ڊm���s��$Q^{(l)}$���琬��($6^{3}$��).






$\beta=0.9,\bm{r}=(3,1,2)',F\ni f$(�Œ�)�Ƃ���
%\begin{align*}%(3.5),(3.6)
$\underline{L}(f) \bm{x} = \bm{r}(f)+\beta \min_{Q\in \calQ(f)}Q\bm{x}%\label{def:LwLf}
,
\overline{L}(f) \bm{x} = \bm{r}(f)+\beta \max_{Q\in \calQ(f)}Q\bm{x}%\label{def:UpLf}
$
%\end{align*}
�̕s���_�����߂Ă݂��, $\underline{\phi}(f)=(20.003,17.508,18.643),
\overline{\phi}(f)=(21.732,19.232,20.339)$�𓾂�.
�]����, Theorem 3.1����$\phi(f\vert \calQ(f))=[\underline{\phi}(f),\overline{\phi}(f)]=\phi(f\vert \calQ(f))=([20.003,21.732],[17.508,\\
19.232],[18.643,20,339])
$�𓾂�.
�^�̐��ڊm���s��� $Q=(q_{1\cdot},q_{2\cdot},q_{3\cdot})^{\prime},
q_{1\cdot}=(\frac{1}{2},  \frac{1}{6}, \frac{1}{3}),
q_{2\cdot}=(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}),\\
q_{3\cdot}=(\frac{2}{5}, \frac{2}{5}, \frac{1}{5})$
�ł���Ƃ���value fanction�̒l��$\phi=(22.469,20.116,21.135)$�ł���.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{��ԃx�C�YMDPs}
�ŏ���, ��Ԑ���MDPs$\{\calQ\}$��$\calQ\in %P(S\vert S\times A)
\calM_{n}$�Ɋւ���A����
���ؖ�����.
����, ���O������ԃx�C�Y�@�ɂ���ď��������f�[�^���g���ċ�ԃx�C�YMDPs���`����.

�܂�,
$\calQ=\langle \underline{Q},\overline{Q}\rangle\in \calM_{n}$��$\underline{Q},\overline{Q}\in 
\bR_{+}^{n\times n}$�̘A�����ɂ��Ď�����.
�������藧��. ������, �����͊e��ԂɑΉ����ă��[�N���b�h�����ƃn�E�X�h���t�����ɑΉ����Ă���.

\begin{lem}\label{lem:5.1}
%\begin{itemize}
%\item[(i)] 
(i) $\underline{Q}_{t}\downarrow \underline{Q},
\overline{Q}_{t}\uparrow \overline{Q}\ (t\to \infty),
\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\neq \emptyset\ (t\geqq 1)$
�Ƃ���Ƃ�, $\langle \underline{Q}_{t},\overline{Q}_{t}\rangle \xrightarrow{\rho}
\langle \underline{Q},\overline{Q}\rangle \ (t\to \infty)$.
%\item[(ii)] 
(ii) $\underline{Q}_{t}\uparrow \underline{Q},
\overline{Q}_{t}\downarrow \overline{Q}\ (t\to \infty),
\langle \underline{Q},\overline{Q}\rangle\neq \emptyset\ (t\geqq 1)$
�Ƃ���Ƃ�, $\langle \underline{Q}_{t},\overline{Q}_{t}\rangle \xrightarrow{\rho}
\langle \underline{Q},\overline{Q}\rangle \ (t\to \infty)$.
%\end{itemize}
\end{lem}

\noindent{\it Proof.} (i)
$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle \uparrow$���
$\{\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\}$�͎���
(i.e., $\limsup_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle
=\liminf_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle$)
����, $\lim_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle
=\overline{\cup_{t=1}^{\infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle}$
(��)�ł�����,
$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle \subset \langle \underline{Q},\overline{Q}\rangle$ for all $t\geqq 1$���
\begin{equation}\label{subset}
\lim_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle
\subset \langle \underline{Q},\overline{Q}\rangle
\end{equation}
�ł���.
$\forall Q\in \langle \underline{Q},\overline{Q}\rangle$�����.
$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\neq \empty\ (t\geqq 1)$���
$\exists Q'\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle \ (t\geqq 1)$�ł�����
$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle \subset
\langle \underline{Q},\overline{Q}\rangle$���,
$Q' \in \langle \underline{Q},\overline{Q}\rangle.$
$0 \leqq \alpha \leqq 1$�ɑ΂���,
$
Q(\alpha)=\alpha Q+(1-\alpha)Q'
$
�Ƃ���.���̂Ƃ�,
$Q(0)=Q'\in \langle \underline{Q},\overline{Q}\rangle,
Q(1)=Q\in \langle \underline{Q},\overline{Q}\rangle$
����
Lemma 2.1(i)���
$\langle \underline{Q},\overline{Q}\rangle$�͓ʏW���ł��邩��
\begin{equation}\label{conv}
Q(\alpha)\in\langle \underline{Q},\overline{Q}\rangle\ \ \text{ for all $0\leqq \alpha \leqq 1$}.
\end{equation}
$Q(0)=Q'\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle $ for all $t\geqq 1$
�ɒ��ӂ���,
$\alpha_{t}:=\sup\{\alpha \vert Q(\alpha)\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle\}
\ (t\geqq 1)$�Ƃ����,
$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle$�̓R���p�N�g�ȓʏW���ł���,
����$\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\subset
\langle \underline{Q}_{t+1},\overline{Q}_{t+1}\rangle\ (t\geqq 1)$���,
$Q(\alpha)\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle$ 
for all $0\leqq \alpha \leqq \alpha_{t}$��
$\alpha_{t}\leqq \alpha_{t+1}\leqq 1 \ (t\geqq 1)$�����藧��.

$\alpha^{*}:=\lim_{t\to\infty}\alpha_{t}$�Ƃ���.
$\alpha^{*}<1$�Ƃ����$\alpha^{*}<\alpha\leqq 1$�Ȃ�$\alpha$�ɑ΂���
$Q(\alpha)\notin \langle \underline{Q},\overline{Q}\rangle$
�ƂȂ邪,����͎�(\ref{conv})�ɖ�������.�̂�, $\alpha^{*}=1$.
�]����,
$Q(\alpha_{t})\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle
\to Q(1)=Q \ (t\to \infty).$
�����, $\limsup_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle
\supset \langle \underline{Q},\overline{Q}\rangle$���Ӗ�����.
$\limsup_{t\to\infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle=
\lim_{t\to\infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle$�ł��邩��
\begin{equation}\label{supset}
\lim_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\supset 
\langle \underline{Q},\overline{Q}\rangle.
\end{equation}
��(\ref{subset})�Ǝ�(\ref{supset})���
$
\lim_{t\to \infty} \langle \underline{Q}_{t},\overline{Q}_{t}\rangle
=\langle \underline{Q},\overline{Q}\rangle.
$
�����(i)�������ꂽ. (ii)�͖��炩�ɐ��藧��.\qed



% \noindent{\it Proof.} (i)
% $\underline{Q}\leqq \underline{Q}_{t},\overline{Q}_{t}\leqq \overline{Q}(componentwise)$
% ���,���ڊm���s��
% $Q\in \langle \underline{Q}_{t},\overline{Q}_{t}\rangle:=D_{t}  \Rightarrow 
% Q\in \langle \underline{Q},\overline{Q} \rangle:=D_{1}$,
% ���Ȃ킿, $D_{t}\subset D_{1}$�����藧��.
% �����,
% \begin{align*}
% &\rho(D_{t},D_{1})
% =\max\{\sup_{Q_{t}\in D_{t}}\inf_{Q\in D_{1}} \Vert Q_{t}- Q\Vert,
%  \sup_{Q\in D_{1}}\inf_{Q_{t}\in D_{t}} \Vert Q_{t}- Q\Vert\}\\
% &=\sup_{Q\in D_{1}}\inf_{Q_{t}\in D_{t}} \Vert Q_{t}- Q\Vert\\
% &\leqq nk\max_{i,j,a}\{|\underline{q}_{ij}(a)-\underline{q}_{ij}^{t}(a)|,
% |\overline{q}_{ij}(a)-\overline{q}_{ij}^{t}(a)|\}\to 0 \ \ \text{(as $t\to \infty$).}
% \end{align*}
% \\
% (ii) (i)�Ɠ��l�ɍl����,
% $\underline{Q}_{t}\leqq \underline{Q},\overline{Q}\leqq \overline{Q}_{t}(componentwise)$
% ���,���ڊm���s��
% $Q\in \langle \underline{Q},\overline{Q}\rangle:=D_{1}  \Rightarrow 
% Q\in \langle \underline{Q}_{t},\overline{Q}_{t} \rangle:=D_{t}$,
% ���Ȃ킿, $D_{1}\subset D_{t}$�����藧��.
% �����,
% \begin{align*}
% &\rho(D_{t},D_{1})
% =\max\{\sup_{Q_{t}\in D_{t}}\inf_{Q\in D_{1}} \Vert Q_{t}- Q\Vert,
%  \sup_{Q\in D_{1}}\inf_{Q_{t}\in D_{t}} \Vert Q_{t}- Q\Vert\}\\
% &=\sup_{Q_{t}\in D_{t}}\inf_{Q\in D_{1}} \Vert Q_{t}- Q\Vert\\
% &\leqq nk\max_{i,j,a}\{|\underline{q}_{ij}^{t}(a)-\underline{q}_{ij}(a)|,
% |\overline{q}_{ij}^{t}(a)-\overline{q}_{ij}(a)|\}\to 0 \ \ \text{(as $t\to \infty$).\qed}
% \end{align*}







\medskip
���Lemma \ref{lem:5.1}��p���Ď����������.
\begin{thm}\label{thm:5.1}
$\underline{Q}_{t}\to \underline{Q},
\overline{Q}_{t}\to \overline{Q}\ (t\to \infty),
\calQ_{t}:=\langle \underline{Q}_{t},\overline{Q}_{t}\rangle\neq \emptyset\ (t\geqq 1),
\calQ:=\langle \underline{Q},\overline{Q}\rangle$�Ƃ���.
���̂Ƃ�, �������藧��:
%\begin{itemize}
%\item[(i)] 
(i) $\calQ_{t}\to\calQ\ (t\to \infty)$.
%\item[(ii)] 
(ii) $\phi(f\vert \calQ_{t})\to \phi(f\vert \calQ)\ (t\to \infty) \ (f\in F).$
%\end{itemize}
\end{thm}

\noindent{\it Proof.}
(i) $\forall \varepsilon >0$�ɑ΂���
$\limsup_{t\to \infty}\calQ_{t}=
\limsup_{t\to \infty}\langle \underline{Q}_{t},\overline{Q}_{t}\rangle
\subset \langle \underline{Q}-\varepsilon E,\overline{Q}+\varepsilon E\rangle,$
������, $E=(e_{ij})$��$e_{ij}=1 \ (1\leqq i,j\leqq n)$�Ƃ���.
���̂Ƃ�,
$\liminf_{t\to \infty}\calQ_{t}=
\liminf_{t\to\infty} \langle \underline{Q}_{t},\overline{Q}_{t}\rangle
\supset
\langle \underline{Q}+\varepsilon E,\overline{Q}-\varepsilon E\rangle$ 
�ł�����, ������$\varepsilon \to 0$�Ƃ����Lemma \ref{lem:5.1}
���
$\lim_{\varepsilon \to 0}\langle \underline{Q}-\varepsilon E,\overline{Q}+\varepsilon E\rangle
=
\lim_{\varepsilon \to 0}\langle \underline{Q}+\varepsilon E,\overline{Q}-\varepsilon E\rangle
=\langle \underline{Q},\overline{Q}\rangle.
$
�̂�, $\{\calQ_{t}\}$�͎�������$\lim_{t\to \infty}\calQ_{t}=\calQ$�𓾂�.
% (i) ���\ref{lem:5.1}��薾�炩.\\
(ii) (i)���, $\calQ_{t}\to \calQ$������, $\bm{x}\in \bR_{+}$�ɂ���
$\min_{Q\in \calQ_{t}}Q\bm{x}\to \min_{Q\in \calQ}Q\bm{x},
\max_{Q\in \calQ_{t}}Q\bm{x}\to \max_{Q\in \calQ}Q\bm{x}\ (t\to \infty).$
�]����
$\underline{L}_{t}(f)\underline{\phi}_{t}(f)\to \underline{L}(f)\underline{\phi}(f),
\overline{L}_{t}(f)\overline{\phi}_{t}(f)\to \overline{L}(f)\overline{\phi}(f)\ (t\to \infty).$
�藝\ref{thm:3.1}����$\phi(f\vert \calQ)=[\underline{\phi}(f),\overline{\phi}(f)]$�ł��邩��
$\phi(f\vert \calQ_{t})\to \phi(f\vert \calQ)\ (t\to \infty)$�𓾂�.\qed
\medskip



�^�̐��ڊm���s��$Q\in P(S\vert S\times A)$�ɂ��MDPs$\{Q\}$��$t$���̏�Ԃƍs����
���ꂼ��$X_{t},\Delta_{T}\ (t\geqq 0)$�ŕ\��, $t$���܂ł̗�����
$H_{t}=(X_{0},\Delta_{0},X_{1},\Delta_{1},\ldots,X_{t})$�Ƃ���.
�C�ӂ�$i,j\in S,a\in A$�ɑ΂���
\begin{equation}\label{def:NT}
N_{T}(j\vert i,a, H_{T}):=\sum_{t=0}^{T-1}I_{\{X_{t}=i,\Delta_{t}=a,X_{t+1}=j\}}
\ (T\geqq 1)
\end{equation}
�Ƃ���.
�e$i\in S,a\in A$�ɑ΂���, �������z�̐��N�m��
$\{p_{j}=p_{ij}(a), \ (1\leqq j \leqq n)\}$�ɑ΂���ϑ��l
$\{N_{T}(j\vert i,a,H_{T}), \ 1\leqq j \leqq n \}$�ɂ��x�C�Y��Ԃ�
$\calQ(H_{T})=\langle \underline{Q}(H_{T}),\overline{Q}(H_{T})\rangle=
\langle(\underline{q}_{ij}(a\vert H_{T})),(\overline{q}_{ij}(a\vert H_{T}))\rangle$
�Ƃ���.���Ȃ킿,
%\begin{align}
$\underline{Q}(H_{T}):=(\underline{q}_{ij}(a\vert H_{T}):
\ i,j\in S, a\in A)\in \bR_{+}^{n\times nk},
\overline{Q}(H_{T}):=(\overline{q}_{ij}(a\vert H_{T}):
\ i,j\in S, a\in A)\in \bR_{+}^{n\times nk}$
%\end{align}
�Ƃ���,
%\begin{equation}%\label{}
$\calQ(H_{T})=\langle \underline{Q}(H_{T}),\overline{Q}(H_{T}) \rangle$
%\end{equation}
�Ƃ���.
$Q\in P(S\vert S\times A)$�ɑ΂���, MDPs$\{Q\}$�����O���$H_{T}$��
��ԃx�C�Y$\calQ(H_{T})$�Ő��肵��MDPs��
��ԃx�C�YMDPs$\{\calQ(H_{T})\}$�ƌ���.
%\begin{equation}%\label{}
$N_{T}(i,a\vert H_{T}):=\sum_{j\in S} N_{T}(j\vert i,a,H_{T})\ (i\in S,a\in A)$
%\end{equation}
�Ƃ���.

��ԃx�C�Y�̐���(\cite{RoHa81})�����Theorem \ref{thm:5.1}��p����
���̌��ʂ𓾂�.

\begin{thm}\label{thm:5.2}
$\{X_{0},\Delta_{0},X_{1},\Delta_{1},\ldots\}$��MDPs$\{Q\}$����̉ߒ��Ƃ���.
�C�ӂ�$i\in S,a\in A$�ɑ΂���, �m��1��
$N_{T}(i,a\vert H_{T})\to \infty\ (T\to \infty)
$
�Ƃ���.���̂Ƃ�, �m��1�ŋ�ԃx�C�YMDPs$\{\calQ(H_{T})\}$��
MDPs$\{Q\}$�Ɏ�������, ���Ȃ킿, �������藧��.
%\begin{itemize}
%\item[(i)] 
(i) $\calQ(H_{T})\to \{Q\}\ (T\to \infty)$,
%\item[(ii)] 
(ii) $\phi(f\vert \calQ(H_{T}))\to \phi(f\vert Q)\ (T\to \infty), \ (f\in F).$
%\end{itemize}
\end{thm}

\noindent{\it Proof.}
Theorem \ref{thm:5.2}�̏��������藧�Ă�, \cite{RoHa81}�̒藝5.2���
$\underline{Q}(H_{T}),\overline{Q}(H_{T})\to Q\ (T\to \infty)$ 
�𓾂�. �]����, Theorem \ref{thm:5.1}���(i),(ii)�����藧���Ƃ��킩��.\qed


%\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{Mart67}
\nocite{vHee78}
\nocite{Furu80}
\nocite{Krtw66}
\nocite{So03}

% \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
%%%%%%%%%%%%%%%%%%%%
%\begin{multicols}{2}
%\harvardparenthesis{round}
%\bibliographystyle{agsm}%{plain}%
\bibliographystyle{plain}%
%\bibliography{myrefs.bib}
\begin{thebibliography}{10}

\bibitem{RoHa81}
L.~De~Robertis and J.~A. Hartigan.
\newblock Bayesian inference using intervals of measures.
\newblock {\em Ann. Statist.}, 9(2):235--244, 1981.

\bibitem{DS80}
B. Doshi and S.~E. Shreve.
\newblock Strong consistency of a modified maximum likelihood estimator for
  controlled {M}arkov chains.
\newblock {\em J. Appl. Probab.}, 17(3):726--734, 1980.

\bibitem{Furu80}
N. Furukawa.
\newblock Characterization of optimal policies in vector-valued {M}arkovian
  decision processes.
\newblock {\em Math. Oper. Res.}, 5(2):271--279, 1980.

\bibitem{Hart98}
D. J. Hartfiel.
\newblock {\em Markov set-chains}, volume 1695 of {\em Lecture Notes in
  Mathematics}.
\newblock Springer-Verlag, Berlin, 1998.

\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{HrWeb}
M.~Horiguchi. Examples for Bayesian approach to uncertain MDPs, \\
\newblock {\bf URL} http://www.math.kanagawa-u.ac.jp/\~{}horiguchi/


\bibitem{IHYK07}
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 Informatics and Cybernetics}, 39:11--24, 2007.

\bibitem{KSHH98}
M. Kurano, J. Song, M. Hosaka, and Y. Huang.
\newblock Controlled {M}arkov set-chains with discounting.
\newblock {\em J. Appl. Probab.}, 35(2):293--302, 1998.

\bibitem{KYN02}
M. Kurano, M. Yasuda, and J. Nakagami.
\newblock Interval methods for uncertain {M}arkov decision processes.
\newblock In {\em Markov processes and controlled {M}arkov chains ({C}hangsha,
  1999)}, pages 223--232. Kluwer, 2002.

\bibitem{Krtw66}
K.~Kuratowski.
\newblock {\em Topology. {V}ol. {I}}.
\newblock New edition, revised and augmented. Translated from the French by J.
  Jaworowski. Academic Press, 1966.

\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.,
1967.

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

\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{vHee78}
K.~M. van Hee.
\newblock {\em Bayesian control of {M}arkov chains}, volume~95 of {\em
  Mathematical Centre Tracts}.
\newblock Mathematisch Centrum, 1978.

\bibitem{Wlks62}
S.~S. Wilks.
\newblock {\em Mathematical statistics}.
\newblock A Wiley Publication in Mathematical Statistics. John Wiley \& Sons
  Inc., 1962.
\newblock
  �c���p�V�C��{����i��j�C�u�������v�w�E�����V��1,2�v�C1971,1972�N�C�����}��.

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

\harvardparenthesis{round}
\bibliographystyle{agsm}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
