Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings
Authors: Hengyuan Hu
Adam Lerer
Noam Brown
Jakob Nicolaus Foerster
Venue:  (2021)
Keywords: Search
partially observable games
multi-agent learning
Hanabi

Abstract: Search is an important tool for computing effective policies in single- and multi-agent environments, and has been crucial for achieving superhuman performance in several benchmark fully and partially observable games. However, one major limitation of prior search approaches for partially observable environments is that the computational cost scales poorly with the amount of hidden information. In this paper we present Learned Belief Search (LBS), a computationally efficient search procedure for partially observable environments. Rather than maintaining an exact belief distribution, LBS uses an approximate auto-regressive counterfactual belief that is learned as a supervised task. In multi-agent settings, LBS uses a novel public-private model architecture for underlying policies in order to efficiently evaluate these policies during rollouts. In the benchmark domain of Hanabi, LBS obtains more than 60% of the benefit of exact search while reducing compute requirements by 35×, allowing it to scale to larger settings that were inaccessible to previous search methods.

Under review as a conference paper at ICLR 2021
LEARNED BELIEF SEARCH: EFFICIENTLY IMPROVING POLICIES IN PARTIALLY OBSERVABLE SETTINGS
Anonymous authors Paper under double-blind review
ABSTRACT
Search is an important tool for computing effective policies in single- and multi- agent environments, and has been crucial for achieving superhuman performance in several benchmark fully and partially observable games. However, one major limitation of prior search approaches for partially observable environments is that the computational cost scales poorly with the amount of hidden information. In this paper we present Learned Belief Search (LBS), computationally efficient search procedure for partially observable environments. Rather than maintaining an exact belief distribution, LBS uses an approximate auto-regressive counterfac- tual belief that is learned supervised task. In multi-agent settings, LBS uses a novel public-private model architecture for underlying policies in order to effi- ciently evaluate these policies during rollouts. In the benchmark domain of Han- abi, LBS obtains more than 60% of the benefit of exact search while reducing compute requirements by 35x, allowing it to scale larger settings that were inaccessible to previous search methods.
INTRODUCTION
Search has been a vital component for achieving superhuman performance in a number of hard benchmark problems in AI, including Go (Silver et al., 2016 2017 2018). Chess (Campbell et al.) 2002), Poker (Moravčík et al. 2017: (Brown & Sandholm 2017 |017]22099 2019). and, more recently, self-play Hanabi (Lerer et al. 2020). Beyond achieving impressive results, the work Hanabi and Poker are some the few examples of search being applied in large partially observable settings. In contrast, the work on belief-space planning typically assumes small belief space, since these methods scale poorly with the size of the belief space.
Inspired by the recent success of the SPARTA search technique in Hanabi (Lerer et al. 2020 we propose Learned Belief Search (LBS) a simpler and more scalable approach for policy improvement in partially observable settings, applicable whenever model of the environment and the policies of any other agents are available at test time. Like SPARTA, the key idea is to obtain Monte Carlo es- timates of the expected return for every possible action in given action-observation history (AOH) by sampling from a belief distribution over possible states of the environment. However, LBS ad- dresses one of the key limitations of SPARTA. Rather than requiring a sufficiently small belief space, in which we can compute and sample from an exact belief distribution, LBS samples from a learned, auto-regressive belief model which is trained via supervised learning (SL). The auto- regressive parameterization of the probabilities allows LBS to be scaled to high- nigh-dimensional state spaces, whenever these are composed as a sequence of features.
Another efficiency improvement over SPARTA is replacing the full rollouts with partial rollouts that bootstrap from a value function after specific number of steps. While general this value function can be trained via SL in separate training process, this is not necessary when the blueprint (BP) was trained via RL. In these cases the RL training typically produces both a policy and an approximate value function (either for variance reduction for value-based learning). In particular, it is common practice to train centralized value functions, which capture the required dependency on the sampled state even when this state cannot be observed by the agent during test time.
While LBS is a very general search method for Partially Observable Markov Decision Pro- cesses (POMDPs), our application is focused single-agent policy improvement in Decentralized

---

Under review as a conference paper at ICLR 2021
POMDPs (Dec-POMDPs) (in our specific case, Hanabi). One additional challenge of single-agent policy improvement in Dec- Pec-POMDss is that, unlike standard POMDPs, the Markov state s of the environment is longer sufficient for estimating the future expected return for a given AOH of the searching player. Instead, since the other players' policies also depend on their entire action- observation histories, e-g., via Recurrent-Neural Networks (RNNs), only the union of Markov state and all AOHS is sufficient.
This in general makes it challenging apply LBS, since it would require sampling entire AOHs, rather than states. However, in many Dec-POMDPs, including Hanabi, information can be split between the common- -nowlede (CK) trajectory and private observations. Furthermore, commonly information is 'revealing', such that there is a mapping from the most recent private observation and the CK trajectory to the AOH for each given player. these settings it sufficient to track belief over the union of private observations, rather than over trajectories, which was also exploited in SPARTA. We adapt LBS to this setting with novel public-RNN architecture which makes replaying games from the beginning, as was done in SPARTA, unnecessary.
When applied to the benchmark problem of two player Hanabi self-play, LBS obtains around 60% of the performance improvement of exact search, while reducing compute requirements by up to 35x. We also successfully apply LBS to a six card version of Hanabi, where calculating the exact belief distribution would be prohibitively expensive.
RELATED WORK
2.1 BELIEF MODELING & PLANNING IN POMDPS
Deep RL on POMDPs typically circumvents explicit belief modeling by using a policy architecture such as an LSTM that can condition its action on its history, allowing it to implicitly operate on belief states (Hausknecht Stone 2015). 'Blueprint' policies used in this (and prior) work take that approach, but this approach does not permit search since search requires explicitly sampling from beliefs in order to perform rollouts.
There has been extensive prior work on learning and planning in POMDPs. Since solving for op- timal policies in POMDPs intractable for all but the smallest problems, most work focuses on approximate solutions, including offline methods to compute approximate policies well as ap- proximate search algorithms, although these are still typically restricted to small grid-world envi- ronments (Ross al. 2008).
One closely related approach is the Rollout algorithm (Bertsekas & Castanon 1999). which given an initial policy, computes Monte Carlo rollouts of the belief-space MDP assuming that this policy is played going forward, and plays the action with the highest expected value. In the POMDP setting, rollouts occur in the MDP induced by the belief states
There has been some prior work on search in large POMDPs. Silver & Veness (2010) propose a method for performing Monte Carlo Tree Search large POMDPs like Battleship and partially- observable PacMan. Instead of maintaining exact beliefs. they approximate beliefs using a particle filter with Monte Carlo updates. Roy et al.) (2005) attempt to scale large belief spaces by learning a compressed representation of the beliet's and then performing Bayesian updates in this space.
Most recently MuZero combines RL and MCTS with a learned implicit model of the environ- ment (Schrittwieser et al., 2019). Since recurrent models can implicitly operate on belief states in partially-observel environments, MuZero in effect performs search with implicit learned beliefs as well as learned environment model.
2.2 GAMES HANABI
Search has been responsible for many breakthroughs benchmark games. Most of these successes were achieved in fully observable games such as Backgammon (Tesauro) 1994), Chess (Campbell
al. 2002) and Go (Silver al. 2016 2017 2018). More recently, belief-based search techniques
SPARTA's single agent search uses similar strategy in the DEC-POMDP setting, but samples states from the beliefs rather than doing rollouts directly in helief space.
2

---

Under review as a conference paper at ICLR 2021
have been scaled to large games, leading to breakthroughs in poker (Moravčík al. 2017 Brown & Sandholm, 2017 2019) and the cooperative game Hanabi (Lerer et al. 2020). as well as large improvements in Bridge Tian et al. 2020).
There has been a growing body of work developing agents in the card game Hanabi. While early hobbyist agents codified human conventions with some search (O'Dwyer 2019 Wu 2018). more recent work has focused on Hanabi as a challenge problem for learning in cooperative partially- observed games (Bard et al., 2020). In the self-play setting (Iwo copies of the agent playing gether), the Bayesian Action Decoder (BAD) was the first learning agent (Foerster et al. 2019),
which was improved upon by the Simplified Action Decoder (SAD) (Hu & Foerster 2022). The state-of-theearr in Hanabi self-play is achieved by the SPARTA Monte Carlo search algorithm ap- plied to the SAD blueprint policy (Lerer et al. 2020).
There has been recent work on ad-hoc team play and zero-shot coordination, in which agents are paired with unknown partners (Canaan al. 2019 Walton Riverss et al. 2017 Hu al. 2020).
3 SETTING AND BACKGROUND
In this paper consider Dec-POMDP, in which N agents each take actions at at each timestep, after which the state 8t updates to 8++1 based on the conditional probability P($2+1/s, a,) and the agents receive (joint) reward r(st, ae), where a, is the joint action of all agents.
Since the environment is partially observed each agent only obtains the observation of = Z i) from a deterministic observation function Z. We denote the environment trajectory Ti {s0, ...,.. } and the action-observation history (AOH) of agent i as T| = (%): ab..., oj aij. The total forward looking return from time & for trajectory T is R²(r) = Eeze7 7" "r(s,, at), where 7 is optional discount factor. Each agent chooses policy <7(r") conditioned on its AOHs, with the goal that the joint policy = { maximises the total expected return Jx ((T)
Starting from a common knowledge blueprint (BP), i.c. predetermined policy that is known to all players, in order perform search in a partially observable setting, agents will need main- tain beliefs about the state of the world given their observations. We define beliefs ('(r)) P((s,, { IT?), which is the probability distribution over states and AOHs, given player i's pri- vate trajectory. Note that in Dec-POMDPs the beliefs must model other agents' AOHs as well as the current state, since in general the policies of other players condition on these AOHs.
In general. the domain of Bi (the range) is extremely large, but in Dec-POMDPs with a limited amount of hidden information there is often games like Hanabi, the range consists of the unobserved cards in players' hands. SPARTA (Lerer al. (2200) assumed that the domain was small enough be explicitly enumerated. In our case, we assume that the beliefs are over private features I' that can be encoded as a sequence of tokens from some vocabulary: f = II, fj E V. Furthermore, simplifies the algorithm if, as is typically the case, we can factor out these private features from т to produce a public trajectory 7rub, then )N.
compact representation. For example, in card
each 7' can be specified by the pair (rPub, f() and by (rruh,
LBS is applicable to general POMDPs, which are a natural corner case of the Dec-POMDP formal- ism when we set the number of players to I.
4 METHOD
The starting point for our method is the single-agent search version of SPARTA (Lerer et al. 2020 Given a set of BP policies, n', we estimate expected returns, Q(a² /7"), by sampling possible trajec- tories from belief conditioned on r':
Q(a'1r+) (inp(rrre((("11)
3

---

Under review as a conference paper at ICLR 2021
SPARTA
LBS
P1 private observation history
PI private
Belief' Model
observation history
Possible Hidden States
Sumpled P2 hand history
33% 3
GD
1
Sampled P2 hand
pride (Br)
50% 3
As (4)
3
Play
Biacard Red
Apmie
4
16%
Notal notiou
puttor
Masto yallour
Play Gaod 1 Full pulbur
Disord Cazd Full riloor
Hint Red Full kullout
max (s)
23.8
22.4
24.6
Final Sovres:
24
22
25
Figure/ 1: Comparison of SPARTA Lerer et al. 2020 and LBS (ours). SPARTA maintains explicit belief distribution with an accompanying AOH h2 for each helief state. LBS uses an auto-regressive helief model sample states from the belief distribution, given the AOH. AOHs do not need to be maintained for each belief state in LBS since the model only relies the public trajectory. Additionally. LBS uses N-step rollout followed by a bootstrap value estimate.
Here ((a7 (r) is the expected return for playing action a² given the history T:
(aal(r) Ep' R R (T'),
where 1t' (7') is the Monte Carlo forward looking return from time t.
Whenever the argmax of ((a"(r') exceeds the expected return of the BP, Q(aBplT'), by more than a threshold 6, the search-player player deviates from the BP and plays the argmax instead. For more details, please see Figure | (LHS) and the original paper.
Even though this is single-agent search, in SPARTA this process is costly: First of all, the belief P(r|r') is an exact counterfactual belief, which requires evaluating the BP at every timestep for every possible
identify which of these are consistent with the actions taken by the other agents. Secondly, to estimate R (T') SPARTA plays full episodes (rollouts) until the end of the game.
Lastly, since in Dec-POMDPs policies condition on full AOHs (typically implemented via RNNs) the games have to be replayed from the beginning for each of the sampled r to obtain the correct hidden state, (())())), for all players i, for each of the sampled trajectories, т.
Learned Belief Search addresses all of these issues: First of all, rather than using costly exact beliefs, we use supervised learning (SL) to train an auto-regressive belief model which predicts P(r(r*). As described in Section 3 in our setting this reduces to predicting the private observations for all other players f since the public trajectory is known. We use an auto-regressive model to encode the private observations as it can be decomposed to sequence tokens - -I, II, 1, For scalability, as illustrated in Figure 2 (RHS), the auto-regressive belief model parameterized by neural network with weights Ø:
Pazact ( (S - ((
(3)
Secondly, to avoid having to unroll episodes until the end of the game to bootstrap the expected return after a predefined number, N, of steps. While this value function in general needs be trained via SL, this is not necessary in our setting: Since our BPs are recurrent DQN agents that learn an approximate expected return via value-decomposition networks (VDN), can directly use the BP estimate the expected return, as illustrated in Figure (B):
learned value function
4+N
R((T')2
Σ rv r Tn pub '
(4)
K=t
4

---

Under review as a conference paper at ICLR 2021
(A)
Policy Model
B
Auto Regreesive Belief Model (trsined by SL on final agenta)
(trained by RLJ
Action Q Values
Sompled Hidden Info (Player Hand)
Ply Card 24,0
Red Disaré Card
Regrreasive Decoder
Dueling Net
5
3
Docodlr LSTM
Decodor LSTM
Decador LSTM
1STM
MLP
Ag hikenry encodding
Public Observations Board carda, discards, commson Indge
Private Observations (Partiser' hand)
Encoder LSTM
beliefal
Player's Public
Private Observations
Figure 2: (A): Illustration of the public-LSTM network used for the BP policy. (B): The auto-regressive network for modeling beliefs.
This is fairly general insight, since RL training in POMDPs commonly involves centralized value functions that correctly capture the dependency of the expected return on the central state.
Lastly, we address challenge that is specific to Dec-POMDPS To avoid having to re-unroll the policies for the other agents from the beginning of the game for each of the sampled т, LBS uses a specific RNN architecture. Inspired by other public-private methods (Foerster et al. 2019: Kovařík et al. 2019 Horák& & Bošansky 2019), we exploit that the public trajectory in combination with the current private observation contains the same information the entire private trajectory and only feed the public information ypub into the RNN. The public hidden state h(7p"")) is then combined with the private observation f through a feedforward neural network, as illustrated in Figure
(LHS).
. (Tt) + π (h(T?""))
(5)
We note that whenever it is possible to factor out the public trajectory, this architecture can be used. not, LBS can still be used, but instead for each sampled fr we would need reconstruct the entire game from scratch to obtain the correct model state.
We also point out that in this paper we only consider single player search where all others act according to the BP. Carrying out search for more than one player would not be theoretically sound because the trained belief model would no longer be accurate. Crucially, the learned belief model can only provide accurate implicit belief's when the other players are playing according to the blueprint policy, because the belief model is trained before any agent conducts search. As a consequence, doing independent LBS for multiple players at the same time would lead to inaccurate beliefs and hence could lower the performance Further details, including specific architectures, of our three innovations are included in Section 5
EXPERIMENTAL SETUP
We evaluate our methods in Hanabi, a partially observable fully cooperative multi-stpp game. In Hanabi, there are 5 different colors and 5 different ranks. Each card may have one or more copies in the deck. All players are of the same team trying to finish 5 stacks of cards, one for each color. They need to play the cards in order from to as in Solitaire. The main challenge in Hanabi is that each player can only see other players' cards, not their own. Players have to use limited number of hint tokens to reveal information for their partners and form conventions or use theory mind reasoning to convey information more efficiently. Please refer to Appendix B for more details Hanabi. For simplicity we focus on 2-player Hanabi for all our experiments and note that straightforward to extend our method any number of players.
5

---

Under review as a conference paper at ICLR 2021
5.1 BLUEPRINT TRAINING
As explained in Section 3 the public and private observations in Hanabi can be factorized into public and private features. We modify the open-source Hanabi Learning Environment (HLE) (Bard al. 2020) to implement this. Here, the only private observation is the partner's ' hand, while all other information public. There are many different options for implementing the Public-RNN concept. We end up with the design shown in Figure (A). Specifically, the LSTM only takes public features as input while an additional MLP takes in the concatenation of private and public features. The outputs of the two streams are fused through element-wise multiplication before feeding into the dueling architecture (Wang et al. 2016) to produce Q values. We have also experimented with other designs such as using concatenation in place of the element-wise multiplication, feeding only private observation to the MLP. Empirically we find that the design chosen performs the best, achieving the highest score in self-play
To train our BP with reinforcement learning, we base our implementation on the open-source code of Other-Play (Hu et al. 2020), which includes several recent advancements for RL in Hanabi. We follow most their practices such as value decomposition network, color shuffling and auxiliary tasks. We also leave their spprr-parrmeters unchanged. For completeness, we include detailed description of experimental setup and hyper-parameters in Appendix C
5.2 BELIEF LEARNING
The belief model is trained to predict the player's own hand given their action observation history. An overview of the architecture is shown in the right panel of Fig 2 An encoder LSTM converts the sequence of observations to a context vector. The model then predicts its own hand in an auto- regressive fashion from oldest card to newest. The input at each step is the concatenation of the context vector and the embedding of the last predicted card. The model is trained end-to-end with maximum likelihood:
L(ctml/T
Σ logplal7,e1a-))
(6)
where n is the number of cards in hand and is the i-th card.
We use setup similar to that of reinforcement learning to train the belief model instead of a more traditional way of creating fixed train, test and validation set. We use trained policy and large number of parallel Hanabi simulators to continuously collect trajectories and write them into a replay buffer. In parallel This helps us easily avoid over-fitting without manually tuning aperrparameters and regularization. The RL policy used to generate data is fixed during the entire process.
sample from the replay buffer to train the belief model using supervised loss.
5.3 LBS IMPLEMENTATION DETAILS
Learned Belief Search is straightforward once we have trained BP and a belief model. The search player samples hands from the belief model and filters out the ones that are inconsistent with current game status based on their private observation. In the extremely rare case where the belief model fails to produce a sufficient number legal hands, it reverts back to the BP. To understand the impact of various design parameters, we experimented with both playing out all trajectories until the end of the game, LBS-inf, as well as rolling out for a fixed number of steps, LBS-k and using bootstrapped value estimate at the final state. Similar SPARTA, the search actor only deviates from the BP if the expected value of the action chosen by search 5 = 0.05 higher than that of the BP and UCB-like pruning method used reduce the number of samples required.
RESULTS
Belief Quality. We first examine the quality of the learned belief model by looking at its cross en- tropy loss for predicting hidden card values. We compare against two benchmarks: the exact beliefs marginalized over each card, and an auto-regressive belief based only on grounded information. The grounded belief predicts a distribution over card values proportional to remaining card counts, for all card values consistent with past hints. A formal definition is provided in Appendix A

---

Under review as a conference paper at ICLR 2021
card Hanabi
6 card Hanabi
24.2
*6
16
24.0
o<
16
nf
Score
Average Score
24.75
23.6
24.70
23.4
24.65
Glueprint (RL)
Exact Search ISPARTA! LBS (Ours)
Search (SPARTA)
24.60
23.0
LBS (Ours)
Blueprint
50
100
125
150
175
100
1675
1700
1725
Time/ game
Time game
Figure 3: Comparison of speed and average score of different policies in 5-card (left) and 6-card (right) Hanabi. The number next each LBS data point the rollout depth. LBS with different rollout depths provide a tunable tradeoff' between speed and performance. LBS provides most of the performance benefits of exact search (SPARTA) at a fraction (5-card vs 6-card).
compute cost, speedup grows with the size belief space
Method
Time
RL-1H
RL-5H
RL-10H
RL-20H
Blueprint SPARTA
<Is
15.38
22.99
23.70
24.08
215s
19.53
24.16
24.39
24.52
LBS-inf
121s
18.88
23.95
24.29
24.42
LBS-32
84s
19.05
24.01
24.31
24.45
LBS-16
47s
19.27
24.04
24.29
24.48
LBS-8
25g
19.14
24.03
24.28
24.43
LBS-1
6s
17.99
23.69
24.06
24.26
Table 1: Average scores in 2-player Hanabi with different search variants. Time column shows the average wall-clock time of each method to play game. Columns of RL-KH show performance of different methods applied blucprint policies trained for different amounts of time. Each cell contains the mean averaged over 5000 games. Please refer to Appendix D for the complete version of the table that includes the standard mean, percentage of perfect games, and more test scenarios. LBS variants achieve substantial fraction of the policy improvements of SPARTA over the blueprint at a lower computational cost.
We generate 1000 games with our trained RL pol- icy and compute the two benchmarks together with the loss of the learned belief (Eq. 6 from fully trained belief model. Figure 4 shows how these values change over the course of games. We see that our learned belief model performs considerably bet- than the grounded belief. There is still gap be- tween learned belief' and exact belief, especially in the later stage of the game. More powerful models such as transformers /Vaswani et al., (017) may fur- ther improve the belief learning but we leave it for future work.
Grounded Belsf
Corm 40m
Figure summarizes the speed/performance tradeoffs of LBS compared to running an RL policy directly or using an exact search method (SPARTA). In 5-card Hanabi (left). we start with a blueprint policy that achieves an average score of 22.99 after hours of training, and apply LBS with different rollout lengths well exact search. LBS achieves most of the score improvement exact search while being much faster to execute. Changing the rollout depth allows for tuning speed performance. As move larger game (6-card Hanabi), SPARTA
Performance.
Figure 4: Per-card cross entropy with the true hand for different beliefs in games played by BP.

---

Under review as a conference paper at ICLR 2021
LS5-nt
244
Baagrn
26.1
242
242
Austag Stove
20.
23.
24.1
23.4
212
Bisepint Lt5-ed
123
919
985 11/13
12j0K 16/5K
4j57
apoc
[RL] Bolefi Tainnn Time (Hour))
(SearchD:pch INumScarcPP: Stopt The Time (Hours)
(a) Fixed Model Training Budget
(b) Fixed Search Budget
Figure 5: (a) Result fixed budget (24 Hours) at training time. The ticks "alb"on onn x-axis means a hours train BP and hours to train belief model. (b) Result of fixed budget test time. The ticks "a on x-axis means run search for steps before bootstrapping with Q function and run search per Each data point on both figures is evaluated on 5000 games and the shaded area is the standard error of mean.
becomes 10x slower while LBS runs at approximately the same speed and continues to provide similar fraction of the performance improvement.
A more comprehensive analysis of these tradeoff's is shown in Table T We train the BP with RL for 40 hours in total and use snapshots dubbed RL-KH which have been trained for 1, 5, 10, 20 and 40 hours showcase the performance of method given different BPs of different strength. Note that in Table we only show results on 4 snapshots for conciseness. A more complete version of the table with standard error of (s.e.m.) and more data points can also be found in Table in Appendix D The belief models are trained to convergence for each BP. For comparison, we rerun SPARTA on our models which can be seen as a expensive upper bound for LBS. All search methods run 10K rollouts per step. The best performing LBS variant is LBS-16, delivering 86% (on ROH) to 94% (on RH- of the improvement comparing to the exact search while being 4.6x faster. Even the cheapest method, LBS-1, returns decent improvement of 45% on average and 35.8 speedup. It also worth noting that LBS performs strongly even on a quite poor RL policy, RL- HH, demonstrating high versatility of the method.
We note that the more expensive LBS-inf not the best performing one, consistently under- performs some of the LBS-k versions by small, in many cases significant, amount. We hypothesis that under LBS-inf is more likely for the agents to reach a state that is under-explored during training. Therefore the approximate belief will be less accurate and the estimate Q-value be wrong. The LBS-k method where the Q-value after k steps is as a bootstrap may naturally avoid those situations since the BP may also have low Q values for under-explored states. One piece of evidence for this theory is that in LBS-inf, 0.1 % of the games end up with a completely failed belief prediction and have to revert back BP while the same only happens 0.0083% of the games for LBS-k.
Clearly, this is a potential problem: part of the reason search works well is that it can discover moves that were underestimated and, consequently, under-explored by the BP. The brittleness of the learned belief, in combination with the difference in overall belief quality (Fig 4), help explain the difference performance between LBS and exact methods like SPARTA.
Fixed Budget Training & Testing. Since one of the motivations for LBS is speed, it would be inter- esting to know how we could allocate resources training and test time to maximize performance given a fixed computational budget. For fixed training budget, we train the BP for / hours and then train belief model for 24- hours. We evaluate these combinations with LBSSinf as well as BPs themselves. As shown in Figure Sal with longer RL training, the BP improves monotonically, but the final performance suffers due to poor belief model. The best combination 18 hours for RL and ~66 hours for belief learning.
We then take the models from the best combination to study how to allocate compute between the number of rollouts and rollout depth. We start with LBS-1 and 128K search per step, and then halve the number of searches as we double the search depth. The result shown Figure (5b] we compare the results here with those from Table I
that although LBS-16 still has the best
8

---

Under review as a conference paper at ICLR 2021
Blueprint
SPARTA
LBS-32
LBS-16
Performance
24.57 = 0.01
24.82 + 0.01
24.76 + 0.01
24.76 + 0.01
75.94%
87.80%
84.12%
84.06%
Run Time
<1s
1747s
74s
42s
Table 2: Result on 6-card Hanabi variant. Each cell contains the mean and standard error of mean over 5000 games in the first row and percentage of perfect games (25 points) in the second row.
performance, the relative strength between LBS-32 and LBS-8 flips, indicating that the trade-off may still matter in some cases.
Extension 6-card Hanabi.
To further demonstrate the scalability LBS compared to SPARTA, we test them on modified version of Hanabi where each player holds 6 cards instead of 5. This is an official variant of Hanabi and is easier to achieve high score than the standard form due to more choices at each turn and shorter episode length. We train the BP and belief model with the same method. The results are shown in Table 2 The SPARTA method runs 8x slower than it does on standard Hanabi while LBS runs faster due to shorter games, delivering 76% of the improvement with 42 less time.
7 CONCLUSION
We presented Learned Belief Search, a novel search algorithms for POMDPs that can be used to improve upon the performance of blueprint policy at test time whenever simulator of the environ- ment is available. We also presented extensions of LBS that make it applicable to fully cooperative, partially observable multi-agent settings. The heart of LBS is auto-regressive model that can be used to generate samples from an approximate belief for any given AOH.
While LBS achieves strong performance on the benchmark problem Hanabi, our work also clearly points to number of future directions. For a start, the search process can bring the belief model to under-explored regions of the state space. This could be addressed by retraining the belief model on the data generated from LBS.
Another interesting direction for future work is to amortize the search process, egg. by integrating into the training process, and to extend LBS to multiplayer and multi-step search. To enable these directions, and many others, we plan to open-source all of the code for LBS.
REFERENCES
Nolan Bard, Jakob N. Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H. Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, lain Dunning, Shibl Mourad, Hugo Larochelle, Mare G. Bellemare, and Michael Bowling. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280:103216, 2020. ISSN 0004-3702.
Dimitri P Bertsekas and David A Castanon. Rollout algorithms for stochastic scheduling problems. Journal of Heuristics, 5(1):99-108; 1999.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: top professionals. Science, pp. eaaol733, 2017.
Libratus beats
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, pp. eaay2400, 2019.
Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep Blue. Artificial intelligence, 134 (1-2):57-83, 2002.
Rodrigo Canaan, Julian Togelius, Andy Nealen, and Stefan Menzel. Diverse agents for ad-hoc cooperation in hanabi. In IEEE Conference Games 2019, CoG 2019, IEEE Conference

---

Under review as a conference paper at ICLR 2021
Computatonal Intelligence and Games, CIG. IEEE Computer Society, August 2019. doi: 10. 1109/CIG, 8847944. 2019 IEEE Conference on Games, CoG 2019; Conference date: 20- 08-2019 Through 23-08-2019.
Jakob Foerster, Francis Song, Edward Hughes, Neil Burch, lain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent re- inforcement learning. In International Conference on Machine Learning, pp. 1942-19511 2019.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. In 2015 AAAI Fall Symposium Series, 2015.
Karel Horák and Branislav Bošanský. Solving partially observable stochastic games with public observations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp- 2029-2036, 2019.
Hengyuan Hu and Jakob N Foerster. Simplified action decoder for deep multi-agent reinforcement learning. In International Conference on Learning Representations, 2020. URL https://
openrevi eww. wwwp:/ee/oorrummmmmm
xm3RVt.B.
Hengyuan Hu, Alexander Peysakhovich, Adam Lerer, and Jakob Foerster. "other- forr zero-shot coordination. In Proceedings of Machine Learning and Systems 2020, pp. 9396-9407. 2020.
Steven Kapturowski, Georg Ostrovski, Will Dabney, John Quan, and Remi Munos. Recurrent
perience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019. URL
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprini 1rXiv: 2014.
Vojtéch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisy. Rethinking formal models of partially observable multiagent decision making. arXiv preprint 1906. 2019.
Adam Lerer, Hengyuan Hu, Jakob N Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In AAAI, pp. 7187-7194, 2020.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, (56(6337):508--555 2017.
Arthur O'Dwyer. Hanabi. hnttps:///ittubb.ccmm httpc//mmmmuuuuuuuuousseeeeeeeee
2019.
Stéphane Ross, Joelle Pineau, Sébastien Paquet, and Brahim Chaib-Draa. Online planning algo- rithms for pomdps. Journal of Artificial Intelligence Research, 32:663-704, 2008.
Nicholas Roy, Geoffrey Gordon, and Sebastian Thrun. Finding approximate pomdp solutions through belief compression. Journal of artificial intelligence research, 23:1-40 2005.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized Experience Replay. arXiv e-prints, art. arXiv: 151.0555 Nov 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv: 191.0269 2019.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in neural infor- mation processing systems, pp. 2164 2172, 2010.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 429 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang. Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):3544 2017.
10

---

Under review as a conference paper at ICLR 2021
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362 1144, 2018.
Gerald Tesauro. TD-Gammon, a self-teaching backgammon program, achieves master-level play. Neural computation, 6(2):215-219 1994.
Yuandong Tian, Qucheng Gong, and Tina Jiang. Joint policy search for multi-agent collaboration with imperfect information. arXiv preprint arXiv:2008.0649)) 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neu- ral Information Processing Systems 30, pp. 5998-6008. Curran Associates, Inc., 2017. URL http://papens nips wwtp:cpppppppcc.peee attention- -aa---alll---------- you-oouueeee pdf
Joseph Riienn- Piers R Williams, Richard Bartle, Diego Perez-Liebana, and Simon M Lucas. Evaluating and modelling aanabi-playing agents. In /EEE Congress on Evolutionary Computation (CEC), pp. 1382-1389, 2017.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Ducling network architectures for deep reinforcement learning. volume 48 of Proceedings of Machine Learning Research, pp. wtt...rres//////aagf......
New York, New York, USA, 20-22 Jun 2016. PMLR. URL http://proceedinng mlr. prw.sppsssseeeeee
David Wu. A rewrite of hanabi-bot in scala. https:://ittuu.comm//
Fireflower 2018.

---

Under review as a conference paper at ICLR 2021
A DEFINITION OF GROUNDED BELIEF AND EXACT BELIEF
The grounded belief for each card in hand is defined as
1(c,, ((),CC)) ((C,)eess))) E/=1 1(c,, Cj) f(Cyle1s-1)
p(c Cyloni-1)
where CI...., CK=25 are all possible outcomes for card, (c;, C2) is an indicator function telling whether particular outcome Cj is plausible for card based on the information revealed through hints, and f returns number of remaining copies of a card by excluding played cards, discarded cards, partner's hand and my cards in previous slots.
On the other side of the spectrum, we can compute the exact belief over hand as in Lerer et al. (2020) by tracking all possible hands and performing counterfactual filtering as game progresses. We then compute the marginal distribution for each card in hand as:
En= 1 (n4
(R) Cy, c11-1) ((((()))
p(c, Cylea-1)
(8)
Σ 1 (1 = (1--11- g(h((t)
where q(h(k)) is the counterfactual distribution of my possible hands.
B DESCRIPTION OF HANABI
Hanabi is fully cooperative partially observable multi-player card game. All players in the game work towards common goal. The deck consists of 5 colors and 5 ranks from to 5. For each color, there are copies of Is, 2 copies of 2, 3, 4s and copy of 5, totaling 50 cards. At beginning of game, each player draw 5 cards. However, they cannot observe their own cards but instead can see all of their partners' cards. Players take turn to move and the goal for the team is to play cards of in the correct order to get points. For example, the beginning of the game
each color from where nothing has been played, the 1s of every color can be played. If red I is played, then red 2 become playable while the of all other colors remain playable. Playing a wrong card will cause the entire team to lose 1 life token and the game will terminate early and the team will get 0 point all life tokens are exhausted. At each turn, the active player can either play a card, discard a card, or select partner and reveal information about their cards. To reveal information, the active player can either choose a color or a rank and every card of that color/rank will be revealed to the chosen player. The game starts with 8 information tokens. Each reveal action costs 1 token and each discard action regains I token. Players will draw a new card after play/discard action until the deck is finished. After the entire deck is drawn, each player has one last turn before the game ends.
C ADDITIONAL DETAILS ON EXPERIMENTAL SETUP
As mentioned in the main text, we base our experiments on the existing implementations of Other- Play and SPARTA for training blueprint and running search respectively and therefore inherit many of their hyper-parameter, For completeness we include a detailed documentation of the experimen- tal setup here.
The blueprint policy training is set up in a distributed fashion. On the simulation side, 6400 Hanabi simulators run parallel and the observations produced by those simulators are batched together for efficient neural network computation on GPU. Due to the high computational efficiency of the Hanabi-Learninn Environment Laniinna-nnngg-eeoomeentttt (Bard et al., 2020) and an effective batching technique introduced Hu & Foerster (2020), a single machine with 40 CPU cores and 2 GPUs is sufficient to run entire simulation workload. The simulated trajectories are collected into a prioritized replay buffer Schaul cet al. (2015). The priority of each trajectory is computed as E = 0.9 x maxx, + 0.1 (Kapturowski jet al. 2019 where & is the per step absolute TD error. On the training front, we sample mini- batches from the replay buffer to update the policy. The simulation policy is synced with the policy being trained every 10 gradient steps. The exploration is handled by epsilon greedy method. At the beginning of each simulated game, each player samples epsilon independently from 6;
12

---

Under review as a conference paper at ICLR 2021
Hyper-paranee parametarses
Value
# replay buffer related burn.in.frames
5000
replay.buufee..sze
131072 (2
priority.exponent
0.9
priority.weight
0.6
laxtrajeecooy..engthh
80
optimization
optimizer
Adam Kingma & Bay 2014
6.25e-05
eps
1.5e-05 05
grad_clip
5
batchsize
64
learning
n_step
3
discount.factor
0.999
target.networr..yyo.ntttevll
2500
Table 3: Hyper-Parameters for Reinfoncement Learning
x+ where a 0.1. 3 and N 80. The rest of the hyper- syper-parameters can be found in T
The belief model is trained under a similar setting as blueprint policy with major modifications. Firstly we load pretrained policy for running simulations and keep it fixed. Secondly the trajecto- ries are drawn uniformly from the replay buffer with no priorities. Finally the model is trained with the auto-regressive maximum likelihood loss defined in Eq, 6 with supervised learning. The belief model trained with Adam optimizer with learning rate 2.5 x 10-4 and eps 1.5 x 10-5,
The search experiments are benchmarked under the resource constraint of 10 CPU cores and GPU. At each step, we perform around 10K searches evenly distributed across legal actions. Searches run parallel over multiple CPU cores while neural network computations are batched across searches for maximum efficiency. The search will only change the move if the expected value the action chosen by search is 5 0.05 higher than that chosen by the BP. A UCB-like pruning method is used to reduce the number of samples required.
13

---

Under review as a conference paper at ICLR 2021
D FULL LEARNED BELIEF SEARCH RESULT
Test Method
RL-1H
RI-SH
RI-10H
RI-200H
RI.-40H
& Run Time
Blueprint
15.38 + 0.05
22.99 + 0.03
23.70 = 0.01
24.08 0.01
24.29 0.01
<s
0.02%
22.38%
40.12%
53.90%
63.30%
SPARTA
19.53 + 0.03
24.16 +: 0.02
24.39
0.01
24.52
0.01 69.9%
24.58 0.01
215s
0.03%
48.90%
61.14%
73.16%
LBS-inf
18.88 + 0.03
23.95 + 0.02
24.29 + 0.01
24.42
0.01 65.14%
24.52 0.01
121s
0.04%
42.16%
57.10%
71.12%
LBS-32
19.05 + 0.03
24.01 + 0.02
24.31 + 0.01
24.45
0.01 67.56%
24.53 0.01
84s
0.02%
42.60%
58.82%
71.78%
LBS-16
19.27 + 0.03
24.04 + 0.02
24.29 + 0.02
24.48 + 0.01
24.34 0.01
47s
0.02%
45.40%
57.98%
68.18%
72.14%
LBS-8
19.14 + 0.03
24.03 + 0.02
24.28 + 0.02
24.43 + 0.01 66.50%
24.49 + 0.01
25s
0.08%
44.64%
57.32%
68.78%
LBS-4
18.75 + 0.03
23.95 + 0.02
24.26 + 0.02
24.41 + 0.01
24.45 + 0.01
14s
0.06%
41.56%
55.38%
64.50%
66.40%
LBS-2
18.26 + 0.04
23.81 + 0.02
24.12 + 0.01
24.35 + 0.01
24.38 + 0.01
9s
0.02%
36.80%
50.60%
61.16%
63.88%
LBS-1
17.99 + 0.04
23.69 + 0.02
24.06 = 0.02
24.26 + 0.02
24.37 + 0.01
6s
0.00%
32.90%
48.66%
58.36%
62.72%
Table 4: Learned Belief Search Result. RL-kH means blueprint policy after k hours of training with RL. The numbers beneath method name leftmost column is average run time time. Each cell contains the mean and standard error of mean over 2000 games in the first row and percentage of perfect games (25 points) in the second row.
14


Reviews:
[{"review_id": "pUGIwN7zlN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n1. Summary:\n\nThis paper address efficient searching technique in partially observed MDP. The proposed a learned belief search (LBS) and use auto-regression model to learn the belief distribution of unobserved information. With the learned belief model, they can estimate the expected return via VDN technique. They evaluate the method on Hanabi and obtain 60\\% benefit of the exact search with $35\\times$ reduction in computation cost.\nHowever, it seems that there are many typos or technique issues, i think this paper needs proofreading before it can be accepted.\n\n2. Some Concerns/weakness:\n\n(1) When using argmax of $Q(a^i|\\tau^i)$ in n-step rollout, how to handle the overestimation? especially, there is a large variance in rollout, do you use any variance reduction technique?\n\n(2) All the experiments are evaluated on Hanabi. Does this method can solve different imperfect information games? I am not sure whether the improvement are specially designed for this particular game. I want to see at least one experiment evaluated on another different game, such as Leduc.\n\n(3) This paper is not well written. There are many typos in the equation or some other paragraphs, which i will list in the following.\n\n3. Questions:\n\n(1) what's BP in \"when the BP was trained via RL.\", page 1. BP is not defined beffor it's used.\n\n(2) what's blueprint policies in section 2.1?\n\n(3) the belief is not well defined in section 3. “We defined beliefs $B^i(\\tau_t)=P((s_t, \\{\\tau^j_t\\})|\\tau^i_t)$, which is the probability distribution ...”.  What's $\\{\\tau^j_t\\}$?\n\n(4) In Eq.2, it's a little bit confusing. in the expectation of $R^t(\\tau')$, $t$ refers to the horizon index of $\\tau'$?\n\n(5) could you explain equation 3 and 4 , they are very important in this paper. \n\n\n4. some issues/typos:\n\n[1] page 2, \"Simplified Action Decoder (SAD) (?)\"\n\n[2] We denote the environment trajectory as $\\tau_{t}=\\{s_0, a_0, ..., s_t, a_t\\}$\n\n[3] page 8, \"At the heart of LBS is an autoregressive model\", remove \"at\"\n\n[4] page 8, \"This could e.g. be addressed by retraining\", remove \"e.g.\"\n\n[5] page 1, \" the policies of any other agents is available at test time\", is -> are.\n\n[6] MC rollouts refers to Monte Carlo rollouts?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "j3feMKfzzl", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new approach to search in POMDP environments. The main idea is to extend a previous SPARTA search technique with a belief learning ability, called Learned Belief Search (LBS). While the existing work maintains explicit belief representation, LBS is an approximate auto-regressive counterfactual belief learning method that is based on supervised learning. Belief learning is showed to both have a good generalization and reduce searching time significantly. Experiments are mainly done on the benchmark problem of two-player Hanabi self-play. \n\nThe research direction is interesting and worth pursuing given recent work on this topic. Learning belief representation makes sense in this problem setting. The search would benefit a lot if computation time can be reduced through a cheap belief computation. While I found belief learning is commmon in single-agent POMDP tasks, the motivation of why LBS can be challenging and useful for DEC-POMDP or the multi-agent game domains is not convincing.\n\nThe experiment can also be improved with regards to the elaboration of experiment settings, the problem description, and discussions. \nThe result in Table 1 is not discussed in the main text. It's hard to understand the numbers reported in Table 1 and 3. May the authors elaborate in the response? It would also be helpful if a brief description of the Hanabi game can be included in Appendix too.  Comparisons of different design/hyperparameter choices can also help to judge the benefit of using learning for belief representation.\n\nMinor comment: \n- missing reference in page 3: \"Simplified Action Decoder (SAD) (?)\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "ixOPrcvZYVg", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThis paper is an extension of previous work SPARTA, with two improvements: one is to use a learned belief model to sample in a large state space; the other is to improve the efficiency by replacing full rollouts with partial rollouts that bootstrap from a value function after a specific number of steps. Experiments on the target game, Hanabi shows its superior performance than previous belief search methods in terms of efficiency.\n\n**Strengths**\nThis paper is more scalable by learning an auto-regressive belief model via supervised learning.\n\n**Weaknesses**\nLBS only supports one agent in a two-player game.\n\n**Detailed comments**\nI do not have sufficient expertise to comment on LBS (sections 3 and 4).\n\n**Some questions**\nOne question is that the authors mention learning a centralized reward function using VDN, while other agent’s q-value functions are unavailable. Also, I don’t understand how to use the total reward expectation to avoid having to unroll episodes until the end of the game.\n\n**Small comments**\nSome notations are not explained well. For example, on page 1, what does BP mean? BP is not given the full name. It is hard to understand without domain knowledge.\nOn page 3, there is a typo about the reference of SAD, with a symbol ‘?’\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hv18XLj64NL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis work provides a novel extension to the state-of-art approach (SPARTA) to solving Dec-POMDPs, a co-operative variant of partially observable stochastic games. Its main idea relies on the segmentation of action-observation histories (AOH) into more manageable public-private factors and training belief models to predict the belief on a trajecotory. Specifically, this work examines a single Dec-POMDP setting - the co-operative card-game Hanabi with two players.\n\n##########################################################################\n\nPros: \nWell pitched experiment, especially the use of snap-shotting to show improvement over time. Further, the inclusion of fixed budget analysis strongly emphasizes the utility of the method. \n\nUsing a natural fit of deep learning for modeling belief histories and trading-off exactness for speed, the work demonstrates a clear computational advantage over existing state-of-art approach.\n\n##########################################################################\n\nCons: \nMore detail is required to explain why multi-agent search is not theoretically sound.  If the trained model is only accurate for single agent search, is it not possible to train a model that is compatible with multi-agent search under different settings for max range?\nSPARTA shows that multi-agent search provides substantial improvements to the final scores at a large computational expense. Your work seems like it should be able to balance a trade-off for both of these functions.\n\nFor simplicity, the authors focus on 2-player Hanabi and claim it to be straightforward to extend to any number of players. I think this was a mistake, SPARTA itself was computationally limited to single-agent search for these 3-player and up variants. Applying your approach in these experiments would make a stronger case for elevation of the state-of-the-art than the 6-card variant.\n\nThe experimental setup requires significantly more details on the hardware used for training, testing and validating.\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nIn addition to the questions raised in the cons above, I have the following questions:\n1. Have you examined how this would look for more general partially observable settings? In particular, work on POSGs with public observations [Horák, K.; and Bosanský, B. 2019. Solving Partially Observable Stochastic Games with Public Observations. In AAAI Conf. on Artificial Intelligence, 2029–2036. AAAI Press.]. \n2. Are there any other DEC-POMDP settings that you considered? It may be insightful to compare the effects of different feature spaces. \n\n#########################################################################\nAdditional Comments/Suggestions\n\nThe x-axes in Figures 4a & 4b while understandable could be formatted in a formatted that does not require an extremely detailed reading of the Results section, for example in Fig 4a you could specify that the training budget was 24 hours and then use percentage of the training time spent on RL (from 5% up to 95%, which would be equivalent to 1|23 and 23|1).\n\nTable 1 is very busy, it may be worthwhile either taking fewer snapshots (or fewer rows) or removing the standard error of mean just to make it more readable. Especially since you include the full listing at Table 3.\n\nSome typos and errors:\nMissing reference for SAD in Section 2.2 \n\n##########################################################################\n\nReasons for score: \nOverall the approach of using a learned belief model to speed up costly belief searching is interesting. My main concern is on the soundness claim that limits the experimental scope to single-agent search. However, even with a comparison on just single-agent search this work is a fine fit for ICLR.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ggR807dxwRf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n \nThe paper proposed a computationally efficient search procedure for partially observable environments. The key idea behind the proposed method, LBS,  is to obtain Monte Carlo estimates of the expected return for every possible action in a given action-observation history of an agent. The proposed method reduced the complexity of sampling from belief space over the SOTA approach SPARTA by introducing an approximate auto-regressive counterfactual belief model over the opponent's private hands.  An empirical study on cooperative multi-agent game Hanabi shows that LBS could achieve considerable score while reducing compute requirements by 35x compare to previous SPARTA.\n##########################################################################\nReasons for score: \n \nOverall, I'd vote for rejection of the paper. My primary concern is that the LBS is highly dependent on the well-trained Blue Policy. It's not clear to me how the importance of BP contributes to the final performance. To be specific, would LBS fail when based on a broken BP policy(see cons below). Hopefully, the authors can address my concern in the rebuttal period.  \n##########################################################################\nPros: \n 1.The idea that using a learned belief model to replace exact sampling is interesting in general.\n2.Overall, the paper is well written. The motivation of the proposed method is clear and sound. As an improvement over SPARTA, LBS has addressed one of the main issues of scalability. LBS offered a choice to apply SPARTA to more complex environments.\n \n \n##########################################################################\nCons: \n \n1. The key concern about the paper is that the choice of BP, which decides the performance of the belief model. It is natural that LBS will work If the belief model is perfect. But not vice versa. There is no guarantee that LBS would work if the belief model is broken or even flawed.\na).How does LBS perform when using an unconverging learned belief model? Or value model?\nb).It is not clear to me that the choice of the number of factorized private features.\n2.Although LBS provides several ablation studies of the choice of BP and Run time, but I'm not convinced of the efficacy of LBS, especially in more complex environments, e.g., Contract Bridge.\n  \n##########################################################################\nQuestions during the rebuttal period: \n \nPlease address and clarify the cons above \n \n#########################################################################\nOthers\nReference alignment: Figure 1 (LHS), Figure 1(A), Fig 2.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has some interesting ideas and is an incremental improvement over previous work. However, it needs further revisions and polishing. The relation to prior work is a bit unclear. Since you mention POMDPs, what would be an equivalent version of your method in POMDPS? Why not compare your algorithm with a state-of-the-art method for small discrete problems? It is also a bit unclear why training a model to predict beliefs would be faster than just calculating them (after all the data must come from somewhere)..
Decision: Reject