We consider the problem of adaptive home heating in the smart grid, assuming that real-time electricity prices are being exposed to end-users with the goal of realizing demand-side management. To lower the burden on the end-users, our goal is the design of a smart thermostat that automatically heats the home, optimally trading o the user’s comfort and cost. This is a challenging problem due to two sources of uncertainty: future weather conditions and future electricity prices. Our main technical contribution is a general technique that uses predictive distributions obtained from Gaussian Process (GP) regressions to compute the state transition probabilities of an MDP, such that the solution to the resulting MDP constitutes a sequentially optimal policy. We apply this general approach to the home-heating problem, where we use the predictive distributions of the GPs for the day-ahead external temperatures and electricity prices. The solution to the home-heating MDP constitutes an optimal heating policy that maximizes the user’s utility given the probability information gathered by the Gaussian process model. Via simulations we show that our MDP-based approach outperforms various benchmarks, especially for cost-sensitive users.