Deep neural networks have proven to be extremely useful for many tasks. However, they typically have large memory and compute requirements and so are difficult to deploy on small devices, e.g., mobiles. Pruning reduces the size of neural networks by removing (‘pruning’) neurons such that the performance drop is minimal. Traditional pruning approaches focus on designing metrics to quantify the 'usefulness' of a neuron. However, designing such metrics is often quite tedious and suboptimal. Some recent approaches have instead focused on training auxiliary neural networks to automatically learn how useful each neuron is in the network we wish to prune. In many cases, we are constrained in the amount of computational power that we can use. However, these auxiliary networks often do not take this into account. In this work, we focus on using constrained reinforcement learning algorithms to train these auxiliary neural networks to respect pre-defined computational budgets. We also present some preliminary results which indicate the effectiveness of our approach.