Q-learning - Q-learning

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

Q -learning é umalgoritmo de aprendizado por reforço sem modelo para aprender o valor de uma ação em um estado particular. Ele não requer um modelo de ambiente (portanto, "sem modelo") e pode lidar com problemas com transições estocásticas e recompensas sem exigir adaptações.

Para qualquer processo de decisão Markov finito (FMDP), Q -learning encontra uma política ótima no sentido de maximizar o valor esperado da recompensa total em todas e quaisquer etapas sucessivas, a partir do estado atual. Q -learning pode identificar uma política de seleção de ação ideal para qualquer FMDP dado, dado o tempo de exploração infinito e uma política parcialmente aleatória. "Q" refere-se à função que o algoritmo calcula - as recompensas esperadas por uma ação realizada em um determinado estado.

Aprendizagem por reforço

A aprendizagem por reforço envolve um agente , um conjunto de estados e um conjunto de ações por estado. Ao executar uma ação , o agente faz a transição de um estado para outro. Executar uma ação em um estado específico fornece ao agente uma recompensa (uma pontuação numérica). ${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle a \ in A}$

O objetivo do agente é maximizar sua recompensa total. Ele faz isso adicionando a recompensa máxima atingível em estados futuros à recompensa por atingir seu estado atual, influenciando efetivamente a ação atual pela recompensa futura em potencial. Essa recompensa potencial é uma soma ponderada dos valores esperados das recompensas de todas as etapas futuras a partir do estado atual.

A título de exemplo, considere o processo de embarque em um trem, no qual a recompensa é medida pelo valor negativo do tempo total de embarque (alternativamente, o custo de embarque no trem é igual ao tempo de embarque). Uma estratégia é entrar pela porta do trem assim que ela abrir, minimizando o tempo de espera inicial para você. Se o trem estiver lotado, no entanto, você terá uma entrada lenta após a ação inicial de entrar pela porta, já que as pessoas estão brigando com você para sair do trem enquanto você tenta embarcar. O tempo total de embarque, ou custo, é então:

• 0 segundos de tempo de espera + 15 segundos de tempo de luta

No dia seguinte, por acaso (exploração), você decide esperar e deixar outras pessoas partirem primeiro. Isso inicialmente resulta em um tempo de espera mais longo. No entanto, o tempo de luta com outros passageiros é menor. No geral, esse trajeto tem uma recompensa maior que o do dia anterior, já que o tempo total de embarque agora é:

• 5 segundos de tempo de espera + 0 segundos de tempo de luta

Por meio da exploração, apesar da ação inicial (paciente) resultar em um custo maior (ou recompensa negativa) do que na estratégia vigorosa, o custo geral é menor, revelando assim uma estratégia mais recompensadora.

Algoritmo

Tabela de Q-Learning de estados por ações que é inicializada em zero, então cada célula é atualizada por meio de treinamento.

Após as etapas no futuro, o agente decidirá a próxima etapa. O peso para esta etapa é calculado como , onde (o fator de desconto ) é um número entre 0 e 1 ( ) e tem o efeito de avaliar as recompensas recebidas mais cedo do que as recebidas mais tarde (refletindo o valor de um "bom começo"). também pode ser interpretado como a probabilidade de sucesso (ou sobrevivência) em cada etapa . ${\ displaystyle \ Delta t}$${\ displaystyle \ gamma ^ {\ Delta t}}$${\ displaystyle \ gamma}$${\ displaystyle 0 \ leq \ gamma \ leq 1}$${\ displaystyle \ gamma}$${\ displaystyle \ Delta t}$

O algoritmo, portanto, tem uma função que calcula a qualidade de uma combinação estado-ação:

${\ displaystyle Q: S \ times A \ to \ mathbb {R}}$.

Antes de começar a aprendizagem, é inicializado com um valor fixo possivelmente arbitrário (escolhido pelo programador). Então, a cada vez que o agente seleciona uma ação , observa uma recompensa , entra em um novo estado (que pode depender tanto do estado anterior quanto da ação selecionada) e é atualizado. O núcleo do algoritmo é uma equação de Bellman como uma atualização de iteração de valor simples , usando a média ponderada do valor antigo e as novas informações: ${\ displaystyle Q}$${\ displaystyle t}$${\ displaystyle a_ {t}}$${\ displaystyle r_ {t}}$${\ displaystyle s_ {t + 1}}$${\ displaystyle s_ {t}}$${\ displaystyle Q}$

${\ displaystyle Q ^ {new} (s_ {t}, a_ {t}) \ leftarrow \ underbrace {Q (s_ {t}, a_ {t})} _ {\ text {old value}} + \ underbrace { \ alpha} _ {\ text {taxa de aprendizagem}} \ cdot \ overbrace {{\ bigg (} \ underbrace {\ underbrace {r_ {t}} _ {\ text {recompensa}} + \ underbrace {\ gamma} _ { \ text {fator de desconto}} \ cdot \ underbrace {\ max _ {a} Q (s_ {t + 1}, a)} _ {\ text {estimativa do valor futuro ótimo}}} _ {\ text {novo valor (alvo de diferença temporal)}} - \ underbrace {Q (s_ {t}, a_ {t})} _ {\ text {valor antigo}} {\ bigg)}} ^ {\ text {diferença temporal}}}$

onde está a recompensa recebida ao mudar de um estado para outro e é a taxa de aprendizagem . ${\ displaystyle r_ {t}}$${\ displaystyle s_ {t}}$${\ displaystyle s_ {t + 1}}$${\ displaystyle \ alpha}$ ${\ displaystyle (0 <\ alpha \ leq 1)}$

Observe que é a soma de três fatores: ${\ displaystyle Q ^ {novo} (s_ {t}, a_ {t})}$

• ${\ displaystyle (1- \ alpha) Q (s_ {t}, a_ {t})}$: o valor atual ponderado pela taxa de aprendizagem. Valores da taxa de aprendizagem próximos a 1 tornam as mudanças mais rápidas.${\ displaystyle Q}$
• ${\ displaystyle \ alpha \, r_ {t}}$: a recompensa a ser obtida se a ação for realizada quando no estado (ponderada pela taxa de aprendizagem)${\ displaystyle r_ {t} = r (s_ {t}, a_ {t})}$${\ displaystyle a_ {t}}$${\ displaystyle s_ {t}}$
• ${\ displaystyle \ alpha \ gamma \ max _ {a} Q (s_ {t + 1}, a)}$: a recompensa máxima que pode ser obtida do estado (ponderada pela taxa de aprendizagem e fator de desconto)${\ displaystyle s_ {t + 1}}$

Um episódio do algoritmo termina quando o estado é um estado final ou terminal . No entanto, o Q- learning também pode aprender em tarefas não episódicas (como resultado da propriedade de séries infinitas convergentes). Se o fator de desconto for menor que 1, os valores da ação são finitos, mesmo que o problema possa conter loops infinitos. ${\ displaystyle s_ {t + 1}}$

Para todos os estados finais , nunca é atualizado, mas é definido com o valor de recompensa observado para o estado . Na maioria dos casos, pode ser igual a zero. ${\ displaystyle s_ {f}}$${\ displaystyle Q (s_ {f}, a)}$${\ displaystyle r}$${\ displaystyle s_ {f}}$${\ displaystyle Q (s_ {f}, a)}$

Influência de variáveis

Taxa de Aprendizagem

A taxa de aprendizado ou o tamanho do passo determinam em que medida as informações recém-adquiridas substituem as informações antigas. Um fator de 0 faz com que o agente não aprenda nada (explorando exclusivamente o conhecimento prévio), enquanto um fator de 1 faz com que o agente considere apenas as informações mais recentes (ignorando o conhecimento anterior para explorar possibilidades). Em ambientes totalmente determinísticos , uma taxa de aprendizado de é ótima. Quando o problema é estocástico , o algoritmo converge sob algumas condições técnicas na taxa de aprendizado que exige que ele diminua para zero. Na prática, muitas vezes é usada uma taxa de aprendizado constante, como para todos . ${\ displaystyle \ alpha _ {t} = 1}$${\ displaystyle \ alpha _ {t} = 0,1}$${\ displaystyle t}$

Factor de desconto

O fator de desconto determina a importância das recompensas futuras. Um fator de 0 tornará o agente "míope" (ou míope) considerando apenas as recompensas atuais, isto é (na regra de atualização acima), enquanto um fator próximo de 1 o fará se esforçar por uma alta recompensa a longo prazo. Se o fator de desconto atingir ou ultrapassar 1, os valores da ação podem divergir. Pois , sem um estado terminal, ou se o agente nunca chega a um, todas as histórias do ambiente tornam-se infinitamente longas, e as utilidades com recompensas aditivas e não descontadas geralmente tornam-se infinitas. Mesmo com um fator de desconto apenas ligeiramente inferior a 1, o aprendizado da função Q leva à propagação de erros e instabilidades quando a função de valor é aproximada com uma rede neural artificial . Nesse caso, começar com um fator de desconto menor e aumentá-lo em direção ao seu valor final acelera o aprendizado. ${\ displaystyle \ gamma}$${\ displaystyle r_ {t}}$${\ displaystyle \ gamma = 1}$

Condições iniciais ( Q ₀ )

Como o Q- learning é um algoritmo iterativo, ele assume implicitamente uma condição inicial antes que ocorra a primeira atualização. Valores iniciais altos, também conhecidos como "condições iniciais otimistas", podem encorajar a exploração: não importa qual ação for selecionada, a regra de atualização fará com que ela tenha valores menores que a outra alternativa, aumentando assim sua probabilidade de escolha. A primeira recompensa pode ser usada para redefinir as condições iniciais. De acordo com essa ideia, a primeira vez que uma ação é realizada, a recompensa é usada para definir o valor de . Isso permite o aprendizado imediato no caso de recompensas determinísticas fixas. Espera-se que um modelo que incorpora redefinição das condições iniciais (RIC) preveja o comportamento dos participantes melhor do que um modelo que assume qualquer condição inicial arbitrária (AIC). RIC parece ser consistente com o comportamento humano em experimentos de escolha binária repetidos. ${\ displaystyle r}$${\ displaystyle Q}$

Implementação

Q -learning em sua forma mais simples armazena dados em tabelas. Essa abordagem vacila com o aumento do número de estados / ações, pois a probabilidade de o agente visitar um determinado estado e executar uma determinada ação é cada vez menor.

Aproximação de função

O Q- learning pode ser combinado com a aproximação de função . Isso torna possível aplicar o algoritmo a problemas maiores, mesmo quando o espaço de estados é contínuo.

Uma solução é usar uma rede neural artificial (adaptada) como um aproximador de função. A aproximação de funções pode acelerar o aprendizado em problemas finitos, devido ao fato de que o algoritmo pode generalizar experiências anteriores para estados não vistos anteriormente.

Quantização

Outra técnica para diminuir o espaço de estado / ação quantiza os valores possíveis. Considere o exemplo de aprender a equilibrar uma vara no dedo. Descrever um estado em um determinado ponto no tempo envolve a posição do dedo no espaço, sua velocidade, o ângulo do bastão e a velocidade angular do bastão. Isso produz um vetor de quatro elementos que descreve um estado, ou seja, um instantâneo de um estado codificado em quatro valores. O problema é que infinitamente muitos estados possíveis estão presentes. Para reduzir o espaço possível de ações válidas, vários valores podem ser atribuídos a um balde. A distância exata do dedo de sua posição inicial (-Infinito ao infinito) não é conhecida, mas sim se está longe ou não (Perto, Longe).

História

Q -learning foi introduzido por Chris Watkins em 1989. Uma prova de convergência foi apresentada por Watkins e Peter Dayan em 1992.

Watkins estava abordando “Aprendendo com recompensas atrasadas”, o título de sua tese de doutorado. Oito anos antes, em 1981, o mesmo problema, sob o nome de “Aprendizagem por reforço retardada”, foi resolvido pelo Crossbar Adaptive Array (CAA) de Bozinovski. A matriz de memória era a mesma oito anos depois da mesa Q do Q-learning. A arquitetura introduziu o termo “avaliação de estado” na aprendizagem por reforço. O algoritmo de aprendizagem crossbar, escrito em pseudocódigo matemático no papel, em cada iteração realiza o seguinte cálculo: ${\ displaystyle W = \ | w (a, s) \ |}$

• Em estado de executar a acção de um ;
• Recebe os estados de conseqüência ' ;
• Avaliação de estado de computação ;${\ displaystyle v (s ')}$
• Atualize o valor da barra transversal .${\ displaystyle w '(a, s) = w (a, s) + v (s')}$

O termo “reforço secundário” é emprestado da teoria de aprendizagem animal, para modelar valores de estado via retropropagação : o valor de estado da situação de consequência é retropropagado para as situações encontradas anteriormente. CAA calcula valores de estado verticalmente e ações horizontalmente (a "barra transversal"). Gráficos de demonstração mostrando estados contidos de aprendizado de reforço atrasado (estados desejáveis, indesejáveis ​​e neutros), que foram calculados pela função de avaliação de estado. Este sistema de aprendizagem foi o precursor do algoritmo Q-learning. ${\ displaystyle v (s ')}$

Em 2014, o Google DeepMind patenteou um aplicativo de Q-learning para aprendizado profundo , intitulado "deep reforço learning" ou "deep Q-learning", que pode jogar jogos Atari 2600 em níveis humanos especializados.

Variantes

Deep Q-learning

O sistema DeepMind usava uma rede neural convolucional profunda , com camadas de filtros convolucionais lado a lado para imitar os efeitos dos campos receptivos. A aprendizagem por reforço é instável ou divergente quando um aproximador de função não linear, como uma rede neural, é usado para representar Q. Essa instabilidade vem das correlações presentes na sequência de observações, o fato de que pequenas atualizações em Q podem alterar significativamente a política do agente e a distribuição de dados e as correlações entre Q e os valores alvo.

A técnica usava repetição de experiência, um mecanismo inspirado biologicamente que usa uma amostra aleatória de ações anteriores em vez da ação mais recente para prosseguir. Isso remove as correlações na sequência de observação e suaviza as mudanças na distribuição de dados. As atualizações iterativas ajustam Q em relação aos valores de destino que são atualizados apenas periodicamente, reduzindo ainda mais as correlações com o destino.

Double Q-learning

Como o valor futuro máximo aproximado da ação no Q-learning é avaliado usando a mesma função Q da política de seleção de ação atual, em ambientes ruidosos o Q-learning pode às vezes superestimar os valores da ação, retardando o aprendizado. Uma variante chamada Double Q-learning foi proposta para corrigir isso. Double Q-learning é um algoritmo de aprendizagem por reforço fora da política , onde uma política diferente é usada para avaliação de valor daquela que é usada para selecionar a próxima ação.

Na prática, duas funções de valor separadas são treinadas de maneira mutuamente simétrica usando experiências separadas, e . A etapa dupla de atualização do Q-learning é então a seguinte: ${\ displaystyle Q ^ {A}}$${\ displaystyle Q ^ {B}}$

${\ displaystyle Q_ {t + 1} ^ {A} (s_ {t}, a_ {t}) = Q_ {t} ^ {A} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma Q_ {t} ^ {B} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max} } _ {a} Q_ {t} ^ {A} (s_ {t + 1}, a) \ direita) -Q_ {t} ^ {A} (s_ {t}, a_ {t}) \ direita)}$, e

${\ displaystyle Q_ {t + 1} ^ {B} (s_ {t}, a_ {t}) = Q_ {t} ^ {B} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma Q_ {t} ^ {A} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max} } _ {a} Q_ {t} ^ {B} (s_ {t + 1}, a) \ direita) -Q_ {t} ^ {B} (s_ {t}, a_ {t}) \ direita). }$

Agora, o valor estimado do futuro descontado é avaliado usando uma política diferente, que resolve o problema da superestimação.

Esse algoritmo foi posteriormente modificado em 2015 e combinado com aprendizado profundo , como no algoritmo DQN, resultando em Double DQN, que supera o algoritmo DQN original.

Outros

Adiada Q-learning é uma implementação alternativa da linha Q -learning algoritmo, com aprendizagem provavelmente aproximadamente correto (PAC) .

Greedy GQ é uma variante do Q- learning para usar em combinação com a aproximação de função (linear). A vantagem do Greedy GQ é que a convergência é garantida mesmo quando a aproximação da função é usada para estimar os valores da ação.

Distributivo Q-learning é uma variante do Q Learning que busca modelar a distribuição de retornos em vez do retorno esperado de cada ação. Foi observado que facilita a estimativa por redes neurais profundas e pode permitir métodos de controle alternativos, como o controle sensível ao risco.

Limitações

O algoritmo padrão de Q-learning (usando uma tabela) se aplica apenas a ações discretas e espaços de estado. A discretização desses valores leva a um aprendizado ineficiente, em grande parte devido à maldição da dimensionalidade . No entanto, existem adaptações do Q-learning que tentam resolver esse problema, como o Q-Learning com rede neural cabeada. ${\ displaystyle Q}$

Veja também

• Aprendizagem por reforço
• Aprendizagem de diferença temporal
• SARSA
• Dilema do prisioneiro iterado
• Teoria do jogo

Referências

links externos

• Watkins, CJCH (1989). Aprendendo com recompensas atrasadas. Tese de doutorado, Cambridge University, Cambridge, Inglaterra.
• Strehl, Li, Wiewiora, Langford, Littman (2006). Aprendizagem por reforço sem modelo PAC
• Aprendizagem por Reforço: Uma Introdução de Richard Sutton e Andrew S. Barto, um livro online. Consulte "6.5 Q-Learning: Controle TD fora da política" .
• Piqle: uma plataforma Java genérica para aprendizado por reforço
• Reinforcement Learning Maze , uma demonstração de como guiar uma formiga através de um labirinto usando Q -learning
• Trabalho de Q- learning por Gerald Tesauro