Pengantar Bandit Multi-Bersenjata

Hak Cipta 2021 The TF-Agents Authors.

pengantar

Multi-Armed Bandit (MAB) adalah kerangka kerja Machine Learning di mana agen harus memilih tindakan (senjata) untuk memaksimalkan imbalan kumulatifnya dalam jangka panjang. Di setiap putaran, agen menerima beberapa informasi tentang keadaan saat ini (konteks), kemudian memilih tindakan berdasarkan informasi ini dan pengalaman yang dikumpulkan di putaran sebelumnya. Di akhir setiap putaran, agen menerima hadiah yang terkait dengan tindakan yang dipilih.

Mungkin contoh yang paling murni adalah masalah yang dipinjamkan nama menjadi MAB: membayangkan bahwa kita dihadapkan dengan k mesin slot (bandit bertangan satu), dan kita perlu mencari tahu mana yang memiliki payout terbaik, sementara tidak kehilangan terlalu banyak uang.

Mencoba setiap mesin satu kali dan kemudian memilih salah satu yang paling banyak membayar bukanlah strategi yang baik: Agen dapat jatuh ke dalam memilih mesin yang memiliki hasil keberuntungan pada awalnya tetapi secara umum kurang optimal. Sebaliknya, agen harus berulang kali kembali memilih mesin yang tidak terlihat bagus, untuk mengumpulkan lebih banyak informasi tentang mereka. Inilah tantangan utama dalam Multi-Armed Bandit: agen harus menemukan campuran yang tepat antara mengeksploitasi pengetahuan sebelumnya dan mengeksplorasi agar tidak mengabaikan tindakan yang optimal.

Contoh MAB yang lebih praktis melibatkan sepotong informasi sampingan setiap kali pelajar membuat keputusan. Kami menyebut informasi sampingan ini "konteks" atau "pengamatan".

Bandit Multi-Bersenjata dan Pembelajaran Penguatan

Mengapa ada MAB Suite di perpustakaan TF-Agents? Apa hubungan antara RL dan MAB? Bandit Multi-Bersenjata dapat dianggap sebagai kasus khusus Pembelajaran Penguatan. Mengutip Pengenalan RL :

Pada setiap langkah waktu, agen mengambil tindakan terhadap lingkungan berdasarkan kebijakan \(\pi(a_t|s_t)\), di mana \(s_t\) adalah pengamatan saat ini dari lingkungan, dan menerima hadiah \(r_{t+1}\) dan pengamatan berikutnya \(s_{t+1}\) dari lingkungan . Tujuannya adalah untuk memperbaiki kebijakan sehingga memaksimalkan jumlah imbalan (pengembalian).

Dalam kasus RL umum, pengamatan berikutnya \(s_{t+1}\) tergantung pada keadaan sebelumnya \(s_t\) dan tindakan \(a_t\) diambil oleh kebijakan. Bagian terakhir inilah yang membedakan MAB dari RL: pada MAB, state selanjutnya yaitu observasi, tidak bergantung pada aksi yang dipilih oleh agen.

Kesamaan ini memungkinkan kita untuk menggunakan kembali semua konsep yang ada di TF-Agents.

• Lingkungan output pengamatan, dan merespon tindakan dengan imbalan.
• Sebuah kebijakan output tindakan berdasarkan observasi, dan
• Seorang agen berulang kali update kebijakan berdasarkan sebelumnya tupel pengamatan-aksi-reward.

Lingkungan jamur

Untuk tujuan ilustrasi, kami menggunakan contoh mainan yang disebut "Lingkungan Jamur". Jamur dataset ( Schlimmer, 1981 ) terdiri dari contoh label dari jamur dan beracun. Fitur termasuk bentuk, warna, ukuran berbagai bagian jamur, serta bau dan banyak lagi.

Kumpulan data jamur, seperti semua kumpulan data pembelajaran yang diawasi, dapat diubah menjadi masalah MAB kontekstual. Kami menggunakan metode juga digunakan oleh Riquelme et al. (2018) . Dalam konversi ini, agen menerima fitur jamur, memutuskan untuk memakannya atau tidak. Memakan jamur yang dapat dimakan menghasilkan hadiah +5, sementara memakan jamur beracun akan memberikan +5 atau -35 dengan probabilitas yang sama. Tidak memakan jamur menghasilkan 0, terlepas dari jenis jamurnya. Tabel berikut merangkum tugas hadiah:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

Agen LinUCB

Berkinerja baik dalam lingkungan bandit kontekstual memerlukan perkiraan yang baik tentang fungsi penghargaan dari setiap tindakan, mengingat pengamatan. Salah satu kemungkinannya adalah mengestimasi fungsi reward dengan fungsi linier. Artinya, untuk setiap tindakan \(i\), kami mencoba untuk menemukan parameter \(\theta_i\in\mathbb R^d\) yang perkiraan

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

sedekat mungkin dengan kenyataan. Berikut \(v_t\in\mathbb R^d\) adalah konteks yang diterima pada saat langkah \(t\). Kemudian, jika agen sangat percaya diri dalam perkiraan, ia dapat memilih \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) untuk mendapatkan diharapkan reward tertinggi.

Seperti dijelaskan di atas, hanya memilih lengan dengan perkiraan hadiah terbaik tidak mengarah pada strategi yang baik. Ada banyak cara yang berbeda untuk mencampur eksploitasi dan eksplorasi di agen estimator linier, dan salah satu yang paling terkenal adalah Confidence Linear Atas Bound (LinUCB) algoritma (lihat misalnya Li et al. 2010 ). LinUCB memiliki dua blok bangunan utama (dengan beberapa detail dihilangkan):

1. Ia memelihara perkiraan untuk parameter setiap lengan dengan Linear Least Squares: \(\hat\theta_i\sim X^+_i r_i\), di mana \(X_i\) dan \(r_i\) adalah konteks ditumpuk dan manfaat dari putaran di mana lengan \(i\) dipilih, dan \(()^+\) adalah kebalikan semu .
2. Ia memelihara ellipsoids kepercayaan didefinisikan oleh terbalik kovarians \(X_i^\top X_i\) untuk perkiraan di atas.

Ide utama LinUCB adalah "Optimisme dalam Menghadapi Ketidakpastian". Agen menggabungkan eksplorasi melalui peningkatan perkiraan dengan jumlah yang sesuai dengan varians dari perkiraan tersebut. Itu adalah di mana ellipsoids percaya diri datang ke dalam gambar: untuk setiap lengan, perkiraan optimis adalah \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\), di mana \(E_i\) adalah ellipsoid sekitar \(\hat\theta_i\). Memilih agen terbaik mencari lengan \(\arg\max_i\hat r_i\).

Tentu saja deskripsi di atas hanyalah ringkasan intuitif tetapi dangkal dari apa yang dilakukan LinUCB. Sebuah implementasi dapat ditemukan di basis kode kita di sini

Apa berikutnya?

Jika Anda ingin memiliki tutorial yang lebih rinci tentang perpustakaan Bandits kami lihat kami tutorial untuk Bandits . Jika, sebaliknya, Anda ingin mulai menjelajahi perpustakaan kami segera, Anda dapat menemukannya di sini . Jika Anda bahkan lebih bersemangat untuk memulai latihan, melihat beberapa kami contoh end-to-end di sini , termasuk lingkungan jamur yang dijelaskan di atas dengan LinUCB sini .