Approximation to Object Conditional Validity with Inductive Conformal Predictors

Conformal predictors are machine learning algorithms that output prediction sets that have a guarantee of marginal validity for finite samples with minimal distributional assumptions. This is a property that makes conformal predictors useful for machine learning tasks where we require reliable predictions. It would also be desirable to achieve conditional validity in the same setting, in the sense that validity of the prediction intervals remains valid regardless of conditioning on any particular property of the object of the prediction. Unfortunately, it has been shown that such conditional validity is impossible to guarantee for non-trivial prediction problems for finite samples. In this article, instead of trying to achieve a strong conditional validity result, the weaker goal of achieving an approximation to conditional validity is considered. A new algorithm is introduced to do this by iteratively adjusting a conformity measure to deviations from object conditional validity measured in the training data. Along with some theoretical results, experimental results are provided for three data sets that demonstrate (1) in real world machine learning tasks, lack of conditional validity is a measurable problem and (2) that the proposed algorithm is effective at alleviating this problem.

Introduction
In some predictive analytic tasks it is useful to provide a prediction set of possible outcomes rather than a single point prediction. For example, a doctor diagnosing a patient's symptoms may find it more valuable if an automated decision support system suggested two or more possible causes instead of just one, if there is some ambiguity in diagnosis [Nouretdinov et al., 2014]. Or, given the uncertainty in property sale prices, it may be better if an automated valuation model provides a range of possible predicted sale prices, rather than a single point estimate. Indeed, for automated valuation, the delivery of a property price range is the norm; see e.g. [Bellotti, 2017] or www.zoopla.co.uk.
The conformal predictor (CP) is a machine learning algorithm that is able to generate prediction sets with a guarantee that its prediction sets are correct, i.e. the true label 1 will be a member of the prediction set, at a preset confidence level [Vovk et al., 2005]. We therefore say that the CP is a valid predictor. Other statistical methods based on frequentist and Bayesian approaches exist that promise the same guarantee, but only with some specific distributional assumptions. When those assumptions do not hold true, validity is no longer guaranteed. In contrast, CPs require only the assumption of exchangeability of data. Hence the CP is referred to as distribution-free [Lei and Wasserman, 2014]. Central to the CP is the use of a conformity measure (CM) that, given a new example, provides a measure of how typical it is of the population. Often the CM is based on some underlying machine learning algorithm, although this is not essential. The CP has been applied successfully in many problem domains including medical and financial, anomaly detection and network traffic applications, amongst others; see e.g. Balasubramanian et al. [2014].
Since the accuracy of CP is essentially fixed, the optimization task is to maximize the efficiency of the prediction sets which is some measure of the information given by the prediction set. There are multiple alternative measures of predictive efficiency, or conversely, predictive inefficiency [Vovk et al., 2016]. For example, Colombo and Vovk [2020] optimize on the object fuzziness of the predictions. Another approach is to build CPs that minimize the mean width of prediction intervals for regression [Bellotti, 2020] or mean prediction set size for classification. This is also the approach used for Prediction Interval Neural Networks [Khosravi et al., 2011, Pearce et al., 2018. For clarification, Examples 1 and 2 give two cases of what is meant by predictive efficiency.
The CP guarantees marginal validity: that is, across the whole population of observations, the accuracy of the CP will meet the confidence level preset by the user. However, even with marginal validity, there may be some sub-segments of the population for which accuracy is greater or less than the confidence level. Here are two examples demonstrating why this may be a problem.
• Medical example. If diagnosing a disease, we may have a CP that gives 95% accuracy guaranteed across all people. However, for a particular racial minority group, it gives only 85% accuracy, whilst for the majority racial group it gives 96% accuracy. This is clearly a problem for two reasons: (1) it makes clinical decisions less precise, especially for hospitals operating with a higher racial minority demographic, (2) it leads to medical decision support that is discriminatory.
• Business example. Suppose we have an automated valuation model (AVM) that gives good property price prediction intervals at 90% confidence levels across UK. However, for the particular county of Devon its accuracy is only 75%. This could adversely affect the business of any real estate company or mortgage provider operating in Devon who use the AVM. Worst still, the weakness of the AVM in their location may not even be known and so they will be operating under the misconception that the AVM is guaranteed to be 90% accurate: it is in general, but not for them.
For this reason, conditional validity has been identified as an important criterion, alongside marginal validity and predictive efficiency, for CP and indeed any algorithm generating prediction sets. That is, ideally, the validity should hold conditional on any underlying segmentation of the population. There are alternative forms of conditional validity depending on the type of information that accuracy is conditioned on. Vovk [2013] identifies (1) label conditional validity for conditioning on the label, (2) object conditional validity if conditioning on the features of each example (as opposed to the label) and (3) training conditional validity for conditioning on a property of the training set. We can also consider combinations of these types, so if we are interested in object and label conditional validity together, we call this example conditional validity. Lei and Wasserman [2014] construct a CP which has asymptotic object conditional validity and asymptotic efficiency in the number of examples used in development (more precisely: in the calibration set), basing their CM on a conditional kernel density estimator. However, for practical purposes and in this article we are interested in finite sample results. McCullagh et al. [2009] present provably conditionally valid prediction intervals, for the finite sample case, based specifically on linear regression, although other parametric models could be used, assuming some known probability distribution. However, it has been shown that it is impossible to meet the criterion of conditional validity in the finite sample case for non-trivial problems in the general case [Vovk, 2013, Lei andWasserman, 2014]. Both papers suggest label-conditioned CPs for classification as a way to address this problem. More generally, a conditional CP can be used that allows the user to specify a taxonomy of data into finite categories and then the CP is valid within those pre-defined categories [Vovk, 2014]. However, these approaches are problematic since (1) they limit the conditional validity to just some finite pre-defined categories and do not apply generally to any taxonomy, and (2) the effectiveness of the CP is reduced with the more categories included in the taxonomy, since the conditional CP essentially relies on a separate CP for each segment of data, limiting these approaches for practical use with large taxonomies.
These practical limitations with conditional validity have led Barber et al.
[2020] to proprose relaxing the requirement for conditional validity and to explore using an approximation to conditional validity. They set up a framework called distributionfree approximate conditional coverage meaning that conditional validity should be true for at least some pre-defined proportion of the population, which is similar to the PAC-type conditional validity given by Vovk [2014]. However, in the general case, they find that it is also impossible to meet this broad target. They make further progress proposing restricted conditional coverage to provide local conditional validity in the neighbourhood (ball) around some point. This is a promising approach and they show that CP satisfies this condition, but only for the case of CP for regression with the standard CM. Additionally, they identify computational difficulties with this method that require further research. The development of the normalized CM for regression [Papadopoulos et al., 2002] is an approach which can be seen as addressing this problem since the normalization factor allows more difficult prediction cases to be given wider prediction intervals, hence increasing their probability of being correct, and vice versa for easier prediction cases. However, it is a heuristic approach since it does not directly optimize for approximation to conditional validity and there has been little investigation of its effectiveness for approximation to conditional validity.
It may be supposed that pursuing the goal of maximizing predictive efficiency may align with conditional validity, in some sense. However, Example 3 gives a simple case demonstrating predictive efficiency is not consistent with conditional validity. In this paper, we focus on object conditional validity. The medical and business examples given above are both examples of this. We demonstrate that lack of object conditional validity is a genuine problem for CP through experiments with three data sets and alternative CPs; and, secondly, propose a new iterative feedbackadjusted conformity measure (IFACM) algorithm that can be used as part of an inductive conformal predictor (ICP) to achieve approximation to object conditional validity (AOCV), although in a different sense to Barber et al. [2020]. We provide some theory and experimental results. The methodology is based on ICP since ICP is a practical version of CP appropriate for batch machine learning. The proposed IFACM algorithm works from the proposition that (1) the AOCV of an ICP can be estimated using a meta-model, and (2) this meta-model can then be used to adjust the CM thus forming a new ICP which is able to achieve better AOCV on the same problem. This process can be repeated until no improvement in AOCV can be acheived. Finally, this algorithm will output a CM formed as layers of adjustments to some base CM. The algorithm is similar in approach to that of boosting algorithms that are used to reduce errors on point predictions through layers of simple predictive models [Freund and Schapire, 1999].
The remainder of this article is organized as follows. Section 2 introduces CP and the proposed IFACM algorithm, Section 3 presents some experimental results for both regression and classification, demonstrating the effectiveness of the proposed algorithm to achieve AOCV and conclusions are given in Section 4. The Appendix provides supporting theoretical results. Abbreviations used in this article are listed in Table 1  Example 1. Suppose a disease subtype needs to be diagnosed and it must be one of A, B or C. If the predictor outputs the prediction set {A, B, C} then it provides no new information at all, since the prediction set just states that the subtype is any of those available. The most informative prediction is the prediction singleton set, say {B}, since this isolates one single case. The prediction set {A, B} offers some information (by excluding C) but is not as informative as the singleton set. Hence this example suggests that cardinality of the prediction set is a good measure of predictive inefficiency.
Example 2. Suppose property price is predicted and a prediction interval [230,534] (in '000 GBP) is given. Then this range is rather broad and may not be particularly useful to a real estate agent. If the prediction algorithm is improved to give prediction interval [240,350] then this may prove an informatve and useful prediction. Hence, this example suggests that width of prediction interval would be a good measure of predictive inefficiency. For these particular examples, the predictive inefficiency would be 304 and 110 respectively.
Example 3. A simple example is constructed to demonstrate that finding the most efficient prediction intervals, on average, whilst maintaining marginal validity, leads to conditionally invalid prediction intervals.
By the law of total probability, Measure inefficiency as width of the prediction interval, then minimizing mean inefficiency is minimizing With the marginal validity constraint above, this is a simple linear programming problem with the solution, noticing that since ε < 1 2 , b > 0 (an alternative is to use the square of prediction interval width as an inefficiency measure, in which case 1 2 a 2 + 1 2 b 2 is minimized; however, this leads to the same solution). This then leads to the two conditional probabilities of accuracy: which both deviate from the confidence level 1 − ε, hence the solution does not exhibit conditional validity.
It is possible to enforce object conditional validity for this simple example by setting a = 1 − ε and b = 2(1 − ε) so that However, mean inefficiency then increases from 3 2 − 2ε to 3 2 (1 − ε), a difference of 1 2 ε more than optimal inefficiency. Therefore enforcing object conditional validity leads to a reduction in predictive efficiency.

Methodology
We first introduce ICP and marginal validity, then discuss AOCV before introducing the IFACM algorithm. Finally we show that IFACM for regression is consistent with the normalized CM.

Inductive Conformal Predictors
We set up the ICP framework following Vovk et al. [2005].
• Let z = (x, y) denote examples from the same unknown distribution P such that x is a vector of m predictor variables x ∈ R m and label y ∈ Y for some set of labels Y.
• Let z 1 , · · · , z l be a particular sequence of examples z j = (x j , y j ) from P .
• Let 1 to k index the training data set and k + 1 to l index the calibration set, for 1 < k < l.
• A conformity measure (CM) is any computable function for all permutations π of 1, · · · , k. For convenience, we will sometimes use A(x, y) to denote A(z).
• Let ε be a preset significance level, so 1−ε is the confidence level for predictions.
We typically consider a CM having the form A(z) = A p (θ, z) for some parameters θ = M (z 1 , · · · , z k ) where M is intended to be a model structure within which θ are estimated based on data z 1 , · · · , z k . For example, for regression, M could be ordinary least squares (OLS) linear regression and θ, the vector of coefficients in the OLS linear regression model; or M could be an artificial neural network with θ the vector of weights in the network. The ICP is defined as the prediction algorithm that gives the prediction set at significance level ε for a new example x, based on the calibration set of examples k + 1 to l as where I is the usual indicator function. This prediction set is dependent on the CM used so this is made explicit on the left-hand side of the expression. Assuming only that the calibration data set, z k+1 , · · · , z l , and any new test or operational data sets are exchangeable, ICP predictions on the new data are marginally valid: (2) for each new example (x, y) 2 . When the label set Y is finite, this is ICP for classification. When Y = R, this is ICP for regression. For these two cases, we can consider two particular CMs that are common in the literature.

Scoring CM
A scoring function f : R m × Y → R for which a higher output of f (x, y) means that label y is (in some sense) more likely to be associated with example x, then f itself can be used directly as a CM. An example of this is multinomial logistic regression for classification which estimates coefficient vectors β y for each possible label y ∈ Y such that f (x, y) = β y · x is the logodds of y conditional on x. We will use the multinomial logistic regression scoring function in the later experimental section.
Normalized CM In the case of regression, a typical choice is the normalized nonconformity measure: whereŷ is a point estimate based on a regression model of y andσ > 0 is some estimate of uncertainty in the prediction given by the model [Papadopoulos et al., 2002]. Both can be computed from models estimated from training data, z 1 , · · · , z k . For later experiments in this article, OLS linear regression of y is used for the numerator and a OLS linear regression of the log of absolute residual is used for σ following Papadopoulos et al. [2002]. For consistency, we use CM for this study and a normalized CM can be constructed as the reciprocal of the normalized nonconformity measure A N (x, y) = 1/N (x, y).
For the normalized nonconformity measure thus forming a prediction interval, where q is the ε-quantile of the empirical distribution of CM values within the calibration set. In the special case when σ = 1, this gives the standard CM. As can be seen from (4), the standard CM always gives the same fixed width 2q for prediction intervals. The introduction of the normalizing denominator allows for variation in the prediction interval width and hence form a CP that has varied prediction interval widths according to the difficulty of the observation, with observations that are more difficult to predict having wider prediction intervals.

Approximation to Object Conditional Validity
As discussed earlier, it would be valuable to achieve object conditional validity given by for all x ∈ R m , but, in the nontrivial case, this is impossible to achieve for CPs as shown byVovk [2013] and Lei and Wasserman [2014]. Instead we consider relaxing the constraint and allow for AOCV given broadly by This requirement can be made more precise by expressing it as minimizing the square difference across the population, This approach to AOCV is quite different to Barber et al. [2020] who, instead, consider proportions of the population that are exactly conditionally valid as an approximation method. After conformal predictions are made on a data set indexed by some index set S, (5) is estimated as is some probability estimator. The probability estimator can be logistic regression, k-nearest neighbours (k-NN) or any other probabilistic model taking training data indicates whether the prediction set for example j is correct. Therefore, this measure can be used to quantify AOCV. We take the square root of this estimate, so that the measure is on the same scale as the conditional probability. Hence the root mean square error gives deviation from conditional validity (DCV), If an ICP is conditionally valid then DCV(A) ≈ 0. The closer it is to zero, the better the AOCV exhibited by the ICP. Essentially p(z; A) ≈ 1 − ε indicating an uninformative model. For example, using logistic regression for p, the coefficient estimates will be close to zero and statistically insignificant. On the other hand, a low value of DCV does not guarantee conditional validity, since it only reflects the model structure that is used to construct the probability estimate, such as logistic regression, and not all possible conditionalities in the data. However, it will be a good indicator of AOCV for practical purposes.

Iterative Feedback-adjusted Conformity Measure
Consider constructing CMs that seek to minimize DCV(A). Our proposal is to extend an existing base CM A which may have a high DCV with another as follows: where γ > 0 is a control parameter, U is an update function based on the discrepency between estimated probability given A and confidence level, with the properties, where the underlying estimator p is exchangeable, i.e. the estimates are invariant to the order of the training examples. This ensures that A * γ is also a CM. This exchangeability condition is true of most probabilistic estimators and, in particular, is true of logistic regression and k-NN where the order of training examples is irrelevant. Hence, if the training data for p is independent of calibration and test data, then the use of A * γ in an ICP guarantees marginal validity (2).
The inituition for the update function is that if the conditional probability of being correct is too low, then we increase the CM so that the correct label has more chance of being in the prediction interval (1), hence increasing the conditional probability of being correct if ICP is rerun with the updated CM, and vice versa, for conditional probabilities that are too high, the CM value is lowered following the update, thus making it less likely that the prediction is correct.
A specific update function considered in this study is where δ ≥ 0 is a sensitivity parameter. Notice that U * is not dependent on y but this is not a problem, since A is expected to provide discrimatory power for the ICP, whilst U * just provides an adjustment to lead the ICP to achieve better AOCV. Ideally we would like to prove that adjusting by U * will improve AOCV in some way: perhaps showing that DCV is reduced. However, this seems difficult to achieve, at least in the general case, and remains an area for further research. However, it is possible to prove that applying U * adjustment to the CM does improve the average log-odds of being correct for those observations whose outcome (i.e. c j ) is switched by the adjustment, so that it is closer to the target confidence level, in the case when logistic regression is used as the probability estimator p. Technical details are provided in Appendix A.
The updated CM A * γ is optimized with respect to γ and δ using the training data set with the goal to minimize the DCV measure. There is no gradient that can be used for optimization but with only two parameters to minimize across, Nelder-Mead optimization [Nelder and Mead, 1965] is adequate for this task. Since both parameters are greater or equal to zero, the optimization is performed over the logarithm of the parameters.
The U * update function is rather simplistic and one application of an update may provide just a small improvement in DCV. However, since the update A * is itself a CM, the application of the update function can be applied iteratively, minimizing DCV at each iteration, until it cannot be minimized any further. Representing the CM recursively: for parameters γ i > 0 and δ i ≥ 0 that are computed at each iteration to minimize DCV. Importantly, the probability estimator (6) is re-estimated at each iteration based on the ICP with the current version of A * [i] . Then the output after n u iterations is the IFACM expressed as the weighted sum, This use of iterative modifications to the CM based on feedback from previous stages of the ICP performance mirrors the method of boosting that is used to reduce errors iteratively by giving greater weight to examples with errors from previous iterations in each model build at the next iteration. We would expect that the process of adjusting the CM by iterative updates will lead to reduced DCV, but on the other hand, that there will be a trade-off in an increase in predictive inefficiency. Hence, to mitigate against this the optimization task is modified to minimize at each iteration i, where I is an inefficiency measure for predictions made using the CM on index set S and C ≥ 0 is a control hyperparameter. There are several alternative measures of prediction inefficiency [Vovk et al., 2016]. In this study, the mean size of prediction sets is used, For classification, the size is the cardinality of the prediction set. For regression, using normalized CM, the size is the width of the prediction interval.
The method is introduced with the abstract set S. However, in practice, this would typically be the training data; i.e. S = {1, · · · , k}, in order to conserve data. The consequence of this is that the ICP constructed at each iteration of the algorithm is not marginally valid since the training, calibration and independent test sets all coincide, leading to overfitting. However, ultimately this is not a problem since the IFACM that is computed is subsequently an input to a proper ICP that does have an independent calibration set and independent testing (or operational) data. Algorithms 1 and 2 show how to compute the IFACM that can then be used within an external ICP with an independent calibration data set.
Algorithm 1: Run ICP on training data to measure DCV input : Train = training data set, CL = confidence level, A = conformity measure. Compute prediction intervals PI for all observations in Train using ICP with A, CL and Train as the calibration data set; Construct a probabilitic model M of the correctness of PI on Train ; Compute DCV of M predicting on Train, relative to CL ; W ← mean width of PI, using (9) ; output: DCV, W

IFACM and Normalized CM
The CM A * * is consistent with the normalized CM for regression. To see this, first observe that applying a monotonically increasing transform to a CM does not change the behaviour of the ICP since it is the rank ordering of CM that matters, as can be seen in (1). Therefore, taking base A(x, y) = log σ − log |y −ŷ| and applying the exponential function to (7) gives Algorithm 2: Iterative feedback-adjusted conformity measure (IFACM) input : Train = training data set, CL = confidence level, C = control parameter in equation (8), Run Algorithm 1 multiple times with input: Train, CL, A + γ i U * (.; A, δ i ) to minimize DCV + C(W − W 0 )I(W > W 0 ) with respect to γ i , δ i using the Nelder-Mead algorithm (i.e. minimize (8) with respect to γ i , δ i ) ; DCV 2 ← DCV from the minimization step above ; if DCV 2 < DCV 1 then Since the exponential function is monotonically increasing, this CM will give the same ICP as (7), except in the transformed version it can be seen that this is the normalized CM with an extra product update. Indeed, the update functions can be interpreted as a further normalizing factor in the CM. Therefore from (4), the prediction interval yielded by this CM for regression is whereσ =σ exp nu i=1 γ i U * (x, y; A, δ i ) .

Experimental settings and results
Experiments were conducted with three data sets listed in Table 2. Data set "covtype" has outcome identifying tree cover type for different forest locations. It is used in this study since it is a large multi-class classification problem. Data set "GPU" provides GPU performance data for different GPU settings, outcome is average performance time and it is a large regression data set [Nugteren and Codreanu, 2012] . Data set "KC" (King's County) contains US housing data and the outcome variable is property sale price. It is a smaller regression problem but is interesting for this study since the normalized CM gives improved performance over the standard CM, which was not the case with the GPU regression problem. Both "covtype" and  Parameter settings are as follows:- • Confidence level. For all experiments, confidence level is set to make the problem sufficiently hard that predictive efficiency becomes a challenge. For "covtype" this is 0.95 and for "GPU" and "KC" it is 0.9. Additionally a confidence level of 0.99 is also used for "GPU" to explore the consequences of high confidence levels. • Base CM. For classification, the multinomial scoring CM is used as base CM, whereas normalized CM is used for the regression problems. Additionally standard CM for regression is used for "KC" to explore if normalized CM improves on standard CM in terms of AOCV. Both use a base OLS linear regression model for point estimates ofŷ and normalized CM also uses OLS linear regression for estimates of logσ for (3). • Probability estimator. Logistic regression is used as the probability estimator (6). • C: penalty hyperparameter in (8). For "covtype", it was possible to achieve good results with C = 0. However, for the other data sets, C = 0 leads to huge predictive inefficiency, hence a value of C = 0.5 is used instead. For contrast, C = 5 is also used. • Nelder-Mead optimization. Low starting values log γ i = −5, log δ i = −5 were used when minimizing (8).
Results are shown in Table 3. The main points that we find are as follows.
• For all experiments, the IFACM algorithm successfully reduces DCV on both the training and test data sets, whilst maintaining marginal validity (i.e. Acc. ≈ CL). • As expected, the reduction in DCV comes at the cost of increase in predictive inefficiency and this is controlled by the hyperparameter C. However, the impact of this trade-off is different for each data set. For "covtype", inefficiency increases from 1.78 to 1.84 for the best improvement in DCV (when C = 0, lines 3-4), whereas taking C = 5 will yield better inefficiency (1.80) but the DCV more than doubles, so the impact of the trade-off between DCV and inefficiency is high for this data set. However, for "GPU", a low DCV is measured with minimal increase in inefficiency when C is low (lines 11-12). Surprisingly, when a high confidence level is used, IFACM yields lower inefficiency even with low DCV (lines 15-18). Whether this is a general result requires further investigation, but at the very least it demonstrates that for "GPU", the impact of applying IFACM on inefficiency is minimal.
• In many cases, DCV is much lower on the training data set compared to the test set. This is especially the case when low values of C are used (compare line 11 to 12 and 25 to 26). This suggests that in some situations, the IFACM algorithm gives rise to a large degree of overfit for the goal of minimizing DCV. For these data sets, it does not give rise to a significant problem with performance on the test data; however, it is worth some further investigation.
• Lines 19-22 demonstrate that for the "KC" regression problem, using NCM gives lower predictive inefficiency than the standard CM which confirms what we expect from previous work (e.g. [Papadopoulos et al., 2002]), but also interestingly the normalized CM is able to reduce DCV on training and test data (lines 21-22), which is expected by construction of the normalized CM. Nevertheless, we see that applying IFACM with the normalized CM as base CM allows for even further reduction in DCV. Using C = 5, IFACM is able to achieve this with only a small increase in inefficiency (lines 29-30). Interestingly, applying IFACM on the standard CM gives improvement over standard CM, but is not as good as IFACM applied to normalized CM in terms of either inefficiency or DCV measures (compare lines 27-28 to 29-30). This is important since it shows that IFACM cannot simply replace a good base CM (i.e. the normalized CM) but is a supplement to an existing base CM, for the purpose of achieving AOCV.
We can look in further detail at the behaviour of the IFACM algorithm.
• Figure 1 shows the coefficient estimates for each of the variables in "GPU" using the logistic regression probability estimator p in (6), before and after IFACM is applied, corresponding to lines 10 and 12 of Table 3 respectively. Since data has been standardized, the magnitude of the coefficients are comparable. The left graph shows the result on training data: in this case, the reduction in magnitude of coefficients is large, leading to an uninformative model after IFACM (i.e. coefficients ≈ 0) 3 . The right graph shows coefficients on test data: overall, there is a reduction in magnitude, but it is not as pronounced as with training data and some coefficients actually become larger in magnitude. This demonstrates there is overfitting with this algorithm, i.e. it does not perform so well on test data as training, in terms of AOCV, corroborating the results for DCV given in Table 3.
• Table 4 shows the sequence of values of parameters γ i and δ i estimated in several experiments. They show that the number of iterations of the IFACM algorithm is not large, with maximum 5 in our experiments. Also, the number of iterations goes down as C increases, showing that greater control of inefficiency means less precision with the feedback adjustment. The sequence of values of γ i decreases with each iteration, as the magnitude of the adjustment at each iteration is reduced. Finally, however, we notice no particular pattern with the sequences of δ i values. Figure 1: Change in coefficient estimates in probability estimator p before (dark grey) and after (light grey) applying the IFACM algorithm on "GPU" training data (left) and test data (right).
• Although DCV reported in Table 3 measures average deviation from conditional validity across the whole data set, to convince ourselves that the method is effective, it is also valuable to show accuracy for different sub-segments of the data. Therefore, as an illustration, Table 5 shows this for several segments in the test data sets. These segments are chosen as deviating greatly from the confidence level when the Base ICP is used. The results show that for each of these segments, using IFACM makes a considerable difference, giving accuracies much closer to the target confidence level, within each segment, as required for AOCV. So, e.g. in "covtype", for V43 we can see a bias in accuracy with better performance for V43=1 (accuracy=0.973). However, once IFACM is used, this bias is reduced and accuracy for V43=1 becomes closer to the target confidence level 0.95 (accuracy=0.955). Although improvements in AOCV are observed within all segments, some segments receive greater improvement than others. For example, in "GPU", the improved AOCV is much better for KWG than for the segment MWG=64.
• The code was written in R and was run on a PC with a processor running at 2.1 GHz with 16GB RAM. The Nelder-Mead optimizer was set to take no more than 100 steps each iteration of the IFACM algorithm. The computation times for training in Algorithm 2 on "covtype", "GPU" and "KC" data sets (corresponding to lines 3, 11 and 25 of Table 3, respectively) were 6125, 225 and 51 seconds respectively. The much longer running time for "covtype" was a consequence of a larger training data set size and larger number of iterations, n u .

Conclusion
The IFACM algorithm is introduced as a mechanism to iteratively update a base CM in order to adjust the conditional probability of a predictive interval being correct so that it is close to the target confidence level across the population and hence achieve AOCV. The experimental results provide good evidence that IFACM algorithm works well at this task, whilst maintaining marginal validity when the IFACM is used in the ICP. There is a cost in terms of increased predictive inefficiency, but the impact of that cost differs by data set and for all the data sets used in this study, the cost is not too onerous with the correct choice of hyperparameter C.
The results show that deviation from object conditional validity can be high and hence we recommend that developers using ICP should control for all three objectives: • Marginal validity: guaranteed by (2) for any ICP with independent and identically distributed training, calibration and test (or operational) data; • Predictive inefficiency: needs to be minimized; e.g. minimizing mean prediction interval width (9) for regression; • Deviation from conditional validity (DCV): needs to be minimized; this is the main objective of this study.
This article introduces the problem and proposes the novel IFACM algorithm with some initial experimental results that demonstrate that the algorithm is effective. There remain several avenues for further research.
1. Further benchmark studies on different data sets, different underlying machine learning algorithms for the base CM and alternative U update functions. 2. Exploring the effect of data set size and model complexity for the overfitting problem identified in the experimental results. 3. Testing alternative probability estimators p, such as nonparametric k-nearest neighbours, or estimators that could alleviate the overfitting problem, such as those using regularization. 4. The theoretical results given in the Appendix show that the behaviour of the update function is appropriate; however they are not complete and there is room for further theoretical work to help prove that improved AOCV can be achieved using IFACM. 5. As recommended above, CP should be built taking into account minimizing both predictive inefficiency and DCV. Colombo and Vovk [2020] and Bellotti [2020] propose methods specifically for minimizing predictive inefficiency, whilst this article focusses just on DCV. It would be interesting to develop a method that integrates both approaches. This is not straightforward since the optimization methods are quite different in each case. 6. This study only considers object conditional validity. It would be interesting to extend to other forms of conditional validity, such as label or example conditional validity.

A Theoretical Results
Some theoretical results for the update function U * with the logistic regression probability estimator p are given in Theorems 1 and 2 below. More generally, these results apply to any estimator using a binomial likelihood function (e.g. probit regression). Then, g(β) ≥ g(α).
Definition 1. The binomial log-likelihood for data set E of observations (x, c) ∈ E with c ∈ {0, 1}, for some parametric model with coefficients β, is Definition 2. The sample mean of conditional log-odds of c ∈ {0, 1} over data set , · · · , n}} for some n ≥ 1. Suppose S ⊆ {1, · · · , n}. Let Then since D T has the same observations as D S but only differs in outcome, Notice that the outer min is needed to deal with the case when two indexes both give the same minimum for the inner arg min.
• Base step, for γ < γ 1 : q(γ) remains the same value, i.e. i = q(γ) = q(0), so t(0) = A(z i ) and • Inductive step (1), for γ = γ k for some k ≥ 1: • Inductive step (2), for γ > γ k for some k ≥ 1 and γ < γ k+1 if k < K: There is no change in q(γ) from γ k to γ, hence i = q(γ) = q(γ k ). Therefore, Let the training data set and calibration data sets coincide so that observation i is the same as i + k for 1 ≤ i ≤ k and l = 2k for the ICP used in Algorithm 1.
Suppose A * γ (x, y) < t(γ), since t(γ) is the smallest value for which Definition 3 holds, then Since l = 2k and all observations i are the same as i + k, substituting A * γ for A, (1) gives Considering (11) and (12), it immediately follows that The prediction for observation i is correct if and only if Use an indicator variable to express this: . Definition 6. Suppose S is an index set of observations and let the data set of be the vector of coefficients using logistic regression as probability estimator for the correctness of the prediction intervals.
We use the notation for the probability estimator in (6) but since we use logistic regression, we supplement it with the coefficients β as an additional argument: p(z; A, β). For convenience, let p i = p(z i ; A,β(0)); i.e. the probability estimate from the base ICP using CM A.
We now have a framework in place to prove our result. Our idea is that, for a particular example z i , for any feedback-adjusted weight γ > 0 and sensitivity δ ≥ 0: 1. if c i (0) = 0 and p i < 1 − ε and c i (γ) = 1, then we expect p(z i ; A * γ ,β(γ)) > p i ; 2. if c i (0) = 0 and p i > (1 − ε) + δ, then c i (γ) = 0; 3. if c i (0) = 1 and p i < (1 − ε) − δ, then c i (γ) = 1; 4. if c i (0) = 1 and p i > 1 − ε and c i (γ) = 0, then we expect p(z i ; A * γ ,β(γ)) < p i . Line 1 states that if the conditional probability of being correct is biassed below confidence level then if the feedback-adjusted update by γ switches it to correct, this should increase the conditional probability of being correct. Line 4 states a similar objective but, vice versa, for bias above the confidence level. Both lines 1 and 4 will have the effect of shifting the conditional probability of being correct towards the confidence level. Line 2 states that if the conditional probability is biassed above confidence level but the outcome is already incorrect, then the feedback-adjusted update for any value γ will not change that outcome, since that will not help move the conditional probability towards the confidence level. Line 3 states a similar requirement, vice versa, for bias below confidence level. The following Theorem proves lines 2 and 3.
Proof. Take c i (0) as outcome variable c i , n = k, and S = {i ∈ {1, · · · , k}|c i (0) = c i (γ)}. Then since c i (γ) = 1 − c i (0) for i ∈ S, D S = S γ and DS = {(x i , c i (0))|i ∈ {1, · · · , k} and c i (0) = c i (γ)}.   (8) Table 4: Optimized values of γ i and δ i in (7) for each iteration i of Algorithm 2, for different experiments. CL=confidence level 1 − ε, C=penalty hyperparameter in (8) Table 5: Accuracies within some segments of the test data set using the Base ICP and ICP with IFACM. Each line shows accuracy measured within just the segment of observations given by the value of the variable. CL=confidence level 1 − ε, C=penalty hyperparameter in (8), # is the number of observations within the segment.


Transferable Dialogue Systems and User Simulators

One of the difficulties in training dialogue systems is the lack of training data. We explore the possibility of creating dialogue data through the interaction between a dialogue system and a user simulator. Our goal is to develop a modelling framework that can incorporate new dialogue scenarios through self-play between the two agents. In this framework, we first pre-train the two agents on a collection of source domain dialogues, which equips the agents to converse with each other via natural language. With further fine-tuning on a small amount of target domain data, the agents continue to interact with the aim of improving their behaviors using reinforcement learning with structured reward functions. In experiments on the MultiWOZ dataset, two practical transfer learning problems are investigated: 1) domain adaptation and 2) single-to-multiple domain transfer. We demonstrate that the proposed framework is highly effective in bootstrapping the performance of the two agents in transfer learning. We also show that our method leads to improvements in dialogue system performance on complete datasets.

Introduction
This work aims to develop a modelling framework in which dialogue systems (DSs) converse with user simulators (USs) about complex topics using natural language. Although the idea of joint learning of two such agents has been proposed before, this paper is the first to successfully train both agents on complex multi-domain human-human dialogues and to demonstrate a capacity for transfer learning to low-resource scenarios without requiring re-redesign or re-training of the models.
One of the challenges in task-oriented dialogue modelling is to obtain adequate and relevant training data. A practical approach in moving to a new domain is via transfer learning, where pre-training on a general domain with rich data is first performed and then fine-tuning the model on the target domain. End-to-end DS (Wen et al., 2017;Dhingra et al., 2017) are particularly suitable for transfer learning, in that such models are optimised as a single system. By comparison, pipe-lined based DSs with multiple individual components (Young et al., 2013) require fine-tuning of each component system. These separate steps can be done independently, but it becomes difficult to ensure optimality of the overall system.
A similar problem arises in the data-driven US as commonly used in interaction with the DS. Though many USs have been proposed and been widely studied, they usually operate at the level of semantic representation El Asri et al., 2016). These models can capture user intent, but are otherwise somewhat artificial as user simulators in that they do not consume and produce natural language. As discussed above for DSs, the end-to-end architecture for the US also offers simplicity in transfer learning across domains.
There are also potential advantages to continued joint training of the DS and the US. If a user model is less than perfectly optimised after supervised learning over a fixed training corpus, further learning through interaction between the two agents offers the US the opportunity to refine its behavior. Prior work has shown benefits from this approach to dialogue policy learning, with a higher success rate at dialogue level (Liu and Lane, 2017b;Papangelis et al., 2019;Takanobu et al., 2020), but there has not been previous work that addresses multi-domain end-to-end dialogue modelling for both agents. Takanobu et al. (2020) address refinement of the dialogue policy alone at the semantic level, but do not address end-to-end system architectures. Liu and Lane (2017b); Papangelis et al. (2019) address single-domain dialogues (Henderson et al., 2014), but not the more realistic and complex multi-domain dialogues.
This paper proposes a novel learning framework for developing dialogue systems that performs Joint Optimisation with a User SimulaTor (JOUST). 1 Through the pre-training on complex multi-domain datasets, two agents are able to interact using natural language, and further create more diverse and rich dialogues. Using reinforcement learning (RL) to optimise both agents enables them to depart from known strategies learned from a fixed limited corpus, to explore new, potentially better policies. Importantly, the end-to-end designs in the framework makes it easier for transfer learning of two agents from one domain to another. We also investigate and compare two reward designs within this framework: 1) the common choice of task success at dialogue level; 2) a fine-grained reward that operates at turn level. Results on Mul-tiWOZ dataset  show that our method is effective in boosting the performance of the DS in complicated multi-domain conversation. To further test our method in more realistic scenarios, we design specific experiments on two low-resource setups that address different aspects of data sparsity. Our contributions can be summarised as follows: • Novel contributions in joint optimisation of a fully text-to-text dialogue system with a matched user simulator on complex, multidomain human-human dialogues.
• Extensive experiments, including exploring different types of reward, showing that our framework with a learnable US boost overall performance and reach new state-of-the-art performance on MultiWOZ.
• Demonstration that our framework is effective in two transfer learning tasks of practical benefit in low-resources scenarios with in-depth analysis of the source of improvements.
2 Pre-training the Dialogue System and User Simulator In our joint learning framework, we first pre-train the DS and US using supervised learning so that two models are able to interact via natural language. This section presents the architectures of 1 The code is released at https://github.com/ andy194673/joust. two agents, illustrated in Fig. 1, and the objectives used for supervised learning.

Dialogue system
Dialogue state tracking (DST) The first task of a DS is to process the dialogue history in order to maintain the belief state which records essential information of the dialogue. A DST model is utilized to predict the set of slot-value pairs which constitute the constraints of the entity for which the user is looking for, e.g. {hotel_area=north, hotel_name=gonville_hotel}.
The DST model used here is an encoder-decoder model with attention mechanism (Bahdanau et al., 2015). The set of slot-value pairs is formulated as a slot sequence together with a value sequence. For the t th dialogue turn, the DST model first encodes the dialogue context and the most recent user utterance x us t−1 using a bi-directional LSTM (Graves et al., 2005)  is then passed through separate affine transforms followed by the softmax function to predict a slot token and value for step i. The final belief state is the aggregation of predicted slot-value pairs of all decoding steps.
Database Query Based on the updated belief state, the system searches the database and retrieves the matched entities. In addition, a one-hot vector of size 3 characterises the result of every query.
Context Encoding To capture the dialogue flow, a hierarchical LSTM (Serban et al., 2016) encodes the dialogue context from turn to turn throughout the dialogue. At each turn t, the most recent user utterance x us t−1 is encoded by an LSTM-based sentence encoder to obtain a sentence embedding e us t and hidden states H us t . Another LSTM is used as the context encoder, which encodes e us t as well as the output of the context encoder on the user side c us t−1 from the previous turn (see Fig. 1). The context encoder produces the next dialogue context state c ds t for the downstream dialogue manager.
Policy The dialogue manager determines the system dialogue act based on the current state of the dialogue. The system dialogue act is treated as a sequence of tokens in order to handle cases in Figure 1: Overall architecture of the proposed framework, where the dialogue system (DS) and user simulator (US) discourse with each other. t denotes dialogue turn index. The context encoder is shared between the two agents.
which multiple system actions exist in the same turn.The problem is therefore formulated as a sequence generation task using an LSTM. At each decoding step, the inputs to the policy decoder are: 1) the embedding of the act token predicted at the previous step; 2) the previous hidden state; 3) the attention vector obtained by attending over the hidden states of the user utterance H us t using 2) as query; 4) the database retrieval vector; 5) the summarized belief state, which is a binary vector where each entry corresponds to a domain-slot pair. The output space contains all possible act tokens. For better modeling of the dialogue flow, the initialization of the hidden state is set to the context state c ds t obtained by the context encoder.
Natural language generation (NLG) The final task of the DS is to generate the system response, based on the predicted system dialogue act. To generate the word sequence another LSTM is used as the NLG model. At each decoding step, the previous hidden state serves as a query to attend over the hidden states of the policy decoder. The resulting attention vector and the embedding of the previous output word are the inputs to an LSTM whose output is the word sequence with delexicalized tokens. These delexicalized tokens will be replaced by retrieval results to form the final utterance.

User Simulator
As in the DS, the proposed US has a dialogue manager, an NLG model and a dialogue context encoder. However, in place of a DST to maintain the belief state, the US maintains an internal goal state to track progress towards satisfying the user goals.

Goal State
The goal state is modelled as a binary vector that summarises the dialogue goal. Each entry of the vector corresponds to a domain-slot pair in the ontology. At the beginning of a dialogue, goal state entries are turned on for all slots that make up the goal. At each dialogue turn, the goal state is updated based on the previous user dialogue act. If a slot appears in the previous dialogue act, either as information from the user or as a request by the US, the corresponding entry is turned off.

Context encoding, Policy & NLG in the US
These steps follow their implementations in the DS. For context encoding in the US, a sentence encoder first encodes the system response using an LSTM to obtain hidden states H ds t and sentence embedding e ds t . The context encoder takes e ds t and DS context state c ds t as inputs to produce the dialogue context state c us t which is passed to the DS at the next turn.
Also as in the DS, the policy and the NLG model of the US are based on LSTMs. The input to the policy are goal state, hidden states of the sentence encoder H ds t and context state c us t , to produce the user dialogue act, represented as in the DS as a sequence of tokens. The NLG model takes the hidden states of policy decoder as input to generate the user utterance, which is then lexicalised by replacing delexicalised tokens using the user goal.

Supervised Learning
For each dialogue turn, the ground truth dialogue acts and the output word sequences are used as supervision for both the DS and the US. The losses of the policy and the NLG model are the crossentropy losses of the predicted sequence probability p and the ground-truth y: In the above, * can be either ds or us, referring either to the DS or the US: e.g. p ds a,i is the probability of the system act token at the i th decoding step in a given turn. The ground-truth y contains both word sequences and act sequences with W and A as their lengths.
The DST annotations are also used as supervision for the DS. The loss of the DST model is defined as the sum of the cross-entropy losses for slot and value: where |SV | is the number of slot-value pairs in a turn; i is the decoding step index. p ds s,i and p ds v,i are the predictions of slot and value at the i th step.
The overall losses for the DS and the US are: where θ ds and θ us are the parameters of DS and US, respectively. The two agents are updated jointly to minimize the sum of the losses (L ds +L us ). The success rate of the generated dialogues is used as the stopping criterion for supervised learning.

RL Optimisation of the Dialogue System and User Simulator
After the DS and US models are pre-trained from the corpus using supervised learning, they are finetuned using reinforcement learning (RL) based on the dialogues generated during their interactions. Two reward designs are presented after which the optimisation strategy is given.

Dialogue-Level Reward
Following common practice (El Asri et al., 2014;Zhao et al., 2019), the success of the simulated dialogues is used as the reward, which can only be observed at the end of the dialogue. A small penalty is given at each turn to discourage lengthy dialogues. When updating the US jointly with the DS during interaction using RL, the reward is shared between two agents.

Turn-Level Reward
While the dialogue-level reward is straight-forward, it only considers the final task success rate of the dialogues and neglects the quality of the individual turns. For complex multi-domain dialogues there is a risk that this will make it difficult for the system to learn the relationship between actions and rewards. We thus propose a turn-level reward function that encapsulates the desired behavioural features of fundamental dialogue tasks. The rewards are designed separately for the US and the DS according to their characteristics.
DS Reward A good DS should learn to refine the search by requesting needs from the user and providing the correct entities, with their attributes, that the user wishes to know. Therefore at the current turn a positive reward is assigned to DS if: 1) it requests slots that it has not requested before; 2) it successfully provides an entity; or 3) is answers correctly all additional attributes requested by the user. Otherwise, a negative reward is given.
US Reward A good US should not repeatedly give the same information or request attributes that have already been provided by the DS. Therefore, a positive reward is assigned to the US if: 1) it provides new information about slots; 2) it asks new attributes about a certain entity, or 3) it replies correctly to a request from the DS. Otherwise a penalty is given.

Optimization
We apply the Policy Gradient Theorem (Sutton et al., 2000) to the space of (user/system) dialogue acts. In the t th dialogue turn, the reward r ds t or r us t is assigned to the two agents at final last step of their generated act sequence. The return for the action at the i th step is R * i = γ |A * |−i r * t , where * denotes ds or us, and |A * | is the length of the act sequence of each agent. γ ∈ [0, 1] is a discounting factor. The policy gradient of each turn can then be written as: where p * a,i is the probability of the act token at the i th step in the predicted dialogue act sequence. The two agents are updated using Eqn. (4) at each turn within the entire simulated dialogue.

Experiments
Dataset The MultiWOZ 2.0 dataset  is used for all experiments. It contains 10.4k dialogues with an average of 13.6 turns. Each dialogue can span up to three domains. Compared to previous benchmark corpora such as DSTC2 (Williams et al., 2016) or WOZ2.0 (Wen et al., 2017, MultiWOZ is more challenging because 1) its rich ontology contains 39 slots across 7 domains; 2) the DS can take multiple actions in a single turn; 3) the complex dialogue flow makes it difficult to hand-craft a rule-based DS or an agenda-based US. Lee et al. (2019) provided the user act labels.
Training Details The positive and negative RL rewards of Sec. 3 are tuned in the range [-5, 5] based on the dev set. The user goals employed for interaction during RL are taken from the training data without synthesizing new goals. Further training details can be found in Appendix A.1.
Evaluation Metrics The proposed model is evaluated in terms of the inform rate (Info), the success rate (Succ), and BLEU. 2 The inform rate measures whether the DS provides the correct entity matching the user goal, while the success rate further requires the system to answer all user questions correctly. Following (Mehri et al., 2019), the combined performance (Comb) is also reported, calculated as 0.5 * (Info + Succ) + BLEU.

Interaction Quality
First, it is examined whether the proposed learning framework improves the discourse between dialogue system and user simulator. Several variants of our model are examined: 1) two agents are pre-trained using supervised learning, serving as baseline; 2) RL is used to fine-tune only the DS (RL-DS) or both agents (RL-Joint). In each RL case, we can either use rewards at the dialogue level (dial-R, Sec. 3.1) or rewards at the turn-level (turn-R, Sec. 3.2). The two trained agents interact based on 1k user goals from the test corpus, with the generated dialogues being evaluated using the metrics above.
From Table 1, we can see that the application of RL in our framework improves the success rate by more than 10% (b-e vs. a). This indicates that the DS learns through interaction with the learned US, and the designed rewards, to be better at completing the task successfully. Moreover, the joint  optimisation of both the US and the DS provides dialogues with higher success rate than only optimising the DS (c&e vs. b&d). It shows that the behaviour of the US is realistic enough and diverse enough to interact with the DS, and its behavior can be improved together during RL optimisation. Finally, by comparing two reward designs, the finegrained rewards at the turn level seem to be more effective towards guiding two agents' interaction (b&c vs. d&e), which is reasonable since they reflect more than simple success rate in terms of the nature of the tasks. Some real, generated dialogues through the interactions are provided in Appendix A.6; we note that after RL, both agents respond to requests more correctly and also learn not to repeat the same information, leading to a more successful and smooth interaction without loops in the dialogue. The corresponding error analysis of each of the agents is provided later in Sec. 4.4.1.

Benchmark Results
We conduct experiments on the official test set for comparison to existing end-to-end DSs. The trained DS is used to interact with the fixed test corpus following the same setup of . Results are reported using a predicted belief state (Table 2) and using an oracle belief state (  of our model. Joint learning of two agents using RL with the fine-grained rewards reaches the best combined score and success rate. This implies that the exploration of more dialogue states and actions in the simulated interactions reinforces the behaviors that lead to higher success rate, and that these generalise well to unfamiliar states encountered in the test corpus. Our best RL model produces competitive results in Table 2 when using predicted belief state, and can further outperform the previous work in Table 3 when using oracle belief state. Note that we do not leverage the powerful pre-trained transformerbased models like SOLOIST or MinTL-BART model. We found that with RL optimisation, our LSTM-based models can still perform competitively. In terms of DS model structure, the most similar work would be the DAMD model. The performance gain found in comparing "JOUST Supervised Learning" to DAMD is partially due to the better performance of our DST model. 3 We also conduct experiments using only 50% of the training data for supervised learning to verify the efficacy of the proposed method under different amounts of data. As shown in Table 4, it is observed that our method also improves the model upon supervised learning when trained with less data and the improvements are consistent with the complete data scenario.

Transfer Learning
In this section, we demonstrate the capability of transfer learning of the proposed framework under two low-resource setups: Domain Adaptation and Single-to-Multiple Domain Transfer. Two finetuning methods are adopted: the straightforward fine-tuning without any constraints (Naive) and 3 In correspondence, the DAMD authors report a DST model with joint accuracy of ca. 35%, while ours is 45%.  elastic weight consolidation (EWC) (Kirkpatrick et al., 2017). We show that the proposed RL can be further applied to both methods and produces significantly improved results. Here we experiment the best RL variants using turn-level rewards (same as (e) in Table 1).

Domain Adaptation
In these experiments, each of five domains is selected as the target domain.
Taking the hotel domain for example, 300 dialogues 4 involving the hotel domain are sampled from the training corpus as adaptation data. The rest of the dialogues, not involving the hotel domain, form the source data. Both the DS and the US are first trained on the source data (Source), and then fine-tuned on the limited data of the target domain (Naive, EWC). Afterwards, the pair of agents is trained in interaction using the proposed RL training regime (+RL). Results in the form of the combined score are given in Table 5 (corresponding success rates are provided in Appendix A.5). As expected, models pre-trained on source domains obtain low combined scores on target domains. Fine-tuning using Naive or EWC method significantly bootstraps the systems, where the regularization in EWC benefits more for the low-resource training. By applying our proposed framework to the two sets of finetuned models, the performance can be further improved by 7-10% in averaged numbers, with both predicted and oracle belief states. This indicates that through the interaction with the US, the DS is not constrained by having seen only a very limited amount of target domain data, and that it can learn effectively from the simulated dialogues using the simple reward structure (the RL learning curve is presented in Sec. 4.4.3). With a better initialization points such as EWC models, the models can learn from a higher quality interaction and produce better results (EWC+RL vs Naive+RL). On aver-  Single-to-Multiple Domain Transfer Another transfer learning scenario is investigated where only limited multi-domain data is accessible but sufficient single-domain dialogues are available. This setup is based on a practical fact that singledomain dialogues are often easier to collect than multi-domain ones. All single-domain dialogues in the training set form the source data. For each target multi-domain combination, 100 dialogues 5 are sampled as adaptation data. As before, the DS and the US are first pre-trained on the source data and then fine-tuned on the adaptation data. Afterwards, two agents improve themselves through interaction. The models are tested using the multi-domain dialogues of the test corpus. Results in the form of the combined score are given in Table 6 (refer to Appendix A.5 for success rates). Although the Source models capture individual domains, they cannot manage the complex flow of multi-domain dialogues and hence produce poor combined scores, with worst results on combinations of three domains. Fine-tuning improves performance significantly, as the systems learn to transition between domains in the multi-domain dialogue flow. Finally, applying our RL optimization further increases the performance by 6-9% on average. This indicates that the dialogue agents can learn more complicated policies through exploring more dialogue states and actions while interacting with user simulator. We analyse the sources of improvements in the following section.

Error Analysis
We first examine the behavior of the US and the DS to understand the improved success rate in transfer learning. The models are those of Table 5 and are examined after fine-tuning using Naive method (Naive) and then after reinforcement learning (Naive+RL). For the DS, the rates of missing entities (Miss Ent.) and of wrong answers (Wrong Ans.) are reported. For the US, rates of repetitions of attributes (Rep. Att.) and of missing answers (Miss Ans.) are reported. The results shown in Table 7 are averaged over the five adaptation domains 6 . We see that with RL optimisation the errors made by the two agents are reduced significantly. Notably, the user model learns not to repeat the information already provided and attempts to answer more of the questions from the dialogue agent. These are the behaviors the reward structure of Sec. 3.2 are intended to encourage, and they lead to more successful interactions in policy learning.

Exploration of States and Actions
We now investigate whether our framework encourages exploration through increased interaction in transfer learning. We report the number of unique belief states in the training corpus and in the dialogues generated during RL interaction, as well as the unique action sequences per state that each  agent predicts. As shown in Table 8, the DS encounters more states in interaction with the US and also takes more unique actions in reinforcement learning relative to what it sees in supervised learning. In this way the DS considers additional strategies during the simulated training dialogues, with the opportunity to reach better performance even with only limited supervised data. Detailed results for each adaptation case are provided in Appendix A.4.

RL Learning Curve
Here we show that the designed reward structure is indeed a useful objective for training. Figure  We can see that both the reward value and model performance are consistently improved during RL, and their high correlation verifies the efficacy of the proposed reward design for training task-oriented dialogue systems.

Human Evaluation
The human assessment of dialogue quality is performed to confirm the improvements of the proposed methods. 400 dialogues, generated by the two trained agents, are evaluated by 14 human assessors. Each assessor is shown a comparison of two dialogues where one dialogue is generated by  Table 9: Human assessment of the system quality under supervised learning and reinforcement learning. the models using supervised learning (SL) and another is generated by the models after RL optimization. Note that here we are evaluating the performance gain during interactions between two agents (Sec. 4.1), instead of the gain in benchmark results by interacting with the static corpus (Sec. 4.2). This is why the baseline is our SL model instead of the existing state-of-the-art systems.
The assessor offers judgement regarding: • Which dialogue system completes the task more successfully (DS Success)?
• Which user simulator behaves more like a real human user (US Human-like)?
• Which dialogue is more natural, fluent and efficient (Dialogue Flow)? The results with relative win ratio, shown in Table 9, are consistent with the automatic evaluation. With the proposed RL optimisation, the DS is more successful in dialogue completion. More importantly, joint optimisation of the US is found to produce more human-like behavior. The improvement under the two agents leads to a more natural and efficient dialogue flow.

Related Work
In the emerging field of end-to-end DSs, in which all components of a system are trained jointly (Liu and Lane, 2017a;Wen et al., 2017;Lei et al., 2018). RL methods have been used effectively to optimize end-to-end DSs in (Dhingra et al., 2017;Zhao et al., 2019), although using rule-based USs or a fixed corpus for interaction. Recent works utilise powerful transformers such as GPT-2 (Peng et al., 2020;Hosseini-Asl et al., 2020) or T5 (Lin et al., 2020b) for dialogue modeling and reach stateof-the-art performance; however, the area of having a user simulator involved during training is unexplored. By comparison, this work uses a learned US as the environment for RL. The two agents we propose are able to generate abundant high-quality dialog examples and they can be extended easily to unseen domains. By utilizing an interactive envi-ronment instead of a fixed corpus, more dialogue strategies are explored and more dialogue states are visited.
There have been various approaches to building USs. In the research literature of USs, one line of research is rule-based simulation such as the agenda-based user simulator (ABUS) (Schatzmann and Young, 2009;Li et al., 2016). The ABUS's structure is such that it has to be re-designed for different tasks, which presents challenges in shifting to new scenarios. Another line of work is datadriven modelling. El Asri et al. (2016) modelled user simulation as a seq2seq task, where the output is a sequence of user dialogue acts the level of semantics. Gur et al. (2018) proposed a variational hierarchical seq2seq framework to introduce more diversity in generating the user dialogue act.  introduced the Neural User Simulator (NUS), a seq2seq model that learns the user behaviour entirely from a corpus, generates natural language instead of dialogue acts and possesses an explicit goal representation. The NUS outperformed the ABUS on several metrics. Kreyssig (2018) also compared the NUS and ABUS to a combination of the ABUS with an NLG component. However, none of these prior works are suitable for modelling complex, multi-domain dialogues in an end-to-end fashion. By contrast, the user model proposed here consumes and generates text and so can be directly employed to interact with the DS, communicating via natural language.
The literature on joint optimization of the DS and the US is line of research most relevant to our work. Takanobu et al. (2020) proposed a hybrid value network using MARL (Lowe et al., 2017) with roleaware reward decomposition used in optimising the dialogue manager. However, their model requires separate NLU/NLG models to interact via natural language, which hinders its application in the transfer learning to new domains. Liu and Lane (2017b); Papangelis et al. (2019) learn both the DS and the US in a (partially) end-to-end manner. However, their systems are designed for the single-domain dataset (DSTC2) and cannot handle the complexity of multi-domain dialogues: 1) their models can only predict one dialogue act per turn, which is not sophisticated enough for modelling multiple concurrent dialogue acts; 2) the simple DST components cannot achieve satisfactory performance in the multi-domain setup; 3) the user goal change is not modelled along the dialogue proceeds, which we found in our experiments very important for learning complex behaviors of user simulators. Relative to these three publications, this paper focuses on joint training of two fully end-to-end agents that are able to participate in complex multi-domain dialogues. More importantly, it is shown that the proposed framework is highly effective for transfer learning, which is a novel contribution relative to previous work.

Conclusion and Future Work
We propose a novel joint learning framework of training both the DS and the US for complex multidomain dialogues. Under the low-resource scenarios, the two agents can generate more dialogue data through interacting with each other and their behaviors can be significantly improved using RL through this self-play strategy. Two types of reward are investigated and the turn-level reward benefits more due to its fine-grained structure. Experiments shows that our framework outperforms previously published results on the MultiWOZ dataset. In two transfer learning setups, our method can further improves the well-performed EWC models and bootstraps the final performance largely. Future work will focus on improving the two agents' underlying capability with the powerful transformer-based models.

A.1 Training Details
Both the DS and the US are trained in an end-to-end fashion using the Adam optimizer. The sizes of the embedding and of the hidden layers are set to 300. During supervised training, the batch size is 100 and the learning rate is 0.001, while during RL, 10 is used as the batch size and 0.0001 as the learning rate for stability. We set the discounting factor γ to 1. The computing infrastructure used is Linux 4.4.0-138-generic x86_64 with the NVIDIA GPU GTX-1080. Average run time per model using 100% training data is around 6 hours. Model parameters is around 11M in total.
The turn-level rewards used for the best models in benchmark results are reported in Table 10 below. All rewards are tuned based on the combined score of the validation performance averaged over three seeds. As for dialogue-level rewards, a positive reward 1.0 will be given if a dialogue is successful.

A.2 Details of Dataset
As noted in the paper, we follow the original split of the MultiWOZ dataset and the number of dialogues for train/dev/test split is 8420/1000/1000. Data statistics of the number of dialogues in the two transfer learning scenarios are provided in Tables 11 and 12. Taxi  Train  300  300  300  300  300  Dev  438  415  400  484  206  Test  437  394  396  495 195

A.3 Error Analysis
The error analysis of each domain adaptation cases are provided in Tables 13 and 14.

A.4 Exploration
The detailed numbers of explored dialogue states and the average of unique dialogue actions per state in each case of two transfer learning scenarios are provided in Tables 15 and 16.

A.5 Transfer Learning
Here we provide the results in success rate in two transfer learning setups.

A.6 Generated Dialogue Examples
Here we provides two dialogue pairs examples that are generated by the two agents' interaction using supervised learning (SL) and using RL respectively in the following pages. As seen in the Table 19 first dialogue, since the SL user model answers wrong to the system's request, the system keeps asking the unsolved question, leading to an unsuccessful dialogue with loop (highlighted in color). On the other hand, the interaction between RL models (second dialogue) is much smoother and efficient since both agents answer correctly to each other. This indicates the designed rewards are useful to improve the agents' behaviors. Similar trend can be observed in Table 20, where the user model keeps stating the same information about restaurant. 19-sys: TR0269 arrives at 18:15 . would you like me to book it for you ? 20-usr: yes , please . i need the price and travel time . 21-sys: the train id is TR0269 , the price is 10 and the travel time is 50 . 22-usr: i am also looking for a particular attraction called club salsa . 23-sys: club salsa is a nightclub in the centre . the address is 1 station road . entrance is free .
is there anything else i can help you with ? 24-usr: that is all i need . thank you for your help . 25-sys: thank you for using our system ! Dialogue generated by two agents trained using RL (Dialogue is smooth and successful) 00-usr: i am looking for a train from kings lynn on wednesday . 01-sys: what is your destination ? 02-usr: i need to arrive in cambridge by 18:15 . 03-sys: i have train TR0415 that leaves at 17:11 and arrives at 17:58 . would you like me to book it for you ? 04-usr: yes , please book 2 tickets . 05-sys: booking was successful , the total fee is 9.80 pounds payable at the station . reference number is fztwszhh . is there anything else i can help you with ? 06-usr: yes , i am also looking for a particular attraction called club salsa . 07-sys: club salsa is located at 1 station road , postcode cb12jb . is there anything else i can help you with ? 08-usr: no , that s all i need today . thank you . 09-sys: thank you for using our service . have a great day ! Table 19: Example 1: two dialogues generated by SL system and RL system respectively. The dialogue loop with repeated information is highlighted. Output utterances are lexicalised with corresponding slot values (belief state for system; user goal for user). If the system generates attributes that has not existing in the belief state, the values are randomly sampled from the ontology, e.g., the train departure "london kings cross" in the first dialogue.