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

concerning 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 the US, with the instruction to ahead the letter to their private contact probably to know one other particular person – the goal – in the identical nation. In flip, the particular person receiving the letter can 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 common variety of hops was round 6. The “six levels of separation” has turn into 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, by means of a couple of hops.

How is that attainable? 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. Then again, 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 course.

If we undertake the perspective of the community’s nodes (the people concerned within the experiment), their out there actions are to ahead the message (the letter) to one among their outgoing edges (private contacts). This downside of transmitting the message in the correct course affords a chance to have enjoyable with machine studying!

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

For these desirous about operating the code, you’ll be able to attain the repo right here.

The Downside

We’ll be given a directed graph the place edges between nodes are sparse, that means the common variety of outgoing edges from a node is considerably smaller than the variety of nodes. Moreover, the sides may have an related price. 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 attainable, 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 shall be helpful to judge the outcomes of our reinforcement studying algorithm, which isn’t assured to search out the optimum answer.

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) akin 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 educational charge, controlling how briskly new outcomes will erase outdated high quality estimates.
• γ is the low cost issue, controlling how a lot future rewards evaluate with speedy 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, made from the sum of the speedy reward and the discounted estimate of the subsequent state’s most high quality over attainable actions.

For our downside assertion, a attainable formulation for the state can be the pair (present node, goal node), and the set of actions can 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. Nevertheless, 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 end in 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 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 overall 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 fluctuate 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 is going to embrace the goal node. For the reason that sender of the earlier message just 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, shall 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 just 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)  # No less than 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 shall be unfavourable
                # 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 just 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 setting would be the unfavourable of the sting prices. Therefore, the standard values will all be unfavourable. For that reason, initializing with zeros is an optimistic initialization.

When a message reaches a QNode object, it selects one among its outgoing edges by means of the epsilon-greedy algorithm. If ε is small, the epsilon-greedy algorithm selects more often than not the outgoing edge with the best Q-value. Now and again, it is going to 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 most important 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() methodology, which calls the QNode.epsilon_greedy() methodology:

    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)
            price = float(self.cost_arr[current_node, next_node])
            visited_nodes.append(next_node)
            prices.append(price)
            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() methodology returns the listing of visited nodes alongside the trail and the listing of prices related to the sides that have been used.

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

def update_Q(self, start_node, neighbor_node, alpha, gamma, target_node):
   price = 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 means of the pairs of (start_node, target_node) with an interior 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. Subsequently, no different node moreover 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 unfavourable Q-values in these circumstances.

After we prepare 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() methodology, setting epsilon=0 for the grasping deterministic answer: [4, 3, 5, 11] for a complete undiscounted price of 0.9 + 0.9 + 0.3 = 2.1. The Dijkstra algorithm returns the identical path.

In some uncommon circumstances, the optimum path was not discovered. For instance, to go from Node-6 to Node-9, a particular occasion of the educated Q-graph returned [6, 11, 0, 4, 10, 2, 9] for a complete undiscounted price of three.5, whereas the Dijkstra algorithm returned [6, 0, 4, 10, 2, 9] for a complete undiscounted price 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 price 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 means of 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 on your time, and be at liberty to experiment with the code. In case you have concepts for enjoyable purposes 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