Playing Atari Space Invaders with Sparse Cosine Optimized Policy Evolution
Jim O’Connor, Jay B. Nash, Derin Gezgin, Gary B. Parker · 2025
Read Playing Atari Space Invaders with Sparse Cosine Optimized Policy Evolution by Jim O’Connor, Jay B. Nash, Derin Gezgin, Gary B. Parker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08526.txt.
Introduction
Jim O'Connor and co-authors teach, in a 2025 paper, an evolved game-playing policy for the arcade classic Space Invaders that shrinks its input first. Evolution-based learning works in many domains but strains on video games. The screen's huge state space forces huge policies, and the search space balloons.
Their method compresses the screen with a sparse cosine transform before evolving the policy. A meaningful picture survives in far fewer numbers. The smaller policy evolves faster toward competent play. The trick addresses a general bottleneck: raw perception is too rich for direct evolution. Any robot learning from cameras faces the same flood, so compression-first evolution may travel.
Catalog record
| CREATOR | Jim O’Connor, Jay B. Nash, Derin Gezgin, Gary B. Parker |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-08526
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Playing Atari Space Invaders with Sparse Cosine Optimized Policy Evolution Jim O’Connor, Jay B. Nash, Derin Gezgin, Gary B. Parker Abstract Evolutionary approaches have previously been shown to be effective learning methods for a diverse set of domains. However, the domain of game-playing poses a particular challenge for evolutionary methods due to the inherently large state space of video games. As the size of the input state expands, the size of the policy must also increase in order to effectively learn the temporal patterns in the game space. Consequently, a larger policy must contain more trainable parameters, exponentially increasing the size of the search space. Any increase in search space is highly problematic for evolutionary methods, as increasing the number of trainable parameters is inversely correlated with convergence speed. To reduce the size of the input space while maintaining a meaningful representation of the original space, we introduce Sparse Cosine Optimized Policy Evolution (SCOPE). SCOPE utilizes the Discrete Cosine Transform (DCT) as a pseudo attention mechanism, transforming an input state into a coefficient matrix. By truncating and applying sparsification to this matrix, we reduce the dimensionality of the input space while retaining the highest energy features of the original input. We demonstrate the effectiveness of SCOPE as the policy for the Atari game Space Invaders. In this task, SCOPE with CMA-ES outperforms evolutionary methods that consider an unmodified input state, such as OpenAI-ES and HyperNEAT. SCOPE also outperforms simple reinforcement learning methods, such as DQN and A3C. SCOPE achieves this result through reducing the input size by 53% from 33,600 to 15,625 then using a bilinear affine mapping of sparse DCT coefficients to policy actions learned by the CMA-ES algorithm. The results presented in this paper demonstrate that the use of SCOPE allow evolutionary computation to achieve results competitive with reinforcement learning methods and far beyond what previous evolutionary methods have achieved. 1 Introduction Policy learning for game-playing agents has been extensively explored, with many approaches utilizing large policy networks learned via gradient decent, self-play, neuroevolution, and other methods ( Pearce and Zhu 2022 ; Schrittwieser et al. 2020 ; Hausknecht et al. 2014 ) . Atari 2600 games and the Atari Learning Environment have developed as a middle ground between traditional board games and modern, complex video games ( Bellemare et al. 2013 ) . A key difference between board games, which are generally dominated by tree searching methods ( Cowling et al. 2013 ) , and video games is the presence of noise and irrelevant information. In most cases, this noise must be directly handled by the policy or filtered out by some other method ( Mnih et al. 2015 ) . Existing noise-filtering techniques have been shown to be effective in a variety of circumstances, but these techniques greatly increase the dimensionality of the overall policy. While increasing the number of free parameters in a policy is often more effective for gradient-based methods, this generally causes the efficacy of derivative-free optimization methods to decrease. This decrease in efficacy is due to additional free parameters increasing the dimensionality of the search space, and thus increasing the difficulty of optimization without the use of a gradient. In order to avoid increasing the number of free parameters to account for the high dimensional input, SCOPE utilizes the Discrete Cosine Transform (DCT) to compress the input ( Strang 1999 ) . The DCT is a domain-agnostic tool that is widely used in applications such as image encoding ( Ahmed, Natarajan, and Rao 1974 ; Watson et al. 1994 ) , where it is valued for its ability to concentrate signal energy into a small number of low-frequency components ( Rao and Yip 1990 ) . When applied to neural learning methods, the DCT has been shown to be capable of a type of pseudo-attention as well as showing the ability to augment standard attention methods ( Scribano et al. 2023 ; Dang et al. 2024 ; Nguyen and Kuo 2024 ) . Additionally, DCT has been applied to extract additional features from input images to classifier models, which resulted in an increase to classification accuracy on standard benchmarks ( Lee and Kim 2023 ) . We aim to leverage this pseudo-attention as an all-in-one dimensionality reduction solution, enabling an evolved policy to process a much larger number of inputs than otherwise would be feasible. In addition to the DCT, SCOPE enforces sparsification in the input coefficient matrix by zeroing out all coefficients below a predefined percentile threshold. This step effectively discards low‐energy components typically corresponding to high‐frequency noise or redundant visual detail, where energy is the absolute magnitude of the coefficient. By retaining only the top‐energy coefficients, we reduce the number of active inputs, which in turn allows the subsequent affine mapping to be realized with fewer weights. Moreover, as the specific positions of the retained coefficients can shift over time, the affine mapping implicitly adapts its receptive “focus” without any explicit attention mechanism, yielding a flexible yet lightweight representation for CMA-ES to optimize ( Hansen 2006 ) . 2 Related Work The Atari 2600 platform has served as a benchmark for general AI agents due to its diverse game dynamics and simple interface ( Bellemare et al. 2013 ) . Early work in this area emphasized general game-playing capabilities over domain-specific heuristics. These approaches relied on methods such as linear function approximation with handcrafted features, object-centric representations like Object-Oriented MDPs (OO-MDPs), and planning algorithms that utilized perfect emulators or forward models ( Diuk, Cohen, and Littman 2008 ) . Feature extraction methods like BASS and DISCO aimed to capture color-based patterns or object classes directly from the screen ( Naddaf 2010 ) , while others leveraged RAM-level observations to model the internal game state. 2.1 Reinforcement Learning Approaches Mnih et al. 2013 introduced the first reinforcement learning approaches to ALE through their use of Deep Q-Networks (DQNs) which they used to learn control policies directly from high-dimensional pixel inputs ( Mnih et al. 2013 ) . Follow-up work by Sorokin et al. 2015 extended this approach by including recurrent layers, attention mechanisms, and Hasselt, Guez, and Silver 2016 introduced Double Q-Learning to address the training instabilities found in previous methods ( Sorokin et al. 2015 ; Hasselt, Guez, and Silver 2016 ) . Consequently, Distributional Reinforcement Learning (DistRL) was introduced by Bellemare, Dabney, and Munos 2017 as a follow-up to existing DQN-based solutions ( Bellemare, Dabney, and Munos 2017 ) . Improving upon the success of DistRL in the Atari Learning Environment, Dabney et al. 2018b introduced Quantile Regression DQN (QR-DQN) ( Dabney et al. 2018b ) . QR-DQN re-parametrized the distribution of the returns by fixing probabilities and learning value locations through quantile regression. Implicit Quantile Networks (IQN) introduced by Dabney et al. 2018a further extended QR-DQN by learning a continuous quantile function, rather than value locations ( Dabney et al. 2018a ) . This improvement allowed IQN to represent a wider family of return distributions, resulting in improved performance across the Atari benchmark. Following the success of Q-Learning based approaches on the Atari benchmark, Schulman et al. 2017 utilized Proximal Policy Optimization (PPO) as a scalable, robust and simple method for training game agents ( Schulman et al.