Index-equating conjecture for UCB algorithms

Consider a KK-armed bandit model. For arm kk, let Nk,TN_{k,T} be the number of pulls by time TT, let μˉk,T\bar\mu_{k,T} be its empirical mean reward, and let I()I(\cdot) be the index function of a UCB algorithm. In a “reasonable” bandit model and under a “reasonable” UCB algorithm, index-equating conjecture. The pull counts should satisfy

I(μˉ1,T,N1,T,T)I(μˉk,T,Nk,T,T),2kK,I\left(\bar\mu_{1,T},N_{1,T},T\right)\approx I\left(\bar\mu_{k,T},N_{k,T},T\right),\qquad 2\leq k\leq K,

with

k=1KNk,T=T.\sum_{k=1}^{K}N_{k,T}=T.

This conjecture informally extends the equal-index characterization of the associated fluid system to the stochastic bandit process. The paper presents it as a natural conjecture within a perturbation-analysis framework; no resolution is supplied in the provided text.

Sources & referencesView supporting material

Primary source

Yilun Chen and Jiaqi Lu, “A characterization of sample adaptivity in UCB data”, arXiv:2503.04855 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.