Interaction-Aware Client Selection in Federated Learning via Learned Coalition Utility

Client selection in federated learning is inherently combinatorial. The value of a training round depends on which clients train together, not on their individual contributions alone. Clients with overlapping data are redundant when combined, while those with complementary data reinforce one another, and which of these relationships matter shifts as the global model evolves. Methods that rank clients by individual importance, including Shapley-based selectors, and methods limited to pairwise correlations cannot capture this higher-order, evolving structure. We introduce , which learns a surrogate of coalition utility directly and selects client subsets by their predicted joint utility. A tree-based surrogate captures client interactions up to a controllable order and is refit each round to track the evolving learning dynamics. The same surrogate proposes the candidate pool and chooses the aggregation set, and we analyse the induced selection regret. Because the fitted surrogate decomposes additively into interaction effects, each selection step scores a candidate by its individual effect and its interactions with the clients already selected, making the policy interpretable. Across twelve settings on nine datasets, attains the highest trajectory-mean accuracy in every setting, by up to $12$ points over the strongest baseline.