論文の概要: Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

• arxiv url: http://arxiv.org/abs/2609.19963v2
• Date: Mon, 28 Sep 2026 07:42:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-05 14:48:16.092183
• Title: Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
• Title（参考訳）: 集中型シリアルディクタトリー帯域における排他的レグレトフロンティアと外部性スケジューリング
• Abstract要約: 一致レベルグレイブス・レイの制約は、有限個の対探索クォータとクォータに制約を還元することを示した。 さらに、同一の探索クォータがスケジューリングによって全く異なる後悔を引き起こすことを示す。 我々は、一意性を仮定することなく、すべての正の正の最適値が得られる全行制限クラスで一様に良い推定ポリシーを構築する。
• 参考スコア（独自算出の注目度）: 4.988148613131287
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(θ)\mathcal{X}(θ)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.
• Abstract（参考訳）: 集中型シリアル・ディクテーター・マッチング・バンドイットでの探索は完全なマッチングを使わなければならないため、プレイヤー・アームのペアの1つの学習は他人に後悔を強いる可能性がある。 この外部性は、既知の共通優先順序と単位分散を持つガウス報酬の下で研究する。 マッチングレベルグレーブス・レイの制約は、有限個のペアワイズ探索クォータに減少し、トップチョイス分離の場合、多項式サイズの境界線形プログラムが得られることを示す。 これらの場合、予想される対数的後悔係数の正確な集合は$G(θ)\mathcal{X}(θ)$であり、$\mathcal{X}$は実現可能なマッチング割り当てセットであり、$G$はプレイヤーの後悔に対するマップアロケーションである。 通常の上閉じのグレーヴス・レイ地域は、パレト・ミニマル境界が同じであるにもかかわらず、厳密に大きい。 さらに、同一の探索クォータがスケジューリングによって全く異なる後悔を引き起こすことを示す。 最後に、全行制限クラスで一様に良い推定解トラックポリシーを構築し、最適化器の特異性を仮定することなく、任意の正の重み付けされた最適値が得られるようにする。 パレート最小点はすべて、インスタンスキャリブレーションされたターゲットを通して、ポイントワイズ到達可能である。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
  我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。 この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。 ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
  論文  参考訳（メタデータ） (2026-07-28T21:10:39Z)
• Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning [39.8867004581646]
  すべての信頼レベル$in (0,1]$に対して均一に保たれる確率的保証として分布的後悔を定式化する。 探索ボーナス$minc_1,k/N,c_2,k/sqrtN$,$N$は訪問数を表し,$(c_1,k,c_2,k)$はユーザ指定パラメータである。 我々の境界は、ミニマックスとインスタンス依存のレジームの両方において、期待と分布の後悔の間の最適なトレードオフを達成する
  論文  参考訳（メタデータ） (2026-05-06T16:38:30Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Regret Minimization in Heavy-Tailed Bandits [12.272975892517039]
  マルチアームバンディット設定における古典的後悔最小化問題を再考する。 本稿では,1次項における下界を正確に一致させる最適アルゴリズムを提案する。 我々の指数は、よく知られたトリミングまたはトリミングされた経験的平均推定値よりも速く集中していることを示す。
  論文  参考訳（メタデータ） (2021-02-07T07:46:24Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
  我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。 ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
  論文  参考訳（メタデータ） (2020-02-29T23:50:08Z)

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

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