Dynamic Subgoal-based Exploration via Bayesian Optimization
Authors: Yijia Wang
Matthias Poloczek
Daniel R. Jiang
Venue: Accepted by TMLR ()

Abstract: Reinforcement learning in sparse-reward navigation environments with expensive and limited interactions is challenging and poses a need for effective exploration. Motivated by complex navigation tasks that require real-world training (when cheap simulators are not available), we consider an agent that faces an unknown distribution of environments and must decide on an exploration strategy. It may leverage a series of training environments to improve its policy before it is evaluated in a test environment drawn from the same environment distribution. Most existing approaches focus on fixed exploration strategies, while the few that view exploration as a meta-optimization problem tend to ignore the need for _cost-efficient_ exploration. We propose a cost-aware Bayesian optimization approach that efficiently searches over a class of dynamic subgoal-based exploration strategies. The algorithm adjusts a variety of levers --- the locations of the subgoals, the length of each episode, and the number of replications per trial --- in order to overcome the challenges of sparse rewards, expensive interactions, and noise. An experimental evaluation demonstrates that the new approach outperforms existing baselines across a number of problem domains. We also provide a theoretical foundation and prove that the method asymptotically identifies a near-optimal subgoal design.

Published in Transactions on Machine Learning Research (09/2023)
Dynamic Subgoal-based Exploration via Bayesian Optimization
Yijia Wang
yiul @pitt, edu
University of Pittsburgh
Matthias Poloczek*
matthicas-poloczekkggga de
Amazon
Daniel R. Jiang
drftang@meta..com
Meta AT, University of Pittsburgh
Reviewed on OpenReview: https: // openreview. net/ forum? id- TNJL4d5JRg
Abstract
Reinforcement learning in sparso-reward navigation environments with expensive and limited interactions is challenging and poses a need for effective exploration. Motivaled by complex navigation tasks that require real-world training (when cheap simulators are not available), we consider an agent that faces an unknown distribution of environments and must decide on an exploration strategy. It may leverage series of training environments its policy before it is evaluated in test environment drawn from the same environment distribution. Most existing approaches focus fixed exploration strategies, while the few that view exploration as a meta-optimization problem tend to ignore the need for cost-efficient exploration. We propose cost-aware Bayesian optimization approach that efficiently searches over a class of dynamic subgoal-based based exploration strategies. The algorithm adjusts a variety of levers the locations of the subgoals, the length of each episode, and the number of replications per trial in order overcome the challenges of sparse rewards, expensive interactions, and noise. An experimental evaluation demonstrates that the approach outperforms existing baselines across number of problem domains. We also provide theoretical foundation and prove that the method asymptotically identifies near-optimal subgoal design.
improve
1 Introduction
Reinforcement learning (RL) is becoming the standard for approaching control problems usually modeled by Markov decision process (MDP) in environments whose dynamics unknown and learned from data. In many applications involving navigation tasks, rewards are sparse and delayed. Since most RL algorithms rely, at least initially, on random exploration, this can cause an agent to require large, often impractical number of interactions with the environment before obtaining any rewards. Simultaneously, in real-world settings, it is often the case that fast and cheap interactions with the environment are not available, making it nearly impossible apply RL algorithms. To address the two issucs of sparse rewards and expensive interactions in navigation tasks, our objective in this paper is to design methods for learning better exploration policies in cost-efficient manner: specifically, we propose Bayesian optimization approach to optimize exploration strategy based subgoals, where each subgoal is defined set of states that the agent must reach, serving as an intermediate target for the agent to "complete" before navigating to the primary goal.
An illustrative example comes from the field robotics: autonomous systems have long been used to explore unknown or dangerous terrains (Matthies et al., 1995; Apostolopoulos al., 2001; Ferguson et al., 2004;
*The work was done before Matthias joined Amazon.

---

Published in Transactions on Machine Learning Research (09/2023)
Thrun et al., 2004). Policies learned offiine (e.g., via simmlator) common in these situations, but it may be beneficial to introduce agents that execute oflline-leareed exploration policy to guide the learning of an online policy that can better tailor to the details of the test environment. An example of this general idea can be found in Matthics et al. (1995), which describes the design of a rover for the Mars Pathfinder mission. One of the main lasks navigating the rover a rocky lerrain and reaching a goal (the test. environment). To train for the eventual mission, the engincers utilized an "indoor arena" that mimics the test environment. The need for cost-efficient training also arises in the setting of safe robot navigation (Oliveira al., 2020). Existing approaches to exploration have largely ignored the need to be cost-efficient during the training process and therefore are challenging to apply to real-world scenarios (see Section 2 for detailed discussion of related work).
In our setup, an agent is given a fixed (and small) number of opportunities to train in environments randomly drawn from a distribution E (henceforth, we refer to these as "training environments"), with the caveat that each interaction the training environment incurs a cost. After these opportunities are exhausted, the agent enters a random fest encironment Ç and exccutes an underlying RL algorithm to adapt the particulars of f, while aided by the higher-level exploration stralegy learned for E. One can view this formulation meta-optimization problem with two levels: upper-level problem to select exploration strategy, represented by parameters 0, and a lower-level RL task that explores with the help of the exploration strategy 9 on an environment instance { E.
(a) Original
(b) First subgoal
(c) Second subgoal
(d) Third subgoal
Example of a dynamic subgoal exploration strategy. The first, second, and third subgoals are denoted by the circle, triangle, and cross, respectively. The blue square is the starting location of the agent, the grey region a wall, the yellow region the location of the key, and the rod region is the door (goal). Note that although the second subgoal is not exactly in the location of the key, it brings the agent to the correct vicinity, allowing the underlying RL algorithm (executed online) to further adapt to the environment's particular details.
Figure 1:
We propose optimizing over class of dynomic subgoal erploration stralegies in the upper-level optimization problem. To illustrate this concept, consider the sparsc-reward environment shown in Figure la, where an agent is tasked with picking up "key" in the yellow region, in order to exit the "door" in the red region. The grey region is a wall. An RL algorithm paired with a naive exploration strategy making use of random actions (such as e-greedy) requires a prohibitively large number of random actions before finding a suitable path to the door through the key, while avoiding the wall. A dynamic subgoal strategy is an ordered set of subgoals (along with associated rewards leading to each subgoal, omitted here for illustrative clarity) that leads the agent a trajectory where the underlying RL algorithm is more likely to discover the optimal behavior. Figures 1b-ld together show an example of dynamic subgoal exploration with three subgoals, which first leads the agent to the vicinity of the key and later lowards the door. Note that the situation here in Figure is simplified in that we are actually interested in finding dynamic subgoal strategies that work on average across a distribution environments, rather than a single environment.
1.1 Our Contributions
Our main contributions are follows. We first propose framework for cost-efficient learning of dynamic subgoal exploration strategy for distribution of environments; in other words, interactions with the environment are expensive during training, making most gradient-based approaches infeasible. We instead
2

---

Published in Transactions on Machine Learning Research (09/2023)
N training environments
Training phase:
Subgoal design 0, Interactions т, Replications g.
Costly, real- world RL interactions
GP model f
Test phase:
Test environment
Distribution of environments
Subgoal design 0
Figure 2: Outline of the BESD algorithm. During the training phase BESD optimizes an exploration strategy (represented as subgoals) on sampled training environments. It then utilizes the learned subgoal design as an exploration strategy in the test environment to train an effective policy within a limited mumber of interactions.
leverage the Bayesian optimization (BO) paradigm, a well-known class of sample-efficient optimization techniques (Brochu et al., 2010; Snock ct al., 2012; Herbol et al., 2018; Frazier, 2018), and propose a new acquisition function as a core ingredient of our approach. The Gaussian process (GP) surrogate model used by the BO formulation has the ability to reason about the learning curve the underlying RI. algorithm, enabling to introduce two additional levers in the BO learning process to improve cost-efficiency: (1) how long to run each episode of training, (2) the number of replications to run in each training environment. These levers allow to intelligently trade-off running a longer trial versus more replications of shorter trials; the motivation is that, given < 72, an accurate evaluation of particular exploration strategy after steps may be more informative than & noisy evaluation of afler steps, even though the same number of euvironment interactions are used in both cases. The proposed algorithm, Boyesian exploratory subgoal design (BESD), is outlined in Figure 2. We also prove an asymptotic guarantee on the quality of the solution found by our approach, compared to the best possible subgoal-basee exploration strategy within given parameterized class.
2 Related Work
Our framework of cost-cfficient learning of exploration strategics through BO appears be distinct from existing formulations in its strong focus on expensive environmental interactions during training, made possible through the additional control levers of episode length and number of replications. Nevertheless, work is related to number of distinct areas of study: Bayesian optimization, exploration for RL, intrinsic reward and reward design in RL, multi-task RL, and transfer learning. Here, we attempt to give a tour through the various strands of relevance in each field.
2.1 Bayesian Optimization
BO is a technique for optimizing black-box functions in sample-efficient manner, in particular for tuning ML models and design of experiments (Snoek et al., 2012; Brochu et al., 2010; Frazier, 2018; Herbol et al., 2018). BO methods for problems with multiple information sources or fidelities (Swersky al., 2013; 2014: Feurer al., 2015; Domhan et al., 2015; Li al., 2017) is especially relevant to our proposed method's ability to select the length of an RL training episode, which builds upon ideas from Picheny & Ginsbourger (2013), Poloczek et al. (2017), and Klein et al. (2017). The first paper proposes fitting GP to partially converged simulations, and the latter two propose acquisition functions that consider the ratio of "information gain" to cost of evaluation. Our approach also reasons about multiple replications in an environment, similar to the problem studied in Binois et al. (2019) in the context of computer experiments. Our work fills a gap in the BO literature where the length of training and number of replications are selected jointly a cost-aware setting, a natural and powerful idea that has not been considered in the literature. Our theoretical analysis builds upon techniques developed in Frazier et al. (2008) and Poloczek et al. (2017) but extend them in
3

---

Published in Transactions on Machine Learning Research (09/2023)
directions, accounting for the ability to select the number of replications, and providing characterization of the asymptotic suboptimality due to using discretized domain."
BO has previously been applied in the setting of navigation planning, Martinez-Cantin et al. (2007), Martinez- Cantin et al. (2009), and Binney et al. (2013) use BO to optimize a sequence of waypoints for a robot to follow. While our method similarly optimizes a sequence of subgoals, we use the subgoals as an exploration strategy (over a distribution of environments) on top of an existing RL algorithm, rather than as a direct specification of the control policy. In order to allow subgoals to provide exploration in a "plug-and-play" manner for existing RL algorithms, our approach also features novel integration of subgoals with potential-bas based intrinsic rewards.
In two other works, Tesch et al. (2011) and Garcia-Barcos & Martinez-Cantin (2021), BO is directly applied to optimize a parameterized policy, but this is limited to low-dimensional parameterizations of the policy: Tesch et al. (2011) tune two-dimensional gait parameter, while Garcia-Barcos & Martinez-Canthn (2021) tune four policy parameters. In our work, we augment an underlying RL algorithm that can learn arbitrary policies with a B0-optimized low-dimensional exploration strategy, striking balance between flexibility and cost-efficiency.
2.2 Exploration in Reinforcement Learning
Naive exploration strategies such as e-greedy can lead to unreasonably large data requirements, making exploration a commonly studiod topic in RL. Most existing work focus on proposing a fixed exploration strategy that is executed for a single underlying environment. For example, some previous related work employ approaches based on optimism (Kearns & Singh, 2002; Stadie et al., 2015; Bellemare et al., 2016; Tang et al., 2017) and posterior sampling (Osband et al., 2016; Russo & Van Roy, 2014; Osband & Van Roy, 2017; Morere & Ramos, 2018) to guide exploration. Others insert an active learning (Shyam et al., 2019) or experimental design (Mehta et al., 2021) perspective into the model-based RL framework.
Our work departs from these existing studies in that we formulate the problem of exploration as a meta- optimization over a parameterized class of exploration strategies and aim to find a suitable strategy for a distribution of environments. A more closely related paper is Gupta et al. (2018), which extends the model-agnostic meta-learning (MAML) approach of (Finn et al., 2017a) to the problem of exploration for set of lasks in way that is similar in spirit to our formulation. However, their gradient-based approach is not sample-eficcient and they do not consider costly environment interactions during training. In addition, Gupta et al. (2018) make use of task-specific parameters during training, limiting their approach to a small set of environments. For a more comprehensive list of methods for exploration in RL, we refer the reader to the excellent survey of Amin et al. (2021).
2.3 Hierarchical Reinforcement Learning and Options
Our proposed approach is related to the hierarchical reinforcement learning (HRL) framework, which refers to methods that decompose complex, long-horizon problem into smaller subtasks; see Barto & Mahadevan (2003) and Pateria et al. (2021) for extensive reviews of the topic. A well-known type of HRL is feudal reinforcement learning, introduced in Dayan & Hinton (1992), where a high-level manager delegates low-level workers to complete subtasks. Examples of more recent work that follow this feudal hierarchy paradigm include Kulkarni et al. (2016), Levy et al. (2018), and Nachum et al. (2018). Our work exhibits similar flavor in that high-level BO method sets a subgoal-based based exploration strategy, which is then executed by the underlying RL algorithm.
The concept of options, which are temporally extended actions represented as policy and termination condition, also fall under the HRL framework. Options can improve the efficiency of RL through the use of previously acquired "skills" (Sutton et al., 1999; Precup et al., 1998). These skills might be acquired with the help of a human, either fully uscr-specified (c.g., Jothimurugan et al. (2021)) or obtained from expert demon-
I Discretizing the domain is common computational technique used when optimixing complex acquisition functions, but improve upon the existing theoretical analysis in Polorzek al. (2017) with explicit characterization of the induced error.
4

---

Published in Transactions on Machine Learning Research (09/2023)
strations (e.g., Pan et al. (2018), Paul et al. (2019)). In this paper, a subgoal is a particular type of option and therefore, our dynamic subgoal exploration strategy can be thought of, at a high level, as a sequence of options.
Of particular relevance to our work is when options are automatically discovered, a problem that is well-known to be challenging. One stream of work views option discovery to be (at least somewhat) detached from the RL reward maximization objective, using state visitation frequencies (Stolle & Precup, 2002; McGovern Barto, 2001; Goel & Huber, 2003), clustering (Mannor et al., 2004), novelty (Şimşek & Barto, 2004), local graph partitioning (Şimşek et al., 2005), diversity objectives (Eysenbach et al., 2018; Zhang et al., 2020), to name few examples. Approaches that considers joint objective for option learning RL reward maximization objective like ours (Kulkarni et al., 2016; Vezhnevets et al., 2016; Bacon et al., 2017; Frans et al., 2018; Veeriah et al., 2021) typically use large, neural network-based representations along with gradient-based (meta-)oph) Jottiizzitninn and do not focus on cost-aware training. The method that we propose in this paper is unique from previous works in that (1) it designed specifically for the case where cost-aware training is warranted and uses BO for option-learning, (2) offers an integrated objective for subgoal-desige and RL reward maximization, and (3) it uses novel combination of subgoals and reward shaping, which has simpler representation than generic option.
2.4 Intrinsic Reward and Reward Design
When particular subgoal of our proposed dynamic subgoal exploration strategy is active, we "turn on" set of artificial rewards that incentivize the agent to move toward that subgoal (these rewards are then removed after the agent moves on to the next subgoal). Hence, the literature on intrinsic reward and reward design in RL are also relevant. Intrinsic reward (also called intrinsic motivation) helps an agent learn increasingly complex behavior in a self-motivated way (Randløv & Alstrom, 1998; Ng et al., 1999; Huang & Weng, 2002; Kaplan & Oudeyer, 2004; Şimgek & Barto, 2006; Gonzale et al., 2010; Pathak et al., 2017; Achiam & Sastry, 2017; Lample & Chaplot, 2017). Several works from the reward design litcrature are most closely related to our paper. Sorg et al. (2010) and Guo et al. (2016) directly optimize the intrinsie reward parameters, via gradient ascent, to maximize the outcome of the learning process. Similarly, Zheng et al. (2018) use intrinsic rewards in policy gradient, and treat the parameters of policy as a function of the parameters of intrinsic rewards. Again, these methods differ from ours in that they do not consider the costliness of training and focus on finding intrinsic rewards for a single MDP.
2.5
Multi-task RL and Transfer Learning
Also related to our setting are methods that aim to train agents with the capability of solving (or adapting to) multiple sequential decision making tasks (Pickett & Barto, 2002; Konidaris & Barto, 2006; Wilson et al., 2007; Feruández et al., 2010; Deisenroth et al., 2014; Doshi- Velez & Konidaris, 2016; Finn et al., 2017;;b; Pinto & Gupta, 2017; Espeholt et al., 2018; Hessel et al., 2019; Vithayathil Varghese & Mahmoud, 2020); such methods generally fall under the umbrella of multi- task RL or transfer learning. As before, many of these methods require the training of large neural networks and are not designed for cost-aware setting. Despite their stated purpose of being sample-efficient in adapting to new tasks, most multi-task RT. or transfer learning approaches do not place strong emphasis on cost-efficiency of training on existing tasks. This is an important distinction to our work. The two papers that are closest in spirit to our work are Pickett & Barto (2002), where macro-actions are extracted from previous tasks, and Konidaris & Barto (2006), where shaped rewards are learned for a set of tasks. One drawback of Pickett & Barto (2002) is that assumes accoss to optimal policies for an initial set of MDPs. Konidaris & Barto (2006) directly uses previous value functions as shaped rewards (thereby requiring the agent to solve some tasks from scratch) and does not provide an avenue for cost-effective exploration.
3 Problem Formulation
This section formulates the problem mathematically, by defining the original (sparso-reward) MDPs and how a dynamic subgoal exploration strategy induces an auxiliary, "subgoal-augmented" MDPs. We then describe the iterative training process.
5

---

Published in Transactions on Machine Learning Research (09/2023)
3.1 Original MDPs Me with Sparse Rewards
Consider a family of MDPs (Mę = A, Te, Re,7))e parameterized by random variable ~ E, where S and A are the state and action spaces, Tg is the transition matrix, Rg : S x xx - IR is the extrinsic" reward function, 7 E [o, 1] is the discount factor', and E is the environment distribution (not assumed to be known, nor does it need to be finite or discrete). 4 A sparse-reward environment is an environment where Rg is non-zero only for a small number of " "goal" states. To ensure that all quantities are well-defined, we assume that Rg is bounded, as is common in the reinforcement learning literature. We assume common state and action spaces across the distribution of MDPs (i.e., they are independent of E); while the reward and transition functions vary with g.
Given S and A, policy is mapping such that <(|1s) is a distribution over A for any state 8 E S. For any & ~~ E, define the value function of policy a at any state as
Ve (s) = E Σ y (e ar S2+1) TT,
(1)
where the notation of "conditioning" on I and indicates that su = s is the initial state and at ~ (())))). For the MDP Me, its optimal value function and associated optimal policy are
Ve( = sup (s) and =5(s) E arg max TE. (s,e(s,,,s')) + (V)( [.
aEA
Now that we have defined the value function, let comment on the environment distribution E. In Section 3.4, we will formulate the vntaaooptimizaiion problem, which requires that the expected performance of any policy π over the environment distribution, i.e., Rg[VV (s)], is well-defined. However, since we assumed bounded rewards, implying bounded performance V (s), it will always be the case that this expectation exists and we do not require further assumptions on E.
When the extrinsic reward function Re is sparse, it produces little to no learning signal for the agent. Under most RL algorithms, the agent essentially performs random exploration and does not start learning until the first time it wanders to the goal. The time it takes to find the goal under random exploration strategy is often prohibitively long. The e-greedy exploration strategy, which takes random action with probability and the best action under the current value function approximation, is an example of a random exploration strategy.
3.2 Dynamic Subgoal Exploration Strategies
An intrinsic reward is an artificial reward signal experienced by the agent that does not come directly from the environment. A subgoal is defined by a (usually small) set of states, such that when the agent lands in any of them, the subgoal is considered "completed." A dynamic subgoal exploration strategy is a sequence of subgoals, along with an associated reward shaping function for each subgoal, that provides an intrinsic reward signal for the agent. If the locations of the subgoals are chosen well, this strategy can help the agent explore the environment efficiently. We call this a dynamic strategy because the subgoals are turned on one-by-one and consequently introduces new state into the MDP (described in detail below).
Suppose there are K subgoals and let 0 E θ be paramcter that fully describes a subgoal exploration strategy, including the subgoal locations, associated rewards, and sequencing. Let Ga. S S be a set of "target" states associated with the kth subgoal, for E (1,2...., in the sense that if the agent lands in some state in G0 then the kth subgoal considered "completed." In addition, we define an artificial reward function (s.s)) that, when activated, provides sequence of rewards that leads the agent toward subgoal k. Coneretely, we use potential-based reward shaping from Ng et al. (1999) to achieve this. Let L be a potential function, function that assigns value for each state in S, with higher potential indicating more
PIn Section 3.3, we describe how a dynamic subgual exploration strategy supplements the extrinsic reward function with additional intrinsic rewards.
We allow for the case of cpisodic MDPs, where 7 = provided that any policy will reach a ferminal state with probability one. A terminal state absorbing and any action taken in that state gives zero reward. Note that our approach also applies to the case single environment the distribution contains only one environment.
6

---

Published in Transactions on Machine Learning Research (09/2023)
"valuable" state. fø.k should have the property that target states in Go have the highest potential. Then, let
g0 s') = = (o)
(2)
for all s E. The definition of ( 8') in (2) can be interpreted as the difference in potential between states of and 8 (with discount 7). This potential difference motivates the agent to move towards the target states (high potential) of kth subgoal. Thus, parameterization of set of K subgoals, which forms our exploration strategy, is fully described by
(19,,x) f90 (90))
the locations and associated reward shaping functions.
Example 1 (Key and Door Environment) Let us consider distribution of moze MDPs with states (ssiigin and a sporse reword in the upper left corner at (0, 10). In addition, suppose that the agent needs to pick up a key in order to receive the reward at (0, 10), where the location of the key is uncertain but likely to be in the right half of the room. The enwironment illustrated in Figure can be considered to be one possible realization from this distribution of mazes. Now, let us consider subgoal design with K 3 subgoals. The simple parameterization 0 (11, b2, f2, iz, with
Go.s ((in) and (o)x(s) = (s) -(lls-(iede)))
specifies that for (1,2,3), the kth subgoal is located at a single state (ik)Je) and the artificial reward potential a Gaussian centered at ju). Using Figure 1 as visual reference, one can imagine that the subgoal design 0 (1, 8, 4, 2) would be useful in guiding the agent toward the vicirity of the key on the right side of the room and then toward the vicinity of the goal. Once the agent is in the correct vicinity, the underbying RL algorithm can discover the precise locations of the key and gool in the particular environment realization more quickly.
3.2.1 Subgoal Parameterization vs State Dimensionality
For the types of navigation tasks that we are concerned with in this paper, the dimension of the subgoal parameterization 0 need not scale with the dimension of the state which would pose a potential scalability issue. Instead, one general rule-of-thumb to keep in mind is that for a dynamic subgoal exploration strategy to be effective in navigation tasks, the dimension of 0 only needs to scale with the number components of that pertain to the spotial positioning of the agent. The next example provides an illustration.
Example 2 (Mountain Car Environment, with dim(0) < dim(s)) Consider the well-known Mountain Car problem, continuous control task where an underpowered car, operating in one-dimensional space, must make its way up steep mountain (Sutton & Barto, 2018, Example 10.1). The state is two-dimensional, = (z, ,), where x E [-1.2,0.3 0.5] is the position of the agent while & E [-0007 0.07] is its velocity. A possible subgoal design with K = is 0 (i1, with
Go.k = ((ie, 4) i E 0-.07.0..7) and e
for each k. In other words, the agent reaches a subgoal larget state if ils posilion is in, for any value of its velocity. Also, the artificial reward only depends on the spatial position x rather than the full state (x, i). In Section 5, we give rumerical results for exactly this example.
One could imagine that the concept illustrated in Example 2 also applies to more complex robotics environments with a high-dimensional state, where the number of components related to the spatial positioning is relatively small. This suggests that the subgoal paramoterization (and the resulting BO problem) is often of much lower dimension than that of the state itself.
3.3 Subgoal-Augmented MDPs Mg.0
Now that we have described how particular subgoal design is parameterized, the remaining question is how these are integrated in a useful way into the original, sparse-reward MDP described in Section 3.1. We
7

---

Published in Transactions on Machine Learning Research (09/2023)
propose the notion of a subgoal-augmented auxiliary MDP, where the K subgoals are sequentially "activated." This way, we encode subgoal ordering into the exploration strategy, meaning that the agent only moves on to the next subgoal after finishing the current one.
Let Mg.o denote an auxiliary, subgoal-augmentt MDP based on an original MDP Mg. except that is includes rewards and transitions associated with the dynamic subgoal exploration strategy We introduce an auxiliary state i == {0, ,,,1,,.,.... ....,,K, where represents the number of subgoals reached by the agent far. Initially, we have in = O. The state of the Ma,9 is (s. E S x I and the transition for the auxiliary state is /' = i + [s' :.. where we take Ge Ke,K+1 Ø. This means the auxiliary state i is updated to + whenever s' reaches the next subgoal. Let the intrinsic reward of the agent be:
Σ ( 900 (St, 8t+1);
where the indicator function encodes the logic that if is subgoals have been completed so far, then the current. larget is subgoal is + 1 and only the rewards leading to subgoal j + are active. The new reward function consists of both extrinsic (Rg) and intrinsic (Gg) rewards:
i,, s') Ro(s,a,)) + Go(s,,,s).
The value function for the new MDP Me, is written
(s, = Σ 7 Rg, ie, ai S1+1) 1 8,
(3)
where i)) is now a policy defined on the new state space S x I.
Figure 3 gives an example of the overall sctup: Figure 3a shows the original MDP environment Mg, where the dark gray cells are walls, the light gray represent uncertainty in the size of the "doors", and the red cells represent goal states (the sparse, extrinsic reward). Figure 3b shows the possible rewards the agent can encounter in the augmented MDP Ma,e, for random selection of subgoals 0. The original sparse reward is reprosented by the red bar in the corner and the first subgoal is the one that is farther from the goal. Both subgoals are singletons and the potential functions are radial basis functions centered at the subgoal locations, similar to the paramctorization described in Example 1. Note that this randomly selected set of subgoals 0 is not a good exploration strategy for the enviromment in Figure 3a (as it leads the agent toward a wall), motivating the need for optimizing their locations, as we discuss in the next section.
3.4 Optimizing the Exploration Strategy
The selection of the subgoal design 0 depends on the agent's underlying learning algorithm, which could in principle be any RL algorithm where intermediate rewards influence the learning process: this includes any temporal difference-basee algorithm that makes use of learned value functions. In the numerical results of Section 5, our agent learns via Q-learning Watkins & Dayan (1992). We refer to the underlying RL algorithm as RL-ALGO. Let us use the notation RL-ALGO[T, M] to refer to the policy learned by RL-ALGO on MDP M after 7 training interactions. We remind the reader that the aubgoal-based exploration strategy fixed before the test environment is revealed, so that the sequence of events in the test phase is as follows:
1. A subgoal design 0 for exploration is selected. The agent is placed in new environment &.
3. The agent uses the subgoal-angmented MDP MM.0 and an RL algorithm with a budget of Tmax interactions to learn a policy RL-ALGO (Tmxx: Mg.j.
4. The agent's 's policy is evaluated using only the extrinsic reward function Re of the original MDP.
Without ordering, rewards from multiple subgoals can inhibit the agent's progress.
8

---

Published in Transactions on Machine Learning Research (09/2023)
04
5
15
20
15
10
(a) 20 x 20 Gridworld Environment
(b) Goal and Subgoal Rewards
Figure 3: An example that visualizes an environment and a random dynamic subgoal exploration strategy along with the rewards of the associated subgonl-augmentee MDP.
Our goal is to find an exploration strategy E such that a policy trained using behaves well in the original MDP:
max E
Σ 7't (B, T=0
des 8141) amm (so, io) with "..0" RL-ALGO [Tmax Mg,e],
(4)
where (so, in) is the initial augmented state. The interpretation of the objective in (4) is as follows: Evaluate MDP) using the same dynamics the subgool-augmente
gE (a policy for the but without the rewards associated with the subgoals. In other words, the policy takes actions based on the augmented state (st, it), but only receives rewards associated with the original MDP. This explains why we need to consider a starting state (so: io): rather than just so (note that the reward does not depend on the auxiliary state it).
MDP,
The expectation in (4) is taken over the random choice of test environment &, the stochastic dynamics within Ma, and the stochasticity of the learning algorithm itself. Tt is convenient to explicitly define the following:
u(O DC
7²t Rg (st, aes st+1) f0 so, io with o6 = RL-ALGO (T,.,e)T,MM,]]
Although the objective function in (4) u(0, Fmax), the notation w(0,7) 7) will be useful in Section 4, where we discuss using fewer than Tmax interactions to learn about u(O, Tmax) as way of reducing cost.
3.5 Iterative Training and Additional Rost-Reduction Levers
In our setting, we observe the performance of exploration strategies and the resulting policies in a sequence of training environment realizations .2......,, gN drawn from the MDP distribution E. By default, each complete evaluation of the objective function in (4) u(0, 7max) for a fixed 0 requires running RL-ALGO for Tmax interactions. Since each interaction in the training environments is expensive (e.g., in robotics applications, this could involve time, labor, and equipment), we want consider ways to reduce the number of training interactions. To do so, we propose two additional levers:
Maximum number of interactions. For each training environment e" we allow the specification of a maximum number interactions r", chosen from a finite set T C N. In episodic tasks, if an episode finishes before nh interactions are used, we start a new episode and continue in this manner until exactly 7" environment interactions are exhausted. In the next section, we describe our probabilistic model of the RI. training curve, which allows observations of short episodes to

---

Published in Transactions on Machine Learning Research (09/2023)
be informative about the final performance. This also can reduce the risk of spending too many interactions with an unpromising exploration strategy.
2. Multiple replications. We can reduce the variance of performance observations by averaging over the observed cunulative reward over q" i..d. replications, for total of r"q" interactions in training environment 5=*1. Each replication is an independent invocation of an agent. We suppose that q" is chosen from a finite set Ω. The idea here is that even with the same number of total interactions, a lower variance observation of a "preliminary" result could be more informative than a higher variance observation of the "full" result.
To summarize, three decisions are made at the beginning of each training opportunity n: (1) choice of subgoal design 0", (2) the maximum number of interactions r", and (3) the number q" of independent. replications to use for this particular 0", For each of the q" replications, we obtain a policy
= RL-ALGG [T", MMg=+ ,n]]
before observing a estimate of its performance. After the q" training replications are complete, we compute the average performance over the g" replications. Written more succinctly, our observation in episode n takes the form
y n+ "0",00""""""
T" """""" u(00",")) + seev + t
e (q").
where e represents the deviation from the u(0", due to the random environment g"+1, while the observation noise "x""("") (q") represents the noise that can be reduced via multiple replications, i.c., the noise in ag=+1 on due to a sample run of RL-ALGO. Thus, (q"" depends on the number of replications q". Naturally, a larger number of replications implics smaller observation noise. Note that the obsorvations {v"} are i.i.d., since new MDP is sampled in each iteration. The total training cost. incurred is cumulative number of interactions: Σx- r""".
After training opportumities 0, ......... - 1, we reach the test phase and commit to a final subgoal design AN This design is evaluated the test MDP e++ ~ E with agent that has a full budget of Tmax interactions.
4 Bayesian Optimization for Cost-Efficient Exploration
The setup for BO typically consists of two components: (1) a probabilistic surrogate model (usually a Gaussian process) for modeling the objective function, and (2) an acquisition function, which given dataset of past. observations, assigns score to each potential observation location (Garnett, 2023). Selecting the optimizer of the acquisition function as the next point to sample gives rise to strategy for balancing exploration with exploitation. The BO "loop" repeats the following: sample a point (using a combination of the current. surrogate model and acquisition function), observe new data, and update the surrogate model. For a detailed tutorial, we refer readers to Frazier (2018) and Garnett (2023).
For our setting of learning a dynamic subgoal exploration strategy, we propose a tailored probabilistic model for the RL learning curve and acquisition function for selecting the next subgoal design, the maximum episode length, and the number of replications to run. Although shorter episodes and smaller number of replications are more cost-efficient, they also decrease the chance of reaching the goal and produce higher observation noise. Thus, the acquisition function must carefully trade off these downsides with the cost of interactions. We call this the Bayesian Exploratory Subgoal Design (BESD) acquisition function.
4.1 Surrogate Model
In order to enable the ability to dynamically select the maximum episode length of training, as described in Section 3.5, our approach uses a GP surrogate model over 7), rather than u(0, 7max). In other words, our model is a function of both 0 and 7 rather than just 0, enabling it to capture the performance of a policy trainod with subgoals f, for a variety of episode lengths. Assume that θ C T.... We place GP prior o on the latent function with mean function μc: θ T + R and covariance function k : (0 x T) x (0 T) - R4. More precisely, to capture the structure of the RL learning curve, we set μ to the mean of initial set.
10

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 1 Bayesian Exploratory Subgoal Design
1. Set n = 0. Estimate hyperparameters of the GP prior using initial samples.
2. Compute next decision (0", ,T", "r""""" according to the acquisition function (7).
Train environment g augmented with Hr (Mgnti,gu) using levers (T", g²").
4. Observe y (0", .*) and update posterior on f-
5. If < N, increment and return to Step 2.
6. Return a subgoal recommendation 0 that maximizes f (0, Tiaxx).
of samples and use multidinenssioal product kernel, based on the kernel used in Klein el al. (2017) for modeling ML performance as a function of parameters and time:
4: ((,,T), (0','''))) x')) = ko( 07) ky (T,
(5)
where the first kernel hg is the (5/2)-Matérn kernel and k,- is a polynomial kernel ky (T, = ((T) Eg 6(T') with ((T) = (1, and hyperparamntters Eg. Note that the covariance under k is large only the covariance is large under both kg and ky. We make the modeling assumption that ex+1 and eppp are independent, zero mean, and normally distributed with variances oe and 0qpp/"", respectively. This allows advantage of standard GP machinery to analytically compute the posterior on f conditioned on the history after steps. This posterior is another GP, whose mean and kernel functions are denoted n² (0,T) and k" ((0, T), (0', 7')); the exact expressions can be found in, e.g., Rasmussen & Williams (2006).
take
We remind the reader that the dimensionality of the GP surrogate model is dim(@) + 1, i.c., the dimension of the subgoal parameterization, along with an additional dimension for т. As illustrated in Example 2, it will often be the case for navigation domains that the dimension of the subgoal parameterization is smaller than that of the state space of the underlying RL problem (due the relatively small number of spatial components of the state). Therefore, dynamic subgoal exploration strategies can be tractably modeled and optimized for broad classes of navigation problems, even with vanilla GPs.?
4.2 Acquisition Function
As described above, the proposed algorithm proceeds in iterations, selecting one set of subgoals tth along with 7" and q", to be evaluated in each training enviromment. We now propose the acquisition function for making these evaluation decisions. An overview of the BO setup is given in Algorithm 1.
Suppose the training budget is used up after training iterations 0, 1,..... decision to use subgoals on the lest MDP eN+1 that have maximum expected performance under the posterior. The expected score of this choice is μºa where
, N 1. Then, the optimal risk-neutral
(6) where (0, Tmax) [,, mmax]]. Here En is the conditional expectation with respect the history after the first n observations: (80, r .. v'''..... ...... fn..,,n-1,_ ,,=== _qm=1 y)).. Note that although fewer than Tmax interactions in training environments to reduce cost, the agent uses its full budget for the test MDP N+11
1 == maxe n² (0, Tmax):
allowed to use
The proposed acquisition function is based upon the knowledge gradient, which one-step lookahead approach (Frazier et al., 2008; 2009). That means we imagine for each training MDP that it is the last opportunity before the test MDP and act optimally. Full lookahcad approaches require solving an intractable dynamic
6 Although the assumption of normality is commonplace in BO for tractability of the posterior (Frazier, 2018), other noise distributions can be used through appropriate likelihood function.
When the need arises to optimize for high dimensional subgoal paramcterizations, one may opt for scalable extensions of the model and optimization formulation; see, e.g., Wang et (2016); Mutny & Krause (2018); Nayehi al. (2019); Eriksson al. (2019); Papenmeier et. (2022; 2023). We leave extensions in this direction future work and focus on more standard setting.
11

---

Published in Transactions on Machine Learning Research (09/2023)
programming problem; however, we show that nonetheless, the one-step approach is asymptotically optimal in Theorem and Theorem 2. If we evaluate (0,),)) i.e., the subgoals 0 for steps and q replications, then the expected gain in performance in the test MDP of the recommended exploration strategy after the evaluation, based on (6), with respect to the current best is
( r, g) = En [u=+ 8" = 0, T" = T. -
Therefore, the one-step optimal stralegy is to choose the next subgoals 0", maximum episode length r"; and number of replications q" so that v" is maximized. However, this strategy would generally allocate a maximum number steps Tmax and replications Qmax for the evaluation the next subgoal design, as observing Tmax during training is most informative, and repeating for qmax replications reduces the noise maximally. In other words, this strategy does not consider the cost of training.
Hence, we propose acquisition strategy that maximizes the gain in performance per effort:
D" (",,,T,))
"""""",""" E arg max 0,r
(7)
qT
The optimization problem (7) is challenging when the domain θ is continuous, we take the approach of replacing it with discrete domain θ θ (for example, this could be selected by Latin hypercube design (Stein, 1987)). This approach has been applied successfully in other knowledge gradient style acquisition functions (Scott et al., 2011; Wu & Frazier, 2016; Poloczek et al., 2017). We provide a novel theoretical guarantee on the asymptotic suboptimality of a discretized optimization domain. characterizes the Lipschitz constant explicitly, thereby improving on the analysis of Poloczek et al. (2017); see Theorem in the next section.
4.3 Theoretical Analysis
We now provide our main theoretical results on the asymptotic optimality of BESD. Detailed proofs can be found in Appendix A. For convenience, suppose ((0, for all (0, and further assume that the kernel k(---) has continuous partial derivatives up to the fourth order. Recall that ON O is the final recommendation made in iteration N:
E arg max 4º' (0, Tmax).
Fee
PEô
Our first theorem is concerned with the finite, discretized optimization domain θ.
Theorem The acquisition function described in (7) has the property of asymptotic optimality with respect to 6, i.e.,
lim S(ON Tmax) max f(0, Tmax), 8E8
N-000
almost surely. That is, the recommended design ON becomes oplimal as N 00.
If the optimization domain θ O, then Theorem suffices. Unfortunately, for many applications, the subgoal parameterizations will naturally be continuous. Next, provide additive bound the difference between the solution of BESD in & and the unknown optimum in O, the number of iterations N tends to infinity.
We use a probabilistic Lipschitz constant of GP from Lederer et al. (2019) to quantify the performance with respect to the full, continuous subgoal parameter space. We make use of the fact that the derivative df (0, dd0, is another GP with covariance
22
(0, 0') 00,00
k((0, Tmax)) (0', Truax)):
for all i 1,2, m (Rasmussen & Williams, 2006, Section 9.4). See also Ghosal et al. (2006) and Wu et al. (2017) for other uses of this property. For each 1, 11,,,..,,m. m, define the constant
2m )
+ 12y6m max o R /
L) = kd
2 2log
L max dist(0,
(8)
12

---

Published in Transactions on Machine Learning Research (09/2023)
Random Doors' (1x8)
15
B
10
4
Random Wall (1x6)
5
2
0
2
15
(a) GW10 Domain
(b) GW20 Domain
Figure 4: Recommendation paths for GW10 and GW20. The blue and red shaded regions denote the starting points and goals, respectively. Dark and light gray regions possible locations of walls and doors, respectively. Each plot displays four realizations of the "recommendation paths" of BESD. Each color corresponds to one sample realization, and the color becomes darker as n increases, with the lightest points being the initial samples. The circles and triangles represent the first and second subgoals, respectively, of the exploration strategy. The 'A' and 'B' labels point out two example sets of subgoals displaying notable behaviors.
where LE be a Lipschitz constant of the kernel h and kaax = maxsge V (0,00.
The acquisition function of (7) has bounded asymptotic suboptimality with respect to the original domain in the sense that with probubility at least - 8, holds that
Theorem
Tim 1(0N Tmax) 2 maxege [0, Tmax) d. [|Ta8]]
where d = maxsge mingree (0, 0²) is mensure on the "courseness" of the discrelization and Ls is the vector (L) L with each L3 defined as in (8).
5 Numerical Experiments
We now show numerical experiments to demonstrate the cost-effectiveness of the BESD framework. BESD is implemented using the MOE package (Clark et al., 2014) and the full source code be found at the following URL: https: / git.t....bb.... com/yj /jj comm/yjang06618 (amng0001///uboalll basaall-aaaddddaae expl poatiinn... In the experiments that follow, we use the BESD approach to optimize dynamic subgoal exploration strategies consisting of two or three subgoals.
BESD given few choices for the interaction length and number of replications q (values reported for each benchmark below). Each replication of the BESD is given an initial set of 10 observations for each value of 7 (these initial observations incur interaction costs just like future observations). The potential function at exp[-0.5(s - -)) where the "height" is 0.2
state with the jth subgoal activated is (s) and "width" is W2 10. The underlying RL algorithm for all environments is Q-learning with an e-greedy behavioral policy (with e = 0.2) for all environments.
In the next few subsections, we first introduce each of the environments and along the way, show some qualitative results obtained by BESD, focusing on providing intuition. Later, in Section 5.6, we introduce the baseline algorithms used for empirical comparison, and in Section 5.7, provide discussion of those results.
13

---

Published in Transactions on Machine Learning Research (09/2023)
5.1 Windy Gridworlds with Walls
The first set of environments (GW10) is a distribution over 10 x 10 gridworlds, where the goal is to reach the upper left square that is shaded red in Figure 4a to collect a reward of one. The agent starts from the lower-left grid square shaded in blue and may in each step choose an action from the action space consisting of the four compass directions. Each gridworld is partitioned by a wall into two rooms. The wall, randomly located in one of the middle five rows in the gridworld, has a door located on four grid squares on its right. The agent will stay in the current location when it hits the wall.
There is a small amount of "wind" or noise in the transition: the agent moves in random direction with probability that is itself uniformly distributed between 0 and 0.02 (thus, a particular environment instance drawn from the distribution has a random wall location and wind probability).
We use T= = {200, 600, 1000} for the possible values of t and Q = {5,20} for the possible values of 9. We parameterize the exploration strategy using two subgoals, whose locations are optimized. Subgoal locations are limited to the continuous subset of IR² which contains the grid, i.e., O ((0, 10] x [0, 10])2 for GW10.
5.1.1 Recommendation Paths for GW10
In order to visualize the qualitative behavior BESD, we show in Figure 4a the evolution of the recommended subgoals over time (itcrations), a concept that we refer to as recommendation path. The plot displays four recommendation path realizations of BESD using distinct colors. Within each color, the lightest points are the initial samples while the darker points represent recommendations for larger n. Also within each color, the circles represent the first subgoal of the exploration strategy, while the triangles represent the second subgoal. We point out two types of exploration behaviors discovered by BESD in Figure 4a:
Behavior 'A': The pairs of regions labeled 'A' are the final recommendations of the orange, green, and purple sample paths. The strategy leads the agent toward the upper right corner (away from the wall), and then after that, directly towards the goal.
Behavior 'B: The final recommendation of the red sample path is labeled by 'B'' Note that in behavior 'A', a direct path to the first subgoal (upper right corner) is blocked by the random wall for some realizations of the environment. Behavior 'B' might be interpreted as a slight remody of this situation by targeting a lower region of the right edge, creating a more direct path around the wall.
Both strategies appear to be reasonable ways for the agent to avoid the door and head to the goal.
5.2 Larger, Three-Room Windy Gridworlds
The second domain (GW20) is a distribution of larger 20 x 20 gridworlds with three rooms soparated by two walls. As shown in Figure 4b, the walls are randomly located in the middle rows (dark gray). A door of size 8 randomly located somewhere within the wall, shaded in light gray. The starting location is the blue square in the lower left and the goal is displayed in red in the upper right. As in GW10, we optimize the locations of two-subgoal exploration strategy, with θ = ([0, 20] x [0, 20]) The noise due to wind is the same in GW10. In this experiment, we consider the case of only allowing BESD to select the maximum episode length from T = {4000, 7000, 10000}, while keeping = 20 fixed.
5.2.1 Recommendation Paths for GW20
Recommendation paths are shown in Figure 4b. Unlike the case of GW10, all four of the realizations converge to roughly the same exploration strategy, labeled by 'A.' Focusing on the lighter red and orange circles, we can notice trend of the first subgoal initially being placed (naively) near the goal, but as learning progresses, they move downward toward the entrance of the first. door. The second subgoal converges toward the exit of the second door, moving the agent near the goal.
Regarding the placement of the first subgoal near the goal and inducing a direct path, is worth pointing out this strategy might work for some environments (i.e., those where the first door is at its leftmost position
14

---

Published in Transactions on Machine Learning Research (09/2023)
Random Treasure (1x1)
4
11.
-0.8
0044
0.0
0.4
B
B
(b) MC Domain
(a) TR Domain
Figure 5: Recommendation paths for TR and MC. The first panel, Figure 5a, largely follows the same design as Figures 4a and 4b, except that the green squares represent possible location of the trcasure. In the second panel, Figure 5b, since the location of the mountain-car is one-dimensional, we visualize the four recommendation paths by spacing them vertically to avoid crowding (therefore, the vertical axis represents different trajectories, each shown in a different color). The initial location of the car is colored blue, while the goal is in red, corresponding to the overlay of the mountain. See the caption of Figure for an explanation of the symbols used.
and the second door is at its rightmost position). However, BESD learns that in order perform well across the distribution of environments, the strategy of first moving rightward is better.
5.3 Treasure-in-Room
The third domain (TR) is a distribution of 10 x 10 gridworlds with a "treasure" hidden in a small room; see Figure 5a. The light green area shows the possible positions of the treasure. The agent gets a reward upon entering the square with treasure, and reward of 10 upon reaching the goal. The cumulative reward, however, is zero if the agent does not find the goal within the interaction budget. The discount. factor is set to y 0.98 to encourage policies that collect the reward carlier. We sct T {400, 1200, 2000) and Q [5, 20).
5.3.1 Recommendation Paths for TR
The recommendation paths for TR are shown in Figure 5a. We observe that two strategies were discovered by BESD across these four realizations:
Behavior 'A: This appears to be the ideal behavior and was discovered in the orange, purple, and red sample paths: first lead the agent to the treasure and then toward the goal through the upper right. It is also notable that the first subgoal is located at the bottom of the room, meaning that wherever the treasure turns out to be, the agent can pick it up without backtracking.
Behavior 'B: The green sample path's final recommendation coincides with the (apparently subopti- mal) exploration strategy denoted by 'B' simply leads the agent to the treasure, but does not provide any guidance toward the goal. We highlight that this an instance where BESD's lcarning is not yet. complete, evidenced by the fact that behavior 'B' is often recommended in carlier iterations of the orange sample path. In that case however, BESD eventually discovers behavior 'A" in later iterations.
15

---

Published in Transactions on Machine Learning Research (09/202))
B
A
B
4
B
B
B
Random Keys (2x2)
Random Keys (2x2)
8
2
(a) KEY2 Domain
(b) KEY3 Domain
Figure 6: Recommendation paths. The blue and red shaded regions denote the starting points and goals, respectively. Dark and light gray regions possible locations of walls and doors, respectively. Each plot displays four realizations of the "recommendation paths" of BESD. Each color corresponds to one sample realization, and the color becomes darker as n increases, with the lightest points being the initial samples. The circles, triangles, and crosses represent the first, second, and third subgoals, respectively. The 'A' and 'B' labels point two example sets of subgoals displaying notable behaviors.
5.4 The Mountain Car Problem (MC)
The mountain car (MC) domain, as we introduced in Example 2, is a commonly used RL benchmark environment that tests an agent's ability explore, as it required to go in the opposite direction of the goal in order reach the top of the mountain; see, e.g., (Sutton & Barto, 2018, Example 10.1). For this experiment, created distribution of environments by randomizing the starting location of the agent, which is chosen uniformly from [-0.6, -0.4]. Here, we set T (4000, 7000, 10000) and Q (10, 50}.
5.4.1 Recommendation Paths for MC
The subgoal-pairs discovered by BESD are shown in Figure 5b; they tend to be on opposite sides of the agent's 's starting location, thereby creating back-and-forth movement needed to generate momentum and move up the mountain. is worth noting that the symmetric behaviors of going from left to right (Behavior 'B' in Figure 5b, for the orange sample path) and going from right to left (Behavior 'A', exhibited by the green, red, and purple sample paths) can both be found in the results of BESD.
5.5 Key-Door with Highly Varying Key Locations (KEY2 and KEY3)
In our last experiment, test for the situation where the distribution of environments E contains environments that might vary dramatically from one another. We also consider how the exploration behavior changes when we add an additional subgoal to the strategy.
In domains KEY2 (with two subgoals) and KEY3 (with three subgoals), we consider a 10 x 10 gridworld with one wall, where a "key" needs to be picked up before opening a closed door at the upper-right corner of the grid. The location of the key, however, highly varying and is either near the left wall or the right wall. The environment is visualized in Figures 6a and 6b. We set T {400, 700, 1000) and Q (5,20).
16

---

Published in Transactions on Machine Learning Research (09/2023)
5.5.1 Recommendation Paths for KEY2/KEY3
It important that the agent moves in the vicinity of both keys in order for to perform well across the distribution of environments. We now discuss how this is achieved by the two- and three-subgoal exploration strategies, using the annotations in Figures 6a and 6b.
Behavior 'A' in KEY2 (Figure 6a): In the first exploration behavior discovered by BESD, the agent is first directed to the right-most key location and then towards the door. This is behavior reasonable in the sense that the agent's initial location is near the left-most key location; hence, the naive exploration (e.g.; e-greddy) "built-in" to RL-ALGO would likely find the key (if it is there) without. additional subgoal rewards.
Behavior 'B' in KEY2 (Figure 6a): The second exploration behavior that we highlight takes a similar approach. This strategy incentivizes the agent to first check the left-most key location (going upwards from the initial location). Interestingly, the second subgoal is neither the other key location nor the goal: instead, the agent is directed toward the upper edge of the environment, slightly right of center. Upon examination, one might conclude that this path compromises between the second key location and the goal. On its way from the first to second subgoal, the agent enters the vicinity of the second key location and also ends up not far from the goal. In other words, the exploration strategy puts the agent in a position such that RL-ALGO's ' naive exploration is more likely to be successful.
Behavior ''' in KEY3 (Figure 6b): With an additional subgoal to work with, BESD is able to find more flexible exploration strategies. For behavior 'A', we see that the first subgoal is near the left-most key location, the second subgoal indirectly leads the agent loward the vicinity of the right-most key location, and the third subgoal at the goal. The placement of the second subgoal reminiscent of behavior 'B' of KEY2, but this time, a third subgoal allows BESD to directly lead the agent towards the goal
Behavior 'B' in KEY3 (Figure 6b): This strategy is more intuitive (indeed, more replications converge to behavior 'B' than behavior 'A') and leads the agent to check each of the possible key locations (the closer one first) and then sends the agent directly toward the goal.
5.6 Baseline Algorithms
Given the somewhat unique positioning of the BESD framework, it is important for us to compare against from several streams of literature. Due to our strong focus on cost-efficiency, non-gradient-basel approaches from the BO literature are particularly relevant. Two of the most common approaches are expected improvement (Močkus, 1975; Jones et al., 1998) and lower confidence bound (LCB) & John, 1992; Srinivas et al., 2010). Expected improvement (EI) allocates one sample in each round, selecting a point that maximizes the expected improvement beyond currently sampled points:
EI(@) E,, [[min ........ .'] t0, Tmax)) +J.
In each iteration, we evaluate the EI selection using Tmax iterations. LCB controls the exploration-exxloitaaioon trade-off using a "bonus term" proportional to the standard deviation at each point:
LCB(0)= (0,, Tmax) R. 1e" ((0, Tmaax) ) (8, Tmuxx))
The parameter x is set to 2. Both EI and LCB are implemented using the GPyOpt package González (2016). As sanity check, we also compare against baseline where the subgoals are randomly selected at each iteration (RND), implemented using Latin hypercube sampling (Stein, 1987).
We also compare against two "default RL" baselines, that do not incorporate an aspect of tuning the exploration strategy. The first baseline is the Q-learning algorithm (QL) (Watkins, 1989) with no subgoals or reward shaping: that is, we directly run QL on environment & for Tmax interactions. The second one is a heuristic based on the approximate Q-values learned by QL, which we call "transfer" Q-learning (TQL): for the test instance, initialize the Q-values using the previously stored results from randomly chosen training
17

---

Published in Transactions on Machine Learning Research (09/2023)
3.5
2.5
Log of regret
Log of regret
3.0
2.0
2.5
1.5
2.0
QL
HB
LCB BESD
1.5
QL
HBB
LCB
1.0
TQL
TQL
EI
BESD
1.0
RND
RND
0.5
0.5
2
6
2
3
4
6
7
Total cost
1e5
Total cost
1e6
(a) GW10 Domain
(b) GW20 Domain
16
2.2
QL
HB
Log of regret
2.1
TQL
E1
BESD
12
Reward
2.0
RND
10
1.9
QL
EL
TQL
LCB
1.8
RND
BESD
1.7
HB
0.0
1.6
0.5
1.0
0.0
0.4
0.6
0.8 1.0 1.2 1.4
1.8
2.0
2.2 1e7
Total cost
1e6
Total cost
(c) TR Domain
(d) MC Domain
2.7
2.7
2.6
Log of regret
2.6
Log of regret
2.5
2.4
2.4
QL
BI
2.3
QL
TOL
LCB
TOL
LCB
2.2
2.3
RND
BESD
RND
BESD
HB
2.1
HB
2.2
2.0
Total cost
1e5
Total cost
1e5
(e) KEY2 Domain
(f) KEY3 Domain
Figure 7: Performance as a function of the total training costs. The curves are averaged over replications of the mela-optimization problem and the error bars indicate standard errors of the mean. Note that the curves associated with the BO methods, BESD, LCB, EI, start later due to the use of set of initial points for initializing the GP model.
environment. This heuristic is inspired by the idea of policy reuse proposed in Fernández et al. (2010) for transferring learned strategies to tasks.
An alternative to applying BO bandit algorithms to hyperparameter optimization is the idea of adoptive configuration evaluation, which focuses on improving the throughput of configuration evaluation by quickly eliminating ones that are not promising. From this line of thinking, the Hyperband algorithm (HB) of al. (2017) stands out as popular and representative approach. trcats hyperparamcter optimization as a pure-exploration infinitearmmdd bandit problem; it uses sophisticated techniques for adaptive resource allocation and early-stopping to concentrate its learning efforts promising designs. Setting 1) = 3 (the
18

---

Published in Transactions on Machine Learning Research (09/2023)
default value) and R. = 81, HB consists of [log, RJ rounds. The first round starts with R samples of subgoal designs 0 from a Latin hypercube sample. Following HB's motivation of early-stopping unpromising designs, each 0 is evaluated for Tmin steps. The best 1/n-fraction designs are kept for the next round. In round i, Hyperband samples R/n"' subgoal designs to evaluate for Tmin 17' stops.
A detailed empirical comparison of BESD to baseline algorithms for all environments are given in Figure 7. The purpose of each numerical experiment is to show that BESD able to, in a cost-efficient manner (where cost is defined the number of environment interactions), produce exploration strategies that lead to policies that perform well in randomly drawn test environment. For each replication, to assess the performance at a particular point in the process, we take its latest recommendation and test it by averaging its performance on a random sample of 200 test MDPs (i.e., )* The x-axis is the cumulative cost, which includes the initial sampling cost. The y-axis is typically the log regret (lower is better), where regret is defined as the number of additional steps needed to reach the goal when compared to the optimal policy. The exception is the TR domain, where the y-axis is the discounted reward (higher better), since in TR, the performance is measured by both reward and steps.
5.7 Takeaways from Baseline Comparisons in Figure
We now offer some observations and takeaways from the performance plots of Figures 7a-7f, where BESD is compared to a variety of baseline approaches. In these figures, the x-axis shows the total cost, defined be the total number of environment interactions, and the y-axis shows the performance measure (either regret or reward, depending on the environment) when averaged across environments drawn from E. In all environments, BESD (in red) achieves either the lowest regret highest reward.
Sanity checks. The methods RND, QL, and TQL tend perform poorly across all domains. This suggests that subgoal-free methods (QL and TQL) are unable to achieve cost-efficient exploration. At the same time, the results of RND suggest that when using subgoals, they must be carefully selected (i.e., exploration based on random subgoals does not perform well).
2. Comparison to Hyperband. HB is reasonably competitive against BESD on two of the easier domains, GW10 and TR. In particular, we notice that HB tends to have good performance early on (as it able to use early stopping to quickly eliminate inferior subgoal strategies). However, as the interaction budget grows, we see that most domaïns, BESD is eventually able to make better use of its evaluations, likely explained by BESD's use of a tailored surrogate model.
3. Comparison to other BO methods. The popular вО methods EI and LCB tend to perform similarly to each other in all domains. Compared to BESD, however, they are less cost-efficient. Since all three approaches make use of underlying GP surrogate models, but EI and LCB are constrained in always using fmax interactions, this is evidence that being able to reduce the episode lengths and the number of replications is valuable.
4. Impact of more subgoals. Lastly, we point out that Figures 7e and 7f show that although a two-subgoal exploration strategy achieves better results than the baselines, a three-subgou bgoal strategy performs even better. This demonstrates the benefit of expanding the dimension of the parameterization in certain environments. Choosing the number subgoals to use in a particular sot of environments is not an exact science; in general, higher dimensional subgoal parameterization makes the BO meta-optimization problem more challenging and each acquisition function optimization is also more dine-consuming We recommend the following guidelines: (1) Consider the total interaction budget across all training iterations. A rulc-of-thumb is that a d-dimensional subgoal parameterizatio ion should have 2d - random initial points. The interaction cost. of the initial points should be less than 1/3 of the total budget in order to give BESD adequate time to make progress (if the cost of initial points is too high, then one might want to reduce d). (2) Optimizing the acquisition function becomes more time consuming as increases, so d should be small enough such that (7) can be computed in one's allotted per-iteration time budget for acquisition function optimization.
19

---

Published in Transactions on Machine Learning Research (09/2023)
5.8 Dynamic Subgoal Exploration Strategy vs. Learning From Scratch at Test Time
In Section 5, Figures 4, 5, and 6 gave visual intuition about the types of exploration behaviors that were discovered by BESD, In this section, we show how the final dynamic subgoal strategy 0 recommended by BESD is able to speed up learning in the test environment, by comparing it to "learning from scratch" (i.c., running RL directly in the sparse reward environment, with no subgoals). Let
RL-ALLG Mc] and "E, ON = RL-ALGO [T, MM, oN.
be the policy learned using RL-ALGO on the original, sparsc-reward environment (i.c., no subgoals) and the policy learned by RL-ALGO with the aid of the subgoal strategy found by BESD after T test-time interactions. The performance ratio that we are interested in is
performance ratio(T) B. B.V" E. (80) IE [V[ (so)];
which, stated simply, represents the ratio "performance with subgoals performance without subgoals." On GW10, GW20, MC, KEY2, and KEY3, a smaller performance ratio indicates a more effective exploration strategy. For TR, we mcasure performance using rewards instead of costs, so a larger performance ratio is better. Table displays the performance ratios as a function of the number of interactions used in the test environment. We can see that an optimized exploration strategy corresponds to dramatic improvements, ranging from roughly 3x in the worst cases (MC, KEY2, and KEY3) to nearly 20x in the best cases (GW10, GW20, and TR). Note that due to the varying difficulty between environments, we use a scaling factor to show how the performance improves with additional cost. The takeaway here is that using a good exploration strategy can lead to dramatic improvements at test-time.
Table 1: Performance ratios as function of interactions in the test environment. GW10, GW20 TR, MC, KEY2, and KEY3 are evaluated every m = 100, 1000, 200, 1000, 500, 500 steps respectively.
T
GW10
GW20
TR
MC
KEY2
KEY3
m
0.458
0.779
0.436
0.980
1.456
1.025
2m
0.218
0.492
2.823
1.048
0.736
0.940
3m
0.086
0.234
2.823
0.949
1.277
0.698
4m
0.080
0.224
0.917
0.896
0.704
0.788
5m
0.070
0.108
6.723
0.987
1.355
0.531
6m
0.086
0.088
8.939
0.878
0.856
0.503
7m
0.080
0.068
9.908
1.077
0.920
0.623
8m
0.087
0.075
10.216
0.877
0.883
0.532
9m
0.069
0.059
23.2936
0.512
0.232
0.566
10m
0.069
0.058
18.011
0.354
0.332
0.361
6 Conclusion and Future Work
The problem of finding exploration strategies for a distribution of environments with a strong focus on cost-awareness during training has not been adequately studied in the literature. This can be deterrent to applying RL in real-world settings where interactions with the environment are limited and expensive (and where cheap simulators
not available). This paper proposes solution based on Bayesian optimization; in a cost-aware manner, approach finds subgoals with an intrinsic shaped reward that aids the agent in scenarios with sparse and delayed rewards, thereby reducing the number of interactions needed to obtain good solution. We hope that this approach can help RL become more applicable in real world seltings. An experimental evaluation demonstrates that BESD achieves considerably better solutions than a comprehensive field of bascline methods on a varioty of benchmark problems. Morcover, an examination of its "recommendation paths" shows that BESD discovers solutions that induce interesting exploration strategies. There are several exciting directions for extending this paper:
20

---

Published in Transactions on Machine Learning Research (09/2023)
Richer BO formulations. Extensions to the BO formulation could be made in various ways. For example, one interesting direction is to allow the acquisition function to determine the number of subgoals as an additional lever. Based on a few informal observations, such a formulation is likely only intercsting in scttings where more subgoals incur additional experimentation cost. Alternatively, the acquisition function itself could be extended with additional features, such as encouraging successive subgoal evaluations to be nearby previous ones (i.e., reduce sctup cost) or the ability reason about (known) symmetries in the domain. Such advanced features might be enabled by dynamic programming formulations of the BO problem itself, which be tackled using multi-step lookahead BO (Lam et al., 2016; González et al., 2016; Jiang et al., 2020; Lee et al., 2020). Other possiblities include the ability to handle expensive-to-evaluse constraints (Gardner et al., 2014; Gelbart et al., 2014; Letham et al., 2019) or lotal cost. budgets (Astudillo et al., 2021; Lee et al., 2021).
Case study in application domain. Our experiments gave proof-of-concept results benchmarks where the RI training itself did not use prohibitive amounts of computation, in order for us to stay within a reasonable computational budget. This is because statistically distinguishable results for baseline algorithms require many replications of the meta-optimization problem (i.e., the BO routines), each of which require many iterations of RL training. One immediate area of future work to "productionize" the dynamic subgoal exploration strategies real-world application involving a navigation task.
The task-aware setting. Finally, our problem formulation does not include "labels" for environ- ments, as our sctting is concerned with case of exogenous variation in the environments, but otherwise the same task. The situation often sduded in the multi-task RT. setting, however, often comes with task identifiers, where the agent knows that is operating in particular task. An extension to this setting might be useful for certain applications, where exploration strategies that are good for one task (e.g., biking through an environment) are also useful for other tasks (e.g., walking through the same environment).
We small number of informal experiments where we allowed BO to select the number of subgoals, but found that BESD almost immediately gravitates the largest number subgoals (as subgoals come cost). Since in the applications that have mind, subgoal cost was not primary concern, did not pursue this direction did not bring any particularly strong insights for the standard case.
21

---

Published in Transactions on Machine Learning Research (09/2023)
References
Joshua Achiam and Shankar Sastry. Surprise-based based intrinsic motivation for deep reinforcement learning. In International Conference on Learning Representations, 2017.
Susan Amin, Maziar Gomrokchi, Harsh Satija, Herke van Hoof, and Doina Precup. A survoy of exploration methods in reinforcement learning. arXiv preprint arXiv:2109. 00157, 2021.
Dimitrios S Apostolopoulos, Liam Pedersen, Benjamin N Shamah, Kimberly Shilleutt, Michael D Wagner, and William L Whittaker. Robotic antarctic meteorite search: Outcomes, In International Conference Robotics and Automation, volume 4, pp. 4174 4179. IEEE, 2001.
Raul Astudillo, Daniel Jiang, Maximilian Balandat, Eytan Bakshy, and Peter Frazier. Multi-stop budgeted Bayesian optimization with unknown evaluation costs. Advances in Neural Information Processing Systems, 34, 2021.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13(1-2):41-77, 2003.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471 1479, 2016.
Jonathan Binney, Andreas Krause, and Gaurav S Sukhatme. Optimizing waypoints for monitoring spatiotem- poral phenomena. The International Journal of Robotics Research, 32(8):873 878-8887 2013.
Mickaël Binois, Jiangeng Huang, Robert B Gramacy, and Mike Ludkovski. Replication or exploration? sequential design for stochastic simulation experiments. Technometrics, (1(:777233 2019.
Eric Brochu, Vlad M Cora, and Nando De Freitas, A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning, arXiv preprint 1012v 2599, 2010.
Scott Clark, Eric Liu, Peter Frazier, JiaLei Wang, Deniz Oktay, and Norases Vesdapunt. Moe: A global, black box optimization engine for real world metric optimization. https:/ //1 thub. com//elp//EEEE 2014.
Dennis D Cox and Susan John. A statistical method for global optimization. In International Conference on Systems, Man, and Cybernetics, pp. 1241 1246. IEEE, 1992.
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. Advances in Neural Information Processing Systems, 5, 1992.
Mare Peter Deisenroth, Peter Englert, Jan Peters, and Dieter Fox. Multi-lask policy search for robotics. In International Conference on Robotics and Automation, 2014.
Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In International Joint Conferences on Artificial Intelligence, volume 15, pp. 3460-8, 2015.
Finale Doshi-Velez and George Konidaris. Hidden parameter Markov decision processes: A semiparametric regression approach for discovering latent task parametrivations. In International Joint Conferences on Artificial Intelligence, 1432. NIH Public Access, 2016.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloezek. Scalable global optimization via local Bayesian optimization. Advances in Neural Information Processing Systems, pp. 5497-5508, 2019.
22

---

Published in Transactions on Machine Learning Research (09/2023)
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pp. 1407 1416. PMLR, 2018.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2018.
David Ferguson, Aaron Morris, Dirk Hachnel, Christopher Baker, Zachary Omohundro, Carlos Reverte, Scott Thayer, Charles Whittaker, William Whittaker, Wolfram Burgard, et al. An autonomous robotic system for mapping abandoned mines. In Advances in Newral Information Processing Systems, pp. 587 594, 2004.
Fernando Fernández, Javier García, and Manuela Veloso. Probabilistie policy reuse for inter-task transfer learning. Robotics and Autonomous Systems, 58(7):866- 1866-871, 2010.
Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Initializing Bayesian hyperparameter opti- mization via meta-learning. In Association for the Advancement of Artificial Intelligence, pp. 1128-1135, 2015.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pp. 1126 1135. JMLR. org, 2017a.
Chelsea Finn, Tianhe Yu, Tianhao Zhang, Pieter Abbeel, and Sergey Levine. One-shot visual imitation learning via meta-nearning. In Conference on Robot Learning, pp. 357-368, 2017b.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In International Conference on Learning Representations, 2018.
Peter Frazier, Warren Powell, and Savas Dayaník. The knowledge-gradient policy for correlated normal beliefs. INFORMS Journal on Compuling, 21 (4):599 613, 2009.
Peter I Frazier. A lutorial on Bayesian oplimization. arXiv preprial arXiv:1807.0281 2018.
Peter I Frazier, Warren B Powell, and Savas Dayanik. A knowledge-gradiin policy for sequential information collection. SIAM Journal on Control and Optimization, 27(5):2410-22) 2-39,, 2008.
Javier Garcia-Barcos and Ruben Martinez-Cantin. Robust policy search for robot navigation. JEEE Robotics and Automation Letters, 6(2):2389 2396, 2021.
Jacob Gardner, Matt Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunningham. Bayesian optimization with inequality constraints. In International Conference on Machine Learning, volume 2014, pp. 937 945, 2014.
Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023.
Michael A Gelbart, Jasper Snoek, and Ryan P Adams. Bayesian optimization with unknown constraints. arXiv preprint ar Xiv: T4::440955000 2014.
Subhashis Ghosal, Anindya Roy, et al. Posterior consistency of Gaussian process prior for nonparametric binary regression. The Annals of Statistics, 34(5):2413 2429, 2006.
Sandeep Goel and Manfred Huber. Subgoal discovery for hierarchical reinforcement learning using learned policies. In FLAIRS Conference, pp. 350, 2003.
González, GPyOpt: Bayesian optimization framework Python. http://github wtt.ee/o.ooooeeeeeeeee htnm/SheffieldM// GPyOpt, 2016.
Javier González, Michael Osborne, and Neil Lawrence. Glasses: Relieving the myopia of bayesian optimisation. In Artificial Intelligence and Slatistics, pp. 790-799. PMLR, 2016.
23

---

Published in Transactions on Machine Learning Research (09/2023)
Xiaoxiao Guo, Satinder Singh, Richard Lewis, and Honglak Lee. Deep learning for reward design to improve Monte Carlo tree search in ATART games. In International Joinl Conference on Arlificial Intelligence, pp- 1519 1525, 2016.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Picter Abbecl, and Sergey Levine. Mota-rcinforcement learning of structured exploration stralegies. In Advances in Neural Information Processing Systems, pp. 5302-534 5311, 2018.
Henry C Herbol, Weici Hu, Peter Frazier, Paulette Clancy, and Matthias Poloczek. Efficient search of compositional space for hybrid organic inorganic perovskites via Bayesian optimization. NPJ Computational Malerials, 4(1):51, 2018.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with PopArt. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 33, pp. 3796 3803, 2019.
Xiao Huang and John Weng. Novelty and reinforcement learning in the value system of developmental robots. In 2nd International Workshop on Epigenelic Robolics: Modeling Cognilive Development in Robolic Systems. Lund University Cognitive Studies, 2002.
Shali Jiang, Daniel Jiang, Maximilian Balandat, Brian Karrer, Jacob Gardner, and Roman Garnett. Efficient nonmyopic Bayesian optimization via one-shot multi-step trees. Advances in Newral Information Processing Systems, 11118099-10445 2020.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-49) -92, 1998.
Kishor Jothimurugan, Osbert Bastani, and Rajeev Alur. Abstract value iteration for hierarchical reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 1162-1170. PMLR, 2021.
Frédéric Kaplan and Pierre-Yves Oudeyer. Maximizing learning progress: An internal reward system for development. In Embodied Artificial Intelligence, pp. 259-270, Springer, 2004.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2-3)2209 232, 2002.
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian optimization of machine learning hyperparameters on large datasets. In Artificial Intelligence and Statistics, pp. 528-552-5 2017.
George Konidaris and Andrew Barto. Autonomous shaping: Knowledge transfer in reinforcement learning. In International Conference on Machine Learning, pp. 489 496. ACM, 2006.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Sacedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances Newral Information Processing Systems, 29, 2016.
Remi Lam, Karen Willcox, and David H Wolpert. Bayesian optimization with finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29, 2016.
Guillaume Lample and Devendra Singh Chaplot. Playing FPS games with deep reinforcement learning. In Association for the Advancement of Artificial Intelligence, pp. 2140 2146, 2017.
Armin Loderer, Jonas Umlauft, and Sandra. Hirche. Uniform error bounds for Gaussian process regression with application to safe control. In Advonces in Neural Information Processing Systems, pp. 657 667, 2019.
Eric Lee, David Eriksson, David Bindel, Bolong Cheng, and Mike Mccourt. Efficient rollout strategies for Bayesian optimization. In Conference on Uncertainty in Artificial Intelligence, pp. 260 269. PMI.R, 2020.
24

---

Published in Transactions on Machine Learning Research (09/2023)
Eric Hans Lee, David Eriksson, Valerio Perrone, and Matthias Seeger. A nonmyopic approach to cost- constrained bayesian optimization. In Uncertainty in Artificial Intelligence, pp. 968-577. PMTR, 2021.
Benjamin Letham, Brian Karrer, Guilherme Outoni, and Eytan Bakshy, Constrained Bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):495-54) 519, 2019.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In International Conference on Learning Representations, 2018.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1): 6765 6816, 2017.
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In International Conference on Machine Leurning, pp. 71, 2004.
Ruben Martinez- Cantin, Nando de Freitas, Arnaud Doucet, and José A Castellanos. Active policy learning for robot planning and exploration under uncertainty. In Robotics: Science and systems, volume 3, pp. 321-328, 2007.
Ruben Canlin, Nando De Freitas, Eric Brochu, José Castellanos, and Arnaud Doucet. A Bayesian exploration-exploitaaio approach for optimal online sensing and planning with a visually guided mobile robot. Autonomous Robots, 27:93 103, 2009.
Larry Matthies, Erann Gat, Reid Harrison, Brian Wilcox, Richard Volpe, and Todd Litwin. Mars microrover navigation: Performance evaluation and onhancement. Autonomous Robots, 244) 1995.
Amy McGovern and Andrew G Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In International Conference on Machine Learning, 2001.
Viraj Mchta, Biswajit Paria, Jeff Schneider, Stefano Ermon, and Willic Neiswanger. An experimental design perspective model-based reinforcement learning. In International Conference Learning Representations, 2021.
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference, pp. 400-404 Springer, 1975.
Philippe Morere and Fabio Ramos. Bayesian RL for goal-only rewards. In Conference on Robot Learning, 2018.
Mojmir Mutny and Andreas Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature fourier features. Advances in Neural Information Processing Systems, 31, 2018
Ofrr Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018
Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for Bayesian optimization in embedded subspaces. In International Conference on Machine Learning, pp. 4752-4761, 2019.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning, volume 99, pp. 278 287, 1999.
Rafael Oliveira, Lionel Ott, Vitor Guizilini, and Fabio Ramos. Bayesian optimisation for safe navigation under localisation uncertainty. In Robotics Research, pp. 489-504. Springer, 2020.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pp.
JMLR. org, 2017.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference Machine Learning, pp. 2377-2327 2016.
25

---

Published in Transactions on Machine Learning Research (09/2023)
Xinlei Pan, Eshed Ohn-Bar, Nicholas Rhinchart, Yan Xu, Yilin Shen, and Kris M Kitani. Human-interactinn subgoal supervision for elficient inverse reinforcement learning. arXiv preprinl or 1ix: 08479, 2018.
Leonard Papenmeier, Luigi Nardi, and Matthias Poloczek. Increasing the scope as you learn: Adaptive Bayesian optimization in nested subspaces. Advances in Neural Information Processing Systems, 35: 11586 11601, 2022.
Leonard Papenmeier, Luigi Nardi, and Matthias Poloczek. Bounce: a reliable bayesian optimization algorithm for combinatorial and mixed spaces. Xiv preprint arXiv:2307.00618, 2023.
Shubham Pateria, Budhitama Subagdja, Ah-hwee Tan, and Chai Quck. Hicrarchical reinforcement learning: A comprehensive survey, ACM Compuling Surveys (CSUR), 54(5):1 35, 2021.
Deepak Pathak, Pulkit Agrawal, Alexci A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Leurning, volume 2017, 2017.
Sujoy Paul, Jeroen Baar, and Amit K Roy-Chowdhury. Learning from trajectorics via subgoal discovery. arviv preprinl ar Xiv: (tt:191107222) 1.07224, 2019.
Victor Picheny and David Ginsbourger. nonstationary space-time Gaussian process model for partially converged simulations. STAM/ASA Journal on Uncertainly Quantifteation, 1(1):57-78, 2013.
Mare Pickett and Andrew G Barto. Policyblocks: An algorithm for creating useful macro-actions reinforcement learning. In International Conference on Machine Learning, volume 19, pp. 506-513, 2002.
Lerrel Pinto and Abhinav Gupta, Learning to push by grasping: Using multiple tasks for effective learning. In 2017 IEFE international conference on robotics and automation (ICRA), pp. 2161-2168. TEEE, 2017.
Matthias Poloczek, Jialei Wang, and Peter Frazier. Multi-information source optimization. In Advances in Neural Information Processing Systems, pp. 4288-4298, 2017.
Doina Precup, Richard S Sutton, and Satinder Singh. Theoretical results on reinforcement learning with temporally abstract options. In European conference machine learning, pp. 382-393. Springer, 1998.
Jette Randlov and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In International Conference on Machine Learning, volume 98, pp. 463-471. Citeseer, 1998.
Carl Edward Rasmussen and Christopher K.I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. ISBN 0-262-18253-X.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling, Mathematics of Operations Research, 39(4):1221-1244) 2014.
Warren Scott, Peter Frazier, and Warren Powell. The correlated knowledge gradient for simulation optimization of continuous parameters using Gaussian process regression. STAM Journal on Optimization, 23(3)-996-100 2011.
Pranav Shyam, Wojeiech Jaskowski, and Fanstino Gomez. Model-based active exploration. In International Conference on Machine Learning, pp. 5779 5788. PMLR, 2019.
Özgür Şimşek and Andrew G Barto. Using relative novelty to identify useful temporal abstractions in reinforcement learning. In International Conference on Machine Learning, pp. 95, 2004.
Özgür Şimşek and Andrew G Barto. An intrinsic reward mechanism for efficient exploration. In International Conference on Machine Learning, pp. 833 840, 2006.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In International Conference on Machine Learning, pp. 816 823, 2005.
Jasper Snock, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems, pp. 1951-2959, 2012.
26

---

Published in Transactions on Machine Learning Research (09/2023)
Jonathan Sorg, Richard L Lewis, and Satinder P Singh. Reward design via online gradient ascent. In Advances in Newral Information Processing Systems, pp. 2190-2198, 2010.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization the bandit setting: No regret and experimental design. In International Conference on Machine Learning, pp. 1015-1022, 2010.
Bradly C Stadic, Sergey Levine, and Picter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. orXi preprint arXiv:1507.0081, 2015.
Michael Stein. Large sample properties of simulations using latin hypercube sampling, Technometrics, 29(2): 143-151, 1987.
Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and opprozimation, pp. 212 223. Springer, 2002.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-211 1111 1999.
Kevin Swersky, Jasper Snoek, and Ryan P Adams. Multi-task Bayesian optimization. Aduances in Neural Information Processing Systems, pp. 2004 2012, 2013.
Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Freeze-thaw Bayesian optimization. arXiv preprint arXiv:1406.3880 2014.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2753-2762, 2762, 2017.
Ana C. Tonorie- Eduardo F Morales, and Luis Villasetor-Pineda. Dynamic reward shaping: Training a robot by voice. In American Conference on Artificial Intelligence, pp. 483 492. Springer, 2010.
Matthew Tesch, Jeff Schneider, and Howie Choset. Adapting control policies for expensive systems to changing environments. In 2011 IEEE/RSJ International Conference on Intelligent Robols and Systems, pp. 357 364.
IEEE, 2011.
Sebastian Thrun, Scott Thayer, William Whittaker, Christopher Baker, Wolfram Burgard, David Ferguson, Dirk Hahnel, D) Montemerlo, Aaron Morris, Zachary Omohundro, et al. Autonomous exploration and mapping of abandoned mines. Robotics & Automation Magazine, 11(4):79 91, 2004.
Vivek Veeriah, Tom Zahavy, Matteo Hessel, Zhongwen Xu, Junhyuk Oh, lurii Kemaev, Hado van Hasselt, David Silver, and Satinder Singh. Discovery of options via meta-learned subgoals. Advonces in Neural Information Processing Systems, 34, 2021.
Alexander Vezhnevets, Volodymyr Mnih, Simon Osindero, Alex Graves, Oriol Vinyals, John Agapiou, et al. Strategic attentive writer for learning macro-actions. Advances in Neural Information Processing Systems, 29, 2016.
Nelson Vithayathil Varghese and Qusay H Mahmoud. A survey of multi-task deep reinforcement learning. Electronics, 99)::1363, 2020.
Ziyu Wang. Frank Hutter, Masrour Zoghi, David Matheson, and Nando de Feitas. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 15:361-387, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-25)) 292, 1992.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
27

---

Published in Transactions on Machine Learning Research (09/2023)
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: A hierarchical Bayesian approach. In International Conference on Machine Learning, pp- 1015-1022. ACM, 2007.
Jian Wu and Peter Frazier. The parallel knowledge gradient method for batch bayesian optimization. Advances in Neural Information Processing Systems, 29, 2016.
Jian Wu, Matthias Poloczek, Andrew G Wilson, and Peter Frazier. Bayesian optimization with gradients. Advances in Neurul Information Processing Systems, pp. 5267-5278, 2017.
Jesse Zhang, Haonan Yu, and Wei Xu. Hierarchical reinforcement learning by discovering intrinsic options. In International Conference on Learning Represenlations, 2020.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. In A Adancces in Newral Information Processing Systems, pp. 4649-4665 6649-4659, 2018.
28

---

Published in Transactions on Machine Learning Research (09/2023)
A Proofs
A.1 Restatement of Theorems
Here we restate the two main theorems from the paper for the reader's convenience. Full proofs are provided in the following sections.
Theorem The acquisition function described in (7) has the property of asymptotic optimality with respect to 6, L..,,
lim f(0 Tmaz) max f(0, Tmaa),
N
BE8
almost surely. That is, the recommended design 8N becomes optimal as N + 00.
Theorem The acquisition function of (?) has bounded asymptotic suboptimality with respect to the original domain @ in the sense that with probability at least 1 8, it holds that
lim f( Tmax)) 2 maxage f(0, Tmax) d. ||
where d = maxsee mingre dis 0¹) is a measure on the "coarseness" of the discretization and Ls is the vector (L3, ......,. ) with each L3 defined as in (8).
A.2 Proof of Theorem 1
The proof is based on theoretical results of Poloczek et al. (2017). Our result, however, includes the ability to select the number of replications q. Denote X(0, T, q) = de + 2.p//. Also, let f denote the o-algebra
generated by the history H The expectation E,, == EP[ [ is taken with respect "" Recall that n² and kn are the mean and covariance matrix of the time n belief on Define the quantities
(0,7( (0,
z
Var Tarlyn+11 ((, - (0,T) F
and
kn ("(('T''), (0, +))
= V \10, T, km ((0, (0,T))
Observe that z is standard normal (conditional on g²). We have the following recursive updating equation for t+1
1 (0")))="0001 (0, - ((0,T), (0 ,atl)) (
zut1,
(9)
and another recursive formula 1n+1;
h T'), (0, ()) = ktah ((0', 7'), (0, T))
(10)
G (10', r'), (g=+1, r(t [ ((0, r), ( ,(t
These updating equations are based on the Shernan-Woodbury identity; see Frazier et al. (2009) for full derivation. The objective of the acquisition function thus:
nd (0, 4)
1
gr En [( p.)) (0", ,,",,"" """ (0, T)
qT
En (0" ;maa) + 0% ((0', Tmax)) : (0, z
(11)
qr
max p. (0) F (0","",0") (0, (0.
We also define the quantity
V" 7, 0', E, (0',+') = ((0,)), n¹" (0,7) (0')))
(12)
Next, restate useful technical lemma from Poloczek et al. (2017).
29

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma 1 (Restatement of Lemma of (Poloczek et al., 2017)) Let T E T and 0,0' O. The limils of the series ()) and (V* 7,0', ,')Jn exist. Denote them by 1² (0,7) and V (0, (0,7,0',7) respectively. We have
lim μ² (0, =0000000 n-000
(13)
lim (",0,,,0',7) (0,,7,00))
(14)
almost surely. If (0,,") is sampled infinitely oflen, then
lim -100,,,,,,))~100000000 1 (0',
D 2=000
Fix sample path w, which corresponds to particular path of measurements and observations
{(0", T" .², y (""",,",""))))
By the finiteness of θ T, and Q, there must exist a configuration (0',''g') that is visited infinitely often on sample path w. The following lemma states the asymptotic behavior of 1/ ( ('d')((('T)) for n + co as a function of (:,-) and ,. (s-)).
Lemma 2 Consider the sample path w and (0','', .'d') described above. Then, on that sample path w, it holds thot.
lim o. ((8", Tmax); (f', ,')) =0 n-000
for every 8" e. Also, the acquisition value tends to zero: limn v" v"( -' +'
Proof. It follows from Lemma that
kt ((0, T), (8', ,')) BnIf((,T) -(00,)))""000-)) ( (8', n000 0
for any 0 O, T. Then for all 0" O, we have
1thh ((0", Tmaxx (0',
lim o ((0", mm (0', (0)) lim 2-000
0.
n-000
AA +' + km (10,, T'), (0', (')
Note that we made use of the fact that the observation noise A00', -','' > for any q'. From the proof of Lemma 1 of Poloczek et al. (2017), it shown that for any 8" E E
(0" )maa)) and {Ø ((0", Tmax), (0', r'))],
are uniformly integrable (u.i.) families of random variables that converge almost surely to their respective limits (B", mmax) and 0z ((0", Tmax), (0', 0. Note that the family of random variables {Øz ((8", -mmxa) (f','',) r)))) zu+i), is also uniformly integrable since z is independent of og ((0", Tiaa), (0','") Let Z be a standard normal random variable (independent from all other quantities).
It holds that
nd (0' (8',''s r')'))
lim 100000
G'T'
+.00
Tm (0',')) 2 dz ((Z) max {u 1 Fimax) + ((8", Tiax)), arEe
(15)
G'r'
l 00 (0", Tmax))
max 0"
0.
The first equality is due (11) and the fact that the operations of summing and taking maximum over a finite set of uniform integrable random variables maintains uniform integrability.
30

---

Published in Transactions on Machine Learning Research (09/2023)
From (7), we know that in each iteration n, the configuration (0","",9") is selected from according to arg ma, (O, g)/(4)). Now, for the sake of contradiction, suppose that there exists some configuration (0,7. such that lim (0, F, ()/(tF) 0. This immediately leads contradiction, since then it cannot be the case that ('") is visited infinitely often.
Since the sample path w was arbitrary, we conclude that
lim v" ((,,T,)/((T)) =0 a.s.
(16)
for all 0 θ, T TT, and q E Q.
Lemma 3 Given that (16) holds, we have that
arg max 10 (0, Tmaz) = arg max f(0, Tmax)
868
almost surely.
Proof. We can conclude from (12) and Lemma 1 that
lim kin ((0, Tmax); (0, Tmax)) = 2:20 ((0, T, (0, Tmax)) a.8. 12+20
for all O. the case that the posterior variance k: ((0, Tmax)), (0, Fimax)) = 0 for all A E O then the maximizer known perfectly and we are done.
If not, then we define é {0 E | ((0, Tmax); (0, [max)) 0} and consider some 0 E θ where the posterior variance is positive. Fix any E Q. We now argue that
: ((0, Tmax); (0, Fiaa)) = q ((0", Tmax); (0, Tmaa))
(17)
for all H" O. Suppose, for the sake of contradiction, that there cxist some 0 02 2 with tे (101, m,ax), ) (0, Tmax)) + 0 ((02, Tiax),, (0, mmax))
(18)
Recall (15) and note that it be rewritten
lim 13000
B[M(Z)] G'T'
mmx "00 (max))a 0"E@
(19)
G't'
where h(2) = max (0", (0", Tmax) + # ((0", Tmax)), ), (')) 2). Since θ is finite and each function within the maximization in h is affine in 2, the h(2) is convex" and piecewise linear. Since h is convex, there is an affine function such that
10) = h(0), ((x) S h(2) for all IR.
The assumption made in (18), which effectively says that h is created by taking maximum over affine functions of differing slopes, implies cannot itself be affine (and indeed, must consist of various "pieces"). Therefore, there exists an interval I, either of the form (20, (0) or (-o0, 20), such that I(2) < h(z) for a E I. It follows that E[((Z)] < [[]. By the linearity of I, we have
[[) 1(T Z I(0) = h()) = max - (0" Tmmxx) < E [T()]]
0"E8
This implics that (19) is strictly positive, contradicting (16). We thus conclude that (17) holds, which is equivalent to
0 (10", Tmax), ), (0, Tmax))
c:20 ((0") Tmax)) > (0, Tmax))
1 Tmax: ① + 1:00 ((0, Tmax); ) (0, Timax))
v 1(0 Tiaxx ②) + 1:00 ((O, Timax) (0, Tinax))
Poinntwis maximum of convex functions convex.
31

---

Published in Transactions on Machine Learning Research (09/2023)
for all 0", 8" E O. Moreover, since was chosen from θ we know that
2(0, Tmax: 9) + h: ((0, Tmax), (0, Fmaxx) 0,
and hence x ((0") Tmaax), (6, fmax)) = w000 ((0", Tmaa)), , (6, rmaxx) for all 0" 8 E
This means the covariance matrix of {f(0, Tmaxx 10 θ} is proportional to the all-ones trix, and that draws from [(0, Tmax) (0, Tmax) are constant across 0 E Ô. Therefore, arg m p(x) Tmax) = arg m f(0, Tmax) and the statement of the theorem holds.
A.3 Proof of Theorem 2
In Theorem 2, we establish an additive bound on the loss of the solution obtained by BESD, f(0, Tmax), with respect to the unknown optimum f(0PPT, Tmax), as the number of iterations N + co. Recall that we suppose p(0, r) = for all 0, and that the kernel k(:;-) has continuous partial derivatives up to the fourth order. According to Theorem 3.2 of Lederer et al. (2019), for any ò E (0, 1], with probability at least 1 6, the quantity
|6 [[(L], L3 lX'I
is a Lipschitz constant of f on O i.e, it holds that (8, Tmax) - f(0', Tmax)) < |s||| dist(0, (')
where 0,0' O. By the definition of d, there exists E θ such that dist OOPT) S d. Therefore, it follows that the suboptimality due to optimizing in θ is bounded by
f(gOPT Tmaxx f(0, Tiaax) S || d.
(20)
Theorem 1 completes the proof of Theorem 2 since (0 holds with probability 1-5. 5.
B GP Hyperparameter Estimation
The hyperparameters of the covariance function & are set via marimun posteriori (MAP) estimation. Recall that MAP estimate is the mode under the log-posterior obtained as the sum of the log-marginal likelihood of the observations and the logarithm of the probability under hyper-prior. We focus on describing the hyper-prior, since the log-marginal likelihood follows canonically; see (Rasmussen & Williams, 2006, Ch. 5) for details. The proposed prior extends the hyper-prior for the multi-task GP model used in Poloczek et al. (2017). We set the mean function fu and the noise function to constants that we estimate. For the covariance function we need to estimate d + hyperparameters: the signal variance, one length scale for every subgoal parameter in 0 and the four parameters associated with k,. We suppose normal prior for these parameters. For the signal variance, the prior mean is given by the variance of the observations, after subtracting the above estimate for the observational noise. Here we use the independence of observational noise that we argued in Section 3.5. For any length scale, we set the prior mean to the size the interval that the associated parameter is chosen in. Having determined a prior mean pv for each hyperparameter tú, we may then set the variance of the normal prior to o = (2w/2)²
32


Reviews:
[{"review_id": "smzrOczIh6", "reviewer": "Reviewer_k6VU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Paper is well-written, the algorithm is simple to understand. \n* Related work section is exhaustive and clearly describes relevant prior work.\n* Section 3 (Problem formulation) is particularly useful and sets up the task setup that is considered in their method and experiments.\n* The different subgoal trajectories selected by their approach are presented in Figure 4, adding more clarity in how the agent operates.\n* Empirical section compares the proposed method against a number of baselines\n\nWeaknesses:\n* The domains in the experiments seem to be limited; only 2 or 3 goal selections are necessary in these domains.\n* The experiments do not seem to make a fair comparison with MAML. In page 13, it is mentioned that the batch size in outer-loop is set to 1. This seems like a severe limitation. What happens to the experiments if MAML was used with a reasonable choice of hyperparameters (perhaps as defined in its paper)?\n* Another simple approach could be a hierarchical RL approach where the higher level selects goals and the lower level selects actions conditioned on the goal and current state. The experiments could be more insightful if it included such a simple baseline.\n* A discussion on how the presented approach can be scaled up to much more complex environments (with potentially 1000s of goals) is missing.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of policy optimization in environments where interacting with the environment is expensive, thus only allowing for a limited number of interactions. The experiments in the paper considers an agent that faces a distribution of tasks, experienced through a number of training environments. The agent from its training environments must learn an exploration strategy so that when it encounters a new environment, it can use this strategy to improve its performance and learning. The paper presents a cost-aware Bayesian optimization approach to search over  a class of subgoal-based exploration strategies. The experiments show that the proposed algorithm relatively improves existing meta-learning algorithms like MAML and Hyperband. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* To strengthen the contribution, it would be useful to see how the approach scales when there are more than 2-3 goals in the domain, along with comparisons with relevant baselines.\n* Also adding a discussion on how the approach can scale to much more complex domains will be particularly useful to the community.\n* Another direction could be to improve the baselines: compare against MAML with its optimal hyperparameters and also include simpler non-Bayesian hierarchical RL baselines that seem natural for the tasks considered.\n* Finally, it would also be interesting to compare against the different trajectories generated by the baselines in one of the tasks.\n", "broader_impact_concerns": "A broader impact statement was not available.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Yu3IzrDVj", "reviewer": "Reviewer_LUqN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The paper addresses a relevant and important problem, which has been underexplored in the literature: cost-efficient exploration strategies for RL environments with expensive interactions and sparse rewards.\n2. The proposed BESD algorithm is well-motivated and grounded. The manuscript does an excellent job at describing it, using the right level of formalism as well as being clear in design choices for all of its components. Well done!\n3. The experimental evaluation is comprehensive wrt. the chosen testbeds, providing a clear comparison between the proposed method and existing baseline approaches.\n4. Overall, the paper is well-written and structured, making it easy to understand the proposed method and its contributions.\n\n### Weaknesses\n\n1. The experiments are mainly limited to grid world environments, raising questions about the method's performance in more complex or real-world settings.\n2. It feels like the manuscript is trying to argue that BESD is a generic method for discovering efficient exploration \"policies\", however to me it seems fairly clear that it might be limited to environments where (a) it is possible to define state based goals, (b) it is possible to define a potential function for each subgoal. The manuscript sometimes tries to clarify that this method is really targeted at navigation tasks (which makes a lot of sense -- it is well suited to them!), but overall it feels like it's a bit of a misdirection that is not very warranted.\n3. The problem formulation presented in this paper bears some resemblance to options learning. One might easily summarize the method as effectively learning a set of environment-distribution specific options, using BO.\n4. The authors argue that BESD is superior to \"standard\" intrinsic exploration RL methods because it considers the cost of exploration. However, it is important to note that the cost of exploration is often marginalized away when the exploration strategy is trained alongside the learned policy in intrinsic exploration methods.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript presents a \"cost-efficient\" framework for learning dynamic subgoal exploration strategies in reinforcement learning environments characterized by sparse rewards and expensive interactions. The authors leverage Bayesian optimization to develop the Bayesian Exploratory Subgoal Design (BESD) algorithm, which learns a set of useful subgoals for a distribution of environments under a couple of constraints. The proposed approach is thoroughly evaluated on various grid worlds against a meta-learning baseline and a few BO algorithms.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I would appreciate a tightening of scope of the manuscript to either (1) be extremely clear that this method is currently relevant primarily to a particular kind navigation domain with very well defined constraints, and/or (2) discuss the limitations of the method wrt. these domain constraints.\n2. It would be beneficial to discuss the differences and connections between the proposed method and options learning in HRL. Are there any unique aspects to the presented method that distinguish it from existing HRL approaches? Addressing this question will help to further clarify the paper's novelty and contributions.\n3. It would be useful to provide a more detailed comparison between BESD and such methods, addressing this point. How does the proposed method handle the cost of exploration differently, and what advantages does this bring? By clarifying these aspects, the authors can better position their work within the context of existing approaches.\n\nBy addressing these additional points, the authors can further strengthen their paper and provide a more comprehensive understanding of the proposed method's advantages and limitations compared to existing approaches in the literature.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QXDLgXvEQR", "reviewer": "Reviewer_1jSM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The question of how subgoals should and can shape the structure of exploratory behavior is interesting.\n- Findings from this research could be potentially impactful---by exemplifying how to improve sample efficiency in large domains with non-Markovian dynamics.\n- The study includes reasonable choices for evaluation domains.\n- The study uses a reasonable number of domains.\n### Weaknesses\n- Presentation of technical concepts makes this paper difficult to follow.\n- Originality of some theoretical results is unclear.\n- The theoretical results have limited significance in the context of this study.\n- Empirical methodology is unclear.\n- Empirical support could be stronger.\n\nFurther comments are provided below.\n\n### General Comments \n\n- Many technical concepts are used before they are defined. I provide a few examples, but there are more in the text.\n  - Introduction: The notion of subgoals should be described before the final paragraph of the introduction.\n  - Section 3.2: artificial reward\n  - Section 3.2: intrinsic reward\n  - Section 4: acquisition function\n  - \"A dynamic subgoal strategy is an ordered set of subgoals (along with associated rewards leading to each subgoal, omitted here for illustrative clarity) that leads the agent on a trajectory where the underlying RL algorithm is more likely to discover the optimal behavior.\"\n    - There is a lot of unpack here, especially early without any additional context in the introduction.\n    - Define a subgoal.\n    - Define a subgoal strategy.\n    - Describe what it means for a subgoal strategy to be \"dynamic\".\n- The related work seems somewhat superficial, and it appears to have been written with the intention of avoiding any potential challenges to the contributions of this paper. I would suggest that the paper could benefit from a more thorough and candid discussion of related work. For instance, the paper claims the work of Gupta et al. 2018 is \"impractical\" without supporting evidence of why.\n- Be careful with overstating your claims. For instance, \"Theta is an arbitrary distribution.\" Certainly this to respect some constraints to remain relevant to your problem setting.\n- Mention where the proofs can be found before stating the formal claims.\n- Several references should be enclosed in parentheses. For example, Page 12: \"Clark et al. (2014)\" should be in parentheses.\n- Colors in your figures need to be bolder.\n- This statement is not true in general: \"For example, in a 20 × 20 gridworld with a sparse reward, the goal is not even reached for the first time by a standard Q-learning agent (let alone find an optimal policy) after 10 million interactions.\"\n- This is vague: \"if properly designed, can direct the agent to explore useful parts of the state space.\" Be specific about what is meant by \"useful\" and \"properly designed.\"\n- Section 3.2: What is a subgoal parameterization?\n- Example 1: I took a while to understand this example, because it references a figure on page 1, when the text is on page 6.\n- It appears that, in the examples you provided, the sequence of subgoals is just as critical, if not more so, than the actual location of the goals. Could you please elaborate on how your method ensures the correct sequencing of these subgoals?\n- \"the dimension of $\\theta$ only needs to scale with the number components of s that pertain to the spatial positioning of the agent.\"\n  - This suggests that the applicability of your contributions apply to only spatial settings. Can you expand on this potential limitation?\n- Section 3.3: It is worth noting how your \"subgoal-augmented MDP\" is a factored MDP.\n- Figure 3a: The colors are very faint.\n- Section 3.4: Does the training budget $\\tau$ include steps over multiple episodes, or is this the maximum length of a single episode?\n- Section 3.4: Referring to a generic RL algorithm is too vague. This needs to be restricted to one that explores in a certain way, no?\n- Equation 4: It is not clear where $i_0$ is used.\n- Section 3.5: The total training cost is not necessarily proportional to $\\tau^n$, since any given episode could take fewer steps.\n- Section 4.1: The performance of the algorithm is assumed to be i.i.d according to the GP prior. However, the performance of subsequent policies benefit from prior experiences. Comment on how the significance of this assumption violation.\n- Equation 7: It is a bit confusing to call this the output of a policy and an action the output of a policy.\n- The theoretical arguments seem to contain missing assumptions, and its proofs are also missing steps that could be helpful to the reader. For example, assumptions made about convexity (Appendix A).\n\n\n### Experiment Comments \n- Differences from the Q-learning baseline quantify the degree to which subgoals are useful. It may help to call this this baseline \"No Subgoals\".\n- The Transfer Q-learning is initialized with experience from one randomly selected training environment.\n  - I understand that this was meant to be a random baseline. However, unlike the other baselines, it does not benefit from experience gained in multiple environment instances. I believe that it would be beneficial to include another baseline that employs experience from multiple randomly selected environments, essentially training sequentially on a random sequence of environments. This baseline is expected to perform worse than your proposed method, assuming that the learned subgoal sequences are useful.- Performance differences from the adaptive configuration baseline are unclear.\n- I have the impression that the MAML baseline is somewhat of a straw man comparison, given that Bayesian Optimization is typically utilized in scenarios where gradients are unavailable. Indeed, the outcomes indicate that MAML underperforms the proposed method, though its performance has not always flatlined. Nevertheless, I do not believe you need to compare with MAML to prove your point. In fact, applying MAML to the subgoal learning problem seems to be a topic that warrants a distinct line of inquiry.\n- \" in order to bypass the wall,\" \n  - I believe that it may be inaccurate to assert that the algorithm produced this output for a specific reason. It is more appropriate to say that this was the best possible output under the given constraints and information.\n- Section 5.2.1: I think the take away here is generally correct: When structuring the exploration strategy with a sequence of two subgoals, the subgoals appear to be located in places one would expect. However, I think this point could be made more clearly with cleaner figures and some supporting text.\n- Section 5.4.1: It is unclear what Behavior B is intended to illustrate. This seems to be a negative result.\n- Section 5.5: This feels like an environment that could have benefited from more than two subgoals. It would be compelling if you were able to show an oscillatory pattern in the direction the subgoals take the agent.\n- In this section, the paper first presents several baselines before evaluating the qualitative aspect of a single method (BESD). To enhance readability, it may be helpful to postpone the introduction of these baselines until Section 5.7. Another option could be to split this section up by each experiment rather than by the evaluation domain.\n- Figure 7: The plots presented do not effectively convey the point that the proposed subgoal structure leads to an enhancement in sample efficiency when averaged over the test environments.\n- Instead of total cost, it would be more clear report the number of environment interactions as the performance measure.\n- Table 1: It is not clear what $\\tau$ means here. Is it for a single value of $m$ ?\n- Table 1: I'm confused by what to take away from this.\n- The domains used here are reasonable. However, they are still solvable with standard approaches.  Other domains, where interaction costs are prohibitively high for standard exploration approaches, would provide stronger support for your main claim.\n\n### Other Questions \n- What is a \"Latin Hypercube\"?\n- What does it mean for a subgoal to be complete?\n- Figure 1: Why are the subgoal locations not centered on the cells? Is this significant?\n- Section 3.5: Is $\\mathcal{T}$ just the set of natural numbers?\n- Does $q^n$ control the number of episodes?\n- Section 5.2.1: What were the final values selected for the number of episodes and the steps per episode?\n- Figure 5b: What does the vertical axis represent?\n- Shouldn't the last subgoal always be the original goal?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to improve the sample efficiency of reinforcement learning (RL) algorithms in settings with sparse rewards and costly environment interactions. Specifically, the authors introduce a framework for learning exploration policies that employ a sequence of subgoals, which are trained in a few-shot Bayesian meta optimization setting. The training tasks are drawn from a distribution over parameterized MDPs, and the evaluation is performed on separate tasks sampled from the same distribution. The subgoals are structured by the duration and number of episodes, with the ultimate goal of improving average performance across the task distribution, particularly in spatial navigation tasks. The authors suggest that their algorithm provides useful subgoal structures to exploration policies.\n\nExperiments show a mix of qualitative and quantitative support. The authors evaluate the proposed algorithm on a number of grid world problems and the Mountain Car domain. They provide visualizations of several samples of subgoal sequences and argue that their location and ordering make intuitive sense for the domain at hand. While some examples demonstrate reasonable subgoal sequences, others appear less helpful. The quantitative results are presented in the form of plots showing that the quality of the solution improves as the algorithm is provided with more data. The plots also demonstrate comparatively better trends than the chosen baselines. Although the presentation of the data could be clearer, especially with a different choice of baselines, the results overall show generally positive trends. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Comment on how this work brings RL closer to real-world settings, as your motivation suggests it can.\n- Provide a more candid discussion of related work. \n- Section 3.1: Change $\\gamma \\in [0,1]$ to $\\gamma \\in [0,1)$ .\n- Section 3.1: Change \"arbitrary distribution\" to be something more specific.\n- Section 3.1: Define what a sparse reward is precisely.\n- Section 3.1: Define the $\\epsilon$ -greedy policy.\n- Equation 1: Make it clear that $a_t\\sim \\pi(\\cdot|s_t)$ and $s_1=s$ .\n- Section 3.2: Define a potential function in this context.\n- Equation 2: Make it clear that this holds for all $s,s'\\in\\mathcal{S}$\n- Example 1: Define $n$ .\n- Describe the exploration policy you consider.\n- Describe how the subgoals inform the exploration policy. the process how the subgoals.\n- Section 4.1: Justify the choice of kernels and their hyperparameters.\n- Algorithm 1: Describe how you estimate hyperparameters of the GP prior.\n- Include a section that introduces Bayesian Optimization.\n- Section 4.2: Introduce the notion of Bayes optimality.\n- Include a proof of Proposition 1.\n- Include a summary of the methodology followed in each experiment.\n- Include results from another random baseline that employs experience from multiple randomly selected environments.\n- Remove comparison to MAML.\n- Report single standard error bars (not double standard error).", "broader_impact_concerns": "This paper does not present any ethical concerns that would require a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All 3 reviewers agreed on acceptance. There have been major improvements to the paper due to the authors responding well to the reviews and the extensive interactions with the reviewers.

I understand the authors are still waiting on new results. Once those are ready I will make a final check of the paper. 
Decision: Accept (poster)