Conjectured universally tight lower bound for personalized federated bandits

Let $M$ clients play a multi-armed bandit for $T$ time slots. For client $m$, let $k'_{*,m}$ denote its optimal arm, let $X'_{k,m}$ denote the reward distribution of arm $k$ for client $m$, and let $T_{k,m}$ be the expected number of pulls of arm $k$ by client $m$. Write $[M]=\{1,\ldots,M\}$, and define

$$\beta=\alpha+\frac{1-\alpha}{M},\qquad \gamma=\frac{1-\alpha}{M},\qquad \eta=\left(\beta^2+(M-1)\gamma^2\right)^{\frac{1}{2}}.$$

For distributions $P,Q$, let $\mathrm{kl}(P,Q)$ denote their Kullback–Leibler divergence. Conjectured lower-bound constraint. For any consistent algorithm $\Pi$, as $T\to\infty$, for every $m\in[M]$ and every arm $k\neq k'_{*,m}$,

$$\frac{\beta^2}{T_{k,m}}+\sum_{n: n\neq m,\, k'_{*,n}\neq k}\frac{\gamma^2}{T_{k,n}}\leq \frac{\eta^2\mathrm{kl}(X'_{k,m},X'_{k'_{*,m},m})}{\log(T)}.$$

This conjecture is proposed as the missing universally tight lower-bound characterization for all values of $\alpha$ in personalized federated multi-armed bandits. The preceding lower-bound results establish related constraints but do not determine the precise dependence on $\alpha$; characterizing that dependence remains open.