Active learning with strong and weak labelers considers a practical setting
where we have access to both costly but accurate strong labelers and inaccurate
but cheap predictions provided by weak labelers. We study this problem in the
streaming setting, where decisions must be taken \textit{online}. We design a
novel algorithmic template, Weak Labeler Active Cover (WL-AC), that is able to
robustly leverage the lower quality weak labelers to reduce the query
complexity while retaining the desired level of accuracy. Prior active learning
algorithms with access to weak labelers learn a difference classifier which
predicts where the weak labels differ from strong labelers; this requires the
strong assumption of realizability of the difference classifier (Zhang and
Chaudhuri,2015). WL-AC bypasses this \textit{realizability} assumption and thus
is applicable to many real-world scenarios such as random corrupted weak labels
and high dimensional family of difference classifiers (\textit{e.g.,} deep
neural nets). Moreover, WL-AC cleverly trades off evaluating the quality with
full exploitation of weak labelers, which allows to convert any active learning
strategy to one that can leverage weak labelers. We provide an instantiation of
this template that achieves the optimal query complexity for any given weak
labeler, without knowing its accuracy a-priori. Empirically, we propose an
instantiation of the WL-AC template that can be efficiently implemented for
large-scale models (\textit{e.g}., deep neural nets) and show its effectiveness
on the corrupted-MNIST dataset by significantly reducing the number of labels
while keeping the same accuracy as in passive learning.

文章提出了一种名为 WL-AC 的新型算法模板，该模板可以利用低质量的弱标注器来减少查询复杂性，同时保持所需的准确度水平。通过绕过实现假设，WL-AC 适用于许多现实世界的情况，包括随机损坏的弱标签和高维度家族的区别分类器。在经验上，我们提出了一种 WL-AC 的实现，可以在保持与被动学习相同的准确度的情况下，显著降低标签数量。

可扩展弱标注主动学习的改进自适应算法

Improved Adaptive Algorithm for Scalable Active Learning with Weak Labeler

Contextual bandit learning is a reinforcement learning problem where the
learner repeatedly receives a set of features (context), takes an action and
receives a reward based on the action and context. We consider this problem
under a realizability assumption: there exists a function in a (known) function
class, always capable of predicting the expected reward, given the action and
context. Under this assumption, we show three things. We present a new
algorithm---Regressor Elimination--- with a regret similar to the agnostic
setting (i.e. in the absence of realizability assumption). We prove a new lower
bound showing no algorithm can achieve superior performance in the worst case
even with the realizability assumption. However, we do show that for any set of
policies (mapping contexts to actions), there is a distribution over rewards
(given context) such that our new algorithm has constant regret unlike the
previous approaches.

本研究探讨了一种基于可实现性假设下的上下文强化学习问题，并提出了一种新算法 —— 回归器消除，证明了其在保证可实现性前提下，也具有与不可实现性假设情况相似的遗憾率；同时在任意一组策略的情况下，我们证明了本算法具有恒定遗憾，相对于之前的方法而言。