論文の概要: Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
- arxiv url: http://arxiv.org/abs/2402.14013v1
- Date: Wed, 21 Feb 2024 18:52:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 14:06:41.424022
- Title: Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
- Title（参考訳）: 誤解、学習、ランキング: ユーザーの注意を限定した活用
- Authors: Arpit Agarwal, Rad Niazadeh, Prathamesh Patil
- Abstract要約: 本稿では,最適ベンチマークに対する後悔を解消するオンラインアルゴリズムの設計について検討する。
逆オンライン線形最適化の標準的なアルゴリズムは、$O(sqrtT)$ regretのペイオフ時間アルゴリズムを得るためにどのように使用できるかを示す。
- 参考スコア（独自算出の注目度）: 16.74322664734553
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In digital health and EdTech, recommendation systems face a significant
challenge: users often choose impulsively, in ways that conflict with the
platform's long-term payoffs. This misalignment makes it difficult to
effectively learn to rank items, as it may hinder exploration of items with
greater long-term payoffs. Our paper tackles this issue by utilizing users'
limited attention spans. We propose a model where a platform presents items
with unknown payoffs to the platform in a ranked list to $T$ users over time.
Each user selects an item by first considering a prefix window of these ranked
items and then picking the highest preferred item in that window (and the
platform observes its payoff for this item). We study the design of online
bandit algorithms that obtain vanishing regret against hindsight optimal
benchmarks.
We first consider adversarial window sizes and stochastic iid payoffs. We
design an active-elimination-based algorithm that achieves an optimal
instance-dependent regret bound of $O(\log(T))$, by showing matching regret
upper and lower bounds. The key idea is using the combinatorial structure of
the problem to either obtain a large payoff from each item or to explore by
getting a sample from that item. This method systematically narrows down the
item choices to enhance learning efficiency and payoff.
Second, we consider adversarial payoffs and stochastic iid window sizes. We
start from the full-information problem of finding the permutation that
maximizes the expected payoff. By a novel combinatorial argument, we
characterize the polytope of admissible item selection probabilities by a
permutation and show it has a polynomial-size representation. Using this
representation, we show how standard algorithms for adversarial online linear
optimization in the space of admissible probabilities can be used to obtain a
polynomial-time algorithm with $O(\sqrt{T})$ regret.
- Abstract（参考訳）: デジタルヘルスとEdTechでは、レコメンデーションシステムは重大な課題に直面している。
この不一致は、長期の給与の増加を伴うアイテムの探索を妨げる可能性があるため、アイテムのランク付けを効果的に学ぶことが困難になる。
本稿では,ユーザの注意力の制限を生かしてこの問題に取り組む。
本稿では,プラットフォームが未払いのアイテムをランキングリストに表示し,時間とともに$T$ユーザに提示するモデルを提案する。
各ユーザは、まずこれらのランキング項目のプレフィックスウィンドウを考慮し、そのウィンドウ内で最も好まれる項目を選択してアイテムを選択する(そしてプラットフォームは、この項目に対する支払いを観察する)。
追従的最適ベンチマークに対する後悔を消失させるオンラインバンディットアルゴリズムの設計について検討した。
まず,adversarial window sizes と stochastic iid payoff について考察した。
我々は, 最適インスタンス依存後悔境界を$O(\log(T))$とし, 一致した後悔の上限と下限を示す能動消去アルゴリズムを設計する。
鍵となるアイデアは、問題の組合せ構造を使用して、各アイテムから大きな支払いを得るか、そのアイテムからサンプルを取得することで探索することです。
この方法は、学習効率とペイオフを高めるために、項目選択を体系的に絞り込む。
第二に、対向的なペイオフと確率的iidウィンドウサイズを考える。
私たちは、期待される支払いを最大化する置換を見つけるという完全な情報問題から始めます。
新たな組合せ論により,許容アイテム選択確率のポリトープを置換によって特徴付け,多項式サイズの表現を持つことを示す。
この表現を用いて、許容確率の空間における逆オンライン線形最適化の標準アルゴリズムを用いて、$o(\sqrt{t})$ regret の多項式時間アルゴリズムを得る方法を示す。
関連論文リスト
- Adaptively Learning to Select-Rank in Online Platforms [34.258659206323664]
本研究は、異種ユーザの候補プールからアイテムを適応的にランク付けすることの課題に対処する。
本研究では,多様なユーザの好みや項目位置の影響を考慮に入れたユーザ応答モデルを構築した。
シミュレーションと実世界の両方のデータセットで実施された実験は、アルゴリズムがベースラインを上回っていることを示している。
論文 参考訳（メタデータ） (2024-06-07T15:33:48Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
レコメンデーションシステムのようないくつかのアプリケーションでは、統計学者は主に大量のアイテムから上位のアイテムの集合を回収することに興味がある。
そこで本稿では,K$-recoveryの高速かつ高精度なランキングアルゴリズムとして,選択に基づくボルダカウントアルゴリズムを提案する。
選択に基づくボルダカウントアルゴリズムは,多種多様なランダム効用モデルの下で,上位$Kの回収に最適なサンプル複雑性を有することを示す。
論文 参考訳（メタデータ） (2022-06-23T22:05:08Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit [2.9998316151418107]
我々は、意思決定者が消費者に製品のサブセットを提供する動的集合最適化問題を考える。
MNL(Multinomial Logit)モデルを用いて消費者選択行動のモデル化を行う。
後悔は$O(sqrtdT + kappa)$で束縛され、既存のメソッドよりもパフォーマンスが大幅に向上していることを示す。
論文 参考訳（メタデータ） (2020-11-28T00:20:36Z) - Regret in Online Recommendation Systems [73.58127515175127]
本稿では,オンライン環境におけるレコメンデーションシステムの理論的分析について提案する。
各ラウンドにおいて、ユーザがランダムに$m$ユーザから選択され、レコメンデーションが要求される。決定者は、ユーザを観察し、$n$アイテムのカタログからアイテムを選択する。
推奨アルゴリズムのパフォーマンスは、これらの可能性を認識したOracleアルゴリズムを参照して、その後悔を通じて取得される。
論文 参考訳（メタデータ） (2020-10-23T12:48:35Z) - Learning to Rank under Multinomial Logit Choice [6.929312022493406]
コンテンツの最適順序付けを学ぶことは、ウェブサイト設計において重要な課題である。
本稿では,この問題に対する$Omega(sqrtJT)$lowbound,$tildeO(sqrtJT)$ upperbound on the regret of the UCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-07T16:15:12Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。
具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。
また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
論文 参考訳（メタデータ） (2020-02-23T06:40:48Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。