Active automata learning enables model-based testing and verification of black-box systems by automatically constructing models from observations via interactions with the system. As interactions are usually expensive, active algorithms attempt to perform as few interactions as possible to learn a given system. However, many such algorithms struggle when confronted with noise, such as message loss, when learning otherwise deterministic systems. We investigate and adapt different algorithms to learn deterministic automata in a noisy setting. One of these is a novel active algorithm based on our previous passive Partial Max-SAT algorithm. In our analysis, we demonstrate techniques to lower the required number of interactions and order the evaluated algorithms accordingly. Finally, we show that the necessary interactions can be further reduced when leaving the classical active learning framework.