論文の概要: Computational Intractability of Strategizing against Online Learners
- arxiv url: http://arxiv.org/abs/2503.04202v1
- Date: Thu, 06 Mar 2025 08:28:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-07 15:57:45.038872
- Title: Computational Intractability of Strategizing against Online Learners
- Title（参考訳）: オンライン学習者に対するストラテジジングの計算的抽出性
- Authors: Angelos Assos, Yuval Dagan, Nived Rajaraman,
- Abstract要約: 本稿では,学習者に対する準最適戦略を,標準の非回帰アルゴリズムで計算可能であることを示す。
これにより、一般的なゲーム理論の設定において最適な戦略を見つけるための基本的な計算障壁が確立される。
- 参考スコア（独自算出の注目度）: 7.225039292056237
- License:
- Abstract: Online learning algorithms are widely used in strategic multi-agent settings, including repeated auctions, contract design, and pricing competitions, where agents adapt their strategies over time. A key question in such environments is how an optimizing agent can best respond to a learning agent to improve its own long-term outcomes. While prior work has developed efficient algorithms for the optimizer in special cases - such as structured auction settings or contract design - no general efficient algorithm is known. In this paper, we establish a strong computational hardness result: unless $\mathsf{P} = \mathsf{NP}$, no polynomial-time optimizer can compute a near-optimal strategy against a learner using a standard no-regret algorithm, specifically Multiplicative Weights Update (MWU). Our result proves an $\Omega(T)$ hardness bound, significantly strengthening previous work that only showed an additive $\Theta(1)$ impossibility result. Furthermore, while the prior hardness result focused on learners using fictitious play - an algorithm that is not no-regret - we prove intractability for a widely used no-regret learning algorithm. This establishes a fundamental computational barrier to finding optimal strategies in general game-theoretic settings.
- Abstract（参考訳）: オンライン学習アルゴリズムは、繰り返しオークション、契約設計、価格競争など、戦略的なマルチエージェント設定で広く使用されている。
このような環境における重要な疑問は、最適化エージェントが学習エージェントにどのように最もよく反応し、長期的な結果を改善するかである。
以前の研究では、構造化されたオークション設定やコントラクト設計など、特別な場合における最適化のための効率的なアルゴリズムが開発されたが、一般的な効率的なアルゴリズムは知られていない。
本稿では, 多項式時間オプティマイザが, $\mathsf{P} = \mathsf{NP}$でない限り, 標準的な非回帰アルゴリズム, 特にMultiplicative Weights Update (MWU) を用いて学習者に対する準最適戦略を計算できない。
我々の結果は、$\Omega(T)$硬さ境界を証明し、付加的な$\Theta(1)$不合理結果のみを示す以前の研究を大幅に強化する。
さらに, 従来の難易度は, 虚偽プレイ(非回帰学習アルゴリズム)を用いた学習者に焦点を当てていたが, 広く使われている非回帰学習アルゴリズムの難易度が証明された。
これにより、一般的なゲーム理論の設定において最適な戦略を見つけるための基本的な計算障壁が確立される。
関連論文リスト
- Learning to Play Against Unknown Opponents [9.346742321348366]
本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。
これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
論文 参考訳（メタデータ） (2024-12-24T09:05:06Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
論文 参考訳（メタデータ） (2022-01-19T22:21:21Z) - A Pragmatic Look at Deep Imitation Learning [0.3626013617212666]
我々は6つの異なる対向的模倣学習アルゴリズムを再実装する。
広く使われている専門的軌跡データセットで評価する。
GAILは、様々なサンプルサイズにわたって、一貫してよく機能する。
論文 参考訳（メタデータ） (2021-08-04T06:33:10Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z) - Quantum algorithms for hedging and the learning of Ising models [6.346764987071066]
オンライン学習のためのパラダイムアルゴリズムは、FreundとSchapireのHedgeアルゴリズムである。
この研究は、このようなオンライン学習のための量子アルゴリズムを論理的に提示する。
論文 参考訳（メタデータ） (2020-02-14T12:48:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。