論文の概要: Differentiable Bilevel Programming for Stackelberg Congestion Games
- arxiv url: http://arxiv.org/abs/2209.07618v1
- Date: Thu, 15 Sep 2022 21:32:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-19 13:36:47.709033
- Title: Differentiable Bilevel Programming for Stackelberg Congestion Games
- Title(参考訳): stackelberg congestionゲームのための微分可能双レベルプログラミング
- Authors: Jiayang Li, Jing Yu, Qianni Wang, Boyi Liu, Zhaoran Wang, Yu Marco Nie
- Abstract要約: Stackelberg Congestion Game (SCG) は、リーダーが利得を最大化するための二段階のプログラムである。
本研究は,従来の手法と機械学習の最新の発展を融合した,微分可能プログラミングによるSCGにアプローチする。
- 参考スコア(独自算出の注目度): 53.99859235245136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A Stackelberg congestion game (SCG) is a bilevel program in which a leader
aims to maximize their own gain by anticipating and manipulating the
equilibrium state at which followers settle by playing a congestion game.
Large-scale SCGs are well known for their intractability and complexity. This
study approaches SCGs through differentiable programming, which marries the
latest developments in machine learning with conventional methodologies. The
core idea centers on representing the lower-level equilibrium problem using an
evolution path formed by the imitative logit dynamics. It enables the use of
automatic differentiation over the evolution path towards equilibrium, leading
to a double-loop gradient descent algorithm. We further show the fixation on
the lower-level equilibrium may be a self-imposed computational obstacle.
Instead, the leader may only look ahead along the followers' evolution path for
a few steps, while updating their decisions in sync with the followers through
a co-evolution process. The revelation gives rise to a single-loop algorithm
that is more efficient in terms of both memory consumption and computation
time. Through numerical experiments that cover a wide range of benchmark
problems, we find the single-loop algorithm consistently strikes a good balance
between solution quality and efficiency, outperforming not only the standard
double-loop implementation but also other methods from the literature.
Importantly, our results highlight both the wastefulness of "full anticipation"
and the peril of "zero anticipation". If a quick-and-dirty heuristic is needed
for solving a really large SCG, the proposed single-loop algorithm with a
one-step look-ahead makes an ideal candidate.
- Abstract(参考訳): スタックルバーグ混雑ゲーム(英: stackelberg crowded game, scg)は、リーダーが、混雑ゲームを行うことでフォロワーが落ち着く平衡状態を予測し、操作することで、自身の利益を最大化することを目指す、二段階のプログラムである。
大規模scgはその難易度と複雑さでよく知られている。
本研究は,従来の手法と機械学習の最新の発展を融合した,微分可能プログラミングによるSCGにアプローチする。
核となるアイデアは、模倣ロジットダイナミクスによって形成された進化経路を用いて、低レベルの平衡問題を表現することに集中する。
これにより、平衡への進化経路上の自動微分が可能となり、二重ループ勾配降下アルゴリズムが実現される。
さらに, 低次平衡の固定は, 自発的計算障害である可能性が示唆された。
代わりに、リーダーはフォロワの進化経路に沿って数ステップしか前進しないが、共同進化プロセスを通じてフォロワと同期して決定を更新できる。
この啓示により、メモリ消費と計算時間の両方においてより効率的なシングルループアルゴリズムが生まれる。
幅広いベンチマーク問題をカバーする数値実験により、単一ループアルゴリズムはソリューションの品質と効率のバランスが良く、標準のダブルループ実装だけでなく、文献からの他の手法よりも優れていることがわかった。
以上より,「完全な期待」の無駄さと「ゼロ期待」の危険を浮き彫りにした。
非常に大きなSCGを解くためには、素早い経験則を必要とする場合、ワンステップルックアヘッドによるシングルループアルゴリズムが理想的な候補となる。
関連論文リスト
- Non-convex Bayesian Learning via Stochastic Gradient Markov Chain Monte
Carlo [4.656426393230839]
人工知能(AI)の台頭は、非トリップと不確実性のための現代のディープニューラルネットワーク(DNN)の効率性を重視している。
本論文ではモンテカルロ利用問題を扱うためのツールを提案する。
また,基礎となる正規方程式(ODE)システムに対する2つの動的重要度サンプリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-05-30T18:25:11Z) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-07-12T16:30:34Z) - Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。
我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
論文 参考訳(メタデータ) (2022-05-27T03:24:12Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳(メタデータ) (2022-01-28T20:26:55Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - Uncoupled Bandit Learning towards Rationalizability: Benchmarks,
Barriers, and Algorithms [41.307340085194625]
一般ゲームにおける最終点収束保証を合理化可能性へ向けて検討する。
この学習課題は、最高の腕識別問題を自然に一般化する。
そこで我々は,Exp3をDimishing Historical rewardsで調整するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-11-10T02:10:07Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳(メタデータ) (2020-06-17T22:11:35Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳(メタデータ) (2020-06-05T13:48:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。