In this paper we present the first decision theoretic planner for the prob- lem of Navigation Among Movable Obstacles (NAMO). While efficient planners for NAMO exist, they suffer in practice from the inherent uncertainties in both per- ception and control on real robots. Generalizing the ideas of these planners to the nondeterministic case has proven difficult, due to the sensitivity of MDP methods to task dimensionality. Our work addresses this challenge by combining ideas from Hierarchical Reinforcement Learning with Monte Carlo Tree Search, and results in an algorithm that can be used for fast online planning in uncertain environments. We evaluate our algorithm in simulation, and provide a theoretical argument for our results which suggest linear time complexity in the number of obstacles for non- degenerate environments.