The design of alloys for use in gas turbine engine blades is a complex task that involves balancing multiple objectives and constraints. Candidate alloys must be ductile at room temperature and retain their yield strength at high temperatures, as well as possess low density, high thermal conductivity, narrow solidification range, high solidus temperature, and a small linear thermal expansion coefficient. Traditional methods are not sufficient for exploring combinatorially-vast alloy design spaces, optimizing for multiple objectives, nor ensuring that multiple constraints are met. In this work, an approach for solving a constrained multi-objective materials design problem over a large composition space is proposed, specifically focusing on the Mo-Nb-Ti-V-W system as a representative Multi-Principal Element Alloy (MPEA) for potential use in next generation gas turbine blades. This approach is able tolearn and adapt to unknown constraints in the design space, making decisions about the best course of action at each stage of the process. As a result, 21 Pareto-optimal alloys were identified that satisfy all constraints. This proposed framework is significantly more efficient and faster than a brute force approach.