Participant selection is a major research challenge in Mobile Crowdsensing (MCS). Previous approaches commonly assume that adequately long and fixed periods of candidate participants' historical mobility trajectories are available before the selection process. This enables the frameworks to accurately model mobility which enables the optimization of selection. However, this assumption may not be realistic for newly-released MCS applications or platforms because the candidates have just boarded without previous mobility profiles. The sparsity or even absence of mobility traces will incur inaccurate location prediction of the individual participant, thus imposing negative effects on the participant selection process and hindering the practical deployment of new MCS applications. To this end, this paper investigates a novel problem called "From-Scratch MCS" (FS-MCS for short), in which we study how to intelligently select participants to minimize such "cold-start" effect. Specifically, we propose a novel framework based on reinforcement learning, which we name RL-Recruiter. With the gradual accumulation of mobility trajectories over time, RL-Recruiter can make a good sequence of participant selection decisions for each sensing slot by incrementally extracting and utilizing the collective mobility patterns of all candidate participants, thus avoiding the prediction of individual participant's location that is very inaccurate when the training data is sparse. We test our approach experimentally based on two real-world mobility datasets. Our experiment results demonstrate that RL-Recruiter outperforms the baseline approaches under various settings.