Eksplorasi yang lebih cerdas

Epsilon-greedy dengan epsilon tetap membuang sebagian reward untuk eksplorasi yang tidak lagi diperlukan setelah estimasi memadai. Tiga penyempurnaan lazim mengatasi hal ini: peluruhan epsilon yang menurunkan laju eksplorasi seiring waktu, inisialisasi optimistis yang mendorong eksplorasi awal melalui estimasi awal yang sengaja ditetapkan tinggi, serta UCB1 yang memilih aksi berdasarkan kombinasi estimasi dan ketidakpastian. Topik ini memperkenalkan ketiganya dan membandingkan epsilon-greedy dengan peluruhan terhadap UCB1 pada bandit 10-lengan.

Peluruhan epsilon#

Alih-alih mempertahankan $\varepsilon$ konstan, peluruhan epsilon menurunkannya seiring langkah $t$ sehingga eksplorasi intensif di awal dan eksploitasi dominan di akhir. Bentuk peluruhan yang lazim adalah peluruhan kebalikan:

dengan $\varepsilon_0$ adalah nilai awal dan $\beta$ mengatur kecepatan peluruhan. Pada $t=0$, $\varepsilon_t=\varepsilon_0$, lalu menurun menuju nol seiring $t$ membesar. Dengan demikian, eksplorasi yang dilakukan di awal, ketika estimasi masih kasar, lebih banyak daripada di akhir, ketika estimasi sudah konvergen.

Peluruhan epsilon memperbaiki epsilon-greedy konstan tetapi tetap memilih aksi eksplorasi secara seragam acak, tanpa memperhitungkan lengan mana yang paling perlu dijelajahi. Akibatnya, sebagian langkah eksplorasi terbuang pada lengan yang estimasinya sudah akurat, sementara lengan yang jarang ditarik tetap kurang dieksplorasi. Kelemahan inilah yang melatarbelakangi pendekatan berbasis ketidakpastian seperti UCB.

Inisialisasi optimistis#

Inisialisasi optimistis menetapkan nilai awal $Q_0(a)$ yang sengaja tinggi, misalnya $+5$, untuk semua lengan pada awalnya. Karena pembaruan rata-rata sampel bersifat menarik nilai ke arah reward observasi, lengan yang ditarik akan melihat estimasinya turun, sedangkan lengan yang belum ditarik tetap pada nilai optimistisnya. Algoritma greedy murni pun kemudian akan menarik setiap lengan sekurang-kurangnya beberapa kali sebelum estimasinya turun di bawah lengan lain, sehingga eksplorasi terjadi tanpa komponen acak eksplisit.

Pendekatan ini elegan karena eksplorasi muncul dari struktur pembaruan itu sendiri, bukan dari probabilitas terpisah. Namun, inisialisasi optimistis sangat bergantung pada skala reward: nilai awal yang terlalu tinggi memperlambat konvergensi karena butuh banyak tarikan untuk menurunkan estimasi, sedangkan nilai yang tidak cukup tinggi gagal mendorong eksplorasi menyeluruh. Pada masalah non-stasioner, di mana nilai sebenarnya lengan berubah seiring waktu, inisialisasi optimistis juga kehilangan keunggulannya karena estimasi awal yang tinggi tidak lagi relevan setelah dinamika berubah.

UCB1#

UCB1, atau Upper Confidence Bound, memilih aksi yang memaksimalkan jumlah antara estimasi reward dan sebuah bonus ketidakpastian:

dengan $N(a)$ adalah jumlah tarikan lengan $a$ sejauh $t$ dan $c$ adalah konstanta yang mengatur bobot ketidakpastian. Bonus besar ketika $N(a)$ kecil, yaitu lengan yang jarang ditarik, sehingga algoritma didorong untuk mengeksplorasi lengan yang paling belum dipahami. Sebaliknya, ketika $N(a)$ besar, bonus mengecil dan pilihan didominasi oleh estimasi $Q(a)$.

Berbeda dengan epsilon-greedy yang mengeksplorasi secara seragam acak, UCB mengeksplorasi secara terarah, yaitu ke arah lengan dengan ketidakpastian tertinggi. Hal ini umumnya menghasilkan regret sublinear yang lebih baik secara teoretis pada bandit stasioner. Namun, UCB tidak selalu lebih baik dalam praktik: pada masalah non-stasioner atau reward yang sangat berderau, bonus ketidakpastian dapat menyesatkan, dan konstanta $c$ harus disetel ulang. Karena itu, perbandingan antarmetode sebaiknya didasarkan pada eksperimen, bukan klaim mutlak.

Membandingkan peluruhan epsilon dan UCB1#

Blok berikut menjalankan dua strategi pada bandit 10-lengan yang sama selama 1000 langkah: epsilon-greedy dengan peluruhan kebalikan dan UCB1 dengan $c=2$. UCB1 menginisialisasi dengan menarik tiap lengan sekali sebelum perulangan utama, agar $N(a) \geq 1$ dan bonus terdefinisi.

import warnings; warnings.filterwarnings("ignore")
import numpy as np

np.random.seed(0)

k = 10
steps = 1000
q_true = np.random.normal(0, 1, k)
optimal = int(np.argmax(q_true))

def epsilon_greedy_decay(eps0=0.3, decay=0.005):
    Q = np.zeros(k)
    N = np.zeros(k, dtype=int)
    total = 0.0
    for t in range(steps):
        eps = eps0 / (1.0 + decay * t)
        if np.random.rand() < eps:
            a = int(np.random.randint(k))
        else:
            a = int(np.argmax(Q))
        r = q_true[a] + np.random.normal(0, 1)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
        total += r
    return total / steps

def ucb1(c=2.0):
    Q = np.zeros(k)
    N = np.zeros(k, dtype=int)
    total = 0.0
    for a in range(k):
        r = q_true[a] + np.random.normal(0, 1)
        N[a] = 1
        Q[a] = r
        total += r
    for t in range(k, steps):
        ucb = Q + c * np.sqrt(np.log(t + 1) / N)
        a = int(np.argmax(ucb))
        r = q_true[a] + np.random.normal(0, 1)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
        total += r
    return total / steps

avg_decay = epsilon_greedy_decay()
avg_ucb = ucb1()
print(f"epsilon-greedy decay : avg_reward={avg_decay:.4f}")
print(f"ucb1                 : avg_reward={avg_ucb:.4f}")

epsilon-greedy decay : avg_reward=2.0399
ucb1                 : avg_reward=2.0953

Membaca keluaran#

Pada seed ini, UCB1 mencapai reward rata-rata 2.0953, sedikit lebih tinggi daripada epsilon-greedy dengan peluruhan yang memperoleh 2.0399. Selisih tipis ini bukan bukti bahwa UCB selalu lebih baik, melainkan hasil satu run pada satu konfigurasi bandit. Pada seed atau parameter berbeda, urutan dapat terbalik, terutama bila reward berderau tinggi sehingga bonus ketidakpastian UCB kadang memilih lengan yang sebenarnya buruk.

Perbedaan yang lebih konsisten antara kedua strategi terlihat pada pola eksplorasi. UCB1 menghabiskan tarikan awal untuk memeratakan informasi antarlengan, sedangkan peluruhan epsilon masih menyisakan eksplorasi acak yang menyentuh lengan sama berkali-kali tanpa tambahan informasi. Untuk eksperimen yang serius, perbandingan harus diulang pada banyak seed dan dirata-ratakan, agar kesimpulan tidak didasarkan pada satu realisasi derau. Catatan ini berlaku umum untuk seluruh modul bandit ini.

Kesalahan umum#

• Menjalankan satu seed lalu menyimpulkan UCB selalu lebih baik. Penyebabnya, selisih tipis antarmetode pada satu run mudah berubah pada seed lain. Perbaikannya, mengulang pada banyak seed dan merata-ratakan reward, karena kesimpulan dari satu realisasi derau tidak dapat dipercaya.
• Menggunakan inisialisasi optimistis pada masalah non-stasioner. Penyebabnya, nilai awal yang tinggi hanya bermanfaat sekali, lalu estimasi terkunci pada rata-rata riwayat yang sudah tidak relevan. Perbaikannya, memakai langkah konstan $\alpha$ dan inisialisasi nol, atau beralih ke metode yang secara eksplisit melacak ketidakpastian.
• Lupa menarik tiap lengan sekali pada UCB1 sebelum perulangan utama. Penyebabnya, bonus $\sqrt{\ln t / N(a)}$ tidak terdefinisi ketika $N(a)=0$. Perbaikannya, menginisialisasi $N(a) \geq 1$ untuk semua lengan, seperti yang dilakukan blok di atas.

Ringkasan#

• Peluruhan epsilon menurunkan $\varepsilon_t=\varepsilon_0/(1+\beta t)$ sehingga eksplorasi intensif di awal dan eksploitasi dominan di akhir.
• Inisialisasi optimistis mendorong eksplorasi melalui nilai $Q_0$ yang sengaja tinggi, tanpa komponen acak eksplisit.
• UCB1 memilih $A_t=\arg\max_a[Q(a)+c\sqrt{\ln t/N(a)}]$, mengeksplorasi lengan dengan ketidakpastian tertinggi, dan tidak selalu lebih baik daripada epsilon-greedy dalam praktik.

Referensi#

• Reinforcement Learning: An Introduction (2nd ed.) — Sutton & Barto — Bab 2 membahas inisialisasi optimistis, UCB, dan peluruhan epsilon sebagai penyempurnaan epsilon-greedy.