Fugu-MT 論文翻訳(概要): Multi-Armed Bandits and Quantum Channel Oracles

論文の概要: Multi-Armed Bandits and Quantum Channel Oracles

arxiv url: http://arxiv.org/abs/2301.08544v3
Date: Mon, 26 Feb 2024 08:47:32 GMT
ステータス: 処理完了
システム内更新日: 2024-02-27 19:47:26.577364
Title: Multi-Armed Bandits and Quantum Channel Oracles
Title（参考訳）: マルチアームバンドと量子チャネルオラクル
Authors: Simon Buchholz, Jonas M. K\"ubler, Bernhard Sch\"olkopf
Abstract要約: 我々は、報酬のランダム性に制限されたアクセスしか持たないバンディットモデルを導入するが、それでも重ね合わせの腕に問い合わせることができる。これは、オラクルが正の故障確率を持つ場合、非構造化探索ではスピードアップが不可能である、という事前の結果を一般化する。
参考スコア（独自算出の注目度）: 17.50587686418541
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability.
Abstract（参考訳）: 多腕バンディットは強化学習の理論的柱の1つである。近年,マルチアームバンディット問題に対する量子アルゴリズムの研究が開始され,腕と腕の報酬のランダム性が重ね合わせで問合せ可能な場合,二次的なスピードアップ(クエリ複雑性)が可能であることが判明した。ここでは,報酬のランダム性への限定的なアクセスしかできないが,重ね合わせで腕を照会できる,さらなるバンディットモデルを紹介する。クエリの複雑さは古典的なアルゴリズムと同じであることを示す。これにより、オラクルが正の故障確率を持つ場合、非構造化探索ではスピードアップができないという事前結果が一般化される。

関連論文リスト

A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
論文参考訳（メタデータ） (2024-01-25T17:13:51Z)
Bandit Social Learning: Exploration under Myopic Behavior [58.75758600464338]
オンラインプラットフォーム上でのレビューによって動機付けられた社会学習のダイナミクスについて検討する。エージェントはまとめて単純なマルチアームのバンディットプロトコルに従うが、各エージェントは探索を伴わずにミオプティカルに振る舞う。このような振る舞いに対して,スターク学習の失敗を導出し,好意的な結果を提供する。
論文参考訳（メタデータ） (2023-02-15T01:57:57Z)
Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文参考訳（メタデータ） (2021-05-22T02:46:04Z)
Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-13T12:25:41Z)
Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文参考訳（メタデータ） (2020-10-07T01:33:06Z)
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)
A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-05-23T19:52:44Z)
Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文参考訳（メタデータ） (2020-03-05T21:29:27Z)
The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文参考訳（メタデータ） (2020-02-03T04:58:51Z)
Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文参考訳（メタデータ） (2020-01-23T16:47:52Z)

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