Research map / Bandits and online learning / Online convex optimization and games
A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds
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.
Proposes SPB-matching, a simple adaptive FTRL learning rate for minimax-Theta(T^{2/3}) online learning problems, and uses it with Tsallis entropy to get improved best-of-both-worlds bounds for globally observable partial monitoring, weakly observable graph bandits, and MAB with paid observations.
Problem
Designing adaptive FTRL learning rates for online learning problems with minimax regret Theta(T^{2/3}) (hard problems with indirect feedback), where existing adaptive rates were designed for Theta(sqrt(T)) problems and BOBW guarantees for hard problems are complicated.
Approach
Choose the FTRL learning rate by matching the stability, bias (from forced exploration rate gamma_t = sqrt(z_t/beta_t) + u_t/beta_t), and penalty terms in the regret decomposition, yielding a simple recursive update for beta_t that adapts to both stability and penalty components; combined with Tsallis entropy (exponent 1 - 1/log k), this gives BOBW bounds including MS-type self-bounding bounds.
Key results
- For globally observable partial monitoring, the FTRL+SPB-matching algorithm achieves stochastic regret O(c_G^2 log k log T / Delta_min^2) and adversarial regret O((c_G T)^{2/3} (log k)^{1/3}), matching the best known adversarial rate while improving stochastic dependence.
- For weakly observable graph bandits, the algorithm achieves stochastic O(delta* log k log T / Delta_min^2) and adversarial O((delta* log k)^{1/3} T^{2/3}), the first FTRL-based O(log T) stochastic bound in this setting (with delta* the fractional domination number).
- For MAB with paid observations, the framework gives the first BOBW bounds: adversarial (ck log k)^{1/3} T^{2/3} + sqrt(T log k) and stochastic max{c,1} k log k log T / Delta_min^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SPB-matching with Tsallis entropy for globally observable partial monitoring | FTRL-based BOBW algorithm · Partial monitoring with global observability, stochastic | regret bound | Helped |
| Use SPB-matching with Tsallis entropy for weakly observable graph bandits | FTRL-based BOBW algorithm · Graph bandits with weak observability, stochastic | regret bound | Helped |
| Use fractional domination number δ* in place of weak domination number δ | SPB-matching graph-bandit bound · Graph bandits with weak observability, adversarial | regret bound | Mixed |
| Use SPB-matching for paid observations | FTRL-based BOBW algorithm · MAB with paid observations, stochastic and adversarial | regret bound | Helped |
Surprising findings
- The optimal Tsallis exponent in these settings is alpha = 1 - 1/log k, suggesting Shannon entropy used in prior work is reasonable.
- The naive choice gamma_t = sqrt(z_t/beta_t) (matching stability and bias only) fails for hard problems because a lower bound on exploration is needed to control loss estimator magnitude.
Limitations
- Graph bandit bound depends on fractional domination number delta* rather than weak domination number delta, which can be larger.
- Optimality in k, m, d for partial monitoring is unclear.
- Assumes unique optimal action and Pareto-optimal, non-duplicate actions in partial monitoring; results are theoretical only.
Experimental setup
Metrics: pseudo-regret upper bounds (adversarial, stochastic, self-bo
Baselines: Tsallis-INF-style FTRL for partial monitoring (Tsallis/Shannon entropy BOBW) reduction-based BOBW for partial monitoring Shannon-entropy FTRL for graph bandits reduction-based BOBW for graph bandits MAB with paid observations minimax algorithm
Builds on: Tsallis-INF FTRL stability-penalty decomposition AdaGrad-style adaptive learning rates self-bounding constraint regime (Zimmert and Seldin)
Closest papers by meaning
- On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls (NeurIPS 2025 · similarity 0.90)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.89)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.89)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.89)
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.88)
- Online Non-convex Learning in Dynamic Environments (NeurIPS 2024 · similarity 0.88)
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.