Att lära sig gå över en graf mot en målnod för en given fråga och en källnod är ett viktigt problem i tillämpningar som kunskapsbaskomplettering (KBC). Det kan formuleras som en förstärkning lärande (RL) problem med en känd stat övergångsmodell. För att övervinna utmaningen med glesa belöningar, utvecklar vi en graf-walking agent som kallas M-Walk, som består av en djup återkommande neurala nätverk (RNN) och Monte Carlo Tree Search (MCTS). RNN kodar tillståndet (dvs. historien om den gångna vägen) och kartlägger det separat till en policy och Q-värden. För att effektivt träna agenten från glesa belöningar kombinerar vi MCTS med den neurala politiken för att generera banor som ger mer positiva belöningar. Av dessa banor förbättras nätverket på ett icke-politiskt sätt med hjälp av Q-learning, vilket ändrar RNN-policyn genom parameterdelning. Vår föreslagna RL-algoritm tillämpar upprepade gånger detta policyförbättringssteg för att lära sig modellen. Vid testtillfället kombineras MCTS med neuralpolitiken för att förutsäga målnoden. Experimentella resultat på flera graf-walking riktmärken visar att M-Walk kan lära sig bättre politik än andra RL-baserade metoder, som huvudsakligen bygger på policy gradienter. M-Walk överträffar också traditionella KBC-baslinjer.
REF använder Monte Carlo Tree Search för att övervinna problemet med sparsam belöning.
M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search
{'venue': 'NeurIPS', 'journal': None, 'mag_field_of_study': ['Computer Science']}