Event Tables for Efficient Experience Replay
Authors: Varun Raj Kompella
Thomas Walsh
Samuel Barrett
Peter R. Wurman
Peter Stone
Venue: Accepted by TMLR ()

Abstract: Experience replay (ER) is a crucial component of many deep reinforcement learning (RL) systems.
However, uniform sampling from an ER buffer can lead to slow convergence and unstable asymptotic
behaviors. This paper introduces Stratified Sampling from Event Tables (SSET), which partitions
an ER buffer into Event Tables, each capturing important subsequences of optimal behavior. We
prove a theoretical advantage over the traditional monolithic buffer approach and combine SSET with
an existing prioritized sampling strategy to further improve learning speed and stability. Empirical
results in challenging MiniGrid domains, benchmark RL environments, and a high-fidelity car racing
simulator demonstrate the advantages and versatility of SSET over existing ER buffer sampling

Published in Transactions on Machine Learning Research (04/2023)
Event Tables for Efficient Experience Replay
Varun Kompella
sarwn.oompplal@oong com
Sony AI
Thomas J. Walsh
thomas. wwalssssww.lls@oyccoooo
Sony Al
Samuel Barrett
wwmmuulbarret//Soonn...om com
Sony Al
Peter R. Wurman
peter. welterr.rrmnnnerr Bonooonsswooo.ommmm
Sony Al
Peter Stone
pstone www.ass..ususs.... edu
Sony AI
The University of Texas at Austin, Austin, TX 78712, USA
Reviewed on OpenReview: https: // openreview. net/ por/ff id- XejajAjKjj
Abstract
Experience replay (ER) is crucial component of many deep reinforcement learning (RL) systems. However, uniform sampling from an ER buffer can lead to slow convergence and unstable asymptotic behaviors. This paper introduces Stratified Sampling from Event Ta- bles (SSET), which partitions an ER buffer into Event Tables, each capturing important subsequences of optimal behavior. We prove a theoretical advantage over the traditional monolithic buffer approach and combine SSET with an existing prioritized sampling strategy to further improve learning speed and slability. Empirical results in challenging MiniGrid domains, benchmark RL environments, and high-fidelity racing simulator demonstrate the advantages and versatility of SSET over existing ER buffer sampling approaches.
1 Introduction
Many recent deep reinforcement learning (RL) breakthroughs (Mnih al. 2013 Silver et al. 2016 Wurman et al. 2022) rely Experience Replay (ER) and the corresponding buffer (an ERB) to store massive amounts of data that is re-sampled during training. Consider, however, high-frequency car-racing simulator where agent takes thousands of steps to complete lap and where crucial events, such passing another car, may occur on just few of those steps. Uniform random sampling from an ERB populated with all the lap data is highly unlikely to focus on this key event. Prioritized Experience Replay (PER) (Schaul et al., 2016). which skews sampling based on TD Errors, might do better, but may also focus on states unlikely to be reached by the optimal policy (Oh et al. 2021). To address these limitations of existing ER methods, this paper introduces Event Tables, ERB partitions that hold sub-trajectories leading to events, and corresponding wrapper algorithm, Stratified Sampling from Event Tables (SSET), to build training samples for off-policy RL.
In large domains, simply over-sampling the small number of disconnected state / actions where events occur is unlikely to be beneficial since initial state values would still rely on uniform sampling of the states between event occurrences. Instead, we take lesson from previous works on trajectory-bascl backups (Barto et al., 1995 Karimpanal & Bouffanais 2018) and store the finite-length history that preceded the event in the corresponding event table. Intuitively, this data forms "fast lane" for backups between event occurrences

---

Published in Transactions on Machine Learning Research (04/2023)
that chains back to the initial state(s). And by sampling individual steps from each table iidd. SSET avoids the instability (de Bruin et al. 2015 2016) of using temporally correlated data in mini-batches.
We develop a theoretical underpinning for the fast-lane intuition and show that, if the events are correlated with optimal behavior and histories are sufficiently long, SSET can dramatically speed up the convergence of off-policy learning compared to using uniform sampling or even PER. Even if those conditions fail, a bias correction term preserves the Bellman target, although convergence may be slowed. From our empirical results, these properties translate to different off-policy RL base learners including DDQN (Van Hasselt et al. 2016), SAC (Haarnoja et al., 2018), and the distributional QR-SAC (Wurman et al. 2022 algorithm.
While SSET is a new way to optimize sampling from an ERB, it is complementary to many existing prioriti- zation approaches or behavior shaping techniques. Specifically, SSET can be applied based on known events with TD-error PER used within each table, thereby focusing on crucial states that also need value updates, We apply this "best of both worlds" approach many of our experiments and show that it performs better than using only one of the techniques. Similarly, SSET outperforms potential-based reward shaping in our empirical experiments, but the combination of two provides both better agent exploration and more efficient backups. Finally, viewing each event table as a data set for a particular skill, SSET can mitigate catastrophic forgetting [Goodfellow et al.) 2014 Kirkpatrick et al. 2017) in RL. Our experiments show this advantage in acquiring multiple skills (Section 5.4| and retaining skills over time (Section 7.2
This paper makes several contributions for ER using Event Tables. (1) We introduce Event Tables and the SSET framework. (2) We derive theoretical guarantees quantifying the sample complexity improvement with properly designed events and provide bias correction that ensures the Bellman target is preserved. (3) We empirically demonstrate the advantages of SSET over uniform sampling or PER in challenging MiniGrid environments and ionuin RL benchmarks (MuJoCo and Lunar Lander), and find that combining SSET with TD-error PER or potential- potential-based based reward shaping can further improve learning speed. (4) We also
provide results in the highly-realistic Gran Turismo Sport race-car simulator where SSET improves learning speed and policy stability.
2 Terminology
2018 g. we consider a reinforcement learning agent acting in an episodic Markov Decision Process M (S, R. II I,
Following standard definitions (Sutton & Barto
with state space S, action space A, reward function R: 5, A - Pr[R), transition kernel p : S,A - Pr[S]. discount factor y E [0, initial state distribution I : Pr[S], and episode termination function 8 : S - [0,1) At time step L, the agent uses its current behavior policy Te : S + Pr[A] to select an action and then observes the reward Ta ~ R(st, az) and next state s' ~ P(st, a1). If B(s') = 1 or a horizon of T' is reached, then the episode ends. The value function of a policy is defined by its long-term discounted return: (=(ssa) = R(s,a) + + EEss-(s..)) [V* (s')), where (*(s) = (*, (s)). The agent is lasked with finding an optimal policy "' and the corresponding Q" (s, a) that maximizes the expected discounted return. In this paper we focus on model-free off- off-policy methods that learn Q"(ss, a) directly from data through incremental updates, such as Q-lcarning's (Watkins & Dayan 1992) gradient-style update to the current value function Qu(s, Qk+1(s, = (1 (1-a)Qu(s: a) ad with learning a) for Vs()') = max.' (s','a'') d').
rate a E (0, 1] and temporal difference (TD)-error 8 = r(s, +VV((=))
In deep reinforcement learning, S is typically continuous and high dimensional, so the value function and (sometimes) policy are represented by neural networks with parameters 0ix for each network i. To update the value networks, model-free deep RL algorithms like DDQN (Van Hassolt et al. 2016) make updates to Q(s, ((s) along the gradient of the TD-error. To improve stability, deep RL methods typically utilize a fixed target network for computing Vi((s) that is only updated after batch of updates.
Experience replay Lin 1992p is technique used in off-policy RL to improve sample efficiency by performing gradient updates based on many experience tuples (s, a, r,) stored in an ERB (see Algorithm 2 in the Appendix as an example). In the deep learning case, the ERB often stores tens or hundreds of millions of tuples with bani-batches sampled from the buffer and then used in gradient updates to 0..
Formally, we define an event specification (event spec): == (w, r), composed of a (Boolean) event condition over states w S + {0, 1} and history length We say an event occurs in state 8 if w(s) is true. In this
2

---

Published in Transactions on Machine Learning Research (04/2023)
paper, we assume event conditions are specified by domain experts or RL practitioners: provide guidance on selecting a default set of useful event conditions (refer to Section gh. Section A.1 proves that event conditions that are true only in states that are visited more often by the optimal policy than the behavior collection policy (see Definitions 2 3 and 4 in the Appendix) yield sample efficiency gains when paired with sufficiently long histories. Terminal goal states, high reward states, bottleneck states, or important rare states (e.g- passing another car) are all strong candidates. To avoid under-sampling any crucial states, histories T must be long enough (in expectation) to reach back a previous event occurrence, an initial state, or the horizon and chain together from I to the optimal policy's final state(s) (see Figure I Finally, outside of the core theory, when using function approximation, negatively rewarding states that are not often encountered by the optimal policy may be useful event conditions to avoid catastrophic forgetting of these possible outcomes from nearby states.
3 Related Work
Many approaches have been proposed for prioritized ERB sampling. The most widely used is Prioritized Experience Replay (PER) (Schaul et al. 2016)), which prioritizes state/actions with the largest TD errors. However, PER does not specifically focus on states aligned with the optimal policy: indeed experiences that have zero TD error under one policy may never be sampled again even after the behavior policy has changed. In addition to empirical comparisons against PER, we show that SSET can be used with PER to leverage the benefits of both approaches: focusing leaning on high-value event trajectories aligned with the optimal policy, but also prioritizing states along those trajectories with high Bellman error. Other met that augment vanilla PER with prioritization based on model error (Oh et al. 2021 or a meta-learning process (Zha et al. 2019) could similarly be used conjunction with SSET.
The importance of sampling along "good" trajectories was explored in classical RL through RTDP (Barto et al. 1995) and in deep RL (Karimpanal & Bouffanais 2018). The latter cause unwanted data correlation in mani-e (de Bruin et al. 2015 2016 Huang et al. 2019). By contrast, SSET does not attempt to use data from the same trajectory in mini batch, instead relying on sampling to spread trajectories across many mini-batches, providing both stability and backups along a trajectory. Variants of Topological Experience Replay (Hong et al. 2021 Lee et al., 2019) also attempted to prioritize backups along a trajectory using a graph embedding originating from goal states. By contrast, SSET does not require goal states or discrete state embedding.
Event Tables generalize the idcas explored in several "multi-table" partitioning schemes for ERBs. In Narasimhan et al.) 2015)) and (Sharma et al. 2020) different tables are used to store high (or high and low) reward transitions separately from common transitions and stratified sampling is used to construct mini-batches. By contrast, SSET allows for any state-basod event to partition the ERB, and more impor- fantly stores trajectories that led to events, not just the events themselves, which is essential to ensure the sample complexity guarantees. Fampirical comparisons to a reward-based event. approach without histories are provided in Section 5.6 Lucid Dreaming (Du et al. 2022) stores trajectories that produce better Monte Carlo returns than the current value estimates in separate table, but relies on generative access to the domain to create them, which is not a requirement for SSET. (de Bruin et al. 2016) keeps two bullers, one for on-policy data and another more "uniform" " buffer, but requires heavy kernel computation to maintain them.
A closer comparison is the use of multi-tables in the training simulated race car (Wurman et al. 2022 There, the ERB is partitioned into multiple tables for different skill training scenarios based on initial states (e.g. tables for driving alone, driving in traffic, etc.) Event Tables are a generalization of this idea where data is dynamically mapped to tables rather than partitioning an episode's initial state.
SSET also bears resemblance to multi-task and lifelong learning RI. algorithms that balance the amount of data used from different tasks. Some of these approaches (e.g. Lin et al. (2019)) sacrifice general performance for success on a "main" task, or mitigate catastrophic forgetting across a sequence of tasks (Isele Cosgun 2018 Rolnick et al.] 2019 Yin & Pan| (2017) which are not applicable in our singlo-task setting. Hindsight Experience Replay (Andrychowicz et al.) 2017) augments the monolithic ERB in a multi-task setting by imagining goals that the trajectories could have achieved. SSET is not restricted to the multi-task setting
3

---

Published in Transactions on Machine Learning Research (04/2023)
Legend
Initial State
At-Gap Event State
Default Table
Done Event State
Data
Event
Data
Figure 1: An example MiniGrid domain with event conditions for reaching the goal gap between rooms. Blue squares indicate the "fast lane" of states that can be over-sampled because they appear in both the event tables and the default table. Grey states appear only in the default table.
but could be combined with HER in such cases. CAGrad @Lu et al., 2021 constructs gradients in a way that minimizes policy degradation on the worst affected task, and is natural pair with SSET, where updates to the model can be performed in way that preserves performance in each of the ERB partitions (see experiments in Section 5.7
SSET uses prior knowledge to ensure focus key areas of the state space and therefore has connections to initial state selection [Taanvvie al., 2019) and potential-based reward shaping (Ng el. al. 1999 Grzes
2017). Section 5.2 shows SSET outperforming reward shaping on comparable states, but also demonstrates
that the two can be used together to improve exploration (shaping) and focus value function backups (Event
Tables). Because Event Tables often align with bottleneck states, they have relationship to options (Sutonn
et al. 1999,, but the mechanism in our work through ER. While events in our case come from domain
knowled kooweedge, futuure work could utilize subgoal discovery techniques (Kulkarni al. 2016 McGovern & Barto 2001 to identify potential events.
Algorithm 1: SSET: STRATIFIED SAMPLING FROM EVENT TABLES
//input parameters:
= (Wr, T.) Vi [1,n]: event conditions and their corresponding history lengths
Ki, d,) Vi E [0, n]: sampling probabilities, capacity sizes, and minimum data requirements A, T Off-policy RL algorithm, behavior policy and episode length
5 + (mr)), 8 + [(())) vi E [1,n].
for episode
to 0 do
E + // init episode buffer for t= to T (or episode termination) do +- current state observation
execute action a sampled from (8)) observe r and next state s'
10
store transition as,,,,,s) s') in B and E for i - to do //update event tables if (s(')) then store last 7; transitions [E, Ed] in B end end 16
12
13
14
15
17
end
18
5 LB Vi s.t. |B%| 2 d, //sample & concat i.i.d. minibatches
19
Update weights for bias correction using E // (Lemma in Appendix)
20
Update critic and policy networks using A and D
end
4

---

Published in Transactions on Machine Learning Research (04/2023)
4 Stratified Sampling from Event Tables
We now formally define Stratified Sampling from Event Tables (SSET; Algorithm 1 and state our main theoretical result. The full proof appears in Section A.1 Given n event spees {ui E [1, nil the ERB is partitioned into n event tables, B and a "default" table 8 Each 8% holds only time steps where wy(s") was true or steps preceding the event occurrence in the Ty-length history. The default table 8 holds all time steps, including those with event occurrences. Data is inserted into each table in FIFO manner with table capacities governed by parameter Ky and later used to construct training data for off-policy RL algorithm A.
On each agent step in SSET, experience (st,a,, "t,,a,,,,,,, S(41) is stored in E as well as an ephemeral buffer E for the current episode (line 11. If wi(+)+1) is true (line 13 the experience and all the T; steps preceding the event that were not already sent to B are added there as well. Intuitively, each table contains data necessary to train the value function in the area approaching an event occurrence and chain logether to form a "fast lane" (Figure I for backups that will be over-sampled compared to monolithic ER. For simplicity Algorithm 1 be surjective. Note that the (potentially overlapping) data stored in these tables can be managed efficiently by ERB implementations like Reverb (Cassirer el. al. 2021 n.
assumes each event spec maps to a unique table (lines 4 and 14 but the mapping could also
When mini-batches are constructed (line 18 fixed i.i.d. proportions are collected from each table using probabilities Ty, for E [0, n]. To prevent early over-fitting, minimal data requirements (based on the mini- batch size) can be applied, with proportions normalized appropriately if one or more tables has insufficient data.
Like PER and other ERB prioritization schemes, SSET can introduce bias in stochastic environments. In the extreme case, if P(s, a) has equal probability for two terminal states 81 and 82 but only w(s1) is true, then sampling from the event table will skew the data distribution higher for 81 outcomes. To alleviate this error, line 19 applics a weighted correction derived in Lemma 2 (Appendix). The full correction term applies a weight based on the probability of (s, a) not being in each event table, which can be computed in discrete domains by counting the number of times a (s, a) pair was not part of any event history. For continuous domains, a priority sum tree data-structure could be used similarly to PER (Schaul al. 2016) by setting priorities for samples in the event buffer equal to (1 + 7) and samples outside to (1 -1-10 77). The correction weights for each transition inside the event tables would be priority-sum However, this approach is aggressive and might slow down learning, as seen in PER. Note, for deterministic MDPs the correction is not needed. In environments without non-goal terminal states, increasing т may mitigale some bias by storing more non-event outcomes in the event table. In our mildly stochastic empirical studies we use this longer 7 approach.
1+;
We now state the main theoretical result of the paper, with the full proof in Section A.1 Intuitively, the theorem states that SSET using event conditions that are correlated with an optimal policy and histories that are sufficiently long, will have sample complexity NB K for learning Q" a) in the necessary part of the state space (8²), and N8"UB", KK is (with high probability) smaller than the sample complexity of learning with monolithic buffer of the same size.
Thcorem 1. Let 8 (s {s P(T C BB) b} denote the set of stotes s.t. the sampled optimal trajectories (T";; ; :Def. () starting from those states are contained in the combined event-buffer with a probability greater than p E (0,1), and 1 = Σi Thp Under the conditions of Prop. ] and using i as defined in Lemma 1 if [m+1]app then at iteration K of Q-learning with target function:
TvkE(L,n) S (1-m)"
P (N K < (11-1)) (1--))= (11-))2m8B.88 N..KK 2 2g.sE m m 2
Proof sketch. We make use of lower bounds [Li et al.) 2022) on the convergence rate of labular Q-learning with a target function (Algorithm in the Appendix). We define the state probability distribution (density) following given policy to a finite horizon from an initial state and use that define the state density disparity to the optimal policy. We then formally define event conditions on the states with low optimal- policy disparity or final states of the optimal policy. We extend this definition to event sections and their
5

---

Published in Transactions on Machine Learning Research (04/2023)
Get to the green square
(a)
Summed Q-Values
Episode Return
-32
Retur
-20
(b)
(c)
-20
-992
SSET
-40
SSET
Sweep*
Sweep*
Uniform ER
Uniform ER
250
590
750
1995
1956
1500
1758
7000
35p
5ce
356
1900
175h
175
7000
training opach
training epoch
With TD-Error Prioritization
Summed Q-Values
Episode Return
-200
Retum
(d)
(e)
000
Prioritized SSET
-00
Prioritized SSET
Prioritized ER
Prioritized
200
SSET
SSET
350
500
750 1006
1259
1750
2000
252
520
350
1063
1350
3500
3750
7000
training epoch
training epoch
Figure 2: Three Room Grid World Statistical results from 30 randomly seeded runs (mean shown using solid lines and std-error using shaded regions) (a) Environment (b) Learned target Q-values summed across the entire state-action space vs training epoch. SSET Q-values converge with a significantly low std-error. (c) Episode return vs training epoch (d)-(e) Results with TD-error prioritized sampling.
corresponding tables that include sufficient history to (on expectation) reach back to a previous event or initial state. We then quantify (Lemma] I the over-sampling of experience in the event tables and derive the convergence rate (Prop. g and bias correction procedure (Lemma 2). Finally, we show that the resulting convergence bound an improvement over uniform sampling.
5 MiniGrid Experiments
We provide experimental validation of SSET in environments from the MiniGrid Boissver ct al. 2018) domain using the DDQN (Van Hasselt et al., 2016) RL algorithm. We use a dense neural not architecture with hidden layers to encode the Q-functions and an e-greedy behavior policy for collecting data. In each experiment SSET demonstrates improvements sample complexity or decreased variance against uniform experience replay (Uniform ER), an off-policy version of an (on-policy) reverse sweep updates from the goal (Reverso-sweep"; in the spirit of EBU (Lee et al. 2019 ), and TD-error prioritized experience replay (PER) (Schaul al. 2016

---

Published in Transactions on Machine Learning Research (04/2023)
Mission: Get to the green square
(a)
Summed Q-Values
Episode Return
-10
400
-00
-32
SSET
SSET
Shaping (gap)
Shaping (gap)
Shaping a SSET
Shaping +SET
-1000
eco
training epoch (b)
training epach (c)
Figure 3: Comparison with Intermediate Shaping Rewards. Results from 30 randomly seeded runs comparing SSET against using intermediate shaping reward at the gap. (a) Environment (b) Learned target Q-values summed across the entire stale-action space vs training epoch. (c) Episode return vs training epoch.
5.1 Proof of Concept: Three Room Grid World
We first demonstrate the sample complexity speedup of SSET in three-room world (Figure Za)). The agent's observation is its 3D grid position and orientation (x, y, 0) and its available actions are turn-lefl, turn-right and forward. The rewards are +1 at the green square and -0.1 otherwise. We use two event conditions for SSET with a history length of 200: one that occurs any gap state between two rooms, and another that occurs at the green square. Refer to the Appendix for more details. Figures (c) show the and standard error (from 30 randomly initialized runs) of the learned Q-values summed across the entire state-action space and the resulting episodic return during the course of training, SSET performs best in terms of both sample efficiency and learning stability (lower variance between runs). The result against a reverse-sweep approach demonstrates the utility of the intermediate gap events, which serve as waypoints for the backups. Figure dd)-(e compares SSET to PER and a combination of the two. PER speeds up learning compared to uniform sampling, but with considerably more variance across seeds than SSET, possibly due to overestimation bias. Combining SSET with TD-error prioritization yields the best of both worlds; providing reliable local Bellman target estimates and prioritizing samples with high error to those targets.
5.2 Comparison with Shaping Rewards
Potential-based shaping (PBS) [gg al 1999 Grzes 2017) provides framework for adding rewards to speed up Icarning without affecting the optimal policy. Similar to PBS, SSET preserves optimality (sce Lemma 2 in Appendix) while providing an effective way to infuse domain knowledge. Here, we compare the performance SSET and reward shaping as well as their combination a grid-world domain similar to the previous experiment (Figure (()).. A shaping potential with Φ(s) at the gap and 0 elsewhere used provide reward component of (yø(s') p(s)) in addition to the environmental (goal) reward. SSET events that occur the gap and the goal. Figures 3b)((c) show SSET outperforms both shaping and

---

Published in Transactions on Machine Learning Research (04/2023)
Mission: Get to the green square
near goal
near initial
Potential Shaping Functions
(a)
SSET with Different Event Conditions
episode retur
episode retum
-12-
10-
shaping
Reward Shaping (gap)
no shaping (UER)
right-woll
shaping (UER)
lelt-wall
manhattan gool manhattan_gan
only_gap gap near, Jnitial
only_gost
+50
gap
-59
250
500
1002
2250
1500
1758
2000
250
500
750
1000
1250
1590
3150
2000
training epach
training epach
(b)
(c)
Figure 4: SSET performance with ideal and less-ideal event-conditions (a) Environment (b) Com- parisons of different potential-based reward shaping functions with uniform FR to use baselines (c) SSET's performance of ideal and less-ideal event conditions along with baselines (Uniform ER with our best shaping function and with no shaping rewards).
the no-shaping baseline. While reward shaping acts heuristic to speed up exploration, those rewards still need to be bootstrapped back to the initial states, which is the forte of SSET. Thus, when the two are combined (brown line), even better performance is realized as shaping guides exploration and SSET provides a "fast lane" to bootstrap the values. Comparisons to less ideal potential shaping functions and ablations of the No parameter for SSET in this domain are provided Sec. 5.3
5.3 SSET Performance with Badly Designed Event Conditions
Based on the formal definition of event conditions (Def. 4 good events occur in states that are aligned along optimal trajectories. We assume that such event conditions typically specified by domain experts or RL practitioners. In this section, we evaluate the performance of SSET when the event conditions are badly designed and compare them against good conditions, along with other baselines such as uniform ER with different potential reward-shaping functions. Finally, we also study how performance varies with changes to the default buffer's sampling probability (no).
Figure 4 (a) shows results from the 2D grid world domain used the reward shaping comparisons (Sec- tion 5.2 The task is to get the green square starting from an initial bottom-left grid position, which requires navigating through the gap between the rooms. We first compare several potential reward-shaping functions to pick a good baseline. Figure (bb) shows the statistical means (computed from 30 randomly seoded runs) of episodic-return during training using different potential shaping functions: gap (+1 at the gap grid position and zero everywhere), manhaltan goal (normalized manhatlan distance between agent's 's position and the goal), manhattan_ (distance to the gap), right-wall (normalized didittance to the right boundary wall), left-wall (normalized x-distance to the left boundary wall) and no-shaping. Not surprisingly, the best performing shaping function the 'gap" function, which motivates the agent to get to the gap first. Others perform either similar subpar to the experiment with no-shaping rewards.

---

Published in Transactions on Machine Learning Research (04/2023)
Performance vs Default Buffer Sampling Weight (no)
No 0.9
No 0.7
Epicodo Beturn
Episode Return
-12-
-10
950, goal
gop, gool
only gap
onl gap
near Inhiia
near Intiia
500
750
1250
1560
2000
500
1290
1962
2000
training epoch
training epoch
(a)
(b)
No 0.5
No 0.3
Episadic Retur
Episode Return
gsp_goal
gap. goal
only goal
only gool
only_gag gap
only gap
near, near_intial
near near_intbal
-50
near goo_ggaall
-00
near_goal
300
1258
1300
300
L302
(c)
training epoch
(d)
training epoch
no 0.1
Episode
Uniform ER
only.goal
only pap
Initial
near gool
-30
250 1000
1250
1939
1750
2000
(e)
training epoch
Figure 5: SSET performance vs default-buffer sampling weight Statistical means of episodic-returi from 30 randomly seeded runs for different values of dlo and different event-conditions Experiments with good conditions (gap_godt goal, only_goal) are least affected by the changes in 170- The experiment with the mediocre condition (near (icar_goaa) seems to benefit from fine-tuning (best at 0.7), and the experiments with bad conditions (near initial, only gap) suffer due under-sampling the default buffer.
Next, compare SSET performance for different event conditions and 170 0.7: two conditions (based Def. 4 that trigger at the goal and gap (gap goal), or goal alone (only_ goal) with sufficient history length (T = 30). We selected three less-ideal conditions that occur at positions near the goal (near goal), at the gap (ouly_gap) and near the initial position (near ieiiiiiiiial,,..aa respectively. Figure [(c) shows statistical means of the corresponding experiments along with the basclines shaping (using the gap potential function) and uniform ER with no shaping. The plot shows that there is a significant improvement in learning efficiency for experiments using the well defined events. The performance of SSET of near goal event condition is not

---

Published in Transactions on Machine Learning Research (04/2023)
Get to the green square
(a)
Q-Values Averaged Over Agent's Trajectory
Episode Return
Return
-20
-00
-eacc 015.al)
-35-
4.0
045
-00
SSET
SSET
Reverse Sweep"
Reverse Sweep?
Uniform
Uniform
200
training eacch
training epoch
(b)
(c)
With TD-Error Prioritization
Q-Values Averaged Over Agent's Trajectory
Episode Return
-130
-135
Return
-2.00
Leaer O1s.al)
-15
-2.5
-20
Σ
-2.55
-562
-3.2
Prioritized
-20
Prioritized SSET
SSET
SSET
440
Priortized
Prioritized ER
100
200
300
200
360
998
training eacch
training epoch
(d)
(e)
Figure 6: Obstacle Course Results from 30 randomly seeded runs (mean shown using solid lines and std- error using shaded regions) (a) An environment with spikes (yellow), lava (orange), colored keys and locked doors (b) Learned target Q-values averaged over agent trajectories vs training epoch (c) Episodic return training epoch (d)-(e) Results with TD-error Prioritized Sampling
ideal, but still much better than our best shaping baseline. Experiments with only_gap and near initial conditions perform similar the Uniform ER (no-shaping) as learning relies significantly on transitions the default buffer to bootstrap the value from the rewarding states (goal reward in this case) the states where the events occur. Based these results, conclude that both reward shaping and event tables show degradation when using poorly chosen shaping functions event conditions but that even with poorly chosen events SSET often outperforms reward shaping in this domain.
near_initial
Next, we compare how SSET's performance varies with default-buffer's sampling probability (Figure 5). The plots show that experiments with good conditions are least affected by the changes in T70- The experiment with the mediocre condition (near goal) scems benefit from fino-tuning (best at 0.7), and the experiments with bad conditions suffer (no 0.7) due to under-sam sadel-sampiin the default buffer. For all practical purposes, recommend using higher values for ?h unless the event. conditions carefully designed.
10

---

Published in Transactions on Machine Learning Research (04/2023)
Lava Configuration
Gap Configuration
Door-key Configuration
(a)
(b)
(c)
-50
Epicade Raturn
Episoce
-100
-15
-15
150
SSET
SSET
SSET
-75
Prioritized ER
-25
Priontized
Prioritized ER
Uniform ER
Uniform
-200
Uniform
1000
2000
3000
e00o
5000
7000
3000
1000
2000
3000
4nco
5000
B000
T00O
B000
5
1000
2000
3000
coop 5000
600n
7000 8000
training epoch
troining spach
training opoch
(d)
(e)
(f)
Figure 7: Randomized Skill Environment Statistical results from 30 randomly seeded runs (mean shown using solid lines and std-error using shaded regions) (a)-(c) Instances randomly sampled object configu- rations. (d)-(e) Episodic return for each skill during the course of training.
5.4 Obstacle Course and Randomized Skill Environment
The more complex obstacle course environment consists of multiple sections (Figure 0 (a)) containing spikes with -1 reward (yellow squares), lava with -1 reward and episode termination (orange squares), and colored keys to open doors. The exact positions of lava, gaps in the walls, keys, doors, and key/door colors are randomly set in each episode but the ordering of the rooms is fixed (e.g. the spikes are always in the first room). The agent's task is to get to the green square starting from the top-left corner. The agent's observation consists of (a) an egocentric 5 localized forward-view image (highlighted region in Figure Gla) that encodes a representation of obstacles around it, (b) Boolean indicator for carrying an object, (c) 2D representation (category, color) of the object it is carrying, otherwise (-1.-1), and (d) 3D grid position and orientation (x, y, 8). The agent's action space includes 3 additional actions (pickup key, drop key, toggle door). We use event. conditions with history length of 50 associated with each obstacle category (e.g. picked-up-a-key, opened-a-door, etc. see Appendix for more details). Figure 6 bbb((c) clearly illustrates the improved efficiency and stability of using event-tables over reverse-swecp and uniform ER. In comparison TD-error prioritization (Figure ())-))) again PER exhibits more variance across multiple seeded runs. Interestingly, this domain, SSET performs cqually well with or without additional TD-error prioritization.
Finally, consider randomized multi-skill setup where the agent must either avoid lava, go through gap, open the correct door to reach the goal (Figure 7 ac)). The scenario (lava, gap, open-door) and object positions/ / colors are sampled randomly for each training episode. This is a more challenging task than the obstacle course above because object locations don't follow a fixed sequential pattern. A square that contains a door in one episode may contain lava in the next one. Using uniform ER, value function learning dominated by the casier skills (lava, gap) and the agent fails to acquire the difficult open-door skill. Learning using SSET performs much better, acquiring and maintaining all the skills compared uniform sampling and even PER
11

---

Published in Transactions on Machine Learning Research (04/2023)
Init Pos (Training)
Init Pos (Evaluation)
(a)
Successful Episodes (out of 30)
num episodes
Prioritized Prioritized ER Uniform ER
M
Aw
Man MM
155
3-
250
750
1000
1250
1500
1750
2000
training epoch
(b)
Figure 8: Evaluation Result of a Slightly Shifted Initial Position Test-time performance of the agent starting from a slightly shifted initial grid position (1, (a) Environment instance (b) Number of successful episodes out 30 seeded runs of the experiment for each evaluation checkpoint.
5.5 Catastrophic Forgetting in Obstacle Course
Here, we illustrate how SSET avoids catastrophic forgetting that hampers even PER during extended learning in the obstacle course experiment presented in Section 5.4
At the end each episode during training, the agent always reset to the top-left corner (1, of the environment. a frequency of every 20 epochs during training, we evaluated the performance of the agent starting from slightly shifted initial grid position (1,4) as shown in Figure B()). Figure (b shows the number of successful episodes over the 30 sceded runs of the experiment for cach evaluation chockpoint. An episode is considered successful if the agent is able to navigate through the obstacles and reach the green square. The plot shows that the agents with both uniform and TD-error prioritized experience replay learn how to complete the task early on, but forget the skill as training continues. We hypothesize that due to changing epsilon-greedy behavior policy, the Q-function updating with samples from a standard FIFO uniform (and even prioritized) replay buffer, quickly begins to over-fit trajectories starting from (1, 1) avoiding the nearby negative rewarding spikes. Over-fitting on these trajectorics potentially leads losing previously learned estimates for nearby transitions. On the other hand, with SSET and sampling from the at-spike event table that is unaffected by the updating behavior policy, the agent continues to improve its value estimates for those transitions over time resulting in better behavior.
In the context of this particular experiment and similar RL domains, having robust performance against perturbations not typically expected and therefore catastrophic forgetting may not a serious issue. However, becomes challenging issue to tackle in realistic domains like Gran Turismo where the training and testing distributions can be different or the domain is simply large that one can forget low probability events, like leaving the course in Section 7.2
12

---

Published in Transactions on Machine Learning Research (04/2023)
Advantage of Intermediate Events
return
40
-60
80
SSer
Done (r 300
Done (r 2000
-100
Done (t 1000
Done (y 11
100
200
300
400
500
600
training epoch
Figure 9: Episodic return from 30 randomly seeded runs (mean shown using solid lines and std-error using shaded regions) in the obstacle course environment comparing SSET with intermediate events like, pickup- key, at-door, etc. against only using a done-conditioned event with different history lengths.
Sensitivity to Sampling Weights
60
Handset n
0.083
0.4. 2......
0.02
Noone 0.4, m... Bone 0.02
Uniform ER (reference)
300 training epoch
500
Figure 10: Episodic return from 30 randomly seeded runs (mean shown using solid lines and std-error using shaded regions) in the obstacle course environment comparing different sampling weights 7 keeping the default table's sampling weight fixed To = 0.5.
5.6 Intermediate Events, Histories, and Sampling Weights
The proof of Theorem I shows that SSET improves sample complexity along transitions from the optimal trajectory that are, with high probability, stored in the Event Tables. We can increase this probability by either increasing the number of event conditioned tables n with short histories or having fewer tables with longer histories т₁ However, the proof of Lemma [ shows the latter is not as effective, especially in early learning when the histories leading to a far-off event may contain many sub-optimal actions, diluting the impact of that table until the policy better optimized. Instead, when possible, it best to have many events acting as waypoints in the environment as shown in Figure [ We now present an empirical test supporting this insight in the sparse-reward obstacle course environment presented in Section 5.4 The test doubles comparison to methods that partition an ERB based solely on reward conditions without corresponding histories (Sharma et al. 2020).
We compare SSET with the intermediate events used in Section 5.4 (pickup-key, at-door, etc.), each with a history length of 50 (see Table I for parameters) against only using a terminal rewarding event with different history lengths. Figure g shows the statistical average curves of episodic return during the course of training computed from 30 random seoded runs. It is clear from the result that SSET with intermediate events outperforms the rest.. Intuitively, intermediate events can be seen waypoints on the fast. lane for
13

---

Published in Transactions on Machine Learning Research (04/2023)
Lava Skill
Gap Skill
Open Door Skill
Episode ftetrn
Episade Return
Epicade Return
-30-
-10-
-15-
-10
c=0
-20
C=0
-150
c=0
-25
.25
-25
25
-375
c=.
==
C=.5
-200
c=.5
-30
1050 2000
30d0
6000
5002
6002
1003
1000
-20
1000
2000
3000
4003
5002
6003
1003
100
2000 2000
2000
6000
7000
5000
training epoch
training epach
training epoch
Figure 11: CAGrad with SSET Statistical results for different values of CAGrad's coefficient of regular- ization c E [0, 1) from 30 randomly seeded runs (mean shown using solid lines and std-error using shaded regions). Higher values of e boost early performance but result in a lower asymptote.
TD backups to the initial states, thereby improving the overall sample efficiency. The plot also highlights that just sampling terminal goal states (as in SER (Sharma et al.) 20200). T = in the chart) or transition sequences leading to them (as in TER (Hong et al. 2021), EBU (Lee et al. 2019 or Reverse-Sweep" higher I values) may not be sufficient to achieve improved efficiency in a sparse reward setting like the Obstacle Course.
Finally, in Figure we compare SSET performance for different sampling weights di keeping the default table's sampling weight fixed (No 0.5). Handset 7 the same as the ones mentioned in Table | in Appendix, 7>>0 0.5/6 0.083 are weights distributed equally across the six event tables, 'ddoor 0.4 assigns large weight to the door event table and 7/oone = 0.4 assigns a large weight to the done table. The sampling is done such that there is at least one sample picked from each table. The results show that the performance is similar with the extreme sets showing some minor fluctuations at the end, but still performing better compared to using uniform experience replay. Our general recommendation to start with using equal weights across all events tables and if needed tuning them further to get a peak performance.
5.7 Conflict Averse Gradient Descent with SSET
Most temporal-difference RL algorithms like Q-learning rely on minimizing Bellman errors to local target estimates (Qu; see Alg, 2 With an increasing number of outer iterations, these local targets inch closer to the true global target Q", thereby optimizing the RL objective asymptotically. During carly training, stratified mini-batch sampling from event tables could result in local gradients that may conflict. with each other. Using a standard average gradient descent approach, like SGD, might not be beneficial for uncommon difficult-to-lcann events the average gradient would be skewed in the direction of the casier events. For example, in the randomized multi-skill experiment presented in Section 5.4 (Figure 7 the agent takes longer to learn the open-door skill compared to the others. Previous multi-task learning work has proposed several approaches mitigating this problem, albeit in a multi-task pareto-optimal setting. We explore using one such recently proposed multi-objective optimization algorithm called Conflict-Averse Gradient descent (CAGrad) (Liu al. 2021) to see if we could boast up learning the difficult open-door skill.
Figure I1 shows statistical results using CAGrad with SSET for different values for the algorithm hyper- parameter (0, 1), which controls the extent of minimizing conflicts between losses within local ball centered around the average gradient. Therefore, setting descent. The plots illustrate that higher values of c boost initial learning but result in lowering the asymptotic value. This can be explained by the fact that, as the local value function targets Qs move closer to the global target Q", the conflicts between event-section losses minimize making conflict optimization redundant. We hypothesize that scheduling the parameter from high values to zero during the course of training would improve the sample complexity and reach optimal asymptotic behavior. Exploring different schedules is outside the scope of this paper and we leave this for future work.
0 reduces to the standard average gradient
14

---

Published in Transactions on Machine Learning Research (04/2023)
Lunar Lander (Continuous)
Episode Return
300
solved
700
100
-200
-300
Unitorm ER
-100
Priorit, ERIO.S)
2000
4002
2002
10000
Half Cheetah Episode Return
trainiing epoch
Walker2D
(a)
Episode Return
14003
12000
12000
4000
2000
5000
4000
SSET
7000
Prioriizeed ER1O
Priotiized
1000
Prontiized ERJO 8)
fiteed BRi0
0-
4050
4030
training epoch (b)
epoch (c)
Hopper Episode Return
Humanoid Episode Return
3500
9200
3200
8000
2500
2200
6000
1500
5000
Uniform ER
1200
SSET
Prioritzed ER/O 2)
SSET Priritized
Printized
500
1000
2000
3200
4200
10000
22003
30000
40020
50000
training epoch
training opoch
(d)
(e)
Figure 12: Continuous Control Benchmark Tasks SSET out various parameterizations of PER and Uniform sampling in common RL benchmarks.
6 Lunar Lander and Mujoco Experiments
We now demonstrate the improved sample complexity and stability of SSET several continuous control benchmark tasks (LumarLanderContimmnn))
and MuJoCo (Todorov et al. 2012) suite defined in OpenAl Gym [Brockman et al.) 2016)) that have dense shaping rewards and, in the case of the MuJoCo domains, no pre-defined goal states. For the LunarLander environment, we used two event conditions for SSET with a history length of 200: one that occurs when both lander's legs make contact between the flags, and another when the lander's position close the middle of the flags. For the MuJoCo suite, we used three event conditions that occur when the agent receives rewards greater than certain thresholds (See Appendix Table Each of those events used history lengths of 200. The thresholds manually selected for each environment
15

---

Published in Transactions on Machine Learning Research (04/2023)
Half Cheetah Episode Return
Walker2D Episode Return
5000
12000
1000
3000
5000
2000
4003
SSET (5- 200)
SSET 2001
2000
100)
SSET 100)
SSFT 50)
12- 1)
SSET (X- 11
0-
1002
7003
1000 training epoch (a)
4000
5000
0
1000
2000
2050
1002
5000
0005
tralining epoch (b)
Hopper Episode Return
Humanoid Episode Return
3500
3000
7000
2300
6000
2000
3000
1500
1000
SSET (t- 200)
SSET (r- 100)
[2- 100)
SSFT
SSET (t- 50)
SSET (r- 11
1000
2000
3000
4200
3000
10003
15000
20030
training epach
training epoch
(c)
(d)
Figure 13: Continuous Control History Lengths (r) SSET performance in MuJoCo domains at different history lengths. SSET benefits from using sufficiently longer history lengths, which can be tuned for peak performance.
based on the reward bounds. We used the stato-of-tho-art SAC (Haarnoja et al. 2018 RL algorithm to compare SSET against uniform experience replay and PER al different priority exponents. Figure shoows the statistical mean and standard errors of empirical returns computed from 30 randomly seeded episodes evaluated at different epochs during training. The results definitively illustrate SSET improves sample- efficiency (by roughly half the number of epochs) and achieves stable policies by bootstraping the salient rewards more rapidly. All four of the MuJoCo domains and LunarLander show similar patterns for SSET. PER performs at-best similar to the uniform experience replay and the performance degrades as we increase the priority exponent. We suspect this is because of the high density of shaping rewards, which makes the TD-Errors volatile, making them a bad match for PER.
Next we show results from an ablation study of changing history lengths in the dense reward MuJoCo domains, similar to the experiments in sparse reward domains in Section 5.6 Figure 13 shows the average episodic return (with std-error shown using the shaded regions) during the course of training computed from 30 random seeded runs. In MuJoCo domains, rewards are proportional to the continuous progress made by the agent and with events based on reward thresholds, sample histories for a higher threshold get stored in the tables corresponding to the previous threshold. The results of this study show SSET is again robust to 'non-optimal' history lengths, but still show the benefits from using sufficiently long history lengths. These results reinforce the use of longer history lengths in the absence of prior knowledge, and also show the history lengths can be tuned for a peak performance.
16

---

Published in Transactions on Machine Learning Research (04/2023)
Cumulative First Place Finishes
Avg. winning margin (w/o losses)
cumulative first place finishes
in last 100 epochs
SSET13)
80
558112)
SSET(1)
SSET13)
S58114)
SSET(2)
SSFT15)
SSET(3)
60
Unit1:
run(replica)
SSET(4)
Unit3/
SSET(5)
Uni[4;
40
Uni(1)
Uni(2)
Uni(3)
20
Uni(4)
Uni(5)
0
10 15
20
25
0
100
200
300
400
500
winning margin (meters)
epoch
Figure 14: Left: Cumulative wins evaluated every epochs in the slingshot passing test. Uniform sampling shows high variance while SSET with slipstream (0.7) event and a "won" event consistently has sample complexity par with the best uniform-sampling run. Right: Average (and std dev) of winning margins (excluding losses) in the last 100 epochs for each run. While one uniform ERB run did best, average (dashed lines) SSET has the consistently better performance.
7 Simulated Car Racing Experiments
Gran Turismo" TM Sport is PlayStation racing simulator that has been previously used as an RL testbed (Fuchs et al.] 2021: Song et al. 2021) and where an RL system recently outraced human e-sports champi- ons (Wurman et al. 2022j. The latter work used a multi-table ERB based on different imitial state conditions, which in the experiments below is equivalent to the uniform sampling approach. We show the SSET speeds up convergence when learning to pass another car and mitigates off-course driving in a time-trial scenario.
The environment, features, and training details (see Section A.3 are the same Wurman et al's except that focus smaller sccnarios to isolate the specific effects of Event Tables. All experiments collected data at 10Hz from 21 PlayStations with one of those typically dedicated to evaluation lasks. The state representation includes hundreds of state features covering aspects such 3-D velocity, steering angle, a representation of the upcoming course points, and representation of opponent cars including [0, 1] measure of the slipstream produced by a car ahead. The Quantile Regression SAC (QR-SAC) algorithm used with 2048 x ferd-forward neural networks for the value functions and policy. Dropout is used when training the policy network.
7.1 Learning the "Slingshot" Pass
In the first experiment, demonstrate SSET 's sample complexity benefits in "slingshot passing" scenario on the Circuit de la Sarthe (Sarthe) track, using Red Bull X2019 Competition race car, similar to Formula vehicle. The environment is a relatively straight 1700 meter section of the course with the RL agent always launched behind (in training between [10,40 40] meters) one built-in-AI from the game. To succeed, the agent needs to use the opponent's slipstream to accelerate beyond top open-air speed and use the added momentum to slingshot by the opponent and hold it off the end of the section. Reward function components incentivize course progress and passing and penalize wall hits, car collisions and off-course driving. Full details are provided in the supplemental material.
For this task, we introduce two events. A "slipstream" event (with 7 = 10s) occurs when the agent's slipstream feature is above à threshold (0.7 in this case) and "won" event (with - = 15s) occurs the agent ends the section in first place. Both events use x = = 10%. Figure [eruoort] the cumulative wins for replicas each of SSET versus a monolithic ERB with uniform sampling, both with total capacitics (Σ k;) of 2.5 million steps and sharing common seeds. Policies were evaluated after every 5 epochs with the agent started 35 meters behind the opponent. The uniform sampling runs display high variance, taking anywhere
17

---

Published in Transactions on Machine Learning Research (04/2023)
Cumulative First Place Finishes (Threshold 0.1]
Avg. winning margin (w/o losses) in last 100 epochs [Threshold 0.1]
cumulative first place finishes
SSET(1)
SSE122)
SSET(1)
SSFT(3)
SSET(2)
60
SSET(5)
SSET(3)
Unit3)
run(replica)
SSET(4)
SSET(5)
40
uni4)
Uni
Uni
20
Uni(3)
Uni(4)
Uni(5)
10 15 20
25
100
200
300
400
500
winning margin (meters)
epoch
Figure 15: Left: Cumulative wins evaluated every 5 epochs in the slingshot passing test with a threshold of 0.1 (almost any slipstream effect). Uniform sampling shows high variance while SSET with a slipstream (0.1) event and a "won" event has better variance but overall performance is not as good as the results with 0.7 threshold. Right: Average (and std dev) of winning margins (excluding losses) the last 100 epochs for each run.
cumulative first place finishes
Cumulative First Place Finishes (Threshold 0.9]
Avg. winning margin (w/o losses) in last 100 epochs [Threshold 0.9]
80
SSET(1)
SSET12)
SSET(1)
SSET(3)
SSET(4)
SSET(2)
60
SSE1(5)
SSET(3)
run(replica)
Unit2)
S4ET(4)
Unit3)
SSET(5)
40
Uni(1)
Uni(2)
20
Uni(3)
Uni(4)
Uni(5)
10 15
20
25
100
200
300
400
500
winning margin (meters)
epoch
Figure 16: Left: Cumulative wins evaluated every epochs in the slingshot passing test with threshold of 0.9 (only counting slipstream from very close opponent). In this case the difficulty of finding states with > 0.9 slipstream leads to higher variance, but not high as uniform sampling. Right: Average (and std dev) of winning margins (excluding losses) in the last 100 epochs for each run.
from 70 epochs to 505 epochs to start winning. By contrast all SSET runs learn to win consistently by epoch 110. In addition, the SSET runs seem to learn stronger passing skills, with an average winning distance (discarding runs where the agent lost) of 18.4 meters in the last 100 epochs compared to 14.4 meters for uniform sampling.
The behavior is somewhat sensitive to the choice of slipstream threshold. Figure 15 provides results in cases where the slipstream event was triggered by values greater than 0.1, which occurs very commonly when there is an opponent car ahead of the agent within a 60 meter range. Under these conditions, the event is not as informative as the > 0.7 event used carlier. Figure shows that under these conditions, SSET still has better average performance and less variance than uniform sampling, but its performance not as good
the results in Figure 14
18

---

Published in Transactions on Machine Learning Research (04/2023)
Cumulative Steps Crossed
Out of Bounds
Metric
300
SSET
Uni
cumulative steps on to off
(epochs 1000-2000)
250
5SE113)
S0FT(4)
Min/Avg/Max fraction policies left track
.040
.210
5SET(5)
.111
.253
200
.180
.305
Uni(3)
150
Uni(4)
Un)(5)
Avg = (a) best lap time (s) w/o disqualified policies
114.607
114.459
= ..12
= .12
100
50
Avg = (a)
114.618 = .15
114.496 = .22
best lap time (s) with disqualified policies
0
500
1000
1500
2000
epoch
Figure 17: Left: Cumulative times an agent went off-course in 3-lap evaluations performed every 5 epochs. Uniform sampling runs (red lines) display catastrophic forgetting, oscillating between steady laps and policies that take risks and go off course. SSET converges to policies that more consistently stay on course (flatter blue lines). Right: Summary statistics on converged behavior. The worst SSET run stays on course more than the best uniform one, with comparable lap times.
Figure 16 illustrates results when value greater than 0.9 was needed to trigger the event. This event requires significant exploration to trigger the event carly lcarning, since the agent must be very close the ahead to achieve such value. Under these conditions, the variance of SSET increases significantly the time it takes for the events to aid in learning is highly dependent on early exploration. However, SSET 's variance is still lower than the uniform sampling approach and SSET tends to win carlier and by a slightly larger margin.
Overall these results indicate that SSET is robust to events that happen frequently or (at the other extreme) are hard to find in early learning. SSET fares no worse than uniform sampling in these cases, though not as well as when using better chosen events.
7.2 Remembering to Stay On Course
We now present an experiment on maintaining multiple skills in a time-trial (solo car) setting on the full Lago Maggiore GP (Maggiore) track using a Porsche 911. The experimental details (see Section A.3) follow Wurman et al's except that we use only the time-trial reward components. The agent. is tasked with running fast laps as well as avoiding off-course penalties. As learning progresses, off-course events become very scarce compared to the roughly 1200 steps agent takes per lap. Consequently, learned behavior with monolithic ERB and uniform sampling (red lines in Figure 17 oscillates: policies may not go off course for several epochs, then "forget" the potential penalty and shift to policy that cuts corners, and the cycle repeats.
To retain consistent on-track behavior, we use SSET with a re-establish event that occurs an agent returns the track for 2 seconds after having left the course and use history length of seconds (roughly the half-life of the agent's horizon) to capture the full sub-trajectory of leaving and returning the course. We set n7 and to 1% and used an ERB of total capacity 10-million. Note this is an extension of the formal event spec definition since the event condition here is based a history of states, not just s'. The results of this approach (blue lines in Figure 17 show the oscillating behavior is replaced by consistent on-course laps, with 88.9% of SSET policies (up from 74.7% of uniform sampling policies) incurring no penalties after epoch 1000. Notably the worst off-course percentage for the SSET runs is still better than the best percentage with uniform sampling. The minimum (out of in each eval) lap times averaged across later epochs are also within 0.15 seconds. A second set of 5 runs using a 1s reestablish requirement with T 5s achieved virtually the same results (86.9% of policies course with similar lap times). Thus, in highly realistic
19

---

Published in Transactions on Machine Learning Research (04/2023)
driving simulator with deep neural network, SSET mitigates catastrophic forgetting and balances learning of multiple skills, echoing the results on MiniGrid domains in Sections 5.4 and 5.5
8 Recommendations on How to Pick Helpful Events
SSET requires domain knowledge to specify the table partitions and in this regard, is similar to designing potential functions for shaping rewards. In large domains like Mujoco (Section ( and GT (Section 7 there are already dense reward structures built into the canonical versions of the environments, so is difficult to add "yet another reward term" in meaningful way, but quite easy to use SSET and gain benefits from domain knowledge. As for the case of specifying domain knowledge for SSET, provide the following guidelines:
For users that don't know their domain well, one can use "goal" event (see mini-grid experiments in Section 5 in non-goal environment, use reward-threshold events (sce Mujoco experiments in Section 6 with a fairly long history and reap benefits, even without understanding the true subgoals.
Even the events are poorly chosen, the technique usually does only as badly as uniform sampling The cases where it would actually hinder performance are relatively patholog- ical (i.e.. using the majority of the buffer for incorrect events) and casily avoidable in practice by setting reasonable caps on the event lable sizes (say no more than 30% total as indicated in Figure 5 with table size experiments with bad events).
(see Figures g
Event Tables in SSET only require unsigned integer indices pointing to the data that is already stored in the main buffer. The additional memory footprint expands with the number of tables limes their sizes. The publicly available Reverb (Cassirer el al. 2021) package already implements this data structure efficiently.
Beyond these guidelines for using user-specified events, the topic of learning helpful set of events online is open, but rigring question. The difficulty in identilying events with no background knowledge is that by Definition 4 in the Appendix, events correspond to states that are most likely on optimal trajectories, so in the extreme case knowing the perfect set of events means knowing the optimal policy's state distribution. However, in cases where some model information is known, subgoal discovery methods could be used to propose events. One could also over-specify a large number of events and attempt to learn the weights (n and x) online, though the current work does not guarantee the convergence of such a meta-learner.
9 Conclusions and Future Work
This paper introduced Event Tables and SSET algorithm to improve the sample complexity and stability of off-policy RL. algorithms. The theoretical results quantify the potential speedups and lend guidance for choosing event conditions. Experiments in MiniGrid, standard RL benchmarks, and Gran Turismo Sport show the benefits of SSET over monolithic ERBs or other prioritization schemes. Furthermore, combining TD-error PER or reward shaping on top of SSET led to further improvements sample complexity and stability.
The current approach relies on domain experts or RL practitioners to designate event conditions. It may be possible to use subgoal discovery methods (Kulkarni et al. 2016 McGovern & Barto 2001 Kompella et all 2017) to automatically identify event conditions. Future studies may also consider dynamically changing the events or their proportions (1) and k) based on learning progress. For instance, an event like "driving forward" might help early in learning but could be supplanted later by an "overtake" table as the agent hones in on more complex skills. Such dynamic rules, which might be based on the insertion rates different tables, could be used to encode a curriculum that would directly change the complexion of mini- bini-batches, not just the data collection tasks.
20

---

Published in Transactions on Machine Learning Research (04/2023)
References
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schncider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in Newral Information Processing Systems, 2017.
Andrew G. Barto, Steven J. Bradtke, and Satinder P. Singh. Learning to act using real-time dy- namic programming. Artificial Intelligence, 72 1995. ISSN 0004-3702. doi: https://doi.
URL
0004370294000110
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.0/ 014000 2016.
Albin Cassirer, Gabriel Barth-Maron, Eugene Brevdo, Sabela Ramos, Toby Boyd, Thibault Sottiaux, and Manuel Kroiss. Reverb: A framework for experience replay. arXiv preprint arXiv:2102.047796 2021.
Maxime Chevalier Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for OpenAl gym.
hww.://www...mnommmmmmm/em/e///e wwwpee/wwwwwmmmmmmmmmeeeeeemeeee 2018.
Robert M Corless, Gaston Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth. On the lambert w function. Aduances in Computational Mathematics, 5(1):329 359, 1996.
Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuška. The importance of experience replay database composition in deep reinforcement learning. In Advances in Neural Information Processing Systems (NIPS- DRLWS), 2015.
Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuška. Improved deep reinforeement learning for robotics through distribution-based experience retention. In JEEE/RSJ International Conference on In- telligent Robots and Systems (IROS), pp. 3947-3952, 2016.
Yunshu Du, Garrett Warnell, Assefaw H. Gebremedhin, Peter Stone, and Matthew E. Taylor. Lucid dreaming for experience replay: refreshing past states with the current policy. Neural Computing and Applications, 34(3):1687-1712, 2022.
Florian Fuchs, Yunlong Song, Fliaa Kaufmann, Davide Scaramuzza, and Peter Dürr. Super-human perfor- mance in Gran Turismo Sport using deep reinforcement learning. IEEE Robotics and Automation Letters, 6(3):4257-4264, 2021.
doi: 10.1109 11109/LR..20 W...A.2021.306..2 2061.3064224.
lan J. Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investigation of catastrophic forgeting in gradientbased neural networks. International Conference on Learning Representations (ICLR), 2014.
Marck Grzes. Reward shaping in episodic reinforcement learning. In International Conference on Au- tonomous Agents and Multiagent Systems (AAMAS), 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-poliey maximum entropy deep reinforcement learning with stochastic actor. In International conference machine learning, pp. 1861-1870, 2018.
Zhang- Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. In International Conference on Learning Representations (ICLR), 2021.
Wanming Huang, Richard Yi Da Xu, and Ian Oppermann. Efficient diversified mini-batch selection using variable high-layer features. In Asian Conference on Machine Learning (ACML), 2019.
David Iscle and Akansel Cosgun. Selective experience replay for lifelong learning. AAAI Conference on Arlificial Intelligence, 2018.
21

---

Published in Transactions on Machine Learning Research (04/2023)
Boris Ivanovic, James Harrison, Apoorva Sharma, Mo Chen, and Marco Pavone. Bare: Backward reacha- bility curriculum for robotic reinforcement learning. In IEEE International Conference on Robolics and Automation (ICRA), 2019.
Thommen George Karimpanal and Roland Bouffanais. Experience replay using transition sequences. Fron- tiers in Neurorobotics, 12:32, 2018.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barrkka-BBwiiskaa,, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114((3):3521-933) 3326,, 2017. doi: 10.1073/pnas.1111 1611835114
URL https: /// http://wwwppppa....aa.aa wttg/////as///../..oo/
Varun Raj Kompella, Marijn Stollenga, Matthew Luciw, and Juergen Schmidhuber. Continual curiosity-
driven skill acquisition from high-dimensional video inputs for humanoid robots. Artificial Intelligence, 247:313-335, 2017.
Tejas D Kulkarni, Ardavan Saeedi, Simanta Gautam, and Samuel J Gershman, Deep successor reinforcement learning. arXiv preprint 1606: 02396, 2016.
Donghwan Lee and Niao He. Periodic Q-learning. In Learning for Dynamics and Control, 2020.
Su Young Lee, Choi Sungik, and Sae-You Young Chung, Sample-efficient deep reinforcement learning via episodic backward update. In Advances in Newral Information Processing Systems, 2019.
Ziniu Li, Tian Xu, and Yang Yu. A note target Q-learning for solving finite MDPs with generative oracle. arXiv preprint 2r: 2022.
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching, Machine Learning, 8(3-4):293-33) 321,, May 1992.
Xingyu Lin, Harjatin Baweja, George Kantor, and David Held. Adaptive auxiliary task weighting for rein- forcement learning. In Advances in Neural Information Processing Systems, 2019.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. In Advances in neural information processing systems, 2021.
A Rupam Mahmood, Hado P Van Hasselt, and Richard S Sutton. Weighted importance sampling for off- policy learning with linear function approximation. In Advances in Neural Information Processing Systems, 2014.
Amy McGovern and Andrew G Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In International Conference on Machine Learning (ICMT), 2001.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement lcarning. arXie preprint arXin:1312.5602, 2013.
Karthik Narasimhan, Tejas D Kulkarni, and Regina Barzilay. Language understanding for textbased games using deep reinforcement learning. In Conference on Empirical Methods in Natural Language Processing, 2015.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference Machine Learning (ICML), 1999.
Youngmin Oh, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Model-augmented prioritized experience replay. In International Conference on Learning Representations (ICLR), 2021.
Martin L Puterman. Markow decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
22

---

Published in Transactions on Machine Learning Research (04/2023)
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. In Advances in Neural Information Processing Systems, 2019. URL https://
Paceeedc--Pppp.pppppp pdff
Tom Schaul, John Quan, Toannis Antonoglou, and David Silver. Prioritized experience replay. In Interna-
tional Conference Learning Representations (ICLR), 2016.
Anil Sharma, Mayank K Pal, Saket Anand, and Sanjit K Kaul. Stratified sampling based experience replay for efficient camera selection decisions. In IEEE International Conference on Multimedia Big Data (BigMM), 2020.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Do- minik Grewe, John Nham, Nal Kalchbrenner, Πlya Sutskever, Timothy Lillicrap, Madclcine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, (29(7787) 489, january 2016.
Yunlong Song, HaoChih Lin, Elia Kaufmann, Peter Dürr, and Davide Scaramuzza. Autonomous Overtaking Gran Turismo Sport Using Curriculum Reinforcement Learning. In TEEE International Conference on Robotics and Automation (ICRA), 2021.
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, 1999.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. In
AAAI Conference on Artificial Intelligence, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279-29) 1992.
Peter R. Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, Leilani Gilpin, Piyush Khan- delwal, Varun Kompella, HaoChih Lin, Patrick MacAlpine, Declan Oller, Takuma Seno, Craig Sherstan, Michael D. Thomure, Houmchr Aghabozorgi, Leon Barrett, Rory Douglas, Dion Whitehead, Peter Dürr, Peter Stone, Michael Spranger, and Hiroaki Kitano. Outracing champion Gran Turismo drivers with deep reinforcement learning. Nature, 602:223 228, 2022.
Haiyan Yin and Sinno Jialin Pan. Knowledge transfer for deep reinforcement learning with hierarchical experience replay. In AAAT Conference Artificial Intelligence, 2017.
Daochen Zha, Kwei- Kwei-Herng Lai, Kaixiong Zhou, and Xia Hu. Experience replay optimization. International Joint Conference on Artificial Intelligence (IJCAT), 2019.
23

---

Published in Transactions on Machine Learning Research (04/2023)
A Appendix
A.1 Theoretical Analysis
In this section we prove sufficient conditions for the improvement of convergence speed using Event Tables and SSET. Specifically, we show that the more correlated events are with optimal behavior, the larger the expected improvement. To ground the analysis and make use of existing results, use labular Q-learning with a target function. We start from known fniie-timm convergence results in this setting (Lee & He 2020; Li et al. 2022). Specifically, Theorem from Li ct al. (Li ct al., 2022) (a refined version of Theorem from Lee et al. (Lee & He. 2020)) computes the lower bound of sample complexity (NV for learning an s-optimal solution using an iterative tabular Q-learning algorithm with target. networks (Algorithm 2]. We show that the lower bound of the sample complexity for achieving s-optimal behavior is reduced by using event tables for sampling (Theorem D
The steps taken from the know result in the uniform sampling case to the new theorem are as follows. We define the state probability distribution (density) following a given policy to a finite horizon from an initial state and use that to define the state density disparity to the optimal policy (Definitions 2 We then formally define event conditions (Definition 4 on the states with low optimal-policy disparity or final states of the optimal policy. We extend this dcfinition to event sections and their corresponding tables that include sulficient history to (on expectation) reach back to a previous event or initial state (Definitions 5 We then quantify the over-sampling of experience in the event tables (Lemma I and derive the convergence rate (Prop. 3) and bias correction procedure (Lemma 21 Finally, we show that the resulting convergence bound is an improvement over uniform sampling (Theorem
Algorithm 2: TARGET Q-LEARNING USING AN EXPERIENCE REPLAY BUFFER.
//input: outer loop iteration number K, inner loop iteration number 4, initialization Qo. step-sizes de.
//output: QK
for k- = 0 to K - do
// outer loop
Qa,0 + Qs
for i= 0 to I - do
// inner loop
4
(s,a,r,8') ~ B // randomly sample a transition
Qk.++1(s,a) = Qu.(ss a) + ar(r + max. Qu(s', d') Qu.(ss,)) // update end
Qu+1 + Qu, // refresh target
end
First, we provide a general overview of the base algorithm and the existing results.
Assumptions: Throughout the analysis we consider a finite discrete episodic MDP M (S, (SP.,R,, where S and A are finite and discrete state and action spaces, is the state transition probability and R a bounded reward function, s.t. r(s, a) E [0, 1]. V(s, S A, T is the length of each episode and E (0, 1) is the discount factor, We assume for simplicity in notation that any terminal state traps the agent until time step T. We assume that the agent takes actions using fixed stochastic behavior policy T² : :S A- (0. 1], such that it can visit every state and execute every action with a non-zero probability within the T time-step horizon. We denote x* S A + [0, 1] to be an optimal policy the MDP (Puterman] 2014), such that its state-action value function is optimal Q (s, a) = max, (s,(ss),, V(s,a) E S x A. Again for simplicity notation, we assume that the event-tables are sampled uniformly with total sampling probability denoted by 77 = E m=(= n/n) (see Alg. D. The sampling probability of the default-table is 7/p- 1 n)
24

---

Published in Transactions on Machine Learning Research (04/2023)
Let T: : RIIAI | define the Bellman operator
())( = (gll(a)))) (r(s.a) + ymax Qu(s',a)).
Q-learning using target-network Qk and an experience replay buffer B can be viewed as minimizing the following loss function
E (((s,a) 7max a)( Q(s, a)) )
min 1Q: QERISIIA
(1)
(
For a given buffer generated using the fixed behavior policy x², we define constants (following the notation used (eee He 2020 et al. 2022
CB = min a((s,,,;))~ B)
sES,aEA
LB = max P((8, a. B)
Here, og and Lag denote the minimum and the maximum probability that a state-action pair (8, () sampled from the buffer. From our assumptions, CB
Carrying out N steps of SGD optimizing Eq. we get approximation of TQu with certain error bound E [1|Qx+1 TQ II] S Ek-1, which then accumulates across outer iterations over k.
Proposition 1. (Theorem [T et al., 2022) Consider MDP with Qo 0, cg > 0, 0₁ x where a = 2/c8 and X (13 LB)/ (2cg). The minimam number of samples required to achieve an e-optimal solution [|[[QK [=11=0] S e using Algorithm given by
NB.
832n²
LB 3
log
(1- 7)-
(1
7)
C
We show SSET can decrease this bound when the events correlated with optimal policy and histories are sufficiently long. To quantify these conditions, use the following definitions of optimal trajectories and their state densities induced by various policies.
Definition 1. Trajectory: We define trajectory IT, of the MDP M temporal sequence of transition tuples
m %i.og
{Sk, ak, Pk: Sk+1) Sk+1 P(-|sk, an ((((sk)), Th R R5K.8411 Vk [ř,j 11)}
For simplicity, 15 denotes the length or the number of transitions of the trajectory.
Definition 2. State Density: We define p= S [0, 1] as the state probability distribution following any policy n for the MDP with the initial state so over finile lime horizon K
50 K (8) (s)=
Σ P(8k = 80), k=0
(2)
C enforces the constraint 1T s 1 to make s0. a probability distribution, where s bo (s1).((s.,..,,)......... 7... (sN))) [s E N
Definition 3. State Density Disparity from Optimal: We define p ~T.50. K. :S [-1,1] the difference in the state density following any policy compared to shiimal-policy n" for the MDP with the initial state 8o over finite time horizon. K
10.880KK K.
=s)=p" so 80. (8) R.o.
(3)
25

---

Published in Transactions on Machine Learning Research (04/2023)
We now formally define event condition : S {0, 1), which is the core concept of our SSET algorithm. An event occurs when an agent enters a state that satisfies the event condition, which implicitly defines a set of event states: [. Intuitively, good event conditions should be aligned with the optimal policy and also act as waypoints linking imitial and final states visited by the optimal policy. Therefore, final states visited by the optimal policy should also satisly at least one event condition.
{0,1},
Definition 4. Event condition: Let I denote the initial state distribution of the episodic MDP with the episode length T. For a given threshold E (0,1), we define a collection of event sets S = {S-1 Swh), }. s.t. Vs, S 3s, E IIS where the following conditions are true:
Nat
either
P
(s:)
2 A (1
(4) (5)
or
I SEI
= T
We define event condition S (0, 1J. Vi E [1, s.t. wi(s) = [.E81))
Intuitively Condition (4) covers states that significantly (based on μ³) more likely under the optimal policy than under T². Condition 55) covers terminal states visited by the optimal policy in case they are not satisfied under Condition 4 Note, the definition above could cover a large amount of the state space in highly stochastic domains. Therefore, Theorem [ filters the set further to focus on higher probability states without significant degradation to the overall sample complexity.
For simplicity in the notation used in our proofs, we denote an event section Edr as a set of states whose state density disparity from the optimal policy is less than (or equal to) A. Intuitively, these are the states from which the agent can easily reach the event states.
Definition 5. Event Section: We define an event section Exi
8 cm=$f
{s sup s'ES
whth e' (si), Vss E SWi } 1
E }
Proposition 2. For a given n1 38 s.l. all initial states of the MDP I, the event states Swn, and the optimal terminal states {s | TT} belong to at least one event section EH.
Proof. Let us first consider the case where for given μ,, Condition does not hold for any E S. From Def. 1 S" contains only a single event-set that includes all the optimal terminal states Swherm {s E = T)). Therefore, from Def. 5. all initial states belong to the event section Emeam, and hence the result is true for this case.
Now for the case where there are non-zero number of event-sets that satisfy Condition 4 it follows that the event states belong to either the event section where Condition 44 is true or the terminal @ueeem J
From the definition of events, we can define an event table that stores these experiences that lead to them.
Definition Event Table: An event table B% for event spec v; (w,, m,), denotes an experience replay buffer, which is a multiset (a set with repeated elements) of transitions from trajectories of given mazimum length s.t.
B "--UP (((ssan7))) E 81. I S Vo E S )
pr
(6)
Using the above definitions, we can now analyze the likelihood of sampling any particular state from an ERB that contains both event tables and a default table Dd based on fixed sampling probabilities of the event tables (as used in Algorithm The following lemma quantifies the over-sampling of experiences in the event tables.
Lemma Let B"
Bd denote the wnion events table and B denote the defoult table that contains vie(l.n]
all the transitions collected following a fixed behavior policy n². 2 B U B denotes weighted sampling
26

---

Published in Transactions on Machine Learning Research (04/2023)
00 < nj < 1) of a transition tuple (8,)))))) between the event and the default tables. For any event-spec Vs+
if Ti S (1 1))
(m 1)mp' then P(s Be U 2 (1 - 17 P(s ~ B)). v(8,),))) E B m E Z
Proof. Expanding the weighted sampling probability, we have
P(s 2 B" Bd) = mp Ps B*) + (1
P(s ~ B
nP(s~~ ~ B*) + (1 - P(8~~ B0) P(s ~ B3)
P(s ~ 15)
+
(1 m)m
(1 -7)m
P(s ~ Bd) (1 17)
P(s ~ B²))
+ (1 - 11) m P(s ~ B²)
1/11 17)
Ck=n( (1 11)*
-1
P(s ~ B²)
P(s B²))
+ (1 - 1)) P(s BB
7)
21
P(s ~ B²)
m + 1
P(s 88) + (1 -nn) 1 P(s B²) (:: (1 17) < 1)
(1 1)
(B")))
P( = =8|s7; = ,th x0) P(ST. = (B m + m)
P(sr; = 8 18%)
Def.
k=U
+ (1 -n1 1) " P(s B²),
g E Str
(7)
5% contains only trajectories of length S that all lead to thh Sw: Therefore P(st. 8 Given the event-table sampling algorithm described Sec. (with the assumption that table uniformly sampled), we have P(st, = s01(B") = P(w; ~ tui, Vis) sht (8)
For the event section En:
from Def. and p= .. (s*)) s 1, therefore P(s = 5h: BB) I p. Substituting in Eq. 7 we get
P(s U B 2 1)
P( k =187: = 80r ; 2
m 1
m p(s B²) + (1 -n))
(1 - 77) 11
nti
k=
1
m + 1
(1 7) th P(s B²)
(1 17 /
noT
Typically, the threshold μ is very small as the state density following the behavior policy drops exponentially with the number of forward time steps. With small values of jr, next show that > 1, thereby quantifying the over-sampling of experiences in positive powers of [T-1)-
Proposition 3. m is asymptotically converyent to - Im((T)) In In(r4))))) + +o() as μ + 0.
Proof. Rearranging the condition in Lemma 1 for equality
(m++1) hal1))l(11))) (1 (1-10 (1-n)nTiH In(1 1)
(m + 1) In(11 n
Setting a = 1/(1 (), b /mult,/aaa x = (m + 1) and y = (x the equation reduces to yeV solution to this equation is the Lambert W function Wo since lnfe > 0
Inc.
The
b
1 In(a)
(aln(a)
nT: ) 1.
Wo
(8)
27

---

Published in Transactions on Machine Learning Research (04/2023)
Wo(x)) is asymptotic to In In In + o(1) for large values of (Corless et al. 1996 With small values of H, we get
m In(T:))))) In (n(pp) + o(1)
(9)
Sampling using event-tables may introduce a bias as it can change the expected value of the stochastic Bellman operator TQx(s, a) = (g.r)(s))) ((ss,) + ymax (x(s',a") for the (s, pair whose next state
has finite probability to either belong the event-tables or not. We can correct this bias by computing weights for weighted importance sampling (Mahmood ct al., 2014) similarly to PER (Schaul et al. 2016).
Lemma 2. Bias introduced by the weighted sampling 2 8" B between the event and the defaull tables is given by
17 E P((s,a,,, S'ES
$ B31 s,a),
w(s a)
if (8,a,,,,) B"
otherwise.
Proof. Event tables construction (sce Algorithm prioritizes transitions that are in either of the event buffers over the ones that are out. Given an (s,a) pair, the transitions that are not present in any of the event tables are sampled from the default table with probability of 1 n. Therefore, the remainder n EVES P(s' & B s, a) is adjusted among the probabilities of transitions in the event-buffers. The correction weight that is needed is n) Eees P(s' B"| s.a). For the transitions that not in the event buffers, only scaled correction of (1 11) is required.
Now that have quantified the oversampling and bias-corrections of event histories, state main theorem showing that with sulficient history and events that are correlated with optimal behavior, the convergence speed of Q-learning to an optimal policy is improved over the monolithic ERB (B = B") sample complexity (NB.K).
Theorem 1. Let S denote the set of states s.t. the sampled optimal trajectories starting from those states, are contained in the combined event- buffer with probability greater than (0, 1]
s = (s P(rs 3,8 CB") N p}.
(1 - (1- then
Under the conditions of Prop.
1 and if Tveel1,n) 1
(m 1)mp²
P PNBBUBB (11-)) 2)2 2 P. As VsE z
Proof. Let M = (S5 (SS,A,,,R)) be a reduced MDP M with the initial, event and terminal states in Sf (Prop. 2 With the bias correction applied from Lemma
2 n To.Mo (s) = π T (s), Vs e Sf, With max P((s,a,;,) 1 U as constants the sES! ,aEA
BB = min p((s,a,,,) ~ B" U'))) 3B) and I uB
.ES!,aEA
result the theorem then follows from using Lemma in Prop. for MDP S using event-tables for experience replay.
Remark 1. Applying the results of Theorem 1 and Lemma I in the loss function of Q-leorning (Eq. D. the speed-up (1 1)) 22 compounds across multiple outer iterations of target Q-learning (Alg. [). Therefore, the transitions that are not in the event buffers are also benefited in expectation, countering the lower sampling rate of n)
28

---

Published in Transactions on Machine Learning Research (04/2023)
A.2 Learning Parameters and Resources Used in MiniGrid and Continuous Control Experiments
Table lists the parameters used in MiniGrid experiments. Event conditions are true when the agent interacts with an object, the goal, or crosses between rooms. History lengths are shorter in the obstacle course where the events are denser (since there are more objects), but we use a larger buffer there to accommodate the more diverse skills and larger number of event tables. For all the MiniGrid experiments, we used two asynchronous rollout workers each with 1.5 CPUs and 2GB memory to collect and transmit experience data replay buffer efficiently implemented using Reverb (Cassirer al. (021]. The training was conducted using virtual CPUs and 3 GB of memory rale of 40 training steps per sec. For the continuous control tasks
and MuJoCo domains), used single rollout worker with 1 CPU and 2GB memory, and the training was conducted asynchronously using 7.7 CPUs with 8GB of memory. Table lists all the algorithm parameters used for these benchmark experiments. Parameters that are not related to SSET are either set to values that are typically used in the literature (e.g. (Hong et al. 2021 (discount factor, stale network refresh rate, max buffer capacity, batch size) or set based on parameter tuning to get the best performance of the basclines (learning-rates, TD-priority exponent, architectures, (esilon-gredyy)
Table 1:
Parameters in the MiniGrid domain
Parameter
Three Room Grid World
Obstacle Course
at-spike, al-lava, at-gap, pickup-key, al-door, done
Event conditions (wz)
at-gap, done
Event history length (r)
200
50
Default: 0.5, at-spike: 0.1, at-lava: 0.0625, at-gap: 0.0625, pickup-key: 0.0625, at-door: 0.1125, done: 0.1
Event sampling probahili-
Default: 0.5, at-gap: 0.2, done: 0.3
ties (n.)
Max bulfer capacity
20000
100000
Value function networks
hidden layer ReLU units
hidden layers of 256 ReLU units each
Learning rate
1o-3
5c-4
Table capacity sizes (Nx)
max buffer capacity m
batch-size
epsilon-greedy (e)
0.3
TD-Priority exponent
0.65
Stale network refresh rate
0.01
Discount factor
0.99
A.3 Appendix: Details of Gran Turismo Experiments
The Gran Turismo TM (GT) Sport lhttps://wwr htapp:g///ggggnnn-i.. turismoo htt.riism.coomus////oo. racing simulator for PlayStation" Tx allows an agent race automobiles with highly realistic dynamics. The environment, was recently used in (Wurman et al., 2022) to demonstrate an RI system that learned to beat human c-Sports champions 3 different tracks in 4v4 (4 humans and 4 RL agent) competitions. Our experiments investigate smaller scenarios, either sections of track or without opponents, in order to isolate the specific effects of Event Tables Almost all of the parameters of the representation and learning algorithms are the same as those reported in |Wurman et al. 2022) for the selected track / car combinations. We provide summary of these settings below and note the small deviations for our particular scenarios.
slingshot passing scenario on 1700m. straightaway at the Circuit de la Sarthe (Sarthe) track, using a Red Bull X2019 Competition race car, similar Formula 1 vehicle (see Figure 18 Training is performed in one-on-one race against built-in AT opponent from the game with
The first experiment investigated
29

---

Published in Transactions on Machine Learning Research (04/2023)
Table 2: Parameters in the Continuous Control Benchmark Tasks
Parameter
LunarLanderContinouus
MuJoCo
Salient reward thresholds
Half-Cheetal: (r (r> r 12, 16)
Event conditions (we)
land-between- (If), land-near-middle (Im)
Hopper: (r 2.5, r 3, 3.5)
Walker2D: (r> r> 6,
Humanoid: (r (,>,r
Default: 0.6,
Half-Cheetah: (ns: 0.2, ri2: 0.1, r16: 0.1)
Event sampling probabili- (m:
Default: 0.7, If: 0.1, Im: 0.2
Hopper: (r2.3: 0.2, rar 0.1, ra.s: 0.1)
Walker2D: (ras 0.2, 0.1, ret 0.05, 0.05)
Humanoid: (ra: 0.2, P7: 0.1, rio: 0.1)
Max buffer capacity
20000
1000000
batch-size
32
256
Learning rates
Actor: 0.0003, Critic: 0.0003
SAC networks
2 hidden layer of 256 ReLU units each, Gaussian Policy
Half CalffCheetahh -6.0 Hopper: -3.0
Target entropy (optimized entropy)
-2.0
Walker2D: -6.0
Humanoid: 117.0
Table capacity sizes (Na)
max buffer capacity
Event history length (r)
200
Stale network refresh rate
0.005
Discount factor
0.99
the RL agent always starting behind. To succeed, the RL agent needs use the opponent's slipstream accelerate beyond its top speed in open air and use the added momentum "slingshot" past the opponent and hold it off to the end of the section. The second setting is time trial competition the full Lago Maggiore GP (Maggiore) track using Porsche 911 from the FIA GT3 class of cars (see Figure 19 There the experiment focuses on driving fast lap times without going off course.
We used the same state features as the prior work in GT. State features include information about the agent's velocity, acceleration, tire slip, most recent. actions (steering, throttle, and brake), position on the track, and the "course points" outlining the shape the upcoming track. Indicator features capture collisions with the walls or other leaving the track). A [0, slipstream feature provided by the game measures the draft from car(s) ahead is also passed in as state feature. Opponent cars were represented by two lists, one for opponents ahead, and one for opponents behind, with opponents masked out if they are more than 20 meters behind or 75 m. ahead. Each opponent in view was represented with their agent-centered relative position, velocity, and acceleration. The agent. controlled the car by sending actions for the the steering wheel and combined phrottle/brake dimension.
as well as going off course by more than two tires (the game's definition of
The previous work with Gran Turismo used different reward functions different tracks and different scenarios (such as Time Trial racing and head competition). We used the reward functions from their investigation that best fit our scenarios. In our slingshot passing tests at the Sarthe track, we used the reward components previously used in 4v4 compelitive racing. These components and their weights are specified in Table 3 and included a reward for forward progress, penalties for hitting the wall, and a penalty for going off course that was linearly proportional the agent's velocity. A passing reward provided reward for approaching an opponent from behind or pulling away from ahead (and penalized the opposites). For car collisions, three different components used to penalize different aspects of collisions, including hitting
30

---

Published in Transactions on Machine Learning Research (04/2023)
166
6
Figure 18: The section of the Sarthe track used for slingshot passing and a screenshot from the experiment.
12.5
DESION
44
Figure 19: The Maggiore track used for Time Trial training and screenshot from the experiment.
cars from behind, at-fault collisions, and a penalty for any collision at all. Because the Slingshot experiment locused on a section without difficult curves we did not use the "mistake learning" spin-out replays that prior work used on the Sarthe track.
For the off-course experiments at Maggiore, we used the reward components from previous work at that track but dropped the reward terms pertaining to other cars (such collision passing). These components
31

---

Published in Transactions on Machine Learning Research (04/2023)
Table 3: Reward components used in the two experiments in the paper, slingshot passing and time trial training. The reward weights are all the same as (Wurman et al. 2022/3 's results but the car collision and passing components are dropped in the time trial scenario.
Reward
weight in slingshot (Sarthe)
weight in
Component
off-course TT (Maggiore)
Progress
1
1
Off-course"
0
0.01
cif-course-linear
5
0
wall penalty
0.1
0.1
tire slip (per tire)
0
0.25
passing bonus
0.5
0
car collision (any)
4
0
car collision (rear)
0.1
0
car collision (unsportsmanlikk)
5
0
include a wheel-slip penalty and an off-course penalty based on the square of the agent's velocity, which replaces the linear off-course penalty from Sarthe.
The base RL algorithm and all of its parameters were kept the same as Wurman et al's experiments. The base RL algorithm was Quantile Regression Soft Actor Critic (QR-SAC), a version of SAC where the critic networks represent the quantiles of the value function rather than just their mcan. The neural networks used for value function and policy networks were all feed-forward networks with 2048 ReLU units in each of 4 hidden layers. dini-batches of size 1024 were used with 6000 pulled from an ERB with total capacity k)) of 2.5 million (slingshot test on 1.7 kilometer segment) or 10 million (time trial test on a nearly 6 kilometer track). Each table was blocked from sampling until it had at least 1024 experiences in the time trial test or 5000 experience tuples in the slingshot test (avoiding over-fitting) The Adam optimizer was used to optimize the weights with learning rates of 5 x 10-5 for the Q-networks and 2.5 10- for the policy network. A discount factor of 0.9896 was used and the SAC entropy temperature controlling exploration was 0.01. Dropout (0.1) was used when learning the policy network.
per epoch. These samples were
Following the hardware setup from the prior work, both of our experiments used 21 PlayStations in parallel during training with of those PlayStations typically devoted to evaluations. In the slingshot experiments on small segment of the track, each PlayStation had only one agent racing against an opponent. The competitor in this scenario was the game's own built-in AI with randomization controlling the spacing of the agents (uniformly drawn in [10,40] meters) and lateral spacing. The learning agent always starting behind the opponent. To provide extra diversity, the Balance of Power on the opponent, that is its horsepower and weight, were randomly increased or decreased up 25% in each training episode. Training episodes were capped at 60 seconds although less than 25 seconds were usually sufficient to complete the section (also ending the training episode).
For the time-trial training scenario at Maggiore, no opponents were needed but we utilized the parallel collection strategy from (Fuchs et al., 2021 Wurman et al.) 2022) to spawn 20 different agents uniformly around the track and collect data from each of these, yielding roughly 400 experiences per time step. Training episodes in these scenarios lasted 150 seconds. Notice that in both experiments there is only one training scenario with some minor randomization on exact locations, so we did not need to employ task sampling scheme like the one needed to master the full racing scenario.
Using the same setup as prior work, agents on the PlayStations were controlled by rollout workers using two virtual CPUs and 3.3 GB of memory at a frequency of 10Hz. Policies were sent from the trainer to the rollout workers at the beginning of each training episode and kept static until the next episode. Actions and obscrvations were sent between the rollout worker and the PlayStation through a restricted APT. Experience was periodically streamed back to trainer and stored in an ERB implemented via Reverb (Casssree et al. 2021 ). Training was conducted using one NVIDIA V100 half of an NVIDIA A100, ~ virtual CPUs and 55 GB of RAM.
32


Reviews:
[{"review_id": "X88r5PZ24g", "reviewer": "Reviewer_Gpmo", "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 approach presented in the paper paper is sound and, as far as I know, novel and well-positioned with respect to existing work.\n- The method seems to be easily implementable and potentially very helpful for applying reinforcement learning to any domain in which identifying successful events is easy but designing a reward function is harder.\n- The empirical analysis of the presented method is quite thorough and enjoyable. As an example, I particularly liked the analysis in Section 5.6, showing in an easily understandable example the impact of the decisions around event selection.\n\nWeaknesses:\n- I am concerned about the lack of error bands on some of the plots concerning the empirical evaluation of the method (e.g., Figure 7-8-9), especially given the noisy nature of the episode return curves. \n- More generally, overlapping error bands in other plots (e.g., Figure 11) undermine the ability to understand whether SSET performs better than other prioritization approaches in a statistically significant way. \n- One drawback of the proposed method is its reliance on manually-selected events. Despite there is already some discussion on the robustness of the method to bad event selection, I think the paper would benefit from extended discussion on what would the difficulties be in designing a system that automatically learns how to identify such events. ", "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 proposes the use of event tables, special replay buffers filled with experience related to particular events happening in the environment, to speed up training in reinforcement learning algorithms. The paper presents SSET, an algorithm based on the idea of executing stratified sampling from the event tables, as well as a theoretical and empirical analysis of this algorithm in comparison to other off-policy approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Results, especially in continuous control, would be more convincing if using an evaluation that allows to draw statistically meaningful conclusions about the performance of the presented algorithm compared to other baselines.\nI recommend the authors to look into the evaluation procedures proposed by \"Deep Reinforcement Learning at the Edge of the Statistical Precipice\" (Agarwal et al., 2021), which are directly applicable to similar domains such as the ones from DeepMind Control Suite (it just requires normalized returns for meaningful aggregation).", "broader_impact_concerns": "I have no particular concerns about the broader impact of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YUZ5nlE8RK", "reviewer": "Reviewer_j8j6", "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- Intuitive method for utilizing event states when they are available\n- Extensive experiments on a range of tasks and domains\n\nWeaknesses\n- Inconsistency in plots for reporting results statistics\n- Lack of analyss on the effect of additionally introduced hyperparameters (e.g., Event history length ($\\tau$), Event sampling probabilities ($\\eta_{i}$))\n- Lack of statistical significance over baselines on MiniGrid domain\n\nOverall\n- This paper proposes an intuitive method for utilizing event states, but its focus on MiniGrid experiments where results are not significant and the lack of analysis on additionally introduced hyperparameters make the claims in the paper not convincing enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 presents Stratified Sampling from Event Tables (SSET) that introduces multiple \"event tables\" which are separate replay buffers that contains trajectory segments containing a human-defined \"event\" states and does stratified sampling from them. A major difference to previous works is that (i) SSET stores histories of states that lead to specific events instead of storing each state and (ii) SSET can utilize any state other than initial state for partitioning the buffer.  Experiments evaluate SSET on various domains, including GridWorld, Gym benchmark tasks, and a simulated racing game.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My suggested changes are mostly focused on experiments:\n- Investigation into the importance of history length ($\\tau$) is required on multiple domains as it's currently reported when the event is not intermediate (Figure 7). From the current experimental results, it's not clear whether it's important or not.\n- Invesitgation into the sensitivity to event sampling probabilities ($\\eta_{i}$) is required as it's a quite complex additional hyperparameter for SSET. Is the method robust to naively chosen set of sampling probabilities, or carefully designed probabilities?\n- On dense reward benchmarks, it's not clear whether the performance gain comes from over-sampling of high-rewarding states or SSET. What would be the performance of sampling minibatches with priorities correlated reward scales?\n- Plots should be consistent by reporting both mean and standard deviations. Currently some figures report standard deviations but some are not. Moreover, why does Figure 12 report the std over each run but not across multiple runs? It could help understanding the significance of results.\n- Performance of SSET is not significant over baselines in MiniGrid domain as confidence intervals overlap with each other, making the claims not convincing enough. Conducting more supporting experiments on more complex domains (e.g., Car Racing environments) could help.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "V3i5NzGOaP", "reviewer": "Reviewer_CmcH", "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+ This is a great paper! I like the idea of using events for sampling from the replay and this paper convincingly shows how using them for replay sampling significantly improves the training of RL agents in many non-trivial MDPs in contrast to uniform and prioritized sampling. The claims of this helping are strongly backed up.\n+ The paper is well-written and clearly communicates all of the key ideas, insights, and recommendations. I especially like section 8 with recommendations on picking helpful events\n+ The concept of events in MDPs seems like a very reasonable way of integrating more domain knowledge into MDP solutions.\n\nWeaknesses\n+ While events are nice way of integrating more knowledge into MDPs, they require manually specifying more information about how the agent should explore and learn an optimal policy. This gives the event-driven settings a slight advantage in comparison to the baselines that are not able to use this information.", "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 investigates the best way of sampling experience replay for learning reinforcement learning agents in contrast to the standard methods of uniform or prioritized sampling from the replay buffer. They propose to define \"events\" that characterize behaviors in MDPs and use those to help guide how the replay sampling should be done (alg 1) and show extensive results improving upon the standard environments, including MiniGrid, Mujoco, Lunar Lander, and a Gran Turismo Sport racing simulator.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I only have one question: are there other ways of integrating events than just in how the replay buffer is sampled? it seems like they could be used to create a curriculum or other kind of reward augmentation", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is easy to read and the idea useful. The paper can be accepted mostly as is. 

However, I have one very minor request (two sentences at most). I would ask for the camera ready version that you give a couple of sentences of explanation for the choice of hyperparameters in Section A.2. In A.3, you justify that most hyperparameters were set to the previous implementation. But for Section A.2, there is no such explanation. Tuning hyperparameters for your approach can cause misleading results. I am giving the benefit of the doubt that you have not done so here, but you should explain to the reader where these came from (e.g., why epsilon = 0.3?). 
Decision: Accept (poster)