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

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

I’m nonetheless amazed by the thought that individuals with ~10² contacts handle to attach with a random particular person in a community of ~10⁸ individuals, via a number of hops.

How is that doable? Heuristics.

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

Sadly, I don’t have any contacts in Finland. Alternatively, I do know somebody who lived in Sweden for a few years. Maybe she is aware of individuals in Finland. If not, she in all probability nonetheless has contacts in Sweden, which is a neighboring nation. She is my greatest guess to get nearer to the goal particular person. 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 correct path.

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

Nodes don’t understand the entire community topology. We are able to arrange an atmosphere that rewards them for routing the message alongside the shortest recognized path, whereas encouraging them to discover sub-optimal candidate paths. That feels like an important use case for reinforcement studying, don’t you assume?

For these curious about 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, that means the typical variety of outgoing edges from a node is considerably smaller than the variety of nodes. Moreover, the perimeters can 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 think about 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 drawback. For instance, Dijkstra’s algorithm finds the shortest path from a begin node to all the opposite nodes in a directed graph. This can be helpful to guage the outcomes of our reinforcement studying algorithm, which isn’t assured to search out the optimum resolution.

Q-Studying

Q-Studying is a reinforcement studying approach 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. By way of 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) similar 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_okay, a reward r, and a greatest estimate of the standard of the subsequent state s_okay, 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 fee, controlling how briskly new outcomes will erase previous high quality estimates.
• γ is the low cost issue, controlling how a lot future rewards examine 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) must be partly up to date with a brand new high quality worth, fabricated from the sum of the rapid reward and the discounted estimate of the subsequent state’s most high quality over doable actions.

For our drawback 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 include N² values, and the motion set would include 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 massive 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 will be regarded as 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 range from one node to a different. For a sparsely linked 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. For the reason that sender of the earlier message isn’t wanted to find out the routing of the subsequent message, it is not going to be included within the latter.

Code

The core class, the node, can 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 isn't 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 can be unfavorable
                # 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 isn't 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 acquired from the atmosphere would be the unfavorable of the sting prices. Therefore, the standard values will all be unfavorable. For that reason, initializing with zeros is an optimistic initialization.

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

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

The opposite class is the graph, referred to 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.

Once 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, applied 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 via the pairs of (start_node, target_node) with an inside 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 are able to 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. Subsequently, no different node apart from 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 anticipate to see giant unfavorable Q-values in these instances.

Once we practice our graph, we get statistics about the fee and the variety of hops as a perform 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, will 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 selected 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 acknowledged 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 applied the nodes as Q-Studying brokers, who be taught via the replace rule to take the least pricey motion, given a goal node.

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

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

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

References

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