Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

• URL: http://arxiv.org/abs/2310.11684v3
• Date: Sun, 28 Apr 2024 20:04:52 GMT
• Title: Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes
• Authors: Bhargav Ganguly, Yang Xu, Vaneet Aggarwal,
• Abstract summary: We introduce an innovative quantum framework for the agent's engagement with an unknown MDP. We show that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning.
• Score: 32.07657827173262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of $\tilde{\mathcal{O}}(1)$, a significant improvement over the $\tilde{\mathcal{O}}(\sqrt{T})$ bound exhibited by classical counterparts.

Related papers

• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach. The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions [0.0]
  It reviews state-of-the-art approaches, including analytical algorithms, strategies, machine learning based methods, and hybrid quantum-classical frameworks. The paper highlights the strengths and limitations of each method, along with the challenges they pose.
  arXiv  Detail & Related papers  (2024-08-16T15:07:51Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Evaluating the Convergence of Tabu Enhanced Hybrid Quantum Optimization [58.720142291102135]
  We introduce the Tabu Enhanced Hybrid Quantum Optimization metaheuristic approach useful for optimization problem solving on a quantum hardware. We address the theoretical convergence of the proposed scheme from the viewpoint of the collisions in the object which stores the tabu states, based on the Ising model.
  arXiv  Detail & Related papers  (2022-09-05T07:23:03Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Circuit Symmetry Verification Mitigates Quantum-Domain Impairments [69.33243249411113]
  We propose circuit-oriented symmetry verification that are capable of verifying the commutativity of quantum circuits without the knowledge of the quantum state. In particular, we propose the Fourier-temporal stabilizer (STS) technique, which generalizes the conventional quantum-domain formalism to circuit-oriented stabilizers.
  arXiv  Detail & Related papers  (2021-12-27T21:15:35Z)
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms [1.1682745573995112]
  We consider digitized-counterdiabatic quantum computing as an advanced paradigm to approach quantum advantage for industrial applications in the NISQ era. Our analysis shows a drastic improvement in the success probabilities of the resulting digital quantum algorithm when approximate counterdiabatic techniques are introduced.
  arXiv  Detail & Related papers  (2021-12-15T18:55:02Z)
• Direct Quantum Communications in the Presence of Realistic Noisy Entanglement [69.25543534545538]
  We propose a novel quantum communication scheme relying on realistic noisy pre-shared entanglement. Our performance analysis shows that the proposed scheme offers competitive QBER, yield, and goodput.
  arXiv  Detail & Related papers  (2020-12-22T13:06:12Z)
• K-spin Hamiltonian for quantum-resolvable Markov decision processes [0.0]
  We derive a pseudo-Boolean cost function that is equivalent to a K-spin Hamiltonian representation of the discrete, finite, discounted Markov decision process. This K-spin Hamiltonian furnishes a starting point from which to solve for an optimal policy using quantum algorithms.
  arXiv  Detail & Related papers  (2020-04-13T16:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.