Recently, regret-based choice models have been introduced in the travel behavior research community as an alternative to expected/random utility models. The fundamental proposition of regret theory is that individuals minimize the amount of regret they (are expected to) experience when choosing among choice alternatives. In this context, regret is defined as a function of attribute differences between the considered choice alternative and one or more foregone choice alternatives in an individual’s choice set. This definition of regret as a function of physical attributes of the choice alternatives implies that current regret-based choice models do not account for the perception of attributes, which is likely related to their magnitude. Therefore, in this paper, we propose and empirically test such an elaboration of the basic regret-minimization models. The current paper sets out to formulate random regret minimization models that incorporate a non-linear representation of the perception of attribute levels. Inspired by long-standing research on psycho-physical measurement, it is assumed that the perception of stimuli (attributes) is proportional to their magnitude. To allow for slight deviations from this representation, a more general non-linear psycho-physical representation of the relationship between attribute levels and their perception is also tested. The suggested models are tested using two data sets, one data set concerned the stated choice of shopping centre, the other concerned revealed preference of mode choice. The two newly formulated regret models are compared against each other and against their original random regret minimization base specifications. In addition to comparing the predictive performance of these model specifications, validation tests are conducted. In each case study, the newly suggested regret models, incorporating a non-linear representation of perception, achieve significant improvements in goodness-of-fit over the original regret formulations. The results of the K-fold validation tests provide further support to this finding.