acceptodds
Under review as a conference paper at ICLR 2027

Scalar Limits and Geometric Recovery in Softmax Gradient Bandits

Abstract

Softmax gradient bandits can converge to the best arm, but convergence alone does not determine the cumulative reward lost during learning. This leaves open whether adaptive learning rates and reward baselines can achieve square-root worst-case regret, or whether the update structure must change. The analysis addresses this question for bounded, independent and identically distributed rewards with a unique best arm. The analysis identifies a coupling in the mean update: a common scalar rescales corrective and competing drift terms together, while the baseline cancels from the conditional mean. Beyond this local mechanism, matching lower and upper polynomial exponents characterize the entire bounded scalar class, including history- and horizon-dependent learning rates and common baselines with nonnegative steps. For each fixed number of arms , its minimax regret is of order up to logarithmic factors, uniformly over an explicit neighborhood of biased initial logits. To change this coupling, an explicit diagonal update reweights coordinates while preserving softmax sampling and single-reward feedback. It achieves square-root worst-case regret up to logarithmic factors and polylogarithmic fixed-gap regret from every fixed finite initialization, without gap or horizon inputs. These guarantees establish a polynomial separation on the common initialization domain: changing coordinate weights achieves a regret exponent unavailable through bounded scalar tuning alone.

Primary area:
learning theory
Keywords:
stochastic multi-armed bandits, softmax gradient bandits, policy gradient, minimax regret, adaptive learning rates, diagonal preconditioning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_zqvYOpenReview ↗
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.

1 comment
AuthorsOpenReview ↗

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/K1-1/K for fixed K≥3K\ge3, whereas DGB achieves 1/21/2, up to logarithmic factors.

For a sampled arm II at policy pp, the score is eI−pe_I-p. In tabular softmax, the Fisher matrix is F=diag⁡(p)−pp⊤F=\operatorname{diag}(p)-pp^\top, and F(eI/pI)=eI−pF(e_I/p_I)=e_I-p. Thus the sampled natural-gradient direction is eI/pIe_I/p_I up to a common logit shift. Full inverse weighting of the score also gives eI/pI−1e_I/p_I-\mathbf1: 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−pe_I/\sqrt{p_I}-\sqrt 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/20<\gamma\le1/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\eta_t r_t, where rtr_t is the conditional expected regret in round tt. Small steps can hide many costly rounds in this weighted sum. To recover regret in actual rounds, we divide by ηt\eta_t. Its inverse depends on the running amplification cap C‾t\overline C_t. The same past observations determine the potential Wj,tW_{j,t}, which measures the other arms' probabilities relative to that of the best arm jj. Section 4 (p. 7) separates two products. Equation (67) in B.5 bounds the expectation of (t+C‾t)Wj,t(\sqrt t+\overline C_t)W_{j,t}. The second product is (C‾t−C‾t−1)Wj,t(\overline C_t-\overline C_{t-1})W_{j,t}. Since the cap increment is nonnegative, B.6 uses Wj,t≤ehWj,t−1W_{j,t}\le e^h W_{j,t-1} and then bounds the increment conditional on the previous history. At γ=1/2\gamma=1/2, B.1 gives β=1/2\beta=1/2, a=ν=1a=\nu=1, d=0d=0 and cγ=1/2c_\gamma=1/2: the extra step multiplier is one, so this argument applies to Algorithm 1.

Writing xi,t=Epi,tx_{i,t}=\mathbb E p_{i,t}, Lt=1+log⁡tL_t=1+\log t and vt=CrateLtω/tv_t=C_{\rm rate}L_t^\omega/\sqrt t, the resulting bound is Eq. (6): RT≤Cinit+∑t=1Tvt∑i≠jxi,t.R_T\le C_{\rm init}+\sum_{t=1}^T v_t\sum_{i\ne j}\sqrt{x_{i,t}}. Since the xi,tx_{i,t} sum to one over arms, Cauchy–Schwarz gives ∑i≠jxi,t≤K−1\sum_{i\ne j}\sqrt{x_{i,t}}\le\sqrt{K-1}. Also Lt≤LTL_t\le L_T for t≤Tt\le T and ∑t=1Tt−1/2≤2T\sum_{t=1}^T t^{-1/2}\le2\sqrt T, so ∑t=1Tvt≤2CrateLTωT\sum_{t=1}^T v_t\le2C_{\rm rate}L_T^\omega\sqrt T. Substitution gives (4) directly: RT≤Cinit+2CrateLTω(K−1)T.R_T\le C_{\rm init}+2C_{\rm rate}L_T^\omega\sqrt{(K-1)T}.

For fixed gaps Δi=μj−μi\Delta_i=\mu_j-\mu_i, subtract RT=∑t,i≠jΔixi,tR_T=\sum_{t,i\ne j}\Delta_i x_{i,t} from twice (6). The result is RT≤2Cinit+∑t,i≠j(2vtxi,t−Δixi,t).R_T\le 2C_{\rm init}+\sum_{t,i\ne j}\big(2v_t\sqrt{x_{i,t}}-\Delta_i x_{i,t}\big). Each summand is at most vt2/Δiv_t^2/\Delta_i. Summing over rounds and arms gives (5) for the same algorithm.

What depends on initialization? For fixed KK and starting probabilities, the design choices are hh and ω\omega. B.2 computes CinitC_{\rm init} directly from the initial potential and cap; for CrateC_{\rm rate}, it first bounds the potential moments and cap increments, then forms the mixed-moment constants A0,A1A_0,A_1. The definitions use no gaps or horizon. At a uniform start Cinit=2(1+K2)(K−1)/hC_{\rm init}=2(1+K^2)(K-1)/h. Diagonal weighting improves the exponent of TT; 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/Kp_{\min,1}\ge e^{-5/4}/K. Later probabilities are allowed to approach zero.

Reviewer_m77ROpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary
  • This work establishes regret limits for softmax gradient bandits with bounded learning rates and reward baselines that adapt to past observations. It proposes giving larger update weights to rarely selected arms and proves a polynomial regret improvement under specified initialization conditions.
Critical strengths
  • This work establishes a lower bound for softmax gradient bandit algorithms with bounded learning rates and reward baselines.
  • This work proposes a diagonal update and shows a polynomial regret separation from these algorithms on a common initialization domain.
Critical weaknesses
  • The presentation is very difficult to follow. Technical expressions are used without sufficiently explaining what they refer to. To name a few, these include “endpoint clock” and “tail-mass correction” (Section 5, p.7, lines 364, 370), and “projected score norm” (Section 6, p.9, lines 433-434). Ambiguous expressions are used in the conclusion section, such as “sufficient onset” and “asymptotic entry,” without clearly explaining their meaning (Section 7, p.9, lines 463–464). See the question below.

  • The empirical advantages of DGB are limited. It is outperformed by UCB1 and Thompson sampling in Figure 2(a), and by scalar baselines under uniform initialization in Figure 2(b). It also performs worse than the constructive scalar algorithm in all tested five-arm small-gap settings (Table 22). See the question below.

Questions for authors
  • Could you explain these terms more clearly in the main text and explicitly connect them to the corresponding quantities or operations? Could you also state the conclusions and limitations more clearly?

  • Could you clarify the practical significance of DGB given these experimental results? Also, could you show under what conditions its asymptotic theoretical advantage leads to improved finite-horizon performance?

2 comments
AuthorsOpenReview ↗

Where finite-horizon gains and losses occur; meanings of the terms

Thank you for asking when the change of update helps. For each start in the region of Theorem 1, Corollary 4 compares the best worst-case regret attainable by the scalar class with DGB's worst-case regret. The experiments ask a different question: for a specified instance, comparator and horizon, which update incurs less regret?

Where did regret decrease? At the five-arm Bernoulli anchor in Fig. 2(a), the initial logits (0,3,0,0,0)(0,3,0,0,0) favor the second-best arm; the means are (0.625,0.5,0.05,0.05,0.05)(0.625,0.5,0.05,0.05,0.05). This start lies outside the initialization region of Theorem 1. With (h,ω,γ)=(8,0.51,1/2)(h,\omega,\gamma)=(8,0.51,1/2) and step bound u=16u=16, DGB's sample mean regret at T=65,536T=65,536 was 808.74, versus 2401.27 for the lowest sample mean among 13 fixed scalar implementations (4,096 paired runs). The simultaneous 95% lower confidence bounds on the expected regret differences (scalar minus DGB) were positive for all 13 comparisons (Table 4).

In a separate 4,096-run cohort at the same biased anchor, DGB's sample mean regret at T=220T=2^{20} was 90.41% lower than S2's (constant step) and 82.01% lower than S10's (confidence-scaled step). Table 5 also quantifies persistence: for this numerical process, a simultaneous 95% confidence bound gives at least 45.38% lower expected regret than both controls at every integer horizon from 65,536 to 2202^{20}.

Where did the comparison reverse? With the same reward means but uniform initial probabilities, both displayed scalar controls had lower sample mean regret than DGB at T=65,536T=65,536 (Fig. 2(b)). Back at the original biased anchor, a separate 512-run comparison at T=220T=2^{20} gave sample means of 854.57 for DGB, 345.98 for UCB1 and 58.14 for Thompson sampling (Table 5, lower panel). Thus even at the anchor where DGB improved on S2 and S10, both standard bandit methods had lower sample mean regret.

Inside the region of Theorem 1, Tables 21–22 compare DGB with the theorem's constructive scalar rule, Upper, which knows the horizon. This separate small-gap study used u=1u=1, h=0.1h=0.1, ω=0.6\omega=0.6, T=218T=2^{18} and 32 paired runs per setting. Across two gaps and four starts, DGB's sample mean regret was 11.50%–15.18% lower in all eight three-arm settings and 45.68%–72.77% higher in all eight five-arm settings. The pull counts account for the difference: at the five-arm center with gap 1/321/32, more best-arm pulls saved 873.76 regret units relative to Upper, but extra pulls of arms 3–5 cost 6937.78, leaving DGB's sample mean regret 6064.02 higher.

Section 7 replaces the earlier phrases “sufficient onset” and “asymptotic entry” with the question that remains open: on a new instance, will DGB attain lower expected cumulative regret than a specified scalar rule, and if so, when? The worst-case exponents alone do not give that crossover horizon.

What do the terms measure? In §5, the “endpoint” is γ=1/2\gamma=1/2, the setting of Algorithm 1. Its cumulative step At=∑s<tηsA_t=\sum_{s<t}\eta_s adds the learning rates used before round tt. The “tail mass” is the total sampling probability outside the most probable arm, qt=1−max⁡ipi,tq_t=1-\max_i p_{i,t}. The general step has a multiplier qt−(1/2−γ)q_t^{-(1/2-\gamma)}, equal to one in Algorithm 1. In §6, projection removes the component that shifts every logit equally, since softmax is invariant to that shift. The norm is the Euclidean length of the remaining direction. At each state visited by Scalar-NM, both candidate updates are evaluated at that state; its scalar step matches their action-averaged squared lengths before multiplying by the reward residual (Appendix H.4, Eq. (160)). This matches scale, while the reward-weighted variances may differ.

We thank the authors for answering our question about DGB’s performance.

However, the revisions have not improved the paper’s readability, which we identified as the main weakness. We therefore maintain our rating of 1 (Reject).

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

The paper shows that for softmax gradient bandits with K ≥ 3 arms, no bounded scalar learning-rate or baseline schedule can beat roughly T^{1−1/K} worst-case regret from a biased initialization, and this rate is attainable. It then proposes a diagonal rescaling of the update (DGB) that recovers O~(T)\tilde{O}(\sqrt{T}) worst-case and polylogarithmic fixed-gap regret, establishing a polynomial separation.

Critical strengths
  • The main theoretical comparison is broad and sound. The lower bound covers history- and horizon-dependent learning rates and common baselines, including zero or vanishing steps, establishing a limitation of the scalar update class rather than a particular schedule.
  • The bounds match in their polynomial exponent. On the specified biased-initialization neighborhood, an upper bound within the scalar class achieves the same T^{1-1/K} exponent as the lower bound, making the characterization tight up to logarithmic factors.
Critical weaknesses
  • The sharp separation has a restricted initialization domain. The matching T^{1-1/K} characterization applies to a biased-logit neighborhood that excludes uniform initialization. Although the paper establishes an obstruction from uniform starts for each fixed anytime rule, its exponent is controller-dependent, leaving the sharp minimax rate under this common initialization unresolved.
Questions for authors
  • Can the sharp scalar minimax characterization be extended to uniform initialization, or is there evidence that its optimal exponent differs?
1 comment
AuthorsOpenReview ↗

What the uniform-start result establishes

The sharp scalar minimax exponent at uniform initialization is open for horizon-aware rules: our results establish neither equality with 1−1/K1-1/K nor a different value.

The distinction is how the algorithm is chosen. On the biased region, Theorem 1 allows a separate scalar rule for each horizon TT and gives a common lower bound with a matching polynomial exponent. Theorem 2 instead fixes one adaptive rule that runs at all horizons without receiving TT. From uniform logits, every such rule has a worst-case lower-bound exponent strictly above 1/21/2. That exponent, its constant and the horizon at which the bound applies may all depend on the rule. This leaves room between a lower bound for each fixed rule and one that holds uniformly when the rule is chosen anew for each TT.

There is a concrete obstacle to extending the biased-start proof. At uniform probabilities the best arm and its close rival are equally likely, so the outside-arm term that reinforces an existing lead vanishes. The rival's expected logit gain relative to the best arm is then −ηtδ/K≤0-\eta_t\delta/K\le0, where δ\delta is their mean-reward gap. For a rule that moves, Appendix D finds a finite history of positive probability that creates a rival lead. Both the probability of this event and the resulting lead depend on the rule; rules that never move are treated separately. Section 3 (p. 5) now explains this distinction after Theorem 2. DGB's upper bound itself holds at uniform initialization (Theorem 3).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision overview

For fixed K≥3K\ge3 on the stated region of biased initial logits, the bounded scalar class has minimax regret exponent 1−1/K1-1/K. One diagonal update (DGB) achieves exponent 1/21/2 with the same softmax sampling and single-reward feedback, up to logarithmic factors. The revision clarifies three aspects of this comparison; the algorithm, theorem statements, and experimental cohorts are unchanged.

  • Why the exponents differ. Section 3 connects the time spent favoring a rival to the limited information obtained from rare best-arm pulls. Section 4 shows why controlling step-weighted regret is insufficient when the step is adaptive, then derives both DGB rates from Eq. (6) (pp. 4–7; full proofs in A–C).
  • Which initializations are covered. The sharp scalar result allows a controller chosen for each horizon on the biased region. From uniform logits, each fixed anytime scalar rule faces a rule-dependent exponent above 1/21/2; the sharp horizon-aware scalar exponent there is open (Table 1; Theorem 2, p. 5).
  • What happens at finite horizons. At the five-arm anchor, whose initial bias lies outside the region of Theorem 1, DGB's gains over two fixed scalar implementations (S2 and S10) persist to T=220T=2^{20}. A separate small-gap study inside that region compares DGB with the theorem's constructive scalar rule (Upper). DGB had lower sample mean regret in the tested three-arm settings and higher sample mean regret in the five-arm settings. In the latter, the extra cost of sampling arms outside the best-arm/rival pair outweighed the saving from pulling the best arm more often (§6; Tables 5, 21–22).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.