Shared mobility-on-demand systems have very promising prospects in making urban transportation efficient and affordable. However, due to operational challenges among others, many mobility applications still remain niche products. This paper addresses rebalancing needs that are critical for effective fleet management in order to offset the inevitable imbalance of vehicle supply and travel demand. Specifically, we propose a reinforcement learning approach which adopts a deep Q network and adaptively moves idle vehicles to regain balance. This innovative model-free approach takes a very different perspective from the state-of-the-art network-based methods and is able to cope with large-scale shared systems in real time with partial or full data availability. We apply this approach to an agent based simulator and test it on a London case study. Results show that, the proposed method outperforms the local anticipatory method by reducing the fleet size by 14% while inducing little extra vehicle distance traveled. The performance is close to the optimal solution yet the computational speed is 2.5 times faster. Collectively, the paper concludes that the proposed rebalancing approach is effective under various demand scenarios and will benefit both travelers and operators if implemented in a shared mobility-on-demand system.