Experience is known to facilitate our ability to interpret sequences of events and make predictions about the future by extracting temporal regularities in our environments. Here, we ask whether uncertainty in dynamic environments affects our ability to learn predictive structures. We exposed participants to sequences of symbols determined by first-order Markov models and asked them to indicate which symbol they expected to follow each sequence. We introduced uncertainty in this prediction task by manipulating the: (a) probability of symbol co-occurrence, (b) stimulus presentation rate. Further, we manipulated feedback, as it is known to play a key role in resolving uncertainty. Our results demonstrate that increasing the similarity in the probabilities of symbol co-occurrence impaired performance on the prediction task. In contrast, increasing uncertainty in stimulus presentation rate by introducing temporal jitter resulted in participants adopting a strategy closer to probability maximization than matching and improving in the prediction tasks. Next, we show that feedback plays a key role in learning predictive statistics. Trial-by-trial feedback yielded stronger improvement than block feedback or no feedback; that is, participants adopted a strategy closer to probability maximization and showed stronger improvement when trained with trial-by-trial feedback. Further, correlating individual strategy with learning performance showed better performance in structure learning for observers who adopted a strategy closer to maximization. Our results indicate that executive cognitive functions (i.e., selective attention) may account for this individual variability in strategy and structure learning ability. Taken together, our results provide evidence for flexible structure learning; individuals adapt their decision strategy closer to probability maximization, reducing uncertainty in temporal sequences and improving their ability to learn predictive statistics in variable environments.