\chapter{Algoritmos de Reinforcement Learning}
\label{chap:Reinforcement_Learning}

\section{\textit{Markov Decision Processes}}

No \textit{Reinforcement Learning}, um agente toma as suas decisões em função dos sinais obtidos do ambiente, e que constituem o ``estado''. Um estado que contenha todas as informações do ambiente, é designado \textit{Markoviano}, ou como tendo a propriedade \textit{Markoviana}.\cite{RL_introduction}
Assumindo que, o número de estados são finitos, passamos a trabalhar em termos de probabilidades e somas, em vez de integrais e probabilidades densas. Se considerarmos como um ambiente geral irá responder num tempo $t+1$, a uma acção realizada em $t$, a resposta pode depender de tudo o que se passou anteriormente. Neste caso, a dinâmica pode ser definida da seguinte forma:
\begin{equation} \label{eq:markov_property}
\mathit{P_{r}\big\{s_{t+1}=s' , r_{t+1} = r\ \big|\ s_{t} , a_{t} , r_{t} , s_{t-1} , a_{t-1} , r_{t-1} ,\dots, r_{1} , s_{0} , a_{0}\big\},\ \forall\ s' , r , s\ e\ a}
\end{equation}
em que $r$ é a recompensa, $s$ o estado, $s'$ o próximo estado e $a$ a acção. Se o estado for \textit{Markoviano}, então a resposta do ambiente no tempo $t+1$ passa a depender apenas do estado e da acção em $t$. Neste caso, a dinâmica passa a ser definida por:
\begin{equation} \label{eq:markov_property2}
\mathit{P_{r}\big\{s_{t+1} = s' , r_{t+1} = r\ \big|\ s_{t} , a{t}\big\},\ \forall\ s' , r , s_{t}\ e\ a_{t}}
\end{equation}
Ou seja, um estado inicial é um estado \textit{Markoviano}, apenas se a equação \ref{eq:markov_property} for igual a \ref{eq:markov_property2} para todo o $s',r$ e contiver um historial dos valores, $s_{t} , a_{t} , r_{t} , s_{t-1} , a_{t-1}, r_{t-1} , \dots , r_{1} , s_{0} , a_{0}$. Neste caso, o ambiente e as tarefas também se designam como tendo a propriedade \textit{Markoviana}. No \textit{reinforcement learning}, a propriedade \textit{Markoviana} é importante, porque as decisões e valores são assumidas apenas em função do estado actual.

Um processo \textit{Markoviano} é um processo estocástico, que satisfaz a propriedade \textit{Markoviana}. E uma tarefa de \textit{Reinforcement Learning} que contenha processos \textit{Markovianos}, em tempos discretos, é designada por MDP (\textit{Markov Decision Process}). No entanto, mesmo que a informação do estado seja não-\textit{Markoviana}, continua a ser válido tratar o estado, no \textit{reinforcement learning}, como sendo uma aproximação ao estado \textit{Markoviano}. No caso de os estados e as acções serem finitas, então estamos na presença de um MDP finito. Para qualquer estado $s$ e acção $a$ a probabilidade de o próximo estado ser $s'$, designado por probabilidade de transição é dada por:
\begin{equation} \label{eq:mdp_1}
\mathit{\mathcal{P}_{s s'}^{a} = P_{r}\big\{s_{t+1} = s'\ \big|\ s_{t} = s , a_{t} = a\big\}}
\end{equation}
De igual modo, para um dado estado $s$, acção $a$ e próximo estado $s'$, o valor esperado para a recompensa é dado por:
\begin{equation} \label{eq:mdp_2}
\mathit{\mathcal{R}_{s s'}^{a} = E\big\{r_{t+1}\ \big|\ s_{t} = s , a_{t} = a , s_{t+1} = s'\big\}}
\end{equation}
Tanto a probabilidade de transição $\mathit{\mathcal{P}_{s s'}^{a}}$ como a recompensa esperada $\mathit{\mathcal{R}_{s s'}^{a}}$ especificam os aspectos mais importantes da dinâmica de um MDP finito.\cite{RL_introduction}


\section{Funções de Valor}

Quase todos os algoritmos de \textit{reinforcement learning} são baseados na estimativa de funções de valor. As funções de valor são funções de estados, ou pares de estado-acção, que estimam o valor, que pode ser esperado de futuras recompensas, por um agente estar num dado estado, ou por um agente realizar uma acção num dado estado. As funções de valor são definidas adequadamente com as políticas em causa.\cite{RL_introduction}

Uma política $\pi$, de um agente, é um mapeamento de cada estado $s \in \mathcal{S}$ e acção $a \in \mathcal{A}(s)$ para a probabilidade $\pi(s , a)$ de um agente escolher uma acção $a$, possível, estando num estado $s$. Para MDPs, o valor de um estado $s$, regido por uma dada política $\pi$, designado por $\mathit{V^{\pi}(s)}$ ou função de valor de estado para a política $\pi$, é dado por:
\begin{equation} \label{eq:val_fun1}
\mathit{V^{\pi}(s) = E_{\pi}\big\{R_{t}\ \big|\ s_{t} = s\big\} = E_{\pi}\bigg\{\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \bigg| s_{t} = s\biggr\}}
\end{equation}
em que, $\mathit{E_{\pi}\{\}}$ representa a esperança de um agente ter seguido a política $\pi$ num tempo $t$ e $\gamma$ ($0<\gamma<1$, utilizando-se, normalmente, valores próximos de 1) é designado por factor de desconto.

Da mesma maneira, o valor de executar uma acção $a$ num estado $s$, através de uma política $\pi$, designado por $\mathit{Q^{\pi}(s , a)}$ ou função de valor de estado-acção para a política $\pi$, é dado por:
\begin{equation} \label{eq:val_fun2}
\mathit{Q^{\pi}(s , a) = E_{\pi}\big\{R_{t}\ \big|\ s_{t} = s , a_{t} = a\big\} = E_{\pi}\bigg\{\sum_{k = 0}^{\infty} \gamma^{k} r_{t+k+1} \bigg| s_{t} = s , a_{t} = a\bigg\}}
\end{equation}

No \textit{reinforcement learning}, as funções de valor satisfazem relações recursivas particulares. Para qualquer política $\pi$ e estado $s$, a seguinte condição mantém a coerência entre o valor do estado $s$ e o valor dos estados seguinte:
\begin{IEEEeqnarray}{r/C/l} \label{eq:belman}
V^{\pi}(s) & = & E_{\pi}\big\{R_{t}\ \big|\ s_{t} = s\big\}  \nonumber\\ & = & E_{\pi}\bigg\{\sum_{k=0}^{\infty}\gamma^{k}r_{t+k+1}\ \bigg|\ s_{t} = s\bigg\} \nonumber\\ & = & E_{\pi}\bigg\{r_{t+1}+\gamma\sum_{k = 0}^{\infty}\gamma^{k}r_{t+k+2}\ \bigg|\ s_{t} = s\bigg\} \nonumber\\ & = & \sum_{a} \pi(s , a)\sum_{s'} \mathcal{P}_{s s'}^{a}\Bigg[ \mathcal{R}_{s s'}^{a}+\gamma E_{\pi}\bigg\{ \sum_{k = 0}^{\infty}\gamma^{k}r_{t+k+2}\ \bigg|\ s_{t+1} = s' \bigg\} \Bigg] \nonumber\\ & = & \sum_{a}\pi(s , a)\sum_{s'}^{}\mathcal{P}_{s s'}^{a}\bigg[\mathcal{R}_{s s'}^{a}+\gamma V^{\pi}(s')\bigg],\ \forall\ a \in \mathcal{A}(s), s \in \mathcal{S}
\end{IEEEeqnarray}
Esta equação (eq. \ref{eq:belman}) representa a relação entre o valor de um estado e o valor do estado seguinte, designada por equação de \textit{Bellman}, cuja única solução é $V^{\pi}$.\cite{RL_introduction}

Encontrar uma política, cujas acções devolvam as melhores recompensas, designada por $V^{*}(s)$, é o objectivo de uma tarefa de \textit{reinforcement learning}. Uma política $\pi$ é melhor que uma política $\pi'$ se a sua recompensa esperada for maior, ou igual, que a recompensa esperada para $\pi'$. A política que devolva a maior recompensa é designada por $\pi^{*}$, ou política óptima. Para MDPs finitos, a função de valor óptima é definida por:
\begin{equation} \label{eq:opt_val}
\mathit{V^{*}(s) = \max_{\pi} V^{\pi}(s),\ \forall\ s \in \mathcal{S}}
\end{equation}
Existe pelo menos uma política óptima $\pi^{*}$, no entanto, podem existir mais do que uma. Essas políticas, para além de partilharem as mesmas funções de estado óptimas $V^{*}$, partilham, também, as funções de estado-acção óptimas. A função de estado óptima, ou $Q^{*}$, é definida por:
\begin{equation} \label{eq:opt_valQ}
\mathit{Q^{*}(s,a) = \max_{\pi} Q^{\pi}(s,a),\ \forall\ s \in \mathcal{S}, a \in \mathcal{A}(s)}
\end{equation}
Uma vez que, para cada par estado-acção, esta função devolve a recompensa esperada de executar uma acção $a$ num estado $s$, seguindo uma política óptima $\pi^{*}$, então é possível definir $Q^{*}$ em função de $V^{*}$:
\begin{equation} \label{eq:opt_valQ2}
\mathit{Q^{*}(s,a) = E\big\{ r_{t+1} + \gamma V^{*}(s_{t+1})\ \big|\ s_{t} = s, a_{t} = a \big\}}
\end{equation}
Sendo $V^{*}$ a função de valor para uma política, esta deve satisfazer a condição de coerência, dada pela equação de \textit{Bellman} (eq. \ref{eq:belman}). Esta condição de coerência, designada por equação de \textit{Bellman} para $V^{*}$ ou equação óptima de \textit{Bellman}, pode ser escrita, sem referenciar qualquer tipo específico de política, da seguinte forma:
\begin{IEEEeqnarray}{r/C/l} \label{eq:opt_Bellman}
V^{*}(s) & = & \max_{a \in \mathcal{A}(s)} Q^{\pi^{*}}(s , a) \nonumber\\ & = & \max_{a} E_{\pi^{*}} \big\{R_{t}\ |\ s_{t} = s , a_{t} = a \big\} \nonumber\\ & = & \max_{a} E_{\pi^{*}} \bigg\{\sum_{k = 0}^{\infty} \gamma^{k} r_{t+k+1}\ \bigg|\ s_{t} = s , a_{t} = a\bigg\} \nonumber\\ & = & \max_{a} E_{\pi^{*}} \bigg\{r_{t+1} + \gamma \sum_{k = 0}^{\infty} \gamma^{k} r_{t+k+2}\ \bigg|\ s_{t} = s , a_{t} = a\bigg\} \nonumber\\ & = & \max_{a} E \big\{ r_{t+1} + \gamma V^{*}(s_{t}+1)\ \big|\ s_{t} = s , a_{t} = a \big\} \\ \label{eq:opt_Bellman2} & = & \max_{a \in \mathcal{A}(s)} \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[ \mathcal{R}_{s s'}^{a} + \gamma V^{*}(s') \Big]
\end{IEEEeqnarray}
As duas últimas equações (\ref{eq:opt_Bellman} e \ref{eq:opt_Bellman2}) são duas formas da equação óptima de \textit{Bellman}. Basicamente, a equação óptima de \textit{Bellman} traduz o facto de que um valor de um estado, numa política óptima, deve igualar a recompensa esperada para a melhor das acções para aquele estado.\cite{RL_introduction} De igual forma, a equação óptima de \textit{Bellman} para $Q^{*}$ é dada por:
\begin{IEEEeqnarray}{r/C/l} \label{eq:opt_BellmanQ}
Q^{*}(s , a) & = & E \Big\{ r_{t+1} + \gamma \max_{a'} Q^{*}(s_{t+1} , a')\ \Big|\ s_{t} = s , a_{t} = a \Big\} \nonumber\\ & = & \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[ \mathcal{R}_{s s'}^{a} + \gamma \max_{a'} Q^{*}(s' , a') \Big]
\end{IEEEeqnarray}

\pagebreak

A equação óptima de \textit{Bellman} tem uma única solução, para MDPs finitas, independente da política. Na verdade, a equação óptima de \textit{Bellman} é um sistema de equações, um para cada estado. Assim, para $n$ estados, existem $n$ equações com $n$ incógnitas. É possível resolver o sistema de equações para $V^{*}$, e consequentemente para $Q^{*}$, se a dinâmica do meio ($\mathcal{P}_{s s'}^{a} , \mathcal{R}_{s s'}^{a}$) for conhecida.

Uma vez tendo $V^{*}$, é fácil determinar a política óptima. Basicamente, a política óptima é aquela que é \textit{greedy} (ávida) em relação à função de valor óptima $V^{*}$. Tendo $V^{*}$ em conta as recompensas para todos os comportamentos futuros, se $V^{*}$ for usada para avaliar as consequências das acções a curto prazo, uma política \textit{greedy} (ávida) é óptima a longo prazo. Por outras palavras, a recompensa a longo prazo é transformada num valor que está disponível imediatamente para cada estado e, portanto, uma procura no passo seguinte contém as acções óptimas a longo prazo.

Escolher as acções óptimas tendo $Q^{*}$ é ainda mais simples, pois, não é necessário realizar uma procura no passo seguinte para cada estado, basta simplesmente procurar a acção que maximiza $Q^{*}(s , a)$. A função de valor de estado-acção dá-nos a recompensa esperada a longo prazo na forma de um valor, imediatamente disponível para cada par estado-acção. A função de valor, por representar pares de estado-acção, em vez de apenas estados, permite escolher as acções óptimas sem nada conhecer sobre a dinâmica do ambiente, isto é, sem conhecer nada sobre os possíveis estados futuros e os seus valores.\cite{RL_introduction}

\section{Métodos \textit{Model-free}}

Como já foi referido anteriormente, existem dois tipos básicos de \textit{reinforcement learning}: o \textit{model-based} e o \textit{model-free}. Serão descritos alguns métodos de cada um destes de tipos, sendo dada mais relevância aos métodos \textit{model-free}, uma vez que este tipo é mais adequado para pequenos robôs, pelo facto de não ser necessário um modelo do ambiente. Nesta secção, são descritos alguns métodos \textit{model-free} de \textit{reinforcement learning}, nomeadamente o \textit{Monte Carlo Control},  e três tipos de métodos de diferença temporal (TD - \textit{Temporal-Difference}): o \textit{Q-learning}, SARSA (\textit{State-Action-Reward-State-Action}) e o TD(0).

\subsection{\textit{Monte Carlo Control}}

Os métodos \textit{Monte Carlo} são modos de resolver problemas de \textit{reinforcement learning}, baseando-se na média de recompensas obtidas, nos quais, apenas são necessárias sequências de estados, acções e recompensas, através da interacção de um agente com o ambiente para aprender.

No método \textit{Monte Carlo Control}, a função de valor é ciclicamente alterada, por forma a aproximar a função de valor à política utilizada e a política é ciclicamente melhorada em função da função valor actual.\cite{RL_introduction}
Similarmente à iteração de política, realizam-se passos de avaliação de política e passos de aperfeiçoamento de política alternadamente, iniciando-se com uma política aleatória $\pi_{0}$ e terminando com uma política óptima $\pi^{*}$ e uma função de valor de estado-acção óptima $Q^{*}$, da seguinte forma:
\begin{equation} \label{eq:MontCarlo_iteration}
\mathit{\pi_{0} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} Q^{\pi_{0}} \stackrel{\scriptscriptstyle{I}}{\longrightarrow} \pi_{1} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} Q^{\pi_{1}} \cdots \stackrel{\scriptscriptstyle{I}}{\longrightarrow} \pi^{*} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} Q^{*},}
\end{equation}

\pagebreak

Onde $\stackrel{\scriptscriptstyle{E}}{\longrightarrow}$ representa uma avaliação de política completa e $\stackrel{\scriptscriptstyle{I}}{\longrightarrow}$ representa um aperfeiçoamento de política completo. A avaliação de política resume-se ao cálculo da função de valor de estado $V^{\pi}$ para uma política $\pi$, recorrendo à equação \ref{eq:opt_val}, e é definida por:
\begin{IEEEeqnarray}{r/C/l} \label{eq:pol_evaluation}
V^{\pi}(s) & = & E_{\pi} \big\{ r_{t+1} + \gamma r_{t+2} + \gamma^{2} r_{t+3} + \dots\ \big|\ s_{t} = s \big\} \nonumber\\ & = & E_{\pi} \big\{ r_{t+1} + \gamma V^{\pi}(s_{t+1})\ \big|\ s_{t} = s \big\} ,\ \forall\ s \in \mathcal{S}
\end{IEEEeqnarray}
em que $\pi(s , a)$ é a probabilidade de executar uma acção $a$ num estado $s$ seguindo a política $\pi$. O aperfeiçoamento de política consiste no cálculo do valor de estado-acção de escolher uma acção $a$ num estado $s$ seguindo uma política $\pi$:
\begin{equation} \label{eq:pol_improvement}
\mathit{Q^{\pi}(s,a) = E_{\pi}\big\{ r_{t+1} + \gamma V^{\pi}(s_{t+1})\ \big|\ s_{t} = s , a_{t} = a \big\}}
\end{equation}
e comparar esse valor com o valor de estado, para verificar se é ou não melhor mudar para uma nova política nesse estado $s$. Se, para um par de políticas $\pi$ e $\pi'$, se verificar que:
\begin{equation} \label{eq:improvment_test}
\mathit{Q^{\pi}(s , \pi'(s)) \geq V^{\pi}(s),\ \forall\ s \in \mathcal{S}}
\end{equation}
então a política $\pi'$ é tão boa ou melhor que a política $\pi$. Por outras palavras, a recompensa esperada por executar $a \neq \pi$ num estado $s$, é maior ou igual do que seguir a política $\pi$. Assim, para qualquer função de valor de estado-acção $Q$, a política \textit{greedy} correspondente é dada por:
\begin{equation} \label{eq:MC_greedy_policy}
\mathit{\pi(s) = \mathrm{arg}\max_{a} Q(s,a)},\ \forall\ s \in \mathcal{S}
\end{equation}

O algoritmo mais simples do método \textit{Monte Carlo} é o \textit{Monte Carlo ES} (\textit{Monte Carlo} com exploração inicial), em que, após cada episódio, é obtida uma recompensa, que é usada para a avaliação de política e depois é realizada o aperfeiçoamento de política para todos os estados visitados no episódio. Este algoritmo é descrito na tabela \ref{tab:Monte_Carlo_ES}.

\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do \textit{Monte Carlo ES}, um algoritmo do método \textit{Monte Carlo Control} que usa a exploração inicial.\cite{RL_introduction}}
        \label{tab:Monte_Carlo_ES}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar, $\forall\ s \in \mathcal{S}, a \in \mathcal{A}(s)$: \\
            \hspace{2cm} $Q(s , a) \leftarrow$ arbitrário \\
            \hspace{2cm} $\pi(s) \leftarrow$ arbitrário \\
            \hspace{2cm} $R(s , a) \leftarrow \emptyset$ \\ \\
            Repetir infinitamente: \\
            \hspace{2cm} Gerar um episódio usando exploração inicial e $\pi$ \\
            \hspace{2cm} Para cada $(s , a)$ visitado no episódio: \\
            \hspace{4cm} $r \leftarrow$ recompensa por seguir $\pi$ \\
            \hspace{4cm} adicionar $r$ a $R(s , a)$ \\
            \hspace{4cm} $Q(s , a) \leftarrow$ média de $R(s,a)$ \\
            \hspace{2cm} Para cada $s$ do episódio: \\
            \hspace{4cm} $\displaystyle\pi(s) \leftarrow \mathrm{arg}\max_{a} Q(s , a)$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

Para que o método de \textit{Monte Carlo} tenha, facilmente, a garantia de convergência, são assumidas duas condições: em cada episódio começa-se por explorar e que a avaliação de política pode ser realizada num número infinito de episódios. Porém, para se poder obter um algoritmo prático, é necessário descartar estas duas condições não realísticas. Uma das formas de evitar a realização de avaliação de política, num número infinito de episódios, é interromper a convergência da avaliação de política, antes de voltar ao aperfeiçoamento de política. A outra é aproximar a função de valor de estado-acção $Q^{\pi}$, em vez de calculá-la com precisão.

A única maneira geral de garantir que todas as acções são escolhidas infinitamente várias vezes, evitando o uso de exploração inicial, é um agente continuar a escolhe-las. Existem duas abordagens que garantem essa condição, designadamente os métodos \textit{on-policy} e \textit{off-policy}. Os métodos \textit{on-policy} avaliam e aperfeiçoam as políticas que são realizadas para tomar decisões, enquanto que, nos métodos \textit{off-policy}, essas duas funções são separadas para duas políticas distintas. A política usada para tomar decisões, designada por política de comportamento, pode nem sequer estar relacionada com a política que é avaliada e aperfeiçoada, designada por política de estimativa.\cite{RL_introduction}

\pagebreak

\subsection{\textit{on-policy Monte Carlo Control}}

No método \textit{on-policy Monte Carlo Control}, para evitar o uso de exploração inicial, são usadas, geralmente, políticas \textit{soft}, isto é, $\pi(s , a) \geq 0,\ \forall\ s \in \mathcal{S} , a \in \mathcal{A}(s)$. Existem várias políticas \textit{soft}, entre as quais, se destacam a \textit{$\varepsilon$-soft}, a \textit{$\varepsilon$-greedy} e a \textit{softmax} que utiliza a distribuição de \textit{Boltzmann}, designada por estratégia de exploração de \textit{Boltzmann}.
\begin{table}[h]
    \begin{center}
        \caption{Tipos de estratégia de exploração \textit{soft}}
        \label{tab:Soft_policies}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            \begin{IEEEeqnarray}{s/l/c} \label{eq:e_soft}
                \textit{$\varepsilon$-soft} & : & \pi(s , a) \geq \displaystyle\frac{\varepsilon}{|\mathcal{A}(s)|},\ \forall\ s \in \mathcal{S} , a \in \mathcal{A}(s) \\\nonumber \\\nonumber \\ \label{eq:e_greedy}
                \textit{$\varepsilon$-greedy} & : & \pi(s , a)\left\{ \begin{array}{ll} \displaystyle\frac{\varepsilon}{|\mathcal{A}(s)|} & \rightarrow \textrm{não maximizante}  \\ \\ 1 - \varepsilon + \displaystyle\frac{\varepsilon}{|\mathcal{A}(s)|} & \rightarrow \textrm{\textit{greedy} (ávida)} \end{array} \right. \\ \nonumber \\\nonumber \\ \label{eq:softmax}
                \textit{softmax} & : & \pi(s , a) = \displaystyle\frac{{}\qquad e^{\frac{ Q(s , a)}{\tau}}\qquad {}}{\displaystyle\sum_{b = 1}^{|\mathcal{A}(s)|} e^{\frac{Q(s , b)}{\tau}}}
            \end{IEEEeqnarray}
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}
Estas políticas estão definidas na tabela \ref{tab:Soft_policies}, onde, na política \textit{softmax}, é definida a probabilidade de se escolher uma acção $a$ num estado $s$ e em que $\tau \ge 0$ é um parâmetro, designado por ``temperatura''. No limite, quando o número de iterações $t$ tende para infinito, $\tau \rightarrow 0$ e é definido por:
\begin{displaymath}
\mathit{\tau = T\upsilon^{t}}
\end{displaymath}
em que $\upsilon$ é um factor de ``fortificação'', uma constante próxima de 1, e $\mathit{T}$ é um factor de escala.\cite{Softmax_dist}

%\pagebreak

A ideia geral do \textit{on-policy Monte Carlo Control} é que, em relação a $Q^{\pi}$, qualquer política \textit{$\varepsilon$-greedy} é um aperfeiçoamento de uma política \textit{$\varepsilon$-soft} de $\pi$, que é garantido pelo aperfeiçoamento de política. Para tal, se considerarmos $\pi'$ como sendo uma política \textit{$\varepsilon$-greedy}, temos que:
\begin{IEEEeqnarray}{r/C/l}
Q^{\pi}\big(s , \pi'(s)\big) & = & \sum_{a} \pi'(s , a) Q^{\pi}(s , a) \nonumber\\  \label{eq:on_policy_MC}
& = & \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} Q^{\pi}(s , a) + (1 - \varepsilon) \max_{a} Q^{\pi}(s , a) \\
& \geq & \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} Q^{\pi}(s , a) (1 - \varepsilon) \sum_{a} \displaystyle\frac{\pi(s , a) - \frac{\varepsilon}{|\mathcal{A}(s)|}}{1 - \varepsilon} Q^{\pi}(s , a) \nonumber
\end{IEEEeqnarray}

\pagebreak

Uma vez que, a soma é uma média de valores não negativos que tendem para 1, e como tal deve ser menor ou igual que o maior valor médio, então temos que:
\begin{IEEEeqnarray}{r/C/l}
Q^{\pi}\big(s , \pi'(s)\big) & = & \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} Q^{\pi}(s , a) - \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} Q^{\pi}(s , a) + \sum_{a} \pi(s , a) Q^{\pi}(s , a) \nonumber\\ \nonumber\\
& = & V^{\pi}(s),\ \forall\ s \in \mathcal{S} \nonumber
\end{IEEEeqnarray}
\begin{IEEEeqnarray}{c}
\pi' \geq \pi \Leftrightarrow V^{\pi'}(s) \geq V^{\pi}(s),\ \forall\ s \in \mathcal{S} \nonumber
\end{IEEEeqnarray}
É necessário provar, igualmente, para quando $\pi'$ e $\pi$ são melhores ou iguais que todas as outras políticas \textit{$\varepsilon$-soft}. Se considerarmos um novo ambiente, igual ao original, à excepção das políticas serem \textit{$\varepsilon$-soft}. O comportamento no novo ambiente é o mesmo do que no ambiente original com políticas \textit{$\varepsilon$-soft}. Sendo $\tilde{V}^{*}$ e $\tilde{Q}^{*}$, a função de valor de estado óptimo e a função de valor de estado-acção óptimo, respectivamente. Então, uma política $\pi$ é óptima, entre políticas \textit{$\varepsilon$-soft}, se e só se $V^{\pi} = \tilde{V}^{*}$, condição essa provada por Sutton \& Barto em \textit{Reinforcement Learning: an Introduction}.\cite{RL_introduction}

Assim, alcançamos a melhor política, apenas, a partir de políticas \textit{$\varepsilon$-soft}, mas, por outro lado, eliminamos a condição de exploração inicial.
O algoritmo que traduz o método \textit{on-policy Monte Carlo Control} está descrito na tabela \ref{tab:on_policyMonte_Carlo}.

\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo do método \textit{on-policy Monte Carlo Control}.\cite{RL_introduction}}
        \label{tab:on_policyMonte_Carlo}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar, $\forall\ s \in \mathcal{S}, a \in \mathcal{A}(s)$: \\
            \hspace{2cm} $Q(s , a) \leftarrow$ arbitrário \\
            \hspace{2cm} $R(s , a) \leftarrow \emptyset$ \\
            \hspace{2cm} $\pi(s) \leftarrow$ política \textit{$\varepsilon$-soft} arbitrária \\ \\
            Repetir infinitamente: \\
            \hspace{2cm} Gerar um episódio usando $\pi$ \\
            \hspace{2cm} Para cada $(s , a)$ visitado no episódio: \\
            \hspace{4cm} $r \leftarrow$ recompensa por seguir $\pi$ \\
            \hspace{4cm} adicionar $r$ a $R(s , a)$ \\
            \hspace{4cm} $Q(s , a) \leftarrow$ média de $R(s,a)$ \\
            \hspace{2cm} Para cada $s$ do episódio: \\
            \hspace{4cm} $\displaystyle a^{*} \leftarrow \mathrm{arg}\max_{a} Q(s , a)$ \\
            \hspace{4cm} $\forall\ a \in \mathcal{A}(s)$: \\
            \hspace{6cm} \begin{displaymath}\pi(s , a) \leftarrow \left\{ \begin{array}{ll} 1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|} & , \textrm{se}\ a = a^{*} \\ \\ \frac{\varepsilon}{|\mathcal{A}(s)|} & , \textrm{se}\ a \neq a^{*} \end{array}\right.\end{displaymath}
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

\pagebreak

\subsection{\textit{off-policy Monte Carlo Control}}

No método \textit{off-policy Monte Carlo Control}, como já foi referido atrás, temos duas políticas distintas, a política de comportamento, que escolhe as acções, e a política de estimativa, que é avaliada e aperfeiçoada e a partir da qual se aprende. A vantagem de ter duas políticas para funções diferentes é que, a política de estimativa pode ser determinística (por exemplo \textit{$\varepsilon$-greedy}), enquanto a política de comportamento pode seguir uma política que garante experimentar todas as acções possíveis.

%\pagebreak

Mas, para que seja possível termos essas duas políticas distintas, é necessário utilizar o método de avaliar uma política seguindo outra. Para avaliar uma política $\pi$ seguindo uma política $\pi'$ é necessário que, pelo menos ocasionalmente, as acções realizadas por $\pi$ sejam também realizadas por $\pi'$, isto é, é necessário que $\pi(s , a) \ge 0$ implique que $\pi'(s , a) \ge 0$. Sendo $p_{i}(s)$, $p'_{i}(s)$, num episódio $i$, as probabilidades de executar uma sequência de estados e acções partindo de um estado $s$, dadas as políticas $\pi$ e $\pi'$ e $R_{i}(s)$ a recompensa observada, então a função de valor de estado é dada por:

\begin{equation} \label{eq:follow_policy_wile}
\mathit{V(s) = \frac{\displaystyle\sum_{i = 1}^{n_{s}} \frac{p_{i}}{p'_{i}} R_{i}(s)}{\displaystyle\sum_{i = 1}^{n_{s}} \frac{p_{i}}{p'_{i}}} }
\end{equation}

\pagebreak

Embora o método \textit{Monte Carlo} seja um método \textit{model-free}, pelo que não é possível ter conhecimento de $p_{i}$ e $p'_{i}$, a proporção $\displaystyle\frac{p_{i}}{p'_{i}}$ pode ser determinada sem qualquer conhecimento da dinâmica do ambiente, dependendo, apenas, das duas políticas utilizadas da seguinte forma:
\begin{IEEEeqnarray}{r/C/l/C/l}
p_{i}(s_{t}) & = & \prod_{k = t}^{T_{i}(s)-1} \pi(s_{k} , a_{k}) \mathcal{P}_{s_{k} s_{k+1}}^{a_{k}} & &\nonumber \\ \nonumber \\
\frac{p_{i}(s_{t})}{p'_{i}(s_{t})} & = & \frac{\displaystyle\prod_{k = t}^{T_{i}(s)-1} \pi(s_{k} , a_{k}) \mathcal{P}_{s_{k} s_{k+1}}^{a_{k}}}{\displaystyle\prod_{k = t}^{T_{i}(s)-1} \pi'(s_{k} , a_{k}) \mathcal{P}_{s_{k} s_{k+1}}^{a_{k}}} & = & \prod_{k = t}^{T_{i}(s)-1} \frac{\pi(s_{k} , a_{k})}{\pi'(s_{k} , a_{k})} \nonumber
\end{IEEEeqnarray}

Conhecendo isto, é possível conceber o algoritmo do método \textit{off-policy Monte Carlo Control} descrito na tabela \ref{tab:off_policyMonte_Carlo}, em que $N(s , a)$ e $D(s , a)$ correspondem, respectivamente, ao numerador e dominador da função de valor de estado-acção $Q(s , a)$.
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo \textit{$\varepsilon$-soft} do método \textit{off-policy Monte Carlo Control}.\cite{RL_introduction}}
        \label{tab:off_policyMonte_Carlo}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar, $\forall\ s \in \mathcal{S}, a \in \mathcal{A}(s)$: \\
            \hspace{2cm} $Q(s , a) \leftarrow$ arbitrário \\
            \hspace{2cm} $N(s , a) \leftarrow 0$ \\
            \hspace{2cm} $D(s , a) \leftarrow 0$ \\
            \hspace{2cm} $\pi(s) \leftarrow$ política determinística \textit{$\varepsilon$-soft} arbitrária \\ \\
            Repetir infinitamente: \\
            \hspace{2cm} Seleccionar $\pi'$ usa-la para gerar um episódio: \\
            \hspace{4cm} $s_{0} , a_{0} , r_{1} , s_{1} , a_{1} , \dots , s_{T-1} , a_{T-1} , r_{T} , s_{T}$ \\
            \hspace{2cm} $\tau \leftarrow$ última vez em que $a_{\tau} \neq \pi(s_{\tau})$ \\
            \hspace{2cm} Para cada $(s , a)$ visitado no episódio, depois de $\tau$: \\
            \hspace{4cm} $t \leftarrow$ o tempo da primeira ocorrência, depois de $\tau$ de $(s , a)$ \\
            \hspace{4cm} $\displaystyle\omega \leftarrow \prod_{k = t + 1}^{T - 1} \frac{1}{\pi'(s_{k} , a_{k})}$ \\
            \hspace{4cm} $N(s , a) \leftarrow N(s , a) + \omega R_{t}$ \\
            \hspace{4cm} $D(s , a) \leftarrow D(s , a) + \omega$ \\
            \hspace{4cm} $Q(s , a) \leftarrow \frac{N(s , a)}{D(s , a)}$ \\
            \hspace{2cm} Para cada $s \in \mathcal{S}$ do episódio: \\
            \hspace{4cm} $\displaystyle\pi(s) \leftarrow \mathrm{arg}\max_{a} Q(s , a)$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

\pagebreak

\subsection{TD(0)}

O método da aprendizagem por diferença temporal, ou aprendizagem TD (\textit{Temporal Diference learning}), é considerado um método central e original do \textit{reinforcement learning}. Este, combina o método de \textit{Monte Carlo} com a programação dinâmica, ou DP (\textit{Dynamic Programming}). Tal como nos métodos \textit{Monte Carlo}, também os de diferença temporal são \textit{model-free}, podendo-se aprender através da experiência directa com o ambiente, sem a necessidade de conhecer a sua dinâmica. E os métodos de diferença temporal também estimam e actualizam, baseando-se, em parte, noutras estimativas aprendidas anteriormente, sem esperar pelo final dos episódios, à semelhança da programação dinâmica.

Enquanto que, nos métodos de \textit{Monte Carlo}, é necessário esperar pelo final de cada episódio para receber a recompensa num passo $t$, determinando o incremento da função de valor de estado $V(s_{t})$, nos métodos de diferença temporal, apenas é necessário esperar pelo próximo passo. Isto é, no passo $t + 1$ é observada a recompensa $r + 1$, é estimado $V(s_{t + 1})$ e é actualizado $V(s_{t})$. O método de diferença temporal mais simples é conhecido como TD(0) e a função de valor de estado é dada por:
\begin{equation} \label{eq:TD_0}
\mathit{V(s_{t}) \leftarrow V(s_{t}) + \alpha \Big[ r_{t+1} + \gamma V(s_{t + 1}) - V(s_{t}) \Big]}
\end{equation}
onde $\alpha$ é uma constante, designada por parâmetro de coeficiente de aprendizagem. O algoritmo descrito na tabela \ref{tab:TD0} especifica o método TD(0).
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo TD(0).\cite{RL_introduction}}
        \label{tab:TD0}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar: \\
            \hspace{2cm} $V(s) \leftarrow$ arbitrário \\
            \hspace{2cm} $\pi(s) \leftarrow$ política a ser avaliada \\ \\
            Repetir para cada episódio: \\
            \hspace{2cm} Inicializar $s$ \\
            \hspace{2cm} Repetir para cada passo do episódio até s terminar: \\
            \hspace{4cm} $a \leftarrow$ acção escolhida por $\pi$ para o estado $s$ \\
            \hspace{4cm} Executar a acção $a$ \\
            \hspace{4cm} Observar a recompensa $r$ e o próximo estado $s'$\\
            \hspace{4cm} $V(s) \leftarrow V(s) + \alpha \big[ r + \gamma V(s') - V(s) \big]$ \\
            \hspace{4cm} $s \leftarrow s'$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

\subsection{\textit{Q-learning}}
\label{seq:Q_learning}

O \textit{Q-learning}\cite{Watkins1989}, um método \textit{off-policy}, é o método mais conhecido, e um dos mais importantes, do \textit{reinforcement learning}.
Se as recompensas e acções forem estocásticas, para poder-se modelar a incerteza num sistema (que resulta em parte da dinâmica do ambiente não controlável por um agente), são consideradas a probabilidade de obter uma recompensa $P(r_{t + 1}\ |\ s_{t} , a_{t})$ e a probabilidade de visitarmos o próximo estado $P(s_{t + 1}\ |\ s_{t} , a_{t})$.\cite{Machine_Learing} Se considerarmos, por exemplo, um agente como sendo um robô que, devido a variações de temperatura, por vezes se desvia da trajectória que escolheu seguir, ou avança menos do que esperava, então temos:
\begin{equation} \label{eq:q_learning_model}
\mathit{ Q(s_{t} , a_{t}) = E[r_{t + 1}] + \gamma \sum_{s_{t + 1}} P(s_{t + 1}\ |\ s_{t} , a_{t}) \max_{a_{t + 1}} Q(s_{t + 1} , a_{t + 1}) }
\end{equation}
Sendo assim, não é possível fazer uma atribuição directa do valor da recompensa esperada, visto que, para o mesmo par de estado-acção, é possível que o robô obtenha recompensas distintas ou próximos estados diferentes.\cite{Machine_Learing} O que no Q-learning se faz é manter uma média dos valores de $Q$:
\begin{equation} \label{eq:q_learning}
\mathit{ Q(s_{t} , a_{t}) = Q(s_{t} , a_{t}) + \alpha \Big[r_{t + 1} + \gamma \max_{a} Q(s_{t + 1} , a) - Q(s_{t} , a_{t})\Big] }
\end{equation}
Neste caso, a função de valor de estado-acção $Q$ aprendida, aproxima directamente a função de valor de estado-acção óptima $Q^{*}$, independentemente da política seguida. O que simplifica significativamente o algoritmo e permite uma convergência rápida. A política continua a determinar qual o próximo par de estado-acção a ser actualizado, no entanto, a actualização contínua dos pares de estado-acção é tudo o que é necessário para corrigir a convergência para $Q^{*}$. O procedimento do algoritmo de \textit{Q-learning} é descrito na tabela \ref{tab:Q_learning}.
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo \textit{Q-learning}.\cite{RL_introduction}}
        \label{tab:Q_learning}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar: \\
            \hspace{2cm} $Q(s , a) \leftarrow$ arbitrário \\ \\
            Repetir para cada episódio: \\
            \hspace{2cm} Inicializar $s$ \\
            \hspace{2cm} Repetir para cada passo do episódio até s terminar: \\
            \hspace{4cm} $a' \leftarrow$ tendo $s'$, baseado em $Q$, usando uma política (por ex.: \textit{$\varepsilon$-greedy}) \\
            \hspace{4cm} Executar a acção $a$ \\
            \hspace{4cm} Observar o próximo estado $s'$ e a recompensa $r$ \\
            \hspace{4cm} $\displaystyle Q(s , a) \leftarrow Q(s , a) + \alpha \Big[ r + \gamma \max_{a'} Q(s' , a') - Q(s , a) \Big]$ \\
            \hspace{4cm} $s \leftarrow s'$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

O \textit{Q-learning} tornou-se num dos métodos de \textit{reinforcement learning} mais populares,\linebreak[4] devido ao facto de ser um algoritmo ``insensível à exploração'', ou seja, apesar de existir a problemática \textit{exploration-exploitation}, a convergência de aprendizagem não depende da política de exploração.\cite{reinforcementlearning_A_survey}

\pagebreak

\subsection{SARSA - \textit{State-Action-Reward-State-Action}}
\label{seq:SARSA}

O método SARSA, que significa a sequência estado-acção-recompensa-estado-acção, é um algoritmo \textit{on-policy} para a aprendizagem TD. Muito semelhante ao método de aprendizagem \textit{Q-learning}, a grande diferença entre eles é o facto de, no método SARSA, a recompensa máxima para o próximo passo não ser, necessariamente, usada para actualizar o valor de $Q$. Em vez disso, uma nova acção $a'$ é escolhida, após a observação da recompensa $r$ no novo estado $s'$, usando a mesma política que, no estado original $s$, determinou a acção original $a$. A função de valor de estado-acção, para o método SARSA, é dada por:
\begin{equation} \label{eq:SARSA}
\mathit{ Q(s_{t} , a_{t}) \leftarrow Q(s_{t} , a_{t}) + \alpha \Big[r_{t+1} + \gamma Q(s_{t + 1} , a_{t + 1}) - Q(s_{t} , a_{t})\Big] }
\end{equation}

Esta actualização ocorre após a transição de um estado $s_{t}$ não terminal para um estado $s_{t + 1}$, e se, este último, for terminal, então $Q(s_{t + 1} , a_{t + 1}) = 0$. O algoritmo do método SARSA, descrito na tabela \ref{tab:SARSA_learning} é de fácil concepção. Tal como em qualquer método \textit{on-policy}, a função de valor de estado-acção $Q^{\pi}$ é continuamente estimada para a política de comportamento $\pi$ e, ao mesmo tempo, altera $\pi$ avidamente, isto é, por forma a escolher a melhor acção, respectivamente a $Q^{\pi}$.
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo SARSA.\cite{RL_introduction}}
        \label{tab:SARSA_learning}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar: \\
            \hspace{2cm} $Q(s , a) \leftarrow$ arbitrário \\ \\
            Repetir para cada episódio: \\
            \hspace{2cm} Inicializar $s$ \\
            \hspace{2cm} $a' \leftarrow$ tendo $s'$, baseado em $Q$, usando uma política (por ex.: \textit{$\varepsilon$-greedy}) \\
            \hspace{2cm} Repetir para cada passo do episódio até s terminar: \\
            \hspace{4cm} Executar a acção $a$ \\
            \hspace{4cm} Observar o próximo estado $s'$ e a recompensa $r$ \\
            \hspace{4cm} $a' \leftarrow$ tendo $s'$, baseado em $Q$, usando uma política (por ex.: \textit{$\varepsilon$-greedy}) \\
            \hspace{4cm} $\displaystyle Q(s , a) \leftarrow Q(s , a) + \alpha \Big[ r + \gamma Q(s' , a') - Q(s , a) \Big]$ \\
            \hspace{4cm} $s \leftarrow s'$ \\
            \hspace{4cm} $a \leftarrow a'$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

A convergência do algoritmo do método SARSA depende da natureza da dependência da política $\pi$ em relação a $Q$, como por exemplo \textit{$\varepsilon$-greedy} ou \textit{$\varepsilon$-soft}. O método SARSA converge para uma política óptima $\pi^{*}$ e uma função de valor de estado-acção $Q^{*}$, enquanto os pares de estado-acção forem visitados infinitamente e a política convergir para uma política ávida. Esta última condição pode ser alcançada com políticas \textit{$\varepsilon$-greedy} usando $\displaystyle\varepsilon = \frac{1}{t}$.\cite{RL_introduction}

\pagebreak

\section{Métodos \textit{Model-based}}

Nos métodos \textit{model-based}, a dinâmica do ambiente é conhecida, isto é, os parâmetros do modelo do ambiente $P(r_{t + 1}\ |\ s_{t} , a_{t})$ e $P(s_{t + 1}\ |\ s_{t} , a_{t})$. Assim sendo, não existe a necessidade de explorar os estados e acções e é possível obter a função de valor de estado óptima e a política óptima directamente usando programação dinâmica, ou DP (\textit{Dynamic Programming}). A função de valor de estado óptima $V^{*}$ é única e é a solução para o sistema de equações \ref{eq:opt_Bellman} e \ref{eq:opt_BellmanQ}.\cite{Machine_Learing}

%\pagebreak

Uma vez tendo a função de valor de estado óptima, a política óptima é escolher a acção que maximiza o valor no próximo passo:
\begin{equation} \label{eq:dinamic_programming}
\mathit{ \pi^{*}(s_{t}) = \mathrm{arg}\max_{a_{t}} \bigg(E\Big[r_{t + 1}\ |\ s_{t} , a_{t}\Big] + \gamma \sum_{s_{t + 1} \in \mathcal{S}} P(s_{t + 1}\ |\ s_{t} , a_{t}) V^{*}(s_{t})\bigg) }
\end{equation}

Nesta secção descrevem-se dois tipos de métodos \textit{model-based} de programação dinâmica: \textit{Policy Iteration} e \textit{Value Iteration}.

\subsection{\textit{Policy Iteration}}

O método \textit{model-based} de programação dinâmica \textit{Policy Iteration} é, como o próprio nome sugere, um algoritmo iterativo onde uma política $\pi$ é repetidamente aperfeiçoada até se encontrar a política óptima $\pi^{*}$.\cite{Machine_Learing} Tendo uma política $\pi$, usando a função de valor $V^{\pi}$, sido aperfeiçoada para uma política $\pi'$, é possível então calcular $V^{\pi'}$ e aperfeiçoar, mais uma vez, uma política $\pi'$ para uma política $\pi''$. Seguindo este pensamento obtemos uma sequência de aperfeiçoamento de política e funções de valor:
\begin{equation} \label{eq:Pol_it_seq}
\mathit{\pi_{0} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} V^{\pi_{0}} \stackrel{\scriptscriptstyle{I}}{\longrightarrow} \pi_{1} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} V^{\pi_{1}} \cdots \stackrel{\scriptscriptstyle{I}}{\longrightarrow} \pi^{*} \stackrel{\scriptscriptstyle{E}}{\longrightarrow} V^{*},}
\end{equation}
tal como no método \textit{Monte Carlo Control}, também no \textit{Policy Iteration} começa-se com uma política $\pi_{0}$, a partir da qual são realizados passos de avaliação política $\stackrel{E}{\longrightarrow}$ e passos de aperfeiçoamento de política $\stackrel{E}{\longrightarrow}$ alternadamente, até ser encontrada uma política óptima $\pi^{*}$ e uma função de valor óptima $V^{*}$.

No método \textit{Policy Iteration}, cujo algoritmo pode ser visto na tabela \ref{tab:Policy_Iteration}, a avaliação de política, ela própria uma computação iterativa, inicia a partir de uma função de valor para a política anterior, o que faz com que aumente significativamente a rapidez da sua convergência.\cite{RL_introduction}
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo \textit{Policy Iteration}.\cite{RL_introduction}}
        \label{tab:Policy_Iteration}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            1. Inicializar $\ \forall\ s \in \mathcal{S}$: \\
            \hspace{2cm} $V(s) \in \mathfrak{R} \leftarrow$ arbitrário \\
            \hspace{2cm} $\pi(s) \in \mathcal{A}(s) \leftarrow$ arbitrário \\ \\
            2. Avaliação de política: \\
            \hspace{2cm} Repetir, enquanto $\Delta < \theta$ (um número pequeno positivo): \\
            \hspace{4cm} $\Delta \leftarrow 0$ \\
            \hspace{4cm} Para cada $s \in \mathcal{S}$: \\
            \hspace{6cm} $\nu \leftarrow V(s)$ \\
            \hspace{6cm} $V(s) \leftarrow \displaystyle\sum_{s'} \mathcal{P}_{s s'}^{\pi(s)} \Big[\mathcal{R}_{s s'}^{\pi(s)} + \gamma V(s')\Big]$ \\
            \hspace{6cm} $\Delta \leftarrow \max\big(\Delta , |\nu - V(s)|\big)$ \\ \\
            3. Aperfeiçoamento de política: \\
            \hspace{2cm} política-estável $\leftarrow$ verdadeiro \\
            \hspace{2cm} Para cada $s \in \mathcal{S}$: \\
            \hspace{4cm} $\displaystyle\pi(s) \leftarrow \mathrm{arg}\max_{a} \sum_{s'} \mathcal{P}_{s s'}^{a}\Big[\mathcal{R}_{s s'}^{a} + \gamma V(s')\Big]$ \\
            \hspace{4cm} Se $b \neq \pi(s)$, então: \\
            \hspace{6cm} política-estável $\leftarrow$ falso \\
            \hspace{2cm} Se política-estável, então: \\
            \hspace{4cm} Pára \\
            \hspace{2cm} Caso contrário, voltar para 2.
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}
Tendo em conta a função de valor, que é calculada resolvendo as equações lineares, é verificado se é possível aperfeiçoar a política. Quando já não for possível aperfeiçoar a política, então essa é a política óptima.\cite{Machine_Learing}

%A \textit{Policy Iteration} converge num pequeno número de iterações, no entanto cada iteração demora algum tempo, $\mathcal{O}\big(|\mathcal{A}| |\mathcal{S}|^{2} + |\mathcal{S}|^{3}\big)$ o que é mais do que leva o método \textit{Value Iteration}.

\pagebreak

\subsection{\textit{Value Iteration}}

O \textit{Value Iteration}, à semelhança do \textit{Policy Iteration}, é um algoritmo iterativo \textit{model-based} de programação dinâmica. No entanto, enquanto que no \textit{Policy Iteration} o aperfeiçoamento de política é iterativo, o que faz com que apenas convirja para $V^{*}$ no limite, no \textit{Value Iteration} os passos de avaliação de política podem ser interrompidos sem comprometer a garantia de convergência do \textit{Policy Iteration}. E assim, é possível obter uma política óptima $\pi^{*}$, que, uma vez que apenas são tidas em conta as acções que maximizam $V^{\pi}$, pode convergir mesmo antes de se obter $V^{*}$.\cite{Machine_Learing} Combinando aperfeiçoamento de política com passos incompletos de avaliação de política, o \textit{Value Iteration} pode ser escrito da seguinte forma:
\begin{IEEEeqnarray}{r/C/l} \label{eq:Val_it}
V_{k + 1}(s) & = & \max_{a} E \Big\{r_{t + 1} + \gamma V_{k}(s_{t + 1})\ |\ s_{t} = s , a_{t} = a\Big\} \\
& = & \max_{a} \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[\mathcal{R}_{s s'}^{a} + \gamma V_{k}(s')\Big],\ \forall\ s \in \mathcal{S} \nonumber
\end{IEEEeqnarray}
onde $k$ é o número da iteração. Tal como na avaliação de política, no método \textit{Value Iteration}, idealisticamente é necessário um número infinito de iterações para convergir exactamente para $V^{*}$. Na prática, o valor óptimo $V^{*}$ é encontrado quando a diferença máxima entre duas funções de valor consecutivas é menor que um valor pequeno $\theta$, isto é: $\displaystyle\max_{s \in \mathcal{S}}\big|V_{k + 1}(s) - V_{k}(s)\big| \le \theta$.\cite{Machine_Learing}
\begin{table}[!h]
    \begin{center}
        \caption{Pseudo-código do algoritmo \textit{Value Iteration}.\cite{RL_introduction}}
        \label{tab:Value_Iteration}
        \begin{tabular}{p{.974\linewidth}}
            \hline
            \hline
            \\
            Inicializar $\ \forall\ s \in \mathcal{S}$: \\
            \hspace{2cm} $V(s) \leftarrow$ arbitrário (por ex.: $V(s) = 0$)\\ \\
            Repetir, até $\Delta < \theta$: \\
            \hspace{2cm} Para cada $s \in \mathcal{S}$: \\
            \hspace{4cm} $\Delta \leftarrow 0$ \\
            \hspace{4cm} $\nu \leftarrow V(s)$ \\
            \hspace{4cm} $V(s) \leftarrow \displaystyle \max_{a} \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[\mathcal{R}_{s s'}^{a} + \gamma V(s')\Big]$ \\
            \hspace{4cm} $\Delta \leftarrow \max\big(\Delta , |\nu - V(s)|\big)$ \\ \\
            Resulta uma política determinística $\pi$, tal que: \\
            \hspace{2cm} $\pi(s) = \displaystyle\mathrm{arg}\max_{a} \sum_{s'} \mathcal{P}_{s s'}^{a} \Big[\mathcal{R}_{s s'}^{a} + \gamma V(s')\Big]$ \\
            \\
            \hline
        \end{tabular}
    \end{center}
\end{table}

O algoritmo do método \textit{Value Iteration}, descrito na tabela \ref{tab:Value_Iteration}, combina eficazmente um ciclo de avaliação de política com um ciclo de aperfeiçoamento de política, em cada iteração. Uma rápida convergência pode ser alcançada, entrepondo vários ciclos de avaliação de política entre cada aperfeiçoamento de política.\cite{RL_introduction}

\chapter{Desenhos técnicos}

%\pagebreak[4]
%\newpage
\newpage
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Base do chassi}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Suporte dos sensores de contacto}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Suporte dos sensores frontais}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Suporte do sensor traseiro}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Peça de fixação do suporte dos sensores frontais}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Pilar de suporte dos servos}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Pilar de suporte dos sensores de distância por infra-vermelhos laterais}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Barra de contacto frontal}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Barra de contacto lateral}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Barra de contacto lateral-frontal}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Barra de contacto traseira}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Canto frontal-lateral}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Canto traseiro-lateral}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Tela de latex frontal}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Tela de latex lateral}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Tela de latex lateral-frontal}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Tela de latex traseira}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Tela de latex para os cantos}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{section}{1}
\addcontentsline{toc}{section}{\numberline{\thesection} Suporte dos apoios esféricos}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage


\chapter{Placas de circuito impresso}

\section{Traçado do circuito impresso das Placas}

\begin{figure}[h!]
  \centering
  % Requires \usepackage{graphicx}
  \includegraphics[scale=1]{SALbot_main_pcb}\\
  \caption{Traçado do circuito impresso da placa principal do SALbot.}\label{fig:SALbot_main_pcb}
\end{figure}

\begin{figure}[h!]
  \centering
  % Requires \usepackage{graphicx}
  \includegraphics[scale=1]{SALbot_aux_pcb}\\
  \caption{Traçado do circuito impresso da placa auxiliar do SALbot.}\label{fig:SALbot_aux_pcb}
\end{figure}

%\clearpage
%\addtocounter{page}{1}

\begin{figure}[h!]
  \centering
  % Requires \usepackage{graphicx}
  \includegraphics[scale=1]{SALbot_com}\\
  \caption{Traçado do circuito impresso da placa de interface de comunicação.}\label{fig:SALbot_com_pcb}
\end{figure}

\clearpage
\section{Esquemas eléctricos}
\pagebreak[4]
\newpage
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{subsection}{1}
\addcontentsline{toc}{subsection}{\numberline{\thesubsection} Schematic SALbot Main}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{subsection}{1}
\addcontentsline{toc}{subsection}{\numberline{\thesubsection} Schematic SALbot Aux}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
\phantomsection
\addtocounter{subsection}{1}
\addcontentsline{toc}{subsection}{\numberline{\thesubsection} Schematic SALbot Com}
\mbox{}
\pagebreak[4]
\newpage
\thispagestyle{empty}
\mbox{}
\mbox{}
\pagebreak[4]
\newpage
%\clearpage
%
%\pdfpagewidth=2\paperwidth % Generate A3 by multiplying A4 by 2.
%
%\newgeometry{top=0cm,bottom=0cm,left=0cm,right=0cm,nohead,nofoot}
%\thispagestyle{empty}
%
%\begin{figure}[h!]
%    \centering
%    \includegraphics[scale=1]{Schematic_Prints_SALbot_main}
%    %\vfill
%\end{figure}
%\restoregeometry
%
%\pdfpagewidth=1\paperwidth % "End" A3
%\newpage
%
%\newgeometry{top=0cm,bottom=0cm,left=0cm,right=0cm,nohead,nofoot}
%\thispagestyle{empty}
%
%\begin{figure}[h!]
%    \centering
%    \includegraphics[scale=1]{Schematic_Prints_SALbot_aux}
%    %\vfill
%\end{figure}
%\restoregeometry
%
%\clearpage
%%\addtocounter{page}{3}
\section{Imagens das placas}
\vfill
\begin{figure}[h]
  \centering
  \includegraphics[width=1\textwidth]{SALbot_Main}\\
  \caption{Imagem foto-realista da placa principal do SALbot.}\label{fig:SALbot_main_render}
\end{figure}
\vfill

\begin{figure}[ht]
  \centering
  \includegraphics[width=.9\textwidth]{SALbot_Aux}\\
  \caption{Imagem foto-realista da placa auxiliar do SALbot.}\label{fig:SALbot_Aux_render}
\end{figure}

\begin{figure}[ht]
  \centering
  \includegraphics[width=.9\textwidth]{SALbot_com_receiver}\\
  \caption{Imagem foto-realista da placa de interface de comunicação.}\label{fig:SALbot_com_receiver_render}
\end{figure}

\begin{figure}[ht]
  \centering
  \includegraphics[width=.9\textwidth]{SALbot_com_}\\
  \caption{Imagem da placa de interface de comunicação.}\label{fig:SALbot_com_receiver_}
\end{figure}

\chapter{Imagens dos robôs}


\begin{figure}[ht]
  \centering
  \includegraphics[width=.9\textwidth]{SALbot_render1}\\
  \caption{Imagem foto-realista dos SALbot.}\label{fig:SALbots_render}
\end{figure}

\begin{figure}[ht]
  \centering
  \includegraphics[width=.9\textwidth]{SALbots_}\\
  \caption{Imagem dos SALbot.}\label{fig:SALbots}
\end{figure}

\begin{figure}[ht]
  \centering
  \includegraphics[width=.45\textwidth]{SALbot_logo}\\
  \caption{Logótipo do SALbot.}\label{fig:SALbot_logo}
\end{figure}







