Eksplorasi vs eksploitasi

Dilema yang mendefinisikan seluruh bidang reinforcement learning.

Daftar isi

Dilema eksplorasi versus eksploitasi adalah tegangan antara memanfaatkan lengan yang tampak terbaik saat ini dan mencoba lengan yang belum dikenal untuk memperbaiki perkiraan. Eksploitasi memaksimalkan reward sesaat, sedangkan eksplorasi mengumpulkan informasi yang membuat perkiraan ke depan menjadi lebih akurat. Topik ini mendefinisikan kedua kutub tersebut secara formal melalui regret kumulatif, lalu membandingkan dua kebijakan ekstrem, yaitu greedy murni dan acak murni, pada sebuah bandit 10-lengan selama 1000 langkah.

Definisi eksplorasi dan eksploitasi#

Pada setiap langkah, agen memilih satu aksi. Eksploitasi berarti memilih aksi dengan estimasi $Q(a)$ tertinggi saat ini, yang memaksimalkan reward yang diharapkan pada langkah itu berdasarkan pengetahuan yang sudah dimiliki. Eksplorasi berarti memilih aksi lain dengan sengaja, bukan karena perkiraannya paling tinggi, melainkan untuk mengumpulkan observasi baru yang dapat mengoreksi perkiraan apabila ternyata aksi itu lebih baik daripada yang diperkirakan.

Pilihan antara keduanya tidak dapat dihindari karena keduanya saling membatasi. Setiap langkah yang dipakai untuk eksploitasi menghasilkan reward yang relatif dapat diprediksi, tetapi tidak memberi informasi baru tentang lengan lain. Sebaliknya, setiap langkah eksplorasi mungkin menghasilkan reward yang lebih rendah sesaat, tetapi membuka kemungkinan menemukan lengan yang nilainya lebih tinggi. Tegangan inilah yang sering disebut sebagai dilema yang mendefinisikan seluruh bidang reinforcement learning.

Dua kutub ini sebenarnya tidak berdiri sendiri, melainkan dua sisi dari tujuan yang sama, yaitu memaksimalkan reward kumulatif sepanjang $T$ langkah. Eksploitasi memaksimalkan reward pada langkah berjalan, sedangkan eksplorasi menginvestasikan langkah berjalan demi reward masa depan yang lebih tinggi. Karena agen tidak mengetahui $q_*(a)$ sejak awal, kebijakan yang baik harus mengalokasikan sebagian langkah untuk eksplorasi tanpa mengorbankan terlalu banyak reward, dan titik keseimbangan inilah yang dicari oleh setiap algoritma bandit.

Regret kumulatif sebagai ukuran#

Untuk mengukur seberapa baik sebuah kebijakan, dipakai regret kumulatif yang menjumlahkan selisih antara nilai sebenarnya lengan optimal dan nilai sebenarnya lengan yang dipilih pada setiap langkah:

L_T = \sum_{t=1}^{T} \big( q_*(a^*) - q_*(a_t) \big)

dengan $a^* = \arg\max_a q_*(a)$ adalah aksi optimal dan $a_t$ adalah aksi yang dipilih pada langkah $t$ . Regret memakai nilai sebenarnya, bukan reward yang terderau, sehingga mengukur kerugian akibat keputusan, bukan akibat kebetulan derau. Kebijakan yang baik menjaga regret tumbuh secara sublinear terhadap $T$ , artinya rata-rata kerugian per langkah menuju nol seiring waktu.

Perbedaan antara reward rata-rata dan regret terletak pada apa yang diukur. Reward memperhitungkan derau stokastik pada setiap tarikan, sedangkan regret murni mengukur jarak keputusan dari optimal. Pada eksperimen berikut, kedua besaran dilaporkan bersama agar sifat masing-masing kebijakan terlihat jelas.

Membandingkan greedy murni dan acak murni#

Blok berikut menjalankan dua kebijakan ekstrem pada bandit 10-lengan yang sama selama 1000 langkah. Kebijakan greedy murni selalu memilih aksi dengan estimasi tertinggi saat itu, sedangkan kebijakan acak murni memilih aksi secara seragam tanpa memperhatikan estimasi.

python

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 run(policy):
    Q = np.zeros(k)
    N = np.zeros(k, dtype=int)
    total_reward = 0.0
    total_regret = 0.0
    for t in range(steps):
        if policy == "greedy":
            a = int(np.argmax(Q))
        else:
            a = int(np.random.randint(k))
        r = q_true[a] + np.random.normal(0, 1)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
        total_reward += r
        total_regret += (q_true[optimal] - q_true[a])
    return total_reward / steps, total_regret

avg_g, reg_g = run("greedy")
avg_r, reg_r = run("random")
print(f"greedy : avg_reward={avg_g:.4f}  regret={reg_g:.4f}")
print(f"random : avg_reward={avg_r:.4f}  regret={reg_r:.4f}")

text Keluaran

greedy : avg_reward=1.7119  regret=476.8409
random : avg_reward=0.8061  regret=1466.2756

Membaca keluaran#

Kebijakan greedy murni memperoleh reward rata-rata 1.7119, jauh lebih tinggi daripada kebijakan acak murni yang hanya 0.8061. Namun greedy murni memiliki kelemahan struktural: pada langkah pertama seluruh estimasi $Q$ bernilai nol, sehingga argmax memilih indeks pertama, lalu agen cenderung terjebak pada lengan itu apabila reward pertamanya positif. Akibatnya, banyak lengan yang tidak pernah dieksplorasi, dan regret kumulatifnya tetap besar, yaitu 476.8409.

Sebaliknya, kebijakan acak murni menarik setiap lengan kira-kira 100 kali, sehingga estimasinya merata, tetapi karena tidak memanfaatkan informasi itu sama sekali, regretnya meledak menjadi 1466.2756, sekitar tiga kali lipat greedy murni. Perbandingan ini menunjukkan bahwa ekstrem mana pun kalah dari solusi tengah: eksploitasi tanpa eksplorasi mudah terjebak pada lengan suboptimal, sedangkan eksplorasi tanpa eksploitasi membuang informasi yang sudah dikumpulkan. Penyeimbangan antara keduanya menjadi inti dari setiap strategi yang lebih cerdas.

Lebih jauh, regret greedy yang sekitar 476.84 dapat dijelaskan secara aritmetika. Lengan optimal indeks 3 bernilai 2.2409, sedangkan lengan indeks 0 yang sering dipilih greedy bernilai 1.7641, sehingga selisih per langkah adalah 0.4768. Dikalikan sekitar 1000 langkah, hasilnya mendekati 476.84, yang sesuai dengan keluaran. Pola ini menegaskan bahwa greedy murni menghasilkan regret linear, yaitu tumbuh sebanding dengan jumlah langkah, karena ia tidak pernah keluar dari lengan yang dipilih pertama kali. Kebijakan acak murni juga linear, tetapi dengan kemiringan yang lebih curam karena rata-rata memilih lengan jauh dari optimal.

Kesalahan umum#

Menganggap greedy murni selalu kalah. Penyebabnya, keluaran menunjukkan regret greedy lebih kecil daripada acak murni, sehingga greedy tampak lebih buruk daripada yang sebenarnya. Perbaikannya, membandingkan greedy dengan strategi yang menyeimbangkan eksplorasi, bukan dengan acak murni, agar kontrasnya adil.
Menghitung regret dari reward, bukan dari nilai sebenarnya. Penyebabnya, reward sudah memuat derau sehingga regret yang dihitung dari reward ikut terderau. Perbaikannya, menghitung regret sebagai $q_*(a^*) - q_*(a_t)$ , yang bersih dari derau stokastik.
Menyimpulkan dari satu seed. Penyebabnya, hasil satu run dipengaruhi derau sehingga kesimpulan tidak stabil. Perbaikannya, mengulang pada banyak seed dan merata-ratakan, karena regret bandit memiliki varians yang tidak kecil antar realisasi.

Ringkasan#

Eksplorasi mengumpulkan informasi, eksploitasi memanfaatkan informasi yang sudah ada, dan keduanya saling membatasi pada setiap langkah.
Regret kumulatif $L_T=\sum_t(q_*(a^*)-q_*(a_t))$ mengukur kerugian keputusan terhadap optimal tanpa terpengaruh derau.
Greedy murni dapat terjebak pada lengan suboptimal, sedangkan acak murni membuang informasi, sehingga keduanya kalah dari strategi yang menyeimbangkan.

Referensi#

Reinforcement Learning: An Introduction (2nd ed.) — Sutton & Barto — Bab 2 memperkenalkan regret serta kebijakan greedy versus acak sebagai pembanding dasar.