Reinforcement learning commonly exhibits non-monotonic performance dynamics in single-task settings. During learning, a sequence of policies is generated whose true performance is unknown and may oscillate significantly across iterations. Despite this well-known phenomenon, standard experimental practice typically reports either the final visited policy or the best among periodically evaluated ones, implicitly assuming that these selection criteria reliably approximate the best-performing policy visited throughout the entire sequence. In this work, we present an empirical study on the implications of non-monotonicity for policy selection in single-task policy-based reinforcement learning. We introduce post-hoc diagnostic metrics to characterize performance degradation and assess the accuracy and efficiency of different selection criteria. These metrics allow us to evaluate commonly used selection strategies across standard continuous-control benchmarks using a well-established on-policy actor-critic method. Our results show that, in this representative experimental setting, widely adopted selection practices can deviate considerably from the best policy encountered during learning, leading to underperforming estimates and suboptimal use of computational resources. As an alternative, we recommend a validation-based policy selection strategy constrained by computational cost, which provides a more consistent and accurate approximation of the best visited policy while improving selection efficiency. Overall, our findings highlight policy selection as an underexplored factor in the evaluation protocols of reinforcement learning and motivate further study on explicit and standardized validation-based selection procedures.
Figures & tables
Algorithm 1 Interaction-based STPO process
Figure 1: The box on the left summarizes the well-known conditions of the learning processes resulting from interaction-based STPO, along with the open questions left by the black-box use of RL libraries in experimental practice. The box on the right illustrates the contribution of our experimental study focused on selection in RL, which analyzes the reliability of commonly used selection criteria by quantifying performance degradation ( δt ), selection accuracy ( αt ), and selection efficiency ( εt ), across different possible scenarios.
Figure 2: Examples of degradation δt (see Equation 9 ) at different iterations, over 100 synthetic iterations of policy return.
Figure 3: Examples of selection accuracy αt (see Equation 10 ) for two different selections, over 100 synthetic iterations of policy return.
Figure 4: Examples of selection efficiency εt (see Equation 11 ) for two different selections, over 100 synthetic iterations of policy return.
Figure 5: Characterization of the regions according to Equation 12 across four different cases, with 100 synthetic iterations of the policy return and a window size of w=10 . From left to right: a and b determined by the statistical condition in A and B ; a and b imposed by the minimum size condition; a truncated not to exceed tmax ; and b truncated to ensure a well-defined interval [a,b] with a minimum length of 10%.
Figure 6: On the left, distributions of degradation in each region for each environment shown as a color-coded histogram with medians in red. In the centre and on the right, distributions of accuracy and efficiency respectively for each selection criterion, with the interquartile range and the median. See Appendix G.1 for details on figure construction.
E
Engine
∣S∣
∣A∣
Median δ
LLC
Box2D
8
2
0.02
BW
Box2D
24
4
0.10
S
MuJoCo
8
2
0.12
H
MuJoCo
11
3
0.23
A
MuJoCo
27
8
0.30
HC
MuJoCo
17
6
0.32
Table 1: Environments ordered according to the median degradation across 30 policy sequences, together with their characteristics related to the physics simulation complexity. This ordering is used consistently across all figures in the analysis.
Metric
Criterion
Low
Middle
High
α
last
1
0
20
train
1
0
20
validation
0
0
21
ε
last
4
11
6
train
3
6
12
validation
0
2
19
Table 2: Count of environment-region cases where median accuracy ( α ) or efficiency ( ε ) over 30 policy sequences falls within the low [0,0.25) , middle [0.25,0.75) , or high [0.75,1] ranges.
Figure 7: Scatter plots of median degradation, δ , versus selection accuracy, α , (first row) and efficiency, ε , (second row) for the different selection criteria (distinct markers), across regions (colors) and environments (columns). See Appendix G.1 for details on figure construction.
Figure 8: Proportion of times each criterion outperforms the other in pairwise comparisons by region, with ties in white. Dashed vertical lines highlight the proportions 0.25, 0.5, and 0.75. See Appendix G.2 for details on figure construction.
Figure 9: Pairwise comparison of selection criteria across degradation levels for different environments and regions. For each environment-region pair, rows correspond to compared criterion pairs and columns to degradation intervals. Color intensity encodes both win proportions (within each cell) and the number of comparisons (across cells) via joint normalization, while markers indicate median degradation values for each criterion. See Appendix G.2 for details on figure construction.
Case
Initialization
Learning
Convergence
All regions
Low
Middle
High
Low
Middle
High
Low
Middle
High
Low
Middle
High
train wins last
0.33
0.41
0.62
0.33
0.57
0.80
0.58
0.68
0.90
0.44
0.61
0.80
validation wins last
0.55
0.89
0.99
0.56
0.94
1.00
0.81
0.97
1.00
0.66
0.95
1.00
validation wins train
0.62
0.86
0.96
0.69
0.88
0.91
0.86
0.88
0.91
0.75
0.88
0.92
Table 3: Proportion of pairwise wins between selection criteria across learning regions (initialization, learning and convergence) and degradation ranges (low, middle and high).
Appendix figures & tables22 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 10: Evolution of the absolute differences between the ground truth and the empirical estimators of validation criteria across the policies in the generated sequences for each environment (by column) and for 5 different seeds (by row). Six curves are shown, corresponding to different numbers of episodes κ used for the estimation, where darker curves indicate a larger number of episodes considered.
∣D∣
LLC
BW
S
H
A
HC
W2d
5
0.835 ± 0.063
0.892 ± 0.063
0.974 ± 0.030
0.978 ± 0.021
0.922 ± 0.037
0.898 ± 0.068
0.952 ± 0.034
25
0.927 ± 0.039
0.944 ± 0.033
0.992 ± 0.011
0.992 ± 0.007
0.978 ± 0.011
0.969 ± 0.028
0.986 ± 0.014
50
0.950 ± 0.027
0.961 ± 0.025
0.997 ± 0.004
0.996 ± 0.004
0.988 ± 0.007
0.983 ± 0.016
0.992 ± 0.008
100
0.966 ± 0.023
0.975 ± 0.018
0.999 ± 0.002
0.997 ± 0.003
0.993 ± 0.004
0.990 ± 0.010
0.995 ± 0.005
250
0.980 ± 0.014
0.984 ± 0.011
0.998 ± 0.003
0.999 ± 0.002
0.996 ± 0.002
0.995 ± 0.005
0.998 ± 0.003
500
0.986 ± 0.010
0.987 ± 0.009
0.999 ± 0.002
0.999 ± 0.001
0.997 ± 0.001
0.996 ± 0.004
0.998 ± 0.002
Appendix
Table 4: Spearman rank correlation between policy rankings obtained using 500 initial states and those obtained using smaller independent subsets of initial states, averaged across the 30 policy sequences for each environment. Values are reported as mean ± standard deviation. Gray cells indicate the smallest subset size for which the mean correlation minus one standard deviation exceeds 0.95.
Figure 11: Evolution of the absolute differences between the ground truth and the empirical estimators of train (orange) and validation (green) criteria across the policies in the generated sequences for each environment (by column) and for 5 different seeds (by row). Six curves are shown per criterion, corresponding to different numbers of episodes κ used for the estimation, where darker curves indicate a larger number of episodes considered. The validation curves coincide with those shown in Figure 10 .
Figure 12: Evolution of the ground-truth episodic return (black curve) and empirical return estimates from training trajectories (orange curve for the train criterion) and validation episodes (green curve for the validation criterion) across five different policy sequences for each environment.
Algorithm 2 On-policy STPO with last
Algorithm 3 On-policy STPO with train
Algorithm 4 On-policy STPO with validation
Algorithm 5 On-policy STPO with cost-drive validation
E
Train default κ
Validation default κ
Validation default φ 10000 steps ≈ iter.
Train selected κ
Cost-driven validation selected (κ,φc)
LLC
100
5
10
50
(5,0.2)
BW
5
S
10
H
20
A
5
HC
20
Appendix
Table 5: Default and selected configurations for the train and validation criteria across environments.
Figure 13: Distribution of selection accuracy for different configurations of the train and cost-driven validation criteria across environments and regions. Each distribution is represented by its interquartile range, with the median marked within it. The most accurate configurations overall across all regions and environments are highlighted in red, those that are most accurate for each individual environment are highlighted in yellow, and the default configurations are highlighted in grey.
Figure 14: In each plot, the ground truth (first row), the average length of generated episodes (second row), and the validation-to-learning cost ratio per iteration (last six rows) for the policies in a sequence generated under each environment.
Figure 15: Boxplots of the validation-to-learning cost ratio for the default validation criterion across the 30 generated learning processes, considering different validation periods (rows) and numbers of validation episodes (columns within each plot), for each environment (columns). The green band highlights the admissible validation-to-learning cost ratio range between 0 and 0.2, while the blue boxes in the corresponding columns show the interquartile range and median of the selection accuracy.
Figure 16: Boxplots of the validation-to-learning cost ratio for the cost-driven validation criterion across the 30 generated learning processes, considering different cost thresholds (rows) and numbers of validation episodes (columns within each plot), for each environment (columns). The green band highlights the range delimited by the corresponding cost threshold, while the blue boxes in the matching columns show the interquartile range and median of the selection accuracy.
Figure 17: Evolution of the validation-to-learning cost ratio for the cost-driven validation criterion across the 30 learning processes, considering different cost thresholds (rows) and numbers of validation episodes (different curves), for each environment (columns). Red markers above each plot indicate iterations in which at least one exceedance of the predefined validation-to-learning cost threshold occurred.
Figure 18: In the first and last columns, strip plots of validation-to-learning cost ratios truncated at 1 and accuracies across the 30 policy sequences per environment, together with the interquartile range and median in red. In the central column, the median percentage of validated policies, together with the interquartile range in red.
Figure 19: Validated policies (marked in black) throughout the 30 policy sequences (one row per sequence in each plot) using the cost-driven validation criterion across the different environments.
E
Ta⋅100
Tb⋅100
LLC
9.78±0.00
85.33±9.20
BW
14.49±8.28
70.52±21.48
S
9.81±0.00
70.02±23.01
H
12.3±5.01
31.48±23.04
A
16.58±2.50
79.69±10.58
HC
10.79±3.62
68.44±19.74
Appendix
Table 6: Mean and standard deviation of the percentage of the learning start and convergence start with respect to the total execution horizon for each environment, considering the 30 policy sequences generated in each case.
Figure 20: Evolution of the ground truth (blue curve) across the generated sequences for each environment (by column) and for 5 different seeds (by row), together with the start of learning (red line) and convergence (black line), which delimit the three regions. Above each curve, the evolution of degradation is shown along the sequence, where darker values indicate higher degradation.
Figure 21: For each environment (columns) and selection criterion (rows), application of successive halving to the 30 policy sequences represented as learning curves. Each curve shows the ground-truth return of the best policy identified by the corresponding selection criterion. Red vertical lines indicate successive elimination stages, where half of the surviving processes are discarded according to the estimated return of their currently selected best policies 7 7 7 For the last criterion, which does not rely on return estimates, elimination decisions are based on the default train estimator applied to the last policy of each surviving sequences, using the most recent κ=100 episodes generated during learning. .
Figure 22: Distribution of evaluations allocated by successive halving across different policy return levels for each environment and selection criterion. The observed return range is partitioned into three regions (low, middle and high) using 25% and 75% of the maximum observed return as thresholds. Histograms show the proportion of evaluations assigned to policies within each return range. The black bars correspond to the ideal resource-allocation distribution obtained using ground-truth policy return, while the coloured bars show the distributions induced by each selection criterion. Deviations from the reference distribution indicate differences in how computational resources are allocated across low, medium, and high performing policies.
Figure 23: Tracking accuracy of successive halving under different selection criteria, computed across 30 policy sequences per environment. For each environment (columns) and selection criterion (rows), segments show the interquartile range and markers indicate median of the tracking accuracy defined in Equation 13 .
Figure 24: Trade-off analysis between Resource Allocation (RA) efficiency and best-policy tracking accuracy as a function of the cost threshold φc . In the top row, differences in the distribution of evaluations across low, medium, and high return ranges after applying successive halving, measured relative to the ground-truth allocation. In the bottom row, the distribution of tracking accuracy for each value of φc , showing interquartile range and median in red.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.
Joseph Lazzaro, Alessio Russo, Aldo Pacchiano
Imperial College London · Boston University · Broad Institute of MIT and Harvard
Real-world decision-making often requires optimizing multiple competing objectives simultaneously. In reinforcement learning (RL), this is typically addressed by combining reward signals into a single scalar objective via a scalarization function, which can be fragile: small changes in the weights can induce drastically different policies. Multi-objective reinforcement learning (MORL) instead produces sets of policies that explicitly represent trade-offs between objectives. However, these policies are typically presented to the decision maker only through their value vectors, which can obscure substantial behavioral variation: policies that induce distinct trajectories may appear indistinguishable when evaluated solely by expected returns. We propose an exploratory diagnostic workflow that automatically highlights behavioral variation along the Pareto front that objective values alone do not reveal, providing both quantitative and visual tools to support policy inspection. We validate our approach on simple grid examples and scale it to continuous control benchmarks, demonstrating that it remains effective as problem complexity increases.
Antonio Mone, Zuzanna Osika, Florian Felten +4
Delft University of Technology, the Netherlands · ETH Zurich, Switzerland & herve.review, Belgium · ETH Zurich, Switzerland
Many reinforcement-learning (RL) problems are non-stationary yet structured and can be decomposed into phases, each with its own transition probabilities and reward functions. When the phase sequence is known, the common solution augments the state with information to satisfy the Markovian property and applies standard RL techniques. However, prior work finds that the multi-policy approach for different phases can outperform a single state-augmented policy shared among the phases, for reasons that remain unclear. In this work, we first show that the shared policy can theoretically achieve performance of any multi-policy solution. However, whether a multi-policy solution can perform better than the corresponding single shared policy in practice depends on function approximation, learning and optimization processes, as well as, for multi-policy solutions, the sample efficiency and loss of continuity from one policy to another. We propose a regime-based phase decomposition method to identify which policy can provide better performance. The method is based on consideration of the duration of transient system dynamics relative to the duration of the quasi-stationary period. Numerical experiments are conducted with different non-stationary RL problems to validate our four major hypotheses: (a) longer phase durations favor multi-policies, (b) the heterogeneity between phases increases the burden on single policy, (c) multi-policies need sufficient data for each phase, and (d) environment-specific transition dynamics between phases can affect which policy is preferable.
Guilhem Loussouarn, Nancy Nayak, Kin K. Leung
Department of Electrical and Electronic Engineering Imperial College London, UK