論文の概要: Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models
- arxiv url: http://arxiv.org/abs/2202.04593v1
- Date: Wed, 9 Feb 2022 17:44:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-10 15:06:35.126966
- Title: Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models
- Title(参考訳): 線形確率性モデルに基づく確率的文脈デュエル帯域
- Authors: Viktor Bengs, Aadirupa Saha, Eyke H\"ullermeier
- Abstract要約: 我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。
本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
- 参考スコア(独自算出の注目度): 25.336599480692122
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the regret minimization task in a dueling bandits problem with
context information. In every round of the sequential decision problem, the
learner makes a context-dependent selection of two choice alternatives (arms)
to be compared with each other and receives feedback in the form of noisy
preference information. We assume that the feedback process is determined by a
linear stochastic transitivity model with contextualized utilities (CoLST), and
the learner's task is to include the best arm (with highest latent
context-dependent utility) in the duel. We propose a computationally efficient
algorithm, $\texttt{CoLSTIM}$, which makes its choice based on imitating the
feedback process using perturbed context-dependent utility estimates of the
underlying CoLST model. If each arm is associated with a $d$-dimensional
feature vector, we show that $\texttt{CoLSTIM}$ achieves a regret of order
$\tilde O( \sqrt{dT})$ after $T$ learning rounds. Additionally, we also
establish the optimality of $\texttt{CoLSTIM}$ by showing a lower bound for the
weak regret that refines the existing average regret analysis. Our experiments
demonstrate its superiority over state-of-art algorithms for special cases of
CoLST models.
- Abstract(参考訳): コンテキスト情報を伴うデュエルバンディット問題における後悔の最小化タスクについて考察する。
逐次決定問題の各ラウンドにおいて、学習者は、互いに比較する2つの選択肢(アーム)の文脈依存的な選択を行い、ノイズの多い選好情報としてフィードバックを受け取る。
フィードバックプロセスは文脈化されたユーティリティ(colst)を持つ線形確率的推移モデルによって決定され、学習者のタスクは最善のアーム(最も潜在的なコンテキスト依存のユーティリティを持つ)をデュエルに含めることである。
提案する計算効率のよいアルゴリズムである$\texttt{CoLSTIM}$は,基盤となるCoLSTモデルのコンテキスト依存ユーティリティ推定を用いて,フィードバックプロセスの模倣に基づいて選択する。
それぞれのアームが$d$次元の特徴ベクトルに関連付けられている場合、$\texttt{CoLSTIM}$が$T$学習ラウンドの後に$\tilde O( \sqrt{dT})$を後悔することを示す。
さらに、既存の平均後悔分析を洗練させる弱い後悔に対する低い境界を示すことによって、$\texttt{CoLSTIM}$の最適性を確立する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
関連論文リスト
- Contextual Linear Optimization with Bandit Feedback [35.692428244561626]
文脈線形最適化(CLO)は、ランダムコスト係数の不確実性を低減するために予測的文脈特徴を用いる。
我々は,帯域幅フィードバックを用いたCLOのためのオフライン学習アルゴリズムのクラスについて検討する。
IERMに対する高速な後悔境界を示し、不特定モデルクラスと最適化推定の柔軟な選択を可能にする。
論文 参考訳(メタデータ) (2024-05-26T13:27:27Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳(メタデータ) (2024-04-16T17:59:55Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳(メタデータ) (2023-03-30T02:51:00Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳(メタデータ) (2022-12-07T17:30:45Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳(メタデータ) (2021-11-24T07:14:57Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳(メタデータ) (2021-11-08T18:05:35Z) - Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。
提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
論文 参考訳(メタデータ) (2021-02-01T23:31:10Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。