論文の概要: Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards
- arxiv url: http://arxiv.org/abs/2608.18130v1
- Date: Fri, 24 Jul 2026 13:51:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-23 14:54:39.985225
- Title: Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards
- Title（参考訳）: 非定常逆流下における再使用能力をもつオンラインバイパートイトマッチング
- Abstract要約: 本稿では,再利用可能なサーバ容量と非定常報酬を考慮したオンライン双方向マッチングについて検討する。
BALANCE型アルゴリズムを2つのアルゴリズムで開発し、時間に合った機会コストの損失を発生させる。
数値実験は、大域的な報奨ドリフトの下で頑健な性能を示す。
- 参考スコア（独自算出の注目度）: 9.228828803371668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online bipartite matching with reusable server capacity and non-stationary rewards. Jobs arrive sequentially, reveal compatible servers, reward rates, and processing durations, and must be accepted or rejected irrevocably. An accepted job occupies one unit of server capacity only during its processing interval, so an assignment may displace an unknown sequence of future jobs. Existing guarantees are typically calibrated by a global reward range, which can become arbitrarily large when rewards drift over a long horizon. We instead impose a locally bounded reward condition: reward rates of jobs that can compete for the same server within a relevant time window differ by at most a factor $δ$. Under this condition, we develop two BALANCE-type algorithms with time-aware opportunity-cost losses. TS-BAL maximizes cumulative blocking losses over feasible reuse schedules and achieves a competitive ratio of $2\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$. GR-BAL uses a greedy relaxation of this loss and achieves $\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$, matching a lower bound of $\ln(δD)$ in the leading term. Numerical experiments demonstrate robust performance under substantial global reward drift and favorable finite-capacity performance.
- Abstract（参考訳）: 本稿では,再利用可能なサーバ容量と非定常報酬を考慮したオンライン双方向マッチングについて検討する。
ジョブは順次到着し、互換性のあるサーバ、報酬率、処理期間を明らかにする。
受理されたジョブはその処理間隔でのみサーバ容量の1つの単位を占有するので、代入は将来のジョブの未知のシーケンスを置き換える可能性がある。
既存の保証は、通常、グローバルな報酬範囲によって調整される。
代わりに、局所的に制限された報酬条件を課す: 関連する時間枠内で同じサーバで競合できるジョブの報酬率は、少なくとも$δ$は異なる。
この条件下では,時間を考慮した機会コスト損失を考慮した2つのBALANCE型アルゴリズムを開発した。
TS-BALは、実現可能な再利用可能なスケジュールに対する累積的ブロッキング損失を最大化し、競合比は2.2\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$である。
GR-BALはこの損失のゆるやかな緩和を使い、先頭項で$\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$を下限とする。
数値実験は、大域的な報酬ドリフトと良好な有限容量性能の下で頑健な性能を示す。
関連論文リスト
- MARBLE: Multi-Aspect Reward Balance for Diffusion RL [71.6241143519038]
強化学習は、拡散モデルと人間の嗜好を整合させる主要なアプローチとなっている。
既存のプラクティスは、報酬ごとに1つのスペシャリストモデルをトレーニングすることで、複数の報酬を処理します。
我々は,各報酬に対する独立な優位推定器を維持する勾配空間最適化フレームワークMARBLEを提案する。
論文 参考訳（メタデータ） (2026-05-07T16:20:42Z) - Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
分散パラメータ-サーバ-ワーカー設定における乱数ベクトル$X$の推定について検討する。
主な課題は、敵の計測と非同期である。
その結果, 分散線形推定におけるロバスト性, 識別性, 統計的効率の統一的有限時間評価が得られた。
論文 参考訳（メタデータ） (2026-04-07T11:45:55Z) - Likelihood-Based Reward Designs for General LLM Reasoning [17.640897774014707]
強化学習による微調整された大きな言語モデルは、ベンチマーク毎に特定の報酬関数、しばしばバイナリを必要とする。
ここでは,基準解を出力する確率や対数確率から得られる報酬について検討する。
連鎖学習の報奨として参照回答の対数確率を用いることが,すべての設定において良好に機能する唯一の選択肢であることがわかった。
論文 参考訳（メタデータ） (2026-02-03T20:04:21Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - Uncertainty-Aware Reward-Free Exploration with General Function Approximation [69.27868448449755]
本稿では、algと呼ばれる報酬のない強化学習アルゴリズムを提案する。
私たちのアルゴリズムの背後にある重要なアイデアは、環境を探索する上で不確実性を認識した本質的な報酬である。
実験の結果、GFA-RFEは最先端の教師なしRLアルゴリズムよりも優れ、あるいは同等であることがわかった。
論文 参考訳（メタデータ） (2024-06-24T01:37:18Z) - Learning to Schedule Online Tasks with Bandit Feedback [7.671139712158846]
オンラインタスクスケジューリングは、クラウドコンピューティングやクラウドソーシングにおけるタスク集約型アプリケーションにおいて重要な役割を果たす。
本稿では,二重最適化学習に基づくRobins-Monro(DOL-RM)アルゴリズムを提案する。
DOL-RMは、報酬対コスト比の楽観的な推定と決定モジュールを組み込んだ学習モジュールを統合する。
論文 参考訳（メタデータ） (2024-02-26T10:11:28Z) - Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee
for Improving Bandits [6.537940428724029]
腕から得られる報酬が、受信したプル数に応じて増加するIMAB問題について検討する。
我々の主な貢献は、最良の累積報酬を達成するIMAB問題に対する任意のアルゴリズムである。
論文 参考訳（メタデータ） (2022-08-19T10:23:40Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards [7.519872646378837]
本稿では,ジョブサーバの割り当てが不確実なマルチクラス並列サーバシステムにおけるスケジューリングの問題について考察する。
我々の目標は、時間軸上でのジョブサーバ割り当ての累積報酬を最大化することで、後悔を最小限に抑えることです。
提案アルゴリズムは,サブリニア・リセット・バウンドとサブリニア平均保持コストを実現する。
論文 参考訳（メタデータ） (2021-12-13T00:37:20Z) - Communication Contention Aware Scheduling of Multiple Deep Learning
Training Jobs [17.45154289084637]
我々は、DDLジョブをDAG(Directed Acyclic Graphs)として整理する新しいDDLジョブスケジューリングフレームワークを確立する。
次に、GPU利用のバランスを保ち、各ジョブに割り当てられたGPUを統合するための効率的なアルゴリズム LWF-$kappa$ を提案する。
LWF-$kappa$は、古典的なファーストフィットアルゴリズムよりも最大$1.59タイムで改善できることを示す。
論文 参考訳（メタデータ） (2020-02-24T07:50:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。