In several online marketplaces, the qualities of value-providing supply units (e.g., sellers, workers, service providers) are unknown when they join the platform. Ensuring efficient matchmaking in such markets may require identifying the higher-quality supply units, which requires a certain amount of exploration, i.e., matching with new supply units with uncertain qualities despite the availability of known high-quality supply. In the absence of centralized incentives that subsidize such myopically suboptimal matching choices, a natural question is whether competitive forces in the market may generate adequate incentives for such exploratory behavior amongst customers. The intuition is that established high-quality supply units may naturally demand higher equilibrium prices due to congestion compared to novices, effectively incentivizing customers to participate in exploration. This paper aims to understand the extent to which such intuition is well-founded.

In several applications of the stochastic multi-armed bandit problem, the traditional objective of maximizing the expected sum of rewards obtained can be inappropriate. Motivated by the problem of optimizing job assignments to train novice workers of unknown quality in labor platforms, we consider a new objective in the classical setup. Instead of maximizing the expected total reward from $T$ pulls, we consider the vector of cumulative rewards earned from the $K$ arms at the end of $T$ pulls, and aim to maximize the expected value of the highest cumulative reward across the $K$ arms. This corresponds to the objective of training a single, highly skilled worker using a limited supply of training jobs. For this new objective, we show that any policy must incur an instance-dependent asymptotic regret of $\Omega(\log T)$ (with a higher instance-dependent constant compared to the traditional objective) and an instance-independent regret of $\Omega(K^{1/3}T^{2/3})$. We then design an explore-then-commit policy, featuring exploration based on appropriately tuned confidence bounds on the mean reward and an adaptive stopping criterion, which adapts to the problem difficulty and achieves these bounds (up to logarithmic factors). Our numerical experiments demonstrate the efficacy of this policy compared to several natural alternatives in practical parameter regimes.