論文の概要: Learning to Play Against Unknown Opponents

• arxiv url: http://arxiv.org/abs/2412.18297v2
• Date: Thu, 20 Feb 2025 07:17:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:24:39.565770
• Title: Learning to Play Against Unknown Opponents
• Title（参考訳）: 未知の反対者に対する遊び方を学ぶ
• Authors: Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider,
• Abstract要約: 本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。 これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
• 参考スコア（独自算出の注目度）: 9.346742321348366
• License:
• Abstract: We consider the problem of a learning agent who has to repeatedly play a general sum game against a strategic opponent who acts to maximize their own payoff by optimally responding against the learner's algorithm. The learning agent knows their own payoff function, but is uncertain about the payoff of their opponent (knowing only that it is drawn from some distribution $\mathcal{D}$). What learning algorithm should the agent run in order to maximize their own total utility, either in expectation or in the worst-case over $\mathcal{D}$? When the learning algorithm is constrained to be a no-regret algorithm, we demonstrate how to efficiently construct an optimal learning algorithm (asymptotically achieving the optimal utility) in polynomial time for both the in-expectation and worst-case problems, independent of any other assumptions. When the learning algorithm is not constrained to no-regret, we show how to construct an $\varepsilon$-optimal learning algorithm (obtaining average utility within $\varepsilon$ of the optimal utility) for both the in-expectation and worst-case problems in time polynomial in the size of the input and $1/\varepsilon$, when either the size of the game or the support of $\mathcal{D}$ is constant. Finally, for the special case of the maximin objective, where the learner wishes to maximize their minimum payoff over all possible optimizer types, we construct a learner algorithm that runs in polynomial time in each step and guarantees convergence to the optimal learner payoff. All of these results make use of recently developed machinery that converts the analysis of learning algorithms to the study of the class of corresponding geometric objects known as menus.
• Abstract（参考訳）: 本稿では,学習者のアルゴリズムに最適に対応することで,自己の利益を最大化するために行動する戦略的相手に対して,総合的な総和ゲームを繰り返し行う学習エージェントの問題を考える。 学習エージェントは、自身のペイオフ関数を知っているが、相手のペイオフについて不確実である(ある分布から引き出されることのみを知っていれば、$\mathcal{D}$である)。 エージェントは、期待または最悪の場合の$\mathcal{D}$に対して、自身の全ユーティリティを最大化するために、どのような学習アルゴリズムを実行するべきか? 学習アルゴリズムが非回帰アルゴリズムであると制約された場合、他の仮定とは無関係に、多項式時間で最適学習アルゴリズム(漸近的に最適効用を達成する)を効率的に構築する方法を実証する。 学習アルゴリズムがno-regretに制約されない場合、ゲームのサイズや$\mathcal{D}$のサポートが一定である場合、入力サイズにおける時間多項式のin-expectation問題と worst-case問題の両方に対して、$\varepsilon$-Optimal Learningアルゴリズム(最適ユーティリティの$\varepsilon$内で平均ユーティリティを得る)を構築する方法を示す。 最後に、学習者が全ての可能なオプティマイザタイプに対して最小限のペイオフを最大化したい場合、各ステップで多項式時間で実行し、最適な学習者ペイオフへの収束を保証する学習者アルゴリズムを構築する。 これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。

関連論文リスト

• Maximizing utility in multi-agent environments by anticipating the behavior of other learners [17.703508282875323]
  マルチエージェント設定では、各エージェントの決定がユーティリティや他のエージェントに影響を与える可能性がある。 本稿では,2種類のエージェントを含む2人プレイヤゲームについて検討する。
  論文  参考訳（メタデータ） (2024-07-05T23:16:18Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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