Satu langkah value iteration

Diberikan model lingkungan lengkap (MDP): T[s][a] adalah list hasil yang mungkin [p, s2, r, done], yaitu peluang p pindah ke state s2 dengan reward r, dan done = 1 jika episode berakhir. Lakukan satu sapuan value iteration:

V_\text{baru}(s) = \max_a \sum_{(p, s', r, d)} p\,\bigl[r + \gamma\, V(s')\,(1-d)\bigr]

Semua state memakai V lama (update serentak).

Persamaan Bellman

Nilai optimal sebuah state memenuhi:

V^*(s) = \max_a \mathbb{E}\bigl[r + \gamma V^*(s')\bigr]

“Nilai di sini = reward terbaik yang bisa didapat sekarang ditambah nilai tempat yang akan dituju.” Value iteration menerapkan persamaan ini berulang kali. Setiap sapuan, informasi reward merambat satu langkah lebih jauh, dan untuk $\gamma < 1$ hasilnya dijamin konvergen ke $V^*$ .

Keterbatasannya

Value iteration butuh model lengkap $T$ : semua peluang dan reward harus diketahui. Pada sebagian besar masalah nyata (robot, game), model ini tidak tersedia. Q-learning dan TD-learning menyelesaikannya dengan belajar dari pengalaman (sampel transisi), tanpa model.

Penjelasan

Yang diminta. List V_baru sepanjang V.

Langkah di kode: untuk setiap state s, untuk setiap aksi (setiap outcomes di T[s]), jumlahkan p * (r + gamma * V[s2] * (1 - done)). Ambil max atas semua aksi.

Cek case 1. State 0 punya dua aksi: ke state 1 dengan reward 1 (nilai $1 + 0.9 \cdot 0 = 1$ ), atau tetap dengan reward 0 (nilai 0). Maksimumnya 1. State 1 hanya punya aksi yang mengakhiri episode dengan reward 0, jadi nilainya 0.

Case dengan done. Faktor (1 - done) membuat masa depan tidak dihitung setelah episode berakhir, walaupun V[s2] bukan nol.

Yang dikembalikan: list float.