論文の概要: Leveraging Similarities in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2606.23414v1
• Date: Mon, 22 Jun 2026 14:39:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 19:09:37.851516
• Title: Leveraging Similarities in Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドにおける類似点の活用
• Authors: Khaled Eldowa, Thibaud Rahier, Augustin Cablant, Panayotis Mertikopoulos, Pierre Gaillard,
• Abstract要約: そこで,本研究では,ルート木で符号化された類似性構造化アクションセットを用いてオンライン学習について検討する。 2点フィードバックの下では,リプシッツの盗賊を後悔して$sqrtT$を達成できることが示されている。
• 参考スコア（独自算出の注目度）: 26.91899094459239
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many online learning and bandit problems, the actions we consider possess inherent similarities--for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions $K$ by a similarity-aware effective number of actions $K_{\mathrm{eff}}$ in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve $\sqrt{T}$ regret in Lipschitz bandits when $d \leq 2$.
• Abstract（参考訳）: 多くのオンライン学習や盗賊問題において、私たちが考える行動は固有の類似点を持っている。 オンライン学習を類似度に構造化された行動集合を用いて研究し、葉が行動であり、そのレベルが2つの行動がどの程度密接に関連しているかを定量化するルート木で符号化した。 損失シーケンスはツリー互換であると仮定され、類似したアクションの損失は閉じることに制約される。 非常に強い類似性制約の下でも、通常のワンポイントバンディットフィードバックは、一般的には、範囲や木によって引き起こされる類似性を活用できないことを示す。 次に、半帯域フィードバックから最小の2ポイントフィードバック設定を含むマルチポイントバンディットプロトコルまで、幅広いリッチなフィードバックモデルに適応する統一されたアルゴリズムセットを提供する。 これらのアルゴリズムは, 同一性を考慮したアクション数$K$を, 実効的なアクション数$K_{\mathrm{eff}}$に置き換えることで, 両世界のベスト・オブ・ワールドを保証し, 行動類似性を確実に活用することを示す。 アプリケーションとして、二点フィードバックの下では、$d \leq 2$のときにリプシッツの盗賊に$\sqrt{T}$後悔を達成できることが示される。

関連論文リスト

• A single algorithm for both restless and rested rotting bandits [65.63283411693489]
  本稿では,ロッティング・アダプティブ・ウインドウUCBというアルゴリズムを導入し,ロッティング・レストとレスト・バンディットの両面において,ほぼ最適の後悔を実現する。 これは、報酬が増加するとアルゴリズムが同様の結果を得ることができないことを示す以前の否定的な結果とは対照的である。
  論文  参考訳（メタデータ） (2026-04-23T08:48:52Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (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)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。 有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。 我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
  論文  参考訳（メタデータ） (2023-05-25T14:02:12Z)
• Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds [31.5504566292927]
  我々は, 後悔を最小限に抑えるために, 中央サーバを介して協調できる$M$エージェントを含む線形帯域幅問題を考える。 これらのエージェントのわずか$alpha$は敵対的であり、任意に作用し、次の緊張に繋がる。 我々は、厳密な信頼区間を慎重に構築し、探索と探索のトレードオフをバランスさせる新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-06T18:16:34Z)
• Batched Dueling Bandits [13.69077222007053]
  そこで本研究では,2つの標準設定条件下で,K$アームのデュエルバンディット問題について検討した。 バッチ数と後悔数のトレードオフを円滑に行うアルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-02-22T04:02:36Z)
• Deep Hierarchy in Bandits [51.22833900944146]
  行動の報酬は、しばしば相関する。 統計的効率を最大化するためには,これらの相関を学習に活用することが重要である。 平均作用報酬の相関が階層的ベイズモデルで表されるこの問題のバンディット変法を定式化する。
  論文  参考訳（メタデータ） (2022-02-03T08:15:53Z)
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
  我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。 我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
  論文  参考訳（メタデータ） (2020-10-29T07:13:28Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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