Cómo aplicar el aprendizaje por refuerzo a problemas de planificación de la vida real

Recientemente, he publicado algunos ejemplos en los que he creado modelos de aprendizaje por refuerzo para algunos problemas de la vida real. Por ejemplo, usando el aprendizaje por refuerzo para la planificación de comidas basado en un presupuesto establecido y preferencias personales.

El aprendizaje por refuerzo se puede utilizar de esta manera para una variedad de problemas de planificación, incluidos planes de viaje, planificación presupuestaria y estrategia comercial. Las dos ventajas de usar RL es que tiene en cuenta la probabilidad de resultados y nos permite controlar partes del entorno. Por lo tanto, decidí escribir un ejemplo simple para que otros puedan considerar cómo podrían comenzar a usarlo para resolver algunos de sus problemas cotidianos o laborales.

¿Qué es el aprendizaje por refuerzo?

El aprendizaje por refuerzo (RL) es el proceso de probar qué acciones son las mejores para cada estado de un entorno esencialmente mediante prueba y error. El modelo introduce una política aleatoria para comenzar, y cada vez que se realiza una acción, se ingresa una cantidad inicial (conocida como recompensa) al modelo. Esto continúa hasta que se alcanza un objetivo final, p. ganas o pierdes el juego, donde termina esa carrera (o episodio) y el juego se reinicia.

A medida que el modelo atraviesa más y más episodios, comienza a aprender qué acciones tienen más probabilidades de llevarnos a un resultado positivo. Por lo tanto, encuentra las mejores acciones en cualquier estado dado, conocido como la política óptima.

Proceso general de aprendizaje por refuerzo

Muchas de las aplicaciones RL de modelos de trenes en línea en un juego o entorno virtual donde el modelo puede interactuar con el entorno repetidamente. Por ejemplo, dejas que el modelo juegue una simulación de tic-tac-toe una y otra vez para que observe el éxito y el fracaso de intentar diferentes movimientos.

En la vida real, es probable que no tengamos acceso para entrenar a nuestro modelo de esta manera. Por ejemplo, un sistema de recomendación en compras en línea necesita los comentarios de una persona para decirnos si ha tenido éxito o no, y su disponibilidad es limitada según la cantidad de usuarios que interactúan con el sitio de compras.

En cambio, podemos tener datos de muestra que muestran las tendencias de compra durante un período de tiempo que podemos usar para crear probabilidades estimadas. Con estos, podemos crear lo que se conoce como un Proceso de decisión de Markov parcialmente observado (POMDP) ​​como una forma de generalizar la distribución de probabilidad subyacente.

Procesos de decisión de Markov parcialmente observados (POMDP)

Los procesos de decisión de Markov (MDP) proporcionan un marco para modelar la toma de decisiones en situaciones donde los resultados son en parte aleatorios y en parte bajo el control de un tomador de decisiones. La característica clave de los MDP es que siguen la propiedad de Markov; Todos los estados futuros son independientes del pasado dado el presente. En otras palabras, la probabilidad de pasar al siguiente estado solo depende del estado actual.

Los POMDP funcionan de manera similar, excepto que es una generalización de los MDP. En resumen, esto significa que el modelo no puede simplemente interactuar con el entorno, sino que se le asigna una distribución de probabilidad establecida basada en lo que hemos observado. Aquí se puede encontrar más información. Podríamos usar métodos de iteración de valores en nuestro POMDP, pero en su lugar, decidí usar Monte Carlo Learning en este ejemplo.

Entorno de ejemplo

Imagine que está de regreso en la escuela (o tal vez todavía lo está) y está en un salón de clases, el maestro tiene una política estricta sobre el desperdicio de papel y requiere que se le pasen los pedazos de papel al frente del salón de clases y él colocará los residuos en el contenedor (bote de basura).

Sin embargo, algunos estudiantes en la clase se preocupan poco por las reglas del maestro y prefieren ahorrarse la molestia de pasar el papel por el aula. En cambio, estas personas problemáticas pueden optar por tirar el papel de desecho en la papelera desde la distancia. Ahora esto enoja al maestro y los que hacen esto son castigados.

Esto introduce un concepto muy básico de acción-recompensa, y tenemos un entorno de clase de ejemplo como se muestra en el siguiente diagrama.

Nuestro objetivo es encontrar las mejores instrucciones para cada persona para que el papel llegue al profesor y se coloque en el contenedor y evite que lo arrojen al contenedor.

Estados y acciones

En nuestro entorno, cada persona puede considerarse un estado y tienen una variedad de acciones que pueden tomar con el papel de desecho. Pueden elegir pasarlo a un compañero de clase adyacente, aferrarse a él o algunos pueden elegir tirarlo a la basura. Por lo tanto, podemos asignar nuestro entorno a un diseño de cuadrícula más estándar como se muestra a continuación.

Esto está diseñado a propósito para que cada persona, o estado, tenga cuatro acciones: arriba, abajo, izquierda o derecha y cada una tendrá un resultado variado de la "vida real" en función de quién tomó la acción. Una acción que coloca a la persona en una pared (incluido el bloque negro en el medio) indica que la persona se aferra al papel. En algunos casos, esta acción está duplicada, pero no es un problema en nuestro ejemplo.

Por ejemplo, las acciones de la persona A resultan en:

  • Arriba = Tirar a la papelera
  • Abajo = Mantener en el papel
  • Izquierda = Pase a la persona B
  • Derecha = Sostener en papel

Ambiente probabilístico

Por ahora, el tomador de decisiones que controla en parte el medio ambiente somos nosotros. Le diremos a cada persona qué acción deben tomar. Esto se conoce como la política.

El primer desafío al que me enfrento en mi aprendizaje es comprender que el entorno es probablemente probabilístico y lo que esto significa. Un ambiente probabilístico es cuando le ordenamos a un estado que tome una acción bajo nuestra política, hay una probabilidad asociada de si esto se sigue con éxito. En otras palabras, si le decimos a la persona A que pase el papel a la persona B, pueden decidir no seguir la acción instruida en nuestra política y en su lugar tirar el papel de desecho a la papelera.

Otro ejemplo es si estamos recomendando productos de compra en línea, no hay garantía de que la persona vea cada uno.

Probabilidades de transición observadas

Para encontrar las probabilidades de transición observadas, necesitamos recopilar algunos datos de muestra sobre cómo actúa el entorno. Antes de recopilar información, primero presentamos una política inicial. Para comenzar el proceso, elegí al azar uno que parece que daría un resultado positivo.

Ahora observamos las acciones que toma cada persona dada esta política. En otras palabras, digamos que nos sentamos al final del aula y simplemente observamos la clase y observamos los siguientes resultados para la persona A:

Acciones observadas de la persona A

Vemos que un documento pasó por esta persona 20 veces; 6 veces lo retuvieron, 8 veces se lo pasaron a la persona B y otras 6 veces lo tiraron a la basura. Esto significa que, según nuestra política inicial, la probabilidad de retenerla o tirarla a la basura para esta persona es 6/20 = 0.3 e igualmente 8/20 = 0.4 para pasar a la persona B. Podemos observar al resto de la clase a recopilar los siguientes datos de muestra:

Resultado de la vida real observado

Del mismo modo, calculamos las probabilidades de ser la siguiente matriz y podríamos usar esto para simular la experiencia. La precisión de este modelo dependerá en gran medida de si las probabilidades son representaciones verdaderas de todo el entorno. En otras palabras, debemos asegurarnos de tener una muestra que sea lo suficientemente grande y rica en datos.

Función de probabilidad de transición observada

Bandidos, episodios, recompensas, tasa de devolución y descuento de armas múltiples

Entonces tenemos nuestras probabilidades de transición estimadas a partir de los datos de la muestra bajo un POMDP. El siguiente paso, antes de presentar cualquier modelo, es introducir recompensas. Hasta ahora, solo hemos discutido el resultado del paso final; o bien el profesor coloca el papel en la papelera y obtiene una recompensa positiva o A o M lo arroja y obtiene una recompensa negativa. Esta recompensa final que finaliza el episodio se conoce como la Recompensa Terminal.

Pero, también hay un tercer resultado que tampoco es ideal; el papel se pasa continuamente y nunca (o tarda mucho más de lo que nos gustaría) llega a la papelera. Por lo tanto, en resumen, tenemos tres resultados finales

  • El profesor coloca el papel en la papelera y obtiene una recompensa terminal positiva
  • Un estudiante arroja papel a la papelera y obtiene una recompensa terminal negativa
  • El papel se pasa continuamente por la sala o se atasca en los estudiantes durante un período de tiempo más largo de lo que nos gustaría

Para evitar que el papel se arroje a la papelera, le proporcionamos una recompensa grande y negativa, digamos -1, y debido a que el maestro está satisfecho de que se coloque en la papelera, esto genera una gran recompensa positiva, +1. Para evitar el resultado donde se pasa continuamente por la sala, establecemos que la recompensa para todas las demás acciones sea un valor pequeño y negativo, digamos -0.04.

Si establecemos esto como un número positivo o nulo, entonces el modelo puede dejar que el documento dé vueltas y vueltas, ya que sería mejor obtener pequeños positivos que arriesgarse a acercarse al resultado negativo. Este número también es muy pequeño, ya que solo recopilará una recompensa terminal única, pero podría tomar muchos pasos para finalizar el episodio y debemos asegurarnos de que, si el papel se coloca en el contenedor, el resultado positivo no se cancela.

Tenga en cuenta: las recompensas siempre son relativas entre sí y he elegido figuras arbitrarias, pero se pueden cambiar si los resultados no son los deseados.

Aunque inadvertidamente hemos discutido episodios en el ejemplo, todavía tenemos que definirlo formalmente. Un episodio es simplemente las acciones que cada trabajo toma a través del aula llegando al contenedor, que es el estado terminal y finaliza el episodio. En otros ejemplos, como jugar al tic-tac-toe, este sería el final de un juego en el que ganas o pierdes.

En teoría, el documento podría comenzar en cualquier estado y esto introduce por qué necesitamos suficientes episodios para asegurarnos de que cada estado y acción se prueben lo suficiente para que nuestro resultado no sea impulsado por resultados no válidos. Sin embargo, por otro lado, cuantos más episodios introduzcamos, mayor será el tiempo de cálculo y, dependiendo de la escala del entorno, es posible que no tengamos una cantidad ilimitada de recursos para hacer esto.

Esto se conoce como el problema del bandido multi armado; con tiempo finito (u otros recursos), debemos asegurarnos de que probamos cada par estado-acción lo suficiente como para que las acciones seleccionadas en nuestra política sean, de hecho, las óptimas. En otras palabras, debemos validar que las acciones que nos han llevado a buenos resultados en el pasado no son por pura suerte, sino que están en la elección correcta, y de la misma manera para las acciones que parecen pobres. En nuestro ejemplo, esto puede parecer simple con los pocos estados que tenemos, pero imagínese si aumentamos la escala y cómo esto se convierte en un problema cada vez más.

El objetivo general de nuestro modelo RL es seleccionar las acciones que maximicen las recompensas acumuladas esperadas, conocidas como el retorno. En otras palabras, el Retorno es simplemente la recompensa total obtenida por el episodio. Una manera simple de calcular esto sería sumar todas las recompensas, incluida la recompensa terminal, en cada episodio.

Un enfoque más riguroso es considerar que los primeros pasos son más importantes que los posteriores en el episodio aplicando un factor de descuento, gamma, en la siguiente fórmula:

En otras palabras, sumamos todas las recompensas, pero atenuamos los pasos posteriores por un factor de gamma al poder de cuántos pasos tomó para alcanzarlos.

Si pensamos en nuestro ejemplo, el uso de un retorno con descuento se vuelve aún más claro de imaginar, ya que el maestro recompensará (o castigará en consecuencia) a cualquiera que haya estado involucrado en el episodio, pero lo escalará en función de lo lejos que estén del resultado final.

Por ejemplo, si el papel pasó de A a B a M que lo tiró a la basura, M debería ser castigado más, luego B por pasárselo a él y, por último, a la persona A que todavía está involucrada en el resultado final pero menos que M o B. Esto también enfatiza que cuanto más tiempo (según el número de pasos) se inicie en un estado y llegue al contenedor, menos será recompensado o castigado, pero acumulará recompensas negativas por dar más pasos.

Aplicando un modelo a nuestro ejemplo

Como nuestro entorno de ejemplo es pequeño, podemos aplicar cada uno y mostrar algunos de los cálculos realizados manualmente e ilustrar el impacto de los parámetros cambiantes.

Para cualquier algoritmo, primero debemos inicializar la función de valor de estado, V (s), y hemos decidido establecer cada uno de estos en 0 como se muestra a continuación.

A continuación, dejamos que el modelo simule la experiencia en el entorno en función de nuestra distribución de probabilidad observada. El modelo comienza una hoja de papel en estados aleatorios y los resultados de cada acción bajo nuestra política se basan en nuestras probabilidades observadas. Entonces, por ejemplo, digamos que tenemos los primeros tres episodios simulados que son los siguientes:

Con estos episodios podemos calcular nuestras primeras actualizaciones de nuestra función de valor de estado utilizando cada uno de los tres modelos dados. Por ahora, elegimos valores arbitrarios de alfa y gamma para que sean 0.5 para simplificar nuestros cálculos manuales. Más adelante mostraremos el impacto que esta variable tiene en los resultados.

Primero, aplicamos la diferencia temporal 0, el más simple de nuestros modelos y las tres primeras actualizaciones de valores son las siguientes:

Entonces, ¿cómo se han calculado? Bueno, porque nuestro ejemplo es pequeño, podemos mostrar los cálculos a mano.

Entonces, ¿qué podemos observar en esta etapa temprana? En primer lugar, el uso de TD (0) parece injusto para algunos estados, por ejemplo, la persona D, que, en esta etapa, no ha ganado nada del papel que llega al contenedor dos de tres veces. Su actualización solo se ha visto afectada por el valor de la siguiente etapa, pero esto enfatiza cómo las recompensas positivas y negativas se propagan hacia afuera desde la esquina hacia los estados.

A medida que tomemos más episodios, las recompensas terminales positivas y negativas se extenderán cada vez más en todos los estados. Esto se muestra más o menos en el diagrama a continuación, donde podemos ver que los dos episodios que resultaron en un resultado positivo impactan el valor de los estados Maestro y G, mientras que el episodio negativo único ha castigado a la persona M.

Para mostrar esto, podemos probar más episodios. Si repetimos los mismos tres caminos ya dados, producimos la siguiente función de valor de estado:

(Tenga en cuenta que hemos repetido estos tres episodios por simplicidad en este ejemplo, pero el modelo real tendría episodios en los que los resultados se basan en la función de probabilidad de transición observada).

El diagrama anterior muestra las recompensas del terminal que se propagan hacia afuera desde la esquina superior derecha a los estados. A partir de esto, podemos decidir actualizar nuestra política, ya que está claro que la recompensa terminal negativa pasa a través de la persona M y, por lo tanto, B y C se ven afectados negativamente. Por lo tanto, según V27, para cada estado podemos decidir actualizar nuestra política seleccionando el siguiente mejor valor de estado para cada estado como se muestra en la figura a continuación

Hay dos causas de preocupación en este ejemplo: la primera es que la mejor acción de esa persona A es tirarla a la basura y obtener una recompensa negativa. Esto se debe a que ninguno de los episodios ha visitado a esta persona y enfatiza el problema de los bandidos armados múltiples. En este pequeño ejemplo, hay muy pocos estados, por lo que requeriría muchos episodios para visitarlos a todos, pero debemos asegurarnos de que esto se haga.

La razón por la que esta acción es mejor para esta persona es porque ninguno de los estados terminales tiene un valor, sino que los resultados positivos y negativos están en las recompensas terminales. Entonces podríamos, si nuestra situación lo requería, inicializar V0 con cifras para los estados terminales basados ​​en los resultados.

En segundo lugar, el valor del estado de la persona M está cambiando entre -0.03 y -0.51 (aprox.) Después de los episodios y debemos abordar por qué sucede esto. Esto es causado por nuestra tasa de aprendizaje, alfa. Por ahora, solo hemos introducido nuestros parámetros (la tasa de aprendizaje alfa y la tasa de descuento gamma), pero no hemos explicado en detalle cómo afectarán los resultados.

Una gran tasa de aprendizaje puede hacer que los resultados oscilen, pero, por el contrario, no debería ser tan pequeño como para que converja una eternidad. Esto se muestra más adelante en la figura a continuación que demuestra el total de V (s) para cada episodio y podemos ver claramente cómo, aunque hay una tendencia general creciente, está divergiendo de un episodio a otro. Otra buena explicación para la tasa de aprendizaje es la siguiente:

“En el juego de golf cuando la pelota está muy lejos del hoyo, el jugador golpea muy duro para acercarse lo más posible al hoyo. Más tarde, cuando llega al área marcada, elige un palo diferente para obtener un disparo corto preciso.

Por lo tanto, no es que no pueda meter la pelota en el hoyo sin elegir el palo de tiro corto, puede enviar la pelota por delante del objetivo dos o tres veces. Pero sería mejor si juega de manera óptima y usa la cantidad correcta de energía para llegar al hoyo ".

Episodio

Existen algunos métodos complejos para establecer la tasa de aprendizaje óptima para un problema, pero, como con cualquier algoritmo de aprendizaje automático, si el entorno es lo suficientemente simple, itera sobre valores diferentes hasta que se alcanza la convergencia. Esto también se conoce como gradiente estocástico decente. En un proyecto reciente de RL, demostré el impacto de reducir alfa usando un visual animado y esto se muestra a continuación. Esto demuestra la oscilación cuando alfa es grande y cómo se suaviza a medida que se reduce alfa.

Del mismo modo, también debemos tener nuestra tasa de descuento para que sea un número entre 0 y 1, a menudo esto se considera cercano a 0.9. El factor de descuento nos dice cuán importantes son las recompensas en el futuro; un gran número indica que se considerarán importantes, mientras que moverlo hacia 0 hará que el modelo considere pasos futuros cada vez menos.

Con estos dos en mente, podemos cambiar tanto alfa de 0.5 a 0.2 como gamma de 0.5 a 0.9 y logramos los siguientes resultados:

Debido a que nuestra tasa de aprendizaje ahora es mucho más pequeña, el modelo tarda más en aprender y los valores son generalmente más pequeños. Lo más notable es para el maestro, que es claramente el mejor estado. Sin embargo, esta compensación por un mayor tiempo de cálculo significa que nuestro valor para M ya no oscila en el grado que tenían antes. Ahora podemos ver esto en el siguiente diagrama para la suma de V (s) siguiendo nuestros parámetros actualizados. Aunque no es perfectamente uniforme, el total de V (s) aumenta lentamente a una velocidad mucho más suave que antes y parece converger como quisiéramos, pero requiere aproximadamente 75 episodios para hacerlo.

Cambio del resultado del objetivo

Otra ventaja crucial de RL que no hemos mencionado con demasiado detalle es que tenemos cierto control sobre el medio ambiente. Actualmente, las recompensas se basan en lo que decidimos que sería mejor hacer que el modelo alcanzara el resultado positivo en el menor número de pasos posible.

Sin embargo, digamos que el maestro cambió y al nuevo no le importó que los estudiantes tiraran el papel en el contenedor mientras lo alcanzara. Entonces podemos cambiar nuestra recompensa negativa en torno a esto y la política óptima cambiará.

Esto es particularmente útil para soluciones comerciales. Por ejemplo, supongamos que está planeando una estrategia y sabe que ciertas transiciones son menos deseadas que otras, entonces esto se puede tener en cuenta y cambiar a voluntad.

Conclusión

Ahora hemos creado un modelo simple de aprendizaje por refuerzo a partir de datos observados. Hay muchas cosas que podrían mejorarse o llevarse más lejos, incluido el uso de un modelo más complejo, pero esta debería ser una buena introducción para aquellos que desean probar y aplicar a sus propios problemas de la vida real.

Espero que hayas disfrutado leyendo este artículo, si tienes alguna pregunta, no dudes en comentar a continuación.

Gracias

Libra esterlina