Bandit Learning

Wyobraź sobie, że musisz wybrać najlepszy wariant reklamy, lecz za każdym razem dowiadujesz się tylko, ilu użytkowników akurat w niego kliknęło. To właśnie jest wyzwanie uczenia bandytowego – uczy się ono, balansując między eksploracją a eksploatacją, aby jak najszybciej odkryć zwycięzcę. W świecie, gdzie każda próba kosztuje – od budżetu reklamowego po czas pacjenta w eksperymentalnej terapii – bandytowe algorytmy potrafią znacznie przyspieszyć podejmowanie optymalnych decyzji. Rozwiązania bandytowe bywają jednak zaskakująco trudne do teoretycznej oceny!

Artykuł powstał na bazie publikacji naukowej: arXiv:2506.14746 PDF

🎯 Problem, który wydaje się prosty…

Załóżmy, że masz pewną funkcję nagrody $ f(x) $ która przypisuje każdemu działaniu $ x $ wartość – np. prezentacja reklamy, skuteczność terapii, konwersję na stronie.
Twoim celem nie jest poznanie całej funkcji $ f $, tylko znalezienie najlepszego działania:

$$ x^* = \arg\max_{x \in \mathcal{X}} f(x) $$

Jeśli znasz strukturę $ f $ – np. że należy do znanej klasy funkcji $ \mathcal{F} $ – wydaje się, że powinno to być łatwe.

Autorzy tej pracy pokazują, że to złudzenie.

🧠 Czym jest bandit learning?

Uczenie bandytowe to uczenie przez eksplorację:

  • możesz zapytać o $ f(x) $, ale tylko dla jednego wybranego $ x $,
  • nie masz dostępu do pełnej wiedzy o funkcji,
  • próbujesz znaleźć $ x^* $, eksplorując możliwe decyzje.

Przykłady:

  • wybór najlepszej reklamy (A/B/n),
  • personalizacja interfejsu,
  • rekomendacje produktów.

💥 Co wnosi ta publikacja?

Autorzy pokazują fundamentalnie nowe rzeczy:

❗ 1. Brak wymiarowej miary trudności

W klasyfikacji mamy np. VC-dimension — który mówi, czy klasa funkcji jest ucząca się.

W uczeniu bandytowym nie istnieje analogiczna miara – nawet dla skończonych klas funkcji!

❗ 2. Istnieją klasy funkcji, które są “łatwe”, ale niemożliwe do użycia

Autorzy budują klasę funkcji $ \mathcal{F} $, dla której:

  • Wystarczą 2 zapytania, by znaleźć optymalne $ x^* $,
  • Ale nie istnieje efektywny algorytm (polinomialny), który by to zrobił, chyba że $ RP = NP $.

Co więcej, nawet jeśli dla tej klasy ERM działa sprawnie, to bandytowe podejście i tak zawodzi.

🔍 Intuicja

Masz 100 wariantów przycisku. Chcesz znaleźć ten, który daje największy zysk.
Wiesz, że funkcja nagrody to np. $ f(x) = x_3 \land x_5 $, ale nie wiesz, które indeksy są aktywne.
Możesz sprawdzić tylko kilka opcji.

Bandytowe uczenie wymaga nie tylko wiedzy o strukturze, ale też sprytnego wyboru zapytań – a to może być obliczeniowo zbyt trudne.

🧪 Praktyczny przykład w Rust

Przykład ε-greedy A/B/n testowania:


// Parametr Epsilon: 10% szans na losowy wybór (eksplorację)
let epsilon = 0.1; 
let trials = 10_000;

...



for _ in 0..trials {
    // 1. DECYZJA: EKSPLORACJA CZY EKSPLOATACJA?
    let choose_random = random::<f64>() < epsilon;

    let idx = if choose_random {
        // 2. EKSPLORACJA: Wybierz całkowicie losowy wariant
        rand::thread_rng().gen_range(0..variants.len())
    } else {
        // 3. EKSPLOATACJA: Wybierz wariant z dotychczas najlepszym wynikiem (CTR)
        variants
            .iter()
            .enumerate()
            .max_by(|a, b| a.1.ctr().partial_cmp(&b.1.ctr()).unwrap())
            .map(|(i, _)| i)
            .unwrap()
    };

    // 4. SYMULACJA: "Pociągnij za dźwignię" wybranego wariantu
    let _ = variants[idx].simulate_click();
}

Pełny przykład znajdziesz w repozytorium: AiDaily-1

Choć prosty, ten algorytm może wpaść w pułapkę eksploracji — nigdy nie zagwarantuje znalezienia $ x^* $ w ograniczonej liczbie prób, szczególnie gdy definicja $ f $ jest ukryta w trudnych do odnalezienia wzorcach.

Co więcej, nawet gdyby po 5000 prób algorytm w końcu poprawnie ustalił, że B jest lepszy, przez kolejne 5000 prób i tak poświęci 10% z nich (czyli 500 prób) na losową eksplorację, w tym na świadome wybieranie gorszego wariantu A.

✅ Wnioski

  • Samo to, że wiemy z jakiej klasy pochodzi funkcja nagrody – nie wystarczy.
  • Nie da się opisać trudności bandytów analogicznie do klasyfikacji.
  • Potrzebujemy nowej teorii bandit learnability.

📎 Linki