In this paper we present the Markov chain Hyper-heuristic (MCHH), a novel online selective hyper-heuristic which employs reinforcement learning and Markov chains to provide an adaptive heuristic selection method. Experiments are conducted to demonstrate the efficacy of the method and comparisons are made with standard heuristics, a random hyper-heuristic and a multi-objective hyper-heuristic from the literature. The approaches are compared on a small number of evaluations of the multi-objective DTLZ test problems to reflect the computational limitations of expensive optimisation problems. The results demonstrate the MCHH robust and reliable performance on these problems.