- 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 high-probability regret, with a minimax lower bound matching the leading dependence on and up to logarithmic factors. The analysis extends to windowed excitation, while an ellipsoidal variant achieves 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 and with 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 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 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?