direita|miniaturadaimagem|A forma típica de enquadrar um cenário de aprendizado por reforço (RL): um agente executa ações em um ambiente, que são interpretadas em um sinal de recompensa e uma representação de estado, os quais são retornados ao agente. Aprendizado ou apredizagem por reforço (AR) é uma área interdisciplinar de aprendizado de máquina e controle ótimo que se preocupa com a forma como um agente inteligente deve tomar ações em um ambiente dinâmico para maximizar um sinal de recompensa. É um dos três paradigmas básicos de aprendizado de máquina, juntamente com o aprendizado supervisionado e o aprendizado não supervisionado.

O Q-learning, em sua forma mais simples, armazena dados em tabelas. Essa abordagem se torna inviável à medida que o número de estados/ações aumenta (por exemplo, se o espaço de estados ou o espaço de ações fosse contínuo), pois a probabilidade do agente visitar um estado específico e executar uma ação específica diminui. O aprendizado por reforço difere do aprendizado supervisionado por não precisar que pares de entrada-saída rotulados sejam apresentados e por não precisar que ações subótimas sejam explicitamente corrigidas. Em vez disso, o foco está em encontrar um equilíbrio entre a exploração (de território desconhecido) e a exploração (do conhecimento atual) com o objetivo de maximizar a recompensa cumulativa (cujo feedback pode ser incompleto ou atrasado).

O ambiente é normalmente declarado na forma de um processo de decisão de Markov (PDM), já que muitos algoritmos de aprendizagem por reforço usam técnicas de programação dinâmica. A principal diferença entre os métodos clássicos de programação dinâmica e os algoritmos de aprendizagem por reforço é que estes últimos não pressupõem o conhecimento de um modelo matemático exato do processo de decisão de Markov e têm como alvo grandes PDMs onde os métodos exatos se tornam inviáveis.

Princípios Devido à sua generalidade, o aprendizado por reforço é estudado em muitas disciplinas, como teoria dos jogos, teoria de controle, pesquisa operacional, teoria da informação, otimização baseada em simulação, sistemas multiagente, inteligência de enxame e estatística. Na pesquisa operacional e na literatura de controle, o AR é chamado de programação dinâmica aproximada ou programação neuro-dinâmica. Os problemas de interesse em AR também são estudados na teoria de controle ótimo, que se preocupa principalmente com a existência e caracterização de soluções ótimas e algoritmos para seu cálculo exato, e menos com aprendizado ou aproximação (particularmente na ausência de um modelo matemático do ambiente).

O aprendizado por reforço básico é modelado como um processo de decisão de Markov:

Um conjunto de estados do ambiente e do agente (o espaço de estados), ; Um conjunto de ações (o espaço de ações), , do agente; , a probabilidade de transição (no tempo ) de estado para estado sob a ação . , a recompensa imediata após a transição de para sob a ação .

O objetivo do aprendizado por reforço é levar o agente a aprender uma política ótima (ou próxima do ótimo) que maximize a função de recompensa ou outro sinal de reforço fornecido pelo usuário, acumulado a partir de recompensas imediatas. Isso é semelhante a processos que parecem ocorrer na psicologia animal. Por exemplo, cérebros biológicos são programados para interpretar sinais como dor e fome como reforços negativos e interpretar prazer e consumo de alimentos como reforços positivos. Em algumas circunstâncias, animais aprendem a adotar comportamentos que otimizam essas recompensas, sugerindo que animais são capazes de aprendizado por reforço.

Um agente básico de aprendizado por reforço interage com seu ambiente em passos de tempo discretos. A cada passo de tempo , o agente recebe o estado atual e a recompensa . Em seguida, escolhe uma ação dentre as ações disponíveis, que então é enviada ao ambiente. O ambiente passa para um novo estado e a recompensa associada à transição é determinada. O objetivo de um agente de aprendizado por reforço é aprender uma política:

,

que maximize a recompensa acumulada esperada.

Formular o problema como um processo de decisão de Markov pressupõe que o agente observa diretamente o estado atual do ambiente; nesse caso, diz-se que o problema tem observabilidade completa. Se o agente só tem acesso a um subconjunto de estados ou se os estados observados são corrompidos por ruído, o agente tem observabilidade parcial, e formalmente o problema deve ser definido como um processo de decisão de Markov parcialmente observável. Em ambos os casos, o conjunto de ações disponíveis ao agente pode ser restringido. Por exemplo, o estado de um saldo bancário pode ser restrito a ser positivo; se o valor atual do estado é 3 e a transição de estado tenta reduzir o valor em 4, essa transição não será permitida.

Quando o desempenho do agente é comparado ao de um agente que atua de modo ótimo, a diferença de desempenho resulta no conceito de arrependimento (regret). Para agir de forma quase ótima, o agente deve raciocinar sobre as consequências de longo prazo de suas ações (isto é, maximizar recompensas futuras), embora a recompensa imediata associada possa ser negativa.

Assim, o aprendizado por reforço é particularmente adequado para problemas que envolvem a troca entre recompensas de longo e curto prazo. Ele já foi aplicado com sucesso a diversos problemas, incluindo armazenamento de energia, controle de robôs, geradores fotovoltaicos, backgammon, damas, Go (AlphaGo) e sistemas de direção autônoma.

Dois elementos tornam o aprendizado por reforço poderoso: o uso de amostras para otimizar desempenho e o uso de aproximação de função para lidar com ambientes grandes. Graças a esses dois componentes, o AR pode ser usado em ambientes grandes nas seguintes situações:

Um modelo do ambiente é conhecido, mas não se dispõe de uma solução analítica; Somente um modelo de simulação do ambiente é fornecido (assunto de otimização baseada em simulação); A única forma de coletar informações sobre o ambiente é interagindo com ele.

Os dois primeiros problemas poderiam ser considerados problemas de planejamento (já que algum tipo de modelo está disponível), enquanto o último poderia ser considerado realmente um problema de aprendizado. Entretanto, o aprendizado por reforço converte ambos os problemas de planejamento em problemas de aprendizado de máquina.

Exploração A troca entre exploração e exploração foi estudada principalmente através do problema multi-armed bandit e para processos de decisão de Markov com espaço de estados finito em Burnetas e Katehakis (1997).

O aprendizado por reforço exige mecanismos de exploração inteligentes; selecionar ações aleatoriamente, sem referência a uma distribuição de probabilidade estimada, apresenta baixo desempenho. O caso de processos de decisão de Markov finitos (pequenos) é relativamente bem compreendido. Entretanto, devido à falta de algoritmos que escalem bem com o número de estados (ou que escalem para problemas com espaço de estados infinito), métodos simples de exploração são os mais práticos.

Um desses métodos é -ganancioso (\varepsilon-greedy), onde é um parâmetro que controla a quantidade de exploração vs. exploração. Com probabilidade , escolhe-se a exploração, e o agente escolhe a ação que acredita ter o melhor efeito de longo prazo (desempates entre ações são escolhidos uniformemente ao acaso). Por outro lado, com probabilidade , a exploração é escolhida, e a ação é selecionada uniformemente ao acaso. Normalmente, é um parâmetro fixo, mas pode ser ajustado de acordo com um cronograma (levando o agente a explorar cada vez menos) ou adaptado com base em heurísticas.

Algoritmos para aprendizado de controle Mesmo desconsiderando a questão da exploração e assumindo que o estado é observável (assumido daqui em diante), o problema ainda é usar a experiência passada para descobrir quais ações levam a maiores recompensas acumuladas.

Critério de optimalidade

Política A seleção de ação do agente é modelada como um mapeamento chamado política:

O mapa de política fornece a probabilidade de realizar a ação ao estar no estado . Também existem políticas determinísticas , para as quais denota a ação que deve ser executada no estado .

Função de valor de estado A função de valor de estado é definida como o retorno descontado esperado a partir do estado , ou seja, , seguindo sucessivamente a política . Em termos gerais, a função de valor estima "o quão bom" é estar em um estado dado.

onde a variável aleatória denota o retorno descontado, definido como a soma de recompensas futuras descontadas:

onde é a recompensa pela transição do estado para , e é a taxa de desconto. é menor que 1, de modo que recompensas distantes no futuro têm peso menor do que recompensas imediatas.

O algoritmo deve encontrar uma política que maximize o retorno descontado esperado. A partir da teoria de processos de decisão de Markov, sabe-se que, sem perda de generalidade, a busca pode ser restringida ao conjunto de políticas chamadas estacionárias. Uma política é estacionária se a distribuição de ações retornada por ela depende apenas do último estado visitado (considerado o histórico de observações do agente). A busca pode ser ainda mais restringida a políticas determinísticas estacionárias. Uma política estacionária determinística seleciona ações de forma determinística com base no estado atual. Como toda política desse tipo pode ser identificada com um mapeamento do conjunto de estados para o conjunto de ações, nenhuma generalidade é perdida ao restringir a busca a esses mapeamentos.

Força bruta A abordagem de força bruta envolve dois passos:

Para cada política possível, amostrar retornos enquanto a segue Escolher a política com o maior retorno descontado esperado

Um problema é que o número de políticas pode ser muito grande, ou mesmo infinito. Outro é que a variância dos retornos pode ser grande, exigindo muitas amostras para estimar precisamente o retorno descontado de cada política.

Esses problemas podem ser amenizados se assumirmos alguma estrutura e permitirmos que as amostras geradas a partir de uma política influenciem as estimativas feitas para outras. As duas abordagens principais para alcançar isso são estimação de função de valor e busca direta por política.

Função de valor

Abordagens baseadas em função de valor tentam encontrar uma política que maximize o retorno descontado, mantendo um conjunto de estimativas de retornos descontados esperados para alguma política (geralmente a "atual" [on-policy] ou a ótima [off-policy]).

Esses métodos se baseiam na teoria de processos de decisão de Markov, em que a otimalidade é definida de maneira mais forte do que a definição acima: Uma política é ótima se atinge o melhor retorno descontado esperado a partir de qualquer estado inicial (isto é, distribuições iniciais não influenciam essa definição). Novamente, uma política ótima sempre pode ser encontrada entre as políticas estacionárias.

Para definir a otimalidade formalmente, define-se o valor de estado de uma política por

onde representa o retorno descontado associado a seguir a partir do estado inicial . Definindo como o valor de estado máximo possível de , onde pode mudar,

Uma política que atinge esses valores de estado ótimos em cada estado é chamada ótima. Claramente, uma política ótima nesse sentido também é ótima no sentido de que maximiza o retorno descontado esperado, pois , em que é um estado amostrado aleatoriamente da distribuição de estados iniciais (de modo que ).

Embora valores de estado sejam suficientes para definir a otimalidade, é útil definir valores de ação. Dado um estado , uma ação e uma política , o valor de ação do par sob é definido por

onde agora representa o retorno descontado associado a tomar primeiro a ação no estado e então seguir dali em diante.