IJCAI 2026 Papers

Optimization in industrial systems often involves calibrating from a semi-optimized state, where global exploration methods like Reinforcement Learning (RL) or Bayesian Optimization (BO) are inefficient or unsafe. We propose Causal Newton Optimization (CNO), an online algorithm that iteratively calibrates inputs under a known causal graph but unknown structural equations. CNO estimates local linear causal effects via additive interventions and employs a log-linear variance regression to robustly guide Newton-based updates. Evaluations on synthetic systems and a chemical plant simulator demonstrate that CNO achieves the best balance between objective improvement and robustness. While traditional PID control suits standard dynamical systems, CNO significantly outperforms RL and BO in complex structural causal models, providing the robust stability vital for safety-critical real-world applications.

Finding the maximum common induced subgraph (MCIS) between two graphs is a well-known NP-hard problem. While sequential MCIS algorithms have been extensively studied, parallel computing has emerged as an important direction for further performance enhancement with the advancement of computing resources. In this paper, we propose a parallel MCIS framework integrating a dynamic task decomposition method guided by search information and a novel pruning strategy based on shared information. The experimental results demonstrate that the algorithm enhanced by our framework achieves superior performance over both state-of-the-art sequential and existing parallel algorithms. Extensive results further demonstrate the wide scalability and generality of our framework, and the effectiveness of our strategies.

Many real-world applications require solving families of expensive multi-objective optimization problems~(EMOPs) under varying operational conditions. This can be formulated as parametric expensive multi-objective optimization problems (P-EMOPs) where each task parameter defines a distinct optimization instance. Current multi-objective Bayesian optimization methods have been widely used for finding finite sets of Pareto optimal solutions for each task. However, P-EMOPs present a fundamental challenge: the continuous task parameter space can contain infinite distinct problems, each requiring separate expensive evaluations. To address this, we propose learning an inverse model to amortize the multi-objective optimization cost across the continuous task-preference space, enabling direct solution prediction for any query without the need for expensive re-evaluation. This paper introduces a novel parametric multi-objective Bayesian optimizer that learns this inverse model by alternating between (1) generative solution sampling via conditional generative models and (2) acquisition-driven search leveraging inter-task synergies. This approach enables effective optimization across multiple tasks and finally achieves direct solution prediction for unseen parameterized EMOPs without re-evaluations. We theoretically justify the faster convergence by leveraging inter-task synergies through task-aware Gaussian processes. Based on that, empirical studies in synthetic and real-world benchmarks further verify the effectiveness of the proposed parametric optimizer.

Multi-objective evolutionary algorithms (MOEAs) are popular tools for multi-objective optimization (MOO), and have been successfully applied to many real-world MOO problems. However, the theoretical study has lagged behind their practical success and remains largely confined to synthetic pseudo-Boolean functions. To close this gap, this paper--drawing inspiration from a class of popular continuous problems with real-world relevance--introduces a multi-objective benchmark defined on an integer space, featuring an analyzable landscape and the presence of local optima. We conduct a running time analysis on the proposed benchmark and derive several theoretical results. Specifically, we prove that a widely-studied MOEA, GSEMO, using unit-step mutation can be trapped in local optimal regions and fail to identify the Pareto front. Fortunately, we find that this difficulty can be overcome either by incorporating an ageing mechanism or using heavy-tailed mutations that allow multi-valued changes along each dimension of an individual. In addition, we demonstrate the extendability of the proposed benchmark to more complex landscapes with numerous local optima, resembling well-established problems in the field (e.g., those from the ZDT and DTLZ suites). We hope this work is a step forward for the theoretical study of MOEAs on problems that are closely related to those commonly investigated in empirical research.

Parallel tempering, or the replica exchange method, is a Markov Chain Monte Carlo (MCMC) sampling technique for finding low-energy states in complex landscapes by executing multiple processes at different temperatures and allowing for states to migrate between parallel processes based on the Metropolis criterion. Despite a growing interest in the technique as a randomized search heuristic, it is not clear when and why parallel tempering is effective. We conduct a first runtime analysis of the parallel tempering algorithm on a simple quadratic unconstrained binary optimization problem that induces a rugged energy landscape with tunable parameters. We prove that a single-temperature Metropolis process fails to efficiently optimize the problem at any temperature. In sharp contrast, a two-state parallel tempering approach using a low and a high temperature typically solves the problem in O(n^2 log n) iterations. The low-temperature process ensures stability, as it is unlikely to accept worsenings, whereas the high-temperature process facilitates exploration by traversing energy barriers. Improvements are discovered through exploration in the high-temperature process and transferred to the low-temperature process, where they are permanently retained. This effective interplay between processes demonstrates the power of parallel tempering and lends credence to its design.

In recent years, theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical m-objective m-OneJumpZeroJump function (m-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes m-OJZJ asymptotically faster than NSGA-III without crossover for any number m of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on 4-OJZJ when crossover is turned off.

Finding an arbitrary number of shortest paths in a graph is a fundamental problem in Graph Theory and Artificial Intelligence with numerous applications to real-world problems. While some algorithms produce paths which might contain loops, the most interesting and challenging problem variant consists of finding simple (or loopless) paths. This problem has been addressed with algorithms which always conduct an arbitrary number of Dijkstra searches. While the current state-of-the-art leverages the notion of sidetrack edge, a new development upon sidetrack edges has been recently introduced which can be used to produce non-simple paths very efficiently, centroids. In this paper, centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijkstra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency. Experimental results across various domains show substantial improvements over the current state of the art, both in runtime and memory usage.

NeuroEvolution of Augmenting Topologies (NEAT) is a widely used neuroevolution algorithm for learning neural network architectures and weights for control tasks. However, standard offline optimisation searches for connection strengths directly, which can scale poorly in high-dimensional weight spaces and more difficult continuous control problems. Hybrid methods that combine neuroevolution with online learning can address this challenge, but their theoretical properties remain underexplored. This paper gives the first regret analysis for a general NeuroEvolutionary Online Learning (NEOL) framework, which decouples learning into two timescales: an outer loop for architecture search and an inner loop for online weight adaptation via reward-modulated plasticity. Under mild conditions, we prove that NEOL achieves sublinear regret. Empirically, under fixed interaction budgets on four standard control benchmarks, a NEAT-based NEOL implementation achieves higher final fitness and lower variance than pure NEAT, and is competitive with strong reinforcement learning (RL) baselines on several tasks. The results are supported by Wilcoxon rank-sum tests and ablation studies. Overall, the findings show that online plasticity can improve the sample efficiency and robustness of two-timescale neuroevolution. Code is available at https://github.com/boobaa2001/NeuroEvolution_Online_Learning_NEOL

Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number r > 2 of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an r-valued counterpart of the classic ONEMINMAX benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of O(n²r² log n) and a near-tight lower bound of Ω(n²r(r + log n)). We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of O(n²r(r + log n)), matching our lower bound, which also holds for this variant. Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.

Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm ?, we use ? to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.

In heuristic search, a well-known technique to speed up search while providing a suboptimality guarantee is to multiply the heuristic function by a weight w > 1. In this paper, we study the theoretical and practical implications of using such a technique in bi-objective heuristic search, a natural academic exercise that has remained unexplored. We introduce Weighted BOA∗ϵ (WBOA∗ ϵ ), a weighted version of the BOA* algorithm, which uses two real parameters: a weight w for the heuristic and an approximation factor ϵ. Higher values of w and ϵ allow for faster computation of approximate Pareto-optimal solution sets. We prove that WBOA∗ ϵ returns a representative solution set containing (w − 1, ϵ)-approximate solutions. We empirically compare it to A*pex, the state-of-the-art approximate bi-objective search algorithm. We find that WBOA∗ ϵ is competitive with A*pex: when using perfect heuristic functions, in road maps WBOA∗ϵ is faster for higher approximation factors, while in grid maps WBOA∗ϵ dominates A*pex. With imperfect heuristic functions, WBOA∗ϵ performs better than A*pex for lower approximation factors, while the opposite is true for larger approximation factors.

Evolutionary Algorithms (EAs) are currently the most popular tool for solving multi-objective optimization problems. Balancing exploration and exploitation is fundamental to the performance of Multi-Objective EAs (MOEAs). Achieving this requires maintaining a set of high-quality solutions for effective exploitation while simultaneously enabling exploration of diverse regions of the search space. In MOEAs, these two roles are typically fulfilled by a single evolutionary population. However, high-quality solutions that are promising for exploitation may lack the potential to guide the search toward different regions of the search space. Conversely, solutions with high exploratory potential that can lead the search toward more promising regions may themselves be of low quality. To address this issue, this paper proposes a dual-population MOEA with Exploration and Exploitation Decoupled (MOEA/EED): the exploration population uses a simple aging mechanism, while the exploitation population preserves the currently optimal solutions. We theoretically prove the benefits of MOEA/EED, i.e., it achieves the upper bounds, O(n^(k+1) · min{1, (e ln(3e) / k)^k}) and O((5e ln(3e))^(n/5)), on the expected running time for solving two commonly studied bi-objective problems OneJumpZeroJump and bi-objective RealRoyalRoad, which are significantly better (even exponentially smaller) than that of the popular SMS-EMOA, NSGA-II, and their non-elitist variants. Lastly, we empirically show its effectiveness on a wide range of practical optimization problems.

Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number ? of function evaluations, up to a maximum size of ?ₘₐₓ. We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size ? with high probability in O(? log² ?) function evaluations, which is considerably faster than the Θ(?² log ?) runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size ?, we show a runtime of O(?^? log² ?), improving upon the known runtime of Θ(?^(? + 1)). We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of ͠Ω(?).

Mobile Manipulation (MM) involves long-horizon decision-making over multi-stage compositions of heterogeneous skills, such as navigation and picking up objects. Despite recent progress, existing MM methods still face two key limitations: (i) low sample efficiency, due to ineffective use of redundant data generated during long-term MM interactions; and (ii) poor spatial generalization, as policies trained on specific tasks struggle to transfer to new spatial layouts without additional training. In this paper, we address these challenges through Adaptive Experience Selection (AES) and model-based dynamic imagination. In particular, AES makes MM agents pay more attention to critical experience fragments in long trajectories that affect task success, improving skill chain learning and mitigating skill forgetting. Based on AES, a Recurrent State-Space Model (RSSM) is introduced for Model-Predictive Forward Planning (MPFP) by capturing the coupled dynamics between the mobile base and the manipulator and imagining the dynamics of future manipulations. RSSM-based MPFP can reinforce MM skill learning on the current task while enabling effective generalization to new spatial layouts. Comparative studies across different experimental configurations demonstrate that our method significantly outperforms existing MM policies. Real-world experiments further validate the feasibility and practicality of our method. The source code is available at https://csu-hero-lab.github.io/SG-MM Web.

In human-aware vision-and-language navigation (HA-VLN), agents need to follow instructions while navigating safely among people in crowded environments. Existing methods often struggle to effectively transform forward-looking risk prediction into decision-making basis, resulting in intelligent agents being prone to collisions in crowded scenarios and taking overly cautious actions, thereby reducing navigation efficiency. Moreover, it is difficult for high-level decisions based on social norms to be stably implemented in dynamic crowd scenarios, which can easily lead to behavioral jitter and planning deviation. In this work, we propose the AHead-VLN, a navigation framework that incorporates forward-looking risk information in the reasoning process. Specifically, we designed the path risk association (PRA) module, which compiles future risks into structured risk events aligned with each candidate path, making risk information decision-ready for the large language model (LLM) reasoning. To balance executability and decision stability, we have further designed the hierarchical LLM planner (HLP) with two specialized components. The ``Brain'' LLM makes route choices based on instructions and risks, while the ``Cerebellum'' LLM prepares executable action scripts for candidate routes and retrieves the appropriate script for execution. Experiments on the HA-VLN benchmark show that AHead-VLN improves success while enhancing safety compared to strong baselines.

Vision-Language-Action (VLA) models have demonstrated strong capabilities in robotic manipulation, but their performance degrades significantly in long-horizon tasks due to cumulative error propagation. This limitation largely arises from static feature fusion mechanisms that rely on fixed weights to combine visual, language, and action representations, preventing the model from adapting to different phases of task execution. To address this limitation, we propose S²-VLA, a framework that introduces a State-Space Guided Adaptive Attention (SSGAA) mechanism. SSGAA maintains a belief state that tracks task progression and generates dynamic gating weights to adaptively fuse information from three complementary sources visual features for spatial perception, task intents for high-level task planning, and temporal action sequences for execution consistency. This adaptive fusion allows the model to shift its focus throughout task execution, aligning with the evolving requirements of different task stages. Despite its compact 2B parameter size, S²-VLA consistently outperforms larger 7B-scale models and achieves state-of-the-art performance on long-horizon manipulation benchmarks, including LIBERO and SimplerEnv. highlighting the importance of adaptive feature fusion for long-horizon robotic manipulation.

Humanoid robots have been increasingly deployed in real-world environments such as intelligent manufacturing, healthcare, and agriculture, from indoor spaces to outdoor terrains where friction conditions vary significantly. However, existing approaches such as domain randomization or employing estimation struggle to handle low-friction gait control and fail to address variable friction conditions, making it difficult to ensure control robustness. To address these challenges, we propose Walking on Ice (WoI), a friction-aware locomotion framework that combines proactive prediction with reactive adaptation for varying surface friction. We introduce a VLM-based friction predictor that enables the policy to take anticipatory actions before friction changing, thereby addressing variable-friction scenarios. Additionally, we design a friction estimator combined with a joint history encoder that perceives proprioceptive states to handle low-friction surfaces. Experimental results demonstrate that WoI improves success rate by 8.5% and reduces slip rate by 5.15% over the state-of-the-art method Denoising World Model Learning (DWL). Particularly, in extreme cases, WoI achieves 98.3% success rate with 51.0% higher survival rate, 3.20% lower slip rate, and 46.5% lower stuck rate than DWL, demonstrating stable and efficient gait adaptation. Our work provides a robust and efficient gait control framework for stable locomotion in real-world scenarios with dynamic friction conditions.

Redundant manipulators are broadly used in safety tasks that require precise execution. However, some actual factors, such as assembly defects and mechanical wear, inevitably introduce uncertainties in their physical parameters. Due to the insufficient excitation, existing methods fail to achieve high-accuracy physical parameter identification, which seriously affects the accurate operation of multiple safety tasks. Considering that quadratic programming (QP) can integrate desired behaviors with constraints into a unified optimization framework and can be solved online in real time, this paper formulates the collision-free trajectory tracking of redundant manipulators with uncertain structure as a QP problem, which describes the trajectory tracking, obstacle avoidance and joint motion limits simultaneously. To tackle the above issues, we first develop an online physical parameters identification method called regularization and zeroing neural dynamics (RZND) by using the state information of the manipulator, which realizes highly accurate physical parameters identification and real-time Jacobian matrix updates. On the basis of this, a multi-task quadruple projection neural network (MT-QPNN) solver is proposed by applying projection operators to handle the joint constraints, and further the trajectory tracking and obstacle avoidance tasks of the redundant manipulator are well achieved. Relative experiments verify that the presented RZND method and MT-QPNN solver can accurately identify physical parameters and enable collision-free tracking with superior performance.

We introduce missingness-MDPs (miss-MDPs), a novel subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. A miss-MDP is a POMDP whose observation function is a missingness function, specifying the probability that individual state features are missing (i.e., unobserved) at a time step. The literature distinguishes three canonical missingness types: (1) missing completely at random (MCAR), (2) missing at random (MAR), and (3) missing not at random (MNAR). The problem is to compute near-optimal policies for a miss-MDP with an unknown missingness function, given a dataset of action-observation histories. Achieving such optimality guarantees for policies requires learning the missingness function from data, which is infeasible for general POMDPs. To overcome this challenge, we exploit the structural properties of different missingness types to derive probably approximately correct (PAC) algorithms for learning the missingness function. These algorithms yield an approximate but fully specified miss-MDP that we solve using off-the-shelf planning methods. We prove that, with high probability, the resulting policies are ε-optimal in the true miss-MDP. Empirical results confirm the theory and demonstrate superior performance of our approach over two model-free methods.