論文の概要: 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)フレームワークに基づく量子アルゴリズムを提案する。
最後に,実験は理論結果をサポートし,提案手法の有効性を示す。
関連論文リスト
- Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - 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) - Generalized Bayesian Upper Confidence Bound with Approximate Inference
for Bandit Problems [14.933622702326721]
我々は、一般化ベイズ的アッパー信頼境界(GBUCB)と呼ばれるベイズ的バンディットアルゴリズムを提案する。
我々の理論的分析は、ベルヌーイのマルチアームバンディットにおいて、シンメトリケートされたクルバック・リーブラーの発散によって測定された推論誤差が制御可能であれば、GBUCBは$O(sqrtT(log T)c)$ oftenist regretを達成できることを示している。
論文 参考訳（メタデータ） (2022-01-31T01:36:15Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-10-26T17:30:44Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。