論文の概要: New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2207.09588v1
• Date: Tue, 19 Jul 2022 23:31:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-21 14:15:44.756805
• Title: New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning
• Title（参考訳）: 経路計画、ネットワーク輸送、強化学習のための新しいオークションアルゴリズム
• Authors: Dimitri Bertsekas
• Abstract要約: 最適および準最適解に対する新しいオークションベースのアルゴリズムを提案する。 アルゴリズムは、オブジェクトの人による競争入札に関連する数学的アイデアに基づいている。 新しいアルゴリズムは、既存の手法よりもいくつかの潜在的な利点がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider some classical optimization problems in path planning and network transport, and we introduce new auction-based algorithms for their optimal and suboptimal solution. The algorithms are based on mathematical ideas that are related to competitive bidding by persons for objects and the attendant market equilibrium, which underlie auction processes. However, the starting point of our algorithms is different, namely weighted and unweighted path construction in directed graphs, rather than assignment of persons to objects. The new algorithms have several potential advantages over existing methods: they are empirically faster in some important contexts, such as max-flow, they are well-suited for on-line replanning, and they can be adapted to distributed asynchronous operation. Moreover, they allow arbitrary initial prices, without complementary slackness restrictions, and thus are better-suited to take advantage of reinforcement learning methods that use off-line training with data, as well as on-line training during real-time operation. The new algorithms may also find use in reinforcement learning contexts involving approximation, such as multistep lookahead and tree search schemes, and/or rollout algorithms.
• Abstract（参考訳）: 経路計画とネットワーク転送における古典的な最適化問題について考察し,その最適および準最適解に対する新しいオークションベースのアルゴリズムを提案する。 アルゴリズムは、物を求める人による競争入札に関連する数学的アイデアと、競売プロセスを支える付随する市場均衡に基づいている。 しかし、我々のアルゴリズムの出発点は、対象への人の割り当てではなく、有向グラフにおける重み付けと非重み付けのパス構成が異なる。 新しいアルゴリズムは、既存のメソッドに対していくつかの潜在的な利点がある。最大フローのような重要なコンテキストで経験的に高速であり、オンラインのリプランニングに適しており、分散非同期操作に適応できる。 さらに、スラック性制限を補うことなく、任意の初期価格を許容するので、オフライントレーニングやリアルタイム操作時のオンライントレーニングを使用する強化学習手法を活用できる。 この新しいアルゴリズムは、マルチステップのルックアヘッドやツリー検索スキーム、および/またはロールアウトアルゴリズムなどの近似を含む強化学習コンテキストにも使われる。

関連論文リスト

• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  我々は、中間的監督に訴えることなく、入出力ペアからのみニューラルネットワーク推論を学ぶことに集中する。 我々は、アルゴリズムの軌跡にアクセスできることなく、モデルの中間計算を正規化できる自己教師対象を構築する。 CLRSic Algorithmic Reasoning Benchmarkのタスクにおいて,提案手法はトラジェクトリを教師する手法と競合することを示す。
  論文  参考訳（メタデータ） (2023-06-23T09:57:44Z)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。 妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。 このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
  論文  参考訳（メタデータ） (2023-05-17T06:22:11Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Federated Learning with a Sampling Algorithm under Isoperimetry [9.990687944474738]
  フェデレーション学習は、機械学習アルゴリズムのトレーニングを複数のデバイスに効率的に分散するために、一連のテクニックを使用する。 本稿では,Langevinvin のサンプル Aafteri の通信効率のよい変種を提案する。
  論文  参考訳（メタデータ） (2022-06-02T08:19:03Z)
• An Improved Reinforcement Learning Algorithm for Learning to Branch [12.27934038849211]
  ブランチ・アンド・バウンド(B&B)は最適化の一般的な方法である。 本稿では,新しい強化学習に基づくB&Bアルゴリズムを提案する。 提案アルゴリズムの性能を3つの公開研究ベンチマークで評価した。
  論文  参考訳（メタデータ） (2022-01-17T04:50:11Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。 提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。 我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
  論文  参考訳（メタデータ） (2021-10-08T07:22:45Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
  本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。 高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。 我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
  論文  参考訳（メタデータ） (2020-11-09T10:57:21Z)

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

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