Many studies of Action-Outcome Learning have demonstrated that reinforcement delays exert a detrimental influence on learning performance. Different theoretical perspectives offer varying explanations for this effect. A rational perspective suggests that as long as action-outcome pairings can be clearly recognized, delays should not interfere with the inductive process. Here we tested this idea by manipulating whether action-outcome contingencies were clearly identifiable as such by providing structural information in real time. In the absence of such information, we replicated the familiar detrimental effects of delay. Providing structural markers, and thus allowing easy identification of action-outcome pairings, eradicated this effect. Importantly, two additional experiments indicate that these results cannot be attributed to alternative explanations involving outcome salience or better awareness of timing. We conclude that when the environment allows Action-Outcome Learning to be conceptualized as a contingency learning task, learners are capable of covariation computation and immune to variations of response-outcome timing.