  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
$\Theta(\sqrt{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
$\Theta(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
$\Theta(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 $\Theta(T^{2/3})$. As applications of this
framework, we consider two major problems dealing with indirect feedback:
partial monitoring and graph bandits. 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 $\Theta(T^{2/3})$.
