Apa perbedaan antara iterasi nilai dan iterasi kebijakan?

94

Dalam pembelajaran penguatan, apa perbedaan antara iterasi kebijakan dan iterasi nilai ?

Sejauh yang saya pahami, dalam iterasi nilai, Anda menggunakan persamaan Bellman untuk menyelesaikan kebijakan yang optimal, sedangkan, dalam iterasi kebijakan, Anda secara acak memilih kebijakan π, dan menemukan imbalan dari kebijakan itu.

Keraguan saya adalah jika Anda memilih kebijakan acak π di PI, bagaimana kebijakan tersebut dijamin akan menjadi kebijakan yang optimal, bahkan jika kami memilih beberapa kebijakan acak.

machine-learning reinforcement-learning markov-models value-iteration Arslan
sumber
13
Akan lebih tepat untuk mengajukan pertanyaan ini di situs web seperti ai.stackexchange.com , stats.stackexchange.com , atau datasetcience.stackexchange.com .
nbro

Jawaban:

124

Mari kita lihat mereka berdampingan. Bagian kunci untuk perbandingan disorot. Gambar diambil dari buku Sutton dan Barto: Reinforcement Learning: An Introduction .

masukkan deskripsi gambar di sini Poin utama:

  1. Iterasi kebijakan meliputi: evaluasi kebijakan + perbaikan kebijakan , dan keduanya diulangi secara berulang sampai kebijakan menyatu.
  2. Iterasi nilai meliputi: menemukan fungsi nilai optimal + satu ekstraksi kebijakan . Tidak ada pengulangan dari keduanya karena begitu fungsi nilai sudah optimal, maka kebijakan di luarnya juga harus optimal (yaitu konvergen).
  3. Menemukan fungsi nilai yang optimal juga dapat dilihat sebagai kombinasi dari perbaikan kebijakan (karena maks) dan evaluasi kebijakan yang terpotong (penugasan ulang v_ (s) setelah hanya satu sapuan dari semua status terlepas dari konvergensi).
  4. Algoritme untuk evaluasi kebijakan dan menemukan fungsi nilai optimal sangat mirip kecuali untuk operasi maksimal (seperti yang disorot)
  5. Demikian pula, langkah kunci untuk perbaikan kebijakan dan ekstraksi kebijakan adalah identik kecuali langkah pertama melibatkan pemeriksaan stabilitas.

Menurut pengalaman saya, iterasi kebijakan lebih cepat daripada iterasi nilai , karena kebijakan menyatu lebih cepat daripada fungsi nilai. Saya ingat ini juga dijelaskan di buku.

Saya kira kebingungan itu terutama berasal dari semua istilah yang agak mirip ini, yang juga membingungkan saya sebelumnya.

zyxue
sumber
3
Saya setuju bahwa iterasi kebijakan menyatu dalam lebih sedikit iterasi dan saya juga membaca di beberapa tempat bahwa ini lebih cepat. Saya melakukan beberapa eksperimen penyelesaian dunia kotak dan labirin sederhana dengan kedua metode di Burlap. Saya menemukan bahwa iterasi nilai melakukan lebih banyak iterasi tetapi membutuhkan lebih sedikit waktu untuk mencapai konvergensi. YMMV.
Ryan
1
@Chrom, Anda harus membaca kebalikannya. Berikut adalah kutipan dari buku tersebut, " Iterasi kebijakan sering kali bertemu dalam beberapa iterasi yang mengejutkan. Hal ini diilustrasikan oleh contoh pada Gambar 4.1. ", Dari Halaman 65 versi buku 2017nov5 .
zyxue
3
Ya, saya telah bermain dengan beberapa jenis dunia Grid. Saya hanya mencoba menunjukkan bahwa "Lebih cepat" dalam hal iterasi mungkin akan mendukung PI. Tapi "Lebih cepat" dalam hitungan detik mungkin sebenarnya mendukung VI.
Ryan
3
Untuk memperjelas, iterasi kebijakan akan membutuhkan lebih sedikit iterasi tetapi lebih kompleks secara komputasi daripada iterasi nilai; mana yang lebih cepat tergantung pada lingkungan.
RF Nelson
2
Saya tahu bahwa ini adalah posting lama. Tetapi saya sangat menyarankan, melihat ini ( medium.com/@m.alzantot/… ) Tautan menyediakan kode dan itu membuatnya lebih jelas bagi saya.
tandem
73

Dalam algoritme iterasi kebijakan , Anda mulai dengan kebijakan acak, lalu temukan fungsi nilai kebijakan tersebut (langkah evaluasi kebijakan), lalu temukan kebijakan baru (yang ditingkatkan) berdasarkan fungsi nilai sebelumnya, dan seterusnya. Dalam proses ini, setiap kebijakan dijamin akan mengalami perbaikan yang ketat dari sebelumnya (kecuali sudah optimal). Dengan adanya kebijakan, fungsi nilainya dapat diperoleh dengan menggunakan operator Bellman .

Dalam iterasi nilai , Anda mulai dengan fungsi nilai acak dan kemudian menemukan fungsi nilai baru (ditingkatkan) dalam proses berulang, hingga mencapai fungsi nilai optimal. Perhatikan bahwa Anda dapat dengan mudah mendapatkan kebijakan optimal dari fungsi nilai optimal. Proses ini didasarkan pada optimalitas operator Bellman .

Dalam beberapa hal, kedua algoritme memiliki prinsip kerja yang sama, dan mereka dapat dilihat sebagai dua kasus dari iterasi kebijakan umum . Namun, operator Bellman yang optimal memiliki operator max , yang non linier, sehingga memiliki fitur yang berbeda. Selain itu, dimungkinkan untuk menggunakan metode hibrida antara iterasi nilai murni dan iterasi kebijakan murni.

Pablo EM
sumber
1
Deskripsi bagus tentang ini. Baiklah saya tambahkan hal ini dalam iterasi kebijakan itu menggunakan persamaan harapan belman dan dalam iterasi nilai menggunakan persamaan maksimum melman. Untuk iterasi nilai bisa jadi lebih sedikit iterasi tetapi untuk satu iterasi bisa jadi ada begitu banyak pekerjaan. Untuk kebijakan iterasi lebih banyak iterasi
Shamane Siriwardhana
bukankah ada operator maks dalam iterasi kebijakan juga? jika tidak, bagaimana cara memperbarui kebijakan berdasarkan fungsi nilai baru?
huangzonghao
Tidak, algoritme SARSA adalah contoh tipikal dari iterasi kebijakan. Seperti yang Anda lihat di kode pseudo ini ( incompleteideas.net/book/ebook/node64.html ), pembaruan fungsi nilai tidak berisi operator maks. Namun, jika yang Anda maksud adalah operator maks untuk memilih tindakan terbaik dari fungsi nilai (yaitu tindakan serakah), ya, ada operasi maks dalam proses tersebut.
Pablo EM
11

Perbedaan dasarnya adalah -

Dalam Iterasi Kebijakan - Anda secara acak memilih kebijakan dan menemukan fungsi nilai yang sesuai dengannya, kemudian menemukan kebijakan baru (yang ditingkatkan) berdasarkan fungsi nilai sebelumnya, dan seterusnya ini akan menghasilkan kebijakan yang optimal.

Dalam Iterasi Nilai - Anda memilih fungsi nilai secara acak, kemudian mencari fungsi nilai baru (yang ditingkatkan) dalam proses berulang, hingga mencapai fungsi nilai optimal, kemudian mendapatkan kebijakan optimal dari fungsi nilai optimal tersebut.

Iterasi kebijakan bekerja berdasarkan prinsip “Evaluasi kebijakan —-> Perbaikan kebijakan”.

Iterasi Nilai bekerja berdasarkan prinsip “Fungsi nilai optimal —-> kebijakan optimal”.

Himanshu Gupta
sumber
0

Sejauh yang saya ketahui, bertentangan dengan ide @zyxue, VI secara umum jauh lebih cepat daripada PI.

Alasannya sangat mudah, seperti yang telah Anda ketahui, Persamaan Bellman digunakan untuk menyelesaikan fungsi nilai untuk kebijakan yang diberikan. Karena kita dapat menyelesaikan fungsi nilai untuk kebijakan optimal secara langsung , fungsi nilai penyelesaian untuk kebijakan saat ini jelas membuang-buang waktu.

Adapun pertanyaan Anda tentang konvergensi PI, saya pikir Anda mungkin mengabaikan fakta bahwa jika Anda meningkatkan strategi untuk setiap status informasi, maka Anda meningkatkan strategi untuk keseluruhan permainan. Ini juga mudah untuk dibuktikan, jika Anda terbiasa dengan Counterfactual Regret Minimization - jumlah penyesalan untuk setiap status informasi telah membentuk batas atas dari keseluruhan penyesalan, dan dengan demikian meminimalkan penyesalan untuk setiap status akan meminimalkan penyesalan secara keseluruhan, yang mana mengarah pada kebijakan yang optimal.

Respon 777
sumber