Mengapa algoritma iterasi kebijakan menyatu dengan fungsi kebijakan dan nilai yang optimal?

10

Saya membaca catatan kuliah Andrew Ng tentang pembelajaran penguatan, dan saya mencoba memahami mengapa iterasi kebijakan digabungkan ke fungsi nilai optimal dan kebijakan optimal .Vπ

Ingat iterasi kebijakan adalah:

Initialize π randomlyRepeat{Let V:=Vπ \for the current policy, solve bellman's eqn's and set that to the current VLet π(s):=argmaxaAsPsa(s)V(s)}

Mengapa algoritma serakah mengarah pada kebijakan optimal dan fungsi nilai optimal? (Saya tahu algoritma serakah tidak selalu menjamin hal itu, atau mungkin terjebak dalam optima lokal, jadi saya hanya ingin melihat bukti untuk optimalitas algoritma).

Juga, bagi saya tampaknya iterasi kebijakan adalah sesuatu yang analog dengan pengelompokan atau penurunan gradien. Untuk pengelompokan, karena dengan pengaturan parameter saat ini, kami mengoptimalkan. Mirip dengan gradient descent karena hanya memilih beberapa nilai yang tampaknya meningkatkan beberapa fungsi. Dua metode ini tidak selalu menyatu ke maxima optimal, dan saya mencoba memahami bagaimana algoritma ini berbeda dari yang sebelumnya saya sebutkan.


Ini adalah pemikiran saya sejauh ini:

Katakanlah bahwa kita mulai dengan beberapa kebijakan , kemudian setelah langkah pertama, untuk kebijakan tetap itu kita memilikinya:π1

Vπ1(s)=R(s)+γsPsπ1(s)(s)Vπ1(s)

V(1):=Vπ1(s)

Di mana V ^ {(1)} adalah fungsi nilai untuk iterasi pertama. Kemudian setelah langkah kedua kami memilih beberapa kebijakan baru untuk meningkatkan nilai . Sekarang, dengan kebijakan baru , jika kita melakukan langkah kedua algoritma, ketidaksetaraan berikut ini berlaku:π2Vπ1(s)π2

R(s)+γsPsπ1(s)(s)Vπ1(s)R(s)+γsPsπ2(s)(s)Vπ1(s)

Karena kita memilih pada langkah kedua untuk meningkatkan fungsi nilai pada langkah sebelumnya (yaitu untuk meningkatkan . Sejauh ini, jelas bahwa memilih hanya dapat meningkatkan V ^ {(1)}, karena itulah cara kami memilih . Namun, kebingungan saya muncul pada langkah pengulangan karena setelah kami mengulangi dan kembali ke langkah 1, kami benar-benar mengubah banyak hal karena kami menghitung ulang untuk kebijakan baru . Pemberian yang mana:π2V(1)π2π2V2π2

Vπ2(s)=R(s)+γsPsπ2(s)(s)Vπ2(s)

tapi ini BUKAN:

Vπ1(s)=R(s)+γsPsπ2(s)(s)Vπ1(s)

Yang tampaknya menjadi masalah karena dipilih untuk meningkatkan , dan bukan . Pada dasarnya masalahnya adalah bahwa menjamin untuk meningkatkan dengan melakukan sebagai gantinya dari ketika fungsi nilai adalah . Tetapi pada langkah berulang kami mengubah menjadi , tetapi saya tidak melihat bagaimana hal itu menjamin bahwa fungsi nilai meningkat secara monoton pada setiap pengulangan karena dihitung untuk meningkatkan fungsi nilai saat fungsi nilai tetap diπ2V(1)Vπ2pi2R(s)+γsPsπ1(s)(s)Vπ1(s)π 2 p i 1 V π 1 V π 1 V π 2 π 2 V π 1 V π 1V π 2 π 2π2pi1Vπ1Vπ1Vπ2π2Vπ1, tetapi langkah 1 mengubah menjadi (yang buruk karena I hanya meningkatkan fungsi nilai sebelumnya yang kami miliki).Vπ1Vπ2π2

Pinokio
sumber
1
Sekedar catatan: serakah tidak menyiratkan bahwa suatu algoritma tidak akan menemukan solusi optimal secara umum.
Regenschein
1
Iterasi nilai adalah algoritma Pemrograman Dinamis, bukan yang serakah. Keduanya memiliki beberapa kesamaan, tetapi ada perbedaan. Lihatlah stackoverflow.com/questions/13713572/… .
francoisr
@ Francoisr tidak ada yang pernah mengatakan itu padaku. Mungkin itulah mengapa hal itu sangat (tidak perlu) misterius bagi saya. Saya kenal DP dengan cukup baik. Terimakasih Meskipun! :)
Pinocchio

Jawaban:

4

Saya pikir bagian yang Anda lewatkan adalah bahwa dijamin untuk alasan yang sama kita dapat memesan . Itulah dasarnya definisi dari satu kebijakan menjadi lebih baik dari yang lain - bahwa fungsi nilainya lebih besar atau sama di semua negara. Anda telah menjamin ini dengan memilih tindakan pemaksimalan - tidak ada nilai keadaan yang mungkin lebih buruk daripada sebelumnya, dan jika hanya satu pilihan tindakan telah berubah untuk memilih tindakan pemaksimalan yang lebih baik, maka Anda sudah tahu (tetapi mungkin belum menghitung) bahwa untuk keadaan itu akan lebih tinggi daripada . π 2π 1 V π 2 ( s ) V π 1 ( s )Vπ2Vπ1π2π1Vπ2(s)Vπ1(s)

Ketika kami memilih untuk memaksimalkan hasil untuk menghasilkan , kami tidak tahu apa yang akan menjadi untuk keadaan apa pun, tetapi kami tahu bahwa .V π 2 ( s ) s : V π 2 ( s ) V π 1 ( s )π2Vπ2(s)s:Vπ2(s)Vπ1(s)

Karena itu, kembali melalui loop dan menghitung untuk kebijakan baru dijamin memiliki nilai yang sama atau lebih tinggi dari sebelumnya, dan ketika datang untuk memperbarui kebijakan lagi, . π 3π 2π 1Vπ2π3π2π1

Neil Slater
sumber
4

Pertama mari kita lihat mengapa Algoritma Iterasi Kebijakan berfungsi. Ini memiliki dua langkah.

Langkah Evaluasi Kebijakan:

vn=rdn+γPdnvn adalah bentuk umum dari sistem persamaan linear.

Di sini, istilah adalah hadiah langsung dan baris yang sesuai dari matriks transisi.rdn,Pdn

Istilah-istilah ini tergantung pada kebijakanΠn

Memecahkan sistem persamaan di atas kita dapat menemukan nilai-nilaivn

Langkah Perbaikan Kebijakan:

Asumsikan bahwa kami dapat menemukan kebijakan baru sedemikian rupaΠn+1

rdn+1+γPdn+1vnrdn+γPdnvnrdn+1[IγPdn+1]vnsay this is eqn. 1

Sekarang, berdasarkan pada kebijakan baru , kita dapat menemukan , katakan ini adalah persamaan 2. v n + 1 = r d n + 1 + γ P d n + 1 v n + 1Πn+1vn+1=rdn+1+γPdn+1vn+1

Kami akan menunjukkan bahwa ;vn+1vn

yaitu dasarnya untuk semua negara, kebijakan yang baru dipilih memberikan nilai yang lebih baik dibandingkan dengan kebijakan sebelumnya Π nΠn+1Πn

Bukti:

Dari, persamaan 2, kita memiliki,

[IγPdn+1]vn+1=rdn+1

Dari, , kami punya1&2

vn+1vn

Pada dasarnya, nilai-nilai meningkat secara monoton dengan setiap iterasi.

Ini penting untuk memahami mengapa Interasi Kebijakan tidak akan macet secara maksimal.

Kebijakan tidak lain adalah ruang tindakan negara.

Pada setiap langkah iterasi kebijakan, kami mencoba menemukan setidaknya satu tindakan-negara yang berbeda antara dan dan melihat apakah . Hanya jika kondisi terpenuhi kami akan menghitung solusi untuk sistem persamaan linear baru.Πn+1Πnrdn+1+γPdn+1vnrdn+γPdnvn

Asumsikan dan adalah optimum global dan lokal masing-masing.ΠΠ#

Tersirat,vv#

Asumsikan algoritma macet pada optimal lokal.

Jika ini masalahnya, maka langkah peningkatan kebijakan tidak akan berhenti di ruang tindakan-tindakan lokal optimal , karena terdapat setidaknya satu tindakan negara di yang berbeda dari dan menghasilkan nilai dibandingkan denganΠ#ΠΠ#vv#

atau, dengan kata lain,

[IγPd]v[IγPd]v#

rd[IγPd]v#

rd+γPdv#v#

rd+γPdv#rd#+γPd#v#

Oleh karena itu, iterasi Kebijakan tidak berhenti pada optimal lokal

musang madu
sumber