Mengapa Q-learning tidak bertemu ketika menggunakan perkiraan fungsi?

12

Algoritma Q-learning tabular dijamin untuk menemukan fungsi Q optimal , Q , asalkan kondisi berikut (kondisi Robbins-Monro ) mengenai tingkat pembelajaran terpenuhi

  1. tαt(s,Sebuah)=
  2. tαt2(s,Sebuah)<

di mana αt(s,a) berarti tingkat pembelajaran yang digunakan ketika memperbarui nilai Q terkait dengan keadaan s dan tindakan a pada waktu waktu t langkah , di mana 0αt(s,a)<1 diasumsikan benar, untuk semua negara s dan tindakan a .

Rupanya, mengingat bahwa 0αt(s,a)<1 , agar kedua kondisi menjadi benar, semua pasangan tindakan-negara harus sering dikunjungi tanpa batas: ini juga dinyatakan dalam buku Reinforcement Learning: An Introduction , terlepas dari fakta bahwa ini harus diketahui secara luas dan itu adalah alasan di balik penggunaan kebijakan ϵ -regal (atau kebijakan serupa) selama pelatihan.

Bukti lengkap yang menunjukkan bahwa pembelajaran- Q menemukan fungsi Q optimal dapat ditemukan dalam makalah Konvergensi pembelajaran-Q: Bukti Sederhana (oleh Francisco S. Melo). Dia menggunakan konsep seperti pemetaan kontraksi untuk mendefinisikan fungsi Q optimal (lihat juga Apa operator Bellman dalam pembelajaran penguatan? ), Yang merupakan titik tetap dari operator kontraksi ini. Dia juga menggunakan teorema (n. 2) mengenai proses acak yang konvergen ke 0 , diberikan beberapa asumsi. (Buktinya mungkin tidak mudah diikuti jika Anda bukan seorang pria matematika.)

Jika jaringan saraf digunakan untuk mewakili fungsi Q , apakah jaminan konvergensi dari pembelajaran Q masih berlaku? Mengapa (atau tidak) Q-learning bertemu ketika menggunakan pendekatan fungsi? Apakah ada bukti formal dari non-konvergensi Q learning menggunakan pendekatan fungsi?

Saya mencari berbagai jenis jawaban, dari jawaban yang hanya memberikan intuisi di balik non-konvergensi pembelajaran- Q saat menggunakan perkiraan fungsi hingga yang memberikan bukti formal (atau tautan ke kertas dengan bukti formal).

nbro
sumber
2
Pertanyaan bagus!
John Doucette
Buku yang Anda rujuk berbicara tentang masalah ini di bab 11 sehingga Anda dapat membacanya. Juga, saya tidak berpikir ada bukti formal mengapa ini terjadi tetapi ada beberapa contoh yang menunjukkan perbedaan bahkan dalam lingkungan yang sederhana (misalnya Tsitsiklis dan van Roy).
Brale_

Jawaban:

8

Inilah jawaban deskripsi yang intuitif:

Perkiraan fungsi dapat dilakukan dengan fungsi parameterabel apa pun. Pertimbangkan masalah ruang Q(s,a)s mana s adalah real positif, a adalah 0 atau1 , dan fungsi-Q sebenarnya adalahQ(s,0)=s2 , danQ(s,1)=2s2 , untuk semua status. Jika aproksimasi fungsi Anda adalahQ(s,Sebuah)=ms+nSebuah+b , tidak ada parameter yang dapat secara akurat mewakilifungsiQ sebenarnya(kami mencoba menyesuaikan garis dengan fungsi kuadratik). Akibatnya, bahkan jika Anda memilih tingkat pembelajaran yang baik, dan sering mengunjungi semua negara bagian, fungsi perkiraan Anda tidak akan pernah menyatu dengan Q yang sebenarnya.Q fungsi .

Dan ini sedikit lebih detail:

  1. Jaringan saraf memperkirakan fungsi. Suatu fungsi dapat diperkirakan hingga derajat yang lebih besar atau lebih kecil dengan menggunakan polinomial yang lebih atau kurang kompleks untuk memperkirakannya. Jika Anda terbiasa dengan pendekatan Taylor Series, ide ini seharusnya terlihat cukup alami. Jika tidak, pikirkan fungsi seperti gelombang sinus selama interval [0 π/2 ). Anda dapat memperkirakannya (buruk) dengan garis lurus. Anda bisa memperkirakannya lebih baik dengan kurva kuadratik. Dengan meningkatkan derajat polinomial yang kita gunakan untuk memperkirakan kurva, kita bisa mendapatkan sesuatu yang lebih sesuai dengan kurva.
  2. Jaringan saraf adalah penaksir fungsi universal . Ini berarti bahwa, jika Anda memiliki fungsi, Anda juga dapat membuat jaringan saraf yang dalam atau cukup lebar sehingga dapat mendekati fungsi yang Anda buat ke tingkat yang tepat secara sewenang-wenang. Namun, topologi jaringan spesifik apa pun yang Anda pilih tidak akan dapat mempelajari semua fungsi, kecuali jika luasnya tidak terbatas atau sangat dalam. Ini analog dengan bagaimana, jika Anda memilih parameter yang tepat, garis dapat cocok dengan dua poin, tetapi tidak 3 poin. Jika Anda memilih jaringan yang memiliki lebar atau kedalaman terbatas tertentu, saya selalu dapat membangun fungsi yang membutuhkan beberapa neuron agar sesuai dengan benar.

  3. Batas Q-learning hanya berlaku ketika representasi dari fungsi-Q adalah tepat . Untuk mengetahui alasannya, anggaplah Anda memilih untuk memperkirakan fungsi-Q Anda dengan interpolasi linier. Jika fungsi sebenarnya dapat mengambil bentuk apa pun, maka jelas kesalahan dalam interpolasi kami dapat dibuat besar tanpa batas hanya dengan membangun fungsi fungsi Q seperti XOR, dan tidak ada jumlah waktu ekstra atau data yang memungkinkan kami untuk mengurangi kesalahan ini . Jika Anda menggunakan aproksimator fungsi, dan fungsi sebenarnya yang Anda coba cocokkan tidaksesuatu yang fungsinya dapat mendekati sewenang-wenang dengan baik, maka model Anda tidak akan bertemu dengan benar, bahkan dengan tingkat pembelajaran dan tingkat eksplorasi yang dipilih dengan baik. Dengan menggunakan terminologi teori pembelajaran komputasi, kita dapat mengatakan bahwa bukti konvergensi untuk pembelajaran Q telah secara implisit mengasumsikan bahwa fungsi-Q yang sebenarnya adalah anggota ruang hipotesis di mana Anda akan memilih model Anda.

John Doucette
sumber
Di mana kita bisa melihat dari bukti yang saya sebutkan bahwa "batas Q-learning hanya berlaku ketika representasi fungsi Q tepat" benar?
nbro
Jadi, kita dapat memperkirakan setiap fungsi (masuk akal) menggunakan beberapa jaringan saraf (arsitektur), tetapi, mengingat arsitektur jaringan saraf tetap (yang perlu kita pilih pada awal fase pelatihan dari pembelajaran- Q ), pembelajaran- Q mungkin tidak konvergen menggunakan arsitektur spesifik ZZQQZ , karena mungkin tidak cukup ekspresif untuk mewakili Q . ZQ
nbro
@nbro Buktinya tidak mengatakan itu secara eksplisit, tetapi mengasumsikan representasi yang tepat dari fungsi-Q (yaitu, bahwa nilai-nilai yang tepat dihitung dan disimpan untuk setiap pasangan negara / tindakan). Untuk ruang keadaan tak terhingga, jelas bahwa representasi persis ini bisa sangat besar dalam kasus terburuk (contoh sederhana: misalkan Q (s, a) = sth digit pi). Komentar kedua Anda merangkumnya dengan baik. Lebih formal, jika hipotesis sebenarnya Q * bukan elemen dari ruang hipotesis H yang Anda pilih modelnya, Anda tidak dapat konvergen ke Q *, bahkan dengan waktu atau data yang tak terbatas.
John Doucette
4

Sejauh yang saya ketahui, masih agak masalah terbuka untuk mendapatkan pemahaman formal yang benar-benar jelas tentang mengapa / ketika kita kekurangan konvergensi - atau, lebih buruk, kadang-kadang bahaya perbedaan. Ini biasanya dikaitkan dengan "triad mematikan" (lihat 11.3 dari edisi kedua buku Sutton dan Barto), kombinasi dari:

  1. Aproksimasi fungsi, DAN
  2. Bootstrapping (menggunakan estimasi nilai kami sendiri dalam perhitungan target pelatihan kami, seperti yang dilakukan oleh Q learning), DAN
  3. Pelatihan off-kebijakan ( Q learning memang off-kebijakan).

Itu hanya memberi kita gambaran (mungkin tidak lengkap) kasus di mana kita memiliki kurangnya konvergensi dan / atau bahaya divergensi, tetapi masih tidak memberi tahu kita mengapa itu terjadi dalam kasus-kasus itu.


Jawaban John sudah memberikan intuisi bahwa sebagian dari masalah adalah hanya bahwa penggunaan aproksimasi fungsi dapat dengan mudah menyebabkan situasi di mana aproksimator fungsi Anda tidak cukup kuat untuk mewakili fungsi Q sebenarnya , mungkin selalu ada kesalahan aproksimasi yang tidak mungkin untuk menyingkirkan tanpa beralih ke pendekatan fungsi yang berbeda.

Secara pribadi, saya pikir intuisi ini memang membantu untuk memahami mengapa algoritma tidak dapat menjamin konvergensi ke solusi optimal, tetapi saya masih secara intuitif berharap itu mungkin mampu "menyatu" ke beberapa solusi "stabil" yang merupakan perkiraan terbaik yang diberikan pembatasan yang melekat dalam representasi fungsi yang dipilih. Memang, inilah yang kami amati dalam praktik ketika kami beralih ke pelatihan on-kebijakan (misalnya Sarsa), setidaknya dalam kasus dengan aproksimasi fungsi linier.


Intuisi saya sendiri sehubungan dengan pertanyaan ini umumnya adalah bahwa sumber masalah yang penting adalah generalisasi . Dalam pengaturan tabular, kami telah sepenuhnya mengisolasi entri Q(s,a) untuk semua (s,a) pasangan. Setiap kali kami memperbarui estimasi kami untuk satu entri, ia membiarkan semua entri lainnya tidak dimodifikasi (setidaknya pada awalnya - mungkin ada beberapa efek pada entri lain di pembaruan mendatang karena bootstrap dalam aturan pembaruan). Perbarui aturan untuk algoritme seperti Q learning dan Sarsa kadang-kadang dapat diperbarui ke arah yang "salah" jika kita mendapat "sial", tetapi dengan harapan, mereka umumnya memperbarui ke arah "arah" yang benar. Secara intuitif, ini berarti bahwa, dalam pengaturan tabular, dengan harapan kita akan secara perlahan, secara bertahap memperbaiki kesalahan dalam setiap entri secara terpisah, tanpa mungkin merusak entri lainnya.

Dengan perkiraan fungsi, saat kami memperbarui perkiraan Q(s,a) untuk satu (s,a)Q


maxmax

Masalahnya adalah sebagai berikut. Misalkan kita menjalankan Q iniQ(s,a)

Q(s,a)Q(s,a)+α[maxaQ(s,a)Q(s,a)].

maxaQ(s,a)QQ(s,a)maxaQ(s,a)


Akhirnya, makalah lain (bahkan yang lebih baru) yang saya duga relevan dengan pertanyaan ini adalah Mendiagnosis Kemacetan dalam Algoritma Pembelajaran Q Dalam , tetapi sayangnya saya belum sempat membacanya dengan detail yang cukup dan merangkumnya dengan memadai.

Dennis Soemers
sumber
1
Tapi bukankah penggunaan jaringan saraf juga karena asumsi bahwa keadaan tertentu sangat mirip dengan masing-masing? Status yang sangat mirip (misalnya frame berurutan dalam permainan) sering memiliki tindakan optimal yang sangat mirip (atau sama), jadi saya tidak yakin bahwa penjelasan dalam makalah pertama valid (saya harus membacanya untuk memahami sepenuhnya poin utama mereka).
nbro
1
@nbro Ya, sering kali generalisasi dianggap sebagai keuntungan daripada masalah justru karena alasan itu. Jika itu berfungsi sebagai "yang dimaksudkan", itu bisa sangat kuat dan mempercepat pembelajaran karena kita mentransfer apa pun yang kita pelajari ke status / tindakan yang serupa, daripada belajar untuk setiap keadaan / tindakan yang sedikit berbeda secara terpisah. Tapi itu juga dapat menyebabkan masalah, terutama dalam teori tetapi juga dalam praktik. Itu seperti "pedang bermata dua" kurasa.
Dennis Soemers
1
@DennisSoemers Jawaban super menarik. Titik Q-learning Non-delusi masuk akal. Menemukan fungsi-Q yang benar berarti menemukan titik tetap untuk aturan pembaruan Anda, tetapi tampaknya pendekatan fungsi dapat menyebabkan pembaruan siklik dalam pembelajaran-Q jika Anda memikirkannya dengan cara ini.
John Doucette