Epsilon-greedy

Epsilon-greedy adalah strategi dasar yang menyeimbangkan eksplorasi dan eksploitasi dengan aturan sederhana: pada setiap langkah, dengan probabilitas $\varepsilon$ pilih aksi secara acak, dan dengan probabilitas $1-\varepsilon$ pilih aksi dengan estimasi tertinggi. Nilai $\varepsilon$ mengatur seberapa banyak eksplorasi dilakukan, sedangkan estimasi action-value diperbarui melalui rata-rata sampel. Topik ini mengimplementasikan epsilon-greedy pada bandit 10-lengan selama 1000 langkah dan mengukur dua hal, yaitu reward rata-rata dan persentase pemilihan aksi optimal.

Mekanisme epsilon-greedy#

Pada setiap langkah $t$, agen menarik sebuah bilangan acak seragam $u \in [0,1)$. Apabila $u < \varepsilon$, agen memilih aksi secara seragam acak dari k lengan, yang merupakan eksplorasi. Apabila $u \geq \varepsilon$, agen memilih $a_t = \arg\max_a Q_t(a)$, yang merupakan eksploitasi. Nilai $\varepsilon$ yang besar mendorong lebih banyak eksplorasi tetapi mengurangi pemanfaatan lengan terbaik yang sudah diketahui, sedangkan $\varepsilon$ yang kecil cenderung membuat agen cepat terjebak pada lengan suboptimal.

Estimasi $Q(a)$ diperbarui dengan rata-rata sampel, yang pada setiap observasi reward $R_n$ melakukan koreksi inkremental:

dengan $n$ adalah jumlah tarikan lengan itu sejauh ini. Bentuk ini setara dengan rata-rata aritmetika, tetapi tidak perlu menyimpan seluruh riwayat reward, sehingga hemat memori. Karena setiap lengan diperbarui secara terpisah, pembaruan pada satu lengan tidak mempengaruhi estimasi lengan lain.

Bentuk pembaruan di atas dapat diturunkan dari definisi rata-rata sampel. Misalkan $Q_n$ adalah rata-rata $n$ reward pertama. Rata-rata $n+1$ reward adalah $\frac{1}{n+1}\sum_{i=1}^{n+1} R_i = \frac{1}{n+1}\big(n Q_n + R_{n+1}\big) = Q_n + \frac{1}{n+1}(R_{n+1} - Q_n)$. Dengan menamai ulang indeks, diperoleh bentuk pembaruan pada blok di bawah. Turunan ini menunjukkan bahwa pembaruan inkremental dan rata-rata sampel penuh adalah objek yang sama, hanya berbeda dalam penggunaan memori.

Pada bandit dengan $k$ lengan, eksplorasi acak memilih tiap lengan dengan probabilitas $1/k$. Dalam $T$ langkah, rata-rata jumlah tarikan per lengan akibat eksplorasi saja adalah $\varepsilon T / k$. Untuk $k=10$, $\varepsilon=0.1$, dan $T=1000$, angka ini menjadi 10, yang cukup untuk membangun estimasi kasar tiap lengan tanpa menguras terlalu banyak langkah dari eksploitasi. Perhitungan kasar ini menjelaskan mengapa $\varepsilon=0.1$ menjadi kompromi lazim pada bandit 10-lengan.

Implementasi epsilon-greedy#

Blok berikut adalah berkas epsilon_greedy.py yang utuh dan dapat dijalankan. Berkas ini membangun bandit 10-lengan, menjalankan epsilon-greedy dengan $\varepsilon=0.1$ selama 1000 langkah, lalu mencetak reward rata-rata dan persentase pemilihan aksi optimal.

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

np.random.seed(0)

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

Q = np.zeros(k)
N = np.zeros(k, dtype=int)
total_reward = 0.0
optimal_count = 0

for t in range(steps):
    if np.random.rand() < epsilon:
        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_reward += r
    if a == optimal:
        optimal_count += 1

print(f"avg_reward       = {total_reward / steps:.4f}")
print(f"optimal_action % = {100 * optimal_count / steps:.2f}")

avg_reward       = 1.9161
optimal_action % = 54.10

Membaca keluaran#

Dengan $\varepsilon=0.1$, reward rata-rata mencapai 1.9161 dan aksi optimal terpilih pada 54.10% langkah. Angka ini jauh lebih baik daripada greedy murni karena eksplorasi sesekali memaksa agen mencoba lengan selain yang saat ini tampak terbaik, sehingga estimasi $Q$ untuk lengan optimal akhirnya naik melebihi lengan yang dulu tampak unggul. Persentase 54.10% bukan angka tinggi karena sepuluh persen langkah secara eksplisit dihabiskan untuk eksplorasi acak, yang hampir selalu tidak memilih lengan optimal.

Pemilihan $\varepsilon=0.1$ merupakan kompromi lazim: cukup kecil agar eksploitasi dominan, tetapi cukup besar agar setiap lengan ditarik berkali-kali dalam 1000 langkah. Nilai yang lebih kecil, misalnya 0.01, mempercepat eksploitasi tetapi memperlambat penemuan lengan optimal, sedangkan nilai yang lebih besar seperti 0.3 memperbanyak eksplorasi dengan biaya reward sesaat. Tidak ada $\varepsilon$ tunggal yang optimal untuk semua masalah, sehingga pemilihannya sering menjadi bagian dari penalaan eksperimen.

Perbandingan dengan greedy murni menggarisbawahi loncatan kualitas. Greedy murni memperoleh reward rata-rata 1.7119 karena terjebak pada lengan suboptimal, sedangkan epsilon-greedy dengan $\varepsilon=0.1$ mencapai 1.9161, naik sekitar 12 persen. Kenaikan ini datang dari eksplorasi yang sesekali menemukan lengan optimal indeks 3 dan mengangkat estimasinya di atas lengan yang dulu tampak unggul. Persentase pemilihan aksi optimal 54.10% mencerminkan keseimbangan: mayoritas langkah memilih lengan optimal setelah estimasi konvergen, tetapi sekitar 46 persen langkah lain terbagi antara eksplorasi acak dan eksploitasi lengan suboptimal yang estimasinya belum turun.

Kesalahan umum#

• Memilih epsilon tanpa mempertimbangkan skala reward. Penyebabnya, nilai epsilon yang sama memberi efek berbeda pada bandit dengan reward berskala kecil dan besar. Perbaikannya, mencoba beberapa nilai epsilon pada bandit yang sama dan memilih berdasarkan reward rata-rata yang diobservasi, bukan meniru nilai dari contoh.
• Memakai rata-rata sampel pada masalah non-stasioner. Penyebabnya, bobot $1/n$ memberi bobot sama pada seluruh riwayat sehingga perubahan terbaru lengan lambat tercermin. Perbaikannya, mengganti $1/n$ dengan langkah konstan $\alpha$, misalnya 0.1, agar pembaruan memberi bobot lebih pada reward terbaru.
• Lupa memperbarui N(a) sebelum Q(a). Penyebabnya, urutan pembaruan yang terbalik membuat pembagi rata-rata salah. Perbaikannya, menambah N[a] lebih dulu, baru memperbarui Q[a] dengan N[a] yang baru.

Ringkasan#

• Epsilon-greedy menyeimbangkan eksplorasi (probabilitas $\varepsilon$) dan eksploitasi (probabilitas $1-\varepsilon$) dengan aturan sederhana.
• Estimasi $Q$ diperbarui inkremental melalui $Q_{n+1}=Q_n+\frac{1}{n}(R_n-Q_n)$, setara dengan rata-rata sampel tanpa menyimpan riwayat.
• Pada bandit 10-lengan, $\varepsilon=0.1$ menghasilkan reward rata-rata 1.9161 dan aksi optimal terpilih pada 54.10% langkah.

Referensi#

• Reinforcement Learning: An Introduction (2nd ed.) — Sutton & Barto — Bab 2 memperkenalkan epsilon-greedy dan pembaruan rata-rata sampel sebagai strategi dasar.