Learning to Actively Learn: A Robust Approach
Authors: Jifan Zhang
Kevin Jamieson
Venue:  (2021)
Keywords: Active Learning
Adversarial Learning
Bandit Algorithms
Meta-Learning

Abstract: 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.

Under review as a conference paper at ICLR 2021
LEARNING TO ACTIVELY LEARN: A ROBUST AP- PROACH
Anonymous authors Paper under double-blind review
ABSTRACT
This work proposes procedure for designing algorithms for specific adaptive data collection tasks like active learning and pure-exploration multi-armed ban- dits. 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 adap- tive 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 per- form synthetic experiments to justify the stability and effectiveness of the training procedure, and then evaluate the method on tasks derived from real data including noisy 20 Questions game and a joke recommendation task.
INTRODUCTION
Closed-loop learning algorithms use previous observations to inform what measurements to take next in a closed-loop in order to accomplish inference tasks far faster than any fixed measurement plan set in advance. For example, active learning algorithms for binary classification have been proposed that under favorable conditions require exponentially fewer labels than passive, random sampling to identify the optimal classifier (Hanneke et al. 2014). And in the multi-armed bandits literature, adaptive sampling techniques have demonstrated the ability to identify the "best arm" that optimizes some metric with far fewer experiments than a fixed design (Garivier & Kaufmann| [016] Fiez et al. 2019). Unfortunately, such guarantees often either require simplifying assumptions that limit robustness and applicability, or appeal to concentration inequalities that are very loose unless the number of samples very large (e.g., web-scale).
The aim of this work is framework that achieves the best of both worlds: algorithms that learn through simulated experience be as effective as possible with a tiny measurement budget (e.g.. 20 queries), while remaining robust due to adversarial training. Our work fits into a recent trend sometimes referred to learning to actively learn (Konyushkova et al. 2017 Bachman al. 2017 Fang et al. 2017, Boutilier et al.) 2020 Kveton et al., (020)) which tunes existing algorithms or learns entirely new active learning algorithms by policy optimization. Previous works in this area learn policy by optimizing with respect to data observed through prior experience (e.g., meta- learning or transfer learning) or an assumed explicit prior distribution of problem parameters (e.g. the true weight vector for linear regression). In contrast, our approach makes no assumptions about what parameters are likely to be encountered at test time, and therefore produces algorithms that do not suffer from potential mismatch of priors. Instead, our method leams a policy that attempts to mirror the guarantees of frequentist algorithms with instance dependent sample complexities: if the problem is hard you will suffer large loss, if it is easy you will suffer little.

---

Under review as a conference paper at ICLR 2021
The learning framework is general enough to be applied to many active learning settings of interest and is intended to be used to produce novel and robust high performing algorithms. The difference is that instead of hand-crafting hard instances that witness the difficulty of the problem, use adver- sarial training inspired by the robust reinforcement learning literature to automatically train minimax policies. Embracing the use of simulator allows our learned policies to be very aggressive while maintaining robustness. Indeed, this work is particularly useful in the setting where relatively few rounds of querying can be made, where concentration inequalities of existing algorithms are vacu- ous. To demonstrate the efficacy of our approach we implement the framework for the (transductive) linear bandit problem. This paradigm includes pure-exploration combinatorial bandits (e.g., shortest path, matchings) as special case which itself reduces to active binary classification. We empirically validate our framework on a simple synthetic experiment before turning our attention to datasets de- rived from real data including noisy 20 questions game and joke recommendation task.
2 PROPOSED FRAMEWORK FOR ROBUST LEARNING TO ACTIVELY LEARN
Whether learned or defined by expert, any algorithm for active learning can be thought of as a policy from the perspective of reinforcement learning. At time 4, based on an internal state 8t. the policy takes action z; and receives observation yt, which then updates the state and the process repeats. In our work, at time the state 8t E S is a function of the history {(I,, })] such as its sufficient statistics. Without loss of generality, policy æ takes state input and defines a probability distribution over X' so that at time we have It ~ (8t). Fix a horizon T. For t 1,2....,T
state 8, E - is a function of the history, {(a 91) M=
action Si X is drawn at random from the distribution क (sc) defined over X, and next state 81+1 E S is constructed by taking action &2 in state 8t and observing yt ~ f'(100, 8t, xx)
until the game terminates time T and the policy receives loss L.- Note that L. is a random variable that depends on the tuple (T, {(T; y4) v;) ) 0.). We assume that f is distribution of known parameteric form to the policy (e.g., f[|10 s, = ((((2, 0), 1)) but the parameter is unknown to the policy. Let P 7,0, E,,0 denote the probability and expectation under the probability law induced by executing policy ı in the game with 6₂ to completion. Note that IP,, T, includes any internal randomness of the policy π and the random observations y/ s((10, 8t, .x). Thus, Pr.0 assigns probability to any trajectory {x;; {x;;, } For a given policy and 0_ 0, the metric of interest we wish to minimize is the expected loss ((TT, 0) == E,,0 [Lr]] where Lr as defined above is the loss observed at the end of the episode. For a fixed policy π. ((x, 0) defines a loss surface over all possible values of 0. This loss surface captures the fact that some values of 0 are just intrinsically harder than others, but also that policy may be better suited for some values of 0 versus others.
Example: In active binary classification, T label budget, X' could be a set of images such that can query the label of example image 2, E X, Yt {-1, is the requested binary label, and the loss LT is the classification error of a trained classifier on these collected labels. Finally, Og ply = 1[x:) for all x E X. More examples
can be found in Appendix A
Rerfomance Hoower is bettor)
arginf, zte 8n") Indespendent baseline)
(min-gap optimal)
acceptable policy, not min-gey optimel
2.1 INSTANCE DEPENDENT PERFORMANCE METRIC
12 = argint, din. ohij
100 6i) sidlish
We now define the sense in which wish to evaluate a particular policy. For any fixed value of 0 one could clearly design an algorithm that would maximize perfor- mance on 0, but then it might have very poor performance on some other value 0' * Thus, we would ideally like to perform uniformly well over set of 0's that are all equivalent in a certain sense. Define a positive function C: θ - (0, oo) that assigns a score to each 0 E θ that intuitively captures the "difficulty" of a particular 8, and can be used as a partial ordering of O. Ideally, C(0) is monotonic transformation of É( 8) for some "best" pol- icy से that we will define shortly. We give the explicit C())
(Difcuity)
Figure 1: The r-dependent baseline defines a different policy for each value of r, thus, the blue curve may be unachievable with just a single policy. w. is the single policy that minimizes the maximum gap to this r- dependent baseline policy.
2

---

Under review as a conference paper at ICLR 2021
for the active binary classification example in Section 3 further description of in Section 2.2. and more examples in Appendix A, For any set of problem instances define
{( θ)
sup { 0).
8E8
And for any 2 0, define
( C()) Sr).
The quantity f(TT, 0(r)) - inf <(T' 0(1) ) is then function of that describes the sub-optimality gap of a given policy π relative to an r-dependent baseline policy trained specifically for each r. For fixed N% > 0, a policy that aims to minimize just {(TT, ((7) might focus just on the hard instances (i.e.. those with C(0) close to r) and there may exist different policy x' that performs far better than æ easier instances (i.e., those with C(0) < r). To avoid this, assuming sup, f(TT, ((1)) inf, E(T', (())) < oc, we define
T. == arg inf sup (((T, (()) inf E(T', ((1)) r>0
x'
as the policy that minimizes the worst case sub-optimality gap over all r O. Figure illustrates these definitions. Instead of computing inf, f(=', ((r)) for all r, in practice we define a grid with an increasing sequence {r to find an approximation T.. We are now ready state the goal of this work:
Objective: Given an increasing sequence rı ... < rk that indexes nested sets of problem instances of increasing difficulty, ((r)) ((ra) c... ( we wish identify policy â that minimizes the maximum sub-optimality gap with respect to this sequence. Explicitly, we seek to learn
म := arginf max (((T, ((r))) ASK
- inf l(T', ( x²'
(2)
where ((T, 0) == sup (( 8) and E(T, 0) is the expected loss incurred by policy и on instance A. o
Note that as K + oo and supk Th+11 + 1. I and 2 are essentially equivalent under benign smoothness conditions C(O), in which case 7 - Te. In practice, choose a finite K where rxx contains all problems that can be solved within the budget T relatively accurately, and a small 0, where max; Fkil + e. Furthermore, the objective in (2) is equivalent with
arginf max ASK
(((TT, ((+x)) E(TR, ((()))
where Thk E arg inf sup (.C(0)sr
E(m, 0).
We can efficiently solve this objective by first computing ne for all ls E [K] to obtain [(T,, ((r))) benchmarks, and then use these benchmarks to train R.
2.2 PICKING THE COMPLEXITY FUNCTION C(O)
We have defined an optimal policy in terms of a function C(f) that determines a partial ordering over instances 0. This function can come from heuristic that intuitively captures the difficulty of an instance. Or it can be defined and motivated from information theoretic lower bounds that often describe general ordering, but are typically very loose relative empirical performance. For ex- ample, consider the standard mulli--rmed bandit game where an agent has access to K distributions and in each round [T] she chooses a distribution I [K] and observes a random variable in [0, with mean 1,.. If her strategy is described by policy I,, once reaches T she receives loss Lr = maxie(K) (K)) DT 0, 0,-0,, with expectation {(T, 0) E[ where the expectation is taken with respect to the randomness in the observations, and potentially any randomness of the policy. Under benign conditions, it known that any policy must suffer E( 0) Z min(VK7 Eiye (0_ (0.-0.000))) 0,)
where 8. = max;e[M] 0 (Lattimore & Szepesvári, 2018). Such a lower bound is an ideal candi- date for C(#). We define a different C(#) for our particular experiments interest, and others are described in Appendix A The bottom line is that any function C(Ø) works, but if it happens to cor- respond to an information theoretic lower bound, the resulting policy will match the lower bound it is achievable.
3

---

Under review as a conference paper at ICLR 2021
2.3 DIFFERENTIABLE POLICY OPTIMIZATION
The first step in learning the policy मे defined in Equation 2 is to learn each T inf, Su)): ((T,0) for all k 1,..., K. Once all Th defined, ß of (2) is optimiza- tion of the same form after shifting the loss by the scalar AT,, ((r))). Consequently, to learn म suffices develop training procedure solve inf, supsen El (π, 0) for an arbitrary Q and generic loss function E' (TT,
To make the optimization problem inf, supoen ('( 0) tractable, we parameterize it follows. First, to compute the suprema over θ we consider a finite set é = {0:] C Ω weighted by SOFTMAX (w) where w R. addition, instead of optimizing over all possible policies, we restrict the policy as the class of neural networks that take state representation input and output probability distribution over actions, parameterized by weights vb. Mathematically, could be stated the following:
inf sup E 0) = inf sup max ((T, 0.) 0E
(3)
Cn ie[N]
inf
sup
SOFTMAXX)) (((T, B:))
(4)
WERN C
2 inf
sup
SQ [
(5)
WERK OLNNC CR
Algorithm 1: Gradient Based Optimization of (5)
Input: partition Ω, number of iterations Na.- number of problem samples M. number of
rollouts per problem L, and loss variable LT at horizon (see beginning of Section 2
Goal: Compute the optimal policy arginf, supsen {(TT, 0) arginf, supsen LE, |
Initialization: w, finite set é and vp
for f. 1, 1,..., N₂ do
Collect rollouts of play:
Sample M problem indices 4I,...,Ix, IM i.i.d. SOFTMAX(w)
for 1, 1.,, M do
Collect independent rollout trajectories, denoted Tm,1:L, by the policy n for problem instant f),, and observe losses V1 < 1 S L, LT Tm.d 11m))
end
Optimize worst cases in Ω:: Update the generating distribution by taking ascending steps on gradient estimates:
11
M
1
f- +
V w (SFFTMA((W)))))
LT( Tm, Or..))
(6)
ML
12
M
1
V Vo (0r., 22 V V (1T Tm,li 0mml)0mm)
ML
+ LT Tm,,, 0r..) )- V (Pg((P x B, (Tm.i))
where Lounter is differentiable barrier loss that heavily penalizes the θ, 's outside Ω.
12 Optimize policy: Update the policy by taking descending step on gradient estimate:
13
M
LT(TV Tm,,, Orm)) V log(P, x x0, (Tmi))
(8)
ML m=
1=1
end
Note that the objectives in 3 and 4 are indeed equivalent as 0 are free parameters we optimize rather than taking fixed values. Now, motivate ( starting from the left hand side of 3
4

---

Under review as a conference paper at ICLR 2021
observe that small change in may result in a large change in argsupeeq 0). Therefore, with the goal of covering the entire Ω2 we optimize the N points so that when a changes a bit, there is at least one 0; close to the optimal argsup. In addition, to covering the entire space of Ω, N is expected to be very large in practice. However, to optimize the objective effectively, we can only evaluate on of f's (M < N) in each iteration. Therefore, instead of naively sampling M points uniformly at random from the N points, in ( we optimize an extra multinomial distribution, SOFTMAX w)) over the N points so that the points around the argsup are sampled more often. The final approximation in (5) comes from parameterizing the policy by a neural network.
To solve the saddle point optimization problem in (5), we use an instance of the Gradient Descent Ascent (GDA) algorithm shown in Algorithm I The gradient estimates are unbiased estimates of
the true gradients with respect to t. w and Ô (shown in Appendix B) We choose N large enough to avoid mode collapse, and M, L. as large as possible to reduce variance in gradient estimates while fitting the memory constraint. We use Adam optimization (Kingma & Ba 2014) in taking gradient updates and regularize some of the parameters (an example will be presented in the next section).
Note the decomposition for log(F T (T)) in and g where rollout
(e),, and
log(P,* nt or (f(2e, Ue) ve)) = log (x11
f ((
II T (st, f 10", 21)
Here x and f are only dependent on sb and θ respectively. During evaluation of a fixed policy n, we are interested in solving supeen ((T,, 0) by gradient ascent updates like 77. The decoupling of T and thus enables us to optimize the objective without differentiating through a policy オ, which could be differeferent policies like deterministic algorithms.
Finally, we make a few remarks on the parameterization of (5). As given in 5 we represent the gen- erating distribution P simple finite number of weighted particles, analogous to particle filter. Our policy parameterization T could modelled by multi-layer perceptrons, recurrent neural net- works, etc. We note that when using alternative generator parameterization like GANs (Goodfellow eet al. 2014), an unbiased gradient can also be derived similarly.
3
IMPLEMENTATION FOR LINEAR BANDITS AND CLASSIFICATION
We now apply the general framework of the previous section to a specific problem: transductive linear bandits. As described in Sections 3 and Appendix [ this setting generalizes standard multi- armed bandits, linear bandits, and all of binary classification through simple reduction to combi- natorial bandits. We are particularly motivated to look at classification because the existing agnostic active learning algorithms very inefficient (see Section 5). Indeed when applied to setting of = 20 they never get past their first stage of uniform random sampling. Consider the game:
Input: Policy n, X' C Rdd 2 C IRd, time horizon T E T Initialization: Nature chooses 0, Rd (hidden from policy) for t t= 1.2....,
Policy æ selects x, E X' using history ((x,, (x),,,)))]=1
Nature reveals 1/- ~ J'(10,, vr,) with E[y, 20. (x,, 0.)
Output: Policy π recommends 2 E Z as an estimate for 2 (B.) = 522,,, and
suffers loss LT (z (0.) 2, 0-) if SIMPLE REGRET
[1 (0.) # 8} if BEST IDENTIFICATION
The observation distribution f((-10,a) . is domain specific but typically taken to be either a Bernoulli distribution for binary data, Gaussian for real-valued data. We are generally interested in two objectives: BEST IDENTIICATION which attempts to exactly identify the vector x* E Z that is most aligned with 0., and SIMPLE REGRET which settles for approximate maximizer.
Defining C(#) Recalling the discussion of Section 2.1 C(9) should ideally be monotonically in- creasing in the intrinsic difficulty of minimizing the loss with respect to a particular 8. For arbitrary X C. 2d and Z C Rdd it is shown in Fiez et al. (019 that the sample complexity of identify- ing (0) arg maxxe (2, 0) with high probability is proportional quantity px (0), the value
5

---

Under review as a conference paper at ICLR 2021
obtained by optimization program. Another complexity term that appears in the combinatorial
bandits literature (Cao & Krishnamurthy 2017) where X' = {er e [d] and 2 C 10.11
|| 20)
((0)
max 2:2, #2 (8) (z 2 (0)
(9)
One can show (0) < ((0) and in many cases track each other. Because (0) be computed much more efficiently compared to (0), we use C(0) = p(() in our experiments.
Algorithm 2: Training Workflow
Input: sequence {r complexity function C, and obj E (SIMPLE REGRET, BEST IDENTIFICATION]
Define k(() E [K] such that (1 < C(0) I r for all with C(0) I TK
For each E [K], obtain policy Hy by Algorithm with Ω = (mx) and SIMPLE REGRET loss
if obj is SIMPLE REGRET then
For each E [K]. compute l(TR, rk) // In this case, T = Tg.
Warm start π = π K/2j optimize मे by Algorithm with Ω = ( and objective in (2).
i.e., Lr (0) 2, 8) ((T (TROO))
else if obj is BEST IDENTIFICATION then
For each & E [K], warm start ग& Ty. optimize Ty by Algorithm | with Ω (rr)) and
BEST IDENTIFICATION loss; compute {(TE, ((x))
Warm start γ7 [[K/2] optimize by Algorithm with Ω (fxx) and objective in (2).
i.c. LT = 1 (0) 2} 100---(-a (TT()) (+(())))
10 end Output: î (an approximate solution to
Training. When training our policies, we follow the following procedure in Algorithm Note that when training for BEST IDENTIFICATION, optimizing SIMPLE REGRET. This is because a random initialized policy performs so poorly that BEST IDENTIFICATION nearly always 1, making it difficult to improve the policy. In addition, our generating distribution parameterizations exactly follows from Section 2.3 while detailed state representations, policy parametrization and hyperparamters can be found in Appendix C
still warm start the training with
Loss functions. Instead of optimizing the approximated quantity from (5) directly, we add regu- larizers the losses for both the policy and generator. First, we choose the Coartier 7 to be Aburrier max(0, log(C(XX, Z, 0)) log(rr)), for some large constant Abarrier To discourage the pol- icy from over committing small subset of particles (i.e.. mode collapse), we also add negative entropy penalties to both policy's s output distributions and SOFTMAX(w)) with scaling factors Xpot-reg and AGen-reg-
certain action and/or the generating distribution from covering only
EXPERIMENTS
We now evaluate the approach described the previous section for combinatorial bandits with X' = (e; i [d] and 2 1)d. We stress that the framework implemented here can be applied to any X, 2 C IRd and any appropriate f-just plug and play to learn a new policy. In our experiments we take particular instances of combinatorial bandits with Bernoulli observations. We evaluated based on two criterion: instance-dependen worst-case and average-case. For instance- dependent worst-case, we measure, for each and policy म, ((T)) = max {(T, #) and
oEe(rk)
plot this value as a function of rı- We note that our algorithm designed to optimize for such metric. For the secondary average-case metric, we instead measure, for policy æ and some collected set O Epee ((T,, 8). Performances of instance-dependent worst-case metric are reported in Figures 6 and below while the average case performances are reported in the tables and Figure
Full scale of the figures also be found in Appendix F

---

Under review as a conference paper at ICLR 2021
Algorithms. We compare against a number of baseline active learning algorithms (see Section for a review). UNCERTAINTY SAMPLING at time computes the empirical maximizer of (2, 0) and the runner-up, and samples an index uniformly from their symmetric difference; if either are not unique, an index is sampled from the region of disagreement of the winners (see Appendix G for details). The greedy methods are represented by soft generalized binary search (SGBS) (Nowak) 2011] which maintains a posterior distribution over 2 and samples to maximize information gain. A hyperparameter 3 E (0, 1/2) of SGBS determines the strength of the likelihood update. We plot or report a range of performance over / E {.01, .0,, 11, .2, .3, .4). The agnostic algorithms for classification (Dasguptal 2006 Hanneke| 2007b a Dasgupta et al. 2008 Huang et al. 2015 Jain &
Jamieson 2019) or combinatorial bandits (Chen et al. 2014 Gabillon et al., [016) Chen et al., 2017
Cao & Krishnamurthy 2017: Fiez et al. 2019 Jain & Jamieson 2019) are so conservative that given
just T = 20 samples, they are all exactly equivalent to uniform sampling and hence represented by
UNIFORM. To represent policy based on learning actively learn (LAL), we employ the method
of Kveton al. (020) with fixed prior P constructed by drawing a uniformly at random from 2 and defining 6 = 2z - E [-1, 1] (details in Appendix [H.. When evaluating each policy, we use the successive halving algorithm (Li et al. [017]] 2018) for optimizing our non-convex objective
with randomly initialized gradient descent and restarts (details in Appendix B
Thresholds. We begin with a very simple instance to demonstrate the instance-dependent performance achieved by our learned policy. For d = 25 let = {e, : [4]. 2 = {o + >>
Cap 191 sup al 12 moue
12
15
11 C, : k 0. d), and S(-00, . is a Bernoulli distribu- tion over {-1,1) with mean (xr 0) [-,,1]. Note this is a binary classi- fication task in one-dimension where the set of classifiers are thresholds on line. We trained baseline policies {Tx)) )==1 for the BEST IDENTIFICA- TION metric with C(O) = ((X 0) and rk= 23+1/2 for i E (0..... 80. 8).
Eyduro
120
20
60
386
120
Figure 3: Sub-optimality of Figure 2: Learned policies, individual policies, lower is lower is better
better
100
42
First we compare the base poli- cies Thk to a. Figure 2 presents (I, supo:a0))r ((T,0) (0)) P P2, # (0)) as function of for base policies {T h and the global policy n., each as individual curve. Pigut the same information in terms of gap: {(TT, (())
Sctt, vertous
33
n.(0knd) Unitrm
Uncertaiiy
20
ndependent bastrre
30
LAL
LAL
20
42
50
100
120
85
0.6
07
0.8
09
16
Figure 4: Max {0 ((0) < Figure 5: Average Ea-p, I.]
r). lower is better
lower is better
min ( We observe that each Ser Th performs best in a particular region and т. performs almost as well as the r-dependent baseline policies over the range of This plot confirms that our optimization objective of (2) was successful. Under the same conditions as Figure 2 Figure 4 compares the performance of x. to the algorithm benchmarks. Since SGBS and LAL are deterministic. the adversarial training finds a that tricks them into catastrophic failure. Figure traddes adversarial evaluation for evaluating with respect to a parameterized prior: For each E {0.5, 0.6, ..... 1}. ~ Pr. is defined by drawing z uniformly at random from 2 and then setting 0g = (2z, 1)(2a; 1) where o; ~ Bernoulli(h). Thus, each sign of 2 is flipped with probability h. We then compute Eg- e = z, (0)) = Ee-,,, [k(T, 0)]. While SGBS now performs much better than uniform and uncertainty sampling, our policy π. is still superior to these policies. However, LAL is best overall which is expected since the support of Ps. is basically& rescaled version of the prior used in LAL.
20 Questions. We now address an instance constructed from the real data of Hu et al. 2018 Summarizing how we used the data from Hu et al. (2018) (see Appendix for details), 100 yes/no questions were considered for 1000 celebrities. Fach question i E [100) for each person j E [1000]
was answered by several annotators to construct an empirical probability of E [0, 1] denoting the
7

---

Under review as a conference paper at ICLR 2021
proportion of annotators that answered "yes." To construct our instance, take X' fe; E [100]} and Z = {20); : [ = 16p > 1/2]] C {0, 1 1o Just as before, we trained {
for the BEST IDENTIFICATION metric with ((0) = p(x, 2, 0) and r. = 23+/22 for i E {l,...,, 4].
Figure analogous to Fig- ure but for this 20 questions instance. Uncertainty sampling performs remarkably well on this instance. potential explana- tion is that on a noiseless instance (e.g., 8 2% for some 2 E Z), our implementation of uncer- tainty sampling
Table 1: Average Bewp!)
Eror 150 Po Pt.00=..00
103
93
Method x (Ours)
Accuracy (%)
17.9
(0uis)
5665, varouss 8
SGBS
(26.5,
Lister
27.2, 26.5,
ridependert be
21.4, 12.8]
Uncertainty
14.3
22
equivalent to CAL (Cohn et al.] 1994) and is known to have near-optimal sample complexity (Hanneke et al. 2014). Uncertainty sampling even
LAL
4.1
Figure 6: Max :0: <r)
Uniform
6.9
outperforms our r-dependent baseline by a bit which in theory should not occur-we conjecture this is due to insufficient convergence of our policies or local minima. Our second experiment constructs a distribution P based on the dataset: to draw a 0 ~ P we uniformly at random select a E [1000] and sets 02 -p
for all i [d]. As shown in Table SGBS and т. are the winners. LAL performs much worse in this case, potentially because of the distribution shift from P (prior we train on) to P (prior at test time). The strong performance of SGBS may be due to the fact that (ig)(0;) = (0); 1 for all i and 0 ~ P, realizability condition under which SGBS has strong guarantees (Nowak) 2011).
Jester Joke Recommendation We now turn our attention away from best identification of the last two experiments {(TT, 0) = F2 # z. (0)). to simple gret ((TT = (=,0 2, 0. We consider the Jester jokes dataset of Goldberg et al. (200I) that contains jokes rang- ing innocent puns to grossly of- fensive jokes. We filter the dataset to only contain users that rated all 100 jokes, resulting in 14116
Table 2: Average E. [|]
-.40
Method
Average Regret
x (Ours)
3.209
5083. varius
SGBS
{3.180, 3.224,
Rogret,
Unoa aiifr
Unitom
3.278, 3.263,
rdspendert
3.153, 3.090]
Uncertainty
3.027
LAL
3.610
Figure 7: Max {0 p()
Sr)
Uniform 3,877
users. A rating of each joke was provided on [-10, 10] scale which was rescaled to [-1, 1] and observations were simulated as Bernoulli's like above. We then clustered the ratings of these users (see Appendix D for details) 10 groups to obtain Z (2(1) k E [10], (k) E [0,1]1100 1000 where (k) = corresponds to recommending the ith joke in user cluster 2(k) E Z. Figure 7 shows the same style plot as Figures 46 but for this jokes dataset, with our policy alone nearly achieving the r-dependent baseline for all r. Mirroring the construction of the 20Q prior, we construct P by uni- formly sampling a user and employing their 0 to answer queries. Table 2 shows that despite our policy not being trained for this setting, its performance is still among the top.
RELATED WORK
Learning to actively learn. Previous works vary in how the parameterize the policy, ranging from parameterized mixtures of existing expertly designed active learning algorithms (Baram al. 2004
Hsu & Lin 2015 Agarwal et al.) 2016). parameterizing hyperparameters (e.g.. learning rate, rate of forced exploration, etc.) in an existing popular algorithm (e.g, EXP3) (Konyushkova et al. 2017
Bachman et al., 3017//elle et al.
2020). and the most ambitious, policies parameterized end-to-end
2020 Kveton et al. 2020, (hharf & Daumé III 2019) Fang et al.) 2017 Woodward & Finn 2017).
like in this work (Boutilier et al.
These works take an approach of defining prior distribution either through past experience (meta-learning) or expert created (e.g., 0 ~ (0, Σ)), and then evaluate their policy with respect to this prior distribution. Defining this prior can be difficult, and moreover, if the encountered at test time did not follow this prior distribution, performance could suffer significantly. Our approach, on the other hand, takes an adversarial training approach and can
8

---

Under review as a conference paper at ICLR 2021
be interpreted as learning parameterized least favorable prior (Wasserman 2013), thus gaining much more robust policy as an end result.
Our work is also highly related to the field of robust and safe reinforcement learning, where our objective can be considered as an instance of minimar criterion under parameter uncertainry (Gareıa & Fernández 2015). Widely applied in applications
Robust and Safe Reinforcement Learning:
such as robotics (Mordatch et al. [2015] Rajeswaran et al.) 2016). these methods train a policy in a simulator like Mujoco (Todorov et al.) 2012) to minimize defined loss objective while remaining robust to uncertainties and perturbations to the environment (Mordatch et al. 2015: Rajeswaran al., 2016). Ranges of these uncertainty parameters are chosen based on potential values that could be encountered when deploying the robot in the real world. In our setting, however, defining the set of environments is far less straightforward and is overcome by the adoption of the C(0) function.
Active Binary Classification Algorithms. The literature on active learning algorithms can be partitioned into model-based heuristics like uncertainty sampling, query by committee, or model- change sampling (Settles (2009), greedy binary-search like algorithms that typically rely form of bounded noise for correctness (Dasguptal 2005; Kääriäinen, 2006 Golovin & Krause 2011 Nowak (01T), and agnostic algorithms that make assumptions on the probabilistic model (Das-) gupta 2006 Hanneke, 2007b at Dasgupta et al., 2008; Huang et al., 2015; Jain & Jamieson 2019).
Though the heuristies and greedy methods can perform very well for some problems, is typically easy to construct counter-examples (e.g., outside the assumptions) in which they catastrophically fail (as demonstrated in our experiments). The agnostic algorithms have strong robustness guaran- tees but rely on concentration inequalities, and consequently require at least hundreds of labels to observe any deviation from random sampling (see Huang al. (2015) for comparison). Therefore, they were not included in our experiments explicitly but were represented by uniform.
Pure-exploration Multi-armed Bandit Algorithms. In the linear structure setting, for sets 2, C Rd known to the player, pulling an "arm" x E X results in an observation (z, 0z)+ zero- mean noise, and the objective is to identify arg max,e 222, 0_) for a vector 02 unknown to the player (Soare et [014] Karnin 2016 Tao et al., 2018 Xu et al. 2017 Fiez et al., 2019). A special case of linear bandits combinatorial bandits where
d and 2 C {0. 1) (Chen al., Gabillon et al.) 2016 Chen et al.] 2017, Cao & Krishnamurthy, 2017 Fiez et al.) 2019 Jain & Jamieson 2019). Active binary classification is a special case of combinatorial pure-exploration multi-armed bandits (Jain & Jamieson] 2019), which we exploit in the threshold experiments. While the above works have made great theoretical advances in deriving algorithms and information theo- retic lower bounds that match up constants, the constants are so large that these algorithms only behave well when the number measurements is very large. When applied to the instances of our paper (only 20 queries are made), these algorithms behave no differently than random sampling.
DISCUSSION AND FUTURE DIRECTIONS
We see this work exciting but preliminary step towards realizing the full potential of this general approach. From a practical perspective, training a т. can take many hours of computational resources for even these small instances. Scaling these methods larger instances is an important next step. While training time scales linearly with the horizon length T, we note that one can take multiple samples per time step with minimal computational overhead enabling problems that require larger sample complexities. In our implementation we hard-coded the decision rule for 2 given 8T, while it could also be learned as in (Luedtke et al., 2020). Likewise, the parameterization of the policy and generator worked well for our purposes but was chosen somewhat arbitrarily-are there more natural choices? Finally, while we focused on stochastic settings, this work naturally extends to constrained fully adaptive adversarial sequences which is an interesting direction of future work.

---

Under review as a conference paper at ICLR 2021
FUNDING DISCLOSURE
Removed for anonymization purposes.
ACKNOWLEEDGEMENT
Removed for anonymization purposes.
REFERENCES
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a bandit algo- rithms. arXiv preprint arXiv:1612.06246, 2016.
VM Aleksandrov, VI Sysoyev, and SHEMENEV. VV. Stochastic optimization. Engineering Cybernetics, (5): 11+t, 1968.
Philip Bachman, Alessandro Sordoni, and Adam Trischler. Learning algorithms for active learning. In Pro- ceedings of the 34th International Conference Machine Learning- Volume 70, pp. 301-310. JMLR. org, 2017.
Yoram Baram, El Yaniv, and Kobi Luz. Online choice active learning algorithms. Journal of Machine Learning Research, 5(Mar):255 251-2 2004.
Craig Boutilier, Chih Wei Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable bandit exploration. arXiv preprint arXiv:2002.06772 2020.
Tongyi Cao and Akshay Krishnamurthy. Disagreement- combinatorial pure exploration: Efficient algo- rithms and an analysis with localization. star, 2017.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference Learning Theory, pp. 590-604, 2016.
Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. arXiv preprint wxXiv:20050083// 2020.
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly optimal sampling algorithms for combinatorial pure exploration. In Conference on Learning Theory, pp. 482 534, 2017.
Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of
multi-armed bandits. In Advances in Neural Information Processing Systems, pp. 379-387, 2014.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning. 15(2):201 221, 1994.
Sanjoy Dasgupta. Analysis of greedy active learning strategy. Advances neural information processing systems, pp. 337-344, 2005.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Advances in neural information processing systems, pp. 235 235-242, 2006.
Sanjoy Dasgupta, Daniel J Hsu. and Claire Monteleoni. A general agnostic active learning algorithm. In Advances in neural information processing systems, pp. 353-360, 2008.
Meng Fang, Yuan Li, and Trevor Cohn. Learning how active leam: A deep reinforcement learning approach. arXiv preprint arXiv:/70S 02383, 2017.
Tanner Fiez, Lalit Jain, Kevin Jamieson, Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances in Neural Information Processing Systems, pp. 10666-10676, 2019.
Victor Gabillon, Alessandro Lazaric, Mohammad Ghavamzadeh, Ronald Ortner, and Peter Bartlett. Improved learning complexity in combinatorial pure exploration bandits. In Artificial Intelligence and Statistics, 1004-1012, 2016.
Javier Garcia and Fernando Fernández. A comprehensive survey safe reinforcement learning. Journal of Machine Learning Research, 16(1 16(1):1437-1480, 2015.
10

---

Under review as a conference paper at ICLR 2021
Aurélien Garivier and Emilie Kaufmann. Optimal best identification with fixed confidence. In Conference on Learning Theory, pp. 998 198-7027, 2016.
Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. filtering algorithm. information retrieval, 4(2):133-151, 2001.
Eigentaste: constant time collaborative
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-488 2011.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron
Courville, Yoshua Bengio. Generative adversarial nets. In Advances neural information procexs- ing systems, pp. 2672-2680, 2014.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference Machine learning, pp. 353-360, 2007a.
Steve Hanneke. Teaching dimension and the complexity of active learning. In International Conference Computational Learning Theory, pp. 66 81. Springer, 2007b.
Steve Hanneke et Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 122-3):311-309 2014.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in lincar contextual bandit. arXiv preprint 1tt.v::9100066660 2019.
Wei-Ning Hsu and Hsuan- Lin. Active learning by learning. In Twenty-Ninhh AAAI conference on artificial intelligence, 2015.
Huang Hu, Xianchao Wu, Bingfeng Luo, Chongyang Tao, Can Xu, Wei Wu, Zhan Chen. Playing 20 question game with policy-based reinforcement learning. arXiv preprint 1808: 2018.
Tzu-Kuo Huang, Alekh Agarwal, Daniel J Hsu, John Langford, and Robert E Schapire. Efficient and parsi- monious agnostic active learning. In Advances in Neural Information Processing Systems, pp. 2015.
Lalit Jain Kevin Jamicson. new perspective on pool-based active classification and false-discovery control. In Advances in Neural Information Processing Systems, pp. 13992-14003, 2019.
Matti Kääriäinen. Active learning in the non-realizable case. In International Conference on Algorithmic Learning Theory, pp. 63-77. Springer, 2006.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Inter- national Conference on Machine Learning, pp. 1238 1246, 2013.
Zohar S Karnin. Verification based solution for structured mab problems. Advances in Neural Information Processing Systems, pp. 145-153, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
14X1v:1412.69880 2014.
Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua. Learning active leamingg from data. In Advances Neural Information Processing Systems, pp. 4225-4235, 2017.
Branislav Kveton, Martin Mladenov, Chih- Wei Hsu, Manzil Zaheer, Csaba Szepesvari, and Craig Boutilier. Differentiable meta-lcarning in contextual bandits. arXiv preprint arXiv:2006.05090 2020.
Tor Lattimore and Csaba Szepesvari. The end of optimism? asymptotic analysis of finite-armed linear bandits. arXiv preprint 16X1v:1610.04491, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, pp. 28, 2018.
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet 2018.
Talwalkar. Massively parallel hyperparameter tuning. arXiv preprint
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1): 6765-68 16, 2017.
11

---

Under review as a conference paper at ICLR 2021
Alex Luedtke, Marco Carone. Noah Simon, and Oleg Sofrygin. Learning to leam from data: Using deep adversarial learning construct optimal statistical procedures. Science Advances, 6(9), 2020. doi: 10. 10.11 sciadv.aa22140. URL hRtphs/:://aaaaaaa ott.://c....o.oooooooooooo/ooooa http://ttt////////////e/
Shie Mannor and John Tsitsiklis. The sample complexity of exploration multi-armed bandit problem. Journal of Machine Learning Research, 5(Jum):623366) 648, 2004.
Igor Mordatch, Kendall Lowrey, and Emanuel Todorov. Ensemble-cio: Full-bodi boll-body dynamic motion planning that transfers to physical humanoids. In 2015 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5307-5314, IEEE, 2015.
Robert D Nowak. The geometry of generalized binary search. IEEE Transactions on Information Theory, 57 (12):7893-7906 2011.
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration structured reinforcement learning. In Advances in Neural Information Processing Systems, 8874 8882, 2018.
Aravind Rajeswaran, Sarvject Ghotra, Balaraman Ravindran, and Sergey Levine, Epopt: Learning robust neural network policies using model ensembles. arXiv preprint 1r0.01661.00/283, 2016.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin- Department of Computer Sciences, 2009.
Amr Sharaf and Hal Daumé III. arXiv:1901.085 08159, 2019.
Meta-leaming for contextual bandit exploration.
arXiv preprint
Max Simehowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, 1151- 160, 2019.
Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the moderate-confident regime. arXiv preprint arXiv:1702.05122 05786 2017.
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, pp. 828 836, 2014.
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear dimension depen- dency. In International Conference on Machine Learning, 4877-4886, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model- based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026- 5033. IEEE, 2012.
Alexandre B Tsybakov. Introduction to nonparumetric estimation. Springer Science & Business Media, 2008.
Bart Van Parys and Negin Golrezaci. Optimal learning for structured bandits. 2020.
Larry Wasserman. All of statistics: concise course in statistical inference. Springer Science & Business Media, 2013.
Mark Woodward and Chelsea Finn. Active one-shot learning. arXiv preprint arXiv: 2017.
Liyuan Xu, Junya Honda, and Masashi Sugiyama. Fully adaptive algorithm for pure exploration in linear bandits. arXiv preprint arX1::1710005522, 2017.
12

---

Under review as a conference paper at ICLR 2021
A INSTANCE DEPENDENT SAMPLE COMPLEXITY
Identifying forms of (() is not as difficult a task as one might think due to the proliferation of tools for proving lower bounds for active learning (Mannor & Tsitsiklis, 22004; Tsybakov 2008 Garivier & Kaufmann 2016 Carpentier & Locatelli, 2016; Simchowitz et al. 2017 Chen et 2014). One can directly extract values of C(O) from the literature for regret miniiization of linear other structured bandits (Lattimore & Szepesvari! 2016) Van Parys & Golrezaei 2020), contextual bandits (Hao et al.) 2019)), and tabular well as structured MDPs (Simchowitz & Jamieson 2019 Ok et al.) 2018). Moreover, we believe that even reasonable surrogates of C(0) should result in a high quality policy m..
We review some canonical examples:
Multi-armed bandits. In the best-arm identification problem, there are d N Gaussian distri- butions where the ith distribution has mean 0; E R for i = 1,...,d. dd In the above formulation, this problem is encoded as action 24 l results in observation y/: Bernoulli(O.) and the loss ((x, 0) == o [i # (0)) where 7 is r's recommended index and (0) = arg max; 0,. It's been shown that there exists constant eo > 0 such that for any sufficiently large > 0 we have inf sup (0)
{(T 0) 2 exp(-c
where CMAB(O)
Σ (01.(0) - 0.) (t)
TT
Moreover, for any 9 E R there exists policy न that achieves ((T.0) 0) 0j exp( -o CCTT/CMa CM ())
where C1. C2 capture constant and low-order terms (Carpentier & Locatelli 2016 Karnin et al. 2013 [iichowitz al. 2017 Garivier & Kaufmann 2016).
The above correspondence between the lower bound and the upper bound suggests that CMAB plays critical role in determining the difficult of identifying (0) for any 0. This exereise extends to more structured settings as well:
Content recommendation active search. Consider n items (e.g., movies, proteins) where the ith item is represented by a feature vector 3i E X' C Re and a measurement I2 = x; (e.g.. preference rating, binding affinity
target) is modeled as a linear response model such that RR If ((T.. 0) == E,,o i * i, (0))] as above then nearly identical results to that of above hold for an analogous function of (O) (Soare et al.,
yt ~ (Z; 8), 1) for some unknown
2014 Karnin 2016 Fiez et al. 2019).
Active binary classification. For i 1.....d let Φ; E R be feature vector of an unlabeled item (e.g., image) that can be queried for its binary label y/, E {-1,1] where y ~ Bernoulli for some 0 e R. Let H. be an arbitrary set of classifiers (c.g., neural nets, random forest, etc.) such that each h E H assigns a label {-1, to each of the items { in the pool. items are chosen sequentially to observe their labels, the objective is to identify the true risk minimizer (f) arg minnen Ei= (h(o()(o)) # yill using as few requested labels as possible and fh= + (0)}) where E H is T's recommended classifier. Many candi- dates for C(#) have been proposed from the agnostic active learning literature (Dasgupta 2006 Hanneke 2007b a Dasgupta et al., 20088; Huang et al.) 2015] Jain & Jamieson, 2019) but we believe the most granular candidates come from the combinatorial bandit literature (Chen et al.)
((TT,) 0) == Ex, e [1
2017 Fiez et al. 2019 Cao & Krishnamurthy] 2017 Jain & Jamieson 2019). To make the re- duction, for each h E H assign 2h E [0 such that [2 == 1(h(0;) = 1} for all = 1,.....d and set Z = (h)()) h E H}. It is easy to check that 2, (6) := arg max (2, B) satisfies z. (0) = ((), Thus, requesting the label of example i is equivalent to sam- pling from Bernoulli( (e,, 0)) (-1, completing the reduction combinatorial bandits: X {c: : [d], 2 C 1). We then apply the exact same C(0) as above for linear bandits.
B GRADIENT ESTIMATE DERIVATION
Here we derive the unbiased gradient estimates (6. and ( in Algorithm 1 Since each the gradient estimates in the above averages over M L identically distributed trajectories, is therefore sufficient to show that our gradient estimate is unbiased for a single problem 0 and its rollout trajectory ((x,,,))) yr))
13

---

Under review as a conference paper at ICLR 2021
For feasible w, using the ecore-function identity (Aleksandrov et al. 1968
V (oLEA-SOFTMAX(e)) [((TT) " 0.]] (E-SOFFMAX(()) [((TT) 0.) V log (og(SOFFMAX
Observe that i SOFTMAX(w)) ()) and ((te, the result of rolling out a policy Nº on 0, then
gth == Lr(T", (( BOTTE1 V (ogg((OFFMAA(())))
is an unbiased estimate of V V.B.A.SOFTMMA( ((T,, [.3]
For feasible set θ by definition of E (),,)),
Vg SO ((T)) (())
SOA-SOFFMAXX
V VB a. LT((T, (0 v.))
=E, -BA-SOFFMAX((U)
xx VoLr(T (1x,, 30) 0.)
(10)
LT(T, {( Be)) 0.) Vg log(Ip n" 3. (1 Me WED
where the last equality follows from chain rule and the score-function identity (Aleksan- drov al. 1968). The quantity inside the expectations, call it g is then unbiased estimator of SOFBA-SOFTMAX(L)) [((TT, 0.) given i and {(x+,, w:) are rolled out accord- ingly. Note that if Loarrier * O, Vg Coarier (0,, 52) is clearly an unbiased gradient estimator of SO.-SOFTMA((w) ,,,, [Churrier (C0, Ri]] given and rollout sampled accordingly.
Likewise, for policy,
gb == LT(TV, (l.. (.)) k.) log(P, uv, (((T).B)) b())
an unbiased estimate of V SO (((TV) Ø.]
C LINEAR BANDIT PARAMETERIZATION
C. STATE REPRESENTATION
We parameterize our state space S flattened |X' x 3 matrix where each row represents distinct X. Specifically, at time the row of &, corresponding some X' records the number of
times that action x has been taken Et=l 1f2 = x), its inverse (Σi=1 1(x, = x+}-1, and the sum of the observations E
1-1 == 1x, = r/y..
C.2 POLICY MLP ARCHITECTURE
Our policy T is multi-layer perceptron with weights v. The policy take a 3) sized state as input and outputs vector of size |X' which is then pushed through soft-max to create prob- ability distribution over X. the end of game, regardless the policy's weights, we set $ = argmax ,e2 (z, 0) where is the minimum & norm solution to argming Σ (u. - ()).
Our policy network is simple 6-layer MLP, with layer sizes (3 X') 256, 256, 256, 256, (2]) where 3 X corresponds to the input layer and | is the size of the output layer, which is then pushed through Softmax function to create probability over arms. In addition, all intermediate layers are activated with the leaky ReLU activation units with negative slopes of ,01. For the experiments for ID thresholds and 20 Questions, they share the same network structure as mentioned above with | 25 and X 100 respectively.
D HYPER- SYPER-PARAMETERS
In this section, we list our hyperparameters. First we define Apinary to be coefficient that gets multiplied to binary loses, instead of (==(0.) o 2). receive loss Apinary 1( (0.) # 2). We
14

---

Under review as a conference paper at ICLR 2021
choose Abinary that the recieved rewards are approximately the same scale SIMPLE REGRET. During our experiments, all the optimizers are Adam. All budget sizes are T = 20. For fairness of evaluation, during each experiment (ID thresholds 20 Questions), all parameters below are shared for evaluating all of the policies. To elaborate on training strategy proposed in Algorithm more, divide our training into four procedures, as indicated in Table
Init. The initialization procedure takes up a rather small portion of iterations primarily for the purpose of optimizing for Larrier that the particles converge into the constrained difficulty sets. In addition, during the initialization process we initialize and freeze uniform distribution over the particles. This allows us to utilize the entire set of particles without w converge to only a few partieles early on. To initialize θ, we sample 2/3 of the N particles N uniformly from [-1,1]|x| and the rest 1/3 3 of the particles by sampling, for each i E [[ उ particles uniformly from {0 argmax, (0, 2n} i]. We initialize our policy weights by Xavier initialization with weights sampled from normal distribution and scaled by .01.
Ö, thus putting
Regret Training, 7. Training with SIMPLE REGRET objective usually takes the longest among the Procedures. The primary purpose for this process is to let the policy converge reasonable warm start that already captures some essence of the task.
multiple times for each with their corresponding complexity set θ, During each run, we start with warm started policy, and reinitialize the rest of the models by running the initialization procedure followed by optimizing the BEST IDENTIFICATION objective.
Fine-tune π. Training with BEST IDENTIFICATION objective
Fine-tune ग This procedure optimizes 2 with baselines ming ( (r+))) evaluated based on each T. learned from the previous procedure. Similar to fine-tuning each individual Tg, warm start a policy [222 and reinitialize w and θ by running the initialization procedure again.
Experiment
ID Threshold
20 Questions | = 100
Jester Joke | = 100
Procedure
Hyper- parraeee
X 25
N₂:
20000 (all)
? learning rate
10 (all)
Init
+ learning rate
10-3 (all)
w learning rate
0 (all)
Not
480000 (all)
à learning rate
10-4 (all)
Regret Training
learning rate
10-3 (all)
learning rate
10-3 (all)
No
200000 (all)
à learning rate
10-4 (all)
Fine-tune Mi
θ learning rate
10 (all)
w learning rate
10 (all)
N₂
500000
300000
500000
? learning rate
10-4 (all)
Fine-tune ा.
θ learning rate
10 (all)
w learning rate
10 (all)
B B2
.9 (all)
Adam Optimizer
.999 (all)
Table 3: Number of Iterations and Learning Rates
15

---

Under review as a conference paper at ICLR 2021
Experiment
ID Threshold
20 Questions
Jester Joke
Procedure Hyper-parameter
| = 25
[ 100
[X] 100
N
1000 2
300 |
2000
2
M
1000
500
500
30
Init + Train + Fine-tune
Abinary
7.5
30
30
Apol-reg (regret)
.2
.8
Apol-reg (fine-tune)
.3
.8
.8
ren
.05
.05
Abarrier
10 (all)
Table 4: Parallel Sizes and Regularization coefficients
To provide general strategy of choosing hyper- syper-parameters, note that L, firstly, Abinary. Apol-reg are primarily parameters tuned for |X| as the noisiness and scale of the gradients, and entropy over the arms X grows with the size [.8]. Secondly, AGen is primarily tuned for |Z| as it penalizes the entropy over the arms, which is a multiple of |2]. Thirdly, learning rate of A is primarily tuned for the convergence of constraint p" into the restricted class, thus Laariier becoming O after the specified number of iterations during initialization is good indicator. Finally, we choose N and M by memory constraint of our GPU. The hyper-parameters for each experiment was tuned with less than 20 hyper-paue parameter assignments, some metrics to look at while tuning these hyper- parameters includes but are limited to: gradient magnitudes of each component, convergence of each loss and entropy losses for each regularization term (how close it is to the entropy of uniform probability), etc.
E POLICY EVALUATION
When evaluating policy, essentially solving the following objective for fixed policy
max E(TT 0)
BEnt
where 52 is a set of problems. However, due to non-concavity of this loss function, gradient descent initialized randomly may converge to local maxima. To reduce this possibility, we randomly initialize many initial iterates and take gradient steps round-robin, eliminating poorly performing trajectories. To do this with a fixed amount of computational resource, we apply the successive halving algorithm from Li al. (2018). Specifically, we choose hyperparamters: 4, 100,
R 1600 and s = 0. This translates to:
Initialize | 1600, optimize for 100 iterations for each 0, θ
Take the top 400 them and optimize for another 400 iterations
Take the top 100 of the remaining 400 and optimize for additional 1600 iterations
We take gradient steps with the Adam optimizer Kingmaa & Ba 2014) with learning rate 10-3 8 and 32 .999.
16

---

Under review as a conference paper at ICLR 2021
F
FIGURES AT FULL SCALE
Error (%) sup Pn,e( # Z (0)) (:p.(0) sr
80
60
40
l2
I[7
20
T4
n(OOrs)
20
40
60
80
100
120
Figure 8: Full scale Figure
Gap (%) sup Pn,e(2 + z. (0)) - [(TTK(0), ) sr)
25
Th
20
T2
n(OOus)
15
T4
10
5
0
20
40
60
80
100
120
Figure 9: Full scale of Figure
17

---

Under review as a conference paper at ICLR 2021
100
Error (%) sup Pn.e(2 # Z (0)) 0:
80
60
î (Ours)
SGBS, various B Uncertainty Uniform
40
20
r-dependent baseline
LAL
20
40
60
80
100
120
Figure 10: Full scale of Figure
70
Error (%) Eg - P,,Pn, e n + z (()
60
50
40
30
n (Ours)
SGBS, various B
20
Uncertainty
10
Uniform
LAL
0
0.5
0.6
0.7
0.8
0.9
1.0
Figure 11: Full scale of Figure
18

---

Under review as a conference paper at ICLR 2021
100
Error (%) sup Pn.e(2 # 2 (0)) p:
95
90
ît (Ours)
85
SGBS, various B
Uncertainty
80
Uniform
r-dependent baseline
75
LAL
15
20
25
30
Figure 12: Full scale of Figure
>40
(z 1z'(6) (0) 2,
7
Regret sup p:
6
π (Ours)
SGBS, various B Uncertainty Uniform
5
4
3
r-dependent baseline
LAL
2
20
40
60
80
100
120
Figure 13: Full scale of Figure
19

---

Under review as a conference paper at ICLR 2021
G UNCERTAINTY SAMPLING
We define the symmetric difference set of binary vectors, SymDifff (.., 2n3) = {i: 3j, [n] s.t., 23 1 (t) 0), as the dimensions where inconsistencies exist.
Algorithm 3: Uncertainty sampling in very small budget setting
Input: X,
for t 1,.., T do
0111 argming E' (r,;
2 {= : :maxxez('' (2 (z, 01-))
2 1 then
2, = U12 E max max m (2), 00-1) = (2, (2,00-1))
else
2, 2
end
Uniformly sample I, from SymDiff( 2.) Pull F,, and observe Jr
11
12 end
H LEARNING TO ACTIVELY LEARN ALGORITHM
To train a policy under the learning to actively learn setting, we aim to solve for the objective
min p 0)]
where our policy and states are parameterized the same way as Appendix [ for fair comparison. To optimize for the parameter, we take gradient steps like ( but with the new sampling and rollout where 0g ~ P. This gradient step follows from both the classical policy gradient algorithm in reinforcement learning as well as from recent LAL work by Kveton al. 2020).
Moreover, note that the optimal policy for the objective must be deterministic as justified by deter- ministic policies being optimal for MDPs. Therefore, it clear that, under our experiment setting, the deterministic LAL policy will perform poorly in the adversarial setting (for the same reason why SGBS performs poorly).
I 20 QUESTIONS SETUP
Hu et al. 2018) collected dataset of 1000 celebrities and 500 possible questions to ask about each celebrity. We chose 100 questions out the 500 by first constructing 5', X' and Z' for the 500 dimensions data, and sampling without replacement 100 of the 500 dimensions from a distribution derived from static allocation. We down-sampled the number of questions so our training can run with sufficient M and L. to de-noise the gradients while being prototyped with single GPU.
Specifically, the dataset from Hu et al. (2018) consists of probabilities of people answering Yes / No / Unknown each filebrity-questrrn pair collected from some population. To better fit the linear bandit scenario, we re-normalize the probability of getting Yes /No, conditioning on the event that these people did not answer Unknown. The probability of answering Yes all 500 questions for each celebrity then constitutes vectors (((1,. ....,
"..,,p((100) ((1000)) E 500 where each dimension a give p (()) represents the probability of yes to the ith question about the jth person. The action set X' is then
constructed as X' {e; [500]] while Z' = (z() |2( (p > 1/2]} c {0, 1] 1000 are
binary vectors taking the majority votes.
To sub-sample 100 questions from the 500, we could have uniformly at random selected the ques- tions, but many of these questions not very discriminative. Thus, chose "good" set of queries based on the design recommended by P. of et al. (2019). If questions were being an- swered noiselessly in response to particular E Z then equivalently have that for this setting
20

---

Under review as a conference paper at ICLR 2021
0 22 - 1. Since P. optimizes allocations À over X' that would reduce the number of required queries as much as possible (according to the information theoretic bound of (Fiez et al. 2019) want find single allocation for all z' Z simultaneously, problem
perform the optimization
|| - ( (
min XEAUXI-1
max max 2'E'' xf22
((=' - (2'-2)²(22) 222 - 1))²
We then sample elements from 2" according to this optimal À without replacement and add them to X until | 100.
JESTER JOKE RECOMMENDATION SETUP
We consider the Jester jokes dataset of Goldberg et al. 2001 that contains jokes ranging from pun- based jokes to grossly offensive. We filter the dataset to only contain users that rated all 100 jokes, resulting 14116 users. A rating of each joke was provided on [-10, 10] scale which was shrunk to |-1, 1]. Denote this set ratings as é {0: : [14116], 0 [-1, 1]100,, where 0, encodes the ratings of all 100 jokes by user i. To construct the set of arms 2, we then clustered the ratings of
these users to 10 groups to obtain 2 { í E [10], 2, E {0, 1 100) } by minimizing the following metric:
14116
min
Σ
max (2,, 0,) max 0t).
2: 2:12=110
2.E 100
26
To solve for Z. we adapt the & means algorithm, with the metric above instead of the 2 metric used traditionally.
21


Reviews:
[{"review_id": "w_osFly_rBl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, the authors present an adaptive model that can learn a good policy by adversarial training. The proposed model is based on theoretic lower bounds. They focus on the setting when the query budget is small and conduct some experiments to verify the proposed method.\n\nPros:\n- The authors derive some theoretical results.\n- Using adversarial training is interesting.\n\nCons:\n- The notations are too complicated and it's hard to follow the author's thought.\n- I feel like the query budget in the experiment is very small (T=20). This setting might be unrealistic. I would like to see if the proposed method can have good performance when the budget is reasonably large.\n- The current experimental results are not very convincing for me. Uncertainty or SGBS seems to be a good choice in some cases as well. Maybe the author can do experiments on more datasets and see if the proposed method performs better in most datasets.\n- I notice that the authors subsample the training examples. It seems that the training the proposed method is slow so the number of training data and the budget are limited.\n\nTypos:\n- I thought in Figure 2, 3, 4, 6, 7, \\hat{pi} should be pi_*", "extra_scores": {}, "extra_text": {}}, {"review_id": "u9PVPNUIH1u", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper \"Learning to Actively Learn\" proposes a differentiable procedure to design algorithms for adaptive data collection tasks. The framework is based on the idea of making use of a measure of problem convexity (each problem is parametrized by a parameter theta) to solve solving a min-max objective over policies. The rationale behind this objective is that the resulting policy of solving this min-max objective should be robust to the problem complexity. The algorithm then proceeds to sample problem instances and making use of a differentiable objective to find a policy parametrized by a parameter psi, which could be parametrizing a neural network.  \n\nOne potential drawback is that the authors assume the dynamics of the problem instance rewards are known by the learner (for example they are a gaussian), which is necessary for computing policy gradients through the policy parametrization. A second drawback lies in the problem tessellation over the theta space. As it is written the method does not seem to scale beyond very small dimensional problem instances, since otherwise the value N would have to be exponential in the dimension, and therefore intractably large. The paper falls within the differentiable \"meta-learning\" for bandits literature, and it does a good job of placing itself within that literature. It also has a convincing experimental section. Other works in the area have not tackled the problem that the authors set themselves to solve: designing algorithms that can adaptively perform well depending on the instance they are fed.\n\nI also find particularly interesting the use of the model complexity balls that can be defined using other existing results in the literature such as in the case of transductive linear bandits. I would suggest to add more explanation to what r is earlier in the paper as it is hard on the reader after a first read. Overall I think this is nice work. The paper itself is more applied than theoretical but I think it is appropriate for ICLR. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gsfpwz0xihO", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper sets out to address a class of pure exploration problems. Of particular interest to the authors seem to be settings where the sample complexity requirements are very stringent. A good example of such a task would be that of tuning the hyperparameters of an expensive training algorithm like BERT pre-training or ResNet.\n\nEven though the problem domain is very interesting, the paper is just not fit for publication in this form for the following reasons:\n\n1- The write-up is just horrific:\n\n  a- The problem setting doesn't mention anything about intermediate rewards, which was very confusing because the reader is given the impression that learning happens based on just the total reward at the end of the trajectory.\n\n  b- There are some definitions that just don't make sense: for instance, Equation (1) is subtracting a number from a policy. My guess is that the equation is missing some parentheses, but what's the point of formulas if they're not precise. Also, a more minor point is that the is no such thing as arginf: the whole point of inf is to deal with situations where the function doesn't have a minimum, e.g. inf_{x>0} 1/x = 0. What you mean is argmin, in which case you need some sort of compactness assumption in the policy space.\n\n  c- It's completely unclear what the point of Prop 1 is.\n\n  d- More generally, the paper could really benefit from a table of notations so the reader doesn't have to keep jumping back and forth.\n\n2- It's really unclear what the contributions of the paper are: there are tons of papers on linear bandits in the pure exploration setting, so what does this paper add? There is no sample complexity analysis in there, which would be fine if the paper was a solid experimental paper, which it is not as discussed in the next point.\n\n3- I find the experiments very unconvincing: as mentioned above, a really good motivating use-case is hyperparameter tuning for a very complex models or at least a diverse set of examples. A good example of a paper that does a satisfactory job of providing convincing experimental results is the Hyperband paper [Li et al, 2017], which render the paper valuable despite its weak theoretical results.\n\nPlease get one of your colleagues to read the paper before resubmitting it.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TuQ78X_-8F", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Even though the paper introduces an interesting solution to an important problem, it suffers from two main weaknesses:\n- it lacks an lacks an intuitive explanation of the proposed approach, thus making it hard to read\n- the Empirical Evaluation seems to lack both a unifying theme and certain critical details\n\nIn order to make the paper easier to read, it would be great to add, right after the introduction, a section that explains in an intuitive manner the proposed approach. The authors should choose a motivating example  (ideally, it should be a real world domain, but it could also a be a simplified, synthetic one)  on which to explain all the basics of the proposed approach: which are the equivalence classes, how is the adversarial training leveraged, and how/when will one suffer the catastrophic loss referred to at the very bottom of page 1.\n\nThe empirical validation will greatly benefit by tightening the various arguments.\n\nFor 20 Questions:\n- the scalability issue should not be confined to APPENDIX I: what would have taken to train on the entire dataset? What would take to use a dataset with 10x celebrities, 10x questions, or both? \n- the statement \"Uncertainty sampling even outperforms our r-dependent baseline by a bit which in theory should not occur – we conjecture this is due to insufficient convergence of our policies or local minima\" certainly deserves a paragraph of its own, and a lot deeper an explanation than currently provided\n- the accuracy results in Table 1 deserve a discussion:  why is your approach better than SGBS, when in 5 out of 6 settings SGBS has farr better results than your method?\n- last but not least, you define should explain how \"Accuracy\" is computed (Table 1 is the only place in the paper where this term is used), and you should also use the \"Win Rate\" metric so that we can have an apples-to-apples comparison with the results in the original paper  \n\nFor Joke Jester:\n- please explain why your are restricting the dataset to include only jokes that are rated by all users. Is it a scalability issue? Or something else?\n- you should also provide results in terms of Normalized Mean Absolute Error (NMAE), so that we can compare with results in the original paper\n- In Table 2, the Uncertainty Sampling approach has better performance than your proposed method, even though in Figure 7 it seems to be doing consistently worse. Could you please discuss this phenomenon?  \n\nOther comments:\n- it is very difficult to make sense of Figures 2 & 3 even when zooming-in of a large display. \n- In Figure 2, for r > 20, there seems to always be 2-3 policies better than the proposed one; however, the image is so \"crowded\" in the r <= 20 region that it is impossible to see what is going on even at max-magnification. The authors should explain in prose what is going on & why they consider their policy best-overall. They should also provide in an APPENDIX several 1:1 graphs that compare the proposed policy against each of the other main contenders.\n- In the paragraph that covers Figure 3, the authors write \"π∗ performs almost as well as the r-dependent baseline policies over the range of r.\" However, Figure 3 does not include the r-dependent baseline.\n- the authors should be consistent in notation: Figure 4 uses the LAL acronym, while Figure 5 uses the full name for it.           ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an adaptive model that learns a good policy by adversarial training, focusing on the setting where the query budget is very small. Some experiments are carried out to validate the proposed method. The reviewers' opinions turned out to be split on this paper. On one hand, all reviewers appreciated the idea of the problem and recognized its importance. On the other hand, there are have been multiple concerns regarding readability (but that has improved during the discussion) and about the empirical validation/evaluation.
Based on the above, as well as my own reading, I believe this paper contains interesting ideas but, as it currently stands, is not ready for publication.
Decision: Reject