Small UAS typically fly at low altitudes where the atmospheric environment is complex and uncertain. Typical error in even the best modern weather forecasting systems introduces significant uncertainty into the optimal flight path for a UAS to complete a mission and the energy required. Existing approaches to managing this uncertainty involve creating flight plans whose cost is robust to uncertainty or assimilating aircraft observations into a weather model to eliminate forecast error. Robust approaches cannot respond to the real atmospheric environment and data assimilation requires a high bandwidth data link and significant computational resources be dedicated to the aircraft. This paper proposes a multi-armed bandit inspired approach to altitude optimization. By taking advantage of the spectral characteristics of atmospheric motion this approach enables an aircraft to seek low-cost altitudes while maintaining a model of the atmosphere using in situ sensing and computational resources. In simulation the approach demonstrates performance superior to a collocation based optimal control technique, identifying low cost regions and rejecting poor information provided to the planner by a forecast.