On Lottery Tickets and Minimal Task Representations in Deep Reinforcement Learning
Authors: Marc Vischer
Robert Tjarko Lange
Henning Sprekeler
Venue: ICLR 2022 Spotlight (2022)
Keywords: Reinforcement Learning
Sparsity
Pruning
Lottery Ticket Hypothesis

Abstract: The lottery ticket hypothesis questions the role of overparameterization in supervised deep learning. But how is the performance of winning lottery tickets affected by the distributional shift inherent to reinforcement learning problems? In this work, we address this question by comparing sparse agents who have to address the non-stationarity of the exploration-exploitation problem with supervised agents trained to imitate an expert. We show that feed-forward networks trained with behavioural cloning compared to reinforcement learning can be pruned to higher levels of sparsity without performance degradation. This suggests that in order to solve the RL-specific distributional shift agents require more degrees of freedom. Using a set of carefully designed baseline conditions, we find that the majority of the lottery ticket effect in both learning paradigms can be attributed to the identified mask rather than the weight initialization. The input layer mask selectively prunes entire input dimensions that turn out to be irrelevant for the task at hand. At a moderate level of sparsity the mask identified by iterative magnitude pruning yields minimal task-relevant representations, i.e., an interpretable inductive bias. Finally, we propose a simple initialization rescaling which promotes the robust identification of sparse task representations in low-dimensional control tasks.

Published as a conference paper at ICLR 2022
ON LOTTERY TICKETS AND MINIMAL TASK REPRE- SENTATIONS IN DEEP REINFORCEMENT LEARNING
Mare Vischer
Robert Tjarko Lange* Technical University Berlin Science of Intelligence
Henning Sprekeler
Technical University Berlin
Technical University Berlin Science of Intelligence
ABSTRACT
The lottery ticket hypothesis questions the role of overparameterization in super- vised deep learning. But how is the performance of winning lottery tickets af- fected by the distributional shift inherent to reinforcement learning problems? this work, we address this question by comparing sparse agents who have ad- dress the non-stationarity of the exploration-exploitttio problem with supervised agents trained imitate an expert. We show that feed-forward networks trained with behavioural cloning compared to reinforcement learning can be pruned to higher levels of sparsity without performance degradation. This suggests that in order to solve the RL problem agents require more degrees of freedom. Using a set of carefully designed baseline conditions, we find that the majority of the lottery ticket effect in both learning paradigms can be attributed to the identified mask rather than the weight initialization. The input layer mask selectively prunes entire input dimensions that turn out to be irrelevant for the task at hand. At a moderate level of sparsity the mask identified by iterative magnitude pruning yields minimal task-relevant representations, i.e., interpretable inductive bias. Finally, we propose a simple initialization rescaling which promotes the robust identification of sparse task representations in low-dimensional control tasks.
INTRODUCTION
Recent research on the lottery ticket hypothesis (LTH, Frankle & Carbin, 2019; Frankle et al., 2019) in deep learning has demonstrated the existence of very sparse neural networks that train to per- formance levels comparable to those of their dense counterparts. These results challenge the role of overparamettriizaton in supervised learning and provide new perspective the emergence of stable learning dynamics (Frankle et al., 2020a;b). Recently these results have been extended to various domains beyond supervised image classification. These include self-supervised learning (Chen et al., 2020a), natural language processing (Yu et al., 2019; Chen et al., 2020b) and semantic segmentation (Girish et al., 2020). But how does the lottery ticket ticket phenomenon transfer to reinforcement learning agents? One key challenge may be the inherent non-stationarity of the opti- mization problem deep reinforcement learning (DRL): The data-generation process is not static, but depends on the changing state of the neural network. Furthermore, weight may serve different roles at different stages of learning (e.g. during exploration and exploitation). It is not obvious how pruning heuristic acting
simple weight magnitude-basee learning process of the agent. In this work, we therefore investigate winning tickets in reinforce- ment learning and their underlying contributing factors. We compare supervised behavioral cloning with DRL, putting a special emphasis on the resulting input representations used for prediction and control. Thereby, we connect the statistical perspective of sparse structure discovery (c.g. Hastie et al., 2019) with the iterative magnitude pruning (IMP, Han et al., 2015) procedure in the context of Markov decision processes (MDPs). The contributions of this work are summarized as follows:
well- performnr policy shapes the
1. We show that winning tickets exist in both high-dimensional visual and control tasks (con- tinuous/discrete. A positive lottery ticket effect is robustly observed for both off-policy DRL algorithms, including Deep-Q-Networkss (DQN, Mnih et al., 2015) and on-policy
Authorr contrihuted equally. RTI. the corresponding author (robert. Jangeltu- de).

---

Published as a conference paper at ICLR 2022
IMP
IMP
PyBuleet: Supervised Baselines
1.0
6
Performance
6
"mask/weightt
WW
0.5
Inttery ricket
0.4
IMP Iteration 15
IMP Iteaaiio 20
permune mask and we girta
permune weights only
0.0
Weights Remaining
PyBullet: RL (PPO) Baselines
IMP Iteration
IMP Iberation 10
m' NWWW
Narm Performencs
1.00
ppermatedj
"mask/permutedd
0.76
Iteration 15
Iberationn 20
0.50
1ahhwaggf rredipar
Sumple initaalization
022
mow "randamirainit
32:77
10
1.44
Woights Ramaining 1%6
Figure 1: Representation compression, disentangling baselines & lottery ticket effects in continuous control tasks. Left. IMP successively prunes lask-itrelevant outer rim pixels in a MNIST digit- classification task and for IMP-masked agent solving a visual navigation task in DRL. The chan- nel encoding the patrolling enemy is pruned up to the point where only potential enemy locations considered. Middle. To disentangle the contributions of mask, initialization and layer-wise pruning ratio to the winning lottery ticket (mask/weights condition), we compare three baselines: After each IMP iteration, we permute either only the remaining initial weights (mask/perrutedd) or also the sparsity mask (permuted/permuted) The third baseline is created by randomly sampling a sparse mask and random re-initialization of the weights (randon/re-intt -nnt)). Right. Avg. normalized performance of policies at different sparsity levels and for different baseline conditions and four PyBullet (Ellenberger, 2018) tasks. For both behavioral cloning and PPO agents most of the ticket effect can be attributed to tasks IMP-derived mask compared to the weight initialization. Agents trained with supervision can be pruned to higher sparsity levels before performance deteriorates.
policy-gradiee methods (PPO, Schulman et al., 2015; 2017), providing evidence that the lottery ticket effect is a universal phenomenon across optimization formulations in DRL.
2. By comparing RL to supervised behavioral cloning (BC), show that networks trained with explicit supervision can be pruned to higher sparsity levels before performance starts degrade, indicating that the RL problem requires a larger amount of parameters to ad- dress exploration, distribution shift & quality of the credit assignment signal (section 3.1).
3. By introducing set of lottery ticket baselines (section 3; figure 1), we disentangle the con- tributions of the mask, weight initialization and layer-wise pruning ratio. We demonstrate that the mask explains most of the ticket effect in behavioral cloning and reinforcement learning for MLP-based agents, whereas the associated weight initialization is less impor- tant (section 3.2 and 3.3). For CNN-based agents the weight initialization contributes more.
4. By visualizing the sparsified weights for each layer, we find that early network layers are pruned more. Entire input dimensions can be rendered invisible to MLP-based agents by the pruning procedure. By this mechanism, IMP compresses the input representation of the MDP (e.g. figure 1, left column, bottom row) and reveals a minimal task representation for the underlying control problems (section 4).
5. The IMP input layer mask not only climinates obviously redundant dimensions, but also identifies complex relationships between input features and the task of the agent (section 4.1), e.g. the proximity of an enemy the speed of an approaching object. We show that the input masking can be transferred to train dense agents with sparse inputs at lower costs.
6. We show that the weight initialization scheme is important for discovering minimal rep- resentations. Depending on the input size of different layers of the network, global magnitude-based pruning can introduce strong layer-specific pruning bias. We com- pare initializations and show that a suitable initialization scheme enables the removal of task-irrelevant dimensions (section 4.2).
2

---

Published as a conference paper at ICLR 2022
2 BACKGROUND AND RELATED WORK
Iterative Magnitude Pruning. We use the iterative pruning procedure outlined in Frankle & Carbin (2019) to identify winning tickets. We train DRL agents for a previously calibrated number of transitions and track the best performing network checkpoint throughout. Performance is measured by the average return on a set of evaluation episodes. Afterwards, we prune 20% of the weights with smallest magnitude globally (across all layers). The remaining weights are reset to their initial values and we iterate this procedure (train + prune + reset). The lottery ticket effect refers to the performance gap between the sparse network obtained via IMP and randomly initialized network with sparsity-matched random pruning mask.
Lottery Tickets in Deep Reinforcement Learning. Yu et al. (2019) previously demonstrated the existence of tickets in DRL that outperform marameter-matched random initializations. They ob- tained tickets for a distributed on-policy actor-critic agent on a subset of environments in the ALE benchmark (Bellemare et al., 2013) as well as set of discrete control tasks. While they provide em- pirical evidence for the existence of lottery tickets in DRI., they did not investigate the underlying mechanisms. Here, we aim to unravel these mechanisms. To this end, we focus diverse set of environments and provide a detailed comparison between supervised behavioral cloning and on-/off- policy Deep RL with set of carefully designed ticket baselines. We analyze the resulting masked representations that the agent learns to act upon and the impact of specific weight initializations on the resulting sparse networks.
Lottery Tickets with Non-Stationary Data Distributions. Desai et al. (2019) investigated whether trained lottery tickets overfit the training data distribution under which they were obtained. Using transfer learning tasks on natural language data, they showed that lottery tickets provide general inductive biases. Similar ticket transfer results were reported by Morcos al. (2019) and Mehta (2019) in the context of optimizers and vision datasets. Unlike our work, these studies do not investigate within- training covariate shift, but instead focus on transferring ticket initializations after a full IMP run. Chen et al. (2021), on the other hand, investigate the ticket phenomenon in the context of lifelong learning and class-incremental image classification. They propose new pruning strategies to overcome the sequential nature of tasks and need for increased model capacity. Compared to the DRL setting, the covariate shift is here determined by the curriculum schedule of tasks and not the exploration behaviour of the network-paramettet parameterized agent.
Deep Reinforcement Learning Background. In our off-policy DRL experiments, we train Deep- Q-Networks (DQN, Mnih et al., 2015) with double Q-learnin loss (Van Hasselt et al., 2016) and prioritized experience replay (Schaul et al., 2015). As a representative on-policy algorithm, we chose Proximal Policy Optimization (PPO, Schulman et al., 2015; 2017). PPO is caseline-correecte pol- icy gradient algorithm which uses a clipping strategy to approximate a computationally expensive trust-region optimization method. For illustrative purposes, we train DQN agents gation task, in which an agent has to collect coins in grid while avoiding poison and two patrollers that are moving in restricted parts of the grid (figure 1, left column, bottom row; SI B). We scale our results to four PyBullet (Ellenberger, 2018) continuous control and a subset of ALE benchmark (Bellemare et al., 2013) environments. Due to computational considerations we limit each individ- ual IMP iteration for the ATARI environments to 2.5 million frames. All other tasks were trained for a pre-calibrated generous amount of transitions. We focus on feedforward value estimators and policies (MLP& & CNN) and used default hyperparameters with little tuning (SI C).
visual navi-
Supervised Behavioral Cloning. While most supervised learning relies on a stationary data dis- tribution provided by a static dataset. reinforcement learning agents have to acquire their training data in an netion-perception loop. Since the agent's 's behavioural policy is learned over time, the data distribution used in optimization undergoes covariate shift. To study how the covariate shift, additional exploration problem and different credit assignment signal influence winning tickets, we mimic the supervised learning case by training agents via supervised policy distillation (Rusu al., 2015; Schmitt et al., 2018). We roll out a pre-trained expert policy and train the student agent by minimizing the KL divergence between the student's and teacher's 's policies.
In supervised learning, the pruning mask is often constructed based on an early stopping criterion and the final network. We instead track the best performing agent. Thereby, we reduce noise introduced by unstable learning dynamics and exploit that the agent is trained and evaluated on the same environment. We found that late rewinding to later checkpoint (Frankle al., 2019) is not necessary for obtaining tickets (ST figure 14).
3

---

Published as a conference paper at ICLR 2022
3 DISENTANGLING TICKET CONTRIBUTIONS IN BC AND DEEP RL
There are two contributing fac- tors to the lottery ticket ef- feet: The IMP-identified binary mask and the preserved initial- ized weights that remain after pruning (mask/weights). We aim to disentangle the contributions by introducing set of counter- factual baselines, which modify the original IMP procedure (fig- ure I, middle column; table 1). A first baseline estimates how much of the performance of the ticket can be attributed to the initial weights, by means of a layer- specific permutation of the weights that remain after masking (mask/permutedd) A second, weaker baseline estimates the contribution of the mask, by also permuting the layer-specific masks (per- muted//prrmuted). Finally, we consider the standard random/re-init baseline, which samples random binary masks discarding layer-specific pruning ratios and re-initializes all weights at each IMP iteration. Throughout the next sections we use these baselines to analyze and compare the factors that give rise to the lottery ticket effect in different control settings.
Examined
IMP Variants
Retain weights
Retain mask
Retain layer
pruning ratio
mask/weights mask/permuted permutedlpermuted random/re-ing init
X
V
X
X
x
x
Table 1: Baselines for Disentangling Ticket Contributions
3.1 COMPARING WINNING TICKETS SUPERVISED BEHIAVIRAL CLONING AND DEEP RL
Does the covariate shift in DRL affect the existence and nature of lottery tickets? Weights pruned for their small magnitude at the end of the learning process might be needed at earlier stages, e.g., during exploration. If this were the case, the performance of the ticket DRL should degrade for lower levels of sparsity than in corresponding supervised task. To investigate this question, we turn to a behavioral cloning setting. in which a student agent is trained imitate the stochastic policy of a pre-trained expert and apply magnitude pruning to the student network after each training run iteration. By collecting transitions based on the static behavioral policy of the expert, we avoid the need for exploration and the effect of otherwise non-stationary data distribution. For both the discrete action space and all continuous control tasks we find that agents trained with RL and the supervised settings start degrade in performance at different sparsity levels (figure 2). More specifically, the maximal return of agents that were trained with reinforcement learning starts to drop significantly earlier stages of the IMP procedure. Hence, the covariate shift inherent the RL problem increases the minimal required size of winning ticket in the tasks studied here: More parameters are required for an agent that has to solve the additional exploration problem.
3.2 DISENTANGLING TICKET CONTRIBUTIONS IN SUPERVISED BEHAVIORAL. CLONING
To disentangle the contributions of the initial weights and the weight mask to the ticket effect in su- pervised behavioral cloning, next compared the three baselines to the full non-randomized ticket (figure 1, top, right and 3). For most agents, training performance does not degrade substantially when the weights permuted but the mask is kept intact (no significant gap between red and green curves). But we observe a strong decrease in the ability to prune the policy to high sparsity levels if one additionally permutes the der-verived weight mask (gap between green and blue curves). This observation holds for the cloning of expert policies in both discrete and continuous control tasks. Hence, the ticket effect can be mainly attributed to the mask rather than the weights. Fi- nally, the traditional random/re-init baseline performs worse already for moderate levels of sparsity. The resulting performance gap (blue and yellow curves) indicates the contribution of the layer-wist pruning ratio to the mask effect. These insights emphasize the importance of strong and nuanced baselines to understand the contributions to the full lottery ticket effect.
3.3 DISENTANGLING TICKET CONTRIBUTIONS IN DEEP REINFORCEMENT LEARNING
The observation that ticket information is mostly carried by the mask rather than the initial weights carries over the full DRL setups (figure 1, bottom, right and figure 4).
4

---

Published as a conference paper at ICLR 2022
Carl-Pole: Supervised RL
Walker2D: Supervised RL
HalfCheetah: Supervised
200
1500
Perfomrace
1000
500
50
200
Acrobol: Supervised vs.
Supervised
Hopper: Supervised RL
-100
2500
Perfrmmncc
-200
2000
1500
-300
-400
-500
Supervised
1000
500
RL (PPO)
-600
100.0
32.77
10.74 Weights Remaining
Weights Remaining (5)
Weights Remaining (%)
Figure 2: Comparing lottery tickets in DRL and supervised behavioral cloning. Networks trained with explicit supervision be pruned to higher sparsity levels before performance starts to de- grade. Results are averaged over 15 runs for both the Cart-Pole and Acrobot and 10 runs for PyBullet environments. We plot mean best performance and one standard deviation.
Cart-Pole: Supervised Baselines
Walker2D: Supervised Baselines
HalfCheetah: Supervised Baselines
1000
2000
200
Performanne
800
1500
150
1000
100
530
Supervised
Supervised
Hopper: Supervised Baselines
2500
-100
2000
Peformence
2000
-300
whitt/s
1500
1000
-500
-400
pern.permm
mask/perm.
1000
530
random/raint
800
3.50
37:77
100.0
10 Weights Remaining (%)
Weights Remeining (%)
Weights Remainngg (5)
Disentangling baselines for lottery tickets in supervised behavioral cloning. The gap be- tween the ticket (mask/weights) and
Figure 3:
baseline (mask/permutedd) is small, indicating a strong contribution of the mask. Results are averaged over 15 runs for both Cart-Pole and Acrobot and 10 runs for PyBullet environments. We plot mean best performance and one standard deviation.
When preserving the information contained in the mask, agents can be pruned to much higher lev- els of sparsity compared to the in which the mask information is distorted (permuted or resampled). This effect holds for both PPO- and DQN-based agents and across a wide range of qualitatively different tasks. Interestingly, ticket weights more important for CNN-based agents (e.g., see ATARI plots). We provide further experimental evidence for this observation on four Mi- nAtar games (Young & Tian, 2019) in the supplementary material (SI figure 10), where compare MLP- and CNN-based agents.
Unlike the behavioral cloning experiments, for some tasks the permuteddpermuted baseline performs worse than the random/reinit configuration. This observation only occurs for the PyBullet control
For further experiments investigating the role of different network capacities (SI figures 11, 12), state encading (ST figure 13) and regularization (ST figure 14) refer the interested reader the ST.
5

---

Published as a conference paper at ICLR 2022
Walker2D: PPO Baselines (ACP)
HalfCheeteh: PPO Baselines inee (ACP)
Ant: PPO Baselines (ACP)
2000
Perfommnnce
500
1500
250
100.0
32
77
10.74
3.52
1.44
102.0
30.77
50
3.52
144
100.0
32.77
10.24
3.57
1.44
Hopper: PPO Baselines (ACP)
Cart-Pole: PPO Baselines (AP)
Gridworld: DQN Baselines
2000
Parkommnne
150
30
1000
100
20
10
100.0
52.77
10.74
3.62
1.44
102.0
32.77
10.74
3.62
1.16
0.38 0.15
100.0
32.77
10.74
3.62
1.15
0.38
0.15
Obert: PPO Beselines (AP)
Asterix: PPO Baselines (AP)
Breakout: PPO Basalines (AP)
meek/weights mask/pam.
100
30
Porfomanco
75
random/teini
60
100.0
32.77
10.74
3,52
1.46
100.0
32,77
10:74
3.52
1.44
100.0
32:77 10.26
3,52
1.46
Weights Remaining (8)
Waights Remaining [%)
Weights Romaining [%]
Figure 4: Tickets in and off-policy deep reinforcement learning. The disentangling baselines for tickets in on-policy (PPO) and off-policy (DQN) DRL for set of continuous control, visual nav- igation and subset of ATARI environments reveal the consistent importance of the IMP-extracted mask. Results are averaged over independent runs on the Gridworld and ATARI and 10 runs on the continuous control environments. We plot mean best performance and one standard deviation.
tasks in which both the separate critic and actor networks pruned (ACP). If instead, only prunes the actor network (AP), as was done for the PPO agents trained on Cart-Pole, Acrobot and ATARI, the permuted/permuted baseline performs stronger (see SI figure 15). This result highlights the importance of differences in IMP-derived pruning ratios between agent modules, i.e. separate actor and critic networks.
4 MINIMALLY TASK-SUFFCIRE REPRESENTATIONS VIA IMP
The previous results establish the importance of the information contained in the mask for the suc- cess of winning tickets. To better understand this phenomenon and the resulting inductive biases, we analyzed the sparsified weight matrices, specifically between the input and the units in layer one. The next section sets out answer the following questions: 1) The derived mask can be thought of as a pair of goggles which guide the processing state information. What do the masked MLP- based agents observe? 2) Can transfer the input layer mask and re-use it as inductive bias for otherwise dense agents? 3) How much influence do weight initialization and input dimensionality have the discovered input layer mask?
4.1 MINIMAL TASK REPRESENTATIONS IN HIGH-DIMENSIONAL VISUAL TASKS
In the visual navigation experiments, the pruning primarily affects the input layer (figure 5, top right column). When visualizing the cumulative absolute weights of the input layer an IMP- derived DQN agent, we find that IMP deletes entire dimensions from the observation vector (figure left column) by removing all connections between those dimensions and the first hidden layer. These eliminated input dimensions are not task-relevant. A fully-connected network trained on the remaining dimensions learns the task as quickly as when trained on the complete set of input dimensions (figure 5, bottom right column). Hence, the deriver mask provides compressed representation of a high-dimensional observation space, enabling successful training even at high levels of sparsity.

---

Published as a conference paper at ICLR 2022
GriMMaze Channel- & Poosl-wiss Cumulative Weight Magnitudes
GridMaze: Layer-wise Sparsity IMP Iterations
tee 25
Agent
Dveryy
Overr
IMP heration
Training Curves for Sparstied Gridwarid
Clans
Vogut and Model
input network
Full inpul spa networn IMP 201
Training Emvirommet Steps
Figure 5: IMP eliminates irreleeat observation dimensions for high- dimensionni visual nav- igation task (o, I2xx10x20 Left. Channel-/pixel-vie cumulative weight magnitudes. IMP successively prunes redundant input pixels which are not necessary to solve the navigation task. All of the pruned enemy channel pixels encode locations which the patrolling enemy cannot access. Right, Top. Pruning affects the layers and object channels differentially. The imput layer is pruned most strongly, while the agent channel is pruned the least. Right, Bottom. The input layer pruning mask (at moderate sparsity levels) can be used as an inductive bias for training a dense network.
This result extends to masked input layers MLP-agents trained on the MinAtar environments (figure 6 and SI). For the Freeway task find that the IMP mask encodes the notion of velocity of moving cars. The input layer weights corresponding to the binary observation channel which encodes the slowest moving car are pruned the most, maintaining only the pixels needed to react in time. The same principle applies to the enemy bullet channel in the SpaceInvaders task. The agent only needs to know about potential collision at the next time step in order avoid being hit. Therefore, IMP prunes all information about the enemy bullet that is more than one step away from the agent. For all visualized MinAtar tasks, only the actionable row/column of the agent channel is preserved. In Breakout, additionally the bottom row of the ball and trail channel is pruned since the game terminates once the ball or trail reach There no action-relevant information encoded and it can be discarded. In summary, find that IMP-derive input layer mask provides visually interpretable and physically meaningful compression of the observation space.
4.2
MINIMAL REPRESENTATIONS IN LOW-DIMENSIONAL CONTROL TASKS AND THE ISSUE OF INITIALIZATION SCALES
The continuous and discrete control tasks, on the other hand, rely on low-dimensional state repre- sentations. At first sight, they do not contain obviously uninformative input dimensions that lend themselves to be pruned. We would expect the cumulative weight strength of each input dimension to decrease at equal speed over the course of iterative pruning. Contrary to this initial intuition, IMP still aggressively prunes core dimensions while yielding trainable agents (figure 7, 8). For subset of continuous control tasks, we find that one can prune 20 and up to 50 percent of the input dimensions, while still being able to train the agent to the performance level of a dense counterpart (figure 7). The exact amount depends on the considered environment indicating varying degree of observation over-specification across task formulations. For example, the Walker2D environment can train to full performance with only 11 out of 22 observation dimensions, while the Ant environ- ment requires 22 out of 28 dimensions. We note an initial positive effect of the weight pruning on the performance of all agents indicating the effectiveness of the implied regularization.
In the Cart-Pole task the cart position and its velocity are pruned (figure 8, top). Newton's 's laws are invariant with regard to the choice of the inertial frame of reference, the input channels encod- ing the cart position and velocity do not provide additional information over the pole's ' angle and velocity. The Acrobot task requires the agent to swing-up two-link pendulum across a line fast
7

---

Published as a conference paper at ICLR 2022
Freeway
Spacelmaadess
Breakout
Genron
Boles
Afle
Figure 6: IMP eliminates task-irrelevant observation dimensions for a selection of MinAtar environ- ments (Young & Tian, 2019). The environment depicting figures were adapted from Young & Tian (2019). Left. Freeway. IMP provides an inductive bias by differentially pruning object channels with different velocities (e.g. car speeds). Middle. Spacelnvaders. IMP only preserves pixels of en- emy objects which encode actionable proximity information (e.g. bullets being close the agent). Right. Breakout. IMP discards pixels which only change when it is too late to act (e.g. when the ball has left the display and the episode terminates).
Walker2D: Or E g2
HalfCheetah: Or E 26
Ant: O E 88
% Pruned input Dimensions
vs. Rolatire Perfomance
1.25
1.00
0.75
0.50
Inpul Dim. Sparsity Rel. Performance
0.25
100.0
32.77
10.74
3.52
1.44
100.0
32.77
10.74
3.52
1.44
100.0
32.77
10.74
3,52
1.44
Weights Remaining [%)
Weights Remaining [%)
Weights Remaining [%]
Figure 7: IMP eliminates task-irrelevant observation dimensions for set of continuous control tasks. For all three tasks there exists moderate sparsity level (approximately 10% non-sparse weights) at which entire input units (columns of the first linear layer) pruned while the agents still train to the performance level of their dense counterparts. The extent of this observation strongly depends on the considered environment indicating varying extent of observation over-specification.
as possible. Here, IMP eliminates all sine and cosine transformations of the rotational angles of the links (figure 8, middle row, right column). Since the swing-up can be achieved by coordinating and increasing the angular velocities of the two links, only these two dimensions have to be preserved from pruning. These experiments demonstrate that IMP can yield fundamental insights into what physical information is sufficient to solve task and leverages them to prune the input represen- tation without impairing performance. During our analysis we discovered that the core dimension discovery of IMP crucially depends on the initialization of the input layer weights. Popular weight initialization heuristics such as the Kaiming family (He et al., 2015) aim to preserve activation mag- nitudes across network layers. As result, layers that receive high-dimensional input are initialized at lower values and are therefore prone to more aggressive pruning by IMP. This bias does not occur for Xavier initializations (Glorot & Bengio, 2010, figure 8, top rows, right column). Furthermore, we experimented with different approaches to combat this initialization bias. We find that down- scaling the Kaiming initialization of the input layer by a factor of ten leads to a robust discovery after few IMP iterations (figure 8, top rows, middle column). While smaller rescaling factors lead to slower separation of dimensions, larger factors result in overly aggressive pruning of the input layer. In summary, have shown that the input layer initialization shape the resulting lottery ticket mask and provide a first initialization heuristic promoting efficient minimal task representation discovery.
8

---

Published as a conference paper at ICLR 2022
Caripole- Kaiming Normal
Cartpole Kaiminn Normal Rescale
Carppole Xavier Uniform
Weights Romn
Din. T:X
10
Den.
Den. 9
Acrobol- Kaiming Uniform
Acrobot - Kainnng Unitomm Rescale
Acrobol Xavier Uniform
10"
Welghts Rom.
snipo
Den coatd.)
Den. 2niP
10
Din. 0b
10
20
30
0
t0
20
30
5
1n
30
30
IMP leeraion
IMP lleration
IMP heration
PPO Regular & Carl-Pole
PPO Regular
200
Performance
Performancs
-200
100
2km Muskes Pan-
+400
Dix Nassod Aoruott Dim Aexbott
4 Dmn. Full Cart Rale
40000 Environment Step Trensitions
20000
80000
80000
200000 400000 600000 800000 1000000 Environment Step Traneilions
Figure 8: IMP eliminates task-irrelevant observation dimensions for low-dimensional control tasks. Suitable initialization heuristics can promote and accelerate the discovery of minimal representa- tions. Top. IMP identifies that the Cart-Pole task can be solved with only two dimensions: The pole angle and angular velocity. Middle. IMP identifies that the Acrobot task can be solved with only two dimensions: The angular velocities of the two pendulum links. Bottom. Agents can success- fully be trained on the subset of IMP-derived dimensions alone. We plot mean performance and one standard deviation across independent runs.
CONCLUSION
Summary. This work has investigated the mechanisms underlying the lottery ticket effect in be- havioral cloning and DRL. We provide evidence that agents which are trained on a stationary data distribution and do not face the exploration problem, can be pruned to higher levels of sparsity while successfully performing their task. For both setups we find that the effect can be attributed to the identified mask rather than to the corresponding weight initialization. We have shown that the mask compresses the input representation by removing task-irrelevant information in the form of visual object pixels or entire control observation dimensions. Finally, we found that the pruning process is sensitive to the layer-specific scale of the weight initialization. The interpretability of the resulting minimal representations can be enhanced by heuristically re-scaling the weights in different layers.
Limitations. While our observations qualitatively robust, they quantitatively vary across learn- ing paradigms, algorithms, architectures and different tasks. Compared to our results, weight values have been claimed to play classification (Frankle et al., 2020a). Future work will need to investigate under which conditions the initialization of the weight values significantly contributes more, most of our experimental results have been obtained for on-policy PPO and policy-based BC agents. Whether the interpretation of the mask effect as a representation regularizer also holds for intermediate and higher layer masks is hard to assess and remains an open question. Finally, this study is empirical in its nature and will require further theoretical guidance and foundations.
central role in the context of lottery tickets in supervised image
the ticket effect RL. Further-
Future Work. In future work we want to investigate layer-wise effects, c.g., by studying layer- specific pruning ratios, normalization schemes and fine-grained baseline analyses, in the hope of identifying sparser, more efficient and interpretable winning tickets. Further work needs to be done to disentangle the contributions of the additional exploration problem, distribution shift and credit assignment signal in RL. Our proposed baseline analysis can be applied more generally to all stud- ies considering the lottery ticket procedure. Finally, we believe that there are many opportunities to modify the original IMP procedure to simplify the discovery of minimal representations. For example, pruning entire units of intermediate layers may improve the interpretability hidden rep- resentations.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank Jonathan Frankle for initial discussions and feedback on the first manuscript draft. Further- more, we thank Joram Keijser for reviewing the manuscript. This work is funded by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) under Germanys Excellence Strat- egy EXC 2002/1 Science of Intelligence project number 390523135.
REFERENCES
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 0100000015440 2016.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. arXiv preprint arXiv:2012.06900 2020a.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint arXiv:2007.12223, 2020b.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Long live the lottery: The existence of winning tickets in lifelong learning. In International Conference on Learning Representations, 2021a. URL https://openreview. net/forum, 2021.
Shrey Desai, Hongyuan Zhan, and Ahmed Aly. Evaluating lottery tickets under distributional shifts. arXiv preprint arXiv: 11..9100..7.., 12708, 2019.
Benjamin Ellenberger. pybullet-gym gym, 2018.
Pybullet gymperium.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint 1rXiv:1803.03635, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv:1903.01611, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. arXiv preprint arXiv: 2020aa
Jonathan Frankle, David Schwab, and Ari S Morcos. The early phase of neural network training. arXiv preprint arXiv:2002.00 200..0000..3 2020b.
Sharath Girish, Shishira R Maiya, Kamal Gupta. Hao Chen, Larry Davis, and Abhinav Shrivastava. The lottery ticket hypothesis for object recognition. arXiv preprint 3XXv:2012.046433 2020.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural networks. arXiv preprint arXiv: 156.002626 2015.
Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, er al. Array program- ming with numpy. Nature, 585(7825):357-362 2020.
Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical learning with sparsity: the lasso and generalizations. Chapman and Hall/CRC, 2019.
10

---

Published as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, In Proceedings of the IEEE international conference on computer vision, pp. 1026-10344 2015.
John Hunter. Matplodib: A 2d graphics environment. IEEE Annals of the History of Computing. 9(03):90-95, 2007.
Rahul Mehta. Sparse transfer learning via winning lottery tickets. arXiv preprint arXiv:1905.07755 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. natwre 51 518(7540):529-533 2015.
Ari Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: gener- alizing lottery ticket initializations across datasets and optimizers. In Advances in Neural Infor- mation Processing Systems, pp. 4933-4943, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alhan Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell, Policy distil- lation. arXiv preprint /5 2015.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.059% 2015.
Simon Schmitt, Jonathan J Hudson, Augustin Zidek, Simon Osindero, Carl Doersch, Wojeiech M Czarnecki, Joel Z Leibo, Heinrich Kuttler, Andrew Zisserman, Karen Simonyan, et al. Kickstart- ing deep reinforcement learning, arXiv preprint arXiv:1803.03833 2018.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Adam Stooke and Pieter Abbeel. ripyt: A research code base for deep reinforcement Iearning in pytorch. arXiv preprint 1rXiv:1909.01500 2019.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-
learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Michael L Waskom. Seaborn: statistical data visualization. Journal of Open Source Softwrre (60):3021, 2021.
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint 1rXiv:1903.03119 2019.
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp. arXiv preprint arXiv: /906. 02768, 2019.
11

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY INFORMATION: ON LOTTERY TICKETS AND MINIMAL TASK REPRESENTATIONS IN DEEP REINFORCEMENT LEARNING
A ADDITIONAL RESULTS
A.1 MINATAR DISTILLATION AND DQN RESULTS- MLP AND CNN-BASED AGENTS
To test the robustness of the lottery ticket phenomenon to different architectures and diverse tasks, we repeat the baseline comparison distillation experiments for the MinAtar environments (see figure 9). We trained MLP- and CNN-based agents distill experts' value estimators and using the same architecture and hyperparameters for all considered games. For MLP agents the mask consistently contributes most to the the ticket. For CNN-based agents and selected games (Asterix and Space Invaders) the weight initialization contributes more.
Asterix: PD (DGN)- MLP
Dreakout: PD (DGN)-MLP -LPP
Freeway: PD (DGN)-MLL MLP
Spacelnvader:: PD- MLP
100
Peformanos
60
Astaric: PD (DON)- - GMN
Braakott: PD (DDN)-CNN
Freeway: PD (DGN)- -NNN
Spacainvaders: PD - CNN
Perfomance
30
10
20
0
100.0
3.50
3.52
32.77
52.77
3.52
1.44
Weights Rormaiing
Weights Remaining
Weights Rermiining [S]
Weights Remaining (%6
Figure 9: Lottery tickets in supervised policy distillation (MinAtar environments, Young & Tian, 2019). We find evidence for a strong contribution of the IMP-identified mask to the overall ticket effect. The qualitative baseline comparison generalizes from MLP- CNN-based agents. Top. Disentangling ticket baselines for MLP-based value function estimators across four MinAtar games. Bottom. Disentangling ticket baselines for CNN-based value function estimators across four Mi- nAtar games. The results are averaged over 5 independent runs for all MinAtar environments. We plot mean best performance and one standard deviation.
Asterix P-DON
Breakout MUP-DON
Freesny: ML P-DON
Spacalnvaders: ML MLP-DON
rashieigh
60
Performanc
resh pem.
pemupers
40
0
Asteric CNN-DON
Broakout CNN-DON
Frooway:
Spacainvaders CNN-DON
Perforanne
20
60
88
0
100.0
10.74 Weights Remaiiing (56)
32.77
3.52
1.44
100.0
32,77
10,74
3.52
1.44
100.0
32.77
10.74
3.52
1.44
100.0
32.77
10.74
3.52 1.44
Welghtt Remaining (74]
Weights Remaining (74)
Weights Remahning (8)
Figure 10: Tickets in poo-co deep reinforcement learning (MinAtar environments, Young & Tian, 2019). We find evidence for strong contribution of the IMP-identified mask to the overall ticket effect. The qualitative baseline comparison generalizes from MLP- to CNN-based agents. Top. Disentangling ticket baselines for MLP-baaed value function estimators across four MinAtar games. Bottom. Disentangling ticket baselines for CNN- value function estimators across four Mi- nAtar games. The results are averaged over 5 independent runs for all MinAtar environments. We plot mean best performance and one standard deviation.
Strengthening an observation in Yu et al. (2019), we observe that the performance deteriorates at different levels of network sparsity depending on the considered game. Freeway agents keep per-
12

---

Published as a conference paper at ICLR 2022
forming well even for high levels of sparsity, while agents trained Breakout and Space Invaders continually get worse as the sparsity level increases. In general we find that the qualitative results obtained for MLP agents generalize well to CNN-based agents. The only major difference is that unlike the Asterix CNN agent, the MLP agent improves their performance at moderate levels of sparsity. In summary, provide further consistent evidence for the strong contribution of the mask to the lottery ticket effect in DRL (both on-policy and off-policy algorithms). The results gener- alize between different architectures indicating that the strength of the overall lottery ticket effect is mainly dictated by the combination of the aas-sppeciiicttion of the environment and the DRL algorithm.
A.2
THE EF FECT OF NETWORK CAPACITY ON THE ABSOLUTE SIZE OF WINNING TICKETS
Gridword:: PD (DGN)- -Newwokk Size
Cart-Pole: (PPO)- Netwwrkk Siza
Acrobol: (PPO)- S2w
-100
manooesr (hA $12.002
Performing POTTTTTOOO
150
250250
Porformaree
-200
thite
100
10
perr 133
400
128-4
pers yairs:
20h24
-500
-800
1.00 Abs. Waights Remaining
0,10
0.01
1.00
0.10
0.01
0,00
1.00
0.10
0.01
0.00
0.00
x10"
Number Weights Remaining
x10"
Numbar Weights Ramaining
x10"
Gridwordd RL (DGN) Network Size
Cart Pole: RL (PPO).
Network Size
Acrzbot RL (PPO) Natwork Size
200
Perforance
Performiiioo
Performanos
-200
2/300
20
-300
100
-000
50
5030
No02
1.00 Abs Number Weights Remaining x100
0.10
0.01
1.00
0.10
0.01
0.00
1.30
0.10
0.01
0.00
0.00
Abs. Number Weights Remaining x1D"
Abal Number Weights Remaining x10"
Figure 11: Effect of network size on lottery ticket effect in supervised behavioral cloning and deep reinforcement learning. Top. The initial network size has influence relative performance of tickets and permuted/pernutte baselines for supervised behavioral cloning. Larger networks do not yield tickets that outperform those generated from smaller networks for a given absolute number of remaining weights. Bottom. Initial network size comparison for tickets in on- and off- off-policy DRL. Again, larger initial network size does not lead more performant tickets. The results are averaged over 5 independent runs on the GridMaze environment and 15 independent runs on the Cart-Pole and Acrobot environments. We plot mean best performance and one standard deviation.
The lottery ticket hypothesis suggests that using larger original network size increases the number of sub-networks which may turn out to be winning tickets (Frankle & Carbin, 2019). To investigate this hypothesis for the case of policy distillation, we analyzed the effect the initial network size on the lottery ticket effect (figure 2, right column). Against this initial intuition, we observe that smaller dense networks are capable of maintaining strong performance at higher levels of absolute sparsity as compared to their larger counterparts. Furthermore, the initial network size does not have strong effect on the relative performance gap between the ticket configuration (mask/weights) and the baseline (permutee/permmuted) We suspect that larger networks can not realize their combinatorial potential due to a an unfavorable layer-wiss wise pruning bias introduced by initialization schemes such the Kaiming family (He al., 2015). An imbalance between input size and hidden layer size can have strong impact on which weights are targeted by IMP. We further investigate this relationship in section 4.2.
13

---

Published as a conference paper at ICLR 2022
Gridwori:: PPO Network Size Comperison
Cartpolo: DQN Network Size Comparison
Max Evel. Feeuun [Mese eic (DD
(Maan (D)
-000
50
1:00
Layer
100
Hidden Layer Size
010 witt ants
128 128 unis
512.512
Corditon
Condition
mesk/weights
pers/alpereed
permutodiiprmaa mutoded
tovds
16x04
"exid
Te-32
Abc. Number Weights Remaining
Abs. Number Weights Remaining
Figure 12: In the main text, agents were trained GridMaze using the DQN algorithm and on Cart-Pole using PPO. Here, we report the performance of PPO-trained agents on the GridMaze task (left) and of DQN-trained agents on the cart-pole task (right) for different network sizes.
A.3 THE EFFECT OF DIFENT REPRESENTATIONS ON LOTTERY TICKETS IN DRI.
CridMaze, RGB Representation
GridMaze, Entangled Repreeentation
Nor Evol Reaurn (Nesn of (30)
Condition
Condition
maa-)yenrrhe sked
nandrronenn
tercknl/weri
1000
3277
12
122
3.50
075
32.1
10.00
0.50
0.75
Ramaiiing 1S]
Figure 13: Performance of agents trained on an RGB RGB-encoded GridMaze task (left) and on ran- domly projected, entangled representation (right). The derived mask robustly contributes most to the ticket. More information can be found section B.
A.4 THE EFFECT REGULARRIZTTION AND LATE REWINDING ON LOTTERY TICKETS DRL
Tidhda untitoales
Rewindin
0/9
Van Noter Moaer- 103)
Rowind ng to 100 000 Ur
No Weight Denry, perm tedipermutee
No Dropout, sermuted/pomm..o Diopout semuuedponnito
Weight Decay, gemmuledroermulleed Decay, maskiwdights
Rewind ng C00.0000
Figure 14: Left. Lottery ticket plot with and without L2 weight decay 0.1). Using weight decay does not impair the ticket phenomenon for DQN agent. Middle. Lottery ticket plot with and without dropout in all layers (p 0.1). Dropout deteriorates overall performance at all levels of sparsity, but does not impair the ticket effect for DQN agent. Right. Late rewinding (Frankle al., 2019) to different stages of training (0, 100k, 400k, 4000k environment steps).
14

---

Published as a conference paper at ICLR 2022
A.5
PYBULLET DEEP RL PPO EXPERIMENTS WITHOUT PRUNING OF THE CRITIC
Walker2D: PPO Baselines (AP)
HaifCheetah: PPO Baselines (AP)
mapiinggla medpperreed jenmupallemmalll rer
1000
2000
Performance
Performance
750
500
1000
FasATA gnls maskSAATARE
250
perruzzdipamutee
sandoriisii
0
100.0
32.77
10.74
3.52
1.44
100.0
32.77
10.74
3.52
1.44
Weights Remaining [%]]
Weights Remaining [%)]
Ant: PPO Baselines (AP)
Hopper: PPO Baselines (AP)
2500
2000
Performance
Performance
2000
1500
1000
madkww chtt
1000
sernssddpeeutte
perm/zadpemm/ed
sandorsisint
0
rancorstrin:
100.0
32.77
10.74
3.52
1.44
100.0
10.74 Weights Remaining [%]
32.77
3.52
1.44
Weights Remaining [%]
Figure 15: Tickets in on-policy deep reinforcement learning and when pruning only the actor mod- ule. The random re-sampling baseline in this case outperforms permuting both the weights and the mask. The results are averaged over 10 runs. We plot mean best performance and one standard deviation.
B MAZEGRID ENVIRONMENT
The MazeGrid is visual navigation task: The agent navigates a grid environment, which is ten pixels high and twenty pixels wide. Each location holds a single unique object. There are six types of objects: empty background (black), walls (grey), the agent (cyan), two moving enemies (magenta and green), as well as 42 coins (yellow) and twelve poisons (brown) (visualized figure 1, bottom row, left column). The layout of the game the same in every episode. The agent walk in four directions (up. down, left, right). The enemies patrol horizontally inside the gaps in the wall. A full game in motion can be watched in the project repository, which will be released after publication. A game terminates after 200 timesteps, or the agent collects (walks over) all coins, or if the agent in the same location an enemy. Each collected coin yields a reward of plus one, each collected poison yields minus one, presented immediately to the agent. To ensure our results do not depend on the specific encoding the environment, we compared three different representation of the MazeGrri environment (section A.3):
The object-map encoding consists of separate one-hot maps for each type of object. Empty space is encoded explicitly by a separate map, walls however do not have their own map and are only implicitly represented by the lack of any other object. The representation thus contains six maps, ten by twenty pixels each for total of 1200 binary values for each state.
The RGB encoding consists of the canonical three color channels for each location, result- ing in 600 integer values in range [0, 255). Losing information due to occlusion is not an issue in this environment since any location can only hold a single object at time.
The entangled encoding is derived from the object-map encoding by flattening all values into vector and multiplying with pseudo-randon 1200 by 1200 matrix. The matrix's 's values are sampled independently from ((-1, The matrix remains constant across all IMP iterations, every seed has its own matrix.
15

---

Published as a conference paper at ICLR 2022
All experiments in the main text were conducted the object-map environment. Figure 13 provides a comprehensive overview over the baselines to demonstrate that tickets do rely on one specific encoding. The importance of the mask is even further highlighted by our results RGB specifically.
C HYPERPARAMETER SETTINGS FOR REPRODUCTION
All simulations were implemented in Python using the rlpyt DRL training package (Stooke & Abbeel, 2019, MIT License) and PyTorch pruning utilities (Paszke et al., 2017). The environments were implented by the OpenAl gym (Brockman et al., 2016, MIT License). MinAtar (Young & Tian, 2019, GPL-3.0 License), PyBullet gym (Ellenberger, 2018) packages and the ALE benchmark environment (Bellemare et al., 2013). Furthermore, all visualizations were done using Matplotlib (Humter. 2007) and Seaborn (Waskom, 2021, BSD-3 1-D-3-Clan 3-CCuuee License). Finally, the numerical analy- License). We will release the code conducted CPU cluster and GPUs
sis was supported by NumPy (Harris et al., 2020, after the publication of the paper. The simulations were used. Each individual IMP run required between 8 (Cart-Pole and Acrobot), 10 (MazeGrid, MinAtar) and 20 cores (PyBullet and ATARI environments). Depending on the setting, for lottery ticket experiment of 20 to 30 iterations lasts between 2 hours (Cart-Pole) and 5 (ATARI games) days of training time.
C.I CART-POLE BEHAVIORAL CLONING & PPO
Parameter
Value
Student Network Size
128,128 units and 256,256 units
Teacher Network Size
64.64 units and 128,128 units
Learning Rate
0.001 (Adam)
Training Environment Steps
10.000
Number of workers
4
Distillation Loss
Cross-entropy expert-student policies
Table 2: Hyperparameters for the BC algorithm on Cart-Pole. Results reported fig. 2, and 11.
Parameter
Value
Parameter
Value
Optimizer
Adam
Value Loss Coeff.
0.5
Learning Rate
0.0005
Entropy Loss Coeff.
0.001
Temporal Discount Factor
0.99
Likelihood Ratio Clip
0.2
Training Environment Steps
80.000
Number of workers
4
GAE A 0.8
Number of epochs
4
Table Hyperparameters for the PPO algorithm on Cart-Pole, Results reported in fig. 2, and 11.
C.2 ACROBOT BEHAVIORAL CLONING & PPO
Parameter
Value
Student Network Size
128,64 and 226,128 and 512,256 units
Teacher Network Size
128,6 64 units
Learning Rate
0.0005 (Adam)
Training Environment Steps
200.000
Number of workers
Distillation Loss
Cross-entropy expert-student policies
Table 4: Hyperparameters the BC algorithm on Acrobot. Results reported fig. 2, 11.
16

---

Published as a conference paper at ICLR 2022
Parameter
Value
Parameter
Value
Optimizer
Adam
Value Loss Coeff.
0.5
Learning Rate
0.0005
Entropy Loss Coeff.
0.01
Temporal Discount Factor
0.99
Likelihood Ratio Clip
0.2
Training Environment Steps
500.000
Number of workers
4
GAE A 0.95
Number of epochs
4
Table 5: Hyperparameters for the PPO algorithm on Acrobot. Results reported in fig. 2, and 11.
C.3 PYBULLET CONTINUOUS CONTROL- BEHAVIORAL CLONING & PPO
Parameter
Value
Student Network Size
64,64 Actor and Critic
Teacher Network Size
64,64 units
Learning Rate
0.0005 (Adam)
Training Environment Steps
500.000
Number of workers
10
Distillation Loss
KI. divergence expert-student policies
Table 6: Hyperparameters for the BC algorithm PyBullet. Results reported in fig. 2, and 3.
Parameter
Value
Parameter
Value
Optimizer
Adam 0.0005
Value Loss Coeff.
0.5
Learning Rate
Entropy Loss Coeff.
0.001
Temporal Discount Factor
0.99
Likelihood Ratio Clip
0.2
Training Environment Steps
1.500.000
Number of workers
10
GAE A 0.98
Number of epochs
10
Table 7: Hyperparameters for the PPO algorithm on PyBullet. Results reported in fig. 4 and 7.
C.4
GRIDMAZE DQN
Parameter
Value
Parameter
Value
Optimizer
Adam
Replay Buffer Size
100.000
Learning Rate
0.0005
Replay Buffer
0.6
Temporal Discount Factor
0.99
Replay Buffer (init.)
0.4
Batch Size
256
Replay Buffer 3 (final)
I
Huber Loss 5
1.0
Data Replay Ratio
4
Clip Grad. Norm
10
Training Environment Steps
5.000.000
start
/
0.01
#e Annealing Frames
1.000.000
e eval
0.001
Table Hyperparameters for DQN algorithm on GridMaze. Results reported fig. 4.
17

---

Published as a conference paper at ICLR 2022
C.5 ATARI PPO
Parameter
Value
Parameter
Value
Optimizer
Adam
Value Loss Coeff.
0.5
Learning Rate
0.0005
Entropy Loss Coeff.
0.001
Temporal Discount Factor
0.99
Likelihood Ratio Clip
0.2
Training Environment Steps
2.500.000
Number of workers
10
GAE 0.98
Number of epochs
10
Table Hyperparameters for the PPO algorithm on ATARI. Results reported in fig. 8.
C.6 MINATAR- BEHAVIORAL. CLONING DQN FOR MLP/CNN AGENTS
Parameter
Value
Student Network Size
1024,512 units (MLP) and Conv2D-16x3, 128-64 (CNN) 512,256 units (MLP) and Conv2ID116x3, 128-64 (CNN)
Teacher Network Size
Learning Rate
0.0005
Training Environment Steps
10.000.000 (MLP) and 5.000.000 (CNN)
Independent Seeds
5
Distillation Loss
Huber loss of expert-student value estimates
Table 10: Hyperparameters for the BC algorithm on MinAtar. Results reported in fig. 9.
Parameter
Value
Parameter
Value
Optimizer
Adam
Replay Buffer Size
100.000
Learning Rate
0.00025
Replay Buffer
0.6
Temporal Discount Factor
0.99
Replay Buffer 3 (init.)
0.4
Batch Size
256
Replay Buffer 3 (final)
1
Huber Loss 5
1.0
Data Replay Ratio
4
Clip Grad. Norm
10
Training Environment Steps c final
15.000.00
start
1
0.05
#c Annealing Frames
7.500.000
e amal
0.001
Table 11: Hyperparameters for the DQN algorithm on MinAtar. Results reported in fig. 10.
18


Reviews:
[{"review_id": "iWFZd5WX5XO", "reviewer": "Reviewer_HrAw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n- The principal strength of the paper is in the thoroughness of its empirical evaluations. \n    - In particular, the paper identifies a key source of the distinction between RL and supervised learning relevant to lottery tickets: that of distribution shifts induced by the policy improvement operator over the course of training in RL, something absent in supervised learning.\n    - The distinction between policy-based and value-based RL is important and I was happy to see both value-based and policy-based agents included in the experimental evaluations.\n    - Similarly, I am aware of many papers which study the effect of variations on the IMP masking procedure (e.g. Frankle et al. 2019, 2020; Yu et al., 2020; Zhou et al., 2020), but the clarity and comprehensiveness of the ablation in this work makes it a worthwhile contribution to the literature. I also appreciated that the effect of convolutional layers was discussed in the main paper, and that late rewinding was also evaluated in the appendix.\n- The connection between magnitude pruning and state abstraction, particularly in low-dimensional input settings, presents an interpretable and intuitive visualization of lottery tickets.\n- The paper is clearly written and it is easy to see how the experimental results justify the claims made in the text.\n- While prior works have studied lottery tickets in RL (Yu et al., 2020), this work is distinguished by its focus on the interaction between the non-stationarity inherent in RL and magnitude pruning methods. \n- The paper provides useful recommendations for training sparse networks in RL tasks, such as noting the importance of the weight initialization scheme in determining how aggressively inputs are pruned.\n\n### Weaknesses\n\n- The focus of the paper at the moment seems to be “about” the LTH, with RL as an experimental condition in which to study it. In contrast, I think the paper also has the potential to tell us a lot about properties of deep RL agents using the LTH as an experimental condition. The degree to which a network can be pruned seems to be telling us something really interesting about the complexity of a given task, and I think there’s potential to draw a deeper connection to prior work studying non-stationarity in RL. \n- The paper dives quite quickly into its findings, but leaves some gaps in the motivation of its investigation. At the moment, my interpretation of the motivational paragraph is that it essentially says “People are interested in lottery tickets but haven’t looked at them properly in deep RL yet, so that is what we will do”. A sentence or two justifying why looking at lottery tickets in RL is interesting and important, beyond simply an absence of existing literature, would greatly benefit the paper. For example, would lottery tickets enable more efficient control systems? Would this investigation tell us something important about deep neural networks? \nWhile it is interesting to look at “retraining” a pruned network from scratch on an RL task, it’s not clear that this is the best approach to sparsify RL agents. As the motivation of IMP is largely to find computationally efficient sparse subnetworks that perform well on the target task, finding a maximally sparse network which attains high return in the target task seems desirable. In this case, presumably a better approach to obtaining sparse agents would be to distill the sparsified network on the outputs of the dense network as a form of supervised training, rather than forcing the network to maintain the capacity necessary to fit all of the intermediate policies and value functions necessary to reach the final high-performing policy.  \n- I am somewhat skeptical of the interpretation of the convolutional masks in Figure 6. While I can see how each of the labels might correspond to their respective mask, I think it might be reaching a bit to say that particular horizontal lines correspond to bullets as opposed to cannons. I agree with the overall take that magnitude pruning preserves semantically significant components of the filters, but in contrast to the thorough and careful analysis of the rest of the paper, the mapping from the mask on a particular filter into a specific interpretation seems less than rigorous.\n\n\n### Potential Improvements/Questions\n- While behaviour cloning is one way to introduce supervision into RL tasks, I would also be interested in seeing what happens when policy evaluation of an expert policy is used as the supervised task, to complement the comparison between policy-based vs value-based agents trained with policy improvement.\n- A priori I would have thought that the value prediction networks would be more sensitive to pruning than policy networks, and the paragraph at the top of page 6 seems to support this intuition. I think it would be easier to parse the paper if it is made clearer in the figures which pruning scheme is used in which evaluations. ", "summary_of_the_paper": "This paper empirically studies the lottery ticket hypothesis in deep reinforcement learning. It confirms the existence of lottery tickets in RL agents, and provides a detailed study of lottery tickets in both control problems and supervised behavioural cloning problems to identify the effect of RL-specific distribution shifts and to evaluate properties of the weight masks produced by iterative magnitude pruning.\n", "summary_of_the_review": "Overall, I think the careful analysis and clear presentation of the findings of this paper make it a valuable contribution to both the lottery ticket hypothesis literature as well as to our understanding of non-stationarity in deep RL. I therefore recommend that it be accepted to ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D5SNgta0PCo", "reviewer": "Reviewer_SmNw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n\n1. The paper targets the important problem of dimensionality reduction of task representation which helps in improving performance of several applications where inference response plays a key role.\n\n2. Such empirical studies are extremely important and it provides valuable insights to researchers interested in model optimization in the context of control problems. This study will definitely motivate further work into developing newer classes of sparsification/pruning algorithms in the context of deep RL. \n\n\nWeakness\t\t\t\t\n\n1. The intent of the paper is at times difficult to realize .. since the paper has not been structured well. The contributions listed in the introduction does not align well with the arrangement of the sections and respective discussions. \n\n2. Many of the experimental details are pushed to the appendix. This is an important study and researchers will want to try their hands on the the actual experiments and validating their results against the results presented here. So more details on experimental settings .. choice of exp env. ... system reqs etc. is needed.\n\n3. Novelty over state of the art is not clear. While it is understandable that this is an empirical analysis, the reader will still expect at least one of 2 things \n       3a. One liner empirical outcome. As in what is right / wrong / broken/ beautiful  about the thing there is being studied\n       3b. What can be done about it? A proposal of some sort at least. \n", "summary_of_the_paper": "This paper investigates the Lottery Ticket hypothesis in the context of deep RL for identification of sparse task representation in low-dimensional control tasks. This is primarily an empirical investigation where several experiments and consequent analysis reveal what a \"winning ticket\" means in case of policy models or Q function approximators given that Deep RL is prone to gradual distribution shift. The experiments also help to identify how standard magnitude pruning will behave under different environment updates, feedback schedules or initialization dynamics.  ", "summary_of_the_review": "This an important study and analysis that will motivate further research. However the current version has some major concerns that the authors need to address. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5IeGAdW4Se", "reviewer": "Reviewer_BwRq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Quality, Clarity, Soundness, Correctness**\n\nThe paper is an impressive empirical study covering a vast range of variations, baselines and ablations. All experiments are repeated multiple times and std-deviations are reported which helps with judging the stat. significance of findings. The necessary background and related work is briefly, but well summarized. Experiments are and findings are well presented - though given the sheer number of experiments and results some parts of the paper appear a bit crammed (but there is no easy solution to this given the limitations of a conference-format paper). Experiments and the conclusions drawn appear to be correct to me - though, sometimes aggregate results like Fig 1 right, bottom do not strictly hold for all experiments that went into the aggregate result (Fig 4 bottom row, where there is no very pronounced difference between the red, green and blue lines). My one criticism is the hypothesis that attributes distributional shift due to exploration as the reason for why pruning rations (without performance degradation) in RL are typically lower than in supervised learning. While the hypothesis is sensible, it is never formally verified, and no alternative explanations are presented (one simple control could be to train the supervised baseline on data that includes the various stages of the RL agent, including early exploration phases, rather than just using “expert” trajectories).\n\n**Verdict**\n\nOverall I think this is a great empirical paper. Experiments are plentiful, well executed and with an impressive amount of relevant baselines and controls. While the lottery ticket effect has been investigated in great detail in non-RL domains before, and many ideas and inspiration for experiments could be transferred from previous work, I do not think this limits the merit of the current paper. Important empirical verification was carried out and results were presented in detail, and with some interesting observations. The paper lays the groundwork for now digging deeper into some of the findings. I have some small suggestions for improvements, but am currently in favor of accepting the paper. Looking forward to hearing the other reviewer’s opinion.\n\n**Improvements**\n\n1) As stated earlier, my main criticism is that the “distributional shift” hypothesis is never verified and no alternative explanations are provided as to why pruning rates in RL seem to be generally lower. At the current stage I would phrase the finding as a (sensible) hypothesis that needs further investigation rather than an established finding.\n    * 1a: One control experiment that comes to my mind is to run the behavioral cloning baseline on data across the full “lifetime” of an RL agent, including the early exploration phase and thus exhibiting the same distributional shift throughout supervised training. \n    * 1b: One alternative explanation not related to distributional shift is that the supervised and RL learning signal might be qualitatively different and thus lead to the different pruning rates (not entirely sure how to test that though). \n    * 1c: If the hypothesis is true there should also be observable qualitative effects for tasks where this distributional shift is large compared to tasks where the distributional shift is small.\n    * 1d: See 3 for more alternatives related to exploration.\n\n2) Another limitation that should ideally be noted more explicitly is that most findings are based on PPO (an on-policy algorithm) with fewer experiments for DQN (off-policy). Large parts of the paper are written as if the findings were established in general about RL. While the paper certainly does a great job of supporting the main claims with broad sets of experiments, I think it would be nice to point out a small hint of caution (e.g. in the limitations section) regarding the generality of findings in the off-policy setting.\n\n3) Clarification: how is exploration in the RL algorithms implemented? Is it baked in via a fixed epsilon-greedy action-selection? Is there some annealing of the exploration strength? \n    * 3a: If the policy has to account for exploration as well (e.g. through some entropy regularization) this might be another explanation why pruning rates in RL are lower - because the policy needs to be more complex than the supervised policy. \n    * 3b: If the RL algorithm is using fixed epsilon-greedy (no annealing), is this taken into account when generating the expert data for the behavioral cloning baseline (i.e. using an expert with the same epsilon)? If not, the data-distribution for RL (even at the end of training) is potentially much broader compared to the behavioral cloning baseline which could also be a reason for the lower pruning rates in RL.\n", "summary_of_the_paper": "**Update after reading the other reviews and authors' responses:** Some valid criticism has been raised and addressed by the authors to a reasonable degree (given e.g. the limitations of a conference-format paper). Given all current information I remain in favor of accepting the paper (my score and confidence remains unchanged).\n\n**Summary:**\n\nThe paper investigates the lottery-ticket effect in detail in reinforcement learning tasks. While it has been shown before that lottery-tickets also exist in deep reinforcement learning, this paper performs a thorough analysis using (i) both discrete and continuous action- and observation-spaces, (ii) an on- and an off-policy RL algorithm (as well as a behavioral cloning baseline), and (iii) careful ablations to distinguish the importance of the binary mask and the initial weight values which together form a winning ticket. Various controls and ablations are performed, leading to a plethora of experimental results. The main result is that winning tickets can be found efficiently via iterative magnitude-based pruning in RL tasks, and that in many tasks the binary mask contributes more to performance than the initial weight values. Compared to the supervised (behavioral cloning) baseline, RL performance degrades more rapidly with increasing sparsity levels which is attributed to the distributional shift introduced by exploration in RL. Finally, the paper also investigates the effect of pruning (in winning tickets) of the first-layer weights, and shows that in many cases multiple input dimensions (or regions, which are often semantically meaningful) can be pruned without loss in task performance. This observation could be an interesting approach to producing sparse input representations in RL.\n\n**Main contributions**\n\n1) Investigation of the lottery ticket effect in RL. Significance: though it has been reported before that winning tickets can be found in RL, the paper performs an impressive amount of empirical investigations, including many baselines and ablations across a range of continuous and discrete tasks and an on- and off-policy RL algorithm as well as a supervised baseline. Naturally, results vary somewhat between settings and variations, but the sheer number of results allows to extract trends that hold across many variations. This significantly increases the reliability of the findings.\n2) Disentangling the lottery ticket effect through control experiments that allow to attribute the effect strength to (i) the binary mask, (ii) the initial weight-values, or (iii) the layer-specific pruning ratios, which are all combined in a winning ticket. Significance: these control experiments shed some important light on the role of the three components. Interestingly, the binary mask seems to play the most important role in RL tasks, whereas initial weight-values seem to matter more in the supervised setting. This is an interesting, and very consistent insight which might spawn further investigation into the topological structure induced by the winning mask.\n\n3) Investigation of first-layer weights of winning tickets. In many cases whole input dimensions (in continuous tasks) or input regions (in discrete tasks) that are irrelevant to the problem are pruned. This reflects an important (implicit?) regularizing effect - the corresponding weights remain at low magnitudes and can be safely pruned. Investigation of the pruning patterns or pruned dimensions also provides semantic insight which allows for interesting hypotheses regarding how the network solves the task and which information it ignores. Significance: this is an interesting artifact of the analysis of winning tickets in RL. Results are promising and ask for further investigation and perhaps even formulation of a method for sparse/compressed input representations for RL (the identified irrelevant dimensions also transfer to non-pruned architectures).\n", "summary_of_the_review": "An impressive empirical paper that investigates many findings regarding the lottery ticket effect found in other domains to RL tasks and algorithms. The paper presents results for a large number of tasks (with continuous and discrete observation- and action-spaces), and loads of relevant controls, baselines and ablations. The main finding is that iterative magnitude-based pruning can effectively find winning tickets in RL, and that there are some qualitative differences between RL and supervised learning (masks seem to be more relevant than initial-weight values of winning tickets). I only have some small criticism regarding one hypothesis, and whether it can be stated as empirically verified given the current set of experiments. Currently I think the paper is interesting and relevant to a large part of the ICLR community and vote in favor of accepting the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the Lottery Ticket hypothesis in reinforcement learning for identifying good sparse representations for low-dimensional tasks. The paper received initial reviews tended towards acceptance. However, the reviewers had some clarification questions and concerns. The authors provided a thoughtful rebuttal. The paper was discussed and most reviewers updated their reviews in the post-rebuttal phase. Reviewers generally agree that the paper should be accepted but still have good feedback. AC agrees with the reviewers and suggests acceptance. However, the authors are urged to look at reviewers' feedback and incorporate their comments in the camera-ready.
Decision: Accept (Spotlight)