Introdução

O termo aprendizado por reforço refere-se a um conjunto de técnicas desenvolvidas pelas comunidades de inteligência artificial e aprendizado de máquina cujo objetivo é treinar um agente artificial para tomar decisões sequenciais enquanto interage com um ambiente. O aprendizado por reforço (doravante chamado de RL, de reinforcement learning em inglês) teve sua origem em meados dos anos 1980, e desde então tem sido aplicado em diversas áreas, dentre as quais se destacam a robótica, jogos de tabuleiro, jogos eletrônicos e problemas tradicionalmente estudados na pesquisa operacional.

As teorias e os algoritmos de RL estão intimamente relacionadas com uma técnica de pesquisa operacional conhecida por programação dinâmica (dynamic programming - DP). Por esta razão, para entender os algoritmos de RL, é importante conhecer primeiro conceitos relacionados à DP.

Programação Dinâmica

Programação dinâmica é uma técnica de modelagem matemática e solução de problemas de decisão sequenciais desenvolvida por Richard Bellman. A programação dinâmica é uma técnica de grande generalidade, de forma que pode ser aplicada tanto a problemas discretos quanto contínuos, determinísticos ou estocásticos, de horizonte finito ou infinito.

O aprendizado por reforço é baseado principalmente na teoria da programação dinâmica discreta estocástica. Os problemas resolvidos são conhecidos por processos de decisão markovianos. Um processo de decisão markoviano é definido por um conjunto finito de estados $s \in \mathcal{S}$ do ambiente (ou sistema), um conjunto finito de ações $a \in \mathcal{A}$ que podem ser tomadas, uma função de transição de estados, dada pela probabilidade condicional $p(s'|s,a)$, e uma função de recompensa $r(s,a)$.

A distribuição de probabilidades condicional $p(s'|s,a)$ define a probabilidade do ambiente realizar uma transição de um estado $s$ para um estado $s'$ dada uma ação $a$. Note que a ação tomada influencia a transição de estados. Em um dado estado $s$, se o agente tomar uma decisão $a$, ele recebe uma recompensa $r(s,a)$.¹

O problema de decisão markoviano corresponde a encontrar uma política de decisão $\pi$ que otimiza uma função de desempenho do agente. Uma política de decisão é uma função $\pi: \mathcal{S} \to \mathcal A$ que associa a cada estado do ambiente uma ação. Intuitivamente, uma política determina o comportamento do agente. Uma função de desempenho bastante popular é a maximização da recompensa acumulada em um horizonte de tempo infinito. Dada uma política $\pi$, define-se o seu desempenho por meio da função: $$ v_{\pi}(s_0) = \lim_{T \to \infty} \mathbb{E}\Bigg[\sum_{t=0}^T \gamma^t r(s_t,\pi(s_t))\Bigg], $$ em que $s_0$ é o estado inicial e $0< \gamma < 1$ é um fator de desconto para garantir que a soma infinita converge. Portanto, o problema consiste em encontrar uma política ótima $\pi^\star$ que maximiza a função de desempenho, dada por $$ \pi^\star(s) = \arg\max_{\pi \in \Pi} v_{\pi}(s), \quad \forall s \in \mathcal{S}, $$ e $\Pi$ é uma classe de políticas. Em princípio, o problema pode ser resolvido enumerando todas as políticas no conjunto $\Pi$ se for possível computar a função de desempenho para cada uma delas. No entanto, frequentemente isso não é possível. Por outro lado, é possível obter algoritmos de solução por meio da Equação de Bellman. Seja $v^\star$ a função de valor ótima definida por $$ v^\star(s) = \max_{\pi \in \Pi} v_{\pi}(s), \quad \forall s \in \mathcal{S}. $$

A Equação de Bellman estabelece que $$ v^\star(s) = \max_{a \in \mathcal{A}_s} \Big\{r(s,a)+\sum_{s’ \in \mathcal{S}}p(s'|s,a)v^\star(s’) \Big\}. $$

Note que a função de valor ótima é o ponto fixo da Equação de Bellman. Portanto, a Equação de Bellman é a base de um algoritmo para obtenção da função de valor ótima conhecido como iteração de valor, que é essencialmente um tipo de iteração de ponto fixo. Além disso, se conhecermos a função de valor ótima, uma política ótima $\pi^\star$ pode ser obtida escolhendo em cada estado $s \in \mathcal{S}$ a ação gulosa $a^\star(s)$ em relação à função de valor ótima, dada por $$ a^\star(s) = \arg\max_{a \in \mathcal{A}_s} \Big\{r(s,a)+\sum_{s’ \in \mathcal{S}}p(s'|s,a)v^\star(s’) \Big\}. $$

O método de iteração de valor consiste nos seguintes passos:

Iteração de Valor

1. Para cada $s \in \mathcal{S}$, atribua um valor inicial $v^{(0)}(s) = 0$, faça $k \gets 0$;

2. Repita: $v^{(k+1)} \gets \max_{a \in \mathcal{A}_s} \Big\{r(s,a)+\sum_{s’ \in \mathcal{S}}p(s'|s,a)v^{(k)} \Big\}$; $k \gets k+1$;

   Até

   $||v^{(k+1)}-v^{(k)}||_{\infty} < \epsilon$;

em que $\epsilon$ é um número pequeno (valores típicos variam entre $10^{-3}$ a $10^{-9}$), e $||.||_{\infty}$ denota a *norma de Chebyshev*.

Note que, tecnicamente, o método de iteração de valor obtém a função de valor ótima somente quando $k \to \infty$. Portanto, como as iterações são interrompidas quando a norma é menor que $\epsilon$, não há garantia de que a função de valor obtida é ótima. Mas, frequentemente, quando $\epsilon$ é suficientemente pequeno, a função de valor obtida é ótima ou muito próxima da ótima. Existe outro método, chamado de iteração de política, que garante a obtenção de uma política ótima em um número finito de iterações.

Exemplo: Caminho mínimo estocástico

Imagine um problema em que um agente (um robô, por exemplo) deseja sair um um local de origem e chegar a um local de destino no menor tempo possível. O ambiente em que o agente se encontra é um mundo em grade (grid world), como na figura abaixo.

A maldição da dimensionalidade

Aprendizado por reforço

O aprendizado por reforço é uma técnica originada na comunidade de inteligência artificial cuja fundamentação matemática é a programação dinâmica, de forma que o aprendizado por reforço também é conhecido por programação dinâmica aproximada.

Essencialmente, o aprendizado por reforço tenta superar as limitações da programação dinâmica por meio de técnicas aproximativas. Uma primeira limitação da PD é que o modelo do ambiente, ou seja, a função de transição de estados e a função de recompensa, precisam ser conhecidos para se computar uma política ótima. No entanto, frequentemente não se conhece exatamente a função de transição e a função de recompensa. As técnicas de aprendizado por reforço não necessitam explicitamente do modelo do ambiente, necessitando apenas de amostras de transições e recompensas, obtidas diretamente do ambiente ou por simulação. Por essa razão, as técnicas de RL são referidas como livres de modelo.