Sequential Decision Making Under Uncertainty: Optimality Guarantees, Compositional Learning, And Applications To Robotics And Ecology