acceptodds
Under review as a conference paper at ICLR 2027

Belief Embedding Tree Search

Abstract

Beliefs in a Partially Observable Markov Decision Process (POMDP) are posterior distributions over the hidden state given the agent's history of actions and observations. They summarize everything the history says about the state, so planning in a POMDP is planning in a Markov decision process (MDP) over beliefs. Belief MDPs have continuous state spaces even for finite POMDPs, and exact planning in them is intractable in general. Planners must therefore approximate beliefs and estimate values. Monte Carlo planners do both inside a search tree, with an approximate belief at every node and a value estimate at every leaf. Approximations usually consist of sets of sampled states, with leaf values coming from rollouts, hand-designed bounds, or learned networks. Policies and values computed from these approximations are limited by approximation quality, and prior methods with learned networks rely on hand-chosen summaries of the sampled states to compute them. A belief representation should be computable from the parent node's representation using the POMDP's dynamics and it should let the search sample from it, but it should also be learned so that it provides the information needed to condition policies and values functions. We present Belief Embedding Tree Search (BETS), a Monte Carlo planner that meets these requirements by representing each node's belief with a generative distribution embedding (GDE) while updating it through the POMDP dynamics. BETS trains its belief model alongside its policy and value networks through experience, with the realized hidden state of the POMDP as the belief model's training target. We evaluate BETS on six configurations of RockSample, LightDark, and PocMan against BetaZero and three planners without learned components. BETS is competitive or leading on all six, while every baseline falls far behind on at least one. Where beliefs are highest-dimensional, it outperforms them by a large margin, even without search.

Primary area:
reinforcement learning
Keywords:
MCTS, Search, POMDP, Planning, Beliefs, Embedding

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_bM9nOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes BETS (Belief Embedding Tree Search), a Monte Carlo planner for POMDPs that represents the belief at every search-tree node with a generative distribution embedding (GDE) instead of a particle set. Expanding a leaf is one Neural Bayesian Filtering (NBF) update, which regenerates particles from the parent node’s embedding, propagates them through the known dynamics, reweights them by the observation likelihood, and re-embeds the weighted set — so the impoverishment that accumulates under repeated resampling in particle filters does not accumulate across updates. Prior methods such as BetaZero also guide the search with learned policy and value networks, but condition them on hand-chosen summary statistics of a particle filter (per-variable mean and standard deviation), which cannot represent dependence between state variables or multimodal marginals. BETS conditions its networks directly on the embedding, and extends GDEs with a variable-coupling stream that pools pairwise co-occurrence statistics explicitly. The belief model and both networks are trained jointly on self-collected episodes. On six configurations of RockSample, LightDark, and PocMan, BETS is competitive or leading everywhere, with large margins on the configurations with the highest-dimensional beliefs.

Critical strengths
  1. Well-motivated, elegant design. The motivation is laid out clearly: (1) tracking beliefs with particle filters suffers from long-term particle impoverishment, and (2) summarizing the particle set with per-variable statistics (as BetaZero does) discards the dependence between state variables and the shape of the marginals. BETS keeps BetaZero’s overall loop but replaces the particle set with a single object — the NBF embedding — that satisfies the three requirements the paper states: updatable from the parent node through the known dynamics, sampleable for simulation, and learned so the networks can condition on it.

  2. The value-prediction experiment (Table 2b) isolates the representational claim from search effects: with identical value-network architectures and data, embeddings predict returns more accurately than the moments of a particle filter with 16x as many particles. This turns “higher returns” into direct evidence for the paper’s stated mechanism.

Critical weaknesses
  1. The variable-coupling stream is underspecified, and its contribution cannot be verified as written. The mechanism in Section 3.3 appears mostly in the Figure 2 caption; Appendix C.1 covers only the generator, and the paper contains no encoder equations. Three components are left undefined: (a) the “joint feature of each pair of variables” averaged over samples is never defined; (b) the per-variable “variable summaries” appear only in the caption, so the block diagram cannot be reconstructed from the main text; (c) the attention-bias mechanism is unspecified (how is the pair feature projected into a bias?). Finally, the motivating b_excl/b_co​ example is not tested empirically. A small synthetic experiment, using the two-cell example or k-bit parity beliefs, could demonstrate that the pooled encoder fails to capture the joint distribution while VC recovers it.

  2. No learning-based baseline outside the known-model planning family. The policy network alone outperforms every baseline with search on RockSample(20,20) and both PocMan mazes, suggesting that, once it learns a sufficient belief statistic, acting on these benchmarks is largely reactive. The paper therefore cannot rule out that a recurrent model-free agent (e.g., recurrent PPO or R2D2), trained at a matched budget of simulated environment interactions — optionally with an asymmetric critic to match BETS’s privileged access to the realized hidden state during training — would be competitive without any explicit belief tracking.

Questions for authors

First, I have the following suggestions for improving the clarity of the paper:

  1. Figure 1 shows a single edge for each action at both the root and internal nodes. However, my understanding is that each action node also branches over the sampled observations. Please revise the figure or its caption to clarify this point, as the current depiction was misleading on a first read.

  2. Including pseudocode for the training loop would improve the clarity of Section 4.

  3. I encourage the authors to expand Section 3.3 to provide a more detailed explanation of the proposed variable-coupling embeddings.

  4. A small empirical evaluation based on the b_excl/b_co​​ example would provide useful empirical support for the main argument.

Regarding questions, my main question is how the proposed methods compare with model-free approaches.

1 comment

We thank the reviewer for their review and useful suggestions which led to substantial improvements.

Based on your suggestions, we have added additional details to improve clarity of the paper. We have revised Figure 1 and its caption to include observation nodes. Appendix A contains pseudocode detailing the training procedure. Section 3.3, Appendix D.1 and Table 3 now contain details about the (fixed) variable-coupling stream, including the three missing pieces mentioned in the review. We apologize for not including them in the initial version.

We have also evaluated variable-coupling embeddings in a synthetic task based on the example from Section 2.2 which led us to an edge-case that the original VC formulation didn't cover. Please see the experiment, the fix and the results in the general response. The revised submission contains description of the fixed version.

Regarding the requested model-free baseline, we implemented Recurrent PPO and ran it on the smaller configuration of each domain. A GRU actor-critic replaces both the belief model and the search. At every step the policy receives the observation, its previous action and the same features of the observed part of the state that the BETS policy and value networks receive; the critic uses the two-hot value parameterization of BETS. We ran it with a standard critic and, as suggested, with an asymmetric critic that also sees the full simulator state during training. Evaluation follows the same setup as in the paper: three training seeds, 300 episodes at each of three evaluation seeds, greedy actions, mean discounted return with the SEM across training seeds.

DomainPPOPPO, asymmetric criticBETS searchBETS policy
RockSample(15, 15)15.76 ±\pm 1.1012.15 ±\pm 0.7120.78 ±\pm 0.0920.65 ±\pm 0.10
LightDark(5)4.12 ±\pm 0.024.13 ±\pm 0.023.61 ±\pm 0.103.77 ±\pm 0.12
PocMan(M)46.56 ±\pm 1.0251.32 ±\pm 2.0378.08 ±\pm 0.5472.42 ±\pm 2.05

Recurrent PPO is above BETS on LightDark(5), where the belief is one-dimensional. On PocMan(M) it reaches about 60 to 65% of the return of BETS with search (above BetaZero's 40.87), its training curves are flat after 5×1075 \times 10^7 steps, and the asymmetric critic adds about 5. On RockSample(15, 15), under-tuned PPO stays on a trivial policy at all three seeds (4.35): it checks and samples the rock next to the start and then idles until the horizon. With a constant learning rate, an entropy bonus annealed from 0.2 to 0.01 and four times the budget of the other two domains, it reaches the numbers in the table: about three quarters of the return of BETS with the standard critic, and less with the asymmetric one.

Each PPO run trains on 1.3×1081.3 \times 10^8 environment steps (5.2×1085.2 \times 10^8 on RockSample), roughly 100 times the real environment steps of a BETS run. The general response contains a table listing estimated training costs of BETS, BetaZero and Recurrent PPO. We commit to including Recurrent PPO as a baseline in all six configurations in the final version of the paper.

Reviewer_aKBCOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents Belief Embedding Tree Search (BETS), a Monte Carlo planning algorithm for partially observable Markov decision processes (POMDPs). The method represents beliefs at search tree nodes using generative distribution embeddings (GDEs), which allow the planner to sample hidden states and update beliefs through Neural Bayesian Filtering (NBF). Building on this representation, BETS introduces learned policy and value networks to guide the search. The belief model and policy/value networks are trained concurrently using experience collected by the planner. The approach is evaluated on six configurations of RockSample, LightDark, and PocMan, against BetaZero, POMCPOW, DESPOT, and AdaOPS. Additional experiments investigate the contribution of variable-coupling embeddings and compare the predictive quality of different belief representations.

Critical strengths
  • Relevance to the conference: the topic of the paper is relevant to the ICLR community.
  • Significance/impact: introducing embeddings in MCTS-based planning could be useful to allow its scaling to larger domains, so the problem tackled, and the proposed technique are significant and the paper could have a good good impact.
  • Writing quality and paper organization: The paper is generally clear and well structured. It motivates the limitations of particle summaries, presents the planner and training procedure in separate sections, and includes diagrams and appendices that help explain the architecture and experimental settings. I only suggest to reduce the problem definition part in the abstract and introduction, and to provide more information about the contribution, both methodological and empirical.
  • Novelty/originality: The proposed framework builds directly on Neural Bayesian Filtering (Solinas et al., 2025) and BetaZero. BETS’s main novelty relative to BetaZero is where the learned belief representation sits in the planner. BetaZero retains particle sets in its search tree and gives its policy and value networks hand-designed particle statistics; BETS stores a learned generative distribution embedding at each node, updates it with Neural Bayesian Filtering, and samples from its conditional generator. Its variable-coupling stream also explicitly targets dependencies between hidden-state variables. This makes BETS a substantive change to the belief representation and update within MCTS, rather than simply a different network input.
  • Reproducibility: The paper provides substantial implementation detail, including domain descriptions, hyperparameters, training schedules, baseline settings, and timing measurements in the appendices. The source code is also included as supplementary material and will be released publicly.
  • Problem formulation and clarity: The target problem is clear: particle-based beliefs can impoverish, while per-variable summaries can discard multimodality and dependencies that matter for decisions. The paper explains why those limitations motivate a learned belief representation.
  • Method description: The main components are described in enough detail to follow the proposed algorithm. In particular, the paper explains the root’s paired simulations, PUCT selection at interior nodes, the KL-regularized policy improvement step, and the training targets.
Critical weaknesses
  • Theoretical analysis: An important weakness of the proposed method is that the paper does not present any formal performance guarantee or error bounds. Its training objective has a sound interpretation (i.e., minimizing realized-state negative log likelihood trains the model toward the conditional state distribution given the sampled particle set) but this does not guarantee that the set retains all information in the history, that the learned embedding approximates the true posterior, or that errors in the belief update produce bounded errors in value or policy. The paper acknowledges possible loss of support during an update, but provides no quantitative analysis of this failure mode or of how belief errors accumulate through search. The empirical results therefore support performance on the tested tasks, not guarantees of posterior accuracy or planner performance. Although the NLL training objective encourages accurate state prediction, it does not establish that the embedding preserves decision-relevant information or that BETS approaches an optimal policy. The authors should either provide guarantees under explicit assumptions - such as bounds on filtering and planning error - or temper their claims and discuss these theoretical limitations.
  • Missing/Incomplete comparison with state-of-the-art methods: The contribution should be positioned more carefully as an extension of learned, belief-guided search and filtering. The paper cites BetaZero (Moss et al., 2024) and the building blocks Neural Bayesian Filtering (NBF) (Solinas et al., 2025) and GDE (Fishman et al., 2025), but does not cite related work such as Learned Belief Search (Hu et al., 2021; AAAI-21 Reinforcement Learning in Games workshop) or The Wasserstein Believer (ICLR 2024), which also learn belief models or updates for partially observable decision-making. Regarding NBF, it introduces the generative belief representation and recursive belief updates underlying BETS. Although the paper extends this framework with learned policy and value networks, variable-coupling embeddings, and additional search mechanisms, the methodological novelty of these extensions remains insufficiently substantiated. In particular, the paper does not clearly establish their individual contributions to the overall performance. Learning Online Belief Prediction for Efficient POMDP Planning in Autonomous Driving (Huang et al., 2024; arXiv:2401.15315) also combines a learned latent belief update with MCTS. These works are not all directly comparable benchmarks, but discussing them - and clarifying what the proposed version adds would make the originality claim more convincing. More targeted ablation studies would help assess the significance of the proposed extensions beyond the existing NBF framework. All these methods should be also evaluated in the experimental section. In particular, the paper cites NBF but does not compare against it as a belief-modeling alternative or isolate its effect in a planner. Hu, H., Lerer, A., Brown, N., & Foerster, J. (2021). “Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings.” arXiv:2106.09086. Presented at the AAAI-21 Workshop on Reinforcement Learning in Games (RLG). arXiv · Workshop schedule arxiv.org Avalos, R., Delgrange, F., Nowé, A., Pérez, G. A., & Roijers, D. M. (2024). “The Wasserstein Believer: Learning Belief Updates for Partially Observable Environments through Reliable Latent Space Models.” International Conference on Learning Representations (ICLR 2024).
  • Comparison with state of the art: beside the missing comparison with NBF, BetaZero is the only recent learned planner in the comparison; AdaOPS, DESPOT, and POMCPOW are established planners without learned components. Some classical baselines also lack domain heuristics in particular settings, as noted in Table 1. The results establish a useful comparison with these baselines, but do not yet show how BETS fares against a broader set of contemporary learned belief or planning methods.
  • Experimental evaluation quality: The headline results use three training seeds for BETS and BetaZero. That is a limited basis for claims about consistent advantages, especially when return differences are small; the paper does not report statistical tests for the main Table 1 comparisons. The attribution of BETS’s gains to belief representation is also partly interpretive: the PocMan ablations help, but do not fully separate representation quality from other differences in the planner and training setup.
  • Isolation of the methodological contribution providing the performance improvement: Although BETS achieves substantial improvements over BetaZero, the two methods differ in several aspects beyond belief representation, including search strategy and training procedure. The variable-coupling ablation is useful, but does not isolate the contribution of NBF from the other components. Moreover, the claimed advantage of avoiding particle impoverishment is not supported by a direct evaluation of belief accuracy, as generative updates may still introduce and propagate approximation errors. Overall, the results demonstrate strong performance, but do not clearly establish which components are responsible for the improvements.
  • Results: Overall, the results demonstrate strong performance, but provide limited evidence explaining which components are responsible for the improvements.
  • Relationship between dembedding size and performance: No systematic embedding-dimension study is reported. Appendix Table 3 gives the chosen dimensions—32 for RockSample and LightDark, 64 for PocMan—but does not vary them to measure performance. Table 2 compares the 64-dimensional variable-coupling model with a 128-dimensional pooled model, but it removes the coupling stream while increasing dimension, so the effects are confounded. It therefore does not establish how performance changes as embedding dimension increases.
Questions for authors
  1. Could the authors clarify the main methodological advances of BETS over Neural Bayesian Filtering (Solinas et al., 2025) and BetaZero (Moss et al., 2024)? In particular, which components represent the most significant contributions beyond integrating NBF into Monte Carlo Tree Search? 2. Could the authors provide a more controlled ablation separating the contributions of the belief representation, paired root simulations, and KL-regularized policy improvement? This would help identify which components are primarily responsible for the reported improvements. 3. Have the authors evaluated how accurately the learned embeddings approximate the true posterior over successive belief updates? 4. How does BETS scale with increasing state-space dimensionality, action-space size, and planning horizon? Could the authors discuss the computational complexity of this architecture and its scalability to larger and more complex environments? 5. Please elaborate on the weaknesses reported above. This paper is actually borderline in my opinion, it has good potential but il looks still not very mature, so clarifications could make me increase my final score.
3 comments

We thank the reviewer for their thorough review.

Missing theoretical analysis. BETS is built from two components, GDEs and NBF, both of which come with theoretical guarantees. These results transfer to BETS under the same assumptions. GDEs show that a correctly specified model that attains the minimum of its training objective recovers the belief from its samples. Under several conditions, NBF has been shown to be a consistent estimator, i.e. for any finite horizon and any bounded function of the state, its estimate converges almost surely to the posterior as the number of particles grows at the Monte Carlo rate of Op(n−1/2)\mathcal{O}_p(n^{-1/2}). Under these assumptions BETS plans on the exact posterior in the limit, and since the posterior is a sufficient statistic of the history, no decision-relevant information is lost. Additionally, the Wasserstein Believer paper presents several theoretical results that we believe may be adaptable to BETS. We plan to pursue these theoretical results further as well as temper our language and discuss remaining theoretical limitations in the final revision.

Missing SOTA comparisons. Thank you for these suggestions.

Learned Belief Search uses an autoregressive belief model, that is similar to ours; it feeds hidden states to the simulator to estimate the expected return of a belief using a pre-trained policy and a value network. However, LBS's belief model contains a recurrent layer that learns an implicit belief representation. Such an approach has to learn the dynamics and the observation function of the environment as opposed to BETS which assumes an access to the environment model and thus avoids the added approximation error that stems from inaccurate approximation of the dynamics. Furthermore, LBS lists belief re-training on search trajectories and purely online belief training, things BETS was built around from the start, as future work.

The Wasserstein Believer learns both the dynamics and the observation function as well as a belief model over these learned components. Similarly to BETS, it passes the belief representation to the learned policy and value networks. On the other hand, BETS assumes an access to the true dynamics functions and it is not obvious whether WBU's approach to belief modeling is applicable to true dynamics functions as it seems its loss needs transition and observation densities which simulators usually do not provide.

The paper "Learning Online Belief Prediction for Efficient POMDP Planning in Autonomous Driving" combines MCTS with a learned belief planner which uses a recurrent network to update the beliefs trained by a forecasting loss that does not ensure the learned hidden state is a sufficient statistic of the belief.

We will better position BETS among and add a discussion about the cited papers in the final version of the paper. Based on the discussion above, we still believe that BetaZero is the closest directly comparable learned search baseline. Its paper also reports the performance of the same baselines with additional heuristics. Lastly, some of the raised points talk about a missing comparison to NBF. NBF is only a filtering algorithm and a component of BETS. It does not have the capabilities to solve POMDPs by maximizing agent's expected return. Could the reviewer please clarify what they meant by this point?

Ablations of the components. We agree that it is not obvious which components provide most performance gains. Although the new VC ablation on the synthetic task (available in the general response) partly answers this point (including the confounded comparison of the variable-coupling vs. the pooled stream in Table 2a that you have raised), we will test the gains provided by the remaining components in isolation and report the results in the final version of the paper. This includes the paired root simulations, KL-regularized policy improvement, and the relationship between the embedding size and the performance. Regarding the unsupported advantage claim of particle impoverishment mitigation, we believe this has been sufficiently demonstrated in the NBF paper where such a question is more appropriate. BETS uses NBF as presented in its paper and thus inherits its performance benefits and limitations.

Experimental evaluation. As mentioned in the general response, we commit to re-training all our models due to the changes in the VC stream and we additionally commit to adding further seeds and statistical tests to strenghten the comparison. Likewise a learned search-free baseline will also be added in the final version.

Answers to questions.

  1. Thanks to NBF, BETS enjoys significantly more accurate belief tracking that directly influences its performance in two meaningful ways: 1) as search samples and directly starts from hidden states, more accurate beliefs allow a better utilization of the provided search budget as fewer simulations are wasted on impossible states, and 2) learned embeddings are better suited as inputs to policy and value networks than summary statistics that BetaZero uses which is directly supported by the results in Table 2b. Additionally, BETS is not just a combination of NBF with MCTS. The techniques presented here combine with any decision-making algorithm that trains on its own data and uses policy and/or value networks as those benefit from improved state representations, especially in partially observable domains.
  2. Yes, we commit to including additional ablation studies to better understand which components provide biggest performance gains.
  3. Due to the sizes of beliefs in our environments, evaluating the quality of their approximations against the true posteriors is not easily achievable. Just computing the true posteriors deeper in the trees is not possible. However, such an evaluation on a smaller domain is available in the NBF paper.
  4. We have estimated the training costs in the general response. Additionally, the six domains cover state spaces ranging from one-dimensional in LightDark to 20 and 22 dimensional in RockSample(20, 20) and PocMan(L), respectively. Action spaces range from 3 and 4 actions in LightDark and PocMan to 25 actions in RockSample(20, 20). As BETS uses MCTS, it can be applied to large (or continuous) state and action space with progressive observation and action widening. Additionally, our mean planning horizons are 7/18 steps in LightDark, 34/48 steps in RockSample and 68/131 in PocMan.

I thank the authors for their explanation and answers. I will consider them in my discussion with other reviewers. Although several aspects have been clarified, my feeling is still that the work has strong potential, but it is not fully mature for publication in the ICLR proceedings. In particular, the theoretical analysis is only partially discussed in the rebuttal, but it should be fully developed in the final version of the paper, and it is difficult to understand how it can affect it.

Reviewer_m2uROpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes an MC tree search planner for POMDP. It stores a learned belief embedding at every node (instead of a particle set). The embedding can then both generate these states that the search simulates, as well as serve as the input to the policy and value networks. This is unlike previous methods (e.g., Beta Zero) which may require particle summaries. Variate coupling is also added to the embedding. Experiment on six benchmarks showed that the proposed method (BETS) is competitive or works best. Ablations show that the gains in performance come from embedding and coupling streams rather than the model size.

Critical strengths

I think the idea of using learned belief embeddings is novel, as it avoids particle collapse. Also, the scheme that they use, where they learn belief embeddings feeds the search, the policy and value networks. They show that BetaZero which feeds its networks the mean and standard deviation of each state variable has serious limitations e.g., The example that they gave for BetaZero where two beliefs with identical means and standard deviations but no states in common, so any network that sees only those numbers has to treat them the same. Their proposed method fixes this limitation.

Critical weaknesses

The paper compares various methods at equal number of simulations. Which this, however, does not mean comparison at equal compute. I think it's important because as I understand it each BETS simulation costs far more than a baseline's i.e., a GPU neural filter update plus two network passes, against a cheap simulator step and rollout. The training cost for BETS are not described, even though training runs full search at every step. Consequently, the paper doesn't show whether BETS's search results would hold at equal time or compute.

Questions for authors

Since a BETS simulation costs much more than a baseline simulation, does BETS still outperform the baselines when every method gets the same time per decision instead of the same number of simulations?

1 comment

We thank the reviewer for their positive review.

Unfortunately, due to the choices of programming languages, a fair compute-matched comparison is not easily doable. BETS is fully implemented in JAX, whereas all reported baselines, including BetaZero, are implemented in Julia. BetaZero also splits its computation between the CPU and the GPU. To ensure correctness we reused the official BetaZero implementation along with its baselines. However, we have estimated several statistics of the training costs (available in the general response) and we will properly measure these statistics during re-training.

Additionally, we can look at the published NBF wall-clock numbers and its comparison to Particle filters presented in Appendix E, Table 12 of the NBF paper. As NBF contains a neural network and simulates a set of particles forward through the environment during every update step, its computational performance heavily depends on the size of the network and the speed of the environment. From Table 12, NBF's wall clock roughly matches that of a Particle filter with 32x more particles while achieving significantly better results. However, the gap shrinks when sample dimensionality and the cost of an environment step increase. Apart from this, BETS and BetaZero share much of the search mechanism. Both algorithms run the same number of search simulations and node expansion entails the same steps, only the filters differ. Both algorithms query the policy and the value network once during expansion. The only remaining differences are that 1) BETS generates K/∣A∣K / |A| distinct root particles which involves NBF's generative model, while BetaZero only samples KK particles from its existing pool, and 2) during training BETS generates and propagates particles when processing belief training data, whereas BetaZero only computes the summary statistics.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response - Estimated Training Costs

Below we provide the estimated cost of one training run. Samples seen is gradient steps times batch size and real steps are those of the acting agent. BetaZero's estimates of real steps are only rough estimates as we did not track its mean episode lengths during training.

DomainMethodGradient stepsSamples seenReal steps
RockSample(15,15)BETS150k4.8M~3.2M
RockSample(15,15)BetaZero39.5k40M1.3M to 3.0M
RockSample(15,15)PPO64k2.1B524M
RockSample(20,20)BETS300k9.6M~6.4M
RockSample(20,20)BetaZero39.5k40M2.1M to 3.0M
LightDark(5)BETS75k2.4M~1.6M
LightDark(5)BetaZero118.5k120M0.12M to 1.5M
LightDark(5)PPO16k524M131M
LightDark(10)BETS150k4.8M~3.2M
LightDark(10)BetaZero118.5k120M0.30M to 1.5M
PocMan(M)BETS60k1.9M~1.3M
PocMan(M)BetaZero31.6k32M0.67M to 1.1M
PocMan(M)PPO16k524M131M
PocMan(L)BETS60k1.9M~1.3M
PocMan(L)BetaZero31.6k32M1.1M

BETS takes its gradient steps on batches of 32 and BetaZero on batches of 1024, so BETS sees 4 to 50 times fewer training samples than BetaZero, while it plays 1.1 to 13 times as many real episodes. At evaluation both run the same number of simulations KK on the same number of particles nn, so both make about KnK n simulator calls per decision.

AuthorsOpenReview ↗

General Response - VC Embeddings on a Synthetic Task

Variable-coupling embeddings on a synthetic task

Based on the Reviewer bM9n's raised point we include an ablation experiment that quantifies the improvement brought by the (now-fixed) variable-coupling embeddings. We believe this also partly answers one of the points raised by Reviewer aKBC.

Setup. We generalize the example of Section 2.2 to DD binary cells, where cell jj is occupied with a fixed probability pjp_j. Each belief splits the cells into random pairs and links the two cells of each pair in one of two ways: they are occupied together as often as their probabilities allow (co-occurring) or as rarely as possible (exclusive). For example, with pj=0.3p_j = 0.3 and pk=0.6p_k = 0.6, a co-occurring pair never has jj occupied without kk, and an exclusive pair never has both occupied. The link decides how the two values line up, not how often each cell is occupied, so every belief gives cell jj the same probability pjp_j. Statistics computed one cell at a time, such as per-cell means and standard deviations, are therefore identical for all beliefs, and only statistics of pairs of cells can tell them apart. We use two settings: pj=1/2p_j = 1/2 for every cell, which for D=2D = 2 is exactly bcob_{\mathrm{co}} versus bexclb_{\mathrm{excl}}, and pjp_j spread evenly over [0.15,0.85][0.15, 0.85]. Due to space constraints, training and evaluation details are only in Appendix E.1 of the revised paper.

Original formulation and its results. With pj=1/2p_j = 1/2 for every cell all variable summaries coincide, so the tokens of the paper's VC stream are identical, and attention over identical values returns the same vector whatever the pair-feature biases are. Its coupling summaries are then identical for every belief in the family (numerically to 10−710^{-7}), so it can do no better than its pooled stream. Looking at the table below, this is the case from D=8D = 8 on. VC is on par with a baseline whose generator keeps the marginals, but ignores the pairing. With distinct marginals, the original formulation recovers the pairing almost exactly. It also outperforms both sizes of the pooled embedding. With pj=1/2p_j = 1/2 its coupling summaries are the same for every belief: it learns the pairing at D=4D = 4 through its pooled stream and stays at the level of ignoring it from D=8D = 8 on, on every seed.

The fix and its results. We fixed the problem of matching coupling summaries by adding a learned linear map of the pair's edge features together with a learned embedding of the attended variable to every attention value. A description of the current version of the stream is in Section 3.3 and Appendix D.1 of the revision. Adding these additional features allows the pair statistics to reach the coupling summaries even when all marginals coincide. The VC (fixed) column of the table below uses the fixed stream.

VC now recovers the pairing almost exactly in every setting. It matches or improves on the original formulation when marginals differ. With spread marginals the pooled stream loses most of the pairing from D=12D = 12 on, and widening it to the embedding size of VC makes it worse, so the gain comes from the coupling structure rather than from the embedding size. With pj=1/2p_j = 1/2 the pooled models learn the pairing at D=4D = 4, in only one of three seeds at D=8D = 8, and stay at or near the level of ignoring it from D=12D = 12 on.

Excess bits ±\pm SEM over 3 seeds, with the ruled-out mass in parentheses:

MarginalsDDVC (submitted)VC (fixed)PooledPooled, widenedIgnores pairing
spread40.000 (0.0%)0.000 (0.0%)0.000 (0.0%)0.000 (0.0%)0.57 (23%)
spread80.009 ±\pm 0.003 (0.2%)0.002 ±\pm 0.001 (0.0%)0.014 ±\pm 0.002 (0.3%)0.012 ±\pm 0.002 (0.2%)1.30 (42%)
spread120.008 ±\pm 0.001 (0.2%)0.005 ±\pm 0.001 (0.0%)0.92 ±\pm 0.07 (28%)1.85 ±\pm 0.11 (48%)2.08 (57%)
spread160.018 ±\pm 0.004 (0.4%)0.008 ±\pm 0.002 (0.1%)2.02 ±\pm 0.06 (50%)2.84 ±\pm 0.01 (62%)2.87 (68%)
1/21/240.000 (0.0%)0.000 (0.0%)0.000 (0.0%)0.000 (0.0%)2.00 (75%)
1/21/284.00 ±\pm 0.00 (94%)0.000 (0.0%)2.07 ±\pm 1.16 (56%)2.68 ±\pm 1.32 (63%)4.00 (94%)
1/21/2126.00 ±\pm 0.00 (98%)0.000 (0.0%)5.18 ±\pm 0.82 (95%)6.00 ±\pm 0.00 (98%)6.00 (98%)
1/21/2168.00 ±\pm 0.00 (99.6%)0.010 ±\pm 0.006 (0.2%)8.00 ±\pm 0.00 (99.6%)8.00 ±\pm 0.00 (99.6%)8.00 (99.6%)

As the VC fix can influence the reported performance in RockSample and PocMan, we will re-train BETS on these environments before the final version of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.