論文の概要: Bandits with Deterministically Evolving States
- arxiv url: http://arxiv.org/abs/2307.11655v1
- Date: Fri, 21 Jul 2023 15:43:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 12:08:08.664207
- Title: Bandits with Deterministically Evolving States
- Title(参考訳): 決定論的に進化する状態を持つバンディット
- Authors: Khashayar Khosravi, Renato Paes Leme, Chara Podimata, and Apostolis
Tsorvantzis
- Abstract要約: 本稿では,決定論的に進化し,観測不能な状態を考慮しながら,帯域幅フィードバックによる学習モデルを提案する。
我々のモデルにおけるワークホースの応用は、レコメンデーションシステムのための学習とオンライン広告のための学習である。
- 参考スコア(独自算出の注目度): 18.54931308524932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a model for learning with bandit feedback while accounting for
deterministically evolving and unobservable states that we call Bandits with
Deterministically Evolving States. The workhorse applications of our model are
learning for recommendation systems and learning for online ads. In both cases,
the reward that the algorithm obtains at each round is a function of the
short-term reward of the action chosen and how ``healthy'' the system is (i.e.,
as measured by its state). For example, in recommendation systems, the reward
that the platform obtains from a user's engagement with a particular type of
content depends not only on the inherent features of the specific content, but
also on how the user's preferences have evolved as a result of interacting with
other types of content on the platform. Our general model accounts for the
different rate $\lambda \in [0,1]$ at which the state evolves (e.g., how fast a
user's preferences shift as a result of previous content consumption) and
encompasses standard multi-armed bandits as a special case. The goal of the
algorithm is to minimize a notion of regret against the best-fixed sequence of
arms pulled. We analyze online learning algorithms for any possible
parametrization of the evolution rate $\lambda$. Specifically, the regret rates
obtained are: for $\lambda \in [0, 1/T^2]$: $\widetilde O(\sqrt{KT})$; for
$\lambda = T^{-a/b}$ with $b < a < 2b$: $\widetilde O (T^{b/a})$; for $\lambda
\in (1/T, 1 - 1/\sqrt{T}): \widetilde O (K^{1/3}T^{2/3})$; and for $\lambda \in
[1 - 1/\sqrt{T}, 1]: \widetilde O (K\sqrt{T})$.
- Abstract(参考訳): そこで本稿では,Bandits with Deterministically Evolving Statesと呼ぶ,決定論的に進化し,観測不能な状態を考慮しながら,帯域フィードバックによる学習モデルを提案する。
私たちのモデルのワークホースアプリケーションは、レコメンデーションシステムのための学習とオンライン広告のための学習です。
どちらの場合も、アルゴリズムが各ラウンドで得られる報酬は、選択されたアクションの短期的な報酬の関数であり、システムがどのように「健康」である(すなわち、その状態によって測定される)。
例えば、レコメンデーションシステムでは、プラットフォームが特定のタイプのコンテンツに対するユーザのエンゲージメントから得られる報酬は、特定のコンテンツの固有の特徴だけでなく、プラットフォーム上の他のタイプのコンテンツとのインタラクションの結果、ユーザの好みがどのように進化したかにも依存する。
我々の一般的なモデルは、状態が進化する異なるレートの$\lambda \in [0,1]$(例えば、以前のコンテンツ消費の結果、ユーザの嗜好がどれだけ速く変化するか)を考慮し、特殊なケースとして標準のマルチアームバンディットを包含する。
このアルゴリズムの目標は、最も固定されたアームのシーケンスに対する後悔の概念を最小化することである。
進化率$\lambda$のパラメータ化が可能なオンライン学習アルゴリズムを解析する。
具体的には、$\lambda \in [0, 1/t^2]$:$\widetilde o(\sqrt{kt})$;$\lambda = t^{-a/b}$ with $b < a < 2b$: $\widetilde o (t^{b/a})$;$\lambda \in (1/t, 1 - 1/\sqrt{t}): \widetilde o (k^{1/3}t^{2/3})$;$\lambda \in [1 - 1/\sqrt{t}, 1]: \widetilde o (k\sqrt{t})$;$;$\lambda \in [1 - 1/\sqrt{t}, 1]: \widetilde o (k\sqrt{t})$;$である。
関連論文リスト
- Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳(メタデータ) (2023-11-27T09:19:01Z) - Anytime Model Selection in Linear Bandits [61.97047189786905]
ALEXPは,その後悔に対するM$への依存を指数関数的に改善した。
提案手法は,オンライン学習と高次元統計学の新たな関連性を確立するために,ラッソの時間的一様解析を利用する。
論文 参考訳(メタデータ) (2023-07-24T15:44:30Z) - Improving Recommendation System Serendipity Through Lexicase Selection [53.57498970940369]
本稿では,レコメンデーションシステムにおけるエコーチャンバーとホモフィリーの存在を測定するための新しいセレンディピティー指標を提案する。
そこで我々は,レキシケース選択と呼ばれる親選択アルゴリズムを採用することにより,よく知られたレコメンデーション手法の多様性保存性の向上を試みる。
以上の結果から,レキシケースの選択とランキングの混合は,パーソナライゼーション,カバレッジ,セレンディピティー・ベンチマークにおいて,純粋にランク付けされている。
論文 参考訳(メタデータ) (2023-05-18T15:37:38Z) - How Bad is Top-$K$ Recommendation under Competing Content Creators? [43.2268992294178]
我々は,アナーキー価格のレンズによるユーザ福祉保証について検討する。
創造者競争によるユーザ福祉損失のごく一部は、ユーザ決定におけるKドルとランダム性に応じて、常に小さな一定値で上限づけられていることが示される。
論文 参考訳(メタデータ) (2023-02-03T19:37:35Z) - Recommendation Systems with Distribution-Free Reliability Guarantees [83.80644194980042]
我々は、主に良いアイテムを含むことを厳格に保証されたアイテムのセットを返す方法を示す。
本手法は, 擬似発見率の厳密な有限サンプル制御によるランキングモデルを提供する。
我々はYahoo!のランキングとMSMarcoデータセットの学習方法を評価する。
論文 参考訳(メタデータ) (2022-07-04T17:49:25Z) - Modeling Attrition in Recommender Systems with Departing Bandits [84.85560764274399]
政策に依存した地平線を捉えた新しいマルチアームバンディット構成を提案する。
まず、全てのユーザが同じタイプを共有しているケースに対処し、最近の UCB ベースのアルゴリズムが最適であることを実証する。
次に、ユーザが2つのタイプに分けられる、より困難なケースを前進させます。
論文 参考訳(メタデータ) (2022-03-25T02:30:54Z) - Learning the Optimal Recommendation from Explorative Users [38.332330484187395]
本研究では,レコメンデータシステムとユーザ間の逐次的インタラクションについて検討する。
効率的なシステム学習は依然として可能であるが、より困難であることを示す。
論文 参考訳(メタデータ) (2021-10-06T21:01:18Z) - DORB: Dynamically Optimizing Multiple Rewards with Bandits [101.68525259222164]
政策に基づく強化学習は、言語生成タスクにおいて、微分不可能な評価指標を最適化するための有望なアプローチであることが証明されている。
We use the Exp3 algorithm for bandit and formulate two approach for bandit rewards: (1) Single Multi-reward Bandit (SM-Bandit), (2) Hierarchical Multi-reward Bandit (HM-Bandit)
我々は,2つの重要なNLGタスクにおいて,様々な自動計測と人的評価を通じて,我々のアプローチの有効性を実証的に示す。
論文 参考訳(メタデータ) (2020-11-15T21:57:47Z) - Incentivising Exploration and Recommendations for Contextual Bandits
with Payments [2.5966580648312223]
本研究では,累積的社会福祉を最大化しながら,プラットフォームが項目固有の属性を学習し,サブリニアな後悔を実現する方法を示す。
弊社のアプローチは、eコマースストアやレコメンデーションエンジン、マッチングプラットフォーム上のユーザのエンゲージメント指標を改善できる。
論文 参考訳(メタデータ) (2020-01-22T02:26:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。