Optimistic Hedge - algorytm wykorzystujący aktualizację wag mnożeniowych z ekstrapolacją - jest jednym z naturalnych podejść do minimalizacji straty (regret) w grach. Przez lata naukowcy pytali, czy można osiągnąć stałą stratę niezależną od horyzontu czasowego i zależną wielomianowo od rozmiaru gry. Nowe badanie pokazuje, że odpowiedź zdecydowanie zależy od liczby graczy.
W grach dwuosobowych istnieje tempo uczenia się, dla którego Optimistic Hedge gwarantuje stratę O(n log n) niezależną od horyzontu T, gdzie n to liczba akcji dostępnych dla każdego gracza. To znaczący pozytywny wynik. Jednak sytuacja radykalnie się zmienia w grach trzygracza i większych: badacze konstruują przykłady gier, w których dla każdego tempa uczenia się strata pewnego gracza rośnie wykładniczo - wynosi 2 do potęgi Omega(n). Dla gier m-osobowych z m większym lub równym 3 konstruują gry, gdzie strata osiąga 2 do potęgi Omega(mn). Gdy tempo uczenia przekroczy próg 2 do potęgi -Omega(mn), strata może nawet rosnąć liniowo w horyzoncie czasowym.
Wyniki stanowią przełom w zrozumieniu granic tego algorytmu i pokazują, że uczenie się w grach wieloosobowych jest fundamentalnie trudniejsze niż w grach dwuosobowych. Badanie rozstrzyga długotrwały otwarty problem w teorii gier i ma implikacje dla algorytmów rozproszonych i systemów wieloagentowych w sztucznej inteligencji.