Program Studi Bisnis Digital • FEB UNDIP

Pembelajaran Dalam dan Pembelajaran Mesin

Pertemuan 8 — Reinforcement Learning: MDP dan Bellman Equations

Bagaimana mesin belajar mengambil keputusan berurutan lewat coba-coba dan hadiah — dari Markov Decision Process sampai Persamaan Bellman.

RPS MINGGU 9 • 2×50 MENIT

Selamat pagi, Anda semua. Hari ini kita masuk ke bab yang paling berbeda dari semua yang sudah kita pelajari: reinforcement learning, atau pembelajaran penguatan. Kalau minggu-minggu lalu kita belajar regresi dan SVM yang butuh data berlabel jawaban benar-salah, hari ini kita bicara tentang mesin yang belajar dari konsekuensi tindakannya sendiri — persis seperti aplikasi Gojek yang belajar rute tercepat lewat jutaan perjalanan, atau bot yang belajar main game dengan coba-coba sampai menang. Kita akan bedah dua fondasi matematis di baliknya: Markov Decision Process, kerangka untuk memodelkan keputusan berurutan, dan Persamaan Bellman, rumus yang membuat komputer bisa menghitung strategi optimal. Siapkan diri Anda, karena ini pertemuan terakhir sebelum kita berpindah dari "algoritma inti" ke dunia data mining di pertemuan sembilan.

Tujuan Pembelajaran Hari Ini

Setelah pertemuan ini, Anda diharapkan mampu menjelaskan konsep reinforcement learning dan menerapkannya pada kasus keputusan sederhana. Secara rinci:

CAPAIAN 1

KONSEP RL

Menjelaskan komponen agent, environment, state, action, reward dan bedanya dengan supervised/unsupervised learning.

CAPAIAN 2

MDP

Memodelkan masalah keputusan sebagai Markov Decision Process: state, action, transisi, reward, discount factor.

CAPAIAN 3

BELLMAN

Menghitung value function memakai Persamaan Bellman secara manual, langkah demi langkah.

CAPAIAN 4

EKSPLORASI

Memahami trade-off eksplorasi vs eksploitasi dan aplikasi RL di bisnis digital.

Bayangkan Anda Melatih Kurir Baru Tanpa Instruksi

Sebuah startup logistik di Semarang punya driver baru yang tidak diberi peta rute — hanya diberi tahu: "Antar tepat waktu, dapat bonus. Telat, dapat teguran." Setelah ratusan pengiriman, driver ini belajar sendiri rute tercepat, jam macet mana yang dihindari, dan pelanggan mana yang butuh perhatian ekstra.

TANPA LABEL

COBA-COBA

Tidak ada "jawaban benar" diberikan di awal — driver mencoba rute, lalu belajar dari hasilnya.

UMPAN BALIK

REWARD

Bonus (reward positif) atau teguran (reward negatif) menjadi sinyal belajar satu-satunya.

JANGKA PANJANG

STRATEGI

Tujuannya bukan bonus hari ini saja, tapi total bonus terbaik selama berbulan-bulan bekerja.

Inilah Reinforcement Learning (RL): mesin (atau driver) belajar strategi optimal lewat interaksi berulang dengan lingkungan, dipandu oleh sinyal hadiah — bukan dari data berlabel seperti supervised learning yang sudah kita pelajari minggu lalu.

Analogi kurir ini penting supaya Anda tidak salah kira RL sama dengan yang kita bahas dua minggu terakhir, yaitu regresi atau SVM. Di sana, kita punya data historis lengkap dengan jawaban benarnya — misalnya harga rumah yang sudah diketahui. Di RL, tidak ada guru yang memberi jawaban benar di setiap langkah. Driver kita hanya tahu hasilnya belakangan: dapat bonus atau teguran. Yang menarik, driver yang cerdas tidak cuma mengejar bonus hari ini, tapi mempertimbangkan dampak jangka panjang — misalnya, dia mungkin rela sedikit telat sekali demi membangun hubungan baik dengan pelanggan yang akan memberi tip besar bulan depan. Pola pikir "optimalkan total hadiah jangka panjang, bukan hadiah sesaat" inilah jantung dari reinforcement learning, dan akan kita formalkan secara matematis sepanjang pertemuan ini.

Bagian 1 dari 4

Anatomi Reinforcement Learning

Agent, environment, state, action, reward — lima kata yang akan terus kita pakai sepanjang pertemuan ini.

Lima Komponen Inti Reinforcement Learning

Setiap masalah RL, sekecil apa pun, selalu bisa dipecah menjadi lima elemen berikut:

KOMPONEN

Agent — pengambil keputusan (mis. robot gudang, bot trading).
Environment — dunia tempat agent beroperasi (mis. layout gudang).
State (s) — kondisi saat ini (mis. posisi robot di rak ke-5).
Action (a) — pilihan yang bisa diambil (mis. maju, belok, ambil barang).
Reward (r) — angka umpan balik (mis. +10 jika barang terambil benar).

Di Mana Posisi RL di Antara Jenis Pembelajaran Lain?

Kita sudah bahas unsupervised (K-means, klasterisasi) dan supervised (regresi, SVM) di pertemuan sebelumnya. RL adalah kategori ketiga dengan karakter yang berbeda.

Aspek	Supervised	Unsupervised	Reinforcement
Data	Berlabel (X, y)	Tanpa label	Interaksi + reward
Tujuan	Prediksi akurat	Temukan pola/struktur	Maksimalkan reward jangka panjang
Umpan balik	Jawaban benar langsung	Tidak ada	Reward tertunda (delayed)
Contoh	Prediksi harga rumah	Segmentasi pelanggan	Bot trading, robot navigasi

Perbedaan paling krusial: reward di RL sering tertunda (delayed reward) — tindakan sekarang baru terlihat hasilnya beberapa langkah kemudian. Ini yang membuat RL secara matematis lebih rumit dari supervised learning.

Tabel ini penting untuk meluruskan pemahaman Anda, karena mahasiswa baru sering mengira RL hanyalah "supervised learning versi lain". Padahal bedanya fundamental: di supervised learning, begitu model memprediksi, kita langsung tahu benar atau salah karena punya label. Di RL, agent bisa saja mengambil sepuluh langkah action berturut-turut, dan baru di langkah kesebelas ia tahu apakah strategi itu bagus atau buruk — itulah yang disebut delayed reward atau reward tertunda. Bayangkan bot trading saham BBCA: ia membeli hari ini, tapi baru tahu keputusan itu untung atau rugi beberapa hari kemudian setelah menjual. Kerumitan menghubungkan action masa lalu dengan reward yang baru muncul kemudian, itulah yang membuat RL butuh kerangka matematis khusus bernama Markov Decision Process yang akan kita bahas selanjutnya.

Bagian 2 dari 4

Markov Decision Process (MDP)

Kerangka matematis formal untuk membingkai masalah keputusan berurutan.

MDP: Lima Elemen Formal (S, A, P, R, γ)

MDP (Markov Decision Process) adalah cara formal menuliskan masalah RL memakai lima komponen matematis:

S — STATE SPACE

Himpunan Kondisi

Semua kemungkinan kondisi yang bisa dialami agent, mis. semua rak di gudang.

A — ACTION SPACE

Himpunan Aksi

Semua pilihan tindakan yang tersedia di setiap state, mis. maju/mundur/kiri/kanan.

P — TRANSISI

P(s'|s,a)

Peluang berpindah ke state baru s' setelah mengambil action a di state s.

R & γ

Reward & Discount

R = reward yang diterima; γ (gamma, 0-1) = seberapa besar bobot reward masa depan.

Coba Sendiri: Eksplorasi MDP dan Persamaan Bellman

Ubah reward dan discount factor gamma pada MDP sederhana, amati bagaimana value function tiap state dihitung lewat persamaan Bellman.

Properti Markov: "Masa Depan Hanya Bergantung Saat Ini"

Nama "Markov" berasal dari properti Markov: peluang state berikutnya hanya bergantung pada state sekarang, bukan seluruh riwayat sebelumnya.

P(s_t+1 | s_t, a_t) = P(s_t+1 | s_t, a_t, s_t-1, ..., s₀)

Analogi: posisi bidak catur sekarang sudah cukup untuk menentukan langkah selanjutnya — tidak peduli bagaimana urutan langkah yang membawa bidak sampai ke posisi itu. Ini yang disebut sifat "tanpa memori" (memoryless).

Konsekuensinya: state harus dirancang lengkap agar mencakup semua informasi relevan — kalau tidak, properti Markov gagal dan model jadi tidak akurat.

Discount Factor (γ): Seberapa Peduli Agent pada Masa Depan?

γ (gamma) adalah angka antara 0 dan 1 yang menentukan bobot reward masa depan dibanding reward sekarang.

Return G_t = r_t + γr_t+1 + γ²r_t+2 + ... = ∑ γ^k r_t+k

γ MENDEKATI 0

MYOPIC

Agent hanya peduli reward saat ini — seperti kurir yang cuma kejar bonus antar hari ini, abai risiko besok.

γ MENDEKATI 1

FAR-SIGHTED

Agent mempertimbangkan reward jauh ke depan — seperti investor saham BEI yang berpikir jangka panjang.

Discount factor gamma ini analoginya mirip dengan bunga majemuk, tapi berjalan mundur — ia mengecilkan nilai reward yang datangnya makin jauh di masa depan. Kenapa perlu dikecilkan? Karena secara intuitif, hadiah seratus ribu rupiah yang kita terima sekarang biasanya dianggap lebih berharga daripada janji hadiah seratus ribu rupiah lima tahun lagi — ada faktor ketidakpastian. Kalau gamma mendekati nol, agent menjadi seperti pedagang kaki lima yang hanya mikirin untung hari ini, tidak peduli reputasi jangka panjang. Kalau gamma mendekati satu, agent berpikir seperti investor BEI yang membeli saham Astra dengan horizon lima sampai sepuluh tahun, rela menahan sabar demi hasil besar di masa depan. Pemilihan gamma yang tepat sangat tergantung konteks bisnis: untuk rekomendasi produk e-commerce yang berubah cepat, gamma biasanya lebih kecil; untuk strategi investasi jangka panjang, gamma dipasang mendekati satu.

Policy (π) dan Value Function: Dua Alat Ukur Strategi

Setelah MDP terdefinisi, agent butuh strategi (policy) dan cara mengukur seberapa bagus strategi itu.

POLICY (π)

Aturan yang memetakan state ke action: "kalau di state s, ambil action a".

Bisa deterministik (satu aksi pasti)
Bisa stokastik (peluang tiap aksi)

VALUE FUNCTION V(s)

Estimasi total reward jangka panjang jika mulai dari state s dan mengikuti policy π.

V tinggi = state "menguntungkan"
V rendah = state "merugikan"

Tujuan akhir RL: menemukan policy optimal (π*) yang memaksimalkan value function di setiap state. Persamaan Bellman (slide berikutnya) adalah alat untuk menghitung V(s) ini secara sistematis.

Policy dan value function adalah dua sisi mata uang yang sama. Policy menjawab pertanyaan "apa yang harus saya lakukan", sedangkan value function menjawab "seberapa bagus posisi saya sekarang". Sebagai analogi bisnis, bayangkan seorang manajer toko online yang punya aturan baku: kalau stok menipis, segera re-order — itu adalah policy-nya. Value function-nya adalah estimasi keuntungan total jangka panjang jika toko itu terus mengikuti aturan tersebut. Tujuan akhir setiap algoritma RL adalah menemukan policy optimal, yaitu aturan terbaik yang memaksimalkan value function di semua kondisi. Nah, alat matematis untuk menghitung value function ini secara sistematis punya nama sendiri: Persamaan Bellman, yang akan kita bedah habis-habisan mulai slide berikutnya karena inilah inti perhitungan RL.

Bagian 3 dari 4

Persamaan Bellman: Menghitung dari Nol

Dua kasus perhitungan langkah-demi-langkah agar rumus ini terasa nyata, bukan sekadar simbol.

Persamaan Bellman untuk Value Function

Ide inti: nilai sebuah state = reward sekarang + nilai state berikutnya yang didiskon.

V(s) = R(s) + γ × V(s')

Untuk kasus dengan beberapa state tujuan yang mungkin (peluang transisi P), rumus lengkapnya:

V(s) = R(s) + γ × ∑ P(s'|s,a) × V(s')

Rumus ini disebut rekursif: nilai satu state didefinisikan lewat nilai state lain. Karena itu, cara praktis menghitungnya adalah mulai dari state paling akhir (yang nilainya sudah pasti), lalu mundur ke state sebelumnya — seperti akan kita praktikkan di dua slide berikutnya.

Mari kita bedah rumus ini kata demi kata. V(s) adalah nilai yang ingin kita cari, yaitu seberapa bagus berada di state s. R(s) adalah reward langsung yang didapat di state itu. Bagian gamma dikali V(s') adalah nilai state berikutnya, tapi didiskon karena itu terjadi di masa depan. Kalau ada beberapa kemungkinan state tujuan — misalnya karena ada faktor acak seperti robot yang kadang selip — kita jumlahkan semua kemungkinan itu dikalikan peluangnya masing-masing, itulah rumus kedua dengan simbol sigma dan P. Yang membuat rumus ini unik adalah sifat rekursifnya: untuk tahu nilai satu state, kita butuh nilai state lain, yang mungkin juga butuh nilai state lainnya lagi. Solusinya adalah mulai menghitung dari ujung — state terakhir yang nilainya sudah pasti diketahui — lalu mundur selangkah demi selangkah. Ini persis yang akan kita praktikkan bersama di dua contoh soal berikutnya.

Hitung dari Nol #1: Value Function Robot Gudang (3 State Linear)

Robot bergerak di lorong gudang 1 arah: State A → B → C (rak barang, C = reward akhir 100). γ = 0,9. Tidak ada reward di A dan B (R=0). Hitung V(C), V(B), V(A) mundur dari akhir.

Langkah	Perhitungan	Nilai
1. V(C) — state akhir	Reward langsung diterima penuh, tidak ada state setelahnya	V(C) = 100
2. V(B) — satu langkah sebelum C	R(B) + γ × V(C) = 0 + 0,9 × 100	V(B) = 90
3. V(A) — dua langkah sebelum C	R(A) + γ × V(B) = 0 + 0,9 × 90	V(A) = 81

HASIL AKHIR

V(A)=81 · V(B)=90 · V(C)=100

Nilai menurun makin jauh dari sumber reward — konsisten dengan makna discount factor.

Hitung dari Nol #2: Value dengan Peluang Transisi Tidak Pasti

Bot rekomendasi Tokopedia di state S bisa pilih action "tampilkan produk X": 70% peluang pelanggan klik (reward 20), 30% peluang tidak klik (reward 0). Tidak ada state lanjutan (episode berakhir). γ = 1 (episode pendek, tanpa masa depan lanjutan).

Langkah	Perhitungan	Nilai
1. Kontribusi hasil "klik"	P(klik) × Reward = 0,7 × 20	14
2. Kontribusi hasil "tidak klik"	P(tidak klik) × Reward = 0,3 × 0	0
3. V(S) = jumlah semua kontribusi	14 + 0	V(S) = 14

HASIL AKHIR

V(S) = 14

Ekspektasi reward memperhitungkan SEMUA kemungkinan hasil, dibobot peluangnya.

Contoh ini berbeda dari yang pertama karena sekarang ada ketidakpastian transisi — persis rumus Bellman kedua yang memakai peluang P(s prima diberi s koma a). Bot rekomendasi tidak pernah tahu pasti apakah pelanggan akan klik produk yang ditampilkan, ia hanya tahu berdasarkan data historis bahwa peluang klik sekitar 70 persen. Kita hitung kontribusi masing-masing kemungkinan: kalau klik terjadi, dengan peluang 0,7 dan reward 20, kontribusinya 14. Kalau tidak klik, dengan peluang 0,3 dan reward nol, kontribusinya nol. Jumlahkan keduanya, dapat value function sebesar 14. Angka 14 ini bukan reward yang pasti didapat, melainkan ekspektasi rata-rata jika action ini diulang berkali-kali — inilah yang dimaksimalkan agent ketika memilih antara beberapa pilihan produk yang mungkin ditampilkan ke pelanggan.

Bellman Optimality: Memilih Action Terbaik

Kalau agent punya beberapa pilihan action di satu state, Persamaan Bellman Optimality memilih action yang memaksimalkan value:

V*(s) = max_a [ R(s,a) + γ × ∑ P(s'|s,a) × V*(s') ]

CONTOH: BOT REKOMENDASI

Action 1 (tampilkan produk X): V = 14 (dihitung slide sebelumnya)
Action 2 (tampilkan produk Y): V = 9
Action 3 (tampilkan produk Z): V = 21

PILIHAN OPTIMAL

PRODUK Z

max(14, 9, 21) = 21 → policy optimal π*(s) memilih action dengan value tertinggi.

Bedanya dengan rumus Bellman biasa yang tadi kita hitung, di sini ada tambahan operator "max" atau maksimum di depan rumus. Artinya, kalau agent punya beberapa pilihan action di satu state yang sama, ia harus menghitung value dari setiap pilihan, lalu memilih yang paling besar. Contohnya bot rekomendasi Tokopedia yang bisa menampilkan tiga produk berbeda ke satu pelanggan: produk X menghasilkan value 14 seperti yang kita hitung tadi, produk Y menghasilkan value 9, dan produk Z menghasilkan value 21. Karena tujuannya memaksimalkan value jangka panjang, policy optimal akan memilih menampilkan produk Z. Inilah yang sebenarnya terjadi di balik layar sistem rekomendasi e-commerce besar: bukan menampilkan produk secara acak, melainkan memilih yang secara matematis diprediksi memberi total reward — klik, pembelian, retensi pelanggan — paling tinggi.

Dilema Eksplorasi vs Eksploitasi

Agent RL selalu menghadapi trade-off ini di setiap keputusan:

EKSPLOITASI (EXPLOIT)

PAKAI YANG TERBUKTI

Pilih action dengan value tertinggi yang sudah diketahui. Risiko: melewatkan pilihan lebih bagus yang belum pernah dicoba.

EKSPLORASI (EXPLORE)

COBA HAL BARU

Coba action yang belum banyak dicoba, demi info baru. Risiko: reward jangka pendek lebih rendah.

Contoh: Netflix (atau layanan streaming lokal) yang selalu merekomendasikan genre favorit Anda (eksploitasi) tidak pernah tahu apakah Anda akan suka genre baru — sesekali sistem perlu "coba-coba" (eksplorasi) untuk memperkaya data preferensi Anda.

Bayangkan Anda punya lima warung makan langganan di dekat kampus, dan salah satunya paling enak menurut pengalaman Anda selama ini. Eksploitasi berarti Anda terus makan di warung favorit itu karena sudah terbukti enak. Tapi kalau Anda selalu melakukan itu, Anda tidak akan pernah tahu apakah ada warung keenam yang mungkin lebih enak lagi — itulah kenapa sesekali eksplorasi diperlukan, mencoba warung baru meski berisiko kecewa. Algoritma RL menghadapi dilema yang sama persis di setiap pengambilan keputusan. Sistem rekomendasi Spotify atau Netflix, misalnya, tidak akan selalu menyodorkan lagu atau film yang mirip dengan yang sudah Anda sukai — sesekali mereka menyisipkan rekomendasi yang agak berbeda, untuk mengeksplorasi apakah selera Anda lebih luas dari yang terlihat, dan hasil eksplorasi ini pada akhirnya memperbaiki akurasi rekomendasi jangka panjang.

Reinforcement Learning di Dunia Bisnis Digital

Konsep MDP dan Bellman yang kita hitung hari ini bukan sekadar teori — ini fondasi sistem-sistem berikut:

E-COMMERCE

DYNAMIC PRICING

Menentukan harga optimal secara real-time berdasarkan respons pembeli (mis. strategi diskon flash sale).

RIDE-HAILING

ALOKASI DRIVER

Menempatkan driver Gojek/Grab di lokasi dengan ekspektasi permintaan tertinggi (surge area).

KEUANGAN

ALGORITMA TRADING

Menentukan kapan beli/jual saham (mis. BBCA) untuk memaksimalkan return jangka panjang.

Benang merah ketiganya: setiap keputusan (action) di setiap kondisi pasar (state) dinilai lewat estimasi reward jangka panjang — persis logika value function yang baru kita hitung manual.

Mari kita hubungkan semua rumus tadi dengan dunia nyata yang relevan untuk mahasiswa bisnis digital. Dynamic pricing di marketplace seperti Shopee menggunakan logika RL untuk menentukan kapan menaikkan atau menurunkan harga demi memaksimalkan total pendapatan, bukan cuma penjualan sesaat. Di industri ride-hailing seperti Gojek, algoritma RL membantu menentukan di area mana driver sebaiknya menunggu, dengan mempertimbangkan ekspektasi permintaan yang berubah-ubah sepanjang hari — ini persis konsep value function yang lebih tinggi di state atau lokasi tertentu. Di dunia keuangan, algoritma trading otomatis memakai kerangka MDP untuk memutuskan kapan membeli atau menjual saham seperti BBCA, dengan mempertimbangkan risiko dan potensi keuntungan jangka panjang, bukan sekadar sinyal harga sesaat. Yang ingin saya tekankan, angka-angka yang tadi kita hitung manual di kertas — value function 81, 90, 100, atau 14 — adalah versi sederhana dari perhitungan yang sebenarnya berjalan di balik layar sistem-sistem raksasa ini, hanya dengan state dan action yang jauh lebih banyak.

Latihan Mandiri: Hitung Value Function Anda Sendiri

Kerjakan berpasangan (10 menit). Kasus: Bot customer service punya 3 state linear D → E → F (F = state akhir, reward 50). γ = 0,8. R(D) = R(E) = 0.

INSTRUKSI

Hitung V(F) terlebih dahulu (state akhir).
Hitung V(E) memakai Persamaan Bellman.
Hitung V(D) memakai hasil V(E).
Bandingkan hasil dengan teman sebangku Anda.

PETUNJUK

MUNDUR DARI F

Ikuti pola Hitung dari Nol #1: mulai dari state yang nilainya paling pasti, lalu mundur selangkah demi selangkah.

Kunci jawaban akan dibahas bersama di 5 menit terakhir sesi ini — siapkan hasil hitungan Anda.

Rangkuman & Sebelum Pertemuan Berikutnya

Istilah	Rumus / Arti
MDP	(S, A, P, R, γ) — kerangka formal masalah keputusan berurutan
Value Function V(s)	R(s) + γ × V(s') — estimasi total reward mulai dari state s
Bellman Optimality	V(s) = max_a [R(s,a) + γ × ∑P(s'\|s,a)V(s')]
Eksplorasi vs Eksploitasi	Coba hal baru vs pakai strategi terbukti — trade-off inti RL

MINGGU DEPAN: PERTEMUAN 9

Kita berpindah dari algoritma inti ke Konsep Dasar Data Mining dan Tahapan Proses — bagaimana pola tersembunyi ditemukan dari data mentah skala besar.

TUGAS MANDIRI

SOAL LATIHAN

Selesaikan latihan value function 3-state (slide 19) jika belum tuntas di kelas; bawa jawaban ke pertemuan berikutnya.

Mari kita rangkum perjalanan dua jam kita hari ini sekaligus melihat ke depan. Kita mulai dari memahami bahwa RL adalah kategori pembelajaran ketiga yang berbeda dari supervised dan unsupervised yang sudah Anda kuasai di pertemuan-pertemuan sebelumnya, lalu memformalkannya menjadi Markov Decision Process dengan lima komponennya, dan belajar menghitung value function memakai Persamaan Bellman lewat dua contoh angka nyata yang saya harap sudah melekat di kepala Anda. Tabel di atas adalah cheat sheet yang saya sarankan Anda foto atau catat, karena berisi semua rumus inti hari ini dalam satu tempat. Minggu depan kita berpindah topik cukup signifikan, dari algoritma pembelajaran inti ke dunia data mining, dimulai dengan konsep dasar dan tahapan prosesnya. Sebagai tugas mandiri, pastikan Anda menyelesaikan latihan menghitung value function tiga state tadi jika belum sempat tuntas di kelas, dan jangan sungkan menghubungi saya di forum kelas atau jam konsultasi kalau ada bagian dari Persamaan Bellman yang masih terasa mengambang. Sampai jumpa minggu depan!