EvoGraphWM: A Structure-Evolving World Model with Adaptive Object Graph for Long-Horizon Tasks in Dynamic Environments

Long-horizon tasks are challenging due to their sparse rewards, where useful behaviour takes many steps to pay off. World models address such tasks by learning environment dynamics and optimising behaviour through imagined rollouts, which therefore need to stay accurate over long horizons. In dynamic environments, new objects continually appear as the agent explores, changing the structure required to represent the environment state. Existing world models fix the structure of their state representation as a holistic vector or a predefined set of object slots, leaving new objects uncaptured and their relations unmodelled, and the resulting errors compound over long-horizon imagination. To solve this problem, in this paper we propose a world model that evolves its state structure with the objects encountered during training. However, realising such structural evolution raises three challenges: 1) how to discover and prioritise new objects during training; 2) how to model the relations between newly discovered objects and those already known; 3) how to learn dynamics and behaviour over a structure-evolving state. To address them, we present EvoGraphWM, a structure-evolving world model centred on an adaptive object graph, whose nodes, focus, and relations evolve as the agent learns. EvoGraphWM consists of: (i) a Self-evolving Node Extractor that grows the node set, discovering new objects through the reconstruction error and prioritising the reward-relevant ones as dedicated nodes while the rest stay in a shared background; (ii) a Relational Dynamics Modeller that learns the graph's transition through collaborative node prediction, where object relations emerge; (iii) an Evolved Graph Integrator that anchors the adaptive object graph to a steady holistic state through two complementary routes, giving dynamics and behaviour a stable footing to learn from. Experiments demonstrate that EvoGraphWM outperforms strong baselines on both Crafter and Procgen Heist, and further keeps the imagined rollouts accurate over remarkably longer horizons.