IF Notes

Optimal Policy Formulation

4 min read

Back to IF3270 Pembelajaran Mesin

Optimal Policy Formulation

Questions/Cues

  • Bagaimana interface RL diformalkan sebagai Markov Decision Process?
  • Apa itu Return Gt dan bagaimana cara menghitungnya?
  • Mengapa kita memerlukan discount factor γ?
  • Apa definisi optimal policy π*?
  • Bagaimana hubungan value function dengan policy?

Reference Points

  • IF3270 Pembelajaran Mesin - Reinforcement Learning (Pages 31-34)

Formalisasi Interface RL: Markov Decision Process

Interaksi agent-environment diformalkan sebagai Markov Decision Process (MDP), sebuah tuple yang terdiri dari: himpunan states (S), himpunan actions (A), fungsi transition yang menentukan probabilitas state berikutnya P(s’ | s, a), dan fungsi reward R(s, a) yang menyatakan reward yang diharapkan saat mengambil aksi a di state s. MDP bersandar pada Markov property: state berikutnya dan reward hanya bergantung pada state dan aksi saat ini, bukan pada seluruh riwayat — artinya state telah merangkum semua informasi relevan dari masa lalu.

Return Gt

Tujuan agent bukan reward sesaat melainkan Return (Gt), yaitu akumulasi reward masa depan mulai dari langkah t. Karena reward yang jauh di masa depan dianggap kurang bernilai dibanding yang dekat, setiap reward masa depan didiskon dengan discount factor γ (0 ≤ γ ≤ 1). Return didefinisikan sebagai jumlah reward terdiskon:

Gt = Rt+1 + γ·Rt+2 + γ²·Rt+3 + γ³·Rt+4 + ...
   = Σ (k=0 → ∞) γ^k · Rt+k+1

Bentuk rekursif:
Gt = Rt+1 + γ·Gt+1

Semakin kecil γ (mendekati 0), agent semakin myopic (hanya peduli reward dekat); semakin besar γ (mendekati 1), agent semakin far-sighted (memperhitungkan reward jangka panjang).

Mengapa Discounting

Penggunaan discount factor memiliki beberapa alasan. Pertama, secara matematis ia menjamin Return konvergen (terbatas) untuk tugas yang berlangsung tak hingga (γ < 1). Kedua, ia merepresentasikan ketidakpastian masa depan — reward yang jauh lebih tidak pasti sehingga wajar dinilai lebih rendah. Ketiga, ada preferensi terhadap reward yang lebih cepat (analogi nilai waktu uang dalam ekonomi). Dengan discounting, agent secara alami menyeimbangkan reward langsung dengan reward jangka panjang.

Optimal Policy π*

Sebuah policy π memetakan state ke aksi (atau distribusi atas aksi). Setiap policy memiliki value function yang mengukur ekspektasi Return jika mengikuti policy tersebut: state-value v_π(s) = E_π[Gt | St = s], dan action-value q_π(s, a) = E_π[Gt | St = s, At = a]. Optimal policy π* adalah policy yang memaksimalkan expected return (value) di seluruh state. Policy ini menghasilkan value function optimal v*(s) dan q*(s, a) — nilai tertinggi yang dapat dicapai dari setiap state atau pasangan state-aksi.

Hubungan Value Function dengan Policy

Value function dan policy saling terkait erat dalam siklus dua arah. Diberikan sebuah policy, kita dapat mengevaluasinya dengan menghitung value function-nya. Sebaliknya, diberikan value function, kita dapat memperbaiki policy dengan memilih aksi yang memaksimalkan value (bertindak greedy terhadap value function). Begitu kita memiliki q*(s, a), optimal policy diperoleh secara langsung: π*(s) = argmax_a q*(s, a). Inilah dasar yang memungkinkan metode value-based menemukan kebijakan optimal hanya dengan mempelajari value function.

Summary

Interface RL diformalkan sebagai Markov Decision Process (MDP) berisi states, actions, fungsi transition, dan reward, yang bertumpu pada Markov property. Tujuan agent adalah memaksimalkan Return Gt, yaitu akumulasi reward masa depan terdiskon Gt = Rt+1 + γRt+2 + γ²Rt+3 + … dengan discount factor γ yang menjamin konvergensi, merepresentasikan ketidakpastian masa depan, dan memberi preferensi pada reward lebih cepat. Optimal policy π* adalah policy yang memaksimalkan expected return (value), menghasilkan value function optimal v* dan q*. Karena value function dan policy saling terkait, optimal policy dapat diturunkan langsung dari q* melalui π*(s) = argmax_a q*(s, a).

Graph View

Backlinks