Routing in a Sparse Graph: a Distributed Q-Studying Strategy

concerning the Small-World Experiment, performed by Stanley Milgram within the 1960’s. He devised an experiment by which a letter was given to a volunteer individual in the USA, with the instruction to ahead the letter to their private contact most probably to know one other individual – the goal – in the identical nation. In flip, the individual receiving the letter could be requested to ahead the letter once more till the goal individual was reached. Though a lot of the letters by no means reached the goal individual, amongst people who did (survivorship bias at play right here!), the typical variety of hops was round 6. The “six levels of separation” has develop into a cultural reference to the tight interconnectivity of society.

I’m nonetheless amazed by the thought that folks with ~10² contacts handle to attach with a random individual in a community of ~10⁸ folks, by a couple of hops.

How is that doable? Heuristics.

Let’s assume I’m requested to ship a letter to a goal individual in Finland¹.

Sadly, I don’t have any contacts in Finland. Then again, I do know somebody who lived in Sweden for a few years. Maybe she is aware of folks in Finland. If not, she most likely nonetheless has contacts in Sweden, which is a neighboring nation. She is my greatest wager to get nearer to the goal individual. The purpose is, though I have no idea the topology of the social community past my very own private contacts, I can use guidelines of thumb to ahead the letter in the fitting path.

If we undertake the standpoint of the community’s nodes (the people concerned within the experiment), their obtainable actions are to ahead the message (the letter) to one in every of their outgoing edges (private contacts). This downside of transmitting the message in the fitting path gives a chance to have enjoyable with machine studying!

Nodes don’t understand the entire community topology. We will arrange an surroundings that rewards them for routing the message alongside the shortest identified path, whereas encouraging them to discover sub-optimal candidate paths. That appears like an amazing use case for reinforcement studying, don’t you suppose?

For these excited by working the code, you’ll be able to attain the repo right here.

The Drawback

We’ll be given a directed graph the place edges between nodes are sparse, which means the typical variety of outgoing edges from a node is considerably smaller than the variety of nodes. Moreover, the perimeters may have an related value. This extra function generalizes the case of the Small-World Experiment, the place every hop of the letter counted for a value of 1.

The issue we’ll contemplate is to design a reinforcement studying algorithm that finds a path from an arbitrary begin node to an arbitrary goal node in a sparse directed graph, with a value as little as doable, if such a path exists. Deterministic options exist for this downside. For instance, Dijkstra’s algorithm finds the shortest path from a begin node to all the opposite nodes in a directed graph. This will likely be helpful to guage the outcomes of our reinforcement studying algorithm, which isn’t assured to seek out the optimum resolution.

Q-Studying

Q-Studying is a reinforcement studying method the place an agent maintains a desk of state-action pairs, related to the anticipated discounted cumulative reward – the high quality, therefore the Q-Studying. Via iterative experiments, the desk is up to date till a stopping criterion is met. After coaching, the agent can select the motion (the column of the Q-matrix) equivalent to the maximal high quality, for a given state (the row of the Q-matrix).

The replace rule, given a trial motion a_j, ensuing within the transition from state s_i to state s_ok, a reward r, and a greatest estimate of the standard of the subsequent state s_ok, is:

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

_{Equation 1: The replace rule for Q-Studying.}

In equation 1:

• α is the training price, controlling how briskly new outcomes will erase previous high quality estimates.
• γ is the low cost issue, controlling how a lot future rewards evaluate with rapid rewards.
• Q is the standard matrix. The row index i is the index of the origin state, and the column index j is the index of the chosen motion.

In brief, equation 1 states that the standard of (state, motion) needs to be partly up to date with a brand new high quality worth, manufactured from the sum of the rapid reward and the discounted estimate of the subsequent state’s most high quality over doable actions.

For our downside assertion, a doable formulation for the state could be the pair (present node, goal node), and the set of actions could be the set of nodes. The state set would then comprise N² values, and the motion set would comprise N values, the place N is the variety of nodes. Nonetheless, as a result of the graph is sparse, a given origin node has solely a small subset of nodes as outgoing edges. This formulation would lead to a Q-matrix the place the big majority of the N³ entries are by no means visited, consuming reminiscence needlessly.

Distributed brokers

A greater use of assets is to distribute the brokers. Every node could be considered an agent. The agent’s state is the goal node, therefore its Q-matrix has N rows and N_out columns (the variety of outgoing edges for this particular node). With N brokers, the whole variety of matrix entries is N²N_out, which is decrease than N³.

To summarize:

• We’ll be coaching N brokers, one for every node within the graph.
• Every agent will be taught a Q-matrix of dimensions [N x N_out]. The variety of outgoing edges (N_out) can differ from one node to a different. For a sparsely related graph, N_out << N.
• The row indices of the Q-matrix correspond to the state of the agent, i.e., the goal node.
• The column indices of the Q-matrix correspond to the outgoing edge chosen by an agent to route a message towards the goal node.
• Q[i, j] represents a node’s estimate of the standard of forwarding the message to its j^th outgoing edge, given the goal node is i.
• When a node receives a message, it would embody the goal node. Because the sender of the earlier message will not be wanted to find out the routing of the subsequent message, it won’t be included within the latter.

Code

The core class, the node, will likely be named 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 will not be 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 = spherical(number_of_neighbors)
                number_of_neighbors = max(number_of_neighbors, 2)  # A minimum of two out-connections
                number_of_neighbors = min(number_of_neighbors, self.number_of_nodes)  # No more than N connections
                self.neighbor_nodes = random.pattern(vary(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 likely be destructive
                # q = self.Q[state, action]: state = goal node; motion = chosen neighbor node (transformed to column index) to route the message to

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

The category QNode has three fields: the variety of nodes within the graph, the listing of outgoing edges, and the Q-matrix. The Q-matrix is initialized with zeros. The rewards obtained from the surroundings would be the destructive of the sting prices. Therefore, the standard values will all be destructive. Because of this, initializing with zeros is an optimistic initialization.

When a message reaches a QNode object, it selects one in every of its outgoing edges by the epsilon-greedy algorithm. If ε is small, the epsilon-greedy algorithm selects more often than not the outgoing edge with the very best Q-value. Every so often, it would choose an outgoing edge randomly:

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

The opposite class is the graph, known as 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 vary(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))

Its major fields are the listing of nodes and the array of edge prices. Discover that the precise edges are a part of the QNode class, as an inventory of outgoing nodes.

After we need to generate a path from a begin node to a goal node, we name the QGraph.trajectory() technique, which calls the QNode.epsilon_greedy() technique:

    def trajectory(self, start_node, target_node, epsilon):
        visited_nodes = [start_node]
        prices = []
        if start_node == target_node:
            return visited_nodes, prices
        current_node = start_node
        whereas len(visited_nodes) < self.maximum_hops + 1:
            next_node = self.QNodes[current_node].epsilon_greedy(target_node, epsilon)
            value = float(self.cost_arr[current_node, next_node])
            visited_nodes.append(next_node)
            prices.append(value)
            current_node = next_node
            if current_node == target_node:
                return visited_nodes, prices
        # We reached the utmost variety of hops
        return visited_nodes, prices

The trajectory() technique returns the listing of visited nodes alongside the trail and the listing of prices related to the perimeters that have been used.

The final lacking piece is the replace rule of equation 1, carried out by the QGraph.update_Q() technique:

def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node):
   value = self.cost_arr[start_node, neighbor_node]
   reward = -cost
   # Q_orig(goal, dest) <- (1 - alpha) Q_orig(goal, dest) + alpha * ( r + gamma * max_neigh' Q_dest(goal, 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

To coach our brokers, we iteratively loop by the pairs of (start_node, target_node) with an internal loop over the neighbor nodes of start_node, and we name update_Q().

Experiments and Outcomes

Let’s begin with a easy graph of 12 nodes, with directed weighted edges.

We will observe from Determine 1 that the one incoming node to Node-1 is Node-7, and the one incoming node to Node-7 is Node-1. Due to this fact, no different node in addition to these two can attain Node-1 and Node-7. When one other node is tasked with sending a message to Node-1 or Node-7, the message will bounce across the graph till the utmost variety of hops is reached. We count on to see giant destructive Q-values in these instances.

After we practice our graph, we get statistics about the fee and the variety of hops as a operate of the epoch, as in Determine 2:

After coaching, that is the Q-matrix for Node-4:

The trajectory from Node-4 to, say, Node-11, could be obtained by calling the trajectory() technique, setting epsilon=0 for the grasping deterministic resolution: [4, 3, 5, 11] for a complete undiscounted value of 0.9 + 0.9 + 0.3 = 2.1. The Dijkstra algorithm returns the identical path.

In some uncommon instances, the optimum path was not discovered. For instance, to go from Node-6 to Node-9, a particular occasion of the skilled Q-graph returned [6, 11, 0, 4, 10, 2, 9] for a complete undiscounted value of three.5, whereas the Dijkstra algorithm returned [6, 0, 4, 10, 2, 9] for a complete undiscounted value of three.4. As we said earlier than, that is anticipated from an iterative algorithm

Conclusion

We formulated the Small-World Experiment as an issue of discovering the trail with minimal value between any pair of nodes in a sparse directed graph with weighted edges. We carried out the nodes as Q-Studying brokers, who be taught by the replace rule to take the least expensive motion, given a goal node.

With a easy graph, we confirmed that the coaching settled to an answer near the optimum one.

Thanks to your time, and be at liberty to experiment with the code. You probably have concepts for enjoyable functions for Q-Studying, please let me know!

¹ OK, I’m going past the unique Small-World Experiment, which needs to be known as the Small-Nation Experiment.

References

Reinforcement Studying, Richard S. Sutton, Andrew G. Barto, MIT Press, 1998