Przejdź do treści

Don’t Predict Counterfactual Values, Predict Expected Values Instead

Algorytmy minimalizacji żalu kontrfaktycznego (Counterfactual Regret Minimization, CRM) są najpopularniejszym sposobem szacowania równowagi Nasha w grach o sumie zerowej z niepełną informacją. W szczególności, zaawansowany bot do pokera, DeepStack, wykorzystuje tzw. Deep Counterfactual Value Network (DCVN) do nauki wartości kontrfaktycznych (CFV) związanych z różnymi stanami gry. Każda wartość kontrfaktyczna to iloczyn dwóch czynników: (1) prawdopodobieństwa, że przeciwnik osiągnie dany stan w grze, które można obliczyć na podstawie danych wejściowych, oraz (2) oczekiwanej wartości (EV) wypłaty w tym stanie, która jest złożoną funkcją danych wejściowych, trudną do obliczenia. W niniejszym artykule proponujemy prostą, ale skuteczną modyfikację procesu szacowania CFV, polegającą na wykorzystaniu głębokiej sieci neuronowej do szacowania jedynie czynnika EV wartości kontrfaktycznej. Nowe podejście znacznie upraszcza problem nauki i prowadzi do dokładniejszego szacowania CFV. Bezpośrednie porównanie strat predykcji CFV wykazuje znaczną poprawę dokładności predykcji proponowanego podejścia (DEVN) w porównaniu z oryginalną formułą DCVN (relatywnie o 9,18-15,70%, w zależności od konkretnego ustawienia eksperymentu). Ponadto zastosowanie DEVN poprawia teoretyczną, dolną granicę błędu o 29,05-31,83% w porównaniu do treningu opartego na DCVN. Dodatkowo, DEVN osiąga cel wykorzystując do wnioskowania znacznie mniejsze i szybsze sieci. Chociaż proponowana modyfikacja może wydawać się raczej techniczna, w rzeczywistości przedstawia fundamentalnie inne podejście do procesu nauki i szacowania CFV, ponieważ rozkłady sygnałów treningowych różnią się znacząco między DCVN a DEVN. Pierwszy szacuje CFV, które są obciążone prawdopodobieństwem osiągnięcia danego stanu gry, podczas gdy trening drugiego opiera się na bezpośrednim szacowaniu EV, niezależnie od prawdopodobieństwa stanu. W efekcie sygnał nauki DEVN lepiej odzwierciedla rzeczywistą wartość danego stanu, co pozwala na dokładniejsze szacowanie CFV.

Materiał konferencyjny:

Proceedings of the 37th AAAI Conference on Artificial Intelligence

Autorzy z PW:

Jacek Mańdziuk

Rok wydania: