Node Types: V = V_obj ∪ V_attr ∪ V_act ∪ {v_global}

• Object nodes V_obj — all distinct entities; unifies movable entities (robot, box, package) and spatial entities (rooms, hallways, waypoints). Persist across all beliefs; serve as the valid arguments for actions and attributes; encode type (e.g. is_location, is_item) and static attributes.
• Attribute instance nodes V_attr — one node per attribute–value assignment that holds with sufficient probability, e.g. At(robot) = kitchen. Created selectively only when particle support ≥ τ.
• Action nodes V_act — parameterized actions, e.g. move(?from, ?to), pick(?object); applicability read off their connections to entities and condition nodes.
• Global node v_global — maintains a holistic representation of the belief and propagates information across distant nodes in the graph.

Belief-Driven Sparsity: the Threshold τ

Attribute nodes are instantiated only with sufficient particle support — not all possible groundings

• Topology encodes the belief — a node's existence itself implies plausibility.
• Reduces computation — no nodes for unlikely hypotheses.
• Learn from structure — patterns come from structural presence/absence, not only numerical features.

Edge Types: E = E_attr-obj ∪ E_act-obj ∪ E_attr-act

• Attribute ↔ Object — each attribute node connects to the object it describes (owner) and to the node representing its value: At(robot) = kitchen links to both robot and kitchen. Edge features distinguish the two roles; edge weights carry the belief probability of the assignment.
• Action ↔ Object — actions link to objects that can serve as their parameters, capturing applicability constraints and expected outcomes. E.g. an edge from check(?rock) to rock₃ encodes that rock₃ can be checked, plus observation accuracy (decreasing with distance) and expected information gain.
• Attribute ↔ Action — attribute instances link to actions that require them as preconditions or produce them as effects, encoding how current beliefs constrain future actions and their outcomes.

Edge Features

• φ_type ∈ {0,1}¹⁰ — one-hot edge type; bidirectional edges get distinct types to capture directionality.
• φ_role ∈ {0,1}² — for attribute edges: connects to the owner object vs. the value node.
• φ_belief ∈ [0,1] — continuous probability: Σ_i w_i · 1[relationship holds in s_i].
• φ_support — categorical consensus level: unanimous (>95%) · strong (70–95%) · weak (30–70%) · split (<30%).

GNN: L Rounds of Message Passing

• φ_e, φ_v, φ_g are learned update functions; AGG is attention-weighted aggregation.
• The global node g enables rapid information propagation across distant nodes — crucial for maintaining performance as problem size increases.

Expert Data Generation & Loss

Supervised learning: V_θ : B → ℝ and π_φ : B × A → [0,1] from tuples (b_i, v_i*, π_i*)

• Run optimal or near-optimal planners on small instances where exact solutions are computationally feasible.
• At each belief: query expert for action and Q-values → execute in environment → update belief from the received observation.
• After the episode: compute discounted returns by backward induction, associating each visited belief with its value-to-go (Algorithm 3).

MCTS Integration: Three Enhancements

• Action prioritization — node expansion samples from the learned policy instead of uniformly:  a ∼ P_θ(·|φ(b))
• Value estimation — leaf nodes evaluated by network lookup instead of expensive rollouts:  v = V_θ(φ(b))
• Root action selection — combines visit counts with Q-values:  π(a|b) ∝ N(b,a)^z_n · exp(Q(b,a))^z_q

Tree traversal uses PUCT adapted from AlphaZero to the belief-space setting:

Implementation Details

Ablation: Policy & Value Networks Alone

* one-step look-ahead using only the value network. Same-size setting (Table 1).

Full Results: Same-Size (Table 1)

All methods trained and tested on the same problem size — Returns ± SE

* one-step look-ahead using only the value network. “—” = unsupported domain: BetaZero only supports LightDark and RockSample.

Full Results: Zero-Shot Generalization (Table 2)

GammaZero trained on small problems only; classical baselines run per-size — Returns ± SE

* one-step look-ahead. † search timeout/failure. BetaZero cannot run zero-shot at all (fixed input dimensions).

Graceful Degradation with Scale

• RockSample scaling: 17.8 → 10.2 → 3.5 across (15,15) → (20,20) → (25,25) — despite never training beyond 10×10.
• At (25,25), all methods struggle with timeouts — and the raw policy network alone is the best performer (4.8 ± 1.2): structural patterns learned on small instances transfer even when search itself becomes intractable.
• Performance degrades gradually, not catastrophically, as size exceeds the training distribution — fixed-dimensional approaches cannot process out-of-distribution inputs at all.

Domain Details & State-Space Sizes

• LightDark(d) — 1D localization under state uncertainty; noisy observations improve near a “light” region at distance d. Larger d requires longer-horizon information gathering.
• RockSample(n,k) — n×n grid, k rocks of unknown quality; distance-dependent noisy sensor. |S| = O(n² · 2^k) — from 12,800 states at (7,8) to over 400 million at (20,20).
• MultiObjectSearch(n,k) — find and declare k hidden objects with a range-limited sensor with detection probability ε. |S| = O(n^2(k+1) · 2^k).
• Rearrangement(n,k) — mobile manipulation domain introduced for this evaluation: locate k objects with unknown positions and transport them to goal locations. |S| = O(n^2(k+1) · 4 · 2^k) — perceptual uncertainty combined with multi-step planning.

Baselines

• BetaZero (Moss et al. 2024) — state-of-the-art learning-based POMDP planner: offline policy/value networks from expert demonstrations + online MCTS. Requires separate training for each problem size due to its fixed-dimensional belief representation.
• POMCPOW (Sunberg & Kochenderfer 2018) — extends POMCP to continuous observation spaces via progressive widening; tested with domain-specific heuristics.
• DESPOT (Ye et al. 2017) — scenario sampling builds a sparse belief tree; regularization balances policy size against estimated value.
• AdaOPS (Wu et al. 2021) — adaptively adjusts particle beliefs to maintain value function bounds; tested with fixed bounds on problems where QMDP is intractable.

Limitation: Object-Centric Scope

• Scope is object-centric POMDPs: the state must decompose into discrete entities with typed attributes and inter-entity relations (e.g. spatial adjacency, prerequisite dependencies).
• Graph construction assumes V_obj is known at planning time.
• Domains where objects appear, disappear, or have unknown cardinality would require dynamic graph construction.

Limitation: Independent Per-Attribute Marginals

• The graph approximates the joint belief through independent per-attribute distributions — particle weights are aggregated per attribute-value pair.
• Inter-attribute correlations are not preserved: two beliefs with identical marginals but different correlations produce the same graph.
• Paper's example: a correlation like “all objects are co-located” present in the particles is lost in the graph.
• Capturing joint structure would require higher-order representations such as hyperedges.

Limitation: Discrete Action Spaces

• The current formulation assumes discrete action spaces — each grounded action is a node in V_act.
• Extending to continuous actions requires modifications to the action-node representation.
• Listed as a future direction alongside continuous state spaces.

Relation to Prior Work

• Learning for online POMDP planning (BetaZero, ConstrainedZero, LeTS-Drive) — learn offline, guide online search; all rely on fixed-size belief representations predetermined per domain. GammaZero's graphs handle variable-sized problems and capture action–state relationships.
• Classical online planners (POMCP, POMCPOW, DESPOT, AdaOPS) — rely on domain-specific heuristics for value estimation and action selection; GammaZero learns these instead.
• Generalized classical planning — GPL: globally consistent value estimates get harder at scale; ASNets: fixed-depth architecture limits long dependency chains; GRAPL: no explicit action-object / parameter-dependency modeling.
• GABAR (Mangannavar et al. 2025) — action-centric graphs with GNN encoder + GRU decoder for deterministic planning; strong generalization but cannot handle belief uncertainty. GammaZero extends the graph representation to POMDPs: encode belief uncertainty while preserving the structural patterns that enable generalization.

Future Directions

• Hierarchical graph representations for extreme-scale problems.
• Continuous state and action spaces.
• Self-supervised learning to reduce dependence on expert demonstrations.

Search Budget: 1000–2000× Fewer Simulations

Values from the experiment configurations.

Same Base Search — Only the Representation Differs

• GammaZero and BetaZero use the exact same base MCTS algorithm (PUCT): same solver code, same particle-filter infrastructure.
• If the base algorithm explained the results, the two would be identical — Table 1 shows GammaZero matches or beats BetaZero at the same size. The difference is the graph representation.
• BetaZero's search is actually tuned harder on RockSample: c = 50, depth = 15, progressive widening disabled — GammaZero evaluates with c = 1.0, depth = 10.
• Ablation: the raw policy network with no MCTS at all reaches 60–80% of full performance — if search were doing the heavy lifting, that column would be near zero.

Baselines Use Hand-Crafted Heuristics — We Use None

• POMCPOW — LightDark: Local Approximate Value Iteration heuristic (1,000 iterations, 1,000 samples); RockSample: RSExitSolver (“move east”) heuristic.
• AdaOPS — lower bound: random-rollout value / RSExitSolver; upper bound: LAVI approximation / QMDP (fully observable relaxation).
• DESPOT — lower bound: random rollout / RSExitSolver rollout; upper bound: problem-specific / fully observable value bound (QMDP); default action: RSExitSolver.
• GammaZero — replaces all of these with the learned GNN: no hand-crafted value bounds, no domain rollout policies.

GammaZero: MCTS Parameters per Domain

From the experiment configurations.

GammaZero: GNN Architecture per Domain

From the experiment configurations.

GammaZero: Training Hyperparameters

Value loss: MSE · policy loss: cross-entropy · dynamic loss scaling: EMA α = 0.9 · hardware: RTX 3080, 2–4 h per domain.

BetaZero Configuration (Direct Competitor)

Cannot generalize to new problem sizes — requires retraining per size. Note the harder-tuned search on RockSample (c=50, depth=15, no widening).

Classical Baseline Configurations

From the experiment configurations. All classical baselines run per-size with these domain-specific bounds and heuristics.