AlphaGo Zero: faz $Q(s_t, a)$ dominar $U(s_t, a)$ em estados de jogo difíceis?

Dec 03 2020

AlphaGo Zero

AlphaGo Zero usa um Monte-Carlo Tree Search onde a fase de seleção é governada por $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, Onde:

o parâmetro de exploração é $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (ou seja, a média dos valores $v_i$ de todas as simulações que passam pela borda $(s_t, a)$)
o parâmetro de exploração é $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (ou seja, a probabilidade anterior $P(s_t, a)$, ponderado pela constante $c_{puct}$, o número de simulações que passam por $(s_t, a)$, bem como o número de simulações que passam por $s_t$)

A probabilidade anterior $P(s_t, a)$ e valor de simulação $v_i$ são produzidos pela rede neural profunda $f_{\theta}(s_t)$:

Essa rede neural toma como entrada as representações brutas da posição e seu histórico no tabuleiro, e gera as probabilidades de movimento e um valor, (p, v) = fθ (s). O vetor de probabilidades de movimento p representa a probabilidade de selecionar cada movimento a (incluindo aprovação), pa = Pr (a | s). O valor v é uma avaliação escalar, estimando a probabilidade do jogador atual ganhar na posição s.

Minha confusão

Minha confusão é que $P(s_t, a)$ e $v_i$ são probabilidades normalizadas para distribuições diferentes, resultando em $v_i$ sendo cerca de 80x maior do que $P(s_t,a)$ na média.

As saídas da rede neural $(p, v)$, Onde $p$ é um vetor de probabilidade dado $s_t$, normalizado sobre todas as ações possíveis naquele turno. $p_a = P(s_t, a)$ é a probabilidade de escolher a ação $a$ determinado estado $s_t$. Um jogo de Go tem cerca de 250 movimentos por turno, então, em média, cada movimento tem probabilidade$\frac{1}{250}$, ie $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

Por outro lado, $v$ é a probabilidade de ganhar determinado estado $s_t$, normalizado em todas as condições de final de jogo possíveis (vitória / empate / derrota). Para simplificar, vamos supor$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, onde o jogo é jogado aleatoriamente e cada resultado é igualmente provável.

Isso significa que o valor esperado de $v_i$ é pelo menos 80x maior do que o valor esperado de $P(s_t, a)$. A consequência disso é que$Q(s_t, a)$ é pelo menos 80x maior do que $U(s_t, a)$ na média.

Se o acima for verdade, então a fase de seleção será dominada pelo $Q(s_t, a)$ termo, então AlphaGo Zero deve tender a evitar arestas sem simulações nelas (arestas onde $Q(s_t, a) = 0$) a menos que todos existentes $Q(s_t, a)$ termos são extremamente pequenos ($< \frac{1}{250}$), ou o MCTS tem tantas simulações que o $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ termo em $U(s_t, a)$equilibra as magnitudes dos dois termos. O último não é provável que aconteça, pois acredito que AlphaGo Zero usa apenas$1,600$ simulações por movimento, então $\sqrt{\sum_b N(s_t, b)}$ termina em $40$.

Selecionando apenas movimentos viáveis

Idealmente, o MCTS não deve selecionar todos os movimentos possíveis para explorar. Deve apenas selecionar movimentos viáveis dado estado$s_t$e ignorar todos os movimentos ruins. Deixar$m_t$ é o número de movimentos viáveis para o estado $s_t$, e deixar $P(s_t, a)$ = 0 para todos os movimentos $a$que não são viáveis. Além disso, vamos supor que o MCTS nunca selecione um movimento que não seja viável.

Em seguida, a seção anterior é parcialmente aliviada, porque agora $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. Como resultado,$Q(s_T, a)$ só deveria ser $\frac{m_t}{3}$ vezes maior que $U(s_t, a)$em média . Assumindo$m_t \le 6$, então não deve haver muito problema

No entanto, isso significa que AlphaGo Zero funciona idealmente apenas quando o número de movimentos viáveis é pequeno. Em estado de jogo$s_t$ onde há muitos movimentos viáveis ($>30$) (por exemplo, uma curva difícil com muitas escolhas possíveis), a fase de seleção do MCTS se deteriorará conforme descrito na seção anterior.

Questões

Acho que minhas perguntas são:

Meu entendimento está correto ou cometi erro (s) em algum lugar?
Faz $Q(s_t, a)$ geralmente domina $U(s_t, a)$por tanto na prática quando o estado do jogo tem muitos movimentos viáveis? A fase de seleção é geralmente dominada por$Q(s_t, a)$ durante esses estados de jogo?
O fato de que $Q(s_t, a)$ e $U(s_t, a)$ estar em ordens de magnitude tão diferentes (quando o estado do jogo tem muitos movimentos viáveis) afeta a qualidade do algoritmo MCTS, ou o MCTS é robusto para esse efeito e ainda produz políticas de alta qualidade?
Quão comum é para um estado de jogo ter muitos movimentos viáveis (> 30) no Go?

Respostas

2 DennisSoemers Dec 05 2020 at 03:08

Eu não acho que você necessariamente cometeu erros reais em seus cálculos ou qualquer coisa assim, tudo parece correto. Não consigo responder com segurança às suas perguntas sobre "X geralmente acontece?" ou "Quão comum é X?", teria que experimentar para ter certeza disso. Acho que também podemos responder imediatamente com segurança à pergunta sobre se o MCTS é robusto e ainda pode produzir políticas de alta qualidade com "sim", já que vimos resultados sobre-humanos de última geração em vários jogos usando essas técnicas .