Li-S batteries are a promising alternative to Li-ion batteries, offering large energy storage capacity and wide operating temperature range. However, their performance is heavily affected by the Li-polysulfide (LiPS) shuttling. Computational screening of LiPS adsorption on single-atom catalyst (SAC) substrates is of great aid to the design of Li-S batteries which are robust against the LiPS shuttling from the cathode to the anode and the electrolyte. To facilitate this process, we develop a machine learning (ML) protocol to accelerate the systematic mapping of dominant local energy minima found with calculations based on the density functional theory (DFT), and, in turn, fast screening of LiPS adsorption properties on SACs. We first validate the approach by probing the potential energy surface for LiPS adsorbed on graphene decorated with a Fe-N-4-C SAC. We identify minima whose binding energies are better or on par with the one previously reported in the literature. We then move to analyze the adsorption trends on Zn-N-4-C SAC and observe similar adsorption strength and behavior with the Fe-N-4-C SAC, highlighting the good predictive power of our protocol. Our approach offers a comprehensive and computationally efficient alternative to conventional approaches studying LiPS adsorption.