Kebijakan dan kondisi konvergensi algoritma iterasi nilai

8

Algoritme kebijakan dan nilai iterasi dapat digunakan untuk menyelesaikan masalah proses keputusan Markov. Saya mengalami kesulitan memahami kondisi yang diperlukan untuk konvergensi. Jika kebijakan optimal tidak berubah selama dua langkah (yaitu selama iterasi i dan i +1 ), dapatkah disimpulkan bahwa algoritma telah konvergen? Jika tidak, lalu kapan?

ELEC
sumber

Jawaban:

3

Untuk menjawab pertanyaan Anda, izinkan saya terlebih dahulu menuliskan beberapa persamaan penting (dalam).

Persamaan optimalitas Bellman:

v(s)=maxaE[Rt+1+γv(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γv(s)]

di mana v(.) adalah fungsi nilai optimal.

Teorema peningkatan kebijakan ( Pit ):

Biarkan dan pasangan kebijakan deterministik apa pun sehingga, untuk semua , Kemudian kebijakan harus sebagus, atau lebih baik dari, . Artinya, ia harus memperoleh pengembalian yang diharapkan lebih besar atau sama dari semua negara . ππsSqπ(s,π(s))vπ(s)ππsS:vπ(s)vπ(s)

(temukan di halaman 89 dari Sutton & Barto, Reinforcement learning: An Introduction book)

Kami dapat meningkatkan kebijakan di setiap negara bagian dengan aturan berikut:π

π(s)=argmaxaqπ(s,a)=argmaxasp(ss,a)[r(s,a,s)+γvπ(s)]

Kebijakan baru kami memenuhi kondisi Pit dan sama baiknya dengan atau lebih baik dari . Jika sama baiknya dengan, tetapi tidak lebih baik dari , maka untuk semua . Dari definisi kami tentang kami menyimpulkan, bahwa:ππππvπ(s)=vπ(s)sπ

vπ(s)=maxaE[Rt+1+γvπ(St+1)St=s,At=a]=maxasp(ss,a)[r(s,a,s)+γvπ(s)]

Tetapi persamaan ini sama dengan persamaan optimalitas Bellman sehingga harus sama dengan .vπv

Dari kata di atas, mudah-mudahan jelas, bahwa jika kita meningkatkan kebijakan dan mendapatkan fungsi nilai yang sama, yang kita miliki sebelumnya, kebijakan baru harus menjadi salah satu kebijakan yang optimal. Untuk informasi lebih lanjut, lihat Sutton & Barto (2012)

Jan Vainer
sumber
1

Anda benar: estimasi fungsi nilai saat ini atau estimasi kebijakan saat ini dapat sepenuhnya menggambarkan keadaan algoritma. Masing-masing menyiratkan pilihan unik berikutnya untuk yang lain. Dari kertas yang ditautkan di bawah ini,

"Iterasi kebijakan berlanjut hingga ."Vn+1=Vn,αn+1=αn

https://editorialexpress.com/jrust/research/siam_dp_paper.pdf

eric_kernfeld
sumber