It is well known that context-dependent decisions incur mental costs. While previous research has sought to formalize these costs at various levels of analysis, we still lack basic insight into the nature of mental costs, including the underlying cognitive resources being consumed. Moreover, many computational models assume that mental costs scale linearly with the cognitive resource being used, an assumption of convenience that has yet to be systematically tested. To address these gaps, we build on rate-distortion theory by formalizing an information-theoretic notion of mental costs. Specifically, we define the cost of policies---the mappings from states to actions---as a function of the mutual information between states and actions, the policy complexity. Across four decision-making experiments featuring diverse task manipulations, we find that this mental cost formulation offers a parsimonious description of how humans adaptively adjust their policy complexity across different tasks. Notably, a quadratic mental cost formulation, where increases in policy complexity incur supralinear costs, provides the best fit. These findings highlight the meta-cognitive ability of humans to account for mental costs when forming decision strategies, and pave the way towards a domain-general quantification of mental effort.