Abstract: Computationally intractable tasks are ubiquitous in physics and optimization. Whereas variational approaches count amongst the most direct tools to find an optimal solution, they suffer from two main drawbacks: (i) non-convexity of the cost function and/or the feasible
set and (ii) they provide only an inner bound to the optimal solution. On the other hand, relaxation techniques, which allow for more efficient methods, provide outer bounds to the optimal solution. Hence, the combination of both, variational ansatze and relaxations, provide bounded intervals which contain the optimal solution, thus allowing for control of the optimization error.

We propose a novel approach combining the power of relaxation techniques with deep reinforcement learning (RL) to find the best possible relaxations given a limited computational budget. We illustrate the procedure in the context of ground state energy approximation. We showcase its validity in various scenarios where the ground states have different properties. Additionally, we benchmark the results against other optimization techniques and we study the effect of transfer learning. We highlight that our methods, while presented in the context of ground state energy approximation, are actually of much broader applicability, ranging, e.g. from entanglement witnesses optimization to device-independent quantum information processing tasks.