論文の概要: Leveraging Good Representations in Linear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2104.03781v1
- Date: Thu, 8 Apr 2021 14:05:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-09 12:58:41.207874
- Title: Leveraging Good Representations in Linear Contextual Bandits
- Title（参考訳）: 線形文脈バンディットにおける良き表現の活用
- Authors: Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric
and Matteo Pirotta
- Abstract要約: 文脈的バンディット問題は複数の線形表現を許容することがある。
最近の研究は、絶え間ない問題依存の後悔を達成できる「良い」表現が存在することを示した。
最善の表現でlinucbを実行することで得られる後悔よりも、後悔は決して悪くありません。
- 参考スコア（独自算出の注目度）: 131.91060536108301
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The linear contextual bandit literature is mostly focused on the design of
efficient learning algorithms for a given representation. However, a contextual
bandit problem may admit multiple linear representations, each one with
different characteristics that directly impact the regret of the learning
algorithm. In particular, recent works showed that there exist "good"
representations for which constant problem-dependent regret can be achieved. In
this paper, we first provide a systematic analysis of the different definitions
of "good" representations proposed in the literature. We then propose a novel
selection algorithm able to adapt to the best representation in a set of $M$
candidates. We show that the regret is indeed never worse than the regret
obtained by running LinUCB on the best representation (up to a $\ln M$ factor).
As a result, our algorithm achieves constant regret whenever a "good"
representation is available in the set. Furthermore, we show that the algorithm
may still achieve constant regret by implicitly constructing a "good"
representation, even when none of the initial representations is "good".
Finally, we empirically validate our theoretical findings in a number of
standard contextual bandit problems.
- Abstract（参考訳）: 線形文脈バンディット文学は主に、与えられた表現に対する効率的な学習アルゴリズムの設計に焦点を当てている。
しかし、文脈的バンディット問題は、学習アルゴリズムの後悔に直接影響を及ぼす異なる特徴を持つ複数の線形表現を許容することがある。
特に、最近の研究は、一定の問題依存的後悔が達成できる「良い」表現が存在することを示した。
本稿ではまず,文献で提案されている「良い」表現の異なる定義を体系的に分析する。
そこで我々は,$M$の候補集合において,最適な表現に適応できる新しい選択アルゴリズムを提案する。
我々は、LinUCBを最良の表現($\ln M$ factorまで)で実行したことによる後悔よりも、後悔は決して悪いことではないことを示した。
その結果,本アルゴリズムは,集合内で「よい」表現が利用可能であれば,常に後悔する。
さらに,初期表現が「良い」場合であっても,暗黙的に「良い」表現を構築することによって,アルゴリズムが常に後悔することを示す。
最後に,多くの標準的な文脈的包帯問題における理論的知見を実証的に検証した。
関連論文リスト
- On the Complexity of Representation Learning in Contextual Linear
Bandits [110.84649234726442]
表現学習は線形帯域よりも根本的に複雑であることを示す。
特に、与えられた表現の集合で学ぶことは、その集合の中で最悪の実現可能な表現で学ぶことよりも決して単純ではない。
論文 参考訳（メタデータ） (2022-12-19T13:08:58Z) - Scalable Representation Learning in Linear Contextual Bandits with
Constant Regret Guarantees [103.69464492445779]
本稿では,スペクトル特性のよい表現を学習する表現学習アルゴリズムBanditSRLを提案する。
我々は、BanditSRLが任意の非regretアルゴリズムとペアリング可能であることを証明し、HLS表現が利用可能であれば常に後悔する。
論文 参考訳（メタデータ） (2022-10-24T10:04:54Z) - Contextual Bandits with Smooth Regret: Efficient Learning in Continuous
Action Spaces [14.366265951396587]
我々は、大規模または連続的なアクション空間に対する効率的な汎用的コンテキスト帯域幅アルゴリズムを設計する。
本稿では,従来提案されていた代替案に支配的な文脈的包帯に対して,スムーズな後悔の念を抱く概念を提案する。
我々のアルゴリズムは、標準的な後悔の下で以前のminimax/Paretoの最適保証を回復するために使用することができる。
論文 参考訳（メタデータ） (2022-07-12T21:27:09Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。