Exploration vs Exploitation

Chapter Q-Learning menutup dengan janji yang belum ditepati: dari mana angka epsilon berasal, dan kapan agent sebaiknya berhenti mencoba? Pertanyaan tersebut bukan detail teknis kecil — pertanyaan tersebut adalah dilema eksplorasi vs eksploitasi, masalah mendasar yang muncul setiap kali keputusan harus diambil dengan informasi yang baru terbentuk. Pilih selalu yang kelihatannya terbaik saat ini, dan agent terjebak pada pilihan kedua yang kebetulan dicoba lebih dulu; coba-coba terus, dan agent membayar pajak eksplorasi selamanya. Chapter ini membongkar dilema tersebut di laboratorium paling ringkas yang tersedia — bandit multi-lengan — lalu mengadu lima strategi: greedy murni, epsilon-greedy tetap, epsilon menurun, inisialisasi optimistis, dan UCB1.

Dilema dalam Bentuk Paling Murni #

Bayangkan aplikasi memiliki lima varian pesan promo dan 1.000 kesempatan menayangkannya. Setiap varian punya rata-rata nilai interaksi yang tidak diketahui; penayangan satu varian menghasilkan nilai yang berosilasi di sekitar rata-ratanya. Setiap penayangan adalah keputusan: memakai varian yang taksirannya tertinggi (eksploitasi) atau mencoba varian yang datanya masih tipis (eksplorasi) untuk tahu lebih banyak? Masalah ini — multi-armed bandit — adalah RL tanpa state: cukup satu keputusan berulang tanpa akibat berantai, sehingga dampak murni dari strategi eksplorasi terlihat tanpa derau lain. Ukuran penilaiannya kita buat eksplisit lewat regret (penyesalan): selisih antara total yang seharusnya diperoleh jika selalu memilih lengan terbaik dengan total yang benar-benar diperoleh.

Epsilon-Greedy: Tetap dan Menurun #

Strategi pertama sekaligus garis dasar: dengan peluang epsilon pilih aksi seragam acak, selebihnya pilih taksiran tertinggi. Dua rasa tersedia. Epsilon tetap (misalnya 0,1) sederhana dan tangguh: berapa pun umur percobaan, agent selalu menyisakan 10% kemungkinan mencoba — namun pajaknya juga permanen, karena 10% dari 1.000 penayangan terbuang pada varian yang sudah jelas bukan yang terbaik. Epsilon menurun (misalnya 1/t) berangkat dari eksplorasi lebat lalu melunur seiring waktu — cocok ketika kesempatan belajar terkonsentrasi di awal, tetapi berisiko berhenti mencoba terlalu dini jika keberuntungan awal menyesatkan. Keduanya akan kita ukur, bukan mendebatkan.

Inisialisasi Optimistis #

Trik kedua memanipulasi titik nol tabel. Alih-alih memulai taksiran Q pada 0, mulai pada nilai yang sengaja terlalu tinggi (misalnya +1,5). Agen serakah yang menghadapi taksiran optimistis akan tersistematisasi mencoba: sebuah lengan hanya berhenti ditarik ketika taksirannya turun menuju kenyataan, sehingga setiap lengan pasti mendapat giliran verifikasi. Eksplorasi tidak diatur oleh pelempar koin, melainkan oleh kekecewaan yang terjadwal — dan setelah semua taksiran selesai terkoreksi, perilaku otomatis menjadi eksploitasi murni. Kelemahannya: pada lingkungan yang berubah, keoptimistisan awal hanya terjadi sekali dan tidak bisa diulang tanpa mengatur ulang tabel.

UCB1: Eksplorasi yang Berhitung #

Strategi ketiga menghitung, bukan menebak. UCB1 memilih lengan dengan skor tertinggi berikut ini:

a_t = argmax_a [ Q(a) + c * sqrt( ln t / N(a) ) ],   c = sqrt(2)

Suku pertama adalah eksploitasi: taksiran rata-rata terbaik. Suku kedua adalah bonus ketidakpastian yang membesar ketika lengan jarang ditarik (N(a) kecil) dan mengecil ketika waktu berjalan (ln t tumbuh lambat). Lengan yang belum pernah dicoba mendapat prioritas penuh. Hasilnya eksplorasi yang terarah: lengan dengan taksiran tinggi namun data tipis didahulukan, bukan diundi secara seragam. Teori UCB1 memberi jaminan elegan — total regret tumbuh paling cepat secara logaritmik terhadap jumlah langkah, atau dikenal sebagai batas bawah yang dicapai strategi mana pun pada bandit stokastik. Harganya: bonus tersebut tetap menagih verifikasi berkala selamanya, seperti akan kita lihat pada keluaran program.

Softmax dan Peta Ringkas Lima Strategi #

Keluarga terakhir yang layak dikenal adalah softmax (Boltzmann): memilih aksi dengan peluang proporsional terhadap exp(Q(a)/tau). Parameter temperatur tau mengatur tingkat keacakan — tau besar membuat pilihan nyaris seragam, tau kecil membuat pilihan nyaris serakah. Softmax cocok saat selisih antar-aksi perlu diterjemahkan menjadi peluang yang halus, misalnya pada aksi berskala kontinu; kelemahannya, kualitas strategi bergantung penuh pada pemilihan tau dan biaya komputasinya lebih tinggi daripada pelempar koin epsilon-greedy. Karena kelima pesaing lain lebih mudah dianalisis, laboratorium bandit kita menguji mereka terlebih dahulu.

Laboratorium: Lima Strategi di Bandit Lima Lengan #

Skenarionya: rata-rata sejati kelima varian adalah [0,30; 0,55; 0,10; 0,80; 0,45] dengan derau Normal baku 0,25 — lengan terbaik adalah varian 3. Setiap strategi menjalani 1.000 penayangan dengan dua Generator berseed 42 (satu untuk derau ganjaran, satu untuk keputusan eksplorasi), sehingga seluruh angka dapat direproduksi persis.

# Bandit multi-lengan dengan 5 lengan sebagai laboratorium eksplorasi.
# Skenario bisnis: lima varian pesan promo, setiap penayangan (tarikan
# lengan) menghasilkan nilai interaksi yang berosilasi di sekitar
# rata-rata tak diketahui. Kita membandingkan lima strategi pemilihan:
# greedy murni, epsilon-greedy tetap, epsilon menurun 1/t, UCB1, dan
# greedy dengan inisialisasi optimistis. Setiap strategi memakai dua
# Generator berseed 42 (satu untuk derau ganjaran, satu untuk keputusan
# eksplorasi) sehingga hasil selalu dapat direproduksi.

import numpy as np

K = 5
T = 1000
MEAN_SEJATI = np.array([0.30, 0.55, 0.10, 0.80, 0.45])
DERAU = 0.25
LENGAN_TERBAIK = int(np.argmax(MEAN_SEJATI))


def jalankan_strategi(nama, pilih, q_awal=0.0):
    """Jalankan satu strategi selama T langkah.

    pilih(Q, N, t, rng) -> indeks lengan yang ditarik.
    Mengembalikan dictionary ringkasan termasuk penyesalan (regret).
    """
    rng_ganjaran = np.random.default_rng(42)
    rng_eksplorasi = np.random.default_rng(42)
    Q = np.full(K, q_awal, dtype=float)
    N = np.zeros(K, dtype=int)
    total = 0.0
    penyesalan = 0.0
    for t in range(1, T + 1):
        lengan = pilih(Q, N, t, rng_eksplorasi)
        ganjaran = rng_ganjaran.normal(MEAN_SEJATI[lengan], DERAU)
        N[lengan] += 1
        Q[lengan] += (ganjaran - Q[lengan]) / N[lengan]  # rata-rata berjalan
        total += ganjaran
        penyesalan += MEAN_SEJATI[LENGAN_TERBAIK] - MEAN_SEJATI[lengan]
    return {
        "nama": nama,
        "total": total,
        "persen_terbaik": 100.0 * N[LENGAN_TERBAIK] / T,
        "penyesalan": penyesalan,
        "N": N.copy(),
        "Q": Q.copy(),
    }


def pilih_greedy(Q, N, t, rng):
    """Serakah murni: selalu rata-rata taksiran tertinggi (ties -> terkecil)."""
    return int(np.argmax(Q))


def pilih_epsilon_tetap(Q, N, t, rng):
    """Epsilon-greedy tetap 0.1: eksplorasi seragam dengan peluang 0.1."""
    if rng.random() < 0.1:
        return int(rng.integers(K))
    return int(np.argmax(Q))


def pilih_epsilon_menurun(Q, N, t, rng):
    """Epsilon menurun 1/t: berani di awal, nyaris murni di akhir."""
    if rng.random() < 1.0 / t:
        return int(rng.integers(K))
    return int(np.argmax(Q))


def pilih_ucb1(Q, N, t, rng):
    """UCB1: pilih taksiran + bonus ketidakpastian sqrt(2 ln t / N)."""
    if (N == 0).any():
        return int(np.flatnonzero(N == 0)[0])   # lengan belum dicoba didahulukan
    bonus = np.sqrt(2.0 * np.log(t) / N)
    return int(np.argmax(Q + bonus))


hasil = [
    jalankan_strategi("greedy murni", pilih_greedy),
    jalankan_strategi("epsilon-greedy 0.1", pilih_epsilon_tetap),
    jalankan_strategi("epsilon menurun 1/t", pilih_epsilon_menurun),
    jalankan_strategi("UCB1 (c = akar 2)", pilih_ucb1),
    jalankan_strategi("optimistis (Q0 = +1.5)", pilih_greedy, q_awal=1.5),
]

print(f"Bandit {K} lengan | T = {T} langkah | derau Normal(0, {DERAU})")
print(f"Rata-rata sejati lengan : {MEAN_SEJATI}")
print(f"Lengan terbaik           : {LENGAN_TERBAIK} "
      f"(mu = {MEAN_SEJATI[LENGAN_TERBAIK]:.2f})")
print(f"Total ideal jika selalu lengan terbaik: "
      f"{T * MEAN_SEJATI[LENGAN_TERBAIK]:.1f}\n")

print(f"{'strategi':<24} {'total':>7} {'rata2':>7} {'%terbaik':>9} "
      f"{'penyesalan':>11}")
for r in hasil:
    print(f"{r['nama']:<24} {r['total']:>7.1f} {r['total'] / T:>7.3f} "
          f"{r['persen_terbaik']:>8.1f}% {r['penyesalan']:>11.1f}")

print("\nJumlah tarikan per lengan (kolom = lengan 0..4):")
for r in hasil:
    print(f"{r['nama']:<24} {r['N']}")

print("\nTaksiran rata-rata akhir Q per lengan:")
for r in hasil:
    print(f"{r['nama']:<24} [{', '.join(f'{v:.2f}' for v in r['Q'])}]")

Output yang Dihasilkan:

Bandit 5 lengan | T = 1000 langkah | derau Normal(0, 0.25)
Rata-rata sejati lengan : [0.3  0.55 0.1  0.8  0.45]
Lengan terbaik           : 3 (mu = 0.80)
Total ideal jika selalu lengan terbaik: 800.0

strategi                   total   rata2  %terbaik  penyesalan
greedy murni               292.8   0.293      0.0%       500.0
epsilon-greedy 0.1         704.0   0.704     75.3%        88.8
epsilon menurun 1/t        792.1   0.792     99.9%         0.7
UCB1 (c = akar 2)          722.4   0.722     81.7%        70.4
optimistis (Q0 = +1.5)     791.0   0.791     99.6%         1.8

Jumlah tarikan per lengan (kolom = lengan 0..4):
greedy murni             [1000    0    0    0    0]
epsilon-greedy 0.1       [ 35 120  26 753  66]
epsilon menurun 1/t      [  0   0   1 999   0]
UCB1 (c = akar 2)        [ 33  63  22 817  65]
optimistis (Q0 = +1.5)   [  1   1   1 996   1]

Taksiran rata-rata akhir Q per lengan:
greedy murni             [0.29, 0.00, 0.00, 0.00, 0.00]
epsilon-greedy 0.1       [0.32, 0.53, 0.09, 0.79, 0.46]
epsilon menurun 1/t      [0.00, 0.00, 0.34, 0.79, 0.00]
UCB1 (c = akar 2)        [0.28, 0.46, 0.10, 0.80, 0.47]
optimistis (Q0 = +1.5)   [0.38, 0.29, 0.29, 0.79, -0.04]

Mari kita bedah bagian-bagian pentingnya:

1. Baris 25–27 (dua Generator): rng_ganjaran menyuapi derau sedangkan rng_eksplorasi menentukan keputusan acak; keduanya berseed 42 dan dibuat segar per strategi, sehingga tiap baris tabel berasal dari eksperimen yang dapat direproduksi persis.
2. Baris 34–37 (pembukuan): Q[lengan] += (ganjaran - Q[lengan]) / N[lengan] memperbarui rata-rata berjalan tanpa menyimpan riwayat, dan penyesalan terakumulasi selangkah demi selangkah sebagai selisih rata-rata terbaik terhadap rata-rata lengan yang dipilih.
3. Baris 48–51 (greedy murni): np.argmax memecah hasil seri dengan mengembalikan indeks terkecil — detail kecil yang menjelaskan mengapa lengan 0 yang dikunci, karena lengan tersebut kebetulan dicoba lebih dulu.
4. Baris 67–72 (UCB1): lengan yang belum pernah ditarik didahulukan lewat np.flatnonzero(N == 0)[0]; setelahnya skor Q + bonus menggabungkan eksploitasi dan bonus ketidakpastian persis seperti rumus.
5. Baris 75–81 (lima strategi): inisialisasi optimistis tidak memerlukan fungsi pemilih baru — fungsi pilih_greedy yang sama dipakai ulang dengan q_awal=1.5, memperlihatkan bahwa trik tersebut murni soal titik nol tabel.

Keluaran program meneguhkan tiap klaim teori dengan angka. Greedy murni menarik lengan 0 sebanyak 1.000 kali tanpa pernah menyentuh lengan lain — total 292,8 dan regret 500,0, harga yang dibayar karena satu keputusan awal tidak pernah diverifikasi. Epsilon tetap 0,1 mendapat 704,0 dengan regret 88,8: lebih baik jauh, tetapi sekitar 100 tarikan tetap terbuang seragam pada semua lengan (lihat baris tarikannya: 35, 120, 26, 753, 66). Epsilon menurun 1/t dan inisialisasi optimistis nyaris sempurna di sini — masing-masing regret 0,7 dan 1,8 — dan baris tarikan optimistis [1, 1, 1, 996, 1] memperlihatkan pola verifikasi satu kali per lengan yang khas dari trik tersebut. UCB1 merebut 722,4 dengan regret 70,4: terarah dan berhitung, tetapi bonus sqrt(ln t / N) terus menagih verifikasi berkala sepanjang 1.000 langkah — bayangan yang pantas dibayar ketika kepastian identifikasi lebih penting daripada total sesaat.

Semua strategi di atas menghasilkan satu bilangan kebijakan statis: taksiran per lengan. Agent gridworld pada Chapter berikutnya menghadapi versi yang jauh lebih kaya dari dilema yang sama — keputusan eksplorasi di satu state memengaruhi state mana yang akan dikunjungi selanjutnya — dan menyatukan seluruh perangkat Section ini menjadi satu program utuh pada Chapter Membangun Agent Q-Learning untuk Gridworld.

Referensi Resmi #

• numpy — Random sampling (numpy.random) — dokumentasi resmi Generator default_rng untuk derau ganjaran dan keputusan eksplorasi yang reproducible.
• numpy — numpy.argmax — API resmi pemilihan taksiran tertinggi pada semua varian strategi.
• Gymnasium — situs resmi pustaka lingkungan RL; menyediakan lingkungan bandit standar untuk memperluas eksperimen di luar implementasi NumPy murni Course ini.