Od banditov k Monte-Carlo Tree Search: Optimistický princíp aplikovaný na optimalizáciu a plánovanie

Pôvodný názov:

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

Obsah knihy:

Od banditov k Monte-Carlovmu prehľadávaniu stromov: Princíp optimizmu aplikovaný na optimalizáciu a plánovanie zahŕňa niekoľko aspektov princípu "optimizmu tvárou v tvár neistote" pre rozsiahle optimalizačné problémy s konečným numerickým rozpočtom. Prvotná motivácia monografie vyplynula z empirického úspechu takzvanej metódy "Monte-Carlo Tree Search" spopularizovanej v počítačovej hre Go a ďalej rozšírenej na mnohé ďalšie hry, ako aj na optimalizačné a plánovacie problémy.

Stanovuje teoretické základy tejto oblasti charakterizovaním zložitosti optimalizačných problémov a návrhom efektívnych algoritmov so zárukou výkonnosti. Hlavný smer, ktorý sa sleduje v tejto monografii, spočíva v dekompozícii komplexného rozhodovacieho problému (napríklad optimalizačného problému vo veľkom priestore hľadania) na postupnosť elementárnych rozhodnutí, pričom každé rozhodnutie z tejto postupnosti sa rieši pomocou stochastického "viacramenného banditu" (matematický model rozhodovania v stochastickom prostredí). Tým sa definuje hierarchické vyhľadávanie, ktoré má tú peknú vlastnosť, že sa začína skúmaním kvázi rovnomerným vzorkovaním priestoru a potom sa v rôznych mierkach zameriava na najsľubnejšie oblasti (s použitím optimistického princípu), až sa nakoniec vykoná lokálne vyhľadávanie okolo globálneho optima funkcie.

Táto monografia sa zaoberá problémom optimalizácie funkcií vo všeobecných prehľadávacích priestoroch (ako sú metrické priestory, štruktúrované priestory, stromy a grafy), ako aj problémom plánovania v markovských rozhodovacích procesoch. Jej hlavným prínosom je trieda hierarchických optimistických algoritmov s rôznymi inštanciami algoritmu v závislosti od toho, či sú vyhodnotenia zašumené alebo nezašumené a či je známa alebo neznáma nejaká miera lokálnej ''hladkosti'' funkcie v okolí globálneho maxima.