Routage dans un graphique clairsemé : une approche Q-Learning distribuée

à propos du Expérience dans un petit mondedirigé par Stanley Milgram dans les années 1960. Il a conçu une expérience selon laquelle une lettre était remise à une personne volontaire aux États-Unis, avec pour instruction de transmettre la lettre à son contact personnel le plus susceptible de connaître une autre personne – la cible – dans le même pays. À son tour, la personne recevant la lettre serait invitée à la transmettre à nouveau jusqu’à ce que la personne cible soit atteinte. Bien que la plupart des lettres n’atteignent jamais la personne cible, parmi celles qui parvenaient (le biais de survie en jeu ici !), le nombre moyen de sauts était d’environ 6. Les « six degrés de séparation » sont devenus une référence culturelle à l’interconnectivité étroite de la société.

Je suis toujours étonné à l’idée que les personnes ayant ~10² les contacts parviennent à se connecter avec une personne aléatoire dans un réseau de ~10⁸ les gens, en quelques sauts.

Comment est-ce possible ? Heuristique.

Supposons qu’on me demande d’envoyer une lettre à une personne cible en Finlande¹.

Malheureusement, je n’ai aucun contact en Finlande. D’un autre côté, je connais quelqu’un qui a vécu de nombreuses années en Suède. Peut-être qu’elle connaît des gens en Finlande. Sinon, elle a probablement encore des contacts en Suède, un pays voisin. Elle est ma meilleure chance de me rapprocher de la personne cible. Le fait est que, même si je ne connais pas la topologie du réseau social au-delà de mes propres contacts personnels, je peux utiliser des règles empiriques pour transmettre la lettre dans la bonne direction.

Si l’on adopte le point de vue des nœuds du réseau (les humains impliqués dans l’expérience), leurs actions disponibles sont de transmettre le message (la lettre) à l’un de leurs bords sortants (les contacts personnels). Cette problématique de transmettre le message dans le bon sens offre l’occasion de s’amuser avec le machine learning !

Les nœuds ne perçoivent pas l’ensemble de la topologie du réseau. Nous pouvons mettre en place un environnement qui les récompense pour avoir acheminé le message le long du chemin connu le plus court, tout en les encourageant à explorer les chemins candidats sous-optimaux. Cela semble être un excellent cas d’utilisation pour l’apprentissage par renforcement, n’est-ce pas ?

Pour ceux qui souhaitent exécuter le code, vous pouvez accéder au dépôt ici.

Le problème

Nous obtiendrons un graphe orienté dans lequel les arêtes entre les nœuds sont clairsemées, ce qui signifie que le nombre moyen d’arêtes sortantes d’un nœud est nettement inférieur au nombre de nœuds. De plus, les bords auront un coût associé. Cette fonctionnalité supplémentaire généralise le cas de la Small-World Experiment, où chaque saut de la lettre comptait pour un coût de 1.

Le problème que nous considérerons est de concevoir un algorithme d’apprentissage par renforcement qui trouve un chemin depuis un nœud de départ arbitraire vers un nœud cible arbitraire dans un graphe orienté clairsemé, avec un coût aussi bas que possible, si un tel chemin existe. Des solutions déterministes existent pour ce problème. Par exemple, L’algorithme de Dijkstra trouve le chemin le plus court depuis un nœud de départ vers tous les autres nœuds dans un graphe orienté. Cela sera utile pour évaluer les résultats de notre algorithme d’apprentissage par renforcement, qui n’est pas garanti de trouver la solution optimale.

Q-Apprentissage

Q-Apprentissage est une technique d’apprentissage par renforcement dans laquelle un agent maintient un tableau de paires état-action, associées à la récompense cumulée actualisée attendue – le qualitéd’où le Q-Apprentissage. Grâce à des expériences itératives, le tableau est mis à jour jusqu’à ce qu’un critère d’arrêt soit satisfait. Après entraînement, l’agent peut choisir l’action (la colonne de la matrice Q) correspondant à la qualité maximale, pour un état donné (la ligne de la matrice Q).

La règle de mise à jour, compte tenu d’une action d’essai a_jentraînant le passage de l’état s_je déclarer s_kune récompense ret une meilleure estimation de la qualité du prochain état s_kest:

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

_{Équation 1 : la règle de mise à jour pour Q-Learning.}

Dans l’équation 1 :

• α est le taux d’apprentissage, contrôlant la rapidité avec laquelle les nouveaux résultats effaceront les anciennes estimations de qualité.
• γ est le facteur d’actualisation, contrôlant la comparaison entre les récompenses futures et les récompenses immédiates.
• Q est la matrice de qualité. L’index des lignes i est l’index de l’état d’origine et l’index de la colonne j est l’index de l’action sélectionnée.

En bref, l’équation 1 indique que la qualité de (état, action) devrait être en partie mise à jour avec une nouvelle valeur de qualité, constituée de la somme de la récompense immédiate et de l’estimation actualisée de la qualité maximale de l’état suivant sur les actions possibles.

Pour notre énoncé du problème, une formulation possible pour l’état serait la paire (nœud actuel, nœud cible), et l’ensemble des actions serait l’ensemble des nœuds. L’ensemble d’états contiendrait alors N² valeurs, et l’ensemble d’actions contiendrait N valeurs, où N est le nombre de nœuds. Cependant, comme le graphe est clairsemé, un nœud d’origine donné n’a qu’un petit sous-ensemble de nœuds comme arêtes sortantes. Cette formulation entraînerait une Q-matrice où la grande majorité des N³ les entrées ne sont jamais visitées, consommant inutilement de la mémoire.

Agents distribués

Une meilleure utilisation des ressources consiste à répartir les agents. Chaque nœud peut être considéré comme un agent. L’état de l’agent est le nœud cible, d’où son Q-la matrice a N lignes et N_dehors colonnes (le nombre d’arêtes sortantes pour ce nœud spécifique). Avec N agents, le nombre total d’entrées de la matrice est N²N_dehorsce qui est inférieur à N³.

Pour résumer :

• Nous nous entraînerons N agents, un pour chaque nœud du graphique.
• Chaque agent apprendra un Q-matrice de dimensions [N x N_out]. Le nombre de fronts sortants (N_dehors) peut varier d’un nœud à l’autre. Pour un graphe peu connecté, N_dehors << N.
• Les indices de ligne du Q-matrix correspond à l’état de l’agent, c’est-à-dire le nœud cible.
• Les indices de colonnes du Q-matrix correspond au edge sortant sélectionné par un agent pour acheminer un message vers le nœud cible.
• Q[i, j] représente l’estimation par un nœud de la qualité de transmission du message à son j^ème bord sortant, étant donné que le nœud cible est i.
• Lorsqu’un nœud reçoit un message, il inclut le nœud cible. Puisque l’expéditeur du message précédent n’est pas nécessaire pour déterminer le routage du message suivant, il ne sera pas inclus dans ce dernier.

Code

La classe principale, le nœud, sera nommé 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 classe QNode comporte trois champs : le nombre de nœuds dans le graphe, la liste des arêtes sortantes et le Q-matrice. Le Q-matrix est initialisé avec des zéros. Les récompenses reçues de l’environnement seront négatives par rapport aux coûts marginaux. Par conséquent, les valeurs de qualité seront toutes négatives. Pour cette raison, l’initialisation avec des zéros est une initialisation optimiste.

Lorsqu’un message parvient à un QNode objet, il sélectionne l’un de ses bords sortants à travers le epsilon-gourmand algorithme. Si ε est petit, l’algorithme epsilon-gourmand sélectionne la plupart du temps l’arête sortante ayant le plus haut Q-valeur. De temps en temps, il sélectionnera un bord sortant au hasard :

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

L’autre classe est le graphe, appelé 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))

Ses principaux champs sont la liste des nœuds et le tableau des coûts de périphérie. Notez que les arêtes réelles font partie du QNode classe, sous forme de liste de nœuds sortants.

Lorsque nous voulons générer un chemin depuis un nœud de départ vers un nœud cible, nous appelons le QGraph.trajectory() méthode, qui appelle le QNode.epsilon_greedy() méthode:

    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

Le trajectory() La méthode renvoie la liste des nœuds visités le long du chemin et la liste des coûts associés aux arêtes qui ont été utilisées.

La dernière pièce manquante est la règle de mise à jour de l’équation 1, implémentée par le QGraph.update_Q() méthode:

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

Pour former nos agents, nous parcourons de manière itérative les paires de (start_node, target_node) avec une boucle interne sur les nœuds voisins de start_nodeet nous appelons update_Q().

Expériences et résultats

Commençons par un simple graphe de 12 nœuds, avec des arêtes pondérées dirigées.

Nous pouvons observer sur la figure 1 que le seul nœud entrant vers le nœud-1 est le nœud-7, et que le seul nœud entrant vers le nœud-7 est le nœud-1. Par conséquent, aucun autre nœud que ces deux-là ne peut atteindre le nœud 1 et le nœud 7. Lorsqu’un autre nœud est chargé d’envoyer un message au nœud-1 ou au nœud-7, le message rebondira sur le graphique jusqu’à ce que le nombre maximum de sauts soit atteint. Nous nous attendons à voir un résultat négatif important Q-valeurs dans ces cas.

Quand nous entraînons notre graphiqueon obtient des statistiques sur le coût et le nombre de sauts en fonction de l’époque, comme dans la figure 2 :

Après l’entraînement, c’est le Q-matrice pour le nœud-4 :

La trajectoire du nœud 4 jusqu’au nœud 11, par exemple, peut être obtenue en appelant le trajectory() méthode, réglage epsilon=0 pour la solution déterministe gloutonne : [4, 3, 5, 11] pour un coût total non actualisé de 0,9 + 0,9 + 0,3 = 2,1. L’algorithme de Dijkstra renvoie le même chemin.

Dans de rares cas, le chemin optimal n’a pas été trouvé. Par exemple, pour passer du nœud 6 au nœud 9, une instance spécifique du Q-graph entraîné a renvoyé [6, 11, 0, 4, 10, 2, 9] pour un coût total non actualisé de 3,5, tandis que l’algorithme de Dijkstra renvoyait [6, 0, 4, 10, 2, 9] pour un coût total non actualisé de 3,4. Comme nous l’avons dit précédemment, cela est attendu d’un algorithme itératif

Conclusion

Nous avons formulé l’expérience Small-World comme un problème consistant à trouver le chemin avec un coût minimum entre n’importe quelle paire de nœuds dans un graphe orienté clairsemé avec des arêtes pondérées. Nous avons implémenté les nœuds en tant qu’agents Q-Learning, qui apprennent grâce à la règle de mise à jour à entreprendre l’action la moins coûteuse, étant donné un nœud cible.

Avec un graphique simple, nous avons montré que la formation aboutissait à une solution proche de la solution optimale.

Merci pour votre temps et n’hésitez pas à expérimenter avec le code. Si vous avez des idées d’applications amusantes pour le Q-Learning, n’hésitez pas à me le faire savoir !

---

¹ OK, je vais au-delà de l’expérience originale du petit monde, qui devrait s’appeler l’expérience du petit pays.

Références

Apprentissage par renforcement, Richard S. Sutton, Andrew G. Barto, MIT Press, 1998