Naukowcy z arXiv opublikowali badanie, które wprowadza nowy protokół porównywania wyników algorytmów uczenia ze wzmacnianiem dla problemu średniej nagrody. Głównym problemem w dotychczasowych publikacjach była trudność w porównywaniu gwarancji teoretycznych, ponieważ różne prace używały różnych metod, parametrów strukturalnych i założeń dotyczących informacji wstępnej.
Autorzy skonstruowali jawny dolny certyfikat dla skończonych problemów z komunikacją między stanami (MDPs) przy użyciu drzewa binarnego złożonego z dwustanowych bloków. Ich podejście opiera się na dokładnej analizie dywergencji Kullbacka-Leiblera na poziomie trajektorii i utrzymuje wszystkie kluczowe parametry jawne: budżet akcji, średnicę, zajętość stanu, koszt nawigacji i błąd terminalny. Wynik jest imponujący - udało im się poprawić publikowany wcześniej współczynnik 0.015 do wartości 0.0200 w wariancie umiarkowanym i aż 0.0291 pod silniejszymi warunkami dotyczącymi akcji, średnicy i horyzontu, co stanowi wzrost o 94 procent.
Praca wprowadza także audytowalne reguły kompozycji dla algorytmów optymistycznych z ograniczeniami span oraz formalnie definiuje prawidłową konwersję wartości oczekiwanej i porównywalność stałych. Choć autorzy nie podają ostatecznych współczynników dla górnych granic, wyznaczyli asymptotyczny limit współczynnika na poziomie jeden-trzydztesta pierwiastka z (A-3)/A, gdzie A to liczba dostępnych akcji. Badanie uzupełniono kontrolowanymi testami diagnostycznymi sprawdzającymi zależność od średnicy problemu, interakcje między bonusem a szerokością oraz błędy specyfikacji parametru span.