Dilema exploración-explotación

El concepto en la toma de decisiones

El dilema exploración-explotación , también conocido como el dilema explorar-explotar , es un concepto fundamental en la toma de decisiones que surge en muchos dominios. ^{[1] [2]} Se describe como el acto de equilibrio entre dos estrategias opuestas. La explotación implica elegir la mejor opción en función del conocimiento actual del sistema (que puede ser incompleto o engañoso), mientras que la exploración implica probar nuevas opciones que pueden conducir a mejores resultados en el futuro a expensas de una oportunidad de explotación. Encontrar el equilibrio óptimo entre estas dos estrategias es un desafío crucial en muchos problemas de toma de decisiones cuyo objetivo es maximizar los beneficios a largo plazo. ^[3]

Aplicación en el aprendizaje automático

En el contexto del aprendizaje automático, la disyuntiva entre exploración y explotación es fundamental en el aprendizaje por refuerzo (RL), un tipo de aprendizaje automático que implica entrenar a los agentes para que tomen decisiones en función de la retroalimentación del entorno. Fundamentalmente, esta retroalimentación puede ser incompleta o retrasada. ^[4] El agente debe decidir si explotar la política más conocida actual o explorar nuevas políticas para mejorar su rendimiento.

Métodos de bandidos con múltiples brazos

El problema del bandido multibrazo (MAB) fue un ejemplo clásico de esta disyuntiva y se desarrollaron muchos métodos para solucionarlo, como el método épsilon-greedy, el muestreo de Thompson y el límite superior de confianza (UCB). Consulte la página sobre MAB para obtener más detalles.

En situaciones de RL más complejas que el problema MAB, el agente puede tratar cada elección como un MAB, donde el resultado es la recompensa futura esperada. Por ejemplo, si el agente aplica el método epsilon-greedy, entonces el agente a menudo "tirará de la mejor palanca" al elegir la acción que tenía la mejor recompensa esperada prevista (explotar). Sin embargo, con probabilidad epsilon elegiría una acción aleatoria (explorar). El método Monte Carlo Tree Search , por ejemplo, utiliza una variante del método UCB. ^[5]

Problemas de exploración

Existen algunos problemas que dificultan la exploración. ^[5]

• Recompensa escasa. Si las recompensas ocurren solo una vez cada cierto tiempo, entonces el agente podría no persistir en la exploración. Además, si el espacio de acciones es grande, entonces la recompensa escasa significaría que el agente no se dejaría guiar por la recompensa para encontrar una buena dirección para una exploración más profunda. Un ejemplo estándar es la venganza de Moctezuma . ^[6]
• Recompensa engañosa. Si algunas acciones tempranas dan una pequeña recompensa inmediata, pero otras acciones dan una recompensa mayor más adelante, el agente podría verse tentado a no explorar las otras acciones.
• Problema de ruido en la televisión. Si ciertas observaciones son irreductiblemente ruidosas (como un televisor que muestra imágenes aleatorias), entonces el agente podría quedar atrapado explorando esas observaciones (mirando la televisión). ^[7]

Recompensa de exploración

Esta sección se basa en. ^[8]

Los métodos de recompensa por exploración (también llamados bonos por exploración ) convierten el dilema exploración-explotación en un equilibrio de explotaciones. Es decir, en lugar de intentar que el agente equilibre la exploración y la explotación, la exploración se trata simplemente como otra forma de explotación, y el agente simplemente intenta maximizar la suma de recompensas de la exploración y la explotación. La recompensa por exploración puede tratarse como una forma de recompensa intrínseca . ^[9]

Los escribimos como , es decir, las recompensas intrínsecas y extrínsecas en el paso de tiempo . ${\displaystyle r_{t}^{i},r_{t}^{e}}$ ${\displaystyle t}$

Sin embargo, la recompensa por exploración se diferencia de la recompensa por explotación en dos aspectos:

• La recompensa de la explotación no se elige libremente, sino que la proporciona el entorno, pero la recompensa de la exploración se puede elegir libremente. De hecho, hay muchas formas diferentes de diseñar, que se describen a continuación. ${\displaystyle r_{t}^{i}}$
• La recompensa de la explotación suele ser estacionaria (es decir, la misma acción en el mismo estado da la misma recompensa), pero la recompensa de la exploración no es estacionaria (es decir, la misma acción en el mismo estado debería dar cada vez menos recompensa). ^[7]

La exploración basada en recuentos utiliza , la cantidad de visitas a un estado durante los intervalos de tiempo , para calcular la recompensa de exploración. Esto solo es posible en espacios de estados pequeños y discretos. La exploración basada en densidad extiende la exploración basada en recuentos mediante el uso de un modelo de densidad . La idea es que, si se ha visitado un estado, los estados cercanos también se visitan parcialmente. ^[10] ${\displaystyle N_{n}(s)}$ ${\displaystyle s}$ ${\displaystyle 1:n}$ ${\displaystyle \rho _{n}(s)}$

En la exploración de máxima entropía , la entropía de la política del agente se incluye como un término en la recompensa intrínseca. Es decir, . ^[11] ${\displaystyle \pi }$ ${\displaystyle r_{t}^{i}=-\sum _{a}\pi (a|s_{t})\ln \pi (a|s_{t})+\cdots }$

Basado en predicciones

Esta sección se basa en. ^[8]

El modelo de dinámica de avance es una función para predecir el próximo estado en función del estado actual y la acción actual: . El modelo de dinámica de avance se entrena mientras el agente juega. El modelo mejora en la predicción de la transición de estado para pares de estado-acción que se han realizado muchas veces. ${\displaystyle f:(s_{t},a_{t})\mapsto s_{t+1}}$

Un modelo de dinámica hacia adelante puede definir una recompensa de exploración por . Es decir, la recompensa es el error al cuadrado de la predicción en comparación con la realidad. Esto recompensa al agente por realizar pares de estados y acciones que no se habían realizado muchas veces. Sin embargo, esto es susceptible al problema de la televisión ruidosa. ${\displaystyle r_{t}^{i}=\|f(s_{t},a_{t})-s_{t+1}\|_{2}^{2}}$

El modelo de dinámica se puede ejecutar en el espacio latente . Es decir, para algún caracterizador . El caracterizador puede ser la función de identidad (es decir, ), generada aleatoriamente, la mitad codificadora de un autocodificador variacional , etc. Un buen caracterizador mejora la exploración de dinámicas hacia adelante. ^[12] ${\displaystyle r_{t}^{i}=\|f(s_{t},a_{t})-\phi (s_{t+1})\|_{2}^{2}}$ ${\displaystyle \phi }$ ${\displaystyle \phi (x)=x}$

El método del Módulo de Curiosidad Intrínseca (ICM) entrena simultáneamente un modelo de dinámica hacia delante y un caracterizador. El caracterizador se entrena mediante un modelo de dinámica inversa , que es una función para predecir la acción actual en función de las características del estado actual y del siguiente: . Al optimizar la dinámica inversa, se mejoran tanto el modelo de dinámica inversa como el caracterizador. Luego, el caracterizador mejorado mejora el modelo de dinámica hacia delante, lo que mejora la exploración del agente. ^[13] ${\displaystyle g:(\phi (s_{t}),\phi (s_{t+1}))\mapsto a_{t}}$

El método de destilación de red aleatoria (RND) intenta resolver este problema mediante la destilación profesor-alumno . En lugar de un modelo de dinámica hacia adelante, tiene dos modelos . El modelo del profesor es fijo y el modelo del alumno se entrena para minimizar los estados . A medida que se visita un estado cada vez más, la red del alumno mejora en la predicción del profesor. Mientras tanto, el error de predicción también es una recompensa de exploración para el agente, por lo que el agente aprende a realizar acciones que dan como resultado un mayor error de predicción. Por lo tanto, tenemos una red de alumnos que intenta minimizar el error de predicción, mientras que el agente intenta maximizarlo, lo que da como resultado la exploración. ${\displaystyle f,f'}$ ${\displaystyle f'}$ ${\displaystyle f}$ ${\displaystyle \|f(s)-f'(s)\|_{2}^{2}}$ ${\displaystyle s}$

Los estados se normalizan restando un promedio móvil y dividiendo una varianza móvil, lo cual es necesario ya que el modelo del maestro está congelado. Las recompensas se normalizan dividiendo por una varianza móvil. ^{[7] [14]}

La exploración por desacuerdo entrena un conjunto de modelos de dinámica hacia adelante, cada uno en un subconjunto aleatorio de todas las tuplas. La recompensa de la exploración es la varianza de las predicciones de los modelos. ^[15] ${\displaystyle (s_{t},a_{t},s_{t+1})}$

Ruido

Para los agentes basados ​​en redes neuronales, el método NoisyNet cambia algunos de sus módulos de red neuronal por versiones ruidosas. Es decir, algunos parámetros de la red son variables aleatorias de una distribución de probabilidad. Los parámetros de la distribución son en sí mismos aprendibles. ^[16] Por ejemplo, en una capa lineal , ambas se muestrean a partir de distribuciones gaussianas en cada paso, y los parámetros se aprenden a través del truco de reparametrización . ^[17] ${\displaystyle y=Wx+b}$ ${\displaystyle W,b}$ ${\displaystyle {\mathcal {N}}(\mu _{W},\Sigma _{W}),{\mathcal {N}}(\mu _{b},\Sigma _{b})}$ ${\displaystyle \mu _{W},\Sigma _{W},\mu _{b},\Sigma _{b}}$

Referencias

1. Berger-Tal, Oded; Nathan, Jonathan; Meron, Ehud; Saltz, David (22 de abril de 2014). "El dilema exploración-explotación: un marco multidisciplinario". PLOS ONE . ​​9 (4): e95693. Bibcode :2014PLoSO...995693B. doi : 10.1371/journal.pone.0095693 . PMC  3995763 . PMID  24756026.
2. Rhee, Mooweon; Kim, Tohyun (2018). "Exploración y explotación". The Palgrave Encyclopedia of Strategic Management . Londres: Palgrave Macmillan UK. págs. 543–546. doi :10.1057/978-1-137-00772-8_388. ISBN 978-0-230-53721-7.
3. Fruit, R. (2019). Dilema exploración-explotación en el aprendizaje por refuerzo bajo diversas formas de conocimiento previo (Tesis doctoral, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189).
4. Richard S. Sutton; Andrew G. Barto (2020). Aprendizaje por refuerzo: una introducción (segunda edición). http://incompleteideas.net/book/the-book-2nd.html
5. Weng, Lilian (23 de enero de 2018). "El problema de los bandidos multiarmados y sus soluciones". lilianweng.github.io . Consultado el 15 de septiembre de 2024 .
6. Salimans, Tim; Chen, Richard (4 de julio de 2018). "Aprendiendo la venganza de Moctezuma a partir de una única demostración". OpenAI Blog . arXiv : 1812.03381 . Bibcode :2018arXiv181203381S . Consultado el 1 de marzo de 2019 .
7. Burda, Yuri; Edwards, Harrison; Storkey, Amos; Klimov, Oleg (30 de octubre de 2018). "Exploración mediante destilación de redes aleatorias". arXiv : 1810.12894 [cs.LG].
8. Weng, Lilian (7 de junio de 2020). "Estrategias de exploración en el aprendizaje por refuerzo profundo". lilianweng.github.io . Consultado el 15 de septiembre de 2024 .
9. Şimşek, Özgür; Barto, Andrew G. (25 de junio de 2006). "Un mecanismo de recompensa intrínseco para la exploración eficiente". Actas de la 23.ª conferencia internacional sobre aprendizaje automático - ICML '06. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 833–840. doi :10.1145/1143844.1143949. ISBN 978-1-59593-383-6.
10. Bellemare, Marc G.; Srinivasan, Sriram; Ostrovski, Georg; Schaul, Tom; Saxton, David; Munos, Remi (7 de noviembre de 2016). "Unificación de la exploración basada en recuentos y la motivación intrínseca". arXiv : 1606.01868 [cs.AI].
11. Hazan, Elad; Kakade, Sham; Singh, Karan; Soest, Abby Van (24 de mayo de 2019). "Exploración de máxima entropía demostrablemente eficiente". Actas de la 36.ª Conferencia internacional sobre aprendizaje automático . PMLR: 2681–2691.
12. Burda, Yuri; Edwards, Harri; Pathak, Deepak; Storkey, Amos; Darrell, Trevor; Efros, Alexei A. (13 de agosto de 2018). "Estudio a gran escala del aprendizaje impulsado por la curiosidad". arXiv : 1808.04355 [cs.LG].
13. Pathak, Deepak; Agrawal, Pulkit; Efros, Alexei A.; Darrell, Trevor (15 de mayo de 2017). "Exploración impulsada por la curiosidad mediante predicción autosupervisada". arXiv : 1705.05363 [cs.LG].
14. "Aprendizaje de refuerzo con recompensas basadas en predicciones". Blog de OpenAI . 2018-10-31 . Consultado el 2019-03-01 .
15. Pathak, Deepak; Gandhi, Dhiraj; Gupta, Abhinav (10 de junio de 2019). "Exploración autosupervisada mediante desacuerdo". arXiv : 1906.04161 [cs.LG].
16. Fortunato, Meire; Azar, Mohammad Gheshlaghi; Piot, Bilal; Menick, Jacob; Osband, Ian; Tumbas, Alex; Mnih, Vlad; Munos, Remi; Hassabis, Demis; Pietquin, Olivier; Blundell, Charles; Legg, Shane (2017). "Redes ruidosas para la exploración". arXiv : 1706.10295 [cs.LG].
17. Kingma, Durk P; Salimans, Tim; Welling, Max (2015). "Deserción variacional y el truco de la reparametrización local". Avances en sistemas de procesamiento de información neuronal . 28 . Curran Associates, Inc.

• Amin, Susan; Gomrokchi, Maziar; Satija, Harsh; Hoof, van; Precup, Doina (1 de septiembre de 2021). "Un estudio de los métodos de exploración en el aprendizaje por refuerzo". arXiv : 2109.00157 [cs.LG].