  Reinforcement learning is a powerful framework aiming to determine optimal
behavior in highly complex decision-making scenarios. This objective can be
achieved using policy iteration, which requires to solve a typically large
linear system of equations. We propose the variational quantum policy iteration
(VarQPI) algorithm, realizing this step with a NISQ-compatible quantum-enhanced
subroutine. Its scalability is supported by an analysis of the structure of
generic reinforcement learning environments, laying the foundation for
potential quantum advantage with utility-scale quantum computers. Furthermore,
we introduce the warm-start initialization variant (WS-VarQPI) that
significantly reduces resource overhead. The algorithm solves a large
FrozenLake environment with an underlying 256x256-dimensional linear system,
indicating its practical robustness.
