Persamaan Bellman

Persamaan Bellman adalah hubungan rekursif yang dipenuhi oleh fungsi nilai, dan menjadi titik tumpu seluruh algoritma berbasis model di reinforcement learning. Topik ini memperkenalkan dua bentuk persamaan Bellman, yaitu Bellman expectation yang dipenuhi $V^\pi$ dari sebuah kebijakan $\pi$, dan Bellman optimality yang dipenuhi $V^*$ dari kebijakan optimal. Pembaca akan melihat kedua rumus tersebut, lalu mengimplementasikan satu backup Bellman ekspektasi pada gridworld mini dan mencetak nilai sebelum serta sesudah satu sapuan.

Dua persamaan Bellman#

Fungsi nilai state memenuhi dua persamaan rekursif tergantung apakah kebijakan sudah optimal atau belum. Untuk sebuah kebijakan $\pi$ yang tetap, Bellman expectation menyatakan bahwa nilai sebuah state adalah rata-rata atas aksi, ditimbang kebijakan, dari expected reward satu langkah ditambah nilai state berikutnya yang terdiskon:

Bila agen selalu memilih aksi terbaik, $\pi$ digantikan oleh operator $\max_a$, dan persamaannya menjadi Bellman optimality:

Perbedaan antara keduanya berada pada bagian luar penjumlahan. Bellman expectation menjumlahkan atas aksi dengan bobot kebijakan $\pi(a \mid s)$, sedangkan Bellman optimality mengambil aksi yang memberi nilai terbesar. Akibatnya, $V^\pi$ menggambarkan kualitas sebuah kebijakan tertentu, sedangkan $V^*$ menggambarkan kualitas kebijakan terbaik yang dapat dicapai. Karena keduanya rekursif terhadap nilai state lain, perhitungan dilakukan dengan sapuan berulang atas seluruh state.

Mekanisme backup Bellman#

Satu langkah pembaruan nilai disebut backup Bellman. Backup menjumlahkan atas seluruh outcome transisi (next_state, prob, reward) untuk sebuah pasangan $(s, a)$, lalu menggabungkan hasilnya. Pada Bellman expectation, hasil tiap aksi ditimbang dengan $\pi(a \mid s)$ lalu dijumlahkan, sedangkan pada Bellman optimality hasil tiap aksi dibandingkan dan yang terbesar dipakai. Karena setiap backup menggunakan $V$ lawan, kebijakan yang diperbarui hanya stabil setelah seluruh state disapu berulang kali hingga perubahan terbesar di bawah ambang batas. Iterasi ini konvergen karena $\gamma < 1$ membuat operator Bellman bersifat kontraktif pada norma tak hingga.

Satu backup Bellman pada gridworld mini#

Blok berikut mendefinisikan ulang MDP gridworld mini agar berdiri sendiri, memilih kebijakan seragam $\pi(a \mid s) = 0{,}5$, lalu menjalankan satu sapuan backup Bellman ekspektasi. Nilai $V$ dicetak sebelum dan sesudah sapuan tersebut.

import warnings
warnings.filterwarnings("ignore")

# MDP gridworld mini: 4 state (s0..s3), 2 aksi (kiri, kanan)
states = ["s0", "s1", "s2", "s3"]
actions = ["kiri", "kanan"]
gamma = 0.9
transisi = {
    "s0": {"kiri": [("s0", 1.0, 0.0)], "kanan": [("s1", 1.0, 0.0)]},
    "s1": {"kiri": [("s0", 1.0, 0.0)], "kanan": [("s2", 1.0, 0.0)]},
    "s2": {"kiri": [("s1", 1.0, 0.0)], "kanan": [("s3", 0.8, 1.0), ("s2", 0.2, 0.0)]},
    "s3": {"kiri": [("s3", 1.0, 0.0)], "kanan": [("s3", 1.0, 0.0)]},
}

# Satu backup Bellman ekspektasi pada kebijakan seragam pi(a|s)=0.5
pi = {s: {a: 0.5 for a in actions} for s in states}

V = {s: 0.0 for s in states}
print("V sebelum satu sapuan Bellman:")
for s in states:
    print(f"  V({s}) = {V[s]:.4f}")

newV = {}
for s in states:
    total = 0.0
    for a in actions:
        q = 0.0
        for ns, prob, r in transisi[s][a]:
            q += prob * (r + gamma * V[ns])
        total += pi[s][a] * q
    newV[s] = total

V = newV
print()
print("V setelah satu sapuan Bellman:")
for s in states:
    print(f"  V({s}) = {V[s]:.4f}")

V sebelum satu sapuan Bellman:
  V(s0) = 0.0000
  V(s1) = 0.0000
  V(s2) = 0.0000
  V(s3) = 0.0000

V setelah satu sapuan Bellman:
  V(s0) = 0.0000
  V(s1) = 0.0000
  V(s2) = 0.4000
  V(s3) = 0.0000

Alasan hanya s2 yang berubah#

Hanya $V(s_2)$ yang berubah dari nol menjadi 0,4000 setelah satu sapuan. Penyebabnya, state $s_0$, $s_1$, dan $s_3$ hanya memiliki transisi dengan reward nol pada langkah pertama, sehingga backup menghasilkan nol. State $s_2$ memiliki transisi kanan yang menuju $s_3$ dengan reward 1,0 pada peluang 0,8. Pada kebijakan seragam, kontribusi aksi kanan ke backup $s_2$ adalah $0{,}5 \times [0{,}8 \times (1{,}0 + 0{,}9 \times 0) + 0{,}2 \times (0{,}0 + 0{,}9 \times 0)] = 0{,}5 \times 0{,}8 = 0{,}4$. Karena $V(s_3)$ masih nol pada sapuan pertama, hasil backup $s_2$ menjadi tepat 0,4000. Sapuan kedua akan menularkan nilai $s_2$ ke $s_1$, sapuan ketiga ke $s_0$, dan seterusnya hingga nilai menyebar ke seluruh state.

Kesalahan umum#

Mencampur $\max_a$ dan $\sum_a \pi(a \mid s)$. Penyebabnya, kedua persamaan Bellman sekilas mirip sehingga operator luar tertukar. Akibatnya, kode yang seharusnya mengevaluasi kebijakan malah menghitung nilai optimal, atau sebaliknya. Perbaikannya, tetapkan satu nama fungsi terpisah untuk backup ekspektasi dan backup optimal, dan uji bahwa hasil backup ekspektasi selalu kurang dari atau sama dengan hasil backup optimal pada state yang sama.

Mengakses $V(s')$ yang belum diperbarui dalam satu sapuan. Penyebabnya, backup membaca dan menulis $V$ pada objek yang sama secara langsung. Akibatnya, urutan pemrosesan state memengaruhi hasil, sehingga nilai tidak reproduksibel lintas urutan. Perbaikannya, simpan nilai baru pada objek sementara newV, lalu tukar referensi setelah seluruh state selesai disapu.

Ringkasan#

• Bellman expectation $V^\pi(s)=\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma V^\pi(s')]$ dipenuhi fungsi nilai sebuah kebijakan tertentu.
• Bellman optimality $V^*(s)=\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma V^*(s')]$ dipenuhi fungsi nilai kebijakan optimal.
• Backup Bellman menggabungkan outcome transisi (next_state, prob, reward) per pasangan $(s,a)$, lalu menimbang aksi atau mengambil maksimumnya.
• Satu sapuan hanya menyebarkan informasi satu langkah, sehingga konvergensi memerlukan sapuan berulang yang dijamin oleh sifat kontraktif operator Bellman saat $\gamma < 1$.

Referensi#

• Reinforcement Learning: An Introduction, ch. 4 — Sutton & Barto — Derivasi persamaan Bellman ekspektasi dan optimalitas pada bab “Dynamic Programming”.
• Bellman equation — Wikipedia — Sifat kontraktif operator Bellman dan syarat konvergensi pada proses keputusan Markov.