Evaluasi dan perbaikan kebijakan

Topik ini memecah pekerjaan pemrograman dinamis menjadi dua operator yang berbeda, yaitu evaluasi kebijakan yang menghitung $V^\pi$ untuk sebuah kebijakan tetap, dan perbaikan kebijakan yang membuat kebijakan serakah (greedy) terhadap nilai tersebut. Pembaca akan melihat kedua operator dijalankan bergantian pada gridworld mini, mengamati kapan kebijakan berubah dan kapan tidak, lalu menaruh keduanya sebagai bahan penyusun iterasi kebijakan pada topik selanjutnya.

Dua operator yang berbeda#

Pemrograman dinamis memisahkan dua pertanyaan yang sering bercampur, yaitu seberapa baik sebuah kebijakan dan mana kebijakan yang lebih baik. Evaluasi kebijakan menjawab pertanyaan pertama dengan menyelesaikan persamaan Bellman ekspektasi untuk sebuah $\pi$ yang tetap, sehingga yang dihitung murni $V^\pi$. Operator ini bersifat pasif terhadap kebijakan, sebab $\pi$ tidak berubah selama perhitungan berlangsung. Hasilnya adalah gambaran kualitas kebijakan tersebut, bukan kebijakan baru.

Perbaikan kebijakan menjawab pertanyaan kedua. Diberikan $V^\pi$, operator ini menghitung $Q^\pi(s,a)=\sum_{s',r}p(s',r\mid s,a)[r+\gamma V^\pi(s')]$ untuk setiap aksi, lalu memilih aksi yang memberi nilai terbesar pada tiap state. Kebijakan hasil perbaikan adalah kebijakan serakah terhadap $V^\pi$, yang nilainya paling tidak sama dengan $\pi$ lama menurut teorema perbaikan kebijakan. Bila kebijakan serakah berbeda dari $\pi$ lama, kualitasnya meningkat, dan bila identik, $\pi$ sudah optimal.

Satu putaran evaluasi lalu perbaikan#

Berkas evaluasi_perbaikan.py berikut memakai gridworld mini dari topik persamaan Bellman, menetapkan kebijakan awal yang selalu memilih aksi kanan, lalu menjalankan evaluasi kebijakan sampai konvergen, dilanjutkan satu langkah perbaikan. Laporan yang dicetak memperlihatkan nilai akhir dan apakah kebijakan berubah.

import warnings
warnings.filterwarnings("ignore")

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

# Kebijakan acak awal: selalu 'kanan' (tidak optimal, hanya contoh).
pi = {s: {a: (1.0 if a == "kanan" else 0.0) for a in actions} for s in states}


def backup_nilai(V, pi, gamma, theta=1e-6, max_sapuan=1000):
    """Evaluasi kebijakan: sapuan penuh sampai perubahan terbesar di bawah theta."""
    for _ in range(max_sapuan):
        delta = 0.0
        newV = {}
        for s in states:
            v = 0.0
            for a in actions:
                q = 0.0
                for ns, prob, r in transisi[s][a]:
                    q += prob * (r + gamma * V[ns])
                v += pi[s][a] * q
            newV[s] = v
            delta = max(delta, abs(v - V[s]))
        V = newV
        if delta < theta:
            break
    return V


def perbaiki_kebijakan(V, gamma):
    """Greedy terhadap V: pilih aksi dengan Q(s,a) terbesar."""
    pi_baru = {}
    berubah = False
    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"))
        pi_baru[s] = {a: (1.0 if a == a_baik else 0.0) for a in actions}
        if pi_baru[s] != pi[s]:
            berubah = True
    return pi_baru, berubah


V = {s: 0.0 for s in states}
V = backup_nilai(V, pi, gamma)
print("V setelah evaluasi kebijakan (kanan saja):")
for s in states:
    print(f"  V({s}) = {V[s]:.4f}")

pi_baru, berubah = perbaiki_kebijakan(V, gamma)
print()
print("kebijakan setelah satu kali perbaikan:")
for s in states:
    a_baik = max(pi_baru[s], key=lambda a: pi_baru[s][a])
    print(f"  pi({s}) = {a_baik}")
print()
print("kebijakan berubah:", berubah)

V setelah evaluasi kebijakan (kanan saja):
  V(s0) = 0.7902
  V(s1) = 0.8780
  V(s2) = 0.9756
  V(s3) = 0.0000

kebijakan setelah satu kali perbaikan:
  pi(s0) = kanan
  pi(s1) = kanan
  pi(s2) = kanan
  pi(s3) = kanan

kebijakan berubah: False

Membaca keluaran#

Nilai $V^\pi$ setelah evaluasi meningkat sepanjang jalur menuju tujuan: $V(s_2)=0{,}9756$ paling tinggi karena reward 1,0 berjarak satu langkah, sedangkan $V(s_0)=0{,}7902$ terdiskon sepanjang tiga langkah menuju $s_3$. State $s_3$ bernilai nol karena tidak ada reward maupun transisi keluar. Kebijakan serakah terhadap nilai ini ternyata identik dengan kebijakan awal yang selalu memilih kanan, sehingga laporan menyatakan berubah: False.

Hasil ini bukan kegagalan, melainkan kebetulan bahwa kebijakan awal yang dipilih sudah optimal untuk gridworld mini ini. Pada lingkungan yang lebih besar, perbaikan kebijakan biasanya mengubah beberapa aksi pada putaran pertama, dan putaran berikutnya mengubah aksi lain yang baru terlihat setelah nilai terbarui. Operator ini tidak menjamin satu langkah sudah cukup, dan justru itulah yang memotivasi iterasi kebijakan.

Kesalahan umum#

Menganggap satu putaran evaluasi sudah cukup. Penyebabnya, nilai $V^\pi$ dihitung hanya satu sapuan, padahal informasi reward baru menyebar satu langkah per sapuan. Akibatnya, perbaikan kebijakan memakai nilai yang belum konvergen dan memilih aksi yang keliru. Perbaikannya, jalankan evaluasi sampai perubahan terbesar di bawah ambang batas $\theta$ sebelum memanggil perbaikan kebijakan.

Mencampur evaluasi dan perbaikan dalam satu sapuan. Penyebabnya, kebijakan diubah di tengah perhitungan nilai sehingga yang dihitung bukan $V^\pi$ untuk sebuah $\pi$ tetap. Akibatnya, kedua operator kehilangan jaminan konvergensinya. Perbaikannya, pertahankan pemisahan tegas: evaluasi selesai penuh, baru perbaikan dijalankan.

Ringkasan#

• Evaluasi kebijakan menyelesaikan persamaan Bellman ekspektasi untuk sebuah $\pi$ tetap hingga $V^\pi$ konvergen, tanpa mengubah $\pi$.
• Perbaikan kebijakan membuat kebijakan serakah terhadap $V^\pi$ dengan memilih aksi ber-$Q^\pi(s,a)$ terbesar, yang nilainya paling tidak sama dengan $\pi$ lama.
• Pada gridworld mini, kebijakan awal kanan saja ternyata sudah optimal sehingga perbaikan melaporkan berubah: False, sebuah hasil yang memperlihatkan kapan perbaikan tidak mengubah apa pun.

Referensi#

• Reinforcement Learning: An Introduction, ch. 4 — Sutton & Barto — Bab “Dynamic Programming” yang merumuskan policy evaluation, policy improvement, dan teorema perbaikan kebijakan.
• Policy improvement theorem — Wikipedia — Penjelasan mengenai jaminan bahwa kebijakan serakah tidak menurunkan nilai.