Aprendizaje por refuerzo (RL) — Capítulo 5: Programación dinámica — Parte 2: Implementación en Python

5 min readDec 19, 2023

En la parte anterior de este capítulo vimos la teoría detrás de los algoritmos de programación dinámica en aprendizaje por refuerzo. En esta segunda parte vamos a ver como implementar estos algoritmos en Python, asi que, manos a la obra!

Lo primeros que debemos hacer, como es costumbre, es definir los parámetros de nuestro algoritmo, que es este caso es el valor de γ, nuestro factor de descuento, que para nuestro caso le vamos a dar un valor de 0.9.

SIZE = 30
GAMMA = 0.9

También podemos notar que tenemos un parámetro SIZE. Este parámetro no es propio del algoritmo sino del problema que vamos a resolver, que igual al ejemplo de la parte anterior de este capítulo, es una grilla de SIZExSIZE donde los puntos superior izquierdo e inferior derecho son estados terminales.

El objetivo de nuestro agente es moverse por esta grilla y alcanzar los estados terminales lo antes posible. Cada paso de movimiento da una recompensa de -1, excepto el estado terminal con una recompensa de 0.

Así que, con esto en mente, vamos a definir la siguiente función:

def transition(s,a,ss, SIZE=SIZE):
    # izquierda, derecha, arriba, abajo.
    actions = {0:s-1 if (s%SIZE)!= 0 else s,
               1:s+1 if ((s+1)%SIZE)!= 0 else s,
               2:s+SIZE if (s+SIZE<SIZE**2) else s,
               3:s-SIZE if (s-SIZE>-1) else s}

    END = [0,SIZE**2-1]
    P = 1*(actions[a]==ss)
    R = -1*(ss not in END)
    return P,R

Esta función recibe tres parámetros:

s: nuestro estado actual
a: nuestra acción (arriba, abajo, izquierda o derecha)
ss: el estado siguiente que queremos alcanzar

Al principio de esta función vemos el resultado de aplicar la acción a al estado s, que pueden ser: ir al estado superior, inferior, al de la izquierda, al de la recha o quedarse donde está si la acción nos lleva a salir de la grilla.

Luego definimos la variable END, que no es mas que la posición de los estados terminales. A continuación calculamos la probabilidad de transicionar del estado s al ss al realizar la acción a y finalmente la recompensa que obtenemos.

Podemos ver que este es un entorno determinista, por lo tanto si aplicamos la acción subir, la probabilidad de terminar en el estado superior (siempre que no estemos en el borde superior) son del 100%.

Una vez que tenemos definido nuestro entorno y las probabilidades de movernos por el al aplicar una acción, estamos listos de aplicar el algoritmo de programación dinámica:

V = {s:0 for s in range(SIZE**2)}
evolution = [np.array(list(V.values())).reshape(SIZE,SIZE).round(2)]
while True:
    delta = 0
    for s in range(1,SIZE**2-1):
        v = V[s]
        V_actions = []
        for a in range(4):
            va = 0
            for ss in range(SIZE**2):
                P, R = transition(s,a,ss)
                va += P*(R+GAMMA*V[ss])
            V_actions.append(va)
        V[s] = max(V_actions)
        delta = max(delta, np.abs(V[s]-v))
        
    evolution.append(np.array(list(V.values())).reshape(SIZE,SIZE).round(2))
    if delta < 1e-5:
        break

Primero definimos nuestra matriz de valores inicial con un valor de 0 para todas las celdas. Luego para cada uno de los estados de la grilla, todas las acciones posibles, y todos los estados destino, calculamos la probabilidad de transición y la recompensa obtenida y calculamos la nueva matriz de valores a partir de la ecuación:

y calculamos los cambios de esta nueva matriz respecto a la anterior. Si este valor de δ es mayor a 0.0001 repetimos nuevamente el proceso hasta converger a la solución final.

Y hasta aquí la implementación de nuestro algoritmo de programación dinámica, a continuación puede ver dicha implementación en pseudocódigo:

Los algoritmos de programación dinámica en aprendizaje por refuerzo son sumamente útiles debido a su capacidad para encontrar soluciones óptimas en problemas complejos, sin embargo, son costosos computacionalmente porque requieren almacenar y actualizar información sobre todas las posibles situaciones y acciones, lo que puede consumir grandes cantidades de memoria y tiempo de cómputo. A pesar de su costo, su capacidad para resolver problemas difíciles hace que sean esenciales en campos como la inteligencia artificial y la toma de decisiones automatizada.

A continuación podemos ver la evolución de la estimación de los valores de las celdas de la grilla del ejemplo anterior:

Como podemos ver los primeros valores en converger son los de la esquina superior izquierda e inferior derecha. Esto se debe a que son estados terminales y no dependen de las acciones siguientes. Luego que estos convergen, le siguen los estados inmediatamente posterior a ellos y así sucesivamente. En el resultado final podemos ver que los estados con mayor valor son aquellos cercanos al estado final, lo cual tiene sentido ya que recordemos que recibimos una recompensa de -1 por cada movimiento hasta llegar a los estados finales.

Y eso es todo, recuerde que tiene en el repositorio de Git la notebook con los códigos que acabamos de analizar:

GitHub - jcerretani/AprendizajePorRefuerzo

Contribute to jcerretani/AprendizajePorRefuerzo development by creating an account on GitHub.

github.com

En el próximo capítulo de esta serie sobre aprendizaje por refuerzo, nos sumergiremos en el fascinante mundo de los algoritmos de Monte Carlo. Descubriremos cómo estos métodos utilizan la simulación y el muestreo para resolver problemas complejos de toma de decisiones, y cómo están revolucionando el campo de la inteligencia artificial. ¡Prepárate para un viaje emocionante!