Thompson Sampling

"Multi-Armed Bandit: Pilih Judi yang Mana?"

1. Masalah Multi-Armed Bandit

Bayangkan Anda di kasino menghadap 3 mesin slot. Setiap mesin punya peluang menang berbeda yang TIDAK ANDA KETAHUI.
Goal: Memaksimalkan uang kemenangan dalam waktu terbatas.

  • Exploration: Coba mesin baru (siapa tau dia gacor).
  • Exploitation: Main terus di mesin yang sejauh ini memberi hasil bagus.

Thompson Sampling adalah cara cerdas menyeimbangkan ini menggunakan Probabilitas (Distribusi Beta).

2. Visualisasi: "Keyakinan" Kita

A

Menang: 5
Kalah: 2

Lebar & Tinggi

B

Menang: 50
Kalah: 40

Sempit (Yakin)

Setiap mesin direpresentasikan oleh Kurva Distribusi.

  • Mesin A (Baru main dikit): Kurvanya lebar. Kita "tidak yakin" rata-ratanya dimana. Bisa jadi sangat jelek, bisa jadi sangat bagus.
  • Mesin B (Udah sering main): Kurvanya sempit. Kita "yakin" rata-ratanya ada di sekitar 55%.
Cara Main: Kita ambil satu sampel acak dari kurva A dan kurva B. Siapa yang angkanya paling tinggi, dia yang kita mainkan! Mesin A yang lebar punya peluang sesekali menghasilkan angka sampel yang sangat tinggi (Exploration).

3. Algoritma

Rumus Distribusi Beta: $\text{Beta}(\alpha, \beta)$

  • $\alpha$: Jumlah Sukses (Menang) + 1
  • $\beta$: Jumlah Gagal (Kalah) + 1
  1. Untuk setiap mesin $i$, ambil sampel acak $\theta_i$ dari distribusi $\text{Beta}(\alpha_i, \beta_i)$.
  2. Pilih mesin dengan $\theta$ terbesar.
  3. Mainkan mesin itu, lihat hasilnya (Menang/Kalah).
  4. Update $\alpha$ atau $\beta$ mesin tersebut.

4. Implementasi Python

import random
import matplotlib.pyplot as plt

# Setup: 3 Iklan (Mesin Slot), dengan konversi rate JAWABAN (User tdk tau ini)
conversion_rates = [0.10, 0.50, 0.15] # Iklan ke-2 jelas paling bagus
N = 1000 # Jumlah user
d = len(conversion_rates) # Jumlah Iklan

# Inisialisasi
ads_selected = []
numbers_of_rewards_1 = [0] * d # Alpha (Menang)
numbers_of_rewards_0 = [0] * d # Beta (Kalah)
total_reward = 0

for n in range(N):
    ad = 0
    max_random = 0
    
    # --- THOMPSON SAMPLING STEP ---
    for i in range(d):
        # Ambil sampel acak dari distribusi Beta saat ini
        random_beta = random.betavariate(numbers_of_rewards_1[i] + 1, 
                                         numbers_of_rewards_0[i] + 1)
        
        if random_beta > max_random:
            max_random = random_beta
            ad = i
            
    # Mainkan Iklan terpilih (Simulasi Dunia Nyata)
    ads_selected.append(ad)
    reward = 1 if random.random() < conversion_rates[ad] else 0
    
    # Update Pengetahuan Kita
    if reward == 1:
        numbers_of_rewards_1[ad] += 1
    else:
        numbers_of_rewards_0[ad] += 1
    
    total_reward += reward

print("Jumlah Iklan Dipilih:", numbers_of_rewards_1) 
# Iklan ke-2 pasti yang paling sering dipilih (otomatis konvergen)