論文の概要: Maximizing utility in multi-agent environments by anticipating the behavior of other learners

• arxiv url: http://arxiv.org/abs/2407.04889v1
• Date: Fri, 5 Jul 2024 23:16:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 22:07:12.921081
• Title: Maximizing utility in multi-agent environments by anticipating the behavior of other learners
• Title（参考訳）: 学習者の行動予測によるマルチエージェント環境におけるユーティリティの最大化
• Authors: Angelos Assos, Yuval Dagan, Constantinos Daskalakis,
• Abstract要約: マルチエージェント設定では、各エージェントの決定がユーティリティや他のエージェントに影響を与える可能性がある。 本稿では,2種類のエージェントを含む2人プレイヤゲームについて検討する。
• 参考スコア（独自算出の注目度）: 17.703508282875323
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Learning algorithms are often used to make decisions in sequential decision-making environments. In multi-agent settings, the decisions of each agent can affect the utilities/losses of the other agents. Therefore, if an agent is good at anticipating the behavior of the other agents, in particular how they will make decisions in each round as a function of their experience that far, it could try to judiciously make its own decisions over the rounds of the interaction so as to influence the other agents to behave in a way that ultimately benefits its own utility. In this paper, we study repeated two-player games involving two types of agents: a learner, which employs an online learning algorithm to choose its strategy in each round; and an optimizer, which knows the learner's utility function and the learner's online learning algorithm. The optimizer wants to plan ahead to maximize its own utility, while taking into account the learner's behavior. We provide two results: a positive result for repeated zero-sum games and a negative result for repeated general-sum games. Our positive result is an algorithm for the optimizer, which exactly maximizes its utility against a learner that plays the Replicator Dynamics -- the continuous-time analogue of Multiplicative Weights Update (MWU). Additionally, we use this result to provide an algorithm for the optimizer against MWU, i.e.~for the discrete-time setting, which guarantees an average utility for the optimizer that is higher than the value of the one-shot game. Our negative result shows that, unless P=NP, there is no Fully Polynomial Time Approximation Scheme (FPTAS) for maximizing the utility of an optimizer against a learner that best-responds to the history in each round. Yet, this still leaves open the question of whether there exists a polynomial-time algorithm that optimizes the utility up to $o(T)$.
• Abstract（参考訳）: 学習アルゴリズムはしばしば、シーケンシャルな意思決定環境で意思決定に使用される。 マルチエージェント設定では、各エージェントの判断は他のエージェントのユーティリティ/ロスに影響を与える可能性がある。 したがって、エージェントが他のエージェントの行動、特にその経験の関数として各ラウンドでどのように決定を行うかを予測するのに長けているなら、相互作用のラウンドに対して司法的に独自の決定をし、他のエージェントに影響を与え、最終的に自身の効用に恩恵を与えるようにすることができる。 本稿では,オンライン学習アルゴリズムを用いて各ラウンドの戦略を選択する学習者と,学習者のユーティリティ機能と学習者のオンライン学習アルゴリズムを知る最適化者という,2種類のエージェントを含む2種類の繰り返しゲームについて検討する。 最適化者は、学習者の振る舞いを考慮しつつ、自身のユーティリティを最大化する計画を立てている。 繰り返しゼロサムゲームに対する正の結果と、繰り返し一般サムゲームに対する負の結果の2つの結果を提供する。 我々の肯定的な結果はオプティマイザのアルゴリズムであり、マルチプライケーションウェイト更新(MWU)の連続的なアナログであるReplicator Dynamicsを再生する学習者に対して、その効用を正確に最大化する。 さらに、この結果を用いて、MWUに対する最適化アルゴリズム、すなわち離散時間設定に対して、ワンショットゲームよりも高いオプティマイザに対する平均効用を保証するアルゴリズムを提供する。 我々の否定的な結果は、P=NPがなければ、各ラウンドの履歴に対応する学習者に対して最適化器の効用を最大化する完全多項式時間近似スキーム(FPTAS)が存在しないことを示している。 しかし、このことは、ユーティリティを最大$o(T)$まで最適化する多項式時間アルゴリズムが存在するかどうかという疑問を残している。

関連論文リスト

• Learning to Play Against Unknown Opponents [9.346742321348366]
  本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。 これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
  論文  参考訳（メタデータ） (2024-12-24T09:05:06Z)
• Deep Learning Algorithms for Mean Field Optimal Stopping in Finite Space and Discrete Time [3.350071725971209]
  本研究は, エージェント数が無限に近づくにつれて得られる平均場最適停止(MFOS)問題を考察する。 本研究では,2つの深層学習手法を提案する。一方は最適決定を学習するために全軌道をシミュレートし,他方は逆方向誘導でDPPを利用する。 空間次元最大300の6つの異なる問題に対する数値実験により,これらの手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-10-11T14:27:17Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Meta-Wrapper: Differentiable Wrapping Operator for User Interest Selection in CTR Prediction [97.99938802797377]
  クリックスルー率(CTR)予測は、ユーザーが商品をクリックする確率を予測することを目的としており、リコメンデーションシステムにおいてますます重要になっている。 近年,ユーザの行動からユーザの興味を自動的に抽出する深層学習モデルが大きな成功を収めている。 そこで我々は,メタラッパー(Meta-Wrapper)と呼ばれるラッパー手法の枠組みに基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2022-06-28T03:28:15Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• ORSA: Outlier Robust Stacked Aggregation for Best- and Worst-Case Approximations of Ensemble Systems\ [0.0]
  半導体デバイスのためのポストシリコンバリデーション(PSV)では、複数の学習アルゴリズムでデータの基盤となる機能を近似することが課題である。 PSVでは、未知の数のサブセットが、非常に異なる特性を示す関数を記述することが期待されている。 本手法は, オフレーヤに対して堅牢で, 可能な限り多くの型に適用可能な, 最良の, 最悪のケースを示す適切な近似を求めることを目的としている。
  論文  参考訳（メタデータ） (2021-11-17T11:33:46Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games [102.23975166536326]
  tree-form sequential decision making (tfsdm) は、エージェントと潜在的に敵対的な環境の間のツリー形式の相互作用をモデル化することで、古典的なワンショット意思決定を拡張する。 これは、各プレイヤーが幅広い形式のゲームで直面するオンライン意思決定問題、およびマルコフ決定プロセス、およびエージェントが観測された履歴を条件とする部分観察可能なマルコフ決定プロセスをキャプチャする。 本稿では, (i) 線形時間損失と (ii) $o(sqrtt)$ cumulative regret の両方を提供する拡張dmのバンディット線形最適化問題に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-08T05:00:13Z)
• Time Efficiency in Optimization with a Bayesian-Evolutionary Algorithm [13.66850118870667]
  すべての生成とテストの検索アルゴリズムが等しく作られているわけではないことを示す。 本稿では,ベイズ最適化と進化的アルゴリズムを組み合わせた新しいアルゴリズムBEAを提案する。 その結果、BEA は BO と EA の両方を時間効率で上回り、最終的には多くの局所最適値を持つよく知られたベンチマーク対象関数の性能が向上することがわかった。
  論文  参考訳（メタデータ） (2020-05-04T15:29:22Z)

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

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