論文の概要: Sparse Nonparametric Contextual Bandits

• arxiv url: http://arxiv.org/abs/2503.16382v1
• Date: Thu, 20 Mar 2025 17:44:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-21 16:35:45.878748
• Title: Sparse Nonparametric Contextual Bandits
• Title（参考訳）: スパース非パラメトリックコンテキスト帯域
• Authors: Hamish Flynn, Julia Olkhovskaya, Paul Rognon-Vael,
• Abstract要約: 本稿では,関連する特徴を同時に学習し,文脈的盗賊問題における後悔を最小限に抑えることの課題について検討する。 我々は、スパース非パラメトリックな文脈的包帯問題(sparse nonparametric contextual bandit)と呼ばれる新しい文脈的包帯問題を紹介し、分析する。 スパシティとアクションの数に対して地平線が十分に大きい限り、スパシティは常により良い後悔境界を可能にする。
• 参考スコア（独自算出の注目度）: 2.0072624123275533
• License:
• Abstract: This paper studies the problem of simultaneously learning relevant features and minimising regret in contextual bandit problems. We introduce and analyse a new class of contextual bandit problems, called sparse nonparametric contextual bandits, in which the expected reward function lies in the linear span of a small unknown set of features that belongs to a known infinite set of candidate features. We consider two notions of sparsity, for which the set of candidate features is either countable or uncountable. Our contribution is two-fold. First, we provide lower bounds on the minimax regret, which show that polynomial dependence on the number of actions is generally unavoidable in this setting. Second, we show that a variant of the Feel-Good Thompson Sampling algorithm enjoys regret bounds that match our lower bounds up to logarithmic factors of the horizon, and have logarithmic dependence on the effective number of candidate features. When we apply our results to kernelised and neural contextual bandits, we find that sparsity always enables better regret bounds, as long as the horizon is large enough relative to the sparsity and the number of actions.
• Abstract（参考訳）: 本稿では,関連する特徴を同時に学習し,文脈的包帯問題における後悔を最小限に抑えることの課題について検討する。 我々は、期待される報酬関数が既知の無限個の候補特徴集合に属する小さな未知の特徴集合の線形スパンに存在するスパース非パラメトリック文脈バンドイット(sparse nonparametric contextual bandits)と呼ばれる新しい文脈的バンドイット問題を紹介し、解析する。 空間性という2つの概念を考察し、候補となる特徴の集合を可算あるいは非可算のいずれかとする。 私たちの貢献は2倍です。 第一に、ミニマックスの後悔に対する下限を提供し、この設定では、作用数に対する多項式依存が一般的に避けられないことを示す。 第二に、Feel-Good Thompson Smpling アルゴリズムの変種は、水平線の対数的要因まで下界に一致する後悔境界を楽しみ、有効数の候補特徴に対数的依存を持つことを示す。 カーネル化された、神経的な文脈の包帯に結果を適用すると、スパシティとアクションの数に対して地平線が十分に大きい限り、スパシティは常により良い後悔境界を許容することがわかった。

関連論文リスト

• Neural Dueling Bandits [58.90189511247936]
  ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。 次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
  論文  参考訳（メタデータ） (2024-07-24T09:23:22Z)
• Batched Nonparametric Contextual Bandits [21.031965676746776]
  バッチ制約下での非パラメトリック文脈帯域について検討する。 最適な後悔を実現する新しいバッチ学習アルゴリズムを提案する。 我々の理論的結果は、非パラメトリックな文脈的帯域幅では、ほぼ一定数のポリシー更新が最適な後悔をもたらすことを示唆している。
  論文  参考訳（メタデータ） (2024-02-27T18:06:20Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Contextual Multinomial Logit Bandits with General Value Functions [47.06746975822902]
  MNL(Contextual multinomial logit)バンドレットは、オンライン小売や広告など、現実のアソシエーションレコメンデーション問題の多くをキャプチャする。 我々は、文脈的盗賊の研究の最近の動向からアイデアを借りて、基礎的真理を含む一般値関数クラスを持つ文脈的MNL盗賊を考察する。 具体的には、計算と逆の設定の両方を考慮し、それぞれが異なるトレードオフを持つ一連のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-12T23:50:44Z)
• 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)
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。 文脈問題を線形バンディット問題として解くことができることを示す。 この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
  論文  参考訳（メタデータ） (2022-11-08T22:18:53Z)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  この研究は、両腕のベルヌーイ・バンディット問題(英語版)(Bernoulli bandit problem)の、腕の手段の和が1であるバージョンに対処する。 我々は, それぞれの問題を線形熱方程式の解に関連付けることにより, minmax最適後悔と擬似回帰の先行順序項を得る。
  論文  参考訳（メタデータ） (2022-02-11T17:03:18Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits [40.01661188919779]
  有限作用集合を持つ線形文脈帯域における逐次バッチ学習問題について検討する。 この問題は、実用アプリケーションにおいて、多くのパーソナライズされたシーケンシャルな意思決定問題のよりきめ細かい定式化を提供する。
  論文  参考訳（メタデータ） (2020-04-14T06:47:40Z)

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

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