Kapan metode Monte Carlo lebih disukai daripada yang perbedaan temporal?

12

Saya telah melakukan banyak penelitian tentang Penguatan Pembelajaran akhir-akhir ini. Saya mengikuti Pembelajaran Penguatan Sutton & Barto : Pengantar untuk sebagian besar dari ini.

Saya tahu apa itu Proses Keputusan Markov dan bagaimana pembelajaran Dynamic Programming (DP), Monte Carlo dan Temporal Difference (DP) dapat digunakan untuk menyelesaikannya. The Masalah Saya mengalami adalah bahwa saya tidak melihat ketika Monte Carlo akan menjadi pilihan yang lebih baik atas TD-learning.

Perbedaan utama di antara mereka adalah bahwa pembelajaran TD menggunakan bootstrap untuk memperkirakan fungsi nilai tindakan dan Monte Carlo menggunakan rata-rata untuk mencapai hal ini. Saya benar-benar tidak bisa memikirkan skenario ketika ini adalah cara yang lebih baik untuk pergi.

Dugaan saya adalah bahwa itu mungkin ada hubungannya dengan kinerja tetapi saya tidak dapat menemukan sumber yang dapat membuktikan hal ini.

Apakah saya melewatkan sesuatu atau apakah belajar-TD umumnya merupakan pilihan yang lebih baik?

Anne-dirk
sumber

Jawaban:

8

Masalah utama dengan pembelajaran TD dan DP adalah bahwa pembaruan langkah mereka bias pada kondisi awal parameter pembelajaran. Proses bootstrap biasanya memperbarui fungsi atau pencarian Q (s, a) pada nilai penerus Q (s ', a') menggunakan apa pun perkiraan saat ini di yang terakhir. Jelas pada awal pembelajaran estimasi ini tidak mengandung informasi dari imbalan nyata atau transisi negara.

Jika pembelajaran berfungsi sebagaimana dimaksud, maka bias akan berkurang secara asimptotik pada beberapa iterasi. Namun, bias dapat menyebabkan masalah yang signifikan, terutama untuk metode di luar kebijakan (mis. Q Learning) dan saat menggunakan penaksir fungsi. Kombinasi itu sangat mungkin gagal bertemu sehingga disebut triad mematikan di Sutton & Bart.

Metode kontrol Monte Carlo tidak mengalami bias ini, karena setiap pembaruan dibuat menggunakan sampel sebenarnya dari Q (s, a) yang seharusnya. Namun, metode Monte Carlo dapat menderita varians tinggi, yang berarti lebih banyak sampel diperlukan untuk mencapai tingkat pembelajaran yang sama dibandingkan dengan TD.

Dalam praktiknya, pembelajaran TD tampaknya belajar lebih efisien jika masalah dengan triad mematikan dapat diatasi. Hasil terbaru menggunakan replay pengalaman dan salinan taksir "beku" yang dipentaskan memberikan penyelesaian sekitar yang mengatasi masalah - misalnya, itulah cara pelajar DQN untuk game Atari dibangun.

Ada juga jalan tengah antara TD dan Monte Carlo. Dimungkinkan untuk membangun metode umum yang menggabungkan lintasan panjang yang berbeda - dari TD satu langkah hingga menyelesaikan episode berjalan di Monte Carlo - dan menggabungkannya. Varian yang paling umum dari ini adalah pembelajaran TD ( ), di mana λ adalah parameter dari 0 (pembelajaran TD langkah tunggal efektif) hingga 1 (pembelajaran Monte Carlo efektif, tetapi dengan fitur yang bagus sehingga dapat digunakan dalam masalah yang berkelanjutan) . Biasanya, nilai antara 0 dan 1 membuat agen pembelajaran paling efisien - meskipun seperti banyak hiperparameter, nilai terbaik untuk digunakan tergantung pada masalahnya.λλ0101

Jika Anda menggunakan metode berbasis nilai (yang bertentangan dengan yang berbasis kebijakan), maka pembelajaran TD umumnya lebih banyak digunakan dalam praktik, atau metode kombinasi TD / MC seperti TD (λ) bisa menjadi lebih baik.

Dalam hal "keunggulan praktis" untuk MC? Pembelajaran Monte Carlo secara konseptual sederhana, kuat dan mudah diimplementasikan, walaupun seringkali lebih lambat dari TD. Saya biasanya tidak akan menggunakannya untuk mesin pengontrol pembelajaran (kecuali terburu-buru untuk mengimplementasikan sesuatu untuk lingkungan yang sederhana), tetapi saya akan dengan serius mempertimbangkannya untuk evaluasi kebijakan untuk membandingkan beberapa agen misalnya - itu karena itu menjadi ukuran yang tidak bias, yang penting untuk pengujian.

Neil Slater
sumber
Pertama, terima kasih atas jawabannya. Saya melihat bagaimana dalam teori suatu algoritma yang tidak bias bisa lebih disukai daripada yang bias. Tetapi mengingat varians tinggi yang dapat diberikan Monte Carlo pada awal pelatihan, saya tidak melihat bagaimana ini benar-benar penting. Baik Monte Carlo dan TD akan mulai dengan perkiraan yang tidak akurat dan dari apa yang saya baca, TD akan bertemu lebih cepat. Saya benar-benar tidak dapat menemukan keuntungan praktis menggunakan Monte Carlo. (Menghibur triad maut dapat dihindari)
Anne-dirk
1
@ Anne-dirk Jika Anda menggunakan metode berbasis nilai (sebagai lawan satu berbasis kebijakan), kemudian belajar TD yang umumnya digunakan lebih dalam praktek, atau TD / MC metode kombinasi seperti TD (λ) dapat lebih lebih baik. Saya tidak yakin apa yang Anda maksud dengan "keunggulan praktis"? Pembelajaran Monte Carlo secara konseptual sederhana, kuat dan mudah diimplementasikan. Saya biasanya tidak akan menggunakannya untuk mesin pengontrol pembelajaran (kecuali terburu-buru untuk mengimplementasikan sesuatu untuk lingkungan yang sederhana), tetapi saya akan dengan serius mempertimbangkannya untuk evaluasi kebijakan untuk membandingkan beberapa agen misalnya.
Neil Slater
@Neul Slater Aaaah saya mengerti ... Itulah jawaban yang saya cari :) Terima kasih atas bantuan Anda!
Anne-dirk
-1

Pada dasarnya itu tergantung pada lingkungan Anda.

TD mengeksploitasi properti Markov, yaitu keadaan masa depan dari suatu proses hanya bergantung pada keadaan saat ini, dan karena itu biasanya lebih efisien untuk menggunakan TD di lingkungan Markov.

MC tidak mengeksploitasi properti Markov karena mendasarkan hadiah pada seluruh proses pembelajaran, yang cocok untuk lingkungan non-Markov.

BigBadMe
sumber
Saya tidak berpikir ini benar atau, setidaknya, jelas terlihat. Properti Markov, dalam konteks RL, dikaitkan dengan status. Bisakah Anda menjelaskan mengapa algoritma MC akan bekerja lebih baik ketika properti Markov tidak puas?
1919
Untuk lebih jelasnya, saya mengacu pada efisiensi. Jika Anda dapat mengeksploitasi properti Markov maka TD menguntungkan karena Anda dapat memulai dalam keadaan apa pun, mengambil dan bertindak dan hasilnya akan selalu sama, sehingga Anda dapat menghitung kesalahan TD dengan tingkat kepastian yang tinggi. Dengan non-MDP jika Anda mendapatkan status yang diamati sebagian maka TD mungkin tidak terlalu efisien. Itu tidak berarti Anda tidak dapat menggunakan TD di non-MDP, Anda bisa, tetapi mungkin tidak efisien dan mungkin mendapatkan kesuksesan yang lebih baik dengan TD lambda daripada TD (1).
BigBadMe
"Jika Anda dapat mengeksploitasi properti Markov maka TD menguntungkan karena Anda dapat memulai dalam keadaan apa pun, mengambil dan bertindak dan hasilnya akan selalu sama", itu akan sama jika lingkungan bersifat deterministik. Apa hubungannya ini dengan properti Markov? Saya tidak mendapatkan klaim Anda. Di mana Anda membaca bahwa TD akan lebih tidak efisien daripada MC di misalnya POMDP?
nbro
Secara harfiah ada hubungannya dengan itu menjadi Markov; jika Anda berada di lingkungan Markov maka setelah Anda menetapkan mengambil tindakan dalam keadaan a itu akan mengarah akan menyatakan 'dengan hadiah x - itu akan selalu menjadi kasus di lingkungan markov, sehingga Anda tidak perlu mengevaluasi lebih dan lebih - Anda dapat mengambil langkah lebih besar dan TD memungkinkan Anda untuk mengeksploitasinya. Tetapi itu tidak akan menjadi kasus dalam POMDP karena Anda dapat memiliki kondisi yang sama persis, mengambil tindakan yang sama, tetapi berakhir di negara yang sangat berbeda dan imbalan.
BigBadMe
"Jika Anda berada di lingkungan Markov maka sekali Anda menetapkan mengambil tindakan dalam keadaan a itu akan menyebabkan akan menyatakan 'dengan hadiah x". Tidak ada . Ini hanya benar jika lingkungannya deterministik . Lingkungan juga bisa menjadi stokastik . "itu akan selalu menjadi kasus di lingkungan markov", Tidak , ini adalah masalah ortogonal untuk properti Markov.
nbro