Upper confidence bound (UCB)

Implementasikan pemilihan aksi UCB1:

a = \arg\max_a \left[ Q(a) + c\sqrt{\frac{\ln t}{N(a)}} \right]

Aksi dengan $N(a) = 0$ dipilih lebih dulu (yang indeksnya terkecil). Jika seri, pilih indeks terkecil.

Q = [1.0, 0.5], N = [10, 1], t = 11, c = 2  →  1   // aksi 1 baru dicoba sekali: bonusnya besar
Q = [1.0, 0.5], N = [10, 10], t = 21, c = 2 →  0   // bonus sama, Q menentukan

Optimis saat ragu

ε-greedy menjelajah secara acak, termasuk mencoba lagi aksi yang sudah jelas buruk. UCB menjelajah secara terarah: setiap aksi diberi bonus sebesar ketidakpastiannya. Aksi yang jarang dicoba punya selang kepercayaan lebar, sehingga batas atasnya (upper confidence bound) bisa saja tinggi.

$\ln t$ tumbuh pelan: aksi yang lama diabaikan perlahan-lahan mendapat bonus lagi.
$N(a)$ besar: bonus kecil, karena perkiraan sudah yakin.
$c$ mengatur seberapa berani menjelajah. Dengan $c = 0$ , UCB menjadi serakah murni.

Di lab Bandit, bandingkan grafik % lengan terbaik UCB dengan ε-greedy.

Penjelasan

Yang diminta. Satu indeks aksi.

Langkah di kode:

Loop N: jika ada yang 0, kembalikan indeks pertama itu. Tanpa ini, rumusnya membagi dengan nol.
Skor setiap aksi: Q[a] + c * sqrt(ln(t) / N[a]).
scores.index(max(scores)) memberi argmax dengan indeks terkecil saat seri.

Cek case 2. Aksi 0: $1 + 2\sqrt{\ln 11/10} \approx 2.10$ . Aksi 1: $0.5 + 2\sqrt{\ln 11/1} \approx 3.60$ . Aksi 1 menang karena belum banyak dicoba.

Case $c = 0$ . Bonus hilang, jadi hanya $Q$ yang dibandingkan: aksi 1 ( $Q = 0.3$ ).

Yang dikembalikan: int.