The problem that is considered is that of maximizing the energy storage density of Pb-free BaTiO-based dielectrics at low electric fields. It is demonstrated that how varying the size of the combinatorial search space influences the efficiency of material discovery by comparing the performance of two machine learning based approaches where different levels of physical insights are involved. It is started with physics intuition to provide guiding principles to find better performers lying in the crossover region in the composition-temperature phase diagram between the ferroelectric phase and relaxor ferroelectric phase. Such an approach is limiting for multidopant solid solutions and motivates the use of two data-driven machine learning and design strategies with a feedback loop to experiments. Strategy I considers learning and property prediction on all the compounds, and strategy II learns to preselect compounds in the crossover region on which prediction is carried out. By performing only two active learning loops via strategy II, the compound (BaCa)(TiZrHf)O is synthesized with the largest energy storage density ≈73 mJ cm at a field of 20 kV cm, and an insight into the relative performance of the strategies using varying levels of knowledge is provided.