acceptodds
Withdrawn from ICLR 2027

The Price of a Fixed Scale: Exact Regret Constants and Adaptive Scaling for Tsallis-INF

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Best of both worlds bandit algorithms are usually compared by regret rates, but their stochastic leading constants determine whether robustness preserves asymptotic efficiency. We resolve this question for reduced variance -Tsallis-INF. For every fixed scale and fixed , its Bernoulli small gap coefficient is exactly under an explicit admissibility condition. The optimum is , strictly above the local Lai–Robbins constant , while the standard choice yields . Thus every fixed scale under this limit misses local Lai–Robbins efficiency. The formula points to local variance as the missing quantity. Guided by this decomposition, we adapt the scale using sparse probes that require neither instance parameters nor arm order. For two stochastic arms, a fixed clip family approaches for every interior mean, and a moving-clip learner attains on the central family under ordered limits. The proof identifies a harmonic occupation law and controls the singular regret cost using recovery estimates and inverse moments. The adaptive learners do not retain adversarial guarantees, and we do not provide a joint finite horizon and small gap rate.

Primary area:
learning theory
Keywords:
multi-armed bandits, online learning, stochastic bandits, adversarial bandits, regret minimization, Tsallis-INF

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jR5FOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the precise stochastic regret constants of Tsallis-INF, beyond its known regret-rate guarantees. Under the stated assumptions, it shows that no fixed learning-rate scale attains the local optimal constant when the horizon tends to infinity before the arm gaps vanish. The authors also propose adaptive scaling methods for two-arm Bernoulli bandits that approach or attain this benchmark under additional conditions. The analysis connects long-run sampling behavior to limiting stochastic processes. The adaptive methods do not retain the adversarial guarantees of the original algorithm.

Critical strengths

The paper addresses an interesting question about the precise regret constants of Tsallis-INF. Understanding the limitations of fixed learning-rate scaling is a worthwhile direction beyond establishing regret rates.

Critical weaknesses

I found the paper very difficult to follow. The exposition is repetitive and fragmented, with extensive technical qualifications that obscure the main ideas and logical dependencies. It often reads like heavily AI-assisted text that would benefit from substantial editorial revision. In particular, I struggled to understand the precise scope of the main theorems, the specific gap they address in the existing literature, and the significance of the resulting advances. A clearer explanation of what was previously unknown, what is established here, and why it matters is needed. This makes independent verification difficult. Although I have not identified an error in the main theorems and I am not an expert is this field, the current presentation leaves me insufficiently confident in both correctness and significance of the results. These concerns contribute to my weak reject recommendation.

Questions for authors

Could the authors substantially revise the paper to present its contributions more clearly and concisely? In particular, please explain the precise gap in the literature, state the main theorems with their assumptions and implications, and clarify why the results are significant relative to prior work. Streamlining repetitive passages and providing a concise overview of the proof strategy would make the paper easier to follow and independently verify.

Reviewer_iyPvOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the exact asymptotic regret constants of Tsallis-INF in stochastic multi-armed bandits. For the reduced variance estimator with a fixed learning rate scale cc, the authors derive the exact small-gap regret coefficient C(c)=4/c2+3/8+c2/128C(c)=4/c^2+3/8+c^2/128. Its minimum is approximately 0.7286, strictly larger than the Lai–Robbins constant 1/2 for Bernoulli means near 1/2. The paper also derives corresponding results for the standard importance-weighted estimator. Motivated by the fixed-scale result, the authors further propose adaptive scaling algorithms that achieve the Lai–Robbins constant for two-arm Bernoulli bandits under ordered limits.

Critical strengths
  • I like Theorem 1, which establishes the exact asymptotic regret coefficient of fixed-scale Tsallis-INF. It shows that even the optimal fixed scale cannot achieve the local Lai–Robbins constant. This provides a more precise understanding of the stochastic efficiency of a widely studied bandit algorithm.
  • The proof of Theorem 1 is technically nontrivial. In particular, establishing the exact regret constant requires controlling a singular inverse-square cost through recovery estimates and uniform integrability arguments.
Critical weaknesses
  • The presentation and writing could be improved. For example, the paper could provide a clearer introduction to the problem background and better explain the motivation for studying this problem.
  • The adaptive scaling results are limited to two-arm stochastic Bernoulli bandits. Moreover, Theorem 2 requires four ordered limits, while Theorem 3 only establishes the optimal constant when the two arms have means 1/21/2 and 1/2+Δ1/2+\Delta.
Questions for authors
  • In the proof of Proposition 2, could the authors explain in more detail how the recovery estimates extend to time-varying clipping parameters, and how the resulting bounds establish the uniform integrability needed for the exact regret identity in Eq. (137)?
  • Existing algorithms such as KL-UCB already achieve asymptotic optimality for general stochastic Bernoulli bandits. In contrast, the proposed adaptive scaling algorithms are limited to two arms and do not retain adversarial guarantees. Could the authors clarify what advantages or additional contributions these algorithms offer over existing methods such as KL-UCB?
Reviewer_JAiKOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the leading regret constant of reduced-variance 1/21/2-Tsallis-INF in stochastic Bernoulli bandits. For every fixed scale cc and fixed KK, it establishes the exact small-gap coefficient C(c)=4/c2+3/8+c2/128C(c) = 4/c^2 + 3/8 + c^2/128 under the stated admissibility condition, taking T→∞T \to \infty before the gaps vanish. The minimum over cc is (3+22)/8≈0.7286(3+2\sqrt{2})/8 \approx 0.7286, which is strictly above the local Lai–Robbins constant 1/21/2. For two arms, it further proposes sparse-probe adaptive scaling: a fixed-clip family approaches the local Lai–Robbins coefficient, and a moving-clip learner attains 1/21/2 when the optimal mean is 1/21/2, both under ordered limits.

Critical strengths

The exact characterization of the leading regret constant is interesting. The explicit formula identifies the optimal fixed scale and quantifies its remaining gap to the local Lai–Robbins benchmark.

Critical weaknesses

The presentation makes the paper hard to follow, and its contributions are difficult to assess.

  1. Some key objects are not specified in the main text. The MC learner is only described qualitatively before Theorem 3. Its update rules and the roles of α\alpha and MM are deferred to Appendix I. Similarly, the process that Theorem 1 relies on is only given in Eq. (24) of Appendix A.

  2. Section 3 devotes substantial space to proof-level details, including KKT calculations, compact-set estimates, and the coordinate update table. Moving these details to the appendix would leave more space for explaining the main results and specifying the MC learner.

  3. Several abbreviations are introduced without being explicitly expanded, including RV, IW, and VA (in πΔ,L,UVA\pi^{\mathrm{VA}}_{\Delta,L,U}).

  4. The repeated use of the letter aa for different purposes (the arm index, ai=min⁡x∈Qxia_i = \min_{x \in Q} x_i, and the scale ana_n) adds avoidable notational overhead.

  5. There are layout issues. The table on page 4 has no caption or number and is not referenced in the text. Figure 3 is not referenced in the text and interrupts the guide to the results and proofs on page 13.

  6. Some wording is unnecessarily rhetorical, such as "The scientific point is architectural" and "The question has teeth".

Overall, the main result seems interesting, but the current presentation makes it difficult to check the results and assess the contribution. I think the paper needs substantial revision before it is ready for publication.

Questions for authors

See weakness

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.