Sampling of alternatives is often required in discrete choice models to reduce the computational burden and to avoid describing a large number of attributes. This approach has been used in many areas, including modeling of route choice, vehicle ownership, trip destination, residential location, and activity scheduling. The need for sampling of alternatives is accentuated for random regret minimization (RRM) models because, unlike random utility models, the regret function for each alternative depends on all of the alternatives in the choice-set. In this paper we develop and test a method to achieve consistency, asymptotic normality, and relative efficiency of the estimators while sampling alternatives in a class of models that includes RRM. The proposed method can be seen as an extension of the approach used to address sampling of alternatives in multivariate extreme value models. We illustrate the methodology using Monte Carlo experimentation and a case study with real data. Experiments show that the proposed method is practical, performs better than a truncated model, and results in finite-sample estimates that provide a good approximation of those obtained with a model considering all of the alternatives.