The goal of this paper is to make Optimal Experimental Design (OED) computationally feasible for problems involving significant computational expense. We focus exclusively on the Mean Objective Cost of Uncertainty (MOCU), which is a specific methodology for OED, and we propose extensions to MOCU that leverage surrogates and adaptive sampling. We focus on reducing the computational expense associated with evaluating a large set of control policies across a large set of uncertain variables. We propose reducing the computational expense of MOCU by approximating intermediate calculations associated with each parameter/control pair with a surrogate. This surrogate is constructed from sparse sampling and (possibly) refined adaptively through a combination of sensitivity estimation and probabilistic knowledge gained directly from the experimental measurements prescribed from MOCU. We demonstrate our methods on example problems and compare performance relative to surrogate-approximated MOCU with no adaptive sampling and to full MOCU. We find evidence that adaptive sampling does improve performance, but the decision on whether to use surrogate-approximated MOCU versus full MOCU will depend on the relative expense of computation versus experimentation. If computation is more expensive than experimentation, then one should consider using our approach.