論文の概要: Optimal Online Regret for Context-Lumpable Bandits

• arxiv url: http://arxiv.org/abs/2610.18258v1
• Date: Tue, 13 Oct 2026 12:23:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-17 06:43:18.442843
• Title: Optimal Online Regret for Context-Lumpable Bandits
• Title（参考訳）: コンテキストLumpable Banditsのための最適オンラインレグレット
• Abstract要約: 我々は,未知の文脈可聴構造を持つ文脈的包帯について検討する。 S$コンテキストは$r$ブロックに分割され、各アームは同じブロック内のコンテキスト間で同じ平均報酬を持つ。 We design a algorithm with expected regret $widetildeO(sqrtr(S+K)T)$, with the lower bound of Lee et al. (2023) to logarithmic factors and improve their previous upper bound by a factor of $r$。
• 参考スコア（独自算出の注目度）: 17.336411916552915
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic contextual bandits with an unknown context-lumpable structure. The $S$ contexts are partitioned into $r$ blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret $\widetilde{O}(\sqrt{r(S+K)T})$, matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of $r$. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most $r$ selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.
• Abstract（参考訳）: 確率的文脈包括構造を未知の文脈包括構造で研究する。 S$コンテキストは$r$ブロックに分割され、各アームは同じブロック内のコンテキスト間で同じ平均報酬を持つ。 任意の文脈分布と分離仮定がなければ、期待される$\widetilde{O}(\sqrt{r(S+K)T})$でアルゴリズムを設計し、Lee et al (2023) の下位境界を対数的因子にマッチングし、以前の上限を$r$で改善する。 このアルゴリズムは、基準方針と信頼に基づく早期停止を用いて、二進的精度のレベル以上を演算し、探索を制御する。 報酬はブロック内で同一であるため、1つの選択されたアームはそのブロックから生き残ったすべてのレコードを排除し、各レベルで少なくとも$r$の選択を必要とする。 マルチスケール探索では、頻繁なブロックに細かなアキュラティを割り当て、希少なブロックに粗いアキュラティを割り当て、重み付けされたポリシーエラーを小さく保ちながら、各ブロックにほぼ最適のアームを与える。

関連論文リスト

• Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity [54.77408659142336]
  我々は,複数の最適な腕を持つマルチアーム・バンディット(MAB)について検討し,実際的な意思決定問題の多くが複数の正解を許容しているという事実に動機づけられた。 たとえば$tildeOBig(fracK-AsqrtKAsqrtT Big)$ minimax regret, where $T$ is the total number of interaction and $tilde O(cdot)$ drops all constant and logarithmic factors。
  論文  参考訳（メタデータ） (2026-09-29T23:33:10Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。 アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
  論文  参考訳（メタデータ） (2023-06-28T21:59:11Z)
• Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
  最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。 我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。 鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
  論文  参考訳（メタデータ） (2021-01-30T21:51:47Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)

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

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