P3IV: Probabilistic Procedure Planning from Instructional Videos with Weak Supervision

In this paper, we study the problem of procedure planning in instructional videos. Here, an agent must produce a plausible sequence of actions that can transform the environment from a given start to a desired goal state. When learning procedure planning from instructional videos, most recent work leverages intermediate visual observations as supervision, which requires expensive annotation efforts to localize precisely all the instructional steps in training videos. In contrast, we remove the need for expensive temporal video annotations and propose a weakly supervised approach by learning from natural language instructions. Our model is based on a transformer equipped with a memory module, which maps the start and goal observations to a sequence of plausible actions. Furthermore, we augment our model with a probabilistic generative module to capture the uncertainty inherent to procedure planning, an aspect largely overlooked by previous work. We evaluate our model on three datasets and show our weaklysupervised approach outperforms previous fully supervised state-of-the-art models on multiple metrics.


Introduction
Procedure planning is a natural task for humans -one must plan out a sequence of actions that takes one from the current state to the desired goal. While effortless for humans, procedure planning is notoriously hard for artificial agents. Nevertheless, solving procedure planning is of great importance for building next-level artificial intelligence systems capable of analyzing and mimicking human behaviour, and eventually assisting humans in goal-directed problem solving, e.g., cooking, assembling furniture or tasks that can be represented as a clear set of instructions. Traditionally, procedure planning has been addressed in structured environments, such as object manipulation on a table surface [13,44]. While restricting the environment helps improve planning, it also limits the range of possible applica- In contrast, our approach (top row) exploits natural language representations, li, of the intermediate labels, ai, as a surrogate supervision, which only requires labeling the order of events. Note that the action label, ai, is a discrete variable, whereas the action language representation, li, is a pre-trained continuous embedding.
tions. Here, we follow more recent work [8] and tackle procedure planning in the realm of instructional videos [47,56]. Given visual observations of the start and goal states, the task is to predict a sequence of high-level actions needed to achieve a goal; see Fig 1. This task is particularly challenging as it requires parsing unstructured environments, recognizing human activities and understanding human-object interactions. Yet, the range of applications for such planners is broad, which motivates research efforts on this problem.
Current approaches for procedure planning from instructional videos share a serious limitation -reliance on strong supervision with expensive annotations [6,8,46]. Specifically, all such methods require access to (i) a list of action labels used to transition from start to the goaafl state and (ii) the visual representation of the intermediate states. Using such intermediate visual representations entails very expensive annotation of the start and end times of each intermediate instructional step; see Fig 1 (bottom). In contrast, our work removes the need for intermediate visual states during training and instead uses their linguistic representation for supervision. Relying on language representations allows us to better leverage instructional videos and significantly reduce the labeling effort; see Fig. 1 (top). For example, language annotations for the intermediate instructional steps could be extracted from general procedure descriptions available in recipes or websites, e.g., WikiHow [21]. In contrast, to obtain the timestamps for intermediate instructional steps one must watch the entire instructional video. In addition, a language representation can be a more stable supervisory signal [40], as the description of a given step (e.g., add seasoning) remains the same, while its visual observation varies across different videos.
Previous work on procedure planning from video relies on a two-branch autoregressive approach while adopting different architectures to model these branches [6,8,46]. In such models, one branch is dedicated to predicting actions based on the previous observation, while the other approximates the observation given the previous action in a step-bystep manner. Such models are cumbersome and compound errors, especially for longer sequences. In contrast, we rely on a single branch non-autoregressive model, implemented as a transformer [48] that generates all intermediate steps in parallel conditioned on the start and goal observations. Another important factor in procedure planning is to model the uncertainty inherent to the prediction task. For example, given a set of ingredients and the goal of making a pancake, the intermediate steps could be either (i) [add wet ingredients − → add dry ingredients − → whisk mixture] or (ii) [add dry ingredients − → add wet ingredients − → whisk mixture]. This example shows that in realistic scenarios some plans can vary even under a shared common goal. This observation is usually handled in physical path planning tasks (e.g., robotic arms are allowed to follow multiple feasible trajectories [44]); yet, effort is lacking on probabilistic modeling of procedure planning from instructional videos. While previous work included a probabilistic component at training time [6], we are the first to use and benefit from multiple plausible plans at inference. We explicitly handle uncertainty in procedure planning with a dedicated generative module that can produce multiple feasible plans.
Contributions. In summary, the main technical contributions of our work are threefold. (i) We introduce a weakly supervised approach for procedure planning, which leverages powerful language representations extracted from pre-trained text-video embeddings. (ii) We tackle the task with a simpler single branch model, which can generate all intermediate steps in parallel, rather than relying on the two-branch auto-regressive approach used in previous work. (iii) We propose a generative adversarial framework, trained with an extra adversarial objective, to capture the stochastic property of planned procedures. We evaluate our approach on three widely used instructional videos datasets and show state-of-the-art performance across different prediction time horizons, even while relying on weaker supervision. We also show the advantage of modeling uncertainty. Our code is available at: https://github. com/SamsungLabs/procedure-planning.

Related work
Procedure planning. Traditionally, goal-conditioned planning has been studied mostly in physical environments, e.g., robotic motion planning [14,16,23] and human pedestrian trajectory planning [33]. Recently, the task of procedure planning from instructional videos was introduced [8]. Various approaches have made use of recurrent neural networks (RNNs) [8], transformers [46] and adversarial policy planning [6]; all have used two-branches and strong visual supervision. In contrast, we model the actions directly using a non-autoregressive transformer-based architecture. More importantly, we use low-budget weak supervision in the form of language instructions instead of supervising the model with "costly" visual observations as done by all existing approaches.
Supervision with natural language. A common alternative to training visual models using manually defined label sets is to exploit semantic supervision from natural language. Using natural language as supervision has several advantages: (i) language annotations can be collected automatically [37]; (ii) modeling language and vision jointly can produce stronger representations [10]; (iii) such supervision can achieve better generalization to unseen domains [40]. Such benefits resulted in a growing interest in using language as supervision for variety of tasks, e.g., image classification [10,17,22], representation learning [36,51], video retrieval [15,37], step localization [11,36] and navigation with instruction following [38]. We use advances in joint video and language modeling for procedure planning. We use pre-trained features [36] to map language and video to a common space and replace expensive video supervision with readily available language instructions Sequence modeling with transformers. Procedure planning is a task of conditional sequence prediction and thus it directly benefits from recent advances in sequence modeling. One of the strongest recent approaches to sequence modeling is the transformer architecture [48], which has been adopted for a wide variety of tasks, e.g., images [26], videos [4] and multi-modal data [31,32,51] tasks. Recent work adopted the transformer decoder architecture for fixed-size set prediction via learnable input queries [7,54]. We build upon similar ideas by setting the first and last queries to correspond to the start and goal observations, while making the intermediate queries learnable. To improve long-range sequence modeling and help overall sequence coherence, recent work augmented transformers with an explicit external memory [29,50]. For the same reasons, we also integrate a learnable memory module. Future prediction. The task of procedure planning is closely related to future prediction, where only past observations are provided as input. A key consideration in future prediction is modeling prediction uncertainty from partial initial observations. One common approach for modeling uncertainty is a Variational Auto Encoder (VAE) [25] that captures the distribution over future actions. Another approach is to use generative adversarial networks (GANs) to forecast multiple, distinct and high quality future activities [39,55]. In this work, we adopt the generative modeling framework to model distributions over possible plans.

Technical approach
Here, we present our approach to procedure planning that relies on three main components. First, we predict all steps in the plan in parallel using a non-autoregressive transformer decoder. To obtain coherent plan predictions, our transformer is augmented with a learned memory shared across all possible tasks in a given dataset (Sec. 3.2). Second, to model the uncertainty inherent to the task, we include a generative component trained with an adversarial loss. As a result, we can infer multiple feasible plans conditioned on start and goal observations (Sec. 3.3). Third, to supervise the transformer's outputs, we use the crossentropy loss on action predictions and a contrastive loss to match visual state predictions with the corresponding language descriptions (Sec. 3.4). Fig. 2 provides an overview of our approach, which we detail next.

Problem formulation
Given a start visual observation, v start , and a desired visual goal, v goal , our task is to predict a plan defined as the sequence of T intermediate action steps,π =ã 1:T , taken to transition from v start to v goal . We overscore with ∼ to indicate our predictions, while the lack of such overscoring indicates ground truth (GT). At training time, given v start and v goal , we predict a plan,π, and corresponding visual observations,ṽ 1:T . We use the intermediate action labels, a 1:T , to train the plan prediction,π, and corresponding language descriptions (embedded with a pre-trained text encoder), l 1:T , to supervise the intermediate visual observations,ṽ 1:T . That is, we substitute the visual information about intermediate instruction steps, v 1:T , with their language counterparts, l 1:T , to train the planner; see Fig. 2. We believe such supervision substitution is meaningful, as we are using a strong pre-trained vision-language encoder [36], mapping visual activities and their descriptions in a common space, thus making visual, v t , and language, l t , features, corresponding to the same activity, interchangeable for training. In contrast, previous work assumes access to the set of intermediate action-observation pairs (i.e., a 1:T , v 1:T ) [6,8,46], thereby requiring strong supervision to identify all intermediate visual observations. At inference time, we only use the start and goal observation, to predict a plan,π =ã 1:T , for a given time horizon, T .

Memory augmented transformer decoder
To implement our planner, we use a non-autoregressive transformer decoder architecture [7,54]. Our transformer decoder takes two input types; namely, learnable queries augmented with the start and goal observations and a learned memory component, and outputs action and intermediate state predictions, as illustrated in Fig. 2.
Conditioned learned-query input. The first input is the query set, Q = [q start , q 1 , . . . , q T −1 , q goal ], where the first and last inputs correspond to the representations of our initial and goal visual observations, v start and v goal , respectively, while q 1:T −1 are a set of learned queries. Queries, [q 1 , . . . , q goal ], are associated with the action labels, a 1:T , that we wish to predict. To communicate information about the order of elements to the decoder, we add to each query a fixed cosine positional embedding [5], p t , as follows Q = [q start + p 0 , . . . , q t + p t , . . . , q goal + p T ], where q t and p t all are encoded as d dimensional embeddings, (i.e., q t , p t ∈ R d ) and t = 1, . . . , T − 1.
Learned memory input. The second input to our transformer decoder is a learned memory component that is common across all examples in a given dataset. The memory is defined as a set of d-dimensional vectors where n is the number of learnable vectors in the memory bank. Notably, the size of the memory (i.e., number of entries, n, in the memory) is a hyperparameter that is independent from the prediction time horizon. We use read-only memory [34] and share it among all layers for simplicity.
Memory-augmented transformer decoder. Our architecture is a stack of standard transformer decoder blocks [48] (see Fig. 3), where each such block has access to the global learnable memory, (2). Specifically, the memoryaugmented transformer block consists of two key operations. First, the input is processed with the self-attention operation. Second, the cross-attention module attends to the learnable memory to generate the output. The input to  Figure 2. Overview of our procedure planning approach. First, we embed the visual observations of the start and goal states (i.e., black nodes), attach them to the sequence of learned queries (i.e., colored nodes) and add random noise to the resulting input sequence. Second, we pass the input to the transformer decoder that interacts with the global memory to generate feasible procedure plans. Third, we produce state and action vectors, {ṽi,ãi}, and use a number of losses, L (described in Sec 3.4), to supervise our architecture.
Multi-Head Self-Attention self-attention in the first transformer block corresponds to the query, Q. All cross-attention blocks access the same memory, M. Intuitively, the memory module can be seen as a collection of learnable plan embeddings shared across the entire dataset. Empirically, we show that the memory module plays a key role in our framework. Our transformer decoder, T , consists of a stack of N such memory-augmented blocks. We add two output heads (implemented as multi-layer perceptrons (MLPs)) at the final decoding layer. One head, h a , yields intermediate predicted actions,ã t , while the second, h v , yields corresponding intermediate visual representations,ṽ t , according tõ

Adversarial generative modeling
To capture the uncertainty in prediction, where multiple plans from v start to v goal are plausible, we augment our model with a stochastic component using generative adversarial learning [18]. To make the generation process condi-tional on the input, we augment the entire query input, (1), with a random noise vector, z ∼ N (0, 1), z ∈ R d , through concatenation. The new query input sequence to our transformer, T , thus becomes We employ adversarial training wherein the generator, G, is trained to produce realistic action sequences, while the critic, C, provides the supervisory signal for training G [3]. In our case, we treat the memory-augmented transformer, T , as the generator, G (i.e., G = h v (T (Q z , M))), while the critic is modeled by a simple MLP. More precisely, we pass the output of our transformer,ṽ 1:T , concatenated along the temporal dimension, to the critic, C, which outputs a value between 0 and 1, indicating its ability to discriminate between the predicted and ground truth sequence, as depicted in Fig. 2. Notably, to avoid the notorious issue of mode collapse associated with training GANs [45] (i.e., regardless of variations in random latent noise, z ), we follow previous work [30,52,55] and include the normalized distance regularizing loss, L reg , defined in the supplement.

Training
To supervise our transformer, we rely on two complementary loss functions that enforce our transformer to decode the correct set of action labels in the procedure as well as corresponding visual representations. We also use an adversarial loss to train the stochastic component of our model.
Visual step supervision. One of the outputs of our model at training time is the sequence of visual features, corresponding to the procedure steps,ṽ 1:T . To supervise the visual features with corresponding language features, l 1:T , we adopt contrastive learning [19]. For each feature,ṽ t , predicted by the transformer's head, h v , we use the corresponding ground truth language embedding, l t , as the pos-itive example and all the other embeddings in the language vocabulary, {l j }, as negative examples. The contrastive loss is calculated as where (·) denotes the dot-product operator. Note, we use all examples in the language vocabulary as negatives as our vocabulary is typically small (< 1K elements) and doing so allows for better training compared to per-batch negative sampling, e.g., [20].
Action plan supervision. We also enforce the action prediction head, h a , to output sequences of action probabilities,ã t , corresponding to ground truth one-hot labels, a t . For this purpose, we use the cross-entropy loss Adversarial supervision. To model uncertainty, we use adversarial training on the visual state predictions,ṽ 1:T . The goal is to make predicted visual observation sequences indistinguishable from feature sequences composed of the ground truth language step description, l 1:T . We optimize the generator, G, (our transformer) and the critic, C, (an MLP) using an adversarial loss [3] L adv = min where V is the standard GAN objective, defined as with l∼p data and z∼p z denoting the data distributions of the language representation and random noise, resp.
Complete loss. Overall, our full loss function is defined as where θ refers to the parameters associated with all learnable modules, i.e., queries, memory module, as well as the transformer decoder and discriminator parameters and λ 1:4 are empirically determined loss weights.

Inference
At inference time, we use our transformer as a generative model to sample multiple procedure plans,π k =ã k 1:T , for the same input start and goal observations. This operation is achieved by drawing K latent noise vectors, z k , and forwarding them through our transformer, T , conditioned on a single start-goal observation, as follows for k = 1, . . . , K.
To obtain a probability distribution over actions at each timestep, t, of the plan, given by our model, we calculate action frequencies as follows: Given that a k t are one-hot vectors, eachā t results in a marginal distribution over actions at a specific timestep, t.
Most standard benchmark metrics for procedure planning, such as Success Rate, Accuracy or Intersection over Union (IoU), require a single action sequence output for evaluation (see Section 4.1). To compute the most probable action sequence, induced by our action distribution,Π, we use the Viterbi algorithm [49], as commonly seen in sequential labeling work [27,28,41,42]. More specifically, we usē Π as the emission matrix in the Viterbi formulation, while the transition matrix is estimated from action co-occurrence frequencies in the training set (details in the supplement). Our Viterbi post-processing step can be viewed as biasing sample selections from {π k } K k=1 , toward plans that are more likely under a first-order model of action transitions. An alternative approach to select a likely action sequence is simply to select the mode from the set {π k } K k=1 . We empirically demonstrate the superiority of the Viterbi approach, which proved especially useful for smaller datasets.

Implementation details
Our planner operates on video and language features, pre-extracted by a model trained for joint video-text embedding [36] using the HowTo100M [37] dataset and self supervision. We use a memory-augmented transformer with two layers and eight heads, and optimize it for 200 epochs with ADAM [24] on a single V100 GPU. Additional training and architecture details are provided in the supplement.

Experiments
In this section, we evaluate the role of each module in our approach (Sec. 4.2) and demonstrate its performance across three different datasets. We include evaluation on the largest labeled instructional video dataset, which has not been used previously for the task of procedure planning due to the need of strong supervision in previous work (Sec. 4.3). Finally, we provide prediction uncertainty evaluation in procedure planning for the first time, which sheds light on our approach and the task of planning itself (Sec. 4.4).

Evaluation protocol
Datasets. For evaluation, we use three different instructional video datasets, namely, CrossTask [56], the Narrated Instructional Videos datasets [2] (NIV) and COIN [47]. is much smaller with 150 videos, five procedures and 9.5 actions/video on average. COIN is the largest dataset in our evaluation. It contains 11827 videos, 778 procedures and 3.6 actions/video. Depicted procedures vary widely, e.g., Make Taco Salad and Change Car Tire. We follow previous work [8] and adopt 70%/30% to create our train/test splits and we use 20% of the training data for validation. We also follow the data pre-processing steps outlined in the original procedure planning paper [8] to select {start, goal} observations and curate the dataset into plans covering different time horizons. More details are in the supplement.
Metrics. Following previous work [6,8,46], we evaluate the performance using three increasingly strict metrics. (i) mean Intersection over Union (mIoU) treats the predicted and ground truth action sequences as sets, and measures the overlap between these sets. mIoU is agnostic to the order of actions and only indicates whether the model captures the correct set of steps needed to complete the plan.
(ii) mean Accuracy (mAcc) performs element-wise comparisons between the predicted and ground truth action sequences, thereby considering the order of the actions as well. (iii) Success Rate (SR) considers a plan successful only if it exactly matches the ground truth. We also evaluate the stochastic nature of our model by measuring the following probabilistic metrics: (i) the Kullback-Leibler (KL) divergence between our predicted plan distributions and ground truth; (ii) how well the ground truth modes are covered by our results (Mode Recall); (iii) how often our plans correspond to the ground truth mode (Mode Precision). To this end, for each {start, goal} observation, we draw (K = 1500) samples from our generative model and explicitly approximate a distribution, as described in Sec. 3.5. For completeness, we also evaluate using more standard probabilistic prediction metrics, including Negative Log Likelihood (NLL) and the cosine distance [9,35,55].
Baselines. We compare to all previous approaches to procedure planning from instructional videos [6,8,46] as well as other fully supervised planning approaches [1,12,44].  Table 2. Ablation study on the impact of external memory sizes for prediction horizon, T = 3, with CrossTask. All results are obtained using our transformer, with two layers and eight heads.

Ablation study
Impact of different loss functions. We evaluate the role of each loss component by gradually introducing each objective. The results in Table 1 show the pivotal role of language-based supervision, as evidenced by increased performance across all metrics, and the complementarity of the three objectives. Notably, improvements from the adversarial loss may seem marginal (e.g., ∼ 1% in SR), as the metrics only compare a single prediction to a single ground truth plan. We show its strict superiority to deterministic models for modelling distributions of procedures in Sec. 4.4.
Impact of Viterbi post-processing. Throughout the empirical results, we use the Viterbi algorithm on top of the predicted action probabilities,Π (10), to produce the optimal plan at inference time. Notably, the Viterbi post-processing is optional, and one may directly use the setπ k to produce the final plan by simply selecting the mode across the set. Comparing the last two rows in each block of Table 1 shows the added advantage of using Viterbi to model the optimal action order in procedure plans explicitly, for all datasets.
Notably, Viterbi post-processing is especially helpful on the NIV dataset. We hypothesize that the data scarcity in NIV results in a weaker predictive model at training; therefore, explicitly modeling the optimal transition between the actions with Viterbi plays a more important role in this case.
Impact of model configuration. We also include an ablation evaluating the adopted memory augmented transformer decoder. Table 2 shows that the size of our memory plays a key role in our architecture. Indeed, excluding the memory component yields the worst results, while too large a memory degrades performance. These results suggest that the memory component helps capture dataset content, where it yields stronger results when the number of memory entries is large enough to properly span the actions present in the entire dataset. Notably, while tuning the memory size for each dataset might yield better results, for simplicity, we elect to use the best setting of CrossTask for all datasets.

Comparison to alternative approaches
CrossTask (short-horizon).  consistently better, except for the the success rate (SR) at T = 4, where we are the second best approach. The performance improvement in SR is especially striking at shortterm horizon, T = 3, where we outperform the previous best (i.e., Ext-GAIL [6]) by more than 2%, while using weaker supervision. Notably, Ext-GAIL achieves its level of performance via data augmentation, which allows it to have 30% more training data. In a more similar setup (i.e., when Ext-GAIL does not use data augmentation) the performance gain of our method over "Ext-GAIL w/o Aug" is 5.3%. Importantly, our results are obtained with weaker supervision, which speaks decisively in favor of our approach. We also notice a larger gain in mIoU compared to previous work, i.e., 73.89% vs. 61.70% for T = 3 and 70.01% vs. 60.93% for T = 4. This result suggests that our approach is better at capturing feasible action steps than other approaches (e.g., never producing pour water when input observations are related to making a salad). We hypothesize that this performance is enabled by the languagebased contrastive learning, which is more effective at clustering latent representations than its vision counterpart. For example, while some visual observations can look similar (e.g., pour water and add oil), the distinction between the two is clearer in natural language. Notably, the level of improvements in mIoU and mAcc is typically higher than the gain in SR. We attribute this result to the uncertainty inherent to the task (i.e., multiple feasible plans for the same start and goal observations). We explore this aspect in greater detail in Sec. 4.4. Finally, thanks to the non-autoregressive nature, we are 4x faster at inference, e.g., 6.75ms (ours) vs.

27.34ms (DDN [8]) on CrossTask for T = 3.
CrossTask (long-horizon). We now evaluate our model's ability to predict plans for longer time horizons (i.e., T ∈ {3, . . . , 6}). We compare to previous approaches that reported results on such horizons. There are two different protocols for these settings. (i) Protocol 1 [8] and (ii) Protocol 2 [46]; see details in supplement. For a fair comparison, we present our results using both protocols in Table 4 and show that our approach is the most effective on both.
NIV. Following previous work [6], we also evaluate our model on the smaller NIV dataset. The results in Table 5 are consistent with our results on CrossTask. Once again, our approach is the top performer across all metrics. This result suggests our language supervision works for smaller datasets as well.

COIN.
To show the capability of our method to scale, we evaluate our method on the largest labeled instructional video dataset (i.e., COIN). As we are the first ones to perform procedure planning on such a large-scale dataset, there is a lack of comparison methods. Therefore, we follow existing work [8] and include three baselines: (i) Random selection; (ii) Retrieval-based; (iii) and a re-implementation of the DDN model [8] , using our video features, described in Sec. 3.6. Table 5 shows that our model equipped with language supervision consistently outperforms the baselines, even strongly-supervised ones.  Table 6. Evaluation of the plan distributions produced by our probabilistic approach vs. the deterministic variant.

Evaluating probabilistic modeling
To evaluate our probabilistic modeling, we compare plan distributions produced by our model, with the ground truth distribution over feasible plans. We focus our evaluation of probabilistic modeling on CrossTask as it is the most suitable dataset in terms of variations in the set of feasible plans, as we demonstrate in the supplement.
Plan distribution modeling. Our approach is probabilistic by design as described in Secs. 3.3 and 3.5. To establish a deterministic baseline, we train our model without the adversarial loss and fix the latent noise vector, z = 0, both during training and testing. To build the ground truth distribution over goal-conditioned plans, we retrieve all action sequences of length T in the test set that share the given start and goal state. The plan distribution of our probabilistic model (conditioned on the start and goal observations) is obtained by sampling K = 1500 different action sequences, as discussed in Sec. 3.5. For the deterministic baseline, the model produces only one plan (i.e., K = 1). In all cases, the probability of a plan is defined as its frequency in the obtained sample set. To evaluate the quality of the predicted plans, we measure the (dis-)similarity between plan distributions produced by each model (i.e., ours vs. the deterministic variant) and that of the ground truth using the KL divergence and NLL. Table 6 shows that our probabilistic approach better matches the ground truth plan distribution (i.e., it has lower KL and NLL). These results come about because our model is able to sample multiple valid plans with respect to the test set distribution, as opposed to the deterministic model that considers a single feasible plan.
Sample diversity and mode coverage. For given start and goal observations, our approach produces multiple plan hypotheses, using probabilistic sampling described in Sec. 3.5 (as visualized in Figure 4). In this section, we measure the diversity of our samples and their relation to the ground truth plans distribution. To characterize the ground truth distribution, we define ground truth modes as the set of unique action sequences in the test set that share the same start and goal state. To calculate the relation of our samples to the ground truth modes we define two metrics, Mode Recall (ModeRec) and Mode Precision (ModePrec). Mod-eRec reflects how well the GT modes are covered by our model and is calculated as the average number of GT modes captured by at least one sample from our model. In com-  Table 7 suggest our probabilistic approach can produce both diverse and accurate plans, where it is superior on all metrics.

Conclusion
We have introduced a weakly-supervised method for probabilistic procedure planning using instructional videos. Different from previous work, we echew the need for expensive visual supervision in favor of cheaper language supervision by capitalizing on pre-trained text-video embeddings, which, remarkably, leads to superior planning performance. We showed that modeling the interplay between intermediate visual states and actions step-by-step is not a necessity for procedure planning. Instead, we efficiently solve the problem with a "one-shot" transformer decoder architecture. In addition, we demonstrated the crucial role of modeling uncertainty in obtained plans to yield a principled approach to planning from videos. We introduced a way to evaluate such uncertainty on the test set and show that it is a powerful metric to better understand the model and the task of planning itself. Hopefully, future work will adopt the probabilistic view on procedure planning from instructional videos, not only in training but also in evaluation, such that the next generation of planners can confidently predict multiple feasible plans to achieve the desired goal.

A. Supplementary material
Our supplemental material is organized as follows: Section B provides details on the regularization loss used in our adversarial training. Section C elaborates on our inference procedure using the Viterbi algorithm. Section D includes a thorough description of our implementation details. We then provide a detailed description of the evaluation protocols in Section E. We describe the baselines we compare to in Section F. Finally, in Section G, we present additional ablation experiments and more visualizations.

B. Regularization loss for the generative model
As mentioned in the main paper, Section. 3.5, in addition to the contrastive and cross-entropy losses, we also use an adversarial loss to train the stochastic component of our model. To effectively capture the different modes present in the data and avoid the notorious mode collapse problem of GANs, we apply the recently proposed latent code normalized distance regularizing loss [30,52,53,55] defined as (11) Intuitively, this regularization loss encourages model outputs to be different (in L 1 -norm), for different input noise vectors z 1 , z 2 ∈ N (0, 1). Note that we only apply the regularization loss on the outputs of the visual state branch, i.e. h v (·) in the main paper. For stronger supervision, in our implementation we follow previous work [30] and generate S = 20 samples using S latent noise vectors, {z i } 1:S , calculate the value of L reg for all possible pairs, and select the maximum value to use in the regularization loss L reg . We validate the role of this regularization loss in Sec. G.

C. Inference with Viterbi algorithm
To find the optimal procedure plan, we use the Viterbi algorithm [49], as discussed in Section 3.5 of the main paper. Traditionally, the Viterbi algorithm is used to find the most probable path in the first-order Markov model of a dynamic system. For a sequence of length T and N a possible states of the system, the Viterbi algorithm relies on two main inputs: (i) a transition matrix, A ∈ R Na×Na , capturing the probability of transitioning from one state, a i , to another, a j , (ii) an emission matrix, B ∈ R T ×Na , describing the probability of each state, a i , given a set of observations. In our work, we use the marginal state probabilities for each timestep (defined asΠ in Section 3.5 of the main paper) as the emission matrix, B, and estimate the transition matrix, A, directly from the ground truth plans. Specifically, the transition matrix, A, is calculated based on the action co-occurence frequencies in the training data. To calculate the value of A i,j , we must find the number of times action a i is followed by action a j in the ground truth plans. We then normalize each row of A to sum to 1, by applying L 1 -normalization followed by a softmax with temperature τ = 1.

D. Implementation details
Our model uses pre-extracted language and vision features, with a model trained on the HowTo100M dataset for joint text-video embedding [37]. This backbone model embeds both vision and language inputs into 512 dimensional features. For our model, we use a transformer decoder [48] with eight heads, two layers and 128 dimensional hidden states. Note that we provide an ablation on our architecture choices in Sec. G. Since our pre-trained features are of dimension 512, we embed our initial features using a multilayer perceptron (MLP) with shape [512 → 256 → 128] interspersed with ReLU nonlinearities. A similar MLP is used to project the ground truth language features, l i , to the same dimension. For the memory module, we empirically set the number of memory entries, n, to 128. For the critic, C, we use another three layer MLP with shape [256 → 64 → 32] with ReLU activations in all layers. The dimension of the noise vector, z , is empirically set to 32. We train our model for 200 epochs with an initial learning rate set to 7 × 10 −4 and decayed by 0.65 every 40 epochs. The best performing model on the validation set (i.e. randomly collected using 20% training data as mentioned in main paper Section 4.1) is used to report the final test set results.

E. Data curation and evaluation protocol
To train and evaluate our model, we use instructional video datasets to construct sequences with plans of various time horizons, T . Each plan contains a pair of {start, goal} visual observations, {v start , v goal }, and a sequence of ground truth intermediate action labels, a 1:T .
Data curation. Following previous work [6,8], for each instructional video, we start by extracting the ordered list of all actions, a 1:N , present in the video. We also collect language descriptions, l 1:N , corresponding to each action, a i . In addition, to obtain various start and goal observations, we also extract corresponding visual observations, v 1:N , by locating the start and end times of each action following previous work [6,8]. Note that this information is only used for data curation and not for training as done in previous work. Each video is therefore described as the ordered set of tuples l 1 , v 1 ), . . . , (a N , l N where N is the total number of actions present in the video. Given the video, V , represented with (12), we curate a set of plans with prediction time horizon T by sliding a window of size T + 1, such that a t+1:t+T and l t+1:t+T represent the set of action plans we need to predict, whereas v t and v t+T represent v start and v goal , respectively.
Evaluation protocols. As mentioned in Section 4.3 of the main paper, there exist two different evaluation protocols on CrossTask, namely "Protocol 1" and "Protocol 2". In all our experiments, we follow previous work [6,8] and use "Protocol 1", which relies on the sliding window based data curation procedure described above. In addition, "Protocol 1", uses a 70/30 train/test dataset split as mentioned in Section 4.1 of the main paper. For the long horizon planning experiments on CrossTask (i.e. Section 4.3 of the main paper), we also adopt an additional protocol, proposed in recent work [46] and referred to as "Protocol 2". The main differences of "Protocol 2" can be summarized in the following three points: (i) Instead of relying on a sliding window to consider all procedure plans of time horizon T for each video, "Protocol 2" randomly selects one procedure plan of horizon T per video. (ii) "Protocol 2" uses 85/15 train/test split. (iii) "Protocol 2" predicts actions, a 1:T −1 , which concretely means that, for a prediction horizon, T , it actually makes T − 1 predictions.

F. Baselines
Here, we provide a more detailed description of the procedure planning baselines used in our paper.
-Random. As an elementary baseline, we randomly select action steps from the entire vocabulary with equal probability (i.e. Uniform distribution) for evaluation.
-Retrieval-Based. For each start and goal observation pairing, {v start , v goal }, in the test set, this method retrieves the nearest neighbor in the train-set based on visual feature similarity. The plan labels associated with the retrieved nearest neighbor is used for evaluation.
-Universal Planning Networks (UPN) [44]. UPN is a physical-world path planning algorithm with a continuous action policy. We follow previous work [8] to modify it via appending a softmax function for the discrete action space.
-Dual Dynamics Networks (DDN) [8]. DDN models the state-action transition of procedural plans with a two-branch auto-regressive model. The state branch is modeled with an MLP, while the action branch uses an RNN.
-PlaTe [46]. This method simply replaces the models used in the two-branch model of DDN with autoregressive transformer modules.
-Ext-GAIL [6]. This method uses reinforcement learning techniques for procedure planning and augments the DDN  architecture with a context latent variable.

G. Additional ablation experiments
In addition to the various ablations presented in the main paper, here, we provide additional experiments to evaluate other aspects of our loss, architecture and inference procedure.

G.1. Impact of the regularization loss
In this experiment we further evaluate our model's capability to model plan distributions. For this purpose we follow the evaluation procedure adopted in Section 4.4 of the main paper. The effectiveness of the diversity regularization loss, (11), for our approach is studied in Table 8. It is clear that training without the regularization leads to worse NLL and KL-div values. These results confirm the important role of the regularization in the probabilistic model, which indeed seems to suffer from mode dropping in the absence of such regularization.

G.2. Impact of the Viterbi post-processing
In the main paper, we have shown that using Viterbi postprocessing, while relying on our predicted plan distribution, Π, as an emission matrix, leads to overall better plan predictions (i.e. see Table 1 of the main paper). Here, we further study the role of emission, B, vs. transition, A, matrices, in the Viterbi-based plan inference. In particular, to show the importance of using our predicted distribution,Π, as an emission matrix, we substitute it with a uniform matrix, i.e. a matrix with all values equal to 1 Na , and perform plan inference with a correspondingly modified Viterbi algorithm. In other words, in these settings, the plan inference will be driven purely by the transition matrix, A. We also experiment with setting A to the uniform matrix, and only using B to drive Viterbi's inference. Table 9 shows that our original formulation gives the best results and highlights the importance of estimating the emission and transition matrices properly from data, as handled by our model.

G.3. Impact of the size of the sample set
In the main paper, we provide inference results obtained by sampling K = 1500 procedure plans from our probabilistic model. Here, we ablate this parameter and show its influence on how well we fit the ground truth plan distribution.  Table 11. Ablation study on the number of layers and heads for prediction horizon, T = 3, with CrossTask.
to better results as it can better approximate the true distribution. However, it should be noted that larger value of K require more computation. We therefore chose K = 1500 for our experiments as a reasonable trade-off between performance and computation cost.

G.4. Impact of transformer architecture
Here, we examine the impact of the transformer architecture on the plan prediction performance. To save on the computations, we limit this study to a prediction horizon of T = 3. Table 11 shows the performance of alternative transformer configurations with different number of layers and/or heads. The model used in our paper -with two layers and eight heads -performs best on CrossTask.

G.5. Alternative uncertainty baselines
Our approach captures the uncertainty of plans by learning a stochastic model (GAN), which allows it to produce distinct procedure plans when seeded with different random noise vectors. On the other hand, one can follow a more naive approach and obtain diverse outputs from a model trained deterministically (i.e. no randomness at training), by adding random noise to the system only at inference, e.g., injecting random noise in the input or using dropout at inference. Here, we compare our GAN-based formulation to the aformentioned naive approaches for introducing diversity in the predicted plans; results are summarized in Table 12. In particular, we evaluate adding Gaussian random noise of different intensity to the input, i.e. N (0, σ), and applying dropout (of probability p) to the hidden representation of the network at inference time. We see that both baselines can increase diversity at the cost of accuracy. The best naive configuration is Ours-deter+dropout (p = 0.3) which is still inferior to our full GAN-based approach on both deterministic and probabilistic metrics. This result shows the importance of learning the uncertainty model during training, as opposed to simply adding it at inference, confirming that the GAN is useful for modelling uncertainty in our scenario.

G.6. Ablation on Video+Language features
In this study, we choose vision+language features pretrained on HowTo100M because recent work (e.g., [32,36]) show state-of-the-art results with such features on the datasets we are experimenting with (i.e., COIN, CrossTask). Still, it is interesting to consider using a dataset's "native" features as a variation. For this experiment, we use the CrossTask dataset, employ the video features trained on it (provided with the dataset) and train language embeddings (not provided by the dataset) by ourselves; we finetune the language model [36] to align with CrossTask's video features, using contrastive learning. These features are then used to train our model as described in Section 3 in the main paper. Table 12 (top two rows) shows that using the "native" CrossTask features is still inferior to the large-scale pre-training on HowTo100M [37]. This result could be due to the relative scarcity of data in CrossTask that is insufficient to train strong language+vision features.

G.7. Comparison to strong supervision
Our framework also can be trained with strong supervision, i.e. simply swapping the language supervision signals, {l i }, in Eq. 5 of the main manuscript with visual ones, {v i }; see Sec. E in this supplement. We show the results resulting from this setting in Table 12 (bottom row). Accessing the full annotations can modestly improve or hurt the performance, depending on the metric. Thus, our weakly supervised model performs comparably, while being cheaper to train.

G.8. Additional probabilistic evaluation
In the main paper, we evaluated our probabilistic model on the CrossTask dataset by measuring the Negative Loglikelihood (NLL) and KL divergence (KL-Div). Here, we further provide such results for COIN (in Table 13) and NIV (in Table 14). Interestingly, different from the results obtained on CrossTask (i.e. Table 6  observe that there is no significant difference between our approach and the deterministic counterpart on COIN and NIV. We suspect that this happens because the NIV and COIN datasets are lacking variability in goal-conditioned plans. To verify that hypothesis, we conduct a quantitative evaluation of such variability on COIN and NIV. In Table 15, we show the average number of distinct plans that can connect the same start and goal observations for each dataset and prediction horizon. It is clear that the plans in CrossTask are much more diverse than those present in the other two datasets. In particular, CrossTask has the largest average number of distinct plans for each time horizon. Notably, for all datasets, it seems longer horizons tend to have larger variability. We believe that this is reasonable because any variations of intermediate steps would result in different paths, which highlights the importance of adopting a probabilistic point of view for procedure planning.

G.9. Additional visualizations
In Figures 5 to 8, we provide additional visual examples of plans produced by our model for different prediction horizons. We also show failure cases and discuss potential Datasets T = 3 T = 4 T = 5 T = 6 reasons for such behaviour in corresponding captions. Note that the top two rows in each figure are successful predictions and the bottom row is the failure case. In each row of images, the first and last images denote the start and goal observations respectively, and the very next row shows the action labels predicted from our approach (i.e. rows beginning with "Sample"). For failure cases, we show the corresponding ground truth plan (i.e. rows beginning with "GT") for better understanding. In addition, we also show the (unseen) intermediate visual observations just for clarity of presentation. Our approach does not use them for training and/or testing.

H. Attribution of assets
This research was made possible thanks to the following assets.
-CrossTask dataset [56]. Our study follows the rules from the official license and uses the video URLs and annotations from this website: https://github.com/ DmZhukov/CrossTask. Our usage of CrossTask is limited to this academic work. -COIN dataset [47]. We have signed and submitted the official licence agreement from URL: https://coindataset.github.io/. Our study uses the provided videos/annotations and follows the rules from their license. -NIV dataset [2]. We follow the license agreement and use videos/annotations from URL: https://github.com/ jalayrac/instructionVideos. -MIL-NCE pre-trained model [37]. We follow the license agreement and use the provided pre-trained model weights from URL: https://github.com/ antoine77340/S3D_HowTo100M.     Figure 8. Visualization of two successful outputs (top two rows) and one failure output for T = 6 (bottom row) on CrossTask. Note that the ground truth of the failure case depicted here contains a sequence of repetitive actions. Importantly, notice that while the goal observation depicts a change in color, suggesting the action of Paint Shelves as predicted by our model, the ground truth seems to ignore that matter.