title: Bandit Data-Driven Optimization
authors: Zheyuan Ryan Shi Zhiwei Steven Wu Rayid Ghani Fei Fang
text: 
  
  Short Term Variability of Evolved Massive Stars with 
  
  II: A New Class of Cool, Pulsating Supergiants
      [
      
  =====================================================================================================
  
  
  
  
  Applications of machine learning in the non-profit and public sectors often feature an iterative workflow of data acquisition, prediction, and optimization of interventions.
  There are four major pain points that a machine learning pipeline must overcome in order to be actually useful in these settings: small data, data collected only under the default intervention, unmodeled objectives due to communication gap, and unforeseen consequences of the intervention. 
  In this paper, we introduce bandit data-driven optimization, the first iterative prediction-prescription framework to address these pain points.
  Bandit data-driven optimization combines the advantages of online bandit learning and offline predictive analytics in an integrated framework. We propose PROOF, a novel algorithm for this framework and formally prove that it has no-regret. 
  Using numerical simulations, we show that PROOF achieves superior performance than existing baseline. We also apply PROOF in a detailed case study of food rescue volunteer recommendation, and show that PROOF as a framework works well with the intricacies of ML models in real-world AI for non-profit and public sector applications.
  
  
  
  
  § INTRODUCTION
  
  
  
  The success of modern machine learning (ML) largely lies in supervised learning, where one predicts some label c given input feature x. 
  Off-the-shelf predictive models have made their ways into numerous commercial applications. 
  Deep learning has repeatedly advanced our ability to tell a cat from a dog. 
  Such tangible progress has motivated the community to address more real-world societal challenges, and in particular, in the non-profit and public sectors.
  
  
  
  Unfortunately, the success of ML often does not translate directly into a satisfactory solution to a real-world societal problem. One obvious reason is supervised learning focuses on prediction, yet real-world problems, by and large, need prescription. For example, rather than predict which households' water pipes are contaminated (labels) using construction data (features), municipal officials need to schedule inspections (interventions) <cit.>. The common practice is a two-stage procedure, as shown in Figure <ref>a. After training an ML model, one makes prescriptive decisions based on some optimization problem parametrized by the prediction output.
  In an emerging line of work on (one-shot) data-driven optimization, the learning problem is made aware of the downstream optimization objective through its loss function, gluing the two stages together <cit.>. We illustrate this in Figure <ref>b.
  
  However, this is still far from a complete picture. Figure <ref>c shows a typical workflow in many AI for non-profit and public sector projects. After getting existing data which are often under a default intervention, a data scientist trains an ML model and then, based on it, recommends an intervention. Using the new data collected under the new intervention, the researcher updates the ML model and recommends a new intervention, so on and so forth, leading to an iterative process. The principles of these steps are often not aligned. Without a rigorous, integrated framework to guide the procedure, this could lead to operation inefficiency, missed expectations, dampened initiatives, and new barriers of mistrust which are not meant to be. 
  
  While the reader might think this is workflow is universal across applications of ML, whether for profit or not, such an iterative process is especially prominent and necessary in the non-profit and public sectors due to the following key features of those applications distilled from existing research <cit.>.
  First, there may not be enough data to begin with. Many of these domains do not have the luxury of millions of training examples. A small dataset at the beginning leads to inaccurate predictions and hence suboptimal decisions, but they will improve as we collect more data, as seen in, e.g., predicting poaching threats from patrol data and designing ranger patrols <cit.>. Second, too often the initial dataset has some default intervention embedded, while the project's goal is to find the optimal intervention. For example, <cit.> design a smartphone notification scheme for a volunteer-based platform but existing data are all collected under a default suboptimal scheme. If one expects the data distribution to vary across interventions, one has to try out some interventions and collect data under them.
  Third, we may not perfectly know the the correct objective function to optimize. This is especially true considering the knowledge and communication gap between the data scientists and the domain practitioners. Fourth, the proposed interventions may have unexpected consequences. This hints at the inherent impossibility of fully modeling the problem in one shot. 
  
  We propose the first iterative prediction-prescription framework, which we term as bandit data-driven optimization. This framework combines the relative advantages of both online bandit learning and offline predictive analytics. We achieve this with our algorithm PRedict-then-Optimize with Optimism in Face of uncertainty (PROOF). PROOF is a modular algorithm which can work with a variety of predictive models and optimization problems. Under specific settings, we formally analyze its performance and show that PROOF achieves no-regret. In addition, we propose a variant of PROOF which handles the scenario where the intervention affects the data distribution and prove that it also enjoys no-regret. Using numerical simulations, we show that PROOF achieves much better performance than a pure bandit baseline. We also apply PROOF in a case study of a real-world AI for nonprofit project on food rescue volunteer engagement.
  
  
  
  § RELATED WORK
  
  
  
  We propose bandit data-driven optimization to address the challenges we encountered in our previous work on AI for the non-profit and public sectors, because we found surprisingly no existing work that rigorously studies the iterative prediction-prescription procedure.
  We explain below how several lines of work with similar goals fail to address the challenges we face, and summarize them in Table <ref>.
  
  First, (one-shot) data-driven optimization aims to find the action w^* that maximizes the expected value of objective function p(c, w) given some feature x where c is a function of x, i.e. w^* = max_w 𝔼_c|x [p(c, w)] <cit.>. 
  A popular approach is referred to as the predict-then-optimize framework <cit.>. There, one learns an ML predictor f from data and then optimize p(c,w) with the predicted label c = f(x).
  This entire literature assumes that the optimization objective is known a priori, which is often too good to be true. It also does not consider sequential settings and hence cannot adapt to new data. 
  Meanwhile, inverse optimization <cit.> also does not apply to our problem, for the actions taken obviously have no definite relationship with the optimal action.
  Our work touches on optimization under uncertainty <cit.>. They learn the parameters of an optimization problem. However, they do not learn the data distribution or use the feature/label dataset that is so common in real-world applications like food rescue.
  
  Contextual bandit is a proper setting for sequential decision making <cit.>, and algorithms like LinUCB <cit.> play a central role in designing PROOF. Recent advances further improve the convergence rate under specific settings <cit.>.
  Bandit data-driven optimization reduces to contextual bandit if we skip training an ML model and directly pick an action.
  However, by doing so, we would effectively give up all the valuable historical data. Furthermore, although bandit algorithms have succeeded in millisecond-level decision-making <cit.>, they are impractical in applications like food rescue where one time step represents a week, if not a month. The resulting long convergence time would hardly be acceptable to any stakeholders. We prove the same regret bound as previous work in our more realistic setting, with the regret decreasing much faster empirically.
  
  Also related is offline policy learning <cit.>. It does not need any online trials, and hence is much easier to convince the stakeholder to adopt. 
  However, it assumes the historical data has various actions attempted, which fails to hold in most public sector applications.
  
  In short, by proposing bandit data-driven optimization as a new learning paradigm, we fill a hole that no existing models were designed to address. 
  
  
  
  
  § BANDIT DATA-DRIVEN OPTIMIZATION
  
  
  We describe the formal setup of bandit data-driven optimization in Procedure <ref>. 
  On Line <ref>, we receive an initial dataset 𝒟 of size n_0, with features x_i^0 and label c_i^0 for data point i, and intervention in-place w^0_i when the data point is collected.
  Each feature vector x_i^0 is drawn i.i.d. from an unknown distribution D_x. Each label c_i^0∈ C is independently drawn from an unknown conditional distribution D(w^0_i)_c|x_i^0, which is parameterized by the intervention w^0_i, as different interventions could lead to different data distributions. 
  In reality, w^0_i is often identical across all i.
  On Line <ref>, we use all the data collected so far to train an ML model f_t, which is a mapping from features X to labels C.
  On Line <ref>, we get a new set of feature samples 𝐱^t={x_i^t}_i=1^n. Then, we select an intervention w_i^t ∈ W for each individual i. 
  On Line <ref>, we commit to interventions 𝐰^t = {w^t_i} and receive the labels 𝐜^t={c_i^t}. Each label is independently drawn from the distribution D(w^t_i)_c|x_i^t. 
  Then, on Line <ref>, we incur a cost u_t.
  
  We assume that the cost u_t is determined by a partially known function u(𝐜^t,𝐰^t). The function consists of three terms. The first term ∑_i p(c_i^t, w^t_i) is the known loss. p(c, w) is a fully known function capturing the loss for choosing intervention w and getting label c. It represents our modeling effort and domain knowledge. The second term ∑_i q(w^t_i) is the unknown loss. q(w) is an unknown function representing all the unmodeled objectives and the unintended consequences of using the intervention w. The third term is random noise η.
  This form of loss – a known part p(·) and an unknown part q(·) – is a realistic compromise of two extremes. We spend a lot of time communicating with food rescue practitioners to understand the problem. It would go against this honest effort to eliminate p(·) and model the process as a pure bandit problem. On the other hand, there will be unmodeled objectives, however hard we try. It would be too arrogant to eliminate q(·) and pretend that anything not going according to the plan is noise. 
  The unknown q(·) is our acknowledgement that any intervention may have unintended consequences.
  We leave to future work to consider other interactions between p(·) and q(·).
  
  
  
  
  
  Hence, the question is how to select the intervention 𝐰^t.
  As is typical in the bandit literature, we define the optimal 
  policy to be that given feature 𝐱, pick action π(𝐱) such that
  
      π(𝐱) = min_𝐰𝔼_𝐜, η | 𝐱 [u(𝐜, 𝐰)],
  
  where the expectation is taken over labels 𝐜 and noise η conditioned on the features 𝐱.
  The goal is to devise an algorithm to select interventions 𝐰^t to minimize the regret
  
      R_T =  𝔼_x, c, η[   ∑_t=1^T ( u(𝐜^t, 𝐰^t)   - u(𝐜^t, π(𝐱^t))  ) ].
  
  
  The label c can be a scalar or a vector. For the rest of the paper, we assume C∈ℝ^d and W∈ℝ^d. W may be discrete or continuous but it is assumed to be bounded. 
  
  
  Bandit data-driven optimization could be applied to a variety of AI for non-profit and public sector projects across application domains. 
  The canonical problem setting is the scarce resource allocation in the non-profit and public context where an intervention corresponds to a resource allocation plan and new interventions need to be chosen periodically based on the data collected under previous interventions.
  For example, in game-theoretic anti-poaching, one trains an ML model using geospatial features to predict poacher activity, and then solves an optimization problem to find a patrol strategy <cit.>. The patrol finds more poaching data points so we go back to update the ML model, starting another iteration of trial. In education programs, one trains an ML model to predict students' risk of dropping out, and then solves an optimization problem to allocate education resources to the students under budget and fairness constraints <cit.>. After one round, one observes the students' performance and starts the next iteration of the program.
  To illustrate how bandit data-driven optimization captures real-world AI for nonprofit workflows more concretely, we describe below one particular application, food rescue volunteer recommendation, in detail.
  
  
  
  
   §.§ Food Rescue Volunteer Recommendation as Bandit Data-Driven Optimization
  
  
  Wasted food account for 25% of the US food consumption, while 12% of the US population struggle with food insecurity <cit.>. With the end of COVID-19 pandemic nowhere in sight, the problem is becoming even more serious <cit.>. From New York to Colorado, from San Francisco to Sydney, food rescue platforms are fighting against food waste and insecurity in over 100 cities around the world. Their operation has proved to be effective <cit.>. These platforms match food donations from restaurants and grocery stores to low-resource community organizations. 
  Once this matching is done, the food rescue dispatcher would post the donor and recipient information on their mobile app. The volunteers will then receive push notifications about the rescue. They could then claim it on the app and then complete the rescue.
  
  
  Relying on external volunteers brings great uncertainty to the food rescue operation. Occasionally, some rescue trips would stay unclaimed for a long time. Since unclaimed rescues would seriously discourage the donors and recipients from further participation, food rescue dispatchers want to prevent this as much as possible. 
  The dispatcher may recommend each rescue to a subset of volunteers through push notifications, The selection of volunteers to notify is the intervention w∈{0,1}^d (with the j^th dimension representing whether to send notification to the j^th volunteer). This decision is dependent on how likely a rescue will be claimed by each volunteer. Thus, we can use an ML-based recommender system which leverages the features of a rescue and the volunteers, e.g. donor/recipient location, weather, the volunteer's historical activities, etc. (feature x), to predict the probabilities that each volunteer will claim the rescue. Our previous work is focused exclusively on this static recommender system <cit.>. After we select w for a rescue, we observe which volunteer actually claim the rescue, that is, the vector label c (with the j^th dimension representing whether the j^th volunteer claims the rescue). This data point will be added to our dataset and used for training later. The base optimization objective p(c, w) reflects the fact that we want to send notifications to the volunteers who will claim it, while not sending too many notifications. Obviously, whether or not the rescue gets claimed after these push notifications matter to the food rescue organization. 
  Yet, there is more to the cost to the food rescue, e.g. how each volunteer reacts to push notifications (will they get annoyed and leave?). 
  The q(·) cost could capture such factors. 
  
  
  § ALGORITHMS AND REGRET ANALYSIS
  
  
  We propose a flexible algorithm for bandit data-driven optimization and establish a formal regret analysis.
  
  The data points are drawn from X × C ⊆ℝ^m ×ℝ^d. We assume all x ∈ X has l^2-norm bounded by constant K_X, and the label space C has l^1-diameter K_C. The action space W could be either discrete or continuous, but is bounded inside the unit l^2-ball in ℝ^d. We specify the data distribution by an arbitrary marginal distribution D_x on X and a conditional distribution such that c = f(x) + ϵ where ϵ∼𝒩(0, σ^2 I), for some unknown function f. To begin with, we assume f ∈ℱ comes from the class of all linear functions with f(x) = Fx, and we use ordinary least squares regression as the learning algorithm. We will relax this assumption towards the end of Section <ref>. 
  The known cost p(c, w) = c^† w is the inner product of label c and action w.[We use superscript † to denote matrix and vector transpose.] The unknown cost is q(w) = μ^† w, where μ is an unknown but fixed vector.
  Furthermore, for exposition purpose we will start by assuming that the intervention w does not affect the data distribution. In Section <ref>, we will remove this assumption.
  
  
  
  
   §.§ With Exactly Known Objectives
  
  As a primer to our main results to be introduced in the following section, we first look into a special case where we know the optimization objective. That is, our cost only consists of p(·), with q(·) = 0. This is not very realistic, but by studying it we will gain intuition for the general case.
  
  At each iteration, this setting resembles the predict-then-optimize framework studied by <cit.>. Given a sample feature x, we need to solve the linear program with a known feasible region W ⊆ℝ^d:
  
      min_w      𝔼_c ∼ D_c|x [p(c, w) | x] = 𝔼_c ∼ D_c|x [c | x]^† w
      
          s.t.       w ∈ W
  
  We hope to learn a predictor f̂: X → C from the given dataset, so that we can solve the following problem instead.
  
      w^*(ĉ) :=  min_w      ĉ^† w     where  ĉ = f̂(x)
      
          s.t.       w ∈ W
  
  In this paper we assume that the problem has a unique optimal solution.
  Since the total cost is the same as the known optimization objective, intuitively we should simply commit to the action w^*(ĉ). By doing so, the expected regret we incur on this data point is 𝔼_x [r(x)], where 
  
      r(x) = 𝔼_c|x[c]^† (w^*(ĉ) - w^*(𝔼_c|x[c])).
  
  Theorem <ref> establishes that, indeed, this strategy leads to no-regret. This is not entirely trivial, because the optimization is based on the learned predictor yet the cost is based on the true distribution. The proof is instrumental to the subsequent results. All the proofs are in Appendix <ref>.
  
  When the total cost is fully modeled, i.e. q(·) = 0, simply following the predict-then-optimize optimal solution leads to regret O(√(ndmT)).
  
  
  
  
  
  
   §.§ PROOF: Predict-then-Optimize with Optimism in Face of Uncertainty
  
  
  When there is no bandit uncertainty, as we showed just now one can simply follow the predict-then-optimize framework and no-regret is guaranteed. However, the unknown bandit cost is crucial to real-world food rescue and similar applications. We now describe the first algorithm for bandit data-driven optimization, PRedict-then-Optimize with Optimism in Face of uncertainty (PROOF), shown in Algorithm <ref>.
  
  
  
  AlgorithmalgorithmList of Algorithms
  
  
  
  PROOF is an integration of the celebrated Optimism in Face of Uncertainty (OFU) framework and the predict-then-optimize framework.
  It is clear that the unknown cost component q(·) + η forms a linear bandit.
  For this bandit component, we run an OFU algorithm for each individual i with the same unknown loss vector μ. The OFU component for each individual i maintains a confidence ball B^t_i which is independent of the predict-optimize framework. The predict-then-optimize framework produces an estimated optimization objective ĉ^t independent of OFU. The two components are integrated together on Line <ref> of Algorithm <ref>, where we compute the intervention for the current round taking into consideration the essence of both frameworks. 
  
  
  Below, we justify why this algorithm achieves no-regret.
  First, we state a theorem by <cit.>, which states that the confidence ball captures the true loss vector μ with high probability. The result was proved for the original OFU algorithm. However, since the result itself does not depend on the way we choose w^t, it still holds in bandit data-driven optimization.
  We adapt it by adding a union bound so that the result holds for all the n bandits simultaneously.
  
   
  Let γ > 0, then
  ℙ( ∀ t, ∀ i, μ∈ B^t_i) ≥ 1-γ.
  
  The following key lemma decomposes the regret into two components: one involving the online bandit loss, the other concerning the offline supervised learning loss.
  
  
  
  With probability 1-δ, Algorithm <ref> has regret
  
      O ( n√(8m T β^T log T) + ∑_t=1^T ∑_i=1^n  𝔼[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i _2 ] ).
  
  
  
  
  Clearly, to characterize the regret, we need to bound 𝔼[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i _2 ]. In the case of linear regression, we have the following theorem.
  
  
  
  Assuming we use ordinary least squares regression as the ML algorithm, Algorithm <ref> has regret Õ( n√(dmT)) with probability 1-δ.
  
  
  
  
  
  Theorem <ref> assumes a linear regression problem with a specific learning algorithm – ordinary least squares linear regression. If our intent is for Algorithm <ref> to be modular where one can use any learning algorithm, we could resort to sample complexity bounds. In Appendix <ref>, we include a derivation of the regret bound from the sample complexity perspective. This approach allows us to extend the result in Theorem <ref> to a more general setting.
  
  
  
  
  
  
   
   
  
  
  
   §.§ When Interventions Affect Label Distribution
  
  
  So far in this section, we have had the assumption that the action w does not affect the distribution D from which as sample (X, C). In many real-world scenarios this is not the case. For example, if the wildlife patrollers change their patrol routes, the poachers' poaching location would change accordingly and hence its distribution would be very different. Thus, it is valuable to study this more general setting where the intervention could affect the label distribution.
  
  First, let us make the assumption that there are finitely many possible actions. We will consider the continuous action space later.
  Since there are finitely many actions, an intuitive idea is to train an ML predictor for each action separately. Because we do not impose any assumption on our initial dataset, which might only have a single action embedded, we clearly need to use exploration in the bandit algorithm and use the data points gathered along the way to train the predictor. It might seem very natural to fit this directly into the framework of PROOF as shown in Algorithm <ref>: simply maintain several predictors instead of one, and still choose the best action on Line <ref>. However, to train the predictor corresponding to each action, we need at least a certain number of data points to bound the prediction error. Yet, PROOF, and UCB-type algorithms in general, do not give a lower bound on how many times each action is tried. For example, Algorithm <ref> might never try some action at all, and we would not be able to train a predictor for that action. To resolve this philosophical contradiction, we add a uniform exploration phase of length T̃ at the beginning, where at each round 1,2,…, T̃, each action is taken on some examples. 
  Other than this, we inherit all the setup for the analysis in Section <ref>. We describe the detailed procedure as Algorithm <ref> in Appendix <ref>.
  
  We establish the following lemma which decomposes the regret into 3 parts: regret during uniform exploration, regret in UCB bandit, and regret through supervised learning.
  
  
  
  With probability 1-δ, Algorithm <ref> has regret
  
      O   ( nT̃ + n√(8mT β_T log T)
         + ∑_t=T̃ + 1^T ∑_i=1^n 𝔼[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ]  ).
  
  
  
  
  
  By combining Lemma <ref> with previous results, we arrive at the regret of PROOF in this more general setting.
  
  With finitely many actions and OLS as the ML algorithm, Algorithm <ref> has regret Õ( n (d |W|)^1/3 m^1/2 T^2/3).
  
  
  
  
  
  
  
  
  
  We now move on to the scenario where the action space W is continuous. In this case, we assume the true label of feature x under action w is c = Fx + Gw + ϵ where ϵ∼𝒩(0, σ^2 I). A small modification of Algorithm <ref> will work in this scenario: instead of rotating over each action in the uniform exploration phase, we simply pick action w uniformly at random for each individual. Then, the regret of the algorithm is as follows.
  
  
  
  
  Suppose the action space is continuous and the label can be modeled as a linear function of the feature and action. Assuming OLS as the ML algorithm, Algorithm <ref> has regret Õ( m^1/3 d^2/3 n T^2/3).
  
  
  
  
  
  
  
  
   §.§ PROOF Is a Modular Algorithm
  
  In practice, PROOF can be applied beyond the setting under which we proved the previous results. Rather than a fixed algorithm, it is designed to be modular so that we can plug in different learning algorithms and optimization problems. 
  First, instead of linear regression, PROOF can accommodate any predictive model such as tree-based models and neural networks. Second, The nominal optimization problem need not be a linear optimization problem. The optimization problem may be continuous or discrete, convex or non-convex, as we do not concern ourselves with computational complexity in this paper.
  In Section <ref>, we demonstrate that even when we insert complex algorithms into the PROOF framework, thereby going beyond the setting where we established formal regret guarantees, PROOF still works well.
  
  
  
  
  § EXPERIMENTAL RESULTS
  
  
  
   §.§ Numerical Simulations
  
  
  
  
  
  
  As the first step of validation, we implement PROOF in the setting described in Section <ref> on a simulated dataset. 
  We start with a small-scale experiment.
  Recall that we train an ML predictor f̂: X → C where X ⊆ℝ^m and C ⊆ℝ^d. 
  We take feature dimension m=20 and label dimension d=5. At every round we get n=20 data points. As is typical, we assume the bandit reward is bounded in [-1,1] and the feasible region W is the unit l_2-ball. For the true linear map F where c = Fx + ϵ, we upper bound its l_1 matrix norm at 10. We sample the noise ϵ∼𝒩(0, σ^2 I_d) from a normal distribution where σ^2 = 0.1. We take the bandit noise η∼ N(0, 10^-4). We use OLS at each time step. We solve the non-convex program on Line <ref> in Algorithm <ref> with IPOPT. We find the best action given the true reward parameters using Gurobi. 
  We set β^t = 1 so that the algorithm can quickly concentrate on the region of interest.[The code for all the experiments in this section is available at <https://github.com/AIandSocialGoodLab/bandit-data-driven-optimization>]
  
  
  
  The expected cost for a fixed action w is 𝔼_c, η[(c+μ)^† w + η] = 𝔼[x^† F^† w] + μ^† w  = μ^† w,
  because when we generated x, the distribution has zero mean. This problem in theory might be solved as a linear bandit by feeding the total cost to OFU. Since the regret bound of OFU is the same as PROOF in the order of T, this brings back the point that we have been emphasizing since the beginning: if linear bandit is a more general model whose algorithms already solve our problem, why would we care about bandit data-driven optimization? 
  
  In Sections <ref> through <ref>, we answered this question with the characteristics of the food rescue. Here, we answer this question using experiments.
  We show the average regret of PROOF as the orange curve in Figure <ref>, and that of OFU in red. 
  We can decompose the average regret of PROOF into the regret of the optimization component and the regret of the bandit component. The former is simply the algorithm's optimization (known) cost minus the best intervention's optimization cost. The latter is defined similarly. Neither needs to be positive.
  Figure <ref> shows that PROOF quickly reduces the regret in both components, while the performance of vanilla OFU is much more underwhelming. 
  This difference is because an offline predictive model captures the large variance in the implicit context x and c much better.
  In fact, PROOF consistently has much smaller variance than OFU. 
  
  We now tweak the parameters a bit. When we increase the number of data points per iteration from n=20 to 40, Figure <ref> shows that the regret of the optimization component becomes very small to start with, because we have more data to learn from. When we increase ||F|| from 10 to 100, Figure <ref> shows that the optimization regret dominates the total regret, as the optimization cost is now much larger than the bandit cost. Here, vanilla OFU suffers even more, because now its cost signal has even larger magnitude and variance. 
  
  We then scale up the experiments and show that PROOF still outperforms OFU even when the problem parameters are not as friendly. Suppose we get n=500 data points every time and each data point has m=50 features. Keeping all other parameters unchanged, Fig. <ref> shows that PROOF still outperforms OFU by a lot. 
  In Fig. <ref>, we change ||F|| from 10 to 1, making the optimization cost less important. This reduces the variance of OFU and it is doing better than previously. However, our PROOF still outperforms OFU. In Fig. <ref>, we increase the label noise from ϵ∼𝒩(0, 0.1I_d) to 𝒩(0, 0.5I_d). This poses more challenge to PROOF. 
  But still, PROOF manages to keep its regret below OFU.
  
  
  
  
  
  
   §.§ Food Rescue Volunteer Recommendation
  
  
  
  
  Bandit data-driven optimization is motivated by the practical challenges in the deployment of AI for non-profit and public sector projects. After abstracting these challenges to a theoretical model, we now return to the food rescue volunteer recommendation problem. We have introduced the details of food rescue operations in Section <ref>. 
  
  
  There are 100 volunteers. At each time step, we get a new rescue and decide a subset of 10 volunteers to whom we send push notifications. We represent this action with a binary vector w ∈{0,1}^100 such that w_i = 1 if volunteer i is notified and 0 otherwise. Thus, the feasible action space W is {0,1}^100 with the constraint of ∑_i=1^100 w_i ≤ 10. 
  The action w we take at each time step is backed by a content-based ML recommender system. The ML model receives a feature vector x which describes a particular rescue-volunteer pair, and outputs a label prediction ĉ as the likelihood of this volunteer claiming this rescue.[Here the label is 1-dimensional while our action space is 100-dimensional. This is easy to resolve. Each rescue-volunteer pair has m' features. While in practice we have f̂': ℝ^m'→ℝ and pass 100 feature vectors to it serially, one could think of a product model f̂ = ∏_i=1^100f̂' which takes the concatenation of 100 feature vectors and outputs a 100-dimensional vector.] 
  We adapt this ML component from the one studied in <cit.>. Its feature selection, model architecture, and training techniques, are not trivial. Yet, since they are not the focus of this paper, we include all these details in Appendix <ref>.
  The actual label c is a one-hot vector in {0,1}^100 indicating which volunteer actually claimed the rescue.
  The known cost p(c, w) = c^† w is 1 if we notify a volunteer who eventually claimed a rescue and 0 otherwise. To minimize it, we could negate the label c (and its prediction ĉ). The bandit cost q(·) is the same as before. We solve the optimization at each time step of PROOF with Gurobi after applying a standard linearization trick <cit.>. We also gradually decrease the confidence radius β.
  
  
  
  
  Unlike the case in Section <ref>, OFU algorithm does not work here in principle. This is because, working with real-world data, we do not know the data distribution and it is almost certainly not zero-mean. In fact, this experiment has also gone beyond the setting for which we proved formal regret bound for PROOF, yet we would like to see how these two algorithms perform in such a real-world use case.
  
  
  We assume an initial dataset of 300 rescues and run the algorithms for 50 time steps, each time step corresponding to one new rescue. As shown in Figure <ref>, PROOF outperforms vanilla OFU by roughly 15%. The performance gain by PROOF can be contributed to its effective use of the available data, as the progress on bandit made by PROOF and vanilla OFU are quite similar. In Figure <ref>, we scale up the known part of the cost by a factor of 4. Because the optimization is more emphasized, it is unsurprising to see that most of PROOF's progress depends on the recommender system itself. In this case, it has a larger performance margin over vanilla OFU. Finally, in Figure <ref> we decrease the size of the initial dataset from 300 rescues to 20 rescues. We observe that PROOF still has an edge over vanilla OFU. The margin is minimal at the initial time steps, because we have much less initial information here. Yet still, as time goes by PROOF picks up more information in the feature/label dataset to expand its margin. In actual food rescue projects, the amount of initial data is typically more than this, more resembling Figure <ref>, but Figure <ref> assures us that PROOF still works in this more extreme case.
  
  
  
  
  § CONCLUSION
  
  Non-profit and public sectors have huge potential to benefit from the advancing machine learning research. However, plenty of experience shows that the machine learning model itself is almost always not enough to address the real-world societal challenges. Motivated by four practical pain points in such applications, we proposed bandit data-driven optimization, designed the PROOF algorithm, and showed that it has no-regret. Finally, we show its better performance over bandit algorithm in simulations and the food rescue context.
  We view bandit data-driven optimization as our first attempt to bridge the last-mile gap between static ML models and their actual deployment in the real-world non-profit and public context. 
  
  
  § ACKNOWLEDGMENTS
  
  We have learned so much from our collaborators at 412 Food Rescue and other nonprofit organizations and we thank them for what they are doing for our community.
  We thank Thomas G. Dietterich, Fatma Kılınç-Karzan and Kit T. Rodolfa for the inspiring discussions at the early stage of this work.
  This work was supported in part by NSF grants IIS-1850477 and IIS-2046640 (CAREER), a Siebel Scholarship and a Carnegie Mellon Presidential Fellowship. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the funding agencies.
  
  plainnat
  
  
  
  
  
  
  
  § OMITTED PROOFS IN THE MAIN TEXT
  
  
  
  Let w^t_i* = min_w𝔼_c_i^t | x_i^t[c_i^t]^† w and w^t_i = min_wĉ_i^t^† w.
  The expected regret at round t on individual i is 𝔼[r_i^t], where 
  
      r_i^t    = 𝔼[ 𝔼_c_i^t|x_i^t[c_i^t]^† (w^t_i - w^t_i*) ] 
         ≤𝔼[  (𝔼_c_i^t|x_i^t[c_i^t] - ĉ_i^t)^† (w^t_i - w^t_i*) ] 
         = O( 𝔼[ 𝔼_c_i^t|x_i^t[c_i^t] - ĉ_i^t_2 ] )
  
  The first inequality above used the definition of w_i^t and w_i*^t. The second step used Cauchy-Schwartz. Note that what remains to prove is simply an error bound on the OLS regression, which we prove as Lemma <ref>. Using that result, we can conclude the total regret is
  
      R_T    = 𝔼[∑_t=1^T ∑_i=1^n r_i^t]
         = O( ∑_t=1^T ∑_i=1^n 𝔼[ 𝔼_c_i^t|x_i^t[c_i^t] - ĉ_i^t_2 ] )
         = O( ∑_t=1^T ∑_i=1^n √(dm/nt)) 
         = O(√(ndmT))
  
  The last step (bounding ∑_t=1^T t^-1/2) is by an upper bound on the generalized harmonic numbers, which can be found in Theorem 3.2 (b) in the text by <cit.>.
  
  
  
  Recall that ℱ is the class of all linear functions mapping X to C and c = Fx + ϵ where F ∈ℱ and ϵ∼𝒩(0, σ^2 I_d).  Assume that n > m, that is, assume the number of data points we receive each round is greater than the number of features.
  Let F_k be the k-th row of F. Fix k, we have a linear regression problem c_k = F_k^† x + ϵ_k, where ϵ_k ∼𝒩(0, σ^2). At the t-th round, we have nt data points and we need to predict on n new data points. Let X^t be the n × m matrix whose i-th row is x^t_i. Let X̃^t be the nt × m matrix consisting of all the training data points. 
  Suppose we fun an ordinary least wquares regression. Let F̂_k be the OLS estimate of F_k, and ĉ_k = F̂_k x. 
  
  
  Suppose we use the ordinary least squares regression as the ML algorithm. The prediction error is 
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2 ] = O(√(dm/nt)),
  
  assuming either (1) x ∼𝒩(0, Λ) follows a normal distribution, or (2) the eigenvalues of Σ = X̃^t^†X̃^t/nt are lower bounded by a positive number.
  
  
  
  
  
  Consider the first case, since x ∼𝒩(0, Λ),
  we know X^T^† X^t ∼ W(Λ, n), a Wishart distribution with n degrees of freedom, and X̃^T^†X̃^t ∼ W(Λ^-1, nt), an inverse Wishart distribution with nt degrees of freedom. Thus, 𝔼_X[(X^t^† X^t)^-1] = nΛ and 𝔼_X[(X̃^t^†X̃^t)^-1] = Λ^-1/(nt-m-1). 
  
      𝔼[∑_i=1^n (𝔼_c_ik^t | x_i^t[c_ik^t] - ĉ^t_ik)^2 ] = 𝔼[ ||X^t (F_k - F̂_k)||_2^2 ] 
         = 𝔼[ (F_k - F̂_k)^† X^t^† X^t (F_k - F̂_k) ] 
         = 𝔼[ tr( (F_k - F̂_k)^† X^t^† X^t (F_k - F̂_k) )] 
         =  tr ( 𝔼[X^t^† X^t] 𝔼_X[ (F_k - F̂_k) (F_k - F̂_k)^†] ) 
         = σ^2  tr( 𝔼[X^t^† X^t] 𝔼_X[ (X̃^t^†X̃^t)^-1] )
         = σ^2  tr(  n ΛΛ^-1/nt-m-1) = nmσ^2 /nt-m-1
  
  The above derivation has appeared in previous literature, e.g. the work by <cit.>. The result holds for all k, we get 
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2^2 ]  = mdσ^2 /nt-m-1.
  
  That is,
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2 ] = O(√(dm/nt)).
  
  
  
  In the second case, suppose the eigenvalues of Σ = X̃^t^†X̃^t/nt are lower bounded by a constant K_Σ > 0.
  
      𝔼_X, ϵ[ |𝔼_c_ik^t | x_i^t[c_ik^t] - c^t_ik| ] =  𝔼_X, ϵ[  | F_k^†  x^t_ik - F̂_k^† x^t_ik| ]
         ≤𝔼_X[ |F_k^†  x^t_ik - F̂_k^† x^t_ik| ] 
          ≤𝔼_X[  F_k- F̂_k _2   x^t_ik_2 ] 
         ≤ K_X 𝔼_X[  F_k- F̂_k _2^2  ]^1/2 
          = K_X 𝔼_X [ tr(σ^2 (X̃^t^†X̃^t)^-1 ) ]^1/2
         =  σ K_X/√(nt)𝔼_X [ tr (Σ^-1) ]^1/2
  
  Then the prediction error can be bounded by
  
      𝔼_X, ϵ[ |𝔼_c_ik^t | x_i^t[c_ik^t] - ĉ^t_ik| ] ≤  O( √(m/nt))
  
  This holds for all k. Thus, we have
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2 ] ≤  O( √(md/nt))
  
  
  
  
  
  Let w^t_i* = min_w (𝔼_c_i^t | x_i^t[c_i^t] + μ)^† w. w^t_i* is the optimal action for individual i at time t, and is the benchmark in our regret computation.
  
  Fix i, fix t. Let ν̃= min_ν∈ B^t_i (ĉ^t_i + ν)^† w^t_i.
  Because of Line <ref>, we have
  
      (ĉ^t_i + ν̃)^† w^t_i = min_ν∈ B^t_i, w∈ W (ĉ^t_i + ν)^† w 
         ≤ (𝔼_c_i^t | x_i^t[c_i^t] + μ)^† w^t_i* + (ĉ^t_i)^† w^t_i* - 𝔼_c_i^t | x_i^t[c_i^t]^† w^t_i*.
  
  The inequality above used the fact that μ∈ B_i^t, by Lemma <ref>.
  Thus, we get the per-round regret
  
      (𝔼_c_i^t | x_i^t[c_i^t] + μ)^† (w^t_i - w^t_i*) 
         ≤ (𝔼_c_i^t | x_i^t[c_i^t] + μ)^† w^t_i - (ĉ^t_i + ν̃)^† w^t_i + (ĉ^t_i)^† w^t_i*
         - 𝔼_c_i^t | x_i^t[c_i^t]^† w^t_i*
         = (𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i)^† (w^t_i - w^t_i*) + (μ - ν̃)^† w^t_i
  
  We can view the second term is the per-round regret for the bandit part. By Theorem 6 in <cit.>, we have
  
      ∑_t=1^T ((μ - ν̃)^† w^t_i)^2 ≤ 8m β^T log T
  
  Using the Cauchy-Schwarz, we get 
  
      ∑_t=1^T (μ - ν̃)^† w^t_i ≤√(8m T β^T log T)
  
  Thus, the regret of Algorithm <ref> is
  
      𝔼[ ∑_t=1^T ∑_i=1^n (𝔼_c_i^t | x_i^t[c_i^t] + μ)^† (w^t_i - w^t_i*) ] 
         ≤𝔼[ ∑_t=1^T ∑_i=1^n (𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i)^† (w^t_i - w^t_i*) ] 
         + n√(8mT β_T log T)
          = O(  ∑_t=1^T ∑_i=1^n 𝔼[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i _2 ] + n√(8mT β_T log T))
  
  The last step used Cauchy-Schwartz and the bounded action space assumption.
  
  
  
  
  Combine Lemma <ref> and Lemma <ref>.
  
  
  
  
  
  
  In Algorithm <ref>, at each round 1,2,…, T̃ in the exploration phase, each action is sequentially taken on some examples. This means by the end of step T̃, we have ñ = nT̃/|W| data points for training the predictor for each w_i. Although in practice one can keep updating (learning) the predictor during the exploitation phase, in the following theoretical analysis it suffices to ignore this additional learning effect.
  We assume ñ is an integer, but this is not an issue in the general case.
  
  Let us first analyze the regret in the exploitation phase.
  
  Let w^t_i* = min_w (𝔼_c_i^t | x_i^t, w [c^t_i(w)] + μ)^† w. w^t_i* is the optimal action for individual i at time t, and is the benchmark in our regret computation.
  
  Fix i, fix t. Let ν̃= min_ν∈ B^t_i (ĉ^t_i(w^t_i) + ν)^† w^t_i.
  Because of Line <ref>, we have
  
      (ĉ^t_i(w^t_i) + ν̃)^† w^t_i = min_ν∈ B^t_i, w∈ W (ĉ^t_i(w) + ν)^† w 
         ≤ (𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)] + μ)^† w^t_i* + (ĉ^t_i(w^t_i*))^† w^t_i*
         -  𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)]^† w^t_i*.
  
  The inequality above used the fact that μ∈ B_i^t, by Lemma <ref>.
  Thus, we get the per-round regret
  
      (𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] + μ)^† w^t_i - (𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)] + μ)^† w^t_i*
         ≤ (𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] + μ)^† w^t_i  - (ĉ^t_i(w^t_i) + ν̃)^† w^t_i  
         + (ĉ^t_i(w^t_i*))^† w^t_i* - 𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)]^† w^t_i*
         = (𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i))^† w^t_i 
         + (ĉ^t_i(w^t_i*) -𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)])^† w^t_i* + (μ - ν̃)^† w^t_i
  
  We can view the third term as the per-round regret for the bandit part. By Theorem 6 in <cit.>, we have
  
      ∑_t=1^T ((μ - ν̃)^† w^t_i)^2 ≤ 8m β^T log T
  
  Using the Cauchy-Schwarz, we get 
  
      ∑_t=1^T (μ - ν̃)^† w^t_i ≤√(8m T β^T log T)
  
  Thus, the regret of Algorithm <ref> is upper bounded by
  
      𝔼[ ∑_t=1^T ∑_i=1^n (𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] + μ)^† w^t_i - (𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)] + μ)^† w^t_i*]
         ≤ K n T̃ + 𝔼[ ∑_t=T̃ + 1^T ∑_i=1^n (𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i))^† w^t_i
         + (ĉ^t_i(w^t_i*) -𝔼_c_i^t | x_i^t, w^t_i* [c^t_i(w^t_i*)])^† w^t_i*] + n√(8mT β_T log T)
          = O( nT̃ + n√(8mT β_T log T)
         + ∑_t=T̃ + 1^T ∑_i=1^n 𝔼[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ]  )
  
  The last step used Cauchy-Schwartz, symmetry, and the bounded action space assumption.
  
  
  
  
  
  Again, we prove by bounding the linear regret prediction error. The proof follows identically as Theorem <ref>. We get, ∀ t > T̃, ∀ w, ∀ i,
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ] = O(√(dm |W|/nT̃)).
  
  Using Lemma <ref>, and taking T̃ = T^2/3 (d|W|)^1/3, we get
  
      O( nT̃ + n√(8mT β_T log T) + ∑_t=T̃ + 1^T ∑_i=1^n √(dm |W|/nT̃))
         = O( nT̃ + n√(8mT β_T log T) + T  √(ndm |W|/T̃))
         = Õ( (d |W|)^1/3 m^1/2 n T^2/3)
  
  
  
  
  Using Lemma <ref>, we know that at the beginning of the exploitation phase, the prediction error is 
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ] = O(√((m+d)d/nT̃)),
  
  ∀ t > T̃, ∀ w, ∀ i.
  Thus, using Lemma <ref>, we know the regret is Õ( m^1/3 d^2/3 n T^2/3), when we take T̃ = m^1/3 d^2/3 T^2/3. 
  
  
  
  
  § OMITTED ALGORITHM
  
  
  
  
  
  
  
  
  
  
  § REGRET BOUNDS USING SAMPLE COMPLEXITY CHARACTERIZATION
  
  
  Let us first introduce the multivariate Rademacher complexity and its associated generalization bounds, which were introduced by <cit.>.
  
  
  Given a sample S_n = {s_1,…, s_n }, the empirical multivariate Rademacher complexity of a class of functions ℱ taking values in ℝ^d is defined as
  
      ℜ̂_n(ℱ; S_n) = 𝔼_σ[ sup_g ∈ℱ1/n∑_i=1^n ∑_k=1^d σ_ik g_k(s_i) ]
  
  where σ_ik's are independent Rademacher random variables.
  The multivariate Rademacher complexity is defined as ℜ_n(ℱ) = 𝔼_S_n [ℜ̂_n(ℱ; S_n)]
  
   <cit.>
  Suppose function c(z; y) is bounded and equi-Lipschitz in z:
  
      sup_z ∈ Z, y ∈ Y c(z; y) ≤c̅, andsup_z ≠ z' ∈ Z, y ∈ Yc(z;y) - c(z';y)/||z - z'||_∞≤ L < ∞
  
  For any δ > 0, each of the following events occurs with probability at least 1-δ,
  
      𝔼[c(z(X);Y )] 
         ≤1/n∑_i=1^n c(z(x^i); y^i) + L ℜ_n(ℱ) + c̅√(log(1/δ)/2n)
         𝔼[c(z(X);Y )] 
         ≤1/n∑_i=1^n c(z(x^i); y^i) + L ℜ̂_n(ℱ; S_n) + 3c̅√(log(2/δ)/2n).
   
  
  
  When the function c(z; y) is nonnegative, we have
  
      𝔼[c(z(X);Y )] 
         ≤1/1-δ𝔼[ 1/n∑_i=1^n c(z(x^i); y^i) ] + L ℜ_n(ℱ) + c̅√(log(1/δ)/2n)
  
  
  
  Before we proceed, we make the following assumption.
  
  
  With n training data points x_1,… x_n, the learning algorithm learns a predictor f̂ such that 𝔼[ ∑_i=1^n    f(x_i) - f̂(x_i) _2^2  ]
  is constant with respect to n.
  
  
  
  
  Although this assumption might appear somewhat unintuitive, it is actually satisfied when, for example, f ∈ℱ comes from the class of all linear functions, ordinary least squares regression used as the learning algorithm satisfies this assumption. In that case, we have 𝔼[ ∑_i=1^n    f(x_i) - f̂(x_i) _2^2  ] = O(md).
  
  
  
  Suppose we use any learning algorithm that satisfies Assumption <ref>, including but not limited to OLS regression. The regret of Algorithm <ref> is Õ(md √(nT)), with probability 1 - δ.
  
  
  
  First, let's compute the Rademacher complexity of the linear hypothesis class, for completeness and for our specific setting.
  Let F_k be the k-th row of matrix F. We have
  
      ℜ̂_n(ℱ; X_n)
          = 𝔼_σ[ sup_F ∈ℱ1/n∑_i=1^n ∑_k=1^d σ_ik F_k^† x_i ] 
         = 𝔼_σ[ sup_F ∈ℱ1/n∑_k=1^d  F_k^†(∑_i=1^n  σ_ik  x_i ) ] 
         ≤𝔼_σ[ sup_F ∈ℱ1/n∑_k=1^d  ||F_k||_1 ∑_i=1^n  σ_ik  x_i _2 ]   (Cauchy-Schwartz)
         ≤𝔼_σ[ sup_F ∈ℱ1/n∑_k=1^d  ||F||_∞∑_i=1^n  σ_ik  x_i _2 ]
         ≤∑_k=1^d  m K_F 𝔼_σ[ 1/n∑_i=1^n  σ_ik  x_i _2 ] 
         ≤∑_k=1^d  m K_F (𝔼_σ[ 1/n∑_i=1^n  σ_ik  x_i _2^2 ] )^1/2    (Jensen)
         ≤∑_k=1^d  m K_F (𝔼_σ[  1/n^2∑_i=1^n  ||x_i||_2^2 + 2/n^2∑_i<jσ_ikσ_jk x_i^† x_j  ] )^1/2
         = ∑_k=1^d  m K_F (𝔼_σ[  1/n^2∑_i=1^n  ||x_i||_2^2   ] )^1/2 =  d m K_F K_X/√(n)
  
  Using Equation <ref>, we have
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2 ]
         ≤1/(1-δ)nt𝔼[ ∑_i=1^n ∑_τ=1^t   f(x_i^τ) - f̂(x_i^τ) _2 ] 
         + L ℜ_nt(ℱ) + c̅√(log(T/δ)/2nt)
         ≤1/(1-δ)nt𝔼[ √( nt ∑_i=1^n ∑_τ=1^t   f(x_i^τ) - f̂(x_i^τ) _2^2 )] 
         + L ℜ_nt(ℱ) + c̅√(log(T/δ)/2nt)
         ≤1/(1-δ)√(nt)√(𝔼[ ∑_i=1^n ∑_τ=1^t   f(x_i^τ) - f̂(x_i^τ) _2^2  ] )
         + L ℜ_nt(ℱ) + c̅√(log(T/δ)/2nt)
  
  By Assumption <ref>, the term under square root is constant w.r.t. nt, under regularity conditions. Thus, we have
  
      𝔼_X, ϵ[ 𝔼_c_i^t | x_i^t[c_i^t] - ĉ^t_i_2 ] = Õ( md (nt)^-1/2)
  
  The rest of the proof follows from Lemma <ref>. 
  
  
  This result is almost identical as Theorem <ref>. However, the intent to work with Rademacher complexity is that we hope to at least get some bound when we move beyond the linear regression scenario. Let us consider a feed-forward neural network with ReLU activation. There are existing results which shows that the Rademacher complexity is O(1/√(n)) <cit.>. Thus, if we accept Assumption <ref>, we would have the following result.
  
  
  Supose the learning problem is fitting a neural network and we use any learning algorithm that satisfies Assumption <ref>. The regret of Algorithm <ref> is Õ(n T^1/2), with probability 1-δ-λ, ignoring the dependency on d and m.
  
  
  
  
  Finally, we extend the previous results to the more general case where interventions affect the label distribution. Please refer to the setting described in Section <ref> and Algorithm <ref> in Appendix <ref>. 
  
  Suppose there are finitely many actions. Assuming we use any learning algorithm that satisfies Assumption <ref>, including but not limited to OLS regression, the regret of Algorithm <ref> is Õ(|W|^1/3 (md)^2/3 n T^2/3), with probability 1 - δ.
  
  
  
  After the exploration phase, we have had ñ = nT̃/|W| data points for training the predictor for each w_i. 
  Similar to our approach in Theorem <ref>, we have
  
      𝔼[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ] 
         ≤1/(1-δ)ñ𝔼[ ∑_i=1^ñ f(x_i) - f̂(x_i) _2^2 ] 
         + L ℜ_ñ(ℱ) + c̅√(log(T/δ)/2ñ)
         = Õ(|W|^1/2 md (n T̃)^-1/2),    ∀ t > T̃
  
  Thus, the regret is
  
      O( nT̃ + n√(8mT β_T log T)
         + ∑_t=T̃ + 1^T ∑_i=1^n 𝔼[ 𝔼_c_i^t | x_i^t, w_i^t [c^t_i(w_i^t)] - ĉ^t_i(w^t_i) _2 ]  )
         = Õ( nT̃ + n√(8mT β_T log T) + nT |W|^1/2 dm(n T̃)^-1/2)
         = Õ(  |W|^1/3 (md)^2/3 n T^2/3)
  
  where we let T̃ = T^2/3 |W|^1/3 (md)^2/3. 
  
  
  
  
  
  § DETAILS OF THE FOOD RESCUE EXPERIMENT
  
  
  
  In this section, we provide additional information about the ML recommender system component of the food rescue experiment in Section <ref>. The data description and feature engineering in Appendix <ref> is adapted from <cit.> to serve our purpose. The design and training of the recommender system in Appendix <ref> and Appendix <ref> are novel of this work.
  
  
  
  
  
   §.§ Data
  
  
  To develop a recommender system, we need both positive and negative labeled examples. A positive example means that a particular volunteer (item) claims a particular rescue (user); a negative example means the volunteer does not claim the rescue. In this section, we detail our data acquisition, labeling, and feature engineering process.
  
  
  
    
  Positive Labels
  We obtained the rescue database from our partner organization, covering the period from March 2018 to March 2020. The database keeps the log of each rescue. For most rescues, the database logs its timestamps from being drafted by the dispatcher, to being published on the mobile app, to being claimed and completed by a volunteer. We take the rescue plus the volunteer who claimed it as a positive data point. 
  
  
  
    
  Negative Labels
  
  A negative example means that a particular volunteer did not claim a particular rescue. Since almost all rescues have only one volunteer who claimed the rescue, obviously most of our data points will have negative labels. However, not all of these negative data points are necessarily true, because perhaps a volunteer would have claimed some rescue if someone else had not claimed it 10 minutes in advance. Thus, we use the following ways to construct a selected negative dataset. First, in the time period covered by our database, our partner used a mobile app push notification scheme which notifies volunteers within 5 miles when the rescue is first available and then notifies all volunteers 15 minutes later if the rescue has not been claimed. Thus, if a rescue is claimed within 15 minutes, we only treat the volunteers who were within 5 miles and did not opt out of push notifications as negative examples. 
  
  We also incorporate another data source to strengthen our negative sampling. In addition to mobile app notifications, the dispatcher at our partner organization also manually call some regular volunteers to ask for help with a specific rescue. This usually happens when some rescue has been available for over an hour yet nobody has claimed it. We obtained the call history, from which we identify the volunteers they reached out to within the time frame of each rescue. If these volunteers did not claim the rescues in the end, we treat them as negative examples. Compared to the negative examples derived from push notifications, we have more confidence in this set of negative examples, since declining on a phone call is a stronger indicator than ignoring a push notification.
  
  
  
    
  Feature Engineering
  
  
  
  Based on our collaboration with our partner, we carefully identify a selected set of useful features that are relevant in the food rescue operation. 
  
  
  
  First, the experience of food rescue dispatcher indicates that if a volunteer has completed a rescue at or near a donor or recipient, they are more likely to do a rescue trip again in the neighborhood. As shown in Figure <ref>, we divide the region of interest into 16 cells. We evenly divide a central rectangular region into a 3 × 5 grid, and label them grid cells 0 through 14. Then, we label the entire map outside the rectangular region cell 15. The rationale is that in the outer suburbs there are fewer donors, recipients, and volunteers, and furthermore volunteers who live in suburbs are more willing to do long-distance, i.e. inter-cell, rescue than volunteers in downtown. For each rescue trip and each volunteer, we calculate the number of rescues the volunteer has done in the rescue donor's cell, in the rescue recipient's cell, and across all cells. We also tried to include as features the volunteer's historical rescues in each cell, not just the donor's and recipient's cell. However, they did not contribute any predictive power and thus we leave them out of the final model.
  
  Closely related to this is the distance between the volunteer and the donor. It is unlikely that a volunteer would drive 30 miles to pick up a donation. We measure the distance using the straight line distance based on geographic coordinates. Although the actual traveling distance might be a better indicator, we observe that the straight line distance already serves our purpose. 
  
  
  
  Aside from the geographical information, the length of time between volunteer's registration on the platform and the rescue is also an important factor, as suggested by our partner. Immediately after registration, the volunteer is eager to claim a rescue to get a feel of the food rescue experience. Thus, we include this feature in our prediction model. 
  
  Weather information is also an important factor in the prediction. Presumably rainy and snowy days would see a lower volunteer activity in general. However, the impact of inclement weather would fall disproportionately on volunteers who do not have a car or live in suburban areas. We use the Climate Data Online (CDO) service provided by the National Oceanic and Atmospheric Administration to access the weather information.[<https://www.ncdc.noaa.gov/cdo-web/>] The CDO dataset contains weather information at the discretization level of days and weather station. There are multiple weather stations in the area and for each rescue we select the data for the date of rescue and the station that is closest to the donor organization. As shown in Figure <ref>, on wet days, relatively more volunteers who claim the rescue reside in downtown (cell 4 and 7). Whereas on dry days, a lot more volunteers who live in the outer suburbs (cell 15) are active. In fact, we also saw a significant difference in the average distance between volunteer and donor for dry days (5.94 miles) and rainy days (5.22 miles), with a t-test p-value 3× 10^-8.
  
  
  
  We also explored a number of other features but did not incorporate them into our final model. These features include the rescue's time of day and day of week, the volunteer's availability, whether the volunteer uploaded an avatar to their profile or not, whether the volunteer is located in the same grid as the donor or recipient, and so on. Although these are intuitive factors, we did not find them improve the predictive power of our model and hence left them out. 
  
  
  
  
   §.§ Recommender System Model
  
  
  We build our recommender system using a neural network.
  We show the neural network architecture in Table <ref>. The input to the neural network is the feature vector of a rescue-volunteer pair. The feature vector passes through three dense layers. Each layer is followed by a ReLU activation function, except for the last layer where we output a single number which is then converted to a number between 0 and 1 by the logistic function. This output represents the likelihood that this volunteer will claim this rescue trip. We use the cross entropy loss to train the neural network. At prediction time, for a given rescue, we pass the feature vectors of the rescue-volunteer pairs for all volunteers on a fixed rescue through the network and obtain a likelihood estimate for each volunteer.
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Training
  
  
  We performed all the experiments in this paper on an Intel Core i5-7600K CPU and 32GB RAM.
  
  We use the data from March 2018 to October 2019 for feature preparation. Recall that some of the features we use are related to the volunteer's historical number of rescues. We use the data from this period to generate such features. Then, we use the 556 rescues from November 2019 to March 2020 for learning and prediction in the actual experiment. In this way we avoid the potential data leakage.
  
  In these 556 rescues, we select the first 300 of them to be the initial dataset for the bandit data-driven optimization (refer to Line <ref> in Procedure <ref>, Section <ref>). From the remaining 256 rescues, we randomly sample and set aside 150 rescues as the validation dataset. Finally we take the 50 earliest rescues from the remaining 106 rescues to run the PROOF algorithm for 50 iterations, each iteration corresponding to one rescue. At time step t, our training set consists of the 300 rescues in the initial dataset and all the rescues we have seen from time step 1 up to time step t-1. When training the recommender system at each time step, we use the Adam optimizer with learning rate 1 × 10^-3. We stop the training when the 3-episode moving average loss on the validation set stops decreasing. In the following paragraph, we discuss our way to address a key challenge in the training dataset in more detail.
  
  
  
  
  
    
  Negative Sampling
  
  As mentioned earlier, there is an extremely high label imbalance in our dataset. Each rescue typically has only one volunteer who claimed it, which means, theoretically, the ratio between negative and positive examples is about 100:1. Using the method introduced in Section <ref>, we can obtain a selected set of negative examples D_n derived from push notifications and another set of negative examples D_c derived from dispatcher calls. The set D_c is about the same size as the positive examples D_p, while |D_n| : |D_p| ≈ 11:1. When training the neural network, we always use all the examples from D_p and D_c. However, we randomly sample a subset of examples from D_n at each episode of the training. By doing this, we ensure that the negative examples from D_n do not dominate the training set, and at the same time the “more certain” negative examples from D_c gets emphasized more than D_n. This whole procedure leads to an overall ratio between negative and positive samples around 3.5:1 in each single batch.
  
  
  
    
  Hyperparameters
  We ran a grid search over the hyperparameters of the ML model on an offline recommendation task. In the search process, we used the data from March 2018 to October 2019 (i.e. not including the data we test PROOF on), where the first 7/8 of the selected data are used as the training set and the last 1/8 are used as the validation set. We show the search result in Table <ref>.
  
  
  
  
  