Dinâmicas de aprendizado de auto-jogo sem arrependimentos tornaram-se uma das principais maneiras de resolver jogos de grande escala na prática. Acelerar sua convergência ao melhorar o arrependimento dos jogadores sobre o limite ingênuo O (T) após T rodadas tem sido amplamente estudado nos últimos anos, mas quase todos os estudos assumem acesso a feedback de gradiente exato. Abordamos a questão de se a aceleração é possível apenas sob feedback de bandido e fornecemos uma resposta afirmativa para jogos de soma zero de forma normal com dois jogadores. Especificamente, mostramos que se ambos os jogadores aplicarem o algoritmo Tsallis-INF de Zimmert e Seldin (2018, arXiv: 1807. 07623), então seu arrependimento é no máximo O (c₁ T + c₂ T), onde c₁ e c₂ são constantes dependentes do jogo que caracterizam a dificuldade de aprendizado -- c₁ se assemelha à complexidade de aprender uma instância de bandido multi-armado estocástico e depende inversamente de algumas medidas de intervalo, enquanto c₂ pode ser muito menor do que o número de ações quando os equilíbrios de Nash têm um suporte pequeno ou estão próximos da fronteira. Em particular, para o caso em que existe um equilíbrio de Nash em estratégia pura, c₂ se torna zero, levando a um limite de arrependimento dependente da instância ótimo como mostramos. Além disso, provamos que neste caso, nosso algoritmo também desfruta de convergência na última iteração e pode identificar o equilíbrio de Nash em estratégia pura com complexidade de amostra quase ótima.
Ito et al. (Mon,) estudaram esta questão.