Zespół badaczy zaproponował nowy algorytm probe-and-commit, który radzi sobie z problemem improving multi-armed bandits bez znajomości skali maksymalnej nagrody ani długości horyzontu czasowego. Algorytm osiąga współczynnik konkurencyjności 4√3·√k dla k ramion, gdzie każde ramię ma nieznaną, niemalejącą funkcję nagrody, co stanowi znaczące ulepszenie względem poprzednich wyników wymagających dodatkowymi log k w mianowniku.
Badanie rozróżnia dwa scenariusze: w idealnym świecie bez szumu,RandomMarginalProbing osiąga optymalny współczynnik Θ(k^(β/(1+β))+k/T) bez znajomości żadnych parametrów - ani skali m, ani współczynnika wklęsłości β, ani horyzontu T. To pokazuje, że przy odpowiedniej konstrukcji algorytmu wiele naturalnych parametrów problemów można całkowicie zignorować.
Jednak sytuacja radykalnie się zmienia w obecności szumu mnożnikowego. Choć probe-and-commit utrzymuje ten sam optymalny porządek Θ(√k+k/T) dla wszystkich horyzontów bez znajomości poziomu szumu, koszty znajomości innych parametrów dramatycznie rosną. Dla każdego ustalonego poziomu szumu ε między 0 a 0.5 algorytm uniform spacing wymaga właściwej kalibracji, co wskazuje na fundamentalną asymetrię między światami noszumowym a szumowym.