Learning Effective Exploration Strategies For Contextual Bandits
Authors: Amr Sharaf
Hal Daumé III
Venue:  (2020)
Keywords: meta-learning
contextual bandits
imitation learning

Abstract: In contextual bandits, an algorithm must choose actions given observed contexts, learning from a reward signal that is observed only for the action chosen. This leads to an exploration/exploitation trade-off: the algorithm must balance taking actions it already believes are good with taking new actions to potentially discover better choices. We develop a meta-learning algorithm, MELEE, that learns an exploration policy based on simulated, synthetic contextual bandit tasks. MELEE uses imitation learning against these simulations to train an exploration policy that can be applied to true contextual bandit tasks at test time. We evaluate on both a natural contextual bandit problem derived from a learning to rank dataset as well as hundreds of simulated contextual bandit problems derived from classification tasks. MELEE outperforms seven strong baselines on most of these datasets by leveraging a rich feature representation for learning an exploration strategy.

Under review as a conference paper at ICLR 2020
LEARNING EFFECTIVE EXPLORATION STRATEGIES FOR CONTEXTUAL BANDITS
Anonymous authors Paper under double-blind review
ABSTRACT
In contextual bandits, an algorithm must choose actions given observed contexts, learning from a reward signal that is observed only for the action chosen. This leads to exploration/exploitttion trade-off: the algorithm must balance taking actions it already believes are good with taking new actions to potentially discover better choices. We develop meta-learning algorithm, MÊLÉE, that learns exploration policy based on simulated, synthetic contextual bandit tasks. MÅLÉR uses imitation learning against these simulations train an exploration policy that can be applied to true contextual bandit tasks at test time. We evaluate on both a natural contextual bandit problem derived from a learning to rank dataset as well as hundreds of simulated contextual bandit problems derived from classification tasks. MÊLÁR outperforms seven strong baselines on most of these datasets by leveraging a rich feature representation for learning exploration strategy.
INTRODUCTION
In contextual bandit problem, an agent attempts optimize its behavior over sequence of rounds based on limited feedback (Kaelbling 1994 Auer 2003 Langford & Zhang 2008). In each round, the agent chooses an action based on a context (features) for that round, and observes reward for that action but no others 2). Contextual bandit problems arise in many real-world settings like online recommendations and personalized medicine. As in reinforcement learning, the agent must learn to balance exploitation (taking actions that, based on past experience, it believes will lead to high instantaneous reward) and exploration (trying actions that it knows less about).
In this paper, we present meta-learning approach to automatically learn a good exploration mech- anism from data. To achieve this, we use synthetic supervised learning data sets on which we can simulate contextual bandit tasks in offline setting. Based these simulations, our algorithm, MÂLÉE (MEta L.aarner for Exploration [ learns a good heuristic exploration strategy that should ideally generalize to future contextual bandit problems. MÊLÁÉ contrasts with more classical ap- proaches to exploration (like c-greedy or LinUCB; see (36). in which exploration strategies are con- structed by expert algorithm designers. These approaches often achieve provably good exploration strategies in the worst case, but are potentially overly pessimistic and are sometimes computationally intractable.
At training time $ 3.2). MÉLÉE simulates many contextual bandit problems from fully labeled synthetic data. Using this data, in each round, MÉLÉE is able to counterfactually simulate what would happen under all possible action choices. We can then use this information to compute regret estimates for each action, which can be optimized using the Aggre VaTe imitation learning algo- rithm (Ross & Bagnell| 2014). Our imitation learning strategy mirrors that of the meta-learning approach Bachman et al. (2017) in the active learning setting. We present a simplified, stylized analysis of the behavior of MÉLÉE to ensure that our cost function encourages good behavior (84). Empirically, we use MÉLÉE to train an exploration policy on only synthetic datasets and evaluate this policy on both a contextual bandit task based
natural learning rank dataset as well as three hundred simulated contextual bandit tasks 5.2).. h. We compare the trained policy to a number
of alternative exploration algorithms, and show the efficacy of our approach 55.3
Coode release: the code is available online dc:3v8oo5cbu87aww AACu1 4c4w Zxble w
https://ve /twp://www.... wwwpbox..oooooooo wwmpppxw..co//eeemmm /h/

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES: CONTEXTUAL BANDITS AND POLICY OPTIMIZATION
Contextual bandits is model of interaction in which an agent chooses actions (based on contexts) and receives immediate rewards for that action alone. For example, in simplified news personaliza- tion setting, at each time step i, a user arrives and the system must choose a news article to display to them. Each possible news article corresponds to an action a, and the user corresponds to a context Tt. After the system chooses an article a display, it can observe, for instance, the amount of time that the user spends reading that article, which it can use as a reward Tr (oe).
Formally, we largely follow the setup and notation of Agarwal et al. (0144). Let X' be an input space of contexts (users) and [K] (1..... K} be a fimite action space (articles). We consider the statistical setting in which there exists a fixed but unknown distribution D over pairs (z. r) E |0, 1J where where is a vector of rewards (for convenience, we assume all rewards are bounded in [0, I).. In this setting, the world operates iteratively over rounds 1.2,.... Each round l:
1. The world draws (I2, r2) D and reveals context Tt-
2. The agent (randomly) chooses action ar E [K] based on I₁, and observes reward r. (ae)..
The goal of an algorithm is to maximize the cumulative sum of rewards over time, Typically the primary quantity considered is the average regret of a sequence of actions di,..., 0r to the behavior of the best possible function in prespecified class F:
T
Xaa uT)
max Σ JEF
[r((((a)))
- ra.))
t=1
An agent is call no-regrer if its average regret is zero in the limit of large T.
To produce good agent for interacting with the world, we assume access to a function class F and to oracle policy optimizer for that function class. For example, F may be set of single layer neural networks mapping user features x E X' to predicted rewards for actions a E [K]. Formally, the observable record of interaction resulting from round t is the tuple 0z, ra (a.). pe(aa))
Xx(K][ M0, 10 1]. where (aa)) is the probability that the agent chose action or, and the full history of interaction is he ((ri; as, (aa)) Pi (a)))) The oracle policy optimizer, POLOPT, takes as input history of user interactions and outputs an f f F with low expected regret.
A standard example of a policy optimizer is to combine inverse propensity scaling (IPS) with a regression algorithm (Dudik et al., 2011). Here, given a history h. each tuple (z, a, p, in that history mapped to a iuultpple-ouppl regression example. The input for this regression example is the same z; the output is vector of K costs, all of which are zero except the at component, which takes value r/p. This mapping is done for all tuples in the history, and supervised learning algorithm on the function class F is used to produce low-regret regressor f. This is the function returned by the policy optimizer. IPS, and other estimators that have lower-variance than IPS (such of
as the doubly-robust estimator), have the property of being unbiased. In experiments, we use the direct method (Dudik et al., 2011) largely for its simplicity, however, MÉLÉE is agnostic to the type of the estimator used by the policy optimizer.
3 APPROACH: LEARNING AND EFFECTIVE EXPLORATION STRATEGY
In order to have an effective approach the contextual bandit problem. one must be able both optimize a policy based on historic data and make decisions about how to explore. The explo- ration/exploitation dilemma is fundamentally about long-term payoffs: potentially suboptimal now in order to learn how to behave better in the future? A particularly simple and effective form of exploration is e-greedy: given a function f output by POLOPT, act according to f(x) with probability (I e) and act uniformly at random with probability Intuitively, one would hope to improve on such a strategy by taking more (any!) information into account; for instance, basing the probability of exploration on f's uncertainty. In this section, we describe MÉLÉE, first by describing how it operates at test time when applied to a new contextual bandit problem (3.)) and then by describing how to train it using synthetic simulated contextual bandit problems
worth trying something
3.2
2

---

Under review as a conference paper at ICLR 2020
3.1 TEST TIME BEHAVIOR OF MÉLÉE
Our goal in this paper is to learn how to explore from experience, The training procedure for MÊLÉE will use offiine supervised learning problems to learn an exploration policy æ, which takes two imputs: a function I E F and a context x, and outputs an action. In our example, ʃ will be the output of the policy optimizer on all historic data, and z will be the current user. This is used to produce an agent which interacts with the world, maintaining an initially empty history buffer h, as:
1. The world draws (xe, r:) ~ D and reveals context Ft.
2. The agent computes ft < (h) and greedy action ã = (fe, 22).
3. The agent plays a; = ag with probability (1 - 44), and at uniformly at random otherwise.
4. The agent observes r. (at) and appends (xa, at (=(e)), pt) to the history h, where pt. //K if 04 + āe; and pt = μ + /// K if de dz.
Here, ft is the function optimized on the historical data, and uses it and 2y to choose an action. Intuitively, т might choose to use the prediction f((2;) most of the time, unless ft is quite uncertain on this example, in which case might choose return the second (or third) most likely action according to ft. The agent then performs a small amount of additional μ y-greedy-style exploration: most of the time it acts according to π but occasionally it explores some more. In practice (33). find that setting μ = 0 is optimal in aggregate, but ner-zero/ j is necessary for our theory (4).
Importantly, we wish to train π using one set of tasks (for which we have fully supervised data on which to run simulations) and apply to wholly different tasks (for which we only have bandit feed- back). To achieve this, we allow и to depend representationally on fa in arbitrary ways: for instance, it might use features that capture ft's 's uncertainty on the current example (see |5.1 for details). We additionally allow и depend in a tast-independent manner on the history (for instance, which actions have not yet been tried): it can use features of the actions, rewards and probabilities in the history but not depend directly on the contexts r. This is to ensure that æ only learns to explore and not also to solve the underlying task-dependent classification problem. Because т needs to learn to be task independent, we found that if ft's predictions were uncalibrated, was very difficult for π to generalize well to unseen tasks. Therefore, we additionally allow т to depend on a very small amount of fully labeled data from the task at hand, which we use to allow x to calibrate fi pre- use only 30 fully labeled examples, but alternative approaches to calibrating fe that do not require this data would be preferable.
dictions. In our experiments
3.2 TRAINING MÉLÉE BY IMITATION LEARNING
The meta-learning challenge is: how do we learn a good exploration policy n?? We assume we have access to fully labeled data on which we can train n; this data must include context/reward pairs, but where the reward for all actions is known. This is weak assumption: in practice, we use purely synthetic data as this training data; one could alternatively use any fully labeled classification dataset (Beygelzimer & Langford, 2009). Under this assumption about the data, it is natural to think of i r's behavior as sequential decision making problem in simulated setting, for which a natural class of learning algorithms to consider are imitation learning algorithms (Daumé et al. 2009 Ross
et al. 2011 Ross & Bagnell 2014] Chang et al. 2015)
Informally, at training time, MÂLÉE will treat one of these synthetic datasets as if it were a contextual bandit dataset. At each time step t, it will compute ft by running POLOPT on the historical data, and then ask: for each action, what would the long time reward look like if I were to take this action. Because the training data for MÉLÉEiA is fully labeled, this can be evaluated for each possible action, and a policy т can be learned to maximize these rewards. More formally, in imitation learning, we assume training- tiiming-timeeae access to expert, 'τ, whose behavior we wish to learn to imitate test-time. From this, we can define an optimal reference policy x² which effectively "cheats" " at training time by looking the true labels. The learning problem is then estimate æ to have as similar behavior to xt as possible, but without access to those labels.
The imitation learning algorithm we use is Aggre (Ross& & Bagnell 2014) (closely related to DAgger (Ross et al. (01I)), and is instantiated for the contextual bandits meta-learning problem in Aggre VaTe learns to choose actions minimize the cost-to-go of the expert rather than the
Alg
In other work meta-learning, such problems are often cast as full reinforeement-eerriig problems. We opt for imitation learning instead because it computationally attractive and effective when a simulator exists.
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1 MÉLÉE (supervised training sets (Sm.). hypothesis class F, exploration rate μa, num- ber of validation examples Naa, feature extractor +)
1: for round n. . N do
2: initialize meta-dataset D = { choose S at random from {Sm), and set history hnp = 0
3: partition and permute S randomly into train Tr and validation Val where |Val] Nuat
4: for round t = 2, .......................... [r| do
5: let (z,, rr) Tr
6: for each action ......, K do
7:
optimize ftaa POLOPT(F, h4-1 ① (1,, r,r,((), K-1 14) --)) on augmented history
8: roll-out: estimate čas the cost-to-go of a, using re(a) and roll-out policy Thth on fr.
9: end for
compute f: POLOPT(F, h1-1)
11: aggregate D +- D @ (+ (t, 11-1, Val), (cI,..., (x))
roll-in: ar ~ x l + (1 (1) - (Sc: 24) with probability Pt, where is the ones-vector
13: append history he f- he-1 @ (Ze, ae (e(a)),t))
14: end for
15: update nn LEARN(D)
16: end for
return [
zero-one classification loss of mimicking its actions. On the first iteration AggreVa'l collects data by observing the expert perform the task, and in each trajectory, time t, explores action in state s, and observes the cost-to-go Q of the expert after performing this action.
Following the AggreVaTe template, MÉLÉE operates in iterative fashion, starting with arbi- trary π and improving it through interaction with an expert. Over N rounds, MÂLÉE selects random training sets and simulates the test-time behavior that training set. The functionality is to generate a number of states (Je, xt) on which to train π, and to use the supervised data to estimate the value of every action from those states. MÉLÉE achieves this by sampling random supervised training set and setting aside some validation data from it fine 3). It then simulates a contextual ban- dit problem on this training data; at each time step f, tries all actions and "pretends" like they were appended to the current history (line 7) which it trains new policy and evaluates it's roll-out value (Tine 8). This yields, for each a new training example for æ, which added to r's training set (line 11): the features for this example are features of the classifier based on true history (Tine 10) (and possibly statistics of the history itself), with a label that gives, for each action, the correspond- ing cost-to-go of that action (the computed in line 8) MÉLÉE then must commit to a roll-in action to actually take; it chooses this according to a roll-in policy (line 12). MÉLÉE has no explicit "exploitation policy", exploitation happens when ı chooses the same action fi, while exploration happens when it chooses a different action. In learning to explore, MÉLÉE simultaneously learns when exploit.
Roll-in actions. The distribution over states visited by MÈLÉE depends on the actions taken, and in general good have that distribution match what seen test time. This distribution is determined by a roll-in policy (ine 12h, controlled in MÉLÉE by exploration parameter μ. E [0, 1]. As μ + the roll-in policy approaches uniform random policy; as μ O, the roll-in policy becomes deterministic. When the roll-in policy does not explore, it acts according to xffe..).
Roll-out values. The ideal value to assign to an action (from the perspective of the imitation learning procedure) is that total reward (or advantage) that would be achieved in the long run if we took this action and then behaved according to our final learned policy. Unfortunately, during training, we do not yet know the final learned policy. Thus, surrogate roll-out policy л our is used instead. A convenient, and often computationally efficient alternative, is to evaluate the value assuming all future actions were taken by the expert (Langford & Zadrozny 2005 Daumé et al.) 2009 Ross & Bagnell 2014). our setting, at any time step f, the expert has access to the fully supervised reward vector r, for the context æ;, When estimating the roll-out value for action a, the expert will return the true reward value for this action ra(a) and we use this as our estimate for the roll-out value.
4

---

Under review as a conference paper at ICLR 2020
4 THEORETICAL GUARANTEES
We analyze MÉLÉF, showing that the no-regret property of AGGREVATE can be leveraged in our meta-learning setting for learning contextual bandit exploration. In particular, we first relate the regret of the learner in line 15) to the overall regret of ग. This will show that, if the underlying classifier improves sufficiently quickly, MÉLÉE will achieve sublinear regret. We then show that for a specific choice of underlying classifier (BANDITRON), this is achieved. MÉLÉE is an instantiation of AGGREVATE (Ross & Bagnell 2014;; as such, inherits AGGRE regret guarantees.
Theorem (Thm 2.2 of Ross& Bagnell (2014), adapted) Afte N rounds, if LEARN Tine 15) is no-regret algorithm, then as N - co, with probability 1, it holds that J(R) S ((x))
2T v K & (T), where J(-) is the reward of the exploration policy, & is the average policy returned, and eea (T) )) is the average regression regret for each n. accurately predicting è, where
N
Eclass (T) = min E swddt Σ [0
1 f N
min Q7 Q7-c+1(5.a)
(2)
the empirical minimum expected cost- cest-sensitive classification regret achieved by policies in the class II on all the data over the N iterations of training when compared to the Bayes optimal
regressor. for (T) the uniform distribution over {l...., T. d' the distribution of states at time induced by executing policy and Q' the cost-to-ge of the imitation learning expert.
Thus, achieving low regret at the problem of learning π on the training data it observes ("D" in MÉLÉE), i.e. Eotass (T)) is small, translates into low regret the contextual-bandi setting. At first glance this bound looks like it may scale linearly with T. However, the bound in Theorem ] is dependent on Estoss (T). Note however, that s is a combination of the context vector I' and the clas- sification function fo- As T - co, one would hope that fo improves significantly and &ctass (T)) decays quickly. Thus, sublinear regret may still be achievable when f learns sufficiently quickly as function of T. For instance, if f is optimizing strongly convex loss function, online gradient de- scent achieves regret guarantee of 0 log
(Hazan al. 2016 Theorem 3.3), potentially leading
to regret for MÉLÉE of O ( (log T)/T).
The above statement is informal (it does not take into account the interaction between learning and σ). However, we can show a specific concrete example: we analyze MÂLÉE'S test-time behavior when the underlying learning algorithm is BANDITRON. BANDITRON is variant of the multiclass Perceptron that operates under bandit feedback. Details of this analysis (and proofs, which directly follow the original BANDITRON analysis) are given in Appendix A] here state the main result. Let % = ( xT) = 1) [r]] (r())(f((z.) = [|x,] be the edge of π (ff..) over f, and let r = + Σt= E Ky be overall measure of the edge. For instance if simply returns f's prediction, then all y 0 and r 1. We then show the following:
Theorem 2 Assume that for the sequence of examples, (21, r1), (I2, r2),..., (xT, TT), we have, for all t, || S 1. Let W* be any matrix, let L be the cumulative hinge-loss of W*, let be a uniform exploration probability, and let D = 2 I| be the complexity of W Assume that By 2 0 for all t. Then the number of mistakes M made by MÍLÁE with BANDITRON as POLOPT satisfies:
EM & + K₁T + max { (DT/H, / DDKTT + DDI//P
(3)
where the expectation taken with respect to the randomness of the algorithm.
Note that under the assumption Ey, 2 O for all t, we have I < The analysis gives the same mistake bound for BANDITRON but with the factor of I, hence this result improves upon the BAN- DITRON analysis only when T < (in the realizable setting, the number of mistakes analogous to the regret). This result is highly stylized and the assumption that Ey: 2 0 is overly strong. This assumption ensures that π never decreases the probability of a "correct" action. It does, however, help understand the behavior of MÉLÉE, qualitatively: First, the quantity that matters in Theo- rem 2 Egy is (in the 0/1 loss case) exactly what MÉLÉE is optimizing: the expected improvement for choosing action against ft's 's recommendation. Second, the benefit of using within BAN- DITRON is a local benefit: because π is trained with expert rollouts, as discussed in [4] the primary improvement in the analysis is to ensure that π does better job predicting (in single step) than
5

---

Under review as a conference paper at ICLR 2020
ft does. An obvious open question is whether it is possible to base the analysis on the regrer of (rather than its error) and whether it is possible to extend beyond the BANDITRON.
EXPERIMENTAL SETUP AND RESULTS
Using a collection of synthetically generated classification problems, we train an exploration policy using MÊLÍF (Alg 1}. This exploration policy learns to explore on the basis of calibrated proba- bilistic predictions from f together with a predefined set exploration features [..I). Once π is learned and fixed, we follow the test-time behavior described in 3. to evaluate textual bandit problems. We evaluate MÉLÉE on a natural learning to rank task (5..3.11. To ensure that the performance of MÉLÉE generalizes beyond this single learning rank task, additionally perform thorough evaluation on 300 "simulated" contextual bandit problems, derived from standard classification tasks (.3.2))
a of con-
In all cases, the underlying classifier f is a linear model trained with a policy optimizer that runs stochastic gradient descent (details are AA..). We seek answer two questions experimentally; (I) How does MÉLÉE compare empirically to alternative (expert designed) exploration strategies? (2) How important are the additional features used by MÉLÉE in comparison to using calibrated probability predictions from as features?
5.1 TRAINING DETAILS FOR THE EXPLORATION POLICY
Exploration Features. In our experiments, the exploration policy is trained based on features & Alg I line II). These features are allowed to depend on the current classifier ft. and on any part of the history except the inputs Ię in order to maintain task independence. We additionally ensure that its features independent of the dimensionality of the inputs, that generalize to datasets of arbitrary dimensions. The specific features we use are listed below; these are largely inspired by Konyushkova et al. (201)) but adapted and augmented our setting.
The features of fe that we use are: a) predicted probability p(a; æ.), we use a softmax over the predicted rewards from fi convert them to probabilities; b) entropy of the predicted probability distribution; c) a one-hot encoding for the predicted action (zx,) The feeatures of fi-1 that we use are: current time step t; normalized counts for all previous actions predicted so far; e) average observed rewards for each action; d) empirical variance of the observed rewards for each action in the history. our experiments, we found that it is essential to calibrate the predicted probabilities of the classifier ft. We use very small held-out dataset, of size 30, to achieve this. We use Platt's s scaling (Plati 1999 Lin et al. 2007) method to calibrate the predicted probabilities. Platt's scaling works by fitting logistic regression model to the classifier's predicted scores.
Training Datasets. In our experiments, we follow Konyushkova et al. (017)) (and also Peters et al. 2014), in different setting) and train the exploration policy only synthetic data. This is possi- ble because the exploration policy т never makes use of x explicitly and instead only accesses it via fi behavior on it. We generate datasets with uniformly distributed class conditional distributions. The datasets are always two-dimensional. Details are in A.
5.2 EVALUATION METHODOLOGY
For evaluation, we use progressive validation (Blum et al. 1999), which is exactly computing the reward of the algorithm. Specifically, to evaluate the performance of an exploration algorithm AA on dataset S of size n, we compute the progressive validation return G((A) 1 Ei= Tt (ax) as the average reward up to where is the action chosen by the algorithm A and r, is the true reward.
n
Because our evaluation over 300 datasets, we report aggregate results two forms. The simpler one is Win/Loss Statistics: We compare two exploration methods on a given dataset by counting the number of statistically significant wins and losses. An exploration algorithm AA wins over another algorithm B if the progressive validation return G(A) is statistically significantly larger than B's return G(B) at the 0.01 level using a paired sample t-test. We also report cumulative distributions of rewards for each algorithm, following Zhang al. (2019). In particular, for given relative reward value (x E [o, 1)), the corresponding CDF value for a given algorithm is the fraction of datasets which this algorithm achieved reward at least æ. We compute relative reward by Min-

---

Under review as a conference paper at ICLR 2020
Max normalization: linearly transforming reward y to y/ --
max-mi min' where min & max the
minimum& & maximum rewards among all exploration algorithms.
In our experiments, we compare to the following baseline exploration methods, keeping the policy optimization method fixed (details in SA.4): e-greedy (Sutton 1996); e-decreasing (Sutton & Barto, 1998]: EG e-greedy (Li et al. 2010b); T -irsst. We additionally compare to three state-of-the-ar exploration methods: LinUCB (Li et al. 2010a); Cover (Agarwal et al.) 2014); and its variant Cover-NU (Bietti et al.
2018). We select the best hyperparameters following Bietti et al. (2018).
5.3
EXPERIMENTAL RESULTS
5.3.1 LEARNING RANK
We evaluate MÊLÉE on natural learning to rank dataset. The dataset we consider is the Microsoft Learning to Rank dataset, variant MSLR-IOK from Qin & Liu (2013) J The dataset consists of feature vectors extracted from query-url pairs along with relevance judgment labels. The relevance judgments are obtained from retired labeling set of commercial web search engine (Microsoft Bing), which take values from 0 (irrelevant) to 4 (perfectly relevant) and we drop the queries not labelled as any of the two extremes. In our experiments, we limit the number of labels to the two extremes: O and 4. A query-url pair is represented by a 136-dimensional feature vector. The dataset is highly imbalanced the number of irrelevant queries is much larger than the number of relevant ones. To address this, we sample the number of irrelevant queries to match that of the relevant ones. To avoid correlations between the observed query-url pairs, we group the queries by the query ID, and sample single query from each group. We convert relevance scores to losses with 0 indicating a perfectly relevant document, and an irrelevant one.
Figure Ihshoss the evaluation results on a subset of the MSLR-10K dataset. Since the performance closely matched between the different exploration algorithms, we repeat the experiment 16 times with randomly shuffled permutations of the MSLR-10K dataset. [Figure T (left) shows the learning curve of the trained policy æ as well as the baselines. Here, we see that MÊLÁF quickly achieves high reward, after about 100 examples the two strongest baselines catch up. By 200 examples all approaches have asymptoted. We exclude LinUCB from these runs because the required matrix win/loss
inversions made it too computationally expensive Figure shows statisticalll-signifff differences for each of the algorithms, across these 16 shuffles. Each row/column entry shows the number of times the row algorithm won against the column, minus the number of losses. MÊLÉE is the only algorithm that always wins more than it loses against other algorithms, and outperforms the nearest competition (e-decreasing) by points.
5.3.2 SIMULATED CONTEXTUAL BANDIT TASKS
We additionally perform exhaustive evaluation simulated contextual bandit tasks to ensure that the performance of MÈLÉE generalizes beyond learning to rank. Following Bietti et al. (2018), collection of 300 binary classification datasets from openmll orgi for evaluation; the
precise list and download instructions is in |A.3 These datasets cover a variety of different domains including text & image processing, medical, and sensory data. We convert classification datasets into cost-sensitive classification problems by using a 0/1 encoding. Given these fully supervised cost-sensitive multi-class datasets, we simulate the contextual bandit setting by only revealing the reward for the selected actions.
In Figure 2 (left), we show representative learning curve. Here, we see that as more data becomes available, all the approaches improve (except r-rist, which has ceased to learn after 2% of the data). MÊLÉE, in particular, is able to very quickly achieve near-optimal performance (in around 40 examples) in comparison to the best baseline which takes at least 200. In Figure 2 (right), we show the CDFs for the different algorithms. To help read this, at x 1.0, MÉLÉE has relative reward at least 1.0 on more than 40% of datasets, while e-decreasing and e-greedy achieve this on about 30% of datasets. We find that the two strongest basclines are e-decreasing and e-greedy (better when reward differences are small, toward the left of the graph). The two curves for e-decreasing and e- greedy coincide. This happens because the exploration probability 6g for c-decreasing decays rapidly
https: / /wwww m crosoft. com/en-uu///eeeeeo en us/ research//a hwt.ch/ooc/c/ssss1.1 In single of LiUUCB we observed that its performance is on par with r-greedy.
7

---

Under review as a conference paper at ICLR 2020
Progressive Reward
0.8
0.6
0.4
egenyy
0.2
0.0
Caverey
0 50
100
150
200
Ove
Time
MÉLÉE, μr: 0.0
E-decreasing, &o: 0.1
EG E-greedy
E-greedy, 0.0
LinUCB
T-first, 0.02
Cover, Bag Size: 16, 4: 0.1
Figure I: Results for the Learning to Rank task. (Left) Learning curve on the MSLR-10K dataset: x-axis shows the number of queries observed, and y-axis shows the progressive reward. (Right) Win/Loss counts for all pairs of algorithms over 16 random shuffles for the MSLR- R-KK dataset.
(Left) A representative
1.0
1.0
learning curve on dataset #1 144. (Right) Compar- ison of all exploration algorithms using the empirical cumulative distribution function of the relative progressive validation return G (upper-right is optimal) on 300 classification problems. The CDF curves for e-decreasing and e-gredy coincide.
Progressive Reward
0.9
Normalized Counts
0.8
0.8
0.6
0.7
0.6
0.5
100
200
0.0
0.2
0.4
0.6 0.8 1.0
Time
Relative Reward (Higher is Better)
MÉLÉE, μr: 0.0
g-decreasing, Eg: 0.1
EG s-greedy
E-greedy,
LinUCB
T-first, E: 0.02
Cover, Bag Size: 16, w: 0.1
Figure 2: Behavior of MÉLÉE in comparison to baseline and state-of-the-ar exploration algorithms.
approaching zero with rate of y where t is the index of the current round. MÂLÉE outperforms baselines the "large reward" regimes (right of graph) but under-performs e-decreasing and e-greedy in low reward regimes (left of graph).
In Figure 3
we show statistically-sinnffica win/loss differences for each the algorithms. Here, each (row, column) entry shows the number of times the row algorithm against the column, minus the number of losses. MÉLÉε the only algorithm that always wins more than it loses against other algorithms, and outperforms the nearest competition (c-decreasing) by 23 points.
To understand more directly how MÉLÉE compares to e-decreasing, the left plot of Figure 4 we show scatter plot of rewards achieved by MÉLÉE (X-axis) and e-decreasing (y-axis) on each of the 300 datasets, with statistically significant differences highlighted in red and insignificant differences in blue. Points below the diagonal line correspond to better performance by MÉLÉÉ (147 datasets)
8

---

Under review as a conference paper at ICLR 2020
MÉLEE
30
23
167
126
160
166
182
agreedy
174
e-decreasing
177
c-greedy
-177
57
LinUCC
136
160
144
141
-59
33
Cover -166
-174
-176
-57
-91
-33
-19
Cover-nu 182
105
204
-48
-77
-31
19
Figure 3: Win/Loss counts for all pairs of algorithms (columns match the rows).
(Left) MÉLÉE
Reward for MELEE with Callbration Only
decreasing: every point represents one dataset; the x-axis shows the reward of MÊLÁr, the y-axis shows e-decreasing. and red dots represent statistically significant runs.
Reward for e-decreasing. 0.1
0.8
0.6
0.4
(Right) MÉLÉE vs MÉLÉE using only the calibrated prediction probabilities (x- axis). MÉLÉE gets an ad- ditional leverage when us- ing all the features.
MELÉE wins 147 datasets
All features wins on 85 datasets Calibration wins on datasets
e-decreasing wins 124 datasets
0.0
Reward MÉLÉE,
Reward for MÉLÉE with All Features
Figure 4: Scatterplots comparing MÉLÉE the best baseline and variant with fewer features.
and points above to e-decreasing (124 datasets). The remaining 29 had no statistically significant difference.
Finally, consider the effect that the additional features have MÉLÉE'S performance. In partic- ular, we consider version of MÉLÉE with all features (this is the version used in all other exper- iments) with ablated version that only has access to the (calibrated) probabilities of each action from the underlying classifier f. The comparison is shown as a scatter plot in Figure 4 (right). Here, see that the full feature set does provide lift just the calibrated probabilities, with win-minus-loss improvement of 24 by adding additional features from which to learn to explore.
RELATED WORK AND DISCUSSION
The field of meta-learning based on the idea of replacing hand-engineered learning heuristics with heuristics learned from data. One of the most relevant settings for meta-learning to ours is active learning, in which one aims to learn decision function to decide which examples, from pool of unlabeled examples, should be labeled. Past approaches to meta- meta-learning for active learning include reinforcement learning-basse strategies (Woodward & Finn 2017 Fang et al.) 2017), imita- tion learning- based strategies (Bachman et al. 2017), and batch supervised learning-based strategies (Konyuskoova et al.] 2017). Similar approaches have been used to learn heuristics for optimiza- tion (Li & Malik| 2016 Andrychowicz et al. 2016), multiarm (non-contextual) bandits Maes et al. (2012), and neural architecture search (Zoph & Le 2016), recently mostly based on (deep) rein- forcement learning. While meta-learning for contextual bandits is most similar to meta-learning for

---

Under review as a conference paper at ICLR 2020
active learning, there is fundamental difference that makes it significantly more challenging: in active learning, the goal is to select as few examples as you can to learn, so by definition the horizon is short; in contextual bandits, learning to explore is fundamentally a long-horizen problem, because what matters is not immediate reward but long term learning.
In reinforcement learning. Gupta et al. (2018) investigated the task of meta-learning exploration strategy for a distribution of related tasks by learning a latent exploration space. Similarly, Xu et al. (2018) proposed teacher-student approach for learning do exploration in off-policy reinforce- ment learning. While these approaches are effective if the distribution of tasks is very similar and the state space is shared among different tasks, they fail generalize when the tasks are different. Our approach targets an easier problem than exploration in full reinforcement learning environments, and can generalize well across wide range of different tasks with completely unrelated features spaces.
There has also been substantial amount of work on constructing "good" exploration policies, in problems of varying complexity: traditional bandit settings (Karnin & Anava, (016)), contextual bandits (Fraud al. 2016) and reinforcement learning (Osband et al. (0066). both bandit set- tings, most of this work has focused on the learning theory aspect of exploration: what exploration distributions guarantee that learning will succeed (with high probability)? ) MÉLÉE, lacks such guar- antees: in particular, if the data distribution of the observed contexts (o(ft)) in some test problem differs substantially from that on which MÅLÁR was trained, we can say nothing about the quality of the learned exploration. Nevertheless, despite fairly substantial distribution mismatch (synthetic + real-world), MÉLÉE works well in practice, and our stylized theory (4) suggests that there may be an interesting avenue for developing strong theoretical results for contextual bandit learning with learned exploration policies, and perhaps other meta-learning problems.
In conclusion, we presented MÉLÉE, a meta-learning algorithm for learning exploration policies in the contextual bandit setting. MÉLÉE enjoys no-regret guarantees, and empirically it outperforms alternative exploration algorithm most settings. One limitation of MÉLÉE is the computational resources required during the offline training phase on the synthetic datasets. In the future, we will work on improving the computational efficiency for MÈLÉE in the offline training phase and scale the experimental analysis to problems with larger number of classes.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. Tam- ing the monster: fast and simple algorithm for contextual bandits. In In Proceedings of the 31st International Conference on Machine Learning (ICML-14, pp. 1638-1646, 2014.
Marein Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pp. 3981-3989, 2016.
Peter Auer. Using confidence bounds for exploitationnexxloraiio trade-offs. The Journal of Ma- chine Learning Research, 3:397-422, 2003.
Philip Bachman, Alessandro Sordoni, and Adam Trischler. Learning algorithms for active learning. In ICML, 2017.
Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In Pro- ceedings of the 1 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 129-138 138.138.44 ACM, 2009.
Alberto Bietti, Alekh Agarwal, and John Langford. Contextual Bandit Bake-off. working paper or preprint, May 2018.
Avrim Blum, Adam Kalai, and John Langford. Beating the hold-out: Bounds for k-fold and progres- sive cross- validation. In Proceedings of the twelfth annual conference on Computational learning theory, pp. 203-208. ACM, 1999.
Leo Breiman. Random forests. Mach. Learn., 45(1):5-32, October 2001. ISSN 0885-6125. doi: 10.1023/A:1010033444433
10

---

Under review as a conference paper at ICLR 2020
Kai- Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé, III, and John Langford. Learning to search better than your teacher. In Proceedings of the 32Nd International Confer- International Conference on Machine Learning Volume 37, ICML, pp. 2058-2066 Jorg. 2015.
Hal Daumé, III, John Langford, and Daniel Mareu. Search-based structured prediction. Machine Learning, 75(3):297-325, Jun 2009. ISSN 1573-0565. doi: 10.1007/s109994-009
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. arXiv preprini arXiv: 106. 2369, 2011.
Meng Fang, Yuan Li, and Trevor Cohn. Learning how to active learn: A deep reinforcement learning approach. In EMNLP, 2017.
Raphal Fraud, Robin Allesiardo, Tanguy Urvoy, and Fabrice Clrot. Random forest for the contex- tual bandit problem. In Arthur Gretton and Christian C. Robert (eds.), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 93-101, Cadiz, Spain, 09-11 May 2016. PMLR.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. arXiv preprint arXiv:180..07245. 2018.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 153-4): 2016.
Leslie Pack Kaelbling. Associative reinforcement learning: Functions ink-dnf. 15(3):279-293 1994.
Machine Learning,
Sham M. Kakade, Shai Shalev-Shwart, and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In ICML, 2008.
Zohar S Karnin and Oren Anava. Multi-armed bandits: Competing with optimal sequences. In
D. D. Lee, M. Sugiyama, U. V. Luxburg. I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 199-207. Curran Associates, Inc., 2016.
Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua. Learning active learning from data. In Advances in Neural Information Processing Systems, 2017.
John Langford and Bianca Zadrozny. Relating reinforcement learning performance classification performance. In Proceedings of the 22nd international conference on Machine learning, pp- 473-480. ACM, 2005.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems 20, pp. 817-824. Curran Associates, Inc., 2008.
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv: 2016.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10 pp. 661-670, New York, NY, USA, 2010a. ACM. ISBN 978-1- 60558-799-8 doi: 10. 00.1145/1772690.1772
Wei Li, Xuerui Wang, Ruofei Zhang, Ying Cui, Jianchang Mao, and Rong Jin. Exploitation and exploration in a performance based contextual advertising system. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '10, pp. 27-36, New York, NY, USA, 2010b. ACM.
Hsuan-Ties Lin, Chih-Jen Lin, and Ruby C. Weng. A note platt's probabilistic outputs for support vector machines. Machine Learning, 68(3):267-22 276, Oct 2007. ISSN 1573-0565. doi:

---

Under review as a conference paper at ICLR 2020
Francis Maes, Louis Wehenkel, and Damien Ernst. Meta-leaming of exploration/explotttionn strate- gies: The multi-armed bandit case. In International Conference on Agents and Artificial Intelli- gence, pp. 100-115. Springer, 2012.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In D. D. Lee, M. Sugiyama, U. V. Luxburg. I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4026 4034. Curran Associates, Inc., 2016.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. The Journal Machine Learning Research, 15(1):2009-2053, 2014.
John C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In ADVANCES LARGE MARGIN CLASSIFIERS, pp. 61-74. MIT Press, 1999.
Tao Qin and Tie- Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013. URL http: wwtp/ogg//a///eo 2597
Stéphane Ross and Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning, arXiv preprint 10X6v:1406.500 5979, 2014.
Stéphane Ross, Geoffrey Gordon, and Andrew Bagnell, A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligncce and Statistics, volume 15 of Proceedings of Machine Learn- ing Research, pp. 627-635, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In Advances in neural information processing xystems, pp. 1038-1044, 1996.
Richard S. Sutton and Andrew G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1st edition, 1998. ISBN 0262193981.
Mark Woodward and Chelsea Finn. Active one-shot learning. arXiv preprint arXiv: 172.v:170,.06559, 2017.
Tianbing Xu, Qiang Liu, Liang Zhao, Wei Xu, and Jian Peng. Learning to explore with meta-policy 2018.
gradient. arXiv preprint
Chicheng Zhang, Alekh Agarwal, Hal Daumé, III, John Langford, and Sahand N Negahban. Warm- starting contextual bandits: Robustly combining supervised and bandit feedback. In ICML, 2019.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint 1.10057,, 2016.
12

---

Under review as a conference paper at ICLR 2020
Supplementary Material For:
Learning Effective Exploration Strategies for Contextual Bandits
A STYLIZED TEST-TIME ANALYSIS FOR BANDITRON: DETAILS
The BANDITRONMÈLÉE algorithm is specified in Alg 2
The is exactly the same the typical test time behavior, except it uses a BANDITRON-Ly strategy for learning the underlying classifier f in the place of POLOPT. POLICYYLIMINATIONNEE policy) and μ E (0, (22K) an added uniform exploration parameter. The BANDITRON learns a linear multi-class classifier parameterized by weight matrix of size KxD, where D is the input dimensionality. The BANDITRON assumes a pure multi-class setting in which the reward for one ("correct") action is and the reward for all other actions is zero.
takes arguments: (the learned exploration
At each round t, prediction âe is made according to ft (summarized by W²). We then define an exploration distribution that "most of the time" acts according π Tff..), but smooths each action with lr probability. The chosen action a, is sampled from this distribution and binary reward is observed. The weights of the BANDITRON are updated according to the BANDITRON update rule using U..
Algorithm 2 BANDITRONMÉLÉÉ (g.
1: initialize W = 0 E IR KDD
2: for rounds: f 11...... do
3: observe Iy E DRD
4: compute å, = f(() argmax (W'z1);
5: define (a) = + (1 -a)) T(W x1]]
6: sample ~ Q"
7:
observe reward r (at) {0,1)
8: define O E RRD as:
U1. = [[rela))=
1 [ā, a)
("(a)
9: update W++
W Tr
10:
end for
The only difference between BANDITRONMÉLÉE and the original BANDITRON is the introduction of æ in the sampling distribution. The original algorithm achieves the following mistake bound shown below, which depends on the notion multi-class hinge-loss. In particular, the hinge-loss of W on (x, r) is E(W, (I. r)) maXayaa max {0, (Wx).- + (Wx)a). where a* is the for which r(a) = 1. The overall binge-loss L is the sum of l over the sequence of examples.
Theorem (Thm. 1 and Corr. 2 Kakade et al. (2008) Assume that for the sequence of exam- ples, (I1,T1), (22, T2),.... (ZT, TT), we have, for all t,
æ s 1. Let W* be any matrix, let L be the cumulative hinge-loss of W*, and let D ||? be the complexity of W*. The number of mistakes M made by the BANDITRON satisfies
EM < L KpT 3 max {D. {
(DVVDTK VDLjU
(4)
where the expectation is taken with respect to the randomness of the algorithm. Furthermore, in a low noise setting (there exists W with fixed complexity d and loss L S O(VDKT)) then by setting μ (DK,T we obtain EM S O(VKDT).
We can prove an analogous result for BANDITRONMÈLÉÉ. The key quantity that will control how much improves the execution of BANDITRONMÁLLÃ is how much л improves on fa when fa is wrong. In particular, let 7
1[x,] be the edge of T (ft,-) over f, and let r = 7 Σ ET4k be an overall measure of the edge. (If π. does nothing,
Pr(r:(T(fe,
1)]a;] - (ff))(f((x:))
then all 7 = 0 and I = 1.) Given this quantity, we can prove the following Theorem 2
Proof: [sketch] The proof is small modification of the original proof of Theorem The only change is that in the original proof, the following bound is used: E, |0*||// [|]///|[]]]]]] 1+ 1/p 2/p.
13

---

Under review as a conference paper at ICLR 2020
We use, instead: |,/1099///|/a// S 11+ R
1 1177
23 1i
The rest of the proof goes through
P
identically.
A.1 DETAILS OF SYNTHETIC DATASETS
We generate datasets with uniformly distributed class conditional distributions. We generate 2D datasets by first sampling a random variable representing the Bayes classification error. The Bayes error is sampled uniformly from the interval 0.0 to 0.5. Next, we generate a balanced dataset where the data for each class lies within unit rectangle and sampled uniformly. We overlap the sampling rectangular regions to generate a dataset with the desired Bayes error selected in the first step.
A.2 IMPLEMENTATION DETAILS
Our implementation is based on scikit-leam (Pedregosa et al. 2011). We fix the training time ploration parameter to 0.1. We train the exploration policy т on 82 synthetic datasets each of size 3000 with uniform class conditional distributions, total of 246k samples [A.I]. We train using a linear classifier [Breiman (2001) and set the hyper-parameters for the learning rate, and data scal- ing methods using three-fold cross-validation on the whole meta-training dataset. For the classifier class F, we use a linear model trained with stochastic gradient descent. We standardize all features to zero mean and unit variance, or scale the features to lie between zero and one. To select between the two scaling methods, and tune the classifier's i learning rate, we use three-fold cross-validation on a small fully supervised training set of size 30 samples. The same set is used to calibrate the predicted probabilities of f.-
A.3 LIST OF DATASETS
The datasets we used can be accessed at ltt potttss:/www... orgenmmoor////iii/ The list of (id, size) pairs below shows the (id for the datasets we used and the dataset size in number of examples:
(46,100) (716, 100) (726, 100) (754, 100) (762, 100) (768, 100) (775, 100) (783, 100) (789, 100)
(808, 100) (812, 100) (828, 100) (829, 100) (850, 100) (865, 100) (868, 100) (875, 100) (876, 100)
(878, 100) (916, 100) (922, 100) (932, 100) (1473, 100) (965, 101) (1064, 101) (956. 106) (1061,
107) (771, 108) (736, 111) (448, 120) (782, 120) (1455, 120) (1059, 121) (1441, 123) (714, 125)
(867, 130) (924, 130) (1075, 130) (1141, 130) (885, 131) (444, 132) (921, 132) (974, 132) (719,
137) (1013, 138) (1151, (784, 140) (1045, 145) (1066, 145) (1125, 146) (902, 147) (1006, 148)
(969, 150) (955, 151) (1026, 155) (745, 159) (756, 159) (1085, 159) (1054, 161) (748, 163) (747,
167) (973, 178) (463, 180) (801, 185) (1164, 185) (788, 186) (1154, 187) (941, 189) (1131, 193)
(753, 194) (1012, 194) (1155, 195) (1488, 195) (446, 200) (721, 200) (1124, 201) (1132, 203) (40,
208) (733, 209) (796, 209) (996, 214) (1005, 214) (895, 222) (1412, 226) (820, 235) (851, 240)
(464, 250) (730, 250) (732, 250) (744, 250) (746, 250) (763, 250) (769, 250) (773, 250) (776, 250)
(793, 250) (794, 250) (830, 250) (832, 250) (834, 250) (863, 250) (873, 250) (877, 250) (911, 250)
(918, 250) (933, 250) (935, 250) (1136, 250) (778, 252) (1442, 253) (1449, 253) (1159, 259) (450,
264) (811, 264) (336, 267) (1152, 267) (53, 270) (1073, 274) (1156, 275) (880, 284) (1121, 294)
(43, 306) (818, 310) (915, 315) (1157, 321) (1162, 322) (925, 323) (1140, 324) (1144, 329) (1011,
336) (1147, 337) (1133, 347) (337, 349) (59, 351) (1135, 355) (1143, 363) (1048, 369) (860, 380)
(1129, 384) (1163, 386) (900, 400) (906, 400) (907, 400) (908, 400) (909, 400) (1025, 400) (1071,
403) (1123, 405) (1160, 410) (1126, 412) (1122, 413) (1127, 421) (764, 450) (1065, 458) (1149,
458) (1498, 462) (724, 468) (814, 468) (1148, 468) (1150, 470) (765, 475) (767, 475) (1153, 484)
(742, 500) (749, 500) (750. 500) (766, 500) (779, 500) (792, 500) (805, 500) (824, 500) (838, 500)
(855, 500) (869, 500) (870, 500) (879, 500) (884, 500) (886, 500) (888, 500) (896, 500) (920, 500)
(926, 500) (936, 500) (937, 500) (943, 500) (987, 500) (1470, 500) (825, 506) (853, 506) (872, 506)
(717, 508) (1063, 522) (954, 531) (1467, 540) (1165, 542) (1137, 546) (335, 554) (333, 556) (947,
559) (949, 559) (950, 559) (951, 559) (826, 576) (1004, 600) (334, 601) (1158, 604) (770, 625)
(997, 625) (1145, 630) (1443, 661) (774, 662) (795, 662) (827, 662) (931, 662) (292, 690) (1451,
705) (1464, 748) (37, 768) (1014, 797) (970, 841) (994, 846) (841, 950) (50, 958) (1016, 990)
(31, 1000) (715, 1000) (718, 1000) (723, 1000) (740, 1000) (743, 1000) (751, 1000) (797, 1000)
(799, 1000) (806, 1000) (813, 1000) (837, 1000) (845, 1000) (849, 1000) (866, 1000) (903, 1000)
(904, 1000) (910, 1000) (912, 1000) (913, 1000) (917, 1000) (741, 1024) (1444, 1043) (1453, 1077)
14

---

Under review as a conference paper at ICLR 2020
(1068, 1109) (934, 1156) (1049, 1458) (1454, 1458) (983, 1473) (1128, 1545) (1130, 1545) (1138,
1545) (1139, 1545) (1142, 1545) (1146, 1545) (1161, 1545) (1166, 1545) (1050, 1563) (991, 1728)
(962, 2000) (971, 2000) (978, 2000) (995, 2000) (1020, 2000) (1022, 2000) (914, 2001) (1067,
2109) (772, 2178) (948, 2178) (958, 2310) (312, 2407) (1487, 2534) (737, 3107) (953, 3190) (3, 3196) (1038, 3468) (871, 3848) (728, 4052) (720, 4177) (1043, 4562) (44, 4601) (979, 5000) (1460, 5300) (1489, 5404) (1021, 5473) (1069, 5589) (980, 5620) (847, 6574) (1116, 6598) (803, 7129)
(1496, 7400) (725, 8192) (735, 8192) (752, 8192) (761, 8192) (807, 8192)
A.4 BASELINE EXPLORATION ALGORITHMS
Our experiments aim to determine how MÉLÉE compares to other standard exploration strategies. In particular, we compare to:
e-greedy:
With probability explore uniformly at random; with probability 1 - act greedily according to fe (Sutton 1996). Experimentally, we found c = 0 optimal on average, consistent with the results of Bietti et al. (2018).
c-decreasing: selects a random action with probabilities e,, where e, = <n/t, =n/t, en E E00, 1] and t the index of the current round. In experiments we 6n 0.1. (Sutton & Barto 1998)
Exponentiated Gradient c-greedy: maintains a set of candidate values for c-greedy exploration. At each iteration, it runs sampling procedure to select new e from finite set of candidates. The probabilities associated with the candidates are initialized uniformly and updated with the Exponentiated Gradient (EG) algorithm. Following Li al. (2010b), we use the candidate set
{a = 0.05xi + i = 1, ... 10} for c.
LinUCB: Maintains confidence bounds for reward payoffs and selects actions with the highest confidence bound. It is impractical to run "as is" due to high-dimensional matrix inversions. We
use diagonal approximation to the covariance when the dimensions exceeds 150. (Li al., 20TOa)
7-first: Explore uniformly on the first fraction of the data; after that, act greedily.
Cover: Maintains a uniform distribution over a fixed number of policies. The policies are used to approximate covering distribution over policies that are good for both exploration and exploita- tion (Agarwal et al.] 2014).
Cover Non-Uniform: similar to Cover, but reduces the level of exploration of Cover be more competitive with the Greedy method. Cover-Nu doesn't 't add extra exploration beyond the actions chose by the covering policies (Bietti al., 2018).
In all cases, we select the best hyperparameters for each exploration algorithm following Bietti et al. (2018). These hyperparameters are: the choice of in e-greedy, J in -irsst the number of bags, and the tolerance & for Cover and Cover-NU. We set = 0.0, T = 0.02, bag size = 16, and vp = 0.1.
15


Reviews:
[{"review_id": "rkg1o4HTYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "This paper proposes a meta-learning algorithm to solve the problem of exploration in a contextual bandit task using prior knowledge. This is analogous to how exploration strategies have been learned from past data in the meta-learning for RL (for example, [1]). Their algorithm simulates contextual bandit problems from fully labeled data and uses it to learn an exploration policy that works well on tasks with bandit feedback. The training step for the exploration policy builds upon the AggreVaTe algorithm, where policy optimization is performed on the history augmented data by using a separate roll-out policy to estimate the advantage of a particular action for a particular context, from the point of view of regret minimization.  In terms of theory, they show that by using specific algorithms (example, Banditron) as the inner policy optimization procedure, a no-regret algorithm can be obtained.   \n\nSome of my questions are:\n\n1. The method seems a bit hacky to me, for example, it requires calibration of f, requires access to test time examples, and it is unclear why this should be needed if an algorithm were provably good. Can this be elaborated upon?\n\n2. Section 3.2 and Algorithm 1 are very unclear, and it requires multiple passes to be able to understand in the current draft. I encourage the authors to revise these sections for increasing clarity. \n\n3. In Algorithm 1, which is the exploitation policy? The theory section says \" In particular, we first relate the\nregret of the learner in line 16 to the overall regret of $pi$\", but line 16 in the algorithm refers to \"end for\". Can the authors clearly point me to the location where the exploitation policy is mentioned in the algorithm? What is the precise definition of $\\pi_n$ (Line 15), and how does it relate to the average exploration policy and the policy $\\bar{\\pi}$ used in Theorem 1. These definitions have not been made clear, making this hard to follow. What is the optimal policy $\\pi^*$, in particular, what is the formal meaning of \"which effectively cheats” at training time by looking at the true labels.\"\n\n4. The paper lacks discussion about how the roll-out and the roll-in policy affect regret bounds, and what assumption about these is used to derive no-regret guarantees. Can this be described? \n \nOverall, my recommendation currently is reject. I feel that the paper tries to theoretically analyse an interesting problem, however, at this point the paper is very hard to follow and not complete. I encourage the authors to revise the details and improve clarity. Also, it would be good if the authors can explain the significance of the results at the cost of added complexity.\n\nReferences:\n[1] Meta-exploration of structured exploration strategies, Gupta et.al. NeuRIPS 2018", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eaIvcAYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "•\tSummary\n    This paper introduced a meta-learning algorithm for the contextual bandit problem, MELEE, which learns an exploration policy based on simulated and synthetic contextual bandit tasks. The training is mainly divided into two steps. In step one, they proposed to train a policy optimizer, which maps features and actions to rewards. This policy optimizer could be used to reveal the most valuable action to take according to the modeled reward. All possible actions and their corresponding values are revealed to the policy optimizer because of the existing ground-truth labels in the synthetic dataset. The policy optimizer would then suggest which action to take. The algorithm takes the action in an  greedy fashion, i.e. with probability  it will follow the suggestion and with probability  it will sample it uniformly at random. The policy optimizer, historical actions and the taken actions are appended to the training set for training the exploration policy  in the next step. The procedure in step one is proposed to be done in  rounds. In step two, the training set is used for training an exploration policy  . During testing, the contexts are drawn from the real world, the policy optimizer will first evaluate the whole history and the exploration policy will generate actions with the input from the policy optimizer and the context. The algorithm suggests the action to explore in an  greedy fashion. The proposed algorithm is evaluated on a dataset for learning to rank, and 300 synthetic datasets. It shows better performances in most cases.\n    I am critical about the paper  because 1) the experiments show that all more recently published exploration methods are worse than weak baselines, for which it lacks enough justification and convincing explanations. 2) the experiments are difficult to understand with only citation to publications. Detailed information of the datasets, tasks, procedures is missing.\n•\tMain arguments\n    The paper is in general hard to follow because of too many citations of the previous works without simple explanations. It refers to the imitation algorithm, AggreVate, which is an instantiate of meta-learning for contextual bandits. Meanwhile, they failed to clarify the difference between the proposed algorithm and the existing one, making the training algorithm part confusing. The major concern lies in the experiment section, I can not see big performance difference between the proposed method and the  greedy based methods in Figure 1 (left) as 1) the variances are large 2) there are overlapping . It is surprising to see all recently published method are worse than the classical  greedy method. These results may require deeper investigations. In addiction, the used datasets in experiments are mentioned without any details and task definitions, which makes the experiments part unclear and the result not that convincing. Below are some other inconsistencies in the paper:\n1.\tI had a hard time to understand what the function  means. In Section 2,  is used to map user feature to predicted rewards for actions, i.e.  is a function with user features and actions as input and reward as output. However, in equation 1, it only takes user feature as input. In Section 5.1,  is called a classifier (I regard it as a variant of function  ). Both are not consistent with the mapping definition when first formally defined. This point confuses me so that I cannot fully understand what the POLOPT does as the function  is the output of it.\n2.\tBy the end of section 2, the paper claims that they used direct method for it simplicity and unbiased property. However, as verified in [1], the direct method is biased with low variance whereas IPS is unbiased with high variance.\n[1] Dudık, Miroslav, John Langford, and Lihong Li. “Doubly Robust Policy Evaluation and Learning.”\n\n\n•\tThings to improve that did not impact the score\na.\tclear definition of the introduced notations, including the ones in algorithms 1.\n•\tQuestions:\na.\tWhat is  ?\nb.\tWhat is POLOPT?\nc.\tWhy do you choose AggreVate?\nd.\tWill the performance change if using any other methods instead of direct method for policy optimizer?\ne.\tWhat is roll-out policy in line 8 of Algorithm 1? (In text only the roll-out value is defined.)\nf.\tWhat will happen if the roll-in action is different from the behavior in test time?\ng.\tHow is exploration policy trained?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Hyxr-LhDYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "This paper presents an approach to learning exploration strategies for contextual bandits by meta-learning the exploration strategy across synthetic tasks. The approach is shown to outperform alternative exploration strategies on a learning to rank task as well as simulated bandit problems derived from classification tasks.\n\nApplying meta-learning to this setting is a novel and interesting approach and appears to have nice results.\n\nThe main issue with this paper is that the presentation of the algorithm is vague and it is difficult to determine what the algorithm actually does. Here are a few of my main questions:\n\n1. The algorithm is dependent on a function class F and PolOpt which finds an f in F with low expected regret. However, F is not really defined. In equation 1, it appears to directly output an action. Below that, it says \"For example, F may be... mapping user features x in X to predicted rewards for actoins a in [K].\" In Section 5.1, the policy is using a probability distribution over actions from f, the entropy of the predicted probability distribution, and a one hot encoding for the predicted action f(a). What is the class F? Is it predicting a probability distribution and an action? What's the one hot encoding of the predicted action, is that an action sampled from the probability distribution of F?\n\n2. Section 3.1 describes the test time behavior of MELEE. They state the goal is to learn an exploration policy pi, and specifically state that pi can \"not depend directly on the context x\" so it \"only learns to explore and not also to solve the underlying task-dependent classification problem\". However, in the equations, pi is a function of x_t. The algorithm is motivated by the exploration exploitation trade-off problem, however there's no policy doing any exploiting here.  When does exploitation happen? Is it a separate policy? How is it trained and when is it used? The decision of when to explore and when to exploit is the key question here and it's unclear how that is happening in this algorithm. It's unclear to me how the algorithm achieves good rewards on the task without any attempt at exploitation.\n\n3. What are the rollouts and expert cost-to-go in this setting? In section 3.2, you say the algorithm asks what would the \"long time reward look like if I were to take this action.\" So are you looking at how that action would affect future exploitation? You say there's an optimal reference policy* which effectively cheats by looking at the true labels. Is this policy taking the action with the highest reward at each state? Or is it looking at the effects of exploration on the learned policy? The start of page 4 says that the \"cost-to-go Q of the expert\" is observed, why would the expert in a bandit have a cost-to-go? In the section on roll-out values, you say that you evaluate the value of taking this action and then assuming all future actions were taken by the expert. But this then precludes there being any effect of this action on the policy and any exploration effect. Are you solely optimizing for the one step reward? In the algorithm, the rollouts computed on line 8 don't appear to be used anywhere.\n\n4. How are the synthetic tasks setup? There are almost no details other than that they are two dimensional and have uniformly distributed class conditional distributions. How are they related to the learning to rank task you perform at the end? How are they related to the other tasks you evaluate on? It seems like the choice of synthetic tasks would be important to what the algorithm learns, so it's important to be clear on what these tasks were and how closely they match the target tasks. It would be even better to show results with different sets of synthetic tasks that are more or less similar to the target tasks.\n\n5. In the results, you say you limit the number of labels to two extremes, 0 and 4. I assume you mean you limit it to just those two labels. What do you do with the other data? Do you drop it or do you map it to these two labels?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces MELEE, a meta-learning procedure for contextual bandits. In particular, MELEE learns how to explore by training on datasets with full-information about what every reward each action would obtain (e.g., using classification datasets). The idea is strongly related to imitation learning, and a regret bound is demonstrated for the procedure that comes from that literature. Experiments are performed. 

Perhaps due to the generality in which the algorithm was presented, reviewers found some parts of the work unintuitive and difficult to follow. The work may greatly benefit from having an explicit running example for F and pi and how it evolves during training. Some reviewers were not impressed by the experimental results relative to epsilon-greedy. Yes, epsilon-greedy is a strong baseline, but MELEE introduces significant technical debt and data infrastructure so it seems fair to expect a sizable bump over epsilon-greedy or else why is it worth it?

Perhaps with revisions and experiments within a domain that justify its complexity, this paper may be suitable at another venue. But it is not deemed acceptable at this time, Reject.  
Decision: Reject