<p>Continuously changing environments have a paramount role in the evolution of cooperative behavior. Previous works have shown that the transitions among different games, as the feedback between behaviors and environments, can promote cooperative behavior significantly. Quantitative analysis, however, is limited to homogeneous populations, while realistic populations in nature are often more complex and highly heterogeneous. We hereby provide an analytical treatment of when the evolution of cooperation can be supported in stochastic games, applying to arbitrary spatial heterogeneity and payoff structure. We highlight that the rule and frequency of game changes can have surprisingly diverse effects on evolutionary outcomes, depending on the governing social dilemmas. While stochastic games favor the evolution of cooperation in donation games, this is not the case for public goods games and snowdrift games. Hence, our framework and model results offer a more subtle insight into the long-standing enigma.</p>