Pith. sign in

REVIEW 3 major objections 3 minor 41 references

Precise Asymptotics and Refined Regret of Variance-Aware UCB

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that UCB-V's arm-pulling counts converge to a deterministic fixed-point law, except at one critical variance-gap ratio where they turn unstable; it also derives a refined regret bound that depends on the optimal arm's…

desk verdict Solid on the stable-side asymptotics and the refined regret bound; the headline instability result is proven only for an oracle-variance variant, so the abstract overclaims as written. read the letter →

arxiv 2412.08843 v2 pith:IBRKM2EF submitted 2024-12-12 stat.ML cs.LGmath.STstat.TH

Yingying Fan , Yuxuan Han , Jinchi Lv , Xiaocong Xu , Zhengyuan Zhou This is my paper · ORCID
classification stat.MLcs.LGmath.STstat.TH MSC 62L0560F0568W27
keywords multi-armedbanditsUCB-Vvariance-awareexplorationarm-pullingratesasymptoticstabilityphasetransitionfixed-pointequationregretbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies UCB-V, the variant of the upper-confidence-bound bandit algorithm that builds its exploration bonus from variance estimates, and tries to say exactly how often it pulls each arm over a long horizon. Its main claim is that, away from one exceptional regime, the arm-pulling counts are asymptotically deterministic: the number of pulls of the optimal arm converges in probability to the unique solution of an explicit fixed-point equation, so an experimenter can predict the algorithm's exploration. The exception is a phase transition: when the optimal arm has much smaller variance than the suboptimal arm and the gap sits at precisely $\Delta_2 = \sigma_2\sqrt{\rho\log T / T}$, there is a Bernoulli bandit on which the optimal arm is pulled far too few and far too many times, each with constant probability. The same concentration machinery yields a high-probability regret bound of order $(\sigma_2 \wedge 16\sigma_2^2 / \sigma_1)\sqrt{\rho T\log T}$, the first variance-aware regret bound that shows the optimal arm's own variance helps.

What carries the argument

The machinery is the monotone map $\phi(n;\sigma)=(\sigma\vee n^{-1/2})/\sqrt{n}$, which converts a pull count into the scale of the UCB-V bonus, together with the fixed-point equation $f(\phi)=1$ whose left side is the sum in (6). Proposition 1 sandwiches the realized $\phi_{1,T}$ between solutions of $f(\phi)=1\pm\varepsilon$ with probability $1-\delta$, and Lemma 2 controls how far a perturbed solution lies from $\phi^\star$; that control degrades exactly when $\sigma_2^2/(T\bar\Delta_2^2)$ approaches 1 in the $\sigma_1=o(\sigma_2)$ regime, which is the mechanism behind the phase transition. For the hard instance, a Donsker-principle anti-concentration lemma (Lemma 22) shows that the Bernoulli reward path can sit just above or just below the critical threshold at the last pull times, forcing $n_{1,T}$ into two separated scales with constant probability.

What would settle it

Run Algorithm 1 on the two-armed Bernoulli instance of Proposition 5 (arm 1 reward $\mu+\Delta$ with variance 0, arm 2 reward $\mu$ with variance $\mu(1-\mu)$, and $\Delta = \mu(1-\mu)\rho\log T/T$) over many horizons. If at the critical ratio the distribution of $n_{1,T}$ concentrates at $n^\star_{1,T}$ with probability tending to 1, the phase-transition claim fails for the estimated-variance algorithm; if it stays bimodal with both $P(n_{1,T}\le c\sqrt{T\log T})$ and $P(n_{1,T}\ge c^{-1}T/\sqrt{\log T})$ bounded below by a positive constant, the claim survives. A companion check is whether the $Z$-statistic for the suboptimal arm remains asymptotically standard normal at that ratio.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that UCB-V has a deterministic skeleton. Let $\phi(n;\sigma) = (\sigma \vee n^{-1/2})/\sqrt{n}$ be the variance-aware scale of the bonus. The paper shows that, unless a single exceptional ratio is hit, the optimal arm's pull count $n_{1,T}$ satisfies $$\frac{\$sigma_1^{2}$ \vee \$\varphi$(n^\star_{1,T};\bar\sigma_1)}{T\$\varphi$(n^\star_{1,T};\bar\sigma_1)^2} + \frac{\$sigma_2^{2}$ \vee (\$\varphi$(n^\star_{1,T};\bar\sigma_1)+\bar\Delta_2)}{T(\$\varphi$(n^\star_{1,T};\bar\sigma_1)+\bar\Delta_2)^2} = 1$$ in the sense that $n_{1,T}/n^\star_{1,T}\xrightarrow{p}1$, with $n^\star_{1,T}$ the unique solution of this fixed-point equation. The counterpoint is Proposition 5: when $\sigma_1=o(\sigma_2)$ and $\Lambda_T = \sigma_2\sqrt{\rho\log T}/(\sqrt T\,\Delta_2)\to 1$, there is a Bernoulli instance in which even an oracle-variance version of UCB-V satisfies $P(n_{1,T}\le c_1\sqrt{T\log T})$ and $P(n_{1,T}\ge c_1^{-1}T/\sqrt{\log T})$ both bounded below by a positive constant. Hence at that critical ratio the arm-pulling rates are not asymptotically deterministic.

Load-bearing premise

The load-bearing premise is that the instability proven for UCB-V with true variances already known carries over to UCB-V with its own estimated variances; that transfer is assumed rather than proved, and if it fails the phase transition disappears while the stability theorem and regret bound survive.

Editorial extensions

If this is right

  • Away from the critical ratio, UCB-V's exploration is predictable at the $n^\star_{a,T}$ scale; for stable arms the martingale CLT gives asymptotic normality of $\sqrt{n_{a,T}}(\bar X_{a,T}-\mu_a)/\hat\sigma_{a,T}$, enabling confidence intervals for adaptively collected rewards.
  • At the critical ratio, that CLT fails: the paper's Bernoulli instance makes the $Z$-statistic distribution noticeably non-normal, so post-policy inference for UCB-V data requires new methods or a different variance-aware rule.
  • The high-probability bound on suboptimal-arm pulls yields regret $O((\sigma_2 \wedge 16\sigma_2^2/\sigma_1)\sqrt{\rho T\log T})$; when $\sigma_1\gg\sigma_2$ this improves on the previously known $O(\sigma_2\sqrt{T\log T})$ regret and reveals that a larger optimal-arm variance directly lowers regret.
  • In the $K$-armed extension, the same fixed-point equation (15) predicts pull counts whenever condition (14) holds, and the regret bound becomes $O((\sqrt{\sum_{a\ne1}\sigma_a^2} \wedge \sum_{a\ne1}16\sigma_a^2/\sigma_1)\sqrt{\rho T\log T})$.
  • In the small-gap, homogeneous-variance limit the optimal arm's share of pulls tends to $\sigma_1^2/(\sigma_1^2+\sigma_2^2)$, generalizing the canonical UCB's $1/2$ share and giving the higher-variance arm more exploration.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension the paper leaves implicit: the instability half of the abstract is proven for UCB-V run with oracle variances (Proposition 5), and the transfer to the fully estimated Algorithm 1 is assumed rather than proven; if that transfer fails, UCB-V could remain asymptotically deterministic at the critical ratio while the stability theorem and regret bound would still stand.
  • Adjacent problem worth testing: the critical ratio $\Lambda_T=1$ is exactly where the gap sits on the variance-driven diffusion scale $\sigma_2\sqrt{\rho\log T/T}$, so a diffusion-limit analysis of UCB-V at this boundary would be a natural check on whether the phase transition persists under the estimated-variance algorithm.
  • Open sharpening the paper leaves for future work: condition (14) is sufficient for $K$-arm stability, and a plausible sharp condition is that at least one suboptimal arm stays safely away from its critical variance-gap ratio even when others approach it.
  • Untested conjecture with a clean experiment: variance-adaptive Thompson sampling on the same two-armed Bernoulli instance should show a similarly bimodal arm-pull distribution at the analogue of $\Lambda_T=1$, which would confirm that the phenomenon is not specific to UCB-V.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper analyzes the UCB-V bandit algorithm and gives three sets of results. First, it derives a deterministic fixed-point equation for the asymptotic arm-pulling counts and proves, under a stability condition (Theorem 3, condition (5)), that n_{a,T}/n^*_{a,T} converges to 1 in probability. Second, it claims a phase transition at the critical ratio Λ_T = 1 when σ_1 = o(σ_2): at this point UCB-V is said to be unstable, with the optimal-arm pull count taking both sublinear and near-linear values with constant probability (Section 3.3, Proposition 5). Third, it uses high-probability bounds on the suboptimal-arm pull count to derive a refined regret bound for UCB-V of the form O((σ_2 ∧ σ_2^2/σ_1) √(T log T)) and complements it with matching lower bounds (Theorems 7 and 8). The proofs are extensive and largely self-contained, with concentration inequalities and perturbation analyses of the fixed-point equation.

Significance. If the results are correct, the paper makes a substantial contribution to the precise asymptotic theory of variance-aware bandit algorithms. The deterministic fixed-point characterization, the high-probability confidence region for pull counts, and the refined regret bound with variance of the optimal arm are all novel and of interest to the bandit and adaptive-inference communities. The paper is careful to derive the fixed-point equation from the algorithm's decision rule rather than fitting it to simulations, and the lower-bound constructions are explicit. The claimed instability at Λ_T = 1 is the most striking finding, as it contrasts with the stability of canonical UCB; however, the formal support for that specific claim is currently incomplete, and one of the K-armed stability statements appears to contain a mathematical error. The core stability theorem and the regret bound are more robust and would remain valuable even if the instability claim is later modified.

major comments (3)
  1. [§3.3, Proposition 5] The instability result that supports the paper's central claim — that UCB-V 'can exhibit instability' — is proved only for an oracle-variance variant of Algorithm 1: Proposition 5 explicitly states that n_{a,T} is computed by Algorithm 1 with σ̂_{a,t} = σ_a. The abstract and the discussion following Proposition 5, however, present this as a property of UCB-V itself. No proof is given that the bimodal behavior transfers to Algorithm 1 with estimated variances. Lemma 11 gives uniform control on |φ̂_{a,t} − φ_{a,t}|, but that bound is o(1), not o(1/√T), and the oracle-variance proof at the critical ratio is a delicate balance involving fluctuations of order 1/√n. An o(1) error in the bonus term could in principle shift the threshold or smooth the bimodality. This is a load-bearing gap for the abstract's instability claim, though the stability theorem and the regret bound do not depend on this transfer. The authors should either prove Proposition 5 for the estimated-variance algorithm or explicitly restrict the instability claim to the oracle variant and adjust the abstract and title-level conclusions accordingly.
  2. [Theorem 9 and Lemma 19, condition (14) and bound (36)] The K-armed stability condition (14) and the perturbation bound (36) in Lemma 19 use the expression (1/(K−1) − σ_a^2/(T Δ̄_a^2))_+^{-1} ∧ (σ_a^2/(T Δ̄_a^2) − 1)_+^{-1} ∧ σ_a/(σ_1 ∨ T^{−1/2}). Since exactly one of the two reciprocal terms is positive on each side of the critical ratio — and the other is zero — the minimum of the two terms is identically zero near the critical ratio. For K = 2, this makes condition (14) vacuous: it holds even when σ_2^2/(T Δ̄_2^2) → 1, which contradicts Theorem 3 and Proposition 5. The proof of Lemma 19 actually derives separate bounds for the two regimes and then combines them; the displayed ∧ must be replaced by an addition or the two reciprocal terms must appear as separate summands in the max. As written, Theorem 9 would claim stability for the two-armed case in exactly the regime where the paper establishes instability. This is a correctness issue in the K-armed extension and requires a correction.
  3. [Section 3.3, proof of Proposition 5, Appendix C.3] In the proof of the upper bound for n_{1,T}, the text states 'n_{1,T1} = n_{1,T1} − 1' where the intended identity is n_{1,T1} = n_{1,T} − 1, since T_1 is the last time arm 1 is pulled. The surrounding argument depends on the correct identity to relate n_{1,T1} to n_{1,T}; the displayed typo does not affect the conclusion, but it makes the proof difficult to follow. Please correct it and check for similar typographical slips elsewhere in the appendix.
minor comments (3)
  1. [Abstract] The abstract contains the phrase 'more complicate and advanced variance-aware online decision-making algorithms'; this should be 'more complicated and advanced'.
  2. [Introduction, bullet list after Theorem 3] The summary bullet on instability writes events of the form P(n_{1,T} ≳ T) ∧ P(n_{1,T} ≲ √T/σ_2) ≳ 1, while Proposition 5 states the slightly different bounds n_{1,T} ≤ c_1 √(T log T) and n_{1,T} ≥ c_1^{−1} T / log^{1/2} T. The introduction should reconcile these two statements, since the log factors are not visible in the bullet-list version.
  3. [Appendix C.3] The appendix refers to 'Lemme 14' and 'Lemme 16' (typos for 'Lemma'); the same formatting issue appears with the symbols '≳' and '≲' rendered as 'greaterorsimilar' in places.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the deterministic fixed-point equations are derived from the UCB-V decision rule and concentration inequalities, not fitted to the arm-pulling counts they predict.

full rationale

The paper's central derivation is self-contained. Proposition 1 obtains a sandwich inequality for the arm-pulling counts directly from the UCB-V selection rule and the concentration events M and V, without using the target arm-pulling rates as inputs. The deterministic equation f(phi)=1 in Eq. (3) is then read off from that inequality, and Eq. (6) defines n*_a,T as the unique solution of that equation; uniqueness is proved internally in Lemma 2 rather than imported from prior work. Theorem 3's stability conclusion follows by combining Proposition 1, Lemma 2, and an elementary equivalence between phi-ratios and count-ratios (Proposition 15), so the prediction n_a,T/n*_a,T -> 1 is not equivalent to its own definition. The high-probability regret bound in Theorem 7 is derived from the non-asymptotic pull-count bound in Proposition 6, which again follows from the UCB rule and concentration, and the lower bounds in Theorem 8 use a standard divergence decomposition; none of these steps fits a parameter to data and then calls the same quantity a prediction. The instability result in Proposition 5 is formally stated for the oracle-variance variant with hat-sigma = sigma, so its transfer to Algorithm 1 with estimated variances is an unproven gap and a correctness risk, but it is not circularity: Proposition 5 does not assume the conclusion it is used to support, and no equation in its proof reduces by construction to its input. Self-citations to Kalvit and Zeevi, Khamaru and Zhang, and the companion Han et al. paper provide context and comparison, but the load-bearing arguments (perturbation analysis, concentration bounds, and lower-bound constructions) are carried out in the present paper rather than being replaced by those citations. No circular step satisfying the quoted-evidence standard can be identified.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to data; the algorithm's exploration coefficient rho is a user input, not a fitted constant. The fixed-point equation is derived from concentration inequalities, so the analysis is self-contained. The paper relies on standard tools: bounded rewards, a time-uniform law of the iterated logarithm, Donsker's theorem, and the martingale CLT from Khamaru and Zhang (2024). No new entities are postulated.

free parameters (1)
  • Exploration coefficient rho
    The UCB-V algorithm takes rho as an input. The theory requires rho > 1 for the asymptotic results (Theorem 3) and rho >= C0 for a large universal constant in the regret bound (Theorem 7). No value is fitted to data.
assumptions (4)
  • domain assumption Rewards are supported on [0,1] with mean mu_a and variance sigma_a^2.
    Stated at the beginning of Section 1; used throughout for boundedness in the Bernstein LIL, the concentration events, and the regret bounds.
  • standard math Time-uniform law of iterated logarithm (Lemma 20) holds for bounded i.i.d. random variables.
    Proved in Appendix F; it underpins the high-probability events M and V used in Proposition 1 and hence all subsequent results.
  • standard math Donsker's theorem for Bernoulli random walks.
    Used in Lemma 22 to establish the anti-concentration events U and L with constant probability, which drive the instability result.
  • standard math Martingale CLT for stable arms from Khamaru and Zhang (2024, Section 2.1).
    Used in Section 3.2.2 to link arm stability to asymptotic normality of the Z-statistic; this is an external result, not rederived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Precise Asymptotics and Refined Regret of Variance-Aware UCB." pith.science (2026). https://pith.science/paper/IBRKM2EF

@misc{pith2026241208843,
  author       = {Pith},
  title        = {Pith review of: Precise Asymptotics and Refined Regret of Variance-Aware UCB},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IBRKM2EF}},
  note         = {Machine review of arXiv:2412.08843}
}
read the original abstract

In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems, a variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its decision-making process. More precisely, we provide an asymptotic characterization of the arm-pulling rates for UCB-V, extending recent results for the canonical UCB in Kalvit and Zeevi (2021) and Khamaru and Zhang (2024). In an interesting contrast to the canonical UCB, our analysis reveals that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve a more refined regret bound, previously unknown even for more complicate and advanced variance-aware online decision-making algorithms.

Figures

Figures reproduced from arXiv: 2412.08843 by the authors.

Figure 1
Figure 1. The distributions of n1,T (optimal arm-pulling count) for UCB-V and UCB with T = 50, 000 over 5000 repetitions. in the optimal arm-pulling numbers, as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. (a): The regrets of UCB-V with σ2 ≍ T −1/4 , ∆2 ≍ 1/ √ T fixed and σ1 ≍ T −1/2 , T −1/4 , 1, each instance with 10 repetitions. (b): The median and 30% quantile of n1,T (optimal arm-pulling count) for UCB and UCB-V, under varying ΛT in the σ1 = o(σ2) regime, with T = 1, 000, 000 over 30 repetitions for each ∆2. The red dotted line is the predicted n1,T of UCB-V using (6). Notation. For any positive integer n, denote… view at source ↗
Figure 3
Figure 3. (a): The confidence region of n1,T under different ΛT , with σ1 = o(σ2). The dot￾ted lines represent the exact and perturbed solutions of (3), where the perturbed curves solve f(ϕ) = 1±1/ log T. The UCB-V line shows the number of arm pulls under the UCB-V algorithm with 30% quantile, with T = 105 over 30 repetitions. (b): The ratio between the perturbed solution f(ϕ) = 1 ± 1/ log T and the exact solution f(ϕ) = 1 is… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The empirical distributions of the Z-statistic for the sub-optimal arm for UCB and UCB-V with σ1 = 0, σ2 = 1/4 under different ΛT , both with T = 50, 000 over 2, 000 repetitions. which allows for the application of the martingale CLT to establish the asymptotic normali…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 28 canonical work pages

  1. [1]

    Agrawal and N

    S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39--1. JMLR Workshop and Conference Proceedings, 2012

    work page 2012

  2. [2]

    V. F. Araman and R. A. Caldentey. Diffusion approximations for a class of sequential experimentation problems. Management Science, 68 0 (8): 0 5958--5979, 2022

    work page 2022

  3. [3]

    Audibert, R

    J.-Y. Audibert, R. Munos, and C. Szepesv \'a ri. Tuning bandit algorithms in stochastic environments. In International conference on algorithmic learning theory, pages 150--165. Springer, 2007

    work page 2007

  4. [4]

    Audibert, R

    J.-Y. Audibert, R. Munos, and C. Szepesv \'a ri. Exploration--exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410 0 (19): 0 1876--1902, 2009

    work page 1902

  5. [5]

    P. Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3 0 (Nov): 0 397--422, 2002

    work page 2002

  6. [6]

    Billingsley

    P. Billingsley. Convergence of probability measures. John Wiley & Sons, 2013

    work page 2013

  7. [7]

    H. Chen, W. Lu, and R. Song. Statistical inference for online decision making: In a contextual bandit setting. Journal of the American Statistical Association, 116 0 (533): 0 240--255, 2021

    work page 2021

  8. [8]

    X. Chen, Z. Lai, H. Li, and Y. Zhang. Online statistical inference for contextual bandits via stochastic gradient descent. arXiv preprint arXiv:2212.14883, 2022

    arXiv 2022

Show all 41 references
  1. [9]

    Y. Dai, R. Wang, and S. S. Du. Variance-aware sparse linear bandits. arXiv preprint arXiv:2205.13450, 2022

    2022 arXiv

  2. [10]

    Q. Di, T. Jin, Y. Wu, H. Zhao, F. Farnoud, and Q. Gu. Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00968, 2023

    2023 arXiv

  3. [11]

    Dimakopoulou, Z

    M. Dimakopoulou, Z. Ren, and Z. Zhou. Online multi-armed bandits with adaptive inference. Advances in Neural Information Processing Systems, 34: 0 1939--1951, 2021

    1939

  4. [12]

    C. Duan, J. Li, and D. Xia. Online policy learning and inference by matrix completion. arXiv preprint arXiv:2404.17398, 2024

    2024 arXiv

  5. [13]

    Even-Dar, S

    E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7 0 (6), 2006

    2006

  6. [14]

    Fan and P

    L. Fan and P. W. Glynn. Diffusion approximations for thompson sampling. arXiv preprint arXiv:2105.09232, 2021 a

    2021 arXiv

  7. [15]

    Fan and P

    L. Fan and P. W. Glynn. The fragility of optimized bandit algorithms. arXiv preprint arXiv:2109.13595, 2021 b

    2021 arXiv

  8. [16]

    Fan and P

    L. Fan and P. W. Glynn. The typical behavior of bandit algorithms. arXiv preprint arXiv:2210.05660, 2022

    2022 arXiv

  9. [17]

    Faury, M

    L. Faury, M. Abeille, C. Calauz \`e nes, and O. Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052--3060. PMLR, 2020

    2020

  10. [18]

    Goldenshluger and A

    A. Goldenshluger and A. Zeevi. A linear response bandit problem. Stochastic Systems, 3 0 (1): 0 230--261, 2013

    2013

  11. [19]

    Hadad, D

    V. Hadad, D. A. Hirshberg, R. Zhan, S. Wager, and S. Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, 118 0 (15): 0 e2014602118, 2021

    2021

  12. [20]

    Q. Han, K. Khamaru, and C.-H. Zhang. Ucb algorithms for multi-armed bandits: Precise regret and adaptive inference. 2024. URL https://arxiv.org/abs/2412.06126

    2024 arXiv

  13. [21]

    Honda and A

    J. Honda and A. Takemura. Optimality of thompson sampling for gaussian bandits depends on priors. In Artificial Intelligence and Statistics, pages 375--383. PMLR, 2014

    2014

  14. [22]

    Kalvit and A

    A. Kalvit and A. Zeevi. A closer look at the worst-case behavior of multi-armed bandit algorithms. Advances in Neural Information Processing Systems, 34: 0 8807--8819, 2021

    2021

  15. [23]

    Kaufmann, O

    E. Kaufmann, O. Capp \'e , and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 0 (1): 0 1--42, 2016

    2016

  16. [24]

    Khamaru and C.-H

    K. Khamaru and C.-H. Zhang. Inference with the upper confidence bound algorithm. arXiv preprint arXiv:2408.04595, 2024

    2024 arXiv

  17. [25]

    Kuang and S

    X. Kuang and S. Wager. Weak signal asymptotics for sequentially randomized experiments. Management Science, 2023

    2023

  18. [26]

    T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 0 (1): 0 4--22, 1985

    1985

  19. [27]

    Lattimore

    T. Lattimore. Refining the confidence level for optimistic bandit strategies. Journal of Machine Learning Research, 19 0 (20): 0 1--32, 2018

    2018

  20. [28]

    Lattimore and C

    T. Lattimore and C. Szepesv \'a ri. Bandit algorithms. Cambridge University Press, 2020

    2020

  21. [29]

    Mukherjee, K

    S. Mukherjee, K. Naveen, N. Sudarsanam, and B. Ravindran. Efficient-ucbv: An almost optimal algorithm using variance estimates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018

    2018

  22. [30]

    X. Nie, X. Tian, J. Taylor, and J. Zou. Why adaptively collected data have negative bias and how to correct for it. In International Conference on Artificial Intelligence and Statistics, pages 1261--1269. PMLR, 2018

    2018

  23. [31]

    Rigollet and A

    P. Rigollet and A. Zeevi. Nonparametric bandits with covariates. COLT 2010, page 54, 2010

    2010

  24. [32]

    D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning , 11 0 (1): 0 1--96, 2018

    2018

  25. [33]

    Saha and B

    A. Saha and B. Kveton. Only pay for what is uncertain: Variance-adaptive thompson sampling. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=p8ujRTjEf3

    2024

  26. [34]

    Simchi-Levi, Z

    D. Simchi-Levi, Z. Zheng, and F. Zhu. Regret distribution in stochastic bandits: Optimal trade-off between expectation and tail risk. arXiv preprint arXiv:2304.04341, 2023

    2023

  27. [35]

    Slivkins et al

    A. Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning , 12 0 (1-2): 0 1--286, 2019

    2019

  28. [36]

    M. S. Talebi and O.-A. Maillard. Variance-aware regret bounds for undiscounted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770--805. PMLR, 2018

    2018

  29. [37]

    R. Xu, Y. Min, and T. Wang. Noise-adaptive thompson sampling for linear contextual bandits. Advances in Neural Information Processing Systems, 36, 2024

    2024

  30. [38]

    R. Zhan, V. Hadad, D. A. Hirshberg, and S. Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125--2135, 2021

    2021

  31. [39]

    Zhang, L

    K. Zhang, L. Janson, and S. Murphy. Inference for batched bandits. Advances in neural information processing systems, 33: 0 9818--9829, 2020

    2020

  32. [40]

    Zhang, J

    Z. Zhang, J. Yang, X. Ji, and S. S. Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34: 0 4342--4355, 2021

    2021

  33. [41]

    H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pages 4977--5020. PMLR, 2023

    2023

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.