論文の概要: Offline Local Search for Online Stochastic Bandits

• arxiv url: http://arxiv.org/abs/2604.09423v1
• Date: Fri, 10 Apr 2026 15:36:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-13 17:57:53.938055
• Title: Offline Local Search for Online Stochastic Bandits
• Title（参考訳）: オンライン確率帯域のオフラインローカル検索
• Authors: Gerdus Benadè, Rathish Das, Thomas Lavastida,
• Abstract要約: コンビニアル・マルチアーマード・バンディットは基本的なオンライン意思決定環境を提供する。 目的は、後ろ向きの最適な固定アクションに比べて損失として定義される後悔である。 オフラインの欲求と線形最適化アルゴリズム(正確にも近似的にも)は、オンラインにデプロイする際に有用な保証を提供することが示されている。
• 参考スコア（独自算出の注目度）: 3.029373177207996
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial multi-armed bandits provide a fundamental online decision-making environment where a decision-maker interacts with an environment across $T$ time steps, each time selecting an action and learning the cost of that action. The goal is to minimize regret, defined as the loss compared to the optimal fixed action in hindsight under full-information. There has been substantial interest in leveraging what is known about offline algorithm design in this online setting. Offline greedy and linear optimization algorithms (both exact and approximate) have been shown to provide useful guarantees when deployed online. We investigate local search methods, a broad class of algorithms used widely in both theory and practice, which have thus far been under-explored in this context. We focus on problems where offline local search terminates in an approximately optimal solution and give a generic method for converting such an offline algorithm into an online stochastic combinatorial bandit algorithm with $O(\log^3 T)$ (approximate) regret. In contrast, existing offline-to-online frameworks yield regret (and approximate regret) which depend sub-linearly, but polynomially on $T$. We demonstrate the flexibility of our framework by applying it to three online stochastic combinatorial optimization problems: scheduling to minimize total completion time, finding a minimum cost base of a matroid and uncertain clustering.
• Abstract（参考訳）: Combinatorのマルチアームバンドは、意思決定者がアクションを選択し、そのアクションのコストを学習するたびに、T$タイムステップの環境と対話する、基本的なオンライン意思決定環境を提供する。 目的は、完全な情報の下での後ろ向きの最適な固定行動に比べて損失として定義される後悔を最小限に抑えることである。 このオンライン環境では、オフラインのアルゴリズム設計で知られていることを活用することに、かなりの関心が寄せられている。 オフラインの欲求と線形最適化アルゴリズム(正確にも近似的にも)は、オンラインにデプロイする際に有用な保証を提供することが示されている。 提案手法は,理論と実践の両方で広く用いられているアルゴリズムの幅広いクラスである局所探索法について検討する。 我々は,オフライン局所探索がほぼ最適解で終了する問題に着目し,そのようなオフラインアルゴリズムを$O(\log^3 T)$ (approximate) の後悔を伴うオンライン確率的組合せ帯域アルゴリズムに変換する一般的な方法を提案する。 対照的に、既存のオフライン-オフラインのフレームワークは、サブリニアに依存するが、多項式的に$T$に依存する後悔(およびほぼ後悔)をもたらす。 本稿では,3つのオンライン確率的組合せ最適化問題 – 全体の完了時間を最小化するためのスケジューリング,マトロイドの最小コストベース探索,不確実クラスタリング – に適用することで,フレームワークの柔軟性を実証する。

関連論文リスト

• Leveraging Offline Data in Linear Latent Contextual Bandits [27.272915631913175]
  我々は、数え切れないほど多くの潜伏状態を処理できるエンドツーエンドの潜伏包帯アルゴリズムを設計する。 このオフラインアルゴリズムの出力を利用してオンライン学習を高速化する2つのオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T16:23:34Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
  離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
  論文  参考訳（メタデータ） (2023-01-30T23:18:06Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization [0.0]
  我々は局所的エラーに頑健な欲望アルゴリズムを用いて,定数係数近似に適応可能なオフライン問題に焦点を当てた。 このような問題に対して,オフラインロバストなアルゴリズムをオンラインに効率的に変換する汎用フレームワークを提供する。 得られたオンラインアルゴリズムは、完全な情報設定の下で、$O(sqrtT)$ (approximate) の後悔を持つことを示す。
  論文  参考訳（メタデータ） (2021-02-18T19:05:26Z)

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

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