Recurrent Neural Networks (RNNs) have been shown to be valuable forconstructing Intrusion Detection Systems (IDSs) for network data. They allowdetermining if a flow is malicious or not already before it is over, making itpossible to take action immediately. However, considering the large number ofpackets that have to be inspected, the question of computational efficiencyarises. We show that by using a novel Reinforcement Learning (RL)-basedapproach called SparseIDS, we can reduce the number of consumed packets by morethan three fourths while keeping classification accuracy high. Comparing tovarious other sampling techniques, SparseIDS consistently achieves higherclassification accuracy by learning to sample only relevant packets. A majornovelty of our RL-based approach is that it can not only skip up to apredefined maximum number of samples like other approaches proposed in thedomain of Natural Language Processing but can even skip arbitrarily manypackets in one step. This enables saving even more computational resources forlong sequences. Inspecting SparseIDS's behavior of choosing packets shows thatit adopts different sampling strategies for different attack types and networkflows. Finally we build an automatic steering mechanism that can guideSparseIDS in deployment to achieve a desired level of sparsity.