Confessioni di un MDP mascherato

Abstract degli autori

Nell’apprendimento per rinforzo si presume che l’insieme delle azioni sia noto in anticipo e, quindi, che si sappia prima di iniziare i calcoli se alcune coppie stato-azione non sono ammissibili. In alcune applicazioni, determinare questa maschera delle azioni è il principale collo di bottiglia computazionale. Per mettere in luce le proprietà fondamentali del problema, studiamo come combinare la ricerca di una politica ottimale con l’apprendimento della maschera stessa, nell’ambito di un modello MDP lineare in cui ogni azione tentata rivela il valore esatto di un punteggio lineare che ne determina la validità. In questo quadro, costruiamo anzitutto un algoritmo basato sull’ottimizzazione ottimistica deterministica e dimostriamo che è ottimale in senso minimax e computazionalmente efficiente. Mostriamo tuttavia che non è ottimale nei casi non degeneri. Proponiamo quindi un’alternativa, anch’essa computazionalmente efficiente, che pianifica la propria strategia di esplorazione. Questo algoritmo ammette un’interpretazione formale come analogo dell’information-directed sampling per il feedback deterministico, che potrebbe essere di interesse a sé stante. Infine, studiamo un’applicazione di questo quadro al transfer learning, in cui l’insieme delle azioni non valide cambia nel tempo.