Usuário(a):Chapulinaaa/Aprendizado por reforço

Introdução

Aprendizado por reforço, ou aprendizagem por reforço, é uma área de aprendizado de máquina inspirada pela psicologia behaviorista, interessada na forma como agentes de software devem realizar ações em um ambiente de modo a maximizar alguma noção de recompensa cumulativa. O problema, devido a sua generalidade, é estudado em muitas outras disciplinas, tais como a teoria dos jogos, teoria de controle, investigação operacional, teoria da informação, otimização baseada em simulação, sistemas multiagentes, swarm intelligence, estatística, e algoritmos genéticos. Na pesquisa de operações e literatura de controle, o campo onde métodos de reforço de aprendizagem são estudados se chama programação dinâmica aproximada. O problema tem sido estudado na teoria de controle ótimo, apesar da maioria dos estudos estar preocupada com a existência de soluções ótimas e a sua caracterização, e não com os aspectos de aprendizagem ou aproximação. Em economia e teoria dos jogos, aprendizado por reforço pode ser usado para explicar como equilíbrio pode surgir sob limitação de racionalidade.

Exploração

Em aprendizado de máquina, o ambiente é normalmente concebido como um processo de decisão de Markov (em inglês, Markov Decision Process, MDP), pois muitos algoritmos de aprendizado por reforço neste contexto utilizam técnicas de programação dinâmica. A diferença principal entre as técnicas clássicas e algoritmos de reforço de aprendizagem é que estes últimos não precisam de conhecimento sobre o MDP e atacam MDPs onde métodos exatos tornam-se inviáveis.

Aprendizado por reforço difere do aprendizado supervisionado padrão, onde pares de entrada/saída nunca são apresentados, nem ações sub-óptimas explicitamente corrigidas. Além disso, há um foco no desempenho online, que consiste em encontrar um equilíbrio entre explorar (um território inexplorado) e usufruir (do conhecimento atual). O equilíbrio entre explorar e usufruir em aprendizagem por reforço foi bem estudada através do problema multi-armed bandit e em MDPs finitos.

Critério de optimização

O modelo básico de aprendizagem por reforço consiste em:

1. um conjunto de estados de ambiente e de agente ${\displaystyle }$;
2. um conjunto de ações ${\displaystyle }$ do agente;
3. políticas de transição entre estados para ações;
4. regras que determinam a recompensa imediata escalar de transição; e
5. regras que descrevem o que o agente observa.

As regras são muitas vezes estocásticas. A observação envolve tipicamente a recompensa imediata escalar associada com a última transição. Em muitas obras, também se pressupõe que o agente observe o estado ambiental atual, no caso falamos de observabilidade total, e no case oposto falamos em observabilidade parcial. Às vezes, o conjunto de ações disponíveis para o agente é restrito (por exemplo, você não pode gastar mais dinheiro do que o que você possui).

Um agente em aprendizado por reforço interage com o seu ambiente em passos de tempo discretos. Em cada momento ${\displaystyle }$, o agente recebe uma observação ${\displaystyle }$, que normalmente inclui a recompensa ${\displaystyle }$. Em seguida, ele escolhe uma ação ${\displaystyle }$ a partir do conjunto de ações disponíveis, que posteriormente é enviada para o ambiente. O ambiente move para um novo estado ${\displaystyle }$ e a recompensa ${\displaystyle }$ associada com a transição ${\displaystyle }$ é determinada. O objetivo de um agente em aprendizado por reforço é coletar a maior recompensa possível. O agente pode escolher qualquer ação como função da história e pode até mesmo escolher uma ação aleatória.

Quando o desempenho do agente é comparado com o de um agente que atua de forma otimizada desde o início, a diferença no desempenho gera a noção de arrependimento. Note que, a fim de agir perto do ideal, o agente tem que racionalizar sobre as consequências a longo prazo de suas ações: a fim de maximizar o rendimento futuro era melhor eu ir para a escola agora, apesar da recompensa monetária imediata associada poder ser negativa.

Assim, o aprendizado por reforço é particularmente adequado para problemas incluem um trade-off de recompensa a longo prazo versus curto prazo. Ele tem sido aplicado com sucesso para vários problemas, incluindo o controle de robôs, agendamento de elevadores, telecomunicações, gamão, damas (Sutton & Barto 1998, Chapter 11) e go (AlphaGo).

Dois componentes fazem a aprendizagem por reforço poderosa: A utilização de amostras para otimizar o desempenho e a utilização da aproximação de funções  para lidar com ambientes grandes. Graças a estes dois componentes-chave, a aprendizagem por reforço pode ser usada em ambientes de grandes dimensões em qualquer das seguintes situações:

• Um modelo do ambiente é conhecido, mas uma solução analítica não está disponível;
• Apenas um modelo de simulação do ambiente é dado (o assunto de simulação baseada em otimização);
• A única maneira de coletar informações sobre o ambiente é interagindo com ele.

Os dois primeiros desses problemas poderiam ser considerados problemas de planejamento (pois algum tipo de modelo está disponível), enquanto o último pode ser considerado como um verdadeiro problema de aprendizagem. No entanto, sob uma metodologia de aprendizagem por reforço, ambos problemas de planejamento seriam convertidos em problemas de aprendizado de máquina.

O problema de aprendizagem por reforço conforme descrito requer mecanismos de exploração inteligentes. Sabe-se que a seleção aleatória de ações, sem referência a uma estimativa de distribuição de probabilidade, geralmente resulta em um desempenho muito fraco. O caso de (pequenos) processos de decisão de Markov finitos é relativamente bem compreendido até agora. No entanto, devido à falta de algoritmos comprovadamente escalariam bem com o número de estados (ou escalariam para problemas com estado de espaços infinito), na prática, as pessoas recorrem a simples métodos de exploração. Um tal método é ${\displaystyle }$-greedy (ganancioso), quando o agente escolhe a ação que ele acredita que tem o melhor efeito de longo prazo com probabilidade ${\displaystyle }$, e no caso contrário, escolhe uma ação aleatória uniformemente. Aqui, ${\displaystyle }$ é um dos parâmetros de ajuste, que às vezes é alterado de acordo com uma programação fixa (fazendo com que o agente explore menos conforme o tempo passa), ou de forma adaptativa com base em alguma heurística.

Mesmo se o problema da exploração for desconsiderado e mesmo se o estado for observável (que assumimos a partir de agora), o problema de descobrir quais ações são boas com base na experiência do passado permanece.

Por simplicidade, suponha por um momento que o problema estudado é episódico, um episódio termina quando algum estado terminal é atingido. Suponha, ainda, que independentemente do curso de ações que o agente tomar, a extinção é inevitável. Em algumas condições de regularidade leves, a expectativa da recompensa total é então bem definida, para qualquer política e qualquer distribuição inicial pelos estados. Aqui, uma política refere-se a um mapeamento que atribui alguma distribuição de probabilidade sobre as ações para todas as histórias possíveis.

Dada uma determinada distribuição inicial ${\displaystyle }$podemos portanto atribuir o retorno esperado ${\displaystyle }$ à política ${\displaystyle }$:

${\displaystyle }$

onde a variável aleatória ${\displaystyle }$ denota o retorno e é definida por

${\displaystyle }$

onde ${\displaystyle }$ é a recompensa recebida após a ${\displaystyle }$-ésima transição, o estado inicial é escolhido de forma aleatória a partir de ${\displaystyle }$ e ações são selecionadas pela política ${\displaystyle }$. Aqui, ${\displaystyle }$ indica o tempo (aleatório) quando um estado terminal é alcançado, ou seja, o tempo quando o episódio termina.

No caso de problemas não-episódicos o retorno muitas vezes é descontado,

${\displaystyle }$

dando origem ao total esperado critério de recompensa descontado. Aqui ${\displaystyle }$ é o chamado fator de desconto. Já que o retorno sem desconto é um caso especial de desconto com retorno, a partir de agora nós assumimos que há desconto. Embora isto pareça inocente o suficiente, o desconto é de fato problemático se estamos preocupados com desempenho on-line. Isso porque o desconto faz com que os passos de tempo iniciais sejam mais importantes. Como um agente de aprendizagem é propenso a cometer erros durante os primeiros passos após a sua "vida" começa, nenhum algoritmo de aprendizagem desinformado pode atingir um desempenho quase ideal com desconto, mesmo se a classe dos ambientes é restrita à MDPs finitos. (Isto não significa, porém, que, dado tempo suficiente, uma agente de aprendizagem não consiga entender como agir perto do ideal, se o tempo fosse reiniciado.)

Em seguida, o problema é especificar um algoritmo que possa ser usado para localizar uma política com o máximo de retorno esperado. A partir da teoria de MDPs sabe-se que, sem perda de generalidade, a pesquisa pode se restringir ao conjunto das políticas estacionárias. Uma política é chamada de estacionária se a distribuição de ações retornada por ela depende apenas do último estado que visitou (que é parte da observação da história do agente, pela nossa suposição simplificada). Na verdade, a busca pode ser ainda mais restringida a políticas estacionárias determinísticas. Uma política estacionária determinística é aquela que de maneira determinística seleciona ações com base no estado atual. Já que este tipo de política pode ser identificada com um mapeamento do conjunto de estados para o conjunto de ações, estas políticas podem ser identificados com tais mapeamentos sem perda de generalidade.

A abordagem da força bruta envolve as seguintes etapas:

1. Para cada uma das políticas possíveis, experimente retornos enquanto segue
   
2. Escolha a política com o maior retorno esperado

Um problema com isto é que o número de políticas pode ser extremamente grande, até mesmo infinito. Outro é que a variância dos retornos pode ser grande, e nesse caso um grande número de amostras é necessário para estimar com precisão o retorno de cada política.

Estes problemas podem ser amenizados se assumirmos alguma estrutura e, talvez, permitirmos que exemplos gerados a partir de uma política influenciem as estimativas feitas para outra. As duas abordagens principais para atingir isso são estimativa de função de valor e pesquisa direta de política.

Abordagens de função de valor tentam encontrar uma política que maximize o retorno através da manutenção de um conjunto de estimativas de retornos esperados para alguma política (normalmente ou o "atual" (on-policy) ou ótimo (off-policy)).

Estes métodos baseiam-se na teoria de MDPs, onde a excelência é definida em um sentido que é mais forte do que o anterior: se diz que uma política é ideal se obtém o melhor retorno esperado de qualquer estado inicial (por exemplo, distribuições iniciais não desempenham nenhum papel nessa definição). Novamente, pode-se sempre encontrar uma política ótima entre políticas estacionárias.

Para definir a excelência de uma maneira formal, definimos o valor de uma política ${\displaystyle }$ como

${\displaystyle }$

onde ${\displaystyle }$ representa o retorno aleatório associado com a ${\displaystyle }$ seguinte a partir do estado inicial ${\displaystyle }$. Definir ${\displaystyle }$ como o valor máximo possível de ${\displaystyle }$, onde ${\displaystyle }$ é permitido alterar:

${\displaystyle }$

Uma política que atinge esses valores ideais em cada estado é chamada de ótima. Claramente, uma política que é ótima neste sentido também é ótima no sentido de que maximiza o retorno esperado ${\displaystyle }$, já que ${\displaystyle }$, onde ${\displaystyle }$ é um estado escolhido aleatoriamente da distribuição ${\displaystyle }$.

Veja também

• Multi-agente
• Inteligência artificial distribuída