Memahami peran faktor diskon dalam pembelajaran penguatan

43

Saya belajar sendiri tentang penguatan pembelajaran, dan mencoba memahami konsep diskon hadiah. Jadi hadiah itu diperlukan untuk memberi tahu sistem pasangan tindakan negara mana yang baik, dan mana yang buruk. Tapi yang tidak saya mengerti adalah mengapa hadiah diskon diperlukan. Mengapa harus menjadi masalah apakah keadaan yang baik tercapai segera daripada nanti?

Saya mengerti bahwa ini relevan dalam beberapa kasus tertentu. Misalnya, jika Anda menggunakan pembelajaran penguatan untuk berdagang di pasar saham, akan lebih menguntungkan untuk mendapatkan keuntungan lebih cepat daripada nanti. Ini karena memiliki uang sekarang memungkinkan Anda melakukan sesuatu dengan uang itu sekarang, yang lebih diinginkan daripada melakukan sesuatu dengan uang itu nanti.

Tetapi dalam kebanyakan kasus, saya tidak melihat mengapa diskon itu berguna. Misalnya, Anda ingin robot mempelajari cara menavigasi di sekitar ruangan untuk mencapai sisi lain, di mana ada hukuman jika bertabrakan dengan penghalang. Jika tidak ada faktor diskon, maka itu akan belajar untuk mencapai sisi lain dengan sempurna, tanpa bertabrakan dengan hambatan. Mungkin perlu waktu lama untuk sampai ke sana, tetapi akhirnya akan sampai di sana.

Tetapi jika kita memberikan diskon untuk hadiah, maka robot akan didorong untuk mencapai sisi lain ruangan dengan cepat, bahkan jika itu harus bertabrakan dengan benda-benda di sepanjang jalan. Ini jelas bukan hasil yang diinginkan. Tentu, Anda ingin robot itu sampai ke sisi lain dengan cepat, tetapi tidak jika ini berarti harus bertabrakan dengan benda-benda di sepanjang jalan.

Jadi intuisi saya adalah bahwa segala bentuk faktor diskon, sebenarnya akan mengarah pada solusi yang kurang optimal. Dan pilihan faktor diskon sering tampak sewenang-wenang - banyak metode yang saya lihat cukup mengaturnya menjadi 0,9. Ini tampaknya sangat naif bagi saya, dan tampaknya memberikan trade-off sewenang-wenang antara solusi optimal dan solusi tercepat, sedangkan dalam kenyataannya trade-off ini sangat penting.

Tolong bisakah seseorang membantu saya untuk memahami semua ini? Terima kasih :)

Karnivaurus
sumber

Jawaban:

36

TL; DR.

Fakta bahwa tingkat diskonto dibatasi menjadi lebih kecil dari 1 adalah trik matematika untuk membuat jumlah terbatas tak hingga. Ini membantu membuktikan konvergensi algoritma tertentu.

Dalam praktiknya, faktor diskonto dapat digunakan untuk memodelkan fakta bahwa pembuat keputusan tidak pasti tentang apakah dalam keputusan berikutnya instan dunia (misalnya, lingkungan / permainan / proses ) akan berakhir.

Sebagai contoh:

Jika pembuat keputusan adalah robot, faktor diskon bisa menjadi probabilitas bahwa robot dimatikan di waktu berikutnya (dunia berakhir dalam terminologi sebelumnya). Itulah alasan mengapa robot ini terlihat pendek dan tidak mengoptimalkan jumlah hadiah tetapi jumlah hadiah diskon .

Faktor diskon lebih kecil dari 1 (Rincian)

Untuk menjawab lebih tepatnya, mengapa tingkat diskonto harus lebih kecil dari yang saya pertama kali akan memperkenalkan Proses Keputusan Markov (MDPs).

Teknik pembelajaran penguatan dapat digunakan untuk menyelesaikan MDP. MDP menyediakan kerangka kerja matematis untuk memodelkan situasi pengambilan keputusan di mana hasilnya sebagian acak dan sebagian di bawah kendali pengambil keputusan. MDP didefinisikan melalui ruang keadaan , ruang tindakan , fungsi probabilitas transisi antar negara (dikondisikan untuk tindakan yang diambil oleh pembuat keputusan), dan fungsi hadiah.SA

Dalam pengaturan dasarnya, pembuat keputusan mengambil dan bertindak, dan mendapat hadiah dari lingkungan, dan lingkungan mengubah kondisinya. Kemudian pembuat keputusan merasakan keadaan lingkungan, mengambil tindakan, mendapat hadiah, dan sebagainya. Transisi negara bersifat probabilistik dan hanya bergantung pada keadaan aktual dan tindakan yang diambil oleh pembuat keputusan. Hadiah yang diperoleh oleh pembuat keputusan tergantung pada tindakan yang diambil, dan pada kondisi lingkungan asli dan baru.

Hadiah diperoleh ketika mengambil tindakan dalam keadaan dan lingkungan / sistem berubah menjadi keadaan setelah pembuat keputusan mengambil tindakan . Pembuat keputusan mengikuti kebijakan, , yang untuk setiap negara bagian mengambil tindakan . Sehingga kebijakan itulah yang memberi tahu pembuat keputusan tindakan apa yang harus diambil di setiap negara bagian. Kebijakan dapat diacak juga tetapi tidak masalah untuk saat ini.Rai(sj,sk)aisjskaiπ π():SAsjSaiAπ

Tujuannya adalah untuk menemukan kebijakan sedemikian rupaπ

maxπ:S(n)ailimTE{n=1TβnRxi(S(n),S(n+1))}(1),
mana adalah faktor diskon dan .ββ<1

Perhatikan bahwa masalah pengoptimalan di atas, memiliki horizon waktu tak terbatas ( ), dan tujuannya adalah untuk memaksimalkan jumlah hadiah (hadiah dikalikan dengan ). Ini biasanya disebut masalah MDP dengan kriteria hadiah diskon cakrawala tak terbatas .TdiscountedRβn

Masalahnya disebut diskon karena . Jika itu bukan masalah diskon jumlahnya tidak akan bertemu. Semua kebijakan yang telah memperoleh rata-rata hadiah positif pada setiap saat instan akan berjumlah hingga tak terbatas. Akan menjadi kriteria reward cakrawala jumlah terbatas , dan bukan merupakan kriteria optimasi yang baik.β<1β=1

Ini adalah contoh mainan untuk menunjukkan kepada Anda apa yang saya maksud:

Asumsikan bahwa hanya ada dua tindakan yang mungkin dan bahwa fungsi hadiah sama dengan jika , dan jika (hadiah tidak tergantung pada keadaan).a=0,1R1a=10a=0

Jelas bahwa kebijakan yang mendapatkan hadiah lebih banyak adalah selalu mengambil tindakan dan tidak pernah bertindak . Saya akan menelepon kebijakan ini . Saya akan membandingkan dengan kebijakan lain yang mengambil tindakan dengan probabilitas kecil , dan tindakan sebaliknya.a=1a=0πππa=1α<<1a=0

Dalam persamaan kriteria diskon diskon cakrawala tak terbatas (1) menjadi (jumlah deret geometri) untuk polis sedangkan untuk polis persamaan kebijakan (1) menjadi . Karena , kami mengatakan bahwa adalah kebijakan yang lebih baik daripada . Sebenarnya adalah kebijakan optimal.11βππα1β11β>α1βπππ

Dalam kriteria jumlah horison jumlah yang tak terbatas ( ) persamaan (1) tidak menyatu untuk salah satu kebijakan (jumlahnya hingga tak terbatas). Jadi, sementara polis mencapai imbalan yang lebih tinggi daripada kedua polis itu sama menurut kriteria ini. Itulah salah satu alasan mengapa kriteria hadiah horizon tak terbatas tidak berguna.β=1ππ

Seperti yang saya sebutkan sebelumnya, membuat trik membuat jumlah dalam persamaan (1) bertemu.β<1

Kriteria optimalitas lainnya

Ada kriteria optimalitas lain yang tidak memaksakan itu :β<1

Kasus kriteria horizon hingga tujuannya adalah untuk memaksimalkan hadiah diskon hingga horizon waktuT

maxπ:S(n)aiE{n=1TβnRxi(S(n),S(n+1))},

untuk dan hingga.β1T

Dalam kriteria imbalan rata-rata horizon tak terbatas tujuannya adalah

maxπ:S(n)ailimTE{n=1T1TRxi(S(n),S(n+1))},

Catatan akhir

Bergantung pada kriteria optimalitas seseorang akan menggunakan algoritma yang berbeda untuk menemukan kebijakan yang optimal. Sebagai contoh, kebijakan optimal dari masalah horizon terbatas akan bergantung pada keadaan dan waktu instan aktual. Sebagian besar algoritma Pembelajaran Penguatan (seperti SARSA atau pembelajaran-Q) menyatu dengan kebijakan optimal hanya untuk diskon kriteria imbalan cakrawala tak terbatas diskon (hal yang sama terjadi untuk algoritma pemrograman Dinamis). Untuk kriteria hadiah rata-rata tidak ada algoritma yang telah ditunjukkan untuk menyatu dengan kebijakan optimal, namun seseorang dapat menggunakan R-learning yang memiliki kinerja yang baik meskipun tidak konvergensi teoritis yang baik.

PolBM
sumber
1
Adakah ide tentang apa yang harus saya baca untuk memahami semua bahasa Cina dalam jawaban Anda?
thibaut noah
@ thibautnoah Ini IMHO referensi terbaik Penguatan Pembelajaran: Pengantar dari Sutton dan Barto. [ people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf]
PolBM
terima kasih sobat, mungkin akan membutuhkan buku lain tentang matematika tetapi saya kira itu awal;)
thibaut noah
6

Anda benar bahwa faktor diskon (disebut - perhatikan bahwa ini berbeda dari dari TD- ) bertindak seperti "urgensi kehidupan" dan karena itu merupakan bagian dari masalah - sama seperti di kehidupan manusia: Beberapa orang hidup seolah-olah mereka akan hidup selamanya; beberapa orang hidup seolah-olah mereka akan mati besok.γλλ

Neil G
sumber
2

TL; DR: Faktor diskon dikaitkan dengan horizon waktu. Cakrawala waktu yang lebih lama memiliki varians yang jauh lebih banyak karena mencakup lebih banyak informasi yang tidak relevan, sementara cakrawala waktu singkat bias terhadap keuntungan jangka pendek.

Faktor diskon pada dasarnya menentukan seberapa besar agen pembelajaran penguatan peduli tentang hadiah di masa depan yang relatif dibandingkan dengan mereka di masa depan yang dekat. Jika , agen akan sepenuhnya rabun dan hanya belajar tentang tindakan yang menghasilkan hadiah langsung. Jika , agen akan mengevaluasi setiap tindakannya berdasarkan jumlah total semua hadiahnya di masa depan.γ=0γ=1

Jadi mengapa Anda tidak selalu ingin membuat setinggi mungkin? Yah, sebagian besar tindakan tidak memiliki dampak jangka panjang. Sebagai contoh, anggaplah bahwa pada hari pertama setiap bulan Anda memutuskan untuk memperlakukan diri Anda dengan smoothie, dan Anda harus memutuskan apakah Anda akan mendapatkan smoothie blueberry atau smoothie stroberi. Sebagai pembelajar pembelajar yang baik, Anda menilai kualitas keputusan Anda dengan seberapa besar penghargaan Anda selanjutnya. Jika horizon waktu Anda sangat singkat, Anda hanya akan memperhitungkan imbalan langsung, seperti seberapa lezat smoothie Anda. Dengan cakrawala waktu yang lebih lama, seperti beberapa jam, Anda mungkin juga mempertimbangkan hal-hal seperti apakah Anda sakit perut atau tidak. Tetapi jika cakrawala waktu Anda berlangsung selama sebulan penuh, maka setiap hal yang membuat Anda merasa baik atau buruk selama sebulan penuhγakan menjadi faktor pertimbangan Anda apakah Anda membuat keputusan smoothie yang tepat atau tidak. Anda akan memperhitungkan banyak informasi yang tidak relevan, dan oleh karena itu penilaian Anda akan sangat bervariasi dan sulit untuk dipelajari.

Memilih nilai tertentu dari sama dengan memilih horizon waktu. Ini membantu untuk menulis ulang reward potongan agen ini sebagai mana saya mengidentifikasi dan . Nilai secara eksplisit menunjukkan horizon waktu yang terkait dengan faktor diskon; sesuai dengan , dan imbalan apa pun yang lebih dariγG

Gt=Rt+γRt+1+γ2Rt+2+=k=0γkRt+k=Δt=0eΔt/τRt+Δt
γ=e1/τkΔtτγ=1τ=τlangkah-langkah waktu di masa depan ditekan secara eksponensial. Anda biasanya harus memilih faktor diskon sehingga horizon waktu berisi semua hadiah yang relevan untuk tindakan tertentu, tetapi tidak lagi.

clwainwright
sumber