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

Hyun Kyu Lee, Joongheon Kim, Sung Whan YoonICML 2026 · OpenReview

Reinforcement Learning (RL) agents frequently struggle when transitioning from simulated training environments to the real world—a challenge widely known as the "sim-to-real gap." Robust Reinforcement Learning (RRL) attempts to bridge this gap by training agents to optimize their policies against the worst-case scenarios within a defined set of environmental variations, known as the uncertainty set ($\mathcal{U}$).

However, RRL has historically faced a massive computational bottleneck. To find the worst-case scenario at every training step, classical RRL algorithms must exhaustively scan through every possibility in the uncertainty set. As the uncertainty set grows to accommodate more complex real-world variables—such as varying friction, mass, or wind conditions—this "inner minimization" process scales linearly, $\mathcal{O}(|\mathcal{U}|)$, making RRL impractical for high-dimensional tasks.

This paper introduces Quantum Robust Inner Minimization (QRIM), a novel method that leverages quantum algorithms to solve this primary bottleneck. By utilizing quantum superposition and minimum-finding techniques, QRIM achieves a quadratic speed-up in searching for worst-case environmental scenarios, reducing query complexity to $\mathcal{O}(\sqrt{|\mathcal{U}|})$ without requiring modifications to the outer RL training pipeline.

The Quantum Solution: QRIM

QRIM reframes the search for the worst-case scenario as a quantum search problem. Recognizing that the RRL bottleneck is essentially an unstructured search, the authors apply a "quantum lens" to exploit the native advantages of quantum computing. The approach relies on three core components:

  1. Quantum-Accessible Environment: The framework assumes an interface where the environment can be queried in quantum superposition. This allows the agent to evaluate multiple potential next states and rewards simultaneously, rather than sequentially.
  2. Quantum Amplitude Estimation (QAE): Instead of running numerous classical simulations to estimate the expected return of a specific scenario, QRIM employs QAE. This provides a quadratic improvement in the precision dependence of the expected return estimates.
  3. Quantum Minimum Finding (QMF): Building on Grover’s algorithm, QMF is utilized to efficiently identify the index within the uncertainty set that produces the minimum return.

Crucially, QRIM is designed as a modular, "drop-in" replacement for the inner loop of standard RL algorithms. Whether integrated with value-based methods like Q-Learning or policy-gradient methods like PPO, QRIM accelerates training by replacing the classical exhaustive search.

Experimental Validation and Key Results

The researchers evaluated QRIM across both discrete and continuous control benchmarks:

  • FrozenLake-8x8 (Tabular): A navigation task where uncertainty was introduced via different hole layouts and varying slip probabilities.
  • CartPole Swingup (Continuous Control): A classic physics task with uncertainty in pole length, pole mass, and damping coefficients.
  • Real Hardware Validation: Experiments were also conducted on the IBM 127-qubit Eagle processor to test the algorithm's viability under real-world quantum noise.

Massive Query Reduction

The theoretical quadratic speed-up translated into significant empirical gains. In the CartPole benchmark, QRIM required 79.5% fewer queries than classical RRL to reach convergence. In the FrozenLake environment, it used only 35.9% of the classical query count.

Superior Robustness and Noise Resilience

Policies trained with QRIM significantly outperformed non-robust classical RL in out-of-distribution tests. In CartPole extrapolation tests, QRIM maintained a much higher mean return than its classical counterparts. Surprisingly, QRIM maintained its robustness even on Noisy Intermediate-Scale Quantum (NISQ) hardware. On the IBM 127-qubit system, QRIM achieved an extrapolation return of -0.52. While slightly lower than the noise-free simulation (-0.37), it remained far superior to the non-robust classical baseline (-0.79), proving that imperfect quantum gates can still successfully identify "bad" scenarios well enough to train a robust policy.

Limitations and Future Directions

While QRIM presents a major theoretical and practical leap for RRL, several challenges remain:

  • Oracle Complexity: Constructing the "quantum-accessible environment" (the oracle) for highly complex physics engines requires deep quantum circuits that currently exceed the limits of near-term hardware.
  • Communication Overhead: The hybrid setup—a classical outer loop paired with a quantum inner loop—introduces communication latency between the CPU and QPU, which can offset speed-up gains in terms of actual wall-clock time.
  • Scaling to Deep RL: The current experiments focused on relatively small uncertainty sets. Future work must explore how QRIM scales when the uncertainty set is continuous or exponentially large.

By successfully reducing the query complexity of the RRL inner loop, QRIM provides a promising blueprint for the future of scalable, robust reinforcement learning powered by quantum computing.

Summary updated

Abstract

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.
BibTeX
@inproceedings{lee2026quantum,
  author = {Hyun Kyu Lee and Joongheon Kim and Sung Whan Yoon},
  title = {{Quantum Robust Inner Minimization for Reinforcement Learning with Quadratic Speed-Up in Query Complexity}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=6rTth6ujE2},
}
Figure