Reducing the material cost of inorganic solid-state electrolytes is crucial to advancing all-solid-state batteries (ASSBs) for next-generation energy storage applications. The halospinel Li2Sc2/3Cl4 solid electrolyte (SE) possesses a high ionic conductivity of 1.5 mS cm-1 and good cycling stability up to 4.6 V. However, the high cost of Sc limits its practical application. In this study, we combine M3GNET universal machine learning interatomic potential (UMLIP) and density functional theory (DFT) for efficient screening of lower-cost cation-substituted halospinel compositions for synthesis. As a cost-mitigation strategy, predicted Mg2+-, Al3+-, and Zr4+-substituted Li2Sc2/3Cl4 spinels with substitution fractions ranging from 20.9% to 37.5% were experimentally synthesized with only minor impurities, achieving room-temperature ionic conductivities as high as 1.85 mS cm-1. Substitution of Fe3+ was also achieved, albeit with a 7% Fe2+ impurity. Molecular dynamics simulations (MD) using highly accurate moment tensor potentials (MTPs) indicate that Li+/Sc3+/Mn+ ordering plays a crucial role in determining the conductivity of disordered substituted compositions. ASSBs operating at 3.8 mAh cm-2 capacity with Li1.75Sc0.416Zr0.25Cl4 at a high current density of 2 mA cm-2 exhibited 80% of the capacity of more moderately loaded ASSBs cycled at a low rate. This work provides a foundational methodology for predicting the thermodynamic stability and ion transport of disordered lithium solid electrolytes and accelerating the discovery of novel materials for a range of applications.