Combinatorial reinforcement learning

This thesis explores how reinforcement learning (RL) can be applied to combinatorial problems, both in explicit combinatorial optimisation (CO) and in tasks with high-dimensional discrete action spaces that have combinatorially many base-level actions. Initially, we demonstrate how RL can scale existing heuristic solvers to very large CO problem instances. We do this by pruning the problem space, learning to remove potential solutions unlikely to be optimal, allowing the heuristic to run more efficiently. We find we can remove up to 95% of the solution space, with the heuristic running 140x faster without significant performance degradation. We then apply RL to problems with high-dimensional discrete action spaces. Under the standard action representation, there would be an exponential number of actions to consider. Recent approaches utilise value-decomposition to learn about each dimension independently. Building on this work, we prove that certain value-decompositions can lead to lower bias but higher variance and propose an approach to address this. We support our theoretical analysis with thorough experiments, demonstrating state-of-the-art performance in the discretised variants of the DeepMind Control Suite (DMC) tasks. Finally, we extend this work by creating offline datasets for the discretised DMC tasks. Motivated by real-world applications with such action spaces and limited work in offline RL for discrete actions, we modify an existing offline RL algorithm for this context. We adapt a common regularisation term to be compatible with algorithms for high-dimensional discrete actions and perform thorough benchmarking on our datasets for both offline performance and online fine-tuning.