acceptodds
Desk rejected at ICLR 2027

Imitation Beyond Expectation via Second-order Stochastic Dominance

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Expected utility theory provides an ordering for policies when the utilities of behavior sequences are given. Many imitation learning methods extend this perspective by seeking policies that match or exceed the utility of demonstrations in expectation, despite the exact utility function only being assumed to be Markovian (and linear). However, this reduces a distribution of demonstrations to its average characteristics, ignoring the distinct characteristics of individual demonstrations that may be important to imitate. We adopt second-order multivariate stochastic dominance, a stricter notion for partially ordering distributions, to guide imitation learning. It broadens the performance guarantees of imitation learning to all non-decreasing and concave utility functions. We investigate both left-sided (i.e., risk-avoidant) and right-sided (i.e., risk-seeking) variants of this stochastic dominance to demonstrate the advantages compared to employing stricter first-order stochastic dominance and other imitation learning baselines.

Primary area:
reinforcement learning
Keywords:
imitation learning, stochastic dominance, reinforcement learning, alignment

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_QUX2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Following previous work on stochastic dominance guarantees for imitation learning, this work focuses on guaranteeing multivariate second order stochastic dominance. SSD is a property of learned policies over the expert demonstrator. This is defined for a given/assumed reward class and using the corresponding feature distributions of the learned and expert policies.

This paper develops an imitation learning algorithm that constructs an imitation policy whose feature distribution satisfies (up to some slackness) SSD over the reference feature distribution. For both left-sided and right-sided SSD, the algorithm is empirically validated over a diverse set of environments, comprising discrete and continuous state/action sets.

Critical strengths
  • this paper is well motivated, clear and well written
  • the proposed method is very simple
  • the algorithm is evaluated on a diverse set of environments
Critical weaknesses
  • The definition of the target distribution is unclear to me. Specifically, the right-hand side of equation 14 has free indices in i and j in the definition of P_target.
  • Proposition 3 and Corollary 4 are given without proof. Recommendation for acceptance can only be given if the results are verifiable.
  • There seems to be a typo in the VaR definition on page 2, where the stated CVaR definition is integrating the right tail. Did you mean to define \operatorname{VaR}_{1-\alpha}(R) = \inf_{t \in \mathbb{R}}\left\{t : \mathbb{P}(R \leq t) \geq \alpha\right\\}?

Minor:

  • the paper is inconsistent on the notation of the target distribution, it uses both P_target and P_trg.
Questions for authors
  • Table 1: it seems that R-SSD does better than L-SSD even for LCVaR objectives. How would you explain this behavior?
  • Table 2: L-SSD is not doing better than FSD for LCVaR metrics. In fact, FSD beats L-SSD on every LCVaR columns. How do you explain this?
  • Are the metrics computed on shared rollouts? In that case, why is it possible to have LCVaR_001 > LCVaR_005 in the first and fourth row of Table 1? Please clarify how the metrics are computed in your work.
Reviewer_XjmuOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduce an inverse RL method that instead of matching expected return, it matches the distributional return using second order stochastic dominance criteria. This paper assumes a feature map, which significantly reduce the complexity of the problem but also adding restriction on its modeling capabilities. Solution method largely follows the reward-policy optimization alternating optimization structure, with a particular interesting use case of a special construction of the advantage like objective to re-weight policy update. Experiments show the proposed approach outperforms baselines in numerous tasks.

Critical strengths
  1. The formulation, and the solution methods are clean and clearly presented. The problem itself is well motivated - we need to model risk sensitive control policies.
  2. The reduction and application of the LP formulation is interesting. Although LP for RL is well known but the slack augmented formulation (together with the structure of the risk aware objective) is very clever and nicely put together.
  3. Experiments show some interesting performance edge over baselines.
Critical weaknesses
  1. Since the author already use the LP formulation, can the author further write in a LP way? The current development largely jump back and forth between LP and imitation, which is very confusing to read. I feel there's some interesting and deep insight here but I cannot see it in the current form.
  2. I do not see how Eq 14 come into play and its implications. Line 250 "Corollary 4. Following from Proposition 3, the random vector of features defined by Ptrg also has second-order stochastic dominance over the demonstrations..." what does this mean?
  3. The way Eq14 come into policy improvement step is mentioned to have resemblance to REINFORCE, and in my opinion somewhat related to AWR and the probability term itself represent some form of the advantage function (correct me if I am wrong). But the paper never dig into this, leaving this unjustified.
  4. Finally for experiments in 4.2-4.3, I do not see the meaning of metric comparison in table 2. Shouldn't we expect all imitation methods imitate the dataset and thus the close performance to the demo the better? I also don't understand table 1-2. For example what does it mean to have maxent-irl with LCVAR?
Questions for authors

see limitations

1 comment

Since the author already use the LP formulation, can the author further write in a LP way? The current development largely jump back and forth between LP and imitation, which is very confusing to read. I feel there's some interesting and deep insight here but I cannot see it in the current form.

The LP is used to obtain a target probability distribution. Then that target probability distribution is used as a training signal to push the imitator's distribution towards the target distribution. For example for left-sided SSD, we use (13) to obtain γ\*\gamma^\* and ϵ\*\epsilon^\*, then construct target probability using (14), and then (15) for optimizing the policy. The role of the LP is to tell us how to construct the target distribution.


I do not see how Eq 14 come into play and its implications. Line 250 "Corollary 4. Following from Proposition 3, the random vector of features defined by Ptrg also has second-order stochastic dominance over the demonstrations..." what does this mean?

The LP in (13) starts with a uniform probability distribution over demonstrations. It transfers probability mass from mixtures of demonstrations to each imitator subject to that imitator being better (component-wise) than the mixture of demos (in other words, dominating that mixture of demos, such that the feature vector is component-wise greater than weighted average of demonstrator feature vectors). If some mass cannot be pushed to imitators, the demonstrator samples keep that mass and that is represented by slack variable ϵj\epsilon_j. The last constraint ensures that sum of mass on each demonstrator, and the mass `transferred' to imitator samples from each particular demonstrator remains 1/M. Minimizing the slack variable ϵj\epsilon_j achieves the goal of pushing as much probability mass as possible to imitators.

The LP gives us the optimal ϵ\*\epsilon^\* and γ\*\gamma^\*. Now Equation (14) comes in. To construct a target distribution, we consider the union of both demonstrator samples and imitator samples. Each of the imitator samples ξi\xi_i get mass ∑jγi,j∗\sum_j\gamma^*_{i,j}, while the remaining mass that remains on demonstrators ξ~j\tilde{\xi}_j is ϵj\epsilon_j. This constructs the target distribution on union of demonstrator samples and imitator samples.

Finally, this target probability is used as a surrogate reward to update policy using Policy Gradient / REINFORCE style update.

We will update Equation (14) in the final version to explicitly clarify the target probability distribution being assigned to both demonstrator and imitator samples.


The way Eq14 come into policy improvement step is mentioned to have resemblance to REINFORCE, and in my opinion somewhat related to AWR and the probability term itself represent some form of the advantage function (correct me if I am wrong). But the paper never dig into this, leaving this unjustified.

Yes the policy improvement is definitely related to REINFORCE but instead of using the true returns of trajectories or rewards of actions; the target probability distribution is used as a policy improvement signal. We note this in the paper on page 5 under equation (15).

Another difference from how REINFORCE is typically used in practice is that we need an entire set of trajectories to compute target probabilities. Hence this `surrogate' reward of target probability mass is assigned at the trajectory-level not at the state-action level.

It is not an advantage function because we do not use a baseline to compute each trajectory's advantage relative to that baseline. Instead, we use the absolute (not relative) target probability of each trajectory.


Finally for experiments in 4.2-4.3, I do not see the meaning of metric comparison in table 2. Shouldn't we expect all imitation methods imitate the dataset and thus the close performance to the demo the better? I also don't understand table 1-2. For example what does it mean to have maxent-irl with LCVAR?

We are working under the premise that demonstrations are not always optimal, and are noisy. So our goal is not to exactly copy the demonstrator, but to outperform them. There are many existing works that aim to do this, under different assumptions of unknown reward functions, or by obtaining ranked preferences of trajectories from the user.

We aim to build an imitator that outperforms the demonstrator for any unknown reward function as long as that reward function is a) monotonically non-decreasing and b) concave with respect to reward features.

In Tables 1 and 2, the column heading names the metric being measured, and the row heading names the algorithm being used. So that particular cell, "MaxEnt-IRL with LCVAR$_{0.01}$" tells us when using MaxEnt IRL what is the value of Left-sided Conditional Value at Risk at α=0.01\alpha=0.01 of rollouts from a policy trained using MaxEnt IRL.


Reviewer_LuwrOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper is inspired by expected utility theory, which sees agents as optimising the expected utility for decision-making. Utility functions take on different forms as a function of features, which depend on the policy. In this case they are features that signal improvement of the policy, and it is important to formulate their aggregation so the utility function is defined appropriately for policy improvement on the task. Previous work proposed first order stochastic dominance, which is based on the CDF. This paper goes a bit beyond that in proposing a second order multivariate statistical dominance, which is based on the area under the curve of the CDF, and which broadens the performance guarantees of imitation learning to all non-decreasing and concave utility functions.The criterion is easier to achieve than first order statistical dominance. There are two algorithms considered, one for left tail emphasis (robustness to worst-case demonstrations), and one for right tail emphasis (outperforming the best-case demonstrations), and in both cases the algorithm works to obtain guarantees for all tail thresholds. Various imitation learning algorithms and FSD are compared on GridWorld, PointBot, and DrivingSim; and across various CVaR criteria generally the best results are obtained by the proposed algorithms.

Critical strengths

Strengths:

  • guarantees for all tail thresholds
  • the algorithm is compared to many baselines and overall seems to be outperforming the rest
  • the baselines are relevant and a number of benchmark environments are included
Critical weaknesses

Weaknesses:

  • the benchmarks are on the small scale so one wonders how scalable the techniques are to large state-action spaces
  • the baselines are pretty dated, all before 2020
  • the theory development is limited for a fundamental ML paper
Questions for authors
  • Abstract: the abstract seems to contradict itself by saying it is stricter while then later saying the first order criterion is stricter.
  • In which sense is the term “second order” used? Is this to be understood as in a distribution over distributions?
  • In the gridworld, why is R-SSD outperforming L-SSD on the left tails?
  • When would we select L-SSD and when would we select R-SSD?
  • Could you compare against some more recent imitation learning baselines, like IQLearn, VAIL, ILDE and GIRIL?
  • Including some more theory development about the guarantees given would be very important

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.