Animals must balance a series of costs and benefits while trying to maximize their fitness. For example, an individual may need to choose how much energy to allocate to reproduction versus growth, or how much time to spend on vigilance versus foraging. Their decisions depend on complex interactions between environmental conditions, behavioral plasticity, reproductive biology, and energetic demands. As animals respond to novel environmental conditions caused by climate change, the optimal decisions may shift. Stochastic dynamic programming provides a flexible modeling framework with which to explore these trade-offs, but this method has not yet been used to study possible changes in optimal trade-offs caused by climate change. We created a stochastic dynamic programming model capturing trade-off decisions required by an individual adult female polar bear (Ursus maritimus) as well as the fitness consequences of her decisions. We predicted optimal foraging decisions throughout her lifetime as well as the energetic thresholds below which it is optimal for her to abandon a reproductive attempt. To explore the effects of climate change, we shortened the spring feeding period by up to 3 weeks, which led to predictions of riskier foraging behavior and higher reproductive thresholds. The resulting changes in fitness may be interpreted as a best-case scenario, where bears adapt instantaneously and optimally to new environmental conditions. If the spring feeding period was reduced by 1 week, her expected fitness declined by 15%, and if reduced by 3 weeks, expected fitness declined by 68%. This demonstrates an effective way to explore a species' optimal response to a changing landscape of costs and benefits and highlights the fact that small annual effects can result in large cumulative changes in expected lifetime fitness.