This paper tackles one of the "holy grails" of artificial intelligence: making the theoretically perfect, but practically impossible, AIXI agent work in the real world.
The Problem: AIXI's Uncomputability
In the world of Reinforcement Learning (RL), AIXI is the gold standard. It is a mathematical definition of a "perfect" agent that uses Solomonoff induction to predict the environment and expectimax search to plan. There is just one problem: it is uncomputable. It assumes the environment is a universal Turing machine, which requires infinite computing power.
Previous attempts to approximate AIXI (like MC-AIXI) were limited to simple "Markovian" environments—situations where the current state tells you everything you need to know. However, real-world problems are often non-Markovian and highly structured. For example, in an epidemic, the "state" isn't just who is sick today; it is the entire history of contacts and previous vaccinations. This paper addresses the gap between AIXI's theoretical elegance and the messy, history-dependent nature of complex systems.
Methods: Bringing AIXI to Life
The authors propose $\Phi$-AIXI-CTW, a practical approximation of the mathematically optimal AIXI agent that uses higher-order logic to handle complex, structured environments. They introduce a three-part architecture:
- Logical State Abstractions: Instead of trying to model every possible detail of a history, the agent uses higher-order logic to define "predicates" (features). These predicates act as a lens, compressing a long history of actions and observations into a manageable "abstract state."
- RF-BDD (Random Forest Binary Decision Diagrams): Since there could be thousands of potential logical features, the agent needs to pick the best ones. The authors developed a feature selection method based on Binary Decision Diagrams. It identifies "sharp" mappings—features that are specifically good at predicting rewards, even when those rewards are sparse or infrequent.
- $\Phi$-BCTW (Generalized Context Tree Weighting): This is the "brain" of the agent. It performs Bayesian model learning by building a mixture of possible environment models. Unlike previous versions that only looked at raw bit-strings, this version uses the logical predicates as nodes in a tree to predict future rewards and states.
For the final step—deciding what to do—the agent uses $\rho$UCT, a variant of Monte Carlo Tree Search, to plan its actions based on its learned models.
Datasets and Evaluation
The researchers evaluated their agent on two fronts:
- Simple Benchmarks: Classic RL puzzles like Taxi, Jackpot, Stop Heist, and Biased Rock-Paper-Scissors.
- Epidemic Control: A complex, large-scale simulation using a real-world email contact network (1,133 nodes and over 5,000 edges). The agent had to decide when to quarantine individuals or distribute vaccines to stop a virus from spreading across the network.
Key Insights
- Reward-Centric Abstraction: The authors argue that standard state abstraction (which tries to compress the whole environment) is often inefficient. Their "sharpness" criterion focuses specifically on features that make the reward predictable. This is crucial for RL, where the goal isn't to understand everything, but to maximize a specific signal.
- Logic + Bayesian Learning: By using higher-order logic, the agent can incorporate "background knowledge" (like the structure of a graph) into a Bayesian framework. This allows the agent to reason about the environment in a way that raw neural networks often struggle with.
- Efficiency through Pruning: The use of BDDs to prune redundant features allows the agent to navigate a massive search space of potential logical rules without getting bogged down in "spurious splits" that don't actually help with learning.
Key Results
- Outperforming Baselines: In simple domains like Taxi and Jackpot, $\Phi$-AIXI-CTW significantly outperformed standard decision-tree-based RL methods (U-Tree and PARSS-DT), which failed to capture the necessary history-dependent features.
- Epidemic Mastery: In the epidemic simulation, the agent successfully learned sophisticated strategies. For instance, it learned to prioritize quarantine actions when the virus was highly infectious and shifted toward vaccination when vaccines were more effective.
- Feature Selection Matters: The RF-BDD method proved superior to standard Random Forest feature selection. Without the "sharpness" threshold, the agent couldn't find the specific features needed to understand the epidemic's spread.
Limitations and Future Work
Despite the progress, the authors note a few hurdles:
- Causal Blind Spots: The agent sometimes struggled with deep causal reasoning—for example, it might vaccinate the same person multiple times because it doesn't fully grasp that the first vaccination already "solved" the problem for that node.
- Predicate Engineering: While the agent is great at selecting features, the initial pool of 1,489 predicates was still human-defined. A major future goal is to have the agent automatically generate its own logical predicates from scratch.
- Privacy Concerns: Using full network data for epidemic control is powerful but raises privacy issues. The authors suggest that exploring "Differential Privacy" constraints is a vital next step for real-world deployment.
Summary updated