Humans and other animals can generalise from local to global relationships in a transitive manner. Recent research has shown that asymmetrically biased learning, where beliefs about only the winners (or losers) of local comparisons are updated, is well-suited for inferring relational structures from sparse feedback. However, less is known about how belief-updating biases intersect with humans' capacity to adapt to changes in relational structure, where re-valuing an item may have downstream implications for inferential knowledge pertaining to unchanged items. We designed a transitive inference paradigm involving one of two possible changepoints for which an asymmetric (winner- or loser-biased) learning rule was more or less optimal. Participants (N = 83) exhibited differential sensitivity to changes in relational structure: whereas participants readily learned that a hitherto low-ranking item increased its rank ('up' condition), moving a high-ranking item down the hierarchy impaired downstream inferential knowledge ('down' condition). Behaviour was best captured by a reinforcement learning model which exhibited an initially winner-biased learning strategy that was nonetheless adaptable - that is, while this winner bias predominantly limited participants' flexibility in the 'down' condition, well-performing participants were able to reduce or even reverse their winner bias in order to appropriately accommodate the relational change. Our results indicate that asymmetric learning not only accounts for efficient inference of latent relational structures but also for differences in the ease with which learners accommodate structural changes.