Zespół badaczy rozwiązuje zagadnienie uczenia się w bandytach Markowa z niedostępnymi stanami wewnętrznymi i potencjalnie ograniczonymi momentami decyzji. Problem polega na minimalizacji żalu w stosunku do tzw. czystych polityk - strategii, które od początku wybierają jeden optymalny wariant bez przełączania, podobnie jak w klasycznych bandytach stochastycznych.
Głównym wkładem pracy jest wprowadzenie klasy bandytów Markowa zwanych self-degrading, dla których takie czyste polityki zawsze pozostają asymptotycznie optymalne. Naukowcy wykazali, że bez wiedzy o parametrach systemu każdy algorytm, który rzadko przełącza warianty, musi generować żal skalujący się ponad-logarytmicznie (omega(log T)). Oznacza to fundamentalne ograniczenie teoretyczne dla takiego problemu.
Pomimo tego ograniczenia zespół zaprojektował algorytm UCB-NOM inspirowany algorytmem UCB, który osiąga niemal logarytmiczny żal. Co ważne, gdy dysponuje się wiedzą o górnym ograniczeniu funkcji bias systemu, UCB-NOM uzyskuje optimalny regret O(log T). Kluczowym wynikiem jest także to, że wszystkie uzyskane granice żalu nie zależą od liczby stanów łańcuchów Markowa - co stanowi istotne ulepszenie, gdyż w praktyce liczba stanów może być bardzo duża lub nawet nieskończona.