論文の概要: Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2302.08617v1
• Date: Thu, 16 Feb 2023 23:01:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-20 16:24:18.879335
• Title: Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning
• Title（参考訳）: エピソード強化学習における指数レギュレット改善のための量子コンピューティング
• Authors: Bhargav Ganguly and Yulian Wu and Di Wang and Vaneet Aggarwal
• Abstract要約: 有限水平MDPの学習を容易にするために,textitUpper Confidence Bound (UCB) ベースの量子アルゴリズムフレームワークを提案する。 我々の量子アルゴリズムは、古典的なアルゴリズムと比較して、後悔の指数的な改善を実現している。
• 参考スコア（独自算出の注目度）: 35.11103784048256
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the problem of \textit{episodic reinforcement learning} with quantum oracles for state evolution. To this end, we propose an \textit{Upper Confidence Bound} (UCB) based quantum algorithmic framework to facilitate learning of a finite-horizon MDP. Our quantum algorithm achieves an exponential improvement in regret as compared to the classical counterparts, achieving a regret of $\Tilde{\mathcal{O}}(1)$ as compared to $\Tilde{\mathcal{O}}(\sqrt{K})$ \footnote{$\Tilde{\mathcal{O}}(\cdot)$ hides logarithmic terms.}, $K$ being the number of training episodes. In order to achieve this advantage, we exploit efficient quantum mean estimation technique that provides quadratic improvement in the number of i.i.d. samples needed to estimate the mean of sub-Gaussian random variables as compared to classical mean estimation. This improvement is a key to the significant regret improvement in quantum reinforcement learning. We provide proof-of-concept experiments on various RL environments that in turn demonstrate performance gains of the proposed algorithmic framework.
• Abstract（参考訳）: 本稿では,状態進化のための量子神託を用いた \textit{episodic reinforcement learning} の問題について検討する。 そこで本研究では,有限水平MDPの学習を容易にするために, UCB(textit{Upper Confidence Bound})に基づく量子アルゴリズムフレームワークを提案する。 我々の量子アルゴリズムは、古典的手法と比較して、後悔の指数的な改善を達成し、$\Tilde{\mathcal{O}}(1)$を$\Tilde{\mathcal{O}}(\sqrt{K})$ \footnote{$\Tilde{\mathcal{O}}(\cdot)$と比較すると、対数項を隠蔽する。 K$はトレーニングエピソードの数だ。 この利点を達成するために、古典平均推定と比較して、サブガウシアン確率変数の平均を推定するために必要なi.i.d.サンプル数を二次的に改善する効率的な量子平均推定手法を利用する。 この改善は、量子強化学習における重大な後悔の改善の鍵である。 提案するアルゴリズムフレームワークの性能向上を示す,様々なrl環境における概念実証実験を行う。

関連論文リスト

• Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
  量子振幅の推定は、量子コンピューティングの基本的な課題である。 純状態を行列形式に変換することによって量子振幅を推定するための新しい枠組みを提案する。 我々のフレームワークは、それぞれ標準量子極限$epsilon-2$とハイゼンベルク極限$epsilon-1$を達成する。
  論文  参考訳（メタデータ） (2024-08-25T04:35:53Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradients [51.82488018573326]
  重み付きニューラルネットワークのトレーニングに適した,新しいレイヤワイドオプティマイザであるQP-SBGDを提案する。 BNNは、深層学習モデルの計算要求とエネルギー消費を最小限の精度で削減する。 提案アルゴリズムは階層的に実装されており,リソース制限量子ハードウェア上での大規模ネットワークのトレーニングに適している。
  論文  参考訳（メタデータ） (2023-10-23T17:32:38Z)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  我々は,未知のMDPとエージェントのエンゲージメントのための革新的な量子フレームワークを提案する。 平均推定における量子的優位性は、無限の地平線強化学習に対する後悔の保証において指数的な進歩をもたらすことを示す。
  論文  参考訳（メタデータ） (2023-10-18T03:17:51Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-19T18:00:05Z)
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
  量子強化学習(RL)のための新しいUCRL型アルゴリズムを提案する。 我々は$mathcalO(mathrmpoly(S, A, H, log T))$ the worst-case regret for it, where $T$ is the number of episodes。 具体的には、$d$次元線形表現を持つ線形混合MDPに対する値目標回帰(VTR)に基づく量子アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-21T16:23:11Z)
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits [0.0]
  量子回路Bornマシンを$f$-divergencesを使ってトレーニングすることを検討する。 ボルンマシンのトレーニングを実証的に改善するアルゴリズムを2つ導入する。 量子デバイスによる$f$-divergencesの長期的影響について論じる。
  論文  参考訳（メタデータ） (2021-10-08T17:04:18Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。