Year: 2021

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 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., 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.

text: 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 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., 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.

heading: 1 INTRODUCTION
text: 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 performance levels comparable to those of their dense counterparts. These results challenge the role of overparameterization in supervised learning and provide a new perspective on 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 optimization problem in deep reinforcement learning (DRL): The data-generation process is not static, but depends on the changing state of the neural network. Furthermore, a weight may serve different roles at different stages of learning (e.g. during exploration and exploitation). It is not obvious how a simple weight magnitude-based pruning heuristic acting on a well-performing policy shapes the learning process of the agent. In this work, we therefore investigate winning tickets in reinforcement 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 (e.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:
1. We show that winning tickets exist in both high-dimensional visual and control tasks (continuous/discrete). A positive lottery ticket effect is robustly observed for both off-policy DRL algorithms, including Deep-Q-Networks (DQN, Mnih et al., 2015) and on-policy policy-gradient 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), we show that networks trained with explicit supervision can be pruned to higher sparsity levels before performance starts to degrade, indicating that the RL problem requires a larger amount of parameters to address exploration, distribution shift & quality of the credit assignment signal (section 3.1).
3. By introducing a set of lottery ticket baselines (section 3; figure 1, middle column), we disentangle the contributions 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 important (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 eliminates 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 or 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 representations. Depending on the input size of different layers of the network, global magnitude-based pruning can introduce a strong layer-specific pruning bias. We compare initializations and show that a suitable initialization scheme enables the removal of task-irrelevant dimensions (section 4.2).

heading: 2 BACKGROUND AND RELATED WORK
text: 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).1 The lottery ticket effect refers to the performance gap between the sparse network obtained via IMP and a 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 parameter-matched random initializations. They obtained 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 a set of discrete control tasks. While they provide empirical evidence for the existence of lottery tickets in DRL, they did not investigate the underlying mechanisms. Here, we aim to unravel these mechanisms. To this end, we focus on a diverse set of environments and provide a detailed comparison between supervised behavioral cloning and on-/offpolicy Deep RL with a 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 et 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-parameterized agent.
Deep Reinforcement Learning Background. In our off-policy DRL experiments, we train DeepQ-Networks (DQN, Mnih et al., 2015) with double Q-learning 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 a baseline-corrected policy gradient algorithm which uses a clipping strategy to approximate a computationally expensive trust-region optimization method. For illustrative purposes, we train DQN agents on a visual navigation task, in which an agent has to collect coins in a 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 individual 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).
Supervised Behavioral Cloning. While most supervised learning relies on a stationary data distribution provided by a static dataset, reinforcement learning agents have to acquire their training data in an action-perception loop. Since the agent’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 et 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 policies.
1In 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 a later checkpoint (Frankle et al., 2019) is not necessary for obtaining tickets (SI figure 14).

heading: 3 DISENTANGLING TICKET CONTRIBUTIONS IN BC AND DEEP RL
text: There are two contributing factors to the lottery ticket effect: The IMP-identified binary mask and the preserved initialized weights that remain after pruning (mask/weights). We aim to disentangle the contributions by introducing a set of counterfactual baselines, which modify
the original IMP procedure (figure 1, 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/permuted). A second, weaker baseline estimates the contribution of the mask, by also permuting the layer-specific masks (permuted/permuted). 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.

heading: 3.1 COMPARING WINNING TICKETS IN SUPERVISED BEHAVIORAL CLONING AND DEEP RL
text: 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 in DRL should degrade for lower levels of sparsity than in a corresponding supervised task. To investigate this question, we turn to a behavioral cloning setting, in which a student agent is trained to 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 an 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 to 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 at significantly earlier stages of the IMP procedure. Hence, the covariate shift inherent to the RL problem increases the minimal required size of a winning ticket in the tasks studied here: More parameters are required for an agent that has to solve the additional exploration problem.

heading: 3.2 DISENTANGLING TICKET CONTRIBUTIONS IN SUPERVISED BEHAVIORAL CLONING
text: To disentangle the contributions of the initial weights and the weight mask to the ticket effect in supervised behavioral cloning, we 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 are 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 IMP-derived 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. Finally, 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-wise 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.

heading: 3.3 DISENTANGLING TICKET CONTRIBUTIONS IN DEEP REINFORCEMENT LEARNING
text: The observation that ticket information is mostly carried by the mask rather than the initial weights carries over to the full DRL setups (figure 1, bottom, right and figure 4).
When preserving the information contained in the mask, agents can be pruned to much higher levels of sparsity as compared to the case 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.2 Interestingly, ticket weights are more important for CNN-based agents (e.g., see ATARI plots). We provide further experimental evidence for this observation on four MinAtar games (Young & Tian, 2019) in the supplementary material (SI figure 10), where we compare MLP- and CNN-based agents. Unlike the behavioral cloning experiments, for some tasks the permuted/permuted baseline performs worse than the random/reinit configuration. This observation
2For further experiments investigating the role of different network capacities (SI figures 11, 12), state encoding (SI figure 13) and regularization (SI figure 14) we refer the interested reader to the SI.
only occurs for the PyBullet control tasks in which both the separate critic and actor networks were pruned (ACP). If instead, one 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.

heading: 4 MINIMALLY TASK-SUFFICIENT REPRESENTATIONS VIA IMP
text: The previous results establish the importance of the information contained in the mask for the success 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 to answer the following questions: 1) The derived mask can be thought of as a pair of goggles which guide the processing of state information. What do the masked MLPbased agents observe? 2) Can we transfer the input layer mask and re-use it as an inductive bias for otherwise dense agents? 3) How much influence do weight initialization and input dimensionality have on the discovered input layer mask?

heading: 4.1 MINIMAL TASK REPRESENTATIONS IN HIGH-DIMENSIONAL VISUAL TASKS
text: 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 for an IMPderived DQN agent, we find that IMP deletes entire dimensions from the observation vector (figure 5, 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 IMP-derived mask provides a compressed representation of a high-dimensional observation space, enabling successful training even at high levels of sparsity.
This result extends to masked input layers of MLP-agents trained on the MinAtar environments (figure 6 and SI). For the Freeway task we 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 a potential collision at the next time step in order to 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 it. There is no action-relevant information encoded and it can be discarded. In summary, we find that IMP-derived input layer mask provides a visually interpretable and physically meaningful compression of the observation space.

heading: 4.2 MINIMAL REPRESENTATIONS IN LOW-DIMENSIONAL CONTROL TASKS AND THE ISSUE
text: OF INITIALIZATION SCALES
The continuous and discrete control tasks, on the other hand, rely on low-dimensional state representations. 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 a 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 a 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 environment 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 laws are invariant with regard to the choice of the inertial frame of reference, so the input channels encoding 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 a two-link pendulum across a line as fast 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 a task and leverages them to prune the input representation 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 magnitudes across network layers. As a 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 downscaling 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 a slower separation of dimensions, larger factors result in overly aggressive pruning of the input layer. In summary, we have shown that the input layer initialization can shape the resulting lottery ticket mask and provide a first initialization heuristic promoting efficient minimal task representation discovery.

heading: 5 CONCLUSION
text: Summary. This work has investigated the mechanisms underlying the lottery ticket effect in behavioral 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 are qualitatively robust, they quantitatively vary across learning paradigms, algorithms, architectures and different tasks. Compared to our results, weight values have been claimed to play a more central role in the context of lottery tickets in supervised image classification (Frankle et al., 2020a). Future work will need to investigate under which conditions the initialization of the weight values significantly contributes to the ticket effect in RL. Furthermore, 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.
Future Work. In future work we want to investigate layer-wise effects, e.g., by studying layerspecific 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 studies 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 of hidden representations.

heading: REPRODUCIBILITY CHECKLIST BASED ON NEURIPS 2021 TEMPLATE
text: 1. For all authors... (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s
contributions and scope? [Yes] (b) Did you describe the limitations of your work? [Yes] See section 5. (c) Did you discuss any potential negative societal impacts of your work? [N/A] (d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes] 2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A] (b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main exper-
imental results (either in the supplemental material or as a URL)? [No] The code and instructions will be made available after publication.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See supplementary information.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] See captions of included figures.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See supplementary information.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a) If your work uses existing assets, did you cite the creators? [Yes] See supplementary
information. (b) Did you mention the license of the assets? [Yes] See supplementary information. (c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects... (a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount
spent on participant compensation? [N/A]
SUPPLEMENTARY INFORMATION: ON LOTTERY TICKETS AND MINIMAL

heading: TASK REPRESENTATIONS IN DEEP REINFORCEMENT LEARNING

heading: A ADDITIONAL RESULTS

heading: A.1 MINATAR DISTILLATION AND DQN RESULTS - MLP AND CNN-BASED AGENTS
text: 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 to 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.
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-
forming well even for high levels of sparsity, while agents trained on 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, we 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 generalize between different architectures indicating that the strength of the overall lottery ticket effect is mainly dictated by the combination of the task-specification of the environment and the DRL algorithm.

heading: A.2 THE EFFECT OF NETWORK CAPACITY ON THE ABSOLUTE SIZE OF WINNING TICKETS
text: The lottery ticket hypothesis suggests that using a 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 of 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 a strong effect on the relative performance gap between the ticket configuration (mask/weights) and the baseline (permuted/permuted). We suspect that larger networks can not realize their combinatorial potential due to a an unfavorable layer-wise pruning bias introduced by initialization schemes such as the Kaiming family (He et 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.

heading: A.4 THE EFFECT OF REGULARIZATION AND LATE REWINDING ON LOTTERY TICKETS IN

heading: A.3 THE EFFECT OF DIFFERENT REPRESENTATIONS ON LOTTERY TICKETS IN DRL

heading: A.5 PYBULLET DEEP RL PPO EXPERIMENTS WITHOUT PRUNING OF THE CRITIC

heading: B MAZEGRID ENVIRONMENT
text: The MazeGrid is a 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 in figure 1, bottom row, left column). The layout of the game is the same in every episode. The agent can 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 if the agent collects (walks over) all coins, or if the agent is in the same location as 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 of the environment, we compared three different representation of the MazeGrid 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 a total of 1200 binary values for each state.
• The RGB encoding consists of the canonical three color channels for each location, resulting 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 a time.
• The entangled encoding is derived from the object-map encoding by flattening all values into a vector and multiplying it with a pseudo-random 1200 by 1200 matrix. The matrix’s values are sampled independently from U(−1, 1). The matrix remains constant across all IMP iterations, every seed has its own matrix.
All experiments in the main text were conducted on 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 on RGB specifically.

heading: C HYPERPARAMETER SETTINGS FOR REPRODUCTION
text: 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 OpenAI 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 (Hunter, 2007) and Seaborn (Waskom, 2021, BSD-3-Clause License). Finally, the numerical analysis was supported by NumPy (Harris et al., 2020, BSD-3-Clause License). We will release the code after the publication of the paper. The simulations were conducted on a CPU cluster and no GPUs 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, a for lottery ticket experiment of 20 to 30 iterations lasts between 2 hours (Cart-Pole) and 5 (ATARI games) days of training time.

heading: C.2 ACROBOT - BEHAVIORAL CLONING & PPO

heading: C.1 CART-POLE - BEHAVIORAL CLONING & PPO

heading: C.4 GRIDMAZE - DQN

heading: C.3 PYBULLET CONTINUOUS CONTROL - BEHAVIORAL CLONING & PPO

heading: C.6 MINATAR - BEHAVIORAL CLONING & DQN FOR MLP/CNN AGENTS

heading: C.5 ATARI - PPO

Review summaries:
**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).  **Summary:**  The 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.  **Main contributions**  1) 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. 2) 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.  3) 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). 

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.