Credible property exploration or prediction can not be achieved without well-established compositions and structures of catalysts under working conditions. We construct surrogate models via combination of machine learning (ML), genetic algorithm (GA) and ab initio thermodynamics (AITD) to accelerate global optimization of PtSn binary metal oxides, which are typically used for CO2-assisted propane dehydrogenation to propylene. This challenging case illustrates that the subtle oxidized states of PtSnO clusters can be predicted in a large chemical space including a wide range of reaction conditions. The oxidation patterns, phase diagrams and atomic charge distributions of the PtSnO clusters have been discussed. The Sn decorating mechanism to Pt in PtSnO has been explained. These results also indicate that the oxidation of PtSn clusters is more feasible under working conditions, and that previous understanding obtained only with a fully reduced PtSn alloy may be incomplete.