
%%%%%%%%%%%%%%%%%%%% author.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% sample root file for your "contribution" to a contributed volume
%
% Use this file as a template for your own input.
%
%%%%%%%%%%%%%%%% Springer %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% RECOMMENDED %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[graybox]{svmult}

\usepackage{array}
\usepackage{latexsym}
\usepackage{theorem}
\usepackage{supertabular}
\usepackage{epsfig}
\usepackage{subfigure}
%\usepackage{bibentry}
%\usepackage{natbib}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd} % commutative diagrams
\usepackage{amsfonts}
\usepackage[boxed]{algorithm}
\usepackage[noend]{algorithmic}
%\usepackage[dvips]{color}
%\usepackage{stmaryrd}
\usepackage{graphicx,subfigure,url}
\usepackage[vflt]{floatflt}
\usepackage{wrapfig}
%\usepackage{lettrine}
\usepackage[latin1]{inputenc}

\newcommand{\ab}[1]{{\mathbbm{#1}}}
\newcommand{\abb}[1]{{\boldsymbol{\boldsymbol{\mathbbm{#1}}}}}
\newcommand{\me}[1]{\mbox{\it #1}}
\newcommand{\lb}{\llbracket}
\newcommand{\rb}{\rrbracket}
\newcommand{\sub}{\preceq_{\theta}}

% onderstaande keuze is voor de bold symbols in math mode

% bold font when it comes to Prolog stuff
\newcommand{\m}[1]{\mathtt{#1}}
% bold font for math stuff, such as variables
\newcommand{\p}[1]{\mathbf{#1}}

\newcommand{\tl}[1]{\tilde{#1}}

\floatname{algorithm}{Algorithm}

\DeclareMathOperator{\lh}{LH}
\DeclareMathOperator{\mgu}{mgu}
\DeclareMathOperator{\unifies}{unifies}
\DeclareMathOperator{\hb}{HB}
\DeclareMathOperator{\hu}{HU}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\out}{out}
\DeclareMathOperator{\act}{active}
\DeclareMathOperator{\least}{least}
\DeclareMathOperator{\dom}{D}
\DeclareMathOperator{\domain}{D}
\DeclareMathOperator{\vars}{vars}
\DeclareMathOperator{\head}{head}
\DeclareMathOperator{\body}{body}
\DeclareMathOperator{\leas}{least}
\DeclareMathOperator{\wpre}{wp}
\DeclareMathOperator{\pre}{pre}
\DeclareMathOperator{\post}{post}
\DeclareMathOperator{\cons}{cons}
\DeclareMathOperator{\true}{true}
\DeclareMathOperator{\false}{false}
\DeclareMathOperator{\cond}{cond}
\DeclareMathOperator{\glb}{glb}
\DeclareMathOperator{\var}{var}
\DeclareMathOperator{\domn}{dom}
\DeclareMathOperator{\niet}{not}
\DeclareMathOperator{\ran}{ran}
\DeclareMathOperator{\tree}{Tree}
\DeclareMathOperator{\ptree}{PTree}
\DeclareMathOperator{\fvtree}{FVTree}
\DeclareMathOperator{\move}{move}
\DeclareMathOperator{\moveToTable}{moveToTable}
\DeclareMathOperator{\clear}{clear}
\DeclareMathOperator{\on}{on}
\DeclareMathOperator{\sdo}{do}
\DeclareMathOperator{\Poss}{Poss}
\DeclareMathOperator{\onTable}{onTable}
\DeclareMathOperator{\Regr}{Regr}
\DeclareMathOperator{\hsmq}{HSMQ}
\DeclareMathOperator{\taskhierarchy}{TaskHierarchy}
\DeclareMathOperator{\kb}{KB}
\DeclareMathOperator{\covers}{cv}
\DeclareMathOperator{\lgg}{lgg}
%\DeclareMathOperator{\operators}{Ops}
\DeclareMathOperator{\causes}{causes}
%\DeclareMathOperator{\case}{case}
\DeclareMathOperator{\pcase}{pCase}

\theoremstyle{break}
\newtheorem{thm}{Theorem}[section]
\newtheorem{exam}{Example}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{fact}{Fact}[section]
\newtheorem{mental}{MENTAL NOTE}

%%%%% Typesetting Names
\newcommand{\acro}[1]{{\textsc{#1}}}
\newcommand{\tsss}[1]{{\textsc{#1}}}

%%%%% Typesetting Math BB Mode
\newcommand{\mc}[1]{\mathcal{#1}}

%%%%% Typesetting Glossary Items
\newcommand{\glsitem}[2]{\textbf{\tsss{#1}} & \emph{#2}\\}
\newcommand{\glsitemm}[3]{\textbf{\tsss{#1}} & \emph{#2}\\ & \emph{#3}\\}

%\newcommand{\bibentryx}[1]{\parbox[c]{0.9\linewidth}{$\blacktriangleright$\ \ \bibentry{#1}}\\}
\newcommand{\bibentryx}[1]{\noindent $\blacktriangleright$\ \ \bibentry{#1}\\}
%\newcommand{\bibentryx}[1]{\noindent $\star\star\star$\ \ \bibentry{#1}\\}

%\citep{#1}

%%%%% Names
\newcommand{\bwp}{\textsc{Blocks World }}
\newcommand{\bwps}{\textsc{Blocks Worlds }}
\newcommand{\rmdp}{{\textsc{RMDP}}}
\newcommand{\mdp}{{\textsc{MDP}}}
\newcommand{\mdps}{{\textsc{MDPs}}}
\newcommand{\piag}{{\tsss{PIAGeT}}}
\newcommand{\piaga}{{\tsss{PIAGeT}-$0$ }}
\newcommand{\piagb}{{\tsss{PIAGeT}-$1$ }}
\newcommand{\piagc}{{\tsss{PIAGeT}-$2$ }}
\newcommand{\piagd}{{\tsss{PIAGeT}-$3$ }}


% choose options for [] as required from the list
% in the Reference Guide

\usepackage{mathptmx} % selects Times Roman as basic font
\usepackage{helvet} % selects Helvetica as sans-serif font
\usepackage{courier} % selects Courier as typewriter font
\usepackage{type1cm} % activate if the above 3 fonts are
                            % not available on your system
%
\usepackage{makeidx} % allows index generation
\usepackage{graphicx} % standard LaTeX graphics tool
                             % when including figure files
\usepackage{multicol} % used for the two-column index
\usepackage[bottom]{footmisc}% places footnotes at page bottom

% see the list of further useful packages
% in the Reference Guide

\makeindex % used for the subject index
                       % please use the style svind.ist with
                       % your makeindex program

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

\begin{document}

\title*{Reinforcement Learning and Markov Decision Processes}
% Use \titlerunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\author{Martijn van Otterlo and Marco Wiering}
% Use \authorrunning{Short Title} for an abbreviated version of
% your contribution title if the original one is too long
\institute{Martijn van Otterlo \at Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3001 Heverlee, Belgium, \email{martijn.vanotterlo@cs.kuleuven.be}
\and Marco Wiering \at Department of Artificial Intelligence, University of Groningen, The Netherlands \email{m.a.wiering@rug.nl}}
%
% Use the package "url.sty" to avoid
% problems with special characters
% used in your e-mail or web address
%
\maketitle

\abstract*{Situated in between supervised learning and unsupervised learning, the paradigm of reinforcement learning deals with learning in sequential decision making problems in which there is limited feedback. This text introduces the intuitions and concepts behind Markov decision processes and two classes of algorithms for computing optimal behaviors: reinforcement learning and dynamic programming. First the formal framework of Markov decision process is defined, accompanied by the definition of value functions and policies. The main part of this text deals with introducing foundational classes of algorithms for learning optimal behaviors, based on various definitions of optimality with respect to the goal of learning sequential decisions. Additionally, it surveys efficient extensions of the foundational algorithms, differing mainly in the way feedback given by the environment is used to speed up learning, and in the way they concentrate on relevant parts of the problem. For both model-based and model-free settings these efficient extensions have shown useful in scaling up to larger problems.}

\abstract{Situated in between supervised learning and unsupervised learning, the paradigm of reinforcement learning deals with learning in sequential decision making problems in which there is limited feedback. This text introduces the intuitions and concepts behind Markov decision processes and two classes of algorithms for computing optimal behaviors: reinforcement learning and dynamic programming. First the formal framework of Markov decision process is defined, accompanied by the definition of value functions and policies. The main part of this text deals with introducing foundational classes of algorithms for learning optimal behaviors, based on various definitions of optimality with respect to the goal of learning sequential decisions. Additionally, it surveys efficient extensions of the foundational algorithms, differing mainly in the way feedback given by the environment is used to speed up learning, and in the way they concentrate on relevant parts of the problem. For both model-based and model-free settings these efficient extensions have shown useful in scaling up to larger problems.}

\begin{svgraybox}
This text was assembled from the initial chapters of \emph{The Logic of Adaptive Behavior} by Martijn van Otterlo (2008), later published at IOS Press (2009). The purpose of this chapter is to show i) which kinds of algorithms, concepts, techniques etc. one can assume when writing chapters on specific topics (i.e. concepts such as \tsss{MDP}s and Q-learning can be assumed, and do not have to be explained again), and ii) the type of notation that is expected (e.g. the \tsss{AI}-style of \ts{RL}, as opposed to the Bertsekas and Tsitsiklis (1996) \ts{OR}-style. The specifics and length of this chapter are -- of course -- subject to change.
\end{svgraybox}


\section{Introduction}
\begin{sloppypar}
Markov Decision Processes~(\tsss{MDP})~\cite{puterman:mdp:94} are an intuitive and fundamental formalism for \emph{decision-theoretic planning} (\tsss{DTP}) \cite{boutilier:dtp:99,boutilier:krfsdp:99}, reinforcement learning (\tsss{RL}) \cite{bertsekas:ndp:96,sutton:rlai:98,kaelbling:rlas:96} and other learning problems in stochastic domains. In this model, an environment is modelled as a set of states and actions can be performed to control the system's state. The goal is to control the system in such a way that some performance criterium is maximized. Many problems such as (stochastic) planning problems, learning robot control and game playing problems have successfully been modelled in terms of an \tsss{MDP}. In fact \tsss{MDP}s have become the \emph{de facto} standard formalism for learning sequential decision making.
\end{sloppypar}

\tsss{DTP} \cite{boutilier:dtp:99}, e.g. planning using decision-theoretic notions to represent uncertainty and plan quality, is an important extension of the \tsss{AI} \emph{planning paradigm}, adding the ability to deal with \emph{uncertainty} in action effects and the ability to deal with less-defined \emph{goals}. Furthermore it adds a significant dimension in that it considers situations in which factors such as resource consumption and uncertainty demand solutions of \emph{varying quality}, for example in \emph{real-time} decision situations. There are many connections between \tsss{AI} planning, research done in the field of \emph{operations research} \cite{winston:oraaa:91} and \emph{control theory} \cite{bertsekas:dpaoc:95}, as most work in these fields on \emph{sequential decision making} can be viewed as instances of \tsss{MDP}s. The notion of a \emph{plan} in \tsss{AI} planning, i.e. a series of actions from a start state to a goal state, is extended to the notion of a \emph{policy}, which is mapping from \emph{all} states to an (optimal) action, based on decision-theoretic measures of \emph{optimality} with respect to some goal to be optimized.

As an example, consider a typical planning domain, involving boxes to be moved around and where the goal is to move some particular boxes to a designated area. This type of problems can be solved using \tsss{AI} planning techniques. Consider now a slightly more realistic extension in which some of the actions can fail, or have uncertain side-effects that can depend on factors beyond the operator's control, and where the goal is specified by giving credit for how many boxes are put on the right place. In this type of environment, the notion of a plan is less suitable, because a sequence of actions can have many different outcomes, depending on the effects of the operators used in the plan. Instead, the methods in this chapter are concerned about \emph{policies} that map states onto actions in such a way that the \emph{expected} outcome of the operators will have the intended effects. The expectation over actions is based on a decision-theoretic expectation with respect to their probabilistic outcomes and credits associated with the problem goals. The \tsss{MDP} framework allows for online solutions that \emph{learn} optimal policies gradually through \emph{simulated trials}, and additionally, it allows for \emph{approximated} solutions with respect to resources such as computation time. Finally, the model allows for numeric, decision-theoretic measurement of the \emph{quality} of policies and learning \emph{performance}. For example, policies can be ordered by how much credit they receive, or by how much computation is needed for a particular performance.

This chapter will cover the broad spectrum of methods that have been developed in the literature to compute good or optimal policies for problems modelled as an \tsss{MDP}. The term \tsss{RL} is associated with the more difficult setting in which no (prior) knowledge about the \tsss{MDP} is presented. The task then of the algorithm is to \emph{interact}, or \emph{experiment} with the environment (i.e. the \tsss{MDP}), in order to gain knowledge about how to optimize its behavior, being guided by the evaluative feedback (rewards). The model-based setting, in which the full transition dynamics and reward distributions are known, is usually characterized by the use of \emph{dynamic programming} (\tsss{DP}) techniques. However, we will see that the underlying basis is very similar, and that mixed forms occur.


%**********************************************************************************************
%* The Conceptual idea of sequential decision making
%* Put planning and stuff here!
%*
%*
%*
%**********************************************************************************************

\section{Learning Sequential Decision Making}
\label{sec:seqdecmaking}

\tsss{RL} is a general class of algorithms in the field of machine learning that aims at allowing an \emph{agent} to learn how to behave in an environment, where the only feedback consists of a \emph{scalar} reward signal. \tsss{RL} should not be seen as characterized by a particular class of learning methods, but rather as a learning \emph{problem} or a \emph{paradigm}. The \emph{goal} of the agent is to perform \emph{actions} that maximize the reward signal in the long run.

The distinction between the \emph{agent} and the \emph{environment} might not always be the most intuitive one. We will draw a boundary based on \emph{control} \cite{sutton:rlai:98}. Everything the agent cannot control is considered part of the environment. For example, although the motors of a robot agent might be considered part of the agent, the exact functioning of them in the environment is beyond the agent's control. It can give commands to gear up or down, but their physical realization can be influenced by many things.

\begin{figure}[t]
\begin{center}
\begin{tabular}{|l|l|}
  \hline
  \textbf{environment} & You are in state $65$. You have $4$ possible actions. \\
  \textbf{agent} & I'll take action $2$. \\
  \textbf{environment} & You have received a reward of $7$ units. You are now in state $15$. \\
                       & You have $2$ possible actions. \\
  \textbf{agent} & I'll take action $1$. \\
  \textbf{environment} & You have received a reward of $-4$ units. You are now in state $65$. \\
                       & You have $4$ possible actions. \\
  \textbf{agent} & I'll take action $2$. \\
  \textbf{environment} & You have received a reward of $5$ units. You are now in state $44$. \\
                       & You have $5$ possible actions. \\
  \ldots & \ldots \\
  \hline
\end{tabular}
\end{center}
\caption{\label{fig:exampleinteraction} Example of interaction between an agent and its environment, from a \tsss{RL} perspective.}
\end{figure}

An example of interaction with the environment is given in Figure~\ref{fig:exampleinteraction}. It shows how the interaction between an \emph{agent} and the \emph{environment} can take place. The agent can choose an action in each state, and the \emph{perceptions} the agent gets from the environment are the environment's state after each action plus the scalar reward signal at each step. Here a discrete model is used in which there are distinct numbers for each state and action. The way the interaction is depicted is highly general in the sense that one just talks about states and actions as discrete \emph{symbols}. In the rest of this book we will be more concerned about interactions in which states and actions have more \emph{structure}, such that a state can be something like \emph{there are two blue boxes and one white one and you are standing next to a blue box}. However, this figure clearly shows the \emph{mechanism} of sequential decision making.

There are several important aspects in learning sequential decision making which we will describe in this section, after which we will describe formalizations in the next sections.

\paragraph{Approaching Sequential Decision Making.} There are several classes of algorithms that deal with the problem of sequential decision making. In this book we deal specifically with the topic of \emph{learning}, but some other options exist.

The first solution is the \emph{programming} solution. An intelligent system for sequential decision making can -- in principle -- be \emph{programmed} to handle all situations. For each possible state an appropriate or optimal action can be specified \emph{a priori}. However, this puts a heavy burden on the designer or programmer of the system. All situations should be foreseen in the design phase and programmed into the agent. This is a tedious and almost impossible task for most interesting problems, and it only works for problems which can be modelled completely. In most realistic problems this is not possible due to the sheer \emph{size} of the problem, or the intrinsic \emph{uncertainty} in the system. A simple example is \emph{robot control} in which factors such as lighting or temperature can have a large, and unforeseen, influence on the behavior of camera and motor systems. Furthermore, in situations where the problem changes, for example due to new elements in the description of the problem or changing dynamic of the system, a programmed solution will no longer work. Programmed solutions are \emph{brittle} in that they will only work for completely known, static problems with fixed probability distributions.

A second solution uses \emph{search} and \emph{planning} for sequential decision making. The successful chess program \emph{Deep Blue} \cite{schaeffer:kvdb:97} was able to defeat the human world champion Gary Kasparov by smart, brute force search algorithms that used a model of the dynamics of chess, tuned to Kasparov's style of playing. When the dynamics of the system are known, one can \emph{search} or \emph{plan} from the current state to a desirable goal state. However, when there is uncertainty about the action outcomes standard search and planning algorithms do not apply. \emph{Admissible heuristics} can solve some problems concerning the reward-based nature of sequential decision making, but the probabilistic effects of actions pose a difficult problem. Probabilistic planning algorithms exist, e.g. \cite{kushmerick:aafpp:95}, but their performance is not as good as their deterministic counterparts. An additional problem is that planning and search focus on specific start and goal states. In contrast, we are looking for \emph{policies} which are defined for all states, and are defined with respect to \emph{rewards}.

The third solution is \emph{learning}, and this will be the main topic of this book. Learning has several advantages in sequential decision making. First, it relieves the designer of the system from the difficult task of deciding upon everything in the design phase. Second, it can cope with uncertainty, goals specified in terms of reward measures, and with changing situations. Third, it is aimed at solving the problem for every state, as opposed to a mere plan from one state to another. Additionally, although a model of the environment can be used or learned, it is not necessary in order to compute optimal policies, such as is exemplified by \tsss{RL} methods. Everything can be learned from interaction with the environment.

\paragraph{Online versus Off-line Learning.} One important aspect in the learning task we consider in this book is the distinction between \emph{online} and \emph{off-line} learning. The difference between these two types is influenced by factors such as whether one wants to control a \emph{real-world} entity -- such as a robot player robot soccer or a machine in a factory -- or whether all necessary information is available. Online learning performs learning directly on the problem instance. Off-line learning uses a \emph{simulator} of the environment as a cheap way to get many training examples for \emph{safe} and \emph{fast} learning.

Learning the controller directly on the real task is often not possible. For example, the learning algorithms in this chapter sometimes need millions of training instances which can be too time-consuming to collect. Instead, a simulator is much faster, and in addition it can be used to provide arbitrary training situations, including situations that rarely happen in the real system. Furthermore, it provides a "safe" training situation in which the agent can explore and make mistakes. Obtaining negative feedback in the real task in order to learn to avoid these situations, might entail destroying the machine that is controlled, which is unacceptable. Often one uses a simulation to obtain a reasonable policy for a given problem, after which some parts of the behavior are \emph{fine-tuned} on the real task. For example, a simulation might provide the means for learning a reasonable robot controller, but some \emph{physical} factors concerning variance in motor and perception systems of the robot might make additional fine-tuning necessary. A simulation is just a \emph{model} of the real problem, such that small differences between the two are natural, and learning might make up for that difference. Many problems in the literature however, \emph{are} simulations of games and optimization problems, such that the distinction disappears.

\paragraph{Credit Assignment.} An important aspect of sequential decision making is the fact that deciding whether an action is "good" or "bad" cannot be decided upon right away. The appropriateness of actions is completely determined by the \emph{goal} the agent is trying to pursue. The real problem is that the effect of actions with respect to the goal can be much \emph{delayed}. For example, the opening moves in chess have a large influence on winning the game. However, between the first opening moves and receiving a reward for winning the game, a couple of tens of moves might have been played. Deciding how to give \emph{credit} to the first moves -- which did not get the immediate reward for winning -- is a difficult problem called the \emph{temporal credit assignment} problem. Each move in a winning chess game contributes more or less to the success of the last move, although some moves along this path can be less optimal or even bad. A related problem is the \emph{structural credit assignment} problem, in which the problem is to distribute feedback over the \emph{structure} representing the agent's policy. For example, the policy can be represented by a structure containing parameters (e.g. a neural network). Deciding which parameters have to be updated forms the structural credit assignment problem.

\paragraph{The Exploration-Exploitation Trade-off.} If we know a complete model of dynamics of the problem, there exist methods (e.g. \tsss{DP}) that can compute optimal policies from this model. However, in the more general case where we do not have access to this knowledge (e.g. \tsss{RL}), it becomes necessary to \emph{interact} with the environment to learn by \emph{trial-and-error} a correct policy. The agent has to \emph{explore} the environment by performing actions and perceiving their consequences (i.e. the effects on the environments and the obtained rewards). The only feedback the agent gets are rewards, but it does not get information about what is the right action. At some point in time, it will have a policy with a particular performance. In order to see whether there are possible improvements to this policy, it sometimes has to \emph{try out} various actions to see their results. This might result in worse performance because the actions might also be less good than the current policy. However, without trying them, it might never find possible improvements. In addition, if the world is not stationary, the agent has to explore to keep its policy up-to-date. So, in order to \emph{learn} it has to \emph{explore}, but in order to \emph{perform well} it should \emph{exploit} what it already knows. Balancing these two things is called the \emph{exploration-exploitation problem}.

\paragraph{Feedback, Goals and Performance.} Compared to supervised learning, the amount of feedback the learning system gets in \tsss{RL}, is much less. In supervised learning, for every learning sample the correct output is given in a training set. The performance of the learning system can be measured relative to the number of correct answers, resulting in a \emph{predictive accuracy}. The difficulty lies in learning this mapping, and whether this mapping \emph{generalizes} to new, unclassified, examples. In unsupervised learning, the difficulty lies in constructing a useful partitioning of the data such that classes naturally arise. In reinforcement there is only some information available about performance, in the form of one \emph{scalar} signal. This feedback system is \emph{evaluative} rather than being \emph{instructive}. Using this limited signal for feedback renders a need to put more effort in using it to evaluate and improve behavior during learning.

A second aspect about feedback and performance is related to the stochastic nature of the problem formulation. In supervised and unsupervised learning, the data is usually considered \emph{static}, i.e. a data set is given and performance can be measured with respect to this data. The learning samples for the learner originate from a fixed distribution, i.e. the data set. From a \tsss{RL} perspective, the data can be seen as a \emph{moving target}. The learning process is driven by the current policy, but this policy will change over time. That means that the \emph{distribution} over states and rewards will change because of this. In machine learning the problem of a changing distribution of learning samples is termed \emph{concept drift} \cite{maloof:irlwpimfcc:03} and it demands special features to deal with it. In \tsss{RL} this problem is dealt with by exploration, a constant interaction between evaluation and improvement of policies and additionally the use of \emph{learning rate adaption schemes}.

A third aspect of feedback is the question \emph{"where do the numbers come from?"}. In many sequential decision tasks, suitable reward functions present themselves quite naturally. For games in which there are winning, losing and draw situations, the reward function is easy to specify. In some situations special care has to be taken in giving rewards for states or actions, and also their \emph{relative size} is important. When the agent will encounter a large negative reward before it finally gets a small positive reward, this positive reward might get \emph{overshadowed}. All problems posed will have \emph{some} optimal policy, but it depends on whether the reward function is in accordance with the right goals, whether the policy will tackle the \emph{right} problem. In some problems it can be useful to provide the agent with rewards for reaching intermediate \emph{subgoals}. This can be helpful in problems which require very long action sequences.

\paragraph{Representations.} One of the most important aspects in learning sequential decision making is \emph{representation}. Two central issues are \emph{what} should be represented, and \emph{how} things should be represented. The first issue is dealt with in this chapter. Key components that can or should be represented are models of the dynamics of the environment, reward distributions, value functions and policies. For some algorithms all components are explicitly stored in tables, for example in classic \tsss{DP} algorithms. Actor-critic methods keep separate, explicit representations of both value functions and policies. However, in most \tsss{RL} algorithms just a value function is represented whereas policy decisions are derived from this value function online. Methods that search in policy space do not represent value functions explicitly, but instead an explicitly represented policy is used to compute values when necessary. Overall, the choice for \emph{not} representing certain elements can influence the choice for a type of algorithm, and its efficiency.

The question of \emph{how} various structures can be represented is dealt with extensively in this book, starting from the next chapter. Structures such as policies, transition functions and value functions can be represented in more compact form by using various \emph{structured} knowledge representation formalisms and this enables much more efficient solution mechanisms and scaling up to larger domains.


%**********************************************************************************************
%* Markov Decision Processes
%*
%*
%*
%**********************************************************************************************
\section{A Formal Framework}
\label{sec:mdp}

The elements of the \tsss{RL} problem as described in the introduction to this chapter can be formalized using the \emph{Markov decision process} (\tsss{MDP}) framework. In this section we will formally describe components such as \emph{states} and \emph{actions} and \emph{policies}, as well as the \emph{goals} of learning using different kinds of \emph{optimality criteria}. \tsss{MDP}s are extensively described in \cite{puterman:mdp:94} and \cite{boutilier:dtp:99}. They can be seen as stochastic extensions of finite automata and also as \emph{Markov processes} augmented with actions.

Although general \tsss{MDP}s may have infinite (even uncountable) state and action spaces, we limit the discussion to finite-state and finite-action problems. In the next chapter we will encounter continuous spaces and in later chapters we will encounter situations arising in the first-order logic setting in which infinite spaces can quite naturally occur.

%**********************************************************************************************
%* MDP
%*
%*
%*
%**********************************************************************************************

\subsection{Markov Decision Processes.}
\tsss{MDP}s consist of states, actions, transitions between states and a reward function definition. We consider each of them in turn.

%**********************************************************************************************
%* States
%*
%*
%*
%**********************************************************************************************

\paragraph{States.}

The set of environmental states $S$ is defined as the finite set $\{ s^1, \ldots , s^N \}$ where the \emph{size} of the state space is $N$, i.e. $|S|=N$. A \emph{state} is a unique characterization of all that is important in a state of the problem that is modeled. For example, in chess a complete configuration of board pieces of both black and white, is a state. In the next chapter we will encounter the use of \emph{features} that \emph{describe} the state. In those contexts, it becomes necessary to distinguish between \emph{legal} and \emph{illegal} states, for some combinations of features might not result in an actually existing state in the problem. In this chapter, we will confine ourselves to the discrete state set $S$ in which each state is represented by a \emph{distinct symbol}, and all states $s \in S$ are legal.

%**********************************************************************************************
%* Actions
%*
%*
%*
%**********************************************************************************************

\paragraph{Actions.}

The set of actions $A$ is defined as the finite set $\{ a^1, \ldots , a^K \}$ where the \emph{size} of the action space is $K$, i.e. $|A|=K$. Actions can be used to \emph{control} the system state. The set of actions that can be applied in some particular state $s \in S$, is denoted $A(s)$, where $A(s)\subseteq A$. In some systems, not all actions can be applied in every state, but in general we will assume that $A(s) = A$ for all $s \in S$. In more structured representations (e.g. by means of \emph{features}), the fact that some actions are not applicable in some states, is modeled by a \emph{precondition function} $\pre : S \times A \rightarrow \{\m{true},\m{false}\}$, stating whether action $a \in A$ is applicable in state $s \in S$.

%**********************************************************************************************
%* Transition Function
%*
%*
%*
%**********************************************************************************************

\paragraph{The Transition Function.}

By applying action $a \in A$ in a state $s \in S$, the system makes a \emph{transition} from $s$ to a new state $s^\prime \in S$, based on a probability distribution over the set of possible transitions. The transition function $T$ is defined as $T:S \times A \times S \rightarrow [0,1]$, i.e. the probability of ending up in state $s^\prime$ after doing action $a$ in state $s$ is denoted $T(s,a,s^\prime)$. It is required that for all actions $a$, and all states $s$ and $s^\prime$, $T(s,a,s^\prime) \geq 0$ and $T(s,a,s^\prime) \leq 1$. Furthermore, for all states $s$ and actions $a$, $\sum_{s^\prime \in S} T(s,a,s^\prime) = 1$, i.e. $T$ defines a \emph{proper probability distribution over possible next states}. Instead of a precondition function, it is also possible to set\footnote{Although this is the same, the explicit distinction between an action not begin applicable in a state and a zero probability for transitions with that action, is lost in this way.} $T(s,a,s^\prime)=0$ for all states $s^\prime \in S$ if $a$ is not applicable in $s$. For talking about the \emph{order} in which actions occur, we will define a discrete \emph{global clock}, $t=1,2,\ldots$. Using this, the notation $s_t$ denotes the state at time $t$ and $s_{t+1}$ denotes the state at time $t+1$. This enables to compare different states (and actions) occurring ordered in time during interaction.

The system being controlled is \emph{Markovian} if the result of an action does not depend on the previous actions and visited states (history), but only depends on the current state, i.e.
%
\begin{equation*}
  P(s_{t+1}\ |\ s_t,a_t,s_{t-1},a_{t-1},\ldots)\ \ =\ \ P(s_{t+1}\ |\ s_t,a_t)
  \ \ =\ \ T(s_t,a_t,s_{t+1})
\end{equation*}
%
\noindent The idea of Markovian dynamics is that the current state $s$ gives enough information to make an optimal decision; if is not important which states and actions preceded $s$. Another way of saying this, is that if you select an action $a$, the probability distribution over next states is the same as the last time you tried this action in the same state. More general models can be characterized by being $k$-\emph{Markov}, i.e. the last $k$ are states sufficient, such that \emph{Markov} is actually $1$-\emph{Markov}. Though, each $k$-\emph{Markov} problem can be transformed into an equivalent \emph{Markov} problem. The \emph{Markov property} forms a boundary between the \tsss{MDP} and more general models such as \tsss{POMDP}s.

%**********************************************************************************************
%* Reward Function
%*
%*
%*
%**********************************************************************************************

\paragraph{The Reward Function.}

The \emph{reward function}\footnote{Although we talk about \emph{rewards} here, with the usual connotation of something positive, the reward function merely gives a \emph{scalar} feedback signal. This can be interpreted as negative (\emph{punishment}) or positive (\emph{reward}). The various origins of work in \tsss{MDP}s in the literature creates an additional confusion with the reward function. In the \emph{operations resarch} literature, one usually speaks of a \emph{cost function} instead and the goal of learning and optimization is to \emph{minimize} this function.} specifies rewards for being in a state, or doing some action in a state. The \emph{state reward} function is defined as $R:S \rightarrow \mathbb{R}$, and it specifies the reward obtained in states. However, two other definitions exist. One can define either $R : S \times A \rightarrow \mathbb{R}$ or $R : S \times A \times S \rightarrow \mathbb{R}$. The first one gives rewards for performing an action in a state, and the second gives rewards for particular transitions between states. All definitions are interchangeable though the last one is convenient in \emph{model-free} algorithms (see Section~\ref{sec:modelfreealgs}), because there we usually need both the starting state and the resulting state in backing up values. Throughout this book we will mainly use $R(s,a,s^\prime$), but deviate from this when more convenient.

The reward function is an important part of the \tsss{MDP} that specifies implicitly the \emph{goal} of learning. For example, in episodic tasks such as in the games \emph{Tic-Tac-Toe} and chess, one can assign all states in which the agent has won a positive reward value, all states in which the agent loses a negative reward value and a zero reward value in all states where the final outcome of the game is a draw. The goal of the agent is to reach positive valued states, which means winning the game. Thus, the reward function is used to give \emph{direction} in which way the system, i.e. the \tsss{MDP}, should be controlled. Often, the reward function assigns non-zero reward to non-goal states as well, which can be interpreted as defining \emph{sub-goals} for learning.

%**********************************************************************************************
%* Markov decision processes
%*
%*
%*
%**********************************************************************************************

\paragraph{The Markov Decision Process.}
\label{sec:themdp}

Putting all elements together results in the definition of a \emph{Markov decision process}, which will be the base model for the large majority of methods described in this book.
%
\begin{defn}
\label{def:mdp}
  A \textbf{Markov decision process} is a tuple $\langle S, A, T, R \rangle$ in which $S$ is a finite set of states, $A$ a finite set of actions, $T$ a transition function defined as $T : S \times A \times S \rightarrow [0,1]$ and $R$ a reward function defined as $R : S \times A \times S \rightarrow \mathbb{R}$.
\end{defn}
%
\noindent The transition function $T$ and the reward function $R$ together define the \emph{model} of the \tsss{MDP}. Often \tsss{MDP}s are depicted as a state transition graph for an example) where the nodes correspond to states and (directed) edges denote transitions. A typical domain that is frequently used in the \tsss{MDP} literature is the \emph{maze} \cite{matthews:mal:22}, in which the reward function assigns a positive reward for reaching the exit state.

There are several distinct types of systems that can be modelled by this definition of an \tsss{MDP}. In \emph{episodic tasks}, there is the notion of \emph{episodes} of some length, where the goal is to take the agent from a starting state to a \emph{goal state}. An \emph{initial state distribution} $I : S \rightarrow [0,1]$ gives for each state the probability of the system being started in that state. Starting from a state $s$ the system progresses through a sequence of states, based on the actions performed. In episodic tasks, there is a specific subset $G \subseteq S$, denoted \emph{goal state area} containing states (usually with some distinct reward) where the process \emph{ends}. We can furthermore distinguish between \emph{finite, fixed horizon} tasks in which each episode consists of a fixed number of steps, \emph{indefinite horizon} tasks in which each episode can end but episodes can have arbitrary length, and \emph{infinite} horizon tasks where the system does not end at all. The last type of model is usually called a \emph{continuing task}.

Episodic tasks, i.e. in which there so-called \emph{goal states}, can be modelled using the same model defined in Definition~\ref{def:mdp}. This is usually modelled by means of \emph{absorbing states} or \emph{terminal states}, e.g. states from which every action results in a transition to that same state with probability $1$ and reward $0$. Formally, for an absorbing state $s$, it holds that $T(s,a,s) = 1$ and $R(s,a,s^\prime) = 0$ for all states $s^\prime \in S$ and actions $a \in A$. When entering an absorbing state, the process is reset and restarts in a new starting state. Episodic tasks and absorbing states can in this way be elegantly modelled in the same framework as continuing tasks.

%**********************************************************************************************
%* Policies
%*
%*
%*
%**********************************************************************************************

\subsection{Policies}

Given an \tsss{MDP} $\langle S, A, T, R \rangle$, a policy is a computable function that outputs for each state $s \in S$ an action $a \in A$ (or $a \in A(s)$). Formally, a \emph{deterministic} policy $\pi$ is a function defined as $\pi : S \rightarrow A$. It is also possible to define a \emph{stochastic} policy as $\pi : S \times A \rightarrow [0,1]$ such that for each state $s \in S$, it holds that $\pi(s,a) \geq 0$ and $\sum_{a \in A} \pi(s,a) = 1$. We will assume deterministic policies in this book unless stated otherwise.

\emph{Application} of a policy to an \tsss{MDP} is done in the following way. First, a start state $s_0$ from the initial state distribution $I$ is generated. Then, the policy $\pi$ suggest the action $a_0 = \pi(s_0)$ and this action is performed. Based on the transition function $T$ and reward function $R$, a transition is made to state $s_1$, with probability $T(s_0,a,s_1)$ and a reward $r_0 = R(s_0,a_0,s_1)$ is received. This process continues, producing $s_0, a_0, r_0, s_1, a_1, r_1, s_2, a_2, \ldots$. If the task is episodic, the process ends in state $s_{\text{goal}}$ and is restarted in a new state drawn from $I$. If the task is continuing, the sequence of states can be extended indefinitely.

The policy is part of the agent and its aim is to \emph{control} the environment modeled as an \tsss{MDP}. A fixed policy induces a stationary transition distribution over the \tsss{MDP} which can be transformed into a \emph{Markov system}\footnote{In other words, if $\pi$ is fixed, the system behaves as a stochastic transition system with a stationary distribution over states.} $\langle S^\prime, T^\prime \rangle$ where $S^\prime = S$ and $T^\prime(s,s^\prime) = T(s,a,s^\prime)$ whenever $\pi(s) = a$.

%**********************************************************************************************
%* Optimality, Discounting
%*
%*
%*
%**********************************************************************************************

\subsection{Optimality Criteria and Discounting}

In the previous sections, we have defined the environment (the \tsss{MDP}) and the agent (i.e. the controlling element, or policy). Before we can talk about algorithms for computing \emph{optimal} policies, we have to define what that means. That is, we have to define what the \emph{model of optimality} is. There are two ways of looking at optimality. First, there is the aspect of \emph{what} is actually being optimized, i.e. what is the \emph{goal} of the agent? Second, there is the aspect of how optimal the way in which the goal is being optimized, is. The first aspect is related to \emph{gathering reward} and is treated in this section. The second aspect is related to the efficiency and optimality of algorithms, and this is briefly touched upon and dealt with more extensively in Section~\ref{sec:mdpsolving} and further.

The goal of learning in an \tsss{MDP} is to gather rewards. If the agent was only concerned about the immediate reward, a simple optimality criterion would be to optimize $E[r_t]$. However, there are several ways of taking into account the future in how to behave now. There are basically three models of optimality in the \tsss{MDP}, which are sufficient to cover most of the approaches in the literature. They are strongly related to the types of tasks that were defined in Section~\ref{sec:themdp}.
%
\begin{figure}[H]
\begin{equation*}
  E \biggl [ \sum_{t=0}^h r_t \biggr ] \mbox{\hspace{2cm}}
  E \biggl [ \sum_{t=1}^{\infty} \gamma^t r_t \biggr ] \mbox{\hspace{2cm}}
  \lim_{h \rightarrow \infty}
    E \biggl [ \frac{1}{h} \sum_{t=0}^h r_t \biggr ]
\end{equation*}
\caption{\label{fig:optimalitycriteria} \textbf{Optimality}: \textbf{a)} finite horizon, \textbf{b)} discounted, infinite horizon, \textbf{c)} average reward.}
\end{figure}
%
\noindent The \emph{finite horizon} model simply takes a finite horizon of length $h$ and states that the agent should optimize its expected reward over this horizon, i.e. the next $h$ steps (see Figure~\ref{fig:optimalitycriteria}\textbf{a)}). One can think of this in two ways. The agent could in the first step take the $h$-\emph{step optimal action}, after this the $(h-1)$-\emph{step optimal action}, and so on. Another way is that the agent will always take the $h$-\emph{step optimal action}, which is called \emph{receding-horizon control}. The problem, however, with this model, is that the (optimal) choice for the horizon length $h$ is not always known.

In the \emph{infinite-horizon model}, the long-run reward is taken into account, but the rewards that are received in the future are discounted according to how far away in time they will be received. A \emph{discount factor} $\gamma$, with $0 \leq \gamma < 1$ is used for this (see Figure~\ref{fig:optimalitycriteria}\textbf{b)}). Note that in this \emph{discounted} case, rewards obtained later are discounted more than rewards obtained earlier. Additionally, the discount factor ensures that -- even with infinite horizon -- the sum of the rewards obtained is finite. In episodic tasks, i.e. in tasks where the horizon is finite, the discount factor is not needed or can equivalently be set to $1$. If $\gamma = 0$ the agent is said to be \emph{myopic}, which means that it is only concerned about immediate rewards. The discount factor can be interpreted in several ways; as an interest rate, probability of living another step, or the mathematical trick for bounding the infinite sum. The discounted, infinite-horizon model is mathematically more convenient, but conceptually similar to the finite horizon model. Most algorithms in this book use this model of optimality.

A third optimality model is the \emph{average-reward} model, maximizing the long-run \emph{average reward} (see Figure~\ref{fig:optimalitycriteria}\textbf{c)}). Sometimes this is called the \emph{gain optimal} policy and in the limit, as the discount factor approaches $1$, it is equal to the infinite-horizon discounted model. A difficult problem with this criterion that we cannot distinguish between two policies in which one receives a lot of reward in the initial phases and another one which does not. This initial difference in reward is hidden in the long-run average. This problem can be solved in using a \emph{bias optimal} model in which the long-run average is still being optimized, but policies are preferred if they additionally get initially extra reward. See \cite{mahadevan:arrl:96} for a survey on average reward \tsss{RL}.

Choosing between these optimality criteria can be related to the learning problem. If the length of the episode is known, the finite-horizon model is best. However, often this is not known, or the task is continuing, the infinite-horizon model is more suitable. \cite{koenig:tiorapofdtpt:02} gives an extensive overview of different modelings of \tsss{MDP}s and their relationship with optimality.

The second kind of optimality in this section is related to the more general aspect of the optimality of the learning process itself. We will encounter various concepts in the remainder of this book. We will briefly summarize three important notions here.

\emph{Learning optimality} can be explained in terms of \emph{what} the end result of learning might be. A first concern is whether the agent is able to obtain \emph{optimal performance} in principle. For some algorithms there are proofs stating this, but for some not. In other words, is there a way to ensure that the learning process will reach a global optimum, or merely a local optimum, or even an oscillation between performances? A second kind of optimality is related to the \emph{speed} of converging to a solution. We can distinguish between two learning methods by looking at how many interactions are needed, or how much computation is needed per interaction. And related to that, what will the performance be after a certain period of time? In supervised learning the optimality criterion is often defined in terms of \emph{predictive accuracy} which is different from optimality in the \tsss{MDP} setting. Also, it is important to look at how much \emph{experimentation} is necessary, or even allowed, for reaching optimal behavior. For example, a learning robot or helicopter might not be allowed to make many mistakes during learning.
A last kind of optimality is related to how much reward is \emph{not} obtained by the learned policy, as compared to an optimal one. This is usually called the \emph{regret} of a policy.

%**********************************************************************************************
%* Value functions
%*
%*
%*
%**********************************************************************************************

\section{Value Functions and Bellman Equations}
\label{sec:valuefunctions}

In the preceding sections we have defined \tsss{MDP}s and optimality criteria that can be useful for learning optimal policies. In this section we define \emph{value functions}, which are a way to link the optimality criteria to policies. Most learning algorithms for \tsss{MDP}s compute optimal policies by learning value functions. A value function represents an estimate \emph{how good} it is for the agent to be in a certain state (or how good it is to perform a certain action in that state). The notion of \emph{how good} is expressed in terms of an optimality criterion, i.e. in terms of the expected return. Value functions are defined for particular policies.

The \emph{value of a state $s$ under policy $\pi$}, denoted $V^\pi(s)$ is the expected return when starting in $s$ and following $\pi$ thereafter. We will use the infinite-horizon, discounted model in this section, such that this can be expressed\footnote{Note that we use $E_{\pi}$ for the \emph{expected value under policy} $\pi$.} as:
%
\begin{equation}
\label{eq:policyvalue}
  V^\pi(s) = E_\pi \biggl \{ \sum_{k=0}^\infty \gamma^k r_{t+k} | s_t = s \biggr \}
\end{equation}
%
\noindent A similar \emph{state-action value function} $Q : S \times A \rightarrow \mathbb{R}$ can be defined as the expected return starting from state $s$, taking action $a$ and thereafter following policy $\pi$:
%
\begin{equation*}
  Q^\pi(s,a) = E_\pi \biggl \{ \sum_{k=0}^\infty \gamma^k r_{t+k} | s_t = s, a_t = a \biggr \}
\end{equation*}
%
\noindent One fundamental property of value functions is that they satisfy certain recursive properties. For any policy $\pi$ and any state $s$ the expression in Equation~\ref{eq:policyvalue} can recursively be defined in terms of a so-called \emph{Bellman Equation} \cite{bellman:dp:57}:
%
\begin{align}
\label{eq:bellmanVpi}
      V^\pi(s) & = E_\pi \biggl \{ r_t + \gamma r_{t+1} +
                                     \gamma^2 r_{t+2} + \ldots | s_t = t \biggr \} \nonumber\\
               & = E_\pi \biggl \{ r_t + \gamma V^\pi(s_{t+1}) | s_t = s \biggr \} \nonumber\\
               & = \sum_{s^\prime} T(s,\pi(s),s^\prime)
                     \biggl ( R(s,a,s^\prime) + \gamma V^\pi(s^\prime) \biggr )
\end{align}
%
\noindent It denotes that the expected value of state is defined in terms of the immediate reward and values of possible next states weighted by their transition probabilities, and additionally a discount factor. $V^{\pi}$ is the unique solution for this set of equations. Note that multiple policies can have the same value function, but for a given policy $\pi$, $V^{\pi}$ is unique.

The goal for any given MDP is to find a \emph{best} policy, i.e. the policy that receives the most reward. This means maximizing the value function of Equation~\ref{eq:policyvalue} for all states $s \in S$. An \emph{optimal policy}, denoted $\pi^*$, is such that $V^{\pi^*}(s) \geq V^{\pi}(s)$ for all $s \in S$ and all policies $\pi$. It can be proven that the optimal solution $V^* = V^{\pi^*}$ satisfies the following Equation:
%
\begin{equation}
\label{eq:bellmanV}
  V^*(s) = \max_{a\in A} \sum_{s^\prime \in S} T(s,a,s^\prime)
    \biggl ( R(s,a,s^\prime) + \gamma V^*(s^\prime) \biggr )
\end{equation}
%
\noindent This expression is called the \emph{Bellman optimality equation}. It states that the value of a state under an optimal policy must be equal to the expected return for the best action in that state. To select an optimal action given the optimal state value function $V^*$ the following rule can be applied:
%
\begin{equation}
\label{eq:actionselectionV}
  \pi^*(s) = \arg\max_a \sum_{s^\prime \in S} T(s,a,s^\prime)
    \biggl ( R(s,a,s^\prime) + \gamma V^*(s^\prime) \biggr )
\end{equation}
%
\noindent We call this policy the \emph{greedy policy}, denoted $\pi_{greedy}(V)$ because it greedily selects the best action using the value function $V$. An analogous optimal state-action value is:
%
\begin{equation*}
  Q^*(s,a) = \sum_{s^\prime} T(s,a,s^\prime)
    \biggl ( R(s,a,s^\prime) + \gamma \max_{a^\prime} Q^*(s^\prime,a^\prime) \biggr )
\end{equation*}
%
\noindent $Q$-functions are useful because they make the weighted summation over different alternatives (such as in Equation~\ref{eq:actionselectionV}) using the transition function unnecessary. No forward-reasoning step is needed to compute an optimal action in a state. This is the reason that in model-free approaches, i.e. in case $T$ and $R$ are unknown, $Q$-functions are learned instead of $V$-functions. The relation between $Q^*$ and $V^*$ is given by
%
\begin{align}
  Q^*(s,a) & = \sum_{s^\prime \in S} T(s,a,s^\prime)
     \biggl ( R(s,a,s^\prime) + \gamma V^*(s^\prime) \biggr )\\
  V^*(s) & = \max_a Q^*(s,a)
\end{align}
%
\noindent Now, analogously to Equation~\ref{eq:actionselectionV}, optimal action selection can be simply put as:
%
\begin{equation}
\label{eq:actionselectionQ}
  \pi^*(s) = \arg\max_a Q^*(s,a)
\end{equation}
%
\noindent That is, the best action is the action that has the highest expected utility based on possible next states resulting from taking that action. One can, analogous to the expression in Equation~\ref{eq:actionselectionV}, define a greedy policy $\pi_{greedy}(Q)$ based on $Q$. In contrast to $\pi_{greedy}(V)$ there is no need to consult the model of the \tsss{MDP}; the $Q$-function suffices.


%**********************************************************************************************
%* Solving Markov Deicison Processes
%*
%*
%*
%**********************************************************************************************

\section{Solving Markov decision processes}
\label{sec:mdpsolving}

Now that we have defined \tsss{MDP}s, policies, optimality criteria and value functions, it is time to consider the question of \emph{how} to compute optimal policies. \emph{Solving} a given MDP means computing an optimal policy $\pi^*$. Several dimensions exist along which algorithms have been developed for this purpose. The most important distinction is that between \emph{model-based} and \emph{model-free} algorithms.

Model-based algorithms exist under the general name of \tsss{DP}. The basic assumption in these algorithms is that a \emph{model} of the \tsss{MDP} is known beforehand, and can be used to compute value functions and policies using the Bellman equation (see Equation~\ref{eq:bellmanV}). Most methods are aimed at computing state value functions which can, in the presence of the model, be used for optimal action selection. In this chapter we will focus on \emph{iterative} procedures for computing value functions and policies.

Model-free algorithms, under the general name of \tsss{RL}, do not rely on the availability of a perfect model. Instead, they rely on \emph{interaction} with the environment, i.e. a \emph{simulation} of the policy thereby generating \emph{samples} of state transitions and rewards. These samples are then used to estimate state-action value functions. Because a model of the \tsss{MDP} is not known, the agent has to \emph{explore} the \tsss{MDP} to obtain information. This naturally induces a \emph{exploration-exploitation} trade-off which has to be balanced to obtain an optimal policy.

A very important underlying mechanism, the so-called \emph{generalized policy iteration} (\tsss{GPI}) principle, present in all methods is depicted in Figure~\ref{fig:gpistuff}. This principle consists of two interaction processes. The \emph{policy evaluation} step estimates the utility of the current policy $\pi$, that is, it computes $V^\pi$. There are several ways for computing this. In model-based algorithms, one can use the model to compute it directly or iteratively approximate it. In model-free algorithms, one can \emph{simulate} the policy and estimate its utility from the sampled execution traces. The main purpose of this step is to gather information about the policy for computing the second step, the \emph{policy improvement} step. In this step, the values of the actions are evaluated for every state, in order to find possible improvements, i.e. possible other actions in particular states that are better than the action the current policy proposes. This step computes an improved policy $\pi^\prime$ from the current policy $\pi$ using the information in $V^\pi$. Both the evaluation and the improvement steps can be implemented in various ways, and interleaved in several distinct ways. The bottom line is that there is a policy that drives value learning, i.e. it determines the value function, but in turn there is a value function that can be used by the policy to select good actions. Note that it is also possible to have an \emph{implicit} representation of the policy, which means that only the value function is stored, and a policy is computed on-the-fly for each state based on the value function when needed. This is common practice in model-free algorithms (see Section~\ref{sec:modelfreealgs}). And vice versa it is also possible to have implicit representations of value functions in the context of an explicit policy representation. Another interesting aspect is that in general a value function does not have to be perfectly accurate. In many cases it suffices that sufficient distinction is present between suboptimal and optimal actions, such that small errors in values do not have to influence policy optimality. This is also important in \emph{approximation} and \emph{abstraction} methods discussed in the next chapter.

\begin{figure}[t]
  \centering
  \includegraphics[width=0.25\linewidth]{pictures/GPI}
  \hspace{0.04\linewidth}
  \includegraphics[width=0.65\linewidth]{pictures/coconv}
  \caption{\label{fig:gpistuff}a) The algorithms in Section~\ref{sec:mdpsolving} can be seen as instantiations of \emph{Generalized Policy Iteration} (GPI) \cite{sutton:rlai:98}. The \emph{policy evaluation} step estimates $V^{\pi}$, the policy's performance. The \emph{policy improvement} step improves the policy $\pi$ based on the estimates in $V^{\pi}$. b) The gradual convergence of both the value function and the policy to optimal versions.}
\end{figure}

\paragraph{Planning as a \tsss{RL} Problem.} The \tsss{MDP} formalism is a general formalism for \emph{decision-theoretic planning}, which entails that standard (deterministic) \emph{planning} problems can be formalized as such too. All the algorithms in this chapter can -- in principle -- be used for these planning problems too. In order to solve planning problems in the \tsss{MDP} framework we have to specify \emph{goals} and \emph{rewards}. We can assume that the transition function $T$ is given, accompanied by a \emph{precondition function}. In planning we are given a \emph{goal} function $G : S \rightarrow \{\m{true}, \m{false}\}$ that defines which states are goal states. The planning task is compute a sequence of actions $a_t,a_{t+1},\ldots, a_{t+n}$ such that applying this sequence from a \emph{start} state will lead to a state $s \in G$. All transitions are assumed to be deterministic, i.e. for all states $s \in S$ and actions $a \in A$ there exists only one state $s^\prime \in S$ such that $T(s,a,s^\prime)=1$. All states in $G$ are assumed to be absorbing. The only thing left is to specify the reward function. We can specify this in such a way that a positive reinforcement is received once a goal state is reached, and zero otherwise:
%
\begin{equation*}
  R(s_t,a_t,s_{t+1}) =
  \begin{cases}
    1, & \text{if}\ s_t \not\in G\ \text{and}\ s_{t+1} \in G \\
    0, & \text{otherwise}
  \end{cases}
\end{equation*}
%
\noindent Now, depending on whether the transition function and reward function are known to the agent, one can solve this planning task with either model-based or model-free learning. The difference with classic planning is that the learned policy will apply to all states.

%**********************************************************************************************
%* Model-Based Solution Techniques
%*
%*
%*
%**********************************************************************************************

\section{Dynamic Programming: Model-based Solution Techniques}
\label{sec:modelbasedalgs}

The term \tsss{DP} refers to a class of algorithms that is able to compute optimal policies in the presence of a perfect model of the environment. The assumption that a model is available will be hard to ensure for many applications. However, we will see that from a theoretical viewpoint, as well as from an algorithmic viewpoint, \tsss{DP} are very relevant because they define fundamental computational mechanisms which are also used when no model is available. The methods in this section all assume a standard \tsss{MDP} $\langle S, A, T, R \rangle$, where the state and action sets are finite and discrete such that they can be stored in tables. Furthermore, transition, reward and value functions are assumed to store values for all states and actions separately.

%**********************************************************************************************
%* The standard DP algorithms
%*
%*
%*
%**********************************************************************************************

\subsection{Fundamental \tsss{DP} Algorithms}

Two core \tsss{DP} methods are \emph{policy iteration} \cite{howard:dpamdp:60} and \emph{value iteration} \cite{bellman:dp:57}. In the first, the \tsss{GPI} mechanism is clearly separated into two steps, whereas the second represents a tight integration of policy evaluation and improvement. We will consider both these algorithms in turn.

%**********************************************************************************************
%* Policy Iteration
%*
%*
%*
%**********************************************************************************************

\subsubsection{Policy Iteration}

\emph{Policy iteration} (PI) \cite{howard:dpamdp:60} iterates between the two phases of $\tsss{GPI}$. The \emph{policy evaluation} phase computes the value function of the current policy and the \emph{policy improvement} phase computes an improved policy by a maximization over the value function. This is repeated until converging to an optimal policy.

%**********************************************************************************************
%* Policy Evaluation
%*
%*
%*
%**********************************************************************************************

\paragraph{Policy Evaluation: The Prediction Problem.} A first step is to find the value function $V^\pi$ of a fixed policy $\pi$. This is called the \emph{prediction problem}. It is a part of the complete problem, that of computing an \emph{optimal} policy. Remember from the previous sections that for all $s \in S$,
%
\begin{equation}
\label{eq:bellmanVpi}
  V^{\pi}(s) = \sum_{s^\prime \in S} T(s,\pi(s),s^\prime)
    \biggl ( R(s,\pi(s),s^\prime) + \gamma V^{\pi}(s^\prime) \biggr )
\end{equation}
%
\noindent If the dynamics of the system is known, i.e. a model of the \tsss{MDP} is given, then these equations form a system of $|S|$ equations in $|S|$ unknowns (the values of $V^\pi$ for each $s \in S$). This can be solved by linear programming (\tsss{LP}). However, an \emph{iterative} procedure is possible, and in fact common in \tsss{DP} and \tsss{RL}. The Bellman equation is transformed into an \emph{update rule} which updates the current value function $V^{\pi}_k$ into $V^{\pi}_{k+1}$ by 'looking one step further in the future', thereby extending the planning horizon with one step:
%
\begin{align}
\label{eq:updatev_k_plus_one}
  V^{\pi}_{k+1}(s) & = E_\pi \biggl \{ r_t + \gamma V^{\pi}_k(s_{t+1}) | s_t = s \biggr \} \nonumber\\
             & = \sum_{s^\prime} T(s,\pi(s),s^\prime)
                  \biggl ( R(s,\pi(s),s^\prime) + \gamma V^{\pi}_k(s^\prime) \biggr )
\end{align}
%
\noindent The sequence of approximations of $V^{\pi}_{k}$ as $k$ goes to infinity can be shown to converge. In order to converge, the update rule is applied to each state $s \in S$ in each iteration. It replaces the old value for that state by a new one that is based on the expected value of possible successor states, intermediate rewards and weighted by the transition probabilities. This operation is called a \emph{full backup} because it is based on all possible transitions from that state.

A more general formulation can be given by defining a \emph{backup operator} $B^\pi$ over arbitrary real-valued functions $\varphi$ over the state space (e.g. a value function):
%
\begin{equation}
\label{eq:backup}
  (B^\pi \varphi)(s) = \sum_{s^\prime \in S} T(s,\pi(s),s^\prime)
    \biggl ( R(s,\pi(s),s^\prime) + \gamma \varphi(s^\prime) \biggr )
\end{equation}
%
\noindent The value function $V^\pi$ of a fixed policy $\pi$ satisfies the \emph{fixed point} of this backup operator as $V^\pi = B^\pi V^\pi$. A useful special case of this backup operator is defined with respect to a fixed action $a$:
%
\begin{equation*}
  (B^a \varphi)(s) = R(s) + \gamma \sum_{s^\prime \in S} T(s,a,s^\prime)\varphi(s^\prime)
\end{equation*}
%
\noindent Now \tsss{LP} for solving the \emph{prediction problem} can be stated as follows. Computing $V^{\pi}$ can be accomplished by solving the Bellman equations (see Equation~\ref{eq:bellmanV}) for all states. The \emph{optimal} value function $V^*$ can be found by using a \tsss{LP} problem solver that computes $V^* = \arg\max_V \sum_s V(s)$ subject to $V(s) \geq (B^a V)(s)$ for all $a$ and $s$.


%**********************************************************************************************
%* Policy Improvement
%*
%*
%*
%**********************************************************************************************

\paragraph{Policy Improvement.} Now that we know the value function $V^\pi$ of a policy $\pi$ as the outcome of the policy evaluation step, we can try to improve the policy. First we identify the value of all actions by using:
%
\begin{align}
  Q^\pi(s,a) & = E_\pi \biggl \{ r_t + \gamma V^\pi(s_{t+1}) | s_t = s, a_t = a \biggr \} \\
             & = \sum_{s^\prime} T(s,a,s^\prime) \biggl ( R(s,a,s^\prime) + \gamma V^\pi(s^\prime) \biggr )
\end{align}
%
\noindent If now $Q^\pi(s,a)$ is larger than $V^\pi(s)$ for some $a \in A$ then we could do better by choosing action $a$ instead of the current $\pi(s)$. In other words, we can \emph{improve} the current policy by selecting a different, better, action in a particular state. In fact, we can evaluate all actions in all states and choose the best action in all states. That is, we can compute the \emph{greedy} policy $\pi^\prime$ by selecting the best action in each state, based on the current value function $V^\pi$:
%
\begin{align}
  \pi^\prime(s) & = \arg \max_a Q^\pi(s,a) \nonumber \\
                & = \arg \max_a E
                  \biggl \{ r_t + \gamma V^\pi(s_{t+1}) | s_t = s, a_t = a \biggr \} \nonumber \\
                & = \arg \max_a \sum_{s^\prime} T(s,a,s^\prime) \biggl ( R(s,a,s^\prime) + \gamma V^\pi(s^\prime) \biggr )
\end{align}
%
\noindent Computing an improved policy by greedily selecting the best action with respect to the value function of the original policy is called \emph{policy improvement}. If the policy cannot be improved in this way, it means that the policy is already optimal and its value function satisfies the Bellman equation for the optimal value function. In a similar way one can also perform these steps for stochastic policies by blending the action probabilities into the expectation operator.

\begin{algorithm}[t]
\caption{ \label{alg:pi} Policy Iteration \protect \cite{howard:dpamdp:60} }
\begin{algorithmic}
    \REQUIRE $V(s) \in \mathbb{R}$ and $\pi(s) \in A(s)$ arbitrarily for all $s
    \in S$\\
    \STATE \COMMENT{\textsc{Policy Evaluation}}\\
    \REPEAT
        \STATE $\Delta := 0$\\
    \FOR{\textbf{each} $s \in S$}
        \STATE $v := V^{\pi}(s)$\\
        \STATE $V(s) := \sum_{s^\prime}
        T(s,\pi(s),s^\prime) \biggl ( R(s,\pi(s),s^\prime) + \gamma V(s^\prime) \biggr )$\\
        \STATE $\Delta := \max(\Delta,|v-V(s)|)$\\
    \ENDFOR
    \UNTIL $\Delta < \sigma$
    \STATE \COMMENT{\textsc{Policy Improvement}}\\
    \STATE policy-stable $:= \true$\\
    \FOR{\textbf{each} $s \in S$}
        \STATE $b := \pi(s)$\\
    \STATE $\pi(s) := \arg\max_a \sum_{s^\prime}
    T(s,a,s^\prime) \biggl ( R(s,a,s^\prime) + \gamma \cdot V(s^\prime) \biggr )$\\
    \STATE \textbf{if} $b \neq \pi(s)$ \textbf{then} policy-stable $:= \false$\\
    \ENDFOR
    \STATE \textbf{if} policy-stable \textbf{then} stop; \textbf{else} go to \textsc{Policy Evaluation}
\end{algorithmic}
\end{algorithm}

Summarizing, \emph{policy iteration} \cite{howard:dpamdp:60} starts with an arbitrary initialized policy $\pi_0$. Then a sequence of iterations follows in which the current policy is evaluated after which it is improved. The first step, the \emph{policy evaluation} step computes $V^{\pi_{k}}$, making use of Equation~\ref{eq:updatev_k_plus_one} in an iterative way. The second step, the \emph{policy improvement} step, computes $\pi_{k+1}$ from $\pi_k$ using $V^{\pi_{k}}$. For each state, using equation \ref{eq:actionselectionV}, the optimal action is determined. If for all states $s$, $\pi_{k+1}(s) = \pi_{k}(s)$, the policy is \emph{stable} and the policy iteration algorithm can stop. Policy iteration generates a sequence of alternating policies and value functions
\begin{equation*}
\pi_0 \rightarrow V^{\pi_0} \rightarrow \pi_1 \rightarrow V^{\pi_1} \rightarrow
\pi_2 \rightarrow V^{\pi_2} \rightarrow \pi_3 \rightarrow V^{\pi_3} \rightarrow \ldots \rightarrow \pi^*
\end{equation*}

\noindent The complete algorithm can be found in Algorithm~\ref{alg:pi}.

\noindent For finite \tsss{MDP}s, i.e. state and action spaces are finite, policy iteration converges after a finite number of iterations. Each policy $\pi_{k+1}$ is a strictly better policy than $\pi_{k}$ unless in case $\pi_{k} = \pi^*$, in which case the algorithm stops. And because for a finite MDP, the number of different policies is finite, policy iteration converges in finite time. In practice, it usually converges after a small number of iterations. Although policy iteration computes the optimal policy for a given MDP in finite time, it is relatively inefficient. In particular the first step, the policy evaluation step, is computationally expensive. Value functions for all intermediate policies $\pi_0 , \ldots , \pi_k , \ldots , \pi^*$ are computed, which involves multiple sweeps through the complete state space per iteration. A bound on the number of iterations is not known \cite{littman:otcosmdp:95} and depends on the \tsss{MDP} transition structure, but it often converges after few iterations in practice.

%**********************************************************************************************
%* Value Iteration
%*
%*
%*
%**********************************************************************************************

\subsubsection{Value Iteration}
The policy iteration algorithm completely separates the evaluation and improvement phases. In the evaluation step, the value function must be computed in the limit. However, it is not necessary to wait for full convergence, but it is possible to stop evaluating earlier and improve the policy based on the evaluation so far. The extreme point of truncating the evaluation step is the \emph{value iteration} \cite{bellman:dp:57} algorithm. It breaks off evaluation after just one iteration. In fact, it immediately blends the policy improvement step into its iterations, thereby purely focusing on estimating directly the value function. Necessary updates are computed on-the-fly. In essence, it combines a truncated version of the policy evaluation step with the policy improvement step, which is essentially Equation~\ref{eq:bellmanV} turned into one update rule:
%
\begin{align}
    V_{t+1}(s) &= \max_a \sum_{s^\prime} T(s,a,s^\prime) \biggl ( R(s,a,s^\prime) +
    \gamma V_t(s^\prime) \biggr ) \label{eq:bellman_update}\\
    &= \max_a Q_{t+1}(s,a). \label{eq:bellman_update2}
\end{align}
%
\begin{algorithm}[t]
\caption{ \label{alg:vi} Value Iteration \protect\cite{bellman:dp:57}}
\begin{algorithmic}
    \REQUIRE initialize V arbitrarily (e.g. $V(s) := 0, \forall s \in S$)\\
    \REPEAT
        \STATE $\Delta := 0$\\
        \FOR{\textbf{each} $s \in S$}
            \STATE $v := V(s)$\\
            \FOR{\textbf{each} $a \in A(s)$}
                \STATE $Q(s,a) := \sum_{s'} T(s,a,s') \biggl ( R(s,a,s^\prime) + \gamma V(s') \biggr )$\\
            \ENDFOR
            \STATE $V(s) := \max_a Q(s,a)$\\
            \STATE $\Delta := \max(\Delta, |v-V(s)|)$\\
    \ENDFOR
    \UNTIL{$\Delta < \sigma$}
\end{algorithmic}
\end{algorithm}
%
\noindent Using Equations~\eqref{eq:bellman_update}~and~\eqref{eq:bellman_update2}, the value iteration algorithm (see Figure~\ref{alg:vi}) can be stated as follows: starting with a value function $V_0$ over all states, one iteratively updates the value of each state according to~\eqref{eq:bellman_update} to get the next value functions $V_t$ ($t=1,2,3,\ldots$). It produces the following sequence of value functions:
%
\begin{equation*}
  V_0 \rightarrow V_1 \rightarrow V_2 \rightarrow V_3 \rightarrow V_4 \rightarrow
  V_5 \rightarrow V_6 \rightarrow V_7 \rightarrow \ldots V^*
\end{equation*}
%
\noindent Actually, in the way it is computed it also produces the intermediate $Q$-value functions such that the sequence is
%
\begin{equation*}
  V_0 \rightarrow Q_1 \rightarrow V_1 \rightarrow Q_2 \rightarrow V_2 \rightarrow Q_3 \rightarrow
  V_3 \rightarrow Q_4 \rightarrow V_4 \rightarrow \ldots V^*
\end{equation*}
%
\noindent Value iteration is guaranteed to converge in the limit towards $V^*$, i.e. the Bellman optimality Equation~\eqref{eq:bellmanV} holds for each state. A deterministic policy $\pi$ for all states $s \in S$ can be computed using Equation~\ref{eq:actionselectionV}. If we use the same general \emph{backup operator} mechanism used in the previous section, we can define value iteration in the following way.
%
\begin{equation}
\label{eq:optimalbackup}
  (B^* \varphi)(s) = \max_a \sum_{s^\prime \in S} T(s,a,s^\prime)
     \biggl \{ R(s,a,s^\prime) + \gamma \varphi(s) \biggr \}
\end{equation}
%
\noindent The backup operator $B^*$ functions as a \emph{contraction mapping} on the value function. If we let $\pi^*$ denote the \emph{optimal} policy and $V^*$ its value function, we have the relationship (fixed point) $V^* = B^* V^*$ where $(B^* V)(s) = \max_a (B^a V)(s)$. If we define $Q^*(s,a) = B^aV^*$ then we have $\pi^*(s) = \pi_{greedy}(V^*)(s) = \arg\max_a Q^*(s,a)$. That is, the algorithm starts with an arbitrary value function $V^0$ after which it iterates $V_{t+1} = B^*V^t$ until $\| V_{t+1} - V_t \|_S < \epsilon$, i.e. until the distance between subsequent value function approximations is small enough.

%**********************************************************************************************
%* Asynchronous and Approximate Methods in DP
%* so, MPI, search stuff etc.
%*
%*
%**********************************************************************************************

\subsection{Efficient \tsss{DP} Algorithms}
\label{sec:efficientDP}

The policy iteration and value iteration algorithms can be seen as spanning a \emph{spectrum} of \tsss{DP} approaches. This spectrum ranges from complete \emph{separation} of evaluation and improvement steps to a complete \emph{integration} of these steps. Clearly, in between the extreme points is much room for variations on algorithms. Let us first consider the computational complexity of the extreme points.


%**********************************************************************************************
%* Complexity
%*
%*
%**********************************************************************************************

\paragraph{Complexity.} \begin{sloppypar} Value iteration works by producing successive approximations of the optimal value function. Each iteration can be performed in $O(|A||S|^2)$ steps, or faster if $T$ is sparse. However, the \emph{number} of iterations can grow exponentially in the discount factor cf. \cite{bertsekas:ndp:96}. This follows from the fact that a larger $\gamma$ implies that a longer sequence of future rewards has to be taken into account, hence a larger number of value iteration steps because each step only extends the horizon taking into account in $V$ by one step. The complexity of value iteration is linear in number of actions, and quadratic in the number of states. But, usually the transition matrix is sparse. In practice policy iteration converges much faster, but each evaluation step is expensive. Each iteration has a complexity of $O(|A||S|^2+|S|^3)$, which can grow large quickly. A worst case bound on the number of iterations is not known \cite{littman:otcosmdp:95}. Linear programming is is a common tool that can be used for the evaluation too. In general, the number of iterations and value backups can quickly grow extremely large when the problem size grows. The state spaces of games such as backgammon and chess consist of too many states to perform just one full sweep. In this section we will describe some efficient variations on \tsss{DP} approaches. Detailed coverage of complexity results for the solution of \tsss{MDP}s can be found in \cite{littman:otcosmdp:95, bertsekas:ndp:96, boutilier:dtp:99}.
\end{sloppypar}

The efficiency of \tsss{DP} can be roughly improved along two lines. The first is a \emph{tighter integration} of the evaluation and improvement steps of the \tsss{GPI} process. We will discuss this issue briefly in the next section. The second is that of using (\emph{heuristic}) \emph{search} algorithms in combination with \tsss{DP} algorithms. For example, using search as an exploration mechanism can highlight important parts of the state space such that value backups can be concentrated on these parts. This is the underlying mechanism used in the methods discussed briefly in Section~\ref{sec:heuristicsandsearch}

%**********************************************************************************************
%* Styles of Updating
%*
%*
%**********************************************************************************************

\subsubsection{Styles of Updating}
\label{sec:stylesofupdating}
The full backups updates in \tsss{DP} algorithms can be done in several ways. We have assumed in the description of the algorithms that in each step an old and a new value function are kept in memory. Each update puts a new value in the new table, based on the information of the old. This is called \emph{synchronous}, or \emph{Jacobi-style} updating \cite{sutton:rlai:98}. This is useful for explanation of algorithms and theoretical proofs of convergence. However, there are two more common ways for updates. One can keep a single table and do the updating directly in there. This is called \emph{in-place} updating \cite{sutton:rlai:98} or \emph{Gauss-Seidel} \cite{bertsekas:ndp:96} and usually speeds up convergence, because during one sweep of updates, some updates use already newly updated values of other states. Another type of updating is called \emph{asynchronous updating} which is an extension of the \emph{in-place} updates, but here updates can be performed in any order. An advantage is that the updates may be distributed unevenly throughout the state(-action) space, with more updates being given to more important parts of this space. For all these methods convergence can be proved under the general condition that values are updated infinitely often but with a finite frequency.

%**********************************************************************************************
%* MPI
%*
%*
%**********************************************************************************************

\paragraph{Modified Policy Iteration.} \emph{Modified policy iteration} (\tsss{MPI}) \cite{puterman:mpiafdmdp:78} strikes a middle ground between value and policy iteration. \tsss{MPI} maintains the two separate steps of \tsss{GPI}, but both steps are not necessarily computed in the limit. The key insight here is that for policy improvement, one does not need an \emph{exactly} evaluated policy in order to improve it. For example, the policy estimation step can be approximative after which a policy improvement step can follow. In general, both steps can be performed quite independently \emph{by different means}. For example, instead of iteratively applying the Bellman update rule from Equation~\ref{eq:bellman_update2}, one can perform the policy estimation step by using a sampling procedure such as \emph{Monte Carlo} estimation \cite{sutton:rlai:98}. These general forms in which mixed forms of estimation and improvements is captured by the generalized policy iteration mechanism depicted in Figure~\ref{fig:gpistuff}. Policy iteration and value iteration are both the extreme cases of modified policy iteration, whereas \tsss{MPI} is a general method for asynchronous updating.


%**********************************************************************************************
%* Heuristics, Search
%*
%*
%**********************************************************************************************

\subsubsection{Heuristics and Search}
\label{sec:heuristicsandsearch}

In many realistic problems, only a fraction of the state space is relevant to the problem of reaching the goal state from some state $s$. This has inspired a number of algorithms that focus computation on states that seem most relevant for finding an optimal policy from a start state $s$. These algorithms usually display good \emph{anytime behavior}, i.e. they produce good or reasonable policies fast, after which they are gradually improved. In addition, they can be seen as implementing various ways of \emph{asynchronous} \tsss{DP}.


%**********************************************************************************************
%* Envelopes
%*
%*
%**********************************************************************************************

\paragraph{Envelopes and Fringe States.} \begin{sloppypar} One form of \emph{asynchronous} methods is the \tsss{Plexus} system \cite{dean:putcisd:95}. It was designed for goal-based reward functions, i.e. episodic tasks in which only goal states get positive reward. It starts with an approximated version of the \tsss{MDP} in which not the full state space is contained. This smaller version of the \tsss{MDP} is called an \emph{envelope} and it includes the agent's current state and the goal state. A special \tsss{OUT} state represents all the states outside the envelope. The initial envelope is constructed by a forward search until a goal state is found. The envelope can be extended by considering states outside the envelope that can be reached with high probability. The intuitive idea is to include in the envelope all the states that are likely to be reached on the way to the goal. Once the envelope has been constructed a policy is computed through policy iteration. If at any point the agent leaves the envelope, it has to replan by extending the envelope. This combination of learning and planning still uses policy iteration, but on a much smaller (and presumably more relevant with respect to the goal) state space.
\end{sloppypar}

A related method proposed in \cite{tash:csfasp:94} considers goal-based tasks too. However, instead of the single \tsss{OUT} state, they keep a \emph{fringe} of states on the edge of the envelope and use a heuristic to estimate values of the other states. When computing a policy for the envelope, all fringe states become absorbing states with the heuristic set as their value. Over time the heuristic values of the fringe states converge to the optimal values of those states.

Similar to the previous methods the \tsss{LAO*} algorithm \cite{hansen:lao:01} also alternates between an expansion phase and a policy generation phase. It too keeps a fringe of states outside the envelope such that expansions can be larger than the envelope method in \cite{dean:putcisd:95}. The motivation behind \tsss{LAO*} was to extend the classic search algorithm \tsss{AO*} cf. \cite{russell:aiama:03} to \emph{cyclic} domains such as \tsss{MDPs}.



%**********************************************************************************************
%* Search and Planning in DP
%*
%*
%**********************************************************************************************

\paragraph{Search and Planning in \tsss{DP}.} \emph{Real-time dynamic} \tsss{DP} (\tsss{RTDP}) \cite{barto:ltaurtdp:95} combines forward search with \tsss{DP} too. It is used as an alternative for value iteration in which only a subset of values in the state space are backed up in each iteration. \tsss{RTDP} performs \emph{trials} from a randomly selected state to a goal state, by simulating the greedy policy using an \emph{admissable heuristic} function as the initial value function. It then backups values \emph{fully} only along these trials, such that backups are concentrated on the \emph{relevant} parts of the state. The approach was later extended into \emph{labeled} \tsss{RTDP} \cite{bonet:lrtdp:03} where some states are \emph{labeled} as \emph{solved} which means that their value has already converged. Furthermore, it was recently extended to \emph{bounded} \tsss{RTDP}\cite{mcmahan:brtdp:05} which keeps lower and upper \emph{bounds} on the optimal value function. Other recent methods along these lines are \emph{focussed} \tsss{DP} \cite{ferguson:fdp:04} and \emph{heuristic search-DP} \cite{bonet:fhsafpwuaff:03}

%**********************************************************************************************
%* Model-Free Solution Techniques
%*
%*
%*
%**********************************************************************************************

\section{Reinforcement Learning: Model-Free Solution Techniques}
\label{sec:modelfreealgs}

The previous section has reviewed several methods for computing an optimal policy for an \tsss{MDP} assuming that a (perfect) model is available. \tsss{RL} is primarily concerned with how to obtain an optimal policy when such a model is not available. \tsss{RL} adds to \tsss{MDP}s a focus on approximation and incomplete information, and the need for sampling and exploration. In contrast with the algorithms discussed in the previous section, \emph{model-free} methods do not rely on the availability of priori known transition and reward models, i.e. a \emph{model of the MDP}. The lack of a model generates a need to \emph{sample} the MDP to gather statistical knowledge about this unknown model. Many model-free \tsss{RL} techniques exist that probe the environment by doing actions, thereby estimating the same kind of state value and state-action value functions as model-based techniques. This section will review model-free methods along with several efficient extensions.

In model-free contexts one has still a choice between two options. The first one is first to \emph{learn} the transition and reward model from interaction with the environment. After that, when the model is (approximately or sufficiently) correct, all the \tsss{DP} methods from the previous section apply. This type of learning is called \emph{indirect} \tsss{RL}. The second option, called \emph{direct} \tsss{RL}, is to step right into estimating values for actions, without even estimating the model of the \tsss{MDP}. Additionally, mixed forms between these two exists too. For example, one can still do model-free estimation of action values, but use an approximated model to speed up value learning by using this model to perform more, and in addition, full backups of values (see Section~\ref{sec:efficientRL}). Most model-free methods however, focus on direct estimation of (action) values.

A second choice one has to make is what to do with the \emph{temporal credit assignment}. It is difficult to assess the utility of some action, if the real effects of this particular action can only be perceived much later. One possibility is to wait until the "end" (e.g. of an episode) and punish or reward specific actions along the path taken. However, this will take a lot of memory and often, with ongoing tasks, it is not known beforehand whether, or when, there will be an "end". Instead, one can use similar mechanisms as in \emph{value iteration} to adjust the estimated value of a state based on the immediate reward and the estimated (discounted) value of the next state. This is generally called \emph{temporal difference learning} which is a general mechanism underlying the model-free methods in this section. The main difference with the update rules for \tsss{DP} approaches (such as Equation~\ref{eq:bellman_update}) is that the transition function $T$ and reward function $R$ cannot appear in the update rules now. The general class of algorithms that interact with the environment and update their estimates after each experience is called \emph{online}.

\begin{algorithm}[t]
\caption{ \label{alg:onlineRL} A general algorithm for online \tsss{RL}}
\begin{algorithmic}
    \FOR{\textbf{each} episode}
        \STATE $s \in S$ is initialized as the \emph{starting} state\\
        \STATE $t := 0$
        \REPEAT
            \STATE choose an action $a \in A(s)$\\
            \STATE perform action $a$
            \STATE observe the new state $s^\prime$ and received reward $r$\\
            \STATE update $\tilde{T}$, $\tilde{R}$, $\tilde{Q}$ and/or $\tilde{V}$\\
            \STATE using the experience $\langle s, a, r, s^\prime \rangle$
            \STATE $s := s^\prime$\\
        \UNTIL{$s^\prime$ is a goal state}
    \ENDFOR
\end{algorithmic}
\end{algorithm}

A general template for \emph{online} \tsss{RL} is depicted in Figure~\ref{alg:onlineRL}. It shows an interaction loop in which the agent selects an action (by whatever means) based on its current state, gets feedback in the form of the resulting state and an associated reward, after which it updates its estimated values stored in $\tilde{V}$ and $\tilde{Q}$ and possibly statistics concerning $\tilde{T}$ and $\tilde{R}$ (in case of some form of indirect learning). The selection of the action is based on the current state $s$ and the value function (either $Q$ or $V$). To solve the exploration-exploitation problem, usually a separate \emph{exploration} mechanism ensures that sometimes the best action (according to current estimates of action values) is taken (exploitation) but sometimes a different action is chosen (exploration). Various choices for exploration, ranging from random to sophisticated, exist and we will see some examples in Section~\ref{sec:efficientRL}.

%**********************************************************************************************
%* Exploration
%*
%*
%*
%**********************************************************************************************

\paragraph{Exploration.} One important aspect of model-free algorithms is that there is a need for \emph{exploration}. Because the model is unknown, the learner has to try out different actions to see their results. A learning algorithm has to strike a balance between \emph{exploration} and \emph{exploitation}, i.e. in order to gain a lot of reward the learner has to exploit its current knowledge about good actions, although it sometimes must try out different actions to explore the environment for possible better actions. The most basic exploration strategy is the $\epsilon$-greedy policy, i.e. the learner takes its current best action with probability $(1-\epsilon)$ and a (randomly selected) other action with probability $\epsilon$. There are many more ways of doing exploration (see \cite{wiering:eierl:99, reynolds:rlwe:02, ratitch:ocomdparlild:05} for overviews) and in Section~\ref{sec:efficientRL} we will see some examples. One additional method that is often used in combination with the algorithms in this section is the \emph{Boltzmann} (or: \emph{softmax}) exploration strategy. It is only slightly more complicated than the $\epsilon$-greedy strategy. The action selection strategy is still random, but selection probabilities are weighted by their relative $Q$-values. This makes it more likely for the agent to choose very good actions, whereas two actions that have similar $Q$-values will have almost the same probability to get selected. Its general form is
%
\begin{equation}
\label{eq:boltzmann}
  P(a_n) = \frac{e^{\frac{Q(s,a)}{T}}}{\sum_i e^{\frac{Q(s,a_i)}{T}}}
\end{equation}
%
\noindent in which $P(a_n)$ is the probability of selecting action $a_n$ and $T$ is the \emph{temperature} parameter. Higher values of $T$ will move the selection strategy more towards a purely random strategy and lower values will move to a fully greedy strategy. A combination of both $\epsilon$-greedy and Boltzmann exploration can be taken by taking the best action with probability $(1-\epsilon)$ and otherwise an action computed according to Equation~\ref{eq:boltzmann} \cite{wiering:eierl:99}.

Another simple method to stimulate exploration is \emph{optimistic Q-values initialization}; one can initialize all $Q$-values to high values -- e.g. an a priori defined upperbound -- at the start of learning. Because $Q$-values will decrease during learning, actions that have not been tried a number of times will have a large enough value to get selected when using Boltzmann exploration for example. Another solution with a similar effect is to keep counters on the number of times a particular state-action pair has been selected.

%**********************************************************************************************
%* Temporal Difference Methods
%*
%*
%*
%**********************************************************************************************

\subsection{Temporal Difference Learning}

\emph{Temporal difference} learning algorithms learn estimates of values based on other estimates. Each step in the world generates a \emph{learning example} which can be used to bring some value in accordance to the immediate reward and the estimated value of the next state or state-action pair. An intuitive example, along the lines of \cite{sutton:rlai:98}(Chapter $6$), is the following.

Imagine you have to predict at what time your guests can arrive for a small diner in your house. Before cooking, you have to go to the supermarket, the butcher and the wine seller, in that order. You have estimates of driving times between all locations, and you predict that you can manage to visit the two last stores both in $10$ minutes, but given the crowdy time on the day, your estimate about the supermarket is a half hour. Based on this prediction, you have notified your guests that they can arrive no earlier than $18.00h$. Once you have found out while in the supermarket that it will take you only $10$ minutes to get all the things you need, you can adjust your estimate on arriving back home with $20$ minutes less. However, once on your way from the butcher to the wine seller, you see that there is quite some traffic along the way and it takes you $30$ minutes longer to get there. Finally you arrive $10$ minutes later than you predicted in the first place. The bottom line of this example is that you can adjust your estimate about what time you will be back home every time you have obtained new information about in-between steps. Each time you can adjust your estimate on how long it will still take based on actually experienced times of parts of your path. This is the main principle of \tsss{TD} learning: you do not have to wait until the end of a trial to make updates along your path.

\tsss{TD} methods learn their value estimates based on estimates of other values, which is called \emph{bootstrapping}. They have an advantage over \tsss{DP} in that they do not require a model of the \tsss{MDP}. Another advantage is that they are naturally implemented in an online, incremental fashion such that they can be easily used in various circumstances. No full sweeps through the full state space are needed; only along experienced paths values get updated, and updates are effected after each step.

\paragraph{TD(0).} TD($0$) is a member of the family of \tsss{TD} learning algorithms \cite{sutton:ltpbtmotd:88}. It solves the prediction problem, i.e. it estimates $V^\pi$ for some policy $\pi$, in an online, incremental fashion. $TD(0)$ can be used to evaluate a policy and works through the use of the following update rule\footnote{The learning parameter $\alpha$ should comply with some criteria on its value, and the way it is changed. In the algorithms in this section, one often chooses a small, fixed learning parameter, or it is decreased every iteration.}:
%
\begin{equation*}
  V_{k+1}(s) := V_k(s) + \alpha \biggl ( r + \gamma V_k(s^\prime) - V_k(s) \biggr )
\end{equation*}
%
\noindent where $\alpha \in [0,1]$ is the \emph{learning rate}, that determines by how much values get updated. This backup is performed after experiencing the transition from state $s$ to $s^\prime$ based on the action $a$, while receiving reward $r$. The difference with \tsss{DP} backups such as used in Equation~\ref{eq:bellman_update} is that the update is still done by using bootstrapping, but it is based on an \emph{observed} transition, i.e. it uses a \emph{sample backup} instead of a full backup. Only the value of one successor state is used, instead of a weighted average of all possible successor states. When using the value function $V^\pi$ for action selection, a model is needed to compute an expected value over all action outcomes (e.g. see Equation~\ref{eq:actionselectionV}).

The learning rate $\alpha$ has to be decreased appropriately for learning to converge. Sometimes the learning rate can be defined for states separately as in $\alpha(s)$, in which case it can be dependent on how often the state is visited. The next two algorithms learn $Q$-functions directly from samples, removing the need for a transition model for action selection.

%**********************************************************************************************
%* Q-learning
%*
%*
%*
%**********************************************************************************************

\paragraph{$Q$-learning.}

\begin{algorithm}[t]
\caption{ \label{alg:qlearning} $Q$-Learning \protect\cite{watkins:ql:92}}
\begin{algorithmic}
    \REQUIRE discount factor $\gamma$, learning parameter $\alpha$\\
    \STATE initialize $Q$ arbitrarily (e.g. $Q(s,a)=0, \forall s \in S, \forall a \in A$ )\\
    \FOR{\textbf{each} episode}
        \STATE $s$ is initialized as the \emph{starting} state\\
        \REPEAT
            \STATE choose an action $a \in A(s)$ based on an exploration strategy\\
            \STATE perform action $a$
            \STATE observe the new state $s^\prime$ and received reward $r$\\
            \STATE $Q(s,a) := Q(s,a) + \alpha \biggl ( r + \gamma \cdot \max_{ a^\prime \in A(s^\prime)} Q(s^\prime, a^\prime) - Q(s,a) \biggr )$\\
            \STATE $s := s^\prime$\\
        \UNTIL{$s^\prime$ is a goal state}
    \ENDFOR
\end{algorithmic}
\end{algorithm}

One of the most basic and popular methods to estimate $Q$-value functions in a model-free fashion is the $Q$-learning algorithm \cite{watkins:lfdr:89, watkins:ql:92}, see Algorithm~\ref{alg:qlearning}.

The basic idea in $Q$-learning is to incrementally estimate $Q$-values for actions, based on feedback (i.e. rewards) and the agent's $Q$-value function. The update rule is a variation on the theme of \tsss{TD} learning, using $Q$-values and a built-in $\max$-operator over the $Q$-values of the next state in order to update $Q_t$ into $Q_{t+1}$:
%
\begin{equation}
\label{eq:qlearningrule}
  Q_{k+1}(s_t,a_t) = Q_k(s_t,a_t) + \alpha \biggl ( r_t + \gamma
     \max_a Q_k(s_{t+1},a) - Q_k(s_t,a_t) \biggr )
\end{equation}
%
\noindent The agent makes a step in the environment from state $s_t$ to $s_{t+1}$ using action $a_t$ while receiving reward $r_t$. The update takes place on the $Q$-value of action $a_t$ in the state $s_t$ from which this action was executed.

Q-learning is exploration-insensitive. It means that it will converge to the optimal policy regardless of the exploration policy being followed, under the assumption that each state-action pair is visited an infinite number of times, and the learning parameter $\alpha$ is decreased appropriately \cite{watkins:ql:92, bertsekas:ndp:96}.


%**********************************************************************************************
%* SARSA
%*
%*
%*
%**********************************************************************************************

\paragraph{\tsss{SARSA}.} $Q$-learning is an \emph{off-policy} learning algorithm, which means that while following some exploration policy $\pi$, it aims at estimating the optimal policy $\pi^*$. A related \emph{on-policy} algorithm that learns the $Q$-value function for the policy the agent is actually executing is the \tsss{SARSA} \cite{rummery:olqlucs:94, rummery:pswrl:95, sutton:girl:96} algorithm, which stands for \textbf{S}tate--\textbf{A}ction--\textbf{R}eward--\textbf{S}tate--\textbf{A}action. It uses the following update rule:
%
\begin{equation}
\label{eq:sarsalearningrule}
  Q_{t+1}(s_t,a_t) = Q_t(s_t,a_t) + \alpha \biggl ( r_t + \gamma
     Q_t(s_{t+1},a_{t+1}) - Q_t(s_t,a_t) \biggr )
\end{equation}
%
\noindent where the action $a_{t+1}$ is the action that is executed by the current policy for state $s_{t+1}$. Note that the $\max$-operator in $Q$-learning is replaced by the estimate of the value of the next action according to the policy. This learning algorithm will still converge in the limit to the optimal value function (and policy) under the condition that all states and actions are tried infinitely often and the policy converges in the limit to the greedy policy, i.e. such that exploration does not occur anymore. \tsss{SARSA} is especially useful in non-stationary environments. In these situations one will never reach an optimal policy. It is also useful if \emph{function approximation} is used, because off-policy methods can diverge when this is used. However, off-policy methods are needed in many situations such as in learning using hierarchically structured policies.

%**********************************************************************************************
%* Actor-Critic
%*
%*
%*
%**********************************************************************************************

\paragraph{Actor-Critic Learning.} Another class of algorithms that precede $Q$-learning and \tsss{SARSA} are \emph{actor--critic} methods \cite{witten:aaocfdtme:77, barto:netcsdlcp:83, konda:aca:03}, which learn on-policy. This branch of \tsss{TD} methods keeps a \emph{separate} policy independent of the value function. The policy is called the \emph{actor} and the value function the \emph{critic}. The critic -- typically a state-value function -- evaluates, or: criticizes, the actions executed by the actor. After action selection, the critic evaluates the action using the \tsss{TD}-error:
%
\begin{equation*}
  \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)
\end{equation*}
%
\noindent The purpose of this error is to strengthen or weaken the selection of this action in this state. A \emph{preference} for an action $a$ in some state $s$ can be represented as $p(s,a)$ such that this preference can be modified using:
%
\begin{equation*}
  p(s_t,a_t) := p(s_t,a_t) + \beta \delta_t
\end{equation*}
%
\noindent where a parameter $\beta$ determines the size of the update. There are other versions of actor--critic methods, differing mainly in how preferences are changed, or experience is used (for example using \emph{eligibility traces}, see next section). An advantage of having separate policy representation is that if there are many actions, or when the action space is continuous, there is no need to consider all actions' $Q$-values in order to select one of them. A second advantage is that they can learn \emph{stochastic} policies naturally. Furthermore, a priori knowledge about policy constraints can be used, e.g. see \cite{framling:bmmfgebpek:05}.

%**********************************************************************************************
%* Average Reward
%*
%*
%*
%**********************************************************************************************

\paragraph{Average Reward Temporal Difference Learning.} We have explained $Q$-learning and related algorithms in the context of discounted, infinite-horizon \tsss{MDP}s. $Q$-learning can also be adapted to the average-reward framework, for example in the $R$-learning algorithm \cite{schwartz:arlmfmur:93}. Other extensions of algorithms to the average reward framework exist (see \cite{mahadevan:arrl:96} for an overview).

%**********************************************************************************************
%* Monte Carlo Techniques
%*
%*
%*
%**********************************************************************************************

\subsection{Monte Carlo Methods}
Other algorithms that use more \emph{unbiased} estimates are \emph{Monte Carlo} (\tsss{MC}) techniques. They keep frequency counts of transitions and rewards and base their values on these estimates. \tsss{MC} methods only require samples to estimate average sample returns. For example, in \tsss{MC} policy evaluation, for each state $s \in S$ all returns obtained from $s$ are kept and the value of a state $s \in S$ is just their average. In other words, \tsss{MC} algorithms treat the long-term reward as a random variable and take as its estimate the sampled mean. In contrast with one-step \tsss{TD} methods, \tsss{MC} estimates values based on \emph{averaging sample returns} observed during interaction. Especially for episodic tasks this can be very useful, because samples from complete returns can be obtained. One way of using \tsss{MC} is by using it for the evaluation step in policy iteration. However, because the sampling is dependent on the current policy $\pi$, only returns for actions suggested by $\pi$ are evaluated. Thus, exploration is of key importance here, just as in other model-free methods.

A distinction can be made between \emph{every-visit} \tsss{MC}, which averages over all \emph{visits} of a state $s \in S$ in all episodes, and \emph{first-visit} \tsss{MC}, which averages over just the returns obtained from the first visit to a state $s \in S$ for all episodes. Both variants will converge to $V^\pi$ for the current policy $\pi$ over time. \tsss{MC} methods can also be applied to the problem of estimating action values. One way of ensuring enough exploration is to use \emph{exploring starts}, i.e. each state-action pair has a non-zero probability of being selected as the initial pair. \tsss{MC} methods can be used for both on-policy and off-policy control, and the general pattern complies with the generalized policy iteration procedure. The fact that \tsss{MC} methods do not \emph{bootstrap} makes them less dependent on the \emph{Markov assumption}. \tsss{TD} methods too focus on \emph{sampled} experience, although they do use bootstrapping.

%**********************************************************************************************
%* Learning a Model
%*
%*
%*
%**********************************************************************************************

\paragraph{Learning a Model.} We have described \tsss{MC} methods in the context of learning value functions. Methods similar to \tsss{MC} can also be used to estimate a \emph{model} of the \tsss{MDP}. An average over sample transition probabilities experienced during interaction can be used to gradually estimate transition probabilities. The same can be done for \emph{immediate} rewards. \emph{Indirect} \tsss{RL} algorithms make use of this to strike a balance between model-based and model-free learning. They are essentially model-free, but learn a transition and reward model in parallel with model-free \tsss{RL}, and use this model to do more efficient value function learning (see also the next section). An example of this is the \tsss{DYNA} model \cite{sutton:dyna:91}. Another method that often employs model learning is \emph{prioritized sweeping} \cite{moore:ps:93}. Learning a model can also be very useful to learn in continuous spaces where the transition model is defined over a discretized version of the underlying (infinite) state space \cite{grossmann:assqamtrlucnn:00}.

%**********************************************************************************************
%* Relations with Dynamic Programming Approaches
%*
%*
%*
%**********************************************************************************************

\paragraph{Relations with Dynamic Programming.} The methods in this section solve essentially similar problems as \tsss{DP} techniques. \tsss{RL} approaches can be seen as \emph{asynchronous} \tsss{DP}. There are some important differences in both approaches though.

\tsss{RL} approaches avoid the exhaustive sweeps of \tsss{DP} by restricting computation on, or in the neighborhood of, sampled trajectories, either real or simulated. This can exploit situations in which many states have low probabilities of occurring in actual trajectories. The backups used in \tsss{DP} are simplified by using sampling. Instead of generating and evaluating all of a state's possible immediate successors, the estimate of a backup's effect is done by sampling from the appropriate distribution. \tsss{MC} methods use this to base their estimates completely on the sample returns, without bootstrapping using values of other, sampled, states. Furthermore, the focus on learning (action) value functions in \tsss{RL} is easily amenable to \emph{function approximation} approaches. Representing value functions and or policies can be done more compactly than lookup-table representations by using \emph{numeric regression algorithms} without breaking the standard \tsss{RL} interaction process; one can just feed the update values into a regression engine.

An interesting point here is the similarity between $Q$-learning and \emph{value iteration} on the one hand and \tsss{SARSA} and \emph{policy iteration} on the other hand. In the first two methods, the updates immediately combine policy evaluation and improvement into one step by using the $\max$-operator. In contrast, the second two methods separate evaluation and improvement of the policy. In this respect, value iteration can be considered as off-policy because it aims at directly estimating $V^*$ whereas policy iteration estimates values for the current policy and is on-policy. However, in the model-based setting the distinction is only superficial, because instead of samples that can be influenced by an on-policy distribution, a model is available such that the distribution over states and rewards is known.

%**********************************************************************************************
%* Exploration
%*
%*
%*
%**********************************************************************************************

\subsection{Efficient Exploration and Value Updating}
\label{sec:efficientRL}

The methods in the previous section have shown that both prediction and control can be learned using samples from interaction with the environment, without having access to a model of the \tsss{MDP}. One problem with these methods is that they often need a large number of experiences to converge. In this section we describe a number of extensions used to speed up learning. One direction for improvement lies in the exploration. One can -- in principle -- use \tsss{MC} sampling until one knows everything about the \tsss{MDP} but this simply takes too long. Using more information enables more focused exploration procedures to generate experience more efficiently. Another direction is to put more efforts in using the experience for updating multiple values of the value function on each step. Improving exploration generates \emph{better samples}, whereas improving updates will squeeze \emph{more information} from samples.

%**********************************************************************************************
%* Efficient Exploration
%*
%*
%*
%**********************************************************************************************

\paragraph{Efficient Exploration.} We have already encountered $\epsilon$-greedy and \emph{Boltzmann} exploration. Although commonly used, these are relatively simple \emph{undirected} exploration methods. They are mainly driven by \emph{randomness}. In addition, they are \emph{stateless}, i.e. the exploration is driven without knowing which areas of the state space have been explored so far.

A large class of \emph{directed} methods for exploration have been proposed in the literature that use additional information about the learning process. The focus of these methods is to do more uniform exploration of the state space and to balance the relative benefits of discovering new information relative to exploiting current knowledge. Most methods use or learn a model of the \tsss{MDP} in parallel with \tsss{RL}. In addition they learn an \emph{exploration value function}.

Several options for directed exploration are available. One distinction between methods is whether to
work \emph{locally} (e.g. exploration of individual state-action pairs) or \emph{globally} by considering information about parts or the complete state-space when making a decision to explore. Furthermore, there are several other classes of exploration algorithms.

\emph{Counter-based} or \emph{recency-based} methods keep records of how often, or how long ago, a state-action pair has been visited. \emph{Error-based} methods, of which \emph{prioritized sweeping} \cite{moore:ps:93} is one example, use an exploration bonus based on the error in the value of states. Other methods base exploration on the \emph{uncertainty} about the value of a state, or the \emph{confidence} about the state's current value. They decide whether to explore by calculating the probability that an explorative action will encover a larger reward than already found. The \emph{interval estimation} (\tsss{IE}) method \cite{kaelbling:lies:93} is an example of this kind of methods. \tsss{IE} uses a statistical model to measure the degree of uncertainty of each $Q(s,a)$-value. An upper bound can be calculated on the likely value of each $Q$-value, and the action with the highest upper bound is taken. If the action taken happens to be a poor choice, the upper bound will be decreased when the statistical model is updated. Good actions will continue to have a high upper bound and will be chosen often. In contrast to counter- and recency-based exploration, \tsss{IE} is concerned with \emph{action exploration} and not with \emph{state space} exploration. \cite{wiering:eierl:99} (see also \cite{wiering:embe:98}) introduced an extension to model-based \tsss{RL} in the \emph{model-based interval estimation} algorithm in which the same idea is used for estimates of transition probabilities.

Another recent method that deals explicitly with the exploration-exploitation trade-off is the $E^3$ method \cite{kearns:norlipt:98}. $E^3$ stands for \emph{explicit exploration and exploitation}. It learns by updating a model of the environment by collecting statistics. The state space is divided into \emph{known} and \emph{unknown} parts. On every step a decision is made whether the known part contains sufficient opportunities for getting rewards or whether the unknown part should be explored to obtain possibly more reward. An important aspect of this algorithm is that it was the first general near-optimal (tabular) \tsss{RL} algorithm with provable bounds on computation time. The approach was extended in \cite{brafman:rmax:02} into the more general algorithm \tsss{R-MAX}. It too provides a polynomial bound on computation time for reaching near-optimal policies. As a last example, \cite{ratitch:ocomdparlild:05} present an approach for efficient, directed exploration based on more sophisticated characteristics of the \tsss{MDP} such as an \emph{entropy} measure over state transitions. An interesting feature of this approach is that these characteristics can be computed \emph{before} learning and be used in combination with other exploration methods, thereby improving their behavior.

For a more detailed coverage of exploration strategies we refer the reader to \cite{ratitch:ocomdparlild:05} and \cite{wiering:eierl:99}.

%**********************************************************************************************
%* Guidance and Shaping
%*
%*
%*
%**********************************************************************************************

\paragraph{Guidance and Shaping.} Exploration methods can be used to speed up learning and focus attention to relevant areas in the state space. The exploration methods mainly use statistics derived from the problem before or during learning. However, sometimes more information is available that can be used to \emph{guide} the learner. For example, if a reasonable policy for a domain is available, it can be used to generate more useful learning samples than (random) exploration could do. In fact, humans are usually very bad in specifying optimal policies, but considerably good at specifying reasonable ones\footnote{Quote taken from the invited talk by Leslie Kaelbling at the European Workshop on Reinforcement Learning \tsss{EWRL}, in Utrecht $2001$.}.

The work in \emph{behavioral cloning} \cite{bain:affbc:95} takes an extreme point on the guidance spectrum in that the goal is to \emph{replicate} example behavior from expert traces, i.e. to \emph{clone} this \emph{behavior}. This type of guidance moves learning more in the direction of \emph{supervised} learning. Another way to help the agent is by \emph{shaping} \cite{mataric:rffal:94, dorigo:rs:97, ng:piurt:99}. Shaping pushes the reward closer to the subgoals of behavior, and thus encourages the agent to incrementally improve its behavior by searching the policy space more effectively. This is also related to the general issue of giving rewards to appropriate subgoals, and the gradual increase in difficulty of tasks. The agent can be trained on increasingly more difficult problems, which can also be considered as a form of guidance.

Various other mechanisms can be used to provide guidance to \tsss{RL} algorithms, such as decompositions \cite{dixon:ipkapliirla:00}, heuristic rules for better exploration \cite{framling:bmmfgebpek:05} and various types of \emph{transfer} in which knowledge learned in one problem is transferred to other, related problems, e.g. see \cite{konidaris:afftirl:06}.


%**********************************************************************************************
%* Eligibility Traces
%*
%*
%*
%**********************************************************************************************

\paragraph{Eligibility Traces.} In \tsss{MC} methods, the updates are based on the entire sequence of observed rewards until the end of an episode. In \tsss{TD} methods, the estimates are based on the samples of immediate rewards and the next states. An intermediate approach is to use the $n$-\emph{step-truncated-return} $R^{(n)}_t$, obtained from a whole sequence of returns:
%
\begin{equation*}
  R^{(n)}_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots + \gamma^n V_t(s_{t+n})
\end{equation*}
%
\noindent With this, one can go to the approach of computing the updates of values based on several $n$-step returns. The family of \tsss{TD}$(\lambda)$, with $0 \leq \lambda \leq 1$, combines $n$-step returns weighted proportionally to $\lambda^{n-1}$.

The problem with this is that we would have to wait indefinitely to compute $R^{(\infty)}_t$. This view is useful for theoretical analysis and understanding of $n$-step backups. It is called the \emph{forward view of the \tsss{TD}$(\lambda)$ algorithm}. However, the usual way to implement this kind of updates is called the \emph{backward view of the \tsss{TD}$(\lambda)$ algorithm} and is done by using \emph{eligibility traces}, which is an incremental implementation of the same idea.

Eligibility traces are a way to perform $n$-step backups in an elegant way. For each state $s \in S$, an eligibility $e_t(s)$ is kept in memory. They are initialized at $0$ and incremented every time according to:
%
\begin{equation*}
  e_t(s) =
  \begin{cases}
    \gamma \lambda e_{t-1}(s) & \text{if}\ s \neq s_t \\
    \gamma \lambda e_{t-1}(s) + 1 & \text{if}\ s = s_t
  \end{cases}
\end{equation*}
%
\noindent where $\lambda$ is the \emph{trace decay parameter}. The trace for each state is increased every time that state is visited and decreases exponentially otherwise. Now $\delta_t$ is the \emph{temporal difference} error at stage $t$:
%
\begin{equation*}
  \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)
\end{equation*}
%
\noindent On every step, all states are updated in proportion to their eligibility traces as in:
%
\begin{equation*}
  V(s) := V(s) + \alpha \delta_t e_t(s)
\end{equation*}
%
\noindent The forward and backward view on eligibility traces can be proved equivalent \cite{sutton:rlai:98}. For $\lambda = 1$, \tsss{TD}($\lambda$) is essentially the same as \tsss{MC}, because it considers the complete return, and for $\lambda = 0$, \tsss{TD}($\lambda$) uses just the immediate return as in all one-step \tsss{RL} algorithms. Eligibility traces are a general mechanism to learn from $n$-step returns. They can be combined with all of the model-free methods we have described in the previous section. \cite{watkins:lfdr:89} combined $Q$-learning with eligibility traces in the $Q(\lambda)$-algorithm. \cite{peng:imsq:96} proposed a similar algorithm, and \cite{wiering:foq:98} and \cite{reynolds:rlwe:02} both proposed efficient versions of $Q(\lambda)$. The problem with combining eligibility traces with learning \emph{control} is special care has to be taken in case of \emph{exploratory} actions, which can break the intended meaning of the $n$-step return for the current policy that is followed. In \cite{watkins:lfdr:89}'s version, eligibility traces are reset every time an exploratory action is taken. \cite{peng:imsq:96}'s version is, in that respect more efficient, in that traces do not have to be set to zero every time. \tsss{SARSA}($\lambda$) \cite{sutton:rlai:98} is more safe in this respect, because action selection is on-policy. Another recent on-policy learning algorithm is the \tsss{QV}($\lambda$) algorithm by \cite{wiering:qvl:05}. In \tsss{QV}($\lambda$)-learning two value functions are learned; \tsss{TD}($\lambda$) is used for learning a state value function $V$ and one-step $Q$-learning is used for learning a state-action value function, based on $V$.

%**********************************************************************************************
%* Dyna stuff
%*
%*
%*
%**********************************************************************************************

\paragraph{Learning and Using a Model: Learning and Planning.} Even though \tsss{RL} methods can function without a model of the \tsss{MDP}, such a model can be useful to speed up learning, or bias exploration. A learned model can also be useful to do more efficient value \emph{updating}. A general guideline is when experience is costly, it pays off to learn a model. In \tsss{RL} model-learning is usually targeted at the specific learning task defined by the \tsss{MDP} , i.e. determined by the rewards and the goal. In general, learning a model is most often useful because it gives knowledge about the \emph{dynamics} of the environment, such that it can be used for other tasks too (see \cite{drescher:mum:91} for extensive elaboration on this point).

\begin{algorithm}[t]
\caption{ \label{alg:dynaq} Dyna-Q \protect\cite{sutton:rlai:98}}
\begin{algorithmic}
    \REQUIRE initialize Q and Model arbitrarily\\
    \REPEAT
        \STATE $s \in S$ is the start state \\
        \STATE $a := \epsilon$-greedy$(s,Q)$\\
        \STATE update $Q$\\
        \STATE update Model\\
        \FOR{$i:=1$ \textbf{to} $n$}
          \STATE $s :=$ randomly selected observed state\\
          \STATE $a :=$ random, previously selected action from $s$\\
          \STATE update $Q$ using the model
        \ENDFOR
    \UNTIL{Sufficient Performance}
\end{algorithmic}
\end{algorithm}

The \tsss{DYNA} architecture \cite{sutton:iaflparbaadp:90, sutton:rlafa:91, sutton:dyna:91, sutton:rlai:98} is a simple way to use the model to amplify experiences. Algorithm~\ref{alg:dynaq} shows \tsss{DYNA}-$Q$ which combines $Q$-learning with planning. In a continuous loop, $Q$-learning is interleaved with series of extra updates using a model that is constantly updated too. \tsss{DYNA} needs less interactions with the environment, because it \emph{replays} experience to do more value updates.

A related method that makes more use of experience using a learned model is \emph{prioritized sweeping} (\tsss{PS}) \cite{moore:ps:93}. Instead of selecting states to be updated randomly (as in \tsss{DYNA}), \tsss{PS} prioritizes updates based on their change in values. Once a state is updated, the \tsss{PS} algortithm considers all states that can reach that state, by looking at the transition model, and sees whether these states will have to be updated as well. The order of the updates is determined by the size of the value updates. The general mechanism can be summarized as follows. In each step i) one remembers the old value of the current state, ii) one updates the state value with a full backup using the learned model, iii) one sets the priority of the current state to $0$, iv) one computes the change $\delta$ in value as the result of the backup, v) one uses this difference to modify \emph{predecessors} of the current state (determined by the model); all states leading to the current state get a priority update of $\delta \times T$. The number of value backups is a parameter to be set in the algorithm. Overall, \tsss{PS} focuses the backups to where they are expected to most quickly reduce the error. Another example of using planning in model-based \tsss{RL} is \cite{wiering:mbrlide:02}.

% BibTeX users please use
\bibliographystyle{spbasic}
\bibliography{mainbibrl}

\end{document}
