Wprowadzenie
Upper Confidence Bound (UCB) to algorytm należący do rodziny strategii Optimism in the Face of Uncertainty. Jest używany głównie w problemie Multi-Armed Bandit, ale ma szerokie zastosowanie w Reinforcement Learning, rekomendacjach, A/B testingach i optymalizacji online.
Jak działa UCB?
Algorytm wybiera akcję (ramię bandyty), która maksymalizuje sumę dwóch składników:
UCB(a) = Q̂(a) + c × √(ln(t) / N(a))
Gdzie:
- Q̂(a) – estymowana wartość (średnia nagroda) akcji a
- N(a) – liczba razy, kiedy akcja a została wybrana
- t – całkowita liczba kroków (czas)
- c – parametr eksploracji (zwykle √2)
Główne warianty
- UCB1 – najpopularniejsza i najczęściej implementowana wersja
- UCB2
- UCB-Tuned
- Bayesian UCB
- Discounted UCB i Restless UCB (dla niestacjonarnych środowisk)
Zalety algorytmu UCB
- Optymalna równowaga między eksploracją a eksploatacją
- Teoretycznie gwarantowana granica regret (sub-linear regret)
- Prosty w implementacji
- Bardzo dobre wyniki empiryczne
- Nie wymaga znajomości rozkładu nagród
Zastosowania
- Rekomendacje (np. wybór reklam)
- A/B testing i optymalizacja online
- Clinical trials (testy medyczne)
- Reinforcement Learning (np. w Monte Carlo Tree Search)
- Hyperparameter optimization
- Resource allocation
UCB vs ε-greedy
UCB jest zazwyczaj znacznie bardziej efektywny niż ε-greedy, ponieważ eksploruje w sposób inteligentny – wybiera akcje, które mają największy potencjał być lepsze (wysoka niepewność), zamiast losować całkowicie na ślepo.
Powiązane pojęcia
Multi-Armed Bandit • Exploration vs Exploitation • Regret • Thompson Sampling • ε-greedy • Monte Carlo Tree Search (MCTS) • Optimism in the Face of Uncertainty