Imitating Past Successes can be Very Suboptimal
Authors: Benjamin Eysenbach
Soumith Udatha
Ruslan Salakhutdinov
Sergey Levine
Venue: NeurIPS 2022 Accept (2022)

Abstract: Prior work has proposed a simple strategy for reinforcement learning (RL): label experience with the outcomes achieved in that experience, and then imitate the relabeled experience. These outcome-conditioned imitation learning methods are appealing because of their simplicity, strong performance, and close ties with supervised learning. However, it remains unclear how these methods relate to the standard RL objective, reward maximization. In this paper, we prove that existing outcome-conditioned imitation learning methods do not necessarily improve the policy. However, we show that a simple modification results in a method that does guarantee policy improvement. Our aim is not to develop an entirely new method, but rather to explain how a variant of outcome-conditioned imitation learning can be used to maximize rewards

Imitating Past Successes can be Very Suboptimal
Benjamin Eysenbach
Soumith "
Sergey Levine Ruslan Salakhutdinoy
CCrnneiee Mellon University beysenbadcs. cmu. edu
PUC Berkeley
Abstract
Prior work has proposed simple strategy for reinforcement learning (RL): label experience with the outcomes achieved in that experience, and then imitate the relabeled experience. These outcome-conditioned imitation learning methods are appealing because of their simplicity, strong performance, and close ties with supervised learning. However, it remains unclear how these methods relate to the standard RL objective, reward maximization. In this paper, we formally relate conditioon imitation learning to reward maximization, drawing precise relationship between the learned policy and Q-values and explaining the close connections between these methods and prior EM-based policy search methods. This analysis shows that existing outcome- cindimee-onditioondd imitation learning methods not necessarily improve the policy, but a simple modification results in a method that does guarantee policy improvement, under some assumptions.
Introduction
Recent work has proposed methods for reducing reinforcement learning (RL) supervised learning
problem using hindsight relabeling [1, 5, 9, 11, 25, 31]. These approaches label each state action pair with an outcome that happened in the future (e.g., reaching a goal), and then learn conditional policy by treating that action optimal for making that outcome happen. While most prior work defines outcomes as reaching goal states [5, 9, 25, 28, 31, 37], some work defines outcomes in terms of rewards [3, 14, 30]. language [19, 23], or sets of reward functions [7, 16]. We will refer to these methods as nutcome-conditioos
behavioral cloning (OCBC).
OCBC methods are appealing because of their simplicity and strong performance [3, 6. 9]. Their implementation mirrors standard supervised learning problems. These methods do not require learning value function and can be implemented without any reference to a reward function. Thus, OCBC methods might preferred over more standard RL algorithms, which are typically challenging to implement correctly and tune [10].
However, these OCBC methods face major challenge: it remains unclear whether the learned policy is actually optimizing any control objective. Does OCBC correspond to maximizing some reward function? If not, can be mended such that it does perform reward maximization? Understanding the theoretical underpinnings of OCBC is important for determining how to correctly apply this semmingy--appellng class of methods. It is important for diagnosing why existing implementations can fail to solve some tasks [13, 25], and is important for predicting when these methods will work effectively. Relating OCBC reward maximization may provide guidance on how to choose tasks and relabeling strategies to maximize a desired reward function.
The aim of this paper is understand how OCBC methods relate reward maximization. The key idea in our analysis to decompose OCBC methods into a two-step procedure: the first step corresponds averaging together experience collected when attempting many tasks, while the second step reweights the combined experience by task-specific reward functions. This averaging step is equivalent taking a convex combination of the initial task-conditioned policies, and this averaging
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

can decrease performance on some tasks. The reweighting step, which is similar to EM-based policy search, corresponds to policy improvement. While EM-based policy search methods are guaranteed to converge, we prove that OCBC methods can fail to converge because they interleave an averaging step. Because this problem has to do with the underlying distributions, it cannot be solved by using more powerful function approximators or training on larger datasets. While prior work has also presented failure cases for OCBC [25], our analysis provides intuition into when and why these failure cases arise.
The main contribution of our work is an explanation of how salcomee-cnniiioons behavioral cloning relates to reward maximization. We show that cuttoome-conditions behavioral cloning does not, in general, maximize performance. In fact, it can result in decreasing performance with successive iterations. However, by appropriately analyzing the conditional probabilities learned via outcome- conditioned behavioral cloning, we show that simple modification results method with guar- anteed improvement under some assumptions. Our analysis also provides practical guidance on applying OCBC methods (e.g., should every state be labeled as a success for some task?).
2 Preliminaries
We focus on a multi-task MDP with states 8 E S, actions E A', initial state distribution po (8)), and dynamics p(8++1 8t, 4z). We use a random variable e E E to identify each task; e can be either continuous or discrete. For example, tasks might correspond to reaching a goal state, so E = S. At the start of each episode, task (e) is sampled, and the agent receives the tpsk-specific reward function re (St, a.) E [0, 1] this episode. We discuss the single task setting in Sec. 3.4. We use (a 8, e) to denote the policy for achieving outcome e. Let r _ (8o, ag 81, (i,...)) be an infinite length trajectory. We overload notation and use <( | e) as the probability of sampling trajectory т from policy x(a s, e).. The objective and Q-values are:
max Bpt(e) En(r)))
Σ Errlasnnaii
Qu(hie A En(rle)
Σ E''ross as A=
(1)
Because the state and action spaces are the same for all tasks, this multi-task task RL problem is equivalent to the multi-objective RL problem [17, 20, 36). Given a policy x(a s,e) and its corresponding
Q-values Qu((-l:ee, policy improvement is procedure that produces new policy n' ra(a s,e) with higher average Q-values:
(rle) (s. > Ex(le) (s, a,
for all states s.
Policy improvement is most often implemented by creating a new policy that acts greedily with respect to the Q-function, but also be implemented by reweighting the action probabilities of the current policy by (some function of) the Q-values [8, 22, 27]. Policy improvement guaranteed to yield a policy that gets higher returns than the original policy, provided the original policy is not already optimal [32]. Policy iteration alternates between policy improvement and estimating the Q-values for the new policy, and is guaranteed to converge to the weward-maximizing policy [32].
2.1 Outcome-Conditiones Behavioral Cloning (OCBC)
Many prior works have used hindsight relabeling to reduce the multi-task RL problem to one of conditional imitation learning. Given a dataset of trajectories, these methods label each trajectory with a task that the trajectory completed, and then perform cusk-conditioned behavioral cloning [3, 5. 7, 9, 14, 16, 19, 25, 28, 30, 31, 37). We call this method nutcome-conditionel behavioral cloning (OCBC). While OCBC can described different ways (see, e.g., [5, 6)), our description below allows us to draw a precise connection between the OCBC problem statement and the standard MDP.
The input to OCBC a behavioral policy {(a s). and the output is an outcome-condiiioned policy (a 8, e). While the behavioral policy is typically left as an arbitrary choice, in our analysis we will construct this behavioral policy out of task-conditioned behavioral policies 3(a s, s,e). This construction will allow us to say whether the new policy ITaa s, e) is better than the old policy 3(a s, e). We define B(T) and (( e) as the trajectory probabilities for behavioral policies ((a s) and ( s, e), respectively.
Most of our analysis applies to both discrete and continuous state and action spaces, with the exception of Lemma 4.1.

---

1. Collect experience.
So. ag
$1. a
52. a2
$3. 33
Label each state.
eu
e
e2
e
3. Relabel each state.
Figure I: Labeling and relabeling: (I) OCBC collects experience, and then (2) labels every state with task that completed that state. For example, in goal-reaching problems we have 8t, st completes the task of reaching goal st- (3) Finally, each state relabeled with a task was completed the future. Each state may be relaheled with multiple tasks, as indicated by the extra green circles.
The key step in OCBC is choosing which experience to use for learning each task, step visualize Fig. 1. After collecting experience with the behavioral policy 3(a 8) (blue circles), every state 8 in this experience is labeled with an outcome e, that is achieved at that state (orange circles). Most commonly, the outcome is equal to the state itself: e 8t [5, 9, 18. 30), though prior work considers other types of outcomes, such natural language descriptions [19]. We define p(e: 8t) as the distribution of outcomes achieved state st. Finally, we define random variable et+ to represent the future outcomes for state s, and action a, The future outcome is defined as the outcomes for states that occur in the y-discounted future. Formally, we can define this distribution over future outcomes as:
plall) (e- |81, as) $ (1 Eprr
Σ r'ple: et 180)
Outcome-conditioned behavioral cloning then performs conditional behavioral cloning on this relabeled experience. Using d (s, a) denote the distribution over states and actions visited by the behavioral policy and (et+ s, a.)) ) to denote the distribution over future outcomes (Eq, 2), can write the conditional behavioral cloning objective
Algorithm
Outcome-conditionee behavioral
cloning (OCBC)
input behavior policy {(a [s)
'D +- REL.AREI(T) where T ~ 3(r) See Fig. F(T; t Eleeeeeee )~2 [logs(a: ((a eet)))
a(a s,e) arg arg,ax, F(T)
return π (a s,e)
F(T:
B. (eu4laa [log 8t, (s,6)+)]- (3)
x" (er.02)
We define (a e) & arg max, F(T; B) the solution to this optimization problem. We summarize the OCBC training procedure Alg. 1.
3 Relating OCBC to Reward Maximization
In this section, we show that the conventional implementation OCBC does not quite perform reward maximization. This analysis identifies why OCBC might perform worse, and provides guidance how to choose tasks and perform relabeling so that OCBC methods perform better. The analysis also allows us draw equivalence with prior EM-based policy search methods.
3.1
What are OCBC methods trying to do?
The OCBC objective (Eq. 3) corresponds to a prediction objective, but we would like to solve a control objective: maximize the probability of achieving outcome We can write this objective as the likelihood of the desired outcome under the future outcome distribution (Eq. 2) following the task-conditioned policy x(a s,e):
Bat=pa(t) (ptthee (eet = = = F. Be--palehaatlomm
Σ rh' (1 App(e = 88)
Br. (se.me)
By substituting the definition of the future outcome distribution (Eq. 2) above, we see that this control objective is equivalent to standard multi-task RL problem (Eq. 1) with the reward function: (ee at) A (1 - >)ppe st). Do OCBC methods succeed in maximizing this RL objective?

---

rewards
e2
initial policy
OCBC policy
Initial policies
average policy
OCBC policies
action probabiltles
@1
e2
returns
-133%
13%
e2
actions
actions
actions
left goal
right goal
Step Aggregate Step 2. Reweight aggregate data from all tasks, data by the task rewards.
Figure 2: How does OCBC relate to reward maximization? OCBC is equivalent to averaging the policies from different tasks (Step 1) and then reweighting the action distribution by Q-values (Step 2). The reweighting step policy improvement, the averaging step can decrease performance. In this example, OCBC decreases the task reward by 13%.
3.2 How does OCBC relate to reward maximization?
While it is unclear whether OCBC methods maximize rewards, the OCBC objective is closely related to reward maximizing because the distribution over future outcomes looks like a value function: Proposition 3.1. The distribution future outcomes (Eq. 2) is equivalent to a Q-function for the reward function re re():): (e = e $1, a4) = Q*(1) at, e).
This result hints that OCBC methods are close to performing reward maximization. To clarify this connection, we use Bayes' rule to express the OCBC policy To(a 8, e) in terms of this Q-function:
To (a Se, et+) = p (ael se, (et)
(4) This expression provides a simple explanation for what OCBC methods are doing - they take the behavioral policy's s action distribution and reweight it by the Q-values, increasing the likelihood of good actions and decreasing the likelihood of bad actions, as done in prior EM-based policy search methods [22, 26, 27J. Such reweighting is guaranteed to perform policy improvement:
e (e st, a.):(BB(a) s:) = (s ec4)
st).
Proposition 3.2. Let (a 1, e) be the Bayes-optimal policy for applying OCBC to behavioral policy 3(a 8). Then T(a 8, e) achieves higher returns than 3(a (s) under reward function re(Se, at):
Em(rie) Σ (r'r((s,,a))
2 Es(r)
Σ )re(ss
The proof Appendix C. This initial result is an apples-to-oranges comparison because it compares a task-conditioned policy (a
to task-agnostic policy, [3 s).
To fully understand whether OCBC corresponds to policy improvement, we have to compare succes- sive iterates of OCBC. To do this, assume that data collected from task-conditioned behavioral policy B(a s, e). where tasks are sampled from the prior e (e()). We can now rewrite the Bayes-optimgs OCBC policy (Eq. 4) as the output of a two-step procedure: average together the policies for different tasks, and then perform policy improvement:
T(a s,e) + (R(1))s
B(a (alss) + 8(a) s, (e s)de
B(a
(e
mwvrgging
improvement stop
The distribution (e is the distribution over commanded tasks, given that the agent is in state st-
Intuitively, the averaging step looks all the the actions that were taken at state St, regardless of which task the agent was trying to solve when it took that action. Then, the improvement step reweights those actions, that actions with high Q-values receive a higher probability and actions with low Q-values receive a lower probability. While makes sense that the improvement step should yield better policy, it is less clear whether the averaging step makes the policy better or worse.
"The state- actennction distribution (s, and future outcome distribution y ss. a) for this mixture of policies is equivalent those for a Markovian policy, B(a B(a s)p (e s)de [38, Thm. 2.8].

---

3.3 OCBC can fail to maximize rewards
We now use this two-step decomposition to show that OCBC can fail maximize rewards. While prior work has also shown that OCBC can fail [25], our analysis helps to explain why: for certain problems, the averaging step can make the policy much worse. We start by illustrating the averaging and improvement steps with simple example, and then provide some formal statements using this example as a proof by counterexample.
While priro work has already presented simple counterexample for OCBC [25], we present a different counterexample
better visualize the averaging and improvement steps. We will use simple bandit problem with one state, a one-dimensional action distribution, and two tasks. We visualize this setting in Fig. 2. The two tasks have equal probability. The averaging step takes the initial task consiiondt policies (left) and combines them into single policy (center-bottom, Since there only one state, the weights p(e s) are equal for both tasks. The improvement step reweights the average distribution by the task rewards (center-top), resulting in the final cusk-condttioned policies learned by OCBC (right). In this example, the final task-conditioned policies achieve returns that are about 13% worse than the initial policies.
Formally, this counterexample provides with proof of three negative results: Proposition 3.3. There exists an environment, task distribution, and task e where the OCBC policy, (a s, e). does not achieve the highest rewards:
Σ Exrelss, as) Cmm
00
< max (rle) Extrlon.aa)
Em((ie)
Proposition 3.4. There exists an environment, policy B(a s, e). and task such that the policy produced by OCBC, x(a s, s, achieves lower returns than the behavior policy:
En(rio) Σ
N're(se, ui)
< <Epcrie)
Σ Crreess az)
Not only can OCBC fail to find the optimal policy, can yield policy that worse than the initial behavior policy. Moreover, iterating OCBC can yield policies that get worse and worse:
Proposition 3.5. There exists environment, initial policy vo(a 8, s), and task such that iteratively applying OCBC, Te+1 + arg max, F(T;; B = nτ), results in decreasing the probability of achieving desired outcomes:
B ((rle)
< Ez,(rle)
Σ (r'ra(s
for all 1,1,
While prior work has claimed that OCBC is effective way learn from suboptimal data [5, 9], this result suggests that this claim is not always true. Moreover, while prior work has argued that iterating OCBC is necessary for good performance [9], analysis suggests that such iteration can actually lead to worse performance than doing no iteration.
In this example, the reason OCBC made the policies worse was because of the averaging step. In general, the averaging step may make the policies better or worse. all the tasks are similar (e.g., correspond to taking similar actions), then the averaging step can decrease the variance in the estimates of the optimal actions. If the tasks visit disjoint sets of states (e.g.. the trajectories do not overlap), then the averaging step will have no effect because the averaging coefficients (e(e |s) are zero for all but one task. If the tasks have different optimal actions but do visit similar states, then the averaging step can cause performance decrease. This case is more likely to occur in settings with wide initial state distributions, wide task distributions, and stochastic dynamics. In Sec. 4, we will use this analysis propose variant of OCBC that does guarantee policy improvement.
3.4 Relationship with EM policy search
While OCBC is conventionally presented as way to solve control problems without explicit [5. 9], can use the analysis in the preceding sections to show that OCBC has a close connection with
5

---

prior RL algorithms based on expectation maximization [4, 12, 15, 21, 22, 26, 27, 33, 34]. We refer to these methods collectively as EM policy search. These methods typically perform some sort of rewgrd-weighted behavioral cloning [4, 27], with each iteration corresponding to a policy update of the following form:
((Q (st, ar)) log (at st)
max (o..a))
where ʃ()) is a positive transformation. While most prior work uses an exponential transformation (f(Q) = e [15, 22, 34), we will use a linear transformation (f(Q) = Q) [4, 27] to draw a precise
connection with OCBC. Prior methods use variety of techniques to estimate the Q-values, with Monte-Carlo estimates being a common choice [27].
OCBC is EM policy search. We now show that each step of EM policy search is equivalent to each step of OCBC, for particular set of tasks & and particular distribution over tasks (e).). To reduce EM policy search OCBC, will use two tasks: task e corresponds reward maximization while task ep corresponds to reward minimization. Given a reward function r(s) E (0, 1), we annotate each state with a task by sampling
e1 with probability r(s)
ple
88)
co
with probability (1 (1-ri) rs))
With this construction, the relabeling distribution is equal to the Q-function for reward function r(s): (e(+ e1 St, ar) = Q az). We assume that data collection is performed by
deterministically sampling the reward maximization task, e1. Under this choice of tasks, the objective for OCBC (Eq. 3) is exactly equivalent to the objective for reward weighted regression [27]:
F(T;; 3) = T (p ( (ec.a))
[log 8t, [(]]
= E (aloa)
(e++ =6 az) log ((r St, (1, + P01 (e+ (ee+ =
e se, oz) log ((a se, se)ew)
Qoctt)(s, at) T(g (1, (1 (1-
= =Bpl(
((az 8c, eu)
On the last line, we have treated the loss for the reward minimization policy (task eq) as a constant, as EM policy search methods do not learn this policy.
While OCBC can fail optimize this objective (Sec. 3.2). EM-based policy search methods are guaranteed to optimize expected returns (Dayan and Hinton [4], Toussaint et al. [35, Lemma 1J). This apparent inconsistency resolved by noting how data are collected. Recall from Sec. 3.2 and Fig. 2 that OCBC is equivalent to an averaging step followed by a policy improvement step. The averaging step emerges because we collect experience for each of the tasks, and then aggregate the experience together. Therein lies the difference: EM policy search methods only collect experience when commanding one task, π (a 8, e1). Conditioning on a single outcome (e1) during data collection removes the averaging step, leaving just the policy improvement step.
We can apply similar trick to any OCBC problem: if there is single outcome that the user cares about (e*), alternate between optimizing the OCBC objective and collecting new experience conditioned on outcome e". If all updates are computed exactly, such procedure is guaranteed to yield the optimal policy for outcome e", maximizing the reward function r(s) = p(c e* s).
This trick only works if the user has a single desired outcome. What if the user wants learn optimal policies for multiple tasks? The following section shows how OCBC can be modified to guarantee policy improvement for learning multiple tasks.
3.5 Should you relabel with failed outcomes?
While our results show that OCBC may may not yield a better policy, they also suggest that the choice of tasks & and the distribution of commanded tasks (e(e) affect the performance of OCBC. In Appendix A, we discuss whether every state should be labeled as success for some task, or whether some tasks should treated as a failure for all tasks. The main result relates this decision to bias-variance tradeoff: labeling every state as success for some task decreases variance but potentially incurs bias. Our experiment shows that relabeling some tasks as failures harmful the low-data setting, but helpful in settings with large amounts of data.

---

Algorithm 2 Normalized OCBC
function RATIOPOLICY(s, e; 3(: ( (x B(a s,e)
mia (1) for 1.2,
CATEGORICAL
return a(9)
function POLICY|MPROVEMENTT6 (, s,),,c
8) (a
arg max (e (e)1 [log x st)]
a(a s, + arg max, (xpp(e)
[[II
Blaylepie) -
s log ( se, ecti)
return RATIOPOLICYY6, c4: 1s))
4 Fixing OCBC
OCBC is not guaranteed to produce optimal step. To fix OCBC, we propose minor modification that "undoes" the averaging step, similar to prior work [25]. To provide a provably-converg procedure, we will also modify the relabeling procedure, though find that this modification is unnecessary in practice.
policies because of the averaging
4.1 Normalized OCBC
OCBC can fail to maximize rewards because of the averaging step, we propose variant of OCBC (normalized OCBC) that effectively removes this averaging step, leaving just the improvement step: 3( s, s,e). To achieve this, normalized OCBC will modify OCBC so
[a s,e) x Q that it learns two policies: learns the cask-conditioned policy using standard OCBC (Eq. 3) and additionally learns the average behavioral policy π ( s) using (unconditional) behavioral cloning. Whereas standard OCBC simply replaces the behavioral policy with the T(a 8, e), normalized OCBC will reweight the behavioral policy by the ratio of these two policies:
(a 8, e) + <(a 8, e)
(a 8(a s,
The intuition here is that the ratio of these two policies represents Q-function: xa s, and Ty s) are learned perfectly (i.e., Bayes' optimal), rearranging Eq. shows that
<aa s. e.4)
x
Thus, normalized OCBC can be interpreted as reweighting the policy by the Q-values, akin to EM policy search methods, but without learning an explicit Q-function. This approach similar to GLAMOR [25], a prior OCBC method that also normalizes the policy by the behavioral policy, but focuses on planning over open-loop action sequences. However, because our analysis relates Q-values to reward maximization, we identify that normalization alone is not enough to prove convergence.
To obtain provably convergent algorithm. need more modification. When relating OCBC to Q-values (Eq. 4), the Q-values reflected the probability of solving task using any policy; that is, they were ( a), rather than @+((1-)) (s, a, e). Intuitively, the problem here is that we are using experience collected for one task to learn solve another task. A similar issue arises when policy gradient methods are used in the off ool-co setting (e.g.. (29]). While we can correct for this issue using importance weights of the form A(rie)
B(rie") such importance weights typically have high variance. Instead, we modify the relabeling procedure. Let us say that the policy for task e collects trajectory т which solves task e'. We will only use this trajectory as a training example of task e' A(rie') < B[ree] I <1+e. If the importance
if the importance weights are sufficiently close to one: weights are too big or small, then we discard this trajectory.
The error e represents bias-variance tradeoff. When small, we only use experience from one task to solve another task if the corresponding policies are very similar. This limits the amount of data
7

---

averaging step
ippovement step
many steps of OCBC
normalized OCBC (ours)
task C2
forokke
opdinal po
mt 32l
task Ca
task
0
0
a1)
nla a1)
m(a a,)
Figure 3: OCBC = averaging + improvement. (Left) On a bandit problem with three actions and three tasks. we plot the current and optimal policies for each task. OCBC first averages together the action distributions for each task and then (Left-Center) Center) learns new policies by reweighting the action distribution by the Q-values for each task. (Right-Center) Iterating OCBC (averaging improvement) produces the optimal policy for task ei but suboptimal policies for tasks 62 and ex; the final policies for tasks e2 and eg are worse than the initial policies. (Right) Normalized OCBC does converge to the optimal policies for each task.
available for training (incurring variance), but minimizes the approximation error. On the other hand, large value of means that experience is shared freely among the tasks, but potentially means that normalized OCBC will converge to a suboptimal policy. Normalized OCBC performs approximate policy iteration, with an approximation term that depends on e (proof in Appendix C):
Lemma 4.1. Assume that states, actions, and tasks are finite. Assume that normalized OCBC obtains the Bayes' optimal policies at each iteration. Normalized OCBC converges to a near-optimal policy:
limsup (xg- A-+00
[v= (o0poo(0))
[vmathie]]
24
(1 (1-7)2
Implementing normalized OCBC is easy, simply involving an additional behavioral cloning objective. Sampling from the ratio policy is also straightforward to do via importance sampling. As shown in Alg. 2, we can first sample many actions from the behavioral policy and estimate their corresponding Q-values using the policy ratio. Then, select one among these many actions by sampling according to their Q-values. In practice, we find that modifying the relabeling step is unnecessary, and use in experiments, decision ablate in Appendix B.
4.2 How to embed reward maximization problems into OCBC problems?
We assume that a set of reward functions is given: (re a)le E E}. Without loss of generality, we assume that all reward functions are positive. Let Tmax - max re (8,a) a) be the maximum reward for any task, any state and action. We then define additional, "failure" task: raai (8, a) Tmax
"E re(s, a). We then use these reward functions to determine how to label each state for OCBC: p(er S2, az) (e(st, 0z) for all e E U {fail].
5 Experiments
Our experiments study three questions. First, does OCBC fail to converge to the optimal policy in practice, as predicted by our theory? We test this claim on both bandit problem and simple 2D navigation problem. Second, on these same tasks, does our proposed fix to OCBC allow the method to converge the optimal policy, is to show that OCBC can fail to converge, even on extremely simple problems. Third, do these issues with OCBC persist on suite of more challenging, goal-conditioned RL tasks [9]? We also use these more challenging tasks to understand when existing OCBC methods work well, and when the normalized version is most important. Our experiments aim to understanding when OCBC methods can work and when our proposed normalization can boost performance, not to present an entirely new method that achieves ttate-of-the-ee art results. Appendix D contains experimental details. Code to reproduce the didactic experiments in available.3.
theory predicts? Our aim in starting with simple problems
Bandit problem. Our first experiment looks at the learning dynamics of iterated OCBC on a bandit problem. We intentionally choose a simple problem to illustrate that OCBC methods can fail on

---

original tasks (med. diff +3%)
blased actions (med. diff. +149%)
blased goals
normalized returns
(med. diff. +62%)
GCSL
normalized OCBC (ours)
Door
Pusher
Pointmass
roams
Pointmass
empg
Door
Pusher
Lunar
Pointmass rooms
Pointmass
empyy
Door
Pusher
Lunar
Paintmass
rooms
Poi Pointmass
empg
Figure 5: Goal-conditioned RL benchmark. We compared normalized OCBC to prototypical implementation
of OCBC (GCSL (9]), using the tasks proposed in that prior work. (Left) On the original tasks, both methods
perform comparably. On versions of the tasks with (Center) skewed action distributions or (Right) goal distributions, normalized OCBC performs better, with median improvement of ~ 149% and ~ 62%.
even the simplest of problems. The bandit setting allows us to visualize the policy for each task as a distribution over actions. We consider a setting with three actions and three tasks, so the policy for each task can be represented as a point (a = 01 e), t 02 e)), as shown in Fig. 3. We first visualize the averaging and improvement steps of OCBC. The averaging step (left) collapses the three task-conditioned policies into a single, lask-agnostic policy. The improvement step (center-left) then produces task-conditioned policies by weighting the action distribution by the probability that each action solves the task. The blue task (e1) is only solved using action di, so the new policy for task e1 exclusively takes action 01. The green task (ey) is solved by both action α1 (with probability 0.3) and action ag (with probability 0.4). so the new policy samples one of these two actions (with higher probability for az). Iterating OCBC (center-right) produces the optimal policy for task e1 but suboptimal policies for tasks 22 and Ey; the final policies for tasks 62 and Eg are worse than the initial policies. In contrast, normalized OCBC (right) does converge to the optimal policies for each task. The fact that OCBC can fail on such an easy task suggests it may fail in other settings.
The bandit setting is a worst-case scenario for OCBC methods because the averaging step computes an weightt average of the three aos-coondt policies. In general, different tasks visit different states, and so the averaging step will only average together policies that visit similar states.
2D navigation. Our next experiment tests whether OCBC can fail to converge on prob- lems beyond bandit settings. As noted above, expect the averaging step to have smaller neg- ative effect non-bandit settings. To study this question, we use simple 2D navigation task with two goals (see Appendix Fig. for details). We compare OCBC to normalized OCBC, mea- suring the average number of steps to reach the commanded goal and plotting results in Fig. 4. At each iteration, we compute the OCBC up- date (Eq. 3) exactly. While both methods learn near-optimal policies for reaching the blue goal, only method learns a near-optimal policy for the orange goal. OCBC's poor performance at reaching the orange goal can be explained by looking at the averaging step. Because the blue goal is commanded nine times more often than the orange goal, the averaging policy p(a s) is skewed towards actions that lead to the blue goal. Removing this averaging step, as done by normalized OCBC, results in learning the optimal policy.
OCBC
Normalized OCBC (ours)
good (oooe 10 2ape
left goel right geal
2)
Sptmar poney
Optmal polley
10
15
0
10
15
iterations
Figure OCBC + policy improvement: On tabular environment with two goals, OCBC fails to learn the optimal policy for one of the goals, whereas normalized OCBC learns near-optimal policies for both goals.
Comparison on benchmark tasks. So far, our experiments have confirmed our theoretical predictions that OCBC can fail to converge; our analysis does not suggest that OCBC methods will always fail. Our next experiments study whether this failure occurs in higher-dimensiona. tasks. We compare to a recent and prototypical implementation of OCBC, GCSL [9]. To give this baseline a strong footing, we use the goal-reaching benchmark proposed in that paper, reporting normalized returns. As shown in Fig. 5 (Left), OCBC and normalized OCBC perform comparably on these tasks. The median improvement from normalized OCBC is negligible +3%. This result in line with prior work that finds that OCBC methods can perform well [5, 9, 31], despite theoretical results.

---

We hypothesize that OCBC methods will perform worst in settings where the averaging step has the largest effect, and that normalization will be important in these settings. We test this hypothesis by modifying the GCSL tasks in two ways, by biasing the action distribution and by biasing the goal distribution. See Appendix for details. We show results in Fig. 5. On both sets of imbalanced tasks, our normalized OCBC significantly outperforms OCBC. Normalized OCBC yields median improvement of + 149% and +62% for biased settings, supporting our theoretical predictions about the importance of normalization. These results also suggest that existing benchmarks may be accidentally easy for the prior methods because the data distributions are close to uniform, an attribute that may not transfer to real-world problems.
6 Conclusion
The aim of this paper is to analyze how outcome behavioral cloning relates to training optimal dowardmmaximize
policies. While prior work has pitched these methods as an attractive alternative to standard RL algorithms, it has remained unclear whether these methods actually optimize any control objective. Understanding how these methods relate to reward maximization is important for predicting when they will work and for diagnosing their failures. Our main result is a connection between OCBC methods and Q-values, connection that helps relates OCBC methods to many prior methods while also explaining why OCBC can fail to perform policy improvement. Based on our analysis, we propose simple change that makes OCBC methods perform policy iteration. While the aim of this work was not to propose an entirely new method, simple experiments did show that these simple changes are important for guaranteeing convergence simple problems.
One limitation of our analysis is that does not address the effects of function approximation error and sampling error. As such, we showed that the problem with OCBC will persist even when using arbitrarily expressive and tabular policies trained on unlimited data. The practical performance of OCBC methods, and the normalized counterparts that we introduce in this paper, will be affected by these sorts of errors, and analyzing these promising direction for future work. A second limitation of our analysis is that it does not focus how the set of tasks should be selected, and what distribution over tasks should be commanded. Despite these limitations, we believe our analysis may be useful for designing simple RL methods that are guaranteed to maximize returns.
Acknowledgements. Thanks to Lisa Loc, Raj Ghugare, and anonymous reviewers for feedback on previous versions of this paper. We thank Keiran Paster for helping understand the connections with prior work. This material is supported by the Fannie and John Hertz Foundation and the NSF GRFP (DGE1745016).
References
[1] Andrychowiez, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abheel, O. P., and Zaremba, W. (2017). Hindsight experience replay. In Advances in neural information processing systems, pages 5048-5058.
[2] Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Neuro-dynamic programming. Athena Scientific.
[3] Chen, L.. Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A.. and Mor- datch, I. (2021). Decision transformer: Reinforcement learnin via sequence modeling. arXiv preprint arXiv:2106.013:
[4] Dayan, and Hinton, G. E. (1997). Using expectation-maximizzaion for reinforcement learning. Neural Computation, 9 278..
[5] Ding, Y., Florensa, C., Abbeel, P., and Phiclipp, M. (2019). Goal-conditioned imitation learning. Advances in Neural Information Processing Systems, 32:15324- 15335.
[6] Emmons, S., Eysenbach, B., Kostrikov, I., and Levine, S. (2021). Rvs: What is essential for offline rl via supervised learning? arXiv preprini arXiv:2
[7] Eysenbach, B., Geng, X., Levine. S., and Salakhutdinov, R. (2020). Rewriting history with inverse rl: Hindsight inference for policy improvement. In Advances in Neural Information Processing Systems.
[8] Geist, M.. Scherrer, B., and Pietquin, O. (2019). A theory of regularized markov decision processes. In International Conference Machine Learning pages 2160-2166 PMLR.
10

---

[9] Ghosh, D., Gupta, A., Reddy, A., Fu, Devin. C. M.. Eysenbach, B., and Levine, S. (2020). Learning to reach goals via iterated supervised learning. In International Conference Learning Representations.
[10] Henderson, P. Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D. (2018). Deep reinforcement learning that matters. In Proceedings of the AAAI conference artificial intelligence, volume 32.
[11] Kaelbling, L. P. (1993). Learning to achieve goals. In IJCAI, pages 1094-1099, Citeseer.
[12] Kober, and Peters, (2009). Learning motor primitives for robotics. In 2009 IEEE International Conference on Robotics and Automation, pages 2112-2118, IEEE.
[13] Kostrikov, I., Nair, A.. and Levine, S. (2021). Offline reinforcement learning with implicit q-learning. arXiv preprint arXiv:2110.06162
[14] Kumar, A., Peng, X. B., and Levine, S. (2019). Reward-conditioeed policies. arXiv preprint arXiv:1912.13460 13465.
[15] Levine, S. and Koltun, V. (2013). Variational policy search via trajectory optimization. Advances in neural information processing systems, 26:207-215.
[16] Li, A. C., Pinto, I.., and Abbecl, P. (2020a). Generalized hindsight for reinforcement learning. arXiv preprint urXiv:2002.11788.
[17] Li, K., Zhang. T., and Wang. R. (2020b). Deep reinforcement learning for multiobjectiive optimization. IEFE transactions on cybernetics, 5106):103-3111
[18] Lynch, C. and Sermanet, P. (2020). Grounding language in play. arXiv preprint arXiv:2005.0m
[19] Lyneh, C. and Sermanet, P. (2021). Language conditioned imitation learning over unstructured data. Proceedings of Robotics: Science and Systems.
[20] Mossalam, H., Assael, Y. M., Roijers, D. M., and Whiteson, S. (2016). Multi-ohjective deep reinforcement learning. arXiv preprint arXiv:1610.02707.
[21] Neumann, G. et al. (2011). Variational inference for policy search in changing situations. In Proceedings of the 28th International Conference Machine Learning, ICML 20/1, pages 817-824.
[22] Neumaun, G., Peters, J., et al. (2009). Fitted Q-iteration by advantage weighted regression. In Advances in Neural Information Processing Systems 21- 1--Proceedings of the 2008 Conference, pages 1 1177-1184,
[23] Nguyen, X., Misra, D., Schapire, R., Dudík, M., and Shafto, P. (2021). Interactive learning from activity description. In International Conference on Machine Learning. pages 8096-8 8108. PMLR.
[24] Oh, J., Guo, Y., Singh, S., Lee, H. (2018). Self-imitation learning. In International Conference on Machine Learning, pages 3978-3887. PMLR.
[25] Paster, K., Mcllraith. S. A., and Ba, J. (2020). Planning from pixels using inverse dynamics models, arXiv preprint arXiw:2012.02419
[26] Peters, J., Mulling, K., and Altun, Y. (2010). Relative entropy policy search. In Twenty-Fourth AAAI Conference on Artificial Intelligence.
[27] Peters, J. and Schaal, S. (2007). Reinforcement learning by reward-weightee regression for operational space control. In Proceedings the 24th international conference on Machine learning, pages 745 750.
[28] Savinov, N., Dosovitskiy, A., and Koltun, V. (2018). Semi- parameearcctic topological memory for navigation. In International Conference Learning Representations.
[29] Schulman, J., Wolski, F., Dhariwal. P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.063:
[30] Srivastava, R. K., Shyam, P., Mutz, F., Jaskowski, W., and Schmidhuber, J. (2019). Training agents using upside-down reinfoncement learning, arXiv preprint 191iv:
[31] Sun, Z., Liu, X., Zhou, B., and Lin, (2019). Policy continuation with hindsight inverse dynamics. Advances in Neural Information Processing Systems, 32:10265 12:10265-10225..
[32] Sutton, R. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
[33] Toussaint, M. (2009). Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference machine learning, pages 1049-1056.

---

[34] Toussaint, M., Harmeling. S., and Storkey, A. (2006). Probabilistic inference for solving (PO)MDPs. Technical report, Technical Report
School of Informatics, University of Edinburgh.
[35] Toussaint, M., Storkey, A., and Harmeling. S. (2010). mdps and optimal control problems. Inference and Learning in Dynamic Models.
methods for solving (po)
[36] Van Moffaert, K. and Nowé, A. (2014). Multi-objective reinforcement learning using sets of pareto dominating policies. The Journal Machine Learning Research, 15(1)334333512.
[37] Yang, R., Fang, M., Han, L.,, Du, Y., Luo, F,, and Li, X. (2021). MHER: Model-based hindsight experience replay. ArXiv, 0bs/2107.00308
[38] Ziebart, B. D. (2010). Madeling purposeful adaptive behavior with the principle of maximum causal entroy.. Camegie Mellon University.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] The main claim of the paper is that existing outcome conditioned RL methods can learn policies that are suboptimal; they get progressively worse. We include the proof in Apepndix
(b) Did you describe the limitations of your work? [Yes] See Sec. 6.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Our contributions are theoretical nature, and therefore do not have direct effect on the potential societal applications of RI..
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix C.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code is attached in the supplemental
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix. D.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Error bars show the mean and standard deviation across random seeds. The number of random seeds is specified within each section.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The didactic experiments ran in few minutes hours on a desktop GPU.
desktop CPU. The continuous control experiments for few
4. If you are using existing assets (e.g., code, data, models) or curating/relcusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "kZoxPqK0aCY", "reviewer": "Reviewer_qZCX", "summary": "The authors theoretically prove that the recent outcome-conditioned imitation learning methods do not always improve the policy. They analyze the OCBC methods from the reward maximizing view, which is the fundamental goal of imitation learning. And they find that the OCBC is a type of EM policy search and the average step makes it fail to find the optimal policy. Then they propose Normalized OCBC to \"cancel out\" the average step by importance weighting. The experimental results show that OCBC indeed fails to converge to the policy in practice and the proposed solution works well.", "questions": "Please see the Weaknesses part above.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper studies a fundamental problem of outcome-conditioned imitation learning. The theory is sound and the proposed method is simple and effective. The writing is good and I enjoy reading the paper.\n\nWeaknesses:\n\n1. Would you please introduce some failure cases in the real-world application of OCBC? in Line171, the failure condition \"the tasks have different optimal actions but do visit similar states\" is a little too demanding. I worry that in real-world settings, if you collect a diverse enough dataset, this phenomenon may never happen, which will limit the value of this paper.\n2. For comparison results on benchmark tasks, there is only one baseline method. Although I don't think it is a big deal, it would be better to compare with more imitation learning methods.\n3. The proposed Normalized OCBC is quite similar to some debiasing methods [1,2] in deep learning literature, i.e., using a biased model to cancel out the biasing effect. It is worthwhile to mention them in related work.\n\n[1] Cadene, Remi, et al. \"Rubi: Reducing unimodal biases for visual question answering.\" Advances in neural information processing systems 32 (2019).\n\n[2] Bahng, Hyojin, et al. \"Learning de-biased representations with biased representations.\" International Conference on Machine Learning. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "B6LvQb6QRoL", "reviewer": "Reviewer_MVgi", "summary": "This paper studies an existing family of methods for multi-task Reinforcement learning called outcome conditioned behaviour cloning (OCBC). The paper identifies a short-coming of these methods, that, these methods are not guaranteed to maximize rewards when applied to multi-task RL. The paper proposes a correction to these method and shows that the proposed method is guaranteed to obey the policy improvement theorem. The experiments show that the proposed method performs better than OCBC under various settings.", "questions": "My main confusion lies in the problem setting and problem formulation. \nWhat is multi-task RL? \nHow is it different from multi-objective RL? \nThe paper presents preliminaries and many mathematical definitions regarding the Q values and distributions of trajectories. However, the paper fails to mention what the aim of the agent in this setting is? \nDoes the agent want to maximize rewards? \nDoes the agent want to reproduce a trajectory that leads to a state where it achieves a tasks?\nWhat is the relation between task and reward? \nWhat if the original algorithm OCBC was designed for the agent to achieve the task and it does not really care about maximizing an abstract notion of reward? \nWhy is reward maximization important in this setting\nGenerally speaking, it is fair to say that goal of almost every MDP agent is reward maximization. Is that not true in this case? \n\nThe most simplest experimental setting the paper presents is of a multi-armed bandit. But here again, the paper presets a multi-task multi-armed bandit? What is this setting. Does the actions not have reward associated with each arm? Are the rewards of these arms dependent on each other since each action accomplishes a task? Again, what is the relation between reward and task? \n", "limitations": "The problem setting and formulation for this paper were quite confusing. It is not possible to gather the significance and relevance of the results without a clear understanding of the goal of the agent. The paper will benefit from clearly describing the problem setting and goal. This should naturally answer the question regarding the relationship between reward and multi-tasking. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ Seems to follow and study an existing suite of methods and analyzes their theoretical relevance in depth\n+ Follows a good step-wise process towards building its results\n+ Presents a theoretical, algorithmic and experimental contribution\nWeakness\n- The problem setting and formulation was not clear\n- The experimental setting was also not clear (related to previous weakness) \n- Difficult to understand the significance of these results", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ACQALEy3tau", "reviewer": "Reviewer_Z1NT", "summary": "This paper discusses about the outcome-conditioned behavior cloning (OCBC) method in the goal-conditioned reinforcement learning field. It suggests that OCBC is not guaranteed to produce optimal (reward-maximizing) policies because of the averaging step (averaging the policies from different tasks). Furthermore, a normalized OCBC is proposed to fix the problem above. Both theoretical and experimental evidences are provided to support the suboptimality of OCBC.  ", "questions": "Is the conclusion and proposed method (normalized OCBC) suitable to single-task behavior cloning, both online and offline settings?\nIs OCBC the mainstream method in goal-conditioned RL? Are there any other variants of OCBC?", "limitations": "The authors adequately address the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The discussion of OCBC's suboptimality is novel and interesting. Authors provide solid theoretical analyses and easy-to-understand illustrations. However, it would be better if the significance and related works are more detailedly clarified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept