Kiedy bandyta jest silniejszy niż Twój model – o ograniczeniach uczenia przez eksplorację

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^{*} = ar g max_{x \in X} f (x)$

Jeśli znasz strukturę $f$ – np. że należy do znanej klasy funkcji $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 $F$ , dla której:

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

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

Na podstawie publikacji 📄 arXiv:2506.14746 PDF