Fugu-MT 論文翻訳(概要): Quantum exploration algorithms for multi-armed bandits

論文の概要: 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アームの平均的な報酬の差を表す。このアルゴリズムは、可変時間振幅増幅と推定に基づいて、最良の古典的結果と比較して二次的なスピードアップを与える。また、(多対数因子まで)一致する量子下界も証明する。

関連論文リスト

A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文参考訳（メタデータ） (2024-09-08T12:19:12Z)
Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文参考訳（メタデータ） (2024-06-05T08:02:40Z)
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem [10.994427113326996]
この問題の例としては、$k$のアームがあり、それぞれの報酬関数は凹凸であり、腕が引き抜かれた回数の関数が増加する。任意のランダム化オンラインアルゴリズムに対して、最適報酬に対して少なくとも$Omega(sqrtk)$近似係数を負わなければならない事例が存在することを示す。次に、この仮定を余分な$O(sqrtk log k)$近似係数のコストで除去する方法を示し、全体的な$O(sqrtk)を達成する。
論文参考訳（メタデータ） (2024-04-01T15:55:45Z)
Quantum Heavy-tailed Bandits [36.458771174473924]
重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-23T19:23:10Z)
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)
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)

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