Learning Permutations with Sinkhorn Policy Gradient

Understand

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.