Upper Confidence Bound (UCB)

"Optimisme Saat Tidak Tahu"

1. Masalah yang Sama, Pendekatan Beda

Sama seperti Thompson Sampling, UCB digunakan untuk menyelesaikan masalah Multi-Armed Bandit (memilih opsi terbaik dari beberapa pilihan misterius).

Bedanya:

  • Thompson Sampling pakai Probabilitas (Acak).
  • UCB pakai Matematika Deterministik (Pasti).
Prinsip UCB: "Optimism in the face of uncertainty". Jika kita belum banyak mencoba opsi A, kita ASUMSIKAN opsi A itu sangat bagus (Upper Bound tinggi), supaya kita terpacu mencobanya.

2. Visualisasi: Rata-Rata + Confidence

Mesin 1
Mesin 2
Mesin 3

Biru (Rata-rata Menang) + Kuning (Ketidakpastian) = UCB (Total Tinggi)

Lihat Mesin 1. Rata-rata kemenangannya rendah (Biru pendek). Tapi "Topi Kuning" nya tinggi sekali karena dia jarang dimainkan. Total tingginya (Biru+Kuning) mengalahkan Mesin 2!
Jadi algoritma akan memilih Mesin 1. Setelah dicoba, "Topi Kuning" akan memendek (kita jadi lebih yakin).

3. Rumus UCB

$$ \text{UCB}_i = \underbrace{\bar{x}_i}_{\text{Rata-rata Reward}} + \underbrace{\sqrt{\frac{1.5 \ln(N)}{n_i}}}_{\text{Confidence / Bonus}} $$
  • $\bar{x}_i$: Persentase kemenangan mesin $i$ sejauh ini.
  • $N$: Total semua putaran main (ronde ke-berapa sekarang).
  • $n_i$: Berapa kali mesin $i$ sudah dimainkan.

Perhatikan $n_i$ ada di penyebut (bawah). Semakin sering mesin dimainkan ($n_i$ besar), bonusnya makin kecil (kita makin gak penasaran). Semakin jarang dimainkan, bonusnya besar (kita penasaran).

4. Implementasi Python

import math

# setup sama seperti Thompson
conversion_rates = [0.10, 0.50, 0.15]
N = 1000
d = 3

ads_selected = []
numbers_of_selections = [0] * d
sums_of_rewards = [0] * d
total_reward = 0

for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    
    for i in range(d):
        if numbers_of_selections[i] > 0:
            # Hitung rata-rata
            average_reward = sums_of_rewards[i] / numbers_of_selections[i]
            
            # Hitung Delta (Confidence)
            delta_i = math.sqrt(1.5 * math.log(n + 1) / numbers_of_selections[i])
            
            upper_bound = average_reward + delta_i
        else:
            # Jika belum pernah dipilih, kasih nilai super tinggi (1e400) biar DIPILIH DULUAN
            upper_bound = 1e400
            
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
            
    # Mainkan
    ads_selected.append(ad)
    numbers_of_selections[ad] += 1
    
    reward = 1 if random.random() < conversion_rates[ad] else 0
    sums_of_rewards[ad] += reward
    total_reward += reward

print("Seleksi UCB:", numbers_of_selections)