Naukowcy wprowadzili nowy problem uczenia się online nazwany Stochastic Reset Pathfinding (SRP), w którym agent musi wybrać ścieżkę ze źródła do celu na znanym grafie skierowanym. Problem polega na tym, że każda krawędź ma nieznaną, stałą w czasie probabilistę sukcesu - jeśli jakakolwiek krawędź zawiedzie, agent wraca do źródła i musi zacząć od nowa. Ta struktura "globalnego resetowania" sprawia, że optymalną strategią jest zawsze ścieżka otwarta pętla, co umieszcza problem w ramach kombinatorycznych bandytów kaskadowych.
Do rozwiązania tego wyzwania zaproponowano meta-algorytm Log-Dijkstra z dwoma wariantami: PathUCB oparty na indeksowaniu górnych granic ufności i PathTS wykorzystujący Thompson Sampling. Kluczowym teoretycznym wkładem jest nowa miara żalu na poziomie ścieżek, która rozkłada koszt eksploracji ścieżek subpotimalnych za pomocą złożoności ścieżki łączącej niezawodność prefiksu i suffiksu każdej krawędzi. To podejście jest bardziej informacyjne niż tradycyjne analizy na poziomie krawędzi, szczególnie dla grafów z wielomianową liczbą możliwych ścieżek.
Algorytm został przetestowany na scenariuszach kwantowych sieci powtarzaczy, warstwowych DAG-ów, świata siatki oraz sieciach Erdosa-Renyiego. PathTS wykazał najlepszą wydajność empiryczną, choć badacze zidentyfikowali też patologiczne przypadki, w których Thompson Sampling zawodzi - konsekwencja znanej eksponencjalnej trudności dla kombinatorycznego Thompson Samplingu w problemach z nagrodami multiplikatywnymi.