論文の概要: Water-Filling is Universally Minimax Optimal

• arxiv url: http://arxiv.org/abs/2603.26893v1
• Date: Fri, 27 Mar 2026 18:13:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 23:18:44.683156
• Title: Water-Filling is Universally Minimax Optimal
• Title（参考訳）: 透かしは最小限に最適
• Authors: Siddhartha Banerjee, Ramiro N. Deo-Campo Vuong, Robert Kleinberg,
• Abstract要約: 保証を実現するために,オンライン環境におけるメジャー化の理論を適用した。 水の充填は、基礎となる目的がバランスをとることを好む場合、最小限の非依存である。 我々の手法は、オンラインアルゴリズムの一般的な原始二重解析から逸脱している。
• 参考スコア（独自算出の注目度）: 4.040013871160853
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Allocation of dynamically-arriving (i.e., online) divisible resources among a set of offline agents is a fundamental problem, with applications to online marketplaces, scheduling, portfolio selection, signal processing, and many other areas. The water-filling algorithm, which allocates an incoming resource to maximize the minimum load of compatible agents, is ubiquitous in many of these applications whenever the underlying objectives prefer more balanced solutions; however, the analysis and guarantees differ across settings. We provide a justification for the widespread use of water-filling by showing that it is a universally minimax optimal policy in a strong sense. Formally, our main result implies that water-filling is minimax optimal for a large class of objectives -- including both Schur-concave maximization and Schur-convex minimization -- under $α$-regret and competitive ratio measures. This optimality holds for every fixed tuple of agents and resource counts. Remarkably, water-filling achieves these guarantees as a myopic policy, remaining entirely agnostic to the objective function, agent count, and resource availability. Our techniques notably depart from the popular primal-dual analysis of online algorithms, and instead develop a novel way to apply the theory of majorization in online settings to achieve universality guarantees.
• Abstract（参考訳）: オフラインエージェント間の動的に配置する(オンライン)リソースの割り当ては、オンラインマーケットプレース、スケジューリング、ポートフォリオの選択、信号処理など、基本的な問題である。 適合エージェントの最小負荷を最大化するために、入ってくるリソースを割り当てる給水アルゴリズムは、基礎となる目的がよりバランスのとれたソリューションを好む場合、これらのアプリケーションの多くにおいてユビキタスである。 我々は,水充填の広汎な利用を正当化するために,それが強い意味で,普遍的に最小限の最適政策であることを示す。 以上の結果から,シュル・コンケーブの最大化とシュル・コンベックスの最小化を含む多種多様な目的に対して,α$-regretと競争比の両面において水充填が最適であることが示唆された。 この最適性は、各固定されたエージェントとリソース数に対して成り立つ。 注目すべきは、水充填はこれらの保証をミオピックポリシーとして達成し、目的関数、エージェント数、リソース可用性に完全に依存しないままである。 我々の手法は、オンラインアルゴリズムの一般的な原始的双対分析から逸脱し、代わりに、オンライン設定における偏化理論を適用して普遍性を保証する新しい方法を開発した。

関連論文リスト

• Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning [59.11663802446183]
  フローおよび拡散生成モデルは、事前情報を保持しながらタスク固有の目的を最適化するために適応することができる。 本研究では,フロー密度制御(FDC)を導入し,複雑な問題をより単純な微調整タスクの特定のシーケンスに還元する。 我々は,近年のミラーフローの理解を活用して,現実的な仮定の下で提案されたスキームの収束保証を導出する。
  論文  参考訳（メタデータ） (2025-11-27T17:19:01Z)
• A Fair OR-ML Framework for Resource Substitution in Large-Scale Networks [14.634171922038675]
  本稿では,オペレーティングリサーチ(OR)と機械学習(ML)を組み合わせて,大規模ネットワークにおける資源の公平な置換を可能にする汎用フレームワークを提案する。 このフレームワークは、世界最大のパッケージデリバリー企業のネットワークに適用されている。
  論文  参考訳（メタデータ） (2025-11-23T03:38:41Z)
• Collab: Controlled Decoding using Mixture of Agents for LLM Alignment [90.6117569025754]
  人間のフィードバックからの強化学習は、大規模言語モデルを整合させる効果的な手法として現れてきた。 制御された復号化は、再訓練せずに推論時にモデルを整列するメカニズムを提供する。 本稿では,既存の既成のLCMポリシを活用するエージェントベースのデコーディング戦略の混合を提案する。
  論文  参考訳（メタデータ） (2025-03-27T17:34:25Z)
• Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning [46.28771270378047]
  フェデレート強化学習(RL)は、ローカルデータトラジェクトリを共有することなく、複数の分散エージェントの協調的な意思決定を可能にする。 本研究では,環境の同じ遷移カーネルを共有しながら,各エージェントが異なるタスクに対応する個別の報酬関数を持つマルチタスク設定について考察する。 我々は、分散された方法で全てのエージェントの割引された全報酬の総和を最大化する、世界的な最適政策を学習する。
  論文  参考訳（メタデータ） (2023-11-01T00:15:18Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。 マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
  論文  参考訳（メタデータ） (2023-05-08T16:20:03Z)
• Multi-resource allocation for federated settings: A non-homogeneous Markov chain model [2.552459629685159]
  連合設定において、エージェントは中央エージェントまたはサーバと協調し、エージェントが互いに情報を共有しない最適化問題を解決する。 本稿では,アジェント間通信のない単一共有リソースのフェデレーション設定における最適化問題のクラスを解決するために,AIMDアルゴリズムを簡単な方法で変更する方法について述べる。 シングルリソースのアルゴリズムを、スマートシティや共有エコノミー、その他多くのアプリケーションに出現する複数の異種共有リソースに拡張する。
  論文  参考訳（メタデータ） (2021-04-26T19:10:00Z)
• Quality-Diversity Optimization: a novel branch of stochastic optimization [5.677685109155078]
  マルチモーダル最適化アルゴリズムは、複数のことができる検索空間で最も高いピークを検索します。 品質多様性アルゴリズムは、進化的計算ツールボックスに最近追加されたもので、単一の局所光学系を探索するだけでなく、検索空間を照らそうとする。
  論文  参考訳（メタデータ） (2020-12-08T09:52:50Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。 様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。 我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
  論文  参考訳（メタデータ） (2020-11-18T18:39:17Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。 この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。 目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
  論文  参考訳（メタデータ） (2020-07-01T14:24:58Z)

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

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