Q-learning

Na inteligência artificial , mais precisamente no aprendizado de máquina , o Q-learning é uma técnica de aprendizado por reforço . Esta técnica não requer nenhum modelo inicial do ambiente . A letra 'Q' denota a função que mede a qualidade de uma ação realizada em um determinado estado do sistema.

Descrição

Este método de aprendizagem permite que você aprenda uma política, que indica qual ação executar em cada estado do sistema. Ele funciona aprendendo uma função de valor de ação de estado observada que determina o ganho potencial, ou seja, a recompensa de longo prazo , trazida pela realização de uma determinada ação em um determinado estado , seguindo uma política ótima. Quando esta função de valor de estado de ação é conhecida / aprendida pelo agente, a política ótima pode ser construída selecionando a ação de valor máximo para cada estado, ou seja, selecionando a ação que maximiza o valor quando o agente está no estado . $Q$ ${\ displaystyle Q (s, a)}$ $no$ $s$ $no$ ${\ displaystyle Q (s, a)}$ $s$

Um dos pontos fortes da -aprendizagem é que permite comparar as prováveis recompensas de realizar ações acessíveis sem ter nenhum conhecimento inicial do ambiente. Em outras palavras, embora o sistema seja modelado como um processo de decisão de Markov (concluído), o agente aprende não sabe e o algoritmo - o aprendizado não o usa. $Q$ $Q$

Essa noção de aprendizado por recompensa foi originalmente introduzida na tese de Watkins em 1989. É uma variante do aprendizado por diferença temporal. Posteriormente, foi comprovado que - a aprendizagem converge para uma política ótima, ou seja, leva à maximização da recompensa total das etapas sucessivas. $Q$

Algoritmo

A situação consiste em um agente, um conjunto de estados e ações . Ao realizar uma ação , o agente passa de um estado para outro e recebe uma recompensa (é um valor numérico). O objetivo do agente é maximizar sua recompensa total. Isso é conseguido aprendendo a ação ideal para cada estado. A ação ideal para cada estado é aquela com a maior recompensa de longo prazo. Essa recompensa é a soma ponderada da expectativa matemática das recompensas de cada etapa futura do estado atual. O peso de cada etapa pode ser onde está o atraso entre a etapa atual e a futura e um número entre 0 e 1 (ou seja, ) chamado de fator de desconto . $S$ $NO$ $a \ em A$ $s$ $s '$ $r$ ${\ displaystyle \ gamma ^ {\ Delta t}}$ $\ Delta t$ $\gama$ ${\ displaystyle 0 \ leq \ gamma \ leq 1}$

O algoritmo calcula uma função de valor de estado de ação:

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

Antes de o aprendizado começar, a função é inicializada arbitrariamente. Então, a cada escolha de ação, o agente observa a recompensa e o novo estado (que depende do estado anterior e da ação atual). O coração do algoritmo é uma atualização da função de valor . A definição da função de valor é atualizada a cada etapa da seguinte forma: $Q$

{\ displaystyle Q [s, a]: = (1- \ alpha) Q [s, a] + \ alpha \ left (r + \ gamma \ max _ {a '} Q [s', a '] \ right )}

onde é o novo estado, é o estado anterior, é a ação escolhida, é a recompensa recebida pelo agente, é um número entre 0 e 1, denominado fator de aprendizagem , e é o fator de atualização . $s '$ $s$ $no$ $r$ $\alfa$ $\gama$

Um episódio do algoritmo termina quando está em um estado final. No entanto, - a aprendizagem também pode ser aplicada a tarefas não episódicas. Se o fator de desconto for menor que 1, o valor do estado de ação é finito, mesmo para o infinito. $s _ {{t + 1}}$ $Q$ $\ Delta t$

NB: Para cada estado final , o valor de nunca é atualizado e mantém seu valor inicial. Normalmente, é inicializado em zero. ${\ displaystyle s_ {f}}$ ${\ displaystyle Q (s_ {f}, a)}$ ${\ displaystyle Q (s_ {f}, a)}$

Pseudo-código

Aqui está o pseudo-código do Q-learning.

initialiser Q[s, a] pour tout état s, toute action a de façon arbitraire, mais Q(état terminal, a) = 0 pour toute action a répéter //début d'un épisode initialiser l'état s répéter //étape d'un épisode choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy) exécuter l'action a observer la récompense r et l'état s' Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)] s := s' a := a' jusqu'à ce que s soit l'état terminal

Influência das variáveis no algoritmo

Fator de aprendizagem

O fator de aprendizagem determina o quanto as novas informações calculadas irão superar as antigas. Se = 0, o agente não aprende nada. Por outro lado, se = 1, o agente sempre ignora tudo o que aprendeu e considerará apenas a última informação. $\alfa$ $\alfa$ $\alfa$

Em um ambiente determinístico, a velocidade de aprendizagem é ótima. Quando o problema é estocástico, o algoritmo converge sob certas condições dependendo da velocidade de aprendizado. Na prática, muitas vezes essa velocidade corresponde a toda a duração do processo. ${\ displaystyle \ alpha _ {t} (s, a) = 1}$ ${\ displaystyle \ alpha _ {t} (s, a) = 0,1}$

Factor de desconto

O fator de desconto $γ$ determina o tamanho das recompensas futuras. Um fator de 0 tornaria o agente míope, considerando apenas as recompensas atuais, enquanto um fator próximo a 1 também traria as recompensas mais distantes. Se o fator de desconto for próximo ou igual a 1, o valor de pode divergir. $Q$

Extensões e variantes

Double Q- learning

Como o Q- learning usa o estimador máximo, o Q- learning superestima o valor das ações e, portanto, em ambientes ruidosos, o aprendizado é lento. Esse problema é resolvido na variante chamada double Q- learning, que usa duas funções de avaliação e é aprendida em dois conjuntos diferentes de experiências. A atualização é feita transversalmente: ${\ 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) .}

Como o valor estimado é avaliado por outra política, o problema da superestimação está resolvido. O aprendizado do algoritmo definido pode ser feito usando técnicas de aprendizado profundo, resultando em DQNs ( redes Q profundas ). Podemos então ter Double DQN, para obter melhor desempenho do que com o algoritmo DQN original.

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado “ Q-Learning ” ( veja a lista de autores ) .

Tambet Matiisen , “ Demystifying Deep Reforcement Learning | Laboratório de Neurociência Computacional ” , em neuro.cs.ut.ee ,19 de dezembro de 2015(acessado em 6 de abril de 2018 )
CJ Watkins, Learning from atrasado recompensas , Kings College, Cambridge, maio de 1989
(in) George F Luger, Artificial Intelligence: Structures and Strategies for complex problem solving. 5ª edição. , Addison Wesley,2005, 903 p. ( ISBN 0-321-26318-9 , leia online ) , p. 448
Watkins e Dayan, Q-learning. Machine Learning , 1992
(em) David L. Poole e Alan K. Mackworth , Artificial Intelligence , Cambridge University Press ,2009( ISBN 978-0-511-79479-7 , DOI 10.1017 / CBO9780511794797 , ler online ) , p. 469
Reinforcement Learning: An Introduction , Richard Sutton e Andrew Barto, MIT Press, 1998.
(em) Stuart J. Russell e Peter Norvig , Artificial Intelligence: A Modern Approach , Prentice Hall ,2010, Terceira ed. , 1132 p. ( ISBN 978-0-13-604259-4 ) , p. 649
Hado van Hasselt , “ Double Q-learning ”, Advances in Neural Information Processing Systems , vol. 23,2011, p. 2613-2622 ( leia online [PDF] )
Hado van Hasselt , Arthur Guez e David Silver , " Aprendizagem por reforço profundo com duplo Q-learning ", Conferência AAAI sobre Inteligência Artificial ,2015, p. 2094–2100 ( leia online [PDF] )