Enrutamiento en un gráfico disperso: un enfoque de Q-Learning distribuido

sobre el Experimento del Pequeño Mundo, realizado por Stanley Milgram en los años 1960. Ideó un experimento mediante el cual se entregaba una carta a un voluntario en los Estados Unidos, con la instrucción de reenviarla al contacto personal con más probabilidades de conocer a otra persona (el objetivo) en el mismo país. A su vez, a la persona que recibe la carta se le pedirá que la reenvíe nuevamente hasta localizar a la persona objetivo. Aunque la mayoría de las cartas nunca llegaron a la persona objetivo, entre las que sí lo hicieron (¡el sesgo de supervivencia en juego aquí!), el número promedio de saltos fue de aproximadamente 6. Los “seis grados de separación” se han convertido en una referencia cultural a la estrecha interconexión de la sociedad.

Todavía me sorprende la idea de que las personas con ~10² Los contactos pueden conectarse con una persona aleatoria en una red de aproximadamente 10⁸ personas, a través de algunos saltos.

¿Cómo es esto posible? Heurístico.

Supongamos que me piden que envíe una carta a una persona objetivo en Finlandia.¹.

Lamentablemente no tengo contactos en Finlandia. Por otro lado, conozco a una persona que vivió muchos años en Suecia. Quizás conozca gente en Finlandia. Por lo demás, probablemente todavía tenga contactos en Suecia, que es un país vecino. Ella es mi mejor apuesta para acercarme a la persona objetivo. El punto es que, aunque no conozco la topología de la red social más allá de mis contactos personales, puedo usar reglas generales para enviar la carta en la dirección correcta.

Si adoptamos el punto de vista de los nodos de la red (los humanos involucrados en el experimento), sus acciones disponibles son reenviar el mensaje (la carta) a uno de sus bordes salientes (contactos personales). ¡Este problema de transmitir el mensaje en la dirección correcta brinda la oportunidad de divertirse con el aprendizaje automático!

Los nodos no perciben toda la topología de la red. Podemos crear un entorno que los recompense por reenviar el mensaje por el camino más corto conocido, al tiempo que los alienta a explorar caminos candidatos subóptimos. Suena como un gran caso de uso para el aprendizaje por refuerzo, ¿no crees?

Para aquellos interesados ​​en ejecutar el código, pueden acceder al repositorio aquí.

el problema

Tendremos un gráfico dirigido donde los bordes entre nodos son escasos, lo que significa que el número promedio de bordes que salen de un nodo es significativamente menor que el número de nodos. Además los bordes tendrán un coste asociado. Esta característica adicional generaliza el caso del Experimento del Mundo Pequeño, donde cada salto de letra tenía un coste de 1.

El problema que consideraremos es diseñar un algoritmo de aprendizaje por refuerzo que encuentre una ruta desde un nodo inicial arbitrario hasta un nodo objetivo arbitrario en un gráfico dirigido disperso, con el menor costo posible, si dicha ruta existe. Hay soluciones deterministas a este problema. Por ejemplo, el algoritmo de Dijkstra encuentra el camino más corto desde un nodo inicial hasta todos los demás nodos en un gráfico dirigido. Esto será útil para evaluar los resultados de nuestro algoritmo de aprendizaje por refuerzo, que no garantiza encontrar la solución óptima.

Q-aprendizaje

Q-Learning es una técnica de aprendizaje por refuerzo en la que un agente mantiene una tabla de pares estado-acción, asociada con la recompensa acumulativa descontada esperada: la calidadde ahí el PAG-Aprendizaje. A través de experimentos iterativos, la tabla se actualiza hasta que se cumple un criterio de parada. Después del entrenamiento, el agente puede elegir la acción (la columna de la matriz Q) correspondiente a la calidad máxima, para un estado determinado (la fila de la matriz Q).

La regla de actualización dada una acción de prueba. a_jresultando en la transición estatal s_I declarar s_kuna recompensa ry una mejor estimación de la calidad del siguiente estado s_ky:

[ Q(i, j) leftarrow (1 – alpha) Q(i, j) + alpha left( r + gamma max_{l} Q(k, l) right) ]

_{Ecuación 1: La regla de actualización para Q-Learning.}

En la ecuación 1:

• α es la tasa de aprendizaje, que controla la rapidez con la que los nuevos resultados borrarán las antiguas estimaciones de calidad.
• γ es el factor de descuento, que controla en qué medida se comparan las recompensas futuras con las recompensas inmediatas.
• Q es la matriz de calidad. El índice de fila i es el índice del estado fuente y el índice de la columna j es el índice de la acción seleccionada.

En resumen, la ecuación 1 establece que la calidad de (estado, acción) debe actualizarse parcialmente con un nuevo valor de calidad, compuesto por la suma de la recompensa inmediata y la estimación descontada de la calidad máxima del siguiente estado sobre las posibles acciones.

Para definir nuestro problema, una posible formulación para el estado sería el par (nodo actual, nodo objetivo), y el conjunto de acciones sería el conjunto de nodos. El conjunto de estados contendría entonces N² valores, y el conjunto de acciones contendría N valores, donde N es el número de nosotros. Sin embargo, debido a que el gráfico es escaso, un nodo de origen determinado solo tiene un pequeño subconjunto de nodos como bordes de salida. Esta formulación daría como resultado una Q-matriz donde la gran mayoría de N³ las entradas nunca se visitan, consumiendo memoria innecesariamente.

Agentes distribuidos

Un mejor uso de los recursos es distribuir agentes. Cada nodo puede considerarse un agente. El estado del agente es el nodo objetivo, de ahí su Q-matriz tiene N líneas y N_afuera columnas (el número de aristas salientes para este nodo específico). Con N agentes, el número total de entradas de la matriz es N²N_afueraque es menor que N³.

Para resumir:

• estaremos entrenando N agentes, uno para cada nodo del gráfico.
• Cada agente aprenderá un Q-matriz dimensional [N x N_out]. El número de bordes salientes (N_afuera) puede variar de un nodo a otro. Para un gráfico escasamente conectado, N_afuera << N.
• Los índices de línea del Q-matriz corresponde al estado del agente, es decir, el nodo objetivo.
• Los índices de las columnas del Q-matriz corresponde al borde de salida seleccionado por un agente para enrutar un mensaje hacia el nodo de destino.
• Q[i, j] representa la estimación de un nodo de la calidad del enrutamiento de mensajes a su j^el borde de salida, dado que el nodo de destino es i.
• Cuando un nodo recibe un mensaje, incluirá el nodo de destino. Dado que el remitente del mensaje anterior no es necesario para determinar la ruta del siguiente mensaje, no se incluirá en el siguiente mensaje.

Código

La clase principal, el nodo, se denominará QNode.

class QNode:
    def __init__(self, number_of_nodes=0, connectivity_average=0, connectivity_std_dev=0, Q_arr=None, neighbor_nodes=None,
                 state_dict=None):
        if state_dict is not None:
            self.Q = state_dict['Q']
            self.number_of_nodes = state_dict['number_of_nodes']
            self.neighbor_nodes = state_dict['neighbor_nodes']
        else:  # state_dict is None
            if Q_arr is None:
                self.number_of_nodes = number_of_nodes
                number_of_neighbors = connectivity_average + connectivity_std_dev * np.random.randn()
                number_of_neighbors = round(number_of_neighbors)
                number_of_neighbors = max(number_of_neighbors, 2)  # At least two out-connections
                number_of_neighbors = min(number_of_neighbors, self.number_of_nodes)  # Not more than N connections
                self.neighbor_nodes = random.sample(range(self.number_of_nodes), number_of_neighbors)  # [1, 4, 5, ...]
                self.Q = np.zeros((self.number_of_nodes, number_of_neighbors))  # Optimistic initialization: all rewards will be negative
                # q = self.Q[state, action]: state = target node; action = chosen neighbor node (converted to column index) to route the message to

            else:  # state_dict is None and Q_arr is not None
                self.Q = Q_arr
                self.number_of_nodes = self.Q.shape[0]
                self.neighbor_nodes = neighbor_nodes

la clase QNode tiene tres campos: el número de nodos en el gráfico, la lista de bordes salientes y el Q-sede. EL Q-la matriz se inicializa con ceros. Las recompensas recibidas del medio ambiente serán negativas de los costos marginales. En consecuencia, los valores de calidad serán todos negativos. Por esta razón, inicializar con ceros es una inicialización optimista.

Cuando llega un mensaje a un QNode objeto, selecciona uno de sus bordes salientes a través del épsilon codicioso algoritmo. Si ε es pequeño, el algoritmo épsilon-codicioso selecciona con mayor frecuencia el borde de salida con el mayor Q-valor. De vez en cuando seleccionará un flanco de salida al azar:

def epsilon_greedy(self, target_node, epsilon):
        rdm_nbr = random.random()
        if rdm_nbr < epsilon:  # Random choice
            random_choice = random.choice(self.neighbor_nodes)
            return random_choice
        else:  # Greedy choice
            neighbor_columns = np.where(self.Q[target_node, :] == self.Q[target_node, :].max())[0]  # [1, 4, 5]
            neighbor_column = random.choice(neighbor_columns)
            neighbor_node = self.neighbor_node(neighbor_column)
            return neighbor_node

La otra clase es la gráfica, llamada QGraph.

class QGraph:
    def __init__(self, number_of_nodes=10, connectivity_average=3, connectivity_std_dev=0, cost_range=[0.0, 1.0],
                 maximum_hops=100, maximum_hops_penalty=1.0):
        self.number_of_nodes = number_of_nodes
        self.connectivity_average = connectivity_average
        self.connectivity_std_dev = connectivity_std_dev
        self.cost_range = cost_range
        self.maximum_hops = maximum_hops
        self.maximum_hops_penalty = maximum_hops_penalty
        self.QNodes = []
        for node in range(self.number_of_nodes):
            self.QNodes.append(QNode(self.number_of_nodes, self.connectivity_average, self.connectivity_std_dev))

        self.cost_arr = cost_range[0] + (cost_range[1] - cost_range[0]) * np.random.random((self.number_of_nodes, self.number_of_nodes))

Sus campos principales son la lista de nodos y la matriz de costos marginales. Tenga en cuenta que los bordes reales son parte de la QNode clase, como una lista de nodos de salida.

Cuando queremos generar una ruta desde un nodo inicial a un nodo objetivo, llamamos al método QGraph.trajectory() método, que llama al QNode.epsilon_greedy() método:

    def trajectory(self, start_node, target_node, epsilon):
        visited_nodes = [start_node]
        costs = []
        if start_node == target_node:
            return visited_nodes, costs
        current_node = start_node
        while len(visited_nodes) < self.maximum_hops + 1:
            next_node = self.QNodes[current_node].epsilon_greedy(target_node, epsilon)
            cost = float(self.cost_arr[current_node, next_node])
            visited_nodes.append(next_node)
            costs.append(cost)
            current_node = next_node
            if current_node == target_node:
                return visited_nodes, costs
        # We reached the maximum number of hops
        return visited_nodes, costs

EL trajectory() El método devuelve la lista de nodos visitados a lo largo del camino y la lista de costos asociados con los bordes que se utilizaron.

La última pieza que falta es la regla de actualización para la ecuación 1, implementada por QGraph.update_Q() método:

def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node):
   cost = self.cost_arr[start_node, neighbor_node]
   reward = -cost
   # Q_orig(target, dest) <- (1 - alpha) Q_orig(target, dest) + alpha * ( r + gamma * max_neigh' Q_dest(target, neigh') )
   Q_orig_target_dest = self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)]
   max_neigh_Q_dest_target_neigh = np.max(self.QNodes[neighbor_node].Q[target_node, :])
   updated_Q = (1 - alpha) * Q_orig_target_dest + alpha * (reward + gamma * max_neigh_Q_dest_target_neigh)
   self.QNodes[start_node].Q[target_node, self.QNodes[start_node].neighbor_column(neighbor_node)] = updated_Q

Para entrenar a nuestros agentes, recorremos iterativamente los pares de (start_node, target_node) con un bucle interno sobre los nodos vecinos de start_nodey llamamos update_Q().

Experimentos y resultados

Comencemos con un gráfico simple de 12 nodos, con aristas ponderadas dirigidas.

Podemos ver en la Figura 1 que el único nodo que llega al Nodo-1 es el Nodo-7, y el único nodo que llega al Nodo-7 es el Nodo-1. Por lo tanto, ningún otro nodo aparte de estos dos puede llegar al Nodo 1 y al Nodo 7. Cuando a otro nodo se le asigna la tarea de enviar un mensaje al Nodo 1 o al Nodo 7, el mensaje rebotará en el gráfico hasta alcanzar el número máximo de saltos. Esperamos ver grandes resultados negativos. Q-valores en estos casos.

Cuando entrenamos nuestro gráfico, obtenemos estadísticas sobre el costo y la cantidad de saltos en función de la época, como en la Figura 2:

Después del entrenamiento, este es el Q-matriz para el Nodo-4:

La trayectoria desde el Nodo-4 hasta, digamos, el Nodo-11, se puede obtener llamando al método trajectory() método, configuración epsilon=0 para la codiciosa solución determinista: [4, 3, 5, 11] para un costo total sin descuento de 0,9 + 0,9 + 0,3 = 2,1. El algoritmo de Dijkstra devuelve el mismo camino.

En algunos casos raros, no se encontró la ruta óptima. Por ejemplo, para pasar del Nodo 6 al Nodo 9, se devolvió una instancia específica del gráfico Q entrenado [6, 11, 0, 4, 10, 2, 9] para un costo total sin descuento de 3,5, mientras que el algoritmo de Dijkstra arrojó [6, 0, 4, 10, 2, 9] para un costo total sin descuento de 3,4. Como dijimos antes, esto es lo que se espera de un algoritmo iterativo.

Conclusión

Formulamos el Experimento del Mundo Pequeño como un problema de encontrar el camino con costo mínimo entre cualquier par de nodos en un gráfico dirigido disperso con bordes ponderados. Implementamos los nodos como agentes Q-Learning, que aprenden a través de la regla de actualización a realizar la acción menos costosa, dado un nodo objetivo.

Con un gráfico simple, mostramos que la capacitación estableció una solución cercana a la óptima.

Gracias por tu tiempo y no dudes en probar el código. Si tiene ideas de aplicaciones divertidas para Q-Learning, ¡hágamelo saber!

¹ Bien, voy más allá del Experimento del Pequeño Mundo original, que debería llamarse Experimento del Pequeño País.

Referencias

Aprendizaje por refuerzo, Richard S. Sutton, Andrew G. Barto, MIT Press, 1998