Q -learning es unalgoritmo de aprendizaje por refuerzo sin modelo para aprender el valor de una acción en un estado particular. No requiere un modelo del entorno (por lo tanto, "sin modelo") y puede manejar problemas con transiciones estocásticas y recompensas sin requerir adaptaciones.
Para cualquier proceso de decisión de Markov finito (FMDP), Q -learning encuentra una política óptima en el sentido de maximizar el valor esperado de la recompensa total en todos y cada uno de los pasos sucesivos, comenzando desde el estado actual. [1] Q -learning puede identificar una política de selección de acciones óptima para cualquier FMDP dado, dado un tiempo de exploración infinito y una política parcialmente aleatoria. [1] "Q" se refiere a la función que calcula el algoritmo: las recompensas esperadas por una acción realizada en un estado determinado. [2]
Aprendizaje reforzado
El aprendizaje por refuerzo implica un agente , un conjunto de estados y un set de acciones por estado. Al realizar una acción, el agente pasa de un estado a otro. La ejecución de una acción en un estado específico proporciona al agente una recompensa (una puntuación numérica).
El objetivo del agente es maximizar su recompensa total. Lo hace agregando la recompensa máxima obtenible de estados futuros a la recompensa por lograr su estado actual, influyendo de manera efectiva en la acción actual mediante la recompensa futura potencial. Esta recompensa potencial es una suma ponderada de los valores esperados de las recompensas de todos los pasos futuros a partir del estado actual.
Como ejemplo, considere el proceso de abordar un tren, en el que la recompensa se mide por el valor negativo del tiempo total dedicado al abordaje (alternativamente, el costo de abordar el tren es igual al tiempo de abordaje). Una estrategia es entrar por la puerta del tren tan pronto como se abran, minimizando el tiempo de espera inicial para usted. Sin embargo, si el tren está lleno de gente, tendrá una entrada lenta después de la acción inicial de entrar por la puerta, ya que la gente está luchando contra usted para que abandone el tren mientras intenta abordar. El tiempo total de embarque, o costo, es entonces:
- 0 segundos de tiempo de espera + 15 segundos de tiempo de pelea
Al día siguiente, por casualidad (exploración), decides esperar y dejar que otras personas se vayan primero. Esto inicialmente da como resultado un tiempo de espera más largo. Sin embargo, el tiempo para luchar contra otros pasajeros es menor. En general, esta ruta tiene una recompensa más alta que la del día anterior, ya que el tiempo total de embarque es ahora:
- 5 segundos de tiempo de espera + 0 segundos de tiempo de pelea
A través de la exploración, a pesar de que la acción inicial (del paciente) resulta en un costo mayor (o recompensa negativa) que en la estrategia contundente, el costo general es menor, revelando así una estrategia más gratificante.
Algoritmo
Después pasos hacia el futuro, el agente decidirá el próximo paso. El peso de este paso se calcula como, dónde (el factor de descuento ) es un número entre 0 y 1 () y tiene el efecto de valorar las recompensas recibidas antes por encima de las recibidas más tarde (lo que refleja el valor de un "buen comienzo"). también se puede interpretar como la probabilidad de tener éxito (o sobrevivir) en cada paso .
El algoritmo, por tanto, tiene una función que calcula la calidad de una combinación de estado-acción:
- .
Antes de que comience el aprendizaje, se inicializa a un valor fijo posiblemente arbitrario (elegido por el programador). Entonces, en cada momento el agente selecciona una acción , observa una recompensa , entra en un nuevo estado (que puede depender tanto del estado anterior y la acción seleccionada), y se actualiza. El núcleo del algoritmo es una ecuación de Bellman como una actualización de iteración de valor simple , utilizando el promedio ponderado del valor anterior y la nueva información:
dónde es la recompensa recibida al mudarse del estado al Estado , y es la tasa de aprendizaje .
Tenga en cuenta que es la suma de tres factores:
- : el valor actual ponderado por la tasa de aprendizaje. Los valores de la tasa de aprendizaje cercanos a 1 aceleraron los cambios en Q.
- : la recompensa para obtener si acción se toma cuando en el estado (ponderado por la tasa de aprendizaje)
- : la recompensa máxima que se puede obtener del estado (ponderado por la tasa de aprendizaje y el factor de descuento)
Un episodio del algoritmo termina cuando el estado es un estado final o terminal . Sin embargo, Q -learning también puede aprender en tareas no episódicas. [ cita requerida ] Si el factor de descuento es menor que 1, los valores de acción son finitos incluso si el problema puede contener bucles infinitos.
Para todos los estados finales , nunca se actualiza, pero se establece en el valor de recompensa observado para el estado . En la mayoría de los casos, puede tomarse igual a cero.
Influencia de variables
Tasa de aprendizaje
La velocidad de aprendizaje o el tamaño del paso determina hasta qué punto la información recién adquirida prevalece sobre la información anterior. Un factor de 0 hace que el agente no aprenda nada (explotando exclusivamente el conocimiento previo), mientras que un factor de 1 hace que el agente considere solo la información más reciente (ignorando el conocimiento previo para explorar posibilidades). En entornos completamente deterministas , una tasa de aprendizaje dees óptimo. Cuando el problema es estocástico , el algoritmo converge bajo algunas condiciones técnicas en la tasa de aprendizaje que requieren que disminuya a cero. En la práctica, a menudo se utiliza una tasa de aprendizaje constante, como para todos . [3]
Factor de descuento
El factor de descuento determina la importancia de las recompensas futuras. Un factor de 0 hará que el agente sea "miope" (o miope) al considerar solo las recompensas actuales, es decir(en la regla de actualización anterior), mientras que un factor cercano a 1 hará que se esfuerce por obtener una alta recompensa a largo plazo. Si el factor de descuento alcanza o excede 1, los valores de acción pueden divergir. Para, sin un estado terminal, o si el agente nunca llega a uno, todas las historias ambientales se vuelven infinitamente largas y las utilidades con recompensas aditivas y sin descuento generalmente se vuelven infinitas. [4] Incluso con un factor de descuento sólo ligeramente inferior a 1, el aprendizaje de la función Q conduce a la propagación de errores e inestabilidades cuando la función de valor se aproxima con una red neuronal artificial . [5] En ese caso, comenzar con un factor de descuento más bajo y aumentarlo hacia su valor final acelera el aprendizaje. [6]
Condiciones iniciales ( Q 0 )
Dado que Q -learning es un algoritmo iterativo, implícitamente asume una condición inicial antes de que ocurra la primera actualización. Los valores iniciales altos, también conocidos como "condiciones iniciales optimistas", [7] pueden fomentar la exploración: no importa qué acción se seleccione, la regla de actualización hará que tenga valores más bajos que la otra alternativa, aumentando así su probabilidad de elección. La primera recompensase puede utilizar para restablecer las condiciones iniciales. [8] Según esta idea, la primera vez que se realiza una acción, la recompensa se utiliza para establecer el valor de. Esto permite el aprendizaje inmediato en caso de recompensas deterministas fijas. Se espera que un modelo que incorpore el restablecimiento de las condiciones iniciales (RIC) prediga el comportamiento de los participantes mejor que un modelo que asume cualquier condición inicial arbitraria (AIC). [8] RIC parece ser consistente con el comportamiento humano en repetidos experimentos de elección binaria. [8]
Implementación
Q -learning en su forma más simple almacena datos en tablas. Este enfoque falla con un número creciente de estados / acciones, ya que la probabilidad de que el agente visite un estado en particular y realice una acción en particular es cada vez más pequeña.
Aproximación de funciones
Q -learning se puede combinar con la aproximación de funciones . [9] Esto hace posible aplicar el algoritmo a problemas más grandes, incluso cuando el espacio de estados es continuo.
Una solución es utilizar una red neuronal artificial (adaptada) como un aproximador de funciones. [10] La aproximación de funciones puede acelerar el aprendizaje en problemas finitos, debido al hecho de que el algoritmo puede generalizar experiencias anteriores a estados nunca antes vistos.
Cuantización
Otra técnica para disminuir el espacio de estado / acción cuantifica los valores posibles. Considere el ejemplo de aprender a equilibrar un palo en un dedo. Describir un estado en un determinado momento implica la posición del dedo en el espacio, su velocidad, el ángulo del palo y la velocidad angular del palo. Esto produce un vector de cuatro elementos que describe un estado, es decir, una instantánea de un estado codificado en cuatro valores. El problema es que están presentes una infinidad de estados posibles. Para reducir el espacio posible de acciones válidas, se pueden asignar varios valores a un depósito. Se desconoce la distancia exacta del dedo desde su posición inicial (-Infinito a Infinito), sino más bien si está lejos o no (Cerca, Lejos).
Historia
El Q -learning fue introducido por Chris Watkins [11] en 1989. Watkins y Dayan [12] presentaron una prueba de convergencia en 1992.
Watkins se refería a "Aprender de las recompensas retrasadas", el título de su tesis doctoral. Ocho años antes, en 1981, el mismo problema, bajo el nombre de “Aprendizaje por refuerzo retardado”, fue resuelto por el Crossbar Adaptive Array (CAA) de Bozinovski. [13] [14] La matriz de memoriaera el mismo que el Q-table de Q-learning ocho años después. La arquitectura introdujo el término "evaluación estatal" en el aprendizaje por refuerzo. El algoritmo de aprendizaje de barras cruzadas, escrito en pseudocódigo matemático en el papel, en cada iteración realiza el siguiente cálculo:
- En el estado s, realice la acción a ;
- Recibe el estado de consecuencia s ' ;
- Calcular la evaluación del estado ;
- Actualizar el valor de la barra transversal .
El término "refuerzo secundario" se toma prestado de la teoría del aprendizaje animal, para modelar los valores de estado a través de la retropropagación : el valor de estadode la situación de consecuencia se propaga hacia atrás a las situaciones encontradas previamente. CAA calcula los valores de estado verticalmente y las acciones horizontalmente (la "barra transversal"). Gráficos de demostración que muestran estados contenidos de aprendizaje por refuerzo retardado (estados deseables, indeseables y neutrales), que fueron calculados por la función de evaluación de estados. Este sistema de aprendizaje fue un precursor del algoritmo Q-learning. [15]
En 2014, Google DeepMind patentó [16] una aplicación de Q-learning para el aprendizaje profundo , titulada "aprendizaje de refuerzo profundo" o "aprendizaje profundo de Q" que puede jugar juegos de Atari 2600 a niveles humanos expertos.
Variantes
Q-aprendizaje profundo
El sistema DeepMind utilizó una red neuronal convolucional profunda , con capas de filtros convolucionales en mosaico para imitar los efectos de los campos receptivos. El aprendizaje por refuerzo es inestable o divergente cuando se usa un aproximador de función no lineal como una red neuronal para representar Q.Esta inestabilidad proviene de las correlaciones presentes en la secuencia de observaciones, el hecho de que pequeñas actualizaciones de Q pueden cambiar significativamente la política del agente y la distribución de datos, y las correlaciones entre Q y los valores objetivo.
La técnica utilizó la repetición de la experiencia, un mecanismo de inspiración biológica que utiliza una muestra aleatoria de acciones anteriores en lugar de la acción más reciente para continuar. [2] Esto elimina las correlaciones en la secuencia de observación y suaviza los cambios en la distribución de datos. Las actualizaciones iterativas ajustan Q hacia los valores objetivo que solo se actualizan periódicamente, lo que reduce aún más las correlaciones con el objetivo. [17]
Doble Q-learning
Debido a que el valor de acción aproximado máximo futuro en Q-learning se evalúa utilizando la misma función Q que en la política de selección de acciones actual, en entornos ruidosos Q-learning a veces puede sobreestimar los valores de acción, lo que ralentiza el aprendizaje. Se propuso una variante llamada Double Q-learning para corregir esto. Double Q-learning [18] es un algoritmo de aprendizaje reforzado fuera de la política , en el que se utiliza una política diferente para la evaluación de valor que la que se utiliza para seleccionar la siguiente acción.
En la práctica, dos funciones de valor separadas se entrenan de manera mutuamente simétrica utilizando experiencias separadas, y . El paso de actualización doble de Q-learning es el siguiente:
- , y
Ahora, el valor estimado del futuro descontado se evalúa utilizando una política diferente, lo que resuelve el problema de la sobreestimación.
Este algoritmo se modificó posteriormente [se necesita aclaración ] en 2015 y se combinó con el aprendizaje profundo , como en el algoritmo DQN, lo que resultó en Double DQN, que supera al algoritmo DQN original. [19]
Otros
El Q-learning retrasado es una implementación alternativa del algoritmo Q -learning en línea , con un aprendizaje probablemente aproximadamente correcto (PAC) . [20]
Greedy GQ es una variante de Q -learning para usar en combinación con la aproximación de función (lineal). [21] La ventaja de Greedy GQ es que la convergencia está garantizada incluso cuando se utiliza la aproximación de funciones para estimar los valores de acción.
Limitaciones
El algoritmo estándar de Q-learning (utilizando un table) se aplica solo a espacios de acción y estado discretos. La discretización de estos valores conduce a un aprendizaje ineficaz, en gran parte debido a la maldición de la dimensionalidad . Sin embargo, existen adaptaciones de Q-learning que intentan resolver este problema, como Q-Learning con redes neuronales equipadas con cables. [22]
Ver también
- Aprendizaje reforzado
- Aprendizaje de la diferencia temporal
- SARSA
- El dilema del prisionero iterado
- Teoría de juego
Referencias
- ^ a b Melo, Francisco S. "Convergencia de Q-learning: una prueba simple" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b Matiisen, Tambet (19 de diciembre de 2015). "Desmitificando el aprendizaje por refuerzo profundo" . neuro.cs.ut.ee . Laboratorio de Neurociencia Computacional . Consultado el 6 de abril de 2018 .
- ^ Sutton, Richard; Barto, Andrew (1998). Aprendizaje por refuerzo: una introducción . Prensa del MIT.
- ^ Russell, Stuart J .; Norvig, Peter (2010). Inteligencia artificial: un enfoque moderno (tercera ed.). Prentice Hall . pag. 649. ISBN 978-0136042594.
- ^ Baird, Leemon (1995). "Algoritmos residuales: Aprendizaje reforzado con aproximación de funciones" (PDF) . ICML : 30–37.
- ^ François-Lavet, Vincent; Fonteneau, Rafael; Ernst, Damien (7 de diciembre de 2015). "Cómo descontar el aprendizaje por refuerzo profundo: hacia nuevas estrategias dinámicas". arXiv : 1512.02011 [ cs.LG ].
- ^ Sutton, Richard S .; Barto, Andrew G. "2.7 Valores iniciales optimistas" . Aprendizaje por refuerzo: una introducción . Archivado desde el original el 8 de septiembre de 2013 . Consultado el 18 de julio de 2013 .
- ^ a b c Shteingart, Hanan; Neiman, Tal; Loewenstein, Yonatan (mayo de 2013). "El papel de la primera impresión en el aprendizaje operante" (PDF) . Revista de Psicología Experimental: General . 142 (2): 476–488. doi : 10.1037 / a0029550 . ISSN 1939-2222 . PMID 22924882 .
- ^ Hasselt, Hado van (5 de marzo de 2012). "Aprendizaje por refuerzo en espacios de acción y estado continuo" . En Wiering, Marco; Otterlo, Martijn van (eds.). Aprendizaje por refuerzo: estado de la técnica . Springer Science & Business Media. págs. 207-251. ISBN 978-3-642-27645-3.
- ^ Tesauro, Gerald (marzo de 1995). "Aprendizaje de la diferencia temporal y TD-Gammon" . Comunicaciones de la ACM . 38 (3): 58–68. doi : 10.1145 / 203330.203343 . S2CID 8763243 . Consultado el 8 de febrero de 2010 .
- ^ Watkins, CJCH (1989), Learning from Delayed Rewards (PDF) (tesis de doctorado), Universidad de Cambridge
- ^ Watkins y Dayan, CJCH, (1992), 'Q-learning. Aprendizaje automático'
- ^ Bozinovski, S. (15 de julio de 1999). "Crossbar Adaptive Array: La primera red conexionista que resolvió el problema del aprendizaje por refuerzo retardado" . En Dobnikar, Andrej; Steele, Nigel C .; Pearson, David W .; Albrecht, Rudolf F. (eds.). Redes neuronales artificiales y algoritmos genéticos: Actas de la Conferencia Internacional en Portorož, Eslovenia, 1999 . Springer Science & Business Media. págs. 320–325. ISBN 978-3-211-83364-3.
- ^ Bozinovski, S. (1982). "Un sistema de autoaprendizaje mediante refuerzo secundario" . En Trappl, Robert (ed.). Investigación en cibernética y sistemas: Actas del sexto encuentro europeo sobre investigación en cibernética y sistemas . Holanda Septentrional. págs. 397–402. ISBN 978-0-444-86488-8.
- ^ Barto, A. (24 de febrero de 1997). "Aprendizaje por refuerzo" . En Omidvar, Omid; Elliott, David L. (eds.). Sistemas neuronales de control . Elsevier. ISBN 978-0-08-053739-9.
- ^ "Métodos y aparatos para el aprendizaje por refuerzo, patente de EE. UU. # 20150100530A1" (PDF) . Oficina de Patentes de Estados Unidos. 9 de abril de 2015 . Consultado el 28 de julio de 2018 .
- ^ Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A .; Veness, Joel; Bellemare, Marc G .; Graves, Alex; Riedmiller, Martin; Fidjeland, Andreas K. (febrero de 2015). "Control a nivel humano a través del aprendizaje por refuerzo profundo". Naturaleza . 518 (7540): 529–533. Código bibliográfico : 2015Natur.518..529M . doi : 10.1038 / nature14236 . ISSN 0028-0836 . PMID 25719670 . S2CID 205242740 .
- ^ van Hasselt, Hado (2011). "Doble Q-learning" (PDF) . Avances en sistemas de procesamiento de información neuronal . 23 : 2613–2622.
- ^ van Hasselt, Hado; Guez, Arthur; Plata, David (2015). "Aprendizaje por refuerzo profundo con doble Q-learning" (PDF) . Conferencia AAAI sobre Inteligencia Artificial : 2094–2100. arXiv : 1509.06461 .
- ^ Strehl, Alexander L .; Li, Lihong; Wiewiora, Eric; Langford, John; Littman, Michael L. (2006). "Aprendizaje por refuerzo sin modelo Pac" (PDF) . Proc. 22º ICML : 881–888.
- ^ Maei, Hamid; Szepesvári, Csaba; Bhatnagar, Shalabh; Sutton, Richard (2010). "Hacia el control del aprendizaje fuera de las políticas con aproximación de funciones en las actas de la 27ª Conferencia Internacional sobre Aprendizaje Automático" (PDF) . págs. 719–726. Archivado desde el original (PDF) el 8 de septiembre de 2012 . Consultado el 25 de enero de 2016 .
- ^ Gaskett, Chris; Wettergreen, David; Zelinsky, Alexander (1999). "Q-Learning en espacios de acción y estado continuo" (PDF) .
enlaces externos
- Watkins, CJCH (1989). Aprendiendo de las recompensas retrasadas. Tesis de doctorado, Universidad de Cambridge, Cambridge, Inglaterra.
- Strehl, Li, Wiewiora, Langford, Littman (2006). Aprendizaje por refuerzo sin modelo PAC
- Aprendizaje reforzado: una introducción de Richard Sutton y Andrew S. Barto, un libro de texto en línea. Consulte "6.5 Q-Learning: Control TD fuera de la política" .
- Piqle: una plataforma Java genérica para el aprendizaje por refuerzo
- Reinforcement Learning Maze , una demostración de cómo guiar a una hormiga a través de un laberinto usando Q -learning
- Q -learning trabajo de Gerald Tesauro