Apprendimento di MDP ad Albero Trattando le Politiche come Bracci di Bandit

Un nuovo articolo su arXiv (2605.04979) introduce un approccio per l'apprendimento online nei Problemi di Decisione Markoviani ad Albero (T-MDP) trattando ogni politica come un braccio in algoritmi bandit. I T-MDP sono MDP a orizzonte finito in cui ogni stato è raggiungibile dallo stato iniziale tramite una traiettoria unica, modellando naturalmente giochi sequenziali con perfetta memoria contro avversari stazionari. Gli autori mostrano che algoritmi bandit standard come LUCB e UCB possono essere applicati nonostante il numero esponenziale di politiche, progettando limiti di confidenza che condividono dati tra le politiche, consentendo memoria polinomiale e calcolo per passo. Vengono forniti limiti superiori dipendenti dall'istanza sulla complessità del campione e sul regret.