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

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 america, with the instruction to ahead the letter to their private contact almost definitely to know one other individual – the goal – in the identical nation. In flip, the individual receiving the letter can 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 change 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⁸ individuals, via just a few hops.

How is that potential? 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. However, 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 finest guess 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 correct course.

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 all their outgoing edges (private contacts). This drawback of transmitting the message in the correct course presents a chance to have enjoyable with machine studying!

Nodes don’t understand the entire community topology. We are able to 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 feels like a terrific use case for reinforcement studying, don’t you suppose?

For these inquisitive about operating the code, you possibly can attain the repo right here.

The Downside

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 price 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 price as little as potential, 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 shall 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 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. 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 finest estimate of the standard of the following 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 fast 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.

Briefly, equation 1 states that the standard of (state, motion) must be partly up to date with a brand new high quality worth, manufactured from the sum of the fast reward and the discounted estimate of the following state’s most high quality over potential actions.

For our drawback assertion, a potential 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. 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 may 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 full 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 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’s going to embrace the goal node. For the reason that sender of the earlier message will not be wanted to find out the routing of the following message, it won’t 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 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)  # At the very least 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 adverse
                # 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 adverse of the sting prices. Therefore, the standard values will all be adverse. Because of this, initializing with zeros is an optimistic initialization.

When a message reaches a QNode object, it selects one in all 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 very best Q-value. Every so often, it’s going to 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, 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 predominant 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 a listing of outgoing nodes.

After we wish 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)
            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() methodology 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() methodology:

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 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 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. Due to this fact, 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 count on to see giant adverse Q-values in these instances.

After 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, may be obtained by calling the trajectory() methodology, 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 carried out 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 on your time, and be happy 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