A Fine-Tuning Approach to Belief State Modeling
Authors: Samuel Sokota
Hengyuan Hu
David J Wu
J Zico Kolter
Jakob Nicolaus Foerster
Noam Brown
Venue: ICLR 2022 Poster (2022)
Keywords: imperfect-information
partial observability
search
decision-time planning

Abstract: We investigate the challenge of modeling the belief state of a partially observable Markov system, given sample-access to its dynamics model. This problem setting is often approached using parametric sequential generative modeling methods. However, these methods do not leverage any additional computation at inference time to increase their accuracy. Moreover, applying these methods to belief state modeling in certain multi-agent settings would require passing policies into the belief model---at the time of writing, there have been no successful demonstrations of this. Toward addressing these shortcomings, we propose an inference-time improvement framework for parametric sequential generative modeling methods called belief fine-tuning (BFT). BFT leverages approximate dynamic programming in the form of fine-tuning to determine the model parameters at each time step. It can improve the accuracy of the belief model at test time because it specializes the model to the space of local observations. Furthermore, because this specialization occurs after the action or policy has already been decided, BFT does not require the belief model to process it as input. As a result of the latter point, BFT enables, for the first time, approximate public belief state search in imperfect-information games where the number of possible information states is too large to track tabularly. We exhibit these findings on large-scale variants of the benchmark game Hanabi.

Published as a conference paper at ICLR 2022
A FINE-TUNING APPROACH TO BELIEF STATE MODELING
Samuel Sokota"
Hengyuan Hu
David J. Wu
Carnegie Mellon University
Meta Al
Meta Al dwu @ fb.
@sokota@andrewt ctttarewwcwuuee. wmw.cmu.eee. edu
hengyuan fom
Zico Kolter
Jakob Foerster Oxford University
Noam Brown
Carnegie Mellon University zkolterêcs cmu. edu
Meta AI noamb wwwbroow@@@... com
jakob www.seeeeeeeegee.....ooooo ax.ac.uuuuuuuc
ABSTRACT
We investigate the challenge of modeling the belief state of a partially observable Markov system, given sample-access its dynamics model. This problem setting is often approached using parametric sequential generative modeling methods. However, these methods do not leverage any additional computation at inference time to increase their accuracy. Moreover, applying these methods to belief state modeling in certain multi-agent settings would require passing policies into the be- lief model-at at the time of writing, there have been successful demonstrations this. Toward addressing these shortcomings, we propose an inference- improvement framework for parametric sequential generative modeling methods called belief fine-tuning (BFT). BFT leverages approximate dynamic program- ming in the form of fine-tuming step. It can improve the accuracy of the belief model at test time because it spe- cializes the model to the space of local observations. Furthermore, because this specialization occurs after the action or policy has already been decided, BFT does not require the belief model to process it as input. As result of the latter point, BFT enables, for the first time, approximate public belief state search in imperfect-informatee
determine the model parameters at each time
games where the number of possible information states is too large to track tabularly. We exhibit these findings on acale variants of the benchmark game Hanabi.
INTRODUCTION
A Markov system is sequential process in which future events are independent of past events, conditioned on the current Markov state (Gagniue 2017). the Markov state cannot be directly observed, the system is said to have partial observability. This work considers three kinds of Markov systems with partial observability: hidden Markov models (HMMs), partially observable Markov decision processes (POMDPs), and factored observation stochastic games (FOSGs). An HMM is Markov system which, at each time step, a distribution determined by the current (unobservable) Markov state generates observable and new (unobservable) Markov state (Rabiner & Juang, 1986). A POMDP is generalization of an HMM in which an agent influences the trajectory of the system by taking actions (Kaelbling multiple agents receive observations from the system and take actions that influence the trajectory of the system (Kovařík et al. (022)).
1998). A FOSG is generalization of a POMDP in which
An important inference problem associated with Markov systems with partial observability is belief state modeling. The objective of belief state modeling is compute the posterior (called the belief state) over the current Markov state. This problem is important because belief states are sufficient information forecast future events and to anticipate how the system will respond to external actors. In sufficiently small systems, the problem can be solved exactly using the classical forward algorithm
Work done while Meta AI.

---

Published as a conference paper at ICLR 2022
(Rabiner 1989), which is based on tabular dynamic programming. However, in larger systems, the forward algorithm is inapplicable, as it scales quadratically in the number of Markov states.
In such cases, an appealing alternative is to learn an approximate model of the belief state using parametric sequential generative model. Parametric models are appealing because they can be scaled to very large settings and can be trained from samples. However, suggest that naively performing inference on parametric models has two significant drawbacks. First, doing so does not leverage any additional computation at inference time to improve the accuracy of the model. While the idea of performing additional local improvement is widely leveraged in reinforcement learning under the terms decision-time planning and search (Silver et al., 2018 Schrittwieser al.) [0200] Brown et al., (2020a), it has gone largely overlooked in the context of approximating belief states in large systems. Second, in the context of public belief state modeling in multi-agent systems, parametric models require a representation of the policy as input at each time step. At the time of writing, there has been no successful demonstration of this. As a result, performing belief modeling in large multi-agent systems remains out of reach, rendering celebrated algorithms for imperfect information games inapplicable (Brown & Sandholm, 2017 Moravčík et al. 2017 Brown & Sandholm 2019).
To address these shortcomings, we propose an inference-time improvement framework for paramet- ric models called belief fine-tuning (BFT). At each time step, BFT uses the belief model for the current step to generate an empirical distribution of current Markov states. Next, it uses this em- pirical distribution, along with the dynamics model (and player policies), to generate an empirical distribution of next Markov states and observations. Finally, BFT fine-tunes the belief model for the next time step using the latter empirical distribution. BFT can improve the accuracy of belief model, even if it has been trained to convergence, by specializing its capacity the space of local observations (Silver et al., 2008). Furthermore, BFT can model belief states even without taking actions or policies as input because, during fine-tuning, the action or policy has already been fixed.
To demonstrate the efficacy of BFT, we proceed with our experimental agenda in two parts, focusing on the cooperative imperfect-information game Hanabi (Bard et al. 2020p. First, we verify that, as advertised above, BFT can improve the accuracy of a belief model in various settings. Second, we investigate the performance of decision-time planning running on top of BFT. We find that in cases in which tracking exact belief states is tractable, BFT can yield performance competitive with that of an exact belief. Furthermore, in cases in which tracking the exact belief state is intractable, we find that performing search on top of BFT can yield substantial improvements over not performing search. This is the first instance of successful approximate public belief state-based search in a setting in which computing an exact belief state is intractable.
2 BACKGROUND AND NOTATION
We describe three formalisms for Markov models with partial observability, and then present a unifying notation for them.
2.1 HIDDEN MARKOV MODELS
An HMM a tuple (T, O) where T: W + AW the transition function and O: W + AO is the observation function, where 40 is the simplex on C. At each time, the current Markov state w' generates a new Markov state W ~ T(w"). The new Markov state generates a new observation o OWW++1). The belief state is the posterior P(W? |o! .o.....,o') over the Markov state, given the history of observations.
2.2 PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES
A POMDP is tuple OT,ORR, R) where T: W A + AW is the transition function, O: W + AO is the observation function, and R: W x + R is the reward function. At each time step, an agent selects action a² E A as function of the history of its actions and observations (ot ,a' .......o'). This action is used in conjunction with the current Markov state w/ to generate a new Markov state W T(w", a²) and reward rd R(w a²). The observation for the next time step O++ OW is determined as a function of the new Markov state. The belief state is the posterior P(W* o at,.. a......,0' .²) over the Markov state, given the history of actions and observations.
2

---

Published as a conference paper at ICLR 2022
General
HMM
POMDP
FOSG
Markov Variable
X
W
W
(W.S Sp)
Emission Variable
Y
0
Ppd (5iT..., xT
Control Variable
Z
A
Table 1: The relationship between notations for belief state modeling for different settings.
2.3 FACTORED OBSERVATION STOCHASTIC GAMES
FOSG is a tuple (T, Outh Oprio(1)..... O printn): Ri..... R,), where T: W x + AW is the transition function, Opub: W - A0 is the public observation function, O Opriv(t) W AOpriv() is player i's private observation function, and R,: W x A. + IR is player i's reward function. At each time step, each agent selects an action of ~ (s()) as a function of the his- tory of its observations and actions st (ouuss o priu(s)) ai p....... ... putr of (prie()). The joint action a' = -ai....., ai) is used in conjunction with the current Markov state w" to generate a new Markov state W T(w', a) and a reward r R(w", a) for each player. The public ob- servation 0++1 Opp (W/+1) and each player's private observation O++1 pub
prin(i) Oprio(() (W++1) are determined as functions of the concurrent Markov state. In FOSGs the relevant belief state is opub: Vi, ..... Th..... the posterior P(W*, Si..... history, conditioned on the sequence of public observations and the each player's 's sequence policies. This belief state is called the public belief state.
......... pun) over the current Markov state and
zo
Z
X
X
X2
ya
y1 y2
A graphical model depicting the belief state modeling problem. The Markov vari- able X and an externally specified control variable z' stochastically determine the next Markov variable x Each Markov variable X stochastically determines the contemporaneous emis- sion variable y++ The belief state modeling problem is approximate the posterior P(X Y1, 2t, 2 Y`) over the current Markov variable given all past and present emission variables and all past control variables.
Figure 1:
2.4 GENERAL NOTATION FOR BELIEF STATE MODELING
Regardless of whether the belief state modeling problem is in the context of HMMs, POMDPs, or FOSGs, belief state modeling can be expressed modeling distribution P(X y 21 .t......, Y!). where each yJ )(X*), each 2 is specified by an external process, and the process moves forward in time by sampling Xi+1 X(X', Z²), as depicted in Figure 1 We call X the Markov variable, Y the emission variable, and Z the control variable. In HMMs, the Markov variable is the Markov state X W, the emission variable is the observation Y O and the control variable null. In POMDPs, the Markov variable is the Markov state X W. the emission variable is the observation = and the control variable is the action = A. In FOSGs, the Markov variable is tuple of the Markov state and each player's action-observation history X (W, S S,), the emission variable is the public observation Y = Opub. and the control variable is the joint decision rule Z (Tf...... =()) (i.c., the joint policy for that time step). Table I summarizes the relationships between these notations. To minimize clutter, we will use this more concise notation going forward. In all cases, assume sampling access to y: X AV A and X: X Z AX

---

Published as a conference paper at ICLR 2022
2.5 SEQUENTIAL GENERATIVE MODELING
The sequential generative modeling problem is to model the distribution of one sequence of vari- ables, conditioned on another sequence of variables. Because it is a superset of the belief state mod- eling problem. its solution methods are immediately applicable to belief state modeling. Among the most popular of these methods are parametric modeling approaches. Parametric modeling ap- proaches use set of sequences [(Xg &: Yg Z k...... ..... X Y he collected from the dynamics model (X, y) minimize the difference between the output of parameterized model fs ....... YY) and the distribution over X y Z . ........ Y observed in the dataset, for each and k, over pa- rameters 0. They generally require two design choices. First, whether to maintain a running sum- mary of the conditioning sequence using recurrent network (Hochreiter & Schmidhuber 1997) or whether to model the desired distribution as a direct function of the running sequence at each time step (Vaswani et al. 2017). Second, what kind of model use capture the desired distribu- tion. Common choices include autoregressive models, adversarial models (Goodfellow et al. 2014),
variational models (Kingma Welling, 2014), score-based models (Hyvärinen] (2005). among others. Because the experiments in this work focus on the Hanabi benchmark (Bard et al. 2020),
which involves long sequences and discrete output variables, we choose use recurrent architec- ture with an autoregressive output (Sutskever et al., 2014). However, BFT is not specific to these design choices and can also be combined with other approaches for sequential generative modeling in the context of belief state modeling.
METHODOLOGY
BFT comes from the approximate dynamic programming perspective on belief state modeling, We describe this perspective below, discuss its advantages, and then introduce BFT.
3.1 BELIEF STATE MODELING AS APPROXIMATE DYNAMIC PROGRAMMING
A second way to approach belief state daaeeling-dsttinne from the standard sequential generative modeling setups discussed in the background as an approximate dynamic programming prob- lem. Observe, for some fixed control variable 2²11, previous belief state b--1, and current emission variable y", we have
by, = P(X"
x P(y' x ")p(X" 1=-118611 = PPy' xx)xx( Iob P(x 1 1--1x(11)
(2)
(3)
Line (1) follows by definition, line (2) follows by Bayes' rule, and line (3) follows by the Markov property and the law of total probability. As result of this proportionality, the procedure
1. Sample xt-1 ~ b-1
Sample X XXx-11 2(-1)
3. Sample y ~ ((X))
yields a sample X by... Thus, given sample-access to Y. and the distribution of X it is entirely possible to train belief model inductively via approximate dynamic programming, whereby the belief states at time step one bootstrap from the initial belief state, the belief states time step two bootstrap from the belief states at time step one, and forth, as shown in Figure 2
While this procedure is known, it is unusual for it to be used to train belief state models because the training data it produces is biased-unless the approximation to 6f-1 is exactly correct, the training data for By. will only come from an approximately correct distribution. In contrast, sampling full trajectories guarantees that the training data will come from exactly the correct distribution.
3.2 ADVANTAGES OF APPROXIMATE DYNAMIC PROGRAMMING
Despite that approximate dynamic programming produces biased samples. argue here that the approximate dynamic programming perspective offers advantages that have gone largely overlooked in existing literature. These advantages derive from the fact that approximate dynamic programming
4

---

Published as a conference paper at ICLR 2022
z
Bt-1
Xt-
x B
Y
Table 2: A graphical model depiction of the dynamic programming perspective on belief state modeling. Gray arrows denote causal relationships; white arrows denote distributional modeling.
allows us to generate local data. Given previous belief state 1 generating samples for the current time step is as simple as following the procedure above. In contrast, generating unbiased versions of the same samples would require sampling collection of initial Markov states .f:.... X2 ~ X0, propagating them forward using the same sequence of control variables 20, ..... and rejecting the rollouts that yielded emission sequences y ...., y inconsistent with the previously observed sequence of emission variables. For large it becomes prohibitively unlikely to sample trajectory with exactly the same sequence of observations.
The ability generate local data in the context of belief state modeling may be helpful for two reasons. First, it may increase the accuracy of the belief model by allowing it to perform an ad- ditional improvement step immediately prior inference time. Even if the model was trained to convergence offline, it may be the case that the model does not possess sufficient capacity to capture the exact belief for every possible sequence of emission and control variables. Therefore, an addi- tional improvement step can provide utility by reallocating the belief model's capacity to the space of immediate possible futures, thereby increasing its ability to approximate the belief state for those futures. These ideas have long been understood in reinforcement learning literature (Silver et al.) 2008 but are overlooked in the context of belief modeling.
A second advantage of inference-time improvement is that the control variable can be omitted from the belief model. This is a result of the fact that the Markov variable only depends on the control variable from the previous time step (not the current time step). Therefore, long as inference- time improvement takes place after the control variable for the previous time step has been decided, the belief state depends only the contemporaneous emission variable. In the context of HMMs or POMDPs, where the control variables are nulls and actions, respectively, the ability to omit the control variable carries little value. However, in FOSGs, where the control variables themselves joint policies, the ability to omit the control variable is an important attribute. Indeed, at the time of writing, there have been convincing demonstrations of belief state modcling at scale in FOSGs due to the fact that it is not clear how to train sequential generative model as function of policy networks.
3.3 BELIEF FINE-TUNIES
Toward leveraging the advantages of inference-tine time improvement discussed above, we propose framework for belief fine-tuning (BFT). BFT takes pretrained belief model fo as input and, at each time step during online inference, performs the following procedure:
1. Sample X--1 ..... Xt-1 fo--1 20 ..... ".......--! 111)
2. Sample X! X 211 for each i 1, 1,...,k. k.
3. Sample Y ((X)) for each =1 ........ k.
4. Set 6t +- fine- fine-t (YY X²) 1....,k) k})
For the final step, exactly how the fine-tuning is performed depends on the structure of the architec- ture If takes the control variable input, then 20-1 should also be passed into the model during
5

---

Published as a conference paper at ICLR 2022
; 20 fine tuning; if f is recurrent, then the hidden state hy, the model; if f takes the full sequence as input, then the full sequence should also be passed in during fine-tuning, In principle, BFT could produce accurate distributions from an untrained model that only took a single emission variable Y as input. However, we do not recommend this approach, as it amounts training new generative model at each time step from scratch.
..... ..... .......'"") should also be passed into
4 EXPERIMENTS
We divide our experimental investigation into two parts. In the first part, we explore the extent to which BFT can improve the belief quality of parametric model in HMMs, POMDPs, and FOSGs. In the second part, we explore the idea of performing search on top of beliefs from BFT.
We use the cooperative card game Hanabi (Bard et al. 2020) for these experiments. Hanabi re- sembles something in the realm of cooperative Solitaire the players are tasked with collectively playing cards of each suit rank order into piles on the table. However, characterizing feature of Hanabi is that no player can observe its own cards. Instead, each must infer information about its own cards from other players' actions. A more elaborate description of Hanabi is in the appendix.
In Hanabi, if the participants in the game agree to follow fixed joint policy, the system can be considered an HMM from the perspective of a third party who does not observe the players' cards. If all but one of the players in the game agree to follow fixed (joint) policy, the system can be considered a POMDP from the perspective of the player with a varying policy. If none of the players' policies fixed, then the system can be modeled as FOSG. Therefore, Hanabi allows us to investigate all three systems within the same infrastructure.
The codebase for offferrrc/oofeeee///eeeee www.ressarrccoof-eeeeeeeeee
experiments can be found at atttss//giihunt com/ Additional ablations on number of fine-tuning steps, amount of offline training, network capacity, and part of network tuned are included in the appendix.
4.1 BELIEF FINE- TUNING FOR IMPROVING BELIEF QUALITY
For first set of experiments, we verify that BFT can improve the accuracy of pre-trained parametric belief model in HMMs, POMDPs, and FOSGs. For our experimental setup, we trained policies using independent R2D2 (Kapturowski et al. 2019) that collectively score around 24 out of 25 points, using the same hyperparameters as those found in (Hu & Foerster 2020). We then trained a Seq2Seq model (Sutskever et al.) (0144) close to convergence for an HMM belief state, the POMDP belief state, and the public belief state (i.e., the FOSG belief state). For the Seq2Seq model, we used the same hyperparameters as those found (Hu al. 2021 For the FOSG case, we did not feed the players' policy networks into the Seq2Seq model.
At evaluation time, we used RLSearch (Fickinger et al., 202T) on top of the R2D2 policies to gen- erate the actions for the non-fixed players in each setting. In short, RLSearch performs additional fine-tuning of the policy or value network at decision time, using samples from the belief state and the same learning algorithm that used during training time. We used the same hyperparameters as those found in the original paper, with the exception that we used the search policy at every time step, rather than sometimes using the blueprint policy (i.e., the policy computed using R2D2). This choice was made so as to highlight the amount of improvement achievable from BFT. For BFT, we fine-tuned the encoder of the belief network for 10,000 gradient steps at each decision-point using the same hyperparameters that were used for offline training.
VÔ Belief
Seq2Seq
Seq + BFT (Ours)
HMM
2.08 + 0.01
1.67 0.01
1.58 + 0.01
POMDP
1.73 0.01
1.39 + 0.01
FOSG
2.12 0.01
1.81 + 0.01
1.62 + 0.01
Table 3: Cross entropy per card with standard error for different settings, aggregated over 300 games.
Table 3 shows results for the Seq2Seq model, BFT on top of the Seq2Seq model, and a baseline called the VO belief, which is naively from independence assumptions and the rules of the game (in

---

Published as a conference paper at ICLR 2022
ignorance of the actual player policies). The VO belief serves as sanity check that the belief model working and provides sense of scale about cross entropy values for each setting. The scale for the POMDP setting differs because it conditions belief is over only one player's ' hand; in contrast, the belief in the HMM and FOSG settings are over both players' hands and condition only public information.
the acting player's private information and the
For the HMM setting, we observe BFT yields an improvement over the belief model. This improve- ment comes despite the facts that 1) the belief model was trained using a stream of freshly generated data (so there is no overfitting problem), 2) the belief model was trained close to convergence, 3) there is no distribution shift test time. This result may be evidence of the benefit of reallocating the capacity of the neural network at inference time.
For the POMDP setting, we observe that BFT yields an even larger improvement over the Seq2Seq model. While facts 1) and 2) of the above paragraph still hold true here, fact 3) does not. In particular, in the POMDP setting. there is covariate distribution shift- the acting player uses a search policy at evaluation time, rather than the blueprint policy used at training time. In principle, if the model had a sufficiently large amount capacity and was trained to convergence, covariate distribution should not impact model performance. However, as matter of practice, is illustrated by the results in Table 3 covariate distribution shift can have a large effect on model performance.
Finally, in the FOSG setting, observe that BFT induces the largest improvement. In this setting, the belief model faces not only covariate distribution shift, as it did in the POMDP setting, but also concept distribution shift, variables (the player policies) and that the distribution of control variables changes at test time because the agents are using search.
result of the facts that the belief model is ignorant to the control
4.2 BELIEF FINE- TUNING FOR DECISION TIME PLANNING
For our second set of experiments, we investigate whether the improvement in belief quality yielded by BFT leads to downstream improvements search performance. For these experiments, we used the same hyperparameters as those found in (Fickinger et al. [222]) for the search algorithms and (Hu et al. (222)) for the Seq2Seq model. Again, we used 10,000 gradient steps on the encoder of the belief model with the same hyperparameters offline training.
5-card 8-hint Hanabi
SPARTA
RL Search
SPARTA
RL Search
RL Search
RL Search
Blueprint
Single Exact
Single
Multi
Multi
Multi Seq2Seq
Multi BFT (Ours)
Exact
Exact
Exact
24.23
24.57
24.59
24.61
24.62
24.35
24.58
+-0.44
+0.03
+0.02
+0.02
+0.03
+0.03
+0.02
5-card 2-hint Hanabi
SPARTA
RL Search
SPARTA
RL Search
SPARTA
RL Search
Blueprint
Single
Single
Multi
Multi
Multi
Multi
Exact
Exact
Exact
Exact
Seq2Seq
BFT (Ours)
22.99
23.60
23.61
23.67
23.76
23.35
23.69
+.0.04
+0.03
+.0.3
+00.33
+0004
+0.03
+00.33
Table 4: Expected returns with standard error, aggregated over 2000 games. RL Search Multi Exact is an upper bound on the performance we would hope for from BFT. RL Search Multi Seq2Seq is our baseline. BFT significantly outperforms the Seq2Seq model, and nearly matches the performance of exact beliefs.
We show performance results for (5-card, 8-hint) and (5-card, 2-hint) Hanabi Table We compare single and multi-agent SPARTA (Lerer et al.) 2020) with exact beliefs, and single and multi-agent RLSearch (Fickinger et al. 2021 with exact beliefs, to two versions of multi-agent RLSearch with approximate beliefs. In approximate-belle belief version, used the Seq2Seq model trained offline. In the other version, we performed BFT on top of the Seq2Seq model after the search policy had been computed.
7

---

Published as a conference paper at ICLR 2022
In both the 2-hint and 8-hint variants, exact-belief multi-agent search substantially improved upon the blueprint policy. Seq2Seq beliefs fell far short of this improvement, while Seq2Seq + BFT nearly matches the performance of exact beliefs. These results suggest that the improvement in cross entropy from BFT observed in the previous section has an important effect on downstream search.
We can further investigate the added value of BFT by looking at the self-assessed improve- ment of multi-agent RLSearch with each of the three belief types (Seq2Seq. Seq2Seq BFT, Exact), shown in Figure (4.2 We compute the increase in expected return by performing roll-
6.05
outs from the public belief state to the end of the game, using both the policy determined by RLSearch and the blueprint policy. Us- ing the exact belief (blue) corresponds to com- puting the true improvement, whereas any ror in the approximate beliefs will spill over into the improvement computation. We ob- serve that BFT (orange) mostly yields compara- ble self-assessed improvements an exact be- lief, with some overestimation toward the end of the game. In contrast, the Seq2Seq belief (green) significantly overestimates the amount of improvement over the blueprint throughout the course of the game. These results help ex- plain those found Table -te the Seq2Seq model is not able to properly assess policy values without BFT, leading it to believe that its search policy is making large improvements when, in fact, its im- provements may be small or non-existent.
Nethod
0.03
Exact
6.01
10
20
30 Tum farmerr
40
63
Figure 2: Without BFT, multi-agent RLSearch with Seq2Seq overestimates its performance.
7-card 4-nint Hanabi
RLSearch Single Seq2Seq
RL Search
RL Search
RL Search
Blueprint
Single
Multi
Multi
BFT (Ours)
Seq2Seq
BFT (Ours)
23.67
24.14
24.18
23.71
24.18
+0.02
=0.04
+0.03
+0.07
+0.03
Table 5: Expected returns with standard error, aggregated over 1000 games. Multi-agent search with BFT significantly outperforms the multi-agent search with Seq2Seq belief. Computing exact beliefs is intractable in this setting.
For our final experiment, we examine 7-card Hanabi a setting in which there so much private information that it is difficult compute an exact belief. For this experiment, include single and multi-agent variants of RLSearch using approximate beliefs from Seq2Seq and BFT. Similarly to the results in Table we observe in Table 5 that multi-agent RI.Search without BFT outperformed the blueprint (though not with significance in this case) but was significantly outperformed by every other setup. In contrast, multi-agent RLSearch with BFT substantially outperforms the blueprint. For single-agent RLSearch, BFT also resulted in better performance than Seq2Seq. We computed a one-sided t-test (computed by pairing deck orderings) and found that this improvement occurred with p-value of 0.052.
5 RELATED WORK
There has been much recent focus among the machine learning community on large, relatively general purpose, machine models that are fine-tuned for more specific tasks, such BERT (Devlin) et al., 2019), GPT-3 (Brown et al., 2020b), or DALL-E (Ramesh et al. [002]). Our work relates to this literature in the way it handles belief states for FOSGs by training belief model ignorant of the control variable offline, then later specializing the belief model to a specific control variable during online inference, though much smaller scale.
8

---

Published as a conference paper at ICLR 2022
More generally, the idea of improving model from small amount of data inference time also places our work close to the meta-learning literature (Hospedales et al., 2021). There are various ways to perform meta- meta-learning, such recurrent neural networks (Ravi & Larochelle| (011ch hyper- networks (Qiao et al. 2018), or fine-tuning a network initialized using second order gradient descent (Finn al. 2017)-
BFT is also closely related to the idea of performing additional improvement at decision-time, which has a rich history in reinforcement learning inerature-including many of the most widely acclaimed game-playing Al systems (Tesauro et al. 1995, Silver et al. 2018 Moravčík et al., 2017 Brown & Sandholm 2017; 2019). However, the literature that specifically uses fine-tuning for decision- time planning is much smaller. The first works to do so with large non-linear networks (Anthony et al. 2019 Anthony 202T) showed that a policy gradient fine-tuning-based search can perform competitively with, or even outperform, MCTS in Hex. More recently, |Fickinger et al. (2021) investigated the idea of finetuning-baaae based search using independent Q-learning in Hanabi and policy gradients in Ms. Pacman (Bellemare al. 2012).
Our work also relates to literature that attempts to work with public belief states at scale in FOSGs. The Bayesian action decoder scales approximate public belief states to Hanabi using Hanabi-specific independence heuristics and an expectation propagation like procedure (Foerster et al. 2019). While method differs in
also examine the performance of approximate belief states on Hanabi, that it uses no independence heuristic, is focused on inference-time improvement, and is not tied specifically Hanabi. Another paper investigating public belief states in large settings is that of Sustr al. (2021). who propose scalable method for approximating the value of public belief state from samples. More precisely, they investigate a value function architecture that takes samples from public belief states as input, rather than closed form public belief state. Our contribution is complementary to theirs, as our method aims to produce high quality public belief state samples.
Finally, work also relates to particle filtering literature (Doucet & Johansen 2009). Particle filtering maintains works by maintaining a set of Markov states { (called particles) and corre- sponding weights {wi}: that collectively approximate the belief state. At each time step, similarly to BFT, the collection of particles is propagated forward in time using the dynamics model. The weights are updated based on the proportional posterior probability of each particle. One disadvan- tage of particle filtering compared to BFT is that all of the particles may become infeasible; in other words, every particle may have probability zero given the sequence of emission and control vari- ables. Moreover, whereas particle filtering can only resample particles from its finitely supported empirical distribution, BFT can produce arbitrary resamples.
6 CONCLUSION AND FUTURE WORK
In this work introduced BFT, a framework for improving belief state models during online in- ference. We sought to demonstrate two claims: i) BFT can improve the performance of a belief model ii) this gain in belief accuracy yields downstream gains in search performance. We provided evidence for both claims using large scale variants of the Hanabi benchmark.
We see three lines of work worth pursuing follow ups to this one. The first to investigate whether incorporating meta-learning into BFT can improve its performance. While the inference-time im- provement framework can be cast as meta-learning problem, we did not actually incorporate this into the BFT objective. The second is to investigate the design of belief models that can quickly model public belief states. While BFT allows us to effectively model public belief states, requires performing fine-tuning each time public belief state is required. This is fine for algorithms which only use public belief states to construct the root of their search trees (Brown et al. 2018 Lerer et al.) 2020), but may be too slow to use for algorithms that use public belief state-based value functions (Moravčík et al. 2017] Brown et al. [220aa; Sokota et al. 202Tb. The third line is to investigate elim- inating the need for sampling access the dynamics model. While MuZero (Schrittwieser al.) 2020) accomplished this for deterministic fully observable settings, determining the best way to do this for partially observable settings remains an open problem.

---

Published as a conference paper at ICLR 2022
REFERENCES
Thomas Anthony, Robert Nishibara, Philipp Moritz, Tim Salimans, and John Schulman. Policy gra- dient search: Online planning and expert iteration without search trees. CoRR, 00s//994.03346,, 2019. URL htRp:/tp:///axii www.ariwwv....rraeoemmmee abs/ / 904. 63646
Thomas William Anthony. Expert iteration. PhD thesis, UCL (University College London), 2021.
Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 130:103216, 2020.
Mare Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47, 07 2012. doi:
1/jair3/jai::311.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaaol 2017.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019. ISSN 0036-8075. doi: 10. 10.1126/sciene..nn24400 URL htttt://ssccenee sciencemag wtarg//ootent//ttt
Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth-limited solving for imperfect- information games. In NeurlPS, 2018.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep re- inforcement learning and search for imperfect-infooraatio games. In H. Larochelle, F. Balcan, and Lin (eds.). Advances in Neu- ral Information Processing Systems, volume 33, pp. 17057-17069. Curran Associates, Inc., 2020a. URL https: /ttpp:://proceedingsscoo neurips pcc/ppper/222//11ee// 1608d4448880 Paper pdd
M. Ranzato, R. Hadsell,
c61f571dbod
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020b. URL /ttppptttts:: hwwp://wwwee..........eeeeeeeeee neurips cc//ppper//222///i1e/
Paper. .dff
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACI, 2019.
Arnaud Doucet and Adam Johansen. A tutorial on particle filtering and smoothing: Fifteen years later. Handbook of Nonlinear Filtering, 12, 2009.
Arnaud Fickinger, Hengyuan Hu, Brandon Amos, Stuart Russell, and Noam Brown. Scalable on- line planning via reinforcement learning fine-tuning. In International Conference Learning Representations, 2021.
Chelsea Finn, P. Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. ICML, 2017.
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 Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference Learning Research, pp. 1942-1951 1951, PMLR, 09-15 15 Jun 2019. Btthtt:: //ppcceeccccc..... m www.preas//99/fforrsteo 9a html
Machine Learning, volume 97 of Proceedings of Machine
10

---

Published as a conference paper at ICLR 2022
Paul Gagniuc. Markov Chains: From Theory to Implementation and Experimentation. 05 2017.
ISBN 978-1-119-3875--8 doi: 10.1002/97811193375599
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sher- jil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https::/pproceddings www.:/iiinnnnnnnuinneeeee neurips.ps.... cct/papper/211//111e Papeeaa
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8):
1735-1780, 1997.
Timothy M. Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J. Storkey. Meta-learning in neural networks: survey. IEEE transactions on pattern analysis and machine intelligence, PP, 2021.
Hengyuan Hu and Jakob Foerster. Simplified action decoder for deep multi-agent reinforcement learning. In International Conference on Learning Representations, 2020. URL https://
openreview. www. forum B1-
Hengyuan Hu, Adam Lerer, Noam Brown, and Jakob N. Foerster. Learned belief search: Efficiently
improving policies policiis in partially observable settings. CoRR, abs/2106.09088, 2021. URL https:
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching, Journal of Machine Learning Research, 6(24):695-709) 2005. URL http:// hwtp://..../p/aa//////////
hyvarinen05a.. html
Leslie Pack Kaclbling, Michael L. Littman, and Anthony R. Cassandra. Plamning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1):99-1344 1998. ISSN
0004-3702. doi: httpa//cc.....co.c.oc.o..eoeeeaa sciencedirect.
URL httpps://wwy
Steven Kapturowski, Georg Ostrovski, Will Dabney, John Quan, and Remi Munos. Recurrent ex- perience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019. [tL[tttts///:pereeeee
net/ fet.:e/oooommlmrr..11
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Vojtëch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisy. Rethinking formal models of partially observable multiagent decision making, Artificial Intelligence, 303:103645, 2022.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. Proceedings of the AAAI Conference on Artificial Intelligence, 34005977177-714, Apr. 2020. doi: 10.1609/aaai. 10.1669%aaai..34055.60000 v34i05.6208.
URL https:
7/ojs. awai. www.aaa......naeee
AAAI
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, 3566663777688---1333 2017, doi: (0.1122 10.1126/science. aam6960.
Siyuan Qiao, Chenxi Liu, Wei Shen, and Alan Loddon Yuille. Few-shot image recognition by predicting parameters from activations. 2018 IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 7229-7238. 2018
L. Rabiner and B. Juang. An introduction to hidden markov models. IEEE ASSP Magazine, 3(1): 16, 1986. doi: 10.1 10.1009ASSP......11116

---

Published as a conference paper at ICLR 2022
L.R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-2866 1989. doi: 10.1109/5.18626.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 8821-8833 PMLR, 2021.
S. Ravi and H. Larochelle. Optimization as a model for few-shot learning, In ICLR, 2017.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, L. Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588 7839:604-609, 2020.
David Silver, Richard S. Sutton, and Martin Müller. Sample- cample-based learning and search with per- manent and transient memories. In Proceedings of the 25th International Conference Ma- chine Learning, ICMI '08, pp. 968-975, New York, NY, USA, 2008. Association for Com- doi: 10. 10.1145/139115..1999 13902788
puting Machinery. ISBN 9781605582054.
URL https:
//doi. 1ttp:/0011155//11115511 1390278
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis 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(6419): 1140- 1144, 2018
Samuel Sokota, Edward Lockhart, Finbarr Timbers, Elnaz Davoodi, Ryan D'Orazio, Neil Burch, Martin Schmid, Michael Bowling, and Mare Lanctot. Solving common-payotf games with ap- proximate policy iteration. Proceedings of the AAAI Conference on Artificial Intelligence, 35(11); 9695-9703. May 2021. URL hwk.hhttpss//oo...aaaa.ooooo//np wttp:e/pppp.AAAAaaiii.ccoo view/17166
Michal Sustr, Vojtëch Kovařík, and Viliam Lisy. Particle value functions in imperfect information games. In AAMAS Adaptive and Learning Agents Workshop, 2021.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neu- ral networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 27. Curran Asso- www.ennuriip.
ciates, Inc., 2014. URL
http://rrrssssee//////////////// wc./papeerr211//11ee Paper pdf
Gerald Tesauro et al. Temporal difference learning and td id-gammon. Communications of the ACM, 38(3):58-68 68, 1995.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, t. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems. volume 30. Curran Asso- ciates. Inc., 2017. URL /ttsss/t///pp
http:/pss..c//aee///////L1 pdf
A APPENDIX
A.1 RULES OF HANABI
The following rule description is quoted from the Hanabi challenge paper (Bard et al. 2020
Hanabi is game for two to five players, best described as type of cooperative solitaire. Each player holds hand four cards (or five, when playing with two three players). Each card depicts rank (I to 5) and colour (red, green, blue, yellow, and white); the deck (set of all cards) is composed of a total of 50 cards, 10 of each colour: three 1s, two 28, 3s, and 4s, and finally single 5. The goal
12

---

Play Finally, the active player may pick a card from their hand and attempt to play it. Playing card is successful if the card is the next in the sequence of its colour to be played. If the play is successful, the card is placed on top of the corresponding stack. When stack is completed (the 5 is played) the players also receive a new information token (if they have fewer than eight). The player can play a card even if they know nothing about it; but if the play is unsuccessful, the card is discarded (without yielding an information token) and the group loses one Published as a conference paper at ICLR 2022
of the game is to play cards to form five consecutively ordered stacks, for each colour, beginning with a card of rank and ending with a card of rank 5. What makes Hanabi special is that, unlike most card games, players can only see their partners' hands, and not their own. Players take turns doing one of three actions: giving hint, playing card from their hand, discarding card. We call the player whose turn it is the active player.
Hints On their turn, the active player can give a hint to any other player. A hint consists of choosing rank colour, and indicating to another player all of their cards that match the given rank or colour. Only ranks and colors that are present in the player's hand be hinted for. To make the game interesting, hints in limited supply. The game begins with the group owning eight information tokens, one of which consumed every time hint given. If no information tokens remain, hints cannot be given and the player must instead play or discard.
Discard Whenever fewer than cight information tokens remain, the active player can discard card from their hand. The discarded card is placed face up (along with any unsuccessfully played cards), visible to all players. Discarding has two effects: the player draws new card from the deck and an information token is recovered.
life, possibly ending the game. In either circumstances, a new card is drawn from the deck.
Game Over The game ends in one of three ways: either because the group has successfully played cards complete all five stacks, when three lives have been lost, or after a player draws the last card from the deck and every player has taken one final turn. If the game ends before three lives are lost, the group scores one point for each card in each stack, for maximum of 25.
A.2 ADDITIONAL EXPERIMENTS
We performed additional experiments of training epochs, and the size of the belief model. Note that we did not use the same networks for these results for the HMM results in the main body so they not directly comparable.
the effect of the number of fine-tuning steps, the number
A.2.1 NUMBER OF FINE-TUNING STEPS
In the main body, we used 10,000 gradient steps for all our experiments. Table we examine the effect of using fewer gradient steps in an HMM setting. We find that BFT can yield benefits even with as few as 100 gradient steps. We also find that the benefits appear to saturate after 1000 gradient steps. This, in part, may be because the belief model is already relatively good in the HMM case.
VO Belief
2.08 0.01
Seq2Seq
1.68 + 0.01
Seq2Seq + BFT(100 steps)
1.64 0.01
Seq2Seq BFT((000 steps)
1.61 + 0.01
Seq2Seq + BFT((0000 steps)
1.61 + 0.01
Table 6: Cross entropy per card with standard error for different settings, aggregated over 300 games.
13

---

Published as a conference paper at ICLR 2022
A.2.2 AMOUNT OF OFFLINE TRAINING
In the main body, our belief model was trained for 400 epochs offline. In Table we examine the performance of combining BFT with lower quality belief models in an HMM setting, We find that BFT can produce large improvements even when its original model performs poorly.
V0 Belief
2.08 = 0.01
Seq2Seq(400 epochs) Seq2Seq epochs) + BFT
1.68 + 0,01
1.61 + 0.01
Seq2Seq epochs) Seq2Seq(200 epochs) + BFT Seq2Seq( (100 epochs)
1.74 #.011
1.63 + 0.01
1.82 0.01
Seq2Seq( 100 epochs) BFT
1.70 + 0.01
Table 7: Cross entropy per card with standard error for different settings, aggregated over 300 games.
A.2.3 NETWORK SIZE AND PART OF NETWORK TUNED
In the main body of the paper, the belief model's encoder was a two layer LSTM with 512 hidden units, Also, in the main body of the paper, we performed fine-tuning only on the encoder. In Table we examine the effect of using smaller encoders and of fine-tuning the whole belief network, rather than just the encoder, in the HMM setting, We find that the benefits to performing fine-tuning may increase as the capacity of the belief network decreases, if fine-tuning is performed for the whole network. However, in the case that fine-tuning is performed only on the encoder, we did not observe this effect.
VO Belief
2.08 + 0.01
Seq2Seq(512 units) Seq2Seq(512 12 units) + (FT(Edn)
1.68 0.0T
1.61
Seq2Seq(512 units) + BFT(Full)
0.00
Seq2Seq(2555 (256 units)
1.76
Seq2Seq(256 units) + (FT(Enn)der)
1.00
Seq2Seq(256 units) + (Fl()
1.63
Seq2Seq units)
1.87 1.07
Seq2Seq units) + BFT(Encoder)
1.84
Seq2Seq(128 units) BFT(Full)
1.69 0.01
Table 8: Cross entropy per card with standard error for different settings, aggregated over 300 games.
A.3 DESCRIPTION ALGORITHM IMPLEMENTATION
We describe the instantiation of BFT we used for our Hanabi experiments. We used Seq2Seq model with LSTMs as encoders and an LSTM our encoder took the previous control variable 2 z--1, the current emission variable y". and summary of the history h(y", 20 ..........""............ y' and output next summary of the history Myr 20 ...... (....v")) = e(z'-1 y²: h(y", " ..... of ))- Our decoder d took the summary of the his- tory hiy", .....,y'" (1)) as input, and autoregressively modeled the Markov state Xt.
decoder. In particular,
1. Sample X--1 ,..., .t.,, Xt-1 do eg - 2, y ho(80,20 20 20....,y"
Sample X X(X!-1 2(11) for each i ,.....h.. hi
3. Sample Y V(X)) for each I.... k.
Set 0t + ming NLL(X; dg o egr (x X (1
2t 11) for I,...,k.
During fine-tuning time, first sample Markov states using the decoder with offline parameters 0, the encoder using the ine-tuned parameters from the previous time step gr-1, and the hidden state produced two time steps ago using the the offline parameters 0. In steps 2) and 3), propagate these samples forward to the current time step, as described in the main body of the paper. In the fourth step, fine-tune the parameters of the encoder (with the parameters initialized as the offline
14

---

Published as a conference paper at ICLR 2022
parameters f), using the decoder (with fixed offline parameters 0), and the fixed hidden state from the previous time step computed using offline parameters 8. The result of this fine tuning yields encoder parameters 6 For the FOSG setting, omitted 2 as input in step 1) and step 4) (i.e., only used step 2)).
An alternative instantiation, used for BFT(Full) in Table 8 fine-tunes both the encoder and the decoder. In this case dg replaced by dgr-1 in step 1), and da is replaced by dæ in step 4). Only fine-tuning the encoder has the advantage of preserving the equivalence between the encoding and the belief state, which may be useful for training belief state-dependent value functions in future work. However, fine-tuning the whole network can sometimes result better performance, as found in Table
RLSearch only requires samples from the current belief state. To provide these samples, time we generated samples from dg egi (=*-1, .y. ho 2..... =² , y)" Again, in the FOSG case we omitted the control variables. We sampled large number of Markov states prior the start of search, and then passed this empirical distribution of samples to our RLSearch implementation. Note that, if fine-tuning the whole network, de should be replaced with dg here.
15


Reviews:
[{"review_id": "z2prraYXjry", "reviewer": "Reviewer_kvNa", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "-- After Author Response --\n\nI am leaving my original review below for transparency, but my most significant concerns have been addressed. In particular:\n- The RLSearch paper has been accepted for presentation at NeurIPS 2021.\n- The authors have provided the sample sizes for their averages and they are sufficient to support their claims.\n\nI still think the authors should aim to make the paper more self-contained by providing more algorithmic details about RLSearch (which is a new approach), how it interacts with BFT, and why it was selected for these experiments instead of a more well-established search method.\n\n-- Original Review -- \n\nBelief state inference is an important step toward developing agents that can make sound decisions in partially observable environments. A great deal of effort has been spent studying exact inference or approximate inference with access to ground truth state distributions. This paper's focus on bringing this tool to more complex domains where representing distributions and performing exact inference are both a challenge is worthwhile and is bound to be of interest to the ICLR community. The results also fit into a larger story about neural network fine-tuning/meta-learning, which is certainly of interest.\n\nTechnically, the approach is only modestly novel, mainly applying an idea that has been studied elsewhere in a context where it hasn't been applied yet. That said, in my opinion, the empirical results are both novel and significant. In particular, the idea of directly learning a belief state model has not gained a lot of traction because it, frankly, doesn't work all that well! We can see in the 7-card Hanabi results that performing search on such a model yields essentially no benefit (we are lucky that it didn't cause harm!). The fact that the fine-tuning enabled the approximate belief model to yield a planning benefit is notable and a promising signpost toward future work, which might enable belief state inference to scale to larger, more interesting partially observable problems.\n\nAll that said, I do have a significant concern about this paper. The empirical results rely heavily on an existing algorithm called RLSearch. As far as I can tell, the paper that describes RLSearch has not been peer reviewed and has only been available on arXiv for about a month at time of reviewing. The paper makes a very brief attempt to explain RLSearch at a high level, and how that algorithm is altered for this paper, but this is not sufficient. From this paper, I do not know what algorithm is being performed in these experiments or why RLSearch is even a sound foundation to build upon, let alone why it is the right base algorithm to combine with BFT in order to answer these empirical questions. Can BFT be applied to other search methods? Is there some special synergy with RLSearch since they both appear to be fine-tuning methods? If the answers to these questions is no, then I would recommend using a baseline algorithm that is more established and better studied. If the answer is yes, then that needs to be made far more explicit and clear. If the answer is \"we don't know\" then I think that's a major missing piece of this work.\n\nThe fact is that the paper is not sufficiently self-contained and the parts that it doesn't contain haven't been peer reviewed. That makes me deeply uncomfortable and makes it difficult for me to confidently assess the technical quality and the significance of the findings.\n\nAnother concern I have is that I don't know how many independent trials are represented in the empirical results. Maybe I just missed it, but it seems like a very important detail to state. If the number is not sufficiently high, that would raise questions about the strength of the support for the conclusions.\n\nA couple of more minor issues:\n- The references section is, frankly, a mess. There is no consistency in the formatting and content of the references and some don't even list a venue, just authors, a title, and a year.\n- p. 2: \"At the time of writing, there has been no successful demonstration of this.\" It wasn't clear to me at this point what \"this\" refers to. Even now I'm not totally sure. It would be good to have a more clear expression of the open problem here.", "summary_of_the_paper": "This paper concerns the idea of directly learning a model of a belief state MDP from samples from the ground truth dynamics and observation models. One could then use that model for decision-time planning (e.g. some form of tree search). In particular, the paper aims to improve upon this idea by fine-tuning the belief state model before search using samples from local state region. Experiments are performed in Hanabi, showing that fine-tuning does improve belief accuracy and enables search through belief space to improve control performance in problems where exact inference is impractical.", "summary_of_the_review": "-- After Author Response --\n\nThe paper is well-written and considers an important and challenging problem. The empirical results seem to offer a path to progress in a direction that hasn't shown much promise. The paper could be improved by offering more details about RLSearch, a recently introduced approach upon which the experiments heavily rely.\n\n-- Original Summary -- \n\nThe paper is well-written and considers an important and challenging problem. The empirical results seem to offer a path to progress in a direction that hasn't shown much promise. However, the algorithmic results make heavy use of an algorithm that is not sufficiently described in this paper and that has not been peer-reviewed. Though I would really like to have these results in the literature, that makes me uncomfortable with recommending acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W_pqkBnElk0", "reviewer": "Reviewer_WyMC", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The abstract, introduction and background is very clearly written. It does a good job of introducing the problem to be solved and outlining the method to be used at a high level.\n\nThe method itself is rather mathematically simple. It is based on simple mathematical techniques in the area and effectively amounts to sampling from known distributions.\n\nWhile the authors state that they present an algorithm, it might be better to view this as a framework, as the method involves an externally supplied model as an input, and the fine tuning method needs to be tailored to this model. The experiments performed use only a single model, which limits the conclusions that can be drawn from the results.\n\nThe experimental results are only provided for a single domain, albeit for a HMM, POMDP and FOSG setting in the same model. The choice of domain seems rather poorly selected, as the basic models used as a comparison in the domain already appear to be almost optimal, meaning there is little improvement from the new technique - while the results may be statistically significant, they appear to be a very minor improvements in effect size.\n\nIt would be very useful to see some mention of time in the results section. The procedure doesn't appear particularly onerous but in a game playing setting, there may be time limits and any improvement in quality would need to be seen after X seconds, not after X iterations.\n\nThese criticisms aside, the experiments appear to be fairly conducted and reported, and look at sensible aspects of the problem, with a good choice of baselines/competitors.\n\n", "summary_of_the_paper": "The authors propose a new method for calculating distributions over states in Markov problems in which the true state is not directly observable. The method relies on using an existing model and then fine tuning the results online at each time step. Experiments presented show this gives a more accurate distribution, and that this more accurate distribution leads to statistically significant improvements in performance.", "summary_of_the_review": "The authors present an interesting idea well. However, the experimentation is very limited (even for a conference paper) and the results given show a very small effect size. More data is needed to convince that the technique is useful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GB_mxXkwJc5", "reviewer": "Reviewer_F3L2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This is an interesting paper that is fairly novel, as far as I know.  However, there were some problems in the exposition that left me feeling that I might have misunderstood some aspects of it.  I do think it will be important to clarify some of these points in any published version of the paper.  Many of my confusions were about the types or APIs of various components.  I will start with larger questions, and then list some minor ones.\n\nIn section 3.1, I immediately was confused by the type of b^{t+1}_{Y^{t+1}}.   Because Y is capitalized, it seems to be a random variable?  But that doesn't make a lot of sense to me.  Here are some possible interpretations of b^{t+1}_{Y^{t+1}}:\n- Given a particular observation Y_{t+1}, then it's just the next belief state (but why is Y capitalized?)\n- Not given an observation, it's a random variable over next beliefs b (where the distribution over b is introduced by distribution over observations)\n- Not given an observation, it's the next belief state we would get if we made no observation.\n- Not given an observation, it's some sort of expectation over the next belief (this is tricky, I think.)\n\nThe discussion of the sampling procedure (in that same section) says it produces samples of X^{t+1}---but it seems to be important that we are getting samples of the Y_{t+i}, as well, so we can use them to fine-tune our estimator.\n\nI'm not sure the analogy with approximate dynamic programming is helpful;  or, at least, it would help to clarify it.  In particular, is it critical to actually fine-tune \\theta?   An alternative would be to stick with the particle view, and use the sampled X's to represent the posterior belief, or use some combination of the belief produced by the parameteric model \\theta and the particles more explicitly, rather than actually changing the \\theta.   (To me, it would feel much more like ADP if you were training some function b_\\theta to represent the belief-state directly, on each iteration, which would be yet another possible approach I suppose, except that representing belief states is notoriously difficult.)\n\nI really wanted Figure 2 (which is called table 2) clarify things for me, but it really didn't help me at all.   I think something more like a data-flow diagram that illustrates how \\theta gets changed over time (and makes very clear that \\theta doesn't parameterize B (nothing parameterizes or really explicitly represents B itself), but instead parametrizes the state-estimator \"box\".) would be more helpful.\n\nThe standard error values seem quite small (given the amount of potential variance in the different training processes).  Please state very clearly exactly what sources of variance are being captured here:  initializations / batches /data for training the initial \\theta, randomness due to evolution of the game trajectory at runtime (due to card shuffling, randomness in agents' play, etc.), variance of sampling to generate the fine-tuning data, variance of the fine-tuning training (potentially due to batching I guess).   What were the various \"N\" values?\n\nThe performance improvements seem to be real, and interesting, but the gains aren't enormous.  This is fine, but I'm not sure I'd claim that performance is *greatly* improved.\n\nMore minor:\n- I appreciate the generality of the approach and the desire to be agnostic to the form and training details of f_\\theta, but I had to go digging, a bit, into other papers to try to understand the actual approach you used.  A bit more detail about that would have been helpful in understanding your approach.\n- In early parts of the paper you talked about going from step t to step t+1;  later it was from step t-1 to step t.\n- \"which is naively from independence assumptions\"\n- \"covariate distribution should not impact model performance\" (missing \"shift\")", "summary_of_the_paper": "This paper proposes a strategy for improving a trained parametric model for belief-state update, by generating and training on new data, online.  This strategy is particularly helpful for dealing with problems of covariate shift (when, e.g, the system has moved outside the training regime) and dependence on unobservable factors (e.g. the agent's policies in a game setting).   This fine-tuning strategy is shown both to improve the fidelity of belief-state updates and to have an ultimate impact in the quality of play in Hanabi, a game with a substantial amount of private information.", "summary_of_the_review": "This paper has interesting ideas that seem to be useful.  Clarity could be improved but interesting enough to publish.  I wanted to give it a 7.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6LGIztrusEu", "reviewer": "Reviewer_Pqjr", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nThe problem of learning and optimizing over belief states is an important problem in reinforcement learning, and while the ideas in this paper are not particularly novel, the core idea is implemented and tested well. I thought that the lack of details made certain section rocky, but in general found the paper a pleasure to read. \n\nStrengths:\n\n- Simplicity is perhaps the main strength of this paper: the method is very closely inspired by a wide body of existing work on belief filtering, and the method looks like fine-tuning a learned model on augmented data. Empirical details withstanding, the generic idea of re-allocating the \"capacity\" of a neural network at test-time in this way seems well-justified and simple to implement.\n\n- The paper is easy to read, and exposes the main concepts well.\n\nWeaknesses:\n\n- The paper is a little light on exact algorithmic details (and I did not see more in the appendix). In particular, I think it would be useful to exactly detail out the algorithm being proposed in a more fleshed-out manner somewhere in the main text or appendix. It would also be a good idea within Section 2 to more explicitly what the goal of the belief state modelling problem is, and what the belief state model will be used downstream for (as this dictates what approximations are useful / worthwhile). I found the latter point difficult to understand in the current treatment.\n- Along the same lines, I think it would be useful to more explicitly outline in the appendix exactly how BFT is used for down-stream decision-time planning (e.g. with RL Search). To generate an action at a time-step, is BFT (for 10k timesteps) run only once, or is it necessary to run multiple times within the policy search loop? \n- I found no details for exactly how the particular choice of 10,000 gradient steps for BFT were chosen. How sensitive is BFT to the number of gradient steps that are taken to fine-tune the learned model? How much does this depend on the quality of the original model: e.g. with a worse original model, does running BFT degrade the quality of the belief since BFT bootstraps off of the original model? \n- It seems that this problem assumes access to the \"true\" underlying state space and the transition dynamics / emission distributions in this state space, in which case the main purpose of the neural network is simply amortization of an exact search problem. It would be useful to make these assumptions more explicit earlier (perhaps even in the introduction). As a question to the authors, how would these techniques transfer to the setting where these assumptions do not hold (in particular, where the underlying state space $\\mathcal{X}$ is not known).\n- I think the point that the method works because it \"refocuses\" the capacity of the parametric belief state model is interesting, but I don't think it is supported very strongly by the provided data. It would be interesting to see whether these effects diminish as the neural network capacity increases (or equivalently, if the effects amplify as it decreases), since presumably, the better the original neural network is at the belief modelling problem, the less impact a fine-tuning step should have. Along these lines, I think it would be interesting to have some discussion as to whether fine-tuning procedures can simply be supplanted by training bigger networks.", "summary_of_the_paper": "This paper seeks to understand whether finetuning a learned belief state model can enable improvements in performance in partially observable problems, in particular in the Hanabi domain. The general intuition is that while the original parametric model is trained on a wide distribution of belief distributions / input histories, during deployment, the model need only be good on the sequence that is actually realized. The authors demonstrate that indeed such techniques lead to improved performance over a non-adaptive belief state method, in particular when there is significant stochasticity in the transitions.\n", "summary_of_the_review": "(Copied from above) The problem of learning and optimizing over belief states is an important problem in reinforcement learning, and while the ideas in this paper are not particularly novel, the core idea is implemented and tested well. I thought that the lack of details made certain section rocky, but in general found the paper a pleasure to read. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to fine tune the belief states of a MDP, for later using the learned model for decision-time planning, e.g. via search.
The contribution is well-presented, motivated and focused to a specific scenario, which is generally considered challenging in the literature. This scenario is exemplified by the cooperative card game Hanabi, which takes the role of the benchmarking setting for the empirical evaluation of the fine-tuning procedure.

The major concern raised in the review and discussion phases are about the limited evaluation, which is centered around only Hanabi, as well as the magnitudes of the improvements over previous baselines. However, three knowledgeable reviewers agreed that since the setting has been historically challenging, the reported improvements are in fact significant and potentially inspiring future works in this direction. 

The paper is accepted provided that the authors include and polish in the camera-ready the additional experiments over the parameter sensitivities, the ablation tests and the discussions highlighted by the reviewers in the comments.
Decision: Accept (Poster)