論文の概要: Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach

• arxiv url: http://arxiv.org/abs/2307.09295v2
• Date: Wed, 01 Jan 2025 15:20:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-03 17:39:34.612709
• Title: Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach
• Title（参考訳）: 選択に基づくフィードバックから選択とランク付けを学習する:シンプルなネステッドアプローチ
• Authors: Junwen Yang, Yifan Feng,
• Abstract要約: 本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.293894471295205
• License:
• Abstract: We study a ranking and selection problem of learning from choice-based feedback with dynamic assortments. In this problem, a company sequentially displays a set of items to a population of customers and collects their choices as feedback. The only information available about the underlying choice model is that the choice probabilities are consistent with some unknown true strict ranking over the items. The objective is to identify, with the fewest samples, the most preferred item or the full ranking over the items at a high confidence level. We present novel and simple algorithms for both learning goals. In the first subproblem regarding best-item identification, we introduce an elimination-based algorithm, Nested Elimination (NE). In the more complex subproblem regarding full-ranking identification, we generalize NE and propose a divide-and-conquer algorithm, Nested Partition (NP). We provide strong characterizations of both algorithms through instance-specific and non-asymptotic bounds on the sample complexity. This is accomplished using an analytical framework that characterizes the system dynamics through analyzing a sequence of multi-dimensional random walks. We also establish a connection between our nested approach and the information-theoretic lower bounds. We thus show that NE is worst-case asymptotically optimal, and NP is optimal up to a constant factor. Finally, numerical experiments from both synthetic and real data corroborate our theoretical findings.
• Abstract（参考訳）: 本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 この問題において、企業は一連のアイテムを顧客の集団に順次表示し、その選択をフィードバックとして収集する。 基礎となる選択モデルに関する唯一の情報は、選択確率がアイテムに対する真の厳密なランキングと一致していることである。 目的は、最も少ないサンプル、最も好まれるアイテム、あるいは高い信頼度レベルでアイテムよりも完全なランキングを識別することである。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。 最良項目識別に関する最初のサブプロブレムでは、除去に基づくアルゴリズム、Nested Elimination (NE)を導入する。 フルランク識別に関するより複雑なサブプロブレムでは、NEを一般化し、Nested Partition (NP) という分割・分散アルゴリズムを提案する。 本研究は, サンプルの複雑性について, 事例特異的および非漸近的境界を用いて, 両方のアルゴリズムの特性を強く評価する。 これは、多次元ランダムウォークのシーケンスを分析することによって、システムダイナミクスを特徴付ける分析フレームワークを用いて達成される。 また、ネストしたアプローチと情報理論の下界との接続を確立する。 したがって, NE は漸近的に最適であり, NP は定数因子まで最適である。 最後に、合成データと実データの両方による数値実験は、我々の理論的知見を裏付けるものである。

関連論文リスト

• 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)

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

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