Multi-Positive Top-$K$ Recommendation: A Differentiable Dynamic Programming Approach

Modern recommender systems typically optimize for top-$K$ retrieval; however, they largely rely on continuous surrogate loss functions due to the non-differentiable nature of ranking metrics. A fundamental limitation of these conventional losses is that they evaluate positive items independently—contrasting a single positive item against one or more negative items per instance. Consequently, they fail to capture the joint combinatorial structure and mutual associations among a user's multiple positive interactions. To overcome this bottleneck, we adopt a novel framework powered by Differentiable Dynamic Programming (DiffDP), which reformulates multi-positive item selection as a dynamic programming process. Specifically, we leverage the Fenchel-Young loss framework—a theoretically rigorous surrogate objective that enables direct optimization over joint multi-positive subsets. By regularizing the multi-positive selection problem with Shannon entropy, our dynamic programming formulation recovers the exact log-partition function of a Conditional Poisson Binomial Distribution (CPBD). Unlike Gumbel-perturbed relaxes or sampling-based approaches, our formulation models simultaneous unordered sets under a strict global capacity constraint. This key property enables the exact, deterministic, and noise-free computation of marginal inclusion probabilities via automatic differentiation. Extensive experiments on real-world benchmark datasets demonstrate that our approach yields competitive top-$K$ recommendation performance. The code is provided anonymously at https://anonymous.4open.science/r/Differentiable-Dynamic-Programming-1857.