PoRank: A Practical Framework for Learning to Rank Policies

1 Introduction

In 1 many real-world scenarios such as trading [Zhang et al., 2020], advertising [Cai et al., 2023], autonomous vehicles [Shi et al., 2021; Deng et al., 2023b; Deng et al., 2023a], and drug trials [Yang et al., 2023], the task often involves selecting the most promising policy from a set of candidates prior to online deployment. This selection is critical, as online evaluation of each policy can be costly and potentially risky. The conventional approach for policy selection is to estimate the online performance of candidate policies via Off-Policy Evaluation (OPE) [Paduraru, 2013]. OPE requires only off-policy data, which means that we can estimate the performance of a target policy using data generated by other policies.

1 † Corresponding author.

Although OPE is a promising direction, existing OPE methods are still far from reliable in practice. For example, standard Inverse Propensity Scoring (IPS) based estimators such as importance sampling suffer from high variance due to the product of importance weights [Hanna et al., 2019]. Direct Methods (DM) requires extra estimators of environmental dynamics or value functions, which are hard to learn when the observation data is high-dimensional or insufficient. Hybrid Methods (HM) such as doubly robust estimators combine IPS and DM [Jiang and Li, 2016], yet it often comes with additional hyperparameters that need to be carefully chosen.

Fortunately, in many real-world scenarios, we do not need to estimate the exact online performance of candidate policies. Instead, we only care about which policywould perform the best when deployed online. This inspires us to develop a policy ranker focusing on predicting the ranking of target policies regarding to their online performance. Learning such a policy ranker is similar to learning item rankers in recommender systems [Liu, 2009]. However, learning to rank policies faces two unique challenges. First, the policy space could be extremely large, even in simple environments. Therefore, a policy ranker with poor generalization ability would fail to rank unseen policies. Second, unless deployed online, we can hardly know the real performance of the policies, which means that we are lack of ground-truth labels for training the policy ranker. These challenges make it extremely hard to train useful policy rankers in real-world tasks.

In this paper, we propose a novel and practical framework called PoRank for learning to rank policies. PoRank composes of a Policy Comparison Transformer (PCT) and a learning-to-rank (LTR) module, where the PCT aims to learn compact representations of policy pairs and the LTR module focuses on predicting the order of input policies. Instead of directly encoding the raw trajectories to policy representations (as is done in existing works), PCT encodes different behaviors of two policies at the same sates to represent a policy pair. In such a way, PCT successfully extracts the most useful features for policy ranking and significantly improves the generalization over the policy space. The LTR module is built upon the PCT. Conventionally, given two input policies, LTR requires a label to tell which policy performs better. If we can easily obtain such labels, for example in the game environments, we can directly train the policy ranker using supervised learning. However, in many industrial scenarios, obtaining such labels could be very expensive due to deployment cost. To resolve this, we propose a novel crowdsourcing based LTR module, where a set of OPE methods are employed to estimate the policy comparison labels. Specifically, these labels are constructed by comparing the estimated accumulated rewards of the target policies. In such a way, we can easily collect plenty of labels without deploying training policies online. In the experiments, we first demonstrate the advantage of the PCT architecture by comparing it with the state-of-the-art policy ranking network, where both networks are trained using ground-truth labels. Hence, we show that a simple crowdsourcing mechanism could compensate for the lack of ground-truth labels, which makes PoRank practical in many real-world scenarios.

2 RelatedWorks

Off-Policy Evaluation/Selection/Ranking The goal of OPE is to precisely predict the online performance of target policies given trajectory data collected by some other behavior policies. Standard importance sampling approach suffers from exponential variance with respect to the time horizon [Li et al., 2015; Jiang and Li, 2016]. Recent works such as FittedQ evaluation [Hoang et al., 2019] and marginalized importance sampling [Liu et al., 2018] achieve polynomial variance, yet they rely on additional function approximators. Direct methods avoid the large variance by learning the dynamic model or Q-function, which could be biased especially when the data is insufficient. Some works study the offline policy selection problem, yet their methods require running from scratch for each candidate policy [Zhang and Jiang, 2021; Mengjiao et al., 2022]. By contrast, in offline policy ranking (OPR) problem we aim to develop a policy ranker that could directly rank policies. A recent work on OPR collects online performance of a set of policies and uses these labeled data to train the policy ranker [Jin et al., 2022]. However, collecting such data might be extremely expensive in practice.

Learning from Crowds Crowdsourcing systems enable machine learners to collect labels of large datasets from crowds. One big issue with crowdsourcing is that the labels provided by crowds are often noisy [S. and Zhang, 2019]. To tackle this challenge, various probabilistic generative methods are proposed for statistical inference [Yuchen et al., 2016; Tian and Zhu, 2015]. Another line of works use discriminative models that find the most likely label for each instance [Jing et al., 2014; Jing et al., 2015]. A recently work called Crowd Layer (CL) first describes an algorithm for jointly learning the target model and the reliability of workers [Filipe and Pereira, 2018]. CL proposes a simple yet efficient crowd layer that can train deep neural networks end-to-end directly from the noisy labels. In our work, we treat existing OPE methods as workers and adopt CL to process multiple labels due to its simplicity and effectiveness.

Policy Representations Compact but informative representations of policies not only benefit the policy learning process [Tang et al., 2022], but also help with the policy transfer among different tasks [Isac et al., 2019; G. et al., 2017].

A straightforward idea is to represent a policy by its network parameters, yet this leads to a very sparse representation space. Network Fingerprint [Harb et al., 2020] proposes a differentiable representation that uses the concatenation of the vectors of actions outputted by the policy network on a set of probing states. Some recent works try to encode policy parameters as well as state-action pair data into a low-dimensional embedding space [Tang et al., 2022; Jin et al., 2022]. However, existing works focus on single policy representations, which fail to capture the relative discrepancies between different policies.

3 Problem Statement

Markov Decision Process We consider the underlying environment as a Markov decision process (MDP) and define an MDP as a finite-horizon tuple M = (S, A, T , P, R, γ). Here, S is the state space, and A is the action space. T is the length of time horizon. P and R are the transition function and the reward function, respectively. P(st+1|st, at) represents the probability of transitioning from state st to state st+1 ∈ S when the agent takes action at ∈ A under state st ∈ S and R(st, at) represents the immediate reward the agent receives. The expected return of a policy π can be computed by EP [ ∑Tt=1 [γ tR(st, π(st)]], where γ ∈ (0, 1] is the discount factor.

Ranking Policies without Online Deployment The goal of OPE is to estimate the expected return of a policy π without deploying it online, given an offline dataset D = {τ k }Nk=1 , where τ k = (s0, a0, r0, · · · , sT , aT , rT )k are trajectories generated by some behavior policies. OPE is usually used for model selection: We are required to select the most promising policy from a candidate set of available policies before actual deployment. Take recommender systems as example, we can easily obtain a set of candidate policies by adjusting the training data or the hyperparameters of the model. However, we often need to select very few policies from the candidates for online test, since a bad policy would harm the user experience. Therefore, we care more about the ranking of the candidate policies, instead of their exact expected reward. We formally define the off-policy ranking problem as follows.

Definition 1 (Offline Policy Ranking, OPR). Given a set of trajectory data D = {τ k }Nk=1 generated by some behavior policies and a set of target policies Π = {πi}Mi=1 , the OPR problem is to seek a ranking of the target policies that aligns with their online expected accumulated rewards.

Intuitively, OPR is a simpler problem than OPE because we do not care about the exact online performace of the candidate polcies. While OPE as well as off-policy selection (OPS) can also be used to rank candidate policies, they often need to inputrun an estimation procedure from scratch for each candidate policy, thus leading to poor efficiency. In this work, we aim to learn an universal policy ranker that could directly return the ranking results for any input candidate policies.

4 Approach

In this section, we will elaborate our PoRank framework. PoRank borrows the idea from learning-to-rank literature and explicitly solves two unique challenges in ranking policies. Firstly, given the vastness of the policy space, we need an effective policy representation scheme so that the ranking module can accurately comprehend and compare different policies. Secondly, although we can easily generate many policies for training, we can hardly know their actual online performance, therefore we are lack of ground-truth labels for training the ranker. Overall, PoRank consists of a Policy Comparison Transformer (PCT) and a Learning-to-Rank (LTR) module, as shown in Figure 2(a). We will introduce each of them in the following subsections.

4.1 Learning Cross-Policy Representations

Cross-Policy Representation A policy can be considered as a conditional distribution over actions given the state. Therefore, a policy can be naturally represented by a set of state-action pairs where the actions are sampled from the policy. However, such a naive policy representation could be inefficient since the number of state-action pairs can be extremely large. Previous works address this issue by extracting high-level features from the state-action pairs using deep neural networks [Jin et al., 2022]. Although these representations reflect the features of single policies, they fail to capture the discrepancies of different policies at some crucial states.

To this end, we aim to learn cross-policy representations by comparing two policies' decisions at the same set of states. Formally, given a set of states {s1, ..., sK} and two policies πi , πj , we can construct the following sequence of stateaction pairs by taking actions at these states:

where ai ∼ πi (·|s), and aj ∼ πj (·|s). We denote by χi≻j = g(ξ i≻j ) ∈ Rn the cross-policy representation where g is a function that maps ξ i≻j to an n-dimensional representation space. Figure 2(a) shows the computation of cross-policy representations. By contrast, Figure 2(b) shows the computation of single-policy representations, which is adopted in [Jin et al., 2022]. Intuitively, cross-policy representations focus on encoding the discrepancies between policies, while single-policy representations only encode features of single policies. Thus, cross-policy representations are more effective for downstream learning-to-rank tasks.

PolicyComparisonTransformer (PCT) Transformers are proved to be effective for learning dependencies between different positions in sequences. Prior works has employed transformers to extract features from trajectory sequences [Lili et al., 2021; Michael et al., 2021]. However, existing transformer architectures fail to capture the differences of two policies' decisions. In our work, we propose the PCT architecture to learn cross-policy representations. Unlike previous works where the positional encodings indicate the positions of state-action pairs in a trajectory, PCT uses positional encoding to distinguish the relative order of two policies. In this way, the learned cross-policy representation χi≻j can be directly used to predict whether πi performs better than πj .

Figure 1 shows the construction of input tokens. We first sample K states from D and then use a linear encoder f to map the K state-action pairs into 2K tokens:

where i and j represent the indexes of two policies. In order to represent the relative order of πi and πj , we introduce two one-hot positional encodings e+ = [1, 0] and e- = [0, 1], where e+ indicates the policy ranked higher and e- indicates the policy ranked lower. We also use an aggregation token e0, which is a learnable vector for aggregating the information from the other 2K tokens [Zhu et al., 2021]. The final inputs that indicate πi ranked higher than πj can be represented as:

This construction of inputs has two advantages. First, the two policies share the same set of states, thus their discrepancies are naturally represented by the different actions taken at these states. Second, we can easily get a mirrored representation zj≻i by simply exchange the positional encoding eα and eβ used in zi≻j .

We adopt a widely used transformer architecture as our encoder [Dosovitskiy et al., 2021]. It contains L alternating layers of multi-head self-attention (MSA) and multi-layer perception (MLP) blocks. Layernorm (LN) and residual connections are applied to the outputs of each block. For brevity, we rewrite the inputs in Equation 3 as z(0) . And the computations at each block can be represented as:

The final cross-policy representation χi≻j is the corresponding outputs of the aggregation token e0 taken from zL. Note that χi≻j changes to χj≻i when we exchange the positional encodings e+ and e-, but they are permutation invariant to the order of inputted state-action pairs.

4.2 Learning to Rank Policies

In this section, we will introduce how to train the PCT in two cases regarding to the existence of ground-truth ranking labels of policies. First, we show that the policy ranking problem can be reduced to a binary classification problem since our cross-policy representations can be directly used to predict the ranking of two policies. Second, we will introduce a learning paradigm where multiple OPE methods are modeled as label providers. We will also show how to train the PCT leveraging the inaccurate labels provided by the workers.

Reducing OPR to Binary Classification We first consider the case when there is a training set Π = {(πi , Ri )}Ti=1 consisting of T deployed policies πi as well as their real expected accumulated rewards Ri . In this case, we can directly construct binary labels by comparing the performance of the two

%& %(

%+

%& %(

Figure 1: Generation of input tokens.

a

Figure 2: Comparison between Cross-Policy Representation (left) and Single-Policy Representation (right).

policies. We use an indicator 1Ri>Rj to represent the label of a pair of policies (πi , πj ). The PCT can be trained by minimizing the following binary cross entropy loss:

where ˆ yi≻j = sigmoid(ϕ(χi≻j )) represents the predicted probability that πi performs better than πj . ϕ is a function that projects χi≻j to a real number. The final ranking of test policies is based on their scores computed by:

which can be interpreted as the expected probability that πi performs better than other test policies [Rodrigo et al., 2019].

Figure 3 shows the framework of the Learning-to-rank module. In the presence of ground-truth label yi>j, the LTR module is simplified to Situation 1. Otherwise, we will rely on OPE workers to provide supervision signals. Situation 2 will be illustrated bellow.

Learning from OPE Workers Supervised training is efficient when the dataset Π = {(πi ,Ri )}Ti=1 contains enough policies. Unfortunately, collecting such training data can be extremely expensive in many real applications. Meanwhile, we note that although existing OPE methods are not robust enough, they actually provide candidate solutions to the OPR problem. To this end, we borrow ideas from crowdsourcing domain as an alternative way to approach the OPR problem. Specifically, suppose that there exists a set of OPE algorithms estimating the policy performance, we can employ them as crowd workers to generate possibly inaccurate labels and make use of these labels to train our models. The intuition is that the inaccurate labels generated by OPE workers are implicitly conditioned on the ground-truth performance of policies. If we can take advantage of these labels and learn their relationships with the ground-truth labels, our prediction ˆ yi≻j would be more close to the ground-truth labels.

In the framework of PoRank, we adopt Crowd Layer (CL, [Filipe and Pereira, 2018]) as our backend for learning from crowd labels. CL is able to automatically distinguish the good from the unreliable workers and capture their individual biases in many other domains, such as image annotation [Guan et al., 2018; Li et al., 2022] and music genre classification [Rodrigues et al., 2013]. In addition, CL is naturally compatible with deep learning approaches since it simply adds a crowd layer to the deep neural networks and can be trained in an end-to-end way. As shown in Figure 2, we add CL to the top of our predicted probability ˆ yi≻j . During training, CL adjusts the gradients coming from these noisy labels according to its reliability by scaling them and adjusting their bias. The adjusted gradients are then backpropagated to PCT according to the chain rule.

Formally, assume that there are W workers of OPE methods. For each worker wm, its estimation about the expected return of πi is denoted as Rim. The goal of CL is to train a mapping function ˆ ym i≻j = ζ m(ˆ yi≻j) to predict the noisy binary label generated by worker wm: ym i,j = 1Rim>Rjm . The overall objective can be written as:

The complete training procedures of PoRank is summa-

%+

#&' #(' #)'

#&* #(* #)*

rized in Appendix. In practice, to reduce the computational cost brought by CL, we set ζ m as a linear projection followed by a sigmoid function. Therefore, the number of additional parameters only grows linearly with the number of workers. Note that the CL is only available during training since we still use ˆ yi≻j to generate the predicted ranking of policies.

5 Experiments

In this section, we compare PoRank with widely-used OPE methods on various tasks. We present ablation studies with respect to PCT and CL, which are the main components of PoRank. Note that hyper-parameter selection and more experimental results can be found in Appendix.

5.1 Experimental Settings

Trajectory Set We evaluate PoRank and all baseline OPE methods on D4RL dataset consisting of various trajectory sets [Fu et al., 2020]. Overall, we adopt trajectory sets collected from 2 environments of Mujoco games: HalfCheetah-v2 and Walker2d-v2. Besides, there are 3 different types of trajectory sets for each environment: expert, full-replay and medium. The difference between them is that the behavioral policies collecting these 3 types of trajectories show different performance. And these behavioral policies are trained by the Soft Actor-Critic (SAC) algorithm online [Haarnoja et al., 2018].

Policy Set To evaluate the abilities of all methods to correctly rank policies. We use the policy set released by [Jin et al., 2022] . For each trajectory set mentioned above, there are 2 types of policy sets ( referred as Set I and Set II) in which the expected return of policies are evenly spaced in the performance range of them. As mentioned in [Jin et al., 2022], Set I and Set II aim to simulate two kinds of OPE cases. The policies contained in Set I are trained by offline RL algorithms (CQL [Kumar et al., 2020], BEAR [Kumar et al., 2019], CRR [Wang et al., 2020]) and show diverse behavioral performance. This is aligned with practical cases where the sources of policies are diverse and unknown. Set II contains policies trained by SAC, which is the same as the algorithm of training the behavioral policies. Therefore, Set II corresponds to the practical OPE cases in which the target policies share many common properties with the policies generating the trajectory data.

Baselines 2 We compare PoRank with six state-of-theart baselines. i) Fitted Q-Evaluation (FQE [Hoang et al., 2019]). It is a value-based OPE method, which learns a neural network to approximate the Q-function of the evaluated policy by temporal difference learning on the trajectory set. ii) Model-based estimation (MB [Paduraru, 2013]). It learns the dynamics model of environment, and estimates the expected return of evaluated policies by computing their average returns of Monte-Carlo rollouts in the model environment. iii) Weighted importance sampling (IW [Mahmood et al., 2014]). It leverages weighted importance sampling to correct the weight of the reward, regarding the collected trajectory data distribution to the data distribution of the evaluated policy. iv) DualDICE [Nachum et al., 2019]. It also aims to achieve distribution correction yet without directly using importance sampling. It learns an estimation of the state-action stationary distribution for achieving distribution correction. v) Doubly Robust (DR [Jiang and Li, 2016]). It utilizes an unbiased estimator that leverages an estimated environment model to decrease the variance of the unbiased estimates produced by importance sampling techniques.

Worker Set In all experiments, we use 15 models trained by 5 OPE methods mentioned above ( IW, MB, DR, DualDICE, and FQE, each trained 3 models with different seeds) as our OPE workers. We present the architecture details for them in Appendix.

Evaluation Metrics We evaluate all models according two widely-used metrics. i) Spearman's Rank Correlation. It is the Pearson correlation between the ground truth rank sequence and the evaluated rank sequence of the evaluated policies. So, a higher rank correlation indicates a better policy ranker. ii) Normalized Regret@k. It is the normalized difference between the actual value of the best policy in the policy set, and the actual value of the best policy in the estimated top-k set. Mathematically, it can be computed by regret@k = Vmax-Vtopk Vmax-Vmin , where Vmax and Vmin is the expected return of the best and the worse policies, respectively, in the entire set, while Vtopk is the estimated top k policies. So, a lower regret value indicates a better policy ranker.

2 We leverage a popular implementation of OPE algorithms: https://github.com/google-research/google-research/tree/ master/policy eval. It contains the first 5 baselines used in our paper

5.2 Experimental Results

ComparisonwithOtherOPEBaselines We evaluated PoRank against five baseline methods in two environments. Figure 1 presents the rank correlation and regret@1 values of the estimated rank sequences generated by each model.

Our results demonstrate that PoRank consistently outperforms the baseline methods. Specifically, PoRank achieved the highest rank correlations in 11 of the 12 policy sets and the lowest regret@1 values in 7 sets. This indicates PoRank's capability to deliver robust and effective performance across diverse policy scenarios.

Notably, PoRank excels in learning from noisy labels generated by other OPE workers. In our experiments, the OPE workers, which generate these noisy labels for PoRank, were directly sampled from the trained models of the baselines. For instance, in the Set I of the expert trajectory set in HalfCheetah-v2, while all OPE baselines exhibited poor performance , PoRank achieved a high rank correlation of about 0.65-despite relying on these low-quality labels. We attribute this resilience to two key factors: i) The Policy Comparison Transformer (PCT) in PoRank effectively mitigates the biases of inaccurate workers. ii) The crowd layer adeptly distinguishes reliable OPE workers from unreliable ones and adjusts for their individual biases. In conclusion, PoRank demonstrates highly effective and robust OPR results across a variety of policy sets. It effectively reduces the biases induced by OPE workers, thereby outperforming these workers significantly.

Comparing withOther Label AggregationMethods We propose to use PCT and crowd layer to aggregate the information of multiple OPE workers. There are also other simple mechanism to aggregate worker information. For example, ranking policies by the average score of workers (denoted by Average) or ranking policies by the number of worker votes (denoted by Major Voting).

Actually, the superiority of CL over these baslines has been demonstrated in [Filipe and Pereira, 2018]. However, it is still valuable to reproduce this superiority in the context of OPR. Specifically, we report the rank correlations in the following Table 2. We can see from the first four columns that our method dominates these two baselines in all of the six environements. Note that the framework of PoRank can also combine with more advanced crowdsourcing methods other than CL. On the other hand, the line of works in rank aggregation, focusing on aggregating a set of pairwise comparisons into a ranking list. Therefore, we use a more recent and simple RA method [Maystre and Grossglauser, 2017] (denoted by RA) to replace Equation 6 in our work. From the last two columns we can see that this method indeed further improves PoRank in some evironments. However, this does not contradicts to our main contribution: modeling the OPR problem from the perspective of crowdsourcing.

Selection of the Batch Size of State-Action Pairs In the training phase, the batch size of state-action pairs feeded into the Transformer is an important hyper-parameter in our model. It play the role in balancing the computational cost and the performance. We chose the number 256 as the batch size. This choice is supported by the experimental results reported in Table 3, which show the averaged rank correlations of our model with the batch size growing. We can find that when the batch size is larger than 256, the performance of our model tends to be stable.

Ablations We conducted ablation studies to evaluate the importance of each component in our framework, using the same policy sets as the primary experiments. The results are depicted in Table 4. In our framework, termed PoRank, we integrate two key components: the Policy Comparison Transformer (PCT) for generating cross-policy representations, and the Crowd Layer (CL) that aggregates information from OPE workers. This integration allows PoRank to rank policies without requiring additional ground truth labels. We compared PCT with CL (PoRank) against three different ablations: i) PCT with GL: This model uses our PCT architecture but discards the CL, relying on extra ground truth labels (GL) for training. It is trained using additional sets of deployed policies released by [Jin et al., 2022]. Without CL, it lacks the capability to learn from OPE workers. ii) SOPR-T with GL: [Jin et al., 2022], a transformer-based model designed to learn individual policy representations. Unlike PCT, SOPR-T does not focus on capturing the differences between policies at the decision level. Like PCT with GL, it also requires extra ground truth labels for training. iii) SOPR-T

with CL: This variation of SOPR-T attempts to learn from OPE workers by incorporating the CL, similar to PoRank, but does not require additional supervised information from deployed policies.

As shown in Table 4, PCT with CL outperforms SOPR-T with CL on 8 policy sets, while PCT with GL surpasses SOPR-T with GL on 8 policy sets. This suggests that our cross-policy representation, which aims to discern the nuanced decision differences between policies, exhibits stronger representational power compared to singlepolicy representations used by SOPR-T. Moreover, PCT with CL (PoRank) and SOPR-T with CL both demonstrate competitive performance against their counterparts PCT with GL and SOPR-T with GL, despite the absence of additional supervised information from deployed policies. This underscores the effectiveness of using the CL to learn from OPE-generated noisy labels when extra policies providing supervised labels are not readily available.

6 Conclusions

In this study, we introduced PoRank, a novel framework designed to learn robust off-policy rankers from a set of unreliable off-policy estimators. Unlike existing approaches that require the deployment of policies online for gathering supervision signals, PoRank innovatively leverages labels generated by existing Off-Policy Evaluation (OPE) methods. This feature significantly reduces the training cost of the ranker. Our theoretical analysis elucidates the relationships between a worker's bias, variance, and overall quality. We further contribute a unique Policy Comparison Transformer (PCT) architecture, developed to discern the relative discrepancies between policies through effective cross-policy representations. Empirical results confirm PoRank's superior performance over baseline models across diverse tasks and policy sets. Importantly, PoRank demonstrates excellent generalizability across various policy sets. Our ablation studies further validate the effectiveness of each individual component within the PoRank framework.

Acknowledgments

This research is supported by the National Research Foundation, Singapore under its Industry Alignment Fund - Prepositioning (IAF-PP) Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.