  This work proposes a procedure for designing algorithms for specific adaptive
data collection tasks like active learning and pure-exploration multi-armed
bandits. Unlike the design of traditional adaptive algorithms that rely on
concentration of measure and careful analysis to justify the correctness and
sample complexity of the procedure, our adaptive algorithm is learned via
adversarial training over equivalence classes of problems derived from
information theoretic lower bounds. In particular, a single adaptive learning
algorithm is learned that competes with the best adaptive algorithm learned for
each equivalence class. Our procedure takes as input just the available
queries, set of hypotheses, loss function, and total query budget. This is in
contrast to existing meta-learning work that learns an adaptive algorithm
relative to an explicit, user-defined subset or prior distribution over
problems which can be challenging to define and be mismatched to the instance
encountered at test time. This work is particularly focused on the regime when
the total query budget is very small, such as a few dozen, which is much
smaller than those budgets typically considered by theoretically derived
algorithms. We perform synthetic experiments to justify the stability and
effectiveness of the training procedure, and then evaluate the method on tasks
derived from real data including a noisy 20 Questions game and a joke
recommendation task.
