Learning to Re-rank with Constrained Meta-Optimal Transport
Andrés Hoyos-Idrobo · 2023
Many re-ranking strategies in search systems rely on stochastic ranking policies, encoded as Doubly-Stochastic (DS) matrices, that satisfy desired ranking constraints in expectation, e.g., Fairness of Exposure (FOE). These strategies are generally two-stage pipelines: (i) an offline re-ranking policy construction step and (ii) an online sampling of rankings step. Building a re-ranking policy requires repeatedly solving a constrained optimization problem, one for each issued query. Thus, it is necessary to recompute the optimization procedure for any new/unseen query. Regarding sampling, the Birkhoff-von-Neumann decomposition (BvND) is the favored approach to draw rankings from any DS-based policy. Nonetheless, the BvND is too costly to compute online. Hence, the BvND as a sampling solution is memory-consuming as it can grow as O(N n2) for N queries and n documents.