Offline Policy Comparison with Confidence: Benchmarks and Baselines

We consider the fundamental decision problem of predicting the relative future performance of two policies, which we formalize via policy comparison queries (PCQs). A PCQ is a tuple $q=(s,\pi,{\hat{s}},{\hat{\pi}},h)$, where $s$ and ${\hat{s}}$ are arbitrary starting states, $\pi$ and ${\hat{\pi}}$ are policies, and $h$ is a horizon. The answer to a PCQ is the truth value of $V^{\pi}(s,h)<V^{{\hat{\pi}}}({\hat{s}},h)$. That is, a PCQ asks whether the $h$-horizon value of ${\hat{\pi}}$ is greater than $\pi$ when started in ${\hat{s}}$ and $s$ respectively.

As motivated in Section 1, PCQs are useful for both human-decision support and automated policy optimization. For example, if a farm manager wants information about which of two irrigation policies, $\pi$ and ${\hat{\pi}}$, will result in the best future crop yield given the environment state $s$, then the corresponding PCQ would be $(s,\pi,s,{\hat{\pi}},h)$. Alternatively, the manager may be interested in whether a policy $\pi$ is better suited to an environmental state $s$ or ${\hat{s}}$, which is captured by the PCQ $(s,\pi,{\hat{s}},\pi,h)$. In addition, PCQs can be used as the basis for the classic policy improvement step of policy iteration (Puterman, 2014). In particular, we can improve over policy $\pi$ at state $s$ by identifying an action $a^{\prime}$ with higher action value than chosen by $\pi$. The corresponding PCQ for testing $a^{\prime}$ is $(s,\pi,s,\pi^{\prime},h)$, where $\pi^{\prime}$ is the non-stationary policy that first takes action $a^{\prime}$ and then follows $\pi$.

In practice, PCQs within an application domain need not be restricted to comparing policies via a single reward function. Rather there are often multiple quantities of interest to users. For example, a farm manager may be interested in understanding how two irrigation policies compare across multiple features of the future, such as cumulative water usage, plant stress, run off, etc. This can be facilitated by defining reward functions corresponding to each feature and issuing the appropriate PCQs.

Given an accurate generative model of the environment MDP, a PCQ $(s,\pi,{\hat{s}},{\hat{\pi}},h)$ can be answered via Monte-Carlo trajectory sampling to estimate $V^{\pi}(s,h)$ and $V^{{\hat{\pi}}}({\hat{s}},h)$. Further, the confidence in the answer can be arbitrarily improved by increasing the number of sampled trajectories. In this work, we do not assume an environment model, but instead are provided with an offline data set of environment trajectories produced by one or more unknown behavior policies. We will denote this dataset by $\mathcal{D}=\{(s_{i},a_{i},s^{\prime}_{i},r_{i})\}$ where each tuple corresponds to an observed transitions from state $s_{i}$ to state $s^{\prime}_{i}$ after taking action $a_{i}$ and receiving reward $r_{i}$.

Given a dataset $\mathcal{D}$ we would like to learn a model for predicting answers to PCQs from a query space $\mathcal{Q}$. Here, $\mathcal{Q}$ may assert application-specific restrictions on states and policies involved in PCQs. A fundamental challenge is that the coverage of $\mathcal{D}$ will not necessarily be representative of the dynamics and rewards relevant to answering all queries in $\mathcal{Q}$. Thus, if query answers are being used to inform important decisions, then it is critical for each answer to come with a meaningful measure of confidence that accounts for data coverage and statistical variance. Dealing with this uncertainty is also a core challenge for general offline RL (Levine et al., 2020), which has lead to a number of approaches for addressing it. However, there is little direct evaluation of the uncertainty-handling components.

The above motivates the OPCC learning problem, which provides a dataset $\mathcal{D}$ and desired constraints on the query space $\mathcal{Q}$. The learner should output a model $w=(f,c)$ composed of: 1) a query prediction function $f:\mathcal{Q}\rightarrow\{0,1\}$, which returns a binary answer for any query in $\mathcal{Q}$, and 2) a confidence function $c:\mathcal{Q}\rightarrow[l,u]$ that maps queries in $\mathcal{Q}$ to a confidence value within a bounded interval. Given a query $q$, the intent is for larger values of $c(q)$ to indicate a higher confidence in the prediction $f(q)$. Note that we do not attach any predefined semantics to the values of $c(q)$ to allow for flexibility of potential solutions. Rather, we focus on defining metrics for directly evaluating the quality of uncertainty quantification provided by $w$. If desired, various methods can be used after learning to calibrate the confidence values of $c$ to meaningful scales (e.g. (Loh, 1987; Naeini et al., 2015). Section 5 discusses possible learning approach and the baselines evaluated in this paper.

Since OPCC involves confidence estimation for binary PCQ predictions, we can draw on evaluation metrics from prior work on selective classification (e.g. (El-Yaniv et al., 2010; Xin et al., 2021)). In selective classification, the aim is to reduce prediction errors by allowing a predictor to abstain from a prediction if the confidence is below a threshold. The quality of confidence values is thus related to how well they result in abstaining when the prediction would have been incorrect. This idea is formalized via risk-coverage curves (RCCs), as outlined below.

Risk-Coverage Curve. Let $\mathcal{L}(q,\hat{y})$ be a loss function for predicting $\hat{y}$ for query $q$, e.g. 0/1 loss. Given a test set of queries $Q=\{q_{1},\ldots,q_{N}\}$, a model $w=(f,c)$, and confidence threshold $\tau$, the coverage is the fraction of test queries with confidence at least $\tau$. The selective risk is the average loss of $f$ over the covered queries. Formally, the coverage and selective risk are respectively define by

where $I$ is the binary indicator function. Thus, each possible threshold corresponds to a risk-coverage operating point $\langle r(w,Q,\tau),cov(w,Q,\tau)\rangle$. An RCC is simply the risk versus coverage curve of these operating points when sweeping through possible thresholds. Practically, for a finite test set $Q$ there can be at most $|Q|$ unique operating points since there are at most $|Q|$ distinct confidence values produced by $c$. Thus, when displaying empirical RCCs we linearly interpolate between those operating points.³³3This is justified by the fact that we can achieve (in expectation) any linearly interpolated operting point between two thresholds $\tau_{1}$ and $\tau_{2}$ by varying the probability $p\in[0,1]$ of using $\tau_{1}$ versus $\tau_{2}$ to decide on abstention. Figure 1 shows an example of an RCC from our experiments. The curve starts at the point $(0,0)$, since the risk is 0 at zero coverage, and ends at $(1,r_{f})$, where $r_{f}$ is the risk of $f$ evaluated on all of $Q$.

In order to provide a single measure of the RCC quality, we aggregate across all thresholds to compute the Area Under the RCC (AURCC). Since lower risk is preferred, we consider a lower AURCC to indicate better confidence estimation. The minimum AURCC is 0, which occurs when the predictor $f$ has zero risk on all of $Q$. Rather, for a ranomized confidence function that returns a uniformly random value in $[l,u]$, the expected AURCC is $r_{f}$⁴⁴4This is because for any threshold $\tau$ and uniformly random confidence function, there is a uniform probability of covering any particular query. Thus, the expected risk for any threshold $\tau>l$ is the expected risk over a random draw from the query set, which is $r_{f}$., indicating no ability to quantify prediction uncertainty.

RPP. Our second selective-classification metric from (Xin et al., 2021) is reverse pair proportion (RPP). The main idea is that the ordering of confidence values for a pair of queries should reflect the relative prediction loss for those queries. RPP measures how often the confidence value ordering conflicts with the relative losses across all pairs of queries. In particular, a conflict occurs when the loss of $q_{1}$ is less than $q_{2}$, but we are more confident about $q_{2}$ than $q_{1}$. The RPP is just the fraction of such conflicts.

where $l(q)=L(q,f(q))$ is the loss of $f$ on $q$.

$\bm{CR_{K}}$. Finally, we introduce a new metric on just the confidence function $c$. A practical difference between different confidence functions is the resolution of values that they output in practice. For example, given a set of queries $Q$, one confidence function $c_{1}$ may result in only three distinct coverage values $cov(w,Q,\tau)$ across all thresholds, while another confidence function $c_{2}$ results in $|Q|$ distinct coverage values. All else being equal $c_{2}$ is the preferable function, since it provides a higher level of resolution with respect to abstention/coverage rates. We measure this via coverage resolution at $K$, denoted $CR_{K}$. To compute $CR_{K}$ for $w=(c,f)$ and query set $Q$, the coverage interval $[0,1]$ is partitioned into $K$ equal bins and we return the fraction of bins which contain $cov(w,Q,\tau)$ for some threshold $\tau$. By increasing $K$ we get a finer grained distinction in coverage resolution.

To support easier adoption of our benchmarks, we selected seven environments and corresponding datasets that are currently used in offline RL research. As a first set of OPCC benchmarks, we have chosen to focus on relatively low-dimensional environments with non-image-based observations. This helps focus initial studies on fundamental OPCC capabilities, rather than simultaneously addressing the additional complexities that enter with lower-level perceptual observations such as images.

Maze2d (4 environments). The Maze2d environments were introduced in D4RL (Fu et al., 2020) and comprise of 2d mazes of different complexities: open, u-maze, medium, and large as illustrated in Figure 3. Each environment has 4D observations giving the position and velocity of the ball being controlled and a 2D action space specifying the direction of movement. The goal in each environment is to control a rolling ball to reach a goal location. For our benchmarks, we used the sparse-reward version of the environments that provides unit reward for each time step in the goal region. There are no terminal states in these environments and episode ends after maximum number of allowed time-steps reported in Table 8. We use the datasets provided by D4RL, which we refer to as “1M" due to the datasets each having 1 million state transitions. The D4RL trajectory data sets were created by running a path-planning algorithm to navigate in the maze between different start and end points.

Gym-Mujoco (3 environments). The Gym-Mujoco environments are based on controlling the actuators of systems within the Mujoco physics simulators. We consider three locomotion-based environments from OpenAI Gym (Brockman et al., 2016): HalfCheetah, Walker2d, and Hopper. For each environment, we use the corresponding D4RL (Fu et al., 2020) datasets that include behavior trajectories of varying qualities. This includes "random, medium, medium-replay, expert and expert-replay". These environments are qualitatively different from Maze2d in that they involve controlling periodic locomotion behavior based on continuous states and actions. Rather Maze2d is primarily about goal-based path planning (navigation) rather than controlling low-level locomotion.

For each environment we must create a set of PCQs with ground truth answers for evaluating OPCC. A possible starting point is the off-policy evaluation (OPE) extension (Fu et al., 2021) to D4RL, which includes policies for a subset of the environments. In particular, one of the tasks considered is policy ranking, which is similar in spirit to OPCC. However, that extension of D4RL does not capture at least two important characteristics of OPCC. First, the evaluation protocols do not explicitly address measuring the quality of uncertainty quantification. Of course, this can be addressed by just extending the evaluation protocol and metrics.

Second, and more importantly, it is not clear how to define adequate query sets for evaluating OPCC. In particular, the OPE ranking task from D4RL is currently limited to just ranking policies based on their expected values over the initial state distribution of each environment. In contrast, OPCC evaluations should involve sets of PCQs that cover a wide range of states that are both in-distribution and out-of-distribution relative to the offline data set. Further, it is desirable to select the PCQs in a way that spans some notion of PCQ difficulty. In particular, the notion of difficulty we consider here for a PCQ $(s,\pi,{\hat{s}},{\hat{\pi}},h)$ is directly related to the performance gap between the policies, i.e $\left|V^{\pi}(s,h)-V^{{\hat{\pi}}}({\hat{s}},h)\right|$. It is expected that all else being equal, larger gaps will reason in easier discrimination between policies. Indeed one of the initial challenges in developing the benchmarks was to try to create query sets that were not all too easy or too hard.

Bases on above considerations we create the evaluation sets of PCQs for each environments via the following steps.

Step 1: Policy Generation. We first train multiple policies for an environment to serve as the policy used for PCQ construction. We chose to train new policies, rather than use policies from D4RL, to ensure they would be distinct from the behavior policies used to create the D4RL datasets. For each environment we used the corresponding simulator and multiple runs of the PPO algorithm (Schulman et al., 2017) to train a set of policies of varying quality. We then hand-picked 4 policies with an effort to ensure that they were sufficiently distinct in terms of quality and behavior to support non-trivial PCQs. Performance of these policies in shared in Table 9 (appendix).

Step 2: Initial State Generation. For each environment we generated a large set of potential initial states by running episodes of the random policy, the learned policies, and a mixture of random and learned policies. This produced a set of states that covered a wide range of the environment that extended well beyond the initial state distributions.

Step 3: Candidate PCQ Generation. For each horizon $h\in\{10,20,30,40,50\}$ we create a set of 2000 randomly constructed PCQs from the initial states and learned policies. This included explicitly creating random PCQs of the form $(s,\pi,s,{\hat{\pi}},h)$ with $s$ a random initial state and $\pi,{\hat{\pi}}$ a random pair of the learned policies. In addition, we create a set of PCQs of the form $(s,\pi,{\hat{s}},{\hat{\pi}},h)$ in the same way, except that two random initial states are used instead of one.

Step 4: PCQ Labeling and Selection. For each generated PCQ from step 3 we used Monte-Carlo simulation via the environment simulator to accurately estimate $V^{\pi}(s,h)$ and $V^{{\hat{\pi}}}({\hat{s}},h)$ and removed any PCQ having a difference of less than 10 between the value of each side of a query. The motivation is to filter out PCQs that are the most ambiguous and more likely to act as a source of noise in evaluations. Finally, for each $h$, we randomly selected 1500 of the PCQs to include as the benchmark query set. In Figure 4, we show, a scatter plot of $\left(V^{\pi}(s,h),V^{{\hat{\pi}}}({\hat{s}},h)\right)$ for the selected set of PCQs for Halfcheetah-v2 and maze2d-open-v0. Notice the lack of PCQs along the diagonal, which corresponds to the removal of ambiguous queries. Also note that the PCQs span a range of value gaps, which suggests that they span varying PCQs of varying difficult. If these plots showed a bias toward only large gap queries, then additional steps would be necessary to ensure that more variation was present in the selected query sets.

In our experiments, we consider two types of base models for forming ensembles. The first base model is the commonly use Feed-Forward (FF) Gaussian model, which, given the current state/observation and action as input, returns the mean and diagonal covariance matrix of a Gaussian distribution over the next state and reward. This model allows for stochastic Monte-Carlo simulations by drawing the next state from the model’s Gaussian distribution at each time step. In this work, we use the same FF base-model architecture and training details as MBPO (Janner et al., 2019).

We also consider a recent base model (Zhang et al., 2021) (referred to as Auto-regressive (AR)), which was demonstrated in some cases to improve over the output architecture of FF. Instead of generating all $n$ features of the predicted next state in a single pass, AG auto-regressively samples each feature one at a time using $n$ forward passes. In particular, to sample state feature $i$ of the next state, denoted $s_{t+1}^{i}$, the network receives the usual input $s_{t}$ and $a_{t}$ as well as the previously sampled state features $s^{0}_{t+1},...s^{i-1}_{t+1}$. AR then returns the mean and covariance for a Gaussian that is used to sample $s_{t+1}^{i}$. The intuition is that this approach may allow for representing non-Gaussian and multi-modal next-state distributions compared to the uni-modal Gaussian FF model.

Model-based approaches to ORL have commonly used ensembles as an attempt to quantify uncertainty, e.g. via measures of ensemble-member disagreement (Janner et al., 2019). We consider two choices for generating ensembles. The first choice is the standard bootstrapping ensemble approach, which simply trains each ensemble member using a different random weight initialization and bootstrapped dataset $\hat{\mathcal{D}}$ by sampling from $\mathcal{D}$ with replacement $|\mathcal{D}|$ times. The intent is that the combination of classic statistical bootstrapping Efron & Tibshirani (1994) and random initialization will produce a diverse set of ensemble models.

Often, however, it is observed that the basic bootstrapping approach does not create enough diversity in an ensemble, which is counter to our motivation of representing uncertainty. For this reason, there are a number of proposals for increasing the ensemble diversity, of which, we consider just one in this work. In particular, work motivated by capturing uncertainty in ORL proposed the use of randomized constant priors to increase ensemble diversity (Osband et al., 2018). For each base model, a randomized constant prior is produced, which is simply a network with random initial weights. The base model is trained as an additive component on top of this prior and the final output is the sum of the two. The intuition is that the constant prior should cause ensemble members to disagree more often in unrepresented parts of the state-space, which will provide a better measure of disagreement-based uncertainty.

Given a PCQ $(s,\pi,{\hat{s}},{\hat{\pi}},h)$ query and ensemble of size $M$ we generate a prediction and confidence by first using each ensemble member to generate, via Monte-Carlo simulation, a pair of value estimates of $V^{\pi}(s,h)$ and $V^{{\hat{\pi}}}({\hat{s}},h)$. This results in a set of $M$ value estimate pairs, denoted by $\mathcal{V}=\{(V_{1},{\hat{V}}_{1}),\ldots,(V_{M},{\hat{V}}_{M})\}$. This approach is based on the classic view, from bagging classifiers (Breiman, 1996), of the base learning algorithm being a stochastic function⁵⁵5Indeed, each run of the base algorithm has at least two sources of randomness in our implementation. First, each run uses a different bootstrap sample of the dataset. Second, each run uses randomized initial weights. Third, mini-batches in stochastic gradient descent depend on the random seed. The set $\mathcal{V}$ can then be viewed as value-estimate pairs sampled from the distribution of learning algorithm runs. Bagging analysis tells us that if 50% of the learning algorithm runs result in estimates $(V_{i},{\hat{V}}_{i})$ that correctly rank the values, then a large enough ensemble will correctly predict the query.⁶⁶6This argument assumes independence of the ensemble members, which clearly is not true in practice due to at least correlation between their training data. Based on this view, below we describe the three approaches we consider for producing predictions and confidences from $\mathcal{V}$.

• •

  Ensemble Voting (EV). Following (Dietterich, 2000), EV simply returns a prediction for a query based on the majority vote across the ensemble of $V_{i}<{\hat{V}}_{i}$. The confidence score is equal to the fraction of ensemble members that agree on the majority vote (in the range [0.5,1]), but re-scaled to fall in the range [0,1].

• •

  Paired Confidence Interval (PCI). The PCI confidence value is computed by estimating the expected value of $V-{\hat{V}}$ for a random run of the learning algorithm. The mean estimate is given by $\sum_{i}V_{i}-{\hat{V}}_{i}$ and the prediction is based on the sign of this estimate. The confidence value is based on computing $\alpha$ percentile confidence intervals on the difference, denoted by $[l_{\alpha},u_{\alpha}]$. In particular, it is equal to the largest value of $\alpha$ such that $0\not\in[l_{\alpha},u_{\alpha}]$. Thus, a high confidence value reflects that there is strong evidence that the expected difference is either above or below zero (in agreement with the prediction). Confidence intervals are computed based on the $t$ distribution.

• •

  UnPaired Confidence Interval (U-PCI). This approach makes the prediction in the same way as PCI, but uses unpaired confidence intervals to compute the confidence, which should be expected to be more conservative. In particular, we compute $\alpha$ percentile confidence intervals for the means of the $V_{i}$ and ${\hat{V}}_{i}$ denoted respectively by $\left[l_{\alpha},u_{\alpha}\right]$ and $\left[\hat{l}_{\alpha},\hat{u}_{\alpha}\right]$ and let the confidence be the maximum value of $\alpha$ for which the confidence intervals do not overlap.