論文の概要: Active Context Selection Improves Simple Regret in Contextual Bandits

• arxiv url: http://arxiv.org/abs/2605.20040v1
• Date: Tue, 19 May 2026 16:01:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.506606
• Title: Active Context Selection Improves Simple Regret in Contextual Bandits
• Title（参考訳）: アクティブコンテキスト選択は、コンテキスト帯域の単純なレグレットを改善する
• Authors: Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash,
• Abstract要約: 有限文脈空間(サブポピュレーション)を用いた文脈多重武装バンディット問題について検討する。 私たちの保証は、報酬分布よりも最悪のケースですが、コンテキスト分布ベクトル$p$に関しては、インスタンス依存のままです。 p$が不明な場合、コンテキスト分布とアクティブアロケーションに切り替える時間を最適に推定するExplore-Explore-Then-Commit (EETC)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 25.361115767570244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector $p$. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known $p$, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order $\sqrt{n/T \, \lVert p \rVert_{1/2}}$, whereas active sampling with allocation $q_j \propto p_j^{2/3}$ achieves the tight rate $\sqrt{n/T} \, \lVert p \rVert_{2/3}$. The resulting improvement can be as large as $Θ(k^{1/4})$, where $k$ is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When $p$ is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-$p$ active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.
• Abstract（参考訳）: そこで,学習者が各文脈に対して最善のアクションを推奨し,文脈重み付けされた単純な後悔によって評価されるような,コンテキスト空間の有限なマルチアームバンディット問題(サブポピュレーション)について検討する。 私たちの保証は報酬分布よりも最悪のケースで、コンテキスト分布ベクトル$p$に関してインスタンス依存のままです。 興味の集団が固定されているが、サンプル化されたサブポピュレーションを制御できる実験的な設計問題とは異なり、学習者はどのコンテキストからサンプリングするかを積極的に選択できる。 一方、$q_j \propto p_j^{2/3}$は、$\sqrt{n/T} \, \lVert p \rVert_{2/3}$である。 結果として得られる改善は、$(k^{1/4})$で、$k$はコンテキストの数である。 さらに、分析を予算化されたアクティブサンプリングに拡張し、対応するタイトレートを特徴付けるとともに、限られたアクティブな予算が完全にアクティブなレートを回復するのに十分であるかどうかを識別する。 p$が不明な場合、探索的-Explore-Then-Commit (EETC) アルゴリズムを提案し、このアルゴリズムはコンテキスト分布とアクティブアロケーションに切り替える時間とを最適にバランスさせ、大きな地平線の場合、既知の-$$アクティブレートを定数まで一致させる。 合成および実世界のデータに関する実験は、我々の理論的な発見を支持する。

関連論文リスト

• Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions [1.0098114696565863]
  SupSplitLogは、コンテキストの多様性を仮定せずに$tildemathcalO(sqrtdT)$ regretを達成するロジスティックバンディットのための最初のアルゴリズムである。 SupSplitLogは、後悔の上限における次元$d$への依存の観点から、既存のアルゴリズムを厳密に改善する。
  論文  参考訳（メタデータ） (2026-04-24T02:21:59Z)
• Optimal Best Arm Identification with Post-Action Context [15.613350380708798]
  動作後コンテキストを用いたベストアーム識別の問題を紹介する。 動作後コンテキストの2つの異なるタイプを解析する。 非セパレータ設定では、トラック・アンド・ストップのアルゴリズムをこの設定に拡張できることを実証する。 セパレータ設定では,コンテキスト空間の幾何学を用いてアクションではなくコンテキストを直接追跡する「textitG-tracking$」という新しいサンプリングルールを提案する。
  論文  参考訳（メタデータ） (2025-02-05T10:47:05Z)
• Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration [40.73142019282658]
  ランダム化を注入することは、環境を連続的に探索するエージェントの社会に役立てるかどうかを考察する。 有限および無限水平環境における最悪の後悔境界を示す。 我々は空間の複雑さを$K$の係数で減らし、最悪ケースの後悔の上限を$sqrtK$だけ増やす。
  論文  参考訳（メタデータ） (2025-01-23T05:37:33Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• 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 Contextual Dueling Bandits under Linear Stochastic Transitivity Models [25.336599480692122]
  我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。 本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。 本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-09T17:44:19Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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