論文の概要: Deep Policies for Online Bipartite Matching: A Reinforcement Learning
Approach
- arxiv url: http://arxiv.org/abs/2109.10380v1
- Date: Tue, 21 Sep 2021 18:04:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-24 00:36:50.494108
- Title: Deep Policies for Online Bipartite Matching: A Reinforcement Learning
Approach
- Title(参考訳): オンライン双方向マッチングのためのディープポリシー:強化学習アプローチ
- Authors: Mohammad Ali Alomrani, Reza Moravej, Elias B. Khalil
- Abstract要約: 本稿では,過去のデータに対する試行錯誤に基づく適切な対応策を導出するためのエンドツーエンド強化学習フレームワークを提案する。
学習手法の大部分は,4つの合成および実世界のデータセットにおいて,古典的なグリーディアルゴリズムよりもはるかに優れていることを示す。
- 参考スコア(独自算出の注目度): 5.683591363967851
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: From assigning computing tasks to servers and advertisements to users,
sequential online matching problems arise in a wide variety of domains. The
challenge in online matching lies in making irrevocable assignments while there
is uncertainty about future inputs. In the theoretical computer science
literature, most policies are myopic or greedy in nature. In real-world
applications where the matching process is repeated on a regular basis, the
underlying data distribution can be leveraged for better decision-making. We
present an end-to-end Reinforcement Learning framework for deriving better
matching policies based on trial-and-error on historical data. We devise a set
of neural network architectures, design feature representations, and
empirically evaluate them across two online matching problems: Edge-Weighted
Online Bipartite Matching and Online Submodular Bipartite Matching. We show
that most of the learning approaches perform significantly better than
classical greedy algorithms on four synthetic and real-world datasets. Our code
is publicly available at https://github.com/lyeskhalil/CORL.git.
- Abstract(参考訳): コンピューティングタスクをサーバや広告に割り当てることから、シーケンシャルなオンラインマッチング問題はさまざまなドメインで発生します。
オンラインマッチングの課題は、将来の入力について不確実性がある間、取り消せない割り当てを行うことである。
理論計算機科学の文献では、ほとんどの政策はミオピックまたは自然の欲望である。
マッチングプロセスが定期的に繰り返される現実世界のアプリケーションでは、基礎となるデータ分布をより良い意思決定のために利用することができる。
本稿では,歴史データに対する試行錯誤に基づくマッチングポリシを導出するためのエンドツーエンド強化学習フレームワークを提案する。
我々は、一連のニューラルネットワークアーキテクチャ、設計特徴表現を考案し、2つのオンラインマッチング問題(エッジ重み付きオンライン2部マッチングとオンラインサブモジュラー2部マッチング)を経験的に評価する。
4つの合成データと実世界のデータセットにおいて,学習アプローチのほとんどが,古典的な欲望アルゴリズムよりも優れた性能を示す。
私たちのコードはhttps://github.com/lyeskhalil/corl.gitで公開しています。
関連論文リスト
- Learning for Edge-Weighted Online Bipartite Matching with Robustness
Guarantees [28.737193318136725]
我々は,ロバストネス保証 (LOMAR) を用いたエッジ重み付きオンラインバイパートイトマッチングの新しい手法を提案する。
LOMARは、平均ケースと最悪のケースのパフォーマンスの両方を達成する。
論文 参考訳(メタデータ) (2023-05-31T20:41:42Z) - GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed
Graph Neural Networks [68.61934077627085]
本稿では,グラフ埋め込みを学習可能なGNNと互換性のあるモデリングフレームワークであるGNNRankを紹介する。
既存の手法と比較して,我々の手法が競争力があり,しばしば優れた性能を発揮することを示す。
論文 参考訳(メタデータ) (2022-02-01T04:19:50Z) - Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。
私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
論文 参考訳(メタデータ) (2021-11-19T15:48:43Z) - Combining Online Learning and Offline Learning for Contextual Bandits
with Deficient Support [53.11601029040302]
現在のオフライン政治学習アルゴリズムは、主に逆確率スコア(IPS)重み付けに基づいている。
オフライン学習とオンライン探索を組み合わせた新しい手法を提案する。
提案手法は,最小限のオンライン探索数を用いて理論的保証を伴う最適政策を決定する。
論文 参考訳(メタデータ) (2021-07-24T05:07:43Z) - Online Adversarial Attacks [57.448101834579624]
我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。
まず、オンライン脅威モデルの決定論的変種を厳格に分析する。
このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
論文 参考訳(メタデータ) (2021-03-02T20:36:04Z) - Learning Robust Algorithms for Online Allocation Problems Using
Adversarial Training [10.14260510961573]
機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。
本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
論文 参考訳(メタデータ) (2020-10-16T14:33:11Z) - Learning to Match Jobs with Resumes from Sparse Interaction Data using
Multi-View Co-Teaching Network [83.64416937454801]
ジョブ列のインタラクションデータは疎結合でノイズが多く、ジョブ列のマッチングアルゴリズムのパフォーマンスに影響する。
求人情報マッチングのための疎相互作用データから,新しいマルチビュー協調学習ネットワークを提案する。
我々のモデルは求人マッチングの最先端手法より優れている。
論文 参考訳(メタデータ) (2020-09-25T03:09:54Z) - Active Online Learning with Hidden Shifting Domains [64.75186088512034]
本稿では,その後悔度とラベルクエリ数とを適応的にバランスさせる,驚くほど単純なアルゴリズムを提案する。
我々のアルゴリズムは、異なる領域からの入力のインターリービングスパンを適応的に処理できる。
論文 参考訳(メタデータ) (2020-06-25T15:23:59Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Unbiased Learning to Rank: Online or Offline? [28.431648823968278]
偏りのあるユーザフィードバックでランク付けすることを学ぶことで、偏りのないランキングモデルを得る方法が、IRにとって重要な研究課題である。
既存の非バイアス付き学習のランク付けの研究は、ログデータを用いた非バイアス付き学習アルゴリズムの研究と、リアルタイムユーザインタラクションによる非バイアス付きパラメータ推定の研究という、2つのグループに大別することができる。
本稿では,非偏見学習をランク付けするタスクを形式化し,オフライン非偏見学習とオンライン学習をランク付けするための既存のアルゴリズムが,同じコインの両面にのみ存在することを示す。
論文 参考訳(メタデータ) (2020-04-28T15:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。