Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates

Summary

This paper studies stochastic gradient bandits with arbitrarily large learning rates. The authors prove an interesting result -- the learning rate of the gradient bandit algorithm (in particular, REINFORCE without baseline) can be arbitrarily large. Some numerical simulations are also provided to validate the findings.

Strengths

1. Theoretically, the authors prove that for any constant learning rate, the stochastic gradient bandit algorithm (REINFORCE without baselines) converges to the globally optimal policy almost surely as the number of iterations goes to infinity. The authors also avoid using non-uniform smoothness and noise growth conditions in a previous related work ([1]). 2. The authors also provide some simulation results to verify their theoretical findings. [1] Stochastic gradient succeeds for bandits.

Weaknesses

1. Optimization with large learrning rates have been studied, but the authors seem to only focus on the RL settings. It might be helpful to also include some literature review on deep learning with large learning rates (see, e.g., [1]). 2. Although it is shown that the algorithm can converge with arbitrarily large learning rates, it is still unclear what the exact convergence rate is. In contrast, a previous work [2], as also mentioned by the authors, has the finite-time convergence guarantees. 3. The code is not provided, although the experimental setting is simple. [1] Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability [2] Stochastic gradient succeeds for bandits.

Questions

1. Algorithm 1 is the gradient bandit algorithm without baselines. Can we also have similar results for the version with baselines? 2. What would be the challenges of extending the current analysis to the non-asymptotic rate analysis? Furthermore, what would be the challenges of extending the current proof techniques to other RL algorithms like natural gradient methods?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

1. The convergence results only imply asymptotic convergence without an explicit rate. Thus one direct question one may ask is, how does the learning rate affects the convergence speed. It would be interesting to study if there is an optimal learning rate. 2. The current results are only limited to REINFORCE without baselines for bandit setting, which is simpler than more complex RL settings. Hence it is unclear if it can provide any guidance to RL research in general.

Summary

This work studies the asymptotic global convergence rate of the stochastic gradient bandit algorithm with an arbitrary constant learning rate and proves that this algorithm asymptotically converges to the global optimal. This work reveals how this algorithm balances exploitation and exploration and proves the results by contradiction and reduction. This work also provides simulation experiments to support their results.

Strengths

The proof process based on contradiction and reduction is novel. Furthermore, the analysis reveals why the stochastic gradient bandits algorithm can naturally balance exploitation and exploration, which deepens the understanding of this algorithm.

Weaknesses

The empirical success of a large learning rate is unclear. This work shows that softmax policies and logistic regression can be learned when using a large learning rate. However, they do not show that a large learning rate can lead to great empirical performance.

Questions

Question 1: As shown in Figure 1, when choosing $\eta= 100$ or $1000$, the algorithm does not converge. Can you discuss this phenomenon in detail? Question 2: [1] consider $K=10$ in the simulation study. However, this work does simulation experiments with small arm numbers such as $K=4$ or $K=2$. It would be better to consider larger $K$ and show that the learning rate would not be influenced by $K$. Comment 1: It would be helpful to discuss the challenge when using the technique in [1] for a constant learning rate. [1] Mei, J., Zhong, Z., Dai, B., Agarwal, A., Szepesvari, C., & Schuurmans, D. (2023, July). Stochastic gradient succeeds for bandits. In International Conference on Machine Learning (pp. 24325-24360). PMLR.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors adequately addressed the limitations and societal impact.

Summary

The paper presents a novel theoretical analysis of the stochastic gradient bandit algorithm, showing that it converges to a globally optimal policy almost surely using any constant learning rate. This result is significant as it extends the understanding of stochastic gradient methods in bandit settings, even when standard smoothness and noise control assumptions do not hold.

Strengths

1. Theoretical Contribution: The paper provides a strong theoretical result, proving the global convergence of the stochastic gradient bandit algorithm for any constant learning rate. This is a significant advancement over existing literature that typically requires decaying or small learning rates. 2. Novel Insights: The authors uncover interesting properties of action sampling rates and the relationship between cumulative progress and noise, contributing to a deeper understanding of exploration-exploitation trade-offs in stochastic gradient methods. 3. Clarity and Rigor: The proofs are presented with clarity and rigor, making the paper accessible to readers with a solid background in stochastic optimization and reinforcement learning. 4. Empirical Validation: The simulation studies support the theoretical findings, demonstrating the convergence behavior under various learning rates.

Weaknesses

1. Practical Implications: While the theoretical results are robust, the practical implications, especially regarding the choice of learning rate in real-world applications, are not thoroughly discussed. It would be beneficial to include more guidance on how practitioners can leverage these findings. 2. Rate of Convergence: The paper establishes almost sure convergence but does not provide specific rates of convergence. Including more detailed analysis or conjectures about the rate would enhance the practical utility of the results. 3. Generalization: The study is limited to multi-armed bandits. Extending the results to more general reinforcement learning settings would significantly increase the impact of the work. 4. Assumption 1: The assumption that the true mean reward has no ties (Assumption 1) is restrictive. Addressing this limitation or providing more discussion on how this assumption might be relaxed in future work would strengthen the paper.

Questions

Proof Details: Could you provide more detailed explanations for Lemma 1 and Lemma 2? Specifically, how do the assumptions ensure the boundedness of parameters? Experimental Results: In the experimental section, you use different learning rates (η). Could you elaborate on the observed differences in convergence behavior for these learning rates? How does the algorithm perform with learning rates outside the tested range? Practical Implications: How would you recommend practitioners choose an appropriate learning rate for real-world applications based on your findings? Are there any heuristics or rules of thumb that can be derived from your results? Generalization: Your results are currently limited to multi-armed bandits. What challenges do you foresee in extending these results to more general reinforcement learning settings? How might the approach change? Assumption 1: Assumption 1 states that the true mean reward has no ties. How critical is this assumption to your results? Do you have any ideas on how to relax this assumption in future work? Convergence Rate: While you have shown almost sure convergence, the specific rate of convergence is not detailed. Could you provide more insights or conjectures about the expected rate of convergence for different learning rates? Limitations and Future Work: You mention that a more refined analysis is needed to explain the subtleties of different stages of convergence. Could you suggest specific directions or methods for this refined analysis?

Rating

8

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

no

Summary

The paper reveals that the stochastic gradient bandit algorithm converges to a globally optimal policy almost surely using any constant learning rate. This result stands even when traditional smoothness and noise control assumptions are not met, showing the algorithm’s balance between exploration and exploitation.

Strengths

1. The paper provides useful asymptotic insights into stochastic gradient bandits, which to the best of my knowledge are novel. Unlike previous work, where the methodology would not work for large learning rates, the gradient bandit algorithm proposed by the authors is proven to asymptotically converge to the globally optimal policy. 2. The paper discusses how exploration and exploitation trade-offs are balanced without exploration bonuses. Significant insights are provided into how constant learning rates affect the algorithm’s ability to explore different actions and avoid getting stuck in sub-optimal points. 3. The proof sketches for Theorems 1 and 2 are particularly beneficial in elucidating the intuition underpinning the proofs. The contradiction-based argument presented in the case where ( $K \geq 2$) is especially neat and clever.

Weaknesses

1. As the authors also acknowledge, Assumption 1 seems to be a strong one and possibly unrealistic in applications. 2. The work establishes almost sure convergence to the globally optimal policy as $t \rightarrow \infty$, which doesn't tell anything about the rate of convergence. 3. Section 5.1 in [23] appears to have similar results as the one presented in this paper. In the discussion of the natural exploratory behavior is attributed to the softmax Jacobian in the update, which is also discussed extensively in [23]. However, I understand that the main focus of [23] is to show that the stochastic gradient bandit algorithm converges to a globally optimal policy at an $O(1/t)$ rate. I am concerned that this paper loses significance as [23] already establishes convergence rates to the globally optimal policy. 4. Even though the main focus of the paper is theoretical, it would be nice to see how the stochastic gradient compares to other bandit algorithms such as UCB and Thompson Sampling in numerical experiments. *[23] Mei, Jincheng, et al. "Stochastic gradient succeeds for bandits." International Conference on Machine Learning. PMLR, 2023.*

Questions

1. The paper focuses on the simplest setting of the stochastic bandit problem, where decisions only matter for one step. The more common consideration in bandits literature is to maximizing the cumulative reward (or minimizing the expected regret). Can we apply the stochastic gradient bandit algorithm in that setting? 2. The numerical experiments section in the paper indicates that smaller learning rates perform better during early optimization stages, while larger rates are beneficial later. I have two related thoughts to this and was wondering if any comments could be made regarding the same: - For adaptive learning rates, can one think of running the algorithm in batches, such that the learning rates are decreased systematically for consequent batches? - Intuitively the right learning rate should depend on the underlying difficulty of the reward generating mechanism for different arms, however I am not sure if that is apparent from the discussion in the paper. 3. Can this be extended to the contextual bandits framework?

Rating

5

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes, limitations have been adequately addressed. Societal impact statement N/A.

Summary

This paper proved that stochastic gradient bandits converge to a globally optimal policy almost surely for arbitrary constant learning rates if true mean reward has no ties.

Strengths

This work extends the previous convergence results of stochastic gradient bandits by generalizing from a specific constant learning rate to an arbitrary constant learning rate. The high-level idea is demonstrated, and simple simulations are conducted to validate the theoretical finding.

Weaknesses

This paper heavily relies on prior work [23], which established the asymptotic rate for a constant learning rate. As a follow-up study, however, I believe this paper does not present sufficiently strong results to warrant acceptance at a top conference.

Questions

In simulations, if the learning rate is initially set to large number and then decreased, does algorithm show fast convergence?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

Yes, the authors address the limitations.

Reply to the rebuttal

Thank you for your rebuttal. Your rebuttal addressed my questions and I would like to keep my score to vote for acceptance.

Reply to rebuttal

Thank you for your rebuttal. I have updated the score to 'borderline accept.'