Many current recommender system techniques reinforce established tastes, leaving little room for venturing into unfamiliar music. A key challenge is our uncertainty about user preferences for previously unconsumed content, making it safer to build upon known preferences. To address this, we propose an incremental, feedback-driven method that gradually introduces users to new genres. By dynamically balancing recommendations between verified preferences and content with uncertain appeal, our approach maintains engagement while progressively expanding musical horizons. Adopting a Bayesian active learning approach, we update belief states iteratively as users provide feedback on new items. In a user study with data from a commercial music video platform, participants gradually discovered a previously unfamiliar music genre of their choosing. Comparing our method to both immediate genre introduction and passive small-step strategies without real-time adaptation, we observed significant improvements. Participants showed higher engagement with new music, stronger affinity for unfamiliar genres, and a greater sense of control, demonstrating the effectiveness of our iterative, feedback-informed strategy for broadening musical tastes. Supplementary code is available here.