- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the sampled softmax policy-gradient algorithm for finite stochastic bandits. It derives an implicit critical learning rate for a bounded residual class: below or at this threshold, expected regret is uniformly O(log T), while above it, a bounded IID instance can produce polynomial expected regret. Below the threshold, it also proves inverse-gap cumulative allocation. At the critical point, a specially constructed two-arm signed-reward family exhibits a gap between the almost-sure logarithmic regret coefficient and the expected coefficient, attributed to rare trajectories and non-uniform integrability.
Critical strengths
The endpoint analysis. The exponential-drift function, the multi-arm subset-potential argument, and the change-of-measure lower bound form a technically ambitious attempt to characterize the safety boundary rather than merely give a sufficient small-step condition. The paper also makes a useful conceptual distinction between almost-sure convergence, typical-path regret, and expected regret. The cumulative allocation result and the explicit critical harmonic correction could be valuable if the proof details and literature positioning hold up.
Critical weaknesses
The claims should nevertheless be narrowed. The “exact safe range” is exact only for a highly restricted class: fixed finite K, a positive known gap floor, bounded residuals, IID pull-indexed rewards, a common predictable scalar baseline, and no resets, projections, or arm-specific rates. The critical expectation defect is proved for one special two-arm reward family, not for the whole class. Several ingredients are imported from recent work, including the convergence theorem used in the converse, while the novelty relative to Baudry et al. and Jia–Ouyang needs a more explicit theorem-by-theorem comparison. The harmonic coefficient is defined implicitly and appears computationally expensive, and the experiments are mainly illustrative: the rare-event estimates have very low effective sample size, so they do not provide strong quantitative validation of the asymptotic constants.
The biggest problem is that there is no sufficient discussion on related works, and the contributions are not properly contextualized in the literature.
Questions for authors
N/A.