Neural Pseudo-Label Optimism for the Bank Loan Problem
Year: 2022

Abstract:
We study a class of classification problems best exemplified by the bank loan problem, where a lender decides whether or not to issue a loan. The lender only observes whether a customer will repay a loan if the loan is issued to begin with, and thus modeled decisions affect what data is available to the lender for future decisions. As a result, it is possible for the lender’s algorithm to “get stuck” with a self-fulfilling model. This model never corrects its false negatives, since it never sees the true label for rejected data, thus accumulating infinite regret. In the case of linear models, this issue can be addressed by adding optimism directly into the model predictions. However, there are few methods that extend to the function approximation case using Deep Neural Networks. We present PseudoLabel Optimism (PLOT), a conceptually and computationally simple method for this setting applicable to DNNs. PLOT adds an optimistic label to the subset of decision points the current model is deciding on, trains the model on all data so far (including these points along with their optimistic labels), and finally uses the resulting optimistic model for decision making. PLOT achieves competitive performance on a set of three challenging benchmark problems, requiring minimal hyperparameter tuning. We also show that PLOT satisfies a logarithmic regret guarantee, under a Lipschitz and logistic mean label model, and under a separability condition on the data.

heading: 1 Introduction
text: Binary classification models are used for online decision-making in a wide variety of practical settings. These settings include bank lending [44, 22, 42], criminal recidivism prediction [43, 45, 5], credit card fraud [7, 41], spam detection [20, 39], self-driving motion planning [35, 28], and recommendation systems [36, 10, 18]. In many of these tasks, the model only receives the true labels for examples accepted by the learner. We refer to this class of online learning problem as the bank loan problem (BLP), motivated by the following prototypical task. A learner interacts with an online sequence of loan applicants. At the beginning of each time-step the learner receives features describing a loan applicant, from which the learner decides whether or not to issue the requested loan. If the learner decides to issue the loan, the learner, at some point in the future, observes whether or not the applicant repays the loan. If the loan is not issued, no further information is observed by the learner. The process is then repeated in the subsequent time-steps. The learner’s objective is to maximize its reward by handing out loans to as many applicants that can repay them and deny loans to applicants unable to pay them back.
The BLP can be viewed as a contextual bandit problem with two actions: accepting/rejecting a loan application. Rejection carries a fixed, known, reward of 0: with no loan issued, there is no dependency on the applicant. If in contrast the learner accepts a loan application, it receives a reward of 1 in case the loan is repaid and suffers a loss of −1 if the loan is not repaid. The probabilities of repayment ∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
associated to any individual are not known in advance, thus the learner is required to build an accurate predictive model of these while ensuring not too many loans are handed out to individuals who can’t repay them and not too many loans are denied to individuals that can repay. This task can become tricky since the samples used to train the model, which govern the model’s future decisions, can suffer from bias as they are the result of past predictions from a potentially incompletely trained model. In the BLP setting, a model can get stuck in a self-fulfilling false rejection loop, in which the very samples that could correct the erroneous model never enter the training data in the first place because they are being rejected by the model.
Existing contextual bandit approaches typically assume a known parametric form on the reward function. With restrictions on the reward function, a variety of methods ([13, 8]) introduce strong theoretical guarantees and empirical results, both in the linear and generalized linear model settings2. These methods often make use of end-to-end optimism, incorporating uncertainty about the reward function in both the reward model and decision criteria.
In practice, however, deep neural networks (DNNs) are often used to learn the binary classification model [38, 47], presenting to us a scenario that is vastly richer than the linear and generalized linear model assumptions of many contextual bandit works. In the static setting these methods have achieved effective practical performance, and in the case of [47], theoretical guarantees. A large class of these methods use two components: a feature extractor, and a post-hoc exploration strategy fed by the feature extractor. These methods leave the feature extractor itself open to bias, with the limited post-hoc exploration strategy. Another class of methods incorporate uncertainty into the neural network feature extractor ([32]), building on the vast literature on uncertainty estimation in neural networks.
We introduce an algorithm, PLOT (see Algorithm 1), which explicitly trains DNNs to make optimistic online decisions for the BLP, by incorporating optimism in both representation learning and decision making. The intuition behind PLOT’s optimistic optimization procedure is as follows:
“If I trained a model with the query point having a positive label, would it predict it to be positive?"
If the answer to this question is yes, PLOT would accept this point. To achieve this, at each time step, the PLOT algorithm re-trains its base model, treating the new candidate points as if they had already been accepted and temporarily adds them to the existing dataset with positive pseudo-labels. PLOT’s accept and reject decisions are based on the predictions from this optimistically retrained base model. The addition of the fake pseudo-labeled points prevents the emergence of self-fulfilling false negatives. In contrast to false rejections, any false accepts introduced by the pseudo-labels are self-correcting. Once the model has (optimistically) accepted enough similar data points and obtained their true, negative label, these will overrule the impact of the optimistic label and result in a reject for novel queries.
While conceptually and computationally simple, we empirically show that PLOT obtains competitive performance across a set of 3 different benchmark problems in the BLP domain. With minimal hyperparameter tuning, it matches or outperforms greedy, -greedy (with a decaying schedule) and state-of-the-art methods from the literature such as NeuralUCB[47]. Furthermore, our analysis shows that PLOT is 3-5 times more likely to accept a data point that the current model rejects if the data point is indeed a true accept, compared to a true reject.

heading: 1.1 Related Work
text: Contextual Bandits As we formally describe in Section 2, the BLP can be formulated as a contextual bandit. Perhaps the most related setting the BLP in the contextual bandits literature is the work of [30]. In their paper the authors study the loan problem in the presence of offline data. In contrast with our definition for the BLP, their formulation is not concerned with the online decision making component of the BLP, the main point of interest in our formulation. Furthermore, their setting is also concerned with studying ways to satisfy fairness constraints, an aspect of the loan problem that we consider completely orthogonal to our work. Other recent works have forayed into the analysis and deployment of bandit algorithms in the setting of function approximation. Most notably the
2In a linear model the expected response of a point x satisfies ȳ = x>θ, whereas in a generalized linear model the expected response satisfies ȳ = µ(x>θ) for some non-linearity µ, typically assumed to be the logistic function.
authors of [38] conduct an extensive empirical evaluation of existing bandit algorithms on public datasets. A more recent line of work has focused on devising ways to add optimism to the predictions of neural network models. Methods such as Neural UCB and Shallow Neural UCB [47, 46] are designed to add an optimistic bonus to the model predictions, that is a function of the representation layers of the model. Their theoretical analysis is inspired by insights gained from Neural Tangent Kernel (NTK) theory. Other recent works in the contextual bandit literature such as [14] have started to pose the question of how to extend theoretically valid guarantees into the function approximation scenario, so far with limited success [40]. A fundamental component of our work that is markedly different from previous approaches to is to explicitly encourage optimism throughout representation learning, rather than post-hoc exploration on top of a non-optimistic representation.
Learning with Abstention The literature on learning with abstention shares many features with our setting. In this literature, an online learner can choose to abstain from prediction for a fixed cost, rather than incurring arbitrary regret[9]. In our setting, a rejected point always receives a constant reward, similar to learning with abstention. However, here, regret in the BLP is measured against the potential reward, rather than against a fixed cost. Although the BLP itself does not naturally admit abstention, the extension of PLOT to abstention setting is an interesting future problem.
Repeated Loss Minimization A closely related problem setting to the BLP (see Section 2) is Repeated Loss Minimization. Previous works [17] have studied the problem of repeated classification settings where the acceptance or rejection decision produces a change in the underlying distribution of individuals faced by the decision maker. In their work, the distributional shift induced by the learner’s decisions is assumed to be intrinsic to the dynamics of the world. This line of work has recently garnered a flurry of attention and inspired the formalization of different problem domains such as strategic classification [15] and performative prediction [37, 31]. A common theme in these works is the necessity of thinking strategically about the learner’s actions and how these may affect its future decisions as a result of the world reacting to them. In this paper we focus on a different set of problems encountered by decision makers when faced with the BLP in the presence of a reward function. We do not treat the world as a strategic decision maker, instead we treat the distribution of data points presented to the learner as fixed, and focus on understanding the effects that making online decisions can have on the future accuracy and reward experienced by an agent engaged in repeated classification. The main goal in this setting is to devise methods that allow the learner to get trapped in false rejection or false acceptance cycles that may compromise its reward. Thus, the learner’s task is not contingent on the arbitrariness of the world, but on a precise understanding of its own knowledge of the world.
Learning with partial feedback In [39], the authors study the one-sided feedback setting for the application of email spam filtering and show that the approach of [19] was less effective than a simple greedy strategy. The one-sided feedback setting has in common with our definition of the BLP the assumption that an estimator of the instantaneous regret is only available in the presence of an accept decision. The main difference between the setting of [19] and ours is that the BLP is defined in the presence of possibly noisy labels. Moreover our algorithm PLOT can be used with powerful function approximators, a setting that goes beyond the simple label generating functions studied in [19]. In a related work [4] considers the problem of one-sided learning in the group-based fairness context with the goal of satisfying equal opportunity [16] at every time-step. They consider convex combinations over a finite set of classifiers and arrive at a solution which is a randomized mixture of at most two of these classifiers. Moving beyond the single player one-sided feedback problem [6] studies a setting which generalizes the one-sided feedback, called partial monitoring, through considering repeated two-player games in which the player receives a feedback generated by the combined choice of the player and the environment, proposing a randomized solution. [2] provides a classification of such two-player games in terms of the regret rates attained and [3] study a variant of the problem with side information.

heading: 2 Setting
text: We formally define the bank loan problem (BLP) as a sequential contextual binary decision problem with conditional labels, where the labels are only observed when datapoints are accepted. In this setting, a decision maker and a data generator interact through a series of time-steps, which we index
by time t. At the beginning of every time-step t, the decision maker receives a data point xt ∈ Rd and has to decide whether to accept or reject this point. The label yt ∈ {0, 1}, is only observed if the data point is accepted. If the datapoint is rejected the learner collects a reward of zero. If instead the datapoint is accepted the learner collects a reward of 1 if yt = 1 and −1 otherwise. Here, we focus our notation and discussion on the setting where only one point is acted upon in each time-step. All definitions below can be extended naturally to the batch scenario, where a learner receives a batch of data points xt,1, · · · ,xt,B , and sees labels for accepted points (yt,1 · · · , yt,B′ ), yt ∈ {0, 1} in each time-step, where B is the size of the batch, and B ′ is the number of accepted points.
In the BLP, contexts (unlabeled batches of query points) do not have to be IID – their distributions, P(x), may change adversarially. As a simple example, the bank may only see applicants for loans under $1000, until some time point t, where the bank sees applicants for larger loans. Although contexts do not have to be IID, we assume that the reward function itself is always stationary – i.e. the conditional distribution of the responses, P(y|x), is fixed for all t. Finally, in the BLP, it is common for rewards to be delayed – e.g. the learner does not observed the reward for its decision at time t until some later time, t ′ . In this work, we assume that rewards are received immediately, as a wide body of work exists for adapting on-line learning algorithms to delayed rewards [29].
Reward The learner’s objective is to maximize its cumulative accuracy, or the number of correct decisions it has made during training, as in [21]. In our model, if the learner accepts the datapoint, xt, it receives a reward of 2yt − 1, where yt is a binary random variable, while a rejection leads to a reward of 0. Concretely, in the loan scenario, this reward model corresponds to a lender that makes a unit gain for a repaid loan, incurs a unit loss for an unpaid loan and collects zero reward whenever no loan is given.
Contextual Bandit Reduction The BLP can be easily modeled as a specific type of contextual bandit problem [24], where at the beginning of every time-step t the learner receives a context xt, and has the choice of selecting one of two actions {Accept,Reject}. It is easy to see this characterization implies an immediate reduction of our problem into a two-action contextual bandit problem, where the payout of one of the actions is known by the learner (rt(Reject, xt) = 0). To distinguish the problem we study from a more general contextual bandits setting, we refer to our problem setting as the bank-loan problem (BLP).

heading: 3 Pseudo-Label Optimism
text: Overview In this section, we describe PLOT in detail, and provide theoretical guarantees for the method. Recall the discussion from Section 1 where we described the basic principle behind the PLOT Algorithm. At the beginning of each time-step t, PLOT retrains its base model by adding the candidate points with positive pseudo-labels into the existing data buffer. The learner then decides whether to accept or reject the candidate points by following the predictions from this optimistically trained model. Although the implementation details of PLOT (see Algorithm 1) are a bit more involved than this, the basic operating principle behind the algorithm remains rooted in this very simple idea.
Primarily, PLOT aims to provide similar guarantees as the existing contextual bandit literature, generalized to the function approximation regime. To do so, we rely on the following realizability assumption for the underlying neural model and the distribution of the labels:
Assumption 1 (Labels generation). We assume the labels yt ∈ {0, 1} are generated according to the following model:
yt = { 1 with probability µ(fθ?(xt)) 0 o.w.
(1)
For some function fθ? : Rd → R parameterized by θ? ∈ Θ and where µ(z) = exp(z)
1+exp(z) is the logistic link function. We denote the function class parameterized by θ ∈ Θ as FΘ = {fθ s.t. θ ∈ Θ}.
For simplicity, we discuss PLOT under the assumption that FΘ is a parametric class. Our main theoretical results of Theorem 1 hold when this parameterization is rich enough to encompass the set of all constant functions.
In PLOT the learner’s decision at time t is parameterized by parameters, θt and a function fθt and takes the form:
If fθt(xt) ≥ 0 accept
We call the function fθt the learner’s model. We denote by at ∈ {0, 1} the indicator of whether the learner has decided to accept (1) or reject (0) data point xt. We measure the performance of a given decision making procedure by its pseudo-regret3:
R(t) = t∑ `=1 max(0, 2µ(fθ?(x`))− 1)− a`(2µ(fθ?(x`))− 1)
For all t we denote the pseudo-reward received at time t as rt = at(2µ(fθ?(xt))− 1). The optimal pseudo-reward at time t equals 0 if fθ?(xt) ≤ 0 and 2µ(fθ?(xt))− 1 otherwise. Minimizing regret is a standard objective in the online learning and bandits literature (see [25]). As a consequence of Assumption 1, the optimal reward maximizing decision rule equals the true model fθ? .
In order to show theoretical guarantees for our setting we will work with the following realizability assumption.
Assumption 2 (Neural Realizability). There exists an L−Lipschitz function fθ? : Rd → R such that for all xt ∈ Rd :
yt = { 1 with probability µ(fθ?(xt)) 0 o.w.
(2)
Recall that in our setting the learner interacts with the environment in a series of time-steps t = 1, . . . T, observing points {xt}Tt=1 and labels yt only during those timesteps when at = 1. The learner also receives an expected reward of at(2µ(fθ?(xt)) − 1), a quantity for which the learner only has access to an unbiased estimator. Whenever Assumption 2 holds, a natural way of computing an estimator θ̂t of θ? is via maximum-likelihood estimation. If we denote by Dt = {(x`, y`) s.t.a` = 1 and ` ≤ t − 1} as the dataset of accepted points up to the learners decision at time t − 1, the regularized log-likelihood (or negative cross-entropy loss) can be written as,
Lλ(θ|Dt) = ∑
(x,y)∈Dt
−y log (µ(fθ(x)))− (1− y) log (1− µ(fθ(x)) + λ
2 ‖θ‖22
The Realizable Linear Setting If fθ(x) = x>θ, the BLP can be reduced to a generalized linear contextual bandit problem (see [13]) via the following reduction. At time t, the learner observes a context of the form {0,xt}. In this case, the payoff corresponding to a Reject decision can be realized by action 0 for all models in FΘ. Unfortunately, this reduction does not immediately apply to the neural realizable setting. In the neural setting, there may not exist a vector z ∈ Rd with which to model the payoff of the Reject action known a priori to satisfy fθ?(z) = 0. Stated differently, there may not exist an easy way to represent the bank loan problem as a natural instance of a two action contextual bandit problem with the payoffs fully specified by the neural function class at hand. We can get around this issue here, because in the BLP it is enough to compare the model’s prediction with the neutral probability 1/2. Although we make Assumption 2 for the purpose of analyzing and explaining our algorithms, in practice it is not necessary that this assumption holds.
Just as in the case of generalized linear contextual bandits, utilizing the model given by fθ̂t may lead to catastrophic under estimation of the true response µ(fθ?(xt)) for any query point xt. The core of PLOT is a method to avoid the emergence of self-fulfilling negative predictions. We do so using a form of implicit optimism, resulting directly from the optimization of a new loss function, which we call the optimistic pseudo-label loss.
3The prefix pseudo in the naming of the pseudo-regret is a common moniker to indicate the reward considered is a conditional expectation. It has no relation to the pseudo-label optimism of our methods.
Definition 1 (Optimistic Pseudo-Label Loss). Let D = {(x`, y`)}N`=1 be a dataset consisting of labeled datapoints x` ∈ Rd and responses y` ∈ {0, 1} and let B = {x(j)}Bj=1 ⊂ Rd be a dataset of unlabeled data points. We define the optimistic pseudo-label loss of (D,B) as,
LC(θ|D,B,W,R) = Lλ(θ|D ∪ {(x, 1) for x ∈ B}) = ∑
(x,y)∈D(R,B) −y log (µ(fθ(x)))− (1− y) log(1− µ(fθ(x)))︸ ︷︷ ︸ cross-entropy loss +
W ∑ x∈B
log(µ(fθ(x))︸ ︷︷ ︸ pseudo-label loss
+ λ‖θ‖2
2
Where W > 0 is a weighting factor, R > 0 is the ’focus’ radius and D(R,B) = {(x, y) ∈ D s.t. ∃x′ ∈ B with ‖x− x′‖ ≤ R}.
Let’s take a closer look at the optimistic pseudo-label loss. Given any pair of labeled-unlabeled datasets (D,B), optimizing for the optimistic loss LC(θ|D,B,W ) corresponds to minimizing the cross-entropy of a dataset of pairs (x, y) of the form (x, y) ∈ B or (x, 1) such that x ∈ B. In other words, the minimizer of LC(θ|D,B,W ) aims to satisfy two objectives:
1. Minimize error on the labeled data 2. Maximize the likelihood of a positive label for the unlabeled points in B.
The model θ̂C resulting from minimizing LC will therefore strive to be optimistic over B while keeping a low loss value, and consequently a high accuracy (when Assumption 2 holds) over the true labels of the points in D. We note that if D is much larger than WB (the weighted size of B), optimizing LC will favor models that are accurate over D instead of optimistic over B. Whenever |D| W |B|, the opposite is true.
PLOT Algorithm Based on these insights, we design Pseudo-Labels for Optimism (PLOT), an algorithm that utilizes the optimistic pseudo-label loss to inject the appropriate amount of optimism into the learner’s decisions: high for points that have not been seen much during training, and low for those points whose acceptance may cause a catastrophic loss increase over the points accepted by the learner so far.
Algorithm 1 Pseudo-Labels for Optimism (PLOT) Input: −greedy exploration parameter, weight schedule {Wt}∞t=1, radius R Initialize accepted dataset D1 = ∅ for t = 1, · · ·T do
1. Observe batch Bt = {x(j)t }Bj=1 and sample Qt = {qj}Bj=1 such that qj i.i.d.∼ Ber( ) 2. Build the MLE estimator, θ̂t = min
θ Lt(θ|Dt)
3. Compute the pseudo-label filtered batch B̃t = {(x(j)t , 1) s.t. fθ̂t(x (j) t ) < 0 and qj = 1}. 4. Calculate the minimizer of the empirical optimistic pseudo-label loss,
θ̂Ct = min θ LCt (θ|Dt, B̃t,Wt, R),
3. For all x(j) ∈ Bt compute acceptance decision via a(j)t =
{ 1 if fθ̂Ct (x (j) t ) ≥ 0
0 o.w.
4. Update Dt+1 ← Dt ∪ {(x(j)t , y (j) t )}j∈{1,··· ,B} s.t. a(j)t =1.
end
During the very first time-step (t = 1), PLOT accepts all the points in Bt. In subsequent time-steps PLOT makes use of a dual −greedy and MLE-greedy filtering subroutine to find a subset of the
current batch composed of those points that are both currently being predicted as rejects by the MLE estimator and have been selected by the −greedy schedule (see step 3 of PLOT). This dual filtering mechanism ensures that only a small proportion (based on the ) of the datapoints are ever considered to be included into the empirical optimistic pseudo-label loss. The MLE filtering mechanism further ensures that not all the points selected by −greedy are further investigated, but only those that are currently being rejected by the MLE model. This has the effect of preventing the pseudo-label filtered batch from growing too large.
As we have mentioned above, the relative sizes of the labeled and unlabeled batches has an effect on the degree of optimism the algorithm will inject into its predictions. As the size of the collected dataset grows, the inclusion of B̃t, has less and less effect on θ̂Ct . In the limit, once the dataset is sufficiently large and accurate information can be inferred about the true labels, the inclusion of B̃t into the pseudo-label loss has vanishing effect. The later has the beneficial effect of making false positive rate decrease with t.
The following guarantee shows that in the case of separable data satisfying Assumption 2, the PLOT Algorithm initialized with the right parameters R, {Wt}∞t=1 satisfies a logarithmic regret guarantee. Theorem 1. Let P be a distribution over data point, label pairs (x, y) satisfying
1. All x ∈ supp(P) are bounded ‖x‖ ≤ B.
2. The conditional distributions of the labels y satisfy the data generating Assumption 2 with F a class of L−Lipschitz functions containing all constant functions.
3. |fθ?(x)| ≥ τ > 0 holds for all x ∈ supp(P).
Let the marginal distribution of P over points x be PX and let’s assume the PLOT algorithm will be used in the presence of i.i.d. data such that xt ∼ PX independently for all t ∈ N. Define At = ∑t−1 `=1 1 {x` ∈ B(xt, R)} and Dt = ∑t−1 `=1 y`1 {x` ∈ B (xt, R)} where B(x, R) corresponds to the ‖ · ‖2 ball centered at x and radius R. Let δ′ ∈ (0, 1). If R = τ 2
128L ,
Wt = max
( 4 √ t ln (
6t2 ln t δ′
) , (µ(τ)2 + 1 4 )At−Dt
3 4− µ(τ) 2
) and = 1, the PLOT Algorithm with batch size 1
satisfies for all t ∈ N simultaneously, R(t) ≤ Õ ( 1
τpX ln
( 1
δ′ )) With probability at least 1− δ′, where pX is a parameter that only depends on the geometry of PX and Õ hides logarithmic factors in τ and pX .
The proof can be found in Appendix ??. Although the guarantees of Theorem 1 require knowledge of τ , in practice this requirement can easily be alleviated by using any of a variety of Model Selection approaches such as in [34, 11, 1, 27, 33], at the price of a slightly worse regret rate. In the following section we conduct extensive empirical studies of PLOT and demonstrate competitive finite time regret on a variety of public classification datasets.

heading: 4 Experimental Results
text: Experiment Design and Methods We evaluate the performance of PLOT4 on three binary classification problems adapted to the BLP setting. In time-step t, the algorithm observes context xt ∈ Rd, and classifies the point, a.k.a accepts/rejects the point. If the point is accepted, a reward of one is given if that point is from the target class, and minus one otherwise. If the point is rejected, the reward is zero. We focus on two datasets from the UCI Collection [12], the Adult dataset and the Bank dataset. Additionally we make use of MNIST [26] (d=784). The Adult dataset is defined as a binary classification problem, where the positive class has income > $50k. The Bank dataset is also binary, with the positive class as a successful marketing conversion. On MNIST, we convert the multi-class problem to binary classification by taking the positive class to be images of the digit 5,
4Google Colab: shorturl.at/pzDY7
and treating all other images as negatives. Our main metric of interest is regret, measured against a baseline model trained on the entire dataset. The baseline model is used instead of the true label, as many methods cannot achieve oracle accuracy on real-world problems even with access to the entire dataset.
We focus on comparing our method to other neural algorithms, as prior papers [38], [23], [47] generally find neural models to have the best performance on these datasets. In particular, we focus on NeuralUCB[47] as a strong benchmark method. We perform a grid search over a few values of the hyperparameter of NeuralUCB, considering {0.1, 1, 4, 10} and report results from the best value. We also consider greedy and -greedy methods. For -greedy, we follow [23], and give the method an unfair advantage, i.e. we use a decayed schedule, dropping to 0.1% exploration by T=2000. Otherwise, the performance is too poor to plot.
In our experiments, we set the PLOT weight parameter to 1, equivalent to simply adding the pseudolabel point to the dataset. We set the PLOT radius parameter to∞, thus including all prior observed points in the training dataset. Although our regret guarantees require problem-dependent settings of these two parameters, PLOT achieves strong performance with these simple and intuitive settings, without sweeping.
For computational efficiency, we run our method on batches of data, with batch size n = 32. We average results over 5 runs, running for a horizon of t = 2000 time-steps. Our dataset consists of the points accepted by the algorithm, for which we have the true labels. We report results for a two-layer, 40-node, fully-connected neural network. At each timestep, we train this neural network on the above data, for a fixed number of steps. Then, a second neural network is cloned from those weights. A new dataset with pseudo-label data and historical data is constructed, and the second neural network is trained on that dataset for the same number of steps. This allows us to keep a continuously trained model which only sees true labels. The pseudo-label model only ever sees one batch of pseudo-labels. Each experiment runs on a single Nvidia Pascal GPU, and replicated experiments, distinct datasets, and methods can be run in parallel, depending on GPU availability.
Analysis of Results In the top row of Figure 1, we provide cumulative regret plots for the above datasets and methods. Our method’s cumulative regret is consistently competitive with other methods, and outperforms on MNIST. In addition, the variance of our method is much lower than that of NeuralUCB and Greedy, showing very consistent performance across the five experiments.
The bottom row of Figure 1 provides a breakdown of the decisions made by our model. As described in Section 3, on average the pseudo-label model only acts on -percent of points classified as negative by the base model. We provide the cumulative probability of acceptance of true positive and true negative points acted on by the pseudo-label model. As the base model improves, the pseudo-label model receives fewer false positives, and becomes more confident in supporting rejections from the base model. To differentiate this decaying process from the pseudo-label learning, we highlight the significant gap between the probability of accepting positives and the probability of accepting negatives in our method. This shows that the PLOT method is not simply performing a decayedstrategy, but rather learning for which datapoints to inject optimism into the base classifier.
PLOT in action. We illustrate the workings of the PLOT algorithm by testing it on a simple XOR dataset. In Figure 2 we illustrate the evolution of the model’s decision boundary in the presence of pseudo-label optimism. On the top left panel of Figure 2 we plot 300 samples from the XOR dataset. There are four clusters in the XOR dataset. Each of these is produced by sampling a multivariate normal with isotropic covariance with a diagonal value of 0.5. The cluster centers are set at (0, 5), (0, 0), (5,−2), and (5, 5). All points sampled from the red clusters are classified as 0 and all points sampled from the black clusters are classified as 1. Although there are no overlaps in this picture, there is a non-zero probability that a black point may be sampled from deep inside a black region and vice versa.

heading: 5 Conclusion
text: We propose PLOT, a novel algorithm that provides end-to-end optimism for the bank loan problem with neural networks. Rather than post-hoc optimism separate from the neural net training, optimism is directly incorporated into the neural net loss function through the addition of optimistic pseudo-
labels. We provide regret guarantees for PLOT, and demonstrate its performance on real-world problems, where its performance illustrates the value of end-to-end optimism.
Our current analysis and deployment of PLOT is focused on the bank loan problem, with binary actions, where pseudo-label semantics are most clear. Due to the deep connections with active learning and binary contextual bandits, extending this work to larger action spaces is an interesting future direction.
Although the BLP is naturally modeled with delayed feedback, PLOT assumes that rewards are received immediately, as a wide body of work exists for adapting on-line learning algorithms to delayed rewards [29]. Contexts (unlabeled batches of query points) do not have to be IID – their distributions, P(x), may change adversarially. Handling this type of shift is a key component of PLOT’s approach. Optimism is essential to avoiding feedback loops in online learning algorithms, with significant implications for the fairness literature. We presented regret analyses here, which we hope can lay the foundation for future work on the analysis of optimism in the fairness literature.

heading: 6 Statement of Broader Impact
text: Explicitly incorporating optimism into neural representation learning is key to ensuring optimal exploration in the bank loan problem. Other methods for exploration run the risk of feature blindness, where a neural network loses its uncertainty over certain features. When a representation learning method falls victim to this, additional optimism is insufficient to ensure exploration. This has ramifications for fairness and safe decision making. We believe that explicit optimism is a key step forward for safe and fair decision making.
However, we do want to provide caution around our method’s limitations. Our regret guarantees and empirical results assume I.I.D data, and may not prevent representation collapse in non-stationary and adversarial settings. Additionally, although our empirical results show strong performance in the non-separable setting, our regret guarantees only hold uniformly in the separable setting.

Review summaries:
This paper first motivates the "bank loan problem", which is a scenario where the learner only observes whether a customer will repay a loan if the loan is issued to begin with. The paper moves on to discussions of this problem and introduces contextual linear bandit formulations. This is extended to the case where the model is a deep neural network, and a Theorem shows theoretical guarantees under the case where data is separable. Experiments show improvement over baseline methods, including the recent NeuralUCB method.

The paper studies class of problems, called bank loan problem (BLP), where the learner only observes whether a customer will repay a loan if the loan is issued to begin with. To solve this problem, the paper proposes a simple and efficient algorithm, Pseudo-Labels for Optimism (PLOT), which adds an optimistic label to a subset of data points rejected by the model and trains the model on all the data seen so far including the optimistically added points. Empirical evidence shows that PLOT achieves competitive performance in comparison to known storng baselines such as NeuralUCB.

This paper proposes a new approach to improve the performance of non-linear predictors (DNN models) on binary labels when the observations are endogenously selected. The issue arising in traditional setups is that the algorithm will only select observations with high positive outcome (reward). This may lead to sub-optimal and unfair models generating a large proportion of false negatives. The solution proposed in this paper is to add optimistic labels (with positive rewards) to a subset of points that the model would normally reject. Doing so optimistically bias the model, and stimulate the exploration of the more uncertain regions. The suggested algorithm and paper focus is on online learning methods. Several experiments highlight the competitiveness of this approach compared to similar ones.

Authors propose neural pseudo-label optimism for solving the bank loan problem. This is an interesting setting and I judge the work in the paper (theory & experiments) to be mostly correct. I consider this paper to be sufficiently novel, although there are certainly a large number of papers on the bank loan problem. I am not an expert on the bank loan problem in particular, so I hope another review can provide more clarity as to this paper’s novelty. I am tentatively voting for a rating of 7, but I would like the authors to address some of my concerns below.