Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits

arXiv:2510.22819 · cs.LG · Submitted 2026-08-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits".

Jane: The paper was written by Jingxin Zhan, Yuze Han and Zhihua Zhang from Peking University and Renmin University of China.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we're digging into a fresh arXiv paper with a real mouthful of a title: "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits." Jane, I'm going to need you to translate that for our listeners.

Jane: Happy to, Tom. So imagine you're at a casino with a row of slot machines. You don't know which one pays out best, and you have to decide which to pull each round. That's the multi-armed bandit problem. The "FTRL" part is a specific strategy for making those decisions, and the "one/two-Tsallis entropy" is a particular formula that strategy uses to balance exploring new machines versus sticking with the ones that look good.

Tom: Right, and this paper is from Jingxin Zhan, Yuze Han, and Zhihua Zhang at Peking University. They're looking at something called "last-iterate convergence." That's a fancy way of asking: if you run this strategy for a long time, how quickly does your final choice get close to the best possible choice?

Jane: Exactly. Most research on these algorithms focuses on the total regret—how much money you lost over the whole game. But this paper asks a different question: at any single moment, how good is your current guess? That matters in real life, like in clinical trials where you're testing drugs. You don't just care about the average performance; you care about whether the drug you're giving patients right now is the right one.

Tom: And the authors found something specific. They proved that the gap between where the algorithm is and where it should be shrinks at a rate of one over the square root of time. So if you run it for one hundred rounds, the gap is roughly a tenth of where it started. Run it for ten thousand rounds, and it's a hundredth.

Jane: That's solid progress, but here's the intriguing part. The algorithm achieves logarithmic regret, which is the gold standard. And mathematically, that suggests the last-iterate convergence should be even faster—like one over time, not one over square root of time. The authors couldn't quite prove that stronger result, but their experiments hint it's true.

Tom: So they've got a proven result and a tantalizing conjecture. That's the kind of thing that gets researchers excited. We'll dig into the actual proof techniques and the new decomposition they introduced in just a moment.

Jane: And I want to talk about why this matters beyond the math. If we can get faster convergence, that means real systems—recommendation engines, adaptive pricing, clinical trials—can zero in on the best option more quickly. That's a big deal.

Tom: Stick around. We're just getting started with "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits."

Summary: Tom: Welcome back. We're still on "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits." Jane, let's get into what the paper actually does, because the summary is pretty dense.

Jane: The core contribution is a new way to analyze the algorithm's behavior at each step, not just over the whole run. They call it a "new decomposition." Think of it like taking apart a car engine to see how each cylinder fires, instead of just measuring how fast the car goes.

Tom: And that decomposition lets them prove something concrete. The Bregman divergence—which is a mathematical way to measure the distance between the algorithm's current probability distribution and the perfect distribution that always picks the best arm—decays at a rate of t to the minus one-half. So after t rounds, the distance is proportional to one over the square root of t.

Jane: That's their Theorem three point two, and it's the first time anyone has proven a last-iterate convergence result for this specific FTRL algorithm in the stochastic bandit setting. That's a meaningful milestone.

Tom: But they didn't stop there. They also ran experiments. They set up a simple problem with five arms, each with a different average loss, and ran the algorithm a million times, repeating the whole thing five thousand times to get good statistics.

Jane: The experiments confirmed their theoretical result—the Bregman divergence decayed at the predicted rate. But here's the exciting part: the simple regret, which is the actual expected loss at each step, decayed at a rate of one over t, which is faster than their proof guarantees.

Tom: So the theory says "at least this fast," and the experiments say "actually, it's faster." That gap between theory and practice is exactly where the next breakthrough will come from.

Jane: And the authors are honest about that. They say the faster rate is a conjecture, not a proven theorem. They even include a counterexample showing why their current proof technique can't directly give the stronger result.

Tom: A counterexample in the appendix—that's the kind of rigor I appreciate. They're not overselling their results. They're saying, "Here's what we proved, here's what we suspect, and here's why the proof doesn't easily extend."

Jane: That intellectual honesty is what makes this paper valuable to the community. It gives other researchers a clear target. Now we know the gap between the proven bound and the suspected bound, and we can try to close it.

Tom: So we've got a new proof technique, a solid result, and a clear open question. Next, we should talk about the technical machinery they built—the lemmas about bounding the estimated losses and controlling how fast the algorithm's choices change.

Jane: That's where the real engineering of the proof happens. Let's get into that.

Improvements: Tom: We're back with "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits." Jane, the proof of this result isn't just one big leap—it's built on several smaller technical pieces. What are the key ones?

Jane: The first is what they call a bound on the second moment of the estimated loss. That sounds technical, but here's the intuition. The algorithm uses an unbiased estimator for the losses, but that estimator can have huge variance, especially when the algorithm rarely picks a suboptimal arm. The authors show that even with that variance, the squared estimated loss grows only linearly with time, not quadratically.

Tom: And why is that important?

Jane: Because it lets them control how much the algorithm's belief about the best arm can be thrown off by noise. If the estimator's variance blew up too fast, the algorithm might get stuck on the wrong arm. Their Lemma four point one shows that doesn't happen.

Tom: The second piece is about how fast the algorithm's choices can change from one round to the next. They prove that the probability of picking any arm can't jump up too much in a single step—it's bounded by a constant times the previous probability plus a small term that shrinks with time.

Jane: That's Lemma four point four, and it's crucial for handling what they call the "extra term" in their decomposition. In the classical analysis, there's no such term, but their new decomposition introduces it, and they need to show it doesn't blow up.

Tom: And they do that by proving two smaller lemmas about the properties of the function that maps cumulative losses to probabilities. One handles additive changes—like when you update the loss estimate for one arm—and the other handles multiplicative changes—like when the learning rate shrinks over time.

Jane: The learning rate is another important detail. The algorithm uses a learning rate that decays as one over the square root of time. That's what makes the algorithm adaptive, but it also complicates the analysis because the algorithm's objective changes slightly each round.

Tom: So they're juggling three things at once: the noisy loss estimates, the changing learning rate, and the need to track the distance to the optimal distribution. And they manage to keep all three under control.

Jane: That's the real contribution. The self-bounding technique they use—where you bound a quantity in terms of itself—is extended in a new way. They derive a lower bound on the simple regret that's tied to the Bregman divergence, which is exactly what you need to close the loop.

Tom: It's like they built a new tool for the toolbox. And that tool might apply to other algorithms, not just this one. The authors even mention that in the paper—these techniques could be useful for analyzing other FTRL variants.

Jane: Exactly. So we've got a new decomposition, new bounds, and a proof that works. But the experiments showed something even faster. We should talk about what that means for the field and where this research goes next.

Tom: Let's wrap up with the big picture.

Conclusion: Tom: Alright, we're wrapping up our discussion of "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits." Jane, give us the one-minute version.

Jane: The paper proves that this particular bandit algorithm—one/two-Tsallis-INF—converges to the optimal strategy at a rate of one over the square root of time, measured by a specific distance called the Bregman divergence. That's the first such result for this algorithm in the stochastic setting.

Tom: And the experiments suggest the actual convergence is even faster—one over time—but the authors couldn't prove that yet. So there's a clear open problem for future researchers.

Jane: The techniques they introduced—the new decomposition, the bounds on estimated losses, the control on how fast probabilities change—those are reusable tools. Other researchers working on FTRL algorithms can pick these up and apply them to their own problems.

Tom: Why should our listeners care? Because bandit algorithms are everywhere. They're in ad placement, clinical trials, recommendation systems, even in how robots explore unknown environments. Faster convergence means these systems adapt more quickly to the best option, which saves money, time, and in medical contexts, lives.

Jane: And the fact that this algorithm is "best of both worlds"—it works well whether the environment is predictable or adversarial—makes it especially valuable in real-world settings where you don't know what you're dealing with.

Tom: So we've got a solid theoretical result, a tantalizing conjecture, and practical implications. That's a good day's work from the authors.

Jane: We'll be watching to see if someone closes that gap between t to the minus one-half and t to the minus one. That would be the next big result in this line of research.

Tom: Thanks for joining us. We're signing off on "Last-Iterate Analyses of FTRL with the one/two-Tsallis Entropy in Stochastic Bandits." Next time, we'll pick up another paper from the arXiv. Until then, keep exploring.

Jane: See you all next time.

Jingxin Zhan, Yuze Han, Zhihua Zhang

Peking University · Renmin University of China

cs.LG

Submitted: 2026-08-15

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 67/100

The gist: This paper investigates the last-iterate convergence properties of the Follow-the-Regularized-Leader (FTRL) algorithm with the 1/2-Tsallis entropy regularizer in stochastic multi-armed bandits.

Key concepts

Stochastic Bandits
This problem involves choosing among several options (like slot machines) where the outcome of each choice is uncertain. The goal is to decide which option pays out best over time while balancing exploration and exploitation.
FTRL
A specific strategy used in bandit problems, FTRL helps make decisions by balancing the need to explore new options with sticking to those that have performed well so far.
Last-Iterate Convergence
This measures how quickly the algorithm's current choice approaches the best possible choice as it runs for a long time. It differs from measuring total loss over the entire game, focusing instead on instantaneous performance.
Bregman Divergence
A mathematical measure used to quantify the distance between the algorithm's current probability distribution and the perfect distribution that always selects the best option.

Terminology

Summary

This paper investigates the last-iterate convergence properties of the Follow-the-Regularized-Leader (FTRL) algorithm with the 1/2-Tsallis entropy regularizer in stochastic multi-armed bandits. The algorithm, named 1/2-Tsallis-INF, was previously shown by Zimmert and Seldin [2021] to achieve logarithmic regret in stochastic bandits and the Best-of-Both-Worlds (BOBW) property. However, its last-iterate convergence rate had not been studied prior to this work.

The paper addresses the natural question: Does the last-iterate convergence rate of the 1/2-Tsallis-INF scale as O(t−1)? The authors provide a preliminary positive answer by proving that the Bregman divergence between the point mass on the optimal arm and the probability distribution obtained at iteration t decays at a rate of O(t−1ᐟ2).

Main Results:

  1. Theorem 3.2: For Algorithm 1 (1/2-Tsallis-INF), if 0 < α < 1, then for any t ≥ 1:

E[D Ψ(e i*, p t)] ≤ C(C α d4/Δ3 + d5/(αΔ) + d5/α2) t−1ᐟ2,

where C α = α3/(3(1−α2)) and C is a positive constant.

  1. Corollary 3.3: For any i ≠ i*, E[√p t,i] ≤ C(C α d4/Δ3 + d5/(αΔ) + d5/α2) t−1ᐟ2, and consequently, the simple regret satisfies Reg simple t ≤ C Σ i≠i* Δ i (C α d4/Δ3 + d5/(αΔ) + d5/α2) t−1ᐟ2.

Technical Contributions:

The paper introduces a new decomposition (Lemma 3.1) tailored for last-iterate analysis:

⟨p t − e i*, l̂ t⟩ = ⟨p t − p t+1, l̂ t⟩ − (1/η t+1)D Ψ(p t+1, p t) + (1/η t+1)(D Ψ(e i*, p t) − D Ψ(e i*, p t+1)) + (1/η t+1 − 1/η t)⟨p t+1 − e i*, η t L̂ t⟩.

This decomposition differs from classical regret decompositions by the appearance of the extra term III, which requires new techniques to handle.

Key Intermediate Results:

  1. Lemma 4.1: E[L̂2 t,i*] ≤ (C d e α/(α2(1−α2))) t, showing that the second moment of the estimated loss of the optimal arm grows at most linearly. This is achieved without concentration inequalities by decomposing L̂ t,i* into a sum of simple inner products and a regret term.

  2. Lemma 4.4: p t+1,i ≤ 7d·p t,i + 1/t, bounding the growth rate of each component of p t. This follows from two perturbation results (Lemma 4.5 and Lemma 4.6) about the continuity properties of the function φ.

  3. Lemma 5.1: Reg simple t ≥ (C(1−α2)Δ/(d e α2))(E[D Ψ(e i*, p t)])2, establishing a new lower bound connecting the simple regret to the Bregman divergence.

Proof Strategy:

The proof uses a self-bounding technique. Taking expectations on both sides of the new decomposition and rearranging terms, the authors obtain an iterative inequality for E[D Ψ(e i*, p t)]:

(1−α2)Δ/(d e α2)(E[D Ψ(e i*, p t)])2 ≤ C d3/(α2 tΔ) + C(d2/(α√t) − Δ)+ + C′α√t + 1·E[D Ψ(e i*, p t) − D Ψ(e i*, p t+1)].

Applying Lemma B.2 to this inequality yields the final t−1ᐟ2 convergence rate.

Experimental Validation:

The paper includes experiments on a Bernoulli bandit instance with d = 5 arms and mean loss vector μ = (0.1, 0.2, 0.3, 0.4, 0.5), run for 106 rounds and repeated 5000 times. The log-log plot regression shows slopes of −0.494 for E[D Ψ(e i*, p t)] (consistent with the theoretical t−1ᐟ2 rate) and −0.989 for Reg simple t (suggesting a t−1 rate, confirming the conjecture).

Concluding Remarks:

The paper notes that while the t−1ᐟ2 convergence rate of the Bregman divergence does not directly imply a t−1 last-iterate convergence rate, this does not mean the latter is necessarily stronger, since the Bregman divergence also contains the term 2(1−p t,i*)2/√p t,i*, whose convergence rate cannot be directly inferred from last-iterate analysis. A counterexample in Appendix E illustrates this point. The authors state this is the first last-iterate convergence result for FTRL algorithms in stochastic bandits, and the new decomposition and extended self-bounding techniques may be applicable to other FTRL-related algorithms.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems, particularly for sequential decision-making and online learning:

1. Adaptive Exploration-Exploitation Balancing

  • Implement the 1/2-Tsallis-INF algorithm with the exact regularizer Ψ(p) = -4∑√pi and learning rate ηt = α/√t

  • The system automatically balances exploration and exploitation without needing separate exploration parameters or schedules

  • Guarantees logarithmic regret in stochastic environments while maintaining optimal adversarial performance (Best-of-Both-Worlds property)

2. Last-Iterate Convergence Guarantees

  • The improved system now has provable convergence guarantees for its final decision distribution, not just average performance

  • Specifically, the Bregman divergence between the current arm-selection distribution and the optimal distribution decays at rate O(t(-1/2))

  • This means the system's actual decisions at each time step become increasingly reliable, not just its cumulative performance

3. Robust Decision Making Under Uncertainty

  • The system uses importance-weighted loss estimators that remain unbiased even when arm selection probabilities are small

  • The new bound on the second moment of the estimated loss (Lemma 4.1) ensures the system doesn't suffer from variance explosion

  • The growth control lemma (Lemma 4.4) prevents the selection probabilities from changing too drastically between consecutive rounds

4. Self-Bounding Regret Analysis

  • The system now has a new decomposition (Lemma 3.1) that separates stability, penalty, and learning-rate adjustment terms

  • This enables tighter analysis of the trade-off between exploration (maintaining diverse arm selection) and exploitation (concentrating on the best arm)

  • The lower bound on simple regret (Lemma 5.1) connects the convergence of the Bregman divergence to actual performance improvements

5. Practical Applications

  • Clinical Trial Design: The system can identify the best treatment more quickly while maintaining rigorous statistical guarantees

  • Recommendation Systems: Can balance showing diverse content (exploration) with showing known-good content (exploitation) with provable convergence to optimal recommendations

  • A/B Testing: Provides reliable decisions at any point during the experiment, not just at the end

  • Resource Allocation: Can dynamically allocate resources across options with guaranteed convergence to the optimal allocation

6. Theoretical Guarantees for Safety-Critical Systems

  • The convergence rate O(t(-1/2)) for the Bregman divergence provides a concrete bound on how quickly the system's decisions become reliable

  • The simple regret bound O(t(-1/2)) (Corollary 3.3) directly quantifies the expected performance gap between the system's chosen action and the optimal action at any time t

  • These guarantees hold even in adversarial environments, making the system suitable for deployment in uncertain or changing conditions

7. Implementation Efficiency

  • The algorithm requires only O(d) computation per round (where d is the number of arms/options)

  • The closed-form solution for the probability distribution (Eq. 5) avoids expensive numerical optimization

  • The system can handle large action spaces efficiently while maintaining theoretical guarantees

Sources

Related papers