Energy-efficient navigation constitutes an important challenge in electric\nvehicles, due to their limited battery capacity. We employ a Bayesian approach\nto model the energy consumption at road segments for efficient navigation. In\norder to learn the model parameters, we develop an online learning framework\nand investigate several exploration strategies such as Thompson Sampling and\nUpper Confidence Bound. We then extend our online learning framework to\nmulti-agent setting, where multiple vehicles adaptively navigate and learn the\nparameters of the energy model. We analyze Thompson Sampling and establish\nrigorous regret bounds on its performance. Finally, we demonstrate the\nperformance of our methods via several real-world experiments on Luxembourg\nSUMO Traffic dataset.\n