論文の概要: Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

• arxiv url: http://arxiv.org/abs/2607.26273v1
• Date: Tue, 28 Jul 2026 21:10:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-30 21:06:25.471032
• Title: Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
• Title（参考訳）: Top-k$ Pareto Bandits:多目的スレート選択のためのハイパーボリュームレグレット
• Authors: Nicolas Gutowski, Fabien Chhel, Alexandre Letard, Sylvain Lamprier,
• Abstract要約: 我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。 この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。 ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
• 参考スコア（独自算出の注目度）: 48.83076933238825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $α$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight, where $α= 1 - 1/e$ reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce \textit{THV-UCB}, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound $\tilde{O}(d\sqrt{nkT})$ that holds on every instance, together with a gap-dependent bound $\tilde{O}(nk^{2.5}/Δ_{\min})$ that becomes polylogarithmic in $T$ once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.
• Abstract（参考訳）: 確率的多目的バンディット問題を考えると、各ラウンドでエージェントが$k$アームのスレートを選択し、半帯域フィードバックの下でそれらの$d$次元報酬ベクトルを観測する。 我々は、一つの最適な腕を特定することではなく、パレートフロンティアを共同で近似する小さな行動群を維持することの問題を考察する。 この目的は、選択されたアームのサブセットによって誘導される支配的な超体積によって定式化され、最高のサイズに対して$α$-approximate hypervolume regretを定義します。 この問題に対処するために,楽観的なアルゴリズムである \textit{THV-UCB} を導入する。 ギャップフリーな後悔境界 $\tilde{O}(d\sqrt{nkT})$ とギャップ依存境界 $\tilde{O}(nk^{2.5}/Δ_{\min})$ は、腕が十分に分離された後に$T$ の多元対数となる。 この結果は, 様々な多目的アプリケーションにおいて, パレートフロントを近似するために小部分集合を用いる理論的支援を提供する。

関連論文リスト

• Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback [2.1772197319352498]
  マルチラジオアクセス選択とモバイルエッジコンピューティングのオフロードによるオンラインリソース選択問題について検討する。 各ラウンドでエージェントは、$d$-dimensionalベクターのパフォーマンスを持つ$K$候補リンク/サーバを選択する。 我々は、楽観的なプローブ-then-commitアルゴリズムであるtextscPtC-P-UCB を開発した。
  論文  参考訳（メタデータ） (2026-02-03T06:44:00Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application to Joint Communications and Sensing [7.0997346625024]
  本稿では,この問題を解決するために,変化検出を用いた汎用上信頼境界(UCB)に基づくアルゴリズムを提案する。 また,統合通信・センシングシステムにおけるエネルギー効率のよい波形設計問題を玩具の例として定式化する。
  論文  参考訳（メタデータ） (2023-02-10T14:10:14Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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