\batchmode
\documentstyle[12pt]{book}
\makeatletter


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
%













\newcounter{bibliosection}

  


\newcounter{example}


\newcounter{exercise}





  





  






















































































\input psfig   %








\def\CE#1#2{{{E}\left\{{#1}{\mid}{#2}\right\}}}

\def\CEpi#1#2{{{E_\pi}\!\left\{{#1}{\mid}{#2}\right\}}}

\def\CEpip#1#2{{{E_{\pi^\prime}}\!\left\{{#1}{\mid}{#2}\right\}}}

\def\CEpistar#1#2{{{E_{\pi^*}}\!\left\{{#1}{\mid}{#2}\right\}}}

\def\CEggpistar#1#2{{{E_{\pi^*}}\!\biggl\{#1\biggm|#2\biggr\}}}

\def\CEggpi#1#2{{{E_\pi}\!\biggl\{#1\biggm|#2\biggr\}}}

\def\CEgpi#1#2{{{E_\pi}\!\Bigl\{#1\Bigm|#2\Bigr\}}}

\def\hatCE#1#2{{\hat {E}\left\{{#1}{\mid}{#2}\right\}}}

\def\CEgg#1#2{{{E}\biggl\{#1\biggm|#2\biggr\}}}

\def\E#1{{{E}\left\{#1\right\}}}

\def\Epi#1{{{E_\pi}\!\left\{#1\right\}}}

\def\Eggpi#1{{{E_\pi}\!\biggl\{#1\biggr\}}}

\def\Epip#1{{{E_{\pi^\prime}}\!\left\{#1\right\}}}

\def\Ea#1{{{E_a}\!\left\{#1\right\}}}

\def\Egg#1{{{E}\biggl\{#1\biggr\}}}

\def\CP#1#2{{{Pr}\left\{{#1}{\mid}{#2}\right\}}}

\def\Pr#1{{{Pr}\left\{#1\right\}}}

\def\w{{\bf w}}

\def\cross{\times}

\def\grad{\nabla}

\def\first#1#2{{\partial #1\over \partial #2}}

\def\second#1#2{{\partial^2 #1\over \partial #2^2}}

\def\implies{\Rightarrow}

\def\union{\cup}

\def\bibliosection#1{%
  \addtocounter{bibliosection}{1}%
  \medskip\goodbreak
  {\bf \arabic{chapter}.\arabic{bibliosection} #1}
  \smallskip}

\def\skipbibliosection{\addtocounter{bibliosection}{1}}

\def\example{
  \addtocounter{example}{1}
  \smallskip
  \noindent
  {\bf Example \arabic{chapter}.\arabic{example}}~~}

\def\exercise{
  \addtocounter{exercise}{1}
  \smallskip
  \noindent
  {\bf Exercise \arabic{chapter}.\arabic{exercise}}~~ }

\def\pexercise{
  \addtocounter{exercise}{1}
  \smallskip
  \noindent
  {\bf Exercise \arabic{chapter}.\arabic{exercise}~(programming)~~}}

\def\starredexercise{
  \addtocounter{exercise}{1}
  \smallskip
  \noindent
  {\bf Exercise \arabic{chapter}.\arabic{exercise}*~}}

\def\lastexample{\arabic{chapter}.\arabic{example}}

\def\lastexercise{\arabic{chapter}.\arabic{exercise}}

\def\resetmycounters{
  \setcounter{bibliosection}{0}
  \setcounter{example}{0}
  \setcounter{exercise}{0}}

\def\myfootnote#1{\footnote{#1}}

\def\lambdatarget{7.3}

\def\polefigure{3.2}

\def\StateAggregation{8.4}

\def\banditchap{2}

\def\probchap{3}

\def\DPchap{4}

\def\MCchap{5}

\def\TDchap{6}

\def\ETchap{7}

\def\FAchap{8}

\def\modelchap{9}

\def\CSchap{11}

\def\Sumchap{10}

\def\finalchap{10}

\def\eqincN{\banditchap.4}

\def\eqAverage{\banditchap.1}

\def\eqSAconditions{\banditchap.7}

\def\secinc{\banditchap.5}

\def\secnonstationary{\banditchap.6}

\def\softmaxsection{\banditchap.3}

\def\RCsection{2.8}

\def\predictionbackups{\probchap.4}

\def\DPbackupVpi{\probchap.4a}

\def\undiscountedsection{\probchap.?}

\def\maxbackups{\probchap.7}

\def\BellmanVpi{\probchap.10}

\def\PImprov{\DPchap.2}

\def\GPIsec{\DPchap.6}

\def\EstimateOtherPolicySec{\MCchap.5}

\def\TDprediction{\TDchap.2}

\def\simpleTDrule{\TDchap.2}

\def\randomwalkexample{\TDchap.2}

\def\randomwalkfigure{\TDchap.4}

\def\sarsasection{\TDchap.3}

\def\ACsection{\TDchap.6}

\def\Rlearningsection{\TDchap.7}

\def\afterstatesection{\TDchap.8}

\def\ACrule{\TDchap.8}

\def\ACruleplus{\TDchap.9}

\def\TileCodingSection{\FAchap.3.2}

\def\sarsalalg{\FAchap.8}

\def\lambdacomparison{\FAchap.10}

\def\heuristicsearchsection{\modelchap.7}

\def\planspacesection{\modelchap.10}

\def\uniformvsonpolicysection{\modelchap.9}

\def\ZDcasestudy{\CSchap.6}

\def\samuelsection{\CSchap.2}

\def\TDGammonSection{\CSchap.1}

\def\g{\mbox{$\gamma$}}

\def\a{\mbox{$\alpha$}}

\def\l{\mbox{$\lambda$}}

\def\e{\mbox{$\epsilon$}}

\def\ee{\mbox{$\varepsilon$}}

\def\n{\mbox{$n$}}

\def\r{\mbox{$R$}}

\def\rl{R^{\lambda}}

\def\sp{{s^\prime}}

\def\ap{{a^\prime}}

\def\TDl{TD($\lambda$)}

\def\itTDl{{\it TD\/}\mbox{\rm ($\lambda$)}}

\def\Ql{Q($\lambda$)}

\def\itQl{{\it Q\/}\mbox{\rm ($\lambda$)}}

\def\sarsal{Sarsa($\lambda$)}

\def\itsarsal{{\it Sarsa\/}\mbox{\rm ($\lambda$)}}

\def\={\!=\!}

\def\X{{\cal X}}

\def\A{{\cal A}}

\def\S{{\cal S}}

\def\P{{\cal P}}

\def\R{{\cal R}}

\def\Pssa{\P_{s\sp}^a}

\def\Rssa{\R_{s\sp}^a}

\def\endofexample{$\diamondsuit$}

\def\starredsection#1{\section{#1\ (*)}}

\def\&{and}

\def\figbody#1#2#3#4#5{%








\centerline{\psfig{figure=#1.ps,rheight=#3,#5}}}

\def\comment#1{}

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
             \vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}

\def\myboxit#1{\vbox{\hrule\hbox{\vrule\kern6pt
             \vbox{\kern-17pt#1\kern-12pt}\kern8pt\vrule}\hrule}}

\def\n{$n$}

\def\p#1{{\pi_#1}}

\def\pip{{\pi^\prime}}

\def\pipp{{\pi^{\prime\prime}}}

\def\mapright#1{\,\mathop{\longrightarrow}\limits^{#1}\,}

\def\raPE{\mapright{\mbox{\tiny E}}}

\def\raPI{\mapright{\mbox{\tiny I}}}

\def\tV{\widetilde{V}^*}

\def\tQ{\widetilde{Q}^*}

\def\Pp{p^{\prime}}

\def\i{$i$}

\def\k{\mbox{$k$}}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi $}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1003: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi $}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1005: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon $}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1007: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\setcounter{bibliosection}{0}
\setcounter{example}{0}
\setcounter{exercise}{0}
\setcounter{chapter}{4}
\stepcounter{chapter}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1009: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1011: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1013: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1015: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1019: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1021: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1029: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi \gets \mbox{policy to be evaluated}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1039: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V \gets \mbox{an arbitrary state-value function}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1041: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s) \gets \mbox{an empty list, for all $s\in\S$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1043: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1045: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mbox{$R$}
  \gets \mbox{return following the first occurrence of $s$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1049: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1051: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1053: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V(s) \gets \mbox{average}(Returns(s))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1055: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1057: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1057: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\vbox{\hrule\hbox{\vrule\kern6pt
\vbox{\kern-17pt\box4\kern-12pt}\kern8pt\vrule}\hrule}}
  
  \label{fig:MCfirst}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1059: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1063: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$1/\sqrt{n}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1065: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1069: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{example}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1095
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1096
\arabic{example}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mbox{$\gamma$}
 =1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1077: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Pssa$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1079: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Rssa$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1081: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\diamondsuit$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1083: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=bj-eval-v.ps,rheight=3.0in,height=2.832in}}

   
   \label{fig:bj-eval-v}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1085: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1087: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1087: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=MCbackupV.ps,rheight=2.8in,height=2.832in}}

   
   \label{fig:MCbackupV}
\end{figure}
}

\addtocounter{example}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1097
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1098
\arabic{example}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\diamondsuit$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1089: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1099
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1100
\arabic{exercise}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^*$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1101: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1103: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1109: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1111: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1113: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1119
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1120
\arabic{exercise}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1117: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \psfig{figure=little-GPI.ps,rheight=1.1in,width=1.5in}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1123: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}%
\p0 \,\mathop{\longrightarrow}\limits^{\mbox{\tiny E}}\,  Q^{\p0} \,\mathop{\longrightarrow}\limits^{\mbox{\tiny I}}\,  \p1 \,\mathop{\longrightarrow}\limits^{\mbox{\tiny E}}\,  Q^{\p1} \,\mathop{\longrightarrow}\limits^{\mbox{\tiny I}}\,  \p2 \,\mathop{\longrightarrow}\limits^{\mbox{\tiny E}}\,  %
    \,\cdots\, \,\mathop{\longrightarrow}\limits^{\mbox{\tiny I}}\,  \pi^* \,\mathop{\longrightarrow}\limits^{\mbox{\tiny E}}\,  Q^*
\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\raPE$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1125: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\raPI$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1127: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^{\pi_k}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1129: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_k$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1131: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1135: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{equation}\label{eq:greedy}
\pi(s) = \arg \max_a Q(s,a).
\end{equation}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_{k+1}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1139: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^{\pi_k}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1141: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_k$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1143: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_{k+1}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1145: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1147: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}Q^{\pi_k}\!\left(s,\pi_{k+1}(s)\right) &=& Q^{\pi_k}(s, \arg\max_a
Q^{\pi_k}(s,a))\\ 
            &=& \max_a Q^{\pi_k}(s,a)\\ 
            &\ge& Q^{\pi_k}\!\left(s,\pi_k(s)\right)\\ 
            &\ge& V^{\pi_k}(s).
\end{eqnarray*}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_{k+1}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1149: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_k$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1151: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi_k$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1153: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^{\pi_k}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1155: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^{\pi_k}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1157: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1159: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a\in{\cal A}
 (s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1161: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets \mbox{arbitrary}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1163: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s) \gets \mbox{arbitrary}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1165: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s,a) \gets \mbox{empty list}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1167: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1169: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mbox{$R$}
  \gets \mbox{return following the first occurrence of $s,a$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1173: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1175: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1177: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets \mbox{average}(Returns(s,a))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1179: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s) \gets \arg\max_a Q(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1183: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\vbox{\hrule\hbox{\vrule\kern6pt
\vbox{\kern-17pt\box4\kern-12pt}\kern8pt\vrule}\hrule}}
  
  \label{fig:MCexploring}
\end{figure}
}

\addtocounter{example}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1191
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1192
\arabic{example}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\diamondsuit$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1185: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=bj-V*.ps,rheight=3.0in,height=2.832in}}

   
   \label{fig:bj-V*}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s,a)>0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1193: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1195: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a\in{\cal A}
 (s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1197: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1199: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\e$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1201: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\mbox{$\epsilon$} \over |{\cal A}
 (s)|}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1203: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$1-\e+{\mbox{$\epsilon$} \over
|{\cal A}
 (s)|}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1205: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1207: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1209: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s,a)\ge{\mbox{$\epsilon$} \over |{\cal A}
 (s)|}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1211: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mbox{$\epsilon$} >0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1213: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1215: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1217: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1219: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1221: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1223: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1225: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1227: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1229: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1231: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1233: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1235: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1237: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1239: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1241: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1243: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:ePIcondition}
Q^\pi(s,{\pi^\prime} (s)) 
&=& \sum_a {\pi^\prime} (s,a)Q^\pi(s,a)\nonumber\\ 
&=& {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a Q^\pi(s,a) ~+~ (1-\mbox{$\epsilon$} )\max_a Q^\pi(s,a) \\ 
&\ge& {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a Q^\pi(s,a) ~+~
(1-\mbox{$\epsilon$} )\sum_a {\pi(s,a)-{\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\over1-\mbox{$\epsilon$} }Q^\pi(s,a)
\nonumber\\ 
\noalign{\noindent
(the sum is a weighted average with non-negative weights
summing to one, and as such it must be less than or equal to the largest
number averaged)}
&=& {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a Q^\pi(s,a) ~-~
{\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a Q^\pi(s,a) ~+~ \sum_a
\pi(s,a)Q^\pi(s,a)
\nonumber\\ 
&=& V^\pi(s). \nonumber
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\pi^\prime} \ge\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1261: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^{\pi^\prime} (s)\ge
V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1263: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\forall s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1265: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1267: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1269: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1271: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1273: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1275: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$1-\e$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1281: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\e$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1283: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1285: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1287: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tQ$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1289: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1291: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1293: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi = \tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1295: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1297: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}\widetilde{V}^* (s) 
   &=& (1-\mbox{$\epsilon$} )\max_a \widetilde{Q}^* (s,a) + {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a \widetilde{Q}^* (s,a)\\ 
   &=&(1-\mbox{$\epsilon$} )\max_a\sum_{{s^\prime}
 }\P_{s{s^\prime}
 }^a\left[\R_{s{s^\prime}
 }^a+\mbox{$\gamma$}
 \widetilde{V}^*({s^\prime}
 )\right]\\ 
   &&   ~~~~+~~
{\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a\sum_{{s^\prime}
 }\P_{s{s^\prime}
 }^a
\left[\R_{s{s^\prime}
 }^a+\gamma\widetilde{V}^* ({s^\prime}
 )\right].
\end{eqnarray*}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1309: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1311: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}V^\pi(s) &=& (1-\mbox{$\epsilon$} )\max_a Q^\pi(s,a) + {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a Q^\pi(s,a)\\ 
   &=&(1-\mbox{$\epsilon$} )\max_a\sum_{{s^\prime}
 }\P_{s{s^\prime}
 }^a\left[\R_{s{s^\prime}
 }^a+\gamma
V^\pi({s^\prime}
 )\right]\\ 
 && ~~~~+~~ {\mbox{$\epsilon$} \over|{\cal A}
 (s)|}\sum_a\sum_{{s^\prime}
 }\P_{s{s^\prime}
 }^a\left[\R_{s{s^\prime}
 }^a+\gamma
V^\pi({s^\prime}
 )\right].
\end{eqnarray*}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1321: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1323: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1325: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi=\tV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1327: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1329: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1331: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1333: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1335: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1337: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a\in{\cal A}
 (s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1339: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets \mbox{arbitrary}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1341: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s,a) \gets \mbox{empty list}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1343: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi \gets \mbox{an arbitrary \mbox{$\epsilon$} -soft policy}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1345: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1347: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mbox{$R$}
  \gets \mbox{return following the first occurrence of $s,a$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1351: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1353: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Returns(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1355: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets \mbox{average}(Returns(s,a))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1357: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a^* \gets \arg\max_a Q(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1361: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a\in{\cal A}
 (s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1363: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s,a) \gets \left\{\begin{array}{ll}
                   1-\mbox{$\epsilon$}  +{\mbox{$\epsilon$} /|{\cal A}
 (s)|}  & \mbox{if $a=a^*$}\\ 
                   {\mbox{$\epsilon$} /|{\cal A}
 (s)|}            & \mbox{if $a\not=a^*$}
\end{array}\right.$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1365: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1367: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1367: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\vbox{\hrule\hbox{\vrule\kern6pt
\vbox{\kern-17pt\box4\kern-12pt}\kern8pt\vrule}\hrule}}
  
  \label{fig:MConpolicy}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1373: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1375: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1377: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\pi^\prime} \not=\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1379: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1381: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1383: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1385: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1387: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s,a)>0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1389: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\pi^\prime} (s,a)>0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1391: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1393: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$p_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1399: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Pp_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1401: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1403: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1405: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\r_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1409: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^\pi(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1413: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1415: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1417: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$p_i(s)/\Pp_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1419: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$n_s$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1421: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{equation}\label{eq:weightedMC}
V(s) = {\sum_{i=1}^{n_s} {p_i(s)\over\Pp_i(s)} \r_i(s) \over
\sum_{i=1}^{n_s} {p_i(s)\over\Pp_i(s)}}.
\end{equation}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$p_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1425: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Pp_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1427: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$p_i(s)/\Pp_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1429: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$T_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1431: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}p_i(s_t) = \prod_{k=t}^{T_i(s)-1} \pi(s_k,a_k) \P_{s_k s_{k+1}}^{a_k}\end{displaymath}
}

{\newpage
\clearpage
\samepage \begin{displaymath}{p_i(s_t)\over \Pp_i(s_t)} = {\prod_{k=t}^{T_i(s)-1} \pi(s_k,a_k) \P_{s_k
s_{k+1}}^{a_k}
                 \over \prod_{k=t}^{T_i(s)-1} {\pi^\prime} (s_k,a_k) \P_{s_k
s_{k+1}}^{a_k}}
  = \prod_{k=t}^{T_i(s)-1} {\pi(s_k,a_k)\over {\pi^\prime} (s_k,a_k)}.
\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$p_i(s)/\Pp_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1435: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1439
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1440
\arabic{exercise}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1437: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1441: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a\in{\cal A}
 (s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1443: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets \mbox{arbitrary}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1445: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N(s,a) \gets 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1447: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D(s,a) \gets 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1449: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1451: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi \gets \mbox{an arbitrary deterministic policy}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1453: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi^\prime$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1455: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s_0,a_0,r_1,s_1,a_1,r_2,\ldots,s_{T-1},a_{T-1},r_T,s_T$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1457: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tau \gets \mbox{latest time at which $a_\tau \not= \pi(s_\tau)$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1459: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\tau$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1463: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$t \gets \mbox{the time of first occurrence (after $\tau$) of $s,a$}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1465: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$w \gets \prod_{k=t+1}^{T-1}  {1\over {\pi^\prime} (s_k,a_k)}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1467: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N(s,a) \gets N(s,a) + w\r_t$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1469: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D(s,a) \gets D(s,a) + w$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1471: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q(s,a) \gets {N(s,a)\over D(s,a)}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1473: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s\in\S$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1475: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi(s) \gets \arg\max_a Q(s,a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1477: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\vbox{\hrule\hbox{\vrule\kern6pt
\vbox{\kern-17pt\box4\kern-12pt}\kern8pt\vrule}\hrule}}
  
  \label{fig:MCoffpolicy}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^*$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1479: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pip$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1481: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1483: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$Q^\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1487: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1489: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1491: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1505
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1506
\arabic{exercise}
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=racetrack.ps,rheight=2.415in,width=4.472in}}

   
   \label{fig:racetrack}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\r_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1511: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$w_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1513: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{equation}\label{eq:MCweighted}
 V_n = {\sum_{k=1}^n w_k \r_k \over \sum_{k=1}^n w_k }
\end{equation}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$w_n(s)=p_n(s)/\Pp_n(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1515: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1517: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$W_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1519: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1523: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{equation}\label{eq:incweighted}
V_{n+1} = V_n + {w_{n+1}\over W_{n+1}} \biggl[\r_{n+1} -
V_n\biggr]
\end{equation}
}

{\newpage
\clearpage
\samepage \begin{displaymath}W_{n+1} = W_n + w_{n+1}  \end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$W_0 = 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1525: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1527
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1528
\arabic{exercise}
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1529
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1530
\arabic{exercise}
}

\addtocounter{exercise}{1}
{\newpage
\clearpage
\samepage % latex2html id marker 1531
\arabic{chapter}
}

{\newpage
\clearpage
\samepage % latex2html id marker 1532
\arabic{exercise}
}

\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}

\end{document}
