論文の概要: Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

• arxiv url: http://arxiv.org/abs/2205.14988v1
• Date: Mon, 30 May 2022 10:54:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-31 18:45:15.408658
• Title: Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
• Title（参考訳）: 量子多腕バンディットと確率線形バンディットは対数的後悔を味わう
• Authors: Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, Xiaoming Sun
• Abstract要約: 強化学習において,マルチアーム・バンディット(MAB)とリニア・バンディット(SLB)は重要なモデルである。 両モデルに対して$O(mboxpoly(log T))$ regrets を用いて量子アルゴリズムを提案する。 これは、バンディット問題に対する後悔と、強化学習における一般的な利用に対する最初の証明可能な量子スピードアップである。
• 参考スコア（独自算出の注目度）: 20.426493569846855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $\Omega(\sqrt{T})$ regret. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with $O(\mbox{poly}(\log T))$ regrets, exponentially improving the dependence in terms of $T$. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.
• Abstract（参考訳）: 強化学習におけるマルチアームバンディット (mab) と確率線形バンディット (slb) は重要なモデルであり、時間軸を持つバンディットに対する古典的アルゴリズムは$t$が$\omega(\sqrt{t})$ regretを被る。 本稿では,MAB と SLB を量子報酬オーラクルで検討し,$O(\mbox{poly}(\log T))$ regrets を用いて両方のモデルに対して量子アルゴリズムを提案し,その依存性を$T$ で指数関数的に改善する。 私たちの知る限りでは、これが初めて証明可能な量子スピードアップであり、バンディット問題の後悔と強化学習の一般的な活用です。 従来のMABと強化学習の量子探索アルゴリズムと比較して、我々の量子入力モデルはより単純であり、個々のアームに量子オラクルを仮定するのみである。

関連論文リスト

• Differential Privacy of Quantum and Quantum-Inspired-Classical Recommendation Algorithms [2.36119616330904]
  量子レコメンデーションアルゴリズムと量子インスパイアされた古典的レコメンデーションアルゴリズムのDP特性を解析する。 量子レコメンデーションアルゴリズムは、独自のプライバシキュレーション機構であり、外部ノイズを必要としないことが分かりました。 比較すると、量子アルゴリズムは古典的アルゴリズムよりもプライバシー保護の可能性が高いことが示される。
  論文  参考訳（メタデータ） (2025-02-07T08:45:00Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• 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)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Quantum Heavy-tailed Bandits [36.458771174473924]
  重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。 まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。 量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-23T19:23:10Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
  量子量$k$-juntasの検証と学習の問題を考察する。 a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。 我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
  論文  参考訳（メタデータ） (2022-07-13T00:11:14Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum exploration algorithms for multi-armed bandits [15.666205208594567]
  我々は、$tildeObigl(sqrtsum_i=2nDeltasmash-2_ibigr)$quantum query.sqrtsum_i=2nDeltasmash-2_ibigr)を用いて、信頼度の高い最適なアームを見つけることができることを示す。 このアルゴリズムは、可変時間振幅増幅と推定に基づいて、可能な限りの古典的な結果と比較して二次的なスピードアップを与える。
  論文  参考訳（メタデータ） (2020-07-14T14:15:20Z)
• Quantum Bandits [10.151012770913622]
  我々は、エム・ベスト・アーム・アイデンティティ(BAI)として知られるバンディット問題の量子バージョンを考える。 まず,学習エージェントと環境の両方が量子であると仮定した,BAI問題の量子モデリングを提案する。 次に,BAIを解くために,量子振幅増幅に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-15T15:17:11Z)

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

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