Understanding the atomistic models underlying experimentally observed oxide surface reconstructions remains an active area of research, requiring efficient exploration of the high-dimensional potential energy surface. In a previous study, we identified several alternative low-energy (n×1)-SrTiO₃ (110) surface reconstructions at low titanium chemical potential by combining the covariance matrix adaptation evolution strategy (CMA-ES) with randomly generated initial structures and a fine-tuned MACE potential, where all but the readout layer were frozen. This approach required only 23 DFT calculations to reproduce the reported results [1]. We are now extending this methodology to the more challenging Ti-rich (2×4)-SrTiO₃ (110) surface reconstructions, which involve more degrees of freedom and a broader range of stoichiometries. To address this, we have incorporated mirror symmetry constraints and developed a multistep optimization strategy that iteratively builds up the stoichiometry. Our second ongoing project combines Gaussian process regressors (GPRs) with MACE foundation models to provide uncertainty estimates and guide active learning by selecting the most informative structures for fine-tuning; [1] R. Wanzenböck, E. Doloszeski, and G. K. Madsen, A Gentle Push: Data Efficiency in Fine-Tuning Foundation Models for Complex Oxide Surface Reconstructions (2026);