論文の概要: Nested Elimination: A Simple Algorithm for Best-Item Identification from
Choice-Based Feedback
- arxiv url: http://arxiv.org/abs/2307.09295v1
- Date: Thu, 13 Jul 2023 05:05:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-23 12:06:44.620134
- Title: Nested Elimination: A Simple Algorithm for Best-Item Identification from
Choice-Based Feedback
- Title（参考訳）: Nested Elimination: 選択に基づくフィードバックからのベスト項目識別のための簡易アルゴリズム
- Authors: Junwen Yang, Yifan Feng
- Abstract要約: 選択に基づくフィードバックから最良項目識別の問題について検討する。
この問題において、企業は、顧客集団に順次かつ適応的に表示セットを表示し、その選択を収集する。
情報理論の下界にインスパイアされたネスト構造にインスパイアされた,除去に基づくアルゴリズムNested Elimination(NE)を提案する。
- 参考スコア（独自算出の注目度）: 8.043586007062858
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the problem of best-item identification from choice-based feedback.
In this problem, a company sequentially and adaptively shows display sets to a
population of customers and collects their choices. The objective is to
identify the most preferred item with the least number of samples and at a high
confidence level. We propose an elimination-based algorithm, namely Nested
Elimination (NE), which is inspired by the nested structure implied by the
information-theoretic lower bound. NE is simple in structure, easy to
implement, and has a strong theoretical guarantee for sample complexity.
Specifically, NE utilizes an innovative elimination criterion and circumvents
the need to solve any complex combinatorial optimization problem. We provide an
instance-specific and non-asymptotic bound on the expected sample complexity of
NE. We also show NE achieves high-order worst-case asymptotic optimality.
Finally, numerical experiments from both synthetic and real data corroborate
our theoretical findings.
- Abstract（参考訳）: 選択に基づくフィードバックから最良項目識別の問題を検討する。
この問題において、企業は顧客集団に表示セットを順次かつ適応的に表示し、選択を収集する。
その目的は、最少のサンプル数と高い信頼度で、最も好ましいアイテムを特定することである。
本稿では,情報理論下界に暗示されるネスト構造に触発された除去に基づくアルゴリズムであるネスト除去(ne)を提案する。
NEは構造がシンプルで実装が容易で、サンプルの複雑さに対する理論的な保証が強い。
具体的には、NEは革新的な除去基準を利用し、複雑な組合せ最適化問題の解決を回避している。
ne のサンプル複雑性に対するインスタンス固有かつ非漸近的境界を提供する。
また、NEは高次最悪の漸近的最適性を達成することを示す。
最後に、合成データと実データの両方による数値実験は、我々の理論的知見を裏付けるものである。
関連論文リスト
- Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes [9.321976218862542]
プールベースのアクティブラーニングでは、学習者にラベルのないデータセットが与えられ、データポイントのラベルをクエリすることで未知の仮説を効率的に学習することを目的としている。
これは古典的最適決定木(ODT)問題として定式化できる: テストのセット、仮説のセット、各テストと仮説に対する結果が与えられた場合、我々の目標は、真の仮説を識別する低コストなテスト手順(すなわち決定木)を見つけることである。
本研究では,ODT問題の基本的変種について検討し,実験結果がうるさい場合,さらに一般的な場合であっても検討する。
論文 参考訳（メタデータ） (2023-12-23T21:47:50Z) - Dual-Directed Algorithm Design for Efficient Pure Exploration [9.728332815218181]
有限組の代替品を用いた逐次適応実験の文脈における純粋探索問題を考える。
固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。
我々のアルゴリズムは、$varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
論文 参考訳（メタデータ） (2023-10-30T07:29:17Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。