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

Follow-the-Regularized-Leader (FTRL) is a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of Θ( √ T ) for the number of rounds T , and there are only a few studies on adaptive learning rates for problems with a minimax regret of Θ(T 2/3 ), which include several important problems dealing with indirect feedback. To address this limitation, we establish a new adaptive learning rate framework for problems with a minimax regret of Θ(T 2/3 ). Our learning rate is designed by matching the stability, penalty, and bias terms that naturally appear in regret upper bounds for problems with a minimax regret of Θ(T 2/3 ). As applications of this framework, we consider three major problems with a minimax regret of Θ(T 2/3 ): partial monitoring, graph bandits, and multi-armed bandits with paid observations. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adversarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of Θ(T 2/3 ).

for any ε ≥ 1/T , where z max = max t∈[T ] z t and h max = max t∈[T ] h t .

Within the general online learning framework, this theorem allows us to prove the following Bestof-Both-Worlds (BOBW) guarantee [10,58,61], which achieves an O(log T ) regret in the stochastic regime and an O(T 2/3 ) regret in the adversarial regime simultaneously: Theorem 2 (informal version of Theorem 7). Under some regularity conditions, an FTRL-based algorithm with SPB-matching achieves Reg T ≲ (z max h max ) 1/3 T 2/3 in the adversarial regime. In the stochastic regime, if √ z t h t ≤ √ ρ 1 (1 -q ta * ) holds for FTRL output q t ∈ P k and ρ 1 > 0 for all t ∈ [T ], the same algorithm achieves Reg T ≲ ρ1 ∆ 2 min log(T ∆ 3 min ) for the minimum suboptimality gap ∆ min .

To assess the usefulness of the above result that holds for the general online learning framework, this study focuses on two major hard problems: partial monitoring with global observability, graph