Pseudo ε-Net Method with Delayed Decisions Based on Representatives and Anti-Representatives for Multi-Agent Stream Classification

A method for constructing a pseudo ε-net (PεN) for stream classification in metric spaces is proposed for real-time multi-agent systems. The method significantly reduces the set of stored elements by introducing representatives—centers of balls with a specific action label, where all elements of the classified set correspond to that action—and anti-representatives—centers of uncertainty balls in which no single action can be uniquely chosen, allowing an agent to defer the decision until additional information is available. Sufficient conditions for the existence of a pseudo ε-net are formulated in terms of ε-consistency of action classes, and training and classification algorithms with logarithmic query complexity are given. In a traffic balancing problem with 25,000 states, the PεN method reduces inter-agent communication by up to 74% with a classification accuracy of 0.93, or by 60% with an accuracy of 0.96, while degrading the balancing objective by 2% at most. The stored state set is reduced by a factor of up to 150× compared to k-NN. Compared with k-NN, Centroids, and SAMAROH-2L on two real network topologies (Abilene and Geant2009), PεN attains an action-prediction accuracy not lower than that of the baselines at a comparable number of message exchanges, while storing substantially fewer representatives. When compared with published prototype-based classifiers—LVQ1, GLVQ, the open-source GLVQ, LRVQ with a local reject option, and Prototypical Nets—on the same per-iteration protocol, PεN attains comparable accuracy, while additionally providing a built-in rejection mechanism and correctness guarantees.