Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learning
Authors: David Yunis
Justin Jung
Falcon Z Dai
Matthew Walter
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Deep Learning
Exploration
Hierarchical RL
Primary area: reinforcement_learning
TL;DR: Tokenization methods from NLP lead to much faster skill-extraction which can help solve very difficult sparse-reward RL tasks.

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.

Subwords as Skills: Tokenization for Sparse-Reward Reinforcement Learning
David Yunis TTI-Chicago Chicago, IL dyunis@ttic.edd edu
Justin Jung" Springtail.ai San Francisco, CA justindspringtail.e
Falcon Z. Dai
Matthew R. Walter TTI-Chicago Chicago. IL
Symbolica AI
San Francisco, CA
felcondaymmolica.ce
mwalter@ttic.edu
Abstract
Exploration in sparse-reward reinforcement learning (RL) is difficult due to the need for long, coordinated sequences of actions order to achieve any reward. Skill learning, from demonstrations interaction, is promising approach address this, but skill extraction and inference are expensive for current methods. We present 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, show strong performance in variety tasks, x000 accelcration for skill-extraction and 100x acceleration for policy inference. Given the simplicity of 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 method yields finite set of interpretable behaviors. Our code is available at https:/ //gi thub. com/ com/dyun wtwpii///swooodssseeeeaess skills.
(a) AntMaze
(b) Kitchen
Figure 1: sample of some "skills" that our method identifies for the (a) AntMaze and Kitchen environments, where color is darker for poses earlier in the trajectory. Skills consist of linear motion and turning in AntMaze, and reaching and pulling motions in Kitchen. Our method discovers a finite inventory of skills, so it is possible to visualize and interpret them.
Introduction
The reinforcement learning (RL) paradigm, that allows an agent to interact with an a priori unknown environment and collect its own data, is promising approach to learning in many domains where high-quality data collection financially too expensive otherwise intractable. Though it began with dynamic programming in tabular settings, the recent use of neural networks as function approximators has led great success on many challenging learning tasks [47, 71, 26]. Typically, these successes owe to particular properties of the tasks. In some cases, it is simple to define reward function that provides an informative learning signal every step of interaction (the dense-reward setting),
Work done while University Chicago.
Work done while at Toyota Technological Institute at Chicago (TTI-Chicago).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

like directional velocity of a robot learning to walk [27]. In other cases, an environment model can aid search, as in the case of Chess or Go [71]. In all cases access to fast simulator is paramount. However, for many natural tasks tell when the task is completed than to supervise each individual step or model the environment dynamics. Learning in these sparse-reward settings, where an informative 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 find reward, which requires long periods of exploration, often in a coordinated fashion. One solution to the sparse-reward problem is to engineer proxy dense- reward, but that requires significant expertise and can lead to undesired reward-hacking [73].
teaching a robot to make an omelet-it is much simpler to
Another class of solutions to the exploration problem aims to create temporally extended actions, or "skills", from interaction [69, 22, 51, 52] or demonstrations [38. 72, 57, 2, 6, 46]. Formally,
0. (3) of related behavior to the desired task, we want extract new action space A' - 1 consisting of sequences of the original action space, and then find a policy for the desired task using this action space, S + A'. Current methods for skill-extraction rely on neural networks, which require large numbers of demonstrations and expensive training.
given dataset of demonstrations D {
(4) 0 (2)
(2)
Like the long-range coordination required for exploration in sparse-reward RL, language models must model long-range dependencies between discrete tokens. Finer-grained character input leads to extremely long sequences and requires low-level modeling; coarser-grained word-level input results in the model poorly capturing rare and unseen words. The standard solution for language models is to create "subword" tokens somewhere in between individual characters and words, that can express any text [24, 67, 62, 39, 66, 31].
Lifting this idea from language modeling to RL, propose tokenization method for skill-learning from demonstrations: Subwords as Skills (SaS). Following prior work [18, 68], we discretize the action space where necessary and use simple byte-pair encoding (BPE) scheme [24, 67] to obtain temporally extended actions. Then, we use this subword vocabulary as the action-space for online RL. As we demonstrate, such a method benefits from extremely fast skill- gelllaeeeerttion (seconds v.s. hours for neural network-basse methods), 100x faster rollouts due to the lack of an extra neural network during inference, and strong results in several sparse-reward domains. Additionally, we demonstrate transfer of skills collected in a different environment and we interpret the finite set of skills. Code is available for experiments at https: / /ttp//gttttttt///////////
thub. com/ hoom/dyniss dyunis/suboorde suwwwodds. as as_ skills.
2 Related Work
Exploration in RL: Exploration is fundamental problem in RL, particularly when reward is sparse. common approach to encouraging exploratory behavior is augment the (sparse) environment reward with a dense bonus term that biases toward exploration. This includes the use of (possibly approximate) state visitation counts [61, 45, 9, 13] and state entropy objectives [48, 30, 42, 60, 44, 79] that incentivize the agent to reach "novel" states. Related, "curiosity" -bbsed bonuses encourage the agent to take actions in states where the effect difficult to predict using a learned forward [65, 15, 74, 56, 1, 12] or inverse [29] dynamics model.
Temporally Extended Actions and Hierarchical RL: Another long line of work proposes action abstractions to enable more effective exploration [49] and simplify the credit assignment problem. Hierarchical reinforcement learning (HRL) [20, 34, 75, 11, 53, 54, 76, 21, 8, 40, 5, 77] considers the problem of learning policies with successively higher levels of abstraction, where the lowest level considers primitive actions in the environment and the higher levels reason over temporally extended transitions. A classic example of action abstractions is the options framework [76], which provides a standardization of HRL in which an option is terminating sub-policy that maps states (or observations) to low-level actions. Options can be prescribed as predefined low-level controllers or learned via intermediate rewards [21, 20, 76]. Some simple instantiations of options include repeated actions [70] and avof-dvoiding random walks [3]. Konidaris and Barto [37] learn a two-level hierarchy by incrementally chaining options ("skills"") backwards from the goal state to the start state. Nachum et al. [49] propose hierarchical algorithm that learns in sample-efficient, off-policy fashion. Such gains require addressing normal off- off-policy instability and non-stationarity that comes with jointly learning low- and high- policies. Levy et al. [43] use different forms of hindsight [4]
2

---

Demos
Tokenization
Skills
RL over Skills
ES
<>>>>>>>>>>>>
T
<ab>
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 technique to recover "subwords" that form vocabulary of skills. We then train a policy on top of these skills for new task. We only require common action space between demonstrations and the downstream task.
to address similar instability issues that arise when learning policies at multiple levels in parallel. One particularly related work applies grammar-learing to online RL [41], but such method learns an ever-growing number of longer actions which is problematic in the sparse-reward setting.
Skill Learning from Demonstrations: In addition to the methods mentioned above in the context of HRL, there an existing body of work that seeks to discover extended actions (skills) prior to. instead of during, online RL. Many methods have been developed for skill discovery from interaction [19, 25, 22, 78, 51, 52]. Most related to our setting is line of work that explores skill discovery from demonstrations [38, 46, 2, 72, 57, 6]. As example, Lynch et al. [46] learn VAE [36, 64] on chunks of action sequences order to generate temporally extended action by sampling single vector. Ajay et al. [2] follow a similar approach on top of entire trajectories and only rollout a partial trajectory at inference time. Some these methods [2, 72, 57] condition on the observations when learning skills; however, such skills transfer poorly across domains unless they are trained on randomized environments [57, 6]. Others [46, 6] simply condition on actions, which means that skills can be reused in any domain that shares the same action space. To extract more generalizable skills, we follow the latter approach. While a concurrent work [80] uses a method similar to ours in order to discover skills for supervised learning and transfer learning, focus the use of tokenization for online RL.
Method
Similar to prior work [46, 2, 72, 57, 6]. we extract skills from demonstration data of action sequences. Formally, these sequences are a dataset of N trajectories with lengths [n:) action space as our downstream task:
N. that involve the same
D= (ag)iii [J, (I,...,n), 0₃ E ACC
where aj denotes an individual action. After extracting skills from this dataset, we use these skills as the new action space for reinforcement learning on downstream task. Crucially, our skills do rely on observations in the demonstrations, which allows them to transfer to different environments even with very little data. In following subsections we detail our precise method.
3.1 Byte-Pair Encoding
Byte-pair encoding (BPE) was first proposed simple method to compress files [24], but it has recently been used to construct vocabularies for NLP tasks with a resolution in between characters and whole-words [66, 67, 39, 62, 31].
Given long sequence of tokens (e.g., characters) 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 instances the pair in the sequence. These two steps of adding tokens and merging alternate until desired vocabulary size is reached.

---

3.2 Discretizing the Action Space
BPE requires an initial vocabulary V and data formatted string of discrete tokens. Clustering is simple way to form discrete tokens from continuous action space. Prior work has leveraged these ideas in similar contexts [32, 68, 33] and we follow suit. For simplicity, we perform k-means clustering with the Euclidean metric on the actions of demonstrations in 'D to form vocabulary of & discrete tokens = fvo.... }... Our default choice for & will be two times the number of degrees-of freedom (DoF) of the original action space, or 2 x dact. We further study this choice in Appendix 4.5, Such clustering is the same as the action space of Shafiullah et al. [68] without the residual correction.
3.3 Merging and Pruning the Subwords
After discretizing the action space (if continuous), we can relabel our demonstrations so that trajecto- ries consist of "strings" of action tokens. Then, we can run BPE [24] with large final vocabulary size on these strings to extract skills.
As it runs, BPE keeps all intermediate subwords that make up the longest units. In the context of language, this redundancy may not be particularly detrimental. However, in reinforcement learning redundancy in the action space of a policy will result in large number of similar actions that compete for probability mass, making exploration and optimization difficult. Thus, we prune the BPE vocabulary
much smaller size.
To prune our vocabulary to a size Ninns we choose a desired maximum length of skills, say L. = 10 actions long. For our pruned vocabulary, we take the first Nmin subwords of length L that were found by BPE. If there are only m < Nmin subwords of length discovered, we then take the first Nmio - m subwords of length L - 1, and so on until we reach the desired vocabulary size of N We choose certain length because by the design of BPE, those will be the most frequent
the first subwords units of that length. If our demonstrations contain common and useful behavior, these will be the most frequent chunks. We provide an algorithmic description of our entire skill-extraction method in Algorithm 1.
Implicit in our method is an assumption that portions of the demonstrations can be recomposed to solve new task, i.e., that there exists policy that solves the new task with the action space that we choose. One can imagine a counter-example where the subwords we obtain lack some critical action sequence without which the new task cannot be solved, either because it is lacking in the demonstrations or because extraction imperfect. Still, we will show that this assumption is reasonable for several sparse-reward tasks.
4 Experiments
In the following sections, we demonstrate the empirical performance of our proposed method: first extracting skills from demonstrations and then using those skills as an action space for online sparse- reward RL. Unlike common methods for offline RL, we do not any information about observations or reward in the demonstrations. We see that our extracted skills provide significant speed benefits and sensible exploration behavior. We also compare our observation-free unconditional skills to Abservation-coodiiione skills and discuss performance. We then examine the transfer setting, where demonstrations come from different domain. Finally, present an ablation of hyperparameters.
4.1 Reinforcement Learning with Unconditional Skills
Tasks: We consider online RL on AntMaze and Kitchen from D4RL [23], two very challenging sparse- reward state-based environments. AntMaze a maze navigation environment with a quadrupedal robot where the reward is 0 except for at the goal, and Kitchen is manipulation environment in kitchen setting where reward 0 except for on successful completion of a subtask. Demonstrations in AntMaze consist of trajectories between random start and end states in the same maze, while demonstrations in Kitchen consist of different sequences of subtasks than the eventual task. We also consider CoinRun [17], a discrete-action platforming game. Unlike AntMaze and Kitchen, CoinRun visual domain and the demonstrations are collected in levels distinct from those of the final task. All of these domains require many coordinated actions in sequence to achieve any reward, with

---

Algorithm Skill-extraction with BPE
1: Given action-only demonstrations D {(a))ili (I,.., N), (i,,,,,), ag E A C Rdx)
2: Given number of clusters max vocab size Naxx skill length L, desired vocab size Nin
3:
4: if' the action space is not discrete, i.c. Vj, 0j $ N then
5: Run k-means on actions with clusters to get discrete actions V = [1
6: Replace aj in D with closest discrete action index, aj t argminggtsullog 1ll2
7: else
8: Use the discrete action space as seed vocabulary V + A
9: end if
10:
Initialize subword vocabulary W V
12: while [W] < N Mmx do
13: Find most common pair of neighboring subwords ws, w E W demonstrations
14: Merge pair into a new subword, w' concat wn, wy), and add to vocabulary, W <- WU (w'
15:
Relabel demonstrations D, replacing sequences of (wy, wy) with w/
16:
end while
17:
18: Initialize final vocabulary W =
19: while [W'| Nuin do
20: n f number of subwords w E W with length
21: W" < W U (first min(n, Nmin [W subwords of length L that were merged)
22:
6-L-1
23:
end while
24:
return W
520
264
6:6
62
02
SAC4
C22
25.
5i05s
Stapa
Steps
(a) AntMaze-U
(b) AntMaze-M
(c) AntMazeLL
(d) Kitchen
(c) CoinRun
Figure 3: Main comparison (unnormalized scores). SSP corresponds to results from official code of Pertsch et al. [57], SSP-p corresponds to published results. AntMaze is scored 0-1, Kitchen is scored 004 increments of 1, CoinRun scored (-1100 in increments of 10. CoinRun is a discrete- action domain, instead of SAC only SAC-discrete can be used. We see strong performance when compared to baselines across tasks.
horizons between 280 and 1000 steps. See Appendix A for more information on the tasks and data. Due to the suboptimality of demonstrations AntMaze, we filter demonstrations to remove portions that correspond to jittering in place.
Baselines: We consider SAC [28]; SAC-discrete [16] on top of our discretized k-means actions;
Skill-Space Policy (SSP), a VAE [36, 64] trained on sequences of 10 actions at time [57]; and State-Free Priors (SFP) [6], sequence model of actions that is used to inform action-selection during SAC inference. For SAC method. For SSP we use the official implementation [59] and tune hyperparameters for new domains. For SFP we use official code [7], and are unable to tune hyperparameters due very large runtimes. Figure 3 provides the complete set of results. We report mean and standard deviation across five seeds. As defaults for our method, we use k- = 2 x d and Nmin = 16. We choose Nmux = 10 so that we always find sufficiently many skills with the desired length L == 10, which we choose to be comparable with SSP's length 10. We ablate these choices Appendix 4.5. For more experimental details and hyperparameter settings, see Appendix A. Including our method, all methods only use
use a standard implementation. For SAC-discrete
reimplement the
5

---

PRE9 +
(a) SAC-discrete
SFP
(c) SSP
(d) SaS
Figure 4: A visualization of state visitation in online RL on AntMaze Medium in the first million timesteps for (a) SAC-discrete, (b) SFP, (c) SSP, and (d) our method averaged over 5 seeds. The grey circle in the bottom-left denotes the start position, while the green circle in the top-right indicates the goal. Notice that our method explores the maze much more extensively, with exploration behavior that is similar for all five seeds. SAC's visitation is tightly concentrated on the start state, which is why there is so little red in (a) the visitation rendering for SAC-discrete (i.e., it is occluded by the gray circle).
the action sequences of demonstrations. For AntMaze, we take the best setting of SSP whether the demonstrations are filtered or not.
We see in Figure 3, that even in these challenging sparse-reward tasks, our method can perform well. We show strong performance over baselines, which mostly achieve 0 return, except for in CoinRun where we are competitive. The large standard deviations are due to the fact that we can only run small number of seeds and some seeds fail to achieve any reward, but we will show that exploration behavior still reasonable, which gives us more confidence in the conclusions.
Due to the simplicity of our method, it is sig- nificantly faster than baselines. Table we measure the wall-clock time required to gen- erate skills, as well for single rollout. We see that our method achieves extremely signif- icant speedups compared to prior work. Our skill discovery method is fast as we simply need to run k-means and tokenization. SSP and SFP require training larger generative models. the case of rollouts, our method predicts entire sequence of actions using a simple policy every T. steps, while SSP and SFP require 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 RI. (around 10 hours for our method vs. 24 hours for SSP and week for SFP).
Table 1: Timing (mean + one standard deviation) on AntMaze Medium seconds. Methods measured on the same Nvidia RTX 3090 GPU with 8 Intel Core i7-9700 3 GHz CPUs @ 3.00 GHz. SSP takes 336 hours for skill generation and SFP takes ~2 hours.
Method
Skill Generation
Online Rollout
SSP SFP SaS
130000=1800 8000=500
0. 0.9+t0.55
4.14
311
0.007:10.006
4.2 Exploration Behavior on AntMaze Medium
The stringent evaluation procedure for sparse-reward RL equally penalizes poor learning and explo- ration. order to shed light on the poor performance of some methods Figure 3, we examine exploration on AntMaze Medium. We choose this domain because it is straightforward to visualize good and bad exploration behavior by plotting maze coverage. In Figure 4 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 saturation corresponds to higher probability of that state. Color is scaled nonlinearly according to power law between and for illustration purposes. Thin white areas between the density and the walls can be attributed the fact that we plot the center body position, and the legs have nontrivial size limiting the proximity to the wall.
Figure 4 visualizes the exploration behavior across methods, averaged over 5 seeds. We see that the values for return in Figure 3 for SAC, SSP and SFP are likely due not to poor optimization, but rather to poor exploration early in training, unlike our method. Indeed, we show in Appendix C that

---

MAL
12.
fat
166
SRiLL
3.
13-
Eb-
80
SYR.
6.
Steps
Strps
Steps
Steps
(a) AntMaze-U
(b) AntMaze-M
(c) AntMaze-L.
(d) Kitchen
(c) CoinRun
Figure 5: Comparison to methods with cntevaatio-conditiionn skills. In general we see conditioning helps when the data closely overlaps with the downstream task (Kitchen), but not in AntMaze where the demonstrations are somewhat disjoint. OPAL is a closed-source method similar to SPiRL, so results are taken from Ajay al. [2, Section 5.3].
on AntMaze Large, for which not all seeds succeeds (unlike AntMaze Medium, for which all seeds succeed), seeds that perform poorly still exhibit good exploration behavior. One reason for this could be due to the fact that our subwords are discrete set, so the policy always has diverse options to pick, whereas continuous latent variables can model infinitely many skills with only minor differences. In addition, SAC has fundamental issues in sparse-reward environments as the signal to the Q-function driven entirely by the entropy bonus, which will lead to uniform weighting on every action and as result, Brownian motion in the action space. Such behavior is likely why the default setting for SAC [28] aggressively drives the policy to determinism, but in the sparse reward setting, this also results in uniform policy. Without diverse and long sequences of coordinated actions, such uniform exploration is insufficient.
4.3 Comparison to Enservation-Condition Skills
Our skill extraction method does not rely observations and may lead to more generalizable skills. However, not conditioning on observations comes with the drawback that policy needs to learn the context to deploy skills from scratch. Alternatively, observation-condiioone skills bias policy exploration to match that of the demonstrations. This allows for more stable exploration [57, 58, 2], but worse generalization [6].
Baselines: Here we compare to the observation-condiioone extension SSP, SPiRL [57] which biases policy toward the use of skills in the same context as in the demonstrations. We also include OPAL [2], a concurrent work with SPiRL. We take numbers from the paper as OPAL is closed-source source. Our tuning procedure for SPiRL. is similar to SSP, where we consider the best setting over filtered and unfiltered demonstrations.
In Figure 5, we see that SPiRL shows very strong performance on Kitchen, where the overlap between the dataset and the downstream task is exact, but struggles with AntMaze, likely due to differences between the random trajectories in the dataset and the final task. We also note that our result for SPiRL in Kitchen is worse than the reported 2-3 [57]. Given that we use the official code, which already implements Kitchen, the difficulty of sparse-reward RL is likely to blame.
4.4 Transferring Skills
One benefit of unconditioned skills is that they can be extracted from demonstrations that differ from the final task domain. In Figure 6, we highlight that such transfer is possible, and that with varying percentages of demonstrations (down to 10 trajectories) performance is fairly stable. It may seem odd that 1% performs better than 10% and 25%, but this may be explained by the bias that ran- dom subsampling imposes on the demonstra- tions. By contrast, observation-condition methods require large amounts of trajectories in randomized environments to transfer effec- tively [57, 6].
0.8
Return
0.6
0.4
1%
10%
0.2
25%
100%
8
Steps
1e6
Figure 6: Results on transferring skills extracted from AntMaze-M to downstream RL AntMaze-U U, with varying quantity of demonstrations. Even with 1% of the data, our method extracts useful skills
7

---

4.5 Ablations
There are a few key hyperparameters of our method (k; Nmin and L). In the following, we perform ablations them in the AntMaze Medium and Kitchen environments. In general, behavior in the Kitchen environment much noisier, which may indicate that RI. training is still unstable.
Number of Discrete Primitives All of our results in Figure 3 use the simple rule-of-thumb that x degrees-of-free of-rredoom.. In Figure 7 we see that this choice seems to be acceptable, though should be noted that significantly larger values of & lead to shorter skills as there fewer and fewer common subwords with the desired length L.
1.0
1.25
0.8
1.00
9
Return
0.6
Retum
0.75
0.4
16
0.50
8
0.2
32
0.25
64
0.0
0.00
2
4 Steps
8
0.5
1.0
1.5
1e6
Steps
1e6
(a) AntMaze
(b) Kitchen
Figure 7: Results for different numbers of clusters. For AntMaze, Dof = dast Kitchen DoF=
dast = 9, and the default setting is & = 2 x daa- Note the legend is left unsorted so that the default setting & daet is rendered in consistent color and position across all plots.
Subword Length A crucial property of the vocabulary is the length of the subwords. Long subwords lead to more temporal abstraction and casier credit-assigmment for the policy. but long subwords can also get stuck for many transitions, possibly leading to poor exploration. In Figure 8, we vary the value of subword length L. Our default setting for each environment uses L 10 to match the baselines, but more difficult in AntMaze.
that different values also acceptable, though L makes RL
1.0
1.25
10
0.8
1.00
15
Return
0.6
Retum
0.75
20
0.4
10
0.50
0.2
15
0.25
0.0
0.00
2
0.5
1.0 Steps
Steps
1e6
1e6
(a) AntMaze
(b) Kitchen
Figure 8: Results for different choices subword length L, where the default setting is L 10. Note the legend is left unsorted so that the default setting L = 10 is in consistent color and position.
Vocabulary Size Ultimately, the dimensionality of the action space will make exploration easier or harder. A large vocabulary results in too many paths for the policy to explore well, but vocabulary that is too small may not include all the skills necessary to represent a good policy for the task. We in Figure 9 that larger vocabulary sizes do in fact make RL more difficult in AntMaze.

---

1.0
1.25
16
0.8
1.00
16
32
Retur
0.6
8
Retur
0.75
32
0.4
0.50
64
0.2
0.25
0.0
0.00
0
2
4
6
8
0.0
0.5
1.0
1.5
Steps
1e6
Steps
1e6
AntMaze
(b) Kitchen
Figure 9: Results for different choices of vocabulary size Nmin where the default setting is Nuin = 16. Note the legend left unsorted so the default setting Mmin 16 consistent color and position.
1.0
1.25
BPE
0.8
1.00
WordPiece Unigram
Retum
0.6
Return
0.75
0.4
0.50
BPE
0.2
WordPiece Unigram
0.25
0.0
0.00
2
4
8
0.0
0.5
1.0
1.5
Steps
1e6
Steps
(a) AntMaze
(b) Kitchen
Figure 10: Results for different choices of tokenizer algorithm, where BPE is the default.
Tokenizer Algorithm All of the results thus far have only considered the BPE tokenizer [24], but other tokenizers have seen benefits in language modeling, like WordPiece [67] or Unigram [39]. We see Figure 10 that BPE and WordPiece are somewhat interchangeable, but that performance suffers with Unigram. This is likely because, unlike BPE and WordPiece, Unigram does not discover hierarchically structured vocabulary where shorter subwords are contained in longer subwords. Thus, naively picking the first Nmin subwords of length L 10 may not extract the most common behavior. we were to allow a indepedendee vocabulary. Unigram might be more natural choice, but we did not explore that here due to the necessity of comparing fairly with baselines.
5 Conclusion
Architectures from NLP have made their way into offline RL [14, 32, 68), but as we have demonstrated, there is trove of further techniques explore. Motivated by prior evidence that the full range of the action space is not required, we discretize and form skills through simple tokenization method. Our method is much faster in skill generation and policy inference and leads to strong performance in several challenging sparse-reward tasks with relatively small sample budget. In addition, the finite vocabulary size lends itself to interpretable skills: one can simply look the execution to figure out what has been extracted (Appendix B). As proposed, however, there are few key limitations. Discretization removes resolution from the action space, which may be detrimental in settings like fast locomotion (Appendix D), but this may be fixed by using more clusters or residual correction [68]. addition, like prior work execution of our subwords open-loop, so exploration may be inefficient [3] and unsafe [50]. Still, given the speed, performance and interpretability advantages, we believe that our tokenization method the first step on new road to efficient reinforcement learning.

---

Acknowledgments
We thank Takuma Yoneda and Jiading Fang as well as other members of the RIPL lab at TTIC for helpful discussions throughout the process. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. 1754881. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views the National Science Foundation.
10

---

References
[1] Achiam and S. Sastry. Surprise-based intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv:1703.01733
2017. 2017.
[2] A. Ajay, A. Kumar, P. Agrawal, S. Levine, and O. Nachum. OPAL: Offline primitive discovery for accelerating offline reinforcement learning, arXiv preprint arXiv:2010.13611 2020.
[3] S. Amin, M. Gomrokchi, H. Aboutalebi, H. Satija, and D. Precup. Locally persistent exploration in continuous control tasks with sparse rewards. arXiv preprint arXiv:2012.13656 2020.
[4] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin,
P. Abbeel, and W. Zaremba. Hindsight experience replay. arXiv preprint arXiv:1707.01495 2017.
[5] P.-L. Bacon, J. Harb, and D. Precup. The option-critic architecture. In Proceedings of the National Conference Artificial Intelligence (AAAI), pages 1726-1734, 2017.
[6] M. Bagatella, S. Christen, and O. Hilliges. SFP: State-free priors for exploration in off-policy reinforcement learning. Transactions on Machine Learning Research, 2022.
[7] M. Bagatella, S. Christen, and O. Hilliges. SFP: State-free priors for exploration in off- policy reinforcement learning GitHub, 2024. URL https: Accessed on March 1, 2024.
//gitub github.t....... com/ eth ait/sfp.
[8] A. G. Barto and S. Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13:41-77, 2003.
[9] M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[10] L.. Biewald. Experiment tracking with weights and biases, 2020. URL. httph::/p///ttt wandb. com/. Software available from wandb.com.
[11] C. Boutillirr R. I. Brafman, and C. Geib. Prioritized goal decomposition of Markov decision
processes: Toward synthesis of classical and decision theoretic planning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1156-1166 162, 1997.
[12] Y. Burda, H. Edwards, D. Pathak, A. Storkey, T. Darrell, and A. A. Efros. Large-scale study of curiosity-driven learning, arXiv preprint arXiv: 1808. 04355, 2018.
[13] Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. arXiv preprint arXiv: 12894, 2018
[14] L. Chen, K. Lu, A. Rajeswaran, Lee, A. Grover, M. Laskin, Abbeel, A. Srinivas, and
I. Mordatch. Decision transformer: Reinforcement learning via sequence modeling, In Advances Neural Information Processing Systems (NeurIPS), pages 15084-15097, Dec. 2021.
[15] N. Chentanez, A. Barto, and Singh. Intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2004.
[16] P. Christodoulou. Soft actor-critic for discrete action settings. arXiv preprint arXiv:1910.07207, 2019.
[17] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman. Quantifying generalization in reinforcement learning. In International Conference on Machine Learning, pages 1282-1289, 2019.
[18] R. Dadashi, L. Hussenot, D. Vincent, S. Girgin, A. Raichuk, M. Geist, and O. Pictquin. Continuous control with action quantization from demonstrations, In International Conference on Machine Learning, pages 4537 4557, 2022.
[19] C. Daniel, G. Neumann, and J. Peters. Hierarchical relative entropy policy search. In Proceed- ings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 273-281, 2012.

---

[20] P. Dayan and G. E. Hinton. Feudal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 1992.
[21] T. G. Dietterich. Hierarchical reinforcement learning with the MAXQ value function decompo- sition. Journal of Artificial Intelligence Research, 13:227-303, November 2000.
[22] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is all you need: Learning skills without reward function. arXiv preprint arXiv: 2018.
[23] J. Fu, A. Kumar, O. Nachum, G. Tucker, and Levine, D4RL: Datasets for deep data-driven reinforcement learning, arXiv preprint arXiv:2004.0723 2020.
[24] Gage. new algorithm for data compression. C Users Journal, 12(2):23-38, 1994.
[25] K. Gregor, D. J. Rezende, and D. Wierstra. Variational intrinsic control. arXiv preprint 1rXiv:1611.0750,, 2016.
[26] S. Gu, E. Holly, T. Lillicrap, and S. Levine. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 3389-3396 2017.
[27] T. Haarnoja, S. Ha. A. Zhou, J. Tan, G. Tucker, and S. Levine. Learning walk via deep reinforcement learning. arXiv preprint arXiv:1812.11 2018.
[28] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, Abbeel, and S. Levine. Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905, 2018.
[29] N. Haber, D. Mrowca. S. Wang. L. F. Fei-Fei, and D. L. Yamins. Learning to play with intrinsiaall--ooiivaeed, self-aware agents. In Advances in Neural Information Processing Systems (NeurIPS), Montréal, Canada, Dec. 2018.
[30] E. Hazan, S. Kakade, K. Singh, and A. Van Soest. Provably efficient maximum entropy exploration. In Proceedings of the International Conference on Machine Learning (ICML), pages 2681-2691 2019.
[31] X. He, G. Haffari, and M. Norouzi. Dynamic programming encoding for subword segmentation in neural machine translation. In Proceedings of the Association for Computational Linguistics (ACL), pages 3042-3051, 2020.
[32] M. Janner, Q. Li, and S. Levine. Offline reinforcement learning as one big sequence modeling problem. In Advances in Neural Information Processing Systems (NeurIPS), pages 1273-1286, 2021.
[33] Z. Jiang, T. Zhang, M. Janner, Y. Li, T. Rocktäschel, E. Grefenstette, and Y. Tian. Efficient planning in a compact latent action space. arXiv preprint arXiv:2208. 10291, 2022.
[34] I. P. Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In Proceedings of the International Conference on Machine Learning (ICML), pages 167-173, 1993.
[35] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 41260:1412.6980, 2014.
[36] D. P. Kingma and 2013.
and M. Welling, Auto-encoding variational bayes. arXiv preprint arXiv: 1312,6114,
[37] G. Konidaris and A. Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Advances in Neural Information Processing Systems (NeurIPS), December 2009.
[38] G. Konidaris, S. R. Kuindersma, R. A. Grupen, and A. G. Barto. Robot learning from demon- stration by constructing skill trees. International Journal of Robotics Research, 3163336603375 March 2012.
12

---

[39] T. Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the Association for Computational Linguistics (ACL), pages 66-75, 2018. doi: 10.18653/v 1/P1// 1/P18- 1007.
[40] T. D. Kulkarni, K. R. Narasimhan, A. Saeedi, and J. B. Tenenbaum. Hierarchical deep rein- forcement learning: Ingegrating temporal abstaction and intrinsic motivation. In Advances in Neural Information Processing Systems (NeurIPS), Barcelona, Spain, December 2016.
[41] R. T. Lange and A. Faisal. Semantic with action grammars: Data-efficient learning of hierarchical task abstractions. arXiv preprint 1rXiv:1907.12444 2019.
[42] L. Lee, B. Eysenbach, E. Parisotto, E. Xing, S. Levine, and R. Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv: 19X.:1906.00274, 2019.
[43] A. Levy, G. Konidaris, R. Platt, and K. Saenko. Learning multi-level hierarchies with hindsight. arXiv preprint arXiv: 1et..0112...... 2017.
[44] H. Liu and P. Abbeel. Behavior from the void: Unsupervised active pre-training. In Advances in Neural Information Processing Systems (NeurIPS), pages 18459-18473, 2021.
[45] M. Lopes, T. Lang, M. Toussaint, and P.- Y. Oudeyer. Exploration in model- based reinforcement learning by empirically estimating learning progress. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
[46] C. Lynch, M. Khansari, T. Xiao, V. Kumar, J. Tompson, S. Levine, and P. Sermanet. Learning latent plans from play. In Proceedings of the Conference on Robot Learning (CoRL), pages 1113-1131 1132, 2020.
[47] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. A. Ried- miller. Playing atari with deep reinforcement learning. arXiv:1312.5602 2013.
[48] S. Mohamed and D. Jimenez Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
[49] O. Nachum, S. S. Gu, H. Lee, and Levine. Data-efficient hierarchical reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), Montréal, Canada, 2018.
[50] S. Park, J. Kim, and G. Kim. Time discretization-invariin safe action repetition for policy gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), pages 267-279, 2021.
[51] S. Park, J. Choi, J. Kim, H. Lee, and G. Kim. Lipschitz-connstraieed unsupervised skill discovery. In International Conference on Learning Representations, 2022.
[52] S. Park, K. Lee, Y. Lee, and P. Abbeel. Controllability unsupervised skill discovery. arXiv preprint 33X 2023.
[53] R. Parr and S. Russell. Reinforcement learning with hierarchies of machines. In Advances in Neural Information Processing Systems (NeurIPS), pages 1043-1049, 1997.
[54] R. E. Parr. Hierarchical control and learning for Markov decision processes. PhD thesis, University of California, Berkeley, Berkeley, CA, 1998.
[55] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. PyTorch: An imperative style, high persoreeffrmancc deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[56] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-driven exploration by self- supervised prediction. In Proceedings of the International Conference on Machine Learning (ICML), pages 2778-2787, 2017.
[57] K. Pertsch, Lee, and J. Lim. Accelerating reinforcement learning with learned skill priors. In Proceedings of the Conference on Robot Learning (CoRL), pages 188-204, 2021.
13

---

[58] K. Pertsch, Y. Lee, Y. Wu, and J. Lim. Guided reinforcement learning with learned skills. In Conference on Robot Learning, pages 729-739, 2022.
[59] K. Pertsch, Y. Lee, and Lim. Accelerating reinforcement learning with learned skill priors- GitHub, 2024. URL httppp//.gghhhh...cmm////ar//ppp Accessed on March 1, 2024.
[60] S. Pitis, H. Chan, S. Zhao, B. Stadie, and J. Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pages 7750-7761, 2020.
[61] Poupart, N. Vlassis. J. Hoey, and K. Regan. An analytic solution discrete Bayesian reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pages 697-704, Pittsburgh, PA, 2006.
[62] Provilkov, D. Emelianenko, and E. Voita. BPE-dropout: Simple and effective subword regularization. In Proceedings of the Association for Computational Linguistics (ACL), pages 1882-1892, 2020.
[63] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann. Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22 (268), 2021.
[64] D. J. Rezende, S. Mohamed, and D. Wierstra. Stochastic backpropagation and approximate inference deep generative models. International conference on machine learning, pages 1278-1286. PMLR, 2014.
[65] J. Schmidhuberr A possibility for implementing curiosity and boredom in model-building neural controllers. In Proceedings of the International Conference on Simulation of Adaptive Behavior: From Animals to Animuts (SAB), pages 222-227, 1991.
[66] M. Schuster and K. Nakajima. Japanese and korean voice search. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5 5149-5152, 2012.
[67] R. Sennrich, B. Haddow, and A. Birch. Neural machine translation of rare words with subword units, arXiv preprint arXiv:1508.077 07909, 2015.
[68] N. M. Shafiullah, Z. Cui, A. A. Altanzaya, and L. Pinto. Behavior transformers: Cloning k modes with one stone. In Advances in Neural Information Processing Systems (NeurIPS), pages 22955-22968,, New Orleans, LA, 2022.
[69] A. Sharma, S. Gu, S. Levine, V. Kumar, and K. Hausman. Dynamics-awarr unsupervised discovery of skills. arXiv preprint (XXXv:990700155. 2019.
[70] S. Sharma, A. Srinivas, and B. Ravindran. Learning to repeat: Fine grained action repetition for deep reinforcement learning. In International Conference on Learning Representations, 2017.
[71] D. Silver, J. Schritwieser, Simonyan, I. Antonoglou, Huang, A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap. F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676):
354-359, 2017.
[72] 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.
[73] J. Skalse, N. Howe, D. Krasheninnikov, and D. Krueger. Defining and characterizing reward gaming. In Advances in Neural Information Processing Systems (NeurIPS), pages 9460-9471, 2022.
[74] B. C. Stadie, S. Levine, and P. Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint / 2015.
[75] R. S. Sutton. TD models: Modeling the world a mixture of time scales. In Proceedings of the International Conference Machine Learning (ICML), pages 531-539. 1995.
14

---

[76] R. S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(122)181-211. August 1999.
[77] S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg. D. Silver, and K. Kavukeuoglu. FeUdal networks for hierarchical reinforcement learning. In Proceedings of the International Conference Machine Learning (ICML), pages 3540-3549, Sydney, Australia, Aug. 2017.
[78] D. Warde-Farley. T. Van de Wiele, T. Kulkarni, C. Ionescu, S. Hansen, and V. Mnih. Unsuper- vised control through non-parametric discriminative rewards. arXiv preprint arXiv:/811.1133 2018.
[79] D. Yarats, Fergus, Lazaric, and L. Pinto. Reinforcement learning with prototypical representations. In Proceedings of the International Conference on Machine Learning (ICML), pages 11920-11933) July 2021.
[80] R. Zheng, C.-A. Cheng, H. Daumé III, F. Huang, and A. Kolobov. Prise: Learning temporal action abstractions sequence compression problem. arXiv preprint vrXiv:242..1444 2024.
15

---

(a) AntMaze Umaze (b) AntMaze Medium (c) AntMaze Large
(d) Kitchen
(e) CoinRun
Figure 11: Offline environments, figures courtesy of Fu et al. [23] and Cobbe et al. [17]. For AntMaze Umaze the starting location is in the bottom left, and the goal the top left. For AntMaze Medium and Large the starting locations are in the bottom left, and goals are in the top right.
A
Online RL Experimental Details
A.1
Data
As a set of diverse and challenging sparse-reward tasks, we select AntMaze and Kitchen from D4RL [23] and CoinRun [17]. We choose AntMaze much more challenging version of the PointMaze task considered in prior work [57, 6), and Kitchen as the most complicated manipulation environment considered by Pertsch al. [57]. CoinRun is chosen challenging discrete-action environment.
AntMaze An environment in which MuJoCo Ant robot is tasked with navigating a maze (Fig- ures 1i),), 11(b) and 11(c)). The observation space consists of positions and joint angles of the body geometries. while actions correspond to joint torques. Crucially, no information about the maze layout is given, so the agent must learn this through exploration. Reward is O unless within small distance of the goal. in which case 1. Demonstrations from the dataset consist of non-RI. agent navigating between random start and end points within the maze [23]. In particular, the demonstrations are highly suboptimal, often crashing into walls, flipping over, and getting stuck. In order to extract nontrivial behavior with our method, we filter this data so that 10-step chunks that fail to move past a certain threshold normalized distance in observation space are dropped. We consider the best setting of filtered or unfiltered data for baselines.
Kitchen An environment which a Franka Panda arm is tasked with performing a sequence of 4 subtasks in mock kitchen environment (Figure Id)).. Example subtasks include moving kettle between burners, turning on the stove, and opening the microwave. Observations consist of position and joint angles of the arm, as well as positions of key objects be manipulated, and actions joint torques. Once again, no information about the layout is given to the agent, and instead, must be learned through exploration. Rewards order, which yields reward of 1. There are 4 subtasks to be completed, so there is a maximum reward of 4 available. Demonstrations are collected by humans using a VR interface [23], and consist of near- pear-perfect executions of different sequences of 4 subtasks from the final sequence.
0 unless the correct subtask is completed in the correct
CoinRun A procedurally generrtee platforming game that involves traversing obstacles and avoid- ing enemies in order to reach final goal (Figure 11(e)). Each level has different layout and visual style, designed by humans, order to require more general recognition from the policy. Observations consist of a 64 x 64 visual observation of the scene, centered on the agent, with velocity information painted into the upper-left corner. Actions are discrete and consist of moving, jumping, and staying still. Reward is O until the final goal for a level is reached, in which case it is 10. For RI., we select fixed subset of 10 "hard" levels in sequence for an agent to complete, to mimic classic games, so the maximum possible reward is 100. We collect demonstration data through playing around 100 "easy" levels with different layouts and visual style than the eventual levels we perform RL on.
A.2 Model
For the model, we choose a 4-layer MI.P with 256 hidden units in each layer. We use the default initialization in Stable Basclines 3 [63]]
16

---

Figure 12: All skills discovered for AntMaze-M where color is darker for poses earlier in the trajectory. We see a range of linear motion and turning behaviors.
A.3 Optimization
For our RL agent, we use SAC-discrete [16]. Both critics as well as the policy are optimized with Adam [35] with standard learning rate of 3e 4. Replay buffer size is set the standard million transitions. We update both critics and the policy every step of environment interaction and sample uniformly from the replay buffer to do Unlike Christodoulou [16], follow similar convention to Haarnoja et al. [28] and automatically optimize a. We choose a target entropy dependent on the domain: 0.1 for AntMazes, 0 for Kitchen, and 0.5 for CoinRun, though we find this hyperparameter to be relatively unimportant. More importantly, we found a large batch size crucial to good performance in AntMaze, where we
batch size of 4096. For other tasks, we use batch size of 64. Other hyperparameters are kept to their default values following SPiRL. Baselines are kept with original hyperparmeters for the domains they studied, and given was the critical hyperparameter for our method, we tune batch sizes for SSP and SPiRL, but find default hyperparameters perform best. Because SFP so expensive to run, we do not have the computational budget to tune hyperparameters.
For AntMaze we train for 10 million steps, for Kitchen we train for million, and for CoinRun we train for 1.5 million steps. All numbers come from random seeds.
A.4 Skill-extraction hyperparameters
For AntMazes and Kitchen, we choose defaults of k: = 2 x daet. L = 10, Nmax 10th and Nmin = 16. For CoinRun there is need for discretization, we only choose Nmax 10 L 10, and Nmin = 16. These defaults are chosen to match the length 10 skills of SSP.
A.5
Implementation
Code was implemented in Python using PyTorch [55] for deep learning, Stable Baselines 3 [63] for RL, and Weights & Biases [10] for logging. It is available at https://gitaii com dyunis/ wwwpordd__s_skkill____
A.6 Computational Requirements
All experiments were performed on an internal cluster with access to around 100 Nvidia 2080 Ti (or more capable) GPUs. Each single run fits around GB of GPU memory on a single machine. AntMaze, training for our method typically takes around 10 hours for single run, while SSP [57] takes 24 hours and SFP [6] takes over week. In particular, this highlights exactly how poor the scaling can be for methods that call large model at every transition.
B Qualitative Description of Skills
One nice property of our method is that, given that we extract finite vocabulary, we can inspect the discovered skills. Below, we discuss the AntMaze and Kitchen domains as an example. In order to visualize skills, we execute the subwords for 100 steps in the environment, and visualize the resulting trajectory. The actual duration of a skill is much shorter, but this done make the motions very clear.
17

---

Figure 13: All skills discovered for Kitchen where color is darker for poses earlier in the trajectory. We see range of different behaviors across the skills, including reaching (top row, first column), pulling (bottom row, first column), and pushing (bottom row, fifth column) motions.
PP
PP
TP
PPA
UF
(a) Seed 0
(b) SFP
(c) Seed
(d) Seed 3
(c) Seed 4
Figure 14: A visualization of state visitation in online RL AntMaze Large for all 10 million timesteps across different seeds. The grey circle in the bottom-left denotes the start position, while the green circle in the top-right indicates the goal. Notice that method explores the maze much more extensively, with exploration behavior that is similar for all five seeds, even if the performance of some of those seeds is 0 in the eventual evaluation. In particular, Seeds 0 and 2 do not result in good evaluation performance regardless of the sensible exploration behavior.
In Figure 12, we see the skills extracted in AntMaze. In particular, we see turning in both directions, with differing radii, well various linear motions. It is straightforward to imagine why one would need both designing an action space, and it seems that there are few explicit repetitions (though many variations on the theme).
In Figure 13, we visualize the different skills discovered to present in a static form, is not simple to visualize interaction with the environment, but they consist of a variety of reaching and rotational motions that are useful for interacting with different objects. In the bordered images, we highlight three particular skills. In the top left is reaching skill that might be used for reaching the light switch/oven knobs. In the bottom left is a pulling skill that could be useful opening door. Lastly there is pushing skill, that might be useful for sliding door.
Kitchen domain. These are difficult
C Exploration Behavior when RL fails
Figure visualizes the exploration behavior of our method on AntMaze Medium, for which all five seeds our method succeed. believe that is informative to consider the exploration behavior on
domains for which some seeds fail. To that end, we analyze the differences in exploration behavior of SaS on Antmaze Large, for which not seeds achieve perfect performance. We see Figure 14 that even those seeds that do not perform well have quite sensible exploration behavior and good coverage of the maze, so it seems like the major issue has to do with optimization the RL setting, not exploration.
3000
D Effect of Discretization In Locomotion
Return
2000
As mentioned in Section 5, discretization may remove resolu-
1000
tion from the action space that could be useful, in particular for fine-grained manipulation or fast-locomotion tasks. To study this limitation, we investigate the effect of varying the dis- cretization level on the Hopper locomotion environment from D4RL [23]. We use hyperparameters k 12, N = 16, L == 5 and train 5 seeds for 3 million steps each.
Steps
1c6
Figure 15: Experiments on the Hop- per domain for varying number of clusters
18

---

In Figure 15, we see that the conclusions are curious. Finer discretization helps up certain point, after which it hurts performance. We are not totally certain to why this happens. One hypothesis is that finer levels of discretization naturally results in shorter skills, as there are fewer repeated subwords, but this might make RL in a dense reward environment easier, not harder. In any case, all runs are worse than training continuous actions.
Effect of Data Quality
To see how method performs with different kinds of data quality, we again use the Hopper environment from D4RL [23]. This is because, unlike sparse-reward tasks considered in the rest of the paper, Hopper provides a clear delineation of demon- stration quality: "Random" for transitions from random policy, "Medium" for transitions from policy partway through train- ing, and "Expert" for transitions from policy the end of training. We set = 12, Niin = 16, L and train seeds for 3 million steps.
3000
2500
Retur
1500
Random
500
Medium
Steps
1e6
From Figure 16, "Expert" demonstrations provide the best skills, "Medium" demonstrations are very similar "Expert", but surprisingly "Random" demonstrations are quite compet- itive. What is likely happening here is that random demonstra- tions do not have enough common subwords, so the discovered subwords are quite short in length. Thus, with dense reward it is still possible to recover good behavior.
Figure 16:
Experiments with
demonstration data of varying qual- ity in the Hopper domain.
19

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: believe that the main claims provided in the abstract and introduction, are accurate reflection of the paper's contributions and scope, with empirical results that support these claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
20

---

Justification:
We discuss the limitations of our work in Section 5 as well as in the Appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sele--ppeiiiainnn. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The authors have made an effort to provide information sufficient to reproduce the main experimental results, including details regarding the domains considered, the baselines, and the hyperparameter settings the main paper and appendix. Additionally, we will make the code publicly available if/when the paper is accepted.
Justification:
21

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The data on which our method and the baselines trained publicly available as part of the D4RL and CoinRun benchmarks. The code is available and mentioned in the text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
Stw.addeee/ooeeummssisiiisiss commooolly).o..oollll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //nips.co wttpcc//pppppppeeeeeeeeeeeeeeece http:/uwiee//eeeeeeee htppbbiigggiddeeeoettttttaiiiiii
/oooeeeobiissiiiiiceaaeaae seiionnncyc)) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
22

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
These details are provided in the main text and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports standard deviations across 5 seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These details are provided in Appendix A.6 and Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
23

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //terr//////r...../// cccppblic/eeeeecccccecccceceeeee Ceabbic/Ethiccee httee/itiiiiiiiieeeeeeeeeeeeeeae ctthicscuiellnes diies??
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics and believe that the paper is in compli-
ance.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper proposes an algorithm for reinforcement learning in sparse reward settings. We do not anticipate any societal impacts for this work, positive or negative.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

---

Answer:
[NA]
Justification:
We believe that the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We train and evaluate our model on benchmark tasks from D4RL, (https: g thub. Faaarrraaaaounnattoooooo and CoinRun (https: //tgttgtttb///t www/opeeai/coiieeeeece which is governed by the MIT License. We cite both in the paper.
which is governed by the Apache-2.0 License,
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: We do not release any new assets with this submission. However, we will make the code well trained models publicly available if/when the paper is accepted.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the detaset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
25

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "FAwhEX2w2g", "reviewer": "Reviewer_bwJh", "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.", "questions": "1. Effect of Stochasticity on Algorithm Performance\n\nHow 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.\n\n2. Intuition Behind BPE Benefits\n\nCan 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": "The authors acknowledge several limitations of their work:\n\n1. **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.\n2. **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.\n\nThe paper does discuss these limitations openly.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **Originality**\n\nThe paper presents a novel approach by adapting the Byte-Pair Encoding (BPE) algorithm from natural language processing to skill extraction in reinforcement learning. This creative application demonstrates originality.\n\n\n- **Quality**\n\nThe method is evaluated on several challenging sparse-reward RL tasks, such as AntMaze and Kitchen environments. The results indicate significant improvements in performance and efficiency compared to existing methods.\n\n\n- **Clarity**\n\nThe paper is well-organized and clearly explains the methodology, experiments, and results. Visualizations and detailed explanations help in understanding the process and the outcomes of the proposed approach.\n\n\n- **Significance**\n\nThe proposed method addresses a critical problem in RL, namely extracting skills from the demonstrations to solve exploration in sparse-reward environments. By significantly accelerating skill extraction and policy inference, the method has the potential to impact a wide range of applications in RL.", "weaknesses": "1. Stochasticity of the Environment\n\nThe 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.\n\n2. Intuitive Explanation of BPE Advantage\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and consideration spent reviewing. We appreciate that you highlight the novelty and significance of the approach, as well as the clarity in presentation and the challenge of the tasks that we choose to evaluate in. We respond to the weaknesses and questions below.\n\n1. Stochasticity of the environment\n\nIt is indeed the case that stochastic environments can pose issues, though we would like to clarify how exactly. The skills that we discover are 10 steps long, while the tasks that we set out to accomplish are hundreds of steps long. This means that skills tend to correspond to short sequences (e.g., taking a step or two forward, turning slightly, reaching toward an object), but not completely memorized actions. Thus if the environment layout were to change (as is the case in DMLab30, and in the case of our transfer experiments), it shouldn't pose an issue for our method as long as the policy can learn a generalized map from observation to action (which would be the case if many training environments were given). However, low-level stochastic dynamics would be more problematic and we discuss this in the limitations. We would be happy to expand this discussion. The deterministic environments we test are standard in the literature (including the baselines we use), so we did not consider this to be a deal-breaker. One option to mitigate this issue is to tune a residual policy on top of skills once they are discovered (not dissimilar to the residual correction in Behavior Transformers), though we find this to be out of scope for the current submission.\n\n2. Advantage of BPE over simpler methods\n\nWe believe there may be a slight miscommunication happening here, so we apologize for any lack of clarity in the writing. In short, we do not believe it is correct to compare \"simple k-means clustering\" with BPE for skill discovery as the two have entirely different purposes, and we use the first to seed the second. In particular, we want to discover high-level action *sequences*. Thus in order to use k-means clustering, we will need to define a distance metric over *sequences* of actions, which is tricky to do. One might think to average l2 distance over pairs of actions in different sequences, but if two sequences of scalar actions are shifts of each other, e.g. (a_1, a_2, a_3) =  (0, 1, 0) or (1, 0, 1) (i.e., alternating 0 and 1 actions), these would be farther apart than (0, 1, 0) and (0.5, 0.5, 0.5) which are completely different sequences. Thus it becomes difficult to define a \"simpler\" method operating on sequences. As to why we choose BPE, BPE is the simplest and most common method employed currently in NLP to discover discrete subsequences. It finds the most common subsequences in a greedy fashion, which in demonstration data would correspond to common behaviors useful across many different scenarios. Our insight is to reuse this technique in RL to help in solving the exploration problem, as these reusable behaviors should correspond to reusable skills. As we show in the paper, this method is much cheaper and faster than using sequence models for skill discovery as prior work has done. We hope this addresses any issues in communication and would welcome further questions to help clarify the presentation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jJxXNtyEG3", "reviewer": "Reviewer_iKv2", "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.", "questions": "See the \"Weaknesses\" section.", "limitations": "The authors have discussed a few limitations in the paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper has several strengths:\n\n- The perspective of using  NLP tokenization techniques for skill discovery in RL is creative and innovative.\n- The method outperforms baselines in several sparse-reward environments.\n- The study examines various aspects beyond performance, including computational efficiency, exploration behavior, and domain generalization.", "weaknesses": "While the paper demonstrates several strengths, there are also potential limitations and areas for improvement:\n\n- The range of baseline skill discovery methods could be expanded. Additional algorithms, such as those proposed in [1] and [2], merit consideration.\n\n- The presentation requires refinement. The current format of tables and figures impedes clear interpretation, potentially obscuring the full efficacy of the proposed method.\n\n- 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.\n\n- There is no formal guarantee that the discovered skills are sufficient to construct an optimal policy. This theoretical limitation warrants acknowledgment and discussion.\n\n- The computational complexity of the merging process may prove prohibitive for high-dimensional input domains, potentially limiting the method's scalability.\n\n- 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.\n\n[1]  Y. Jiang, E. Z. Liu, B. Eysenbach, Z. Kolter, and C. Finn, “Learning options via compression,” arXiv preprint arXiv:2212.04590, 2022.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate that you highlighted the creativity of the approach as well as the breadth of the study. We respond point by point to your concerns below.\n\n1. Range of baselines\n\nWe would be happy to cite and discuss these methods in the paper. LOVE [1] is similar in its aims to our method, compressing sequences into reusable parts, but requires observation conditioning, which makes it hard to directly compare to our method. As discussed in Section 4.3, observation conditioning requires in-domain data collection and has tradeoffs with exploration. Parrot [2] is very similar to SSP or OPAL in that it is a flow model over actions, but instead of being over chunks of actions it is only over a single action at a time, so it would be as inefficient to run in practice as SFP, thus we thought SSP would be a better choice. The code is also not available.\n\n2. Presentation requires refinement.\n\nIt would be helpful to understand where precisely the issues are with the presentation so that we may amend them.\n\n3. Dataset-specificity of skills\n\nTo test the specificity of the dataset required to generate skills we provided experiments in the Hopper task in Appendix E, where we found indeed that quality was not so important, and we also subsampled the data in Figure 6, which suggests that only a very small number of decent demonstrations are necessary. If this is referring to the choice of tasks, we already choose more challenging tasks than prior methods.\n\n4. No formal guarantee of optimality\n\nWe agree that there is no formal guarantee of optimality and many skill-learning papers do not provide any such guarantees, including the baselines we consider. We already mention this limitation in lines 131-136, but we would be happy to expand this discussion if it is not sufficient.\n\n5. Computational complexity of the merging process in high-dim\n\nPerhaps the presentation was unclear. In particular our merging process first consists of running k-means on actions and assigning them to their closest cluster centers. Then, we run BPE on the derived \"strings\". As such, the computational complexity of the merging process in high dimensions will only affect the k-means step, which indeed is more expensive for high-dimensional input, but still very very efficient on existing hardware for 1000-dimensional input spaces. The BPE step is on discrete units, so it will be fast regardless of the input dimension, certainly when compared to training neural networks. We hope this clarifies.\n\n6. Unclear how method performs with larger, more diverse datasets\n\nRL with a large action space is difficult, but so is RL with an unconditional skill space that can perform many different behaviors. As such we don't believe this is any more difficult with our method than existing methods. We believe such studies are out of scope given the current large batch of experiments, but agree it would be interesting to follow up. Certainly our method would be much faster to test on larger datasets when compared to prior work given the speedups.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zUMHDcp3R8", "reviewer": "Reviewer_g8NK", "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:\n* improve exploration in sparse reward settings\n* creating the skill action space is computationally cheap compared to methods that train deep learning models\n* their approach is not conditioned on observation, which improves generalisation", "questions": "How important is using K-means clustering before the byte pair encoding?\n\nCould use simpler disrectisation approaches (e.g. like the one used in the continuous control experiments here: https://arxiv.org/abs/2107.05431)\n\nThey mention filtering demonstrations", "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.\n\nI 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?", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors present a clear explanation of how (as far as I know) novel method for extracting skills from demonstrations. What is really cool is that you only to run k-means clustering, making this approach scale favorably to other approaches that use deep learning.\n\nAlso give the success of BPE in NLP, this is a very intuitive idea that seems like a great contribution to the RL community.\n\nThe ablations answered most of my questions about the design of their method.", "weaknesses": "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.\n\nAlso, from the paper alone, I cannot tell whether the baselines are the state of the art approach for skill extraction.\n\nTo help with these weaknesses I would like:\n\n* details on the number of demonstrations used\n* more explanation of what the baselines are and how they work\n\nFor the transferring skills, it would be good to run the baseline (even if it is very poor) to plot in figure 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and care in reviewing our paper. We appreciate your feedback and share your excitement regarding the intuitiveness of the method and the computational efficiency. We answer your questions below.\n\n1. How many demonstrations are used?\n\nFor these tasks we use the existing D4RL dataset, and we give details on demonstrations in Appendix A. As to the quantity, we use ~1000 demonstrations for the AntMaze results, ~600 for the Kitchen results and ~100 for CoinRun. These numbers are defined (except in the case of CoinRun which we collect) by practices in prior work that we compare against. In Figure 6 we explore subsampling.\n\n2. Can offline methods be used?\n\nD4RL was a dataset collected for offline RL, but the goal of our work is orthogonal. Even though offline RL might be used for these tasks, it assumes access to the observations, and the reward labels, whereas we only require the action sequences. In addition, because offline RL requires access to this extra information, it will memorize the particular layout of the scene in order to accomplish the task, and if the layout is rearranged, as in the transfer experiment, then new demonstrations and reward will have to be collected in the new layout. Thus, the use of offline RL is predicated on the availability of in-domain data, which is the opposite of exploration.\n\n3. Are baselines SOTA?\n\nThe baselines used are strong methods for unconditional learning, though the benchmarks tested in the literature are rarely shared. Our goal in this work is not only to compete for SOTA, but additionally to point out that a relatively simple and inexpensive method can compete with very expensive neural-network based solutions. In particula,  these NN-based solutions are so expensive that even running experiments takes substantially longer. The baselines are chosen to represent two common classes seen in the literature: models that generate subsequences with VAEs (SSP) and sequence models as priors (SFP).\n\n4. How important is $k$-means before BPE?\n\nWithout some kind of discretization step it would be impossible to run BPE as we need to merge the most common pair among a discrete set. k-means was chosen as it is a very standard way to discretize.\n\n5. Could we use simpler discretization through binning?\n\nWe did think about this possibility, but binning would result in an exponentially large number of discrete units (with the action space). This means that there could be a very large number of subwords discovered, which would result in a necessarily large final vocabulary. Such a large vocabulary makes RL difficult as we see in the paper. In addition, most of these discrete units discovered might not actually be necessary. In the example of the Ant, every possible motion of every leg joint is not necessary to make the Ant move, just the coordinated motions of lifting each leg up and down as a whole.\n\n6. Missing limitations.\n\nWe do address limitations in the conclusion section, but found it difficult space-wise to include a separate heading. We do not believe the comparison to offline RL is applicable as it is an orthogonal problem with different aims. Our goal is to improve exploration even when in-domain task data is not already available.\n\n7. When is this method not applicable?\n\nThanks for the question. We discuss this in the Conclusion section where we mention several limitations. In particular we speak about discretization removing resolution, which might be necessary for very fine-grained motor skills, and the open-loop execution, which would have disadvantages in stochastic environments. We believe some of these issues are addressable in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zqyr4pnuMa", "reviewer": "Reviewer_jRfS", "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.", "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.\n- Why are the ablations performed on Hopper (appendix D + E) but no Hopper experiments are in the main paper?\n- 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?\n\nAs 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": "Sufficiently addressed", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Presentation:** Writing is clear and the method is intuitive and simple, the paper is overall easy to understand. The main figure also does a good job of distilling the algorithm into a simple illustration.\n\n**Method:** The method is extremely compute-efficient in skill creation. It’s also faster when using for downstream RL because the action sequences are unique skills, no forward passes are needed.\n\n**Results:** Overall, results are convincing in that the method works on par with or better than other non-state conditioned skill-based RL methods. \n\n**Experiments:** The authors performed a good amount of ablations and the experiments are performed across a few locomotion, manipulation, and discrete procgen settings that seem pretty comprehensive for an RL paper.", "weaknesses": "**Method:** \n\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your care in reading our paper. We appreciate the positive feedback on the clarity, and the comment on efficiency and the strength of the results, including a “pretty comprehensive” evaluation. We respond to your concerns below.\n\n1. Method cannot be state-conditioned\n\nThough it is true that we present an unconditional method, it is completely possible to adapt into a state-conditioned method. After discovering skills and tokenizing the demonstrations via BPE, one can take all the observation-action pairs that correspond to, say, 3-action prefixes of our skills, and train a classifier to map from observations to one of these prefixes. Then, one can bias the sampling during RL toward skills whose prefix is more likely under the prior, in exactly the same way that SPiRL does. We did attempt to prototype this method during the rebuttal, but it was not possible to properly tune and compare to prior work due to time constraints. We do consider it interesting for future work.\n\n2. Policy must learn association.\n\nThis is intentional. Our goal here is to drive strong exploration, even when the collected demonstration data is small or out of domain (Figure 6). Having a strong skill prior requires lots of in-domain data collected, which is the language modeling case. That being said, we agree that learning a prior is a reasonable solution in such settings. See above for how we might go about doing so.\n\n3. Why choose a specific skill length?\n\nThis choice was made to make comparisons to baselines fair. We agree that BPE is perfectly suited to discover skills of different lengths which would be more flexible and makes more sense.\n\n4. Why are ablations on Hopper?\n\nOne of these ablations explores the effect of discretization in a task where we might expect it to matter more as hopper only has a single contact point. The sparse-reward tasks explored in the main text are quite resilient to discretization (Ant and Franka are stable) so it made less sense to do this for those tasks. For the ablation on data quality, D4RL does not provide quality splits for the Ant and Franka tasks, and we could try to synthesize quality splits by combining with random data, but this seemed like a poor proxy. Hopper provides these splits.\n\n5. Related work?\n\nThank you for pointing out this very related work and concurrent work, we will be sure to add a citation! It appears they have a similar use of BPE, but their goals are different: they discover BPE skills in the offline setting and then test the ability to generalize to downstream tasks with additional finetuning, still in the offline setting. Nowhere do they concern themselves with exploration or the online setting, and they use the entire vocabulary without pruning, which would be impossible for us as we show.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the time and care all reviewers have taken in reading our paper and offering feedback, and thank them for their input.

We are particularly happy to see reviewers appreciate the novelty and creativity of the proposed method (bwJh, iKv2), the extreme efficiency of the approach (bwJh, iKv2, g8NK, jRfS), the breadth of the evaluation (iKv2, g8NK, jRfS) and the quality of the presentation (bwJh, g8NK, jRfS).

We address concerns with the current draft in individual rebuttals for each reviewer below.

Meta-review: 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.
Decision: Accept (poster)