Många problem vid korsningen av kombinatorik och datavetenskap kräver att lösa för en permutation som optimalt matchar, rankar, eller sorterar vissa data. Dessa problem har vanligtvis en uppgiftsspecifik, ofta icke-differential objektiv funktion som datadrivna algoritmer kan använda som en inlärningssignal. I detta dokument föreslår vi Sinkhorn Policy Gradient (SPG) algoritm för lärande policyer på permutationsmatriser. Den skådespelare-kritiska neurala nätverk arkitektur vi introducerar för SPG unikt frikopplar representation lära av tillståndet utrymme från den mycket strukturerade åtgärd utrymme permutationer med en temperaturreglerad Sinkhorn lager. Sinkhorn-lagret ger kontinuerliga avkopplingar av permutationsmatriser så att den skådespelare-kritiska arkitekturen kan tränas end-to-end. Våra empiriska resultat visar att agenter som utbildats med SPG kan prestera konkurrenskraftigt på sortering, Euclidean TSP, och matchande uppgifter. Vi observerar också att SPG är betydligt mer dataeffektiv vid matchningsuppgiften än basalmetoderna, vilket indikerar att SPG bidrar till lärande representationer som är användbara för resonemang om permutationer.
Det arbete som presenteras i REF använder sig av ett aktörskritiskt lärande på permutationsmatriser.
Learning Permutations with Sinkhorn Policy Gradient
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}