AlphaGo Zero: tidak $Q(s_t, a)$ mendominasi $U(s_t, a)$ di negara bagian yang sulit?

Dec 03 2020

AlphaGo Zero

AlphaGo Zero menggunakan Pencarian Pohon Monte-Carlo di mana fase pemilihan diatur oleh $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, dimana:

parameter eksploitasi adalah $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (yaitu rata-rata nilai $v_i$ dari semua simulasi yang melewati edge $(s_t, a)$)
parameter eksplorasi adalah $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (yaitu probabilitas sebelumnya $P(s_t, a)$, dibobot oleh konstanta $c_{puct}$, jumlah simulasi yang lolos $(s_t, a)$, serta jumlah simulasi yang lolos $s_t$).

Probabilitas sebelumnya $P(s_t, a)$ dan nilai simulasi $v_i$ keduanya dikeluarkan oleh jaringan neural dalam $f_{\theta}(s_t)$:

Jaringan syaraf tiruan ini mengambil sebagai masukan representasi papan mentah dari posisi dan riwayatnya, dan mengeluarkan kemungkinan pergerakan dan nilai, (p, v) = fθ (s). Vektor probabilitas gerakan p mewakili probabilitas pemilihan setiap gerakan a (termasuk operan), pa = Pr (a | s). Nilai v adalah evaluasi skalar, memperkirakan kemungkinan pemain saat ini menang dari posisi s.

Kebingungan saya

Kebingungan saya adalah itu $P(s_t, a)$ dan $v_i$ adalah probabilitas yang dinormalisasi ke distribusi yang berbeda, menghasilkan $v_i$ menjadi sekitar 80x lebih besar dari $P(s_t,a)$ rata-rata.

Keluaran jaringan saraf $(p, v)$, dimana $p$ adalah vektor probabilitas yang diberikan $s_t$, dinormalisasi atas semua kemungkinan tindakan pada giliran itu. $p_a = P(s_t, a)$ adalah kemungkinan memilih tindakan $a$ negara tertentu $s_t$. Permainan Go memiliki sekitar 250 gerakan per giliran, jadi rata-rata setiap gerakan memiliki probabilitas$\frac{1}{250}$, yaitu $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

Di samping itu, $v$ adalah probabilitas untuk memenangkan negara bagian tertentu $s_t$, dinormalisasi pada semua kemungkinan kondisi akhir pertandingan (menang / seri / kalah). Demi kesederhanaan, mari kita asumsikan$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, di mana permainan dimainkan secara acak dan setiap hasil memiliki kemungkinan yang sama.

Artinya nilai yang diharapkan dari $v_i$ setidaknya 80x lebih besar dari nilai yang diharapkan dari $P(s_t, a)$. Konsekuensi dari ini adalah itu$Q(s_t, a)$ setidaknya 80x lebih besar dari $U(s_t, a)$ rata-rata.

Jika hal di atas benar, maka tahap pemilihan akan didominasi oleh $Q(s_t, a)$ istilah, jadi AlphaGo Zero harus cenderung menghindari tepi tanpa simulasi di dalamnya (tepi di mana $Q(s_t, a) = 0$) kecuali semua yang ada $Q(s_t, a)$ istilah sangat kecil ($< \frac{1}{250}$), atau MCTS memiliki begitu banyak simulasi di dalamnya sehingga $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ istilah dalam $U(s_t, a)$meratakan besaran kedua istilah tersebut. Yang terakhir sepertinya tidak akan terjadi karena saya percaya AlphaGo Zero hanya menggunakan$1,600$ simulasi per gerakan, jadi $\sqrt{\sum_b N(s_t, b)}$ tutup pada $40$.

Memilih hanya gerakan yang layak

Idealnya, MCTS tidak memilih setiap kemungkinan gerakan untuk dijelajahi. Itu seharusnya hanya memilih gerakan yang layak diberikan keadaan$s_t$, dan abaikan semua gerakan buruk. Membiarkan$m_t$ adalah jumlah langkah yang layak untuk negara bagian $s_t$, dan biarkan $P(s_t, a)$ = 0 untuk semua gerakan $a$itu tidak layak. Juga, mari kita asumsikan MCTS tidak pernah memilih langkah yang tidak layak.

Kemudian bagian sebelumnya sebagian diringankan, karena sekarang $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. Hasil dari,$Q(s_T, a)$ seharusnya hanya $\frac{m_t}{3}$ kali lebih besar dari $U(s_t, a)$rata-rata . Asumsi$m_t \le 6$, maka seharusnya tidak ada terlalu banyak masalah

Namun, ini berarti AlphaGo Zero bekerja secara ideal hanya jika jumlah gerakan yang layak sedikit. Dalam keadaan permainan$s_t$ di mana ada banyak gerakan yang layak ($>30$) (misalnya belokan yang sulit dengan banyak kemungkinan pilihan), fase pemilihan MCTS akan memburuk seperti yang dijelaskan di bagian sebelumnya.

Pertanyaan

Saya kira pertanyaan saya adalah:

Apakah pemahaman saya benar, atau apakah saya membuat kesalahan di suatu tempat?
Apakah $Q(s_t, a)$ biasanya mendominasi $U(s_t, a)$sebanyak ini dalam praktiknya ketika status permainan memiliki banyak gerakan yang layak? Apakah tahap seleksi biasanya didominasi oleh$Q(s_t, a)$ selama status game ini?
Apakah fakta itu $Q(s_t, a)$ dan $U(s_t, a)$ Berada dalam urutan yang berbeda besarnya (ketika keadaan permainan memiliki banyak gerakan yang layak) mempengaruhi kualitas algoritma MCTS, atau apakah MCTS kuat untuk efek ini dan masih menghasilkan kebijakan berkualitas tinggi?
Seberapa umum keadaan game memiliki banyak gerakan yang layak (> 30) di Go?

Jawaban

2 DennisSoemers Dec 05 2020 at 03:08

Saya tidak berpikir Anda telah membuat kesalahan nyata dalam perhitungan Anda atau semacamnya, yang semuanya tampak akurat. Saya tidak bisa benar-benar menjawab pertanyaan Anda dengan percaya diri tentang "Apakah X biasanya terjadi?" atau "Seberapa umum X?", harus bereksperimen untuk memastikannya. Saya rasa kami juga dapat dengan percaya diri segera menjawab pertanyaan tentang apakah MCTS kuat dan masih dapat menghasilkan kebijakan berkualitas tinggi dengan "ya", karena kami telah melihat hasil manusia super yang canggih dalam banyak game yang menggunakan teknik ini .