A shift toward shopping at (autonomous) wheeled vending stores is redefining urban retail. Compared with traditional brick-and-mortar stores, such mobile stores are cost-efficient to deploy and adaptive to fast-evolving business environments. However, mobile stores are confronted with unknown demand and limited capacity. Store mobility enables demand learning and profit maximization, yet an optimal dynamic store location policy remains unclear. We model this “learning-and-earning” problem by taking optimistic actions under parameter uncertainty. The joint optimization over parameter and action set is complicated by the combinatorial nature and infinite choices within the action set. We overcome these challenges by leveraging continuous approximation methods, and then propose a continuous-approximation optimistic (CA-O) learning framework under some special problem structures. Nevertheless, for more general scenarios, the problem remains intricate due to the nonconvexity in unknown parameters. We alternatively propose a CA-O faster learning algorithm by utilizing first-order approximation techniques and further proving a closed-form gradient to guarantee computational efficiency. We theoretically analyze and numerically validate the regret for the proposed algorithms. In a Toronto case study, our algorithm significantly outperforms baselines. Mobile stores earn higher profits than brick-and-mortar stores through demand learning and store mobility. More broadly, this paper envisions the future landscape of urban retail enhanced by omnipresent mobile facilities.