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.

本文提出了 Sinkhorn Policy Gradient (SPG) 算法，它使用了温度控制的 Sinkhorn 层独特分离状态空间和高度结构化的置换操作空间的表示学习，取得了排序、欧几里得 TSP 和匹配任务的有竞争力的表现，并且可以有效地学习有用于推理置换的表示。