Teaching people clever heuristics is a promising approach to improve decision-making under uncertainty. The theory of resource-rationality makes it possible to leverage machine learning to discover optimal heuristics automatically. One bottleneck of this approach is that the resulting decision strategies are only as good as the model of the decision-problem that the machine learning methods were applied to. This is problematic because even domain experts cannot give complete and fully accurate descriptions of the decisions they face. To address this problem we develop strategy discovery methods that are robust to model misspecification. The basic idea is to derive the strategy that will perform best in expectation across all possible real-world problems that could have given rise to the likely erroneous description that a domain expert provided. To achieve this, our method uses a probabilistic model of model-misspecification to perform Bayesian inference on what the real-world problem might be like. We applied our Bayesian approach to robust strategy discovery in two domains - planning and risky choice. In both applications we find that our approach leads to more robust strategies and that teaching those strategies to people significantly improves their performance in scenarios where approaches ignoring the risk of model-misspecification are ineffective or even harmful. The methods developed in this article are an important step towards leveraging machine learning to improve human decision-making in the real world because they tackle the problem that the real world is fundamentally uncertain.