Balancing Public Cycle Sharing Schemes Using Independent Learners
Jeremiah Smith, Luke Dickens, Krysia B. Broda · 2012
This paper concerns the resource management problem arising in public cycle sharing schemes, when some docking stations become empty and remain so while others fill to capacity. To alleviate this, managing companies move bicycles between docking stations in order to maximise the number of satisfied customers while minimising the movement cost. We identify Reinforcement learning (RL) as the most promising technique for finding good movement strategies in these networks, but conventional function-approximation RL methods do not scale well here, due to the quadratic growth in number of actions with network size. We propose the use of cooperating agents, namely Independent Learners, to partition the action space. To overcome the well known issue of coordination in Independent Learners, we combine a novel scheduling approach for asynchronous learning, with a modified Gradient-descent Sarsa(λ) algorithm to manage variable step-sizes. Our method competes with, and scales more favourably than, single-agent RL on a selection of simulated networks.