Quantum Robust Inner Minimization for Reinforcement Learning with Quadratic Speed-Up in Query Complexity

Robust reinforcement learning (RRL) aims to tackle unexpected environmental changes by optimizing policies against the worst case. However, RRL remains impractical due to the cost of the Max-Min optimization, where it suffers from the exhaustive query complexity for finding the worst-case (dubbed 'Min') within the environmental uncertainty set $\mathcal{U}$, i.e., $\mathcal{O}(|\mathcal{U}|)$. By viewing this via a lens of quantum perspective, we raise a pivotal question: *If we can query from the environment with quantum superpositions, is it possible to accelerate the Max-Min optimization of RRL?* Our answer is 'Yes'. Our method, called quantum robust inner minimization (QRIM), encodes the uncertainty set with quantum superposition and amplifies low-return cases, thus enabling RL for solving the robust (i.e., worst-case) Bellman equation. Importantly, QRIM achieves a quadratic speed-up in query complexity without altering the outer RL pipeline, i.e., $\mathcal{O}(\sqrt{|\mathcal{U}|})$. Validated through classical simulations to real quantum hardware execution, QRIM learns more robust policies with quadratically reduced queries than classical RL.

Robust reinforcement learning trains AI agents to perform reliably even when the deployment environment differs from the training environment. To achieve this, the agent learns by optimizing against the worst-case scenario within an uncertainty set that captures possible variations of the environment. However, identifying that worst case requires querying every candidate scenario, which becomes the dominant cost of training. We address this bottleneck through a quantum approach. Our method, QRIM, accesses the uncertainty set as a quantum-accessible environment and amplifies the worst case through a quantum search routine. This reduces the number of required queries from N to √N, a quadratic speed-up, without modifying the outer learning procedure. We validate QRIM in classical simulation and on IBM's 127-qubit quantum processor, where the speed-up holds even under hardware noise. The result illustrates how quantum approaches can be integrated into machine learning to address well-defined computational bottlenecks.