Mobile robots often need to learn an initially uknown map of a position-dependent parameter from sampled values. Examples include learning radio transmission rates, the density of litter at each point, forest density, etc. Moreover, learning this map is often only one part of the robot's task -- the robot may also have a navigation objective, low energy consumption goals, etc. In this project, we aim to design and study a robot motion control strategy that optimally takes into account both map learning and the other objectives of the robot.