Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization
Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov · 2026
Read Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization by Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17570.txt.
Introduction
Hadi Salloum and three co-authors speed up Monte Carlo reinforcement learning. That method learns from sampled episodes of play. It suffers high sample complexity. Sparse rewards, large state spaces, and correlated paths make it worse. The authors reformulate episode selection as a QUBO problem. QUBO is quadratic unconstrained binary optimization, a compact math form.
Quantum-inspired samplers then solve that selection problem. Picking the right episodes should cut wasted learning. Each episode costs time and compute to run. Smarter picks mean faster training for the same budget. The work joins quantum-style optimization with classic learning. It treats data choice as an optimization task in itself.
Catalog record
| CREATOR | Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-17570
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov Abstract Monte Carlo (MC) reinforcement learning suffers from high sample complexity, especially in environments with sparse rewards, large state spaces, and correlated trajectories. We address these limitations by reformulating episode selection as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solving it with quantum-inspired samplers. Our method, MC+QUBO, integrates a combinatorial filtering step into standard MC policy evaluation: from each batch of trajectories, we select a subset that maximizes cumulative reward while promoting state-space coverage. This selection is encoded as a QUBO, where linear terms favor high-reward episodes and quadratic terms penalize redundancy. We explore both Simulated Quantum Annealing (SQA) and Simulated Bifurcation (SB) as black-box solvers within this framework. Experiments in a finite-horizon GridWorld demonstrate that MC+QUBO outperforms vanilla MC in convergence speed and final policy quality, highlighting the potential of quantum-inspired optimization as a decision-making subroutine in reinforcement learning. † † volume: tbd † † year: 2025 † † workshop: International Conference on Computational Optimization 1 Introduction The Ising model 2 , originating in statistical mechanics, provides a fundamental framework for combinatorial optimization 9 ; 1 . Defined on an undirected graph G=(V,E) with |V|=n vertices, its Hamiltonian for spin configurations \mathbf{s}\in\{\pm 1\}^{n} is H_{\mathrm{Ising}}(\mathbf{s})=-\sum_{(i,j)\in E}J_{ij}s_{i}s_{j}-\sum_{i\in V}h_{i}s_{i}, (1) where J_{ij}\in\mathbb{R} represents pairwise couplings and h_{i}\in\mathbb{R} denotes local fields. For J_{ij}\geq 0 , the couplings are ferromagnetic (favoring aligned spins). The Quadratic Unconstrained Binary Optimization (QUBO) formulation provides an equivalent representation using binary variables: H_{\mathrm{QUBO}}(\mathbf{x})=\mathbf{x}^{\top}Q\mathbf{x}+\mathbf{q}^{\top}\mathbf{x},\qquad\mathbf{x}\in\{0,1\}^{n}, (2) where Q\in\mathbb{R}^{n\times n} is symmetric and may include diagonal terms encoding linear biases 17 ; 15 ; 13 ; 14 . The link between Ising spins and binary variables is given by: s_{i}=2x_{i}-1. (3) Substituting s_{i}s_{j}=4x_{i}x_{j}-2x_{i}-2x_{j}+1 into ( 1 ) and collecting terms yields: \displaystyle H_{\mathrm{Ising}}(\mathbf{s}) \displaystyle=\underbrace{\Big(-\sum_{i<j}J_{ij}+\sum_{i}h_{i}\Big)}_{C}+\sum_{i}\Big(2\sum_{j\neq i}J_{ij}-2h_{i}\Big)x_{i}+\sum_{i<j}(-4J_{ij})\,x_{i}x_{j}, (4) so that a QUBO representation is obtained with: Q_{ij}=-4J_{ij}\quad(i<j),\qquad q_{i}=2\sum_{j\neq i}J_{ij}-2h_{i}, and an additive constant C (irrelevant for optimization). Remark: different sign conventions for H_{\mathrm{Ising}} and H_{\mathrm{QUBO}} exist; the above is exact for the chosen convention. We consider the minimization form: \textsc{Min-QUBO:}\quad\min_{x\in\{0,1\}^{n}}F(x)=x^{\top}Qx+q^{\top}x. This is NP-hard : solving it exactly in polynomial time would imply \mathrm{P}=\mathrm{NP} . The related decision problem is: \textsc{QUBO-Decision:}\quad\text{Given }Q,q,T,\ \exists x\in\{0,1\}^{n}\ \text{with }F(x)\leq T? This is NP-complete. NP-hardness of Min-QUBO follows since an optimizer for all instances also solves the decision form 16 ; 12 . Proof sketch (reduction from Partition). Given positive integers a_{1},\dots,a_{n} and K=\frac{1}{2}\sum_{i}a_{i} , define: f(x)=\bigg(\sum_{i=1}^{n}a_{i}x_{i}-K\bigg)^{2}=x^{\top}(\mathbf{a}\mathbf{a}^{\top})x-2K\,\mathbf{a}^{\top}x+K^{2}. Set Q=\mathbf{a}\mathbf{a}^{\top} (rank 1), q=-2K\mathbf{a} , constant C=K^{2} . Then \min f(x)=0 iff there is a subset summing to K — i.e., a Partition solution ( ) . Approximability and special cases. • Some subclasses (e.g., MAX-CUT with nonnegative weights) admit constant-factor approximations (Goemans–Williamson \approx 0.878 ) 4 . • For arbitrary signed weights, uniform guarantees are generally impossible without structural restrictions. • Special cases (e.g., positive semidefinite Q with sparse structure) can be solved efficiently. Practical note. Because exact solution is often infeasible for large n , practical work uses: • Exact methods: integer programming, branch-and-bound for small/medium instances. • Relaxations: SDP, spectral methods for bounds plus rounding heuristics. • Heuristics: physics-inspired or metaheuristic approaches for large-scale best-effort solutions. Two quantum-inspired approaches to QUBO/Ising are Simulated Quantum Annealing (SQA) 3 and Simulated Bifurcation (SB) 5 . In this work, our aim is to integrate such solvers into reinforcement learning (RL) agents, enabling adaptive strategies that leverage physics-inspired optimization within decision-making frameworks. To the best of our knowledge, only a few works have explored RL–solver integration, and existing studies are limited in scope and quality. Figure 1 : Iterative Quantum-Assisted Reinforcement Learning — The policy generates multiple episodes, which are encoded as a QUBO and solved by a quantum black-box solver. The best sample guides the policy update, and the process repeats iteratively to converge toward the optimal policy. We therefore begin with a value-function-approximation RL setting and choose Monte Carlo methods as our starting point, as they provide a simple, unbiased baseline for exploring this integration. SQA mimics quantum annealing (please refer to 6 ; 10 understand the concept of quantum annealing and its mathematical foundation) using classical stochastic updates (e.g., path-integral Monte Carlo) rather than real quantum hardware. It interpolates between a driver Hamiltonian H_{0} and the problem Hamiltonian H_{P} : H_{\mathrm{SQA}}(t)=A(t)H_{0}+B(t)H_{P},\quad t\in[0,T], (5) with A(0)=1,\ B(0)=0 and A(T)=0,\ B(T)=1 . The simulation samples trajectories from an effective quantum partition function, using a discretized “imaginary time” dimension to represent quantum fluctuations. These fluctuations allow the simulated system to perform quantum-like tunneling between separated minima, a mechanism that can escape traps more efficiently than purely thermal hops in simulated annealing. The performance of SQA depends on the annealing schedule (A(t),B(t)) , the number of Trotter slices (which controls the resolution of quantum fluctuations), and the Monte Carlo update strategy. Proper tuning balances exploration (large quantum fluctuations) and exploitation (classical convergence) as t approaches T . While SQA is not a quantum algorithm in the strict sense, it inherits many behaviors of quantum annealing and is attractive as a software-based, hardware-independent tool. In the other hand, SB is a classical dynamical system approach that drives continuous variables toward binary states via bifurcation phenomena: \dot{x}_{i}=y_{i},\quad\dot{y}_{i}=-(\mu(t)-\lambda)x_{i}+\sum_{j}J_{ij}x_{j}-\gamma y_{i}. (6) Here \mu(t) ramps through a critical value \mu_{c}=\lambda+\rho(J) (spectral radius of J ), triggering a symmetry-breaking transition that favors low-energy configurations. Parameter choices for \gamma , \lambda , and the ramp schedule crucially influence solution quality, and empirical tuning is often necessary. Analogy and distinction. Both SQA and SB use gradual parameter changes to steer the system toward good solutions: • SQA uses stochastic sampling to emulate quantum transitions, with tunable quantum fluctuations. • SB uses deterministic dynamics with bifurcation-induced binary state formation. We treat both as black-box oracles: \mathbb{P}\big(H_{\mathrm{QUBO}}(\mathbf{x}^{*})\leq\min_{\mathbf{x}}H_{\mathrm{QUBO}}(\mathbf{x})+\delta\big)\geq 1-\eta, (7) allowing their integration into RL agents. Our starting point is to use quantum inspired computing as action-selection subroutines within Monte Carlo-based RL as shown in Figure 1 , building toward more sophisticated architectures. We will use the Qonquester Cloud platform by Q Deep to implement and run these quantum-inspired components 11 . 2 Sample Efficiency Limitations in Monte Carlo Reinforcement Learning A central limitation of most modern stochastic optimization methods is their reliance on the assumption that data samples are independently and identically distributed. In reinforcement learning, this assumption is inherently violated, as samples are temporally correlated through the underlying Markov decision process (MDP). Furthermore, the effective application of many algorithms presupposes knowledge of the MDP’s mixing time or asymptotic behavior. For MDPs with high-dimensional state spaces or sparse reward structures, the mixing time is often intractable to estimate 20 —if not entirely unknown—thereby restricting the applicability of such methods in practice. Monte Carlo (MC) methods estimate the value function based on the returns obtained from visiting a given state. However, these estimates are inherently tied to the policy under which the trajectories are generated, and that policy is not guaranteed to be optimal. Consequently, the value estimates may fail to converge to the optimal solution 8 ; 19 . A common remedy is to employ an exploration–exploitation strategy 18 , in which the agent occasionally takes random actions (exploration) to discover new states, while otherwise selecting actions according to the current value