Technical Summary: Multi-Excitation Projective Simulation with a Many-Body Physics-Inspired Inductive Bias

1. Problem Statement

Deep learning models, while powerful, often function as opaque "oracles," making their decision-making processes difficult to interpret. This lack of transparency has driven the field of eXplainable Artificial Intelligence (XAI). One existing XAI framework, Projective Simulation (PS), models deliberation as a random walk of a single particle on a graph where vertices represent concepts (clips). While PS offers interpretability and potential for quantization, it suffers from a fundamental limitation: it cannot naturally model thoughts that combine multiple concepts simultaneously. In standard PS, a single excitation must carry all short-term information for a decision, preventing the disentangling of composite thought structures (e.g., logical deductions involving multiple variables).

Furthermore, a naive extension of PS to handle multiple simultaneous concepts (Multi-Excitation PS or MEPS) using hypergraphs faces exponential complexity. The size of the power set of vertices scales exponentially with the number of atomic clips, rendering the number of trainable parameters and the computational cost of a single random walk step intractable for all but the smallest graphs.

2. Methodology

Multi-Excitation Projective Simulation (MEPS)

The authors propose MEPS, a generalization of PS where deliberation is modeled as a random walk of multiple particles (excitations) on a hypergraph.

• Structure: The Episodic and Compositional Memory (ECM) is a weighted, directed hypergraph $G=(V, E, h)$. Vertices $V$ are atomic clips (concepts), and hyperedges $E$ connect sets of input clips to sets of output clips.
• State: The agent's state is an excitation configuration $C \subset V$, representing the set of currently relevant concepts.
• Dynamics: A deliberation step involves sampling a transition from the current configuration $C_{now}$ to a new configuration $C_{next}$ based on hyperedge weights (h-values).
• Learning: The agent learns via a reinforcement learning update rule adapted from PS, modifying h-values based on rewards and a "glow" factor for delayed rewards.

The Many-Body Physics-Inspired Inductive Bias

To overcome the exponential complexity of naive MEPS, the authors introduce an inductive bias inspired by quantum many-body physics.

• Core Concept: Just as physical phenomena often arise from interactions between a small number of particles (few-body interactions), the authors constrain MEPS transitions to be composed of elementary transitions involving only a few excitations at a time.
• Formalism: Instead of defining h-values for arbitrary subsets of vertices, the model defines trainable parameters for elementary transitions $(i, o)$, where $i$ ingoing excitations interact to produce $o$ outgoing excitations.
• Cutoff: A set $IO$ defines the allowed pairs of $(i, o)$. A cutoff is imposed such that $i + o \leq \text{max\_IO}$.
• Mechanism: In a single random walk step, the agent samples one elementary transition $(C^{(i)}_{in} \to C^{(o)}_{out})$ where $C^{(i)}_{in} \subset C_{now}$. The new configuration is formed by removing the input excitations and adding the output excitations: $C_{next} = (C_{now} \setminus C^{(i)}_{in}) \cup C^{(o)}_{out}$.
• Complexity Reduction: The authors prove that this bias reduces the number of trainable parameters and the complexity of a deliberation step from exponential ($O(2^{|V|})$) to polynomial ($O(|V|^{\text{max\_IO}})$). The degree of the polynomial is determined by the interaction cutoff.

Dynamic Hypergraphs and Layered Architectures

• Dynamic Hypergraphs: The training history is formalized as a dynamic hypergraph, allowing the visualization of how the agent's memory structure evolves over time.
• Layered Feed-Forward Variants: For specific applications, the authors define Inductive Bias 2FF (Feed-Forward), which restricts transitions to move excitations between layers (e.g., Percept $\to$ Hidden $\to$ Action). They also propose stricter variants (2SF and 2DP) to guarantee polynomial upper bounds on random walk lengths, preventing pathological "avalanches" of excitations.

3. Key Contributions

1. MEPS Framework: Introduction of a multi-particle random walk model on hypergraphs to represent composite thoughts and disentangled memory structures.
2. Physics-Inspired Inductive Bias: Formalization of a classical inductive bias derived from few-body interactions in quantum many-body physics. This reduces the computational complexity of MEPS from exponential to polynomial.
3. Theoretical Proofs: Proof that the inductive bias reduces the number of trainable parameters and the complexity of random walk steps to a polynomial degree determined by the interaction cutoff.
4. Dynamic Hypergraph Definition: A new definition for dynamic hypergraphs to model and visualize agent training histories.
5. Quantum Motivation: A formal derivation linking the classical inductive bias to the Hamiltonian of quantum many-body systems, outlining a path toward a quantum implementation of MEPS on quantum simulators.

4. Experimental Results

The authors evaluated MEPS with various inductive biases in three synthetic environments:

• Invasion Game with Distraction: A contextual bandit problem where the correct action depends on two relevant observables and one irrelevant "distraction."
  • Result: Agents with a 2-body inductive bias (matching the problem's complexity) learned the optimal policy fastest. A 1-body agent failed to solve the problem, while a 3-body agent (equivalent to standard PS) solved it but learned significantly slower due to the larger parameter space.
• Deceptive Invasion Game: An extension with more actions and a deceptive reward structure (parity-based).
  • Result: The 2-body agent again outperformed the 3-body agent. The 1-body agent failed to learn, getting stuck in suboptimal policies due to the inability to model the necessary composite logic.
• Computer Maintenance: A complex scenario modeling the diagnosis and repair of a broken computer, requiring a multi-layered chain of thought (Symptoms $\to$ Components/Causes $\to$ Fixes).
  • Result: A multi-layered MEPS agent with a specific inductive bias configuration achieved near-optimal performance with roughly 16,766 steps. In contrast, an unrestricted standard PS agent and a tabular PS-inspired multi-layer Q-learning agent required roughly 35,817 and 115,261 steps, respectively. The inductive bias agent used approximately 13 times fewer trainable parameters than the baselines.

5. Significance and Claims

The paper claims that MEPS, combined with the many-body inductive bias, offers a scalable and interpretable alternative to standard deep learning and tabular reinforcement learning methods for problems requiring composite reasoning.

• Interpretability: By explicitly representing multiple concepts simultaneously and using a hypergraph structure, MEPS provides a transparent "chain-of-thought" that can be visualized and analyzed.
• Efficiency: The inductive bias allows agents to solve complex tasks with significantly fewer parameters and training steps compared to unrestricted models, avoiding the "curse of dimensionality" inherent in naive hypergraph implementations.
• Biological and Physical Plausibility: The approach is motivated by the observation that human cognition and physical systems often rely on combining a limited number of factors simultaneously, rather than processing all possible combinations.
• Quantum Potential: The formal analogy to quantum many-body physics suggests a natural pathway for implementing MEPS on quantum hardware, potentially leveraging quantum speedups for deliberation.

The authors remain modest, noting that while the inductive bias restricts the hypothesis space, it aligns with human cognitive limitations and physical laws, suggesting it is a practical rather than a restrictive constraint. They acknowledge that further work is needed to optimize sampling algorithms and explore the integration of hypergraph literature techniques for further scalability.