In this paper we perform application-level energy minimization through the control of the CPU power states during the program execution. To attain this goal we model the program and the underlying architecture with Markov Decision Process (MDP) models. The MDP model augments the program CFG with probabilities of how likely is to take the conditional branches and costs expressing how long and how much energy it takes to execute the various regions of code. We learn the models through program proﬁling, obtain ofﬂine an optimal solution, apply the solution to the existing program and then run the program to validate that the theoretical results are met. Using this method we are able to minimize the average total energy of the program, while keeping the average execution time below a given threshold. In certain cases we are also able to obtain better program Energy Delay Product (EDP) when following the standard optimal MDP policy than with other standard assignments of CPU power states. For example, the program EDP of the optimal solution can be 30% less than the EDP for the maximum performance power state. We also develop some new algorithms to tackle the problem of non-negligible CPU transition latencies with MDP optimization. This is but an instance of quantitative analysis and optimization. We can apply this method as well for the analysis and control of the Quality of Results (QoR) or the memory used by the software.