Bandit multi-lengan

Satu state dan pilihan berulang, RL dengan bagian yang bergerak ditiadakan.

Daftar isi

Bandit multi-lengan adalah masalah reinforcement learning dengan satu state dan pilihan yang berulang. Agen menghadapi sekumpulan lengan, menarik satu di antaranya pada setiap langkah, lalu menerima reward berupa nilai sebenarnya lengan itu ditambah derau. Bagian yang bergerak pada MDP penuh, yaitu transisi state dan faktor diskon, sengaja ditiadakan sehingga pertanyaan menyempit menjadi satu hal: lengan mana yang harus ditarik berikutnya. Setelah membaca topik ini, pembaca mengenal definisi formal bandit k-armed, hubungan antara nilai sebenarnya lengan dan reward yang diobservasi, serta cara membangun sebuah bandit dengan NumPy.

Bandit k-armed sebagai kasus khusus MDP#

Bandit k-armed adalah MDP dengan satu state tunggal, k aksi diskret, dan tanpa transisi state. Apabila sebuah aksi $a$ dipilih, lingkungan mengembalikan sebuah reward yang ditarik dari distribusi bersyarat pada aksi itu, lalu agen kembali ke state yang sama. Karena state tidak pernah berubah, setiap keputusan bersifat stasioner, dan return jangka panjang disederhanakan menjadi reward instan. Faktor diskon $\gamma$ tidak berperan karena tidak ada langkah masa depan yang perlu didiskon.

Dengan penghapusan transisi state, sebagian besar peralatan MDP penuh, seperti fungsi nilai $V(s)$ dan persamaan Bellman, tidak lagi diperlukan. Yang tersisa hanyalah pasangan antara aksi dan reward, sehingga tugas pembelajaran menjadi memperkirakan nilai harapan setiap aksi dari pengalaman. Inilah sebabnya bandit disebut sebagai RL dengan bagian yang bergerak ditiadakan: agen tetap belajar dari interaksi, tetapi ruang masalahnya direduksi menjadi satu tabel berisi k buah nilai.

Karena hanya ada satu state, kebijakan yang dipelajari berupa distribusi probabilitas atas k aksi, bukan pemetaan dari state ke aksi. Penyederhanaan ini membuat bandit menjadi medan uji yang ideal untuk memahami dilema eksplorasi versus eksploitasi sebelum masuk ke MDP penuh dengan banyak state.

Nilai sebenarnya lengan dan reward yang diobservasi#

Setiap lengan $a$ memiliki nilai sebenarnya $q_*(a)$ , yaitu nilai harapan reward apabila aksi itu dipilih:

q_*(a) = \mathbb{E}[R \mid A = a]

Pada bandit Gaussian yang lazim dipakai di buku Sutton dan Barto, nilai sebenarnya setiap lengan ditarik sekali dari $\mathcal{N}(0,1)$ , dan reward yang diobservasi pada setiap penarikan ditambah derau stokastik $R = q_*(a) + \mathcal{N}(0,1)$ . Agen tidak mengetahui $q_*(a)$ dan harus memperkirakannya dari reward yang diterimanya, yang lazim disebut estimasi action-value, dilambangkan $Q(a)$ .

Karena derau memiliki rata-rata nol, rata-rata sampel reward yang diterima dari sebuah lengan akan konvergen ke $q_*(a)$ seiring banyaknya tarikan. Inilah inti gagasan sample-average: semakin sering sebuah lengan ditarik, semakin akurat $Q(a)$ sebagai pendekatan $q_*(a)$ . Namun, setiap reward tunggal tetap membawa derau, sehingga satu observasi tidak pernah cukup untuk menilai kualitas lengan secara andal.

Membangun bandit dengan NumPy#

Blok berikut membangun sebuah bandit 10-lengan, menarik tiap lengan tepat sekali, lalu mencetak nilai sebenarnya q_true bersama reward yang diperoleh. Karena seed ditegaskan pada awal skrip, keluaran bersifat reproducible pada mesin yang sama.

python

import warnings; warnings.filterwarnings("ignore")
import numpy as np
np.random.seed(0)
k = 10
q_true = np.random.normal(0, 1, k)
rewards = q_true + np.random.normal(0, 1, k)
print("q_true :", np.array2string(q_true, precision=4))
print("reward :", np.array2string(rewards, precision=4))
print("argmax :", int(np.argmax(q_true)))

text Keluaran

q_true : [ 1.7641  0.4002  0.9787  2.2409  1.8676 -0.9773  0.9501 -0.1514 -0.1032
  0.4106]
reward : [ 1.9081  1.8544  1.7398  2.3626  2.3114 -0.6436  2.4442 -0.3565  0.2098
 -0.4435]
argmax : 3

Membaca keluaran#

Lengan dengan nilai sebenarnya tertinggi adalah lengan indeks 3 dengan q_true sebesar 2.2409, sehingga argmax mengembalikan 3. Namun reward yang diobservasi untuk lengan itu, yaitu 2.3626, tidak persis sama dengan nilai sebenarnya karena derau stokastik ditambahkan saat penarikan. Sebaliknya, lengan indeks 6 memiliki q_true yang lebih rendah, yaitu 0.9501, tetapi reward observasinya justru 2.4442, lebih tinggi daripada reward lengan terbaik.

Ketimpangan ini menunjukkan inti masalah bandit: reward tunggal adalah estimator yang berisiko tinggi terhadap kualitas lengan. Tanpa penarikan berulang, agen tidak dapat membedakan apakah sebuah reward tinggi berasal dari lengan yang benar-benar baik atau sekadar derau positif. Estimasi action-value yang andal membutuhkan rata-rata atas banyak tarikan, dan dari sinilah muncul dilema eksplorasi versus eksploitasi yang menjadi inti masalah bandit.

Lebih jauh, rentang q_true dari -0.9773 sampai 2.2409 menunjukkan bahwa lengan-lengan ini tidak setara, melainkan membentuk hierarki nilai yang cukup lebar. Lengan dengan q_true negatif, yaitu indeks 5, 7, dan 8, layak dihindari, sedangkan lengan indeks 3 dan 4 saling bersaing rapat di puncak. Pada eksperimen yang melibatkan banyak tarikan, agen ideal menghabiskan sebagian besar langkah pada dua lengan teratas dan meninggalkan tiga lengan negatif setelah mengetahuinya. Pola alokasi seperti inilah yang menjadi sasaran setiap strategi eksplorasi yang dibahas pada topik-topik selanjutnya dalam modul ini.

Kesalahan umum#

Menganggap reward tunggal sebagai nilai sebenarnya lengan. Penyebabnya, keluaran mencampuradukkan q_true dan reward dalam satu tampilan sehingga kedua besaran tampak setara. Perbaikannya, selalu membedakan q_true sebagai parameter tetap lingkungan dan reward sebagai observasi yang terderau, lalu merata-ratakan banyak reward untuk memperkirakan q_true.
Membangun bandit tanpa seed. Penyebabnya, np.random.normal tanpa seed menghasilkan nilai berbeda pada setiap eksekusi. Perbaikannya, menetapkan np.random.seed(0) di awal skrip agar q_true dan reward reproducible pada mesin yang sama.
Mencampurkan indeks berbasis nol dan satu. Penyebabnya, dalam prosa sering dikatakan “lengan keempat” padahal NumPy menyatakannya sebagai indeks 3. Perbaikannya, konsisten memakai indeks berbasis nol dan menulis “lengan indeks 3” dalam prosa maupun kode.

Ringkasan#

Bandit k-armed adalah MDP satu state dengan k aksi dan tanpa transisi, sehingga return direduksi menjadi reward instan.
Nilai sebenarnya lengan $q_*(a)=\mathbb{E}[R\mid A=a]$ tidak diketahui agen, dan reward observasi adalah $q_*(a)$ ditambah derau.
Estimasi $Q(a)$ menuju $q_*(a)$ melalui rata-rata sampel, tetapi satu tarikan tidak cukup karena derau.

Referensi#

Reinforcement Learning: An Introduction (2nd ed.) — Sutton & Barto — Bab 2 memperkenalkan bandit k-armed sebagai kasus paling sederhana reinforcement learning.
Gymnasium Documentation — Farama Foundation — Referensi API lingkungan yang dipakai sepanjang jalur ini, meskipun bandit pada topik ini dibangun langsung dengan NumPy.