From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning
A banditáktól a Monte-Carlo fakeresésig: Az optimizmus elve az optimalizálásban és a tervezésben alkalmazva: Az optimizmus a bizonytalansággal szemben: Az optimista elv az optimalizálás és a tervezés számos aspektusát tárgyalja nagyméretű optimalizálási problémákra, véges numerikus költségvetés mellett. A monográfia kezdeti motivációját a számítógépes góban népszerűsített, majd számos más játékra, valamint optimalizálási és tervezési problémákra kiterjesztett úgynevezett "Monte-Carlo Tree Search" módszer empirikus sikere adta.
A könyv az optimalizálási problémák komplexitásának jellemzésével és hatékony, teljesítménygaranciával rendelkező algoritmusok tervezésével fekteti le a terület elméleti alapjait. A monográfia által követett fő irányvonal abban áll, hogy egy komplex döntéshozatali problémát (például egy optimalizálási problémát egy nagy keresési térben) elemi döntések sorozatára bontunk, ahol a sorozat minden egyes döntését egy sztochasztikus "többkarú bandit" (a sztochasztikus környezetben történő döntéshozatal matematikai modellje) segítségével oldjuk meg. Ez egy hierarchikus keresést határoz meg, amely rendelkezik azzal a szép tulajdonsággal, hogy a feltárást a tér kvázi-egyenletes mintavételezésével kezdi, majd különböző léptékben a legígéretesebb területekre összpontosít (az optimista elv alkalmazásával), míg végül a függvény globális optimuma körüli lokális keresést hajt végre.
Ez a monográfia az általános keresési terekben (például metrikus terekben, strukturált terekben, fákban és gráfokban) történő függvényoptimalizálás problémáját, valamint a Markov-döntési folyamatokban történő tervezés problémáját vizsgálja. Fő hozzájárulása a hierarchikus optimista algoritmusok egy osztálya, amelynek különböző algoritmikus instanciái attól függően, hogy az értékelések zajosak vagy zajmentesek, illetve hogy a függvény globális maximum körüli lokális ''simaságának'' valamilyen mértéke ismert vagy ismeretlen.