Dai banditi alla ricerca ad albero Monte-Carlo: Il principio ottimistico applicato all'ottimizzazione e alla pianificazione

Titolo originale:

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

Contenuto del libro:

Dai banditi alla ricerca ad albero Monte-Carlo: The Optimistic Principle Applied to Optimization and Planning tratta diversi aspetti del principio dell'"ottimismo di fronte all'incertezza" per problemi di ottimizzazione su larga scala con budget numerico finito. La motivazione iniziale della monografia deriva dal successo empirico del cosiddetto metodo "Monte-Carlo Tree Search", reso popolare dal Go al computer ed esteso a molti altri giochi, nonché a problemi di ottimizzazione e pianificazione.

La monografia pone le basi teoriche del settore, caratterizzando la complessità dei problemi di ottimizzazione e progettando algoritmi efficienti con garanzie di prestazioni. La direzione principale seguita in questa monografia consiste nel decomporre un problema decisionale complesso (come un problema di ottimizzazione in un grande spazio di ricerca) in una sequenza di decisioni elementari, dove ogni decisione della sequenza viene risolta utilizzando un "bandito a più braccia" stocastico (modello matematico per le decisioni in ambienti stocastici). Questo definisce una ricerca gerarchica che ha la caratteristica di iniziare l'esplorazione con un campionamento quasi uniforme dello spazio e poi di concentrarsi, a scale diverse, sulle aree più promettenti (utilizzando il principio dell'ottimismo), fino a eseguire una ricerca locale intorno all'optima globale della funzione.

Questa monografia considera il problema dell'ottimizzazione di funzioni in spazi di ricerca generali (come spazi metrici, spazi strutturati, alberi e grafi) e il problema della pianificazione nei processi decisionali di Markov. Il suo contributo principale è una classe di algoritmi ottimistici gerarchici con istanziazioni algoritmiche diverse a seconda che le valutazioni siano rumorose o prive di rumore e che sia nota o sconosciuta una misura della ''morbidezza'' locale della funzione intorno al massimo globale.