bandit

crossroads
awas salah ngasih tahu abang gojeknya belok kiri atau kanan

Pembukaan

Pernahkah Anda berada dalam keadaan harus memilih di antara 2 pilihan, di mana pilihan yang Anda ambil itu dapat mengubah kehidupan Anda secara drastis?

Saya pernah dan hampir mengalaminya setiap hari. Setiap pulang dari kantor saya selalu dihadapkan pilihan untuk naik bis atau naik busway. Skenario pertama adalah saya langsung dapat bus dan sampai rumah dengan cepat. Skenario kedua saya langsung dapat busway, sampai rumah lumayan cepat tapi lebih capek karena harus berdiri. Skenario terburuk adalah menunggu bus, bus tidak lewat dalam waktu satu jam, Kemudian jadinya menunggu busway, tapi kemudian bisnya malah lewat di depan mata, akhirnya baru dapat busway 30 menit kemudian, itu pun berdiri hingga 1.5 jam karena jalan macet…

Efeknya tentunya sangat berpengaruh. Kalau saya dapat opsi yang pertama, maka saya bisa sampai rumah dengan waktu yang relatif lebih cepat, badan tidak terlalu capek, dan mungkin malamnya bisa produktif sedikit seperti untuk menulis blog atau belajar hal baru dengan menonton video online course.

Bandingkan dengan opsi terakhir yang mana saya sampai rumah larut malam dan kehabisan tenaga sehingga saya hanya bisa menghabiskan waktu dengan menonton video pewdiepie di youtube atau main hearthstone tanpa mikir.

Bandit algorithm

Joking aside, contoh kisah nyata di atas hanyalah ilustrasi belaka untuk menggambarkan suatu kelas masalah yang di matematika dikenal dengan nama bandit algorithm. Bandit algorithm ini namanya terinspirasi dari mesin slot yang ada di kasino2.

Las_Vegas_slot_machines
hati-hati judi dapat meracuni kehidupan, kata bang roma

Penjelasan resminya dari algoritma bandit kira-kira seperti berikut. Pada setiap turn kita memiliki beberapa opsi yang bisa dipilih. Masing-masing opsi akan memberikan reward/hadiah dengan jumlah yang kita belum ketahui sebelumnya. Tugas kita adalah memaksimalkan total reward yang kita dapatkan dari awal pilihan pertama hingga pilihan terakhir. Terdengarnya susah-susah gampang bukan?

Ada juga yang mengklasifikasikan algoritma bandit ini ke dalam special case dari reinforcement learning (RL yang tidak memiliki states). Kalau penasaran, lebih lanjutnya bisa cek chapter 1 dari buku Reinforcement Learning-nya Sutton & Barto.

Implementasi

Untuk mengetes performa dari algoritma2 yang akan kita coba, pertama kita generate terlebih dahulu 2000 simulasi yang masing-masing memiliki distribusi reward yang berbeda-beda. Simulasi ini akan kita jalankan selama 1000 putaran. Contoh salah satu distribusinya adalah sebagai berikut:

distribution
option 3 dan 4 punya reward yg relatif lebih besar dari pilihan lainnya, tapi kita tidak tahu informasi itu di awal

Apa strategi pertama yang bisa kita coba? Pure random. Di tiap turn kita pilih saja opsi terserah yang mana saja. Kalau misalkan random saja sudah bagus, ngapain mikirin algoritma lain yang lebih rumit?

random bandit

Ternyata kalau random, rata2 reward yg kita dapat untuk masing-masing putaran berkisar di angka 0. Weks, jelek sekali performanya.

Bagaimana kalau kita bersifat serakah (greedy), jadi kita hanya memilih opsi yang selama ini memberikan rata2 reward paling tinggi?

greedy bandit

Lumayan, hasilnya secara rata-rata lebih bagus dari random (1, bukan 0). Kekurangannya adalah, karena sifatnya yang greedy, begitu kita memilih opsi yang memberikan nilai positif, maka kita bakal terus-terusan memilih opsi tersebut. Padahal di luar sana mungkin ada pilihan yg bisa menghasilkan reward yang lebih tinggi.

Untuk mengatasi hal tersebut, kita harus bisa menyeimbangkan antara exploitation (mengumpulkan reward sebanyak-banyaknya dengan memilih opsi yang pasti memberikan hasil bagus) dengan exploration (mencari opsi yang mungkin memberikan hasil yang lebih bagus lagi). Salah satu strategi yang bisa dipakai adalah e(epsilon)-greedy. Jadi pada setiap turn, kita punya peluang sebesar e untuk memilih opsi lain secara random. Nilai e ini sendiri jelas harus dipilih secara bijak, karena kalau terlalu kecil maka kita bisa terjebak di pilihan yang tidak optimal, tapi kalau terlalu besar maka kita akan melewatkan terlalu banyak kesempatan untuk mendapat reward yang pasti besar, sehingga secara kumulatif total reward yang kita kumpulkan bisa lebih kecil.

Implementasi-nya kira-kira seperti berikut:

greedy bandit code

egreedy bandit

Wow, sekarang kita bisa mendapatkan nilai dari 1.2 hingga 1.4, tergantung nilai e yg kita pilih.

Now can we do even better than that? Tentu saja. Perhatikan, pada strategy e-greedy, pada saat kita melakukan eksplorasi, kita memilih opsi secara random, tidak peduli terhadap performanya yang sebelumnya. Bagaimana kalau misalkan kita pilih suatu opsi berdasarkan rata-rata performanya sekarang dan yang paling sedikit dipilih sejak saat ini. Motivasinya adalah opsi yang jarang dipilih bisa jadi memiliki potensi memberikan reward besar yang belum terealisasikan.

Strategi ini bernama Upper Confidence Bound (UCB). Untuk derivasi lengkapnya, bisa diintip di blog-nya bang Jeremy Kun. Implementasinya kira-kira seperti ini:

ucb bandit code

Dan hasilnya ternyata memang paling bagus di antara algoritma-algoritma sebelumnya, hingga 1.5!.

ucb bandit

Dan ini adalah perbandingan semua algoritma yang sudah disebut di atas. UCB memiliki nilai paling tinggi dan paling cepat juga mencapai nilai tersebut.

bandit full

Penutup

Apa aplikasi langsung yang bisa dicoba dengan menggunakan teknik ini? Misalkan kamu mau mengoptimisasi conversion rate dari sebuah website dengan mencoba beberapa versi dari landing page-nya. Conventional wisdom-nya adalah kita lakukan A/B test untuk mengetahui varian mana yang performanya paling bagus. Nah, tapi seringkali A/B test ini harus dilakukan dalam jangka waktu yang lumayan lama dengan agar jumlah sampelnya cukup secara statistik. Dengan menjalankan A/B test ini, kita kehilangan potensi untuk menghasilkan reward karena sebagian user akan mendapat varian yang mungkin secara performa lebih buruk daripada yang lainnya.

Nah, kalau misalkan kita formulasikan ini sebagai problem bandit dengan menggunakan algoritma UCB misalnya, maka sistem akan secara otomatis meng-assign user ke varian yang mempunyai performa yang paling bagus. Tanpa harus menunggu A/B test-nya selesai sehingga total cumulative reward yang dikumpulkan di akhir jauh lebih tinggi.

Lalu apakah dengan adanya bandit algorithm maka A/B testing jadi obsolete? Tentu saja tidak, karena keduanya memiliki tujuan yang berbeda. Berikut wejangan dari om Chris Stucchio.

conclusions

File eksperimen di atas bisa ditemukan di link berikut: https://github.com/mitbal/sidu/blob/master/bandit.ipynb

Selamat mencoba. Semoga berguna. Salam.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s