Teori : Pengenalan Bellman Equation

Untuk mengikuti modul ini, diharapkan Anda sudah memahami konsep reinforcement learning.

Untuk memahami Markov Decision Process dan Q-Learning, kita perlu memahami dulu Bellman Equation.

Jika Anda sudah memahami Bellman Equation, modul ini bisa dilewati.

Bellman equation menggunakan konsep state, action, reward dan gamma untuk melakukan perhitungan value state.

• state : kondisi yang dihadapi agent.
• action : aksi yang dapat dilakukan oleh agent.
• reward: reward yang dapat diperoleh agent dalam melakukan aksi.
• gamma: discount value dari suatu state.

Berikut formula dari Bellman equation

• V(s) adalah nilai dari state saat ini.
• s’ adalah state berikutnya.
• gamma adalah konstan value yang digunakan untuk menghitung diskon.

Jadi Bellman equation bertujuan menghitung state saat ini dengan mendapatkan nilai maksimum dari suatu aksi berdasarkan nilai state berikutnya.

Mari lihat perbandingan dibawah antara agent tanpa Bellman dan agen yang menggunakan Bellman.

Contoh, ada agent dalam sebuah mase, memiliki aksi yang dapat dilakukan, yaitu bergerak keatas, kebawah, kekiri dan kekanan.

Kemudian, dengan aturan block putih saja yang bisa dilalui, block hijau adalah block reward dengan nilai 1 dan block merah adalah block punishment dengan nilai -1.

Agent akan mencoba melakukan berbagai macam aksi, dengan tujuan mendapatkan reward terbesar, yaitu mencapai block reward.

Untuk mengetahui urutan aksi dalam mencapai block reward, agent akan memberi nilai dari suatu state.

Tanpa Bellman Equation

Jika tanpa menggunakan Bellman Equation, maka agent akan memberi nilai semua block putih dengan nilai yang sama.

Hal ini akan membuat agent tidak dapat menyelesaikan maze dengan mencapai block reward, karena pada state tertentu, agent tidak dapat mengetahui harus mengambil aksi yang mana.

Pada contoh gambar dibawah, agent tidak akan mengetahui, pada state tersebut apakah harus kekanan atau kebawah.

Menggunakan Bellman Equation

Contoh menggunakan nilai gamma = 0.9. Dengan menggunakan formula Bellman diatas, maka setiap block akan memiliki nilai berbeda.

Contoh perhitungan

block v=1, agent akan mendapatkan reward jika bergerak kekanan, yaitu, nilai 1.

v(s) = Max(R(s,a) + (discount * s')
v(s) = 1 + 0.9 * 0
v(s) = 1

block v=0.9, nilai reward tidak ada , namun nilai maksimum dapat diperoleh dengan bergerak kekanan, yaitu

v(s) = Max(R(s,a) + (discount * s')
v(s) = 0 + 0.9 * 1
v(s) = 0.9

Dengan kondisi ini, agent akan memiliih aksi yang memberikan value state lebih besar.

Jadi saat agent diposisikan di state dengan v=0.81, agent akan memilih aksi bergerak kekanan (0.9), karena nilainya lebih besar dari pada bergerak kebawah (0.73)

Plan

Setelah setiap state dihitung, kita dapat menentukan Plan, yaitu bagaimana agent akan melakukan aksi berdasarkan nilai setiap state.

Jika Anda berminat untuk mempelajari lebih mendalam mengenai Dynamic Programming, berikut white paper yang dibuat oleh Bellman, www.rand.org/content/dam/rand/pubs/papers/2008/P550.pdf