論文の概要: Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits

• arxiv url: http://arxiv.org/abs/2511.05802v1
• Date: Sat, 08 Nov 2025 02:22:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.583927
• Title: Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits
• Title（参考訳）: 下界を越えて:レギュレット最小化とレキシコグラフィーバンドにおける腕の同定
• Authors: Bo Xue, Yuanyu Wan, Zhichao Lu, Qingfu Zhang,
• Abstract要約: 多目的意思決定において、レキシコグラフィーの帯域幅は、優先順位付けされた順序で複数の目的を最適化するための自然な枠組みを提供する。 本稿では,この共同目的に対処する2つの除去アルゴリズムを提案する。 注目すべきは、シングルオブジェクトのバンディット問題に対する既知の下界よりも優れていることである。
• 参考スコア（独自算出の注目度）: 38.6018343928571
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In multi-objective decision-making with hierarchical preferences, lexicographic bandits provide a natural framework for optimizing multiple objectives in a prioritized order. In this setting, a learner repeatedly selects arms and observes reward vectors, aiming to maximize the reward for the highest-priority objective, then the next, and so on. While previous studies have primarily focused on regret minimization, this work bridges the gap between \textit{regret minimization} and \textit{best arm identification} under lexicographic preferences. We propose two elimination-based algorithms to address this joint objective. The first algorithm eliminates suboptimal arms sequentially, layer by layer, in accordance with the objective priorities, and achieves sample complexity and regret bounds comparable to those of the best single-objective algorithms. The second algorithm simultaneously leverages reward information from all objectives in each round, effectively exploiting cross-objective dependencies. Remarkably, it outperforms the known lower bound for the single-objective bandit problem, highlighting the benefit of cross-objective information sharing in the multi-objective setting. Empirical results further validate their superior performance over baselines.
• Abstract（参考訳）: 階層的な選好を持つ多目的意思決定において、語彙的帯域幅は優先順位付けされた順序で複数の目的を最適化するための自然な枠組みを提供する。 この設定では、学習者が繰り返しアームを選択し、報酬ベクトルを観察し、最優先目標の報酬を最大化し、次に報酬を最大化する。 過去の研究では主に後悔の最小化に焦点が当てられていたが、この研究はレキソグラフィーの嗜好の下で、 \textit{regret minimization} と \textit{best arm identification} のギャップを埋めるものである。 本稿では,この共同目的に対処する2つの除去アルゴリズムを提案する。 第1のアルゴリズムは、目的の優先事項に従って、層ごとに順次、最適腕を除去し、最も優れた単目的アルゴリズムに匹敵する、サンプルの複雑さと後悔の限界を達成する。 第2のアルゴリズムは、各ラウンドのすべての目的からの報奨情報を同時に利用し、オブジェクト間の依存関係を効果的に活用する。 注目すべきは、シングルオブジェクトのバンディット問題に対する既知の下位境界よりも優れており、多目的設定におけるクロスオブジェクトの情報共有の利点を強調していることである。 実験結果はさらに、ベースラインよりも優れたパフォーマンスを実証する。

関連論文リスト

• Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences [7.18523391773903]
  多目的経路探索(MO-MAPF)アルゴリズムは競合のない計画を生成する。 我々は,MO-MAPFをモデル化するためのレキシコグラフィーフレームワークと,アルゴリズムのテクスタイストLexicographic Conflict-Based Search (LCBS)を提案する。 LCBSは優先順位を意識した低レベルの$A*$検索とコンフリクトベースの検索を統合している。 私たちは最適性とスケーラビリティに関する洞察を提供し、LCBSが最大10の目的を持つインスタンスにスケーリングしながら最適なソリューションを計算していることを実証的に示しています。
  論文  参考訳（メタデータ） (2025-10-08T17:40:41Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  本稿では,2次基準のしきい値に基づく制約を満たしつつ,主目的を最大化し,アライメントの多面性に対処する推論フレームワークSITAlignを提案する。 我々は、満足度に基づく推論アライメントアプローチの準最適境界を導出することで理論的洞察を提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:56:05Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Jacobian Descent for Multi-Objective Optimization [0.6138671548064355]
  勾配降下は単目的最適化に限られる。 Jacobian descent (JD) はベクトル値の目的関数のヤコビ行列を用いてパラメータを反復的に更新する。
  論文  参考訳（メタデータ） (2024-06-23T22:06:25Z)
• Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints [69.27190330994635]
  コアセットの選択は、計算コストの削減とディープラーニングアルゴリズムのデータ処理の高速化に強力である。 本稿では,モデル性能とコアセットサイズに対する最適化優先順序を維持する革新的な手法を提案する。 実験的に、広範な実験によりその優位性が確認され、しばしばより小さなコアセットサイズでモデル性能が向上する。
  論文  参考訳（メタデータ） (2023-11-15T03:43:04Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)

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

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