{'fraction_non_alphanumeric': 0.03077997207261121, 'fraction_numerical': 0.008677438659485339, 'mean_word_length': 4.571968433922419, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Safe Exploration for Optimizing Contextual Bandits

Contextual bandit problems are a natural fit for many information retrieval tasks, such as learning to rank, text classification, recommendation, etc. However, existing learning methods for contextual bandit problems have one of two drawbacks: they either do not explore the space of all possible document rankings (i.e., actions) and, thus, may miss the optimal ranking, or they present suboptimal rankings to a user and, thus, may harm the user experience. We introduce a new learning method for contextual bandit problems, Safe Exploration Algorithm (SEA), which overcomes the above drawbacks. SEA starts by using a baseline (or production) ranking system (i.e., policy), which does not harm the user experience and, thus, is safe to execute, but has suboptimal performance and, thus, needs to be improved. Then SEA uses counterfactual learning to learn a new policy based on the behavior of the baseline policy. SEA also uses high-confidence off-policy evaluation to estimate the performance of the newly learned policy. Once the performance of the newly learned policy is at least as good as the performance of the baseline policy, SEA starts using the new policy to execute new actions, allowing it to actively explore favorable regions of the action space. This way, SEA never performs worse than the baseline policy and, thus, does not harm the user experience, while still exploring the action space and, thus, being able to find an optimal policy. Our experiments using text classification and document retrieval confirm the above by comparing SEA (and a boundless variant called BSEA) to online and offline learning methods for contextual bandit problems.


INTRODUCTION
A multi-armed bandit problem is a problem in which a limited number of resources must be allocated between alternative choices so as to maximize their expected gain. In contextual bandit problems, when making a choice, a representation of the context is available to inform the decision. Contextual bandit problems are a natural framework to capture a range of Information Retrieval (IR) tasks [1,10,14]. Example tasks to which contextual bandits have been applied include news recommendation [31], text classification [43], ad placement [28], and online learning to rank [13]. For example, in online Learning to Rank (LTR) (see Figure 1): (1) a user issues a query, (2) a search engine presents a ranked document list, and (3) clicks on the documents are recorded as feedback.
The interactive nature of this problem makes it an ideal application for the contextual bandit framework. The LTR model is a decision-making policy π , the ranked document lists it produces are actions, the user is the context or environment, and clicks are the reward signal.
There are two major classes of algorithms to maximize the reward of a contextual bandit policy π . The first are online algorithms, which optimize a policy while it is being executed [2,24,31,47]. The second are offline algorithms, which optimize a policy based on data that was collected using an existing logging policy, often called π 0 [39,43]. Online learning methods for contextual bandits are widely studied and there are many known algorithms to solve this problem. E.g., popular algorithms include ϵ-greedy, LinUCB [31] and Thompson Sampling [2]. Despite their attractive properties, the adoption of online learning methods for contextual bandits in production systems has been limited. Especially in the early stages of learning, online algorithms may perform actions that are suboptimal and, thus, hurt the user experience. E.g., in online LTR it is risky to present suboptimal rankings of documents [34,46].
Offline learning from logged feedback [11,12,39,43] has been proposed as a solution to this problem. Using an existing and already deployed logging policy, one only takes actions from that logging policy to collect bandit feedback. Using this collected data, a new policy is then learned offline in an unbiased manner. This learning process is safe in the sense that the new policy is not executed and, thus, the user experience is not affected. The drawback of offline learning, however, is that it relies on the deployed logging policy, which never changes by design. Due to this, there may be areas in the action space left unexplored, i.e., bandit feedback may be missing for those areas. In IR terms, potentially high quality document rankings might never be presented to users and the corresponding user interactions will never be observed.
In this paper, we propose a method that performs exploration of the action space in contextual bandit problems, but does this exploration safely, that is, without hurting the user experience. In our proposed solution, called Safe Exploration Algorithm (SEA), we use an already deployed logging policy which is safe, static but suboptimal, as a warm-start for learning a new policy. As soon as SEA is confident that the performance of the new policy does not fall below that of the logging policy, it starts executing actions from the new policy, thus, exploring the action space. In the context of LTR, this means that SEA is capable of exploring and presenting new rankings to users, gathering feedback for rankings that might otherwise have never been presented. This enables SEA to trade off various strengths and weaknesses of both online and offline learning.
We note that periodic deployment of a policy, after a successfull evaluation on held-out data, is a common practice in industry. In our experiments we include a boundless version of SEA, called BSEA, which represents such a deployment pipeline. What SEA adds over and above a standard deployment procedure is: (1) it comes with a formal proof of safety, i.e., with high probability the performance of SEA will be at least as good as that of a baseline policy (Section 3.4); and (2) we introduce a computationally efficient manner for computing high-confidence off-policy bounds (Section 3.3).
The research questions we address in this paper are: (RQ1) Is SEA safe? I.e., does it always perform at least as good as a baseline policy? (RQ2) Does SEA provide a better user experience during training than offline or online learning methods? I.e., does it accumulate a higher reward during training? (RQ3) Does SEA, which explores the action space, learn a more effective policy compared to offline learning methods, which do not perform exploration?
Our key technical contributions in this paper are: (1) we introduce SEA and show it to be safe: its performance never falls below that of a baseline policy; (2) we show that SEA improves the user experience: it provides higher cumulative reward during training than both offline and online methods; and (3) we show that a policy learned with SEA, which is capable of exploring new actions, outperforms that of offline methods, which are incapable of exploration.

Contextual bandits
In online LTR we try to optimize the parameters of a ranking model such that it places relevant items at the top of the ranked list. We can view the ranking model as a decision-making policy. When a new query arrives, the policy takes an action: it displays one possible ranked list to the user. The user then decides to click on documents shown in the ranked list, thus providing a reward signal. More formally, we consider the following contextual bandit framework. At each round t: (1) The environment announces an m-dimensional context vector x t ∈ X. In IR terms, this would be a user (environment) issuing a query (context vector). (2) A policy π samples an action a t ∈ A, one of n possible actions, conditioned on x t : a t ∼ π (· | x t ). In IR terms, this would be a ranking model (policy) producing a ranked list (action). (3) The environment announces only the reward r t,a t for the chosen action a t , and not for other possible actions that the policy could have taken. We assume that r ∈ [0, 1]. In IR terms, this reward signal could be clicks on documents.
This learning setup is inherently different from supervised learning, where rewards for all possible actions are known. We only observe rewards for actions that the policy has taken. The setting is referred to as partial-label problem [25], associative bandit problem [40] or associative reinforcement learning [24]. In the context of LTR, this means that we do not know the optimal ranked list but can only observe a reward signal for rankings that our policy chooses to display. There are two major classes of algorithms for learning a contextual bandit policy. The first are online algorithms that optimize the policy while it is being executed [2,24,31,47]. Algorithms of this class explore the space of possible actions but may harm the user experience, because suboptimal actions could be executed. The second are offline algorithms, which optimize a policy based on data that was collected using an existing logging policy [39,43]. Algorithms of this class are safe as the newly learned policy is not executed and, thus, there is no risk of hurting the user experience. However, offline algorithms are incapable of exploring the action space, which may harm the performance of the learned model. In this work we build on the second class of algorithms; see below.

Offline learning from logged bandit feedback
Offline learning algorithms collect bandit feedback using an existing logging policy, which we call a baseline policy π b (also referred to as π 0 in the literature [22,43,44]). This feedback is collected in the following form, where at time t we have: where x i is the observed context vector, a i is the action taken by the baseline policy, r i,a i ∈ [0, 1] is the reward given by the environment, and p i is the propensity score for action a i . The propensity score is the probability of the baseline policy taking the logged action, that is, To learn a new policy π w from the collected bandit feedback, the following maximization problem has to be solved [22]: This optimization problem is solved via p i and update the weights of π w using SGD. We refer to this offline learning method as Inverse Propensity Scoring (IPS) [22].

High-confidence off-policy evaluation
In an offline learning setting, a newly learned policy π w is never executed, so its performance cannot be measured directly. Instead, we estimate its performance using the collected bandit feedback D t at time t. The estimated reward of a policy π can be written as [32]: This estimate suffers from high variance, especially when the propensity scores are small. To resolve this issue, Thomas et al. [45] propose several high-confidence off-policy estimators. These estimators first calculate a confidence interval around the policy's performance and then use the lower bound on this performance for off-policy evaluation. The high-confidence off-policy estimator that we use is based on the Maurer & Pontill empirical Bernstein inequality. The confidence bound can be written as [45]: where (1 − δ ) ∈ [0, 1] is the confidence level and b is an upper bound onR. When both r and p are bounded, b can be calculated exactly: b = max r min p . The lower confidence bound on the performance of a policy at time t, LCB(π , D t ), can be computed as: Similarly, we compute the upper confidence bound on the performance of a policy as follows: The estimator described in this section provides an effective way to compute a lower and upper bound on the performance of a policy without executing it.
In this paper we build on the estimators designed by Thomas et al. [45], but provide the following contributions: First, we develop SEA, an algorithm for automatic safe exploration by deploying new models (Section 3.2); second, we provide an efficient way to compute the high-confidence bounds (Section 3.3); and, third, we formally prove that SEA is indeed safe (Section 3.4).
We define the notion of safety as part of the learning process (Section 3.1), walk through the Safe Exploration Algorithm (SEA) (Section 3.2), address the problem of efficient off-policy evaluation (Section 3.3), formally prove the safety of SEA (Section 3.4), and then analyse SEA (Section 3.5).

Safety
We use the definition of safety from so-called conservative methods [26,49]. These methods make a key assumption: there exists a baseline policy π b whose actions can always be executed without risk. This assumption is very reasonable in practice. In most industrial settings there exists a production system that we can consider to be the baseline policy. A learning algorithm is considered safe if its performance at any round t is at least as good as the baseline policy. Thus, safety is a concept that is always measured relative to a baseline.
More formally, let us first consider the notion of regret at round t during training. We define the regret at time t as the cumulative difference in reward obtained by executing actions from our policy π compared to a perfect policy π * , one that always chooses the action with maximum reward. For notational simplicity, we denote the action that a policy chooses in response to a context vector x as π (x): A policy π is considered safe if its regret is always at most as large as that of the safe baseline policy π b , i.e., for every t = 1, . . . ,T : In other words, at every time t, we want the average reward of our policy π to be at least as large as the average reward of the baseline policy π b . In practice, we cannot observe the average reward of a policy without executing it. This is problematic because we cannot know if a policy is safe until we execute it. Fortunately, the off-policy estimators described in Section 2.3 provide a way to estimate the performance of a policy without executing it.

A walkthrough of SEA
The Safe Exploration Algorithm (SEA) learns a new policy π w offline from the output of a baseline policy π b using offline learning techniques described in Section 2.2. At each iteration t, SEA estimates the performance of the newly learned policy π w t and the currently deployed policy π d using the high-confidence off-policy evaluators described in Section 2.3. The new policy is only deployed online when its estimated performance is above that of the existing deployed policy. This allows the newly learned policy to take over and start exploring. This only happens once SEA is confident enough that the new policy's performance will be satisfactory and safe to execute. The pseudocode for the Safe Exploration Algorithm (SEA) is provided in Algorithm 1. SEA starts from a baseline policy π b (Line 1) and a new policy that we wish to optimize, π w 0 (Line 2). At the start, SEA deploys the policy π d , which is initialized to the baseline policy (Line 3). At every Algorithm 1 Safe Exploration Algorithm (SEA) 1: π b // Baseline policy (current production system) 2: π w 0 ← π b // Policy to be learned (initialized with baseline weights) 3: π d ← π b // The deployed policy that is executing actions x t ← contextual feature vector at time t 7: Play a t and observe reward r t,a t 10: // Update weights via gradient ascent 12: Compute LCB(π w t , D t ) using Equation 5 13: Compute U CB(π d , D t ) using Equation 6 14: if LCB(π w t , D t ) ≥ U CB(π d , D t ) then 15: π d ← π w t // Deploy new policy only when it is safe to do so 16: end if 17: end for iteration t, a context vector x t is observed (Line 6). SEA draws an action from the deployed policy and computes its propensity score (Lines 7-8). SEA executes the chosen action a t and observes the reward r t (Line 9). The policy π w is then updated via SGD (Line 11). We then update the confidence bounds on the estimated performance for the new policy π w t and the deployed policy π d (Lines 12-13). When the estimated lower bound performance of π w t is better than the estimated upper bound performance of π d (Line 14), we deploy π w t , such that future actions are executed by the newly learned policy instead of the previous deployed policy π d .

Efficient policy evaluation
To implement SEA we use the off-policy estimator described in Section 2.3. Such an implementation will be computationally expensive, because at each round T we have to compute a sum over all t data points collected so far. E.g., in Equation 5, we need to compute the mean at every round t. Therefore, the complexity of applying Equation 5 or 6 would be O (T ) and the complexity of Algorithm 1 would be O T 2 . Recall is the collected log data and that there are |A| possible actions and |X| possible contexts. We can then compute the mean 1 results hold for computing the variance term): where 1[·] is the indicator function.
The key insight here is that the inner sum, r t, a t p t can be efficiently computed online during data collection and is independent of the policy π w that is being evaluated. Specifically, we can create a zero-initialized matrix W ∈ R | A |×|X | where, each time a new data point (x i , a i , r i,a i , p i ) is logged, we update an entry as follows: This results in the following method for computing the mean: which can be orders of magnitude faster to compute when T ≫ |A| · |X|. This is not unreasonable in practice, as the size of interaction logs is usually much larger than the number of users and items.
In addition, we only need to compute the above sum for a and x for which W a,x 0. This enables the use of sparse data structures that can speed up computation even further.

Proof of safety
SEA is an online learning method that we claim to be safe. To show that SEA is actually safe, we bound the probability that a suboptimal policy, one whose expected reward is lower than the expected reward of the deployed policy, will be deployed during the duration of the algorithm.
Theorem 3.1. At any time t, with probability at least 1 − 2δ , SEA will not deploy a suboptimal policy.
Proof. For notational simplicity we write the expected reward of a policy π as: First, from Algorithm 1 we know that we only deploy π w t when LCB(π w t ) > UCB(π d ). Suppose that our confidence bounds do not fail. In this case, it is impossible to deploy a suboptimal policy, Consequently, a suboptimal policy can only be deployed when either the confidence bound estimate on our newly learned policy π w t or our deployed policy π d fails.
The high-confidence off-policy estimators (see Equations 5 and 6) provide a lower and upper bound on the estimated performance. According to Theorem 1 in [45], these confidence bounds hold with probability at least 1 − δ . Conversely, this means that the confidence bounds may fail with probability at most δ : and, as a result, the probability that either the confidence bound on π w t or π d will fail is at most 2δ : Therefore, with probability at least 1 − 2δ , we will not deploy a suboptimal policy. □ In our experiments (see Section 4) we set δ = 0.05, which means that the algorithm is safe with probability at least 1 − 2δ = 0.90 at any time t. We observe that this lower bound is fairly loose because we do not observe a single suboptimal deployment across many repetitions and possible deployment moments.

Analysis
Conservative Linear Contextual Bandits (CLUCB) [26] is, to our knowledge, the only other online learning method for contextual bandits that is also safe. Unfortunately, CLUCB comes with two limitations: (1) CLUCB does not scale beyond toy problems because it constructs confidence sets around parameters, which requires solving a constraint optimization problem every time an action has to be chosen which makes it infeasible for realistic IR problems; and (2) CLUCB can only be applied to linear models. Our method addresses both limitations. First, SEA scales to large and complex datasets, because it merely needs to compute the lower confidence bound and perform a gradient update step, both of which can be done highly efficiently. Second, SEA can easily be adapted to non-linear models such as gradient-boosted decision trees and neural networks as it is based on gradient descent.
SEA, being an online learning method, is capable of exploration. In contrast, offline methods do not explore, they merely observe what a baseline policy is doing. If this baseline policy does not explore well, offline learning techniques, whilst still able to learn, are less effective [43]. And even if the baseline policy is highly explorative, what truly matters is how well this policy explores the regions with favorable losses [36]. SEA solves this problem as it starts exploring actions using the newly learned policy as soon as it is safe to do so. Since the policy learned by SEA has a higher estimated performance than the baseline policy, the actions that it eventually takes are likely to be actions with high reward.
We note that the safety that SEA guarantees does come at a cost: SEA cannot guarantee that it will explore new actions beyond the initial deployed policy. In contrast, purely online methods can explore without any restrictions and as a result they may end up learning a better policy than SEA. Put differently, SEA provides a trade-off between safety and exploration: with a lower δ , SEA will be more safe, but gives up some amount of exploration. Vice versa, a higher δ allows SEA to explore more aggressively while giving up some level of safety.

EXPERIMENTAL SETUP
To answer our research questions, we consider two tasks: text classification and document ranking. We consider these two complementary tasks as they differ in the size of the action space, which is small in the case of text classification (the number of classes) but large in the case of document ranking (the number of possible ranked lists). In both cases we turn a supervised learning problem into a bandit problem.

Text classification task
, where x t ∈ R m is a feature representation of the object we wish to classify and y t ∈ {0, . . . , n} is the correct label for that object. E.g., in text classification x t is a bag-of-words representation of a document we wish to classify and y t the correct label for that document. We are interested in the contextual bandit formulation for multi-class classification, i.e., where the correct label y t is not known, but we can observe a reward signal for a chosen label a t . We follow the methodology of Beygelzimer and Langford [3] to transform a supervised learning problem into a contextual bandit problem: (1) The environment presents the policy with the feature vector x t (e.g., the bag-of-words representation of a text document). (2) The policy chooses a t , one of n possible labels, as its prediction.
(3) The environment returns a reward of 1 if the chosen label was correct and a reward of 0 if it was incorrect.
Methods that use counterfactual learning (IPS and SEA), require a stochastic baseline policy and the corresponding propensity scores, i.e., the probability that the baseline policy chose the selected label a t . To this end we define our data-collection policy using the ϵ-greedy approach. An ϵ-greedy approach offers several benefits over alternative exploration strategies: (1) The amount of exploration can be manually tuned with the ϵ parameter, allowing either very conservative or very aggressive exploration. (2) It is a priori known, via the ϵ parameter, how much performance we are giving up to perform exploration. (3) The ϵ-greedy strategy generates stable and bounded propensity scores; this counteracts the high variance problem that is common in counterfactual learning and evaluation.
We consider two types of reward signals. First, the perfect scenario where a reward of 1 is given if the chosen label a t is correct and 0 otherwise. Second, a near-random scenario where rewards are sampled from a Bernoulli distribution. More specifically, when a policy chooses the correct label a t , the policy is given a reward of 1 with probability 0.6. Conversely, if the chosen label a t is incorrect, the learner is given a reward of 1 with probability 0.4. We choose these contrasting scenarios as they highlight the need for safety. It is much easier for a learner to make mistakes in the near-random scenario due to the high levels of noise and we hypothesize that safety plays a more important role in that case. The text classification datasets that we use are specified in Table 1.

Document ranking task
For the document ranking task we use the counterfactual LTR framework as described in [23]. In this setup, a production ranker displays a ranked list to the user. It is assumed that the user does not examine all documents in the presented ranking, but is instead more likely to observe top-ranked documents than lower ranked ones, a phenomenon called "position bias" [21]. After a user observes a document they can either judge it as relevant, by clicking on it, or judge it as non-relevant, by not clicking on it. We simulate user behavior as follows: (1) The policy being learned presents a ranked list to the simulated user.  Table 3. Click noise settings for the document ranking task. Each entry is the probability of clicking a document given its relevance label.
P(click | relevance) where η is a parameter that controls the severity of click bias. This setup is identical to the one described in [23]. (3) For each observed document, we generate clicks depending on the relevance of the document.
We use varying levels of click noise ("perfect", "position-biased" and "near-random"), the specific click probabilities are listed in Table 3. This setup is in line with the methodologies described in [13,15,34,35]. In our setup, clicks are simulated only on the top 10 documents. This more realistically simulates the behavior of Web search users who are unlikely to visit the second (or later) result page [7]. For the counterfactual models we assume the correct propensity scores are known during learning. In other words, the propensity model used to simulate position bias is also used to compute the propensity scores during learning. We update our model via stochastic gradient descent at the document level by updating the weights using a weighted gradient and stochastic gradient descent, as described in Section 2.2. Table 2 details the datasets used for the document ranking task.

Methods used for comparison
Our experiments are aimed at assessing the performance of SEA for solving contextual bandit problems. We compare SEA against offline and online methods. The former comparison is motivated by the fact that offline methods are safe by definition so a comparison of SEA against such methods will inform us about the potential performance gains by using SEA. The latter is motivated by the fact that SEA is an online method so a comparison of SEA against such methods will inform us about the safety of using SEA. In all experiments, the models to be trained are warm-started with the weights of the deployed policy.
Offline methods for contextual bandit problems optimize a policy by observing actions that are taken by a separate logging policy π b . This makes them safe, because learning happens only on data that has been collected in the past by a logging policy. However, safety also makes them incapable of exploration. We use the state-of-the-art offline method λ-translated Inverse Propensity Scoring (λ-IPS) [22]. We hypothesize that the average reward of a model trained by SEA is higher than of a model trained by λ-IPS because SEA is capable of exploring actions from the newly learned policy.
Online methods optimize a policy π w by having it interact with the environment. Such methods are effective at exploring the action space but have no notion of safety. The online methods we use for the classification task are: (1) policy gradient with an ϵ-greedy strategy, (2) policy gradient with a Boltzmann exploration strategy, (3) LinUCB [31], and (4) Thompson Sampling [2]. For the ranking task, we use the following online methods: (1) SVMRank Online [20] (2) Dueling Bandit Gradient Descent [50] with Team-Draft Interleaving [38] We hypothesize that the user experience of online methods suffers in the early stages of learning (i.e., performance will be below the baseline policy π b ) because these approaches do not provide formal guarantees of safety while exploring new actions.
Safe online methods are meant to be safe in the sense that during training, the algorithms never perform worse than a baseline policy π b . Our contribution, SEA, falls in this class of methods. We also consider CLUCB (Conservative Linear UCB) [26]. Its design makes it impractical for problems with high dimensionality or large action spaces as it requires performing an m ×m matrix inversion and solving a constrained optimization problem whenever an action has to be selected; its high computational complexity prevents us from using it with our datasets.
Finally, we also include an empirically safe version of SEA, which does not use the high-confidence bounds, which we denote as Boundless Safe Exploration Algorithm (BSEA). This method compares the mean estimate of the reward of the learned policy π w and the deployed policy π d , instead of the lower and upper confidence bounds. Specifically, we use Algorithm 1 where we set We expect this method to deploy its learned model earlier and more frequently than SEA because it does not have to overcome potentially large confidence bounds. Hence, we expect this policy to do better than SEA, but it may exhibit unsafe behavior as it no longer provides the same formal safety guarantees as SEA.

Choice of baseline policy
Both λ-IPS and SEA depend on a baseline policy π b . We require that this baseline policy is suboptimal, so that learning can occur. This requirement is reasonable since we cannot hope to improve an already optimal policy. We introduce suboptimality in π b by subsampling the training set on which we train the policy (1% sample for the classification task and 0.1% sample for the ranking task). This is motivated by a scenario that commonly occurs in real search engines or classification systems: Manual labels are expensive to obtain and are usually available on a scale of several orders of magnitude smaller than logged bandit feedback. This strategy for introducing suboptimality results in a baseline policy whose performance is much better than random, but still not optimal.

Metrics and statistical significance
We evaluate SEA and the competing approaches in two ways. One is in terms of cumulative reward during training, which is the sum of all rewards received as a function of the number of rounds; this type of metric allows us to quantify the degree to which the user experience is affected. A higher cumulative reward during training indicates a better user experience. The second is in terms of average reward, which is the reward averaged per action on held-out test data; this type of metric allows us to quantify how well a trained policy generalizes to unseen test data. The document ranking task uses simulated clicks as a reward signal (see Section 4.2) during training, which is not a very insightful metric for evaluating the true performance of a policy. Instead, to evaluate the learned policies, we use nDCG@10 [19]. We measure statistical significance of observed differences using a t-test (p < 0.01).

Safety
We first address RQ1: Is SEA safe? I.e., does it always perform at least as good as a baseline policy?
To answer RQ1, we plot the performance of SEA against that of online algorithms while they are training, using average reward on a held-out test dataset as our metric. Let us first consider the text classification task; see Figure 2. The baseline policies have an average accuracy of around 0.6, except in the 20 Newsgroups dataset where this is 0.4. The tested online algorithms include ϵ-greedy, Boltzmann exploration, Thompson sampling and LinUCB. For the 20 Newsgroups and RCV1 datasets we do not run LinUCB and Thompson sampling because they require inverting a 47,236 × 47,236 matrix (for 20 Newsgroups) and 62,060 × 62,060 matrix (for RCV1) on every update which is too computationally expensive. The performance of SEA is at least as good as the baseline policy. Similarly, it seems that warm-started online algorithms are also safe in this scenario, as they too perform always at least as good as the baseline policy. The best algorithm in terms of final performance is different for each of the datasets. Overall we find that when it is computationally feasible to apply UCB or Thompson sampling, they outperform all other methods. Furthermore we find that Boltzmann exploration works very well with a perfect reward signal. However, in the case of near random rewards, both Boltzmann exploration and ϵ-greedy are not always capable of learning a good policy. Finally, we observe that BSEA is on par with SEA, and in some cases significantly outperforms it, while being empirically safe. BSEA is capable of deploying its learned model faster and more frequently than SEA as it does not have to overcome potentially large confidence bounds. Although this means that BSEA is not guaranteed to be safe, we find that it is empirically safe across all experimental conditions. Next, we consider the document ranking setting; see Figure 3. We use NDCG@10 on held-out test data as the evaluation metric. We observe that SEA is always at least as good as the baseline policy whereas online learning methods may suffer from unsafe performance in the early stages of learning. We see that in the case of near-random clicks on the Istella-s dataset, SEA accurately identifies that it is not safe to deploy whereas the online method suffers from unsafe performance and actually go below the baseline level. However, on the other datasets with near-random clicks, SEA never deploys a new model and consequently does not explore different actions. As a result, it is unable to improve upon the production policy. Online approaches outperform SEA here because they explore more aggressively and are able to learn even in the face of large amounts of noise. These results are in line with previous work [18], which has shown that counterfactual methods have difficulty learning in scenarios with large amounts of noise. In cases with position-biased or perfect clicks, the ranker trained by SEA performs on par with the online method. This means that in realistic scenarios we do not sacrifice any performance by using SEA. Finally, we note that BSEA performs empirically safe on the document ranking task across all experimental settings, which is in line with the results on the text classification task. This answers RQ1. Our experiments indicate that SEA is indeed safe, its performance does not fall below that of the baseline policy.

Improved user experience
Next, we answer RQ2: Does SEA provide a better user experience during training than offline or online learning methods? I.e., does it accumulate a higher reward during training?
To answer RQ2, we measure the cumulative reward obtained by the learning algorithms. During training, the offline method, λ-IPS, only observes actions taken by the baseline policy, hence its cumulative reward is always equal to the cumulative reward of the baseline and is omitted from the result tables to save space. Table 4 lists the results for the text classification task. The cumulative reward achieved by SEA is at least as good as the baseline, and eventually better. We find that only ϵ-greedy on the RCV1 dataset under near random rewards performs significantly worse than the baseline. In all other settings we find that all the warm-started online methods similarly provide a user experience that is at least as good as the baseline, and eventually better. This means that for the text classification task, all methods, with the exception of ϵ-greedy, perform safely and never harm the user experience. Finally, we see that BSEA is able to improve the user experience faster and more quickly than SEA in the perfect rewards setting, and performs on par in the near random rewards setting. Similar to the results we have observed in Section 5.1, we hypothesize that BSEA does not have to overcome potentially large confidence bounds and as a result is able to more quickly and more frequently deploy its learned model. As a result, BSEA is capable of improving the user experience over SEA.
Next we turn to the case of ranking. See Table 5 for the cumulative reward results for document ranking. It is clear that SEA performs at least as good as the baseline policy and eventually outperforms it. For the online learning method, this is not the case. Specifically for the Istella-s dataset with near random clicks, we observe significant performance degradations in the early stages of learning which harms the user experience. However, on the other datasets with near random clicks we find that the online methods are capable of safely exploring the action space, even with high noise, and as a result improve the overall user experience more than SEA. From Table 6 we see that Istella-s contains very sparse relevance feedback compared to the MSLR10k and Webscope datasets. In the near-random click scenario this means that there are significantly more clicks on non-relevant documents, making Istella-s with near-random clicks the most challenging learning scenario. We once again see that BSEA is a very strong baseline across all datasets, improving the user experience over SEA in the perfect and position-biased clicks settings while performing on par with SEA in the near-random click setting.
This answers RQ2. SEA provides a better user experience than online methods, particularly in the document ranking setting with high levels of click noise where the user experience may be negatively affected by online algorithms. In the later stages of learning SEA provides a user experience that is significantly better than the baseline and comparable to online approaches. We find that BSEA is able to improve the user experience even further by being able to deploy its learned model earlier and more frequently. Table 4. Cumulative reward, relative to the baseline policy, while training for text classification. LinUCB and Thompson Sampling cannot be run on the 20 Newsgroups and RCV1 datasets due to their high computational complexity. Statistically significant differences with SEA are indicated using ▲ (p < 0.01) for gains and ▼ (p < 0.01) for losses.

The benefit of exploring
Finally, we turn to RQ3: Does SEA, which explores the action space, learn a more effective policy compared to offline learning methods, which do not perform exploration?
To answer RQ3, we compare SEA to the state-of-the-art offline learning algorithm λ-IPS on unseen test data. The results for the classification task are displayed in Table 7. Because SEA is capable of has a performance of around 0.6, whereas the baseline policy for the 20 Newsgroups dataset only has a performance of around 0.4. We postulate that this difference in baseline performance may cause λ-IPS to learn better and therefore perform equally to SEA on the USPS and RCV1 datasets. Lastly, we find that BSEA performs on par with SEA in all settings, while producing a significantly better model on the RCV1 dataset with perfect rewards. Similar to our observations in Sections 5.1 and 5.2, we find that BSEA likely performs so well because it does not have to overcome confidence bounds and can deploy its learned model faster and more frequently than SEA, allowing it to learn a more effective model. Finally, we consider the document ranking setting; see Table 8. SEA is able to learn a more effective ranker than λ-IPS on all datasets with perfect clicks and on Istella-s with position-biased clicks. We hypothesize that this is because SEA, being capable of exploration, eventually shows Table 8. Average reward on held-out test data for the learned model for the document ranking task after 10,000,000 rounds. Statistical significance is denoted the same way as in Table 4. documents to the user that the baseline policy would rarely, if ever, show. As a result, SEA is able to obtain clicks on these documents, allowing it to learn more effectively. This is in line with our expectations because previous work has shown that even a tiny amount of exploration can result in substantial improvements in LTR [14]. Finally, we find that BSEA does not produce a better ranker than SEA for the document ranking task. Across all settings, the models produced by BSEA and SEA are comparable. This answers RQ3. Exploration does indeed help the performance of the policy learned by SEA and it outperforms λ-IPS both for scenarios with a small action space (e.g., text classification) and for scenarios with a large action space (e.g., document ranking).

RELATED WORK
The idea of deploying automated decision making systems in IR is not new. The contextual bandit framework has been used in news recommendation [31], ad placement [28], and online learning to rank [13]. Contextual bandit formulations of IR problems allow insights and methods from the bandit literature to be applied and extended to address these problems [14]. For research on contextual bandits this connection has opened up an application area where new approaches can be evaluated on large-scale datasets [32].

Learning in contextual bandits
Contextual bandit algorithms have been widely studied in the online and offline learning settings [2,31,43]. A key challenge in contextual bandit problems is the exploration-vs-exploitation tradeoff. On the one hand we want to explore new actions so as to find favorable rewards. On the other hand, we want to exploit existing knowledge about actions so as to maximize the total reward. The online learning methods we consider in this paper deal with this tradeoff in various ways. The methods we consider are policy gradient with ϵ-greedy exploration, policy gradient with Boltzmann exploration, LinUCB and Thompson Sampling. Policy gradient methods optimize the weights of a policy via stochastic gradient descent, by solving the following optimization problem: The ϵ-greedy heuristic selects actions by choosing with probability ϵ an action uniformly at random and with probability (1 − ϵ) the best possible action. Boltzmann exploration [4] chooses actions by drawing them with a probability proportional to the policy: a t ∼ π w ( · | x t ). LinUCB [31] and Thompson Sampling [2] are different from policy gradient methods because they make a linearity assumption. These methods construct a set of weights w a ∈ R m for every possible action, such that π w (a t | x t ) = w T a t x t . LinUCB selects actions by choosing the one with the highest confidence bound. Thompson Sampling samples new weightsŵ a from a posterior distribution and then chooses the best action given the sampled weights: a t = arg max a πŵ a (a | x t ).
In IR there has been considerable attention for exploiting log data [12]. It is one of the most ubiquitous forms of data available, as it can be recorded from a variety of systems at little cost [42]. The interaction logs of such systems typically contain a record of the input to the system, the prediction made by the system, and the feedback. The feedback provides only partial information limited to the particular prediction shown by the system. Offline learning algorithms tell us how data collected from interaction logs of one system can be used to optimize a new system [14,42]. Interaction logs used in offline learning are usually biased towards the policy that collected the data. To remove this bias, offline learning methods resort to inverse propensity scoring. To use inverse propensity scoring, the logging policy must be stochastic and the corresponding propensity scores (probability of choosing the logged action) are recorded. Using these propensity scores, it is possible to reweigh data samples to remove the bias. An advantage of offline learning methods is that they do not require interactive experimental control. Thus, there is no risk of hurting the user experience with these methods. In other words, offline learning methods are safe by definition [18].
Unlike online methods, SEA's performance during the early stages of learning does not suffer and always stays at least as good as a baseline, making the method safe to use. Compared to offline methods, SEA is capable of exploration, which makes it effective at finding areas of the action space that may have high reward.

Safety in contextual bandits
There has been a growing interest in concepts related to safety for contextual bandit problems. This is due to the fact that contextual bandit formulations are applied to automated decision making systems, where actions taken by the system can have a significant impact on the real world. There are two main groups of work: risk-aware methods and conservative methods.
Risk-aware methods [8,17,41] are online learning algorithms that model the risk associated with executing certain actions as a cost which is to be constrained and minimized. Galichet et al. [8] introduce the concept of risk-awareness for the multi-armed bandit framework. Sun et al. [41] extend the idea of risk-awareness to the adversial contextual bandit setting. Garcia and Fernández [9] explore risk-awareness for the reinforcement learning paradigm. Risk-aware methods use a separate type of feedback signal, in addition to the standard reward feedback, which is called risk. Risk-aware methods aim to keep the cumulative risk below a specific threshold. These types of methods are typically applied in fields like robotics where certain actions can be dangerous or cause damage. A drawback is that the risk has to be explicitly quantified by the environment. Designing a good risk feedback signal for IR systems is subject to modeling biases and in some cases impossible, limiting the application of such methods.
Conservative methods [49] measure safety as a policy's performance relative to a baseline policy. A method is safe if its performance is always within some margin of the baseline policy. The idea was first introduced for the multi-armed bandit case [49] and later extended to linear contextual bandits in the form of the CLUCB algorithm [26]. CLUCB is a safe conservative online learning method, which works by constructing confidence sets around the parameters of the policy. Unfortunately, the method has to solve a constrained optimization problem every time an action has to be selected, which has a significant computational overhead. In contrast, SEA addresses this problem because it only needs to do two computationally efficient operations: update a lower confidence bound estimate and perform a gradient update step. This makes SEA applicable to larger and more complex datasets.
Finally, Li et al. [30] introduce a complementary approach to SEA, called BubbleRank, an algorithm that gradually improves upon an initial ranked list by exchanging higher-ranked less attractive items for lower-ranked more attractive items. Li et al. define a safety constraint that is based on incorrectly-ordered item pairs in the ranked list, and prove that BubbleRank never violates this constraint with a high probability. We do not compare to BubbleRank in our experiments because it assumes a user model [6], an assumption that is orthogonal to our experimental setup [18].

CONCLUSION
We have proposed SEA, a safe online learning algorithm for contextual bandit problems. SEA learns a new policy from the behavior of an existing baseline policy and then starts to execute actions from the new policy once its estimated performance is at least as good as that of the baseline. This brings us the best of both worlds, achieving the performance of online learning with the safety of offline learning.
We perform extensive experimentation on two IR tasks, text classification and document ranking. In both tasks SEA is safe. It never performs worse than a baseline policy, whereas online methods are unsafe and suffer from suboptimal performance in the early stages of learning. We observe that the user experience with SEA is improved in the early stages of training, but may be suboptimal in later stages when compared to methods that converge much faster, such as LinUCB (although such methods are not generalizable to all datasets). The final performance of a model learned with SEA is comparable to other online algorithms and beats that of offline methods, which are incapable of exploration. Finally, we find that BSEA, a boundless version of SEA, is empirically just as safe as SEA while being able to explore faster and, as a result, outperform SEA in many experimental conditions. These results confirm that SEA does indeed trade off advantages and disadvantages of offline and online learning, in some scenarios outperforming online methods in the early stages of learning and having higher final performance than offline methods. However, compared to purely online approaches, SEA may not be as effective in learning a good policy due to the fact that it is more conservative when exploring. The conservative nature of SEA implies that safety is not free, there is a possible performance cost involved for cases where SEA is unable to effectively explore.
An interesting direction for future work is an extension of SEA to non-linear models. SEA builds on gradient descent and it is trivial to extend the method to use gradient-boosted decision trees or neural networks. This line of work is especially applicable for the document ranking task where it is known that non-linear models can outperform linear models by a wide margin [48]. Furthermore, another possibility for future work is to perform a study on safety for a broad range of online and offline methods, similar to [18]. Specifically, it would be interesting to compare against recent work on safe online learning to re-rank [30].

CODE AND DATA
To facilitate reproducibility of the results in this paper, we are sharing all resources used in this paper at https://github.com/rjagerman/tois2019-safe-exploration-algorithm. This includes the training procedures and parameters of the online, offline, safe and baseline policies.