We study how to adapt to smoothly-varying ('easy') environments in well-known
online learning problems where acquiring information is expensive. For the
problem of label efficient prediction, which is a budgeted version of
prediction with expert advice, we present an online algorithm whose regret
depends optimally on the number of labels allowed and $Q^*$ (the quadratic
variation of the losses of the best action in hindsight), along with a
parameter-free counterpart whose regret depends optimally on $Q$ (the quadratic
variation of the losses of all the actions). These quantities can be
significantly smaller than $T$ (the total time horizon), yielding an
improvement over existing, variation-independent results for the problem. We
then extend our analysis to handle label efficient prediction with bandit
feedback, i.e., label efficient bandits. Our work builds upon the framework of
optimistic online mirror descent, and leverages second order corrections along
with a carefully designed hybrid regularizer that encodes the constrained
information structure of the problem. We then consider revealing action-partial
monitoring games -- a version of label efficient prediction with additive
information costs, which in general are known to lie in the \textit{hard} class
of games having minimax regret of order $T^{\frac{2}{3}}$. We provide a
strategy with an $\mathcal{O}((Q^*T)^{\frac{1}{3}})$ bound for revealing action
games, along with one with a $\mathcal{O}((QT)^{\frac{1}{3}})$ bound for the
full class of hard partial monitoring games, both being strict improvements
over current bounds.

研究了如何适应信息获取成本昂贵的在线学习问题中平稳变化环境的影响；提出了一种算法用于处理标签有效预测的问题，并扩展到标签有效的赌博反馈和揭示行动部分监测游戏等领域，显著提高了现有算法的性能。

信息约束在线学习中的适应性

On Adaptivity in Information-constrained Online Learning

We study a general class of online learning problems where the feedback is
specified by a graph. This class includes online prediction with expert advice
and the multi-armed bandit problem, but also several learning problems where
the online player does not necessarily observe his own loss. We analyze how the
structure of the feedback graph controls the inherent difficulty of the induced
$T$-round learning problem. Specifically, we show that any feedback graph
belongs to one of three classes: strongly observable graphs, weakly observable
graphs, and unobservable graphs. We prove that the first class induces learning
problems with $\widetilde\Theta(\alpha^{1/2} T^{1/2})$ minimax regret, where
$\alpha$ is the independence number of the underlying graph; the second class
induces problems with $\widetilde\Theta(\delta^{1/3}T^{2/3})$ minimax regret,
where $\delta$ is the domination number of a certain portion of the graph; and
the third class induces problems with linear minimax regret. Our results
subsume much of the previous work on learning with feedback graphs and reveal
new connections to partial monitoring games. We also show how the regret is
affected if the graphs are allowed to vary with time.

研究在线学习问题中的反馈问题，证明反馈图的结构控制引起的学习难度，并给出了三个类别的反馈图的理论极限表现和影响。