Bagaimana cara menangani gerakan yang tidak valid dalam pembelajaran penguatan?

20

Saya ingin membuat AI yang bisa memainkan lima-dalam-baris / gomoku. Seperti yang saya sebutkan dalam judul, saya ingin menggunakan pembelajaran penguatan untuk ini.

Saya menggunakan metode gradien kebijakan , yaitu REINFORCE, dengan baseline. Untuk perkiraan nilai dan fungsi kebijakan, saya menggunakan jaringan saraf . Ini memiliki lapisan convolutional dan sepenuhnya terhubung. Semua layer, kecuali untuk output, dibagikan. Lapisan output kebijakan memiliki $8 \times 8=64$ (ukuran papan) unit output dan softmax pada mereka. Jadi stochastic. Tetapi bagaimana jika jaringan menghasilkan probabilitas yang sangat tinggi untuk perpindahan yang tidak valid? Langkah tidak valid adalah ketika agen ingin memeriksa kotak yang memiliki satu "X" atau "O" di dalamnya. Saya pikir itu bisa macet dalam keadaan permainan itu.

Bisakah Anda merekomendasikan solusi untuk masalah ini?

Dugaan saya adalah menggunakan metode aktor-kritik . Untuk langkah yang tidak valid, kita harus memberikan hadiah negatif dan memberikan giliran kepada lawan.

machine-learning reinforcement-learning game-ai combinatorial-games Molnár István
sumber

10

Abaikan saja langkah yang tidak valid.

Untuk penjelajahan, Anda mungkin tidak akan hanya menjalankan langkah dengan probabilitas tertinggi, tetapi sebaliknya memilih gerakan secara acak berdasarkan probabilitas yang dihasilkan. Jika Anda hanya menghukum tindakan ilegal, mereka masih akan mempertahankan beberapa kemungkinan (betapapun kecilnya) dan karenanya akan dieksekusi dari waktu ke waktu (namun jarang). Jadi, Anda akan selalu mempertahankan agen yang sesekali melakukan tindakan ilegal.

Bagi saya lebih masuk akal untuk hanya mengatur probabilitas semua gerakan ilegal ke nol dan renormalisasi vektor output sebelum Anda memilih langkah Anda.

BlindKungFuMaster
sumber

Terima kasih. mungkin saya tidak jelas tetapi saya memilih langkah secara acak oleh probabilites yang dihasilkan. Saya akan mencoba saran Anda untuk mengatur probabilitas pergerakan ilegal menjadi nol dan melihat apa yang akan terjadi. Semoga harimu menyenangkan.

Molnár István

8

Biasanya metode softmax dalam metode gradien kebijakan menggunakan pendekatan fungsi linier menggunakan rumus berikut untuk menghitung probabilitas memilih tindakan $a$ . Di sini, bobot yang $\theta$ , dan fitur $\phi$ adalah fungsi dari keadaan saat ini $s$ dan tindakan dari serangkaian tindakan $A$ .

π (θ, a) = \frac{e^{θ ϕ (s, a)}}{\sum_{b \in A} e^{θ ϕ (s, b)}}

$\pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in A} e^{\theta \phi(s, b)}}$

Untuk menghilangkan gerakan ilegal, seseorang akan membatasi serangkaian tindakan hanya pada tindakan yang legal, karenanya $Legal(A)$ .

π (θ, a) = \frac{e^{θ ϕ (s, a)}}{\sum_{b \in L e g a l (A)} e^{θ ϕ (s, b)}}, a \in L e g a l (A)

$\pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \in Legal(A)} e^{\theta \phi(s, b)}}, \, a \in Legal(A)$

Dalam pseudocode rumusnya mungkin terlihat seperti ini:

action_probs = Agent.getActionProbs(state)
legal_actions = filterLegalActions(state, action_probs)
best_legal_action = softmax(legal_actions)

Baik menggunakan aproksimasi fungsi linear atau non-linear (jaringan saraf Anda), idenya adalah hanya menggunakan gerakan legal saat menghitung softmax Anda. Metode ini berarti bahwa hanya gerakan yang valid yang akan diberikan oleh agen, yang bagus jika Anda ingin mengubah permainan Anda nanti, dan bahwa perbedaan nilai antara pilihan tindakan terbatas akan lebih mudah untuk dibedakan oleh agen. Ini juga akan lebih cepat karena jumlah tindakan yang mungkin berkurang.

Jaden Travnik
sumber

Sangat berguna. Terima kasih telah memposting persamaan dan kodesemu!

DukeZhou

1

Matematika dan kodesemu tidak cocok di sini. Softmax atas probabilitas langkah hukum akan menyesuaikan probabilitas relatif. Misalnya (0,3, 0,4, 0,2, 0,1) disaring dengan item pertama dan ketiga dihapus akan menjadi (0,0, 0,8, 0,0, 0,2) dengan rumus Anda, tetapi akan menjadi (0,0, 0,57, 0,0, 0,42) menggunakan pseudocode. Pseudocode perlu mengambil log, sebelum perhitungan probabilitas tindakan.

Neil Slater

4

Bagaimana cara menghitung gradien versi Softmax yang difilter? Sepertinya ini akan diperlukan untuk backpropagation agar berhasil, ya?

brianberns

@brianberns Apakah Anda berhasil menemukan jawaban? Sepertinya itu akan menjadi masalah bagi saya tetapi entah bagaimana dalam contoh mainan saya, saya hanya mendapatkan jawaban yang benar ketika menggunakan probabilitas log dari softmax tanpa filter ...

mencoba

5

IMHO gagasan gerakan tidak valid itu sendiri tidak valid. Bayangkan menempatkan "X" pada koordinat (9, 9). Anda dapat menganggapnya sebagai langkah yang tidak valid dan memberinya hadiah negatif. Konyol? Tentu!

Tetapi sebenarnya gerakan Anda yang tidak valid hanyalah peninggalan dari representasi (yang itu sendiri mudah dan baik-baik saja). Perlakuan terbaik dari mereka adalah dengan mengeluarkan mereka sepenuhnya dari perhitungan apa pun.

Ini semakin nyata dalam catur:

Dalam representasi posisi, Anda dapat mempertimbangkan gerakan a1-a8, yang hanya termasuk dalam permainan jika ada Benteng atau Ratu di a1(dan beberapa kondisi lainnya berlaku).
Dalam representasi yang berbeda, Anda dapat mempertimbangkan langkah tersebut Qb2. Sekali lagi, ini mungkin atau bukan milik game. Ketika pemain saat ini tidak memiliki Queen, maka pastinya tidak.

Karena gerakan yang tidak valid lebih terkait dengan representasi daripada permainan, mereka tidak boleh dianggap sama sekali.

maaartinus
sumber

1

Poin yang bagus. Dalam permainan [M], yang dimainkan di Sudoku, kendala membuat banyak posisi (koordinat + nilai) ilegal setelah penempatan pertama. Tidak ada nilai dalam mempertimbangkan posisi ilegal ini dari sudut pandang penempatan, tetapi , lapisan strategis yang penting mengakui penempatan mana yang meminimalkan nilai posisi yang tersisa dan tidak dimainkan. (yaitu jika saya menempatkan 8 di sini, itu menghalangi lawan saya untuk menempatkan 8 di baris, kolom atau wilayah itu. Pada dasarnya, "berapa banyak posisi strategis yang dilepaskan penempatan ini dari gameboard?")

DukeZhou

5

Saya menghadapi masalah serupa baru-baru ini dengan Minesweeper.

Cara saya menyelesaikannya adalah dengan mengabaikan sepenuhnya gerakan ilegal / tidak valid.

Gunakan jaringan-Q untuk memprediksi nilai-Q untuk semua tindakan Anda (valid dan tidak valid)
Pra-proses nilai-Q dengan mengatur semua gerakan yang tidak valid ke nilai-Q dari angka nol / negatif (tergantung pada skenario Anda)
Gunakan kebijakan pilihan Anda untuk memilih tindakan dari nilai-Q yang disempurnakan (yaitu serakah atau Boltzmann)
Jalankan tindakan yang dipilih dan lanjutkan logika DQN Anda

Semoga ini membantu.

Sanavesa
sumber

1

Satu-satunya hal yang akan saya tambahkan ke ini adalah bahwa Anda harus ingat untuk melakukan backprop pada DQN ketika Anda menetapkan nilai Q untuk pasangan (s, a) ilegal ke nilai negatif besar sehingga dilatih untuk tidak memilih keadaan tersebut, tindakan berpasangan lain kali.

SN

Tapi saya bertanya-tanya apa pengaturan nilai target Q besar -ve lakukan untuk kontinuitas atau bentuk fungsi kerugian / kesalahan (sehingga mempengaruhi pencarian gradien). Apa pengalaman anda

SN

1

@SN Saya mengerti maksud Anda. Idenya adalah untuk memilih tindakan dengan nilai Q tertinggi yang bukan tindakan tidak valid . Selanjutnya, Anda menjalankan tindakan itu dan menggunakan tindakan itu dalam aturan pembaruan Anda (yaitu melatih DQN Anda untuk mendukung tindakan ini dalam jangka panjang). Apa yang dilakukan adalah membuat nilai-Q di masa depan dari tindakan yang dipilih menjadi lebih tinggi dan dengan demikian lebih menguntungkan. Ini TIDAK akan membuat tindakan ilegal nilai-Q lebih rendah, yang tidak masalah karena mereka selalu disaring (tidak dipertimbangkan). Beri tahu saya jika Anda ingin saya menjelaskan lebih banyak dengan contoh. :)

Sanavesa

1

@ Sanavesa tentu masuk akal, Anda pada dasarnya mengandalkan DQN akhirnya belajar apa pilihan yang benar melalui sekolah pukulan keras. Tetapi dalam situasi di mana hanya ada satu atau beberapa pilihan hukum Anda akan berakhir dengan pembelajaran yang sangat lambat. Pendekatan yang saya sarankan adalah cara memasukkan domain K ke dalam masalah untuk mempercepat pembelajaran itu. Ini juga apa yang saya pikir Anda lakukan di pos asli tempat Anda menulis "mengatur perpindahan tidak valid ke nilai-Q dari angka nol / negatif"

SN

1

@SNTepatnya! Kedua pendekatan memiliki kelebihan. Tergantung pada aplikasi jika lebih mudah untuk mempelajari langkah-langkah hukum atau langsung mengabaikannya. Untuk aplikasi besar yang kompleks, saya merasa mengabaikan langkah yang tidak valid jauh lebih cepat bagi agen untuk belajar, tetapi jangan mengutip saya tentang itu.

Sanavesa

Bagaimana cara menangani gerakan yang tidak valid dalam pembelajaran penguatan?

Jawaban: