Od bandytów do wyszukiwania drzew Monte-Carlo: Optymistyczna zasada stosowana w optymalizacji i planowaniu

Oryginalny tytuł:

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

Zawartość książki:

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning obejmuje kilka aspektów zasady "optymizmu w obliczu niepewności" dla problemów optymalizacji na dużą skalę przy skończonym budżecie numerycznym. Początkowa motywacja monografii wynikała z empirycznego sukcesu tak zwanej metody "Monte-Carlo Tree Search" spopularyzowanej w komputerowej grze Go i rozszerzonej na wiele innych gier, a także problemów optymalizacji i planowania.

Określa ona teoretyczne podstawy tej dziedziny poprzez scharakteryzowanie złożoności problemów optymalizacyjnych i zaprojektowanie skutecznych algorytmów z gwarancją wydajności. Główny kierunek podążania w tej monografii polega na dekompozycji złożonego problemu decyzyjnego (takiego jak problem optymalizacji w dużej przestrzeni poszukiwań) na sekwencję elementarnych decyzji, gdzie każda decyzja sekwencji jest rozwiązywana przy użyciu stochastycznego "wielorękiego bandyty" (matematyczny model podejmowania decyzji w środowiskach stochastycznych). Definiuje to hierarchiczne wyszukiwanie, które posiada przyjemną cechę rozpoczynania eksploracji od quasi-jednolitego próbkowania przestrzeni, a następnie skupiania się, w różnych skalach, na najbardziej obiecujących obszarach (przy użyciu zasady optymistycznej), aż do ostatecznego przeprowadzenia lokalnego wyszukiwania wokół globalnych optymalnych wartości funkcji.

Niniejsza monografia rozważa problem optymalizacji funkcji w ogólnych przestrzeniach przeszukiwania (takich jak przestrzenie metryczne, przestrzenie strukturalne, drzewa i grafy), jak również problem planowania w Markowskich procesach decyzyjnych. Jej głównym wkładem jest klasa hierarchicznych algorytmów optymistycznych z różnymi instancjami algorytmicznymi w zależności od tego, czy oceny są zaszumione czy zaszumione oraz czy pewna miara lokalnej "gładkości" funkcji wokół globalnego maksimum jest znana czy nieznana.