Thompson sampling: Precise arm-pull dynamics and adaptive inference

2026-01-29 · Qiyang Han arxiv

Adaptive sampling schemes are well known to create complex dependence that may invalidate conventional inference methods. A recent line of work shows that this need not be the case for UCB-type algorithms in multi-armed bandits. A central emerging theme is a stability' property with asymptotically deterministic arm-pull counts in these algorithms, making inference as easy as in the i.i.d. setting. In this paper, we study the precise arm-pull dynamics in another canonical class of Thompson-sampling type algorithms. We show that the phenomenology is qualitatively different: the arm-pull count is asymptotically deterministic if and only if the arm is suboptimal or is the unique optimal arm; otherwise it converges in distribution to the unique invariant law of an SDE. This dichotomy uncovers a unifying principle behind many existing (in)stability results: an arm is stable if and only if its interaction with statistical noise is asymptotically negligible. As an application, we show that normalized arm means obey the same dichotomy, with Gaussian limits for stable arms and a semi-universal, non-Gaussian limit for unstable arms. This not only enables the construction of confidence intervals for the unknown mean rewards despite non-normality, but also reveals the potential of developing tractable inference procedures beyond the stable regime. The proofs rely on two new approaches. For suboptimal arms, we develop an inverse process' approach that characterizes the inverse of the arm-pull count process via a Stieltjes integral. For optimal arms, we adopt a reparametrization of the arm-pull and noise processes that reduces the singularity in the natural SDE to proving the uniqueness of the invariant law of another SDE. We prove the latter by a set of analytic tools, including the parabolic Hörmander condition and the Stroock-Varadhan support theorem.

📄 PDF Abstract BibTeX arXiv:2601.21131

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-Armed Bandits

Optimism Stabilizes Thompson Sampling for Adaptive Inference

2026-02-05 · Shunxing Yan, Han Zhong arxiv

Thompson sampling (TS) is widely used for stochastic multi-armed bandits, yet its inferential properties under adaptive data collection are subtle. Classical asymptotic theory for sample means can fail because arm-specif…

Multi-Armed Bandits

Efficient and Adaptive Posterior Sampling Algorithms for Bandits

2024-05-02 · Bingshan Hu, Zhiming Huang, Tianyue H. Zhang, Mathias Lécuyer 외

We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when…

Thompson Sampling

Batched Thompson Sampling for Multi-Armed Bandits

2021-08-15 · Nikolai Karpov, Qin Zhang

We study Thompson Sampling algorithms for stochastic multi-armed bandits in the batched setting, in which we want to minimize the regret over a sequence of arm pulls using a small number of policy changes (or, batches). …

Multi-Armed Bandits Thompson Sampling

BOTS: Batch Bayesian Optimization of Extended Thompson Sampling for Severely Episode-Limited RL Settings

2024-11-30 · Karine Karine, Susan A. Murphy, Benjamin M. Marlin

In settings where the application of reinforcement learning (RL) requires running real-world trials, including the optimization of adaptive health interventions, the number of episodes available for learning can be sever…

Bayesian Optimization Policy Gradient Methods Reinforcement Learning (RL)Thompson Sampling

Thompson Sampling for Budgeted Multi-armed Bandits

2015-05-01 · Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu 외

Thompson sampling is one of the earliest randomized algorithms for multi-armed bandits (MAB). In this paper, we extend the Thompson sampling to Budgeted MAB, where there is random cost for pulling an arm and the total co…