Understanding the stochastic dynamics of sequential decision-making processes: A path-integral analysis of multi-armed bandits
This work addresses the problem of understanding finite-time behaviors in sequential decision-making for researchers in machine learning and optimization, though it appears incremental as it applies existing physics methods to a known bottleneck.
The paper tackled the challenge of analyzing finite-time stochastic dynamics in multi-armed bandits, using statistical physics techniques to characterize the distribution of cumulative regrets and revealing a multimodal regret distribution with large regrets from excess exploitation of sub-optimal arms due to initial unlucky outputs.
The multi-armed bandit (MAB) model is one of the most classical models to study decision-making in an uncertain environment. In this model, a player chooses one of $K$ possible arms of a bandit machine to play at each time step, where the corresponding arm returns a random reward to the player, potentially from a specific unknown distribution. The target of the player is to collect as many rewards as possible during the process. Despite its simplicity, the MAB model offers an excellent playground for studying the trade-off between exploration versus exploitation and designing effective algorithms for sequential decision-making under uncertainty. Although many asymptotically optimal algorithms have been established, the finite-time behaviors of the stochastic dynamics of the MAB model appear much more challenging to analyze, due to the intertwine between the decision-making and the rewards being collected. In this paper, we employ techniques in statistical physics to analyze the MAB model, which facilitates the characterization of the distribution of cumulative regrets at a finite short time, the central quantity of interest in an MAB algorithm, as well as the intricate dynamical behaviors of the model. Our analytical results, in good agreement with simulations, point to the emergence of an interesting multimodal regret distribution, with large regrets resulting from excess exploitation of sub-optimal arms due to an initial unlucky output from the optimal one.