# Learning Permutations with Sinkhorn Policy Gradient

arXiv: https://arxiv.org/abs/1805.07010 · HTML: https://mlsanity.com/paper/1805.07010/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2018.

## Built on by (most cited first, 26 of 26)

- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems](https://mlsanity.com/paper/2207.03876/) (2022)
- [Federated Learning of Models Pre-Trained on Different Features with Consensus Graphs](https://mlsanity.com/paper/2306.01240/) (2023)
- [FGOT: Graph Distances based on Filters and Optimal Transport](https://mlsanity.com/paper/2109.04442/) (2021)
- [Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem](https://mlsanity.com/paper/2203.00903/) (2022)
- [Set-to-Sequence Methods in Machine Learning: a Review](https://mlsanity.com/paper/2103.09656/) (2021)
- [Assessment of Reinforcement Learning Algorithms for Nuclear Power Plant Fuel Optimization](https://mlsanity.com/paper/2305.05812/) (2023)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Multivariate rank via entropic optimal transport: sample efficiency and generative modeling](https://mlsanity.com/paper/2111.00043/) (2021)
- [PROPEL: Supervised and Reinforcement Learning for Large-Scale Supply Chain Planning](https://mlsanity.com/paper/2504.07383/) (2025)
- [Combinatorial Optimization Augmented Machine Learning](https://mlsanity.com/paper/2601.10583/) (2026)
- [SOTAlign: Semi-Supervised Alignment of Unimodal Vision and Language Models via Optimal Transport](https://mlsanity.com/paper/2602.23353/) (2026)
- [Neural Simulated Annealing](https://mlsanity.com/paper/2203.02201/) (2022)
- [Enforcing convex constraints in Graph Neural Networks](https://mlsanity.com/paper/2510.11227/) (2025)
- [Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2107.06870/) (2021)
- [PermLLM: Learnable Channel Permutation for N:M Sparse Large Language Models](https://mlsanity.com/paper/2510.10136/) (2025)
- [Permutation Picture of Graph Combinatorial Optimization Problems](https://mlsanity.com/paper/2410.17111/) (2024)
- [DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs](https://mlsanity.com/paper/2505.23131/) (2025)
- [Learning Unbiased Permutations via Flow Matching](https://mlsanity.com/paper/2605.16755/) (2026)
- [Learning Permutation from Structure Without Supervision](https://mlsanity.com/paper/2605.25551/) (2026)
- [Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields](https://mlsanity.com/paper/2610.18186/) (2026)

## Abstract (arXiv)

Many problems at the intersection of combinatorics and computer science require solving for a permutation that optimally matches, ranks, or sorts some data. These problems usually have a task-specific, often non-differentiable objective function that data-driven algorithms can use as a learning signal. In this paper, we propose the Sinkhorn Policy Gradient (SPG) algorithm for learning policies on permutation matrices. The actor-critic neural network architecture we introduce for SPG uniquely decouples representation learning of the state space from the highly-structured action space of permutations with a temperature-controlled Sinkhorn layer. The Sinkhorn layer produces continuous relaxations of permutation matrices so that the actor-critic architecture can be trained end-to-end. Our empirical results show that agents trained with SPG can perform competitively on sorting, the Euclidean TSP, and matching tasks. We also observe that SPG is significantly more data efficient at the matching task than the baseline methods, which indicates that SPG is conducive to learning representations that are useful for reasoning about permutations.