It has been shown that the right set of polyhedral optimizations can make a significant difference in the running time of a program. However, the number of alternatives for a program transformed with polyhedral optimizations can be enormous. Thus, it is often impossible to iterate over a significant fraction of the entire space of polyhedral transformed variants. Recent research has focused on iterating over this search space with manually-constructed heuristics or with expensive search algorithms (e.g., genetic algorithms) that can eventually find good points in the polyhedral space. In this paper, we evaluate methods of modeling the polyhedral optimization problem using machine learning techniques. We show that these techniques can quickly find excellent program variants in the polyhedral space. We introduce two different modeling techniques, we call a "one-shot" model and a "reactive" model. Our one-shot model takes as input "one" characterization of the program and outputs several different variants that are predicted to give good performance. In contrast, our "reactive" model takes as input the characterization of the program that was last predicted to give good performance. Unlike the one-shot model, our reactive model explores the space of polyhedral program variants obtaining characterizations of each program variants and using these characterizations for the model to decide where to traverse the search space next. We show that our reactive predictor outperforms our one-shot model and can significantly outperform the most aggressive setting of state-of-the-art model-based heuristics in a just a few iterations.