Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary**
This 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.

**Strengths**
This paper is more scalable by learning an auto-regressive belief model via supervised learning.

**Weaknesses**
LBS only supports one agent in a two-player game.

**Detailed comments**
I do not have sufficient expertise to comment on LBS (sections 3 and 4).

**Some questions**
One 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.

**Small comments**
Some 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.
On page 3, there is a typo about the reference of SAD, with a symbol ‘?’


review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
1. Summary:

This 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.
However, it seems that there are many typos or technique issues, i think this paper needs proofreading before it can be accepted.

2. Some Concerns/weakness:

(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?

(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.

(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.

3. Questions:

(1) what's BP in "when the BP was trained via RL.", page 1. BP is not defined beffor it's used.

(2) what's blueprint policies in section 2.1?

(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\}$?

(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'$?

(5) could you explain equation 3 and 4 , they are very important in this paper. 


4. some issues/typos:

[1] page 2, "Simplified Action Decoder (SAD) (?)"

[2] We denote the environment trajectory as $\tau_{t}=\{s_0, a_0, ..., s_t, a_t\}$

[3] page 8, "At the heart of LBS is an autoregressive model", remove "at"

[4] page 8, "This could e.g. be addressed by retraining", remove "e.g."

[5] page 1, " the policies of any other agents is available at test time", is -> are.

[6] MC rollouts refers to Monte Carlo rollouts?

review_title:  Borderline paper. Need proofreading.

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

The 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.

The experiment can also be improved with regards to the elaboration of experiment settings, the problem description, and discussions. 
The 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.

Minor comment: 
- missing reference in page 3: "Simplified Action Decoder (SAD) (?)"
review_title: Good paper to read, not convincing presentation.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
 
The 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.
##########################################################################
Reasons for score: 
 
Overall, 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.  
##########################################################################
Pros: 
 1.The idea that using a learned belief model to replace exact sampling is interesting in general.
2.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.
 
 
##########################################################################
Cons: 
 
1. 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.
a).How does LBS perform when using an unconverging learned belief model? Or value model?
b).It is not clear to me that the choice of the number of factorized private features.
2.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.
  
##########################################################################
Questions during the rebuttal period: 
 
Please address and clarify the cons above 
 
#########################################################################
Others
Reference alignment: Figure 1 (LHS), Figure 1(A), Fig 2.

review_title: recommendation to Reject

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

This 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.

##########################################################################

Pros: 
Well 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. 

Using 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.

##########################################################################

Cons: 
More 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?
SPARTA 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.

For 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.

The experimental setup requires significantly more details on the hardware used for training, testing and validating.

##########################################################################

Questions during rebuttal period: 

In addition to the questions raised in the cons above, I have the following questions:
1. 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.]. 
2. Are there any other DEC-POMDP settings that you considered? It may be insightful to compare the effects of different feature spaces. 

#########################################################################
Additional Comments/Suggestions

The 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).

Table 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.

Some typos and errors:
Missing reference for SAD in Section 2.2 

##########################################################################

Reasons for score: 
Overall 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.


review_title: Interesting work on POMDPs but there is room for improvement

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