論文の概要: Quantum Heavy-tailed Bandits
- arxiv url: http://arxiv.org/abs/2301.09680v1
- Date: Mon, 23 Jan 2023 19:23:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 14:55:37.345820
- Title: Quantum Heavy-tailed Bandits
- Title（参考訳）: 量子ヘビーテールバンド
- Authors: Yulian Wu, Chaowen Guan, Vaneet Aggarwal and Di Wang
- Abstract要約: 重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。
まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。
量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 36.458771174473924
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study multi-armed bandits (MAB) and stochastic linear
bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the
previous work on quantum bandits that assumes bounded/sub-Gaussian
distributions for rewards, here we investigate the quantum bandits problem
under a weaker assumption that the distributions of rewards only have bounded
$(1+v)$-th moment for some $v\in (0,1]$. In order to achieve regret
improvements for heavy-tailed bandits, we first propose a new quantum mean
estimator for heavy-tailed distributions, which is based on the Quantum Monte
Carlo Mean Estimator and achieves a quadratic improvement of estimation error
compared to the classical one. Based on our quantum mean estimator, we focus on
quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the
Upper Confidence Bound (UCB) framework for both problems with
$\Tilde{O}(T^{\frac{1-v}{1+v}})$ regrets, polynomially improving the dependence
in terms of $T$ as compared to classical (near) optimal regrets of
$\Tilde{O}(T^{\frac{1}{1+v}})$, where $T$ is the number of rounds. Finally,
experiments also support our theoretical results and show the effectiveness of
our proposed methods.
- Abstract（参考訳）: 本稿では,重み付き報酬と量子報酬オラクルを用いたマルチアームバンディット(MAB)と確率線形バンディット(SLB)について検討する。
ここでは、報酬に対する有界/準ガウス分布を仮定する以前の量子包帯に関する研究とは異なり、報酬の分布は、ある$v\in (0,1]$に対して(1+v)$-第モーメントしか持たないというより弱い仮定の下で量子包帯問題を研究する。
まず,重み付きバンディットに対する後悔的な改善を達成するために,量子モンテカルロ平均推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。
量子平均推定器に基づき、量子重み付きMABおよびSLBに着目し、$Tilde{O}(T^{\frac{1-v}{1+v}})と$T$(T^{\frac{1-v}{1+v}})と$T$(T^{\frac{1+v}})の両方の問題に対するアッパー信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
最後に,実験は理論結果をサポートし,提案手法の有効性を示す。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - 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) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳（メタデータ） (2023-10-09T03:10:42Z) - Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
論文 参考訳（メタデータ） (2023-08-03T14:41:49Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Quantum advantages for transportation tasks: projectiles, rockets and
quantum backflow [0.0]
我々は、同じ運動量分布を持つどの古典粒子よりも到着確率が高い「超高速」量子状態が存在することを発見した。
発射体とロケットの両方にとって、量子的優位性は、量子的および最適古典的到達確率の違いによって定量化され、ブラッケン・メロイ定数$c_bm$で制限される。
論文 参考訳（メタデータ） (2022-09-01T20:56:00Z) - Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy
Logarithmic Regrets [20.426493569846855]
強化学習において,マルチアーム・バンディット(MAB)とリニア・バンディット(SLB)は重要なモデルである。
両モデルに対して$O(mboxpoly(log T))$ regrets を用いて量子アルゴリズムを提案する。
これは、バンディット問題に対する後悔と、強化学習における一般的な利用に対する最初の証明可能な量子スピードアップである。
論文 参考訳（メタデータ） (2022-05-30T10:54:53Z) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。