論文の概要: Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees

• arxiv url: http://arxiv.org/abs/2306.00172v1
• Date: Wed, 31 May 2023 20:41:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-02 19:27:32.600055
• Title: Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees
• Title（参考訳）: ロバスト性保証によるエッジ重み付きオンライン2部マッチングの学習
• Authors: Pengfei Li, Jianyi Yang, Shaolei Ren
• Abstract要約: 我々は,ロバストネス保証 (LOMAR) を用いたエッジ重み付きオンラインバイパートイトマッチングの新しい手法を提案する。 LOMARは、平均ケースと最悪のケースのパフォーマンスの両方を達成する。
• 参考スコア（独自算出の注目度）: 28.737193318136725
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Many problems, such as online ad display, can be formulated as online bipartite matching. The crucial challenge lies in the nature of sequentially-revealed online item information, based on which we make irreversible matching decisions at each step. While numerous expert online algorithms have been proposed with bounded worst-case competitive ratios, they may not offer satisfactory performance in average cases. On the other hand, reinforcement learning (RL) has been applied to improve the average performance, but it lacks robustness and can perform arbitrarily poorly. In this paper, we propose a novel RL-based approach to edge-weighted online bipartite matching with robustness guarantees (LOMAR), achieving both good average-case and worst-case performance. The key novelty of LOMAR is a new online switching operation which, based on a judicious condition to hedge against future uncertainties, decides whether to follow the expert's decision or the RL decision for each online item. We prove that for any $\rho\in[0,1]$, LOMAR is $\rho$-competitive against any given expert online algorithm. To improve the average performance, we train the RL policy by explicitly considering the online switching operation. Finally, we run empirical experiments to demonstrate the advantages of LOMAR compared to existing baselines. Our code is available at: https://github.com/Ren-Research/LOMAR
• Abstract（参考訳）: オンライン広告表示などの多くの問題は、オンラインの2部マッチングとして定式化することができる。 重要な課題は、各ステップで不可逆的なマッチング決定を行うオンラインアイテム情報のシーケンシャルな展開にある。 多くの専門的なオンラインアルゴリズムが、限定された最悪のケースの競合比率で提案されているが、平均的なケースでは十分な性能を提供できない可能性がある。 一方、強化学習(RL)は平均性能向上に応用されているが、頑健性に欠け、任意に性能が劣る。 本稿では,ロバスト性保証 (LOMAR) とエッジ重み付きオンライン双極子マッチング (RL) に対する新しいアプローチを提案する。 lomar の重要な新機能は,将来的な不確実性に対してヘッジするための賢明な条件に基づいて,専門家の判断に従うか,あるいは各オンラインアイテムのrl決定に従うかを決定する,新たなオンラインスイッチング操作である。 我々は、任意の$\rho\in[0,1]$に対して、LOMARが任意の専門家オンラインアルゴリズムに対して$\rho$-competitiveであることを証明する。 平均性能を向上させるため、オンラインスイッチング操作を明示的に考慮してRLポリシーを訓練する。 最後に,既存のベースラインと比較してLOMARの利点を示す実験を行った。 私たちのコードは、https://github.com/Ren-Research/LOMARで利用可能です。

関連論文リスト

• Unsupervised-to-Online Reinforcement Learning [59.910638327123394]
  Unsupervised-to-online RL (U2O RL) は、ドメイン固有の教師なしオフラインRLを非教師なしオフラインRLに置き換える。 U2O RLは、複数の下流タスクのために訓練済みのモデルを再利用できるだけでなく、より良い表現も学べる。 U2O RLは、従来のオフライン-オフラインのRLアプローチにマッチしたり、さらに性能が優れていることを実証的に実証する。
  論文  参考訳（メタデータ） (2024-08-27T05:23:45Z)
• Bayesian Design Principles for Offline-to-Online Reinforcement Learning [50.97583504192167]
  オフラインからオンラインへの微調整は、探索にコストがかかる、あるいは安全でない、現実世界のアプリケーションにとって極めて重要です。 本稿では,オフラインからオフラインまでの微調整のジレンマに対処する:エージェントが悲観的のままであれば,より良いポリシーを習得できないかもしれないが,楽観的になった場合,性能が突然低下する可能性がある。 このようなジレンマを解決するにはベイズ設計の原則が不可欠であることを示す。
  論文  参考訳（メタデータ） (2024-05-31T16:31:07Z)
• Understanding the performance gap between online and offline alignment algorithms [63.137832242488926]
  オフラインのアルゴリズムは、ペアの分類が得意になるようにポリシーを訓練し、オンラインのアルゴリズムは世代ごとに良いことを示しています。 このことは、識別能力と生成能力の間のユニークな相互作用を示唆しており、これはサンプリングプロセスに大きく影響している。 我々の研究は、AIアライメントにおけるオンラインサンプリングの重要な役割に光を当て、オフラインアライメントアルゴリズムのある種の根本的な課題を示唆している。
  論文  参考訳（メタデータ） (2024-05-14T09:12:30Z)
• More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning [58.626683114119906]
  本研究では,分散強化学習(DistRL)がオンラインとオフラインのRLの2次境界を得ることができることを示す。 我々の結果は、低ランク MDP とオフライン RL に対する最初の2階境界である。
  論文  参考訳（メタデータ） (2024-02-11T13:25:53Z)
• Learning-augmented Online Algorithm for Two-level Ski-rental Problem [8.381344684943212]
  本研究では,3つの支払いオプションのうちの1つを選択することで,複数の項目に対する要求の順序を満たす必要がある2段階のスキーレンタル問題について検討する。 我々は、機械学習予測を頑健なオンラインアルゴリズムに組み込むことにより、学習増強アルゴリズム(LADTSR)を開発した。
  論文  参考訳（メタデータ） (2024-02-09T16:10:54Z)
• Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient [42.47810044648846]
  エージェントがオフラインのデータセットにアクセスでき、実世界のオンラインインタラクションを通じて経験を収集できるハイブリッド強化学習環境(Hybrid RL)を検討する。 従来のQラーニング/イテレーションアルゴリズムをハイブリッド環境に適用し,ハイブリッドQラーニングやHy-Qと呼ぶ。 ニューラルネットワーク関数近似を用いたHy-Qは、挑戦的なベンチマークにおいて、最先端のオンライン、オフライン、ハイブリッドRLベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-13T04:19:05Z)
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach [5.683591363967851]
  本稿では,過去のデータに対する試行錯誤に基づく適切な対応策を導出するためのエンドツーエンド強化学習フレームワークを提案する。 学習手法の大部分は,4つの合成および実世界のデータセットにおいて,古典的なグリーディアルゴリズムよりもはるかに優れていることを示す。
  論文  参考訳（メタデータ） (2021-09-21T18:04:19Z)
• Fairness Maximization among Offline Agents in Online-Matching Markets [18.689388188794023]
  マッチングマーケットには、相互利益のためにペアを組む異種エージェント(典型的には2つのパーティから)が含まれる。 OMMと従来のマッチング市場を区別する2つの特徴がある。 個人レベルのフェアネスとグループレベルのフェアネスを最適化するオンラインマッチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-18T13:41:42Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)

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

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