In one set of embodiments, a deep reinforcement learning (RL) system can train an agent to construct an efficient decision tree for classifying network packets according to a rule set, where the training includes: identifying, by an environment of the deep RL system, a leaf node in a decision tree; computing, by the environment, a graph structure representing a state of the leaf node, the graph structure including information regarding how one or more rules in the rule set that are contained in the leaf node are distributed in a hypercube of the leaf node; communicating, by the environment, the graph structure to the agent; providing, by the agent, the graph structure as input to a graph neural network; and generating, by the graph neural network based on the graph structure, an action to be taken on the leaf node for extending the decision tree.