Research map / Bandits and online learning / RL theory and MDPs
Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces uniform last-iterate (ULI) guarantee, a per-round suboptimality metric stronger than uniform-PAC, and shows elimination, adversarial-reduction, and a new oracle-efficient linear bandit and tabular MDP algorithm achieve near-optimal ULI, while optimistic methods (lil'UCB) do not.
Problem
Existing RL/bandit metrics (regret, (δ,ε)-PAC, uniform-PAC) evaluate cumulative performance and allow arbitrarily bad policies at late finite rounds, which is problematic in high-stakes applications.
Approach
Define uniform last-iterate (ULI): with high probability, per-round suboptimality Δ_t is bounded by a monotonically decreasing function of t (near-optimal ~ t^{-1/2}). Show ULI implies uniform-PAC and high-probability regret, analyze elimination and adversarial-based algorithms to achieve it, prove optimistic lil'UCB cannot, and extend phased elimination with an adaptive barycentric spanner for in
Key results
- Elimination algorithms SE-MAB and PE-MAB, and PE-L, achieve ULI with rate O~(t^{-1/2}), i.e., near-optimal.
- lil'UCB on a two-armed deterministic instance has Δ_t = Ω(t^{-1/4}) at some t, so optimistic algorithms are not near-optimal ULI and ULI is strictly stronger than uniform-PAC.
- The proposed infinite-armed linear bandit algorithm achieves ULI with O~(d^{3/2}/sqrt(t)) and O(d^3 log_C d) oracle calls per phase; the tabular MDP algorithm achieves O~(S^{3/2}A^{1/2}H^{5/2}/sqrt(t)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use successive elimination | Finite-arm MAB · Finite-arm MAB | ULI bound: \FULI(\delta,t)= \order \rbr{\sqrt{\frac{K\log \rbr{Kt/\delta}}{t}}} | Helped |
| Use phased elimination | Finite-arm MAB · Finite-arm MAB | ULI bound: \FULI(\delta,t) =\order \big(t^{-\frac{1}{2}}\sqrt{ K\log(\delta^{-1} K\log (t+1))}\big) | Helped |
| Use phased elimination | Finite-arm linear bandits · Finite-arm linear bandits | ULI bound: \FULI(\delta,t) =\order \big(t^{-\frac{1}{2}}\sqrt{d\log(\delta^{-1} K\log (t+1) \log d)}\big) | Helped |
| Use an adaptive barycentric spanner with phased elimination | Infinite-arm linear bandits · Infinite-arm linear bandits | ULI bound: \FULI(\delta,t)=\order \big(t^{-\frac{1}{2}}\sqrt{d^3\log(\delta^{-1} dt) } \big) | Helped |
| Use uncertainty-driven reward functions during exploration, followed by policy elimination | Tabular episodic MDP algorithm · Tabular episodic MDPs | ULI bound: \FULI(\delta,t) =\order \big(t^{-\frac{1}{2}} \sqrt{ S^3 A H^5 } \log \rbr{ t S A H /\delta}\big) | Helped |
| Use lil'UCB instead of an elimination-based algorithm | Two-armed bandit with deterministic rewards · Two-armed bandit with deterministic rewards | instantaneous suboptimality convergence rate: \Delta_t = \Omega \rbr{t^{-\frac{1}{4}} \sqrt{\log \log \rbr{\Delta^{-2} \log(\delta^{-1})} +\log(\delta^{-1})} } | Hurt |
| Use optimistic algorithms with a \log t bonus term | Finite-arm bandits · Finite-arm bandits | ULI guarantee | Hurt |
Surprising findings
- Optimistic algorithms with log t bonus (UCB) play suboptimal arms infinitely often, and even near-optimal uniform-PAC lil'UCB fails near-optimal ULI.
- Near-optimal ULI implies anytime sublinear high-probability regret but cannot give anytime sublinear expected regret.
Limitations
- Tabular MDP algorithm enumerates all deterministic policies and is not computationally efficient.
- Regret bound implied by ULI has suboptimal dependence on S, H and log terms; linear bandit regret has extra sqrt(d) factor.
Experimental setup
Metrics: per-round suboptimality bound (ULI) regret uniform-PAC sample complexity
Baselines: lil'UCB UCB uniform-PAC algorithms (Dann et al., 2017)
Builds on: uniform-PAC phased elimination UCB-VI lil'UCB
Closest papers by meaning
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.88)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.87)
- Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL (NeurIPS 2024 · similarity 0.87)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.87)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.86)
- Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.