High-entropy alloys are emerging as highly efficient thermoelectrics, but their vast compositional spaces hinder efficient material discovery using conventional heuristics-based and advanced machine learning approaches. Here, this fundamental challenge is addressed by demonstrating an active learning framework that leverages sparse experimental data (80 out of 16206) to efficiently identify three new high-entropy chalcogenides (HECs) with remarkable thermoelectric performance (zT >2). By integrating physics-informed descriptors with uncertainty-aware sampling, this model efficiently assimilates latent structure-property relationships. This allows for systematic exclusion of unfavorable chemistries, enabling even non-experts in thermoelectrics to design unexplored systems with arbitrary components. Furthermore, novel atomic arrangements and distinctive electron and phonon transport properties are uncovered, which are responsible for the superior performance in HECs, advancing the understanding of physical phenomena in disorder-rich systems.