論文の概要: Pure Exploration under Mediators' Feedback
- arxiv url: http://arxiv.org/abs/2308.15552v2
- Date: Fri, 12 Jan 2024 12:28:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-15 21:28:47.159212
- Title: Pure Exploration under Mediators' Feedback
- Title（参考訳）: 仲介者のフィードバックによる純粋探査
- Authors: Riccardo Poiani, Alberto Maria Metelli, Marcello Restelli
- Abstract要約: マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
- 参考スコア（独自算出の注目度）: 63.56002444692792
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic multi-armed bandits are a sequential-decision-making framework,
where, at each interaction step, the learner selects an arm and observes a
stochastic reward. Within the context of best-arm identification (BAI)
problems, the goal of the agent lies in finding the optimal arm, i.e., the one
with highest expected reward, as accurately and efficiently as possible.
Nevertheless, the sequential interaction protocol of classical BAI problems,
where the agent has complete control over the arm being pulled at each round,
does not effectively model several decision-making problems of interest (e.g.,
off-policy learning, partially controllable environments, and human feedback).
For this reason, in this work, we propose a novel strict generalization of the
classical BAI problem that we refer to as best-arm identification under
mediators' feedback (BAI-MF). More specifically, we consider the scenario in
which the learner has access to a set of mediators, each of which selects the
arms on the agent's behalf according to a stochastic and possibly unknown
policy. The mediator, then, communicates back to the agent the pulled arm
together with the observed reward. In this setting, the agent's goal lies in
sequentially choosing which mediator to query to identify with high probability
the optimal arm while minimizing the identification time, i.e., the sample
complexity. To this end, we first derive and analyze a statistical lower bound
on the sample complexity specific to our general mediator feedback scenario.
Then, we propose a sequential decision-making strategy for discovering the best
arm under the assumption that the mediators' policies are known to the learner.
As our theory verifies, this algorithm matches the lower bound both almost
surely and in expectation. Finally, we extend these results to cases where the
mediators' policies are unknown to the learner obtaining comparable results.
- Abstract（参考訳）: 確率的マルチアームバンディット(Stochastic multi-armed bandits)は、各インタラクションステップにおいて、学習者がアームを選択し、確率的報酬を観察するシーケンシャル意思決定フレームワークである。
最善の腕識別問題(bai)の文脈において、エージェントの目標は最適な腕(即ち最も期待された報酬を持つもの)を可能な限り正確かつ効率的に見つけることである。
それでも、エージェントが各ラウンドで引き出される腕を完全に制御する古典的BAI問題のシーケンシャルな相互作用プロトコルは、関心のある意思決定問題(例えば、非政治学習、部分的に制御可能な環境、人間からのフィードバック)を効果的にモデル化しない。
そこで,本研究では,仲介者のフィードバック(bai-mf)の下でのベストアーム識別と呼ぶ,古典bai問題の新たな厳密な一般化を提案する。
より具体的には、学習者が一組の仲介者にアクセスし、それぞれが確率的かつおそらく未知の方針に従ってエージェントの代理の腕を選択するシナリオを考える。
仲介者は、観察した報酬と共に、引き抜かれた腕とエージェントと通信する。
この設定では、エージェントの目標は、どのメディエーターに問い合わせて最適なアームを高い確率で識別するかを順次選択し、識別時間、すなわちサンプル複雑性を最小化することである。
この目的のために、我々はまず、一般的なメディエータフィードバックシナリオに特有のサンプルの複雑さの統計的下限を導出し分析する。
そこで我々は,仲介者の方針が学習者に知られていると仮定して,最良のアームを見つけるための逐次的意思決定戦略を提案する。
我々の理論が検証する通り、このアルゴリズムは下限とほぼ確実に一致する。
最後に、比較結果を得る学習者に対して、仲介者の方針が不明な場合に、これらの結果を拡張する。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳（メタデータ） (2024-10-08T09:49:47Z) - Optimal Regret Bounds for Collaborative Learning in Bandits [10.76667043339504]
一般的な協調型マルチエージェント・マルチアーム・バンディット・モデルにおける後悔について考察する。
このモデルの下では、順序最適後悔境界を持つ最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-15T10:36:13Z) - Online Decision Mediation [72.80902932543474]
意思決定支援アシスタントを学習し、(好奇心)専門家の行動と(不完全)人間の行動の仲介役として機能することを検討する。
臨床診断では、完全に自律的な機械行動は倫理的余裕を超えることが多い。
論文 参考訳（メタデータ） (2023-10-28T05:59:43Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
本稿では,各エージェントが有限個のアームに対向する一般マルチエージェントバンディットモデルを提案する。
ツイストは、各エージェントの最適なアームは最大の混合報酬を持つアームであり、アームの混合報酬は全てのエージェントに対するこのアームの報酬の重み付けの和である。
純粋探索のための近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-31T21:11:47Z) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。
本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
論文 参考訳（メタデータ） (2021-12-08T02:20:18Z) - Exploiting Heterogeneity in Robust Federated Best-Arm Identification [19.777265059976337]
Fed-SELは、逐次除去技術に基づく単純な通信効率のアルゴリズムであり、クライアントのローカルサンプリングステップを含む。
異種問題の場合、Fed-SELは1ラウンドの通信でベストアームを出力する。
最後のコントリビューションとして、フェデレーションとピアツーピア設定の両方を対象としてFed-SELの亜種を開発しました。
論文 参考訳（メタデータ） (2021-09-13T04:22:21Z) - Peer Selection with Noisy Assessments [43.307040330622186]
現在最も正確なピアレビューアルゴリズムであるPeerNominationをWeightedPeerNominationに拡張します。
重み付け方式により、選択の全体的な精度が大幅に向上できることを解析的に示す。
論文 参考訳（メタデータ） (2021-07-21T14:47:11Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Continuous Mean-Covariance Bandits [39.820490484375156]
本稿では,選択肢相関を考慮した連続平均共分散帯域モデルを提案する。
CMCBでは、与えられた選択肢の重みベクトルを逐次選択し、決定に従ってランダムなフィードバックを観察する学習者がいる。
最適な後悔(対数的因子を含む)を伴う新しいアルゴリズムを提案し、それらの最適性を検証するために一致した下界を提供する。
論文 参考訳（メタデータ） (2021-02-24T06:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。