How do humans get better at planning? Previous work postulated that the improvement of cognitive strategies occurs through feedback-based metacognitive reinforcement learning (MCRL). However, it is not clear whether and, if so, how people can learn planning strategies without reinforcement. To answer these questions, we experimentally investigated the effect of frequency of feedback on people's ability to learn adaptive planning strategies. We found that participants receiving feedback only 25\% of the time nonetheless learned about as well as participants receiving constant feedback. Quantitative modelling of the data revealed that state-of-the-art MCRL models cannot explain this finding. However, extending these models by a mechanism generating an additional learning signal through self-evaluation of plan quality can account for people's ability to learn planning strategies without feedback. The findings of this research have implications for the design of learning environments and enabling people and machines to self-sufficiently improve their strategies in naturalistic settings.