論文の概要: Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

• arxiv url: http://arxiv.org/abs/2607.02150v1
• Date: Thu, 02 Jul 2026 13:26:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-03 19:45:08.844258
• Title: Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
• Title（参考訳）: ベルマン証明書によるマルチセカンダリ問題に対する高次下界
• Authors: Jiawei Zhang,
• Abstract要約: 本稿では,多官能問題における加法的後悔について考察する。 それは、予想されるオフライン預言者報酬と最高のオンラインポリシーの報酬とのギャップを定義する。
• 参考スコア（独自算出の注目度）: 7.379474076344059
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established \(O(\log T)\) regret for bounded-density distributions with connected support and \(O((\log T)^2)\) upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of \((\log T)^2\). Thus the existing \(O((\log T)^2)\) upper bounds for bounded-density gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.
• Abstract（参考訳）: 本稿では,複数秘書問題における積極的後悔を,期待するオフライン預言者報酬と最高のオンライン政策の報酬とのギャップとして定義する。 以前の研究は、連結な支持を持つ有界密度分布に対する \(O(\log T)\) の後悔と、支持ギャップを持つ有界密度分布に対する \(O((\log T)^2)\) の上界を確立した。 単一資源モデルにおいても余分な対数係数が必要かどうかは不明である。 私たちはそれが必要なことを証明する。 臨界容量で分離された2つの均一分布の混合に対して、最適の後悔は少なくとも \(((\log T)^2\) の順序で増大する。 したがって、連続的な報酬を伴うネットワーク収益管理モデルによって示唆されるような、有界密度ギャップ付きインスタンスに対する既存の \(O((\log T)^2)\ の上界は、この最も単純な特殊化において厳密である。 同じフレームワークは、サポートエッジ付近でギャップ面密度が消滅したギャップ分布に対する一致した下界も生成する。 証明はベルマン証明書(英語版)を用いており、正確なベルマン再帰の緩和の可能な解決策である。 このフレームワークは、下位境界を明示的な証明書構造に変換し、サポートギャップがより大きな後悔を許す理由を特定する。

関連論文リスト

• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization [20.87701856262044]
  非線型制約問題に対するBregman ADMMを両側の相対的滑らかさの下で解析する。 分散最適化のためのマルチブロック星コンセンサス定式化に解析を拡張した。
  論文  参考訳（メタデータ） (2026-06-26T17:52:39Z)
• Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards [1.370633147306388]
  $text-mathrmNPTS_mathrmSG$はアンカーフリーの非パラメトリックトンプソンサンプリングアルゴリズムである。 我々は、$text-mathrmNPTS_mathrmSG$が、$log n$の先頭の順にインスタンス依存の下位境界と一致することを証明した。
  論文  参考訳（メタデータ） (2026-06-08T08:26:37Z)
• 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)
• Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
  本研究では,新しいDDPMサンプリング器が,これまで考慮されていなかった3種類の分散クラスに対して高速化性能を実現することを示す。 この結果から, DDPM型加速サンプリング器におけるデータ次元$d$への依存性が改善された。
  論文  参考訳（メタデータ） (2024-02-21T16:11:47Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning [14.036298712230233]
  エントロピー的リスク尺度に基づいて,リスクに敏感な強化学習のためのギャップ依存的後悔保証について検討した。 マルコフ決定過程における2つのモデル自由アルゴリズムに対する非漸近的および対数的後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-03-07T03:07:09Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)

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

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