I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD. The core contribution here is the Nash equilibrium component to imperfect information games using only self-play. Note, there is no MCTS being done in this paper. This differs from counter factual regret methods (like the most famous Poker AIs) because it does not need to compute for all possible "information sets" which makes it intractable for even sufficiently complicated poker variants. It should also be noted (as they do in the paper) that this is more incremental than methodologically innovative as AlphaGo. This is the AlphaZero step increment to NeuRD. As is my general critique with their previous papers, they generally omit many engineering details that prove to be very important. Here, they admit that fine-tuning is vitally important (one of the 3 core steps) but details are relegated to the supplementary materials. It also opens up the question of if this new "fine-tuned" policy still guarantees the Nash equilibrium which it obviously does not as some mixed strategies are going to have sufficiently small probability. I wish researchers would be more honest with "this is a hack to get things to work on a computer because neural networks have floating point inaccuracies". It doesn't ruin any of the theory and no one is going to hold it against you. But it causes all sorts of confusion when trying to reimplement.
What I don't understand is why they don't try to make inferences about the opponent's private state. I get that the full Bayesian update is intractable, but some sort of RNN or LSTM should be able to produce pretty accurate estimates for the opponent's private info. And with self-play, you can train the deduction head of a NN by adding a KL-divergence between inferred and ex-post observed pieces. That would both make you guess better and also try and "jam" your opponent's inference by randomizing your own piece distribution.
This is an interesting avenue for future research. The reason why it is not as straightforward as you claim is because all inference is going to depend on your perception of their policy. That's why the Nash equilibrium is sought after first. Because you should assume your opponent is perfect until you start observing their suboptimal behavior that you can exploit. Additionally, you would also have to handle the meta part where the exploiting portion of the algorithm isn't itself being exploited by the opponent. Somehow, you should deviate slowly from the Nash equilibrium but revert quickly if the opponent is abusing your new strategy.
But their NN already outputs a policy conditional on public and private info! Why not have a separate intermediate branch in the NN that is fed with the current estimate of private info (for both players) and outputs the policies (again for both players) given those info estimates? Wouldn't it be possible to learn from that?
First, the neural network is taking the history of observations into account. We don't know what the NN has learned, but the NN is probably making some inference on likelihood of opponent piece locations. They haven't explicitly coded it to do that but it is difficult to imagine a human-level AI not doing this.
Second, what you are suggesting is probably best done as a secondary process outside of learning the Nash equilibrium. If you knew an opponent's policy, you would need to recalculate your optimal counterplay for that specific policy. This is completely orthogonal to the goal of this paper which is to learn the Nash equilibrium through self-play alone.
Bayesian play is not necessarily optimal for imperfect information games. The reason is: You don't only need to play optimally with respect to the information you have observed, you also need to hide your own information and balance those two needs.
See the Deep Mind "Player of Games" paper from last year for an agent that takes a more game theoretic approach, which is probably needed for "simpler" games like Poker, that we can play to higher levels of accuracy: https://arxiv.org/pdf/2112.03178.pdf
POMDPs is exactly how one formalizes imperfect information games. This is where the concept of information sets comes from. To answer your question, any two player algorithm is going to apply to single player games as it is trivial to transform. For games like 2048, the "adversary" is simply the opposite of your outcome. For games where you are trying to maximize your score, this is the standard RL setting and any of the Atari algorithms (including MuZero) can be used.
POMDPs? Are those considered to be much simpler problems?
Well, solving a Partially Observed Markov Decision Processes in general isn't just NP-complete but actually undecidable. So I'm not sure how one measures SOTA (state of the art).
It strongly depends on what type of structure you can assume and how expensive sampling is. Dreamerv2, agent57 on Atari, dreamerv2 and the generalized agent model trained on 600 tasks by deepmind might be worth looking into for different approaches on pomdps, but you can do much better if you impose physics priors by e.g. using neural ODEs for the latent state modeling.
POMDP just means "observations are not state" and that you need to use a stateful policy to infer the state somehow, but without further assumptions it's difficult to answer this question
Comments
I'm still trying to grok and implement the paper, but I studied AlphaGo/AlphaZero/MuZero during my PhD. The core contribution here is the Nash equilibrium component to imperfect information games using only self-play. Note, there is no MCTS being done in this paper. This differs from counter factual regret methods (like the most famous Poker AIs) because it does not need to compute for all possible "information sets" which makes it intractable for even sufficiently complicated poker variants. It should also be noted (as they do in the paper) that this is more incremental than methodologically innovative as AlphaGo. This is the AlphaZero step increment to NeuRD. As is my general critique with their previous papers, they generally omit many engineering details that prove to be very important. Here, they admit that fine-tuning is vitally important (one of the 3 core steps) but details are relegated to the supplementary materials. It also opens up the question of if this new "fine-tuned" policy still guarantees the Nash equilibrium which it obviously does not as some mixed strategies are going to have sufficiently small probability. I wish researchers would be more honest with "this is a hack to get things to work on a computer because neural networks have floating point inaccuracies". It doesn't ruin any of the theory and no one is going to hold it against you. But it causes all sorts of confusion when trying to reimplement.
What I don't understand is why they don't try to make inferences about the opponent's private state. I get that the full Bayesian update is intractable, but some sort of RNN or LSTM should be able to produce pretty accurate estimates for the opponent's private info. And with self-play, you can train the deduction head of a NN by adding a KL-divergence between inferred and ex-post observed pieces. That would both make you guess better and also try and "jam" your opponent's inference by randomizing your own piece distribution.
This is an interesting avenue for future research. The reason why it is not as straightforward as you claim is because all inference is going to depend on your perception of their policy. That's why the Nash equilibrium is sought after first. Because you should assume your opponent is perfect until you start observing their suboptimal behavior that you can exploit. Additionally, you would also have to handle the meta part where the exploiting portion of the algorithm isn't itself being exploited by the opponent. Somehow, you should deviate slowly from the Nash equilibrium but revert quickly if the opponent is abusing your new strategy.
But their NN already outputs a policy conditional on public and private info! Why not have a separate intermediate branch in the NN that is fed with the current estimate of private info (for both players) and outputs the policies (again for both players) given those info estimates? Wouldn't it be possible to learn from that?
First, the neural network is taking the history of observations into account. We don't know what the NN has learned, but the NN is probably making some inference on likelihood of opponent piece locations. They haven't explicitly coded it to do that but it is difficult to imagine a human-level AI not doing this.
Second, what you are suggesting is probably best done as a secondary process outside of learning the Nash equilibrium. If you knew an opponent's policy, you would need to recalculate your optimal counterplay for that specific policy. This is completely orthogonal to the goal of this paper which is to learn the Nash equilibrium through self-play alone.
Bayesian play is not necessarily optimal for imperfect information games. The reason is: You don't only need to play optimally with respect to the information you have observed, you also need to hide your own information and balance those two needs.
See the Deep Mind "Player of Games" paper from last year for an agent that takes a more game theoretic approach, which is probably needed for "simpler" games like Poker, that we can play to higher levels of accuracy: https://arxiv.org/pdf/2112.03178.pdf
What is the SOTA on solving non-adversarial (single player?) POMDPs? Are those considered to be much simpler problems?
POMDPs is exactly how one formalizes imperfect information games. This is where the concept of information sets comes from. To answer your question, any two player algorithm is going to apply to single player games as it is trivial to transform. For games like 2048, the "adversary" is simply the opposite of your outcome. For games where you are trying to maximize your score, this is the standard RL setting and any of the Atari algorithms (including MuZero) can be used.
In case you are wondering about cooperative multi-agent games, I would check this group's publications: https://www.cs.ox.ac.uk/people/publications/date/Shimon.Whit...
POMDPs? Are those considered to be much simpler problems?
Well, solving a Partially Observed Markov Decision Processes in general isn't just NP-complete but actually undecidable. So I'm not sure how one measures SOTA (state of the art).
You measure it by practical performance on a test suite of important POMDPs and games.
It strongly depends on what type of structure you can assume and how expensive sampling is. Dreamerv2, agent57 on Atari, dreamerv2 and the generalized agent model trained on 600 tasks by deepmind might be worth looking into for different approaches on pomdps, but you can do much better if you impose physics priors by e.g. using neural ODEs for the latent state modeling.
POMDP just means "observations are not state" and that you need to use a stateful policy to infer the state somehow, but without further assumptions it's difficult to answer this question