Naukowcy z arXiv przedstawili algorytm THV-UCB rozwiązujący problem banditów wielocelu - gdzie agent iteracyjnie wybiera zestawy k ramion obserwując wielowymiarowe wektory nagród (d wymiarów). Zamiast szukać jednego optymalnego działania, celem jest utrzymywanie małego zbioru opcji przybliżających front Pareto, czyli granicę rozwiązań niezdominowanych przez inne.
Problemu formalizuje hipervolumen - metryka opisująca obszar zdominowany przez wybrany podzbiór w przestrzeni celów. Autorzy definiują alfa-przybliżone regret hipervolumenu gdzie alfa wynosi 1-1/e, co odpowiada gwarancji greedy maksymalizacji dla funkcji monotonicznie submodularnych. Algorytm THV-UCB wybiera ramiona greedy na podstawie optymistycznych oszacowań marginalnych wkładów w hipervolumen - klasyczne podejście z upper confidence bounds.
Teoretyczne wyniki to gap-free bound O(d√nkT) gwarantowany na każdej instancji oraz gap-dependent bound O(nk²,⁵/Delta_min) stający się polilogarytmiczny w T gdy ramiona są dostatecznie rozdzielone. Praca dostarcza teoretycznego wsparcia dla praktyki stosowania małych podzbiorów do przybliżania frontów Pareto w systemach rekomendacyjnych, optymalizacji portfela czy innych aplikacjach z conflictingowymi celami.