- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper gives results on the convergence of policy gradient methods for softmax bandits. The first part gives finite-time upper and lower bounds for the vanilla PG with baseline approach, and establishes a tight T^{1-1/K} bound for K actions. Of course, general RL formulations, which are not studied here, have the additional complexity of min probability on the optimal policy's choices, which is a trivial concern in softmax bandits. We can always initialize at the zero weights, and this yields a uniform distribution. An inverse dependence on the min probability is present in the results of this paper too, showing that any general results will be subject to the same issues. That said, a precise finite-time result is still interesting and novel to my knowledge.
Second, the authors show a bound using a diagonal correction that can be improved a \sqrt{T} rate. This is certainly novel and interesting. But the authors overlook an interesting connection here. A classical no-regret algorithm for bandits is EXP3, which takes the form of \theta_{t+1, i} = \theta_{t, i} - \eta \ell_{t,i}1(i = i_t)/p_{t, i}. With the diagonal normalization, the DGB rule obtains some of this inverse probability correction as well. Finally, there is NPG which also looks close to EXP3 and DGB for the softmax bandits case as explained in the work of Agarwal et al. (2020) on policy gradient methods. Crucially, both EXP3 and NPG can be analyzed in a couple of pages of elementary arguments, instead of the mammoth appendix in this paper, so the authors need to give a good argument for the added complexity.
Finally, while not the topic of this paper, I am concerned regarding the scope of the diagonal correction's impacts, given that the crucial min probability terms are still retained in the final bounds.
Critical strengths
The results are novel and interesting, and the diagonal correction is also a very simple algorithmic trick with a significant boost to convergence rates.
Critical weaknesses
The paper needs to better connect to the relevant literature as indicated above. More crucially, the paper, as written is not readable. This is somewhat true of the main text, and extensively true for the appendix. Even understanding why the stated DGB bound for exponent of 1/2 correctly follows from the master theorem is not easy. There are about 10 constants which are interdependent, and whose settings need to be verified. Use of AI in assisting with analysis is okay, but the authors bear the responsibility for producing human readable artifacts.
Questions for authors
Please address the comments in the weaknesses above.
Update geometry, the master inequality, and initialization constants
Thank you for asking how DGB relates to EXP3 and natural policy gradient, and which part of the proof is responsible for the square-root bound.
What changes in the update? Our main comparison is between the bounded scalar class and DGB. Both sample from the softmax policy and observe one reward per round. On the biased-initialization region of Theorem 1, the scalar class has minimax exponent 1−1/K for fixed K≥3, whereas DGB achieves 1/2, up to logarithmic factors.
For a sampled arm I at policy p, the score is eI−p. In tabular softmax, the Fisher matrix is F=diag(p)−pp⊤, and F(eI/pI)=eI−p. Thus the sampled natural-gradient direction is eI/pI up to a common logit shift. Full inverse weighting of the score also gives eI/pI−1: modulo that shift, this is the importance-weighted direction in the EXP3 log-weight update. Classical EXP3 additionally mixes in uniform exploration. DGB instead uses eI/pI−p and an adaptive step that limits amplification. Its corrections to two unselected arms can therefore differ. This compares directions; the guarantee here is for partial weighting (0<γ≤1/2). Section 1 and Appendix N connect this calculation to Auer et al., Agarwal et al., and Chung et al.
Where does the proof do the work? The one-step drift controls ηtrt, where rt is the conditional expected regret in round t. Small steps can hide many costly rounds in this weighted sum. To recover regret in actual rounds, we divide by ηt. Its inverse depends on the running amplification cap Ct. The same past observations determine the potential Wj,t, which measures the other arms' probabilities relative to that of the best arm j. Section 4 (p. 7) separates two products. Equation (67) in B.5 bounds the expectation of (t+Ct)Wj,t. The second product is (Ct−Ct−1)Wj,t. Since the cap increment is nonnegative, B.6 uses Wj,t≤ehWj,t−1 and then bounds the increment conditional on the previous history. At γ=1/2, B.1 gives β=1/2, a=ν=1, d=0 and cγ=1/2: the extra step multiplier is one, so this argument applies to Algorithm 1.
Writing xi,t=Epi,t, Lt=1+logt and vt=CrateLtω/t, the resulting bound is Eq. (6): RT≤Cinit+∑t=1Tvt∑i=jxi,t. Since the xi,t sum to one over arms, Cauchy–Schwarz gives ∑i=jxi,t≤K−1. Also Lt≤LT for t≤T and ∑t=1Tt−1/2≤2T, so ∑t=1Tvt≤2CrateLTωT. Substitution gives (4) directly: RT≤Cinit+2CrateLTω(K−1)T.
For fixed gaps Δi=μj−μi, subtract RT=∑t,i=jΔixi,t from twice (6). The result is RT≤2Cinit+∑t,i=j(2vtxi,t−Δixi,t). Each summand is at most vt2/Δi. Summing over rounds and arms gives (5) for the same algorithm.
What depends on initialization? For fixed K and starting probabilities, the design choices are h and ω. B.2 computes Cinit directly from the initial potential and cap; for Crate, it first bounds the potential moments and cap increments, then forms the mixed-moment constants A0,A1. The definitions use no gaps or horizon. At a uniform start Cinit=2(1+K2)(K−1)/h. Diagonal weighting improves the exponent of T; the constants retain their initial-policy dependence. They are finite for each fixed finite start and uniformly bounded on the comparison region, where initially pmin,1≥e−5/4/K. Later probabilities are allowed to approach zero.