Precise Asymptotics and Refined Regret of Variance-Aware UCB

Thank you for your interest in our work and for reviewing our manuscript! We greatly appreciate your feedback and address your comment below.

Question: Modifying current analysis to the $\log t$ variant

Thank you for raising this insightful question!

(1) In [4], UCB-V is presented in the general form

$

     \mathrm{UCB}(a,t) = \bar{X}\_{a,t} +  \widehat \sigma\_{a,t} \cdot \sqrt{\frac{\mathcal{E}\_t}{n\_{a,t}}}
+\frac{\mathcal{E}\_t}{n\_{a,t}},

$

where $\mathcal{E}_t$ is any non-decreasing function of $t$. Setting $\mathcal{E}_t = \log t$ recovers the ``$\log t$'' variant you mentioned.

(2) We believe extending our current analysis to the ``$\log t$'' variant is not straightforward. Technically, it requires at least two major changes:

• An improved Bernstein‑type non‑asymptotic LIL result.

In our Lemma 8, the Bernstein-type non-asymptotic LIL is stated as: with probability at least $1-\delta$,

$

    \big| \bar{X}_t\big| \lesssim \sigma\sqrt{\frac{\log\frac{\log(T/\delta)}{\delta}}{t}} + \frac{\log(1/\delta)}{t},  \forall 1 \leq t \leq T.

$

To handle the ``$\log t$'' variant, we may need to replace the fixed threshold $\log\frac{\log(T/\delta)}{\delta}$ by a time-varying $\log\frac{\log(t/\delta)}{\delta}$ inside the square root, i.e.,

$

    \big| \bar{X}_t\big| \lesssim \sigma\sqrt{\frac{\log\frac{\log(t/\delta)}{\delta}}{t}} + \frac{\log(1/\delta)}{t},  \forall 1 \leq t \leq T.

$

Although obtaining such an improvement might require a more refined martingale-based analysis, we are hopeful that a stronger bound could be achievable.

• A revised UCB‑V analysis framework.

Even with the refined LIL concentration inequality we mentioned in point 1, under the ``$\log t$'' variant our current analysis framework breaks down. Concretely, one obtains

$

    1 + \mathfrak{o}\_{\mathbf{P}}(1) \geq \frac{\Delta_a / \log T_a+ \varphi\_{1,T} }{ \varphi_{a,T}} ,\quad \frac{\Delta_a / \log T_1+ \varphi\_{1,T} }{ \varphi\_{a,T}} \geq 1 -\mathfrak{o}\_{\mathbf{P}}(1),

$

where $\log T_1$ and $\log T_a$ now differ because of the time-varying bonus. Such mismatch prevents us from collapsing to a single fixed point equation.

A similar limitation appears in the non-variance UCB analysis in [23], which also studies the ``$\log T$'' version of the UCB algorithm, and this may be a fundamental gap in using such a framework to conduct analysis. It is worth noting that [21] has successfully analyzed the behaviour of non-variance UCB in the ``$\log t$'' variant, but with a different, dedicated analysis and with results in a less complete characterization (as discussed below Theorem 3.1 of [23]). We tend to believe that this subtle limitation of the framework used by [23] and our work is a fundamental price paid for providing more complete characterization and simplifying the analysis of [21]. Given the less conservative nature and strong empirical performance of this ``$\log t$'' variant algorithm, exploring it further could be a worthwhile avenue for future work.

Thanks for your interest in our work and for reviewing our manuscript. We greatly appreciate your feedback and address your comment below.

1. Writing suggestions

Thank you for these valuable suggestions! We apologize for the roughness of some discussion sections and for omitting a conclusion due to page limitations. In the revised version, we will:

i) Expand the introduction to state our UCB‑V asymptotics explicitly and include a compact table summarizing our stability results and regret rates across different regimes.

ii) Add a new section that consolidates all simulation results, detailing each experimental setup and explaining how each experiment aligns with our theoretical findings.

iii) In Section 2’s Additional Notation paragraph, explicitly define the stability function
$\varphi\_{a,t} = \frac{\bar{\sigma}\_a \vee n_{a,t}^{-1/2}}{\sqrt{n_{a,t}}},$ and clarify that these two components correspond to the two error terms in Bernstein's inequality—so that the UCB‑V bonus for arm $a$ at time $t$ is taken as the larger of the variance‑based and boundedness‑based corrections.

iv) Add a Concluding section that summarizes our main contributions, acknowledges limitations, and outlines directions for future work.

2. Limitations in $K$ armed setting.

We agree that our stability condition (14) may not be optimal for $K>2$, and that a full phase‑transition characterization is still lacking. The main technical challenge in extending our theory to the $K>2$ case lies in the increased number of parameters and their complex interactions. We therefore leave a tighter analysis of the $K>2$ case as an important direction for future work.

3. Instability example beyond zero‑variance instances

We chose $\sigma_1 = 0$ solely for simplicity of exposition. In fact, the instability analysis in Proposition 2 extends directly to settings where the optimal arm’s variance satisfies $\sigma_1 = \mathcal{O}(1 /\sqrt{T})$, since the UCB‑V bonus term for the optimal arm is the same as in the $\sigma_1 = 0$ case. We will generalize Proposition 2 accordingly in the revised manuscript.

On the other hand, we would like to note that constructing an instance with $\sigma_1 = T^{-\alpha}$ for some $\alpha \in (0,1/2)$ is more challenging and requires some new ideas, as the asymptotic equation from Example 2 no longer applies. We will acknowledge such limitation in the revised version.

Thank you for your interest in our work and for reviewing our manuscript! We greatly appreciate your feedback and address your comments below.

Question 1: $\Delta \asymp 1/\sqrt{T}$ setting of interest

We agree with the reviewer that $\Delta = \Theta(1/\sqrt{T})$ represents a delicate “edge case” in practical applications. However, this regime plays a crucial conceptual and methodological role: by parameterizing $\Delta \asymp \frac{\theta}{\sqrt{T}}$ and letting $\theta\to0$ or $\theta\to+\infty$, one interpolates smoothly between the small-gap and large-gap regimes. In addition to this interpolation perspective, we borrow examples and explanations from [21] to illustrate how small-gap phenomena arise in practice:

• A/B testing and clinical trials.
  With large sample budgets $T$, the minimum detectable effect at fixed significance and power satisfies $T \propto \Delta^{-2} \Longrightarrow \Delta = \mathcal{O}\bigl(1/\sqrt{T}\bigr).$ Hence, web experiments and vaccine dosage trials naturally operate in this small-gap regime.

• Online allocation of homogeneous tasks.
  Many platforms (ride‑hailing, crowdsourcing) route statistically indistinguishable tasks to agents, requiring fairness on each sample path. Here, true performance differences shrink to $\mathcal{O}(1/\sqrt{T})$, so early random fluctuations can lead to stark imbalances in task allocation.

Under such small‑gap regime, prior works [21, 23] showed that UCB algorithms can maintain low regret and balanced allocations. By contrast, our analysis reveals that incorporating variance estimates yields lower regret but the allocation depends on variances and may not be balanced. Such trade-off highlights a fundamental tension between efficiency and fairness: variance‑aware policies achieve better performance by pulling high-variance arms more often, yet this comes at the cost of an unbalanced allocation, which may be undesirable in applications.

Question 2: Notational confusions

Thank you for your careful reading! We have corrected the noted notational issues in the revised version:

1. In line 85, we will update the inequality to

$$\mathbb{P}\bigl(n_{1,T} \lesssim \sqrt{T}\log T\bigr) \wedge \mathbb{P}\bigl(n_{2,T} \gtrsim T/(\sigma_2\sqrt{\log T})\bigr) \gtrsim 1.$$

Moreover, in the Notation section we will add: we write $a \gtrsim b$ (resp. $a \lesssim b$) to mean $a \geq C b$ (resp. $a \leq Cb$) for some absolute constant $C > 0$.

2. We will replace the perturbation symbol $\delta$ in line 166 with $\zeta$ to avoid confusion.

Thank you for your interest in our work and for reviewing our manuscript. We greatly appreciate your feedback and address your comments below.

Question: Extension to the $K$‑armed setting

As mentioned in our last section and Appendix B, we can derive analogous results in the $K$‑armed setting—including the asymptotic equation (15), the sufficient condition for stability (14), and the improved regret bound in Theorem 5—which all reduce to the two‑armed results presented in the main text. We would like to discuss several additional points and calculations:

1. Asymptotic arm‑pulling characterization. To provide some intuition for (15), we can generalize Example 1 from the two‑armed setting: assume all variances $\sigma_a=\Omega(1)$ and the gaps $\Delta_a$ are proportional to $\theta_a\sqrt{\log(T)/T}$—the “moderate‑gap regime” of [21]. In this regime, condition (14) always holds, and (15) simplifies to

$$\sum_{a=1}^K \frac{\sigma_a^2}{T\bigl(\sigma_1/\sqrt{n_{1}^\star} + \theta_a/\sqrt{T}\bigr)^2} = 1, \qquad n_a^\star = \frac{\sigma_a^2}{T\bigl(\sigma_1/\sqrt{n_{1}^\star} + \theta_a/\sqrt{T}\bigr)^2}.$$

As $\theta_a\to0$, arm‑$a$’s normalized pulling rate ($n_a^\star/T$) converges to

$$\frac{\sigma_a^2}{\sum_{j=1}^K \sigma_j^2}.$$

That is, when the gaps shrink, each arm’s asymptotic pulling rate becomes proportional to its variance. This generalizes the intuition from Example 1 and the homogeneous setting in [23]. We will include this as an illustrative example in the revised manuscript.

Besides this case (i.e., $\sigma_a=\Omega(1)$ for all $a$), we note that, unlike the two‑armed setting, our stability condition (14) may not be tight for general $K$: it is intrinsically harder to construct a counterexample as in Section 3.3 due to the increased number of parameters. In (14), we require an arm‑wise boundedness condition to guarantee convergence to the solution of (15), but we conjecture that it might be relaxed to a single, global condition over all arms.

2. Regret in the K‑armed setting. When

$$\sqrt{\sum_{a}\sigma_a^2}\lesssim \sum_{a\ge2}\frac{\sigma_a^2}{\sigma_1},$$

our regret bound in Theorem 5 reduces to

$$\widetilde O\bigl(\sqrt{\sum_{a\ge2}\sigma_a^2 T}\bigr),$$

matching previous variance‑aware results. However, in the regime of small $\sigma_a$ and large $\sigma_1$, our bound improves to

$$\sum_{a\ge2}\frac{\sigma_a^2}{\sigma_1}\sqrt{T},$$

which is near‑optimal in the two‑armed case (Theorem 3). Interestingly, for general $K$, this rate scales linearly in $K$, unlike the previous bound which scales as $\sqrt{K}$; we conjecture that such linear dependence may be unavoidable for UCB‑V, as supported by our empirical results in the Table below (if plotted, the curve of final cumulative regret versus $K$ exhibits an approximately linear trend). Establishing matching lower bounds remains a valuable direction for future work.

Table: Regret for UCB‑V under different $K$.

Simulation parameters: rewards are drawn from the beta distributions with $(\mu_1,\sigma_1)=(0.5,0.4)$ and $(\mu_2, \sigma_2) = \ldots = (\mu_K, \sigma_K) = (0.1, 0.01)$; each simulation is run for $T = 10,000$ rounds.

Limitation: Practical relevance of the two‑armed setting

We agree that a full treatment of the $K$-armed case is both important and challenging. Nonetheless, the two-armed setting itself actually admits several concrete applications. For example, A/B testing in web experiments or marketing campaigns naturally reduces to two arms (control vs. treatment). The analysis in the two-armed setting also provides useful insights for the eventual $K$-armed extension. We hope this explanation is helpful.