論文の概要: Pure Exploration with Structured Preference Feedback

• arxiv url: http://arxiv.org/abs/2104.05294v1
• Date: Mon, 12 Apr 2021 08:57:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-13 14:01:07.437274
• Title: Pure Exploration with Structured Preference Feedback
• Title（参考訳）: 構造的選好フィードバックによる純粋探索
• Authors: Shubham Gupta, Aadirupa Saha, and Sumeet Katariya
• Abstract要約: 我々は、機能付きN$アームを含むサブセットワイドな選好フィードバックによる純粋探索の問題を考察する。 我々は,$tildeo (fracd2k delta2)$サンプル中の最良アームの検出を少なくとも1.99ドルで保証する2つのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 25.894827160719526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of pure exploration with subset-wise preference feedback, which contains $N$ arms with features. The learner is allowed to query subsets of size $K$ and receives feedback in the form of a noisy winner. The goal of the learner is to identify the best arm efficiently using as few queries as possible. This setting is relevant in various online decision-making scenarios involving human feedback such as online retailing, streaming services, news feed, and online advertising; since it is easier and more reliable for people to choose a preferred item from a subset than to assign a likability score to an item in isolation. To the best of our knowledge, this is the first work that considers the subset-wise preference feedback model in a structured setting, which allows for potentially infinite set of arms. We present two algorithms that guarantee the detection of the best-arm in $\tilde{O} (\frac{d^2}{K \Delta^2})$ samples with probability at least $1 - \delta$, where $d$ is the dimension of the arm-features and $\Delta$ is the appropriate notion of utility gap among the arms. We also derive an instance-dependent lower bound of $\Omega(\frac{d}{\Delta^2} \log \frac{1}{\delta})$ which matches our upper bound on a worst-case instance. Finally, we run extensive experiments to corroborate our theoretical findings, and observe that our adaptive algorithm stops and requires up to 12x fewer samples than a non-adaptive algorithm.
• Abstract（参考訳）: 我々は、機能付きN$アームを含むサブセットワイドな選好フィードバックによる純粋探索の問題を考察する。 学習者は、$K$のサブセットをクエリでき、ノイズの多い勝者の形でフィードバックを受け取ることができる。 学習者の目標は、可能な限り少ないクエリを使用して、最適なアームを効率的に識別することである。 この設定は、オンライン小売、ストリーミングサービス、ニュースフィード、オンライン広告などの人間のフィードバックを含む様々なオンライン意思決定シナリオに関係している。 私たちの知る限りでは、これは構造的な設定で部分的な選好フィードバックモデルを検討する最初の仕事であり、潜在的に無限のアームセットを可能にする。 我々は,$\tilde{o} (\frac{d^2}{k \delta^2})$サンプルにおける最良アームの検出を少なくとも$\delta$で保証する2つのアルゴリズムを提案する。 また、インスタンス依存の下位境界である$\Omega(\frac{d}{\Delta^2} \log \frac{1}{\delta})$を導出します。 最後に、我々は理論的な発見を裏付ける広範な実験を行い、適応アルゴリズムが停止し、非適応アルゴリズムよりも最大12倍少ないサンプルを必要とすることを観察した。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Selective Sampling for Online Best-arm Identification [19.767267982167578]
  潜在的なオプションのセットが与えられた場合、学習者は1-delta$以上の確率で計算することを目指している。 この研究の主な成果は、ラベル付きサンプルと停止時間の間のトレードオフを正確に特徴づけるものである。 我々のフレームワークは、以前の作業で改善されたバイナリ分類をキャプチャするのに十分な一般性を持っている。
  論文  参考訳（メタデータ） (2021-10-28T03:02:08Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• 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)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。