Pengenalan kepada Masalah Multi-Armed Bandit

Banyak aplikasi praktikal memerlukan masalah pembuatan keputusan berurutan di mana ejen mesti memilih tindakan terbaik antara beberapa alternatif. Contoh aplikasi tersebut termasuk percubaan klinikal, sistem cadangan, dan pengesanan anomali. Dalam beberapa kes, maklumat sekunder atau konteks dikaitkan dengan setiap tindakan (contohnya, profil pengguna), dan maklum balas, atau ganjaran, adalah terhad kepada pilihan yang dipilih. Sebagai contoh, dalam percubaan klinikal, konteksnya ialah rekod perubatan pesakit (contohnya, status kesihatan, sejarah keluarga, dll.), tindakan sepadan dengan pilihan rawatan yang dibandingkan, dan ganjaran mewakili hasil rawatan yang dicadangkan (contohnya, kejayaan atau kegagalan). Aspek penting yang mempengaruhi kejayaan jangka panjang dalam konteks sedemikian ialah mencari keseimbangan yang baik antara penerokaan (contohnya, mencuba rawatan baru) dan eksploitasi (memilih rawatan terbaik yang diketahui setakat ini).

Pertukaran semula jadi antara penerokaan dan eksploitasi wujud dalam banyak masalah pembuatan keputusan berurutan dan secara tradisinya dirumuskan sebagai masalah bandit, yang dipersembahkan seperti berikut: Diberi K tindakan yang mungkin, atau "lengan", setiap satu dikaitkan dengan taburan kebarangkalian ganjaran yang tetap tetapi tidak diketahui, pada setiap lelaran, ejen memilih lengan untuk dimainkan dan menerima ganjaran, disampel daripada taburan kebarangkalian lengan masing-masing secara bebas daripada tindakan sebelumnya. Tugas ejen adalah belajar untuk memilih tindakannya supaya ganjaran kumulatif dari masa ke masa dimaksimumkan.

Perumusan Masalah Multi-Armed Bandit

Masalah multi-armed bandit (MAB) klasik ditakrifkan oleh K lengan, setiap satu dengan taburan ganjaran yang tidak diketahui. Pada setiap langkah masa t, ejen memilih lengan a_t ∈ {1, 2, ..., K} dan menerima ganjaran r_t yang disampel daripada taburan lengan yang dipilih. Matlamatnya adalah untuk memaksimumkan ganjaran kumulatif sepanjang T pusingan, atau setara, untuk meminimumkan penyesalan, iaitu perbezaan antara ganjaran kumulatif lengan optimum dan ganjaran kumulatif lengan yang dipilih.

Perhatikan bahawa ejen mesti mencuba lengan yang berbeza untuk belajar ganjaran mereka (iaitu, meneroka ganjaran), dan juga menggunakan maklumat yang dipelajari ini untuk menerima ganjaran terbaik (mengeksploitasi ganjaran yang dipelajari). Terdapat pertukaran semula jadi antara penerokaan dan eksploitasi. Sebagai contoh, mencuba setiap lengan tepat sekali, kemudian memainkan yang terbaik antara mereka. Pendekatan ini sering cenderung membawa kepada penyelesaian yang sangat tidak optimum apabila ganjaran lengan tidak pasti.

Penyelesaian yang berbeza telah dicadangkan untuk masalah ini, berdasarkan perumusan stokastik dan perumusan Bayesian; bagaimanapun, pendekatan ini tidak mengambil kira konteks atau maklumat sekunder yang tersedia untuk ejen.

Multi-Armed Bandit Kontekstual

Versi MAB yang sangat berguna ialah multi-arm bandit kontekstual (CMAB), atau ringkasnya bandit kontekstual, di mana pada setiap pusingan, sebelum memilih lengan, ejen memerhati vektor konteks x_t yang mungkin mempengaruhi taburan ganjaran lengan. Konteks boleh termasuk ciri pengguna, pembolehubah persekitaran, atau sebarang maklumat sampingan yang relevan. Matlamatnya kekal untuk memaksimumkan ganjaran kumulatif, tetapi kini dasar boleh bergantung pada konteks yang diperhatikan.

Bandit kontekstual telah mendapat perhatian yang ketara disebabkan oleh kebolehgunaannya dalam sistem cadangan diperibadikan, di mana konteks biasanya mewakili ciri pengguna, dan lengan sepadan dengan item atau kandungan yang berbeza untuk disyorkan. Ganjaran mungkin berupa klik, pembelian, atau sebarang bentuk penglibatan lain.

Beberapa algoritma telah dibangunkan untuk bandit kontekstual, termasuk LinUCB, yang menganggap hubungan linear antara konteks dan ganjaran jangkaan setiap lengan, dan persampelan Thompson dengan model linear. Algoritma ini telah menunjukkan prestasi empirikal yang kuat dalam pelbagai aplikasi.

Aplikasi Dunia Sebenar Multi-Armed Bandit

Percubaan Klinikal

Dalam percubaan klinikal, rangka kerja multi-armed bandit menyediakan pendekatan beretika untuk peruntukan rawatan. Konteks termasuk rekod perubatan pesakit, maklumat demografi, dan penanda genetik. Lengan mewakili pilihan rawatan yang berbeza, dan ganjaran menunjukkan kejayaan atau kegagalan rawatan. Algoritma bandit boleh memperuntukkan lebih banyak pesakit kepada rawatan yang berpotensi secara dinamik sambil masih meneroka alternatif, berpotensi membawa kepada hasil pesakit yang lebih baik dan percubaan yang lebih cekap.

Sistem Cadangan

Sistem cadangan mewakili salah satu aplikasi algoritma bandit yang paling berjaya. Platform utama menggunakan bandit kontekstual untuk memperibadikan kandungan, produk, dan cadangan iklan. Komponen penerokaan membolehkan sistem menemui keutamaan pengguna untuk item baru, manakala eksploitasi memanfaatkan keutamaan yang diketahui untuk memaksimumkan penglibatan pengguna. Pendekatan ini menangani masalah permulaan sejuk untuk item baru dan menyesuaikan diri dengan minat pengguna yang berubah dari masa ke masa.

Pengesanan Anomali

Dalam sistem pengesanan anomali, algoritma bandit boleh mengoptimumkan peruntukan sumber pemeriksaan yang terhad. Konteks mungkin termasuk metrik sistem, corak trafik rangkaian, atau ciri tingkah laku pengguna. Lengan mewakili strategi pemeriksaan yang berbeza atau model pengesanan anomali, dan ganjaran mencerminkan sama ada anomali sebenar dikenal pasti. Pendekatan ini membolehkan peruntukan sumber adaptif kepada kaedah pengesanan yang paling berpotensi.

Aplikasi Lain

Aplikasi tambahan termasuk pengoptimuman portfolio dalam kewangan, ujian A/B dalam pembangunan web, peruntukan sumber dalam pengkomputeran awan, dan teknologi pendidikan untuk pembelajaran adaptif. Fleksibiliti rangka kerja bandit menjadikannya boleh digunakan untuk mana-mana senario yang memerlukan pembuatan keputusan berurutan di bawah ketidakpastian dengan maklum balas terhad.

Algoritma dan Pendekatan Bandit

Bandit Stokastik

Bandit stokastik menganggap bahawa ganjaran setiap lengan diambil secara bebas daripada taburan tetap. Algoritma utama termasuk ε-greedy, yang memilih lengan terbaik dengan kebarangkalian 1-ε dan lengan rawak dengan kebarangkalian ε; Algoritma Upper Confidence Bound (UCB), yang memilih lengan berdasarkan anggaran optimis potensi mereka; dan persampelan Thompson, yang menggunakan taburan posterior Bayesian untuk mengimbangi penerokaan dan eksploitasi.

Bandit Adversarial

Bandit adversarial tidak membuat andaian statistik tentang penjanaan ganjaran, menganggapnya sebagai urutan sewenang-wenangnya yang mungkin dipilih oleh penentang. Algoritma Exp3 dan variannya direka untuk tetapan ini, menggunakan skema pemberat eksponen untuk mencapai penyesalan sublinear terhadap sebarang urutan ganjaran.

Bandit Bayesian

Bandit Bayesian mengekalkan taburan kebarangkalian ke atas taburan ganjaran mungkin lengan. Persampelan Thompson adalah pendekatan Bayesian yang paling terkemuka, yang menyampel daripada taburan posterior parameter ganjaran setiap lengan dan memilih lengan dengan nilai sampel tertinggi. Ini dengan elegan mengimbangi penerokaan dan eksploitasi mengikut ketidakpastian semasa.

Algoritma Bandit Kontekstual

Algoritma bandit kontekstual melanjutkan pendekatan ini untuk menggabungkan maklumat konteks. LinUCB menganggap fungsi ganjaran linear dan mengekalkan elipsoid keyakinan di sekitar anggaran parameter. Bandit neural menggunakan rangkaian neural dalam untuk memodelkan hubungan kompleks antara konteks dan ganjaran. Algoritma ini telah menunjukkan prestasi yang kuat dalam aplikasi berskala besar dengan konteks dimensi tinggi.

Tren Semasa dan Perspektif Masa Depan

Bidang multi-armed bandit sedang mengalami kebangkitan semula, dengan parameter masalah dan algoritma baru yang didorong oleh pelbagai aplikasi praktikal diperkenalkan, sebagai tambahan kepada masalah bandit klasik. Tren semasa yang penting termasuk integrasi bandit dengan pembelajaran mendalam, membawa kepada algoritma bandit kontekstual yang lebih berkuasa mampu mengendalikan konteks kompleks dan dimensi tinggi.

Tren penting lain ialah pembangunan algoritma bandit untuk persekitaran tidak pegun, di mana taburan ganjaran berubah dari masa ke masa. Ini adalah penting untuk banyak aplikasi dunia sebenar di mana keutamaan pengguna, keadaan pasaran, atau tingkah laku sistem berkembang. Algoritma seperti UCB tetingkap gelongsor dan teknik pendiskaunan menangani cabaran ini.

Terdapat minat yang semakin meningkat terhadap bandit kolaboratif dan teragih, di mana berbilang ejen belajar serentak dan mungkin berkongsi maklumat. Ini adalah relevan untuk tetapan pembelajaran terpersekutu di mana privasi data adalah penting. Selain itu, bandit dengan kekangan dan pertimbangan keselamatan mendapat perhatian, terutamanya untuk aplikasi dalam penjagaan kesihatan dan kewangan di mana tindakan tertentu mesti dielakkan.

Arah penyelidikan masa depan termasuk membangunkan algoritma yang lebih cekap untuk ruang tindakan yang sangat besar, menggabungkan maklumat struktur tentang ruang tindakan, dan meningkatkan pemahaman teori algoritma bandit dalam. Persilangan bandit dengan inferens kausal mewakili arah lain yang menjanjikan, membolehkan pembuatan keputusan yang lebih baik apabila intervensi mungkin mempunyai kesan jangka panjang.

Kesimpulan

Multi-armed bandit menyediakan rangka kerja yang berkuasa untuk pembuatan keputusan berurutan di bawah ketidakpastian dengan maklum balas terhad. Pertukaran penerokaan-eksploitasi asas muncul dalam banyak aplikasi praktikal, dari percubaan klinikal hingga sistem cadangan. Sambungan bandit kontekstual telah terbukti sangat berharga untuk sistem diperibadikan yang menyesuaikan diri dengan ciri individu.

Tinjauan ini telah memberikan gambaran keseluruhan komprehensif tentang perkembangan utama dalam multi-armed bandit, dengan tumpuan pada aplikasi dunia sebenar. Kami telah memeriksa perumusan masalah, algoritma utama, dan domain aplikasi yang pelbagai. Bidang ini terus berkembang dengan pantas, dengan algoritma baru menangani cabaran seperti ketidakpegunan, ruang tindakan besar, dan kekangan keselamatan.

Apabila algoritma bandit menjadi lebih canggih dan digunakan untuk masalah yang semakin kompleks, mereka akan terus memainkan peranan penting dalam mengoptimumkan pembuatan keputusan merentasi pelbagai domain. Penyelidikan berterusan dalam bidang ini menjanjikan algoritma yang lebih berkesan dan aplikasi yang lebih luas pada masa hadapan.