Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Technical Summary: Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Problem Statement
Monte Carlo (MC) reinforcement learning faces significant challenges regarding sample efficiency, particularly in environments characterized by sparse rewards, large state spaces, and temporally correlated trajectories. Standard MC methods rely on the assumption that data samples are independent and identically distributed (i.i.d.), an assumption violated by the Markovian nature of RL trajectories. Consequently, MC estimators suffer from:

1. Variance Propagation: Returns exhibit compounding variance, requiring a number of episodes ($N_s$) that scales as $O(\epsilon^{-2})$ to reduce estimation error.
2. Suboptimal Trajectory Dilution: In sparse-reward domains, the estimator is diluted by low-reward trajectories, necessitating exponential growth in sample size to ensure sufficient coverage of optimal paths.
3. Combinatorial Explosion: Theoretically, selecting an optimal subset of $m$ episodes from $N$ candidates to maximize value estimation accuracy is an NP-hard problem isomorphic to feature selection and set cover, with a solution space of $\binom{N}{m}$.

Methodology
The authors propose MC+QUBO, a framework that reformulates the episode selection process as a Quadratic Unconstrained Binary Optimization (QUBO) problem. Instead of using all sampled episodes for policy updates, the method filters a batch of trajectories to select a subset that maximizes cumulative reward while promoting state-space coverage (diversity).

• QUBO Formulation: The selection problem is encoded as:
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  Where:

  • $x_i = 1$ indicates the selection of episode $\tau_i$.
  • $R_i$ is the cumulative reward of episode $i$.
  • $w_{ij}$ represents the pairwise similarity between episodes (e.g., Jaccard similarity of visited state sets).
  • $\alpha$ is a reward-scaling multiplier, and $\gamma$ weights the similarity penalty.
  • The linear term ($-\alpha R_i$) favors high-reward episodes, while the quadratic term ($\gamma w_{ij}$) penalizes redundancy, encouraging the selection of diverse trajectories.

• Quantum-Inspired Solvers: The QUBO problem is solved using black-box quantum-inspired samplers, specifically Simulated Quantum Annealing (SQA) and Simulated Bifurcation (SB).

  • SQA mimics quantum annealing using classical stochastic updates and path-integral Monte Carlo to simulate quantum tunneling between energy minima.
  • SB utilizes a classical dynamical system approach where continuous variables evolve toward binary states via bifurcation phenomena.
  • The authors treat these solvers as oracles that provide high-quality approximate solutions within practical computational budgets.

• Integration: The workflow involves generating a batch of episodes, computing rewards and similarities, formulating the QUBO, dispatching it to the solver, and using the best-observed solution (the binary vector $x^*$) to determine which episodes are used to update the action-value table $Q(s, a)$ via first-visit MC.

Key Contributions

1. Reformulation of Episode Selection: The paper establishes a formal link between MC episode selection and combinatorial optimization, demonstrating that the selection problem can be mapped to a QUBO formulation.
2. Algorithmic Integration: It introduces a concrete pipeline (Algorithm 2) that inserts a QUBO-based filtering step between trajectory sampling and policy evaluation in standard MC learning.
3. Empirical Validation: The study evaluates the method on finite-horizon GridWorld environments of varying sizes ($3\times3$ to $20\times20$), comparing MC+QUBO against a vanilla MC baseline.

Results
Experiments conducted in GridWorld environments demonstrate that MC+QUBO consistently outperforms vanilla MC in terms of convergence speed and final policy quality.

• Scalability: The performance gap widens in larger environments ($\ge 10\times10$), where sparse rewards and exponential state-space growth typically hinder standard MC evaluation.
• Convergence: MC+QUBO converges in fewer batches by focusing learning on informative and diverse trajectories, effectively filtering out redundant episodes.
• Design Insight: The authors note that prioritizing state-space coverage (setting the reward weight influence close to zero) yielded more balanced learning and better generalization than reward-driven selection, which tended to cause faster but less stable convergence.
• Solver Performance: Quantum-inspired solvers (SQA and SB) outperformed classical heuristics (such as Tabu Search and Simulated Annealing) in this context. The computational latency was dominated by cloud communication rather than the solver time itself (which was negligible for $n \le 200$).

Significance and Claims
The paper claims that integrating quantum-inspired optimization as a decision-making subroutine in reinforcement learning offers a practical enhancement to MC methods, particularly for problems with sparse rewards and correlated trajectories. By bridging RL with combinatorial optimization, the study suggests a pathway for algorithms where quantum and quantum-inspired methods actively guide the learning process to overcome sample inefficiency.

The authors remain modest regarding the scope, noting that while the framework shows promise in GridWorld, future work is required to explore extensions to continuous control, hierarchical RL, and multi-agent systems, as well as the deployment on real quantum hardware. The current work serves as a proof-of-concept for using physics-inspired solvers to optimize the data selection phase of reinforcement learning.