Fungsi nilai

Fungsi nilai adalah ukuran numerik atas kualitas sebuah kebijakan, dan menjadi jembatan antara perilaku agen dengan optimasi yang dilakukan algoritma reinforcement learning. Topik ini memperkenalkan dua fungsi nilai, yaitu state-value function $V^\pi(s)$ yang mengukur kebaikan berada di sebuah state di bawah kebijakan tertentu, dan action-value function $Q^\pi(s,a)$ yang mengukur kebaikan memilih sebuah aksi pada state tersebut. Pembaca akan melihat implementasi evaluasi kebijakan yang menghitung $V^\pi$ secara iteratif sampai konvergen, lalu memperoleh $Q^\pi$ dari $V^\pi$ yang sudah stabil.

Dua fungsi nilai dan return yang diharapkan#

Return adalah jumlah reward terdiskon sepanjang sebuah episode, yaitu $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$. Karena lintasan bergantung pada kebijakan dan dinamika yang bersifat stokastik, return bersifat acak sehingga yang berguna bagi agen adalah nilainya yang diharapkan. Fungsi nilai state didefinisikan sebagai expected return mulai dari state $s$ dan mengikuti kebijakan $\pi$:

Fungsi nilai aksi memperinci definisi ini dengan menyertakan aksi pertama yang dipilih, yaitu expected return mulai dari state $s$, memilih aksi $a$, lalu mengikuti $\pi$:

Kedua fungsi ini saling terkait. $V^\pi(s)$ adalah rata-rata $Q^\pi(s, a)$ ditimbang oleh kebijakan, sedangkan $Q^\pi(s, a)$ adalah jumlah expected reward satu langkah ditambah nilai state berikutnya. Karena hubungan ini, menghitung salah satu cukup untuk memperoleh yang lain, dan pemilihan antara keduanya bergantung pada algoritma yang dipakai.

Persamaan ekspektasi Bellman#

Fungsi nilai memenuhi hubungan rekursif yang disebut persamaan ekspektasi Bellman. Untuk fungsi nilai state, persamaannya adalah

Persamaan ini menyatakan bahwa nilai sebuah state sama dengan rata-rata atas aksi, ditimbang kebijakan, dari expected reward satu langkah ditambah nilai state berikutnya yang terdiskon. Bentuk rekursif inilah yang memungkinkan perhitungan iteratif, karena nilai state dapat diperbarui berulang kali hingga persamaan tersebut terpenuhi. Konvergensi dijamin oleh syarat $\gamma < 1$ yang membuat pemetaan bersifat kontraktif.

Persamaan ekspektasi Bellman menjadi dasar algoritma evaluasi kebijakan, yaitu menghitung $V^\pi$ untuk sebuah kebijakan yang sudah ditetapkan. Algoritma ini memulai dari nilai nol, lalu mengulang pembaruan berdasarkan persamaan di atas sampai perubahan terbesar di bawah ambang batas yang ditetapkan. Karena tidak melibatkan acak, hasilnya dapat direproduksi persis dan cocok untuk verifikasi numerik pada MDP kecil.

Evaluasi kebijakan secara iteratif#

Blok berikut mendefinisikan ulang MDP gridworld mini agar berdiri sendiri, memilih kebijakan seragam $\pi(a \mid s) = 0{,}5$, lalu menjalankan evaluasi kebijakan sampai perubahan terbesar di bawah $10^{-4}$. Setelah $V^\pi$ konvergen, $Q^\pi(s_2, a)$ dihitung untuk kedua aksi guna memperlihatkan hubungan antara kedua fungsi nilai.

import warnings
warnings.filterwarnings("ignore")

# MDP mini yang sama (didefinisikan ulang agar berdiri sendiri)
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 seragam: pi(kiri|s) = pi(kanan|s) = 0.5
pi = {s: {a: 0.5 for a in actions} for s in states}

# Evaluasi kebijakan: iterasi sampai konvergen
V = {s: 0.0 for s in states}
theta = 1e-4
for _ in range(10000):
    delta = 0.0
    newV = {}
    for s in states:
        total = 0.0
        for a in actions:
            p_a = pi[s][a]
            q = 0.0
            for ns, prob, r in transisi[s][a]:
                q += prob * (r + gamma * V[ns])
            total += p_a * q
        newV[s] = total
        delta = max(delta, abs(newV[s] - V[s]))
    V = newV
    if delta < theta:
        break

print("V^pi (kebijakan seragam, gamma=0.9):")
for s in states:
    print(f"  V({s}) = {V[s]:.4f}")

# Q^pi(s2, a) untuk kedua aksi
print()
print("Q^pi(s2, a):")
for a in actions:
    q = 0.0
    for ns, prob, r in transisi["s2"][a]:
        q += prob * (r + gamma * V[ns])
    print(f"  Q(s2, {a}) = {q:.4f}")

V^pi (kebijakan seragam, gamma=0.9):
  V(s0) = 0.3950
  V(s1) = 0.4829
  V(s2) = 0.6783
  V(s3) = 0.0000

Q^pi(s2, a):
  Q(s2, kiri) = 0.4346
  Q(s2, kanan) = 0.9221

Keluaran tersebut mengandung tiga pengamatan. Pertama, nilai state meningkat dari s0 menuju s2 karena semakin dekat ke peluang memperoleh reward 1,0 pada transisi s2 ke s3, lalu turun ke nol pada s3 yang terminal. Kedua, $V^\pi(s_2) = 0{,}6783$ berada di antara $Q^\pi(s_2, \text{kiri})$ dan $Q^\pi(s_2, \text{kanan})$, dan rata-rata tertimbang keduanya dengan bobot kebijakan 0,5 menghasilkan $(0{,}4346 + 0{,}9221)/2 = 0{,}6784$, yang sesuai dengan $V^\pi(s_2)$ hingga pembulatan. Hubungan ini memperlihatkan bahwa $V^\pi$ memang rata-rata $Q^\pi$ ditimbang kebijakan. Ketiga, $Q^\pi(s_2, \text{kanan})$ jauh lebih besar daripada $Q^\pi(s_2, \text{kiri})$, yang menandakan bahwa kebijakan seragam belum optimal karena aksi kanan lebih baik namun tidak dipilih lebih sering.

Dari fungsi nilai ke kebijakan yang lebih baik#

Fungsi nilai tidak hanya mengukur kualitas kebijakan, melainkan juga memberi petunjuk perbaikan. Bila sebuah aksi memiliki $Q^\pi(s, a)$ tertinggi pada sebuah state, agen dapat meningkatkan kebijakan dengan memilih aksi tersebut secara deterministik di state itu. Langkah ini disebut perbaikan kebijakan, dan penggabungan antara evaluasi serta perbaikan membentuk iterasi kebijakan yang akan dibahas di modul pemrograman dinamis. Pada contoh di atas, kebijakan seragam dapat diperbaiki dengan mengubah kebijakan di s2 menjadi selalu memilih kanan, yang akan menaikkan $V^\pi$ keseluruhan.

Pada masalah tanpa model, yaitu ketika dinamika $P$ dan $R$ tidak diketahui, algoritma seperti Q-learning dan SARSA mengaproksimasi $Q^\pi$ langsung dari sampel pengalaman tanpa menjalankan evaluasi kebijakan penuh. Fungsi nilai tetap menjadi kuantitas yang dipelajari, hanya saja persamaan Bellman didekati secara stokastik daripada dihitung secara eksak. Dengan demikian, pemahaman persamaan ekspektasi Bellman di sini menjadi fondasi untuk seluruh algoritma pembelajaran tanpa model pada modul-modul berikutnya.

Kesalahan umum#

Menggunakan $\gamma = 1$ pada episode tak berhingga. Penyebabnya, nilai diskon kadang dianggap detail kosmetik sehingga dipasang satu agar reward masa depan tidak dikurangi. Akibatnya, return dapat divergen dan evaluasi kebijakan tidak konvergen. Perbaikannya, tetapkan $\gamma < 1$ untuk masalah berkelanjutan, dan cadangkan $\gamma = 1$ hanya untuk episode yang pasti berakhir dengan jumlah langkah terbatas.

Menghentikan iterasi terlalu awal. Penyebabnya, ambang batas $\theta$ dipasang terlalu longgar atau iterasi dibatasi sedikit. Akibatnya, $V^\pi$ yang dilaporkan belum stabil sehingga kebijakan yang diperbaiki darinya juga tidak optimal. Perbaikannya, gunakan $\theta$ yang cukup kecil, misalnya $10^{-4}$, dan periksa bahwa perubahan terbesar sudah benar-benar di bawah ambang sebelum berhenti.

Ringkasan#

• Fungsi nilai state $V^\pi(s)$ mengukur expected return dari sebuah state, sedangkan fungsi nilai aksi $Q^\pi(s,a)$ mengukur expected return dari sebuah pasangan state-aksi.
• Persamaan ekspektasi Bellman $V^\pi(s)=\sum_a \pi(a|s)\sum_{s'} P(s'|s,a)[r + \gamma V^\pi(s')]$ bersifat rekursif dan menjadi dasar evaluasi kebijakan.
• Evaluasi kebijakan menghitung $V^\pi$ secara iteratif sampai perubahan di bawah ambang, dan $Q^\pi$ diperoleh dari expected reward satu langkah ditambah nilai state berikutnya.
• Selisih $Q^\pi(s,a)$ antar aksi memberi petunjuk perbaikan kebijakan, yang menjadi inti iterasi kebijakan dan algoritma pembelajaran tanpa model.

Referensi#

• Reinforcement Learning: An Introduction, ch. 3 — Sutton & Barto — Definisi $V^\pi$, $Q^\pi$, dan persamaan ekspektasi Bellman pada bab “Finite Markov Decision Processes”.
• Bellman equation — Wikipedia — Penurunan dan sifat kontraktif persamaan Bellman pada proses keputusan Markov.