Additional Experiments

To help address reviewer feedback, we have conducted additional experiments described below. Due to discussion-phase constraints, we report results for a representative subset of configurations; full results will appear in the final version. We believe these experiments significantly strengthen our empirical evaluation. The rebuttal to Reviewer YTdG follows the description of these experiments.

Additional Experiment: Wall-Clock Time [AE1]

We benchmarked a single update step using time.perf_counter() on a 2019 MacBook Pro (Intel i7). Each experiment ran 5,000 updates on a randomly generated size-8 grid in both 2D and 3D. To reduce the impact of outliers, we removed any measurements below Q1–1.5·IQR or above Q3+1.5·IQR, where IQR = Q3–Q1. Results (in seconds):

To compare against fine-tuning methods, we also timed gradient updates for the recurrent model used in Section 5. Using a precomputed batch of size 32 (5,000 batches), we measured the average time per update (excluding batch preparation):

Additional Experiment: Larger Grid without Exact Posteriors [AE2]

In the randomized setting, we evaluate on a size 15 grid with 3 dimensions and 4 obstacles (size 4 cubes). We report the mean JS divergence over 100 runs of 15 filtering steps, using a particle filter with 2,048 particles as a ground-truth proxy for training and evaluation:

Additional Experiment: Enhanced Recurrent Baseline [AE3]

We increased the Recurrent baseline’s capacity and provided the grid layout as input features in the randomized setting. On size 8 grids with 3 dimensions and 2 size 3 cubes, we compare:

• Recurrent (ORIGINAL) from Section 5
• Recurrent (MODIFIED): 4 hidden layers × 128 units, receiving k-hot obstacle encodings

We ran 500 episodes of length 15 under random policies and report the mean JS divergence averaged over each sequence:

Note: Both recurrent baselines perform well in early timesteps but degrade later, highlighting the challenge of belief modeling without explicit policy information despite increased capacity and additional grid features.

---

Rebuttal to Reviewer YTdG

We thank the reviewer for the helpful comments regarding clarity and the notation change. We will address those comments in the revision. The reviewer is also correct that the updated weights are not reweighted by $T_G$.

I would argue that the contribution is limited, as this embedding just serves as a novel resampling step in the particle filter method.

We respectfully disagree that the embedding merely serves as a resampling step for particle filtering. NBF's learned representation has numerous advantages over empirical distributions of particles found in a particle filter. Please see the comment on originality in the response to Reviewer HrMH for more details.

Why consider policy and system? The policy could be integrated and be seen as part of the system, like often done in filtering.

We believe that considering policy and system separately is well-motivated by learning in multi-player games, where the rest of the system is stationary but the policy is non-stationary and changes according to the learning dynamics specified by the algorithm.

We thank the reviewer for the detailed review and insightful comments. We have added experiments (described in the rebuttal to Reviewer YTdG) to help address the reviewer's feedback and improve the paper.

NBF depends on the assumption that the embedding model is expressive enough to represent every belief state exactly. This is a strong requirement, and it's not clear how realistic it is in practice, especially in higher-dimensional or dynamic settings.

The reviewer is correct that Theorem 1 (NBF consistency) has strong requirements about the embeddings model's expressiveness. Model expressiveness is an important factor in NBF's performance, but a perfect model is not strictly necessary to achieve good belief approximations in practice. The baseline Approx Beliefs in the GridWorld and Goofspiel experiments show the model has significant approximation error, and NBF still outputs better approximations than the baseline particle filters, with fewer particles.

The experiments also suggest that NBF’s performance drops as environments get more complex, as in the randomized Gridworld and larger Goofspiel variants (Figures 5 and 6). This points to a limitation in how well the belief approximation holds up under harder conditions.

The reviewer is also correct to point out that NBF's performance drops as the complexity of the task increases. This is expected, as we keep the embedding model complexity and the number of particles consistent across differing sizes of Gridworld and Goofspiel. Standard particle filters are well known to have poor scalability as dimensionality increases (Thrun 2002), and though our experiments are on relatively small domains, we observe this happening. For example, on 8x8 grids, particle filters with more particles than states in the environment's state space fail to achieve belief approximations comparable in quality to NBF with 16 particles. Our experiments are designed to demonstrate that, in some domains, we can bypass these scaling issues given a suitable embedding model.

Also, the belief embeddings themselves are computed using a weighted mean over sample embeddings (Section 3.1), which feels like a simplification. This approach might miss important structure in the distribution, like multimodality or higher-order interactions, which could be especially problematic in more complex scenarios.

By computing the mean over pointwise embeddings, we are effectively computing expectations over feature maps, which in the case of characteristic kernel embeddings is shown to be sufficient to uniquely identify distributions (Song et al., 2009). Our method for embedding beliefs has a finite-dimensional feature space and doesn't carry the same guarantees, but that doesn't mean the embeddings we use cannot parameterize distributions with multi-modality or higher-order interactions. For example, consider a Gridworld with two obstacles in opposite corners. Given a uniform prior on the grid, upon observing a collision with an obstacle, the resulting posterior distribution is bimodal with significant mass concentrated near each obstacle. This and similar situations occur regularly in our Gridworld experiments from Section 5.

However, for a fair comparison, the number of particles alone isn’t the right metric—it would be more meaningful to compare models under a similar computational budget.

We agree with the reviewer's concerns about fairness and evaluating methods under a similar computational budget. To address this, we have conducted the additional experiment EA1. We measure wall clock time for NBF and particle filters of varying size. In size 8 grids, we see that NBF with 32 particles is significantly faster than a particle filter with 128 particles.

The consistency guarantee of NBF (Theorem 4.1) assumes ϵ-global observation positivity. How generic or realistic is this assumption in practical settings?

$\epsilon$-global positivity is a simplifying assumption that helps avoid the case where all weights in the estimator are equal to zero in the analysis. It is violated in both Goofspiel and Gridworld because certain observations have zero chance of occurring in some states. For example, in Goofspiel, if the opponent has already played all cards smaller than $c$, there is zero chance that the player can play $c$ and observe that they played the higher card. In practice, this is not a problem outside of the unlikely event that all generated particles carry zero weight after a single step. This is an instant form of particle impoverishment, and could happen in some domains, but any particle-based approaches that follow the paradigm laid out on lines 173-175 would be similarly affected. We did not observe this happening in our experiments.

Finally, the donut example in Figure 2 is useful for building intuition on the learned densities, but the paper could benefit from a more concrete illustration of the learned embeddings as well, to understand what the model is learning (to simplify the task for visualization purposes you could also fix the donut width).

Could the reviewer please clarify this point? As we understand, we agree with the reviewer that visualizing what the model is learning would be interesting, but we use an embedding size of eight for the donut example (even though donuts are generated from three parameters in closed form).

We thank the reviewer for the detailed feedback and will use it to improve the paper. We have added experiments (described in the rebuttal to Reviewer YTdG) to help address the reviewer's comments.

Originality

First, we would like to make some broad clarifications on the originality of the work. NBF doesn't just provide a novel resampling scheme. Aside from the ability to sample from outside the support of the particle filter's empirical distribution, it also provides a continuous representation of the belief state that has numerous advantages over particle filters. For example, we are unaware of methods for evaluating densities of points outside the particle set, but NBF can query the density of any point in the sample space. NBF opens up new avenues for future work that builds on the ability to track belief embeddings over sequences of observations. One example is approximating value functions that map belief states to real numbers. Such value functions are key to many state-of-the-art depth-limited search methods, but it is not clear how to effectively learn them over sets of particles that do not encompass the full support of the belief distribution (Sustr et al, 2021). We would also like to reiterate Reviewer jFmS's comment that "The proposed approach is based on well-known ideas (vector embedding, normalising flow, particle filter), but the combination is new and interesting."

Training embeddings of $p(x)$ requires samples of all the possible posteriors induced by the problem.

We don't need samples from all possible posterior distributions to achieve good generalization if there is some learnable underlying structure. For example, the set of donut distributions from Section 3.2 is infinitely large, but given samples from a sufficient number of example donuts, we can learn the structure and generalize to unseen donuts.

It is unclear whether this method can scale to more complex and larger problems than ones investigated in the paper. Related to the previous point, I imagine getting representative samples of posterior distributions can be extremely difficult as the problem becomes more complex

Building a training set has the same requirements as a standard particle filter: the ability to simulate the relevant environment dynamics and policies. We thank the reviewer for this question because this was not clear from the original set of experiments. As a result, we include a new experiment (AE2) to address this. Running a large particle filter offline and training on the approximate belief states results in a model with which NBF outperforms particle filters with an order of magnitude more particles. Collecting posteriors in this manner is more scalable than computing them exactly and still trades off more expensive offline computation for faster updates at test time. NBF with 16 particles significantly outperforms a standard particle filter with 256 particles in this domain, and we expect that this trend would continue to larger grid sizes.

RNN baseline - available information / capacity

We have also included another experiment (AE3) to help address the reviewer's concerns about fairness in comparison to the RNN baseline. In Experiment AE3, we train a larger Recurrent baseline in the 3-dimensional, size eight grid, and provide it with k-hot encoded obstacle locations. Increased capacity and obstacle locations do not help the RNN baseline perform significantly better in the randomized setting. Considering this baseline's good performance in the fixed setting, we suspect that differences in policies significantly impact the belief state, and it is generally not clear how to incorporate policy information into the model.

We thank the reviewer for their detailed review. The additional references and valuable suggestions about the development will significantly improve the paper. We commit to implementing the clarity suggestions throughout. We have added experiments (described in the rebuttal to Reviewer YTdG) to help address the reviewer's comments.

However, the paper only mentions the "vanilla" (standard) particle filter, and it completely ignores the substantial body of work on the particle filter that aims to address its shortcomings

We thank the reviewer for their suggestions regarding other particle filtering variants that help mitigate impoverishment and the need for large numbers of particles in environments with high dimensionality. We commit to adding a discussion regarding the referenced papers and the tradeoffs they make to mitigate impoverishment in the related work section of our revision. As mentioned in the response to Reviewer HrMH's originality concerns, the belief embeddings maintained by NBF offer significant advantages over the empirical distributions of particles maintained by particle filters. The comparisons to the standard SIR filter help demonstrate that NBF mitigates impoverishment, while also offering a novel representation of beliefs. Furthermore, unlike NBF, the proposed improvements to vanilla particle filters require developing domain-specific operators or exploiting the underlying structure of states in the environment. For example, Rao-Blackwellized Particle Filters rely on the ability to exploit the underlying structure of the state and analytically marginalize out parts of it, and EPF requires domain-dependent genetic operators.

There exist other approaches for embedding beliefs (see e.g. Song et al. (2009)), but these are not discussed in the paper

We thank the reviewer for pointing us to Song et al. (2009). Their approach uses a fixed RKHS kernel to embed conditional distributions, which gives the desirable property of embedding uniqueness if a characteristic kernel is used. However, it hinges on choosing a kernel up front and risking mismatches with the structure of the set of the target posteriors. Instead, we learn a compact finite-dimensional feature map for embedding distributions together with a generative model, end-to-end. This lets the model discover a latent embedding space suitable for generating samples from the set of posteriors needed for NBF. We’ll include a discussion on this trade-off in the revision.

The choice of representing all beliefs that are expected to be encountered during filtering by the latent representation is not well motivated in the paper.

We agree with the reviewer that, for some problems, learning this latent representation for an arbitrary target set of belief distributions may be challenging. However, we demonstrate that when we can learn an embedding model effectively, NBF yields a clear computational benefit during inference and a compelling alternative to methods that ignore potential underlying structure in the belief state. Discerning the limits of where NBF is applicable remains an interesting and open question. We will clarify this in the revised version.

one could e.g. demonstrate how well the proposed approach scales with problem complexity by using more complex scenarios and comparing the results of the proposed filter with that of a particle filter with a large number of particles (to provide an accurate estimate of the true belief, instead of a competing method)

We thank the reviewer for the insightful suggestion to use a large particle filter to approximate true beliefs in more complex settings. We have added a proof-of-concept in Additional Experiment AE2, where we use a large particle filter to generate training data and as an approximation of the ground truth for evaluation. Under these conditions, NBF with 16 particles significantly outperforms a particle filter with 256 particles. These results show that NBF doesn't require samples from all exact posteriors to outperform more computationally expensive particle filters in some domains.

The proposed approach is not evaluated against other neural-based filtering approaches (e.g. that by Sokota et al. (2022)). Without an evaluation, the supposed high computation cost of these methods mentioned in lines 316-318 remains speculation.

Experiment AE1 shows that the cost of performing a gradient update to our model is roughly 1.5x slower than a single step of NBF with 32 particles in Gridworld. Though the cost of an individual step may seem small, Belief Fine-Tuning uses 10,000 fine-tuning steps at every decision point (Sokota et al., 2022). Simpler environments might require significantly fewer gradient updates, but even 1000 or 100 updates add significant overhead relative to a step of NBF. This difference is potentially exacerbated in downstream tasks where beliefs are frequently updated.

how costly is the inference expected to be for more complex scenarios and continuous state spaces

The wall clock time experiments (AE1) also suggest that the cost of inference in NBF can be comparable to a particle filter with more particles. This, of course, depends on model size, number of particles, and the complexity of simulating the environment one step. Complex environments may require more expressive, slower models, but on the other hand, computation time may also be dominated by particle simulation.

While we only evaluate our work in discrete settings (outside of the toy donut example), we expect our approach will extend to continuous state spaces because Normalizing flows are better suited to continuous data. For the discrete state spaces, we require additional tricks like Variation Dequantization. Verifying this is an important next step.