Ulasan Buku: Reinforcement Learning: An Introduction, 2nd Edition (Sutton & Barto)

Reinforcement learning (RL) adalah salah satu cabang dari pembelajaran mesin untuk mengajari sebuah agent agar membuat keputusan yang terbaik, yaitu yang memberikan imbal hasil terbesar. Kalau Anda ingin mempelajari RL dari sebuah buku, maka singkat kata ini adalah buku terbaik yang bisa Anda baca. Dan gratis pula!

Ya, versi draft (PDF) dari buku ini bisa Anda unduh di laman penulisnya:   http://incompleteideas.net/book/the-book-2nd.html.

Reinforcement Learning Introduction - book cover

Penulis buku ini, Richard S. Sutton, adalah profesor ilmu komputer di University of Alberta, Kanada, dan tahun lalu direkrut oleh Google DeepMind. Beliau diakui banyak orang sebagai “bapaknya” RL. Sedangkan Andrew Barto, profesor ilkom di University of Massachusetts Amherst, adalah gurunya Sutton (pembimbing PHD-nya). Lebih jauh lagi, Sutton adalah pembimbing dari David Silver, profesor di UCL yang juga bagian dari Deep Mind dan video pengajaran RL-nya sudah pernah saya review di sini.

Edisi pertama dari buku “Reinforcement Learning: An Introduction” ini terbit pertama kali di tahun 1998. Jadi sekali lagi ini menunjukkan betapa pak Sutton ini telah sekian lama mendalami bidang RL ini. Rentang waktu yang sekian lama ini juga menyebabkan buku ini dinanti oleh banyak orang, karena orang ingin melihat perkembangan RL terbaru dituliskan dalam buku ini.

Saya sendiri menanti-nanti buku ini dari tahun lalu, dan sampai saat ini (Feb 2018) buku ini belum juga terbit. Tapi, berita bagusnya adalah, Anda bisa baca draft terakhir buku ini, versi lengkap bukan cuplikan, dengan cara mengunduh PDF-nya di http://incompleteideas.net/book/the-book-2nd.html. Draft versi terakhir (Januari 2018) sudah berisi tulisan yang lengkap (semua babnya lengkap), jadi isinya tidak akan jauh berbeda dengan bukunya nanti.

Sebagai tambahan, saya amati memang ada banyak buku di bidang pembelajaran mesin yang versi PDF-nya tersedia, misalnya Algorithms for Reinforcement Learning oleh Szepesvári, The Elements of Statistical Learning oleh Hastie, Tibshirani, dan Friedman, Machine Learning oleh Tom Mitchell, Pattern Recognition and Machine Learning oleh Bishop, Artificial Intelligence: A Modern Approach oleh Russel dan Norvig, dsb. Mungkin memang para penulisnya mempunyai semangat untuk berbagi.

Kembali ke buku ini..

Seperti ditulis di awal, RL adalah tentang bagaimana memutuskan suatu aksi yang tepat — bagaimana memetakan dari situasi menjadi aksi — untuk mendapatkan imbalan yang sebesar-besarnya. Ada beberapa faktor yang membuat RL berbeda dengan pembelajaran mesin yang lain misalnya supervised dan unsupervised learning:

  • RL memungkinkan suatu agent membuat rencana atau strategi. Jadi tidak terbatas pada membuat satu keputusan untuk satu waktu saja, tapi juga bagaimana agar rangkaian keputusan yang nanti dipilih dapat mencapai suatu tujuan tertentu (atau dalam terminologi RL, mendapatkan imbalan sebesar-besarnya).
  • Tidak ada orang yang mensupervisi pembelajaran suatu agent. Tidak ada “guru” yang memberitahu langkah apa yang baik dilakukan, atau apakah langkah yang dipilih baik atau tidak. Agent harus belajar sendiri dengan berbuat dan mempelajari hasil perbuatannya (disebut juga trial and error).
  • Seringkali imbalan yang diterima sifatnya tertunda, dan agent harus melakukan langkah-langkah yang panjang sebelum hasilnya diketahui (misalnya, imbalan untuk sebuah langkah di permainan catur hanya diketahui belasan atau puluhan langkah berikutnya ketika permainannya berakhir baik dengan kemenangan atau kekalahan).
  • Agent harus mencari mana di antara langkah-langkah yang telah dilakukan yang berkontribusi terhadap hasil dan mana yang sebenarnya tidak berkontribusi. Seperti pada contoh permainan catur di atas, setelah kemenangan tercapai, mana di antara belasan atau puluhan langkah-langkah yang telah dilakukan sebelumnya yang paling berkontribusi pada kemenangan tersebut? Permasalahan ini dikenal dengan credit assignment problem.
  • Agent bisa mengorbankan imbalan sekarang untuk mendapatkan imbalan yang lebih besar di masa mendatang.
  • Agent harus mencari keseimbangan antara memaksimalkan imbalan yang diterima (dengan kata lain, mengeksploitasi strategi yang sudah diketahui) dengan mengeksplorasi hal-hal baru yang mungkin akan menghasilkan imbalan yang lebih baik di masa mendatang.

Hal-hal di atas adalah hal-hal yang sangat mirip dengan permasalahan yang kita hadapi di kehidupan nyata. Tidak heran kalau kemajuan di bidang RL memungkinkan robot untuk melakukan hal-hal yang mirip manusia, misalnya bermain game, mengendalikan mobil atau helikopter, berjalan dan bermanuver dengan dua kaki, mengendalikan portfolio keuangan, dan sebagainya. Di banyak hal, bahkan kemampuannya jauh melebihi kemampuan manusia. Dengan pertimbangan lagi bahwa RL memungkinkan agent untuk membuat suatu strategi, maka ini menjadikan RL suatu bidang pembelajaran mesin yang sangat menarik untuk dipelajari.

Buku 400 halaman ini dibagi menjadi tiga bagian:

  • bagian I: pengenalan pada permasalahan dan solusi RL. Sebagian besar teori RL dijelaskan di bagian ini, tapi agar sederhana maka solusinya diberikan dalam bentuk tabular, artinya semua state disimpan dalam tabel. Karena jumlah state bisa banyak sekali (bahkan bisa tak terhingga), maka metoda tabular kurang bisa dipakai di dunia nyata. Metoda tabular dipilih di sini agar mudah dipahami dan agar kita bisa lebih berkonsentrasi pada metoda RL-nya, bukan metoda penyimpanan state-nya.
  • bagian II:  mengganti metoda tabular dengan function approximator (FA). Dengan FA, value dari suatu state atau action tidak disimpan mentah-mentah dalam tabel seperti metoda tabular yang membutuhkan tempat penyimpanan besar, tapi dibuat model untuk meramalkan value tersebut, dengan menggunakan model supervied learning apapun misalnya regresi linier atau jaringan saraf tiruan.
  • bagian III: menyajikan hubungan RL dengan bidang-bidang terkait misalnya psikologi dan ilmu saraf, dan menilik perkembangan terakhir RL terutama bidang-bidang dimana RL telah mengalami keberhasilan yang signifikan (terutama di bidang permainan sih).

Buku ini memberikan pengenalan RL dari permasalahan yang mendasar sekali. Pertama, kita akan dikenalkan dengan permasalahan pengambilan keputusan dengan cara mengenali permainan multi-armed bandits.

slot_machine
One-arm bandit

Karakteristik permainan ini adalah hanya mempunyai satu state, artinya apa yang terjadi saat ini tidak ada hubungannya dengan apa yang terjadi sebelumnya. Namun demikian konsep-konsep mendasar dari RL sudah mulai tampak di sini, misalnya interaksi dengan lingkungan, konsep imbalan, dan konsep eksploitasi eksplorasi.

Kemudian pembaca akan dikenalkan dengan konsep penting dalam RL yaitu Markov Decision Process (MDP), yaitu tentang bagaimana merepresentasikan permasalahan dalam representasi yang bisa diproses secara formal oleh RL atau Dynamic Programming (DP). Dalam MDP, kita merepresentasikan permasalahan dalam states, actions, state transitions, reward function, dan discount factor.

Lalu dibahas tentang Dynamic Programming (DP). Dalam DP, kita mulai diperkenalkan dengan bagaimana memilih aksi ketika kita mempunyai model yang sempurna dari lingkungan tempat agent itu berada. Baru kemudian kita beranjak ke situasi nyata untuk memilih aksi ketika kita tidak mempunyai model dari lingkungan, dengan dua pendekatan pemecahan masalah utama di RL yaitu Monte Carlo (MC) dan Temporal Difference (TD).

Berikut adalah daftar isi lengkap dari buku ini.

toc-1.pngTOC-2TOC-3TOC-4TOC-5toc-6.png

Tiap bab disajikan dengan runut, mulai dari motivasi kenapa suatu metoda dibutuhkan dan apa keunggulannya dibandingkan metoda yang dijelaskan sebelumnya, sejarah dan latar belakang, intuisi dari metoda tersebut, formula matematika tentunya, sampai ke algoritma prosedural, pengembangan-pengembangan, pemakaian, contoh kasus, dan pertimbangan-pertimbangan yang relevan untuk pemakaian metoda tersebut. Penjelasannya sangat memuaskan karena sangat komprehensif, dari sumber yang autoritatif, dan formula-formula matematika yang disajikan rasanya cukup terjangkau untuk dipahami.

Rasanya semua metoda dan pendekatan di RL dijelaskan di buku ini. Sebagai informasi, metoda-metoda dalam RL dapat kita pilah menjadi beberapa jenis:

  • Berdasarkan apakah proses RL membutuhkan model dari lingkungan atau tidak, RL dipilah menjadi:
    • model based
    • model free learning
    • hybrid (Dyna)
  • Berdasarkan representasi dari value function, bisa dipilah menjadi:
    • tabular
    • function approximation
  • Berdasarkan apakah interaksi agen dengan lingkungan dibatasi oleh sesi (mempunyai awal dan akhir sesi) ataukah berlangsung terus menerus tanpa ada awal dan akhir:
    • episodic
    • continuous
  • value function vs policy gradient
  • full backup (dynamic programming) vs sample based (Monte Carlo, TD)
  • episodic (Monte Carlo) vs bootstrap (TD)
  • masalah eksploitasi vs eksplorasi

Setelah membaca buku ini, Anda akan mengerti betul konsep-konsep dasar dalam RL, tidak hanya formula matematika dan algoritma proseduralnya, tapi juga hal-hal penting dibalik itu. Rasanya Anda akan siap untuk membuat implementasi sendiri metoda-metoda RL yang dijelaskan di buku ini seperti misalnya Sarsa, Q-Learning,TD(λ), actor-critic, dsb.

Namun demikian ada beberapa hal yang kurang dalam buku ini.

Pertama, sesuai dengan judulnya yaitu “An Introduction“, banyak konsep-konsep advanced dan termutakhir yang tidak dijelaskan di buku ini, misalnya Asynchronous Advanced Actor Critic (A3C). Demikian juga dengan Deep-Q-Network (DQN), hanya dijelaskan secara singkat di bagian III buku ini.

Kedua, bagian III dari buku ini membahas bidang lain di luar komputer yang berkaitan dengan RL, yaitu Psychology dan Neurosciences. Terus terang kedua bidang ini kurang berguna bagi saya oleh karena itu saya skip-skip saja.

Kesimpulannya, buku ini sangat saya rekomendasikan untuk Anda yang ingin belajar RL. Lima bintang!

starf16starf16starf16starf16starf16

 

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

Blog di WordPress.com.

Atas ↑

%d blogger menyukai ini: