On-demand deployment of small cells plays a key role in augmenting macro-cell coverage for outdoor hotspots, where user devices are brought together and intensively upload self-generated data. In this paper, we study spectrum sharing among rapidly deployable small cells in the uplink, even without a priori global knowledge. We propose a hybrid multi-agent approach, which allows a leading macro-cell base station (MBS) and multiple following small base stations (SBSs) to take part in a user-centric, online joint optimization of small cell deployment and uplink resource allocation. Specifically, we propose a centralized mechanism for the MBS to solve the first subproblem of small cell deployment stage by stage, based on an adversarial bandit model. Furthermore, we propose a distributed mechanism for the group of SBSs to collectively solve the second subproblem of uplink resource allocation stage by stage, based on a stochastic game model. We prove that our approach is guaranteed to produce a joint strategy, which is built upon a mixed strategy with bounded regret on the first tier and an equilibrium solution on the second tier. Our approach is validated by simulations on the aspects of convergence behavior, strategy correctness, power consumption, and spectral efficiency.