Prior evidence suggests that increasingly efficient task performance in human learning is associated with large scale brain network dynamics. However, the specific nature of this general relationship has remained unclear. Here, we characterize performance improvement during feedback-driven stimulus-response (S-R) learning by learning rate as well as S-R habit strength and test whether and how these two behavioral measures are associated with a functional brain state transition from a more integrated to a more segregated brain state across learning. Capitalizing on two separate fMRI studies using similar but not identical experimental designs, we demonstrate for both studies that a higher learning rate is associated with a more rapid brain network segregation. By contrast, S-R habit strength is not reliably related to changes in brain network segregation. Overall, our current study results highlight the utility of dynamic functional brain state analysis. From a broader perspective taking into account previous study results, our findings align with a framework that conceptualizes brain network segregation as a general feature of processing efficiency not only in feedback-driven learning as in the present study but also in other types of learning and in other task domains.