Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learning

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:41:53

Abstract: Exploration in sparse-reward reinforcement learning (RL) is difficult due to the need for long, coordinated sequences of actions in order to achieve any reward. Skill learning, from demonstrations or interaction, is a promising approach to address this, but skill extraction and inference are expensive for current methods. We present a novel method to extract skills from demonstrations for use in sparse-reward RL, inspired by the popular Byte-Pair Encoding (BPE) algorithm in natural language processing. With these skills, we show strong performance in a variety of tasks, 1000$\times$ acceleration for skill-extraction and 100$\times$ acceleration for policy inference. Given the simplicity of our method, skills extracted from 1\% of the demonstrations in one task can be transferred to a new loosely related task. We also note that such a method yields a finite set of interpretable behaviors. Our code is available at https://github.com/dyunis/subwords_as_skills.

Main paper: 
 introduction: 
 Reinforcement learning (RL), the learning paradigm that allows an agent to interact with an environment and collect its own data, is a promising approach to learning in many domains where high-quality data collection is too financially expensive or otherwise intractable. Though it began with dynamic programming in tabular settings, the recent use of neural networks as function approximators has led to great success on many challenging learning tasks (Mnih et al., 2013; Silver et al., 2017; Gu et al., 2017) . These successful tasks tend to have some particular properties. In some cases, it is simple to define a reward function that yields reward at every step of interaction (the "dense" reward setting), like directional velocity of a robot learning to walk (Haarnoja et al., 2018a) . In other cases, the environment dynamics are known, as in the case of Chess or Go (Silver et al., 2017) . However, for many natural tasks like teaching a robot to make an omelet, it is much more straightforward to tell when the task is completed without knowing how to automatically supervise each individual step, how to model the environment dynamics. Learning in these "sparse" reward settings, where reward is only obtained extremely infrequently (e.g., at the end of successful episodes) is notoriously difficult. In order for a learning agent to improve its policy, the agent needs to explore its environment for long periods of time, often in a coordinated fashion, until it finds any reward.One class of solutions to this problem involves including additional task-agnostic dense rewards as bonuses that encourage agents to explore the state space (Pathak et al., 2017; Burda et al., 2018b) . Another class of solutions to the exploration issue is to jumpstart the function approximator to be used in reinforcement learning by training it on some pretext task (Yarats et al., 2021; Liu and Abbeel, 2021) , which works well when the training and downstream domains are well aligned. A third class of methods aims to create temporally extended actions, or "skills", from interactions or data. A particular subclass of methods learns skills that are conditioned on the observations (Singh et al., 2020; Pertsch et al., 2021; Ajay et al., 2020; Sharma et al., 2019; Eysenbach et al., 2018; Park et al., 2022; 2023) , which means that the deployment scenario needs to match the data. Others relax this assumption (Lynch et al., 2020; Pertsch et al., 2021; Bagatella et al., 2022 ) so that such skills can easily be transferred to some new domain as long as the action space remains the same. This has the potential to speed up exploration in new tasks for which it is not easy to collect data a priori (i.e., few-shot), which can lead to faster task adaptation. However, these recent efforts in skill learning all require lengthy pretraining phases due to their reliance on neural networks in order to learn the skills. Inspired by the recent cross-pollination of natural language processing (NLP) techniques in offline RL (Chen et al., 2021; Janner et al., 2021; Shafiullah et al., 2022) , we take a different approach.Like the long-range coordination required for exploration in sparse-reward RL, language models must model long range dependencies between discrete tokens. Character inputs leads to extremely long sequences, and requires language models to both spell correctly and model inter-word relations. On the other hand, word-level input results in the model poorly capturing certain rare and unseen words. The solution is to create "subword" tokens somewhere in between individual characters and words that can express any text (Gage, 1994; Sennrich et al., 2015; Provilkov et al., 2020; Kudo, 2018; Schuster and Nakajima, 2012; He et al., 2020) .In the spirit of this development in language modeling, we propose a tokenization method for learning skills. Following prior work (Dadashi et al., 2022; Shafiullah et al., 2022) , we discretize the action space and use a modified byte-pair encoding (BPE) scheme (Gage, 1994; Sennrich et al., 2015) to obtain temporally extended actions. Then, we use this as the action-space for RL. As we demonstrate, such a method benefits from extremely fast skill-generation (minutes v.s. hours for neural networkbased methods), significantly faster rollouts and training due to open-loop subword execution that does not require an additional neural network, interpretability of a finite set of skills, and strong results in several sparse-reward domains. 
related work: 
 Exploration in RL: Exploration is a fundamental problem in RL, particularly when reward is sparse. A common approach to encouraging exploratory behavior is to augment the (sparse) environment reward with a dense bonus term that biases toward exploration. This includes the use of state visitation counts (Poupart et al., 2006; Lopes et al., 2012; Bellemare et al., 2016) and state entropy objectives (Mohamed and Jimenez Rezende, 2015; Hazan et al., 2019; Lee et al., 2019; Pitis et al., 2020; Liu and Abbeel, 2021; Yarats et al., 2021) that incentivize the agent to reach "novel" states. Related, "curiosity"-based exploration bonuses encourage the agent to take actions in states where the effect is difficult to predict using a learned forward (Schmidhuber, 1991; Chentanez et al., 2004; Stadie et al., 2015; Pathak et al., 2017; Achiam and Sastry, 2017; Burda et al., 2018a) or inverse (Haber et al., 2018) dynamics model. Burda et al. (2018b) propose a random network distillation exploration bonus based upon the error in observation features predicted by a randomly initialized neural network.Temporally Extended Actions and Hierarchical RL: Another long line of work explores temporally extended actions due to the potential for such abstractions to improve learning efficiency. These advantages are particularly pronounced for difficult learning problems including sparse reward tasks, which is the focus of our work. In particular, action abstractions enable more effective exploration (Nachum et al., 2018) and simplify the credit assignment problem. Hierarchical reinforcement learning (HRL) (Dayan and Hinton, 1992; Kaelbling, 1993; Sutton, 1995; Boutilier et al., 1997; Parr and Russell, 1997; Parr, 1998; Sutton et al., 1999; Dietterich, 2000; Barto and Mahadevan, 2003; Kulkarni et al., 2016; Bacon et al., 2017; Vezhnevets et al., 2017) considers the problem of learning policies with successively higher levels of abstraction (typically two), whereby the lowest level considers actions directly applied in the environment while the higher levels reason over temporally extended transitions. A classic example of action abstractions is the options framework (Sutton et al., 1999) , which provides a standardization of HRL in which an option is a terminating sub-policy that maps states (or observations) to low-level actions. Options are often either prescribed as predefined low-level controllers or learned via subgoals or explicit intermediate rewards (Dayan and Hinton, 1992; Dietterich, 2000; Sutton et al., 1999) . Some simple instantiations of options include repeated actions (Sharma et al., 2017) and self-avoiding random walks (Amin et al., 2020) . Konidaris and Barto (2009) learn a two-level hierarchy by incrementally chaining options ("skills") backwards from the goal state to the start state. Nachum et al. (2018) propose a hierarchical learning algorithm (HIRO) that learns in an off-policy fashion and, in turn, is more sample-efficient than typical HRL algorithms, which learn on-policy. Achieving these sample efficiency gains requires addressing the instability typical of off-policy learning, which is complicated by the non-stationarity that comes with jointly learning low-and high-level policies. Levy et al. (2017) use different forms of hindsight (Andrychowicz et al., 2017) to address similar instability issues that arise when learning policies at multiple levels in parallel.Skill Learning from Demonstrations: In addition to the methods mentioned above in the context of HRL, there is an existing body of work that seeks to discover extended actions prior to their use in online RL, often called "skills". Many methods have been developed for skill discovery from interaction (Daniel et al., 2012; Gregor et al., 2016; Eysenbach et al., 2018; Warde-Farley et al., 2018; Park et al., 2022; 2023) . Most related to our setting is a line of work that explores extended action discovery from demonstration data (Lynch et al., 2020; Ajay et al., 2020; Singh et al., 2020; Pertsch et al., 2021; Bagatella et al., 2022) . As an example, Lynch et al. ( 2020) learn a VAE on chunks of action sequences in order to generate a temporally extended action by sampling a single vector. Ajay et al. (2020) follow a similar approach, but use flow models on top of entire trajectories, and only rollout a partial trajectory at inference time. Some of these methods (Ajay et al., 2020; Singh et al., 2020; Pertsch et al., 2021) condition on the observations when learning skills, which leads to more efficient exploration, but such conditioning means that any skill that is learned will need to be deployed in the same environment as the one in which the data was collected, resulting in poor domain transfer performance (Bagatella et al., 2022) . Others (Lynch et al., 2020; Bagatella et al., 2022) simply condition on actions, which means that the skills can be reused in any domain that shares the same action space. In an effort to learn more generalizable skills, we follow this latter example. There is also a related prior work that applies grammar-learning to online RL (Lange and Faisal, 2019) , but such a method learns an ever-growing number of longer actions, which poses significant issues in the sparse-reward setting, as we discuss later. 
method: 
 Similar to prior work (Lynch et al., 2020; Ajay et al., 2020; Singh et al., 2020; Pertsch et al., 2021; Bagatella et al., 2022) , we extract skills from demonstration data, more formally a dataset of N trajectories with lengths {n i } i2N that involve the same action space as our downstream taskD = (o ij , a ij ) i |i 2 N \ [0, N), j 2 N \ [0, n i ), o ij 2 R dobs , a ij 2 R dact ,where a ij and o ij denote actions and observations, respectively. After extracting skills from this dataset, we use these skills as a new action space for reinforcement learning on some downstream task. Crucially, our skills are unconditional so do not have any information as to when they should be used in the downstream task. In following sections we detail our exact method.Byte-pair encoding (BPE) was first proposed as a simple method to compress files (Gage, 1994) , but it has recently been used to construct vocabularies for NLP tasks in between the resolution of characters and whole-words (Sennrich et al., 2015) . With character vocabularies, the vocabulary is small, but the sequence lengths are large. Such long sequences are extremely burdensome to process, especially for the current generation of Transformers. In addition, making predictions at the character level imposes a more difficult task on the language model: it needs to spell everything correctly, ... ... ... ...Figure 2 : Abstract representation of our method. Given demonstrations in the same action space as our downstream task, we discretize the actions and apply tokenization techniques to recover "subwords" that form a vocabulary of skills. We then train a policy on top of these skills for some new task. We only require a common action space between demonstrations and downstream task.or make a long-coordinated set of predictions, not unlike the requirement on action sequences for sparse-reward exploration. Whole-word vocabularies shorten the sequence lengths and make the prediction task easier, but if a word is rare or, even worse, unseen in the training data, the outputs of the language model may not be correct in many cases. Subword vocabularies have emerged as a sweet-spot between these two extremes and are widely used in language models (Schuster and Nakajima, 2012; Sennrich et al., 2015; Kudo, 2018; Provilkov et al., 2020; He et al., 2020) .Given a long sequence of tokens and an initial fixed vocabulary, BPE consists of two core operations: (i) compute the most frequent pair of neighboring tokens and add it to the vocabulary, and (ii) merge all instances of the pair in the sequence. These two steps of adding tokens and making merges alternate until a fixed maximum vocabulary size is reached.In order to run BPE, it is necessary to have an initial vocabulary V as well as a string of discrete tokens. In a continuous action space, one simple way to form tokens is through clustering. Prior work has leveraged these ideas in similar contexts (Janner et al., 2021; Shafiullah et al., 2022; Jiang et al., 2022) and we follow suit. For simplicity, we perform k-means clustering with the Euclidean metric on the actions of demonstrations in D to form a vocabulary of k discrete tokens V = {v 0 , . . . , v k }.Our default choice for k will be two times the number of degrees-of-freedom (DoF) of the original action space, or 2 • d act . We will further study this choice in Appendix A.1. Such a clustering is the same as the action space of Shafiullah et al. (2022) without the residual correction.In NLP, we often have access to a large amount of text data from (mostly) correct human authors. However, for robotics applications we may not have the same quantity of near-optimal (or even suboptimal) demonstrations. As a result, it may be undesirable to merge tokens based on frequency alone. Thus, in addition to merging based on frequency, we implement a variant of our method that merges based on a proxy for the distance traveled in the observation space in order to encourage the creation of skills that explore diversely in state space and thus are efficient for tasks. We take inspiration from LSD (Park et al., 2022) and CSD (Park et al., 2023) for this choice. At the high sampling rate of continuous control observations, the observation space should be locally Euclidean, so such a measure makes sense as long as the length of skills is short enough. We label the two variants of our method as SaS-freq and SaS-dist respectively (SaS for Subwords as Skills).More formally, suppose that two neighboring subwords w 1 and w 2 correspond to the trajectories⌧ 1 = {(o 1 , a 1 ), . . . , (o n , a n )} and ⌧ 2 = {(o n+1 , a n+1 ), . . . , (o m , a m )}.For an instance of the subword w = concat(w 1 , w 2 ) consisting of the entire trajectory ⌧ = concat(⌧ 1 , ⌧ 2 ), we associate the vector q ⌧ = 1 m P m i=1 (o i o 1 ). This vector is analogous to the average "heading" of the subword, which ignores possible high-frequency, periodic motion like legs moving up and down. In order to obtain a vector that summarizes w, we compute the mean of such instances q w = E (⌧1,⌧2)2D [q ⌧ ], which takes into account possible observation noise at different instances.1: Given dataset D = {(o ij , a ij ) i |i 2 N \ [0, N), j 2 N \ [0, n i ), o ij 2 R dobs , a ij 2 R dact } 2: Given k, N max , N min , ✏ ⌧ 1 3: Run k-means on actions with k clusters to get tokens V = {v i } k i=1 4: Tokenize D according to V 5: Initialize W = {w i } k i=1 V, Q ?, q = 0, ⌃ q = I 6:// Merge vocabulary 7: while |W| < N max do 8:W 0 {All possible merges w = concat(w 1 , w 2 ) in D | w 1 , w 2 2 W} // Get candidates 9:for w 0 2 W 0 do 10:Compute w 0 = arg max w 0 2W 0 (q w 0 q) > ⌃ 1 q (q w 0 q) // Find best possible merge 13: w 0 = arg min w 0 2W (q w 0 q) > ⌃ 1 q (q w 0 q) // Find most redundant subword 20:q w 0 = E instances of w 0 in D h 1 L P L = length of w 0 r=1 o ir o i1 i //W W [ {w 0 }, Q Q [ {q w 0 } // Add merge to vocabulary 14: q E q2Q [q], ⌃ q Cov q2Q (q) + ✏I //W W \ {w 0 }, Q Q \ {q w 0 } // Remove worst 21: q E q2Q [q], ⌃ qCov q2Q (q) + ✏I // Update vocabulary mean and covariance 22: end while 23: 24: return W Given an existing vocabulary of subwords W = {w 0 , . . . , w n 1 } and their corresponding vectors Q = {q 0 , . . . , q n 1 }, we can compute the mean q = E q2Q [q] and covariance matrix ⌃ q = Cov q2Q (q) + ✏I for some small ✏. Now, we associate a score to each possible new subword according to the Mahalanobis distance between the candidate subword and the set of existing subwords: d w = (q w q) > ⌃ 1 q (q w q). We add the subword with maximum distance d w to our vocabulary. We update ⌃ q and q at every iteration. This results in a growing vocabulary of subwords that not only achieve high distance in observation space but are diverse. Such a scoring function also accounts for the fact that different parts of the observation space may have different natural scales. We merge up to a maximum vocabulary size |W| = N max . The choice of N max is further studied in Appendix A.2.If we stopped after merging to a maximum size, the final vocabulary would contain the intermediate subwords that make up the longest units. In the context of NLP, this redundancy may not be particularly detrimental. In reinforcement learning, however, redundancy in the action space of a new policy will result in similar actions competing for probability mass, making exploration and optimization more difficult. Thus we propose pruning the vocabulary.For frequency-based merging, we start with the longest subword, and remove subwords that are strictly contained in it, then move to the next longest and repeat the process. We do this until we reach the desired vocabulary size N min .For distance-based merging, we prune the set of subwords using the same metric as was used to merge. In particular, we find w 0 = arg min w d w , update W W \ {w 0 }, and recompute ⌃ q and q. We continue pruning in this fashion until reaching a minimum vocabulary size |W| = N min . Finally, W becomes the action space for a new policy. Algorithm 1 provides the pseudocode for the distance-based method, and Figure 2 provides a graphical representation. We ablate the choice of N min in Appendix A.3. Implicit in our method is an assumption that portions of the demonstrations can be recomposed to solve a new task, i.e., that there exists a policy that solves the new task with this new action space. One can imagine a counter-example where the subwords we obtain lack some critical action sequence without which the task cannot be solved. Still, we will show that this is a reasonable assumption for several sparse-reward tasks. 
experiments: 
 In the following sections, we explore the empirical performance of our proposed method: first extracting skills from data, then using those skills as an action space for learning a new policy through sparse-reward RL. We see that there are significant speed and performance benefits, with strong exploration behavior. We also discuss benefits and drawbacks of our unconditional skills when compared to conditional skills like those of SPiRL (Pertsch et al., 2021) .Table 1 : Main comparison (unnormalized scores). SSP corresponds to results from official code of Pertsch et al. (2021) . We report numbers at the end of training for consistency. SFP takes so long it is unmanageable on many domains. AntMaze is scored 0-1, Kitchen is scored 0-4 in increments of 1, CoinRun is scored 0-100 in increments of 10. ⇤ CoinRun is a discrete-action domain, so instead of SAC only SAC-discrete can be used. SSP results exist for Kitchen, (0.8±0.2 (Pertsch et al., 2021 , Figure 4 )), but we are unable to reproduce this number using official code. Tasks: We consider AntMaze and Kitchen from D4RL (Fu et al., 2020) , two challenging sparsereward state-based tasks/datasets. AntMaze is a maze navigation task with a quadrupedal robot where the reward is 0 except for at the goal, and Kitchen is a manipulation task in a kitchen setting where reward is 0 except for on successful completion of a subtask. Demonstrations in AntMaze consist of random start and end states in the same maze collected by a suboptimal scripted policy, while demonstrations in Kitchen consist of different sequences of subtasks than the eventual goal in the same kitchen collected by humans in VR. We also consider CoinRun (Cobbe et al., 2019) , a discrete-action platforming game. Unlike AntMaze and Kitchen, CoinRun is a visual domain and the demonstrations are collected by humans in distinct levels than the final task. All of these domains require many coordinated actions in sequence to achieve any reward, with horizons between 280 and 1000 steps. See Appendix E for more information on the data.Baselines: We consider SAC (Haarnoja et al., 2018b) ; SAC-discrete (Christodoulou, 2019) on top of our discretized k-means actions; Skill-Space Policy (SSP), a VAE trained on sequences of 10 actions at a time (Pertsch et al., 2021) ; and State-Free Priors (SFP) (Bagatella et al., 2022) We see in Table 1 , that even in these challenging sparse-reward tasks, our method is the only one that is able to achieve nonzero reward across all tasks. All settings with zero reward fail to achieve any reward during training. The large standard deviations are due to the fact that some seeds fail to achieve any reward. Figure 3 visualizes 200-step rollouts of all of the discovered subwords for antmaze-medium-diverse. We provide mean and standard deviations for subword lengths in extracted vocabularies in Table 2 . Failures of frequency-based merging in AntMazes are directly attributable to the discovery of long, constant sequences of actions, likely due to suboptimal demonstration trajectories that often jitter in place. Due to the simplicity of our method, it also enjoys significant acceleration compared to the baselines. In Table 3 , we measure the wall-clock time required to generate skills, as well as inference for a single rollout. We see that our method achieves extremely significant speedups compared to prior work, achieving both faster and more efficient learning, as well as faster inference during execution. Our skill discovery is fast as we simply need to run k-means and tokenization. SSP and SFP require training larger generative models. In the case of rollouts our method predicts an entire sequence of actions using a simple policy every 10 steps or so, while SSP and SFP require much larger models in order to predict the latent variable, and then generate the next action from that latent. The speedup of our method also translates to faster RL (around 10 hours for our method vs. 12 hours for SSP and 1 week for SFP), which leads to faster iteration.The stringent evaluation procedure for sparse-reward RL equally penalizes poor learning and exploration. In order to shed light on the many zeros in Table 1 , we examine the exploration behavior on AntMaze Medium. We choose this domain because it is particularly straightforward to interpret what good and bad exploration looks like: coverage of the maze. In Figure 4 and Figure 5 we plot state visitation for the first 1 million of 10 million steps of RL. We show the approximate start position in grey in the bottom left and the approximate goal location in green in the top right. Higher color intensity (saturation) corresponds to a higher probability of that state. Color is scaled nonlinearly according to a power law between 0 and 1 for illustration purposes. Thin white areas between the density and the walls can be attributed to the fact that we plot the center body position, and the legs have a nontrivial size limiting the proximity to the wall.In Figure 4 , we show the exploration behavior across methods, averaged over 5 seeds. We see that the 0 values for the final reward in Table 1 for SAC, SSP and SFP are likely due not to poor optimization, but rather poor exploration early in training, unlike our method. One reason for this could be due to the fact that our subwords are a discrete set, so policy exploration does not include small differences in a continuous space. In addition, SAC has fundamental issues in sparse-reward environments as the Figure 5 : State visitation achieved with our method for each of the 5 individual seeds. Notice the diversity of exploration behavior. This is true even for seeds 0, 2 and 3 that, as reflected in the standard deviations in Table 1 , eventually finish with a final reward of 0.signal to the Q function is driven entirely by the entropy bonus, which will lead to uniform weighting on every action and as a result Brownian motion in the action space. Such behavior is likely why the default setting for SAC (Haarnoja et al., 2018b) aggressively drives the policy to determinism, but in the sparse reward setting this also results in a uniform policy. Without long sequences of coordinated actions such exploration is insufficient.In Figure 5 , we show the individual seed visitation of our method in the first 1 million steps. This is to demonstrate that, even though individual seeds may have some bias, they all are able to explore much more widely than the collective exploration of baseline methods. Indeed, this suggests that the large standard deviations of our method are a result of an optimization failure, as suggested by Zhou et al. (2022) , and not poor exploration due to bad skill-encoding.Our method for extracting skills is an unconditional, open-loop method with the idea in mind that the skills should generalize. Still, this comes with the drawback that a policy will have to learn the right context to deploy skills from scratch. Alternatively, observation-conditioned skills bias policy exploration to match that of the demonstrations. This allows for more stable exploration, but worse generalization (Bagatella et al., 2022) .Baselines: Here we compare to observation-conditioned extension of SSP, SPiRL and SPiRL-cl (the closed-loop version) (Pertsch et al., 2021; 2022) which bias a policy toward skills used in the exact context of demonstrations in the dataset. We also include OPAL (Ajay et al., 2020) , a similar method to SPiRL, a flow model for entire trajectories of actions that is conditioned on observations. We take numbers from the paper as OPAL is closed-source.In Table 4 , we see that SPiRL and SPiRL-cl show very strong performance on Kitchen, where the overlap between the dataset and the downstream task is exact, but SPiRL fails on AntMaze-large, while SPiRL-cl fails on CoinRun, likely due to differences between the dataset for CoinRun (easy levels) and the downstream task (hard levels). In addition we notice that BPE with simple frequency (Pertsch et al., 2022) ), but for SPiRL our result is significantly worse (2-3 in the original paper (Pertsch et al., 2021) ). It is unclear from where this discrepancy stems, but we use the official code, for which Kitchen is already implemented.In addition, we examine generalization behavior across observation-conditioned methods. Table 5 highlights the drawback that conditioning has in generalization. In particular the strongest advantage for conditional skills is in a setting where the data closely matches the final task, but it may be detrimental when we do not have access to sufficiently general demonstrations, like the ⇠10,000 trajectories in randomized environments that SPiRL uses for visual PointMaze (Pertsch et al., 2021) .Table 5 : Results on transferring skills extracted from antmaze-medium-diverse to downstream RL on antmaze-umaze-diverse. We see that methods with conditioning (SPiRL and SPiRL-cl) underperform our simple unconditional method. Similar conclusions were drawn by the authors of SFP (Bagatella et al., 2022, Figures 7, 16) , where stronger conditioning fails to generalize.  
conclusion: 
 Limitations: As proposed, there are a few key limitations to our method. Discretization removes resolution from the action space, which may be detrimental in settings like fast locomotion (Appendix H), but this may be fixed by more clusters or a residual correction (Shafiullah et al., 2022) . In addition, like prior work execution of our subwords is open loop, so exploration can be inefficient (Amin et al., 2020) and unsafe (Park et al., 2021) . Finally, in order to operate on the CoinRun domain, we downsample inputs from 64 ⇥ 64 resolution to 32 ⇥ 32 to make matrix inversion during merging less expensive (2 hours vs. 2 minutes). In high-dimensional visual input domains, our merging may be too computationally expensive to perform. However, this can be resolved by using neural network features instead of images. We also speculate that higher-quality demonstrations could allow us to generate skills simply by merging based on frequency (Table 1 , CoinRun), and these demonstrations may be easy to obtain if they don't need to be collected in the deployment domain (Table 5 ).Architectures from NLP have made their way into offline RL (Chen et al., 2021; Janner et al., 2021; Shafiullah et al., 2022) , but as we have demonstrated, there is a trove of further techniques to explore. Given prior evidence, and the experiments in Appendix C, that discretization can be helpful in offline RL, we leveraged such discretization to form skills through a simple tokenization method. Such a method is much faster both in skill generation and in policy inference, and leads to strong performance in a relatively small sample budget on several challenging sparse-reward tasks. Moreover, the discrete nature of our skills lends itself to interpretation: one can simply look at the execution to figure out what has been extracted (Appendix B). Given its many advantages, we believe that such a tokenization method is the first step on a new road to efficient reinforcement learning. 
 
 Appendix:  


Decision: This paper tackles reinforcement learning (RL) through a skill-learning framework to overcome the issue of needing to learn from sparse rewards collected only after a long, coordinated sequence of actions. The paper's approach is inspired by Byte-Pair Encoding (BPE) from natural language processing (NLP) to extract skills from demonstrations for re-use in RL. The paper shows that skills can be extracted from a small subset of the demonstrations and transferred to a new task. 

The reviewers felt that the paper was interesting and warranted consideration. The reviewers appreciate the paper's originality, quality, clarity, and significance. However, reviewers also had concerns about the drift that can occur in a stochastic environment when focusing only on high-level actions (one reviewer with this concern raised their score), limited baselines, need for an improved presentation, reliance upon a high-quality dataset, no guarantees, computational complexity, insufficient details, and concerns about scalability.

The authors did a good job in seeking to improve the reviewers' assessments. 

Remaining concerns after the rebuttal included a point about the inability to confirm the sufficiency of discovered skills to form a good policy and that the analogy of BPE in NLP translated to RL might not be an exact fit due to an inability to express the space of continuous control policies in robotics. Reviewers felt it might have been better to show a greater variety of tasks performed on the same robot embodiment.  However, other reviewers disagreed, arguing the current results were sufficient, and multiple reviewers argued for acceptance.

Reviews: review: paper_summary: paper_summary: The paper titled "Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learning" introduces a novel method for skill extraction from demonstrations to address the challenge of exploration in sparse-reward reinforcement learning (RL). Inspired by the Byte-Pair Encoding (BPE) algorithm used in natural language processing, the authors propose a method to generate skills that can be used to accelerate both skill extraction and policy inference in RL tasks. The proposed method demonstrates strong performance in various tasks, providing up to 1000× acceleration in skill extraction and 100× acceleration in policy inference. The method also shows potential for skill transfer across loosely related tasks and generates a finite set of interpretable behaviors.
strength_weakness: strength_weakness: 1. Stochasticity of the Environment

The impact of the environment stochasticity raises concerns. Since the method treats sequences of low-level actions as high-level actions, the cumulative effect of each low-level action can vary significantly in highly stochastic environments. For instance, if there is a 50% chance of wind blowing the agent off course, the resulting states from executing a single high-level action could vary greatly, potentially harming the algorithm's performance. The current evaluation environments, such as AntMaze and Kitchen, seem to have relatively low stochasticity. To strengthen the paper, it would be beneficial to include evaluation results from highly stochastic or procedurally generated environments, such as DMLAB30.

2. Intuitive Explanation of BPE Advantage

The paper would benefit from more intuitive explanations regarding why skills discovered using Byte-Pair Encoding (BPE) can outperform those discovered through simple k-means clustering. While BPE is known for its hierarchical and incremental construction of subwords in language processing, clarifying how these characteristics translate to improved skill discovery in reinforcement learning would enhance the understanding of the proposed method's advantages.
questions: questions: 1. Effect of Stochasticity on Algorithm Performance

How do you think the about stochasticity of the environment affects the algorithm's performance? Given the potential variability in outcomes when low-level actions are aggregated into high-level actions, understanding this impact is crucial.

2. Intuition Behind BPE Benefits

Can you provide some intuition on how BPE can be beneficial for skill discovery in reinforcement learning? Understanding the specific advantages of BPE over simpler methods of forming high-level actions like k-means clustering would help clarify the strengths of the proposed approach.
limitations: limitations: The authors acknowledge several limitations of their work:

1. **Resolution Loss Due to Discretization**: The discretization step in the skill extraction process reduces the resolution of the action space, which might not be suitable for tasks requiring fine-grained actions.
2. **Open-Loop Execution**: The method involves open-loop execution of subwords, which can lead to inefficient and unsafe exploration in certain scenarios. This limitation highlights the need for incorporating feedback mechanisms in future iterations of the method.

The paper does discuss these limitations openly.
paper_summary: paper_summary: This paper presents a novel method for skill discovery in reinforcement learning by leveraging tokenization techniques from Natural Language Processing (NLP). The approach involves discretizing the action space through clustering, and then using byte-pair encoding to generate temporally extended actions. The method is evaluated on various environments including AntMaze, Kitchen, and CoinRun, demonstrating improved performance over some state-free skill learning baselines and vanilla SAC.
strength_weakness: strength_weakness: While the paper demonstrates several strengths, there are also potential limitations and areas for improvement:

- The range of baseline skill discovery methods could be expanded. Additional algorithms, such as those proposed in [1] and [2], merit consideration.

- The presentation requires refinement. The current format of tables and figures impedes clear interpretation, potentially obscuring the full efficacy of the proposed method.

- The effectiveness of the skill discovery process appears to be heavily contingent on the specific dataset utilized. A more comprehensive exploration of dataset variability and its impact on outcomes would strengthen the study.

- There is no formal guarantee that the discovered skills are sufficient to construct an optimal policy. This theoretical limitation warrants acknowledgment and discussion.

- The computational complexity of the merging process may prove prohibitive for high-dimensional input domains, potentially limiting the method's scalability.

- It is unclear how the method would perform with larger, more diverse datasets that might require a larger skill space. This leaves questions about the approach's generalizability unanswered.

[1]  Y. Jiang, E. Z. Liu, B. Eysenbach, Z. Kolter, and C. Finn, “Learning options via compression,” arXiv preprint arXiv:2212.04590, 2022.

[2] A. Singh, H. Liu, G. Zhou, A. Yu, N. Rhinehart, and S. Levine, “Parrot: Data-driven behavioral priors for reinforcement learning,” arXiv preprint arXiv:2011.10024, 2020.
questions: questions: See the "Weaknesses" section.
limitations: limitations: The authors have discussed a few limitations in the paper.
paper_summary: paper_summary: This paper uses Byte pair encoding to create a discretised action space for RL from demonstrations. The authors show that Byte pair encoding can:
* improve exploration in sparse reward settings
* creating the skill action space is computationally cheap compared to methods that train deep learning models
* their approach is not conditioned on observation, which improves generalisation
strength_weakness: strength_weakness: It is difficult for me to understand the baselines and some details of the experiments. For example, its not clear how many demonstrations are used for each of the methods. Presumably as it only using k-means and BPE, it can work with a small number of demonstrations (this is hinted at on the skill transfer results). I assume for example, that offline RL methods cannot be used because the dataset of demonstrations is too small? It would be good to explain these basics to someone (like me) who is not familiar with this subfield.

Also, from the paper alone, I cannot tell whether the baselines are the state of the art approach for skill extraction.

To help with these weaknesses I would like:

* details on the number of demonstrations used
* more explanation of what the baselines are and how they work

For the transferring skills, it would be good to run the baseline (even if it is very poor) to plot in figure 6.
questions: questions: How important is using K-means clustering before the byte pair encoding?

Could use simpler disrectisation approaches (e.g. like the one used in the continuous control experiments here: https://arxiv.org/abs/2107.05431)

They mention filtering demonstrations
limitations: limitations: The paper does not have an explicit limitations section, which I think it could benefit from. For example, I would like to see a discussion of how this approach compares to settings where there is a very large amount of data to train offline RL agents. How does it compare then? In general, I would like to understand when this approach is the most suitable given data and simulator constraints.

I would also like to understand a little better how far this approach can go. For example, are there tasks at which point the vocab becomes filled very quickly and this approach is not applicable?
paper_summary: paper_summary: This paper presents a method which discretizes action trajectories from offline data into skills through a BPE-inspired tokenization method. These discrete action trajectory skills are given directly to a high-level agent to utilize for solving downstream tasks.
strength_weakness: strength_weakness: **Method:** 

- One limitation of this method is that it *cannot be state conditioned*. Figure 5 clearly demonstrates that state-conditioned methods that can utilize state-based priors (e.g., SPiRL) can perform much better depending on the problem setting (Franka Kitchen, where there is a lot of overlap between the pre-training data and testing environment). On the other hand, methods like SPiRL can also be used without state-conditioning. This thus is less flexible in this regard.
- Another limitation that stems from the comparison in the introduction against large language models and NLP is that in NLP, associations between text tokens are learned during pre-training time and then utilized for downstream tasks. The authors’ method does not utilize this intuition despite being influenced by NLP. Instead, the policy must learn how to associate the action sequence tokens from scratch during RL training time, possibly wasting many environment steps just learning the associations. One way to fix this would be to learn some state-conditioned associations between skills/some prior over how to associate discrete action sequences together.
questions: questions: - Why choose a specific desired length $L=10$ for the action sequences? A more flexible method would be able to use skills of varying lengths to better solve the task like https://openreview.net/pdf?id=r4XxtrIo1m9 or the already cited CompILE work by Kipf et al. It seems like the proposed method could easily be adapted for variable length skills too.
- Why are the ablations performed on Hopper (appendix D + E) but no Hopper experiments are in the main paper?
- Because this came out ~3 months before neurips submissions, it seems reasonable the authors did not cite it yet. But, this paper https://arxiv.org/abs/2402.10450 is extremely similar in the use of BPE for creating skills to use for downstream policy learning. How does your method compare to this?

As such, when using the NeurIPS rating scale, I'm currently giving this paper a 6 because I believe it is of moderate impact (results are adequate, method is nice and simple, but I'm not sure it would be considered high-impact, i.e. a 7, and there are some flaws and remaining questions).
limitations: limitations: Sufficiently addressed

Comments: title: Reviewer g8NK
comment: Can the reviewer kindly engage with the authors?
Thank you for your reply, we appreciate the engagement. We're also happy that our rebuttal was able to change your opinion of the paper for the better. We agree that stochastic environments are an interesting direction, and in particular the idea of learning a residual correction on top of the low-resolution actions is something we may explore in the future.
Thank you for your responses, and I apologize for the late reply. After reading your rebuttal, I decided to increase the rating from 5 to 6. However, I still believe that exploring a systematic approach to dealing with highly stochastic environments could be an interesting direction.
We wanted to reach out to see if you had any remaining questions given that the discussion period wraps up in a few hours. 

Thank you again for your positive feedback.
A friendly bump as there are only a few hours left in the discussion period.
Thank you again for your feedback. 

The discussion period ends in a few hours. We would appreciate it if you could share any additional comments/questions you may have in light of our rebuttal above so that we can respond to them.
We made a concerted effort to address each of the issues that the reviewer raised and, while we respect the reviewer’s opinion, we would appreciate a justification for the decision. In our rebuttal we address all concerns and, with all due respect, we find a number of them to be broad or vague.

As an example, when the reviewer says “the presentation requires refinement” without details as to specific changes desired, it is in direct contradiction to all other reviewers who praised the clarity of the presentation, thus it would be helpful to make specific comments.

In addition, the comment that “computational complexity... may prove prohibitive in high dimensional input domains” is factually inaccurate. The current method scales quite nicely to high-dimensional action spaces as it only relies on K-Means, which has minibatch approximations in high dimensions.

We already make these points in our rebuttal above, along with addressing other concerns. We understand that the reviewer has other commitments, but we would appreciate if they took the time to provide substantive feedback and a justification for their decision.
We are glad that our response was able to answer your questions and change your opinion of the paper for the better. Thank you for the engagement and careful read.
Thanks for the response. I will maintain my original score.
Thanks for the rebuttal, my questions are answered and I'll be raising my score to a 7.