acceptodds
Under review as a conference paper at ICLR 2027

Direct Contextual UCB under Exact Cauchy Noise

Abstract

Contextual bandits whose reward noise is so heavy-tailed that the mean does not exist break the usual pseudo-regret benchmark; we study exact symmetric Cauchy noise, targeting latent location regret. We analyze Direct-Cauchy-UCB, a one-pass arm-local projected gradient update driven by the Cauchy likelihood score, with optimism from the current iterate, and state per arm. Under bounded parameters, bounded contexts and directional excitation — every direction excited at every step—it attains high-probability location regret . Our lower bound of order matches this up to logarithmic factors once the horizon is large enough. The same update keeps that rate under a weaker windowed persistent-excitation assumption, covering deterministic adversarial context designs. Without any excitation assumption, an ellipsoidal variant is sublinear at with per-arm state. Beyond exact Cauchy noise, a sign (median-score) variant handles symmetric heavy tails at the same rate, with no moment assumption, given a known lower bound on the noise law's slope at its median. Bounded per-arm deviations of size from Cauchy cost the exact-score policy an additive , against a floor proved for that class. On synthetic exact-Cauchy environments our policy attains the lowest location regret among a strengthened suite of robust baselines at low and moderate noise scales.

Primary area:
optimization
Keywords:
contextual multi armed bandits, bandits with heavy tails

Reviews

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

This work studies linear contextual bandits under Cauchy reward noise, where expected rewards are undefined, using location regret instead. The authors propose Direct-Cauchy-UCB, a one-pass, arm-specific projected gradient method based on the Cauchy likelihood score.

Under directional excitation, the method achieves O~(Klog⁡T+KT)\widetilde O(K\log T+\sqrt{KT}) high-probability regret, with a minimax lower bound matching the leading dependence on KK and TT up to logarithmic factors. The analysis extends to windowed excitation, while an ellipsoidal variant achieves O~(dKT3/4)\widetilde O(\sqrt{dK}T^{3/4}) regret without excitation. Further results address general symmetric heavy-tailed noise through sign-based updates, scale uncertainty, and bounded deviations from Cauchy.

Synthetic experiments and an experiment on daily industry-portfolio returns compare the proposed approach with robust bandit baselines, with the strongest empirical results obtained by a practically tuned variant.

Critical strengths
  • The paper develops a computationally efficient approach to contextual bandit learning when reward means do not exist. By exploiting the bounded Cauchy likelihood score and its expected drift toward the true location, the authors derive confidence bounds directly from one-pass, arm-specific updates without repeatedly fitting a regression model. Under directional excitation, this yields near-minimax regret in KK and TT with O(d)O(d) memory per arm, giving a combination of statistical guarantees and computational efficiency.

  • The paper also examines how its theoretical guarantees extend under weaker assumptions. The main regret rate is preserved under windowed excitation, while an ellipsoidal variant achieves O~(dKT3/4)\widetilde O(\sqrt{dK}T^{3/4}) regret without excitation. Further results extend the analysis to symmetric heavy-tailed noise under a median-growth condition through sign-based updates and quantify the effect of bounded deviations from Cauchy. These results broaden the scope of the work.

Critical weaknesses
  • The practical significance of the main theoretical advantages is somewhat unclear. While the Cauchy setting provides a clean framework for studying learning without finite reward means, the paper also emphasizes computational efficiency. However, achieving near-minimax regret with O(d)O(d) memory relies on directional excitation, which may be difficult to verify under adaptive arm selection. The excitation-free variant broadens applicability but requires more memory and yields a weaker regret bound. This makes it difficult to assess when the main statistical and computational advantages can be realized together.

  • The experimental results do not directly validate the theoretically analyzed algorithm. The strongest empirical performance comes from Direct-Cauchy-Tuned, which uses online-Newton preconditioning and replaces the theoretically justified confidence radius with a proxy UCB bonus. These changes appear to go beyond ordinary hyperparameter tuning, making it difficult to assess how directly the experiments support the claimed statistical and computational advantages.

Questions for authors
  • Could the authors clarify what regret performance might be achievable by exactly maximizing the Cauchy likelihood at each round? In this context, what motivates the paper's emphasis on computational and memory efficiency and the associated regret guarantees, given that the Cauchy setting itself also appears to be motivated largely by theoretical understanding?

  • Could the authors clarify how the empirical results should be interpreted in relation to the theoretically analyzed algorithm, given the use of online-Newton preconditioning and a proxy UCB bonus in Direct-Cauchy-Tuned?

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

This paper studies contextual bandit with exact Cauchy noise, which does not have first monent as other heavy-tailed reward studied in previous paper. The paper proposes Direct-Cauchy-UCB, where the core component is an updating mechnism that survive the infinite-mean noise. The paper shows that the proposed algorithm achieves a regret upper bound of O~(KT)\tilde{O}(\sqrt{KT}) regret with excitation assumption and a regret upper bound of O~(dKT3/4)\tilde{O}(\sqrt{dK}T^{3/4}) regret upper bound without excitation. The proposed algorithm is further verified through numerical simulations.

Critical strengths
  1. This paper considers bandit learning with Cauchy noise, with is harder than the setting considered by previous work on heavy-taield bandit that the noise has 1+ϵ1+\epsilon moment. Under Cauchy noise, the paper proposes an algorithm that achieves sub-linear regret
  2. The paper spends reasonably space on explanation of core mechanism, which provides an overview of the idea of algorithm design
Critical weaknesses

I do not see major weakness. Some of my minor concerns and questions are listed below

  1. The paper starts with the complicated contextual linear setting. If my understanding is correct, this paper is the first one studying bandits with Cauchy noise, therefore I would generally expect preliminary results like the regret for multi-armed bandit, then linear bandit with single parameter, then the more complex setting studied in this paper. The current narration starts with the complex setting, making it a little bit hard to grasp the core idea of the algorithm design.
  2. The paper would also be benefited from a brief discussion of why previous approaches for heavy-tailed bandit is not applicable for Cauchy noise
  3. Could the author provide some explanation on why the regret becomes O(T3/4)O(T^{3/4}) without excitation. It looks like that in standard linear contextual bandit O(T)O(\sqrt{T}) regret is achievable even without excitation assumption. Could the author provide more discussion on this?
Questions for authors

See weakness

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

This paper does not seem to follow the ICLR 2027 template and it should be desk rejected.

Critical strengths

This paper does not seem to follow the ICLR 2027 template and it should be desk rejected.

Critical weaknesses

This paper does not seem to follow the ICLR 2027 template and it should be desk rejected.

Questions for authors

This paper does not seem to follow the ICLR 2027 template and it should be desk rejected.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.