論文の概要: Quantum exploration algorithms for multi-armed bandits
- arxiv url: http://arxiv.org/abs/2007.07049v2
- Date: Tue, 15 Dec 2020 18:31:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 15:34:55.654387
- Title: Quantum exploration algorithms for multi-armed bandits
- Title(参考訳): 多腕バンディットの量子探索アルゴリズム
- Authors: Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs
- Abstract要約: 我々は、$tildeObigl(sqrtsum_i=2nDeltasmash-2_ibigr)$quantum query.sqrtsum_i=2nDeltasmash-2_ibigr)を用いて、信頼度の高い最適なアームを見つけることができることを示す。
このアルゴリズムは、可変時間振幅増幅と推定に基づいて、可能な限りの古典的な結果と比較して二次的なスピードアップを与える。
- 参考スコア(独自算出の注目度): 15.666205208594567
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Identifying the best arm of a multi-armed bandit is a central problem in
bandit optimization. We study a quantum computational version of this problem
with coherent oracle access to states encoding the reward probabilities of each
arm as quantum amplitudes. Specifically, we show that we can find the best arm
with fixed confidence using
$\tilde{O}\bigl(\sqrt{\sum_{i=2}^n\Delta^{\smash{-2}}_i}\bigr)$ quantum
queries, where $\Delta_{i}$ represents the difference between the mean reward
of the best arm and the $i^\text{th}$-best arm. This algorithm, based on
variable-time amplitude amplification and estimation, gives a quadratic speedup
compared to the best possible classical result. We also prove a matching
quantum lower bound (up to poly-logarithmic factors).
- Abstract(参考訳): マルチアームバンディットの最適腕を特定することは、バンディット最適化における中心的な問題である。
我々は、各アームの報酬確率を量子振幅としてエンコードする状態に対するoracleの一貫性のあるアクセスを用いて、この問題の量子計算版を研究した。
具体的には、$\tilde{O}\bigl(\sqrt{\sum_{i=2}^n\Delta^{\smash{-2}}_i}\bigr)$量子クエリーを用いて、最適な腕と$i^\text{th}$-bestアームの平均的な報酬の差を表す。
このアルゴリズムは、可変時間振幅増幅と推定に基づいて、最良の古典的結果と比較して二次的なスピードアップを与える。
また、(多対数因子まで)一致する量子下界も証明する。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Quantum Heavy-tailed Bandits [36.458771174473924]
重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。
まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。
量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-23T19:23:10Z) - 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) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。
C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
論文 参考訳(メタデータ) (2021-09-10T15:41:07Z) - Continuous Time Bandits With Sampling Costs [17.412117389855222]
連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。
サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。
目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
論文 参考訳(メタデータ) (2021-07-12T10:00:35Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳(メタデータ) (2021-02-15T19:10:52Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳(メタデータ) (2021-01-21T10:35:09Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z) - Quantum Bandits [10.151012770913622]
我々は、エム・ベスト・アーム・アイデンティティ(BAI)として知られるバンディット問題の量子バージョンを考える。
まず,学習エージェントと環境の両方が量子であると仮定した,BAI問題の量子モデリングを提案する。
次に,BAIを解くために,量子振幅増幅に基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-15T15:17:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。