KAL
Menu

Iterasi nilai dan kebijakan

Konvergen menuju optimal ketika model diketahui sepenuhnya.

Daftar isi

Topik ini menyatukan kedua operator sebelumnya menjadi dua algoritma lengkap yang menemukan kebijakan optimal ketika model lingkungan diketahui sepenuhnya, yaitu iterasi kebijakan yang berselang-seling evaluasi dan perbaikan, serta iterasi nilai yang memadukan keduanya dalam satu sapuan. Pembaca akan menjalankan iterasi nilai pada gridworld mini, mengamati konvergensi pada sapuan ke-11, lalu menurunkan kebijakan optimal dari nilai yang dihasilkan.

Dua algoritma, satu tujuan#

Iterasi kebijakan mengulang dua langkah secara eksplisit: evaluasi kebijakan sampai VπV^\pi konvergen, lalu perbaikan kebijakan yang menghasilkan π′\pi'. Pasangan ini diulang hingga perbaikan tidak lagi mengubah kebijakan, yang berarti π\pi sudah optimal. Jaminannya datang dari teorema perbaikan kebijakan, yang menyatakan bahwa setiap perbaikan tidak menurunkan nilai, sehingga pada lingkungan dengan banyak state berhingga, barisan kebijakan harus berhenti pada kebijakan optimal dalam jumlah langkah berhingga.

Iterasi nilai menggabungkan kedua langkah menjadi satu sapuan yang langsung memakai operator max⁡a\max_a. Alih-alih menyelesaikan VπV^\pi sampai konvergen sebelum memperbarui kebijakan, iterasi nilai memperbarui nilai tiap state dengan aksi terbaik saat ini, sehingga evaluasi dan perbaikan terjadi serempak. Konvergensinya tidak lagi bergantung pada kebijakan yang berhenti berubah, melainkan pada nilai yang berhenti berubah, yang dijamin oleh sifat kontraktif operator Bellman optimality ketika γ<1\gamma < 1.

Iterasi nilai pada gridworld mini#

Berkas value_iteration.py berikut menjalankan iterasi nilai penuh pada gridworld mini, dengan ambang batas θ=10−6\theta = 10^{-6}. Setelah nilai konvergen, kebijakan optimal diturunkan sebagai kebijakan serakah terhadap nilai akhir.

python value_iteration.py 
import warnings
warnings.filterwarnings("ignore")

# MDP gridworld mini yang sama dengan topik sebelumnya.
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)]},
}

theta = 1e-6
V = {s: 0.0 for s in states}

# Iterasi nilai: ulang backup optimal sampai konvergen.
for sapuan in range(1, 1001):
    delta = 0.0
    newV = {}
    for s in states:
        q_a = []
        for a in actions:
            q = 0.0
            for ns, prob, r in transisi[s][a]:
                q += prob * (r + gamma * V[ns])
            q_a.append(q)
        v_baru = max(q_a)
        newV[s] = v_baru
        delta = max(delta, abs(v_baru - V[s]))
    V = newV
    if delta < theta:
        print(f"konvergen pada sapuan ke-{sapuan}")
        break

# Kebijakan greedy final dari V*.
print("V* (iterasi nilai):")
for s in states:
    print(f"  V*({s}) = {V[s]:.4f}")
print()
print("kebijakan optimal pi* (greedy terhadap V*):")
for s in states:
    q_a = {}
    for a in actions:
        q = 0.0
        for ns, prob, r in transisi[s][a]:
            q += prob * (r + gamma * V[ns])
        q_a[a] = q
    a_baik = max(q_a, key=lambda a: (q_a[a], a == "kanan"))
    print(f"  pi*({s}) = {a_baik}  (Q: {q_a})")
text Keluaran 
konvergen pada sapuan ke-11
V* (iterasi nilai):
  V*(s0) = 0.7902
  V*(s1) = 0.8780
  V*(s2) = 0.9756
  V*(s3) = 0.0000

kebijakan optimal pi* (greedy terhadap V*):
  pi*(s0) = kanan  (Q: {'kiri': 0.7112193711181243, 'kanan': 0.790243874223625})
  pi*(s1) = kanan  (Q: {'kiri': 0.7112193711181243, 'kanan': 0.8780487748447251})
  pi*(s2) = kanan  (Q: {'kiri': 0.790243874223625, 'kanan': 0.9756097549689451})
  pi*(s3) = kanan  (Q: {'kiri': 0.0, 'kanan': 0.0})

Membaca konvergensi#

Iterasi nilai konvergen pada sapuan ke-11, yang berarti informasi reward 1,0 di s3s_3 memerlukan sekitar sepuluh sapuan untuk menyebar penuh melintasi tiga state dan terdiskon kembali hingga di bawah θ\theta. Nilai V∗V^* yang dihasilkan identik dengan VπV^\pi pada topik sebelumnya, yang memperlihatkan bahwa kebijakan kanan saja memang sudah optimal. Pada tiap state, aksi kanan memberi QQ lebih besar kecuali di s3s_3 di mana kedua aksi bernilai nol karena tidak ada transisi maupun reward keluar.

Pemisahan iterasi nilai dan iterasi kebijakan terutama bersifat praktis. Iterasi kebijakan memerlukan evaluasi penuh pada setiap putaran, yang mahal pada lingkungan besar, sedangkan iterasi nilai melakukan satu sapuan per putaran tetapi biasanya membutuhkan lebih banyak putaran. Keduanya menuju kebijakan optimal yang sama, sehingga pilihan antara keduanya didasarkan pada biaya per sapuan versus jumlah sapuan, bukan pada hasil akhir.

Kesalahan umum#

Memakai ambang batas yang terlalu longgar. Penyebabnya, θ\theta yang besar membuat iterasi berhenti sebelum nilai benar-benar konvergen. Akibatnya, kebijakan serakah yang diturunkan dapat keliru pada state yang nilai minimumnya sensitif. Perbaikannya, pakai θ\theta yang jauh lebih kecil dari skala reward, misalnya 10−610^{-6} untuk reward berskala satu.

Mengabaikan diskon pada lingkungan episodik. Penyebabnya, γ=1\gamma=1 dianggap aman karena episodenya berhenti. Akibatnya, sifat kontraktif operator Bellman hilang dan iterasi nilai tidak menjamin konvergen, terutama bila ada siklus dengan reward positif. Perbaikannya, tetapkan γ<1\gamma < 1 bahkan pada lingkungan episodik, agar jaminan konvergensi tetap berlaku.

Ringkasan#

  • Iterasi kebijakan berselang-seling evaluasi dan perbaikan kebijakan hingga kebijakan berhenti berubah, yang menandakan keoptimalan.
  • Iterasi nilai memadukan kedua operator dalam satu sapuan dengan operator max⁡a\max_a, dan konvergen karena sifat kontraktif operator Bellman optimality saat γ<1\gamma < 1.
  • Pada gridworld mini, iterasi nilai konvergen pada sapuan ke-11 dan menghasilkan V∗V^* yang identik dengan hasil evaluasi kebijakan kanan, yang menegaskan bahwa kebijakan tersebut memang optimal.

Referensi#