Bagaimana saya bisa membuat model masalah sebagai MDP jika agen tidak mengikuti urutan negara bagian yang berurutan?

Dec 31 2020

Dalam masalah saya, agen tidak mengikuti urutan negara bagian yang berurutan, tetapi memilih dengan $\epsilon$-membuat pasangan terbaik (status, tindakan) dari antrian prioritas. Lebih khusus lagi, ketika agen saya pergi ke suatu negara bagian$s$ dan membuka tindakan yang tersedia $\{ a_i \}$, lalu memperkirakan masing-masing $(s,a)$pasangan (regresi dengan DQN) dan menyimpannya ke dalam antrian. Agar agen saya berubah menjadi negara bagian$s'$, ini memilih pasangan terbaik dari antrian alih-alih mengikuti salah satu tindakan yang tersedia $\{ a_i \}$ dari $s$. Saya perhatikan bahwa sebuah negara bagian memiliki set tindakan yang sebagian berbeda dari yang lain.

Namun, dengan cara ini, bagaimana saya dapat membuat model MDP saya jika agen saya tidak mengikuti urutan negara bagian yang berurutan?

Lebih khusus lagi, saya memiliki crawler terfokus yang memiliki masukan dari beberapa URL benih. Saya ingin menghasilkan sebanyak mungkin URL yang relevan dengan benih. Saya memodelkan kerangka RL sebagai berikut.

  • Status: halaman web,
  • Tindakan: URL tautan dari halaman web negara bagian,
  • Imbalan: dari sumber eksternal saya tahu apakah konten halaman web relevan.

Masalahnya adalah, saat merayapi, jika agen terus maju dengan mengikuti transisi status berturut-turut, itu dapat jatuh ke dalam perangkap perayapan atau optima lokal. Itulah alasan mengapa antrian prioritas digunakan secara penting dalam perayapan. Agen perayapan tidak lagi mengikuti urutan transisi status yang berurutan. Setiap pasangan state-action ditambahkan ke antrian prioritas dengan perkiraan nilai tindakannya. Untuk setiap kali, ia memilih pasangan keadaan-tindakan yang paling menjanjikan di antara semua pasangan dalam antrian. Saya perhatikan bahwa setiap tindakan URL dapat diperkirakan dengan mempertimbangkan halaman web negara bagian tempat tindakan itu diekstraksi.

Jawaban

1 FedericoMalerba Jan 03 2021 at 15:38

Masalah Anda pada dasarnya adalah bahwa Anda bingung tentang keadaan dan tindakan dalam pengaturan ini. Halaman web bukanlah negara bagian Anda; negara Anda adalah seluruh antrian prioritas (website-outlink)pasangan + (new_website-outlink)pasangan. Tindakan Anda adalah pasangan mana yang Anda pilih.

Sekarang ini adalah pengaturan masalah ruang-keadaan berukuran variabel dan ruang tindakan berukuran variabel pada saat yang sama. Untuk mengatasi hal ini mari kita mulai dengan mencatat bahwa state==observationkebutuhan tidak menjadi (secara umum). Jadi apa pengamatanmu? Pengamatan Anda adalah kumpulan berukuran variabel dari:

  1. (website-outlink)berpasangan atau
  2. next_website(di mana masing next_website- masing ditentukan oleh pasangannya yang sesuai)

Kedua pengamatan ini dapat berfungsi dengan baik, memilih di antara satu atau lainnya hanyalah masalah apakah Anda ingin agen Anda mempelajari "tautan mana yang harus dibuka sebelum membukanya" atau "tautan mana yang bermakna (setelah membukanya)".

Apa yang pada dasarnya dilakukan antrean prioritas Anda hanyalah menambahkan trik rapi yang:

  • Menyimpan kompleksitas komputasi untuk menjaga agar status tetap teratur (ingat bahwa status Anda bukanlah a website, tetapi daftar / kumpulan website-outlink)
  • Menghindari penghitungan ulang nilai-Q yang tidak perlu untuk setiap tindakan Anda (ingat bahwa tindakan bukanlah memilih tautan keluar dari new_website, tetapi memilih tautan keluar dari semua pilihan yang tersedia dalam antrean)

Namun perlu dicatat bahwa untuk benar-benar memiliki tabungan kedua, sangat penting untuk menyimpan nilai-Q untuk setiap pasangan !!!

Hal penting terakhir yang perlu diperhatikan adalah bahwa dalam skenario di mana Anda menggunakan Replay Buffer (yang saya kira kemungkinan besar diberikan bahwa Anda memilih DQN), Anda tidak dapat menggunakan antrian prioritas saat belajar dari RB. Untuk melihat mengapa (dan untuk melihat secara rinci bagaimana proses pembelajaran Anda sebenarnya terlihat), mulailah dengan mengingat bahwa pembaruan nilai-Q Anda diberikan oleh rumus di sini ; negara bagian Anda s_tadalah kumpulan pasangan (kuasi-dipesan 1 ). Q(s_t, a_t)hanyalah keluaran dari menjalankan regresi DQN Anda hanya pada situs web / pasangan terbaik dalam kelompok ini (Anda punyauntuk menambahkan indeks untuk menunjukkan pilihan terbaik saat menambahkan transisi ke RB, agar konsisten tentang tindakan mana yang diambil dari status ini). Untuk menghitung perkiraan nilai masa depan yang optimal, Anda harus menghitung ulang nilai Q dari setiap situs web / pasangan di status berikutnya. Anda TIDAK DAPAT menggunakan antrian prioritas saat berlatih dari RB.

1 Anda memiliki antrian prioritas yang dipesan untuk semua situs web yang Anda miliki di dalamnya saat melihat situs web terakhir, tetapi semua new_website-outlinkpasangan yang sekarang Anda tambahkan belum dipesan. Anda masih harus menjalankan agen pada mereka dan kemudian Anda dapat memesannya dengan sisa antrian prioritas untuk menghasilkan status berikutnya (yang masih tidak akan dipesan karena Anda akan memiliki new_new_website-outinkpasangan).